时间窗约束下的无人集群分布式任务分配算法

李瑞琳; 崔巍; 冯彦翔; 杨宜康

doi:10.15892/j.cnki.djzdxb.2023.03.003

弹箭与制导学报 >

2023 , Vol. 43 >Issue 3: 16 - 25

DOI: https://doi.org/10.15892/j.cnki.djzdxb.2023.03.003

时间窗约束下的无人集群分布式任务分配算法

李瑞琳 ,
崔巍 ,
冯彦翔 ,
杨宜康

展开

西安交通大学自动化科学与工程学院,陕西西安 710049

杨宜康(1974—),男,教授,博士,研究方向:超大规模互联网星座优化与调度。

李瑞琳(1999—),女,硕士研究生,研究方向:任务规划。

收稿日期: 2023-02-04

网络出版日期: 2025-02-07

基金资助

科技部2020年度科技创新2030-“新一代人工智能”重大项目(2020AAA0108200)

收起

Distributed Task Allocation Algorithm for Unmanned Cluster with Time Window Constraints

LI Ruilin ,
CUI Wei ,
FENG Yanxiang ,
YANG Yikang

Expand

School of Automation Science and Engineering,Xi'an Jiaotong University,Xi'an 710049,Shaanxi, China

Received date: 2023-02-04

Online published: 2025-02-07

Fold

摘要

综合考虑任务时间窗以及无人机能力约束,以任务的平均时间成本最小为优化目标,提出一种无人集群分布式协同任务分配算法。首先,定义任务对于无人机的增益和边际增益,用以描述无人机执行任务的时间成本的变化情况。然后,建立包括任务添加、冲突消解和任务再分配三个阶段的分布式分配算法。最后,仿真实验结果表明:第三个阶段将任务完全分配率提高了13.76%,相比现有算法,所提算法将任务完全分配率提高了21.94%,任务平均完成时间降低了24.25 s。

关键词： 无人集群系统; 时间窗约束; 任务分配; 分布式算法

本文引用格式

李瑞琳 , 崔巍 , 冯彦翔 , 杨宜康 . 时间窗约束下的无人集群分布式任务分配算法[J]. 弹箭与制导学报, 2023 , 43(3) : 16 -25 . DOI: 10.15892/j.cnki.djzdxb.2023.03.003

Abstract

Considering the constraints of task time window and UAV capability, and taking the minimum average time cost of tasks as the optimization objective, a distributed collaborative task allocation algorithm for unmanned cluster is proposed. First, the gain and marginal gain of tasks for UAVs are defined to describe the change of the time cost of UAVs to perform tasks. Then, a distributed allocation algorithm is established, which includes three stages: task addition, conflict resolution and task reallocation. Finally, the experimental results show that the third stage increases the task complete allocation rate by 13.76%, the proposed algorithm increases the task complete allocation rate by 21.94%, and the average task completion time decreases by 24.25 s.

Key words： unmanned cluster system; time window constraint; task assignment; distributed algorithm

[an error occurred while processing this directive]

参考文献

原文顺序 | 文献年度倒序 | 文中引用次数倒序

[1]	YU X, GAO X, WANG L, et al. Cooperative multi-UAV task assignment in cross-regional joint operations considering ammunition inventory[J]. Drones, 2022, 6(3): 77.

[2]	岳源, 屈高敏. 分布式多无人机协同侦察目标分配研究[J]. 兵器装备工程学报, 2018(3): 57-61, 82. YUE Y, QU G M. Research on distributed multi-UAV cooperative reconnaissance task allocation[J]. Journal of Ordnance Equipment Engineering, 2018(3): 57-61.

[3]	CHEN Y, YANG D, YU J. Multi-UAV task assignment with parameter and time-sensitive uncertainties using modified two-part wolf pack search algorithm[J]. IEEE Transactions on Aerospace and Electronic Systems, 2018, 54(6): 2853-2872.

[4]	齐小刚, 李博, 范英盛, 等. 多约束下多无人机的任务规划研究综述[J]. 智能系统学报, 2020, 15(2): 204-217. QI X G, LI B, FAN Y S, et al. A survey of mission planning on UAVs systems based on multiple constraints[J]. CAAI Transactions on Intelligent Systems, 2020, 15(2): 204-217.

[5]	RABIL B S, FAHMY M A, ALY G M. Traveling salesman problem for surveillance mission using particle swarm optimization[C]// IEEE. Proceedings of the 2007 IEEE Congress on Evolutionary Computation. New York: IEEE, 2007: 2137-2145.

[6]	O'ROURKE K P, CARLTON W B, BAILEY T G, et al. Dynamic routing of unmanned aerial vehicles using reactive tabu search[J]. Military Operations Research, 2001, 6(1): 5-30.

[7]	DARRAH M A, NILAND W M, STOLARIK B M. Multiple UAV dynamic task allocation using mixed integer linear programming in a SEAD mission: AIAA 2005-7164[R]. Reston: AIAA, 2005.

[8]	郑玉会. 多无人机任务分配算法研究[D]. 西安: 西安电子科技大学, 2018. ZHENG Y H. On task allocation algorithms for multi-UAV[D]. Xi'an: Xidian University, 2018.

[9]	邓启波. 多无人机协同任务规划技术研究[D]. 北京: 北京理工大学, 2014. DENG Q B. Cooperative task planning of multiple unmanned aerial vehicles[D]. Beijing: Beijing Institute of Technology, 2014.

[10]	SUN Y X, WU H S, ZHAN R J. Optimal scheduling method of marine transportation resources based on wolf swarm algorithm[J]. Journal of Coastal Research, 2019, 93: 646-651.

