摘 要：針對(duì)跳點(diǎn)搜索（jump point search，JPS）路徑規(guī)劃算法在大尺度復(fù)雜場(chǎng)景下存在內(nèi)存資源消耗較大、路徑結(jié)果平滑度較低且路徑過于靠近障礙物等問題，提出融合安全勢(shì)場(chǎng)等級(jí)函數(shù)與優(yōu)化Floyd算法的改進(jìn)JPS算法。首先建立了安全等級(jí)函數(shù)對(duì)柵格地圖中的柵格狀態(tài)進(jìn)行重新賦值構(gòu)建安全等級(jí)地圖；然后改進(jìn)了啟發(fā)式函數(shù)，引入目標(biāo)與主方向兩項(xiàng)偏置函數(shù)項(xiàng)結(jié)合安全等級(jí)函數(shù)項(xiàng)，進(jìn)一步減少對(duì)稱性搜索帶來的時(shí)間消耗，改善了所規(guī)劃路徑的安全程度;其次通過添加二次平滑算法流程優(yōu)化了Floyd算法；最后結(jié)合B-spline樣條插值法，進(jìn)一步提高了改進(jìn)算法所規(guī)劃路徑的平滑程度。仿真實(shí)驗(yàn)驗(yàn)證了改進(jìn)優(yōu)化算法在內(nèi)存資源消耗、路徑長(zhǎng)度、路徑平滑程度以及路徑安全程度都有顯著提升。

關(guān)鍵詞：移動(dòng)機(jī)器人； 路徑規(guī)劃； JPS算法； Floyd算法； B-spline

中圖分類號(hào)：TP242 文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：1001-3695（2022）07-010-1985-07

doi：10.19734/j.issn.1001-3695.2021.12.0671

基金項(xiàng)目：裝備預(yù)研教育部聯(lián)合基金資助項(xiàng)目;四川省科技計(jì)劃資助項(xiàng)目（2021YJ0334）

作者簡(jiǎn)介：蔡佳成（1996-），男，四川達(dá)州人，碩士研究生，主要研究方向?yàn)橐苿?dòng)機(jī)器人路徑規(guī)劃、移動(dòng)機(jī)器人智能感知；白克強(qiáng)（1979-），男，甘肅慶陽人，副教授，碩導(dǎo)，主要研究方向?yàn)橐苿?dòng)機(jī)器人、人工智能；李旭春（1998-），女，四川巴中人，碩士研究生，主要研究方向?yàn)樽詣?dòng)控制、智能移動(dòng)機(jī)器人；黃正良（1962-），男，湖南益陽人，教授，博導(dǎo)，主要研究方向?yàn)榭刂评碚摵陀?jì)算機(jī)應(yīng)用技術(shù)研究；劉知貴（1966-），男（通信作者），四川射洪人，教授，博導(dǎo)，主要研究方向?yàn)橛?jì)算機(jī)技術(shù)及應(yīng)用研究、控制理論應(yīng)用及自動(dòng)化裝置研究（liuzhigui@swust.edu.cn.）.

Improved path planning algorithm for mobile robot based on JPS

Cai Jiacheng， Bai Keqiang， Li Xuchun， Huang Zhengliang， Liu Zhigui?

（School of Information Engineering， Southwest University of Science amp; Technology， Mianyang Sichuan 621010， China）

Abstract：Under a large-scale and complex environment， for the path planning algorithm of JPS， the memory consumption is large， the smoothness of path result is low， and the path result is excessively close to obstacles. Aiming at these problems， this paper proposed an improved JPS algorithm that integrated a level function of safety potential field and an optimized Floyd algorithm. It firstly built the safety level function and reassigned the grid status in the grid map to build a safety level map. Then by introducing two bias functions of goal and cardinal direction， and by combining the safety level function， this paper further reduced the time consumption brought by symmetric search， which improved the safety level of the path planned. Besides， it also optimized Floyd algorithm by adding a flow of second smoothing algorithm. At last， the paper integrated B-spline interpolation， improving the smoothness of path planned by the improved algorithm. The simulation tests verify that there are significant improvements in memory consumption， path length， path smoothness and path safety level for the improved and optimized algorithm.

Key words：mobile robot; path planning; JPS algorithm; Floyd algorithm; B-spline

0 引言

如今自主移動(dòng)機(jī)器人因其高度智能、高效、可靠等特點(diǎn)，已被廣泛應(yīng)用在各類工業(yè)、農(nóng)業(yè)、醫(yī)療居家服務(wù)以及軍事科考等危險(xiǎn)環(huán)境下的勘探巡檢等行業(yè)之中，其場(chǎng)景環(huán)境的復(fù)雜程度隨著機(jī)器人應(yīng)用場(chǎng)景的多樣化以及更多的人機(jī)互動(dòng)場(chǎng)景而增加^［1］。為保證機(jī)器人在此類環(huán)境中運(yùn)行的可靠性、完備性、能耗最優(yōu)以及速度最優(yōu)等性質(zhì)，需通過環(huán)境感知獲得自身的位姿與環(huán)境地圖的一致性估計(jì)之后，依據(jù)估計(jì)所得的先驗(yàn)環(huán)境信息運(yùn)用有效的路徑規(guī)劃算法可保證機(jī)器人在復(fù)雜大尺度環(huán)境下能快速有效地規(guī)劃出一條最優(yōu)的可行路徑^［2］。

根據(jù)先驗(yàn)環(huán)境信息的已知程度以及時(shí)效性可將路徑規(guī)劃分為全局路徑規(guī)劃與局部路徑規(guī)劃^［3］。全局路徑規(guī)劃為局部路徑規(guī)劃提供導(dǎo)引，避免局部路徑規(guī)劃陷入局部死鎖或局部最優(yōu)。局部路徑規(guī)劃為全局路徑規(guī)劃提供應(yīng)對(duì)動(dòng)態(tài)環(huán)境實(shí)時(shí)快速規(guī)劃的能力^［4］。全局路徑規(guī)劃的速度與所得路徑的質(zhì)量直接影響整個(gè)路徑規(guī)劃的效果?，F(xiàn)有的全局路徑規(guī)劃算法可分為三大類：a）基于柵格圖的啟發(fā)式搜索路徑規(guī)劃算法，如Dijkstra算法^［5］、A*算法^［6］、D*算法^［7］等；b）基于采樣的路徑規(guī)劃算法，如PRM^［8］、RRT^［9］以及RRT*算法^［10］等；c）各類智能仿生算法^［11］，如粒子群算法、人工魚群算法等。

