摘要:隨著無人機(jī)技術(shù)的快速發(fā)展,多無人機(jī)協(xié)同作戰(zhàn)成為無人機(jī)系統(tǒng)的重要發(fā)展方向。在多無人機(jī)協(xié)同作戰(zhàn)中,任務(wù)分配與路徑規(guī)劃是2個關(guān)鍵問題,其質(zhì)量直接影響著整個系統(tǒng)的作戰(zhàn)效能。文章針對多無人機(jī)協(xié)同作戰(zhàn)中的任務(wù)分配與路徑規(guī)劃問題展開研究,建立多無人機(jī)協(xié)同作戰(zhàn)的數(shù)學(xué)模型,對問題進(jìn)行形式化描述。文章提出一種基于混合整數(shù)規(guī)劃的任務(wù)分配算法和一種基于改進(jìn)A*算法的路徑規(guī)劃算法。通過仿真實(shí)驗(yàn)對所提出算法的有效性進(jìn)行了驗(yàn)證,與其他經(jīng)典算法進(jìn)行對比分析。實(shí)驗(yàn)結(jié)果表明,文章提出的任務(wù)分配與路徑規(guī)劃算法能夠有效提高多無人機(jī)協(xié)同作戰(zhàn)效能。
關(guān)鍵詞:多無人機(jī)協(xié)同作戰(zhàn);任務(wù)分配;路徑規(guī)劃;混合整數(shù)規(guī)劃;改進(jìn)A*算法
中圖分類號:G305 文獻(xiàn)標(biāo)志碼:A
0 引言
無人機(jī)技術(shù)的迅速發(fā)展為現(xiàn)代戰(zhàn)爭帶來了革命性變化,多無人機(jī)協(xié)同作戰(zhàn)更是未來作戰(zhàn)樣式的重要發(fā)展方向。在多無人機(jī)協(xié)同作戰(zhàn)中,任務(wù)分配與路徑規(guī)劃是2個關(guān)鍵問題,其質(zhì)量直接影響著整個作戰(zhàn)系統(tǒng)的效能。本文針對上述問題,提出了一種基于混合整數(shù)規(guī)劃與改進(jìn)A*算法的2個階段求解框架。首先,構(gòu)建多無人機(jī)任務(wù)分配的混合整數(shù)規(guī)劃模型,求解最優(yōu)的任務(wù)分配方案;然后,利用改進(jìn)的A*算法為每架無人機(jī)規(guī)劃一條安全、高效的飛行路徑。實(shí)驗(yàn)結(jié)果表明,本文所提出的算法在多種場景下都取得了優(yōu)異的性能,為多無人機(jī)協(xié)同作戰(zhàn)提供了一種高效可行的解決方案。
1 多無人機(jī)協(xié)同作戰(zhàn)問題描述
多無人機(jī)協(xié)同作戰(zhàn)問題研究的是在復(fù)雜環(huán)境下,如何高效地利用多架無人機(jī)完成一系列作戰(zhàn)任務(wù)。具體而言,現(xiàn)有一組需要執(zhí)行的任務(wù)和一組可用的無人機(jī),問題就在于滿足諸如無人機(jī)性能、任務(wù)時間窗口、任務(wù)優(yōu)先級等各種約束條件的前提下,為每個任務(wù)合理分配執(zhí)行無人機(jī),為每架參與作戰(zhàn)的無人機(jī)規(guī)劃出一條安全高效的飛行路徑,使得整個作戰(zhàn)系統(tǒng)的任務(wù)完成效率達(dá)到最優(yōu)。
問題的輸入包括任務(wù)集合及其位置、執(zhí)行時間窗口、優(yōu)先級等屬性信息,無人機(jī)集合及其飛行速度、航程,載荷能力等性能參數(shù),無人機(jī)之間的通信拓?fù)潢P(guān)系以及作戰(zhàn)環(huán)境的地圖、氣象、威脅目標(biāo)分布等信息。輸出則是每個任務(wù)的執(zhí)行無人機(jī)分配方案,每架無人機(jī)的詳細(xì)飛行路線,由一系列航路點(diǎn)構(gòu)成。
在建模過程中,研究人員建立了多無人機(jī)協(xié)同作戰(zhàn)問題的混合整數(shù)規(guī)劃模型。該模型的目標(biāo)函數(shù)是最小化整個任務(wù)執(zhí)行過程中,各架無人機(jī)完成所有分配任務(wù)的時間最大值,從而使任務(wù)執(zhí)行時間更加均衡[1]。約束條件保證了每個任務(wù)只能由一架無人機(jī)執(zhí)行,每架無人機(jī)的任務(wù)執(zhí)行時間不超過其可用時間,每個任務(wù)必須在規(guī)定的時間窗口內(nèi)完成,無人機(jī)的燃料消耗限制以及防止無人機(jī)相互碰撞的空間距離約束等。求解這個混合整數(shù)規(guī)劃模型,就可以得到最優(yōu)或近似最優(yōu)的任務(wù)分配方案和無人機(jī)路徑規(guī)劃方案。
2 任務(wù)分配算法設(shè)計(jì)
2.1 基于混合整數(shù)規(guī)劃的任務(wù)分配模型
在上節(jié)中,本文建立了多無人機(jī)協(xié)同作戰(zhàn)問題的混合整數(shù)規(guī)劃模型。該模型考慮了任務(wù)時間窗口、無人機(jī)資源約束等因素,是一種典型的任務(wù)分配模型。在此基礎(chǔ)上,本文設(shè)計(jì)了高效的任務(wù)分配算法。為進(jìn)一步提高模型的適用性和求解效率,可以考慮引入以下技巧。
(1)預(yù)處理:在求解之前,通過一些預(yù)處理技術(shù)(如約束傳播、冗余約束刪除等)來簡化模型,縮小變量取值范圍。
(2)線性松弛:將混合整數(shù)規(guī)劃模型(Mixed Integer Programming,MIP)松弛為線性規(guī)劃模型,快速獲得一個下界,用于指導(dǎo)Branch and Bound搜索。
(3)cutting plane:在Branch and Bound搜索過程中,動態(tài)生成割平面,減小搜索空間。
(4)啟發(fā)式方法:利用問題的特點(diǎn),設(shè)計(jì)啟發(fā)式算法生成高質(zhì)量的初始解,加速收斂速度。
(5)分解算法:將大規(guī)模問題分解為多個小規(guī)模子問題分別求解,再合并結(jié)果。
引入這些技巧后,混合整數(shù)規(guī)劃模型的求解性能可以得到顯著提升。
2.2 任務(wù)分配算法流程
基于2.1節(jié)的混合整數(shù)規(guī)劃模型,本文設(shè)計(jì)了一種兩階段任務(wù)分配算法。算法的基本流程如下。
輸入:任務(wù)集合T,無人機(jī)集合U,無人機(jī)性能參數(shù),任務(wù)屬性參數(shù)。
輸出:任務(wù)分配方案X。
第一階段:初始化。
(1)根據(jù)無人機(jī)性能參數(shù)和任務(wù)屬性參數(shù),計(jì)算無人機(jī)執(zhí)行每個任務(wù)所需的代價cij。
(2)根據(jù)任務(wù)時間窗口和無人機(jī)位置,計(jì)算最早到達(dá)的時間矩陣D。
(3)生成初始任務(wù)分配方案X0,可采用最短任務(wù)優(yōu)先、最近無人機(jī)優(yōu)先等簡單規(guī)則。
(4)利用啟發(fā)式算法(如模擬退火、遺傳算法等)對X0進(jìn)行改進(jìn),得到改進(jìn)解X1。
第二階段:求解混合整數(shù)規(guī)劃。
(1)以X1為初始解構(gòu)建MIP。
(2)設(shè)置求解器參數(shù)(如時間限制、Gap限制等),調(diào)用求解器求解MIP。
(3)若在時間限制內(nèi)得到最優(yōu)解X*,則輸出X*;否則輸出當(dāng)前最優(yōu)可行解。
后處理:
(1)對任務(wù)分配方案X*進(jìn)行可視化呈現(xiàn)。
(2)統(tǒng)計(jì)任務(wù)完成率、平均任務(wù)延遲等性能指標(biāo)。
算法的偽代碼如下:
以上算法在初始化階段引入啟發(fā)式方法,生成高質(zhì)量可行解,加快MIP的求解速度;在求解階段,利用MIP求解器得到最優(yōu)解或近似最優(yōu)解;后處理階段,對結(jié)果進(jìn)行可視化呈現(xiàn)和性能評估。
3 路徑規(guī)劃算法設(shè)計(jì)
3.1 改進(jìn)的A*算法
本文在標(biāo)準(zhǔn)A*算法的基礎(chǔ)上,引入自適應(yīng)啟發(fā)函數(shù)、多啟發(fā)函數(shù)融合、搜索空間動態(tài)調(diào)整、雙向搜索和局部路徑優(yōu)化等策略,以進(jìn)一步提高算法在復(fù)雜環(huán)境下的搜索效率和路徑質(zhì)量[2]。
3.2 無人機(jī)路徑規(guī)劃模型
為了使用改進(jìn)的A*算法進(jìn)行無人機(jī)路徑規(guī)劃,需要將問題轉(zhuǎn)化為圖搜索問題。首先,將無人機(jī)的飛行環(huán)境離散化為一個三維網(wǎng)格地圖,每個網(wǎng)格代表一個可能的航路點(diǎn)。無人機(jī)在相鄰網(wǎng)格之間飛行,構(gòu)成了一條飛行路徑?,F(xiàn)定義以下符號:
(1)s:起點(diǎn),無人機(jī)的初始位置。
(2)g:目標(biāo)點(diǎn),無人機(jī)的目標(biāo)位置。
(3)N(n):節(jié)點(diǎn)n的相鄰節(jié)點(diǎn)集合。
(4)c(n,n′):無人機(jī)從節(jié)點(diǎn)n飛行到節(jié)點(diǎn)n′的代價。
(5)h(n):從節(jié)點(diǎn)n到目標(biāo)點(diǎn)的估計(jì)代價,即啟發(fā)函數(shù)值。
(6)f(n)=g(n)+h(n):節(jié)點(diǎn)n的估價函數(shù)值,g(n)為從起點(diǎn)到n的實(shí)際代價。
(7)d(n):節(jié)點(diǎn)n的飛行高度。
(8)t(n):節(jié)點(diǎn)n所處的威脅區(qū)域等級。
無人機(jī)路徑規(guī)劃問題可建模為加權(quán)有向圖上的最短路徑搜索問題,現(xiàn)做出以下定義:
(1)頂點(diǎn):每個網(wǎng)格對應(yīng)一個頂點(diǎn),起點(diǎn)s和目標(biāo)點(diǎn)g也是2個特殊頂點(diǎn)。
(2)邊:若2個網(wǎng)格相鄰,則它們對應(yīng)的頂點(diǎn)之間存在一條有向邊。
(3)邊權(quán):無人機(jī)在2個相鄰網(wǎng)格之間飛行的代價,與飛行距離、高度變化量、威脅區(qū)域等級等因素有關(guān)。
在該模型下,無人機(jī)路徑規(guī)劃問題轉(zhuǎn)化為在加權(quán)有向圖中,尋找一條從起點(diǎn)s到目標(biāo)點(diǎn)g的最小代價路徑。
3.3 路徑規(guī)劃算法流程
基于3.1節(jié)的改進(jìn)A*算法和3.2節(jié)的無人機(jī)路徑規(guī)劃模型,本文設(shè)計(jì)了一種無人機(jī)路徑規(guī)劃算法。算法的基本流程如下。
輸入:三維網(wǎng)格地圖Map,起點(diǎn)s,目標(biāo)點(diǎn)g,無人機(jī)性能參數(shù)。
輸出:一條從s到g的飛行路徑Path。
算法流程:
(1)初始化:將起點(diǎn)s加入開放列表OpenList,計(jì)算f(s)。
(2)迭代搜索:while OpenList不為空:從OpenList中取出f值最小的節(jié)點(diǎn)n。if n是目標(biāo)點(diǎn)g:返回路徑Path。將n加入閉合列表ClosedList。for each n′∈N(n):if n′在ClosedList中:continue計(jì)算g(n′)、h(n′)、f(n′)。if n′不在OpenList中:將n′加入OpenList,將n記為n′的父節(jié)點(diǎn)[3]。else if g(n′)<n′的原g值:更新n′的g值和f值,將n記為n′的父節(jié)點(diǎn)。
(3)路徑提取:if找到目標(biāo)點(diǎn)g:從g開始,沿著父節(jié)點(diǎn)指針逆向追蹤,得到一條從s到g的路徑Path。對Path進(jìn)行局部優(yōu)化,得到最終路徑。else:報(bào)告搜索失敗。
其中,f(n)的計(jì)算公式為:
f(n)=g(n)+w1×h1(n)+w2×h2(n)+w3×h3(n)+...
其中,h1(n)、h2(n)、h3(n)...為多個啟發(fā)函數(shù),分別估計(jì)節(jié)點(diǎn)n到目標(biāo)點(diǎn)的距離、飛行高度差、威脅區(qū)域等級等;w1、w2、w3...為對應(yīng)的權(quán)重系數(shù),可根據(jù)無人機(jī)性能和任務(wù)需求動態(tài)調(diào)整。
6kjcFKvsAp8v5ScRv6mABSft/WllqIhoIp4aaKIWRD0=算法的偽代碼如下:
4 仿真實(shí)驗(yàn)與結(jié)果分析
4.1 實(shí)驗(yàn)環(huán)境與參數(shù)設(shè)置
實(shí)驗(yàn)在一臺配置為Intel Core i7處理器、16 GB內(nèi)存的計(jì)算機(jī)上進(jìn)行。仿真平臺基于C++語言開發(fā),可以靈活配置無人機(jī)數(shù)量、任務(wù)類型、地圖環(huán)境等參數(shù)。
實(shí)驗(yàn)中,本文考慮了以下幾種場景。
(1)小規(guī)模場景:10架無人機(jī),20個任務(wù),100×100的網(wǎng)格地圖。
(2)中規(guī)模場景:30架無人機(jī),50個任務(wù),200×200的網(wǎng)格地圖。
(3)大規(guī)模場景:50架無人機(jī),100個任務(wù),500×500的網(wǎng)格地圖。
無人機(jī)的飛行速度、航程、通信范圍等參數(shù)根據(jù)實(shí)際情況設(shè)置。任務(wù)的位置、優(yōu)先級、時間窗口等屬性隨機(jī)生成。地圖中包含不同高度的地形和若干威脅區(qū)域。
算法參數(shù)方面,混合整數(shù)規(guī)劃模型采用Gurobi求解器,時間限制設(shè)為300 s。A*算法的啟發(fā)函數(shù)權(quán)重通過網(wǎng)格搜索調(diào)優(yōu)得到[4]。每個場景下隨機(jī)生成30組測試數(shù)據(jù),取平均值作為算法的性能指標(biāo)。
4.2 任務(wù)分配算法實(shí)驗(yàn)結(jié)果
本文測試了基于混合整數(shù)規(guī)劃的任務(wù)分配算法在不同場景下的求解性能,與基于市場機(jī)制的分配算法、基于遺傳算法的分配算法進(jìn)行了對比。實(shí)驗(yàn)結(jié)果表明:
(1)混合整數(shù)規(guī)劃算法能夠在較短時間內(nèi)得到全局最優(yōu)解或近似最優(yōu)解,優(yōu)于另外2種算法。求解時間隨著問題規(guī)模的增大而增長。
(2)市場機(jī)制算法具有分布式特性,計(jì)算速度快,但解的質(zhì)量難以保證。
(3)遺傳算法的解質(zhì)量較高,但在大規(guī)模問題上的收斂速度較慢。
在小規(guī)模場景下,3種算法的性能差異不明顯。但在中大規(guī)模場景下,混合整數(shù)規(guī)劃算法的優(yōu)勢逐漸體現(xiàn)。例如:在50架無人機(jī)、100個任務(wù)的場景下,混合整數(shù)規(guī)劃算法的任務(wù)完成率比另外2種算法高出10%以上,而平均求解時間僅為180 s左右。
4.3 路徑規(guī)劃算法實(shí)驗(yàn)結(jié)果
實(shí)驗(yàn)測試了改進(jìn)A*算法在不同地圖環(huán)境下的路徑規(guī)劃性能,與標(biāo)準(zhǔn)A*算法、人工勢場法、RRT算法進(jìn)行了對比。實(shí)驗(yàn)結(jié)果表明:
(1)改進(jìn)A*算法能夠快速規(guī)劃出一條無碰撞、低威脅的飛行路徑。在同等條件下,其搜索效率比標(biāo)準(zhǔn)A*算法提高了50%以上。
(2)人工勢場法容易陷入局部最優(yōu),無法有效處理復(fù)雜地形。
(3)RRT算法能夠找到一條可行路徑,但路徑質(zhì)量不高且不具備最優(yōu)性。
對于不同復(fù)雜度的地圖,改進(jìn)A*算法都能在1 s內(nèi)得到一條高質(zhì)量飛行路徑。即使在500×500的大規(guī)模地圖上,其平均規(guī)劃時間也在5 s以內(nèi)。相比之下,標(biāo)準(zhǔn)A*算法常常需要幾十秒甚至更長時間。
多啟發(fā)函數(shù)融合策略和動態(tài)搜索空間調(diào)整策略是提升算法性能的關(guān)鍵。前者綜合考慮了無人機(jī)的飛行特性和環(huán)境信息,后者避免了不必要的搜索擴(kuò)展。實(shí)驗(yàn)表明,這2個策略使算法的收斂速度提高了1倍以上。此外,本文還測試了改進(jìn)A*算法應(yīng)對動態(tài)威脅的能力。通過實(shí)時更新地圖信息并重新規(guī)劃路徑,無人機(jī)能夠及時躲避突發(fā)威脅,保證飛行安全。
4.4 與其他算法的對比分析
本文提出的任務(wù)分配與路徑規(guī)劃算法,在多個場景下展現(xiàn)了優(yōu)異的性能。與基于市場機(jī)制和遺傳算法的任務(wù)分配方法相比,本文算法在解的質(zhì)量和求解效率方面都有明顯優(yōu)勢,尤其在大規(guī)模問題上。在路徑規(guī)劃方面,改進(jìn)的A*算法在搜索效率、路徑質(zhì)量等指標(biāo)上也優(yōu)于標(biāo)準(zhǔn)A*算法、人工勢場法和RRT算法[5]。本文算法之所以表現(xiàn)出色,主要在于其充分利用了問題的特點(diǎn),引入了多種優(yōu)化策略,如任務(wù)分配中的線性松弛和割平面技術(shù),路徑規(guī)劃中的多啟發(fā)函數(shù)融合等。兩階段協(xié)同優(yōu)化框架考慮了任務(wù)分配與路徑規(guī)劃的耦合關(guān)系,進(jìn)一步提升了算法整體性能。
5 結(jié)語
本文針對多無人機(jī)協(xié)同作戰(zhàn)中的任務(wù)分配與路徑規(guī)劃問題,提出了一種基于混合整數(shù)規(guī)劃和改進(jìn)A*算法的兩階段優(yōu)化求解方法。通過建立精確的數(shù)學(xué)模型,引入多種優(yōu)化策略,考慮任務(wù)分配與路徑規(guī)劃的耦合關(guān)系,本文算法能夠高效地解決多無人機(jī)協(xié)同作戰(zhàn)問題,為無人機(jī)的實(shí)際應(yīng)用提供了新的思路和方法。在未來的工作中,筆者將進(jìn)一步完善算法,提高其適應(yīng)復(fù)雜動態(tài)環(huán)境的能力,拓展其應(yīng)用場景,如考慮無人機(jī)的異構(gòu)性、引入在線學(xué)習(xí)機(jī)制等,以期為無人機(jī)技術(shù)和軍事應(yīng)用的發(fā)展作出更大貢獻(xiàn)。
參考文獻(xiàn)
[1]楊廣超,周傳睿,邢文革.海戰(zhàn)場無人機(jī)集群與反艦導(dǎo)彈協(xié)同作戰(zhàn)樣式與反制策略研究[J].戰(zhàn)術(shù)導(dǎo)彈技術(shù),2024(1):141-149.
[2]劉芳名,王凱.美軍有人戰(zhàn)機(jī)與無人機(jī)協(xié)同作戰(zhàn)研究[J].艦船電子工程,2023(12):14-18.
[3]侯典寧,孟凡凱,朱煉.直升機(jī)與無人機(jī)協(xié)同作戰(zhàn)研究[J].艦船電子工程,2023(10):6-8.
[4]毛雪玥,彭盛龍.基于協(xié)同作戰(zhàn)的無人機(jī)航路重規(guī)劃算法研究[J].艦船電子工程,2023(6):27-31,93.
[5]趙琳,呂科,郭靖,等.基于深度強(qiáng)化學(xué)習(xí)的無人機(jī)集群協(xié)同作戰(zhàn)決策方法[J].計(jì)算機(jī)應(yīng)用,2023(11):3641-3646.
Research on task allocation and path planning algorithms in Multi-UAV cooperative combat
Abstract: With the rapid development of UAV technology, multi-UAV cooperative operation has become an important development direction of UAV system. In multi-UAV cooperative operations, mission assignment and path planning are two key issues, and their quality directly affects the operational effectiveness of the whole system. This paper studies the task allocation and path planning in multi-UAV collaborative operation. The mathematical model of multi-UAV cooperative operation is established, and the problem is formally described. We propose a task assignment algorithm based on mixed integer programming and a path planning algorithm based on an improved A* algorithm. The effectiveness of the proposed algorithm is verified by simulation experiments and compared with other classical algorithms. The experimental results show that the task assignment and path planning algorithm can improve the effectiveness of multi-UAV cooperation.
Key words: multi-UAV collaboration; task assignment; path planning; mixed integer planning; improved A* algorithm