， ，

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

0 引 言

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

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

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

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

1.2 柵格法

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

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

(1)

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

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

圖1 柵格編碼圖

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

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

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

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

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

2.1 蟻群算法概述

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

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

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

2.2 最優(yōu)軌跡

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

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

(2)

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

(3)

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

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

(4)

minL=min(Lall)

(5)

2.3 蟻群算法的應用

(6)

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

圖3 基本蟻群的算法框圖

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

在螞蟻行走過程中中會存在啟發(fā)信息無法體現(xiàn)的問題，這是由于殘留信息素過多的原因，因此在每只螞蟻走遍所有城市之后，要求對殘留信息素信息素進行更新處理。(t+n)時刻在路徑(i,j)上的信息量按式(7)和式(8)所示的規(guī)則進行更新

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

(7)

(8)

(9)

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

3 規(guī)劃結果

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

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

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

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

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

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

圖7 蟻群算法的搜索路徑

4 結 語

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