移動(dòng)機器人導航路徑規劃

*，移動(dòng)機器人是工廠(chǎng)物料運輸的解決方案，是提高生產(chǎn)效率，降低生產(chǎn)成本，增強生產(chǎn)穩定性的*。為了滿(mǎn)足工業(yè)生產(chǎn)需求，一款的移動(dòng)機器人產(chǎn)品首先需要解決三大問(wèn)題：

小藍（杭州藍芯科技有限公司簡(jiǎn)稱(chēng)）就是專(zhuān)業(yè)解決導航規劃問(wèn)題滴，接下來(lái)就和大家好好嘮嘮怎么實(shí)現一次走位。

軌跡計劃

世界上遙遠的距離不是生與死，而是明明出口就在眼前，而我卻要去遠遠的兜一圈才能到。移動(dòng)機器人在面對復(luan)雜(dui)環(huán)(luan)境(fang)時(shí)，也需要完成走迷宮般的絕望任務(wù)。

圖 1

為了應付復雜的人類(lèi)以及胖胖的自己，我們機智的機器人，擁有了自己的軌跡規劃方法。那就是把你們變胖，把自己變瘦（美麗）！于是提出了兩個(gè)重要假設（敲黑板）：
機器人是一個(gè)點(diǎn)，障礙物按機器人半徑進(jìn)行膨脹；
機器人是完整的，忽略非完整約束對姿態(tài)的限制；
于是，工作空間就的降為了二維物理空間（姿態(tài)空間），如圖2

圖 2

于是路徑規劃問(wèn)題就變成了姿態(tài)空間的搜索問(wèn)題：在自由姿態(tài)空間中為機器人尋找一條路徑，使其從初始姿態(tài)發(fā)展到目標姿態(tài)。將姿態(tài)空間離散化以后，就能進(jìn)行啦。

快速擴展隨機樹(shù)法（RRT）

快速擴展隨機樹(shù)法可以看作一種樹(shù)形算法，它從一個(gè)起始構型（對于二維圖，就是一個(gè)點(diǎn)）出發(fā)，不斷延伸樹(shù)型數據，終與目標點(diǎn)相連。具體做法就是以一個(gè)初始點(diǎn)作為根節點(diǎn)，通過(guò)隨機采樣增加葉子節點(diǎn)的方式，生成一個(gè)隨機擴展樹(shù)，當隨機樹(shù)中的葉子節點(diǎn)包含了目標點(diǎn)或進(jìn)入了目標區域，便可以在隨機樹(shù)中找到一條由從初始點(diǎn)到目標點(diǎn)的路徑。

圖 3

RRT算法也有一些缺點(diǎn)，它是一種純粹的隨機搜索算法對環(huán)境類(lèi)型不敏感，當C-空間中包含大量障礙物或狹窄通道約束時(shí)，算法的收斂速度慢，效率會(huì )大幅下降。同時(shí)，RRT 的一個(gè)弱點(diǎn)是難以在有狹窄通道的環(huán)境找到路徑。因為狹窄通道面積小，被碰到的概率低。

因此有學(xué)者提出了RRTConnect算法，基本的RRT每次搜索都只有從初始狀態(tài)點(diǎn)生長(cháng)的快速擴展隨機樹(shù)來(lái)搜索整個(gè)狀態(tài)空間，如果從初始狀態(tài)點(diǎn)和目標狀態(tài)點(diǎn)同時(shí)生長(cháng)兩棵快速擴展隨機樹(shù)來(lái)搜索狀態(tài)空間，效率會(huì )更高。

該算法與原始RRT相比，在目標點(diǎn)區域建立第二棵樹(shù)進(jìn)行擴展。每一次迭代中，開(kāi)始步驟與原始的RRT算法一樣，都是采樣隨機點(diǎn)然后進(jìn)行擴展。然后擴展完棵樹(shù)的新節點(diǎn)qnew后，以這個(gè)新的目標點(diǎn)作為第二棵樹(shù)擴展的方向。

圖 4

