[1H3-GS-1b] 基礎・理論：モデル化

[1H3-GS-1b-04] Asynchronous and Dynamic Step Size for Heuristic Algorithm in Generalized Mutual Assignment Problem

〇Yuki Amemiya¹, Kenta Hanada¹, Kenji Sugimoto¹ (1. Nara Institute of Science and Technology)

Keywords:multi-agent systems, distributed optimization, generalized mutual assignment problem, Lagrangian decomposition, heuristic algorithm

Generalized Mutual Assignment Problem (GMAP) is a multi-agent based distributed optimization where the agents try to maximize the sum of the entire profits in the system. In order to cope with the difficulty to solve this problem within the reasonable computation time in a decentralized manner, a distributed heuristic algorithm to obtain feasible solutions is investigated in this paper. First, GMAP is reformulated by using the Lagrangian decomposition technique, then a multi-agent consensus based optimization algorithm is applied. Since it is too hard to obtain feasible solutions by the ordinary diminishing step size in the algorithm, an asynchronous and dynamic step size is proposed for the algorithm. Our numerical experiments show the effectiveness of our proposed method.