Resumo Técnico: TinySDP

Declaração do Problema

O planejamento de movimento seguro e o controle em ambientes dinâmicos permanecem um desafio significativo para a robótica, particularmente em sistemas embarcados com recursos limitados. Embora o Controle Preditivo Baseado em Modelo (MPC) seja eficaz para o raciocínio sobre dinâmicas do sistema e restrições, a imposição de garantias formais de segurança para a evasão de obstáculos não convexos é difícil em tempo real. Abordagens existentes frequentemente dependem de superaproximações conservadoras (por exemplo, restrições de distância linearizadas) ou convexificações locais que falham em capturar estruturas geométricas globais. Esses métodos são propensos a falhar em cenários envolvendo passagens estreitas, becos sem saída ou obstáculos dinâmicos, exigindo frequentemente um ajuste extensivo de margens de segurança que inflam a pegada efetiva do robô. Por outro lado, embora a Programação Semidefinida (SDP) ofereça uma estrutura fundamentada para convexificar restrições geométricas não convexas via elevação, solvers de SDP de propósito geral são computacionalmente caros e intensivos em memória, tornando-os inadequados para controle de horizonte recuado em tempo real em microcontroladores.

Metodologia

Os autores introduzem o TinySDP, o primeiro solver de programação semidefinida projetado especificamente para sistemas embarcados para permitir evasão de obstáculos em tempo real e certificável. A abordagem integra três componentes principais:

1. Elevação e Relaxamento Estruturados

O TinySDP formula o problema de MPC usando um relaxamento semidefinido, convexo e por estágio, de restrições de evasão de obstáculos não convexas, quadráticas e baseadas em discos.

• Elevação: O método eleva o estado geométrico (por exemplo, posição planar $p_k$) para um cone de semidefinição positiva (PSD) de dimensão superior. Especificamente, ele introduz variáveis auxiliares para os produtos externos de estados e entradas (por exemplo, $X_k = x_k x_k^\top$).
• Linearização: Essa elevação transforma restrições de obstáculos quadráticas (por exemplo, $\|p_k - c_j\|^2 \geq r_j^2$) em desigualdades afins lineares nas variáveis elevadas, mantendo as dinâmicas lineares do sistema no espaço elevado.
• Relaxamento: A restrição exata de posto 1 na matriz de momentos é relaxada para uma restrição PSD ($M_k \succeq 0$), tornando o problema convexo.

2. Solver ADMM Baseado em Riccati

Para resolver o problema convexo resultante de forma eficiente em hardware embarcado, os autores estendem o framework TinyMPC (que utiliza recursões de Riccati em cache) para lidar com restrições PSD por estágio.

• Algoritmo: O solver utiliza o Método de Direção Alternada de Multiplicadores (ADMM).
• Atualização Primal: O subproblema primal é um problema de Regulador Linear Quadrático (LQR) elevado. Crucialmente, as dinâmicas do sistema permanecem lineares nas variáveis elevadas, permitindo o uso de varreduras eficientes de Riccati para trás e para frente com quantidades de estado estacionário pré-computadas e em cache.
• Atualizações de Folga e Duais: As restrições PSD são tratadas por meio de um passo de projeção. Em cada iteração do ADMM, o solver computa a projeção euclidiana de uma matriz sobre o cone PSD (via decomposição de autovalores e limitação de autovalores) e atualiza as variáveis duais. Essa projeção é realizada por estágio, preservando a estrutura computacional necessária para execução em tempo real.

3. Certificado de Segurança de Posto 1 A Posteriori

Para abordar a folga introduzida pelo relaxamento SDP, o artigo propõe um certificado simples e computacionalmente barato avaliado a cada passo de tempo.

• Lacuna de Rastreamento (Trace Gap): O certificado mede a "lacuna de rastreamento" ($\Delta_k$), definida como a diferença entre o rastreamento do bloco de posição elevado e o quadrado da norma da posição física ($\text{trace}(X^{(p)}_k) - \|p_k\|^2$).
• Lógica de Certificação: Se a margem elevada (o valor da restrição de obstáculo linearizada) for não negativa e a lacuna de rastreamento for suficientemente pequena em relação a essa margem, a solução é certificada como livre de colisões.
• Fallback: Se o certificado falhar, o sistema descarta a entrada de controle planejada e executa uma política de fallback reativa (parar e pairar), garantindo que comandos não certificados nunca sejam aplicados ao robô físico.

