COALA : COntraintes, ALgorithmes et Applications

Mots clés

Intelligence Artificielle, Programmation par Contraintes, Résolution de problèmes combinatoires, Applications Industrielles, Conception de Solveurs, Calcul propositionnel, SAT, CSP, Optimisation sous contraintes, Algorithmique, Théorie de la Complexité, Théorie Algorithmique des Graphes, Planification automatique, Packing

 

Responsable
Djamal HABET

 
Membres

ADRAR Nabil  
BALAFREJ Mohamed Amine  Post-Docs / ATER / Ingenieurs
CHERIF Mohamed Sami  Doctorant
COLL Jordi  Post-Docs / ATER / Ingenieurs
GONZALES Christophe  Enseignant-Chercheur / Chercheur
GRANDCOLAS Stephane  Enseignant-Chercheur / Chercheur
HABET Djamal  Enseignant-Chercheur / Chercheur
HENOCQUE Laurent  Enseignant-Chercheur / Chercheur
JEGOU Philippe  Enseignant-Chercheur / Chercheur
JOURNE Axel  Doctorant
LI Chu min  Enseignant-Chercheur / Chercheur
OSTROWSKI Richard  Enseignant-Chercheur / Chercheur
OXUSOFF Laurent  Enseignant-Chercheur / Chercheur
PAIN-BARRE Cyril  Enseignant-Chercheur / Chercheur
PARIS Lionel  Enseignant-Chercheur / Chercheur
PRCOVIC Nicolas  Enseignant-Chercheur / Chercheur
PY Matthieu  Doctorant
TERRIOUX Cyril  Enseignant-Chercheur / Chercheur
VALIZADEH Amir hosein  Doctorant
VARET Adrien  Doctorant

Objectif scientifique

L’activité de l’équipe COALA se situe au cœur des fondements de l’Intelligence Artificielle et de la Programmation par Contraintes.

Nos travaux ont pour objectif de doter les systèmes de raisonnement de l’Intelligence Artificielle d’outils de résolution efficaces à la fois en théorie et en pratique mais ils ont des retombées bien au-delà dans de nombreux domaines d’applications.

Notre activité porte ainsi principalement sur l’algorithmique associée à la résolution du problème de la satisfiabilité en logique des propositions (SAT), des problèmes de satisfaction de contraintes (CSP) et de leurs extensions (optimisation sous contraintes).

Cette activité passe par l’élaboration de méthodes pour la résolution de problèmes combinatoires, la mise en évidence de fragments polynomiaux, la conception de solveurs efficaces en pratique, et leur application à des problèmes réels.

Les fondements théoriques s’appuient sur la théorie des graphes et la théorie de la complexité.
Nous développons 3 axes majeurs :

  • élaboration de méthodes de résolution pour SAT, CSP et leurs extensions à l’optimisation
  • problèmes connexes et transfert vers des applications industrielles
  • conception et réalisation de solveurs