基于柵格圖的啟發(fā)式搜索路徑規(guī)劃算法相較于基于采樣的算法和各類智能優(yōu)化算法存在路徑短、計(jì)算量小、資源消耗小、不會(huì)陷入局部最優(yōu)導(dǎo)致目標(biāo)點(diǎn)不可達(dá)等優(yōu)點(diǎn)。其中A*算法相較于其他基于柵格圖的啟發(fā)式搜索算法依據(jù)較為合理的啟發(fā)式設(shè)計(jì)被廣泛應(yīng)用在各類移動(dòng)機(jī)器人路徑規(guī)劃中，但A*算法仍存在搜索內(nèi)存消耗較大、路徑平滑性較差以及無法在動(dòng)態(tài)環(huán)境下運(yùn)行等問題。文獻(xiàn)［12］改進(jìn)雙向時(shí)效的方法，采用多鄰柵格距離計(jì)算方式加快路徑規(guī)劃效率的同時(shí)提升了路徑的平滑程度，但存在內(nèi)存占用資源較大的問題。文獻(xiàn)［13］運(yùn)用K-means聚類算法對(duì)柵格地圖進(jìn)行分區(qū)建模進(jìn)一步提高A*算法的搜索速率。文獻(xiàn)［14］為保障自主移動(dòng)消防機(jī)器人快速滅火的目的，添加Floyd算法平滑路徑，消除A*算法鄰域拓展時(shí)僅沿八個(gè)方向進(jìn)行拓展而產(chǎn)生的冗余節(jié)點(diǎn)問題。

以上方法皆是以A*算法的鄰域拓展方式進(jìn)行搜索，這將導(dǎo)致open list與closed list存在大量由相鄰柵格節(jié)點(diǎn)搜索產(chǎn)生的冗余判斷路徑節(jié)點(diǎn)，在大尺度環(huán)境下將大幅度降低路徑規(guī)劃的速度。Harabor等人^［15］提出了跳點(diǎn)搜索算法，通過對(duì)A*算法在拓展的路徑節(jié)點(diǎn)進(jìn)行修剪，大幅度提高了路徑規(guī)劃的速率。文獻(xiàn)［16］構(gòu)建正六邊形柵格，修改鄰居剪枝和強(qiáng)制鄰域判斷規(guī)則，提高了路徑規(guī)劃的效率以及規(guī)劃路徑的質(zhì)量，但由于鄰域拓展方向僅包含六邊形的六個(gè)方向，仍存在大量冗余的中繼節(jié)點(diǎn)。文獻(xiàn)［17］修改JPS算法，原有啟發(fā)式函數(shù)運(yùn)用切比雪夫距離代替歐氏距離能更精確地估計(jì)出實(shí)際響應(yīng)距離，進(jìn)一步加快了JPS算法路徑規(guī)劃的速度，但該方法未考慮所規(guī)劃路徑的平滑性。文獻(xiàn)［18］通過融合JPS算法與動(dòng)態(tài)窗口法加快獲得局部路徑規(guī)劃所需的局部目標(biāo)點(diǎn)，但該類目標(biāo)點(diǎn)不是最優(yōu)的局部目標(biāo)節(jié)點(diǎn)，導(dǎo)致最終動(dòng)態(tài)窗口法所規(guī)劃的路徑長(zhǎng)度增加。文獻(xiàn)［19］通過刪除中間的冗余節(jié)點(diǎn)進(jìn)而提高所規(guī)劃路徑的平滑程度，該方法未考慮JPS算法所生成路徑節(jié)點(diǎn)存在不連續(xù)的問題，在大尺度環(huán)境中的平滑性有所欠缺。文獻(xiàn)［20］定義一種新的跳點(diǎn)以及跳點(diǎn)域矩陣，通過選擇不同大小的跳點(diǎn)域矩陣獲取與障礙物間的有效距離，進(jìn)而提高所規(guī)劃路徑的安全性，但該方法并未考慮所規(guī)劃路徑的平滑程度。

綜上所述，現(xiàn)有JPS算法可以有效解決大尺度環(huán)境地圖下的路徑規(guī)劃算法效率問題，但并未兼顧規(guī)劃所得的路徑質(zhì)量，無法同時(shí)滿足規(guī)劃路徑的安全性以及平滑性。本文在此基礎(chǔ)上提出一種平滑安全跳點(diǎn)搜索（smooth safe jump point search，SSJPS）算法，該算法在保證高效性的同時(shí)進(jìn)一步提高了規(guī)劃路徑的平滑程度，降低了資源占用，提高了路徑的安全程度，同時(shí)解決了路徑姿態(tài)不連續(xù)問題。

1 算法基礎(chǔ)

1.1 環(huán)境地圖模型構(gòu)建

環(huán)境地圖模型構(gòu)建是整個(gè)路徑規(guī)劃最初的一個(gè)步驟，建立一個(gè)能準(zhǔn)確描述障礙物信息的環(huán)境地圖模型決定了一個(gè)路徑規(guī)劃方法的有效性。運(yùn)用在經(jīng)過激光雷達(dá)與視覺相機(jī)的信息建立機(jī)器人觀測(cè)模型，以及IMU 與編碼器信息建立機(jī)器人運(yùn)動(dòng)學(xué)模型，通過后端優(yōu)化的方法以及回環(huán)檢測(cè)建立全局一致性良好的全局地圖，同時(shí)將全局地圖柵格化建立全局的柵格地圖，如圖1所示。圖中黑色柵格為障礙物區(qū)域，記為不可通行節(jié)點(diǎn)，白色柵格為無障礙物區(qū)域，記為可通行區(qū)域節(jié)點(diǎn)。

1.2 JPS算法

JPS算法是由Harabor在A*算法的基礎(chǔ)上提出的一種減少鄰域拓展過程產(chǎn)生的大量冗余中繼節(jié)點(diǎn)而帶來的資源消耗的優(yōu)化策略^［15］。該策略包含跳點(diǎn)篩選規(guī)則、強(qiáng)制鄰域節(jié)點(diǎn)規(guī)則與跳躍規(guī)則。跳點(diǎn)篩選規(guī)則是對(duì)自然鄰域節(jié)點(diǎn)以及強(qiáng)制鄰域節(jié)點(diǎn)兩類節(jié)點(diǎn)進(jìn)行篩選。自然鄰域節(jié)點(diǎn)篩選規(guī)則是在鄰域拓展過程中所拓展節(jié)點(diǎn)x相較于其他節(jié)點(diǎn)而言，自父節(jié)點(diǎn)p（x）出發(fā)經(jīng)過該拓展節(jié)點(diǎn)x到目標(biāo)節(jié)點(diǎn)n的距離代價(jià)len小于其余中間節(jié)點(diǎn)，其規(guī)則定義為

強(qiáng)制鄰域節(jié)點(diǎn)篩選規(guī)則是指當(dāng)鄰域搜索過程中相鄰八向鄰域存在障礙物時(shí)，所拓展節(jié)點(diǎn)x的父節(jié)點(diǎn)p（x）經(jīng)過x到達(dá)目標(biāo)節(jié)點(diǎn)n的距離代價(jià)相較于其他不經(jīng)過x到達(dá)目標(biāo)節(jié)點(diǎn)n的距離代價(jià)len小，則稱n是x的強(qiáng)制鄰域節(jié)點(diǎn)，其規(guī)則定義為

