Provably Safe Motion Planning Under Unknown Disturbances

Enunciado do Problema
Este artigo aborda o desafio do planejamento de movimento para sistemas robóticos sujeitos a perturbações aleatórias com distribuições desconhecidas. Planejadores tradicionais baseados em amostragem frequentemente assumem modelos determinísticos ou dependem de fortes suposições distribucionais (por exemplo, ruído gaussiano) e modelos de perturbação limitados. Essas abordagens resultam frequentemente em planos excessivamente conservadores que falham em ambientes congestionados ou exigem conhecimento irrealista da distribuição de perturbação. Os autores formulam o problema como a geração de um plano de movimento para sistemas lineares (ou linearizáveis por feedback) que satisfaça restrições de chance para evitar colisões e alcançar o objetivo com alta confiança, apesar de as distribuições do estado inicial e do ruído do processo serem desconhecidas. O sistema deve operar dentro de restrições de estado e controle em espaços de trabalho contendo obstáculos de formato arbitrário.

Metodologia
A abordagem proposta, denominada WDR-X (Wasserstein Distributionally Robust-X), é um framework de planejamento de movimento baseado em amostragem que integra quantificação de incerteza orientada a dados com busca baseada em árvores. A metodologia procede em duas fases principais:

1. Construção do Tubo de Ambiguidade (Offline):
   Em vez de assumir uma distribuição de ruído específica, o algoritmo aprende um tubo de ambiguidade de Wasserstein a partir de um conjunto de $N$ amostras de trajetória i.i.d. Este tubo é uma sequência de conjuntos de ambiguidade (esferas de Wasserstein) que, com um nível de confiança definido pelo usuário, contém a verdadeira distribuição de estado em cada passo de tempo.

   • Dinâmica do Erro: Os autores desacoplam o problema de planejamento da propagação de incerteza analisando a dinâmica do erro relativa a uma trajetória de referência. Eles provam que o conjunto de ambiguidade para o estado pode ser derivado do conjunto de ambiguidade do erro e do estado de referência.
   • Horizonte Infinito: Ao contrário de métodos anteriores onde os limites de ambiguidade crescem ilimitadamente ao longo do tempo, esta abordagem constrói um tubo de comprimento temporal infinito com confiança finita. Isso é alcançado aprendendo conjuntos de ambiguidade orientados a dados em passos de tempo específicos e derivando os conjuntos para passos intermediários usando a dinâmica do sistema, resultando em um perfil de raio "serra" que permanece limitado.
   • Decomposição de Dimensão Inferior: Para abordar a maldição da dimensionalidade, o framework aproveita tubos de ambiguidade de dimensão inferior. Ao projetar a distribuição de estado em subespaços relevantes para restrições específicas (por exemplo, posição no espaço de trabalho para obstáculos, esforço de controle para limites), o método reduz significativamente a complexidade de amostragem e o custo computacional, mantendo garantias de segurança.

2. Planejamento Probabilisticamente Completo (Online):
   O planejador expande uma árvore baseada em amostragem (por exemplo, RRT) sobre as trajetórias de referência nominais (determinísticas).

   • Verificação de Validade: Em cada nó, o algoritmo verifica se o estado satisfaz as restrições de chance. Isso é feito avaliando a probabilidade de colisão no pior caso sobre o conjunto de ambiguidade aprendido.
   • Verificadores Eficientes: O artigo introduz três estratégias de verificação de validade:
     • Verificador Exato: Um algoritmo sem otimização baseado no transporte de massa probabilística que computa a probabilidade exata de colisão no pior caso para distribuições discretas.
     • Verificador Preguiçoso (Lazy): Um método mais rápido e mais conservador que utiliza tubos de confiança (esferas) pré-computados, evitando cálculos detalhados de transporte de massa.
     • Verificador Baseado em Bandit: Uma abordagem híbrida que seleciona adaptativamente entre os verificadores exato e preguiçoso usando um framework de bandit de múltiplos braços. Isso equilibra eficiência e conservadorismo, particularmente em ambientes complexos como passagens estreitas.

Contribuições Principais
O artigo faz as seguintes contribuições específicas:

• Algoritmo: Um algoritmo de planejamento de movimento baseado em amostragem para sistemas lineares com perturbações aditivas desconhecidas que utiliza dados de observação de trajetória.
• Garantias Teóricas: Provas de correção e completude probabilística para o planejador sob suposições relaxadas regarding distribuições de perturbação.
• Propagação de Ambiguidade: Novos resultados teóricos sobre a propagação de ambiguidade distribucional, especificamente mostrando que a propagação de ambiguidade se desacopla do planejamento para sistemas lineares, permitindo um único tubo aprendido offline.
• Limites Mais Apertados: Uma caracterização mais apertada do tamanho dos conjuntos de ambiguidade orientados a dados definidos pela distância de Wasserstein-1 em comparação com a literatura existente, utilizando desigualdades de McDiarmid de um lado e informações de momento.
• Verificação de Validade: Três métodos de verificação de validade que trocam eficiência e conservadorismo, todos menos conservadores que trabalhos existentes, unificados por um esquema de bandit de múltiplos braços que seleciona adaptativamente o verificador apropriado.
• Redução de Dimensionalidade: Uma formalização do uso de múltiplos tubos de ambiguidade de dimensão inferior para reduzir requisitos de dados e computacionais sem sacrificar a segurança.

Resultados Experimentais
Os autores avaliaram a abordagem em dois sistemas: um sistema linear de 4 dimensões e um sistema de drone de 8 dimensões navegando em espaços de trabalho 2D.

• Linhas de Base: O método foi comparado contra abordagens robustas distribucionalmente baseadas em momentos (TS e Risk-Assigned) e outras variantes baseadas em Wasserstein (Particle, Confidence, Hybrid).
• Desempenho:
  • Em ambientes congestionados e de passagens estreitas, o Bandit-WDR-RRT proposto superou significativamente as linhas de base baseadas em momentos, que falharam em encontrar caminhos devido ao conservadorismo excessivo. Por exemplo, em uma passagem estreita com ruído não gaussiano, as linhas de base alcançaram taxas de sucesso de 0–9%, enquanto o Bandit-WDR-RRT alcançou até 100%.
  • O verificador baseado em bandit demonstrou o melhor equilíbrio, igualando ou superando as taxas de sucesso de outras variantes enquanto era 1,5–3 vezes mais rápido que a abordagem Híbrida.
  • A abordagem de dimensão inferior permitiu com sucesso o planejamento para o sistema de drone de 8 dimensões aprendendo tubos separados para restrições de posição e controle, demonstrando escalabilidade.
• Segurança: Simulações de Monte Carlo confirmaram que os planos gerados alcançaram taxas de sucesso de 99–100% em evitar colisões, validando a correção das restrições do tubo de ambiguidade.

Significado
O artigo afirma que seu significado principal reside em fornecer um framework de planejamento de movimento provavelmente seguro e escalável para sistemas com distribuições de perturbação desconhecidas. Ao aproveitar conjuntos de ambiguidade de Wasserstein e aprendizado orientado a dados, a abordagem evita as super-approximações geométricas inerentes a métodos baseados em momentos e as suposições distribucionais de métodos baseados em Gaussianas. A capacidade de lidar com obstáculos de formato arbitrário e restrições não convexas sem sacrificar a completude probabilística torna o método adequado para aplicações robóticas complexas do mundo real onde a segurança é crítica e os modelos de perturbação são incertos. A introdução do verificador de validade baseado em bandit aprimora ainda mais a utilidade prática gerenciando dinamicamente o compromisso entre velocidade computacional e conservadorismo da solução.