基于正六邊形柵格JPS算法的智能體路徑規(guī)劃

王文明, 杜佳璐

(1. 大連海事大學(xué)輪機(jī)工程學(xué)院, 遼寧 大連 116026;2. 大連海事大學(xué)船舶電氣工程學(xué)院, 遼寧 大連 116026)

0 引 言

隨著現(xiàn)代科技的飛速發(fā)展,無人車、無人機(jī)、無人船等智能體應(yīng)運(yùn)而生,并被廣泛應(yīng)用于各個領(lǐng)域。智能體的路徑規(guī)劃技術(shù)是實(shí)現(xiàn)其自主導(dǎo)航的關(guān)鍵技術(shù)之一,也是智能化水平的體現(xiàn)。智能體的路徑規(guī)劃旨在根據(jù)當(dāng)前的任務(wù)需求,規(guī)劃出一條從起始點(diǎn)至目標(biāo)點(diǎn)無碰撞、安全合理的路徑[1],其核心是路徑規(guī)劃算法的設(shè)計(jì)。從傳統(tǒng)算法到各種算法的組合優(yōu)化,再到結(jié)合仿生學(xué)發(fā)展起來的智能優(yōu)化算法[2],路徑規(guī)劃算法已經(jīng)取得了巨大的進(jìn)步。不同的路徑規(guī)劃算法有著其各自適用的范圍和領(lǐng)域,傳統(tǒng)的全局路徑規(guī)劃方法有Dijkstra算法[3]、A*算法[4]、跳點(diǎn)搜索(jump point search,JPS)算法[5]、人工勢場法[6]等。其中,JPS算法是Daniel Harabor和Alban Grastien于2011年提出的正方形柵格地圖下的路徑規(guī)劃算法。該方法優(yōu)化了A*算法尋找后繼節(jié)點(diǎn)的操作,提高了路徑規(guī)劃效率[7],因此被廣泛應(yīng)用于智能體的全局路徑規(guī)劃[8-13]。

2016年邱磊[14]等利用JPS算法解決移動機(jī)器人的路徑規(guī)劃問題,并在障礙物分布情況不同的3張地圖上進(jìn)行仿真驗(yàn)證,進(jìn)而與A*算法進(jìn)行仿真比較,結(jié)果表明,在保證路徑最短的前提下,JPS算法的路徑規(guī)劃效率比A*算法高。2019年Ma[15]等利用JPS算法解決了機(jī)器人在家庭服務(wù)過程中的室內(nèi)路徑規(guī)劃問題,仿真結(jié)果也表明JPS算法比A*算法路徑規(guī)劃效率高。2020年武達(dá)[16]等利用JPS算法解決礦用機(jī)器人在礦井巷道內(nèi)的避障路徑規(guī)劃問題,仿真實(shí)驗(yàn)結(jié)果表明JPS算法的路徑規(guī)劃速度較傳統(tǒng)A*算法提高了約2倍。然而,傳統(tǒng)正方形柵格JPS(后文簡稱傳統(tǒng)JPS)算法規(guī)劃出的路徑存在穿越墻角的不安全行為,智能體跟蹤該路徑移動易與障礙物發(fā)生碰撞。近年來有研究者以正六邊形代替正方形對環(huán)境地圖進(jìn)行柵格化建模,并在正六邊形柵格地圖的基礎(chǔ)上結(jié)合蟻群算法[17-18]、A*算法[19-20]等解決智能體的路徑規(guī)劃問題,結(jié)果表明與基于正方形柵格地圖所規(guī)劃的路徑相比,基于正六邊形柵格地圖所規(guī)劃的路徑可以避免穿越墻角的行為,與障礙物的距離更安全合理。

