# Cooperative Route Planning for Multiple Aircraft in a Semifree ATC System

Authors: Yi Yang; Ying Nan; Ming Tong
Journal: Mathematical Problems in Engineering
 (2018)

---

## Abstract

This paper presents the Semifree Flight theory used in a civil air traffic control (ATC) system to improve the capability of the traditional Free Flight mode. The progressiveness and hidden defects of the “Free Flight” model in civil aviation are analysed, and the Semifree Flight ATC system mode is introduced. Moreover, this paper presents the collaborative route planning method, which is the most important method used in the Semifree Flight ATC system. This collaborative route planning method can plan routes for each aircraft (either in flight or just before achieving flight) in real time, and the routes can satisfy all the safety constraints. The final numerical simulations verify the correctness and practicability of the Semifree Flight theory and the collaborative route planning method.


---

## Body

## 1. Introduction

Over time, the air traffic control system has adapted to new social demands. The idea of “Free Flight” was proposed in the last century to address the rapid increase of civil aviation flow. Since then, an increasing number of people choose to travel by air, with long-distance travel becoming more frequent. Because experts thought the traditional air traffic control system was unable to meet the future air traffic demand, Free Flight was implemented according to the actual demand.Limited by outdated facilities and communication technology, it is difficult to apply Free Flight in the present ATC system. Currently, research on the present air traffic control system [1–3] mainly focuses on the management method, which on the one hand aims to increase the flow [1] and on the other hand aims to improve safety [2, 3]. From the above-referenced papers, the routes of aircraft managed by the present ATC system are mainly from point to point. In this mode, flight flow is finite and difficult to increase.To address the issues of the present ATC, the concept of “Free Flight” is proposed and extended. Free flight is considered as the most probable future ATC system mode because it provides the following functions that the present ATC system cannot provide.(a)
Each aircraft can choose its take-off and landing position freely.(b)
Each aircraft can plan its route freely with minimum flight time.(c)
The aircraft in flight can avoid collisions by using the conflict resolution guidance law.Moreover, the difficulties of implementing “Free Flight” are caused by not only the outdated facilities and system but also the supervisory mode. The theoretical issues that make Free Flight difficult to implement in the ATC system are described as follows.First, aviation administration is not able to manage all in-flight aircraft effectively in “Free Flight” mode. Because each aircraft can decide its flight route freely in this mode, the ATC system might fail to receive the flight information of each aircraft in real time, making it difficult to stop and supervise illegal flights.Second, the flight information of each aircraft cannot be transmitted to the ATC system in real time, making it difficult to control the aircraft in real time. As a result, the Free Flight mode is an ideal mode that is difficult to control.Third, in Free Flight mode, each pilot will select a route independently, resulting in conflicting flight routes. The conflict resolution strategy may result in a new conflict.In this situation, to avoid the drawbacks of “Free Flight,” this paper presents a proposed concept of “Semifree Flight” (SFF). Semifree Flight is a mode of air traffic control used to realize the function of “Free Flight” while providing security of airspaces and communication with each aircraft. To some extent, SFF can be considered as a transition stage of Free Flight.Unlike Free Flight, the SFF ATC system must receive information from all aircraft and then produce an overall plan of routes for the aircraft. Thus, route planning for multiple aircraft is the most important and an indispensable part of SFF.Route planning was proved to be an NP problem by Canny in 1988 [4]; since then, route planning has been widely used in a number of diverse applications, including intelligent transportation systems, space applications, autonomous robotics, and military guidance and navigation systems [5, 6]. During the past few decades, extensive efforts have been devoted to route planning for flight vehicles. For the purpose of accelerating the planning process, several planning methods and optimization algorithms have been developed.Graph-Based Algorithms. The Voronoi diagram method is the most widely used method to solve the path planning problem. In the research studies of [7, 8], the threat regions are modelled as points, and these point threats are used to generate the Voronoi diagram. However, the Voronoi diagram method usually fails to cope with constraints. Another commonly used method is the probabilistic roadmap, which uses a digitized grid consisting of square cells of equal size to represent the environment in which the route planning is performed [6, 9].Swarm Intelligence Algorithms. Many swarm intelligence algorithms have been developed for solving the route planning problem, including the genetic algorithm (GA) [10], evolutionary programming (EP) [11, 12], the Particle Swarm Optimization Algorithm (PSO) [13], and ant colony optimization (AOC) [14, 15]. These algorithms are highly robust and flexible and can be used to solve different types of optimization problems; however, the computation speed limits its application in route planning for multiple aircraft.Heuristic Search Algorithms. A∗ is one of the best heuristic search algorithms used to find the least-cost path from a given initial node to one goal node; the algorithm was first described by Hart et al. [14]. Stentz [15] first introduced the D∗ search algorithm. However, as the problem space becomes larger, the time spent searching for the optimal or near-optimal path increases exponentially, for either A∗ or D∗ algorithm.In this paper, a collaborative dynamic programming (CDP) algorithm is proposed to solve the route planning problem for multiple aircraft based on the dynamic grid.This method can realize the route planning function for multiple aircraft while preventing flight conflicts. Further, this method provides the function of route replanning; that is, when one aircraft decides to change its destination, the SFF ATC system can replan its routes in real time while ensuring the new route does not influence the routes of other aircraft. The numerical simulation results confirm the practicability and correctness of the route planning method.


## 2. SFF ATC System Description

