Histogramme de champs de vecteurs
En robotique, l'histogramme de champ de vecteurs (VFH pour l'anglais Vector Field Histogram) est un algorithme de planification de mouvement en temps réel proposé par Johann Borenstein et Yoram Koren en 1991[1] une grande importance accordée à la gestion de l’incertitude liée aux erreurs de capteur et de modélisation. Contrairement aux autres algorithmes d'évitement d'obstacles, le VFH prend en compte la dynamique et la forme du robot, et renvoie des commandes de pilotage spécifiques à la plate-forme. Considéré comme un planificateur de chemin local, c’est-à -dire non conçu pour une optimalité de chemin global, il a été démontré que le VFH produisait des chemins presque optimaux.
L'algorithme VFH d'origine était basé sur des travaux antérieurs sur Virtual Force Field, un algorithme de planification de trajectoire locale. VFH a été mis à jour en 1998 par Iwan Ulrich et Johann Borenstein, et renommé VFH+ (officieusement « Enhanced VFH »)[2]. L’approche a été mise à jour à nouveau en 2000 par Ulrich et Borenstein et a été renommée VFH*[3]. Le VFH est actuellement l’un des concepteurs locaux les plus populaires utilisés en robotique mobile, concurrençant l’approche de la fenêtre dynamique développée ultérieurement. De nombreux outils de développement robotiques et environnements de simulation contiennent un support intégré pour le VFH, tel que dans le projet Player[4].
VFH
L’histogramme de champs de vecteurs a été développé dans le but d’être performant sur le plan informatique, robuste et insensible aux erreurs de lecture. En pratique, l’algorithme VFH s’est avéré rapide et fiable, en particulier lors de la traversée de parcours d’obstacles densément peuplés.
L'utilisation de la représentation statistique des obstacles au moyen de grilles d'histogramme est au centre de l'algorithme VFH (voir aussi la grille d'occupation). Une telle représentation est bien adaptée aux données de capteur imprécises et permet la fusion de lectures de capteurs multiples.
L'algorithme VFH contient trois composantes principales :
- Une grille d'histogramme cartésien : une grille d'histogramme cartésienne à deux dimensions est construite avec les capteurs de distance du robot, tels qu'un sonar ou un télémètre laser. La grille est continuellement mise à jour en temps réel.
- Un histogramme polaire : un histogramme polaire unidimensionnel est construit en réduisant l'histogramme cartésien autour de la position momentanée du robot.
- Une vallée candidate : les secteurs consécutifs dont la densité d'obstacles polaires est inférieure au seuil, appelés vallées candidates, sont sélectionnés en fonction de la proximité de la direction de la cible.
Une fois que le centre de la direction candidate sélectionnée est déterminé, l'orientation du robot est modifiée pour correspondre. La vitesse du robot est réduite à l'approche d'obstacles.
VFH+
Les améliorations de l’algorithme VFH+ comprennent :
- Un hystérésis de seuil : une hystérésis augmente la finesse de la trajectoire prévue.
- La taille du corps du robot : différentes tailles de robot sont prises en compte, ce qui évite de devoir ajuster manuellement les paramètres via des filtres passe-bas.
- Une perspective d'obstacles : les zones bloquées par des obstacles sont masquées dans le VFH+, de sorte que l'angle de braquage ne soit pas dirigé vers un obstacle.
- Une fonction de coût : une fonction de coût a été ajoutée afin de mieux caractériser les performances de l'algorithme et offre également la possibilité de basculer entre les comportements en modifiant la fonction de coût ou ses paramètres.
VFH*
En , Iwan Ulrich et Johann Borenstein ont publié un article décrivant le VFH*, affirmant que les algorithmes originaux du VFH devaient être améliorés en traitant explicitement des inconvénients d'un algorithme de planification locale[5] dans le sens où l'optimalité globale n'est pas assurée. Dans le VFH*, l'algorithme vérifie la commande de pilotage produite à l'aide de l'algorithme A* afin de minimiser le coût et les fonctions heuristiques. Bien que simple en pratique, des résultats expérimentaux ont montré que cette vérification d'anticipation peut traiter avec succès des situations problématiques que le VFH et le VFH+ d'origine ne peuvent pas gérer (la trajectoire résultante est rapide et régulière, sans ralentissement significatif en présence d'obstacles).
Références
- Borenstein, J. et Koren, Y., « The vector field histogram-fast obstacle avoidance for mobile robots », IEEE Transactions on Robotics and Automation, vol. 7, no 3,‎ , p. 278–288 (DOI 10.1109/70.88137)
- Ulrich, I. et Borenstein, J. « VFH+: reliable obstacle avoidance for fast mobile robots » () (lire en ligne)
— « (ibid.) », dans Robotics and Automation, 1998. Proceedings. 1998 IEEE International Conference on, vol. 2 - Ulrich, I. et Borenstein, J. « VFH: local obstacle avoidance with look-aheadverification » () (lire en ligne)
— « (ibid.) », dans Robotics and Automation, 2000. Proceedings. ICRA'00. IEEE International Conference on, vol. 3 - VFH+ in Player/Stage/Gazebo
- « VFH*: Local Obstacle Avoidance with Look-Ahead Verification », (consulté le )