摘 要：

為滿足無人機(jī)群實(shí)時(shí)可交互的隊(duì)形變化和個(gè)性化表演需求，提出了一種基于分布式模型預(yù)測(cè)控制（DMPC）的無人機(jī)群離線軌跡生成新算法。首先對(duì)于無人機(jī)編隊(duì)時(shí)點(diǎn)對(duì)點(diǎn)隊(duì)形變化問題進(jìn)行數(shù)學(xué)建模并求解優(yōu)化問題。為分布式模型預(yù)測(cè)控制引入了一種新的按需防撞策略，提出了一種用于多無人機(jī)點(diǎn)對(duì)點(diǎn)過渡的快速DMPC算法，再結(jié)合智能的目標(biāo)點(diǎn)分配，在減少軌跡生成計(jì)算壓力的同時(shí)得到更高效的飛行軌跡。通過仿真與現(xiàn)有方法進(jìn)行了比較和性能評(píng)估，結(jié)果顯示所提方法顯著提升了軌跡生成的成功率、軌跡生成的速率和軌跡的飛行效率。該算法可以根據(jù)需求快速生成無人機(jī)群點(diǎn)對(duì)點(diǎn)隊(duì)形變化所需的高效飛行軌跡，滿足無人機(jī)群飛行表演的實(shí)時(shí)可交互性和觀眾的個(gè)性化需求。

關(guān)鍵詞：航跡規(guī)劃；模型預(yù)測(cè)控制；分布式機(jī)器人系統(tǒng)；碰撞避免；目標(biāo)點(diǎn)分配；無人機(jī)

