Answer Set Programming

In our paper Stable Logic Programming - a New Logic Programming Paradigm, we discussed a place and role of stable model semantics in declarative programming and knowledge representation. We proposed there that logic programming with stable model semantics is a programming tool well-suited for modeling and solving search problems, including problems in planning, reasoning about action, constraint satisfaction, combinatorics and combinatorial optimization.

The idea is this: to solve a search problem P for a paticular instance I, we encode the instance as the set of ground facts, say D(I), and we encode the specification of the problem P as a logic program D(P) so that solutions to P for the input I are represented by stable models of the program obtained as the union of D(P) and D(I). In this way, an automated reasoning system for computing stable models of logic programs can be used as a general problem solving engine for a wide class of search problems. For instance, a planning problem can be encoded by a logic program and the specific input (initial configuration, goal, etc.) by a set of facts so that plans can be recovered from the stable models of the program consisting of the description of the problem and of the set of facts describing the input. Similarly, the problem to find a hamilton cycle in a graph can be solved by encoding the problem as a logic program and encoding an input graph as a collection of facts in such a way that stable models determine hamilton cycles. Several problems and their encodings are described in detail in Benchmarks and Comparisons section of the page.

The term Answer Set Programming, that we use now, was coined by Vladimir Lifschitz. It nicely captures two key ideas behind the approach: solutions or answers are sets (sets of elementary actions in the case of planning, sets of edges in the case of the hamilton-cycle problem) and logic programming with the answer-set semantics (a generalization of stable model semantics) is an instantiation of the general approach. The term was used for the first time in the volume gathering papers of the Logic Programming Retreat at Shakertown, KY, The Logic Programming Paradigm: A 25-Year Perspective, editors: K.R. Apt, V.W. Marek, M. Truszczynski, D.S. Warren, Springer-Verlag, 1999. Our paper on stable logic programming was also published there.


ACKNOWLEDGEMENT

Activities discussed on this site are partially supported by the National Science Foundation. Any opinions, findings, and conclusions or recommendations expressed here  are those of the author(s) and do not necessarily reflect the views of the National Science Foundation