受上述文獻(xiàn)啟發(fā),利用正六邊形柵格地圖解決傳統(tǒng)JPS算法規(guī)劃所得路徑存在穿越墻角的不安全行為。但在正六邊形柵格地圖上應(yīng)用傳統(tǒng)JPS算法存在搜索方向不確定、強(qiáng)制鄰居判斷規(guī)則、跳點(diǎn)搜索策略不適用等問題,為此本文修改傳統(tǒng)JPS算法的鄰居剪枝、強(qiáng)制鄰居判斷的規(guī)則和跳點(diǎn)搜索策略,提出一種新的正六邊形柵格JPS(后文簡稱HJPS)算法,提高了智能體路徑規(guī)劃的質(zhì)量和效率。

1 HJPS算法的正六邊形柵格地圖建模

圖1所示的六邊形稱為頂角型正六邊形。

圖1 頂角型正六邊形Fig.1 Vertex type regular hexagon

如圖2所示,在二維平面環(huán)境中有一長為L、寬為W的矩形區(qū)域,其內(nèi)部分布著有限個靜態(tài)障礙物。為便于研究并保證利用HJPS算法進(jìn)行路徑規(guī)劃的合理性,做出以下假設(shè):

假設(shè) 1智能體在直徑為a的圓形范圍內(nèi)；

假設(shè) 2智能體的移動指從所在柵格中心點(diǎn)移動至鄰居?xùn)鸥竦闹行狞c(diǎn)；

假設(shè) 3在智能體移動過程中,周圍環(huán)境保持不變。

圖2 矩形區(qū)域地圖Fig.2 Rectangular area map

在上述條件下構(gòu)建正六邊形柵格地圖,如圖3所示,設(shè)定矩形區(qū)域的左上角為原點(diǎn)O,建立直角坐標(biāo)系O-XY,規(guī)定水平向右為X軸正方向,豎直向下為Y軸正方向,采用邊長為a相同大小的頂角型正六邊形柵格鋪滿矩形區(qū)域,考慮假設(shè)1和假設(shè)2,智能體在該正六邊形柵格地圖中可被視作質(zhì)點(diǎn)。進(jìn)而根據(jù)矩形區(qū)域的實(shí)際環(huán)境情況將柵格標(biāo)記為白色和黑色柵格,智能體可自由通過的柵格被標(biāo)記成白色柵格,稱為自由柵格;部分或全部由障礙物占據(jù)的柵格被標(biāo)記成黑色柵格,稱為障礙物柵格,智能體不能通過該柵格。

圖3 矩形區(qū)域的正六邊形柵格地圖Fig.3 Regular hexagon grid map of rectangular area

圖4 智能體的移動方向Fig.4 Moving directions of agent

圖5為智能體在不同柵格地圖中的避障移動方式示意圖,由圖5可見,對比智能體在正方形柵格地圖中的避障移動方式,智能體在正六邊形柵格地圖中的避障移動方式可避免穿越墻角的不安全行為,因此避障過程更安全合理。

圖5 智能體避障移動方式示意圖Fig.5 Schematic diagram of obstacle avoidance moving ways of agent

2 HJPS算法

在A*算法的框架基礎(chǔ)上,傳統(tǒng)JPS算法通過鄰居剪枝、強(qiáng)制鄰居判斷的規(guī)則和JPS策略搜尋后繼節(jié)點(diǎn)[22],如圖6所示,xp為節(jié)點(diǎn)x的父節(jié)點(diǎn),J為跳點(diǎn),N為強(qiáng)制鄰居。若要在xp指向x的方向上尋找后繼節(jié)點(diǎn),鄰居剪枝是剪枝掉圖中灰色柵格所代表的鄰居節(jié)點(diǎn);強(qiáng)制鄰居是在當(dāng)前搜索方向周圍存在障礙物時必須被考慮的鄰居節(jié)點(diǎn),如節(jié)點(diǎn)N;JPS策略是如何搜索到伴有強(qiáng)制鄰居的跳點(diǎn)。上述過程可確定跳點(diǎn)J為xp指向x方向上的后繼節(jié)點(diǎn)。

圖6 東方向上尋找后繼節(jié)點(diǎn)示意圖Fig.6 Schematic diagram of finding the successor node in the east direction

