， ，

(安徽工業(yè)大學(xué) 機(jī)械工程學(xué)院，安徽 馬鞍山 243000)

0 引 言

空中機(jī)器人是當(dāng)今研究的熱點(diǎn)，不論在軍事還是民用都發(fā)揮了巨大的作用。如物流配送[1]，農(nóng)用機(jī)器人[2]，車(chē)輛導(dǎo)航系統(tǒng)[3]，汽車(chē)泊車(chē)系統(tǒng)[4]等領(lǐng)域均得到了應(yīng)用[5]，而軌跡規(guī)劃是空中機(jī)器人研究的一個(gè)重要組成部分，所以空中機(jī)器人自主規(guī)劃路徑問(wèn)題一直是各大高校研究的熱點(diǎn)。空中機(jī)器人軌跡規(guī)劃問(wèn)題可以概括為在順利躲避障礙物的前提下，機(jī)器人可以自主找到一條從初始點(diǎn)到目標(biāo)點(diǎn)的最短路徑[6]。在研究的最初期，軌跡規(guī)劃問(wèn)題是采用人工規(guī)劃的方法，但是此方法不能實(shí)現(xiàn)預(yù)期的飛行任務(wù)，隨著對(duì)問(wèn)題的深入研究，國(guó)內(nèi)外學(xué)者提出了一系列軌跡規(guī)劃算法包括蟻群算法、粒子群算法、遺傳算法、A*算法、模糊邏輯算法[7-10]等 ，其中粒子群算法于1992年被Marco Dorigo提出，其靈感來(lái)自于螞蟻尋找食物時(shí)，螞蟻的路徑軌跡。和其他算法相比較而言，具有以下優(yōu)點(diǎn):1.優(yōu)良的分布式計(jì)算機(jī)制；2.較強(qiáng)的魯棒性；3.全局搜索方法；4.易于其他算法結(jié)合，利用蟻群算法通過(guò)柵格法對(duì)空中機(jī)器人飛行環(huán)境在MATLAB中進(jìn)行二維建模。通過(guò)仿真分析，可以看出蟻群算法在空中機(jī)器人軌跡規(guī)劃得到了很好應(yīng)用。

1 二維軌跡環(huán)境建模

1.1 環(huán)境模型預(yù)處理

空中機(jī)器人的飛行軌跡是在一定空間內(nèi)進(jìn)行的，假設(shè)空中機(jī)器人的飛行高度保持不變，飛行速度不變，并且假設(shè)在飛行過(guò)程中飛行環(huán)境不發(fā)生變化，那么空中機(jī)器人的飛行軌跡就可以簡(jiǎn)化成一個(gè)二維軌跡規(guī)劃問(wèn)題類(lèi)似于移動(dòng)機(jī)器人的軌跡規(guī)劃問(wèn)題。

1.2 柵格法

柵格法[11]是在進(jìn)行軌跡規(guī)劃時(shí)采用柵格來(lái)表示地圖，假設(shè)空中機(jī)器人的飛行環(huán)境是長(zhǎng)為L(zhǎng),寬為W的二維空間，并且每個(gè)柵格的長(zhǎng)和寬均為b，那么柵格的總數(shù)就位(L/b)×(W/b)。飛行環(huán)境A可由柵格Gij表示：

A={Gij/Gij=0或1，i,j為整數(shù)}

(1)

其中Gij=0表示無(wú)障礙區(qū)域，1表示有障礙區(qū)域 通過(guò)使用柵格法將空中機(jī)器人的飛行環(huán)境變成了可以用0,1表示的網(wǎng)格單元。柵格的標(biāo)識(shí)方法通常有兩種：直角坐標(biāo)法和序號(hào)法?？紤]到序號(hào)法相比直角坐標(biāo)法更加節(jié)省系統(tǒng)的存儲(chǔ)空間[12]，因此本文采用序號(hào)法對(duì)柵格進(jìn)行編碼，按照從左到右，從上到下依次對(duì)柵格進(jìn)行編碼，如圖1所示。

12345678910111213141516171819202122232425262728293031323334353637383940…………………………7172737475767778798081828384858687888990919293949596979899100

圖1 柵格編碼圖

1.3 二維飛行環(huán)境建模

