PRM-D* Method for Mobile Robot Path Planning

Chunyang Liu, Saibao Xie, Xin Sui, Yan Huang, Xiqiang Ma, Nan Guo, Fang YangSensors 2023 · DOI

TL;DR

This paper introduces PRM-D, a novel hierarchical path planning method that combines the strengths of Probabilistic Roadmaps (PRM) for global planning and the D algorithm for dynamic obstacle avoidance. By integrating D into PRM's network construction and local planning, PRM-D significantly enhances a robot's ability to navigate complex and dynamic environments with improved speed and success rates.

What Problem Does This Paper Address?

Mobile robots are increasingly deployed in diverse and dynamic environments, from disaster relief to industrial automation. These applications demand robust path planning capabilities, including high success rates, fast planning speeds, effective dynamic obstacle avoidance, and reasonably short paths. While classical methods like Probabilistic Roadmaps (PRM) offer good global planning and probabilistic completeness, they struggle with dynamic obstacles. Conversely, algorithms like D excel at dynamic replanning but can be computationally expensive for large-scale static planning. This paper addresses the challenge of creating a unified path planning system that combines the efficiency of PRM for initial path generation with the responsiveness of D for real-time adjustments in dynamic scenarios, particularly in large-scale environments.

Methods

The core innovation is the PRM-D* method, a hierarchical approach that integrates D* into the PRM framework. This integration occurs in two key areas:

  • Network Construction: Instead of relying solely on straight-line connections between PRM nodes, PRM-D uses the D algorithm to find more robust and efficient paths between nodes, especially in complex or narrow passages. This "secondary retrieval" helps bypass simple occlusions and reduces the need for an excessive number of sampling points, thereby speeding up the initial graph construction.
  • Dynamic Planning: D is employed as a local planner. When the robot navigates, it constructs a local map around its current position. If dynamic obstacles are detected or the environment changes, D is used to quickly replan the path within this local context, ensuring agile obstacle avoidance. This hierarchical structure allows for fast global planning with PRM and rapid local adjustments with D*.

The paper also details improvements in local map construction, focusing on efficiently defining the relevant area for D* replanning to balance responsiveness and computational cost.

Datasets

The paper primarily uses simulated grid maps of varying complexity for evaluation. These maps are generated with different configurations, including those with narrow passages ("slits") and varying obstacle densities, to test the robustness of the proposed method. A real-world experiment was also conducted on a campus street section to validate the algorithm's applicability in a practical scenario.

Key Insights and Ideas

  • Synergistic Combination: The paper demonstrates that combining PRM and D is more effective than using either algorithm in isolation for dynamic, large-scale navigation. PRM provides a solid global foundation, while D injects crucial dynamic responsiveness.
  • Efficient Network Building: Using D* for inter-node pathfinding within PRM's graph construction significantly reduces the number of sampling points needed to achieve a high success rate, especially in complex environments. This directly translates to faster initial planning.
  • Order-of-Magnitude Speedup in Dynamic Scenarios: The integration of D* as a local planner leads to a dramatic improvement in dynamic obstacle avoidance speed, achieving performance two orders of magnitude faster than methods like SPARS2.
  • Trade-off Management: The research highlights the importance of balancing sampling density with map complexity. While more sampling points generally improve success rates, they can also lead to redundancy. PRM-D* appears to mitigate this by being more efficient with fewer points.

Key Results

  • Static Planning: PRM-D* achieves an average planning time of less than 1 second for static maps.
  • Dynamic Planning: The method is two orders of magnitude faster than SPARS2 for dynamic obstacle avoidance, with a single dynamic planning time of less than 0.02 seconds.
  • Path Length: While not strictly optimal, PRM-D*'s global path length is comparable to SPARS2 and shorter than the original PRM, indicating effective optimization.
  • Success Rate: PRM-D* achieves a high success rate, even with fewer sampling points compared to traditional PRM, particularly in challenging "slit" maps. For instance, a 95% success rate was achieved with 300 sampling points, and 100% with 500.
  • Real-World Validation: The algorithm was successfully deployed on a real vehicle, demonstrating its practical utility in navigating a real-world environment with dynamic obstacles.

Limitations and Future Work

  • Optimality of Static Paths: The authors acknowledge that PRM-D* is not strictly optimal in terms of static path length. They suggest that future work could explore methods like SPARS2's iterative node addition near existing paths to achieve better asymptotic optimality.
  • Energy Efficiency: The current method does not explicitly consider energy consumption related to different motion types (straight, turning, in-situ steering). Future research will focus on incorporating kinematic principles to generate paths that are more energy-efficient and aligned with the robot's motion capabilities.

Summary updated

Abstract

Various navigation tasks involving dynamic scenarios require mobile robots to meet the requirements of a high planning success rate, fast planning, dynamic obstacle avoidance, and shortest path. PRM (probabilistic roadmap method), as one of the classical path planning methods, is characterized by simple principles, probabilistic completeness, fast planning speed, and the formation of asymptotically optimal paths, but has poor performance in dynamic obstacle avoidance. In this study, we use the idea of hierarchical planning to improve the dynamic obstacle avoidance performance of PRM by introducing D* into the network construction and planning process of PRM. To demonstrate the feasibility of the proposed method, we conducted simulation experiments using the proposed PRM-D* (probabilistic roadmap method and D*) method for maps of different complexity and compared the results with those obtained by classical methods such as SPARS2 (improving sparse roadmap spanners). The experiments demonstrate that our method is non-optimal in terms of path length but second only to graph search methods; it outperforms other methods in static planning, with an average planning time of less than 1 s, and in terms of the dynamic planning speed, our method is two orders of magnitude faster than the SPARS2 method, with a single dynamic planning time of less than 0.02 s. Finally, we deployed the proposed PRM-D* algorithm on a real vehicle for experimental validation. The experimental results show that the proposed method was able to perform the navigation task in a real-world scenario.
BibTeX
@inproceedings{liu2023prm,
  author = {Chunyang Liu and Saibao Xie and Xin Sui and Yan Huang and Xiqiang Ma and Nan Guo and Fang Yang},
  title = {{PRM-D* Method for Mobile Robot Path Planning}},
  booktitle = {Sensors},
  year = {2023},
  doi = {10.3390/s23073512},
}
Figure