×

Managing concurrency in temporal planning using planner-scheduler interaction. (English) Zbl 1180.68245

Summary: Metric temporal planning involves both selecting and organising actions to satisfy the goals and also assigning to each of these actions its start time and, where necessary, its duration. The assignment of start times to actions is a central concern of scheduling. In PDDL2.1, the widely adopted planning domain description language standard, metric temporal planning problems are described using actions with durations. A large number of planners have been developed to handle this language, but the great majority of them are fundamentally limited in the class of temporal problems they can solve.In this paper, we review the source of this limitation and present an approach to metric temporal planning that is not so restricted. Our approach links planning and scheduling algorithms into a planner, Crikey, that can successfully tackle a wide range of temporal problems. We show how Crikey can be simplified to solve a wide and interesting subset of metric temporal problems, while remaining competitive with other temporal planners that are unable to handle required concurrency. We provide empirical data comparing the performance of this planner, Crikey\(_{\text{SHE}}\), our original version, Crikey, and a range of other modern temporal planners.Our contribution is to describe the first competitive planner capable of solving problems that require concurrent actions.

MSC:

68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
68Q85 Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.)

Software:

PDDL; LPG; VHPOP; SAPA
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Fox, M.; Long, D., PDDL2.1: An extension of PDDL for expressing temporal planning domains, Journal of Artificial Intelligence Research (JAIR), 20, 61-124 (2003) · Zbl 1036.68093
[2] Gerevini, A.; Serina, I., LPG: A planner based on local search for planning graphs, (Proceedings of the 6th International Conference of Artificial Intelligence Planning and Scheduling (AIPS’02) (2002), AAAI Press: AAAI Press Menlo Park, CA) · Zbl 1058.68103
[3] Younes, H. L.S.; Simmons, R. G., VHPOP: Versatile heuristic partial order planner, Journal of Artificial Intelligence Research (JAIR), 20, 405-430 (2003) · Zbl 1036.68107
[4] Edelkamp, S., Taming numbers and durations in the model checking integrated planning system, Journal of Artificial Research (JAIR), 20, 195-238 (2003) · Zbl 1036.68092
[5] Chen, Y.; Wah, B. W.; Hsu, C., Temporal planning using subgoal partitioning and resolution in sgplan, Journal of Artificial Intelligence Research (JAIR), 26, 323-369 (2006) · Zbl 1182.68229
[6] D. Long, M. Fox, Exploiting a graphplan framework in temporal planning, in: Proceedings of the 13th International Conference on Automated Planning and Scheduling (ICAPS), 2003, pp. 52-61; D. Long, M. Fox, Exploiting a graphplan framework in temporal planning, in: Proceedings of the 13th International Conference on Automated Planning and Scheduling (ICAPS), 2003, pp. 52-61
[7] A. Garrido, M. Fox, D. Long, A temporal planning system to manage level 3 durative actions of PDDL2.1, in: Proceedings of the 20th UK Planning and Scheduling Special Interest Group (PlanSIG), 2001, pp. 127-138; A. Garrido, M. Fox, D. Long, A temporal planning system to manage level 3 durative actions of PDDL2.1, in: Proceedings of the 20th UK Planning and Scheduling Special Interest Group (PlanSIG), 2001, pp. 127-138
[8] M.B. Do, S. Kambhampati, Sapa: A domain-independent heuristic metric temporal planner, in: Proceedings from the 6th European Conference of Planning (ECP), 2001, pp. 82-91; M.B. Do, S. Kambhampati, Sapa: A domain-independent heuristic metric temporal planner, in: Proceedings from the 6th European Conference of Planning (ECP), 2001, pp. 82-91
[9] P. Haslum, H. Geffner, Heuristic planning with time and resources, in: Proceedings of the 6th European Conference on Planning (ECP), 2001, pp. 121-132; P. Haslum, H. Geffner, Heuristic planning with time and resources, in: Proceedings of the 6th European Conference on Planning (ECP), 2001, pp. 121-132
[10] Ghallab, M.; Laruelle, H., Representation and control in IxTeT, a temporal planner, (Proceedings of the Second International Conference on Artificial Intelligence Planning Systems (AIPS-94) (1994), AAAI Press: AAAI Press Menlo Park, CA), 61-67
[11] Bacchus, F.; Kabanza, F., Using temporal logics to express search control knowledge for planning, Artificial Intelligence, 116, 1-2, 123-191 (2000) · Zbl 0939.68827
[12] P. Doherty, J. Kvarnstrom, TALplanner: An empirical investigation of a temporal logic-based forward chaining planner, in: Proceedings of the 6th International Workshop on the Temporal Representation and Reasoning, Orlando, Fl. (TIME’99), 1999; P. Doherty, J. Kvarnstrom, TALplanner: An empirical investigation of a temporal logic-based forward chaining planner, in: Proceedings of the 6th International Workshop on the Temporal Representation and Reasoning, Orlando, Fl. (TIME’99), 1999 · Zbl 1002.68158
[13] D. Smith, D.S. Weld, Temporal planning with mutual exclusion reasoning, in: Proceedings of the 16th International Joint Conference on Artificial Intelligence (IJCAI), 1999, pp. 326-337; D. Smith, D.S. Weld, Temporal planning with mutual exclusion reasoning, in: Proceedings of the 16th International Joint Conference on Artificial Intelligence (IJCAI), 1999, pp. 326-337
[14] J. Penberthy, D. Weld, Temporal planning with continuous change, in: Proceedings of the 12th National Conference on Artificial Intelligence (AAAI), 1994; J. Penberthy, D. Weld, Temporal planning with continuous change, in: Proceedings of the 12th National Conference on Artificial Intelligence (AAAI), 1994
[15] K. Halsey, D. Long, M. Fox, CRIKEY—A planner looking at the integration of scheduling and planning, in: Proceedings of the Workshop on Integration Scheduling Into Planning at 13th International Conference on Automated Planning and Scheduling (ICAPS’03), 2004, pp. 46-52; K. Halsey, D. Long, M. Fox, CRIKEY—A planner looking at the integration of scheduling and planning, in: Proceedings of the Workshop on Integration Scheduling Into Planning at 13th International Conference on Automated Planning and Scheduling (ICAPS’03), 2004, pp. 46-52
[16] W. Cushing, S. Kambhampati, Mausam, D. Weld, When is temporal planning really temporal planning? in: Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI), 2007, pp. 1852-1859; W. Cushing, S. Kambhampati, Mausam, D. Weld, When is temporal planning really temporal planning? in: Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI), 2007, pp. 1852-1859
[17] Smith, D.; Frank, J.; Jónsson, A., Bridging the gap between planning and scheduling, Knowledge Engineering Review, 15, 61-94 (2000)
[18] P. Laborie, M. Ghallab, IxTeT: An integrated approach for plan generation and scheduling, in: Proceedings of INRIA/IEEE Symposium on Emerging Technologies and Factory Automation, 1995, pp. 485-495; P. Laborie, M. Ghallab, IxTeT: An integrated approach for plan generation and scheduling, in: Proceedings of INRIA/IEEE Symposium on Emerging Technologies and Factory Automation, 1995, pp. 485-495
[19] M. Boddy, A. Cesta, S. Smith (Eds.), Proceedings of Workshop on Integrating Planning into Scheduling (WIPIS), 2004; M. Boddy, A. Cesta, S. Smith (Eds.), Proceedings of Workshop on Integrating Planning into Scheduling (WIPIS), 2004
[20] Edelkamp, S.; Helmert, M., On the implementation of MIPS, (AIPS-2000 Workshop on Decision-Theoretic Planning (2000), AAAI-Press), 18-25
[21] Allen, J. F., Maintaining knowledge about temporal intervals, Communications of the ACM, 832-843 (1983) · Zbl 0519.68079
[22] M. Fox, D. Long, K. Halsey, An investigation into the expressive power of PDDL2.1, in: Proceedings of the 16th European Conference of Artificial Intelligence (ECAI), 2004; M. Fox, D. Long, K. Halsey, An investigation into the expressive power of PDDL2.1, in: Proceedings of the 16th European Conference of Artificial Intelligence (ECAI), 2004
[23] Hoffmann, J.; Nebel, B., The FF planning system: Fast plan generation through heuristic search, Journal of Artificial Intelligence Research (JAIR), 14, 253-302 (2001) · Zbl 0970.68044
[24] Veloso, M. M.; Pérez, M. A.; Carbonell, J. G., Nonlinear planning with parallel resource allocation, (Proceedings of the DARPA Workshop on Innovative Approaches to Planning, Scheduling, and Control (1990), Morgan Kaufmann: Morgan Kaufmann San Diego, CA), 207-212
[25] R. Dechter, I. Meiri, J. Pearl, Temporal constraint networks, in: Proceedings from Principles of Knowledge Representation and Reasoning, 1989, pp. 83-93; R. Dechter, I. Meiri, J. Pearl, Temporal constraint networks, in: Proceedings from Principles of Knowledge Representation and Reasoning, 1989, pp. 83-93 · Zbl 0709.68101
[26] P. Laborie, D. Godard, Self-adapting large neighbourhood search: Application to single-mde scheduling problems, in: Proceedings of MISTA-07, 2007; P. Laborie, D. Godard, Self-adapting large neighbourhood search: Application to single-mde scheduling problems, in: Proceedings of MISTA-07, 2007
[27] Laborie, P., Algorithms for propagating resource constraints in AI planning and scheduling: Existing approaches and new results, Artificial Intelligence, 143, 2, 151-188 (2003) · Zbl 1079.68622
[28] J. Hoffmann, Extending FF to numerical state variables, in: Proceedings of the 15th European Conference on Artificial Intelligence (ECAI), 2002, pp. 571-575; J. Hoffmann, Extending FF to numerical state variables, in: Proceedings of the 15th European Conference on Artificial Intelligence (ECAI), 2002, pp. 571-575
[29] Hoffmann, J.; Edelkamp, S., The deterministic part of IPC-4: An overview, Journal of Artificial Intelligence Research (JAIR), 24, 519-579 (2005) · Zbl 1080.68669
[30] S. Cresswell, A. Coddington, Planning with timed literals and deadlines, in: J. Porteous (Ed.), Proceedings of the 22nd Workshop of the UK Planning and Scheduling Special Interest Group, University of Strathclyde, 2003, pp. 22-35, ISSN 1368-5708; S. Cresswell, A. Coddington, Planning with timed literals and deadlines, in: J. Porteous (Ed.), Proceedings of the 22nd Workshop of the UK Planning and Scheduling Special Interest Group, University of Strathclyde, 2003, pp. 22-35, ISSN 1368-5708
[31] T. Vidal, M. Ghallab, Constraint-based temporal management in planning: the IxTeT approach, in: Proc. of 12th European Conference on AI, 1996; T. Vidal, M. Ghallab, Constraint-based temporal management in planning: the IxTeT approach, in: Proc. of 12th European Conference on AI, 1996
[32] A. Tate, Generating project networks, in: Proceedings of IJCAI-77, 1977; A. Tate, Generating project networks, in: Proceedings of IJCAI-77, 1977
[33] Drabble, B.; Tate, A., The use of optimistic and pessimistic resource profiles to inform search in an activity based planner, (Proc. of 2nd Conference on AI Planning Systems (AIPS) (1994), AAAI Press)
[34] A. Tate, The 〈I-N-OVA〉 constraint model of plans, in: Proceedings of the Third International Conference on Artificial Intelligence Planning Systems, 1996, pp. 221-228; A. Tate, The 〈I-N-OVA〉 constraint model of plans, in: Proceedings of the Third International Conference on Artificial Intelligence Planning Systems, 1996, pp. 221-228
[35] Muscettola, N., HSTS: Integrating planning and scheduling, (Zweben, M.; Fox, M., Intelligent Scheduling (1994), Morgan Kaufmann: Morgan Kaufmann San Mateo, CA), 169-212
[36] M. Ai-Change, J. Bresina, L. Charest, J. Hsu, A. Jónsson, R. Kanefsy, P. Maldegue, P. Morris, K. Rajan, J. Yglesias, MAPGEN: Mixed intitive activity planning for the Mars Exploratory Rover mission, in: Proceedings of Demonstration Systems Track, ICAPS’03, 2003; M. Ai-Change, J. Bresina, L. Charest, J. Hsu, A. Jónsson, R. Kanefsy, P. Maldegue, P. Morris, K. Rajan, J. Yglesias, MAPGEN: Mixed intitive activity planning for the Mars Exploratory Rover mission, in: Proceedings of Demonstration Systems Track, ICAPS’03, 2003
[37] G. Rabideau, R. Knight, S. Chien, A. Fukunaga, A. Govindjee, Iterative repair planning for spacecraft operations in the ASPEN system, in: International Symposium on Artificial Intelligence Robotics and Automation in Space (ISAIRAS), 1999; G. Rabideau, R. Knight, S. Chien, A. Fukunaga, A. Govindjee, Iterative repair planning for spacecraft operations in the ASPEN system, in: International Symposium on Artificial Intelligence Robotics and Automation in Space (ISAIRAS), 1999
[38] Vere, S., Planning in time: Windows and durations for activities and goals, IEEE Trans. on Pattern Analysis and MI, 5, 246-267 (1983)
[39] M. Fox, D. Long, The third international planning competition: Temporal and metric planning, in: Proceedings from the 6th International Conference on Artificial Intelligence Planning and Scheduling (AIPS), 2002, pp. 115-117; M. Fox, D. Long, The third international planning competition: Temporal and metric planning, in: Proceedings from the 6th International Conference on Artificial Intelligence Planning and Scheduling (AIPS), 2002, pp. 115-117
[40] J. Rintanen, Complexity of concurrent temporal planning, in: Proceedings of the 17th International Conference on Automated Planning and Scheduling (ICAPS), 2007, pp. 280-287; J. Rintanen, Complexity of concurrent temporal planning, in: Proceedings of the 17th International Conference on Automated Planning and Scheduling (ICAPS), 2007, pp. 280-287
[41] M. Fox, D. Long, A note on concurrency and complexity in temporal planning, in: Proceedings of the 26th UK Planning and Scheduling Special Interest Group (PlanSIG), 2007; M. Fox, D. Long, A note on concurrency and complexity in temporal planning, in: Proceedings of the 26th UK Planning and Scheduling Special Interest Group (PlanSIG), 2007
[42] A.I. Coles, M. Fox, D. Long, A.J. Smith, Planning with respect to an existing schedule of events, in: Proceedings of the 17th International Conference on Automated Planning and Scheduling (ICAPS), 2007, pp. 81-88; A.I. Coles, M. Fox, D. Long, A.J. Smith, Planning with respect to an existing schedule of events, in: Proceedings of the 17th International Conference on Automated Planning and Scheduling (ICAPS), 2007, pp. 81-88
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.