跳躍規(guī)則是將篩選出的自然鄰域節(jié)點(diǎn)xnature中由前一節(jié)點(diǎn)經(jīng)對(duì)角線跳躍得到當(dāng)前節(jié)點(diǎn)x，以及具有強(qiáng)制鄰域節(jié)點(diǎn)xforced的當(dāng)前節(jié)點(diǎn)x作為鄰域拓展節(jié)點(diǎn)加入open list，并對(duì)相應(yīng)節(jié)點(diǎn)的啟發(fā)式代價(jià)函數(shù)值進(jìn)行比較，輸出最優(yōu)代價(jià)節(jié)點(diǎn)加入close list中。最終反向遞歸得到規(guī)劃路徑。

2 改進(jìn)JPS算法

2.1 構(gòu)建融入安全勢(shì)場(chǎng)函數(shù)的全局柵格地圖

針對(duì)JPS算法所規(guī)劃的路徑結(jié)果與障礙物距離較近的問題，本文提出一種融入安全勢(shì)場(chǎng)等級(jí)的全局柵格地圖構(gòu)建方法。通過改進(jìn)人工勢(shì)場(chǎng)函數(shù)作為安全等級(jí)函數(shù)，將與障礙物間的距離關(guān)系進(jìn)行更細(xì)化的表示，設(shè)立一定的安全閾值，解決路徑結(jié)果中的節(jié)點(diǎn)靠近障礙物這一問題。

為使機(jī)器人在不同尺度地圖中均具有較好的安全等級(jí)表示，添加自適應(yīng)調(diào)整因子α和β改進(jìn)斥力場(chǎng)函數(shù)F（n），求解障礙物相鄰區(qū)域每個(gè)柵格n的斥力函數(shù)值。其中自適應(yīng)調(diào)整因子可由全局柵格地圖大小msize與機(jī)器人本體柵格大小nsize通過不同的縮放倍數(shù)ζ與η求得。

則改進(jìn)斥力函數(shù)可被定義為

其中：r（n，nobs）為障礙物柵格節(jié)點(diǎn)與相鄰柵格節(jié)點(diǎn)的歐氏距離，即

同時(shí)為對(duì)安全等級(jí)進(jìn)行明確的層級(jí)劃分，進(jìn)一步對(duì)斥力函數(shù)作歸一化取整處理，獲得安全等級(jí)函數(shù)：

其中：argmaxx F（n）為全局柵格地圖所有柵格中的最大斥力函數(shù)值;argminx F（n）為最小斥力函數(shù)值，同時(shí)可通過N指定安全等級(jí)劃分層級(jí)。圖2為N=3的安全全局柵格地圖，S（n）函數(shù)值越大表示危險(xiǎn)程度越高，越小則安全程度越高。

2.2 基于目標(biāo)偏置函數(shù)與主方向偏置函數(shù)的改進(jìn)啟發(fā)式函數(shù)

JPS算法由于保留了A*算法的啟發(fā)式函數(shù)，導(dǎo)致其在鄰域拓展過程中依然存在對(duì)稱性搜索現(xiàn)象，本文SSJPS算法通過添加目標(biāo)偏置函數(shù)gbias（n）以及主方向偏置函數(shù)mbias（n），用于改善對(duì)稱性搜索帶來的冗余跳點(diǎn)、減少時(shí)間消耗以及內(nèi)存資源消耗，同時(shí)將安全等級(jí)函數(shù)加入啟發(fā)式函數(shù)進(jìn)一步提高所規(guī)劃路徑的安全性。其中目標(biāo)偏置函數(shù)gbias（n）為

其中：dmxi-goal與dmyi-goal分別為待估鄰域節(jié)點(diǎn)與目標(biāo)節(jié)點(diǎn)間的x與y方向上的曼哈頓距離;nsize與msize分別為機(jī)器人本體所占柵格大小和全局柵格地圖大小。

主方向偏置函數(shù)mbias（n）為

其中：dmxstart-goal與dmystart-goal分別為起始節(jié)點(diǎn)與目標(biāo)節(jié)點(diǎn)間的x與y方向上的曼哈頓距離。

由兩項(xiàng)偏置函數(shù)gbias（n）與mbias（n）、安全等級(jí)函數(shù)S（n）、當(dāng)前節(jié)點(diǎn)與起始節(jié)點(diǎn)間的距離代價(jià)G（n），可得改進(jìn)后的啟發(fā)式函數(shù)：

2.3 融合改進(jìn)Floyd與B-spline平滑路徑

JPS路徑規(guī)劃算法在鄰域拓展過程中僅沿著上、左、下、右、左上、左下、右上、右下八個(gè)方向行進(jìn)，這一過程產(chǎn)生多個(gè)冗余節(jié)點(diǎn)，增加路徑中總轉(zhuǎn)折角度，降低路徑的平滑程度。本文SSJPS算法引入了改進(jìn)Floyd算法，運(yùn)用其動(dòng)態(tài)規(guī)劃的思想，將規(guī)劃所得的多個(gè)節(jié)點(diǎn)進(jìn)行平滑處理去除冗余節(jié)點(diǎn)，通過優(yōu)化流程改進(jìn)Floyd算法優(yōu)化平滑處理的速度以及優(yōu)化結(jié)果，同時(shí)添加二次平滑優(yōu)化算法改善由跳點(diǎn)路徑坐標(biāo)不連續(xù)帶來的路徑平滑效果不佳問題，最后運(yùn)用B-spline保證所規(guī)劃路徑姿態(tài)的連續(xù)性。

2.3.1 改進(jìn)Floyd初步平滑路徑獲得關(guān)鍵節(jié)點(diǎn)

通過引入安全等級(jí)函數(shù)S（n）的改進(jìn)JPS算法規(guī)劃得到最終路徑及路徑中的多個(gè)跳點(diǎn)n1，n2，…，ni，…，nN，將其坐標(biāo)（xni，yni）放入節(jié)點(diǎn)矩陣Gn中，即

1）構(gòu)建距離判斷函數(shù) 為運(yùn)用Floyd算法求解余下跳點(diǎn)間的最近路徑節(jié)點(diǎn)配置Pathoptimal，構(gòu)造對(duì)應(yīng)的初始鄰接矩陣Dneb，需求出節(jié)點(diǎn)矩陣中任意兩點(diǎn)ni，nj∈Gn間的距離，同時(shí)判讀節(jié)點(diǎn)間的線路是否被障礙物阻擋，構(gòu)建如下函數(shù)：

其中：r（ni，nj）為節(jié)點(diǎn)ni、nj間的歐氏距離，可由式（5）求取;ε（ni，nj，nobs.k）為單位階躍函數(shù);nobs.k∈Aobs表示在碰撞判定區(qū)域Aobs中的障礙物集合。該集合滿足以下條件：

