基于A*算法的機器人路徑規劃與避障研究

張益輝 王長寧 孫玲

摘 要： 針對當前智能機器人應用中傳統人工勢場法路徑規劃存在的問題，對傳統人工勢場法進行改進，同時引入A*算法進行全局路徑優化。具體則是在傳統人工勢場法中，對斥力函數進行改進，同時建立虛擬目標牽引點，以改進局部極小值和目標不可達的問題;在全局路徑規劃方面，引入A*算法，通過改進A*算法中的估計函數，以解決啟發函數信息太弱或太強的問題。最后在Mat-lab2012b對上述混合算法進行編程，得到不同方法下的仿真結果。結果表明，本文構建的改機算法可有效到達終點，并且曲線光滑、平穩。

關鍵詞： A*算法; 人工勢場法; 路徑規劃; 避障; 仿真實驗

中圖分類號： TP311 ? ? ?文獻標志碼： A

Research on Robot Path Planning and Obstacle

Avoidance Based on A* Algorithms

Shi Yu， Li Chunkai

（）

Abstract： Aiming at the problems existing in the path planning of traditional artificial potential field method in the current application of intelligent robots， the A* algorithm is introduced to optimize the global path while improving the traditional artificial potential field method. Specifically， in the traditional artificial potential field method， the repulsion function is improved， and the virtual target traction point is established to improve the local minimum and target unreachability. In the aspect of global path planning， the A* algorithm is introduced to solve the problem that the information of heuristic function is too weak or too strong by improving the estimation function of A* algorithm. Finally， the hybrid algorithm is programmed in Matlab 2012 b， and the simulation results under different methods are obtained. The results show that the improved algorithm constructed in this paper can reach the end point effectively， and the curve is smooth and stable.

Key words： A* algorithm; Artificial potential field method; Path planning; Obstacle avoidance; Simulation experiment

0 引言

隨著現代信息技術的進步，機器人開始逐步走向舞臺，成為人們生活和工作中不可或缺的一部分。在機器人應用過程中，路徑規劃一直以來是研究的重點，也是機器人能夠自主完成任務的基本保障。所謂的路徑規劃，其本質就是在眾多的障礙物環境中找到一條無碰撞的路徑。目前，學術上針對機器人路徑的規劃中，看可以分為局部路徑規劃和全局路徑規劃。其中人工勢場法是常用的一種局部路徑規劃方法，但是人工勢場法很容易陷入目標不可達和局部極小值的問題。由此，在人工勢場法的基礎上，人們主要從兩方面進行改進：一是對人工勢場法本身存在的缺陷進行改進，如在傳統人工勢場法的基礎上，加入加速度場和速度場;二是引入全局路徑規劃算法，比較典型的就是A*算法、粒子群算法等。如許源（2014）在人工勢場法的基礎上，引入粒子群算法，最后通過實物仿真，驗證上述方法的可行性。本文則在上述研究上，在傳統人工勢場法基礎上，提出人工勢場法與A*算法結合的機器人路徑規劃算法，并對其進行驗證。

1 本文研究思路

結合機器人路徑規劃與避障相關理論，本文將研究的思路設計為如圖1所示。

2 移動機器人柵格空間建模

2.1 柵格粒度的確定

在開展柵格建圖工作時，單位柵格尺寸的劃分將會對地圖的精度值造成影響。單位柵格尺寸劃分越細，地圖的信息量也就越大，精確度也就越高，但這種劃分方式會增加地圖干擾項。單位柵格尺寸劃分越大，系統實時性將會有所提高，地圖干擾項也會隨之減少，但這種劃分方式的缺點在于存儲信息量較少，無法在障礙物密集環境下對有效路徑進行規劃。因此在研究中，引入柵格粒度來對障礙物的稀疏程度進行描述，具體數值需對障礙物區域面積以及環境計算而獲取。但是在計算中，會面對不同類型的圖形，如凸形、橢圓形等。若障礙物外形為凸型，可將該障礙物拆分為三角形進行計算;若障礙物為類似橢圓形，則按照矩形進行計算。在獲取到柵格的粒度之后，需將各粒度與機器人自身尺寸進行對比，選取比機器人尺寸更大的粒度，目的是使機器人在運動過程中保持暢通。具體粒度獲取步驟如下：

（1） 獲取地圖中的一個障礙物，并對該障礙物外形進行判斷;

