La recherche classique : de la largeur d’abord à A*

Bien avant que quoi que ce soit ne soit appris à partir de données, l’intelligence artificielle fonctionnait par recherche. On décrit la situation où l’on se trouve, les coups disponibles, et ce qui compte comme terminé - puis un algorithme parcourt l’espace des possibles jusqu’à y arriver. Calcul d’itinéraire, résolution de casse-tête, ordonnancement et démonstration de théorèmes sont un seul et même problème dans ce cadre, et c’est précisément ce qui rend le cadre précieux.

A. Ce qu’est un problème de recherche

Un problème de recherche, c’est cinq choses : un état initial, les actions disponibles dans chaque état, un modèle de transition indiquant où mène chaque action, un test de but, et un coût de pas pour chaque action. Les trois premiers définissent l’espace d’états, le graphe de tout ce qui est atteignable depuis le départ.

L’espace d’états n’est jamais écrit. Il est engendré un successeur à la fois, à la demande, ce qui permet à ces algorithmes de travailler dans des espaces comptant plus d’états qu’il n’y a d’atomes dans l’univers observable. Rien n’est énuméré qui ne soit visité.

Chaque stratégie ci-dessous est jugée sur quatre questions. Est-elle complète - trouve-t-elle une solution quand il en existe une ? Est-elle optimale - trouve-t-elle la moins coûteuse ? Quel est son coût en temps, en nœuds engendrés, et son coût en espace, en nœuds gardés d’un coup ? Les réponses s’écrivent avec le facteur de branchement $b$ et la profondeur $d$ du but le moins profond.

B. La recherche non informée et le mur qu’elle rencontre

La recherche en largeur développe le nœud non développé le moins profond. Elle est complète dès que $b$ est fini, et engendre de l’ordre de $b^d$ nœuds lorsque le test de but est appliqué à chaque nœud dès qu’il est engendré (reportez le test au développement, comme la recherche à coût uniforme doit le faire, et c’est $O(b^{d+1})$). Elle est aussi optimale, mais sous une condition qu’il est facile de survoler : elle renvoie le but le moins profond, qui n’est le but le moins coûteux que si tous les pas coûtent la même chose. Quand les coûts diffèrent, c’est la recherche à coût uniforme - développer le plus petit $g(n)$, le chemin le moins coûteux jusqu’ici - qui est le bon algorithme.

Le problème célèbre de la recherche en largeur n’est pas son temps d’exécution. Comme elle conserve toute la frontière, sa mémoire est elle aussi en $O(b^d)$, et Russell et Norvig en tirent la conclusion sans détour : les besoins en mémoire sont un problème plus grave que le temps d’exécution. Sur leurs chiffres d’illustration, une recherche à la profondeur 12 se termine en une treizaine de jours - supportable, si la réponse importe - et demande un pétaoctet de mémoire, ce qui ne l’est pas du tout. Le temps est une gêne ; la mémoire est un mur.

La recherche en profondeur inverse le compromis. Elle ne stocke que le chemin courant, $O(bm)$ pour une profondeur maximale $m$, et abandonne l’optimalité ainsi que, sur des espaces infinis ou comportant des boucles, la complétude.

L’approfondissement itératif prend la bonne moitié de chacune : lancer une recherche à profondeur limitée avec la limite 0, puis 1, puis 2, jusqu’à ce qu’un but apparaisse.

Réengendrer les niveaux supérieurs à chaque passe semble gaspilleur, et ne l’est pas. Dans un arbre à facteur de branchement à peu près constant, presque tous les nœuds vivent au dernier niveau, qui n’est engendré qu’une fois. La répétition coûte un facteur constant ; l’économie de mémoire est exponentielle. C’est pourquoi l’approfondissement itératif est la méthode non informée par défaut quand l’espace est vaste et la profondeur de la solution inconnue.

C. Ajouter une heuristique

Une heuristique $h(n)$ estime le coût restant de $n$ jusqu’à un but. La façon évidente de s’en servir est de développer le nœud qui paraît le plus proche, $f(n) = h(n)$ - la recherche gloutonne du meilleur d’abord. Sur une carte routière avec l’heuristique de la distance à vol d’oiseau, elle file presque droit vers la destination.

Elle n’est pas non plus optimale, parce qu’elle ignore ce que le trajet a déjà coûté. Une ville proche de la destination peut n’être atteignable que par le long chemin, et la recherche gloutonne s’engagera dans ce détour sans jamais le comparer à une solution dont le premier pas semblait pire.

A* répare exactement cet oubli :

$$f(n) = g(n) + h(n)$$

Coût déjà engagé plus coût estimé à venir : $f(n)$ estime donc le coût total d’une solution passant par $n$. Poser $h = 0$ redonne la recherche à coût uniforme ; ignorer $g$ redonne la recherche gloutonne ; A* est le cas général qui contient les deux.

L’optimalité dépend alors de deux conditions sur l’heuristique.

