A near-optimal node-to-agent mapping heuristic for GDL-based DCOP algorithms in multi-agent systems
File(s)
Published version
Author(s)
Mosaddek Khan, MD
Yeoh, W
Tran-Thanh, L
Jennings, NR
Type
Conference Paper
Abstract
Distributed Constraint Optimization Problems (DCOPs) can be used to model a number of multi-agent coordination problems. The conventional DCOP model assumes that the subproblem that each agent is responsible for (i.e. the mapping of nodes in the constraint graph to agents) is part of the model description. While this assumption is often reasonable, there are many applications where there is some flexibility in making this assignment. In this paper, we focus on this gap and make the following contributions: (1) We formulate this problem as an optimization problem, where the goal is to find an assignment that minimizes the completion time of the DCOP algorithm (e.g. Action-GDL or Max-Sum) that operates on this mapping. (2) We propose a novel heuristic, called MNA, that can be executed in a centralized or decentralized manner. (3) Our empirical evaluation illustrates a substantial reduction in completion time, ranging from 16% to 40%, without affecting the solution quality of the algorithms, compared to the current state of the art. In addition, we observe empirically that the completion time obtained from our approach is near-optimal; it never exceeds more than 10% of what can be achieved from the optimal node-to-agent mapping.
Date Issued
2018-07-15
Date Acceptance
2018-07-10
Citation
Proceedings of the 17th International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS, 2018, pp.1613-1621
ISBN
9781450356497
ISSN
2523-5699
Publisher
International Foundation for Autonomous Agents and MultiAgent Systems (IFAAMAS)
Start Page
1613
End Page
1621
Journal / Book Title
Proceedings of the 17th International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS
Volume
3
Copyright Statement
© 2018 by International Foundation for Autonomous Agents and MultiAgent Systems (IFAAMAS). All rights reserved.
Source
International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS 2018
Publication Status
Published
Start Date
2018-07-10
Finish Date
2018-07-15
Coverage Spatial
Stockholm, Sweden