Dynamic Ordering for Asynchronous Backtracking on DisCSPs

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