RECENT PUBLICATIONS OF JUSSI RINTANEN

Heuristics (lower bounds) for planning

J. Rintanen. Planning as satisfiability: heuristics, Artificial Intelligence Journal, 2012.

J. Rintanen. Planning with SAT, Admissible Heuristics and A*. In Proceedings of the International Joint Conference on Artificial Intelligence, AAAI Press, 2011. A proof that standard SAT algorithms are strictly stronger for heuristic search planning than the iterative deepening A* algorithm, and that A* and IDA* are sometimes exponentially worse than SAT. The paper also provides a framework to use lower-bounds (admissible heuristics) in SAT-based planning.

J. Rintanen. Heuristics for Planning with SAT and Expressive Action Definitions. In Proceedings of the International Conference on Automated Planning and Scheduling, AAAI Press, 2011. Generalization of the SAT heuristics from the 2010 papers to conditional effects and disjunctive preconditions.

J. Rintanen. Heuristic Planning with SAT: Beyond Strict Depth-First Search. Twenty-Third Australasian Joint Conference on Artificial Intelligence, Adelaide, December 7-10, 2010, Proceedings. Lecture Notes in Computer Science, Springer-Verlag, 2010. This paper shows how very simple heuristics on top of the CP'10 paper below increases the efficiency SAT-based planning substantially further.

J. Rintanen. Heuristics for Planning with SAT. In David Cohen, ed., Principles and Practice of Constraint Programming - CP 2010, 16th International Conference, CP 2010, St. Andrews, Scotland, September 2010, Proceedings. Lecture Notes in Computer Science 6308, pages 414-428, Springer-Verlag, 2010. The paper shows how the standard SAT solving algorithm CDCL combined with a very simple planning-specific variable selection scheme yields a planner that is very competitive with the best existing planners. The variable selection scheme makes CDCL do backward chaining starting from the goals.

J. Rintanen, Unified definition of heuristics for classical planning, ECAI 2006. Proceedings of the 17th European Conference on Artificial Intelligence, pages 600-604, IOS Press, 2006. The paper shows how to generalize some of the heuristics (for STRIPS planning) to the an expressive language with conditional effects and arbitrary preconditions (ADL/PDDL).

S. Hickmott, J. Rintanen, S. Thiebaux and L. White, Planning via Petri net unfolding, in M. Veloso, ed., Proceedings of the 20th International Joint Conference on Artificial Intelligence, pages 1904-1911, AAAI Press, 2007.

J. Rintanen, Phase transitions in classical planning: an experimental study, in Proceedings of the 14th International Conference on Automated Planning and Scheduling, pages 101-110, AAAI Press, 2004. [additional material on slides, 8 on 1] Improved methods for generating challenging planning problems + an empirical study of the relative strengths of different approaches to classical planning.

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.

J. Rintanen, Distance estimates for planning in the discrete belief space, in Proceedings of the 19th National Conference on Artificial Intelligence, pages 525-530, AAAI Press, 2004. (© 2004 American Association for Artificial Intelligence. All rights reserved. AAAI) One of the few heuristics for partially-observable planning that is not a direct generalization of a heuristic for classical planning.

J. Rintanen. Regression for classical and nondeterministic planning. In Malik Ghallab, Constantine D. Spyropoulos, and Nikos Fakotakis, editors, ECAI 2008. Proceedings of the 18th European Conference on Artificial Intelligence. pages 568-571, IOS Press, 2008. In addition to other results, the paper gives a generalization of the admissive hn heuristic to full (ground) PDDL as well as a very simple yet efficient and powerful algorithm for computing invariants for ground PDDL/ADL .

Overviews:

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

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

Planning as SAT, constraint-based planning

See also my Planning with SAT page.

J. Rintanen. Planning as Satisfiability: Heuristics, Artificial Intelligence Journal, conditionally accepted for publication, 2012. A detailed article on planning-specific heuristics for SAT solvers and their efficient implementation.

J. Rintanen. Engineering Efficient Planners with SAT, In ECAI 2012. Proceedings of the 20th European Conference on Artificial Intelligence, IOS Press, 2012. Implementation technology for very efficient SAT based planning, with compact representation of very large clause sets.

J. Rintanen. Planning with SAT, Admissible Heuristics and A*. In Proceedings of the International Joint Conference on Artificial Intelligence, AAAI Press, 2011. A proof that standard SAT algorithms are strictly stronger for heuristic search planning than the iterative deepening A* algorithm, and that A* and IDA* are sometimes exponentially worse than SAT.

