Heuristics and planning
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 for the first time how to efficiently generalize some of the best known heuristics for classical STRIPS planning to a much more 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 very 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 very few heuristics for partially-observable planning problems that is not a direct generalization of a heuristic for classical planning.
Jussi 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 h^n heuristic to full (ground) PDDL.
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.
Planning as SAT, constraint-based planning
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 a number of breakthroughs in SAT planning: very practical optimal encodings + new types of plan search algorithms. The encoding and the plan search algorithms are currently (2008) by far the fastest existing ones for SAT-based planning.
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 E-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 planning applicable to larger 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.
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.
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.
Jussi 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.
Diagnosis as SAT, constraint-based diagnosis
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)
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.
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.
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)