邱磊，劉輝玲，雷建龍

(武漢船舶職業(yè)技術(shù)學(xué)院電氣與電子工程學(xué)院，湖北武漢430050)

0 引言

A*算法通過裁剪代價較高的鄰居而發(fā)現(xiàn)最優(yōu)路徑，這不利于游戲開發(fā)和機器人尋路.跳點搜索(JPS)[1]是一種新的尋路算法，是對A*搜索算法的優(yōu)化.它通過圖裁剪來減少搜索過程的對稱性，能讓搜索在網(wǎng)格上直線長“跳”，而不是普通A*的小步移動.JPS跳過了無用節(jié)點，保留了關(guān)鍵的“跳點”.JPS擅長應(yīng)用在等價網(wǎng)格地圖上大的開放區(qū)域.在這些開放的區(qū)域，JPS能略過或跳過大量使用傳統(tǒng)A*算法將被擴展的中間節(jié)點.然而，JPS通常要比A*評估更多的障礙物，但大多數(shù)情況下，JPS的額外評估要比A*的額外列表操作快得多.在最壞情況下，在搜索時間上JPS與A*也能打成平手；至于大型的開放空間，JPS生成最優(yōu)路徑要遠(yuǎn)快于A*.跳點搜索算法比傳統(tǒng)的A*不僅提升了性能而且降低了內(nèi)存成本，跳點搜索算法將是游戲與機器人領(lǐng)域人工智能的未來，甚至可以應(yīng)用在全球定位系統(tǒng)、仿真等領(lǐng)域.

本文的創(chuàng)新點如下：1）主要特色是采用圖的方式，對JPS算法進(jìn)行了直觀的描述和解釋，對算法賦予直觀的物理含義，是對理論方法的一種拓展；2）既使用了規(guī)則的2D方形網(wǎng)格地圖又使用了測試庫中的基準(zhǔn)地圖來表示尋路環(huán)境進(jìn)行仿真實驗，使JPS算法的性能分析結(jié)論更具說服力；3）對同等地圖尺寸與變化地圖尺寸下JPS的性能均進(jìn)行了比較分析.本文待解決的問題如下：1）擬嘗試用圖來解釋JPS算法而不訴諸于在其研究論文中給出的基本數(shù)學(xué)證明；2）擬結(jié)合仿真實驗分別從同等地圖尺寸下障礙物密度的變化對JPS擴展節(jié)點數(shù)和查看鄰居數(shù)的影響、地圖尺寸的變化對JPS與其它典型尋路算法的時間效率趨勢的比較影響，以及基準(zhǔn)地圖環(huán)境的對稱性特征對JPS算法與A*算法的比較影響程度三個方面綜合分析JPS的性能優(yōu)勢.所做工作的價值和意義如下：1）用圖來解釋理論算法是一件有意義的工作，對具體應(yīng)用有更好的指導(dǎo)價值；2）綜合全面分析了JPS的性能，彌補了已有文獻(xiàn)對JPS性能分析的不足.

1 相關(guān)工作

使用2D網(wǎng)格來代表地圖是非常普遍的方式，在等價2D網(wǎng)格上有很多與尋找最短路徑相關(guān)的算法.A*算法是一個常見且簡單的廣度優(yōu)先搜索和深度優(yōu)先搜索的優(yōu)化，它作為通用的搜索工具仍具有強大的生命力.A*算法有很多擴展或變種[2]，跳點搜索(JPS)算法只是其中之一：1985年Richard E.Korf提出的IDA*(Iterative Deepening A*)算法[3]是A*算法和迭代加深算法的結(jié)合，通過調(diào)整閥值進(jìn)行深度優(yōu)先搜索來找到最優(yōu)解；1994年Anthony Stentz提出的D*(Dynamic A*)算法[4]研究了在不知道全部地圖信息的情況下尋路，可以快速改正A*算法由于信息未知而導(dǎo)致的計算錯誤；2004年Sven Koenig等提出的LPA*(Lifelong Planning A*)算法[5]研究了在地圖代價發(fā)生改變的時候，如何重復(fù)利用以前的A*計算來產(chǎn)生新的路徑；2004年AdiBotea等提出的HPA*(Hierarchical Path finding A*)算法[6]是一個在網(wǎng)格地圖上降低問題復(fù)雜度的分層尋路方法，該技術(shù)將地圖抽象成相連接的局部簇.2005年Maxim Likhachev等人提出的AD*(Anytime Dynamic A*)算法[7]研究了如何讓搜索算法在復(fù)雜的環(huán)境和有限的時間內(nèi)收斂于次優(yōu)解的問題；2007年Alex Nash等人提出了Theta*算法[8]，該算法在方形網(wǎng)格上尋路不必嚴(yán)格遵循網(wǎng)格的限制，允許任意角度的路徑；2010年Daniel Harabor等提出的RSR(Rectangular Symmetry Reduction)算法[9]可以看作是一種預(yù)處理算法，它通過將等價網(wǎng)格地圖分解為一組中空的矩形區(qū)域來識別對稱性，從而提高尋找最優(yōu)路徑的速度.文[1]中提出的JPS算法是一種在方形網(wǎng)格上尋路更加有效率的方法，上述這些A*算法的擴展或變種與JPS解決的問題類似.

