Conception d'un algorithme de maintien de solutions dans un reseau de contraintes

Gilles Trombettoni de Menton 1
1 SECOIA - Expert Systems and Design of Tools for Artificial Intelligence
CERMICS - Centre d'Enseignement et de Recherche en Mathématiques, Informatique et Calcul Scientifique, CRISAM - Inria Sophia Antipolis - Méditerranée
Résumé : La plupart des problemes de contraintes sont resolus par des methodes de satisfaction appropriees qui garantissent la completude mais pas necessairement la performance. Une autre interpretation des contraintes a comme point de depart une solution existante, perturbee par l'ajout de nouvelles contraintes et/ou l'alteration de certaines variables. Les algorithmes capables de retablir la coherence du systeme de contraintes, dits de maintien de solution se divisent en plusieurs categories. Le type d'algorithmes developpe dans ce rapport fonctionne par propagation des valeurs, c'est-a-dire qu'il propage ses modifications sur le reseau de contraintes et retablit chacune d'entre elles par ajustement local d'une variable de recalcul. L'algorithme fournit de maniere incrementale et avec une complexite lineaire par rapport au nombre de variables, une solution proche de celle perturbee mais ne verifie plus la propriete de completude. L'algorithme concu sur ce modele se deroule en deux phases ou la premiere planifie les ajustements necessaires et la deuxieme retablit la coherence en se basant sur ce plan. Il tire profit des contraintes numeraires inegalitaires (ou de difference) et du domaine des variables impliquees. Il peut enfin integrer des methodes globales apparentees a des methodes de satisfaction. La derniere partie offre des fonctionnalites supplementaires pour mieux modeliser certains problemes. On obtient finalement une bibliotheque de fonctions Lisp qui permet de manipuler contraintes et variables et de declencher le maintien de solution.
Type de document :
Rapport
[Rapport de recherche] RR-1784, INRIA. 1992
Liste complète des métadonnées

https://hal.inria.fr/inria-00077024
Contributeur : Rapport de Recherche Inria <>
Soumis le : lundi 29 mai 2006 - 11:54:39
Dernière modification le : lundi 16 juillet 2018 - 15:42:10
Document(s) archivé(s) le : lundi 5 avril 2010 - 21:31:52

Fichiers

Identifiants

  • HAL Id : inria-00077024, version 1

Collections

Citation

Gilles Trombettoni de Menton. Conception d'un algorithme de maintien de solutions dans un reseau de contraintes. [Rapport de recherche] RR-1784, INRIA. 1992. 〈inria-00077024〉

Partager

Métriques

Consultations de la notice

230

Téléchargements de fichiers

51