改進A*算法的機器人全局最優(yōu)路徑規(guī)劃

王中玉 曾國輝 黃勃 方志軍

摘 要：針對傳統(tǒng)A*算法規(guī)劃的路徑存在很多冗余點和拐點的問題，提出了一種基于A*算法改進的高效路徑規(guī)劃算法。首先，改進評價函數(shù)的具體計算方式，減小算法搜索每個區(qū)間的計算量，從而降低尋路時間，并改變生成路徑;其次，在改進評價函數(shù)具體計算方式的基礎(chǔ)上，改進評價函數(shù)的權(quán)重比例，減少生成路徑中的冗余點和拐點;最后，改進路徑生成策略，刪除生成路徑中的無用點，從而提高路徑的平滑性;此外，考慮到機器人的實際寬度，改進后算法引入障礙物擴展策略保證規(guī)劃路徑的可行性。將改進A*算法與三種算法進行仿真對比，實驗結(jié)果表明，改進后的A*算法規(guī)劃的路徑更加合理，尋路時間更短，平滑性更高。

關(guān)鍵詞：A*算法;路徑規(guī)劃;評價函數(shù);生成策略;障礙物擴展

中圖分類號：TP242.6

文獻標(biāo)志碼：A

Global optimal path planning for robots with improved A* algorithm

WANG Zhongyu， ZENG Guohui*， HUANG Bo， FANG Zhijun

School of Electronic and Electrical Engineering， Shanghai University of Engineering Science， Shanghai 201620， China

Abstract：

There are many redundant points and inflection points in the path planned by the traditional A* algorithm. Therefore， an efficient path planning algorithm based on A* algorithm was proposed. Firstly， the specific calculation method of the evaluation function was improved to reduce the calculation amount of the algorithm searching each interval， thereby reducing the path finding time and changing the generation path. Secondly， on the basis of improving the specific calculation method of the evaluation function， the weight ratio of the evaluation function was improved， and the redundant points and inflection points in the generation path were reduced. Finally， the path generation strategy was improved to delete the useless points in the generation path， improving the smoothness of the path. In addition， considering the actual width of the robot， the improved algorithm introduced an obstacle expansion strategy to ensure the feasibility of the planned path. The comparison of the improved A* algorithm with three algorithms shows that the path of the improved A* algorithm is more reasonable， the path finding time is shorter， and the smoothness is higher.

Key words：

A* algorithm; path planning; evaluation function; generation strategy; obstacle expansion

0 引言

近年來，移動機器人技術(shù)一直在快速發(fā)展。預(yù)計移動機器人不僅是一種即將到來的新式武器，也是老齡化社會一種新的勞動力。路徑規(guī)劃在移動機器人任務(wù)管理系統(tǒng)中是一項關(guān)鍵技術(shù)，在整個移動機器人研究領(lǐng)域中也是一個熱門而相當(dāng)復(fù)雜的問題[1-2]。規(guī)劃的路徑應(yīng)該是最佳無沖突，并且有助于在復(fù)雜環(huán)境中實現(xiàn)特定任務(wù)[3-4]?，F(xiàn)有的路徑規(guī)劃主要分為兩大類：傳統(tǒng)規(guī)劃方法和智能方法[5-6]。傳統(tǒng)的路徑規(guī)劃算法主要指基于全局環(huán)境模型的圖搜索算法和潛在的現(xiàn)場方法。應(yīng)用較多的智能規(guī)劃方法包括神經(jīng)網(wǎng)絡(luò)[7]、人工勢場法[8]、粒子群算法[9]、遺傳算法[10]、蟻群算法[11]和模擬退火算法[12]。A*算法是一種屬于智能規(guī)劃方法的啟發(fā)式算法，它具有簡單的估值功能，廣泛地應(yīng)用于各種類型搜索問題，如計算機游戲無碰撞檢測、無人機路徑規(guī)劃和移動機器人路徑規(guī)劃[13-14]。

