融合環(huán)境信息和運(yùn)動(dòng)約束的改進(jìn)A*算法研究

白 雄，魯吉林，路 寬，陳鵬云，崔俊杰，劉澤華

1.中北大學(xué) 機(jī)電工程學(xué)院，太原030051

2.中國(guó)人民解放軍 第32381部隊(duì)，北京100072

目前機(jī)器人技術(shù)得到廣泛的發(fā)展，移動(dòng)機(jī)器人在各行各業(yè)當(dāng)中得到了廣泛的使用[1]。其中，路徑規(guī)劃作為移動(dòng)機(jī)器人自主導(dǎo)航的重要前提，在機(jī)器人領(lǐng)域扮演了重要的角色[2]。路徑規(guī)劃A*算法作為一種深度優(yōu)先啟發(fā)式搜索算法[3]，相比于圖搜索算法，A*算法具有計(jì)算量小，算法搜索朝著目標(biāo)點(diǎn)方向等優(yōu)點(diǎn)，但是A*算法的啟發(fā)函數(shù)簡(jiǎn)單，算法在尋路過程當(dāng)中會(huì)出現(xiàn)較多的冗余點(diǎn)，花費(fèi)時(shí)間長(zhǎng)。針對(duì)這一問題已經(jīng)有眾多學(xué)者改進(jìn)了A*算法。文獻(xiàn)[4]提出一種基于改進(jìn)的A*算法與動(dòng)態(tài)窗口法結(jié)合的溫室機(jī)器人路徑規(guī)劃算法，改進(jìn)后的A*算法路徑規(guī)劃更為平滑和高效。文獻(xiàn)[5]在A*算法的啟發(fā)函數(shù)中加入余弦相似性和方法信息，選取36 階領(lǐng)域矩陣解決了移動(dòng)機(jī)器人貼合U型彎的問題，改進(jìn)了路徑曲率的變化。文獻(xiàn)[6]在游戲地圖中通過改進(jìn)區(qū)域搜索點(diǎn)改進(jìn)了A*算法，有效解決了路徑轉(zhuǎn)折問題。文獻(xiàn)[7]針對(duì)公交線路提出一種改進(jìn)A*算法，將乘客人數(shù)加入到估價(jià)函數(shù)中，提高了路徑搜索的效率。文獻(xiàn)[8]采用“視野線”以及“圓弧-直線-圓弧”改善了路徑的平滑度。文獻(xiàn)[9]將物理信息添加到啟發(fā)函數(shù)當(dāng)中并且刪除冗余點(diǎn)，增強(qiáng)路徑搜索效率和平滑度。文獻(xiàn)[10]針對(duì)標(biāo)準(zhǔn)A*算法存在對(duì)稱路徑，使用定向搜索方法減少搜索點(diǎn)，提高了算法的效率。文獻(xiàn)[11]通過引入三次均勻B樣條插值函數(shù)，改進(jìn)了A*算法，改進(jìn)后的算法規(guī)劃的路徑更加平滑。文獻(xiàn)[12]針對(duì)城市地圖進(jìn)行預(yù)處理，同時(shí)改進(jìn)真實(shí)代價(jià)函數(shù)和估價(jià)函數(shù)對(duì)A*算法進(jìn)行改進(jìn)，改進(jìn)后的算法能有效提高無人機(jī)的工作效率。文獻(xiàn)[13]在全局路徑的基礎(chǔ)上選擇關(guān)鍵節(jié)點(diǎn)對(duì)全局路徑進(jìn)行分段，然后結(jié)合局部路徑算法進(jìn)行優(yōu)化，改善了路徑的平滑度。文獻(xiàn)[14]通過全局路徑重規(guī)劃解決了障礙物大面積阻礙全局路徑的問題，提高了移動(dòng)機(jī)器人避障安全性。上述文獻(xiàn)可以看出，之前的改進(jìn)算法主要局限于對(duì)代價(jià)函數(shù)和搜索點(diǎn)的改進(jìn)，適用于簡(jiǎn)單的環(huán)境地圖，算法并沒有考慮移動(dòng)機(jī)器人的運(yùn)動(dòng)特性、環(huán)境信息和避障能力。

