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.

  • News and Highlights
    • STRIPS-HGN: First algorithm capable of learning domain-independent heuristics from scratch (ICAPS'20).
    • New insights and results for ASNets on arXiv (still under review)
    • Guiding search using generalized policies from ASNets (SoCS'19)
    • PLTL-dual: First heuristic search algorithm for SSPs and MDPs with Probabilistic LTL constraints (KR'18).
    • ASNets: Learning generalized policies for SSPs using neural nets (AAAI'18).
    • h-pom, h-roc, and i2-dual won the best paper award at ICAPS'17!
    • New efficient approach to solve SSPs and C-SSPs with dead ends (UAI'17).
    • h-pom and h-roc: the first heuristics able to handle probabilities and costs for SSPs and C-SSPs (ICAPS'17).
    • i-dual won the best paper award at ICAPS'16!
    • QTM won the Kikuchi-Karlaftis best paper award at TRB'16! (demo).
  • Word cloud of my papers
  • wordcloud
    large wordcloud