J. Rintanen. Heuristics for Planning with SAT and Expressive Action Definitions. In Proceedings of the International Conference on Automated Planning and Scheduling, AAAI Press, 2011. Generalization of the SAT heuristics from the 2010 papers to conditional effects and disjunctive preconditions.

J. Rintanen. Heuristic Planning with SAT: Beyond Strict Depth-First Search. Twenty-Third Australasian Joint Conference on Artificial Intelligence, Adelaide, December 7-10, 2010, Proceedings. Lecture Notes in Computer Science, Springer-Verlag, 2010. This paper shows how very simple heuristics on top of the CP'10 paper below increases the efficiency SAT-based planning substantially further.

J. Rintanen. Heuristics for Planning with SAT. In David Cohen, ed., Principles and Practice of Constraint Programming - CP 2010, 16th International Conference, CP 2010, St. Andrews, Scotland, September 2010, Proceedings. Lecture Notes in Computer Science 6308, pages 414-428, Springer-Verlag, 2010. The paper shows how the standard SAT solving algorithm CDCL combined with a very simple planning-specific variable selection scheme yields a planner that is very competitive with the best existing planners. The variable selection scheme makes CDCL do backward chaining starting from the goals.

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. 2nd most downloaded Artificial Intelligence article at ScienceDirect October-December 2006 (excluding review and survey articles) The article presents practical optimal encodings for planning with SAT + new types of plan search algorithms.

J. 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). AAAI Press, 2008.

M. Wehrle and J. Rintanen, Planning as satisfiability with relaxed ∃-step plans, In Mehmet Orgun and John Thornton, editors, 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. Winner of the best paper award of AI'07

R. Mattmüller and J. Rintanen, Planning for temporally extended goals as propositional satisfiability, in M. Veloso, ed., Proceedings of the 20th International Joint Conference on Artificial Intelligence, pages 1966-1971, AAAI Press, 2007.

J. Rintanen, Compact representation of sets of binary constraints, ECAI 2006. Proceedings of the 17th European Conference on Artificial Intelligence, pages 143-147, IOS Press, 2006. [ECAI'06 talk] Biclique-based representations of binary constraints for making SAT representations scalable to very large planning problems.

M. Büttner and J. Rintanen, Improving parallel planning with constraints on the number of operators, in Proceedings of the 15th International Conference on Automated Planning and Scheduling, pages 292-299, AAAI Press, 2005.

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, 8 on 1]

J. Rintanen, K. Heljanko and I. Niemelä. Parallel encodings of classical planning as satisfiability, José Júlio Alferes and João Leite, eds., Logics in Artificial Intelligence: 9th European Conference, JELIA 2004, Lisbon, Portugal, September 27-30, 2004. Proceedings, Lecture Notes in Computer Science 3229, pages 307-319, Springer-Verlag, 2004.

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. Generalization of parallel plans to a setting in which a numeric state variable may be changed simultaneously by several operators + a constraint-based planning method that extends [Rintanen, 1998].

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. The work expresses the classical planning problem directly as a specialized constraint satisfaction problem without the intermediate step of translating it to a general-purpose formalism like required e.g. in the Planning as Satisfiability approach. The paper also gives a simple yet powerful algorithm for computing invariants.

J. Rintanen, Partial implicit unfolding in the Davis-Putnam procedure for quantified Boolean formulae, in International Conference on Logic for Programming, Artificial Intelligence and Reasoning (LPAR01), R. Nieuwenhuis and A. Voronkov, eds., Lecture Notes in Computer Science 2250, pages 362-376, Springer-Verlag, 2001. (© Springer-Verlag) The paper represents the classical planning problem as a Quantified Boolean Formula (QBF), motivated by the use of SAT for classical planning and the fact that QBF can represent exponentially long plans compactly, unlike SAT-based encodings. Algorithms for QBF are developed to address issues arising from the QBF representation.

Overviews:

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

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

Pruning techniques for planning (invariants)

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. Among other results, the paper gives a simple yet powerful algorithm for computing invariants.

J. Rintanen. An iterative algorithm for synthesizing invariants, in Proceedings of the 17th National Conference on Artificial Intelligence / 12th Innovative Applications of AI Conference, pages 806-811, AAAI Press, 2000. (© AAAI) The algorithm for generating invariants [Rintanen, 1998] generalized to work with schematic operator descriptions.