在路徑規(guī)劃領(lǐng)域，A*算法具有計算量小、尋路時間短、規(guī)劃路徑相對最優(yōu)等突出特點。因此，大量學(xué)者對A*算法進行深入研究并加以改進，以適用于不同領(lǐng)域機器人的路徑規(guī)劃。如航海領(lǐng)域，主要在A*算法的評價函數(shù)中增加角度轉(zhuǎn)向成本，以滿足船舶調(diào)頭、轉(zhuǎn)彎的實際需要[15]。航空領(lǐng)域，主要在A*算法的評價函數(shù)中增加坡度成本和燃耗成本，以滿足無人機等飛行器的空間約束[16]。而在陸地的移動機器人路徑規(guī)劃中，A*算法的改進主要分為兩方面：一方面是減少尋路時間，如同步雙向A*算法在路徑的起點和目標(biāo)點同時運行A*算法，缺陷是受地圖環(huán)境影響大，尋路時間和生成路徑可能更差[17];另一方面是優(yōu)化生成路徑，主要通過增加搜索矩陣的搜索方向來實現(xiàn)，如雙向時效A*算法，缺陷是增加了尋路時間[18]。

本文提出了一種在已知環(huán)境中移動機器人全局路徑規(guī)劃的新方法。分析A*算法的問題并進行三方面的改進。首先通過改變A*算法評價函數(shù)的具體計算方法，減少尋路時間。再通過改變啟發(fā)函數(shù)的權(quán)重和改進路徑生成策略減少冗余點與拐點，規(guī)劃全局最優(yōu)路徑。此外，考慮到移動機器人的實際寬度，采用障礙物擴展策略，確保生成的路徑安全可行。通過幾個模擬實驗驗證了A*算法的改進真實有效。

1 A*算法規(guī)劃機器人路徑

A*算法規(guī)劃移動機器人路徑的過程可概括為兩部分：一是環(huán)境建模;二是算法引入，生成路徑。

1.1 環(huán)境建模

規(guī)劃移動機器人路徑的前提是對實際環(huán)境進行模型搭建，A*算法采用柵格法構(gòu)建移動機器人路徑規(guī)劃的環(huán)境。柵格法是移動機器人路徑規(guī)劃最常用的方法，最早是由Morave和Elfesc H P和Elfes A提出的，其基本思想是將有限的規(guī)劃空間劃分為多個大小相同并賦有二進制數(shù)的柵格單元[19]?；跂鸥駡D的移動機器人路徑規(guī)劃通常將機器人視為移動粒子，并且記錄其在柵格上的狀態(tài)。為簡化分析，本文作出以下假設(shè)：

假設(shè)1 在路徑規(guī)劃的過程中，障礙物的位置和大小是已知且不改變的。忽略障礙物的高度信息。

假設(shè)2 規(guī)劃的移動機器人路徑，每一步都占據(jù)整個柵格。忽略移動機器人的高度信息。

假設(shè)3 移動機器人二維工作空間的長是L，寬是W。將該工作空間劃分為大小相同的R*S個柵格，每個柵格的信息用Nij表示，如式（1）整個工作空間的信息可以用Ω表示：

Ω=∑Nij; i∈[1，R]，? j∈[1，S]（1）

如式（2）每個柵格的狀態(tài)信息具體地表示為：

Nij=0， 無障礙

1，有障礙 （2）

其中：當(dāng)Nij取值為0時，表示當(dāng)前柵格是無障礙物的自由空間;當(dāng)Nij取值為1時，表示當(dāng)前柵格是有障礙物的。

從理論上講，移動機器人在行走時會有許多方向和細(xì)微動作。但考慮到模型的復(fù)雜性，A*搜索算法定義，移動機器人在柵格中每一步行走僅有8個可供參考的方向，即8搜索方向A*算法，它們分別是前、后、左、右、左前、左后、右前、右后。移動機器人8個運動方向如圖1所示。

1.2 A*算法引入

A*算法是由Hart和Nilsson在1968年提出的一種的啟發(fā)式圖搜索算法，最早應(yīng)用于解決各種數(shù)學(xué)問題[20]。在人工智能領(lǐng)域中，主要運用A*算法解決各種路徑規(guī)劃問題。其基本思想是，確定一個評價函數(shù)，從起點開始根據(jù)評價函數(shù)不斷向目標(biāo)點的方向進行搜索，同時記錄每一次搜索確定的點，直至搜索到目標(biāo)點為止。最后從目標(biāo)點返回到起始位置，獲得最小成本路徑。A*算法的評價函數(shù)如式（3）所示。

f（n）=g（n）+h（n）（3）

