楊肖寧，程承旗，陳 波，童曉沖，何 靜

（1. 北京大學(xué) 工學(xué)院，北京 100871；2. 信息工程大學(xué) 地理空間信息學(xué)院，河南 鄭州 450001；3. 河南大學(xué)商學(xué)院，河南 開封 475001）

0 引 言

柵格地圖的路徑規(guī)劃問題是指在柵格地圖環(huán)境中以較高效率規(guī)劃出一條從起始點(diǎn)到目標(biāo)點(diǎn)的最優(yōu)或次優(yōu)無碰撞的路徑。對該問題的研究，在移動(dòng)機(jī)器人、計(jì)算機(jī)游戲、人工智能等領(lǐng)域都具有重要意義。近年來許多學(xué)者和專家研究了多種應(yīng)用于柵格地圖的路徑規(guī)劃算法，如蟻群算法[1]、遺傳算法[2]、神經(jīng)網(wǎng)絡(luò)法[3]、人工勢場法[4]、A*算法[5]等，其中，A*算法作為成熟的啟發(fā)式算法[6]，在移動(dòng)機(jī)器人等領(lǐng)域已得到廣泛應(yīng)用和驗(yàn)證[7]。

A*算法[5]是Hart等人在1968年提出的一種啟發(fā)式路徑規(guī)劃算法。A*算法在Dijkstra算法[8]的基礎(chǔ)上引入評價(jià)函數(shù)f(n)=g(n)+h(n)考察節(jié)點(diǎn)n的代價(jià)，其中，g(n)表示從起始點(diǎn)到節(jié)點(diǎn)n的實(shí)際路徑長度，h(n)表示在不考慮障礙物的情況下從節(jié)點(diǎn)n到目標(biāo)點(diǎn)的估算路徑長度，A*算法基于評價(jià)函數(shù)選擇最優(yōu)的移動(dòng)節(jié)點(diǎn)，從而逐步構(gòu)建完整路徑。傳統(tǒng)的A*算法可以規(guī)劃從起始點(diǎn)到目標(biāo)點(diǎn)的最優(yōu)路徑，然而，A*在算法效率上也存在以下問題：其一是內(nèi)存方面，算法需要對網(wǎng)格節(jié)點(diǎn)的鄰接信息及由算法引入的其他變量進(jìn)行存儲，其內(nèi)存需求隨網(wǎng)格規(guī)模的擴(kuò)大而成比例增加，因此其用于大規(guī)模網(wǎng)格時(shí)內(nèi)存消耗較大；其二是計(jì)算時(shí)間方面，算法擴(kuò)展節(jié)點(diǎn)數(shù)目同樣會隨網(wǎng)格規(guī)模的擴(kuò)大而成比例增加，特別地，算法在擴(kuò)展節(jié)點(diǎn)中尋優(yōu)的操作如果基于鏈表數(shù)據(jù)結(jié)構(gòu)，擴(kuò)展節(jié)點(diǎn)數(shù)目的增加會同時(shí)加深算法對鏈表的搜索深度，進(jìn)而更嚴(yán)重地影響算法的規(guī)劃路徑效率。因此，結(jié)合以上兩點(diǎn)，執(zhí)行傳統(tǒng)A*算法的計(jì)算機(jī)資源消耗會隨網(wǎng)格規(guī)模的擴(kuò)大而急劇增長[9]，需要針對算法效率進(jìn)行改進(jìn)。

