Asynchronous Weak-commitment Search for Solving Distributed Constraint Satisfaction Problems
First International
Conference on Principles and Practice of Constraint Programming (CP-95),
pp.407-422,1995.
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
called asynchronous weak-commitment 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.