Université de Bretagne-Sud E.N.S.T. Bretagne
Rapport d’étude
de Stephane GOUGEON, Gurvan UGUEN et Wei YOU
Algorithme de calcul du plus court chemin
pour un robot mobile en environnement connu
avec gestion de l’encombrement
25 février 2004
Dans le cadre du cours de robotique de :
M. Dominique DUHAUT, maître de conférences, U.B.S.
Sommaire 2
Introduction 3
1. Problématique 4
2. Principaux algorithmes de recherche du plus court chemin 5
2.1. Méthodes algorithmiques 5
Méthodes par graphes 5
Décomposition par bande 6
Diagramme de Voronoï 7
Représentation cannonique de l’environnement : est-ce ? 8
Décomposition en quadtree 8
Methodes des Freeways 8
2.2. Méthodes heuristiques 9
3. Notre Algorithme du Plus court chemin 10
3.1. Représentation de l’environnement 10
3.2 Méthodes utilisées 10
3.3 Contraintes de déplacement 11
3.1.4. Gestion de l’encombrement 12
3.2. Présentation 12
3.2.1. Calcul du gradient de distance 13
3.2.2. Identification d’un chemin de longueur minimale 13
3.3. Résultats 14
3.4. Justification de l’algorithme 15
Conclusion 17
Bibliographie 18
L’étude qui a donné lieu au présent rapport a été effectuée dans le cadre du cours de Robotique du D.E.A. Interaction Homme-Machine de Vannes. Cette étude a abouti à la définition et la réalisation d’une application visant à simuler et illustrer le traitement qu’un module de robot aurait à effectuer pour planifier un chemin de longueur minimale à suivre pour atteindre un point donné dans un environnement connu.
Dans ce rapport, nous présenterons tout d’abord plus en détails le sujet et la problématique du projet que nous avons eu à effectuer.
Dans un second temps, nous présenterons brièvement les principales méthodes existantes pour définir un chemin de longueur minimale entre 2 points donnés.
Nous présenterons ensuite l’algorithme que nous avons implémenté dans notre application. Nous y discuterons notamment des différents choix ayant été faits ainsi que les résultats obtenus par notre application.
Enfin, nous conclurons par un rappel des principales idées qui auront été exposées.
Le travail que nous avions à effectuer était la réalisation d’une application. Cette dernière serait un démonstrateur d’une solution envisageable en tant que module de traitement pour la planification hors-ligne d’une trajectoire 2D minimale d’un robot mobile vers une cible donnée, dans un environnement où l’ensemble des obstacles serait connu.
Nous nous sommes donc intéressés au problème du calcul d’un plus court chemin. Nous verrons notamment que la recherche des chemins de longueur optimale ou minimale est une branche importante du domaine de la théorie des graphes. On verra cependant qu’il existe d’autres méthodes de recherches du calcul du plus court chemin que celles issues de ce seul domaine.
Cependant l’application d’une de ces méthodes, théoriquement fonctionnelles, nécessite d’être réfléchie de manière à intégrer les aspects du projet relatifs tant aux contraintes informatiques qu’aux contraintes soulevées par une mise en ?uvre dans un environnement réel.
Nous verrons ainsi que l’implémentation d’un des algorithmes de calcul du plus court chemin peut être optimisée du fait de son application à une image. Il sera aussi intéressant de discuter l’utilisation d’une image comme représentation de l’environnement du robot.
La mise en ?uvre en environnement réel nécessite aussi quelques attentions. Il s’agira ainsi de prendre en compte le fait que l’on effectue un traitement sur une représentation discrétisée de l’environnement et non sur l’environnement réel. Nous montrerons notamment que ceci joue sur la définition des mouvements possibles dans l’environnement du robot.
Un dernier point important à prendre en compte pour l’application de telles méthodes au domaine de la robotique est la gestion de l’encombrement du robot. Du fait que l’on travaille sur la représentation d’un robot en situation dans un environnement réel, celui-ci a nécessairement lui aussi une dimension dans la représentation et il ne peut donc être traité comme un simple objet ponctuel.
Il existe 2 grandes familles d’algorithme pour résoudre le problème du calcul du plus court chemin entre 2 points donnés : les méthodes algorithmiques et les méthodes heuristiques.
Déplacement du robot dans un espace contraint
• Définir un chemin de la configuration initiale à la configuration finale (Roadmap ou algorithmes de réseaux)
• Problème géométrique : obstacles polyédriques
• Solution :
• Suite de segments de droite
• Séquence de configuration du robot
Les 3 grands algorithmes définis pour la recherche d’un chemin minimal dans un graphe sont les algorithmes de Ford, de Bellman et Kallaba, et enfin de Moore et Dijktra. Ils s’appliquent à des graphes orientés dont tous les arcs sont étiquetés par une valeurs représentant un coût, une distance, une durée… Ces algorithmes travaillent avec une matrice M de poids : si Mij est définie, c’est la valeur de l’arc joignant les 2 sommets i et j.
L’algorithme de Bellman-Ford trouve le plus court chemin avec origine unique, y compris dans le cas général ou les arcs sont munis de poids négatifs. S’il n’y a pas de circuit de poids négatif, l’algorithme de Bellman-Ford retourne vrai, et sinon il retourne faux : en effet, dans ce cas, il n’existe pas de plus court chemin à partir de l’origine.
Le principe de l’algorithme est le suivant :
booléen Bellman_Ford( G, s)
initialisation ( G, s) // les poids de tous les sommets sont mis à +infini
// le poids du sommet initial à 0 ;
pour i=1 jusquà Nombre de sommets -1 faire
pour chaque arc (u, v) du graphe faire
paux := poids(u) + poids(arc(u, v));
si paux
pred(v) := u ;
poids(v) := paux;
pour chaque arc (u, v) du graphe faire
si poids(u) + poids(arc(u, v))
retourner faux
retourner vrai
Pour l’utilisation de l’algorithme de Ford, le graphe ne doit pas comporter de circuit de longueur négative. Chaque sommet i est marqué par une valeur ou potentiel ?(i) et le poids d’un arc entre i et j est noté w(ji), . Dans un premier temps on calcule toutes les distances des plus courts chemins entre les sommets 1 et i. L’algorithme est le suivant :
initialisation : ?(1)=0 et ?(i)=+? pour tous les autres sommets i
itération : tant que ?(i) non stabilisé pour tout i faire
?(i) = min[?(i), min(?(j) – w(ji))]
Lorsque tous les potentiels sont stabilisés, pour tout sommet i on a ?(i) qui est la valeur du plus court chemin entre les sommets 1 et i.
Pour augmenter la vitesse de convergence de l’algorithme il est possible d’utiliser l’ordre induit par les niveaux du graphe. Ce partitionnement du graphe nécessite l’application d’un autre algorithme permettant en plus de détecter l’existence d’un circuit négatif.
L’identification d’un plus court chemin entre le sommet 1 et un sommet i spécifique se fait par un algorithme procédant « à reculons » : on commence en i et on cherche les arcs (j,k) tels que ?(j) = ?(k) + w(kj) et qui seront à juxtaposer pour obtenir le chemin le plus court.
L’algorithme de Bellman-Kallaba est basé sur le principe suivant : à chaque itération k, on examine les chemins de au plus k arcs et on attribue la valeur ?(k, i) du plus court chemin de 1 à i. L’algorithme se termine lorsque ?(k, i) = ?(k-1, i), les ?(k, i) étant alors les valeurs des plus courts chemins de 1 à i, ou bien lorsque k atteint N le nombre de sommets du graphe, ce qui est caractéristique de l’existence d’un chemin de longueur négative. L’algorithme est le suivant :
initialisation : ?(1)=0 et ?(i)=+? pour tous les autres sommets i
itération : tant que [?(k, i) != ?(k-1, i)] ET [k < N] faire
?(k, i) = min[?(k-1, i), min(?(k-1, j) – w(ji))]
L’algorithme de Moore-Dijkstra partitionne à chaque itération l’ensemble S des sommets du graphe en 2 sous-ensembles X et X’=S-X. Initialement seul le sommet 1 est contenu dans X, tous les autres étant éléments de X’. Chaque sommet est affecté d’une étiquette ?(i) telle que :
Une itération consiste a prendre 1 sommet i de X’ et à le faire entrer dans X. L’algorithme se termine donc en N-1 itérations. Ce sommet i est choisi tel que ?(i) = min(?(j), j?X’) car dans ce cas là on a ?*(i) = ?(i).
On décompose en bande de largeur variable, l’envrionnement où on doit trouver un plus court chemin. On calcule des positions sur les bandes où le robot peut se placer et l’on rejoint entre eux ces différentes positions clés pour trouver un plus court chemin.
Passage entre 2 cellules par une droite
• Graphe
• n?uds = cellules
• arcs = cellules adjacentes
• l ’union des cellules = espace libre
• Cellule :
• lignes verticales à partir des angles des obstacles
• Chemin libre : connexion de qini à qfin via les points milieux des arêtes communes de 2 cellules.
• Garantie d ’une solution si elle existe
• Possibilité d ’attribuer une fonction coût à chaque cellule pour optimiser la distance par rapport aux obstacles en convergeant vers le but.
On calcule les points milieux entre les obstacles, et à partir de ces points on recherche la trajectoire la plus courte.
• L ’espace libre est limité extérieurement par un rectangle
• qini et qfin sont rétractées en q’ini et q’fin en menant un segment le long duquel la distance par rapport aux obstacles décroît le plus rapidement
• lien des configurations q équidistantes d ’au moins 2 obstacles q ini q’ ini, q fin q’ fin
Remarques
• Chemin = 3 sous sous chemins
• un segment entre qini et q’ini
• un chemin dans le diagramme
• un segment entre q’fin et qfin
• Privilégie la sûreté plutôt que la minimisation du chemin
• Chemins parfois inutilement longs
• Irrégularité dans les arêtes des obstacles = modifications importantes dans le diagramme
ou encore
On cherche un chemin empruntant les arêtes du diagramme de Voronoï car l'existence d'un tel chemin est équivalente à 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
• N?uds du graphe : qi, qf et angles des obstacles
• 2 n?uds connectés si le segment qui les relie n ’a pas d ’intersection avec un obstacle
• 3 étapes :
• Constitution d ’un réseau R
• connexion de qi à R
• connexion de R à qf
Avantages et inconvénients
• Chemin le plus court, au sens des distances Euclidienne.
• Propriété non valable lorsque l ’orientation du robot n ’est pas constante
• Arêtes des obstacles = arcs du réseau donc dilatation des obstacles (peut entraîner une disparition de chemins possibles)
… à trouver
• Description de l ’espace par des couloirs ou cônes généralisés
• Freeway :
– deux arêtes qui se font faces :
• 2 extrémités de E1 (respectivement E2) sont en dehors du demi plan défini par E2 (resp. E1) ne contenant pas l ’obstacle
• le produit scalaire des normales sortantes à E1 et E2 est négatif
• Chaque point d ’un freeway se voit associé d ’un secteur angulaire / orientations admissibles
• Déplacement du robot le long de l ’axe des freeways
• Changement de direction possible à l’intersection de 2 freeways
Remarques
• Méthode rapide dans un environnement peu encombré
• Méthode non complète
• Solutions géométriques ne prenant pas en compte les contraintes du système (ex : non-holonomie)
• Le modèle du monde doit être connu (et avec précision)
• Pas d ’obstacle mobile (replanification) ou utilisation de méthodes plus complexes (fonction du temps)
En plus de ces méthodes algorithmiques qui utilisent plus ou moins les graphes, d’autres méthodes, venant du domaine de la coopération d’agents distribués, ont été définies en utilisant par exemple la programmation évolutionniste ou les algorithmes génétiques. On pourra aussi voir la méthode de recuit simulé (où, quand, on en parle plus tart, mais nullle part en fait) qui présente l’avantage d’être peu sensible aux problèmes de minima locaux.
Ces méthodes visent à optimiser une fonction de coût et la solution obtenue est donc une approximation (du plus court chemin dans notre cas) dont la précision augmente avec le nombre d’itérations. Ces méthodes sont particulièrement indiquées pour les problèmes NP-complets (expliquer).
Une de ces dernières méthodes proposées est la méthode d’optimisation par colonies de fourmis (O.C.F.). Celle-ci est basée sur l’observation de l’insecte social qu’est la fourmi et notamment sur les moyens dont elle dispose pour s’orienter entre la fourmilière et les sources de nourriture. De l’application de ces observations au domaine des systèmes multi-agents a été défini une méthode consistant à utiliser des agents qui, comme les fourmis utilisent des phéromones, vont déposer des marqueurs de passage au cours de leurs déplacements. Ces agents ont pour but d’effectuer des allers-retours entre les 2 points entre lesquels on souhaite trouver le plus court chemin. Les déplacements effectués sont décidés par une combinaison entre un déplacement aléatoire exploratoire et le suivi d’un chemin créé par le passage d’autres agents et identifiable par la quantité de phéromones encore présentes, c’est à dire non évaporée depuis le passage de l’agent ayant laissé des phéromones. D’un comportement initiale d’exploration aléatoire, le comportement global de la colonie va ensuite tendre vers la définition d’un chemin de plus en plus optimisé. Lorsqu’un agent découvre un chemin il va avoir tendance à le reprendre plutôt qu’à explorer aléatoirement et il va donc déposer à chaque passage des phéromones, ce qui va inciter d’autres agents à suivre le même chemin et ainsi encore consolider le chemin. Comme de plus le chemin le plus court sera celui pour lequel les agents l’empruntant seront les plus rapides à faire des allers-retours, de par la quantité de phéromone ce plus court chemin finira par être favorisé, pour, au final, être emprunté par toute la colonie.
Notre algorithme n’a pas pu être trouvé dans la littérature, mais se rapproche de la méthode « décomposition par bande » et du calcul du « freeWay », ou encore des calculs à base de graphe, tout en étant une solution « originale » du calcul du plus court chemin.mais avec une approche très orienté traitements d’images. Tout par du choix de la représentation interne de l’environnement.
La représentation de l’environnement pour le robot est l’un des points important à définir pour pouvoir chercher un chemin dedans.
La représentation d’un environnement peut être envisagée de différentes manières. On peut définir une surface délimitée dans laquelle se positionne le robot et sur laquelle sont définis des obstacles aux formes préfixées (cercle, polygones). Mais du fait que les obstacles sont définis un à un dans une liste, il devient très rapidement impossible de décrire un environnement comportant de nombreux obstacles. De plus un environnement réel comporte souvent des obstacles très différents et donc non limités à quelques formes prédéfinies.
Ces obstacles sont généralement représentés pour l’homme sous forme graphique. L’idée est d’utiliser directement une image bitmap de l’environnement que l’homme utilise, et ainsi utiliser une image comme représentation discrétisée de l’environnement réel. Dans cette image, chaque pixel représente l’approximation d’une petite partie de l’environnement que le robot peut encombrer ou pas. Un pixel de l’image sera donc défini accessible pour le robot s’il peut être placé à la position de celui-ci sans toucher ou intersecter un seul pixel inaccessible de l’environnement.
.
On fait l’hypothèse suivante : les points considérés comme non accessibles sur l’image de l’environnement fournie en entrée du module doivent être les points dont la probabilité qu’un obstacle y soit positionné est non nulle. Il en est de même pour la définition de la représentation du robot dans l’image. L’assurance du fait que les points accessibles ont une probabilité nulle qu’il y ait un obstacle, suite à la discrétisation de l’environnement, devra donc certainement être garantie par un pré-traitement de l’image issue des capteurs avant d’être fourni au module que notre application simule.
Mis à part le fait qu’il est pratique d’utiliser une image pour notre simulateur de manière à vérifier aisément son bon fonctionnement, une image numérique prend la forme d’un tableau de valeurs RGB, une forme de graphe adaptée aux traitements les plus simples par ordinateur.
L’un des principaux choix à effectuer dans ce projet fut celui du type de méthode à utiliser. Du fait que le choix de la représentation de l’environnement réel avait été fixé à celui d’une image bitmap, l’implémentation des méthodes algorithmiques générales semblait pouvoir faire l’objet d’optimisations intéressantes. Comme de plus le choix d’une méthode heuristique est généralement justifié par le nombre de possibilités à considérer tend vers l’infini et que dans notre cas l’utilisation comme graphe de notre image rend, au contraire, les calculs plus simples, nos efforts ce sont portés sur la définition d’une méthode algorithmique adaptée aux caractéristiques et contraintes du projet. (pas clair)
Les méthodes heuristiques sont trop compliquées pour le problème qui nous est posé. On connaît l’environnement, et cet algorithme convient mieux à la recherche d’un chemin par des robots qui ne connaissent pas la
En comparaison des algorithmes généraux, certaines améliorations dues à l’application d’un tel type d’algorithme sont possibles. Il n’est ainsi pas nécessaire d’avoir à stocker une matrice des poids, ceci sont entièrement connus par le fait que l’on travaille sur un graphe qui est une matrice dont on connaît la connexité. On a donc aussi la certitude de la non-existence de circuits de longueur négative. En utilisant une simple propagation de pixel en pixel lors du calcul des plus courts chemins entre le sommet de départ et tous les autres points accessibles, on est assuré, sans calcul préalable, que l’on suit les niveaux du graphe.
L’hypothèse a été faite que les pixels de l’image d’entrée sont de forme carré. Le pixel est alors l’atome le plus petit de représentation de notre environnement. On définit les mouvements que notre robot peut effectuer. Comme nous sommes dans un environnement discret, cela n’est pas trivial ! On peut définir plusieurs niveaux de raffinement des mouvements en fonction des rotations autorisées au robot :
Translation de 1 pixel horizontale ou verticale, rotation de 90° à droite ou à gauche (schéma 1)
Translation de 1 pixel horizontale, verticale ou diagonale, rotation de 45° à droite ou à gauche (schéma 2)
L’utilisation d’angles de rotation plus petits que 90° permet d’envisager des translations d’orientations autres que horizontales et verticales. En favorisant dans l’algorithme la poursuite des chemins vectoriels dont l’orientation nécessite la plus grande norme (par exemple notre application est équivalente au schéma 2 : les vecteurs de translations diagonales de 1 pixel ont une norme de ?(2) et seront privilégiés par rapport aux vecteurs de translations horizontaux et verticaux de 1 pixel qui eux ont une norme de 1). Ceci permet d’obtenir des courbes d’autant plus lissées que le nombre d’angles de rotation possibles augmente. Mais dans ce cas, le nombre de test supplémentaires pour valider le chemin possible augmente de manières exponentielles. Notre application utilise un robot qui ne peut effectuer que des rotations multiples de 45°, à droite ou à gauche. Utiliser une rotation de 22.5°, permettrait de « courber » les trajectoires, sans trop augmenter le nombre de test supplémentaires.
On pourra aussi envisager d’utiliser en sortie du module, non plus une image, mais un ensemble de vecteurs définissant le trajet à emprunter. Cette utilisation conjuguée d’angle de rotation plus fins que 45° et d’une sortie sous forme de vecteurs permet de minimiser le problème de la qualité de la discrétisation de l’environnement pour ce qui concerne la qualité du résultat en sortie. Mais la finesse de la discrétisation reste un problème dès l’entrée (définition des points à probabilité nulle de comporter un obstacle lors ou suite à la capture de l’image). De plus la complexité globale de l’algorithme en est fortement affectée car de nombreux tests sont à rajouter, non seulement du fait que l’on observe plus de pixels à chaque itération mais aussi du fait que l’on est amené à considérer non plus des arcs entre 2 points du graphe de longueur fixée à 1 pixels mais un ensemble de distances possibles relativement aux rotations possibles.
Le robot n’est pas un point ponctuel, il occupe un certain espace circonscrit à un cercle de diamètre égale à la plus grande épaisseur du robot à utiliser (qu’il soit rond ou carré).
Le robot doit être positionné dans notre environnement, ce qui se fait par un pixel central, qui représente la position du robot. De ce fait, définir le rayon de notre robot dans notre univers discret, revient à ajouter des pixels, à un pixel central. Ainsi on ne pourra avoir que des rayons impairs pour notre modélisation de l’encombrement d’un robot. Mais ce n’est pas une limitation, mais juste une question de relativisation des échelles entre le rayon réel (physique) d’un robot, et l’ échelle de représentation de l’environnement par notre système.
Mais avant le calcul du plus court chemin à proprement parlé, notre méthode effectue un premier traitement de l’image en rendant inaccessibles tous les points initialement libres mais étant situés dans une zone suffisamment près d’un obstacle pour que le point central du robot ne puisse y accéder. Il s’agit donc de noter (dans notre environnement) comme encombrés tous les pixels qui sont à coté d’un pixel encombré, pour tous les pixels de l’environnement, puis de recommencer ce même traitement un nombre fois égal au rayon du robot en pixels. A ce niveau on peut aussi envisager d’utiliser la forme du robot sous forme d’un masque à appliquer sur l’image de l’environnement et ainsi n’appliquer le traitement qu’une seule fois.
La représentation de l’environnement est donc ainsi modifié pour prendre en compte l’encombrement du robot.
L’intérêt de gérer de cette façon l’encombrement du robot est double. Tout d’abord une fois effectué ce traitement, si l’environnement n’est pas sujet à modification, plusieurs calculs du plus court chemin peuvent être effectués directement sur la représentation modifiée de l’environnement sans recommencer à chaque fois ce traitement. Ensuite le fait d’effectuer ce traitement avant celui relatif à la recherche du plus court chemin permet de supprimer un certain nombre de points en plus de ceux déjà inaccessibles, ce qui joue sur la complexité etle nombre de calculs effectués par notre méthode du PCC.
L’algorithme que nous avons mis en ?uvre se décompose en 3 étapes dont les 2 dernières sont celles utilisées par les méthodes algorithmiques classiques de calcul d’un chemin minimal :
Pré-traitement de l’image pour prendre en compte.
Calcul de la distance entre le point d’origine et tous les autres points : gradient de distance centré sur l’origine du chemin.
Identification d’un chemin de longueur minimale entre les points de départ et d’arrivée par parcours « arrière » du graphe.
Tout d’abord définissons ce que nous entendons par gradient de distance. Il s’agit de distances calculées sur l’image d’environnement en considérant une 4-connexité entre les pixels de l’image et non une 8-connexité comme on l’utilise ensuite pour le calcul de la solution du PCC. Nous verrons cependant que ceci ne pose pas de problème du fait que la relation d’ordre entre les différentes distances en 8-connexité est équivalente à celle en 4-connexité.
Le calcul du gradient de distance revient en fait à calculer la distance entre chaque point accessible de l’image et l’origine. La métrique de calcul de la distance est pour un point P(i,j) avec origine O(i,j), Dp=|Pi-Oi|+|Pj-Oj|.
On associe à chaque pixel une distance Dij. Pour le point de départ on a Dij=0. On se déplace verticalement et horizontalement, sur les cases libres adjacentes dont les distances à l’origine sont alors définies comme égale à Dij+1. Du fait que l’on se contraint à des déplacements unitaires horizontaux ou verticaux on simplifie beaucoup la complexité de notre algorithme modifié, relativement à l’algorithme général.
Si par ce procédé on n’atteint pas le point d’arrivée alors c’est qu’il n’existe aucun chemin entre les deux points qui soit praticable par notre robot. Si en revanche, et comme généralement cela se produit, on atteint le point d’arrivée avant d’avoir parcouru tout le graphe, on s’arrête car il ne pourrait pas y avoir de chemin plus court défini dans les itérations suivantes et cette assurance permet d’économiser un nombre de calculs souvent non négligeable.
Suite à la définition de l’ensemble des plus courts chemins entre tous les points de l’image et le robot, l’identification du chemin de longueur minimale va se faire par un traitement « en arrière », c’est à dire que nous partons du point d’arrivée pour remonter jusqu’au point d’origine et cela de maniére itérative en cherchant à chaque fois le pixel adjacent (en 8-connexité) et ayant la plus petite distance au point d’origine. Comme cette distance a été calculée à l’étape précédente par rapport au point de départ, on passe nécessairement par l’un des points constitutifs du plus court chemin.
C’est au cours de cette phase qu’on est amené à définir les angles de rotations possibles et impactant sur les trajectoires possibles du robot. Ainsi notre implémentation utilise l’image de l’environnement comme une matrice en 4-connexité à l’étape précédente alors qu’elle la considère en 8-connexité dans la présente étape.
Nous présentons quelques résultats obtenus avec notre application, qui utilise notre algorithme de calcul de plus court chemin.
Recherche d’un chemin dans une forêt
Si l’on change un tout petit peu la position de départ et d’arrivée, le PCC peut complétemenrt
Si l’on augmente le rayon du robot R=3
Il existe en fait plusieurs chemins étant les plus courts chemins. Ceci est dû à la limitation à 45° de la rotation de notre robot et disparaît si on utilise des rotations de plus en plus petites.
Etude de la Complexité de notre Algorithme.
Si notre robot évolue toujours dans le même environnement, alors l’Etape 1 n’est calculée qu’une fois. Par contre l’étape 2 est la plus longue et doit être recalculée pour tout nouveau point de départ. Mais comme l’Etape 1 enlève des points innacessibles, l’étape 2 en est plus rapide. L’étape 3, elle se fait en un nombre fini d’itération, qui est au plus égal au plus petit nombre d’iteration possibles pour trouver le plus court chemin.
Etape 1 : la prise en compte de l’encombrement du Robot est de complexité = O(n)
Etape 2 : le calcul du gradient de distance est de complexité ? O(n)
Etape 3 : le calcul du plus court chemin lui est de complexité << O(n)
Dans notre cas, « n » est égale au nombre de pixel de l’image d’environnement à traiter.
Explication de la complexité :
Etape 1 : On utilise deux boucles « For » imbriquées, ce qui laisserait à penser que la complexité de cette étape est plutôt en O(n²). Mais on utilise deux boucles imbriquées pour traiter tout les pixels d’une image. On pourrait tout aussi bien utiliser une seule boucle pour effectuer le même traitement. Cette étape est donc en fait de complexité égale à O(n).
Etape 2 : on utilise une boucle while(1) pour calculer le gradient de pixel. La complexité est donc en O(n). Comme on ne traite pas forcément tous les pixels de l’image d’environnement. (On arrête le calcul du gradient de distance, dés qu’on a atteint la position d’arrivée.), la complexité de cette Etape est inféieure ou égale à O(n).
Etape 3 : on utilise une boucle while(1) pour trouver le plus court chemin. A ce stade on est sûr de trouver une solution en un nombre maximal d’itérations qui est égale à la distance du point d’arrivée au point de départ. La complexité de cette Etape est donc très inférieure à O(n).
La complexité de notre algorithme justifie la recherche et les développements qui ont été fait dessus et valide notre approche, du moins, d’un point de vue théorique. En effet, les autres algorithmes de calcul de PCC ont tous une complexité ? à O(n log n).
Intérêts de notre algorithme
Pour un environnement donné, et pour un robot de rayon R :
Notre algorithme est une solution « originale » des algorithmes connus et de ce point de vu s’inspire des algorithmes classiques du calcul du PCC, mais en utilisant une approche plus traitement d’image, et une représentation image de l’environnement.
notre algorithme est sûr de trouver le chemin le plus court entre deux points, si celui-ci existe, dans la contrainte d’une rotation limité à 45°. C’est une approximation de la réalité et donc du PCC réel aussi. Une prochaine version pourrait implémenter une rotation possible de 22.5° pour améliorer la « courbure » de la trajectoire et se rapprocher d’avantage du plus court chemin réel.
Il permet de pouvoir prendre en compte l’encombrement du robot que l’on souhaite. : On peut simplement augmenter l’éloignement du robot des bords en augmentant son rayon, permettant ainsi une certaine approximation de la réalité par rapport à notre représentation discrète de celui-ci.
Il est à remarquer, que si on recherche le rayon le plus grand, pour lequel un chemin est possible, on obtient une solution proche de celle que l’on pourrait trouver en utilisant la méthode de Voronoï.
Remarque : En annexe on peut voir l’algorithme utilisé dans notre application tient compte de l’image d’environnement pour ne pas écraser autres choses que des pixels blancs. Il calcule des gradients
Nous avons donc présenté un simulateur de module pour un robot mobile, prenant en entrée une représentation de l’environnement extérieur sous forme d’une image et retournant le plus court chemin entre le robot et un point cible. Ceci s’effectue par un travail de pré-traitement de l’image pour prendre en compte l’encombrement du robot. L’image est ensuite transformée en une matrice utilisée comme un graphe pour l’application de méthodes algorithmiques.
Nous avons pu voir que la discrétisation de l’environnement réel permet de fortement simplifier les algorithmes classiques de recherche du plus court chemin dans un graphe et ainsi réduire leur coût, mais qu’elle agit aussi sur la qualité de la solution trouvée. Il est cependant possible de minimiser cet impact notamment en définissant des matrices de connexité plus élevée ; ceci malheureusement au prix d’un important accroissement de la complexité de l’algorithme. La discrétisation du problème n’empêche cependant pas la prise en compte de caractéristiques relatives à la réalité physique et les comportements dynamiques du robot.
Il peut être aussi intéressant de réfléchir à la notion de plus court chemin. En effet on peut parler de plus court chemin en distance matérielle, comme nous l’avons fait, mais aussi en terme de durée ou encore en terme d’énergie.
On peut ainsi se demander si la solution optimale correspond au plus court chemin en nombre de pixels ou bien s’il ne serait pas intéressant de chercher à définir un chemin moins courbe et plus simple, constitué d’un ensemble de vecteurs aux normes suffisamment grandes pour pouvoir inclure les notions d’accélération et décélération ; et ainsi inclure la notion de durée dans le calcul du plus court chemin.
Moore-Dijkstra
http://fr.wikipedia.org/wiki/Algorithme_de_Dijkstra
Bellmard-Ford
http://brassens.upmf-grenoble.fr/IMSS/mamass/graphecomp/bellmannFord.htm
OCF :
Pour La Science, n°231, mai 2000, p.66-73, « L’intelligence en essaim », Eric Bonabeau, Guy Théraulaz
Cours de DEA Resin : Filière Robots Mobiles
Annexe
1 Lancement
L’application produite pour la présente étude se nomme RobotPcc3rb.exe.
Une liste d’images test est fournie avec l’executable. Dans le sous répertoire labyrinthes.
Il n’y a pas que des labyrinthes, mais ceux-ci permettent de tester la recherche d’une solution unique de plus court chemin non trivial et le test de plusieurs chemins possibles en même temps.
2 Chargement d’une image d’environnement
Après avoir lancé l’application, il faut charger une image représentant l’environnement dans lequel le robot va évoluer. Pour le moment l’échelle fixée pour les caluls de notre application est 1 cm = 1 pixel, c’est à dire que chaque pixel peut être considéré comme une surface carrée de 1 cm de coté. L’image devra avoir les propriétés suivantes pour convenir à notre application : les pixels blancs sont les surfaces libres de l’environnement, et tous les autres pixels représentent des obstacles.
3 Choix des positions de départ et d’arrivée
Après avoir chargé une image d’envrionnement, il faut choisir le point de départ et le point d’arrivée du chemin que le robot doit effectuer. Pour cela il faut cliquer à droite directement sur l’image d’environnement en appuyant sur le bouton gauche de la souris. Une premiére fois, pour la position de départ, et une deuxiéme fois pour la position d’arrivée.
4 Modification du Rayon du Robot
L’utilisateur peut modifier à tous moments le rayon du robot. Cela permet de choisir l’encombrement que l’on veut donner au robot, et aussi d’agrandir le robot lors de l’animation. A remarquer que la visualisation du robot peut baver sur des pixels obstacles. Ce n’est qu’un problème de visualisation sous windows et non un problème de calcul d’une solution correcte. Ce point n’a pas encore put être réglé correctement.
5 Lancement du calcul d’un plus court chemin
Ensuite l’utilisateur peut lancer le calcul d’un plus court chemin en appuyant sur le bouton portant le même nom.
Là, si il n’y a pas de solution, un message adéquat est affiché dans le champ commentaire. Il y a deux raisons pour lesquelles le calcul du plus court chemin n’est pas possible.
Il n’existe pas de plus court chemin
La position de départ et/ou la position d’arrivée sont mal positionnées dans l’environnement. C’est à dire que ces positions tombent sur une case obstacle, ou sur une case non accessible à cause de l’encombrement du robot.
Dans ce dernier cas, il faut changer la position de départ et/ou la position d’arrivée.
6 Modifications des positions de départ et d’arrivée.
Si l’on veut modifier la position de départ et la position d’arrivée, il suffit d’appuyer sur le bouton « nouvelle position » et de choisir un nouveau départ et une nouvelle arrivée en cliquant à droite, directment sur l’image d’environnement.
7 Affichage d’un plus court chemin
Si une solution a été trouvée, l’image d’environnement se remplit alors de couleurs.
Voici la légende des couleurs utilisées comme ayant un sens particulier dans la visualisation :
Les pixels vert montrent le plus court chemin trouvé. Lex pixels vert kaki sont les endroits qui n’ont pas eu besoin d’être traités pour trouver le plus court chemin trouvable par notre algorithme implémentée.
Les pixels vert/bleu pâle, définissent les endroits où le robot ne peut aller à cause de son emcombrement.
Enfin, le gradient de couleur Du bleu vers le rouge, visualise la manière dont notre algorithme fonctionne : par gradient de distance. Plus un pixel est rouge plus il est proche du point d’arrivée. Plus un pixel est bleu, plus il proche du point de départ. L’effet de bord de cette visualisation permet de montrer d’un seul coup tous les points qui sont à la même distance du point de départ. Elle visualise la propagation de la recherche du plus court chemin de notre algorithme.(Un peu comme une onde de propagation dans un milieu, discrétisée sur une image.)
8 Démarrer / Arretter une l’Animation de la solution.
Quand une solution est trouvée, il suffit d’appuyer sur le bouton « démarrer animation » pour qu’un cercle (plus ou moins petit en fonction du rayon défini préalablement) symbolisant un robot apparaisse et commence à emprunter le plus court chemin que nous avons trouvé.
Il suffit de réappuyer sur le même bouton pour arrêter l’animation en court et recommencer une nouvelle animation depuis le debout. Remarque : l’animation tourne en boucle et est moins rapide en mode « mise de l’image à l’échelle » que sans.
9 Mise à l’échelle de l’image d’environnement
La case de selection « mise à l’échelle de l’image », permet d’agrandir de petites images d’environnement, ou au contraire de réduire des images d’environnement trop grandes pour être visualisées en entier dans la zone d’affichage de l’image d’environnement de notre application.
10 Boutons d’informations
Le bouton « ? » permet d’ouvrir la boite de dialogue « à propos »
Le bouton « aide » affiche une brève explication sur l’utilisation de l’application.
Le bouton « légende » affiche une brève légende sur les couleurs utilisées dans la visualisation du plus court chemin dans l’image d’envrionnement.
11 Quitter l’application
Enfin, le bouton « quitter » permet de fermer l’application et de libérer la mémoire du programme.
Les 3 Etapes de notre Algorithme
Etape1()
{
// Image est l’image d’environnement sur laquelle on travaille
// Temp est une image temporaire utilisée pour le traitement.
Répéter Rayon_du_robot - 1 fois
Temp est vide
Pour Tous les pixels (i,j) de Image
Temp(i,j)=Image(i,j)
SI Image(i,j) est INACESSIBLE ALORS
Temp(i-1,j)= INACESSIBLE
Temp(i+1,j)= INACESSIBLE
Temp(i,j-1)= INACESSIBLE
Temp(i,j+1)= INACESSIBLE
Temp(i-1,j-1)= INACESSIBLE
Temp(i+1,j+1)= INACESSIBLE
Temp(i+1,j-1)= INACESSIBLE
Temp(i-1,j+1)= INACESSIBLE
Temp(i,j)= INACESSIBLE
FSI
FinPour
Image=Temp
FinRépéter
}
bool Etape2()
{
// On utilise une pile dans laquelle on place des positions(i,j)
// au début de l’étape la pile est vide,
// à la fin de l’étape on la vide
Empile(Position_de_depart);
Image[Position_de_depart]=0.0
Boucle Infini
{
SI il n’y plus de Positions à dépiler
ALORS il n’y a pas de solution et on retourne FAUX
SINON on dépile une Position dans COORD
SI COORDest égale à Position_d’arrivée
ALORS il y a une solution et on retourne VRAI
Distance_courante=Image(COORD)
SI Image(COORD[i+1,j]) est LIBRE
ALORS
Image(COORD[i+1,j])=Distance_courante + 1
On empile COORD[i+1,j]
SI Image(COORD[i-1,j]) est LIBRE
ALORS
Image(COORD[i-1,j])=Distance_courante + 1
On empile COORD[i-1,j]
SI Image(COORD[i,j-1]) est LIBRE
ALORS
Image(COORD[i,j-1])=Distance_courante + 1
On empile COORD[i,j-1]
SI Image(COORD[i,j+1]) est LIBRE
ALORS
Image(COORD[i,j+1])=Distance_courante + 1
On empile COORD[i,j+1]
} Fin Boucle infini
} Fin Etape2
Etape3()
{
D = Image[Position_d’arrivée]
Longeur_chemin = 0
Boucle Infini
{
blocage1=blocag2=blocag3=blocag4=VRAI;
D1=Image[COORD(i+1,j)];
SI D1 est Libre ALORS blocage1=FAUX
D2=Image[COORD(i-1,j)];
SI D2 est Libre ALORS blocage2=FAUX
D3=Image[COORD(i,j+1)];
SI D3 est Libre ALORS blocage3=FAUX
D4=Image[COORD(i,j-1)];
SI D4 est Libre ALORS blocage4=FAUX
SI blocage4 est FAUX et blocage2 est FAUX
ALORS
D5=Image[I-1,J-1]
SI D5 < D ALORS D=D5 et nouvelle_position=COORD(i-1,j-1)
et nouveau_pas = racine de 2
SI blocage4 est FAUX et blocage1 est FAUX
ALORS
D6=Image[I+1,J-1]
SI D6< D ALORS D=D6 et nouvelle_position=COORD(i+1,j-1)
et nouveau_pas = racine de 2
SI blocage3 est FAUX et blocage2 est FAUX
ALORS
D7=Image[I-1,J+1]
SI d7< D ALORS D=D7 et nouvelle_position=COORD(i-1,j+1)
et nouveau_pas = racine de 2
SI blocage1 est FAUX et blocage3 est FAUX
ALORS
D8=Image[I+1,J+1]
SI d8< D ALORS D=D8 et nouvelle_position=COORD(i+1,j+1)
et nouveau_pas = racine de 2
SI D1
SI D2
SI D3
SI D4
Position_courante = nouvelle_position
Longeur_chemin += nouveau_pas
D=Image[COORD(i,j)];
La nouvelle position EST stockée comme nouvelle position du PCC
SI D est nulle ALORS on a fini de trouver le plus court chemin ;
Et on quitte cette étape.
} Fin boucle infini
} Fin Etape3
Algorithme globale :
DEBUT
Faire Etape1()
SI Etape2 retourne VRAI ALORS faire Etape3()
SINON il n’y a pas de solution
FINSI
FIN