在式（3）中， f（n）是當(dāng)前點的評價函數(shù)，其函數(shù)主要由兩部分組成：第一部分是過去成本函數(shù)g（n），用于評價起點到當(dāng)前點的代價;第二部分是當(dāng)前成本函數(shù)h（n），用于評價當(dāng)前點到目標(biāo)節(jié)點的代價。在二維空間中，代價的值通常指兩個節(jié)點之間的距離，因此函數(shù)g（n）和函數(shù)h（n）的值通常采用歐氏距離計算得來。

g（n）=（xn-xs）2+（yn-ys）2（4）

h（n）=（xt-xn）2+（yt-yn）2（5）

在式（4）和式（5）中，（xs，ys）是起點Ps坐標(biāo)，（xn，yn）是當(dāng)前點Pn坐標(biāo)，（xt，yt）是目標(biāo)點Pt坐標(biāo)。進一步，可以得知A*算法的評價函數(shù)是Dijkstra算法和最佳優(yōu)先搜索（Best-First-Search， BFS）算法的結(jié)合。在評價函數(shù)f（n）中，若g（n）的權(quán)重為1，h（n）的權(quán)重為0，則A*算法可視為Dijkstra算法，傾向于廣度優(yōu)先搜索即偏向于接近起點的頂點，是兩點之間經(jīng)典的路徑最短算法。若g（n）的權(quán)重為0，h（n）的權(quán)重為1，則A*算法可視為BFS算法，算法搜索啟發(fā)性更強即偏向于接近目標(biāo)點的頂點，是路徑規(guī)劃中典型的啟發(fā)式搜索算法，但規(guī)劃的路徑一般不是最優(yōu)，因此，合理分配A*算法評價函數(shù)的權(quán)重比例，則算法規(guī)劃的路徑將更短、更平滑。

2 改進A*算法

2.1 A*算法的實施

A*算法在規(guī)劃移動機器人路徑時，有兩個起輔助作用的鏈表。一個是存放已經(jīng)生成節(jié)點的Closed鏈表，另一個是存放下一步要探索節(jié)點的Open鏈表。如移動機器人在當(dāng)前位置探索下一步要行走的方向時，當(dāng)前點的位置存放在Closed鏈表中，要探索的8個臨近柵格的位置，存放在Open鏈表中。在執(zhí)行A*算法規(guī)劃路徑時，以評價函數(shù)f（n）為標(biāo)準(zhǔn)，從Open鏈表中選出代價值最小的位置存入Closed鏈表中。循環(huán)往復(fù)，直至在Open鏈表中出現(xiàn)目標(biāo)點為止，最后在Closed鏈表中從目標(biāo)點返回到起始位置，獲得最小成本路徑。程序運行結(jié)束后，可以獲得相對最優(yōu)的路徑。

A*算法的流程如圖2所示。

具體步實施驟如下：

步驟1 創(chuàng)建兩個名為Open和Closed的兩個鏈表，將環(huán)境地圖中的障礙物位置信息存放在Closed鏈表中，將起始點的位置存放在Open鏈表中。

步驟2 檢查Open鏈表是否為空。如果為空，跳到步驟8，否則進行步驟3。

步驟3 檢查Open鏈表是否包含目標(biāo)點，如果包含目標(biāo)點，跳到步驟6，否則進行步驟4。

步驟4 從Open鏈表中選取評價函數(shù)最小值的f（n）點放入Closed鏈表中。

步驟5 將下一步可搜索的點放入Open鏈表中，具體表現(xiàn)為：在8個鄰近柵格點中，如果該節(jié)點不在兩個鏈表中，則將其添加到Open鏈表中，并將其父節(jié)點指向當(dāng)前點。 如果該節(jié)點已經(jīng)在Open鏈表中，則將評價函數(shù)的成本f（n）與Open表中的原始值進行比較。如果它小于等于原始值，則記錄新值并將其父點的指針指向當(dāng)前點;如果節(jié)點在Closed鏈表中，則跳過它并繼續(xù)擴展其他節(jié)點。跳到步驟2。

步驟6 將目標(biāo)點放入Closed鏈表中。

步驟7 在Closed鏈表中，從目標(biāo)點返回到起始位置，獲得最小的成本路徑。

步驟8 程序運行結(jié)束。

2.2 A*算法的改進

