Multi-robot task allocation through vacancy chain scheduling

Modeling the effects of robot interaction in multi-robot systems, i.e., the group dynamics, is difficult due to the complexity of such interactions. This article formalizes the concept of group dynamics in the framework of scheduling and presents a proof that multi-robot task allocation (MRTA), in systems with significant performance effects from group dynamics, is an NP-complete problem. As a way of dealing with this complexity we have developed vacancy chain scheduling (VCS), a new formal model of MRTA inspired by a resource distribution process commonly found in nature. VCS is also the foundation of a new MRTA algorithm which relies on optimal allocation patterns to emerge from the stigmergic effects of robot interactions. We present experimental evidence of the validity of the VCS model from high-fidelity simulations. The experimental results validate the VCS model by reliably producing the predicted allocation patterns in both homogeneous and heterogeneous groups of robots. The evidence also supports our claim that VCS is a feasible solution for a restricted class of MRTA problems. (C) 2008 Elsevier B.V. All rights reserved.