Anytime Motion Planning

• Aussi appelé: anytime planning, anytime planner
• Catégorie: Planning & manipulation › Motion planning
• Mots-clés: motion-planning, sampling-based-planning, optimal-planning, real-time, bounded-computation

Planification de mouvement qui renvoie rapidement un chemin valide puis continue de l'améliorer tant que le temps le permet, de sorte qu'une réponse utilisable est disponible dès que le planificateur est arrêté.

Définition

Un planificateur de mouvement anytime (anytime motion planner) produit une première solution réalisable et sans collision le plus tôt possible, puis consacre le temps restant à l'améliorer, en général en réduisant la longueur du chemin, le temps d'exécution ou un autre coût. À chaque instant après la première solution, il détient une meilleure réponse provisoire qui peut être renvoyée s'il est interrompu. L'idée vient de la notion plus large d'algorithme anytime en intelligence artificielle, introduite par Dean et Boddy à la fin des années 1980, où la qualité de la solution est mise en balance avec le temps de calcul et où la relation entre les deux est décrite par un profil de performance (performance profile).

En recherche dans un graphe, le comportement anytime s'obtient généralement en lançant d'abord une heuristique pondérée et gonflée, puis en resserrant le poids tout en réutilisant l'effort de recherche antérieur, comme dans Anytime Repairing A (ARA). En planification par échantillonnage, les planificateurs asymptotiquement optimaux tels que RRT et la variante PRM des cartes de routes probabilistes sont naturellement anytime : ils continuent d'échantillonner et de reconnecter l'arbre après la première solution, et le coût du meilleur chemin tend vers l'optimum à mesure que le nombre d'échantillons augmente. Informed RRT et Batch Informed Trees (BIT) accélèrent la phase d'amélioration en limitant les échantillons à la région qui pourrait encore contenir un meilleur chemin. Un arbre aléatoire à exploration rapide** simple n'est pas anytime en ce sens, car il s'arrête dès que le but est connecté, même si l'on peut l'entourer de redémarrages ou d'un post-traitement.

L'amélioration au fil du temps est rarement régulière. Le coût baisse souvent par paliers, surtout quand le planificateur trouve un itinéraire passant par un autre interstice entre les obstacles, c'est-à-dire un chemin dans une nouvelle classe d'homotopie, et de longues périodes peuvent n'apporter presque aucun gain. La décision d'arrêt devient alors un problème à part entière : s'arrêter trop tôt sacrifie de la qualité, s'arrêter trop tard gaspille du temps que le robot pourrait passer à se déplacer. Les budgets de temps fixes sont la pratique courante, tandis que les méthodes de méta-raisonnement apprennent ou estiment le moment où un calcul supplémentaire n'en vaut plus la peine.

Pourquoi c'est important

Les robots disposent rarement d'un temps de planification fixe et connu. Un planificateur anytime fournit presque immédiatement une solution de repli sûre et convertit tout temps disponible en un meilleur mouvement, ce qui convient aux systèmes qui doivent agir dans un délai imparti tout en tenant à la qualité du chemin, à l'énergie ou au temps de cycle.

Applications principales

• Planification de mouvement de bras avec un budget de temps par requête dans les chaînes de manipulation
• Replanification pour les robots mobiles et les véhicules qui doivent agir selon un cycle de commande fixe
• Planification de chemin pour les robots aériens, où des chemins plus courts économisent la batterie
• Recherche heuristique dans des graphes sur des grilles et des treillis avec réduction du poids à la manière d'ARA*
• Recherche en méta-raisonnement sur le moment où arrêter de planifier et commencer à agir

En pratique

Un manipulateur mobile planifie les mouvements de son bras avec un planificateur par échantillonnage asymptotiquement optimal issu d'une bibliothèque comme OMPL. Chaque requête reçoit un budget de temps : le planificateur trouve généralement un premier chemin tôt dans ce budget, puis continue de le raccourcir. L'équipe enregistre le meilleur coût en fonction du temps écoulé sur de nombreuses requêtes enregistrées et constate que l'essentiel du gain arrive tôt, avec parfois de fortes baisses lorsqu'un itinéraire plus court autour d'un obstacle est trouvé tardivement. Au lieu de toujours utiliser tout le budget, elle s'arrête lorsque le coût ne s'est pas amélioré pendant un intervalle donné, ou utilise une règle d'arrêt apprise, puis applique au résultat un raccourcissement (shortcutting) et une paramétrisation temporelle avant de l'envoyer au contrôleur.

Idées reçues

• Anytime signifie que la première solution est quasi optimale — la première solution est souvent loin de l'optimum, et la qualité dépend de la durée d'exécution du planificateur
• Le coût s'améliore régulièrement avec le temps — il baisse généralement par paliers inégaux, séparés par de longs plateaux
• L'optimalité asymptotique garantit un bon chemin dans le budget de temps — elle ne décrit que la limite lorsque le calcul croît sans borne et ne dit rien d'un délai fini
• Utiliser tout le budget de temps est toujours préférable — le temps passé à planifier est du temps non passé à se déplacer, si bien que s'arrêter tôt est souvent le meilleur compromis

Qui devrait le savoir

• Ingénieurs en planification de mouvement qui configurent des planificateurs par échantillonnage ou par recherche
• Développeurs en manipulation mobile et en navigation travaillant sous des contraintes de temps réel
• Chercheurs en robotique qui étudient la planification à calcul borné
• Étudiants qui apprennent la planification de mouvement optimale

Technologies associées

• ARA (Anytime Repairing A)
• RRT*
• Informed RRT*
• BIT* (Batch Informed Trees)
• OMPL

Termes associés

• RRT*
• Rapidly-exploring random tree
• Probabilistic Roadmap
• Homotopy Class
• Warm Start
• Motion Planning

Projets associés

• GENESIS: World's fastest physics engine: 43M FPS for embodied AI learning
• Cartographer: Google's real-time 2D and 3D SLAM system for multi-platform robotics
• FAST-LIVO2: Fast, direct LiDAR-inertial-visual odometry from HKU-MARS, published in IEEE T-RO
• Dora AI: Dataflow middleware for AI robotics applications, built in Rust
• OpenMind OM1: AI-native operating system for robots with modular perception, cognition, and action
• Fast DDS: eProsima's high-performance DDS middleware — the default transport under ROS 2