| 摘要: |
| 多Agent 协作过程中的许多挑战都可以建模为分布式约束优化问题.针对低约束密度的分布式约束优化问题,提出了一种基于贪婪和回跳思想的求解算法.在该算法中,各Agent 基于贪婪原则进行决策,能够利用低约束密度问题中大量赋值组合代价为0 这一特点来加快求解速度.同时,Agent 间的回跳机制可以在贪婪原则陷入局部最优时保证算法的完全性.相对于已有主流算法,该算法可以在保持多项式级别的消息长度/空间复杂度的前提下,以较少的消息数目求解低约束密度的分布式约束优化问题.给出了算法关键机制的正确性证明,并通过实验验证了算法的上述性能优势. |
| 关键词: 分布式约束优化问题 多Agent 算法 |
| DOI：10.3724/SP.J.1001.2011.03765 |
| 分类号: |
| 基金项目:国家自然科学基金(90818028); 国家重点基础研究发展计划(973)(2011CB302600); 国家杰出青年科学基金(60625203) |
|
| Algorithm for Distributed Constraint Optimization Problems with Low Constraint Density |
|
DING Bo1, WANG Huai-Min1,2, SHI Dian-Xi1, TANG Yang-Bin1
|
|
1.School of Computer, National University of Defense Technology, Changsha 410073, China;2.National Key Laboratory for Parallel and Distributed Processing, School of Computer, National University of Defense Technology, Changsha 410073, China
|
| Abstract: |
| Many challenges in multi-agent coordination can be modeled as Distributed Constraint Optimization Problems (DCOPs). Aiming at DCOPs with low constraint density, this paper proposes a distributed algorithm based on the idea of greed and backjumping. In this algorithm, each agent makes decisions according to the greedy principle that the most assignment combinations in the problems with low constraint density occur at a zero cost, and the backjumping mechanism among the agents ensures the success of this algorithm, even when this greedy principle leads to a local optimum. In contrast with the existing mainstream DCOP algorithms, this algorithm can solve problems with low constraint density with fewer messages while keeping the polynomial message length and space complexity. The correctness of the key mechanisms in this algorithm has been proved, and those advantages in performance have been verified by experiments. |
| Key words: distributed constraint optimization problem multi-agent algorithm |
