PRM-D* Method for Mobile Robot Path Planning

Area of Science:

• Robotics
• Artificial Intelligence
• Path Planning Algorithms

Background:

• Dynamic navigation scenarios necessitate high success rates, rapid planning, and effective obstacle avoidance for mobile robots.
• The Probabilistic Roadmap Method (PRM) offers fast planning and asymptotically optimal paths but struggles with dynamic obstacle avoidance.
• Existing methods often present trade-offs between planning speed, path optimality, and dynamic obstacle handling.

Purpose of the Study:

• To enhance the dynamic obstacle avoidance capabilities of the Probabilistic Roadmap Method (PRM).
• To develop a hybrid path planning approach integrating PRM with D* algorithm principles.
• To validate the performance of the proposed PRM-D* method in complex and dynamic environments.

Main Methods:

• A hierarchical planning approach was employed, integrating the D* algorithm into the network construction and planning phases of PRM.
• The proposed PRM-D* method was simulated and compared against classical methods like SPARS2 across various map complexities.
• Real-world validation was conducted by deploying the PRM-D* algorithm on a physical mobile robot.

Main Results:

• The PRM-D* method demonstrated superior performance in dynamic obstacle avoidance compared to traditional methods.
• Static planning times averaged under 1 second, outperforming other methods.
• Dynamic planning speed was significantly enhanced, achieving speeds two orders of magnitude faster than SPARS2 (under 0.02s per dynamic planning instance).
• While not strictly optimal in path length, PRM-D* achieved near-optimal path lengths, second only to graph search methods.

Conclusions:

• The PRM-D* method effectively addresses the limitations of classical PRM in dynamic environments.
• The algorithm provides a robust and efficient solution for mobile robot navigation in complex, changing scenarios.
• Experimental validation confirmed the practical applicability and effectiveness of PRM-D* in real-world navigation tasks.