CN111272179A - Building space unmanned aerial vehicle route planning method based on seed search - Google Patents

Abstract

The invention discloses a construction space UAV route planning method based on seed search, aiming at the problem of rapid planning of UAV flight routes in complex urban architectural spaces. The method firstly sows several seeds evenly in the space between buildings in the task space, then creates an initial route based on the starting point, copies the seeds to the seed list of the route, and adds the route to the list of planned routes; traverses the list of planned routes to determine each route Whether the last waypoint is visible to the end point, if it is visible, the route is completed, if not, take the n seeds in the seed list of this route that are in sight and close to the last waypoint, and construct n new routes Add to the list of planned routes, and then judge whether the routes are completed one by one. Repeat this until no new routes are generated. Finally, calculate the route with the shortest length from a series of completed routes as the final planning result. It has the characteristics of clear logic, strong adaptability, small amount of code, high execution efficiency and easy expansion.

Description

A route planning method for construction space UAV based on seed search

technical field

The invention proposes a method for planning a UAV route in a building space based on a seed search, which is suitable for the problem of fast and automatic planning of the UAV flight route in a complex urban building space.

Background technique

With the development of UAV and artificial intelligence technology, UAVs have been widely used in various fields. Flight route planning is the basis for UAV mission execution, especially in complex urban building spaces. Aircraft route planning is an important guarantee for the safe and efficient completion of tasks.

Commonly used UAV route planning methods mainly include the following categories: ①Intelligent methods. Including particle swarm optimization algorithm, genetic algorithm, ant colony algorithm, tabu search and heuristic search. ②Geometric method. Such as Voronoi diagrams, etc., combined with some graph theory search methods such as Dijkstra's method to quickly find the optimal path. ③ artificial potential field method, etc. Among them, the genetic algorithm has too slow convergence speed and is easy to fall into local optimum. It can be used in combination with simulated annealing algorithm, but it still cannot really solve the above shortcomings; heuristic search A* algorithm is a classic method for path search and planning, but Its shortcomings in the search process are also obvious; the artificial potential field method is generally optimized by combining Voronoi diagram or genetic algorithm, but the problem is that the algorithm convergence time is too long, and it is generally used for post-processing of route planning. The basic idea of the above method is to reduce the search space and improve the search efficiency through dimensionality reduction. Its essence is still two-dimensional route planning, but it is difficult to consider terrain following and terrain avoidance at the same time, especially for route planning in urban architectural space.

SUMMARY OF THE INVENTION

The invention proposes an algorithm for UAV route planning in view of the complex and changeable urban building environment. The invention has the characteristics of clear and visible logic, high calculation efficiency, easy implementation and debugging, easy expansion, strong compatibility and the like.

The technical problem to be solved by this invention is realized by the following technical solutions:

A method for planning a UAV route in construction space based on seed search, comprising the following steps:

(1) Construction planning model, including mission environment space model: expressing the spatial scope of UAV mission execution, defined as a cube; urban building model: expressing the location and appearance of buildings, all urban building models are bounded by a series of cubes Expression, a complex building is divided into multiple simple cubes that are spliced together; seed model: three-dimensional coordinate points evenly distributed in the environment space, all seeds are in the free area and do not overlap with the building model; route model: start from the starting point , after several seeds, a spatial polyline terminating at the end point, the route includes a set of seeds and a set of waypoints. In the route search, the qualified seeds are taken out from the set of seeds and placed in the set of waypoints until the entire route is opened;

(2) Object declaration, including building model list: used to store all urban building models in the environment; seed list: used to store all seeds; planned route list: used to store temporary routes created during the search process, temporary routes The connection from the start point to the end point has not been completed; the completed route list: store the complete route that has been completed, and the complete route has completed the connection from the start point to the end point;

(3) Obtaining basic information: including obtaining the space range information of the mission environment, all urban building model information, the starting point of the UAV mission, the end point of the UAV mission, and the size constraints of the UAV;

