CN104991895A - Low-altitude rescue aircraft route planning method based on three dimensional airspace grids - Google Patents

Abstract

The invention discloses a low-altitude rescue aircraft track planning method based on a three-dimensional airspace grid, which includes: dividing the low-altitude airspace into grid nodes according to the three-dimensional terrain, aircraft performance and weather distribution, and using the improved A* algorithm to search for a single aircraft The optimal flight trajectory method; on the basis of determining the flight trajectory of a single aircraft, the time window calculation method is used to propose a multi-aircraft conflict-free trajectory planning method that exchanges time for space and space for time, and finally takes the shortest rescue time as the optimization goal. Obtain the multi-aircraft conflict-free trajectory planning scheme. The invention solves the non-conflict planning method of multi-aircraft in low-altitude complex terrain, weather distribution and aircraft performance under aviation rescue, and provides a basis for the aircraft flight plan arrangement of the aviation emergency rescue command system.

Description

A trajectory planning method for low-altitude rescue aircraft based on 3D airspace grid

Technical field:

The present invention relates to a flight scheduling technology for aviation rescue, in particular to a low-altitude rescue aircraft track planning method based on a three-dimensional airspace grid, which is suitable for optimal scheduling and flight planning of aircraft under low-altitude rescue to ensure air traffic operation Safe and efficient.

Background technique:

Among the various measures for disaster relief and emergency response, aviation rescue has the advantages of being fast, efficient, and less restricted by geographical space, and is the most effective means generally adopted by many countries in the world. However, in the aviation emergency rescue system, when the rescue aircraft operates in a low-altitude environment, due to the interference of uncertain factors such as terrain environment, bad weather, and intensive flight, there are often high safety risks, low rescue efficiency, and unreasonable implementation. And other issues. Therefore, reasonable planning of flight paths is particularly important for the safety and efficiency of low-altitude emergency rescue flights.

At present, related researches focus on UAV path planning and other aspects. The problem mainly involves environment representation, planning method, and path execution. On the basis of certain environment expression and planning methods, only from the analysis of path search strategies, the search strategies can be divided into three categories. The first type is the local optimization algorithm, which sacrifices the search space of the solution to obtain the search time of the solution. Typical methods include: steepest descent method, partial greedy algorithm (Verscheure, 2009), etc., but there are long search time and convergence The speed is slow, and it is easy to fall into the local optimal solution; the second type is the global optimization algorithm, which aims to obtain the global optimal solution. The main algorithms are: Dijkstra algorithm of single-source shortest path (Chiba, 2010), any two The Floyed dynamic programming algorithm of the shortest path between points (Sun Dawei, 2006), etc., but there will be longer calculation time and the phenomenon of dimension explosion; the last category is computer intelligence methods, including: genetic algorithm, tabu search, simulated annealing and artificial Neural networks and the idea of combining them with fuzzy logic to pursue computational results quickly and efficiently (Lingxiao, 2011; Anjan, 2010; Tang, 2011; Duygu, 2014). However, there are some problems in the application of the existing research to the trajectory planning of aviation rescue: ① most methods only solve the problem of path planning in the two-dimensional plane; ② the three-dimensional trajectory planning in UAV flight mainly uses altitude The correction method rarely considers safe flight rules, rescue rules and aircraft performance constraints; ③ most of the solutions are single aircraft trajectory planning problems, and the flight conflicts between multiple aircraft are not considered.

Invention content:

The purpose of the present invention is to provide a low-altitude rescue aircraft track planning method based on a three-dimensional airspace grid, which can effectively solve the orderly and efficient operation of low-altitude rescue aircraft under complex terrain, weather and dense flight conditions, and effectively improve the air traffic in the rescue airspace safety.

The present invention adopts the following technical scheme: a low-altitude rescue aircraft track planning method based on a three-dimensional airspace grid, which includes the following steps

Step 1, establish airspace grid division, and determine the flight environment of airspace aircraft;

Step 2, determine the single aircraft track planning of the improved A* algorithm;

Step 3, multi-aircraft conflict-free strategic trajectory planning.

Further, in the step 1, the aircraft in the airspace adopts visual flight rules.

Further, in said step 1: the airspace grid division includes as follows: the low-altitude airspace is divided into cuboid grids of the same size; the grid area is represented by the grid center point, and regular track nodes are generated; the grid size is set It is determined according to the visual flight control separation and the performance parameters of the aircraft.

Further, said step 2 includes:

Step 21, read the aircraft information, create an openlist table for it, initialize it to only include the initial node, that is, the node of the rescue point in the airspace grid; create a closelist table, initialize it to be empty; let g(1)=0, where , g(n) is the cost from the starting point (node 1) to the current node (node n), and w _m (n) is the weight function: $g\left(\mathrm{no}\right)=g(\mathrm{no}-1)+di\mathrm{the\; s}t(\mathrm{no},\mathrm{no}-1)+{\mathrm{\Σ}}_{m=1}^m{w}_m\left(\mathrm{no}\right),\mathrm{no}>1,$ The distance between two adjacent nodes is: h(n) is the heuristic distance cost, that is, the minimum Euclidean distance from the current node to the target node: $h\left(\mathrm{no}\right)=\sqrt{{(x_{goal}-x_{\mathrm{no}})}^2+{({\mathrm{the\; y}}_{goal}-{\mathrm{the\; y}}_{\mathrm{no}})}^2+{(z_{goal}-z_{\mathrm{no}})}^2},\mathrm{no}\&Greater\; Equal;1,$ f(n)=g(n)+h(n), the algorithm seeks the minimum total cost f(n) of each node each time;

Step 22, for the current aircraft, among the adjacent and reachable connected nodes, select a node n with the smallest evaluation function value f and satisfy the constraint conditions from the openlist table as the node to be expanded; delete the node n from the openlist table and loaded into the closelist table;

Step 23, if node n is the target node, stop searching and turn to step 26; otherwise, turn to step 24;

Step 24, select a node m among the nodes that are adjacent to node n and can be reached:

① If m is in the closelist and g(m) is smaller, update the g value of node m and point its parent node to n;

② If m is in the openlist and the current g(m) is small, update the value of node m and point its parent node to n;

③If m is not in the openlist and closelist, add m to the openlist, calculate its g value, and point its parent node pointer to n;

Step 25, return to execute step 22, continue searching;

Step 26, trace back from the target node to the starting point, record the passing grid nodes, and obtain the optimal track from the initial node to the target node, that is, the problem, and the algorithm terminates.

Further, said step 3 includes:

Step 31, multi-aircraft trajectory planning based on time-window principle with time-for-space;

Step 32, space-for-time multi-aircraft trajectory planning based on the A* algorithm;

Step 33, taking the minimum time of the calculation results of steps 31 and 32 as the optimization criterion, to determine the trajectory planning path.

Further, the step 31 includes:

Step 311, within a determined time range of [T ₁ ~T ₂ ], according to the improved A ^* algorithm, search for the optimal initial flight paths of n aircraft;

Step 312, select the optimal initial flight path of aircraft i with the highest mission level, and arbitrarily determine a takeoff time within the time [T ₁ ~T ₂ ] Calculate the retention time window of each node according to the flight track;

Step 313, select the optimal initial flight track of aircraft j with the second highest task level, and judge whether there is an intersection point with aircraft i, if not, according to step 312, determine the retention time window of each track node of aircraft j;

Step 314, if there is an intersection point, within the time range [T ₁ ~ T ₂ ], determine the idle time window of the intersection point of aircraft i, and calculate the idle time of the starting node of aircraft j according to the flight time between nodes on the optimal track Time window, the take-off time of aircraft j is any time within the idle time window of the starting node;

Step 315, similarly, determines the departure time of aircraft j, calculates the retention time windows of each node of aircraft j, and plans the departure times of other aircraft in turn based on the retention time windows of aircraft i and aircraft j, and finally obtains the final Optimal initial flight path remains unchanged, multi-aircraft conflict-free optimal flight path with limited take-off time.

Further, the step 32 includes:

Step 321, within a certain [T ₁ -T ₂ ] time range, according to the improved A ^* algorithm, search for the optimal initial flight paths of n aircraft;

Step 322, assuming that the departure time of each aircraft It is known that the optimal initial trajectory of the aircraft i with the highest mission level is selected, and the take-off time is given Calculate the retention time window of each node according to the flight track;

Step 323, select the optimal initial track of aircraft j with the second highest task level, and judge whether there is an intersection point with the optimal initial track of aircraft i, if not, according to step 322, determine the retention time window of each track node of aircraft j ;

Step 324, if there is an intersection point, judge in turn whether the retention time windows of the two aircraft at the intersection point overlap. If there is no overlap, the aircraft will fly according to the original plan. If there is overlap, it means that the current node is not available for aircraft j, and the attribute value of the node is given by The original 1 becomes 0, and the improved A ^* algorithm is used to search the flight track again;

Step 325, judge again whether there is an intersection between the new track and the track of the aircraft with higher priority, and repeat step 324 until it is judged that all intersection retention time windows do not overlap;

In step 326, similarly, other aircraft search for the optimal flight path sequentially according to the above-designed algorithm at the given take-off time.

