Open Source Robotics

高品質なオープンソースロボティクスプロジェクト、ツール、ソフトウェアの厳選コレクション。

Hybrid A*

  • 別名: Hybrid A-star, hybrid-state A*
  • カテゴリ: Planning & manipulation › Motion planning
  • タグ: path-planning, graph-search, autonomous-driving, nonholonomic, parking

車のようなロボットのための A* 探索の変種で、連続状態で実行可能な操舵動作をシミュレーションしてノードを展開し、粗い (x, y, 方位) グリッドで枝刈りする。

定義

Hybrid A は、非ホロノミック拘束をもつ車両のための探索ベースの経路プランナーで、Dolgov、Thrun、Montemerlo、Diebel が 2007 年の DARPA Urban Challenge に出場したスタンフォード大学の車両のために導入し、駐車場などの非構造化エリアの処理に用いられた。標準の A と同様に、コストとヒューリスティックの和で並べたオープンリストを保持する。違いは状態の表し方にある。探索空間は位置と方位でセルに分割されるが、各ノードは正確な連続の姿勢を保持する。ノードの展開では、通常は運動学的な二輪モデル**を使い、左いっぱい、直進、右いっぱいといった少数の操舵角で、前進と、許される場合は後退について、車両を短い円弧だけシミュレーションする。新しい姿勢は、そのセルにまだより低いコストで到達していない場合にのみ残される。

すべてのエッジがシミュレーションした動作であるため、得られる経路は構成上走行可能であり、これはセル中心を結ぶ素のグリッド A では得られない。その代わり、セル単位の枝刈りが解につながったかもしれない状態を捨てるので、このプランナーは厳密な意味で完全でも最適でもない。セルを粗くすると速くなるが、狭い場所での切り返しを見逃すことがある。元の手法は 2 つの許容的ヒューリスティックを使い、大きいほうを採った。1 つは障害物のない場合の車の最短経路の長さで、Reeds–Shepp 経路や Dubins カー**の経路がこれにあたる。もう 1 つは、その場で旋回できるロボットについてグリッド上の 2D 探索で求めた、障害物を考慮した最短経路である。また、現在のノードを Reeds–Shepp 曲線でゴールに直接つなぐことを定期的に試みた。これは解析的展開と呼ばれ、探索が正確なゴール姿勢に到達するのを助ける。

生の経路は離散的な操舵の選択に従うため、わずかにジグザグする。元のシステムは、クリアランス、曲率、滑らかさのバランスをとる勾配ベースの最適化で経路を平滑化し、その後追従コントローラのために補間した。Hybrid A は、固定された格子点を事前計算した動作プリミティブ**でつなぐステートラティス計画とも、基準となる車線を前提とする Frenet フレームのプランナーとも異なる。

重要な理由

Hybrid A* は、駐車場、ヤードなど車線のない空間で、車のようなロボットに最も広く使われているプランナーの一つである。グリッド探索の速さと、車両の旋回限界を守る経路とを組み合わせる実用的な方法を示しており、その構造は多くのオープンソースの自動運転スタックに見られる。

主な用途

  • 自動駐車やバレーパーキングの操作
  • ヤードやデポでのトラック、牽引車、トレーラーの取り回し
  • 倉庫、農場、建設現場での車のようなロボット
  • 自動運転スタックにおける非構造化エリアでの計画
  • オフロード車両や鉱山車両の経路計画

実際の使われ方

自律走行の牽引車が荷積みベイにバックで入らなければならない。プランナーはヤードを位置のセルと方位のビンに離散化し、二輪モデルを使って前進・後退それぞれ少数の操舵角でノードを展開し、シミュレーションした各姿勢で車両の外形全体について衝突をチェックする。数回の展開ごとに、ベイの姿勢への Reeds–Shepp による直接接続を試みる。経路が見つかると、曲率とクリアランスについて平滑化し、衝突を再チェックし、速度プロファイルを与えてから、経路追従コントローラに走らせる。狭い場所でプランナーが失敗した場合、チームはほかの何かを変える前に、まずセルサイズを小さくするか操舵角を増やす。

よくある誤解

  • Hybrid A はグリッド上の普通の A である — ノードはシミュレーションした操舵動作で到達した連続の姿勢を保持し、グリッドは重複の枝刈りにしか使われない
  • グリッドのせいで経路が運動学的に実行不可能になりうる — エッジはシミュレーションした車両の動作なので実行可能性は保たれる。グリッドが犠牲にするのは完全性と最適性である
  • Hybrid A* は最短経路を与える — セルによる枝刈りと限られた操舵の選択肢のため結果は近似であり、通常はその後に平滑化を行う
  • 速度を含む完全な軌道を計画する — 計画するのは幾何学的な経路であり、速度プロファイルとダイナミクスは後で扱う

知っておくべき人

  • 駐車や非構造化エリアに取り組む自動運転エンジニア
  • 車のようなプラットフォームやアッカーマン型プラットフォームを使う移動ロボット開発者
  • 探索ベースの計画を学ぶモーションプランニングの学生
  • 農業、鉱業、物流のフィールドロボティクスエンジニア

関連技術

  • A* 探索
  • Reeds–Shepp 曲線
  • ステートラティスプランナー(state lattice planner)
  • ボロノイ場(Voronoi field)
  • 経路平滑化(path smoothing)
  • Pure Pursuit と Stanley コントローラ

関連用語

  • Nonholonomic Constraint
  • Dubins Car
  • Bicycle model
  • Motion Primitive
  • Configuration Space
  • Frenet Frame Planning

関連プロジェクト

  • Nav2: ROS 2 navigation stack with path planning and obstacle avoidance for mobile robots
  • ROS Motion Planning: One repo implementing 40+ classic and learning-based robot path planners as ROS plugins
  • OMPL: Sampling-based motion planning library powering MoveIt and countless robotics applications
  • Mesh Navigation: Robot navigation on 3D triangle meshes for rough outdoor terrain, from Nature Robots
  • Fields2Cover: Coverage path planning library for autonomous agricultural vehicles
  • Vision Pilot: Autoware Foundation's open-source L2 ADAS stack from a single camera

このウェブサイトにはJavaScriptが必要です。オープンソースロボティクスプロジェクトを閲覧するにはJavaScriptを有効にしてください。