Parameterized Differential Dynamic Programming

Auteurs: Alex Oshin, Matthew D. Houghton, Michael J. Acheson, Irene M. Gregory, Evangelos A. Theodorou · RSS 2022

Licences

• Accès libre
• Article: CC BY 4.0

Tout ce qui suit s'appuie sur l'article complet sous sa licence CC BY 4.0 ; sa figure est montrée en citant les auteurs.

En bref

PDDP ajoute à DDP des paramètres invariants dans le temps afin que les commandes et les paramètres reçoivent des mises à jour conjointes du second ordre ; il sert à l'identification de modèle en ligne dans la MPC et à la synchronisation des changements de mode de vol.

Pourquoi c'est important

Un seul solveur du second ordre peut identifier en ligne les paramètres d'un modèle tout en commandant le système, et peut choisir combien de temps un système hybride passe dans chaque mode. L'article rapporte, à la connaissance des auteurs, la première utilisation de l'optimisation des instants de commutation pour planifier des transitions entre régimes de vol, appliquée au concept VTOL Lift+Cruise de la NASA.

Problème

De nombreux problèmes de planification robotique comportent des paramètres invariants dans le temps inconnus ou réglables, comme la masse d'une charge utile ou le temps passé dans chaque mode d'un système hybride. Les approches antérieures fondées sur DDP mettaient à jour ces paramètres via la condition initiale de la trajectoire, ce qui décale toute la trajectoire nominale et nuit à la convergence. L'optimisation de trajectoire des systèmes hybrides a par ailleurs surtout visé des robots à pattes avec des modèles réduits, avec peu de travaux sur des aéronefs comme les véhicules de mobilité aérienne urbaine qui passent du vol stationnaire à la transition puis à la croisière.

Solution proposée

Les auteurs écrivent un objectif général de commande optimale dans lequel les paramètres interviennent à la fois dans la dynamique et dans le coût, et dérivent Parameterized DDP : la passe arrière développe la fonction de valeur en l'état et les paramètres, ce qui donne des gains de commande, une mise à jour en anticipation (feedforward) des paramètres et un terme de rétroaction qui maintient la stabilité des commandes lorsque les paramètres changent. Ils prouvent la convergence vers un point stationnaire depuis n'importe quelle initialisation sous une condition de recherche linéaire et une régularisation, et comparent la mise à jour des commandes et des paramètres de façon simultanée, alternée ou seulement après convergence des commandes (STO-DDP). Le même algorithme est appliqué à l'estimation à horizon glissant exécutée en parallèle de la MPC, et à l'optimisation des instants de commutation avec un nombre fixe de pas par mode, une intégration par sous-pas et un solveur de Newton projeté qui maintient les échelles de temps positives ou nulles.

Idées clés

• Traiter les paramètres explicitement dans la dynamique et le coût, plutôt qu'à travers l'état initial, donne des mises à jour conjointes du second ordre des commandes et des paramètres, quelle que soit la façon dont les paramètres sont définis.
• Alterner les mises à jour des commandes et des paramètres a permis d'échapper aux minima locaux mieux que de mettre à jour les deux à la fois ou d'attendre la convergence des commandes.
• Combiner l'estimation à horizon glissant avec la MPC permet au contrôleur de corriger en quelques pas un modèle très erroné, puis d'atteindre le but.
• Pour les problèmes d'instants de commutation, garder constant le nombre de pas de temps par mode et intégrer avec des sous-pas plus petits préserve les propriétés de convergence et évite les échecs numériques.

Principaux résultats

