Polar Coordinate-based Differential Evolution for Moving Target Search Using Vision Sensor on Unmanned Aerial Vehicles

Stellen Sie sich vor, Sie spielen ein hochkarätiges Versteckspiel, aber die Person, die Sie suchen, läuft weg, die Karte ist riesig und Sie haben nur ein Fernglas, das verschwommen wird, wenn die Sonne zu hell oder der Wind zu stark ist. Dies ist die tägliche Realität von Such- und Rettungsteams, die versuchen, verlorene Wanderer oder Überlebende in Katastrophengebieten zu finden. In der Wissenschaft wird dies als „optimales Suchen“ bezeichnet – ein Rätsel, bei dem Computer versuchen herauszufinden, welchen Weg sie am besten nehmen sollen, damit sie keine kostbare Zeit verschwenden. Die Kernidee hierbei ist, dass die Zeit der Feind ist; je länger man sucht, desto schwieriger wird es, jemanden zu finden, da der Standort eher zu einer Vermutung als zu einem Fakt wird. Um dies zu lösen, verwenden Wissenschaftler „Drohnen“ (fliegende Roboter), die mit Kameras ausgestattet sind, aber das Programmieren dieser Drohnen für die perfekte Route ist unglaublich schwer, da die Drohnen physikalische Grenzen haben – sie können sich nicht augenblicklich drehen, sie haben eine maximale Geschwindigkeit und sie können nicht ewig fliegen.

Dieses Paper stellt einen cleveren neuen Weg vor, wie man Drohnen lehrt, nach beweglichen Zielen zu jagen, wie etwa einer verlorenen Person oder einem treibenden Überlebenden. Die Autoren, ein Team von Forschern aus Vietnam und Korea, haben einen neuen Algorithmus namens „Polar coordinate-based Differential Evolution“ (oder kurz PDE) entwickelt. Betrachten Sie dies als einen superintelligenten Trainer, der der Drohne nicht nur sagt, wohin sie fliegen soll, sondern auch, wie sie ihren Körper bewegen muss, um dorthin zu gelangen. Anstatt standardmäßige Kartenkoordinaten zu verwenden (wie „10 Meter nach rechts, dann 5 Meter hoch“), spricht der PDE-Algorithmus die Muttersprache der Drohne: „Drehe diesen Winkel und fliege diese Distanz.“ Auf diese Weise vermeidet die Drohne Sackgassen oder versucht, unmögliche Wendungen zu vollziehen. Die Forscher testeten diese Methode in Computersimulationen sowie mit einer echten Drohne auf einem Feld und fanden heraus, dass PDE besser darin war, das Ziel schneller zu finden als andere populäre Methoden, insbesondere wenn das Ziel sich bewegte und das Suchgebiet groß war.

Das Problem: Das Rennen gegen die „Goldene Zeit“

In der Suche und Rettung gibt es ein Konzept namens „goldene Zeit“. Dies ist das kurze Zeitfenster direkt nachdem jemand vermisst wurde, in dem die Chancen, ihn lebend zu finden, am höchsten sind. Während die Zeit abläuft, sinken die Chancen. Warum? Weil die Person sich bewegen könnte, der Wind sie wegdrücken könnte oder das Gelände sie verbergen könnte. Traditionelle Suchmethoden verlassen sich oft auf Teams am Boden oder bemannte Flugzeuge, die langsam oder gefährlich sein können. Hier kommt die Drohne (UAV) ins Spiel. Drohnen können über gefährliches Gelände sausen und Dinge sehen, die Menschen nicht sehen können. Aber hier ist der Haken: Wenn man einer Drohne einfach nur sagt, sie solle zufällig fliegen, könnte sie das Ziel verpassen. Wenn man ihr sagt, sie solle in einem perfekten Raster fliegen, verschwendet sie vielleicht Zeit, indem sie über leere Stellen fliegt. Das Ziel ist es, den perfekten Flugpfad zu finden, der die Chance maximiert, das Ziel so schnell wie möglich zu entdecken.

Das Gehirn: Wie die Drohne „denkt“

Um den besten Pfad zu finden, benötigt die Drohne ein Gehirn, das vorhersagen kann, wo sich das Ziel befinden könnte. Die Autoren modellierten die Bewegung des Ziels wie einen „Markov-Prozess“. Einfach ausgedrückt bedeutet dies, dass die nächste Bewegung des Ziels hauptsächlich davon abhängt, wo es gerade ist und wie es sich bewegt, und nicht davon, wo es vor einer Stunde war. Es ist wie die Vorhersage eines Blattes, das einen Fluss hinuntertreibt; man kennt die Strömungsrichtung, also kann man erraten, wo es in ein paar Sekunden sein wird.

Die Drohne muss auch wissen, wie gut ihre „Augen“ sind. Das Paper verwendet ein Modell namens NVESD, um die Wahrscheinlichkeit zu berechnen, das Ziel zu entdecken. Dabei geht es nicht nur darum, wie weit das Ziel entfernt ist; es geht um die Qualität des Bildes. Wenn die Sonne blendet oder das Ziel klein und unscharf ist, sinkt die Chance, es zu sehen. Der Algorithmus kombiniert diese beiden Dinge – wo das Ziel sein könnte und wie wahrscheinlich die Kamera es sehen kann – um eine „Belief Map“ (Glaubenskarte) zu erstellen. Diese Karte ist wie eine Heatmap, bei der die hellsten Stellen die höchste Wahrscheinlichkeit anzeigen, dass das Ziel dort zu finden ist.

Die Lösung: Der Polar-Koordinaten-Trick

