結(jié)合B樣條優(yōu)化的UAV多區(qū)域路徑規(guī)劃融合算法

汪瀚洋，盧厚清，陳 亮，趙小康，楊 柳

(1.陸軍工程大學(xué) 野戰(zhàn)工程學(xué)院，南京 210007; 2.軍事交通學(xué)院 汽車士官學(xué)校，安徽 蚌埠 233011)

0 引言

無(wú)人機(jī)(UAV，unmanned aerial vehicle)作為新型智能化作戰(zhàn)力量，具有較低的應(yīng)用成本的同時(shí)，也具有較好的機(jī)動(dòng)性，其在戰(zhàn)場(chǎng)上被廣泛使用于偵察任務(wù)。在實(shí)際復(fù)雜戰(zhàn)場(chǎng)環(huán)境中，一般都有多個(gè)任務(wù)區(qū)域等待無(wú)人機(jī)去執(zhí)行信息偵察任務(wù)。無(wú)人機(jī)需要規(guī)避戰(zhàn)場(chǎng)中的威脅區(qū)域(這些區(qū)域中存在敵防空火力等威脅)對(duì)各個(gè)目標(biāo)區(qū)域進(jìn)行遍歷偵察。如何快速規(guī)劃出保證無(wú)人機(jī)遍歷各個(gè)任務(wù)區(qū)域并安全返回原基地的最優(yōu)路徑是亟待解決的問(wèn)題，該情形可被視為類旅行商問(wèn)題(TSP，travelling salesman problem)，其本質(zhì)是無(wú)人機(jī)自主導(dǎo)航的需要。

當(dāng)前國(guó)內(nèi)外學(xué)者已提出了大量無(wú)人機(jī)路徑規(guī)劃算法。在主要文獻(xiàn)中提到的方法有：1)路圖法，如A*、D*算法;2)概率法;3)勢(shì)場(chǎng)法；4)智能優(yōu)化算法，如蟻群算法等。需要指出的是，TSP問(wèn)題因其本身的特性，目標(biāo)點(diǎn)如果比較多，在進(jìn)行窮舉求解時(shí)，會(huì)出現(xiàn)組合爆炸的問(wèn)題，所以近似求解是常被采取的方法。蟻群算法是眾多智能優(yōu)化算法中最經(jīng)典的算法之一，其常被用于解決TSP問(wèn)題，并取得了良好的計(jì)算效果。該算法具有良好的魯棒性和穩(wěn)定性，同時(shí)在與其他算法融合方面也有良好的表現(xiàn)，在路徑規(guī)劃、自主導(dǎo)航等問(wèn)題上有著廣泛應(yīng)用。

A*算法是一種常見且應(yīng)用廣泛的搜索尋徑算法，其特點(diǎn)在于對(duì)評(píng)價(jià)函數(shù)的定義上。在一般的有序路徑搜索中，該算法總是選擇綜合代價(jià)值最小的路徑節(jié)點(diǎn)作為擴(kuò)展節(jié)點(diǎn)，優(yōu)點(diǎn)是可實(shí)現(xiàn)路徑的快速規(guī)劃。文獻(xiàn)[1]提出了一種使用圓形鄰域節(jié)點(diǎn)擴(kuò)展法的A*算法改進(jìn)，提高了搜索效率，但是沒(méi)有解決生成路徑貼近或者斜穿障礙物的問(wèn)題，給無(wú)人機(jī)的生存安全帶來(lái)隱患。文獻(xiàn)[2]提出了一種混合蟻群算法解決靜態(tài)環(huán)境下的機(jī)器人路徑規(guī)劃問(wèn)題，避免了蟻群算法陷入局部最優(yōu)，但是凸顯了蟻群算法收斂速度較慢的缺點(diǎn)。上述文章都體現(xiàn)出一個(gè)問(wèn)題：即單獨(dú)使用蟻群算法或A*算法，都不能很好解決本文情況下的TSP問(wèn)題。蟻群算法易出現(xiàn)局部最優(yōu)和陷入遲滯，而A*算法會(huì)由于僅僅規(guī)劃兩兩目標(biāo)之間的局部最優(yōu)路徑，以及組合爆炸的問(wèn)題，并不一定保證可以規(guī)劃出全局最優(yōu)遍歷路徑。本文通過(guò)蟻群算法融合改進(jìn)A*算法來(lái)解決無(wú)人機(jī)多目標(biāo)區(qū)域遍歷路徑規(guī)劃的問(wèn)題，并結(jié)合改進(jìn)三次B樣條方法平滑規(guī)劃路徑。仿真結(jié)果表明,融合算法能有效解決問(wèn)題,在算法規(guī)劃速度、路徑質(zhì)量及安全度上有明顯改善,相比傳統(tǒng)算法有明顯優(yōu)勢(shì)。

