Dynamic reordering of variables is known to be important for solving constraint satisfaction problems (CSPs). Efforts to apply this principle for improving polynomial space asynchronous backtracking (ABT) started with [1], using a solution based on synchronization points. [17] shows how to asynchronously enable reordering heuristics in ABT and proposes a general protocol called Asynchronous Backtracking with Reordering (ABTR).

In this work we introduce a first framework for modeling heuristics possible with asynchronous backtracking. We also show that ABTR enables heuristics that displace even the agent requesting the reordering, as in the reordering of Dynamic Backtracking. They have not been illustrated in [17]. The most efficient self-reordering heuristic that we introduce and experiment, approx-AWC1, is inspired from AsynchronousWeak-Commitment [21] and brings small but significant improvements, comparable to the results in [1]. We also report that min-domain dynamic ordering heuristics for ABTR are worse than no reordering and better than max-domain (in experiments that also use maintenance of arc consistency).