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

Matthieu Stéphane Benoit Queva; Christian W. Probst; Laurent Ricci

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

Matthieu Stéphane Benoit Queva, Christian W. Probst, Laurent Ricci

Microsoft Development Center Copenhagen

Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

Abstract

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 language	English
Title of host publication	Proceedings of the Fifth European Starting AI Researcher Symposium (STAIRS 2010)
Publication date	2010
Publication status	Published - 2010
Event	Fifth European Starting AI Researcher Symposium - Lisbon, Portugal Duration: 16 Aug 2010 → 20 Aug 2010 Conference number: 5

Conference

Conference	Fifth European Starting AI Researcher Symposium
Number	5
Country/Territory	Portugal
City	Lisbon
Period	16/08/2010 → 20/08/2010

Keywords

Simple Tabular Reduction
Arc consistency
Table constraints
Dynamic Constraint Satisfaction Problems

OpenUrl availability

Full text

Cite this

@inproceedings{05ea1bc903774d6f9b9dddb495b243a2,

title = "Maintaining Arc Consistency in Non-Binary Dynamic CSPs using Simple Tabular Reduction",

abstract = "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.",

keywords = "Simple Tabular Reduction, Arc consistency, Table constraints, Dynamic Constraint Satisfaction Problems",

author = "Queva, {Matthieu St{\'e}phane Benoit} and Probst, {Christian W.} and Laurent Ricci",

year = "2010",

language = "English",

booktitle = "Proceedings of the Fifth European Starting AI Researcher Symposium (STAIRS 2010)",

note = "Fifth European Starting AI Researcher Symposium, STAIRS ; Conference date: 16-08-2010 Through 20-08-2010",

}

TY - GEN

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

AU - Queva, Matthieu Stéphane Benoit

AU - Probst, Christian W.

AU - Ricci, Laurent

N1 - Conference code: 5

PY - 2010

Y1 - 2010

N2 - 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.

AB - 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.

KW - Simple Tabular Reduction

KW - Arc consistency

KW - Table constraints

KW - Dynamic Constraint Satisfaction Problems

M3 - Article in proceedings

BT - Proceedings of the Fifth European Starting AI Researcher Symposium (STAIRS 2010)

T2 - Fifth European Starting AI Researcher Symposium

Y2 - 16 August 2010 through 20 August 2010

ER -

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

Abstract

Conference

Keywords

OpenUrl availability

Fingerprint

Cite this