運動規劃

構型（Configuration）是機器人的一個狀態，如平面機器人，構型可以是

，分別用於描述機器人的位置與姿態；而對於六軸機械臂，一個構型則是

，即每個關節的角度。

機器人所有構型的集合則形成構型空間（Configuration Space，C-Space）。構型空間的維度就是機器人的自由度，在構型空間中，機器人可以描述成一個點，一般運動規劃算法均是在構型空間中進行的，這樣可以防止奇異。 ^[1] 

對低維度機器人，構型空間可以通過空間離散法進行映射：

運動規劃（Motion Planning）就是在給定的位置A 與位置 B 之間為機器人找到一條符合約束條件的路徑。這個約束可以是無碰撞、路徑最短、機械功最小等。具體的案例可以是為移動機器人規劃出到達指定地點的最短距離，或者是為機械臂規劃出一條無碰撞的運動軌跡，從而實現物體抓取等。

在數學角度而言，運動規劃（Motion Planning）與路徑規劃（Path Planning）屬於同一問題，但路徑規劃一般用於平面無人車/機器人的規劃，問題維度較低，常用的算法也不同，所以習慣上將兩者區別稱呼。

基本的運動規劃就是在起始構型與目標構型之間找到一條連續運動軌跡，同時避開環境中的障礙物。

自由空間（Free Space）是滿足規劃約束的那部分構型空間，對於基本的運動規劃來説，自由空間就是指沒有跟環境發生碰撞的那部分構型空間。

對於常見的機構形成的構型空間均為微分流形，在任一點的局部均與歐式空間同態。這樣，我們便可以將在歐式空間的大部分分析直接應用到構型空間中。

低維度的問題一般可以採用基於網格的算法。直接將構型空間按照一定分辨率劃分為網格，之後用四連通、八連通準則連接網格，之後在網格上進行搜索求解。

而對於高維度的規劃問題，我們沒辦法顯式地描述構型空間，而直接劃分網格會引入極大的計算量。人工勢場等優化算法在高維情況下效果不錯，但很容易陷入局部極值。而基於採樣的算法是目前主流的算法，它可以避免局部極值問題，同時在實際實施中效率很高。此外，直接對軌跡進行修正優化的算法也有不錯的性能。

這類算法直接將構型空間按照一定分辨率劃分網格，在每個網格，機器人可以運動到相鄰網格（基於四連通或八連通準則）。只要在自由空間中指定起始點與目標點，我們就可以使用 Dijkstar 和 A* 等圖搜索算法進行搜索求解。

由於 A* 等圖搜索算法是完備的，所以，網格搜索算法的完備性取決於劃分網格的分辨率，分辨率越高，網格越密，算法的完備性越高；反之亦然。所以這類算法被稱為分辨率完備性算法。 ^[2] 

這類算法依賴於構型空間的幾何信息，所以只能在低維度。而由於機器人具有一定體積，不是一個點，所以需要將工作空間轉換成構型空間，這個拓撲變換可以使用一個叫做Minkowski sum 的工具。

可視圖法（Visibility graph）：可視圖法用封閉多面體描述障礙物；並將連接所有多面體的所有頂點，去除與障礙物相交的連線；之後將起始點與目標點與所有頂點連接，並去除與障礙物相交的連線。由此可得到一個圖。之後在圖上使用圖搜索算法即可。

單元分解法（Cell decomposition）：按照一定規則進行單元分解，得到一系列完全屬於自由空間的單元。

這類算法為機器人的每一個狀態與動作賦予一定的回報，機器人通過一定方法學習得到每一個動作的價值，之後只需每一步沿着價值最高的路徑走即可。這類算法其實屬於強化學習（Reinforcement Learning）的範疇，是另外一大塊內容，這裏便不贅述了。

勢場對應着能量分佈，最常見的勢場就是重力場了，我們在不同高度會擁有不同重力勢能。斜面上的球會自然沿着斜面往下滾。

受此現象的啓發，人們便想到人工勢場法，人工添加勢場函數，讓目標點處於谷底，距離目標點越遠的勢場越高，同時，為了避免發生碰撞，可以在障礙物四周添加排斥勢場（障礙物處勢能最大）。

人工勢場非常直觀，且對運算量要求不高，可以跟機器人的控制相結合。當然，勢場法的一個問題就是沒辦法避開局部極小值問題，所以該方法是不完備的，同時也是非最優化的。 ^[2] 

這類算法並不去直接求取構型空間，而是在構型空間內隨機採樣，只對採樣點進行碰撞檢測，判斷其是否位於自由空間內。之後，將該點連接到一個圖或者樹狀結構中。用這個圖或者樹來描述自由空間。這類算法效率非常高，但規劃的結果不穩定。

概率路圖（Probabilistic Road Maps，PRM）就是在規劃空間內隨機選取N個節點，之後連接各節點，並去除與障礙物接觸的連線，由此得到一個隨機路圖。顯然，當採樣點太少，或者分佈不合理時，PRM算法是不完備的，但是隨着採用點的增加，也可以達到完備。所以PRM是概率完備且不最優的。

快速擴展隨機樹法（Randomly Exploring Randomized Trees，RRT）是從起始點開始向外拓展一個樹狀結構，而樹狀結構的拓展方向是通過在規劃空間內隨機採點確定的。與PRM類似，該方法是概率完備且不最優的。

當然，除了RRT和PRM，還有一大堆基於兩者的變種算法，如 RRT*，lazy-PRM, SBL 等等。

軌跡優化（Trajectory Optimization）也是運動規劃的一個常用算法，這類算法一般是基於先用一個初始軌跡連接起始點與目標點，之後利用梯度下降或者圖優化算法調整軌跡。

這類算法效率很高，得到的軌跡也一般比基於採樣的算法好。但它對初始軌跡的依賴很高，它是從初始軌跡開始調整，所以只能收斂到初始軌跡附近的局部極值。但如果初始軌跡選得好，它的性能非常不錯。 ^[3] 

1、基於模型和基於傳感器的路徑規劃：

c-空間法、自由空間法、網格法、四叉樹法、矢量場流的幾何表示法等。相應的搜索算法有A*、遺傳算法等。

2、全局路徑規劃（global path planning）和局部路徑規劃（local path planning）：

局部路徑規劃主要解決機器人定位和路徑跟蹤問題，方法有人工勢場法、模糊邏輯法等。全局路徑規劃將全局目標分解為局部目標，再由局部規劃實現局部目標，方法有可視圖法、環境分割法（自由空間法、柵格法）等。

3、離線路徑規劃和在線路徑規劃：

離線路徑規劃是基於環境先驗完全信息的路徑路徑規劃。完整的先驗信息只能適用於靜態環境，路徑是離線規劃的；在線路徑規劃是基於傳感器信息的不確定環境的路徑規劃，路徑必須是在線規劃的。 ^[3]