Tech News: So funktioniert automatische Routenplanung

Germandrones bereitet ein Plug-In für seine Bodenstation vor, das automatisch Routen plant und Hindernisse wie Geofences und Berge berücksichtigt. Wie funktioniert das? Und was sind die Vorteile?

Das Erstellen einer Flugroute ist ein komplexer Prozess. Neben dem Verbinden von Punkten auf einer zweidimensionalen Karte kommen beim Betrieb einer Starrflügel-Drohne Aspekte wie Energieverbrauch, maximal zulässige Höhe, minimale Bodenfreiheit, Steig- oder Sinkgradienten und Wenderadien ins Spiel. Germandrones entwickelt eine Erweiterung zu seiner Bodenkontroll-Software, die einen sicheren Flugweg zwischen festgelegten Start- und Endpunkten ermitteln kann. Sie wird derzeit in verschiedenen Projekten getestet und für den Praxiseinsatz vorbereitet.

Der Benutzer platziert lediglich zwei Markierungen in der Karte und wählt einige Parameter aus, die bestimmen, wie die Punkte verbunden werden (minimal und maximal zulässige Höhen usw.). Wenn man bedenkt, dass eine von Hand durchgeführte Routenplanung leicht 10 – 15 Minuten dauern kann, während der Zusammenbau der Songbird-Drohne selbst nur zweieinhalb Minuten benötigt, liegt hier ein enormes Potential und eine wertvolle Ergänzung für jeden zeitkritischen Anwendungsfall wie z. B. Emergency Response. Das Tool berücksichtigt alle Informationen wie Geofences, das Höhenprofil des Geländes und die Fähigkeiten der Drohne.

Als Ergebnis wird eine Reihe von Wegpunkten mit den entsprechenden Koordinaten und Höhenwerten generiert. Die Arbeit dieses Tools ist in einen Generierungs- und einen Prüfprozess unterteilt und somit für zukünftige Erweiterungen gerüstet.

Im Kern der Software wird eine Pathfinding Methode benötigt. Klassische Ansätze wie der Algorithmus von Dijkstra sind nicht geeignet, da sie eine diskretisierte Menge von Knoten benötigen. Im vorliegenden Fall wurde ein stichprobenbasierter Planungsalgorithmus, genauer der Rapidly Exploring Random Tree Star Smart (RRT*-SMART) verwendet, der für nicht-konvexe, mehrdimensionale Suchräume geeignet ist. Dieser erstellt zuerst Knoten, indem er zufällig einen raumfüllenden Baum generiert. In weiteren Schritten wird der Baum gezielt verfeinert und zusätzliche Schritte folgen nachträglich zur Optimierung der resultierenden Route.

Der RRT-Algorithmus kann zuverlässig Lösungen generieren, auch wenn er je nach verfügbarer Rechenzeit nicht immer das Optimum hervorbringt. Der Hauptvorteil der RRT*-Version ist eine verbesserte Optimierung des endgültigen Pfads bei gleichzeitiger Gewährleistung einer schnellen Konvergenz zu dieser Lösung. Mit der Wahl von RRT*-SMART zielt unsere Software darauf ab, im Vergleich zu anderen RRT-Versionen optimale hindernisfreie Wege in kürzerer Ausführungszeit zu erzeugen. Sie kann daher problemlos über kurze oder lange Distanzen mit komplizierten Konfigurationen und zusätzlichen Hardwareanforderungen verwendet werden.

Die Vermeidung von Geofences (egal ob kreisförmig oder polygonal) ist sowohl für Wegpunkte als auch für den Raum dazwischen garantiert. Mit anderen Worten, wir stellen sicher, dass sich kein Wegpunkt innerhalb eines Geofence befindet und dass die Verbindungslinie zwischen zwei Punkten keinen Geofence verletzt. Dies geschieht in jedem Schritt des Algorithmus, ohne gleichzeitig dessen Komplexität zu erhöhen.

Darüber hinaus stellt die Software während der Routenfindung sicher, dass alle Höhenänderungen für unsere Songbird-Modelle fliegbar sind. Dies betrifft die maximal möglichen Steig- und Sinkraten der Drohne.

Zusätzlich berücksichtigt unser Planungstool untere und obere Höhengrenzen, z.B. bei einer eingeschränkten Fluggenehmigung innerhalb des Luftraums. Diese Funktion kann viel Zeit beim Missionsdesign in komplexem Gelände sparen, wo ggf. zusätzliche strenge Höhenbeschränkungen gelten.

Dennoch haben sich die letzten beiden Sicherheitsmechanismen für den Algorithmus in einigen Fällen als stark restriktiv erwiesen. Eine Kombination aus anspruchsvollem Gelände mit einem eingeschränkten Höhenprofil macht es schwierig, sichere Bereiche zu bestimmen, in denen die Drohne alle Höhenänderungen problemlos durchführen kann. Um dies ohne deutlich verlängerte Ausführungszeit des Algorithmus zu bewältigen, wurden spezielle Ansätze verwendet. Die wichtigsten waren ein intelligentes Wegpunkt-Sampling in leicht zugänglichen Teilen des Gebiets und eine allgemeine Philosophie der minimalen Höhenänderungen während der Mission.

Letztendlich kann das automatische Missionsplanungstool in verschiedenen Geländearten für das Fliegen von kurzen oder langen Missionen zeitsparend verwendet werden. Es enthält die erforderlichen Softwarekomponenten, um sicherzustellen, dass Routen zügig generiert werden, sicher sind und dass das Tool ohne zusätzliche Unterstützung des Nutzers einfach in der GCS eingesetzt werden kann.

 

Ihr Ansprechpartner:

Dr. Klaus Scho, Geschäftsführer

Tel. + 49 (0)30 34 78 12 81

Zurück
Screenshot of a of a flight route planned automatically in the Germandrones Ground Station
Beispiel einer automatisch erzeugten Flugroute
Illustration of the algorithm’s path finding procedure
Illustration der Weg-Findungs-Prozedur