Kinodynamic Planning

又稱: kinodynamic motion planning
類別: Planning & manipulation › Motion planning
標籤: motion-planning, dynamics, sampling-based-planning, trajectory-optimization, state-space

一種同時考量幾何約束（例如碰撞）與系統動態的運動規劃，求出的是隨時間變化的控制輸入，而不只是一條無碰撞路徑。

定義

運動動力學規劃（kinodynamic planning）是一種運動規劃，其解必須同時滿足運動學約束（例如避開障礙物與關節極限）和動力學約束（例如有界的加速度、力或扭矩）。這個術語由 Donald、Xavier、Canny 與 Reif 於 1993 年提出。運動動力學規劃器不是先在組態空間中搜尋一條幾何路徑、之後再替它安排時間，而是搜尋一段持續時間與一個控制函數，使得對系統動態積分所得到的軌跡從初始狀態出發、始終位於自由空間內，並結束在目標區域中。

因此，搜尋是在狀態空間中進行，狀態空間除了位置之外還包含速度，維度通常是組態空間的兩倍。主要的困難在於，兩個相近的狀態一般無法以直線相連：要連接它們，必須在動態約束下求解兩點邊界值問題，這對雙積分器或 Dubins 車這類簡單系統很容易，但在一般情況下很困難。以取樣為基礎的規劃器，例如由 LaValle 與 Kuffner 提出的 kinodynamic RRT，藉由向前生長一棵樹來避開這個問題：挑選一個節點，在短時間內施加取樣得到或選定的控制，並保留由此得到的狀態。後來的方法如 SST，則在不需要導引函數的情況下加入了漸近近似最佳性。

其他幾類方法以不同方式處理同一個問題。以搜尋為基礎的規劃器使用由預先計算之運動基元構成的晶格，其中每個運動基元在動力學上都可行。軌跡最佳化方法，包括直接配置法與射擊法，把控制量與狀態當作決策變數，求解帶約束的非線性規劃問題，它在局部收斂得很快，但可能陷入局部極小值。實際系統經常結合兩者：先由取樣或搜尋階段找到一條可行軌跡，再以最佳化加以精修。當動態不確定時，例如推動物體，規劃器可能使用學習得到的系統模型或殘差模型，並以開迴路控制進行規劃，再由回授加以修正。

為何重要

快速或沉重的機器人、汽車、無人機以及被推動的物體，都無法沿任意的幾何路徑移動：忽略動量或致動器限制的路徑，可能根本無法執行。運動動力學規劃產生系統實際上能跟隨的軌跡，在機器人快速移動或控制能力有限時尤其重要。

主要應用

汽車與其他非完整約束載具的軌跡規劃
無人機與定翼機的激進飛行規劃
非抓握式操作，例如規劃一連串推動動作
接近扭矩與速度限制的快速手臂運動
考量接觸動力學的腿足與人形機器人運動規劃
太空載具與水下載具的機動

實際應用

一支機器手臂必須在不夾取的情況下，把一個箱子推過桌面送到目標區域，同時避開一個障礙物。團隊把箱子的運動建模為推動參數（例如接觸點、方向與持續時間）的函數，使用一個以學習殘差修正的解析推動模型。kinodynamic RRT 從目前的箱子狀態取樣推動動作，以模型傳播每個動作，並把得到的箱子姿態加入樹中，同時捨棄會撞到障礙物的推動。一旦某個分支抵達目標區域，就執行這一連串推動，並在每次推動後重新觀測箱子姿態，讓規劃器在模型有誤時能從真實狀態重新規劃。

常見誤解

運動動力學規劃就是幾何規劃再加上時間參數化 — 解耦的流程可能產生任何動力學上可行的軌跡都無法跟隨的路徑，而運動動力學規劃器在搜尋時就考量動態
只要換掉距離度量，任何以取樣為基礎的規劃器都能變成運動動力學規劃器 — 連接兩個狀態通常需要求解邊界值問題或向前傳播控制，而不是畫一條直線
運動動力學規劃可以用開迴路執行 — 模型誤差與擾動會累積，因此規劃通常需要由回授控制器追蹤，或重新規劃

誰需要了解

負責車輛、無人機與機器手臂的運動規劃工程師
研究推動與其他動態任務的操作研究人員
自動駕駛規劃工程師
研讀組態空間之外之規劃問題的機器人學學生

影片

6.8210 Spring 2024 Lecture 18: Sampling-based (kinodynamic) motion planning: underactuated

Open Source Robotics

Kinodynamic Planning

定義

為何重要

主要應用

實際應用

常見誤解

誰需要了解

相關技術

相關術語

相關專案

影片