IGC : Une nouvelle consistance partielle pour les CSPs continus
Résumé
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.