Answer Set Solving in Practice

Jul 28, 2011 - r/1 is not a domain predicate because it is defined in terms of not ...... We get min⊆(ground(Π)X ) = { {a(1,2), b(1)}, {a(1,2), c(2)} }. X is an answer set ...... pro(asparagus,cheap). pro(cucumber,cheap). pre(cheap). pro(asparagus ...
4MB Sizes 2 Downloads 407 Views
Answer Set Solving in Practice Martin Gebser and Torsten Schaub University of Potsdam {gebser,torsten}@cs.uni-potsdam.de

http://www.cs.uni-potsdam.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 high-performance solving capacities

ASP has its roots in (logic-based) 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 high-performance solving capacities

ASP has its roots in (logic-based) 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 high-performance solving capacities

ASP has its roots in (logic-based) knowledge representation and (nonmonotonic) reasoning (deductive) databases constraint solving (in particular, SATisfiability testing) logic programming (with negation)

ASP allows for