Research on Task Allocation of Heterogeneous Multi-Robot Based on Cluster Grouping Algorithm
In the urban combat environments, multiple heterogeneous air-to-ground robots need to process large-scale task targets with time window constraints. In order to ensure fast and effective strategic execution, an acceptable suboptimal task allocation strategy needs to be quickly calculated. This paper...
| Main Author: | |
|---|---|
| Format: | Article |
| Language: | zho |
| Published: |
Editorial Office of Aero Weaponry
2022-08-01
|
| Series: | Hangkong bingqi |
| Subjects: | |
| Online Access: | https://www.aeroweaponry.avic.com/fileup/1673-5048/PDF/2021-00249.pdf |
| _version_ | 1811181574603931648 |
|---|---|
| author | Zheng Xiyu, Xu Ziyu, Wang Jinghua |
| author_facet | Zheng Xiyu, Xu Ziyu, Wang Jinghua |
| author_sort | Zheng Xiyu, Xu Ziyu, Wang Jinghua |
| collection | DOAJ |
| description | In the urban combat environments, multiple heterogeneous air-to-ground robots need to process large-scale task targets with time window constraints. In order to ensure fast and effective strategic execution, an acceptable suboptimal task allocation strategy needs to be quickly calculated. This paper proposes a cluster grouping consensus-based bundle algorithm (C-CBBA) for large-scale task assignment problems with time window constraints. Firstly, the task target points and robots are grouped, and the large-scale problems are tranformed into small-scale problems. The grouping algorithm includes three stages: the K-Means algorithm is used to preliminarily classify the task points accor-ding to the principle of nearest distance, the task point group of each group is adjusted so that it does not exceed the upper load limit of each pre-assigned robot group, and the delay acceptance algorithm (DA) is used to assign the nearest robot to each group. Finally, the improved consensus-based bundle algorithm (CBBA) is used to solve each sub-pro-blem. Simulation results show that the proposed algorithm has high task completion and effectively reduces communication between robots. |
| first_indexed | 2024-04-11T09:19:46Z |
| format | Article |
| id | doaj.art-db1db7860f1f48b8b4528cae5d90b856 |
| institution | Directory Open Access Journal |
| issn | 1673-5048 |
| language | zho |
| last_indexed | 2024-04-11T09:19:46Z |
| publishDate | 2022-08-01 |
| publisher | Editorial Office of Aero Weaponry |
| record_format | Article |
| series | Hangkong bingqi |
| spelling | doaj.art-db1db7860f1f48b8b4528cae5d90b8562022-12-22T04:32:14ZzhoEditorial Office of Aero WeaponryHangkong bingqi1673-50482022-08-0129410010910.12132/ISSN.1673-5048.2021.0249Research on Task Allocation of Heterogeneous Multi-Robot Based on Cluster Grouping AlgorithmZheng Xiyu, Xu Ziyu, Wang Jinghua01. College of Mechanical and Electric Engineering, Changchun University of Science and Technology, Changchun 130022, China;2. Ministry of Education Key Laboratory for Cross-Scale Micro and Nano Manufacturing, Changchun University of Science and Technology, Changchun 130022, ChinaIn the urban combat environments, multiple heterogeneous air-to-ground robots need to process large-scale task targets with time window constraints. In order to ensure fast and effective strategic execution, an acceptable suboptimal task allocation strategy needs to be quickly calculated. This paper proposes a cluster grouping consensus-based bundle algorithm (C-CBBA) for large-scale task assignment problems with time window constraints. Firstly, the task target points and robots are grouped, and the large-scale problems are tranformed into small-scale problems. The grouping algorithm includes three stages: the K-Means algorithm is used to preliminarily classify the task points accor-ding to the principle of nearest distance, the task point group of each group is adjusted so that it does not exceed the upper load limit of each pre-assigned robot group, and the delay acceptance algorithm (DA) is used to assign the nearest robot to each group. Finally, the improved consensus-based bundle algorithm (CBBA) is used to solve each sub-pro-blem. Simulation results show that the proposed algorithm has high task completion and effectively reduces communication between robots.https://www.aeroweaponry.avic.com/fileup/1673-5048/PDF/2021-00249.pdf|cluster grouping|multi-robot system|time window|task allocation|cbba algorithm|unmanned system|combat |
| spellingShingle | Zheng Xiyu, Xu Ziyu, Wang Jinghua Research on Task Allocation of Heterogeneous Multi-Robot Based on Cluster Grouping Algorithm Hangkong bingqi |cluster grouping|multi-robot system|time window|task allocation|cbba algorithm|unmanned system|combat |
| title | Research on Task Allocation of Heterogeneous Multi-Robot Based on Cluster Grouping Algorithm |
| title_full | Research on Task Allocation of Heterogeneous Multi-Robot Based on Cluster Grouping Algorithm |
| title_fullStr | Research on Task Allocation of Heterogeneous Multi-Robot Based on Cluster Grouping Algorithm |
| title_full_unstemmed | Research on Task Allocation of Heterogeneous Multi-Robot Based on Cluster Grouping Algorithm |
| title_short | Research on Task Allocation of Heterogeneous Multi-Robot Based on Cluster Grouping Algorithm |
| title_sort | research on task allocation of heterogeneous multi robot based on cluster grouping algorithm |
| topic | |cluster grouping|multi-robot system|time window|task allocation|cbba algorithm|unmanned system|combat |
| url | https://www.aeroweaponry.avic.com/fileup/1673-5048/PDF/2021-00249.pdf |
| work_keys_str_mv | AT zhengxiyuxuziyuwangjinghua researchontaskallocationofheterogeneousmultirobotbasedonclustergroupingalgorithm |