Identifying and Exploiting Features for Effective Plan Retrieval in Case-Based Planning

• Autorzy: Vallati M. , Serina I. , Saetti A. , Gerevini A. E.

Identyfikatory

DOI

10.3233/FI-2016-1447

• Konferencja: Experimental Evaluation of Algorithms for Solving Problems with Combinatorial Explosion (22; 22.09.2015; Ferrara; Italy)
• Języki publikacji: EN

Abstrakty

EN

Case-based planning can fruitfully exploit knowledge gained by solving a large number of problems, storing the corresponding solutions in a plan library and reusing them for solving similar planning problems in the future. Case-based planning is very effective when similar reuse candidates can be efficiently and effectively chosen. In this paper, we study an innovative technique based on planning problem features for efficiently retrieving solved planning problems (and relative plans) from large plan libraries. A problem feature is a characteristic –usually provided under the form of a number– of the instance that can be automatically derived from the problem specification, domain and search space analyses, or different problem encodings. Given a planning problem to solve, its features are extracted and compared to those of problems stored in the case base, in order to identify most similar problems. Since the use of existing planning features is not always able to effectively distinguish between problems within the same planning domain, we introduce a large number of new features. An experimental analysis in this paper investigates the best set of features to be exploited for retrieving plans in case-based planning, and shows that our feature-based retrieval approach can significantly improve the performance of a state-of-the-art case-based planning system.

Słowa kluczowe

EN

automated planning; case-based planning; planning features

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2016
• Tom: Vol. 149, nr 1/2
• Strony: 209--240
• Opis fizyczny: Bibliogr. 56 poz., rys., tab., wykr.

Twórcy

autor

Vallati M.

• School of Computing and Engineering, University of Huddersfield, Huddersfield, United Kingdom

autor

Serina I.

• Dipartimento d’Ingegneria dell’Informazione, Universitá degli Studi di Brescia, Brescia, Italy

autor

Saetti A.

• Dipartimento d’Ingegneria dell’Informazione, Universitá degli Studi di Brescia, Brescia, Italy

autor

Gerevini A. E.

• Dipartimento d’Ingegneria dell’Informazione, Universitá degli Studi di Brescia, Brescia, Italy

Bibliografia

