多UAV协同搜索的博弈论模型及快速求解方法

摘要/Abstract

摘要： 在分布式模型预测控制（DMPC）方法框架下，提出了一种局部Nash最优的分布式搜索优化决策方法.设计了基于人工势场的协同机制，给出了势场的形成条件，在此基础上建立了多机协同的图论模型.引入局部Nash最优的定义，通过在连通分量的局部范围进行Nash最优迭代，降低了问题的求解维度.建立了以节点出度刻画UAV决策优先度的模型，根据决策偏序关系，提出了对称、主从、主从对称3种决策形式，并给出了相应的Nash、Stackelberg和NashStackelberg的博弈模型，理论推导了该方法的计算复杂度.采用MPC和粒子群（PSO）优化相结合实现单架UAV的最优决策.仿真结果表明，所提出的方法能有效降低问题的求解规模和通信负担.

关键词: 无人机, 协同搜索, 人工势场, 图论, 博弈模型, 局部纳什最优, 决策优先度

Abstract: This paper proposed a local Nash optimal based distributed search decision method in the frame of distributed model predictive control (DMPC). To consider the interaction between the UAVs, a graph theory based multi-UAVs cooperative model was constructed, which was based on artificial potential field (AFP) cooperative mechanism. It proposed a connected component based hierarchical structure that decomposes the complex optimization problem into smaller, more manageable sub-problems, to reduce the computational complex and communication burden. In this approach, a decision priority sequence is determined by node output degree. According to the decision priority, the paper proposed three decision forms: symmetry, leader-follower(LF) and symmetry-LF form. The corresponding game models were generated. The MPC and particle swarm optimization (PSO) based method was implemented to solve the individual UAV decision making. The simulations show that this is potentially a good method for solving cooperative search problem involving a large number of vehicles with robust performance.

Key words: unmanned aerial vehicle (UAV), cooperative search, artificial potential field, graph theory, game theory, local Nash optimal, decision priority order

中图分类号:

V 249.122

杜继永a, 张凤鸣b, 毛红保c, 刘华伟c, 杨骥a. 多UAV协同搜索的博弈论模型及快速求解方法[J]. 上海交通大学学报（自然版）, 2013, 47(04): 667-673.

DU Ji-Yong-a, ZHANG Feng-Ming-b, MAO Hong-Bao-c, LIU Hua-Wei-c, YANG Ji-a. Game Theory Based Multi-UAV Cooperative Searching Model and Fast Solution Approach[J]. Journal of Shanghai Jiaotong University, 2013, 47(04): 667-673.

参考文献

［1］Joel G, Sujit P B, Sousa J B. Search strategies for multiple UAV search and destroy missions ［J］. Intell Robot Syst, 2011，61:355367.
［2］Yang Yanli. Cooperative search by uninhabited air vehicles in dynamic environment［D］. Cincinnati: Department of Electrical and Computer Engineering & Computer Science of the College of Engineering, University of Cincinnati, 2005.
［3］白杰，杨根科，潘常春，等. 基于改进分散搜索算法的无人机路径规划［J］. 上海交通大学学报,2011,45(2):173178.
BAI Jie, YANG Genke, PAN Changchun, et al. A revised scatter search algorithm for path planning of multiple UAVs［J］. Journal of Shanghai Jiaotong University, 2011, 45(2):173178.
［4］Sujit P B, Ghose D. Twoagent cooperative search using game models with endurance time constraints［J］. Engineering Optimization, 2010, 42(7): 617–639.
［5］杨少环，高晓光，符小卫. 基于博弈论的无人机搜索路径规划［J］.系统工程与电子技术,2011,33(10): 22542257.
YANG Shaohuan, GAO Xiaoguang, FU Xiaowei. Search path planning of unmanned aerial vehicles based on game theory［J］. Systems Engineering and Electronics, 2011, 33(10):22542257.
［6］Yan Meng. Multirobot searching using gametheory based approach［J］. International Journal of Advanced Robotic Systems, 2008, 5(4): 341350.
［7］Giovanini L, Balderud J, Katebi R. Autonomous and decentralized mission planning for clusters of UAVs ［J］. International Journal of Control, 2007, 80(7): 11691179.
［8］彭辉,沈林成,朱华勇. 基于分布式模型预测控制的多UAV协同区域搜索［J］.航空学报, 2010,31(3):593601.
PENG Hui, SHEN Lincheng, ZHU Huayong. Multiple UAV cooperative area search based on distributed model predictive control ［J］. Acta Aeronautica Et Astronautica Sinica, 2010, 31(3):593601.
［9］Itay Sisso, Tal Shima, Yakov BenHaim. Infogap approach to mutiagent search under severe uncertainty［C］∥AIAA Guidance, Navigation, and Control Conference. Chicago： AIAA, 2009:121.
［10］David Galati, Yong Liu, Simaan M. A fast algorithm for unit level team resource allocation in a game environment［C］∥Proceedings of the 42nd IEEE Conference on Decision and Control. Hawaii：IEEE, 2003: 28722877.
［11］Douglas B West.图论导引［M］. 2版. 李建中，骆吉洲, 译. 北京: 机械工业出版社，2005.
［12］严平.无人飞行器航迹规划与任务分配方法研究［D］.武汉：华中科技大学图像识别与人工智能研究所，2006.

