基于WGAN-GP的搜索式路徑規(guī)劃算法

收稿日期：2022-04-20；修回日期：2022-07-04" 基金項目：國家自然基金青年項目；科技部重大研發(fā)計劃資助項目；廣東省重大研發(fā)計劃資助項目；廣東省面上自然基金項目

作者簡介：周齊（1999-），男，廣東汕頭人，碩士研究生，主要研究方向為深度學習與機器人路徑規(guī)劃；楊曉君（1983-），男（通信作者），廣東廣州人，副教授，碩導，博士，主要研究方向為機器學習與數(shù)據(jù)聚類（yangxj18@gdut.edu.cn）；林浩申（1992-），男，湖北武漢人，助理研究員，博士，主要研究方向為機器學習與目標跟蹤；廖倫稼（1996-），男，廣東雷州人，碩士研究生，主要研究方向為機器人控制與路徑規(guī)劃；孫博（1986-），男，山西太原人，講師，博士，主要研究方向為目標跟蹤與數(shù)據(jù)聚類.

摘 要：為了提升搜索式路徑規(guī)劃算法在C字型障礙中的探索效率，提出了一種基于對抗生成網(wǎng)絡的A*算法。首先使用訓練更為穩(wěn)定的梯度懲罰Wasserstein對抗生成網(wǎng)絡（WGAN-GP）生成存在可行路徑的感興趣區(qū)域；然后使用A*算法優(yōu)先探索該區(qū)域，使得路徑規(guī)劃能夠被有效引導；最終形成一條連續(xù)的路徑。經(jīng)過實驗仿真驗證，其相較于傳統(tǒng)A*算法節(jié)約了31%的規(guī)劃時間、減少了22.84%的探索空間，提升了路徑規(guī)劃算法的效率。實驗結果表明，改進的A*算法具有較高的探索效率，能夠更好地應用于機器人路徑規(guī)劃中。

關鍵詞：路徑規(guī)劃；對抗生成網(wǎng)絡；搜索式算法；A*算法