2）建立初始鄰接矩陣與頂點(diǎn)矩陣 建立鄰接矩陣與頂點(diǎn)矩陣是Floyd算法的核心。初始鄰接矩陣中每個(gè)矩陣元素的數(shù)值dij等于相應(yīng)角標(biāo)兩點(diǎn)間的距離d（ni，nj），該距離可由距離判斷函數(shù)式（11）求得，即初始鄰接矩陣為

同時(shí)可建立相應(yīng)的初始頂點(diǎn)矩陣，初始頂點(diǎn)矩陣中每個(gè)元素為-1，頂點(diǎn)矩陣為

初始鄰接矩陣和頂點(diǎn)矩陣的求解算法偽代碼如下。

算法1 初始鄰接矩陣Dneb與初始頂點(diǎn)T求解

輸入：路徑節(jié)點(diǎn)Gn=［n1，n2，…，nk，…，nN］=［（xn1，yn1），（xn2，yn2），…，（xnk，ynk），…，（xnN，ynN）］;障礙物節(jié)點(diǎn)Dobs=［dobs.1，dobs.2，…，dobs.N］。

輸出：初始鄰接矩陣Dneb與初始頂點(diǎn)矩陣T。

a）if N≤2 do

b） 不存在冗余節(jié)點(diǎn)

c）else

d） for i=1 to N

e） for j=1 to N

f） DCurrent=［ni，nj］=［（xni，yni），（xnj，ynj）］

g） 由式（11）求得dij

h） Dneb［i］［j］=dij

i） T［i］［j］=－1

j） end for

k） end for

l）end if

3）改進(jìn)Floyd算法迭代更新鄰接矩陣與頂點(diǎn)矩陣 在初始鄰接矩陣和頂點(diǎn)矩陣后，用Floyd動(dòng)態(tài)規(guī)劃的思想，迭代獲得最優(yōu)的鄰接矩陣與頂點(diǎn)矩陣。初始鄰接矩陣Dneb與T頂點(diǎn)矩陣已由2）所求得，對(duì)于每個(gè)節(jié)點(diǎn)nk，其中k∈［1，N］，以及任意一對(duì)節(jié)點(diǎn)ni、nj，其中i，j∈［1，N］，若存在Dneb［i］［j］gt;Dneb［i］［k］+Dneb［k］［j］，則更新鄰接矩陣Dneb［i］［j］的值為Dneb［i］［k］+Dneb［k］［j］，同時(shí)將頂點(diǎn)矩陣T［i］［j］改為k，由此迭代遍歷可獲得更新后的鄰接矩陣NewDneb與頂點(diǎn)矩陣NewT。

算法2 改進(jìn)Floyd算法更新鄰接矩陣Dneb與頂點(diǎn)矩陣T

輸入：初始鄰接矩陣Dneb;頂點(diǎn)矩陣T;節(jié)點(diǎn)個(gè)數(shù)N。

輸出：更新后的NewDneb;更新后的頂點(diǎn)矩陣NewT。

a）NewDneb=Dneb

b）NewT=T

c）for i=1 to N

d） for j=1 to N

e） for k=1 to N

f） if NewDneb［i］［j］gt;NewDneb［i］［k］+NewDneb［k］［j］

g） NewDneb［i］［j］=NewDneb［i］［k］+NewDneb［k］［j］

h） NewT［i］［j］=k

i） end if

j） end for

k） end for

l）end for

4）求解平滑路徑節(jié)點(diǎn)配置 確定起始節(jié)點(diǎn)nu和終末節(jié)點(diǎn)nv，最優(yōu)的鄰接矩陣NewDneb與頂點(diǎn)矩陣NewT已由3）求得，初始化兩個(gè)中繼節(jié)點(diǎn)nmid、nvar，令兩者分別為起始節(jié)點(diǎn)和終末節(jié)點(diǎn)，即nmid=nu，nvar=nv。然后判斷NewT［mid］［var］是否為-1，當(dāng)為-1時(shí)則判斷nvar為最優(yōu)節(jié)點(diǎn)，將其放入最優(yōu)節(jié)點(diǎn)配置Pathoptimal中，同時(shí)更新nmid節(jié)點(diǎn)為nvar，以及再次將節(jié)點(diǎn)nvar變?yōu)榻K末節(jié)點(diǎn)nv，重復(fù)這一過程直到中繼節(jié)點(diǎn)nmid與終末節(jié)點(diǎn)nv重合，輸出改進(jìn)Floyd算法的平滑節(jié)點(diǎn)配置Pathfloyd。

算法3 改進(jìn)Floyd算法回溯平滑節(jié)點(diǎn)配置

輸入：更新后的鄰接矩陣NewDneb與頂點(diǎn)矩陣NewT;起點(diǎn)nu與終點(diǎn)nv（u，v∈［1，N］）。

輸出：平滑節(jié)點(diǎn)配置Pathfloyd。

a）mid=u

b）var=v

c）將節(jié)點(diǎn)nu添加入Pathfloyd

d）while mid≠v do

e） if NewT［mid］［var］=－1

f） 將節(jié)點(diǎn)nvar加入平滑節(jié)點(diǎn)配置Pathfloyd中

g） mid=var

h） var=v

i） else

j） var=NewT［mid］［var］

k） end if

l）end while

5）二次平滑F(xiàn)loyd后的路徑節(jié)點(diǎn) 由于JPS算法輸出路徑節(jié)點(diǎn)僅為open list中的跳點(diǎn)，這將導(dǎo)致Floyd算法中無法獲取路徑中的每一個(gè)相鄰柵格的路徑節(jié)點(diǎn)，使得平滑路徑效果較差。本文設(shè)計(jì)二次平滑處理方法。依據(jù)4）可獲得改進(jìn)Floyd算法的最優(yōu)節(jié)點(diǎn)配置Pathfloyd，以相鄰三個(gè)節(jié)點(diǎn)作為一組，以步長(zhǎng)為a提取前兩個(gè)節(jié)點(diǎn)間的路徑節(jié)點(diǎn)。然后依次判斷提取的路徑節(jié)點(diǎn)與第三個(gè)節(jié)點(diǎn)間是否可通行，將第一個(gè)可通行節(jié)點(diǎn)彈出替代第二個(gè)節(jié)點(diǎn)放入最優(yōu)節(jié)點(diǎn)配置中。相鄰三個(gè)最優(yōu)節(jié)點(diǎn)配置Pathfloyd=［ni，ni+1，ni+2］，三點(diǎn)坐標(biāo)為（xni，yni）、（xni+1，yni+1）、（xni+2，yni+2），以步長(zhǎng)為a提取節(jié)ni、ni+1兩點(diǎn)間的j個(gè)路徑節(jié)點(diǎn)［n¹i_i+1，n²i_i+1，…，nji_i+1］，當(dāng)判斷從第一個(gè)節(jié)點(diǎn)ni以步長(zhǎng)d路徑節(jié)點(diǎn)過程中第一次出現(xiàn)可通行情況的路徑節(jié)點(diǎn)nki_i+1，則用該路徑節(jié)點(diǎn)替代節(jié)點(diǎn)ni，具體算法流程如算法4所示。

