Skip to Main content Skip to Navigation
Reports

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

Gilles Trombettoni 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.
Document type :
Reports
Complete list of metadatas

https://hal.inria.fr/inria-00077024
Contributor : Rapport de Recherche Inria <>
Submitted on : Monday, May 29, 2006 - 11:54:39 AM
Last modification on : Thursday, February 7, 2019 - 1:49:30 PM
Long-term archiving on: : Monday, April 5, 2010 - 9:31:52 PM

Identifiers

  • HAL Id : inria-00077024, version 1

Collections

Citation

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

Share

Metrics

Record views

259

Files downloads

78