elib
DLR-Header
DLR-Logo -> http://www.dlr.de
DLR Portal Home | Imprint | Privacy Policy | Contact | Deutsch
Fontsize: [-] Text [+]

Quantum Annealing Applied to De-Conflicting Optimal Trajectories for Air Traffic Management

Stollenwerk, Tobias and O'Gorman, Bryan and Venturelli, Davide and Mandrà, Salvatore and Rodionova, Olga and Ng, Hok K. and Sridhar, Banavar and Rieffel, Eleanor G. and Biswas, Rupak (2018) Quantum Annealing Applied to De-Conflicting Optimal Trajectories for Air Traffic Management. IEEE Transactions on Intelligent Transportation Systems, pp. 1-13. IEEE - Institute of Electrical and Electronics Engineers. DOI: 10.1109/TITS.2019.2891235 ISBN 1558-0016 ISSN 1524-9050

[img] PDF - Postprint version (accepted manuscript)
1MB

Abstract

We present the mapping of a class of simplified air traffic management (ATM) problems (strategic conflict resolution) to quadratic unconstrained boolean optimization (QUBO) problems. The mapping is performed through an original representation of the conflict-resolution problem in terms of a conflict graph, where nodes of the graph represent flights and edges represent a potential conflict between flights. The representation allows a natural decomposition of a real world instance related to wind- optimal trajectories over the Atlantic ocean into smaller subproblems, that can be discretized and are amenable to be programmed in quantum annealers. In the study, we tested the new programming techniques and we benchmark the hardness of the instances using both classical solvers and the D-Wave 2X and D-Wave 2000Q quantum chip. The preliminary results show that for reasonable modeling choices the most challenging subproblems which are programmable in the current devices are solved to optimality with 99% of probability within a second of annealing time.

Item URL in elib:https://elib.dlr.de/117108/
Document Type:Article
Title:Quantum Annealing Applied to De-Conflicting Optimal Trajectories for Air Traffic Management
Authors:
AuthorsInstitution or Email of AuthorsAuthors ORCID iD
Stollenwerk, Tobiastobias.stollenwerk (at) dlr.dehttps://orcid.org/0000-0001-5445-8082
O'Gorman, BryanQuantum Artifcial Intelligence Laboratory (QuAIL), NASA Ames Research Center, Moffett Field, CA 94035UNSPECIFIED
Venturelli, DavideQuantum Artifcial Intelligence Laboratory (QuAIL), NASA Ames Research Center, Moffett Field, CA 94035UNSPECIFIED
Mandrà, SalvatoreQuantum Artifcial Intelligence Laboratory (QuAIL), NASA Ames Research Center, Moffett Field, CA 94035UNSPECIFIED
Rodionova, OlgaNASA Ames Research Center, Moffett Field, CA 94035UNSPECIFIED
Ng, Hok K.NASA Ames Research Center, Moffett Field, CA 94035UNSPECIFIED
Sridhar, BanavarNASA Ames Research Center, Moffett Field, CA 94035UNSPECIFIED
Rieffel, Eleanor G.Quantum Artifcial Intelligence Laboratory (QuAIL), NASA Ames Research Center, Moffett Field, CA 94035UNSPECIFIED
Biswas, RupakQuantum Artifcial Intelligence Laboratory (QuAIL), NASA Ames Research Center, Moffett Field, CA 94035UNSPECIFIED
Date:2018
Journal or Publication Title:IEEE Transactions on Intelligent Transportation Systems
Refereed publication:Yes
Open Access:Yes
Gold Open Access:No
In SCOPUS:Yes
In ISI Web of Science:Yes
DOI :10.1109/TITS.2019.2891235
Page Range:pp. 1-13
Publisher:IEEE - Institute of Electrical and Electronics Engineers
ISSN:1524-9050
ISBN:1558-0016
Status:Published
Keywords:Computer Science - Data Structures and Algorithms, Quantum Physics, Quantum Computing
HGF - Research field:Aeronautics, Space and Transport
HGF - Program:Space
HGF - Program Themes:Space Technology
DLR - Research area:Raumfahrt
DLR - Program:R SY - Technik für Raumfahrtsysteme
DLR - Research theme (Project):R - Quantencomputing
Location: Köln-Porz
Institutes and Institutions:Institut of Simulation and Software Technology > High Performance Computing
Deposited By: Stollenwerk, Tobias
Deposited On:14 Dec 2018 10:31
Last Modified:21 Oct 2019 11:43

Repository Staff Only: item control page

Browse
Search
Help & Contact
Information
electronic library is running on EPrints 3.3.12
Copyright © 2008-2017 German Aerospace Center (DLR). All rights reserved.