Dévoiler l'algorithme de planification dynamique de la trajectoire dans les AGV

Dans les secteurs modernes de l'entreposage, de la logistique et de la fabrication, les véhicules à guidage automatique (AGV) sont de plus en plus répandus. Telles des fourmis laborieuses, ils naviguent de manière autonome dans des environnements complexes et accomplissent efficacement les tâches de manutention. L'une des technologies de base permettant aux AGV de parvenir à une navigation intelligente est la planification des trajectoires. En particulier lorsque l'environnement n'est pas statique, les capacités de planification dynamique des chemins deviennent cruciales. Cet article se penche sur plusieurs algorithmes de planification dynamique des chemins (tels que A, Dijkstra, RRT, etc.) et explique comment ils ont un impact significatif sur l'industrie des AGV.

Pourquoi la planification dynamique des itinéraires est-elle nécessaire ?

La planification statique traditionnelle des trajectoires suppose que l'environnement est parfaitement connu et reste inchangé pendant que l'AGV exécute ses tâches. Cependant, le monde réel est plein de variables :

• Obstacles temporaires apparaissant soudainement (tels que des cargaisons tombées, des piétons ou d'autres véhicules)
• Modification des zones de contrôle du trafic
• Ajustements temporaires des points cibles ou des tâches

Dans ces situations, les AGV doivent être capables de détecter les changements dans leur environnement en temps réel et de réorganiser rapidement leurs itinéraires. C'est là que la planification dynamique des trajets entre en jeu. Elle donne aux AGV l'intelligence nécessaire pour s'adapter à des circonstances changeantes, ce qui leur permet de continuer à fonctionner de manière sûre et efficace dans des environnements complexes et dynamiques.

Analyse des principaux algorithmes de planification des trajets

1. Algorithme de Dijkstra

L'algorithme de Dijkstra est un algorithme classique de recherche dans les graphes utilisé pour trouver le chemin le plus court entre un nœud source unique et tous les autres nœuds d'un graphe.

‍CoreIdea :

En partant du nœud source, l'algorithme se propage vers l'extérieur comme des ondulations dans l'eau. À chaque fois, il visite le nœud non visité le plus proche du nœud source et met à jour les distances avec ses voisins.

Processus:‍

• Initialisation : Fixer la distance du point de départ à 0 et les distances des autres points à l'infini. Créez une file d'attente prioritaire des nœuds à visiter (triés par distance).
• Itération : Retirer de la file d'attente le nœud u dont la distance est la plus faible.
• Relaxation : Pour chaque voisin v de u, si le chemin de u à v est plus court, mettre à jour la distance de v et l'ajouter à la file d'attente.
• Marquer : Marquer u comme visité.  
• Répéter : continuer jusqu'à ce que le nœud cible soit récupéré ou que la file d'attente soit vide.  

AGV Application :  

• Avantages : Garantit la recherche du plus court chemin global (lorsque les poids des arêtes ne sont pas négatifs).  
• Inconvénients : Large champ de recherche, pas de directionnalité, faible efficacité de calcul (en particulier sur les cartes de grande taille). Les obstacles dynamiques nécessitent de recalculer la trajectoire globale, ce qui entraîne des performances médiocres en temps réel.
• Positionnement : Souvent utilisé comme base pour d'autres algorithmes (tels que A*) ou dans des environnements simples.

2. Algorithme A*

L'algorithme A* (A-Star) est une optimisation de l'algorithme de Dijkstra. Il introduit des informations heuristiques pour guider la direction de la recherche, ce qui permet de trouver la cible plus rapidement.

 Idée maîtresse : Lors de la sélection du prochain nœud à visiter, les éléments suivants doivent être pris en compte simultanément :

• g(n) : Le coût réel du chemin entre le point de départ et le nœud n.
• h(n) : Le coût estimé entre le nœud n et l'objectif (une fonction heuristique, telle que la distance de Manhattan/Euclidean).  
• Fonction d'évaluation : f(n) = g(n) + h(n)  
• Exigences clés : h(n) doit être admissible (valeur estimée ≤ valeur réelle) et cohérent pour garantir la recherche de la solution optimale.

 Processus : Similaire à celui de Dijkstra, mais la file d'attente est triée par f(n), et les nœuds ayant le plus petit f(n) sont prioritaires pour l'expansion, ce qui rend la recherche plus directionnelle vers l'objectif.

 AGV Application :

• Avantages : Garantit la trajectoire optimale lorsque la fonction heuristique remplit les conditions et est généralement beaucoup plus efficace que Dijkstra. Largement utilisé dans la planification globale de la trajectoire des véhicules autoguidés.
• Inconvénients : Les performances sont influencées par le choix de la fonction heuristique ; la consommation de mémoire peut être élevée ; une replanification est toujours nécessaire lorsque l'environnement change fréquemment.
• Variantes dynamiques : Des algorithmes tels que D*, LPA* et D* Lite sont disponibles pour traiter les environnements dynamiques. Ces algorithmes peuvent mettre à jour les trajectoires de manière incrémentale (plutôt que de les recalculer entièrement) lorsque l'environnement change, ce qui améliore considérablement la vitesse de réaction. D* Lite est un algorithme couramment utilisé pour l'évitement dynamique des obstacles dans les AGV.

3. Algorithme RRT

RRT* (Rapidly-exploring Random Tree Star) est un algorithme de planification de trajectoire basé sur l'échantillonnage qui est particulièrement adapté aux espaces de haute dimension et aux contraintes complexes (telles que la cinématique des véhicules).

Idée maîtresse :

En échantillonnant aléatoirement des points dans l'espace d'état, l'algorithme développe progressivement un arbre à partir de l'origine pour explorer l'espace. RRT* est une version optimisée de RRT, incorporant une étape de recâblage pour permettre au chemin de s'approcher asymptotiquement de l'optimalité (plus il y a de points d'échantillonnage, plus le chemin est proche de l'optimalité).  

Processus :  

• Échantillonnage : Générer aléatoirement un point x_rand dans l'espace d'état.
• Trouver le voisin le plus proche : Localiser le nœud x_nearest dans l'arbre qui est le plus proche de x_rand.
• Extend (Steer) : Étendre une longueur de pas de x_nearest à x_rand (en évitant les obstacles) pour obtenir le nouveau nœud x_new.
• Sélectionner le nœud parent (spécifique à la RRT*) : Recherche des nœuds proches de x_new et sélectionne le nœud x_min qui minimise le coût total du chemin depuis le point de départ jusqu'à x_new en tant que nœud parent (les collisions doivent être évitées).
• Rewire (spécifique au RRT*) : Rechercher les nœuds proches de x_new. Si le fait de passer par x_new réduit le coût total du chemin, mettre à jour les nœuds parents de ces nœuds vers x_new.  
• Ajouter : Ajouter x_new et ses arêtes connectées à l'arbre.  
• Répétition : continuer jusqu'à ce que l'arbre s'étende à proximité de la zone cible.  

 AGV Application :

• Avantages : Forte capacité à gérer des états à haute dimension (pose, vitesse, etc.) et des contraintes complexes ; aucune carte explicite de l'environnement n'est nécessaire ; exhaustivité probabiliste (si un chemin existe, il finira par être trouvé) ; RRT présente une optimalité asymptotique.  
• Inconvénients : Les trajectoires ne sont pas strictement optimales (à moins d'utiliser un échantillonnage infini) ; les trajectoires peuvent ne pas être lisses (un post-traitement est nécessaire) ; les performances sont sensibles aux paramètres ; la convergence peut être lente.
• Variantes dynamiques : par exemple, Dynamic RRT, qui permet de replanifier en supprimant/mettant à jour les parties de l'arbre qui entrent en collision avec des obstacles dynamiques et qui continuent à croître.

Applications pratiques de la planification dynamique des trajectoires dans les AGV

Scénarios d'application de l'évitement d'obstacles par l'AGV

Dans les applications AGV réelles, un algorithme unique est rarement utilisé seul ; au contraire, une combinaison d'algorithmes est généralement employée :

1. Planification globale de la trajectoire :

En utilisant A* ou ses variantes (telles que D-Lite) ou parfois une version optimisée de l'algorithme de Dijkstra, un chemin global optimal ou sous-optimal est planifié du point de départ à la destination sur une carte connue. Ce chemin est généralement assez macro.

2. Planification locale de la trajectoire/évitement dynamique des obstacles :  

Tout en suivant la trajectoire globale, l'AGV utilise des capteurs (tels que des lidars ou des caméras) pour détecter en permanence le milieu environnant. Lorsqu'un obstacle inattendu (statique ou dynamique) est détecté, le planificateur local (qui peut être basé sur la DWA - Dynamic Window Approach, TEB - Timed Elastic Band, ou une variante de l'A/RRT avec replanification rapide) intervient pour générer une trajectoire locale d'évitement des obstacles à court terme, sûre et limitée par la cinématique du véhicule, sous l'égide de la trajectoire globale.

3. Suivi de la trajectoire :

L'algorithme de contrôle est responsable de la conduite précise de l'AGV le long de la trajectoire prévue (qu'elle soit globale ou locale).

Cette stratégie de planification hiérarchique permet d'équilibrer l'optimalité globale et les performances locales en temps réel. Les algorithmes tels que D Lite excellent dans la gestion des changements dynamiques locaux grâce à leurs capacités de replanification incrémentale efficace. RRT et ses variantes, en revanche, sont plus avantageux pour gérer les environnements complexes et les contraintes de mouvement.

Défis et tendances futures

1. Les défis

Malgré les progrès significatifs de la technologie de planification dynamique des trajectoires, des défis subsistent dans les applications industrielles des véhicules autoguidés :

• Exigences en temps réel : Les algorithmes doivent effectuer des calculs en quelques millisecondes, en particulier dans le cadre d'opérations à grande vitesse ou de scénarios de trafic dense.
• Incertitude environnementale : Bruit des capteurs, erreurs de positionnement et difficultés à prévoir les obstacles dynamiques.
• Coordination multi-AGV : Éviter les conflits et les blocages pour parvenir à une collaboration efficace.
• Contraintes cinématiques complexes : Prise en compte de la taille de l'AGV, de son rayon de braquage et de ses performances en matière d'accélération et de décélération.

2. Tendances futures

À l'avenir, la planification dynamique des trajets évoluera vers des solutions plus intelligentes et plus efficaces :

• Intégration de l'apprentissage automatique : Utilisation de l'apprentissage par renforcement, de l'apprentissage par imitation et d'autres méthodes pour permettre aux AGV d'apprendre de manière autonome les stratégies de navigation optimales.
• Planification prédictive : Prévoir les intentions et les trajectoires d'autres obstacles dynamiques (tels que les piétons et les véhicules) afin de planifier à l'avance.
• Compréhension sémantique : Permettre aux AGV de comprendre les informations sémantiques de l'environnement (telles que "trottoir" et "zone de chargement") afin de prendre des décisions mieux adaptées au scénario.
• Collaboration homme-machine : Réaliser une interaction et un évitement plus sûrs et plus naturels dans les environnements de coexistence homme-machine.

Conclusion

Dijkstra, A, RRT et leurs variantes dynamiques sont des outils essentiels de la bibliothèque d'algorithmes de planification dynamique de trajectoire de l'AGV. Ils servent d'"yeux intelligents" et de "volant dynamique" à l'AGV, lui permettant de naviguer dans des environnements complexes avec souplesse et efficacité. Il est essentiel de comprendre les principes et les caractéristiques de ces algorithmes pour faire progresser la technologie AGV et le domaine plus large de l'automatisation. Avec l'évolution des algorithmes et l'amélioration de la puissance de calcul, les futurs AGV deviendront sans aucun doute plus intelligents, plus fiables et plus efficaces.

AiTEN Robotics, dont le siège se trouve à Suzhou, en Chine, est un leader mondial dans le domaine des véhicules industriels autonomes (AMR/AGV) et des solutions d'automatisation logistique. AiTEN Robotics a développé dix séries de produits pour répondre aux besoins de scénarios de manutention complets. AiTEN Robotics a déployé plus de 200 projets dans plus de 30 pays et régions, et de nombreuses entreprises du Fortune 500 lui font confiance dans des secteurs tels que l'automobile, l'alimentation et les boissons, les produits chimiques, les produits pharmaceutiques, la fabrication et la logistique de tiers, en améliorant la sécurité opérationnelle, l'efficacité et la préparation à l'avenir.