An Efficient Fine-to-Coarse Wayfinding Strategy for Robot Navigation in Regionalized Environments
提出一种模仿人脑环境表征的区域化空间知识模型和由细到粗的A*搜索算法，在大型环境中降低计算复杂度，提升机器人寻路效率和对用户指令的响应速度。
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.