已有的對A*算法效率的改進(jìn)主要是生成抽象地圖[10]，將真實(shí)柵格地圖數(shù)據(jù)以一定規(guī)則生成總數(shù)較小的網(wǎng)格地圖作為A*算法的輸入地圖，現(xiàn)有的生成抽象地圖的方法包括四叉樹劃分法[11]、多層級簇構(gòu)建法[12]、基于聚類的K-means A*算法[13]等。為解決遍歷大量鄰居節(jié)點(diǎn)問題，H.Samet提出四叉樹表示柵格地圖[11], 對非全障礙區(qū)域不斷以四叉樹形式劃分，直到劃分出的網(wǎng)格全為障礙區(qū)域（柵格標(biāo)識為0）或非障礙區(qū)域（柵格標(biāo)識為1），該方法可有效減少A*算法遍歷的節(jié)點(diǎn)數(shù)，在n2個(gè)柵格的地圖中只需遍歷O(P)個(gè)節(jié)點(diǎn)即可得到路徑，其中P表示障礙區(qū)域的總周長[14]。但四叉樹方法在障礙物區(qū)域較小、數(shù)量巨大且位置隨機(jī)性較高的情況下，由于樹的葉子節(jié)點(diǎn)繁多，遍歷效率降低。此外，當(dāng)起始點(diǎn)與目標(biāo)點(diǎn)在樹的根節(jié)點(diǎn)的不同子節(jié)點(diǎn)的后代中，由于樹的多層次距離設(shè)定，規(guī)劃出的路徑可能與最優(yōu)路徑相差較大[15]。A.Botea提出通過多層級地圖結(jié)構(gòu)優(yōu)化A*算法（HPA）[12]，HPA算法將地圖分為多個(gè)簇，通過簇內(nèi)邊界點(diǎn)以及簇之間的可通行邊連接生成邏輯地圖，多個(gè)簇合并形成更高層級的邏輯地圖。該算法抽象出的節(jié)點(diǎn)數(shù)量較少，可有效提高A*的運(yùn)算效率，但同樣存在在障礙物隨機(jī)性較高、地圖復(fù)雜的情況下效率較低的問題，并且在第三層及更高層級優(yōu)化效果不佳。

本文針對上述問題，提出一種基于鄰接節(jié)點(diǎn)聚合的多層級算法，實(shí)現(xiàn)了對傳統(tǒng)A*算法的效率改進(jìn)。隨后的內(nèi)容首先從節(jié)點(diǎn)聚合方法、抽象網(wǎng)格構(gòu)建方法、粗糙路徑規(guī)劃方法及路徑細(xì)化方法這4個(gè)方面詳細(xì)介紹了MQA-A*算法的實(shí)現(xiàn)途徑；之后構(gòu)造了3組仿真實(shí)驗(yàn)，對MQA-A*的內(nèi)存需求、算法CPU時(shí)間及算法加速比進(jìn)行研究，驗(yàn)證了算法在不同復(fù)雜程度的柵格地圖上都可以對計(jì)算效率實(shí)現(xiàn)較大的提升，并進(jìn)一步分析了仿真實(shí)驗(yàn)的擴(kuò)展網(wǎng)格占比對算法加速比的影響。

1 多層級MQA-A*柵格路徑規(guī)劃算法

1.1 金字塔聚合地圖構(gòu)建

MQA-A*算法首先需要通過構(gòu)造金字塔聚合地圖，來縮減地圖節(jié)點(diǎn)數(shù)目并同時(shí)降低柵格地圖的空間復(fù)雜度。金字塔結(jié)構(gòu)的多層級聚合地圖需要從原始柵格地圖開始逐層構(gòu)造，構(gòu)建第一層聚合地圖的方法如圖1所示，將原始柵格圖1a每個(gè)2×2的網(wǎng)格劃分為一個(gè)區(qū)域，將區(qū)域內(nèi)4個(gè)相鄰的1×1原始柵格聚合成第一層聚合地圖的一個(gè)抽象節(jié)點(diǎn)，圖1b給出了第一層級聚合地圖的4個(gè)抽象節(jié)點(diǎn)，節(jié)點(diǎn)數(shù)相比原始柵格地圖的圖1a減少了3/4。

圖1 第一層抽象地圖節(jié)點(diǎn)的建立Fig.1 The establishment of the fi rst layer of abstract map nodes

