Avoiding Dense Pedestrian Regions: A New Rapidly-Exploring Random Tree (RRT ∗) Algorithm for Shortest Travel Time

Abstract

Currently, regardless of the algorithm used, motion planners for dealing with dynamic obstructions need to rely on high-precision sensors and high performance processors. The requirements for hardware increase as the density of dynamic obstructions in an area becomes higher. Additionally, motion planners are more prone to errors in complex environments. The Rapidly-exploring Random Tree (RRT ∗) algorithm only considers static obstructions and cannot effectively avoid densely populated regions of dynamic obstructions. This paper develops an improved RRT ∗ algorithm that is capable of avoiding densely populated regions of dynamic obstructions. In this algorithm, the cost function of the traditional RRT ∗ algorithm is modified based on the density of dynamic obstructions, allowing the planned path to bypass densely populated regions. The algorithm also introduces reasonable penalty terms to penalize segments that pass through densely populated regions, while maintaining asymptotic optimality of the traditional RRT ∗ algorithm. Numerical experiments reveal that the improved RRT ∗ algorithm is able to successfully avoid densely populated regions of dynamic obstructions with minimal time cost and exhibits better robustness during the path search process in comparison to the traditional RRT ∗ algorithm. Thus, the improved RRT ∗ algorithm possesses the ability to adapt to more complex areas for path planning.