CN-121677746-B - Unmanned aerial vehicle route planning method

CN121677746BCN 121677746 BCN121677746 BCN 121677746BCN-121677746-B

Abstract

The invention relates to an unmanned aerial vehicle route planning method which comprises the steps of conducting grid division on an area formed by encircling a route longitude range and a latitude range, generating safe flying heights of each grid unit, conducting route searching through a route searching algorithm to obtain discrete grid routes, introducing route length, a height climbing angle and a deviation distance from a starting point straight line into a cost function of the route searching algorithm, conducting route smoothing on the discrete grid routes, conducting encryption interpolation on the smooth route to obtain encrypted central line points, generating a plurality of offset points in a normal direction at each central line point, obtaining the elevation of each offset point on a digital elevation model, constructing the most dangerous terrain height on a three-dimensional cross section according to the elevation of the offset point, and calculating final flying heights according to the most dangerous terrain height, so that a final three-dimensional track point sequence is obtained. The route obtained by the method is safe, and the route is as short and straight as possible.

Inventors

BAI HAIWEI
WANG JIANGSHENG
WEN XUEDONG
NIE QIAN
LIN YUN
CHEN HAIZHEN
Mei Yuanxun
LI JUNFENG
ZHU MENGYUAN
SHU JINFANG

Assignees

宁波市测绘和遥感技术研究院(宁波市自然资源和规划调查监测中心)

Dates

Publication Date: 20260508
Application Date: 20260212

Claims (9)

