A Multi-Robot Task Allocation Method Based on the Synergy of the K-Means++ Algorithm and the Particle Swarm Algorithm
Addressing challenges in the traditional K-means algorithm, such as the challenge of selecting initial clustering center points and the lack of a maximum limit on the number of clusters, and where the set of tasks in the clusters is not reasonably sorted after the task assignment, which makes the co...
| Main Authors: | , , , |
|---|---|
| 格式: | Article |
| 語言: | English |
| 出版: |
MDPI AG
2024-11-01
|
| 叢編: | Biomimetics |
| 主題: | |
| 在線閱讀: | https://www.mdpi.com/2313-7673/9/11/694 |
| _version_ | 1826961232717938688 |
|---|---|
| author | Youdong Yuan Ping Yang Hanbing Jiang Tiange Shi |
| author_facet | Youdong Yuan Ping Yang Hanbing Jiang Tiange Shi |
| author_sort | Youdong Yuan |
| collection | DOAJ |
| description | Addressing challenges in the traditional K-means algorithm, such as the challenge of selecting initial clustering center points and the lack of a maximum limit on the number of clusters, and where the set of tasks in the clusters is not reasonably sorted after the task assignment, which makes the cooperative operation of multiple robots inefficient, this paper puts forward a multi-robot task assignment method based on the synergy of the K-means++ algorithm and the particle swarm optimization (PSO) algorithm. According to the processing capability of the robots, the K-means++ algorithm that limits the maximum number of clusters is used to cluster the target points of the task. The clustering results are assigned to the multi-robot system using the PSO algorithm based on the distances between the robots and the centers of the clusters, which divides the multi-robot task assignment problem into a multiple traveling salesmen problem. Then, the PSO algorithm is used to optimize the ordering of the task sets in each cluster for the multiple traveling salesmen problem. An experimental verification platform is established by building a simulation and physical experiment platform utilizing the Robot Operating System (ROS). The findings indicate that the proposed algorithm outperforms both the clustering-based market auction algorithm and the non-clustering particle swarm algorithm, enhancing the efficiency of collaborative operations among multiple robots. |
| first_indexed | 2025-02-18T01:19:28Z |
| format | Article |
| id | doaj.art-e66af710fe7845d6ab24f4cb15b03d1c |
| institution | Directory Open Access Journal |
| issn | 2313-7673 |
| language | English |
| last_indexed | 2025-02-18T01:19:28Z |
| publishDate | 2024-11-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Biomimetics |
| spelling | doaj.art-e66af710fe7845d6ab24f4cb15b03d1c2024-11-26T17:53:45ZengMDPI AGBiomimetics2313-76732024-11-0191169410.3390/biomimetics9110694A Multi-Robot Task Allocation Method Based on the Synergy of the K-Means++ Algorithm and the Particle Swarm AlgorithmYoudong Yuan0Ping Yang1Hanbing Jiang2Tiange Shi3School of Electromechanical Engineering, Lanzhou University of Technology, Lanzhou 730050, ChinaSchool of Electromechanical Engineering, Lanzhou University of Technology, Lanzhou 730050, ChinaSchool of Electromechanical Engineering, Lanzhou University of Technology, Lanzhou 730050, ChinaSchool of Electromechanical Engineering, Lanzhou University of Technology, Lanzhou 730050, ChinaAddressing challenges in the traditional K-means algorithm, such as the challenge of selecting initial clustering center points and the lack of a maximum limit on the number of clusters, and where the set of tasks in the clusters is not reasonably sorted after the task assignment, which makes the cooperative operation of multiple robots inefficient, this paper puts forward a multi-robot task assignment method based on the synergy of the K-means++ algorithm and the particle swarm optimization (PSO) algorithm. According to the processing capability of the robots, the K-means++ algorithm that limits the maximum number of clusters is used to cluster the target points of the task. The clustering results are assigned to the multi-robot system using the PSO algorithm based on the distances between the robots and the centers of the clusters, which divides the multi-robot task assignment problem into a multiple traveling salesmen problem. Then, the PSO algorithm is used to optimize the ordering of the task sets in each cluster for the multiple traveling salesmen problem. An experimental verification platform is established by building a simulation and physical experiment platform utilizing the Robot Operating System (ROS). The findings indicate that the proposed algorithm outperforms both the clustering-based market auction algorithm and the non-clustering particle swarm algorithm, enhancing the efficiency of collaborative operations among multiple robots.https://www.mdpi.com/2313-7673/9/11/694multi-robotparticle swarm algorithmtask allocationK-means++ clustering |
| spellingShingle | Youdong Yuan Ping Yang Hanbing Jiang Tiange Shi A Multi-Robot Task Allocation Method Based on the Synergy of the K-Means++ Algorithm and the Particle Swarm Algorithm Biomimetics multi-robot particle swarm algorithm task allocation K-means++ clustering |
| title | A Multi-Robot Task Allocation Method Based on the Synergy of the K-Means++ Algorithm and the Particle Swarm Algorithm |
| title_full | A Multi-Robot Task Allocation Method Based on the Synergy of the K-Means++ Algorithm and the Particle Swarm Algorithm |
| title_fullStr | A Multi-Robot Task Allocation Method Based on the Synergy of the K-Means++ Algorithm and the Particle Swarm Algorithm |
| title_full_unstemmed | A Multi-Robot Task Allocation Method Based on the Synergy of the K-Means++ Algorithm and the Particle Swarm Algorithm |
| title_short | A Multi-Robot Task Allocation Method Based on the Synergy of the K-Means++ Algorithm and the Particle Swarm Algorithm |
| title_sort | multi robot task allocation method based on the synergy of the k means algorithm and the particle swarm algorithm |
| topic | multi-robot particle swarm algorithm task allocation K-means++ clustering |
| url | https://www.mdpi.com/2313-7673/9/11/694 |
| work_keys_str_mv | AT youdongyuan amultirobottaskallocationmethodbasedonthesynergyofthekmeansalgorithmandtheparticleswarmalgorithm AT pingyang amultirobottaskallocationmethodbasedonthesynergyofthekmeansalgorithmandtheparticleswarmalgorithm AT hanbingjiang amultirobottaskallocationmethodbasedonthesynergyofthekmeansalgorithmandtheparticleswarmalgorithm AT tiangeshi amultirobottaskallocationmethodbasedonthesynergyofthekmeansalgorithmandtheparticleswarmalgorithm AT youdongyuan multirobottaskallocationmethodbasedonthesynergyofthekmeansalgorithmandtheparticleswarmalgorithm AT pingyang multirobottaskallocationmethodbasedonthesynergyofthekmeansalgorithmandtheparticleswarmalgorithm AT hanbingjiang multirobottaskallocationmethodbasedonthesynergyofthekmeansalgorithmandtheparticleswarmalgorithm AT tiangeshi multirobottaskallocationmethodbasedonthesynergyofthekmeansalgorithmandtheparticleswarmalgorithm |