Model-lite planning: case-based vs. model-based approaches. (English) Zbl 1419.68102
Summary: There is increasing awareness in the planning community that depending on complete models impedes the applicability of planning technology in many real world domains where the burden of specifying complete domain models is too high. In this paper, we consider the problem of generating robust and accurate plans, when the agent only has access to incomplete domain models, supplanted by a set of successful plan cases. We will develop two classes of approaches – one case-based and the other model-based. \(\mathsf{ML-BCP}\) is a case-based approach that leverages the incomplete model and the plan cases to solve a new problem directly by affecting case-level transfer. is a model-based approach that uses the incomplete model and the plan cases to first learn a more complete model. This model contains both primitive actions as well as macro-operators that are derived from the plan cases. The learned model is then used in conjunction with an off-the-shelf planner to solve new problems. We present a comprehensive evaluation of the two approaches, both to characterize their relative tradeoffs, and to quantify their advances over existing approaches.
MSC:
| 68T20 | Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) |
| 68T05 | Learning and adaptive systems in artificial intelligence |
References:
| [1] | Alterman, R., An adaptive planner, (Proceedings of AAAI (1986)), 65-71 |
| [2] | Amir, E., Learning partially observable deterministic action models, (Proceedings of IJCAI (2005)), 1433-1439 |
| [3] | Bacchus, F.; Yang, Q., The downward refinement property, (Proceedings of the Twelfth International Joint Conference on Artificial Intelligence (1991)), 286-292 · Zbl 0747.68063 |
| [4] | Bergmann, R.; Wilke, W., Building and refining abstract planning cases by change of representation language, J. Artif. Intell. Res., 3, 53-118 (1995) |
| [5] | Bertoli, P.; Pistore, M.; Traverso, P., Automated composition of web services via planning in asynchronous domains, Artif. Intell., 174, 3-4, 316-361 (2010) |
| [6] | Blythe, J.; Deelman, E.; Gil, Y., Automatically composedworkflows for grid environments, IEEE Intell. Syst., 19, 4, 16-23 (2004) |
| [7] | Bonet, B.; Geffner, H., Planning with incomplete information as heuristic search in belief space, (Proceedings of the Fifth International Conference on Artificial Intelligence Planning Systems. Proceedings of the Fifth International Conference on Artificial Intelligence Planning Systems, Breckenridge, CO, USA, April 14-17, 2000 (2000)), 52-61 |
| [8] | Borrajo, D.; Roubíčková, A.; Serina, I., Progress in case-based planning, ACM Comput. Surv., 47, 2, 35:1-35:39 (Jan. 2015) |
| [9] | Botea, A.; Enzenberger, M.; Muller, M.; Schaeffer, J., Macro-ff: improving AI planning with automatically learned macro-operators, J. Artif. Intell. Res., 24, 581-621 (2005) · Zbl 1080.68657 |
| [10] | Bryce, D.; Weber, C., Planning and acting in incomplete domains, (Proceedings of ICAPS (2011)) |
| [11] | Carbonell, J. G., Learning by analogy: formulating and generalizing plans from past experience, (Michalski, R. S.; Carbonell, J. G.; Mitchell, T. M., Machine Learning: An Artificial Intelligence Approach (1984), Springer: Springer Berlin, Heidelberg), 137-161 |
| [12] | Coles, A.; Smith, A., Marvin: a heuristic search planner with online macro-action learning, J. Artif. Intell. Res., 28, 119-156 (2007) · Zbl 1182.68231 |
| [13] | Cresswell, S.; McCluskey, T. L.; West, M. M., Acquisition of object-centred domain models from planning examples, (Proceedings of the Nineteenth International Conference on Automated Planning and Scheduling. Proceedings of the Nineteenth International Conference on Automated Planning and Scheduling, ICAPS’09 (2009)) |
| [14] | Etzioni, O.; Hanks, S.; Weld, D. S.; Draper, D.; Lesh, N.; Williamson, M., An approach to planning with incomplete information, (Proceedings of the 3rd International Conference on Principles of Knowledge Representation and Reasoning. Proceedings of the 3rd International Conference on Principles of Knowledge Representation and Reasoning, KR’92, Cambridge, MA, October 25-29, 1992 (1992)), 115-125 |
| [15] | Fawcett, C.; Vallati, M.; Hutter, F.; Hoffmann, J.; Hoos, H. H.; Leyton-Brown, K., Improved features for runtime prediction of domain-independent planners, (Proceedings of the Twenty-Fourth International Conference on Automated Planning and Scheduling. Proceedings of the Twenty-Fourth International Conference on Automated Planning and Scheduling, ICAPS 2014, Portsmouth, New Hampshire, USA, June 21-26, 2014 (2014)) |
| [16] | Fikes, R. E.; Hart, P. E.; Niisson, N. J., Learning and executing generalized robot plans, Artif. Intell., 3, 251-288 (1972) |
| [17] | Gerevini, A.; Serina, I., Fast plan adaptation through planning graphs: local and systematic search techniques, (Proceedings of the Fifth International Conference on Artificial Intelligence Planning Systems. Proceedings of the Fifth International Conference on Artificial Intelligence Planning Systems, Breckenridge, CO, USA, April 14-17, 2000 (2000)), 112-121 |
| [18] | Gregory, P.; Cresswell, S., Domain model acquisition in the presence of static relations in the LOP system, (Proceedings of the Twenty-Fifth International Conference on Automated Planning and Scheduling. Proceedings of the Twenty-Fifth International Conference on Automated Planning and Scheduling, ICAPS 2015, Jerusalem, Israel, June 7-11, 2015 (2015)), 97-105 |
| [19] | Gupta, N.; Nau, D. S., On the complexity of blocks-world planning, Artif. Intell., 56, 2-3, 223-254 (1992) · Zbl 0785.68046 |
| [20] | Hammond, K. J., Case-Based Planning: Viewing Planning as a Memory Task (1989), Academic Press: Academic Press San Diego, CA · Zbl 0702.68014 |
| [21] | Hanks, S.; Weld, D. S., A domain-independent algorithm for plan adaptation, J. Artif. Intell. Res., 2, 319-360 (1995) |
| [22] | He, R.; Brunskill, E.; Brunskill, E., Puma: planning under uncertainty with macro-actions, (Proceedings of AAAI (2010)), 1089-1095 |
| [23] | Hoffmann, J.; Bertoli, P.; Pistore, M., Web service composition as planning, revisited: in between background theories and initial state uncertainty, (Proceedings of AAAI (2007)) |
| [24] | Hoffmann, J.; Nebel, B., The FF planning system: fast plan generation through heuristic search, J. Artif. Intell. Res., 14, 253-302 (2001) · Zbl 0970.68044 |
| [25] | Hoffmann, J.; Nebel, B., What makes the difference between HSP and FF?, (Proceedings IJCAI-01 Workshop on Empirical Methods in Artificial Intelligence (2001)) · Zbl 0970.68044 |
| [26] | Iba, G. A., A heuristic approach to the discovery of macro-operators, Mach. Learn., 3, 285-317 (1989) |
| [27] | Ihrig, L. H.; Kambhampati, S., Derivation replay for partial-order planning, (Proceedings of the 12th National Conference on Artificial Intelligence. Proceedings of the 12th National Conference on Artificial Intelligence, Seattle, WA, USA, July 31-August 4, 1994, vol. 2 (1994)), 992-997 |
| [28] | Ihrig, L. H.; Kambhampati, S., Storing and indexing plan derivations through explanation-based analysis of retrieval failures, J. Artif. Intell. Res., 7, 161-198 (1997) |
| [29] | Kambhampati, S., Model-lite planning for the web age masses: the challenges of planning with incomplete and evolving domain theories, (Proceedings of AAAI (2007)) |
| [30] | Kambhampati, S.; Hendler, J. A., A validation-structure-based theory of plan modification and reuse, Artif. Intell., 55, 193-258 (1992) |
| [31] | Korf, R. E., Macro-operators: a weak method for learning, Artif. Intell., 26, 35-77 (1985) · Zbl 0562.68071 |
| [32] | Li, C. M.; Manya, F.; Planes, J., New inference rules for Max-SAT, J. Artif. Intell. Res., 30, 321-359 (October 2007) · Zbl 1182.68254 |
| [33] | Melis, E.; Whittle, J., Internal analogy in theorem proving, (Automated Deduction - CADE-13, 13th International Conference on Automated Deduction, Proceedings. Automated Deduction - CADE-13, 13th International Conference on Automated Deduction, Proceedings, New Brunswick, NJ, USA, July 30-August 3, 1996 (1996)), 92-105 · Zbl 1412.68245 |
| [34] | Morwood, D.; Bryce, D., Evaluating temporal plans in incomplete domains, (Proceedings of the Twenty-Sixth AAAI Conference on Artificial Intelligence. Proceedings of the Twenty-Sixth AAAI Conference on Artificial Intelligence, July 22-26, 2012, Toronto, Ontario, Canada (2012)) |
| [35] | Muñoz-Avila, H., Case-base maintenance by integrating case-index revision and case-retention policies in a derivational replay framework, Comput. Intell., 17, 2, 280-294 (2001) |
| [36] | Muñoz-Avila, H.; Aha, D. W.; Breslow, L.; Nau, D. S., HICAP: an interactive case-based planning architecture and its application to noncombatant evacuation operations, (Proceedings of the Sixteenth National Conference on Artificial Intelligence and Eleventh Conference on Innovative Applications of Artificial Intelligence. Proceedings of the Sixteenth National Conference on Artificial Intelligence and Eleventh Conference on Innovative Applications of Artificial Intelligence, July 18-22, 1999, Orlando, Florida, USA (1999)), 870-875 |
| [37] | Muñoz-Avila, H.; Cox, M. T., Case-based plan adaptation: an analysis and review, IEEE Intell. Syst., 23, 4, 75-81 (2008) |
| [38] | Newton, M. H.; Levine, J.; Fox, M.; Long, D., Learning macro-actions for arbitrary planners and domains, (Proceedings of ICAPS (2007)), 256-263 |
| [39] | Nguyen, T. A.; Kambhampati, S.; Do, M. B., Assessing and generating robust plans with partial domain models, (ICAPS Workshop on Planning Under Uncertainty (2010)) |
| [40] | Oglietti, M., Understanding planning with incomplete information and sensing, Artif. Intell., 164, 1-2, 171-208 (2005) · Zbl 1132.68707 |
| [41] | Olawsky, D.; Gini, M., Deferred planning and sensor use, (DARPA Workshop on Innovative Approaches to Planning, Scheduling, and Control (1990), Morgan Kaufmann) |
| [42] | Pei, J.; Han, J.; Mortazavi-Asl, B.; Wang, J.; Pinto, H.; Chen, Q.; Dayal, U.; Hsu, M.-C., Mining sequential patterns by pattern-growth: the prefixspan approach, IEEE Trans. Knowl. Data Eng., 16, 11, 1424-1440 (2004) |
| [43] | Petrick, R. P.A.; Bacchus, F., A knowledge-based approach to planning with incomplete information and sensing, (Proceedings of the Sixth International Conference on Artificial Intelligence Planning Systems. Proceedings of the Sixth International Conference on Artificial Intelligence Planning Systems, April 23-27, 2002, Toulouse, France (2002)), 212-222 |
| [44] | Serina, I., Kernel functions for case-based planning, Artif. Intell., 174, 16-17, 1369-1406 (2010) · Zbl 1210.68104 |
| [45] | Spalazzi, L., A survey on case-based planning, Artif. Intell. Rev., 16, 1, 3-36 (2001) · Zbl 0985.68062 |
| [46] | Sutton, R. S.; Barto, A. G., Reinforcement Learning: An Introduction (1998), MIT Press: MIT Press Cambridge, Massachusetts |
| [47] | Torreño, A.; Onaindia, E.; Sapena, O., An approach to multi-agent planning with incomplete information (2015), CoRR |
| [48] | Vallati, M.; Serina, I.; Saetti, A.; Gerevini, A. E., Identifying and exploiting features for effective plan retrieval in case-based planning, (Proceedings of ICAPS-15 (2015)) |
| [49] | van der Krogt, R.; de Weerdt, M., Plan repair as an extension of planning, (Proceedings of the Fifteenth International Conference on Automated Planning and Scheduling. Proceedings of the Fifteenth International Conference on Automated Planning and Scheduling, ICAPS 2005, June 5-10, 2005, Monterey, California, USA (2005)), 161-170 |
| [50] | Veloso, M.; Carbonell, J.; Perez, A.; Borrajo, D.; Fink, E.; Blythe, J., Integrating planning and learning: the prodigy architecture, J. Exp. Theor. Artif. Intell., 7, 1 (1995) · Zbl 0939.68830 |
| [51] | Walsh, T. J.; Littman, M. L., Efficient learning of action schemas and web-service descriptions, (Proceedings of the Twenty-Third AAAI Conference on Artificial Intelligence. Proceedings of the Twenty-Third AAAI Conference on Artificial Intelligence, AAAI-08 (2008)), 714-719 |
| [52] | Yang, Q.; Wu, K.; Jiang, Y., Learning action models from plan examples using weighted MAX-SAT, Artif. Intell., 171, 107-143 (February 2007) · Zbl 1168.68555 |
| [53] | Zaki, M. J., Spade: an efficient algorithm for mining frequent sequences, Mach. Learn., 42, 31-60 (2001) · Zbl 0970.68052 |
| [54] | Zettlemoyer, L. S.; Pasula, H. M.; Kaelbling, L. P., Learning planning rules in noisy stochastic worlds, (Proceedings of AAAI (2005)) · Zbl 1182.68181 |
| [55] | Zhuo, H. H., Crowdsourced action-model acquisition for planning, (Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence. Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence, January 25-30, 2015, Austin, Texas, USA (2015)), 3439-3446 |
| [56] | Zhuo, H. H.; Muñoz-Avila, H.; Yang, Q., Learning hierarchical task network domains from partially observed plan traces, Artif. Intell., 212, 134-157 (2014) · Zbl 1405.68333 |
| [57] | Zhuo, H. H.; Nguyen, T. A.; Kambhampati, S., Model-lite case-based planning, (Proceedings of the Twenty-Seventh AAAI Conference on Artificial Intelligence. Proceedings of the Twenty-Seventh AAAI Conference on Artificial Intelligence, July 14-18, 2013, Bellevue, Washington, USA (2013)) |
| [58] | Zhuo, H. H.; Nguyen, T. A.; Kambhampati, S., Refining incomplete planning domain models through plan traces, (Proceedings of the 23rd International Joint Conference on Artificial Intelligence. Proceedings of the 23rd International Joint Conference on Artificial Intelligence, IJCAI 2013, Beijing, China, August 3-9, 2013 (2013)), 2451-2458 |
| [59] | Zhuo, H. H.; Yang, Q., Action-model acquisition for planning via transfer learning, Artif. Intell., 212, 80-103 (2014) · Zbl 1308.68108 |
| [60] | Zhuo, H. H.; Yang, Q.; Hu, D. H.; Li, L., Learning complex action models with quantifiers and logical implications, Artif. Intell., 174, 18, 1540-1569 (2010) |
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.
