Skip to main content

Research Repository

See what's under the surface

Advanced Search

DynABT: dynamic asynchronous backtracking for dynamic DisCSPs.

Omomowo, Bayo; Arana, Inés; Ahriz, Hatem


Bayo Omomowo

Inés Arana

Hatem Ahriz


Daniel Dochev

Marco Pistore

Paolo Traverso


Constraint Satisfaction has been widely used to model static combinatorial problems. However, many AI problems are dynamic and take place in a distributed environment, i.e. the problems are distributed over a number of agents and change over time. Dynamic Distributed Constraint Satisfaction Problems (DDisCSP) [1] are an emerging field for the resolution problems that are dynamic and distributed in nature. In this paper, we propose DynABT, a new Asynchronous algorithm for DDisCSPs which combines solution and reasoning reuse i.e. it handles problem changes by modifying the existing solution while re-using knowledge gained from solving the original(unchanged) problem. The benefits obtained from this approach are two-fold: (i) new solutions are obtained at a lesser cost and; (ii) resulting solutions are stable i.e. close to previous solutions. DynABT has been empirically evaluated on problems of varying difficulty and several degrees of changes has been found to be competitive for the problem classes tested.

Start Date Sep 4, 2008
Publication Date Dec 31, 2008
Publisher Springer (part of Springer Nature)
Pages 285-296
Series Title Lecture notes in computer science
Series Number 5253
ISBN 9783540857754
Institution Citation OMOMOWO, B., ARANA, I. and AHRIZ, H. 2008. DynABT: dynamic asynchronous backtracking for dynamic DisCSPs. In Dochev, D., Pistore, M. and Traverso, P. (eds.) Proceedings of the 13th International conference on artificial intelligence: methodology, systems and applications (AIMSA 2008), 4-6 September 2008, Varna, Bulgaria. Lecture notes in computer science, 5253. Berlin: Springer [online], pages 285-296. Available from:
Keywords Constraint satisfaction; Distributed AI; Dynamic problems


You might also like

Downloadable Citations