第一層聚合地圖上的抽象節(jié)點(diǎn)不能簡單區(qū)分為障礙物或非障礙物，有鑒于此，為體現(xiàn)聚合地圖的障礙物信息，本文借助抽象節(jié)點(diǎn)內(nèi)部原始柵格上的障礙物分布情況，來構(gòu)造第一層聚合地圖上抽象節(jié)點(diǎn)間的連接屬性。抽象節(jié)點(diǎn)間的連接屬性可以分為邊連通性及角連通性：首先，邊連通性取決于緊貼該邊兩側(cè)的原始柵格能否實(shí)現(xiàn)跨越邊的連通，如圖1c所示，在A、B兩個(gè)第一層級抽象節(jié)點(diǎn)之中，由于b1和b4都是障礙物，不存在A、B間的通路，因此A、B兩抽象節(jié)點(diǎn)不連接，而A、C之間則由于a4和c1連通，因此A、C兩抽象節(jié)點(diǎn)是相互連接的；然后，角連通性取決于對頂角的兩個(gè)原始柵格是否存在障礙物，如B、C之間b4及c2均為障礙物因而不連通，而A、D之間則由于a3及d1均非障礙物，因此A、D兩抽象節(jié)點(diǎn)間相互連通，圖1a的第一層級聚合地圖如圖1d所示（抽象節(jié)點(diǎn)通過矩形表示，節(jié)點(diǎn)間連接關(guān)系通過線表示）。抽象聚合地圖是包含抽象節(jié)點(diǎn)及其鄰居列表信息的數(shù)據(jù)結(jié)構(gòu)，通過上述方法，可以得到抽象節(jié)點(diǎn)間的連接屬性即節(jié)點(diǎn)鄰居信息，從而可根據(jù)該信息抽象第一層級聚合網(wǎng)格。

第二層聚合地圖的構(gòu)造需要借助第一層聚合地圖中抽象節(jié)點(diǎn)間的連接信息（僅連接信息即可，第一層聚合地圖的數(shù)據(jù)結(jié)構(gòu)不需要完整獲取），來判斷第二層抽象節(jié)點(diǎn)間的連接屬性。抽象節(jié)點(diǎn)的聚合方式與第一層相同，即每4個(gè)鄰接的第一層抽象節(jié)點(diǎn)聚合成一個(gè)第二層抽象節(jié)點(diǎn)。需要注意的是，從第二層聚合地圖起始，該層上抽象節(jié)點(diǎn)的聚合方法需要考慮節(jié)點(diǎn)內(nèi)部的連通性問題，節(jié)點(diǎn)內(nèi)部連通性的概念是指聚合抽象節(jié)點(diǎn)內(nèi)部的4個(gè)低層級節(jié)點(diǎn)是否相互連通，僅針對存在鄰居的抽象節(jié)點(diǎn)（如底層全是障礙物的高層級抽象網(wǎng)格不屬于內(nèi)部不連通），顯然該屬性只用于第二層級或更高層級聚合地圖的抽象節(jié)點(diǎn)中，考慮節(jié)點(diǎn)內(nèi)部連通的必要性如圖2所示，圖2a中A1與[C]1連通且[C]1與B1連通，若不考慮節(jié)點(diǎn)內(nèi)部連通性，在路徑規(guī)劃時(shí)可認(rèn)為從A1到B1存在通路，但實(shí)際上[C]1內(nèi)部節(jié)點(diǎn)并不相互連通，在[C]1內(nèi)部的A1的鄰居節(jié)點(diǎn)與B1的鄰居節(jié)點(diǎn)間無連接，因此從A1到B1不存在第一層抽象節(jié)點(diǎn)間的通路；而圖2b中節(jié)點(diǎn)[C]2內(nèi)部連通，A2只要與[C]2中的任一低層級抽象節(jié)點(diǎn)連接，即可認(rèn)為A2與[C]2內(nèi)的所有底層級節(jié)點(diǎn)間均存在通路，在圖2b中A2、B2均與[C]2相連因此A2到B2存在通路。有鑒于此，判斷節(jié)點(diǎn)內(nèi)部連通性是保證能否規(guī)劃出正確路徑的前提，考慮到節(jié)點(diǎn)內(nèi)部不連通的情況下，獲取抽象節(jié)點(diǎn)的鄰居需要根據(jù)多種不連通情況和鄰居方位信息來判斷，過程復(fù)雜并嚴(yán)重影響算法的總體效率，本文僅將聚合后內(nèi)部可連通的抽象節(jié)點(diǎn)存儲在第二層聚合地圖上，而內(nèi)部不可連通的第二層抽象節(jié)點(diǎn)將被重新打散成4個(gè)第一層級抽象節(jié)點(diǎn)進(jìn)行存儲，即第二層聚合地圖上可能同時(shí)存在第一、第二兩個(gè)層級的抽象網(wǎng)格。

