<figure><img src="image_1.png" /></figure>

HAL
open science

Query-driven Qualitative Constraint Acquisition

Mohamed-Bachir Belaid, Nassim Belmecheri, Arnaud Gotlieb, Nadjib Lazaar, Helge Spieker

► To cite this version:

Mohamed-Bachir Belaid, Nassim Belmecheri, Arnaud Gotlieb, Nadjib Lazaar, Helge Spieker. Query-
driven Qualitative Constraint Acquisition. Journal of Artificial Intelligence Research, 2024, 79, pp.241-
271. 10.1613/jair.1.14752 . lirmm-04835853

HAL Id: lirmm-04835853

https://hal-lirmm.ccsd.cnrs.fr/lirmm-04835853v1

Submitted on 13 Dec 2024

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_2.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Query-driven Qualitative Constraint Acquisition

**Mohamed-Bachir Belaid**

NILU, Climate and environmental research institute, Kjeller, Norway.
Department of Computer Science, OsloMet, Oslo, Norway.

BBEL@NILU.NO

**Nassim Belmecheri**

Simula Research Laboratory, Oslo, Norway.

NASSIM@SIMULA.NO

**Arnaud Gotlieb**

Simula Research Laboratory, Oslo, Norway.

ARNAUD@SIMULA.NO

**Nadjib Lazaar**

LIRMM, University of Montpellier, CNRS, Montpellier, France.

LAZAAR@LIRMM.FR

**Helge Spieker**

Simula Research Laboratory, Oslo, Norway.

HELGE@SIMULA.NO

## Abstract

Many planning, scheduling or multi-dimensional packing problems involve the design of subtle logical combinations of temporal or spatial constraints. Recently, we introduced GEQCA-I, which stands for *Generic Qualitative Constraint Acquisition*, as a new active constraint acquisition method for learning qualitative constraints using *qualitative queries*. In this paper, we revise and extend GEQCA-I to GEQCA-II with a new type of query, *universal query*, for qualitative constraint acquisition, with a deeper query-driven acquisition algorithm. Our extended experimental evaluation shows the efficiency and usefulness of the concept of universal query in learning randomly-generated qualitative networks, including both temporal networks based on Allen's algebra and spatial networks based on region connection calculus. We also show the effectiveness of GEQCA-II in learning the qualitative part of real scheduling problems.

## 1. Introduction

Qualitative reasoning about time or space is essential for many practical Artificial Intelligence problems, such as automated planning (Belhadji & Isli, 1998), task scheduling (Barták, Salido, & Rossi, 2008), and multi-dimensional packing problems (Crainic, Perboli, & Tadei, 2012). In this context, qualitative calculus provides an algebraic framework that establishes relations between entities (or pairs of entities) through a language that is jointly exhaustive and pairwise disjoint. Examples of qualitative calculus include Point Algebra (Vilain & Kautz, 1986b) and Allen's Interval Algebra (Allen, 1983) for reasoning about temporal tasks, and Region Connection Calculus (RCC) (Randell, Cui, & Cohn, 1992) for reasoning about topological relationships between spatial regions. Constraint satisfaction techniques and constraint programming (CP) are well-suited frameworks to model and solve qualitative constraint networks.

However, in many practical situations, complex problems are not represented as constraint networks and are solved solely based on historical records and manually crafted
solutions. Furthermore, inter-relationships among entities may only be known locally and between pairs of entities, leaving the implications for other pairs of entities unknown.

To facilitate the modelling of CP problems, the concept of *constraint acquisition* (CA) was introduced for learning CP models. CA can be achieved through *passive learning* from a set of complete labelled example assignments (Bessiere, Coletta, Koriche, & O'Sullivan, 2005), or *active learning* with specific queries that aid in classifying complete assignments (Bessiere, Coletta, O'Sullivan, & Paulin, 2007).

