by Martin Gebser and Torsten Schaub
University of Potsdam
Germany
Short Description
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.
Description
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.
Topics of the Tutorial
- Motivation and Introduction
- Formal Foundations
- Solving
- Grounding
- Systems
- Modeling
Material
- Lecture slides
- Lecture examples (also available as inline attachment to lecture slides)
- Collection on ASP
- Potassco user’s manual and overview
- This file as PDF or HTML
Resumes
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.
Contact
Drop us an email at {gebser, torsten}@cs.uni-potsdam.de for any questions.
Bibliography
- 1
- C. Baral.
Knowledge Representation, Reasoning and Declarative Problem Solving.
Cambridge University Press, 2003. - 2
- M. Gebser, R. Kaminski, B. Kaufmann, M. Ostrowski, T. Schaub, and M. Schneider.
Potassco: The Potsdam answer set solving collection.
AI Communications, 24(2):105-124, 2011. - 3
- M. Gebser, B. Kaufmann, A. Neumann, and T. Schaub.
Conflict-driven answer set solving.
In M. Veloso, editor, Proceedings of the Twentieth International Joint Conference on Artificial Intelligence (IJCAI’07), pages 386-392. AAAI Press/The MIT Press, 2007.