In this section, the Semifree Flight (SFF) ATC system is introduced to solve the command and control problem for multiple aircraft in flight or preparing to take off. The SFF ATC system works to maintain the stability and safety of all aircraft flying in its control area. The SFF ATC system provides communication and route support for each aircraft while supervising the entire flight net to ensure its normal operation.The regular work procedure of the SFF ATC system begins with receiving flight requests from the aircraft under its control and then calculating the optimal flight plans in the inner system. Next, the SFF ATC system sends the flight plans to each aircraft. In addition, the system provides updated flight plans at several minutes’ interval.A description of the work mode of the SFF ATC system is shown in Figure1. The system has four interfaces to provide external communication.Figure 1
Work mode of the SFF ATC system.(1  ) Interface to Aircraft about to Take Off. The SFF ATC system receives the flight requests from aircraft about to take off and then sends a reply to each aircraft with a flight plan. Each flight request includes the estimated time, the locations of the take-off and landing, and the information of the aircraft itself.Next, the aircraft should provide the system with feedback on whether it will comply with this flight plan or not.(2  ) Interface to Aircraft in Air. During the process of flight, an aircraft must send its own information in a flight report to the SFF ATC system. In this manner, the system can obtain the flight state of every single aircraft to supervise each flight while regulating and controlling the flight routes of all aircraft. After receiving the flight reports from the aircraft, the system will return the planned flight route to each aircraft based on the actual situation.The flight report includes the following information:(a)
Current aircraft position and other flight status (e.g., remaining fuel)(b)
Decision whether to alter destination or not: if yes, then new destination coordinates are used.Moreover, the flight route returned by the system can be divided into two cases:(a)
Unchanged: the aircraft follows the original route until it receives the next flight route order.(b)
Changed: the aircraft receives a new flight route and follows this new route until it receives the next flight route order.(3  ) Interface to the Commander Window. The commander can transmit instructions to the SFF ATC system in commander window and observe the flight status and the planned route for each aircraft.The instructions transmitted by the commander include the following: change the aircraft’s rank; disable some airports; force some aircraft to end their flights.(4  ) Interface to Environmental Effectors. This interface will import the outside environmental factors of influence into the SFF ATC system, including wind field, temperature, and atmospheric pressure. This information will be used in the route planning module.In the work mode shown in Figure1, the requirements of both facilitation and supervision can be achieved by the SFF ATC system. For a pilot, the work that must be done is to import the positions of the take-off and landing locations. In the SFF ATC system, the most important part is the route planning module. A highly efficient route planning method allows the SFF ATC system to operate in real time; this method is the chief part of this paper.


## 3. Route Planning Problem Statement

### 3.1. Route Planning Problem Requirements

The route planning problem is an inevitable problem in a traditional ATC system; thus, the route planning method determines the efficiency of the ATC system. The approach of “Free Flight” is to leave out the route planning process, allowing each aircraft to plan a route itself. Generally, the route of an aircraft is a straight line between the take-off position and the landing destination. Unfortunately, Free Flight will also cause some problems, including aircraft conflict and a lack of supervision.In Semifree Flight, aircraft are not authorized to plan routes themselves; therefore, route planning is a critical module in the SFF ATC system. Route planning in the SFF ATC system is an optimization problem of multiple aircraft with multiple constraints.The imported data of the route planning module includes the flight request and the flight report from each aircraft at the current time. The information in each flight request includes the flight levels, the take-off position, the desired take-off time, the landing position, and the aircraft minimum turn radius; the information in the flight report includes the flight status in real time, such as the 3D coordinates, the velocity vector, and the remaining flight time. Moreover, the decision regarding whether to change the destination or not should also be reported.The route planning module sorts the flights along with their information and provides a flight plan list, as shown in Table1.Table 1
Flight plan list.
Flight number Flight level Take-off position Take-off time Landing position A 1 Civil (or C) φ T , ϕ T 1 11:50:06 φ L , ϕ L 1 … … … … … A i Civil (or C) φ T , ϕ T i 19:14:46 φ L , ϕ L iThe SFF ATC system will return the planned routes to the corresponding aircraft; each aircraft only needs to track its own route until it arrives at its destination or receives a new order. The planned route should consider 3 factors: performance index, flight constraints, and environment interferences.The performance index of route planning consists of 2 parts: flight time and flight path. The aim of collaborative route planning is to minimize the sum of the flight times and the sum of the paths of all aircraft.The flight constraints consist of 3 different variables: distance constraint between two aircraft, no-fly zone constraint, and minimum turning radius constraint. The distance constraint is posed as (1), which requires the distance between any two aircraft to be less than a safe distance.(1)pix,y,z,t-pjx,y,z,ti,j≤dsafe.The no-fly zone constraint restricts aircraft from entering no-fly zones; the decision method is described in Section 3.2. The minimum turning radius constraint is related to the grid generation, as described in Section 3.2.Environmental interferences have a certain influence on the flight routes of the aircraft, among which the greatest factor is the wind field. In the flight process, a flight with tailwind will have a somewhat reduced flight time.


### 3.2. Mathematical Description of the Route Planning Problem