1 路徑規(guī)劃問(wèn)題描述與環(huán)境建模

1.1 問(wèn)題描述

無(wú)人機(jī)多目標(biāo)區(qū)域遍歷問(wèn)題本質(zhì)是一個(gè)類TSP問(wèn)題，如圖1所示，無(wú)人機(jī)從基地出發(fā)前往各個(gè)目標(biāo)區(qū)域執(zhí)行偵察任務(wù)。在存在威脅區(qū)的偵察任務(wù)環(huán)境中，無(wú)人機(jī)不僅需要規(guī)劃兩兩目標(biāo)區(qū)域之間的路徑，還需要規(guī)劃到各個(gè)目的地的先后順序，在保證自身安全返回的同時(shí)力求全局路徑的最優(yōu)化，以獲取更高的偵察收益。

圖1 問(wèn)題描述

為方便描述無(wú)人機(jī)在偵察任務(wù)中規(guī)避威脅區(qū)域并遍歷各個(gè)任務(wù)區(qū)的問(wèn)題，將該問(wèn)題簡(jiǎn)化描述如下：

1)無(wú)人機(jī)可看作一個(gè)可操縱質(zhì)點(diǎn)；

2)執(zhí)行偵察任務(wù)中，無(wú)人機(jī)保持穩(wěn)定飛行高度及速度，環(huán)境為二維空間；[3]

3)基于柵格法建立地圖模型，全局靜態(tài)威脅區(qū)域范圍及任務(wù)區(qū)位置已知。無(wú)人機(jī)從給定起始基地位置出發(fā)，規(guī)避環(huán)境中的威脅區(qū)并規(guī)劃出一條遍歷所有偵察任務(wù)區(qū)域并最后返回基地的安全航路。

1.2 環(huán)境建模

基于柵格地圖的環(huán)境建模具有建模復(fù)雜性低、適應(yīng)能力強(qiáng)、易于實(shí)現(xiàn)與存儲(chǔ)等優(yōu)點(diǎn)。柵格地圖將三維空間降維為二維平面，并將整個(gè)平面劃為大小相等的各個(gè)柵格。整個(gè)二維平面由柵格取值為二進(jìn)制0-1矩陣所構(gòu)成，利用0-1矩陣進(jìn)行判斷柵格是否可通行。矩陣中數(shù)值為0代表無(wú)人機(jī)可以正常通行，反之?dāng)?shù)值為1則為威脅區(qū)并不可通行[4]。具體對(duì)應(yīng)關(guān)系如圖2所示。

圖2 柵格設(shè)置

在實(shí)際環(huán)境中，威脅區(qū)會(huì)呈現(xiàn)出不同的形狀，在柵格地圖中構(gòu)建威脅區(qū)時(shí)，如按照威脅區(qū)的原形狀進(jìn)行建立，如圓形、多邊形甚至不規(guī)則形等，將會(huì)導(dǎo)致障礙物邊緣出現(xiàn)失真[5]，從而導(dǎo)致搜索效率和路徑安全性的下降。

在現(xiàn)有研究中，柵格地圖大多使用矩形外包原形狀以避免失真情況的發(fā)生。因此，本文中的威脅區(qū)統(tǒng)一使用“外包”進(jìn)行處理，即分別將原有規(guī)則或不規(guī)則形狀統(tǒng)一進(jìn)行柵格填充，當(dāng)威脅區(qū)不滿足一個(gè)柵格大小，將其填充為一個(gè)柵格。圖3中分別為處理前后的威脅區(qū)形狀，這樣只要保證規(guī)劃路徑不進(jìn)入填充后的威脅區(qū)，即可保證規(guī)劃路徑安全性。

