Validating Automated Driving Systems (ADS) requires generating various kinematically executable traffic scenarios. The grounding of qualitative descriptions into concrete trajectories is a combinatorial task poorly addressed by learning-based methods. We propose ScenaGen, a CP model operating on qualitative explainable graphs (QXGs) to encode spatio-temporal relations between traffic entities. Formulated over integer position variables, ScenaGen enforces qualitative spatial constraints, distance thresholds, and inter-frame kinematic consistency. A single QXG acts as a formal template for systematically enumerating distinct, quantitatively varied concrete scenarios. Evaluation of synthetic and real-world benchmarks demonstrates that ScenaGen provides a robust and efficient alternative for scenario instantiation, outperforming standard search baselines in both scalability and solution diversity.

High-Utility Itemset Mining (HUIM) aims to discover itemsets whose utility exceeds a given threshold. While specialized algorithms achieve strong performance, they lack flexibility when additional domain constraints must be incorporated. Constraint Programming (CP) offers a declarative alternative, but requires strong propagation to remain competitive. In this paper, we propose a CP framework for utility-driven pattern mining based on a parameterized global constraint that unifies the enumeration of High-Utility Itemsets (HUIs) and a new condensed representation called Utility-Peak Itemsets (UPIs). A UPI is an itemset whose utility is greater or equal than that of all its immediate subsets and supersets, capturing locally utility-maximal patterns. We study the computational complexity of UPI mining and show that deciding whether a high-utility UPI exists, for a given utility threshold, is NP-complete. Our global constraint, PeakUtility, integrates utility computation and upper-bound pruning through propagation rules. Experiments demonstrate that our approach performs competitively with the state of the art HUIM algorithms while preserving the modelling flexibility of CP.

Dropout is a widely used stochastic regularization technique, yet it overlooks structural dependencies within feature maps.We introduce PB-EDropout, an energy-based approach that preserves low-energy spatial patches within each channel while suppressing the rest.During training, candidate masks are sampled from Gibbs distributions and refined using genetic operators, and a running exponential moving average yields deterministic masks for inference.Experiments on shallow CNNs demonstrate that PB-EDropout consistently improves test accuracy over standard dropout, remains effective even with frozen masks, generates interpretable visualizations of discriminative features and are available here https://github.com/Tom-Dvk/PB-EDropout/tree/main.

Road scene understanding in automated driving (AD) aims to build a comprehensive analysis of video sequences taken on the road by embedded or fixed cameras (e.g., mounted on vertical road signals). One goal is to identify the relevant actors in the scene and another goal is to determine the causes that have triggered a specific action of the ego car (i.e., stop, slow down, turn left, etc.). In a complex urban environment, these causes can be multiple, confusing, possibly contradictory to other causes and not easily expressible using simplistic reasoning. Still, providing accurate automatic cause determination supports a) user acceptance by providing appropriate explanations to the car passengers and road users; b) increased road safety by providing detailed road scene understanding to traffic. In this paper, we propose using spatiotemporal reasoning and Belnap's four-valued logic to formulate complex causes of AD action in a road scene. We compute these causes by analysing a Qualitative eXplainable Graph (QXG), which is an abstract representation of the road scene capturing spatiotemporal relations between road entities. Starting from a QXG, our approach called CAIDLOGIC, is targeted to determine complex causes of a selected AD action occurring in a specific frame of a road scene. The usefulness of CAIDLOGIC is demonstrated on several scenes extracted from the well-known NuScene dataset.

This paper investigates the integration of graph neural networks (GNNs) with Qualitative Explainable Graphs (QXGs) for scene understanding in automated driving. Scene understanding is the basis for any further reactive or proactive decision-making. Scene understanding and related reasoning is inherently an explanation task: why is another traffic participant doing something, what or who caused their actions? While previous work demonstrated QXGs' effectiveness using shallow machine learning models, these approaches were limited to analysing single relation chains between object pairs, disregarding the broader scene context. We propose a novel GNN architecture that processes entire graph structures to identify relevant objects in traffic scenes. We evaluate our method on the nuScenes dataset enriched with DriveLM's human-annotated relevance labels. Experimental results show that our GNN-based approach achieves superior performance compared to baseline methods. The model effectively handles the inherent class imbalance in relevant object identification tasks while considering the complete spatial-temporal relationships between all objects in the scene. Our work demonstrates the potential of combining qualitative representations with deep learning approaches for explainable scene understanding in autonomous driving systems.

Program annotations in the form of function pre/postconditions play a crucial role in various software engineering and program verification tasks. However, the frequent unavailability of these annotations necessitates manual retrofitting. This paper shows how constraint acquisition, a learning framework derived from constraint programming and version space learning, can be extended for automatically inferring program preconditions. Our approach performs this inference in a black-box manner through automatic query generation and input-output observations of program executions. We introduce PreCA, the first-ever precondition inference framework leveraging query-based constraint acquisition. Notably, we specialize PreCA to handle memory-related preconditions on binary code, which pose significant challenges in data and information management systems. In contrast to prior black-box techniques, PreCA provides well-defined guarantees. Specifically, it employs a sound and complete method to generate preconditions consistent with all the observed input-output relationships of the program. Furthermore, empirical evaluations on our benchmark demonstrate that PreCA outperforms the results of state-of-the-art approaches, delivering comparable or superior results in 5s, as opposed to the 1-hour runtime of existing approaches on identical machines. We also present two successful use cases from the standard libc and the mbedtls cryptographic library. PreCA notably infers for the former one a more precise precondition than specified in the documentation.

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.

