Steering with Contingencies: Combinatorial Stabilization and Reach-Avoid Filters

Resumo Técnico: Navegação com Contingências Combinatórias

1. Problema e Motivação

Em aplicações de autonomia (como pouso de espaçonaves, navegação de veículos autônomos e exploração), é crucial que o sistema não apenas navegue em direção a um alvo ativo, mas também mantenha a capacidade de desviar para pelo menos $r$ de $p$ locais alternativos caso as condições mudem (ex.: detecção de perigos, esgotamento de bateria).

O desafio central é que formulações ingênuas desse requisito são computacionalmente intratáveis. Garantir que $r$ de $p$ alvos permaneçam alcançáveis simultaneamente exigiria verificar todas as combinações possíveis ($\binom{p}{r}$), levando a uma "explosão combinatória" que impede a implementação em tempo real. O objetivo do artigo é formalizar esse requisito combinatório e desenvolver filtros de controle tratáveis que garantam estabilidade e segurança sem essa complexidade exponencial.

2. Metodologia

Os autores propõem uma estrutura unificada baseada em duas abordagens principais, ambas utilizando Programação Quadrática (QP) com apenas $p+1$ restrições, evitando a explosão combinatória:

A. Estabilização Combinatória (Baseada em CLF - Funções de Lyapunov de Controle)

• Objetivo: Estabilizar assintoticamente um equilíbrio selecionado ($x^*_{j^\dagger}$) enquanto garante que a trajetória permaneça dentro da região de atração de pelo menos $r$ de $p$ equilíbrios candidatos.
• Abordagem:
  • Utilizam subníveis de Funções de Lyapunov de Controle (CLF) locais para definir regiões de atração seguras para cada alvo.
  • Convertem essas regiões em Funções de Barreira de Controle (CBF).
  • Aplicam o framework de CBF Combinatória (de trabalhos anteriores [8], [9]), que utiliza uma função "pivot" (estatística de ordem) para definir o conjunto seguro como a interseção onde pelo menos $r$ funções de barreira são não-negativas.
  • Introduzem uma condição de relaxamento (usando a função ReLU e uma variável auxiliar $\omega$) para garantir a viabilidade do QP mesmo fora da região de atração local do alvo selecionado, permitindo que o controlador seja bem definido em todo o conjunto combinatório.

B. Alvo Combinatório (Baseada em HJR - Reachability de Hamilton-Jacobi)

• Objetivo: Resolver problemas de horizonte finito onde a região de segurança encolhe com o tempo (devido ao consumo de recursos como combustível ou bateria). O sistema deve alcançar um alvo dentro de um horizonte $T$ mantendo $r$ alternativas viáveis.
• Abordagem:
  • Utilizam Conjuntos de Reach-Avoid (RA) Reversos derivados de funções de valor de Hamilton-Jacobi (HJR).
  • Substituem as CLFs por funções de valor de HJR ($V_j$), que codificam a viabilidade de alcançar um alvo evitando obstáculos em um horizonte de tempo específico.
  • Definem um conjunto combinatório de Reach-Avoid onde pelo menos $r$ funções de valor permanecem não-negativas.
  • O controlador é sintetizado via QP dinâmico, tratando o horizonte de tempo como um estado interno, garantindo que a trajetória permaneça dentro do conjunto combinatório até o objetivo final.

Estrutura do Controlador:
Em ambas as formulações, o controlador é obtido resolvendo um QP que minimiza o desvio de um controlador nominal, sujeito a:

1. Uma restrição de estabilidade (CLF ou condição de HJR) para o alvo selecionado.
2. $p$ restrições de barreira combinatória (uma para cada candidato), que garantem a invariância do conjunto onde $r$ alvos são acessíveis.
   Isso resulta em apenas $p+1$ restrições lineares, independentemente do valor de $r$.

3. Contribuições Chave

1. Formalização do Requisito Combinatório: Definição rigorosa de "Estabilização Combinatória" e "Alvo Combinatório" ($r$-out-of-$p$), garantindo que a perda de qualquer opção não comprometa a missão.
2. Escalabilidade Computacional: Demonstração de que requisitos lógicos complexos ($r$-out-of-$p$) podem ser impostos com apenas $p+1$ restrições em um QP, evitando a explosão combinatória típica de métodos de programação inteira mista (MIP).
3. Filtros de Controle em Tempo Real: Desenvolvimento de filtros que garantem:
   • Estabilidade assintótica do alvo selecionado.
   • Invariância forward do conjunto combinatório de segurança.
   • Continuidade do controlador (sob condições de Slater).
4. Flexibilidade de Comutação: O framework permite a comutação segura e em tempo real entre alvos. Se o alvo atual se tornar inviável, o sistema pode alternar para qualquer um dos $r$ alvos restantes que ainda estão dentro do conjunto combinatório, sem violar restrições de segurança.

4. Resultados e Simulações

O framework foi validado em dois exemplos distintos:

• Exemplo 1: Sistema Linear (Baseado em CLF)

  • Um sistema com 3 alvos e 3 obstáculos.
  • Resultado: O controlador filtrado manteve o estado dentro das regiões de atração de pelo menos 2 alvos ($r=2$) enquanto navegava para o alvo 1. Ao mudar o alvo para o 2 em $t=0.5s$, a comutação foi segura. A trajetória não filtrada colidiu com obstáculos, enquanto a filtrada evitou-os e permitiu a mudança de alvo.
  • Demonstrou a capacidade de ajustar dinamicamente o parâmetro $r$ (de 2 para 3) durante a operação.

• Exemplo 2: Pouso de Avião (Baseado em HJR)

  • Um modelo simplificado de aeronave navegando entre edifícios com 6 pistas de pouso possíveis.
  • Resultado: O filtro garantiu que, mesmo com o horizonte de tempo encolhendo (simulando consumo de combustível), o avião mantivesse acesso a $r$ pistas alternativas.
  • Em um cenário onde o alvo original se tornou inviável devido à redução do horizonte, o filtro comutou automaticamente para uma pista de contingência (rosa), garantindo pouso seguro.
  • As simulações confirmaram que as funções de valor de estabilidade e barreira permaneceram não-negativas, certificando a garantia de segurança.

5. Significado e Impacto

Este trabalho preenche uma lacuna crítica na teoria de controle de sistemas autônomos: a capacidade de planejar trajetórias que são robustas a falhas e mudanças de ambiente sem sacrificar a eficiência computacional.

• Segurança Garantida: Oferece garantias matemáticas de que o sistema nunca ficará "preso" em uma situação onde nenhuma opção de escape ou alvo alternativo seja viável.
• Aplicabilidade Prática: Ao reduzir o problema combinatório para um QP com $p+1$ restrições, torna-se viável a implementação em sistemas embarcados com recursos limitados, permitindo tomada de decisão reativa em tempo real.
• Generalidade: A abordagem é aplicável tanto a problemas de estabilização infinita (CLF) quanto a problemas de horizonte finito com recursos limitados (HJR), cobrindo uma ampla gama de cenários de autonomia, desde drones até veículos espaciais.

Em resumo, o artigo fornece uma ferramenta teórica e prática essencial para a próxima geração de sistemas autônomos que devem operar em ambientes dinâmicos e incertos, onde a capacidade de "ter um plano B, C, D..." é tão importante quanto executar o plano A.