文章基本信息

标题：A Distributed Asynchronous Heuristic Algorithm in Generalized Mutual Assignment Problem
本地全文：下载
作者：Kenta Hanada ; Yuki Amemiya ; Kenji Sugimoto 等
期刊名称：人工知能学会論文誌
印刷版ISSN：1346-0714
电子版ISSN：1346-8030
出版年度：2022
卷号：37
期号：2
页码：1-11
DOI：10.1527/tjsai.37-2_B-L81
语种：English
出版社：The Japanese Society for Artificial Intelligence
摘要：Generalized Mutual Assignment Problem (GMAP) is a multi-agent based distributed combinatorial optimization where the agents try to obtain the most profitable job assignment. Since it is NP-hard problem, it is challenging to achieve feasible solutions of GMAP. Existing algorithms to solve GMAP are synchronous ones, that is, the performance of the entire system would deteriorate if a certain agent takes a long time to solve her own subproblem. Furthermore, topology of communication networks strictly depends on the structure of a given instance due to the way of decomposing the problem into subproblem. In this paper, we propose a novel distributed asynchronous heuristic algorithm based on the Lagrangian decomposition formulation in order to obtain feasible solutions as good as possible. Our proposed algorithm consists of a couple of parts. One is to check the feasibility of candidate feasible solutions and the other is to solve the Lagrangian dual problem to generate a variety of candidates. Both of them are based on asynchronous gossip algorithms which are sometimes introduced for modeling rumor spreading phenomena or calculating an average value of sensors, where only two agents communicate with each other at one iteration. Our experiments show the effectiveness of the proposed method.
关键词：distributed optimization;heuristic algorithms;Lagrangian decomposition;assignment problem