Time Optimal Ergodic Search

Autores: Dayi Dong, Henry Berger, Ian Abraham · RSS 2023

Licenças

Acesso aberto
Artigo: CC BY 4.0

Tudo o que segue se baseia no artigo completo sob a licença CC BY 4.0; sua figura é mostrada com crédito aos autores.

Em resumo

Minimiza o tempo de busca sujeito a um limite superior γ na métrica ergódica: um único parâmetro define o quão minuciosa é a cobertura, e o otimizador escolhe a duração da trajetória.

Por que importa

Em voos de busca e resgate ou de levantamento, o operador pode especificar o quão minuciosa deve ser uma varredura e obter a trajetória mais rápida que a atenda, em vez de adivinhar uma duração. Restrições como limites de velocidade e barreiras contra obstáculos ficam na mesma otimização, e os tempos planejados se mantiveram em um quadricóptero real com diferença de até 1,5 s.

Problema

A busca ergódica planeja trajetórias contínuas que passam em cada região um tempo proporcional à sua informação, mas os métodos existentes fixam o horizonte de planejamento com antecedência, então o usuário não consegue equilibrar a minúcia da busca e o tempo. Minimizar o tempo e, ao mesmo tempo, minimizar a métrica ergódica é um problema mal-posto, porque uma trajetória só se torna totalmente ergódica quando o tempo tende ao infinito.

Solução proposta

A métrica ergódica se torna uma restrição de desigualdade E ≤ γ dentro de um problema de tempo mínimo, de modo que γ define o quão grossa ou fina a cobertura deve ser e o tempo final tf é uma variável de decisão. Os autores provam condições de otimalidade local com o princípio do máximo de Pontryagin usando um 'estado ergódico estendido' e, na prática, resolvem o problema por transcrição direta sobre N pontos de nó (Δt = tf/N) com um solver próprio de lagrangiano aumentado. Os obstáculos são tratados com restrições de funções barreira de controle discretas.

Principais ideias

Tratar a ergodicidade como um limite, e não como um objetivo, torna a busca de tempo mínimo bem-posta; quando γ → 0, o tempo ótimo cresce sem limite, de acordo com a teoria ergódica
Reduzir γ em duas ordens de grandeza (de 0,1 para 0,001) em um mapa de informação com quatro picos praticamente dobrou o tempo ótimo (de 9,86 s para 19,59 s), e mesmo o plano grosseiro ainda visitou todos os picos
O esforço de controle normalizado pelo tempo é maior no meio da faixa de γ, onde a trajetória precisa equilibrar cobertura e tempo, do que em qualquer um dos extremos
Estimativas iniciais suaves (interpolação linear) dão soluções consistentes; trajetórias iniciais ruidosas ou aleatórias caem em mínimos locais igualmente ergódicos com tempos mais longos

Principais resultados

Cobertura uniforme com uma massa pontual 2D: variar γ gera trajetórias de 5 a 10 s com cobertura equivalente a uma trajetória ergódica de horizonte fixo de 10 s (E = 0,007)
Mapa de informação não uniforme: tempos ótimos de 9,86 s com γ = 0,1 e de 19,59 s com γ = 0,001
Sensibilidade com γ = 0,05: variar o tf inicial de 4 a 8 s dá um tempo ótimo de 4,97 ± 0,23 s; variar o número de pontos de nó N de 50 a 600 dá 5,45 ± 0,39 s
Ambiente 2D com obstáculos e funções barreira de controle: tempos ótimos de 7,79 s com γ = 0,2 a 11,85 s com γ = 0,002, com as restrições de barreira mantendo as trajetórias longe de todos os obstáculos
Experimentos com drone com γ = 0,1, 0,05 e 0,01: os tempos de voo executados ficaram a até 1,5 s dos tempos otimizados; a trajetória da Fig. 1 cobre a área com obstáculos em 13,5 s
O solver também produziu trajetórias de cobertura uniforme para um modelo não linear de aeronave 3D entre obstáculos elipsoidais aleatórios

Limitações

Os autores afirmam que as soluções são apenas localmente ótimas, porque a métrica ergódica é altamente não linear e não convexa
Os autores constataram que as condições de otimalidade de Pontryagin são numericamente instáveis para horizontes longos, por isso o solver prático é um método de transcrição direta
O planejamento é offline e com obstáculos conhecidos; os autores listam como trabalho futuro o planejamento em tempo real com obstáculos desconhecidos e incerteza ambiental
Os resultados dependem da trajetória inicial e de N; o solver deixa de retornar soluções para γ muito pequeno, quando o tempo necessário se torna muito grande
Os autores observam que o custo computacional cresce com a dimensão do espaço de exploração

Impacto na área

Vencedor do RSS 2023 Best Paper Award. Os autores disponibilizam o código em github.com/ialab-yale/time_optimal_ergodic_search e uma página de demonstração multimídia.

Resumo

Robôs capazes de equilibrar o tempo e a minúcia da busca têm potencial para prestar assistência em situações críticas em tempo, como busca e resgate. Avanços recentes em métodos de busca baseados em cobertura ergódica permitiram que robôs explorassem e vasculhassem completamente uma área em um tempo fixo. No entanto, otimizar o tempo em relação à qualidade da busca ergódica autônoma ainda não havia sido demonstrado. Neste artigo, investigamos soluções para o problema de busca ergódica de tempo ótimo para busca e exploração robótica rápida e adaptativa. Formulamos o problema como um problema de tempo mínimo com uma restrição de desigualdade ergódica cujo limite superior regula e equilibra a granularidade da busca em relação ao tempo. As soluções do problema são apresentadas analiticamente usando as condições de otimalidade de Pontryagin e demonstradas numericamente por meio de uma abordagem de otimização por transcrição direta. Mostramos a eficácia da abordagem na geração de trajetórias de busca ergódica de tempo ótimo em simulação e em experimentos com drones em um ambiente com obstáculos. Mostra-se que o desvio de obstáculos é facilmente integrado à nossa formulação, e realizamos estudos de ablação que investigam a dependência dos parâmetros no tempo otimizado e a sensibilidade da trajetória para a busca.

Open Source Robotics