黃勁潮

(龍巖學(xué)院繼續(xù)教育學(xué)院，福建龍巖 364012)

0 引言

當(dāng)前社會(huì)，出現(xiàn)了很多自助游愛(ài)好者，他們需要在復(fù)雜的山地地形，尋找一條沒(méi)有前人走過(guò)的路徑來(lái)到達(dá)目的地。如何快速、準(zhǔn)確的規(guī)劃山地三維路徑，成為一個(gè)值得研究的新課題。所謂三維路徑規(guī)劃，是在三維地圖中規(guī)劃出一條避開(kāi)了無(wú)法通過(guò)的障礙，同時(shí)滿足某些指標(biāo)最優(yōu)的三維路徑。目前常用的路徑規(guī)劃算法，大多數(shù)只能規(guī)劃二維平面路徑;而一般的三維規(guī)劃算法，大多運(yùn)算算法復(fù)雜、需要很大的存儲(chǔ)空間，同時(shí)無(wú)法在宏觀全局角度來(lái)進(jìn)行路徑規(guī)劃。目前常用的三維規(guī)劃算法有粒子群算法、遺傳算法、A*算法等，但粒子群算法與遺傳算法只是準(zhǔn)三維算法，而A*算法當(dāng)維數(shù)增加時(shí)計(jì)算量會(huì)急劇增加［1－3］。本文在已有三維山地地圖的基礎(chǔ)上，采用一種改進(jìn)的蟻群算法來(lái)解決上述問(wèn)題。

1 改進(jìn)的蟻群算法

Dorigo M等人在90年代初提出了蟻群算法，它是基于仿生螞蟻搜索行為的一種進(jìn)化算法。觀察者發(fā)現(xiàn)，螞蟻在搜索找尋食物時(shí)，會(huì)在爬過(guò)的路上留下分泌物，這種分泌物包含了螞蟻的信息素。這種信息素會(huì)慢慢揮發(fā)，但是后續(xù)的螞蟻能夠檢測(cè)到這種信息素的存在;并且后續(xù)螞蟻會(huì)優(yōu)先選擇信息素濃度較高的路徑點(diǎn)，同時(shí)它們?cè)谶M(jìn)過(guò)的時(shí)候還會(huì)再次留下信息素。這樣該路徑點(diǎn)的信息素濃度會(huì)不斷增大，同時(shí)也會(huì)更加吸引后續(xù)的螞蟻［4－5］。蟻群算法根據(jù)螞蟻的覓食行為設(shè)計(jì)，它具有群體智能并有分布式計(jì)算的優(yōu)點(diǎn)，因此它在路徑選擇上具有很大的潛力。

1.1 三維空間抽象建模

三維路徑規(guī)劃算法首先需要從三維地圖中抽象出三維空間模型，模型抽象方法如下:首先三維地圖左下角的頂點(diǎn)作為三維空間的坐標(biāo)原點(diǎn)A，在點(diǎn)A中建立三維坐標(biāo)系，其中，x軸為沿經(jīng)度增加的方向，y軸為沿緯度增加的方向，z軸為垂直于海平面方向。在該坐標(biāo)系中以點(diǎn)A為頂點(diǎn)，沿x軸方向取三維地圖的最大長(zhǎng)度AB，沿y軸方向取三維地圖的最大長(zhǎng)度AA’，沿z軸方向取三維地圖的最大長(zhǎng)度AB，這樣就構(gòu)造了包含三維地圖的立方體區(qū)域ABCD–A’B’C’D’，該區(qū)域即為三維路徑的規(guī)劃空間。三維路徑規(guī)劃空間如圖1所示。

三維路徑空間建立起來(lái)之后，采用等分空間的方法從三維空間中抽取出三維路徑規(guī)劃所的網(wǎng)格點(diǎn)。首先沿邊AB把規(guī)劃空間ABCD–A’B’C’D’進(jìn)行等分，得到n+l個(gè)平面∏i(i=1，2，…，n)，然后對(duì)這n+l個(gè)平面沿邊AD進(jìn)行m等分，沿邊AA’進(jìn)行l(wèi)等分，并且并且求解出里面的交點(diǎn)。