Nous coordonnons depuis 2017 le projet ANR Demograph (http://www.lsis.org/demograph/)

L’équipe publie dans les journaux majeurs en Intelligence Artificielle et en Programmation par Contraintes (Artificial Intelligence J al , Constraints, Annals of Mathematics and Artificial Intelligence et SAT J al ) ainsi que dans les conférences phares de ces domaines (IJCAI, AAAI, CP et ECAI).

En illustration, le solveur ahmaxsat qui a remporté 3 médailles d’Or à la compétition mondiale Max-SAT en 2014 et un tracé de route maritime optimale (application industrielle).

Performances du solveur ahmaxsat développé par COALA. Ce solveur a remporté 3 médailles d’or lors de la compétition mondiale Max-SAT à l’occasion de la FloC 2014 à Vienne. (FloC 2014 est à ce jour la plus important manifestation scientifique organisée autour de la Logique)

Tracé d’un chemin optimal (météo et consommation de carburant) entre le Havre et New-York obtenu par un système développé avec l’équipe dans le cade d’une collaboration industrielle pour le routage des navires marchands.

 

Publications récentes de l’équipe



34 documents

Article dans une revue

  • Mohamed Sami Cherif, Djamal Habet, André Abramé. Understanding the power of Max-SAT resolution through UP-resilience. Artificial Intelligence, Elsevier, 2020, 289, pp.103397. ⟨10.1016/j.artint.2020.103397⟩. ⟨hal-02977156⟩
  • Martin Cooper, Achref Mouelhi, Cyril Terrioux. Variable Elimination in Binary CSPs. Journal of Artificial Intelligence Research, Association for the Advancement of Artificial Intelligence, 2019, 66, pp.589 - 624. ⟨10.1613/jair.1.11295⟩. ⟨hal-02338904⟩
  • Laurent Oxusoff, Pascal Prea, Yvan Perez. A complete logical approach to resolve the evolution and dynamics of mitochondrial genome in bilaterians. PLoS ONE, Public Library of Science, 2018, 13 (3), pp.e0194334. ⟨10.1371/journal.pone.0194334⟩. ⟨hal-01765687⟩
  • Achref Mouelhi. Tractable Classes for CSPs of Arbitrary Arity: From Theory to Practice. Constraints, Springer Verlag, 2017. ⟨hal-01785394⟩
  • Philippe Jégou, Cyril Terrioux. Combining Restarts, Nogoods and Bag-Connected Decompositions for Solving CSPs. Constraints, Springer Verlag, 2017, 22(2) (2), pp.191-229. ⟨10.1007/s10601-016-9248-8⟩. ⟨hal-01479532⟩
  • André Abrame, Djamal Habet, Donia Toumi Gatfaoui. Improving Configuration Checking for Satisfiable Random k-SAT Instances. Annals of Mathematics and Artificial Intelligence, Springer Verlag, 2017, 79 (1-3). ⟨hal-01479538⟩

Communication dans un congrès

  • Yannick Carissan, Chisom-Adaobi Dim, Denis Hagebaum-Reignier, Nicolas Prcovic, Cyril Terrioux, et al.. Computing the Local Aromaticity of Benzenoids Thanks to Constraint Programming. 26th International Conference on Principles and Practice of Constraint Programming, Sep 2020, Louvain-la-Neuve, Belgium. pp.673-689, ⟨10.1007/978-3-030-58475-7_39⟩. ⟨hal-02931928⟩
  • Yannick Carissan, Denis Hagebaum-Reignier, Nicolas Prcovic, Cyril Terrioux, Adrien Varet. Using Constraint Programming to Generate Benzenoid Structures in Theoretical Chemistry. 26th International Conference on Principles and Practice of Constraint Programming, Sep 2020, Louvain-la-Neuve, Belgium. pp.690-706, ⟨10.1007/978-3-030-58475-7_40⟩. ⟨hal-02931934⟩
  • Martin Cooper, Achref El Mouelhi, Cyril Terrioux. Variable Elimination in Binary CSPs (Extended Abstract). Twenty-Ninth International Joint Conference on Artificial Intelligence and Seventeenth Pacific Rim International Conference on Artificial Intelligence , Jul 2020, Yokohama, France. pp.5035-5039, ⟨10.24963/ijcai.2020/702⟩. ⟨hal-02897892⟩
  • Richard Ostrowski, Lionel Paris, Adrien Varet. Another Way to Browse the Search Space For Some Transformations from CSP to SAT. International Symposium on Artificial Intelligence and Mathematics, Jan 2020, Fort Lauderdale, United States. ⟨hal-02456248⟩
  • Christophe Gonzales. Dealing with Continuous Variables in Graphical Models. International Conference on Scalable Uncertainty Management, Dec 2019, Compiègne, France. ⟨hal-02444883⟩
  • Mohamed Sami Cherif, Djamal Habet. Towards the Characterization of Max-Resolution Transformations of UCSs by UP-Resilience. The 25th International Conference on Principles and Practice of Constraint Programming (CP 2019), pp. 91-107, Sep 2019, Stamford, United States. ⟨hal-02295154⟩
  • Mohamed Sami Cherif, Djamal Habet. Sur l'UP-résilience des k-UCSs binaires. Actes des 15èmes Journées Francophones de Programmation par Contraintes (JFPC), pp. 177-180, Jun 2019, Albi, France. ⟨hal-02295161⟩
  • Richard Ostrowski, Lionel Paris, Adrien Varet. Une autre règle de séparation pour des codages de CSP vers SAT. Actes des 15èmes Journées Francophones de Programmation par Contraintes (JFPC), Jun 2019, Albi, France. ⟨hal-02299020⟩
  • Philippe Jégou, Cyril Terrioux. Décompositions structurelles et sémantiques Rapport préliminaire. Actes des 15èmes Journées Francophones de Programmation par Contraintes (JFPC), Jun 2019, Albi, France. pp.3-6. ⟨hal-02162848⟩
  • Djamal Habet, Cyril Terrioux. Une heuristique basée sur l'historique des conflits pour les problèmes de satisfaction de contraintes. Actes des 15èmes Journées Francophones de Programmation par Contraintes (JFPC), Jun 2019, Albi, France. pp.153-154. ⟨hal-02162856⟩
  • Philippe Jégou, Hélène Kanso, Cyril Terrioux. Sur la pertinence des décompositions arborescentes optimales pour la résolution de CSP. Actes des 15èmes Journées Francophones de Programmation par Contraintes (JFPC), Jun 2019, Albi, France. ⟨hal-02162858⟩
  • Djamal Habet, Cyril Terrioux. Conflict History based Search for Constraint Satisfaction Problem. Proceedings of the 34th ACM/SIGAPP Symposium On Applied Computing (SAC), Apr 2019, Limassol, Cyprus. ⟨10.1145/3297280.3297389⟩. ⟨hal-02090618⟩
  • Djamal Habet, Cyril Terrioux. Conflict History Based Branching Heuristic for CSP Solving. Proceedings of the 8th International Workshop on Combinations of Intelligent Methods and Applications (CIMA), Nov 2018, Volos, Greece. ⟨hal-02090610⟩
  • Philippe Jégou, Hélène Kanso, Cyril Terrioux. On the Relevance of Optimal Tree Decompositions for Constraint Networks. Proceedings of the 30th International Conference on Tools with Artificial Intelligence (ICTAI), Nov 2018, Volos, Greece. ⟨hal-01933665⟩
  • Philippe Jégou, Hélène Kanso, Cyril Terrioux. Adaptive and Opportunistic Exploitation of Tree-decompositions for Weighted CSPs. 2017 International Conference on Tools with Artificial Intelligence (ICTAI 2017), Nov 2017, Boston, MA, United States. ⟨hal-01779631⟩
  • Estelle Chauveau, Philippe Jégou, Nicolas Prcovic. Weather Routing Optimization: A New Shortest Path Algorithm. 29th IEEE International Conference on Tools with Artificial Intelligence, ICTAI 2017, Nov 2017, Boston, United States. ⟨hal-01792118⟩
  • Philippe Jégou, Hanan Kanso, Cyril Terrioux. Améliorer les méthodes de décomposition pour le dénombrement exact de solutions. Treizièmes Francophones de Programmation par Contraintes, JFPC 2017, Jun 2017, Montreuil-sur-Mer, France. ⟨hal-01785197⟩
  • Philippe Jégou, Hanan Kanso, Cyril Terrioux. Vers une exploitation dynamique de la décomposition pour les CSPs pondérés. Treizièmes Francophones de Programmation par Contraintes, JFPC 2017, Jun 2017, Montreuil-sur-Mer, France. ⟨hal-01785202⟩
  • Estelle Chauveau, Philippe Jégou, Nicolas Prcovic. Optimisation bi-critère de la vitesse le long d'un trajet maritime. Treizièmes Francophones de Programmation par Contraintes, JFPC 2017, Jun 2017, Montreuil-sur-Mer, France. ⟨hal-01785208⟩
  • Achref Mouelhi. Une famille de règles d'élimination de variables pour les CSP binaires basées sur BTP. Treizièmes Francophones de Programmation par Contraintes, JFPC 2017, Jun 2017, Montreuil-sur-Mer, France. ⟨hal-01785215⟩
  • André Abramé, Djamal Habet. Apprentissage de clauses nobetters dans les solveurs séparation et évaluation pour Max-SAT. Actes des Treizièmes Journées Francophones de Programmation par Contraintes (JFPC 2017)), Jun 2017, Montreuil-sur-Mer, France. ⟨hal-01786548⟩
  • Achref Mouelhi. A BTP-Based Family of Variable Elimination Rules for Binary CSPs. Thirty-First AAAI Conference on Artificial Intelligence, Feb 2017, San Francisco, United States. ⟨hal-01785230⟩