Considering the actual problem and requirements, the route planning problem can be described by a mathematical model.Supposing the route planning module receivesN aircraft flight requests, the take-off windows are φT,ϕT,tTi, i=1,2,…,N, which can be transferred to xT,yTi in the launching coordinate system as well. The landing position of the ith aircraft is φL,ϕLi,i=1,2,…,N, which can also be transferred to φT,ϕTi in the launching coordinate system. Optimize the 4D route of each aircraft pi(t), including xt,yt,zti in the launching coordinate system, to minimize the performance index, as given in (2)min⁡Jx,y,h,t=∑ai=1ai=Nωaik1∫t0tfΔdΔtdt+k2tf,Δd=limxi+1→xi⁡xi+1-xi2+yi+1-yi2+zi+1-zi2,where ωai is the weight coefficient of the ith aircraft route; k1 and k2 are coefficients of the flight distance and the flight time, respectively.The path of theith aircraft pi(t) must satisfy the following constraints.(1  ) Safe Distance Constraint (3) x i t i - x j t j 2 + y i t i - y j t j 2 + z i t i - z j t j 2 ≥ d s a f e i + d s a f e j ,  j = 1,2 , … , N ,   j ≠ i ,where dsafei is the radius of the collision model corresponding to the ith aircraft; the collision model here is a normal sphere. The distance between the centroids of any two aircraft must be larger than the sum of the safe radius values of each aircraft.(2  ) No-Fly Zone Constraints. During the process of Free Flight, aircraft must avoid all no-fly areas, including flight prohibited areas, restricted areas, and dangerous areas. These actual areas in an operational environment may have different shapes. In this paper, three geometric shapes are used to represent these no-fly areas briefly: semiellipsoid, cylinder, and cuboid. No-fly areas in reality can be described or approximated adequately by proper combinations of these three basic shapes. In addition, the location and dimension parameters of these basic shapes can be defined as functions of time to represent the threat coefficient caused by no-fly areas.(a) A three-dimensional semiellipsoidal no-fly area is defined by 7 parameters: the coordinates of the centre location(xs,ys,hs), three semiaxes (a,b,c), and one orientation angle θ that relates the basic coordinate system to the principle system (X,Y,H) of the semiellipsoid. The semiellipsoidal no-fly area is shown in Figure 2.(4)XYH=Tθx-xsy-ysz-ys,where(5)Tθ=cos⁡θ-sin⁡θ0sin⁡θcos⁡θ0001.Figure 2
Ellipsoidal no-fly area.If a given point(xp,yp,hp), after the transformation to the principal system, satisfies(6)Xp2a2+Yp2b2+Zp2c2>1then it is outside of the semiellipsoidal no-fly area.(b) A cuboid no-fly area is defined by 7 parameters: the coordinates of the centre location(xc,yc,hc), three dimensions (a,b,c), and one orientation angle θ that relates the basic coordinate system to the principle system (X,Y,H) of the cuboid no-fly area. The transformation to the principle system is also achieved by (4). The cuboid no-fly area is shown in Figure 3.Figure 3
Cuboid no-fly area.If a given point(xp,yp,hp), after the transformation to the principal system, satisfies(7)Xp>a2,Yp>b2,Hp>cthen it is outside of the cuboid no-fly area.(c) A cylindrical no-fly area is defined by 5 parameters: the coordinates of the centre location(xc,yc,hc), the radius of the bottom surface, and the height (R,L). The transformation to the principle system is given by (8). The cylindrical no-fly area is shown in Figure 4.(8)XYH=x-xsy-ysz-ys.Figure 4
Cylinder no-fly area.A given point(xp,yp,hp) is outside of the cylinder if, after transformation, one of the following conditions is met:(9)Xp2+Yp2>R2orH>L.(3  ) Minimum Turning Angle Constraints (10) N x 2 + N y 2 + N z 2 i ≤ N i m a x ,  i = 1,2 , … , N , (11) or   Δ y ≤ Δ y m a x ,  Δ y m a x = R - R 2 - Δ x 2 ,where Δy is the deviation distance along the y-axis while the aircraft flies across Δx on the x-axis; Δymax is the maximum deviation distance along the y-axis while the aircraft flies across Δx on x-axis. The sketch map of the minimum turning radius constraints is shown in Figure 5.Figure 5
Minimum turning radius constraint sketch map.


## 3.1. Route Planning Problem Requirements

The route planning problem is an inevitable problem in a traditional ATC system; thus, the route planning method determines the efficiency of the ATC system. The approach of “Free Flight” is to leave out the route planning process, allowing each aircraft to plan a route itself. Generally, the route of an aircraft is a straight line between the take-off position and the landing destination. Unfortunately, Free Flight will also cause some problems, including aircraft conflict and a lack of supervision.In Semifree Flight, aircraft are not authorized to plan routes themselves; therefore, route planning is a critical module in the SFF ATC system. Route planning in the SFF ATC system is an optimization problem of multiple aircraft with multiple constraints.The imported data of the route planning module includes the flight request and the flight report from each aircraft at the current time. The information in each flight request includes the flight levels, the take-off position, the desired take-off time, the landing position, and the aircraft minimum turn radius; the information in the flight report includes the flight status in real time, such as the 3D coordinates, the velocity vector, and the remaining flight time. Moreover, the decision regarding whether to change the destination or not should also be reported.The route planning module sorts the flights along with their information and provides a flight plan list, as shown in Table1.Table 1
Flight plan list.
Flight number Flight level Take-off position Take-off time Landing position A 1 Civil (or C) φ T , ϕ T 1 11:50:06 φ L , ϕ L 1 … … … … … A i Civil (or C) φ T , ϕ T i 19:14:46 φ L , ϕ L iThe SFF ATC system will return the planned routes to the corresponding aircraft; each aircraft only needs to track its own route until it arrives at its destination or receives a new order. The planned route should consider 3 factors: performance index, flight constraints, and environment interferences.The performance index of route planning consists of 2 parts: flight time and flight path. The aim of collaborative route planning is to minimize the sum of the flight times and the sum of the paths of all aircraft.The flight constraints consist of 3 different variables: distance constraint between two aircraft, no-fly zone constraint, and minimum turning radius constraint. The distance constraint is posed as (1), which requires the distance between any two aircraft to be less than a safe distance.(1)pix,y,z,t-pjx,y,z,ti,j≤dsafe.The no-fly zone constraint restricts aircraft from entering no-fly zones; the decision method is described in Section 3.2. The minimum turning radius constraint is related to the grid generation, as described in Section 3.2.Environmental interferences have a certain influence on the flight routes of the aircraft, among which the greatest factor is the wind field. In the flight process, a flight with tailwind will have a somewhat reduced flight time.


## 3.2. Mathematical Description of the Route Planning Problem

