To Örebro University

oru.seÖrebro University Publications
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • 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
Leveraging Variable Elimination for Efficiently Reasoning about Qualitative Constraints
Örebro University, School of Science and Technology. (AASS)ORCID iD: 0000-0001-7562-2443
Southwest Jiaotong University, Chengdu, China.
Quantum Computation and Intelligent Systems (QSI), University of Technology Sydney, Sydney, Australia.
2018 (English)In: International journal on artificial intelligence tools, ISSN 0218-2130, Vol. 27, no 4, article id 1860001Article in journal (Refereed) Published
Abstract [en]

We introduce, study, and evaluate a novel algorithm in the context of qualitative constraint-based spatial and temporal reasoning that is based on the idea of variable elimination, a simple and general exact inference approach in probabilistic graphical models. Given a qualitative constraint network N, our algorithm utilizes a particular directional local consistency, which we denote by (sic)-consistency, in order to efficiently decide the satisfiability of N. Our discussion is restricted to distributive subclasses of relations, i.e., sets of relations closed under converse, intersection, and weak composition and for which weak composition distributes over non-empty intersections for all of their relations. We demonstrate that enforcing (sic)-consistency in a given qualitative constraint network defined over a distributive subclass of relations allows us to decide its satisfiability, and obtain similar useful results for the problems of minimal labelling and redundancy. Further, we present a generic method that allows extracting a scenario from a satisfiable network, i.e., an atomic satisfiable subnetwork of that network, in a very simple and effective manner. The experimentation that we have conducted with random and real-world qualitative constraint networks defined over a distributive subclass of relations of the Region Connection Calculus and the Interval Algebra, shows that our approach exhibits unparalleled performance against state-of-the-art approaches for checking the satisfiability of such constraint networks.

Place, publisher, year, edition, pages
World Scientific Publishing Co. Pte Ltd , 2018. Vol. 27, no 4, article id 1860001
National Category
Computer Sciences
Identifiers
URN: urn:nbn:se:oru:diva-68153DOI: 10.1142/S0218213018600011ISI: 000436422400002Scopus ID: 2-s2.0-85049173315OAI: oai:DiVA.org:oru-68153DiVA, id: diva2:1235527
Note

Funding Agency:

MoveCare project - European Commission  732158

Available from: 2018-07-26 Created: 2018-07-26 Last updated: 2018-09-16Bibliographically approved

Open Access in DiVA

No full text in DiVA

Other links

Publisher's full textScopus

Authority records

Sioutis, Michael

Search in DiVA

By author/editor
Sioutis, Michael
By organisation
School of Science and Technology
In the same journal
International journal on artificial intelligence tools
Computer Sciences

Search outside of DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric score

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

Direct link
Cite
Citation style
  • apa
  • 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