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

張益輝 王長寧 孫玲

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

關(guān)鍵詞： A*算法; 人工勢場法; 路徑規(guī)劃; 避障; 仿真實驗

中圖分類號： TP311 ? ? ?文獻(xiàn)標(biāo)志碼： 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 引言

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

1 本文研究思路

結(jié)合機器人路徑規(guī)劃與避障相關(guān)理論，本文將研究的思路設(shè)計為如圖1所示。

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

2.1 柵格粒度的確定

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

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

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

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

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

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

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

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

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

dmin，其他

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

2.2 柵格空間的表示

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

實際建模過程中，會碰到形狀多樣的障礙物。在此情況下，通常對柵格地圖中不規(guī)則障礙物進(jìn)行膨化處理，使原本占據(jù)不規(guī)則柵格的障礙物變?yōu)樾螤钜?guī)矩的占據(jù)柵格。

2.3 柵格編碼

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

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

3 機器人局部路徑規(guī)劃

3.1 傳統(tǒng)人工勢場法

傳統(tǒng)人工勢場法主要通過合力來實現(xiàn)對機器人前進(jìn)方向的控制，具體如圖4所示。

機器人在越靠近目標(biāo)點時，其所受到的合力也將隨之減小。當(dāng)機器人到達(dá)目標(biāo)點時，機器人所受的合力為最小。

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

3.2 人工勢場法改進(jìn)

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

0，ρ>ρ0

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

0，ρ>ρ0

（4）其中，F(xiàn)11=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） ?經(jīng)過改進(jìn)之后，斥力函數(shù)將機器人受到的障礙物斥力劃分為兩部分：一部分斥力主要通過障礙物連線向機器人發(fā)起影響，如公式（3）所示;另一部分斥力主要通過機器人與目標(biāo)點之間的連線，由機器人指向目標(biāo)點，如公式（4）所示。在實際應(yīng)用過程中，主要采用公式（3）與公式（4）的簡化形式，具體為式（7）F11=m（1ρ-1ρ0）2·（x-xg）n

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

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

虛擬目標(biāo)牽引點設(shè)置方法為：

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

（8）

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

（9） ?聯(lián)立公式（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 基于人工勢場法的機器人避障改進(jìn)

在采用人工勢場法對局部路徑進(jìn)行改進(jìn)時，要想得到最優(yōu)的路徑，還需要對路徑進(jìn)行全局規(guī)劃。傳統(tǒng)的全局算法中，包括粒子群算法、A*算法等。本文則采用A*算法對機器人全局路徑進(jìn)行優(yōu)化改進(jìn)。

4.1 A*算法原理

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

（11） ?在公式（9）中，f（n）代表地圖中節(jié)點n的總代價函數(shù);g（n）主要是對機器人由最初狀態(tài)節(jié)點至節(jié)點n之間實際代價值大小進(jìn)行表示;h（n）代表機器人由節(jié)點n到最終目標(biāo)點對應(yīng)節(jié)點最小估計代價值大小。

4.2 A*算法改進(jìn)

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

（12）5 混合算法流程設(shè)計

結(jié)合上述的改進(jìn)，提出基于全局路徑規(guī)劃與局部路徑規(guī)劃的避障算法，具體避障流程如圖5所示。

6 仿真實驗驗證

考慮到改進(jìn)算法的有效性，本文將在Mat-lab2012b平臺上對該算法開展仿真實驗。在開展仿真實驗過程中，本文將采用柵格法來對靜態(tài)室內(nèi)環(huán)境模型進(jìn)行構(gòu)建，以二維平面來表示室內(nèi)環(huán)境，通過直角坐標(biāo)法對地圖進(jìn)行表示，以此構(gòu)成其整個相對應(yīng)的仿真路徑規(guī)劃環(huán)境。通過仿真，得到圖6和圖7的結(jié)果。

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

7 總結(jié)

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

參考文獻(xiàn)

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

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

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

[4] 晉曉飛，王浩，宗衛(wèi)佳，等. 自主移動機器人避障技術(shù)研究現(xiàn)狀[J]. 傳感器與微系統(tǒng)，2018，37（5）：5-9.

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

[6] 方嘯，鄭德忠. 移動機器人自主尋路避障啟發(fā)式動態(tài)規(guī)劃算法[J]. 農(nóng)業(yè)機械學(xué)報，2014，45（7）：73-78.

[7] 王哲，孫樹棟，曹飛祥. 動態(tài)環(huán)境下移動機器人路徑規(guī)劃的改進(jìn)蟻群算法[J]. 機械科學(xué)與技術(shù)，2013，32（1）：42-46.

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

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

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

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

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

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

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

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

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

（收稿日期： 2018.12.10）

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

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

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