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

Publication: Research - peer-reviewArticle in proceedings – Annual report year: 2010

View graph of relations

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.
Original languageEnglish
Title of host publicationProceedings of the Fifth European Starting AI Researcher Symposium (STAIRS 2010)
Publication date2010
StatePublished - 2010
EventEuropean Starting AI Researcher Symposium - Lisbon, Portugal


ConferenceEuropean Starting AI Researcher Symposium
CityLisbon, Portugal
Period01/01/2010 → …


  • Simple Tabular Reduction, Arc consistency, Table constraints, Dynamic Constraint Satisfaction Problems
Download as:
Download as PDF
Select render style:
Download as HTML
Select render style:
Download as Word
Select render style:

ID: 5249666