Recherche du plus court chemin - Algorithmes de Djkstra et A-star

De nombreux systèmes industriels automatisés doivent résoudre en temps réel le problème de la navigation autonome : un robot d'entrepôt (AGV), un drone de livraison ou un véhicule à conduite autonome doit relier un point de départ à une destination en évitant les obstacles, tout en minimisant la distance ou le temps de trajet.

Pour modéliser l'environnement de déplacement, on représente l'espace sous forme d'une grille discrète, ici une image en niveaux de gris, dans laquelle chaque pixel accessible constitue un noeud, et chaque déplacement possible une arête pondérée par la distance réelle parcourue. C'est l'objet de la Partie 1.

Ce maillage spatial se formalise ensuite naturellement comme un graphe, dont la structure de données associée (dictionnaire de voisins) est construite en Partie 2. On dispose alors d'une représentation exploitable par des algorithmes de recherche de chemin.

La Partie 3 met en oeuvre l'algorithme de Djkstra, qui garantit le chemin optimal trouvé en explorant le graphe de manière exhaustive depuis le départ, au prix d'un coût calculatoire parfois élevé pour les grands environnements.

La Partie 4 introduit l'algorithme A-star, qui guide la recherche grâce à une heuristique géométrique (distance à vol d'oiseau), réduisant significativement le nombre de noeuds explorés. C'est cette capacité à prioriser l'exploration qui rend A-star incontournable dans les systèmes embarqués à ressources limitées.

Dans la suite, nous allons mettre en application ces principes pour trouver le plus court chemin à réaliser sur une image en noir et blanc entre un départ et une arrivée en ne considérant que les mouvements possibles ←↙↓↘→↗↑↖. Les pixels noirs seront des obstacles, les blancs des cases accessibles.