A Prioritized Time-Aware RRT* Algorithm for Multi-Robot Path Planning in Dynamic Environments

Multi-robot path planning (MRPP) is fundamental to enabling efficient coordination and complex task execution across diverse autonomous systems, from logistics to exploration. Sampling-based algorithms, spearheaded by RRT* (Rapidly-exploring Random Tree star) and its numerous variants, represent a cornerstone of modern path planning due to their effectiveness in exploring high-dimensional spaces and offering desirable properties like probabilistic completeness. While these methods excel in static environments, their direct application to dynamic multi-robot systems often encounters significant challenges. Standard RRT* and many of its existing variants primarily focus on geometric optimization and often lack inherent mechanisms to explicitly manage the crucial temporal dimension. This deficiency hinders their ability to effectively resolve time-dependent inter-robot conflicts or proactively avoid collisions with other dynamic obstacles. To bridge this gap, this paper proposes a Prioritized Time-Aware RRT* (TRRT*) algorithm. Our approach extends the RRT* framework into the time-space domain, enabling explicit reasoning about temporal feasibility by evaluating path segments against dynamic constraints and integrating necessary waiting times into both the planning process and cost evaluation. Planning is coordinated via a predefined priority scheme, where lower-priority robots perceive the planned space-time trajectories of higher-priority agents as dynamic constraints. Comparative simulation experiments validate the proposed method, demonstrating that Prioritized TRRT* achieves significantly higher planning success rates and robustly handles spatio-temporal conflicts in dynamic environments, thereby outperforming a comparable prioritized approach utilizing the standard RRT* algorithm.