Nội dung được dịch bởi AI, chỉ mang tính chất tham khảo
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
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
