On Communication in Solving Distributed Constraint Satisfaction Problems
Distributed Constraint Satisfaction Problems (DCSP) is a g eneral framework for multi-agent coordination and conflict resolution. I most DCSP algorithms, inter-agent communication is restricted to only ex changing values of variables, since any additional information-exchange is assum ed to lead to significant communication overheads and to a breach of privacy. This pap er provides a detailed experimental investigation of the impact of inter-a gent exchange of additional legal values among agents, within a collaborative se tting. We provide a new run-time model that takes into account the overhead of the ad ditional communication in various computing and networking environments. O ur investigation of more than 300 problem settings with the new run-time model (i ) shows that DCSP strategies with additional information-exchange can lead to big speedups in a significant range of settings; and (ii) provides categorizatio n of problem settings with big speedups by the DCSP strategies based on extra communica tio , enabling us to selectively apply the strategies to a given domain. This p aper not only provides a useful method for performance measurement to the DCSP comm unity, but also shows the utility of additional communication in DCSP.