(4) According to the known spatial range of the task environment and the coordinate data of the urban building model, seeds are sown into the environment, and the seeds are evenly filled in the gaps of the urban building model within the spatial range of the task environment, and the interval between the seeds is surrounded by the UAV cube 2 times the maximum side length of the box;

(5) Create an initial route based on the starting point of the route. The initial route only contains one waypoint at the starting point of the UAV mission, copy all the seeds to the seed list in the route, and add the initial route to the planned route list;

(6) Traverse the list of routes in the plan, and determine whether the last waypoint of each route is visible to the end point of the UAV mission. If it is visible, the route is a completed route, and the end point of the UAV mission is added to the route. Take the route out of the planned route list, add it to the completed route list, and go to step (8) after traversing the planned route list; Enter step (7);

(7) Judging the remaining seeds, if the number of remaining seeds is zero or the remaining seeds are not in sight with the last waypoint of the route, then a new route cannot be constructed, the route search process is over, and go to step (8); otherwise, calculate this route The distance between all the remaining seeds and the last waypoint, take the n seeds that are in sight with the last waypoint and the closest distance, construct n routes including the original route, and add the corresponding seeds to the waypoints of the route respectively , as the last waypoint, and remove the corresponding seed from the seed list of the route, and return to step (6); n is the set value;

(8) If the number of routes in the completed route list is 0, there is no route from the start point to the end point of the drone mission, and the route planning is over; if the number of routes in the completed route list is not 0, calculate the distance of each route one by one , and take the route with the shortest distance as the final route of this planning.

Wherein, step (4) specifically comprises the following steps:

为向下取整操作：(401) According to the environmental space SPACE (Xmin, Ymin, Zmin, Xmax, Ymax, Zmax) and the seed interval step=2×UAVSIZE, calculate the seed position point by point, and form the seed position set POS={(x, y, z)| P(x, y, z)}, where P(x, y, z) is defined as follows,

For the round-down operation:

(402) Calculate the spatial relationship between each calculated seed position and each building model in the building model list ListBuilding, if the seed falls in any building model, discard the seed, otherwise add the seed to the seed list ListSeed , then any seed Seed(x,y,z) in the seed list ListSeed is aimed at any building model Building(Xmin, Ymin, Zmin, Xmax, Ymax, Zmax) of the building model list ListBuilding, and satisfies the following conditions:

Seed.x≤Building.Xmin|Seed.x≥Building.Xmax|

Seed.y≤Building.Ymin|Seed.y≥Building.Ymax|

Seed.z≤Building.Zmin|Seed.z≥Building.Zmax

Among them, UAVSIZE is the maximum side length of the UAV cube bounding box, Xmin is the minimum abscissa, Ymin is the minimum ordinate, Zmin is the minimum height coordinate, Xmax is the maximum abscissa, Ymax is the maximum ordinate, and Zmax is the maximum height coordinate.

Among them, the method of judging the visibility of two points in step (6) is: densely sample the connection between the two points pt1 and pt2, if there is a sampling point intersecting with the building model, it is judged that the two points are not visible, and the processing logic is as follows:

Calculate the length of a line connecting two points:

For dense sampling of the connection between two points pt1 and pt2, for any sampling point Pt(x, y, z), the following must be satisfied:

For any sampling point Pt and any building model Building, if the following conditions are met, it is judged that the sampling point intersects with the building model:

Building.Xmin≤Pt.x≤Building.Xmax&

Building.Ymin≤Pt.y≤Building.Ymax&

Building.Zmin≤Pt.z≤Building.Zmax

Building(Xmin, Ymin, Zmin, Xmax, Ymax, Zmax) is the coordinate of any building model.

Among them, in step (7), the distance between all remaining seeds of this route and the last waypoint is calculated, and the n seeds that are in sight with the last waypoint and the distance are the closest are constructed to construct n routes including the original route. The corresponding seeds are added to the route's waypoints as the last waypoint, and the corresponding seeds are removed from the route's seed list, which includes the following steps:

