Approche générique pour l'acquisition de contraintes qualitatives
Résumé
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.
Domaines
Informatique [cs]| Origine | Fichiers produits par l'(les) auteur(s) |
|---|