Randomized coordination search for scalable multiagent planning

Multiagent Markov Decision Processes (MMDP5) are difficult problems to solve due to the exponential increase in the size of the planning space in the number of agents. One of the most successful approaches for solving MMDPs utilizes coordination graphs (CG5), which encode the decouplings between the agents to reduce the dimension of the value function, which in turn reduces the computational complexity. However, it is typically assumed that the structure of the CG is available a priori, which is a limiting assumption for many practical scenarios. This work presents a randomized planning scheme based on the Bayesian optimization algorithm to probabilistically search over the space of CGs to discover CG structures that yield high return policies. The results demonstrate that the proposed method is superior in terms of convergence speed and accumulated reward.