Title

Simple support-based distributed search

Document Type

Conference Paper

Publication Details

Harvey, P., Chang, C. & Ghose, A. K. (2006). Simple support-based distributed search. In L. Lamontagne & M. Marchand (Eds.), 19th Conference ofthe Canadian Society for Computational Studies of Intelligence: Canadian A1 2006: Proceedings (pp. 159-170). Germany: Springer-Verlag.

Abstract

Distributed Constraint Satisfaction Problems provide a natural mechanism for multiagent coordination and agreement. To date, algorithms for Distributed Constraint Satisfaction Problems have tended to mirror existing non-distributed global-search or local-search algorithms. Unfortunately, existing distributed global-search algorithms derive from classical backtracking search methods and require a total ordering over agents for completeness. Distributed variants of local-search algorithms (such as distributed breakout) inherit the incompleteness properties of their predecessors, or depend on the creation of new communication links between agents. In [5, 4] a new algorithm was presented designed explicitly for distributed environments so that a global ordering is not required, while avoiding the problems of existing local-search algorithms. This paper presents a significant improvement on that algorithm in performance and provability.

RIS ID

18518

Please refer to publisher version or contact your library.

Share

COinS
 

Link to publisher version (DOI)

http://dx.doi.org/10.1007/11766247_14