圖3 威脅區(qū)形變

無(wú)人機(jī)在柵格環(huán)境中運(yùn)動(dòng)，圖4顯示了無(wú)人機(jī)的運(yùn)動(dòng)情況。各箭頭所指方向?yàn)闊o(wú)人機(jī)初始可擴(kuò)展方向，即初始8鄰域節(jié)點(diǎn)擴(kuò)展?，F(xiàn)在假設(shè)無(wú)人機(jī)在二維平面區(qū)域S內(nèi)移動(dòng)，設(shè)S的左底角為原點(diǎn)O，以水平方向?yàn)閤軸，垂直方向?yàn)閥軸，建立平面直角坐標(biāo)系xOy，如圖5所示。對(duì)于該25個(gè)柵格集合，其中任一柵格都有確定坐標(biāo)和對(duì)應(yīng)的序號(hào)，則無(wú)人機(jī)在柵格地圖中的地圖坐標(biāo)和序號(hào)位置對(duì)應(yīng)關(guān)系如下:

圖4 運(yùn)動(dòng)環(huán)境

圖5 柵格坐標(biāo)

(1)

其中:mod表示取余運(yùn)算;ceil表示求整運(yùn)算;nx、ny表示每行每列的柵格數(shù);xi、yi表示柵格i的中心點(diǎn)橫坐標(biāo)和縱坐標(biāo)[6]。

2 算法改進(jìn)及融合

2.1 蟻群算法

螞蟻在運(yùn)動(dòng)中,會(huì)在其所經(jīng)過(guò)的路徑上留下一種被稱為信息素的物質(zhì),這種物質(zhì)是各螞蟻之間進(jìn)行信息交流的載體。螞蟻在運(yùn)動(dòng)中會(huì)感知到這種物質(zhì)，并循跡此物質(zhì)進(jìn)行運(yùn)動(dòng),同時(shí)爬行過(guò)程中同樣釋放信息素。某一路徑上的信息素濃度越高,螞蟻將以更高的概率選擇此路徑進(jìn)行運(yùn)動(dòng),使得該路徑上的信息素濃度繼續(xù)增高,至此便出現(xiàn)一種信息正反饋現(xiàn)象。某路徑上運(yùn)動(dòng)過(guò)的螞蟻越多,后來(lái)者選擇該路徑進(jìn)行運(yùn)動(dòng)的可能性就越大[7]。

蟻群算法的基本原理，即基于螞蟻根據(jù)路徑上同類釋放的信息素濃度進(jìn)行路徑選擇，距離短的路徑在理論上會(huì)更多地被選擇，經(jīng)過(guò)迭代和避免局部?jī)?yōu)化后，可得到全局最優(yōu)路徑。蟻群算法可以有效求解TSP問(wèn)題，在本任務(wù)環(huán)境中，算法數(shù)學(xué)模型如下：

(2)

其中:αk表示待偵查區(qū)域的集合，α表示信息度啟發(fā)因子，β為啟發(fā)函數(shù)的重要程度因子,ηij=1/dij是從目標(biāo)區(qū)i到目標(biāo)區(qū)j的啟發(fā)式因子。

在所有螞蟻選擇完路徑后，路徑上的信息素濃度更新為：

(3)

(4)

其中:Q為信息素常量，表示1次循環(huán)中，螞蟻k所釋放的信息素總量。Pathk為螞蟻k的路徑集合,Lk表示第k只螞蟻本次循環(huán)中途徑的路程總長(zhǎng)[8]。

所有螞蟻完成一次路徑選擇后，根據(jù)路徑上的信息素濃度記錄本次最佳路徑，更新路徑信息量。經(jīng)過(guò)指定次數(shù)循環(huán)后，輸出最終路徑的優(yōu)化結(jié)果。

2.2 A*算法

