Press "Enter" to skip to content

2.4. Résoudre

Une part importante de l’intelligence artificielle est la résolution de problèmes difficiles (la difficulté venant souvent du nombre d’opérations à effectuer pour résoudre le problème). Illustrons cela sur un exemple concret, à savoir la création d’une grille de mots croisés: une fois les dimensions de la grille fixées, il s’agit de sélectionner des mots et de les positionner de sorte que deux mots consécutifs soient séparés par au moins une case noire, et que chaque intersection entre un mot placé horizontalement et un mot placé verticalement corresponde bien à une lettre commune. S’il n’y a pas de contrainte sur le nombre ou la position des cases noires, le problème est relativement facile. Si, en revanche, on souhaite limiter le nombre de cases noires, leurs positions ou restreindre le vocabulaire autorisé, alors le problème devient plus complexe. Il faut envisager beaucoup de combinaisons de mots avant d’en trouver une qui soit correcte, et une légère augmentation de la taille de la grille augmente fortement ce nombre de combinaisons. Cette explosion combinatoire rend le problème intrinsèquement difficile. Des techniques d’intelligence artificielle, dont nous donnerons quelques exemples, peuvent alors permettre une résolution efficace.

L’enjeu est important, car de très nombreux cas pratiques sont confrontés à ce phénomène d’explosion combinatoire: par exemple, réaliser l’emploi du temps d’un collège, planifier l’activité d’un robot, configurer un produit selon les préférences d’un utilisateur, ou encore ranger des cartons dans un conteneur en minimisant la place perdue.

Pour résoudre ces problèmes, on pourrait explorer de façon exhaustive l’ensemble des combinaisons, jusqu’à trouver une solution. Mais cette exploration systématique, pour être réalisée en un temps acceptable, doit faire appel à des stratégies et techniques dédiées. S’il s’agit de fabriquer une grille de mots croisés, on peut, par exemple, utiliser des règles pour déduire au plus tôt qu’un début de grille ne peut pas être complété en une grille satisfaisant toutes les contraintes, apprendre que certaines zones de la grille sont plus difficiles à remplir que d’autres, ou que certains mots sont plus faciles à placer que d’autres.

En intelligence artificielle, on cherche des algorithmes de résolution de problèmes génériques, c’est-à-dire qui n’utilisent pas de connaissances préalables sur les problèmes, mais reposent sur des méthodologies et principes généraux.

Pour résoudre un problème avec de tels algorithmes, l’utilisateur doit simplement décrire son problème en utilisant un langage de modélisation* : il s’agit essentiellement de définir les inconnues du problème pour lesquelles on cherche une valeur (par exemple, les cases de la grille), ainsi que les contraintes* portant sur ces inconnues (par exemple, toute suite verticale ou horizontale de cases entre deux cases noires doit former un mot).

Jean-Louis Laurière (1945-2005) a conçu en 1978 un premier système général de résolution de problèmes, à base de contraintes, appelé ALICE**. De nombreux systèmes de programmation par contraintes* ont été proposés depuis et sont largement utilisés dans le monde industriel. Certains de ces algorithmes génériques sont dédiés à la résolution de problèmes formulés en logique (le problème SAT*).

D’autres méthodes de résolution pour des problèmes complexes de grandes dimensions, appelées méta-heuristiques*, sont également génériques et s’inspirent, par exemple, de phénomènes naturels ou physiques, tels que la théorie de l’évolution de Darwin (algorithmes évolutionnaires*) ou du comportement de certains animaux (optimisation par colonies de fourmis* par exemple).

Un certain nombre de problèmes nécessitent une résolution collective et/ ou distribuée, par exemple se mettre d’accord sur la date d’une réunion, ou s’organiser pour une distribution de colis. Il s’agit plus généralement de coopérer et de se coordonner pour atteindre un but collectif, ou de négocier lorsque les agents ont des intérêts divergents. Cela constitue la problématique des systèmes multi-agents* (certains de ces agents pouvant être des humains).

** A language and a program for stating and solving combinatorial problems. Jean-Louis Laurière. Dans Artificial Intelligence, vol. 10(1), pp. 29-127. 1978.