Qu'est-ce que l'algorithme A* (A star) ?

L'algorithme A* (prononcé "A étoile") est un algorithme de recherche de chemin dans un graphe, entre un nœud initial et un nœud final. Il est largement utilisé en intelligence artificielle et en robotique pour trouver des chemins optimaux.

A* combine les avantages de l'algorithme de Dijkstra (qui garantit un chemin optimal) et de la recherche gloutonne (qui est efficace). Il utilise une fonction heuristique pour estimer le coût restant jusqu'à la destination, ce qui le rend très efficace pour trouver des solutions optimales.

Le savais-tu ?

L'algorithme A* a été développé en 1968 par Peter Hart, Nils Nilsson et Bertram Raphael. Il est considéré comme l'un des algorithmes de recherche de chemin les plus performants lorsqu'une bonne heuristique est disponible.

Principe Général de l'algorithme A*

A* fonctionne en maintenant une liste de nœuds à explorer (open list) et une liste de nœuds déjà explorés (closed list). À chaque étape, il sélectionne le nœud le plus prometteur selon la fonction d'évaluation :

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

Où :

  • g(n) est le coût du chemin du nœud de départ au nœud n
  • h(n) est l'estimation heuristique du coût du chemin du nœud n au nœud d'arrivée
  • f(n) est le coût total estimé du chemin passant par n

L'algorithme est complet (il trouvera toujours une solution si elle existe) et optimal (il trouvera la solution la moins coûteuse) si l'heuristique est admissible (ne surestime jamais le coût réel).

Comment appliquer cette notion au projet ?

Dans un projet de robotique ou de jeu vidéo, A* peut être utilisé pour :

  • Calculer des trajectoires optimales pour un robot
  • Trouver le chemin le plus court dans un labyrinthe ou une carte
  • Planifier des déplacements en évitant les obstacles
  • Optimiser les déplacements d'unités dans un jeu de stratégie

Implémentation de l'algorithme A* 
def a_star(start, goal, graph):
    open_set = PriorityQueue()
    open_set.put(start, 0)
    came_from = {}
    g_score = {node: float('inf') for node in graph}
    g_score[start] = 0
    f_score = {node: float('inf') for node in graph}
    f_score[start] = heuristic(start, goal)

    while not open_set.empty():
        current = open_set.get()

        if current == goal:
            return reconstruct_path(came_from, current)

        for neighbor in graph.neighbors(current):
            tentative_g_score = g_score[current] + graph.cost(current, neighbor)
            
            if tentative_g_score < g_score[neighbor]:
                came_from[neighbor] = current
                g_score[neighbor] = tentative_g_score
                f_score[neighbor] = g_score[neighbor] + heuristic(neighbor, goal)
                if neighbor not in open_set:
                    open_set.put(neighbor, f_score[neighbor])

    return None  # Pas de chemin trouvé

Dans quelle partie du code peut intervenir l'algorithme A*?

Système de navigation

Dans un système de navigation autonome, A* peut être utilisé pour calculer le chemin optimal entre la position actuelle et la destination.

Exemple pratique :

Pour un robot de livraison dans un entrepôt, A* peut calculer le chemin le plus court entre les rayonnages en tenant compte des allées, des obstacles fixes et des zones à éviter.

Objectif : Implémenter A* pour permettre au robot de trouver son chemin de manière autonome tout en optimisant la distance parcourue.

Références

  • James, G., Witten, D., Hastie, T., & Tibshirani, R. (2013). An Introduction to Statistical Learning. Springer.
  • Montgomery, D. C., Peck, E. A., & Vining, G. G. (2021). Introduction to Linear Regression Analysis. Wiley.
  • Pedregosa, F., et al. (2011). Scikit-learn: Machine Learning in Python. Journal of Machine Learning Research.
  • Galton, F. (1886). Regression Towards Mediocrity in Hereditary Stature. The Journal of the Anthropological Institute.