Constraint acquisition (CA) is a method for learning users' concepts by representing them as a conjunction of constraints. While this approach works well for many combinatorial problems over finite domains, some applications require the acquisition of disjunctive constraints, possibly coming from logical implications or negations. In this paper, we propose the first CA algorithm tailored to the automatic inference of disjunctive constraints, named DCA. A key ingredient there, is to build upon the computation of maximal satisfiable subsets. We demonstrate experimentally that DCA is faster and more effective than traditional CA with added disjunctive constraints, even for ultra-metric constraints with up to 5 variables. We also apply DCA to precondition acquisition in software verification, where it outperforms the previous CA-based approach PreCA, being 2.5 times faster. Specifically, in our evaluation DCA infers more preconditions in just 5 minutes than PreCA does in an hour, without requiring prior knowledge about disjunction size. Our results demonstrate the potential of DCA for improving the efficiency and scalability of constraint acquisition in the disjunctive case, enabling a wide range of novel applications.

Many planning, scheduling or multi-dimensional packing problems involve the design of subtle logical combinations of temporal or spatial constraints. On the one hand, the precise modelling of these constraints, which are formulated in various relation algebras, entails a number of possible logical combinations and requires expertise in constraint-based modelling. On the other hand, active constraint acquisition (CA) has been used successfully to support non-experienced users in learning conjunctive constraint networks through the generation of a sequence of queries. In this paper, we propose GEACQ, which stands for Generic Qualitative Constraint Acquisition, an active CA method that learns qualitative constraints via the concept of qualitative queries. GEACQ combines qualitative queries with time-bounded path consistency (PC) and background knowledge propagation to acquire the qualitative constraints of any scheduling or packing problem. We prove soundness, completeness and termination of GEACQ by exploiting the jointly exhaustive and pairwise disjoint property of qualitative calculus and we give an experimental evaluation that shows (i) the efficiency of our approach in learning temporal constraints and, (ii) the use of GEACQ on real scheduling instances.

Program annotations under the form of function pre/postconditions are crucial for many software engineering and program verification applications. Unfortunately, such annotations are rarely available and must be retrofit by hand. In this paper, we explore how Constraint Acquisition (CA), a learning framework from Constraint Programming, can be leveraged to automatically infer program preconditions in a black-box manner, from input-output observations. We propose PreCA, the first ever framework based on active constraint acquisition dedicated to infer memory-related preconditions. PreCA overpasses prior techniques based on program analysis and formal methods, offering well-identified guarantees and returning more precise results in practice.

Constraint acquisition systems assist the non-expert user in modelling her problem as a constraint network. QUACQ is a sequential constraint acquisition algorithm that generates queries as (partial) examples to be classified as positive or negative. The drawbacks are that the user may need to answer a great number of such examples, within a significant waiting time between two examples, to learn all the constraints. In this paper, we propose PACQ, a portfolio-based parallel constraint acquisition system. The design of PACQ benefits from having several users sharing the same target problem. Moreover, each user is involved in a particular acquisition session, opened in parallel to improve the overall performance of the whole system.We prove the correctness of PACQ and we give an experimental evaluation that shows that our approach improves on QUACQ.

The problem of discovering frequent itemsets including rare ones has received a great deal of attention. The mining process needs to be flexible enough to extract frequent and rare regularities at once. On the other hand, it has recently been shown that constraint programming is a flexible way to tackle data mining tasks. In this paper, we propose a constraint programming approach for mining itemsets with multiple minimum supports. Our approach provides the user with the possibility to express any kind of constraints on the minimum item supports. An experimental analysis shows the practical effectiveness of our approach compared to the state of the art.

Frequent itemset mining is one of the most studied tasks in knowledge discovery. It is often reduced to mining the positive border of frequent itemsets, i.e. maximal frequent itemsets. Infrequent itemset mining, on the other hand, can be reduced to mining the negative border, i.e. minimal infrequent itemsets. We propose a generic framework based on constraint programming to mine both borders of frequent itemsets.One can easily decide which border to mine by setting a simple parameter. For this, we introduce two new global constraints, FREQUENTSUBS and INFREQUENTSUPERS, with complete polynomial propagators. We then consider the problem of mining borders with additional constraints. We prove that this problem is coNP-hard, ruling out the hope for the existence of a single CSP solving this problem (unless coNP ⊆ NP).

