Kinodynamic Planning

Detto anche: kinodynamic motion planning
Categoria: Planning & manipulation › Motion planning
Tag: motion-planning, dynamics, sampling-based-planning, trajectory-optimization, state-space

Pianificazione del movimento che rispetta sia i vincoli geometrici, come le collisioni, sia la dinamica del sistema, trovando gli ingressi di controllo nel tempo invece di un semplice percorso privo di collisioni.

Definizione

Pianificazione cinodinamica (kinodynamic planning) è la pianificazione del movimento in cui la soluzione deve soddisfare contemporaneamente vincoli cinematici, come evitare gli ostacoli e rispettare i limiti dei giunti, e vincoli dinamici, come accelerazioni, forze o coppie limitate. Il termine è stato introdotto da Donald, Xavier, Canny e Reif nel 1993. Invece di cercare un percorso geometrico nello spazio delle configurazioni e assegnargli i tempi in seguito, un pianificatore cinodinamico cerca una durata e una funzione di controllo la cui traiettoria risultante, ottenuta integrando la dinamica del sistema, parta dallo stato iniziale, resti nello spazio libero e termini in una regione obiettivo.

La ricerca avviene quindi nello spazio degli stati, che comprende velocità oltre alle posizioni e spesso ha dimensione doppia rispetto allo spazio delle configurazioni. La difficoltà principale è che in generale due stati vicini non possono essere uniti da una linea retta: collegarli richiede di risolvere un problema ai valori al contorno a due punti sotto la dinamica, il che è facile per sistemi semplici come i doppi integratori o le auto di Dubins ma difficile in generale. I pianificatori basati sul campionamento, come l'RRT cinodinamico introdotto da LaValle e Kuffner, aggirano il problema facendo crescere un albero in avanti: scelgono un nodo, applicano controlli campionati o scelti per un breve intervallo di tempo e conservano gli stati risultanti. Metodi successivi come SST aggiungono la quasi-ottimalità asintotica senza bisogno di una steering function.

Altre famiglie affrontano lo stesso problema in modo diverso. I pianificatori basati sulla ricerca usano un reticolo di primitive di movimento precalcolate, ognuna dinamicamente fattibile. I metodi di ottimizzazione di traiettorie, tra cui la collocazione diretta e lo shooting, trattano controlli e stati come variabili decisionali e risolvono un programma non lineare vincolato, che converge rapidamente a livello locale ma può restare intrappolato in minimi locali. I sistemi pratici spesso combinano i due: una fase di campionamento o di ricerca trova una traiettoria fattibile e l'ottimizzazione poi la raffina. Quando la dinamica è incerta, come quando si spingono oggetti, i pianificatori possono usare modelli appresi o residui del sistema e pianificare con controlli ad anello aperto che vengono poi corretti dalla retroazione.

Perché è importante

Robot veloci o pesanti, auto, droni e oggetti spinti non possono seguire percorsi geometrici arbitrari: un percorso che ignora la quantità di moto o i limiti degli attuatori può essere impossibile da eseguire. La pianificazione cinodinamica produce traiettorie che il sistema può effettivamente seguire, il che conta soprattutto quando il robot si muove velocemente o ha un'autorità di controllo limitata.

Applicazioni principali

Pianificazione di traiettorie per auto e altri veicoli anolonomi
Pianificazione di voli aggressivi per droni e velivoli ad ala fissa
Manipolazione non prensile, come la pianificazione di sequenze di spinte
Movimenti rapidi del braccio vicino ai limiti di coppia e di velocità
Pianificazione del movimento di robot con gambe e umanoidi con dinamica di contatto
Manovre di veicoli spaziali e subacquei

In pratica

Un braccio robotico deve spingere una scatola su un tavolo fino a una regione obiettivo, evitando un ostacolo, senza afferrarla. Il team modella il moto della scatola in funzione di parametri della spinta come punto di contatto, direzione e durata, usando un modello analitico di spinta corretto da un residuo appreso. Un RRT cinodinamico campiona azioni di spinta a partire dallo stato attuale della scatola, propaga ciascuna attraverso il modello e aggiunge all'albero le pose risultanti della scatola, scartando le spinte che colliderebbero con l'ostacolo. Quando un ramo raggiunge la regione obiettivo, la sequenza di spinte viene eseguita e la posa della scatola viene osservata di nuovo dopo ogni spinta, così che il pianificatore possa ripianificare dallo stato reale se il modello era sbagliato.

Idee sbagliate comuni

La pianificazione cinodinamica è pianificazione geometrica seguita da parametrizzazione temporale — le pipeline disaccoppiate possono produrre percorsi che nessuna traiettoria dinamicamente fattibile può seguire, mentre i pianificatori cinodinamici considerano la dinamica durante la ricerca
Qualsiasi pianificatore basato sul campionamento può diventare cinodinamico cambiando la metrica di distanza — collegare due stati richiede in generale di risolvere un problema ai valori al contorno o di propagare i controlli in avanti, non di tracciare una linea retta
Un piano cinodinamico può essere eseguito ad anello aperto — errori di modello e disturbi si accumulano, quindi il piano viene normalmente inseguito con un controllore in retroazione o ripianificato

Chi dovrebbe saperlo

Ingegneri di pianificazione del movimento per veicoli, droni e bracci
Ricercatori di manipolazione che lavorano su spinte e altri compiti dinamici
Ingegneri di pianificazione per la guida autonoma
Studenti di robotica che studiano la pianificazione oltre lo spazio delle configurazioni

Tecnologie correlate

RRT cinodinamico (Kinodynamic RRT)
Stable Sparse RRT (SST)
Pianificatori a reticolo di stati (State Lattice Planners)
Open Motion Planning Library (OMPL)
Ottimizzazione di traiettorie (Trajectory Optimization)

Termini correlati

Progetti correlati

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

Video

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