（2） 若障礙物外形為凸型，則從障礙物某頂點開始，將其拆分為多個不相交的三角形進行計算;

（3） 若障礙物外形非凸型，則對障礙物所有頂點中坐標系下最大值與最小值xmax、ymax、xmin、ymin，再以（xmin，ymin）以及（xmax，ymax）為對角定點，以此構建起一個矩形，再將矩形分割為兩個不相交三角形進行計算;

（4） 通過公式s=12×a×b×sin α對各三角形面積進行計算。在該公式中，a，b為三角形定點的兩個邊;α為a，b的夾角;

（5） 觀察地圖上是否還存在其他障礙物，若存在則返回步驟（1）;

（6） 對上述障礙物面積的和進行計算，計算公式為Stotal=∑p∈ΩSp，Ω代表所有障礙物的集合;p代表Ω當中的某一障礙物元素;

（7） 對柵格粒度進行計算，計算式為式（1）。dt=StotalSenv×dmax

（1） ?以此得到式（2）。d=dt，if dt>dmin

dmin，其他

（2） ?在步驟（7）的公式中，senv代表環境面積;dmax代表被定義的柵格最大邊長;dmin代表構造的柵格最小邊長，dmin需大于機器人自身尺寸;d代表最終柵格邊長。

2.2 柵格空間的表示

拋開機器人高度信息不計，僅對規劃環境為平面情況進行考慮。若環境空間為W，W中的x軸位于水平方向向右位置;y軸為豎直方向向上位置，以此可構建起直角坐標系∑。假設X軸與Y軸的最大值分別為Xmax以及Ymax。假設柵格粒度為d，那么每行柵格數為Nx=Xmax/d;每列柵格數為Ny=Ymax/d。若地圖中某柵格尺寸范圍內并不具備任何障礙物，那么該柵格則為自由柵格，在地圖中用白色進行表示;反之，該柵格則為障礙柵格，在地圖中用黑色進行表示。當Xmax=Ymax=10，d=1時，機器人柵格工作空間如圖2所示。

實際建模過程中，會碰到形狀多樣的障礙物。在此情況下，通常對柵格地圖中不規則障礙物進行膨化處理，使原本占據不規則柵格的障礙物變為形狀規矩的占據柵格。

2.3 柵格編碼

柵格編碼是路徑搜索的重要部分，對路徑搜索的效率有著直接的影響。傳統的路徑規劃中，是通過行或者列進行搜索，最后連接確定的柵格，從而構成一條路徑。但是這種搜索存在很大的弊端，一旦遇到復雜環境，則不能得到有效路徑。因此，在本文中提出一種改進二維編碼方法，主要思路是把障礙物的頂點信息作為關鍵點，然后將這些關鍵點按照一定的規則來進行編號，最后設計編碼串。而編碼串的長度是關鍵點的數量和。在編碼串中，非0位不能復位，如圖3所示。

如圖3中的A障礙物為例，A的頂點坐標為（0，3）、（0，4）、（2，2）、（1，2）、（2，3）、（1，3）、（2，4）、（1，4）。去掉可能會引起碰撞的點，得到關鍵信息點為（1，2）、（2，2）、（1，3）、（2，4）四個點。以此類推，得到A、B、C三點的關鍵信息點。構建關鍵點的集合。同時假設編碼串為[0，0，3，0，0，0，9，0，10，0，0，0，0，0]，那么機器人的通過坐標則為（2，2）、（4，4）、（4，5）。

3 機器人局部路徑規劃

3.1 傳統人工勢場法

傳統人工勢場法主要通過合力來實現對機器人前進方向的控制，具體如圖4所示。

機器人在越靠近目標點時，其所受到的合力也將隨之減小。當機器人到達目標點時，機器人所受的合力為最小。

但通過圖4看出，機器人在運行至某一些點而并非目標點時，其所受的合力同樣可以為零。當機器人受到的合力為零時，機器人將在該點上停留，不再向目標點進行移動。這些合力為零的點，被稱為人工勢場法的局部極小值點。同時，在機器人運行過程中，若目標點位于障礙物影響范圍內，那么機器人在運行過程中的引力將減少、斥力將增大。當機器人到達某一點時，機器人將由于引力的減少而不再前進，而是以來回運動的方式在該點中進行移動。這種情況稱作為人工勢場法的目標不可達問題。

3.2 人工勢場法改進