在正六邊形柵格地圖上,智能體的移動方向由正方形柵格地圖情況下的8個變?yōu)?個,跳點(diǎn)搜索方向隨之變化,導(dǎo)致傳統(tǒng)JPS算法的鄰居剪枝和強(qiáng)制鄰居判斷的規(guī)則均不再適用,因此需要針對正六邊形柵格地圖的具體情況修改鄰居剪枝和強(qiáng)制鄰居判斷的規(guī)則,并制定新的跳點(diǎn)搜索策略,以在正六邊形柵格地圖中實(shí)現(xiàn)JPS算法,即HJPS算法。

2.1 三斜軸坐標(biāo)系

三斜軸坐標(biāo)系O-xyz如圖7所示,坐標(biāo)原點(diǎn)為O,Ox、Oy和Oz軸與水平方向的夾角分別為30°、150°和270°[20]。若正六邊形的邊長為a,則設(shè)坐標(biāo)軸的單位長度s=1.5a,從某節(jié)點(diǎn)d1分別向Ox、Oy、Oz軸作垂線,交于a、b、c三點(diǎn),則d1的坐標(biāo)為

(1)

圖7 正六邊形三斜軸坐標(biāo)系Fig.7 Regular hexagon coordinate system with three inclined axes

利用直角坐標(biāo)系構(gòu)建正六邊形柵格地圖便于障礙物信息的存儲,但在直角坐標(biāo)系中,當(dāng)某柵格節(jié)點(diǎn)位于奇數(shù)行或偶數(shù)行時,其6個鄰居節(jié)點(diǎn)的坐標(biāo)需要通過不同的坐標(biāo)關(guān)系進(jìn)行計(jì)算;而在三斜軸坐標(biāo)系中,已知任一正六邊形柵格節(jié)點(diǎn)的坐標(biāo),其6個鄰居節(jié)點(diǎn)的坐標(biāo)可通過固定的坐標(biāo)關(guān)系進(jìn)行計(jì)算[23],這可以提高HJPS算法的運(yùn)行效率。因此,選用直角坐標(biāo)系構(gòu)建正六邊形柵格地圖,并存儲地圖信息,選用三斜軸坐標(biāo)系實(shí)現(xiàn)HJPS算法。

2.2 HJPS算法的鄰居剪枝和強(qiáng)制鄰居判斷規(guī)則

設(shè)柵格地圖中的某一連續(xù)節(jié)點(diǎn)序列H={x0,x1,…,xk},H中的各個節(jié)點(diǎn)xi所在的柵格是順次逐個相鄰的。設(shè)柵格地圖中某一節(jié)點(diǎn)x的鄰居節(jié)點(diǎn)為ni(i=1, 2,…, 6),節(jié)點(diǎn)x的父節(jié)點(diǎn)為xp,xp指向節(jié)點(diǎn)x的方向?yàn)榧糁Ψ较?Hx表示節(jié)點(diǎn)x不在H中,len(H)表示H的節(jié)點(diǎn)個數(shù)。

在正方形柵格地圖中,東、西、南、北4個方向與所在正方形柵格的邊垂直,稱為垂直線方向,作為一組剪枝方向;其他4個方向?yàn)閷蔷€方向,作為另一組剪枝方向,兩組剪枝方向分別采用不同的剪枝規(guī)則[24]。正方形柵格地圖中垂直線方向和對角線方向是交替出現(xiàn)的,借鑒這一特點(diǎn),在正六邊形柵格地圖中,將東、西北、西南方向作為一組剪枝方向,該方向采用傳統(tǒng)JPS算法中垂直線方向的剪枝規(guī)則,將西、東北、東南作為另一組剪枝方向,該方向采用傳統(tǒng)JPS算法中對角線方向的剪枝規(guī)則。

(1) HJPS算法的鄰居剪枝規(guī)則

圖8是HJPS算法的鄰居剪枝示意圖。其中,箭頭為剪枝方向,灰色柵格為被剪枝的鄰居節(jié)點(diǎn)所對應(yīng)的柵格。

圖8 鄰居剪枝示意圖Fig.8 Schematic diagram of neighbor nodes pruning

