HTN-like solutions for classical planning problems: an application to BDI agent systems. (English) Zbl 1411.68141
Summary: In this paper we explore the question of what characterises a desirable plan of action and how such a plan could be computed, in the context of systems that already possess a certain amount of hierarchical domain knowledge. In contrast to past work in this setting, which focuses on generating low-level plans, losing much of the domain knowledge inherent in such systems, we argue that plans ought to be HTN-like or abstract, i.e., re-use and respect the user-supplied know-how in the underlying domain. In doing so, we recognise an intrinsic tension between striving for abstract plans but ensuring that unnecessary actions, not linked to the specific goal to be achieved, are avoided. We explore this tension by characterising the set of “ideal” abstract plans that are non-redundant but maximally abstract, and then develop a more limited yet feasible account in which a given (arbitrary) abstract plan is “specialised” into one such non-redundant plan that is as abstract as possible. We present an algorithm that can compute such specialisations, and analyse the theoretical properties of our proposal.
MSC:
| 68T20 | Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) |
| 68T35 | Theory of languages and software systems (knowledge-based systems, expert systems, etc.) for artificial intelligence |
| 68T42 | Agent technology and artificial intelligence |
References:
| [1] | Alami, R.; Chatila, R.; Fleury, S.; Ghallab, M.; Ingrand, F., An architecture for autonomy, Int. J. Robot. Res., 17, 4, 315-337 (1998) |
| [2] | Alford, R.; Bercher, P.; Aha, D. W., Tight bounds for HTN planning with task insertion, (Proc. of the International Joint Conference on Artificial Intelligence (IJCAI) (2015)), 1502-1508 |
| [3] | Alford, R.; Shivashankar, V.; Roberts, M.; Frank, J.; Aha, D. W., Hierarchical planning: relating task and goal decomposition with task sharing, (Proc. of the International Joint Conference on Artificial Intelligence (IJCAI) (2016)), 3022-3029 |
| [4] | Alford, R. W.; Kuter, U.; Nau, D., Translating HTNs to PDDL: a small amount of domain knowledge can go a long way, (Proc. of the International Joint Conference on Artificial Intelligence (IJCAI) (2009)), 1629-1634 |
| [5] | Baier, J. A.; Fritz, C.; McIlraith, S. A., Exploiting procedural domain control knowledge in state-of-the-art planners, (Proc. of the International Conference on Automated Planning and Scheduling (ICAPS) (2007)), 26-33 |
| [6] | Benfield, S. S.; Hendrickson, J.; Galanti, D., Making a strong business case for multiagent technology, (Proc. of the International Conference on Autonomous Agents and Multi-Agent Systems (AAMAS) (2006)), 10-15 |
| [7] | Bordini, R. H.; Braubach, L.; Dastani, M.; Seghrouchni, A. E.F.; Gómez-Sanz, J. J.; Leite, J.; O’Hare, G.; Pokahr, A.; Ricci, A., A survey of programming languages and platforms for multi-agent systems, Informatica (Slovenia), 30, 1, 33-44 (2006) · Zbl 1111.68373 |
| [8] | Botea, A.; Enzenberger, M.; Müller, M.; Schaeffer, J., Macro-FF: improving AI planning with automatically learned macro-operators, J. Artificial Intelligence Res., 24, 581-621 (2005) · Zbl 1080.68657 |
| [9] | Buss, S. R., The boolean formula value problem is in ALOGTIME, (Proc. of the ACM Symposium on Theory of Computing (STOC) (1987)), 123-131 |
| [10] | Claßen, J.; Eyerich, P.; Lakemeyer, G.; Nebel, B., Towards an integration of Golog and planning, (Proc. of the International Joint Conference on Artificial Intelligence (IJCAI) (2007)), 1846-1851 |
| [11] | de Boer, F. S.; Hindriks, K. V.; van der Hoek, W.; Meyer, J. J., A verification framework for agent programming with declarative goals, J. Appl. Log., 5, 2, 277-302 (2007) · Zbl 1122.68078 |
| [12] | de Silva, L.; Padgham, L., A comparison of BDI based real-time reasoning and HTN based planning, (Proc. of the Australian Joint Conference on AI (AI) (2004)), 1167-1173 |
| [13] | Despouys, O.; Ingrand, F. F., Propice-plan: toward a unified framework for planning and execution, (Proc. of the European Conference on Planning (ECP) (1999)), 278-293 |
| [14] | Dix, J.; Muñoz-Avila, H.; Nau, D. S.; Zhang, L., IMPACTing SHOP: putting an AI planner into a multi-agent environment, Ann. Math. Artif. Intell., 37, 4, 381-407 (2003) · Zbl 1010.68171 |
| [15] | Dvorak, F.; Barták, R.; Bit-Monnot, A.; Ingrand, F.; Ghallab, M., Planning and acting with temporal and hierarchical decomposition models, (Proc. of the International Conference on Tools with Artificial Intelligence (ICTAI) (2014)), 115-121 |
| [16] | Erol, K.; Hendler, J.; Nau, D. S., HTN planning: complexity and expressivity, (Proc. of the National Conference on Artificial Intelligence (AAAI) (1994)), 1123-1128 |
| [17] | Erol, K.; Hendler, J.; Nau, D. S., Semantics for Hierarchical Task-Network Planning (1994), Institute for Advanced Computer Studies, University of Maryland: Institute for Advanced Computer Studies, University of Maryland College Park, MD, U.S.A., Tech. Rep. UMIACS-TR-94-31 |
| [18] | Erol, K.; Nau, D. S.; Subrahmanian, V. S., Complexity, decidability and undecidability results for domain-independent planning: a detailed analysis, Artificial Intelligence, 76, 1-2, 75-88 (1995) · Zbl 1013.68548 |
| [19] | Erol, K.; Hendler, J. A.; Nau, D. S., Complexity results for HTN planning, Ann. Math. Artif. Intell., 18, 1, 69-93 (1996) · Zbl 0891.68104 |
| [20] | Fikes, R. E.; Nilsson, N. J., STRIPS: a new approach to the application of theorem proving to problem solving, Artificial Intelligence, 2, 3-4, 189-208 (1971) · Zbl 0234.68036 |
| [21] | Fink, E.; Yang, Q., Formalizing plan justifications, (Proc. of the Conference of the Canadian Society for Computational Studies of Intelligence (1992)), 9-14 |
| [22] | Fox, M., Natural hierarchical planning using operator decomposition, (Proc. of the European Conference on Planning (ECP) (1997)), 195-207 |
| [23] | Fritz, C.; Baier, J. A.; McIlraith, S. A., ConGolog, Sin Trans: Compiling ConGolog into Basic Action Theories for planning and beyond, (Proc. of the International Conference on Principles of Knowledge Representation and Reasoning (KR) (2008)), 600-610 |
| [24] | Geier, T.; Bercher, P., On the decidability of HTN planning with task insertion, (Proc. of the International Joint Conference on Artificial Intelligence (IJCAI) (2011)), 1955-1961 |
| [25] | Georgeff, M. P.; Ingrand, F. F., Decision making in an embedded reasoning system, (Proc. of the International Joint Conference on Artificial Intelligence (IJCAI) (1989)), 972-978 · Zbl 0713.68054 |
| [26] | Ghallab, M.; Nau, D. S.; Traverso, P., Automated Planning: Theory and Practice (2004), Morgan Kaufmann Publishers Inc. · Zbl 1074.68613 |
| [27] | Kambhampati, S.; Mali, A. D.; Srivastava, B., Hybrid planning for partially hierarchical domains, (Proc. of the National Conference on Artificial Intelligence (AAAI) (1998)), 882-888 |
| [28] | Ljungberg, M.; Lucas, A., The OASIS air-traffic management system, (Proc. of the Pacific Rim International Conference on Artificial Intelligence (PRICAI) (1992)), 15-18 |
| [29] | Lloyd, J. W., Foundations of Logic Programming (1987), Springer-Verlag · Zbl 0547.68005 |
| [30] | Marthi, B.; Russell, S. J.; Wolfe, J. A., Angelic hierarchical planning: optimal and online algorithms, (Proc. of the International Conference on Automated Planning and Scheduling (ICAPS) (2008)), 222-231 |
| [31] | Meneguzzi, F.; Luck, M., Declarative planning in procedural agent architectures, Expert Syst. Appl., 40, 16, 6508-6520 (2013) |
| [32] | Meneguzzi, F.; de Silva, L., Planning in BDI agents: a survey of the integration of planning algorithms and agent reasoning, Knowl. Eng. Rev., 30, 1, 1-44 (2015) |
| [33] | Meneguzzi, F.; Zorzo, A. F.; da Costa Móra, M., Propositional planning in BDI agents, (Proc. of the ACM Symposium on Applied Computing (2004)), 58-63 |
| [34] | Minton, S.; Bresina, J.; Drummond, M., Total-order and partial-order planning: a comparative analysis, J. Artificial Intelligence Res., 2, 227-262 (1994) |
| [35] | Nau, D. S.; Cao, Y.; Lotem, A.; Muñoz-Avila, H., SHOP: simple hierarchical ordered planner, (Proc. of the International Joint Conference on Artificial Intelligence (IJCAI) (1999)), 968-973 |
| [36] | Nau, D. S.; Au, T. C.; Ilghami, O.; Kuter, U.; Murdock, J. W.; Wu, D.; Yaman, F., SHOP2: an HTN planning system, J. Artificial Intelligence Res., 20, 379-404 (2003) · Zbl 1058.68106 |
| [37] | Rao, A. S., AgentSpeak(L): BDI agents speak out in a logical computable language, (Proc. of the European workshop on Modelling Autonomous Agents in a Multi-Agent World: Agents Breaking Away (MAAMAW) (1996), Springer), 42-55 |
| [38] | Sardina, S.; Padgham, L., A BDI agent programming language with failure recovery, declarative goals, and planning, Auton. Agents Multi-Agent Syst., 23, 1, 18-70 (2011) |
| [39] | Sardina, S.; de Silva, L.; Padgham, L., Hierarchical planning in BDI agent programming languages: a formal approach, (Proc. of the International Conference on Autonomous Agents and Multi-Agent Systems (AAMAS) (2006)), 1001-1008 |
| [40] | Schattenberg, B., Hybrid Planning and Scheduling (2009), University of Ulm: University of Ulm Germany, PhD thesis |
| [41] | Shivashankar, V.; Alford, R.; Kuter, U.; Nau, D., The GoDeL planning system: a more perfect union of domain-independent and hierarchical planning, (Proc. of the International Joint Conference on Artificial Intelligence (IJCAI) (2013)), 2380-2386 |
| [42] | de Silva, L.; Sardina, S.; Padgham, L., First principles planning in BDI systems, (Proc. of the International Conference on Autonomous Agents and Multi-Agent Systems (AAMAS) (2009)), 1105-1112 |
| [43] | de Silva, L.; Lallement, R.; Alami, R., The HATP hierarchical planner: formalisation and an initial study of its usability and practicality, (Proc. of the International Conference on Intelligent Robots and Systems (IROS) (2015)), 6465-6472 |
| [44] | de Silva, L.; Sardina, S.; Padgham, L., Summary information for reasoning about hierarchical plans, (Proc. of the European Conference on Artificial Intelligence (ECAI) (2016)), 1300-1308 · Zbl 1403.68249 |
| [45] | Sohrabi, S.; Baier, J. A.; McIlraith, S. A., HTN planning with preferences, (Proc. of the International Joint Conference on Artificial Intelligence (IJCAI) (2009)), 1790-1797 |
| [46] | Wallis, P.; Rönnquist, R.; Jarvis, D.; Lucas, A., The automated wingman - using JACK intelligent agents for unmanned autonomous vehicles, (Proc. of the IEEE Aerospace Conference (2002)), 2615-2622 |
| [47] | Wilkins, D. E.; Myers, K. L.; Lowrance, J. D.; Wesley, L. P., Planning and reacting in uncertain and dynamic environments, J. Exp. Theor. Artif. Intell., 7, 1, 197-227 (1995) · Zbl 0939.68834 |
| [48] | Xiao, Z.; Herzig, A.; Perrussel, L.; Wan, H.; Su, X., Hierarchical task network planning with task insertion and state constraints, (Proc. of the International Joint Conference on Artificial Intelligence (IJCAI) (2017)), 4463-4469 |
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.