以上分析看出，傳統人工勢場法存在局部極小點與目標不可達兩大問題。對此，本文根據傳統人工勢場法的特性，采用改進斥力函數對傳統人工勢場法目標不可達問題進行改進。具體改進后的斥力勢場函數表達式為式（3）U2（x）=12m（1ρ-1ρ0）2（x-xg）n，ρ≤ρ0

0，ρ>ρ0

（3） ?在公式（1）中，m代表大于零的斥力場系數常量;ρ0代表障礙物最大影響范圍;ρ代表機器人與障礙物的最短距離;x代表機器人當前位置坐標;xg代表目標點位置坐標，則斥力表達式為式（4）～式（6）。F2（x）=- Δ （U2（x））=F11+F12，ρ≤ρ0

0，ρ>ρ0

（4）其中，F11=m（1ρ-1ρ0）1ρ2·（x-xg）nρx

（5）

F12=12mn（1ρ-1ρ0）2·（x-xg）n-1·（x-xg）x

（6） ?經過改進之后，斥力函數將機器人受到的障礙物斥力劃分為兩部分：一部分斥力主要通過障礙物連線向機器人發起影響，如公式（3）所示;另一部分斥力主要通過機器人與目標點之間的連線，由機器人指向目標點，如公式（4）所示。在實際應用過程中，主要采用公式（3）與公式（4）的簡化形式，具體為式（7）F11=m（1ρ-1ρ0）2·（x-xg）n

F12=12mn（1ρ-1ρ0）2·（x-xg）n-1

（7） ?而對于人工勢場法局部極小點問題，本文通過在極小點附近建立虛擬目標牽引點的方式，來對傳統人工勢場法局部極小點問題進行改進。改進后分為兩個部分：極小值點的檢測以及自主虛擬目標牽引點的建立、對原有目標點的隔離。

虛擬目標牽引點設置方法為：

假設（x1，y1）為機器人當前位置坐標;（c1，c2）為機器人受最大斥力的障礙物位置坐標;（x，y）為設置的虛擬目標牽引點位置坐標;d為可選常數，由此構建方程為式（8）、式（9）。y-y1=-c1-x1c2-y1（x-x1）

（8）

（x-x1）2+（y-y1）2=d2

（9） ?聯立公式（6）與公式（7）可得出解為式（10）。x=x1±d（c2-y1）（c1-x1）2+（c2-y1）2

y=y1±d（c1-x1）（c1-x1）2+（c2-y1）2

（10）4 基于人工勢場法的機器人避障改進

在采用人工勢場法對局部路徑進行改進時，要想得到最優的路徑，還需要對路徑進行全局規劃。傳統的全局算法中，包括粒子群算法、A*算法等。本文則采用A*算法對機器人全局路徑進行優化改進。

4.1 A*算法原理

A*算法屬于啟發式搜索算法的一種，在應用過程中主要通過啟發函數來對平面上任意位置與目標位置之間的距離進行評價，再借助啟發函數對最優方向開始搜索，以此找出最優方向。A*算法憑借自己具備的函數表達簡單、編程易實現等優勢，使其成為當前人工智能領域中廣泛使用的算法之一。A*算法基本啟發函數表達公式為：f（n）=g（n）+h（n）

（11） ?在公式（9）中，f（n）代表地圖中節點n的總代價函數;g（n）主要是對機器人由最初狀態節點至節點n之間實際代價值大小進行表示;h（n）代表機器人由節點n到最終目標點對應節點最小估計代價值大小。

4.2 A*算法改進

在實際應用中發現，A*算法雖然能夠有效降低節點拓展范圍，以及整體計算難度，但啟發信息的增加程度給搜索結果造成很大的影響。若搜索過程的啟發信息增加過強，將會使搜索路徑的最優性無法得以保障;若啟發信息太弱，又會給路徑搜索工作量造成影響，使工作量在原基礎上得以增長，計算的復雜度也將提高。對此，在本文中引入權重的方式，來彌補啟發信息過強或過弱帶來的影響。具體則是對（9）進行改進，利用加權思想改進估價函數，具體數學表達式為：f（n）=（1-w）g（n）+wh（n）

（12）5 混合算法流程設計

結合上述的改進，提出基于全局路徑規劃與局部路徑規劃的避障算法，具體避障流程如圖5所示。

6 仿真實驗驗證

