View in EDS

Computing and restoring global inverse consistency in interactive constraint satisfaction.

Saved in:
Bibliographic Details
Title: Computing and restoring global inverse consistency in interactive constraint satisfaction.
Authors: Bessiere, Christian1 bessiere@lirmm.fr, Fargier, Hélène2 fargier@irit.fr, Lecoutre, Christophe3 lecoutre@cril.fr
Source: Artificial Intelligence. Dec2016, Vol. 241, p153-169. 17p.
Subjects: Computer systems, Problem solving, Algorithms, Design, Combinatorial designs & configurations
Abstract: Some applications require the interactive resolution of a constraint problem by a human user. In such cases, it is highly desirable that the person who interactively solves the problem is not given the choice to select values that do not lead to solutions. We call this property global inverse consistency . Existing systems simulate this either by maintaining arc consistency after each assignment performed by the user or by compiling offline the problem as a multi-valued decision diagram. In this article, we define several questions related to global inverse consistency and analyze their complexity. Despite their theoretical intractability, we propose several algorithms for enforcing and restoring global inverse consistency and we show that the best version is efficient enough to be used in an interactive setting on several configuration and design problems. [ABSTRACT FROM AUTHOR]
Copyright of Artificial Intelligence is the property of Elsevier B.V. and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)
Database: Engineering Source
FullText Text:
  Availability: 0
Header DbId: egs
DbLabel: Engineering Source
An: 118898402
AccessLevel: 6
PubType: Academic Journal
PubTypeId: academicJournal
PreciseRelevancyScore: 0
IllustrationInfo
Items – Name: Title
  Label: Title
  Group: Ti
  Data: Computing and restoring global inverse consistency in interactive constraint satisfaction.
– Name: Author
  Label: Authors
  Group: Au
  Data: <searchLink fieldCode="AR" term="%22Bessiere%2C+Christian%22">Bessiere, Christian</searchLink><relatesTo>1</relatesTo><i> bessiere@lirmm.fr</i><br /><searchLink fieldCode="AR" term="%22Fargier%2C+Hélène%22">Fargier, Hélène</searchLink><relatesTo>2</relatesTo><i> fargier@irit.fr</i><br /><searchLink fieldCode="AR" term="%22Lecoutre%2C+Christophe%22">Lecoutre, Christophe</searchLink><relatesTo>3</relatesTo><i> lecoutre@cril.fr</i>
– Name: TitleSource
  Label: Source
  Group: Src
  Data: <searchLink fieldCode="JN" term="%22Artificial+Intelligence%22">Artificial Intelligence</searchLink>. Dec2016, Vol. 241, p153-169. 17p.
– Name: Subject
  Label: Subjects
  Group: Su
  Data: <searchLink fieldCode="DE" term="%22Computer+systems%22">Computer systems</searchLink><br /><searchLink fieldCode="DE" term="%22Problem+solving%22">Problem solving</searchLink><br /><searchLink fieldCode="DE" term="%22Algorithms%22">Algorithms</searchLink><br /><searchLink fieldCode="DE" term="%22Design%22">Design</searchLink><br /><searchLink fieldCode="DE" term="%22Combinatorial+designs+%26+configurations%22">Combinatorial designs & configurations</searchLink>
– Name: Abstract
  Label: Abstract
  Group: Ab
  Data: Some applications require the interactive resolution of a constraint problem by a human user. In such cases, it is highly desirable that the person who interactively solves the problem is not given the choice to select values that do not lead to solutions. We call this property global inverse consistency . Existing systems simulate this either by maintaining arc consistency after each assignment performed by the user or by compiling offline the problem as a multi-valued decision diagram. In this article, we define several questions related to global inverse consistency and analyze their complexity. Despite their theoretical intractability, we propose several algorithms for enforcing and restoring global inverse consistency and we show that the best version is efficient enough to be used in an interactive setting on several configuration and design problems. [ABSTRACT FROM AUTHOR]
– Name: AbstractSuppliedCopyright
  Label:
  Group: Ab
  Data: <i>Copyright of Artificial Intelligence is the property of Elsevier B.V. and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract.</i> (Copyright applies to all Abstracts.)
PLink https://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=egs&AN=118898402
RecordInfo BibRecord:
  BibEntity:
    Identifiers:
      – Type: doi
        Value: 10.1016/j.artint.2016.09.001
    Languages:
      – Code: eng
        Text: English
    PhysicalDescription:
      Pagination:
        PageCount: 17
        StartPage: 153
    Subjects:
      – SubjectFull: Computer systems
        Type: general
      – SubjectFull: Problem solving
        Type: general
      – SubjectFull: Algorithms
        Type: general
      – SubjectFull: Design
        Type: general
      – SubjectFull: Combinatorial designs & configurations
        Type: general
    Titles:
      – TitleFull: Computing and restoring global inverse consistency in interactive constraint satisfaction.
        Type: main
  BibRelationships:
    HasContributorRelationships:
      – PersonEntity:
          Name:
            NameFull: Bessiere, Christian
      – PersonEntity:
          Name:
            NameFull: Fargier, Hélène
      – PersonEntity:
          Name:
            NameFull: Lecoutre, Christophe
    IsPartOfRelationships:
      – BibEntity:
          Dates:
            – D: 01
              M: 12
              Text: Dec2016
              Type: published
              Y: 2016
          Identifiers:
            – Type: issn-print
              Value: 00043702
          Numbering:
            – Type: volume
              Value: 241
          Titles:
            – TitleFull: Artificial Intelligence
              Type: main
ResultId 1