算法4 二次平滑最優(yōu)節(jié)點(diǎn)配置

輸入：最優(yōu)節(jié)點(diǎn)配置Pathfloyd=［n1，n2，…，nk，…，nN－M］=［（xn1，yn1），（xn2，yn2），…，（xnk，ynk），…，（xnN－M，ynN－M）］;障礙物矩陣Dobs=［dobs.1，dobs.2，…，dobs.k］;步長(zhǎng)為a。

輸出：二次平滑后的最終路徑節(jié)點(diǎn)配置finalPath。

a）for i=1 to M－N－2

b） if xnigt;xni+1 or ynigt;yni+1

c） d=a

d） else if xni≤xni+1 or yni≤yni+1

e） d=－a

f） end if

g） if xni≠xni+1 or yni=yni+1

h） while nki_i+1≠ni+1 do

i） k++

j） nki_i+1=（xni+kd，yni）

k） 由式（11）求得d（nki_i+1，ni+2）

l） if d（nki_i+1，ni+2）≠∞

m） 更新最優(yōu)節(jié)點(diǎn)配置Pathfloyd，令ni+1=nki_i+1

n） end if

o） end while

p） else if xni=xni+1 and yni≠yni+1

q） 過程同步驟h）～o），修改步驟j）為nki_i+1=（xni，yni+kd）

r） else if xni≠xni+1 and yni≠yni+1

s） if |xni－xni+1|gt;|yni－yni+1|

t） 過程同步驟h）～o），修改步驟j）為nki_i+1=（xni+kd，yni+kd（yni+1－yni）（xni+1－xni））

u） else if |xni－xni+1|≤|yni－yni+1|

v） 過程同步驟h）～o），修改步驟j）為nki_i+1=（xni+kd（xni+1－xni）（yni+1－yni），yni+kd）

w） end if //對(duì)應(yīng)步驟s）

x） end if //對(duì)應(yīng)步驟g）

y）end for //對(duì)應(yīng)步驟a）

z）finalPath=Pathfloyd

2.3.2 B-spline平滑關(guān)鍵節(jié)點(diǎn)

針對(duì)Floyd算法平滑后仍存在少量關(guān)鍵節(jié)點(diǎn)，即拐點(diǎn)存在角速度和線速度突變的問題，引入B-spline方法設(shè)定控制點(diǎn)與對(duì)應(yīng)的樣條基函數(shù)，通過線性組合獲得最終的平滑曲線。本文運(yùn)用三次B-spline平滑關(guān)鍵拐點(diǎn)獲得二階可導(dǎo)的平滑曲線，保證規(guī)劃路徑速度可導(dǎo)、加速度連線。如圖3所示，圖中節(jié)點(diǎn)ni即為上述提及的關(guān)鍵節(jié)點(diǎn)，運(yùn)用B-spline平滑此類節(jié)點(diǎn)主要是求解控制點(diǎn)坐標(biāo)以及對(duì)應(yīng)的樣條基函數(shù)，通過線性組合的方式以獲得最終的B-spline曲線F（u），即

其中：n為控制點(diǎn)數(shù)量;Ci為控制點(diǎn)坐標(biāo);Bi，d（u）為控制點(diǎn)Ci的樣條基函數(shù)。

求解平滑關(guān)鍵拐點(diǎn)ni的B-spline步驟如下：

a）確定控制點(diǎn)數(shù)量n。本文在關(guān)鍵拐點(diǎn)處設(shè)定如圖3所示的四個(gè)控制點(diǎn)Ci、Ci+1、Ci+2、Ci+3，由此平滑關(guān)鍵拐點(diǎn)ni。

b）求解控制點(diǎn)坐標(biāo)。如圖3所示，圖中Pni－1、Pni、Pni+1三點(diǎn)為相鄰三個(gè)關(guān)鍵拐點(diǎn)的中心點(diǎn)，其坐標(biāo)分別為（xPn_i－1，yPn_i－1）、（xPn_i，yPn_i）、（xPn_i+1，yPn_i+1），求解四個(gè)關(guān)鍵控制點(diǎn)Ci、Ci+1、Ci+2、Ci+3的位置坐標(biāo)。首尾兩控制點(diǎn)為Ci和Ci+3，其中控制點(diǎn)Ci的坐標(biāo)為

控制點(diǎn)Ci+3則是將控制點(diǎn)Ci求解過程中的xPn_i－1與yPn_i－1變換為xPn_i+1與yPn_i+1，即可求得其對(duì)應(yīng)坐標(biāo)。中間兩控制點(diǎn)Ci+1、Ci+2坐標(biāo)分別為

c）求解樣條基函數(shù)Bi，d（u）主要運(yùn)用Cox-deBoor遞推公式與基樣條初值迭代求解。樣條基函數(shù)為

Bi，d（u）=u－uiui+k－1－ui×Bi，d－1（u）+ui+k－uui+k－ui+1×Bi+1，d－1（u）（19）

基樣條初值為

其中：u為knots節(jié)點(diǎn)，其個(gè)數(shù)為N，由樣條函數(shù)的階數(shù)d=3以及控制點(diǎn)的個(gè)數(shù)n確定，即

本文為保證平滑曲線能更好地符合移動(dòng)機(jī)器人運(yùn)動(dòng)學(xué)與動(dòng)力學(xué)約束，取樣條函數(shù)階數(shù)d=3，控制點(diǎn)個(gè)數(shù)n=4，即可獲得knots節(jié)點(diǎn)序列U為

整體遞推迭代流程如圖4所示。

d）獲得B-spline。通過b）獲得的控制點(diǎn)Ci以及c）中求得控制點(diǎn)Ci對(duì)應(yīng)樣條基函數(shù)Bi，d（u），可獲得B-spline為

F（u）=［Ci Ci+1 Ci+2 Ci+3 ］Bi，3（u）Bi+1，3（u）Bi+2，3（u）Bi+3，3（u）（23）

本文SSJPS算法整體流程如圖5所示。

3 算法仿真與分析

