×

zbMATH — the first resource for mathematics

An approach to efficient planning with numerical fluents and multi-criteria plan quality. (English) Zbl 1183.68575
Summary: Dealing with numerical information is practically important in many real-world planning domains where the executability of an action can depend on certain numerical conditions, and the action effects can consume or renew some critical continuous resources, which in PDDL can be represented by numerical fluents. When a planning problem involves numerical fluents, the quality of the solutions can be expressed by an objective function that can take different plan quality criteria into account. We propose an incremental approach to automated planning with numerical fluents and multi-criteria objective functions for PDDL numerical planning problems. The techniques in this paper significantly extend the framework of planning with action graphs and local search implemented in the LPG planner. We define the numerical action graph (NA-graph) representation for numerical plans and we propose some new local search techniques using this representation, including a heuristic search neighborhood for NA-graphs, a heuristic evaluation function based on relaxed numerical plans, and an incremental method for plan quality optimization based on particular search restarts. Moreover, we analyze our approach through an extensive experimental study aimed at evaluating the importance of some specific techniques for the performance of the approach, and at analyzing its effectiveness in terms of fast computation of a valid plan and quality of the best plan that can be generated within a given CPU-time limit. Overall, the results show that our planner performs quite well compared to other state-of-the-art planners handling numerical fluents.