通過(guò)以上步驟，整個(gè)規(guī)劃空間ABCD–A’B’C’D’就離散化為一個(gè)三維點(diǎn)集合，集合中的任意一點(diǎn)對(duì)應(yīng)著兩個(gè)坐標(biāo)，即序號(hào)坐標(biāo)a1(i，j，k)(i=0，1，2，…，n，j=0，l，2，…，m，k=0，1，2，…，l)和位置坐標(biāo)a2(xi，yi，zi)，其中，i，j，k分別為當(dāng)前點(diǎn)a沿邊AA、邊AD、邊AA’的劃分序號(hào)。蟻群算法即在這些三維路徑點(diǎn)上進(jìn)行規(guī)劃，最終得到連接出發(fā)點(diǎn)和目標(biāo)點(diǎn)滿足某項(xiàng)指標(biāo)最優(yōu)的三維路徑。

圖1 三維路徑規(guī)劃空間

1.2 信息素更新

蟻群算法使用信息素吸引螞蟻搜索，信息素位置設(shè)定及更新方法對(duì)于蟻群算法的成功搜具有非常重要的意義。在1.1節(jié)中已經(jīng)把整個(gè)搜索空間離散為一系列的三維離散點(diǎn)，這離散點(diǎn)為蟻群算法需要搜索的節(jié)點(diǎn)。因此，把信息素存儲(chǔ)在模型的離散點(diǎn)中，每個(gè)離散點(diǎn)都有一個(gè)信息素的濃度值，該濃度值表征了對(duì)后續(xù)螞蟻的吸引力，值越大，吸引力也越大，該值在螞蟻經(jīng)過(guò)改點(diǎn)后更新。

信息素在更新時(shí)可以采用全局更新或者局部更新兩種方式。螞蟻經(jīng)過(guò)一個(gè)路徑點(diǎn)時(shí)，信息素濃度降低，這就是局部更新。信息素濃度的降低是為了讓螞蟻們可以去探索未經(jīng)探索過(guò)得路徑點(diǎn)，在宏觀全局角度來(lái)更好地規(guī)劃線路。局部信息素更新隨著螞蟻的搜索進(jìn)行，信息素更新公式為

其中，τijk是點(diǎn)(i，j，k)上所帶的信息素濃度值;ζ是衰減系數(shù)。

螞蟻搜索完一條完整的路徑，以該路徑的長(zhǎng)度作為評(píng)價(jià)值，從路徑集合中選擇出最短路徑，增加最短路徑各節(jié)點(diǎn)的信息素值，這就叫全局更新。信息素更新公式如下:

其中，length(m)為第m只螞蟻經(jīng)過(guò)的路徑長(zhǎng)度;ρ為信息素更新系數(shù);K是系數(shù)。

1.3 可視搜索空間

取z軸方向作為三維路徑規(guī)劃的主方向，探險(xiǎn)者沿x軸方向前進(jìn)，為了降低規(guī)劃復(fù)雜程度，將探險(xiǎn)者的運(yùn)動(dòng)簡(jiǎn)化為前向運(yùn)動(dòng)、橫向運(yùn)動(dòng)和縱向運(yùn)動(dòng)三種運(yùn)動(dòng)方式。在前向運(yùn)動(dòng)一定單位長(zhǎng)度距離Lx，max情況下，設(shè)定機(jī)器人最大橫向移動(dòng)允許距離為L(zhǎng)y，max，最大縱向移動(dòng)距離為L(zhǎng)z，max。這樣，當(dāng)螞蟻沿著x軸方向前進(jìn)時(shí)，當(dāng)位于點(diǎn)H(i，j，k)時(shí)，對(duì)下一個(gè)點(diǎn)的搜索就存在一個(gè)可視區(qū)域，可視區(qū)域如圖2所示。