Discovering association rules among items in a dataset is one of the fundamental problems in data mining. It has recently been shown that constraint programming is a flexible way to tackle data mining tasks. In this paper we propose a declarative model based on constraint programming to capture association rules. Our model also allows us to specify any additional property and/or user's constraints on the kind of rules the user is looking for. To implement our model, we introduce a new global constraint, Confident, for ensuring the confidence of rules. We prove that completely propagating Confident is NP-hard. We thus provide a decomposition of Confident. In addition to user's constraints on the items composing body and head of the rules, we show that we can capture the popular minimal non-redundant property of association rules. An experimental analysis shows the practical effectiveness of our approach compared to existing approaches.

In long lifespan software systems, specification documents can be outdated or even missing. Developing new software releases or checking whether some user requirements are still valid becomes challenging in this context. This challenge can be addressed by extracting high-level observable capabilities of a system by mining its source code and the available source-level documentation. This paper presents feature extraction and traceability (FEAT), an approach that automatically extracts topoi, which are summaries of the main capabilities of a program, given under the form of collections of code functions along with an index. FEAT acts in two steps: first, clustering: by mining the available source code, possibly augmented with code-level comments, hierarchical agglomerative clustering groups similar code functions. In addition, this process gathers an index for each function. Second, entry point selection: functions within a cluster are then ranked and presented to validation engineers as topoi candidates. We implemented FEAT on top of a general-purpose test management and optimization platform and performed an experimental study over 15 open-source software projects amounting to more than 1 M lines of codes proving that automatically discovering topoi is feasible and meaningful on realistic projects.

Fault localization problem is one of the most difficult processes in software debugging. The current constraint-based approaches draw strength from declarative data mining and allow to consider the dependencies between statements with the notion of patterns. Tackling large faulty programs is clearly a challenging issue for Constraint Programming (CP) approaches. Programs with multiple faults raise numerous issues due to complex dependencies between faults, making the localization quite complex for all of the current localization approaches. In this paper, we provide a new CP model with a global constraint to speed-up the resolution and we improve the localization to be able to tackle multiple faults. Finally, we give an experimental evaluation that shows that our approach improves on CP and standard approaches.

During the last decade several constraint acquisition systems have been proposed for assisting non-expert users in building constraint programming models. GENACQ is an algorithm based on generalization queries that can be plugged into many constraint acquisition systems. However, generalization queries require the aggregation of variables into types which is not always a simple task for non-expert users. In this paper, we propose a new algorithm that is able to learn types during the constraint acquisition process. The idea is to infer potential types by analyzing the structure of the current constraint network and to use the extracted types to ask generalization queries. Our approach gives good results although no knowledge on the types is provided.

Constraint acquisition assists a non-expert user in modeling her problem as a constraint network. In existing constraint acquisition systems the user is only asked to answer very basic questions. The drawback is that when no background knowledge is provided, the user may need to answer a great number of such questions to learn all the constraints. In this paper, we introduce the concept of generalization query based on an aggregation of variables into types. We present a constraint generalization algorithm that can be plugged into any constraint acquisition system. We propose several strategies to make our approach more efficient in terms of number of queries. Finally we experimentally compare the recent QUACQ system to an extended version boosted by the use of our generalization functionality. The results show that the extended version dramatically improves the basic QUACQ.

We study how to find a solution to a constraint problem without modeling it. Constraint acquisition systems such as Conacq or ModelSeeker are not able to solve a single instance of a problem because they require positive examples to learn. The recent QuAcq algorithm for constraint acquisition does not require positive examples to learn a constraint network. It is thus able to solve a constraint problem without modeling it: we simply exit from QuAcq as soon as a complete example is classified as positive by the user. In this paper, we propose ASK&SOLVE, an elicitation-based solver that tries to find the best trade off between learning and solving to converge as soon as possible on a solution. We propose several strategies to speed-up ASK&SOLVE. Finally we give an experimental evaluation that shows that our approach improves the state of the art.

Constraint programs, such as those written in high-level constraint modelling languages, e.g., OPL (Optimization Programming Language), COMET, ZINC or ESSENCE, are more and more used in business-critical programs. As any other critical programs, they require to be thoroughly tested and corrected to prevent catastrophic loss of money. This paper presents a framework for the automatic correction of constraint programs that takes into account the specificity of the software development process of these programs as well as their typical faults. We implemented this framework in our testing platform CPTEST for OPL programs. Using mutation testing, our experimental results show that well-known constraint programs written in OPL can be automatically corrected using our framework.

Constraint programs such as those written in high level modeling languages (e.g., OPL, ZINC, or COMET) must be thoroughly verified before being used in applications. Detecting and localizing faults is therefore of great importance to lower the cost of the development of these constraint programs. In a previous work, we introduced a testing framework called CPTEST enabling automated test case generation for detecting non-conformities. In this paper, we enhance this framework to introduce automatic fault localization in constraint programs. Our approach is based on constraint relaxation to identify the constraint that is responsible of a given fault. CPTEST is henceforth able to automatically localize faults in optimized OPL programs. We provide empirical evidence of the effectiveness of this approach on classical benchmark problems, namely Golomb rulers, n-queens, social golfer and car sequencing.