中圖分類號：TP183"" 文獻標志碼：A""" 文章編號：1001-3695（2022）12-015-3626-05

doi：" 10.19734/j.issn.1001-3695.2022.04.0225

Search-based path planning algorithm based on WGAN-GP

Zhou Qi1， Yang Xiaojun1， Lin Haoshen2， Liao Lunjia1， Sun Bo1

（1. School of Information Engineering， Guangdong University of Technology， Guangzhou 510006， China; 2. Chinese People’s Liberation Army Unit 96901， Beijing 100094， China）

Abstract：

In order to improve the exploration efficiency of the search-type path planning algorithm in the C-shaped obstacles， this paper proposed an A* algorithm based on the generative adversarial network. Firstly， the method used a more stable Wasserstein generative adversarial network with gradient penalty（WGAN-GP） to generate regions of interest with a feasible path. Then the algorithm used the A* algorithm to preferentially explore the regions， enabling it to efficiently guide path planning. Finally， it formed a continuous path. According to the experimental simulation verification， compared with the traditional A* algorithm， it saved 31% less planning time and 22.84% less exploration space， and improved the efficiency of the path planning algorithm. Experimental results show that the improved A* algorithm has high exploration efficiency， and it can achieve better application in robot path planning.

Key words：path planning; generative adversarial network; search algorithm; A* algorithm

0 引言

機器人路徑規(guī)劃是機器人自主定位與導航的關鍵技術之一。路徑規(guī)劃算法的核心任務是確定起始點與目標點后，機器人自動避開環(huán)境中各種障礙物，計算并優(yōu)化時間、距離等性能的無碰撞最優(yōu)路徑［1］。自從20世紀60年代起，移動機器人路徑規(guī)劃算法不斷迭代更新，出現(xiàn)了許多經(jīng)典的規(guī)劃算法，如Dijkstra算法、A*算法、D*算法、人工勢場算法以及RRT算法等。

路徑規(guī)劃算法主要分為兩種，分別是基于采樣的規(guī)劃算法與基于圖的搜索算法。采樣式算法典型代表有PRM算法、RRT與RRT*算法等；搜索式算法的代表有Dijkstra算法、A*算法與D*算法等。其中，A*算法綜合了Dijkstra算法與廣度優(yōu)先搜索算法（BFS）的優(yōu)勢，通過啟發(fā)式函數(shù)的作用使其能夠快速尋找到路徑［2］。在搜索式算法中，A*算法的穩(wěn)定性與實用性已經(jīng)被證明，因而衍生出由A*算法改進的應用于不同領域的路徑規(guī)劃算法：楊明亮等人［3］提出的通過A*與動態(tài)窗口法（dynamic window approach，DWA）相結合的混合算法，能夠縮短算法運行時間并優(yōu)化路徑復雜度；陳萬通等人［4］為解決傳統(tǒng)A*算法拐彎角度大、搜索路徑節(jié)點過多等問題，提出一種基于扇形領域擴展的同步雙向A*搜索算法；為解決移動機器人最短路徑遍歷所有目標點的路徑規(guī)劃問題，李孟錫等人［5］提出一種基于啟發(fā)信息擴展節(jié)點擴展的A*算法，并與混合蟻群算法相結合，減少搜索節(jié)點并增強全局搜索能力；Hong等人［6］提出了結合A*搜索算法與最小snap軌跡生成的實用性路徑規(guī)劃方法，實現(xiàn)路徑點平滑的最小快拍軌跡連接；為解決自動駕駛的路徑規(guī)劃問題，Zhang等人［7］提出一種改進的A*路徑規(guī)劃算法，解決了傳統(tǒng)的A*算法中生成許多不必要的轉折點從而使得路徑不夠平滑等問題。A*算法是解決路徑規(guī)劃問題的搜索式算法代表，前人已對其進行了廣泛的應用、改進與擴展，故本文采用的搜索式算法為A*算法并對其進行改進。

A*算法因其具有完備性、可擴展性以及高效的探索機制，從而獲得廣泛的應用，例如面向AGV的倉庫路徑規(guī)劃［8］、無人機航路自主規(guī)劃［9］以及游戲NPC的智能移動設計［10］等。然而A*算法仍然存在一些待解決的問題：如圖1所示，在一些特定的區(qū)域內（C字型障礙），A*算法從起始點（紅色）往目標點（藍色）尋找路徑（橙色）的過程中，需要均勻探索全局空間（青色區(qū)域為A*算法探索過的區(qū)域），從而降低算法的效率（見電子版）。針對上述問題，本文通過Zhang等人［11］提出的基于對抗生成網(wǎng)絡對采樣式路徑規(guī)劃算法改進思路，將其應用于搜索式算法中。

本文提出了一種新的改進算法：首先使用收斂較快、訓練效果更穩(wěn)定的梯度懲罰Wasserstein對抗生成網(wǎng)絡生成出存在可行路徑的感興趣區(qū)域（region of interest，RoI），然后使用A*算法優(yōu)先在感興趣區(qū)域中進行探索，使得路徑探索能被有效引導；若無法探索到目標點，則進行全局探索。與以往的改進算法不同，本方案在A*算法之前使用GAN生成可行路徑的感興趣區(qū)域，而其他的改進算法，例如雙向時效性［1］與雙向搜索機制算法［12］是改進其啟發(fā)函數(shù)或者其搜索機制，從而提升A*算法的搜索效率，故本文僅與A*算法進行對比以展示本方案的可行性。圖2為不同改進算法的結構對比示意圖。

最后，本文對不同環(huán)境不同任務進行仿真與結果對比分析；結果表明，本文算法能夠提升路徑規(guī)劃的效率，同時優(yōu)化全局空間的探索效率，極大地減少了算法探索時間。

1 A*算法

傳統(tǒng)A*算法是基于啟發(fā)函數(shù)的搜索式算法，其主要流程為：將起始點設置為當前的柵格，并計算當前柵格周圍鄰近柵格的f（n）值，選取f（n）值最小的柵格作為當前柵格后，進行循環(huán)檢測，直到檢測到目標點后結束循環(huán)。其中f（n）為代價函數(shù)，其一般形式為

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

其中：f（n）為當前柵格的總代價值；g（n）為從初始柵格到當前柵格所消耗的真實代價值；h（n）為機器人當前柵格到目標柵格的代價值。一般A*算法使用歐幾里德距離為啟發(fā)函數(shù)來計算機器人的移動代價，h（n）的表達式為

h（n）=（xg－xn）2+（yg－yn）2（2）

其中：xg、xn為目標柵格與當前柵格的橫坐標；yg、yn為目標柵格與當前柵格的縱坐標。

A*算法首先初始化χopen（V，E）與χvisited（E）兩個空集，同時定義x為當前柵格點，χf為存放父節(jié)點的集合，χneis為當前柵格周圍鄰近的柵格點，χfree為非障礙物區(qū)域。其中χneis需要滿足

χneis∈χfree（3）

根據(jù)上述主要流程與變量設定，A*算法的流程如下：

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

輸入：χopen（V，E）、χvisited（E）、χneis、χf；路徑起始點xstart；路徑目標點xgoal。

輸出：路徑集合χPath（E）。

a）x=xstart //初始化

b）通過式（1）計算當前點的代價值cost

c）χopen（cost，x） //將當前點的代價值與坐標放進集合中

d）χvisited（x） //將當前點坐標放進集合中

e）while χopen（V，E）不為空集 do

（a）" x←χopen（V，E） /*從χopen（V，E）中尋找代價最小的點為當前點并將其從集合中移除*/

（b）" if x≠xgoal then

（c）"" 將不在χvisited（E）集的鄰近點放進χneis集中

（d）" "根據(jù)式（1）計算χneis集中鄰近點的代價cost

（e）"" χopen（cost，χneis） //將鄰近點代價與坐標放入集合中

（f）"" χvisited（χneis） //將鄰近點坐標放入集合中

（g）"" 將當前點的坐標作為鄰近點的父節(jié)點放進集合χf中，執(zhí)行后跳轉步驟a）

（h）" else then

（i）"" χPath（χf） //通過χf追溯每個父節(jié)點坐標放入路徑集中

（j）"" return χPath（E）

f） end while

h） return failure

2 基于WGAN-GP的A*算法

本文將在此章中詳細介紹帶有梯度懲罰的Wasserstein對抗生成網(wǎng)絡模型理論以及構建方法，并描述改進算法的流程。其中，模型的輸入為RGB圖像，分別表示A*算法所需要探索的地圖信息maps、包含起始點xstart與目標點xgoal的點坐標信息points；模型的輸出為RGB圖像，表示存在可行路徑的感興趣區(qū)域信息。

2.1 數(shù)據(jù)集生成

為解決A*算法在具有C字型障礙的地圖中探索效率低等問題，本文著重設計了多個具有C字型障礙物的地圖。其中地圖以及起始點目標點均由圖像數(shù)據(jù)表示。

如圖3所示，第1行數(shù)據(jù)代表地圖信息maps，其中黑色為障礙物區(qū)域，白色則為自由空間區(qū)域；從地圖信息中的自由空間區(qū)域隨機篩選20～50個坐標點代表點坐標信息points，如第2/4/6行所示，其中紅色的數(shù)據(jù)為起始點xstart、藍色數(shù)據(jù)為目標點xgoal；第3/5/7行代表感興趣區(qū)域信息，通過每張地圖與對應的起始點與目標點坐標信息，使用快速遍歷隨機樹算法（rapidly-exploring random tree，RRT）進行200次運算后在圖像上使用綠色像素繪制出所有可行路徑區(qū)域。

2.2 模型結構

對于對抗生成網(wǎng)絡，基本框架包括生成器G與判別器D。生成器從噪聲空間Z中獲得噪聲樣本z并輸出圖像，其中Z需要滿足Z∈Rn；判別器接收來自訓練樣本空間X中的圖像x和生成的圖像G（z）并將其區(qū)分。生成器的目標在于“欺騙”判別器，而判別器則試圖將訓練樣本與生成樣本進行區(qū)分，兩者之間不斷對抗，最終使得生成器能夠輸出擁有訓練樣本空間特征的生成圖像G（z）。

傳統(tǒng)的對抗生成網(wǎng)絡雖然能夠實現(xiàn)圖像生成，但是其存在訓練不穩(wěn)定以及容易模式崩塌等問題，故本文使用Gulrajani等人［13］提出的帶有梯度懲罰（gradient penalty）的WGAN模型，即WGAN-GP模型。

2.2.1 WGAN-GP理論

傳統(tǒng)的對抗生成網(wǎng)絡存在一個問題：如果判別器D太過于強大，生成器G則會出現(xiàn)梯度消失的現(xiàn)象，并使得損失函數(shù)無法收斂；如果生成器G訓練太好則判別器D出現(xiàn)梯度爆炸的現(xiàn)象。

為了解決這種問題，WGAN-GP在GAN的基礎上進行改進，采用Wasserstein距離作為度量生成數(shù)據(jù)與訓練樣本空間數(shù)據(jù)的代價，將訓練樣本與生成樣本形成聯(lián)合分布后對期望值取下限進行優(yōu)化，其目標函數(shù)設定為

minGmaxD（Ex～Ρdata（X）［D（x）］－Εz～ΡZ（z）［D（G（z））］）（4）

其中：x為來自訓練樣本X的數(shù)據(jù)；z為噪聲樣本。由于生成器G的目的是使得生成數(shù)據(jù)盡可能與訓練樣本數(shù)據(jù)相似，故生成器的目標函數(shù)需最小化以減少真實數(shù)據(jù)與生成數(shù)據(jù)的分布差異；對于判別器D，其目的是為了更好地區(qū)分生成數(shù)據(jù)與訓練樣本數(shù)據(jù)，故其目標函數(shù)需最大化以增加真實數(shù)據(jù)與生成數(shù)據(jù)的分布距離。

WGAN-GP模型為了防止出現(xiàn)梯度爆炸和梯度消失的現(xiàn)象，通過額外設置一個梯度懲罰項代替權重裁剪以滿足判別器D損失一階Lipschitz函數(shù)約束，從而增強梯度的可控性。梯度懲罰公式如下：

λΕ～Ρ（）［（‖D（）‖2－1）2］（5）

其中：是對生成數(shù)據(jù)和訓練樣本數(shù)據(jù)各進行采樣后，在兩點的連線上再次進行隨機插值采樣，其定義為

=εxr+（1－ε）xg

s.t. xr～Ρdata（X），xg～ΡZ（G（z）），ε～U［0，1］（6）

其中：xr為采樣的訓練樣本數(shù)據(jù)；xg為采樣的生成數(shù)據(jù)；ε為來自實域的隨機參數(shù)，其值為0～1。梯度懲罰項通過式（6）對生成數(shù)據(jù)與訓練樣本數(shù)據(jù)集中區(qū)域進行采樣后，在式（5）中計算判別器梯度Norm的二范數(shù)，使其能夠約束在1附近，使得判別器損失梯度變化趨于緩和。

由于梯度懲罰僅在判別器D參數(shù)更新時起作用，同時為了更好地控制生成過程，通過定義y∈Y作為條件，其中Y為條件空間。故判別器D的目標函數(shù)通過式（4）與（5）可以定義為

maxθ （G，D）=Εx，y～Ρdata（X，Y）［D（x，y）］－

Εz～ΡZ（z），y～Ρdata（Y）［D（G（z，y），y）］－

λΕ～Ρ（），y～Ρdata（Y）［（‖D（，y）‖2－1）2］（7）

其中：判別器的目的是盡可能拉大生成數(shù)據(jù)與訓練樣本數(shù)據(jù)之間的差距，以此對抗生成器縮小生成數(shù)據(jù)與訓練樣本數(shù)據(jù)的分布差距的趨勢。由于生成器G與式（4）中第一項無關，故簡化后可得到生成器G的目標函數(shù)為

minθ （G，D）=－Εz～ΡZ（z），y～Ρdata（y）［D（G（z，y），y）］（8）

最后通過上述對目標函數(shù)的設定，可獲得對應的損失函數(shù)；在之后訓練的過程中，將生成器G與判別器D交替訓練，使得生成能力與判別能力不斷增強，生成器能夠更好地學習到訓練樣本空間的特征。

2.2.2 損失函數(shù)

本文使用的模型中，將地圖信息maps和點坐標信息points定義為條件空間Y的兩個條件，并將感興趣區(qū)域信息定義為訓練樣本空間X；其中，地圖、點坐標與感興趣區(qū)域的信息都來源于2.1節(jié)的數(shù)據(jù)集。

為了增強網(wǎng)絡能夠對點坐標信息與地圖信息的敏感度，本文分別將來自地圖信息maps的圖像M和來自點坐標信息points的圖像P輸入生成網(wǎng)絡與判別網(wǎng)絡中，模型整體架構如圖4所示。

通過模型架構可發(fā)現(xiàn)，生成器輸入噪聲、條件空間Y的地圖信息maps與點坐標信息points后，輸出存在可行路徑的感興趣區(qū)域。判別器同樣輸入條件空間Y的數(shù)據(jù)，同時輸入來自訓練樣本空間X的感興趣區(qū)域信息以及生成網(wǎng)絡生成的感興趣區(qū)域信息，通過訓練更好地區(qū)分真假數(shù)據(jù)樣本。

根據(jù)式（8）可定義生成器G的損失函數(shù)為

G=－Εz～ΡZ（z），M，P～ΡY（maps，points）［D（G（z，M，P），M，P）］（9）

其中：M為來自地圖信息maps的圖像；P為來自點坐標信息points的圖像。生成器損失函數(shù)能夠減少生成的感興趣區(qū)域信息與來自訓練樣本的感興趣區(qū)域信息之間的分布差異，從而增強生成器的能力。

根據(jù)式（7）可定義判別器D的損失函數(shù)為

D=Εz～ΡZ（z），M，P～ΡY（maps，points）［D（G（z，M，P），M，P）］－

ΕS～Ρdata（X），M，P～ΡY（maps，points）［D（S，M，P）］+

λΕ～Ρ（），M，P～ΡY（maps，points）［（‖D（，M，P）‖2－1）2］

s.t. =εxr+（1－ε）xg，xr～Ρdata（S），

xg～ΡZ（G（z，M，P）），ε～U［0，1］（10）

其中：M為來自地圖信息maps的圖像；P為來自點坐標信息points的圖像；S為來自訓練樣本空間X的感興趣區(qū)域圖像；為通過式（6）對生成數(shù)據(jù)G（z，M，P）與感興趣區(qū)域S隨機插值采樣所獲得的數(shù)據(jù)；λ為梯度懲罰的參數(shù)，用于調整懲罰力度。判別器損失的目的是盡可能區(qū)分生成樣本與訓練樣本之間的分布差距，以此對抗生成器減少分布差距的趨勢。

2.2.3 網(wǎng)絡設計

根據(jù)圖4的模型架構，本文確定了用于生成感興趣區(qū)域的WGAN-GP模型整體架構，再通過這個架構詳細設計生成網(wǎng)絡與判別網(wǎng)絡。

生成網(wǎng)絡的輸入為64×64×1的噪聲圖像，64×64×3的地圖圖像M以及64×64×3的點坐標圖像P；輸出為64×64×3的感興趣區(qū)域圖像。將M和P分別輸入到16通道的卷積層中，并將噪聲圖像輸入到32通道的卷積層后，使用維度連接將特征圖沿著通道連接起來，為后續(xù)圖像編碼提供多通道特征。

如圖5所示，生成網(wǎng)絡模型遵循編碼器—解碼器體系結構，其中編碼網(wǎng)絡包括block1～block4。block1由三個殘差網(wǎng)絡層構成，其余的block由Convolution-BatchNormalization-ReLU層和三個殘差網(wǎng)絡層連接構成；在這里，將每一個編碼網(wǎng)絡block對應輸出的特征值定義為I1，I2，I3，I4。解碼器網(wǎng)絡包括block5～block7，每一個解碼器與編碼器相似，僅將卷積層替換成反卷積層；同樣將解碼網(wǎng)絡對應輸出的特征值定義為I5，I6，I7。為了能夠增加網(wǎng)絡對上下文信息的敏感度，將I3與I5維度融合后輸入block6，I2與I6維度融合后輸入block7，I1與I7融合后輸入由Convolution-ReLU構成的網(wǎng)絡層中。最后，將特征值壓縮成3通道的圖像并使用tanh函數(shù)激活。

判別網(wǎng)絡與生成網(wǎng)絡所輸入的第一層通道相同，但判別網(wǎng)絡在第一層通道中加入了自注意力機制（self-attention）模塊，使得網(wǎng)絡能夠考慮全局信息。

自注意力機制模塊通過殘差網(wǎng)絡連接到卷積網(wǎng)絡中，其公式如下：

oa=γq+ oc（11）

其中：q 為自注意力機制的輸出；oc為最后一層的輸出；oa為最終的輸出；γ為用于調整自注意力比例的參數(shù)。自注意力機制可以定義為

q=softmax（θ（oc）Tφ（oc））g（oc）（12）

其中：θ（oc）與φ（oc）用于計算自相關量；g（oc）用于壓縮維度的線性嵌入量；θ（oc）、φ（oc）與g（oc）定義為

θ（oc）=Wθoc，

φ（oc）=Wφoc，

g（oc）=Wgoc（13）

其中：Wθ、Wφ與Wg為通過卷積神經(jīng)網(wǎng)絡提取的權重參數(shù)。

自注意機制的本質思維是從大量信息中有選擇地篩選少量的重要信息并聚焦在重要信息上，所以通過計算θ（oc）與其對應φ（oc）的相關性，得到對應g（oc）的權重系數(shù)。由于權重系數(shù)為0～1，故需softmax函數(shù)將自相關量進行約束，最終與g（oc）進行加權求和后輸出自注意力機制q 。根據(jù)式（11）～（13）可獲得自注意力模塊定義為

oa=γ（softmax （o TcWTθWφoc）Wgoc）+oc（14）

由圖6所示，判別器網(wǎng)絡在第一層特征數(shù)據(jù)中加入自注意力模塊。由于判別器網(wǎng)絡輸入的數(shù)據(jù)不同，故在第一層的自注意力機制權重參數(shù)γ不同，為了使得網(wǎng)絡將聚焦到生成數(shù)據(jù)與訓練樣本數(shù)據(jù)上，分別將地圖信息與點坐標信息的權重設置為0.25，將感興趣區(qū)域信息設置為0.5。判別器的編碼網(wǎng)絡由6個Convolution-InstanceNormlization-LeakyReLU層構成，其中，第2層與第4層同樣也加入了自注意力模塊，最終網(wǎng)絡輸出1×1×1的特征值。

2.3 算法流程

通過第1章對A*算法的闡述以及2.2節(jié)中對WGAN-GP網(wǎng)絡模型的詳細描述，設計了基于WGAN-GP的A*算法。

算法2 基于WGAN-GP的A*算法

輸入：maps、points。

輸出：路徑集合χPath（E）。

a） S←RoIsGenerator（maps，points）

//使用GAN生成存在路徑的感興趣區(qū)域

b） χPath（E）←GanA*（maps，points，S） //生成路徑

c） if χPath（E）= do

S=χfree，執(zhí)行后轉步驟b） //變?yōu)槿炙阉?/p>

d） return χPath（E）

由于地圖信息、點坐標信息與WGAN-GP網(wǎng)絡輸出的感興趣區(qū)域為圖像信息，GanA*算法需要將圖像信息轉換為點集合，才能進行A*路徑規(guī)劃算法。

3 仿真結果與分析

本章主要描述實驗的評估方法并對實驗仿真結果進行分析。在2.1節(jié)中闡述了數(shù)據(jù)集的結構，并生成28 473組數(shù)據(jù)，其中22 425組數(shù)據(jù)用于訓練，其余的6 048組數(shù)據(jù)用于驗證。將式（10）中判別器損失函數(shù)梯度懲罰項參數(shù)λ設定為10，判別器與生成器的學習率設定為0.000 1，并使用參數(shù)為β1=0，β2=0.9的Adam優(yōu)化器，在NVIDIA RTX3090上使用PyTorch進行100個epoch訓練。

3.1 評估方法

由于對抗生成網(wǎng)絡生成的圖像作用于搜索式路徑規(guī)劃算法中，所以需要評估路徑區(qū)域是否連通以及WGAN-GP模型的泛化能力，并對傳統(tǒng)A*算法與基于WGAN-GP的A*算法之間的探索區(qū)域與算法效率進行對比。

3.1.1 連通性

由于圖像作用于路徑規(guī)劃算法中，所以本文使用連通性評估圖像的質量，而不是采用傳統(tǒng)的直方圖等度量指標。如圖7所示，將生成的區(qū)域設定為非障礙區(qū)域χfree并表示為白色，然后僅在非障礙區(qū)域中使用A*算法，若能夠找到路徑則說明生成區(qū)域是連通的。

3.1.2 泛化能力

為了測試對抗生成網(wǎng)絡在不同實驗環(huán)境下的性能，本文設計了新的地圖作為測試集，并在地圖中非障礙物區(qū)域隨機生成了100個起始點與目標點，用于評估網(wǎng)絡的泛化能力，地圖樣例如圖8所示。

3.1.3 A*的性能改進

為了更加直觀地體現(xiàn)本文改進算法性能的提升效果，本文使用探索區(qū)域與規(guī)劃時間這兩個指標來比較A*算法與基于WGAN-GP的A*算法。探索區(qū)域代表對內存空間的要求，規(guī)劃時間指的是規(guī)劃出可行路徑所消耗的時間。這兩個指標反應了算法在實際應用的可行性。

3.2 結果與分析

3.2.1 連通性

通過3.1.1節(jié)對連通性評估方法的講解，本文使用6 048組驗證集數(shù)據(jù)輸入WGAN-GP模型中并使其生成感興趣區(qū)域圖像，對其進行連通性測試。通過實驗證明成功率達到了90.4%，說明在不同條件下本文的模型能夠生成較高質量的圖像用于A*算法中。

3.2.2 泛化能力

通過3.1.2節(jié)的描述，本文使用測試集來測試網(wǎng)絡的泛化能力。如圖8所示，本文創(chuàng)建了與數(shù)據(jù)集完全不同的地圖信息，并在地圖中非障礙物區(qū)域隨機生成100組點坐標信息構成測試集。圖9所示為測試集生成感興趣區(qū)域效果。

同時對測試集生成的圖像進行連通性評估，實驗表明測試集的連通性達到81.8%。

3.2.3 算法對比分析

通過使用6 048組驗證集數(shù)據(jù)對A*算法以及本文算法進行實驗對比，并計算出路徑規(guī)劃算法所需的探索空間以及規(guī)劃時間。如圖10所示，第一行表示A*算法的規(guī)劃圖，其中青色為路徑規(guī)劃算法探索過的區(qū)域，橙色為規(guī)劃出的路徑；第二行表示基于WGAN-GP的A*算法的規(guī)劃圖，綠色表示通過對抗生成網(wǎng)絡生成的感興趣區(qū)域，青色為算法探索過的區(qū)域，橙色表示最終規(guī)劃出的路徑（見電子版）。

在3.1.3節(jié)中介紹了用于評估算法改進的兩個指標，對圖10所展示的地圖分別運行A*算法以及本文改進的算法，并將其規(guī)劃時間與探索區(qū)域進行比較，性能對比如圖11所示。

最后對6 048組驗證集數(shù)據(jù)進行性能評估與統(tǒng)計，實驗表明，本文提出的基于WGAN-GP的A*算法能夠減少22.84%的探索區(qū)域，并節(jié)約31%的規(guī)劃時間。

為了能夠體現(xiàn)本文算法具有的廣泛應用性，將用于測試WGAN-GP模型泛化能力的測試集

進行評估與統(tǒng)計。實驗表明，在完全不同于數(shù)據(jù)集的環(huán)境中，本文算法能夠減少19.37%的探索區(qū)域，節(jié)約24.9%的規(guī)劃時間。圖12所示為測試集路徑規(guī)劃的效果與性能對比。

3.2.4 實驗結論

通過上述的實驗結果顯示，對抗生成網(wǎng)絡生成的存在路徑概率較高的感興趣區(qū)域圖像能夠有效地引導A*算法規(guī)劃路徑，且路徑生成可靠性較高。實驗證明本文算法能夠減少探索區(qū)域、節(jié)約路徑規(guī)劃時間，極大地提升了算法的效率。

4 結束語

本文針對傳統(tǒng)的A*算法進行改進研究，以解決A*算法在C字型障礙物地圖中出現(xiàn)均勻全局搜索的現(xiàn)象；基于梯度懲罰Wasserstein對抗生成網(wǎng)絡的搜索式算法在傳統(tǒng)的A*算法上進行了改進：首先使用對抗生成網(wǎng)絡輸出存在路徑概率較高的感興趣區(qū)域，然后使用A*算法優(yōu)先探索該區(qū)域，若無法在區(qū)域內尋找到目標點，則將進行全局探索；結果表明該算法路徑規(guī)劃結果可靠性較好，能夠應用于機器人路徑規(guī)劃中。

本文下一步將對生成的路徑進行改進并繼續(xù)研究：在網(wǎng)絡模型生成的數(shù)據(jù)中引入圖論，使其賦予其代價值，最后使用A*算法按照代價最小原則進行路徑規(guī)劃。

參考文獻：

［1］高民東，張雅妮，朱凌云. 應用于機器人路徑規(guī)劃的雙向時效A*算法 ［J］. 計算機應用研究，2019，36（3）： 792-795，800. （Gao Mindong，Zhang Yani，Zhu Lingyun. Two-way aging A* algorithm applied to robot path planning ［J］. Application Research of Compu-ters，2019，36（3）： 792-795，800.）

［2］唐晉韜，王挺，王戟. 適合復雜網(wǎng)絡分析的最短路徑近似算法 ［J］. 軟件學報，2011，22（10）： 2279-2290. （Tang Jintao，Wang Ting，Wang Ji. Shortest path approximation algorithm suitable for complex network analysis ［J］. Journal of Software，2011，22（10）： 2279-2290.）

［3］楊明亮，李寧. 改進A*算法的移動機器人路徑規(guī)劃 ［J］. 機械科學與技術，2022，41（5）： 795-800. （Yang Mingliang，Li Ning. Mobile robot path planning with an improved A* algorithm ［J］. Mechanical Science and Technology for Aerospace Engineering，2022，41（5）： 795-800.）

［4］陳萬通，刁天茹，賈吉慶，等. 基于扇形領域擴展的同步雙向A*算法 ［J］. 計算機應用研究，2022，39（1）： 118-122，127. （Chen Wantong，Diao Tianru，Jia Jiqing，et al. Synchronous bidirectional A* algorithm based on sector domain expansion ［J］. Application Research of Computers，2022，39（1）： 118-122，127.）

［5］李孟錫，何博俠，周俁. 基于A*和蟻群算法的移動機器人多目標路徑規(guī)劃方法 ［J］. 機械與電子，2021，39（6）： 61-65，69. （Li Mengxi，He Boxia，Zhou Yu. Multi-objective path planning method for mobile robots based on A* and ant colony algorithms ［J］. Machi-nery amp; Electronics，2021，39（6）： 61-65，69.）

［6］Hong Y，Kim S，Kim Y，et al. Quadrotor path planning using A* search algorithm and minimum snap trajectory generation ［J］. ETRI Journal，2021，43（6）：1013-1023.

［7］Zhang Jing，Liu Zengyuan，Wang Yi，et al. Research on effective path planning algorithm based on improved A* algorithm ［J］. Journal of Physics： Conference Series，2022，2188（1）：012014.

［8］湯家軍，王忠. 一種面向AGV路徑規(guī)劃的改進A*算法 ［J］. 電子制作，2022，30（3）： 60-62，46. （Tang Jiajun，Wang Zhong. An improved A* algorithm for AGV path planning ［J］. Practical Electronics，2022，30（3）： 60-62，46.）

［9］高暉，陳欣，夏云程. 無人機航路規(guī)劃研究 ［J］. 南京航空航天大學學報，2001，33（2）： 135-138. （Gao Hui，Chen Xin，Xia Yuncheng. Research on UAV air route planning ［J］. Journal of Nanjing University of Aeronautics and Astronautics，2001，33（2）： 135-138.）

［10］劉大瑞，錢程，林濤. 基于多目標A*算法的游戲NPC路徑規(guī)劃 ［J］. 計算機應用研究，2014，31（8）： 2279-2282. （Liu Darui，Qian Cheng，Lin Tao. Game NPC path planning based on the multi-objective A* algorithm ［J］. Application Research of Computers，2014，31（8）： 2279-2282.）

［11］Zhang Tianyi，Wang Jiankun，Meng M Q H. Generative adversarial network based heuristics for sampling-based path planning ［J］. IEEE/CAA Journal of Automatica Sinica，2022，9（1）： 64-74.

［12］孔繼利，張鵬坤，劉曉平. 雙向搜索機制的改進A*算法研究 ［J］. 計算機工程與應用，2021，57（8）： 231-237. （Kong Jili，Zhang Pengkun，Liu Xiaoping. Improved A* algorithm of two-way search mechanism ［J］. Computer Engineering and Applications，2021，57（8）： 231-237.）

［13］Gulrajani I，Ahmed F，Arjovsky M，et al. Improved training of Wasserstein GANs ［C］// Advances in Neural Information Processing Systems.California：Curran Associates Inc.，2017： 5767-5777.