[go: up one dir, main page]
More Web Proxy on the site http://driver.im/

CN111486847B - Method and system for unmanned aerial vehicle navigation - Google Patents

Method and system for unmanned aerial vehicle navigation Download PDF

Info

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
exploration
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
Application number
CN202010359481.0A
Other languages
Chinese (zh)
Other versions
CN111486847A (en
Inventor
李玉华
王锦洋
李瑞轩
辜希武
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
Huazhong University of Science and Technology
Original Assignee
Huazhong University of Science and Technology
Priority date (The priority date 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 date listed.)
Filing date
Publication date
Application filed by Huazhong University of Science and Technology filed Critical Huazhong University of Science and Technology
Priority to CN202010359481.0A priority Critical patent/CN111486847B/en
Publication of CN111486847A publication Critical patent/CN111486847A/en
Application granted granted Critical
Publication of CN111486847B publication Critical patent/CN111486847B/en
Active legal-status Critical Current
Anticipated expiration legal-status Critical

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

本发明公开了一种无人机导航方法及系统，首先基于无人机目标飞行区域的原始时空指标数据，构建目标飞行区域环境的扩展层次图，然后通过前向探索矩阵在时间维度上批量进行前向搜索，能够实现并行探索，得到后向路径导航矩阵；最后基于后向路径导航矩阵进行后向回溯，得到最终的导航路径，本发明将复杂动态环境下的多目标优化问题，通过指标数据的融合，将最短路径问题转化为坠毁期望最小的最优路径规划，能够高效地从一个起始点向多个目标点进行最优路径的规划，提高无人飞行器导航的准确性，在满足无人飞行器导航安全性的同时，在三维动态环境中进行导航时计算效率较高。

Figure 202010359481

The invention discloses an unmanned aerial vehicle navigation method and system. First, based on the original space-time index data of the unmanned aerial vehicle target flight area, an extended hierarchical graph of the environment of the target flying area is constructed, and then the forward exploration matrix is used to perform batch processing in the time dimension. The forward search can realize parallel exploration and obtain the backward path navigation matrix; finally, based on the backward path navigation matrix, backward backtracking is performed to obtain the final navigation path. The integration of the shortest path problem into the optimal path planning with the smallest crash expectation can efficiently plan the optimal path from one starting point to multiple target points, improve the accuracy of UAV navigation, and meet the needs of unmanned aerial vehicles. In addition to the safety of aircraft navigation, the calculation efficiency is high when navigating in a three-dimensional dynamic environment.

Figure 202010359481

Description

Unmanned aerial vehicle navigation method and system
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
Figure BDA0002473038300000031
S33, forward search matrix at t moment
Figure BDA0002473038300000032
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
Figure BDA0002473038300000033
Aligned in the exploration direction and based on the passable matrix
Figure BDA0002473038300000034
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
Figure BDA0002473038300000035
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
Figure BDA0002473038300000036
In (1), the obtained path navigation matrix at the time t +1
Figure BDA0002473038300000037
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:
Figure BDA0002473038300000038
wherein, is the Hadamard product,
Figure BDA0002473038300000039
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,
Figure BDA00024730383000000310
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
Figure BDA0002473038300000091
Also X Y in size, passable matrix
Figure BDA0002473038300000092
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
Figure BDA0002473038300000093
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
Figure BDA0002473038300000094
Aligned in the exploration direction and based on the passable matrix
Figure BDA0002473038300000095
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
Figure BDA0002473038300000096
For example, the size of (a) is 4 × 4, and as shown in fig. 4, the forward search matrix at time t is used
Figure BDA0002473038300000101
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
Figure BDA0002473038300000102
And a passable matrix
Figure BDA0002473038300000103
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
Figure BDA0002473038300000104
And a passable matrix
Figure BDA0002473038300000105
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:
Figure BDA0002473038300000106
Figure BDA0002473038300000107
wherein, is the Hadamard product,
Figure BDA0002473038300000108
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,
Figure BDA0002473038300000109
the element in (1) represents the crash probability of the grid point where the element is located at the time t,
Figure BDA00024730383000001010
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,
Figure BDA00024730383000001011
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
Figure BDA00024730383000001012
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
Figure BDA00024730383000001013
In (1), the obtained path navigation matrix at the time t +1
Figure BDA00024730383000001014
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.一种无人机导航方法，其特征在于，包括以下步骤：1. an unmanned aerial vehicle navigation method, is characterized in that, comprises the following steps: S1、获取无人机目标飞行区域的原始时空指标数据，并对所得原始时空指标数据按照类别进行预处理，将指标数据超出其对应类别的预设阈值范围的栅格的通行概率设为0；其中，目标飞行区域预先被划分成多个栅格；S1. Obtain the original spatiotemporal index data of the target flight area of the UAV, and preprocess the obtained original spatiotemporal index data according to the category, and set the passing probability of the grid whose index data exceeds the preset threshold range of the corresponding category to 0; Wherein, the target flight area is divided into a plurality of grids in advance; S2、分别将各类别的指标数据输入到对应的预训练好的机器学习模型中，综合所得结果，得到目标飞行区域中各栅格的可通行概率，并根据所得各栅格的可通行概率，构建目标飞行区域环境的扩展层次图；其中，扩展层次图中的元素表示某一时刻该元素所在栅格点的坠毁概率；S2. Input the index data of each category into the corresponding pre-trained machine learning model respectively, and synthesize the obtained results to obtain the passable probability of each grid in the target flight area, and according to the obtained passable probability of each grid, Build an extended hierarchy map of the target flight area environment; wherein, the elements in the extended hierarchy map represent the crash probability of the grid point where the element is located at a certain moment; S3、初始化前向探索矩阵Me，基于所得扩展层次图，从目标飞行区域的起始栅格点开始，基于坠毁概率最小原则，将前向探索矩阵Me按照可探索方向进行移动，并沿着时间维度进行前向探索，得到后向导航矩阵Mn；S3. Initialize the forward exploration matrix Me, based on the obtained extended hierarchy map, starting from the starting grid point of the target flight area, and based on the principle of minimum crash probability, move the forward exploration matrix Me according to the explorable direction, and move along the explorable direction. Carry out forward exploration along the time dimension to obtain the backward navigation matrix M n ; S4、基于所得后向导航矩阵Mn，依次从目标栅格点列表中的各目标栅格点开始，后向回溯，直至目标飞行区域的起始栅格点被加入导航路径中，得到导航路径。S4. Based on the obtained backward navigation matrix M n , starting from each target grid point in the target grid point list in turn, and backtracking until the starting grid point of the target flight area is added to the navigation path to obtain the navigation path . 2.根据权利要求1所述的无人机导航方法，其特征在于，所述原始时空指标数据包括：依赖于空间位置的指标和依赖于时间时刻的指标；其中，依赖于空间位置的指标包括地势图和坠毁影响图；依赖于时间时刻的指标包括气象云图和能量消耗图。2. The unmanned aerial vehicle navigation method according to claim 1, wherein the original spatiotemporal index data comprises: an index dependent on a spatial position and an index dependent on a time instant; wherein, the index dependent on the spatial position includes Topographic maps and crash impact maps; time-dependent metrics include weather cloud maps and energy consumption maps. 3.根据权利要求1所述的无人机导航方法，其特征在于，所述步骤S3，包括以下步骤：3. UAV navigation method according to claim 1, is characterized in that, described step S3, comprises the following steps: S31、初始化前向探索矩阵Me，使前向探索矩阵Me的小大与目标飞行区域的大小相同，将前向探索矩阵Me中与起始栅格点位置相对应的元素初始化为0，其余元素初始化为1，并令当前时刻t＝0；S31. Initialize the forward exploration matrix Me so that the size of the forward exploration matrix Me is the same as the size of the target flight area, and initialize the element corresponding to the position of the starting grid point in the forward exploration matrix Me to 0 , the remaining elements are initialized to 1, and the current time t=0; S32、基于扩展层次图，获取t时刻的可通行矩阵
Figure FDA0003185152800000011
S32. Based on the extended hierarchical graph, obtain a passable matrix at time t
Figure FDA0003185152800000011
 S33、将t时刻的前向探索矩阵
Figure FDA0003185152800000021
按照某一可探索方向平移一个栅格，将移动后的前向探索矩阵中的空白位置填充为1，使其与可通行矩阵
Figure FDA0003185152800000022
在该探索方向上对齐，并基于可通行矩阵
Figure FDA0003185152800000023
和移动后的前向探索矩阵，计算t时刻到t+1时刻当前探索方向上所有栅格点的坠毁概率，存到暂存矩阵中，重复步骤S33直至遍历完所有可探索方向，此时暂存矩阵中存储有t时刻到t+1时刻每一个栅格点处各探索方向的坠毁概率；S33, the forward exploration matrix at time t
Figure FDA0003185152800000021
Translate a grid according to a certain explorable direction, fill the blank position in the moved forward exploration matrix with 1, and make it consistent with the traversable matrix
Figure FDA0003185152800000022
aligned in this exploration direction and based on the traversable matrix
Figure FDA0003185152800000023
and the moved forward exploration matrix, calculate the crash probability of all grid points in the current exploration direction from time t to time t+1, store it in the temporary storage matrix, repeat step S33 until all explorable directions are traversed, at this time temporarily The storage matrix stores the crash probability of each exploration direction at each grid point from time t to time t+1; S34、将暂存矩阵中t时刻到t+1时刻每一个栅格点处各探索方向上坠毁概率的最小值，存入t+1时刻的前向探索矩阵
Figure FDA0003185152800000024
中，并将暂存矩阵中t时刻到t+1时刻每一个栅格点处坠毁概率的最小值所对应的探索方向对应的存入t+1时刻的路径导航矩阵
Figure FDA0003185152800000025
中，将所得t+1时刻的路径导航矩阵
Figure FDA0003185152800000026
存入后向导航矩阵Mn；S34. Store the minimum value of the crash probability in each exploration direction at each grid point in the temporary storage matrix from time t to time t+1 into the forward exploration matrix at time t+1
Figure FDA0003185152800000024
, and store the exploration direction corresponding to the minimum value of the crash probability at each grid point in the temporary storage matrix from time t to time t+1 into the route navigation matrix at time t+1
Figure FDA0003185152800000025
, the obtained path navigation matrix at time t+1
Figure FDA0003185152800000026
Stored in the backward navigation matrix Mn; S35、令t＝t+1；S35, let t=t+1; S36、重复步骤S32-S35，直至目标栅格点列表中的所有目标栅格点全部探索过或者无人机能量耗尽，得到所述后向导航矩阵Mn。S36. Repeat steps S32-S35 until all the target grid points in the target grid point list have been explored or the UAV energy is exhausted, and the backward navigation matrix Mn is obtained. 4.根据权利要求3所述的无人机导航方法，其特征在于，t时刻到t+1时刻当前探索方向上所有栅格点的坠毁概率为：
Figure FDA0003185152800000027
Figure FDA0003185152800000028
其中，*为哈达马乘积，
Figure FDA0003185152800000029
中的元素表示t时刻从起始栅格点到该元素所在栅格点的轨迹的最低坠毁概率，
Figure FDA00031851528000000210
中的元素表示t时刻该元素所在栅格点的坠毁概率。4. UAV navigation method according to claim 3, is characterized in that, the crash probability of all grid points on the current exploration direction from time t to time t+1 is:
Figure FDA0003185152800000027
Figure FDA0003185152800000028
Among them, * is the Hadamard product,
Figure FDA0003185152800000029
The element in represents the lowest crash probability of the trajectory from the starting grid point to the grid point where the element is located at time t,
Figure FDA00031851528000000210
The element in represents the crash probability of the grid point where the element is located at time t. 5.根据权利要求3所述的无人机导航方法，其特征在于，所述后向导航矩阵Mn为三维矩阵，其大小为X×Y×Tn，其中，X和Y分别为所述后向导航矩阵Mn的行数和列数，Tn为所述步骤S3的终止时刻。5. The unmanned aerial vehicle navigation method according to claim 3, wherein the backward navigation matrix M n is a three-dimensional matrix, and its size is X×Y×T n , wherein X and Y are the The number of rows and columns of the backward navigation matrix Mn , and Tn is the termination time of the step S3. 6.根据权利要求3所述的无人机导航方法，其特征在于，使用GPU执行所述步骤S3中的矩阵操作。6. The UAV navigation method according to claim 3, wherein the matrix operation in the step S3 is performed by using a GPU. 7.根据权利要求1所述的无人机导航方法，其特征在于，包括以下步骤：7. UAV navigation method according to claim 1, is characterized in that, comprises the following steps: S41、根据所得后向导航矩阵Mn，对目标栅格点列表中的某一个目标栅格点，找到探索到该栅格点的最末时刻；S41, according to the obtained backward navigation matrix M n , for a certain target grid point in the target grid point list, find the last moment when the grid point is explored; S42、从栅格点的最末时刻所在的位置开始，基于后向导航矩阵Mn向后进行回溯，找到该栅格点前一时刻所在的位置，加入该目标栅格点的最优路径中；S42, starting from the position of the last moment of the grid point, backtracking based on the backward navigation matrix M n , to find the position of the grid point at the previous moment, and adding it to the optimal path of the target grid point ; S43、令栅格点的最末时刻所在的位置为该栅格点前一时刻所在的位置；S43, let the position of the last moment of the grid point be the position of the previous moment of the grid point; S44、重复步骤S42-S43，直至访问到起始栅格点，此时，从目标飞行区域的起始栅格点到一个目标栅格点的最优路径构建完成；S44, repeating steps S42-S43 until the starting grid point is accessed, at this time, the construction of the optimal path from the starting grid point of the target flight area to a target grid point is completed; S43、重复步骤S41-S44，直至目标栅格点列表中的目标栅格点全部遍历完毕，得到导航路径。S43. Steps S41-S44 are repeated until all the target grid points in the target grid point list are traversed, and a navigation path is obtained. 8.根据权利要求1-7任意一项所述的无人机导航方法，其特征在于，还适用于除无人机之外的无人载具的导航。8. The unmanned aerial vehicle navigation method according to any one of claims 1-7, characterized in that, it is also applicable to the navigation of unmanned vehicles other than unmanned aerial vehicles. 9.一种无人机导航系统，其特征在于，包括：环境数据获取模块、环境信息处理模块、前向路径探索模块和轨迹回溯重建模块；9. An unmanned aerial vehicle navigation system, comprising: an environmental data acquisition module, an environmental information processing module, a forward path exploration module and a trajectory backtracking reconstruction module; 所述环境数据获取模块用于获取无人机目标飞行区域的原始时空指标数据，并输出到环境信息处理模块中；其中，目标飞行区域预先被划分成多个栅格；The environmental data acquisition module is used to acquire the original spatiotemporal index data of the target flight area of the UAV, and output it to the environmental information processing module; wherein, the target flight area is pre-divided into a plurality of grids; 所述环境信息处理模块用于将环境数据获取模块输入到原始时空指标数据按照类别进行预处理，将指标数据超出其对应类别的预设阈值范围的栅格的通行概率设为0；分别将各类别的指标数据输入到对应的预训练好的机器学习模型中，综合所得结果，得到目标飞行区域中各栅格的可通行概率，并根据所得各栅格的可通行概率，构建目标飞行区域环境的扩展层次图，并输出到前向路径探索模块中；其中，扩展层次图中的元素表示某一时刻该元素所在栅格点的坠毁概率；The environmental information processing module is used to input the environmental data acquisition module into the original spatiotemporal index data for preprocessing according to the category, and set the passing probability of the grid whose index data exceeds the preset threshold range of its corresponding category as 0; The index data of the category is input into the corresponding pre-trained machine learning model, and the obtained results are synthesized to obtain the passable probability of each grid in the target flight area, and according to the obtained passable probability of each grid, the target flight area environment is constructed. The extended hierarchical graph of , and output to the forward path exploration module; wherein, the element in the extended hierarchical graph represents the crash probability of the grid point where the element is located at a certain moment; 所述前向路径探索模块用于初始化前向探索矩阵Me，基于所得扩展层次图，从目标飞行区域的起始栅格点开始，基于坠毁概率最小原则，将前向探索矩阵Me按照可探索方向进行移动，并沿着时间维度进行前向探索，得到后向导航矩阵Mn，并输出到轨迹回溯重建模块中；The forward path exploration module is used to initialize the forward exploration matrix Me , and based on the obtained expanded hierarchical graph, starting from the starting grid point of the target flight area, and based on the principle of minimum crash probability, the forward exploration matrix Me is determined according to the available values. Move in the exploration direction, and carry out forward exploration along the time dimension, obtain the backward navigation matrix M n , and output it to the trajectory backtracking reconstruction module; 所述轨迹回溯重建模块用于基于前向路径探索模块输入到后向导航矩阵Mn，依次从目标栅格点列表中的各目标栅格点开始，后向回溯，直至目标飞行区域的起始栅格点被加入导航路径中，得到导航路径。The trajectory backtracking and reconstruction module is used to input into the backward navigation matrix Mn based on the forward path exploration module, starting from each target grid point in the target grid point list in turn, and backtracking until the start of the target flight area The grid points are added to the navigation path to get the navigation path.
CN202010359481.0A 2020-04-29 2020-04-29 Method and system for unmanned aerial vehicle navigation Active CN111486847B (en)

Priority Applications (1)

Application Number Priority Date Filing Date Title
CN202010359481.0A CN111486847B (en) 2020-04-29 2020-04-29 Method and system for unmanned aerial vehicle navigation

Applications Claiming Priority (1)

Application Number Priority Date Filing Date Title
CN202010359481.0A CN111486847B (en) 2020-04-29 2020-04-29 Method and system for unmanned aerial vehicle navigation

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 Method and system for unmanned aerial vehicle navigation

Country Status (1)

Country Link
CN (1) CN111486847B (en)

Families Citing this family (1)

* Cited by examiner, † Cited by third party
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)

