運動規劃(英語:Motion Planning)是一個過程,用來尋找從起始狀態到目標狀態的移動步驟。常需要在運動受到約束的條件下找到最佳解。運動規劃多用於機械人學。例如,一個清潔機械人在樓層里打掃,它不能撞牆,也不能從樓梯口掉下去。給定一個任務,運動規劃演算法計算出一個動作序列,告訴機械人前進多少米,然後左轉右轉多少度。如果機械人要操作物品或者探測未知地形等等,運動規劃就變得很複雜了。除了機械人學,運動規劃在電腦遊戲里也用來模擬人物或車輛的運動。

概念

編輯
 
機械人所在的世界(英語:workspace

基本的運動規劃問題是通過連續的動作從起始位形s到達目標位形g,並且過程中要避開障礙物。機械人和障礙物可以抽象為二維或三維的幾何圖形,動作則被表示為位形空間中的路徑。

自由空間

編輯
 
將世界抽象為位形空間,灰色區域表示障礙物,白色區域為自由空間( )。

如果機械人採用某個位形時不會碰到障礙物,那麼這個位形屬於自由位形空間,簡稱自由空間(英文寫作 )。自由空間的補集即障礙空間。

測試一個位形是否屬於自由空間,先用正向運動學確定機械人的輪廓,然後檢視機械人是否與障礙物碰撞。

演算法

編輯

低維度的運動規劃問題可以用基于格點的演算法求解,如A*演算法

參考文獻

編輯

外部連結

編輯