(701) Before constructing a new route based on the original route line, first calculate the distance between the remaining seeds in the route and the last waypoint of this route;

(702) Sort the distances between all the seeds and the last waypoint in ascending order, take out the n seeds closest to the last waypoint, construct n routes including the original route, and add the n seeds to the In the waypoints of n routes, and the corresponding seeds are removed from the seed list of the routes, the algorithm for constructing a new route based on the seed seeds is as follows:

First construct a new route based on the original route line: line1=line;

Then add the seed seed to line1's list of waypoints:

line1.ListPoint.Add(seed);

Finally remove the seed seed from the candidate seed list:

line1.ListSeed.Remove(seed);

ListPoint is the set of waypoints, and ListSeed is the set of candidate seeds for route planning.

The present invention has the following advantages:

1. The present invention uses uniformly distributed space seeds as a medium for route planning, and the position of waypoints is predicted and easy to understand;

2. The present invention adopts the iterative search method for route planning, with a small amount of code and high operating efficiency;

3. The present invention has the characteristics of easy expansion and strong compatibility;

4. The present invention also has the characteristics of being easy to implement and debug.

Description of drawings

FIG. 1 is a schematic diagram of the UAV route planning in urban building space based on seed search according to the present invention.

FIG. 2 is the overall flow of the method of the present invention.

Fig. 3 is the processing flow of the present invention for sowing seeds.

FIG. 4 is a flow chart of the route search process based on seeds of the present invention.

Detailed ways

Hereinafter, the present invention will be further described with reference to FIG. 1 to FIG. 4 .

The invention comprehensively considers factors such as task space range, building distribution, UAV traffic size, etc., and designs a flight route planning method based on seeds evenly distributed in space. The method firstly sows several seeds evenly in the space between buildings in the task space, then creates an initial route based on the starting point, copies the seeds to the seed list of the route, and adds the route to the list of planned routes; traverses the list of planned routes to determine each route Whether the last waypoint is visible to the end point, if it is visible, the route is completed, if not, take n seeds in the seed list of this route that are in sight and close to the last waypoint, and construct n new routes Add to the list of planned routes, and then judge whether the routes are completed one by one. Repeat this until no new routes are generated. Finally, calculate the route with the shortest length from a series of completed routes as the final planning result. As shown in Figure 2, it specifically includes the following steps:

(1) Models used in the construction of route planning, including task environment space model, building model, seed model, and route model. The specific definitions are as follows:

(101) Task environment space model: used to define the space range of the task environment, expressed in a cube space, defined as SPACE(Xmin, Ymin, Zmin, Xmax, Ymax, Zmax), where Xmin is the minimum abscissa of the environment space, Ymin is the minimum ordinate of the environment space, Zmin is the minimum height coordinate of the environment space, Xmax is the maximum abscissa of the environment space, Ymax is the maximum ordinate of the environment space, and Zmax is the maximum height coordinate of the environment space;

(102) Architectural model: The location and appearance of urban buildings are expressed with a cube bounding box. The complex building model is split into a splicing of multiple cube bounding boxes. The building model is defined as: Building(Xmin, Ymin, Zmin, Xmax, Ymax, Zmax), where Xmin is the minimum abscissa of the building model, Ymin is the minimum ordinate of the building model, Zmin is the minimum height coordinate of the building model, Xmax is the maximum abscissa of the building model, Ymax is the maximum ordinate of the building model, Zmax is the maximum height coordinate of the building model;

(103) Seed model: three-dimensional coordinate points evenly distributed in the environment space, defined as Seed(X, Y, Z), where X is the abscissa of the seed, Y is the ordinate of the seed, and Z is the height coordinate of the seed;

(104) Route model: a spatial polyline that starts from the starting point, passes through several seeds, and ends at the end point. The route is defined as Line(ListSeed, ListPoint, isOK), where ListSeed is the set of candidate seeds for route planning, and ListPoint is the set of waypoints. All waypoints are derived from the seed set, and isOK is the completion mark of the route planning, which establishes the route from the start point to the end point.

