Time-Aware Probabilistic Roadmaps for Multi-Query Path Planning in Dynamic Environments

Abstract

In the evolving landscape of robotic applications, there is an increasing demand for advanced path planning algorithms capable of navigating dynamic environments. Estab-lished sampling-based algorithms like Probabilistic Roadmaps (PRM/PRM*) or Rapidly-exploring Random Trees (RRT/RRT*) and their derivatives have marked significant progress in this domain. However, there remains room for improvements when it comes to effectively planning cost-optimal paths through a priori known time-varying environments without resorting to online replanning. Addressing limitations of related algorithms and extending the range of considered dynamic factors, we propose Time-Aware Probabilistic Roadmaps (TA-PRM*), combining PRM with the concept of time-dependent graphs. Our approach distinctively incorporates dynamic weighting into PRM and introduces a temporal dimension to the A* algorithm, while preserving both asymptotic optimality and probabilistic completeness properties. We also propose techniques for pruning in the temporal dimension and heuristic tuning to improve runtime efficiency, while slightly compromising optimality. Through comprehensive evaluations, we benchmark TA-PRM*'s efficacy against that of its best-known contemporaries and demonstrate its applicability in a real-world scenario for unmanned aerial vehicle trajectory planning.