為驗(yàn)證本文SSJPS算法在大尺度復(fù)雜環(huán)境下的有效性，在物流倉庫地圖、室內(nèi)場(chǎng)景地圖以及復(fù)雜迷宮地圖三個(gè)地圖中與傳統(tǒng)A*算法^［6］、運(yùn)用Floyd算法改進(jìn)A*算法^［14］、JPS算法^［15］、IJPS算法^［17］、SD-JPS算法^［20］進(jìn)行對(duì)比實(shí)驗(yàn)。算法實(shí)驗(yàn)運(yùn)行硬件環(huán)境：CPU為AMD R7-4800H主頻2.9 GHz，內(nèi)存大小16 GB。仿真軟件為MATLAB 2021a。整個(gè)實(shí)驗(yàn)首先驗(yàn)證引入的目標(biāo)偏置函數(shù)以及主方向偏置函數(shù)對(duì)JPS路徑規(guī)劃效率的提升效果；然后針對(duì)不同步長(zhǎng)a所對(duì)應(yīng)的二次平滑優(yōu)化結(jié)果進(jìn)行實(shí)驗(yàn)；之后對(duì)比A*、Floyd改進(jìn)A*、JPS、IJPS、SD-JPS以及SSJPS在三個(gè)地圖場(chǎng)景中的時(shí)間消耗與內(nèi)存消耗。最后以路徑結(jié)果質(zhì)量，即路徑長(zhǎng)度、轉(zhuǎn)動(dòng)角度以及碰撞危險(xiǎn)程度三項(xiàng)指標(biāo)對(duì)六種算法進(jìn)行對(duì)比分析。

3.1 兩項(xiàng)偏置函數(shù)算法效率優(yōu)化效果

目標(biāo)及主方向兩項(xiàng)偏置函數(shù)主要針對(duì)大尺度復(fù)雜環(huán)境的路徑規(guī)劃效率進(jìn)行改善，消除對(duì)稱性搜索導(dǎo)致的冗余時(shí)間，具體實(shí)驗(yàn)設(shè)置如下：設(shè)定大小分別為50×50、100×100、300×300、500×500以及1000×1000的隨機(jī)地圖，起點(diǎn)分別為（3，3）、（3，3）、（5，5）、（5，5）與（15，15），終點(diǎn)分別為（47，47）、（98，98）、（295，295）、（495，495）與（985，985），對(duì)比本文所提兩項(xiàng)偏置函數(shù)下的JPS算法相較于常用以歐氏距離為啟發(fā)式函數(shù)的JPS算法的路徑規(guī)劃時(shí)間，取10次路徑規(guī)劃所耗的平均時(shí)間作為主要評(píng)價(jià)指標(biāo)，兩類算法規(guī)劃路徑結(jié)果如圖6所示，所用時(shí)間如圖7所示。路徑規(guī)劃所耗時(shí)間的具體數(shù)值結(jié)果如表1所示，本文算法所提兩項(xiàng)偏置函數(shù)有效解決了隨機(jī)地圖中大量的對(duì)稱性搜索帶來的時(shí)間消耗。

3.2 二次平滑優(yōu)化結(jié)果

二次平滑主要解決JPS算法所得路徑節(jié)點(diǎn)不連續(xù)，導(dǎo)致改進(jìn)Floyd算法平滑效果不佳，而不同步長(zhǎng)a對(duì)應(yīng)不同的二次平滑效果。該部分實(shí)驗(yàn)主要研究不同步長(zhǎng)a平衡路徑長(zhǎng)度、角度縮減量與時(shí)間耗散程度三者之間的關(guān)系，以最大線速度和角速度作為中間變量，求解平衡效果最佳的步長(zhǎng)參數(shù)a。設(shè)置如下實(shí)驗(yàn)：設(shè)定200×200大小的倉庫地圖;起點(diǎn)坐標(biāo)為（6，6） ，終點(diǎn)坐標(biāo)為（194，194）;以改進(jìn)Floyd算法平滑結(jié)果（無二次平滑）、步長(zhǎng)分別為a=10、a=5、a=1、a=0.5以及a=0.25六個(gè)對(duì)象進(jìn)行實(shí)驗(yàn)。

實(shí)驗(yàn)中評(píng)價(jià)指標(biāo)主要包含路徑長(zhǎng)度縮減率Ratel、轉(zhuǎn)角度數(shù)縮減率Rateθ、時(shí)間耗散率RateT以及綜合所有的三者的優(yōu)化率Rateoptimal四項(xiàng)指標(biāo)作為最優(yōu)參數(shù)a的評(píng)價(jià)指標(biāo)。其中前三項(xiàng)指標(biāo)皆為六個(gè)對(duì)象相應(yīng)指標(biāo)xjps_a與平滑前路徑對(duì)應(yīng)指標(biāo)xjps_init的變化率，x分別為路徑長(zhǎng)度l、轉(zhuǎn)角度數(shù)θ以及耗散時(shí)間T，則有三項(xiàng)評(píng)價(jià)指標(biāo)為

路徑長(zhǎng)度縮減率：

轉(zhuǎn)角度數(shù)縮減率：

時(shí)間耗散率：

優(yōu)化率則是假設(shè)機(jī)器人在最高線速度vmax=1 m/s，最高角速度wmax=3 rad/s的條件下。假設(shè)在相應(yīng)時(shí)間消耗情況下保持最高線速度與角速度對(duì)應(yīng)的位姿變化量ΔPmax，平滑后的位姿變化量為ΔPa，則優(yōu)化率為

其中：ΔPmax=（ljps_init－ljps_a）+（θjps_init－θjps_a），ΔPa=（vmax+wmax）（Tjps_a－Tjps_init）。

實(shí)驗(yàn)結(jié)果如圖8所示，其中圖8（a）為不同步長(zhǎng)a下的路徑規(guī)劃結(jié)果，步長(zhǎng)a值越小，則對(duì)應(yīng)路徑長(zhǎng)度與轉(zhuǎn)角度數(shù)越小。同時(shí)如圖8（b）所示，當(dāng)步長(zhǎng)alt;1時(shí)，長(zhǎng)度與角度縮短率變緩，但時(shí)間耗散率急劇增加，導(dǎo)致最終優(yōu)化率開始下降，遂選擇步長(zhǎng)a=1平衡時(shí)間消耗與路徑質(zhì)量間的關(guān)系。

3.3 規(guī)劃算法效率與資源占用對(duì)比分析

本文以平局路徑規(guī)劃時(shí)間Tavg、占用內(nèi)存大小SizeRAM作為評(píng)價(jià)指標(biāo)衡量路徑規(guī)劃算法效率以及資源占用的問題。其中平局路徑規(guī)劃時(shí)間Tavg是六種路徑規(guī)劃方法取10次規(guī)劃所用時(shí)間的平均值，占用內(nèi)存大小則是存儲(chǔ)相應(yīng)路徑規(guī)劃結(jié)果的路徑節(jié)點(diǎn)所占用的內(nèi)存大小。

