-
Die
Erfindung betrifft ein Verfahren zur Routenbestimmung oder Routenplanung,
insbesondere zur Bestimmung einer Route für ein Fluggerät.
Hierbei zielt die Erfindung darauf ab, die Routenplanung mit einem
möglichst geringen Rechenzeitaufwand durchzuführen.
-
Auf
der Route für ein Fahrzeug (beispielsweise Flugzeug, UAV – unmanned
aerial vehicle, Automobil, Schiff oder U-Boot) können neben
dem Anfangs- und Zielpunkt weitere Wegpunkte vorhanden sein. Zwischen
den einzelnen Wegpunkten existieren häufig mehrere mögliche
Verbindungsstrecken, die unterschiedliche Kosten haben. Die Kosten
stellen dabei die Optimierungsgröße für
die Routenplanung dar. Im Fall von militärisch genutzten
Fluggeräten können Kosten beispielsweise das Gefährdungspotential
angeben, mit welchem auf der jeweiligen Verbindungsstrecke zu rechnen
ist; je höher die Kosten sind, desto gefährlicher
ist die Route. Die Kosten einer Route können z. B. durch
eine heuristische Funktion modelliert werden. Diese Funktion kann
u. a. die Höhe des Geländes, die Position und
den Typ von Radarstationen des Feindes, die Positionen von Nichtflugzonen/Korridore
(Must-Fly-Zonen) und weitere Parameter berücksichtigen,
welche einen Einfluss auf die Gefährdung der Route haben.
Die Verbindungsstrecken weisen typischerweise auch unterschiedliche
Zeitdauern auf.
-
Die
Verbindungsstrecken können durch Routenplanung zwischen
zwei Wegpunkten gewonnen werden. Dies kann beispielsweise durch
Extraktion aus einem Voronoi-Graph erfolgen (s. hierzu Yeonju Eun,
Hyochoong Bang (2004), "Cooperative Control of Multiple
UCAVs for Suppression of Enemy Air Defense", AIAA 3rd "Unmanned
Unlimited" Technical Conference, Workshop and Exhibit,
AIAA, Illinois). Alternativ können Verbindungsstrecken
durch Verschmelzung von zwei Dijkstra-Bäumen gewonnen werden
(s. Verlut Grégoire, "On-board Low-level Flight
Planning for Turboprop Transport Aircraft", Disseration,
Braunschweig, Chapter 4). Der Offenbarungsgehalt der vorstehend
genannten Dokumente im Hinblick auf die Bestimmung von Verbindungsstrecken
wird hiermit in den Offenbarungsgehalt der Anmeldung durch Bezugnahme
aufgenommen.
-
Die
Generierung von Verbindungsstrecken ist sehr rechenzeitintensiv,
während der Speicherbedarf für das Ergebnis heutzutage
unproblematisch ist.
-
Daher
wird vorgeschlagen, das Problem der Routenplanung in zwei Teilprobleme
zu teilen. Es werden mehrere optimierte Verbindungsstrecken zwischen
einzelnen aufeinander folgenden Wegpunkten berechnet, beispielsweise
unter Berücksichtigung des Geländes in niedriger
Höhe oder auch unter Berücksichtigung von Nichtflugzonen,
Korridoren und Bedrohungen über alle Höhen. Dann
wird aus diesen verfügbaren Verbindungsstrecken ausgewählt;
dieses ist in kurzer Rechenzeit möglich.
-
Ein
Aspekt der Erfindung ist es also, eine Route entlang mehr als zwei
aufeinander folgenden vorgegebenen Wegpunkte ausgehend von dazwischen
liegenden gegebenen (d. h. im Voraus berechneten) Verbindungsstrecken
mit jeweiligen Kosten zu bestimmen. Zwischen zwei aufeinander folgenden Wegpunkten
bestehen dabei häufig mehr als zwei Verbindungsstrecken.
Es wird vorgeschlagen, die Gesamtroute durch Auswahl der Verbindungsstrecken
zu ermitteln.
-
Dies
bietet den Vorteil, dass dadurch ein Großteil der Berechnung
vor dem Beginn der Route erfolgen kann und dann in Echtzeit eine
zweite Optimierung über die gesamte Route erfolgen kann.
Dadurch kann die Rechenzeit während der Fahrt oder des
Flugs stark reduziert werden. Typischerweise wird der Speicherbedarf zwar
erhöht; dies stellt jedoch bei den heutigen Speicherkapazitäten
(im Gegensatz zu den Rechenkapazitäten) kein Problem dar.
-
Weiterhin
ist es möglich, während der Fahrt bzw. im Flug
nur einzelne Verbindungstrecken zwischen zwei Wegpunkten zu erneuern,
wenn sich etwas geändert hat (beispielsweise die Nichtflugzonen oder
die Radarstationen). Bei einer Gesamtoptimierung müssten
hier immer alle Verbindungsstrecken neu berechnet werden.
-
Das
erfindungsgemäße Verfahren kann dazu genutzt werden,
dass ein Wegpunkt, mehrere Wegpunkte oder gar alle Wegpunkte in
einer vorgegebenen Zeit (oder in einem vorgegebenen Zeitintervall) mit
minimalen Kosten erreicht werden.
-
Gemäß einer
Ausführungsform der Erfindung weist die Routenbestimmung
zwei Schritte (oder zwei Komponenten) auf: In einem ersten Schritt wird
ausgehend von den effizienten Verbindungsstrecken und den Wegpunkten
ein gerichteter Baum aufgebaut. In einem zweiten Schritt wird aus
dem Baum eine effiziente Route extrahiert, insbesondere durch Rückwärtsrechnung.
-
Ein
solcher Baum umfasst Kanten und durch Kanten verbundene Knoten,
wobei jeder Knoten einem bestimmten Wegpunkt zugeordnet ist und
jede Kanten einer speziellen Verbindungsstrecke entspricht. Nach
Erzeugen eines solchen Baumes lässt sich die Route basierend
auf einer Auswahl von Kanten des Baumes bestimmen.
-
Dieses
Verfahren bietet den Vorteil, dass ausgehend von bereits vorgegebenen
Verbindungsstrecken lediglich ein Baum erzeugt werden muss. Dies
kann mit geringem Rechenaufwand erfolgen, insbesondere in dem jeweiligen
Fluggerät (z. B. Flugzeug, Helikopter, Drohne, Rakete)
oder sonstigen Fahrzeug, für das die Route bestimmt wird.
Die rechenaufwändige Bestimmung der Verbindungsstrecken
kann vor Beginn der Routenbestimmung und/oder außerhalb
des Fahrzeugs erfolgen. Die rechenzeitintensiven Verbindungsstrecken
können beispielsweise vor der Mission in einem getrennten Rechner
bestimmt werden oder während der Mission an einer Bodenstation
mit höherer Reichenleistung.
-
Vorzugsweise
ist jeder effizienten Verbindungsstrecke (neben den Kosten) eine
Zeitdauer zugeordnet. Effizient meint hierbei eine optimale Route für
eine gegebene Randbedingung wie Zeit.
-
In
diesem Fall gliedern sich die Knoten vorzugsweise entlang der sequentiellen
Wegpunkte und des zu optimierenden Zustands Zeit. Mit anderen Worten:
der erzeugte Baum weist eine Mehrzahl von Baumebenen auf, auf die
die Knoten verteilt sind. Die Knoten einer Baumebene sind einem
gemeinsamen Wegpunkt zugeordnet. Unterschiedliche Knoten einer Baumebene
sind unterschiedlichen Zeitangaben zugeordnet.
-
Knoten
einer Baumebene können auch unterschiedliche Werte einer
anderen Eigenschaft als Zustand eines Wegpunkts zugeordnet sein,
beispielsweise Flughöhe oder Track-Winkel. Die Knoten können
sich also auch entlang eines zu optimierenden Zustands Flughöhe
oder eines zu optimierenden Zustands Track-Winkel gliedern.
-
Einem
Wegpunkt sind somit häufig mehrere Knoten zugewiesen, wobei
jeder Knoten durch eine Zeitangabe, beispielsweise die Ankunftszeit
am Wegpunkt oder die Zeitdauer bis zum Wegpunkt, gekennzeichnet
ist.
-
Der
Zustand Zeit ist jedoch nur ein Beispiel. Die Zustand kann z. B.
auch als Flugplan ID (Hauptplan, BackUpPlan1, BackupPlan2, Escape...)
interpretiert werden.
-
Zeitbedingungen
an einem Wegpunkt würden dann einer Flugplan ID entsprechen.
-
Alternative
Beispiele für den Zustand sind Flughöhe oder Track-Winkel.
Jeder Knoten eines Wegpunkts könnte statt einer bestimmten
Zeitangabe einer bestimmten Flughöhe oder einem bestimmten
Track-Winkel zugeordnet sein.
-
Bekannte
Bäume, die bei der Bestimmung einer Verbindungsstrecke
verwendet werden, weisen typischerweise eine sehr hohe Zahl von
Knoten auf. Die Anzahl der Knoten bei dem erfindungsgemäßen Baum
ist im Vergleich dazu typischerweise geringer. Deshalb lässt
sich die Zeit als Baumdimension berücksichtigen, ohne dass
der Baum für die vorhandenen Rechenkapazitäten
zu groß wird.
-
Vorteilhafterweise
werden im jeweiligen Knoten eine knotenspezifische Zeitangabe als
Zustand (beispielsweise die Zeitdauer, insbesondere die Zeitdauer
vom Wurzelknoten oder einem Referenzpunkt bis zum jeweiligen Knoten),
knotenspezifische Kosten (insbesondere die Gesamtkosten vom Wurzelknoten
oder einem Referenzpunkt bis zum jeweiligen Knoten) und ein Referenz
zum vorigen Knoten gespeichert. Die gespeicherte Referenz zum vorigen Knoten
ist vorteilhafterweise diejenige, über die die jeweilige
Zeitangabe (beispielsweise die jeweilige Gesamtzeitdauer bis zum
Knoten) am günstigsten (d. h. mit den geringsten Kosten)
erreicht werden kann. Statt einer knotenspezifischen Zeitangabe
als Zustand kann auch einer Zustand wie Flughöhe oder Track-Höhe
im jeweiligen Knoten gespeichert werden.
-
Als
Referenz kann beispielsweise ein Verbindungsstreckenindex verwendet
werden. Anstatt für die Referenz den Verbindungsstreckenindex
zu verwenden, kann die Referenz beispielsweise auch die Gesamtzeitdauer
des vorherigen Knotens oder die Knotennummer (bei Durchnummerierung
der Knoten) des vorherigen Knotens sein.
-
Der
Baum wird vorzugsweise iterativ erzeugt. Die Optimierung kann beispielsweise
mit dem ersten Wegpunkt beginnen und dann iterativ zum zeitlich
nächsten Wegpunkt übergehen, oder die Optimierung
beginnt am zeitlich letzten Wegpunkt und geht dann zum zeitlich
gesehen vorherigen Wegpunkt über. Der Baum kann also in
Fahrt-/Flugrichtung oder entgegen dieser Richtung erzeugt werden.
-
Bei
einer Iteration können neue Knoten eines im Baum nachfolgenden
Wegpunkts ermittelt werden, indem verschiedene Knoten eines gemeinsamen
Wegpunkts (mit anderen Worten: verschiedene Zeitangaben des Wegpunkts)
mit den verschiedenen Verbindungsstrecken zu dem nachfolgenden Wegpunkt
kombiniert werden. Die Knoten des nachfolgenden Wegpunkts weisen
für die einzelnen Zeitangaben jedoch vorteilhafterweise
die geringsten knotenspezifischen Kosten auf. Ergeben sich also
für einen Wegpunkt durch verschiedene Kombinationen gleiche
Zeitangaben, so wird typischerweise nur die von den Kosten günstigere
Kombination für diese Zeitangabe im Baum gespeichert.
-
Zumindest
für einen der Wegpunkte besteht vorzugsweise eine Zeitanforderung
(diese kann ein Zeitpunkt oder auch Zeitintervall sein), beispielsweise
für den ersten und den letzten Wegpunkt des Baumes. Statt
Zeitanforderungen könnten im Fall eines anderen Zustands
als Zeit (beispielsweise Flughöhe oder Track-Winkel) auch
andere Anforderung für den oder die Wegpunkte besteht,
beispielsweise eine Flughöhen-Anforderung oder ein bestimmter
geforderter Track-Winkel.
-
Der
Baum wird vorteilhafterweise bis zu einem Wegpunkt gebaut, der eine
derartige Zeitanforderung besitzt. Dort wird vorzugsweise eine Zeit, mehrere
Zeiten oder ein Bereich von Zeiten ausgewählt, der möglichst
gut zur Zeitanforderung passt (hierbei können neben der
Zeit auch die Kosten berücksichtigt werden und dann Zeit
und Kosten gegeneinander abgewägt werden). Es werden somit
eine oder mehrere durch ihre Zeitangaben gekennzeichnete Knoten
eines Wegpunkts in Abhängigkeit der Zeitanforderung für
diesen Wegpunkt ausgewählt.
-
Der
Baum wird dabei vorteilhafterweise nur von dem bzw. den ausgewählten
Knoten eines Wegpunkts fortgesetzt; die anderen Knoten der Ebene werden
zu sogenannten Blättern des Baumes. Falls mehrere Knoten
ausgewählt werden, wird eine wie vorstehend beschriebene
Optimierung durchgeführt, d. h. der Baum wird in iterativer
Weise von diesen Knoten wie beschrieben fortgeführt.
-
Die
Ermittlung der Route im zweiten Verfahrensschritt setzt auf den
im ersten Verfahrensschritt ermittelten Baum auf. Es wird dabei
vorteilhafterweise ein Knoten derjenigen Ebene (d. h. desjenigen Wegpunkts)
des Baumes, für welche als letzte eine Zeitanforderung
besteht, ausgewählt. Dabei kann es sich beispielsweise
um die letzte Ebene des Baumes handeln; dies ist jedoch nicht notwendig.
Die Auswahl erfolgt durch Vergleich der Zeitanforderung mit den
Zeitangaben der Knoten in dieser Ebene. Beispielsweise wird im zweiten
Schritt in der letzten Ebene der Knoten ermittelt, welche der Zeitanforderung und
optional vorgegebenen Kosten möglichst gut entspricht.
Durch Zurückgehen vom diesem Knoten bis zur Wurzel können
dann die Streckenverbindungen (d. h. die Teilrouten) ausgewählt
werden. Es werden dabei also Kanten des Baumes vom ausgewählten
Knoten bis zum Wurzelknoten ausgewählt. Dies erfolgt unter
Ausnutzung abgespeicherter Referenzen. Der zweite Verfahrensschritt
behilft sich also vorteilhafterweise der Speicherung der Referenz zum
vorherigen Knoten.
-
Neben
dem vorstehend beschriebenen Verfahren ist die Erfindung auch auf
eine entsprechende Vorrichtung zur Routenbestimmung gerichtet. Die vorstehenden
Aussagen zum Verfahren lassen sich in entsprechender Weise auch
auf die Vor richtung übertragen. Eine derartige Vorrichtung
kann beispielsweise Teil eines Bordcomputers eines Fluggeräts
(beispielsweise Flugzeug, Drohne, Hubschrauber oder Rakete) sein.
Die von der Vorrichtung bestimmte Route kann als Eingabegröße
der Steuereinheit des Fluggeräts dienen, beispielsweise
zur Steuerung des Autopiloten.
-
Außerdem
ist die Erfindung noch auf einen Datenträger gerichtet,
die Daten berechneter Verbindungsstrecken zwischen mehreren Wegpunkten (vorzugsweise
zwischen mehr als 2 Wegpunkten) enthält. Ausgehend von
diesem Datenträger kann dann die Routenbestimmung wie oben
beschrieben durchgeführt werden. Vorzugsweise weist ein
Fluggerät eine Einrichtung auf, um diesen Datenträger auszulesen.
-
Ein
weiterer Aspekt der Erfindung ist auf ein Verfahren zur Bestimmung
einer Route entlang mehr als zwei aufeinander folgender vorgegebener
Wegpunkte gerichtet, wobei das Verfahren Verbindungsstrecken zwischen
einem ersten Paar von zwei Wegpunkten unabhängig von der
Bestimmung anderer Verbindungsstrecken zwischen anderen Paaren von Wegpunkten
bestimmt. Die Bestimmung der Route erfolgt basierend auf den Verbindungsstrecken
der mehr als zwei aufeinander folgenden Wegpunkte.
-
Die
rechenzeitintensiven Verbindungsstrecken können beispielsweise
vor der Mission in einem getrennten Rechner bestimmt werden oder
während der Mission an einer Bodenstation mit höherer
Reichenleistung.
-
Das
Problem der Routenbestimmung wird also in einer Vielzahl von Teilproblemen
zerlegt, die unabhängig von einander gelöst werden
können. Ändern sich die Bedingungen zwischen zwei
Wegpunkten, beispielsweise die Position von Radaren zwischen den
Wegpunkten, müssen die Verbindungsstrecken zwischen den
ande ren Wegpunkten nicht neu berechnet werden; es werden lediglich
eine, mehrere oder alle Verbindungsstrecken zwischen den zwei Wegpunkten
neu bestimmt.
-
Verbindungsstrecken
zwischen dem ersten Paar von Wegpunkten können also neubestimmt werden
und die Route kann basierend auf den neubestimmten Verbindungsstrecken
neu ermittelt werden. Wie vorstehend ausgeführt, ist es
hierbei nicht notwendig, dass die anderen Verbindungsstrecken neu
bestimmt werden müssen.
-
Im
Weiteren werden Ausführungsformen der Erfindung unter Bezugnahme
auf die beigefügten Zeichnungen beschrieben. Es zeigen
-
1 ein
Beispiel für berechnete Verbindungsstrecken zwischen 5
Wegpunkten;
-
2 ein
Beispiel für einen Baum gemäß einem Ausführungsbeispiel
der Erfindung; und
-
3 ein
Ausführungsbeispiel für den Ablauf des erfindungsgemäßen
Verfahrens zur Routenbestimmung.
-
1 zeigt
ein Beispiel für berechnete Verbindungsstrecken zwischen
5 verschiedenen Wegpunkten 1–5 einer
Route. Zwischen zwei aufeinander folgenden Wegpunkten 1–5 sind
jeweils eine Mehrzahl von Verbindungsstrecken berechnet worden. Hierbei
handelt es sich um berechnete Verbindungsstrecken für ein
Fluggerät, beispielsweise für ein Flugzeug, ein
Hubschrauber, eine Drohne, eine Rakete oder dergleichen. Bei diesem
Beispiel wurde bei der Berechnung der verschiedenen Verbindungsstrecken
Radare 6, 7 berücksichtigt. Bei einem
militärischen Einsatz handelt es sich hierbei typischerweise um
feindliche Radarstationen. Ferner wurden sogenannte No-Fly-Zonen 8, 9 berücksichtigt,
d. h. Zonen, durch die nicht geflogen werden darf.
-
Aufgrund
der erhöhten Gefahr eines Abschusses beim Flug durch radarüberwachte
Bereiche entstehen beim Flug durch die Radare 6, 7 hohe Kosten,
da die Gefährdung des Fluggeräts zunimmt. Daher
tendieren die dargestellten Verbindungsstrecken dazu, die Radare 6, 7 zu
meiden. Durch die No-Fly-Zonen 8, 9 darf nicht
geflogen, so dass die berechneten Verbindungsstrecken nicht durch
diese Zonen 8, 9 führen. Typischerweise
hat jede Verbindungsstrecke zwischen zwei Wegpunkten 1–5 eine andere
Zeitdauer.
-
Bei
dem erfindungsgemäßen Verfahren zur Routenplanung
werden vorteilhafterweise Zeitvorgaben (beispielsweise ein vorgegebener
Zeitpunkt oder ein vorgegebenes Zeitintervall) für einen
oder mehrere Wegpunkte 1–5 berücksichtigt.
Es wird darauf abgezielt, diese Zeitvorgaben mit möglichst
geringen Kosten zu erreichen.
-
Zur
Planung der optimalen Route ermöglicht es das Verfahren,
bei gegebenen möglichen Verbindungsstrecken zwischen jeweils
2 Wegpunkten mit unterschiedlichen Kosten und Dauern eine Auswahl der
Verbindungsstrecken dahingehend zu treffen, dass für einen,
mehrere oder gar alle Wegpunkte gegebene Zeitvorgaben mit der geringsten
möglichen zeitlichen Abweichung zu den geringsten möglichen Kosten
erfüllt werden.
-
Gemäß einer
Ausführungsform des erfindungsgemäßen
Verfahrens zu Routenbestimmung wird aus den wie in 1 beispielhaft
dargestellten Verbindungsstrecken ein Baum gebaut, der die Zeitdauer
sowie die Kosten der einzelnen Verbindungsstrecken berücksichtigt.
-
Die
Erfindung löst das Optimierungsproblem vorteilhafterweise
mittels zweier Komponenten: Die erste baut den genannten gerichteten
Baum; die zweite extrahiert daraus die effiziente Route, dies geschieht
durch Rückwärtsrechnung.
-
Beim
Bau des gerichteten Baumes gliedern sich die Knoten des Baumes nicht
nur entlang der sequentiellen Wegpunkte, sondern auch entlang des
zu optimierenden Zustands Zeitdauer.
-
2 zeigt
ein Beispiel für einen derartigen Baum gemäß einem
Ausführungsbeispiel der Erfindung. Der Baum wurde sequentiell
vom ersten Wegpunkt bis zum letzten Wegpunkt aufgebaut.
-
Der
dargestellte Baum umfasst den Knoten 11.1 in der ersten
Baumebene, die Knoten 12.1–12.3 in der
zweiten Baumebene und die Knoten 13.1–13.5 in
der dritten Baumebene. Dabei bildet der Knoten 11.1 den
Wurzelknoten des Baumes. Die Knoten von einem Wegpunkt zum nächsten
Wegpunkt sind jeweils über Kanten verbunden, die den gegebenen Verbindungsstrecken
zwischen den jeweiligen Wegpunkten entsprechen. In den Knoten werden
jeweils der Zustand Zeitdauer gespeichert, hier: die Gesamtzeitdauer.
Außerdem werden in diesen Knoten die Kosten (hier: die
Gesamtkosten) und die Referenz zum jeweils vorigen Knoten gespeichert.
Statt dem Zustand Zeitdauer könnte auch ein Zustand Flughöhe
oder Track-Winkel gespeichert werden.
-
Zwischen
Wegpunkt 1 und Wegpunkt 2 bestehen laut 2 insgesamt
drei mögliche Verbindungsstrecken, die Kosten in Höhe
von 4, 8 bzw. 2 und Zeitdauern in Höhe von 18, 15 bzw.
12 aufweisen (in der Reihenfolge von oben nach unten gesehen). Der
Knoten 11.1 des Wegpunkts 1 ist daher mit den drei
Knoten 12.1–12.3 des Wegpunkts 2 über
drei Kanten, die diesen Verbindungen entsprechen, verbunden. In
den drei Knoten 12.1–12.3 des Wegpunkts 2 werden
jeweils die sich ergebende Gesamtzeitdauer (vom Wurzelknoten bis
zum jeweiligen Knoten), die Gesamtkosten und die Referenz zum vorigen
Knoten abgespeichert. In den Knoten 12.1–12.3 entspricht
die erste dargestellte Angabe jeweils der Referenz, die zwei dargestellte
Angabe jeweils den Gesamtkosten und die dargestellte dritte Angabe
jeweils der Gesamtzeitdauer. Bei der Referenz handelt es sich hier
vorteilhafterweise um einen Verbindungsstreckenindex: Die Indizes „I”, „II” und „III” bezeichnen
dabei jeweils die erste, zweite bzw. dritte Verbindungsstrecke zwischen
zwei Wegpunkten (in 2 in der Reihenfolge von unten
nach oben). Die Routen zwischen zwei Wegpunkten werden also einem
Index zugeordnet.
-
Anstatt
für die Referenz den Verbindungsstreckenindex zu verwenden,
kann die Referenz beispielsweise auch die Gesamtzeitdauer des vorherigen
Knotens oder die Knotennummer (bei Durchnummerierung der Knoten)
des vorherigen Knotens sein.
-
Beispielsweise
weist der erste Knoten 12.1 für Wegpunkt 2 die
gespeicherten Werte „III”, „4” und „18” auf,
d. h. dieser ist über Verbindungsstrecke III mit dem vorigen
Knoten 11.1 verbunden, wobei sich für den Knoten 12.1 Gesamtkosten
in Höhe von 4 und eine Gesamtzeitdauer von 18 ergibt.
-
Ausgehend
von den Knoten 12.1–12.3 des Wegpunkts 2 werden
in der nächsten Iteration neue Knoten des nachfolgenden
Wegpunkts 3 ermittelt, indem die Knoten 12.1–12.3 des
Wegpunkts mit den Verbindungsstrecken zu dem nachfolgenden Wegpunkt 3 kombiniert
werden. Hierbei wird darauf geachtet, dass die Knoten des nachfolgenden
Wegpunkts für die einzelnen Zeitangaben die geringsten knotenspezifischen
Kosten aufweisen. Ergeben sich also für den Wegpunkt 3 durch
verschiedene Kombinationen gleiche Zeitangaben, so wird typischerweise
nur die von den Kosten günstigere Kombination im Baum gespeichert.
Dies ist beispielsweise in 2 beim Knoten 13.2 der
Fall. Die Gesamtzeitdauer von 24 des Knotens 13.2 kann
ausgehend von Knoten 12.2 über die Verbindungsstrecke
III mit der verbindungsstreckenspezifischen Dauer 9 und den Kosten 2
erzielt werden (s. dicke Linie vom Knoten 12.2 zum Knoten 13.2).
Eine Gesamtzeitdauer von 24 lässt sich auch ausgehend von
Knoten 12.1 über die Verbindungsstrecke II mit
der verbindungsstreckenspezifischen Dauer 6 und den Kosten 9 erzielen
(s. dünne Linie vom Knoten 12.1 zum Knoten 13.2).
Jedoch sind die Gesamtkosten in Höhe von 13 (= 4 + 9) bei dieser
Kombination höher als die Gesamtkosten in Höhe
von 10 (= 8 + 2) der vorher genannten Kombination, so dass im Knoten 13.2 als
Referenz der Verbindungsstreckenindex III gespeichert wird. Der
damit referenzierte vorige Knoten 12.2 lässt sich
beispielsweise in Rückwärtsrichtung dadurch bestimmen,
indem von der Gesamtzeitdauer in Höhe von 24 im Knoten 13.2 die
Dauer (hier 9) der abgespeicherten Verbindungsstrecke III abzogen
wird. Die sich ergebende Gesamtzeitdauer von 15 weist auf den Knoten 12.2 als
vorigen Knoten.
-
In
den Knoten 13.1–13.5 ist also die gespeicherte
Referenz zum vorigen Knoten immer die, über die die jeweilige
Gesamtzeitdauer des Knotens mit den geringsten Kosten erreicht werden
kann.
-
Zur
Erstellung des Baumes wird also für jede mögliche
Routenkombination zwischen zwei Wegpunkten für jeden Zustand
(d. h. für jede der möglichen Zeitdauern) die
Route mit den günstigsten Gesamtkosten berechnet und dann
mit der Referenz zum Vorgänger und der Gesamtzeitdauer
gespeichert.
-
Der
Baum wird bis zu einem Wegpunkt gebaut, der eine Zeitanforderung
(beispielsweise ein Zeitpunkt, eine Zeitdauer oder ein Zeitintervall)
besitzt. Dort wird vorzugsweise eine Zeit, mehrere Zeiten oder ein
Bereich von Zeiten ausgewählt, der möglichst gut
zur Zeitanforderung passt (hierbei können neben der Zeit
auch die Kosten berücksichtigt werden, so dass beispielsweise
der bezüglich Zeitvor gabe und Kosten beste Zeit oder Zeitbereich
ausgewählt wird). Eine ausgewählte Zeit entspricht
einem Knoten mit der entsprechenden Zeitangabe.
-
Falls
mehrere Knoten ausgewählt werden, wird eine wie vorstehend
beschriebene Optimierung durchgeführt, d. h. der Baum wird
in iterativer Weise von diesen Knoten fortgeführt. Der
Baum wird dabei nur von dem bzw. den ausgewählten Knoten
eines Wegpunkts fortgesetzt; die anderen Knoten der Ebene werden
zu sogenannten Blättern des Baumes.
-
Nach
der Erstellung des Baumes kommt die zweite Komponente zum Einsatz,
die den in der ersten Komponente gebauten Baum benötigt.
Es wird dabei ein Knoten derjenigen Ebene (d. h. desjenigen Wegpunkts)
des Baumes ermittelt, für welche als letzte eine Zeitanforderung
besteht, typischerweise für die letzte Ebene des Baumes.
Es wird vorzugsweise derjenige Knoten ausgewählt, der der
Zeitforderung und/oder einer Kostenvorgabe am Besten entspricht.
Das Abweichen von der Zeitforderung und die Gesamtkosten können
dabei mittels einer Optimierungsfunktion bewertet werden und die
Funktion minimiert werden. Durch Zurückgehen von dem ausgewählten
Knoten bis zur Wurzel werden dann die Teilrouten zwischen den Wegpunkten
ausgewählt. Dabei behilft sich die zweite Komponente der
Speicherung der Referenz zum vorherigen Knoten. Diese Referenz entspricht
dem als nächsten gewählten Teilroutenstück.
Wird beispielsweise in 2 für den Wegpunkt 3 (als
angenommener letzten Wegpunkt) ein Zeitdauer von 24 gefordert, wird
Knoten 13.2 ausgewählt. Durch Zurückgehen
auf den Wurzelknoten 11.1 ergeben sich dann die Verbindungsstrecke
mit dem Index III zwischen Wegpunkt 2 und Wegpunkt 3 und
die Verbindungsstrecke mit dem Index II zwischen Wegpunkt 2 und
Wegpunkt 1.
-
Es
wird darauf hingewiesen, dass der Baum nicht notwendigerweise für
die Gesamtstrecke berechnet werden muss. Beispielsweise kann der Baum
nur zwi schen einem ersten Wegpunkt mit einer Zeitanforderung und
einem letzten Wegpunkt mit einer Zeitanforderung bestimmt werden,
wobei sich an den ersten und/oder den letzten Wegpunkt mit Zeitanforderung
noch weitere Wegpunkte anschließen (beispielsweise der
Startpunkt und/oder der Landepunkt). So kann beispielsweise gefordert
werden, dass ein Fluggerät zu einem bestimmten Zeitpunkt an
einem ersten Wegpunkt mit Zeitanforderung ankommen soll, wobei an
den Startzeitpunkt keine Anforderungen gestellt werden. Der Startzeitpunkt
ergibt sich dann durch einfache Auswahl derjenigen Streckenverbindung
zwischen dem Startpunkt und dem ersten Wegpunkt mit Zeitanforderung,
die die geringsten Kosten aufweist. In diesem Fall könnte der
Baum ausgehend von diesem ersten Wegpunkt mit Zeitanforderung anstatt
ausgehend vom Startpunkt bestimmt werden (dabei entspricht nicht
der Startpunkt, sondern der erste Wegpunkt mit Zeitanforderung dem
Wurzelknoten 11.1 in 2). Genauso
könnte es sein, dass für den Landepunkt keine Zeitanforderung
besteht und lediglich für einen Wegpunkt vor dem Landepunkt
eine Zeitanforderung besteht. In diesem Fall muss der Baum nicht
unbedingt bis zum Landepunkt bestimmt werden, sondern kann nach
dem letzten Wegpunkt mit Zeitanforderung abgebrochen werden. Darüber
hinaus ist es möglich, derartige zusätzliche Wegpunkte
ohne Zeitanforderung (beispielsweise einen Start- und Landepunkt ohne
Zeitanforderung) außerhalb des Intervalls zwischen dem
ersten Wegpunkt mit Zeitanforderung und dem letzten Wegpunkt mit
Zeitanforderung in den Baum mit aufzunehmen. Vorzugsweise wird der Baum
zwischen dem ersten Wegpunkt mit Zeitanforderung und dem letzten
Wegpunkt mit Zeitanforderung bestimmt.
-
3 zeigt
ein Ausführungsbeispiel für den Ablauf des erfindungsgemäßen
Verfahrens zur Routenbestimmung. In Schritt 100 beginnt
das Verfahren. In Schritt 101 wird der betrachtete Wegpunkt
auf den Wegpunkt 1 gesetzt. Im Schritt 102 wird
geprüft, ob der aktuell betrachtete Wegpunkt kleiner als
der letzte Wegpunkt ist. Ist dies der Fall, wird in Schritt 103 geprüft,
ob eine Zeitanforderung für den Wegpunkt gegeben ist.
-
Falls
keine Zeitforderung für den aktuellen Wegpunkt gegeben
ist, werden alle möglichen Kombinationen aus Gesamtzeitdauern
am betrachteten Wegpunkt (d. h. in der betrachten Ebene) und Verbindungsstreckenindizes
der vom Wegpunkt wegführenden Verbindungsstrecken berechnet,
d. h. jede Kombination besteht aus einer Gesamtzeitdauer eines Knotens
und einem Verbindungssteckenindex. Die sich ergebenden Kombinationen
entsprechen beispielsweise der Gesamtheit der in 2 zwischen Wegpunkt 2 und
Wegpunkt 3 dargestellten Verbindungen (also sowohl die
dick als auch dünn gezeichneten Verbindungen). Dabei werden
folgende Ergebnisse am nächsten Wegpunkt (d. h. in der
nächsten Ebene des Baumes) gespeichert: die sich ergebende Gesamtzeitdauer,
die Gesamtkosten und die Referenz zum vorigen Knoten. Falls eine
Kombination eine Gesamtzeitdauer ergibt, die in der neu berechneten
Ebene des Baumes bereits existiert, wird nur die Kombination mit
den geringeren Kosten gespeichert. Diese jeweils günstigeren
Kombinationen sind in dem Baum in 2 durch
die dick gezeichneten Verbindungen gekennzeichnet, die verworfenen Kombinationen
mit den jeweils höheren Kosten sind in 2 durch
die dünn gezeichneten Linien angedeutet.
-
Falls
hingegen im Schritt 103 festgestellt wird, dass eine Zeitforderung
für den aktuellen Wegpunkt gegeben ist, werden in Schritt 105 nicht
alle Gesamtzeitdauern, d. h. nicht alle Knoten des Wegpunkts, für
die Bestimmung der Knoten des nächsten Wegpunkts berücksichtigt.
Es werden nur eine oder mehrere Gesamtzeitdauern berücksichtigt,
die der Zeitforderung des Wegpunkts entsprechen. Hierbei kann beispielswiese
nur eine Gesamtzeitdauer berücksichtigt werden, die der
Zeitforderung am Wegpunkt am besten entspricht. Alternativ können
auch mehrere Gesamtzeitdauern berücksichtigt werden, beispielsweise
die besten N Gesamt zeitdauern oder bei einem geforderten Zeitintervall
die Gesamtzeitdauern, die innerhalb des Zeitintervalls liegen. Daher werden
in Schritt 105 beispielsweise nur die Kombinationen aus
der Gesamtzeitdauer am Wegpunkt, die der Zeitforderung am Besten
entspricht, und den Verbindungsstreckenindizes der vom Wegpunkt
wegführenden Verbindungsstrecken berechnet. Die übrigen Teilschritte
in Schritt 105 sind entsprechend zu denen des Schritts 104.
-
Nachdem
somit über Schritt 104 oder alternativ über
Schritt 105 die Knoten des nächsten Wegpunkts
berechnet worden sind, wird in Schritt 106 der Index des
aktuell betrachteten Wegpunkts um 1 erhöht.
-
Der
Baum wird solange iterativ in der vorstehend beschriebenen Weise
erzeugt, bis der Wegpunkt aktuell betrachtete Wegpunkt dem letzten Wegpunkt
entspricht, der Baum also bis zum letzten Wegpunkt berechnet worden
ist. In diesem Fall ergibt sich in der Abfrage 102 die „nein”-Alternative
und die Erzeugung des Baumes ist abgeschlossen.
-
Im
nachfolgenden Schritt 107 wird derjenige Knoten der letzten
Baumebene ausgewählt, der der Zeitforderung am besten entspricht;
dieser Knoten ist der nun betrachtete Knoten. Statt die Auswahl
lediglich anhand einer möglichst guten Entsprechung mit der
Zeitforderung der letzten Ebene vorzunehmen, können bei
der Auswahl auch zusätzlich die Gesamtkosten berücksichtigt
werden. Gemäß Schritt 108 wird der letzte
Wegpunkt als aktueller Wegpunkt festgesetzt. Mittels einer Schleife
wird nun der Baum vom ausgewählten Knoten der letzten Baumebene bis
zum Wurzelknoten durchwandert und dabei die gespeicherten Verbindungsstrecken
ausgewählt. Dazu wird in der Abfrage 109 stets
geprüft, ob der Wegpunkt größer als Wegpunkt 1 ist.
Solange dies der Fall ist, wird die Schleife durchlaufen und in Schritt 110 die
Verbindungsstrecke der zum jeweils betrachteten Knoten führenden
Verbindungsstrecke über die gespeicherte Referenz zum Vorgänger ausgewählt.
Falls beispielsweise in Schritt 107 Knoten 13.2 ausgewählt
wurde, wird zunächst in Schritt 110 die gespeicherte
Verbindungsstrecke mit der Referenz III zwischen Wegpunkt 2 und
Wegpunkt 3 ausgewählt. Anhand der gespeicherten
Referenz kann außerdem der Vorgänger des bisher
betrachteten Knotens in Schritt 111 ermittelt werden. Dieser
Vorgänger wird nun in Schritt 111 als aktuell
betrachtete Knoten definiert. Für das vorstehend beschriebene Beispiel
ergibt sich der Knoten 12.2. Der Wegpunktindex wird in
Schritt 112 um 1 reduziert. Beim nächsten Schleifendurchlauf
wird nun in Schritt 110 die zum aktuell betrachteten Knoten
führende Verbindungsstrecke ausgewählt. Für
das vorstehend beschrieben Beispiel ergibt sich dann die zum aktuell
betrachten Knoten 12.2 führende Verbindungsstrecke
mit dem Index II.
-
Sind
alle Verbindungsstrecken vom ausgewählten Knoten der letzten
Ebene bis zum Wurzelknoten ausgewählt worden, endet das
Verfahren in Schritt 113.
-
Das
erfindungsgemäße Verfahren hat den Vorteil, dass
aufgrund der Berücksichtigung von Zeitvorgaben beim Bau
des Baumes, mehrere Zeitvorgaben innerhalb einer Route zu geringsten
möglichen Kosten erfüllt werden können.
Die Rechenzeit wird minimiert, da nur die Routenkombinationen jeweils zwischen
zwei Wegpunkten berechnet werden. Die Berechnung der Verbindungsstrecken
ist nicht nötig, da das Verfahren auf diesen bereits bekannten
Informationen aufbaut.
-
Das
erfindungsgemäße Verfahren erlaubt also eine automatische
Routenberechnung unter Berücksichtigung an einem oder mehreren
Wegpunkt mit gleichzeitiger Minimierung der Kosten. Die Erfindung
ermöglicht also eine Rechenzeit- und Kosten-optimierte
Fahrzeug-Routenplanung unter Berücksichtigung von Zeitvorgaben
an Wegpunkten.
-
Das
erfindungsgemäße Verfahren lässt sich neben
Fluggeräte auch für andere Fahrzeuge wie beispielsweise
Automobile, Schienenfahrzeuge o. ä. einsetzen. Da bei Fluggeräten
der Rechenaufwand zur Bestimmung einer Verbindungsstrecke jedoch besonders
groß ist, da es den zusätzlichen Freiheitsgrad
der Flughöhe und typischerweise keine festen vorgegebenen
Strecken (Straßen) gibt, lässt sich das erfindungsgemäße
Verfahren besonders gewinnbringend bei Fluggeräten einsetzen.
-
- 1–5
- Wegpunkte
- 6,
7
- Radare
- 8,
9
- No-Fly-Zonen
- 11.1
- Wurzelknoten
- 12.1–12.3
- Knoten
der zweiten Ebene
- 13.1–13.5
- Knoten
der dritten Ebene
- 100–113
- Schritte
des Ablaufdiagramms
-
ZITATE ENTHALTEN IN DER BESCHREIBUNG
-
Diese Liste
der vom Anmelder aufgeführten Dokumente wurde automatisiert
erzeugt und ist ausschließlich zur besseren Information
des Lesers aufgenommen. Die Liste ist nicht Bestandteil der deutschen
Patent- bzw. Gebrauchsmusteranmeldung. Das DPMA übernimmt
keinerlei Haftung für etwaige Fehler oder Auslassungen.
-
Zitierte Nicht-Patentliteratur
-
- - Yeonju Eun,
Hyochoong Bang (2004), ”Cooperative Control of Multiple
UCAVs for Suppression of Enemy Air Defense”, AIAA 3rd ”Unmanned
Unlimited” Technical Conference, Workshop and Exhibit,
AIAA, Illinois [0003]
- - Verlut Grégoire, ”On-board Low-level Flight Planning
for Turboprop Transport Aircraft”, Disseration, Braunschweig,
Chapter 4 [0003]