CN-122015855-A - Hierarchical search three-dimensional airspace path planning method and system based on self-adaptive resolution grids

CN122015855ACN 122015855 ACN122015855 ACN 122015855ACN-122015855-A

Abstract

The invention particularly relates to a hierarchical search three-dimensional airspace path planning method and system based on a self-adaptive resolution grid, wherein the method comprises the steps of constructing a corresponding multi-resolution grid model based on a three-dimensional grid map; the method comprises the steps of carrying out global path planning on coarse resolution grids, determining coarse paths of nodes of the coarse resolution grids, constructing a coarse path sequence, carrying out non-overlapping segmentation on the coarse path sequence, planning local windows adapting to fine resolution grids, determining window entrance points corresponding to the local windows, carrying out obstacle recognition on the local windows based on the fine resolution grids, calling a corresponding path generation strategy according to obstacle recognition results of the local windows, determining local refined sub-paths corresponding to the local windows, and carrying out splicing processing on path information of the local windows in sequence to obtain path planning results. The invention can realize the efficient and reliable path planning of a large-scale and complex three-dimensional airspace environment.

Inventors

JIANG SHUYUAN
Wei Shouyue
SHI YIYU

Assignees

浙江省交通运输科学研究院
中国移动通信集团浙江有限公司

Dates

Publication Date: 20260512
Application Date: 20260206

Claims (10)

1. A hierarchical search three-dimensional airspace path planning method based on an adaptive resolution grid, the method comprising: constructing a corresponding multi-resolution grid model based on the three-dimensional grid map, wherein the multi-resolution grid model comprises a coarse resolution grid and a fine resolution grid; performing global path planning on the coarse-resolution grids according to start-stop point information corresponding to the current path planning task, determining coarse paths of all coarse grid nodes, and constructing a coarse path sequence; Planning and adapting local windows of the fine resolution grids, and determining window entrance points corresponding to the local windows; performing obstacle recognition on each local window based on the fine resolution grids, calling a corresponding path generation strategy according to the obstacle recognition result of the local window, and determining a local fine sub-path corresponding to each local window; and sequentially splicing the path information of each local window to obtain a path planning result, wherein the path information of the local window comprises a local fine sub-path or a coarse resolution path.
2. The method of claim 1, wherein constructing a corresponding multi-resolution grid model based on a three-dimensional grid map comprises: performing downsampling processing on the three-dimensional grid map in the horizontal direction based on a preset downsampling factor, and constructing a coarse resolution grid according to a sampling result; performing downsampling processing on the coarse resolution grid in the horizontal direction based on a preset downsampling factor, constructing a fine resolution grid according to the sampling result, and Performing expansion processing based on a preset size on projection of the obstacle on a horizontal plane to obtain an obstacle mask of the obstacle under a coarse resolution grid and a fine resolution grid; the downsampling factor is configured based on the current topographic features corresponding to the three-dimensional grid map.
3. The method of claim 1, wherein performing global path planning on the coarse resolution grid according to start and stop point information corresponding to a current path planning task, and determining a coarse path sequence comprises: Invoking improved A based on coarse resolution grid occupancy mask The method solves the global communication path of the starting point and the ending point and outputs a coarse path sequence, wherein, the improvement A The method comprises the following steps: f(g m )=g (g m )+α・h (g m ) where g (gm) is the actual cost of the accumulated euclidean distance from the starting point to the current coarse grid gm, h (gm) is the heuristic cost of the euclidean distance from the current coarse grid gm to the end point, and α is the heuristic weight.
4. The method of claim 1, wherein non-overlapping segmentation is performed on the coarse path sequence, and planning local windows of the adaptive fine resolution grid, and determining window entry and exit points corresponding to each local window, comprises: configuring the size of a local window according to coarse grid node data in the coarse path sequence; Non-overlapping segmentation processing is carried out on the rough path sequence based on the size of the local window, and a plurality of non-overlapping rough path node groups are obtained; The first minimum outsourcing rectangle is mapped to the fine resolution grid, and the second minimum outsourcing rectangle on the fine resolution grid is determined so as to acquire the pixel index range of the local window based on the fine resolution grid; And calling a preset priority rule to configure an entry point and an exit point of each local window according to the pixel index range of the local window based on the fine resolution grid.
5. The method of claim 4, wherein invoking the preset priority rule to configure the entry point and the exit point of each local window comprises: The priority rule selected by the entry point comprises a starting point corresponding to the current path planning task, an exit point of a previous local window, an intersection point of a skeleton path edge and a local window boundary and a coarse resolution grid node, wherein the priority is from high to low; The priority rule for selecting the exit point comprises an end point corresponding to the current path planning task, an entry point of a next partial window, an intersection point of a skeleton path edge and a partial window boundary and a coarse resolution grid node from high to low in priority.
6. The method of claim 1, wherein performing obstacle recognition on each local window based on the fine resolution grid, and invoking a corresponding path generation policy according to the obstacle recognition result of the local window, and determining a local refined sub-path corresponding to each local window, comprises: identifying whether an occupied grid exists in the current local window, and configuring the current local window as a window containing barriers when the occupied grid is determined to exist; for the window with obstacle, the entry point and the exit point are used as the start and stop points to configure a fine grid search domain, and an improved A is called for the fine grid search domain The method carries out global communication path search on start and stop points, generates continuous path segments based on a fine resolution grid, and configures the continuous path segments into local fine sub-paths; or for the unobstructed window, configuring the rough path node corresponding to the local window as a continuous path section corresponding to the unobstructed window, and configuring the rough path node as a local refined sub-path.
7. The method of claim 6, wherein configuring the fine-grid search field with the entry point and the exit point as start and stop points for the obstacle-containing window comprises: Generating a minimum horizontal plane outsourcing rectangle based on the coordinate information of the inlet point and the outlet point under the fine resolution grid, wherein the minimum outsourcing rectangle is determined based on the coordinate extremum of the inlet point and the outlet point; The height range is superimposed on the horizontal plane minimum bounding rectangle, forms an axis alignment bounding box, and is configured as a base search area based on a fine resolution grid.
8. The method of claim 7, wherein the method further comprises: And uniformly expanding the basic search area to the outside in the horizontal direction based on the expansion parameter S, and configuring the expanded area as the fine grid search area.
9. The method according to claim 1, wherein the method further comprises: Identifying each axial grid of the diagonal grid or the space diagonal of the current grid when the aircraft moves based on the path planning result; If any one of the axial grids has an obstacle, the diagonal grid or space is prohibited from moving diagonally.
10. A hierarchical search three-dimensional airspace path planning system based on an adaptive resolution grid, the system comprising: the multi-resolution grid model creation module is used for building a corresponding multi-resolution grid model based on a three-dimensional grid map, wherein the multi-resolution grid model comprises a coarse resolution grid and a fine resolution grid; the coarse path sequence calculation module is used for carrying out global path planning on the coarse resolution grids according to the start and stop point information corresponding to the current path planning task, determining the coarse paths of the coarse grid nodes and constructing a coarse path sequence; the local window calculation module is used for carrying out non-overlapping segmentation on the coarse path sequence, planning and adapting to local windows of the fine resolution grid, and determining window entrance points corresponding to each local window; The local refined sub-path calculation module is used for identifying obstacles of each local window based on the fine resolution grids, calling a corresponding path generation strategy according to the obstacle identification result of the local window and determining a local refined sub-path corresponding to each local window; And the planning path generation module is used for sequentially splicing the path information of each local window to obtain a path planning result, wherein the path information of the local window comprises a local fine sub-path or a coarse resolution path.

