Constraint Relaxation in Distributed Constraint Satisfaction Problem
5th International Conference on Tools with Artificial Intelligence, pp. 56--63,
1993.
The distributed constraint satisfaction problem (DCSP) formulation
has recently been identified as a general framework for formalizing
various Distributed Artificial Intelligence problems.
In this paper,
we extend the DCSP formalization by introducing the notion of
importance values of constraints. With these values,
we define a solution criterion for DCSPs that are over-constrained
(where no solution satisfies all constraints completely).
We show that agents can find an optimal solution with
this criterion by using the asynchronous incremental relaxation algorithm,
in which the agents
iteratively apply the asynchronous backtracking algorithm
to solve a DCSP, while incrementally relaxing less important constraints.
In this algorithm, agents act asynchronously and concurrently,
in contrast to traditional sequential backtracking techniques,
while guaranteeing the completeness of the algorithm and the optimality of the
optimality.
Furthermore,
we show that, in this algorithm,
agents can avoid redundant computation
and achieve a five-fold speed-up
in example problems by maintaining the dependencies between
constraint violations (nogoods) and constraints.