3.4. L'approche globale
L'approche globale c'est une méthode utilisé
dans le cas d'un environnement partiellement ou complètement connu. Elle
utilise un modèle de l'espace libre dont l'espace de configuration
permet la recherche exhaustive de la trajectoire de cout minimum au sens de
critère donné ou de conclure à la non-exhaustive d'une
trajectoire amenant le système de la configuration initiale à la
configuration finale. Notons que cette approche est très couteuse en
temps de calcul qu'en occupation mémoire, mais son avantage consiste
à la garantie d'arrivée au but en suivant un chemin optimal.
Une multitude des méthodes ont à ce jour
été proposées nous mentionnons ci-dessous quelques
méthodes:
· Méthode de décomposition cellulaire.
· Méthode de roadmap.
· Méthode des vecteurs de traversabilité.
3.4.1. Méthode de décomposition
cellulaire
La méthode de décomposition cellulaire consiste
à décomposer dans un premier temps l'espace libre dans un
ensemble des cellules et à représenter leurs relations
d'adjacence dans un graphe. Ensuite ce graphe est explore, menant à une
succession de cellules adjacentes qui relient celles contenant les
configurations initiale et finale. Ces configurations sont alors reliées
par une trajectoire qui traverse la succession de cellules.
Chapitre 03
Planification de localisation et trajectoire
Une limitation sévère de la méthode de
décomposition cellulaire et que le nombre de cellules nécessaire
pour représenter l'espace libre croit exponentiellement avec la
dimension de I' espace de travail. Cette méthode se restreigne ainsi en
pratique à des cas de faibles dimensions.
Cellule libre Cellule occupé
|
|
|
34
Figure (3.5): Relation d'adjacence.
3.4.2. Méthode de vecteurs de
traversabilité
Une autre méthode emploi la notion de
traversabilité à travers un groupe d'obstacles. Dans cette
méthode l'obstacle est modélisé par un polygone convexe
den arêtes dans R2. Le t-vecteur d'un point p(x, y) de R vis avis d'un
obstacle Oi note t(i, j) est définit comme un n-uples vecteur ligne
binaire.
3.4.3. Méthode de roadmap
Roadmap est un réseau de courbes qui
représentent la connexité de l'espace libre avec les obstacles
existants. Le problème de la planification de trajectoire est alors
résolu, en connectant la position initiale et finale à la roadmap
par des chemins admissibles. Le problème essentiel est la construction
de la roadmap, dans le cas d'un espace de dimension deux et qui est peuple par
des obstacles polygonaux. La roadmap est constituée par des segments
reliant deux sommets de polygones différents et qui ne traversent aucun
obstacle. On peut aussi l'appeler graphe de visibilité
| 