* Cited by examiner, † Cited by third party
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 中国人民解放军国防科技大学 A real-time path planning method for unmanned aerial vehicles based on deep reinforcement learning
CN110672088B (en) * 2019-09-09 2021-03-30 北京航空航天大学 A UAV autonomous navigation method imitating the homing mechanism of carrier pigeon landform perception
CN110849350A (en) * 2019-10-30 2020-02-28 西北工业大学 A Construction Method of 3D Track Planning Space

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
CN111061277B (en) Unmanned vehicle global path planning method and device
CN113776534B (en) Unmanned aerial vehicle three-dimensional time-varying airspace navigation method based on three-dimensional subdivision grid
CN114384920A (en) A dynamic obstacle avoidance method based on real-time construction of local grid map
CN112633602B (en) Traffic congestion index prediction method and device based on GIS map information
CN110530371B (en) An indoor map matching method based on deep reinforcement learning
CN103901891A (en) Dynamic particle tree SLAM algorithm based on hierarchical structure
CN114120115A (en) A point cloud target detection method that fuses point features and grid features
CN106780739A (en) A kind of intelligent substation patrol three-dimension GIS system method for building up
CN115099328A (en) Traffic flow prediction method, system, device and storage medium based on countermeasure network
Lu et al. A beamlet-based graph structure for path planning using multiscale information
CN111486847B (en) Method and system for unmanned aerial vehicle navigation
Yang et al. Feature selection in conditional random fields for map matching of GPS trajectories
CN117078870A (en) Road environment three-dimensional reconstruction method integrating high-precision map and laser sparse point cloud
CN113447039B (en) High-precision road shortest path calculation method based on mapping information
CN114419877A (en) Vehicle track prediction data processing method and device based on road characteristics
Rivière et al. H-TD 2: Hybrid temporal difference learning for adaptive urban taxi dispatch
Hu et al. Pc-nerf: parent-child neural radiance fields under partial sensor data loss in autonomous driving environments
CN118038073A (en) Multi-head attention mechanism-based enhanced visual angle transformation method
Zang et al. Integrating heterogeneous sources for learned prediction of vehicular data consumption
CN114153216A (en) Lunar surface path planning system and method based on deep reinforcement learning and block planning
CN116400682A (en) An Unmanned Ship Trajectory Planning Method Based on Sampling Optimization
Tao et al. Application research on dynamic obstacle avoidance path planning of unmanned vehicle in uncertain environment
Xu et al. Wheelbase-weighted Path Planning Algorithm in Regular Grid Digital Elevation Map
US12229987B2 (en) Simultaneous localization and mapping (SLAM) method

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