QUAV: Quantum-Assisted Path Planning and Optimization for UAV Navigation with Obstacle Avoidance

Stellen Sie sich eine Drohne vor, die versucht, durch eine belebte Stadt zu fliegen, wobei sie zwischen Wolkenkratzern, Stromleitungen und Flugverbotszonen hindurchmanövriert, um ein Paket auszuliefern. Der Computer, der die Drohne steuert, muss in Echtzeit ständig die sicherste und kürzeste Route berechnen. Wenn die Anzahl der Hindernisse wächst, wird die Mathematik, die erforderlich ist, um den perfekten Pfad zu finden, für herkömmliche Computer überwältigend, da diese eine Möglichkeit nach der anderen prüfen müssen. Hier tritt ein neuer Zweig der Informatik auf den Plan: das Quantencomputing. Im Gegensatz zu Standardcomputern, die Informationen in einer linearen Sequenz von Nullen und Einsen verarbeiten, nutzen Quantenmaschinen die seltsamen Regeln der Physik, um viele Möglichkeiten gleichzeitig zu erforschen. Obwohl sich diese Maschinen noch in einem frühen Stadium befinden, sind Forscher bestrebt zu sehen, ob sie komplexe Navigationsprobleme lösen können, an denen konventionelle Systeme scheitern.

In einer kürzlich durchgeführten Studie stellte ein Team von Forschern der New York University Abu Dhabi und der Thales Group eine neue Methode namens QUAV vor, um diese Herausforderung anzugehen. Sie entwickelten ein System, das einen Quantenalgorithmus verwendet, genauer gesagt einen als Quantum Approximate Optimization Algorithm bekannten Algorithmus, um Flugpfade für Drohnen zu planen. Das Ziel war nicht, bestehende Navigationswerkzeuge sofort zu ersetzen, sondern zu testen, ob ein Quantenansatz in der Lage ist, sichere und effiziente Routen in Umgebungen voller Hindernisse zu generieren. Die Forscher behandelten die Reise der Drohne wie ein Puzzle, bei dem jedes mögliche Segment des Flugpfades ein Teil ist, das zusammengefügt werden muss, ohne gegen Barrieren zu stoßen.

Um dies umsetzbar zu machen, musste das Team die reale Welt zuerst in eine Sprache übersetzen, die der Quantencomputer verstehen kann. Sie begannen mit Standard-GPS-Koordinaten für den Startpunkt, das Ziel und die Standorte von Hindernissen wie Gebäuden oder Sperrzonen. Da GPS-Koordinaten der Erdoberfläche folgen und gekrümmt sind, konvertierten die Forscher sie in ein flaches, gitterartiges System namens Universal Transverse Mercator, das präzise Distanzberechnungen ermöglicht. Anschließend zeichneten sie einen digitalen Sicherheitspuffer um jedes Hindernis, wodurch eine größere „No-Go-Zone“ entstand, um sicherzustellen, dass die Drohne niemals zu nah herankommt. Der Raum zwischen Start- und Endpunkt wurde in ein Gitter potenzieller Wegpunkte unterteilt, und die Forscher kartierten jede mögliche Verbindung zwischen diesen Punkten, um ein riesiges Netzwerk potenzieller Routen zu erstellen.

Der Kern des QUAV-Systems besteht darin, die Reise in kleine Segmente aufzuteilen und jedem Segment ein einzelnes Quantenbit, oder Qubit, zuzuweisen. Die Forscher nutzten dann einen Quantenschaltkreis, um alle Kombinationen dieser Segmente gleichzeitig zu erforschen. Anstatt Routen nacheinander zu prüfen, evaluiert das Quantensystem die gesamte Landschaft der Möglichkeiten auf einmal und sucht nach der Kombination, die die Gesamtdistanz minimiert und dabei die Sicherheitsbereiche um die Hindernisse strikt vermeidet. Das System weist jeder Route, die einem Hindernis zu nahe kommt, eine hohe Strafe zu, was dem Computer effektiv beibringt, die Sicherheit zu priorisieren. Durch einen Prozess der iterativen Verfeinerung passt der Algorithmus seine internen Einstellungen an, um den Pfad mit den geringsten Gesamtkosten zu finden, wobei er die Notwendigkeit von Geschwindigkeit mit der absoluten Anforderung der Kollisionsvermeidung abwägt.

Die Forscher testeten diesen Ansatz in sechs verschiedenen Szenarien, die von offenen Räumen bis hin zu Gebieten mit dichten Clustern von Hindernissen reichten. Sie verglichen die Ergebnisse mit zwei bekannten klassischen Navigationsmethoden: einer, die den kürzesten Pfad garantiert, aber sehr langsam in der Berechnung sein kann, und einer anderen, die schnell ist, aber oft windungsreiche, ineffiziente Routen erzeugt. In Simulationen fanden die quantengestützten Systeme konsistent Pfade, die signifikant kürzer und direkter waren als die der schnellen klassischen Methode. Obwohl sie nicht immer die absolut kürzeste Distanz erreichten, die die langsamere, erschöpfendere klassische Methode fand, kamen sie der schnellen Alternative deutlich näher. In einigen komplexen Szenarien erzeugte das Quantensystem Pfade, die etwas mehr zickzackten als die ideale gerade Linie – ein Ergebnis der probabilistischen Natur des Quantencomputings, das mehrere gültige Optionen erforscht, anstatt einem einzigen deterministischen Pfad zu folgen.

Um zu beweisen, dass das System über Computersimulationen hinaus funktioniert, ließen die Forscher den Algorithmus auf einem echten Quantenprozessor laufen, speziell auf der IBM ibm_kyiv Maschine. Diese Hardware gehört zur aktuellen Generation von Quantencomputern, die noch anfällig für Fehler und Rauschen aus ihrer Umgebung sind. Die Ergebnisse zeigten, dass das System selbst mit diesen Unvollkommenheiten immer noch zu einer praktikablen Lösung konvergieren konnte. Die Kosten des Pfades schwankten aufgrund des Hardware-Rauschens stärker als in der Simulation, aber der Algorithmus reduzierte die Kosten erfolgreich und fand in jedem Testfall eine sichere Route. Die Forscher beobachteten, dass das System die physikalischen Beschränkungen der Maschine, wie etwa die begrenzte Anzahl an Verbindungen zwischen den Qubits, bewältigen konnte, indem es das Problem sorgfältig auf die verfügbare Hardware abbildete.

Die Studie kommt zu dem Schluss, dass dieser quantengestützte Ansatz ein praktikabler erster Schritt zur Nutzung von Quantencomputern für die reale Drohnennavigation ist. Das System demonstrierte, dass es machbare, kollisionsfreie Trajektorien generieren kann und dass seine Komplexität linear mit der Anzahl der Pfadsegmente skaliert, eine vielversprechende Eigenschaft für zukünftige Anwendungen. Während die aktuelle Hardware noch nicht leistungsstark genug ist, um die besten klassischen Computer in jeder Situation zu übertreffen, bestätigt die Forschung, dass die grundlegende Logik funktioniert. Die Ergebnisse legen nahe, dass diese Systeme, sobald die Quantenhardware besser und weniger verrauscht ist, schließlich die massiven, dynamischen Berechnungen bewältigen könnten, die für die Navigation autonomer Drohnenflotten in den komplexen Lufträumen von morgen erforderlich sind.