Title |
Multi-Robot Task Allocation Optimizer Using Seeding Genetic Algorithm Based on A* Algorithm and DBSCAN Clustering |
Authors |
서장호(JangHo Seo) ; 이준우(Joonwoo Leerk) |
DOI |
https://doi.org/10.5370/KIEE.2025.74.4.683 |
Keywords |
Multi-Robot Task Allocation; A* Algorithm; DBSCAN; Seeding Genetic Algorithm; Makespan Minimization; Task Clustering; Industrial Applications; Optimization; Genetic Algorithm; Path Planning |
Abstract |
In recent years, robotics technology has made significant advancements, particularly in multi-robot systems where efficient task allocation plays a crucial role in maximizing productivity and minimizing operational time. Previous research has explored various approaches to solving the Multi-Robot Task Allocation problem, but many have faced challenges in task distribution efficiency. To address this issue, we propose a Seeding Genetic Algorithm based on the A* algorithm and DBSCAN clustering. The A* algorithm performs path optimization in a grid environment with obstacles, while DBSCAN clusters tasks to enhance efficient task allocation. By seeding GA with these optimized solutions, the algorithm achieves faster convergence and higher solution quality. Simulations conducted on two maps with different robot configurations show that the A*-DBSCAN Seeding GA outperforms traditional GA and Greedy methods. The proposed method reduced the makespan, and its statistical significance was verified through ANOVA tests. This research contributes to improving multi-robot collaboration in industrial applications, offering an effective solution to the MRTA problem, reducing task completion time, and enhancing system efficiency. |