From one to many: planning for loosely coupled multi-agent systems

Abstract

Loosely coupled multi-agent systems are perceived as easier to plan for because they require less coordination between agent sub-plans. In this paper we set out to formalize this intuition. We establish an upper bound on the complexity of multi-agent planning problems that depends exponentially on two parameters quantifying the level of agents ’ coupling, and on these parameters only. The first parameter is problem-independent, and it measures the inherent level of coupling within the system. The second is problem-specific and it has to do with the minmax number of action-commitments per agent required to solve the problem. Most importantly, the di-rect dependence on the number of agents, on the overall size of the problem, and on the length of the agents ’ plans, is only polynomial. This result is obtained using a new algorithmic methodology which we call “planning as CSP+planning”. We believe this to be one of the first formal results to both quantify the notion of agents ’ coupling, and to demonstrate a multi-agent planning algorithm that, for fixed coupling levels, scales polynomially with the size of the problem.