CN111486847B - Unmanned aerial vehicle navigation method and system - Google Patents
Unmanned aerial vehicle navigation method and system Download PDFInfo
- Publication number
- CN111486847B CN111486847B CN202010359481.0A CN202010359481A CN111486847B CN 111486847 B CN111486847 B CN 111486847B CN 202010359481 A CN202010359481 A CN 202010359481A CN 111486847 B CN111486847 B CN 111486847B
- Authority
- CN
- China
- Prior art keywords
- matrix
- grid point
- time
- navigation
- target
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Active
Links
Images
Classifications
-
- G—PHYSICS
- G01—MEASURING; TESTING
- G01C—MEASURING DISTANCES, LEVELS OR BEARINGS; SURVEYING; NAVIGATION; GYROSCOPIC INSTRUMENTS; PHOTOGRAMMETRY OR VIDEOGRAMMETRY
- G01C21/00—Navigation; Navigational instruments not provided for in groups G01C1/00 - G01C19/00
- G01C21/20—Instruments for performing navigational calculations
Landscapes
- Engineering & Computer Science (AREA)
- Radar, Positioning & Navigation (AREA)
- Remote Sensing (AREA)
- Automation & Control Theory (AREA)
- Physics & Mathematics (AREA)
- General Physics & Mathematics (AREA)
- Traffic Control Systems (AREA)
- Navigation (AREA)
Abstract
The invention discloses an unmanned aerial vehicle navigation method and system, firstly, an extended hierarchical graph of a target flight area environment is constructed based on original time-space index data of a target flight area of an unmanned aerial vehicle, then forward search is carried out in batch on a time dimension through a forward search matrix, parallel search can be realized, and a backward path navigation matrix is obtained; according to the method, the problem of the shortest path is converted into the optimal path planning with the minimum crash expectation by fusing index data with respect to the multi-target optimization problem in the complex dynamic environment, the optimal path planning can be efficiently performed from one starting point to a plurality of target points, the navigation accuracy of the unmanned aerial vehicle is improved, and the calculation efficiency is high when the unmanned aerial vehicle is navigated in the three-dimensional dynamic environment while the navigation safety is met.
Description
Technical Field
The invention belongs to the field of path planning, and particularly relates to an unmanned aerial vehicle navigation method and system.
Background
With the rapid development of the unmanned aerial vehicle technology, the unmanned aerial vehicle gradually develops from the original military field to the civil field, wherein the unmanned aerial vehicle navigation, namely, the optimal flight path from a starting point to a target point is planned under the environmental constraint condition and the unmanned aerial vehicle self-maneuvering performance constraint condition, and plays an increasingly important role in multiple industries such as logistics, rescue and the like, so that the research on the unmanned aerial vehicle navigation method and system has important significance.
A complete unmanned aerial vehicle navigation process is divided into three parts, namely representation of an environment to be explored, obtaining of a path by adopting a path planning algorithm and smoothing and optimization processing of the path. The representation of the to-be-explored environment is an important premise of the unmanned aerial vehicle track planning technology, and when the existing unmanned aerial vehicle navigation method represents the to-be-explored environment, the relation between adjacent space and time grids is not always considered, so that the navigation precision is further influenced. Further, the existing unmanned aerial vehicle navigation method usually adopts a path planning algorithm based on a graph search planning and a sampling-based planning to obtain a path. Typical representations of graph search are Dijkstra and heuristic a algorithms, and typical representations of sampling-based planning algorithms are stochastic roadmap (PRM) and fast-expanding Random Trees (RRT). In a common two-dimensional map, the search space of the map is limited to the specification of the map, the calculation expense is within an acceptable range, and the algorithm can obtain a planning path with effective and acceptable efficiency; however, when the time dimension is increased in a common two-dimensional environment and the environment is converted into a three-dimensional dynamic environment, the search space of the method is greatly increased, a large amount of computing resources are consumed, and the computing efficiency is low.
Disclosure of Invention
In view of the above drawbacks or needs for improvement in the prior art, the present invention provides a method and system for navigating an unmanned aerial vehicle, so as to solve the technical problem of low computational efficiency when navigating in a three-dimensional dynamic environment in the prior art.
In order to achieve the above object, in a first aspect, the present invention provides a method for navigating a drone, including the following steps:
s1, acquiring original time-space index data of a target flight area of the unmanned aerial vehicle, preprocessing the acquired original time-space index data according to categories, and setting the traffic probability of grids with the index data exceeding the preset threshold range of the corresponding category as 0; wherein the target flight area is pre-divided into a plurality of grids;
s2, inputting the index data of each category into the corresponding pre-trained machine learning model, integrating the obtained results to obtain the passable probability of each grid in the target flight area, and constructing an extended hierarchical diagram of the target flight area environment according to the passable probability of each grid; wherein, the elements in the expansion hierarchical diagram represent the crash probability of the grid point where the element is located at a certain moment;
s3, initializing the forward search matrix MeBased on the obtained expansion hierarchical diagram, starting from the initial grid point of the target flight area, and based on the principle of minimum crash probability, the forward exploration matrix M iseMoving according to explorable direction, and conducting forward exploration along time dimension to obtain backward navigation matrix Mn；
S4, based on the obtained backward navigation matrix MnAnd sequentially starting from each target grid point in the target grid point list, and backtracking until the starting grid point of the target flight area is added into the navigation path to obtain the navigation path.
Further preferably, the raw spatiotemporal index data includes: a spatial position-dependent index and a time instant-dependent index; wherein the spatial location dependent indicators comprise a relief map and a crash influence map; the time-dependent metrics include a weather cloud graph and an energy consumption graph.
Further preferably, the step S3 includes the following steps:
s31, initializing the forward search matrix MeLet forward explore matrix MeIs the same as the size of the target flight area, and a forward exploration matrix M is formedeInitializing the element corresponding to the initial grid point position to 0, initializing the other elements to 1, and setting the current time t to 0;
s32, based on the expanded hierarchical diagram, obtaining the passable matrix at the time t
S33, forward search matrix at t moment
Shifting a grid according to a certain explorable direction, filling blank positions in the shifted forward exploration matrix with 1, and enabling the blank positions to be matched with the passable matrix
Aligned in the exploration direction and based on the passable matrix
Calculating the crash probability of all grid points in the current exploration direction from the time t to the time t +1 by using the moved forward exploration matrix, storing the crash probability into a temporary storage matrix, repeating the step S33 until all explorable directions are traversed, and storing the crash probability of each exploration direction at each grid point from the time t to the time t +1 in the temporary storage matrix;
s34, storing the minimum value of the crash probability in each searching direction at each grid point from the moment t to the moment t +1 in the temporary storage matrix into the forward searching matrix at the moment t +1
And storing the path navigation matrix corresponding to the exploration direction corresponding to the minimum value of the crash probability at each grid point from the moment t to the moment t +1 in the temporary storage matrix into the moment t +1
In (1), the obtained path navigation matrix at the time t +1
Storing a backward path navigation matrix Mn;
s35, let t be t + 1;
s36, repeating the steps S32-S35 until all target grid points in the target grid point list are explored completely or the energy of the unmanned aerial vehicle is exhausted, and obtaining the backward navigation matrix Mn。
Further preferably, the crash probability of all grid points in the current exploration direction from time t to time t +1 is:
wherein, is the Hadamard product,
the element in (a) represents the lowest probability of crash from the starting grid point to the trajectory of the grid point at which the element is located at time t,
the element in (1) represents the crash probability of the grid point where the element is located at the time t.
Further preferably, the backward path navigation matrix MnIs a three-dimensional matrix with a size of X Y X TnWherein X and Y are respectively the number of rows and columns of the backward path navigation matrix, TnIs the termination time of the method described in step S3.
Further preferably, a Graphics Processing Unit (GPU) is used to execute the matrix operation in step S3, so as to further increase the parallel computing speed and improve the algorithm efficiency.
Further preferably, the step S4 includes the following steps:
s41, according to the obtained backward navigation matrix MnFor a certain target grid point in the target grid point list, finding the last moment when the grid point is explored;
s42, starting from the position where the last time of the grid point is, based on the backward navigation matrix MnBacktracking backwards, finding the position of the grid point at the previous moment, and adding the position into the optimal path of the target grid point;
s43, setting the last position of the grid point as the position of the last time of the grid point;
s44, repeating the steps S42-S43 until the starting grid point is visited, and at the moment, completing the construction of the optimal path from the starting grid point to one target grid point of the target flight area;
s43, repeating the steps S41-S44 until all the target grid points in the target grid point list are traversed, and obtaining the navigation path.
Further preferably, the unmanned aerial vehicle navigation method provided by the first aspect of the present invention is also applicable to navigation of unmanned vehicles other than unmanned aerial vehicles.
In a second aspect, the present invention provides an unmanned aerial vehicle navigation system, including: the system comprises an environmental data acquisition module, an environmental information processing module, a forward path exploration module and a track backtracking reconstruction module;
the environment data acquisition module is used for acquiring original time-space index data of a target flight area of the unmanned aerial vehicle and outputting the data to the environment information processing module; wherein the target flight area is pre-divided into a plurality of grids;
the environment information processing module is used for preprocessing the original time-space index data input by the environment data acquisition module according to the category and setting the traffic probability of the grids of which the index data exceeds the preset threshold range of the corresponding category as 0; respectively inputting the index data of each category into a corresponding pre-trained machine learning model, synthesizing the obtained results to obtain the passable probability of each grid in the target flight area, constructing an extended hierarchical diagram of the environment of the target flight area according to the passable probability of each grid, and outputting the extended hierarchical diagram to a forward path exploration module; wherein, the elements in the expansion hierarchical diagram represent the crash probability of the grid point where the element is located at a certain moment;
the forward path exploration module is used for initializing a forward exploration matrix MeBased on the obtained expansion hierarchical diagram, starting from the initial grid point of the target flight area, and based on the principle of minimum crash probability, the forward exploration matrix M iseMoving according to explorable direction, and conducting forward exploration along time dimension to obtain backward navigation matrix MnAnd output to the trace backtracking reconstruction module;
the track backtracking reconstruction module is used for inputting the information into a backward navigation matrix M based on the forward path exploration modulenAnd sequentially starting from each target grid point in the target grid point list, and backtracking until the starting grid point of the target flight area is added into the navigation path to obtain the navigation path.
Generally, by the above technical solution conceived by the present invention, the following beneficial effects can be obtained:
1. the invention provides an unmanned aerial vehicle navigation method, which comprises the steps of firstly constructing an extended hierarchical graph of a target flight area environment based on original time-space index data of a target flight area of an unmanned aerial vehicle, then carrying out forward search in batch on a time dimension through a forward search matrix, realizing parallel search and obtaining a backward path navigation matrix; and finally, performing backward backtracking based on a backward path navigation matrix to obtain a final navigation path.
2. In the unmanned aerial vehicle navigation method provided by the invention, an expansion hierarchical diagram is constructed based on original space-time index data of a target flight area of the unmanned aerial vehicle, and a dynamic environment is modeled by using time characteristics in a hierarchical mode aiming at a rasterized environment; factors influencing the flight of the unmanned aerial vehicle in the environment are fused to generate passable probability, the accuracy of the modeling method is improved by using a machine learning method, the relation between adjacent space and time grids is considered in the modeling process, and the navigation precision is further improved.
3. The unmanned aerial vehicle navigation method provided by the invention simulates parallelization exploration of all possible positions of the unmanned aerial vehicle from the moment t to the moment t +1 in all movable directions by utilizing the operation of translation alignment of the exploration matrix, carries out Hadamard multiplication of corresponding positions on the exploration matrix and the passable matrix at the moment t, stores the multiplication result in each direction into a temporary storage matrix, then takes the minimum value of each position of the temporary storage matrix in all directions, and records the direction of the minimum value by using the navigation matrix for backward backtracking. By utilizing the translation alignment of the exploration matrix, the unmanned aerial vehicle is explored in the global search space, the navigation matrix is used for recording the optimal path in the global search, and the search efficiency is high. In addition, the invention can accelerate the exploration process by using the GPU, has very high-efficiency planning efficiency in practical use, can solve the problem of real-time path navigation, and is suitable for navigation of unmanned vehicles except unmanned vehicles besides the unmanned vehicles.
Drawings
Fig. 1 is a flowchart of an unmanned aerial vehicle navigation method according to an embodiment of the present invention;
fig. 2 is a schematic diagram of time-dependent and space-dependent index data in a target flight area provided in embodiment 1 of the present invention; wherein, the picture (a) is a crash influence picture; the figure (b) is a meteorological cloud;
fig. 3 is a schematic diagram of a learning process of time-dependent and space-dependent index data in a target flight area provided in embodiment 1 of the present invention; wherein, the graph (a) is a learning process schematic diagram of the crash influence graph; the figure (b) is a schematic diagram of a meteorological cloud picture learning process;
fig. 4 is a schematic diagram of performing an exploration in each exploration direction by using a forward exploration matrix according to embodiment 1 of the present invention.
Detailed Description
In order to make the objects, technical solutions and advantages of the present invention more apparent, the present invention is described in further detail below with reference to the accompanying drawings and embodiments. It should be understood that the specific embodiments described herein are merely illustrative of the invention and are not intended to limit the invention. In addition, the technical features involved in the embodiments of the present invention described below may be combined with each other as long as they do not conflict with each other.
Examples 1,
A method for navigating a drone, as shown in fig. 1, includes the following steps:
s1, acquiring original time-space index data of a target flight area of the unmanned aerial vehicle, preprocessing the acquired original time-space index data according to categories, and setting the traffic probability of grids with the index data exceeding the preset threshold range of the corresponding category as 0; wherein the target flight area is pre-divided into a plurality of grids;
specifically, the target flight area is divided into X rows × Y columns of grids in advance. The original time-space index data of the target flight area of the unmanned aerial vehicle can be obtained by using sensors, historical data, weather forecast and other sources. The raw spatio-temporal index data includes: a spatial position-dependent index and a time instant-dependent index; wherein the spatial position dependent indicator comprises a relief map GD1(X Y) and crash influence diagram GD2(X Y) which does not change for a long time, and the size of the (X Y) is corresponding to the size of the target flight area; the time-dependent indicators comprise a weather cloud TD1(X Y T) and energy consumption map TD2(X Y T) is a value (X Y T) which varies greatly in a short time depending on time, wherein T represents time. Preprocessing the obtained original space-time index data according to categories, presetting threshold ranges corresponding to various indexes, and setting the traffic probability of grids with the index data exceeding the preset threshold ranges corresponding to the categories as 0. In particular, as shown in FIG. 2The middle (b) diagram shows a meteorological cloud diagram, i.e. a space-time index representing meteorological data in a target airspace, wherein the preset threshold range of the wind speed is [0, 14 ]]When the wind speed in the grid point is greater than 14, the unmanned aerial vehicle is considered to be an obstacle area, the danger is extreme, the passable probability is 0, and the unmanned aerial vehicle can crash when passing through the area.
S2, inputting the index data of each category into the corresponding pre-trained machine learning model, integrating the obtained results to obtain the passable probability of each grid in the target flight area, and constructing an extended hierarchical diagram of the target flight area environment according to the passable probability of each grid; wherein, the elements in the expansion hierarchical diagram represent the crash probability of the grid point where the element is located at a certain moment;
specifically, for different types of index data, different machine learning models are adopted to map the index data into the passable probability of the grid corresponding to the index data. Specifically, as shown in fig. 2 (a), for the crash influence graph, any grid point in the graph has a numerical association relationship with its neighbor grid point, and effective association information can be learned from its neighboring neighbor grid points by learning a convolutional neural network kernel and generating an association relationship kernel. Inputting the crash influence graph into a pre-trained machine learning model, and obtaining the passable probability of each grid in the target flight area under the current index data type through the learning process shown in the graph (a) in fig. 3 by utilizing the geodetic correlation. For the weather cloud picture, as shown in (b) of fig. 2, it reflects that the weather condition of a specific geographic spatial location at a specific time is heavily dependent on the specific time, so that any grid point in the picture is considered to have a relation not only in space but also in a time interval, and the time correlation can be utilized to learn related information from neighbor grid points in a time interval by learning a higher-dimensional association relation kernel, so that the grid point has richer information. Inputting the crash influence graph into a pre-trained machine learning model, and obtaining the passable probability of each grid in the target flight area under the current index data type through the learning process shown in the graph (b) in fig. 3. Wherein, by pre-treatingCollecting historical index data of each category to form a training set, and respectively training corresponding machine learning models to obtain pre-trained machine learning models; specifically, taking historical meteorological data as an example, the meteorological features are split and then spliced, and a linear regression model is used for learning the corresponding association relationship to generate a final prediction model. And finally, integrating the passable probability of each grid in the target flight area under each index data type, and according to the weight of each index data type and the formula S ═ w1·e1+w2·e2+…+wn·enPerforming fusion (wherein, wiIs a weight, eiAnd in order to influence the index, i is 1, 2, a.
S3, initializing the forward search matrix MeBased on the obtained expansion hierarchical diagram, starting from the initial grid point of the target flight area, and based on the principle of minimum crash probability, the forward exploration matrix M iseMoving according to explorable direction, and conducting forward exploration along time dimension to obtain backward navigation matrix Mn；
Specifically, the method comprises the following steps:
s31, initializing the forward search matrix MeLet forward explore matrix MeIs the same as the size of the target flight area, is X multiplied by Y, and the forward exploration matrix MeInitializing the element corresponding to the initial grid point position to 0, initializing the other elements to 1, and setting the current time t to 0; forward exploration matrix MeThe element in (1) represents the lowest crash probability from the starting grid point to the trajectory of the grid point where the current element is located;
s32, based on the expanded hierarchical diagram, obtaining the passable matrix at the time t
Also X Y in size, passable matrix
The element in (2) represents the crash probability of the grid point where the current element is located;
s33, forward search matrix at t moment
Shifting a grid according to a certain explorable direction, filling blank positions in the shifted forward exploration matrix with 1, and enabling the blank positions to be matched with the passable matrix
Aligned in the exploration direction and based on the passable matrix
And calculating crash probabilities of all grid points in the current exploration direction from the time t to the time t +1 by using the moved forward exploration matrix, storing the crash probabilities into a temporary storage matrix, repeating the step S33 until all explorable directions are traversed, wherein the crash probabilities of all the exploration directions at each grid point from the time t to the time t +1 are stored in the temporary storage matrix, and the crash probabilities have the size of X multiplied by Y multiplied by LsWherein L issThe number of search directions;
specifically, the search direction may be 4 directions or 8 directions or 26 three-dimensional directions, in this embodiment, the search direction is four directions, i.e., up, down, left, and right, and the forward search matrix at time t
For example, the size of (a) is 4 × 4, and as shown in fig. 4, the forward search matrix at time t is used
When searching upwards, the whole forward search matrix is translated upwards by one grid, and blank positions in the moved forward search matrix are filled to be 1, at the moment, the forward search matrix at the time t
And a passable matrix
Aligned in the exploration direction, the above process can be considered as a forward exploration behavior in the exploration direction. Forward exploration matrix of t time
And a passable matrix
And carrying out Hadamm multiplication to obtain the crash probability of all grid points in the current exploration direction from the time t to the time t + 1. Specifically, the crash probability of all grid points in the current exploration direction from time t to time t +1 is as follows:
wherein, is the Hadamard product,
the element in (a) represents the lowest probability of crash from the starting grid point to the trajectory of the grid point at which the element is located at time t,
the element in (1) represents the crash probability of the grid point where the element is located at the time t,
the element in (1) represents the security probability of the trajectory from the starting grid point to the grid point where the current element is located,
the element in (1) represents the passable probability of the grid point where the current element is located, and the two corresponding positions are multiplied to obtain the safety probability of the track after exploration. Specifically, the GPU may be used to perform the matrix operation in step S3And the parallel computing speed is further accelerated, and the algorithm efficiency is improved. Further, after the search in all search directions is completed, the temporary storage matrix stores the expansion results in all search directions from time t to time t + 1, so that each grid is expanded by the predecessor grids from different search directions.
S34, storing the minimum value of the crash probability in each searching direction at each grid point from the moment t to the moment t +1 in the temporary storage matrix into the forward searching matrix at the moment t +1
And storing the path navigation matrix corresponding to the exploration direction corresponding to the minimum value of the crash probability at each grid point from the moment t to the moment t +1 in the temporary storage matrix into the moment t +1
In (1), the obtained path navigation matrix at the time t +1
Storing backward path navigation matrix Mn；
Specifically, the crash probability in each exploration direction corresponding to each grid from the moment t to the moment t +1 in the temporary storage matrix is minimized, namely, the safest exploration direction is found and stored into the backward path navigation matrix Mn。
S35, let t be t + 1;
s36, repeating the steps S32-S35 until all target grid points in the target grid point list are explored completely or the energy of the unmanned aerial vehicle is exhausted, and obtaining the backward navigation matrix Mn。
S4, based on the obtained backward navigation matrix MnAnd sequentially starting from each target grid point in the target grid point list, and backtracking until the starting grid point of the target flight area is added into the navigation path to obtain the navigation path.
Specifically, the method comprises the following steps:
s41, according to the obtained backward navigation matrix MnTo the target gridFinding a target grid point in the point list, and searching the last moment of the grid point;
s42, starting from the position where the last time of the grid point is, based on the backward navigation matrix MnBacktracking backwards, finding the position of the grid point at the previous moment, and adding the position into the optimal path of the target grid point;
s43, setting the last position of the grid point as the position of the last time of the grid point;
s44, repeating the steps S42-S43 until the starting grid point is visited, and at the moment, completing the construction of the optimal path from the starting grid point to one target grid point of the target flight area;
s43, repeating the steps S41-S44 until all the target grid points in the target grid point list are traversed, and obtaining the navigation path.
Examples 2,
A drone navigation system comprising: the system comprises an environmental data acquisition module, an environmental information processing module, a forward path exploration module and a track backtracking reconstruction module;
the environment data acquisition module is used for acquiring original time-space index data of a target flight area of the unmanned aerial vehicle and outputting the data to the environment information processing module; wherein the target flight area is pre-divided into a plurality of grids; specifically, sensor equipment on the unmanned aerial vehicle can be used for collecting surrounding entity obstacle information, topographic information stored in a navigation database is used, and a weather forecasting system is used for acquiring real-time weather and meteorological information;
the environment information processing module is used for preprocessing the original time-space index data input by the environment data acquisition module according to the category and setting the traffic probability of the grids of which the index data exceeds the preset threshold range of the corresponding category as 0; respectively inputting the index data of each category into a corresponding pre-trained machine learning model, synthesizing the obtained results to obtain the passable probability of each grid in the target flight area, constructing an extended hierarchical diagram of the environment of the target flight area according to the passable probability of each grid, and outputting the extended hierarchical diagram to a forward path exploration module; wherein, the elements in the expansion hierarchical diagram represent the crash probability of the grid point where the element is located at a certain moment;
the forward path exploration module is used for initializing a forward exploration matrix MeBased on the obtained expansion hierarchical diagram, starting from the initial grid point of the target flight area, and based on the principle of minimum crash probability, the forward exploration matrix M iseMoving according to explorable direction, and conducting forward exploration along time dimension to obtain backward navigation matrix MnAnd output to the trace backtracking reconstruction module;
the track backtracking reconstruction module is used for inputting the information into a backward navigation matrix M based on the forward path exploration modulenAnd sequentially starting from each target grid point in the target grid point list, and backtracking until the starting grid point of the target flight area is added into the navigation path to obtain the navigation path.
It will be understood by those skilled in the art that the foregoing is only a preferred embodiment of the present invention, and is not intended to limit the invention, and that any modification, equivalent replacement, or improvement made within the spirit and principle of the present invention should be included in the scope of the present invention.
Claims (9)
1. An unmanned aerial vehicle navigation method is characterized by comprising the following steps:
s1, acquiring original time-space index data of a target flight area of the unmanned aerial vehicle, preprocessing the acquired original time-space index data according to categories, and setting the traffic probability of grids with the index data exceeding the preset threshold range of the corresponding category as 0; wherein the target flight area is pre-divided into a plurality of grids;
s2, inputting the index data of each category into the corresponding pre-trained machine learning model, integrating the obtained results to obtain the passable probability of each grid in the target flight area, and constructing an extended hierarchical diagram of the target flight area environment according to the passable probability of each grid; wherein, the elements in the expansion hierarchical diagram represent the crash probability of the grid point where the element is located at a certain moment;
s3, initializing the forward search matrix MeBased on the obtained expansion hierarchical diagram, starting from the initial grid point of the target flight area, and based on the principle of minimum crash probability, the forward exploration matrix M iseMoving according to explorable direction, and conducting forward exploration along time dimension to obtain backward navigation matrix Mn；
S4, based on the obtained backward navigation matrix MnAnd sequentially starting from each target grid point in the target grid point list, and backtracking until the starting grid point of the target flight area is added into the navigation path to obtain the navigation path.
2. The drone navigation method of claim 1, wherein the raw spatiotemporal index data includes: a spatial position-dependent index and a time instant-dependent index; wherein the spatial location dependent indicators comprise a relief map and a crash influence map; the time-dependent metrics include a weather cloud graph and an energy consumption graph.
3. The method for navigating unmanned aerial vehicle according to claim 1, wherein the step S3 comprises the steps of:
s31, initializing the forward search matrix MeLet forward explore matrix MeIs the same as the size of the target flight area, and a forward exploration matrix M is formedeInitializing the element corresponding to the initial grid point position to 0, initializing the other elements to 1, and setting the current time t to 0;
s32, based on the expanded hierarchical diagram, obtaining the passable matrix at the time t
S33, forward search matrix at t moment
Shifting a grid according to a certain explorable direction, filling blank positions in the shifted forward exploration matrix with 1, and enabling the blank positions to be matched with the passable matrix
Aligned in the exploration direction and based on the passable matrix
Calculating the crash probability of all grid points in the current exploration direction from the time t to the time t +1 by using the moved forward exploration matrix, storing the crash probability into a temporary storage matrix, repeating the step S33 until all explorable directions are traversed, and storing the crash probability of each exploration direction at each grid point from the time t to the time t +1 in the temporary storage matrix;
s34, storing the minimum value of the crash probability in each searching direction at each grid point from the moment t to the moment t +1 in the temporary storage matrix into the forward searching matrix at the moment t +1
And storing the path navigation matrix corresponding to the exploration direction corresponding to the minimum value of the crash probability at each grid point from the moment t to the moment t +1 in the temporary storage matrix into the moment t +1
In (1), the obtained path navigation matrix at the time t +1
Storing the backward navigation matrix Mn;
s35, let t be t + 1;
s36, repeating the steps S32-S35 until all target grid points in the target grid point list are explored completely or the energy of the unmanned aerial vehicle is exhausted, and obtaining the backward navigation matrix Mn。
4. The unmanned aerial vehicle navigation method of claim 3, wherein the probability of crash of all grid points in the current exploration direction from time t to time t +1 is:
wherein, is the Hadamard product,
the element in (a) represents the lowest probability of crash from the starting grid point to the trajectory of the grid point at which the element is located at time t,
the element in (1) represents the crash probability of the grid point where the element is located at the time t.
5. The drone navigation method of claim 3, wherein the backward navigation matrix MnIs a three-dimensional matrix with a size of X Y X TnWherein X and Y are the backward navigation matrix M respectivelynNumber of rows and columns, TnIs the termination time of said step S3.
6. The drone navigation method of claim 3, wherein the matrix operation in step S3 is performed using a GPU.
7. The unmanned aerial vehicle navigation method of claim 1, comprising the steps of:
s41, according to the obtained backward navigation matrix MnFor a certain target grid point in the target grid point list, finding the last moment when the grid point is explored;
s42, starting from the position where the last time of the grid point is, based on the backward navigation matrix MnBacktracking backwards, finding the position of the grid point at the previous moment, and adding the position into the optimal path of the target grid point;
s43, setting the last position of the grid point as the position of the last time of the grid point;
s44, repeating the steps S42-S43 until the starting grid point is visited, and at the moment, completing the construction of the optimal path from the starting grid point to one target grid point of the target flight area;
s43, repeating the steps S41-S44 until all the target grid points in the target grid point list are traversed, and obtaining the navigation path.
8. The method of any one of claims 1-7, further comprising navigating an unmanned vehicle other than the drone.
9. An unmanned aerial vehicle navigation system, comprising: the system comprises an environmental data acquisition module, an environmental information processing module, a forward path exploration module and a track backtracking reconstruction module;
the environment data acquisition module is used for acquiring original time-space index data of a target flight area of the unmanned aerial vehicle and outputting the data to the environment information processing module; wherein the target flight area is pre-divided into a plurality of grids;
the environment information processing module is used for preprocessing the environment data acquisition module input to the original space-time index data according to categories, and setting the traffic probability of the grids of which the index data exceeds the preset threshold range of the corresponding category as 0; respectively inputting the index data of each category into a corresponding pre-trained machine learning model, synthesizing the obtained results to obtain the passable probability of each grid in the target flight area, constructing an extended hierarchical diagram of the environment of the target flight area according to the passable probability of each grid, and outputting the extended hierarchical diagram to a forward path exploration module; wherein, the elements in the expansion hierarchical diagram represent the crash probability of the grid point where the element is located at a certain moment;
the forward path exploration module is used for initializing a forward exploration matrix MeBased on the obtained expansion hierarchical diagram, starting from the initial grid point of the target flight area, and based on the principle of minimum crash probability, the forward exploration matrix M iseMoving according to explorable direction, and conducting forward exploration along time dimension to obtain backward navigation matrix MnAnd output to the trace backtracking reconstruction module;
the track backtracking reconstruction module is used for inputting the information into a backward navigation matrix M based on a forward path exploration modulenAnd sequentially starting from each target grid point in the target grid point list, and backtracking until the starting grid point of the target flight area is added into the navigation path to obtain the navigation path.
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN202010359481.0A CN111486847B (en) | 2020-04-29 | 2020-04-29 | Unmanned aerial vehicle navigation method and system |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN202010359481.0A CN111486847B (en) | 2020-04-29 | 2020-04-29 | Unmanned aerial vehicle navigation method and system |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| CN111486847A CN111486847A (en) | 2020-08-04 |
| CN111486847B true CN111486847B (en) | 2021-10-08 |
Family
ID=71795316
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| CN202010359481.0A Active CN111486847B (en) | 2020-04-29 | 2020-04-29 | Unmanned aerial vehicle navigation method and system |
Country Status (1)
| Country | Link |
|---|---|
| CN (1) | CN111486847B (en) |
Families Citing this family (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN116467493B (en) * | 2023-04-24 | 2024-06-18 | 中煤科工集团重庆研究院有限公司 | Mine disaster tracing method based on knowledge graph |
Family Cites Families (10)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN105043396B (en) * | 2015-08-14 | 2018-02-02 | 北京进化者机器人科技有限公司 | The method and system of self-built map in a kind of mobile robot room |
| US10635913B2 (en) * | 2016-10-17 | 2020-04-28 | Mediatek Inc. | Path planning method and related navigation device |
| CN106970648B (en) * | 2017-04-19 | 2019-05-14 | 北京航空航天大学 | Unmanned plane multi-goal path plans combined method for searching under the environment of city low latitude |
| KR101964001B1 (en) * | 2018-02-14 | 2019-03-29 | 동국대학교 산학협력단 | Method for generating flight path of drone based on image and apparatus thereof |
| CN109238288A (en) * | 2018-09-10 | 2019-01-18 | 电子科技大学 | Autonomous navigation method in a kind of unmanned plane room |
| CN109597425B (en) * | 2018-10-18 | 2021-10-26 | 中国航空无线电电子研究所 | Unmanned aerial vehicle navigation and obstacle avoidance method based on reinforcement learning |
| CN110514206B (en) * | 2019-08-02 | 2023-08-04 | 中国航空无线电电子研究所 | Unmanned aerial vehicle flight path prediction method based on deep learning |
| CN110488872B (en) * | 2019-09-04 | 2023-03-07 | 中国人民解放军国防科技大学 | Unmanned aerial vehicle real-time path planning method based on deep reinforcement learning |
| CN110672088B (en) * | 2019-09-09 | 2021-03-30 | 北京航空航天大学 | Unmanned aerial vehicle autonomous navigation method imitating homing mechanism of landform perception of homing pigeons |
| CN110849350A (en) * | 2019-10-30 | 2020-02-28 | 西北工业大学 | Construction method of three-dimensional track planning space |
-
2020
- 2020-04-29 CN CN202010359481.0A patent/CN111486847B/en active Active
Also Published As
| Publication number | Publication date |
|---|---|
| CN111486847A (en) | 2020-08-04 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| CN113110592B (en) | Unmanned aerial vehicle obstacle avoidance and path planning method | |
| CN112216108B (en) | Traffic prediction method based on attribute-enhanced space-time graph convolution model | |
| CN103994768B (en) | Method and system for seeking for overall situation time optimal path under dynamic time varying environment | |
| CN104731963B (en) | Recommend method and system in a kind of gridding path based on car networking | |
| CN112148008B (en) | Real-time unmanned aerial vehicle path prediction method based on deep reinforcement learning | |
| CN116518960B (en) | Road network updating method, device, electronic equipment and storage medium | |
| CN114120115A (en) | Point cloud target detection method for fusing point features and grid features | |
| CN112633602B (en) | Traffic congestion index prediction method and device based on GIS map information | |
| CN115200585A (en) | Unmanned aerial vehicle track planning method and device based on airspace grid and electronic equipment | |
| CN111486847B (en) | Unmanned aerial vehicle navigation method and system | |
| CN114692357B (en) | Three-dimensional route network planning system and method based on improved cellular automaton algorithm | |
| CN114637305B (en) | Unmanned aerial vehicle shortest path planning method and device | |
| CN114419877B (en) | Vehicle track prediction data processing method and device based on road characteristics | |
| CN113447039A (en) | High-precision road shortest path calculation method based on mapping information | |
| CN114527759B (en) | End-to-end driving method based on hierarchical reinforcement learning | |
| CN114153216A (en) | Lunar surface path planning system and method based on deep reinforcement learning and block planning | |
| CN116580549A (en) | Dynamic three-dimensional traffic simulation scene collaborative operation method | |
| CN114839975A (en) | Autonomous exploration type semantic map construction method and system | |
| Zang et al. | Integrating heterogeneous sources for learned prediction of vehicular data consumption | |
| CN118366314B (en) | Urban traffic network traffic interruption prediction method | |
| CN117268403B (en) | Improved GBNN dynamic path planning method based on optimized deployment sensing technology | |
| CN117036966B (en) | Learning method, device, equipment and storage medium for point feature in map | |
| Xu et al. | Wheelbase-weighted Path Planning Algorithm in Regular Grid Digital Elevation Map | |
| Yu | The Impact of Path Planning Model Based on Improved Ant Colony Optimization Algorithm on Green Traffic Management. | |
| CN117671165B (en) | DEM data synthesis method based on graph attention network |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| PB01 | Publication | ||
| PB01 | Publication | ||
| SE01 | Entry into force of request for substantive examination | ||
| SE01 | Entry into force of request for substantive examination | ||
| GR01 | Patent grant | ||
| GR01 | Patent grant |