[1]	黄宇昊, 韩超, 赵明辉, 杜乾坤, 王石刚. 考虑安全飞行通道约束的无人机飞行轨迹多目标优化策略[J]. 上海交通大学学报, 2022, 56(8): 1024-1033.
[2]	李登攀, 任晓明, 颜楠楠. 基于无人机航拍的绝缘子掉串实时检测研究[J]. 上海交通大学学报, 2022, 56(8): 994-1003.
[3]	罗菁, 张逸楠. 基于改进Grey-AHP的察打一体无人机作战效能评估方法[J]. 空天防御, 2022, 5(2): 1-7.
[4]	聂瑞, 王红茹. 基于神经网络观测器的无人机编队执行器故障诊断[J]. 空天防御, 2022, 5(2): 32-41.
[5]	李伟湋, 高培雪, 陈进, 路玉卿. 基于累积前景理论和三支决策的无人机态势评估[J]. 上海交通大学学报, 2022, 56(11): 1479-1490.
[6]	郭鹏军, 张睿, 高关根, 许斌. 基于相对速度和位置辅助的无人机编队协同导航[J]. 上海交通大学学报, 2022, 56(11): 1438-1446.
[7]	周齐贤, 王寅, 孙学安. 基于增益自适应超螺旋滑模理论的无人机控制[J]. 上海交通大学学报, 2022, 56(11): 1453-1460.
[8]	王克帆, 邱潇颀, 高长生, 荆武兴. 临近空间太阳能无人机横航向变质心控制技术[J]. 空天防御, 2021, 4(4): 29-36.
[9]	吴诗辉, 贾军, 鲍然, 周宇, 夏青元. 面向集群对抗的多弹协同目标分配模型与仿真分析[J]. 空天防御, 2021, 4(3): 1-9.
[10]	姚天成, 赵永生, 王红雨, 何炎平, 丁子龙, 池哲瀛, 蔡炜锴. 风光混合驱动长航程无人海空立体探测船研发[J]. 上海交通大学学报, 2021, 55(2): 215-220.
[11]	王晓军, 管宇锋. 基于TOPSIS法和仿真法的反集群无人机装备体系贡献率研究[J]. 空天防御, 2021, 4(1): 33-40.
[12]	李征, 陈建伟, 彭博. 基于伪谱法的无人机集群飞行路径规划[J]. 空天防御, 2021, 4(1): 52-59.
[13]	刘晨, 谢宝娣, 董国宝, 霍达, 段雨昕, 夏川. 基于自适应积分滑模的无人机编队控制器设计[J]. 空天防御, 2021, 4(1): 65-70.
[14]	王程, 倪旖, 李亮, 郭正勇, 陈兵. 针对小型商业无人机的预警技术发展现状与思考[J]. 空天防御, 2021, 4(1): 83-90.
[15]	梁烽杨, 杨毅钧, 刘功龙, 万兵, 高王升. 多无人机系统协同侦察规划算法研究[J]. 空天防御, 2021, 4(1): 103-108.