運動規劃（Motion Planning）就是在給定的位置A 與位置 B 之間為機器人找到一條符契約束條件的路徑。這個約束可以是無碰撞、路徑最短、機械功最小等。是機器人學的一個重要研究領域。
基本介紹
- 中文名：運動規劃
- 外文名：Motion Planning
- 套用領域：機械工程
基本概念,構型空間,定義,自由空間,算法介紹,格線搜尋,幾何算法,基於回報的算法,人工勢場法,基採樣的算法,軌跡最佳化,簡單分類,
基本概念
構型空間
構型（Configuration）是機器人的一個狀態，如平面機器人，構型可以是
，分別用於描述機器人的位置與姿態；而對於六軸機械臂，一個構型則是
，即每個關節的角度。
機器人所有構型的集合則形成構型空間（Configuration Space，C-Space）。構型空間的維度就是機器人的自由度，在構型空間中，機器人可以描述成一個點，一般運動規划算法均是在構型空間中進行的，這樣可以防止奇異。
對低維度機器人，構型空間可以通過空間離散法進行映射：
定義
運動規劃（Motion Planning）就是在給定的位置A 與位置 B 之間為機器人找到一條符契約束條件的路徑。這個約束可以是無碰撞、路徑最短、機械功最小等。具體的案例可以是為移動機器人規劃出到達指定地點的最短距離，或者是為機械臂規劃出一條無碰撞的運動軌跡，從而實現物體抓取等。
在數學角度而言，運動規劃（Motion Planning）與路徑規劃（Path Planning）屬於同一問題，但路徑規劃一般用於平面無人車/機器人的規劃，問題維度較低，常用的算法也不同，所以習慣上將兩者區別稱呼。
基本的運動規劃就是在起始構型與目標構型之間找到一條連續運動軌跡，同時避開環境中的障礙物。
自由空間
自由空間（Free Space）是滿足規劃約束的那部分構型空間，對於基本的運動規劃來說，自由空間就是指沒有跟環境發生碰撞的那部分構型空間。
對於常見的機構形成的構型空間均為微分流形，在任一點的局部均與歐式空間同態。這樣，我們便可以將在歐式空間的大部分分析直接套用到構型空間中。
算法介紹
低維度的問題一般可以採用基於格線的算法。直接將構型空間按照一定解析度劃分為格線，之後用四連通、八連通準則連線格線，之後在格線上進行搜尋求解。
而對於高維度的規劃問題，我們沒辦法顯式地描述構型空間，而直接劃分格線會引入極大的計算量。人工勢場等最佳化算法在高維情況下效果不錯，但很容易陷入局部極值。而基於採樣的算法是目前主流的算法，它可以避免局部極值問題，同時在實際實施中效率很高。此外，直接對軌跡進行修正最佳化的算法也有不錯的性能。
格線搜尋
這類算法直接將構型空間按照一定解析度劃分格線，在每個格線，機器人可以運動到相鄰格線（基於四連通或八連通準則）。只要在自由空間中指定起始點與目標點，我們就可以使用 Dijkstar 和 A* 等圖搜尋算法進行搜尋求解。
由於 A* 等圖搜尋算法是完備的，所以，格線搜尋算法的完備性取決於劃分格線的解析度，解析度越高，格線越密，算法的完備性越高；反之亦然。所以這類算法被稱為解析度完備性算法。
幾何算法
這類算法依賴於構型空間的幾何信息，所以只能在低維度。而由於機器人具有一定體積，不是一個點，所以需要將工作空間轉換成構型空間，這個拓撲變換可以使用一個叫做Minkowski sum 的工具。
可視圖法（Visibility graph）：可視圖法用封閉多面體描述障礙物；並將連線所有多面體的所有頂點，去除與障礙物相交的連線；之後將起始點與目標點與所有頂點連線，並去除與障礙物相交的連線。由此可得到一個圖。之後在圖上使用圖搜尋算法即可。
單元分解法（Cell decomposition）：按照一定規則進行單元分解，得到一系列完全屬於自由空間的單元。
基於回報的算法
這類算法為機器人的每一個狀態與動作賦予一定的回報，機器人通過一定方法學習得到每一個動作的價值，之後只需每一步沿著價值最高的路徑走即可。這類算法其實屬於強化學習（Reinforcement Learning）的範疇，是另外一大塊內容，這裡便不贅述了。
人工勢場法
勢場對應著能量分布，最常見的勢場就是重力場了，我們在不同高度會擁有不同重力勢能。斜面上的球會自然沿著斜面往下滾。
受此現象的啟發，人們便想到人工勢場法，人工添加勢場函式，讓目標點處於谷底，距離目標點越遠的勢場越高，同時，為了避免發生碰撞，可以在障礙物四周添加排斥勢場（障礙物處勢能最大）。
人工勢場非常直觀，且對運算量要求不高，可以跟機器人的控制相結合。當然，勢場法的一個問題就是沒辦法避開局部極小值問題，所以該方法是不完備的，同時也是非最最佳化的。
基採樣的算法
這類算法並不去直接求取構型空間，而是在構型空間內隨機採樣，只對採樣點進行碰撞檢測，判斷其是否位於自由空間內。之後，將該點連線到一個圖或者樹狀結構中。用這個圖或者樹來描述自由空間。這類算法效率非常高，但規劃的結果不穩定。
機率路圖（Probabilistic Road Maps，PRM）就是在規劃空間內隨機選取N個節點，之後連線各節點，並去除與障礙物接觸的連線，由此得到一個隨機路圖。顯然，當採樣點太少，或者分布不合理時，PRM算法是不完備的，但是隨著採用點的增加，也可以達到完備。所以PRM是機率完備且不最優的。
快速擴展隨機樹法（Randomly Exploring Randomized Trees，RRT）是從起始點開始向外拓展一個樹狀結構，而樹狀結構的拓展方向是通過在規劃空間內隨機采點確定的。與PRM類似，該方法是機率完備且不最優的。
當然，除了RRT和PRM，還有一大堆基於兩者的變種算法，如 RRT*，lazy-PRM, SBL 等等。
軌跡最佳化
軌跡最佳化（Trajectory Optimization）也是運動規劃的一個常用算法，這類算法一般是基於先用一個初始軌跡連線起始點與目標點，之後利用梯度下降或者圖最佳化算法調整軌跡。
這類算法效率很高，得到的軌跡也一般比基於採樣的算法好。但它對初始軌跡的依賴很高，它是從初始軌跡開始調整，所以只能收斂到初始軌跡附近的局部極值。但如果初始軌跡選得好，它的性能非常不錯。
簡單分類
c-空間法、自由空間法、格線法、四叉樹法、矢量場流的幾何表示法等。相應的搜尋算法有A*、遺傳算法等。
2、全局路徑規劃（global path planning）和局部路徑規劃（local path planning）：
