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 城市挑戰賽的參賽車輛提出,在比賽中用來處理停車場與其他非結構化區域。與標準 A 一樣,它維護一個依成本加啟發值排序的開放串列。差別在於狀態的表示方式。搜尋空間依位置與航向劃分為單元,但每個節點都保存一個精確的連續姿態。擴展節點時,會以幾個轉向角(例如向左打滿、直行與向右打滿),向前行駛,並在允許時倒車,模擬車輛行駛一小段弧線,通常使用運動學自行車模型**。只有當新姿態所在的單元尚未以更低成本到達過時,才會保留它。
由於每條邊都是一段模擬運動,產生的路徑本身就可行駛,這是以單元中心為節點的普通網格 A 無法提供的。代價是依單元剪枝會丟棄一些原本可能通往解的狀態,因此這個規劃器在嚴格意義上既不完備也不最佳;粗的單元讓它很快,但可能使它錯過狹窄處的操控動作。原始方法使用兩個可採納的啟發函數並取較大者:不考慮障礙物時汽車的最短路徑長度,例如 Reeds–Shepp 路徑或 Dubins 車**路徑;以及在網格上做 2D 搜尋所得、能原地轉向之機器人的考慮障礙物最短路徑。它還會定期嘗試以一條 Reeds–Shepp 曲線把目前節點直接連到目標,稱為解析擴展,有助於搜尋到達精確的目標姿態。
原始路徑沿著離散的轉向選擇前進,因此會略呈鋸齒狀。原始系統以一個以梯度為基礎的最佳化器將其平滑化,在淨空距離、曲率與平滑度之間取得平衡,接著為追蹤控制器進行內插。Hybrid A 不同於狀態格點規劃(以預先計算的運動基元**連接固定的格點),也不同於假設有參考車道的 Frenet 座標系規劃器。
為何重要
Hybrid A* 是停車場、場區與其他沒有車道之空間中,類車機器人最廣泛使用的規劃器之一。它示範了一種將網格搜尋的速度與符合車輛轉向限制之路徑結合的實用方法,其結構也出現在許多開源自駕軟體堆疊中。
主要應用
- 自動停車與代客停車操控
- 卡車、牽引車與拖車在場區與站場中的調度操控
- 倉庫、農場與工地中的類車機器人
- 自動駕駛軟體堆疊中非結構化區域的規劃
- 越野與礦用車輛的路徑規劃
實際應用
一台自動牽引車必須倒車進入裝卸區。規劃器把場區離散化為位置單元與航向區間,以自行車模型用前進與後退的幾個轉向角擴展節點,並在每個模擬姿態檢查車輛完整外形輪廓的碰撞。每擴展幾次,它就嘗試一次直接連到裝卸區姿態的 Reeds–Shepp 連線。找到路徑後,會依曲率與淨空距離將其平滑化、重新檢查碰撞,並賦予速度曲線,再由路徑追蹤控制器驅動執行。當規劃器在狹窄處失敗時,團隊會先縮小單元尺寸或增加轉向角,之後才更動其他任何東西。
常見誤解
- Hybrid A 就是網格上的普通 A — 節點保存由模擬轉向運動到達的連續姿態,網格只用來剪除重複的狀態
- 因為有網格,它的路徑可能在運動學上不可行 — 邊是模擬的車輛運動,因此可行性成立;網格犧牲的是完備性與最佳性
- Hybrid A* 會給出最短路徑 — 單元剪枝與有限的轉向選擇代表結果是近似的,通常之後還要平滑化
- 它會規劃包含速度的完整軌跡 — 它規劃的是幾何路徑;速度曲線與動力學是之後才處理的
誰需要了解
- 從事停車與非結構化區域的自動駕駛工程師
- 使用類車或 Ackermann 平台的移動機器人開發者
- 學習搜尋式規劃的運動規劃學生
- 農業、採礦與物流領域的野外機器人工程師
相關技術
- A* 搜尋
- Reeds–Shepp 曲線
- 狀態格點規劃器(state lattice planner)
- Voronoi 場(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