Answer Set Programming

Answer set programming (ASP) is a programming methodology oriented towards combinatorial search problems. In such a problem, the goal is to find a solution among a large but finite number of possibilities. The idea of ASP came from research on artificial intelligence and computational logic. ASP is a form of declarative programming: an ASP program describes what is counted as a solution to the problem, but does not specify an algorithm for solving it. Search is performed by sophisticated software systems called answer set solvers. Combinatorial search problems often arise in science and technology, and ASP has found applications in diverse areas—in historical linguistic, in bioinformatics, in robotics, in space exploration, in oil and gas industry, and many others. The importance of this programming method was recognized by the Association for the Advancement of Artificial Intelligence in 2016, when AI Magazine published a special issue on answer set programming. The book introduces the reader to the theory and practice of ASP. It describes the input language of the answer set solver CLINGO, which was designed at the University of Potsdam in Germany and is used today by ASP programmers in many countries. It includes numerous examples of ASP programs and present the mathematical theory that ASP is based on. There are many exercises with complete solutions. Preface......Page 3 Contents......Page 5 Declarative Programming......Page 8 Logic Programming......Page 9 Remarks......Page 11 2 Input Language of CLINGO......Page 13 Rules......Page 14 Directives & Comments......Page 16 Arithmetic......Page 19 Definitions......Page 21 Choice Rules......Page 25 Variables in Choice Rule......Page 28 Constraints......Page 29 Anonymous Variables......Page 32 Remarks......Page 33 Seating Arrangements......Page 35 Schur Numbers......Page 38 Digression on Grounding & Solving......Page 41 Search in Graphs......Page 43 Search in 2 Dimensions......Page 48 Partner Units Problem......Page 50 Additional Programming Exercises......Page 51 Remarks......Page 54 4 Propositional Programs & Minimal Models......Page 57 Propositional Formulas......Page 58 Equivalence......Page 60 Minimal Models......Page 62 Stable Models of Positive Propositional Programs......Page 64 Propositional Image of clingo Program......Page 66 Values of Ground Term......Page 69 More on Propositional Images......Page 71 Remarks......Page 74 Examples......Page 77 Stable Models of Propositional Program......Page 79 Stable Models as Fixpoints......Page 82 Simplifying Propositional Programs......Page 84 clingo Programs with Negation......Page 87 Law of Excluded Middle......Page 89 clingo Programs with Choice......Page 92 Theorem on Constraints......Page 94 Remarks......Page 95 Strong Equivalence......Page 98 Theorem on Strong Equivalence......Page 103 Program Completion......Page 104 Theorem on Completion......Page 108 Remarks......Page 111 Counting......Page 113 Summation......Page 116 Maximum & Minimum......Page 120 Optimization......Page 121 Symbolic Functions......Page 126 Classical Negation......Page 128 Remarks......Page 130 Example - Blocks World......Page 132 Transition Diagrams......Page 134 Time......Page 135 Effects of Actions......Page 137 Nonexecutable Actions......Page 140 Prediction......Page 141 Planning......Page 143 Concurrency......Page 147 Remarks......Page 148 9 Conclusion......Page 150 Answers......Page 151 Listings......Page 181 Biblio......Page 183 Index......Page 189 Answer set programming (ASP) is a programming methodology oriented towards combinatorial search problems. In such a problem, the goal is to find a solution among a large but finite number of possibilities. The idea of ASP came from research on artificial intelligence and computational logic. ASP is a form of declarative programming: an ASP program describes what is counted as a solution to the problem, but does not specify an algorithm for solving it. Search is performed by sophisticated software systems called answer set solvers. Combinatorial search problems often arise in science and technology, and ASP has found applications in diverse areas--in historical linguistic, in bioinformatics, in robotics, in space exploration, in oil and gas industry, and many others. The importance of this programming method was recognized by the Association for the Advancement of Artificial Intelligence in 2016, when AI Magazine published a special issue on answer set programming. The book will introduce the reader to the theory and practice of ASP. It will describe the input language of the answer set solver CLINGO, which was designed at the University of Potsdam in Germany and is used today by ASP programmers in many countries. It will include numerous examples of ASP programs and present the mathematical theory that ASP is based on. There will be many exercises with complete solutions.