An Empirical Analysis of Some Heuristic Features for Planning through Local Search and Action Graphs

• Autorzy: Gerevini A. , Saetti A. , Serina I.
• Języki publikacji: EN

Abstrakty

EN

Planning through local search and action graphs is a powerful approach to fully-automated planning which is implemented in the well-known LPG planner. The approach is based on a stochastic local search procedure exploring a space of partial plans and several heuristic features with different possible options. In this paper, we experimentally analyze the most important of them, with the goal of understanding and evaluating their impact on the performance of LPG, and of identifying default settings that work well on a large class of problems. In particular, we analyze several heuristic techniques for (a) evaluating the search neighborhood, (b) defining/restricting the search neighborhood, (c) selecting the next plan flaw to handle, (d) setting the "noise" parameter randomizing the search, and (e) computing reachability information that can be exploited by the heuristic functions used to evaluate the neighborhood elements. Some of these techniques were introduced in previous work on LPG, while others are new. Additional experimental results indicate that the current version of LPG using the identified best heuristic techniques as the default settings is competitive with the winner of the last (2008) International Planning Competition.

Słowa kluczowe

EN

automated planning; domain-independent planning; efficient planning; experimental evaluation of planning techniques

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2011
• Tom: Vol. 107, nr 2/3
• Strony: 167--197
• Opis fizyczny: Bibliogr. 33 poz., wykr.

Twórcy

autor

Gerevini A.

autor

Saetti A.

autor

Serina I.

• Dipartimento di Ingegneria dell’Informazione, Universita degli Studi di Brescia Via Branze 38, I-25123 Brescia, Italy,

Bibliografia

