Constraint Relaxation in Distributed Constraint Satisfaction Problems

Abstract

The distributed constraint satisfaction problem (DCSP) formulation has recently been identi ed as a general framework for formalizing various Distributed Arti cial Intelligence problems. In this paper, we extend the DCSP formalization by introducing the notion of importance values of constraints. With these values, we de ne a solution criterion for DCSPs that are over-constrained (where no solution satis es all constraints completely). We show that agents can nd an optimal solution with this criterion by using the asynchronous incremental relaxation algorithm, in which the agents iteratively apply the asynchronous backtracking algorithm [10] 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 vefold speed-up in example problems by maintaining the dependencies between constraint violations (nogoods) and constraints.

Topics

    4 Figures and Tables

    Download Full PDF Version (Non-Commercial Use)