Heuristic Variants for A* Search in 3D Flight Planning

Anders Nicolai Knudsen, Marco Chiarandini, Kim Skak Larsen

Publikation: Kapitel i bog/rapport/konference-proceedingKonferencebidrag i proceedingsForskningpeer review

207 Downloads (Pure)

Abstrakt

A crucial component of a flight plan to be submitted for approval to a control authority in the pre-flight phase is the prescription of a sequence of airways and airway points in the sky that an aircraft has to follow to cover a given route. The generation of such a path in the 3D network that models the airways must respect a number of constraints. They generally state that if a set of points or airways is visited then another set of points or airways must be avoided or visited. Paths are then selected on the basis of cost considerations. The cost of traversing an airway depends, directly, on fuel consumption and on traversing time, and, indirectly, on weight and on weather conditions. Path finding algorithms based on A* search are commonly used in automatic planning. However, the constraints and the dependency structure of the costs invalidate the classic domination criterion in these algorithms. A common approach to tackle the increased computational effort is to decompose the problem heuristically into a sequence of horizontal and vertical route optimizations. Using techniques recently designed for the simplified 2D context, we address the 3D problem directly. We compare the direct approach with the decomposition approach. We enhance both approaches with ad hoc heuristics that exploit the expected appeal of routes to speed-up the solution process. We show that, on data resembling those arising in the context of European airspaces, the direct approach is computationally practical and leads to results of better quality than the decomposition approach.

OriginalsprogEngelsk
TitelIntegration of Constraint Programming, Artificial Intelligence, and Operations Research : 15th International Conference, CPAIOR 2018, Delft, The Netherlands, June 26–29, 2018, Proceedings
RedaktørerWillem-Jan van Hoeve
ForlagSpringer
Publikationsdato2018
Udgave1
Sider361-376
ISBN (Trykt)978-3-319-93030-5
ISBN (Elektronisk)978-3-319-93031-2
DOI
StatusUdgivet - 2018
Begivenhed15th International Conference on the Integration of Constraint Programming, Artificial Intelligence, and Operations Research - Delft, Holland
Varighed: 26. jun. 201829. jun. 2018

Konference

Konference15th International Conference on the Integration of Constraint Programming, Artificial Intelligence, and Operations Research
LandHolland
ByDelft
Periode26/06/201829/06/2018
NavnLecture Notes in Computer Science
Vol/bind10848
ISSN0302-9743

Fingeraftryk

Dyk ned i forskningsemnerne om 'Heuristic Variants for A* Search in 3D Flight Planning'. Sammen danner de et unikt fingeraftryk.

Citationsformater