Narrow Passage Problem

• 別名: narrow passages
• カテゴリ: Planning & manipulation › Motion planning
• タグ: motion-planning, sampling-based-planning, configuration-space, planner-failure-modes

自由空間の細い通路にサンプリングベースのプランナーが抱える難しさ。ランダムなサンプルがその中に入ることはまれなので、計画が遅くなるか、長い回り道に落ち着いてしまう。

定義

狭い通路問題（narrow passage problem）は、確率的ロードマップや高速探索ランダム木のようなサンプリングベースのモーションプランナーの最もよく知られた弱点である。これらのプランナーは、ランダムなサンプルを引き、それらを衝突のない短い動作でつなぐことでコンフィギュレーション空間を探索する。唯一のルート、あるいは最短のルートが、1 つ以上の方向に薄い自由空間の領域を通る場合、一様なサンプルがその中に入る確率はその体積に比例し、その体積はごく小さい。中に入ったサンプルでも、両側の近傍とつながるとは限らない。するとプランナーは通路を見つけるのに非常に多くのサンプルを必要とするか、先により長いルートを見つけてしまう。

この影響は次元とともに大きくなる。2D の地図でロボットより少しだけ広い隙間ならサンプリングは容易だが、棚の中に手を伸ばす 7 関節のアーム、穴へのペグの挿入、治具の中を通して部品を動かす作業では、有効なコンフィギュレーションが多次元の空間の中で薄い断片をなし、その体積の割合は極めて小さくなる。サンプリングベースのプランナーの理論解析、たとえば拡張性（expansiveness）や自由空間の ε-良好性（ε-goodness）は、この依存関係を明示する。収束の保証は依然として成り立つが、通路が狭くなるにつれて必要なサンプル数は急激に増える。

多くの対策は、サンプリングを自由空間の境界や隙間に偏らせる。ガウシアンサンプリングは障害物表面の近くにサンプルを残し、ブリッジテストは両端がともに衝突している短い線分の中点を残し、障害物ベースのサンプラーや中心軸サンプラーはサンプルを境界や通路の中央へ寄せ、学習したサンプラーは有用なコンフィギュレーションがどこにあるかを予測する。ほかの手法は、障害物を縮めたり制約を緩めたりして一時的に自由空間を広げ、より簡単な問題で計画してから経路を修復する。工学の実務では、うまく配置した中間ウェイポイントやゴール領域を選ぶことがしばしば効果的である。

重要な理由

多くの実際のタスクは狭い通路問題である。挿入、散らかった棚やビンへのアクセス、ドアや狭い治具の通過などがそうだ。この問題を見抜ければ、プランナーのタイムアウトや回り道の理由がわかり、単に制限時間を延ばすのではなくサンプラーを直すべきだとわかる。

主な用途

• ペグインホールの挿入と治具への組み付け
• 棚、キャビネット、ビンの中へのアームの動作
• ドアや狭い通路を通り抜ける移動ロボットや車両
• 機械部品の分解性と保守性の解析
• モーションプランナー向けサンプリング戦略のベンチマークと設計

実際の使われ方

あるアームが、両側に数ミリのクリアランスしかない治具に部品を置かなければならない。一様サンプラーでは、プランナーはしばしばタイムアウトするか、治具の周りを大きく振り回す経路を返す。チームは衝突メッシュをわずかに縮めると計画が速くなることを確かめて、原因を確認する。そのうえで、治具の上方に挿入前の姿勢を中間ゴールとして加え、最後のアプローチを衝突チェック付きのデカルト空間での直線移動に切り替え、残りの自由な動作には障害物表面の近くにサンプルを集めるサンプラーを加える。計画時間は短くなり、回り道は消える。

よくある誤解

• 狭い通路とは物理的に狭い隙間のことである — 狭いのはコンフィギュレーション空間においてであり、精密に回転させなければならない長い物体にとっては、広い戸口でも狭い通路になりうる
• 時間をかければ必ず解ける — 必要なサンプル数は次元と狭さに応じて急激に増えうるので、より良いサンプリングや分解のほうが通常は効果が大きい
• 確率的完全性があればプランナーはすぐに通路を見つける — 完全性が約束するのはいずれ成功することだけである
• 影響を受けるのはサンプリングベースのプランナーだけである — グリッド探索や最適化も、解像度の限界や不適切な初期推定のせいで、自由空間の薄い領域に苦労する

知っておくべき人

• OMPL、MoveIt などのライブラリを使うモーションプランニングエンジニア
• 挿入や組立に取り組むマニピュレーションエンジニア
• プランナー向けのサンプリング戦略を開発する研究者
• サンプリングベースの計画を学ぶ学生

関連技術

• ガウシアンサンプリング（Gaussian sampling）
• ブリッジテストサンプリング（bridge test sampling）
• 障害物ベース PRM（obstacle-based PRM）
• 中心軸 PRM（medial-axis PRM）
• 学習したサンプリング分布（learned sampling distributions）
• OMPL

関連用語

• Probabilistic Roadmap
• Rapidly-exploring random tree
• Configuration Space
• RRT*
• Homotopy Class
• Peg-in-hole insertion

関連プロジェクト

• 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