Homotopy Class

• 다른 이름: homotopy class of paths
• 카테고리: Planning & manipulation › Motion planning
• 태그: motion-planning, topology, trajectory-optimization, mobile-navigation

시작점과 목표가 같고 장애물을 통과하지 않고 서로 연속적으로 변형될 수 있는 경로들의 집합으로, 예를 들어 주어진 기둥의 왼쪽으로 지나는 모든 경로가 그렇다.

정의

시작점과 끝점이 같은 두 경로는, 끝점을 고정한 채 한 경로를 다른 경로로 연속적으로 구부려 바꿀 수 있고 그 사이의 모든 중간 경로가 자유 공간 안에 머문다면 호모토픽(homotopic)하다고 한다. 이 관계는 가능한 모든 경로를 동치류로 나누며, 이를 호모토피 클래스(homotopy classes)라고 한다. 시작점과 목표 사이에 장애물이 하나 있는 평면에서, 장애물의 왼쪽으로 지나는 경로들이 한 클래스를 이루고 오른쪽으로 지나는 경로들이 또 다른 클래스를 이룬다. 목표에 이르기 전에 장애물을 한 번 이상 감아 도는 경로들은 또 다른 클래스들을 이루므로, 장애물이 하나뿐이어도 회전수(winding number)로 구별되는 클래스가 무한히 많이 생긴다. 장애물이 하나 늘 때마다 가능성은 곱으로 늘어난다.

이 개념이 중요한 이유는 대부분의 경로 최적화기가 국소적으로 동작하기 때문이다. 경사 기반 궤적 최적화기와 탄성 밴드는 경로를 더 짧거나 매끄럽게 만들도록 변형하지만, 경로를 장애물을 통과해 밀어낼 수는 없으므로 처음 시작한 클래스 안에서 가장 좋은 경로만 찾는다. 어떤 클래스를 쓸지는 전역 플래너가 정하며, 흔히 암묵적으로 정한다. RRT 같은 샘플링 기반 플래너는 처음에 한 틈을 지나는 경로를 찾고 나중에 다른 틈을 지나는 더 짧은 경로를 발견할 수 있는데, 이는 점진적인 개선이 아니라 경로 비용의 갑작스러운 하락으로 나타난다. 호모토피 인식 플래너는 여러 클래스를 병렬로 추적하고 각 클래스에서 가장 좋은 경로를 최적화하여 이를 명시적으로 다룬다.

실제로 플래너는 호모토피 자체 대신 계산 가능한 불변량을 쓰는 경우가 많다. 평면 문제에서는 H-서명(H-signature)이나 각 장애물 주위의 감김 각 계산이 경로가 각 장애물의 어느 쪽으로 지나는지를 표시하는데, 엄밀히 말하면 이것이 식별하는 것은 관련되어 있지만 더 거친 호몰로지 클래스이다. 팔의 고차원 구성 공간에서도 클래스는 존재하지만 열거하기 어렵기 때문에, 주로 이동 로봇, 차량, 평면 문제에 대해 논의된다.

중요한 이유

경로가 어느 호모토피 클래스에 속하는지 알면, 국소 최적화기가 왜 긴 우회로에 갇히는지, 플래너의 비용이 왜 갑자기 뛰는지, 로봇이 왜 장애물을 왼쪽과 오른쪽으로 지나는 사이에서 진동할 수 있는지 설명할 수 있다. 클래스를 고려해 추론하는 플래너는 이런 실패를 피하고 실제로 서로 다른 경로 선택지를 제시할 수 있다.

주요 응용

• 장애물 주위의 대안 경로를 유지하는 이동 로봇용 국소 플래너
• 애니타임 플래너와 점근적 최적 플래너에서 해 비용의 계단식 변화 설명
• 궤적 최적화의 초기 추정값 선택
• 지나갈 쪽을 합의해야 하는 다중 로봇 및 군중 내비게이션
• 장애물 주위에서 케이블이 속한 클래스가 도달 가능한 경로를 제한하는 테더 로봇

실제 사례

한 창고 로봇은 여러 후보 궤적을 유지하는 국소 플래너를 쓰며, 각 후보는 근처의 팔레트와 사람 주위에서 서로 다른 호모토피 클래스에 속한다. 매 주기마다 각 후보를 시간과 여유 거리에 대해 최적화한 뒤 가장 비용이 낮은 것을 고른다. 주의하지 않으면 거의 같은 두 선택지 때문에 로봇이 주기마다 지나갈 쪽을 바꾸며 제자리에서 흔들리므로, 팀은 히스테리시스를 추가한다. 즉 새 클래스가 현재 클래스보다 일정 차이 이상 나아야만 로봇이 결정을 바꾼다. 또한 탐색하는 클래스 수에 상한을 두어 플래너가 사이클 타임 안에 머물게 한다.

흔한 오해

• 호모토픽한 경로는 길이가 비슷하다 — 호모토피는 위상적 성질이며, 같은 클래스의 두 경로도 길이가 크게 다를 수 있다
• 클래스의 수는 장애물을 돌아가는 방법의 수만큼뿐이다 — 장애물을 반복해서 감아 돌면 클래스가 무한히 많이 생긴다
• 국소 최적화기는 반복을 충분히 하면 전역 최단 경로를 찾는다 — 국소 최적화기는 초기 경로의 클래스 안에 머문다
• 호모토피 클래스와 호몰로지 클래스는 같다 — 호몰로지가 더 거칠며, H-서명 같은 실용적인 서명이 식별하는 것은 호몰로지 클래스이다

알아야 할 사람

• 최적 계획과 다중 모드 계획을 연구하는 모션 플래닝 연구자
• 국소 플래너를 튜닝하는 이동 로봇 내비게이션 엔지니어
• 초기화를 선택하는 궤적 최적화 실무자
• 구성 공간의 위상을 공부하는 학생

관련 기술

• H-서명(H-signature)
• Timed Elastic Band(TEB) 플래너
• 회전수(winding number)
• 보로노이 다이어그램(Voronoi diagram)
• 가시성 그래프(visibility graph)
• CHOMP와 TrajOpt

관련 용어

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

관련 프로젝트

• 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