Approche générique pour l'acquisition de contraintes qualitatives - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Access content directly
Conference Papers Year : 2023

Approche générique pour l'acquisition de contraintes qualitatives

Abstract

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 constraintbased modelling. On the other hand, active constraint acquisition (CA) has been used successfully to support nonexperienced users in learning conjunctive constraint networks through the generation of a sequence of queries. In this paper, we propose GEQCA, which stands for Generic Qualitative Constraint Acquisition, an active CA method that learns qualitative constraints via the concept of qualitative queries. GEQCA 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 GEQCA 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 GEQCA on real scheduling instances. * Cette présentation se base sur des résultats publiés à AAAI 2022 [3].
De nombreux problèmes de planification et d’ordonnancement impliquent la création de combinaisons subtiles de contraintes temporelles ou spatiales. La modélisation précise de ces contraintes, qui sont formulées dans diverses algèbres de relations, nécessite une expertise en modélisation basée sur les contraintes et implique un grand nombre de combinaisons logiques possibles. L’acquisition active de contraintes (AC) a été utilisée avec succès pour aider les utilisateurs non expérimentés à apprendre les réseaux de contraintes conjonctives par la génération d’une séquence de requêtes. Dans cet article, nous proposons une méthode d’AC appelée GEQCA pour Generic Qualitative Constraint Acquisition, qui permet d’apprendre les contraintes qualitatives en utilisant des requêtes qualitatives. GEQCA combine les requêtes qualitatives avec la cohérence de chemin limitée dans le temps (PC pour Path Consistency) et la propagation des connaissances de base pour acquérir les contraintes qualitatives. Nous prouvons la correction, la complétude et la terminaison de GEQCA. Nous présentons également une évaluation expérimentale qui montre l’efficacité de notre approche dans l’apprentissage des contraintes temporelles ainsi que l’utilisation de GEQCA sur des instances réelles d’ordonnancement.
Fichier principal
Vignette du fichier
Actes_CH_PFIA2023_3_ pages46 -51.pdf (404.43 Ko) Télécharger le fichier
Origin : Files produced by the author(s)

Dates and versions

lirmm-04473725 , version 1 (22-02-2024)

Identifiers

  • HAL Id : lirmm-04473725 , version 1

Cite

Mohamed-Bachir Belaid, Nassim Belmecheri, Arnaud Gotlieb, Nadjib Lazaar, Helge Spieker. Approche générique pour l'acquisition de contraintes qualitatives. JFPC 2023 - Journées Francophones de Programmation par Contraintes@PFIA2023, Jul 2023, Strasbourg, France. pp.46-47. ⟨lirmm-04473725⟩
15 View
5 Download

Share

Gmail Facebook X LinkedIn More