Distributed Task Allocation Algorithm for Unmanned Cluster with Time Window Constraints

LI Ruilin; CUI Wei; FENG Yanxiang; YANG Yikang

doi:10.15892/j.cnki.djzdxb.2023.03.003

Journal of Projectiles, Rockets, Missiles and Guidance >

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

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

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

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

Cite this article

LI Ruilin , CUI Wei , FENG Yanxiang , YANG Yikang . Distributed Task Allocation Algorithm for Unmanned Cluster with Time Window Constraints[J]. Journal of Projectiles, Rockets, Missiles and Guidance, 2023 , 43(3) : 16 -25 . DOI: 10.15892/j.cnki.djzdxb.2023.03.003

[an error occurred while processing this directive]

References

Publishing order | Descend order by publishing year | Descend order by cited within

[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

Outlines