當(dāng)節(jié)點(diǎn)x的某一鄰居節(jié)點(diǎn)ni所在柵格不是障礙物柵格時,若剪枝方向?yàn)闁|、西北或西南方向,且父節(jié)點(diǎn)xp經(jīng)過節(jié)點(diǎn)x到鄰居節(jié)點(diǎn)ni的最短連續(xù)節(jié)點(diǎn)序列H1以及父節(jié)點(diǎn)xp不經(jīng)過節(jié)點(diǎn)x到鄰居節(jié)點(diǎn)ni的最短連續(xù)節(jié)點(diǎn)序列H2x滿足:

len({xp,x,ni})≥len({xp,…,ni}x)

(2)

則剪枝鄰居節(jié)點(diǎn)為ni;若剪枝方向?yàn)槲鳌|北或東南方向,且滿足:

len({xp,x,ni})>len({xp,…,ni}x)

(3)

則剪枝鄰居節(jié)點(diǎn)為ni。經(jīng)過剪枝后剩余的鄰居節(jié)點(diǎn)稱為自然鄰居。

如圖8(a)所示,剪枝方向?yàn)闁|方向,且節(jié)點(diǎn)x的鄰居節(jié)點(diǎn)均不是障礙物柵格的鄰居剪枝情況,根據(jù)鄰居剪枝規(guī)則,鄰居節(jié)點(diǎn)n1、n2、n4、n5被剪枝,鄰居節(jié)點(diǎn)n3為自然鄰居;如圖8(b)所示,剪枝方向?yàn)闁|北方向的鄰居剪枝情況,根據(jù)鄰居剪枝規(guī)則,鄰居節(jié)點(diǎn)n4、n6被剪枝,鄰居節(jié)點(diǎn)n1、n2、n3為自然鄰居。

(2) HJPS算法的強(qiáng)制鄰居判斷規(guī)則

當(dāng)節(jié)點(diǎn)x的某一鄰居節(jié)點(diǎn)ni所在柵格是障礙物柵格時,剪枝結(jié)果就會發(fā)生變化。比如節(jié)點(diǎn)x的鄰居節(jié)點(diǎn)n1為障礙物柵格,如圖9所示,剪枝方向?yàn)闁|方向,與圖8(a)的剪枝方向相同。對于鄰居節(jié)點(diǎn)n2,由圖9可知,實(shí)線箭頭表示的連續(xù)節(jié)點(diǎn)序列為{xp,x,n2},虛線箭頭表示的連續(xù)節(jié)點(diǎn)序列為{xp,n5,n4,n3,n2}x,根據(jù)上述鄰居剪枝規(guī)則中的式(2),鄰居節(jié)點(diǎn)n2不再滿足被剪枝的條件,此時,鄰居節(jié)點(diǎn)n2就變成節(jié)點(diǎn)x的強(qiáng)制鄰居。

圖9 強(qiáng)制鄰居示意圖Fig.9 Schematic diagram of forced neighbor nodes

綜上,HJPS算法的強(qiáng)制鄰居判斷規(guī)則為:在鄰居剪枝的基礎(chǔ)上,節(jié)點(diǎn)x的某一鄰居節(jié)點(diǎn)ni所在柵格是障礙物柵格時,若其他非障礙物的某一鄰居節(jié)點(diǎn)nj,(j≠i),不是節(jié)點(diǎn)x的自然鄰居,且父節(jié)點(diǎn)xp經(jīng)過節(jié)點(diǎn)x到鄰居節(jié)點(diǎn)nj的最短連續(xù)節(jié)點(diǎn)序列H3以及父節(jié)點(diǎn)xp不經(jīng)過節(jié)點(diǎn)x到鄰居節(jié)點(diǎn)nj的最短連續(xù)節(jié)點(diǎn)序列H4x滿足:

len({xp,x,nj})

(4)

則該鄰居節(jié)點(diǎn)nj是節(jié)點(diǎn)x的強(qiáng)制鄰居。當(dāng)節(jié)點(diǎn)x存在強(qiáng)制鄰居時,節(jié)點(diǎn)x就被定義為跳點(diǎn)。