Considering the actual problem and requirements, the route planning problem can be described by a mathematical model.Supposing the route planning module receivesN aircraft flight requests, the take-off windows are φT,ϕT,tTi, i=1,2,…,N, which can be transferred to xT,yTi in the launching coordinate system as well. The landing position of the ith aircraft is φL,ϕLi,i=1,2,…,N, which can also be transferred to φT,ϕTi in the launching coordinate system. Optimize the 4D route of each aircraft pi(t), including xt,yt,zti in the launching coordinate system, to minimize the performance index, as given in (2)min⁡Jx,y,h,t=∑ai=1ai=Nωaik1∫t0tfΔdΔtdt+k2tf,Δd=limxi+1→xi⁡xi+1-xi2+yi+1-yi2+zi+1-zi2,where ωai is the weight coefficient of the ith aircraft route; k1 and k2 are coefficients of the flight distance and the flight time, respectively.The path of theith aircraft pi(t) must satisfy the following constraints.(1  ) Safe Distance Constraint (3) x i t i - x j t j 2 + y i t i - y j t j 2 + z i t i - z j t j 2 ≥ d s a f e i + d s a f e j ,  j = 1,2 , … , N ,   j ≠ i ,where dsafei is the radius of the collision model corresponding to the ith aircraft; the collision model here is a normal sphere. The distance between the centroids of any two aircraft must be larger than the sum of the safe radius values of each aircraft.(2  ) No-Fly Zone Constraints. During the process of Free Flight, aircraft must avoid all no-fly areas, including flight prohibited areas, restricted areas, and dangerous areas. These actual areas in an operational environment may have different shapes. In this paper, three geometric shapes are used to represent these no-fly areas briefly: semiellipsoid, cylinder, and cuboid. No-fly areas in reality can be described or approximated adequately by proper combinations of these three basic shapes. In addition, the location and dimension parameters of these basic shapes can be defined as functions of time to represent the threat coefficient caused by no-fly areas.(a) A three-dimensional semiellipsoidal no-fly area is defined by 7 parameters: the coordinates of the centre location(xs,ys,hs), three semiaxes (a,b,c), and one orientation angle θ that relates the basic coordinate system to the principle system (X,Y,H) of the semiellipsoid. The semiellipsoidal no-fly area is shown in Figure 2.(4)XYH=Tθx-xsy-ysz-ys,where(5)Tθ=cos⁡θ-sin⁡θ0sin⁡θcos⁡θ0001.Figure 2
Ellipsoidal no-fly area.If a given point(xp,yp,hp), after the transformation to the principal system, satisfies(6)Xp2a2+Yp2b2+Zp2c2>1then it is outside of the semiellipsoidal no-fly area.(b) A cuboid no-fly area is defined by 7 parameters: the coordinates of the centre location(xc,yc,hc), three dimensions (a,b,c), and one orientation angle θ that relates the basic coordinate system to the principle system (X,Y,H) of the cuboid no-fly area. The transformation to the principle system is also achieved by (4). The cuboid no-fly area is shown in Figure 3.Figure 3
Cuboid no-fly area.If a given point(xp,yp,hp), after the transformation to the principal system, satisfies(7)Xp>a2,Yp>b2,Hp>cthen it is outside of the cuboid no-fly area.(c) A cylindrical no-fly area is defined by 5 parameters: the coordinates of the centre location(xc,yc,hc), the radius of the bottom surface, and the height (R,L). The transformation to the principle system is given by (8). The cylindrical no-fly area is shown in Figure 4.(8)XYH=x-xsy-ysz-ys.Figure 4
Cylinder no-fly area.A given point(xp,yp,hp) is outside of the cylinder if, after transformation, one of the following conditions is met:(9)Xp2+Yp2>R2orH>L.(3  ) Minimum Turning Angle Constraints (10) N x 2 + N y 2 + N z 2 i ≤ N i m a x ,  i = 1,2 , … , N , (11) or   Δ y ≤ Δ y m a x ,  Δ y m a x = R - R 2 - Δ x 2 ,where Δy is the deviation distance along the y-axis while the aircraft flies across Δx on the x-axis; Δymax is the maximum deviation distance along the y-axis while the aircraft flies across Δx on x-axis. The sketch map of the minimum turning radius constraints is shown in Figure 5.Figure 5
Minimum turning radius constraint sketch map.


## 4. Collaborative Dynamic Programming Formulation

The collaborative planning method is introduced in this section to solve the collaborative route planning problem for multiple aircraft described above. The collaborative planning method is divided into two parts: real-time dynamic grid method and collaborative dynamic programming algorithm.


### 4.1. Real-Time Dynamic Grid Method

The grid method, as a common cell decomposition modelling method, divides the flight space into 3-dimensional regular grids. The flight environment can be described through assignment of the grids. Moreover, the grid will be considered as the basic unit in the following route planning.The grid method has the following advantages: first, regular grid arrays are easy to store and calculate by computers, and the simple and direct relationship between contiguous grids can avoid complicated computation in processing obstacle boundary information; second, when the grid spacing is small enough, the grid method can describe any obstacle of any arbitrary shape and thus can be widely applied.The shortcomings of the grid method are mainly embodied in the conflict between the precision of the environmental description and the efficiency of the optimization algorithm. The smaller the grid size is, the more accurate its description is; moreover, the larger the storage space that this search algorithm occupies, the longer it takes. However, if the storage space and run time are reduced at the cost of the reduction of description accuracy, then a large difference might exist between the search result and the actual optimal path.To overcome the shortcomings described above, this section presents a real-time dynamic grid method. This method generates the particular coordinate system and grids of theith aircraft Ai at time t. The specific method is described as follows.Suppose the current location of aircraftAi at time t is x0,y0,h0i, and the target position is xT,yT,hTi. Establish the relative coordinate system of each aircraft Ai where the original point is x0,y0,h0i, the y′ axis is the connection from x0,y0,h0i to target point xT,yT,hTi, and the x′ axis is the intersection of the vertical plane of the y′ axis and the horizontal plane at the starting point; h′ axis, x′ axis, and y′ axis constitute aCartesian coordinate system. The schematic diagram is shown in Figure 7.The grid of theith aircraft Ai is partitioned based on the relative coordinate system described above. The specific method is given as follows.We suppose the number of intervals along thex′, y′, and h′ axis is Nx, Ny, and Nh, respectively, and the relationship between the interval and each axis maximum number can be described as(12)dx=xmax-xminNx-1,dy=ymax-yminNy-1,dh=hmax-hminNh-1.The setting method of grid parameters is presented as follows:(13)Nx=Nxmaxdis>12dis0roundNxmax•2disdis0110dis0<dis<12dis010<dis<110dis0,Ny=Nymax-NyminΔy,Δy=Δymax5,Nh=C•Nx,where Nymax is the maximum number of intervals along the y-axis, dis is the distance between the current location of the aircraft and target location, and dis0 is the distance between the location of aircraft and target location at initial time t=0. Δymax can be calculated by (11). Nh is C times Nx, where C is related to the rate of climb. The sketch map of Nx is shown in Figure 6.Figure 6
Grid parameter setting sketch.Figure 7
Schematic diagram of the relative coordinate system of aircraftAi.


