Planification, partie 1 : la recherche de chemin

La recherche de chemin (pathfinding) étant une fonctionnalité incontournable d’un robot mobile, plusieurs articles lui seront dédiés :

  • cet article d’initiation, qui traite de méthodes classiques de recherche de chemin ;
  • un article d’initiation qui traitera des différences entre théorie et pratique : le passage du graphe à la table de jeu, la différence entre plus court chemin et plus rapide chemin ;
  • un article d’initiation sur les calculs de collisions;
  • un article avancé qui s’attaquera à la replanification en cas d’apparition (ou de disparition) d’obstacles;
  • un article avancé sur la planification d’actions ;
  • un article avancé sur l’algorithme de recherche de chemin de TechTheTroll, qui permet la replanification et qui fournit une trajectoire courbe praticable par un robot.

Le problème de la recherche de chemin

La recherche de chemin (pathfinding en anglais) est un problème qui se rencontre très souvent en robotique. Par exemple, à Eurobot, un robot enchaîne plusieurs actions, et doit donc souvent se déplacer d’un point à un autre. Il y a deux manières de faire les choses :

  • statiquement, de manière scriptée : le programmeur a entré à la main le chemin à prendre et le robot le suivra ;
  • dynamiquement : un algorithme fournit au robot l’itinéraire à suivre.

Bien qu’écrire statiquement l’itinéraire puisse être suffisant dans certains cas et possède quelques avantages (pas de temps de calcul), ce n’est pas du tout adapté à Eurobot. En effet, sur la table le robot adverse se déplace également, ce qui signifie que des itinéraires peuvent être bloqués. Il peut aussi y avoir des éléments de jeu qui disparaissent (ce qui modifie encore l’itinéraire). Et puis que se passe-t-il si le robot doit effectuer un itinéraire qui n’est pas prévu ?

Bref, vous l’aurez compris, des itinéraires statiques ne sont pas robustes (et vous savez ce que je pense de la fiabilité). Heureusement, nous disposons d’algorithmes efficaces pour calculer en temps réel un chemin entre deux points.

Le formalisme : la théorie des graphes

Les algorithmes de recherche de chemin s’appuient sur la notion mathématique de graphe. Pour faire simple, un graphe est un ensemble de nœuds reliés par des arcs. Chaque arc possède une certaine valeur, qui est un coût. Tous les nœuds ne sont pas forcément reliés entre eux.

Il faut bien comprendre que mathématiquement, un « nœud » peut représenter n’importe quoi. La théorie des graphes s’applique à de nombreux problèmes, comme le routage des données sur les Internets, l’apprentissage automatique et, bien sûr, la recherche de chemin.

Un exemple de graphe avec 5 nœuds et 6 arcs valués. J’espère que vous appréciez mes talents de graphiste.

Dans le cas de la recherche de chemin, un nœud est une position sur la table et la valuation d’un arc est la distance entre les deux nœuds qu’il relie. Ainsi, en plaçant des nœuds à certains endroit de la table, des algorithmes peuvent établir un itinéraire (qui est en fait une suite de nœuds qui forment une ligne brisée). Dans ce cas, il y a un arc entre deux nœuds s’il n’y a pas d’obstacle sur la table entre eux. Le placement de ces nœuds sera discuté à la fin de cet article.

Je précise bien qu’on minimise la somme des valuations des arcs. Ainsi, dans l’exemple précédent, le plus court chemin entre A et E est A-B-C-D-E (avec une valuation totale de 9), et non pas A-E (avec une valuation totale de 12).

Enfin, un point de vocabulaire. Lorsqu’on demande à un algorithme de chercher un chemin depuis A vers B, on appelle A le nœud de départ et B le nœud d’arrivée.

L’algorithme de Dijkstra

Cet algorithme est heureusement plus simple que le nom de son inventeur ; c’est l’ancêtre de la majorité des algorithmes de recherche de chemin modernes. Ainsi, je vous le présente non pas pour ses performances, mais parce que le comprendre est nécessaire pour comprendre les prochains algorithmes.

Le principe de cet algorithme est de partir du point de départ et d’affecter à chaque autre nœud sa distance minimale au nœud de départ. Pour cela, on prend le nœud N de distance minimale (la première fois, c’est le nœud de départ lui-même), et on affecte à ses voisins Vi la distance de N plus la valuation de l’arc entre N et Vi. Si un nœud est revisité, alors on met à jour sa valeur si elle diminue sa distance.

Un exemple clair, étape par étape, se trouve ici. Je vous invite à le lire : c’est un algorithme fondamental, qui n’est pas bien compliqué une fois qu’il est compris.

À la fin de l’algorithme, on dispose du plus court chemin depuis le nœud de départ vers n’importe quel point. C’est-à-dire qu’il n’a pas seulement trouvé le plus court chemin du point de départ au point d’arrivée, mais beaucoup d’autres ! D’une manière générale, Dijkstra part dans toutes les directions, et ne prend pas en compte le nœud d’arrivée.

Une version plus rapide et plus maligne existe : l’algorithme A*.

L’algorithme A*

L’algorithme A* (qu’on prononce « A star » ou « A étoile ») est une extension de l’algorithme de Dijkstra. Sa différence est qu’il va chercher à se diriger vers le nœud d’arrivée, à l’aide d’une heuristique. Une heuristique est une fonction qui, pour deux nœuds, renvoie une valeur. Cette fonction peut être quelconque mais doit satisfaire une contrainte : elle ne doit jamais surestimer la distance réelle.

