Recherche de chemin à travers l’algorithme A* en C++ 3/4 : étude des algorithmes de recherche de chemin

Recherche de chemin 3/4.pdf Download

La recherche de chemin (pathfinding) est un problème de planification et de recherche solution. Il consiste à trouver comment se déplacer dans un environnement entre un point de départ et un point d’arrivée en prenant en compte différentes contraintes.

L’objet de ce cours est de rappeler dans un premier temps les bases de la complexité et de l’algorithmie, des algorithmes de recherche de chemin naïfs seront ensuite étudiés avant de converger vers un algorithme de recherche de chemin usuel : l’A*

Contenus de la page

Bases de la complexité algorithmique

L’objet de cette section est de définir les notions de bases permettant de caractériser un algorithme. Un grand nombre de problèmes fournissent dans la définition mathématique des objets mentionnés une solution algorithmique. Si nous utilisons la définition de $x^n$ naïve, à savoir $x$ multiplié par lui-même $n$ fois, nous obtenons l’algorithme suivant :

fonction puissance1(x:réel, a:entier): réel
  res = 1.0
  faire a fois
    res = res * x
  retourner res

Une autre définition de la puissance est la relation récursive $x^a$ est égal à 1 si $a$ vaut 0 et $x.x^{a-1}$ sinon.

fonction puissance2(x:réel, a:entier): réel
  si (a=0) alors
    res = 1.0
  sinon
    res = x.puissance2(x,a-1)
  retourner res

Ces deux algorithmes sont tous deux corrects, mais ne sont pas équivalents, le second utilisant davantage de ressources espace que le premier. Les deux ressources que nous considérons ici sont le temps et l’espace.

Un algortihme est un objet qui à partir de toute entrée permet d’exécuter des instructions en consommant deux ressources :

du temps. Le temps sera évalué en considérant le nombre d’instructions élémentaires devant être exécutées : une instruction est élémentaire si elle peut être exécutée en un temps fixe
de l’espace. L’espace est le nombre d’octets utilisé par l’exécution de l’algorithme. Il ne tient pas compte de l’espace utilisé par les objets fournis en entrée.

Instruction élémentaire

Le caractère élémentaire d’une instruction dépend des hypothèses initiales. Ainsi, si l’on décide de manipuler des entiers à taille fixe, l’addition d’entiers doit être considérée comme élémentaire. À l’opposé si l’on considère des entiers pouvant être de grande taille, l’addition ne peut plus être considérée comme élémentaire car elle nécessite autant de manipulations de bits qu’il y en a de présents.

Complexité en temps dans le pire des cas

La complexité en temps dans le pire des cas d’un algorithme A est la fonction qui a tout entier n associe le nombre d’instructions élémentaires maximales exécutées par A sur des entrées de complexité $n$. Ainsi l’algorithme :

fonction decalage(a: entierLong): entierLong
  si a=0 alors retourner 0
  tant que estPair(a) faire 
    a = a/2
  retourner a

qui consiste à supprimer les bits nuls de poids faible a une complexité en temps :

constante pour tout entier impair
égale à $log(a)$ pour toute puissance de 2

Ainsi la complexité en temps dans le pire des cas est $log(a)$

Complexité en espace

Pour définir la complexité en espace, il suffit de remplacer le terme « nombre d’instructions élémentaires exécutées par A » par « nombre d’octets utilisées lors de l’exécution de A ».

Notations et simplifications

Le calcul des complexités est complexe. Pour les mêmes raisons qu’en ce qui concerne la terminaison, il n’existe pas de méthode générale (ou algorithme) pour calculer la complexité d’un algorithme et encore moins celle d’un problème. Nous montrerons comment évaluer la fonction complexité d’un algorithme en évaluant non pas précisément cette fonction, mais la classe à laquelle elle appartient.

À une constante multiplicative près : notation $\Theta$

Les fonctions complexité que nous considérons dès à présent sont supposés à valeurs entières strictement positives.

Supposons que nous utilisons des entiers manipulés au travers d’additions et de multiplications considérées comme instructions élémentaires. Supposons que nous ayons deux algorithmes. Le premier sur une entrée de taille $n$ provoque $10 n$ addition et $n$ multiplications. Le second $n$ additions et $2.n$ multiplications. Le premier a pour complexité en temps $n \rightarrow 11 n$. Le second $n \rightarrow 3 n$