MSC:
68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
90C90 Applications of mathematical programming
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] F. Bacchus, M. Ady, Planning with resources and concurrency: A forward chaining approach, in: Proceedings 17th International Joint Conference on Artificial Intelligence (IJCAI-01), Seattle, WA, USA, 2001, pp. 417-424
[2] J. Benton, M.B. Do, S. Kambhampati, Over-subscription planning with numeric goals, in: Proceedings 19th International Joint Conference on Artificial Intelligence (IJCAI-05), Edinburgh, Scotland, 2005, pp. 1207-1214
[3] Blum, A.; Furst, M.L., Fast planning through planning graph analysis, Artificial intelligence, 90, 281-300, (1997) · Zbl 1017.68533
[4] Chen, Y.; Hsu, C.; Wah, B., Temporal planning using subgoal partitioning and resolution in sgplan, Journal of artificial intelligence research (JAIR), 26, 323-369, (2006) · Zbl 1182.68229
[5] Y. Chen, C. Hsu, W. Wha, SGPlan: Subgoal partitioning and resolution in planning, in: Abstract Booklet of the Competing Planners of ICAPS-04, 2004, pp. 30-32
[6] Dechter, R.; Meiri, I.; Pearl, J., Temporal constraint networks, Artificial intelligence, 49, 61-95, (1991) · Zbl 0737.68070
[7] Y. Dimopoulos, A. Gerevini, P. Haslum, A. Saetti, The benchmark domains of the deterministic part of IPC-5, in: Abstract Booklet of the Competing Planners of ICAPS-06, 2006, pp. 14-19
[8] Do, M.; Kambhampati, S., Sapa: A multi-objective metric temporal planner, Journal of artificial intelligence research (JAIR), 20, 155-194, (2003) · Zbl 1036.68091
[9] Edelkamp, S., Taming numbers and duration in the model checking integrated planning system, Journal of artificial intelligence research (JAIR), 20, 61-124, (2003) · Zbl 1036.68092
[10] M. Fox, D. Long, Utilizing automatically inferred invariants in graph construction and search, in: Proceedings 5th International Conference on Artificial Intelligence Planning and Scheduling (AIPS-00), Breckenridge, CO, USA, 2000, pp. 102-111
[11] Fox, M.; Long, D., PDDL2.1: an extension to PDDL for expressing temporal planning domains, Journal of artificial intelligence research (JAIR), 20, 61-124, (2003) · Zbl 1036.68093
[12] A. Garrido, D. Long, Planning with numeric variables in multi-objective planning, in: Proceedings 16th European Conference on Artificial Intelligence (ECAI-04), Valencia, Spain, 2004, pp. 662-666
[13] A. Gerevini, D. Long, Plan constraints and preferences in PDDL3, Technical Report 2005-08-47, Università degli Studi di Brescia, Dipartimento di Elettronica per l’Automazione, 2005
[14] Gerevini, A.; Saetti, A.; Serina, I., On managing temporal information for handling durative actions in LPG, (), 91-104
[15] Gerevini, A.; Saetti, A.; Serina, I., Planning through stochastic local search and temporal action graphs, Journal of artificial intelligence research (JAIR), 20, 239-290, (2003) · Zbl 1058.68103
[16] A. Gerevini, A. Saetti, I. Serina, An empirical analysis of some heuristic features for local search in LPG, in: Proceedings 14th International Conference on Automated Planning and Scheduling (ICAPS-04), Whistler, Canada, 2004, pp. 171-180
[17] Gerevini, A.; Saetti, A.; Serina, I., An approach to temporal planning and scheduling in domains with predictable exogenous events, Journal of artificial intelligence research (JAIR), 25, 187-231, (2006) · Zbl 1161.68783
[18] A. Gerevini, A. Saetti, I. Serina, An approach to efficient planning with numerical fluents and multi-criteria plan quality (preliminary report), Technical Report 2007-01-53, Università degli Studi di Brescia, Dip. di Elettronica per l’Automazione, 2007 · Zbl 1183.68575
[19] A. Gerevini, I. Serina, Fast planning through greedy action graphs, in: Proceedings 16th National Conference on Artificial Intelligence (AAAI-99), Orlando, FL, USA, 1999, pp. 503-510
[20] 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
[21] Ghallab, M.; Nau, D.; Traverso, P., Automated planning: theory and practice, (2003), Morgan Kaufmann Publishers San Francisco, CA, USA
[22] Glover, F.; Laguna, M., Tabu search, (1997), Kluwer Academic Publishers Boston, MA, USA · Zbl 0930.90083
[23] Goldberg, D.E., Genetic algorithms in search, optimization and machine learning, (1989), Addison-Wesley Boston, MA, USA · Zbl 0721.68056
[24] P. Haslum, H. Geffner, Heuristic planning with time and resources, in: Proceedings 6th European Conference on Planning (ECP-01), Toledo, Spain, 2001
[25] M. Helmert, Decidability and undecidability results for planning with numerical state variables, in: Proceedings 6th International Conference on Artificial Intelligence Planning and Scheduling (AIPS-02), Toulouse, France, 2002, pp. 303-312
[26] Helmert, M., The fast downward planning system, Journal of artificial intelligence research (JAIR), 26, 191-246, (2006) · Zbl 1182.68245
[27] Hoffmann, J., The metric-FF planning system: translating “ignoring delete lists”, to numeric state variables, Journal of artificial intelligence research (JAIR), 20, 291-341, (2003) · Zbl 1036.68095
[28] 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
[29] Hoffmann, J.; Edelkamp, S.; Thièbaux, S.; Englert, R.; Liporace, F.; Trueg, S., Engineering benchmarks for planning: the domains used in the deterministic part of IPC-4, Journal of artificial intelligence research (JAIR), 26, 453-541, (2006) · Zbl 1183.68579
[30] J. Hoffmann, H. Kautz, C. Gomes, B. Selman, SAT encodings of state-space reachability problems in numeric domains, in: Proceedings 20th International Joint Conference on Artificial Intelligence (IJCAI-07), Hyderabad, India, 2007
[31] 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
[32] C. Hsu, B.W. Wah, R. Huang, Y. Chen, New features in SGPlan for handling preferences and constraints in PDDL3.0, in: Abstract Booklet of the competing planners of IPC-5, 2006, pp. 39-41
[33] H. Kautz, J.P. Walser, State-space planning by integer optimization, in: Proceedings 16th National Conference on Artificial Intelligence (AAAI-98), Madison, WI, USA, 1998, pp. 526-533
[34] J. Koehler, Planning under resource constraints, in: Proceedings 13th European Conference on Artificial Intelligence (ECAI-98), Brighton, UK, 1998, pp. 489-493
[35] J. Koehler, B. Nebel, J. Hoffmann, Y. Dimopoulos. Extending planning graphs to an ADL subset, Technical Report 88, Institut für Informatik, Freiburg, Germany, 1997
[36] Long, D.; Fox, M., The 3rd international planning competition: results and analysis, Journal of artificial intelligence research (JAIR), 20, 1-59, (2003) · Zbl 1036.68097
[37] D. Nau, Y. Cao, A. Lotem, H. Muñoz Avila, SHOP: Simple hierarchical ordered planner, in: Proceedings 16th International Joint Conference on Artificial Intelligence (IJCAI-99), Stockholm, Sweden, 1999, pp. 968-973
[38] J.S. Penberthy, D.S. Weld, Temporal planning with continuous change, in: Proceedings 12th National Conference on Artificial Intelligence (AAAI-94), Seattle, WA, USA, 1994, pp. 1010-1015
[39] S.J. Penberthy, Planning with continuous change, PhD thesis, University of Washington, 1993. Available as technical report UW-CSE-93-12-01
[40] Ramesh, T., Traveling purchaser problem, Opsearch, 18, 78-91, (1981) · Zbl 0468.90048
[41] I. Refanidis, I. Vlahavas, GRT: A domain independent heuristic for STRIPS worlds based on greedy regression tables, in: Proceedings 5th European Conference on Planning (ECP-99), Durham, UK, 1999, pp. 346-358
[42] I. Refanidis, I. Vlahavas, Heuristic planning with resources, in: Proceedings 14th European Conference on Artificial Intelligence (ECAI-00), Berlin, Germany, 2000, pp. 521-525
[43] Refanidis, I.; Vlahavas, I., Multiobjective heuristic state-space planning, Artificial intelligence journal, 145, 1-2, 1-32, (2003) · Zbl 1082.68812
[44] B. Selman, H.A. Kautz, B. Cohen, Noise strategies for improving local search, in: Proceedings 12th National Conference on Artificial Intelligence (AAAI-94), Seattle, WA, USA, 1994, pp. 337-343
[45] Simon, A.H., Models of man, (1957), John Wiley & Sons Inc. New York, USA
[46] D. Smith, Choosing objectives in over-subscription planning, in: Proceedings 14th International Conference on Automated Planning and Scheduling (ICAPS-04), Whistler, Canada, 2004
[47] Wilcoxon, F.; Wilcox, R.A., Some rapid approximate statistical procedures, (1964), Lederle Laboratories Pearl River, New York, USA
[48] M. Williamson, S. Hanks, Optimal planning with a goal-directed utility model, in: Proceedings 2nd International Conference on Artificial Intelligence Planning and Scheduling (AIPS-94), Chicago, IL, USA, 1994, pp. 176-181
[49] S. Wolfman, D. Weld, The LPSAT system and its applications to resource planning, in: Proceedings 16th International Joint Conference on Artificial Intelligence (IJCAI-99), Stockholm, Sweden, 1999
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.