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