Chapitre d'ouvrage

  • Christophe Gonzales, Patrice Perny. Decision Under Uncertainty. Marquis, Pierre; Papini, Odile; Prade, Henri. A Guided Tour of Artificial Intelligence Research, I, Springer, pp.549-586, 2020, Knowledge Representation, Reasoning and Learning. ⟨hal-02860485⟩
  • Christophe Gonzales, Patrice Perny. Multicriteria Decision Making. Marquis, Pierre; Papini, Odile; Prade, Henri. A Guided Tour of Artificial Intelligence Research, I, Springer, pp.519-548, 2020, Knowledge Representation, Reasoning and Learning, 978-3-030-06164-7. ⟨10.1007/978-3-030-06164-7_16⟩. ⟨hal-02860326⟩

Direction d'ouvrage, Proceedings

  • Cyril Terrioux. Quatorzièmes Journées Francophones de Programmation par Contraintes. Journées Francophones de Programmation par Contraintes, Jun 2018, Amiens, France. 2018. ⟨hal-02064794⟩

Pré-publication, Document de travail

  • Martin C. Cooper, Achref El Mouelhi, Cyril Terrioux. Variable elimination in binary CSPs. 2019. ⟨hal-02142769⟩

Thèse

  • Estelle Chauveau. Optimisation des routes maritimes : un système de résolution multicritère et dépendant du temps. Informatique [cs]. Aix-Marseille Université (AMU), 2018. Français. ⟨tel-02360141⟩
  • Hélène Kanso. Résolution des problèmes (W)CSP et #CSP par approches structurelles : Calcul et exploitation dynamique de décompositions arborescentes. Intelligence artificielle [cs.AI]. Aix Marseille Universitè, 2017. Français. ⟨NNT : 2017AIXM0655⟩. ⟨tel-02457731⟩