BOW: Bayesian Optimization over Windows for Motion Planning in Complex Environments

1. Declaração do Problema

O planejamento de movimento para robôs móveis em ambientes complexos, congestionados e de alta dimensão é um problema desafiador de otimização com restrições. As dificuldades centrais incluem:

• Restrições Cinodinâmicas: Os robôs devem aderir a limites físicos (velocidade, aceleração, taxa de guinada) enquanto evitam obstáculos.
• Custo Computacional: A avaliação de funções objetivo (por exemplo, tempo, energia) e restrições de segurança ao longo de horizontes de planejamento longos é computacionalmente cara, especialmente para sistemas com dinâmicas complexas.
• Compensações: Métodos existentes frequentemente lutam para equilibrar optimalidade, segurança e eficiência computacional. Métodos tradicionais baseados em amostragem (como RRT) podem ser lentos, enquanto métodos baseados em grade ou heurísticos (como DWA) podem carecer de eficiência de amostragem ou ficar presos em mínimos locais.
• Requisitos em Tempo Real: O planejamento online exige encontrar entradas de controle viáveis e quase ótimas dentro de orçamentos de tempo estritos (milissegundos) a cada passo de tempo.

2. Metodologia: O Planejador BOW

Os autores propõem o BOW (Bayesian Optimization over Windows), um algoritmo de planejamento de movimento escalável que integra a Abordagem de Janela Dinâmica (DWA) com Otimização Bayesiana Constrained (CBO).

Conceito Central

Em vez de buscar todo o espaço de controle ou usar buscas em grade fixas, o BOW restringe a busca a uma janela de planejamento dinâmica ($V_d$) definida pelos limites cinodinâmicos atuais do robô (velocidades e acelerações alcançáveis). Dentro desta janela, ele utiliza Otimização Bayesiana para amostrar eficientemente entradas de controle.

Componentes Técnicos Chave

1. Controle de Horizonte Reduzido (RHC):

   • O planejador opera sobre um horizonte de previsão curto ($\Delta$).
   • Assume-se que uma entrada de controle constante $u_t$ é aplicada ao longo do horizonte para simplificar o cálculo do custo a percorrer.
   • O objetivo é minimizar uma função de custo $J$ (distância até o objetivo) sujeita a restrições de segurança $c_k$ (evitação de obstáculos).

2. Modelos Substitutos de Processo Gaussiano (GP):

   • Como a avaliação do custo real e das restrições via simulação é cara, o BOW modela a função objetivo $J(u)$ e as funções de restrição $c_k(u)$ como Processos Gaussianos.
   • Os GPs são treinados em um pequeno conjunto de amostras iniciais ($p$) dentro da janela dinâmica.

3. Melhoria Esperada Constrained (CEI):

   • Para selecionar a próxima entrada de controle, o BOW utiliza uma função de aquisição modificada chamada Melhoria Esperada Constrained (CEI).
   • Fórmula: $CEI(u) = EI(u) \times P(\text{viável} | u)$
   • $EI(u)$ equilibra exploração e exploração para o objetivo.
   • $P(\text{viável} | u)$ é a probabilidade de que a entrada de controle satisfaça todas as restrições de segurança (derivada do posterior do GP das restrições).
   • Isso permite que o planejador otimize simultaneamente desempenho e segurança, tratando efetivamente as restrições como restrições de chance suaves durante a busca.

4. Fluxo do Algoritmo:

   • Amostra $p$ candidatos de controle da janela dinâmica.
   • Avalia custos e restrições via simulação.
   • Treina GPs nos dados.
   • Maximiza a CEI para encontrar o controle ótimo $u^*_t$.
   • Gera uma trajetória usando o modelo de movimento (integração RK4) e valida-a contra o horizonte completo.
   • Aplica o controle por um passo $\ell$ (onde $\ell \le \Delta$) e repete.

3. Contribuições Principais

• Eficiência de Amostragem Aprimorada: O BOW encontra políticas de controle ótimas com significativamente menos avaliações (por exemplo, 5–15 amostras) em comparação com buscas em grade ou amostragem aleatória, reduzindo drasticamente o tempo de computação.
• Otimização Integrada à Segurança: Diferentemente de métodos que otimizam primeiro e verificam restrições depois, o BOW incorpora restrições de segurança diretamente na função de aquisição, garantindo que os controles selecionados sejam probabilisticamente viáveis.
• Escalabilidade: O método escala efetivamente para problemas de alta dimensão (testado em UAVs de 6-DOF) e ambientes complexos sem uma explosão linear no tempo de computação.
• Garantias Teóricas: O artigo fornece uma prova de convergência assintótica, demonstrando que, à medida que o número de amostras aumenta, o controle selecionado converge para a solução ótima verdadeira dentro da região viável.
• Código Aberto: O planejador é lançado como um pacote de código aberto com vídeos de experimentos do mundo real e simulados.

4. Resultados Experimentais

O planejador BOW foi avaliado em Veículos Terrestres Não Tripulados (UGVs) e Veículos Aéreos Não Tripulados (UAVs) em simulação e cenários do mundo real.

• Benchmarks: Comparado contra RRT, DWA, MPPI, HRVO e CBF em seis ambientes 2D distintos (incluindo "Bugtrap" e florestas de Poisson) e cinco cenários 3D de UAV.
• Métricas de Desempenho:
  • Tempo de Computação: O BOW alcançou os tempos de planejamento mais rápidos, variando de 10ms a 30ms por horizonte, com tempos de execução por passo tão baixos quanto 0,10–0,15 ms. Em contraste, concorrentes como CBF e MPPI levaram centenas a milhares de milissegundos.
  • Completude: O BOW manteve uma taxa de sucesso de 100% (completude perfeita) em todos os ambientes, enquanto concorrentes como DWA, HRVO e CBF falharam em encontrar soluções em cenários complexos específicos (por exemplo, passagens estreitas ou obstáculos de alta densidade).
  • Qualidade da Trajetória: O BOW produziu comprimentos de trajetória competitivos e suavidade (jerk moderado), superando o RRT em suavidade e o MPPI em consistência.
  • Eficiência de Amostragem: Em comparações visuais, o BOW identificou controles ótimos com apenas ~15 amostras, enquanto o DWA exigiu uma busca em grade completa e o MPPI exigiu amostragem uniforme de espaços viáveis e inviáveis.
• Implantação no Mundo Real: Implantado com sucesso em um UGV com tração diferencial e um UAV quadrotor, demonstrando evitação robusta de obstáculos usando LiDAR a bordo e navegação em tempo real em espaços 3D congestionados.

5. Significado e Impacto

• Aplicabilidade Prática: O BOW preenche a lacuna entre optimalidade teórica e viabilidade em tempo real, tornando-o adequado para dispositivos de borda com recursos limitados (por exemplo, Raspberry Pi, Jetson Nano) e aplicações robóticas de alta velocidade.
• Robustez na Incerteza: Ao usar modelos probabilísticos (GPs), o planejador lida melhor com incertezas nas dinâmicas e na percepção do ambiente do que heurísticas determinísticas.
• Direções Futuras: Embora o BOW se destaque como um planejador local, os autores reconhecem limitações no planejamento global (por exemplo, ficar preso em mínimos locais em passagens estreitas). Trabalhos futuros visam integrar o BOW com algoritmos de busca baseados em árvores para resolver problemas de planejamento de movimento global.

Em resumo, o Planejador BOW representa um avanço significativo no planejamento de movimento local, aproveitando a otimização bayesiana constrained para alcançar navegação rápida, segura e eficiente em amostragem em ambientes complexos e dinâmicos.