### 4.2. Collaborative Dynamic Programming Algorithm

During the flights of multiple aircraft, the flight safe distance between any two aircraft is the major constraint to be considered. Moreover, the safe distance constraint makes it difficult for most single route planning method to solve route planning problem for multiple aircraft.In this section, a collaborative dynamic programming algorithm is proposed to solve the collaborative route planning problem for multiple aircraft. The detailed steps are posed as follows.Step 1.
Initialize time variablet=0, and define the size of the airspace:(14)x∈xmin,xmax,y∈ymin,ymax,z∈zmin,zmax.Step 2.
Input the information of the threat areas and waypoints as well as that of the wind field model.Step 3.
Input the take-off locationx0,y0,h0i, the take-off time t0i, and the target locations xT,yT,hTi of each aircraft Ai, i=1,2,…,N.Step 4.
Construct the relative coordinate system and the grids of each aircraftAi, i=1,2,…,N. The specific method can be found in Section 4.1.Step 5.
Prioritize short distance flights, considering the comfort of passenger. Sort the aircraft by distance to the target location: the aircraft with the minimum distance isnumber 1, and the one with the maximum distance isnumberN.Step 6.
Calculate the performance index and optimal route of theith aircraft.
Step  6.1. Calculate the flight trajectory and the performance index of the ith aircraft from 0th step p(x0,y0,h0) to 1st step p(xn1,y1,hn1), where xn1∈[x0-Δx,x0+Δx], hn1∈[h0-Δh,h0+Δh], and Δy and Δh satisfy the constraints of (9).
The performance index of point(xn1,y1,hn1) is calculated as(15)Jpxn1,y1,hn1=Jpx0,y0,h0+k1·disp→0,1+k2·Rpxn1,y1,hn1+k3·ΔVA2,where Jpxn1,y1,hn1 is the performance index of point p(xn1,y1,hn1), and Jpx0,y0,h0 is the performance index of the previous point p(x0,y0,h0); dis(p0,1) is the distance between the points p(x0,y0,h0) and pxn1,y1,hn1, which also represents the added performance index during the movement from p(x0,y0,h0) to pxn1,y1,hn1; Rpxn1,y1,hn1 represents the constraints of the flight trajectory from p(x0,y0,h0) to pxn1,y1,hn1, which includes the safe distance constraint, the threat area constraint, and so on; the calculation method of Rpxn1,y1,hn1 is introduced in Section 3.2. ΔVA2 is the wind factor of point p(xn1,y1,hn1), and k1, k2, and k3 are the weight coefficients corresponding to each index.
Save the optimal route with minimum performance index of each pointpxn1,y1,hn1 in storage Ωxn1,y1,hn1.
Step  6.2. Calculate the flight trajectory and the performance index of the ith aircraft from the 1st step pxn1,y1,hn1 to the 2nd step pxn2,y2,hn2, where xn2∈[xn1-Δx,xn1+Δx], hn2∈[hn1-Δh,hn1+Δh], and Δy and Δh satisfy the constraints of (10).
The performance index of point(xn2,y2,hn2) is calculated as(16)Jpxn2,y2,hn2=Jpxn1,y1,hn1+k1·disp→1,2+k2·Rpxn2,y2,hn2+k3·ΔVA2.
Save the optimal route with the minimum performance index of each pointpxn2,y2,hn2 in storage Ωxn2,y2,hn2.
Step 6. k. Calculate the flight trajectory and the performance index of the ith aircraft from the (k-1)th step p(xn(k-1),y(k-1),hn(k-1)) to kth step p(xnk,yk,hnk), where xnk∈[xn(k-1)-Δx,xn(k-1)+Δx], hnk∈[hn(k-1)-Δh,hn(k-1)+Δh], and Δy and Δh satisfy the constraints of (10).
Calculate the performance index of point(xnk,yk,hnk) as(17)Jpxnk,yk,hnk=Jpxnk-1,yk-1,hnk-1+k1·disp→k-1,k+k2·Rpxnk,yk,hnk+k3·ΔVA2.
Save the optimal route with minimum performance index of each pointp(xnk,yk,hnk) in storage Ω(xnk,yk,hnk).
Step 6. N x. Calculate the flight trajectory and the performance index of the ith aircraft from the (Nx-1)th step p(xnNx-1,yNx-1,hn(Nx-1)) to Nxth step p(xnNx,yNx,hnNx), where xnNx∈[xn(Nx-1)-Δx,xn(Nx-1)+Δx], hnNx∈[hnNx-1-Δh,hn(Nx-1)+Δh], and Δy and Δh must satisfy the constraints of the aircraft.
Calculate the performance index of point(xnNx,yNx,hnNx) as(18)JpxnNy,yNy,hnNy=JpxnNy-1,yNy-1,hnNy-1+k1·disp→Ny-1,Ny+k2·RpxnNy,yNy,hnNy+k3·ΔVA2.
Save the optimal route with minimum performance index of each pointp(xnNx,yNx,hnNx) in storage Ω(xnNx,yNx,hnNx).Step 7 (Nx+1).
Find the optimal trajectoryTi′ from the target point p(xT,yT,hT) back to p(x0,y0,h0) and transform trajectory Ti′ from the ith relative coordinate system x′-y′-z′ to Ti in the basic coordinate system x-y-z.Step 8.
Ifi<N, i=i+1, then go back to Step 5; else, go to Step 7.Step 9.
Smooth the trajectoryTi and track it for Δt; thus, t=t+Δt.Step 10.
Check if all the aircraft reach the target points: ifyes, then end the algorithm and go to Step 9; ifno, then go back to Step 2.Step 11.
Output all routes and performance indices of the aircraftAi, i=1,2,…,N.


## 4.1. Real-Time Dynamic Grid Method