當(dāng)空中機(jī)器人在離線(xiàn)狀態(tài)下要進(jìn)行飛行軌跡規(guī)劃，首先應(yīng)獲取飛行環(huán)境信息，二維飛行環(huán)境建模的關(guān)鍵所在是如何將環(huán)境信息轉(zhuǎn)變?yōu)閿?shù)字信息。在MATLAB中進(jìn)行飛行環(huán)境仿真，MATLAB主要對(duì)矩陣信息進(jìn)行加載，因此本文的環(huán)境建模主要是將環(huán)境信息轉(zhuǎn)換為用矩陣表示的數(shù)值。

根據(jù)柵格法構(gòu)造矩陣，用矩陣來(lái)表示環(huán)境信息，如下20×20矩陣G，由此也可知道該環(huán)境被分割為400個(gè)小柵格，在矩陣G20x20中，0表示自由區(qū)域，1表示障礙物區(qū)域。

將矩陣G20x20在MATLAB環(huán)境中進(jìn)行建模，得到結(jié)果如圖2

2 基于蟻群算法的空中機(jī)器人(UAV)軌跡規(guī)劃

2.1 蟻群算法概述

采用蟻群算法對(duì)空中機(jī)器人的軌跡進(jìn)行規(guī)劃，主要基于以下幾個(gè)原因：1優(yōu)良的分布式計(jì)算機(jī)制；2較強(qiáng)的魯棒性；3全局搜索方法；4易于其他算法結(jié)合

蟻群算法是一種模仿螞蟻群體行為的智能優(yōu)化算法，蟻群算法較早的應(yīng)用在TSP問(wèn)題，很多文獻(xiàn)基于TSP問(wèn)題來(lái)詳細(xì)介紹蟻群算法的基本原理[13],文中以采用此種方法。

圖2 二維環(huán)境建模

2.2 最優(yōu)軌跡

在確定最優(yōu)軌跡之前，首先介紹旅行商問(wèn)題簡(jiǎn)稱(chēng)為T(mén)SP,可將TSP問(wèn)題進(jìn)行如下描述：假設(shè)共有n個(gè)城市C={c1,c2,…,cn}及不同城市組合的路徑長(zhǎng)短dij(1in,1jn,i≠j)。TSP 問(wèn)題可以描述為從起點(diǎn)出發(fā)經(jīng)過(guò)所有城市且每座城市只經(jīng)過(guò)一次，最終回到起點(diǎn)的一條最短路徑問(wèn)題。設(shè)城市i和j之間的距離是dij，表示如式所示：

dij=[(xi-xj)2+(yi-yj)2]1/2

(2)

基于上述TSP問(wèn)題，則可以將空中機(jī)器人軌跡規(guī)劃問(wèn)題描述為：假設(shè)空中機(jī)器人從原點(diǎn)開(kāi)始飛行，并且在飛行過(guò)程中共經(jīng)過(guò)w個(gè)位置點(diǎn)，其中第p個(gè)位置的坐標(biāo)為Wp=(xp，yp),那么在飛行過(guò)程中空中機(jī)器人的飛行距離可以表示為：

(3)

由于在空中機(jī)器人飛過(guò)這w個(gè)位置點(diǎn)時(shí)，經(jīng)過(guò)這些點(diǎn)的順序是不同的，假設(shè)總共有l(wèi)條不同的軌跡路線(xiàn)，通過(guò)(3)式可以計(jì)算不同軌跡路線(xiàn)的長(zhǎng)度，那么可以形成一個(gè)長(zhǎng)度集合Lall，minL就是在長(zhǎng)度集合Lall中長(zhǎng)度最短的那條路徑。

Lall=[L1,L2,L3…,Ll]

(4)

minL=min(Lall)

(5)

2.3 蟻群算法的應(yīng)用

(6)

式中：allowedk代表第k只螞蟻當(dāng)其處在柵格i時(shí)供其下一步可以移動(dòng)的柵格；τij代表柵格i和柵格j之間的信息素強(qiáng)度；a的作用是可以控制信息素的相對(duì)重要程度；β的作用是控制路徑長(zhǎng)度的相對(duì)重要程度；ηij表示柵格i到柵格j的能見(jiàn)度，反映有柵格i轉(zhuǎn)移到柵格j的啟發(fā)程度[14]。

圖3 基本蟻群的算法框圖

