Click here for full text:
Interleaved Backtracking in Distributed Constraint Networks
Hamadi, Youssef
HPL-2001-153
Keyword(s): distributed constraint satisfaction; distributed AI; collaborative software agents; search
Abstract: 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
Back to Index
| 
printable version
