Page d'accueil | Description du projet |
Les sources présentées ici décrivent une implémentation de la notion d'espace de localisation décrite dans mon mémoire de DEA(page 40-50). L'espace de localisation permet de décrire les capacités de localisation d'un robot se repérant grâce à des amers dans un environnement donné.
J'ai utilisé un tel espace pour décrire l'environnement d'un robot équipé d'un capteur télémétrique laser à balayage. Avec un tel capteur et des amers (landmarks), le robot peut connaître sa position dans l'environnement dès qu'il "voit" au moins deux amers. L'ensemble des configurations où il est possible de voir au moins deux amers constitue l'espace de localisation.
Au niveau mathématique, l'espace de localisation est un sous ensemble de l'espace des configurations (ensemble des positions/orientations possibles (x,y,theta) d'un robot).
Le graphe de localisation permet d'obtenir 3 résultats :
Pour un environnement donné (espace de travail et amers), il permet de déterminer quelles sont les configurations où la localisation est possible.
Pour un environnement donné, on peut utiliser ces informations pour planifier une trajectoire garantissant des capacités optimales de localisation (pour un robot Nomade équipé d'une caméra mobile par exemple).
Pour un espace de travail et un nombre d'amers donné, il permet de mettre en place des techniques d'optimisation pour placer les amers de façon optimale. Les sources fournies ici n'implémentent pas directement cette optimisation, mais avec la classe LocalisationGraph et une bibliothèque spécialisée (Algo. Génétique par ex.), l'implémentation est relativement immédiate.
L'interface graphique permet de définir l'environnement étudié :
A partir de cet environnement, on appelle le programme planifCnx :
spawn planifCnx > Init workspace beacons 200 2.09439513333 5 ......................................................................... Linking ......................................................................... ........................................................................ Exploration OK > Volume Used space : 53.0% OK > Connex Connex parts : 1 OK > Save graph OK > VtkExport polyLayer vtkPoly 0.3 0.3 20 OK > Quit OK
On obtient alors la représentation suivante :
Avec un autre environnement :
Les positions du robot au départ et à l'arrivée sont représentées en bleu et en vert. Les zones bleues correspondent aux ensembles de positions, qui, pour une orientation fixée, permettent de voir les balises en cyan. Le but de la planification est de trouver une suite de ces zones telles qu'elles soient connexes dans l'espace de localisation, que la première contienne la position de départ et la dernière la position d'arrivée.
Voici les trois premières étapes d'un tel chemin :
Etape 1 : | |
Etape 2 : | |
Etape 3 : |
> tar zxf LocalisationSpace.tgz > cd LocalisationSpace > make > make test
"make test" fait appel au script expecttk planif.tcl. Expect est une extension libre et gratuite de Tcl/tk qui permet d'interfacer simplement un programme en forme de "shell".
Fichier | Rôle |
---|---|
Makefile | Instruction de compilation. |
planif.tcl | Interface graphique à planifCnx en Tcl/tk (expect). |
planifCnx.cpp | Fichier principal : mini-shell et gestion des commandes. |
Object.h | Classe mère de toutes les autres. |
Balise.h Balise.cpp |
Description des amers (landmarks) : position et visibilité. |
LocalisationGraph.h LocalisationGraph.cpp |
Description de l'espace de localisation. Implémentation des opérations : construction, mesure, recherche de chemin... |
Polygon.h Polygon.cpp |
Description des polygones et des opérations ensemblistes. Wrapper autour de la bibliothèque C gpc.h |
Segment.h Segment.cpp |
Description des segments : fonction d'intersection. |
TriangleStrip.h TriangleStrip.cpp |
Description des "Triangle Strip" (bande de triangle). Wrapper autour de la bibliothèque C gpc.h |
vector2.h vector2.cpp |
Vecteur du plan (cf. V2 Lib). |
Vector.h Vector.cpp |
Tableaux de taille variable (cf. vector). |
VisibilityPolygon.h VisibilityPolygon.cpp |
Elément de la partition d'espace de localisation en zones de visibilité : dans un polygone de visibilité, les mêmes amers sont visibles en tout point. |
gpc.h gpc.c |
Bibliothèque d'opérations sur les polygones (par Alan Murta, University of Manchester). |
VtkPoly.h | Définition de types utiles pour générer une représentation 3D de l'espace de localisation pour VTK. |
Makefile.vtk polyPlot.cxx |
Instruction de compilation et programme pour afficher l'espace de localisation (ou plutôt, son approximation) en 3D avec OpenGL. Nécessite VTK |