Decentralized Subgoal Tree Search for Multiagent Planning without Priors or Communication
Qian Che, Yixuan Li, Ziyao Peng, Wanyuan Wang, Yichuan Jiang · 2023
Multiagent Markov decision processes (MMDPs) provide an expressive framework for multiagent planning in stochastic domains. However, exactly solving a large MMDP is often intractable due to the exponential space of joint action. Due to the trade-off nature of trading computation time for solution quality, decentralized subgoal-based tree search (Dec-SGTS) methods have shown great success for MMDPs. Existing Dec-SGTS methods rely on the predefined subgoals and the communication between agents to perform well, which might not hold in real-world MMDP domains where there is no expert knowledge on subgoals and communication resources are limited. In this paper, we relax these assumptions that arrive at an automated and communication-free Dec-SGTS. On the one hand, we first propose an upstream guided subgoal search (UGSS) technique to exploit historical search experience for subgoal discovery. On the other hand, in order to coordinate agents’ behaviors without communication, we further propose an expectation-alignment technique to proactively align agents’ policies with team’s expectations. Finally, we conduct extensive experiments on multirobot box-pushing tasks, and the results show that compared to multiagent planning benchmarks, the proposed communication-free Dec-SGTS method, which does not require any subgoal priors, achieves satisfactory rewards.