為了解決以上問題，本文基于機(jī)器人運(yùn)動(dòng)特性和環(huán)境信息改進(jìn)A*算法進(jìn)行路徑規(guī)劃。首先通過環(huán)境地圖中障礙物權(quán)重系數(shù)對(duì)代價(jià)函數(shù)進(jìn)行改進(jìn)；其次考慮機(jī)器人運(yùn)動(dòng)約束和最小安全距離，保證機(jī)器人運(yùn)動(dòng)的安全性。最后通過與其他經(jīng)典算法進(jìn)行對(duì)比分析，驗(yàn)證改進(jìn)的算法在路徑拐彎次數(shù)、擴(kuò)展節(jié)點(diǎn)、規(guī)劃時(shí)間和路徑長(zhǎng)度方面的有效性。

1 改進(jìn)A＊算法

針對(duì)標(biāo)準(zhǔn)A*算法代價(jià)函數(shù)缺乏通用性和路徑規(guī)劃算法沒有考慮機(jī)器人運(yùn)動(dòng)特性。改進(jìn)A*算法首先通過環(huán)境地圖信息設(shè)定啟發(fā)函數(shù)；其次根據(jù)搜索方向計(jì)算子節(jié)點(diǎn)的代價(jià)值；最后結(jié)合關(guān)鍵節(jié)點(diǎn)和運(yùn)動(dòng)約束生成最優(yōu)路徑，具體流程如圖1所示。

圖1 改進(jìn)A*算法的優(yōu)化流程Fig.1 Improved A* algorithm optimization process

1.1 環(huán)境信息模型

移動(dòng)機(jī)器人在進(jìn)行路徑規(guī)劃之前要對(duì)環(huán)境地圖進(jìn)行合理的建模，由于柵格地圖具有簡(jiǎn)單、高效的特點(diǎn)，則采用柵格法對(duì)環(huán)境信息建模，地圖中黑色柵格表示障礙物柵格，在數(shù)組中表示為1；白色地圖為機(jī)器人可通行柵格，在數(shù)組中表示為0，S為機(jī)器人人起始位置，G為機(jī)器人目標(biāo)位置。如圖2 所示。機(jī)器人最短路徑就是通過搜索這張柵格地圖來得到的。

圖2 柵格地圖Fig.2 Raster map

通過設(shè)置障礙物權(quán)重系數(shù)表達(dá)柵格地圖的復(fù)雜度，對(duì)環(huán)境信息進(jìn)行的分析，并且定義障礙物權(quán)重系數(shù)為當(dāng)前地圖中障礙物個(gè)數(shù)和整個(gè)柵格地圖中的柵格個(gè)數(shù)占比。障礙柵格數(shù)為N個(gè)，移動(dòng)機(jī)器人起始坐標(biāo)為(xs,ys),終止坐標(biāo)為(xg,yg),障礙物權(quán)重系數(shù)定義為：

1.2 啟發(fā)函數(shù)的改進(jìn)

標(biāo)準(zhǔn)A*算法規(guī)劃出的路徑存在較多的拐點(diǎn)和轉(zhuǎn)折，不利于機(jī)器人運(yùn)動(dòng)。本文基于移動(dòng)機(jī)器人運(yùn)動(dòng)特性和環(huán)境信息提出一種改進(jìn)A*算法。

A*算法的評(píng)價(jià)函數(shù)由代價(jià)函數(shù)g(n)和啟發(fā)函數(shù)h(n)組成，其中算法的最優(yōu)搜索性取決于啟發(fā)函數(shù)的選取，如式（2）、式（3）：

改進(jìn)A*算法將環(huán)境地圖的障礙物權(quán)重系數(shù)引入啟發(fā)函數(shù)當(dāng)中，如式（4）。在不同的環(huán)境地圖當(dāng)中，通過修改代價(jià)函數(shù)與啟發(fā)函數(shù)的權(quán)重，提高算法的效率，保證移動(dòng)機(jī)器人路徑規(guī)劃的最優(yōu)性。

其中，g(n)為起始節(jié)點(diǎn)到當(dāng)前節(jié)點(diǎn)的代價(jià)函數(shù)，h(n)為當(dāng)前節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的啟發(fā)函數(shù)值，(xn,yn)為當(dāng)前節(jié)點(diǎn)的坐標(biāo)，a為代價(jià)函數(shù)g(n)的權(quán)重，即當(dāng)前節(jié)點(diǎn)到目標(biāo)點(diǎn)的距離與起始節(jié)點(diǎn)到目標(biāo)點(diǎn)的距離比值。