The grid method, as a common cell decomposition modelling method, divides the flight space into 3-dimensional regular grids. The flight environment can be described through assignment of the grids. Moreover, the grid will be considered as the basic unit in the following route planning.The grid method has the following advantages: first, regular grid arrays are easy to store and calculate by computers, and the simple and direct relationship between contiguous grids can avoid complicated computation in processing obstacle boundary information; second, when the grid spacing is small enough, the grid method can describe any obstacle of any arbitrary shape and thus can be widely applied.The shortcomings of the grid method are mainly embodied in the conflict between the precision of the environmental description and the efficiency of the optimization algorithm. The smaller the grid size is, the more accurate its description is; moreover, the larger the storage space that this search algorithm occupies, the longer it takes. However, if the storage space and run time are reduced at the cost of the reduction of description accuracy, then a large difference might exist between the search result and the actual optimal path.To overcome the shortcomings described above, this section presents a real-time dynamic grid method. This method generates the particular coordinate system and grids of theith aircraft Ai at time t. The specific method is described as follows.Suppose the current location of aircraftAi at time t is x0,y0,h0i, and the target position is xT,yT,hTi. Establish the relative coordinate system of each aircraft Ai where the original point is x0,y0,h0i, the y′ axis is the connection from x0,y0,h0i to target point xT,yT,hTi, and the x′ axis is the intersection of the vertical plane of the y′ axis and the horizontal plane at the starting point; h′ axis, x′ axis, and y′ axis constitute aCartesian coordinate system. The schematic diagram is shown in Figure 7.The grid of theith aircraft Ai is partitioned based on the relative coordinate system described above. The specific method is given as follows.We suppose the number of intervals along thex′, y′, and h′ axis is Nx, Ny, and Nh, respectively, and the relationship between the interval and each axis maximum number can be described as(12)dx=xmax-xminNx-1,dy=ymax-yminNy-1,dh=hmax-hminNh-1.The setting method of grid parameters is presented as follows:(13)Nx=Nxmaxdis>12dis0roundNxmax•2disdis0110dis0<dis<12dis010<dis<110dis0,Ny=Nymax-NyminΔy,Δy=Δymax5,Nh=C•Nx,where Nymax is the maximum number of intervals along the y-axis, dis is the distance between the current location of the aircraft and target location, and dis0 is the distance between the location of aircraft and target location at initial time t=0. Δymax can be calculated by (11). Nh is C times Nx, where C is related to the rate of climb. The sketch map of Nx is shown in Figure 6.Figure 6
Grid parameter setting sketch.Figure 7
Schematic diagram of the relative coordinate system of aircraftAi.


## 4.2. Collaborative Dynamic Programming Algorithm

During the flights of multiple aircraft, the flight safe distance between any two aircraft is the major constraint to be considered. Moreover, the safe distance constraint makes it difficult for most single route planning method to solve route planning problem for multiple aircraft.In this section, a collaborative dynamic programming algorithm is proposed to solve the collaborative route planning problem for multiple aircraft. The detailed steps are posed as follows.Step 1.
Initialize time variablet=0, and define the size of the airspace:(14)x∈xmin,xmax,y∈ymin,ymax,z∈zmin,zmax.Step 2.
Input the information of the threat areas and waypoints as well as that of the wind field model.Step 3.
Input the take-off locationx0,y0,h0i, the take-off time t0i, and the target locations xT,yT,hTi of each aircraft Ai, i=1,2,…,N.Step 4.
Construct the relative coordinate system and the grids of each aircraftAi, i=1,2,…,N. The specific method can be found in Section 4.1.Step 5.
Prioritize short distance flights, considering the comfort of passenger. Sort the aircraft by distance to the target location: the aircraft with the minimum distance isnumber 1, and the one with the maximum distance isnumberN.Step 6.
Calculate the performance index and optimal route of theith aircraft.
Step  6.1. Calculate the flight trajectory and the performance index of the ith aircraft from 0th step p(x0,y0,h0) to 1st step p(xn1,y1,hn1), where xn1∈[x0-Δx,x0+Δx], hn1∈[h0-Δh,h0+Δh], and Δy and Δh satisfy the constraints of (9).
The performance index of point(xn1,y1,hn1) is calculated as(15)Jpxn1,y1,hn1=Jpx0,y0,h0+k1·disp→0,1+k2·Rpxn1,y1,hn1+k3·ΔVA2,where Jpxn1,y1,hn1 is the performance index of point p(xn1,y1,hn1), and Jpx0,y0,h0 is the performance index of the previous point p(x0,y0,h0); dis(p0,1) is the distance between the points p(x0,y0,h0) and pxn1,y1,hn1, which also represents the added performance index during the movement from p(x0,y0,h0) to pxn1,y1,hn1; Rpxn1,y1,hn1 represents the constraints of the flight trajectory from p(x0,y0,h0) to pxn1,y1,hn1, which includes the safe distance constraint, the threat area constraint, and so on; the calculation method of Rpxn1,y1,hn1 is introduced in Section 3.2. ΔVA2 is the wind factor of point p(xn1,y1,hn1), and k1, k2, and k3 are the weight coefficients corresponding to each index.
Save the optimal route with minimum performance index of each pointpxn1,y1,hn1 in storage Ωxn1,y1,hn1.
Step  6.2. Calculate the flight trajectory and the performance index of the ith aircraft from the 1st step pxn1,y1,hn1 to the 2nd step pxn2,y2,hn2, where xn2∈[xn1-Δx,xn1+Δx], hn2∈[hn1-Δh,hn1+Δh], and Δy and Δh satisfy the constraints of (10).
The performance index of point(xn2,y2,hn2) is calculated as(16)Jpxn2,y2,hn2=Jpxn1,y1,hn1+k1·disp→1,2+k2·Rpxn2,y2,hn2+k3·ΔVA2.
Save the optimal route with the minimum performance index of each pointpxn2,y2,hn2 in storage Ωxn2,y2,hn2.
Step 6. k. Calculate the flight trajectory and the performance index of the ith aircraft from the (k-1)th step p(xn(k-1),y(k-1),hn(k-1)) to kth step p(xnk,yk,hnk), where xnk∈[xn(k-1)-Δx,xn(k-1)+Δx], hnk∈[hn(k-1)-Δh,hn(k-1)+Δh], and Δy and Δh satisfy the constraints of (10).
Calculate the performance index of point(xnk,yk,hnk) as(17)Jpxnk,yk,hnk=Jpxnk-1,yk-1,hnk-1+k1·disp→k-1,k+k2·Rpxnk,yk,hnk+k3·ΔVA2.
Save the optimal route with minimum performance index of each pointp(xnk,yk,hnk) in storage Ω(xnk,yk,hnk).
Step 6. N x. Calculate the flight trajectory and the performance index of the ith aircraft from the (Nx-1)th step p(xnNx-1,yNx-1,hn(Nx-1)) to Nxth step p(xnNx,yNx,hnNx), where xnNx∈[xn(Nx-1)-Δx,xn(Nx-1)+Δx], hnNx∈[hnNx-1-Δh,hn(Nx-1)+Δh], and Δy and Δh must satisfy the constraints of the aircraft.
Calculate the performance index of point(xnNx,yNx,hnNx) as(18)JpxnNy,yNy,hnNy=JpxnNy-1,yNy-1,hnNy-1+k1·disp→Ny-1,Ny+k2·RpxnNy,yNy,hnNy+k3·ΔVA2.
Save the optimal route with minimum performance index of each pointp(xnNx,yNx,hnNx) in storage Ω(xnNx,yNx,hnNx).Step 7 (Nx+1).
Find the optimal trajectoryTi′ from the target point p(xT,yT,hT) back to p(x0,y0,h0) and transform trajectory Ti′ from the ith relative coordinate system x′-y′-z′ to Ti in the basic coordinate system x-y-z.Step 8.
Ifi<N, i=i+1, then go back to Step 5; else, go to Step 7.Step 9.
Smooth the trajectoryTi and track it for Δt; thus, t=t+Δt.Step 10.
Check if all the aircraft reach the target points: ifyes, then end the algorithm and go to Step 9; ifno, then go back to Step 2.Step 11.
Output all routes and performance indices of the aircraftAi, i=1,2,…,N.


