Open Source Robotics

精選高品質的開源機器人專案、工具與軟體，推動機器人社群向前發展。

Anytime Motion Planning

  • 又稱: anytime planning, anytime planner
  • 類別: Planning & manipulation › Motion planning
  • 標籤: motion-planning, sampling-based-planning, optimal-planning, real-time, bounded-computation

一種運動規劃方式：先快速回傳一條有效路徑，再於時間允許時持續改進，因此無論規劃器何時被停止，都有可用的答案。

定義

隨時運動規劃器（anytime motion planner）會盡早產生第一個可行、無碰撞的解，接著把剩下的時間用來改進它，通常是降低路徑長度、執行時間或其他成本。在得到第一個解之後的每一刻，它都持有一個目前為止最好的答案，若被中斷就能回傳這個答案。這個概念源自人工智慧中更廣泛的隨時演算法，由 Dean 與 Boddy 於 1980 年代後期提出：解的品質與計算時間互相取捨，兩者之間的關係以效能曲線（performance profile）描述。

在圖搜尋中，隨時行為通常是這樣取得的：先以加權、放大的啟發式函數執行搜尋，再一邊重複利用先前的搜尋成果，一邊逐步收緊權重，Anytime Repairing A（ARA）即是如此。在以取樣為基礎的規劃中，RRT 以及機率路線圖的 PRM 變體等漸近最佳規劃器天生就是隨時的：它們在得到第一個解後仍持續取樣與重新連線，隨著樣本數增加，目前最佳路徑的成本會趨近最佳值。Informed RRT 與 Batch Informed Trees（BIT）把樣本限制在仍可能含有更好路徑的區域，藉此加快改進階段。單純的快速探索隨機樹**在這個意義上並不是隨時的，因為它一連上目標就會停止，不過可以在外層加上重新啟動或後處理。

隨時間的改進很少是平順的。成本常以階梯方式下降，尤其是當規劃器找到一條穿過障礙物之間另一個空隙的路線時，也就是一條位於新的同倫類中的路徑；而且可能有很長一段時間幾乎沒有進展。這使得何時停止本身成為一個問題：停得太早會犧牲品質，停得太晚則浪費機器人原本可以用來移動的時間。固定的時間預算是一般做法，而後設推理方法則會學習或估計何時進一步的計算已不再值得。

為何重要

機器人很少有固定且已知的規劃時間。隨時規劃器幾乎能立即提供一個安全的備案，並把任何多餘的時間轉換成更好的運動，適合那些必須在期限內行動、但仍重視路徑品質、能耗或週期時間的系統。

主要應用

  • 在操作流程中依每次查詢的時間預算進行機器手臂運動規劃
  • 必須依固定控制週期行動的移動機器人與車輛的重新規劃
  • 空中機器人的路徑規劃，較短的路徑能節省電池
  • 在網格與格點上以 ARA* 式權重遞減進行的啟發式圖搜尋
  • 關於何時停止規劃、開始行動的後設推理研究

實際應用

一台移動式操作臂使用 OMPL 等函式庫中的漸近最佳、以取樣為基礎的規劃器來規劃手臂運動。每次查詢都有一個時間預算：規劃器通常在預算初期就找到第一條路徑，接著持續縮短它。團隊在許多已記錄的查詢上記錄最佳成本與經過時間的關係，發現大部分的改善都很早出現，偶爾在後期找到繞過障礙物的較短路線時，成本會大幅下降。他們不再總是用完整個預算，而是在成本於設定的時間間隔內沒有改善時停止，或使用學習而來的停止規則，接著對結果進行捷徑化與時間參數化，再送給控制器。

常見誤解

  • 隨時代表第一個解接近最佳 — 第一個解往往離最佳很遠，品質取決於規劃器執行多久
  • 成本會隨時間穩定下降 — 它通常以不均勻的階梯下降，階梯之間有很長的停滯期
  • 漸近最佳性保證能在時間預算內得到好路徑 — 它只描述計算量無限增加時的極限，對有限的期限什麼也沒說
  • 用完整個時間預算總是最好的 — 花在規劃上的時間就是沒有花在移動上的時間，因此提早停止往往是更好的取捨

誰需要了解

  • 設定以取樣為基礎或以搜尋為基礎之規劃器的運動規劃工程師
  • 在即時限制下工作的移動式操作與導航開發者
  • 研究有限計算下之規劃的機器人研究人員
  • 學習最佳運動規劃的學生

相關技術

  • ARA（Anytime Repairing A）
  • RRT*
  • Informed RRT*
  • BIT*（Batch Informed Trees）
  • OMPL

相關術語

  • RRT*
  • Rapidly-exploring random tree
  • Probabilistic Roadmap
  • Homotopy Class
  • Warm Start
  • Motion Planning

相關專案

  • GENESIS: World's fastest physics engine: 43M FPS for embodied AI learning
  • Cartographer: Google's real-time 2D and 3D SLAM system for multi-platform robotics
  • FAST-LIVO2: Fast, direct LiDAR-inertial-visual odometry from HKU-MARS, published in IEEE T-RO
  • Dora AI: Dataflow middleware for AI robotics applications, built in Rust
  • OpenMind OM1: AI-native operating system for robots with modular perception, cognition, and action
  • Fast DDS: eProsima's high-performance DDS middleware — the default transport under ROS 2

本網站需要 JavaScript 才能正常運作。請啟用 JavaScript 以瀏覽我們的開源機器人專案。