A*算法結(jié)合了Dijkstra算法和BFS算法。Dijkstra算法屬于廣度優(yōu)先算法，在進行移動機器人路徑規(guī)劃時，需要進行大量節(jié)點遍歷。為減小Dijkstra算法的搜索范圍和計算的復(fù)雜度，因此引入了BFS算法。然而，在A*算法的啟發(fā)式搜索中，仍添加了一些冗余點，規(guī)劃的路徑也就存在了很多拐點和冗余點（如圖6傳統(tǒng)A*算法規(guī)劃路徑中橢圓形區(qū)域所示）。對于實際的機器人路徑規(guī)劃，機器人易于在拐點處偏差，冗余點會增加路徑規(guī)劃的時間，因此，A*算法規(guī)劃的路徑不是最優(yōu)。本文對A*算法進行三方面改進，以減少尋路時間優(yōu)化生成路徑。

2.2.1 改進評價函數(shù)計算方式

第一方面是改進評價函數(shù)f（n）中過去成本函數(shù)g（n）的具體計算方式，減少尋路時間。改進后的過去成本函數(shù)g′（n）如式（6）所示，改進后A*算法的評價函數(shù)如式（7）所示：

g′（n）=g′（n-1）+c（n）（6）

f（n）=g′（n）+h（n）（7）

在式（6）中c（n）是當(dāng)前點Pn和父節(jié)點Pn-1的成本函數(shù)，表達式如式（8）所示，g′（n-1）是父節(jié)點Pn-1的過去成本函數(shù)，表達式如式（9）所示。在計算當(dāng)前點Pn的評價函數(shù)值時，由于父節(jié)點Pn-1的過去成本函數(shù)g′（n-1）是已知的，所以，只需要計算c（n）即可：

c（n）=（xn-xn-1）2+（yn-yn-1）2（8）

g′（n-1）=g′（n-2）+c（n-1）=

∑n-1i=1（xi-xi-1）2+（yi-yi-1）2（9）

由式（4）和式（8）可推得式（10），因為c（n）是計算當(dāng)前點Pn和其相鄰父節(jié)點Pn-1歐氏距離，g（n）是計算當(dāng)前點Pn和起點Ps的歐氏距離，當(dāng)前點Pn和起點Ps距離的增大時g（n）的計算量隨之增大，所以對于任意當(dāng)前點Pn的c（n）計算量一定小于等于g（n）的計算量。在整個規(guī)劃路徑中需要探索大量節(jié)點，改進后算法可節(jié)省大量計算，減少尋路時間。

c（n）≤g（n）（10）

由式（6）和式（9）推得式（11），由式（4）和式（11）推得式（12）。由式（12）得，在相同起點Ps和當(dāng)前點Pn的情況下，g′（n）的值小于等于g（n）的值，這等價于降低了過去成本函數(shù)g′（n）在評價函數(shù)f（n）中的權(quán)重比例，將導(dǎo)致生成路徑的改變，為了減少這種影響，生成合理路徑，本文進行第二方面改進。

g′（n）=∑ni=1（xi-xi-1）2+（yi-yi-1）2（11）

g′（n）≤g（n）（12）

各點和成本函數(shù)的關(guān)系如圖3所示。

2.2.2 改進評價函數(shù)權(quán)重比例

第二方面是改進評價函數(shù)的權(quán)重比例，以此減少生成路徑的冗余點和拐點，減少無用區(qū)間搜索。由1.2節(jié)介紹可知，在A*算法啟發(fā)式搜索的過程中。當(dāng)h（n）的權(quán)重比例偏大時，評價函數(shù)f（n）的啟發(fā)式信息強烈，盡管減少了路徑搜索的工作量，但規(guī)劃的路徑一般不是最佳。當(dāng)h（n）的權(quán)重比例偏小時，評價函數(shù)f（n）的啟發(fā)式信息比較弱，雖可優(yōu)化生成路徑，但這直接導(dǎo)致路徑搜索工作量的增加。在本文中引入了權(quán)重比例的概念，以此達到平衡啟發(fā)式信息的強度和優(yōu)化路徑縮短尋路時間的目的。

11+X+X1+X=1（13）

