Time and Place: TTh 3:30-5pm, RLM 7.120
Instructor: Vladimir Lifschitz (vl@cs.utexas.edu)
Office Hours: TTh 2-3pm and by appointment, TAY 3.150B
Grading: There will be no tests; your grades will be determined by class participation.
Planning is a subarea of AI. In a planning problem, we want to find a plan--a sequence of actions that leads to a given goal. For instance, think of a monkey faced with the problem of getting a bunch of bananas hanging from the ceiling just beyond his reach. There is a box in the room, so that the monkey can solve the problem by pushing the box to an empty space under the bananas, climbing on top of the box, and then reaching the bananas. This is a plan.
We are interested in algorithms for solving problems like this. Some of the computational ideas in the area of planning proposed in recent years are both more efficient and easier to understand than those available earlier. We will study these new ideas and experiment with their implementations.
The first part of the course is about the use of action description languages for formalizing planning problems, about the relation of planning to logic programming, and about three implemented systems that can be used for planning: DLV, SMODELS and CCALC. In the second part of the course, we'll perform several experiments related to the use of these systems and review and discuss some recent publications on planning.
1. Richard Fikes and Nils Nilsson, STRIPS: A new approach to the application of theorem proving to problem solving. Artificial Intelligence, Vol. 2, 1971. Reproduced in: Readings in Planning, Morgan Kaufmann, 1990.
2. Vladimir Lifschitz, On the semantics of STRIPS. In: Reasoning about Actions and Plans, Morgan Kaufmann, 1987. Reproduced in: Readings in Planning, Morgan Kaufmann, 1990.
3. Edwin Pednault, Formulating multiagent, dynamic-world problems in the classical planning framework. In: Reasoning about Actions and Plans, Morgan Kaufmann, 1987. Reproduced in: Readings in Planning, Morgan Kaufmann, 1990.
4. Michael Gelfond and Vladimir Lifschitz, Action languages. Unpublished draft, 1999.
5. Enrico Giunchiglia and Vladimir Lifschitz, An action language based on causal explanation: preliminary report. In: Proc. AAAI-98, 1998.
6. Norman McCain and Hudson Turner, Causal theories of action and change. In: Proc. AAAI-97, 1997.
7. Vladimir Lifschitz, On the logic of causal explanation. Artificial Intelligence, Vol. 96, 1997.
8. Vladimir Lifschitz, Foundations of logic programming. In: Principles of Knowledge Representation, CSLI Publications, 1996.
9. Victor Marek and Miroslaw Truszczynski, Stable models and an alternative logic programming paradigm. To appear in: The Logic Programming Paradigm: a 25-Year Perspective, Springer Verlag, 1999.
10. Vladimir Lifschitz, Action languages, answer sets and planning. To appear in: The Logic Programming Paradigm: a 25-Year Perspective, Springer Verlag, 1999.
11. Esra Erdem, Describing exogenous atoms by disjunctive rules. Unpublished draft, 1999.
12. Ilkka Niemelä and Patrik Simons, Efficient implementation of the well-founded and stable model semantics. In: Proc. JICSLP-96, 1996.
13. Enrico Giunchiglia, Alessandro Massarotto and Roberto Sebastiani, Act, and the rest will follow: exploiting determinism in planning as satisfiability. In: Proc. AAAI-98, 1998.