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

Stel je een drone voor die door een drukke stad probeert te vliegen, terwijl hij tussen wolkenkrabbers, stroomkabels en no-fly zones door manoeuvreert om een pakketje te bezorgen. De computer die de drone aanstuurt, moet in realtime constant de veiligste, kortste route berekenen. Naarmate het aantal obstakels groeit, wordt de wiskunde die nodig is om het perfecte pad te vinden overweldigend voor traditionele computers, die één mogelijkheid na de andere moeten controleren. Dit is waar een nieuwe tak van de informatica in beeld komt: quantum computing. In tegenstelling tot standaardcomputers, die informatie in een lineaire sequentie van enen en nullen verwerken, maken quantummachines gebruik van de vreemde regels van de natuurkunde om vele mogelijkheden tegelijkertijd te verkennen. Hoewel deze machines zich nog in een vroeg stadium bevinden, zijn onderzoekers vastberaden om te zien of ze complexe navigatieproblemen kunnen oplossen die conventionele systemen in de steek laten.

In een recente studie introduceerde een team onderzoekers van de New York University Abu Dhabi en Thales Group een nieuwe methode genaamd QUAV om deze uitdaging aan te pakken. Ze bouwden een systeem dat een quantumalgoritme gebruikt, specifiek een algoritme dat bekend staat als het Quantum Approximate Optimization Algorithm, om vliegroutes voor drones te plannen. Het doel was niet om bestaande navigatietools onmiddellijk te vervangen, maar om te testen of een quantumbenadering succesvol veilige, efficiënte routes kon genereren in omgevingen vol obstakels. De onderzoekers behandelden de reis van de drone als een puzzel waarbij elk mogelijk segment van het vliegpad een stukje was dat in elkaar moest passen zonder obstakels te raken.

Om dit werkend te krijgen, moest het team de echte wereld eerst vertalen naar een taal die de quantumcomputer kan begrijpen. Ze begonnen met standaard GPS-coördinaten voor het startpunt, de bestemming en de locaties van obstakels zoals gebouwen of verboden gebieden. Omdat GPS-coördinaten gebogen zijn om de aarde te volgen, hebben de onderzoekers ze omgezet naar een plat, rasterachtig systeem genaamd Universal Transverse Mercator, wat nauwkeurige afstandsberekeningen mogelijk maakt. Vervolgens tekenden ze een digitale veiligheidsbuffer rond elk obstakel, waardoor een grotere "no-go"-zone ontstond om ervoor te zorgen dat de drone nooit te dichtbij zou komen. De ruimte tussen het start- en eindpunt werd verdeeld in een raster van potentiële waypoints, en de onderzoekers brachten elke mogelijke verbinding tussen deze punten in kaart om een uitgebreid netwerk van potentiële routes te creëren.

De kern van het QUAV-systeem bestaat uit het opdelen van de reis in kleine segmenten en het toewijzen van elk segment aan een enkele quantumbit, of qubit. De onderzoekers gebruikten vervolgens een quantumcircuit om alle mogelijke combinaties van deze segmenten gelijktijdig te verkennen. In plaats van routes één voor één te controleren, evalueert het quantummechanisme het volledige landschap van mogelijkheden tegelijkertijd, op zoek naar de combinatie die de totale afstand minimaliseert terwijl de veiligheidsbuffers rond de obstakels strikt worden vermeden. Het systeem wijst een zware straf toe aan elke route die te dicht bij een obstakel komt, waardoor de computer effectief leert om veiligheid prioriteit te geven. Door een proces van iteratieve verfijning past het algoritme zijn interne instellingen aan om het pad met de laagste totale kosten te vinden, waarbij een balans wordt gezocht tussen snelheid en de absolute vereiste om niet te crashen.

De onderzoekers testten deze aanpak in zes verschillende scenario's, variërend van open ruimtes tot gebieden met dichte clusters van obstakels. Ze vergeleken de resultaten met twee bekende klassieke navigatiemethoden: één die de kortste route garandeert maar erg traag kan zijn om te berekenen, en een andere die snel is maar vaak kronkelige, inefficiënte routes produceert. In simulaties vond het quantum-ondersteunde systeem consequent paden die aanzienlijk korter en directer waren dan de snelle klassieke methode. Hoewel het niet altijd de absoluut kortste afstand bereikte die de tragere, meer uitputtende klassieke methode vond, kwam het veel dichterbij dan het snelle alternatief. In sommige complexe scenario's produceerde het quantum-systeem paden die iets meer zigzagden dan de ideale rechte lijn, een resultaat van de probabilistische aard van quantum computing, die meerdere geldige opties verkent in plaats van één enkel deterministisch pad te volgen.

Om te bewijzen dat het systeem ook buiten computer-simulaties werkte, draaide het team het algoritme op een echte quantumprocessor, specifiek de IBM ibm_kyiv machine. Deze hardware maakt deel uit van de huidige generatie quantumcomputers, die nog steeds gevoelig zijn voor fouten en ruis uit hun omgeving. De resultaten lieten zien dat het systeem, zelfs met deze imperfecties, nog steeds tot een levensvatbare oplossing kon komen. De kosten van het pad fluctueerden meer dan in de simulatie vanwege de hardwareruis, maar het algoritme slaagde erin de kosten te verlagen en vond in elke testcase een veilige route. De onderzoekers observeerden dat het systeem de fysieke beperkingen van de machine, zoals de beperkte verbindingen tussen qubits, kon afhandelen door het probleem zorgvuldig in kaart te brengen voor de beschikbare hardware.

De studie concludeert dat deze quantum-ondersteunde benadering een levensvatbare eerste stap is naar het gebruik van quantumcomputers voor navigatie van drones in de echte wereld. Het systeem toonde aan dat het in staat is om haalbare, botsingsvrije trajecten te genereren en dat de complexiteit ervan lineair schaalt met het aantal padsegmenten, een veelbelovende eigenschap voor toekomstige toepassingen. Hoewel de huidige hardware nog niet krachtig genoeg is om de beste klassieke computers in elke situatie te overtreffen, bevestigt het onderzoek dat de fundamentele logica werkt. De bevindingen suggereren dat, naarmate quantumhardware verbetert en minder ruisgevoelig wordt, deze systemen uiteindelijk de enorme, dynamische berekeningen kunnen afhandelen die nodig zijn voor autonome vloten van drones om door de complexe luchten van morgen te navigeren.