Non-Euclidean Motion Planning with Graphs of Geodesically-Convex Sets

Autores: Thomas Cohn, Mark Petersen, Max Simchowitz, Russ Tedrake · 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

Trata espaços de juntas que dão a volta em si mesmos (bases móveis, juntas contínuas) como variedades planas, de modo que o planejador de caminho mínimo GCS continua gerando caminhos globalmente ótimos e sem colisão.

Por que importa

Manipuladores móveis e braços com juntas de base sem limites agora podem usar um planejador que certifica que cada ponto da trajetória está livre de colisão e, quando resolvido de forma exata, que ela é ótima dentro do espaço livre certificado. O artigo também prova que a curvatura positiva (por exemplo, juntas esféricas SO(3) ou corpos em flutuação livre) quebra a convexidade, o que marca até onde essa abordagem não pode ir.

Problema

O planejador GCS de Marcucci et al. encontra caminhos sem colisão e globalmente ótimos por meio de uma decomposição do espaço de configuração livre em conjuntos convexos, mas apenas para espaços de configuração euclidianos. Uma base móvel que pode girar 360° completos, ou uma junta de revolução contínua, dá a volta em si mesma, então seu espaço de configuração não é euclidiano. Adicionar limites de junta artificiais ou tratar os ângulos como reais ilimitados torna o ótimo inviável ou exige conhecimento prévio da resposta e muitos conjuntos duplicados.

Solução proposta

Os autores modelam o espaço de configuração como uma variedade riemanniana e definem um Graph of Geodesically-Convex Sets (GGCS, grafo de conjuntos geodesicamente convexos), provando que ele mantém as garantias do GCS comum. Para variedades planas (de curvatura zero), que cobrem qualquer robô construído com juntas de 1 DoF mais uma base SE(2), cada conjunto é mapeado para o espaço euclidiano por uma carta de isometria local, e o problema se reduz a um problema GCS padrão de otimização convexa inteira mista com restrições de transição afins. As regiões são expandidas com IRIS e limitadas por junta pelo raio de convexidade, e as trajetórias de Bézier por partes com restrições de continuidade continuam valendo.

Principais ideias

SE(2), toda variedade de dimensão 1 e os produtos de variedades planas são planos, então robôs feitos de juntas de um único DoF e uma base móvel se encaixam no método; juntas esféricas de 3 DoF não
Limitar cada região IRIS por junta pelo raio de convexidade garante que a região continue geodesicamente convexa quando mapeada de volta para a variedade
Em um espaço plano com coordenadas alinhadas globalmente, os mapas de transição são afins, então as restrições de correspondência de extremidades e de continuidade de derivadas continuam convexas
Basta um único ponto de curvatura positiva para que a função de distância riemanniana seja não convexa em toda vizinhança desse ponto (Teorema 5)

Principais resultados

Robô pontual em um toro: caminho ótimo com volta completa em 0,79 s; braço planar de 5 juntas com juntas contínuas: planeja em 5,36 s e 4,63 s, e um dos planos gira a junta do meio mais de 360°
Braço planar: caminhos de relax-and-round (relaxar e arredondar) de comprimento 7,749 e 8,448 contra ótimos de branch-and-bound de 7,274 e 8,008
KUKA iiwa com uma junta de base contínua (simulação): 14 movimentos de separação de canecas usando 18 regiões convexas, com média de 25,75 s por movimento (faixa de 4,63 a 50,30 s)
PR2 (simulação, espaço de configuração de 15 dimensões), 7 tarefas de alcance em prateleiras: os caminhos do GGCS foram livres de colisão em todos os casos, por exemplo, 1M→4M com comprimento 3,875 contra 14,554 do PRM; Drake-Trajopt e PRM+Trajopt às vezes deram caminhos mais curtos, mas com leves colisões
O planejamento online do PR2 levou de 25,51 a 66,15 s com o GGCS-Planner, contra 0,49 a 0,54 s do PRM, 2,26 a 15,23 s do Drake-Trajopt e 11,61 a 40,10 s do PRM+Trajopt
Preparação offline do PR2: uma região IRIS levou em média 30,20 s (de 8,56 a 75,42 s), todas as regiões 156,63 s em paralelo; construir o PRM de 100.000 amostras levou 124,39 s

Limitações

Os autores afirmam que o método não consegue lidar com custos e restrições não convexos, como dinâmica não linear e cadeias cinemáticas fechadas, nem com juntas esféricas
Espaços de curvatura positiva como SO(3) ficam excluídos, porque ali a função de distância é comprovadamente não convexa
A otimalidade vale apenas dentro do espaço livre 'certificado' coberto pelas regiões; o desempenho depende muito da escolha das regiões, e para o PR2 algumas regiões intermediárias foram adicionadas à mão
Os tempos de planejamento online do PR2 (de 25,51 a 66,15 s) foram maiores que os de todas as baselines comparadas
Todos os resultados com robôs são em simulação; os autores listam como trabalho futuro o planejamento bimanual com restrições cinemáticas implícitas e o planejamento através de contato

Impacto na área

Finalista do RSS 2023 Best Paper Award, com 44 citações. Os autores publicam gravações interativas de todas as trajetórias em um site de resultados.

Resumo

Calcular trajetórias ótimas e sem colisão para sistemas de alta dimensão é um problema desafiador. Planejadores baseados em amostragem têm dificuldade com a dimensionalidade, enquanto otimizadores de trajetória podem ficar presos em mínimos locais devido às não convexidades inerentes à paisagem de otimização. O uso de programação inteira mista para encapsular essas não convexidades e encontrar trajetórias globalmente ótimas mostrou-se recentemente muito promissor, graças em parte a relaxações convexas justas e a estratégias de aproximação eficientes que reduzem muito os tempos de execução. Essas abordagens eram até então limitadas a espaços de configuração euclidianos, o que impedia seu uso com bases móveis ou juntas de revolução contínuas. Neste artigo, tratamos esses cenários modelando os espaços de configuração como variedades riemannianas e descrevemos um procedimento de redução, para o caso de curvatura zero, a um problema de otimização convexa inteira mista. Demonstramos nossos resultados em várias plataformas robóticas, incluindo a geração de trajetórias eficientes e sem colisão para um manipulador móvel bimanual PR2.

Open Source Robotics