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

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

    Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-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 languageEnglish
    Title of host publicationProceedings of the Fifth European Starting AI Researcher Symposium (STAIRS 2010)
    Publication date2010
    Publication statusPublished - 2010
    EventEuropean Starting AI Researcher Symposium - Lisbon, Portugal
    Duration: 1 Jan 2010 → …
    Conference number: 5

    Conference

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

    Keywords

    • Simple Tabular Reduction
    • Arc consistency
    • Table constraints
    • Dynamic Constraint Satisfaction Problems

    Cite this

    Queva, M. S. B., Probst, C. W., & Ricci, L. (2010). Maintaining Arc Consistency in Non-Binary Dynamic CSPs using Simple Tabular Reduction. In Proceedings of the Fifth European Starting AI Researcher Symposium (STAIRS 2010)