圖2 第二層抽象節(jié)點(diǎn)的內(nèi)部連通性問題Fig.2 The internal connectivity problem of the second layer of abstract map node

第二層聚合地圖上，抽象節(jié)點(diǎn)間的連接關(guān)系可借助第一層抽象節(jié)點(diǎn)的連接關(guān)系來構(gòu)造。記Lb為包含4個(gè)第一層抽象節(jié)點(diǎn)的一個(gè)第二層抽象節(jié)點(diǎn)，Lc表示Lb中的一個(gè)第一層級抽象節(jié)點(diǎn)，Ls表示第二層聚合地圖中未被聚合而留下的一個(gè)第一層級抽象節(jié)點(diǎn)，分3種情況討論：第1種是Lb與Lb相互連接，即某一個(gè)Lb中至少有一個(gè)Lc與相鄰Lb中的一個(gè)Lc互為鄰居；第2種是Lb與Ls互為鄰居，即某一個(gè)Lb中至少有一個(gè)Lc與相鄰Ls互為鄰居；第3種是Ls與Ls互為鄰居。第二層聚合網(wǎng)格的方式如圖3所示。

圖3 第二層抽象地圖節(jié)點(diǎn)的建立Fig.3 The establishment of the second layer of abstract map nodes

建立更高層級聚合地圖的方法類似，其流程圖如圖4所示。

圖4 建立多層級抽象網(wǎng)格地圖的流程圖Fig.4 The fl ow chart of creating a multi-level abstract grid map

1.2 多層級A*路徑規(guī)劃

多層級A*路徑規(guī)劃方法，首先是在高層級聚合網(wǎng)格地圖上運(yùn)行A*算法，得到當(dāng)前層級網(wǎng)格上的粗糙路徑，并考慮該路徑所經(jīng)過的所有抽象節(jié)點(diǎn)，將這些節(jié)點(diǎn)對應(yīng)到低一層級的地圖中，根據(jù)抽象節(jié)點(diǎn)內(nèi)部的連通屬性、節(jié)點(diǎn)間的連接情況及障礙物信息，將粗糙路徑逐層細(xì)化到底層?xùn)鸥竦貓D中。該算法首先要考慮起始點(diǎn)和目標(biāo)點(diǎn)的層級轉(zhuǎn)換，在第一層級中，起始點(diǎn)和目標(biāo)點(diǎn)通過簡單的坐標(biāo)變換得到第一層級對應(yīng)網(wǎng)格，將其帶入到第一層級的A*路徑規(guī)劃過程中。在第二層級中，起始點(diǎn)和目標(biāo)點(diǎn)對應(yīng)的第二級節(jié)點(diǎn)可能是第二層級聚合節(jié)點(diǎn)，也可能是未聚合節(jié)點(diǎn)，具有不確定性，需要在得到第一層級對應(yīng)節(jié)點(diǎn)后，判斷該節(jié)點(diǎn)的第二級父節(jié)點(diǎn)是否為內(nèi)部可連通節(jié)點(diǎn)，從而確定起始點(diǎn)和目標(biāo)點(diǎn)屬于哪個(gè)層級的節(jié)點(diǎn)并且計(jì)算出坐標(biāo)。隨著層級的升高，對起始點(diǎn)和目標(biāo)點(diǎn)的坐標(biāo)變換過程逐漸復(fù)雜。

在聚合地圖上執(zhí)行A*算法時(shí)，鄰居節(jié)點(diǎn)的獲取、啟發(fā)函數(shù)的計(jì)算與傳統(tǒng)A*不同。傳統(tǒng)的A*算法對每一個(gè)待考慮節(jié)點(diǎn)都需要判斷相鄰節(jié)點(diǎn)是否可通，本文在金字塔結(jié)構(gòu)的聚合地圖生成后，每一抽象節(jié)點(diǎn)都存儲了一個(gè)鄰居列表，在多層級A*判斷鄰居節(jié)點(diǎn)時(shí)可直接調(diào)用。傳統(tǒng)A*算法的啟發(fā)式函數(shù)可采用當(dāng)前節(jié)點(diǎn)到目標(biāo)點(diǎn)的曼哈頓距離作為最小代價(jià)評估值，在第一層聚合地圖上計(jì)算當(dāng)前節(jié)點(diǎn)到目標(biāo)點(diǎn)的曼哈頓距離與傳統(tǒng)A*算法相同，直接用第一層的坐標(biāo)進(jìn)行計(jì)算。第二層聚合地圖為了代價(jià)估計(jì)更精確，其兩個(gè)節(jié)點(diǎn)間的距離為網(wǎng)格中心到另一個(gè)網(wǎng)格中心的歐幾里得距離，由于抽象地圖中存在兩種層級的網(wǎng)格，所以該距離有可能為多種取值。

A*算法得到聚合地圖上的粗糙路徑后，需要在路徑上抽象節(jié)點(diǎn)對應(yīng)的低一層級抽象網(wǎng)格上逐層細(xì)化路徑，直到細(xì)化到原始柵格地圖中。細(xì)化路徑時(shí)不需要啟發(fā)函數(shù)的輔助判別，可根據(jù)高層級網(wǎng)格內(nèi)部的連通情況，以及高層級網(wǎng)格間的連接信息得到細(xì)化的路徑。以第一層級的細(xì)化路徑為例，每一步的方位判斷規(guī)則如圖5所示，低一層級抽象地圖上的起始點(diǎn)下一步的可選方向取決于它所在的高一層節(jié)點(diǎn)與粗糙路徑上的下一節(jié)點(diǎn)的方位關(guān)系。下一節(jié)點(diǎn)為水平或豎直方向移動(dòng)的情況，起始點(diǎn)的移動(dòng)方向有3種，如圖5a箭頭所示，其中粗箭頭表示優(yōu)先選擇的方向；下一節(jié)點(diǎn)為對角線方向移動(dòng)的情況，起始點(diǎn)的移動(dòng)方向有3種，如圖5b箭頭所示，其中粗箭頭表示優(yōu)先選擇的方向，得到下一步路徑點(diǎn)后，重復(fù)上述過程，即可得到最終路徑。高層級抽象網(wǎng)格的細(xì)化原理與第一層級類似。該方法相比于原始的A*算法，步驟較少，判別規(guī)則簡單，執(zhí)行效率較高。

圖5 細(xì)化路徑方位判斷示意圖Fig.5 Schematic diagram of the refinement path orientation

由此可得多層級A*路徑規(guī)劃算法的流程圖如圖6所示：

圖6 多層級A＊路徑規(guī)劃算法流程圖Fig.6 Multi-level A ＊ path planning algorithm fl ow chart

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

2.1 仿真準(zhǔn)備

