化工儀器網(wǎng)
技術文章
移動機器人導航路徑規(guī)劃
閱讀：2138 發(fā)布時間：2019-8-13*,，移動機器人是工廠物料運輸?shù)慕鉀Q方案,，是提高生產(chǎn)效率,，降低生產(chǎn)成本，增強生產(chǎn)穩(wěn)定性的*,。為了滿足工業(yè)生產(chǎn)需求,，一款的移動機器人產(chǎn)品首先需要解決三大問題：
小藍（杭州藍芯科技有限公司簡稱）就是專業(yè)解決導航規(guī)劃問題滴，接下來就和大家好好嘮嘮怎么實現(xiàn)一次走位,。
軌跡計劃
世界上遙遠的距離不是生與死,，而是明明出口就在眼前，而我卻要去遠遠的兜一圈才能到,。移動機器人在面對復(luan)雜(dui)環(huán)(luan)境(fang)時,，也需要完成走迷宮般的絕望任務。
圖 1
為了應付復雜的人類以及胖胖的自己,，我們機智的機器人,，擁有了自己的軌跡規(guī)劃方法。那就是把你們變胖,，把自己變瘦（美麗）,！于是提出了兩個重要假設（敲黑板）：
機器人是一個點，障礙物按機器人半徑進行膨脹,；
機器人是完整的,，忽略非完整約束對姿態(tài)的限制；
于是,，工作空間就的降為了二維物理空間（姿態(tài)空間）,，如圖2
圖 2
于是路徑規(guī)劃問題就變成了姿態(tài)空間的搜索問題：在自由姿態(tài)空間中為機器人尋找一條路徑,，使其從初始姿態(tài)發(fā)展到目標姿態(tài)。將姿態(tài)空間離散化以后,，就能進行啦,。
快速擴展隨機樹法（RRT）
快速擴展隨機樹法可以看作一種樹形算法，它從一個起始構型（對于二維圖,，就是一個點）出發(fā),，不斷延伸樹型數(shù)據(jù),，終與目標點相連,。具體做法就是以一個初始點作為根節(jié)點，通過隨機采樣增加葉子節(jié)點的方式,，生成一個隨機擴展樹,，當隨機樹中的葉子節(jié)點包含了目標點或進入了目標區(qū)域，便可以在隨機樹中找到一條由從初始點到目標點的路徑,。
圖 3
RRT算法也有一些缺點,，它是一種純粹的隨機搜索算法對環(huán)境類型不敏感，當C-空間中包含大量障礙物或狹窄通道約束時,，算法的收斂速度慢,，效率會大幅下降。同時,，RRT 的一個弱點是難以在有狹窄通道的環(huán)境找到路徑,。因為狹窄通道面積小，被碰到的概率低,。
因此有學者提出了RRTConnect算法,，基本的RRT每次搜索都只有從初始狀態(tài)點生長的快速擴展隨機樹來搜索整個狀態(tài)空間，如果從初始狀態(tài)點和目標狀態(tài)點同時生長兩棵快速擴展隨機樹來搜索狀態(tài)空間,，效率會更高,。
該算法與原始RRT相比，在目標點區(qū)域建立第二棵樹進行擴展,。每一次迭代中,，開始步驟與原始的RRT算法一樣，都是采樣隨機點然后進行擴展,。然后擴展完棵樹的新節(jié)點qnew后,，以這個新的目標點作為第二棵樹擴展的方向。
圖 4
這種雙向的RRT技術具有良好的搜索特性,，比原始RRT算法的搜索速度,、搜索效率有了顯著提高，被廣泛應用,。首先,，Connect算法較之前的算法在擴展的步長上更長,，使得樹的生長更快；其次,，兩棵樹不斷朝向對方交替擴展,，而不是采用隨機擴展的方式，特別當起始位姿和目標位姿處于約束區(qū)域時,，兩棵樹可以通過朝向對方快速擴展而逃離各自的約束區(qū)域,。這種帶有啟發(fā)性的擴展使得樹的擴展更加貪婪和明確，使得雙樹RRT算法較之單樹RRT算法更加有效,。
單元分解法
單元分解法的基本思想是將姿態(tài)空間中的自由空間分隔成幾個小區(qū)域,，將每個區(qū)域當成一個單元。以單元為頂點,，以單元之間的相鄰關系為邊構成一張連通圖,。然后在連通圖中搜索初始姿態(tài)和目標姿態(tài)所在的單元，然后搜索連接初始單元和目標單元的路徑,。后就能按照所得路徑的單元序列生成單元內(nèi)部的路徑了,。
圖 5
單元分解法的有點在于，機器人不需要考慮它在每個空閑單元中的具體位置,，只需要考慮如何從一個單元移動到相鄰的空閑單元,，同時單元數(shù)和環(huán)境大小無關。
但是計算效率會極大地依賴于環(huán)境中的物體的復雜度,，為了解決這方面的問題,，又提出了新的單元分解法，也就是柵格表示法：將環(huán)境分解成若干個大小相同的柵格,。這樣其實就是對地圖的一種近似,，就不用考慮環(huán)境的疏密和物體形狀的復雜度。
圖 6
人工勢場法
人工勢場法利用磁場的特性來解決路徑規(guī)劃的問題,。假設目標點對機器人產(chǎn)生吸引力,，障礙物對機器人產(chǎn)生排斥力。這樣就能根據(jù)力的合成構成機器人的控制方法了,。
圖 7
引力場（attraction）隨機器人與目標點的距離增加而單調(diào)遞增,，且方向指向目標點；斥力場（repulsion）在機器人處在障礙物位置時有一極大值,，并隨機器人與障礙物距離的增大而單調(diào)減小,，方向指向遠離障礙物方向。如圖8就是引力場和斥力場同時作用下的勢場圖,。
圖 8
人工勢場法通過構建人工勢場,，進行勢場力計算，受力分析進而計算合力,，得到終加速度,。
圖 9
人工勢場法結構簡單,，便于底層的實時控制，在實時避障和平滑的軌跡控制方面得到廣泛的應用,。但是由于斥力作用范圍較小的問題,，勢場法只能解決局部空間的避障問題，它缺乏全局信息,，這樣,，它就很容易陷入局部小值。當機器人位于局部小點的時候,，機器人容易產(chǎn)生振蕩或者停滯不前,。障礙物越多，產(chǎn)生局部小點的可能性就越大,，產(chǎn)生局部小點的數(shù)量也就越多,，這是具體實現(xiàn)過程中需要注意的。
通過上述介紹,，想必大家存在一個疑惑，構建了很多單元和路徑（拓撲圖）,，那么如何去搜索路徑呢,，又怎么去判斷哪條路徑更加呢。下期論點,，讓我們討論路徑規(guī)劃算法中的路徑所搜法,，一起學習A*算法，遺傳算法以及粒子濾波算法是如何為我們服務的,。