Modèles d’environnements, planification de trajectoires

L’utilisation d’un robot nécessite souvent d’avoir un modèle géométrique de son environnement et d’être capable de planifier des trajectoires à l’intérieur de cet environnement. Dans ce module, nous explorerons les techniques de base de géométrie algorithmique et son utilisation pour modéliser l’environnement, la notion d’espace des configurations du robot et les grandes familles d’algorithmes de planification de trajectoires.

On abordera ainsi la triangulation de Delaunay et les diagrammes de Voronoï, permettant d’avoir des trajectoires les plus éloignées possible des obstacles, et des algorithmes stochastiques de reconstruction 3D, permettant d’obtenir une carte de l’environnement de manière efficace. On mettra en perspective les différentes constructions de l’espace des configurations entre les robots mobiles et les robots articulés, en tenant compte d’éventuels obstacles mobiles. On comparera enfin des algorithmes de planification déterministes (Djikstra, A*) et stochastiques (RRT, RRT*).

Prérequis

  • Algorithmique de base (algorithmes de tri, arbre binaires de recherche, parcours de graphe).
  • Notions de complexité des algorithmes.
  • Notions de probabilité.

Acquis d’apprentissage

  • Bases de géométrie algorithmique : triangulation de Delaunay, diagrammes de Voronoï, reconstruction 3D (Crust).
  • Planification de chemin : algorithmes stochastiques (RRT, RRT*).

Compétences visées

  • Choisir des algorithmes adaptés de traitement géométrique de l’espace.
  • Mettre en œuvre de la planification de mouvement adaptée à un robot donné.