The present invention has the following beneficial effects: the present invention starts from the actual needs of my country's aviation rescue field, and uses the time window and the improved A* algorithm to solve the problem that the low-altitude rescue aircraft is disturbed by uncertain factors such as terrain environment, bad weather and intensive flight. The invention can be directly applied to the aviation emergency rescue command system, effectively improving the safety and efficiency of aviation rescue.

Description of drawings:

Fig. 1 is the flow chart of the low-altitude rescue flight track planning method based on the three-dimensional airspace grid of the present invention.

Figure 2 is a grid map of the low-altitude airspace.

Figure 3 is a schematic diagram of planning space aircraft flight.

Figure 4 is a flowchart of the improved A* algorithm.

Figure 5 is the track diagram of the optimal initial flight plan for a single aircraft.

Fig. 6 is a schematic diagram of an aircraft time window model.

Fig. 7 is a comparison diagram of the time to reach the target node calculated by the two methods.

Detailed ways:

Please refer to shown in Fig. 1, the present invention is based on the low-altitude rescue aircraft track planning method of three-dimensional airspace grid, and it comprises the following steps:

Step 1, establish airspace grid division, and determine the flight environment of airspace aircraft;

Step 2, determine the single aircraft track planning of the improved A* algorithm;

Step 3, multi-aircraft conflict-free strategic trajectory planning.

Wherein step 2 includes:

Step 21, read aircraft information and create an openlist table for it. Initialize it so that it only includes the initial node, that is, the node whose rescue point is in the airspace grid; create a closelist table and initialize it to be empty; let g(1)=0. Among them, g(n) is the cost from the starting point (node 1) to the current node (node n), and w _m (n) is the weight function: $g\left(\mathrm{no}\right)=g(\mathrm{no}-1)+di\mathrm{the\; s}t(\mathrm{no},\mathrm{no}-1)+{\mathrm{\Σ}}_{m=1}^m{w}_m\left(\mathrm{no}\right),\mathrm{no}>1,$ The distance between two adjacent nodes is: h(n) is the heuristic distance cost, that is, the minimum Euclidean distance from the current node to the target node: $h\left(\mathrm{no}\right)=\sqrt{{(x_{goal}-x_{\mathrm{no}})}^2+{({\mathrm{the\; y}}_{goal}-{\mathrm{the\; y}}_{\mathrm{no}})}^2+{(z_{goal}-z_{\mathrm{no}})}^2},\mathrm{no}\&Greater\; Equal;1,$ f(n)=g(n)+h(n), the algorithm seeks the minimum total cost f(n) of each node each time;

Step 22, for the current aircraft, among the adjacent and reachable connected nodes, select a node n with the minimum evaluation function value f and satisfy the constraints (constraints such as terrain, weather, and aircraft performance) from the openlist table, as Node to be expanded; delete node n from the openlist table and load it into the closelist table.

Step 23, if node n is the target node, stop searching and turn to step 26; otherwise, turn to step 24;

Step 24, select a node m among the nodes that are adjacent to node n and can be reached (nodes that meet constraints such as terrain, weather, and aircraft performance):

① If m is in the closelist and g(m) is smaller, update the g value of node m and point its parent node to n;

② If m is in the openlist and the current g(m) is small, update the value of node m and point its parent node to n;

③If m is not in the openlist and closelist, add m to the openlist, calculate its g value, and point its parent node pointer to n;

Step 25, return to execute step 22, continue searching;

Step 26, trace back from the target node to the starting point, record the passing grid nodes, and obtain the optimal track from the initial node to the target node, that is, the problem, and the algorithm terminates.

Step 3 includes:

Step 31, multi-aircraft trajectory planning based on time-window principle with time-for-space;

Step 32, space-for-time multi-aircraft trajectory planning based on the A* algorithm;

Step 33, taking the minimum time of the calculation results of steps 31 and 32 as the optimization criterion, to determine the trajectory planning path.

Wherein step 31 comprises:

Step 311 , within a certain time range of [T ₁ -T ₂ ], according to the improved A ^* algorithm, search for the optimal initial flight paths of n aircraft respectively.

Step 312, select the optimal initial flight path of aircraft i with the highest mission level, and arbitrarily determine a takeoff time within the time [T ₁ ~T ₂ ] Calculate the retention time window of each node according to the flight track.

Step 313, select the optimal initial flight path of aircraft j with the second highest task level, and judge whether there is an intersection with aircraft i. If not, according to step 312, the retention time windows of each track node of aircraft j are determined.

Step 314, if there is an intersection point, within the time range [T ₁ ~ T ₂ ], determine the idle time window of the intersection point of aircraft i, and calculate the idle time of the starting node of aircraft j according to the flight time between nodes on the optimal track Time Window. The take-off time of aircraft j is any time within the idle time window of the starting node.

