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

概念

Thumb
機器人所在的世界(英語:workspace

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

自由空間

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

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

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

算法

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

參考文獻

外部連結

Wikiwand in your browser!

Seamless Wikipedia browsing. On steroids.

Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.

Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.