Maintaining Arc Consistency in Non-Binary Dynamic CSPs using Simple Tabular Reduction

Constraint Satisfaction Problems (CSPs) are well known models used in Artificial Intelligence. In order to represent real world systems, CSPs have been extended to Dynamic CSPs (DCSPs), which support adding and removing constraints at runtime. Some approaches to the NP-complete problem of solving CSPs use filtering techniques such as arc consistency, which also have been adapted to handle DCSPs with binary constraints.

However, there exists only one algorithm targeting non-binary DCSPs (DnGAC4). In this paper we present a new algorithm DnSTR for maintaining arc consistency in DCSPs with non-binary constraints. Our algorithm is based on Simple Tabular Reduction for Table Constraints, a technique that dynamically maintains the tables of supports within the constraints.

Initial results show that our algorithm outperforms DnGAC4 both for addition and removal of constraints.