Answer Set Programming (ASP) evolved in the late 1990s as a declarative modelling and computational problem-solving methodology. It uses logic programming to construct a generative space abstractly and repeatedly establish limits to produce the desired output.
ASP is a type of declarative programming that is used to solve hard search problems, especially those that are NP-hard. It is based on the semantics of logic programming’s stable model (answer set). It can handle event calculus formulas that can’t be computed using predicate completion, like effect constraints, disjunctive event axioms, and definitions of compound events.
In ASP, search problems are broken down into figuring out stable models, and answer set solvers, programmes that make stable models, are used to search. In a broader sense, ASP encompasses all answer set applications to knowledge representation and the use of Prolog-style query evaluation to address issues that arise in these applications.
The 1997 planning method developed by Dimopoulos, Nebel, and Kohler was an early instance of ASP. Their strategy is founded on the connection between plans and stable models. Soininen and Niemela developed what is now known as a response set programming to the product configuration problem in 1998. The term “answer set programming” emerged in 1999 in a compilation of two works titled The Logic Programming Paradigm. The first of these studies identified answer set solvers as a new programming paradigm for search. In the same year, Niemela presented a new paradigm, “logic programmes with stable model semantics.”
Furthermore, the ASP standardisation working group made a standard language specification called ASP-Core-2. Newer ASP systems are getting closer to this standard. For example, the Answer Set Programming Competition uses ASP-Core-2 as its reference language. Periodically, ASP solvers are tested on several reference problems.
Early systems, like Smodels, found solutions by going backwards. As the theory and practise of Boolean SAT solvers grew, the researchers built ASP solvers like ASSAT and Cmodels on top of SAT solvers. These turned ASP formulas into SAT propositions, ran the SAT solver on them, and then turned the answers back into ASP form. Some newer systems, like Clasp, use a hybrid method. These systems use conflict-driven algorithms inspired by SAT but don’t entirely change into a Boolean-logic form. The performance of these methods is much better than that of earlier backtracking algorithms, often by order of magnitude.
Many of the systems listed below fall under the Potassco project, including:
- grounding systems (gringo),
- incremental systems (iclingo),
- constraint solvers (clingcon),
- action language to ASP compilers (coala),
- distributed MPI implementations (claspar), and many others.
Most systems provide some level of support for variables, but usually only via grounding (by using Lparse or gringo, for example). Because the need for grounding can lead to many clauses, systems that can do grounding on the fly might be better. For example, ASP implementations driven by queries, like the Galliwasp system and s(CASP), avoid dropping by using both resolution and coinduction.
Furthermore, ASP is a method for representing and reasoning knowledge. Answer set programmes represent knowledge, whereas answer-set solvers execute reasoning. ASP enables the necessary default thinking for commonsense reasoning. Extensive research in knowledge representation, deductive databases, and logic programming led to the paradigm.