A*算法中評(píng)價(jià)函數(shù)的好壞直接影響路徑規(guī)劃的效率。代價(jià)函數(shù)g(n)較大時(shí)，評(píng)價(jià)函數(shù)的值則會(huì)大于的實(shí)際代價(jià)，算法效率降低，從而導(dǎo)致機(jī)器人運(yùn)動(dòng)的實(shí)際代價(jià)過大，則算法將當(dāng)前節(jié)點(diǎn)到目標(biāo)點(diǎn)的距離與起始節(jié)點(diǎn)到目標(biāo)點(diǎn)的距離比值設(shè)為代價(jià)函數(shù)的權(quán)重。通過式（4）可知，當(dāng)障礙物權(quán)重系數(shù)較小時(shí)，增加啟發(fā)函數(shù)的權(quán)重，A*算法減少搜索空間，提高了路徑規(guī)劃速度，減少路徑的拐點(diǎn)和轉(zhuǎn)折點(diǎn)；當(dāng)障礙物權(quán)重系數(shù)較大時(shí)，減少啟發(fā)函數(shù)的權(quán)重，增大搜索空間，避免算法陷入局部最優(yōu)。因此，改進(jìn)的評(píng)價(jià)函數(shù)可以在不同環(huán)境地圖中提高路徑搜索能力，有利于機(jī)器人找到最短路徑。

1.3 搜索領(lǐng)域的選取

在搜索過程中A*算法向父節(jié)點(diǎn)的任意方向擴(kuò)展，增加了算法的規(guī)劃時(shí)間，改進(jìn)的A*算法提出了一種新的擴(kuò)展方式，即8 節(jié)點(diǎn)擴(kuò)展方式改為5 節(jié)點(diǎn)擴(kuò)展方式。定義終點(diǎn)坐標(biāo)G(xG,yG)，當(dāng)前節(jié)點(diǎn)坐標(biāo)S(xS,yS)，通過坐標(biāo)作差所得值與0進(jìn)行比較來確定算法的擴(kuò)展方向，如圖3（a）所示。

xG-xS>0，且yG-yS>0，則可選節(jié)點(diǎn)為（1，2，3，6，9）；

xG-xS>0，且yG-yS<0，則可選節(jié)點(diǎn)為（3，6，7，8，9）；

xG-xS<0，且yG-yS>0，則可選節(jié)點(diǎn)為（1，2，3，4，7）；

xG-xS<0，且yG-yS<0，則可選節(jié)點(diǎn)為（1，4，7，8，9）。

通過確定節(jié)點(diǎn)擴(kuò)展方向，然后從剩余的五個(gè)子節(jié)點(diǎn)選取下一個(gè)所要擴(kuò)展的節(jié)點(diǎn)，每次選擇評(píng)價(jià)函數(shù)值最小的子節(jié)點(diǎn)作為下一個(gè)路徑規(guī)劃的節(jié)點(diǎn)。

圖3（b）顯示父節(jié)點(diǎn)與其相鄰的各個(gè)子節(jié)點(diǎn)的關(guān)系，主要將父節(jié)點(diǎn)的各子節(jié)點(diǎn)分為2類：父節(jié)點(diǎn)的上下左右四個(gè)節(jié)點(diǎn)和其余的四個(gè)節(jié)點(diǎn)。

圖3 節(jié)點(diǎn)搜索方式Fig.3 Node search mode

針對(duì)標(biāo)準(zhǔn)的A*算法斜穿障礙物邊緣可能性較大，增加子節(jié)點(diǎn)選取規(guī)則去避免此缺點(diǎn)，所用節(jié)點(diǎn)選取規(guī)則為：當(dāng)障礙物節(jié)點(diǎn)為該父節(jié)點(diǎn)上下左右的四個(gè)子節(jié)點(diǎn)時(shí)，則四個(gè)子節(jié)點(diǎn)各自兩邊的子節(jié)點(diǎn)不作為擴(kuò)展節(jié)點(diǎn)，如圖4 所示1 號(hào)路徑；當(dāng)障礙物節(jié)點(diǎn)為其余的四個(gè)節(jié)點(diǎn)時(shí)，則不作任何處理，如圖4所示2號(hào)路徑。經(jīng)過上述處理之后，改進(jìn)A*算法可有效避免斜穿障礙物邊緣。

