×

zbMATH — the first resource for mathematics

A constraint programming formulation for planning: From plan scheduling to plan generation. (English) Zbl 1185.90110
Summary: Planning research is recently concerned with the resolution of more realistic problems as evidenced in the many works and new extensions to the Planning Domain Definition Language (PDDL) to better approximate real problems. Researchers’ works to push planning algorithms and capture more complex domains share an essential ingredient, namely the incorporation of new types of constraints. Adding constraints seems to be the way of approximating real problems: these constraints represent the duration of tasks, temporal and resource constraints, deadlines, soft constraints, etc., i.e. features that have been traditionally associated to the area of scheduling. This desired expressiveness can be achieved by augmenting the planning reasoning capabilities, at the cost of slightly deviating the planning process from its traditional implicit purpose, that is finding the causal structure of the plan. However, the resolution of complex domains with a great variety of different constraints may involve as much planning effort as scheduling effort (and perhaps the latter being more prominent in many problems). For this reason, in this paper we present a general approach to model those problems under a constraint programming formulation which allows us to represent and handle a wide range of constraints. Our work is based on the original model of \(\mathsf{CPT}\) , an optimal temporal planner, and it extends the \(\mathsf{CPT}\) ’s formulation to deal with more expressive constraints. We will show that our general formulation can be used for planning and/or scheduling, from scheduling a given complete plan to generating the whole plan from scratch. However, our contribution is not a new planner but a constraint programming formulation for representing highly-constrained planning + scheduling problems.
MSC:
90B36 Stochastic scheduling theory in operations research
90C29 Multi-objective and goal programming
90B90 Case-oriented studies in operations research
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Blum, A. L., & Furst, M. L. (1997). Fast planning through planning graph analysis. Artificial Intelligence, 90, 281–300. · Zbl 1017.68533
[2] Bonet, B., & Geffner, H. (1999). Planning as heuristic search: New results. In S. Biundo & M. Fox (Eds.), Proc. European conference on planning (ECP-99) (pp. 360–372). Springer.
[3] Bonet, B., & Geffner, H. (2001). Planning as heuristic search. Artificial Intelligence, 129, 5–33. · Zbl 0971.68146
[4] Chen, Y. X., Wah, B. W., & Hsu, C. W. (2006). Temporal planning using subgoal partitioning and resolution in SGPlan. Journal of Artificial Intelligence Research, 26, 323–369. · Zbl 1182.68229
[5] Dechter, R., Meiri, I., & Pearl, J. (1991). Temporal constraint networks. Artificial Intelligence, 49, 61–95. · Zbl 0737.68070
[6] Do, M. B., & Kambhampati, S. (2001a). Sapa: a domain-independent heuristic metric temporal planner. In A. Cesta & D. Borrajo (Eds.), Proc. European conference on planning (ECP-2001) (pp. 109–120).
[7] Do, M. B., & Kambhampati, S. (2001b). Planning as constraint satisfaction: Solving the planning graph by compiling it into CSP. Artificial Intelligence, 132, 151–182. · Zbl 0983.68181
[8] Edelkamp, S., & Hoffmann, J. (2004). PDDL2.2: the language for the classical part of IPC–4. In Proc. int. conference on automated planning and scheduling (ICAPS-2004)–International planning competition (pp. 2–6).
[9] Edelkamp, S., Jabbar, S., & Nazih, M. (2006). Large-scale optimal PDDL3 planning with MIPS-XXL. In Proc. int. conference on automated planning and scheduling (ICAPS-2006)–International planning competition (pp. 28–30).
[10] Fikes, R. E., & Nilsson, N. J. (1971). STRIPS: a new approach to the application of theorem proving to problem solving. Artificial Intelligence, 2, 189–208. · Zbl 0234.68036
[11] Fox, M., & Long, D. (2001). PDDL+: an extension to PDDL2.1 for modelling planning domains with continuous time-dependent effects (Technical report). University of Durham, UK.
[12] Fox, M., & Long, D. (2003). PDDL2.1: an extension to PDDL for expressing temporal planning domains. Journal of Artificial Intelligence Research, 20, 61–124. · Zbl 1036.68093
[13] Fox, M., & Long, D. (2006). Modelling mixed discrete-continuous domains for planning. Journal of Artificial Intelligence Research, 27, 235–297. · Zbl 1182.68238
[14] Garrido, A., & Long, D. (2004). Planning with numeric variables in multi-objective planning. In L. Saitta (Ed.), Proc. European conference on AI (ECAI-2004), Amsterdam (pp. 662–666). IOS Press.
[15] Garrido, A., Onaindía, E., & Arangu, M. (2006). Using constraint programming to model complex plans in an integrated approach for planning and scheduling. In Proc. 25th UK planning and scheduling SIG workshop (pp. 137–144).
[16] Garrido, A., Onaindia, E., & Sapena, O. (2008). Planning and scheduling in an e-learning environment. A constraint-programming-based approach. Engineering Applications of Artificial Intelligence, 21(5), 733–743.
[17] Gerevini, A., & Long, D. (2006). Plan constraints and preferences in PDDL3. In Proc. int. conference on automated planning and scheduling (ICAPS-2006)–International planning competition (pp. 7–13).
[18] Ghallab, M., & Laruelle, H. (1994). Representation and control in IxTeT, a temporal planner. In Proc. 2nd int. conference on AI planning systems (pp. 61–67). Hammond.
[19] Ghallab, M., Nau, D., & Traverso, P. (2004). Automated planning. Theory and practice. San Mateo: Morgan Kaufmann. · Zbl 1074.68613
[20] Haslum, P. (2006). Improving heuristics through relaxed search–an analysis of TP4 and HSP*a in the 2004 planning competition. Journal of Artificial Intelligence Research, 25, 233–267. · Zbl 1182.68062
[21] Haslum, P., & Geffner, H. (2001). Heuristic planning with time and resources. In Proc. IJCAI-2001 workshop on planning with resources.
[22] Hoffmann, J., & Nebel, B. (2001). The FF planning system: Fast plan generation through heuristic search. Journal of Artificial Intelligence Research, 14, 253–302. · Zbl 0970.68044
[23] Hoffmann, J., Edelkamp, S., Englert, R., Liporace, F., Thiebaux, S., & Trug, S. (2004). Towards realistic benchmarks for planning: the domains used in the classical part of IPC–4. In Proc. int. conference on automated planning and scheduling (ICAPS-2004)–International planning competition (pp. 7–14).
[24] Jónsson, A., Morris, P., Muscettola, N., Rajan, K., & Smith, B. (2000). Planning in interplanetary space: theory and practice. In Proc. 5th int. conference on AI planning systems (AIPS-2000) (pp. 177–186). Menlo Park: AAAI Press.
[25] Long, D., & Fox, M. (2001). Encoding temporal planning domains and validating temporal plans. In Proc. 20th UK planning and scheduling SIG workshop (pp. 167–180).
[26] Long, D., & Fox, M. (2003). Time in planning. In Handbook of temporal reasoning in AI. Foundations of artificial intelligence (Vol. 1, pp. 497–537). Amsterdam: Elsevier Science.
[27] Mittal, S., & Falkenhainer, B. (1990). Dynamic constraint satisfaction problems. In Proc. natl. conference on artificial intelligence (pp. 25–32).
[28] Muscettola, N. (1994). HSTS: Integrating planning and scheduling. In M. Zweben & M. S. Fox (Eds.), Intelligent scheduling (pp. 169–212). San Mateo: Morgan Kaufmann.
[29] Penberthy, J., & Weld, D. (1994). Temporal planning with continuous change. In Proc. 12th natl. conference on AI (pp. 1010–1015).
[30] Penberthy, J., & Weld, D. S. (1992). UCPOP: a sound, complete, partial-order planner for ADL. In Proc. int. conference on principles of knowledge representation and reasoning (pp. 103–114). Los Altos: Kaufmann.
[31] Smith, D. E., & Weld, D. S. (1999). Temporal planning with mutual exclusion reasoning. In Proc. 16th int. joint conference on AI (IJCAI-99), Stockholm, Sweden (pp. 326–337).
[32] Smith, D. E., Frank, J., & Jónsson, A. K. (2000). Bridging the gap between planning and scheduling. Knowledge Engineering Review, 15(1), 47–83. · Zbl 02020687
[33] Van Beek, P., & Chen, X. (1999). CPlan: a constraint programming approach to planning. In Proc. natl. conf. on artificial intelligence (AAAI-99) (pp. 585–590).
[34] Vidal, V., & Geffner, H. (2004). Branching and pruning: an optimal temporal POCL planner based on constraint programming. In Proc. natl. conf. on artificial intelligence (AAAI-04) (pp. 570–577). · Zbl 1131.68528
[35] Vidal, V., & Geffner, H. (2006). Branching and pruning: an optimal temporal POCL planner based on constraint programming. Artificial Intelligence, 170, 298–335. · Zbl 1131.68528
[36] Weld, D. S. (1999). Recent advances in AI planning. AI Magazine, 20(2), 93–123.
[37] Younes, H. L. S., & Simmons, R. G. (2003). VHPOP: Versatile heuristic partial order planner. Journal of Artificial Intelligence Research, 20, 405–430. · 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.