Décision combinatoire, optimisation et compilation de connaissances

De nombreux problèmes de raisonnement et de décision peuvent s’exprimer sous la forme d’un problème d’optimisation sur domaines finis dans lequel on peut coder aussi bien des contraintes inviolables que des préférences (bio-informatique, configuration de produit, diagnostic, etc).

C’est le cas pour les dessins au trait qui posent des problèmes d’interprétation visuelle [9]. Des contraintes inviolables permettent de détecter l’impossibilité d’objets correspondant à certains tracés, tandis que ces mêmes contraintes associées à des préférences pour des surfaces planaires et des angles droits permettent de reconstruire la forme de cet objet à partir du dessin. Le temps de résolution du problème s’accroît de façon exponentielle lorsque sa taille augmente.

Nous avons développé plusieurs algorithmes (logiciel libre ToulBar2 en collaboration avec l’INRA) permettant de résoudre ces problèmes d’optimisation de taille importante [6].

Enfin, une question théorique se pose : l’identification de classes, dites traitables, de problèmes combinatoires dont le temps de résolution ne s’accroît pas de façon exponentielle avec la taille. Un projet de recherche avec l’Université d’Oxford a permis d’identifier plusieurs nouvelles classes traitables [1], [3].

Si les problèmes combinatoires sont intégralement résolus en ligne, il est extrêmement difficile d’assurer la réactivité du système. Les techniques dites de “compilation d’information” proposent de pré-traiter la partie statique du problème hors ligne. On va ainsi “compiler” le modèle du système à diagnostiquer ou le véhicule à configurer. L’un des points clés des recherches théoriques, menées avec le CRIL, le GREYC et l’ONERA, est l’étude de langages dans lesquels le modèle sera compact et permettra de répondre efficacement aux requêtes [8], [2], [11], [12]. Sur le plan pratique, nos collaborations avec des équipes industrielles (Renault, Cameleon) visent à intégrer des structures compilées au sein de configurateurs pour la vente en ligne ou de systèmes de planification et de gestion logistique.

Projets en cours

Références

  • [1] David Cohen, Martin Cooper, Paidi Creed, Peter Jeavons, Stanislav Zivny. An Algebraic Theory of Complexity for Discrete Optimization. In : SIAM Journal on Computing, Society for Industrial and Applied Mathematics (SIAM), USA, Vol. 42 N. 5, pp. 1915-1939, 2013.(pdf)
  • [2] Hélène Fargier, Marquis Pierre, Alexandre Niveau, Nicolas Schmidt. A Knowledge Compilation Map for Ordered Real-Valued Decision Diagrams. In : AAAI Conference on Artificial Intelligence, AAAI Press, p. 1049-1055, juillet 2014.(pdf)
  • [3] Martin Cooper, Stanislav Zivny. Hybrid tractability of valued constraint problems. In : Artificial Intelligence, Elsevier, Vol. 175 N. 9-10, pp. 1555-1569, 2011.(pdf)
  • [4] Jean Marc Astesana, Laurent Cosserat, Hélène Fargier. Constraint-based vehicle configuration : a case study. In : International Conference on Tools with Artificial Intelligence (ICTAI 2010), IEEE Computer Society, pp. 0-1, October 2010.(pdf)
  • [5] Martin Cooper, Peter Jeavons, Andras Salamon. Generalizing constraint satisfaction on trees: hybrid tractability and variable elimination. In : Artificial Intelligence, Elsevier, Vol. 174, pp. 570-584, 2010.(pdf)
  • [6] Martin Cooper, Simon De Givry, Marti Sanchez, Thomas Schiex, Matthias Zytnicki, Tomas Werner. Soft arc consistency revisited. In : Artificial Intelligence, Elsevier, Vol. 174, pp. 449-478, 2010.(pdf)
  • [7] Meghyn Bienvenu, Hélène Fargier, Pierre Marquis. Knowledge Compilation in the Modal Logic S5 . In : Conference on Artificial Intelligence (AAAI 2010), AAAI Press, pp. 261-266, July 2010. (pdf)
  • [8] Hélène Fargier, Pierre Marquis. Disjunctive closures for knowledge compilation . In : Artificial Intelligence, Elsevier, Vol. 216, p. 129-162, août 2014.(pdf)
  • [9] Martin Cooper. Line Drawing Interpretation, Springer, 2008.
  • [10] Martin Cooper, Achref El Mouelhi, Cyril Terrioux, Bruno Zanuttini. On Broken Triangles. In : International Conference on Principles and Practice of Constraint Programming (CP 2014), Springer, pp. 9-24, 2014 (Best Paper).(pdf)
  • [11] Hélène Fargier, Frédéric Maris, Vincent Roger. Temporal Constraint Satisfaction Problems and Difference Decision Diagrams: A Compilation Map. Dans / In : IEEE International Conference on Tools with Artificial Intelligence, IEEE : Institute of Electrical and Electronics Engineers, p. 429-436, novembre / november 2015.(pdf)
  • [12] Christian Bessière, Hélène Fargier, Christophe Lecoutre. Computing and restoring global inverse consistency in interactive constraint satisfaction. Dans / In : Artificial Intelligence, Elsevier, Vol. 241, p. 153-169, octobre / october 2016.(pdf)