HPPRM: Hybrid Potential Based Probabilistic Roadmap Algorithm for Improved Dynamic Path Planning of Mobile Robots

Path planning and navigation is a very important problem in robotics, especially for mobile robots operating in complex environments. Sampling based planners such as the probabilistic roadmaps (PRM) have been widely used for different robot applications. However, due to the random sampling of nodes in PRM, it suffers from narrow passage problem that generates unconnected graph. The problem is addressed by increasing the number of nodes but at higher computation cost affecting real-time performance. To address this issue, in this paper, we propose an improved sampling-based path planning method for mobile robot navigation. The proposed method uses a layered hybrid Probabilistic Roadmap (PRM) and the Artificial Potential Field (APF) method for global planning. We used a decomposition method for node distribution that uses map segmentation to produce regions of high and low potential, and propose a method of reducing the dispersion of sample set during the roadmap construction. Our method produces better goal planning queries with a smaller graph and is computationally efficient than the traditional PRM. The proposed planner called the Hybrid Potential based Probabilistic Roadmap (HPPRM) is an improved sampling method with respect to success rate and calculation cost. Furthermore, we present a method for reactive local motion planning in the presence of static and dynamic obstacles in the environment. The advantage of the proposed method is that it can avoid local minima and successfully generate plans in complex maps such as narrow passages and bug trap scenarios that are otherwise difficult for the traditional sample-based methods. We show the validity of our method with experiments in simulation and real environments for both local and global planning. The results indicate that the proposed HPPRM is effective for autonomous mobile robot navigation in complex environments. The success rate of the proposed method is higher than 95% both for local and global planning.