Dec-SGTS: Decentralized Sub-Goal Tree Search for Multi-Agent Coordination

Authors

  • Minglong Li Institute for Quantum Information & State Key Laboratory of High Performance Computing, College of Computer, National University of Defense Technology, China
  • Zhongxuan Cai Institute for Quantum Information & State Key Laboratory of High Performance Computing, College of Computer, National University of Defense Technology, China
  • Wenjing Yang Institute for Quantum Information & State Key Laboratory of High Performance Computing, College of Computer, National University of Defense Technology, China
  • Lixia Wu Artificial Intelligence Department, Zhejiang Cainiao Supply Chain Management Co., Ltd., China
  • Yinghui Xu Artificial Intelligence Department, Zhejiang Cainiao Supply Chain Management Co., Ltd., China
  • Ji Wang Institute for Quantum Information & State Key Laboratory of High Performance Computing, College of Computer, National University of Defense Technology, China

Keywords:

Multiagent Planning, Coordination and Collaboration

Abstract

Multi-agent coordination tends to benefit from efficient communication, where cooperation often happens based on exchanging information about what the agents intend to do, i.e. intention sharing. It becomes a key problem to model the intention by some proper abstraction. Currently, it is either too coarse such as final goals or too fined as primitive steps, which is inefficient due to the lack of modularity and semantics. In this paper, we design a novel multi-agent coordination protocol based on subgoal intentions, defined as the probability distribution over feasible subgoal sequences. The subgoal intentions encode macro-action behaviors with modularity so as to facilitate joint decision making at higher abstraction. Built over the proposed protocol, we present Dec-SGTS (Decentralized Sub-Goal Tree Search) to solve decentralized online multi-agent planning hierarchically and efficiently. Each agent runs Dec-SGTS asynchronously by iteratively performing three phases including local sub-goal tree search, local subgoal intention update and global subgoal intention sharing. We conduct the experiments on courier dispatching problem, and the results show that Dec-SGTS achieves much better reward while enjoying a significant reduction of planning time and communication cost compared with Dec-MCTS (Decentralized Monte Carlo Tree Search).

Downloads

Published

2021-05-18

How to Cite

Li, M., Cai, Z., Yang, W., Wu, L., Xu, Y., & Wang, J. (2021). Dec-SGTS: Decentralized Sub-Goal Tree Search for Multi-Agent Coordination. Proceedings of the AAAI Conference on Artificial Intelligence, 35(13), 11282-11289. Retrieved from https://ojs.aaai.org/index.php/AAAI/article/view/17345

Issue

Section

AAAI Technical Track on Multiagent Systems