Asynchronous Weak-commitment Search for Solving Distributed Constraint Satisfaction Problems
Asynchronous Weak-commitment Search for Solving Distributed Constraint Satisfaction Problems
复制标题
解决分布式约束满足问题的异步弱承诺搜索
DOI：
10.1007/3-540-60299-2_6
复制
发表时间：
1995
期刊：
影响因子：
--
通讯作者：
M. Yokoo
中科院分区：
文献类型：
--
作者：
M. Yokoo
A distributed constraint satisfaction problem (Distributed CSP) is a CSP in which variables and constraints are distributed among multiple automated agents, and various application problems in Distributed Artificial Intelligence can be formalized as Distributed CSPs. We develop a new algorithm for solving Distributed CSPs calledasynchronous weakcommitment search, which is inspired by the weak-commitment search algorithm for solving CSPs. This algorithm can revise a bad decision without an exhaustive search by changing the priority order of agents dynamically. Furthermore, agents can act asynchronously and concurrently based on their local knowledge without any global control, while guaranteeing the completeness of the algorithm.The experimental results on various example problems show that this algorithm is by far more efficient than the asynchronous backtracking algorithm for solving Distributed CSPs, in which the priority order is static. The priority order represents a hierarchy of agent authority, i.e., the priority of decision making. Therefore, these results imply that a flexible agent organization, in which the hierarchical order is changed dynamically, actually performs better than an organization in which the hierarchical order is static and rigid.
