An Approach to Over-constrained Distributed Constraint
Satisfaction Problems: Distributed Hierarchical Constraint Satisfaction
Katsutoshi Hirayama, Makoto Yokoo,
4th International Conference on Multi-agent Systems
(ICMAS-2000), 2000.
Many problems in multi-agent systems can be described
as a distributed CSP. However, some real-life problem can
be over-constrained and without a set of consistent variable
values when described as a distributed CSP. We have
presented a distributed partial CSP for handling such an
over-constrained situation and a distributed maximal CSP
as a subclass of distributed partial CSP. In this paper, we
first show another subclass of distributed partial CSP, a distributed
hierarchical CSP. Next, we present a series of new
algorithms for solving a distributed hierarchical CSP, each
of which is designed based on our previous distributed constraint
satisfaction algorithms. Finally, we evaluate the performance
of the new algorithms on distributed 3-coloring
problems in terms of optimality and anytime characteristics.
The results show that our new algorithms perform much better
than the previous algorithm for finding an optimal solution
and produce good results for anytime characteristics.