Lequel est optimal ? En fait tout dépend des complexités réelles de l’addition et de la multiplication.

ou on comptabilise pour chacune des opérations le nombre d’exécutions. Nous obtenons alors tant de comparaisons, tant d’affectations, tant d’additions, tant de multiplication. Cette précision est parfois nécessaire dans l’étude d’algorithmes embarquées ou à temps réel mais est coûteuse.
ou on considère toutes ces opérations élémentaires comme équivalentes.

En conséquence de quoi, deux fonction $f$ et $g$ égales à une constante multiplicative près devront être considérées comme équivalentes.

La conséquence de ceci, deux fonctions $f$ et $g$ pour lesquelles il existe des réels $0 < \alpha$ et $0 < \beta$ tels que :

$$\forall n \alpha .f(n) \leq g(n) \leq \beta f(n)$$

Cela induit la notation $\Theta$. Soit $f: {N}^\ast \rightarrow {N}^\ast$ une fonction. Nous noterons $\Theta(f)$ l’ensemble des fonctions $g: {N}^\ast \rightarrow {N}^\ast$ telles qu’il existe un entier $N$, deux réels $\alpha$ et $\latex B$ tels que pour tout entier $n > {N}$ on ait :

$$\forall n \alpha .f(n) \leq g(n) \leq \beta f(n)$$

Simple majoration : notation $\mathcal{O}$

Pour toute fonction $f$ la classe $\mathcal{O}(f)$ est l’ensemble des fonction $g$ telles qu’il existe un entier $N$ et un réel $\alpha > 0$ tels que pour tout entier $n > N$ on ait

$$g(n) < \alpha f(n)$$

Cela conclut ce court rappel des notations et calculs des complexités, pour plus d’informations : https://www.apprendre-en-ligne.net/info/bibliotheque/initiation-algorithmique.pdf

Les algorithmes de recherche de chemin

Deux algorithmes déterministes principaux sont utilisées pour la recherche du plus court chemin dans un graphe

l’algorithme de Dijkstra, qui permet de déterminer le chemin optimal. Il est par exemple utilisé pour le routage internet
l’algorithme A* qui est beaucoup plus rapide à condition d’avoir une bonne fonction heuristique et dont l’optimalité n’est garantie que sous certaines conditions. En pratique l’algorithme A* est un bon compromis entre coût de calcul et optimalité de la solution.

Algorithme A*

Principe de l’algorithme

Au premier abord, on pourrait se dire que pour trouver un chemin d’un point à un autre il faut commencer par se diriger vers la destination. L’A* utilise cette idée, à chaque itération, nous allons tenter de nous rapprocher de la destination, nous allons donc privilégier les possibilités directement plus proches de la destination, en mettant de côté toutes les autres.

Toutes les possibilités ne permettant pas de se rapprocher de la destination sont mises de côté, mais pas supprimées. Elles vont simplement être mises dans une liste de possibilités à explorer si jamais la solution explorée actuellement s’avère mauvaise. En effet, nous ne pouvons pas savoir à l’avance si un chemin va aboutir ou bien sera le plus court. Il suffit que ce chemin amène à une impasse pour que cette solution devienne inexploitable.

L’algorithme va donc d’abord se diriger vers les chemins les plus directs. Et si ces chemins n’aboutissent pas ou bien s’avèrent mauvais par la suite, il examinera les solutions mises de côté. C’est ce retour en arrière pour examiner les solutions mises de côté qui nous garantit que l’algorithme nous trouvera toujours une solution si elle existe.

Nous pouvons donc lui donner un terrain avec autant d’obstacles que nous voulons, s’il y a une solution, A* la trouvera

Les listes A*

A* utilise deux listes, ces listes contiennent donc des points. Pour être plus général, nous pouvons même dire que ces listes contiennent des nœuds d’un graphe, lequel graphe représentant notre terrain.

La première liste, appelée liste ouverte, va contenir tous les nœuds étudiés. Dès que l’algorithme va se pencher sur un nœud du graphe, il passera dans la liste ouverte (sauf s’il y est déjà)