In step 315, similarly, the departure time of aircraft j is determined, and the retention time windows of each node of aircraft j are calculated. Based on the reserved time windows of aircraft i and aircraft j, the take-off times of other aircraft are planned sequentially. Finally, the optimal initial flight path is constant and the conflict-free optimal flight path of multi-aircraft with limited take-off time is obtained.

Wherein step 32 comprises:

Step 321 , within a determined time range of [T ₁ -T ₂ ], according to the improved A ^* algorithm, search for the optimal initial flight paths of n aircraft respectively.

Step 322, assuming that the departure time of each aircraft A known. Select the optimal initial track of the aircraft i with the highest mission level, given the take-off time Calculate the retention time window of each node according to the flight track.

Step 323, select the optimal initial track of aircraft j with the second highest task level, and judge whether there is an intersection point with the optimal initial track of aircraft i. If not, according to step 322, the retention time windows of each track node of aircraft j are determined.

Step 324, if there is an intersection point, it is judged sequentially whether the retention time windows of the two aircrafts at the intersection point overlap, if not, the aircraft will fly according to the original plan. If there is overlap, it means that the current node is not available for aircraft j, the attribute value of the node is changed from 1 to 0, and the improved A ^* algorithm is used to search for the flight track again.

Step 325, judge again whether there is an intersection between the new track and the track of the aircraft with a higher priority, and repeat step 324 until it is judged that all intersection retention time windows do not overlap.

In step 326, similarly, other aircraft search for the optimal flight path sequentially according to the above-designed algorithm at the given take-off time.

Combined with the actual rescue flight, the following factors need to be considered in advance:

①Aircraft: In view of the current situation of general aviation in my country and the particularity of low-altitude rescue flights, the object of this patent is light fixed-wing aircraft. Its advantages are low take-off and landing conditions, flexible maneuverability, low cost, and the ability to effectively observe, search and rescue people in distress at a relatively low speed and altitude.

②Rescue flight mission: This patent assumes that the rescue mission and task priority are known, and within a limited time frame, it is necessary to perform flight missions from multiple rescue points to multiple disaster-stricken points.

③Rescue flight environment: The flight environment of aviation emergency rescue is mostly in the low-altitude airspace with a true height of 1000m or less on undulating hills or mountainous areas. The ground communication, navigation and surveillance systems cannot effectively cover the airspace, and the controllers "cannot see or connect" to the aircraft, and do not provide control services, and the flight safety is the responsibility of the aircraft pilots themselves. Therefore, the aircraft flying in this airspace adopts visual flight rules.

④ Rescue flight rules and minimum safe separation: According to the International Civil Aviation Organization's visual flight horizontal separation standard: the longitudinal separation between aircraft on the same track and at the same height for visual flight is: IAS ≥ 250km/h, and 5km between aircraft; IAS<250km/h, 2km between aircraft. The vertical separation between visual flight aircraft and aircraft shall be carried out in accordance with the relevant provisions of the level equipment.

⑤ Airspace grid division: Divide the low-altitude airspace into cuboid grids of the same size. The grid area is represented by the grid center point, and regular track nodes are generated to overcome the defect that there is no air route in low-altitude airspace. The grid size setting is determined according to the visual flight control interval and the performance parameters of the aircraft. The divided airspace grid is shown in Figure 2.

⑥ Three-dimensional terrain and static three-dimensional meteorological factors: Terrain threats are mainly problems that may be encountered during aircraft takeoff and landing, and terrain threat factors are avoided by strictly controlling the safety obstacle clearance during takeoff, landing and flight. Meteorological threats are severe weather that may be dangerous to flight at a certain flight altitude. For simplicity, only static meteorological factors are considered. Through the weather forecast for a period of time before the flight, the bad weather area in the flight airspace can be reasonably located.

⑦Aircraft performance constraints: It is assumed that the speed remains constant under various flight states during the flight. Considering the turning radius of the aircraft and the constraints of climbing or descending, it is stipulated that each time the aircraft advances to a node, the change of the speed direction shall not exceed ±90°. When climbing or descending, meet the requirements of reaching the adjacent node of the adjacent level from the node of the current level. As shown in Figure 3: in the horizontal plane, the velocity direction of the aircraft at the current node O is 0° (along the positive direction of the X axis), and there are at most 5 nodes that the aircraft may reach in the next horizontal plane, namely point A, point B, Point C, point D, point E. In the vertical plane, the velocity direction of node O is 0° (along the positive direction of the Y axis), and the nodes that the aircraft may reach in the next vertical plane are points M, N, and T.

Three types of light fixed-wing aircraft were selected as the research objects, and their performance parameters are shown in Table 1.

Table 1 aircraft performance parameter list

