×

zbMATH — the first resource for mathematics

Deterministic planning in the fifth international planning competition: PDDL3 and experimental evaluation of the planners. (English) Zbl 1191.68634
Summary: The international planning competition (IPC) is an important driver for planning research. The general goals of the IPC include pushing the state of the art in planning technology by posing new scientific challenges, encouraging direct comparison of planning systems and techniques, developing and improving a common planning domain definition language, and designing new planning domains and problems for the research community. This paper focuses on the deterministic part of the fifth international planning competition (IPC5), presenting the language and benchmark domains that we developed for the competition, as well as a detailed experimental evaluation of the deterministic planners that entered IPC5, which helps to understand the state of the art in the field. We present an extension of pddl, called pddl3, allowing the user to express strong and soft constraints about the structure of the desired plans, as well as strong and soft problem goals.
We discuss the expressive power of the new language focusing on the restricted version that was used in IPC5, for which we give some basic results about its compilability into pddl2. Moreover, we study the relative performance of the IPC5 planners in terms of solved problems, CPU time, and plan quality; we analyse their behaviour with respect to the winners of the previous competition; and we evaluate them in terms of their capability of dealing with soft goals and constraints, and of finding good quality plans in general. Overall, the results indicate significant progress in the field, but they also reveal that some important issues remain open and require further research, such as dealing with strong constraints and computing high quality plans in metric-time domains and domains involving soft goals or constraints.