考慮到改進算法的有效性，本文將在Mat-lab2012b平臺上對該算法開展仿真實驗。在開展仿真實驗過程中，本文將采用柵格法來對靜態室內環境模型進行構建，以二維平面來表示室內環境，通過直角坐標法對地圖進行表示，以此構成其整個相對應的仿真路徑規劃環境。通過仿真，得到圖6和圖7的結果。

通過觀察圖6及圖7顯示內容可知，在單獨使用人工勢場法的情況下，存在無法有效繞開U型障礙物這一問題，并且在機器人在運行過程中在通過走廊時的軌跡較為曲折，此情況從圖5中的AB段可以看出。然而，通過對本文混合路徑規劃算法的使用，能夠借助全局路徑規劃找出子目標點，并以此對機器人進行引導，使機器人具備繞過U型障礙物的能力，從而順利到達目標點。同時，通過雙層路徑規劃算法的應用，還能夠使機器人在行走至狹窄的走廊路徑時，保持平滑、筆直的運行軌跡，說明本文構建的算法具有一定的可行性。

7 總結

通過上述的改進可以看出，在對移動機器人進行路徑規劃中，采用單一的路徑規劃方法往往得不到最佳路徑，同時也起不到有效避障的效果。因此，在實際應用中，往往采用混合算法，從全局和局部的角度進行綜合路徑規劃，以此改變以往路徑規劃的弊端。

參考文獻

[1] 李陽，盧健，何耀幀. 基于ROS系統自主路徑規劃與避障小車的研究[J]. 科技風，2018（4）：248.

[2] 陳峰，趙萍. 休閑園林割草機器人設計及性能測試[J]. 農機化研究，2018，40（10）：82-85.

[3] 張曉玲，王正存，吳作君. 基于改進蟻群算法的機器人路徑規劃[J]. 中國石油大學勝利學院學報，2018，32（2）：44-47.

[4] 晉曉飛，王浩，宗衛佳，等. 自主移動機器人避障技術研究現狀[J]. 傳感器與微系統，2018，37（5）：5-9.

[5] 秦承志，呼雪梅. 柵格數字地形分析中的尺度問題研究方法[J]. 地理研究，2014，33（2）：270-283.

[6] 方嘯，鄭德忠. 移動機器人自主尋路避障啟發式動態規劃算法[J]. 農業機械學報，2014，45（7）：73-78.

[7] 王哲，孫樹棟，曹飛祥. 動態環境下移動機器人路徑規劃的改進蟻群算法[J]. 機械科學與技術，2013，32（1）：42-46.

[8] 鄒益民，高陽，高碧悅. 一種基于Dijkstra算法的機器人避障問題路徑規劃[J]. 數學的實踐與認識，2013，43（10）：111-118.

[9] 余翀，邱其文. 基于柵格地圖的分層式機器人路徑規劃算法[J]. 中國科學院大學學報，2013，30（4）：528-538.

[10] 翟紅生，王佳欣. 基于人工勢場的機器人動態路徑規劃新方法[J]. 重慶郵電大學學報（自然科學版），2015，27（6）：814-818.

[11] 余勇. 基于改進蟻群算法的移動機器人路徑規劃研究[J]. 機械傳動，2016，40（7）：58-61.

[12] 賈慶軒，陳鋼，孫漢旭，等. 基于A～*算法的空間機械臂避障路徑規劃[J]. 機械工程學報，2010，46（13）：109-115.

[13] 陳雄，趙一路，韓建達. 一種改進的機器人路徑規劃的蟻群算法[J]. 控制理論與應用，2010，27（6）：821-825.

[14] 張紫輝，熊岳山. 未知環境下基于A～*的機器人路徑規劃算法[J]. 計算機工程與科學，2012，34（11）：141-147.

[15] 左大利，聶清彬，張莉萍，等. 移動機器人路徑規劃中的蟻群優化算法研究[J]. 現代制造工程，2017（5）：44-48.

[16] 張彪，曹其新，王雯珊. 使用三維柵格地圖的移動機器人路徑規劃[J]. 西安交通大學學報，2013，47（10）：57-61.

（收稿日期： 2018.12.10）

作者簡介：張益輝（1972-），男，本科，高級工程師，研究方向：智能巡檢機器人、電力信息化。

王長寧（1982-），男，碩士，工程師，研究方向：智能巡檢機器人、電力信息化。

孫玲（1977-），女，碩士，高級工程師，研究方向：智能巡檢機器人、電力信息化。文章編號：1007-757X（2020）02-0120-04