基于蟻群算法的無人機(jī)航跡規(guī)劃研究

牛昭文，羅銀輝

（中國民用航空飛行學(xué)院計(jì)算機(jī)學(xué)院，廣漢618307）

0 引言

無人機(jī)執(zhí)行任務(wù)的復(fù)雜化，使得無人機(jī)航跡規(guī)劃的研究越來越被重視。其目標(biāo)是在現(xiàn)實(shí)允許的時(shí)間內(nèi)尋找最優(yōu)或較優(yōu)的飛行航跡，是確保無人機(jī)提高飛行器效能，圓滿完成任務(wù)的技術(shù)保障。無人機(jī)航跡規(guī)劃是指在綜合考慮無人機(jī)性能約束、威脅約束、任務(wù)約束等多方面約束條件下，為無人機(jī)規(guī)劃出一條滿足約束的飛行軌跡[1]。根據(jù)對各領(lǐng)域和常用路徑規(guī)劃算法的研究，參照算法的時(shí)間發(fā)展歷程和對應(yīng)的基本原理，可將算法種類分為：傳統(tǒng)算法、圖形學(xué)算法、智能仿生學(xué)算法和其他算法[2]。作為智能仿生學(xué)算法中的蟻群算法，以其優(yōu)越的性能和特點(diǎn)，正逐步被應(yīng)用到規(guī)劃、商旅、調(diào)度、排序等諸多問題中。因此，蟻群算法可以作為實(shí)現(xiàn)無人作航跡規(guī)劃的搜索算法，并輸出無人機(jī)最優(yōu)航跡解[3]。

本文通過運(yùn)用蟻群算法，對無人機(jī)在三維電子地圖中的航跡進(jìn)行規(guī)劃，并通過MATLAB 仿真軟件編程加以實(shí)現(xiàn)，最終輸出基于蟻群算法的無人機(jī)三維航跡最優(yōu)解。

1 蟻群算法概述

1.1 蟻群算法描述

蟻群系統(tǒng)（Ant System 或Ant Colony System）最早是由意大利學(xué)者Dorigo 和Maniezzo 等人在20 世紀(jì)90年代所提出的。1992 年，Marco Dorigo 在他的博士論文中正式提出了這種尋找優(yōu)化路徑的概率型算法——蟻群算法，隨后吸引了一大批世界各地的學(xué)者競相研究[4]。

研究發(fā)現(xiàn)蟻群中單個螞蟻的行為較為簡單，但是整個蟻群卻可以體現(xiàn)一些智能化的行為方式。以蟻群覓食為例，這是因?yàn)橄伻簝?nèi)的螞蟻可以通過某種信息機(jī)制實(shí)現(xiàn)信息的傳遞。在后續(xù)的研究中發(fā)現(xiàn)，螞蟻會在其經(jīng)過的路徑上釋放一種物質(zhì)，稱之為“信息素”。螞蟻對“信息素”的感知能力極強(qiáng)，它們會沿著“信息素”濃度較高的路徑行走，而每只經(jīng)過的螞蟻又會重新留下“信息素”以加深此路徑上的信息濃度，因此形成了一種正反饋的機(jī)制。一段時(shí)間過后，整個覓食的蟻群就會沿著這條最短路徑到達(dá)食物源所在的覓食區(qū)了[5]。

Goss 等學(xué)者在1989 年為了對蟻群的覓食行為做更深層次的研究，進(jìn)行了“非對稱雙橋?qū)嶒?yàn)”。如圖1所示，覓食去和蟻穴之間由非對稱雙橋相連，蟻群需要經(jīng)過非對稱雙橋抵達(dá)覓食區(qū)覓食。在覓食初期階段，由于蟻群未在所有可行的行動路徑上留下信息素，因此，蟻群可隨機(jī)自由選擇路徑抵達(dá)覓食區(qū)，即通過左右兩側(cè)路徑的概率相等。分別在實(shí)驗(yàn)開始的4 分鐘和8分鐘做記錄和比較，觀察得較短路徑上的螞蟻個數(shù)逐漸增多，殘留下的信息素也隨之增多，越來越多的螞蟻被此條最短路徑所“吸引”。該實(shí)驗(yàn)表明，蟻群在覓食行為中，總能找到一條蟻穴至覓食區(qū)之間的最短路徑，并且被絕大多數(shù)的螞蟻共享，同時(shí)也印證了蟻群具有較強(qiáng)的適應(yīng)能力，引申至蟻群算法中，表現(xiàn)為自適應(yīng)性強(qiáng)。

圖1 蟻群非對稱雙橋?qū)嶒?yàn)示意圖

1.2 蟻群算法優(yōu)點(diǎn)

蟻群算法是通過觀察真實(shí)蟻群的生活習(xí)性，研究螞蟻在覓食中的現(xiàn)象而形成的算法，因此蟻群算法繼承了真實(shí)蟻群系統(tǒng)的諸多特點(diǎn)[6]。現(xiàn)將蟻群算法的優(yōu)缺點(diǎn)進(jìn)行羅列比對，其具體優(yōu)點(diǎn)歸納如下：

（1）自適應(yīng)性強(qiáng)

蟻群算法可以不借助外界因素的幫助而高效、有序地運(yùn)行，具有較強(qiáng)的自適應(yīng)性。蟻群特有的信息共享機(jī)制和搜索機(jī)制是蟻群自適應(yīng)性的基本保障。基于此特性，蟻群在行為決策和系統(tǒng)調(diào)整時(shí)，也能保證蟻群整體架構(gòu)繼續(xù)可靠地運(yùn)行。

（2）魯棒性優(yōu)越