La seconde liste, appelée liste fermée, contiendra tous les nœuds qui, à un moment où à un autre, ont été considérés comme faisant partie du chemin solution. Avant de passer dans la liste fermée, un nœud doit d’abord passer dans la liste ouverte, en effet, il doit d’abord être étudié avant d’être jugé comme bon.

Le déroulement de l’algorithme

Pour déterminer si un nœud est susceptible de faire partie du chemin solution, il faut pouvoir quantifier sa qualité. Vous êtes entièrement libre de ce côté-là, vous pouvez mesurer la pertinence d’un nœud de la manière que vous préférez. Néanmoins, une méthode souvent utilisée et qui donne de bons résultats est de mesurer l’écartement entre ce nœud et le chemin à vol d’oiseau. Nous calculons donc la distance entre le point étudié et le dernier point que nous avons jugé comme bon. Nous calculons aussi la distance entre le point examiné et le point de destination. La somme de ces deux distances nous donne la qualité du nœud exploré. Plus un nœud a une qualité faible, meilleur, il est.

Vous pouvez calculer ces distances de la manière que vous voulez, distance euclidienne, distance de Manhattan ou autre, elles peuvent convenir.

Nous ne savons pas grand-chose du chemin solution si ce n’est que le point qui pourra nous rapprocher de la solution est un point voisin du point que nous étudions. Nous allons donc étudier chacun des nœuds voisins du nœud courant pour déterminer celui qui a le plus de chances de faire partie du chemin solution.

La recherche de chemin commence par le premier point, en étudiant tous ses voisins, en calculant leur qualité, et en choisissant le meilleur pour continuer. Chaque point examiné est mis dans la liste ouverte et le meilleur de cette liste passe dans la liste fermée, il va servir de base pour la recherche suivante.

Ainsi, à chaque itération, nous allons regarder parmi tous les nœuds qui ont été étudiés (et qui n’ont pas encore été choisis) celui qui a la meilleure qualité. Et il est tout à fait possible que le meilleur ne soit pas un voisin direct du point courant. Cela signifiera que le point courant nous éloigne de la solution et qu’il faut corriger le tir.

L’algorithme s’arrête quand la destination a été atteinte ou bien lorsque toutes les solutions mises de côté ont été étudiées et qu’aucune ne s’est révélée bonne, c’est le cas où il n’y a pas de solution.

Détermination des nœuds voisins

Si on considère notre domaine de recherche comme un graphe, tous les nœuds voisins d’un nœud courant sont les nœuds adjacents. Mais si nous considérons notre domaine de recherche comme une carte ce sont tous les point adjacents sauf si ceux-ci contiennent des obstacles infranchissables.

Donc, avant de se lancer dans l’étude de la qualité de chacun des nœuds adjacents, il ne faut prendre que ceux qui sont vraiment utilisables. Il faut aussi mettre de côté tous les nœuds déjà présents dans la liste ouverte ou dans la liste fermée. Et pour être plus précis, je dirais qu’il ne faut pas prendre un point s’il est déjà dans la liste ouverte, à moins qu’il ne soit meilleur, auquel cas, nous allons mettre à jour la liste ouverte.

Ce qu’il faut regarder sur chacun des nœuds voisins potentiels :

est ce un obstacle ? Si oui, nous oublions ce nœud
est il dans la liste fermée ? Si oui, ce nœud a déjà été étudié ou bien est en cours d’étude, on ne fait rien
est il dans la liste ouverte ? Si oui, on calcule la qualité de ce nœud, et si elle est meilleure que celle de son homologue dans la liste ouverte, nous modifions le nœud présent dans la liste ouverte
sinon, nous l’ajoutons dans la liste ouverte et nous calculons sa qualité

Notion de parent d’un nœud

Chaque nœud a un parent, c’est par lui que nous arrivons là où nous sommes. Le parent représente le meilleur chemin entre deux nœuds. Le parent est très important à la fin de l’algorithme, pour retrouver son chemin.