2 算法模型

2.1 跳點搜索的原理

JPS算法是基于未修改的A*是相當(dāng)浪費的，花了大量時間去評估一些無需評估的節(jié)點.JPS算法能夠讓A*尋路更上一個檔次，JPS對此是這樣改進(jìn)的：識別并選擇性地擴展網(wǎng)格地圖上的僅僅某些節(jié)點，稱之為跳點，兩個跳點連接的路徑上的中間節(jié)點將不被擴展，該方法總能計算出最優(yōu)解，且能將A*算法的速度提高一個數(shù)量級甚至更多[1].

假設(shè)搜索到了節(jié)點x處，該節(jié)點是從父節(jié)點p(x)直線向右移動而至.由圖1，評估以灰色條紋標(biāo)記的節(jié)點是毫無意義的：因為經(jīng)由同時穿過p(x)和x的路徑去往這些節(jié)點中的任何一個的成本永遠(yuǎn)不會比在不訪問x的情況下從p(x)去往這些節(jié)點更低.

圖1 以直線移動尋找后繼

在通常情況下是沒有障礙物毗鄰節(jié)點的，如圖2a所示，若以直線移動抵達(dá)某節(jié)點，則只有1個單一的鄰居需要被考慮；若對角線移動后抵達(dá)某節(jié)點，則有3個節(jié)點需要被考慮.假設(shè)地形移動成本是一致的，為了找到最短路徑，以灰色條紋標(biāo)記的節(jié)點不需要被評估.在搜索中，有部分節(jié)點的擴展是無用的，如圖2a所示，當(dāng)前按照箭頭方向搜索到了節(jié)點x，至此所有帶有灰色條紋的節(jié)點都是無用的，因為總是存在一條最近路徑可以從節(jié)點x的父節(jié)點p(x)出發(fā)，不經(jīng)過節(jié)點x，而最終到達(dá)帶有灰色條紋的節(jié)點.但有一些節(jié)點比較特殊，如圖2b所示，同樣，以灰色條紋標(biāo)記的節(jié)點都是無用的，而被黑圈圈住的節(jié)點，是不存在一條不經(jīng)過節(jié)點x的最近路徑可以從節(jié)點x的父節(jié)點p(x)出發(fā)而到達(dá).被黑圈圈住的節(jié)點就是特殊的節(jié)點，稱之為被迫鄰居[10?12]，它們是節(jié)點x的后繼節(jié)點，要到達(dá)它們就必須經(jīng)過節(jié)點x，否則就不是最近路徑.

圖2 鄰居裁剪規(guī)則