Description

Hierarchical search three-dimensional airspace path planning method and system based on self-adaptive resolution grids Technical Field The invention relates to the technical field of unmanned aerial vehicle path planning, in particular to a hierarchical search three-dimensional airspace path planning method and system based on a self-adaptive resolution grid. Background In the related art, an unmanned aerial vehicle is required to complete an autonomous path planning task in a complex three-dimensional environment in low-altitude logistics, urban inspection, emergency rescue, military reconnaissance and other applications. The environment is characterized by large airspace range, huge three-dimensional space state quantity, complex obstacle types including terrains, buildings, no-fly zones, temporary restricted zones and the like, high irregularity of obstacle distribution, and simultaneous existence of requirements on path safety, smoothness and instantaneity. Traditional AAlgorithms typically perform path searches based on a uniform resolution grid. When the resolution of the grid is high, the number of the search nodes is increased sharply, so that the calculation complexity is too high, and when the resolution of the grid is low, the path precision is insufficient, and potential safety hazards such as path crossing barriers, too close obstacle sticking and the like are easy to occur. In addition, the uniform grid search is directly performed in a three-dimensional environment, and the problems that the state space grows exponentially due to uniform grid discretization, a 'dimension disaster' is caused, the calculation complexity rises sharply, the real-time planning requirement is difficult to meet, in a complex limited environment, high-density obstacles and irregular 'dead zones' are easy to cause the algorithm to be sunk into local optimum or path deadlock, the generated paths contain a large number of broken line inflection points, the flight adaptability is poor, the planning precision and the calculation efficiency cannot be balanced in fixed resolution grid modeling, the coarse resolution grid can accelerate the searching speed but cannot guarantee the path safety, and the fine resolution grid can improve the planning precision but obviously increase the calculation cost. Although the existing multi-resolution path planning method relieves the calculation pressure of the unified resolution grid in a large-scale space to a certain extent, a plurality of key defects still commonly exist in engineering application. Firstly, path connection mechanisms among different resolution levels are imperfect, and a multi-resolution switching process lacks a stable and uniform transition strategy, so that discontinuous or offset phenomena among thick and thin paths are easily caused, and the feasibility and consistency of the whole path are affected. Secondly, the local refinement process is often performed independent of the global path structure, and effective guidance of the global skeleton path is lacking, so that local search is easy to deviate from the global optimal direction, and even falls into local optimization or search failure. And in a region with dense complex barriers or limited space, the existing method is easy to have the problems of path fracture, partial no solution or frequent backtracking, and the overall planning stability and the robustness are insufficient. In addition, the existing multi-resolution method lacks unified and standard rules in construction and selection of local planning windows, window dimensions and positions often depend on experience setting, searching efficiency and path accuracy are difficult to be considered, and adaptability and consistency of algorithms in different scenes are affected. It should be noted that the information disclosed in the above background section is only for enhancing understanding of the background of the invention and thus may include information that does not form the prior art that is already known to those of ordinary skill in the art. Disclosure of Invention The invention provides a hierarchical search three-dimensional airspace path planning method based on a self-adaptive resolution grid, which is a hierarchical search three-dimensional airspace path planning system based on the self-adaptive resolution grid, and can realize efficient and reliable path planning of a large-scale and complex three-dimensional airspace environment, thereby overcoming the defects in the prior art to a certain extent. Other features and advantages of the invention will be apparent from the following detailed description, or may be learned by the practice of the invention. According to a first aspect of the present invention, there is provided a hierarchical search three-dimensional airspace path planning method based on an adaptive resolution grid, the method comprising: constructing a corresponding multi-resolution grid model based on the three-dimension