Distributed Lagrangean Relaxation Protocol for the Generalized Mutual Assignment Problem(Artificial Intelligence I)

概要

論文の詳細を見る
The generalized assignment problem (GAP) is a typical NP-hard problem and has been studied for many years mainly in the operations research community. The goal of the GAP is to find an optimal assignment of jobs to agents such that the assignment satisfies all of the resource constraints imposed on individual agents. This work provides a distributed formulation of the GAP, the generalized mutual assignment problem (GMAP), to deal with the problems of task/job assignment in multi-agent systems. Then, we present a distributed lagrangean relaxation protocol that enables the agents to simultaneously solve a GMAP instance without any global control mechanism nor globally accessible communication medium like shared memory. In the protocol we introduce a parameter that controls the range of "noise" mixed in with the increment/decrement in a lagrangean multiplier. This parameter can be used to make the agents quickly agree on a feasible solution with reasonably good quality. Our experimental results imply that the parameter may also allow you to control a tradeoff between the quality of a solution and the cost of finding it.
一般社団法人情報処理学会の論文
2004-12-04