The airspace selected in the embodiment is a 50km×50km×1km three-dimensional airspace, which includes the hilly terrain on the ground and the three-dimensional severe weather area in the air. According to the visual flight separation standard and the performance constraints of the aircraft, the grid division standard is set: the grid size is 5000m in length and width, and 300m in height. Nodes are used instead of meshes to form 3 layers of 100 node regions. Use the terrain or severe weather areas indicated by nodes (*). The nodes (○) represent the flyable areas that meet the visual flight rules and aircraft performance. During the programming of the algorithm, a two-dimensional matrix is used to represent the grid nodes on a height layer. The elements in the matrix correspond to the attribute values of the nodes, which are set to 0 or 1, where 1 represents the idle state and 0 represents the occupied state. Given a start node and a destination node for Aircraft 1 (Y-12), Aircraft 2 (C172R), and Aircraft 3 (Y-5). Using the improved A ^* algorithm proposed above, three optimal initial flight paths are calculated respectively, as shown in Figure 5.

It can be obtained from Fig. 5 that the three optimal initial flight paths have three intersection points {(4, 4, 2), (5, 5, 2), (5, 4, 2)}, then there may be Create flight conflicts. The following is to use the two methods proposed above to avoid flight conflicts in advance before flying, and compare the two results.

Trade time for space (method 1): aircraft keep their respective initial flight paths unchanged, and avoid conflicts by limiting takeoff time. It is assumed that the time range of each aircraft takeoff moment is T∈[0,1200]s. The task priority of the aircraft is known: m ₁ >m ₂ >m ₃ . First, aircraft 1 with the highest priority can take off at any time within a certain time range, assuming Table 2 shows the retention time windows of each track node of aircraft 1 calculated from the performance table and track node table.

Table 2 Retention time windows for each track node of aircraft 1

When calculating the flight time, the influence of factors such as wind speed, pilot's reaction time and turn establishment bank time are ignored, and the speed of the aircraft is assumed to remain constant throughout the flight. From Table 2, the retention time window of the first intersection point (4, 4, 2) between aircraft 2 and aircraft 1 is obtained as Within the determined time T∈[0,1200]s, the free time window of the intersection point (4,4,2) is Use the free time window of the intersection point to plan the take-off time of aircraft 2, and obtain the take-off time range of the initial node of aircraft 2 as Within the range of take-off times, select the take-off time of aircraft 2 as The retention time windows of each track node of aircraft 2 are shown in Table 3.

Table 3 Retention time windows for each track node of aircraft 2

From Table 3, the retention time windows of track nodes (4,4,2) and (5,4,2) are obtained as There is no conflict with the retention time window of aircraft 1. That is to say, based on the time window principle, the two aircrafts fly according to their planned take-off times, and can successfully avoid flight conflicts at the intersection point (4,4,2). at this time

${\mathrm{<span\; class="notranslate">\; r</span>}}_{<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 5</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; 5</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; 2</span>}<span\; class="notranslate">\; )</span>}^{\mathrm{<span\; class="notranslate">\; 1</span>}}<span\; class="notranslate">\; =</span><span\; class="notranslate">\; \&lsqb;</span>\mathrm{<span\; class="notranslate">\; 385</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; 491</span>}<span\; class="notranslate">\; \&rsqb;</span><span\; class="notranslate">\; ,</span>{\mathrm{<span\; class="notranslate">\; f</span>}}_{<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 5</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; 5</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; 2</span>}<span\; class="notranslate">\; )</span>}^{\mathrm{<span\; class="notranslate">\; 1</span>}}<span\; class="notranslate">\; =</span><span\; class="notranslate">\; \&lsqb;</span>\mathrm{<span\; class="notranslate">\; 0</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; 385</span>}<span\; class="notranslate">\; \&rsqb;</span><span\; class="notranslate">\; ,</span>{\mathrm{<span\; class="notranslate">\; f</span>}}_{<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 5</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; 5</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; 2</span>}<span\; class="notranslate">\; )</span>}^{\mathrm{<span\; class="notranslate">\; 2</span>}}<span\; class="notranslate">\; =</span><span\; class="notranslate">\; \&lsqb;</span>\mathrm{<span\; class="notranslate">\; 491</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; 1200</span>}<span\; class="notranslate">\; \&rsqb;</span><span\; class="notranslate">\; ,</span>{\mathrm{<span\; class="notranslate">\; f</span>}}_{<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 5</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; 4</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; 2</span>}<span\; class="notranslate">\; )</span>}^{\mathrm{<span\; class="notranslate">\; 1</span>}}<span\; class="notranslate">\; =</span><span\; class="notranslate">\; \&lsqb;</span>\mathrm{<span\; class="notranslate">\; 0</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; 465</span>}<span\; class="notranslate">\; \&rsqb;</span><span\; class="notranslate">\; ,</span>{\mathrm{<span\; class="notranslate">\; f</span>}}_{<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 5</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; 4</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; 2</span>}<span\; class="notranslate">\; )</span>}^{\mathrm{<span\; class="notranslate">\; 2</span>}}<span\; class="notranslate">\; =</span><span\; class="notranslate">\; \&lsqb;</span>\mathrm{<span\; class="notranslate">\; 545</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; 1200</span>}<span\; class="notranslate">\; \&rsqb;</span>$

