Réponse rapide
A* explore une grille ou un graphe en combinant le coût déjà parcouru et une estimation du coût restant vers le but. Il développe les nœuds les plus prometteurs jusqu’à trouver une route ou constater qu’aucune n’est accessible.
Additionner les critères
Chaque arête reçoit un coût de distance, pente, risque ou énergie. Les cellules interdites sont exclues, tandis que les marges autour des obstacles peuvent augmenter le coût sans fermer le passage.
Estimer le chemin restant
L’heuristique guide la recherche vers le but. Si elle ne surestime pas le coût réel, A* conserve une garantie d’optimalité par rapport au graphe défini.
Contrôler la route produite
La route est simplifiée puis vérifiée avec le gabarit, la dynamique et les obstacles actuels. Une carte incomplète peut donner une route mathématiquement valide mais impraticable.
Sources et références
- [1] Robotics and Autonomous Systems — NIST