Lazy Repairing Backtracking for Dynamic Constraint Satisfaction Problems

Abstract

Extended Partial Dynamic Backtracking (EPDB) is a repair algorithm based on PDB. It deals with Dynamic CSPs based on ordering heuristics and retroactive data structures, safety conditions, and nogoods which are saved during the search process. In this paper, we show that the drawback of both EPDB and PDB is the exhaustive verification of orders, saved in safety conditions and nogoods, between variables. This verification affects remarkably search time, especially since orders are often indirectly deduced. Therefore, we propose a new approach for dynamically changing environments, the Lazy Repairing Backtracking (LRB), which is a fast version of EPDB insofar as it deduces orders directly through the used ordering heuristic. We evaluate LRB on various kinds of problems, and compare it, on the one hand, with EPDB to show its effectiveness compared to this approach, and, on the other hand, with MAC-2001 in order to conclude, from what perturbation rate resolving a DCSP with an efficient approach can be more advantageous than repair.