Richtungsbewusster und selbstanpassender A*-Algorithmus mit PPO-Heuristik zur UAV-Wegplanung in der Smart City

Intelligentere Routen für Stadtdrohnen

Stellen Sie sich Flotten kleiner Lieferdrohnen vor, die zwischen Wolkenkratzern hindurchschwirren und Medikamente, Pakete oder Notfallmaterial durch eine belebte Stadt transportieren. Um sicher und schnell zu fliegen, muss jede Drohne ständig entscheiden, wohin sie als Nächstes fliegt. Dieses Papier stellt einen neuen Ansatz vor, mit dem Drohnen in überfüllten dreidimensionalen Stadtbereichen bessere Routen finden können, sodass ihre Wege kürzer, gleichmäßiger und verlässlicher werden als bei traditionellen Methoden.

Warum die Wegfindung so schwierig ist

Für eine Drohne ist die Wahl eines Pfades mehr als nur das Ziehen einer Geraden von Punkt A nach Punkt B. Sie muss Gebäude, Bäume und Sperrgebiete umfliegen und dabei Begrenzungen für Wendungen und Flughöhen einhalten. Klassische Verfahren zur Wegplanung, wie der bekannte A*-Algorithmus, funktionieren auf vereinfachten Karten gut, haben aber in realistischen 3D‑Stadtumgebungen Schwierigkeiten. Sie prüfen oft zu viele mögliche nächste Schritte, verschwenden Rechenleistung und können zackige Routen erzeugen, die länger sind als nötig oder in sehr dicht besiedelten Umgebungen sogar scheitern. Mit dem Wachstum komplexer Smart Cities werden diese Schwächen zu einem ernsthaften Engpass für sicheren und effizienten Luftverkehr.

Ein richtungsbewusster Ausbau eines klassischen Werkzeugs

Die Autoren bauen auf dem A*-Algorithmus auf und schlagen eine verbesserte Variante namens DASA* (Direction‑Aware and Self‑Adaptive A*) vor. Anstatt blind in alle Richtungen um die Drohne herum zu suchen, richtet DASA* die Aufmerksamkeit darauf, wo sich das Ziel befindet. Er klassifiziert nahegelegene Kandidatenpositionen in drei Ebenen: solche überwiegend vor der Drohne in Richtung des Ziels, seitliche Positionen und eine kleine Menge hinter ihr, die helfen können, aus Sackgassen zu entkommen. Ein einfacher Stillstandsdetektor erkennt, wenn die Suche „steckenzubleiben“ droht, und erweitert dann automatisch die Suche von einem schmalen Vorwärtskegel auf eine umfassendere Nachbarschaft, wenn nötig. Diese vorsichtige, zum Ziel hin ausgerichtete Expansion reduziert verschwendete Erkundung, während sie dennoch garantiert, dass eine gültige Route gefunden wird, falls eine existiert.

Anpassung an überfüllte und offene Räume

Ein weiteres zentrales Merkmal von DASA* ist, dass es seine Schrittweite an die Umgebung anpasst. Befindet sich die Drohne weit von Hindernissen, macht der Algorithmus größere Schritte und überbrückt offene Flächen schnell. Nähert er sich Gebäuden oder anderen Gefahren, wechselt er zu kleineren Schritten, um präzises Manövrieren in engen Lücken zu erlauben. Diese variable „Zoom‑Stufe“ erlaubt es dem Planer, dort schnell zu sein, wo es sicher ist, und nur dort zu verlangsamen, wo Genauigkeit wichtig ist. Nachdem ein roher Pfad gefunden wurde, entfernt eine spezielle Nachbearbeitungsstufe unnötige Wegpunkte und legt eine glatte Kurve durch die verbleibenden Schlüsselpunkte. Das Ergebnis ist eine Route, die nicht nur Kollisionen vermeidet, sondern auch eher wie ein natürlicher Flugweg wirkt, den ein geübter Pilot wählen würde, mit weniger abrupten Wendungen.

Dem Algorithmus vorausschauendes Denken beibringen

Der traditionelle A* stützt sich auf einfache Distanzformeln, um abzuschätzen, wie weit jede Position vom Ziel entfernt ist. DASA* ersetzt dieses Schätzen durch eine gelernte Anleitung, basierend auf Proximal Policy Optimization (PPO), einer modernen Verstärkungslern‑Technik. In einer Trainingsumgebung übt ein virtueller Agent wiederholt, sich in 3D‑Raum einem Ziel zu nähern, wobei er Entfernungen, Höhendifferenzen und Richtungsinformationen wahrnimmt. Ein neuronales Netzwerk lernt allmählich, wie vielversprechend jede Situation ist, und dient nach dem Training als einsteckbares „Intuitionsmodul“ für DASA*. Diese gelernte Heuristik lenkt die Suche direkter zu guten Lösungen, besonders in komplexen Layouts, in denen einfache Luftlinienentfernungen irreführend sind.

Wie gut es in virtuellen Städten funktioniert

Die Forschenden testeten DASA* in mehreren simulierten 3D‑Stadtszenarien, gefüllt mit kastenförmigen Gebäuden und zylindrischen Hindernissen, die reale städtische Strukturen nachahmen. Sie verglichen es mit dem klassischen A* und mehreren populären Alternativen, darunter verbesserte Versionen von Rapidly‑Exploring Trees, Partikelschwärmen, Differential Evolution und einer weiteren A*-Variante namens Theta*. In vielen Testfällen fand DASA* durchweg kürzere Pfade, erweiterte deutlich weniger Kandidatenpunkte und lief wesentlich schneller – oft 10‑ bis 50‑mal schneller als der standardmäßige A*. Es hielt außerdem eine perfekte oder nahezu perfekte Erfolgsrate selbst in dichten, labyrinthartigen Umgebungen aufrecht, während einige konkurrierende Methoden häufiger scheiterten oder lange, schleifenartige Umwege produzierten.

Was das für den Alltag bedeutet

Einfach gesagt gibt DASA* fliegenden Robotern ein besseres Gespür für Richtung und Urteilsvermögen. Indem es sich auf vielversprechende Richtungen konzentriert, den Detaillierungsgrad an die lokale Umgebung anpasst, ein gelerntes Gespür dafür nutzt, wie nah man dem Erfolg ist, und die endgültige Route verfeinert, verwandelt es rohe Kartendaten in Flugwege, die effizient, geschmeidig und praktisch sind. Wenn ein solcher Ansatz in realen Systemen eingesetzt wird, könnte er zukünftigen Smart Cities helfen, Lieferungen per Drohne, Inspektionen und Rettungseinsätze sicherer und zuverlässiger zu organisieren, selbst wenn der Luftraum dichter und die Umgebungen komplexer werden.

Zitation: Zhang, X., Tan, L. & Chai, J. Direction aware and self-adaptive A* algorithm with PPO heuristic for UAV path planning of smart city. Sci Rep 16, 6174 (2026). https://doi.org/10.1038/s41598-026-36066-4

Schlüsselwörter: UAV-Wegplanung, Drohnen in Smart Cities, A*-Algorithmus, autonome Navigation, Roboterbewegungsplanung