Contribuições Principais

1. Solver TinySDP: O desenvolvimento do primeiro solver de SDP embarcado que aproveita estruturas de Riccati em cache para resolver problemas de MPC relaxados para PSD em tempo real.
2. Integração de Relaxamento e Certificação: Um framework que acopla relaxamento convexo eficiente com um certificado de segurança geométrico explícito e a posteriori, fechando a lacuna entre otimalidade teórica e garantias de segurança práticas.
3. Validação em Hardware: Implantação bem-sucedida em um quadrotor Crazyflie 2.1 (microcontrolador STM32F405) operando a taxas de controle de 25 Hz, demonstrando que restrições semidefinidas podem ser impostas em plataformas com recursos limitados.

Resultados Experimentais

Os autores avaliaram o TinySDP contra bases de comparação de última geração (TinyMPC-LIN, TinyMPC-HOCBF e RPCBF) em simulação e hardware do mundo real.

• Beco Sem Saída em Forma de U Estático: Em cenários projetados para causar impasse para métodos locais, o TinySDP alcançou navegação livre de colisões com comprimentos de trajetória 31–73% mais curtos do que a melhor base de comparação (RPCBF). Os métodos de base ou colidiram (com margem de segurança zero) ou exigiram margens de segurança impraticavelmente grandes (até 30 vezes o tamanho do drone) para ter sucesso, o que inflou a pegada de colisão e impediu a chegada ao objetivo.
• Evasão de Obstáculos Dinâmicos: Em cenários dinâmicos com obstáculos em movimento fechando passagens estreitas, o TinySDP antecipou e evitou colisões com sucesso. Ele produziu trajetórias 30% mais curtas do que o RPCBF e manteve maior precisão (mais próximo do objetivo) do que as bases de comparação.
• Extensão 3D: Os autores demonstraram que o framework de elevação se estende naturalmente a obstáculos esféricos 3D, navegando com sucesso em cenários dinâmicos 3D em simulação.
• Implantação no Mundo Real: No Crazyflie, o solver executou 5 iterações do ADMM em ~14,8 ms (deixando uma margem de ~25 ms em um período de controle de 40 ms). A pegada de memória foi modesta (aprox. 1,47 KB de sobrecarga de memória estática para lógica PSD). Em cinco ensaios independentes envolvendo um braço robótico em movimento, o certificado de segurança online permaneceu válido a cada passo de tempo, confirmando a preservação da geometria de posto 1 sob perturbações do mundo real.

Significado e Alegações

O artigo afirma que o TinySDP demonstra que restrições semidefinidas não são inerentemente incompatíveis com controle de horizonte recuado em tempo real em sistemas embarcados. Ao explorar estruturas específicas do problema (dinâmicas de Riccati) e separar a otimização da certificação, os autores mostram que é possível ir além de aproximações lineares conservadoras sem sacrificar a tratabilidade computacional.

O trabalho fecha a lacuna entre planejamento semidefinido offline e implantação prática embarcada. Ele sugere que modelos de segurança convexos mais ricos podem ser integrados a controladores de alta taxa se o design do solver respeitar a estrutura subjacente do MPC. Os autores posicionam isso como um passo rumo à habilitação de robótica de borda "ágil" que pode navegar em ambientes complexos e não convexos com garantias formais de segurança, em vez de depender de ajuste heurístico ou métodos baseados em aprendizado que podem ser inviáveis para implantação em pequenas plataformas embarcadas.

Os autores permanecem modestos quanto às limitações, observando que o certificado fornece uma verificação por passo de tempo em vez de uma garantia formal de viabilidade recursiva em malha fechada, e que estender a capacidade completa 3D para microcontroladores permanece um desafio devido ao aumento dos custos computacionais para projeções PSD maiores.