Asynchronous Weak-commitment Search for Solving Large-Scale Distributed Constraint Satisfaction Problems
Makoto Yokoo · 1995
Makoto YokooNTT Communication Science Laboratories2-2 Hikaridai, Seika-choSoraku-gun, Kyoto 619-02, Japane-maih [email protected] ~pA distributed constraint satisfaction problem (Dis-tributed CSP) (Yokoo et aL 1992) is a constraint sat-isfaction problem in which variables and constraintsare distributed among multiple agents. Surprisingly awide variety of AI problems can be formalized as CSPs.Similarly, various application problems in DAI whichare concerned with finding a consistent combinationof agent actions (e.g., distributed resource allocationproblems, distributed scheduling problems, and multi-agent truth maintenance tasks) can be formalized asDistributed CSPs. Therefore, we can consider a Dis-tributed CSP as a general framework for DAI, and al-gorithms for solving Distributed CSPs as an importantinfrastructure in DAI.The author has developed a basic algorithm forsolving Distributed CSPs called asynchronows back-tracking (Yokoo et al. 1992), in which agents actasynchronously and concurrently based on their localknowledge without any global control.In this work, we develop a new algorithm calledasynchronous weak-commitment search, which is in-spired by the weak-commitment search algorithm forsolving CSPs (Yokoo 1994). The main characteristicof this algorithm is as follows.¯ A bad decision can be revised without an exhaus-tive search by changing the priority order of agentsdynamicallyIn the asynchronous backtracking algorithm, the pri-ority order of agents is determined, and an agent triesto find a value satisfying the constraints with the vari-ables of higher priority agents. When an agent sets avariable value, the agent commits to the selected valuestrongly, i.e., the selected value will not be changedunless an exhaustive search is performed by lower pri-ority agents. Therefore, in large-scale problems, a sin-gle mistake of value selection becomes fatal since doingsuch an exhaustive search is virtually impossible.On the other hand, in the asynchronous weak-commitment search, when an agent can not find a valueconsistent with the higher priority agents, the prior-ity of the agent is changed so that the agent has thehighest priority. As a result, when an agent makes amistake in value selection, the priority of another agentasynchronous rain-conflict asynchronousbscktzacking only