CN-121979244-A - Unmanned aerial vehicle space-time path planning method, device, equipment and medium

CN121979244ACN 121979244 ACN121979244 ACN 121979244ACN-121979244-A

Abstract

The application discloses a space-time path planning method, device, equipment and medium for an unmanned aerial vehicle, and relates to the field of unmanned aerial vehicle path planning. The method comprises the steps of constructing a three-dimensional space grid map of an unmanned aerial vehicle task environment, marking static obstacle information and dynamic obstacle information in the three-dimensional space grid map, and carrying out multiple iterations by adopting a neighboring node generation mechanism, a collision detection mechanism, a safety interval detection mechanism and a step-variable mechanism based on heuristic costs of the three-dimensional space grid map and an unmanned aerial vehicle starting point to obtain a path planning result of the unmanned aerial vehicle. The application can realize efficient and feasible path planning in complex or dynamically-changing environments and remarkably improve the calculation efficiency.

Inventors

ZHOU YAOMING
CHENG JIANHUA
XU LIWEN
GAO HUI

Assignees

北京航空航天大学

Dates

Publication Date: 20260505
Application Date: 20260130

Claims (10)

1. The unmanned aerial vehicle space-time path planning method is characterized by comprising the following steps of: Constructing a three-dimensional space grid map of the unmanned aerial vehicle task environment, wherein static obstacle information and dynamic obstacle information are marked in the three-dimensional space grid map; Based on the three-dimensional space grid map and heuristic cost of the starting point of the unmanned aerial vehicle, performing multiple iterations by adopting a neighbor node generating mechanism, a collision detecting mechanism, a safety interval detecting mechanism and a step-variable mechanism to obtain a path planning result of the unmanned aerial vehicle; wherein for the current iteration, it comprises: selecting a node with the minimum heuristic cost from the OPEN table under the current iteration times as a current node, and judging whether the current node is an end point or not and whether the time stamp is in a legal safe time interval or not to obtain a first judgment result; If the first judgment result is yes, outputting a path planning result of the unmanned aerial vehicle; if the first judgment result is negative, for the current node, generating a neighboring node set conforming to the performance constraint of the unmanned aerial vehicle based on the current step length by adopting a neighboring node generation mechanism, and judging each node in the neighboring node set by adopting a collision detection mechanism and a safety interval detection mechanism to obtain a second judgment result; If the second judging result is that the node collides or the time conflicts, discarding the node; if the second judging result is that the node does not collide and no time conflict exists, determining that the node passes detection, and adding the node into an OPEN table; If the number of the nodes passing through the detection in the adjacent node set is smaller than or equal to the variable step threshold, the current node is moved out of the OPEN table and added into the ReOPEN table under the current iteration number, and an updated OPEN table and an updated ReOPEN table are obtained; Judging whether the updated OPEN table is empty or not, and obtaining a third judging result; if the third judging result is not null, taking the updated OPEN table and the updated ReOPEN table as the OPEN table and the ReOPEN table under the next iteration number, and carrying out the next iteration; If the third judging result is null, generating a variable-step-length neighbor node set by adopting a variable-step-length mechanism based on the current step length and the updated ReOPEN table, and re-adding the updated OPEN table by adopting the variable-step-length neighbor node set to obtain a re-added OPEN table, and taking the re-added OPEN table and the updated ReOPEN table as the OPEN table and the ReOPEN table under the next iteration times to carry out the next iteration.
2. The unmanned aerial vehicle space-time path planning method of claim 1, wherein generating a variable-step neighboring node set by using a variable-step mechanism based on a current step and the updated ReOPEN table, and re-adding the updated OPEN table by using the variable-step neighboring node set to obtain the re-added OPEN table, specifically comprising: determining a current update step length according to the current step length and a set decremental step length; generating a variable-step adjacent node set by adopting an adjacent node generating mechanism based on the current updating step length for each node in the updated ReOPEN table, and judging each node in the variable-step adjacent node set by adopting a collision detection mechanism and a safety interval detection mechanism to obtain a fourth judging result; If the fourth judgment result is that the node does not collide, no time conflict exists, and no repeated direction exists in the node, the node is added into the updated OPEN table, otherwise, the node is abandoned; Judging whether the current update step length is smaller than a set minimum step length, if so, obtaining a rejoined OPEN table, if not, continuing to reduce the current update step length according to the set decremental step length, and regenerating a variable step length adjacent node set until the current update step length is smaller than the set minimum step length.
3. The unmanned aerial vehicle space-time path planning method of claim 1, wherein generating a set of neighboring nodes that meet unmanned aerial vehicle performance constraints based on a current step size using a neighboring node generation mechanism, comprises: Generating a neighboring node set conforming to the performance constraint of the unmanned aerial vehicle by adopting a node generating function based on the current step length, wherein the expression of the node generating function is as follows: ; Wherein, the , As the spatial location of the current node, 、 And The values of the current node on three coordinate axes are respectively; Is the current step length; for the current node in the current step length and the action direction set And then, generating all the generated adjacent node sets which can meet the flight constraint, Is the number of actions; Is a node in the set of neighboring nodes; 、 And According to the first Individual actions And the spatial displacement on three coordinate axes generated by the current step calculation, ; Is the current timestamp; Is the first Individual actions The time increment generated at the current step size.
4. The unmanned aerial vehicle space-time path planning method of claim 1, wherein each node in the set of neighboring nodes is determined by a collision detection mechanism and a safety interval detection mechanism, and specifically comprising: And judging whether each node in the adjacent node set collides with an obstacle in the environment by adopting a collision detection function, and judging whether each node in the adjacent node set collides with the obstacle in time by adopting the collision detection function.
5. The unmanned aerial vehicle space-time path planning method of claim 4, wherein the collision detection function has an expression of: ; Wherein, the Representing the first of a set of neighboring nodes Spatial locations of individual nodes; representing a three-dimensional space grid map; Representing static or dynamic obstacles in the three-dimensional space grid map; Representing the first of a set of neighboring nodes Whether each node collides, if so Representing the first node in the adjacent node set The individual nodes being spatially collided with the obstacle, if so Representing the first node in the adjacent node set The individual nodes are spatially non-collided with obstacles.
6. The unmanned aerial vehicle space-time path planning method of claim 4, wherein the collision detection function has an expression of: ; Wherein, the Representing the first of a set of neighboring nodes Spatial locations of individual nodes; representing a three-dimensional space grid map; Representing static or dynamic obstacles in the three-dimensional space grid map; Representing the first of a set of neighboring nodes A timestamp of the individual node; Representing the first of a set of neighboring nodes Whether each node generates time conflict or not, if so Representing the first node in the adjacent node set The individual nodes do not meet the safety time requirement on the time axis, time conflict exists, and if the result is that Representing the first node in the adjacent node set The individual nodes meet the safety time requirement on the time axis, and no time conflict exists.
7. The unmanned aerial vehicle space-time path planning method of claim 1, wherein before selecting a node with the smallest heuristic cost from the OPEN table under the current iteration number as the current node, the unmanned aerial vehicle space-time path planning method further comprises: judging whether the OPEN table and the ReOPEN table under the current iteration are empty or not to obtain a fifth judgment result; And if the fifth judgment result is negative, executing the step of selecting the node with the minimum heuristic cost from the OPEN table under the current iteration times as the current node.
8. Unmanned aerial vehicle space-time path planning device, its characterized in that, unmanned aerial vehicle space-time path planning device includes: The system comprises a grid map construction module, a control module and a control module, wherein the grid map construction module is used for constructing a three-dimensional space grid map of an unmanned aerial vehicle task environment, and static obstacle information and dynamic obstacle information are marked in the three-dimensional space grid map; the path planning module is used for carrying out multiple iterations by adopting a neighboring node generation mechanism, a collision detection mechanism, a safety interval detection mechanism and a variable step length mechanism based on the three-dimensional space grid map and heuristic cost of the starting point of the unmanned aerial vehicle to obtain a path planning result of the unmanned aerial vehicle; wherein for the current iteration, it comprises: selecting a node with the minimum heuristic cost from the OPEN table under the current iteration times as a current node, and judging whether the current node is an end point or not and whether the time stamp is in a legal safe time interval or not to obtain a first judgment result; If the first judgment result is yes, outputting a path planning result of the unmanned aerial vehicle; if the first judgment result is negative, for the current node, generating a neighboring node set conforming to the performance constraint of the unmanned aerial vehicle based on the current step length by adopting a neighboring node generation mechanism, and judging each node in the neighboring node set by adopting a collision detection mechanism and a safety interval detection mechanism to obtain a second judgment result; If the second judging result is that the node collides or the time conflicts, discarding the node; if the second judging result is that the node does not collide and no time conflict exists, determining that the node passes detection, and adding the node into an OPEN table; If the number of the nodes passing through the detection in the adjacent node set is smaller than or equal to the variable step threshold, the current node is moved out of the OPEN table and added into the ReOPEN table under the current iteration number, and an updated OPEN table and an updated ReOPEN table are obtained; Judging whether the updated OPEN table is empty or not, and obtaining a third judging result; if the third judging result is not null, taking the updated OPEN table and the updated ReOPEN table as the OPEN table and the ReOPEN table under the next iteration number, and carrying out the next iteration; If the third judging result is null, generating a variable-step-length neighbor node set by adopting a variable-step-length mechanism based on the current step length and the updated ReOPEN table, and re-adding the updated OPEN table by adopting the variable-step-length neighbor node set to obtain a re-added OPEN table, and taking the re-added OPEN table and the updated ReOPEN table as the OPEN table and the ReOPEN table under the next iteration times to carry out the next iteration.
9. A computer device comprising a memory, a processor and a computer program stored on the memory and capable of running on the processor, characterized in that the processor executes the computer program to implement the unmanned aerial vehicle space-time path planning method of any of claims 1-7.
10. A computer readable storage medium having stored thereon a computer program, which when executed by a processor implements the unmanned aerial vehicle space-time path planning method of any of claims 1-7.

