A Multi-Agent Extension of a Hierarchical Task Network Planning Formalism

Abstract

Describing planning domains using a common formalism promotes greater reuse of research, allowing a fairer comparison between different planners and approaches. Common planning formalisms for single-agent planning are already well established (e.g., PDDL, STRIPS, and HTN), but currently there is a shortage of multi-agent planning formalisms with clear semantics. In this paper, we propose a multi-agent extension of the Hierarchical Task Network (HTN) planning formalism for multi-agent planning problems. Our formalism, the Multi-Agent Hierarchical Task Network (MA-HTN), can be used to specify and represent multi-agent planning domains and problems. We provide a grammar with semantics for the domain and problem representation, and describe two case studies with the translation from multi-agent systems developed in JaCaMo to our MA-HTN formalism.
  • Referencias
  • Cómo citar
  • Del mismo autor
  • Métricas
Boissier, O., Bordini, R. H., Hübner, J. F., Ricci, A., and Santi, A., 2011. Multi-agent oriented programming with JaCaMo. Science of Computer Programming https://doi.org/10.1016/j.scico.2011.10.004

Bordini, R. H., and Dix, J., 2013. Programming Multiagent Systems. In Weiss, G., editor, Multiagent Systems 2nd Edition, chapter 11, pages 5870–639. MIT Press.

Bordini, R. H., Wooldridge, M., and Hübner, J. F., 2007. Programming Multi-Agent Systems in AgentSpeak using Jason. John Wiley & Sons. ISBN 0470029005.

Brafman, R. I., and Domshlak, C., 2008. From One to Many: Planning for Loosely Coupled Multi-Agent Systems.

Cardoso, R. C., and Bordini, R. H., 2016. A Distributed Online Multi-Agent Planning System. In 4th Workshop on Distributed and Multi-Agent Planning (DMAP-16). London, United Kingdom.

Clement, B. J., Durfee, E. H., and Barrett, A. C., 2007. Abstract Reasoning for Planning and Coordination. Journal of Artificial Intelligence Research (JAIR), 28:453–515.

Dignum, V., and Padget, J., 2013. Multiagent Organizations. In Weiss, G., editor, Multiagent Systems 2nd Edition, chapter 2, pages 51–98. MIT Press.

Durfee, E. H., 1999. Distributed problem solving and planning. In Mutliagent systems, pages 121–164. MIT Press.

Durfee, E. H., and Zilberstein, S., 2013. Multiagent Planning, Control, and Execution. In Weiss, G., editor, Multiagent Systems 2nd Edition, chapter 11, pages 485–545. MIT Press.

Fikes, R. E., and Nilsson, N. J., 1971. STRIPS: a new approach to the application of theorem proving to problem solving. In Proceedings of the 2nd international joint conference on Artificial intelligence, IJCAI'71, pages 608-620. San Francisco, CA, USA.

Hübner, J. F.; Sichman, J. S. and Boissier, O., 2007. Developing organised multiagent systems using the MOISE+ model: programming issues at the system and agent levels. Int. J. Agent-Oriented Software Engineering, 1(3/4): 370-395. https://doi.org/10.1504/IJAOSE.2007.016266

Kovacs, D. L., 2012. A Multi-Agent Extension of PDDL3.1. In Proceedings of the 3rd Workshop on the International Planning Competition (IPC), ICAPS-2012, pages 19-27. Atibaia, São Paulo, Brazil.

Nau, D.; Ghallab, M. and Traverso, P., 2004. Automated Planning: Theory & Practice. Morgan Kaufmann Publishers Inc., San Francisco, CA, USA.

Nau, D., Ilghami, O., Kuter, U., Murdock, J. W., Wu, D., and Yaman, F., 2003. SHOP2: An HTN planning system. Journal of Artificial Intelligence Research, 20:379–404.

Ricci, A., Piunti, M., Viroli, M., and Omicini, A., 2009. Environment Programming in CArtAgO. In Multi- Agent Programming: Languages, Tools and Applications, Multiagent Systems, Artificial Societies, and Simulated Organizations, chapter 8, pages 259–288. Springer. ISBN 978-0-387-89298-6. https://doi.org/10.1007/ 978-0-387-89299-3_8.

Russell, S. J., and Norvig, P., 2009. Artificial Intelligence: A Modern Approach. Prentice Hall, 3rd edition.

Stolba, M.; Komenda, A. and Kovacs, D. L., editors, 2015. Competition of Distributed and Multi-Agent Planners (CoDMAP-15). Jerusalem, Israel.

Sycara, K. P., 1998. Multiagent systems. AI Magazine, 19:79–92.

Tang, P., Wang, H., Qi, C. and Wang, J., 2012. Anytime Heuristic Search in Temporal HTN Planning for Developing Incident Action Plans. AI Commun., 25(4):321–342. ISSN 0921-7126.

Weerdt, M. d. and Clement, B., 2009. Introduction to Planning in Multiagent Systems. Multiagent Grid Syst., 5(4):345–355. https://doi.org/10.3233/MGS-2009-0133

Weyns, D., Omicini, A., and Odell, J., 2007. Environment As a First Class Abstraction in Multiagent Systems. Autonomous Agents and Multi-Agent Systems, 14(1):5–30. ISSN 1387-2532. https://doi.org/10.1007/ s10458-006-0012-0.
Cardoso, R. C., & Bordini, R. H. (2017). A Multi-Agent Extension of a Hierarchical Task Network Planning Formalism. ADCAIJ: Advances in Distributed Computing and Artificial Intelligence Journal, 6(2), 5–17. https://doi.org/10.14201/ADCAIJ201762517

Most read articles by the same author(s)

Downloads

Download data is not yet available.

Author Biographies

Rafael Cauê Cardoso

,
PUCRS
Rafael C. Cardoso is a Ph.D. student in Computer Science at PUCRS. He obtained his Master's degree in Computer Science from the same institution in 2014. His main research interests are in Multi-Agent Systems (MAS) and Multi-Agent Planning (MAP). Specifically, he is interested in multi-agent programming languages, benchmarks of agent-based languages, goal allocation mechanisms (both for MAS and MAP), multi-agent planners, and coordination mechanisms.

Rafael Heitor Bordini

,
PUCRS
Rafael H. Bordini is an Associate Professor at FACIN-PUCRS since March 2012. Previous to this appointment, he was an associate professor at INF-UFRGS (from July 2009) and previous to that he was a Lecturer in the Department of Computer Science, Durham University, UK (July 2004 to January 2009). He read for a PhD at UCL (finished in early 1999), then worked as a visiting lecturer at INF-UFRGS (until May 2002), and from June 2002 to May 2004 he was a post-doctoral researcher at the University of Liverpool.
+