運(yùn)動規(guī)劃簡介
當(dāng)虛擬人開始一次漫游時，首先全局規(guī)劃器根據(jù)已有的長期信息進(jìn)行全局靜態(tài)規(guī)劃，確定虛擬人應(yīng)該經(jīng)過的最優(yōu)化路線。然后全局規(guī)劃器控制執(zhí)行系統(tǒng)按照該路徑運(yùn)動。在運(yùn)動過程中，感知系統(tǒng)會持續(xù)對周圍環(huán)境進(jìn)行感知。當(dāng)發(fā)現(xiàn)動態(tài)的物體或未知障礙時，局部規(guī)劃器根據(jù)這些感知到的局部信息，確定短期內(nèi)的運(yùn)動。當(dāng)避障行為的優(yōu)先級高于沿原路徑前進(jìn)時，局部規(guī)劃器就能夠通過競爭獲得執(zhí)行系統(tǒng)的控制權(quán)，使得虛擬人按照局部規(guī)劃結(jié)果運(yùn)動。完成對當(dāng)前感知障礙的規(guī)避行為后，全局規(guī)劃器再次取得執(zhí)行系統(tǒng)的控制權(quán)，使得虛擬人重新回到全局規(guī)劃路徑上，繼續(xù)向目標(biāo)點(diǎn)運(yùn)動。參考
Dijkstra和A*算法做的效果演示動畫
A算法加入了啟發(fā)函數(shù)，用于引導(dǎo)其搜索方向,A算法會比Dijkstra算法規(guī)劃速度快不少。
最佳優(yōu)先搜索（BFS）算法
BFS按照類似的流程運(yùn)行，不同的是它能夠評估（稱為啟發(fā)式的）任意結(jié)點(diǎn)到目標(biāo)點(diǎn)的代價(jià)。與選擇離初始結(jié)點(diǎn)最近的結(jié)點(diǎn)不同的是，它選擇離目標(biāo)最近的結(jié)點(diǎn)。BFS不能保證找到一條最短路徑。然而，它比Dijkstra算法快的多，因?yàn)樗昧艘粋€啟發(fā)式函數(shù)（heuristic function）快速地導(dǎo)向目標(biāo)結(jié)點(diǎn)。例如，如果目標(biāo)位于出發(fā)點(diǎn)的南方，BFS將趨向于導(dǎo)向南方的路徑。在下面的圖中，越黃的結(jié)點(diǎn)代表越高的啟發(fā)式值（移動到目標(biāo)的代價(jià)高），而越黑的結(jié)點(diǎn)代表越低的啟發(fā)式值（移動到目標(biāo)的代價(jià)低）。這表明了與Dijkstra 算法相比，BFS運(yùn)行得更快。
A*算法結(jié)合了Dijkstra和BFS的各自的優(yōu)點(diǎn)，把Dijkstra算法（靠近初始點(diǎn)的結(jié)點(diǎn)）和BFS算法（靠近目標(biāo)點(diǎn)的結(jié)點(diǎn)）的信息塊結(jié)合起來。
隨機(jī)路圖法PRM
是基于圖搜索的方法，隨機(jī)路圖（Probabilistic Road Maps，PRM）就是在規(guī)劃空間內(nèi)隨機(jī)選取N個節(jié)點(diǎn)，之后連接各節(jié)點(diǎn)，并去除與障礙物接觸的連線，由此得到一個隨機(jī)路圖。
快速擴(kuò)展隨機(jī)樹法RRT
是基于樹狀結(jié)構(gòu)的搜索算法，RRT算法是從起始點(diǎn)開始向外拓展一個樹狀結(jié)構(gòu)，而樹狀結(jié)構(gòu)的拓展方向是通過在規(guī)劃空間內(nèi)隨機(jī)采點(diǎn)確定的。與PRM類似，該方法是概率完備且不最優(yōu)的。
快速擴(kuò)展隨機(jī)樹法RRT
是基于樹狀結(jié)構(gòu)的搜索算法，RRT算法是從起始點(diǎn)開始向外拓展一個樹狀結(jié)構(gòu)，而樹狀結(jié)構(gòu)的拓展方向是通過在規(guī)劃空間內(nèi)隨機(jī)采點(diǎn)確定的。與PRM類似，該方法是概率完備且不最優(yōu)的。
雖然基于采樣的規(guī)劃算法（如PRM和RRT）速度很快，但他們也有致命的缺點(diǎn)，那就是由隨機(jī)采樣引入的隨機(jī)性。利用RRT和PRM算法進(jìn)行運(yùn)動規(guī)劃，用戶無法對規(guī)劃結(jié)果進(jìn)行預(yù)判，每次規(guī)劃的結(jié)果都不一樣，這就使得自動規(guī)劃的機(jī)器人無法進(jìn)入工業(yè)領(lǐng)域（極端追求穩(wěn)定性）。
所以目前規(guī)劃領(lǐng)域也主要集中在對PRM和RRT的改進(jìn)上，大家都想要盡可能解決這類算法的不確定性，甚至能實(shí)現(xiàn)一些優(yōu)化目標(biāo)，如RRT，Informed-RRT，SBL等。
Introduction to Autonomous Mobile Robots 中關(guān)于路徑規(guī)劃的內(nèi)容
第一步將可能的連續(xù)的環(huán)境模型裝換成適應(yīng)于所選路徑規(guī)劃算法的離散圖，有三種通用的策略：道路圖、單位分解、勢場。
道路圖
-
可視性圖
由連接彼此可見的全部頂點(diǎn)對的連線組成，連接這些無阻擋的頂點(diǎn)即是它們之間 的最短距離。
該方法僅適用于稀疏目標(biāo)群，而且允許機(jī)器人盡可能的接近障礙物。 -
沃羅諾伊圖
相對于可視化圖，它傾向于使圖中機(jī)器人與障礙物之間的距離最大化。
它也會使環(huán)境中的機(jī)器人與物體之間的距離最大化，使得機(jī)器人上的短距離傳感器檢測不到可能存在的危險(xiǎn)。
單元分解路徑規(guī)劃
- 主要思想是區(qū)分幾何區(qū)（也叫單元）之間的區(qū)別，即把單元區(qū)分為自由的和被物體占用的區(qū)間。
- 主要分為精確單元分解和
-
精確單元分解：基于以下的思想：在自由空間的各單元中內(nèi)， 機(jī)器人的特殊位置不重要，重要的是機(jī)器人從各自由單元走向其相鄰自由單元的能力。
在大的稀疏環(huán)境中，單元的數(shù)目較少，實(shí)施效果挺有效。但是一旦單元數(shù)目巨大，實(shí)現(xiàn)的難度就會劇增。
- 近似單元分解
單元的尺寸不依賴于環(huán)境中的特殊物體，路徑規(guī)劃的計(jì)算復(fù)雜性低。是基于棧格的環(huán)境表示的普遍性。
勢場路徑規(guī)劃
主要思想：把機(jī)器人處理成人工勢場影響下的一個點(diǎn)，像球滾下山一樣，機(jī)器人跟隨著場移動。機(jī)器人被吸引向目標(biāo)，同時也被先前已知的障礙物所排斥。
如果障礙物新出現(xiàn)，應(yīng)該及時更新勢場。
擴(kuò)展勢場法
在基本勢場上，附加了兩個場：轉(zhuǎn)動勢場和任務(wù)勢場。
- 轉(zhuǎn)動勢場：當(dāng)障礙物與機(jī)器人行走的方向平行時，減小斥力，因?yàn)檫@樣的一個物體不會對機(jī)器人的軌跡造成及時的威脅。結(jié)果增強(qiáng)了沿墻跟蹤能力。
-
任務(wù)勢場：考慮了當(dāng)前機(jī)器人速度，排除了根據(jù)近期勢能對機(jī)器人速度無影響的障礙物。結(jié)果是穿過空間的軌跡更平滑。
