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 contrainteune contrainte exprime des restrictions que l’on souhaite imposer sur des éléments d’un problème. Par exemple, il est possible d’imposer pour un logement que la surface d’une chambre soit d’au moins 12 m2 (qui se traduira ici par une inégalité mathématique largeur x longueur ≥... More 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 contraintesune contrainte exprime des restrictions que l’on souhaite imposer sur des éléments d’un problème. Par exemple, il est possible d’imposer pour un logement que la surface d’une chambre soit d’au moins 12 m2 (qui se traduira ici par une inégalité mathématique largeur x longueur ≥... More, 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élisationmodéliser un problème d’intelligence artificielle consiste à en formuler un énoncé dans un langage (dit langage de modélisation) donné. Ce langage peut s’appuyer sur des formalismes logiques*, algébriques ou même graphiques. Un même problème peut donc être modélisé de diverses manières (selon le langage de... More* : 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 contraintesune contrainte exprime des restrictions que l’on souhaite imposer sur des éléments d’un problème. Par exemple, il est possible d’imposer pour un logement que la surface d’une chambre soit d’au moins 12 m2 (qui se traduira ici par une inégalité mathématique largeur x longueur ≥... More* 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 contraintesune contrainte exprime des restrictions que l’on souhaite imposer sur des éléments d’un problème. Par exemple, il est possible d’imposer pour un logement que la surface d’une chambre soit d’au moins 12 m2 (qui se traduira ici par une inégalité mathématique largeur x longueur ≥... More, appelé ALICE**. De nombreux systèmes de programmation par contraintesdomaine de l’intelligence artificielle qui s’intéresse à la résolution de problèmes combinatoires. L’utilisateur modélise sa problématique dans un langage simple en identifiant les inconnues et les contraintes* qu’il souhaite imposer. Un algorithme (appelé solveur), basé sur des principes de résolution génériques, lui fournit alors une... More* 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 logiquela logique, qui apparaît dans la Grèce Antique avec l’étude des syllogismes, s’intéresse à la formalisation du raisonnement. La lo- gique moderne, qui se développe à partir du XIXe siècle, a conduit à la formalisation d’un véritable calcul déductif à partir de formules logiques formées... More (le problème SATle problème de satisfaction en logique* propositionnelle consiste à déterminer si une formule, exprimée en logique propositionnelle, est vraie ou fausse. Ce problème est très important en informatique, car il constitue la référence des problèmes difficiles à résoudre (ce qui est l’objet de la théorie... More*).
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.