Dynamic
Ordering for Asynchronous Backtracking on DisCSPs
Roie Zivan
and Amnon Meisels
Abstract
An algorithm that performs asynchronous backtracking on distributed
CSPs, with dynamic ordering of agents is proposed, ABT DO. Agents
propose reorderings of lower priority agents and send these proposals
whenever they send assignment messages. Changes of ordering triggers a
different computation of Nogoods. The dynamic ordered asynchronous
backtracking algorithm uses polynomial space, similarly to standard
ABT. The ABT DO algorithm with three different ordering heuristics is
compared to standard ABT on randomly generated DisCSPs. A
Nogood-triggered heuristic, inspired by dynamic backtracking, is found
to outperform static order ABT by a large factor in run-time and
improve the network load.