2.3 HJPS算法的跳點(diǎn)搜索策略

傳統(tǒng)JPS算法搜索跳點(diǎn)作為后繼節(jié)點(diǎn)加入到OPEN列表中。在正方形柵格地圖中,垂直線和對角線方向上均有強(qiáng)制鄰居和跳點(diǎn),因此,傳統(tǒng)JPS算法既要在垂直線和對角線方向上搜索伴有強(qiáng)制鄰居的跳點(diǎn),也要在對角線方向分支出的兩個方向上搜索伴有強(qiáng)制鄰居的跳點(diǎn)[25]。

根據(jù)HJPS算法修改后的鄰居剪枝和強(qiáng)制鄰居判斷的規(guī)則可知:在正六邊形柵格地圖中,東、西北和西南方向上會出現(xiàn)強(qiáng)制鄰居和跳點(diǎn),因此將其作為一組搜索方向,定義為方向Ⅰ,如圖10(a)實(shí)線箭頭所示;西、東北和東南方向上不出現(xiàn)強(qiáng)制鄰居和跳點(diǎn),因此將它們作為另一組搜索方向,定義為方向Ⅱ,如圖10(a)虛線箭頭所示。

搜索方向確定后,HJPS算法的跳點(diǎn)搜索策略為:① 目標(biāo)點(diǎn)作為目標(biāo)跳點(diǎn)被搜索;② 為避免重復(fù)遍歷柵格地圖中的節(jié)點(diǎn),在方向Ⅰ上搜索伴有強(qiáng)制鄰居的跳點(diǎn)或目標(biāo)跳點(diǎn),如圖10(b)實(shí)線箭頭所示;③ 也在方向Ⅱ上的節(jié)點(diǎn)分支出的兩個方向上搜索伴有強(qiáng)制鄰居的跳點(diǎn)或目標(biāo)跳點(diǎn),如圖10(b)虛線箭頭所示,若在方向Ⅱ上的某節(jié)點(diǎn)分支出的兩個方向上搜索到伴有強(qiáng)制鄰居的跳點(diǎn)或目標(biāo)跳點(diǎn),則定義該節(jié)點(diǎn)為中間跳點(diǎn)。

圖10 HJPS算法的跳點(diǎn)搜索策略Fig.10 Jump point search strategy of HJPS algorithm

由于因?yàn)镠JPS算法在方向Ⅱ進(jìn)行鄰居剪枝時不產(chǎn)生強(qiáng)制鄰居和跳點(diǎn),因此該算法在方向Ⅱ搜索時只需要在其分支出的兩個方向上搜索跳點(diǎn)即可,這簡化了跳點(diǎn)搜索策略,提高了HJPS算法的運(yùn)行效率。

2.4 HJPS算法流程

圖11為HJPS算法的JPS過程示意圖,圖中S和G分別為起點(diǎn)和目標(biāo)點(diǎn),虛線和實(shí)線分別為未搜索到跳點(diǎn)和搜索到跳點(diǎn)的過程,灰色虛線為跳點(diǎn)指向強(qiáng)制鄰居的方向Ⅱ的搜索過程。

圖11 HJPS算法的JPS過程示意圖Fig.11 Schematic diagram of JPS process of HJPS algorithm

利用HJPS算法搜索S至G的最優(yōu)路徑節(jié)點(diǎn)序列M的流程如下。

步驟 1輸入起點(diǎn)S和目標(biāo)點(diǎn)G的柵格節(jié)點(diǎn)坐標(biāo)。

步驟 2創(chuàng)建OPEN列表和CLOSE列表,分別存放跳點(diǎn)和構(gòu)成最終路徑的跳點(diǎn)。每個跳點(diǎn)的距離成本函數(shù)F(j)計(jì)算公式為

F(j)=G(j)+H(j)

(5)

