Simple support-based distributed search
RIS ID
18518
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.
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.