La semaine dernière, nous avons découvert le fonctionnement du légendaire algorithme de coordination de la marche BigDog. Le robot n'était pas encore autonome et ne pouvait traverser le terrain que sous le contrôle de l'opérateur.
La plupart des lecteurs ont approuvé la dernière fois l'idée d'une nouvelle traduction - sur la façon dont BigDog a appris à se rendre indépendamment au bon point et à naviguer dans l'espace. Eh bien, en fait, le voici. Le système de navigation BigDog utilise une combinaison de balayage laser planaire, de vision stéréo et de perception proprioceptive. Avec son aide, l'emplacement du robot dans le monde environnant est déterminé. Elle découvre les obstacles et les place dans un modèle bidimensionnel du monde. Elle planifie ensuite le chemin et contrôle le robot pour suivre le chemin choisi. Le planificateur de chemin est une variante de l'algorithme de recherche A * classique. L'algorithme de lissage traite les résultats et les transmet à l'algorithme de suivi de chemin. Il calcule les commandes de direction pour BigDog.
Le système décrit a été testé dans une zone forestière avec de nombreux arbres, rochers et sous-bois. En plus des territoires plats, il avait également des pentes (angles allant jusqu'à 11 degrés). Au total, 26 tests ont été effectués, dont 88% ont réussi. Le robot a "vu" le terrain dans un rayon de 130 mètres en se déplaçant à une vitesse donnée et a surmonté plus de 1,1 km.
Équipement
1) Capteurs proprioceptifsUtilisé pour contrôler la démarche BigDog et la navigation autonome. Chacun des 16 degrés de liberté actifs et 4 passifs du robot est équipé d'un capteur. Ils fournissent des données sur la position et la charge actuelles. Ces informations sont combinées avec des données IMU pour évaluer l'état de contact avec le sol, la hauteur du corps, la vitesse du corps. En outre, un certain nombre de capteurs indiquent l'état des systèmes de propulsion, de calcul, hydrauliques, thermiques et autres BigDog.
Capteurs BigDog: a) antenne GPS; b) lidar; c) caméra stéréo Bumblebee; d) Honeywell IMU; e) capteurs communs.2) Capteurs extéroceptifsLe robot est équipé de quatre capteurs externes: le lidar SICK LMS 291, la caméra stéréo Bumblebee PointGrey, le récepteur GPS NovAtel et le Honeywell IMU. Les données qu'ils contiennent pénètrent dans le système illustré dans le diagramme ci-dessous.
3) OrdinateursPour implémenter le système avec le schéma ci-dessus, deux ordinateurs sont utilisés. L'ordinateur principal BigDog est un PC104 avec un processeur Intel Pentium M monocœur (1,8 GHz). Il interagit avec des capteurs proprioceptifs, contrôle l'équilibre et les mouvements du robot, calcule le modèle actuel de l'environnement et le chemin à travers celui-ci, et contrôle également la démarche.
La vision est fournie par un ordinateur séparé avec un processeur Intel CoreDuo (1,7 GHz). Il communique avec une paire de caméras, détecte les incohérences, évalue l'odométrie visuelle et prend en charge une carte du relief 3D. Cet ordinateur transmet la carte et les données d'odométrie visuelle à l'ordinateur hôte à une fréquence de 15 Hz via le réseau local embarqué.
L'avantage d'un tel système est la possibilité de simplifier la tâche de planification en la divisant en deux parties. Les données du lidar et des capteurs sont en trois dimensions, mais nous pouvons compter sur l'auto-stabilisation du système de contrôle de la marche pour abandonner la perception et la planification 3D plus complexes.
Approche technique
Dans notre approche technique générale, nous utilisons les données de deux capteurs environnementaux pour détecter les obstacles, calculer le chemin à travers ou autour des obstacles, et commander au système de contrôle de la marche du robot de suivre un chemin donné.
L'ensemble du processus peut être divisé en trois étapes. Tout d'abord, les images du lidar et de la caméra sont traitées pour obtenir une liste de points indiquant les obstacles dans l'environnement. Ces points sont ensuite divisés en objets disjoints et suivis pendant un certain temps. De plus, ces objets sont combinés dans la mémoire temporaire pour le mappage. Ce graphique est utilisé pour planifier la direction du voyage vers une destination intermédiaire. L'ordonnanceur est conçu pour contrôler que les trajectoires BigDog sont à la bonne distance des obstacles et que les trajectoires sont stables dans l'espace pendant les itérations de l'ordonnanceur. L'algorithme de mouvement le long d'une trajectoire donnée oblige le robot à suivre le chemin prévu, en envoyant des commandes de vitesse au système de contrôle de la marche. Elle déplace alternativement les membres du robot.
A. Collecte d'informations
1) Évaluation de la situationIl existe deux sources d'informations odométriques: des capteurs cinématiques dans les jambes et un système de vision artificielle. Les données obtenues sont combinées pour évaluer l'emplacement du robot.
Le système odométrique utilise les informations cinématiques des jambes pour calculer les mouvements du robot. Et le système d'odométrie visuelle surveille les caractéristiques visuelles pour calculer le mouvement. Ces deux outils utilisent un module de mesure inertielle (IMU) comme source d'information pour l'orientation spatiale. Un compteur général combine la sortie de ces deux odomètres, en se concentrant sur l'odométrie visuelle à basse vitesse et la cinématique à haute vitesse. La combinaison de ces deux indicateurs élimine les défauts de chacun des compteurs: la défaillance éventuelle des systèmes stéréo, la dérive des relevés du compteur kilométrique situés dans les membres lors du fonctionnement en place, ainsi que les erreurs de ce capteur le long de l'axe vertical.
Le lidar utilisé dans le robot BigDog produit une nouvelle image toutes les 13 millisecondes. Chaque image est transformée en un système de coordonnées externes avec le centre à l'emplacement du robot. Dans ce cas, les informations synchronisées dans le temps du compteur d'emplacement sont utilisées. Le nuage de points 3D résultant est ensuite transmis pour traitement par l'algorithme de segmentation décrit ci-dessous. De même, le système de vision stéréoscopique recueille des cartes de non-conformité pendant un certain temps pour créer une carte de terrain 3D dans un carré de 4 x 4 mètres centré sur le robot. Le filtre spatial détermine les zones de changements d'altitude significatifs (c'est-à-dire les obstacles potentiels) et transmet une liste de points appartenant à ces zones à l'algorithme de segmentation des nuages de points.
2) Segmentation des nuages de points et suivi des objetsEn raison des irrégularités de la terre et des mouvements du robot, une partie des données du scanner lidar comprendra des images de la terre. Les réflexions des longs obstacles (tels que les murs) sont similaires en apparence aux réflexions de la surface de la terre. Pour un fonctionnement réussi, le système doit interpréter ces réflexions de manière à pouvoir contrôler le robot près des murs et ne pas avoir «peur» de la terre. La première étape de ce processus est la segmentation des points d'obstacles fournis par le lidar et la carte du terrain en objets séparés. Les nuages de points 3D rares sont segmentés en objets en fusionnant des points individuels séparés par une distance inférieure à 0,5 mètre.
Les objets obtenus grâce à l'algorithme de segmentation sont suivis pendant un certain temps. Pour accomplir cette tâche, nous utilisons un algorithme itératif gourmand avec des contraintes heuristiques. L'objet dans l'image actuelle coïncide avec l'objet le plus proche de la dernière image, à condition que les objets soient séparés par une distance ne dépassant pas 0,7 mètre.
En raison du fait que les nuages de points sont segmentés en objets et suivis pendant un certain temps, le robot peut se déplacer de manière adéquate dans l'environnement avec une inégalité modérée de la terre et divers types d'obstacles: arbres, pavés, billes tombées, murs. Les arbres et les murs sont déterminés principalement par un scanner lidar, et les pavés et les journaux sont déterminés par un système de vision stéréoscopique.
Une séquence d'illustrations montrant un robot (rectangle jaune) avec: a) des données d'un lidar (points bleus) enregistrées en quelques secondes; b) leurs installations respectives. Les grands objets bruns sont des arbres. Les réflexions au sol sont affichées transparentes et plates. Le cylindre vert est le but; la ligne bleue du chemin calculé y mène. c) Vue de dessus du cartogramme: les zones avec la valeur létale la plus faible sont indiquées en vert, et les zones avec la valeur la plus élevée sont indiquées en violet. Chaque unité de grille correspond à 5 mètres.Planification de la navigation
Notre approche pour résoudre le problème de navigation est généralement acceptée dans la communauté robotique. Les points d'obstacles (obtenus grâce aux processus de perception) sont tracés sur un cartogramme avec le centre à l'emplacement du robot. La cible finale du robot est projetée sur la frontière du cartogramme, et une variante de l'algorithme A ∗ lui est appliquée. Ce processus est répété environ une fois par seconde.
1) Mémoire des obstacles suivisEn raison du champ de vision limité des deux capteurs du robot, il est impératif que le robot conserve une mémoire précise des obstacles qu'il ne peut plus voir. Comme la liste des objets est fournie par le système de suivi des objets, des objets individuels sont ajoutés, mis à jour ou supprimés dans la mémoire d'objets du système de planification. La taille de la liste d'objets est limitée, donc lorsque de nouveaux objets y sont ajoutés, d'autres doivent être supprimés.
En dénotant la liste actuelle des objets de la variable O, nous pouvons calculer deux sous-classes paramétrées de O:
Ici l'âge (q) est la différence entre l'heure actuelle et l'heure de la dernière mesure de l'objet q,
norm (q, r) inf - la distance minimale entre l'emplacement actuel du robot et la limite de l'objet q.
Les objets sont supprimés de O selon les critères suivants:- L'ensemble {P (30) ∩ Q (15)} est soustrait de O. Il s'agit d'objets de plus de 30 secondes et situés à moins de 15 mètres du robot.
- L'ensemble {P (1800) ∩ Q (10)} est soustrait de O. Ce sont des objets de plus d'une demi-heure et situés à moins de 10 mètres du robot.
- Les objets sont supprimés de O lorsque la limite de liste est atteinte. La priorité de l'objet est déterminée par le temps pendant lequel il a été suivi avec succès par le tracker. En d'autres termes, les objets que le robot «regardait» plus longtemps sont stockés plus longtemps en mémoire.
- Cependant, aucun objet suivi au cours des 10 dernières secondes n'est rejeté.
Cette allocation de ressources mémoire conduit au comportement suivant: lorsque les objets quittent le champ de vision des capteurs du robot, il oublie les objets supprimés et les objets qu'il n'a pas vus plusieurs fois. Les objets en vue ou inaccessibles, mais situés à proximité du robot, ne sont pas oubliés.
2) Création d'un cartogrammeNous utilisons un cartogramme créé sur la base d'une grille 2D pour représenter l'environnement entourant le robot. Au lieu de créer dynamiquement un cartogramme (lorsque le robot reçoit de nouvelles informations environnementales), un nouveau cartogramme est compilé à chaque itération de la planification et rempli d'objets de la mémoire de l'ordonnanceur. Il s'ensuit que le planificateur d'itinéraire dynamique ne peut pas être utilisé à la place de l'algorithme A *. Étant donné que nous supposons que la taille des objets est limitée (que l'absence d'impasse dans l'environnement représente plus de la moitié de la carte), la portée de la tâche de planification et le temps pour calculer le chemin sont petits.
Le cartogramme est rempli de valeurs de la liste d'objets conformément à l'algorithme suivant:
Les cellules où se trouvent les objets se voient attribuer une valeur létale très élevée. L'indicateur pour les cellules proches de l'objet est réglé en fonction de la fonction f, qui prend en compte la distance actuelle jusqu'à ce point. Pour les résultats des tests présentés ici, f était simplement le cube inverse de la distance.
L'effet de cette approche est qu'elle décroît progressivement des cellules de très grande valeur en s'éloignant d'elles (et des objets qu'elles désignent).
3) Stabilité du cheminPour nous assurer que nous ne «contrôlons» pas BigDog de manière aléatoire et non systématique, une attention particulière est accordée à la stabilité du chemin planifié. Il doit être aussi stable que possible grâce aux itérations du planificateur de trajet. Ceci est fourni de trois manières.
Premièrement, le point de départ passé à l'algorithme A * n'est pas la position actuelle du robot, mais la projection de sa position au point final du chemin donné précédemment par l'algorithme A * (appelons ce point p). Tant que BigDog suit le chemin prévu, il peut en dévier légèrement latéralement. En projetant le point de départ sur le point du calcul précédent de l'algorithme A *, nous filtrons la fluctuation de la position du robot, et les trajets affichés par l'ordonnanceur deviennent plus stables. Si le robot s'écarte de la trajectoire plus que la valeur définie (par défaut, il est de 3 mètres), le point p est simplement transféré à la position actuelle du robot.
Deuxièmement, afin de vérifier la continuité du planificateur de trajet, nous calculons q - la projection de la position du robot de 2,5 secondes dans le passé au dernier point calculé par l'algorithme A *. Ensuite, le segment du dernier chemin planifié de q à p est ajouté au calcul du nouveau chemin. En conséquence, le robot suit une petite distance déjà parcourue. Grâce à cela, l'algorithme de suivi du chemin se montre mieux avec des violations importantes de la position, qui sont souvent rencontrées par des robots sur leurs pieds.
Troisièmement, une partie de l'historique des trajets planifiés est stockée dans la mémoire du robot. Ces chemins sont utilisés pour réduire les valeurs des cellules du cartogramme où le robot est déjà parti, tout en augmentant la valeur des cellules dans la zone environnante. Par conséquent, en règle générale, un nouveau chemin planifié dans la même direction répétera le chemin déjà parcouru par le robot (mais sans garantie stricte).
4) Lissage de trajectoireLe chemin calculé, puisqu'il est basé sur une grille régulière, est un peu dentelé. Des changements de direction importants peuvent provoquer des commandes de contrôle indésirables. Pour éviter cela, l'algorithme de lissage De Boer est appliqué.
De plus, la planification de chemin basée sur la grille conduit souvent à des chemins techniquement optimaux mais moins souhaitables vers la cible. Nous résolvons ce problème en calculant un chemin lissé pour chaque itération de l'ordonnanceur. Pour les itérations suivantes, les cellules du cartogramme où le chemin lissé s'exécute se voient attribuer une valeur inférieure. Cela fournit un chemin plus direct et plus fluide vers l'objectif.
C. Contrôle de la marche: mobilité et équilibre
Le système de planification de la navigation détermine un nouveau trajet environ une fois par seconde. Un algorithme de suivi d'un chemin qui fonctionne à une fréquence de 200 Hz guide le robot en fonction du dernier chemin prévu. Cet algorithme crée un ensemble de commandes sous la forme des vitesses corporelles souhaitées, y compris la vitesse d'avancement, la vitesse latérale et la vitesse de lacet du corps. Ces vitesses sont transmises au contrôleur de marche, qui contrôle le mouvement des jambes.
En fonction de la distance entre le robot et le chemin, l'une des trois stratégies est utilisée. Si le robot est situé près d'une section du chemin, il commence à se déplacer en diagonale jusqu'à ce qu'il y pénètre par le côté, se déplaçant à pleine vitesse. Si le robot est loin du chemin, il dirige exactement vers l'avant jusqu'au point souhaité. Dans une position intermédiaire, une combinaison de ces stratégies est utilisée.
Une description détaillée des algorithmes de contrôle de la marche dépasse le cadre de cet article. Cependant, en règle générale, les vitesses corporelles agissent comme des entrées de contrôle pour les contrôleurs de démarche BigDog de bas niveau. Le contrôleur de marche produit des commandes de force et de position pour chaque articulation pour assurer la stabilité, répond aux anomalies et fournit les vitesses corporelles nécessaires. Bien que les calculs de l'algorithme d'investigateur de trajectoire puissent être utilisés pour n'importe quelle démarche BigDog, le trot est optimal en raison de la vitesse et de la capacité à traverser un terrain accidenté.
Résultats des tests sur le terrain
Le capteur et le système de navigation décrits ci-dessus ont été installés sur BigDog et testés en dehors du laboratoire. Les tests ont été effectués dans une zone où il y avait beaucoup d'arbres, de rochers, de sous-bois, de collines avec des pentes allant jusqu'à 11 degrés. La figure 1 montre des exemples de paysage. La figure 2 montre les données du lidar traitées par le robot.
Fig. 1. Le terrain où les tests ont été effectuésFig. 2. Test, vue de dessus. Image reçue du lidar et des caméras stéréo. Les zones sombres sont des arbres et d'autres obstacles. Le maillage est de 5 mètres.Le système de navigation et le planificateur ont été développés sur une période de 7 mois, avec des tests réguliers environ une fois toutes les cinq semaines. Les résultats des derniers tests sont décrits ici.
Sur les 26 tests effectués, 23 se sont terminés avec succès: le robot a atteint le but, n'a rencontré aucun obstacle et n'était pas près de cela. Les résultats de ces tests sont marqués dans le tableau croisé dynamique comme objectif. Le robot est tombé à la fin d'un seul test après avoir marché sur une petite pierre. Habituellement, le système de contrôle de la marche fait face à de telles situations, mais pas cette fois (le résultat est marqué dans le tableau comme Automne - «Automne»). Lors de trois tests, le robot a rencontré de gros obstacles (plus de 20 mètres de large). Le robot a calculé de quel côté il était préférable de contourner l'obstacle et n'a pas avancé dans un laps de temps donné (20 secondes). Des obstacles de cette taille dépassent le cadre pour lequel un système autonome a été développé. Les résultats de ces tests sont indiqués dans le tableau comme Live-lock.
Dans ces 26 tests, le robot a été placé dans des scénarios assez similaires et au milieu de la forêt. À mesure que l'environnement devient plus complexe, le nombre de résultats de verrouillage en direct augmente et le robot sélectionne des chemins moins efficaces.
Plus intéressant - sur robo-hunter.com :
YouTube