Distributed constraint satisfaction algorithm for complex local problems
Distributed constraint satisfaction algorithm for complex local problems
复制标题
复杂局部问题的分布式约束满足算法
DOI：
10.1109/icmas.1998.699222
复制
发表时间：
1998
期刊：
影响因子：
--
通讯作者：
K. Hirayama
中科院分区：
文献类型：
--
作者：
M. Yokoo;K. Hirayama
分布式约束满足问题可以形式化地描述多智能体系统中的各种应用问题，目前已经提出了几种求解该问题的算法。这些算法的一个局限性是它们假设每个代理只有一个局部变量。虽然简单的修改使这些算法能够处理多个局部变量，但所获得的算法既不高效，也不能扩展到更大的问题。在异步弱承诺搜索算法的基础上，提出了一种能够有效处理多个局部变量的新算法。在该算法中，坏的局部解可以被修改，而不需要迫使其他代理穷尽地搜索局部问题。此外，由于代理只有在找到满足所有本地约束的本地解决方案时才进行通信，因此可以减少代理之间的交互数量。实验结果表明，该算法比采用代理间优先级排序的算法效率高得多。
A distributed constraint satisfaction problem can formalize various application problems in MAS, and several algorithms for solving this problem have been developed. One limitation of these algorithms is that they assume each agent has only one local variable. Although simple modifications enable these algorithms to handle multiple local variables, obtained algorithms are neither efficient nor scalable to larger problems. We develop a new algorithm that can handle multiple local variables efficiently, which is based on the asynchronous weak-commitment search algorithm. In this algorithm, a bad local solution can be modified without forcing other agents to exhaustively search local problems. Also, the number of interactions among agents can be decreased since agents communicate only when they find local solutions that satisfy all of the local constraints. Experimental evaluations show that this algorithm is far more efficient than an algorithm that uses the prioritization among agents.