间歇式信息传输条件下无人机搜索覆盖规划

doi:10.12305/j.issn.1001-506X.2024.01.18

摘要/Abstract

摘要：

在基站通信范围受限条件下, 若无人机(unmanned aerial vehicle, UAV)执行覆盖搜索任务时经常返回至基站通信范围内实现间歇式信息传输, 能够扩展其覆盖区域和提高执行任务的灵活性。为最小化所有环境位点信息传回基站的时间之和, 需解决覆盖规划和间歇式通信时机选择的耦合问题。在覆盖的目标点较少且分散时, 采用改进的层次聚类方法求解每次往返需要覆盖的路径点集合。在需要进行区域全覆盖时, 则在求解完区域的覆盖路径后, 以最小化时间之和为目标, 对目标函数进行分析, 确定最优返回次数的搜索范围, 压缩解空间。对该搜索范围进行遍历搜索得到最优往返次数, 然后利用遗传算法优化UAV返回位点。与前沿算法对比, 所提算法在目标函数和覆盖路径质量上具有一定的提升。

关键词: 通信耦合, 层次聚类, 解空间压缩, 遗传算法

Abstract:

Under the limited communication range of the base station, if the unmanned aerial vehicle (UAV) often returns to the communication range of the base station to realize intermittent information transmission when conducting covering searching task, it can expand its coverage area and improve the flexibility of the execution of the mission. In order to minimize the sum of time for the information of all environmental sites to be transmitted back to the base station, the coupling problem of coverage planning and timing of intermittent communication should be solved. When the target points to be covered are few and scattered, the improved hierarchical clustering method is used to obtain the set of path points that need to be covered in each round trip. When it is necessary to carry out full coverage of the region, the following methods are adopted: after obtaining the coverage path of the region, the objective function is analyzed to minimize the sum of time, and the search range of optimal return times is determined to compress the solution space. The optimal round-trip times are obtained by traversing the search range, and then genetic algorithm is used to optimize the UAV return sites. Compared with the advanced algorithms, the objective function value and the quality of coverage path of the proposed algorithm is significantly improved.

Key words: communication coupling, hierarchical clustering, solution space compression, genetic algorithm

中图分类号:

P242.6

曹志强, 张佳, 辛斌. 间歇式信息传输条件下无人机搜索覆盖规划[J]. 系统工程与电子技术, 2023, 46(1): 152-161.

Zhiqiang CAO, Jia ZHANG, Bin XIN. UAV search coverage planning under intermittent information transmission condition[J]. Systems Engineering and Electronics, 2023, 46(1): 152-161.

图/表 12

图1

图2

图3

图4

图5

表1

图6

图7

表2

表3

图8

表4

参考文献 30

1	周洋, 赵旭毅. 基于地震灾害的分层应急通信保障策略研究[J]. 空间电子技术, 2021, 18 (4): 16- 20. doi: 10.3969/j.issn.1674-7135.2021.04.003
	ZHOU Y , ZHAO X Y . Research on stratified emergency communication guarantee strategy of earthquake disaster[J]. Space Electronic Technology, 2021, 18 (4): 16- 20. doi: 10.3969/j.issn.1674-7135.2021.04.003
2	SABO C , KINGSTON D , COHEN K . A formulation and heuristic approach to task allocation and routing of UAVs under limited communication[J]. Unmanned Systems, 2014, 2 (1) doi: 10.1142/S2301385014500010
3	MENG G, ZAVLANOS M M. Distributed data gathering with buffer constraints and intermittent communication[C]//Proc. of the IEEE International Conference on Robotics and Automation, 2017: 14-27.
4	KANTAROS Y , GUO M , ZAVLANOS M M . Temporal logic task planning and intermittent connectivity control of mobile robot networks[J]. IEEE Trans.on Automatic Control, 2019, 64 (10): 4105- 4120. doi: 10.1109/TAC.2019.2893161
5	ARAGUES R , DIMAROGONAS D V , GUALLAR P , et al. Intermittent connectivity maintenance with heterogeneous robots[J]. IEEE Trans.on Robotics, 2021, 37 (1): 225- 245. doi: 10.1109/TRO.2020.3014521
6	SCHERER J , RINNER B . Multi-UAV surveillance with minimum information idleness and latency constraints[J]. IEEE Trans.on Robotics and Automation Letters, 2020, 5 (3): 4812- 4819. doi: 10.1109/LRA.2020.3003884
7	CARABALLO L , DÍAZ-BÁÑEZ J , FABILA-MONROY R , et al. Stochastic strategies for patrolling a terrain with a synchronized multi-robot system[J]. European Journal of Operational Research, 2021, 301 (3): 1099- 1116.
8	GUASTELLA D C , CANTELLI L , GIAMMELLO G , et al. Complete coverage path planning for aerial vehicle flocks deployed in outdoor environments[J]. Computers & Electrical Engineering, 2019, 75, 189- 201.
9	CHOSET H , PIGNON P . Coverage path planning: the boustrophedon cellular decomposition[M]. London: Springer, 1998.
10	CABREIRA T M , BRISOLARA L B , FERREIRA P R . Survey on coverage path planning with unmanned aerial vehicles[J]. Drones, 2019, 3 (1): 4- 20. doi: 10.3390/drones3010004
11	KHAN A , NOREEN I , ZULFIQAR H . On complete coverage path planning algorithms for non-holonomic mobile robots: survey and challenges[J]. Journal of Information Science and Engineering, 2017, 33 (1): 101- 121.
12	PHAM T H, ICHALAL D, MAMMAR S. Complete coverage path planning for pests-ridden in precision agriculture using UAV[C]//Proc. of the IEEE International Conference on Networking, Sensing and Control, 2020.
13	谢朋志, 魏晨. 单侧区域分割的多无人机扫描线搜索方法研究[J]. 航空兵器, 2020, 27 (3): 67- 72.
	XIE P Z , WEI C . Research on scanning line search method for multi-UAV based on unilateral region segmentation[J]. Aero Weaponry, 2020, 27 (3): 67- 72.