本文構(gòu)建的兩項權(quán)重系數(shù)關(guān)系如式（13）所示，在式（13）中X為自變量，取值范圍是[0，+∞），兩項權(quán)重系數(shù)之和為1，當(dāng)自變量X從0變化到+∞時，第一項權(quán)重系數(shù)從1減少至0，第二項權(quán)重系數(shù)從0增加到1，兩者成反比例關(guān)系，將該權(quán)重系數(shù)引入A*算法的評價函數(shù)中，可自由調(diào)節(jié)g′（n）和h（n）的比例，滿足需求。

f′（n）=11+X g′（n）+X1+X h（n）（14）

將式（13）引入式（7）后得可調(diào)節(jié)權(quán)重比例的評價函f′（n）如式（14）所示。在式（14）中，隨著X取值不同，過去成本函數(shù)g′（n）和當(dāng)前成本函數(shù)h（n）權(quán)重范圍都是0～1。當(dāng)X取值為1時，可得式（15）。與式（7）相比，搜索相同區(qū)間其評價函數(shù)值等比例縮小。

f′（n）=0.5g′（n）+0.5h（n）（15）

在地圖環(huán)境相同的情況下，A算法運用式（15）評價函數(shù)和式（7）評價函數(shù)搜索區(qū)間和規(guī)劃路徑是一致的。因此X的取值探索應(yīng)從1開始擴展，經(jīng)過加權(quán)求平均最終取得合適值，使評價函數(shù)的權(quán)重比例更加合理，從而縮短尋路時間、優(yōu)化生成路徑。

2.2.3 改進路徑生成策略

第三方面是改進路徑生成策略，進一步優(yōu)化生成路徑。當(dāng)A*算法搜索到目標(biāo)點Pt（xt，yt）初步確定全局路徑生成點時，改進路徑生成策略，將目標(biāo)點Pt設(shè)為當(dāng)前點Pn（xn，yn），

并判斷當(dāng)前點Pn和其祖父節(jié)點Pn-2（xn-2，yn-2）之間是否存在障礙物，即作一條連接當(dāng)前點Pn和其祖父節(jié)點Pn-2的直線M，由于已知當(dāng)前節(jié)點Pn和其祖父節(jié)點Pn-2的坐標(biāo)，直線M的解析式可由式（16）和式（17）求得：

k=（yn-2-yn）（xn-2-xn）（16）

y=k（x-xn）+yn（17）

根據(jù)直線M方程，求出橫坐標(biāo)在（xn-2，xn）之間線上的所有點Pa，并逐個判斷這些點是否處于障礙物區(qū)，如果有點處于障礙物區(qū)間，則不作改變。如果所有點Pa都不在障礙物區(qū)，則刪除當(dāng)前點Pn的父節(jié)點Pn-1指向其祖父節(jié)點Pn-2。當(dāng)前點Pn優(yōu)化后，依次對下一節(jié)點進行優(yōu)化，直到起點為止完成第1次路徑優(yōu)化。改進后A*算法可設(shè)置多次優(yōu)化，能夠刪除大量冗余點，優(yōu)化生成路徑。該策略如圖4所示。

改進路徑生成策略的偽代碼如下：

有序號的程序——————————Shift+Alt+Y

程序前

PathSmoothing（ps，pt）

1）

Pn ←（xt，yt）

2）

while（Pn ！= Ps）

3）

M ← Getline（Pn，Pn-2）

4）

Pa ← GetPoint（M，xn-2，xn）

5）

if PointFree（Pa）

6）

Pn-1←（xn-2，yn-2）

7）

Pn ← Pn-1

8）

end while

程序后

在上述偽代碼中，GetLine（）表示求得穿過當(dāng)前兩點的直線方程，GetPoint（）表示求得直線M上橫坐標(biāo)范圍為是（xn-2，xn）的所有點，PointFree（）表示當(dāng)前點不處于障礙物區(qū)域。

2.2.4 障礙物擴展策略

在移動機器人路徑規(guī)劃的模擬實驗中通常不考慮機器人的實際寬度，這導(dǎo)致算法規(guī)劃的路徑過于接近障礙物。在實際運行時，可能導(dǎo)致機器人損壞并無法到達目標(biāo)點Pt。針對這一問題，本文提出了障礙物擴展策略。如1.1節(jié)所述地圖劃分為R*S個柵格，柵格對應(yīng)坐標(biāo)范圍是（x1，y1）到（xR，yS）且每個柵格的信息Nij是已知的。障礙物擴展策略就是將所有柵格逐一進行檢測，如果有柵格處于障礙物區(qū)間則將鄰近8個柵格設(shè)置為禁止搜索，即可視為障礙物擴展區(qū)域。采用障礙物擴展策略后，規(guī)劃的路徑與障礙物柵格具有安全距離，并且可以應(yīng)用于具有一定寬度的真實機器人的工程實踐中。

該策略如圖5所示。在圖5中5為障礙物區(qū)域，1、2、3、4、6、7、8、9為障礙物擴展區(qū)域。

障礙物擴展策略的偽代碼如下：

有序號的程序——————————Shift+Alt+Y

程序前

ObsExpansion（（x1，y1），（xR，yS））

1）

for i=1 to R

2）

for? j=1 to S

3）

Pn ←（xi，xj）

4）

if Nij=1

5）

ExtArea（Pn）;

6）

end if

7）

end for

8）

end for

程序后

在上述偽代碼中，ExtArea（）表示探索當(dāng)前點Pn的8個鄰近柵格，處于障礙區(qū)間的柵格不作改變，沒有處于障礙區(qū)間的柵格設(shè)置為障礙物擴展區(qū)。

3 仿真驗證

為驗證改進A*算法的有效性和靈活性，本文在不同環(huán)境下進行了仿真，仿真軟件平臺為Matlab R2017a，硬件平臺為Intel Core i5-3230M 2.6GHz CPU，RAM 4GB。

首先，本文構(gòu)建了一個包含許多障礙物的柵格圖，尺寸為100×100像素（density independent pixels， dip），即X軸坐標(biāo)范圍是[0，100]，Y軸的范圍是[0，100]。在此柵格圖中上方黑色圓點為起點，坐標(biāo)為（50，85），下方黑色圓點為目標(biāo)點，坐標(biāo)為（50，20），黑色區(qū)間代表障礙物，白色為無障礙區(qū)間。并在此柵格圖上，運用傳統(tǒng)A*算法進行路徑規(guī)劃。構(gòu)建的柵格圖和傳統(tǒng)A*算法路徑規(guī)劃仿真結(jié)果如圖6所示。由圖6可得傳統(tǒng)A*算法規(guī)劃的路徑確實存在很多冗余點和拐點。

其次，改進A*算法評價函數(shù)計算方式和在此基礎(chǔ)上進一步改進A*算法評價函數(shù)的權(quán)重比例，其仿真結(jié)果如圖7所示。由圖7可得，改進A*算法評價函數(shù)的計算方式，可以改善最終生成的路徑。再改進評價函數(shù)的權(quán)重比例（加權(quán)求平均得X取值1.1），可進一步優(yōu)化生成路徑，雖然最終生成的路徑冗余點和拐點減少，路徑轉(zhuǎn)彎角度減小，整體更加平滑，但最終生成的路徑中依然存在一些冗余點和拐點。

完成上述兩步改進后再進一步改進A*算法路徑生成策略，以及完成上述三步改進后最后添加障礙物擴展策略，其仿真結(jié)果如圖8所示，而添加障礙物擴展策略后的仿真結(jié)果就是本文改進后A*算法在該地圖上的最終仿真結(jié)果。由圖8可得，通過改進路徑生成策略（本文設(shè)置經(jīng)過2次節(jié)點優(yōu)化策略）最終生成的路徑更進一步減少了路徑中存在的冗余點和拐點。但此時生成的路徑仍然存在過于靠近障礙物區(qū)域的問題，如果將其應(yīng)用于實際的機器人路徑規(guī)劃中，則機器人將與障礙物碰撞。因此，將障礙物擴展策略添加到程序中解決該問題，最終生成的路徑與附近的障礙物保持一定距離，解決了實際機器人與障礙物碰撞的問題。

傳統(tǒng)A*算法及其改進方法的尋路時間數(shù)據(jù)如表1所示。結(jié)合圖6～8可得，改進A*算法評價函數(shù)的具體計算方式和權(quán)重比例，可減少尋路時間、提高算法的效率并改善生成路徑，但最終生成路徑中仍存在很多冗余點和拐點。再改進A*算法的路徑生成策略引入障礙物擴展策略，可進一步優(yōu)化生成路徑，但會增加尋路時間。綜合本文改進方法的優(yōu)缺點，由最終生成路徑和尋路時間可得，本文改進后A*算法優(yōu)化了生成路徑，減少了尋路時間。

另一個柵格地圖是模仿室內(nèi)環(huán)境構(gòu)建的，大小為100×100dip。室內(nèi)環(huán)境包括走廊和房間。具有不同尺寸的矩形被設(shè)置為房間中的障礙物，起點坐標(biāo)為（25，85），目標(biāo)點坐標(biāo)為（70，15）。如圖9到圖10所示，用傳統(tǒng)A*算法、本文改進后A*算法、文獻[17]中的同步雙向A*算法 和文獻[18]中的雙向時效A*算法分別對該柵格地圖進行路徑規(guī)劃，進而對比分析。不同算法的尋路時間數(shù)據(jù)如表2所示。

結(jié)合圖9、10和表2可得，本文改進后A*算法生成路徑的平滑性明顯優(yōu)于其他三大算法，尋路效率也具有較大的優(yōu)勢。此外，改進后A*算法生成的路徑可以使機器人和障礙物保持安全距離，可以滿足工程實踐的需要。

4 結(jié)語

傳統(tǒng)A*算法在障礙物空間中規(guī)劃的路徑一般不是最優(yōu)，它包含很多冗余點和拐點。本文先改進傳統(tǒng)A*算法評價函數(shù)的具體計算方式，減少搜索區(qū)間的計算量，從而提高算法的搜索效率;其次改變評價函數(shù)中權(quán)重比例，以此減少生成路徑中的拐點和冗余點;最后改進傳統(tǒng)A*算法的路徑生成策略，進一步平滑生成路徑。此外，引入障礙物擴展策略使機器人和障礙物保持安全距離，以滿足實際工程需要。在仿真實驗中，與其他五種算法相比，移動機器人可以在障礙物空間中找到安全且更平滑的路徑，縮短了尋路時間，從而證明改進后A*算法對全局路徑規(guī)劃是非常合適和有效的。但改進后的算法仍存在一些不足之處，如該算法只能應(yīng)用在已知的靜態(tài)環(huán)境中，下一步的研究將集中在動態(tài)環(huán)境中，運用A*算法快速規(guī)劃移動機器人全局最優(yōu)且安全的路徑。

參考文獻 （References）

[1]陸新華，張桂林.室內(nèi)服務(wù)機器人導(dǎo)航方法研究[J].機器人，2003，25（1）：80-87.（LU X H， ZHANG G L. Summarization on indoor service robot navigation [J]. Robot， 2003， 25（1）： 80-87.）

[2]CHEN D， LU Q， YIN K， et al. A method for solving local minimum problem of local path planning based on particle swarm optimization [C]// Proceedings of the 2017 Chinese Automation Congress. Piscataway， NJ： IEEE， 2017： 4944-4949.

[3]JEDDISARAVI K， ALITAPPEH R J， PIMENTA L C A， et al. Multi-objective approach for robot motion planning in search tasks [J]. Applied Intelligence， 2016， 45（2）： 1-17.

[4]張超超，房建東.基于定向加權(quán)A*算法的自主移動機器人路徑規(guī)劃[J].計算機應(yīng)用，2017，37（S2）：77-81.（ZHANG C C， FANG J D. Path planning of autonomous mobile robot based on directional weighted A* algorithmm [J]. Journal of Computer Applications， 2017， 37（S2）： 77-81.）

[5]HAO Z-B， HONG B-R， HUANG Q-C. Study of coverage path planning based on grid-map [J]. Application Research of Computers， 2007， 24（10）： 56-58.

[6]PAN H， GUO C， WANG Z. Research for path planning based on improved astart algorithm [C]// Proceedings of the 2017 4th International Conference on Information， Cybernetics and Computational Social Systems. Piscataway， NJ： IEEE， 2017： 225-230.

[7]GUO Y， WANG W， WU S. Research on robot path planning based on fuzzy neural network and particle swarm optimization [C]// Proceedings of the 2017 29th Chinese Control and Decision Conference. Piscataway， NJ： IEEE， 2017： 2146-2150.

[8]MONTIEL O， SEPULVEDA R， OROZCO-ROSAS U. Optimal path planning generation for mobile robots using parallel evolutionary artificial potential field [J]. Journal of Intelligent and Robotic Systems， 2015， 79（2）： 237-257.

[9]韓明，劉教民，吳朔媚，等.粒子群優(yōu)化的移動機器人路徑規(guī)劃算法[J].計算機應(yīng)用，2017，37（8）：2258-2263.（HAN M， LIU J M， WU S M， et al. Path planning algorithm of mobile robot based on particle swarm optimization [J]. Journal of Computer Applications， 2017， 37（8）： 2258-2263.）

[10]NI J， WANG K， HUANG H. Robot path planning based on an improved genetic algorithm with variable length chromosome [C]// Proceedings of the 2016 12th International Conference on Natural Computation， Fuzzy Systems and Knowledge Discovery. Piscataway， NJ： IEEE， 2016： 145-149.

[11]吳天羿，許繼恒，劉建永.基于改進蟻群算法的越野路徑規(guī)劃[J].計算機應(yīng)用，2013，33（4）：1157-1160.（WU T Y， XU J H， LIU J Y. Cross-country path planning based on improved ant colony algorithm [J]. Journal of Computer Applications， 2013， 33（4）： 1157-1160.）

[12]LIU K， ZHANG M. Path planning based on simulated annealing ant colony algorithm [C]// Proceedings of the 2016 9th International Symposium on Computational Intelligence and Design. Piscataway， NJ： IEEE， 2016： 461-466.

[13]LI Y， ZHANG H， ZHU H. IBAS： index based a-star [J]. IEEE Access， 2018， 6： 11707-11715.

[14]JEDDISARAVI K， ALITAPPEH R J， GUIMARAES F G. Multi-objective mobile robot path planning based on A* search [C]// Proceedings of the 2016 6th International Conference on Computer and Knowledge Engineering. Piscataway， NJ： IEEE， 2016： 7-12.

[15]WANG Z， XIANG X. Improved astar algorithm for path planning of marine robot[C]// Proceedings of the 2018 37th Chinese Control Conference. Piscataway， NJ： IEEE， 2018： 296-300.

[16]WANG Q， ZHANG A， QI L. Three-dimensional pathplanning for UAV based on pmproved PSO algorithm [C]// Proceedings of the 2014 26th Chinese Control and Decision Conference. Piscataway， NJ： IEEE， 2014： 3982-3986.

[17]林娜，李天嘯.基于雙向A*算法的城市無人機航路規(guī)劃[J].沈陽航空航天大學(xué)學(xué)報，2016，33（4）：55-60.（LIN N， LI T X. Urban UAV route planning based on bidirectional A* algorithm [J]. Journal of Shenyang Aerospace University， 2016， 33（4）： 55-60.）

[18]高民東，張雅妮，朱凌云.應(yīng)用于機器人路徑規(guī)劃的雙向時效A*算法[J].計算機應(yīng)用研究，2019，36（3）：792-795.（GAO M D， ZHANG Y N， ZHU L Y. Bidirectional time-efficient A* algorithm for robot path planning [J]. Application Research of Computers， 2019， 36（3）： 792-795.）

[19]陳瑤.變電站智能巡檢機器人全局路徑規(guī)劃設(shè)計與實現(xiàn)[D].濟南：山東大學(xué)，2015：94.（CHEN Y. Design and implementation of global path planning for substation intelligent patrol inspection robot[D]. Jinan： Shandong University， 2015： 94.）

[20]向光海.變電站巡檢機器人路徑規(guī)劃系統(tǒng)設(shè)計與實現(xiàn)[D].成都：西南交通大學(xué)，2015：77.（XIANG G H. Design and implementation of path planning system for substation inspection robot [D]. Chengdu： Southwest Jiaotong University， 2015： 77.）

This work is partially supported by the National Natural Science Foundation of China （61603242）， the Open Project of Jiangxi Collaborative Innovation Center of Economic Crime Investigation， Prevention and Control Technology （JXJZXTCX-030）.

the Jiangxi Province Economic Crime Investigation and Prevention and Control Technology Collaborative Innovation Center Open Fund

WANG Zhongyu， born in 1993， M. S. candidate. His research interests include robot control， path planning algorithm.

ZENG Guohui， born in 1975， Ph. D.， associate professor.His research interests include robot control， power electronics and its control technology.

HUANG Bo， born in 1985， Ph. D.， lecturer. His research interests include requirements engineering， software engineering， artificial intelligence.

FANG Zhijun， born in 1971， Ph. D.， professor. His research interests include pattern recognition， intelligence computation， video analysis.