Kinodynamic Planning

Aussi appelé: kinodynamic motion planning
Catégorie: Planning & manipulation › Motion planning
Mots-clés: motion-planning, dynamics, sampling-based-planning, trajectory-optimization, state-space

Une planification de mouvement qui respecte à la fois les contraintes géométriques, comme les collisions, et la dynamique du système, en trouvant des entrées de commande au cours du temps plutôt qu'un simple chemin sans collision.

Définition

La planification kinodynamique (kinodynamic planning) est une planification de mouvement dans laquelle la solution doit satisfaire en même temps des contraintes cinématiques, comme l'évitement des obstacles et des butées articulaires, et des contraintes dynamiques, comme des accélérations, des forces ou des couples bornés. Le terme a été introduit par Donald, Xavier, Canny et Reif en 1993. Au lieu de chercher un chemin géométrique dans l'espace de configuration puis de le paramétrer en temps, un planificateur kinodynamique cherche une durée et une fonction de commande dont la trajectoire résultante, obtenue en intégrant la dynamique du système, part de l'état initial, reste dans l'espace libre et se termine dans une région but.

La recherche se fait donc dans l'espace d'état, qui inclut les vitesses en plus des positions et a souvent une dimension double de celle de l'espace de configuration. La principale difficulté est que deux états voisins ne peuvent en général pas être reliés par une droite : les relier exige de résoudre un problème aux limites en deux points sous la dynamique, ce qui est facile pour des systèmes simples comme les doubles intégrateurs ou les voitures de Dubins mais difficile en général. Les planificateurs fondés sur l'échantillonnage, comme le RRT kinodynamique introduit par LaValle et Kuffner, contournent ce problème en faisant croître un arbre vers l'avant : ils choisissent un nœud, appliquent des commandes échantillonnées ou choisies pendant un temps court et conservent les états obtenus. Des méthodes ultérieures comme SST ajoutent la quasi-optimalité asymptotique sans nécessiter de fonction de pilotage.

D'autres familles abordent le même problème autrement. Les planificateurs par recherche utilisent un treillis de primitives de mouvement précalculées, chacune dynamiquement réalisable. Les méthodes d'optimisation de trajectoire, dont la collocation directe et les méthodes de tir, traitent commandes et états comme variables de décision et résolvent un programme non linéaire sous contraintes, qui converge vite localement mais peut rester piégé dans des minima locaux. Les systèmes pratiques combinent souvent les deux : une étape d'échantillonnage ou de recherche trouve une trajectoire réalisable, puis l'optimisation l'affine. Lorsque la dynamique est incertaine, comme lorsqu'on pousse des objets, les planificateurs peuvent utiliser des modèles appris ou résiduels du système et planifier avec des commandes en boucle ouverte ensuite corrigées par rétroaction.

Pourquoi c'est important

Les robots rapides ou lourds, les voitures, les drones et les objets poussés ne peuvent pas suivre des chemins géométriques arbitraires : un chemin qui ignore la quantité de mouvement ou les limites des actionneurs peut être impossible à exécuter. La planification kinodynamique produit des trajectoires que le système peut réellement suivre, ce qui compte surtout quand le robot se déplace vite ou dispose d'une autorité de commande limitée.

Applications principales

Planification de trajectoires pour voitures et autres véhicules non holonomes
Planification de vols agressifs pour drones et aéronefs à voilure fixe
Manipulation non préhensile comme la planification de séquences de poussées
Mouvements de bras rapides près des limites de couple et de vitesse
Planification de mouvement pour robots à pattes et humanoïdes avec dynamique de contact
Manœuvres d'engins spatiaux et de véhicules sous-marins

En pratique

Un bras robotique doit pousser une boîte sur une table jusqu'à une région but, en évitant un obstacle, sans la saisir. L'équipe modélise le mouvement de la boîte en fonction de paramètres de poussée comme le point de contact, la direction et la durée, à l'aide d'un modèle de poussée analytique corrigé par un résidu appris. Un RRT kinodynamique échantillonne des actions de poussée à partir de l'état courant de la boîte, propage chacune à travers le modèle et ajoute les poses de boîte obtenues à l'arbre, en écartant les poussées qui entreraient en collision avec l'obstacle. Une fois qu'une branche atteint la région but, la séquence de poussées est exécutée, et la pose de la boîte est réobservée après chaque poussée afin que le planificateur puisse replanifier à partir de l'état réel si le modèle était faux.

Idées reçues

La planification kinodynamique est une planification géométrique suivie d'un paramétrage temporel — les chaînes découplées peuvent produire des chemins qu'aucune trajectoire dynamiquement réalisable ne peut suivre, alors que les planificateurs kinodynamiques tiennent compte de la dynamique pendant la recherche
N'importe quel planificateur par échantillonnage peut devenir kinodynamique en changeant de métrique de distance — relier deux états exige en général de résoudre un problème aux limites ou de propager des commandes vers l'avant, pas de tracer une droite
Un plan kinodynamique peut être exécuté en boucle ouverte — les erreurs de modèle et les perturbations s'accumulent, donc le plan est normalement suivi par un contrôleur par rétroaction ou replanifié

Qui devrait le savoir

Ingénieurs en planification de mouvement pour véhicules, drones et bras
Chercheurs en manipulation travaillant sur la poussée et d'autres tâches dynamiques
Ingénieurs en planification pour la conduite autonome
Étudiants en robotique qui étudient la planification au-delà de l'espace de configuration

Technologies associées

Kinodynamic RRT
Stable Sparse RRT (SST)
Planificateurs à treillis d'états (State Lattice Planners)
Open Motion Planning Library (OMPL)
Optimisation de trajectoire (Trajectory Optimization)

Termes associés

Projets associés

Drake: MIT robotics toolbox for model-based dynamics, optimization, and control system design
OMPL: Sampling-based motion planning library powering MoveIt and countless robotics applications
MoveIt 2: Motion planning framework for ROS 2 robot arms, with kinematics and collision checking
PyRoki: Modular Python toolkit for kinematic optimization across CPU, GPU, and TPU via JAX
mink: Python inverse kinematics library built on MuJoCo supporting 20+ robot platforms
Ruckig: Real-time jerk-constrained time-optimal trajectory generation for robots and machines

Vidéos

6.8210 Spring 2024 Lecture 18: Sampling-based (kinodynamic) motion planning: underactuated