為驗(yàn)證本文算法的有效性，本文設(shè)計(jì)并實(shí)現(xiàn)了A*改進(jìn)算法的仿真試驗(yàn)，實(shí)驗(yàn)選用3種不同障礙物數(shù)量、形態(tài)及分布情況的柵格地圖，如圖7所示，地圖大小分為500×3 000像素和1 000×1000像素2種，在這些地圖上分別運(yùn)行A*、MQA-A*第一層（實(shí)驗(yàn)結(jié)果中簡稱“MQA-A*1”）、MQA-A*第二層（實(shí)驗(yàn)結(jié)果中簡稱“MQA-A*2”）路徑規(guī)劃算法，進(jìn)行對比實(shí)驗(yàn)。硬件環(huán)境為：Intel Core i5 1.7GHz處理器，4GB DDR3內(nèi)存，Intel Visual Fortran 2010編譯器。

圖7 實(shí)驗(yàn)所用地圖Fig.7 Maps for simulation

2.2 仿真結(jié)果

對圖7中3張地圖進(jìn)行A*算法和MQA-A*算法的仿真，收集抽象地圖建立時(shí)間、路徑規(guī)劃總時(shí)間、擴(kuò)展節(jié)點(diǎn)總數(shù)、總內(nèi)存占用等數(shù)據(jù)，仿真結(jié)果見表1。

表1 仿真結(jié)果對比Tab.1 Simulation results comparison

首先關(guān)注連接信息獲取時(shí)間及抽象網(wǎng)格建立時(shí)間，這兩部分時(shí)間的總和就是MQA-A*算法對網(wǎng)格的預(yù)處理CPU時(shí)間。圖7a及圖7b對應(yīng)的兩組仿真實(shí)驗(yàn)，其原始柵格地圖的規(guī)模一致，因此其網(wǎng)格預(yù)處理CPU時(shí)間類似，一起進(jìn)行分析：以圖7a為例，MQA-A*2的連接信息獲取時(shí)間相比MQA-A*1多了一倍，這是因?yàn)榈诙泳酆系貓D上的連接屬性是基于第一層得到的；而抽象網(wǎng)格建立時(shí)間方面，由于該部分的效率主要取決于該層級聚合地圖的抽象節(jié)點(diǎn)總數(shù)，在簡單障礙物柵格地圖中，第二層級聚合地圖的抽象節(jié)點(diǎn)數(shù)目接近于第一層的1/4，因此MQA-A*2所需的CPU時(shí)間也要少于MQA-A*1；在總體網(wǎng)格預(yù)處理CPU時(shí)間方面，MQA-A*2相比MQA-A*1有小幅提升。圖7c代表的地圖具有復(fù)雜的障礙物分布，其連接信息獲取時(shí)間及抽象網(wǎng)格建立時(shí)間的規(guī)律與圖7a及圖7b相同，但在總體網(wǎng)格預(yù)處理CPU時(shí)間方面MQA-A*2的預(yù)處理時(shí)間大于MQA-A*1，原因在于圖7c第二層抽象網(wǎng)格地圖中的內(nèi)部不連通節(jié)點(diǎn)數(shù)較多，如圖8a所示（圖中黑色區(qū)域?yàn)榭蛇B通網(wǎng)格，藍(lán)色區(qū)域?yàn)閮?nèi)部不連通網(wǎng)格，紅色區(qū)域?yàn)榈讓尤渴钦系K物的高層網(wǎng)格），較多的內(nèi)部不連通節(jié)點(diǎn)數(shù)導(dǎo)致第二層抽象網(wǎng)格數(shù)與第一層抽象網(wǎng)格數(shù)相差不多，而第二層抽象網(wǎng)格地圖建立過程相對第一層更復(fù)雜，因此MQA-A*2的預(yù)處理CPU時(shí)間反而更長。

圖8 MQA-A＊2中間過程變量云圖Fig.8 The contours of process variables of MQA-A＊2