(2) Object declaration: declare the variables that store various objects in the route planning, mainly including the list of building models, the list of seeds, the list of planned routes, and the list of completed routes, as follows:

(201) Building model list: store all building models, defined as ListBuilding(Building1, Building2,...);

(202) Seed list: store all seeds, which are defined as ListSeed(Seed1, Seed2,...).

(203) List of planned routes: store all unfinished routes, defined as ListTempLine(Line1, Line2, ..., Linen);

(204) List of completed routes: store all completed routes, which are defined as ListFullLine(Line1, Line2, ..., Linen).

(3) Obtain basic information: obtain the space range information of the task environment and save it to the SPACE object; obtain all urban building model information and save it to the ListBuilding object; obtain the coordinates of the starting point of the drone task and save it to the START(X,Y,Z) object ;Get the coordinates of the end point of the drone mission and save it to the END(X,Y,Z) object; get the maximum size of the drone UAVSIZE.

(4) According to the known spatial range of the environment and the coordinate data of the building model, seeds are sown into the environment, and the seeds evenly fill the gap of the building model of the environment. In order to ensure the flight safety of the drone, the interval between the seeds is UAVSIZE, the largest size of the drone. 2 times, as shown in Figure 3, the specific steps are as follows:

(401) According to the environmental space SPACE (Xmin, Ymin, Zmin, Xmax, Ymax, Zmax) and the seed interval step=2×UAVSIZE, calculate the seed position point by point, and form the seed position set POS={(x, y, z)| P(x, y, z)},

为向下取整操作：where P(x, y, z) is defined as follows,

For the round-down operation:

(402) Calculate the spatial relationship between each calculated seed position and each building model in ListBuilding, if the seed falls in any building model, discard the seed, otherwise add the seed to the set ListSeed, then the set Any seed Seed(x,y,z) in ListSeed must meet the following conditions for any building model Building(Xmin, Ymin, Zmin, Xmax, Ymax, Zmax) in the set ListBuilding:

Seed.x≤Building.Xmin|Seed.x≥Building.Xmax|

Seed.y≤Building.Ymin|Seed.y≥Building.Ymax|

Seed.z≤Building.Zmin|Seed.z≥Building.Zmax

As shown in Figure 4, the seed-based route search process is as follows:

(5) Create an initial route based on the starting point of the route. The initial route contains only one waypoint (starting point), copy all the seeds to the seed list in the route, and add the initial route to the planned route list, as follows:

line = new Line();

line.ListSeed = ListSeed;

line.ListPoint.Add(START);

ListTempLine.Add(line);

(6) Traverse the list of routes in the plan, and determine whether the last waypoint of each route is visible to the end point of the UAV mission. If it is visible, the route is a completed route, and the end point of the UAV mission is added to the route. Take the route out of the planned route list, add it to the completed route list, and go to step (8) after traversing the planned route list; Enter step (7);

The method for judging two-point visibility is: densely sample the connection between the two points pt1 and pt2. If there is a sampling point intersecting with the building model, it is judged that the two points are not fully visible. The processing logic is as follows:

Calculate the length of a line connecting two points:

For dense sampling of the connection between two points pt1 and pt2, for any sampling point Pt(x, y, z), the following must be satisfied:

For any sampling point Pt and any building model Building, if the following conditions are met, it is judged that the sampling point intersects with the building model:

Building.Xmin≤Pt.x≤Building.Xmax&

Building.Ymin≤Pt.y≤Building.Ymax&

Building.Zmin≤Pt.z≤Building.Zmax

(7) Judging the remaining seeds, if the number of remaining seeds is zero or the remaining seeds are not in sight with the last waypoint of the route, then a new route cannot be constructed, the route search process is over, and go to step (8); otherwise, calculate this route The distance between all the remaining seeds and the last waypoint, take the n seeds that are in sight with the last waypoint and the closest distance, construct n routes including the original route, and add the corresponding seeds to the waypoints of the route respectively , as the last waypoint, and remove the corresponding seed from the seed list of the route, and return to step (6); n is the set value;

