Communication-constrained distributed task assignment

This paper considers the problem of distributed assignment of tasks to agents in the presence of task constraints, where the agents use a known, but arbitrary communication topology. The task assignment problem considered here requires that all agents that perform tasks related by a task constraint be able to communicate directly. The problem is motivated by complex military missions where tasks are assigned to various vehicles and tasks must be scheduled to meet constraints between them. This requires communication between vehicles responsible for tasks that are related by constraints. The physically distributed and dynamic nature of such missions combined with unreliable communication motivates algorithms that can perform the required distributed planning. Toward this goal, we introduce a method that assigns tasks under the restrictions imposed by these mission constraints. The new method presented here is a distributed search designed to solve a nonlinear, distributed constrained assignment problem for which a proof of correctness is presented. The method is illustrated on an example involving two unmanned air vehicles and two unmanned ground vehicles.