這種雙向的RRT技術(shù)具有良好的搜索特性，比原始RRT算法的搜索速度、搜索效率有了顯著(zhù)提高，被廣泛應用。首先，Connect算法較之前的算法在擴展的步長(cháng)上更長(cháng)，使得樹(shù)的生長(cháng)更快；其次，兩棵樹(shù)不斷朝向對方交替擴展，而不是采用隨機擴展的方式，特別當起始位姿和目標位姿處于約束區域時(shí)，兩棵樹(shù)可以通過(guò)朝向對方快速擴展而逃離各自的約束區域。這種帶有啟發(fā)性的擴展使得樹(shù)的擴展更加貪婪和明確，使得雙樹(shù)RRT算法較之單樹(shù)RRT算法更加有效。

單元分解法

單元分解法的基本思想是將姿態(tài)空間中的自由空間分隔成幾個(gè)小區域，將每個(gè)區域當成一個(gè)單元。以單元為頂點(diǎn)，以單元之間的相鄰關(guān)系為邊構成一張連通圖。然后在連通圖中搜索初始姿態(tài)和目標姿態(tài)所在的單元，然后搜索連接初始單元和目標單元的路徑。后就能按照所得路徑的單元序列生成單元內部的路徑了。

圖 5

單元分解法的有點(diǎn)在于，機器人不需要考慮它在每個(gè)空閑單元中的具體位置，只需要考慮如何從一個(gè)單元移動(dòng)到相鄰的空閑單元，同時(shí)單元數和環(huán)境大小無(wú)關(guān)。

但是計算效率會(huì )極大地依賴(lài)于環(huán)境中的物體的復雜度，為了解決這方面的問(wèn)題，又提出了新的單元分解法，也就是柵格表示法：將環(huán)境分解成若干個(gè)大小相同的柵格。這樣其實(shí)就是對地圖的一種近似，就不用考慮環(huán)境的疏密和物體形狀的復雜度。

圖 6

人工勢場(chǎng)法

人工勢場(chǎng)法利用磁場(chǎng)的特性來(lái)解決路徑規劃的問(wèn)題。假設目標點(diǎn)對機器人產(chǎn)生吸引力，障礙物對機器人產(chǎn)生排斥力。這樣就能根據力的合成構成機器人的控制方法了。

圖 7

引力場(chǎng)（attraction）隨機器人與目標點(diǎn)的距離增加而單調遞增，且方向指向目標點(diǎn)；斥力場(chǎng)（repulsion）在機器人處在障礙物位置時(shí)有一極大值，并隨機器人與障礙物距離的增大而單調減小，方向指向遠離障礙物方向。如圖8就是引力場(chǎng)和斥力場(chǎng)同時(shí)作用下的勢場(chǎng)圖。

圖 8

人工勢場(chǎng)法通過(guò)構建人工勢場(chǎng)，進(jìn)行勢場(chǎng)力計算，受力分析進(jìn)而計算合力，得到終加速度。

圖 9

人工勢場(chǎng)法結構簡(jiǎn)單，便于底層的實(shí)時(shí)控制，在實(shí)時(shí)避障和平滑的軌跡控制方面得到廣泛的應用。但是由于斥力作用范圍較小的問(wèn)題，勢場(chǎng)法只能解決局部空間的避障問(wèn)題，它缺乏全局信息，這樣，它就很容易陷入局部小值。當機器人位于局部小點(diǎn)的時(shí)候，機器人容易產(chǎn)生振蕩或者停滯不前。障礙物越多，產(chǎn)生局部小點(diǎn)的可能性就越大，產(chǎn)生局部小點(diǎn)的數量也就越多，這是具體實(shí)現過(guò)程中需要注意的。

通過(guò)上述介紹，想必大家存在一個(gè)疑惑，構建了很多單元和路徑（拓撲圖），那么如何去搜索路徑呢，又怎么去判斷哪條路徑更加呢。下期論點(diǎn)，讓我們討論路徑規劃算法中的路徑所搜法，一起學(xué)習A*算法，遺傳算法以及粒子濾波算法是如何為我們服務(wù)的。