MSC:
68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
Software:
IPC-4; Graphplan; PDDL; Yochan
PDF BibTeX Cite
Full Text: DOI
References:
[1] Bacchus, F., The AIPS ’00 planning competition, AI magazine, 22, 3, 47-56, (2001)
[2] Bacchus, F.; Kabanza, F., Planning for temporally extended goals, Annals of mathematics and artificial intelligence, 22, 1-2, 5-27, (1998) · Zbl 1034.68549
[3] Bacchus, F.; Kabanza, F., Using temporal logics to express search control knowledge for planning, Artificial intelligence, 116, 123-191, (2000) · Zbl 0939.68827
[4] Bäckström, C., Expressive equivalence of planning formalisms, Artificial intelligence, 76, 17-34, (1995)
[5] J. Baier, S. McIlraith, Planning with first-order temporally extended goals using heuristic search, in: Proc. of 21st National Conf. on Artificial Intelligence (AAAI’06), 2006
[6] J. Baier, S. McIlraith, Planning with temporally extended goals using heuristic search, in: Proc. of 16th Int. Conf. on Automated Planning and Scheduling (ICAPS’06), 2006
[7] J. Benton, S. Kambhampati, YochanPS: PDDL3 simple preferences as partial satisfaction planning, in: 5th Int. Planning Competition Booklet, 2006
[8] J. Benton, M. van den Briel, S. Kambhampati, A hybrid linear programming and relaxed plan heuristic for partial satisfaction planning problems, in: Proc. of 17th Int. Conf. on Automated Planning and Scheduling (ICAPS’07), 2007 · Zbl 1145.68537
[9] Bistarelli, S.; Montanari, U.; Rossi, F., Semiring-based constraint solving and optimization, Journal of ACM, (1997) · Zbl 0890.68032
[10] Blum, A.; Furst, M.L., Fast planning through planning graph analysis, Artificial intelligence, 90, 281-300, (1997) · Zbl 1017.68533
[11] Bonet, B.; Geffner, H., Planning as heuristic search, Artificial intelligence, 129, 1-2, 5-33, (2001) · Zbl 0971.68146
[12] B. Bonet, H. Geffner, Heuristics for planning with penalties and rewards using compiled knowledge, in: Proc. of 10th Int. Conf. on Knowledge Representation (KR’06), 2006 · Zbl 1183.68569
[13] Bonet, B.; Gerevini, A.E.; Givan, R., Abstract booklet of the fifth int. planning competition, (2006)
[14] R. Brafman, Y. Chernyavsky, Planning with goal preferences and constraints, in: Proc. of 15th Int. Conf. on Automated Planning and Scheduling (ICAPS’05), 2005
[15] M. Briel, R. Sanchez, M. Do, S. Kambhampati, Effective approaches for partial satisfaction (over-subscription) planning, in: Proc. of 19th National Conf. on Artificial Intelligence (AAAI’04), 2004
[16] Chabrier, N., (2003)
[17] Chen, Y.; Wah, B.W.; Hsu, C., Temporal planning using subgoal partitioning and resolution in sgplan, Journal of artificial intelligence research, 26, 323-369, (2006) · Zbl 1182.68229
[18] Clarke, E.M.; Emerson, E.A.; Sistla, A.P., Automatic verification of finite-state concurrent systems using temporal logic specifications, ACM transactions on programming languages and systems, 8, 2, 244-263, (1986) · Zbl 0591.68027
[19] Clarke, E.M.; Grumberg, O.; Peled, D., Model checking, (1999), MIT Press
[20] S. Cresswell, A. Coddington, Compilation of LTL goal formulas into PDDL, in: Proc. of 15th European Conf. on Artificial Intelligence, (ECAI’04), 2004
[21] P.J. Delgrande, T. Schaub, H. Tompits, A general framework for expressing preferences in causal reasoning and planning, in: Proc. of 7th Int. Symposium on Logical Formalizations of Commonsense Reasoning, 2005 · Zbl 1132.68051
[22] M. Do, J. Benton, M. van den Briel, S. Kambhampati, Planning with goal utility dependencies, in: Proc. of 20th Int. Conf. on Artificial Intelligence (IJCAI’07), 2007 · Zbl 1145.68537
[23] M.B. Do, S. Kambhampati, Partial satisfaction (over-subscription) planning as heuristic search, in: Proc. of 5th Int. Conf. on Knowledge Based Computer Systems (KBCS’04), 2004
[24] Dubois, D.; Fargier, H.; Prade, H., Possibility theory in constraint satisfaction problems: handling priority, preference and uncertainty, Applied intelligence, 6, 287-309, (1996) · Zbl 1028.91526
[25] S. Edelkamp, On the compilation of plan constraints and preferences, in: Proc. of 16th Int. Conf. on Automated Planning and Scheduling (ICAPS’06), 2006
[26] S. Edelkamp, J. Hoffmann, PDDL2.2: The language for the classic part of the 4th International Planning Competition, Technical Report 195, Institut für Informatik, Freiburg, Germany, 2004
[27] Fink, A.; Voss, S., Applications of modern heuristic search methods to pattern sequencing problems, Computers & operations research, 26, 17-34, (1999) · Zbl 0957.90044
[28] M. Fox, D. Long, K. Halsey, An investigation into the expressive power of PDDL2.1, in: Proc. of 16th European Conf. on Artificial Intelligence (ECAI-04), 2004
[29] Fox, M.; Long, D., PDDL2.1: an extension to PDDL for expressing temporal planning domains, Journal of artificial intelligence research, 20, 61-124, (2003) · Zbl 1036.68093
[30] H. Geffner, P. Haslum, M. Helmert, J. Hoffmann, V. Vidal, B. Bonet, C. Domshlak, in: Proceedings of the ICAPS-07 Workshop on Heuristics for Domain-independent Planning: Progress, Ideas, Limitations, Challenges, 17th Int. Conf. on Automated Planning and Scheduling (ICAPS’07), 2007
[31] A. Gerevini, D. Long, Plan constraints and preferences in PDDL3, Technical Report RT-2005-08-47, Dipartimento di Elettronica per l’Automazione, Universitá di Brescia, 2005
[32] A. Gerevini, D. Long, Preferences and soft constraints in PDDL3, in: Proc. of ICAPS-2006 Workshop on Preferences and Soft Constraints in Planning, 2006
[33] A. Gerevini, A. Saetti, P. Haslum, D. Long, Y. Dimopoulos, Deterministic planning in the fifth planning competition: PDDL3 and experimental evaluation of the planners, Technical Report RT-2008-02-59, Dipartimento di Elettronica per l’Automazione, Universitá di Brescia, 2008 · Zbl 1191.68634
[34] Gerevini, A.; Saetti, A.; Serina, I., An approach to efficient planning with numerical fluents and multi-criteria plan quality, Artificial intelligence, 172, 8-9, 899-944, (2008) · Zbl 1183.68575
[35] R. Gerth, D. Peled, M. Vardi, P. Wolper, Simple on-the-fly automatic verification of linear temporal logic, in: Proc. of 15th Workshop on Protocol Specification, Testing and Verification, 1995
[36] M. Ghallab, A. Howe, C. Knoblock, D. McDermott, A. Ram, M. Veloso, D. Weld, D. Wilkins, PDDL - the planning domain definition language, Technical Report CVC TR98-003/DCS TR-1165, Yale Center for Computational Vision and Control, 1998
[37] E. Giunchiglia, M. Maratea, Planning as satisfiability with preferences, in: Proc. of 22nd Conf. of Artificial Intelligence (AAAI’07), 2007 · Zbl 1216.68245
[38] P. Haslum, Quality of solutions to IPC5 benchmark problems: Preliminary results, in: Proc. of ICAPS-07 Workshop on Int. Planning Competition: Past, Present & Future, 2007
[39] P. Haslum, P. Jonsson, Some results on the complexity of planning with incomplete information, in: Proc. of 5th European Conf. on Planning (ECP’99), 1999
[40] Helmert, M., The fast downward planning system, Journal of artificial intelligence research, 26, 191-246, (2006) · Zbl 1182.68245
[41] Hoffmann, J.; Edelkamp, S., The deterministic part of IPC-4: an overview, Journal of artificial intelligence research, 24, 519-579, (2005) · Zbl 1080.68669
[42] Hoffmann, J.; Edelkamp, S.; Thiébaux, S.; Englert, R.; Liporace, F.; Trüg, S., Engineering benchmarks for planning: the domains used in the deterministic part of IPC-4, Journal of artificial intelligence research, 26, 453-541, (2006) · Zbl 1183.68579
[43] Hoffmann, J.; Nebel, B., The FF planning system: fast plan generation through heuristic search, Journal of artificial intelligence research, 14, 253-302, (2001) · Zbl 0970.68044
[44] C. Hsu, B.W. Wah, Y. Chen, Personal communication, October 2007
[45] F. Kabanza, S. Thiébaux, Search control in planning for temporally extended goals, in: Proc. of 15th Int. Conf. on Automated Planning and Scheduling (ICAPS’05), 2005 · Zbl 1034.68549
[46] H. Kautz, SATPLAN04: Planning as satisfiability, in: 4th Int. Planning Competition Booklet, 2004
[47] Kohn, K., Molecular interaction map of the Mammalian cell cycle control and DNA repair systems, Molecular biology of the cell, 10, 8, (1999)
[48] Kvarnström, J.; Doherty, P., Talplanner: A temporal logic based forward chaining planner, Annals of mathematics and artificial intelligence, 30, 1-4, 119-169, (2000) · Zbl 1002.68158
[49] Linhares, A.; Yanasse, H.H., Connection between cutting-pattern sequencing, VLSI design and flexible machines, Computers & operations research, 29, 1759-1772, (2002) · Zbl 1259.90166
[50] Long, D.; Fox, M., The 3rd international planning competition: results and analysis, Journal of artificial intelligence research, 20, 1-59, (2003) · Zbl 1036.68097
[51] Long, D.; Kautz, H.; Selman, B.; Bonet, B.; Geffner, H.; Koehler, J.; Brenner, M.; Hoffmann, J.; Rittinger, F.; Anderson, C.; Weld, D.; Smith, D.; Fox, M., The AIPS-98 planning competition, AI magazine, 21, 2, 13-33, (2000)
[52] Manna, Z.; Pnueli, A., The temporal logic of reactive AND concurrent systems, (1992), Springer
[53] Miguel, I.; Jarvis, P.; Shen, Q., Efficient flexible planning via dynamic flexible constraint satisfaction, Engineering applications of artificial intelligence, 14, 3, 301-327, (2001)
[54] Nebel, B., On the compilability and the expressive power of propositional planning formalisms, Journal of artificial intelligence research, 12, 271-315, (2000) · Zbl 0943.68182
[55] J.S. Penberthy, Planning with continuous change, PhD thesis University of Washington, 1993. Available as technical report UW-CSE-93-12-01
[56] A. Pnueli, The temporal logic of programs, in: Proc. of 18th IEEE Symposium on Foundations of Computer Science, 1977
[57] Riera-Ledesma, J.; Salazar-Gonzalez, J.J., A heuristic approach for the travelling purchaser problem, European journal of operational research, 160, 3, 599-613, (2005) · Zbl 1061.90065
[58] J. Rintanen, Incorporation of temporal logic control into plan operators, in: Proc. of 14th European Conf. on Artificial Intelligence (ECAI’00), 2000
[59] J. Rintanen, Complexity of concurrent temporal planning, in: Proc. of 17th Int. Conf. on Automated Planning and Scheduling, 2007
[60] F. Rossi, K.B. Venable, N. Yorke-Smith, Controllability of soft temporal constraint problems, in: Proc. of 10th Int. Conf. on Principles and Practice of Constraint Programming (CP’04), 2004 · Zbl 1152.68579
[61] Smith, B.M.; Gent, I.P., Constraint modelling challenge 2005, (2005)
[62] D. Smith, Choosing objectives in over-subscription planning, in: Proc. of 14th Int. Conf. on Automated Planning and Scheduling (ICAPS’04), 2004
[63] T.C. Son, E. Pontelli, Planning with preferences using logic programming, in: Proc. of 7th Int. Conf. on Logic Programming and Nonmonotonic Reasoning (LPNMR’04), 2004 · Zbl 1122.68616
[64] Thagard, P., Pathways to biomedical discovery, Philosophy of science, 70, (2003)
[65] Thiébaux, S.; Hoffmann, J.; Nebel, B., In defense of PDDL axioms, Artificial intelligence, 168, 38-69, (2005) · Zbl 1132.68714
[66] Vidal, V.; Geffner, H., Branching and pruning: an optimal temporal POCL planner based on constraint programming, Artificial intelligence, 170, 3, 298-335, (2006) · Zbl 1131.68528
[67] Wilcoxon, F.; Wilcox, R.A., Some rapid approximate statistical procedures, (1964), Lederle Laboratories Pearl River, New York, USA
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.