圖4 避開障礙物邊緣后的路徑Fig.4 Path after avoiding edge of obstacle

2 基于運(yùn)動(dòng)約束的路徑生成

2.1 機(jī)器人運(yùn)動(dòng)學(xué)模型

移動(dòng)機(jī)器人運(yùn)動(dòng)過程中，一般將移動(dòng)機(jī)器人作為一個(gè)質(zhì)點(diǎn)處理，而在實(shí)際中機(jī)器人具有一定的尺寸限制。機(jī)器人運(yùn)動(dòng)過程中是保持一定速度的，為防止機(jī)器人發(fā)生原地轉(zhuǎn)向、側(cè)滑等不安全動(dòng)作，需對(duì)機(jī)器人路徑進(jìn)行優(yōu)化。而移動(dòng)機(jī)器人受到運(yùn)動(dòng)特性的限制，存在最小轉(zhuǎn)彎角度，若機(jī)器人轉(zhuǎn)彎時(shí)角度過大時(shí)，會(huì)導(dǎo)致機(jī)器人發(fā)生不安全的動(dòng)作?？紤]到移動(dòng)機(jī)器人作為一個(gè)非完整約束系統(tǒng)，移動(dòng)機(jī)器人的簡(jiǎn)化模型如圖5所示。

圖5 移動(dòng)機(jī)器人運(yùn)動(dòng)模型Fig.5 Mobile robot motion model

某時(shí)刻下，機(jī)器人位置坐標(biāo)為(x,y,θ)，其中x、y和θ分別是移動(dòng)機(jī)器人質(zhì)心位置的橫縱坐標(biāo)和機(jī)器人的航向角。機(jī)器人的導(dǎo)向角為?（機(jī)器人中軸線和前輪行駛方向的夾角），R為機(jī)器人轉(zhuǎn)向半徑，l為前后軸距，b為輪距，v為當(dāng)前速度。移動(dòng)機(jī)器人的運(yùn)動(dòng)特性需滿足如下約束：

由于機(jī)器人受運(yùn)動(dòng)特性所限，導(dǎo)致移動(dòng)機(jī)器人的路徑轉(zhuǎn)角不能過大，否則將發(fā)生不可預(yù)測(cè)的不安全動(dòng)作，改進(jìn)A*算法將其作為路徑規(guī)劃的約束條件，使規(guī)劃出的路徑滿足該運(yùn)動(dòng)約束。

2.2 Floyd算法路徑平滑優(yōu)化

平滑路徑可使機(jī)器人更好地完成任務(wù)，提高機(jī)器人的運(yùn)動(dòng)精度。當(dāng)前機(jī)器人路徑的平滑方式有貝塞爾曲線和利用幾何方式對(duì)移動(dòng)機(jī)器人路徑進(jìn)行優(yōu)化處理，但其復(fù)雜度高，難用在機(jī)器人頻繁轉(zhuǎn)向和轉(zhuǎn)角過大的情況。文獻(xiàn)[15]提出基于多項(xiàng)式的方法優(yōu)化移動(dòng)機(jī)器人路徑，但該方法在復(fù)雜情況下多項(xiàng)式無解，不能保證算法的完整性。文獻(xiàn)[16]在機(jī)器人路徑規(guī)劃參數(shù)單元中設(shè)定狀態(tài)參數(shù)，依據(jù)狀態(tài)參數(shù)生成貝塞爾曲線的控制點(diǎn)，優(yōu)化了機(jī)器人路徑，但是該方法存在著速度方面的限制，在運(yùn)動(dòng)過程中需不斷校正參數(shù)。本研究融合移動(dòng)機(jī)器人運(yùn)動(dòng)特性進(jìn)行路徑點(diǎn)的處理，通過Floyd 算法使得修正后的路徑更加符合移動(dòng)機(jī)器人的運(yùn)動(dòng)約束。