• [1] A. Blum and M.L. Furst. Fast planning through planning graph analysis. Artificial Intelligence, 90:281-300, 1997.
• [2] M.B. Do and S. Kambhampati. Sapa: A domain-independent heuristic metric temporal planner. In Proceedings of the Sixth European Conference on Planning (ECP-01), 2001.
• [3] M. Friedman. The use of ranks to avoid the assumption of normality implicit in the analysis of variance. Journal of the American Statistical Association, 32:675-701, 1937.
• [4] A. Gerevini, U. Kuter, S. Nau, D., Saetti A., and N. Waisbrot. Combining domain-independent planning and HTN planning: The Duet planner. In Proceedings of the Eighteenth European Conference on Artificial Intelligence (ECAI-08), 2008.
• [5] A. Gerevini, A. Saetti, and I. Serina. Planning through stochastic local search and temporal action graphs in LPG. Journal of Artificial Intelligence Research (JAIR), 20:239-290, 2003.
• [6] A. Gerevini, A. Saetti, and I. Serina. An empirical analysis of some heuristic features for local search in LPG. In Proceedings of the Fourteenth International Conference on Automated Planning and Scheduling (ICAPS-04), 2004.
• [7] A. Gerevini, A. Saetti, and I. Serina. An approach to temporal planning and scheduling in domains with predictable exogenous events. Journal of Artificial Intelligence Research (JAIR), 25:187-231, 2006.
• [8] A. Gerevini, A. Saetti, and I. Serina. An approach to efficient planning with numerical fluents and multicriteria plan quality. Artificial Intelligence, 172(8-9):899-944, 2008.
• [9] A. Gerevini, A. Saetti, and I. Serina. An empirical analysis of some heuristic features for planning with LPG. Technical Report R.T. 2010-01-58, DII, Universita degli Studi di Brescia, Dipartimento di Ingegneria dell'Informazione, Brescia, Italy, 2010.
• [10] A. Gerevini, A. Saetti, and M. Vallati. An automatically configurable portfolio-based planner with macroactions: PbP. In Proceedings of the Nineteenth International Conference on Automated Planning and Scheduling (ICAPS-09), 2009.
• [11] A. Gerevini and I. Serina. Fast planning through greedy action graphs. In Proceedings of the Sixteenth National Conference on Artificial Intelligence (AAAI-99), 1999.
• [12] A. Gerevini and I. Serina. LPG: A planner based on local search for planning graphs with action costs. In Proceedings of the Sixth International Conference on Artificial Intelligence Planning and Scheduling (AIPS-02), 2002.
• [13] E. Gerevini, A., P. Haslum, D. Long, A. Saetti, and Y. Dimopoulos. Deterministic planning in the fifth international planning competition: PDDL3 and experimental evaluation of the planners. Artificial Intelligence, 173(5-6):619-668, 2009.
• [14] P. Hansen and N.Mladenovic. Variable neighborhood search: Principles and applications. European Journal of Operational Research, 130(3):449-467, 2001.
• [15] M. Helmert, M. Do, and I. Refanidis. Deterministic part of the 6th international planning competition. In http://ipc.informatik.uni-freiburg.de/, 2010.
• [16] J. Hoffmann and S. Edelkamp. The deterministic part of IPC-4: An overview. Journal of Artificial Intelligence Research (JAIR), 24:519-579, 2005.
• [17] J. Hoffmann, S. Edelkamp, S. Thi´ebaux, R. Englert, F. Liporace, and S. Trüg. Engineering benchmarks for planning: the domains used in the deterministic part of IPC-4. Journal of Artificial Intelligence Research, 26:453-541, 2006.
• [18] J. Hoffmann and B. Nebel. The FF planning system: Fast plan generation through heuristic search. Journal of Artificial Intelligence Research (JAIR), 14:253-302, 2001.
• [19] S. Jimẽnez, F. Fernãndez, and D. Borrajo. The PELA architecture: integrating planning and learning to improve execution. In Proceedings of the Twenty-Third National Conference on Artificial Intelligence (AAAI-08), 2008.
• [20] A. Kolobov, Mausam, and S. Weld, D. Determinize, solve, and generalize: Classical planning for MDP heuristics. In ICAPS-09 Workshop on Heuristics for Domain-independent Planning, 2009.
• [21] D. Long and M. Fox. The 3rd international planning competition: Results and analysis. Journal of Artificial Intelligence Research (JAIR), 20:1-59, 2003.
• [22] O.J. Mengshoel. Understanding the role of noise in stochastic local search: Analysis and experiments. Artificial Intelligence, 172(8-9):955-990, 2008.
• [23] L.Morales, L. Castillo, J. Fernandez-Olivares, and A. Gonzalez-Ferrer. Automatic generation of user adapted learning designs: An AI-planning proposal. In Proceedings of the Fifth International Conference on Adaptive Hypermedia and Adaptive Web-Based Systems (AH-08), 2008.
• [24] A. Nguyen, T., B. Do, M., D. Kambhampati, and B. Srivasta. Planning with partial preference models. In Twenty-first International Joint Conference on Artificial Intelligence (IJCAI-09), 2009.
• [25] J.S. Penberthy and D.S. Weld. UCPOP: A sound, complete, partial order planner for ADL. In Proceedings of the Third International Conference on Principles of Knowledge Representation and Reasoning (KR'92), 1992.
• [26] M.E. Pollack, D. Joslin, and M. Paolucci. Flaw selection strategies for partial-order planning. Journal of Artificial Intelligence Research (JAIR), 6:223-262, 1997.
• [27] S. Richter, M. Helmert, and M. Westphal. Landmarks revisited. In Proceedings of the Twenty-third National Conference on Artificial Intelligence (AAAI-08), 2008.
• [28] B. Selman, H.A. Kautz, and B. Cohen. Noise strategies for improving local search. In Proceedings of the Twelfth National Conference on Artificial Intelligence (AAAI-94), 1994.
• [29] S. Sidney and J. Castellan, N. Nonparametric Statistics for the Behavioral Sciences. McGraw-Hill, 1988.
• [30] N. Srivastava, A. Nguyen, T., A. Gerevini, S. Kambhampati, B. Do, M., and I. Serina. Domain independent approaches for finding diverse plans. In Proceedings of the Twentieth International Joint Conference on Artificial Intelligence (IJCAI-07), 2007.
• [31] D. Vrakas, O. Hatzi, D. Bassiliades, N.and Anagnostopoulos, and I. Vlahavas. A visual programming tool for designing planning problems for semantic web service composition. In Visual Languages for Interactive Computing: Definitions and Formalizations, 2008.
• [32] F. Wilcoxon and R. A.Wilcox. Some Rapid Approximate Statistical Procedures. Lederle Laboratories, Pearl River, New York, USA, 1964.
• [33] L. Xu, F. Hutter, H. Hoos H., and K. Leyton-Brown. Satzilla: Portfolio-based algorithm selection for SAT. Journal of Artificial Intelligence Research (JAIR), 32:565-606, 2008