Algorithme AStar
Un article de Wikibot.
Sommaire |
[modifier] Généralités
Algorithme de résolution de problème combinatoire et d'ordonancement.
Cet algorithme est souvent utilisé pour la recherche de chemin.
[modifier] Principe
L'algorithme se base sur deux listes, l'une appelée liste ouverte, l'autre liste fermée. La liste ouverte est la liste des solutions à examiner, la liste fermée la liste des solutions déjà examinées.
[modifier] Présentation de l'algorithme à travers l'exemple de la recherche de plus court chemin
L'espace est divisé en cases, le robot occupe l'une des cases, il cherche à se rendre sur une destination finale. Des obstacles sont présent sur le damier et sont infranchissables.
Objectif : trouver le plus court chemin du départ à l'arrivée, en explorant le plus petit nombre possible de solution.
L'espace peut être représenté sous forme d'un réseau où chaque case représente un nœud. Chaque nœud est relié à ses huit voisins. Les cases obstacles ne sont reliées à aucune autre case.
Le robot se déplace le long des liens.
Initialisation
A partir de sa position initiale le robot, va explorer les cases voisines à la sienne en suivant les liens disponibles. il calcul un score pour chacune de ces cases en mesurant la distance euclidienne de la case candidate à la case objectif. Il va ensuite empiler ces cases candidates dans la liste ouverte, du score le moins bon (distance la plus grande), au meilleur score (distance la plus courte).
Itération
Si la liste ouverte est vide, cela signifie qu'il n'y a pas de solution.
L'algorithme dépile le premier nœud de la liste ouverte que l'on appellera nœud courant. On calcul pour chacun des nœuds voisins qui ne sont pas dans la liste fermée la distance euclidienne avec le nœud objectif, puis le score du nœud (qui vaut score du nœud courant + distance euclidienne). Dans chaque nœud référencé le nœud courant, qu'on appellera nœud appelant.
Si la case objectif est atteinte alors aller à solution, sinon empiler les nœuds voisins dans la liste ouverte du moins bon score au meilleur, empiler le nœud courant dans la liste fermée.
Solution
A partir du nœud objectif, remonter les nœuds appelant, c'est l'ensemble des nœuds par lequel le robot devra passer pour se rendre à l'objectif.
[modifier] Exemple de code
A faire: {{{1}}}
[modifier] Application à la robotique
A faire: {{{1}}}
