Abstract
We introduce and study a notion of robustness in
Qualitative Constraint Networks (QCNs), which
are typically used to represent and reason about
abstract spatial and temporal information. In
particular, given a QCN, we are interested in obtaining
a robust qualitative solution, or, a robust scenario of
it, which is a satisfiable scenario that has a higher
perturbation tolerance than any other, or, in other
words, a satisfiable scenario that has more chances
than any other to remain valid after it is altered.
This challenging problem requires to consider the
entire set of satisfiable scenarios of a QCN, whose
size is usually exponential in the number of constraints
of that QCN; however, we present a first algorithm
that is able to compute a robust scenario of a QCN
using linear space in the number of constraints.
Preliminary results with a dataset from the
job-shop scheduling domain, and a standard one,
show the interest of our approach and highlight the
fact that not all solutions are created equal.
Keywords
- Knowledge Representation and Reasoning: Qualitative, Geometric, Spatial, Temporal Reasoning
