SCRAMPPI: Efficient Contingency Planning for Mobile Robot Navigation via Hamilton-Jacobi Reachability

Título: SCRAMPPI: Planejamento de Contingência Eficiente para Navegação de Robôs Móveis via Alcançabilidade Hamilton-Jacobi

1. O Problema

Robôs autônomos frequentemente operam em missões onde devem otimizar um comportamento nominal (ex: chegar a um objetivo) enquanto minimizam custos. No entanto, em cenários dinâmicos ou adversários, o robô pode precisar abortar a missão e recuar para um conjunto seguro (ex: estação de carga, zona de pouso ou área oculta de um adversário) devido a falhas de sensor, bateria baixa ou comandos de abortagem.

O desafio central é o Planejamento de Contingência com Restrições de Liveness:

• Diferente da simples evasão de obstáculos (parar ou desviar), o robô deve garantir que, em qualquer ponto de sua trajetória nominal, exista um caminho dinamicamente viável e livre de obstáculos para um conjunto seguro dentro de um horizonte de tempo finito.
• Métodos existentes baseados em amostragem (como Contingency-MPPI) verificam essa viabilidade através de simulações internas. Isso cria uma assimetria fundamental: encontrar um plano de backup prova a viabilidade, mas não encontrar um plano não prova a inviabilidade (pode ser apenas falta de amostras). Isso resulta em garantias probabilísticas, não rigorosas.

2. Metodologia: SCRAMPPI

Os autores propõem o SCRAMPPI (Safe Contingency Reach-Avoid MPPI), um framework que integra a análise de alcançabilidade Hamilton-Jacobi (HJ) ao controle preditivo baseado em amostragem (MPPI).

A. Formulação como Problema de Alcançabilidade (Reach-Avoid)

O requisito de contingência é formalizado como um problema de Reach-Avoid (Alcançar e Evitar):

• Objetivo: Alcançar o conjunto seguro $S$.
• Restrição: Evitar o conjunto de obstáculos $O$ durante o horizonte de tempo $T_c$.
• Solução Exata: Utiliza-se a Função de Valor HJ ($V(x)$). O subconjunto de nível zero ($V(x) \leq 0$) caracteriza matematicamente o conjunto exato de estados a partir dos quais é possível alcançar $S$ evitando $O$.
  • Se $V(x) \leq 0$, um plano de contingência existe (garantia formal).
  • O gradiente $\nabla V(x)$ fornece o controlador ótimo para executar esse plano de fuga.

B. Arquitetura do Algoritmo

O sistema opera em dois modos:

1. Modo Nominal: O robô planeja trajetórias para o objetivo principal usando MPPI, mas com uma restrição estrita: o robô deve permanecer dentro do conjunto viável de contingência ($C = \{x : V(x) \leq 0\}$).
2. Modo de Contingência: Se um sinal externo ou interno dispara uma contingência, o robô abandona o MPPI e segue o controlador ótimo derivado de HJ ($u^*$) para alcançar o conjunto seguro.

C. Integração com MPPI e Resampling (RBR)

Para integrar essa restrição dura no MPPI sem desperdiçar amostras:

• Critério de Sobrevivência: Em vez de penalizar trajetórias que saem da zona segura, o algoritmo utiliza a função de valor HJ como critério de "sobrevivência".
• Resampling Baseado em Rollouts (RBR): Trajetórias que violam a condição $V(x) \leq 0$ são "reconectadas" (rewired) ao estado de uma trajetória sobrevivente segura e seus controles futuros são perturbados.
• Resampling Local por Grupo: Para evitar o colapso de modos (onde todas as amostras convergem para um único caminho), o espaço de amostragem é dividido em grupos baseados em classes homotópicas distintas. O resampling ocorre apenas dentro de cada grupo, preservando a diversidade de rotas.

D. Computação Online

• A função de valor $V(x)$ é computada em tempo real sobre uma grade de ocupação do ambiente usando um solver acelerado por GPU (biblioteca hj_reachability com JAX).
• A função é reavaliada apenas quando novos obstáculos são detectados ou em intervalos fixos, tornando o custo computacional gerenciável (aprox. 43 ms para uma grade 400x160x60).

3. Contribuições Principais

1. Formalização Rigorosa: Transforma o problema de planejamento de contingência em um problema de Reach-Avoid, fornecendo um certificado formal de viabilidade (baseado em HJ) em vez de uma verificação probabilística por amostragem.
2. Algoritmo Híbrido Eficiente: Propõe o SCRAMPPI, que usa a função de valor HJ como critério de sobrevivência em um MPPI com resampling multimodal, garantindo que o robô nunca entre em um estado sem saída.
3. Validação Experimental: Demonstra o funcionamento em tempo real tanto em simulação (robô unicycle) quanto em hardware (AgileX Scout Mini) em cenários de evasão adversarial, com reavaliação online da função de valor conforme o ambiente é revelado.

4. Resultados Experimentais

Os testes comparativos foram realizados em 100 ambientes aleatórios contra MPPI padrão e Contingency-MPPI (C-MPPI) com 100 e 1000 amostras internas.

• Taxa de Sucesso e Segurança:
  • SCRAMPPI: 100% de sucesso e 0% de estados inseguros. Garante sempre um plano de fuga.
  • C-MPPI: Mesmo com 1000 amostras internas, a taxa de contingências válidas foi de 98,5% e houve estados inseguros (falha em encontrar um plano quando ele existia, devido à limitação de amostragem).
• Eficiência de Amostragem (ESS): O SCRAMPPI obteve a maior eficiência de amostragem (0.446), superando o C-MPPI e o SCRAMPPI sem resampling. O método de resampling recicla amostras que violariam a restrição, em vez de descartá-las.
• Desempenho Computacional:
  • Tempo: O SCRAMPPI opera em 44 ms por passo (incluindo a recomputação da função HJ), comparável ao MPPI padrão (2.6 ms) e muito mais rápido que o C-MPPI-1000 (~126 ms).
  • Memória (VRAM): O SCRAMPPI usa apenas 33.6 MB, enquanto o C-MPPI-1000 usa 1159.7 MB (redução de 34x). O uso de memória do C-MPPI escala com o horizonte de planejamento e contingência, enquanto o do SCRAMPPI é fixo (tamanho da grade).
• Hardware: No robô físico, o sistema rodou a 15 Hz, planejando trajetórias que mantinham a viabilidade de fuga, mesmo em rotas mais longas, e executou com sucesso manobras de contingência quando ativadas manualmente.

5. Significado e Conclusão

O SCRAMPPI representa um avanço significativo na navegação robótica segura, eliminando a ambiguidade dos métodos baseados em amostragem para garantias de contingência.

• Inovação Chave: A substituição de verificações de "tentativa e erro" (amostragem) por uma certificação matemática exata (HJ Reachability) integrada a um planejador estocástico.
• Impacto: Permite que robôs operem em ambientes parcialmente desconhecidos e adversários com a garantia de que nunca ficarão "encurralados" sem uma saída segura.
• Limitações Futuras: O método atual depende de solvers de grade, o que limita a dimensionalidade do estado (atualmente 3-4 estados contínuos). Trabalhos futuros podem explorar aproximações aprendidas (Deep Learning) para sistemas de alta dimensão, embora isso possa comprometer a garantia formal exata.

Em resumo, o SCRAMPPI oferece um equilíbrio ideal entre a flexibilidade de planejamento estocástico e a rigidez de garantias de segurança formais, sendo capaz de operar em tempo real em hardware.