Motion planning for hundreds of floating robots

Resumo Técnico: Planejamento de Movimento para Centenas de Robôs Flutuantes

Definição do Problema
O artigo aborda o desafio de planejar trajetórias livres de colisões e dinamicamente viáveis para grandes frotas de robôs omnidirecionais flutuantes (robôs de superfície) operando em um manifold plano. Diferente de drones aéreos, que podem utilizar manobras verticais para evitar conflitos em transições densas, os robôs de superfície são restritos a 2D, o que torna a coordenação e a prevenção de colisões intrinsecamente mais difíceis. O contexto de planejamento é o design de espetáculos interativos, onde um designer especifica keyframes esparsos (configurações de início e fim) e requer feedback quase imediato (segundos) para gerar trajetórias que podem abranger minutos e milhares de passos temporais.

A dificuldade central reside na escalabilidade da prevenção de colisões. À medida que o tamanho da frota ($N$) aumenta, o acoplamento entre agentes cresce rapidamente (frequentemente de forma quadrática), levando a um número de restrições de colisão por par que escala como $\binom{N}{2}K$ (onde $K$ é o número de passos temporais). Para $N$ grande (ex: 500) e $K$ grande (ex: 1000), formulações padrão de Programação Convexa Sequencial (SCP) resultam em Programas Quadráticos (QP) com centenas de milhões de entradas não nulas, tornando-os computacionalmente intratáveis para loops de design iterativos.

Metodologia
Os autores propõem um pipeline de planejamento hierárquico e escalável que decompõe o problema globalmente acoplado em subproblemas menores e independentes. O pipeline consiste em quatro etapas principais:

1. Inicialização e Alocação:

   • O processo começa com um problema de atribuição de custo mínimo para combinar robôs a posições alvo. Para robôs "rotulados" (aqueles com alvos fixos definidos pelo usuário), o custo é zero ou infinito para impor correspondências específicas. Para robôs "não rotulados", o custo é a distância euclidiana, minimizando o deslocamento total para reduzir trocas desnecessárias.
   • Uma trajetória inicial é gerada via interpolação linear entre as posições de início e fim. Esta inicialização geralmente não é livre de colisões.

2. Construção do Grafo de Colisão:

   • Um grafo espaço-temporal é construído onde os nós representam pares robô-tempo.
   • Arestas espaciais conectam robôs no mesmo passo temporal se estiverem dentro de um raio de segurança $R$.
   • Arestas temporais conectam um robô a si mesmo através de passos temporais consecutivos se ocorrer uma colisão em qualquer um deles.
   • Componentes conectados deste grafo definem "clusters de colisão". Os autores utilizam uma estrutura de dados KD-tree para detectar violações por par de forma eficiente, alcançando uma aceleração de quase 2000× em comparação com a verificação por pares ingênua.

3. Agrupamento (Clustering) e Decomposição:

   • Para fornecer ao otimizador a liberdade de planejar desvios, a janela temporal de cada cluster é expandida (bufferizada) por um hiperparâmetro $B$ (definido como 3 segundos).
   • Clusters bufferizados sobrepostos são fundidos usando um procedimento de union-find. Para evitar a criação de subproblemas excessivamente grandes (o que anularia os benefícios de paralelização), uma trava de complexidade é aplicada. Se a fusão exceder um limite de entradas não nulas nas matrizes QP, o grupo é dividido usando um mecanismo de pontuação que minimiza a complexidade máxima dos subproblemas resultantes.

4. Resolução de Subproblemas e Fusão:

   • Cada cluster é resolvido de forma independente e em paralelo usando um framework de SCP.
   • Melhoria de Formulação: O artigo introduz uma formulação de "transcrição direta" onde o vetor de decisão inclui tanto posições quanto velocidades ($\chi = [p, v]$). Isso converte a dinâmica em restrições de igualdade locais e melhora significativamente a esparsidade da matriz de restrição (reduzindo a complexidade de $O(N^2K^2)$ para $O(N^2K)$) em comparação com a formulação de "direct shooting" usada em trabalhos anteriores.
   • Robustez: Os mecanismos incluem perturbação da inicialização para configurações simétricas, coarsening (refinamento grosseiro) adaptativo da discretização caso uma solução seja inviável, e um passo de polimento leve.
   • Detecção de Ciclo: O pipeline detecta dependências cíclicas onde a fusão de clusters leva a padrões de colisão oscilantes. Ao detectar isso, subproblemas conflitantes são travados em um único subproblema conjunto para iterações subsequentes.
   • Finalmente, as soluções locais são fundidas em uma trajetória global, e o loop se repete até que uma solução livre de colisões seja encontrada.

Principais Contribuições

• Pipeline Hierárquico Escalável: Um método que constrói um grafo de colisão, decompõe o problema em clusters de interação e resolve-os em paralelo, permitindo o planejamento para centenas de robôs em segundos.
• Mecanismos de Decomposição Robustos: Técnicas para lidar com patologias comuns, incluindo atualizações rápidas de grafo, estratégias de buffering, travas de complexidade para evitar a explosão de subproblemas e detecção de ciclos para evitar oscilações.
• Reformulação de Otimização: Uma mudança para uma formulação de transcrição direta para a otimização de trajetória ao nível de cluster, o que melhora a esparsidade do QP e a robustez do solver, particularmente para configurações com altas frações de robôs rotulados.

Resultos e Validação
O sistema foi validado em simulações e em duas implementações no mundo real:

• Simulação: O pipeline gerou com sucesso trajetórias livres de colisões para frotas de até 500 robôs ao longo de 1000 passos temporais. Em um estudo de caso com 500 robôs, o solver alcançou uma taxa de convergência de 100% para até 30% de robôs rotulados e 99% para porcentagens superiores, com tempos de computação tipicamente abaixo de alguns segundos.
• Implementação Real 1 (Lago de Zurique): Uma frota de 24 robôs foi coreografada para transições abrangendo 1–2 minutos (400+ passos temporais). Designers puderam ajustar iterativamente os keyframes e regenerar trajetórias em segundos.
• Implementação Real 2 (Bienal de Veneza 2025): Uma frota de 8 robôs realizou transições abrangendo mais de 2000 passos temporais. Uma trajetória de 2491 passos foi computada em 1,23 segundo.

Significância
O artigo afirma que este pipeline focado em engenharia aborda o gargalo central de escalabilidade do planejamento de movimento multi-robô em superfícies. Ao decompor o problema e otimizar a formulação do solver, a abordagem é ordens de magnitude mais rápida do que os pipelines tradicionais de SCP monolíticos. Essa velocidade permite uma experiência de usuário interativa e fluida para o design de coreografia, permitindo que designers ajustem iterativamente keyframes esparsos e recebam feedback imediato sobre trajetórias livres de colisões e dinamicamente viáveis, uma capacidade anteriormente limitada por restrições computacionais em ambientes de superfície 2D.