1. The unmanned aerial vehicle route planning method is characterized by comprising the following steps of: Step 1, determining a minimum boundary according to a route starting point and a route ending point of an unmanned aerial vehicle, acquiring a longitude range and a latitude range according to the minimum boundary, and performing grid division on an area formed by the longitude range and the latitude range in a surrounding manner to obtain a plurality of grid units; Step 2, carrying out multipoint sampling on each grid cell on the digital elevation model, obtaining the maximum elevation value of all sampling points in each grid cell, taking the maximum elevation value corresponding to each grid cell as the representative elevation of the current grid cell, and generating the safe flying height of each grid cell according to the representative elevation of each grid cell; step 3, performing route search by adopting a route search algorithm to obtain a discrete grid route, and introducing a route length, a height climbing angle and a deviation distance from a starting point straight line into a cost function of the route search algorithm, wherein the height climbing angle is calculated according to the route lengths and the safe flying heights of two grid units; the path searching algorithm is based on an A-type searching algorithm, a Theta-type searching algorithm or a D-Lite searching algorithm; step 4, performing route smoothing on the discrete grid paths obtained in the step 3 to obtain smooth route paths; And 5, carrying out encryption interpolation on the smooth route path in the step 4 to obtain encrypted central line points, generating a plurality of offset points at each central line point along the normal direction, acquiring the elevation of each offset point on a digital elevation model, constructing the most dangerous terrain height on the cross section of the three-dimensional flight corridor according to the elevations of all the offset points, and calculating the final flight height of each central line point according to the most dangerous terrain height, thereby acquiring a final three-dimensional track point sequence.
2. The unmanned aerial vehicle route planning method of claim 1, wherein the specific acquisition process of the latitude and longitude ranges in step 1 is: obtaining a minimum rectangle comprising a route start point and a route end point of the unmanned aerial vehicle, wherein the minimum rectangle is a minimum boundary, and expanding the determined minimum boundary to obtain a longitude range and a latitude range.
3. The unmanned aerial vehicle route planning method of claim 1, wherein the step 2 further comprises the steps of: Judging whether the safe flying height of any grid cell is smaller than or equal to the preset maximum flying height, if so, marking the grid cell as a grid cell capable of passing, and if not, marking the grid cell as a grid cell capable of not passing.
4. The unmanned aerial vehicle routing method of claim 3, wherein during the searching using the A-search algorithm, the current grid cell is used to route the unmanned aerial vehicle to the target location Grid cell to its neighbors New accumulated cost of (a) The calculation formula is as follows: Wherein, the To start from the grid cell where the route starting point is located to the grid cell Is used to determine the cumulative cost of (1), Is a grid cell Grid cell to its neighbors Cost increment of (a); If it is , To start from the grid cell where the route starting point is located to the grid cell To the accumulated cost of (1) Grid cell Cost function of (2) The calculation formula of (2) is as follows: , As a function of the heuristic properties, To calculate grid cells Euclidean distance to grid cell where route end point is located; If it is Then 。
5. The method of unmanned aerial vehicle route planning of claim 4, wherein the following steps The calculation formula of (2) is as follows: Wherein, the Is a grid cell Grid cells adjacent thereto I.e. grid cells Grid cells adjacent thereto Distance in planar coordinates; For the gradient weight of the road, the road is provided with a slope, For a high degree of ascent, , , Is a grid cell Is used for the safety flying height of the vehicle, Is a grid cell Is a safe flying height of (2); for the maximum height of the climbing angle, For the straight-line deviation weight, Is a grid node Straight line relative to start and end point Is a vertical offset distance of (2); The calculation formula of (2) is as follows: Wherein, the Is a grid cell Is defined by the plane coordinates of (a), Is the plane coordinates of the grid cell where the route start point is located, Is the plane coordinates of the grid cell where the route end point is located, Scalar results that are two-dimensional vector cross products; taking an absolute value; to calculate the two norms.
6. The unmanned aerial vehicle routing method of claim 5, wherein if the grid cells No data is provided for the elevation values of all sampling points in the grid cell No data or grid cell is used for the elevation value of all sampling points in the system To disable passing grid cells, then grid cells Invalidating, meshing cells Discarding; If it is A climbing angle greater than the maximum height Then grid cell Discarding.
7. The unmanned aerial vehicle route planning method of claim 6, wherein the specific course of route smoothing in step 4 is: Step 4-1, the discrete grid paths are sequentially in sequence 、、.... , Is the grid cell where the route start point is located, The grid unit is where the route end point is located; The total number of grid cells in the discrete grid path; Step 4-2, setting an index Is 0; step 4-3, in the discrete grid path, grid cells Setting candidate indexes for the current grid cell = ; Step 4-4, respectively mesh cells And grid cell As a point, will be defined by the grid cell And grid cell Performing discrete sampling on the composed line segments to obtain a plurality of intermediate sampling points, wherein each intermediate sampling point corresponds to one grid unit; step 4-5, judging whether all the intermediate sampling points meet the following conditions, if yes, using grid cells And grid cell Component line segments replace discrete grid paths ~ With grid cells in between, only remaining And grid cell And order If not, the step 4-6 is carried out; each middle sampling point is a passable grid unit; second, the height climbing angle is calculated according to the safe flying height difference and the path length of the two adjacent middle sampling points ; Step 4-6, order If (if) > Then go to step 4-4 if = Then reserve As the next smoothing node, and let Go to step 4-7; step 4-7, judging Whether or not to be equal to If yes, ending, otherwise, turning to step 4-3.
8. The unmanned aerial vehicle route planning method of claim 1, wherein the specific acquisition method of the most dangerous terrain height on the cross section of the three-dimensional flight corridor in the step 5 is as follows: calculating a tangential vector of each midline point, and calculating a normal vector perpendicular to the tangential vector; selecting a group of offset distance sets in the normal direction, and generating offset points according to the following formula; Wherein, the To at the first The first line point is generated along the normal direction The number of bias points is chosen to be the same, Is the first The center line points of the two lines, To offset the first in the distance set The offset distance is a function of the offset distance, Is the first to Normal vectors perpendicular to tangential vectors of the centerline points; converting each generated bias point back to longitude and latitude coordinates, and inquiring the elevation of the longitude and latitude coordinates corresponding to each bias point on the digital elevation model; and obtaining the maximum elevation value of all the offset points in each neutral line point, taking the maximum elevation value as the most dangerous terrain height of the current neutral line point, and obtaining the most dangerous terrain height on the cross section of each three-dimensional flight corridor by correspondingly obtaining the cross section of each three-dimensional flight corridor by each neutral line point.
9. The unmanned aerial vehicle route planning method of any one of claims 1 to 8, wherein after the final three-dimensional track point sequence is obtained in the step 5, the method further comprises the following steps: Calculating a total course according to the three-dimensional track point sequence and acquiring the maximum flight height of the course; The maximum flight altitude of the route is obtained by the following steps: If the final flying height of a certain central line point is larger than the preset maximum flying height, the current final flying height is still used as the flying height of the central line point, the maximum value of the final flying heights of all the central line points is counted, and the maximum value of the final flying heights of all the central line points is used as the actual maximum flying height required by the route planning.

