運動動力學規劃

運動動力學規劃、運動動力學運動規劃（英文：kinodynamic planning、kinodynamic motion planning）係機械人學同運動規劃中一類問題，要求個運動規劃必須滿足速度、加速度同力/扭矩限制以及運動學約束（例如避開啲障礙物）嘅，而嘸同於一般嘅運動規劃、可能只需要考慮到某樣嘢喺空間中嘅自由度或者同其他嘢嘅約束。

歷史[編輯]

個詞係由Bruce Donald 、Pat Xavier、John Canny 同 John Reif 等人創造嘅。^[1]佢哋幫個問題開發唨第一個多項式時間嘅逼近方案（英文：polynomial-time approximation schemes, PTAS）。透過提供證明得到嘅多項式時間嘅ε 逼近演算法，係噉佢哋解決到個開放問題（open problem）、個長期存在喺最佳化控制當中嘅問題。佢哋篇第一篇論文考慮到牛頓動力學下對點質量嘅時間最佳控制（「最快路徑」）喺多邊形（2D）或者多面體（3D）啲障礙物裏便而且服從位置、速度同加速度嘅狀態限制。跟尾佢哋擴展項技術到其他好多情況，例如，喺完全拉格朗日動力學下嘅 3D 開鏈（open-chain）運動機械人。近排都有好多基於隨機最佳化同迭代採樣嘅實用啟發式演算法、目標係攞嚟解決運動動力學規劃問題嘅得開發出。啲啟發式技術用於運動動力學規劃喺實踐中運作良好；但都未保證得到計算解決方案嘅最佳性（即冇性能保證），並且冇一種係可以喺數學上證明係快過個原始 PTAS 演算法嘅（即冇一種可以有證明到個計算複雜度係會低啲）。