CN-115097870-B - Unmanned aerial vehicle obstacle avoidance flight path planning method based on digital elevation map

CN115097870BCN 115097870 BCN115097870 BCN 115097870BCN-115097870-B

Abstract

The invention provides a digital elevation map-based unmanned aerial vehicle obstacle avoidance track planning method, which comprises digital elevation map conversion, initial track loading, track pre-planning and track re-planning. The method provided by the scheme can fully consider the factors of the fluctuation of the terrain when the low-altitude flight task is executed to realize the ground-attached flight, meanwhile, the scheme performs off-line track pre-planning firstly, and uploads the planned track to the flight control to provide flight guidance for the flight control, so that the problem of low instantaneity is well solved, and when an obstacle or a threat zone appears on the pre-planned track, the method provided by the scheme can find the vertex of the obstacle under the condition that the shape of the obstacle is complex, and the overlapping problem of the obstacle is processed, so that a flight path is rapidly planned.

Inventors

LIAO KAIJUN
QIAN KUN
LIU CONG
ZHU YU
YANG YUCHAO
Xin Gongcai
ZHANG HONGYU

Assignees

中国人民解放军空军工程大学航空机务士官学校

Dates

Publication Date: 20260505
Application Date: 20220629

Claims (6)

1. A unmanned aerial vehicle obstacle avoidance flight path planning method based on a digital elevation map is characterized by comprising the following steps: s1, loading a digital elevation map; s2, converting map data into pictures; s3, loading an initial track point; S4, extracting key nodes and key paths in the skeleton diagram; s5, generating an optimal track by using an A-algorithm; S6, judging whether an obstacle or a threat zone exists on the optimal track generated in the step 5, if so, executing the step S7, otherwise, executing the step S13; s7, connecting all track points, judging a binary image obstacle communication area by utilizing an algorithm based on a union thought, and extracting the boundary of the communication area; s8, judging whether the path intersects with the obstacle, if so, executing a step S9, otherwise, the starting point and the end point are path points, and executing a step S13; S9, recording the intersection sequence and intersection point of the two adjacent obstacles, and adding a reference node between the two adjacent obstacles; S10, calculating a local path; s11, judging whether the two-to-two path point connecting lines intersect with the obstacle, if so, returning to the step S9, otherwise, generating a section of local path; s12, judging whether each local path completes path planning, if all local path calculation is completed, executing a step S13, otherwise, returning to the step S10; S13, deleting redundant track points, and outputting the obtained path points in sequence; S14, outputting an optimal obstacle avoidance track; The obstacle is any three-dimensional object which comprises longitude, latitude, width and height information, and the threat zone is a circular range and comprises threat zone center longitude, threat zone center latitude and threat zone radius information; The digital elevation map is a file stored in an hgt format, wherein one file comprises elevation data in a latitude-longitude range and a longitude range, the file comprises 1201 sampling points, the file name represents the position information of the lower left corner of the data unit, and the data precision is 90 meters; converting map data into a picture with a bmp format, wherein pixel values of points in the picture with the bmp format represent data areas of the image, the scanning mode is from left to right and from top to bottom, color numbers corresponding to pixels of each point are recorded in the part, the recording mode is also determined according to a color mode, each point in a 2-color image occupies 1 bit, each point in a 16-color image occupies 4 bits, and 8 bits are 1 byte; the digital map conversion method comprises the following steps: Step a, calculating gradients of each point to obtain a gradient map with the same size as an original digital map, wherein the gradient represents the change condition of the height difference of the surface curved surface in the east-west direction and the height difference of the surface curved surface in the north-south direction, and the gradient is the first derivative of a data elevation model, and the calculation method comprises the following steps: wherein: p-topography gradient; -the rate of elevation change in the x-direction; -the rate of elevation change in the y-direction; the calculation method of f (x), f (y) is as follows: and f (x) and f (y) are calculated by using a third-order inverse distance square weight difference, wherein the algorithm formula is as follows: In the formula, The elevation value of each vertex is represented, Representing the distance between the grids in the horizontal direction or the vertical direction; And b, performing image segmentation processing on the gradient map by using a threshold segmentation method, wherein after the segmentation processing, each point value is 0 or 1, a corresponding binary map is obtained, a point with a value of 1 represents a valley or a relatively flat terrain, a point with a value of 0 represents a steep ridge terrain, and the threshold segmentation method is as follows: In the formula, Is the planar coordinates of a two-dimensional digital image, Is a coordinate point The gray level of the pixel point above, Is a separation threshold; C, removing noise points with the value of 1, detecting each point with the value of 1, if the point is in a connected area, and if the number of the points with the value of 1 in the connected area is smaller than a constant a, considering the connected area as a mountain top small land or a mountain ridge small land, directly deleting the connected area where the point is located as noise, and assigning the value to be 0; and d, adopting an iterative refinement algorithm for gradually eliminating target boundary points to carry out skeletonization on the binary image.
2. The method for planning unmanned aerial vehicle obstacle avoidance flight path based on the digital elevation map of claim 1, wherein the separation threshold is The determination method of (2) is as follows: b1. Initializing a threshold value To image The method is divided into two types A and B; b2, respectively calculating the average value of the two pixel sets A and B , ; B3, calculating the inter-class variance of the A class and the B class; b4-will be From 0-255 loops, calculating the inter-class variances of A and B respectively, when the inter-class variance is maximum, the corresponding The optimal separation threshold is determined.
3. The unmanned aerial vehicle obstacle avoidance flight path planning method based on the digital elevation map of claim 2, wherein the iterative refinement algorithm is as follows: d1, cycling all points with the value of 1, and marking the pixel points meeting the following conditions as deletion: (1) ; (2) ; (3) ; (4) ; The said Representing heel The number of the pixels with the value of 1 in the adjacent 8 pixels, Representing slave ~ ~ Accumulated times of 0-1 changes in the pixels; d2, cycling all points with the value of 1, and marking the pixel points meeting the following conditions as deletion: (1) ; (2) ; (3) ; (4) ; And (3) cycling the two steps until no pixel is marked to be deleted in the two steps, and outputting a result which is a skeleton after the binary image is thinned.
4. The unmanned aerial vehicle obstacle avoidance flight path planning method of claim 3 wherein the initial flight path point loading comprises reading a configuration file, manually clicking on the map, and manually inputting initial flight path information, the initial flight path information comprising a flight point number, longitude, latitude, and altitude.
5. The unmanned aerial vehicle obstacle avoidance flight path planning method based on the digital elevation map of claim 4, wherein the method for extracting the boundary of the connected region is as follows: initializing a variable i=1; Searching a first pixel position in the background in the binary image, and marking the corresponding equivalence class as the background equivalence class; Step c, traversing the (i+1) th position; step d, merging the corresponding equivalence class with the background equivalence class if the equivalence class is positioned in the background, and jumping to the step i; If the foreground is located in the foreground, detecting the left upper, right upper and right left positions of the foreground, and respectively corresponding to the marks of the equivalent classes, wherein the corresponding equivalent classes in the corresponding foreground equivalent classes are selected to form sets Clt, ct, crt and Cl; F, if the step is empty, jumping to the step i, otherwise, continuing to the step g; Step g, merging the equivalence class in the step e into a foreground equivalence class, and marking the boundary information of the corresponding communication area from 1; merging all foreground equivalence classes, and updating boundary information of a connected region corresponding to the merged equivalence class by using the same method as in the step g; I=i+1, k is the total vertex number, if i < =k, jump to step c, otherwise the algorithm ends.
6. The unmanned aerial vehicle obstacle avoidance flight path planning method based on the digital elevation map of claim 5, wherein the method for calculating the local path comprises the following steps: step a, extracting salient points of barriers contained in each segmented local path by using a template matching mode as a vertex set; Step b, using all points in the vertex set as urban points, and sequencing the vertexes of the barrier and the intersection points of the vertexes and the initial path by using an elastic band formula; C, executing a point removing operation, and deleting points far away from the urban points and points inside the obstacle; And d, calculating the distance between the two intersection points from one intersection point according to two different directions, and taking the urban point with the shorter distance as a path point.