所以，圖1中唯一需要注意的鄰居是位于節(jié)點x直接右側(cè)的鄰居，將其稱之為y，該節(jié)點可經(jīng)由x抵達(dá)，且成本比從p(x)出發(fā)但不經(jīng)過x的路徑低.然而，不是停在那兒去檢查y的每個毗鄰的節(jié)點，JPS所做的是繼續(xù)向右移動，直到抵達(dá)了某節(jié)點——該節(jié)點滿足它的至少一個鄰居（已訪問過的鄰居除外）需要被明確地評估.這樣的節(jié)點被標(biāo)記為y0，在這個節(jié)點的正上方有一個阻塞節(jié)點，由于這個阻塞節(jié)點，經(jīng)過y0抵達(dá)z是最好的（可對照不觸碰y0抵達(dá)z的路徑），z就是這樣的一個鄰居.因此當(dāng)?shù)竭_(dá)了y0時，必須既考慮z又考慮y0直接右側(cè)的節(jié)點（標(biāo)記為q）.因此y0是一個跳點：增加y0作為x的鄰居并將其添加到open列表，以供進(jìn)一步考慮.即當(dāng)從x沿著直線移動到后繼節(jié)點y0時，無需評估沿線路徑上的任何鄰居節(jié)點.至于對角線移動，情況是類似的：首先識別哪些毗鄰的鄰居節(jié)點值得考慮，以便開始；然后在所有相關(guān)的方向上移動，直到找到x的實際后繼節(jié)點.總之，JPS實際上是在搜索中尋找跳點的后繼節(jié)點而轉(zhuǎn)移狀態(tài)，而不是直接從當(dāng)前節(jié)點進(jìn)行擴展，為JPS尋找后繼可簡化為只考慮兩種主要的可能性：一、以直線方式抵達(dá)某節(jié)點；二、進(jìn)行對角線步后抵達(dá)某節(jié)點[13].JPS跳過了部分無用節(jié)點，保留關(guān)鍵的“跳點”，令A(yù)*在搜索時減少了擴展的節(jié)點數(shù)，從而達(dá)到加速的效果.

2.2 跳點搜索的圖解釋

A*算法擴展其搜索的方式是：將一個節(jié)點的直接鄰居添加到下一步要檢查的集合.假使能夠再向前多看幾步，直接跳過某些憑直覺就不值得查看的節(jié)點，從而在擴展搜索時，識別出對稱路徑[1,14]，進(jìn)而忽略某些節(jié)點.所謂“對稱路徑”是指多條等效的最佳路徑的代價相等，唯一的區(qū)別在于選擇以何種序列沿著對角線方向或水平方向移動.等價網(wǎng)格有助于高度的路徑對稱性，盡管JPS算法可以被定制為適應(yīng)其他類型的網(wǎng)格，但它更適合于遍歷8路網(wǎng)格地圖.

2.2.1 水平/垂直方向移動

本節(jié)基于水平/垂直方向上移動來擴展搜索.在一個開放的網(wǎng)格上，節(jié)點x向右移動，見圖3a所示.給出一些關(guān)于該節(jié)點x的直接鄰居的假設(shè)：首先，可以忽略“來自”的節(jié)點p(x)，因為已經(jīng)訪問過它了，該節(jié)點以灰色條紋標(biāo)記，見圖3b.其次，假定當(dāng)前節(jié)點斜后方的節(jié)點已通過當(dāng)前節(jié)點x的父親p(x)到達(dá)，因為相比于經(jīng)過當(dāng)前節(jié)點x而到達(dá)，該走法在路徑長度上更短，見圖3c.當(dāng)前節(jié)點x正上方和正下方的節(jié)點也可以從父親p(x)更優(yōu)地到達(dá)，倘若經(jīng)過當(dāng)前節(jié)點x而到達(dá)的話，則代價為2而不是，因此也可以忽略這兩個節(jié)點，見圖3d.斜前方的鄰居可以通過當(dāng)前節(jié)點x正上方和正下方的鄰居到達(dá)，這與從p(x)經(jīng)過當(dāng)前節(jié)點x而到達(dá)的路徑所花費的成本相同，因此同樣可以忽略這些斜前方的節(jié)點，見圖3e.至此，只剩下當(dāng)前節(jié)點x直接右側(cè)的鄰居要檢查，因已經(jīng)假設(shè)當(dāng)前節(jié)點x的所有鄰居可通過可供替代路徑而到達(dá)，因此可以只專注于這個單一的鄰居，見圖3f.進(jìn)而只要前行道路上沒有障礙物，即道路是暢通無阻的，就可以直接向右側(cè)跳躍多個節(jié)點，并且在不添加節(jié)點到open集合的情況下重復(fù)節(jié)點的檢查，見圖3g.

圖3 水平向前移動的步驟圖

