Warm Start

• Aussi appelé: warm starting
• Catégorie: Planning & manipulation › Trajectory optimisation
• Mots-clés: optimization, model-predictive-control, trajectory-optimization, numerical-methods, real-time

Initialisation d'un solveur itératif avec une bonne estimation, souvent une solution précédente ou apparentée, plutôt qu'à partir de zéro, pour réduire le temps de résolution et l'orienter vers un optimum local utile.

Définition

Un démarrage à chaud (warm start) initialise un algorithme d'optimisation itératif ou un solveur numérique avec des informations issues d'un problème apparenté, plutôt qu'à partir d'un point de départ par défaut ou arbitraire, ce qu'on appelle un démarrage à froid. Ces informations peuvent être les variables primales (les variables de décision elles-mêmes, comme une trajectoire), les variables duales ou multiplicateurs de Lagrange, l'ensemble actif des contraintes d'inégalité, ou des approximations comme un hessien quasi-Newton. Comme les problèmes non linéaires en robotique ont généralement de nombreux optima locaux, le point de départ influe non seulement sur la vitesse de convergence d'un solveur mais aussi sur la solution qu'il trouve.

La commande prédictive en est l'usage le plus courant. À chaque cycle de commande, le contrôleur résout une optimisation sur un horizon qui recouvre presque entièrement le précédent, si bien que la solution précédente, décalée d'un pas de temps vers l'avant et dont le dernier pas est prolongé, est déjà proche du nouvel optimum. Un démarrage à chaud de ce type ramène souvent le solveur à quelques itérations par cycle, et le schéma d'itération en temps réel (real-time iteration) de Diehl et de ses collègues va plus loin en n'effectuant qu'une seule itération de programmation quadratique séquentielle par cycle. Les contrôleurs par échantillonnage comme MPPI et la méthode de l'entropie croisée effectuent un démarrage à chaud en réutilisant la séquence de commande moyenne précédente.

L'apport d'un démarrage à chaud dépend du solveur. Les méthodes à ensemble actif, comme celle de qpOASES, et les méthodes du premier ordre comme le solveur ADMM OSQP en tirent un grand profit, car une estimation primale et duale proche ou un ensemble actif correct leur permet de terminer rapidement. Les méthodes de point intérieur sont plus difficiles à démarrer à chaud, car leurs itérés doivent se trouver strictement à l'intérieur du domaine admissible, loin des frontières des contraintes où se situent généralement les solutions précédentes. En optimisation de trajectoire hors ligne, un démarrage à chaud peut provenir d'un modèle plus simple, d'une discrétisation plus grossière, d'une version relâchée du problème, d'une bibliothèque de solutions stockées ou d'un réseau de neurones entraîné à prédire de bonnes estimations initiales. Les moteurs physiques démarrent de même à chaud les solveurs de contact itératifs avec les impulsions du pas précédent. En apprentissage automatique, le terme désigne aussi l'initialisation d'un entraînement à partir d'un modèle déjà entraîné.

Pourquoi c'est important

Les contrôleurs temps réel fondés sur l'optimisation tournent à des fréquences allant de quelques dizaines à plusieurs milliers de hertz, et ils ne tiennent généralement ces cadences que parce que chaque résolution part près de sa réponse. En planification hors ligne, un bon démarrage à chaud fait souvent la différence entre un solveur qui converge vers un mouvement sensé et un solveur qui échoue ou trouve un mauvais minimum local.

Applications principales

• Commande prédictive en temps réel sur des robots à pattes, des drones et des manipulateurs
• Optimisation de trajectoire à contact implicite et non linéaire
• Suites de programmes quadratiques apparentés en commande corps complet
• Solveurs de contact itératifs dans les moteurs physiques
• Estimations initiales apprises pour une planification de mouvement rapide

En pratique

Un robot à pattes exécute une MPC non linéaire à 100 Hz. Après chaque résolution, le contrôleur stocke les trajectoires optimales d'état et d'entrée ainsi que les multiplicateurs. Au cycle suivant, il les décale d'un pas, recopie le dernier pas pour remplir la fin de l'horizon, remplace le premier état par l'état nouvellement mesuré et transmet le résultat au solveur comme estimation initiale. Les résolutions typiques prennent alors deux ou trois itérations au lieu de vingt. Les ingénieurs traitent aussi les cas où le démarrage à chaud échoue : après une forte poussée ou un changement d'allure, l'estimation décalée est loin du nouvel optimum, donc le contrôleur se rabat sur une trajectoire nominale stockée pour cette allure et autorise davantage d'itérations pour ce cycle.

Idées reçues

• Un démarrage à chaud ne fait qu'accélérer — pour les problèmes non convexes, il décide aussi de l'optimum local trouvé, si bien qu'un mauvais démarrage à chaud peut enfermer le solveur dans une mauvaise solution
• Tous les solveurs en profitent autant — les méthodes à ensemble actif et du premier ordre y gagnent le plus ; les méthodes de point intérieur y gagnent moins et peuvent nécessiter un traitement particulier
• Un démarrage à chaud n'a besoin que des variables de décision précédentes — fournir aussi les variables duales ou l'ensemble actif compte souvent tout autant pour une convergence rapide
• La solution précédente est toujours une bonne estimation — après de fortes perturbations, des changements de mode ou des changements d'objectif, elle peut être loin du nouvel optimum et nécessite une solution de repli

Qui devrait le savoir

• Ingénieurs en commande prédictive
• Développeurs en optimisation de trajectoire
• Ingénieurs en locomotion à pattes et en commande de drones
• Praticiens de l'optimisation numérique en robotique

Technologies associées

• OSQP
• qpOASES
• IPOPT
• acados
• CasADi
• Schéma d'itération en temps réel (Real-Time Iteration Scheme)

Termes associés

• Model Predictive Control
• Direct Collocation
• Differential dynamic programming
• Trajectory Planning
• Model Predictive Path Integral
• Complementarity Constraint

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
• Drake: MIT robotics toolbox for model-based dynamics, optimization, and control system design
• Dora AI: Dataflow middleware for AI robotics applications, built in Rust
• GTSAM: Factor-graph optimization library powering many modern SLAM backends