Token allocation strategy for free-flight conflict solving
Track:Emerging Applications,Technology and Issues
G´e raud Granger and Nicolas Durand and Jean-Marc Alliot
CENA/LOG
7,av Ed Belin
31055Toulouse Cedex France
tel:(33)562174054-fax:(33)562174143
email:ac.a.fr-alliot@dgac.fr
Abstract
For the last10years,airlines have widely supported research
on the development of airspaces where aircraft would be free
to decide their trajectory:these areas where called Free-flight
airspaces.However,as soon as two aircraft are in the same
area,their separation must be guaranteed.FACES1is an
autonomous and coordinated embarked(on board)conflict
solver for Free Flight airspace.It solves conflict by comput-
ing simple manoeuvres that guarantees conflict free trajecto-
ries for the next minutes(min).Coordination is ensured by
giving sequential manoeuvres to aircraft with a token alloca-
tion strategy.FACES can be implemented with the current
positioning,broadcasting andflight management technology.
Moreover,it is robust to communication or system failure for
time up to one or two minutes.FACES was tested with a
traffic simulator on busy traffic days over France.Airspace
overflight level2320was considered as Free Flight.
Introduction
We have all experienced at least once a long wait in an over-
crowded air terminal.Reading magazines distributed by air-
lines during these long hours,we often found that they con-
sider air traffic control as one of the major cause for delays.
And it is true that the air traffic control system is becom-
ing saturated.But,if delays due to overloaded airports are
easy to understand,it is much harder to comprehend delays
due to the En Route control system.In fact,if we ask a
mathematician to analyze the system in cold blood,it can be
proved that the collision probability overflight level320is
very low for aircraftflying direct routes,especially if some
elementary precautions are taken regarding face to face or
overtaking conflicts.So,En Route control could be consid-
ered as expensive(En route charges),inefficient(delays in-
duced)and statistically of very little use.However,if the
Free Route and Free Flight concepts are attractive,espe-
cially to airlines,we still must consider safety as thefirst
priority,and design new algorithms and systems for these
new airspaces(airspace aboveflight level320).
3These parameters can be modified.Thisfirst study does not
discuss the opportunity of increasing or decreasing these values.
Manoeuvres suggested have to be simple to understand and to execute.No manoeuvre can be given during thefirst minute(called the quiescent period)in order to give enough time to the solver to compute a solution and inform the pi-lot(or directly program the FMS).Moreover,only one ma-noeuvre can be given to one aircraft during a minutes time window,and no manoeuvre can start as long as the previous one is notfinished.
The algorithm enforces a global resolution order between conflicting aircraft.The general principle is as follows:the aircraft which isfirst chooses its trajectory without consid-ering other aircraft.Then,the next aircraft in the priority queue takes this trajectory into account,and computes its own,and so on(see section).
Airspace overflight level1is considered as a Free Flight airspace.This area is not a so low density area,es-pecially in France.So it is an excellent test zone for a Free Flight solver.All aircraft entering this
airspace are supposed to be separated for5minutes when entering the Free Flight zone,and are sent back separated for the next5minutes when leaving it.All aircraft entering this airspace have to be Free Flight compliant,i.e:
they all have synchronous clock;
they are able to receive all broadcast information from other aircraft which are within a nmi zone around them (see part);
they are all equipped with the FACES solver.
they are able each minute at the same time to compute, and store their current position,their Free Flight airspace exit point and their predicted trajectory for the next5min-utes.
they are able to reliably broadcast the latter information as soon as it has been computed.
This information consists of203D-points,one every15 seconds(in fact,only16are needed,those beginning at min).Extra information is added to the predicted position that indicates its accuracy(the uncertainty model is detailed in part).Of course,the more accurate the informa-tion,the more efficient detection and resolution.This pre-diction has to be as soon as an aircraft has broadcast
these informations,it has to keep to this trajectory for the next5minutes as long as the solver does not give a manoeuvre.It must be noticed that on exceptional occa-sions,one aircraft can modify this trajectory,or aircraft not equipped for Free Flight can be accepted in the Free Flight zone.This can also take into account exceptional events such as the failure of one aircraft conflict solver.Theses air-craft will be given the highest priority number(see part)and all other aircraft will build their trajectory in order to avoid them.This should be a last resort as the algorithm might fail if two such aircraft are present at the same time in the same zone.Manoeuvre modelling
As stated above,time is discretized into seconds4time steps.As manoeuvres must remain simple to understand and execute,the turning point modelling is chosen in the horizontal plane(seefigure1).In this article,no manoeuvre is given in the vertical plane5.As shown onfigure1,a ma-
α
t
01
t
Figure1:Turning point modelling.
noeuvre is a heading change of,and degrees right or left,it starts at time,and ends at time.As stated above,(and)are always larger than1minute. Uncertainty modelling and1-to-1conflict detection A very simplefilter isfirst applied:only aircraft within a90 nmi zone are considered as being potential threats.This ra-dius is such that aircraft facing each other at kn cannot be in conflict6during the next minutes if they are not in the detection zone of the facing aircraft.
We then assume that there is an error about the aircraft’s future location because of ground speed prediction uncer-tainties7.Uncertainties on climbing and descending rates are even more important8.Uncertainties on the future positions of aircraft are all the more important because the prediction is faraway.
In the vertical plane,we use a cylindrical modelling(fig-ure2).Each aircraft has a maximal altitude and a minimal altitude.To check if two aircraft are in conflict,the minimal altitude of the higher aircraft is compared to the maximal altitude of the lower aircraft.
In the horizontal plane,an aircraft is represented by a point at the initial time.The point becomes a line segment in the uncertainty direction(the speed direction here,seefigure 2).Thefirst point of the line“flies
”at the maximum possi-ble speed,and the last point at the minimum possible speed. When changing direction(),the segment becomes a parallelogram that increases in the speed direction.When changing a second time direction(),the parallelogram
VERTICAL PLANE
Figure2:Modelling of speed uncertainties. becomes a hexagon that increases in the new speed direc-tion.To check the separation standard at time,we compute the distance between the two polygons modelling the aircraft positions and compare it to the separation standard at each time step of the simulation.It must be noticed that,as only one manoeuvre can be given in a minutes time window, and
as no manoeuvre can start as long as the previous one is notfinished,the convex can only be a line,a parallelogram or an hexagon.
A classical problem in1to1conflict detection is symme-try.If aircraft considers it is in conflict with aircraft, then must consider as a conflicting aircraft.In FACES, broadcasting of positions guarantees that two aircraft that can detect each other share exactly the same information re-garding their positions.As detection algorithms are identi-cal,1to1detection will always be symmetrical.
Ordering strategy
The coordination problem
Centralized automatic solvers as described by N.Du-rand(Durand1996)find a global solution to clusters involv-ing many aircraft.Manoeuvres are then given to aircraft simultaneously.An on board solver cannot be based on the same principle:aircraft do not share the same informa-tion,as they do not have the same detection zone(limited to90nmi).A coordination problem appears and must be solved.
The Free-R(VU N.Duong1997)project uses extended flight rules to solve this problem.The TCAS system uses the transponder code to decide which aircraft has to manoeuvre; giving resolution priorities to aircraft is a way often adopted for solving the coordination problem.
A resolution priority order9has to be total if we want each aircraft to solve all conflicts when there is more than air-craft.For example,the Visual Flight Rule that gives priority to the aircraft coming from the right does not define a global
Step
2
4
6630A8
3
20
20A6
20
1A3
1
0A5
Table 1:Token allocation at the different steps of resolution and .detects ,,,and .detects ,and .detects ,and .detects and .Conflicting aircraft are ,,,
,,and .Aircraft that
has the highest priority is and the lowest priority order is
(
).
is in conflict with Figure 4:Cluster of aircraft in conflict
Tokens are allocated as presented on figure 4.
Table 1gives the token allocation at the different steps of the resolution.During step ,and (token)choose their trajecto-ries without considering other aircraft in their detection area (which have at least token).Then,they broadcast their unmodified trajectories and all aircraft that have received a token from them cancel it.,and cancel the tokens sent by ,and cancel the tokens sent by .During step ,(token)has no token and modifies its trajectory to solve conflict with (token).,,,and cancel the tokens sent by .During step ,(token)modifies its trajectory to solve conflict with (token),
(token)modifies its trajectory to solve conflict with (token);the new trajectory must not interfere with (token).cancels one token sent by and cancels
two tokens sent by and .During step ,(token)
modifies its trajectory to solve conflict with (token),the new trajectory must not interfere with (token).and cancel one token sent by .During step ,(token)modifies its trajectory to solve conflict with (to-ken)and (token);the new trajectory must not interfere with (token),(token),(token)and (token).cancel
s the token sent by .1.During step ,(token)modifies its trajectory to solve conflict with (token);the new trajectory must not interfere with (token)and (token).
Provability
The allocation-resolution method described above cannot lead to situations where all aircraft would have at least one token or situations where two aircraft detecting each other without any token would have to solve simultaneously.This is guaranteed by the use of a total priority order on aircraft.At each step,an aircraft with no token cannot have any other conflicting aircraft (that has not already solved)with no to-ken in its detection area.In such a case,one of these two aircraft would have given a token to the other.At each step,among the conflicting aircraft that have not already solved,there is one that has the highest priority.This aircraft cannot have any token.It can solve and get back its tokens.The algorithm can be mathematically proved.
The
algorithm
As soon as the resolution order is chosen,the problem is to
solve a to conflict problem:we have to find the minimum length trajectory for an aircraft avoiding already fixed air-craft trajectories,that can be considered as obstacles.This is a classical robotics problem,therefore a classical al-gorithm (see (Pearl 1984))is used.
In the present application,the initial state is the state of the solving aircraft at minute.The terminal states are the possible states of the solving aircraft after minutes of flight or when they have reached their destination.
Each branch of the tree represents a possible trajectory of the solving aircraft.Fortunately,the heuristic function is used to only develop a small part of the tree.
The cost of a path is the trajectory length described by this path.Before starting a manoeuvre,an aircraft is in state.At each time step,each state generates states cor-responding to the possible deviations of the trajectory (,,degrees right or left),and state (the aircraft is not manoeuvred).At each time step,each state generates one state (the manoeuvre is extended)and one state (the aircraft is sent back to its Free Flight zone exit point).Every state generates a terminal state after minutes or if the aircraft has reached its destination.
The cost function
measures the distance between the position of the aircraft at node (time step ,state )and the position of the aircraft at node (time step ,state ).If a conflict occurs between node and node ,the value is widely increased so that the corresponding branch is no longer developed.The heuristic function is here the direct distance be-tween node and the Free Flight exit point (destination)of
the solving aircraft.This heuristic is clearly an underesti-mating one,which guarantees that the optimal solution will always be found.truncatedelete
Generally,many different paths are developed and the depth of the tree is(minutes).In this applications,the solution is given in less than seconds on a Pentium II300, even for the biggest1-to-35conflict.
Experimental results and improvements The CATS simulator
The algorithm described in part and was tested on the
CATS(Alliot et al.1997)simulator.The core of the CATS system is an En-route traffic simulation engine.It is based on a discrete,fixed time slice execution model:the position and speed of aircraft are computed atfixed time steps,usu-ally every5,10or15seconds.
Aircraft performances are in tabulated form describing ground speed,vertical speed,and fuel burn as a function of altitude,aircraft type andflight segment(cruise,climb or descent.)
In the further applications,aircraft use direct routes to their destination.The separation standard used is nauti-cal miles in the horizontal plane and ft vertically10. Conflicts were not solved underflight level,and a delay was added when necessary for aircraft entering the Free Flight zone in order to separate them on entry points.Un-certainties on speed(either vertical or horizontal)were set to minimal values.
Results
Results presented in this part are obtained with the
flight plans of the of June with no regulation.The Free Flight zone defined is the airspace aboveflight level .The allocation-resolution strategy described in part is repeated every minute and the trajectory prediction is done on the next minutes.
It was found that aircraft enter the Free Flight zone.
conflicts are detected in this zone during the day.
As described in section,the algorithm requires the defi-nition of a total order among aircraft.
The following order is used:an aircraft that is manoeuvre free has a lower priority order than an aircraft that has al-ready started a manoeuvre.The CAUTRA number is used to compare two manoeuvre free aircraft or two manoeuvred aircraft.A maneuver efficiency criteria is also added to the cost criteria in order to prevent aircraft from postponing a crossing maneuver when necessary.Therefore,when two aircraft must cross,the manoeuvre that enforces crossing must have a lower cost than the manoeuvre that postpones the crossing.This new criteria is included in the algo-rithm.
With this new priority order,the algorithm is called times.At the end of the simulation,conflicts remain
Mean Max
per delayed acft
while entering
inside(man)
Waiting
aircraft
1
3
5
7
Table3:Number of waiting aircraft.
So,regarding delays,the performance of the algorithm is very good.
Unsolved conflicts and priority order
There are aircraft in each remaining unsolved conflicts. These conflicts appear because the order between aircraft is not well chosen.
Moreover,it looks extremely difficult to devise an algo-rithm that wouldfind the best possible order without seri-ously increasing the complexity of the global algorithm and the necessary capacity of the communication medium.On-board conflict solvers which have only a partial information on the global si
tuation will almost certainly remain subop-timal,while centralized conflict solvers are able tofind the global optimal solutions.However,this may not be a too serious concern in the upper airspace:the simulation above shows that this algorithm is almost always able to solve con-flicts,even with situations as complex as the one presented on onfigure5where aircraft are involved,while delays remain small.
4956 160
329= 450
1347 131
330= 470
Figure5:aircraft in the detection zone.
Conclusion
We have demonstrated in this article that an efficient on board algorithm for Free Flight conflict resolution can be designed and implemented.This algorithm has the follow-ing advantages:
Compared to a centralized automated system,the devel-opment of such a system could be relatively low cost. Most hypothesis are quite weak:synchronous clocks are already available with GPS,FMS are now elaborate enough to provide the information needed for trajectory prediction in the next5minutes,provides sufficient ca-pacity for communications;the1to resolution algo-rithm is simple to implement and has already been widely used for similar problems in robotics;computing power neededfits in a standard PC computer.
Compared to rule based system,the algorithm is mathe-matically provable,and the simulation above shows that it would be efficient in upper airspace,even when density is quite high
Compared to purely reactive systems(Zeghal1998b), which usually requires permanent changes in headings, the manoeuvre model is classical and easy to implement. Further,and this is the main point to stress,as trajecto-ries are guaranteed conflict free for at least5minutes,a transient failure of communications would not have a dis-astrous effect:the system could still restart later on;reso-lutions would be less optimal,more vertical manoeuvres could be necessary to solve all conflicts,as anticipation would be shorter,but the risk of collision would remain insignificant.
The system could be progressively put into service byfirst defining Free Flight airspace over oceanic ar
eas,and grad-ually extending them.This would help solving the clas-sical transition problem from the current system to a par-tially automated one.
We are aware that the whole system depends on thefi-ability and availability of transmissions.Requirements on the bandwidth are low enough to enable multiple emissions of messages.But error correlations would have to be con-sidered.We miss informations and results on these issues. However,we believe that an airborne implementation of this algorithm can be seriously considered.
References
Alliot,J.;Durand,N.;Bosc,J.;and Maugis,L.1997.Cats: a complete air traffic simulator.16th AIAA/IEEE Digital Avionics Systems Conference,IRVINE.
Bosc,J.-F.1997.Techniques d’´e vitement r´e actif et simu-lation du trafic a´e rien.Ph.D.Dissertation,Ecole Nationale de L’aviation civile.
Durand,N.1996.Optimisation de Trajectoires pour la R´e solution de Conflits en Route.Ph.D.Dissertation,EN-SEEIHT,Institut National Polytechnique de Toulouse. Granger,G.;Durand,
N.;and Alliot,J.1998.FACES: a Freeflight Autonomous and Coordinated Embarked Solver.In2ST U.S.A/EUROPE ATM R&D Seminar. Pearl,J.1984.Heuristics.Addison-Wesley.
VU N.Duong,Eric Hoffman,J.-P.N.1997.Autonomous aircraft.1st U.S.A./EUROPE Air Traffic Management R&D Seminar,SACLAY.
Zeghal,K.1998a.A comparison of different approaches based on forcefields for coordination among multiple mo-biles.In IEEE International Conference on Intelligent Robotic System(IROS).
Zeghal,K.1998b.A review of different approaches based on forcefields for airborne conflict resolution.AIAA Guid-ance,Navigation and Control Conference.

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。