Il joue aussi un rôle important lors de la mise à jour d’un nœud dans la liste ouverte. Nous avons vu qu’il fallait mettre à jour la liste ouverte dans le cas où un nœud avait une meilleure qualité que ce même nœud dans la liste ouverte. Nous avons mis à jour la qualité du nœud dans la liste ouverte, mais il faut aussi mettre à jour son parent, pour bien signifier que cette qualité est possible par tel parent précis.

Une fois que la destination a été atteinte, il faut retrouver le chemin en suivant à chaque fois les parents des nœuds présents dans la liste fermée. Nous remontons le fil jusqu’à arriver au point de départ.

Résumé

On commence par le nœud de départ, c’est le nœud courant.
On regarde tous ses nœuds voisins.
Si un nœud voisin est un obstacle, on l’oublie.
Si un nœud voisin est déjà dans la liste fermée, on l’oublie.
Si un nœud voisin est déjà dans la liste ouverte, on met à jour la liste ouverte si le nœud dans la liste ouverte a une moins bonne qualité (et on n’oublie pas de mettre à jour son parent).
Sinon, on ajoute le nœud voisin dans la liste ouverte avec comme parent le nœud courant.
On cherche le meilleur nœud de toute la liste ouverte. Si la liste ouverte est vide, il n’y a pas de solution, fin de l’algorithme.
On le met dans la liste fermée et on le retire de la liste ouverte.
On réitère avec ce nœud comme nœud courant jusqu’à ce que le nœud courant soit le nœud de destination.

Pseudo code de l’algorithme A*

Voici une implémentation possible de l’algorithme en pseudo code, pour une recherche de chemin dans une carte qui est un tableau à deux dimensions tel que chaque case contient un état : traversable ou non

Structure nœud = {
  x,y : Nombre
  cout, heuristique: Nombre
}

depart = Nœud(x=_, y=_, cout=0, heuristique=0)

Fonction compare2Nœuds(n1: Nœud, n2: Nœud)
  si n1.heuristique < n2.heuristique
    retourner 1
  sinon si n1.heuristique == n2.heuristique
    retourner 0
  sinon 
    retourner -1

Fonction cheminPlusCourt(g:Graphe, objectif:Nœud, depart:Nœud)
   closedList = File()
   openList = FilePrioritaire(comparateur=compare2Noeuds)
   openList.ajouter(depart)
   tant que openList n'est pas vide
       u = openList.defiler()
       si u.x == objectif.x et u.y == objectif.y
           reconstituerChemin(u)
           terminer le programme
       pour chaque voisin v de u dans g
           si non(v existe dans closedList ou v existe dans openList avec un coût inférieur)
                v.cout = u.cout +1 
                v.heuristique = v.cout + distance([v.x, v.y], [objectif.x, objectif.y])
                openList.ajouter(v)
       closedList.ajouter(u)
   terminer le programme (avec erreur)

Digression : Planification de trajectoires dans un environnement incertain

Pour ce type de navigation deux approches sont possibles, les approches délibératives et les approches réactives.

Les approches réactives consistent à calculer à chaque pas de temps (après récupération des informations sur l’environnement fournies par les capteurs du système) le contrôle instantané à appliquer sur les actionneurs du système. Plusieurs approches réactives existent, nous pouvons citer la navigation par diagrammes de proximité, la navigation basée sur les états de collisions inévitables ou encore la navigation par champs de potentiels. Cette dernière est l’une des plus connues et facile à appliquer, elle consiste à considérer le robot mobile comme une particule soumise à divers champs électromagnétiques régissant son mouvement.

Ces approches sont intéressantes et pourraient être utilisées dans le cadre de la navigation dans un environnement tel que le nôtre, cependant plusieurs limites apparaissent. En effet, les modèles primitifs permettent de gérer les robots holonomes avec des obstacles se déplaçant à vitesse constante une perspective serait d’étendre ces modèles pour combler ces manques, mais nous pouvons aussi nous tourner vers d’autres méthodes de navigation : les méthodes délibératives.

