×

zbMATH — the first resource for mathematics

Managing temporal cycles in planning problems requiring concurrency. (English) Zbl 1274.68419
Summary: To correctly model certain real-world planning problems, it is essential to take into account time. This is the case for problems requiring the concurrent execution of actions (known as temporally expressive problems). In this paper, we define and study the notion of temporally cyclic problems, that is problems involving sets of cyclically dependent actions. We characterize those temporal planning languages, which can express temporally cyclic problems. We also present a polynomial-time algorithm, which transforms a temporally cyclic problem into an equivalent acyclic problem. Applying our transformation allows any temporal planner to solve temporally cyclic problems without explicitly managing cyclicity. We first present our results for temporal PDDL (planning domain description language) 2.1 and then extend them to a language that allows conditions over arbitrary intervals and effects at arbitrary instants.
Reviewer: Reviewer (Berlin)

MSC:
68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
Software:
Graphplan; PDDL
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Allen, Towards a general theory of action and time, Artificial Intelligence 23 (2) pp 123– (1984) · Zbl 0567.68025 · doi:10.1016/0004-3702(84)90008-0
[2] Allen , J.F. J. A. G. M. Koomen 1983 Planning using a temporal world model In Proceedings of the 8th International Joint Conference on Artificial Intelligence 741 747
[3] Blum , A. L. M. L. Furst 1995 Fast planning through planning-graphs analysis In Proceedings of the 14th International Joint Conference on Artificial Intelligence 1636 1642 · Zbl 1017.68533
[4] Bylander, The computational complexity of propositional STRIPS planning, Artificial Intelligence 69 (1-2) pp 165– (1994) · Zbl 0821.68065 · doi:10.1016/0004-3702(94)90081-7
[5] Coles , A. M. Fox D. Long A. Smith 2008 Planning with problems requiring temporal coordination In Proceedings of the AAAI 892 897
[6] Cooper , M. F. Maris P. Régnier 2010 Compilation of a high-level temporal planning language into PDDL 2.1 In Proceedings of the 22nd International Conference on Tools with Artificial Intelligence 2 181 188
[7] Cushing , W. S. Kambhampati Mausam D. S. Weld 2007 When is temporal planning really temporal? In Proceedings of the 20th International Joint Conference on Artificial Intelligence 1852 1859
[8] Dean, Hierarchical planning involving deadlines, travel time and resources, Computational Intelligence 6 (1) pp 381– (1988) · doi:10.1111/j.1467-8640.1988.tb00287.x
[9] Fox, PDDL2.1: An extension to PDDL for expressing temporal planning domains, Journal of Artificial Intelligence Research 20 pp 61– (2003) · Zbl 1036.68093
[10] Fox , M. D. Long K. Halsey 2004 An investigation into the expressive power of PDDL2.1 In Proceedings of the 16th European Conference on Artificial Intelligence 328 342
[11] Gerevini , A. A. Saetti I. Serina 2010 Temporal planning with problems requiring concurrency through action graphs and local search In Proceedings of the 20th International Conference on Automated Planning and Scheduling 226 229 · Zbl 1058.68103
[12] Ghallab M. A. M. Alaoui 1989 Managing efficiently temporal relations through indexed spanning trees In Proceedings of the 11th International Joint Conference on Artificial Intelligence 1297 1303 · Zbl 0718.68080
[13] Halsey , K. D. Long M. Fox 2004 CRIKEY - A planner looking at the integration of scheduling and planning In Proceedings of the ”Integration Scheduling Into Planning” Workshop, ICAPS’03 46 52
[14] Hu , Y. 2007 Temporally-expressive planning as constraint satisfaction problems In Proceedings of the 20th International Joint Conference on Artificial Intelligence 192 199
[15] Huang , R. Y. Chen W. Zhang 2009 An optimal temporally expressive planner: Initial results and application to P2P network optimization In Proceedings of the 19th International Conference on Automated Planning and Scheduling Edited by A. Geravini A. Howe A. Cesta I. Refanidis AAI Press
[16] Laborie , P. M. Ghallab 1995 Planning with sharable resource constraints In Proceedings of the 14th International Joint Conference on Artificial Intelligence 1643 1651
[17] Long , D. M. Fox 2003 Exploiting a graphplan framework in temporal planning In Proceedings of the 13th International Conference on Automated Planning and Scheduling Edited by E. Giunchiglia N. Muscettola D. Nau AAAI Press 52 61
[18] Maris , F. P. Régnier 2008a TLP-GP: Solving temporally-expressive planning problems In Proceedings of the 15th International Symposium on Temporal Representation and Reasoning 137 144
[19] Maris , F. P. Régnier 2008b TLP-GP: New results on temporally-expressive planning benchmarks In Proceedings of the 20th IEEE International Conference on Tools with Artificial Intelligence 1 507 514
[20] Maris, Planification temporellement expressive, Revue d’Intelligence Artificielle 24 (4) pp 445– (2010) · doi:10.3166/ria.24.445-464
[21] Mcdermott, Technical Report CVC TR98003/DCS TR1165 (1998)
[22] Muscettola, Intelligent Scheduling pp 169– (1994)
[23] Reichgelt , H. N. Shadbolt 1990 A specification tool for planning systems In Proceedings of the 9th European Conference on Artificial Intelligence 541 546
[24] Rintanen , J. 2007 Complexity of concurrent temporal planning In Proceedings of the 17 th International Conference on Automated Planning and Scheduling 280 287
[25] Rutten, Temporal planner = Nonlinear planner + Time map manager, Artificial Intelligence Communications 6 (1) pp 18– (1993)
[26] Schwartz , P. M. E. Pollack 2004 Planning with disjunctive temporal constraints In Proceedings of the ICAPS’04 Workshop on Integrating Planning into Scheduling 67 74
[27] Shin J. E. Davis 2004 Continuous time in a SAT-based planner In Proceedings of the 19th National Conference on Artificial Intelligence (AAAI’04) 531 536
[28] Smith, The case for durative actions: A commentary on PDDL2.1, Journal of Artificial Intelligence Research 20 pp 149– (2003) · Zbl 1036.68102
[29] Tarjan, Depth-first search and linear graph algorithms, SIAM Journal on Computing 1 (2) pp 146– (1972) · Zbl 0251.05107 · doi:10.1137/0201010
[30] Tsang, TLP - A Temporal Planner, On Advances in Artificial Intelligence pp 63– (1987)
[31] Wolfman , S. D. Weld 1999 The LPSAT engine and its application to resource planning In Proceedings of the 16th International Joint Conference on Artificial Intelligence 310 317
[32] Younes, VHPOP: Versatile heuristic partial order planner, Journal of Artificial Intelligence Research 20 pp 405– (2003) · Zbl 1036.68107
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.