Author: Andrew J. Parkes.
To appear in the Workshop Distributed Constraint Reasoning at the 2001 International Joint Conference on Artificial Intelligence (IJCAI-01)
We consider distributed environments with high communication costs and complex local problems and argue that search can benefit from the exchange of messages containing relatively deep semantic information about the structure of the problems at each node. Specifically, we consider the case that messages contain compact representations of large clusters of solutions from each node. The intention being to weaken the constraints passed between nodes and so reduce the chance of failure in the receiving nodes.
We make some first steps towards such a distributed search method. We define clusters as appropriate for both sequential and distributed problems. Finding optimal (largest possible) clusters turns out to be NP-hard. However, optimality is not necessary for the search, and so we give some heuristic constructive algorithms for producing clusters of varying sizes. Initial experimental studies on the utility of clusters are made in a distributed domain based on random SAT problems. We find evidence that the use of clusters has the potential to greatly reduce the chance of the distributed search failing unnecessarily.