Recherche de chemin en temps réel par A*

Introduction

Le programme A* (A-star) est un algorithme de recherche de chemin utilisé dans les domaines de l'intelligence artificielle, de la robotique et des jeux vidéo. Il est principalement utilisé pour trouver le chemin le plus court entre un point de départ et un point d'arrivée dans un graphe pondéré.

Définition

Graphe comprenant 6 nœuds allant de A à F

Graphe : Comme vous l’avez vu ci-dessus un graphe contient des nœuds et des arrêtes. Il peut être orienté lorsque le sens est fixe (On pourrait passer du point A à B mais pas du point B à A) mais dans notre cas il sera non orienté.

Nœud : Ils sont en bleu sur l’exemple ci-dessus. Ils sont les intersections entre les différentes arrêtes.

Distance : La distance est celle qu’on a entre deux nœuds.

Cout : Il est composé des distances parcourus plus le nœud futur.

Heuristique : Il nous sert à orienter notre recherche, il est composé du cout et de la distance à vol d’oiseau entre le nœud et l’arrivé

Fonctionnement

Le fonctionnement de l'algorithme A* repose sur une exploration de différent paramètre tel que l'heuristique à venir, les coûts passés et les estimations heuristiques. L'algorithme maintient une liste de nœuds à explorer, en choisissant à chaque étape le nœud avec le coût total le plus faible. Il utilise une fonction d'évaluation qui combine le coût passé (g(n)), qui représente le coût cumulé pour atteindre un nœud donné depuis le point de départ, et une estimation heuristique du coût restant (h(n)), qui estime le coût pour atteindre la destination depuis le nœud donné. La fonction d'évaluation est définie comme f(n) = g(n) + h(n).