但是前行道路上沒有障礙物并不意味著以上這些假設(shè)永遠(yuǎn)正確且一直不需要停下來做進(jìn)一步查看.對于當(dāng)前節(jié)點x斜前方的節(jié)點，假定任何等價的路徑都將經(jīng)過當(dāng)前節(jié)點x正上方和正下方的鄰居，但是有一種情況，并非如此：即當(dāng)前節(jié)點x正上方或正下方為障礙物從而阻塞了道路.此時，必須停下來重新檢查，不僅必須查看當(dāng)前節(jié)點x右側(cè)的節(jié)點，也要被迫查看當(dāng)前節(jié)點x斜上方的節(jié)點f(x)，由于節(jié)點f(x)是被迫考慮的而在其它情況下則是已忽略的，在文[1]中，節(jié)點f(x)稱之為“被迫鄰居”.因此，當(dāng)?shù)竭_(dá)一個含有被迫鄰居的節(jié)點x時，需停止向右跳躍，并將當(dāng)前節(jié)點x添加到open集合中，以便以后做進(jìn)一步的檢查和擴展，見圖3h.最后一個假設(shè)：當(dāng)向右跳躍時，如果道路被阻塞了，那么可以直接忽略整個跳躍.已經(jīng)假設(shè)當(dāng)前節(jié)點x正上方和正下方的路徑經(jīng)由其他鄰居節(jié)點生成，同時由于對角線方向存在一個被迫鄰居，因此路徑繼續(xù)生成.所以只需關(guān)心當(dāng)前節(jié)點x的最右側(cè)是什么，若有一個障礙物，則意味著無處可去，見圖3i[15].2.2.2 對角線方向移動

圖4 對角線向前移動的步驟圖

當(dāng)沿著對角線方向移動時，可應(yīng)用與水平/垂直移動相似的簡單假設(shè).本節(jié)基于向右上方移動來擴展搜索，見圖4a.首先假設(shè)：當(dāng)前節(jié)點x左側(cè)和正下方的鄰居可以直接從當(dāng)前節(jié)點x的父親p(x)通過垂直或水平移動而最優(yōu)地到達(dá)，見圖4b.對于當(dāng)前節(jié)點x左上方和右下方的節(jié)點，也可以給出相同的假設(shè)，這些節(jié)點同樣可以通過當(dāng)前節(jié)點x左側(cè)和下方的鄰居而到達(dá)，而且效率更高，見圖4c.還余下3個鄰居需要考慮：其中2個分別位于當(dāng)前節(jié)點x的正上方以及右側(cè)，另1個在當(dāng)前節(jié)點x的對角線方向，見圖4d.與水平移動時討論的被迫鄰居相似，當(dāng)在當(dāng)前節(jié)點x的左側(cè)（或正下方）存在一個障礙物時，則左上方（或右下方）的鄰居無法以其它方式到達(dá)，除非經(jīng)過當(dāng)前節(jié)點x，這些鄰居就是關(guān)于對角線移動時的被迫鄰居，見圖4e.沿著對角線移動時，當(dāng)有上述3個鄰居需要被考慮時，可以首先在當(dāng)前節(jié)點處沿垂直或水平方向查看一下，如果在這兩個方向上都無法尋找到任何值得查看的節(jié)點，那么就沿著對角線方向再多移動一步，接著再重復(fù)上述過程[15].

圖5是對角線跳躍的逐個步驟.在從當(dāng)前節(jié)點x沿著對角線方向移動之前，需先考慮其在水平與垂直方向上的路徑.首先，在水平和垂直方向上擴展，由于這兩個方向上的跳躍均止于障礙物（或地圖邊界），所以需要沿著對角線方向移動，見圖5a.由于在垂直和水平兩個方向上的擴展再次遇到了障礙物（或地圖邊界），因此仍需要沿著對角線方向移動，見圖5b.以此類推，第三次……，見圖5c.最后，當(dāng)從節(jié)點y沿垂直方向擴展抵達(dá)了地圖邊界時，擴展轉(zhuǎn)而沿水平方向向右跳躍至節(jié)點z，該跳躍帶出了節(jié)點z的一個被迫鄰居f(z)，見圖5d.因此，遇到這種情況時需要把當(dāng)前節(jié)點y添加到open集合，并繼續(xù)執(zhí)行A*的下一次迭代，見圖5e.

圖5 對角線跳躍的步驟圖

2.3 算法模型實例

2.2節(jié)分析了當(dāng)朝一個特定的方向行進(jìn)時跳過節(jié)點大多數(shù)鄰居的方法，也確定了一些何時向前跳躍的規(guī)則.為了使這些規(guī)則約束到A*算法上，每當(dāng)檢查open集合中的某一節(jié)點時，運用這些“向前跳躍”的步驟并使用該節(jié)點的父親來確定行進(jìn)的方向，同時盡可能遠(yuǎn)地向前跳躍.如果找到了一個感興趣的節(jié)點，將忽略所有中間步驟并將該新節(jié)點添加到open集合中[16].open集合中的每個節(jié)點都基于它們父親的方向而擴展，圖6是算法模型實例的路徑擴展序列，并在圖6j標(biāo)記出了最終路徑.

