Probabilistic Conflict Detectionin the Presence of Uncertainty
Yoshinori MATSUNO, Takeshi TSUCHIYA
Department of Aeronautics and Astronautics
The University of TokyoEIWAC 2013Outline• Background• Purpose• Probabilistic approach• Simulation results• Summary• Future work

2

EIWAC 2013

3Background• Current air traffic management system
Human-operated system• Increasing demand in air traffic
Double to Triple in the next 25 years

Workloads of air traffic controllers reach limits.

EIWAC 2013

4Background• Automated air traffic control system
Satisfy air traffic demands
Alleviate the workloads of air traffic controllers• Primary concern of air traffic control
Monitor airspace for safety
Maintain safe separation between aircraft

Avoid conflict between aircraft

Automation of conflict detection

Safe separation

Conflict

EIWAC 2013

Purpose• Decision support tools
Assist air traffic controllers
Detect possible conflicts between aircraft

Conflict• Conflict Detection
Merging (in Terminal Area)
Detect potential conflicts
by estimating aircraft’s future trajectories

5

EIWAC 2013

Purpose
1. Trajectory Prediction• Estimate aircraft’s future trajectories

2. Conflict Detection• Detect possible conflicts

Conflict

6

EIWAC 2013

Trajectory Prediction• Deterministic• Probabilistic

7

EIWAC 20138

Trajectory Prediction• Deterministic

Fly along flight plans
Completely predict future
positions of aircraft
Optimistic predictions

EIWAC 20139

Trajectory Prediction• Probabilistic

Consider various uncertainties• Wind• Measurement error• Navigation error• etc.

More appropriate to model
the aircraft’s motion

EIWAC 2013

Probabilistic Approach• Uncertainties
Modeled as standard deviations of the GaussianWind prediction error• 5.17 m/s

Airspeed measurement error• 5 knots (2.57 m/s)

Current position estimation error• 50 m laterally

Based on empirical air traffic data

10

EIWAC 201311

Probabilistic Approach• 2 dimensional horizontal plane• Stochastic aircraft’s motion(stochastic differential equation)

Wind prediction error
5 random variables

Stochastic solution• Statistical information
Expected value
Variance
Covariance
Airspeed measurement error
Current position estimation error

EIWAC 201312

Probabilistic Approach• Monte Carlo Simulation
Random sampling of random variables
Solve as deterministic problems on each sample point
Easy to implement, but high computational burden• Generalized Polynomial Chaos
Preserve the ease of implementation
Reduce computational burden
1. Polynomial approximation to determine the solution
2. Collocation points as the sample points

EIWAC 201313

Generalized Polynomial Chaos• Polynomial approximation
Stochastic solutions are expressed as orthogonal
polynomials of random variables.

M th order approximation

Random variables(Uncertainties)

Stochastic solution :Coefficient

Polynomial basis function

Determined by collocation points

14

EIWAC 2013

Generalized Polynomial Chaos• Collocation points of random variables
Not random sampling method (e.g. Monte Carlo Simulation)
Strategically sampling method
Total number of collocation points

Coefficient :Weights
Deterministic solution

Collocation point

Collocation points and weights are determined uniquely
based on extension of Gaussian quadrature

EIWAC 2013

Generalized Polynomial Chaos• Stochastic solution
Determined by Q deterministic solutions

Statistical information
Expected Value :Variance :

15

16

EIWAC 2013

Generalized Polynomial Chaos
Generate collocation points and weights

Solve deterministic problems on each collocation point

Calculate coefficient

Generate approximate solution

Calculate statistical information of approximate solution

Expected valueVariance

EIWAC 201317

Generalized Polynomial Chaos• Example
Optimal control problem
5 random variables
Wind prediction errors
Airspeed measurement error
Current position estimation errors= 480 knots
40 NM• Control input: Bank angle• Objective function :Bank angle• Stochastic solution :Statistical information
Expected valueStandard deviation (Variance)

18

EIWAC 2013

Generalized Polynomial Chaos• Example
Generalized Polynomial Chaos
Total number ofcollocation pointsExpected valueStandard deviation

Computation time51

300.24 sec.

7.04 sec.

45 sec.

401

300.24 sec.

7.04 sec.

370 sec.

Monte Carlo Simulation
Total number ofsample points

Expected valueStandard deviation

Computation time

25000

300.21 sec.

7.08 sec.

5.5 hr.

EIWAC 2013

Trajectory Prediction• Time of arrival at merging pointA

Time of arrival
BMerging point

Probability density of time of arrival• Gaussian distribution

Expected value(Mean of the Gaussian)Standard deviation

1920

EIWAC 2013

Conflict Detection
Probability density• Conflict Probability at merging pointSafe separation(5 NM)= 600 knots
Time separation( = 30 sec.)time

Convolution integral

Time separation

EIWAC 2013

Simulation Results• Merging situations
Case 1• Without meteorological predictions
Case 2• With meteorological predictions
Provided by the Japan Meteorological Agency
51 collocation points for Generalized Polynomial Chaos
5 random variables• Wind prediction errors• Airspeed measurement error• Current position estimation errors

21

EIWAC 201322

Simulation Results• Without meteorological predictions
Case 1= 480 knots
AX NM

X = 80, 120, 160 NMMerging pointB
X + 5 NM
orX + 10 NM

EIWAC 2013

23

Simulation Results• 5 NM separation• 10 NM separation

24

EIWAC 2013

Simulation Results• 10 NM separation
X = 80 NM

X = 160 NM

Case 1

Mean

Standard deviation

80 NM

600.49 sec.

14.07 sec.

160 NM 1200.97 sec.

28.14 sec.

90 NM

675.55 sec.

15.83 sec.

170 NM 1276.03 sec.

29.90 sec.

Case 1

Mean

Standard deviation

25

EIWAC 2013

Simulation Results• 5 NM separation
X = 80 NM

X = 160 NM

Case 1

Mean

Standard deviation

80 NM

600.49 sec.

14.07 sec.

160 NM 1200.97 sec.

28.14 sec.

85 NM

638.02 sec.

14.95 sec.

165 NM 1238.50 sec.

29.02 sec.

Case 1

Mean

Standard deviation

EIWAC 2013

26

Simulation Results• 5 NM separation• 10 NM separation

EIWAC 201327

Simulation Results

Latitude• With meteorological predictions
Case 2
Merging point= 450 knots

Predicted wind velocity(140, 35.5)
A(138.5, 34.75)

B 25 NM C(139, 34.25)(139.5, 34.25)
Longitude

28

EIWAC 2013

Simulation Results• Case 2ABC

Case 2MeanStandard deviation

Case 2

Conflict Probability

Aircraft A

674.55 sec.

15.01 sec.

A–B

0.16687

Aircraft B

736.66 sec.

17.27 sec.

A–C

0.37491

Aircraft C

641.28 sec.

14.94 sec.

B–C

0.0076496

EIWAC 2013

Summary• Conflict detection in the merging situations
Probabilistic approach• Consider various uncertainties

Generalized Polynomial Chaos• Easy to implement• Reduce computational burden

Conflict probability at merging point• Time of arrival at merging point• Expected value and standard deviation

29

EIWAC 2013

Future Work• 3 dimensional space
Descent phase• Time-varying random variables
Increase the number of random variables• Conflict resolution
Use the information of conflict probability
Change time of arrival

30