Coverage path planning of heterogeneous unmanned aerial vehicles based on ant colony system

被引:251
作者
Chen, Jinchao [1 ]
Ling, Fuyuan [1 ]
Zhang, Ying [1 ]
You, Tao [1 ]
Liu, Yifan [1 ]
Du, Xiaoyan [1 ]
机构
[1] Northwestern Polytech Univ, Sch Comp Sci, Xian 710072, Peoples R China
基金
中国国家自然科学基金;
关键词
Ant colony system; Coverage path planning; Unmanned aerial vehicle; Multiple regions; Heterogeneous UAVs; STRATEGY; TASKS;
D O I
10.1016/j.swevo.2021.101005
中图分类号
TP18 [人工智能理论];
学科分类号
140502 [人工智能];
摘要
Unmanned aerial vehicle (UAV) has been extensively studied and widely adopted in practical systems owing to its effectiveness and flexibility. Although heterogeneous UAVs have an enormous advantage in improving performance and conserving energy with respect to homogeneous ones, they give rise to a complex path planning problem. Especially in large-scale cooperative search systems with multiple separated regions, coverage path planning which seeks optimal paths for UAVs to completely visit and search all of regions of interest, has a NP-hard computation complexity and is difficult to settle. In this work, we focus on the coverage path planning problem of heterogeneous UAVs, and present an ant colony system (ACS)-based algorithm to obtain good enough paths for UAVs and fully cover all regions efficiently. First, models of UAVs and regions are built, and a linear programming-based formulation is presented to exactly provide the best point-to-point flight path for each UAV. Then, inspired by the foraging behaviour of ants that they can obtain the shortest path between their nest and food, an ACS-based heuristic is presented to seek approximately optimal solutions and minimize the time consumption of tasks in the cooperative search system. Experiments on randomly generated regions have been organized to evaluate the performance of the new heuristic in terms of execution time, task completion time and deviation ratio.
引用
收藏
页数:11
相关论文
共 39 条
[1]
Path planning techniques for unmanned aerial vehicles: A review, solutions, and challenges [J].
Aggarwal, Shubhani ;
Kumar, Neeraj .
COMPUTER COMMUNICATIONS, 2020, 149 :270-299
[2]
Batsoyol N., 2018, 2018 IEEE INT C COMM, P1, DOI DOI 10.1109/ICC.2018.8422396
[3]
Sensitivity analysis for fixed-priority real-time systems [J].
Bini, Enrico ;
Di Natale, Marco ;
Buttazzo, Giorgio .
REAL-TIME SYSTEMS, 2008, 39 (1-3) :5-30
[4]
Scheduling independent tasks in cloud environment based on modified differential evolution [J].
Chen, Jinchao ;
Han, Pengcheng ;
Liu, Yifan ;
Du, Xiaoyan .
CONCURRENCY AND COMPUTATION-PRACTICE & EXPERIENCE, 2023, 35 (13)
[5]
Work-in-Progress: Non-Preemptive Scheduling of Periodic Tasks with Data Dependency upon Heterogeneous Multiprocessor Platforms [J].
Chen, Jinchao ;
Du, Chenglie ;
Han, Pengcheng ;
Du, Xiaoyan .
2019 IEEE 40TH REAL-TIME SYSTEMS SYMPOSIUM (RTSS 2019), 2019, :540-543
[6]
Multi-Region Coverage Path Planning for Heterogeneous Unmanned Aerial Vehicles Systems [J].
Chen, Jinchao ;
Du, Chenglie ;
Lu, Xu ;
Chen, Keke .
2019 13TH IEEE INTERNATIONAL CONFERENCE ON SERVICE-ORIENTED SYSTEM ENGINEERING (SOSE) / 10TH INTERNATIONAL WORKSHOP ON JOINT CLOUD COMPUTING (JCC) / IEEE INTERNATIONAL WORKSHOP ON CLOUD COMPUTING IN ROBOTIC SYSTEMS (CCRS), 2019, :356-361
[7]
Scheduling non-preemptive tasks with strict periods in multi-core real-time systems [J].
Chen, Jinchao ;
Du, Chenglie ;
Xie, Fei ;
Lin, Bin .
JOURNAL OF SYSTEMS ARCHITECTURE, 2018, 90 :72-84
[8]
Schedulability analysis of non-preemptive strictly periodic tasks in multi-core real-time systems [J].
Chen, Jinchao ;
Du, Chenglie ;
Xie, Fei ;
Yang, Zhenkun .
REAL-TIME SYSTEMS, 2016, 52 (03) :239-271
[9]
The Relationship Between Age and Mental Health Among Adults in Iran During the COVID-19 Pandemic [J].
Chen, Jiyao ;
Zhang, Stephen X. ;
Wang, Yifei ;
Afshar Jahanshahi, Asghar ;
Mokhtari Dinani, Maryam ;
Nazarian Madavani, Abbas ;
Nawaser, Khaled .
INTERNATIONAL JOURNAL OF MENTAL HEALTH AND ADDICTION, 2022, 20 (05) :3162-3177
[10]
Control strategy of stable walking for a hexapod wheel-legged robot [J].
Chen, Zhihua ;
Wang, Shoukun ;
Wang, Junzheng ;
Xu, Kang ;
Lei, Tao ;
Zhang, Hao ;
Wang, Xiuwen ;
Liu, Daohe ;
Si, Jinge .
ISA TRANSACTIONS, 2021, 108 :367-380