A*算法是一種啟發(fā)式搜索算法，其常被用來(lái)解決無(wú)人機(jī)路徑規(guī)劃問(wèn)題。其是在Dijkstra算法的基礎(chǔ)上引入評(píng)價(jià)函數(shù)機(jī)制，將路徑搜索代價(jià)進(jìn)行綜合考慮，能有效解決全局靜態(tài)環(huán)境下最短路徑的搜索問(wèn)題。

A*算法通過(guò)評(píng)價(jià)函數(shù)來(lái)確定到目標(biāo)節(jié)點(diǎn)搜索方向，路徑由當(dāng)前節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的評(píng)價(jià)函數(shù)f(n)的最小值來(lái)確定。傳統(tǒng)A*算法在進(jìn)行路徑規(guī)劃時(shí)會(huì)設(shè)置兩個(gè)列表，一個(gè)是Open list表，其用來(lái)保存準(zhǔn)備搜索的節(jié)點(diǎn)，另一個(gè)是Closed list表，用來(lái)存放已經(jīng)被搜索到的截至目前最小路徑搜索代價(jià)的點(diǎn)。探索過(guò)程中，先從Open list中找到路徑搜索代價(jià)最小的點(diǎn)設(shè)為當(dāng)前節(jié)點(diǎn)，將其放入Closed list，然后對(duì)其進(jìn)行擴(kuò)展搜索，將擴(kuò)展搜索后得到的節(jié)點(diǎn)更新到Open list中，再?gòu)腛pen list選取搜索代價(jià)最小的點(diǎn)設(shè)為當(dāng)前節(jié)點(diǎn)，重復(fù)過(guò)程，直到找到目標(biāo)點(diǎn)。

A*算法的評(píng)估函數(shù)為：

f(n)=g(n)+h(n)

(5)

其中:n為柵格中某節(jié)點(diǎn)；g(n)為起點(diǎn)到該點(diǎn)的最短路徑的代價(jià)函數(shù)；h(n)為該點(diǎn)達(dá)到目標(biāo)點(diǎn)最短路徑代價(jià)函數(shù)。

在柵格地圖中，評(píng)價(jià)函數(shù)的選擇在一般情況下根據(jù)移動(dòng)體可擴(kuò)展的方向而定。如果移動(dòng)體只能向4個(gè)方向擴(kuò)展，這時(shí)曼哈頓距離是計(jì)算評(píng)價(jià)函數(shù)的最佳選擇；如果移動(dòng)體可以向8個(gè)方向擴(kuò)展，這時(shí)評(píng)價(jià)函數(shù)使用切比雪夫距離計(jì)算更加合適；如果移動(dòng)體可以在任意方向移動(dòng)，則評(píng)價(jià)函數(shù)選擇歐幾里得距離計(jì)算比較有優(yōu)越性。具體如圖6所示。

圖6 評(píng)價(jià)函數(shù)計(jì)算

考慮到無(wú)人機(jī)實(shí)際運(yùn)行軌跡的任意性[9]，本文中A*算法的評(píng)估函數(shù)中的h(n)采用歐氏距離為代價(jià)值進(jìn)行計(jì)算。設(shè)當(dāng)前節(jié)點(diǎn)坐標(biāo)為(xn，yn),目標(biāo)點(diǎn)坐標(biāo)為(xg，yg)，歐幾里得距離表示兩坐標(biāo)的最短距離，其公式為:

(6)

2.3 改進(jìn)A*算法

A*算法的規(guī)劃路徑存在斜穿威脅區(qū)柵格頂點(diǎn)、斜穿兩個(gè)威脅區(qū)柵格相接點(diǎn)的現(xiàn)象，這是由于該路徑的擴(kuò)展代價(jià)最低，且符合節(jié)點(diǎn)擴(kuò)展規(guī)責(zé)造成的，容易導(dǎo)致路徑發(fā)生進(jìn)入威脅區(qū)的風(fēng)險(xiǎn)，路徑如圖7所示。

圖7 非法路徑

針對(duì)傳該問(wèn)題，本文對(duì)節(jié)點(diǎn)選擇規(guī)責(zé)進(jìn)行重新定義：

圖8 節(jié)點(diǎn)分類