這樣，當(dāng)螞蟻由當(dāng)前點(diǎn)向下一個(gè)點(diǎn)移動(dòng)時(shí)，可搜索的區(qū)域限制在螞蟻搜索可視區(qū)域之內(nèi)，簡(jiǎn)化了搜索空間，提了蟻群算法的搜索效率。

1.4 蟻群搜索策略

螞蟻從當(dāng)前點(diǎn)移動(dòng)到下一個(gè)點(diǎn)時(shí)，根據(jù)啟發(fā)函數(shù)來(lái)計(jì)算可視區(qū)域內(nèi)各點(diǎn)的選擇概率，啟發(fā)數(shù)為

圖2 螞蟻搜索可視區(qū)域

其中，D(i，j，k)為兩點(diǎn)間路徑長(zhǎng)度，促使螞蟻選擇距離較近的點(diǎn);S(i，j，k)為安全性因素，選擇點(diǎn)不可達(dá)到時(shí)，該值為0，促使螞蟻選擇安全點(diǎn);Q(i，j，k)為下一點(diǎn)到目標(biāo)點(diǎn)的路徑長(zhǎng)度，促使螞蟻選擇距離目標(biāo)更近的點(diǎn);wl，w2，w3為系數(shù)，代表上述各因素的重要程度。

D(i，j，k)的計(jì)算公式如下:

其中，a為當(dāng)前點(diǎn);b為下一個(gè)點(diǎn)。

S(i，j，k)的計(jì)算公式如下:

其中，Num表示在點(diǎn)(i，j，k)中可視點(diǎn)的數(shù)量;UNum表示可視點(diǎn)中不可達(dá)區(qū)域的點(diǎn)的數(shù)量。

Q(i，j，k)的計(jì)算公式如下:

其中，b表示下一點(diǎn);d表示目標(biāo)點(diǎn)。

螞蟻在平面∏i上的當(dāng)前點(diǎn)pi選擇平面∏i+1上下一個(gè)點(diǎn)pi+1的步驟如下:

1)根據(jù)抽象環(huán)境確定平面∏i+1內(nèi)的可行點(diǎn)集合;

2)根據(jù)啟發(fā)函數(shù)公式(4)依次計(jì)算點(diǎn)pi到平面∏i+1內(nèi)的可行點(diǎn)集合的啟發(fā)信息值Ha+1，u，v;

3)計(jì)算在平面∏i+1內(nèi)任一點(diǎn)(i+1，u，v)的選擇概率p(i+1，u，v):

其中τa+1，u，v為平面∏i+1點(diǎn)P(a+1，u，v)的信息素值。

4)根據(jù)各點(diǎn)的選擇概率采用輪盤(pán)賭法選擇平面∏i+1內(nèi)的點(diǎn)。

1.5 算法流程

基于蟻群算法的三維路徑搜索算法的算法流程如圖3所示。

圖3 三維路徑規(guī)劃算法

其中，三維環(huán)境建模模塊根據(jù)1.1節(jié)抽取出三維環(huán)境數(shù)學(xué)模型;搜索節(jié)點(diǎn)模塊根據(jù)啟發(fā)函數(shù)搜索下個(gè)節(jié)點(diǎn);信息素更新模塊更新環(huán)境中節(jié)點(diǎn)的信息素值。

1.6 本設(shè)計(jì)對(duì)基本蟻群算法的改進(jìn)

采用局部信息素與全局信息素相結(jié)合的更新策略，縮短了基本蟻群算法的計(jì)算時(shí)間，也避免了易陷于停滯的缺陷;基本蟻群算法信息素釋放在節(jié)點(diǎn)邊上，本設(shè)計(jì)把信息素釋放在節(jié)點(diǎn)上，大大降低了運(yùn)算量的同時(shí)也節(jié)約了存儲(chǔ)空間。

2 山地三維路徑規(guī)劃設(shè)計(jì)

2.1 問(wèn)題描述

采用蟻群算法在跨度為24 km×24 km的一片山地中搜索從起點(diǎn)到終點(diǎn)，并且避開(kāi)所有障礙物的路徑，為了方便問(wèn)題的求解，取該區(qū)域內(nèi)最低點(diǎn)的高度為0，其他點(diǎn)高度根據(jù)和最低點(diǎn)高度差依次取得。路徑規(guī)劃起點(diǎn)坐標(biāo)為(1，10，800)，終點(diǎn)坐標(biāo)為(21，4，1 000)，規(guī)劃環(huán)境和起點(diǎn)、終點(diǎn)如圖4所示。整個(gè)搜索空間為24 km×24 km的山地，其中，起點(diǎn)坐標(biāo)為(1，10，800)，終點(diǎn)坐標(biāo)為(21，4，1 000)。

圖4 規(guī)劃環(huán)境、起點(diǎn)、終點(diǎn)圖

2.2 主要函數(shù)MATLAB編程實(shí)現(xiàn)

1)啟發(fā)值計(jì)算函數(shù)

2)適應(yīng)度計(jì)算函數(shù)

2.3 仿真結(jié)果

蟻群算法進(jìn)行三維路徑規(guī)劃，規(guī)劃空間范圍為20 km×20 km的山地，把規(guī)劃空間抽象為24 km× 24 km×2 km的規(guī)劃空間，其中，x軸、y軸方向每個(gè)節(jié)點(diǎn)的間距為1 km，z軸方向每個(gè)節(jié)點(diǎn)間距為200 m。路徑起點(diǎn)在規(guī)劃空間的序號(hào)為［1 10 4］，終點(diǎn)在規(guī)劃空間的序號(hào)為［21 4 5］。算法的基本設(shè)置為種群規(guī)模為20，算法迭代為400次，路徑規(guī)劃結(jié)果如圖5所示。

圖5 規(guī)劃結(jié)果

對(duì)比圖4和圖5，我們可以看出，本算法從出發(fā)點(diǎn)到目標(biāo)點(diǎn)規(guī)劃出了一條能夠避開(kāi)難以攀爬和翻越的障礙、同時(shí)長(zhǎng)度較短的三維路徑。仿真結(jié)果證明了該算法是有效可行的。

3 結(jié)論

通過(guò)對(duì)山地空間的三維空間抽象建模，本設(shè)計(jì)得到了一個(gè)給定山地的三維空間模型。并基于改進(jìn)的蟻群算法，在三維空間模型中規(guī)劃了一條三維最優(yōu)路徑。使用MATLAB軟件進(jìn)行仿真，結(jié)果顯示基于改進(jìn)蟻群算法的山地三維路徑規(guī)劃算法在路徑最優(yōu)值計(jì)算和規(guī)劃時(shí)間上都能夠較好的滿足需求。

［1］Emilio Frazzoli.Real－time motion planning for agile autonomous vehicles［J］.Journal of Guidance，Control and Dynamics，2002，21(1):25.

［2］史峰，王輝，胡斐，等.MATLAB智能算法30個(gè)案例分析［M］.北京:北京航空航天大學(xué)出版社，2011.

［3］李愛(ài)萍，李元宗.移動(dòng)機(jī)器人路徑規(guī)劃方法的研究［J］.機(jī)械工程與自動(dòng)化，2009(5):194－196.

［4］朱慶保.動(dòng)態(tài)復(fù)雜環(huán)境下的機(jī)器人路徑規(guī)劃螞蟻預(yù)測(cè)算法［J］.計(jì)算機(jī)學(xué)報(bào)，2005，28(11):1 898－1 906.

［5］郭必祥.基于蟻群算法的智能機(jī)器人全局路徑規(guī)劃方法研究［D］.哈爾濱:哈爾濱工程大學(xué)，2005.