Résolution des problèmes avec l'IA

La résolution de problèmes avec l’Intelligence Artificielle

L’Intelligence Artificielle se caractérise par une approche nouvelle dans le traitement informatique des problèmes. Les techniques de l’IA consistent à mettre en place une structure informatique qui permet à l’ordinateur de résoudre le problème lui-même. Une fois cette structure en place, il suffit de décrire le problème et non plus de le résoudre.

Principe

Même si plusieurs solutions existent en la matière, 3 méthodes dominantes calquées sur le raisonnement du cerveau humain permettent de comprendre le principe de la résolution de problèmes :

Lorsque plusieurs solutions s’avèrent possibles, il y a généralement des contraintes plus ou moins exogènes qui nous permettent d’aboutir à une solution « forcée ». C’est le principe de la grille de Sudoku qui laisse le choix entre plusieurs chiffres tout en imposant de ne pas avoir deux fois le même dans la grille.

Le cerveau humain cherche aussi souvent, devant un problème, à aller naturellement au plus simple, au plus court ou au plus rapide. Pour ce faire, il analyse les différentes possibilités et les compare pour en sortir l’optimale en parcourant un graphe d’états.

Enfin l’homme rationnel tente souvent de décortiquer un problème chapeau en sous-ensemble en espérant qu’en trouvant la solution, tour à tour, à ces sous- cas plus faciles à résoudre, il parviendra à résoudre le cas ombrelle.

Pour comprendre le principe de la résolution de problèmes par l’IA, on se réfère parfois à la théorie des jeux à deux dits à somme nulle, c’est-à-dire où le gain d’un joueur signifie une perte pour l’autre. Le joueur y tente naturellement les actions de l’autre joueur pour choisir son action optimale à savoir minimiser sa perte maximum. C’est bien là la réaction commune génétique des individus : certes, je veux trouver la solution la meilleure mais je suis souvent conduis à choisir la moins mauvaise avant tout (minimiser ma perte maximum donc).

L’Intelligence Artificielle (AI) suit cette démarche en utilisant par exemple l’algorithme Minimax. La machine passe en revue les possibilités de coups en leur donnant une valeur qui prend en compte le bénéfice du joueur et de son adversaire. L’algorithme tente donc de calculer le meilleur coup en minimisant les pertes tout en présupposant que l’autre joueur tentera, lui, de maximiser ses gains.

Si le nombre de possibilités est trop important, on peut diminuer le nombre de coups possibles en utilisant un second algorithme d’élagage en complément appelé Alpha Beta, comme dans le jeu d’échecs ou le jeu de Go. Pour faire simple, l’élagage suit la logique suivante : Je ne visite pas – dans mon arbre de décision qui modélise l’ensemble des possibilités – une option dont le résultat est inférieur à une option déjà visitée puisque cela est inutile (ça ne sert à rien).

Le graphe d'états

Le graphe d’états

Dans la recherche de solutions, on essaie de suivre un arbre de possibilités ou un Graphe de Résolution de Problèmes (GRP), dont les sommets sont les états possibles du problème. Un graphe d’états peut être souvent très large, voire infini.

La recherche heuristique vise à explorer partiellement le graphe pour aboutir à une solution (c’est-à-dire trouver un plus court chemin) en cherchant à limiter le plus possible la partie explorée.
Tout ceci est réalisé par souci de rapidité (et pour une machine d’utilisation de ressources en mémoire et de limite de vitesse de processeurs). Il en est de même pour l’homme. Prenons un exemple : une voiture vient d’heurter un obstacle vivant. Je ne réagirais pas de la même façon s’il s’agit d’un animal ou d’une personne âgée. Lorsque le fait survient, j’anticipe sur ce que je vais devoir faire tour à tour : dès que j’ai vu qu’il s’agit d’un chien et non d’une personne, il n’est plus utile de rechercher dans mon graphe, les solutions à mettre en œuvre pour secourir la vieille dame. Nous procédons par élimination et il en est de même pour la machine.

On pose un problème en définissant différents états (en arbre ou en graphe) qui constituent chacun une configuration possible du problème. La résolution consistera à trouver un chemin dans le graphe. Par exemple, je peux avoir trois cubes B, C et A. Chaque état sera un empilement différent de deux cubes (C sur A puis B sur C, B sur C puis A sur B, etc.). Si je considère que la solution serait d’empiler les cubes dans l’ordre A, B et C, je parcours le graphe jusqu’à trouver cet état.

Ce principe peut être utilisé dans une séquence concernant la commande d’une machine. Par exemple, dans une machine à laver, « Essorage » doit suivre « Lavage». Dans un distributeur automatique de café, « Remplissage » doit suivre « Arrivée du gobelet » qui lui doit suivre « Insertion de la pièce ». On peut représenter graphiquement ces différents états.

L’algorithme qui permet de passer d‘un état à un autre s’appelle A*, un calcul simple qui recherche le meilleur chemin entre le nœud initial et le nœud final.

Autres méthodes

Optimisation combinatoire

Problèmes de satisfaction de contraintes ou CSP

Méta heuristiques

Un problème d’optimisation combinatoire consiste en général à trouver dans un ensemble discret parmi les meilleurs sous-ensembles ou solutions réalisables.

Les problèmes de satisfaction de contraintes ou CSP (Constraint Satisfaction Problem) sont des problèmes mathématiques dans lesquels on recherche des états ou des objets qui peuvent satisfaire un certain nombre de contraintes ou de critères. Cette méthode fait l’objet de recherches, tant en Intelligence Artificielle qu’en recherche opérationnelle.

Une métaheuristique est un algorithme d’optimisation visant à résoudre des problèmes d’optimisation difficile, pour lesquels on ne dispose pas de solutions classiques plus efficaces. L’algorithme du recuit simulé, l’algorithme génétique, la recherche avec tabous et l’optimisation par colonie de fourmis sont quelques méthodes métaheuristiques.

D’autres articles sur le même thème

Systèmes experts

Les systèmes experts (ou moteurs de règles) sont une technique de l’IA, qui permettent de reproduire les mécanismes cognitifs d’une personne dans un domaine bien particulier.

Système multi agents et IA Distribuée

Le domaines complexes et hétérogènes tels que l’aide à la décision dans des situations subtiles, la reconnaissance et la compréhension de formes dans des environnements mouvants

La chaîne TAL

Le traitement automatique des langues (TAL) ou du langage naturel ou de la langue naturelle (TALN) est un ensemble de techniques d’Intelligence Artificielle

Le Machine learning

« Il n’y a pas d’intelligence sans apprentissage », affirme Yann Le Cun, patron de l’Intelligence Artificielle (IA) chez Facebook. C’est dans cette logique que s’inscrit le machine learning.

Les réseaux neuronaux

De nos jours, on ne peut pas parler de machine learning sans parler de réseau de neurones artificiels, un ensemble d’algorithmes dont le fonctionnement est inspiré des neurones biologiques et qui s’appuie également sur les méthodes statistiques.

Le web sémantique

Le web sémantique permet à la machine de comprendre le langage humain et de le contextualiser.