Dynamic Agent-Ordering and Nogood-Repairing inDistributed Constraint Satisfaction Problems

May 2004

Proceedings of the Seventeenth International Florida Artificial Intelligence Research Society Conference (FLAIRS 2004)

Volume

Proceedings of the Seventeenth International Florida Artificial Intelligence Research Society Conference (FLAIRS 2004)

All Papers

The distributed constraint satisfaction problem (CSP) is ageneral formalization used to represent problems in distributed multi-agent systems. To deal with realistic problems, multiple local variables may be required within eachautonomous agent. A number of heuristics have been developed for solving such multiple local variable problems. However, these approaches do not always guarantee agent independence and have low efficiency search mechanisms. In this paper, we are interested in increasing search efficiencyfor distributed CSPs. To this end we present a new algorithm using unsatisfied constraint densities to dynamicallydetermine agent ordering during the search. Variables having a total order relationship only exist in the local agent.The independence of agents is guaranteed and agents without neighboring relationships can run concurrently and asynchronously. As a result of using nogoods to guarantee completeness, we developed a new technique called nogood repairing, which greatly reduces the number of nogoods storedand communication costs during the search, leading to further efficiency gains. In an empirical study, we show our newapproach outperforms an equivalent static ordering algorithmand a current state-of-the-art technique in terms of executiontime, memory usage and communication cost.