L'objectif principal de ce projet est d'ecrire un programme pour
planifier et simuler les deplacements d'un robot R de forme polygonale
dans le plan muni d'obstacles O1,
..., Ok eux-memes polygonaux. On
commencera par etudier le cas particulier ou le robot et les obstacles
sont convexes, et ou les deplacements sont constitues uniquement de
translations. On continuera l'etude dans un cadre plus general, en
supprimant d'abord l'hypothese de convexite du robot et des obstacles,
puis en considerant des deplacements constitues de translations et de
rotations. La base theorique utilisee pour ce projet est decrite dans
le chapitre 13 du livre [1], nous vous conseillons donc fortement de
vous le procurer (vous pouvez nous le demander si vous ne le trouvez
pas).
1. On commence par le cadre le plus restreint : le robot est convexe et
se deplace par des translations parmi des obstacles eux-memes convexes.
En prenant un point de reference R0 dans
le robot R, on ramene l'espace des configurations de R au plan
lui-meme. Ainsi, toute position du robot est definie de maniere unique
par la position du point R0. On peut
ensuite representer l'espace des configurations admissibles (i.e. celles pour
lesquelles le robot n'est pas en collision avec un ou plusieurs
obstacles) par le plan prive des sommes de
Minkowski Oi + (-R), où le terme -R
est a interpreter comme l'ensemble des vecteurs reliant des points de R
à R0. Il est en effet aisé
de voir que le robot R est en collision avec un obstacle Oi
si et seulement si le point R0 se trouve
a l'interieur de l'obstacle agrandi Oi + (-R).
Votre premiere tache consistera donc a calculer la somme de Minkowski
de deux polygones convexes. Pour cela vous pourrez appliquer un
algorithme tres simple, consistant a faire
glisser le robot R le long de chaque obstacle Oi
et a reporter les sommets du polygone ainsi obtenu. Voir la section
13.3 du livre [1] pour les details.
Votre deuxieme tache sera d'implementer l'algorithme de planification
de trajectoire. Pour cela vous creerez une triangulation 2D contrainte,
ou les aretes de contrainte seront les bords des obstacles. Pour
deplacer le robot R de maniere a amener le point R0
d'un point D a un point A, vous procederez comme suit :
vous localiserez D et A dans la triangulation, puis
vous choisirez un sommet arbitraire D' du triangle contenant D,
ainsi qu'un sommet arbitraire A' du triangle contenant A, puis
vous
determinerez un chemin c du sommet D' au sommet A' dans la
triangulation, de sorte que ce chemin ne traverse pas d'obstacle (il
peut toutefois longer les bords des obstacles), et enfin
vous
deplacerez le point R0 du robot le long
du segment [D,D'] puis du chemin c puis du segment [A',A].
Afin
de rendre le programme plus convivial, vous pourrez implementer une
petite interface graphique simulant les deplacements du robot. Mais
attention, cette etape est facultative et n'est pas au coeur du sujet,
ne lui accordez donc que le minimum de temps !
2. On continue maintenant avec le cas ou le robot et/ou les obstacles
peuvent ne pas etre convexes. Le principe reste le meme, seul le calcul
des sommes de Minkowski change un peu. L'algorithme de calcul qui
consiste a faire glisser le
robot le long de chaque obstacle genere des boucles, qu'il suffit de
supprimer a posteriori. Vous pouvez egalement utiliser la technique
proposee a la fin de la section 13.3 du livre [1], qui propose de
trianguler le robot et les obstacles. Le reste de l'approche reste
rigoureusement le meme.
3. On considere maintenant le cas general d'un robot R qui peut tourner
en plus de se translater. Cette fois l'espace des configurations n'est
plus le plan, mais R^2xS^1 (le produit cartesien du plan avec le
cercle). L'espace des configurations est beaucoup plus complique dans
ce cas, aussi il est preferable de simplifier le probleme, quitte a ne
pas trouver de solution dans certains cas, ce que nous vous conseillons
de faire en suivant l'approche decrite a la section 13.5 du livre [1].
Grosso modo, l'espace des configurations se decompose en strates du
type R^2x{alpha}, ou alpha est un angle fixe. Dans chaque strate les
mouvements du robot sont exclusivement translationnels, donc on peut
appliquer la technique developpee plus haut pour trouver des chemins
entre des points donnes. Il reste a pouvoir se deplacer entre les
strates, ce que l'on fait en discretisant le cercle S^1 et en
cherchant, pour toute paire d'angles consecutifs alphai,
alphai+1, quels sont les points de la i-eme
strate qui peuvent etre relies a la (i+1)-eme strate par une rotation
ne creant pas de collision avec des obstacles. Pour cela il peut etre
necessaire de rajouter des points dans les strates. En testant votre
programme sur des jeux de donnees de votre choix, vous pourrez essayer
de determiner des configurations ou il ne trouve pas de solution alors
qu'un chemin existe entre le depart et l'arrivee. Notez toutefois que
tout chemin trouve par votre programme doit etre valide, i.e. ne doit
pas passer par des configurations non admissibles du robot !
Mot
clés: planification de trajectoires, sommes de Minkowski,
triangulation de Delaunay, parcours de graphes.
Références:
[1]
M. de Berg, O. Cheong, M. van
Kreveld, and M. Overmars. Computational Geometry: Algorithms and
Applications. 3rd Edition, 2008. Springer Berlin Heidelberg. ISBN:
978-3-540-77973-5. DOI: 10.1007/978-3-540-77974-2.
Fig. 1 - Un robot polygonal R en translation dans le plan parmi des
obstacles polygonaux O1, ..., Ok.
La zone interdite pour le point R0 est
l'ensemble des obstacles augmentés de (-R), en rouge
sur l'image.
