Hybrid Clustering-Enhanced Brain Storm Optimization Algorithm for Efficient Multi-Robot Path Planning

摘要

To address the core challenges in multi-robot path planning (MRPP) within large-scale, complex environments-namely path conflicts, suboptimal task allocation, and computational inefficiency-this paper introduces a Hybrid Clustering-Enhanced Brain Storm Optimization (HC-BSO) algorithm designed to improve both path quality and computational efficiency significantly. For optimizing initial task assignment, the conventional K-Means clustering method is supplanted by a hybrid clustering methodology that integrates Mini-Batch K-Means with Density-Based Spatial Clustering of Applications with Noise (DBSCAN), facilitating an efficient and robust partitioning of task points. Concurrently, we incorporate a two-stage exploration-perturbation evolutionary strategy. This strategy effectively balances global exploration with local exploitation, thereby enhancing solution diversity and search depth. Comparative analyses against the standard Brain Storm Optimization (BSO) and other prominent swarm intelligence algorithms reveal that HC-BSO exhibits significant advantages in terms of total path length, computational time, and path conflict avoidance. Notably, in large-scale, multi-task scenarios, HC-BSO consistently generates high-quality, conflict-free paths, demonstrating superior stability, convergence, and scalability.