14	TUNG W C , LIU J S . Solution of an integrated traveling salesman and coverage path planning problem by using a genetic algorithm with modified operators[J]. International Journal on Computer Science and Information Systems, 2019, 14 (2): 95- 114.
15	CAI Z Y , LI S X , GAN Y , et al. Research on complete coverage path planning algorithms based on A^* algorithms[J]. The Open Cybernetics and Systemics Journal, 2014, 8, 418- 426. doi: 10.2174/1874110X01408010418
16	VASQUEZ G J I , MARCIANO M M , VALENTIN L , et al. Coverage path planning for 2D convex regions[J]. Journal of Intelligent & Robotic Systems, 2020, 97 (6): 81- 94.
17	黄月琴, 罗兵, 邓辅秦, 等. 智能扫地机器人的全覆盖路径规划[J]. 五邑大学学报(自然科学版), 2021, 35 (2): 51- 58.
	HUANG Y Q , LUO B , DENG F Q , et al. Complete coverage path planning for intelligent sweeping robot[J]. Journal of Wuyi University(Natural Science Edition), 2021, 35 (2): 51- 58.
18	王伟, 张彦斐, 宫金良, 等. 基于自适应升温模拟退火算法的农业机器人全区域覆盖策略[J]. 华南农业大学学报, 2021, 42 (6): 126- 132.
	WANG W , ZHANG Y F , GONG J L , et al. Whole area coverage strategy of agric ultural robot based on adaptive heating simulated annealing algorithm[J]. Journal of South China Agricultural University, 2021, 42 (6): 126- 132.
19	YUAN J B , LIU Z B , LIAN Y D , et al. Global optimization of UAV area coverage path planning based on good point set and genetic algorithm[J]. Aerospace, 2022, 9 (2): 86- 102.
20	THERESA M D. Complete coverage path planning in an agricultural environment[D]. Iowa: Iowa State University, 2011.
21	尹洋, 杨全顺, 王征, 等. 通信距离约束下的无人船集群覆盖搜索方法[J]. 系统工程与电子技术, 2022, 44 (12): 3821- 3828.
	YIN Y , YANG Q S , WANG Z , et al. USV cluster coverage search method with communication distance constraint[J]. Systems Engineering and Electronics, 2022, 44 (12): 3821- 3828.
22	NESTMEYER T , GIORDANO P , BÜLTHOFF H , et al. Decentralized simultaneous multi-target exploration using a connected network of multiple robots[J]. Autonomous Robots, 2017, 2 (1): 41- 50.
23	CLARK L , GALANTE J , KRISHNAMACHARI B , et al. A queue-stabilizing framework for networked multi-robot exploration[J]. IEEE Robotics and Automation Letters, 2021, 6 (2): 2091- 2098.
24	AGGRAVI M , SIRIGNANO G , GIORDANO P R , et al. Decentralized control of a heterogeneous human-robot team for exploration and patrolling[J]. IEEE Trans.on Automation Science and Engineering, 2021, 10 (1): 101- 133.
25	王宁, 李哲, 梁晓龙, 等. 通信距离受限条件下的无人机集群协同区域搜索[J]. 系统工程与电子技术, 2022, 44 (5): 1615- 1625.
	WANG N , LI Z , LIANG X L , et al. Cooperative region search of UAV swarm with limited communication distance[J]. Systems Engineering and Electronics, 2022, 44 (5): 1615- 1625.
26	BANFI J . Recent advances in multirobot exploration of communication-restricted environments[J]. Intelligenza Artificiale, 2020, 13 (1): 203- 230.
27	BENAVIDES F , PONZONI C C , CAROLINE , et al. An auto-adaptive multi-objective strategy for multi-robot exploration of constrained-communication environments[J]. Applied Sciences, 2019, 9 (3): 573- 619.
28	PEI Y , MUTKA M W , XI N . Connectivity and bandwidth-aware real-time exploration in mobile robot networks[J]. Wireless Communications and Mobile Computing, 2011, 10 (2): 26- 53.
29	SINAGA K P , YANG M . Unsupervised K-means clustering algorithm[J]. IEEE Access, 2020, 8, 80716- 80727.
30	SHUKLA A, PANDEY H M, MEHROTRA. Comparative review of selection techniques in genetic algorithm[C]//Proc. of the International Conference on Futuristic Trends on Computational Analysis and Knowledge Management, 2015: 520-525.

