Skip to content
Last Dictionary
Plane
Symbolic & Classical AI

answer set programming

nounAlso: ASP, stable model semantics, answer set, stable model, clingo

In plain wordsA way to solve hard puzzles and scheduling problems by describing in logical rules what a valid solution looks like; a solver then finds the arrangements that fit those rules.

  1. A form of logic programminglogic programming, n.: A style of programming in which you write down facts and rules in logic and then ask questions; the computer works out the answers itself by logical deduction. for combinatorial search in which the programmer describes what counts as a solution and a solver computes the program's stable models, also called answer sets, each of which encodes one solution. A program consists of rules with default negation ('not'), and often disjunction, integrity constraints that rule out unwanted solutions, choice rules and aggregates; each stable model is a self-supporting set of beliefs justified by the rules. Unlike PrologProlog, prop. n.: A programming language from 1972 in which you state facts and rules in logic and then ask questions; the computer finds answers by searching for proofs., ASP is not executed by proof search: a grounder replaces variables with constants, and a solver closely related to conflict-driven SATBoolean satisfiability problem, n.: The puzzle of deciding whether a set of true-or-false conditions can all be met at once. It is famously hard in theory, yet modern solvers routinely handle millions of conditions. solvers computes the answer sets, as in the Potsdam system clingo. Its non-monotonic reasoningnon-monotonic reasoning, n.: Reasoning in which new information can overturn earlier conclusions — you assume a bird can fly until you learn it is a penguin — as people do constantly but classical logic does not allow. handles defaults and exceptions naturally, and it is used for scheduling, product configuration, planning, robotics and bioinformatics.

Origin

Michael Gelfond and Vladimir Lifschitz defined the stable model semantics in 1988. Using stable models as a general problem-solving paradigm was proposed in 1999 by Victor Marek and Mirosław Truszczyński and by Ilkka Niemelä. The name 'answer set programming' came into use around the same time, and Lifschitz's papers did much to spread it.

Related

See also
  • logic programminglogic programming, n.: A style of programming in which you write down facts and rules in logic and then ask questions; the computer works out the answers itself by logical deduction.
  • non-monotonic reasoningnon-monotonic reasoning, n.: Reasoning in which new information can overturn earlier conclusions — you assume a bird can fly until you learn it is a penguin — as people do constantly but classical logic does not allow.
  • Boolean satisfiability problemBoolean satisfiability problem, n.: The puzzle of deciding whether a set of true-or-false conditions can all be met at once. It is famously hard in theory, yet modern solvers routinely handle millions of conditions.
  • constraint satisfaction problemconstraint satisfaction problem, n.: A problem in which each item must be given a value so that every rule is obeyed, like filling in a Sudoku, coloring a map so no neighbors match, or building a timetable without clashes.
  • closed-world assumptionclosed-world assumption, n.: The rule of treating whatever a system cannot confirm as false: if a library's catalog does not list a book, the library is assumed not to have it.
  • PrologProlog, prop. n.: A programming language from 1972 in which you state facts and rules in logic and then ask questions; the computer finds answers by searching for proofs.

Sources

  1. Gelfond, M. & Lifschitz, V. (1988). The Stable Model Semantics for Logic Programming. Proceedings of the 5th International Conference and Symposium on Logic Programming.
  2. Lifschitz, V. (2019). Answer Set Programming. Springer.

Mentioned in

Boolean satisfiability problemBoolean satisfiability problem, n.: The puzzle of deciding whether a set of true-or-false conditions can all be met at once. It is famously hard in theory, yet modern solvers routinely handle millions of conditions., constraint satisfaction problemconstraint satisfaction problem, n.: A problem in which each item must be given a value so that every rule is obeyed, like filling in a Sudoku, coloring a map so no neighbors match, or building a timetable without clashes., logic programminglogic programming, n.: A style of programming in which you write down facts and rules in logic and then ask questions; the computer works out the answers itself by logical deduction., closed-world assumptionclosed-world assumption, n.: The rule of treating whatever a system cannot confirm as false: if a library's catalog does not list a book, the library is assumed not to have it., inductive logic programminginductive logic programming, n.: A kind of machine learning that discovers general logical rules — such as 'X is a grandparent of Z if X is a parent of a parent of Z' — from examples and background knowledge., non-monotonic reasoningnon-monotonic reasoning, n.: Reasoning in which new information can overturn earlier conclusions — you assume a bird can fly until you learn it is a penguin — as people do constantly but classical logic does not allow.