• Calendar

October 30, Tuesday
12:00 – 14:00

The Asynchronous Backtracking algorithm is considered the state of the art algorithm for solving Distributed Constraint Satisfaction Problems. A strong assumption of all previous studies of this algorithm is that a static order is required for its correctness and completeness when polynomial space is used. In the present study, an algorithm that performs asynchronous backtracking on distributed CSPs, with dynamic ordering of agents was presented, ABT_DO. Agents propose reorderings of lower priority agents and send these proposals whenever they send assignment messages. The dynamic ordered asynchronous backtracking algorithm uses polynomial space, similarly to standard ABT. The ABT_DO algorithm with three different ordering heuristics was compared to standard ABT on randomly generated DisCSPs. A Nogood-triggered heuristic,inspired by dynamic backtracking, was found to outperform static order ABT by a large factor in run-time and improve the network load. A further investigation of this successful heuristic shows the relation between it and the Min-Domain property. This relation was brought to an extreme in a later study in which a Retroactive ordering heuristic improved the run of both distributed and centralized algorithms. The improvement on structured realistic problems was much larger than on random problems.