Solving dynamic constraint satisfaction problems: Relations between problem alteration and search performance

This paper presents a new analysis of dynamic constraint satisfaction problems (DCSPs) and a new approach to solving them. We first show that even very small changes in a CSP, in the form of addition of constraints or changes in constraint relations, can have profound effects on search performance. These effects are reflected in the amenability of the problem to different forms of heuristic action and in the promise and fail-firstness of variable ordering heuristics applied to the problem. This may account for the poor performance of classical DCSP methods. We then show that the same changes do not markedly affect the locations of the major sources of contention in the problem. A technique, called "random probing", that performs a careful assessment of this property and uses the information during subsequent search, performs well even when it only uses information based on the original problem in the DCSP sequence. The result is a new approach to solving DCSPs that is based on a robust strategy for ordering variables rather than on robust solutions.