蟻群算法之所以廣泛應(yīng)用在各個領(lǐng)域中，關(guān)鍵因素就是其魯棒性優(yōu)越，在外界干擾下，也能保證固有的特性繼續(xù)保持，體現(xiàn)為穩(wěn)定魯棒性和性能魯棒性兩點(diǎn)。蟻群算法通過調(diào)整概率轉(zhuǎn)移模型來求解問題的最優(yōu)解，而算法的收斂程度不受參數(shù)、概率模型的改變而改變。

（3）并行計(jì)算能力強(qiáng)

并行計(jì)算是指能夠同時(shí)使用多種運(yùn)算資源解決計(jì)算問題的過程，是提高計(jì)算機(jī)系統(tǒng)計(jì)算速度和處理能力的一種有效手段。蟻群算法能夠獨(dú)立有效地求解搜索空間中的最優(yōu)解，使運(yùn)算過程同步進(jìn)行，在產(chǎn)生信息素的同時(shí)，協(xié)同合作，繼續(xù)搜索，確保了搜索方向的可靠性。

（4）全局搜索能力強(qiáng)

在面對復(fù)雜環(huán)境的搜索任務(wù)時(shí)，往往需要算法將所有可能的解呈現(xiàn)出來，因此，在某些特定應(yīng)用場景下，需要體現(xiàn)出相應(yīng)算法的全局搜索能力。而蟻群算法中的每個螞蟻都作為一個信息素，對全局進(jìn)行搜索并傳遞信息，所以蟻群算法具有極強(qiáng)的全局搜索能力。

（5）易結(jié)合，通用性好

蟻群算法易于與其他算法相結(jié)合，通過在算法性能上的互補(bǔ)，來求解最優(yōu)解以展現(xiàn)算法的高性能，此特點(diǎn)完善了混合智能算法的應(yīng)用，使得蟻群算法在解決諸多問題上可以通用。

1.3 蟻群算法模型

蟻群算法在推廣之初，主要應(yīng)用于解決組合優(yōu)化中旅行商（TSP）的問題，旅行商需要按照一定的順序訪問城市，保證從出發(fā)城市開始至返回出發(fā)城市的過程中，每個城市只訪問一次，且所選路徑最短[7]。

以旅行商問題為例，參照表1，引入以下蟻群算法數(shù)學(xué)模型中的參數(shù)符號。

表1 蟻群算法數(shù)學(xué)模型參數(shù)符號

蟻群算法數(shù)學(xué)模型的狀態(tài)轉(zhuǎn)移概率公式可表示為：

其中，allowedk為螞蟻k 還未曾到訪的城市，allowedk={C - tabuk} ；α、β 均為常數(shù)。螞蟻在每走完一步或經(jīng)過每一個城市之后，都要對路徑上的信息素進(jìn)行更新替換，此舉是為了防止在某條路徑上的信息素殘留過多，導(dǎo)致啟發(fā)信息失去作用，為此，城市i 與城市j 之間的信息素規(guī)則更新如下：

圖2 蟻群算法流程圖

2 航跡規(guī)劃建模

2.1 柵格法劃分三維空間

柵格法是一種地圖建模方法，通過將地圖進(jìn)行單元分割，用大小相同的方塊表示，來直觀地分析路徑規(guī)劃等問題。柵格地圖的精度取決于柵格塊的大小，柵格區(qū)域越小，地圖信息就越清晰。三維空間也同樣采取柵格法進(jìn)行劃分。以中心點(diǎn)為起始點(diǎn)，在三維空間下，周圍共計(jì)26 個相鄰節(jié)點(diǎn)。設(shè)三維規(guī)劃空間的8 個點(diǎn)坐標(biāo)分別為：(xmin,ymin,zmin)、(xmax,ymin,zmin)、(xmax,ymin,zmin)、(xmin,ymin,zmax)、(xmax,ymax,zmin)、(xmax,ymin,zmax)、(xmin,ymax,zmax)、(xmax,ymax,zmax)；則三維空間各方向柵格數(shù)分別為nx、ny、nz，柵格節(jié)點(diǎn)總數(shù)為n=nx×ny×nz。

2.2 信息啟發(fā)因子

3 仿真研究結(jié)果

為驗(yàn)證蟻群算法在航跡規(guī)劃問題上的求解性能，本節(jié)以三維空間電子地圖為例，如圖3 所示，進(jìn)行仿真驗(yàn)證。具體求解問題為：以圖3 中三維電子地形圖為依據(jù)，求解從A 點(diǎn)到B 點(diǎn)的基于蟻群算法的三維航跡規(guī)劃問題。

圖3 航跡規(guī)劃問題起始點(diǎn)、目標(biāo)點(diǎn)示意圖

在電子地圖中設(shè)置兩點(diǎn)地形威脅，具體參數(shù)參照表2。

表2 三維路徑規(guī)劃參數(shù)及數(shù)值

設(shè)置地形威脅1#、2#的威脅半徑分別為：2000m、3000m。地形威脅在電子地圖中，可表示為以不同色圓柱體，其仿真結(jié)果如圖4 所示。

圖4 基于蟻群算法的三維航跡規(guī)劃仿真示意圖

4 結(jié)語

通過上述實(shí)驗(yàn)仿真結(jié)果，可以發(fā)現(xiàn)蟻群算法在求解無人機(jī)航跡規(guī)劃問題中的優(yōu)越性。本文研究了基于蟻群的無人機(jī)三維航跡規(guī)劃，并利用MATLAB 軟件進(jìn)行編程，實(shí)現(xiàn)了該算法求解航跡的仿真結(jié)果，同時(shí)，蟻群算法可用于解決實(shí)際無人機(jī)飛行一些相關(guān)問題，具有一定的實(shí)際意義。而通過MATLAB 編程和仿真，有助于無人機(jī)航跡更好地展示。