Homotopy Class

• Também chamado: homotopy class of paths
• Categoria: Planning & manipulation › Motion planning
• Tags: motion-planning, topology, trajectory-optimization, mobile-navigation

Um conjunto de caminhos com o mesmo início e objetivo que podem ser deformados continuamente uns nos outros sem atravessar um obstáculo, como todos os caminhos que passam à esquerda de um determinado pilar.

Definição

Dois caminhos com os mesmos pontos de início e fim são homotópicos (homotopic) se um puder ser deformado continuamente no outro enquanto as extremidades ficam fixas e todo caminho intermediário permanece no espaço livre. Essa relação divide todos os caminhos possíveis em classes de equivalência, chamadas classes de homotopia (homotopy classes). Em um plano com um obstáculo entre o início e o objetivo, os caminhos que passam pela esquerda dele formam uma classe e os que passam pela direita formam outra; os caminhos que dão uma ou mais voltas ao redor do obstáculo antes de chegar ao objetivo formam outras classes, de modo que até um único obstáculo produz infinitas classes, distinguidas pelo número de voltas. Cada obstáculo a mais multiplica as possibilidades.

O conceito importa porque a maioria dos otimizadores de caminho trabalha localmente. Otimizadores de trajetória baseados em gradiente e bandas elásticas deformam um caminho para torná-lo mais curto ou mais suave, mas não conseguem empurrá-lo através de um obstáculo, então só encontram o melhor caminho dentro da classe em que começaram. Planejadores globais decidem qual classe usar, muitas vezes de forma implícita. Um planejador baseado em amostragem como o RRT pode encontrar primeiro um caminho por uma abertura e mais tarde descobrir um caminho mais curto por outra, o que aparece como uma queda brusca no custo do caminho em vez de uma melhoria gradual. Planejadores que levam a homotopia em conta tornam isso explícito acompanhando várias classes em paralelo e otimizando o melhor caminho de cada uma.

Na prática, os planejadores costumam usar um invariante computável em vez da própria homotopia. Em problemas planares, uma H-signature ou uma contagem do ângulo de enrolamento em torno de cada obstáculo indica por qual lado de cada obstáculo um caminho passa, o que, a rigor, identifica a classe de homologia, relacionada mas mais grosseira. No espaço de configurações de dimensão mais alta de um braço, as classes continuam existindo mas são difíceis de enumerar, por isso são discutidas principalmente para robôs móveis, veículos e problemas planares.

Por que importa

Saber a qual classe de homotopia um caminho pertence explica por que um otimizador local fica preso a um desvio longo, por que o custo de um planejador salta de repente e por que um robô pode oscilar entre passar um obstáculo pela esquerda e pela direita. Planejadores que raciocinam sobre classes evitam essas falhas e podem oferecer opções de rota realmente diferentes.

Principais aplicações

• Planejadores locais para robôs móveis que mantêm rotas alternativas em torno de obstáculos
• Explicar mudanças em degrau no custo da solução em planejadores anytime e assintoticamente ótimos
• Escolher estimativas iniciais para otimização de trajetórias
• Navegação multirrobô e em multidões, em que o lado de passagem precisa ser combinado
• Robôs com cabo, em que a classe do cabo em torno dos obstáculos limita os caminhos alcançáveis

Na prática

Um robô de armazém usa um planejador local que mantém várias trajetórias candidatas, cada uma em uma classe de homotopia diferente em torno de paletes e pessoas próximas. A cada ciclo, ele otimiza cada candidata quanto a tempo e folga e depois escolhe a mais barata. Sem cuidado, duas opções quase iguais fazem o robô trocar de lado de um ciclo para o outro e balançar no lugar, então a equipe acrescenta histerese: uma nova classe precisa superar a atual por uma margem antes que o robô mude de ideia. Eles também limitam o número de classes exploradas para que o planejador fique dentro do seu tempo de ciclo.

Equívocos comuns

• Caminhos homotópicos têm comprimentos semelhantes — a homotopia é uma propriedade topológica; dois caminhos na mesma classe podem diferir muito em comprimento
• Só existem tantas classes quantas são as maneiras de contornar os obstáculos — dar voltas repetidas em torno de um obstáculo cria infinitas classes
• Um otimizador local encontrará o caminho globalmente mais curto com iterações suficientes — ele permanece na classe do seu caminho inicial
• Classes de homotopia e de homologia são a mesma coisa — a homologia é mais grosseira, e assinaturas práticas como a H-signature identificam classes de homologia

Quem deve saber

• Pesquisadores de planejamento de movimento que trabalham com planejamento ótimo e multimodal
• Engenheiros de navegação de robôs móveis que ajustam planejadores locais
• Profissionais de otimização de trajetórias que escolhem inicializações
• Estudantes de topologia do espaço de configurações

Tecnologias relacionadas

• H-signature
• Planejador Timed Elastic Band (TEB)
• Número de voltas (winding number)
• Diagrama de Voronoi
• Grafo de visibilidade (visibility graph)
• CHOMP e TrajOpt

Termos relacionados

• Configuration Space
• Elastic band
• RRT*
• Anytime Motion Planning
• Narrow Passage Problem
• Motion Planning

Projetos relacionados

• OMPL: Sampling-based motion planning library powering MoveIt and countless robotics applications
• MoveIt 2: Motion planning framework for ROS 2 robot arms, with kinematics and collision checking
• PyRoki: Modular Python toolkit for kinematic optimization across CPU, GPU, and TPU via JAX
• mink: Python inverse kinematics library built on MuJoCo supporting 20+ robot platforms
• Ruckig: Real-time jerk-constrained time-optimal trajectory generation for robots and machines
• NeuPAN: Real-time end-to-end planner that maps raw lidar points directly to robot actions