Description

Unmanned aerial vehicle space-time path planning method, device, equipment and medium Technical Field The present application relates to the field of unmanned aerial vehicle path planning, and in particular, to a method, apparatus, device, and medium for unmanned aerial vehicle space-time path planning. Background Along with the wide application of unmanned aerial vehicle technology, fixed wing unmanned aerial vehicle is widely applied to task scenes such as inspection, mapping, monitoring, agricultural spraying and the like because of advantages such as remote range, high flight efficiency and the like. Compared with a multi-rotor unmanned aerial vehicle, the fixed-wing unmanned aerial vehicle has higher flying speed and longer duration, but has structural constraints of poor maneuverability, limited minimum turning radius, incapability of hovering and the like. Therefore, when performing tasks, higher demands are placed on the efficiency, safety and feasibility of their path planning. Algorithms are widely used in path planning because of their superior certainty and efficiency. The method has the core advantages that the path can be quickly found with smaller calculation cost on the premise of ensuring global optimum by combining the heuristic function with the actual cost. This results inThe algorithm is particularly suitable for path searching in a static environment, unnecessary path expansion can be effectively avoided, and the searching efficiency is greatly improved. However, when a problem introduces a time dimension or dynamic environment,The superiority of the algorithm is limited because it is mainly focused on spatial path searching, failing to adequately account for time constraints and dynamic changes. In summary, the problems of poor dynamic environment adaptability, low calculation efficiency and the like exist in unmanned plane path planning at present. Disclosure of Invention The application aims to provide a space-time path planning method, device, equipment and medium for an unmanned aerial vehicle, which can realize efficient and feasible path planning in a complex or dynamically-changing environment and remarkably improve the calculation efficiency. In order to achieve the above object, the present application provides the following solutions: In a first aspect, the present application provides a method for planning a space-time path of an unmanned aerial vehicle, including: Constructing a three-dimensional space grid map of the unmanned aerial vehicle task environment, wherein static obstacle information and dynamic obstacle information are marked in the three-dimensional space grid map; Based on the three-dimensional space grid map and heuristic cost of the starting point of the unmanned aerial vehicle, performing multiple iterations by adopting a neighbor node generating mechanism, a collision detecting mechanism, a safety interval detecting mechanism and a step-variable mechanism to obtain a path planning result of the unmanned aerial vehicle; wherein for the current iteration, it comprises: selecting a node with the minimum heuristic cost from the OPEN table under the current iteration times as a current node, and judging whether the current node is an end point or not and whether the time stamp is in a legal safe time interval or not to obtain a first judgment result; If the first judgment result is yes, outputting a path planning result of the unmanned aerial vehicle; if the first judgment result is negative, for the current node, generating a neighboring node set conforming to the performance constraint of the unmanned aerial vehicle based on the current step length by adopting a neighboring node generation mechanism, and judging each node in the neighboring node set by adopting a collision detection mechanism and a safety interval detection mechanism to obtain a second judgment result; If the second judging result is that the node collides or the time conflicts, discarding the node; if the second judging result is that the node does not collide and no time conflict exists, determining that the node passes detection, and adding the node into an OPEN table; If the number of the nodes passing through the detection in the adjacent node set is smaller than or equal to the variable step threshold, the current node is moved out of the OPEN table and added into the ReOPEN table under the current iteration number, and an updated OPEN table and an updated ReOPEN table are obtained; Judging whether the updated OPEN table is empty or not, and obtaining a third judging result; if the third judging result is not null, taking the updated OPEN table and the updated ReOPEN table as the OPEN table and the ReOPEN table under the next iteration number, and carrying out the next iteration; If the third judging result is null, generating a variable-step-length neighbor node set by adopting a variable-step-length mechanism based on the current step length and the updated ReOPEN table, and re-addin