Admissibilité. $h$ ne doit jamais surestimer le coût restant réel. Comme $g$ est un coût effectivement payé, une $h$ optimiste fait de $f$ une borne inférieure du coût réel de toute solution passant par ce nœud : aucun itinéraire véritablement meilleur n’est donc jamais élagué sur la foi d’une estimation gonflée. La distance à vol d’oiseau convient, car aucune route n’est plus courte que la ligne directe.

Cohérence. Pour la recherche de graphe - où un état peut être atteint par plusieurs chemins - la condition plus forte est

$$h(n) \le c(n, a, n') + h(n')$$

pour tout successeur $n'$ atteint par l’action $a$ : une inégalité triangulaire sur l’estimation. Elle rend $f$ non décroissante le long de tout chemin, si bien que la première fois qu’A* développe un nœud, il a déjà trouvé le chemin le moins coûteux vers lui. Toute heuristique cohérente est admissible.

Au sein de la classe des algorithmes qui prolongent des chemins depuis la racine avec la même heuristique, A* est optimalement efficace : pour une heuristique cohérente donnée, aucun autre algorithme optimal n’est garanti de développer moins de nœuds. Le levier restant est l’heuristique elle-même, et une façon standard d’en construire une est de résoudre un problème relâché - supprimer une contrainte, résoudre exactement la version plus facile, utiliser son coût. Retirer des contraintes ne peut pas rendre une solution plus coûteuse, le résultat est donc admissible par construction.

D. Cela vaut d’être vérifié sur une vraie carte

Le coin Arad-Bucarest de la carte de Roumanie de Russell et Norvig est assez petit pour être fouillé de trois manières et comparé. La recherche à coût uniforme trouve l’itinéraire de 418 km par Rimnicu Vilcea et Pitesti, en développant pour cela toutes les villes de la carte. La recherche gloutonne ne développe que quatre villes et renvoie l’itinéraire par Fagaras - 450 km, soit exactement 32 km de plus. A* renvoie l’itinéraire de 418 km en développant moins de villes que le coût uniforme. Optimalité et effort sont des propriétés distinctes, et c’est l’heuristique qui achète la seconde sans dépenser la première.

La limite pratique d’A* est la mémoire, non la correction : il conserve tous les nœuds engendrés pour que les valeurs de $f$ restent comparables. A* à approfondissement itératif échange du travail répété contre une empreinte bien plus faible, exactement comme l’approfondissement itératif le faisait pour la recherche en largeur.

E. Quand le chemin ne compte pas

Tout ce qui précède conserve le chemin, ce qui est indispensable pour un calcul d’itinéraire et sans intérêt pour un emploi du temps ou un placement de circuit, où seule la configuration finale est la réponse. La recherche locale détient un unique état courant, se déplace vers un voisin, et oublie d’où elle venait : sa mémoire ne croît donc pas du tout avec la recherche.

La simple montée de gradient - toujours se déplacer vers le meilleur voisin - se bloque de trois manières caractéristiques : à un maximum local, plus haut que ses voisins mais pas le plus haut ; sur un plateau, où les voisins ont la même note et où il n’y a pas de pente à suivre ; et sur une crête, où aucun mouvement isolé n’améliore alors qu’une combinaison le ferait. Les redémarrages aléatoires aident : si chaque tentative réussit avec la probabilité $p$, le nombre espéré de tentatives est $1/p$.

Le recuit simulé s’échappe autrement. Il choisit un voisin au hasard, accepte toujours une amélioration, et accepte un mouvement dégradant d’ampleur $\Delta E$ avec la probabilité $e^{-\Delta E/T}$. Les mauvais mouvements sont donc fréquents au début, quand la température $T$ est élevée, et rares ensuite - l’algorithme secoue la surface assez fort pour ressortir d’un optimum local, puis cesse progressivement de secouer. Si le schéma de refroidissement abaisse $T$ assez lentement, la probabilité de trouver un optimum global tend vers 1, ce qui est un énoncé sur la limite plutôt qu’une promesse sur un schéma assez rapide pour être exécuté.

La figure ci-dessous est une surface accidentée : sept maxima locaux et un maximum global. Choisissez un départ : la montée de gradient grimpe puis s’arrête sur la bosse où elle se trouvait, tandis que le recuit en dépasse plusieurs. Aucune des deux exécutions n’est la leçon à elle seule, aussi l’affichage donne-t-il le taux : la montée atteint l’optimum depuis 26,4 % des 201 états de départ, compté exactement, et c’est le p des 1/p redémarrages attendus. Déplacez ensuite la température et observez le nombre de mouvements dégradants acceptés, car ce nombre est le mécanisme d’évasion lui-même.

Pour aller plus loin

Le parcours de formation Recherche et heuristiques travaille tout cela avec des quiz et une cellule exécutable qui fouille la carte de Roumanie de trois manières. La recherche adversariale et le minimax reprend le cas où l’obstacle n’est pas la distance mais un adversaire, et Recherche A* est l’entrée de référence.