Answer Set Solving in Practice Martin Gebser and Torsten Schaub University of Potsdam {gebser,torsten}@cs.unipotsdam.de
http://www.cs.unipotsdam.de/~torsten/ijcai11tutorial/asp.pdf
Martin and Torsten (
[email protected])
Answer Set Solving in Practice
July 28, 2011
1 / 384
Motivation Overview
1 Objective 2 Answer Set Programming 3 Historic Roots 4 Problem Solving 5 Applications
Martin and Torsten (
[email protected])
Answer Set Solving in Practice
July 28, 2011
2 / 384
Objective
Goal: Declarative problem solving “What is the problem?” instead of “How to solve the problem?”
Problem
Solution 6
Modeling
Interpretation ?
Representation

Output
Computation Martin and Torsten (
[email protected])
Answer Set Solving in Practice
July 28, 2011
3 / 384
Objective
Goal: Declarative problem solving “What is the problem?” instead of “How to solve the problem?”
Problem
Solution 6
Modeling
Interpretation ?
Representation

Output
Computation Martin and Torsten (
[email protected])
Answer Set Solving in Practice
July 28, 2011
3 / 384
Objective
Goal: Declarative problem solving “What is the problem?” instead of “How to solve the problem?”
Problem
Solution 6
Modeling
Interpretation ?
Representation

Output
Computation Martin and Torsten (
[email protected])
Answer Set Solving in Practice
July 28, 2011
3 / 384
Answer Set Programming
Answer Set Programming (ASP) in a Nutshell ASP is an approach to declarative problem solving, combining a rich yet simple modeling language with highperformance solving capacities
ASP has its roots in (logicbased) knowledge representation and (nonmonotonic) reasoning (deductive) databases constraint solving (in particular, SATisfiability testing) logic programming (with negation)
ASP allows for solving all search problems in NP (and NP NP ) in a uniform way (being more compact than SAT) The versatility of ASP is reflected by the ASP solver clasp, winning first places at ASP’07/09/11, PB’09/11, and SAT’09/11 ASP embraces many emerging application areas! Martin and Torsten (
[email protected])
Answer Set Solving in Practice
July 28, 2011
4 / 384
Answer Set Programming
Answer Set Programming (ASP) in a Nutshell ASP is an approach to declarative problem solving, combining a rich yet simple modeling language with highperformance solving capacities
ASP has its roots in (logicbased) knowledge representation and (nonmonotonic) reasoning (deductive) databases constraint solving (in particular, SATisfiability testing) logic programming (with negation)
ASP allows for solving all search problems in NP (and NP NP ) in a uniform way (being more compact than SAT) The versatility of ASP is reflected by the ASP solver clasp, winning first places at ASP’07/09/11, PB’09/11, and SAT’09/11 ASP embraces many emerging application areas! Martin and Torsten (
[email protected])
Answer Set Solving in Practice
July 28, 2011
4 / 384
Answer Set Programming
Answer Set Programming (ASP) in a Nutshell ASP is an approach to declarative problem solving, combining a rich yet simple modeling language with highperformance solving capacities
ASP has its roots in (logicbased) knowledge representation and (nonmonotonic) reasoning (deductive) databases constraint solving (in particular, SATisfiability testing) logic programming (with negation)
ASP allows for