Output details

DynABT: Dynamic Asynchronous Backtracking for Dynamic DisCSPs

This paper addresses dynamic distributed constraint satisfaction problems (DDisCSPs) - a field which, up till now has received little attention given the additional difficulties they pose when compared to the already challenging static counterparts. In DDisCSPs a distributed problem which changes over time is solved and, as required, re-solved in order to address dynamic changes to the original problem. The originality of approach presented, DynABT, is that it combines solution reuse with reasoning reuse for the resolution of a problem which has changed dynamically. Instead of solving the problem again from scratch when a dynamic change is introduced, the original solution is modified to fit the changed problem. Our approach uses knowledge learnt from solving the original problem to update the solution. A thorough experimental evaluation on both solvable and unsolvable benchmark problems with various rates of problem change and various degrees of difficulty demonstrates that the new approach leads to a number of benefits including solution stability (the new solution is close to the original solution) and reduced cost.