35
blèmes. Des travaux dans ce sens existent, certains depuis longtemps, comme la logique possibiliste
(qui s’appuie sur une version qualitative de la théorie des possibilités), ou comme plus récemment la
décision argumentée.
Satisfaction de contraintes et SAT (satisfaisabilité d’une formule logique)
Contexte
Une partie de la recherche en intelligence artificielle consiste à rendre la machine capable de résoudre
des problèmes difficiles (pour les ordinateurs et les humains) : ce sont les problèmes dont la complexité théorique est NP-difficile.
Ces problèmes ont été étudiés dès le début de l’IA. Les jeux sont souvent NP-complets (Taquin, Sudoku, Nonogrammes, Candy Crush,. . . ), voire PSPACE ou EXPTIME-complet (Othello, échecs, Go,
Dames. . . ). De nombreux autres domaines de l’IA soulèvent des problèmes des mêmes familles : en
planification robotique, le langage STRIPS définit un problème PSPACE-complet, en apprentissage
automatique, le calcul d’une réalisation “la plus probable” d’un Champ de Markov est NP-complet. La
résolution de ces problèmes a un intérêt au delà de l’IA : la majorité des problèmes de vérification,
conception, configuration, diagnostic, organisation dans le temps ou l’espace sont NP-difficiles (eg. la
gestion des équipages en transport aérien, l’allocation spatio-temporelle optimale de cultures dans des
dispositifs agro-écologiques ou la conception de protéines stables en biologie ont tous une formulation
NP-difficile).
Comme l’on sait que, dans chaque famille, ces problèmes se réduisent rapidement les uns aux autres,
une partie des chercheurs en IA se sont attaqués à l’élaboration de résultats théoriques et empiriques,
d’algorithmes et de logiciels (solvers) capables de résoudre des problèmes difficiles énoncés dans des
formalismes mathématique simples et capables de modéliser de nombreux problèmes d’intérêt (un peu
comme ALICE de JL. Laurière). Les formalismes considérés sont principalement la logique propositionnelle et des modèles graphiques discrets déterministes (réseaux de contraintes) ou stochastiques
(réseaux bayésiens, . . . ).
Historiquement, au travers des GdR BAHIA et CPSFlex (années 90), les Français ont joué un rôle
important dans ces domaines, rôle qu’ils conservent aujourd’hui (voir les répartitions des articles par
pays dans la conférence CP).
Ce domaine de recherche est naturellement proche de la Recherche Opérationnelle, avec un souci particulier de facilité d’expression des problèmes symboliques (sans exclusivité). Sur les objectifs, il est
également proche des techniques des recherche heuristique ou méta-heuristique.
Résultats marquants de ces dernières décennies
1994 à 2005 : la résolution d’instances aléatoires de problèmes de décision NP-complets montre
l’apparition d’un phénomène de transition de phase entre problèmes avec solution et sans solution.
C’est à la transition que les problèmes difficiles à résoudre en pratique abondent. Des liens
s’établissent avec la physique statistique.
1990-: progrès fulgurants dans la capacité à résoudre des instance du problème NP-complet canonique
SAT (trouver une valeur de variables 0/1 rendant vraie une formule logique exprimée sous forme de
clauses). Le développement de logiciels Open Source, l’organisation de compétitions annuelles et
l’accumulation de grands jeux d’instances industrielles y jouent un rôle important.
blèmes. Des travaux dans ce sens existent, certains depuis longtemps, comme la logique possibiliste
(qui s’appuie sur une version qualitative de la théorie des possibilités), ou comme plus récemment la
décision argumentée.
Satisfaction de contraintes et SAT (satisfaisabilité d’une formule logique)
Contexte
Une partie de la recherche en intelligence artificielle consiste à rendre la machine capable de résoudre
des problèmes difficiles (pour les ordinateurs et les humains) : ce sont les problèmes dont la complexité théorique est NP-difficile.
Ces problèmes ont été étudiés dès le début de l’IA. Les jeux sont souvent NP-complets (Taquin, Sudoku, Nonogrammes, Candy Crush,. . . ), voire PSPACE ou EXPTIME-complet (Othello, échecs, Go,
Dames. . . ). De nombreux autres domaines de l’IA soulèvent des problèmes des mêmes familles : en
planification robotique, le langage STRIPS définit un problème PSPACE-complet, en apprentissage
automatique, le calcul d’une réalisation “la plus probable” d’un Champ de Markov est NP-complet. La
résolution de ces problèmes a un intérêt au delà de l’IA : la majorité des problèmes de vérification,
conception, configuration, diagnostic, organisation dans le temps ou l’espace sont NP-difficiles (eg. la
gestion des équipages en transport aérien, l’allocation spatio-temporelle optimale de cultures dans des
dispositifs agro-écologiques ou la conception de protéines stables en biologie ont tous une formulation
NP-difficile).
Comme l’on sait que, dans chaque famille, ces problèmes se réduisent rapidement les uns aux autres,
une partie des chercheurs en IA se sont attaqués à l’élaboration de résultats théoriques et empiriques,
d’algorithmes et de logiciels (solvers) capables de résoudre des problèmes difficiles énoncés dans des
formalismes mathématique simples et capables de modéliser de nombreux problèmes d’intérêt (un peu
comme ALICE de JL. Laurière). Les formalismes considérés sont principalement la logique propositionnelle et des modèles graphiques discrets déterministes (réseaux de contraintes) ou stochastiques
(réseaux bayésiens, . . . ).
Historiquement, au travers des GdR BAHIA et CPSFlex (années 90), les Français ont joué un rôle
important dans ces domaines, rôle qu’ils conservent aujourd’hui (voir les répartitions des articles par
pays dans la conférence CP).
Ce domaine de recherche est naturellement proche de la Recherche Opérationnelle, avec un souci particulier de facilité d’expression des problèmes symboliques (sans exclusivité). Sur les objectifs, il est
également proche des techniques des recherche heuristique ou méta-heuristique.
Résultats marquants de ces dernières décennies
1994 à 2005 : la résolution d’instances aléatoires de problèmes de décision NP-complets montre
l’apparition d’un phénomène de transition de phase entre problèmes avec solution et sans solution.
C’est à la transition que les problèmes difficiles à résoudre en pratique abondent. Des liens
s’établissent avec la physique statistique.
1990-: progrès fulgurants dans la capacité à résoudre des instance du problème NP-complet canonique
SAT (trouver une valeur de variables 0/1 rendant vraie une formule logique exprimée sous forme de
clauses). Le développement de logiciels Open Source, l’organisation de compétitions annuelles et
l’accumulation de grands jeux d’instances industrielles y jouent un rôle important.