• [1] Ghallab M, Nau D, Traverso P. Automated Planning: Theory & Practice. Morgan Kaufmann Publishers; 2004.
• [2] Borrajo D, Roubíkova A, Serina I. Progress in Case-Based Planning. ACM Computing Surveys (CSUR). 2015;47(2):35. doi:10.1145/2674024.
• [3] Spalazzi L. A Survey on Case-Based Planning. Artificial Intelligence Review. 2001;16(1):3-36. doi:10.1023/A:1011081305027.
• [4] Gerevini A, Saetti A, Serina I. Case-based Planning for Problems with Real-valued Fluents: Kernel Functions for Effective Plan Retrieval. In: ECAI; 2012. p. 348-353. doi:10.3233/978-1-61499-098-7-348.
• [5] Nebel B, Koehler J. Plan reuse versus plan generation: A complexity-theoretic perspective. Artificial Intelligence- Special Issue on Planning and Scheduling. 1995;76(1-2):427-454. doi:10.1016/0004-3702(94)00082-C.
• [6] Hanks S, Weld DS. A Domain-Independent Algorithm for Plan Adaptation. Journal of Artificial Intelligence Research. 1995;2(1):319-360. Available from: http://dl.acm.org/citation.cfm?id=1622826.1622836.
• [7] Kambhampati S, Hendler JA. A Validation-Structure-Based Theory of Plan Modification and Reuse. Artificial Intelligence. 1992;55:193-258. doi:10.1016/0004-3702(92)90056-4.
• [8] Köhler J. Planning from Second Principles. Artificial Intelligence. 1996;87(1-2):145-186. doi:10.1016/0004-3702(95)00113-1.
• [9] Bonisoli A, Gerevini AE, Saetti A, Serina I. Effective plan retrieval in case-based planning for metric-temporal problems. Journal of Experimental & Theoretical Artificial Intelligence. 2015;27(5):603-647. Available from: http://dx.doi.org/10.1080/0952813X.2014.993506. doi:10.1080/0952813X.2014.993506.
• [10] de la Rosa T, García-Olaya A, Borrajo D. A Case-Based Approach to Heuristic Planning. Applied Intelligence. 2013;39(1):184-201. doi:10.1007/s10489-012-0404-6.
• [11] Serina I. Kernel functions for case-based planning. Artificial Intelligence. 2010;174(16-17):1369-1406. doi:10.1016/j.artint.2010.07.007.
• [12] Tonidandel F, Rillo M. The FAR-OFF System: A Heuristic Search Case-Based Planning. In: Proc. of AIPS. AAAI Press; 2002. p. 302-311.
• [13] Veloso MM. Planning and Learning by Analogical Reasoning. vol. 886 of LNCS. Springer; 1994. ISBN:978-3-540-58811-5.
• [14] Raymond JW, Gardiner EJ, Willett P. RASCAL: Calculation of Graph Similarity using Maximum Common Edge Subgraphs. The Computer Journal. 2002 June;45(6):631-644. Available from: http://dx.doi.org/10.1093/comjnl/45.6.631. doi:10.1093/comjnl/45.6.631.
• [15] Ruskey F, Cohen R, Eades P, Scott A. Alley CATs in search of good homes. Twenty-fifth Southeastern Conference on Combinatorics, Graph Theory and Computing. 1994;102:97-110.
• [16] Cenamor I, de la Rosa T, Fernández F. Mining IPC-2011 Results. In: Proceedings of the 3rd workshop on the International Planning Competition; 2012.
• [17] Cenamor I, de la Rosa T, Fernández F. Learning Predictive Models to Configure Planning Portfolios. In: Proceedings of the 4th workshop on Planning and Learning (ICAPS-PAL 2013); 2013. p. 14-22.
• [18] Fawcett C, Vallati M, Hutter F, Hoffmann J, Hoos HH, Leyton-Brown K. Improved Features for Runtime Prediction of Domain-Independent Planners. In: Proceedings of the Twenty-Fourth International Conference on Automated Planning and Scheduling, (ICAPS-14); 2014. p. 355-359.
• [19] Howe A, Dahlman E, Hansen C, Von Mayrhauser A, Scheetz M. Exploiting Competitive Planner Performance. In: Proceedings of the 5th European Conference on Planning (ECP-99); 1999. p. 62-72. Available from: http://dl.acm.org/citation.cfm?id=647868.737100.
• [20] Roberts M, Howe AE, Wilson B, desJardins M. What Makes Planners Predictable? In: Proceedings of the 18th International Conference on Automated Planning and Scheduling (ICAPS-08); 2008. p. 288-295.
• [21] Roberts M, Howe A. Learning from planner performance. Artificial Intelligence. 2009;173(5-6):536-561. doi:10.1016/j.artint.2008.11.009.
• [22] Hutter F, Xu L, Hoos HH, Leyton-Brown K. Algorithm runtime prediction: Methods & evaluation. Artificial Intelligence. 2014;206:79-111. Available from: http://dx.doi.org/10.1016/j.artint.2013. 10.003.
• [23] Gerevini A, Saetti A, Vallati M. Exploiting Macro-actions and Predicting Plan Length in Planning as Satisfiability. In: Proceedings of the 12th International Conference of the Italian Association for Artificial Intelligence (AI*IA-11); 2011. p. 189-200. doi:10.1007/978-3-642-23954-0_19.
• [24] Vallati M, Serina I, Saetti A, Gerevini AE. Identifying and Exploiting Features for Effective Plan Retrieval in Case-Based Planning. In: Proceedings of the Twenty-Fifth International Conference on Automated Planning and Scheduling, ICAPS; 2015. p. 239-243. ISBN: 9781577357315.
• [25] Ghallab M, Howe A, Knoblock C, McDermott D, Ram A, Veloso M, et al. PDDL-the Planning Domain Definition Language. Yale Center for Computational Vision and Control; 1998. CVC TR-98-003/DCSTR-1165.
• [26] Fox M, Long D. PDDL2.1: An Extension to PDDL for Expressing Temporal Planning Domains. Journal of Artificial Intelligence Research. 2003;20(1):61-124. Available from: http://dl.acm.org/citation. cfm?id=1622452.1622454.
• [27] Gerevini AE, Haslum P, Long D, Saetti A, Dimopoulos Y. Deterministic Planning in the Fifth Int. Planning Competition: PDDL3 and Experimental Evaluation of the Planners. Artificial Intelligence. 2009;173(5):619-668.
• [28] Fikes RE, Nilsson NJ. STRIPS: A New Approach to the Application of Theorem Proving to Problem Solving. Artificial Intelligence. 1971;2(3/4):189-208.
• [29] Bylander T. The Computational Complexity of Propositional STRIPS Planning. Artificial Intelligence. 1994;69(1-2):165-204. doi:10.1016/0004-3702(94)90081-7.
• [30] Gentner D. The Mechanisms of Analogical Learning. In: Buchanan BG, Wilkins DC, editors. Readings in Knowledge Acquisition and Learning: Automating the Construction and Improvement of Expert Systems. San Mateo, CA: Kaufmann; 1993. p. 673-694. ISBN: 1-55860-163-5.
• [31] Ross BH. Some Psychological Results on Case-Based Reasoning. In: Proc. of a Workshop on Case-Based Reasoning. Pensacola Beach, FL; 1989. p. 144-147.
• [32] Vosniadou S, Ortony A, editors. Similarity and analogical reasoning. New York, NY, USA: Cambridge University Press; 1989. ISBN: 0-521-38935-6.
• [33] Liberatore P. On the complexity of case-based planning. Journal of Experimental & Theoretical Artificial Intelligence. 2005;17(3):283-295. doi:10.1080/09528130500283717.
• [34] Bäckström C, Nebel B. Complexity Results for SAS+Planning. Computational Intelligence. 1995;11:625-656.
• [35] Hoffmann J. Where Ignoring Delete Lists Works, Part II: Causal Graphs. In: Proceedings of the 21st International Conference on Automated Planning and Scheduling (ICAPS-11); 2011. p. 98-105. Available from: https://hal.inria.fr/inria-00578653.
• [36] Hoffmann J. Analyzing Search Topology Without Running Any Search: On the Connection Between Causal Graphs and h+. Journal of Artificial Intelligence Research. 2011;41:155-229. doi:10.1613/jair.3276.
• [37] Hansen P. Upper bounds for the stability number of a graph. Rev Roumaine Math Pures Appl. 1979; 24:1195-1199.
• [38] Liu RY. An upper bound on the chromatic number of a graph. J Xinjiang Univ Natur Sci. 1989;6:24-27.
• [39] Papadopoulos AN, Manolopoulos Y. Structure-based similarity search with graph histograms. In: In Proceedings of the 10th International Workshop on Database & Expert Systems Applications. IEEE Computer Society Press; 1999. p. 174-178. doi:10.1109/DEXA.1999.795162.
• [40] Johnson M. Relating metrics, lines and variables defined on graphs to problems in medicinal chemistry. New York, NY, USA: John Wiley & Sons, Inc.; 1985. ISBN: 0-471-81635-3.
• [41] Cerutti F, Giacomin M, Vallati M. Algorithm selection for preferred extensions enumeration. Proc of the 5th Int Conf on Computational Models of Argument (COMMA 2014). 2014; p. 221-232. doi:10.3233/978-1-61499-436-7-221.
• [42] Bollobás B. Modern graph theory. vol. 184. Springer Science & Business Media; 1998. ISBN: 978-0-387-98488-9.
• [43] Bacchus F, Kabanza F. Using temporal logics to express search control knowledge for planning. Artificial Intelligence. 2000;116(1):123-191. doi:10.1016/S0004-3702(99)00071-5.
• [44] Gerevini A, Roubícková A, Saetti A, Serina I. On the Plan-Library Maintenance Problem in a Case-Based Planner. In: Case-Based Reasoning Research and Development-21st International Conference, (ICCBR-13); 2013. p. 119-133. doi:10.1007/978-3-642-39056-2_9.
• [45] Richter S, Westphal M, Helmert M. LAMA 2008 and 2011. In: Booklet of the 7th International Planning Competition; 2011.
• [46] Gerevini A, Saetti A, Serina I. An Approach to Temporal Planning and Scheduling in Domains with Predictable Exogenous Events. Journal Artificial Intelligence Research (JAIR). 2006;25(1):187-231. Available from: http://dl.acm.org/citation.cfm?id=1622543.1622549.
• [47] Hoffmann J. The Metric-FF Planning System: Translating ”Ignoring Delete Lists” to Numeric State Variables. Journal Artificial Intelligence Research (JAIR). 2003;20(1):291-341. Available from: http://dl.acm.org/citation.cfm?id=1622452.1622463.
• [48] Hsu CW, Wah BW. The SGPlan Planning System in IPC-6. In: The 6th International Planning Competition (IPC-6); 2008.
• [49] Nguyen TA, Do MB, Gerevini A, Serina I, Srivastava B, Kambhampati S. Generating diverse plans to handle unknown and partially known user preferences. Artificial Intelligence. 2012;190:1-31. doi:10.1016/j.artint.2012.05.005.
• [50] Fox M, Gerevini A, Long D, Serina I. Plan Stability: Replanning versus Plan Repair. In: Proceedings of the International Conference on Automated Planning and Scheduling (ICAPS-06). vol. 6; 2006. p. 212-221.
• [51] Tonidandel F, Rillo M. On the Use of the ADG Similarity in Case-Based Planning Systems. In: Proc. of ENIA03. Anais do XXIII Congresso da Sociedade Brasileira de Computacao; 2003. Available from: http://fei.edu.br/~flaviot/pub_arquivos/ENIA03.pdf.
• [52] Malitsky Y, Mehta D, O’Sullivan B. Evolving Instance Specific Algorithm Configuration. In: Proceedings of the Sixth Annual Symposium on Combinatorial Search, (SOCS-13); 2013. p. 132-140.
• [53] Seipp J, Sievers S, Helmert M, Hutter F. Automatic Configuration of Sequential Planning Portfolios. In: Proceedings of the Twenty-fourth National Conference on Artificial Intelligence (AAAI-15); 2015. p. 3364-3370. Available from: http://dl.acm.org/citation.cfm?id=2888116.2888184.
• [54] Seipp J, Braun M, Garimort J, Helmert M. Learning Portfolios of Automatically Tuned Planners. In: Proceedings of the Twenty-Second International Conference on Automated Planning and Scheduling, (ICAPS-12); 2012. p. 368-372.
• [55] Hutter F, Hoos HH, Leyton-Brown K. Sequential Model-Based Optimization for General Algorithm Configuration. In: Proceedings of the 5th Learning and Intelligent Optimization Conference (LION-11); 2011. p. 507-523. doi:10.1007/978-3-642-25566-3_40.
• [56] Sánchez-Ruiz AA, Ontañón S. Least Common Subsumer Trees for Plan Retrieval. In: Lamontagne L, Plaza E, editors. Case-Based Reasoning Research and Development-22nd International Conference, ICCBR 2014, Cork, Ireland, September 29, 2014-October 1, 2014. Proceedings. vol. 8765 of Lecture Notes in Computer Science. Springer; 2014. p. 405-419. doi:10.1007/978-3-319-11209-1_29.

Uwagi

Opracowanie ze środków MNiSW w ramach umowy 812/P-DUN/2016 na działalność upowszechniającą naukę (zadania 2017).