Several state-of-the-art active CA algorithms exist, including: QUACQ (Bessiere, Coletta, Hebrard, Katsirelos, Lazaar, Narodytska, Quimper, & Walsh, 2013), an interactive query-based approach also known as *exact learning* (Bshouty, 2018), which asks complete or partial queries to reduce the set of possible satisfiable constraints from a given constraint language; MULTIACQ (Arcangioli, Bessiere, & Lazaar, 2016), an extension of QUACQ that learns the maximum number of constraints violated by a given negative example; T-QUACQ (Addi, Bessiere, Ezzahir, & Lazaar, 2018), which places a bound on the query-generation time to speed up CA; MQUACQ-2 (Tsouros, Stergiou, & Bessiere, 2019), which leverages the structure of learned models by focusing queries on quasi-cliques of constraints; and CLASSACQ (Prestwich, Freuder, O'Sullivan, & Browne, 2021), which utilizes a Naive Bayes classifier to differentiate solutions from non-solutions and acquire constraint models in a passive manner.

Other notable approaches for learning constraint models include ModelSeeker (Beldiceanu & Simonis, 2012, 2016), which can acquire global constraints, and the general frameworks of *constraint learning* (De Raedt, Passerini, & Reso, 2018) and *constraint synthesis*, which are based on mixed linear integer programming (Pawlak & Krawiec, 2017). The issue of handling incorrect responses to queries is also a significant challenge in interactive CA (Tsouros, Stergiou, & Bessiere, 2020).

However, standard active CA algorithms face difficulties in handling qualitative constraints since managing disjunctions of general relations over variable pairs can result in an exponential increase of the constraint search space.

Moreover, although the number of possible inter-relations is limited, controlling the number of queries asked to the user or the time allocated to generate these queries is a crucial aspect of the adoption of CA techniques in practical applications (Bessiere, Koriche, Lazaar, & O'Sullivan, 2017).

Learning qualitative temporal constraints has been initiated by (Mouhoub, Marri, & Alanazi, 2018) in LQCN. LQCN follows the active learning version of CONACQ by considering each qualitative constraint between time intervals as a concept to learn using *memory queries*. Then, the consistency of the network as a whole is maintained using path consistency and by considering the composition table as background knowledge. Further, LQCN was extended to the RCC8 algebra in (Mouhoub, Marri, & Alanazi, 2021) but its generalization to other algebras is not straightforward without further development and correctness proofs. In particular, understanding which fundamental property of an algebra is necessary to generalize CA to other qualitative reasoning is not easy. Also, using background knowledge beyond the only composition table can be beneficial, in cases more information about the network is available (e.g., task durations, resource limits, pre-crafted constraints). These elements are crucial to complete the constraint propagation step and further filter the queries to generate.
Recently, in (Belaid, Belmecheri, Gotlieb, Lazaar, & Spieker, 2022), we have introduced *Generic Qualitative Constraint Acquisition* coined as (GEQCA-I), which is a generic active CA algorithm for learning any kind of constraints between pairs of entities in a qualitative reasoning problem. GEQCA-I is a correct method in CA that acquires any kind of qualitative constraint network. It combines qualitative queries, time-bounded path consistency (PC), PATH-LEX, a novel search heuristic and extends background knowledge propagation to learn any qualitative constraint network. Our approach differs from classical active CA algorithms in three ways. First, it handles the disjunction of qualitative constraints effectively through the usage of queries and path consistency. Second, it generalizes the concept of CA for qualitative constraint networks by building its theoretical framework on the JEPD (Joint Exhaustive and Pairwise Disjoint) property. Third, it solves CP models to reduce the number of queries using extended background knowledge.

In this paper, our revision and extension of GEQCA-I to GEQCA-II are threefold:

1. We introduce a new type of query, *universal query*, motivated by real-world scenarios and revise GEQCA-I accordingly. We provide a sound and complete query-driven CA algorithm to propagate any information through path consistency. This paper contains a full theoretical analysis of GEQCA-II;

2. We propose another constraint selection heuristics, named PATH-WEIGHTED. We experimentally evaluate which constraint selection heuristics perform better for learning qualitative networks;

3. We provide an extended experimental evaluation of GEQCA-II on temporal and spatial qualitative networks, which answers four research questions related to the comparison between GEQCA-I and II. We also address qualitative networks extracted from real-world scheduling problems.

The paper is organized as follows: In the next section, we introduce the necessary background material required to understand the paper; In Section 3, we introduce the concept of *universal query* and present GEQCA-II, our generic approach to learning qualitative constraints in CA. In Section 4, we conduct experiments with our implementation of GEQCA-II to evaluate its effectiveness and performance. Finally, we conclude the paper in Section 5.

## 2. Background

### 2.1 Qualitative Calculus

A Qualitative Constraint Network (QCN) is a finite set of (binary) constraints $\mathcal{C}$ expressed on $X$, where $X$ is a finite set of variables representing temporal or spatial entities (points, intervals, regions, etc.). For instance, an *interval* variable $X_i$ is a pair of endpoints $(X_i^-, X_i^+)$ on the real line where $X_i^- < X_i^+$ holds.

A QCN is built on a language $\Gamma$, which stands for a finite set of *jointly exhaustive and pairwise disjoint* (JEPD) binary relations (e.g., *before*, *after*, *contains*, *part-of*, etc.) defined over an infinite domain $D$ (e.g., a topological space for Region Connection Calculus or a real line for Allen's Interval Algebra). The 13 basic relations (resp., the 8 basic relations) in
<figure><img src="image_3.png" /><figcaption>Figure 1: (a) Overview of the 13 basic relations in Allen's Interval Algebra (Allen, 1983) as named in Krokhin et al. (2003) and (b) the 8 basic relations in Region connection calculus. These relations resemble the possible temporal/spatial qualitative queries, the oracle is asked.</figcaption></figure>

Allen's Interval Algebra (resp., in RCC8) are illustrated in Figure 1.(a) (resp., Figure 1.(b)).

Formally speaking, $\Gamma = \{r_1, \dots, r_m\}$ and $|\Gamma| = m$. Bear in mind that the relational algebra generated by $\Gamma$ is finite, and it is closed under (weak) composition, converse and contains the identity. A binary constraint $C_{ij} = \{r_{k_1}, \dots, r_{k_d}\}$, is a disjunction of $d$ basic relations in $\Gamma$ between $X_i$ and $X_j$. Note that $C_{ji}$ represents the inverse constraint (with inverse relations) of $C_{ij}$ (i.e., $C_{ji} = C_{ij}^{-1}$). Here, $C_{ij}$ is interpreted as $(X_i r_{k_1} X_j) \vee \dots \vee (X_i r_{k_d} X_j)$ and $|C_{ij}| = d$. We denote by $\perp$ the *empty* constraint (i.e., the constraint defined by the empty set) and by $\top$ the *universal* constraint (i.e., the constraint defined by a set containing all basic relations of the calculus). $Size(C) = \sum_{(C_{ij} \in C | i < j)} |C_{ij}|$ denotes the total number of basic relations in $C$.

The QCN satisfiability problem is the problem of deciding if there exists a temporal/spatial solution (i.e., an interpretation of the variable entities satisfying all constraints) of a given QCN.

**Example 1.** Figure 2 illustrates a temporal QCN with $C_1$ using Allen's Interval Algebra, a spatial QCN with $C_2$ using RCC8 and for each of the two QCNs, a possible solution. In $C_1$, the constraint between the two intervals $X_1$ and $X_2$ is $C_{12} = \{\mathbf{p}, \mathbf{m}, \mathbf{o}\}$. The inverse of $C_{12}$
<figure><img src="image_4.png" /><figcaption>Figure 2: Illustrative examples of temporal QCN with $C_1$ and spatial QCN with $C_2$ and the corresponding possible solutions.</figcaption></figure>

is $C_{21} = \{\text{pi,mi,oi}\}$. The size of $C_1$ and $C_2$ is $\text{size}(C_1) = 25$ and $\text{size}(C_2) = 19$, where the universal constraint $\top$ is of size 13 (resp., 8) in Allen's algebra (resp., in RCC8).

## 2.2 Qualitative Constraint Acquisition

A CA-Agent is a constraint acquisition algorithm (a.k.a., learner or inducer in Machine Learning) defined to acquire constraints from data. In active learning, the CA-Agent needs to share some common knowledge, materialized by the vocabulary $(X, D)$ in our context, with an oracle to communicate through queries. An assignment $e$ on $X$ is rejected by a constraint network $C$ if and only if there is at least one constraint $C_{ij}$ which rejects $e_{ij} = (v_i, v_j)$, the projection of $e$ on $(X_i, X_j)$. $e_{ij}$ violates $C_{ij}$ iff for each $r_k \in C_{ij}$, $(v_i, v_j) \notin r_k$. If $(v_i, v_j)$ does not violate $C_{ij}$, then $(v_i, v_j) \models C_{ij}$. An assignment $e$ on $X$, which is accepted by $C$, is a **solution** of $C$. $\text{Sol}(C)$ denotes the set of solutions of $C$. In addition to the vocabulary $(X, D)$, the CA-Agent owns the language $\Gamma$ from which it can build constraints on specified sets of entity variables.

Given a vocabulary $(X, D)$, a **qualitative concept** is a Boolean function $f$ over $D^{|X|}$, i.e., a mapping of each complete assignment $e$ to a value in $\{\text{true, false}\}$. A **representation** of a
<figure><img src="image_5.png" /><figcaption>Figure 3: An example of two time intervals including background knowledge.</figcaption></figure>

qualitative concept *f* is a QCN, *C* for which $f^{-1}(true) = sol(C)$, denoted by $f = sol(C)$. The oracle qualitative concept is a concept $f_Q$ that returns *true* for *e* if and only if *e* is a solution to the problem that the oracle has in mind. The target network, denoted as *T*, is a QCN representing the concept $f_Q$. It is worth noting that $f_Q$ may correspond to an empty concept $f_Q = \emptyset$. In this case, any unsatisfiable QCN can serve as a candidate for representing the empty concept.

Oracles, teachers, or domain experts can serve as sources of information for learning, but they are not necessarily human-based oracles (Angluin, 1988; Valiant, 1984). The information that needs to be learned is assumed to be known by an oracle, which can be a program in some cases (Menguy, Bardin, Lazaar, & Gotlieb, 2022) or a crowd collectively answering queries (Lazaar, 2021). In many cases, this source of information is composed of multiple locally consistent pieces of knowledge that collectively form the concept to be learned, denoted as $f_Q$. However, this composed concept may not be entirely coherent and may not have a clear solution, resulting in an empty concept ($f_Q = \emptyset$). To represent the locally consistent part of the concept $f_Q$ for the pair $(X_i, X_j)$, we use the notation $f_Q[i, j]$.

We now define *convergence*, which is a crucial property of CA. Given a set *E* of examples labelled by the oracle as *true* or *false*, we say that a network *C* agrees to *E* if *C* accepts all examples labelled *true* and rejects all examples labelled *false*. The learning process has *converged* on the network *L* if (i) *L* agrees to *E* and (ii) for every other network *L'* agreeing to *E*, we have $sol(L') = sol(L)$. Hence, if the learning process has converged, we guarantee that $sol(L) = f_Q$. If there is no such *L* found, then we say that the learning process has *collapsed*. For instance, it happens when $f_Q$ is an empty concept (i.e., $f_Q = \emptyset$).

In practical applications, it happens that the structure of the problem is known, as well as some quantitative constraints, or some models of durative tasks/actions and their preconditions/effects. In CA, that information type can be presented as background knowledge, noted $\mathcal{K}$. From $\mathcal{K}$, we can deduce an extended qualitative knowledge $\mathcal{K}_Q$ by using constraint propagation or the resolution process. Hence, the concept to learn $f_Q$ is subsumed by $\mathcal{K}_Q$ (i.e., $f_Q \subseteq \mathcal{K}_Q$).
**Example 2.** Let us consider the example presented in Figure 3 under Allen's Interval Algebra. We have two time intervals $X_1$ and $X_2$, and background knowledge $K$ which states that (i) $X_1$ and $X_2$ have a duration of two and three time units each (ii) the schedule can take a maximum of four time units. From (i), we can deduce that $X_1$ cannot contain, be equal to, be started by, or be finished by $X_2$. From (ii), we can deduce that $X_1$ cannot precede, meet, be preceded by, or be met by $X_2$. What remains as basic relations between $X_1$ and $X_2$ represents the deduced qualitative knowledge:

$$K_Q : (C_{12} = \{o,d,s,f,oi\})$$

Note that standard version space-based approaches such as CONACQ (Bessiere et al., 2017) and QUACQ (Bessiere et al., 2013) are not suitable for qualitative reasoning, as (i) the acquisition is based on a finite domain and (ii) only languages closed under conjunction can be considered.

### 3. GEQCA-II: Constraint Acquisition via Qualitative Queries

We first recall the concept of the qualitative query introduced in (Belaid et al., 2022) and then, we introduce a new type of query, namely universal query. In the following, we make the hypothesis that GEQCA-II has access to a perfect oracle (human or program) that always answers queries correctly. We further discuss this hypothesis in 4.5.

**Definition 1 (Qualitative Query).** Given a qualitative concept $f_Q$ on $(X, D)$ under $\Gamma$, a qualitative query Q-ASK($X_i\{r\}X_j$) takes as input a constraint with a unique basic relation $r \in \Gamma$ on a pair of variables $(X_i, X_j)$, and outputs "yes" if $\exists e_{ij} \in r$ that satisfies $f_Q[i, j]$ and "no" otherwise.

Please note that the JEPD property guarantees that for any given pair of variables $(X_i, X_j)$, each possible value pair $(v_i, v_j)$ is contained in exactly one relation $r \in \Gamma$. As a result, we can infer that, when considering a pair of entity variables $(X_i, X_j)$ and a basic relation $r \in \Gamma$, a qualitative query answers the question of whether $X_i \{r\} X_j$ holds or not. It is worth noting that a positive response to the qualitative query Q-ASK($X_i, r, X_j$) does not necessarily imply that $e_{ij}$ can be extended to form a solution for the qualitative concept to be learned. The existence of such a solution cannot be guaranteed. In fact, determining whether $e_{ij}$ can be extended to a solution is an NP-complete problem (Vilain & Kautz, 1986a; Maddux, 1994).

In some practical scenarios, the oracle may provide information showing that a universal constraint exists between two entities, $X_i$ and $X_j$, something that allows any basic relation to hold between them. This gives rise to a new type of query called the universal query.

**Definition 2 (Universal Query).** Given a qualitative concept $f_Q$ on $(X, D)$ under $\Gamma$, a universal query U-ASK($X_i, X_j$) takes as input a pair of variables $(X_i, X_j)$, and outputs "yes" if $\forall r \in \Gamma : \exists e_{ij} \in r$ that satisfies $f_Q[i, j]$ and "no" otherwise.

Once again, by utilizing the JEPD property of $\Gamma$, a universal query can answer the question of whether all basic relations in $\Gamma$ hold between a pair of entity variables $(X_i, X_j)$, sequentially or otherwise. In other words, the universal query can determine whether all
possible basic relations between $X_i$ and $X_j$ are allowed. The concept of qualitative and universal queries in GEQCA-II can be explained and motivated by considering the following simple usage scenario.

**Example 3.** Consider a professional architect with experience in building modern-style houses. This architect is responsible for scheduling between 50 to 100 distinct construction tasks and wishes to acquire a general constraint model that can be used for any construction project. At the beginning of the process, the architect can answer "universal queries" to determine which tasks are independent<fnref n="1" /> from each other. For example, a positive response to the query U-ASK("carpentry", "build the walls") would validate all relations between "carpentry" and "build the walls", and there would be no need to ask qualitative queries between these two tasks. After that, "qualitative queries" can be used to detect the exact allowed relations between dependent tasks. For instance, if the architect positively answers the query Q-ASK("build the walls" {precedes} "put the roof"), this would validate the "precedes" relation between the task of "build the walls" and the task of "put the roof".

## 3.1 Description of GEQCA-II

GEQCA-II is presented in Algorithm 1. GEQCA-II takes as input a vocabulary $(X, D)$ of $n$ entity variables, the $\Gamma$ language of binary basic relations, a background knowledge $\mathcal{K}$ and a timed boundary parameter cutoff.

Initially, GEQCA-II sets the possible constraints between entities of the network $L$ to the universal constraint $\top$ (line 4). The value of $\tau$ is then assigned to cutoff in order to ensure that the waiting time between two queries does not exceed the time limit of cutoff. Subsequently, GEQCA-II iterates over $L$ to reduce the constraints to sets of basic relations that are equivalent to the concept being learned $f_Q$ (lines 6-18). To accomplish this, GEQCA-II first selects a $C_{ij}$ and, in the case of $C_{ij} = \top$, presents a universal query on $(X_i, X_j)$ to the oracle (line 7). If the universal query is answered positively, the universal constraint between $X_i$ and $X_j$ is retained.

If there is no universal constraint between $X_i$ and $X_j$, then at least one basic relation must be removed. To accomplish this, GEQCA-II performs two steps. First, the propagate procedure is applied to reduce $C_{ij}$ by propagating $\mathcal{K}$ on it in $\tau$ (line 8). For example, in a temporal context, if "$X_i$ and $X_j$ tasks have respective duration of 1 and 2 hours", which is deduced from $\mathcal{K}$, then the propagate procedure removes *Equals*, *Contains*, *Started-by*, and *Finished-by* from $C_{ij}$. The value of $\tau$ is then updated by deducting the time used in $\mathcal{K}$ propagation. Second, GEQCA-II iterates over the remaining basic relations of $C_{ij}$ (lines 10-16). Each basic relation $r$ is checked in $\tau$ to ensure its consistency with the already learned network $L$ and $\mathcal{K}$ (line 11). If the relation is not consistent, meaning that $\tau$ is sufficient to prove that there is no solution ($s = \emptyset$), it can be removed (line 14). Otherwise, the resolution finds a solution or $\tau$ is insufficient, and in both cases, the basic relation is presented to the oracle under a qualitative query Q-ASK($X_i, r, X_j$) (line 13). Finally, the value of $\tau$ is updated by deducting the time consumed by the solve process (line 12).

If the oracle answers no, then GEQCA-II removes $r$ from $C_{ij}$ (line 14). If $C_{ij}$ is reduced at line 8 or line 14, then GEQCA-II eliminates non-feasible relations from $L$ by maintaining path consistency using the PC function, with a time limit of $\tau$. If $C_{ij}$ is reduced to the empty

<footnote n="1">1. Independent from user perspective, but they can be indirectly dependent.</footnote>
<caption>**Algorithm 1:** GEQCA-II: Constraint Acquisition via Qualitative Queries.</caption>

1 In: vocabulary $(X, D)$; $\Gamma$ language; background knowledge $K$; parameter cutoff;
2 Out: a learned network $L$;
3 begin
4 &nbsp;&nbsp;&nbsp;&nbsp;$L \leftarrow \{C_{ij} = \top : i < j\}$;
5 &nbsp;&nbsp;&nbsp;&nbsp;$\tau \leftarrow$ cutoff;
6 &nbsp;&nbsp;&nbsp;&nbsp;foreach $C_{ij} \in L$ do
7 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if $(C_{ij} = \top) \land (\text{U-ASK}(X_i, X_j) = \text{yes})$ then continue;
8 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;CHANGE $\leftarrow \text{propagate}(K, C_{ij}, \tau)$
9 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;update($\tau$);
10 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;foreach $r \in C_{ij}$ do
11 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$s \leftarrow \text{solve}(L \cup K \cup X_i\{r\}X_j, \tau)$
12 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;update($\tau$);
13 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if $(s = \emptyset) \lor (\text{Q-ASK}(X_i\{r\}X_j) = \text{no})$ then
14 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$C_{ij} \leftarrow C_{ij} \setminus \{r\}$
15 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;CHANGE $\leftarrow$ true;
16 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if $s \neq \emptyset$ then $\tau \leftarrow$ cutoff;
17 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if $(C_{ij} = \bot) \lor (\text{CHANGE} \land \neg \text{PC}(\{C_{ij}\}, \tau))$ then
18 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;return "collapse"
19 Function PC$(Q, \tau)$:
20 &nbsp;&nbsp;&nbsp;&nbsp;while $(Q \neq \emptyset) \land (\tau$ has not yet elapsed$)$ do
21 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;pick $C_{ij}$ in $Q$
22 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;foreach $X_k \in X \setminus \{X_i, X_j\}$ do
23 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$\Delta_1 \leftarrow C_{ik} \cap \text{composition}(C_{ij}, C_{jk})$; if $\Delta_1 = \bot$ then return false
24 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$\Delta_2 \leftarrow C_{ki} \cap \text{composition}(C_{ki}, C_{ij})$; if $\Delta_2 = \bot$ then return false
25 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if $C_{ik} \neq \Delta_1$ then $C_{ik} \leftarrow \Delta_1$; $Q \leftarrow Q \cup \{C_{ik}\}$
26 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if $C_{kj} \neq \Delta_2$ then
27 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$C_{kj} \leftarrow \Delta_2$; $Q \leftarrow Q \cup \{C_{kj}\}$
28 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if $Q = \emptyset$ then update($\tau$);
29 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;return true
end
end

constraint $\perp$ in line 14, or if an inconsistency is detected by PC (lines 23 and 24), it shows that the space of possible networks collapses because of an empty concept ($f_Q = \emptyset$) (line 18). In lines 19-29, we present the PC function (Mackworth, 1977), which is a time-bounded path consistency incremental propagator with a cubic complexity in the number of entity variables. PC returns true when a fixpoint (transitive closure) is reached by propagating qualitative knowledge, or when $\tau$ has elapsed, and false when any inconsistency is detected.
## 3.2 Theoretical Analysis

In this section, we establish the correctness of the GEQCA-II algorithm (Algorithm 1) in learning any constraint network that represents a qualitative concept over the $\Gamma$ language. We prove that GEQCA-II is sound, complete, and terminates.

Let $(X, D)$ be a vocabulary of $n$ entity variables, $\Gamma$ be the set of basic relations, $f_Q$ be a qualitative concept, and let $\mathcal{K}_Q \supseteq f_Q$ be knowledge deduced by a given background knowledge $\mathcal{K}$, then the following propositions and Theorem 1 hold.

**Proposition 1 (Soundness).** *The network $L$ returned by GEQCA-II is such that $f_Q \subseteq \text{sol}(L)$.*

*Proof.* Suppose there exists an example $e \in f_Q$ that is not a solution of $L$, i.e., $e \not\models L$, then there must be at least one constraint $C_{ij} \in L$ for which the projection of the solution $e_{ij}$ does not satisfy $C_{ij}$, i.e., $e_{ij} \not\models C_{ij}$. This implies that there is a missing relation $r^*$ in $C_{ij}$ such that $e_{ij} \in r^*$. The missing relation $r^*$ is unique due to JEPD property of the $\Gamma$ language. Since the *propagate* procedure (line 8) and the consistency check (line 11) are based on a background knowledge that subsumes $f_Q$ ($\mathcal{K}_Q \supseteq f_Q$) and the *PC* function is sound (Allen, 1983; Vilain & Kautz, 1986a), the only place where $r^*$ can be removed from $C_{ij}$ is at line 14 due to a negative answer on a qualitative query. Furthermore, a qualitative query on a consistent relation between a given pair of entities cannot be answered with *no*. Therefore, removing a basic relation from $L$ cannot cause $L$ to reject an example accepted by $f_Q$. $\square$

The soundness property of GEQCA-II ensures that it generates a constraint network $L$ that preserves the solution of the target concept $f_Q(\text{sol}(L) \subseteq f_Q)$. Consequently, it avoids the removal of any basic relation that is part of a solution or could be extended to form one. Consider, for example, the set of basic relations $S = \{p, o, m\}$ between $X_i$ and $X_j$, representing relations participating in solutions of $f_Q$. The soundness property ensures the acquisition of a constraint $C_{ij}$ that wholly encompasses the set $S$ ($S \subseteq C_{ij}$, as illustrated by $C_{ij} = \{p, o, m, f, s\}$). Importantly, it guarantees that no constraint $C'_{ij}$ will be generated in a manner that $C'_{ij} \cap S \neq S$ (for instance, $C'_{ij} = \{o, m, s\}$).

**Proposition 2 (Completeness).** *The network $L$ returned by GEQCA-II is such that $\text{sol}(L) \subseteq f_Q$.*

*Proof.* Suppose there exists $e \in \text{sol}(L) \setminus f_Q$. Here, $L$ accepts solutions rejected by the concept $f_Q$, which means that at least one constraint $C_{ij} \in L$ needs to be restricted further to make $e \not\models L$. To restrict $C_{ij}$ further, we need to remove at least one relation $r^*$ from $C_{ij}$. If $C_{ij} = \top$, GEQCA-II submits a universal query to the oracle at line 7. The query is negatively answered as $r^* \in C_{ij}$. If $r^*$ is not removed using $\mathcal{K}$ propagation (lines 8 and 11) or using PC, it is presented to the oracle as a qualitative query. Since $r^*$ is inconsistent on $(X_i, X_j)$, the qualitative query on $r^*$ can only be negatively answered. Thus, we conclude that keeping a basic relation in $L$ cannot cause $L$ to accept an example rejected by $f_Q$. $\square$

The completeness property of GEQCA-II ensures that the resultant constraint network $L$ does not introduce new solutions concerning the target concept $f_Q$ (i.e., $\text{sol}(L) \subseteq f_Q$). For
example, if the basic relations between $X_i$ and $X_j$, forming part of the solutions of the target concept, are denoted as $\mathcal{S} = \{p, o, m\}$, the completeness property ensures the acquisition of a constraint $C_{ij}$ such that the basic relations in $C_{ij} \setminus \mathcal{S}$ are not part of the solutions of the target concept (e.g., $C_{ij} = \{p, o, s\}$ with $s$ representing a globally inconsistent relation between $X_i$ and $X_j$).

**Proposition 3 (Termination).** GEQCA-II terminates.

*Proof.* The GEQCA-II algorithm iterates over all pairs of entities, which results in $\frac{n(n-1)}{2}$ iterations (line 6). For each pair of entities, if a universal query is negatively answered in line 7, GEQCA-II iterates over the language $\Gamma$ (line 10). Since the size of the pair of entities and $\Gamma$ is finite, and the *propagate* and *solve* procedures as well as the PC function are time-bounded, the algorithm is guaranteed to terminate. $\square$

**Theorem 1 (Correctness).** *The network L returned by GEQCA-II is such that $sol(L) = f_Q$.*

*Proof.* Correctness immediately follows from Propositions 1, 2, and 3. $\square$

**Proposition 4 (Waiting time).** GEQCA-II learns a network *L*, or collapses, with a waiting time not exceeding cutoff time bound between two queries.

*Proof.* If cutoff = $\infty$, the proposition holds trivially. However, if cutoff < $\infty$, GEQCA-II asks a universal query at each iteration of its main loop (line 6). If the query is positively answered, GEQCA-II asks a new universal query with negligible time between the queries. If a universal query is negatively answered, GEQCA-II calls the *propagate* function (line 8) and enters the inner loop in line 10 by asking a series of qualitative queries. Between two queries, *propagate*, *solve*, and PC are executed in a time $t < \tau$, where $\tau$ is initialized to cutoff (line 5) and only decreased by the *update* function after each call to the three procedures/functions. If a qualitative query is asked, $\tau$ is reset to cutoff at line 16. If $\tau$ is reduced to 0, GEQCA-II will ask a query at the next iteration where *propagate*, *solve*, and PC cannot be called, and then $\tau$ is reset to cutoff. Thus, the waiting time between two queries will never exceed the cutoff time-bound. $\square$

**Complexity of GEQCA-II in terms of queries.**

We analyze the complexity of GEQCA-II in terms of number of queries. It is worth noticing that there are two types of queries involved. The first type is universal queries, which are submitted to the oracle in line 7 of Algorithm 1. The second type is qualitative queries, which are submitted to the oracle in line 13 of Algorithm 1.

Given a vocabulary $(X, D)$ of $n$ entity variables, a language $\Gamma$ of $m$ basic relations, a qualitative concept $f_Q$, qualitative knowledge $\mathcal{K}_Q \supseteq f_Q$ deduced from a given background knowledge $\mathcal{K}$, a number $k$ of basic relations pruned using $\mathcal{K}$ and PC propagation, and the number $p$ of universal queries positively answered, GEQCA-II asks $O(\frac{n(n-1)}{2})$ universal queries and exactly $\eta = (\alpha - \beta - \theta)$ qualitative queries, where:

* $\alpha = \frac{mn(n-1)}{2}$: $m$ relations per pair of entities;
• $\beta = k$: pruned relation using $\mathcal{K}$ and PC;

• $\theta = mp$: number of relations between independent entities.

## 3.3 Strategies

To optimize GEQCA-II further, we can improve the constraint selection process at line 6 by using more sophisticated heuristics. By selecting constraints in different ways, we can significantly impact both $\mathcal{K}$ and PC propagation, leading to fewer queries needed to reach convergence. While several heuristics have been proposed for solving qualitative networks, such as the weighted heuristic (van Beek & Manchak, 1996), our goal is to learn these networks. To that end, we introduce two dedicated constraint selection heuristics, the PATH-WEIGHTED and PATH-LEX heuristics, which are based on traversing the line graph of the QCN. The line graph is a graph derived from the QCN, where each edge of the original graph is represented as a vertex in the line graph. Two vertices in the line graph are adjacent if and only if their corresponding edges in the original graph share a common endpoint (Ore, 1987). In our context, the QCN is constructed on $n$ entity variables $X_i$ as vertices and $n(n-1)/2$ constraints $C_{ij}$ as edges. In the corresponding line graph $\mathcal{L}(C)$, $C_{ij}$ and $C_{jk}$ are vertices that share the edge $X_j$. The PATH-WEIGHTED heuristic traverses the line graph in a way that minimizes the weight of the selected constraints, while the PATH-LEX heuristic builds a complete path to maximize the impact of PC and the transitivity between constraints.

### 3.3.1 PATH-WEIGHTED HEURISTIC

Algorithm 2 outlines our heuristic for selecting constraints to form a path traversing the line graph of a QCN $C$, with the aim of maximizing the path length. Given the last selected constraint $C_{ij}$ and the QCN $C$, PATH-WEIGHTED starts by updating the set of visited nodes (line 2). Next, it computes the set of entity variables $X_k$ that have at least one non-visited constraint with either $X_i$ or $X_j$ (line 3). If this set is empty, it means that all constraints involving $X_i$ or $X_j$ have already been visited. In such a case, PATH-WEIGHTED randomly selects a new starting point for a path from the non-visited constraints (line 4). Otherwise, PATH-WEIGHTED selects the constraint linked to $X_i$ or $X_j$ with the minimum weight as the next constraint in the path (line 5, with MINWEIGHT function detailed in lines 7-12). The weight of each constraint is an estimate of how much the basic relations will restrict other constraints, and it is computed as the sum of the weights of involved basic relations (van Beek & Manchak, 1996). Finally, PATH-WEIGHTED returns the selected constraint to be used in the next iteration (line 6).

### 3.3.2 PATH-LEX HEURISTIC

Algorithm 3 presents our second heuristic for selecting constraints forming a path traversing the line graph of the corresponding QCN, $C$, while maximizing its length. Similar to PATH-WEIGHTED, PATH-LEX begins by updating the set of visited nodes (line 2), and then computes the set of entity variables $X_k$ that have a non-visited constraint with $X_i$ or $X_j$ (line 3). However, unlike PATH-WEIGHTED, PATH-LEX selects the next constraint to visit in a lexicographic manner (line 4). Specifically, given the last visited constraint $C_{ij}$ and
<caption>**Algorithm 2:** PATH-WEIGHTED constraint selection heuristic</caption>

1 **Function** PATH-WEIGHTED($C$, Visited, $C_{ij}$):
2 &nbsp;&nbsp;&nbsp;3 Visited ← Visited ∪ {$C_{ij}$}
3 &nbsp;&nbsp;&nbsp;4 $Y \leftarrow \{X_k \in X | C_{ik} \notin \text{Visited} \lor C_{kj} \notin \text{Visited}\}$
4 &nbsp;&nbsp;&nbsp;5 **if** $Y = \emptyset$ **then** $\Delta \leftarrow \text{pick } C_{kl} \in C \setminus \text{Visited}$
5 &nbsp;&nbsp;&nbsp;6 **else** $\Delta \leftarrow \text{MINWEIGHT}(Y, \text{Visited}, i, j)$
6 &nbsp;&nbsp;&nbsp;7 **return** $\Delta$

7 **Function** MINWEIGHT($Y$, Visited, $i, j$):
8 &nbsp;&nbsp;&nbsp;9 **foreach** $X_k \in Y$ **do**
10 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;11 **if** ($C_{ik} \notin \text{Visited}$) ∧ ($\text{WEIGHT}(C_{ik}) < min$) **then** $\Delta \leftarrow C_{ik}$;
10 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;12 **else** ($C_{kj} \notin \text{Visited}$) ∧ ($\text{WEIGHT}(C_{kj}) < min$) **then** $\Delta \leftarrow C_{kj}$;
11 &nbsp;&nbsp;&nbsp;12 **return** $\Delta$

<caption>**Algorithm 3:** PATH-LEX constraint selection heuristic</caption>

1 **Function** PATH-LEX($C$, Visited, $C_{ij}$):
2 &nbsp;&nbsp;&nbsp;3 Visited ← Visited ∪ {$C_{ij}$}
3 &nbsp;&nbsp;&nbsp;4 $Y \leftarrow \{X_k \in X | C_{ik} \notin \text{Visited} \lor C_{kj} \notin \text{Visited}\}$
4 &nbsp;&nbsp;&nbsp;5 $k \leftarrow lex(Y)$
5 &nbsp;&nbsp;&nbsp;6 **if** $C_{ik} \notin \text{Visited}$ **then** $\Delta \leftarrow C_{ik}$
6 &nbsp;&nbsp;&nbsp;7 **else if** $C_{kj} \notin \text{Visited}$ **then** $\Delta \leftarrow C_{kj}$
7 &nbsp;&nbsp;&nbsp;8 **else** $\Delta \leftarrow \text{tossUp}(C_{ik}, C_{kj})$
8 &nbsp;&nbsp;&nbsp;9 **return** $\Delta$

the $X_k$ lexicographically selected at line 4, if both $C_{ik}$ and $C_{kj}$ are non-visited constraints, the path is extended with one of them in a random manner (line 7). The idea behind this approach is to ensure that the traversal of the line graph covers the QCN efficiently, while prioritizing constraints that are likely to have a significant impact on $\mathcal{K}$ and PC propagation.

In summary, PATH-WEIGHTED and PATH-LEX are two dedicated constraint selection heuristics that aim to maximize the length of a path traversing the line graph of a QCN $C$ while ensuring that constraints with a high impact on $\mathcal{K}$ and PC propagation are visited early on. These heuristics have been shown to significantly improve the number of queries needed to reach convergence as compared to more brute-force approaches.
<figure><img src="image_6.png" /><figcaption>Figure 4: Visualization of the illustrative example and the relations intended by the oracle. Given duration of the time intervals are chosen arbitrarily but obey the imposed relations on the ordering.</figcaption></figure>

## 3.4 Illustrative Example

To illustrate our approach, let an Allen's interval-based network with four time intervals $X = \{X_1, X_2, X_3, X_4\}$ and a time concept $f_Q$, which captures the oracle's intention. The time concept can be expressed as follows: "$X_1$ overlaps $X_2$, $X_1$ precedes, meets, or overlaps $X_3$, $X_2$ overlaps or finished by $X_3$, $X_2$ precedes or meets $X_4$, and $X_3$ meets $X_4$. For $X_1$ and $X_4$, there is no specific intention."

The oracle's intention defines an ordering of the time intervals but allows one for some flexibility in the exact placement and duration of the intervals. To illustrate the problem, Figure 4 depicts the intervals, the user's intention, and arbitrary lengths for the time intervals.

Figure 5 depicts the QCN of our example and its corresponding line graph in parts (a) and (b), respectively. Part (c) of the figure illustrates the use of PATH-WEIGHTED as a constraint selector, where $w_{ij}^k$ represents the weight of constraint $C_{ij}$ at iteration $k$ of GEQCA-II. Initially, $C_{24}$ is randomly selected, since all constraints have the same weight as the universal constraint (i.e., $\forall C_{ij} \in C: w_{ij}^k = 34$). For the second iteration, PATH-WEIGHTED randomly selects $C_{34}$. Afterwards, the possible relations for $C_{23}$ are reduced by PC and it gets selected in the third iteration. In the fourth iteration, constraints $C_{12}$ and $C_{13}$ are the remaining non-visited constraints that are connected to $C_{23}$ (i.e., constraint at the current iteration). Constraint $C_{12}$ is randomly selected, since it has the same weight as $C_{13}$ (PC did not cause any change in their weights).

Finally, $C_{14}$ is selected as its weight $w_{14}^5 = 3$ is the minimum among the non-visited, connected constraints, before $C_{13}$ is selected in the sixth and last iteration. It results in the following path traversing the line graph:

$$ PATH-WEIGHTED: C_{24} \rightarrow C_{34} \rightarrow C_{23} \rightarrow C_{12} \rightarrow C_{14} \rightarrow C_{13} $$

Figure 5.(d) illustrates the use of PATH-LEX. In this heuristic, the line graph is traversed in a lexicographic order, where constraints are visited following the lexicographic order of their variables. The resulting path is as follows:

$$ PATH-LEX: C_{12} \rightarrow C_{23} \rightarrow C_{13} \rightarrow C_{14} \rightarrow C_{24} \rightarrow C_{34} $$
<figure><img src="image_7.png" /><figcaption>Figure 5: QCN example with four entity variables (a), its corresponding line graph (b) and illustrative examples of the use of PATH-WEIGHTED (c) and PATH-LEX (d).</figcaption></figure>

To illustrate the use of GEQCA-II on the example, we apply the PATH-LEX heuristic. We first demonstrate the behavior of GEQCA-I (without universal queries) and then present GEQCA-II. Table 1 displays the learned relations after each iteration.

**Iteration 1:** The oracle is queried 13 times for all possible relations of $C_{12}$ and restricts it to requiring that interval 1 overlaps interval 2. Since all other pairs still allow all 13 basic relations, no further reduction can be calculated at this point.

**Iteration 2:** The oracle is queried 13 times for the possible relations of $C_{23}$ and restricts it to requiring that interval 2 overlaps or is finished by interval 3. Given the information already collected, the path consistency algorithm infers that for the pair of (1, 3), only the relations precedes, meets, and overlaps are possible.

**Iteration 3:** This pair is then queried next on the remaining three relations, which are all confirmed by the oracle.

**Iteration 4:** The oracle is queried 13 times until it is discovered that no specific relations are intended for $C_{14}$.

**Iteration 5:** After querying on $C_{24}$ in and confirming that interval 2 should precede or meet interval 4, the path-consistency method infers a first set of relations on pair (3, 4), on which the oracle has not yet been queried. Additionally, even though the oracle has
no intention for $C_{14}$, we already identify through PC that, given the other answers, only a precedes relation is possible for this pair.

**Final iteration 6:** The oracle is queried five times to further reduce the relations to the intent that interval 3 should meet interval 4, and GEQCA-II finishes after 60 queries.

If we consider the same example, but under the availability of universal queries, the total number of queries reduces to 51. Universal queries are asked at iteration 1, 2, 4, and 5. Three of these pairs are dependent, but $C_{24}$ is independent and the single universal query is therefore sufficient at iteration 4. At iteration 3 and 6, no universal query is asked because it is already known that some relations do exist.

<table><caption>Table 1: Illustrative example of GEQCA with the PATH-LEX heuristic. A gray background highlights the pair *i*, *j* on which the oracle is queried. Bold values show a change in the relations, either due to the queries or the following path consistency algorithm. ⊤ marks pairs with the full $|\Gamma| = 13$ basic possible relations in Allen's calculus (see Figure 1(a)).</caption><thead><tr><th>Iteration</th><th>C<sub>12</sub></th><th>C<sub>13</sub></th><th>C<sub>14</sub></th><th>C<sub>23</sub></th><th>C<sub>24</sub></th><th>C<sub>34</sub></th></tr></thead><tbody><tr><td>1</td><td>o</td><td>⊤</td><td>⊤</td><td>⊤</td><td>⊤</td><td>⊤</td></tr><tr><td>2</td><td>o</td><td>p, m, o</td><td>⊤</td><td>o, fi</td><td>⊤</td><td>⊤</td></tr><tr><td>3</td><td>o</td><td>p, m, o</td><td>⊤</td><td>o, fi</td><td>⊤</td><td>⊤</td></tr><tr><td>4</td><td>o</td><td>p, m, o</td><td>⊤</td><td>o, fi</td><td>⊤</td><td>⊤</td></tr><tr><td>5</td><td>o</td><td>p, m, o</td><td>p</td><td>o, fi</td><td>p, m</td><td>p, m, o, fi, di</td></tr><tr><td>6</td><td>o</td><td>p, m, o</td><td>p</td><td>o, fi</td><td>p, m</td><td>m</td></tr></tbody></table>

## 4. Experiments

This section presents an experimental evaluation of the revised GEQCA-I, which we refer to as GEQCA-II. We compare GEQCA-II with classical GEQCA-I (Belaid et al., 2022) when learning temporal constraints based on Allen's Interval Algebra with $|\Gamma| = 13$ (see Figure 1(a)), and learning spatial networks based on RCC8 with $|\Gamma| = 8$ (see Figure 1(b)). Before reporting on the experiments, we compare different constraint selection heuristics to determine the most promising one. The evaluation aims to answer the following research questions:

* **RQ1:** Which constraint selection heuristic performs better for learning qualitative networks using GEQCA-I?

* **RQ2:** Is GEQCA-II useful for learning qualitative networks, and how does it compare with GEQCA-I and LQCN?

* **RQ3:** Is GEQCA-II capable of learning the qualitative part of real-world scheduling problems, and how does it compare with GEQCA-I?

* **RQ4:** What is the impact of a bounded time limit between two queries on the oracle effort?
**Experimental Evaluation Protocol.** In our experiments, we follow a protocol adapted from (Nebel, 1997; Renz & Nebel, 2001) to generate random instances for both the Allen and RCC8 calculi. We start by instantiating each pair of nodes with an initial consistent relation. To create inconsistent instances, we randomly select three nodes and replace the relation on one pair with one not in the composition of the other two pairs, as derived from the composition table. We then follow the A(n,d,s) procedure (Nebel, 1997; Renz & Nebel, 2001) and verify the consistency or inconsistency of the generated instances using the GQR reasoner (Gantner, Westphal, & Wölfl, 2008). If the instance is not consistent, we restart the process.

We vary the number of nodes *n*, the average degree *d*, which denotes how many other nodes have specified relations, the average label size *l*, which denotes the number of relations specified between nodes, and whether the instance is satisfiable or not (SAT/UNSAT). The maximum degree is limited by the number of nodes, and the maximum average label size is limited by the size of the calculus. The average label size of the instances describes their *density*. When there are many pairs of nodes with the universal relation, i.e., a high average label size, we refer to these instances as having a higher density because there are more alternatives in the oracle's intention. This is in comparison to instances where only a few relations are possible between pairs of nodes, which we refer to as *sparse*.

We refer to Allen instances as Allen_n.d.l_{{SAT, UNSAT}}_i, and RCC8 instances as RCC8_n.d.l_{{SAT, UNSAT}}_i, where *i* is the instance number. We provide the exact parameters for all experiments when they are discussed. We generated 40 instances per algebra and triplet (*n*, *d*, *l*), with 20 instances being SAT and 20 being UNSAT. The values of *n*, *d*, and *l* were chosen from the sets {10, 25, 50, 100}, {(n-1), (n/2)}, and {1, (|Γ|/2)}, respectively, except for *n* = 100, where only 4 instances were generated per algebra and triplet. In total, we generated 968 instances.

The algorithms GEQCA-I and GEQCA-II were implemented in Java, and the Choco solver<fnref n="2" /> was used for the *solve* procedure at line 11 in Algorithm 1. The code and complete description of each instance can be found at the following public repository: https://github.com/lirmm/ConstraintAcquisition/tree/GEQCA.

All tests are run on an Intel core i7, 2.8GHz with RAM of 16GB.

## 4.1 [RQ1]: Constraint Selection Heuristics

For our first experiment, we evaluate the effectiveness of different constraint selection heuristics. We compare four heuristics: (i) LEX - the lexicographical heuristic, (ii) WEIGHTED - the weight-based heuristic, and our (iii) PATH-WEIGHTED and (iv) PATH-LEX heuristic presented in Section 3.3. We use each heuristic with three basic settings: (1) GEQCA-I is used as described in (Belaid et al., 2022) (2) *K* is empty, and (3) the PC function runs until a fixpoint is reached (*cutoff* = ∞). As mentioned in (Belaid et al., 2022), employing the WEIGHTED heuristic in GEQCA-I is equivalent to using LQCN (LearningQCN) as proposed in (Mouhoub et al., 2018, 2021). This equivalence enables us to compare our work with LQCN in the experiments.

Figure 6 shows the results of GEQCA-I using the different heuristics on 240 SAT and 240 UNSAT instances for Allen's Algebra and RCC8. The instances are generated with

<footnote n="2">2. https://choco-solver.org/</footnote>
<figure><img src="image_8.png" /><figcaption>Figure 6: Comparison of GEQCA-I performance (eF: oracle effort) on QCN instances using different heuristics.</figcaption></figure>
$n \in \{10, 25, 50\}$. For each learned instance, we report the oracle effort eF which represents the ratio of queries that need to be classified by the oracle according to $Q_{max}$, the maximum number of queries (i.e., $Q_{max} = \frac{mn(n-1)}{2}$, where $n$ is the number of entities and $m$ is the number of basic relations). The oracle effort is calculated as $eF=(Q^{+} + Q^{-})/Q_{max}$.

The results show the effectiveness of using the PATH-LEX and WEIGHTED heuristics for learning SAT and UNSAT instances, respectively. The PATH-LEX heuristic shows better performance in learning SAT instances by enhancing the impact of PC. In contrast, the WEIGHTED heuristic, being the most efficient in solving QCN, detects inconsistencies early in the learning phase, resulting in less effort. However, our path-based heuristics remain competitive for UNSAT instances.

On the densest instances where the PC function is not significantly involved during the learning process, we observed that PATH-LEX outperforms the other heuristics on Allen's instances, with 99 instances showing more than 90% effort, compared to 111 for LEX, and 118 for both PATH-WEIGHTED and WEIGHTED (LQCN). On RCC8 densest instances, the WEIGHTED heuristic performed the best (LQCN), with 168 instances showing more than 90% effort, compared to 171 for PATH-LEX, 175 for LEX and 185 for PATH-WEIGHTED.

Let us now take a closer look at the experiments. The first parts of Table 2 and Table 3 present the results for selected instances per configuration. For each instance and each heuristic, we report the total number of positive qualitative queries ($Q^+$), the total number of negative qualitative queries ($Q^-$), and the required oracle effort (eF).

The number of positive qualitative queries ($Q^+$) represents the basic relations validated by the oracle in $L$. As PC is called at each iteration and can remove previously validated basic relations, the size of the returned $L$ can be smaller than $Q^+$ (i.e., $size(L) \le Q^+$). Our observations on SAT instances reveal that different heuristics lead the oracle to validate different sets of basic relations. For instance, the size of the learned network $L$ for Allen_25_12_6_SAT_20 is bounded above by a range of 1,022 to 1,502, depending on the heuristic used. However, on UNSAT instances, using the WEIGHTED (LQCN) heuristic leads to a lower number of validated basic relations before reaching the collapse state. For example, WEIGHTED (LQCN) collapses on Allen_25_12_1_UNSAT_19 after validating 42 basic relations, while the other heuristics require validating between 138 and 677 basic relations.

The number of negative qualitative queries ($Q^-$) gives us an indication of the impact of PC. A higher number of removed basic relations using PC results in fewer negative queries. We can observe that PATH-LEX enhances the performance of PC by rapidly forming triangles in the line graph. For instance, in Allen_100_99_1_SAT_1, PATH-LEX requires only 7,740 negative queries while the other heuristics require between 8,316 and 17,168 negative queries.

When considering the set of 484 UNSAT instances, the average effort required by PATH-LEX, PATH-WEIGHTED, WEIGHTED (LQCN), and LEX is 48.60%, 45.09%, 38.09%, and 83.11%, respectively. In this case, WEIGHTED (LQCN) clearly outperforms the other heuristics. However, for the set of 484 SAT instances, the average effort required by PATH-LEX, PATH-WEIGHTED, WEIGHTED (LQCN), and LEX is 82.78%, 86.43%, 84.32%, and 83.94%, respectively. Given that the main focus is on learning SAT instances, PATH-LEX is the most efficient heuristic for learning QCNs. Therefore, we will use PATH-LEX in the rest of the experiments.
<figure><img src="image_9.png" /><figcaption>Figure 7: Comparison of Effort Required by LQCN, GEQCA-I, and GEQCA-II on QCN instances.</figcaption></figure>
## 4.2 [RQ2]: Effectiveness of GEQCA-II Compared to LQCN and GEQCA-I

For our second experiment, we evaluate the effectiveness of GEQCA-II in comparison to GEQCA-I and LQCN. We employ GEQCA-II and GEQCA-I with three basic features: (i) selection of pairs in line 6 of Algorithm 1 is carried out using the PATH-LEX heuristic; (ii) $\mathcal{K}$ is empty; and (iii) the PC function is executed until a fixpoint is reached (cutoff = $\infty$). The sole distinction is the utilization of universal queries (line 7 of Algorithm 1) in GEQCA-II.

Figure 7 illustrates the performance of LQCN, GEQCA-I, and GEQCA-II on 240 SAT and 240 UNSAT instances for Allen's Algebra and RCC8, with instance sizes $n \in \{10, 25, 50\}$. The results are presented in terms of the oracle effort eF, which represents the ratio of asked queries to the maximum number of possible queries. It is worth noting that the use of universal queries in GEQCA-II can lead to an effort greater than 100% for some instances. Specifically, we calculate $eF=(Q^+ + Q^- + UQ^+ + UQ^-)/Q_{max}$, where $UQ^+$ is the total number of positive universal queries and $UQ^-$ is the total number of negative universal queries.

Tables 2 and 3 show the performance of GEQCA-II on a selected set of instances for each configuration. Along with $Q^+$, $Q^-$, and eF, we include the total number of positive universal queries ($UQ^+$) and negative universal queries ($UQ^-$) for GEQCA-II.

On SAT instances, GEQCA-II outperforms GEQCA-I and LQCN, achieving an average effort of 71.25% compared to 83% and 84.54%, respectively. When additional universal queries are used, GEQCA-II reduces the effort needed by LQCN and GEQCA-I by approximately 5% on 75 instances, 10% on 25 instances, and more than 15% on 50 instances for Allen's Algebra (Figure 6.(a)). For instance, it reduces the effort by 40% and 38% on the instance Allen_25_24_6_SAT_20 (Table 2) compared to LQCN and GEQCA-I, respectively. Similarly, on RCC8 SAT instances (Figure 6.(c)), GEQCA-II reduces the required effort by approximately 20% on half of the instances. For example, it reduces the effort by 80% on the instance RCC8_100_50_6_SAT_3 (Table 3).

In cases where there are many universal constraints in the problem instances (i.e., dense instances), GEQCA-II outperforms both GEQCA-I and LQCN, achieving an effort greater than 90% on only 52 Allen's Algebra instances (or 88 RCC8 instances). In contrast, GEQCA-I and LQCN require an effort greater than 90% on 99 and 119 Allen's Algebra instances (or 171 and 168 RCC8 instances), respectively. However, on instances with few or no universal constraints (i.e., sparse instances), GEQCA-II is essentially equivalent to GEQCA-I, except for the additional universal queries it asks.

On UNSAT instances (Figure 7.(b) and (d)), GEQCA-II is more or less equivalent to LQCN.

In summary, the results confirm that using universal queries can decrease the effort required for instances with universal constraints. This effect is most pronounced in dense instances where there are more universal constraints between entities. However, on sparse instances where there is a few or no universal constraints, GEQCA-II performs similarly to GEQCA-I, except for the additional universal queries it asks.
Figure 8 presents a comparison of the oracle effort, eF, of GEQCA-II with LQCN and GEQCA-I on Allen SAT instances of size 25, for two scenarios: (a) variable label size of 1 and variable degree from 1 to 24, and (b) degree of 24 and variable label size from 1 to 13. This comparison strengthens our observations.

In Figure 8.(a), we observe that GEQCA-II significantly reduces the oracle effort compared to LQCN and GEQCA-I, especially for smaller degree values, where there are more pairs with the universal constraint. For example, for degree $d = 1$, GEQCA-II requires only 12% effort, while LQCN and GEQCA-I require more than 99%. This improvement is due to the use of universal queries, which prevent GEQCA-II from asking $|\Gamma|$ additional qualitative queries if a given pair of entities are independent. However, for higher degree values, GEQCA-II requires more effort. For degree $d = 21$, GEQCA-II requires less than 1% additional oracle effort compared to GEQCA-I (41.3% vs 40.8%) and is still better than LQCN (41.3% vs 43.7%).

In Figure 8.(b), the average degree $d = 24$, which means that there are no universal constraints (in average) between entities. This scenario puts GEQCA-II in the most extreme conditions where universal queries are useless. For smaller average label sizes (from 1 to 5), the effort of GEQCA-II is close to GEQCA-I (requires only 2% additional effort on average) and even outperforms LQCN (requires 10% less effort on average). For average label sizes in the middle range (from 6 to 11), GEQCA-II requires slightly more effort compared to LQCN and GEQCA-I (only 4% additional effort on average). However, for larger label size where universal constraints start to appear, GEQCA-II significantly reduces the effort, especially when label size $= |\Gamma|$ (13 in Allen's case), where GEQCA-II reduces the effort to only 7% compared to 100% using LQCN and GEQCA-I. This case highlights the usefulness of universal queries since more pairs of entities are related by the universal relation.

## 4.3 [RQ3]: Effectiveness of GEQCA-II vs GEQCA-I for Learning the Qualitative Part of Real-world Scheduling Problems

For our third experiment, we aim to evaluate the effectiveness of GEQCA-II and GEQCA-I in a real-world context by learning temporal constraints of the Resource Constrained Project Scheduling Problem (RCPSP) (Hartmann & Briskorn, 2010). In this experiment, we do not consider LQCN as it does not utilize the background knowledge. We use publicly available RCPSP instances<fnref n="3" /> and consider the problem structure with task durations, resource requirements, and resource capacities as background knowledge $\mathcal{K}$, denoted by $K_1$. It is worth noting that $K_1$ can be propagated at line 8 of GEQCA-II. Additionally, some constraints, such as the *cumulative* global constraint and deadline constraints, may already be known by the oracle. We refer to the background knowledge that includes the *cumulative* and deadline constraints as $K_2$. The information in $K_1 \wedge K_2$ can be propagated at line 11 of GEQCA-II.

In Table 4, we present the oracle effort for 5 scheduling instances using GEQCA-II and GEQCA-I with the PATH-LEX heuristic, a cutoff time of 3,600s, and different background knowledge ($\mathcal{K}$) settings: $\emptyset$, $K_1$, and $K_1 \wedge K_2$. Additionally, we report the maximum waiting

<footnote n="3">3. https://github.com/MiniZinc/minizinc-benchmarks/tree/master/rcpsp</footnote>
<figure><img src="image_10.png" /><figcaption>Figure 8: Comparison of Effort Required by LQCN, GEQCA-I, and GEQCA-II on Allen SAT instances of size 25 with: (i) fixed average label size of 1 and variable degree (from 1 to 24) and (ii) fixed degree of 24 and variable average label size (from 1 to 13).</figcaption></figure>
<table><caption>Table 2: Comparison GEQCA-I using different heuristics vs GEQCA-II using the best heuristic on Allen instances. eF: Oracle effort, Q+: positive qualitative queries, Q-: negative qualitative queries, UQ+: positive universal queries, UQ-: negative universal queries.</caption><thead><tr><th rowspan="3">Instance</th><th colspan="9">GEQCA-I</th><th colspan="6">GEQCA-II</th></tr><tr><th colspan="3">LEX</th><th colspan="3">WEIGHTED (LQCN)</th><th colspan="3">PATH-WEIGHTED</th><th colspan="3">PATH-LEX</th><th colspan="3">PATH-LEX</th></tr><tr><th>Q<sup>+</sup></th><th>Q<sup>-</sup></th><th>eF</th><th>Q<sup>+</sup></th><th>Q<sup>-</sup></th><th>eF</th><th>Q<sup>+</sup></th><th>Q<sup>-</sup></th><th>eF</th><th>Q<sup>+</sup></th><th>Q<sup>-</sup></th><th>eF</th><th>Q<sup>+</sup></th><th>Q<sup>-</sup></th><th>UQ<sup>+</sup></th><th>UQ<sup>-</sup></th><th>eF</th></tr></thead><tbody><tr><td>Allen.10.9.1.SAT.19</td><td>45</td><td>308</td><td>60%</td><td>45</td><td>320</td><td>62%</td><td>45</td><td>380</td><td>72%</td><td>45</td><td>226</td><td><strong>46%</strong></td><td>45</td><td>268</td><td>0</td><td>20</td><td>57%</td></tr><tr><td>Allen.10.9.1.UNSAT.7</td><td>29</td><td>193</td><td>37%</td><td>11</td><td>133</td><td>24%</td><td>21</td><td>145</td><td>28%</td><td>5</td><td>49</td><td><strong>9%</strong></td><td>5</td><td>49</td><td>0</td><td>4</td><td>10%</td></tr><tr><td>Allen.10.9.6.SAT.14</td><td>276</td><td>304</td><td>99%</td><td>276</td><td>304</td><td>99%</td><td>276</td><td>304</td><td>99%</td><td>266</td><td>290</td><td><strong>95%</strong></td><td>276</td><td>302</td><td>0</td><td>43</td><td>106%</td></tr><tr><td>Allen.10.9.6.UNSAT.13</td><td>208</td><td>289</td><td>84%</td><td>15</td><td>33</td><td><strong>8%</strong></td><td>213</td><td>287</td><td>85%</td><td>15</td><td>36</td><td><strong>9%</strong></td><td>26</td><td>32</td><td>0</td><td>3</td><td>10%</td></tr><tr><td>Allen.10.5.1.SAT.17</td><td>157</td><td>232</td><td>66%</td><td>157</td><td>232</td><td>66%</td><td>273</td><td>252</td><td>89%</td><td>157</td><td>192</td><td><strong>59%</strong></td><td>32</td><td>232</td><td>13</td><td>19</td><td><strong>50%</strong></td></tr><tr><td>Allen.10.5.1.UNSAT.12</td><td>101</td><td>115</td><td>36%</td><td>75</td><td>91</td><td>28%</td><td>47</td><td>61</td><td><strong>18%</strong></td><td>29</td><td>93</td><td>21%</td><td>3</td><td>29</td><td>2</td><td>3</td><td><strong>6%</strong></td></tr><tr><td>Allen.10.5.6.SAT.18</td><td>401</td><td>172</td><td>98%</td><td>401</td><td>172</td><td>98%</td><td>422</td><td>162</td><td>99%</td><td>403</td><td>172</td><td>98%</td><td>143</td><td>168</td><td>20</td><td>21</td><td><strong>60%</strong></td></tr><tr><td>Allen.10.5.6.UNSAT.20</td><td>303</td><td>152</td><td>77%</td><td>102</td><td>46</td><td>25%</td><td>225</td><td>91</td><td>54%</td><td>45</td><td>25</td><td><strong>13%</strong></td><td>18</td><td>32</td><td>0</td><td>3</td><td><strong>9%</strong></td></tr><tr><td>Allen.25.24.1.SAT.9</td><td>300</td><td>1,120</td><td>36%</td><td>300</td><td>1,204</td><td>38%</td><td>300</td><td>1,428</td><td>44%</td><td>300</td><td>948</td><td><strong>32%</strong></td><td>300</td><td>964</td><td>0</td><td>70</td><td>34%</td></tr><tr><td>Allen.25.24.1.UNSAT.7</td><td>36</td><td>281</td><td>8%</td><td>17</td><td>50</td><td>1%</td><td>2</td><td>29</td><td><strong>0.8%</strong></td><td>2</td><td>29</td><td><strong>0.8%</strong></td><td>2</td><td>29</td><td>0</td><td>2</td><td>0.8%</td></tr><tr><td>Allen.25.24.6.SAT.7</td><td>1,711</td><td>1,877</td><td>92%</td><td>1,757</td><td>1,965</td><td>95%</td><td>1,752</td><td>1,953</td><td>95%</td><td>1,676</td><td>1,799</td><td><strong>89%</strong></td><td>1,686</td><td>1,801</td><td>0</td><td>216</td><td>95%</td></tr><tr><td>Allen.25.24.6.UNSAT.19</td><td>789</td><td>924</td><td>43%</td><td>792</td><td>918</td><td>43%</td><td>1,424</td><td>1,670</td><td>79%</td><td>413</td><td>479</td><td><strong>22%</strong></td><td>425</td><td>495</td><td>0</td><td>63</td><td>25%</td></tr><tr><td>Allen.25.12.1.SAT.16</td><td>1,072</td><td>912</td><td>50%</td><td>1,116</td><td>970</td><td>53%</td><td>1,502</td><td>1,096</td><td>66%</td><td>1,022</td><td>928</td><td><strong>49%</strong></td><td>307</td><td>930</td><td>57</td><td>74</td><td><strong>35%</strong></td></tr><tr><td>Allen.25.12.1.UNSAT.19</td><td>644</td><td>566</td><td>31%</td><td>42</td><td>37</td><td><strong>2%</strong></td><td>677</td><td>596</td><td>32%</td><td>138</td><td>41</td><td><strong>4%</strong></td><td>12</td><td>109</td><td>5</td><td>9</td><td><strong>3%</strong></td></tr><tr><td>Allen.25.12.6.SAT.20</td><td>2,827</td><td>1,030</td><td>98%</td><td>2,832</td><td>1,030</td><td>99%</td><td>2,833</td><td>1,028</td><td>99%</td><td>2,809</td><td>1,011</td><td><strong>97%</strong></td><td>977</td><td>1,066</td><td>138</td><td>133</td><td><strong>59%</strong></td></tr><tr><td>Allen.25.12.6.UNSAT.20</td><td>1,353</td><td>558</td><td>49%</td><td>729</td><td>282</td><td>26%</td><td>742</td><td>282</td><td>26%</td><td>492</td><td>276</td><td><strong>19%</strong></td><td>232</td><td>277</td><td>20</td><td>37</td><td><strong>14%</strong></td></tr><tr><td>Allen.50.49.1.SAT.17</td><td>1,225</td><td>3,050</td><td>27%</td><td>1,225</td><td>3,512</td><td>30%</td><td>1,225</td><td>4,934</td><td>38%</td><td>1,225</td><td>2,756</td><td><strong>25%</strong></td><td>1,225</td><td>2,966</td><td>0</td><td>232</td><td>27%</td></tr><tr><td>Allen.50.49.1.UNSAT.1</td><td>108</td><td>1,150</td><td>7%</td><td>157</td><td>986</td><td>7%</td><td>138</td><td>1,549</td><td>10%</td><td>16</td><td>34</td><td><strong>0.3%</strong></td><td>16</td><td>34</td><td>0</td><td>3</td><td>0.3%</td></tr><tr><td>Allen.50.49.6.SAT.3</td><td>6,203</td><td>6,527</td><td>80%</td><td>6,812</td><td>7,453</td><td>89%</td><td>6,829</td><td>7,420</td><td>89%</td><td>6,035</td><td>6,177</td><td><strong>77%</strong></td><td>6,112</td><td>6,243</td><td>0</td><td>584</td><td>81%</td></tr><tr><td>Allen.50.49.6.UNSAT.4</td><td>642</td><td>757</td><td>8%</td><td>43</td><td>56</td><td><strong>0.6%</strong></td><td>82</td><td>101</td><td>1%</td><td>92</td><td>110</td><td><strong>1%</strong></td><td>92</td><td>110</td><td>0</td><td>14</td><td>1%</td></tr><tr><td>Allen.50.25.1.SAT.15</td><td>3,353</td><td>2,708</td><td>38%</td><td>3,429</td><td>2,790</td><td>39%</td><td>4,729</td><td>3,216</td><td>50%</td><td>3,365</td><td>2,670</td><td><strong>37%</strong></td><td>1,225</td><td>2,966</td><td>0</td><td>232</td><td>27%</td></tr><tr><td>Allen.50.25.1.UNSAT.17</td><td>1,075</td><td>897</td><td>50%</td><td>21</td><td>61</td><td><strong>0.5%</strong></td><td>312</td><td>421</td><td>4%</td><td>88</td><td>85</td><td><strong>1%</strong></td><td>13</td><td>121</td><td>7</td><td>10</td><td><strong>0.9%</strong></td></tr><tr><td>Allen.50.25.6.SAT.3</td><td>10,999</td><td>4,203</td><td>95%</td><td>11,007</td><td>4,207</td><td>95%</td><td>11,009</td><td>4,200</td><td>95%</td><td>10,951</td><td>4,168</td><td><strong>95%</strong></td><td>4,713</td><td>4,155</td><td>477</td><td>485</td><td><strong>61%</strong></td></tr><tr><td>Allen.50.25.6.UNSAT.18</td><td>9,396</td><td>3,450</td><td>80%</td><td>659</td><td>240</td><td><strong>5%</strong></td><td>3,780</td><td>2,529</td><td>62%</td><td>1,452</td><td>598</td><td><strong>13%</strong></td><td>566</td><td>596</td><td>69</td><td>77</td><td><strong>8%</strong></td></tr><tr><td>Allen.100.99.1.SAT.1</td><td>4,950</td><td>8,316</td><td>20%</td><td>4,950</td><td>9,064</td><td>21%</td><td>4,950</td><td>17,168</td><td>34%</td><td>4,950</td><td>7,740</td><td><strong>19%</strong></td><td>4,950</td><td>7,992</td><td>0</td><td>636</td><td>21%</td></tr><tr><td>Allen.100.99.1.UNSAT.1</td><td>808</td><td>5,039</td><td>9%</td><td>110</td><td>746</td><td><strong>1%</strong></td><td>112</td><td>666</td><td>1%</td><td>813</td><td>2,453</td><td><strong>5%</strong></td><td>813</td><td>2,425</td><td>0</td><td>189</td><td><strong>5%</strong></td></tr><tr><td>Allen.100.50.1.SAT.1</td><td>11,946</td><td>7,428</td><td>30%</td><td>12,098</td><td>7,584</td><td>30%</td><td>15,086</td><td>10,352</td><td>39%</td><td>11,382</td><td>6,994</td><td><strong>28%</strong></td><td>4,639</td><td>7,196</td><td>559</td><td>582</td><td><strong>20%</strong></td></tr><tr><td>Allen.100.50.1.UNSAT.1</td><td>9,187</td><td>6,609</td><td>24%</td><td>6,062</td><td>3,533</td><td>15%</td><td>5,459</td><td>4,045</td><td>14%</td><td>2,850</td><td>1,973</td><td><strong>7%</strong></td><td>495</td><td>1,901</td><td>175</td><td>157</td><td><strong>4%</strong></td></tr></tbody></table>
<table><caption>Table 3: Comparison GEQCA-I using different heuristics vs GEQCA-II using the best heuristic on RCC8 instances. eF: Oracle effort, Q⁺: positive qualitative queries, Q⁻: negative qualitative queries, UQ⁺: positive universal queries, UQ⁻: negative universal queries.</caption><thead><tr><th rowspan="3">Instance</th><th colspan="9">GEQCA-I</th><th colspan="6">GEQCA-II</th></tr><tr><th colspan="3">LEX</th><th colspan="3">WEIGHTED (LQCN)</th><th colspan="3">PATH-WEIGHTED</th><th colspan="3">PATH-LEX</th><th colspan="3">PATH-LEX</th></tr><tr><th>Q<sup>+</sup></th><th>Q<sup>-</sup></th><th>eF</th><th>Q<sup>+</sup></th><th>Q<sup>-</sup></th><th>eF</th><th>Q<sup>+</sup></th><th>Q<sup>-</sup></th><th>eF</th><th>Q<sup>+</sup></th><th>Q<sup>-</sup></th><th>eF</th><th>Q<sup>+</sup></th><th>Q<sup>-</sup></th><th>UQ<sup>+</sup></th><th>UQ<sup>-</sup></th><th>eF</th></tr></thead><tbody><tr><td>RCC8_10_9.1_SAT_10</td><td>45</td><td>245</td><td>80%</td><td>45</td><td>249</td><td>81%</td><td>45</td><td>249</td><td>81%</td><td>45</td><td>223</td><td><strong>74%</strong></td><td>45</td><td>218</td><td>0</td><td>18</td><td>78%</td></tr><tr><td>RCC8_10_9.1_UNSAT_4</td><td>11</td><td>74</td><td>23%</td><td>7</td><td>38</td><td><strong>12%</strong></td><td>22</td><td>122</td><td>40%</td><td>8</td><td>49</td><td>16%</td><td>7</td><td>48</td><td>0</td><td>5</td><td>16%</td></tr><tr><td>RCC8_10_9.4_SAT_2</td><td>173</td><td>178</td><td>97%</td><td>173</td><td>178</td><td>97%</td><td>173</td><td>178</td><td>97%</td><td>173</td><td>181</td><td>98%</td><td>173</td><td>181</td><td>0</td><td>41</td><td>109%</td></tr><tr><td>RCC8_10_9.4_UNSAT_14</td><td>36</td><td>43</td><td>21%</td><td>9</td><td>16</td><td><strong>6%</strong></td><td>58</td><td>55</td><td>31%</td><td>13</td><td>20</td><td>9%</td><td>17</td><td>22</td><td>0</td><td>4</td><td>12%</td></tr><tr><td>RCC8_10_5.1_SAT_14</td><td>154</td><td>162</td><td>87%</td><td>160</td><td>163</td><td>89%</td><td>160</td><td>166</td><td>90%</td><td>154</td><td>146</td><td><strong>83%</strong></td><td>47</td><td>142</td><td>14</td><td>18</td><td><strong>61%</strong></td></tr><tr><td>RCC8_10_5.1_UNSAT_1</td><td>95</td><td>54</td><td>41%</td><td>76</td><td>88</td><td>45%</td><td>17</td><td>20</td><td><strong>10%</strong></td><td>35</td><td>22</td><td>16%</td><td>9</td><td>20</td><td>5</td><td>3</td><td><strong>10%</strong></td></tr><tr><td>RCC8_10_5.4_SAT_3</td><td>254</td><td>105</td><td>98%</td><td>254</td><td>105</td><td>99%</td><td>254</td><td>105</td><td>99%</td><td>248</td><td>97</td><td><strong>95%</strong></td><td>95</td><td>105</td><td>20</td><td>25</td><td><strong>68%</strong></td></tr><tr><td>RCC8_10_5.4_UNSAT_17</td><td>235</td><td>90</td><td>90%</td><td>195</td><td>82</td><td>76%</td><td>190</td><td>79</td><td>74%</td><td>73</td><td>41</td><td><strong>31%</strong></td><td>77</td><td>88</td><td>15</td><td>20</td><td>55%</td></tr><tr><td>RCC8_25_24.1_SAT_5</td><td>300</td><td>1,493</td><td>74%</td><td>300</td><td>1,611</td><td>79%</td><td>300</td><td>1,605</td><td>79%</td><td>300</td><td>1,478</td><td><strong>74%</strong></td><td>300</td><td>1,509</td><td>0</td><td>141</td><td>81%</td></tr><tr><td>RCC8_25_24.1_UNSAT_13</td><td>97</td><td>651</td><td>31%</td><td>170</td><td>834</td><td>41%</td><td>171</td><td>751</td><td>38%</td><td>71</td><td>401</td><td><strong>19%</strong></td><td>71</td><td>431</td><td>0</td><td>50</td><td>23%</td></tr><tr><td>RCC8_25_24.4_SAT_16</td><td>1,180</td><td>1,177</td><td>98%</td><td>1,180</td><td>1,177</td><td>98%</td><td>1,179</td><td>1,176</td><td>98%</td><td>1,174</td><td>1,153</td><td><strong>97%</strong></td><td>1,156</td><td>1,152</td><td>3</td><td>261</td><td>107%</td></tr><tr><td>RCC8_25_24.4_UNSAT_10</td><td>511</td><td>515</td><td>42%</td><td>49</td><td>54</td><td><strong>4%</strong></td><td>139</td><td>159</td><td>12%</td><td>132</td><td>148</td><td>11%</td><td>131</td><td>150</td><td>0</td><td>31</td><td>13%</td></tr><tr><td>RCC8_25_12.1_SAT_3</td><td>1,205</td><td>944</td><td><strong>89%</strong></td><td>1209</td><td>942</td><td>89%</td><td>1,206</td><td>963</td><td>90%</td><td>1,219</td><td>941</td><td>90%</td><td>371</td><td>941</td><td>105</td><td>115</td><td><strong>63%</strong></td></tr><tr><td>RCC8_25_12.1_UNSAT_9</td><td>651</td><td>465</td><td>46%</td><td>449</td><td>239</td><td>28%</td><td>250</td><td>235</td><td><strong>20%</strong></td><td>382</td><td>277</td><td>27%</td><td>62</td><td>277</td><td>40</td><td>38</td><td><strong>17%</strong></td></tr><tr><td>RCC8_25_12.4_SAT_5</td><td>1,793</td><td>599</td><td>99%</td><td>1793</td><td>599</td><td>99%</td><td>1,794</td><td>599</td><td>99%</td><td>1,792</td><td>599</td><td>99%</td><td>617</td><td>599</td><td>147</td><td>147</td><td><strong>63%</strong></td></tr><tr><td>RCC8_25_12.4_UNSAT_5</td><td>1338</td><td>447</td><td>74%</td><td>989</td><td>372</td><td>56%</td><td>997</td><td>372</td><td>57%</td><td>593</td><td>209</td><td><strong>33%</strong></td><td>193</td><td>209</td><td>50</td><td>49</td><td><strong>20%</strong></td></tr><tr><td>RCC8_50_49.1_SAT_5</td><td>1,225</td><td>6,207</td><td>75%</td><td>1,225</td><td>6,404</td><td>78%</td><td>1,225</td><td>6,454</td><td>78%</td><td>1,225</td><td>6,150</td><td><strong>75%</strong></td><td>1,225</td><td>6,189</td><td>0</td><td>579</td><td>81%</td></tr><tr><td>RCC8_50_49.1_UNSAT_2</td><td>700</td><td>4,561</td><td>53%</td><td>466</td><td>2,660</td><td>32%</td><td>467</td><td>2,673</td><td>32%</td><td>191</td><td>1,204</td><td><strong>14%</strong></td><td>191</td><td>1,204</td><td>0</td><td>163</td><td>15%</td></tr><tr><td>RCC8_50_49.4_SAT_2</td><td>4,860</td><td>4,850</td><td>99%</td><td>4,860</td><td>4,852</td><td>99%</td><td>4,860</td><td>4,845</td><td>99%</td><td>4,859</td><td>4,850</td><td><strong>99%</strong></td><td>4,828</td><td>4,849</td><td>4</td><td>1,152</td><td>110%</td></tr><tr><td>RCC8_50_49.4_UNSAT_7</td><td>3,789</td><td>3,767</td><td>77%</td><td>3,062</td><td>3,038</td><td>62%</td><td>3,138</td><td>3,133</td><td>64%</td><td>707</td><td>2,264</td><td><strong>30%</strong></td><td>1,703</td><td>1,723</td><td>0</td><td>419</td><td>39%</td></tr><tr><td>RCC8_50_25.1_SAT_7</td><td>4,990</td><td>3,824</td><td><strong>90%</strong></td><td>4,999</td><td>3,852</td><td>90%</td><td>4,997</td><td>3,848</td><td>90%</td><td>4,996</td><td>3,839</td><td>90%</td><td>1,212</td><td>3,802</td><td>471</td><td>462</td><td><strong>60%</strong></td></tr><tr><td>RCC8_50_25.1_UNSAT_8</td><td>887</td><td>667</td><td>15%</td><td>776</td><td>536</td><td>13%</td><td>713</td><td>489</td><td>12%</td><td>188</td><td>145</td><td><strong>3%</strong></td><td>20</td><td>145</td><td>21</td><td>20</td><td><strong>2%</strong></td></tr><tr><td>RCC8_50_25.4_SAT_9</td><td>7,253</td><td>2,522</td><td>99%</td><td>7,253</td><td>2,522</td><td>99%</td><td>7,250</td><td>2,523</td><td>99%</td><td>7,253</td><td>2,522</td><td>99%</td><td>2,510</td><td>2,524</td><td>593</td><td>616</td><td><strong>63%</strong></td></tr><tr><td>RCC8_50_25.4_UNSAT_4</td><td>3,378</td><td>1,120</td><td>45%</td><td>696</td><td>217</td><td><strong>9%</strong></td><td>704</td><td>217</td><td>9%</td><td>1,117</td><td>349</td><td>15%</td><td>381</td><td>349</td><td>92</td><td>89</td><td><strong>9%</strong></td></tr><tr><td>RCC8_100_99.1_SAT_3</td><td>4,950</td><td>29,003</td><td>87%</td><td>4,950</td><td>28,905</td><td>85%</td><td>4,950</td><td>28,994</td><td>85%</td><td>4,950</td><td>28,980</td><td><strong>85%</strong></td><td>4,950</td><td>28,986</td><td>0</td><td>3,248</td><td>93%</td></tr><tr><td>RCC8_100_99.1_UNSAT_3</td><td>3,883</td><td>21,209</td><td>63%</td><td>4,537</td><td>23,481</td><td>70%</td><td>4,549</td><td>23,619</td><td>66%</td><td>1,951</td><td>11,374</td><td><strong>33%</strong></td><td>1,951</td><td>11,374</td><td>0</td><td>1,281</td><td>36%</td></tr><tr><td>RCC8_100_50.1_SAT_3</td><td>21,154</td><td>16,459</td><td>95%</td><td>21,137</td><td>16,441</td><td>95%</td><td>21,118</td><td>16,439</td><td>94%</td><td>21,154</td><td>16,482</td><td>95%</td><td>722</td><td>4,218</td><td>625</td><td>590</td><td><strong>15%</strong></td></tr><tr><td>RCC8_100_50.1_UNSAT_3</td><td>18,368</td><td>14,486</td><td>83%</td><td>9,729</td><td>7,479</td><td>43%</td><td>10,310</td><td>7,832</td><td>45%</td><td>19,325</td><td>15,055</td><td>86%</td><td>3,788</td><td>15,052</td><td>1,943</td><td>1,997</td><td><strong>57%</strong></td></tr></tbody></table>
time between two queries, denoted as $T_{max}$. Each scheduling instance is labeled by the number of tasks it contains (e.g., sch_30_1 refers to instance 1 with 30 tasks).

Table 4 provides insights into the performance of GEQCA-I and GEQCA-II on scheduling instances. Firstly, we observe that GEQCA-II significantly reduces the oracle effort on all instances when $\mathcal{K}=\emptyset$. For instance, on sch_60_1, GEQCA-II requires only 12% of the effort needed by GEQCA-I (99%), which is due to the presence of independent tasks in these instances. This highlights the usefulness of the universal query in establishing task independence (e.g., more than 1,600 UQ$^+$ on sch_60_1). Secondly, using the problem structure $K_1$ in the propagate procedure reduces the effort of the oracle for GEQCA-I. This reduction corresponds to a 38% average decrease in the number of queries (i.e., 30,528 queries). This reduction is significant when tasks are classified as locally independent using universal queries but not globally. In such cases, $K_1$ drastically reduces the number of qualitative queries asked by GEQCA-I. However, this reduction has no effect on GEQCA-II, where globally inconsistent relations are removed using PC during the acquisition process. Finally, we observe that the oracle effort is reduced when background knowledge is used, especially with known constraints such as cumulative and deadline constraints ($\mathcal{K}=K_1 \wedge K_2$), for both GEQCA-I and GEQCA-II. For instance, on sch_60_1, the effort was reduced from 99% to 62% with GEQCA-I and from 12% to 10% with GEQCA-II.

Using $K_1 \wedge K_2$ in the solve procedure, in addition to using $K_1$ in the propagate procedure, results in a small but insignificant improvement (average effort of 56% instead of 59% using GEQCA-I and average effort of 11% instead of 14% using GEQCA-II). However, under $\mathcal{K}=K_1 \wedge K_2$, the waiting time between two queries can reach the cutoff of one hour on sch_60_3 due to the solve procedure that spends more than an hour trying to prove the consistency of a relation with the network. Note that with $\mathcal{K}=\emptyset$, the waiting time exceeds 7 seconds with a PC call, while the propagate procedure can increase the waiting time to more than 9 seconds under $\mathcal{K}=K_1$.

Comparing GEQCA-II to GEQCA-I, we observe that GEQCA-II spends less time between two queries than GEQCA-I does on most instances. For instance, on sch_30_2, $T_{max}$ reaches 393 seconds using GEQCA-I, whereas it is only 187 seconds using GEQCA-II. This is due to the higher number of calls of the solve procedure in GEQCA-I compared to GEQCA-II. The universal queries used in GEQCA-II prevent calling the solver on independent tasks, which reduces the waiting time.

## 4.4 [RQ4]: Time Limit Impact on GEQCA-II

In this section, we evaluate the performance of the oracle with respect to a time limit between two queries. As presented in Table 4, the waiting time ($T_{max}$) can sometimes exceed the one-hour limit, which could be impractical in some scenarios. In (Lallemand & Gronier, 2012), it is suggested that a cutoff time of 2 seconds is reasonable for human users. Therefore, we conducted a new experiment with a cutoff time of 2 seconds using GEQCA-II. Table 5 displays the results of this experiment.

Table 5 presents the oracle effort on five scheduling instances using GEQCA-I with the PATH-LEX heuristic, a cutoff time of 2 seconds, and $\mathcal{K}$ values of $\emptyset$, $K_1$, and $K_1 \wedge K_2$. Interestingly, we observe that the oracle effort remains unchanged with or without a cutoff, as shown by comparing Table 4 to Table 5. We analyzed the two learning processes
<table><caption>Table 4: GEQCA-I vs GEQCA-II acting on RCPSP instances (with cutoff = 3,600s, T<sub>max</sub> in seconds, eF: oracle effort).</caption><thead><tr><th rowspan="3">Instance</th><th colspan="6">GEQCA-I</th><th colspan="6">GEQCA-II</th></tr><tr><th colspan="2">Ø</th><th colspan="2">K<sub>1</sub></th><th colspan="2">K<sub>1</sub> &amp; K<sub>2</sub></th><th colspan="2">Ø</th><th colspan="2">K<sub>1</sub></th><th colspan="2">K<sub>1</sub> &amp; K<sub>2</sub></th></tr><tr><th>eF</th><th>T<sub>max</sub></th><th>eF</th><th>T<sub>max</sub></th><th>eF</th><th>T<sub>max</sub></th><th>eF</th><th>T<sub>max</sub></th><th>eF</th><th>T<sub>max</sub></th><th>eF</th><th>T<sub>max</sub></th></tr></thead><tbody><tr><td><b>sch_30_1</b></td><td>95%</td><td><b>0.79</b></td><td>55%</td><td>0.91</td><td>53%</td><td>1.18</td><td><b>17%</b></td><td>0.86</td><td><b>17%</b></td><td><b>0.83</b></td><td><b>13%</b></td><td><b>0.92</b></td></tr><tr><td><b>sch_30_2</b></td><td>98%</td><td><b>0.62</b></td><td>52%</td><td>0.90</td><td>48%</td><td>393.08</td><td><b>17%</b></td><td>0.78</td><td><b>17%</b></td><td><b>0.83</b></td><td><b>12%</b></td><td><b>186.80</b></td></tr><tr><td><b>sch_60_1</b></td><td>99%</td><td><b>4.80</b></td><td>65%</td><td>8.51</td><td>62%</td><td>13.00</td><td><b>12%</b></td><td>5.82</td><td><b>12%</b></td><td><b>7.16</b></td><td><b>10%</b></td><td><b>7.83</b></td></tr><tr><td><b>sch_60_2</b></td><td>99%</td><td>7.72</td><td>64%</td><td>8.08</td><td>61%</td><td>12.55</td><td><b>12%</b></td><td><b>4.67</b></td><td><b>12%</b></td><td><b>6.88</b></td><td><b>10%</b></td><td><b>6.95</b></td></tr><tr><td><b>sch_60_3</b></td><td>98%</td><td>5.94</td><td>59%</td><td>9.66</td><td>57%</td><td>3,600</td><td><b>12%</b></td><td><b>5.63</b></td><td><b>12%</b></td><td><b>7.47</b></td><td><b>10%</b></td><td>3,600</td></tr></tbody></table>

<table><caption>Table 5: GEQCA-II acting on RCPSP instances (with cutoff = 2s, T<sub>max</sub> in seconds, eF: oracle effort).</caption><thead><tr><th rowspan="3">Instance</th><th colspan="6">GEQCA-II</th></tr><tr><th colspan="2">Ø</th><th colspan="2">K<sub>1</sub></th><th colspan="2">K<sub>1</sub> &amp; K<sub>2</sub></th></tr><tr><th>eF</th><th>T<sub>max</sub></th><th>eF</th><th>T<sub>max</sub></th><th>eF</th><th>T<sub>max</sub></th></tr></thead><tbody><tr><td><b>sch_30_1</b></td><td>17%</td><td>0.86</td><td>17%</td><td>0.83</td><td>13%</td><td>0.92</td></tr><tr><td><b>sch_30_2</b></td><td>17%</td><td>0.78</td><td>17%</td><td>0.83</td><td>12%</td><td>2</td></tr><tr><td><b>sch_60_1</b></td><td>12%</td><td>2</td><td>12%</td><td>2</td><td>10%</td><td>2</td></tr><tr><td><b>sch_60_2</b></td><td>12%</td><td>2</td><td>12%</td><td>2</td><td>10%</td><td>2</td></tr><tr><td><b>sch_60_3</b></td><td>12%</td><td>2</td><td>12%</td><td>2</td><td>10%</td><td>2</td></tr></tbody></table>

and found that GEQCA-II efficiently prunes the basic relations using PC within the cutoff time. Subsequently, the PC propagation spends the remaining time proving the transitive closure of the network. Propagating the problem structure with $K = K_1$ is also not a time-consuming process. We also observed that the oracle effort is the same even when using $K = K_1 \land K_2$ on sch_60_2 and sch_60_3. This is because the solve procedure can be time-consuming without removing any relation, either because a solution is found after a significant time resolution (e.g., 187 seconds on sch_30_2), or because the time limit is reached without proving the existence of a solution (e.g., one hour on sch_60_3). These observations demonstrate that GEQCA-II is an effective CA-Agent even when subjected to a time limit on the time window between two submitted queries.

The RCPSP instances are formulated using precedes and meets relations. Additionally, we note that GEQCA-I and GEQCA-II learn twice as many precedes constraints compared to the ones in the benchmarks, thanks to the PC procedure which reduces a considerable number of full constraints to precedes. This leads to a faster optimal solution search using networks obtained from GEQCA-I and GEQCA-II compared to the ones in the benchmarks.

## 4.5 Discussion and Limits

In conclusion, our revised approach GEQCA-II shows a higher effectiveness in learning qualitative constraints as compared to the classical GEQCA-I and LQCN. This is mainly due to the new universal query that significantly reduces the number of queries raised to the oracle. The extension addresses the limitations of GEQCA-I in learning dense
instances and the qualitative part of real scheduling problems. Furthermore, both GEQCA-I and GEQCA-II offer a cutoff option to minimize the waiting time between two queries. Assigning the cutoff time to 2 seconds is a reasonable choice.

Note that GEQCA-II may not be suitable for interactive processes when a large number of queries (e.g., thousands) are required and only a single person can answer these queries. Hopefully, as said above in the paper, oracles can also be an automated system (equipped with a non-CP representation of the concept) or a crowd of users. In these cases, the oracle can only check the consistency of information with the concept being learned. For example, expert systems can easily verify the answers to queries, but they may not be able to solve complex queries. An example of an automated oracle in CA is provided in (Paulin, Bessiere, & Sallantin, 2008), where a CA-Agent and a robot interact to acquire sensorimotor behaviors. Another example is provided in (Menguy et al., 2022), where the oracle consists of a program under analysis and its postcondition, which automatically responds to the queries submitted by the CA-agent. It is also possible for the oracle to consist of a community, such as thousands of people or collaborative robots, who share the same concept and are capable of answering questions from any CA-agent (Lazaar, 2021). Furthermore, it is possible to inherit constraints from a past or obsolete model that needs updating. GEQCA-II can easily handle such cases with its incremental calculation of $L$.

There are several ways in which GEQCA-II can be improved:

* **Use other types of queries:** In some practical scenarios, the oracle can provide more informative answers to queries. For example, the oracle can provide all the relations that are allowed on a given pair or all pairs on which a given relation is allowed. Incorporating such query types could improve the efficiency of GEQCA-II.

* **Account for incorrect answers:** GEQCA-II assumes that the oracle always provides correct answers to queries. However, in practice, it may not be the case. To address this issue, we may consider that the oracle answers queries with incorrect answers according to a certain probability distribution. This could lead to a probabilistic version of qualitative CA, which would enable the acquisition of soft constraints enforced with probability restrictions.

* **Constraint selection heuristic:** While PATH-LEX and PATH-WEIGHTED are effective in practice, they may not be suitable for all problems. Combining these heuristics with other dynamic entity-selection heuristics could be interesting. For example, using weights that are dynamically adjusted based on the current status of the acquisition process could be a promising approach.

## 5. Conclusion

In this paper, we presented GEQCA-II, an extension of GEQCA-I, a correct and generic active CA-Agent that can learn any qualitative network using qualitative queries, path consistency, and exploration of background knowledge. The key contribution of GEQCA-II is the incorporation of a new type of query called the *universal query*, which helps to reduce the number of queries required and improves the efficiency of the CA process. Our experimental results demonstrate that GEQCA-II requires only a limited number of queries
to the oracle within a reasonable amount of time, making it a practical and efficient approach. We also showed that GEQCA-II overcomes the limitations of GEQCA-I and LQCN on dense instances. Furthermore, we highlighted the generality of GEQCA-I and GEQCA-II, which can be used to learn not only temporal but also spatial networks. Overall, GEQCA-II presents a promising approach to active constraint acquisition in qualitative reasoning. Future work could explore further enhancements with new query types and real-world applications. The generality of GEQCA-I and GEQCA-II opens up avenues for their application in various domains beyond qualitative reasoning.

## Acknowledgments

This work was funded by the T-LARGO and AutoCSP projects of the Norwegian Research Council, grant numbers 274786 and 324674, as well as projects from the European Union's Horizon research and innovation programme (FAIRiCUBE under grant agreement No 101059238, AI4CCAM under grant agreement No 101076911 and TAILOR under grant agreement No 952215). We would also like to express our gratitude to the reviewers for their constructive and detailed feedback on our manuscript. Their comments helped improving the quality of our work.

## References

Addi, H. A., Bessiere, C., Ezzahir, R., & Lazaar, N. (2018). Time-bounded query generator for constraint acquisition. In *Integration of Constraint Programming, Artificial Intelligence, and Operations Research (CPAIOR 2018)*, Vol. 10848 of *Lecture Notes in Computer Science*. Springer.

Allen, J. F. (1983). Maintaining knowledge about temporal intervals. *Communications of the ACM*, 26(11), 832–843.

Angluin, D. (1988). Queries and concept learning. *Machine learning*, 2(4), 319–342.

Arcangioli, R., Bessiere, C., & Lazaar, N. (2016). Multiple constraint acquisition. In *IJCAI: International Joint Conference on Artificial Intelligence*, pp. 698–704.

Barták, R., Salido, M., & Rossi, F. (2008). Constraint satisfaction techniques in planning and scheduling. *Journal of Intelligent Manufacturing*, 21, 5–15.

Belaid, M.-B., Belmecheri, N., Gotlieb, A., Lazaar, N., & Spieker, H. (2022). GEQCA: Generic qualitative constraint acquisition. In *Proceedings of the AAAI Conference on Artificial Intelligence*, Vol. 36, pp. 3690–3697.

Beldiceanu, N., & Simonis, H. (2012). A Model Seeker: Extracting global constraint models from positive examples. In *International Conference on Principles and Practice of Constraint Programming (CP 2012)*, pp. 141–157. Springer.

Beldiceanu, N., & Simonis, H. (2016). ModelSeeker: Extracting Global Constraint Models from Positive Examples. In Bessiere, C., Raedt, L. D., Kotthoff, L., Nijssen, S., O'Sullivan, B., & Pedreschi, D. (Eds.), *Data Mining and Constraint Programming*, Vol. 10101 of *Data Mining and Constraint Programming*, pp. 77–95. Springer.

Belhadji, S., & Isli, A. (1998). Temporal Constraint Satisfaction Techniques in Job Shop Scheduling Problem Solving. *Constraints*, 3(2), 203–211.

Bessiere, C., Coletta, R., Hebrard, E., Katsirelos, G., Lazaar, N., Narodytska, N., Quimper, C.-G., & Walsh, T. (2013). Constraint acquisition via partial queries. In *Twenty-Third International Joint Conference on Artificial Intelligence*.

Bessiere, C., Coletta, R., Koriche, F., & O'Sullivan, B. (2005). A SAT-based version space algorithm for acquiring constraint satisfaction problems. In *European Conference on Machine Learning*, pp. 23–34. Springer.
Bessiere, C., Coletta, R., O'Sullivan, B., & Paulin, M. (2007). Query-driven constraint acquisition. In *IJCAI*, Vol. 7, pp. 50–55.

Bessiere, C., Koriche, F., Lazaar, N., & O'Sullivan, B. (2017). Constraint acquisition. *Artificial Intelligence*, 244, 315–342.

Bshouty, N. H. (2018). Exact learning from an honest teacher that answers membership queries. *Theoretical Computer Science*, 733, 4–43.

Crainic, T. G., Perboli, G., & Tadei, R. (2012). *Recent Advances in Multi-dimensional Packing Problems*, chap. 5. IntechOpen.

De Raedt, L., Passerini, A., & Reso, S. (2018). Learning constraints from examples. In *Proceedings of the 32nd AAAI Conference on Artificial Intelligence*, pp. 7965–7970.

Gantner, Z., Westphal, M., & Wölfl, S. (2008). GQR - A Fast Reasoner for Binary Qualitative Constraint Calculi. In *AAAI Workshop on Spatial and Temporal Reasoning*, p. 6.

Hartmann, S., & Briskorn, D. (2010). A survey of variants and extensions of the resource-constrained project scheduling problem. *European Journal of operational research*, 207(1), 1–14.

Krokhin, A., Jeavons, P., & Jonsson, P. (2003). Reasoning about temporal relations: The tractable subalgebras of allen's interval algebra. *J. ACM*, 50(5), 591–640.

Lallemand, C., & Gronier, G. (2012). Enhancing user experience during waiting time in hci: contributions of cognitive psychology. In *Proceedings of the Designing Interactive Systems Conference*, pp. 751–760.

Lazaar, N. (2021). Parallel constraint acquisition. In *Thirty-Fifth AAAI Conference on Artificial Intelligence*, AAAI, pp. 3860–3867. AAAI Press.

Mackworth, A. K. (1977). Consistency in networks of relations. *Artificial intelligence*, 8(1), 99–118.

Maddux, R. D. (1994). Relation algebras for reasoning about time and space. In Nivat, M., Rattray, C., Rus, T., & Scollo, G. (Eds.), *Algebraic Methodology and Software Technology (AMAST'93)*, pp. 27–44, London. Springer London.

Menguy, G., Bardin, S., Lazaar, N., & Gotlieb, A. (2022). Automated program analysis: Revisiting precondition inference through constraint acquisition. In Raedt, L. D. (Ed.), *Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence, IJCAI-22*, pp. 1873–1879. International Joint Conferences on Artificial Intelligence Organization.

Mouhoub, M., Marri, H. A., & Alanazi, E. (2018). Learning qualitative constraint networks. In Alechina, N., Nørvåg, K., & Penczek, W. (Eds.), *25th International Symposium on Temporal Representation and Reasoning, TIME 2018, Warsaw, Poland, October 15-17, 2018*, Vol. 120 of *LIPIcs*, pp. 19:1–19:13. Schloss Dagstuhl - Leibniz-Zentrum für Informatik.

Mouhoub, M., Marri, H. A., & Alanazi, E. (2021). Exact learning of qualitative constraint networks from membership queries.

Nebel, B. (1997). Solving hard qualitative temporal reasoning problems: Evaluating the efficiency of using the ORD-Horn class. *Constraints*, 1(3), 175–190.

Ore, O. (1987). *Theory of Graphs*. American Mathematical Society colloquium publications. American Mathematical Society.

Paulin, M., Bessiere, C., & Sallantin, J. (2008). Automatic design of robot behaviors through constraint network acquisition. In *2008 20th IEEE International Conference on Tools with Artificial Intelligence*, Vol. 1, pp. 275–282. IEEE.

Pawlak, T. P., & Krawiec, K. (2017). Automatic synthesis of constraints from examples using mixed integer linear programming. *European Journal of Operational Research*, 261(3), 1141–1157.

Prestwich, S. D., Freuder, E. C., O'Sullivan, B., & Browne, D. (2021). Classifier-based constraint acquisition. *Annals of Mathematics and Artificial Intelligence*, 89(7), 655–674.

Randell, D. A., Cui, Z., & Cohn, A. G. (1992). A spatial logic based on regions and connection.. *KR*, 92, 165–176.

Renz, J., & Nebel, B. (2001). Efficient Methods for Qualitative Spatial Reasoning. *Journal of Artificial Intelligence Research*, 15, 289–318.

Tsouros, D. C., Stergiou, K., & Bessiere, C. (2019). Structure-driven multiple constraint acquisition. In *International Conference on Principles and Practice of Constraint Programming*, pp. 709–725. Springer.
Tsouros, D. C., Stergiou, K., & Bessiere, C. (2020). Omissions in constraint acquisition. In Simonis, H. (Ed.), *Principles and Practice of Constraint Programming*, Vol. 12333 of *Lecture Notes in Computer Science*, pp. 935–951. Springer.

Valiant, L. G. (1984). A theory of the learnable. *Communications of the ACM*, 27(11), 1134–1142.

van Beek, P., & Manchak, D. W. (1996). The design and experimental analysis of algorithms for temporal reasoning. *Journal of Artificial Intelligence Research, 4*.

Vilain, M., & Kautz, H. (1986a). Constraint propagation algorithms for temporal reasoning. In *Proceedings of the Fifth AAAI National Conference on Artificial Intelligence*, AAAI’86, pp. 377–382.

Vilain, M. B., & Kautz, H. A. (1986b). Constraint propagation algorithms for temporal reasoning. In *AAAI*, Vol. 86, pp. 377–382.