根據(jù)問(wèn)題可知每次螞蟻必須經(jīng)過(guò)所有的城市，而且同一城市不得重復(fù)經(jīng)過(guò)，因此為每只螞蟻都設(shè)計(jì)了一個(gè)數(shù)據(jù)結(jié)構(gòu)，稱(chēng)為禁忌列表(Tabu List)。禁忌表的作用是可以對(duì)螞蟻的路徑進(jìn)行約束，在禁忌表中記錄了在本次循環(huán)中螞蟻已經(jīng)走過(guò)的城市，那么在本次循環(huán)中就不允許螞蟻再通過(guò)禁忌表中記錄的這些城市。在結(jié)束一次循環(huán)之后，可以根據(jù)在禁忌表中記錄城市的順序從而可以計(jì)算出每只螞蟻所爬過(guò)的路徑長(zhǎng)度。計(jì)算完成后，禁忌表中記錄的數(shù)據(jù)被清除，那么該螞蟻就可以重新選擇其他路徑。圖3為基本蟻群的算法框圖

在螞蟻行走過(guò)程中中會(huì)存在啟發(fā)信息無(wú)法體現(xiàn)的問(wèn)題，這是由于殘留信息素過(guò)多的原因，因此在每只螞蟻?zhàn)弑樗谐鞘兄螅髮?duì)殘留信息素信息素進(jìn)行更新處理。(t+n)時(shí)刻在路徑(i,j)上的信息量按式(7)和式(8)所示的規(guī)則進(jìn)行更新

τij(t+n)=(1-ρ)·τij(t)+Δτij(t)

(7)

(8)

(9)

式中：LK表示第k只螞蟻其爬過(guò)的那條路徑的總長(zhǎng)度，Q表示第k只螞蟻在其爬過(guò)的路徑上釋放的信息素總量[15]

3 規(guī)劃結(jié)果

設(shè)置初始螞蟻數(shù)量m,啟發(fā)式因子α、期望啟發(fā)式因子β、信息素強(qiáng)度Q、信息素蒸發(fā)系數(shù)ρ[16]，迭代循環(huán)次數(shù)K，初始參數(shù)值見(jiàn)圖：

圖4 二維參數(shù)初始值

圖5 蟻群算法求解二維環(huán)境模型的最短路徑

圖6 蟻群算法求解二維環(huán)境模型的最短路徑(改變起始點(diǎn))

確定起始點(diǎn)S，終止點(diǎn)E，在MATLAB仿真后求得路徑。如圖5所示，S點(diǎn)代表起始點(diǎn)，E代表終止點(diǎn)，在S和E之間有一條線(xiàn)段，這就是通過(guò)基本蟻群算法在已知二維環(huán)境的條件下求得的一條最優(yōu)路徑。如圖6，改變起始點(diǎn)和終止點(diǎn)的位置通過(guò)仿真同樣會(huì)得到一條最優(yōu)路徑。

通過(guò)仿真的軌跡圖所示可以了解到，蟻群算法在尋找到達(dá)終點(diǎn)的路徑過(guò)程中，是按照其基本原理來(lái)實(shí)現(xiàn)的，在圖7中可以看到從起始點(diǎn)到終止點(diǎn)的一系列線(xiàn)條，代表螞蟻尋找目標(biāo)過(guò)程中所走過(guò)的每一條路徑。然后通過(guò)比較每一條路徑的長(zhǎng)度來(lái)確定出最短路徑，也就是尋找的最優(yōu)路徑。

圖7 蟻群算法的搜索路徑

4 結(jié) 語(yǔ)

蟻群算法在尋找最優(yōu)路徑過(guò)程中隨著迭代次數(shù)的增加，所收尋到的路徑越來(lái)越短，圖中直線(xiàn)代表了平均路徑長(zhǎng)度，帶有雪花點(diǎn)的線(xiàn)代表的是最優(yōu)路線(xiàn)長(zhǎng)度，最終在迭代了100次左右，兩條線(xiàn)收斂在同一數(shù)據(jù)上，由此可知參數(shù)的選取是合適的，所尋得的路徑也是可行的，整個(gè)路徑規(guī)劃的過(guò)程是成功的。但本文僅是對(duì)二維飛行環(huán)境進(jìn)行規(guī)劃，與實(shí)際飛行情況略有不符，日后還需進(jìn)一步進(jìn)行研究。同時(shí)蟻群算法本身也存在著缺點(diǎn)：1蟻群算法在進(jìn)行飛行軌跡規(guī)劃時(shí)需要進(jìn)行多次迭代，浪費(fèi)時(shí)間，因此效率較低。2當(dāng)在求解問(wèn)題中，經(jīng)過(guò)的點(diǎn)越多(經(jīng)過(guò)的城市越多)，那么就有可能存在求得的結(jié)果只是求解過(guò)程中一部分的最優(yōu)解而非整個(gè)求解問(wèn)題的最優(yōu)解。因此，我們還需進(jìn)一步的研究以改進(jìn)蟻群算法。