1)當(dāng)威脅區(qū)位置在第Ⅰ類節(jié)點(diǎn)時(shí)。其中，當(dāng)威脅區(qū)位置在節(jié)點(diǎn)2時(shí)，則不選擇節(jié)點(diǎn)1、3；威脅區(qū)位置在節(jié)點(diǎn)7時(shí)，則不選擇節(jié)點(diǎn)6、8。

2)當(dāng)威脅區(qū)位置在第Ⅱ類節(jié)點(diǎn)時(shí)。其中，當(dāng)威脅區(qū)位置在節(jié)點(diǎn)4時(shí)，則不選擇節(jié)點(diǎn)1、6；威脅區(qū)位置在節(jié)點(diǎn)5時(shí)，則不選擇子節(jié)點(diǎn)3、8。

經(jīng)過(guò)初步試驗(yàn)，上述優(yōu)化路徑如圖9所示。改進(jìn)后的路徑可以有效避免無(wú)人機(jī)進(jìn)入威脅區(qū)。

圖9 優(yōu)化路徑

2.4 蟻群-A*算法融合

蟻群算法在解決TSP問(wèn)題時(shí)，是基于目標(biāo)區(qū)的坐標(biāo)來(lái)計(jì)算的，即此時(shí)各目標(biāo)區(qū)之間的距離是已知的。在本文柵格地圖中，由于各任務(wù)區(qū)之間距離未確定、環(huán)境中存在威脅區(qū)不可通過(guò)等原因，蟻群算法在計(jì)算各任務(wù)區(qū)之間的距離時(shí)，需要反復(fù)迭代，且因?yàn)橄伻核惴ū旧碛?jì)算時(shí)間長(zhǎng)、啟發(fā)效果差和易陷入局部最優(yōu)等原因，會(huì)導(dǎo)致全局規(guī)劃路徑耗時(shí)較長(zhǎng)[10]。

A*算法同樣不能很好地單獨(dú)解決TSP問(wèn)題。A*算法通過(guò)找到任意兩個(gè)目標(biāo)區(qū)之間的最短距離的方法搜索全局路徑,會(huì)導(dǎo)致結(jié)果不一定是全局范圍中的最優(yōu)路徑。另外，不同于蟻群算法解決TSP問(wèn)題屬于近似計(jì)算的范疇，A*算法屬于精確計(jì)算，當(dāng)節(jié)點(diǎn)數(shù)很少時(shí)，A*算法進(jìn)行路徑窮舉可以解決，但實(shí)際問(wèn)題中，節(jié)點(diǎn)數(shù)往往很多。例如，對(duì)于一個(gè)僅有16個(gè)城市的旅行商問(wèn)題，若采用A*算法進(jìn)行窮舉來(lái)求解問(wèn)題的最優(yōu)解，可行解共有15!/2=653 837 184 000個(gè)[11]。在1993年，使用當(dāng)時(shí)的工作站用窮舉法求解此問(wèn)題需時(shí)92小時(shí)。即使現(xiàn)在計(jì)算機(jī)速度快，面對(duì)復(fù)雜的問(wèn)題，效率仍然不夠。這就是所謂的“組合爆炸”，即所需要處理的數(shù)據(jù)因指數(shù)級(jí)的增長(zhǎng)而變得難以處理。所以科學(xué)家逐步尋找近似算法或者啟發(fā)式算法，目的是在合理的時(shí)間范圍內(nèi)找到可接受的最優(yōu)解。

總之，蟻群算法的優(yōu)勢(shì)在于解決TSP問(wèn)題的全局路徑規(guī)劃，而A*算法可以很好地解決TSP問(wèn)題中兩兩目標(biāo)區(qū)之間的局部路徑規(guī)劃[12]。為了提高算法可行性和運(yùn)行效率，本文考慮使用融合算法，即使用改進(jìn)A*算法快速計(jì)算各任務(wù)區(qū)之間距離[13]，然后使用蟻群算法規(guī)劃全局路徑[14]。

3 基于改進(jìn)三次B樣條法的路徑平滑處理

3.1 平滑策略

