Journal of Computer Applications ›› 2024, Vol. 44 ›› Issue (10): 3232-3239.DOI: 10.11772/j.issn.1001-9081.2023101432
• Frontier and comprehensive applications • Previous Articles Next Articles
Jian SUN1,2(), Baoquan MA1, Zhuiwei WU1, Xiaohuan YANG1, Tao WU1, Pan CHEN1
Received:
2023-10-23
Revised:
2023-12-19
Accepted:
2023-12-26
Online:
2024-10-15
Published:
2024-10-10
Contact:
Jian SUN
About author:
MA Baoquan, born in 1997, M. S. candidate. His research interests include mobile edge computing, big data storage and management.Supported by:
孙鉴1,2(), 马宝全1, 吴隹伟1, 杨晓焕1, 武涛1, 陈攀1
通讯作者:
孙鉴
作者简介:
孙鉴(1982—),男,山东烟台人,讲师,博士,CCF会员,主要研究方向:大数据存储与管理 2014132@nun.edu.cn基金资助:
CLC Number:
Jian SUN, Baoquan MA, Zhuiwei WU, Xiaohuan YANG, Tao WU, Pan CHEN. Joint optimization of UAV swarm path planning and task allocation balance in earthquake scenarios[J]. Journal of Computer Applications, 2024, 44(10): 3232-3239.
孙鉴, 马宝全, 吴隹伟, 杨晓焕, 武涛, 陈攀. 地震场景下无人机群路径规划与任务分配均衡联合优化[J]. 《计算机应用》唯一官方网站, 2024, 44(10): 3232-3239.
Add to citation manager EndNote|Ris|BibTeX
URL: https://www.joca.cn/EN/10.11772/j.issn.1001-9081.2023101432
参数 | 描述 | 值 |
---|---|---|
无人机加速度 | ||
无人机最大速度 | ||
空气密度 | ||
无人机转子半径 | ||
剖面阻力系数 | 0.012 | |
无人机叶片角速度 | ||
感应功率增量因子 | 0.1 | |
无人机重量 | ||
转子实度 | 20 | |
机身等效板面积 | 0.002 m2 | |
机身阻力比 | 0.001 | |
悬停能耗 | ||
中型无人机能耗上限 | ||
中型无人机任务荷载上限 | 220 | |
大型无人机能耗上限 | ||
大型无人机任务荷载上限 | 600 |
Tab. 1 UAV swarm related parameters
参数 | 描述 | 值 |
---|---|---|
无人机加速度 | ||
无人机最大速度 | ||
空气密度 | ||
无人机转子半径 | ||
剖面阻力系数 | 0.012 | |
无人机叶片角速度 | ||
感应功率增量因子 | 0.1 | |
无人机重量 | ||
转子实度 | 20 | |
机身等效板面积 | 0.002 m2 | |
机身阻力比 | 0.001 | |
悬停能耗 | ||
中型无人机能耗上限 | ||
中型无人机任务荷载上限 | 220 | |
大型无人机能耗上限 | ||
大型无人机任务荷载上限 | 600 |
规模 | 算例 | 模型 | 求解时间 |
---|---|---|---|
小规模 | A-n34-k5 | ADACO | 6.12 |
SMACO | 6.03 | ||
GSACO | 6.11 | ||
IACO | 8.56 | ||
JPACO | 9.29 | ||
E-n76-k8 | ADACO | 22.60 | |
SMACO | 20.95 | ||
GSACO | 17.71 | ||
IACO | 21.32 | ||
JPACO | 32.35 | ||
大规模 | X-n125-k30 | ADACO | 60.03 |
SMACO | 51.35 | ||
GSACO | 50.93 | ||
IACO | 53.54 | ||
JPACO | 46.75 |
Tab. 2 Solution time of models
规模 | 算例 | 模型 | 求解时间 |
---|---|---|---|
小规模 | A-n34-k5 | ADACO | 6.12 |
SMACO | 6.03 | ||
GSACO | 6.11 | ||
IACO | 8.56 | ||
JPACO | 9.29 | ||
E-n76-k8 | ADACO | 22.60 | |
SMACO | 20.95 | ||
GSACO | 17.71 | ||
IACO | 21.32 | ||
JPACO | 32.35 | ||
大规模 | X-n125-k30 | ADACO | 60.03 |
SMACO | 51.35 | ||
GSACO | 50.93 | ||
IACO | 53.54 | ||
JPACO | 46.75 |
规模 | 算例 | 模型 | 路径最优值 | 路径平均值 |
---|---|---|---|---|
小规模 | A-n36-k5 | ADACO | 951.21 | 983.60 |
SMACO | 912.22 | 965.50 | ||
GSACO | 939.65 | 941.30 | ||
IACO | 873.28 | 889.32 | ||
JPACO | 810.30 | 823.20 | ||
E-n76-k7 | ADACO | 896.32 | 932.61 | |
SMACO | 892.22 | 921.61 | ||
GSACO | 819.15 | 829.43 | ||
IACO | 854.76 | 864.16 | ||
JPACO | 811.56 | 819.62 | ||
大规模 | X-n101-k25 | ADACO | 32 976.93 | 33 662.89 |
SMACO | 32 609.48 | 33 231.47 | ||
GSACO | 31 721.29 | 32 119.35 | ||
IACO | 32 769.43 | 32 980.68 | ||
JPACO | 31 490.26 | 31 949.58 |
Tab. 3 Optimal path comparison
规模 | 算例 | 模型 | 路径最优值 | 路径平均值 |
---|---|---|---|---|
小规模 | A-n36-k5 | ADACO | 951.21 | 983.60 |
SMACO | 912.22 | 965.50 | ||
GSACO | 939.65 | 941.30 | ||
IACO | 873.28 | 889.32 | ||
JPACO | 810.30 | 823.20 | ||
E-n76-k7 | ADACO | 896.32 | 932.61 | |
SMACO | 892.22 | 921.61 | ||
GSACO | 819.15 | 829.43 | ||
IACO | 854.76 | 864.16 | ||
JPACO | 811.56 | 819.62 | ||
大规模 | X-n101-k25 | ADACO | 32 976.93 | 33 662.89 |
SMACO | 32 609.48 | 33 231.47 | ||
GSACO | 31 721.29 | 32 119.35 | ||
IACO | 32 769.43 | 32 980.68 | ||
JPACO | 31 490.26 | 31 949.58 |
算例 | 模型 | Number | ||
---|---|---|---|---|
A-n36-k5 | ADACO | 1.10 | 0.30 | 2 |
SMACO | 0.97 | 0.20 | 2 | |
GSACO | 0.84 | 0.34 | 1 | |
IACO | 1.10 | 0.50 | 2 | |
JPACO | 0.82 | 0.54 | 1 | |
E-n76-k7 | ADACO | 1.03 | 0.34 | 1 |
SMACO | 0.98 | 0.45 | 3 | |
GSACO | 0.95 | 0.41 | 2 | |
IACO | 1.10 | 0.32 | 2 | |
JPACO | 0.94 | 0.57 | 1 | |
X-n106-k14 | ADACO | 9.40 | 2.10 | 8 |
SMACO | 9.50 | 3.20 | 8 | |
GSACO | 9.30 | 3.50 | 7 | |
IACO | 9.40 | 3.40 | 6 | |
JPACO | 9.10 | 4.50 | 5 |
Tab. 4 Energy consumption comparison
算例 | 模型 | Number | ||
---|---|---|---|---|
A-n36-k5 | ADACO | 1.10 | 0.30 | 2 |
SMACO | 0.97 | 0.20 | 2 | |
GSACO | 0.84 | 0.34 | 1 | |
IACO | 1.10 | 0.50 | 2 | |
JPACO | 0.82 | 0.54 | 1 | |
E-n76-k7 | ADACO | 1.03 | 0.34 | 1 |
SMACO | 0.98 | 0.45 | 3 | |
GSACO | 0.95 | 0.41 | 2 | |
IACO | 1.10 | 0.32 | 2 | |
JPACO | 0.94 | 0.57 | 1 | |
X-n106-k14 | ADACO | 9.40 | 2.10 | 8 |
SMACO | 9.50 | 3.20 | 8 | |
GSACO | 9.30 | 3.50 | 7 | |
IACO | 9.40 | 3.40 | 6 | |
JPACO | 9.10 | 4.50 | 5 |
算例 | 满载 | 模型 | |||
---|---|---|---|---|---|
A-n32-k5 | 100 | ADACO | 98 | 33 | 30.52 |
SMACO | 98 | 20 | 31.02 | ||
GSACO | 99 | 20 | 25.08 | ||
IACO | 97 | 23 | 27.32 | ||
JPACO | 91 | 44 | 19.23 | ||
X-n106-k14 | 600 | ADACO | 598 | 486 | 32.96 |
SMACO | 594 | 522 | 23.25 | ||
GSACO | 589 | 520 | 19.21 | ||
IACO | 587 | 513 | 24.65 | ||
JPACO | 579 | 532 | 15.46 |
Tab. 5 Task allocation comparison
算例 | 满载 | 模型 | |||
---|---|---|---|---|---|
A-n32-k5 | 100 | ADACO | 98 | 33 | 30.52 |
SMACO | 98 | 20 | 31.02 | ||
GSACO | 99 | 20 | 25.08 | ||
IACO | 97 | 23 | 27.32 | ||
JPACO | 91 | 44 | 19.23 | ||
X-n106-k14 | 600 | ADACO | 598 | 486 | 32.96 |
SMACO | 594 | 522 | 23.25 | ||
GSACO | 589 | 520 | 19.21 | ||
IACO | 587 | 513 | 24.65 | ||
JPACO | 579 | 532 | 15.46 |
1 | SINGHAL G, BANSOD B, MATHEW L. Unmanned aerial vehicle classification, applications and challenges: a review[EB/OL]. [2023-10-18]. . |
2 | BAJRACHARYA R, SHRESTHA R, KIM S, et al. 6G NR-U based wireless infrastructure UAV: standardization, opportunities, challenges and future scopes[J]. IEEE Access, 2022, 10: 30536-30555. |
3 | 张博闻. 无人机航空遥感系统在灾害应急救援中的应用[J]. 中国高新科技, 2022(21):159-160. |
ZHANG B W. Application of UAV aerial remote sensing system in disaster emergency rescue[J]. China High and New Technology, 2022(21): 159-160. | |
4 | WU X, BAI W, XIE Y, et al. A hybrid algorithm of particle swarm optimization, Metropolis criterion and RTS smoother for path planning of UAVs[J]. Applied Soft Computing, 2018, 73: 735-747. |
5 | 李姝,裘昌利,李晶. 攻防一体化无人机蜂群作战体系研究[C]// 2022年无人系统高峰论坛(USS)论文集. 西安: 空军航空大学, 2022: 7-12. |
LI S, QIU C L, LI J. Research on attack-defense integration of UAV swarms[C]// Proceedings of the 2022 Unmanned System Summit Forum (USS). Xi’an: Aviation University of Air Force, 2022: 7-12. | |
6 | WEI C, JI Z, CAI B. Particle swarm optimization for cooperative multi-robot task allocation: a multi-objective approach[J]. IEEE Robotics and Automation Letters, 2020, 5(2): 2530-2537. |
7 | VIDAL T. Hybrid genetic search for the CVRP: open-source implementation and SWAP* neighborhood[J]. Computers and Operations Research, 2022, 140: No.105643. |
8 | 石一鹏,刘杰,祖锦源,等. 基于混合整数线性规划模型的SPONGENT S盒紧凑约束分析[J]. 计算机应用, 2023, 43(5):1504-1510. |
SHI Y P, LIU J, ZU J Y, et al. Compact constraint analysis of SPONGENT S-box based on mixed integer linear programming model[J]. Journal of Computer Applications, 2023, 43(5): 1504-1510. | |
9 | MALVANKAR-MEHTA M S, MEHTA S S. Optimal task allocation in multi-human multi-robot interaction[J]. Optimization Letters, 2015, 9(8): 1787-1803. |
10 | BAYS M J, WETTERGREN T A. Service agent-transport agent task planning incorporating robust scheduling techniques[J]. Robotics and Autonomous Systems, 2017, 89: 15-26. |
11 | DAI W, LU H, XIAO J, et al. Multi-robot dynamic task allocation for exploration and destruction[J]. Journal of Intelligent and Robotic Systems, 2020, 98: 455-479. |
12 | DUAN X, LIU H, TANG H, et al. A novel hybrid auction algorithm for multi-UAVs dynamic task assignment[J]. IEEE Access, 2020, 8: 86207-86222. |
13 | ZHU D, LIU Y, SUB B. Task assignment and path planning of a multi-AUV system based on a Glasius bio-inspired self-organising map algorithm[J]. The Journal of Navigation, 2018, 71(2): 482-496. |
14 | PHUNG M D, QUACH C H, DINH T H, et al. Enhanced discrete particle swarm optimization path planning for UAV vision-based surface inspection[J]. Automation in Construction, 2017, 81: 25-33. |
15 | CHEN J, SUN D. Resource constrained multirobot task allocation based on leader-follower coalition methodology[J]. The International Journal of Robotics Research, 2011, 30(12): 1423-1434. |
16 | 吴虎胜,张凤鸣,吴庐山. 一种新的群体智能算法——狼群算法[J]. 系统工程与电子技术, 2013, 35(11):2430-2438. |
WU H S, ZHANG F M, WU L S. New swarm intelligence algorithm — wolf pack algorithm[J]. Systems Engineering and Electronics, 2013, 35(11): 2430-2438. | |
17 | DORIGO M, GAMBARDELLA L M. Ant colonies for the travelling salesman problem[J]. Biosystems, 1997, 43(2): 73-81. |
18 | DUAN Y Q, ZHANG Y, ZHANG B, et al. Path planning based on improved multi-objective particle swarm algorithm[C]// Proceedings of the IEEE 5th Information Technology and Mechatronics Engineering Conference. Piscataway: IEEE, 2020: 1005-1009. |
19 | TIAN J, WANG Y, FAN C. Research on target assignment of multiple-UAVs based on improved hybrid genetic algorithm[C]// Proceedings of the IEEE 4th International Conference on Control Science and Systems Engineering. Piscataway: IEEE, 2018: 304-307. |
20 | 夏乐. 基于贪婪策略的蚁群优化算法研究与应用[D]. 赣州:江西理工大学, 2022:19-21. |
XIA L. Research and application of ant colony optimization algorithm with greedy strategy[D]. Ganzhou: Jiangxi University of Science and Technology, 2022: 19-21. | |
21 | 张航,高岳林. 求解带容量约束车辆路径问题的改进蚁群算法[J]. 宝鸡文理学院学报(自然科学版), 2022, 42(3):18-23, 29. |
ZHANG H, GAO Y L. An improved ant colony optimization for capacitated vehicle routing problem[J]. Journal of Baoji University of Arts and Sciences (Natural Science Edition), 2022, 42(3): 18-23, 29. | |
22 | 陈颖杰,高茂庭. 基于信息素初始分配和动态更新的蚁群算法[J]. 计算机工程与应用, 2022, 58(2):95-101. |
CHEN Y J, GAO M T. Pheromone initialization and dynamic update based ant colony algorithm[J]. Computer Engineering and Applications, 2022, 58(2): 95-101. | |
23 | 王艳春,郭永峰,夏颖,等. 基于改进蚁群算法的机器人全局路径规划研究[J]. 电子科技, 2024, 37(5): 88-94. |
WANG Y C, GUO Y F, XIA Y, et al. Research on robot global path planning based on improved ant colony algorithm[J]. Electronic Science and Technology, 2024, 37(5): 88-94. | |
24 | KAKOOEI M, BALEGHI Y. Fusion of satellite, aircraft, and UAV data for automatic disaster damage assessment[J]. International Journal of Remote Sensing, 2017, 38(8/9/10): 2511-2534. |
25 | LI K, CHEN X, LIU H, et al. Performance analysis of the thermal automatic tracking method based on the model of the UAV dynamic model in a thermal and cubature Kalman filter[J]. Drones, 2023, 7(2): No.102. |
26 | ZHANG Y X, LI K, LIU J Y. Intelligent prediction method for updraft of UAV that is based on LSTM network[J]. IEEE Transactions on Cognitive and Developmental Systems, 2023, 15(2): 464-475. |
27 | EJAZ W, AHMED A, MUSHTAQ A, et al. Energy-efficient task scheduling and physiological assessment in disaster management using UAV-assisted networks[J]. Computer Communications, 2020, 155: 150-157. |
28 | MAH M C, LIM H S, TAN A W C. Secrecy improvement via joint optimization of UAV relay flight path and transmit power[J]. Vehicular Communications, 2020, 23: No.100217. |
29 | SHAH Z, JAVED U, NAEEM M, et al. Mobile Edge Computing (MEC)-enabled UAV placement and computation efficiency maximization in disaster scenario[J]. IEEE Transactions on Vehicular Technology, 2023, 72(10): 13406-13416. |
30 | BEZAS K, TSOUMANIS G, ANGELIS C T, et al. Coverage path planning and point-of-interest detection using autonomous drone swarms[J]. Sensors, 2022, 22(19): No.7551. |
31 | DENG L, YUAN H, HUANG L, et al. Post-earthquake search via an autonomous UAV: hybrid algorithm and 3D path planning[C]// Proceedings of the 14th International Conference on Natural Computation, Fuzzy Systems and Knowledge Discovery. Piscataway: IEEE, 2018: 1329-1334. |
32 | AIMAIKI F A, SOUFIENE B O. Modifying Hata-Davidson propagation model for remote sensing in complex environments using a multifactional drone[J]. Sensors, 2022, 22(5): No.1786. |
33 | MA Z, GONG H, WANG X. An UAV path planning method in complex mountainous area based on a new improved ant colony algorithm[C]// Proceedings of the 2019 International Conference on Artificial Intelligence and Advanced Manufacturing. Piscataway: IEEE, 2019: 125-129. |
34 | GUO H, ZHOU X, WANG Y, et al. Achieve load balancing in multi-UAV edge computing IoT networks: a dynamic entry and exit mechanism[J]. IEEE Internet of Things Journal, 2022, 9(19): 18725-18736. |
35 | GOUSIOS G. Big data software analytics with Apache Spark[C]// Proceedings of the ACM/IEEE 40th International Conference on Software Engineering: Companion. New York: ACM, 2018: 542-543. |
36 | UCHOA E, PECIN D, PESSOA A, et al. New benchmark instances for the capacitated vehicle routing problem[J]. European Journal of Operational Research, 2017, 257(3): 845-858. |
[1] | Runze TIAN, Yulong ZHOU, Hong ZHU, Gang XUE. Local information based path selection algorithm for service migration [J]. Journal of Computer Applications, 2024, 44(7): 2168-2174. |
[2] | Tian MA, Runtao XI, Jiahao LYU, Yijie ZENG, Jiayi YANG, Jiehui ZHANG. Mobile robot 3D space path planning method based on deep reinforcement learning [J]. Journal of Computer Applications, 2024, 44(7): 2055-2064. |
[3] | Jianqiang LI, Zhou HE. Hybrid NSGA-Ⅱ for vehicle routing problem with multi-trip pickup and delivery [J]. Journal of Computer Applications, 2024, 44(4): 1187-1194. |
[4] | Haixin HUANG, Guangwei YU, Shoushan CHENG, Chunming LI. Full coverage path planning of bridge inspection wall-climbing robot based on improved grey wolf optimization [J]. Journal of Computer Applications, 2024, 44(3): 966-971. |
[5] | Ziyang SONG, Junhuai LI, Huaijun WANG, Xin SU, Lei YU. Path planning algorithm of manipulator based on path imitation and SAC reinforcement learning [J]. Journal of Computer Applications, 2024, 44(2): 439-444. |
[6] | Yongdi LI, Caihong LI, Yaoyu ZHANG, Guosheng ZHANG. Mobile robot path planning based on improved SAC algorithm [J]. Journal of Computer Applications, 2023, 43(2): 654-660. |
[7] | Lin HUANG, Qiang FU, Nan TONG. Solving robot path planning problem by adaptively adjusted Harris hawk optimization algorithm [J]. Journal of Computer Applications, 2023, 43(12): 3840-3847. |
[8] | Longbao WANG, Yinqi LUAN, Liang XU, Xin ZENG, Shuai ZHANG, Shufang XU. Route planning method of UAV swarm based on dynamic cluster particle swarm optimization [J]. Journal of Computer Applications, 2023, 43(12): 3816-3823. |
[9] | Jiahao ZHU, Wei ZHENG, Fengyu YANG, Xin FAN, Peng XIAO. Software quality prediction based on back propagation neural network optimized by ant colony optimization algorithm [J]. Journal of Computer Applications, 2023, 43(11): 3568-3573. |
[10] | Chen LIU, Yang CHEN, Hao FU. UAV path planning for persistent monitoring based on value function iteration [J]. Journal of Computer Applications, 2023, 43(10): 3290-3296. |
[11] | Houming FAN, Shuang MU, Lijun YUE. Collaborative optimization of automated guided vehicle scheduling and path planning considering conflict and congestion [J]. Journal of Computer Applications, 2022, 42(7): 2281-2291. |
[12] | Shuning HAN, Min XU, Xueshi DONG, Qing LIN, Fanfan SHEN. Hybrid ITÖ algorithm for multi-scale colored traveling salesman problem [J]. Journal of Computer Applications, 2022, 42(3): 695-700. |
[13] | Sheng CHEN, Jun ZHOU, Xiaobing HU, Ji MA. Optimization of airport arrival procedures based on hybrid simulated annealing algorithm [J]. Journal of Computer Applications, 2022, 42(2): 606-615. |
[14] | Rongrong DAI, Honghui LI, Xueliang FU. Data center flow scheduling mechanism based on differential evolution and ant colony optimization algorithm [J]. Journal of Computer Applications, 2022, 42(12): 3863-3869. |
[15] | LI Kairong, LIU Shuang, HU Qianqian, TANG Yiyuan. Improved ant colony optimization algorithm for path planning based on turning angle constraint [J]. Journal of Computer Applications, 2021, 41(9): 2560-2568. |
Viewed | ||||||
Full text |
|
|||||
Abstract |
|
|||||