Partially Decentralised Junction Trees for Quality Guaranteed Approximate Coordination in Open Multi-agent Systems with Optimality/Runtime Trade-Off

In this paper we address the problem of efficient decentralised coordination of cooperative multi-agent systems by taking into account the structure of the problem. We consider coordination problems that can be framed as Distributed Constraint Optimization Problems (DCOP).Graphical models such as junction trees are widely used in order to exploit the structure of an inference problem so as to minimise the complexity of the optimal solution of such problems. In this paper we propose an extension of the junction tree inference algorithm in order to provide it with properties befitting more closely multi-agent systems operational constraints. Specifically, our contribution is able to provide an adjustable trade-off between the make span of the coordination process and its decentralisation as well as the solution quality. We provide bounds, and report empirical results on two kinds of instances of coordination networks.