Homotopy Class

• 又稱: homotopy class of paths
• 類別: Planning & manipulation › Motion planning
• 標籤: motion-planning, topology, trajectory-optimization, mobile-navigation

一組起點與目標相同、不需穿過障礙物就能彼此連續變形的路徑，例如所有從某根柱子左側經過的路徑。

定義

若兩條起點與終點相同的路徑中，一條能在端點固定、且每條中間路徑都留在自由空間的情況下連續彎曲成另一條，這兩條路徑就是同倫的（homotopic）。這個關係把所有可能的路徑分成若干等價類，稱為同倫類（homotopy classes）。在起點與目標之間只有一個障礙物的平面上，從它左側經過的路徑構成一類，從它右側經過的路徑構成另一類；在抵達目標前繞障礙物一圈或多圈的路徑則構成更多的類，因此即使只有一個障礙物，也會產生無限多個類，並以環繞數加以區分。每多一個障礙物，可能性就會成倍增加。

這個概念之所以重要，是因為大多數路徑最佳化器都是局部運作的。以梯度為基礎的軌跡最佳化器與彈性帶會讓路徑變形，使其更短或更平滑，但無法把路徑推過障礙物，因此只能找到起始所在的類中的最佳路徑。全域規劃器決定要使用哪個類，而這個決定常常是隱含的。像 RRT 這樣以取樣為基礎的規劃器，可能先找到一條穿過某個空隙的路徑，之後又發現一條穿過另一個空隙的較短路徑，這會表現為路徑成本突然下降，而不是逐步改善。具同倫意識的規劃器會同時追蹤多個類，並在每個類中最佳化最好的路徑，讓這件事變得明確。

實務上，規劃器常使用可計算的不變量，而不是同倫本身。對平面問題而言，H-signature 或繞每個障礙物的環繞角計數會標記路徑從每個障礙物的哪一側經過，嚴格來說，它識別的是相關但較粗略的同調（homology）類。在機器手臂的高維組態空間中，這些類依然存在，但難以列舉，因此大多是在移動機器人、車輛與平面問題的情境中討論。

為何重要

知道一條路徑屬於哪個同倫類，可以說明為什麼局部最佳化器會卡在一條很長的繞行路徑上、為什麼規劃器的成本會突然跳動，以及為什麼機器人可能在從障礙物左側與右側經過之間來回擺盪。會對這些類進行推理的規劃器可以避免這些失敗，並提供真正不同的路線選擇。

主要應用

• 為移動機器人保留繞過障礙物之替代路線的局部規劃器
• 說明隨時規劃器與漸近最佳規劃器中解的成本為何階躍變化
• 為軌跡最佳化選擇初始猜測
• 必須協調從哪一側經過的多機器人與人群導航
• 有纜繩的機器人，其纜繩繞障礙物所屬的類會限制可到達的路徑

實際應用

一台倉儲機器人使用一個局部規劃器，它保留數條候選軌跡，每條都位於繞過附近棧板與行人的不同同倫類中。每個週期它都依時間與淨空距離最佳化每條候選軌跡，再挑出成本最低的一條。若不加處理，兩個幾乎相等的選項會讓機器人在相鄰週期之間換邊，在原地搖晃，因此團隊加入遲滯：新的類必須比目前的類好出一定幅度，機器人才會改變決定。他們也限制探索的類數量，讓規劃器維持在週期時間之內。

常見誤解

• 同倫的路徑長度相近 — 同倫是一種拓樸性質；同一類中的兩條路徑長度可能相差甚遠
• 類的數量只等於繞過障礙物的方式數 — 反覆繞行障礙物會產生無限多個類
• 只要迭代夠多次，局部最佳化器就會找到全域最短路徑 — 它會停留在初始路徑所在的類中
• 同倫類與同調類相同 — 同調較粗略，而 H-signature 等實用簽章識別的是同調類

誰需要了解

• 研究最佳規劃與多模態規劃的運動規劃研究人員
• 調校局部規劃器的移動機器人導航工程師
• 選擇初始化方式的軌跡最佳化實務人員
• 學習組態空間拓樸的學生

相關技術

• H-signature
• 時間彈性帶（Timed Elastic Band，TEB）規劃器
• 環繞數（winding number）
• Voronoi 圖（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