中圖分類號(hào)：TP301"" 文獻(xiàn)標(biāo)志碼：A""" 文章編號(hào)：1001-3695（2024）12-010-3600-07

doi： 10.19734/j.issn.1001-3695.2024.04.0144

Real-time interactive unmanned aerial vehicle swarm formation method based on distributed model predictive control

Wang Zihenga， Li Yitaoa，b， Xiong Xingzhonga，b

（a.School of Automation amp; Information Engineering， b.Artificial Intelligence Key Laboratory of Sichuan Province， Sichuan University of Science amp; Engineering， Yibin Sichuan 643000， China）

Abstract：

To meet the real-time interactive formation changes and personalized performance requirements of drone swarms， this paper proposed a new offline trajectory generation algorithm based on distributed model predictive control （DMPC）. This method began with mathematical modeling of point-to-point formation changes in drone formations and solved the optimization problem. This paper introduced a new on-demand collision avoidance strategy for DMPC and proposed a rapid DMPC algorithm for multi-drone point-to-point transitions. By combining with intelligent target point allocation， the method reduced computational pressure while achieving more efficient flight trajectories. The study conducted simulations and compared the method with existing methods for performance evaluation. The results show that the proposed method significantly improves the success rate of trajectory generation， the rate of trajectory generation， and the efficiency of trajectory flight. The new algorithm quickly generates efficient flight trajectories for point-to-point formation changes in drone swarms， meeting the real-time interactivity and personalized needs of drone swarm flight performances.

Key words：trajectory planning; model predictive control; distributed robotics system; collision avoidance; target assignment; unmanned aerial vehicle （UAV）

0 引言

無人機(jī)編隊(duì)表演在各類大中小型演出中扮演了日益重要的角色，隨著觀眾對(duì)演出個(gè)性化需求的不斷增長(zhǎng)，實(shí)時(shí)可交互式無人機(jī)表演成為無人機(jī)表演領(lǐng)域未來重要的發(fā)展方向。為了滿足觀眾個(gè)性化需求，需要提升無人機(jī)編隊(duì)表演隊(duì)形變化過程中的軌跡生成效率，讓無人機(jī)群能夠快速反應(yīng)觀眾的個(gè)性化需求調(diào)整隊(duì)形，并且保證飛行的安全高效。

無人機(jī)的隊(duì)形變化可以被分解為多無人機(jī)點(diǎn)對(duì)點(diǎn)轉(zhuǎn)換的任務(wù)。多無人機(jī)點(diǎn)到拓?fù)潼c(diǎn)轉(zhuǎn)換問題主要有標(biāo)記無人機(jī)問題和未標(biāo)記無人機(jī)問題兩種變體。前者每個(gè)無人機(jī)都有一個(gè)固定的最終位置，且不能與另一個(gè)無人機(jī)進(jìn)行交換［1］；后者目標(biāo)可以自由地被分配給無人機(jī)，以減輕隊(duì)形變化問題的復(fù)雜性［2］。

對(duì)于解決多無人機(jī)的航跡規(guī)劃問題，常見的方法是將公式轉(zhuǎn)換為優(yōu)化問題。最早提出的技術(shù)之一是依賴混合整數(shù)線性規(guī)劃［3］和混合二次規(guī)劃（MIQP）［4］，這些集中式的方法［5］有著很好的理論特性，例如最優(yōu)性保證，但這些方法在計(jì)算上是較為復(fù)雜的，不適用于大型的無人機(jī)組，且難以滿足軌跡生成的實(shí)時(shí)性。

最近，序列凸規(guī)劃（SCP）［6］已實(shí)現(xiàn)了比MILP更快的處理速度。SCP用于計(jì)算無人機(jī)組的最佳能量軌跡，該算法對(duì)小無人機(jī)群很有用，但它不能很好地應(yīng)對(duì)大型無人機(jī)群軌跡生成的情況［7，8］。文獻(xiàn)［9，10］提出了該算法的解耦版本，以次優(yōu)解決方案為代價(jià)提供了更好的可擴(kuò)展性。然而，所需的解耦將先前解決的無人機(jī)軌跡轉(zhuǎn)換為后續(xù)無人機(jī)的障礙導(dǎo)致了順序貪婪策略，隨著無人機(jī)數(shù)量的增加成功率降低。

分布式優(yōu)化方法可以有效地進(jìn)行成對(duì)的無人機(jī)距離約束［11］，此外，計(jì)算工作量因?yàn)榉植荚诟鱾€(gè)無人機(jī)上，與集中式方法相比減少了計(jì)算量。最優(yōu)相互碰撞避免（ORCA）利用速度障礙法來保證完整［12］和非完整［13］無人機(jī)的無碰撞軌跡，雖然可以證明是安全的，但該方法可能過于保守，因?yàn)樗鼈冊(cè)O(shè)定了時(shí)間范圍內(nèi)的恒定速度剖面?；趧?shì)場(chǎng)的技術(shù)已被用于分布式機(jī)器人系統(tǒng)的沖突避免［14，15］，其中文獻(xiàn)［16］提出的基于人工勢(shì)場(chǎng)的規(guī)劃算法在無人機(jī)實(shí)時(shí)路徑規(guī)劃中具有良好的可行性和有效性，使無人機(jī)能夠有效避開障礙物，同時(shí)路徑長(zhǎng)度以及耗費(fèi)時(shí)間更短，但在應(yīng)對(duì)大型無人機(jī)群的環(huán)境下容易出現(xiàn)鎖死。分布式模型預(yù)測(cè)控制（DMPC）［17］已用于編隊(duì)控制［18，19］等協(xié)調(diào)任務(wù)，但未明確用于點(diǎn)對(duì)點(diǎn)隊(duì)形變化，特別有趣的是DMPC的同步實(shí)現(xiàn)［20］，其中無人機(jī)同時(shí)更新其預(yù)測(cè)，通過并行計(jì)算減少運(yùn)行時(shí)間。

綜上所述，在無人機(jī)編隊(duì)表演中，軌跡生成和隊(duì)形變化過程的現(xiàn)有方法在處理大型無人機(jī)群的軌跡生成時(shí)存在計(jì)算復(fù)雜性和實(shí)時(shí)性不足的問題。本文提出一種基于分布式模型預(yù)測(cè)控制的新算法，以應(yīng)對(duì)觀眾個(gè)性化需求和快速隊(duì)形變化的要求。本文的主要貢獻(xiàn)在于提出了一種適用于多無人機(jī)點(diǎn)對(duì)點(diǎn)隊(duì)形變化的快速DMPC算法，通過分布式優(yōu)化方法和智能目標(biāo)點(diǎn)分配提高了軌跡生成的效率和實(shí)時(shí)性。

1 系統(tǒng)模型

實(shí)時(shí)可交互式無人機(jī)表演系統(tǒng)，通過無人機(jī)編隊(duì)技術(shù)和先進(jìn)的控制算法，不僅能夠提供傳統(tǒng)的視覺表演效果，還能實(shí)現(xiàn)與觀眾的實(shí)時(shí)交互，為觀眾帶來前所未有的表演體驗(yàn)。這種表演系統(tǒng)在彩燈會(huì)、無人機(jī)公司的展廳展示、室內(nèi)外展會(huì)演出等場(chǎng)合具有廣泛的應(yīng)用前景。例如在一場(chǎng)室內(nèi)展會(huì)中，無人機(jī)可以根據(jù)觀眾的實(shí)時(shí)反饋通過移動(dòng)設(shè)備的控制信息改變編隊(duì)的形狀、飛行軌跡和燈光效果，從而實(shí)現(xiàn)高度定制化的表演效果。

設(shè)計(jì)這樣一個(gè)系統(tǒng)需要解決幾個(gè)關(guān)鍵問題，即如何確保無人機(jī)的安全飛行、如何實(shí)現(xiàn)無人機(jī)之間的精準(zhǔn)協(xié)同控制、如何與觀眾的交互指令實(shí)時(shí)同步滿足觀眾個(gè)性化需求，以及如何在保證表演效果的同時(shí)簡(jiǎn)化系統(tǒng)的搭建和操作流程。

其關(guān)鍵問題源于無人機(jī)編隊(duì)在無人機(jī)表演中需要進(jìn)行快速高效的隊(duì)形變化。實(shí)時(shí)可交互無人機(jī)表演要求無人機(jī)編隊(duì)能安全高效地完成任務(wù)，其中關(guān)鍵挑戰(zhàn)是如何快速生成安全、高效的飛行軌跡?？焖俣_的軌跡規(guī)劃直接影響無人機(jī)編隊(duì)的執(zhí)行效率和安全性以及無人機(jī)表演的交互實(shí)時(shí)性。解決這個(gè)問題需要對(duì)軌跡生成算法進(jìn)行改進(jìn)，能夠及時(shí)處理環(huán)境信息，快速作出決策。本文解決方案是先對(duì)無人機(jī)的目標(biāo)航點(diǎn)進(jìn)行智能分配并采用DMPC算法結(jié)合帶有軟約束的按需碰撞避免機(jī)制，通過分布式計(jì)算提高處理速度，實(shí)現(xiàn)快速軌跡生成。DMPC算法允許每架無人機(jī)根據(jù)當(dāng)前狀態(tài)和周圍環(huán)境獨(dú)立計(jì)算其軌跡；同時(shí)考慮到與其他無人機(jī)的相互作用，確保整個(gè)編隊(duì)的協(xié)同和碰撞避免，由此構(gòu)建起分布式機(jī)器人系統(tǒng)，從而實(shí)現(xiàn)快速、安全且高效的軌跡規(guī)劃。

1.1 可交互無人機(jī)系統(tǒng)

設(shè)計(jì)的可交互無人機(jī)系統(tǒng)如圖1所示，地面控制臺(tái)將用戶規(guī)劃的目標(biāo)圖案轉(zhuǎn)換為無人機(jī)的目標(biāo)航點(diǎn)并通過軌跡生成算法快速生成每架無人機(jī)對(duì)應(yīng)的飛行軌跡并發(fā)送給無人機(jī)，無人機(jī)群跟蹤預(yù)定好的軌跡完成無人機(jī)表演。針對(duì)無人機(jī)隊(duì)形變化所需要的飛行軌跡進(jìn)行快速高效的生成，并且所生成的無人機(jī)軌跡可以保證無人機(jī)群的相互安全以及飛行的高效性，以此讓無人機(jī)群的編隊(duì)表演滿足與觀眾的實(shí)時(shí)交互。系統(tǒng)得到觀眾所需個(gè)性化的編隊(duì)需求時(shí)通過軌跡生成算法即可實(shí)時(shí)生成隊(duì)形變化所需軌跡，無人機(jī)群便可以根據(jù)它們各自的軌跡安全高效地完成無人機(jī)表演。

圖2展示了50個(gè)無人機(jī)進(jìn)行隊(duì)形變換的場(chǎng)景，圖2（a）為無人機(jī)群的初始隊(duì)形，圖2（b）為無人機(jī)群的目標(biāo)隊(duì)形。其中圓圈表示無人機(jī)的初始位置，菱形表示無人機(jī)的目標(biāo)位置。根據(jù)無人機(jī)的初始位置對(duì)目標(biāo)位置進(jìn)行合理匹配并快速生成每架無人機(jī)的飛行軌跡，以此快速高效地完成隊(duì)形變化。

通過這樣的設(shè)計(jì)，本系統(tǒng)不僅能夠滿足專業(yè)演出的需要，也為廣大無人機(jī)愛好者提供了一個(gè)易于操作、功能豐富的表演工具，大大拓展了無人機(jī)的應(yīng)用場(chǎng)景，增強(qiáng)了無人機(jī)表演的實(shí)時(shí)互動(dòng)性和觀賞性。

1.2 基礎(chǔ)問題建模

在多無人機(jī)隊(duì)形變化飛行中需要生成無碰撞軌跡，在給定的時(shí)間內(nèi)，根據(jù)無人機(jī)的狀態(tài)、物理約束和碰撞約束驅(qū)動(dòng)N架無人機(jī)從初始位置到最終位置?；A(chǔ)問題建模的目標(biāo)是離線生成這樣的軌跡。

a）無人機(jī)基礎(chǔ)建模。無人機(jī)在Euclid ExtraaBp3中被建模，擁有雙積分動(dòng)力學(xué)，四旋翼無人機(jī)的簡(jiǎn)化模型可以用于實(shí)現(xiàn)更快的計(jì)算。使用pi［k］、vi［k］和ai［k］表示第i個(gè)無人機(jī)在時(shí)間步長(zhǎng)k處的離散化x、y、z坐標(biāo)位置、速度和加速度信息，再結(jié)合每個(gè)離散時(shí)間步長(zhǎng)的持續(xù)時(shí)間h，運(yùn)動(dòng)學(xué)方程可以定義為

pi［k+1］=pi［k］+hvi［k］+h22ai［k］（1）

vi［k+1］=vi［k］+hai［k］（2）

b）無人機(jī)物理約束。約束無人機(jī)的運(yùn)動(dòng)以滿足它的物理特性，首先無人機(jī)的運(yùn)動(dòng)能力是有極限的，這與它的最大和最小加速度相關(guān)：

amin≤ai［k］≤amax（3）

其次，無人機(jī)的飛行范圍必須要控制在一定范圍內(nèi)，加入了飛行范圍約束：

pmin≤pi［k］≤pmax（4）

c）無人機(jī)碰撞約束。為確保無人機(jī)在特定環(huán)境中的安全飛行，設(shè)計(jì)了碰撞避免約束。特別是在四旋翼無人機(jī)飛行過程中，由相鄰飛行器產(chǎn)生的空氣動(dòng)力學(xué)效應(yīng)也有可能觸發(fā)碰撞事件。為此，通過將每架無人機(jī)的碰撞避免邊界建模為沿垂直軸延伸的橢圓形體，其目的是降低由四旋翼無人機(jī)的螺旋槳產(chǎn)生的下洗效應(yīng)［21］，從而增強(qiáng)其在空中的安全距離保障。對(duì)于無人機(jī)i和j的碰撞約束使用尺度矩陣Θ（scaling matrix）來定義：

‖Θ－1（pi［k］－pj［k］）‖n≥rmin（5）

其中：n是橢球的度數(shù)（通常使用n=2）；rmin是無人機(jī)在xy平面中的最小距離；縮放矩陣Θ定義為Θ=diag（a，b，c），設(shè)置a=b=1和cgt;1。因此在垂直軸方向上的最小安全距離被定義為rz，min=crmin。綜上，約束式（5）中檢查的是分別以i和j無人機(jī)為中心的3D橢圓模型之間是否出現(xiàn)重合。

2 分布式模型預(yù)測(cè)控制

基礎(chǔ)問題可被界定為一個(gè)優(yōu)化問題。在單一無人機(jī)的模型預(yù)測(cè)控制（model predictive control，MPC）框架下，每一個(gè)離散時(shí)間步驟都涉及解決一個(gè)優(yōu)化問題，該問題旨在基于無人機(jī)動(dòng)力學(xué)模型，在預(yù)定的預(yù)測(cè)期內(nèi)找到最佳的控制輸入序列。此序列的首個(gè)輸入被施加到實(shí)際無人機(jī)系統(tǒng)上生成新的狀態(tài)，這一新狀態(tài)成為隨后優(yōu)化問題的初始點(diǎn)。然而，在本文描述的離線路徑規(guī)劃場(chǎng)景中，路徑的規(guī)劃并未涉及實(shí)體無人機(jī)的實(shí)時(shí)參與，而是將控制輸入直接施加至模型上，以此計(jì)算并生成軌跡的后續(xù)步驟。通過重復(fù)此過程直到完成所有軌跡的生成，該離線生成方法能夠以分布式的形式實(shí)施，允許對(duì)每一架無人機(jī)的軌跡獨(dú)立并行地迭代優(yōu)化。

2.1 同步算法

本文方法基于分布式模型預(yù)測(cè)控制（distributed model predictive control，DMPC）。該方法要求在并行迭代下一輪優(yōu)化問題前，無人機(jī)需要與機(jī)群中其他無人機(jī)共享其之前預(yù)測(cè)的狀態(tài)序列。在每個(gè)離散時(shí)間點(diǎn)上，每架無人機(jī)遵循以下步驟同時(shí)計(jì)算其范圍內(nèi)新的控制輸入序列：

a）使用上一個(gè)時(shí)間步kt－1計(jì)算的相鄰無人機(jī)的最新預(yù)測(cè)狀態(tài)來檢測(cè)潛在的碰撞風(fēng)險(xiǎn)。

b）構(gòu)造優(yōu)化問題，該問題涵蓋了狀態(tài)和動(dòng)作的限制，以及僅當(dāng)有碰撞風(fēng)險(xiǎn)時(shí)加入的碰撞避免約束。

c）確定下一最優(yōu)控制序列后，將序列的首個(gè)動(dòng)作應(yīng)用于無人機(jī)模型，從而使無人機(jī)模型前進(jìn)一步；隨后，與機(jī)群共享該無人機(jī)的后續(xù)狀態(tài)預(yù)測(cè)。

在此過程中，預(yù)測(cè)碰撞的約束僅在識(shí)別出碰撞風(fēng)險(xiǎn)時(shí)加入，并且只包含與首次預(yù)測(cè)到的碰撞相關(guān)的約束。重復(fù)此過程，直至所有無人機(jī)均到達(dá)其預(yù)定的目標(biāo)航點(diǎn)位置。

2.2 無人機(jī)預(yù)測(cè)模型

使用式（1）（2）中的動(dòng)力學(xué)模型，可以提出一個(gè)線性模型來表示固定長(zhǎng)度K范圍內(nèi)的無人機(jī)狀態(tài)。設(shè)一個(gè)表示方式（^·）［k∣kt］，它表示（·）［kt+k］的預(yù)測(cè)值以及在kt處的可用信息，在之后的表述中k∈{0，…，K－1}是預(yù)測(cè)范圍的離散時(shí)間索引。無人機(jī)的動(dòng)態(tài)模型由式（6）得出。

i［k+1∣kt］i［k+1∣kt］=I3 hI303 I3i［k∣kt］i［k∣kt］+（h2/2）I3hI3i［k∣kt］（6）

其中：I3是一個(gè)3×3的單位矩陣；03是一個(gè)3×3的零矩陣。選擇加速度作為模型的輸入（以及要優(yōu)化的變量），緊湊的表示是

3 智能目標(biāo)點(diǎn)分配

無人機(jī)群隊(duì)形變化主要解決當(dāng)前多無人機(jī)點(diǎn)和目標(biāo)拓?fù)潼c(diǎn)的轉(zhuǎn)換問題。在上一章無人機(jī)的隊(duì)形變化中，每個(gè)無人機(jī)都有一個(gè)固定的最終位置，不能與其他的無人機(jī)進(jìn)行交換，這是一個(gè)帶標(biāo)簽的無人機(jī)隊(duì)形變化問題。在本章算法可以自由地將目標(biāo)點(diǎn)分配給無人機(jī)，將帶標(biāo)簽無人機(jī)隊(duì)形變化問題轉(zhuǎn)換為無標(biāo)簽無人機(jī)隊(duì)形變化問題，以減輕隊(duì)形變化問題的復(fù)雜性。通過合理的目標(biāo)點(diǎn)分配，在軌跡生成時(shí)可以有效減少無人機(jī)軌跡之間可能發(fā)生相交的情況，以此降低了無人機(jī)碰撞發(fā)生的可能性，無人機(jī)可以通過更少的規(guī)避動(dòng)作到達(dá)目標(biāo)點(diǎn)，提升了軌跡生成效率的同時(shí)也提升了無人機(jī)的飛行效率。

本章提出了一種允許無人機(jī)之間自由交換目標(biāo)位置標(biāo)簽的方法，從而優(yōu)化無人機(jī)群的路徑規(guī)劃和隊(duì)形變換過程。如圖3所示的無標(biāo)簽的無人機(jī)群根據(jù)其初始位置以及預(yù)定的目標(biāo)拓?fù)湮恢命c(diǎn)，能夠自主地進(jìn)行目標(biāo)位置點(diǎn)的交換和選擇。這種方法的核心在于利用無人機(jī)之間的協(xié)作，通過動(dòng)態(tài)的目標(biāo)點(diǎn)標(biāo)簽交換有效減少隊(duì)形變化過程中的相互干擾和碰撞風(fēng)險(xiǎn)。

具體來說，首先分析無人機(jī)群的初始位置狀態(tài)和目標(biāo)隊(duì)形的空間布局，然后系統(tǒng)會(huì)評(píng)估在實(shí)現(xiàn)目標(biāo)隊(duì)形過程中各個(gè)無人機(jī)之間交換目標(biāo)點(diǎn)標(biāo)簽的可能性和效益，以決定最終的標(biāo)簽分配方案。通過這種自主的標(biāo)簽選擇和分配策略，無人機(jī)群能夠在減少相互干擾的同時(shí)，更為靈活和高效地完成隊(duì)形變換。

3.1 無人機(jī)相對(duì)位置建模

在本節(jié)中繼續(xù)使用相同的pi表示3×1的無人機(jī)位置向量，設(shè)置一個(gè)3×1向量si， j表示成對(duì)的無人機(jī)之間的位置關(guān)系。如無人機(jī)i和j在時(shí)間步驟k時(shí)的位置關(guān)系：

設(shè)在隊(duì)形變化開始之前的初始無人機(jī)相互位置關(guān)系為ui， j=si， j（0），再設(shè)當(dāng)前的無人機(jī)相互位置關(guān)系為vi， j=si， j（k），最后設(shè)當(dāng)完成隊(duì)形變化的無人機(jī)都達(dá)到目標(biāo)位置時(shí)無人機(jī)相互位置關(guān)系為wi， j=si， j（k），其中k∈{0，…，K}。為了滿足碰撞約束‖ui， j‖，‖wi， j‖≥Δ（i≠j），其中Δ是一個(gè)常數(shù)，如果允許‖ui， j‖，‖wi， j‖盡可能地小，那么在滿足無人機(jī)間最小距離rmin得到

Δ≥2dr（34）

3.2 目標(biāo)點(diǎn)智能分配算法

現(xiàn)在將初始狀態(tài)下的無人機(jī)位置關(guān)系與最終狀態(tài)下的無人機(jī)位置進(jìn)行對(duì)比。如果滿足條件，有可能減少無人機(jī)發(fā)生碰撞的可能，將會(huì)把這一對(duì)無人機(jī)的目標(biāo)位置進(jìn)行交換。在三維空間對(duì)無人機(jī)間位置向量進(jìn)行對(duì)比可以清楚地看出，如果

uTi， jwi， j≥0，

兩無人機(jī)在隊(duì)形變化過程中相對(duì)位置沒有很大的改變，所以沒有動(dòng)機(jī)交換兩無人機(jī)的目標(biāo)位置點(diǎn)；相反，如果

uTi， jwi， jlt;0，

表示兩無人機(jī)完成隊(duì)形變化后相對(duì)位置會(huì)發(fā)生改變，在隊(duì)形變化過程中有可能會(huì)產(chǎn)生阻礙，這時(shí)考慮將這對(duì)無人機(jī)最終目標(biāo)位置進(jìn)行交換，可以將這種交換視為一種目標(biāo)位置點(diǎn)標(biāo)簽的交換。

因?yàn)樗械臒o人機(jī)都在通過uTi， jwi， jlt;0的選擇去交換目標(biāo)位置，就會(huì)出現(xiàn)一個(gè)自然的可收斂問題?？梢杂^察到‖ui， j－wi， j‖的數(shù)值在無人機(jī)交換目標(biāo)位置點(diǎn)的過程中不斷在減?。?/p>

‖ui， j-wi， j‖2=uTi， jui， j+wTi， jwi， j-2uTi， jwi， j（35）

因uTi， jwi， j會(huì)隨著目標(biāo)位置點(diǎn)的交換從負(fù)值變?yōu)檎担栽谟邢薜臒o人機(jī)數(shù)量下最多會(huì)出現(xiàn)N（N－1）/2次的目標(biāo)位置交換。當(dāng)∑Ni=1 ∑j∈Ni‖ui， j－wi， j‖2的數(shù)值收斂到最小值時(shí)得到最優(yōu)的無人機(jī)群目標(biāo)點(diǎn)分配。

4 性能評(píng)估

算法1描述了點(diǎn)對(duì)點(diǎn)轉(zhuǎn)換中采用的分布式模型預(yù)測(cè)控制（DMPC）算法流程。

該流程首先接收N架無人機(jī)的初始位置p0和目標(biāo)位置pf作為輸入，其目的是輸出無人機(jī)的飛行軌跡，其中p、v、a分別代表位置、速度、加速度的向量集，代表所有無人機(jī)在最近時(shí)間步的預(yù)測(cè)位置。

算法1 DMPC點(diǎn)對(duì)點(diǎn)軌跡生成算法

輸入：無人機(jī)的初始位置和目標(biāo)航點(diǎn)位置。

輸出：無人機(jī)的位置、速度、加速度信息。

1 ［Π，x［0］］←intAllPrediction（p0，pf）；

2 kt←0，AtGoal←1；

3 while not AtGoal and ktlt;Kmax do

4" foreach agent i=1，…，N do

5" i［k|kt］←buildSolveQP（xi［kt］，ai［kt－1］，Π）；

6"" if QP feasible then

7"" i［k+1|kt］←getStates（xi［kt］，i［k|kt］）;

8"" Πi←i［k+1|kt］;

9"" xi［kt+1］，ai［kt］←i［1|kt］，i［0|kt］;

10" "end if

11 "end foreach

12 AtGoal←checkGoal（p［kt］，pf）;

13 kt←kt+1;

14 end while

15 if AtGoal then

16 "［p，v，a］←scaleTrajectory（p，v，a，‖amax‖）;

17 "［p，v，a］←interpole（p，v，a，Ts）;

18 "checkCollisions（p，rmin－εcheck）;

19 end if

20 return ［p，v，a］

在第1行中，每個(gè)軌跡被初始化為一條從起點(diǎn)到終點(diǎn)且具有恒定速度的直線。主循環(huán)（第3～14行）循環(huán)解決N架無人機(jī)的優(yōu)化問題，以構(gòu)建同步飛行軌跡，直至所有無人機(jī)到達(dá)終點(diǎn)或達(dá)到最大時(shí)間步限制。如果所有無人機(jī)均位于其目標(biāo)點(diǎn)的指定小半徑范圍內(nèi)，則認(rèn)為軌跡已經(jīng)收斂（第14行）。注意0時(shí)刻無人機(jī)的加速度為零。內(nèi)部循環(huán)（第4～11行）的處理可以串行或并行進(jìn)行，因?yàn)檫@些問題之間不存在數(shù)據(jù)依賴性。

在開展分布式模型預(yù)測(cè)控制算法的QP問題構(gòu)建與求解［22］（第5行）中，算法首先評(píng)估每架無人機(jī)在其預(yù)測(cè)范圍內(nèi)潛在的碰撞風(fēng)險(xiǎn)，接著根據(jù)碰撞預(yù)測(cè)的結(jié)果選擇適當(dāng)?shù)膬?yōu)化方法來解決QP問題。若未檢測(cè)到碰撞風(fēng)險(xiǎn)，算法采用式（21）簡(jiǎn)化QP問題的求解過程，以降低問題的計(jì)算復(fù)雜度；反之，若存在碰撞風(fēng)險(xiǎn)，則引用式（31）來解決碰撞避免的QP問題。一旦求解器成功找到QP問題的解，便在程序的第7行中更新無人機(jī)的狀態(tài)信息，同時(shí)，算法將在第6～9行中預(yù)測(cè)每架無人機(jī)在未來一段時(shí)間內(nèi)的位置和速度。

為了獲取預(yù)測(cè)范圍內(nèi)的無人機(jī)位置及速度信息，采用迭代傳播法對(duì)所需飛行參數(shù)進(jìn)行連續(xù)計(jì)算。當(dāng)每輪迭代的軌跡解得到確認(rèn)后，通過使用時(shí)間間隔Ts對(duì)該解進(jìn)行插值處理，從而生成具有分辨率更高的無人機(jī)飛行軌跡。在算法的第18行，對(duì)于每個(gè)經(jīng)過插值處理的軌跡解都將執(zhí)行一個(gè)軟約束碰撞檢測(cè)過程。該檢測(cè)過程考慮了無人機(jī)的物理安全邊界，以評(píng)估所規(guī)劃軌跡的安全性。若軌跡解在軟約束碰撞檢測(cè)后被判定為安全，則該解被認(rèn)定為有效；若檢測(cè)失敗，則將它視為無效解。

4.1 仿真實(shí)例

使用算法1求解8架無人機(jī)位置交換場(chǎng)景。如圖4所示，圓圈和菱形分別表示初始位置和最終位置。圖4（a）～（c）中的虛線軌跡代表了無人機(jī)3 s內(nèi)預(yù)測(cè)的移動(dòng)路徑，經(jīng)過的實(shí)球是生成的軌跡。通過評(píng)估所有無人機(jī)飛行的總距離作為優(yōu)化標(biāo)準(zhǔn)，與集中式方法相比，分布式方法只是稍微次優(yōu)。

圖5展示了無人機(jī)群在三維空間的點(diǎn)對(duì)點(diǎn)隊(duì)形變化過程，對(duì)應(yīng)顏色的圓圈和菱形分別表示無人機(jī)初始位置和最終位置?？梢钥吹綗o人機(jī)在開始隊(duì)形變化后會(huì)向它們的目標(biāo)位置開始飛行，經(jīng)過的實(shí)球是無人機(jī)各自的飛行軌跡，在飛行過程中遇到將會(huì)發(fā)生與相鄰無人機(jī)碰撞的情況時(shí)無人機(jī)會(huì)選擇調(diào)整速度或是繞行，同時(shí)可以看到之前無人機(jī)群規(guī)劃的路徑不會(huì)對(duì)無人機(jī)的飛行造成阻礙。

4.2 調(diào)參策略

a）軌跡可行性。在給定加速度和松弛約束的情況下不能滿足約束式（28）時(shí)，優(yōu)化問題變得不可行。然而通過局部增加松弛邊界εmax直到滿足約束可以保證問題的可行性，在算法1的第5行中，應(yīng)用此方法來確保問題的遞歸可行性。一旦找到解決方案，變量εmax將重置為其原始值。

b）碰撞可能性。使用具有軟約束的按需碰撞避免并不能保證軌跡無碰撞，軟約束的使用可能導(dǎo)致違反部分軌跡的碰撞約束。此外，由于軌跡是在離散時(shí)間內(nèi)指定的，時(shí)間步長(zhǎng)之間可能會(huì)發(fā)生碰撞沖突，

、ζ的值越高，對(duì)違反碰撞約束的行為懲罰越大，使無人機(jī)對(duì)避免碰撞更加謹(jǐn)慎。

c）振蕩和鎖死。振蕩是由于缺乏中心協(xié)調(diào)而發(fā)生的，無人機(jī)在可能的軌跡之間振蕩以避免碰撞。無人機(jī)可能會(huì)被困在局部極小值中，在那里它無限期地振蕩，永遠(yuǎn)不會(huì)達(dá)到目標(biāo)位置（死鎖）。

4.3 分布式模型預(yù)測(cè)控制算法比較

圖6展示了在保持每立方米空間內(nèi)固定一架無人機(jī)的密度條件下，通過逐漸增加無人機(jī)總數(shù)（進(jìn)而擴(kuò)大工作空間）來評(píng)估不同防撞策略性能的實(shí)驗(yàn)。針對(duì)各種規(guī)模的無人機(jī)群體，進(jìn)行了50次隨機(jī)形態(tài)轉(zhuǎn)換的測(cè)試，圖6（a）揭示了應(yīng)用不同碰撞避免機(jī)制的點(diǎn)對(duì)點(diǎn)隊(duì)形轉(zhuǎn)換成功率。硬約束方法由于無人機(jī)未能到達(dá)指定終點(diǎn)，顯示出較低的成功率，這種方法導(dǎo)致無人機(jī)采取過于保守的策略，通過持續(xù)避免沖突來預(yù)測(cè)軌跡，進(jìn)而妨礙目標(biāo)的實(shí)現(xiàn)；采用硬約束的按需碰撞避免策略可能引發(fā)不可行的優(yōu)化問題，因?yàn)闊o人機(jī)可能在加速度限制范圍內(nèi)無法避免碰撞；采用軟約束策略有效解決了這一問題，在高達(dá)150架無人機(jī)的測(cè)試中實(shí)現(xiàn)了超過75%的成功率，顯著高于其他兩種方案。200架無人機(jī)的成功率降低部分歸因于隊(duì)形變化所需的飛行時(shí)間不足，造成額外50%的失敗率，以至于總失敗率接近80%；隨著無人機(jī)數(shù)量的增加和固定的密度，即更廣闊的環(huán)境，完成隨機(jī)形態(tài)轉(zhuǎn)換的平均時(shí)間也隨之增長(zhǎng)，表明在更大的環(huán)境中隊(duì)形變換的效率可能與所采用的算法無關(guān)。圖6（b）突出顯示了通過采用按需防撞策略顯著降低了計(jì)算時(shí)間。

圖7展示了分布式模型預(yù)測(cè)控制（DMPC）與基于序列凸優(yōu)化（SCP）方法在固定的4 m3空間內(nèi)的性能對(duì)比，對(duì)逐漸增加密度的無人機(jī)群體進(jìn)行了50次不同的隨機(jī)隊(duì)形轉(zhuǎn)換測(cè)試。

從圖7（a）的結(jié)果可以看出，隨著無人機(jī)密度的增加，所提DMPC在95%以上的測(cè)試中成功找到了解決方案，表現(xiàn)出高度的成功率。相比之下，集中式SCP在所有測(cè)試中均能找到解決方案，但解耦方法的成功率隨密度增加而降低。

在計(jì)算時(shí)間方面，如圖7（b）所示，與集中式SCP相比，DMPC的計(jì)算時(shí)間減少了98%，與解耦SCP相比，減少了85%。盡管DMPC的實(shí)現(xiàn)尚未充分利用算法的并行性，但已經(jīng)實(shí)現(xiàn)了顯著更短的運(yùn)行時(shí)間。

為了衡量生成的軌跡規(guī)劃效率的最優(yōu)性，分析了無人機(jī)群點(diǎn)對(duì)點(diǎn)隊(duì)形變化時(shí)飛行距離之和，如圖7（c）所示。分布式模型預(yù)測(cè)控制方法平均產(chǎn)生的飛行路徑長(zhǎng)度較短于解耦式SCP方法，但較長(zhǎng)于集中式SCP方法。次優(yōu)性隨著飛行空間的無人機(jī)密度的增加而增加，因?yàn)闊o人機(jī)主動(dòng)調(diào)整其軌跡以避免碰撞，這些調(diào)整通常會(huì)導(dǎo)致朝向其目標(biāo)航點(diǎn)的非最優(yōu)路徑，但是分布式模型預(yù)測(cè)控制方法的目標(biāo)函數(shù)中包括對(duì)于控制成本和輸入變化的懲罰，這使得生成的軌跡可以讓無人機(jī)更加平滑地飛過障礙以節(jié)省能耗。

如圖7（d）所示，對(duì)于分布式模型預(yù)測(cè)控制方法加入了目標(biāo)航點(diǎn)智能分配，無人機(jī)群根據(jù)無人機(jī)間初始的相對(duì)位置與目標(biāo)航點(diǎn)間相對(duì)位置智能分配目標(biāo)航點(diǎn)，在隊(duì)形變化過程中有效減少了無人機(jī)間可能的飛行軌跡交叉，以此降低了無人機(jī)群總的飛行距離。智能分配航點(diǎn)的無人機(jī)群相較于非智能分配航點(diǎn)的無人機(jī)群的無人機(jī)群飛行總距離下降了26%，實(shí)現(xiàn)軌跡規(guī)劃效率的的顯著提升。

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

本文DMPC能夠快速生成多無人機(jī)點(diǎn)對(duì)點(diǎn)軌跡，使用基于模型的預(yù)測(cè)，無人機(jī)群在移動(dòng)到目標(biāo)位置時(shí)檢測(cè)并避免未來的碰撞。在DMPC框架中引入了具有軟約束的按需碰撞避免算法，以提高先前方法的可擴(kuò)展性和成功率，并使用目標(biāo)點(diǎn)智能分配算法給無人機(jī)合理分配各自的目標(biāo)飛行航點(diǎn)，增加軌跡生成的效率以及無人機(jī)群的飛行效率。與基于SCP的方法相比，大大降低了計(jì)算復(fù)雜性，對(duì)計(jì)劃軌跡的最優(yōu)性只有很小的影響。算法允許并行計(jì)算，這進(jìn)一步減少了軌跡生成的時(shí)間。

該方法可用于快速計(jì)算生成和執(zhí)行大型四旋翼無人機(jī)團(tuán)隊(duì)的飛行軌跡，從而在無人機(jī)表演等應(yīng)用中實(shí)現(xiàn)新的功能，滿足觀眾個(gè)性化需求，進(jìn)而實(shí)現(xiàn)實(shí)時(shí)可交互的無人機(jī)編隊(duì)飛行表演。

參考文獻(xiàn)：

［1］Li Juncheng， Ran Maopeng， Xie Lihua. Efficient trajectory planning for multiple non-holonomic mobile robots via prioritized trajectory optimization ［J］. IEEE Robotics and Automation Letters， 2020， 6（2）： 405-412.

［2］Quan Lun， Yin Longji， Xu Chao， et al. Distributed swarm trajectory optimization for formation flight in dense environments ［C］// Proc of International Conference on Robotics and Automation. Piscataway， NJ： IEEE Press， 2022： 4979-4985.

［3］Zhang Jiayi， Liu Chang， Li Xijun， et al. A survey for solving mixed integer programming via machine learning ［J］. Neurocomputing， 2023， 519（1）： 205-217.

［4］Tang S， Thomas J， Kumar V. Hold or take optimal plan （HOOP）： a quadratic programming approach to multi-robot trajectory generation ［J］. The International Journal of Robotics Research， 2018， 37（9）： 1062-1084.

［5］Zeng Fanruiqi， Idris H R， Clarke J P. Trajectory planning for mission survivability of autonomous vehicles in moderately to extremely uncertain environments ［C］// Proc of the 14th USA/Europe Air Traffic Management Research and Development （ATM Ramp;D） Seminar. 2021： article ID 20210020828.

［6］Zhou Xiang， He Ruizhi， Zhang Hongbo， et al. Sequential convex programming method using adaptive mesh refinement for entry trajec-tory planning problem ［J］. Aerospace Science and Technology， 2021， 109（2）： 106374.

［7］Chen Yufan， Cutler M， How J P. Decoupled path planning via incremental sequential convex programming ［C］// Proc of IEEE International Conference on Robotics and Automation. Piscataway， NJ： IEEE Press， 2015： 5954-5961.

［8］Xu Guangtong， Long Teng， Wang Zhu， et al. Trust-region filtered sequential convex programming for multi-UAV trajectory planning and collision avoidance ［J］. ISA Transactions， 2022， 128（9）： 664-676.

［9］徐廣通， 王祝， 曹嚴(yán)， 等. 動(dòng)態(tài)優(yōu)先級(jí)解耦的無人機(jī)集群軌跡分布式序列凸規(guī)劃 ［J］. 航空學(xué)報(bào)， 2022， 43（2）： 415-426. （Xu Guangtong， Wang Zhu， Cao Yan， et al. Dynamic-priority-decoupled UAV swarm trajectory planning using distributed sequential convex programming ［J］. Acta Aeronautica ET Astronautica Sinica， 2022， 43（2）： 415-426.）

［10］王祝， 徐廣通， 龍騰. 基于定制內(nèi)點(diǎn)法的多無人機(jī)協(xié)同軌跡規(guī)劃 ［J］. 自動(dòng)化學(xué)報(bào)， 2023， 49（11）： 2374-2385. （Wang Zhu， Xu Guangtong， Long Teng. Customized interior-point method for cooperative trajectory planning of multiple unmanned aerial vehicles ［J］. Acta Automatica Sinica， 2023， 49（11）： 2374-2385.）

［11］Qin Zhengyan， Liu Tengfei， Jiang Zhongping. Adaptive backstepping for distributed optimization ［J］. Automatica， 2022， 141（7）： 110304.

［12］Van Den Berg J， Snape J， Guy S J. Reciprocal collision avoidance with acceleration-velocity obstacles ［C］// Proc of IEEE International Conference on Robotics and Automation. Piscataway， NJ： IEEE Press， 2011： 3475-3482.

［13］Alonso Mora J， Breitenmoser A， Rufli M. Optimal reciprocal collision avoidance for multiple non-holonomic robots ［C］// Proc of the 10th International Symposium on Distributed Autonomous Robotic Systems. Berlin： Springer， 2013： 203-216.

［14］郭一聰， 劉小雄， 章衛(wèi)國(guó)， 等. 基于改進(jìn)勢(shì)場(chǎng)法的無人機(jī)三維路徑規(guī)劃方法 ［J］. 西北工業(yè)大學(xué)學(xué)報(bào)， 2020， 38（5）： 977-986. （Guo Yicong， Liu Xiaoxiong， Zhang Weiguo， et al. 3D path planning method for UAV based on improved artificial potential field ［J］. Journal of Northwestern Polytechnical University， 2020， 38（5）： 977-986.）

［15］諶海云， 陳華胄， 劉強(qiáng). 基于改進(jìn)人工勢(shì)場(chǎng)法的多無人機(jī)三維編隊(duì)路徑規(guī)劃 ［J］. 系統(tǒng)仿真學(xué)報(bào)， 2020， 32（3）： 414-420. （Chen Haiyun， Chen Huazhou， Liu Qiang. Multi-UAV 3D formation path planning based on improved artificial potential field ［J］. Journal of System Simulation， 2020， 32（3）： 414-420.）

［16］馮建新， 解爽， 郭冠麟， 等. POMDP-APF：一種基于POMDP模型的APF無人機(jī)路徑規(guī)劃策略 ［J］. 計(jì)算機(jī)應(yīng)用研究， 2023， 40（7）： 2124-2129， 2145. （Feng Jianxin， Xie Shuang， Guo Guanlin， et al. POMDP-APF：UAV path planning strategy of APF based on POMDP model ［J］. Application Research of Computers， 2023， 40（7）： 2124-2129， 2145.）

［17］Luis C E， Vukosavljev M， Schoellig A P. Online trajectory generation with distributed model predictive control for multi-robot motion planning ［J］. IEEE Robotics and Automation Letters， 2020， 5（2）： 604-611.

［18］Bassolillo S R， D’amato E， Notaro I， et al. Decentralized mesh-based model predictive control for swarms of UAVs ［J］. Sensors， 2020， 20（15）： 4324.

［19］秦明星， 王忠， 李海龍， 等. 基于分布式模型預(yù)測(cè)的無人機(jī)編隊(duì)避障控制［J］. 北京航空航天大學(xué)學(xué)報(bào)， 2024， 50（6）： 1969-1981. （Qin Mingxing， Wang Zhong， Li Hailong， et al. Obstacle avoidance control of UAV formation based on distributed model prediction ［J］. Journal of Beijing University of Aeronautics and Astronautics， 2024， 50（6）： 1969-1981.）

［20］Cai Zhihao， Wang Longhong， Zhao Jiang， et al. Virtual target gui-dance-based distributed model predictive control for formation control of multiple UAVs ［J］. Chinese Journal of Aeronautics， 2020， 33（3）： 1037-1056.

［21］Zhou Xin， Zhu Jiangchao， Zhou Hongyu， et al. EGO-swarm： a fully autonomous and decentralized quadrotor swarm system in cluttered environments ［C］// Proc of IEEE International Conference on Robotics and Automation. Piscataway， NJ： IEEE Press， 2021： 4101-4107.

［22］Ferreau H J， Kirches C， Potschka A， et al. qpOASES： a parametric active-set algorithm for quadratic programming ［J］. Mathematical Programming Computation， 2014， 6： 327-363.