Fast Path Planning with Hierarchical Approach Based on 3D Scene Graphs

Abstract

In the literature on autonomous systems in general, and mobile robots in particular, the primary goal of path planning methods is to meet both com pleteness and real-time criteria, ensuring they can be effectively deployed in real-world systems. For Unmanned Aerial Vehicles (UAVs), the requirement for real-time performance becomes even more critical due to constraints of resources.
The most of existed methods use the volumetric map combined with a single-level planning approach. This is computationally expensive even in small scenes. There were many efforts in reducing this burden of computing. The ESDF map encodes the shortest distance from every point in the environment to the nearest obstacle enabling collision-checking faster. Oleynikova et al. has tried to skeletonizing the environment and then creating sparse graph. This work suggests the use of hierarchical planning based on the novel presentation of environment, namely 3D Scene Graph (3DSG), to save computational resources more. Hierarchical path planning is an approach that divides the path finding process into different levels of abstraction, allowing for more efficient and scalable solutions. The 3DSG is inherently suitable to hierarchical planning because it is organized as multi-layers at different levels of abstraction and includes the relationship between nodes at the same layer as well as across different layers.
Moreover, we also did the experiments for illustrating the performance of planning on 3DSG versus sparse graph. We do A-star and D* Lite with the same configuration on 3DSG and sparse graph on some kind of environment. From the result, we figured out that the efficiency of hierarchical planning on 3DSG is superior compared to sparse graph. A summary video of the proposed system is available at https://youtu.be/6leSRoO16KQ.