A hybrid tree-based algorithm to solve asymmetric distributed constraint optimization problems
- PDF / 4,090,036 Bytes
- 42 Pages / 439.37 x 666.142 pts Page_size
- 73 Downloads / 218 Views
(2020) 34:50
A hybrid tree‑based algorithm to solve asymmetric distributed constraint optimization problems Dingding Chen1 · Yanchen Deng2 · Ziyu Chen1 · Zhongshi He1 · Wenxin Zhang1
© Springer Science+Business Media, LLC, part of Springer Nature 2020
Abstract Asymmetric distributed constraint optimization problems (ADCOPs) have emerged as an important formalism in multi-agent community due to their ability to capture personal preferences. However, the existing search-based complete algorithms for ADCOPs only exploit local knowledge to calculate lower bounds, which leads to inefficient pruning and prohibits them from solving large scale problems. On the other hand, inference-based complete algorithms (e.g., DPOP) for distributed constraint optimization problems are able to aggregate the global cost promptly but cannot be directly applied into ADCOPs due to a privacy concern. Thus, in this paper, we investigate the possibility of combining inference and search to effectively solve ADCOPs at an acceptable loss of privacy. Specifically, we propose a hybrid complete ADCOP algorithm called PT-ISABB which uses a tailored inference algorithm to provide tight lower bounds and upper bounds, and a tree-based complete search algorithm to guarantee the optimality. Furthermore, we introduce two suboptimal variants of PT-ISABB based on bounded-error approximation mechanisms to enable trade-off between theoretically guaranteed solutions and coordination overheads. We prove the correctness of PT-ISABB and its suboptimal variants. Finally, the experimental results demonstrate that PT-ISABB exhibits great superiorities over other state-of-the-art searchbased complete algorithms and its suboptimal variants can quickly find a solution within the user-specified bounded-error. Keywords DCOP · ADCOP · Complete ADCOP algorithm · Search · Inference
Dingding Chen and Yanchen Deng have contributed equally to this work. * Ziyu Chen [email protected] * Zhongshi He [email protected] 1
College of Computer Science, Chongqing University, Chongqing 400044, China
2
School of Computer Science and Engineering, Nanyang Technological University, Singapore 639798, Singapore
13
Vol.:(0123456789)
50
Page 2 of 42
Autonomous Agents and Multi-Agent Systems
(2020) 34:50
1 Introduction Distributed constraint optimization problems (DCOPs) [10, 19, 41] are an elegant paradigm for modeling multi-agent system (MAS) where agents coordinate with each other to optimize a global objective. They have been successfully applied into various MAS applications including smart home [11], radio frequency allocation [27], task scheduling [18, 38] and many others. Over the past decades, a wide variety of algorithms have been developed to solve DCOPs and can be divided into either complete or incomplete ones. Incomplete algorithms aim to produce near-optimal solutions at small computational efforts and generally follow three strategies, i.e., local search [24, 42], inference [5, 9, 37, 44] and sampling [29, 31]. On the contrary, complete algorithms guarantee
Data Loading...
