Warm Start

Também chamado: warm starting
Categoria: Planning & manipulation › Trajectory optimisation
Tags: optimization, model-predictive-control, trajectory-optimization, numerical-methods, real-time

Inicializar um solver iterativo com um bom palpite, muitas vezes uma solução anterior ou relacionada, em vez de partir do zero, para reduzir o tempo de resolução e conduzi-lo a um ótimo local útil.

Definição

Uma inicialização a quente (warm start) inicializa um otimizador iterativo ou um solver numérico com informações de um problema relacionado, em vez de partir de um ponto inicial padrão ou arbitrário, o que se chama inicialização a frio. A informação pode ser as variáveis primais (as próprias variáveis de decisão, como uma trajetória), as variáveis duais ou multiplicadores de Lagrange, o conjunto ativo de restrições de desigualdade ou aproximações como uma hessiana quase-Newton. Como os problemas não lineares de robótica costumam ter muitos ótimos locais, o ponto de partida afeta não só a rapidez com que um solver converge, mas também qual solução ele encontra.

O controle preditivo por modelo é o uso mais comum. A cada ciclo de controle, o controlador resolve uma otimização sobre um horizonte que se sobrepõe quase inteiramente ao anterior, de modo que a solução anterior, deslocada um passo de tempo à frente e com o último passo estendido, já está perto do novo ótimo. A inicialização a quente feita dessa forma muitas vezes reduz o solver a poucas iterações por ciclo, e o esquema de iteração em tempo real de Diehl e colegas vai além, executando uma única iteração de programação quadrática sequencial por ciclo. Controladores baseados em amostragem, como o MPPI e o método da entropia cruzada, fazem inicialização a quente reutilizando a sequência de controle média anterior.

O quanto uma inicialização a quente ajuda depende do solver. Métodos de conjunto ativo, como o do qpOASES, e métodos de primeira ordem, como o solver ADMM OSQP, se beneficiam bastante, porque um palpite primal e dual próximo ou um conjunto ativo correto permite que terminem rapidamente. Métodos de pontos interiores são mais difíceis de inicializar a quente, porque precisam de iterados estritamente dentro da região viável e longe das fronteiras das restrições, onde as soluções anteriores normalmente estão. Na otimização de trajetória offline, uma inicialização a quente pode vir de um modelo mais simples, de uma discretização mais grosseira, de uma versão relaxada do problema, de uma biblioteca de soluções armazenadas ou de uma rede neural treinada para prever bons palpites iniciais. Motores de física, de forma semelhante, inicializam a quente os solvers iterativos de contato com os impulsos do passo anterior. Em aprendizado de máquina, o termo também é usado para iniciar o treinamento a partir de um modelo treinado anteriormente.

Por que importa

Controladores em tempo real baseados em otimização rodam a frequências de dezenas a milhares de hertz, e geralmente só atingem essas frequências porque cada resolução começa perto da resposta. No planejamento offline, uma boa inicialização a quente muitas vezes é a diferença entre um solver que converge para um movimento sensato e um que falha ou encontra um mínimo local ruim.

Principais aplicações

Controle preditivo por modelo em tempo real em robôs com pernas, drones e manipuladores
Otimização de trajetória com contato implícito e não linear
Sequências de programas quadráticos relacionados no controle de corpo inteiro
Solvers iterativos de contato em motores de física
Palpites iniciais aprendidos para planejamento de movimento rápido

Na prática

Um robô com pernas executa um MPC não linear a 100 Hz. Depois de cada resolução, o controlador armazena as trajetórias ótimas de estado e de entrada e os multiplicadores. No ciclo seguinte, ele as desloca um passo, copia o último passo para preencher o final do horizonte, substitui o primeiro estado pelo estado recém-medido e passa o resultado ao solver como palpite inicial. As resoluções típicas passam então a levar duas ou três iterações em vez de vinte. Os engenheiros também tratam os casos em que a inicialização a quente falha: depois de um empurrão forte ou de uma mudança de marcha, o palpite deslocado fica longe do novo ótimo, então o controlador recorre a uma trajetória nominal armazenada para essa marcha e permite mais iterações naquele ciclo.

Equívocos comuns

Uma inicialização a quente só acelera as coisas — em problemas não convexos ela também decide qual ótimo local é encontrado, então uma inicialização a quente ruim pode prender o solver em uma solução ruim
Qualquer solver se beneficia igualmente — métodos de conjunto ativo e de primeira ordem ganham mais; métodos de pontos interiores ganham menos e podem precisar de tratamento especial
Uma inicialização a quente só precisa das variáveis de decisão anteriores — fornecer também as variáveis duais ou o conjunto ativo muitas vezes importa tanto quanto para uma convergência rápida
A solução anterior é sempre um bom palpite — depois de grandes perturbações, mudanças de modo ou mudanças de objetivo ela pode estar longe do novo ótimo e precisa de uma alternativa de reserva

Quem deve saber

Engenheiros de controle preditivo por modelo
Desenvolvedores de otimização de trajetória
Engenheiros de locomoção com pernas e de controle de drones
Profissionais de otimização numérica em robótica

Tecnologias relacionadas

OSQP
qpOASES
IPOPT
acados
CasADi
Esquema de iteração em tempo real (Real-Time Iteration Scheme)

Termos relacionados

Projetos relacionados

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