An Efficient Fine-to-Coarse Wayfinding Strategy for Robot Navigation in Regionalized Environments

This paper proposes an efficient wayfinding strategy for robot navigation in regionalized environments by designing a regionalized spatial knowledge model (RSK model) and a region-based wayfinding algorithm, i.e., a fine-to-coarse A* (FTC-A*) search algorithm. First, the RSK model, which imitates the representation of environments in the human brain, is presented to describe the search environments. The environments that are divided into regions are represented by a hierarchical nested structure where small regions are grouped together to form superordinate regions. Second, on the basis of the RSK model, an FTC-A* search algorithm is developed to plan the fine-to-coarse route. By making a fine planning to robot surroundings in vicinity, but a coarse planning to that at the distance, the FTC-A* algorithm can effectively reduce computational complexity, so as to enhance the efficiency of route search, and meanwhile makes robots to react quickly to user's commands, especially in large-scale environments. Finally, four exhaustive simulations and a physical experiment have been carried out to illustrate the feasibility and effectiveness of the proposed wayfinding strategy.