J. Rintanen. Regression for classical and nondeterministic planning. In Malik Ghallab, Constantine D. Spyropoulos, and Nikos Fakotakis, editors, ECAI 2008. Proceedings of the 18th European Conference on Artificial Intelligence. pages 568-571, IOS Press, 2008. In addition to other results, the paper gives a very elegant and powerful algorithm for computing arbitrary length invariant clauses for full (ground) PDDL.

Planning under incomplete information

J. Rintanen, Asymptotically optimal encodings of conformant planning in QBF, Proceedings of the 22nd AAAI Conference on Artificial Intelligence (AAAI-07), pages 1045-1050, AAAI Press, 2007. (© 2007 American Association for Artificial Intelligence. All rights reserved. AAAI)

J. Rintanen, Conditional planning in the discrete belief space, in L. P. Kaelbling, ed., Proceedings of the 19th International Joint Conference on Artificial Intelligence, pages 1260-1265, Morgan Kaufmann Publishers, San Francisco, California, 2005.

J. Rintanen, Complexity of planning with partial observability, in Proceedings of the 14th International Conference on Automated Planning and Scheduling, pages 345-354, AAAI Press, 2004. (© 2004 American Association for Artificial Intelligence. All rights reserved. AAAI)

J. Rintanen, Expressive equivalence of formalisms for planning with sensing, in Proceedings of the 13th International Conference on Automated Planning and Scheduling, pages 185-194, AAAI Press, 2003. (© 2003 American Association for Artificial Intelligence. All rights reserved. AAAI)

J. Rintanen, Backward plan construction for planning with partial observability, in International Conference on Artificial Intelligence Planning and Scheduling (AIPS02), M. Ghallab, J. Hertzberg and P. Traverso, eds., pages 173-182, AAAI Press, 2002. (© AAAI)

J. Rintanen, Complexity of probabilistic planning under average rewards, in Proceedings of the 17th International Joint Conference on Artificial Intelligence, B. Nebel, ed., pages 503-508, August 2001. Morgan Kaufmann Publishers, San Francisco, California, 2001.

J. Rintanen. Constructing conditional plans by a theorem-prover, Journal of Artificial Intelligence Research, 10:323-352, 1999. The paper introduces the QBF based approach to planning under incomplete information (nondeterminism, partial observability). This work is the first ever to propose QBF as a solution method to a concrete computational problem and to demonstrate the feasibility of the approach.

Complexity of planning

J. Rintanen, Complexity of concurrent temporal planning, Proceedings of the 17th International Conference on Automated Planning and Scheduling, to appear, AAAI Press, 2007. (© 2007 American Association for Artificial Intelligence. All rights reserved. AAAI) The paper shows that wide classes of temporal planning problems are in PSPACE and easily reducible to classical planning. It also shows that the general problem is EXPSPACE-complete.

J. Rintanen, Asymptotically optimal encodings of conformant planning in QBF, Proceedings of the 22nd AAAI Conference on Artificial Intelligence (AAAI-07), pages 1045-1050, AAAI Press, 2007. (© 2007 American Association for Artificial Intelligence. All rights reserved. AAAI)

J. Rintanen, Complexity of planning with partial observability, in Proceedings of the 14th International Conference on Automated Planning and Scheduling, pages 345-354, AAAI Press, 2004. (© 2004 American Association for Artificial Intelligence. All rights reserved. AAAI)

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, 8 on 1]

J. Rintanen, Phase transitions in classical planning: an experimental study, in Proceedings of the 14th International Conference on Automated Planning and Scheduling, pages 101-110, AAAI Press, 2004.

J. Rintanen, Complexity of probabilistic planning under average rewards, in Proceedings of the 17th International Joint Conference on Artificial Intelligence, B. Nebel, ed., pages 503-508, August 2001. Morgan Kaufmann Publishers, San Francisco, California, 2001.

Diagnosis

J. Rintanen, Complexity of diagnosability for succinct transition systems, in M. Veloso, ed., Proceedings of the 20th International Joint Conference on Artificial Intelligence, pages 538-544, AAAI Press, 2007.

J. Rintanen and A. Grastien, Diagnosability testing with satisfiability algorithms, in M. Veloso, ed., Proceedings of the 20th International Joint Conference on Artificial Intelligence, pages 532-537, AAAI Press, 2007.

A. Grastien, Anbulagan, J. Rintanen and E. Kelareva, Diagnosis of discrete-event systems using satisfiability algorithms, pages 305-310, Proceedings of the 22nd AAAI Conference on Artificial Intelligence (AAAI-07), AAAI Press, 2007. (© 2007 American Association for Artificial Intelligence. All rights reserved. AAAI)

Other publications

See the complete list.