Floyd算法是解決地圖中任意兩點(diǎn)之間最短路徑的一種經(jīng)典算法。通過柵格地圖規(guī)劃出來的路徑存在較多的轉(zhuǎn)折點(diǎn)、搜索節(jié)點(diǎn)只能在柵格中心位置，導(dǎo)致機(jī)器人路徑平滑度較差。本研究將Floyd 算法與A*算法相融合可以有效減少移動(dòng)機(jī)器人路徑的轉(zhuǎn)折，提高機(jī)器人運(yùn)動(dòng)效率，有利于移動(dòng)機(jī)器人的應(yīng)用需求?？紤]運(yùn)動(dòng)學(xué)模型判斷兩個(gè)路徑點(diǎn)之間的距離、時(shí)間和轉(zhuǎn)角是否比原來的短，算法優(yōu)化路徑對(duì)比如圖6、圖7所示。

圖6 Floyd算法原理Fig.6 Principle of Floyd algorithm

圖7 Floyd算法優(yōu)化路徑Fig.7 Floyd algorithm optimization path

如圖6所示，節(jié)點(diǎn)A、D之間并沒有可直達(dá)的路徑，則在Floyd算法當(dāng)中視為無窮大，那么有：

且

則，節(jié)點(diǎn)A到節(jié)點(diǎn)D的路徑可表示為A、B、D。進(jìn)一步有：

即：

則節(jié)點(diǎn)A到節(jié)點(diǎn)D的路徑表示為A、C、D。

如圖7所示，采用標(biāo)準(zhǔn)A*算法的規(guī)劃路徑為(S、S1、S2、S3、S4、S5、S6、S7、S8、G)，圖中所示路徑拐點(diǎn)及轉(zhuǎn)折點(diǎn)較多，導(dǎo)致路徑平滑度較差。

通過融合移動(dòng)機(jī)器人運(yùn)動(dòng)特性的Floyd平滑算法剔除路徑冗余節(jié)點(diǎn)，從而降低路徑的轉(zhuǎn)折次數(shù)以及優(yōu)化路徑長(zhǎng)度，改善路徑的平滑度。并通過判斷兩個(gè)節(jié)點(diǎn)之間是否有障礙物，以及兩節(jié)點(diǎn)連線到障礙物的距離d和安全距離D的大小，來判斷該路徑是否可行，如圖7 中的路徑為S、S1、S7、G。

2.3 改進(jìn)算法約束條件

文章改進(jìn)的路徑規(guī)劃算法通過融合環(huán)境信息、搜索節(jié)點(diǎn)方式、安全距離和運(yùn)動(dòng)特性來進(jìn)行全局路徑規(guī)劃，算法中所涉及的主要約束條件以及詳細(xì)的數(shù)學(xué)描述如下：

（1）安全距離

改進(jìn)A*算法設(shè)置路徑節(jié)點(diǎn)到障礙物的安全距離，防止移動(dòng)機(jī)器人和障礙物發(fā)生碰撞。障礙物到路徑的垂直距離OE（點(diǎn)O到線段KG的垂直距離）與預(yù)先設(shè)置的安全距離進(jìn)行比較來判斷所規(guī)劃的路徑是否安全可行，安全距離如圖8所示。假設(shè)節(jié)點(diǎn)K的坐標(biāo)為(x1,y1)，終止節(jié)點(diǎn)G的坐標(biāo)為(x2,y2)，障礙物節(jié)點(diǎn)O坐標(biāo)為(x3,y3)；節(jié)點(diǎn)F的坐標(biāo)為(x4,y4)線段OF為障礙物到線段KG沿縱軸方向的距離，記作l；KG之間連線與x軸之間的夾角為α，具體原理圖如下：

圖8 安全距離設(shè)計(jì)Fig.8 Safety distance design

其中，l為線段OF為障礙物節(jié)點(diǎn)到線段KG沿縱軸方向的距離，α為線段OE與線段OF之間的夾角，d為障礙物到路徑的距離。

通過式（13）計(jì)算得障礙物到路徑的距離d，設(shè)置安全距離為D。比較d與安全距離D的大小確定路徑是否可作為備選路徑。具體判斷方式如下所示：

若d≤D，那么放棄該路徑；

若d>D，那么選擇該路徑。

（2）機(jī)器人運(yùn)動(dòng)特性

首先設(shè)置移動(dòng)機(jī)器人在移動(dòng)過程中只能進(jìn)行前后運(yùn)動(dòng)，當(dāng)移動(dòng)機(jī)器人路徑角度發(fā)生改變時(shí)，調(diào)整移動(dòng)機(jī)器人的姿態(tài)，然后按照已經(jīng)規(guī)劃好的路徑移動(dòng)到終點(diǎn)。

