運(yùn)動規(guī)劃簡介
當(dāng)虛擬人開始一次漫游時(shí)弧轧，首先全局規(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)的物體或未知障礙時(shí)，局部規(guī)劃器根據(jù)這些感知到的局部信息晃择，確定短期內(nèi)的運(yùn)動冀值。當(dāng)避障行為的優(yōu)先級高于沿原路徑前進(jìn)時(shí)，局部規(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)樗昧艘粋€(gè)啟發(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個(gè)節(jié)點(diǎn)恋脚，之后連接各節(jié)點(diǎn)，并去除與障礙物接觸的連線钙态，由此得到一個(gè)隨機(jī)路圖慧起。
快速擴(kuò)展隨機(jī)樹法RRT
是基于樹狀結(jié)構(gòu)的搜索算法崇呵，RRT算法是從起始點(diǎn)開始向外拓展一個(gè)樹狀結(jié)構(gòu)缤剧，而樹狀結(jié)構(gòu)的拓展方向是通過在規(guī)劃空間內(nèi)隨機(jī)采點(diǎn)確定的。與PRM類似域慷，該方法是概率完備且不最優(yōu)的荒辕。
快速擴(kuò)展隨機(jī)樹法RRT
是基于樹狀結(jié)構(gòu)的搜索算法汗销，RRT算法是從起始點(diǎn)開始向外拓展一個(gè)樹狀結(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ī)器人處理成人工勢場影響下的一個(gè)點(diǎn)推穷，像球滾下山一樣，機(jī)器人跟隨著場移動类咧。機(jī)器人被吸引向目標(biāo)，同時(shí)也被先前已知的障礙物所排斥蟹腾。
如果障礙物新出現(xiàn)痕惋，應(yīng)該及時(shí)更新勢場。
擴(kuò)展勢場法
在基本勢場上值戳，附加了兩個(gè)場：轉(zhuǎn)動勢場和任務(wù)勢場。
- 轉(zhuǎn)動勢場：當(dāng)障礙物與機(jī)器人行走的方向平行時(shí)炉爆，減小斥力堕虹，因?yàn)檫@樣的一個(gè)物體不會對機(jī)器人的軌跡造成及時(shí)的威脅。結(jié)果增強(qiáng)了沿墻跟蹤能力芬首。
-
任務(wù)勢場：考慮了當(dāng)前機(jī)器人速度赴捞，排除了根據(jù)近期勢能對機(jī)器人速度無影響的障礙物。結(jié)果是穿過空間的軌跡更平滑郁稍。
