A Tutorial at IJCAI'11
Martin Gebser and Torsten Schaub
University of Potsdam, Germany
The tutorial presents a practical introduction to Answer Set Programming (ASP), aiming at using ASP languages and systems for solving application problems. Starting from the essential formal foundations, it introduces ASP's solving technology, modeling language and methodology, while practically illustrating the overall solving process via existing applications.
Answer Set Programming (ASP) is a declarative problem solving approach, combining a rich yet simple modeling language with high-performance solving capacities. ASP is particularly suited for modeling problems in the area of Knowledge Representation and Reasoning involving incomplete, inconsistent, and changing information. From a formal perspective, ASP allows for solving all search problems in NP (and NPupNP) in a uniform way (being more compact than SAT). Applications of ASP include automatic synthesis of multiprocessor systems, decision support systems for NASA shuttle controllers, reasoning tools in systems biology, and many more. The versatility of ASP is also reflected by the ASP solver clasp, developed at the University of Potsdam, and winning first places at international ASP, PB, and SAT competitions.
The tutorial aims at acquainting the participant with ASP's modeling and solving methodology, enabling her/him to independent problem solving using ASP systems. To this end, the tutorial starts with an introduction to the essential formal concepts of ASP, needed for understanding its semantics and solving technology. In fact, ASP solving rests on two major components: A grounder turning specifications in ASP's modeling language into propositional logic programs and a solver computing a requested number of answer sets of the given program. Building on the aforementioned formal concepts, we provide a characterization of ASP's inference schemes that are in turn mapped into algorithms relying on advanced Boolean Constraint technology. Similarly, ASP's grounding inferences are discussed in conjunction with (deductive) database techniques. The remainder of the tutorial is dedicated to applying ASP, involving an introduction to ASP's modeling language, its solving methodology, and advanced techniques fostering scalability. The latter is illustrated via some real-world applications, taken from bio-informatics. All involved ASP systems are freely available from http://potassco.sourceforge.net.
ASP provides a declarative tool for modeling various problems typical to Knowledge Representation and Reasoning in particular and AI in general. The unique pairing of declarativeness and performance allows for concentrating on an actual problem, rather than a smart way of implementing it. The ASP approach is not only highly suitable for the practitioner solving an AI problem at hand but also for disseminating many basic AI techniques through teaching their (executable) formalization in ASP.
Martin Gebser and Torsten Schaub are working on ASP in the Knowledge Representation and Reasoning group at the University of Potsdam. The group's activity in ASP has led to the open source project Potassco [2], the Potsdam Answer Set Solving Collection, bundling tools for ASP developed at Potsdam, and hosted at potassco.sourceforge.net. Potassco comprises more than a dozen ASP-related systems, among them the award winning solver clasp.
This document was generated using the LaTeX2HTML translator Version 2008 (1.71)
Copyright © 1993, 1994, 1995, 1996,
Nikos Drakos,
Computer Based Learning Unit, University of Leeds.
Copyright © 1997, 1998, 1999,
Ross Moore,
Mathematics Department, Macquarie University, Sydney.
The command line arguments were:
latex2html -split 0 summary
The translation was initiated by Torsten Schaub on 2011-07-22
Torsten Schaub 2011-07-22