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

Katsutoshi Hirayama

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.

Subjects: 7. Distributed AI; 7.1 Multi-Agent Systems

This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.