Sicherer Flugzeug- und Drohnenverkehr

Team-up mit Thales: Optimale Drohnenpfade durch die Raumzeit finden

Wie Quantencomputer ihre neuen Geschäftsmodelle zum Fliegen bringen können, wollte auch die Thales Group wissen. Ihre Air-Traffic-Management-Systeme sorgen für eine sichere und effiziente Bewegung von Flugzeugen während aller Phasen des Betriebes. Doch neben Flugzeugen werden künftig auch immer mehr Drohnen den Himmel erobern. Von Flugtaxis über Moni­toring- bis Lieferdrohnen, die eilige Medikamente liefern, ist das Potenzial riesig. Um auch die neuen Flugobjekte im Blick zu behalten, will Thales sein Geschäftsmodell ausweiten. Aber den neuen Herausforderungen sind die bisher erprobten Systeme nicht gewachsen: Neben den optimalen Flugrouten müssen Flugverbotszonen und -zeiten mitberechnet sowie Kollisionen vermieden werden – und das für eine Vielzahl von Drohnen. Neue Methoden sind also gefragt. Daher wendete sich Thales an das Team von Dr. Nico Piatkowski am Fraunhofer- Institut für Intelligente Analyse- und Informations-systeme IAIS in Sankt Augustin bei Bonn.

»Das Bestimmen der kürzesten Wege ist heute Grund­lage jedes Navigationssystems. Doch sobald mehrere da­von gefunden werden sollen, die auch noch miteinander interagieren, kommen klassische Computer schnell an ihre Grenzen. In unserem Szenario ist die Anzahl mög­licher Interaktionen hoch, da die Drohnen nicht mitein­ander oder mit Gebäuden kollidieren dürfen. Mit Quan­tencomputern können wir solche Interaktionen direkt in die Qubits einkodieren«, erklärt der Informatiker. Für Thales formalisierte er mit seinem Team zunächst die Fra­gestellung mitsamt allen relevanten Faktoren mathema­tisch. Aus einer Geodatenbank mit Höheninformationen extrahierten sie ein 3D-Modell von Bonn, ergänzt um die vierte Dimension der Zeit. In diesem Graphen modellier­ten sie die verschiedenen möglichen Wege mehrerer Droh­nen als schlauchartige Räume, um gleiche Wege zu ver­meiden. Das Problem: Allein über der Innenstadt von Bonn gäbe es mehr als 1,2 Millionen Knoten, also Orte, an denen sich eine Drohne theoretisch aufhalten könnte. Für der­zeitige Quantencomputer ist das viel zu groß.

Daher entlasten die Forschen­den den Quantenrechner um Auf­gaben, die klassische Rechner oh­nehin sehr gut können: »Wir setzen die Start- und Zielpunkte fest und lassen einen klassischen Computer die kürzesten Routen berechnen. Aus diesen vorausge­wählten Wegen muss dann der Quantencomputer nur noch die Routen ohne Kollisionen heraus­finden. Er zieht also nicht mehr 1,2 Millionen Punkte in Betracht, sondern muss nur noch ein paar hundert Wege berücksichtigen.« Das Quantenergebnis wird dann wieder von einem klassischen Al­gorithmus geprüft und wenn es trotzdem noch Kollisionen gibt, kann die Menge an Pfadmöglich­keiten erweitert werden. »Ein entscheidender Punkt ist also herauszufinden, welcher Teil des Problems sich für einen Quantencomputer eignet und welcher nicht«, be­tont Dr. Nico Piatkowski.

Für ihre Berechnungen verglichen die Forschenden einen Simulated-Annealing-Software-Algorithmus, einen D-Wave-Quantencomputer, und die an ihrem Institut patentierte Hardware »IAIS Evo Annealer«, die die Funk­tionsweise eines Quantencomputers nachbildet. Damit lässt sich deutlich effizienter als bisher möglich prüfen, inwiefern sich spezifische mathematische Probleme künf­tig mit Quantencomputing lösen lassen. »Wir erzielen für ein Beispiel mit zwanzig Drohnen in einem eingeschränk­ten Gebiet bereits profitable Ergebnisse auf beiden Sys­temen, mit null Kollisionen und der bestmöglichen Weglänge«, freut sich Piatkowski. Damit konnten die For­schenden zeigen, dass sich das Drone-Path-Finding-Pro­blem mithilfe von Qubits lösen lässt. Im nächsten Schritt soll der entworfene Quantenalgorithmus auf weiteren Quantencomputern getestet werden.