IMPACTing SHOP: Putting an AI Planner Into a Multi-Agent Environment

Springer Science and Business Media LLC - Tập 37 - Trang 381-407 - 2003
Jürgen Dix1, Héctor Muñoz-Avila2, Dana S. Nau2, Lingling Zhang2
1The University of Manchester, Manchester, UK
2University of Maryland, College Park, USA

Tóm tắt

In this paper we describe a formalism for integrating the SHOP HTN planning system with the IMPACT multi-agent environment. We define the A-SHOP algorithm, an agentized adaptation of the SHOP planning algorithm that takes advantage of IMPACT's capabilities for interacting with external agents, performing mixed symbolic/numeric computations, and making queries to distributed, heterogeneous information sources (such as arbitrary legacy and/or specialized data structures or external databases). We show that A-SHOP is both sound and complete if certain conditions are met.

Tài liệu tham khảo

S. Adali, K.S. Candan, S.-S. Chen, K. Erol and V.S. Subrahmanian, Advanced video information systems: Data structures and query processing, Multimedia Systems 4(4) (1996) 172–186. S. Adali et al., Web hermes user manual, http://www.cs.umd.edu/projects/hermes/UserManual/index.html (1997). F. Bacchus and F. Kabanza, Using temporal logics to express search control knowledge for planning, Artificial Intelligence 116(1-2) (2000) 123–191. J. Benton and V.S. Subrahmanian, Using hybrid knowledge bases for missile siting problems, in: Proceedings of the Conference on Artificial Intelligence Applications (IEEE Computer Society, 1994) pp. 141–148. A. Brink, S. Marcus and V.S. Subrahmanian, Heterogeneous multimedia reasoning, IEEE Computer 28(9) (1995) 33–39. S. Chien, R. Hill, X. Wang and T. Estlin, Why real-world planning is difficult: A tale of two applications, in: Proceedings of the 3rd Europ. Workshop on Planning (EWSP-95) (1995). K. Currie and A. Tate, O-plan: the open planning architecture, Artificial Intelligence 52(1) (1991). R. Davis and R. Smith, Negotiation as a metaphor for distributed problem solving, Artificial Intelligence 20(1) (1983). M.E. desJardins, E.H. Durfee, C.L. Ortiz Jr. and M.J. Wolverton, A survey of research in distributed, continual planning, AI Magazine 20(4) (1999). J. Dix, S. Kraus and V.S. Subrahmanian, Temporal agent programs, Artificial Intelligence 127(1) (2001) 87–135. J. Dix, H. Munoz-Avila and D.N. Lingling Zhang, Planning in a multi-agent environment: theory and practice, in: Proceedings of the First International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS' 02) (ACM Press, 2002). J. Dix, M. Nanni and V.S. Subrahmanian, Probabilistic agent programs, ACM Transactions of Computational Logic 1(2) (2000) 207–245. J. Dix, F. Öczan and V.S. Subrahmanian, Improving performance of heavily loaded agents, Technical Report CS-TR-4202, Department of Computer Science, University of Maryland, College Park, MD (November 2000). J. Dix, V.S. Subrahmanian and G. Pick, Meta agent programs, Journal of Logic Programming 46(1-2) (2000) 1–60. T. Eiter, V.S. Subrahmanian and G. Pick, Heterogeneous active agents, I: Semantics, Artificial Intelligence 108(1-2) (1999) 179–255. T. Eiter and V.S. Subrahmanian, Heterogeneous active agents, II: Algorithms and complexity, Artificial Intelligence 108(1-2) (1999) 257–307. T. Eiter, V.S. Subrahmanian and T.J. Rogers, Heterogeneous active agents, III: Polynomially implementable agents, Artificial Intelligence 117(1) (2000) 107–167. O. Etzioni, D. Weld, D. Draper, N. Lesh and M. Williamson, An approach to planning with incomplete information, in: Proceedings of KR-92 (1992). M. Friedman and D. Weld, Efficiently executing information-gathering plans, in: Proceedings of IJCAI-97 (1997). K. Golden, O. Etzioni and D. Weld, Omnipotence without omniscience: efficient sensor management for planning, in: Proceedings of AAAI-94 (1994). K.V. Hindriks, F.S. De Boer, W. Van der Hoek and J.-J. Ch. Meyer, Agent programming in 3APL, Autonomous Agents and Multi-Agent Systems 2(4) (1999) 357–401. H. Kautz and J.P. Walser, State-space planning by integer optimization, in: Proceedings of the 17th National Conference of the American Association for Artificial Intelligence (1999) pp. 526–533. C.A. Knoblock, Building a planner for information gathering: a report from the trenches, in: Proceedings of AIPS-96 (1996). J. Köhler, Planning under resource constraints, in: Proceedings of the 13th European Conference on Artificial Intelligence (1998) pp. 489–493. K.S. Lambert, Noncombatant evacuation operations: Plan now or pay later, Technical report, Naval War College, Newport, RI (1992). D.S. Nau, Y. Cao, A. Lotem and H. Muñoz-Avila, Shop: Simple hierarchical ordered planner, in: Proceedings of IJCAI-99 (1999). D.S. Nau, H. Muñoz-Avila, Y. Cao, A. Lotem and S. Mitchell, Total-order planning with partially ordered subtasks, in: Proceedings of IJCAI-2001 (2001). D.S. Nau, S.J.J. Smith and K. Erol, Control strategies in HTN planning: Theory versus practice, in: AAAI-98/IAAI-98 Proceedings (1998) pp. 1127–1133. M. Paolucci, D. Kalp, A. Pannu, O. Shehory and K. Sycara, A planning component for retsina agents, in: Intelligent Agents VI (M. Wooldridge and Y. Lesperance, 2000). M. Paolucci, O. Shehory and K. Sycara, Interleaving planning and execution in a multiagent teamplanning environment, Technical Report CMU-RI-TR-00-01 (2000). A. Rao, BDI agents speak out in a logical computable language, in: Agents Breaking Away: Proceedings of the Seventh European Workshop on Modelling Autonomous Agents in a Multi-Agent World, eds. W. Van de Velde and J.W. Perram, Lecture Notes in Artificial Intelligence, Vol. 1038 (Springer, Berlin, 1996) pp. 42–55. E. Sacerdoti, A Structure for Plans and Behavior (American Elsevier Publishing, 1977). J. Schafer, T.J. Rogers and J.A. Marin, Networked visualization of heterogeneous US Army war reserves readiness data, in: Advances in Multimedia Information Systems, 4th International Workshop, MIS'98, eds. S. Jajodia, T. Ozsu and A. Dogac, Lecture Notes in Computer Science, Vol. 1508, Istanbul, Turkey, September 1998 (Springer, Berlin, 1998) pp. 136–147. A.B. Siegel, Eastern Exit: The noncombatant evacuation operation (NEO) from Mogadishu, Somalia, in January 1991, Technical Report CRM 91-221, Center for Naval Analyses, Arlington, VA (1991). B. Srivastava and S. Kambhampati, Scaling up planning by teasing out resource scheduling, Technical Report ASU CSE TR 99-005 (1999). To appear in ECP-99. V.S. Subrahmanian, P. Bonatti, J. Dix, T. Eiter, S. Kraus, F. Özcan and R. Ross, Heterogenous Active Agents (MIT Press, Cambridge, MA, 2000). A. Tate, Generating project networks, in: Proc. IJCAI-77 (1998) pp. 888–893. S. Thomas, PLACA: An agent-oriented programming language, Ph.D. Thesis, Stanford University (1993). S. Thomas, The placa agent programming language, in: Pre-Proc. of Workshop on Agent Theories, Architectures, and Languages (ATAL'94), Amsterdam, The Netherlands (1994) pp. 307–319. D.E. Wilkins, Practical Planning - Extending the Classical AI Planning Paradigm (Morgan Kaufmann, San Mateo, CA, 1988). S.A. Wolfman and D.S. Weld, The LPSAT engine and its application to resource planning, in: Proceedings of the 15th International Joint Conference on Artificial Intelligence (1999) pp. 310–317. M. Wooldridge and N. Jennings, Intelligent agents: Theory and practice, Knowledge Engineering Reviews 10(2) (1995).