《计算机应用》唯一官方网站 ›› 2024, Vol. 44 ›› Issue (10): 3232-3239.DOI: 10.11772/j.issn.1001-9081.2023101432

• 前沿与综合应用 • 上一篇    下一篇

地震场景下无人机群路径规划与任务分配均衡联合优化

孙鉴1,2(), 马宝全1, 吴隹伟1, 杨晓焕1, 武涛1, 陈攀1   

  1. 1.北方民族大学 计算机科学与工程学院,银川 750021
    2.图像图形智能处理国家民委重点实验室(北方民族大学),银川 750021
  • 收稿日期:2023-10-23 修回日期:2023-12-19 接受日期:2023-12-26 发布日期:2024-10-15 出版日期:2024-10-10
  • 通讯作者: 孙鉴
  • 作者简介:孙鉴(1982—),男,山东烟台人,讲师,博士,CCF会员,主要研究方向:大数据存储与管理 2014132@nun.edu.cn
    马宝全(1997—),男(回族),宁夏银川人,硕士研究生,CCF会员,主要研究方向:移动边缘计算、大数据存储与管理
    吴隹伟(1998—),男,湖南长沙人,硕士研究生,CCF会员,主要研究方向:任务调度、大数据存储与管理
    杨晓焕(1998—),女,山西平遥人,硕士研究生,CCF会员,主要研究方向:大数据存储与管理
    武涛(1998—),男,山西大同人,硕士研究生,CCF会员,主要研究方向:任务调度
    陈攀(1996—),男,湖南长沙人,硕士研究生,CCF会员,主要研究方向:大数据存储与管理。
  • 基金资助:
    国家自然科学基金资助项目(62062002);宁夏自然科学基金资助项目(2022AAC03289);北方民族大学研究生创新项目(YCX23155)

Joint optimization of UAV swarm path planning and task allocation balance in earthquake scenarios

Jian SUN1,2(), Baoquan MA1, Zhuiwei WU1, Xiaohuan YANG1, Tao WU1, Pan CHEN1   

  1. 1.School of Computer Science and Engineering,North Minzu University,Yinchuan Ningxia 750021,China
    2.Key Laboratory of Images and Graphic Intelligent Processing of State Ethnic Affairs Commission (North Minzu University),Yinchuan Ningxia 750021,China
  • 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.
    WU Zhuiwei, born in 1998, M. S. candidate. His research interests include task scheduling, big data storage and management.
    YANG Xiaohuan, born in 1998, M. S. candidate. Her research interests include big data storage and management.
    WU Tao, born in 1998, M. S. candidate. His research interests include task scheduling.
    CHEN Pan, born in 1996, M. S. candidate. His research interests include big data storage and management.
  • Supported by:
    National Natural Science Foundation of China(62062002);Ningxia Natural Science Foundation(2022AAC03289);Graduate Innovation Project of North Minzu University(YCX23155)

摘要:

无人机(UAV)群路径规划和任务分配是UAV群救援应用的核心,然而传统方法分开求解路径规划与任务分配,导致资源分配不均。为了解决上述问题,结合UAV群的物理属性与应用环境因素,改进蚁群算法(ACO),提出联合并行蚁群(JPACO)模型。首先,借助分级信息素增强系数机制更新信息素,以提高JPACO任务分配均衡性和能耗均衡性;其次,设计路径平衡因子和动态概率转移因子优化蚁群模型易陷入局部收敛的情况,从而提高JPACO的全局搜索能力;最后,引入集群并行处理机制,以降低JPACO运算耗时。将JPACO与自适应动态蚁群算法(ADACO)、扫描动态蚁群算法(SMACO)、贪婪策略蚁群算法(GSACO)和交叉蚁群算法(IACO)在公开数据集CVRPLIB上对比最优路径、任务分配均衡、能耗均衡和运算耗时。实验结果表明:与IACO和ADACO相比,JPACO处理小规模运算的最优路径平均值分别降低7.4%和16.3%;处理大规模运算的求解耗时与GSACO、ADACO相比降低8.2%和22.1%。以上结果验证了JPACO在处理小规模运算时能够改善最优路径,处理大规模运算时任务分配均衡、能耗均衡和运算耗时明显优于对比算法。

关键词: 路径规划, 任务均衡, 能耗均衡, 蚁群算法, 无人机群, 集群并行处理

Abstract:

Unmanned Aerial Vehicle (UAV) swarm path planning and task allocation are the cores of UAV swarm rescue applications. However, traditional methods solve path planning and task allocation separately, resulting in uneven resource allocation. In order to solve the above problem, combined with the physical attributes and application environmental factors of UAV swarm, the Ant Colony Optimization (ACO) was improved, and a Joint Parallel ACO (JPACO) was proposed. Firstly, the pheromone was updated by the hierarchical pheromone enhancement coefficient mechanism to improve the performance of JPACO task allocation balance and energy consumption balance. Secondly, the path balance factor and dynamic probability transfer factor were designed to optimize the ant colony model, which is easy to fall into local convergence, so as to improve the global search capability of JPACO. Finally, the cluster parallel processing mechanism was introduced to reduce the time consumption of JPACO operation. JPACO was compared with Adaptive Dynamic ACO (ADACO), Scanning Motion ACO (SMACO), Greedy Strategy ACO (GSACO) and Intersecting ACO (IACO) in terms of optimal path, task allocation balance, energy consumption balance and operation time on the open dataset CVRPLIB. Experimental results show that the average value of the optimal paths of JPACO is 7.4% and 16.3% lower than of IACO and ADACO respectively in processing small-scale operations. Compared with GSACO and ADACO, JPACO has the solution time reduced by 8.2% and 22.1% in large-scale operations. It is verified that JPACO can improve the optimal path when dealing with small-scale operations, and is obviously superior to the comparison algorithms in terms of task allocation balance, energy consumption balance, and operation time consumption when processing large-scale operations.

Key words: path planning, task balance, energy consumption balance, Ant Colony Optimization (ACO), Unmanned Aerial Vehicle (UAV) swarm, cluster parallel processing

中图分类号: