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

Rafael Cauê CARDOSO, Rafael Heitor BORDINI

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.

Keywords


multi-agent planning; hierarchical task network; planning formalism; SHOP2; JaCaMo

Full Text:

PDF

References


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.




DOI: http://dx.doi.org/10.14201/ADCAIJ201762517





Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.

Clarivate Analytics