Die Kerninnovation dieses Papers ist die Art und Weise, wie die Drohne ihren Flugpfad plant. Die meisten Computeralgorithmen verwenden „kartesische Koordinaten“, die wie ein Gitter auf Graphpapier sind (x- und y-Werte). Während das für die Mathematik funktioniert, ist es für Drohnen schrecklich. Wenn eine Drohne fliegt und wenden muss, berechnet ein kartesischer Algorithmus vielleicht einen Pfad, der von der Drohne verlangt, sich augenblicklich im Kreis zu drehen oder schneller zu fliegen, als ihr Motor es erlaubt. Es ist, als würde man einem Auto sagen: „Bewege dich 5 Meter nach Norden und 5 Meter nach Osten“, ohne zu berücksichtigen, dass das Auto einen minimalen Wendekreis hat.

Die Autoren schlugen vor, stattdessen „Polarkoordinaten“ zu verwenden. Anstatt zu sagen „Fliege zum Punkt (x, y)“, sagt der Algorithmus der Drohne: „Fliege diese Distanz ($\rho$) bei diesem Winkel ($\psi$).“ Dies entspricht der Art und Weise, wie sich die Drohne tatsächlich bewegt. Durch die Verwendung dieser Methode respektiert der Algorithmus auf natürliche Weise die physikalischen Grenzen der Drohne. Er kann keine Wendung vorschlagen, die zu scharf oder eine Geschwindigkeit, die zu hoch ist, weil die Mathematik von Anfang an um diese Grenzen herum aufgebaut ist.

Sie betetteten diese Idee in einen „Differential Evolution“ (DE) Algorithmus ein. DE ist eine Art von „Schwarmintelligenz“, die wie ein Team von Entdeckern funktioniert. Stellen Sie sich eine Gruppe von Wanderern vor, die versuchen, den höchsten Gipfel in einem nebligen Gebirge zu finden. Sie kennen die ganze Karte nicht, aber sie tauschen sich aus. Wenn ein Wanderer einen hohen Punkt findet, bewegen sich die anderen in Richtung dieses Gebiets, versuchen aber auch leicht andere Richtungen, um zu sehen, ob sie etwas noch Höheres finden können. Der „Differentielle“ Teil bedeutet, dass sie sich die Differenz zwischen dem Standort zweier Wanderer ansehen, um zu entscheiden, in welche Richtung sie als Nächstes springen sollen.

Die Autoren kombinierten diese Schwarmintelligenz mit ihrem Polarkoordinatensystem. Sie nennen sie PDE. In ihren Simulationen erkundete dieses Team virtueller Drohnen das Suchgebiet viel effizienter als Teams, die Standardmethoden verwendeten.

Die Ergebnisse: Simulationen und echte Flüge

Die Forscher testeten ihren PDE-Algorithmus in sechs verschiedenen Szenarien, die von kleinen Gebieten von 600 m x 600 m bis hin zu massiven Zonen von 2000 m x 2000 m reichten. Sie verglichen PDE mit anderen berühmten Algorithmen wie Particle Swarm Optimization (PSO), Genetic Algorithms (GA) und dem Standard-Differential Evolution (DE).

In den Computersimulationen fand PDE konsequent das Ziel mit einer höheren Wahrscheinlichkeit und tat dies schneller. In einem Szenario erreichte PDE beispielsweise eine Detektionswahrscheinlichkeit von etwa 0,529, während der Standard-DE-Algorithmus nur 0,410 erreichte. Das Paper merkt an, dass der Standard-DE oft in „lokalen Optima“ stecken blieb – das heißt, er fand einen guten Punkt, konnte aber nicht den besten Punkt sehen, weil er in einer Schleife feststeckte. PDE war dank seiner Polarkoordinaten besser darin, aus diesen Schleifen auszubrechen und den global besten Pfad zu finden.

Sie hörten nicht bei Computerspielen auf. Sie nahmen eine echte 3DR Solo Drohne mit in ein Feld, um die Theorie zu testen. Die Drohne wurde mit dem PDE-Pfad programmiert und über ein 80 m x 80 m großes Gebiet geflogen. Eine Person (das Ziel) ging mit einer Geschwindigkeit von 1,5 m/s. Die Drohne folgte dem vom Algorithmus generierten Pfad, und der Pfad, den sie tatsächlich flog, entsprach dem Plan sehr genau. Die Drohne flog erfolgreich über den Bereich, in dem das Ziel erwartet wurde, und die Kamera erfasste die Person. Die Autoren merken an, dass der Test in der realen Welt zwar erfolgreich war, aber darauf basierte, dass sich das Ziel exakt wie vorhergesagt bewegte. In einer echten Katastrophe sind die Dinge chaotischer, aber der Test bewies, dass der Algorithmus Pfade generiert, die echte Drohnen tatsächlich fliegen können.

Warum es wichtig ist

Das Paper legt nahe, dass wir durch das Sprechen der Sprache der Drohne (Polarkoordinaten) und die Verwendung einer smarten, teambasierten Suchstrategie Such- und Rettungseinsätze effektiver gestalten können. Der PDE-Algorithmus findet nicht nur einen Pfad; er findet einen machbaren Pfad, der die Grenzen der Drohne respektiert und gleichzeitig die Chance auf eine Rettung maximiert. Obwohl die Autoren zugeben, dass eine einzelne Drohne aufgrund der Akkulaufzeit nur ein begrenztes Gebiet abdecken kann, schlagen sie vor, dass diese Methode die Grundlage für eine Flotte von Drohnen bilden könnte, die in Zukunft zusammenarbeiten. Für den Moment ist dies ein bedeutender Schritt in Richtung intelligenterer, schnellerer und hilfreicherer fliegender Roboter, wenn jede Sekunde zählt.