基于最優(yōu)傳輸理論的無人艇編隊任務分配方法

摘 要：無人艇編隊的任務分配問題是無人艇編隊協(xié)同控制領域的一個重要研究問題。合理的任務分配方案將有助于無人艇編隊快速決斷和高效執(zhí)行?，F(xiàn)有方法在對無人艇編隊的任務分配問題進行建模時，鮮有將無人艇的姿態(tài)和動力學模型納入考慮。首先，建立帶姿態(tài)的無人艇編隊的任務分配問題模型；接著，通過將該模型與流形上的最優(yōu)傳輸問題聯(lián)系起來，得到離散求解形式；最后，仿真實驗表明對于無人艇編隊的任務分配中考慮無人艇姿態(tài)的必要性，以及提出的計算方法的有效性。

關鍵詞：最優(yōu)傳輸理論；無人艇編隊；任務分配方法

中圖分類號：E911；E925.67 文獻標志碼：A DOI：10.3969/j.issn.1673-3819.2024.06.015

Task assignment method for unmanned surface vessel formation based on optimal transport theory

XUE Min1， QUAN Chongren1， HU Zhengyang2， WANG Yong2

（1. Naval Equipment Department， Beijing 100036， China;

2. Jiangsu Automation Research Institute， Lianyungang 222061， China）

Abstract：The task assignment method for a large group of unmanned surface vessel （USV） is an important research problem in the field of autonomous unmanned system. Appropriate task assignment schemes will facilitate USV formation for quick decision making and efficient execution. Existing methods rarely take the attitude of USVs and their dynamic equations into considerations. This article first established a model of attitude-based task assignment problem for USV formation; next， by linking the model to the optimal transport problem on the manifold， we obtained its discrete form; finally， our simulation experiment demonstrates the necessity of considering attitude-based task assignment problem for USV formation， and the effectiveness of the method proposed in this paper.

Key words：optimal transport; unmanned surface vessel formation; task assignment

收稿日期：2023-09-22修回日期：2024-02-17

作者簡介：

薛 敏（1979—），男，博士，高級工程師，研究方向為艦船裝備管理。

權崇仁（1982—），男，碩士，工程師。

國內(nèi)外無人平臺的研究正朝著智能化方向發(fā)展，無人艇（Unmanned Surface Vehicle， USV）具有體積小、靈活性高、作戰(zhàn)能力強的優(yōu)勢[1]。與單艘USV相比，多艘USV具有負載能力高、覆蓋范圍 廣、信息處理能力強的特點。多無人艇協(xié)同圍捕問題是國內(nèi)外多無人艇系統(tǒng)研究的一個熱點，在軍事領域具有重要意義。美國海軍在2014年和2016年分別進行了無人艇集群對目標的攔截、包圍等任務的演練；此外，大連海事大學和華中科技大學等高校對無人艇集群也展開了研究和試驗。雖然無人艇編隊協(xié)同工作有重大軍事和經(jīng)濟價值，但是這也帶來了新的挑戰(zhàn)。一方面，由于海上通信條件差，無人艇編隊需要進行分布式的智能控制；另一方面，無人艇編隊在執(zhí)行任務時的任務目標分配策略決定了任務完成的質(zhì)量。為了合理高效地制定無人艇編隊的任務分配方案，科學地配合無人艇群的控制系統(tǒng)執(zhí)行，我們需要考慮以下兩點因素：

1）由于無人艇的欠驅(qū)動特性，在任務分配的過程中應考慮無人艇的動力學方程，從而使得任務易于無人艇執(zhí)行；

2）在一些場景中，例如圍捕敵船時，任務目標不僅需要無人艇群到達指定位置，還要求無人艇的姿態(tài)要指向敵船，這就需要在任務分配時考慮無人艇與任務目標之間的姿態(tài)差異。

基于以上兩點因素，在對無人艇編隊任務分配問題進行建模時，我們需要將無人艇編隊所在的位置及每艘艇的姿態(tài)納入考慮，而不是僅僅將每一艘艇當作質(zhì)點來處理。

從數(shù)學的角度來看，任務分配問題屬于復雜的組合優(yōu)化問題[2]。對于非重復性任務的無人艇編隊任務分配問題，可以采用多旅行商模型[3]（Multiple Travelling Salesman Problem， MTSP）或者車輛路由模型[4]（Vehicle Routing Problem， VRP）；對于重復性任務的無人艇編隊任務分配問題，可以采用網(wǎng)絡流模型[5]（Network Flow Optimization， NFO）或者混合整數(shù)線性規(guī)劃模型[6]（Mixed-Integer Linear Programming， MILP）。Shima等人[7]在NFO模型的基礎上基于無人機系統(tǒng)的工作場景建立了被稱為“協(xié)同多任務分配問題”（Cooperative Multiple Task Assignment Problem， CMTAP）的組合優(yōu)化模型。CMTAP 模型被廣泛地應用于無人機協(xié)同的多任務分配問題當中。

