A Sampling-Based Algorithm with the Metropolis Acceptance Criterion for Robot Motion Planning

Area of Science:

• Robotics and Artificial Intelligence
• Computational Geometry and Algorithms

Background:

• Rapidly exploring Random Tree* (RRT*) is a key algorithm for motion planning in robotics, valued for its asymptotic optimality.
• However, RRT*'s performance degrades with increasing path complexity due to slow convergence and high computational cost.
• This limits its real-world applicability in complex robotic systems.

Purpose of the Study:

• To address the convergence and performance limitations of the RRT* motion planning algorithm.
• To introduce a novel, efficient motion planning algorithm that maintains asymptotic optimality while improving speed.
• To enhance the practical utility of RRT* in complex robotic applications.

Main Methods:

• Proposes Metropolis RRT* (M-RRT*), a two-phase motion planning algorithm utilizing the Metropolis acceptance criterion.
• Phase 1: Employs an asymptotic vertex acceptance criterion for efficient initial path estimation.
• Phase 2: Implements a nonlinear dynamic vertex acceptance criterion to prioritize path-improving vertices, accelerating convergence.

Main Results:

• M-RRT* demonstrates significantly improved convergence rates compared to existing RRT* variants.
• Simulations in diverse environments confirm the effectiveness of M-RRT* in motion planning tasks.
• The algorithm successfully balances optimality with reduced computation time.

Conclusions:

• M-RRT* offers a substantial improvement over standard RRT* for robotic motion planning.
• The proposed two-phase approach effectively accelerates convergence without sacrificing asymptotic optimality.
• This enhanced algorithm shows great promise for real-time robotic applications requiring efficient pathfinding.