Một phương pháp phân công lại nhiệm vụ phân tán trong môi trường động cho hệ thống đa UAV

Springer Science and Business Media LLC - Tập 52 - Trang 1582-1601 - 2021
Mi Yang1, Wenhao Bi1, An Zhang1, Fei Gao1
1School of Aeronautics, Northwestern Polytechnical University, Xi'an, China

Tóm tắt

Bài báo này xem xét vấn đề phân công lại nhiệm vụ cho các hệ thống Không Người Lái Đường Không (multi-UAV) phân tán trong môi trường động. Đối với vấn đề phân công lại động trong hệ thống đa UAV, thông tin nhiệm vụ có thể chịu tác động từ nhiều sự kiện động khác nhau, và nhiều thuật toán phân bổ nhiệm vụ hiện có yêu cầu nhiều tài nguyên tính toán và truyền thông để đạt được giải pháp khả thi. Do đó, bài báo này đề xuất một phương pháp phân tán để đối phó với các sự kiện động xảy ra trực tuyến trong quá trình thực hiện lịch trình gốc. Đầu tiên, một khung phân tán để xác định chiến lược xử lý theo các loại sự kiện động được giới thiệu. Thứ hai, một thuật toán phân công lại một phần (PRA) được đề xuất để hỗ trợ khung này, và một cơ chế hình thành nhóm con gia tăng cùng với một cơ chế giải phóng một phần được phát triển để giảm tải cho các yêu cầu tính toán và truyền thông. Hơn nữa, một giai đoạn bổ sung đã được sửa đổi nhằm tối đa hóa việc phân công (MIP-MA) cũng được đề xuất trong PRA để tối đa hóa số lượng phân bổ nhiệm vụ. Các mô phỏng số cho thấy phương pháp đề xuất có khả năng cung cấp một giải pháp không xung đột với ít trao đổi dữ liệu và thời gian vận hành hơn.

Từ khóa

#Phân công lại nhiệm vụ #Drones #Hệ thống UAV #Môi trường động #Thuật toán phân bổ nhiệm vụ

Tài liệu tham khảo

