On robust vs fast solving of qualitative constraints.

Qualitative Constraint Networks (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 QCN consists in employing a backtracking algorithm, where the branching decisions during search and the refinement of the 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 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 QCN that is also robust. In brief, a robust refinement of a 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 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. [ABSTRACT FROM AUTHOR]