Constraint Solving and Planning with Picat

by Agostino Dovier

Logic programming languages entered  the scene of computer science in the early seventies as the answer to the need of paradigms capable of representing and reasoning about  different kinds of knowledge. The big picture pursued by logic programming researchers was to create a black-box system able to transform  declarative and logic-based specifications into actionable problem solutions  (``the holy grail of programming'', as some authors say).

The history of logic programming witnessed periods of genuine enthusiasm and leaps of knowlege and stagnation stages.  The  initial proposal of the language Prolog by Robert Kowalski came with the drawback of the inefficiency of its first implementation of the SLD resolution procedure. As a consequence,  the AI community, looking for fast implementations of planning algorithms, moved towards other directions---from the  (functionally-inspired) PDDL modeling language, the de facto standard formalism for planning problem descriptions, to the use of traditional imperative languages.

In the early eighties, results from unification theory and the implementation of the Warren Abstract Machine by D.H.D. Warren sensibly improved the efficiency of the Prolog implementations---enabling compilation of programs into efficiently executable bytecode. In the same years, the AI problem solving community developed the notion of contraint propagation and constrained-based search; this declarative formalisms required an host language to be effectively exploited. Researchers in the U.S. (e.g., Joxan Jaffar, Jan-Louis Lassez, Michael Maher, Peter Stuckey) and in Europe (e.g., Pascal Van Hentenryck), on the wave of the Fifth Generation project, offered effective frameworks and implementations to enable the parametric extension of the Prolog language into a constraint-based framework. Constraint Logic Programming is a class of logic programming languages which are parametrical w.r.t. an external constraint solver. This extension of Prolog allowed the efficient resolution of large classes of practical problems and constituted a common research path for the logic programming and constraint programming communities.

However, logic programming and constraint logic programming continued to fall short of expectations in the context of knowledge representation and reasoning: the original declarative semantics developed for Prolog and preserved by  constraint logic programming struggled to meet the needs of non-monotonic reasoning. An elegant and effective solution to this problem arose from the work of Michael Gelfond and Vladimir Lifschitz, embodied by the stable model semantics for logic programming with negation as failure. It took almost ten years for researchers to understand how to effectively embed such semantics in a Prolog-style language, leading to a novel paradigm, commonly referred to as Answer Set Programming (ASP). Planning problems are  naturally encoded in ASP, and also directly as a SAT formula, exploiting the progresses in this area. In this millennium, the idea of conflict-driven  learning has been introduced  in both  ASP solvers and  SAT solvers, making these systems highly effective in solving complex and large problems.  In parallel with the ASP evolution, the notion of tabling/memoization was introduced by D.S. Warren and implemented in Prolog systems (including B-Prolog by Neng-Fa Zhou). Tabling allows Prolog systems to avoid the recomputation of sub-goals and can be used also in supporting dynamic programming-style optimizations. A good use of tabling has been proved to speed-up the search, in particular in solving planning problems.

The language Picat, subject of this book,  is the culminating event of all this story.The language is as declarative as Prolog, it supports the encoding of  problems using constraints, and it enables the  search for solutions using of constraint and SAT solvers. Picat provides the use of tabling in  its full power; in particular, Picat allows us to encode planning problems in a programming style similar to PDDL, and their fast resolution thanks to  tabling.

I do not know if Picat is already ``the holy grail,'' but surely a generation of students/programmers can benefit a lot from this language. This book provides the perfect compendium to  enter  the fascinating  universe of Picat.