Publication: Research - peer-review › Article in proceedings – Annual report year: 2010
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.
|Title of host publication||Proceedings of the Fifth European Starting AI Researcher Symposium (STAIRS 2010)|
|State||Published - 2010|
|Event||European Starting AI Researcher Symposium - Lisbon, Portugal|
|Conference||European Starting AI Researcher Symposium|
|Period||01/01/2010 → …|
- Simple Tabular Reduction, Arc consistency, Table constraints, Dynamic Constraint Satisfaction Problems