Un exemple simple dans le cadre de la recherche de chemin est la distance euclidienne (la distance à vol d’oiseau) ; c’est une certaine distance qui est forcément inférieure ou égale à la distance réelle à parcourir. Un autre exemple simple est la fonction nulle : en effet, la distance entre deux nœuds est forcément positive. Dans ce cas, l’algorithme A* se réduit à l’algorithme de Dijkstra.

Plus concrètement, la différence de cet algorithme est dans le calcul de la distance à affecter à un nœud. Au lieu de lui affecter la distance au nœud de départ, on affecte la distance minimale entre le nœud de départ et d’arrivée qu’on pourrait obtenir si on passait par ce nœud.

De même, je vous conseille la lecture de cet article, qui contient également le pseudo-code de cet algorithme.

Autant l’algorithme de Dijkstra ne convient pas à une utilisation à Eurobot, autant l’algorithme A* donnera des résultats satisfaisants.

Mais ce n’est pas tout à fait fini : il reste un problème. L’algorithme A* produit un itinéraire comme une liste de nœuds ; mais supposons que par exemple A* vous renvoie la trajectoire verte dans l’image suivante (ce qui est tout à fait possible).

thetastar_intro

Vous voyez le problème ? Vous imaginez mal votre robot suivre cette courbe étrange pleine d’angles. En effet, il est nécessaire de lisser un itinéraire fourni par A* (ou Djikstra) afin d’avoir un mouvement réaliste et simple à effectuer pour le robot. Concrètement, cela signifie vérifier si on ne peut pas sauter des morceaux de l’itinéraire. Par exemple, si A* me renvoie l’itinéraire A-B-C-D, je vais vérifier la visibilité entre A et C (c’est-à-dire vérifier l’absence d’obstacle entre A et C). S’il n’y a pas d’obstacle entre A et C, alors je vais retirer B de l’itinéraire. Et ainsi de suite.

L’origine de ce problème sera expliqué dans l’article suivant ; pour faire simple, cela provient du fait qu’on simplifie le graphe en retirant des arcs.

L’algorithme Theta*

L’algorithme Theta* est une modification de l’algorithme A*, qui vise à pallier le problème du lissage. En effet, certaines trajectoires sont plus faciles à lisser que d’autres (cf. l’image ci-dessus). L’algorithme Theta* (qui fait partie d’une manière plus générale de la famille des algorithmes any-angle path planning) va lisser la trajectoire tout en la recherchant.

Il n’y a pas beaucoup de différences de performances avec l’A*, je ne vais donc pas le détailler ; sachez tout de même qu’il existe. Si vous souhaitez en savoir plus sur cet algorithme, je vous invite à lire cet article.

L’algorithme Weighted A*

Si l’algorithme A* nous assure de trouver le plus court chemin, c’est grâce à son heuristique qui ne surestime jamais la distance réelle entre deux points. Mais que se passe-t-il si cette condition n’est pas vérifiée ? C’est ce que fait l’algorithme Weighted A*, qui est identique à l’algorithme A* sauf que son heuristique ne vérifie pas cette propriété. Concrètement, au lieu de prendre comme heuristique la distance euclidienne, on prendra par exemple trois fois cette distance.

Cette variante donne généralement une trajectoire suboptimale (c’est-à-dire que ce n’est pas la plus courte possible) mais son calcul est plus rapide. A vous de voir si cela en vaut le coût.

L’algorithme HPA* (Hierarchical Pathfinding A*)

Cet algorithme est encore une variante d’A*. L’idée est la suivante : si vous cherchez à vous rendre à la Ferté-Bernard, vous n’allez pas prendre un immense plan de France pour tout parcourir, rue par rue, jusqu’à trouver un chemin satisfaisant. Vous allez probablement regarder quelles autoroutes sont sur le chemin, ou alors quel train arrive dans les environs de la Ferté-Bernard. Puis, seulement après, vous allez prévoir plus précisément comme se rendre de l’autoroute à la Ferté-Bernard, ou comment aller de la gare de la Ferté-Bernard à la Coupe de France de robotique.

C’est une recherche hiérarchique : vous cherchez d’abord avec un faible niveau de détail, vous faîtes un itinéraire grossier que vous affinez en prenant une carte plus détaillée. C’est ce que fait l’algorithme HPA*.

Je vous invite à consulter cet article pour plus de détails sur le HPA*.

Conclusion

Il existe beaucoup d’autres variantes du A*. Si vous deviez n’en retenir qu’un, je vous recommanderai le Weighted A* qui, avec un poids correctement choisi, est rapide et fournit un chemin satisfaisant. N’oubliez un post-traitement de lissage afin que la trajectoire puisse être utilisable pour le robot.

Tlt,
PF

Votre commentaire

Entrez vos coordonnées ci-dessous ou cliquez sur une icône pour vous connecter:

Logo WordPress.com

Vous commentez à l’aide de votre compte WordPress.com. Déconnexion /  Changer )

Photo Google

Vous commentez à l’aide de votre compte Google. Déconnexion /  Changer )

Image Twitter

Vous commentez à l’aide de votre compte Twitter. Déconnexion /  Changer )

Photo Facebook

Vous commentez à l’aide de votre compte Facebook. Déconnexion /  Changer )

Connexion à %s