Optimal and Heuristic Approaches for Constrained Flight Planning under Weather Uncertainty
Geisser, F., Poveda, G., Trevizan, F., Bondouy, M., Teichteil-Königsbuch, F. and Thiébaux, S.
To appear in Proc. of 30th Int. Conf. on Automated Planning and Scheduling (ICAPS).
We are working on the camera-ready of this paper and it will be available soon.
Bellow is the abstract of this paper.
Aircraft flight planning is impacted by weather uncertainties. Existing
approaches to flight planning are either deterministic and load additional
fuel to account for uncertainty, or probabilistic but have to plan in 4D
space. If constraints are imposed on the flight plan these methods provide
no guarantees that the constraints are actually satisfied. We investigate
constrained flight planning under weather uncertainty on discrete airways
graphs and model this problem as a Constrained Stochastic Shortest Path
(C-SSP) problem. Transitions are generated on-the-fly by the underlying
aircraft performance model. As this prevents us from using off-the-shelf
C-SSP solvers, we generalise column-generation methods stemming from
constrained deterministic path planning to the probabilistic case. This
results in a novel method which is com- plete but computationally expensive.
We therefore also discuss deterministic and heuristic approaches which
average over weather uncertainty and handle constraints by scalarising a
multi-objective cost function. We evaluate and compare these approaches on
real flight routes subject to real weather forecast data and a realistic
aircraft performance model.