Similarly, the take-off time of the aircraft 3 is planned according to the above method. Get the time range of aircraft 3 departure time make The obtained retention time windows of each node of aircraft 3 are shown in Table 4.

Table 4 Retention time windows for each track node of aircraft 3

From Table 4:

${\mathrm{<span\; class="notranslate">\; r</span>}}_{<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 5</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; 4</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; 2</span>}<span\; class="notranslate">\; )</span>}^{\mathrm{<span\; class="notranslate">\; 2</span>}}<span\; class="notranslate">\; =</span><span\; class="notranslate">\; \&lsqb;</span>\mathrm{<span\; class="notranslate">\; 545</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; 659</span>}<span\; class="notranslate">\; \&rsqb;</span><span\; class="notranslate">\; ,</span>{\mathrm{<span\; class="notranslate">\; r</span>}}_{<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 5</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; 5</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; 2</span>}<span\; class="notranslate">\; )</span>}^{\mathrm{<span\; class="notranslate">\; 2</span>}}<span\; class="notranslate">\; =</span><span\; class="notranslate">\; \&lsqb;</span>\mathrm{<span\; class="notranslate">\; 659</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; 773</span>}<span\; class="notranslate">\; \&rsqb;</span><span\; class="notranslate">\; ,</span>{\mathrm{<span\; class="notranslate">\; f</span>}}_{<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 5</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; 4</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; 2</span>}<span\; class="notranslate">\; )</span>}^{\mathrm{<span\; class="notranslate">\; 2</span>}}<span\; class="notranslate">\; =</span><span\; class="notranslate">\; \&lsqb;</span>\mathrm{<span\; class="notranslate">\; 659</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; 1200</span>}<span\; class="notranslate">\; \&rsqb;</span><span\; class="notranslate">\; ,</span>{\mathrm{<span\; class="notranslate">\; f</span>}}_{<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 5</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; 5</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; 2</span>}<span\; class="notranslate">\; )</span>}^{\mathrm{<span\; class="notranslate">\; 2</span>}}<span\; class="notranslate">\; =</span><span\; class="notranslate">\; \&lsqb;</span>\mathrm{<span\; class="notranslate">\; 491</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; 659</span>}<span\; class="notranslate">\; \&rsqb;</span><span\; class="notranslate">\; ,</span>{\mathrm{<span\; class="notranslate">\; f</span>}}_{<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 5</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; 5</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; 2</span>}<span\; class="notranslate">\; )</span>}^{\mathrm{<span\; class="notranslate">\; 3</span>}}<span\; class="notranslate">\; =</span><span\; class="notranslate">\; \&lsqb;</span>\mathrm{<span\; class="notranslate">\; 773</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; 1200</span>}<span\; class="notranslate">\; \&rsqb;</span>$

The schematic diagram of the time window model is obtained from the retention time window and idle time window of each track node of the conflict-free optimal flight track of the above three aircraft, as shown in Figure 6.

Exchange space for time (method 2): The takeoff time of the aircraft is arbitrarily selected between T∈[0,1200]s. Assume that the departure time of the aircraft is The mission priority of the aircraft remains unchanged. The retention time windows of each node of each aircraft can be obtained from the starting time and the optimal initial flight track node, and the retention time windows of the intersection points are listed here, as shown in Table 5.

Table 5 Retention time window for the intersection of the tracks of the three aircraft

Since aircraft 1 has the highest mission priority, its optimal trajectory remains unchanged. It can be obtained from Table 5 that aircraft 2 with the second highest task priority conflicts with aircraft 1 in the retention time window of the track intersection point (4, 4, 2). Therefore, using the above-mentioned improved A ^* algorithm to re-search the flight plan track of aircraft 2 is: {(1, 4, 1)-(2, 4, 1)-(3, 4, 2)-(4, 5, 2)-(5,5,2)-(6,5,2)-(7,5,2)-(8,6,2)-(9,6,2)-(10,6,1) }. The track intersection with aircraft 1 becomes (5, 5, 2). at this time No conflict with Aircraft 1. Aircraft 3 only conflicts with aircraft 1 at the trajectory intersection point (5, 5, 2), and the current node (5, 5, 2) is unavailable to aircraft 3. Therefore, the flight path of aircraft 3 also needs to be replanned. Similarly, get the new flight path {(5,1,1)-(5,2,2)-(5,3,2)-(5,4,2)-(5,5,3)- (5,6,3)-(5,7,3)-(5,8,3)-(5,9,2)-(5,10,1)}. The new trajectory does not intersect with the trajectory of aircraft 1 and aircraft 2, and will not cause flight conflicts with other aircraft.