繼續(xù)分析算法的路徑規(guī)劃時(shí)間。以圖7c柵格地圖上的MQA-A*2仿真實(shí)驗(yàn)為例，圖8給出了第二層聚合地圖上的粗糙路徑及算法相關(guān)變量，其中圖8b展示了粗糙路徑，圖8c展示了所有擴(kuò)展節(jié)點(diǎn)的g值，圖8d展示了算法擴(kuò)展節(jié)點(diǎn)的遍歷順序。在路徑規(guī)劃時(shí)間方面，3張不同的柵格地圖上的實(shí)驗(yàn)均存在以下規(guī)律：MQA-A*算法在路徑規(guī)劃上相比傳統(tǒng)的A*算法優(yōu)勢相當(dāng)明顯，MQA-A*1已經(jīng)將路徑規(guī)劃效率在傳統(tǒng)A*算法的基礎(chǔ)上提升到了至少5倍，而MQA-A*2的路徑規(guī)劃效率還能進(jìn)一步在MQA-A*1的基礎(chǔ)上提升到至少3倍，最終的路徑規(guī)劃效率提升方面，圖7a的柵格地圖上MQA-A*2的路徑規(guī)劃時(shí)間僅為傳統(tǒng)A*算法的1.14%，圖7b及圖7c的結(jié)果分別為2.56%及3.70%，如此大幅度的效率提升源于金字塔結(jié)構(gòu)的高層級聚合地圖大幅縮減了執(zhí)行A*遍歷的擴(kuò)展節(jié)點(diǎn)數(shù)目，圖7a及圖7b的MQA-A*2擴(kuò)展節(jié)點(diǎn)數(shù)目約為傳統(tǒng)A*算法的1/16，而該數(shù)值在圖7c中也同樣小于1/10。擴(kuò)展節(jié)點(diǎn)數(shù)目的縮減，首先成比例減少了路徑規(guī)劃中與擴(kuò)展節(jié)點(diǎn)相關(guān)的鏈表處理次數(shù)，而在每次的鏈表處理中，擴(kuò)展節(jié)點(diǎn)數(shù)目的減少使得鏈表的深度大幅下降，因而MQA-A*進(jìn)一步提升了鏈表具體操作的效率，綜合這兩方面的因素，在路徑規(guī)劃方面MQA-A*可以大幅提升路徑規(guī)劃的效率，且網(wǎng)格的聚合層級越高，該部分的加速效果越好。

特別地，如果認(rèn)為同一個(gè)柵格地圖可以重復(fù)運(yùn)用，基于不同的路徑起始位置及結(jié)束位置構(gòu)造多組實(shí)驗(yàn)，我們可以參考單獨(dú)的路徑規(guī)劃時(shí)間作為算法效率提升的指標(biāo)，如前文所述，在該指標(biāo)下，算法效率提升的效果非常好。但如果每個(gè)柵格地圖只運(yùn)用一次，則考察算法的效率提升需要綜合考慮網(wǎng)格預(yù)處理的CPU時(shí)間，將網(wǎng)格預(yù)處理時(shí)間加上路徑規(guī)劃時(shí)間，得到算法執(zhí)行的總時(shí)間，并以該量定義加速比φ，記算法執(zhí)行總時(shí)間為T,加速比的表達(dá)式為：φ=TA*/TMQA-A*。對圖7a、圖7b及圖7c，MQA-A*1分別提供了8.8倍、3.3倍及2.9倍的加速比，而更高層級聚合網(wǎng)格上的MQA-A*2分別提供了58.4倍、8倍及3.8倍的加速比?？梢缘玫揭韵聝蓚€(gè)結(jié)論，首先是包括了網(wǎng)格預(yù)處理部分的時(shí)間之后，MQA-A*算法相比傳統(tǒng)A*算法依然可以大幅度地提升計(jì)算效率，其次是MQA-A*算法的加速比對柵格地圖的擴(kuò)展節(jié)點(diǎn)數(shù)占比非常敏感，算法的加速效果隨占比的減小而迅速降低，其原因在于擴(kuò)展節(jié)點(diǎn)占比的減少導(dǎo)致路徑規(guī)劃的計(jì)算時(shí)間在算法執(zhí)行總時(shí)間中的比重減少，于是雖然兩個(gè)層級間A*路徑規(guī)劃部分的時(shí)間還是存在數(shù)倍的關(guān)系，但是該差異與網(wǎng)格預(yù)處理時(shí)間相比并非很大的，算法的提速效果降低。