圖6 算法模型實例

本節(jié)實例地圖與2.2.2節(jié)相同，但標(biāo)記了目標(biāo)節(jié)點g.圖6a為初始網(wǎng)格地圖，本路徑擴展實例從先前已識別出的節(jié)點y（即圖5d所識別出的節(jié)點，也是open集合中唯一的節(jié)點）開始，在垂直方向擴展，結(jié)果抵達(dá)了地圖邊界，未找到目標(biāo)點，見圖6b.沿水平方向向右跳躍，發(fā)現(xiàn)了一個含有被迫鄰居的節(jié)點z（被迫鄰居f(z)以紫色高亮顯示），見圖6c，將節(jié)點z添加到open集合.然后，沿著對角方向擴展，結(jié)果未找到目標(biāo)點，因為撞上了地圖的邊緣，見圖6d.接下來，檢查下一個open節(jié)點z，由于到達(dá)節(jié)點z時正在水平移動著，因此擴展繼續(xù)沿著水平方向向前跳躍，見圖6e.鑒于節(jié)點z有一個被迫鄰居f(z)，不妨沿著f(z)方向擴展，依據(jù)對角線跳躍規(guī)則，需先沿著對角線方向移動，再在垂直和水平兩個方向上查看，見圖6f.再次沿著對角線方向移動，并未找到目標(biāo)點，見圖6g.此時，繼續(xù)執(zhí)行水平與垂直方向上的擴展：水平方向上將導(dǎo)致無路可走，垂直方向上則發(fā)現(xiàn)了目標(biāo)節(jié)點g，見圖6h，這與找到一個含有被迫鄰居的節(jié)點一樣有趣，因此添加該節(jié)點w到open集合.最后，擴展最后一個open節(jié)點w時抵達(dá)了目標(biāo)，見圖6i.跳過該算法的最后一次迭代——添加目標(biāo)點g本身到open集合，同樣識別出了該目標(biāo)點g——找到了一條最佳路徑，見圖6j[15,17].

3 實驗與分析

實驗1：為了測試A*與JPS算法所擴展節(jié)點數(shù)量的不同，在向隊列中放置鄰居和從隊列中移除f值最小的元素時，兩算法使用了完全相同的代碼，唯一不同之處在于尋找放置到隊列中的鄰居的過程.每次運行時，首先初始化100×100的網(wǎng)格，其上的初始節(jié)點和目標(biāo)節(jié)點隨機生成.對于每次迭代，障礙物的數(shù)量是沒有配額的，所有的節(jié)點均有設(shè)置為障礙物的可能性，但機率很小.首先在網(wǎng)格上執(zhí)行A*算法，并記錄擴展的節(jié)點與被查看的鄰居.然后，清除網(wǎng)格上所有有用信息（即：啟發(fā)值，鍵值以及從初始節(jié)點所評估的代價都將被刪除）.接著，再在網(wǎng)格上執(zhí)行JPS算法，同樣記錄擴展的節(jié)點與查看的鄰居.最后，網(wǎng)格被徹底清除干凈，開始新一次的運行.共執(zhí)行1000次運行，表1的結(jié)果為實驗1運行時擴展節(jié)點數(shù)和查看鄰居數(shù)的單次平均值.

在表1中，網(wǎng)格上障礙物的密度即是每個節(jié)點被設(shè)置為障礙物的機率.對于JPS來說，障礙物的密度越大，則擴展的節(jié)點越多，查看的鄰居越少；障礙物的密度越小，則擴展的節(jié)點越少，查看的鄰居越多.由表1數(shù)據(jù)可知，JPS擴展節(jié)點的數(shù)量與查看鄰居的數(shù)量成反比.

表1 擴展節(jié)點數(shù)與查看鄰居數(shù)的單次平均值

實驗2：為了說明JPS算法的優(yōu)越性，對比JPS與其他典型的尋路算法[18]，表2給出了當(dāng)?shù)貓D尺寸發(fā)生變化的時候，JPS與A*、Dijkstra、A*、BFS、DFS、Theta*的比較結(jié)果，可知：隨著地圖尺寸的增加，路徑長度和搜索時間同步增加.在同一地圖尺寸下，各個算法所求得的路徑長度相等或一致，但在搜索時間上，JPS明顯快于其他算法，且隨著地圖尺寸的增加，JPS的時間效率優(yōu)勢更加顯著.

