Junseok Lee, Decentralized Task Assignment Methodology with Spatial Constraint, Master's Thesis, Department of Industrial and Systems Engineering, KAIST, 2015 

Abstract

An assignment problem is a traditional research area of the optimization field. Centralized optimization methodologies such as linear programming has advantage in the assignment problems. Meanwhile, the decentralized approaches for solving assignment problem have emerged recently. Under the decentralization, each entity determines its assignment without any central control. Thus, the efficient interaction between entities is the main issue for the decentralized assignment problem solving methodologies. Distributed constraint optimization problem (DCOP) is a representative methodology for decentralized assignment problem. In DCOP model, each entity determines its actions to optimize the cost generated from relational constraints with other entities. Asynchronous distributed optimization (ADOPT) is an algorithm which finds DCOP solution by message communication between entities. Since the number of required message communication exponentially increases as the problem scale increases, the applications of the algorithm into real problem have not been studied frequently. This research proposes three improvement methods to make the algorithm more adaptable for large-scale problems. The improvements aim to reduce the solution time by relaxing the constraints between entities especially with the spatial properties of the entities. The virtual experiment and analysis will address the influence of the improvements on the original algorithm. The proposed improvement methods improves the execution time performance while maintaining the solution quality as same as the original algorithm.

@masterthesis{Lee:2015,

author = {Junseok Lee},

advisor ={Il-Chul Moon},

title = {Decentralized Task Assignment Methodology with Spatial Constraint},

school = {KAIST},

year = {2015}

}