A Fast On-line Global Path Planning Algorithm Based on Regionalized Roadmap for Robot Navigation *

Inspired by the 'fine-to-coarse' way-finding strategy that human utilized in the process of navigation, the paper proposed a fast on-line global path planning algorithm based on regionalized roadmap. First, a regionalized roadmap(RRM) that has a multi-layered structure is proposed for representing environments. Then, the RRM based FTC-A* algorithm is designed to plan an FTC-route('fine-to-coarse' route) with being fine in vicinity yet coarse at a distance. This algorithm can be applied to on-line global path planning in navigation system of mobile robots or vehicles. Finally, the simulation and physical experiments have been carried out to show the efficacy of the proposed path planning algorithm which can be applied to such occasions as large-scale environment and dynamic changes of the destination.