Introduction
In many real-world applications, such as satellite scheduling or interactive layout design, problems are rarely static. These environments are characterized as Dynamic Constraint Satisfaction Problems (DCSPs), where constraints and variables evolve over time. Traditional AI solvers typically treat these as fresh problems, recalculating solutions from scratch whenever a change occurs. This approach is often inefficient, wasting computational effort on previously solved sub-problems, and leads to solution instability—where minor constraint changes result in radically different, "jumpy" solutions that frustrate human users.
This paper introduces the Local Changes (lc) algorithm, a systematic repair method designed to reuse previous solutions effectively. Unlike stochastic local search methods, lc is complete, meaning it is guaranteed to find a valid solution if one exists or prove that the problem is unsolvable.
The Local Changes (lc) Algorithm
The lc algorithm operates on the principle of local repair with a systematic twist. It begins with an existing assignment that has become invalid due to constraint changes. The algorithm identifies variables violating constraints and attempts to reassign them.
To maintain completeness, the algorithm employs a recursive reassignment strategy. If reassigning variable $A$ creates a conflict with variable $B$, $B$ is unassigned, and the algorithm recursively seeks a new value for $B$ without altering $A$. This "sliding tile" intuition ensures that progress is made systematically. Furthermore, lc can be integrated with standard CSP enhancements such as Forward Checking (lc-fc) to prune search spaces and Nogood Recording to prevent redundant explorations of failed assignments.
Experimental Methodology
The authors benchmarked lc against three primary competitors: standard Backtracking (bt), Dynamic Backtracking (dbt), and Heuristic Repair (hrp). The evaluation utilized randomly generated binary CSPs with the following parameters:
- Scale: 15 variables with domain sizes between 6 and 16.
- Variables: Connectivity (the density of constraints) and tightness (the restrictiveness of constraints) were varied to explore different problem topographies.
- Dynamics: Changes were simulated by adding or removing between 1% and 32% of total constraints.
Results and Discussion
The performance of the algorithms was measured by the number of constraint checks required to find a new solution. The results indicate that the optimal algorithm choice is highly dependent on problem tightness and connectivity.
As shown in the experimental data, lc (particularly the lc-fc variant) excels in highly constrained problems, often reducing the computational burden by orders of magnitude compared to solving from scratch. In contrast, simple heuristic repair (hrp) is often sufficient for loosely constrained problems where solutions are abundant. Dynamic backtracking (dbt) remains a strong contender in the "middle ground" of the phase transition.
Interestingly, while lc was designed to improve solution stability, the authors found that most systematic algorithms produced solutions at similar distances from the original. The primary advantage of lc is therefore its efficiency in specific high-tightness zones rather than a unique ability to minimize solution shift.
Conclusion and Future Work
The lc algorithm bridges the gap between efficient local repair and rigorous systematic search. By providing a complete method for solution reuse, it offers a significant performance boost for dynamic environments.
Future research directions include scaling the algorithm to modern CSP benchmarks involving thousands of variables and exploring more sophisticated heuristics for variable unassignment. While the current study focused on binary constraints, the theoretical framework of lc supports $n$-ary constraints, suggesting broader applicability in complex scheduling and configuration tasks.
Summary updated