最后關(guān)注算法的內(nèi)存需求，MQA-A*所需內(nèi)存相對于原始A*算法要少，且MQA-A*2的內(nèi)存占用比MQA-A*1更低。內(nèi)存占用包括連接信息內(nèi)存占用和抽象網(wǎng)格內(nèi)存占用兩部分，其中連接信息內(nèi)存占用是逐層累加的，即每個(gè)層級的連接信息都需要存儲，所以第二層的連接信息內(nèi)存占用大于第一層級；而抽象網(wǎng)格內(nèi)存占用大致是每一層級為低一層級的1/4，如圖7a和圖7b情況，但圖7c中第二層級內(nèi)存占用大于第一層級的1/4是因?yàn)榈诙蛹壷械膬?nèi)部不連通網(wǎng)格相對較多，所以除了存儲第二層級抽象網(wǎng)格，還需要存儲大量的第一層級抽象網(wǎng)格，造成內(nèi)存占用的增大。由于抽象網(wǎng)格內(nèi)存占用在總內(nèi)存占用中的占比大于連接信息內(nèi)存占用，所以總內(nèi)存占用趨勢是逐層減少的。

3 結(jié)束語

本文提出了基于鄰接節(jié)點(diǎn)聚合的多層級MQA-A*柵格路徑規(guī)劃算法，具體工作主要分為以下兩個(gè)部分：

1）首先是從節(jié)點(diǎn)聚合、抽象地圖建立、粗糙路徑規(guī)劃及細(xì)化路徑4個(gè)方面對算法進(jìn)行了詳細(xì)的解釋。節(jié)點(diǎn)聚合方面，將傳統(tǒng)的基于柵格障礙物來構(gòu)造的網(wǎng)格鄰居信息，抽象成節(jié)點(diǎn)間的連接屬性并運(yùn)用于高層級聚合地圖，從而在蘊(yùn)含鄰居信息的同時(shí)大幅降低了用于路徑規(guī)劃的地圖規(guī)模；抽象地圖建立方面，考慮高層級網(wǎng)格抽象節(jié)點(diǎn)內(nèi)部不連通的特點(diǎn)，建立多層級抽象節(jié)點(diǎn)共存的高層聚合地圖，從而避免了抽象節(jié)點(diǎn)內(nèi)部不連通給后續(xù)的路徑規(guī)劃部分帶來的麻煩；粗糙路徑規(guī)劃及細(xì)化路徑方面，算法在最高層級聚合地圖上執(zhí)行A*算法高效地得到粗糙路徑，并根據(jù)抽象節(jié)點(diǎn)內(nèi)的連通屬性及節(jié)點(diǎn)間的連接信息將粗糙路徑逐層細(xì)化，細(xì)化中僅保證單層細(xì)化中路徑最短。

2）基于不同復(fù)雜程度的柵格地圖，構(gòu)造了3組仿真實(shí)驗(yàn)對MQA-A*算法的內(nèi)存需求、算法CPU時(shí)間及算法加速比進(jìn)行研究。實(shí)驗(yàn)結(jié)果表明，MQA-A*算法可以在路徑規(guī)劃方面較傳統(tǒng)A*算法有巨大的提升，在3組實(shí)驗(yàn)中，基于MQA-A*2的路徑規(guī)劃時(shí)間分別是傳統(tǒng)A*算法路徑規(guī)劃時(shí)間的1.14%、2.56%及3.70%，在考慮網(wǎng)格預(yù)處理CPU時(shí)間后，進(jìn)而考察算法執(zhí)行總時(shí)間加速比，MQA-A*2在3組實(shí)驗(yàn)中分別提供了58.4倍、8倍及3.8倍的加速比，分析得到了該加速比在后兩組實(shí)驗(yàn)中沒有第一組明顯的原因在于其擴(kuò)展節(jié)點(diǎn)占比較小。