## 5. Numerical Simulations

This section presents 3 simulations to reflect the feasibility of the route planning module in the SFF system and the collaborative dynamic programming method. These simulations test the routes planning module from three aspects as well as the route planning method. Simulation 1 shows the function of route planning for multiple aircraft at the same time. Simulation 2 shows the function of avoiding conflict between two aircraft during route planning. Simulation 3 shows the function of route replanning for an aircraft.According to the work mode of the SFF ATC system shown in Figure1, the SFF system receives information from each aircraft that plans to take off the next day and then plans the flight routes for these aircraft based on the collaborative dynamic programming algorithm.Generally, the SFF system receives information from each aircraft that plans to take off the next day.


### 5.1. 3D Planned Route Simulation Results

The multiple aircraft route planning module begins to work after the SFF ATC system receives the flight information from each aircraft the next day. The SFF ATC system arranges this information as shown in Table1 and plans routes for the aircraft according to their requests.Simulation 1 gives the take-off windows and the goal locations of 50 aircraft:φT,ϕT,tTi and xT,yTi, i=1,2,…,N. Use the collaborative dynamic programming algorithm to optimize the routes of 50 aircraft; the optimal results must satisfy the constraints of (2)~(9), and the global performance index of (2) should be minimized. The numerical results calculated via the collaborative dynamic programming method are shown as in Figures 8–11. Figure 8 shows the surrounding wind model in the flight simulation. Figure 9 shows the 3D planned routes in the flight zone, and Figures 10 and 11 are the horizontal and vertical views, respectively, of Figure 9. In this simulation result, we can see the flight route of each aircraft reaches its goal destination; moreover, no flight route enters any threat zone.Figure 8
Wind model map.Figure 9
3D planned routes of 50 aircraft.Figure 10
Planned routes of 50 aircraft in the horizontal plane.Figure 11
Planned routes of 50 aircraft in the vertical plane.The results of simulation 1, including Figures9–11, show that collaborative dynamic programming can plan routes for multiple aircraft; however, the flight conflict situation is reflected in Figure 9. Even though two tracks are intersecting, we cannot judge that they will collide because the take-off time of each aircraft is different. Simulation 2 selects two flight routes to analyse the function of conflict resolution.


### 5.2. Flight Conflict Resolution Analysis

This subsection discusses the method to resolve flight conflicts in the SFF ATC system. In the SFF module, the method to resolve flight conflict is not by conflict resolution rules but by the conflict penalty function in the route planning process.To test the ability to resolve conflicts, we choose 2 flight routesri and rj to describe its ability: the take-off time ti of ri is 351.6 s, and the take-off time tj of rj is 94.7 s. If aircraft ai flies straight to its destination, then flight routes ri and rj will be in conflict. In the route planning process of aircraft aj, the system predicted the flight conflict; thus, aircraft aj chooses another route as its optimal route. The simulation result is shown in Figure 12.Figure 12
Sketch map of two 3D routes’ avoidance.
(a)
3D view (b)
Horizontal viewFrom the simulation result, we can see that aircraftaj changes its planned route rj before meeting aircraft ai; thus, no flight conflict occurs with ai. The difference between the SFF system and the Free Flight system is that in the Free Flight system, conflict resolution takes effect at the moment when the two aircraft notice that they will collide, whereas the SFF system plans the routes of the aircraft in advance to avoid collision.


### 5.3. Route Replanning Analysis

This simulation tests the function of route replanning. The route replanning problem occurs during the flight of an aircraft. The original destination of theith aircraft is (xT,yT), assuming that the ith aircraft changes to a new destination (xT∗,yT∗) at time tip.The replanned route is shown in Figure13, where the blue line is the original planned route of the aircraft, and the red line is the replanned route for the new destination.Figure 13
Sketch map of route replanning.
(a)
3D route (b)
Horizontal routeIn this route replanning simulation, the replanned route reaches the goal destination correctly and satisfies the safe distance and no-fly zone constraints.


### 5.4. Cooperation with the Present ATC System

This simulation plans the flight route of the aircraft of the present ATC system under the same conditions as those of the simulation in Section5.3. The planned results are shown in Figure 14; the red stars are the ground radar towers for communication with aircraft, and the green line is the planned route for the aircraft of the present ATC system that must pass the ground radar tower.Figure 14
Planned route cooperation between the present ATC and the SFF ATC systems.The flight distance of the planned route obtained by the present ATC system, which is the green line, is 582.83 km, and that of the SFF ATC system is 546.21 km. The primary cause of this condition is that the aircraft of the present ATC system must pass the ground radar tower, thus preventing it from choosing the optimal path.Compared with the present ATC system, the route planning method of the SFF ATC system can provide the aircraft with shorter flight routes.


