Graph of Convex Sets

Também chamado: GCS, graphs of convex sets
Categoria: Planning & manipulation › Trajectory optimisation
Tags: motion-planning, convex-optimization, trajectory-optimization, configuration-space, manipulation

Uma formulação de planejamento de movimento que liga regiões convexas do espaço livre em um grafo e encontra um caminho suave e livre de colisões através delas por otimização convexa.

Definição

Grafo de conjuntos convexos (graph of convex sets, GCS) é um grafo em que cada vértice é um conjunto convexo e o ponto escolhido dentro de cada conjunto é uma variável de decisão contínua. As arestas ligam conjuntos entre os quais se pode passar, e os custos e restrições das arestas são funções convexas dos pontos em cada extremidade. Encontrar a rota mais barata por um grafo desse tipo combina uma escolha discreta, por quais conjuntos passar, com uma contínua, para onde ir em cada conjunto. Tobia Marcucci, Russ Tedrake e colegas formularam esse problema de caminho mínimo e mostraram que, embora seja em geral um problema inteiro misto, ele tem uma relaxação convexa forte que costuma ser exata ou quase exata.

Para o planejamento de movimento, a parte livre de colisões do espaço de configuração é primeiro coberta por uma coleção de regiões convexas, por exemplo com o algoritmo IRIS, que faz crescer grandes politopos livres de obstáculos a partir de pontos-semente. Cada região se torna um vértice, regiões que se sobrepõem são ligadas por arestas e, dentro de cada região, a trajetória é representada como uma curva suave, tipicamente uma curva de Bézier, que permanece dentro da região porque os pontos de controle da curva também permanecem. Custos como comprimento do caminho, duração ou energia, e limites de velocidade e aceleração, são escritos como restrições convexas. Resolver a relaxação e arredondá-la dá uma trajetória suave e livre de colisões, sem busca baseada em amostragem nem pós-processamento.

A abordagem pressupõe geometria euclidiana comum dentro de cada conjunto. Robôs cujos espaços de configuração dão a volta sobre si mesmos, como juntas de revolução contínuas sem limites ou o rumo de uma base móvel, não se encaixam diretamente nessa suposição. Extensões substituem os conjuntos convexos por conjuntos geodesicamente convexos sobre uma variedade: conjuntos em que dois pontos quaisquer são ligados por um único caminho mínimo, ou geodésica, que permanece dentro do conjunto. Com essa mudança, a mesma formulação de grafo consegue planejar nesses espaços não euclidianos. O GCS está disponível na caixa de ferramentas Drake.

Por que importa

Planejadores baseados em amostragem encontram caminhos viáveis, mas geralmente precisam de suavização e não dão nenhuma medida de quão bom é o caminho. O GCS produz trajetórias suaves que respeitam as restrições em uma única otimização, muitas vezes com um certificado de quão perto do ótimo está o resultado, o que é valioso para braços robóticos que trabalham repetidamente em células fixas, como prateleiras e estações de trabalho.

Principais aplicações

Planejamento de trajetórias livres de colisões para braços robóticos em células de trabalho fixas
Planejamento para robôs com juntas contínuas ou espaços de configuração que dão a volta sobre si mesmos
Planejamento de passos e contatos sobre regiões convexas do terreno
Trajetórias de tempo mínimo para drones em ambientes cheios de obstáculos
Planejamento bimanual e com vários braços em espaços de trabalho compartilhados

Na prática

Uma equipe que implanta um braço robótico para pegar itens de um conjunto fixo de caixas de prateleira primeiro gera, offline, regiões convexas do espaço de configuração livre de colisões, semeando o IRIS em configurações na frente e dentro de cada caixa. Isso leva tempo, mas só precisa ser refeito quando a célula muda. Em tempo de execução, cada pedido de coleta vira uma consulta GCS da configuração atual até uma meta em uma caixa. O solver retorna uma trajetória suave que respeita os limites de velocidade, e o tempo de solução cresce com o número de regiões, então a equipe mantém o conjunto de regiões no tamanho que a célula precisa, e não maior. Se uma meta fica fora de todas as regiões, a consulta falha, então a equipe acrescenta sementes onde falta cobertura. Uma verificação de colisões de horizonte curto ainda protege contra objetos que não estavam no modelo.

Equívocos comuns

O GCS exige que o espaço livre seja convexo — ele exige que o espaço livre seja coberto por uma união de regiões convexas, que pode aproximar formas complexas
O GCS sempre retorna o ótimo global por otimização convexa — a relaxação costuma ser exata, mas nem sempre; pode ser preciso arredondamento ou uma resolução inteira mista
O GCS substitui totalmente a verificação de colisões — ele garante ausência de colisões apenas em relação às regiões usadas, então as regiões precisam refletir o ambiente real

Quem deve saber

Engenheiros de planejamento de movimento para braços robóticos e drones
Pesquisadores de planejamento baseado em otimização
Integradores de sistemas de picking e montagem em células fixas
Estudantes de robótica que estudam planejamento e otimização convexa

Tecnologias relacionadas

Drake
Geração de regiões IRIS (IRIS Region Generation)
Curvas de Bézier (Bézier Curves)
Otimização convexa (Convex Optimization)
Programação convexa inteira mista (Mixed-Integer Convex Programming)

Termos relacionados

Projetos relacionados

LeRobot: HuggingFace ML library for real-world robotics in PyTorch
Isaac Lab: NVIDIA robot learning framework: one task API across Newton, PhysX and Isaac Sim
NVIDIA Isaac GR00T: NVIDIA open foundation model for humanoid robot reasoning and skills
OpenVLA: 7B-parameter Vision-Language-Action model for robotic manipulation
Drake: MIT robotics toolbox for model-based dynamics, optimization, and control system design
OpenArm: 7DOF humanoid arm for physical AI research in contact-rich environments

Vídeos

MIT Robotics - Russ Tedrake - Planning with Graphs of Convex Sets (in the age of foundation models): MIT Robotics