地图序号	本文算法	Sabo算法	文献[17]方法+遗传算法
1	16 461	20 247	29 414
2	78 176	95 588	168 392

地图/基站位置	利用${\bar C}$计算所得返回次数	λ=1对应的目标函数值/返回次数	λ=2对应的目标函数值/返回次数	λ=3对应的目标函数值/返回次数	返回次数不在λ=3对应的范围内的目标函数值/返回次数
地图 1/(10, 12)	6.68	1 631 178/7	1 562 332/8	1 561 416/8	1 681 732/11
地图 2/(19, 5)	6.23	1 715 465/6	1 656 679/8	1 656 679/8	1 772 111 /10
地图 3/(24, 20)	7.83	1 398 851/8	1 397 089/10	1 397 089/10	1 462 004/13
地图 4/(24, 20)	6.57	1 259 469/6	1 240 488/7	1 240 488/7	1 274 252/10

地图/基站位置	本文三阶段优化算法	Sabo算法	文献[17]方法+遗传算法
地图 1/(10, 12)	1 561 416	1 631 178	2 977 033
地图 2/(19, 5)	1 656 679	1 726 471	3 326 471
地图 3/(24, 20)	1 397 089	1 498 706	2 755 517
地图 4/(24, 20)	1 240 488	1 206 292	3 680 581

地图	本文三阶段优化算法	Sabo算法
地图 1	560	724
地图 2	571	731
地图 3	580	752
地图 4	590	710

[1]	邓勇, 姚锋, 邢立宁, 何磊. 基于混合进化算法的卫星网络星间数传方法[J]. 系统工程与电子技术, 2023, 45(9): 2931-2940.
[2]	马维宁, 胡起伟, 曹文斌, 贾希胜. 考虑维修任务分配的装备选择性维修决策优化[J]. 系统工程与电子技术, 2023, 45(6): 1902-1910.
[3]	毕可心, 吴明功, 温祥西, 张文斌, 杨文达. 基于飞行冲突网络和遗传算法的冲突解脱策略[J]. 系统工程与电子技术, 2023, 45(5): 1429-1440.
[4]	吕晓峰, 杨东泽, 马羚. 舰载机模块化弹药调度方案优化设计[J]. 系统工程与电子技术, 2023, 45(2): 465-471.
[5]	阎哲, 汪民乐, 汪江鹏, 闫少强, 吴丰轩. 基于混合遗传算法的海军航空兵场站物资配送车辆调度智能优化[J]. 系统工程与电子技术, 2023, 45(12): 3908-3914.
[6]	文启翟, 康志宇, 卫国宁, 贺彦博, 吴斌, 周睿逸. 子母型航天器抵近观测任务流程规划方法研究[J]. 系统工程与电子技术, 2023, 45(12): 3941-3948.
[7]	胡杰, 鲍帆, 石潇竹. 基于贪婪-遗传算法的机场登机口分配策略[J]. 系统工程与电子技术, 2023, 45(11): 3555-3564.
[8]	骆天溯, 赵灵峰, 冯蕴雯, 薛小锋, 路成. 基于METRIC理论的超大规模卫星星座多级备份策略[J]. 系统工程与电子技术, 2022, 44(7): 2181-2190.
[9]	李波, 周家豪, 刘民岷, 朱品朝. 基于改进NSGA3的焊接缺陷评估特征选择[J]. 系统工程与电子技术, 2022, 44(7): 2211-2218.
[10]	冯豪博, 胡桥, 赵振轶. 基于精英族系遗传算法的AUV集群路径规划[J]. 系统工程与电子技术, 2022, 44(7): 2251-2262.
[11]	杨少龙, 黄金, 向先波, 李伟超. 基于置信椭圆的无人艇区域覆盖搜寻规划优化[J]. 系统工程与电子技术, 2022, 44(7): 2263-2269.
[12]	冯蕴雯, 陈俊宇, 路成. 民用飞机多地域航材支援网络模型研究[J]. 系统工程与电子技术, 2022, 44(5): 1553-1561.
[13]	靳鹏, 唐晓茜. 考虑合成机制的多星应急任务调度[J]. 系统工程与电子技术, 2022, 44(4): 1270-1281.
[14]	孙剑炜, 王超, 施庆展, 任文博, 尧泽昆, 袁乃昌. 基于遗传算法的相位调制波形智能优化[J]. 系统工程与电子技术, 2022, 44(3): 722-729.
[15]	薛乃阳, 丁丹, 王红敏, 刘步花. 基于改进遗传算法的多类测控资源调度方法[J]. 系统工程与电子技术, 2021, 43(9): 2535-2543.