• Quadrirotor MHE+MPC : les estimations de masse et d'inertie sont passées de valeurs initiales de 1 kg et 1 kg·m² aux valeurs réelles de 0,468 kg et 4,856×10⁻³ / 8,801×10⁻³ kg·m² en 15 pas de MHE (moins de 0,2 s de temps d'exécution) ; le véhicule a ensuite atteint sa cible en 3 s au total.
• Quadrupède Ant (physique Brax, état de dimension 117) : les longueurs de pattes sont passées de 1,0 m et 2,0 m aux valeurs réelles de 0,443 m et 0,726 m en 4 pas de MHE.
• Cartpole : la masse du pendule a été correctement estimée (0,5 kg réels, à partir de 2 kg initialement) en 50 pas une fois que le pendule a commencé à bouger ; peu de progrès ont été faits pendant les 15 premiers pas.
• Tâche d'instants de commutation cartpole à cibles multiples, 1 000 initialisations aléatoires : le schéma alterné a atteint un coût en moyenne inférieur d'environ un demi-ordre de grandeur à celui du schéma simultané et de STO-DDP.
• NASA Lift+Cruise (500 initialisations) : un décollage vertical à temps optimal de 5,63 s suivi de 9,79 s pour atteindre la vitesse de croisière ; la manœuvre inverse a ralenti de la croisière au vol stationnaire sur moins de 500 ft en 6,87 s et a atterri en 4,87 s.
• Une implémentation MATLAB sur CPU uniquement a pris environ 1,5 s par itération sur la tâche Lift+Cruise sur un Intel i7-9850H, et moins de 1 s par itération sur les autres tâches.

Limites

• Les auteurs jugent le temps d'exécution assez lent pour de la MPC (environ 1,5 s par itération sur la tâche Lift+Cruise) et indiquent qu'une meilleure parallélisation est nécessaire pour un usage en temps réel.
• Le schéma simultané dépend fortement de la trajectoire de commande initiale (il a été démarré à chaud avec 5 itérations de DDP standard) et est tombé dans de mauvaises solutions sur les tâches quadrirotor et Lift+Cruise.
• Sur la tâche Lift+Cruise, le schéma alterné est resté derrière STO-DDP pendant les 50 premières itérations, tant que les commandes étaient encore mauvaises.
• La méthode suppose l'observabilité complète de l'état ainsi qu'une dynamique et des coûts deux fois différentiables par rapport aux états, aux commandes et aux paramètres ; la convergence repose sur une régularisation qui maintient les hessiennes définies positives.
• Toutes les expériences sont menées en simulation ; aucun essai sur matériel n'est rapporté.

Impact sur le domaine

L'article a été finaliste du RSS 2022 Best Student Paper Award. Il ne mentionne aucune publication de code ni de données.

Résumé

La programmation dynamique différentielle (Differential Dynamic Programming, DDP) est un algorithme efficace d'optimisation de trajectoire reposant sur des approximations du second ordre de la dynamique et de la fonction de coût d'un système, et a récemment été appliquée à l'optimisation de systèmes à paramètres invariants dans le temps. Les travaux antérieurs portent notamment sur l'estimation de paramètres de systèmes et sur l'identification de l'instant de commutation optimal entre les modes de systèmes dynamiques hybrides. Cet article généralise les travaux précédents en proposant un objectif général de commande optimale paramétré et en dérivant une version paramétrique de DDP, intitulée Parameterized Differential Dynamic Programming (PDDP). Une analyse rigoureuse de la convergence de l'algorithme est fournie, et il est montré que PDDP converge vers un minimum du coût quelle que soit l'initialisation. Les effets de variantes de l'optimisation destinées à échapper plus efficacement aux minima locaux sont analysés. Des expériences sont présentées dans lesquelles PDDP est appliqué à plusieurs systèmes robotiques pour résoudre simultanément des tâches de commande prédictive (MPC) et d'estimation à horizon glissant (MHE). Enfin, PDDP est utilisé pour déterminer le point de transition optimal entre les régimes de vol d'un véhicule complexe de la classe mobilité aérienne urbaine (UAM) présentant plusieurs phases de vol.

Liens

• arXiv 2204.03727: https://arxiv.org/abs/2204.03727
• PDF: https://arxiv.org/pdf/2204.03727v1