Learning Cooperation and Online Planning Through Simulation and Graph Convolutional Network
This work addresses the problem of real-time decision-making in multi-agent systems for researchers and practitioners, offering a novel method that improves scalability and adaptability, though it builds incrementally on existing techniques like MCTS and GCNs.
The paper tackles the challenge of efficient and scalable online planning in multi-agent cooperative environments with dynamically changing conditions and large state-action spaces, introducing SiCLOP, which combines Monte Carlo Tree Search, Coordination Graphs, and Graph Neural Networks to learn cooperation and prune action spaces, achieving significant outperformance over state-of-the-art algorithms in empirical results.
Multi-agent Markov Decision Process (MMDP) has been an effective way of modelling sequential decision making algorithms for multi-agent cooperative environments. A number of algorithms based on centralized and decentralized planning have been developed in this domain. However, dynamically changing environment, coupled with exponential size of the state and joint action space, make it difficult for these algorithms to provide both efficiency and scalability. Recently, Centralized planning algorithm FV-MCTS-MP and decentralized planning algorithm \textit{Alternate maximization with Behavioural Cloning} (ABC) have achieved notable performance in solving MMDPs. However, they are not capable of adapting to dynamically changing environments and accounting for the lack of communication among agents, respectively. Against this background, we introduce a simulation based online planning algorithm, that we call SiCLOP, for multi-agent cooperative environments. Specifically, SiCLOP tailors Monte Carlo Tree Search (MCTS) and uses Coordination Graph (CG) and Graph Neural Network (GCN) to learn cooperation and provides real time solution of a MMDP problem. It also improves scalability through an effective pruning of action space. Additionally, unlike FV-MCTS-MP and ABC, SiCLOP supports transfer learning, which enables learned agents to operate in different environments. We also provide theoretical discussion about the convergence property of our algorithm within the context of multi-agent settings. Finally, our extensive empirical results show that SiCLOP significantly outperforms the state-of-the-art online planning algorithms.