Planification de trajectoire
Projet Réalisé par
Cyril Branciard et Benoît Loussier
(promo 2000)
Description du projet
Le but du projet est de calculer et d'afficher une trajectoire pour un robot circulaire, dans un
champ d'obstacles ponctuels, entre un point de départ et un point d'arrivée
saisis à la souris (de même que les obstacles). Afin de simuler une situation
réaliste, des obstacles répartis sur le périmètre d'un carré
imposent au robot de
rester dans un espace fermé.
Algorithmes utilisés
On cherche un chemin empruntant les arêtes du diagramme de Voronoï car l'existence d'un
tel chemin est équivalente a l'existence d'un chemin quelconque. En fait les chemins se projettent
naturellement sur les arêtes de Voronoï.
On procède en plusieurs étapes :
- on modifie la triangulation de Delaunay des obstacles au fur et à mesure qu'on les
insère :
on réalise une localisation par marche courte dans la triangulation existante, puis on
effectue les bascules de diagonales nécessaires.
-
la représentation du diagramme de Voronoï se fait simplement par rajout
des coordonnées du centre du cercle circonscrit dans chaque structure de triangle.
-
points de départ et d'arrivée : on les relie à l'un des sommets de Voronoï
de leur cellule
- recherche d'un chemin dans le graphe de Voronoï : exploration des sommets de voisins
en voisins dans l'ordre croissant de leur distance (par le chemin parcouru) au point de départ.
-
-
tracé du chemin puis animation
Résultats obtenus
Le programme détermine si une solution existe et fournit le cas échéant un chemin possible
qui n'est pas nécessairement
le plus court mais s'en approche.
Par ailleurs l'animation donne une confirmation visuelle de la validité du chemin.
Voici quelques exemples graphiques des résultats :
1ère étape : triangulation de Delaunay
2ème étape : zones accessibles pour le robot et diagramme de Voronoï (en vert)
3ème étape : calcul et affichage d'un chemin (en bleu) entre les points d'arrivée
et de départ
4ème étape : animation pour visualiser le déplacement du robot
configuration sans solution
Problèmes rencontrés et solutions apportées
-
représentation de la boîte englobante :
après avoir tenté de modifier les chemins qui faisaient sortir le robot de la
boîte en les faisant passer sur le bord (si possible), ce qui est relativement complexe,
nous avons opté pour un ensemble d'obstacles sur le périmètre, interdisant le
passage du robot.
-
recherche du plus court chemin :
les solutions envisagées au départ étaient un parcours en largeur d'abord
avec priorité aux sommets les plus proches de l'arrivée, et une recherche de
plus court chemin classique après avoir construit le graphe des sommets de Voronoï.
Finalement nous avons choisi l'exploration décrite plus haut, plus efficace que la
première et plus simple que la deuxième.
-
traitement des situations aberrantes telles que les détours inutiles :
il faudrait pour cela s'affranchir de la contrainte de passage par les arêtes
de Delaunay et tester par exemple si la ligne droite est un chemin valide (ce qui n'est pas
très compliqué). Ces cas étant très marginaux nous ne les
avons pas traités.
une situation aberrante : le robot fait un détour au lieu d'aller en ligne droite
Retour à la liste des projets réalisés
