Uma nova estrutura de otimização para planejamento de movimento de robôs

Não é fácil para um robô sair de um labirinto. Imagine essas máquinas tentando atravessar a sala de jogos de uma criança para chegar à cozinha, com brinquedos diversos espalhados pelo chão e móveis bloqueando alguns caminhos potenciais. Este labirinto confuso exige que o robô calcule a jornada ideal até seu destino, sem colidir com nenhum obstáculo. O que o bot deve fazer?

O algoritmo dos pesquisadores do MIT CSAIL, Graphs of Convex Sets (GCS), Trajectory Optimization apresenta um sistema de planejamento de movimento escalável e livre de colisões para essas necessidades de navegação robótica.

A abordagem combina pesquisa gráfica (um método para encontrar caminhos discretos em uma rede) e otimização convexa (um método eficiente para otimizar variáveis ​​contínuas para que um determinado custo seja minimizado), e pode encontrar rapidamente caminhos através de ambientes labirínticos enquanto otimiza simultaneamente o trajetória do robô.

O GCS pode mapear trajetórias livres de colisões em até 14 dimensões (e potencialmente mais), com o objetivo de melhorar a forma como as máquinas funcionam em conjunto em armazéns, bibliotecas e residências.

O projeto liderado pelo CSAIL encontra consistentemente caminhos mais curtos em menos tempo do que planejadores comparáveis, mostrando a capacidade do GCS de planejar com eficiência em ambientes complexos.

Nas demonstrações, o sistema guiou habilmente dois braços robóticos segurando uma caneca em torno de uma prateleira enquanto otimizava o tempo e o caminho mais curtos. O movimento sincronizado da dupla lembrava uma coreografia de parceiro, balançando nas bordas da estante sem deixar cair objetos.

Nas configurações subsequentes, os pesquisadores removeram as prateleiras e os robôs trocaram as posições das tintas em spray e entregaram uns aos outros uma caixa de açúcar.

O sucesso destes testes no mundo real mostra o potencial do algoritmo para ajudar em domínios como a produção, onde dois braços robóticos trabalhando em conjunto poderiam derrubar um item de uma prateleira. Da mesma forma, essa dupla poderia auxiliar na arrumação dos livros em uma casa ou biblioteca, evitando os demais objetos próximos.

Embora problemas desta natureza tenham sido anteriormente resolvidos com algoritmos baseados em amostragem, que podem ter dificuldades em espaços de alta dimensão, o GCS utiliza otimização convexa rápida e pode coordenar com eficiência o trabalho de vários robôs.

“Os robôs se destacam em movimentos repetitivos e pré-planejados em aplicações como fabricação automotiva ou montagem de eletrônicos, mas têm dificuldade com a geração de movimentos em tempo real em ambientes ou tarefas novas.

Os métodos de planejamento de movimento de última geração empregam uma abordagem ‘hub and spoke’, usando gráficos pré-computados de um número finito de configurações fixas, que são conhecidas por serem seguras. Durante a operação, o robô deve aderir estritamente a este roteiro, muitas vezes levando a movimentos ineficientes do robô.

O planejamento de movimento usando Graph-of-Convex-Sets (GCS) permite que os robôs se adaptem facilmente a diferentes configurações dentro de regiões convexas pré-computadas – permitindo que o robô ‘dobre a esquina’ enquanto faz seus planos de movimento. Ao fazer isso, o GCS permite que o robô calcule planos rapidamente em regiões seguras de maneira muito eficiente, usando otimização convexa.

“Este artigo apresenta uma abordagem inovadora que tem o potencial de aumentar drasticamente a velocidade e a eficiência dos movimentos dos robôs e sua capacidade de adaptação a novos ambientes”, disse David MS Johnson, cofundador e CEO da Dexai Robotics.

O GCS também teve sucesso em demonstrações de simulação, onde a equipe considerou como um quadrotor poderia voar através de um prédio sem bater em árvores ou não conseguir entrar em portas e janelas no ângulo correto. O algoritmo otimizou o caminho em torno dos obstáculos e, ao mesmo tempo, considerou a rica dinâmica do quadrotor.

Um casamento ideal

A receita por trás do sucesso da equipe do MIT envolve o casamento de dois ingredientes principais: pesquisa gráfica e otimização convexa. O primeiro elemento do GCS pesquisa gráficos explorando seus nós, calculando diferentes propriedades em cada um deles para encontrar padrões ocultos e identificar o caminho mais curto para atingir o alvo. Muito parecido com os algoritmos de busca gráfica usados ​​para cálculo de distância no Google Maps, o GCS cria diferentes trajetórias para chegar a cada ponto de seu percurso em direção ao seu destino.

Ao combinar pesquisa gráfica e otimização convexa, o GCS pode encontrar caminhos através de ambientes complexos e otimizar simultaneamente a trajetória do robô.

O GCS executa esse objetivo traçando gráficos de diferentes pontos em seu entorno e calculando como chegar a cada um deles no caminho até seu destino final. Esta trajetória leva em conta diferentes ângulos para garantir que o robô evite colidir com as bordas de seus obstáculos. O plano de movimento resultante permite que as máquinas superem possíveis obstáculos, manobrando com precisão em cada curva, da mesma forma que um motorista evita acidentes em uma rua estreita.

O GCS foi inicialmente proposto em um artigo de 2021 como uma estrutura matemática para encontrar caminhos mais curtos em gráficos onde atravessar uma aresta exigia a resolução de um problema de otimização convexa.

Movendo-se com precisão através de cada vértice em grandes gráficos e espaços de alta dimensão, o GCS tinha um claro potencial no planejamento de movimentos robóticos. Em um artigo de acompanhamento, Marcucci e sua equipe desenvolveram um algoritmo que aplica sua estrutura a problemas complexos de planejamento para robôs que se movem em espaços de grandes dimensões.

O artigo de 2023 foi capa da Robótica Científicaenquanto o trabalho inicial do grupo está agora publicado no Jornal sobre Otimização da Sociedade de Matemática Industrial e Aplicada (SIAM).

Embora o algoritmo seja excelente na navegação em espaços apertados sem colisões, ainda há espaço para crescer. A equipe do CSAIL observa que o GCS poderia eventualmente ajudar com problemas mais complicados em que os robôs precisam fazer contato com seu ambiente, como empurrar ou deslizar objetos para fora do ambiente. o caminho. A equipe também está explorando aplicações de otimização de trajetória GCS para tarefas de robôs e planejamento de movimento.

“Estou muito entusiasmado com esta aplicação do GCS ao planejamento de movimento. Mas isso é apenas o começo. Essa estrutura está profundamente conectada a muitos resultados principais em otimização, controle e aprendizado de máquina, dando-nos uma nova vantagem em problemas que são simultaneamente contínuos e combinatória”, diz Russ Tedrake, professor do MIT, investigador principal do CSAIL e coautor de um novo artigo sobre o trabalho. “Há muito mais trabalho a fazer.”