式中:G(j)為起點(diǎn)到跳點(diǎn)j的實(shí)際距離,若起點(diǎn)至跳點(diǎn)j之間無其他跳點(diǎn),則G(j)為兩點(diǎn)之間的直線距離,若其存在其他跳點(diǎn),則G(j)為起點(diǎn)經(jīng)過其他跳點(diǎn)至跳點(diǎn)j的分段直線距離的累加;H(j)為跳點(diǎn)j到目標(biāo)點(diǎn)的啟發(fā)式距離[26],啟發(fā)式距離是指跳點(diǎn)j至目標(biāo)點(diǎn)的最優(yōu)路徑的估計(jì)距離,可由跳點(diǎn)j至目標(biāo)點(diǎn)的直線距離表示。

步驟 3將起點(diǎn)作為初始跳點(diǎn)加入CLOSE列表。

步驟 4取初始跳點(diǎn)指向非障礙物的鄰居節(jié)點(diǎn)的方向?yàn)楫?dāng)前搜索方向,根據(jù)當(dāng)前搜索方向利用跳點(diǎn)搜索策略搜索所有滿足條件的跳點(diǎn),搜索到跳點(diǎn)后結(jié)束當(dāng)前搜索方向的搜索過程。

步驟 5設(shè)初始跳點(diǎn)為搜索到的所有跳點(diǎn)的父節(jié)點(diǎn),并將搜索到的跳點(diǎn)加入OPEN列表。

步驟 6將OPEN列表中新加入的所有跳點(diǎn)中F(j)值最小的跳點(diǎn)設(shè)為當(dāng)前跳點(diǎn),并移到CLOSE列表中。

步驟 7判斷當(dāng)前跳點(diǎn)是否為目標(biāo)點(diǎn),若是,將CLOSE列表中的所有跳點(diǎn)作為最優(yōu)路徑節(jié)點(diǎn)序列M輸出,HJPS算法結(jié)束;若否,進(jìn)行下一步。

步驟 8取當(dāng)前跳點(diǎn)的父節(jié)點(diǎn)指向當(dāng)前跳點(diǎn)的方向?yàn)榧糁Ψ较?根據(jù)剪枝方向利用HJPS算法的鄰居剪枝規(guī)則剪枝當(dāng)前跳點(diǎn)的鄰居節(jié)點(diǎn)。

步驟 9取當(dāng)前跳點(diǎn)指向經(jīng)過剪枝后剩余的鄰居節(jié)點(diǎn)的方向?yàn)楫?dāng)前搜索方向,根據(jù)當(dāng)前搜索方向利用JPS策略搜索所有滿足條件的跳點(diǎn),搜索到跳點(diǎn)后結(jié)束當(dāng)前搜索方向的搜索過程。

步驟 10設(shè)當(dāng)前跳點(diǎn)為搜索到的所有跳點(diǎn)的父節(jié)點(diǎn),并將搜索到的跳點(diǎn)加入OPEN列表,回到步驟6。

如圖11所示,按照HJPS算法的流程,從初始跳點(diǎn)開始,利用第2.2節(jié)中的鄰居剪枝和強(qiáng)制鄰居判斷的規(guī)則,可以判斷節(jié)點(diǎn)N為強(qiáng)制鄰居,利用第2.3節(jié)中的跳點(diǎn)搜索策略,可以搜索到伴有強(qiáng)制鄰居N的跳點(diǎn)J1、中間跳點(diǎn)Jm1和Jm2、目標(biāo)跳點(diǎn)G,最終得到起點(diǎn)S至目標(biāo)點(diǎn)G的最優(yōu)路徑節(jié)點(diǎn)序列M={S,Jm1,J1,Jm2,G}。

3 基于HJPS算法的智能體路徑規(guī)劃

利用HJPS算法解決在存在障礙物的環(huán)境地圖上的智能體路徑規(guī)劃問題的流程如下。

步驟 1對環(huán)境地圖進(jìn)行正六邊形柵格化建模。

步驟 2確定智能體路徑規(guī)劃的起點(diǎn)S和目標(biāo)點(diǎn)G所在的柵格坐標(biāo)。

