運動規劃

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

概念

機器人所在的世界（英語：workspace）

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

自由空間

將世界抽象為位形空間，灰色區域表示障礙物，白色區域為自由空間（$C_{free}$）。

如果機器人採用某個位形時不會碰到障礙物，那麼這個位形屬於自由位形空間，簡稱自由空間（英文寫作$C_{free}$）。自由空間的補集即障礙空間。

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

算法

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

外部連結

• "Open Robotics Automation Virtual Environment", http://openrave.org/ （頁面存檔備份，存於網際網路檔案館）
• Jean-Claude Latombe talks about his work with robots and motion planning, 5 April 2000
• "Open Motion Planning Library (OMPL)", http://ompl.kavrakilab.org （頁面存檔備份，存於網際網路檔案館）
• "Motion Strategy Library", http://msl.cs.uiuc.edu/msl/ （頁面存檔備份，存於網際網路檔案館）
• "Motion Planning Kit", https://ai.stanford.edu/~mitul/mpk （頁面存檔備份，存於網際網路檔案館）
• "Simox", http://simox.sourceforge.net （頁面存檔備份，存於網際網路檔案館）
• "Robot Motion Planning and Control", http://www.laas.fr/%7Ejpl/book.html （頁面存檔備份，存於網際網路檔案館）