如圖6 所示優(yōu)化路徑起點(diǎn)A(xa,ya)，節(jié)點(diǎn)B(xb,yb)和節(jié)點(diǎn)C(xc,yc)，移動(dòng)機(jī)器人旋轉(zhuǎn)角度計(jì)算方法為：

其中

β表示為機(jī)器人前一運(yùn)動(dòng)狀態(tài)。并且移動(dòng)機(jī)器人從A點(diǎn)到C點(diǎn)之間的路徑為：改進(jìn)A*算法主要融合上述約束條件對(duì)路徑進(jìn)行全局路徑規(guī)劃。

3 實(shí)驗(yàn)和分析

3.1 仿真環(huán)境

仿真實(shí)驗(yàn)主要環(huán)境為Intel?CoreTMi5-8400 CPU@2.80 GHz，Windows10。通過建立柵格地圖來驗(yàn)證此次改進(jìn)的A*算法的有效性以及改進(jìn)A*算法對(duì)于復(fù)雜地圖的適應(yīng)性，同時(shí)將改進(jìn)A*算法與標(biāo)準(zhǔn)A*算法、Dijkstra 算法以及蟻群算法進(jìn)行對(duì)比，檢驗(yàn)改進(jìn)A*算法的優(yōu)越性。仿真實(shí)驗(yàn)所用的柵格地圖為4 個(gè)尺寸為50×50，障礙物權(quán)重占比不同的柵格地圖。地圖中的單位柵格邊長(zhǎng)為1 m，柵格地圖中空白區(qū)域?yàn)榭赏ㄐ袇^(qū)域，黑色區(qū)域?yàn)椴豢赏ㄐ袇^(qū)域，仿真起點(diǎn)為地圖左下角頂點(diǎn)，終點(diǎn)為地圖右上角頂點(diǎn)。安全距離D設(shè)為0.8 m。

3.2 仿真結(jié)果與分析

改進(jìn)A*算法的約束條件可分別計(jì)算路徑長(zhǎng)度和路徑轉(zhuǎn)角，如式（13）、（14）所示；搜索節(jié)點(diǎn)數(shù)通過節(jié)點(diǎn)選取規(guī)則加入Open 列表中節(jié)點(diǎn)個(gè)數(shù)可知，通過上述評(píng)價(jià)指標(biāo)對(duì)仿真實(shí)驗(yàn)進(jìn)行評(píng)價(jià)。通過50×50 的柵格地圖對(duì)蟻群算法、標(biāo)準(zhǔn)A*算法、Dijkstra 算法以及改進(jìn)A*算法在Matlab中進(jìn)行測(cè)試，測(cè)試結(jié)果如圖9～12所示。

圖9 地圖1仿真結(jié)果Fig.9 Simulation results of map 1

上述四個(gè)柵格地圖障礙物權(quán)重占比逐漸增大，環(huán)境地圖越來越復(fù)雜，地圖主要包含了排列整齊的障礙物以及排列混亂的障礙物，所利用的環(huán)境地圖有較好的代表性。仿真實(shí)驗(yàn)通過在Matlab中對(duì)比改進(jìn)A*算法與標(biāo)準(zhǔn)A*算法、Dijkstra 算法以及蟻群算法得到路徑規(guī)劃的時(shí)間、轉(zhuǎn)折次數(shù)、轉(zhuǎn)角度數(shù)、搜索節(jié)點(diǎn)個(gè)數(shù)以及路徑長(zhǎng)度等，如表1所示。

表1 不同地圖下幾種算法對(duì)比實(shí)驗(yàn)Table 1 Comparison tests of several algorithms under different maps

圖10 地圖2仿真結(jié)果Fig.10 Simulation results of map 2

圖11 地圖3仿真結(jié)果Fig.11 Simulation results of map 3

圖12 地圖4仿真結(jié)果Fig.12 Simulation results of map 4