步驟 3利用HJPS算法搜索S至G的最優(yōu)路徑節(jié)點(diǎn)序列M。

步驟 4順次連接M中的節(jié)點(diǎn)得到S至G的規(guī)劃路徑P,輸出P作為所規(guī)劃的智能體路徑,路徑規(guī)劃結(jié)束。

由于正六邊形柵格地圖中6個搜索方向的限制,規(guī)劃路徑P可能存在階梯線或鋸齒線[27],如圖12所示,這樣的路徑存在轉(zhuǎn)折次數(shù)多、轉(zhuǎn)向角度大的問題。針對該問題,可利用弗洛伊德路徑平滑算法[28]對最優(yōu)路徑節(jié)點(diǎn)序列M進(jìn)一步優(yōu)化,得到優(yōu)化后的路徑節(jié)點(diǎn)序列Mo,該算法流程圖如圖13所示,順次連接優(yōu)化后的路徑節(jié)點(diǎn)序列Mo中的節(jié)點(diǎn),便得到智能體的最終規(guī)劃路徑Po。

圖12 存在階梯線的路徑示意圖Fig.12 Schematic diagram of path with step line

圖13 弗洛伊德路徑平滑算法流程圖Fig.13 Flow chart of Floyd path smoothing algorithm

4 仿真研究

利用Python語言和Pycharm平臺對基于HJPS算法的智能體路徑規(guī)劃進(jìn)行仿真研究。

仿真 1為驗(yàn)證HJPS算法的有效性以及對比傳統(tǒng)JPS算法和A*算法的優(yōu)越性,在如圖14所示的45 m×50 m尺寸的某矩形環(huán)境地圖進(jìn)行路徑規(guī)劃仿真,圖中白色部分為可行區(qū)域,黑色部分為障礙物。

圖14 某矩形環(huán)境地圖Fig.14 A rectangular environment map

設(shè)S和G分別為路徑規(guī)劃的起點(diǎn)和目標(biāo)點(diǎn),分別構(gòu)建28×32的相同規(guī)格的正六邊形柵格地圖和正方形柵格地圖,并在兩種柵格地圖上分別利用JPS算法和A*算法進(jìn)行路徑規(guī)劃,仿真結(jié)果如圖15和圖16所示。有關(guān)路徑節(jié)點(diǎn)數(shù)、比較節(jié)點(diǎn)數(shù)、路徑規(guī)劃時間、轉(zhuǎn)折次數(shù)、路徑長度和危險(xiǎn)路徑點(diǎn)數(shù)的仿真結(jié)果對比如表1所示,表中結(jié)果均為50次路徑規(guī)劃仿真結(jié)果的平均值,其中比較節(jié)點(diǎn)數(shù)指添加至OPEN列表進(jìn)行最小值選取的節(jié)點(diǎn)數(shù),危險(xiǎn)路徑點(diǎn)數(shù)指圖16中黑色圓圈所示的涉及穿越墻角行為的路徑點(diǎn)個數(shù)。

圖15 基于正六邊形柵格地圖的路徑規(guī)劃結(jié)果Fig.15 Path planning results based on hexagon grid map

圖16 基于正方邊形柵格地圖的路徑規(guī)劃結(jié)果Fig.16 Path planning results based on square grid map

表1 路徑規(guī)劃結(jié)果對比