表2 JPS與其他典型尋路算法的效率比較

實驗3：為了使實驗更有說服力，再在測試庫中的基準(zhǔn)地圖上測試JPS的性能.測試用的地圖來源于NathanSturtevant免費提供的Benchmark sets中Starcraft（星際爭霸）地圖集，可從http://www.movingai.com/benchmarks獲得.測試用的三個地圖分別是其中的Isolation.map(I)、RedCanyons.map(R)和Entangle ment.map(E)，如圖7所示.

圖7 環(huán)境對稱性程度不同的3個基準(zhǔn)地圖

A*算法和JPS算法在3個基準(zhǔn)地圖上被驗證或評估，變化的是環(huán)境的對稱性.實驗評估了搜索時間、擴展的節(jié)點數(shù)和路徑長度，為了進(jìn)行有說服力的算法驗證，算法重復(fù)執(zhí)行1000次，在搜索時間上給出了單次的平均搜索時間，實驗結(jié)果如表3所示.

表3 對稱性程度不同的3個地圖上A*與JPS重復(fù)執(zhí)行1000次的性能概要

兩算法都能找到從初始節(jié)點至目標(biāo)節(jié)點的最優(yōu)路徑，且JPS保持了A*的最優(yōu)性.地圖I的環(huán)境以高度對稱性為特征，該特征的地圖有多條長度相等的對稱路徑，JPS在搜索時間上要快于A*，在擴展節(jié)點數(shù)上也少于A*.地圖R的環(huán)境以中度對稱性為特征，對稱路徑在減少，在這種情況下，路徑的長度增加了約20%，JPS在搜索時間上仍然快于A*，且擴展的節(jié)點數(shù)少于A*，但返回的路徑長度要長于A*返回的路徑.地圖E的環(huán)境以較低的對稱性為特征，識別這樣的環(huán)境是非常復(fù)雜的，JPS在搜索時間上仍然快于A*，擴展的節(jié)點數(shù)同樣少于A*.

由表3可知，在所求解到的路徑長度相等或一致的情況下，無論是在平均搜索時間還是在擴展的節(jié)點數(shù)上，JPS都明顯優(yōu)于A*，JPS可將A*提速一個數(shù)量級甚至更多.同時，觀察表3“平均搜索時間比值”和“擴展的節(jié)點數(shù)比值”列數(shù)據(jù)可知，JPS的尋路效率取決于地圖環(huán)境的對稱性，地圖環(huán)境的對稱程度越高，JPS較之于A*的優(yōu)勢越明顯，那是由于JPS消除了更多的對稱路徑“貢獻(xiàn)”的，并且JPS較之于A*在擴展的節(jié)點數(shù)上的優(yōu)勢程度比搜索時間上還要顯著.

4 結(jié)論

尋路問題在執(zhí)行時間上仍有改進(jìn)的空間，在A*算法提出近50年后，一個新的算法JPS能夠大幅提高尋優(yōu)的性能，JPS是一個能顯著加速標(biāo)準(zhǔn)A*的算法，在等價網(wǎng)格上實現(xiàn)了比A*高達(dá)一個數(shù)量級甚至更多的速度提升.本文嘗試對JPS進(jìn)行了圖解釋，清晰直觀地呈現(xiàn)了該算法的原理，避免了通過難懂的數(shù)學(xué)證明去理解算法的內(nèi)涵.仿真實驗對JPS算法的性能進(jìn)行了綜合分析，實驗結(jié)果有效表明了JPS算法較之于其它典型尋路算法在搜索時間上的優(yōu)越性，JPS擴展節(jié)點數(shù)與查看鄰居數(shù)之間成反比關(guān)系，地圖環(huán)境的對稱性越高越能體現(xiàn)JPS較之于A*的性能優(yōu)勢.因此，從快速尋路角度上看，JPS是各種地圖環(huán)境下最好的算法，但通常它發(fā)現(xiàn)的路徑可能會長于A*算法.因此，該算法更適合需要快速尋路的情況.

本文的研究“意猶未盡”，未來的研究可以進(jìn)一步豐富，比如：1）考慮對加權(quán)網(wǎng)格或者多目標(biāo)點搜索進(jìn)行研究；2）探討JPS聯(lián)合Star算法家族各個算法的可能性，比如以Basic Theta*and Phi*改進(jìn)JPS，允許以任意角度搜索網(wǎng)格地圖等.