On robust vs fast solving of qualitative constraints

Jan Wehner (), Michael Sioutis () and Diedrich Wolter ()
Additional contact information
Jan Wehner: Delft University of Technology
Michael Sioutis: University of Montpellier
Diedrich Wolter: University of Bamberg

Journal of Heuristics, 2023, vol. 29, issue 4, No 3, 485 pages

Abstract: Abstract Qualitative Constraint Networks ( $$\textsf{QCN}$$ QCN s) comprise a Symbolic AI framework for representing and reasoning about spatial and temporal information via the use of natural disjunctive qualitative relations, e.g., a constraint can be of the form “Task A is scheduled after or during Task C”. In qualitative constraint-based reasoning, the state-of-the-art approach to tackle a given $$\textsf{QCN}$$ QCN consists in employing a backtracking algorithm, where the branching decisions during search and the refinement of the $$\textsf{QCN}$$ QCN are governed by certain heuristics that have been proposed in the literature. Although there has been plenty of research on how these heuristics compare and behave in terms of checking the satisfiability of a $$\textsf{QCN}$$ QCN fast, to the best of our knowledge there has not been any study on how they compare and behave in terms of obtaining a tractable refinement of a $$\textsf{QCN}$$ QCN that is also robust. In brief, a robust refinement of a $$\textsf{QCN}$$ QCN can be primarily seen as one that retains as many qualitative solutions as possible, e.g., the configuration “Task A is scheduled after or during Task C” is more robust than “Task A is scheduled after Task C”. Here, we make such a preliminary comparison and evaluation with respect to prominent heuristics in the literature, and reveal that there exists a trade-off between fast and robust solving of $$\textsf{QCN}$$ QCN s for datasets consisting of instances of Allen’s Interval Algebra and Region Connection Calculus. Furthermore, we investigate reasons for the existence of this trade-off and find that more aggressive heuristics are more efficient at the cost of producing less robust refinements.

Keywords: Qualitative constraints; Spatial and temporal reasoning; Robust refinement; Trade-off (search for similar items in EconPapers)
Date: 2023
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10732-023-09517-8 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:joheur:v:29:y:2023:i:4:d:10.1007_s10732-023-09517-8

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10732

DOI: 10.1007/s10732-023-09517-8

Access Statistics for this article

Journal of Heuristics is currently edited by Manuel Laguna

More articles in Journal of Heuristics from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().