Homotopy Class

• 別名: homotopy class of paths
• カテゴリ: Planning & manipulation › Motion planning
• タグ: motion-planning, topology, trajectory-optimization, mobile-navigation

始点とゴールが同じで、障害物を通過せずに互いに連続的に変形できる経路の集合。たとえば、ある柱の左側を通るすべての経路。

定義

始点と終点が同じ 2 本の経路は、端点を固定したまま、途中のすべての経路が自由空間にとどまるように一方を他方へ連続的に曲げられるとき、ホモトピック（homotopic）であるという。この関係によって、あり得るすべての経路は同値類に分けられ、これをホモトピー類（homotopy classes）と呼ぶ。始点とゴールの間に障害物が 1 つある平面では、その左側を通る経路が 1 つの類をなし、右側を通る経路が別の類をなす。ゴールに着く前に障害物の周りを 1 回以上回る経路はさらに別の類をなすので、障害物が 1 つだけでも類は無限にあり、巻き数によって区別される。障害物が増えるごとに、可能性は掛け算で増えていく。

この概念が重要なのは、ほとんどの経路最適化手法が局所的に働くからである。勾配ベースの軌道最適化やエラスティックバンドは経路を変形させて短く、あるいは滑らかにするが、障害物を突き抜けて経路を押し出すことはできないため、出発した類の中での最良の経路しか見つけられない。どの類を使うかを決めるのは大域的なプランナーであり、その決定は暗黙のうちに行われることが多い。RRT のようなサンプリングベースのプランナーは、最初にある隙間を通る経路を見つけ、後で別の隙間を通るより短い経路を発見することがあり、これは緩やかな改善ではなく経路コストの急な低下として現れる。ホモトピーを考慮するプランナーは、複数の類を並行して追跡し、それぞれの類で最良の経路を最適化することで、これを明示的に扱う。

実際には、プランナーはホモトピーそのものではなく、計算可能な不変量を使うことが多い。平面の問題では、H-signature、または各障害物の周りの巻き角の計数が、経路が各障害物のどちら側を通るかを表すラベルになる。厳密にいえば、これが識別するのは関連するがより粗いホモロジー（homology）類である。アームの高次元のコンフィギュレーション空間でも類は存在するが、列挙するのが難しいため、主に移動ロボット、車両、平面の問題について論じられる。

重要な理由

経路がどのホモトピー類に属するかを知れば、局所最適化が長い回り道から抜け出せない理由、プランナーのコストが急に跳ぶ理由、ロボットが障害物の左を通るか右を通るかで揺れ動く理由を説明できる。類について推論するプランナーはこうした失敗を避け、本当に異なるルートの選択肢を示すことができる。

主な用途

• 障害物を回る代替ルートを保持する移動ロボット用の局所プランナー
• エニタイムプランナーや漸近最適プランナーにおける解のコストの段階的変化の説明
• 軌道最適化の初期推定の選択
• どちら側を通るかを合意する必要があるマルチロボットや群衆の中でのナビゲーション
• 障害物の周りでのケーブルの類が到達可能な経路を制限する、テザー付きロボット

実際の使われ方

倉庫ロボットは、近くのパレットや人の周りでそれぞれ異なるホモトピー類に属する複数の候補軌道を保持する局所プランナーを使う。毎周期、各候補を時間とクリアランスについて最適化し、最もコストの低いものを選ぶ。何も対策をしないと、ほぼ同等の 2 つの選択肢のせいでロボットが周期ごとに通る側を切り替え、その場でふらつく。そこでチームはヒステリシスを加え、新しい類が現在の類を一定の差で上回らない限りロボットが判断を変えないようにする。また、探索する類の数に上限を設け、プランナーが周期時間内に収まるようにする。

よくある誤解

• ホモトピックな経路は長さが近い — ホモトピーは位相的な性質であり、同じ類の 2 本の経路でも長さが大きく異なることがある
• 類の数は障害物を回る方法の数だけである — 障害物の周りを繰り返し回ることで類は無限に生じる
• 局所最適化は反復を十分に重ねれば大域的に最短の経路を見つける — 初期経路の類にとどまる
• ホモトピー類とホモロジー類は同じである — ホモロジーのほうが粗く、H-signature のような実用的なシグネチャが識別するのはホモロジー類である

知っておくべき人

• 最適計画やマルチモーダル計画に取り組むモーションプランニングの研究者
• 局所プランナーを調整する移動ロボットのナビゲーションエンジニア
• 初期化を選ぶ軌道最適化の実務者
• コンフィギュレーション空間のトポロジーを学ぶ学生

関連技術

• 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