Framework for Modeling Reordering Heuristics for Asynchronous Backtracking

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 [A. Armstrong and E.F. Durfee, 1997], using a solution based on synchronization points. [M.-C. Silaghi et al., 2001] 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 [M.-C. Silaghi et al., 2001]. The most efficient self-reordering heuristic that we introduce and experiment, approx-AWCl, is inspired from Asynchronous Weak-Commitment [M. Yokoo et al., 1998 ] and brings small but significant improvements, comparable to the results in [A. Armstrong and E.F. Durfee, 1997]. 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).