Dynamic Ordering for Asynchronous Backtracking on DisCSPs Academic Article uri icon

abstract

  • An algorithm that performs asynchronous backtracking on distributed CSPsCSPs , with dynamic ordering of agents is proposed, ABT_DOABT\_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 NogoodsNogoods . The dynamic ordered asynchronous backtracking algorithm uses polynomial space, similarly to standard ABTABT . The ABT_DOABT\_DO algorithm with three different ordering heuristics is compared to standard ABTABT on randomly generated DisCSPsDisCSPs . A Nogood-triggered heuristic, inspired by dynamic backtracking, is found to outperform static order ABTABT by a large factor in run-time and improve the network load.

publication date

  • January 1, 2006