Feuille de route probabiliste - Probabilistic roadmap
Le planificateur de feuille de route probabiliste est un algorithme de planification de mouvement en robotique, qui résout le problème de déterminer un chemin entre une configuration de départ du robot et une configuration d'objectif tout en évitant les collisions.
L'idée de base derrière PRM est de prélever des échantillons aléatoires dans l' espace de configuration du robot, de les tester pour savoir s'ils se trouvent dans l'espace libre et d'utiliser un planificateur local pour tenter de connecter ces configurations à d'autres configurations proches. Les configurations de départ et d'objectif sont ajoutées et un algorithme de recherche de graphique est appliqué au graphique résultant pour déterminer un chemin entre les configurations de départ et d'objectif.
Le planificateur de feuille de route probabiliste se compose de deux phases: une phase de construction et une phase de requête. Dans la phase de construction, une feuille de route (graphique) est construite, approximant les mouvements qui peuvent être effectués dans l'environnement. Tout d'abord, une configuration aléatoire est créée. Ensuite, il est connecté à certains voisins, typiquement soit les k voisins les plus proches, soit tous les voisins inférieurs à une certaine distance prédéterminée. Les configurations et les connexions sont ajoutées au graphique jusqu'à ce que la feuille de route soit suffisamment dense. Dans la phase de requête, les configurations de début et d'objectif sont connectées au graphique, et le chemin est obtenu par la requête de chemin le plus court d' une Dijkstra .
Compte tenu de certaines conditions relativement faibles sur la forme de l'espace libre, PRM est probabilistiquement complet, ce qui signifie que lorsque le nombre de points échantillonnés augmente sans limite, la probabilité que l'algorithme ne trouve pas de chemin s'il en existe s'approche de zéro. Le taux de convergence dépend de certaines propriétés de visibilité de l'espace libre, où la visibilité est déterminée par le planificateur local. En gros, si chaque point peut "voir" une grande partie de l'espace, et aussi si une grande partie de chaque sous-ensemble de l'espace peut "voir" une grande partie de son complément, alors le planificateur trouvera rapidement un chemin.
L'invention de la méthode PRM est attribuée à Lydia E. Kavraki . Il existe de nombreuses variantes de la méthode PRM de base, certaines assez sophistiquées, qui varient la stratégie d'échantillonnage et la stratégie de connexion pour obtenir des performances plus rapides. Voir par exemple Geraerts & Overmars (2002) pour une discussion.
Les références
 |
Cet article lié à la robotique est un bout . Vous pouvez aider Wikipedia en le développant . |