In Method 2, the computer program for successively judging whether there is a conflict between the initial flight plan tracks is the same as Method 1, save the divided track nodes into the database, and mark 0, 1 attributes (0 means occupied, 1 indicates available). If there is a flight conflict, for the aircraft with low priority, the attribute value of the conflict node is changed from 1 to 0, and then the A ^* algorithm is used to search for a new track, and the new track still needs to be judged and prioritized Whether there is a conflict with the initial flight plan trajectory of the aircraft until there is no conflict.

Use the above two methods to carry out simulation experiments on the three aircraft respectively, and calculate the average time to reach the target node, as shown in Figure 7.

It is not difficult to find out by comparing the two methods: ① Method 2 avoids flight conflicts by changing the original optimal flight path. The new flight plan flight path will slightly increase the total flight time, but its take-off delay time is zero The time of the target node is slightly increased, but in the limited airspace, the available flight paths are limited. With the increase of flight missions, it may not be possible to find a feasible flight path to perform the flight mission; ② Method 1 avoids conflicts by delaying take-off , the aircraft still executes the flight mission according to the optimal initial flight plan trajectory of a single aircraft, and its flight time is the shortest. will increase dramatically. For this simulation validation, the results of the Approach 2 planning are recommended.

Based on the above-mentioned known rescue information, through the computer simulation program of the above two methods, six possible flight mission scheduling schemes are obtained from three rescue points, three disaster-affected points and three different types of aircraft, and their calculations are calculated respectively. The time to reach the affected point without conflict.

Table 6 The time to arrive at the disaster point calculated by the two methods under different scheduling schemes (seconds)

It can be obtained from Table 6 that the time required for the rescue flight mission to arrive at the disaster point is related to different rescue scheduling schemes, different rescue point and disaster point locations, the complexity of the rescue flight environment (available flight airspace), and the aircraft’s Flight speed and so on all matter. At the same time, the calculation results in Table 6 play a certain role in the optimization of the rescue flight scheduling scheme to a certain extent. In the emergency rescue process, time is life. From the perspective of the urgency of rescue time, in the case of ensuring that there is no conflict in the flight, the rescue flight mission of the aircraft should be arranged as far as possible so that it can avoid long waiting on the ground and at the same time shorten the flight time to ensure the safety of low-altitude rescue aircraft. Timely and efficient.

The above is only a preferred embodiment of the present invention, it should be pointed out that for those of ordinary skill in the art, some improvements can also be made without departing from the principle of the present invention, and these improvements should also be regarded as the invention. protected range.

Claims (7)

1., based on a low latitude rescue aircraft path planning method for three-dimensional spatial domain grid, it is characterized in that: comprise the steps.

Step 1, sets up spatial domain stress and strain model, determines spatial domain aircraft environment;

Step 2, determines the single aircraft trajectory planning of the A* algorithm improved;

Step 3, the conflict free strategic trajectory planning of many aircrafts.

2., as claimed in claim 1 based on the low latitude rescue aircraft path planning method of three-dimensional spatial domain grid, it is characterized in that: in described step 1, spatial domain aircraft adopts visual flight rules (VFR).

3., as claimed in claim 1 based on the low latitude rescue aircraft path planning method of three-dimensional spatial domain grid, it is characterized in that: in described step 1: spatial domain stress and strain model comprises as follows: low altitude airspace is divided into the rectangular parallelepiped grid that size is identical; This net region is represented, the flight path node of create-rule with grid element center point; The performance parameter of sizing grid basis of design visual flight control interval and aircraft is determined.

4., as claimed in claim 1 based on the low latitude rescue aircraft path planning method of three-dimensional spatial domain grid, it is characterized in that: described step 2 comprises:

Step 21, reads aircraft information, is that it creates openlist table, and initialization makes it comprise start node namely to go out to rescue node a little in the grid of spatial domain; Create closelist table, be initialized as sky; Make g (1)=0, wherein, g (n) is the cost from starting point and node 1 to present node and node n, w _mn () is weighting function: $g\left(n\right)=g(n-1)+\mathrm{dist}(n,n-1)+{\mathrm{\&Sigma;}}_{m=1}^M{w}_m\left(n\right),n>1,$ Distance between two adjacent nodes is: $\mathrm{dist}(i,j)=\sqrt{{(x_j-x_i)}^2+{(y_j-y_i)}^2+{(z_j-z_i)}^2},$ H (n) is heuristic distance costs, the minimum euclidean distance namely from present node to destination node: $h\left(n\right)=\sqrt{{(x_{\mathrm{goal}}-x_n)}^2+{(y_{\mathrm{goal}}-y_n)}^2+{(z_{\mathrm{goal}}-z_n)}^2},n\&GreaterEqual;1,$ F (n)=g (n)+h (n), algorithm seeks each node minimum total cost f (n) at every turn;

Step 22, for current aerospace device, in the node of adjacent accessibility connection, selects evaluation function value f minimum and meets a node n of constraint condition, as treating expanding node from openlist table; Node n is deleted from openlist table and is loaded in closelist table;

Step 23, if node n is destination node, stops search, turns to step 26; Otherwise, turn to step 24;

Step 24, in the node that can arrive, a node m is selected to node n adjacent node:

If 1. m is in closelist and g (m) is less, the more g value of new node m, its father node is pointed to n;

If 2. m is in openlist and current g (m) is less, the more value of new node m, its father node is pointed to n;

If 3. m is not in openlist and closelist, m is added in openlist, calculate its g value, his father's node pointer is pointed to n;

Step 25, returns and performs step 22, continues search;

Step 26, upwards traces back to starting point from destination node, write down through grid node, obtain from start node to destination node, i.e. the optimal trajectory of problem, algorithm stop.

5., as claimed in claim 1 based on the low latitude rescue aircraft path planning method of three-dimensional spatial domain grid, it is characterized in that: described step 3 comprises:

Step 31, changes space many aircrafts trajectory planning based on time window principle with the time;

Step 32, based on many aircrafts trajectory planning of trading space for time of A* algorithm;

Step 33, with the minimal time of step 31 and step 32 result of calculation for Optimality Criteria, determines trajectory planning path.

6., as claimed in claim 5 based on the low latitude rescue aircraft path planning method of three-dimensional spatial domain grid, it is characterized in that: described step 31 comprises:

Step 311, at [the T that is determined ₁~ T ₂] in time range, according to the A improved ^*algorithm, searches out the optimum initial flight flight path of n frame aircraft respectively;

Step 312, the optimum initial flight flight path of the aircraft i that the task the highest grade of choosing, at time [T ₁~ T ₂] in, determine arbitrarily a departure time the retention time window of each node is calculated according to flight track;

Step 313, chooses the optimum initial flight flight path of the secondary high aircraft j of task grade, judges whether have intersection point with aircraft i, if do not had, according to step 312, determines the retention time window of each flight path node of aircraft j;

Step 314, if there is intersection point, at time [T ₁~ T ₂] in scope, determine the free time window of aircraft i intersection point, according to the flight time between optimal trajectory node, calculate the free time window of the start node of aircraft j, the departure time of aircraft j is exactly any time in start node free time window;

Step 315, in like manner, determine the departure time of aircraft j, calculate the retention time window of each node of aircraft j, on the retention time window basis of aircraft i and aircraft j, plan the departure time of other aircraft successively, finally obtain optimum initial flight flight path constant, the optimum flight track of many aircrafts Lothrus apterus that departure time is limited.

7., as claimed in claim 5 based on the low latitude rescue aircraft path planning method of three-dimensional spatial domain grid, it is characterized in that: described step 32 comprises:

Step 321, at [the T that is determined ₁~ T ₂] in time range, according to the A improved ^*algorithm, searches out the optimum initial flight flight path of n frame aircraft respectively;

Step 322, assuming that each departure time of aircraft known, the initial flight path of optimum of the aircraft i that the task the highest grade of choosing, given departure time the retention time window of each node is calculated according to flight track;

Step 323, chooses the initial flight path of optimum of the secondary high aircraft j of task grade, judges whether optimum initial flight path has intersection point with aircraft i, if do not had, foundation step 322, determines the retention time window of each flight path node of aircraft j;

Step 324, if there is intersection point, judge whether two aircrafts have coincidence at the retention time window of intersection point successively, if do not overlapped, aircraft, according to flight in the original plan, if there is coincidence, represents that present node is just unavailable for aircraft j, the property value of node becomes 0 from original 1, reuses the A of improvement ^*algorithm search flight track;

Whether step 325, have intersection point, repeated execution of steps 324, until judge that all intersection point retention time windows do not overlap between the flight path again judging new flight path and the higher aircraft of priority;

Step 326, in like manner, given departure time, other aircraft successively searched for optimum flight track according to the algorithm designed above.