實(shí)驗(yàn)設(shè)置A*、Floyd A^*、JPS、IJPS、SD-JPS以及SSJPS六種算法分別在三個(gè)地圖場(chǎng)景中進(jìn)行對(duì)比實(shí)驗(yàn)，為保證算法的實(shí)用性以及在應(yīng)對(duì)大尺度復(fù)雜環(huán)境的有效性，設(shè)置三個(gè)地圖場(chǎng)景分別為200×200大小的物流倉庫地圖、300×300大小的室內(nèi)場(chǎng)景地圖以及500×500大小的復(fù)雜迷宮地圖。物流倉庫地圖設(shè)定起點(diǎn)坐標(biāo)為（6，6） ，終點(diǎn)坐標(biāo)為（194，194）；室內(nèi)場(chǎng)景地圖設(shè)定起點(diǎn)坐標(biāo)為（6，6），終點(diǎn)坐標(biāo)為（294，294）；復(fù)雜迷宮地圖設(shè)定起點(diǎn)坐標(biāo)為（6，6），終點(diǎn)坐標(biāo)為（494，494）。路徑規(guī)劃結(jié)果如圖9所示。

表2中SSJPS算法相較于傳統(tǒng)A*與Floyd A*算法而言，平均路徑規(guī)劃時(shí)間均有較大提升，在物流倉庫中相較于傳統(tǒng)A*算法時(shí)間縮短了93.77%，相較于Floyd A*算法縮短了95.60%。地圖越復(fù)雜尺度越大，SSJPS算法提升效果越明顯。在500×500迷宮地圖中，傳統(tǒng)A*以及Floyd A*算法規(guī)劃所耗時(shí)間分別約為SSJPS算法的66倍以及91倍，SSJPS算法效率相對(duì)于A*類算法有顯著提升。在物流倉庫地圖中，SSJPS算法引入兩項(xiàng)偏置函數(shù)，相較于JPS類算法雖減少了平滑前的路徑規(guī)劃時(shí)間，但地圖中并未出現(xiàn)太多對(duì)稱性搜索情況，并且兩階段的平滑過程還需消耗少量時(shí)間，導(dǎo)致最終規(guī)劃時(shí)間相較于JPS算法增加了28.71%。不過在資源消耗方面，SSJPS算法相較于JPS、IJPS以及SD-JPS算法的占用內(nèi)存分別減少了42.85%、50%以及42.85%，在室內(nèi)地圖中相對(duì)于JPS、IJPS以及SD-JPS算法分別以30.91%、33.05%與23.50%的時(shí)間代價(jià)減少了42.85%、50%以及42.85%的占用內(nèi)存大小。且隨著地圖的尺度與復(fù)雜程度增加，SSJPS相較于JPS算法以更少的時(shí)間作為代價(jià)進(jìn)一步減少占用內(nèi)存大小。在500×500的復(fù)雜迷宮地圖中，相較JPS、IJPS算法的時(shí)間代價(jià)分別為12.44%、18.40%，相較于SD-JPS則速度提升了6.39%，同時(shí)占用內(nèi)存大小相較于JPS與SD-JPS算法分別減少了53.33%以及70.83%，而IJPS則是由于啟發(fā)式函數(shù)的影響導(dǎo)致其并未進(jìn)入復(fù)雜環(huán)境區(qū)域而進(jìn)行了繞行，導(dǎo)致其路徑節(jié)點(diǎn)減少。SSJPS算法在算法效率上，相較傳統(tǒng)A*和Floyd A*算法有顯著提升，在資源占用方面相較A*與JPS算法均有明顯改善。

3.4 規(guī)劃算法路徑質(zhì)量對(duì)比分析

本文為對(duì)比規(guī)劃算法所規(guī)劃路徑的平滑程度，以及安全程度以路徑長(zhǎng)度lsum、轉(zhuǎn)動(dòng)角度θsum、速度突變次數(shù)Nmutation以及危險(xiǎn)評(píng)價(jià)函數(shù)值Frisk作為路徑質(zhì)量的評(píng)價(jià)指標(biāo)。路徑長(zhǎng)度以一個(gè)柵格為1 m作為標(biāo)度；轉(zhuǎn)動(dòng)角度θsum是指本體位姿發(fā)生的角度變化；速度突變次數(shù)Nmutation是指機(jī)器人按照規(guī)劃路徑跟蹤控制速度突變導(dǎo)致路徑姿態(tài)不連續(xù)的次數(shù)；危險(xiǎn)評(píng)價(jià)函數(shù)值Frisk由路徑長(zhǎng)度lsum與大于設(shè)定安全等級(jí)函數(shù)閾值的危險(xiǎn)路徑長(zhǎng)度lrisk的比值確定，即

該部分實(shí)驗(yàn)以融入N=3的安全勢(shì)場(chǎng)等級(jí)函數(shù)后的三種不同地圖作為背景，得到如圖10所示的路徑規(guī)劃結(jié)果顯示圖。

表3中SSJPS與Floyd A*算法在路徑長(zhǎng)度lsum以及轉(zhuǎn)角度數(shù)θsum上要明顯優(yōu)于傳統(tǒng)A*、JPS、LJPS以及SD-JPS，但SSJPS考慮到路徑的安全程度，導(dǎo)致路徑長(zhǎng)度lsum與轉(zhuǎn)角度數(shù)θsum略大于Floyd A*算法。同時(shí)SSJPS算法通過引入安全等級(jí)函數(shù)以及B-spline提高規(guī)劃路徑安全性的同時(shí)，保證了路徑姿態(tài)的連續(xù)性。

4 結(jié)束語

本文針對(duì)JPS路徑規(guī)劃算法在大尺度復(fù)雜環(huán)境中存在內(nèi)存資源占用較大、安全性較低、規(guī)劃路徑不夠平滑、姿態(tài)變化不連續(xù)等問題，提出一種改進(jìn)優(yōu)化算法SSJPS，構(gòu)建安全等級(jí)函數(shù)，將其加入啟發(fā)式函數(shù)，提高路徑規(guī)劃的安全性；運(yùn)用主方向偏置函數(shù)與目標(biāo)偏置函數(shù)減少JPS算法在大尺度復(fù)雜環(huán)境中的對(duì)稱性搜索，加快路徑規(guī)劃的速率，減少不必要的中間路徑節(jié)點(diǎn)；結(jié)合改進(jìn)優(yōu)化Floyd算法，減少由八向鄰域拓展產(chǎn)生的冗余路徑節(jié)點(diǎn)，提高了路徑平滑程度，同時(shí)優(yōu)化其平滑處理算法加快平滑處理運(yùn)算；設(shè)計(jì)二次平滑方法，避免改進(jìn)優(yōu)化Floyd算法在處理JPS路徑規(guī)劃算法所得路徑節(jié)點(diǎn)，即跳點(diǎn)間的路徑節(jié)點(diǎn)不連續(xù)問題，影響路徑平滑質(zhì)量；設(shè)定控制節(jié)點(diǎn)運(yùn)用B-spline對(duì)平滑后的拐點(diǎn)進(jìn)行處理，保證整體路徑節(jié)點(diǎn)間姿態(tài)的連續(xù)性。通過實(shí)驗(yàn)對(duì)比分析，證明了SSJPS算法在大尺度復(fù)雜環(huán)境中不耗散過多時(shí)間的同時(shí)，降低了內(nèi)存資源占用、提高了路徑平滑程度、保證了路徑的安全性，為之后的路徑跟蹤提供了連續(xù)的姿態(tài)節(jié)點(diǎn)。在未來研究中，可將SSJPS算法與局部路徑規(guī)劃方法進(jìn)行更好的結(jié)合，解決當(dāng)局部路徑規(guī)劃方法在依據(jù)全局路徑規(guī)劃作為導(dǎo)向時(shí)出現(xiàn)二次死鎖并進(jìn)行重規(guī)劃的這類問題，同時(shí)考慮在接下來的工作中將本文算法應(yīng)用于實(shí)際的機(jī)器人系統(tǒng)中。