Description

Unmanned aerial vehicle route planning method Technical Field The invention relates to the technical field of path planning, in particular to an unmanned aerial vehicle route planning method. Background With the development of low-altitude economy, the unmanned aerial vehicle is widely applied to the scenes such as power inspection, pipeline inspection, emergency rescue, security patrol, logistics distribution, urban management and the like. Unmanned aerial vehicle mission flight often requires planning of safe and economical three-dimensional airlines in complex terrain and urban obstacle environments, which puts higher demands on airlines planning methods and terrain data. The prior art mainly has the following defects in the aspects of supporting the three-dimensional route planning and the low-altitude flight-adaptive zone planning of the unmanned aerial vehicle: 1. in the existing unmanned aerial vehicle route planning method, only a single point (such as a grid center) is sampled on a Digital Elevation Model (DEM) grid, and the value is regarded as the representative elevation of the whole grid unit; 2. In the prior art, the unmanned aerial vehicle route planning method stays at a two-dimensional or weak three-dimensional level, the common method searches the shortest path on the two-dimensional plane by using an A-star or Dijkstra algorithm, and then the flying height is simply overlapped and fixed or the height correction is carried out once according to the DEM; 3. The objective function of the current path search algorithm only considers path length, obstacle cost or simple height penalty, so that the planning result is too roundabout or has too many folding points or the local gradient is too large, which is not beneficial to the control of the aircraft; 4. The method in the prior art generally only verifies the elevation relation between points on the flight path and the DEM, and is difficult to ensure the whole three-dimensional flight corridor range of 'full line safety'. There is a need for further improvements in the art. Disclosure of Invention Aiming at the prior art, the technical problem to be solved by the invention is to provide the unmanned aerial vehicle route planning method which ensures that the acquired route is safe, the route is as short as possible and as straight as possible. The technical scheme adopted for solving the technical problems is that the unmanned aerial vehicle route planning method is characterized by comprising the following steps: Step 1, determining a minimum boundary according to a route starting point and a route ending point of an unmanned aerial vehicle, acquiring a longitude range and a latitude range according to the minimum boundary, and performing grid division on an area formed by the longitude range and the latitude range in a surrounding manner to obtain a plurality of grid units; Step 2, carrying out multipoint sampling on each grid cell on the digital elevation model, obtaining the maximum elevation value of all sampling points in each grid cell, taking the maximum elevation value corresponding to each grid cell as the representative elevation of the current grid cell, and generating the safe flying height of each grid cell according to the representative elevation of each grid cell; step 3, performing route search by adopting a route search algorithm to obtain a discrete grid route, and introducing a route length, a height climbing angle and a deviation distance from a starting point straight line into a cost function of the route search algorithm, wherein the height climbing angle is calculated according to the route lengths and the safe flying heights of two grid units; the path searching algorithm is based on an A-type searching algorithm, a Theta-type searching algorithm or a D-Lite searching algorithm; step 4, performing route smoothing on the discrete grid paths obtained in the step 3 to obtain smooth route paths; And 5, carrying out encryption interpolation on the smooth route path in the step 4 to obtain encrypted central line points, generating a plurality of offset points at each central line point along the normal direction, acquiring the elevation of each offset point on a digital elevation model, constructing the most dangerous terrain height on the cross section of the three-dimensional flight corridor according to the elevations of all the offset points, and calculating the final flight height of each central line point according to the most dangerous terrain height, thereby acquiring a final three-dimensional track point sequence. Preferably, the specific acquiring process of the longitude range and the latitude range in the step 1 is: obtaining a minimum rectangle comprising a route start point and a route end point of the unmanned aerial vehicle, wherein the minimum rectangle is a minimum boundary, and expanding the determined minimum boundary to obtain a longitude range and a latitude range. Preferably, the step 2 further incl