RADES: Rank‐Based Differential Evolution With Successful Archive for Multi‐Robot Coordinated Planning at Intersections

Abstract

ABSTRACT Motion planning for multiple robots operating in constrained environments is a fundamental challenge in robotics. Overcoming limitations in scalability and solution quality in existing multi‐robot planners is essential for safe, efficient, and collision‐free navigation. Contemporary multi‐robot coordinated planning is constrained by the granularity of probabilistic roadmap configurations: Rendering feasible probabilistic roadmaps that can be used effectively and efficiently by sample‐based path‐planning schemes, such as dRRT*, is often time‐consuming. To address roadmap generation and effective sampling in coordinated motion planning for mobile robots, we introduce RADES (Rank‐based Differential Evolution with a Successful Archive), a novel gradient‐free optimization algorithm for multi‐robot coordinated planning. RADES enhances sampling in lattice‐based roadmap configurations by integrating rank‐based selection, successful‐mutation archiving, and stagnation‐control mechanisms. Comprehensive computational experiments across intersection scenarios involving up to 12 robots demonstrate that RADES outperforms seven established gradient‐free optimization techniques and two state‐of‐the‐art winners from CEC 2024 in terms of solution cost and convergence performance. Our approach facilitates the use of gradient‐free optimization algorithms to sample the search space of feasible and safe multi‐robot roadmaps.