Hierarchical graph search for mobile robot path planning

Abstract

This paper focuses on the utilization of a highly structured model of the environment for mobile robot path planning, called hierarchical graph (or H-Graph). It can be seen as a set of different views of the same environment (hierarchical levels), each of them capturing different amounts of detail. We present a hierarchical graph search algorithm computationally less expensive than a conventional plain graph search algorithm that uses only the most detailed hierarchical level of the H-Graph. We also define the weights assigned to each arc of the H-Graph in such a way that they can represent the typical costs that a mobile robot has to assume when it navigates: energy consumption, time elapsed, etc. An example of the application of the hierarchical graph search algorithm to a portion of our research centre serves for demonstrating how the algorithm can guarantee the optimality of the paths found, and the important reduction in computational cost that it achieves with respect to a classical plain graph search.