## 5.1. 3D Planned Route Simulation Results

The multiple aircraft route planning module begins to work after the SFF ATC system receives the flight information from each aircraft the next day. The SFF ATC system arranges this information as shown in Table1 and plans routes for the aircraft according to their requests.Simulation 1 gives the take-off windows and the goal locations of 50 aircraft:φT,ϕT,tTi and xT,yTi, i=1,2,…,N. Use the collaborative dynamic programming algorithm to optimize the routes of 50 aircraft; the optimal results must satisfy the constraints of (2)~(9), and the global performance index of (2) should be minimized. The numerical results calculated via the collaborative dynamic programming method are shown as in Figures 8–11. Figure 8 shows the surrounding wind model in the flight simulation. Figure 9 shows the 3D planned routes in the flight zone, and Figures 10 and 11 are the horizontal and vertical views, respectively, of Figure 9. In this simulation result, we can see the flight route of each aircraft reaches its goal destination; moreover, no flight route enters any threat zone.Figure 8
Wind model map.Figure 9
3D planned routes of 50 aircraft.Figure 10
Planned routes of 50 aircraft in the horizontal plane.Figure 11
Planned routes of 50 aircraft in the vertical plane.The results of simulation 1, including Figures9–11, show that collaborative dynamic programming can plan routes for multiple aircraft; however, the flight conflict situation is reflected in Figure 9. Even though two tracks are intersecting, we cannot judge that they will collide because the take-off time of each aircraft is different. Simulation 2 selects two flight routes to analyse the function of conflict resolution.


## 5.2. Flight Conflict Resolution Analysis

This subsection discusses the method to resolve flight conflicts in the SFF ATC system. In the SFF module, the method to resolve flight conflict is not by conflict resolution rules but by the conflict penalty function in the route planning process.To test the ability to resolve conflicts, we choose 2 flight routesri and rj to describe its ability: the take-off time ti of ri is 351.6 s, and the take-off time tj of rj is 94.7 s. If aircraft ai flies straight to its destination, then flight routes ri and rj will be in conflict. In the route planning process of aircraft aj, the system predicted the flight conflict; thus, aircraft aj chooses another route as its optimal route. The simulation result is shown in Figure 12.Figure 12
Sketch map of two 3D routes’ avoidance.
(a)
3D view (b)
Horizontal viewFrom the simulation result, we can see that aircraftaj changes its planned route rj before meeting aircraft ai; thus, no flight conflict occurs with ai. The difference between the SFF system and the Free Flight system is that in the Free Flight system, conflict resolution takes effect at the moment when the two aircraft notice that they will collide, whereas the SFF system plans the routes of the aircraft in advance to avoid collision.


## 5.3. Route Replanning Analysis

This simulation tests the function of route replanning. The route replanning problem occurs during the flight of an aircraft. The original destination of theith aircraft is (xT,yT), assuming that the ith aircraft changes to a new destination (xT∗,yT∗) at time tip.The replanned route is shown in Figure13, where the blue line is the original planned route of the aircraft, and the red line is the replanned route for the new destination.Figure 13
Sketch map of route replanning.
(a)
3D route (b)
Horizontal routeIn this route replanning simulation, the replanned route reaches the goal destination correctly and satisfies the safe distance and no-fly zone constraints.


## 5.4. Cooperation with the Present ATC System

This simulation plans the flight route of the aircraft of the present ATC system under the same conditions as those of the simulation in Section5.3. The planned results are shown in Figure 14; the red stars are the ground radar towers for communication with aircraft, and the green line is the planned route for the aircraft of the present ATC system that must pass the ground radar tower.Figure 14
Planned route cooperation between the present ATC and the SFF ATC systems.The flight distance of the planned route obtained by the present ATC system, which is the green line, is 582.83 km, and that of the SFF ATC system is 546.21 km. The primary cause of this condition is that the aircraft of the present ATC system must pass the ground radar tower, thus preventing it from choosing the optimal path.Compared with the present ATC system, the route planning method of the SFF ATC system can provide the aircraft with shorter flight routes.


## 6. Conclusions

Semifree Flight is a new air traffic control mode proposed in this paper. “Semifree Flight” centralizes the information of all aircraft and sends back individualized command and control instructions to each aircraft. In this control mode, multiple aircraft route planning is the key technological aspect of the air traffic control process.From the simulations in Section5, the following conclusions can be obtained:(1)
Each aircraft in the SFF ATC system can choose its take-off and landing positions freely and send its plan to the SFF ATC system. The SFF ATC system would approve the requests from the aircraft without a special case.(2)
The flight route with the minimum flight distance for each aircraft is planned by the ATC system. Autonomous planning of the aircraft is not allowed to decrease the global flight distance and to guarantee the safety of the system.(3)
The route planning method can avoid flight collisions between aircraft.Thus, the SFF ATC system can realize the functions of a Free Flight system. Each aircraft can fly to its desired destination with a minimum flight distance, and, during the flight process, the SFF ATC system remains in contact with the aircraft to supervise them and provide feedback on a replanned route if the aircraft must change its destination.In addition, the communication mode of the SFF ATC system guarantees that every aircraft is under the control of the ATC system, thereby avoiding the problem of the ATC system lacking supervisory control.Semifree Flight is a feasible method to improve the air traffic control system in the short term. The study of Semifree Flight and its route planning method in this paper proved its feasibility in civil aviation and its ability to satisfy all flight path requests of the aircraft. Semifree Flight can serve as the transition from an air traffic control mode to Free Flight mode; in Semifree Flight mode, pilots can fly to an arbitrary destination freely but must follow the planned route provided by the ATC system. On the one hand, Semifree Flight gives freedom to each pilot; on the other hand, the ATC system still supervises the aircraft.



---

*Source: 3521905-2018-03-18.xml*