Les méthodes délibératives consistent à résoudre un problème de planification de mouvement. La planification de mouvement est la détermination a priori d’une stratégie de mouvement entre une position initiale et une position finale du robot à partir d’une représentation de l’environnement dans lequel il évolue. Plusieurs méthodes existent dans ce domaine, nous pouvons citer la méthode par graphes où le but est de tenter de capturer la topologie de l’espace de recherche pour simplifier le problème à une recherche dans un graphe. Elles sont donc constituées de deux étapes :

Construction du graphe dans l’espace de recherche approprié
Parcours du graphe dans le but de déterminer un chemin ou une trajectoire entre les configurations initiale et finale

Le parcours du graphe s’effectue la plupart du temps en utilisant un algorithme heuristique tel que le A* est utilisé dans le but d’éviter l’exploration complète de l’espace de recherche. En parallèle de la planification classique par exploration d’un graphe de recherche sont apparues les méthodes par arbres. Celle-ci consistent à construire un arbre à partir de la configuration initiale du système. Cet arbre se développe ensuite dans toutes les directions du robot dans l’espace de recherche. Parmi les méthodes par arbre l’une des plus connues et utilisées sont les RRT (Rapidly-exploring Random Trees, RRT), nous allons étudier plus en profondeur les algorithmes RRT et plus particulièrement à l’une de ses variante, le RiskRRT.

Commençons par présenter l’algorithme RRT avant de présenter son extension. À partir d’une configuration initiale $q_0$, l’espace de configuration du système est exploré en choisissant aléatoirement à chaque itération une nouvelle configuration $q_{nv}$ non obstruée par les obstacles vers laquelle se diriger. La branche la plus proche de l’arbre déjà construit est alors déterminée puis étendue en direction de $q_{nv}$. En répétant le processus, l’espace de recherche est alors rapidement couvert, et un chemin vers toutes configurations de cet espace peut alors être facilement déterminée s’il en existe un. Le but de la planification étant néanmoins d’atteindre une configuration finale $q_f$, le processus essaie de déterminer un chemin liant la configuration la plus proche de l’arbre à $q_f$ après un certain nombre d’itérations de l’expansion de l’arbre.

Le RiskRRT est une méthode de planification partielle conçue pour fonctionner en environnement dynamique et incertain. Cette extension de l’algorithme RRT génère des trajectoires partielles orientées vers le but et évaluées par une probabilité de succès. L’algorithme permet de planifier une trajectoire dans des environnements partiellement connus, incertains, dynamiques et humaines. Nous allons maintenant présenter l’algorithme RiskRRT. Ce dernier gère le fait que le robot ne connaît pas son environnement en totalité. L’algorithme va alors générer des trajectoires dans les zones visibles, la trajectoire la mieux notée selon nos critères est alors choisie. Le suivi de cette trajectoire est alors initié, l’algorithme étend alors l’arbre des trajectoires en fonction des nouvelles données disponibles, si une meilleure trajectoire est trouvée, le robot commencera à la suivre et ainsi de suite.

À ce stade l’algorithme est capable d’évoluer dans un environnement méconnu, mais il reste deux problématiques, comment évaluer chaque trajectoire d’une part et comment éviter les obstacles mobiles d’autre part.

En effet l’évaluation des différentes trajectoires générées par le RiskRRT, lors de la recherche de trajectoire, chaque nœud est évalué par un risque de collision. Ce risque de collision est calculé à l’aide de deux valeurs, la probabilité que le robot entre en collision avec un obstacle statique et la probabilité que le robot entre en collision avec un obstacle dynamique. In fine, le coût dépend de la distance qui le rapproche d’un but et de son orientation par rapport à l’orientation au but, mais aussi de sa probabilité de collision.

Il reste à traiter le cas des obstacles dynamiques, pour cela, le RiskRRT suppose que les obstacles dynamiques suivent des trajectoires typiques et ne sont pas des particules errant aléatoirement dans l’espace. Les méthodes de prédiction de la position des obstacles mobiles sont variés, nous pouvons citer la prédiction linéaire à court terme si le robot possède peu d’information sur l’environnement voir des modèles à plus long terme. Ces modèles sont appris en amont et utilisés pendant l’évolution du robot.

En somme la combinaison du calcul du coût probabiliste et la prévision des trajectoires des obstacles permet de générer des trajectoires fiables permettant de naviguer dans un environnement incertain et dynamique.