王中玉 曾國(guó)輝 黃勃 方志軍

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

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

中圖分類號(hào)：TP242.6

文獻(xiàn)標(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 引言

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

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

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

1 A*算法規(guī)劃?rùn)C(jī)器人路徑

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

1.1 環(huán)境建模

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

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

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

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

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

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

Nij=0， 無(wú)障礙

1，有障礙 （2）

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

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

1.2 A*算法引入

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

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

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

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

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

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

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

2.1 A*算法的實(shí)施

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

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

具體步實(shí)施驟如下：

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

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

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

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

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

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

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

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

2.2 A*算法的改進(jìn)

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

2.2.1 改進(jìn)評(píng)價(jià)函數(shù)計(jì)算方式

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

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

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

在式（6）中c（n）是當(dāng)前點(diǎn)Pn和父節(jié)點(diǎn)Pn-1的成本函數(shù)，表達(dá)式如式（8）所示，g′（n-1）是父節(jié)點(diǎn)Pn-1的過(guò)去成本函數(shù)，表達(dá)式如式（9）所示。在計(jì)算當(dāng)前點(diǎn)Pn的評(píng)價(jià)函數(shù)值時(shí)，由于父節(jié)點(diǎn)Pn-1的過(guò)去成本函數(shù)g′（n-1）是已知的，所以，只需要計(jì)算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），因?yàn)閏（n）是計(jì)算當(dāng)前點(diǎn)Pn和其相鄰父節(jié)點(diǎn)Pn-1歐氏距離，g（n）是計(jì)算當(dāng)前點(diǎn)Pn和起點(diǎn)Ps的歐氏距離，當(dāng)前點(diǎn)Pn和起點(diǎn)Ps距離的增大時(shí)g（n）的計(jì)算量隨之增大，所以對(duì)于任意當(dāng)前點(diǎn)Pn的c（n）計(jì)算量一定小于等于g（n）的計(jì)算量。在整個(gè)規(guī)劃路徑中需要探索大量節(jié)點(diǎn)，改進(jìn)后算法可節(jié)省大量計(jì)算，減少尋路時(shí)間。

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

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

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

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

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

2.2.2 改進(jìn)評(píng)價(jià)函數(shù)權(quán)重比例

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

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

本文構(gòu)建的兩項(xiàng)權(quán)重系數(shù)關(guān)系如式（13）所示，在式（13）中X為自變量，取值范圍是[0，+∞），兩項(xiàng)權(quán)重系數(shù)之和為1，當(dāng)自變量X從0變化到+∞時(shí)，第一項(xiàng)權(quán)重系數(shù)從1減少至0，第二項(xiàng)權(quán)重系數(shù)從0增加到1，兩者成反比例關(guān)系，將該權(quán)重系數(shù)引入A*算法的評(píng)價(jià)函數(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)重比例的評(píng)價(jià)函f′（n）如式（14）所示。在式（14）中，隨著X取值不同，過(guò)去成本函數(shù)g′（n）和當(dāng)前成本函數(shù)h（n）權(quán)重范圍都是0～1。當(dāng)X取值為1時(shí)，可得式（15）。與式（7）相比，搜索相同區(qū)間其評(píng)價(jià)函數(shù)值等比例縮小。

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

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

2.2.3 改進(jìn)路徑生成策略

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

并判斷當(dāng)前點(diǎn)Pn和其祖父節(jié)點(diǎn)Pn-2（xn-2，yn-2）之間是否存在障礙物，即作一條連接當(dāng)前點(diǎn)Pn和其祖父節(jié)點(diǎn)Pn-2的直線M，由于已知當(dāng)前節(jié)點(diǎn)Pn和其祖父節(jié)點(diǎn)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）之間線上的所有點(diǎn)Pa，并逐個(gè)判斷這些點(diǎn)是否處于障礙物區(qū)，如果有點(diǎn)處于障礙物區(qū)間，則不作改變。如果所有點(diǎn)Pa都不在障礙物區(qū)，則刪除當(dāng)前點(diǎn)Pn的父節(jié)點(diǎn)Pn-1指向其祖父節(jié)點(diǎn)Pn-2。當(dāng)前點(diǎn)Pn優(yōu)化后，依次對(duì)下一節(jié)點(diǎn)進(jìn)行優(yōu)化，直到起點(diǎn)為止完成第1次路徑優(yōu)化。改進(jìn)后A*算法可設(shè)置多次優(yōu)化，能夠刪除大量冗余點(diǎn)，優(yōu)化生成路徑。該策略如圖4所示。

改進(jìn)路徑生成策略的偽代碼如下：

有序號(hào)的程序——————————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（）表示求得穿過(guò)當(dāng)前兩點(diǎn)的直線方程，GetPoint（）表示求得直線M上橫坐標(biāo)范圍為是（xn-2，xn）的所有點(diǎn)，PointFree（）表示當(dāng)前點(diǎn)不處于障礙物區(qū)域。

2.2.4 障礙物擴(kuò)展策略

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

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

障礙物擴(kuò)展策略的偽代碼如下：

有序號(hào)的程序——————————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)前點(diǎn)Pn的8個(gè)鄰近柵格，處于障礙區(qū)間的柵格不作改變，沒(méi)有處于障礙區(qū)間的柵格設(shè)置為障礙物擴(kuò)展區(qū)。

3 仿真驗(yàn)證

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

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

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

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

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

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

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

4 結(jié)語(yǔ)

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

參考文獻(xiàn) （References）

[1]陸新華，張桂林.室內(nèi)服務(wù)機(jī)器人導(dǎo)航方法研究[J].機(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*算法的自主移動(dòng)機(jī)器人路徑規(guī)劃[J].計(jì)算機(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)化的移動(dòng)機(jī)器人路徑規(guī)劃算法[J].計(jì)算機(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]吳天羿，許繼恒，劉建永.基于改進(jìn)蟻群算法的越野路徑規(guī)劃[J].計(jì)算機(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*算法的城市無(wú)人機(jī)航路規(guī)劃[J].沈陽(yáng)航空航天大學(xué)學(xué)報(bào)，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)用于機(jī)器人路徑規(guī)劃的雙向時(shí)效A*算法[J].計(jì)算機(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]陳瑤.變電站智能巡檢機(jī)器人全局路徑規(guī)劃設(shè)計(jì)與實(shí)現(xiàn)[D].濟(jì)南：山東大學(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]向光海.變電站巡檢機(jī)器人路徑規(guī)劃系統(tǒng)設(shè)計(jì)與實(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.