Interleaved Backtracking in Distributed Constraint Networks

Hamadi, Youssef

HP Development Company

关键词: distributed constraint satisfaction;    distributed AI;    collaborative software agents;    search;   

RP-ID  :  HPL-2001-153

学科分类：计算机科学（综合）

美国|英语

来源: HP Labs

【 摘 要 】

The adaptation of software technology to distributed environments is an important challenge today. In this work we combine parallel and distributed search. By this way we add the potential speed-up of a parallel exploration in the processing of distributed problems. This paper extends DIBT, a distributed search procedure operating in distributed constraint networks [HBQ98]. The extension is twofold. First the procedure is updated to face delayed information problems upcoming in heterogeneous systems. Second, the search is extended to simultaneously explore independent parts of a distributed search tree. By this way we introduce parallelism into distributed search, which brings to Interleaved Distributed Intelligent BackTracking (IDIBT). Our results show that on problems with nonuniform search space, IDIBT allows superlinear speed-up over DIBT. 14 Pages