An Improved Algorithm for Maintaining Arc Consistency in Dynamic Constraint Satisfaction Problems

All Papers

Real world is dynamic in its nature, so techniques attempting to model the real world should take this dynamicity in consideration. A well known Constraint Satisfaction Problem (CSP) can be extended this way to a so called Dynamic Constraint Satisfaction Problem (DynCSP) that supports adding and removing constraints in runtime. As Arc Consistency is one of the major techniques in solving CSPs, its dynamic version is of a particular interest for DynCSPs. This paper presents an improved version of AC|DC-2 algorithm for maintaining maximal arc consistency after constraint retraction. This improvement leads to runtimes better than the so far fastest dynamic arc consistency algorithm DnAC-6 while keeping low memory consumption. Moreover, the proposed algorithm is open in the sense of using either non-optimal AC-3 algorithm keeping a minimal memory consumption or optimal AC-3.1 algorithm improving runtime for constraint addition but increasing a memory consumption.