基于改進(jìn)A*算法的人工智能魚路徑規(guī)劃研究

袁紅春，毛 瑞，楊蒙召

(上海海洋大學(xué)信息學(xué)院， 上海 201306)

人工智能技術(shù)作為一個(gè)熱門領(lǐng)域，在醫(yī)療和農(nóng)業(yè)等各個(gè)領(lǐng)域都有著重大影響[1-3]。人工智能中每個(gè)實(shí)體都具有一定的高級(jí)自主行為，如何將物體智能化是該領(lǐng)域的重要研究方向之一。路徑規(guī)劃是構(gòu)建人工智能魚不可或缺的環(huán)節(jié)，是將人工魚智能化最有力的保證[4-5]。因此，有效的路徑優(yōu)化算法在構(gòu)建人工智能魚的過程中具有重要的實(shí)際意義。

隨著人工智能領(lǐng)域的興起，如何自主高效地進(jìn)行路徑尋優(yōu)成為一個(gè)重要問題。近年來，各種智能算法的應(yīng)用都獲得了比較理想的結(jié)果。宋建輝等[6]利用人工勢(shì)場(chǎng)法實(shí)現(xiàn)移動(dòng)機(jī)器人的路徑規(guī)劃；張航等[7]提出一種基于量子行為粒子群優(yōu)化算法(QPSO)的飛行器三維路徑規(guī)劃；Luitpold 等[8]提出了一種具有時(shí)間約束的協(xié)調(diào)目標(biāo)分配和無人機(jī)路徑規(guī)劃的算法；朱大奇等[9]針對(duì)水下機(jī)器人(AUV)的路徑規(guī)劃問題給出了一種基于生物啟發(fā)模型的三維路徑規(guī)劃和安全避障算法。A*(A-Star)算法由Hart PE等提出[10]，其利用啟發(fā)函數(shù)進(jìn)行路徑搜索的方法獲得了廣泛的應(yīng)用[11-13]。

本研究針對(duì)魚類檢索路徑時(shí)的回退現(xiàn)象，將傳統(tǒng)A*算法中的OPEN列表進(jìn)行改進(jìn)，減少了遍歷OPEN列表時(shí)的代價(jià)；同時(shí)，為獲取更優(yōu)的路徑，利用碰撞檢測(cè)算法優(yōu)化生成路徑。

1 A*算法概述

A*算法屬于啟發(fā)式搜索算法，搜索路徑由評(píng)價(jià)函數(shù)的返回值作為搜索的成本執(zhí)行。其估價(jià)函數(shù)的公式[14]為：

F(ni)=G(ni)+H(ni)

(1)

式中：F(ni)表示當(dāng)前節(jié)點(diǎn)的估價(jià)函數(shù)，即從初始節(jié)點(diǎn)Start開始，達(dá)到當(dāng)前節(jié)點(diǎn)后再由當(dāng)前節(jié)點(diǎn)前往終止節(jié)點(diǎn)Goal這一段路徑的預(yù)估；G(ni)表示已花費(fèi)的代價(jià)，其代表從初始節(jié)點(diǎn)Start到達(dá)當(dāng)前節(jié)點(diǎn)這一段路徑所消耗的代價(jià)；H(ni)為預(yù)估的代價(jià)，用于估算從當(dāng)前節(jié)點(diǎn)到達(dá)終止節(jié)點(diǎn)Goal這一段路徑可能消耗的代價(jià)。

A*算法的效率與準(zhǔn)確度是由函數(shù)H(ni)決定的。H(ni)對(duì)路徑的預(yù)估主要來源于其距離與單位距離內(nèi)所花費(fèi)的代價(jià)δ的乘積。根據(jù)距離公式得到H(ni)的預(yù)估方式[15]有以下3種：

1)曼哈頓距離預(yù)估

曼哈頓距離是坐標(biāo)系中兩點(diǎn)之間坐標(biāo)系的投影值的總和，其預(yù)估公式為：

hM(n)=δ(|xGoal-xn|+|yGoal-yn|+|ZGoal-zn|)

(2)

2)切比雪夫距離預(yù)估

切比雪夫距離又稱為棋盤距離，其預(yù)估公式為：

hc(n)=δmax(|xGoal-xn|,|yGoal-yn|,|zGoal-zn、)

(3)

3)歐幾里得距離預(yù)估

歐幾里得距離指在坐標(biāo)系的兩點(diǎn)直線距離，其預(yù)估公式為：

(4)

式中：xn、yn、zn為所求點(diǎn)的三維坐標(biāo)；xGoal、yGoal、zGoal為目標(biāo)點(diǎn)的三維坐標(biāo)；δ為單位距離所花費(fèi)的代價(jià)。

如圖1所示，將起始節(jié)點(diǎn)Start放入OPEN列表中，尋找OPEN列表中F值最小的節(jié)點(diǎn)i作為當(dāng)前節(jié)點(diǎn)并判斷是否為終止節(jié)點(diǎn)Goal。若不是，則將i移入CLOSE列表并計(jì)算節(jié)點(diǎn)i的鄰域Ni中各節(jié)點(diǎn)ni的Flatest值。判斷ni是否屬于OPEN列表或CLOSE列表：如果ni在OPEN列表中比較Flatest和原F的值，取最小者作為新的F值并重新設(shè)置父節(jié)點(diǎn)；如果ni屬于CLOSE列表則舍棄該節(jié)點(diǎn)并選擇Ni內(nèi)其他節(jié)點(diǎn)進(jìn)行判斷；如果ni不屬于OPEN列表且不屬于CLOSE列表，將Flatest設(shè)置為F值，并設(shè)置i為其父節(jié)點(diǎn)，將ni移至OPEN列表中。按此循環(huán)不斷查找OPEN列表，直到找到終止節(jié)點(diǎn)Goal，使用回溯法生成最優(yōu)路徑。

圖1 傳統(tǒng)A*算法流程圖

A*算法中，在每次對(duì)OPEN列表的節(jié)點(diǎn)選取時(shí)，要重新比較所有表內(nèi)F值的大小，增大了算法的計(jì)算量。由于OPEN列表節(jié)點(diǎn)選取的不確定性，可能導(dǎo)致在搜索路徑時(shí)的迂回現(xiàn)象。同時(shí)，每次A*算法進(jìn)行搜索路徑時(shí)，均為選擇相鄰節(jié)點(diǎn)的局部路徑，可能使尋找出的路徑并非是其最優(yōu)路徑。

2 改進(jìn)的A*算法

傳統(tǒng)A*算法在OPEN列表處理上不斷將當(dāng)前節(jié)點(diǎn)的相鄰節(jié)點(diǎn)存放至OPEN列表中，這會(huì)造成搜索路徑的迂回。針對(duì)魚類運(yùn)動(dòng)路徑的仿真，將OPEN列表的處理方法進(jìn)行改進(jìn)。每次在選取一個(gè)節(jié)點(diǎn)后，將OPEN列表進(jìn)行清空操作。在尋找當(dāng)前節(jié)點(diǎn)i的相鄰節(jié)點(diǎn)時(shí)，將相鄰節(jié)點(diǎn)標(biāo)記為OLD。如果相鄰節(jié)點(diǎn)為OLD，則略過該點(diǎn)。這樣使得每次在OPEN列表進(jìn)行選擇時(shí)，選擇的節(jié)點(diǎn)為當(dāng)前節(jié)點(diǎn)的下一節(jié)點(diǎn)，防止路徑的回退現(xiàn)象。并且，該做法可限制載入OPEN列表的節(jié)點(diǎn)數(shù)量，列表內(nèi)的節(jié)點(diǎn)F值逐級(jí)遞減，減少了算法的計(jì)算量，提高算法的執(zhí)行效率。同時(shí)使得CLOSE列表的載入節(jié)點(diǎn)在虛擬海洋環(huán)境中始終是相關(guān)節(jié)點(diǎn)，從而確保了魚類運(yùn)動(dòng)行徑的平滑性。

在傳統(tǒng)的A*算法中，由于鄰域閾值的影響，在選取鄰域節(jié)點(diǎn)過程中有約束，始終無法選取出最優(yōu)路徑。為了減少閾值約束的影響，在搜索路徑結(jié)束后使用碰撞檢測(cè)算法對(duì)路徑的節(jié)點(diǎn)進(jìn)行篩選，以達(dá)到優(yōu)化路徑的目的。

碰撞檢測(cè)是在人工智能領(lǐng)域中使用的一項(xiàng)重要技術(shù)，具有快速、準(zhǔn)確等特性。目前的碰撞檢測(cè)主要為基于包圍盒的碰撞技術(shù)。在這里，采用基于AABB碰撞檢測(cè)技術(shù)進(jìn)行路徑的處理[16-17]。該技術(shù)將物體放入三維坐標(biāo)中，依據(jù)其最大值和最小值進(jìn)行計(jì)算。物體的包圍盒可表示為：

R={(X,Y,Z)|Sx≤x≤1x,Sy≤y≤1y,Sz≤z≤lz}

(5)

式中:Sx,1x、Sy、1y、Sz、lz分別表示為包圍盒在不同坐標(biāo)軸上最小值、最大值的映射。

AABB碰撞檢測(cè)算法如圖2所示。

圖2 AABB碰撞檢測(cè)算法

該算法的中心思想為檢測(cè)2個(gè)包圍盒在不同的坐標(biāo)軸上的映射是否相交。記物體A的包圍盒最小頂點(diǎn)元素和最大頂點(diǎn)元素分別為(Axmin,Aymin,Azmin)和(Axmax,Aymax,Azmax)；物體B的包圍盒最小頂點(diǎn)元素和最大頂點(diǎn)元素分別為(Bxmin,Bymin,Bzmin)和(Axmax,Aymax,Azmax)。圖2為使用AABB碰撞檢測(cè)算法檢測(cè)AB兩物體是否碰撞流程圖。由圖2可知，AABB碰撞檢測(cè)算法分別對(duì)x軸、y軸、z軸進(jìn)行碰撞檢測(cè)，最多只需6次對(duì)比即可判斷AB兩物體是否碰撞。

如圖3所示，在OPEN列表尋找到具有最小F值得節(jié)點(diǎn)i后實(shí)行清空OPEN列表操作。同時(shí)在尋找當(dāng)前節(jié)點(diǎn)i的相鄰節(jié)點(diǎn)時(shí)，將相鄰節(jié)點(diǎn)標(biāo)記為OLD，防止路徑的回退現(xiàn)象。同時(shí)，針對(duì)傳統(tǒng)A*算法生成的路徑，使用碰撞檢測(cè)技術(shù)進(jìn)行優(yōu)化。

圖3 改進(jìn)的A*算法流程圖

將生成的路徑節(jié)點(diǎn)進(jìn)行1～n的編號(hào)，從1和n兩個(gè)節(jié)點(diǎn)出發(fā)，遍歷所有的節(jié)點(diǎn)間構(gòu)建的路徑。對(duì)生成的路徑進(jìn)行碰撞檢測(cè)。如果與障礙物等發(fā)生碰撞，則不做處理，否則刪除未發(fā)生碰撞的路徑中節(jié)點(diǎn)，建立新路徑，從而達(dá)到路徑優(yōu)化的目的。

3 試驗(yàn)結(jié)果

3.1 試驗(yàn)平臺(tái)

試驗(yàn)硬件環(huán)境的CPU為AMD Ryzen Threadripper 1950X 16-Core Processor 3.40 GHz，具有32.0 GB RAM，GPU為NVIDIA GeForce 1080Ti?；赪indows 10操作系統(tǒng)，仿真軟件為Matlab 2017a、3ds Max 2017和Unity3D。

3.2 魚類仿真建模

在3ds Max中進(jìn)行魚類的仿真建模[18-19]，采用彈簧—阻尼模型[20]進(jìn)行魚類構(gòu)建。首先使用3ds Max建立魚體的幾何網(wǎng)格模型，采用建模函數(shù)對(duì)曲面上的頂點(diǎn)序列進(jìn)行定義的方法來精確描述控制網(wǎng)點(diǎn)因子；其次采用曲面控制網(wǎng)點(diǎn)位置坐標(biāo)的方式進(jìn)行實(shí)時(shí)繪制，以形成離散的網(wǎng)格模型，并可用其“包裝”生物力學(xué)模型。構(gòu)建后發(fā)布并導(dǎo)入U(xiǎn)nity3D中。

圖4為3ds Max生成初步魚體網(wǎng)格模型圖。首先將需要建模魚的圖片導(dǎo)入至3ds Max中，使用曲面建模方法進(jìn)行構(gòu)建，從而在Front視圖中建立模型。對(duì)圖片進(jìn)行描點(diǎn)并轉(zhuǎn)化成可編輯的多邊形，通過相應(yīng)的拖點(diǎn)來制作魚的外形。然后繼續(xù)進(jìn)行橫向拖點(diǎn)操作，以便產(chǎn)生新的頂點(diǎn)和表面，通過拉伸表面可以生成胸鰭、腹鰭等更多細(xì)節(jié)的魚體形狀。魚眼的制作通過對(duì)魚頭的裂頂點(diǎn)、對(duì)齊及擠壓形成，從而生成如圖5(a)所示的人工魚幾何網(wǎng)格模型。最后，在Left和Top視圖中切換制作立體部分的結(jié)構(gòu)并在達(dá)到基本的構(gòu)線結(jié)構(gòu)之后，使用“渦輪平滑”修改器進(jìn)行模型的平滑處理，初步完成如圖5(b)所示的幾何魚體模型。

圖4 3ds Max生成初步魚體網(wǎng)格模型流程

圖5 人工智能魚仿真模型

3.3 改進(jìn)A*算法仿真試驗(yàn)

在Matlab R2017a中進(jìn)行仿真試驗(yàn)。如圖6所示，在Matlab中繪制一幅三維模擬海底圖。該海底圖中，x、y軸構(gòu)成面積大小為21 km×21 km的海底，x、y、z軸的單位均為千米(km)，是由一個(gè)隨機(jī)數(shù)組組成，代表深海中高度不同的丘陵。

如圖7所示，設(shè)置人工魚在三維海底的起始點(diǎn)為(15，0，1)，終點(diǎn)為(10，21，1)。將人工魚用質(zhì)點(diǎn)來表示，將由改進(jìn)A*算法得到的路徑節(jié)點(diǎn)用空心圓點(diǎn)代替，得到改進(jìn)的A*算法所尋的路徑圖。

圖6 三維海底圖

在模擬的三維海底中，設(shè)置人工魚的不同起始節(jié)點(diǎn)和終止節(jié)點(diǎn)，進(jìn)行多組試驗(yàn)。改進(jìn)A*算法與傳統(tǒng)A*算法的結(jié)果對(duì)比見表1。

圖7 試驗(yàn)結(jié)果

表1 試驗(yàn)結(jié)果

由表1可知，由于對(duì)OPEN列表節(jié)點(diǎn)選取的改進(jìn)，改進(jìn)后的A*算法運(yùn)行消耗時(shí)間比傳統(tǒng)的A*算法要小，但因?yàn)檫M(jìn)行碰撞檢測(cè)需要消耗時(shí)間，所以在運(yùn)算時(shí)間上并沒有太大的提升。在最終生成的路徑上，平均優(yōu)化的距離約占原距離的5%，使得人工魚的路徑更加高效。

將改進(jìn)的A*算法應(yīng)用在人工魚的建模當(dāng)中，借助Unity3D技術(shù)，將海洋魚類與改進(jìn)的A*算法相結(jié)合。首先需要仿真模擬出海底環(huán)境的基本場(chǎng)景，模擬出來的仿真場(chǎng)景俯視圖如圖8所示。地圖的大小為500×500,分為海藻密集區(qū)域和深海丘陵區(qū)域。采用Unity3D自帶的Terrian系統(tǒng)搭建丘陵地貌，海底的植物均由3ds Max進(jìn)行高密度的靜態(tài)建模，并且使用貼圖實(shí)現(xiàn)丘陵的各種顏色。為了模擬海底自然光線和實(shí)時(shí)計(jì)算出光照產(chǎn)生的陰影，采用靜態(tài)的天空盒與一個(gè)平行的光源進(jìn)行光源設(shè)置。最后，通過Shader材質(zhì)實(shí)現(xiàn)水下波紋的逼真效果。

圖8 場(chǎng)景俯視圖

智能魚的模型導(dǎo)入后，將改進(jìn)的A*算法尋路模塊通過A-star腳本和FishNewMove腳本掛載至智能魚的模型上，并以第三人稱視角展現(xiàn)虛擬海洋環(huán)境圖。如圖9所示，智能魚從t1時(shí)刻開始，在遇到海草等障礙物時(shí)，可以沿著改進(jìn)A*算法規(guī)劃好的路徑游走，從而達(dá)到t4時(shí)刻避障的效果。

圖9 魚類避障圖

4 討論

4.1 改進(jìn)A*算法所帶來的影響及其優(yōu)化

傳統(tǒng)的A*算法由于在OPEN列表的處理上，不斷將當(dāng)前節(jié)點(diǎn)的相鄰節(jié)點(diǎn)存放至OPEN列表中，造成搜索路徑的迂回。本研究在每次選取一個(gè)節(jié)點(diǎn)后，將OPEN列表進(jìn)行清空操作。該做法減少了算法的計(jì)算量，提高算法的執(zhí)行效率。同時(shí)，傳統(tǒng)A*算法由于鄰域閾值大小選取的影響，在選取鄰域節(jié)點(diǎn)過程中具有約束，始終無法選取出最優(yōu)路徑。本研究在A*算法的基礎(chǔ)上使用碰撞檢測(cè)的原理進(jìn)行路徑節(jié)點(diǎn)的篩選，有效解決了閾值約束的影響，確保了魚類運(yùn)動(dòng)行徑的平滑性。試驗(yàn)結(jié)果表明，在運(yùn)算時(shí)間相當(dāng)?shù)那闆r下，所尋的路徑減少了5%，使得改進(jìn)后的A*算法相較于傳統(tǒng)模型具有全面的提升。

4.2 人工魚的智能化研究對(duì)比

在傳統(tǒng)的對(duì)人工魚智能研究上，大多數(shù)學(xué)者都選擇對(duì)人工魚自身或者魚群進(jìn)行智能化。人工魚自身方面，孟憲宇等[21-22]采用模糊神經(jīng)網(wǎng)絡(luò)和模糊推理機(jī)制分別實(shí)現(xiàn)人工魚的味覺系統(tǒng)和嗅覺感知；尹璐[23]通過使用BP神經(jīng)網(wǎng)絡(luò)、自組織競(jìng)爭(zhēng)型神經(jīng)網(wǎng)絡(luò)和SOM神經(jīng)網(wǎng)絡(luò)對(duì)人工魚的感知、行為和意圖行為進(jìn)行優(yōu)化。袁紅春等[24-25]通過對(duì)行為決策方面的研究實(shí)現(xiàn)了人工魚群行為的改進(jìn)。相較于傳統(tǒng)的魚類智能研究，本研究重點(diǎn)在于真實(shí)環(huán)境的交互上，有效解決了魚類游泳過程中，魚類游泳路徑的隨機(jī)性。但是本文對(duì)魚群游泳時(shí)的行為缺乏研究，下一步將繼續(xù)研究魚群游泳時(shí)的運(yùn)動(dòng)規(guī)律，進(jìn)一步完善魚類行為的智能化。

5 結(jié)論

針對(duì)三維虛擬海洋環(huán)境中人工智能魚運(yùn)動(dòng)路徑仿真低效的問題，提出一種改進(jìn)的A*算法來進(jìn)行人工魚路徑尋優(yōu)。該算法在尋找路徑過程中對(duì)OPEN列表進(jìn)行節(jié)點(diǎn)清空操作，并利用碰撞檢測(cè)處理A*算法所得到的路徑。試驗(yàn)證明，改進(jìn)后的算法解決了A*算法的回退現(xiàn)象，并且更加高效，尋找的路徑更優(yōu)。該算法能夠有效地為人工智能魚進(jìn)行路徑規(guī)劃，為魚類行為探索提供一種有效參考。

□