[11]	ZHAO J W, ZHAO J J. Study on multi-UAV task clustering and task planning in cooperative reconnaissance[C]// IEEE. Proceedings of the 2014 6th International Conference on Intelligent Human-machine Systems and Cybernetics (IHMSC). New York: IEEE, 2014: 3923-3931.

[12]	杜永浩, 邢立宁, 蔡昭权. 无人飞行器集群智能调度技术综述[J]. 自动化学报, 2020, 46(2): 222-241. DU Y H, XING L N, CAI Z Q. Survey on intelligent scheduling technologies for unmanned flying craft clusters[J]. Acta Automatica Sinica, 2020, 46(2): 222-241.

[13]	汪汝根, 李为民, 刘永兰, 等. 无人机集群组网任务分配方法研究[J]. 系统仿真学报, 2018, 30(12): 4794-4802. DOI WANG R G, LI W M, LIU Y L, et al. Research on task allocation method of unmanned aerial vehicle cluster network[J]. Journal of System Simulation, 2018, 30(12): 4794-4802. DOI

[14]	KE S, KARUNGARU S, FENG Z, et al. AGA-ACO hybrid algorithm for the multi-UAV mission planning problem[C]// IEEE. Proceedings of the 2014 International Symposium on Communications & Information Technologies. New York: IEEE, 2014: 1152-1160.

[15]	邓可, 连振江, 周德云, 等. 基于改进量子粒子群算法的多无人机任务分配[J]. 指挥控制与仿真, 2018, 40(5): 32-36. DOI DENG K, LIAN Z J, ZHOU D Y, et al. Task allocation of multi-unmanned aerial vehicle based on improved quantum particle swarm optimization[J]. Command Control & Simulation, 2018, 40(5): 32-36.

[16]	ZHANG Y Z, LI J W, HU B, et al. An improved PSO algorithm for solving multi-UAV cooperative reconnaissance task decision-making problem[C]// IEEE. Proceedings of the 2016 International Conference on Aircraft Utility Systems. New York: IEEE, 2016: 434-437.

[17]	DENG W, ZHANG X, ZHOU Y, et al. An enhanced fast non-dominated solution sorting genetic algorithm for multi-objective problems[J]. Information Sciences, 2022, 585, 441-453.

[18]	邸斌, 周锐, 丁全心. 多无人机分布式协同异构任务分配[J]. 控制与决策, 2013, 28(2): 274-278. DI B, ZHOU R, DING Q X. Distributed coordinated heterogeneous task allocation for unmanned aerial vehicles[J]. Control and Decision, 2013, 28(2): 274-278.

[19]	CHOI H L, BRUNET L, HOW J P. Consensus-based de-centralized auctions for robust task allocation[J]. IEEE Transactions on Robotics, 2009, 25(4): 912-926.

[20]	JOHNSON L B, PONDA S S, CHOI H L, et al. Asynchronous decentralized task allocation for dynamic environments: AIAA 2011-1441[R]. Reston: AIAA, 2011.

[21]	OH G, KIM Y D, AHN J Y, et al. Market-based task assignment for cooperative timing missions in dynamic environments[J]. Journal of Intelligent & Robotic Systems, 2017, 87: 1-27.

[22]	BUCKMAN N, CHOI H L, HOW J P. Partial replanning for decentralized dynamic task allocation: AIAA 2019-0915[R]. Reston: AIAA, 2019.

[23]	QIN B, ZHANG D, TANG S, et al. Distributed grouping cooperative dynamic task assignment method of UAV swarm[J]. Applied Sciences, 2022, 12: 2865-2873.

[24]	ZHAO W, MENG Q, CHUNG P. A heuristic distributed task allocation method for multivehicle multitask problems and its application to search and rescue scenario[J]. IEEE Transactions on Cybernetics, 2015, 46(4): 902-915.

[25]	GENG L, ZHANG Y F, WANG J, et al. Cooperative mission planning with multiple UAVs in realistic environments[J]. Unmanned Systems, 2014, 2(1): 73-86.

[26]	ZHENG X, ZHANG F, SONG T, et al. Heterogeneous Multi-UAV distributed task allocation based on CBBA[C]// IEEE. Proceedings of the 2019 IEEE International Conference on Unmanned Systems (ICUS). New York: IEEE, 2019: 704-709.

[27]	PONDA S, REDDING J, CHOI H L, et al. Decentralized planning for complex missions with dynamic communication constraints[C]// IEEE. Proceedings of the 2010 American Control Conference. New York: IEEE, 2010: 3998-4003.

[28]	WHITBROOK A, MENG Q, CHUNG P. Reliable, distributed scheduling and rescheduling for time-critical, multi-agent systems[J]. IEEE Transactions on Automation Science & Engineering, 2017, 99: 1-16.

[29]	DIAS M B, ZLOT R, KALRA N, et al. Market-based multirobot coordination: a survey and analysis[J]. Proceedings of the IEEE, 2006, 94(7): 1257-1270.

[30]	SARIEL S, BALCH T R. Efficient bids on task allocation for multi-robot exploration[C]// IEEE. Proceedings of the 19th International Florida Artificial Intelligence Research Society Conference. New York: IEEE, 2006: 2124-2130.

[31]	张可为, 赵晓林, 李宗哲, 等. 多无人机侦察任务分配方法研究综述[J]. 电光与控制, 2021, 28(7): 68-72. ZHANG K W, ZHAO X L, LI Z Z, et al. A review of multi-UAV reconnaissance mission assignment methods[J]. Electronics Optics & Control, 2021, 28(7): 68-72.

Options

文章导航