PV-OSIMr: A Lowest Order Complexity Algorithm for Computing the Delassus Matrix

Autori: Ajay Suresha Sathya, Wilm Decré, Jan Swevers · IEEE Robotics and Automation Letters (RA-L) 2024

Licenze

Open access
Articolo: CC BY-SA 4.0

Tutto ciò che segue si basa sull'articolo completo secondo la sua licenza CC BY-SA 4.0; la figura è riportata citando gli autori.

In breve

Riordina i calcoli di PV-OSIM in modo che i vincoli propagati non superino mai sei dimensioni, ottenendo un calcolo della matrice di Delassus in O(n + m²), che gli autori dimostrano essere asintoticamente ottimale.

Perché è importante

I robot con molti contatti, come gli umanoidi con piedi e mani a più dita, hanno bisogno di questa matrice ad alta frequenza per la simulazione e il controllo, quindi meno operazioni significano solutori più veloci. Poiché costruire una matrice m × m e visitare tutti gli n giunti è inevitabile, gli autori sostengono che O(n + m²) sia l'ordine ottimale. L'algoritmo è stato implementato con la generazione di codice di CasADi e, secondo l'articolo, anche in C++ nella libreria Pinocchio.

Problema

La matrice di Delassus, o matrice di inerzia inversa nello spazio operativo, lega le forze di vincolo alle accelerazioni di vincolo ed è necessaria per la simulazione della dinamica vincolata e con contatti e per il controllo nello spazio operativo, dove è spesso il passo più costoso in MPC e RL. Calcolarla in modo ingenuo costa O(n³ + m²n). Il miglior algoritmo noto, EFPA, raggiunge O(n + md + m²), mentre il precedente PV-OSIM degli autori è O(n + m²d) e scala male quando molti vincoli devono essere propagati attraverso molti giunti.

Soluzione proposta

PV-OSIMr modifica la passata all'indietro di PV-OSIM in modo che, invece di propagare matrici dello spazio dei vincoli che crescono con il numero di vincoli, propaghi propagatori di forza estesi di dimensione fissa 6×6 e inerzie inverse spaziali tra link di ramificazione consecutivi (l'insieme N). Una passata in avanti limitata su N calcola le inerzie inverse, una passata all'indietro limitata calcola il propagatore dello spazio dei vincoli di ciascun end effector e ogni blocco della matrice di Delassus viene assemblato in tempo costante. Ne risulta una complessità O(n + m²).

Idee chiave

Quando un link sostiene più di sei dimensioni di vincolo, propagare grandezze spaziali 6D e ricavare in seguito i termini dello spazio dei vincoli costa meno che propagare direttamente i termini dello spazio dei vincoli.
Le grandezze costose vanno calcolate solo negli antenati comuni più vicini dei link vincolati, quindi le passate aggiuntive percorrono un insieme ridotto di link.
Una complessità asintotica inferiore non garantisce meno operazioni sui robot piccoli: EFPA è risultato più costoso di PV-OSIM e PV-OSIMr per quasi tutti i meccanismi provati, a causa della sua struttura a tre passate e delle trasformazioni di sistema di riferimento per ogni link.
LTL-OSIM, nonostante la complessità maggiore, ha battuto EFPA su una singola mano Shadow perché la ramificazione della mano crea una sparsità che esso sfrutta.

Risultati principali

Complessità: PV-OSIMr O(n + m²) contro PV-OSIM O(n + m²d), EFPA O(n + md + m²), KJR O(n + m²d), LTL-OSIM O(nd² + m²d + md²) e il calcolo ingenuo O(n³ + m²n).
Atlas in piedi con quattro contatti puntuali 3D per piede (12D per piede): PV-OSIM ha richiesto il 19,9 % di operazioni in più rispetto a PV-OSIMr; con un vincolo di saldatura (weld) 6D per piede i due algoritmi sono risultati identici.
Atlas con mani Shadow (vincolo 3D per polpastrello, 15D per mano): la sezione IV-D riporta fino a circa il 34 % di operazioni in meno rispetto a PV-OSIM, il successivo algoritmo più efficiente, mentre le conclusioni indicano un miglioramento fino al 24 % sugli esempi con Atlas.
Su un meccanismo di prova ramificato con vincoli di saldatura 6D all'estremità di ogni ramo, PV-OSIMr ha eguagliato PV-OSIM con un solo ramo ed è scalato in modo più graduale da due rami in su; EFPA ha infine superato PV-OSIM per meccanismi lunghi con dieci rami per lato.
In un caso PV-OSIM ha richiesto circa l'1,5 % di operazioni in meno: Atlas con vincoli di saldatura 6D su entrambe le mani e su entrambi i piedi, dove i vincoli attraversano solo tre giunti prima della base flottante.
Tutti i benchmark sono conteggi di operazioni dall'implementazione in CasADi, non tempi misurati in esecuzione.

Limiti

PV-OSIM può costare meno quando più di sei dimensioni di vincolo attraversano solo pochi (tre o meno) giunti a un solo DoF, perché i suoi aggiornamenti di rango 1 battono i due calcoli di rango 6 di PV-OSIMr.
Quando i vincoli si incontrano solo nella base flottante, o il meccanismo è una singola catena, PV-OSIMr non dà alcun vantaggio rispetto a PV-OSIM.
I risultati sono riportati come conteggi di operazioni anziché come tempi di esecuzione misurati.
L'algoritmo è presentato per alberi cinematici; la versione C++ in Pinocchio sarebbe stata rilasciata solo dopo l'accettazione.

Impatto sul settore

L'articolo ha vinto il RA-L 2025 Best Paper Award e ha 4 citazioni. Gli autori hanno rilasciato la loro implementazione in CasADi come codice sorgente su GitHub e dichiarano che una versione C++ è stata implementata nella libreria Pinocchio per essere rilasciata dopo l'accettazione.

Abstract

Presentiamo PV-OSIMr, un algoritmo efficiente per calcolare la matrice di Delassus (nota anche come matrice di inerzia inversa nello spazio operativo) per un albero cinematico, con la complessità computazionale di ordine più basso nota in letteratura. PV-OSIMr è ricavato ottimizzando i calcoli del solutore di Popov-Vereshchagin (PV) mediante la composizionalità dei propagatori di forza e di moto. Ha una complessità computazionale di O(n + m²), contro O(n + m²d) dell'algoritmo PV-OSIM originale e O(n+md+m²) dell'algoritmo del propagatore di forza esteso (EFPA), dove n è il numero di giunti, m è il numero di vincoli e d è la profondità dell'albero cinematico. Poiché il calcolo della matrice di Delassus richiede di costruire una matrice di dimensione m × m e deve considerare tutti gli n giunti almeno una volta, la complessità computazionale asintotica di PV-OSIMr è ottimale. Valutiamo inoltre il nostro algoritmo e riscontriamo che in pratica è spesso più efficiente di PV-OSIM ed EFPA.

Link

arXiv 2310.03676: https://arxiv.org/abs/2310.03676
DOI 10.1109/LRA.2024.3469829: https://doi.org/10.1109/LRA.2024.3469829
PDF: https://arxiv.org/pdf/2310.03676v1
Codice: https://github.com/AjSat/spatial_V2