Calculate the distance between all the remaining seeds of this route and the last waypoint, take n seeds that are close to the last waypoint and in line with the last waypoint, construct n routes including the original route, and separate the n seeds Add to the waypoints of n routes, and remove the corresponding seeds from the route's seed list. The specific steps are as follows:

(701) Before constructing a new route based on the original route line, the distance between the remaining seeds in the route and the last waypoint pt of the route should be calculated. The specific calculation method is as follows:

(702) Sort the distances between all seeds and pt in ascending order, take out the n seeds closest to pt, construct n routes including the original route, and add the n seeds to the waypoints of the n routes respectively , and remove the corresponding seed from the seed list of the route. The algorithm for constructing a new route based on the seed seed is as follows:

First construct a new route based on the original route line: line1=line;

Then add the seed seed to line1's list of waypoints:

line1.ListPoint.Add(seed);

Finally remove the seed seed from the candidate seed list:

line1.ListSeed.Remove(seed);

Among them, because the seeds evenly fill the mission space, if the last waypoint is not at the boundary of the mission space, it will always be in the center of a cube composed of the nearest 26 seeds. When constructing a new route, all directions and program operation efficiency should be taken into account. It is recommended that the maximum value of n be 26.

(8) If the number of routes in the completed route list is 0, there is no route from the starting point to the end point, and the route planning ends; if the number of routes in the completed route list is not 0, calculate the distance of each route one by one, and take the shortest distance route as the final route of this planning.

Claims (4)

1. a construction space unmanned aerial vehicle route planning method based on seed search, is characterized in that, comprises the following steps: (1) Construction planning model, including mission environment space model: expressing the spatial scope of UAV mission execution, defined as a cube; urban building model: expressing the location and appearance of buildings, all urban building models are bounded by a series of cubes Expression, a complex building is divided into multiple simple cubes that are spliced together; seed model: three-dimensional coordinate points evenly distributed in the environment space, all seeds are in the free area and do not overlap with the building model; route model: start from the starting point , after several seeds, a spatial polyline terminating at the end point, the route includes a set of seeds and a set of waypoints. In the route search, the qualified seeds are taken out from the set of seeds and placed in the set of waypoints until the entire route is opened; (2) Object declaration, including building model list: used to store all urban building models in the environment; seed list: used to store all seeds; planned route list: used to store temporary routes created during the search process, temporary routes The connection from the start point to the end point has not been completed; the completed route list: store the complete route that has been completed, and the complete route has completed the connection from the start point to the end point; (3) Obtaining basic information: including obtaining the space range information of the mission environment, all urban building model information, the starting point of the UAV mission, the end point of the UAV mission, and the size constraints of the UAV; (4) According to the known spatial range of the task environment and the coordinate data of the urban building model, seeds are sown into the environment, and the seeds are evenly filled in the gaps of the urban building model within the spatial range of the task environment, and the interval between the seeds is surrounded by the UAV cube 2 times the maximum side length of the box; (5) Create an initial route based on the starting point of the route. The initial route only contains one waypoint at the starting point of the UAV mission, copy all the seeds to the seed list in the route, and add the initial route to the planned route list; (6) Traverse the list of routes in the plan, and determine whether the last waypoint of each route is visible to the end point of the UAV mission. If it is visible, the route is a completed route, and the end point of the UAV mission is added to the route. Take the route out of the planned route list, add it to the completed route list, and go to step (8) after traversing the planned route list; Enter step (7); (7) Judging the remaining seeds, if the number of remaining seeds is zero or the remaining seeds are not in sight with the last waypoint of the route, then a new route cannot be constructed, the route search process is over, and go to step (8); otherwise, calculate this route The distance between all the remaining seeds and the last waypoint, take the n seeds that are in sight with the last waypoint and the closest distance, construct n routes including the original route, and add the corresponding seeds to the waypoints of the route respectively , as the last waypoint, and remove the corresponding seed from the seed list of the route, and return to step (6); n is the set value; (8) If the number of routes in the completed route list is 0, there is no route from the start point to the end point of the drone mission, and the route planning is over; if the number of routes in the completed route list is not 0, calculate the distance of each route one by one , and take the route with the shortest distance as the final route of this planning. 2. a kind of construction space unmanned aerial vehicle route planning algorithm based on seed search according to claim 1, is characterized in that, step (4) specifically comprises the following steps: (401) According to the environmental space SPACE (Xmin, Ymin, Zmin, Xmax, Ymax, Zmax) and the seed interval step=2×UAVSIZE, calculate the seed position point by point, and form the seed position set POS={(x, y, z)| P(x, y, z)}, where P(x, y, z) is defined as follows,

