Research on satisfiability planning

Research on satisfiability planning

Here I report some of my research on satisfiability planning, a powerful approach to domain-independent planning first proposed by Henry Kautz and Bart Selman.

Problem encodings

In the paper Parallel encodings of classical planning as satisfiability, co-authored with Keijo Heljanko and Ilkka Niemelä, we present a number of new encodings for planning as satisfiability. Almost all of earlier research on planning as satisfiability has adopted parallel plans based on the notion of interference: two actions are allowed to take place in parallel when they do not interfere.

In the new encodings two new notions of parallel plans are used. The first definition of plans, which we call process semantics, requires plans to be in a more restrictive normal form. This reduces the number of potential plans to be considered, and in some cases increases the efficiency of finding plans. The second definition of plans, which we call E-step semantics, allows more parallelism than the standard definition of interference, and is often several orders of magnitude faster than all other existing SAT-encodings.

Evaluation strategies

In the paper Evaluation strategies for planning as satisfiability we show how a planner that solves several SAT instances simultaneously can find plans much more efficiently than traditional SAT planners, at the cost of not necessarily finding a plan with the optimal parallel length.

Phase transitions

Symmetry

Software

NEW! I have a new efficient implementation of Planning as SAT. Start the program without arguments to get help. Currently does not handle non-STRIPS problems well because the translation into CNF is naive, and gets in trouble with many problems containing conditional effects.

Publications

Jussi Rintanen. Planning graphs and propositional clause-learning. In Gerhard Brewka and Patrick Doherty, editors, Principles of Knowledge Representation and Reasoning: Proceedings of the Eleventh International Conference (KR 2008), pages 535-543, AAAI Press, 2008.

M. Wehrle and J. Rintanen, Planning as satisfiability with relaxed E-step plans, In M. Orgun and J. Thornton, eds, AI 2007 : Advances in Artificial Intelligence: 20th Australian Joint Conference on Artificial Intelligence, Surfers Paradise, Gold Coast, Australia, December 2-6, 2007, Proceedings, Lecture Notes in Computer Science 4830, pages 244-253, Springer-Verlag, 2007. The winner of the AI 2007 Best Paper Award

J. Rintanen, K. Heljanko and I. Niemelä, Planning as satisfiability: parallel plans and algorithms for plan search, Artificial Intelligence, 170(12-13), pages 1031-1080, 2006.

J. Rintanen, Evaluation strategies for planning as satisfiability, in R. Lopez de Mantaras and Lorenza Saitta, eds., ECAI 2004. Proceedings of the 16th European Conference on Artificial Intelligence, pages 682-687, IOS Press, 2004. [additional material on slides of ECAI'04 talk, 4 on 1]

J. Rintanen, Phase transitions in classical planning: an experimental study, in Principles of Knowledge Representation and Reasoning: Proceedings of the Ninth International Conference (KR 2004), pages 710-719, AAAI Press, 2004. [additional material on slides of KR'04 talk, 4 on 1]

J. Rintanen, Symmetry reduction for SAT representations of transition systems, in Proceedings of the 13th International Conference on Automated Planning and Scheduling, pages 32-40, AAAI Press, 2003. (© 2003 American Association for Artificial Intelligence. All rights reserved. AAAI)

J. Rintanen and H. Jungholt. Numeric state variables in constraint-based planning, in Recent Advances in AI Planning: 5th European Conference on Planning, ECP'99, Durham, UK, September 8-10, 1999, S. Biundo and M. Fox, eds., Lecture Notes in Artificial Intelligence 1809, pages 109-121, 2000. Springer-Verlag, Berlin, Germany.

J. Rintanen. A planning algorithm not based on directional search. in Principles of Knowledge Representation and Reasoning: Proceedings of the Sixth International Conference (KR '98), A. G. Cohn, L. K. Schubert, and S. C. Shapiro, eds., pages 617-624, Trento, Italy, June 1998. Morgan Kaufmann Publishers, San Francisco, California.

Overviews:

J. Rintanen. State-space traversal techniques for planning, Albert-Ludwigs-Universität-Freiburg, Institut für Informatik, Technical Report 220, 76 pages, 2005. (AAAI-06 Tutorial, IJCAI-05 Tutorial)

J. Rintanen. Introduction to automated planning, course notes, Albert-Ludwigs-Universität Freiburg, 2003-2005.

Bibliography

[DIMACS] Satisfiability suggested format, DIMACS, May 1993.

Henry Kautz and Bart Selman, Planning as Satisfiability, Proceedings of the Tenth European Conference on Artificial Intelligence (ECAI'92), John Wiley, 1992.

Henry Kautz and Bart Selman, Pushing the Envelope: Planning, Propositional Logic, and Stochastic Search, Proceedings of the Thirteenth National Conference on Artificial Intelligence and the Eighth Innovative Applications of Artificial Intelligence Conference, AAAI Press, 1996.

Last modified: Wed Aug 8 17:32:08 2007