在上述文獻中，考慮無人艇姿態(tài)的任務分配問題還鮮少見到，本文將從最優(yōu)傳輸理論的角度嘗試解決這一問題。具體來說，首先考慮無人艇的動力學模型，建立了帶姿態(tài)的無人艇編隊任務分配問題的數(shù)學模型；接著簡要介紹了最優(yōu)傳輸理論及其求解方法，將帶姿態(tài)的無人艇編隊任務分配問題轉(zhuǎn)化為狀態(tài)空間SE（3）中的最優(yōu)傳輸問題；最后介紹了如何求解帶姿態(tài)的無人艇編隊任務分配問題，并通過仿真實驗說明了考慮無人艇與任務之間姿態(tài)差異的重要性。

1 基本數(shù)學模型

1.1 無人艇動力學模型

問題（11）是一個標準的線性規(guī)劃問題，可以采用單純形算法進行求解。第一個仿真實驗圖2展示了9艘?guī)ё藨B(tài)的無人艇的最優(yōu)任務分配；在第二個仿真實驗中，我們考慮4艘?guī)ё藨B(tài)的無人艇編隊的任務分配問題，并嘗試了4種不同的姿態(tài)誤差權重α，來展示考慮位姿的任務分配問題與只考慮位置的任務分配問題之間的差異，仿真結果如圖3所示。圖3中藍色標記為無人艇編隊的當前位姿，紅色標記為無人艇編隊的任務位姿，黑色虛線代表計算出來的分配方案。從仿真結果可以看出，隨著姿態(tài)誤差權重α的增大，無人艇編隊的任務分配方案也隨之改變，這說明姿態(tài)誤差在無人艇編隊任務分配問題中有著重要的影響。

4 結束語

本文建立了帶姿態(tài)的無人艇編隊的任務分配問題模型，通過求解SE（3）空間中的最優(yōu)傳輸問題，解決了該任務分配問題。帶姿態(tài)的無人艇編隊的任務分配問題模型，考慮了無人艇的動力學模型而非運動學模型，這對于無人艇控制系統(tǒng)的執(zhí)行來說十分有利；同時，由于在任務分配的過程中將無人艇編隊的姿態(tài)以及任務的姿態(tài)納入考慮，本文提出的任務分配方法將有利于編隊圍捕等需要考慮無人艇姿態(tài)的任務。需要說明的是，由于該任務分配算法考慮了無人艇姿態(tài)，相對于傳統(tǒng)任務分配算法，在算法復雜度上主要影響因素是時間，其級別是O（n），即與平臺的數(shù)量有線性關系，但對于海上無人艇系統(tǒng)小編組圍捕任務，該算法是適用的。

參考文獻：

[1]

宋利飛， 徐凱凱， 史曉騫， 等. 多無人艇協(xié)同圍捕智能逃跑目標方法研究[J]. 中國艦船研究， 2023， 18（1）： 52-59.

SONG L F， XU K K， SHI X Q， et al. Multiple USV cooperative algorithm method for hunting intelligent escaped targets[J]. Chinese Journal of Ship Research， 2023， 18（1）： 52-59.

[2] MARTELLO S， TOTH P. Liner assignment problems[J]. Annals of Discrete Mathematics， 1987， 132（31）： 259-282.

[3] FLOOD M M. The traveling-salesman problem[J]. Operations Research， 1956， 4（1）： 61-75.

[4] LAPORTE G. The vehicle routing problem： An overview of exact and approximate algorithms[J]. European Journal of Operational Research， 1992， 59（3）： 345-358.

[5] ZARGHAM M， RIBEIRO A， OZDAGLAR A， et al. Accelerated dual descent for network flow optimization[J]. IEEE Transactions on Automatic Control， 2013， 59（4）： 905-920.

[6] VIELMA J P. Mixed integer linear programming formulation techniques[J]. Siam Review， 2015， 57（1）： 3-57.

[7] EDISON E， SHIMA T. Integrated task assignment and path optimization for cooperating uninhabited aerial vehicles using genetic algorithms[J]. Computers & Operations Research， 2011， 38（1）： 340-356.

[8] FOSSEN T I. Guidance and control of ocean vehicles[M]. New York： John Wiley， 1994.

[9] LEONARD N E. Periodic forcing， dynamics and control of under actuated spacecraft and underwater vehicles[C]//Proceedings of 1995 34th IEEE Conference on Decision and Control. IEEE， 1995.

[10]MONGE G. Mémoire sur la théorie des déblais et des remblais[J]. Histoire de l’Académie Royale des Sciences de Paris， 1781：666-704.

[11]VILLANI C. Topics in optimal transportation[M]. Providence： American Mathematical Soc， 2021：58.

[12]KANTOROVICH L.On translation of mass[C]//Dokl. AN SSSR. Moscow： Russian Academy of Sciences， 1942： 20.

[13]BRENIER Y. Polar factorization and monotone rearrangement of vector-valued functions[J]. Communications on Pure and Applied Mathematics， 1991， 44（4）： 375-417.

[14]PARK F C. Distance metrics on the rigid-body motions with applications to mechanism design[J]. 1995，117（1）： 48-54.

[15]MURRAY R M， LI Z， SASTRY S S. A mathematical introduction to robotic manipulation[M]. Boca Raton： CRC press， 2017.

（責任編輯：許韋韋）