For the round-down operation:

(402) Calculate the spatial relationship between each calculated seed position and each building model in the building model list ListBuilding, if the seed falls in any building model, discard the seed, otherwise add the seed to the seed list ListSeed , then any seed Seed(x,y,z) in the seed list ListSeed is aimed at any building model Building(Xmin, Ymin, Zmin, Xmax, Ymax, Zmax) of the building model list ListBuilding, and satisfies the following conditions: Seed.x≤Building.Xmin|Seed.x≥Building.Xmax| Seed.y≤Building.Ymin|Seed.y≥Building.Ymax| Seed.z≤Building.Zmin|Seed.z≥Building.Zmax Among them, UAVSIZE is the maximum side length of the UAV cube bounding box, Xmin is the minimum abscissa, Ymin is the minimum ordinate, Zmin is the minimum height coordinate, Xmax is the maximum abscissa, Ymax is the maximum ordinate, and Zmax is the maximum height coordinate. 3. a kind of construction space unmanned aerial vehicle route planning algorithm based on seed search according to claim 1, is characterized in that, in step (6), judging that the method that two points are visible is: to the connection of two points pt1 and pt2. Line dense sampling, if there is a sampling point intersecting with the building model, it is judged that the two points are not in sight. The processing logic is as follows: Calculate the length of a line connecting two points:

For dense sampling of the connection between two points pt1 and pt2, for any sampling point Pt(x, y, z), the following must be satisfied:

For any sampling point Pt and any building model Building, if the following conditions are met, it is judged that the sampling point intersects with the building model: Building.Xmin≤Pt.x≤Building.Xmax& Building.Ymin≤Pt.y≤Building.Ymax& Building.Zmin≤Pt.z≤Building.Zmax Building(Xmin, Ymin, Zmin, Xmax, Ymax, Zmax) is the coordinate of any building model. 4. a kind of construction space unmanned aerial vehicle route planning algorithm based on seed search according to claim 1, is characterized in that, in step (7), calculate the distance of all remaining seeds of this route and last waypoint, get and last A waypoint is visible and the nearest n seeds, construct n routes including the original route, add the corresponding seeds to the waypoints of the route respectively, as the last waypoint, and add the corresponding seeds from the route. is removed from the torrent list, which includes the following steps: (701) Before constructing a new route based on the original route line, first calculate the distance between the remaining seeds in the route and the last waypoint of this route; (702) Sort the distances between all the seeds and the last waypoint in ascending order, take out the n seeds closest to the last waypoint, construct n routes including the original route, and add the n seeds to the In the waypoints of n routes, and the corresponding seeds are removed from the seed list of the routes, the algorithm for constructing a new route based on the seed seeds is as follows: First construct a new route based on the original route line: line1=line; Then add the seed seed to line1's list of waypoints: line1.ListPoint.Add(seed); Finally remove the seed seed from the candidate seed list: line1.ListSeed.Remove(seed); ListPoint is a set of waypoints, and ListSeed is a set of candidate seeds for route planning.

Images