由圖9～12 所示的仿真結(jié)果可知，在所使用的四種環(huán)境地圖中，地圖復(fù)雜度由易到難，障礙物所占比重逐漸增加。改進(jìn)A*算法和其余三種對(duì)比算法都可以規(guī)劃出路徑，但是改進(jìn)算法和其余路徑規(guī)劃算法在轉(zhuǎn)折點(diǎn)、規(guī)劃時(shí)間、路徑角度、搜索節(jié)點(diǎn)以及路徑長(zhǎng)度上有較大的不同。在不同環(huán)境地圖中，改進(jìn)A*算法規(guī)劃出來的路徑更有利于機(jī)器人運(yùn)動(dòng)，改進(jìn)算法主要在機(jī)器人運(yùn)動(dòng)特性的基礎(chǔ)上通過Floyd算法進(jìn)行處理路徑，F(xiàn)loyd算法是解決地圖中任意兩點(diǎn)之間最短路徑的一種經(jīng)典算法，在兩點(diǎn)之間無障礙物時(shí)，刪除冗余點(diǎn)進(jìn)行規(guī)劃路徑，所以改進(jìn)A*算法規(guī)劃路徑與搜索節(jié)點(diǎn)并不能一一對(duì)應(yīng)，在路徑長(zhǎng)度以及路徑彎曲程度有很大的改進(jìn)。

從表中數(shù)據(jù)可以看出：標(biāo)準(zhǔn)A*算法是經(jīng)典的啟發(fā)式算法，規(guī)劃出來的路徑通往目標(biāo)點(diǎn)所在的方向，并沒有考慮障礙物的影響，而是選取了局部最短路徑；蟻群算法規(guī)劃出來的路徑由于信息素的影響，路徑轉(zhuǎn)角過大，并且路徑規(guī)劃時(shí)間長(zhǎng)，算法在1 500 代左右達(dá)到收斂，并沒有找到最優(yōu)路徑；Dijkstra 算法簡(jiǎn)單，能夠得到最優(yōu)解，但是其搜索節(jié)點(diǎn)過多，效率比較低，占用過多內(nèi)存，路徑搜索時(shí)間長(zhǎng)等缺點(diǎn)導(dǎo)致它并不適合復(fù)雜地圖；在復(fù)雜地圖當(dāng)中改進(jìn)A*算法相比其他算法有較大的優(yōu)勢(shì)，相比于以上四種算法，此次改進(jìn)的算法路徑轉(zhuǎn)折點(diǎn)更少，規(guī)劃出來的路徑轉(zhuǎn)角降低了82%，更適合機(jī)器人運(yùn)動(dòng)；并且始終與障礙物保持一定的距離，避免移動(dòng)機(jī)器人與障礙物發(fā)生碰撞；路徑規(guī)劃時(shí)間平均減少了80%；路徑長(zhǎng)度在不同地圖中相比其他算法都有很大的改進(jìn)。上述分析可知，改進(jìn)后的A*算法在移動(dòng)機(jī)器人路徑規(guī)劃當(dāng)中會(huì)起到更好的效用。

4 結(jié)束語

基于運(yùn)動(dòng)特性的改進(jìn)A*算法，針對(duì)標(biāo)準(zhǔn)A*算法在路徑規(guī)劃過程中拐點(diǎn)較多、轉(zhuǎn)角大不利于機(jī)器人運(yùn)動(dòng)、路徑規(guī)劃時(shí)間長(zhǎng)以及搜索路線緊貼障礙物邊緣等缺點(diǎn)，導(dǎo)致移動(dòng)機(jī)器人容易發(fā)生不安全動(dòng)作，不利于機(jī)器人的行進(jìn)，提出一種改進(jìn)A*算法。主要結(jié)論如下：

（1）通過環(huán)境地圖中障礙物權(quán)重系數(shù)對(duì)代價(jià)函數(shù)進(jìn)行改進(jìn)，算法搜索節(jié)點(diǎn)更具有方向性，提高了算法的效率，也保證了算法的實(shí)時(shí)性。

（2）在路徑優(yōu)化過程中考慮機(jī)器人運(yùn)動(dòng)特性和安全距離等約束條件，保證移動(dòng)機(jī)器人運(yùn)動(dòng)安全性。

（3）實(shí)驗(yàn)結(jié)果表明，改進(jìn)后的A*算法在路徑規(guī)劃中始終與障礙物保持一定的距離，搜索的節(jié)點(diǎn)和路徑規(guī)劃時(shí)間減少；融合運(yùn)動(dòng)特性的路徑規(guī)劃更為平滑，路徑轉(zhuǎn)角更小，更有利于移動(dòng)機(jī)器人的運(yùn)動(dòng)。