La recherche heuristique incrémentale est une famille d'algorithmes en intelligence artificielle qui aborde le problème de la recherche d'un chemin dans un graphe lorsque celui-ci évolue au fil du temps. Contrairement aux méthodes de recherche heuristique classiques comme A*, qui recalculent une solution complète à partir de zéro à chaque changement de l'environnement, les algorithmes de recherche heuristique incrémentale réutilisent autant d'informations que possible des efforts de recherche précédents. Cette réutilisation peut réduire considérablement le coût de calcul dans des environnements dynamiques ou partiellement connus, ce qui les rend particulièrement précieux pour des applications comme la navigation robotique, la recherche de chemin dans les jeux vidéo et le routage des véhicules autonomes.
L'idée centrale est de maintenir une fonction heuristique et un arbre de recherche qui sont mis à jour de manière incrémentale lorsque les coûts des arêtes changent ou lorsque de nouveaux obstacles sont découverts. Lorsqu'un changement survient, l'algorithme identifie quelles parties de la recherche précédente sont encore valides et lesquelles doivent être révisées, puis propage les mises à jour nécessaires. Cette approche contraste à la fois avec la recherche heuristique classique (qui suppose un graphe statique) et avec la recherche incrémentale sans heuristique (qui peut réutiliser des chemins mais manque de l'orientation fournie par une heuristique).
Développement historique
Les fondations de la recherche heuristique incrémentale ont été posées à la fin des années 1990 et au début des années 2000. L'algorithme le plus influent, D Lite, a été introduit par Sven Koenig et Maxim Likhachev en 2002. D Lite est basé sur l'algorithme antérieur D, développé par Anthony Stentz en 1994, qui était conçu pour la navigation de robots mobiles. D Lite simplifie le D* original tout en maintenant son efficacité, et il est devenu une référence standard dans le domaine.
Un autre algorithme clé est Lifelong Planning A (LPA), également introduit par Koenig et Likhachev en 2001. LPA gère les changements de coûts des arêtes tout en maintenant l'heuristique cohérente, et il constitue la base de D Lite. Le domaine s'est depuis élargi avec des variantes telles que Generalized Adaptive A (GAA) et Anytime D*, qui font un compromis entre la qualité de la solution et le temps de calcul.
Principes algorithmiques
Les algorithmes de recherche heuristique incrémentale maintiennent généralement deux types de valeurs pour chaque nœud : une valeur g (le coût du meilleur chemin connu depuis le départ) et une valeur h (l'estimation heuristique vers le but). Ils suivent également si un nœud est cohérent, ce qui signifie que sa valeur g est égale au minimum sur ses prédécesseurs. Lorsque les coûts des arêtes changent, l'algorithme met à jour les valeurs g des nœuds affectés et propage les changements à travers l'arbre de recherche en utilisant une file de priorité ordonnée par f = g + h.
L'innovation clé est l'utilisation d'une « valeur rhs » (valeur du côté droit) dans LPA et D Lite, qui représente le minimum des valeurs g des prédécesseurs plus le coût de l'arête. Un nœud est localement cohérent si sa valeur g est égale à sa valeur rhs. L'algorithme maintient une liste de nœuds localement incohérents et les traite dans l'ordre de leur clé, qui est une paire (min(g, rhs) + h, min(g, rhs)). Cela garantit que seules les parties nécessaires de la recherche sont recalculées.
Applications en robotique et en IA
La recherche heuristique incrémentale est largement utilisée en robotique pour la planification de chemins dans des environnements inconnus ou changeants. Par exemple, un robot explorant un bâtiment peut initialement planifier un chemin basé sur une carte, mais lorsqu'il découvre de nouveaux obstacles (par exemple, des portes fermées), il peut mettre à jour son plan de manière incrémentale sans redémarrer. Cela est crucial pour la navigation en temps réel où le temps de calcul est limité.
Dans les jeux vidéo, les personnages non-joueurs (PNJ) doivent souvent naviguer sur des terrains dynamiques avec des obstacles mobiles ou des objectifs changeants. La recherche heuristique incrémentale permet une replanification efficace, améliorant la réactivité du jeu. La technique est également appliquée dans la logistique, où les itinéraires de livraison doivent s'adapter aux conditions de trafic, et dans le routage réseau, où les coûts des liens fluctuent.
Comparaison avec d'autres méthodes de recherche
La recherche A classique est optimale et complète pour les graphes statiques, mais elle est inefficace dans les environnements dynamiques car elle rejette tout le travail précédent lorsque le graphe change. La recherche heuristique incrémentale conserve les garanties d'optimalité de A tout en réutilisant les calculs antérieurs. Cependant, elle nécessite une mémoire supplémentaire pour stocker l'arbre de recherche et les informations de cohérence.
Une autre approche connexe est la recherche anytime, qui vise à trouver rapidement une bonne solution puis à l'améliorer avec plus de temps. Certains algorithmes incrémentaux, comme Anytime D*, combinent les deux propriétés : ils peuvent retourner rapidement une solution sous-optimale et l'affiner si le temps le permet. Cela est particulièrement utile dans les applications critiques en temps.
Recherche actuelle et orientations futures
Les recherches récentes en recherche heuristique incrémentale se concentrent sur la mise à l'échelle vers de très grands graphes, la gestion d'espaces d'états continus et l'intégration avec l'apprentissage automatique. Par exemple, des heuristiques basées sur l'apprentissage peuvent être utilisées pour améliorer les valeurs h initiales, réduisant le nombre d'expansions. Il existe également des travaux sur la parallélisation de la recherche incrémentale pour les processeurs multi-cœurs et sur sa combinaison avec des planificateurs basés sur l'échantillonnage comme RRT* pour des problèmes de haute dimension.
Dans le contexte des systèmes modernes d'intelligence artificielle, la recherche heuristique incrémentale reste pertinente pour les agents incarnés, tels que ceux des véhicules autonomes Waymo ou des systèmes Tesla Autopilot, où la replanification en temps réel est essentielle. Les principes influencent également la recherche en apprentissage automatique et en apprentissage profond pour apprendre à chercher, bien que les algorithmes classiques restent la norme pour garantir l'optimalité.
Voir aussi
Références
- Koenig, S., & Likhachev, M. (2002). D* Lite. Proceedings of the National Conference on Artificial Intelligence.
- Koenig, S., & Likhachev, M. (2001). Lifelong Planning A*. Artificial Intelligence.
- Stentz, A. (1994). Optimal and Efficient Path Planning for Partially-Known Environments. IEEE International Conference on Robotics and Automation.