A New Approach to Distributed Task Assignment Using Lagrangian Decomposition and Distributed Constraint Satisfaction

Abstract

We present a new formulation of distributed task assignment, called Generalized Mutual Assignment Problem (GMAP), which is derived from an NP-hard combinatorial optimization problem that has been studied for many years in the operations research community. To solve the GMAP, we introduce a novel distributed solution protocol using Lagrangian decomposition and distributed constraint satisfaction, where the agents solve their individual optimization problems and coordinate their locally optimized solutions through a distributed constraint satisfaction technique. Next, to produce quick agreement between the agents on a feasible solution with reasonably good quality, we provide a parameter that controls the range of “noise ” mixed with an increment/decrement in a Lagrange multiplier. Our experimental results indicate that the parameter may allow us to control tradeoffs between the quality of a solution and the cost of finding it.