-
Qualitative Spatio-Temporal Reasoning (QSTR) is a rich sym- inaccurate classifiers. As illustration, timetabling is an instance
bolic AI framework that deals with representing and reasoning of scheduling where inconsistencies can naturally form due to
about abstract, qualitative, spatio-temporal information via the lack of resources for certain tasks, among other reasons. In
human-like natural language descriptions [
2
]; as an example, the context of a hospital, for example, an inconsistency can
occonsider a relation of the form {is north of ∨ is east of} , cur when two surgeons are allocated the same operating room
which abstracts from numerical information and yet is very in- in overlapping temporal intervals; the inconsistency must then
tuitive. Such QSTR descriptions or relations, and disjunctions be repaired by considering available temporal intervals and
thereof, can be modeled as a qualitative constraint network preferences alike, and minimizing changes so as to perturb the
(QCN), a simplified example of which is provided in Figure 1a. structure of the timetable as little as possible. In the broader
The QSTR literature has been deeply invested in point/interval- context of neuro-symbolic AI architectures [
8
], classifiers may
based calculi, with Allen’s Interval Algebra being the most construct inconsistent spatio-temporal KBs due to inaccurate
representative example [
3
], as intervals can be used to rep- predictions, and minimizing inconsistency (i.e., maximizing
resent and reason about anything from durative actions in satisfiability) is an essential step of logical reasoning in the
planning or tasks in robotics [
4
] to temporal abstractions in neuro-symbolic cycle, see, e.g., Figure 1 in [
9
].
multivariate time series classification [
5
], among other appli- State of the Art & Contribution: The state of the art in solving
cations; see also [
6
]. the MAX-QCN problem with respect to constraints and SAT
encodings consists of the works in [
7
] and in [
10
], respectively.
task task Specifically, both of these approaches try to obtain a
refinement of the input QCN that maximizes the number of satisfied
before before ∨ equals before before constraints in the QCN. In doing so, they are trying to solve
task after task task before task itnwgoapsrcoebnlaermios oofftdhieferQeCntNn, awtuhrilestaetntshuerisnagmtehattimthee: eexxttrraacctte-d
(a) An inconsistent plan as a (b) An optimal scenario of the scenario is optimal. This is particularly crippling for the
persimplified QCN. simplified QCN. formance of the constraint-based approach in [
7
], as, should
the constraint not be part of an optimal scenario in the end,
Figure 1: The qualitative constraint network (QCN) in Fig- taking a refinement of it in the beginning might create a huge
ure 1a is inconsistent, and one solution of the MAX-QCN branch in the search tree that is useless to explore. The clause
problem [
7
], viz., an optimal scenario, is shown in Figure 1b, learning of the SAT-based approach in [
10
] circumvents this
with one unsatisfied constraint. issue, but, on the other hand, [
10
] does not exploit
tractability properties for QCNs, viz., Horn theories and/or maximal
Context & Motivation: In [
1
], we focus on the problem of tractable subsets of relations [
11
]; nevertheless, it significantly
maximizing satisfiability in a qualitative constraint network, outperforms [
7
]. In [
1
], with respect to the previous discussion,
formally called the MAX-QCN problem [
7
]. Specifically, given we provide a greedy constraint-based approach for tackling
a QCN , the MAX-QCN problem is the problem of obtaining the MAX-QCN problem that treats the constraints of the input
a spatial or temporal configuration that maximizes the number QCN in whole and, hence, may avoid—to a relatively greater
of satisfied constraints in ; see also Figure 1 for an exam- extent—redundant exploration of search space. Specifically, the
ple. The motivation behind studying this problem lies in the greedy technique consists in adding the original constraints
fact that representing spatial or temporal information may in- of a QCN to a new, initially empty, network, one by one, all
evitably lead to inconsistencies, due to e.g. human error and/or the while filtering out the ones that fail the satisfiability check.
What makes or breaks this technique is the ordering in which
the constraints will be processed to saturate the empty QCN,
and for that purpose we use many diferent strategies to form
a portfolio-style implementation. Then, we experimentally
compare this approach against one of the most compact to
date Partial MaxSAT encodings for the MAX-QCN problem,
which builds upon [
12, 13
], and comment on the trade-of
between optimality and eficiency, making our source code freely
available.
ENIGMA-23, September 03–04, 2023, Rhodes, Greece
⋆ This is an extended abstract of the homonymous TIME 2023
paper [
1
]. The work was partially funded by the Agence Nationale
de la Recherche (ANR) for the “Hybrid AI” project that is tied to
the chair of Dr. Sioutis, and the I-SITE program of excellence of
Université de Montpellier that complements the ANR funding.
$ michael.sioutis@lirmm.fr (M. Sioutis)
https://msioutis.gitlab.io/ (M. Sioutis)
0000-0001-7562-2443 (M. Sioutis)
© 2023 Copyright for this paper by its authors. Use permitted under Creative Commons License
CPWrEooUrckReshdoinpgs IhStpN:/c1e6u1r3-w-0s.o7r3g ACttEribUutRion W4.0oInrtekrnsahtioonpal (PCCroBYce4.0e).dings (CEUR-WS.org)