在柵格地圖中，規(guī)劃路徑由柵格中心點(diǎn)連線組成，這導(dǎo)致A*算法生成的路徑存在轉(zhuǎn)折拐點(diǎn)多的問(wèn)題，客觀上給無(wú)人機(jī)運(yùn)動(dòng)增加了多余路徑長(zhǎng)度，且不符合無(wú)人機(jī)的動(dòng)力學(xué)原理(無(wú)人機(jī)存在最大轉(zhuǎn)彎角等)。本文選擇改進(jìn)的三次B樣條方法對(duì)規(guī)劃路徑進(jìn)行平滑處理，即先使用雙向插點(diǎn)法處理路徑，再使用三次B樣條法平滑路徑。

3.2 雙向插點(diǎn)法

雙向插點(diǎn)法核心思想是在Floyd算法的基礎(chǔ)上，運(yùn)用雙向優(yōu)化的理念，刪除冗余節(jié)點(diǎn)，設(shè)置安全距離，以最大程度減少路徑拐點(diǎn)。在優(yōu)化中，設(shè)置安全距離，通過(guò)比較威脅區(qū)到路徑的垂直距離與設(shè)置的安全距離的關(guān)系來(lái)判斷路徑的安全性。如圖10，設(shè)路徑節(jié)點(diǎn)S坐標(biāo)為(xs,ys)，T坐標(biāo)為(xt,yt)。威脅區(qū)幾何中點(diǎn)O坐標(biāo)(xo,yo)；設(shè)柵格邊長(zhǎng)為d；距離OA為O到線段ST之間的垂線距離，記為d2；線段OB為O到線段ST縱向距離，記為l；夾角α為線段ST與水平方向夾角；記外接圓半徑為r。

圖10 安全距離設(shè)置

則有：

(7)

設(shè)置安全距離為D(D為設(shè)置的以O(shè)為起點(diǎn)的線段長(zhǎng)度，D>r),以保證處理后的路徑不進(jìn)入威脅區(qū)，即將D與d2進(jìn)行比較：如d2≤D，則該路徑不可被選擇。如d2>D,則該路徑可被選擇[15]。

雙向插點(diǎn)法具體步驟如圖11所示。

圖11 雙向插值法

步驟1：對(duì)路徑中同一線段上的冗余點(diǎn)進(jìn)行刪除，只保持路徑轉(zhuǎn)折前的起點(diǎn)S、下一個(gè)目標(biāo)點(diǎn)T。S→N1→N2→N3→N4→N5→N7→T刪除冗余點(diǎn)后的路徑為S→N2→N3→N4→T。

步驟2：從路徑起始點(diǎn)S起算，在保留的Ni、Nj之間每步取一節(jié)點(diǎn)，步長(zhǎng)記為q，判斷取得節(jié)點(diǎn)與上一節(jié)點(diǎn)之間是否存在威脅區(qū)域，并通過(guò)公式(7)計(jì)算d2，判斷d2與D的大??；如果威脅區(qū)域在安全距離之外，則選擇該節(jié)點(diǎn)為路徑節(jié)點(diǎn)；否則不予選擇。如圖所示，處理之后的路徑為S→N6→T。

步驟3：從目標(biāo)點(diǎn)T方向出發(fā)，反方向進(jìn)行取點(diǎn)判斷，如圖所示，處理后得到S→N8→T。

3.3 三次B樣條曲線優(yōu)化

B樣條曲線常用于路徑規(guī)劃的平滑，其具有針對(duì)局部路徑修改的特點(diǎn)，并使用逼近多邊形的方法從而獲得曲線優(yōu)化。結(jié)合前述雙向插點(diǎn)法，B樣條曲線優(yōu)化的路徑會(huì)更為平滑[17]。B樣條曲線實(shí)際是貝塞爾曲線的一種特例，與貝塞爾曲線相比，B樣條曲線在保留貝塞爾曲線全部?jī)?yōu)點(diǎn)的同時(shí)，又克服了其缺乏局部性質(zhì)、連續(xù)性較差等缺點(diǎn)，是路徑平滑常用的數(shù)學(xué)工具。其核心思想是通過(guò)控制點(diǎn)對(duì)路徑軌跡進(jìn)行n次B樣條曲線處理。

廣義的樣條函數(shù)定義為：

給定一組平面上頂點(diǎn)(xi,yi)(i=0,1,…,n)，并設(shè)在區(qū)間[a,b]上的Δ：a=x0