Alshawi MA, Shalan MB (2017) Minimal time dynamic task allocation for a swarm of robots. Int J Mech Eng Robot Res 6(6) Badreldin M, Hussein A, Khamis A (2013) A comparative study between optimization and market-based approaches to multi-robot task allocation. Advances in Artificial Intelligence (16877470) Bänziger T, Kunz A, Wegener K (2018) Optimizing human–robot task allocation using a simulation tool based on standardized work descriptions. J Intell Manuf:1–14 Binetti G, Naso D, Turchiano B (2013) Decentralized task allocation for surveillance systems with critical tasks. Robot Auton Syst 61(12):1653–1664 Cao Y, Yu W, Ren W, Chen G (2012) An overview of recent progress in the study of distributed multi-agent coordination. IEEE Trans Ind Inform 9(1):427–438 Chen X, Zhang P, Du G, Li F (2019) A distributed method for dynamic multi-robot task allocation problems with critical time constraints. Robot Auton Syst 118:31–46 Choi HL, Brunet L, How JP (2009) Consensus-based decentralized auctions for robust task allocation. IEEE Trans Robot 25(4):912–926 Chopra S, Notarstefano G, Rice M, Egerstedt M (2017) A distributed version of the hungarian method for multirobot assignment. IEEE Trans Robot 33(4):932–947 Farinelli A, Iocchi L, Nardi D (2017) Distributed on-line dynamic task assignment for multi-robot patrolling. Auton Robot 41(6):1321–1345 Fu X, Feng P, Gao X (2019) Swarm uavs task and resource dynamic assignment algorithm based on task sequence mechanism. IEEE Access 7:41090–41100 Geng N, Meng Q, Gong D, Chung PW (2018) How good are distributed allocation algorithms for solving urban search and rescue problems? a comparative study with centralized algorithms. IEEE Trans Autom Sci Eng 16(1):478–485 Gerkey BP, Matarić MJ (2004) A formal analysis and taxonomy of task allocation in multi-robot systems. Int J Robot Res 23(9):939–954 Huang H, Zhuo T (2019) Multi-model cooperative task assignment and path planning of multiple ucav formation. Multimed Tools Appl 78(1):415–436 Jang I, Shin HS, Tsourdos A (2018) Anonymous hedonic game for task allocation in a large-scale multiple agent system. IEEE Trans Robot 34(6):1534–1548 Jia Z, Yu J, Ai X, Xu X, Yang D (2018) Cooperative multiple task assignment problem with stochastic velocities and time windows for heterogeneous unmanned aerial vehicles using a genetic algorithm. Aerosp Sci Technol 76:112–125 Johnson L, Ponda S, Choi HL, How J (2011) Asynchronous decentralized task allocation for dynamic environments. In: Infotech@ aerospace, vol 2011, pp 1441 Kapoutsis AC, Chatzichristofis SA, Doitsidis L, de Sousa JB, Pinto J, Braga J, Kosmatopoulos EB (2016) Real-time adaptive multi-robot exploration with application to underwater map construction. Auton Robot 40(6):987–1015 Korsah GA, Stentz A, Dias MB (2013) A comprehensive taxonomy for multi-robot task allocation. Int J Robot Res 32(12):1495–1512 Lim WH, Isa NAM (2015) Particle swarm optimization with dual-level task allocation. Eng Appl Artif Intell 38:88–110 Luo L, Chakraborty N, Sycara K (2015) Distributed algorithms for multirobot task assignment with task deadline constraints. IEEE Trans Autom Sci Eng 12(3):876–888 Nayak S, Yeotikar S, Carrillo E, Rudnick-Cohen E, Jaffar MKM, Patel R, Azarm S, Herrmann JW, Xu H, Otte M (2020) Experimental comparison of decentralized task allocation algorithms under imperfect communication. IEEE Robot Autom Letts 5(2):572–579 Nelke SA, Okamoto S, Zivan R (2020) Market clearing–based dynamic multi-agent task allocation. ACM Trans Intell Syst Technol (TIST) 11(1):1–25 Nunes E, Manner M, Mitiche H, Gini M (2017) A taxonomy for task allocation problems with temporal and ordering constraints. Robot Auton Syst 90:55–70 Oh G, Kim Y, Ahn J, Choi HL (2017) Market-based task assignment for cooperative timing missions in dynamic environments. J Intell Robot Syst 87(1):97–123 Otte M, Kuhlman MJ, Sofge D (2020) Auctions for multi-robot task allocation in communication limited environments. Auton Robot 44(3):547–584 Schillinger P, Bürger M, Dimarogonas DV (2018) Simultaneous task allocation and planning for temporal logic goals in heterogeneous multi-robot systems. Int J Robot Res 37(7):818– 838 Seenu N, RM KC, Ramya M, Janardhanan MN (2020) Review on state-of-the-art dynamic task allocation strategies for multiple-robot systems. Industrial Robot: the international journal of robotics research and application Torreño A, Onaindia E, Komenda A, Štolba M (2018) Cooperative multi-agent planning: A survey. ACM Comput Surv (CSUR) 50(6):84 Turner J, Meng Q, Schaefer G, Whitbrook A, Soltoggio A (2017) Distributed task rescheduling with time constraints for the optimization of total task allocations in a multirobot system. IEEE Trans Cybern 48(9):2583–2597 Wang C, Mu D, Zhao F, Sutherland JW (2015) A parallel simulated annealing method for the vehicle routing problem with simultaneous pickup–delivery and time windows. Comput Ind Eng 83:111–122 Wei C, Hindriks KV, Jonker CM (2016) Dynamic task allocation for multi-robot search and retrieval tasks. Appl Intell 45(2):383–401 Whitbrook A, Meng Q, Chung PW (2017) Reliable, distributed scheduling and rescheduling for time-critical, multiagent systems. IEEE Trans Autom Sci Eng 15(2):732–747 Whitbrook A, Meng Q, Chung PW (2019) Addressing robustness in time-critical, distributed, task allocation algorithms. Appl Intell 49(1):1–15 Wu H, Li H, Xiao R, Liu J (2018a) Modeling and simulation of dynamic ant colony’s labor division for task allocation of uav swarm. Physica A: Stat Mech Appl 491:127–141 Wu W, Cui N, Shan W, Wang X (2018b) Distributed task allocation for multiple heterogeneous uavs based on consensus algorithm and online cooperative strategy. Aircraft Engineering and Aerospace Technology Xie S, Zhang A, Bi W, Tang Y (2019) Multi-uav mission allocation under constraint. Appl Sci 9(11):2184 Yao W, Qi N, Wan N, Liu Y (2019) An iterative strategy for task assignment and path planning of distributed multiple unmanned aerial vehicles. Aerosp Sci Technol 86:455–464 Ye F, Chen J, Sun Q, Tian Y, Jiang T (2021) Decentralized task allocation for heterogeneous multi-uav system with task coupling constraints. J Supercomput 77(1):111–132 Zhang A, Zhou D, Yang M, Yang P (2018) Finite-time formation control for unmanned aerial vehicle swarm system with time-delay and input saturation. IEEE Access 7:5853–5864 Zhao W, Meng Q, Chung PW (2015) A heuristic distributed task allocation method for multivehicle multitask problems and its application to search and rescue scenario. IEEE Trans Cybern 46(4):902–915 Zhou X, Wang H, Ding B, Hu T, Shang S (2019) Balanced connected task allocations for multi-robot systems: an exact flow-based integer program and an approximate tree-based genetic algorithm. Expert Syst Appl 116:10–20 Zhu W, Li L, Teng L, Yonglu W (2018) Multi-uav reconnaissance task allocation for heterogeneous targets using an opposition-based genetic algorithm with double-chromosome encoding. Chin J Aeronaut 31 (2):339–350 Zitouni F, Harous S, Maamri R (2020) A distributed approach to the multi-robot task allocation problem using the consensus-based bundle algorithm and ant colony system. IEEE Access 8:27479–27494