In unknown environments, UAV autonomous exploration often faces efficiency bottlenecks such as path redundancy and repeated entries. Zheng Tianchao and others from the School of Mechanical and Electrical Engineering of Suzhou University proposed a hierarchical path planning method based on multi-subgraph exploration strategy and Octree-topology hybrid map. It combines local-global collaboration and trajectory optimization to effectively reduce path inflection points and flight distances.Prometheus simulation platform and verified in real machine experiments. This paper has been officially included in IEEE ROBIO 2024, an international conference in the field of robotics and bionics, and has received AMOVLABCampus Scholarship Activities The third prize is 2,000 yuan.

01 Research background

In non-prior environments such as underground garages and post-disaster buildings, rotor UAVs need to rely on perception sensors and onboard computers for real-time mapping and decision-making. Traditional global search based on a single grid map is prone to repeated round trips as the map expands, the search space expands exponentially, and turning nodes proliferate. Under conditions of limited computing resources,How to shorten exploration time and trajectory length, becoming an important challenge facing the field of independent exploration.

02 Method overview

In order to solve the problems of path duplication and reduced efficiency in traditional exploration algorithms, this paper proposes a hierarchical path planning method based on multi-map collaboration for rotor UAVs equipped with depth cameras. The algorithm combines local grids and topological hybrid maps, which are used for local backtracking path generation and global topology path planning respectively. Through the "point-to-line" optimization strategy, the turning points and length of the path are effectively reduced.

Multi-submap collaborative exploration strategy

• Use a multi-resolution multi-map structure: the local map (high resolution) is used for fine planning, and the global map (low resolution) guides the sub-map direction;

• The subgraph construction status is used as the basis for task progress to avoid repeated exploration.

• The subgraph area is used as an exploration completion indicator to prevent invalid revisits;

• Optimize the boundary search strategy: perform wavefront boundary detection within the subgraph to reduce the boundary point search range and frequency;

• Information gain evaluation optimization: not only considers the amount of information at a single point, but also determines the exploration priority based on its spatial distribution.

local path planning

• Construct an octree subgraph, initialize the idle grid value and perform wavefront diffusion to form a wave array diagram;

• Perform backtracking path planning based on the wave array value, and select the adjacent node with the smallest wave array value;

• The cost evaluation function (distance from starting point to node + distance from node to target) is introduced to solve the path randomness when the wave array values ​​are equal;

• Finally, the shortest feasible path from the current point to the target boundary is obtained.

Global path planning

• Dynamically extract key nodes in the exploration process (such as subgraph centers, turning points of historical paths) as topological graph nodes;

• Use Delaunay triangulation + collision detection to construct barrier-free connected edges and generate sparse topological graphs;

• Construct a feature matrix to store the Euclidean distance between nodes (non-neighbor points are set to ∞);

• Use Dijkstra's algorithm to search the path from the UAV's current position to the global optimal boundary point on the topology map.

The left picture shows the local planning results, and the right picture shows the global planning results.

Path trajectory optimization: turning points into line segments

• Detect whether there is a visible space between any two points in the path;

• If there are no obstacles, delete all inflection points in the middle and keep the first and last two points as a straight path;

• Iteratively process multiple segments of the entire path to simplify the polygonal path into a smoother sequence of straight line segments.

Technical Highlights

• Integrated path planning framework: adopts a hierarchical structure of "local fine planning + global guidance" to achieve a dynamic balance between accuracy and efficiency;

• Multi-submap collaborative exploration mechanism: improve the resolution of the target area, reduce the overall map maintenance cost, and prevent repeated exploration;

• The trajectory optimization strategy is efficient and reliable: "turning points into straight lines" significantly reduce the number of turning points and the total length of the path, improving flight safety and stability;

• Sparse topology map + feature matrix modeling: Compared with the traditional full-graph path planning method, the storage and retrieval efficiency is higher, and it supports fast path generation in large-scale environments;

• Target boundary point selection is more intelligent: the information gain evaluation strategy incorporates spatial distribution considerations and arranges the exploration sequence more reasonably.

03 Simulation/real machine experiment

Experimental platform

hardware:
AMOVLABP230 quadcopter UAV, equipped with Intel Realsense D435i depth camera, Jetson Xavier NX processor, etc.

software: Prometheus open-source platform

Laboratory scene

In a small laboratory scene with dense obstacles (6mx7.8m), the test found that after trajectory optimization:

• Local path turn points reduced from 4 to 2;

• Path length reduced from 5.24m to 5.01m.

  
  
  

Underground garage scene

Testing in a weak texture environment (42mx15m) with uneven lighting and no GNSS found:

• After global path optimization, the number of turning points is reduced from 7 to 2;

• Path length shortened from 16.79m to 14.36m;

• The path planning node of the topology map is only 0.7% of the grid map, and the planning time is reduced by 34%.

Resource Express
Paper link: https://ieeexplore.ieee.org/abstract/document/10907525