1)在每個(gè)小區(qū)間[xi-1,xi](i=1,2,…,n)內(nèi)，S(x)是具有K階或K階以上連續(xù)函數(shù)。

2)在xi(i=1,2,…,n-1)處成立。

則對(duì)于三次樣條函數(shù)，現(xiàn)在假設(shè)在區(qū)間[a,b]上給定一個(gè)分割Δ：a=x0

1)在每個(gè)小區(qū)間[xi-1,xi](i=1,2,…,n)內(nèi)，S(x)是三次多項(xiàng)式函數(shù)。

2)在xi(i=1,2,…,n-1)處成立：

S(k)(xi-0)=S(k)(xi-0),k=0,1,2

(8)

即小區(qū)間上的三次多項(xiàng)式函數(shù)，在拼接點(diǎn)處xi具有二階連續(xù)拼接。

3)滿足條件yi=S(xi)，i=0,1,…,n

下面對(duì)B樣條曲線進(jìn)行定義，給定m+n+1個(gè)平面或空間頂點(diǎn)(即控制點(diǎn))Pi(i=0,1,…,m+n),稱為n次參數(shù)曲線段：

(9)

其頂點(diǎn)Pi所組成的多邊形稱為B樣條曲線的特征多邊形。其中，基函數(shù)Gi,n(t)定義為：

(10)

其中:t∈[0,1],i=0,1,…,n。

取n=3，則有三次B樣條曲線的基函數(shù)如下：

(11)

將公式(11)代入式(9)中可得：

P(x)=

(12)

將公式(12)以矩陣形式表示，則可得三次B樣條曲線段P0，3(t)為：

(13)

Pi頂點(diǎn)位置定義為：

(14)

(15)

利用上述公式可得滿足三次B樣條的控制點(diǎn)及優(yōu)化曲線。平滑結(jié)果如圖12所示，圖中虛線即為處理后的實(shí)際軌跡。

圖12 三次B樣條曲線優(yōu)化

4 算法流程

本文融合算法結(jié)構(gòu)如圖13，步驟如下。

圖13 算法流程

步驟1:初始化柵格地圖，并設(shè)定n個(gè)目標(biāo)區(qū)域。

步驟2:基于改進(jìn)A*算法進(jìn)行各目標(biāo)區(qū)之間路徑規(guī)劃，得到任意兩個(gè)目標(biāo)區(qū)之間的最短距離。

步驟3:初始化蟻群算法各參數(shù)。令時(shí)間t=0和循環(huán)次數(shù)Nc=0，設(shè)置最大循環(huán)次數(shù)Nmax，將m個(gè)螞蟻置于n個(gè)目標(biāo)區(qū)上，令有向圖上每條邊(i，j)的初始信息素τij(t)=c，其中c表示常數(shù)，且初始時(shí)刻Δτij(0)=0。

步驟4:循環(huán)次數(shù)Nc=Nc+1。

步驟5:螞蟻禁忌表索引號(hào)k=1。

步驟6:螞蟻個(gè)體根據(jù)狀態(tài)轉(zhuǎn)移概率公式(2)計(jì)算的概率選擇下一個(gè)目標(biāo)區(qū)j并前進(jìn)，j∈ak。

步驟7:修改禁忌表指針，即選擇之后螞蟻移動(dòng)到新的目標(biāo)區(qū)，并把該目標(biāo)區(qū)移動(dòng)該螞蟻個(gè)體的禁忌表中[18]。

步驟8:所有螞蟻完成移動(dòng)，記錄本次最佳路線。

步驟9:根據(jù)公式(3)和公(4)更新每條路徑上的信息素。

步驟10:若滿足結(jié)束條件，即如果循環(huán)次數(shù)Nc≥G，則循環(huán)結(jié)束并得到最佳遍歷路徑；否則清空禁忌表轉(zhuǎn)到步驟4。

步驟11:使用三次B樣條與插點(diǎn)法相結(jié)合的方法進(jìn)行路徑平滑，最后輸出最佳路徑。

5 仿真實(shí)驗(yàn)與分析