由圖15(a)可知,HJPS算法能夠?qū)崿F(xiàn)路徑規(guī)劃。由表1可知,基于兩種柵格地圖的JPS算法所規(guī)劃路徑的節(jié)點(diǎn)數(shù)均少于基于兩種柵格地圖的A*算法所規(guī)劃路徑的節(jié)點(diǎn)數(shù);兩種JPS算法對比A*算法減少了約95%的比較節(jié)點(diǎn)數(shù);兩種JPS算法運(yùn)行效率高于A*算法,且HJPS算法對比傳統(tǒng)JPS算法減少了約44%的路徑規(guī)劃時間;基于正六邊形柵格地圖所規(guī)劃路徑的轉(zhuǎn)折次數(shù)比基于正方形柵格地圖所規(guī)劃路徑的轉(zhuǎn)折次數(shù)要少;在同種柵格地圖中基于A*算法和兩種JPS算法所規(guī)劃路徑的長度相等,基于正六邊形柵格地圖所規(guī)劃的路徑比基于正方形柵格地圖所規(guī)劃的路徑長約1%。對比圖15和圖16中基于兩種柵格地圖所規(guī)劃的路徑以及表1中的危險(xiǎn)路徑點(diǎn)數(shù),基于正六邊形柵格地圖所規(guī)劃的路徑避免了穿越墻角的不安全行為,離障礙物的距離更加安全合理,因此危險(xiǎn)路徑點(diǎn)數(shù)為0。

仿真 2為進(jìn)一步對比HJPS算法和傳統(tǒng)JPS算法的性能,對如圖17所示的50 m×50 m尺寸的障礙物分布較復(fù)雜的某正方形環(huán)境地圖進(jìn)行路徑規(guī)劃仿真。

圖17 某正方形環(huán)境地圖Fig.17 A square environmental map

設(shè)S和G分別為路徑規(guī)劃的起點(diǎn)和目標(biāo)點(diǎn),分別構(gòu)建60×60至100×100的不同規(guī)格的正六邊形柵格地圖和正方形柵格地圖,并利用HJPS算法和傳統(tǒng)JPS算法分別進(jìn)行路徑規(guī)劃仿真,該仿真過程使用弗洛伊德路徑平滑算法。

不同規(guī)格的柵格地圖下HJPS算法和傳統(tǒng)JPS算法在路徑規(guī)劃時間和危險(xiǎn)路徑點(diǎn)數(shù)兩個性能指標(biāo)下的對比如圖18所示。由圖18可知,HJPS算法對比傳統(tǒng)JPS算法在不同規(guī)格的柵格地圖下均減少了約40%的路徑規(guī)劃時間,且危險(xiǎn)路徑點(diǎn)數(shù)均為0。其中,60×60柵格地圖下的路徑規(guī)劃仿真結(jié)果如圖19所示,基于傳統(tǒng)JPS算法和弗洛伊德路徑平滑算法所規(guī)劃的路徑存在11個危險(xiǎn)路徑點(diǎn),而基于HJPS算法和弗洛伊德路徑平滑算法所規(guī)劃的路徑均與障礙物保持了一定的安全距離,無危險(xiǎn)路徑點(diǎn)。可見,HJPS算法對比傳統(tǒng)JPS算法,能夠規(guī)劃出更為安全合理的路徑,同時路徑規(guī)劃速度更快。

圖18 HJPS算法和傳統(tǒng)JPS算法性能對比Fig.18 Performance comparison of HJPS algorithm andtraditional JPS algorithm

圖19 60×60柵格地圖下路徑規(guī)劃結(jié)果Fig.19 Path planning results under 60×60 grid map

5 結(jié) 論

針對傳統(tǒng)JPS算法規(guī)劃出的路徑存在穿越墻角的不安全行為的問題,本文構(gòu)建正六邊形柵格地圖,修改傳統(tǒng)JPS算法的鄰居剪枝、強(qiáng)制鄰居判斷的規(guī)則和JPS策略,提出正六邊形柵格JPS算法,并利用該算法解決智能體在障礙物分布較為復(fù)雜的環(huán)境地圖中的路徑規(guī)劃問題。以智能體為對象進(jìn)行路徑規(guī)劃仿真比較,驗(yàn)證了所提算法的有效性和優(yōu)越性。正六邊形柵格JPS算法能夠利用JPS算法路徑規(guī)劃效率高以及正六邊形柵格地圖可避免穿越墻角的不安全行為的特點(diǎn),提高路徑規(guī)劃的質(zhì)量和效率。

本文所提出的正六邊形柵格JPS算法可推廣應(yīng)用于無人車、無人機(jī)、無人船等智能化無人裝備在復(fù)雜環(huán)境下的路徑規(guī)劃問題。