Description

Unmanned aerial vehicle obstacle avoidance flight path planning method based on digital elevation map Technical Field The invention relates to the technical field of unmanned aerial vehicle route planning, in particular to an unmanned aerial vehicle obstacle avoidance route planning method based on a digital elevation map. Background Along with the development of unmanned aerial vehicle technology, unmanned aerial vehicle's application scene is also increasingly widely used, for example is applied to scene such as take photo by plane, air drop supplies, urban fire extinction, electric power inspection, traffic rescue and low altitude are suddenly prevented. In the application scene, in order to realize autonomous flight of the unmanned aerial vehicle, real-time re-planning is often needed for the flight route of the unmanned aerial vehicle, so that the unmanned aerial vehicle is ensured to avoid obstacles in the flight process, safely reach the target position, and further, smooth execution of subsequent tasks is ensured. In the current path planning field, there are two general methods, the first is a method for solving the shortest path in a static road network, the method uses a grid storage mode of a digital map to determine an evaluation function according to the distance, threat degree and other information among nodes, and an optimal flight path is finally obtained under the condition of searching all nodes. However, such methods are relatively poor in real-time performance and are not very friendly to flight tasks with high real-time requirements. The second category is that, starting from obstacle avoidance, optimization and target accessibility of the unmanned aerial vehicle, a path searching method is designed based on a strategy combining global planning and local planning, and mainly comprises the representation of an environment space, the generation of an initial elastic band, the method design of the elastic band for avoiding obstacles, the method design of releasing points on the elastic band and the like. The method has the advantages that the method is simple and feasible, a flight path can be planned quickly, when the shape of the obstacle is complex, the vertex of the obstacle is difficult to find, the problem of overlapping of the obstacle is difficult to treat, and if the added reference node is positioned in the surrounding ring of the obstacle, the path cannot be planned. Disclosure of Invention In view of the above, the invention provides a digital elevation map-based unmanned aerial vehicle obstacle avoidance track planning method, which solves the technical problem that the method in the prior art is difficult to process the path planning of complex obstacles, overlapping of the obstacles, the situation that added reference nodes are located in an obstacle surrounding ring and the like. In order to solve the technical problems, the invention provides a unmanned aerial vehicle obstacle avoidance flight path planning method based on a digital elevation map, which comprises the following steps: s1, loading a digital elevation map; s2, converting map data into pictures; s3, loading an initial track point; S4, extracting key nodes and key paths in the skeleton diagram; s5, generating an optimal track by using an A-algorithm; S6, judging whether an obstacle or a threat zone exists on the optimal track generated in the step 5, if so, executing the step S7, otherwise, executing the step S13; s7, connecting all track points, judging a binary image obstacle communication area by utilizing an algorithm based on a union thought, and extracting the boundary of the communication area; s8, judging whether the path intersects with the obstacle, if so, executing a step S9, otherwise, the starting point and the end point are path points, and executing a step S13; S9, recording the intersection sequence and intersection point of the two adjacent obstacles, and adding a reference node between the two adjacent obstacles; S10, calculating a local path; s11, judging whether the two-to-two path point connecting lines intersect with the obstacle, if so, returning to the step S9, otherwise, generating a section of local path; s12, judging whether each local path completes path planning, if all local path calculation is completed, executing a step S13, otherwise, returning to the step S10; S13, deleting redundant track points, and outputting the obtained path points in sequence; S14, outputting an optimal obstacle avoidance track. Further, the digital elevation map is a file stored in hgt format, where a file contains elevation data within a latitude-longitude range, and includes 1201 x 1201 sampling points, and the file name represents position information of the lower left corner of the data unit, and the data precision is 90 meters. Further, map data are converted into a picture with a bmp format, pixel values of points in the picture with the bmp format represent data areas of the image, the scanning m