IGC : Une nouvelle consistance partielle pour les CSPs continus - Archive ouverte HAL Access content directly
Conference Papers Year : 2005

IGC : Une nouvelle consistance partielle pour les CSPs continus

(1) , (1) , (1)
1

Abstract

Dans cet article, nous proposons une nouvelle classe de consistances partielles sur les CSPs continus, jusque-là ignorée. Cette approche est motivée par le caractère infructueux des algorithmes de propagation de type AC3 conçus pour des problèmes discrets, et appliqués tels quels en domaine continu, c'est à dire avec la même notion de support (au sens des valeurs réelles). Nous donnons une nouvelle définition, celle de support-intervalle, coïncidant avec une autre abstraction du problème, et déclinons plusieurs propriétés des CSPs liées à cette définition. Nous montrons que seule l'une d'elles (IGC) semble exploitable, et qu'il est possible à partir de l'algorithme de base AC3 de l'obtenir, moyennant le recours à des ROBDD (reduced ordered binary decision diagrams), au lieu de simples intervalles, pour la représentation des domaines.
Fichier principal
Vignette du fichier
25.pdf (370.78 Ko) Télécharger le fichier

Dates and versions

inria-00000065 , version 1 (26-05-2005)

Identifiers

  • HAL Id : inria-00000065 , version 1

Cite

Gilles Chabert, Gilles Trombettoni, Bertrand Neveu. IGC : Une nouvelle consistance partielle pour les CSPs continus. Premières Journées Francophones de Programmation par Contraintes, CRIL - CNRS FRE 2499, Jun 2005, Lens, France. pp.199-210. ⟨inria-00000065⟩
91 View
35 Download

Share

Gmail Facebook Twitter LinkedIn More