為驗(yàn)證算法的性能，擬在MATLAB2018b環(huán)境中進(jìn)行仿真實(shí)驗(yàn)。仿真選擇基本蟻群算法(ACO)、蟻群-A*算法(ACO-A*)、蟻群-A*改進(jìn)算法(ACO-IA*)和本文融合算法(ACO-MA*)。首先建立30×30 km的柵格地圖，并在地圖中設(shè)立20個(gè)目標(biāo)區(qū)域進(jìn)行實(shí)驗(yàn)，目標(biāo)區(qū)域如圖中淺色區(qū)域所示。參數(shù)初始化設(shè)置如下：螞蟻數(shù)量m=30,目標(biāo)區(qū)域數(shù)量n=20，最大迭代次數(shù)200,信息素啟發(fā)因子α=1，啟發(fā)函數(shù)重要度因子β=5，ρ=0.3，Q=50，d=1 km，D=0.8 km，q=0.1 km。仿真結(jié)果如圖14所示。

圖14 實(shí)驗(yàn)對(duì)比情況

從表1中可以看出，基本蟻群算法(ACO)、蟻群-A*算法(ACO-A*)、蟻群-A*改進(jìn)算法(ACO-IA*)和本文融合算法(ACO-MA*)都能順利獲得路徑。但對(duì)比而言，ACO算法處理時(shí)間最長(zhǎng)，且路徑轉(zhuǎn)角和路徑靠近威脅區(qū)次數(shù)最多，在實(shí)際應(yīng)用中，無(wú)人機(jī)將消耗更多燃料，且無(wú)人機(jī)生存面臨更大威脅。ACO-A*算法相比ACO算法路徑長(zhǎng)度增加了1 km，但轉(zhuǎn)角次數(shù)減少了12次，占比19.3%。處理時(shí)間顯著減少了24.33秒，占比92.7%。路徑靠近威脅區(qū)次數(shù)減少了2次，占比22.2%。ACO-IA*算法生成的路徑相比ACO-A*算法生成的路徑，路徑長(zhǎng)度、轉(zhuǎn)角次數(shù)和處理時(shí)間幾乎相同，但有效避免了路徑靠近威脅區(qū)，顯著增加了無(wú)人機(jī)路徑安全性[19]。而ACO-MA*算法相比ACO算法路徑長(zhǎng)度減少了6.13 km，占比4.2%。轉(zhuǎn)角次數(shù)減少了43次，占比69.4%。處理時(shí)間減少了24.3秒，占比92.9%，同時(shí)有效保證了路徑的安全性。且ACO-MA*算法相比于ACO-A*算法和ACO-IA*算法，除了處理時(shí)間有略微增加，各項(xiàng)數(shù)據(jù)指標(biāo)均有明顯優(yōu)化?？紤]到本地圖僅是30×30 km的柵格地圖，如果地圖區(qū)域更大，融合算法的性能將更有顯著提升。如圖13所示，融合算法相比其他算法也更有良好的收斂性。

表1 實(shí)驗(yàn)數(shù)據(jù)對(duì)比

圖15 收斂性對(duì)比情況

6 結(jié)束語(yǔ)

本文針對(duì)無(wú)人機(jī)多目標(biāo)區(qū)域遍歷偵察問(wèn)題，提出一種高效的遍歷路徑規(guī)劃融合算法，對(duì)無(wú)人機(jī)多任務(wù)區(qū)遍歷路徑進(jìn)行快速規(guī)劃。針對(duì)傳統(tǒng)的蟻群算法和A*算法在解決TSP路徑規(guī)劃問(wèn)題上均有缺陷的情況,通過(guò)兩種算法的改進(jìn)與融合，使新算法相比于單個(gè)或其他融合算法有明顯優(yōu)勢(shì),證明了該算法的有效性和實(shí)用性。預(yù)計(jì)本文的研究成果將幫助智能無(wú)人機(jī)或決策者在復(fù)雜戰(zhàn)場(chǎng)環(huán)境中快速和高效地作出決策，提高無(wú)人機(jī)生存能力和偵察效益，更好地發(fā)揮無(wú)人作戰(zhàn)力量的優(yōu)勢(shì)[20]。