Learning When to Quit: Meta-Reasoning for Motion Planning

Autores: Yoonchang Sung, Leslie Pack Kaelbling, Tomás Lozano-Pérez · IROS 2021

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

Aprende, a partir de execuções anteriores do planejador, quando parar um planejador de movimento anytime (RRT, PRM, Lazy PRM*) para maximizar o compromisso entre a qualidade do caminho e o tempo de planejamento.

Por que importa

Todo robô que planeja com RRT ou PRM precisa escolher um orçamento de tempo de planejamento, e um tempo fixo ou um limiar de qualidade fixo desperdiça tempo ou qualidade do caminho. O método envolve um planejador anytime não modificado, de modo que pode ser acrescentado sobre planejadores existentes no estilo OMPL, desde que haja problemas de treinamento da distribuição de ambientes-alvo.

Problema

Planejadores de movimento anytime continuam encurtando um caminho quanto mais tempo rodam, mas não há uma relação bem caracterizada entre a qualidade da solução e o tempo de computação, então não está claro quando parar de planejar e começar a se mover. Seus perfis de desempenho são altamente não suaves porque caminhos mais curtos surgem em saltos repentinos quando o planejador encontra uma nova classe de homotopia, o que descarta uma extrapolação online simples da qualidade futura.

Solução proposta

Os autores aprendem uma política de parada a partir dos perfis de desempenho de problemas de planejamento anteriores extraídos da mesma distribuição, maximizando uma utilidade ponderada pelo usuário U(q, t) = wq − (1 − w)t. Uma variante baseada em modelo aprende um processo de decisão de Markov sobre qualidade e tempo discretizados e o resolve com iteração de valor; duas variantes livres de modelo (um classificador feed-forward sobre características projetadas à mão e um modelo sequência a sequência RNN) imitam decisões de parada de um oráculo calculadas a posteriori. Uma CNN prevê o comprimento do caminho ótimo a partir de uma imagem 2D do espaço de trabalho para que perfis de problemas de dificuldades diferentes possam ser normalizados e comparados.

Principais ideias

Os tempos de parada ótimos podem ser calculados a posteriori para cada execução de treinamento, o que transforma o problema de aprendizado da política em aprendizado por imitação supervisionado, em vez de aprendizado por reforço.
Normalizar a qualidade do caminho exige o comprimento do caminho ótimo, que é desconhecido; uma CNN que o prevê a partir de uma imagem 2D do espaço de trabalho torna os perfis comparáveis entre problemas, e um normalizador ruim (uma linha reta do início ao objetivo) reduz a utilidade drasticamente.
Características de histórico mais ricas (inclinação, planicidade) tornam o modelo de transição baseado em modelo muito mais preciso, mas seu custo de estimação cresce de segundos para mais de um dia, um caso direto da maldição da dimensionalidade.
A RNN aprende suas próprias características temporais a partir da sequência bruta de utilidade e deu os resultados bons mais confiáveis entre planejadores e pesos de utilidade.

Principais resultados

Acurácia do preditor CNN do comprimento do caminho ótimo em 200 espaços de trabalho reservados: 88,21%, 96,23% e 94,25% em três distribuições de ambientes.
O uso do normalizador CNN deu utilidades de 0,58, 0,65 e 0,66 nesses três ambientes, contra 0,63, 0,70 e 0,67 com os comprimentos ótimos reais e 0,39, 0,40 e 0,60 com um normalizador de linha reta.
A perda em dados reservados do modelo de transição caiu de 1,84 (sem características) para 0,22 com (t, q) e 0,10 com (t, q, inclinação), enquanto o tempo de estimação subiu de 0,41 s para 10,64 s e 11.933,72 s.
RRT* com w = 0,8: utilidade do oráculo 0,677, RNN 0,670, baseado em modelo 0,663, classificador 0,658, contra 0,634 da referência de qualidade fixa e 0,575 da referência de tempo fixo.
PRM* com w = 0,8: oráculo 0,718, baseado em modelo 0,702, RNN 0,698, classificador 0,697, qualidade fixa 0,674, tempo fixo 0,662.
Com w = 0,2 a referência de qualidade fixa ficou negativa (−0,283 para RRT, −0,344 para PRM, −0,367 para Lazy PRM*), enquanto os métodos aprendidos permaneceram positivos.

Limitações

O preditor CNN da solução ótima recebe uma imagem 2D do espaço de trabalho, o que limita os métodos a problemas com espaços de trabalho planos; a extensão para 3D por meio de grades de voxels ou nuvens de pontos é sugerida, mas não realizada.
Supõe-se que um novo problema venha da mesma distribuição dos problemas de treinamento, e o treinamento exige muitas execuções longas do planejador em problemas representativos.
Adicionar características de histórico ao método baseado em modelo era computacionalmente inviável nos experimentos maiores, então ele usou apenas (q, q_prev, t).
Toda a avaliação é em simulação com um robô rígido de três graus de liberdade em espaços de trabalho 2D; nenhum robô físico foi testado.
Apenas uma utilidade linear U(q, t) = wq − (1 − w)t foi estudada.

Impacto na área

O artigo foi finalista do IROS 2021 Best Paper Award on Cognitive Robotics e tem 14 citações. Ele não informa a publicação de código ou dados.

Resumo

Planejadores de movimento anytime são amplamente usados em robótica. No entanto, a relação entre a qualidade de sua solução e o tempo de computação não é bem compreendida e, portanto, não está claro como determinar quando abandonar o planejamento e iniciar a execução. Neste artigo, abordamos o problema de decidir quando parar a deliberação sob capacidade computacional limitada, o chamado metarraciocínio, para o planejamento de movimento anytime. Propomos métodos de aprendizado orientados por dados, metarraciocínio baseado em modelo e livre de modelo, que são aplicáveis a diferentes distribuições de ambientes e independentes da escolha do planejador de movimento anytime. Como parte do arcabouço, projetamos um preditor da solução ótima baseado em rede neural convolucional que prevê o comprimento do caminho ótimo a partir de uma imagem 2D dada do espaço de trabalho. Avaliamos empiricamente o desempenho dos métodos propostos em simulação, em comparação com métodos de referência.

Open Source Robotics