oru.sePublications
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
A Lazy Algorithm to Efficiently Approximate Singleton Path Consistency for Qualitative Constraint Networks
Örebro University, School of Science and Technology. (AASS)ORCID iD: 0000-0001-7562-2443
CRIL-CNRS UMR, Universite D'Artois, Lens, France.
CRIL-CNRS UMR, Universite D'Artois, Lens, France.
2017 (English)In: 2017 IEEE 29th International Conference on Tools with Artificial Intelligence (ICTAI), Institute of Electrical and Electronics Engineers (IEEE), 2017, p. 110-117Conference paper, Published paper (Refereed)
Abstract [en]

Partial singleton (weak) path consistency, or partial lozenge-consistency, for a qualitative constraint network, ensures that the process of instantiating any constraint of that network with any of its base relations b and enforcing partial (weak) path consistency, or partial lozenge-consistency, in the updated network, yields a partially lozenge-consistent subnetwork where the respective constraint is still defined by b. This local consistency is essential for helping to decide the satisfiability of challenging qualitative constraint networks and has been shown to play a crucial role in tackling more demanding problems associated with a given qualitative constraint network, such as the problem of minimal labeling. One of the main downsides to using partial lozenge-consistency, is that it is computationally expensive to enforce in a given qualitative constraint network, as, despite being a local consistency in principle, it retains a global scope of the network at hand. In this paper, we propose a lazy algorithm that restricts the singleton checks associated with partial lozenge-consistency to constraints that are likely to lead to the removal of a base relation upon their propagation. A key feature of this algorithm is that it collectively eliminates certain unfeasible base relations by exploiting singleton checks. Further, we show that the closure that is obtained by our algorithm is incomparable to the one that is entailed by partial lozenge-consistency and non-unique in general. We demonstrate the efficiency of our algorithm via an experimental evaluation with random Interval Algebra networks from the phase transition region of two separate models and, moreover, show that it can exhibit very similar pruning capability for such networks to the one of an algorithm for enforcing partial lozenge-consistency.

Place, publisher, year, edition, pages
Institute of Electrical and Electronics Engineers (IEEE), 2017. p. 110-117
Series
Proceedings - International Conference on Tools With Artificial Intelligence, ISSN 1082-3409, E-ISSN 2375-0197
Keywords [en]
Qualitative constraint-based reasoning, spatial and temporal relations, partial lozenge-consistency, approximation
National Category
Computer Sciences
Identifiers
URN: urn:nbn:se:oru:diva-68109DOI: 10.1109/ICTAI.2017.00028ISI: 000435294700017Scopus ID: 2-s2.0-85048502743ISBN: 978-1-5386-3876-7 (electronic)ISBN: 978-1-5386-3877-4 (print)OAI: oai:DiVA.org:oru-68109DiVA, id: diva2:1235214
Conference
IEEE 29th International Conference on Tools with Artificial Intelligence (ICTAI), NOV 06-08, 2017, Boston, MA
Available from: 2018-07-24 Created: 2018-07-24 Last updated: 2018-09-12Bibliographically approved

Open Access in DiVA

No full text in DiVA

Other links

Publisher's full textScopus

Authority records BETA

Sioutis, Michael

Search in DiVA

By author/editor
Sioutis, Michael
By organisation
School of Science and Technology
Computer Sciences

Search outside of DiVA

GoogleGoogle Scholar

doi
isbn
urn-nbn

Altmetric score

doi
isbn
urn-nbn
Total: 28 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf