袁紅春，毛 瑞，楊蒙召

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

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

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

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

1 A*算法概述

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

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

(1)

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

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

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

曼哈頓距離是坐標(biāo)系中兩點之間坐標(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)系的兩點直線距離，其預(yù)估公式為：

(4)

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

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

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

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

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

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

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

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

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

(5)

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

AABB碰撞檢測算法如圖2所示。

圖2 AABB碰撞檢測算法

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

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

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

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

3 試驗結(jié)果

3.1 試驗平臺

試驗硬件環(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ù)對曲面上的頂點序列進(jìn)行定義的方法來精確描述控制網(wǎng)點因子；其次采用曲面控制網(wǎng)點位置坐標(biāo)的方式進(jìn)行實時繪制，以形成離散的網(wǎng)格模型，并可用其“包裝”生物力學(xué)模型。構(gòu)建后發(fā)布并導(dǎo)入Unity3D中。

圖4為3ds Max生成初步魚體網(wǎng)格模型圖。首先將需要建模魚的圖片導(dǎo)入至3ds Max中，使用曲面建模方法進(jìn)行構(gòu)建，從而在Front視圖中建立模型。對圖片進(jìn)行描點并轉(zhuǎn)化成可編輯的多邊形，通過相應(yīng)的拖點來制作魚的外形。然后繼續(xù)進(jìn)行橫向拖點操作，以便產(chǎn)生新的頂點和表面，通過拉伸表面可以生成胸鰭、腹鰭等更多細(xì)節(jié)的魚體形狀。魚眼的制作通過對魚頭的裂頂點、對齊及擠壓形成，從而生成如圖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*算法仿真試驗

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

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

圖6 三維海底圖

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

圖7 試驗結(jié)果

表1 試驗結(jié)果

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

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

圖8 場景俯視圖

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

圖9 魚類避障圖

4 討論

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

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

4.2 人工魚的智能化研究對比

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

5 結(jié)論

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

□