Incremental hierarchical roadmap construction for efficient path planning

Abstract

This paper proposes a hierarchical roadmap (HRM) and its construction process to efficiently represent navigable areas in an indoor environment. HRM is adopted to solve the path‐planning problems of mobile robots in indoor environments. HRM has a multi‐layered graphical structure that enables it to abstract and cover navigable areas using a smaller number of nodes and edges than a probabilistic roadmap. During the incremental process of constructing HRM, information on navigable areas is abstracted using a sonar gridmap when the mobile robot navigates an unexplored area. The HRM‐based planner efficiently searches for paths to answer queries by reducing the search space size using the multi‐layered graphical structure. The benefits of the proposed HRM are experimentally verified in real indoor environments.

Keywords

• environment representation
• gridmap
• mobile robot
• path planning
• probabilistic roadmap