參考文獻(xiàn)：

[1]Garaffa L C，Basso M，Konzen A A，et al.Reinforcement learning for mobile robotics exploration：a survey［J/OL］.IEEE Trans on Neural Networks and Learning Systems.（2021）.https：//doi.org/10.1109/TNNLS.2021.3124466.

［2]Rubio F，Valero F，Llopis-Albert C.A review of mobile robots：concepts，methods，theoretical framework，and applications［J］.International Journal of Advanced Robotic Systems，2019，16（2）：1736996972.

［3]Low E S，Ong P，Cheah K C.Solving the optimal path planning of a mobile robot using improved Q-learning［J］.Robotics and Autonomous Systems，2019，115：143-161.

［4]王洪斌，尹鵬衡，鄭維，等.基于改進(jìn)的A*算法與動(dòng)態(tài)窗口法的移動(dòng)機(jī)器人路徑規(guī)劃［J］.機(jī)器人，2020，42（3）：346-353.（Wang Hongbin，Yin Pengheng，Zheng Wei，et al.Mobile robot path planning based on improved A* algorithm and dynamic window method［J］.Robots，2020，42（3）：346-353.）

［5]Wang Zhiyong，Zlatanova S.Safe route determination for first respon-ders in the presence of moving obstacles［J］.IEEE Trans on Intelligent Transportation Systems，2020，21（3）：1044-1053.

［6]Everson L R，Sapatnekar S S，Kim C H.A time-based intra-memory computing graph processor featuring A* wavefront expansion and 2-D gradient control［J］.IEEE Journal of Solid-State Circuits，2021，56（7）：2281-2290.

［7]Maurovic＇ I，Seder M，Lenac K，et al.Path planning for active SLAM based on the D* algorithm with negative edge weights［J］.IEEE Trans on Systems，Man，and Cybernetics：Systems，2018，48（8）：1321-1331.

［8]Kai Cao，Qian Cheng，Song Gao，et al.Improved PRM for path planning in narrow passages［C］//Proc of the 16th IEEE International Conference on Mechatronics and Automation .Piscataway，NJ：IEEE Press，2019：45-50.

［9]Da Silva Costa L，Tonidandel F.DVG+A* and RRT path-planners：a comparison in a highly dynamic environment［J］.Journal of Intelligent amp; Robotic Systems，2021，101（3）：article No.58.

［10]Karaman S，F(xiàn)razzoli E.Sampling-based algorithms for optimal motion planning［J］.The International Journal of Robotics Research，2011，30（7）：846-894.

［11]于振中，李強(qiáng)，樊啟高.智能仿生算法在移動(dòng)機(jī)器人路徑規(guī)劃優(yōu)化中的應(yīng)用綜述［J］.計(jì)算機(jī)應(yīng)用研究，2019，36（11）：3210-3219.（Yu Zhenzhong，Li Qiang，F(xiàn)an Qigao.Survey on application of bioinspired intelligent algorithms in path planning optimization of mobile robots［J］.Application Research of Computers，2019，36（11）：3210-3219.）

［12]高民東，張雅妮，朱凌云.應(yīng)用于機(jī)器人路徑規(guī)劃的雙向時(shí)效A*算法［J］.計(jì)算機(jī)應(yīng)用研究，2019，6（3）：792-795，800.（Gao Min-dong，Zhang Yani，Zhu Lingyun.Bidirectional time-efficient A* algorithm for robot path planning［J］.Application Research of Compu-ters，2019，36（3）：792-795，800.）

［13]余文凱，章政，付雪畫，等.基于地圖預(yù)處理及改進(jìn)A*算法的路徑規(guī)劃［J］.高技術(shù)通信，2020，30（4）：383-390.（Yu Wenkai，Zhang Zheng，F(xiàn)u Xuehua，et al.Path planning based on map partition preprocessing and improved A* algorithm［J］.Chinese High Technology Letters，2020，30（4）：383-390.）

［14]Liu Yongtao，Sun Ruizhi，Zhang Tianyi，et al.Warehouse-oriented optimal path planning for autonomous mobile fire-fighting robots［J］.Security and Communication Networks，2020，2020：article ID 6371814 .

［15]Harabor D，Grastien A.Online graph pruning for pathfinding on grid maps［C］//Proc of the 25th AAAI Conference on Artificial Intelligence.Palo Alto，CA：AAAI Press，2011：1114-1119.

［16]王文明，杜佳璐.基于正六邊形柵格JPS算法的智能體路徑規(guī)劃［J］.系統(tǒng)工程與電子技術(shù)，2021，43（12）：3635-3642.（Wang Wenming，Du Jialu.Agent path planning based on regular hexagon grid JPS algorithm［J］.Systems Engineering and Electronics，2021，43（12）：3635-3642.）

［17]張慶，劉旭，彭力，等.融合JPS和改進(jìn)A*算法的移動(dòng)機(jī)器人路徑規(guī)劃 ［J］.計(jì)算機(jī)科學(xué)與探索，2021，15（11）：2233-2240.（Zhang Qing，Liu Xu ，Peng Li，et al.Path planning for mobile robots based on JPS and improved A* algorithm［J］.Journal of Frontiers of Computer Science and Technology，2021，15（11）：2233-2240.）

［18]Liu Lisang，Yao Jinxin，He Dongwei，et al.Global dynamic path planning fusion algorithm combining jump-A* algorithm and dynamic window approach［J］.IEEE Access，2021，9：19632-19638.

［19]Zafar M A，Zhang Zheng，Yu Wenkai.Mobile robots path planning based on A* algorithm improved with jump point search［C］//Proc of the 18th International Bhurban Conference on Applied Sciences and Technologies .Piscataway，NJ：IEEE Press，2021：536-544.

［20]Zheng Xue ，Tu Xiaowei，Yang Qinghua.Improved JPS algorithm using new jump point for path planning of mobile robot［C］//Proc of the 16th IEEE International Conference on Mechatronics and Automation.Piscataway，NJ：IEEE Press，2019：2463-2468.