Ein Hindernisvermeidungssystem für ein Autonomes

at 11/2004
ANWENDUNGEN
Ein Hindernisvermeidungssystem
für ein Autonomes Unterwasserfahrzeug
An Obstacle Avoidance System for an Autonomous Underwater Vehicle
Mike Eichhorn
In diesem Artikel wird ein System zum Ausweichen von Hindernissen für das autonome
Unterwasserfahrzeug DeepC vorgestellt. Bei Auswahl und Entwicklung der eingesetzten
Strategien wurden die besonderen Anforderungen in der Unterwasserwelt und die im Fahrzeug zur Verfügung stehende Rechenleistung und Sensorik sowie dessen Manövrierfähigkeit
berücksichtigt. Anforderungen in der Unterwasserwelt sind die Einbeziehung der Strömungsinformation, die Berücksichtigung von bewegten Objekten, ein Ausweichen im 3-D Raum
sowie ein begrenzter Auffassbereich durch das Sonar.
This paper describes an Obstacle Avoidance System for an Autonomous Underwater Vehicle. The specific requirements of the underwater world, the computational capacity and the
sensors of the vehicle as well as its manoeuvrability was considered by the choice and the
development of strategies used. Such requirements include the sea current information, the
consideration of moving objects, the evasion in 3D and the constrained view of sonar.
Schlagwörter: Autonomes Unterwasserfahrzeug, geometrischer Graph, Hindernisvermeidung, Wegeplanung
Keywords: Autonomous underwater vehicle, geometric graph, obstacle avoidance, path
planning
1 Einführung
Tabelle 1: Leistungsparameter des Fahrzeuges.
1.1 Forschungsprojekt ,,DeepC“
Parameter
Bei dem Forschungsprojekt ,,DeepC“ arbeitet ein interdisziplinäres Konsortium, bestehend aus deutschen Firmen und
Forschungseinrichtungen, mit Unterstützung des Bundesministeriums für Forschung und Entwicklung an der Entwicklung eines autonomen Unterwasserfahrzeuges [2; 3]. Dieses
Unterwasserfahrzeug soll in der Lage sein, selbstständig
eine vorgegebene Mission durchzuführen und bei unvorhergesehenen Situationen (auftauchende Hindernisse, Ausfall
von Baugruppen) eigenständig zu handeln. Das Fahrzeug
wird durch die Leistungsparameter nach Tabelle 1 spezifiziert. Realisiert werden diese Eigenschaften u. a. durch
die folgenden technischen Details (vergleiche die schematische Darstellung des Fahrzeuges mit seinen wichtigsten
Antriebs- und Manövriereinrichtungen in Bild 1):
Abmaße des Fahrzeuges
Gewicht des Fahrzeuges
Missionstiefe
Marschgeschwindigkeit
Maximale Geschwindigkeit
Einsatzdauer
Nutzlast
Energiegewinnung
Wert
Länge 5800 mm
Breite 2300 mm
Höhe 1700 mm
2,4 t
4000 m
4 kn
6 kn
40 h
300 kg
Brennstoffzelle
• Separate Payload- und Fahrzeughülle
• Verwendung kohlefaserverstärkter Verbundstoffe (CFK)
für die Druckkörper (2)
• Redundanter Aufbau aller wichtigen Systeme und getrennte Unterbringung in den einzelnen Fahrzeugkörpern (1)
• Einsatz von Polymerelektrolytmembran-Brennstoffzellen
(PEM-FC)
• Austauschbarer Payloadcontainer (5).
514
at – Automatisierungstechnik 52 (2004) 11  Oldenbourg Verlag
M. Eichhorn: Ein Hindernisvermeidungssystem für ein Autonomes Unterwasserfahrzeug
at 11/2004
-geschwindigkeit an den Autopiloten übergeben. Dies ist
vergleichbar mit der vollautomatischen Führung eines Passagierflugzeuges durch einen Flugmanagementrechner.
Das Softwaremodul Objekterkennung detektiert aus den
Rohdaten des Sonarsystems Objekte in Form von elliptischen Zylindern. Tangieren solche Objekte die Sollbahn des
Fahrzeuges, muss in dieser Sondersituation die automatische Führung durch andere Algorithmen abgelöst werden,
die die Fahrzeugführung übernehmen. Diese Algorithmen
sind Komponenten des Hindernisvermeidungssystems, welches in den nachfolgenden Kapiteln vorgestellt wird. Das
Hindernisvermeidungssystem ist ein Bestandteil des Softwaremoduls ,,Fahrzeugführung in Sondersituationen“ (FIS)
(im Bild 2 grau hinterlegt).
Bild 1: Strukturbild des AUV’s DeepC.
Seine guten Positionier- und Manövriereigenschaften im
Stand und bei kleineren Geschwindigkeiten erhält es durch
die senkrecht und waagerecht eingesetzten Truster (3). Bei
höheren Geschwindigkeiten erfolgt die Steuerung des Fahrzeuges in einer Kombination von Rudereinheiten (4), Trustern (3) und Drehzahldifferenzen der Hauptantriebe (6).
1.2 Steuerungsstruktur des Fahrzeuges
Die Führungshierarchie des Fahrzeuges ist in einer Mehrebenenstruktur [4] aufgebaut (siehe Bild 2). Im Normalfall arbeitet das Fahrzeug einen Missionsplan ab. Dieser Plan enthält Positionswerte und geometrische Daten
zur Beschreibung von Basismanövern, welche das Fahrzeug in einer vorgegebenen Reihenfolge abzufahren hat.
Dabei werden definierte Vorgaben zur Führung des Fahrzeuges in Form von Sollkurs, -tiefe, -bahn, -lage und
Eine weitere Sondersituation besteht in der Identifikation
von unbekannten Objekten während einer Mission. Eine
Identifikation kann eine visuelle oder kartographische Erfassung des Objektes und/oder eine Bestimmung seiner
physikalischen/chemischen Eigenschaften beinhalten. Die
Steuerung des Fahrzeuges wird hierbei durch Algorithmen
zur Positionierung und Führung des Fahrzeuges, welche
Bestandteil des Softwaremoduls FIS sind, übernommen.
Um bei dem eingangs beschriebenen Vergleich zu bleiben,
wären diese beiden Sondersituationen (Hindernisvermeidung, Identifikation) in Analogie zur manuellen Führung
eines Flugzeuges durch den Kapitän zu sehen.
1.3 Struktur des Hindernisvermeidungssystems
Die Hindernisinformationen werden vom Softwaremodul
Objekterkennung in Form von elliptischen Zylindern an
das Softwaremodul FIS übergeben (Bild 3). Diese Form
Bild 2: Steuerungsstruktur des Fahrzeuges.
515
at 11/2004
ANWENDUNGEN
Bild 3: Struktur des Softwaremoduls FIS.
lässt sich leicht aus den Rohdaten des Sonars generieren und charakterisiert durch wenige geometrische Abmaße
(Hauptachse, Nebenachse und Rotationswinkel der Ellipse,
Höhe des Zylinders) eine Vielzahl von praktischen Hindernisstrukturen. Die Zielpunktgenerierung berechnet während
einer Ausweichsituation, unter Verwendung des aktuellen
Missionsplanes und der detektierten Objekte, einen Rendezvouspunkt mit der Sollroute des Missionsplanes, welcher für das Hindernisvermeidungssystem den anzufahrenden Zielpunkt darstellt.
Für das Hindernisvermeidungssystem des Fahrzeuges
wurde eine Zweiebenen-Struktur favorisiert (im Bild 3 dunkelgrau hinterlegt). Die obere Ebene verwendet zusätzlich
zu den aktuellen Informationen des Sonars die gesammelten Hindernisdaten der bisherigen Mission sowie die Daten
einer digitalen Seekarte. Mit diesen Informationen findet
eine Wegeplanung auf der Basis geometrischer Graphen
statt. Die Verfahren hierzu ermöglichen es, einen optimalen
Weg nach definierten Vorgaben in einer kalkulierbaren Zeit
zu ermitteln. Einen Überblick über die bei der Wegeplanung
eingesetzten Verfahren gibt Kapitel 2.
Treten beim Abfahren des generierten Weges unvorhersehbare, plötzlich auftauchende Hindernisse auf, übergibt
die Kollisionsüberwachung die Steuerung an die untere
Ebene, die Reaktive Ausweichsteuerung. Die Reaktive Ausweichsteuerung reagiert auf die im Nahbereich des Sonars aufgefassten Hindernisse durch entsprechende reaktive
Steuerkommandos, wodurch ein wegoptimales Umfahren
nicht immer möglich ist. Eine solche Forderung hat hier
aber nicht die oberste Priorität. Aufgabe ist ein sicheres
und schnelles Ausweichen zur Vermeidung einer Kollisionssituation. In der Aktivierungszeit der Ebene Reaktive
Ausweichsteuerung kann in der Ebene Wegeplanung der
Routenplan unter Verwendung der neuen Objektinformatio-
516
nen modifiziert bzw. neu erstellt werden. Das Ausweichen
mit der Reaktiven Ausweichsteuerung erfolgt nur in der
x-y Ebene. Dies ist durch den begrenzten Nicklagewinkel
des Fahrzeuges infolge seiner konstruktiven Gegebenheiten
und die gute Manövrierfähigkeit in der horizontalen Ebene
begründet. Eine detaillierte Beschreibung der in der Reaktiven Ausweichsteuerung eingesetzten Algorithmen vermittelt
Kapitel 3.
Bild 4 stellt generierte Fahrtrouten bei Verwendung der
Wegeplanung und der Reaktiven Ausweichsteuerung am
Beispiel eines möglichen Hindernisparcours bei gegebenem Start- und Zielpunkt gegenüber. Hier ist deutlich das
reaktive (,,lokale“) Verhalten der Reaktiven Ausweichsteuerung und das ,,vorausschauende“ (,,globale“) Verhalten
der Wegeplanung an Punkt A zu erkennen. Die Wegeplanung nutzt alle Objektinformationen zur Generierung einer
Route, wogegen die Reaktive Ausweichsteuerung nur die
im Nahbereich vorhandenen Objekte zur Generierung der
Sollkommandos verwendet.
Bild 4: Fahrtrouten bei Verwendung der einzelnen Ebenen.
M. Eichhorn: Ein Hindernisvermeidungssystem für ein Autonomes Unterwasserfahrzeug
at 11/2004
2 Wegeplanung
Bei der Wegeplanung werden die gesamten Informationen
über das aktuelle Operationsgebiet zur Generierung eines
Routenplanes verwendet. Das sind neben den aktuellen Informationen des Sonars, die ,,gesammelten“ Hindernisdaten
der bisherigen Mission sowie die Daten einer digitalen
Seekarte. Ein solcher Routenplan wird auf Basis von Graphen ermittelt. Dabei werden Punkte (Knoten) im Operationsgebiet definiert, welche durch das Fahrzeug befahrbar
sind. Die befahrbaren Verbindungen zwischen diesen Punkten werden als Kanten in den Graphen eingetragen. Jede
Kante besitzt eine Bewertung (Kosten, Gewicht), welche
die Länge der Verbindung, die entstehenden Kosten beim
Abfahren der Verbindung oder die dafür benötigte Zeit sein
kann (siehe Bild 5).
Nach Generierung eines solchen Graphen wird ein Weg
(Routenplan) vom Anfangsknoten (Startpunkt) zum Endknoten (Zielpunkt) mit den geringsten Gesamtkosten durch
Suchalgorithmen (Dijkstra-[5], A∗ -[6], D∗ -Algorithmus [7])
ermittelt. Sie durchsuchen den Graphen, um eine Kombination von Kanten zu ermitteln, welche den Startknoten
und den Endknoten mit der geringsten Summe an Kosten verbinden. In den nächsten beiden Abschnitten werden
die Arbeitsschritte zur Generierung eines Graphen (Erzeugung der Kanten und Knoten unter Echtzeitanforderungen:
Abschnitt 2.1, ein neuartiges Verfahren zur Bestimmung
der Kosten unter Einbeziehung der Strömungsinformation:
Abschnitt 2.2) beschrieben.
Bild 6: Sichtbarkeitsgraph.
(Kreis, Ellipse) werden durch eine Polygonform nachgebildet, welche das Hindernis vollständig einschließt. Alle
möglichen Linien zwischen den Knoten, die keine Hindernisse schneiden, werden zu Kanten des Graphen. Bild 6
zeigt einen so generierten Graphen mit der im Projekt verwendeten elliptischen Hindernisform.
2.1.2 Quadtree- / Octreegraph
Bei diesem Verfahren wird das Operationsgebiet in quadratische (2D-Raum) bzw. kubische (3D-Raum) Sektoren
unterteilt. In Abhängigkeit von darin vorhandenen Hindernissen können sie den Zustand ,,frei“, ,,belegt“ oder
,,teilweise belegt“ besitzen. Teilweise belegte Sektoren werden rekursiv weiter geteilt, bis eine maximale Teilungstiefe
bzw. eine minimale Sektorgröße erreicht wurde. Als ,,frei“
oder ,,belegt“ klassifizierte Sektoren werden nicht weiter
geteilt. So findet eine systematische Zerlegung des Operationsgebietes, analog der Verästelung eines Baumes, statt.
Nach Erzeugung aller Sektoren wird der Graph aufgebaut.
Dazu bilden die Mittelpunkte aller hindernisfreien Sektoren
Bild 5: Geometrischer Graph.
2.1 Darstellungsmöglichkeiten der Umwelt in
einem Graphen
In diesem Abschnitt werden zwei Methoden zur Erzeugung eines geometrischen Graphen (Sichtbarkeitsgraph,
Quadtree- / Octreegraph) vorgestellt. Die Auswahl dieser
Methoden erfolgte auf Grundlage der vorgegebenen Hindernisform (elliptischer Zylinder) und der Forderung nach
einer echtzeitfähigen Abarbeitung der Algorithmen unter
den gegebenen rechentechnischen Restriktionen des Fahrzeuges.
2.1.1 Sichtbarkeitsgraph
Beim Sichtbarkeitsgraphen bilden die Ecken der Hindernisse die Knoten des Graphen [8]. Hindernisse ohne Ecken
Bild 7: Quadtreegraph.
517
ANWENDUNGEN
at 11/2004
die Knoten des Graphen. Die Kanten sind die Verbindungen zwischen benachbarten hindernisfreien Sektoren (siehe
Bild 7).
2.2 Bestimmung des Kostenwertes
Um die Strömungsinformation mit in die Bewertung der
Kante einfließen zu lassen, wird als Kriterium die benötigte
Zeit tBahn zum Abfahren der Kante verwendet. Diese Zeit
bestimmt sich für die i-te Kante durch Bildung des Quotienten aus der Weglänge sBahn und der Geschwindigkeit
vBahn_ef , welche das Fahrzeug auf diesem Wegabschnitt gegenüber einem erdfesten Koordinatensystem fährt. Es gilt:
i
tBahn
=
i
sBahn
.
i
vBahn_ef
(1)
Diese Geschwindigkeit vBahn_ef ist abhängig von der Fahrzeuggeschwindigkeit durchs Wasser vFahr_kf (Marschgeschwindigkeit), dem Betrag und der Richtung des Strömungsvektors vStrömung sowie der Richtung des Wegabschnittes xBahn_dir . Sie kann durch eine geometrische
Schnittberechnung zwischen einer Linie und einem Kreis
(2D) bzw. Kugel (3D) [9] auf der Basis von Bild 8 nach den
folgenden Beziehungen ermittelt werden:
Linie: x vBahn_ef = vBahn_ef xunit
Bahn_dir (2)
2
Kreis/Kugel : v2
= x − vStrömung Fahr_kf
2
T
disc = xunit
·
v
Strömung
Bahn_dir
Fahrzeug in eine starke Gegenströmung gerät und dadurch
die Sollroute verlässt. Bei Verwendung der oben beschriebenen Kostenfunktion ist es auch möglich, bei komplexen
Strömungsprofilen einen zeitoptimalen Weg zu ermitteln.
Dies soll am nachfolgenden Beispiel erläutert werden.
Die Aufgabe besteht in der Ermittlung eines zeitoptimalen
Weges bei der Durchquerung eines Flusslaufes, welcher das
nachfolgende Strömungsprofil besitzt:
x
vStrömung
= 0,0
4
0
x (b − x) vStrömung
(4)
b2
m
0
mit b = 300 m vStrömung
= 1,8 .
s
Bild 9 zeigt die ermittelten Wegverläufe bei Verwendung
der Graphenmethode sowie die korrekte zeitoptimale Lösung durch Optimale Steuerung [10; 11]. Beide Wegverläufe besitzen ähnliche Profile, welche durch jeden
Schwimmer, der einen Fluss mit starker Strömung durchschwommen hat, bestätigt werden. Zuerst schwimmt man
gegen die Strömung, um sich dann in der Mitte des Flusses treiben zu lassen und in Richtung des andern Ufers zu
schwimmen.
y
vStrömung =
+ v2Fahr_kf − vStrömung T · vStrömung
für disc > 0 :
√
T
v Bahn_ef = xunit
Bahn_dir · vStrömung + disc .
Bild 9: Wegplanung mit Strömung.
(3)
Wird die Diskriminante disc negativ, bedeutet dies, dass
das Fahrzeug nicht mehr auf dem Wegabschnitt gehalten werden kann. Ist die Geschwindigkeit v Bahn_ef negativ,
hält sich das Fahrzeug noch auf dem Wegabschnitt, fährt
aber rückwärts. Beide Fälle müssen durch Setzen eines
großen Zahlenwertes für das Kantengewicht Berücksichtigung finden. So werden solche Wegabschnitte bei der
Suche ausgeschlossen, und es kommt nicht dazu, dass ein
Der Graph wurde bei dieser Aufgabe durch ein Gitternetz
aus Knoten aufgebaut. Eine feinere Diskretisierung dieses
Netzes würde zu einer weiteren Annäherung an die exakte
Lösung führen.
2.3 Praktische Umsetzung und Tests
Die durchgeführten Tests erfolgten auf einem Pentium III
450 MHz Desktop. Dieser Rechner entspricht hinsichtlich
seiner Rechenleistung der im Fahrzeug eingesetzten Recheneinheit eines Single Board Computers des Typs VP7
mit einem Pentium III Prozessor 450 MHz der Firma SBS
Technologies [12].
Bild 8: Definition der Geschwindigkeitsvektoren.
518
Für die Tests wurde ein Hindernisparcours mit den Abmaßen von 170 m Länge, 84 m Breite und 50 m Höhe
M. Eichhorn: Ein Hindernisvermeidungssystem für ein Autonomes Unterwasserfahrzeug
definiert. Innerhalb dieses Operationsgebietes wurden Hindernisse nach dem in Bild 10 angegebenen Schema platziert.
Die Konturen in Bild 10 entsprechen den um einen Sicherheitsbereich vergrößerten Hindernissen. Allerdings sind
Test 15 und Test 20 durch das begrenzte Auffassvermögen
eines Sonars nicht praxisrelevant. Diese beiden Tests sollen
nur die Leistungsfähigkeit der Algorithmen überprüfen.
at 11/2004
Tabelle 2: Testfälle im Hindernisparcours.
Test
Anzahl
der Hindernisse
Hindernisnummern
Test 5
5
1-5
Test 10
10
1-10
Test 15
15
1-15
Test 20
20
1-20
Die Testreihen wurden für den 2D-und 3D-Raum durchgeführt. Bei den 2D-Tests wurden die Hindernisse auf die
x-y Ebene projektiert. Die bei den Tests erstellten Graphen
beinhalten die in Abschnitt 3.1 dieses Kapitels vorgestellte
Kostenfunktion. Dies führt zur Generierung eines gerichteten Graphen, da jede Kante in Abhängigkeit der Fahrtrichtung einen eigenen Kostenwert beinhaltet.
Für die Pfadsuche wurde die Boost Graph Library [13; 14]
eingesetzt. Sie beinhaltet eine Bibliothek mit fertigen Datenstrukturen für Graphen und Suchalgorithmen und unterstützt eine Vielzahl von C++ Compilern. Als Wegsuchalgorithmus kam das Dijkstra-Verfahren zum Einsatz.
Des Weiteren wurden für die Tests die Compiler Borland
C++ Builder Version 6.0 [15], Microsoft Visual C++
(Version 6.0) und Mircosoft Visual C++.NET (Version
7.0) [16] eingesetzt. Da im Projekt der Borland C++
Builder verwendet wird, stammen die in Bild 11 und 12
aufgeführten Rechenzeiten aus den Programmen, welche
mit diesem Compiler übersetzt wurden.
Der Vergleich von Bild 11 und 12 zeigt ein deutliches Anwachsen der Rechenzeit bei den 3D-Tests. Den größten
Zeitaufwand erfordert die Generierung des Graphen. Die
Zeit für die Wegsuche nimmt dabei einen verschwindend
kleinen Anteil ein. Der Rechenaufwand zur Generierung
eines Quadtree- / Octreegraphen liegt um das 3fache im
2D-Raum und um das 7fache im 3D-Raum höher als
beim Sichtbarkeitsgraphen. Dies ist durch die notwendige
minimale Sektorgrösse (1 m × 1 m × 6 m) und der damit
verbundenen zeitaufwändigen Generierung der Datenstrukturen für den 2D bzw. 3D-Baum [17] und des Graphen
begründet. Nur durch eine solch feine Diskretisierung können auch ,,freie“ Sektoren zwischen den Hindernissen
generiert werden.
Bild 11: 2D-Tests.
Bild 12: 3D-Tests.
Der Einsatz der Microsoft-Compiler brachte im Durchschnitt eine Senkung der Rechenzeit um 35%. Für das Projekt wurde der Sichtbarkeitsgraph favorisiert. Dies ist durch
seinen geringeren Rechenaufwand und durch die Form der
ermittelten Wege (vergleiche Bild 6 und Bild 7) begründet.
Es finden bei diesem Verfahren weniger Kursänderungen
als beim Octreegraphen während des Durchfahrens eines
Parcours statt.
3 Reaktive Ausweichsteuerung
Bild 10: Hindernisparcours.
Die Reaktive Ausweichsteuerung muss bei plötzlich auftauchenden Hindernissen die Wegeplanung ablösen und
519
at 11/2004
ANWENDUNGEN
die Fahrzeugführung übernehmen. Ein anderer Einsatzfall
ist bei Bereitstellung ,,ungenauer“ Objektdaten durch das
Modul Objekterkennung gegeben. Unter ungenau ist ein
stochastisches Variieren der Abmaße und der Lage der Objekte infolge der begrenzten Reichweite der AufklärungsSensorik (z. B. Forward Looking Sonar) sowie der entfernungsabhängigen Detektionsgüte zu verstehen. In solchen Fällen ist ein Ausweichverfahren gefordert, welches
eine hohe Robustheit gegenüber solchen Variationen besitzt. Diese Forderung wird durch die Reaktive Ausweichsteuerung erfüllt, da sie die Steuerkommandos (Sollkurs,
-geschwindigkeit) für den Autopiloten nur auf der Basis
der aktuellen Lage der Objekte zum Fahrzeug generiert.
Eine Wegeplanung, welche eine gewisse Konstanz der Objektdaten zwischen Erstellung und Abarbeitung des Planes
voraussetzt, wird nicht durchgeführt.
Die Idee des in diesem Kapitel vorgestellten neuen Verfahrens besteht in der Verwendung von Bahnlinien, welche
von jeder beliebigen Position des Operationsgebietes einen
Weg zum Zielpunkt aufzeigen. Der Sollkurs des Fahrzeuges wird durch Bildung des Bahnanstiegs (Gradienten G)
an der aktuellen Fahrzeugposition bestimmt. So kann das
Fahrzeug von seiner aktuellen Position aus die aktuelle
Bahnlinie bzw. ihren Gradienten verwenden, um vorbei an
den Hindernissen zum Zielpunkt geführt zu werden. Da für
die reaktive Ebene nur die x-y Ausdehnung der Hindernisobjekte berücksichtigt wird, soll in diesem Kapitel auch
nur der 2D-Raum behandelt werden. Es ist jedoch auch
möglich, das vorgestellte Verfahren für den 3D-Raum durch
entsprechende Modifikationen zu verwenden.
Das in diesem Kapitel beschriebene Verfahren basiert auf
den Arbeiten von [18; 19]. Es werden Gradientenlinien
durch künstliche harmonische Dipol-Potentiale erzeugt.
Durch die Verwendung solcher Dipol-Potentiale können
die negativen Eigenschaften der künstlichen Potentialfelder kompensiert werden. Solche Eigenschaften sind das
,,Festsetzen“ des Fahrzeuges in lokalen Minima, die oszillierende Bewegung in engen Durchfahrten sowie das
Sperren von möglichen Routen durch das resultierende abstoßende Kraftfeld am Eingang einer Durchfahrt [18].
negative Ladung im Zielpunkt wird zu –1 gewählt. Die positive Ladung des Hindernisses wird durch die Gleichung:
R
q=
(5)
R+ D
beschrieben. Dabei ist R der Radius des Hinderniskreises.
D beschreibt den Abstand zwischen den beiden Ladungen.
Durch Gleichung (5) wird garantiert, dass alle Gradientenlinien, welche innerhalb des Kreises beginnen, herausgeführt
werden und im Zielpunkt enden. Gradientenlinien, welche
außerhalb des Kreises beginnen, verlaufen ausschließlich
außerhalb des Kreises. Für die Beweisführung sei auf [18]
und [19] verwiesen.
Für die Ermittlung des resultierenden Gradienten G an der
aktuellen Fahrzeugposition sind die beiden Gradienten für
die positive und negative Ladung getrennt zu berechnen
und durch Superposition zusammenzufassen. Bild 13 zeigt
das so entstandene Potentialfeld mit den dazugehörigen
Gradientenlinien.
Da die Gradientenlinien das Hindernis tangieren können
(aber nicht schneiden), muss der Radius R des Kreises um
einen solchen Betrag vergrößert werden, welcher eine Kollision zwischen Fahrzeug und Objekt verhindert. Hier bietet
sich eine Vergrößerung mit der n-fachen maximalen Ausdehnung des Fahrzeuges an. Der so entstandene Kreis wird
auch als Sicherheitszone bezeichnet [18].
Befindet sich das Fahrzeug auf der dem Zielpunkt abgewandten Seite und fährt in der Nähe der Symmetrieachse
des Dipols, wird es erst kurz vor Erreichen des Hinderniskreises zum Umfahren des Hindernisses gebracht (siehe
Bild 13). Dabei sind starke Lenkkommandos notwendig,
um das Fahrzeug auf der vorgegebenen Gradientenlinie zu
halten. Des Weiteren entspricht die Form der Gradientenlinien in diesem Bereich und an den seitlichen Vorbeiführungen nicht einer wegoptimalen Fahrtroute. Diese Effekte
nehmen mit größer werdenden Parametern von R und D zu.
Sie sollen durch die geometrische Konstruktion von Gradientenlinien zur wegoptimalen Führung im neuen Verfahren
beseitigt werden.
Es wird ein neues Verfahren vorgestellt, welches die Gewinnung der Gradienten aus einer geometrischen Konstruktion der Gradientenlinien ermöglicht. Des Weiteren werden
Möglichkeiten aufgezeigt, ein Ausweichen unter Einbeziehung der Geschwindigkeitsinformationen der Seeströmung
und der Hindernisse durchzuführen.
3.1 Erzeugung von Gradientenlinien durch
harmonische Dipol-Potentiale
Für die nachfolgenden Ausführungen sei angenommen,
dass ein Hindernis durch einen Kreis beschrieben wird.
Fasst man den Kreis als positive Ladung und den anzufahrenden Zielpunkt als negative Punktladung auf, so bildet
diese Struktur einen Dipol, dessen Feldlinien von der positiven zur negativen Ladung führen. Der Wert für die
520
Bild 13: Gradientenlinien des Dipols.
M. Eichhorn: Ein Hindernisvermeidungssystem für ein Autonomes Unterwasserfahrzeug
at 11/2004
3.2 Erzeugung von Gradientenlinien durch
geometrische Konstruktion
Einführend sei an dieser Stelle erwähnt, dass die in diesem
Abschnitt erzeugten Gradientenlinien keine physikalischen
,,Vorbilder“ haben. Sie sollen lediglich zu einer wegoptimalen Fahrtroute führen.
Hierzu wird das Operationsgebiet in einzelne Sektoren aufgeteilt (siehe Bild 14). Die Einteilung der Sektoren erfolgt
in Abhängigkeit der Fahrzeugposition xFahr vom Hinderniszentrum xHind und vom Zielpunkt.
Wenn die Bedingung (|xFahr − xHind| < R) erfüllt ist, befindet sich das Fahrzeug im Inneren des Sicherheitskreises. Es
ist der Sektor 3 aktiv. Der Gradient wird dabei durch die
Gleichung:
xDistanz
Hind = xFahr − xHind
xDistanz
Hind
G =
Distanz xHind Bild 15: Gradientenlinien bei geometrischer Konstruktion.
(6)
berechnet. Die Aktivierung des Sektors 3 scheint im ersten
Moment ausgeschlossen. An dieser Stelle sei jedoch noch
einmal festgestellt, dass der Radius R eine Sicherheitszone
beschreibt, in welcher sich das Hindernis befindet. So ist es
durchaus möglich, dass ein Fahrzeug in diesen Sicherheitskreis eindringen kann (starke Strömung, zu späte Erfassung
des Hindernisses). In einem solchen Fall muss das Fahrzeug wieder sicher aus dem Kreis geführt werden, was eine
Gradientenbeschreibung im Innern des Kreises erfordert.
Wird die Sicht zwischen Fahrzeug und Zielpunkt durch den
Kreis verdeckt, ist keine direkte Anfahrt zum Zielpunkt
möglich (Sektor 1). In diesem Fall muss der Richtungsvektor der Tangentengerade von xFahr zum Kreis in Abhängigkeit der Lage von xFahr zur Symmetrieachse bestimmt
werden. Der Gradient ist dabei der normierte RichtungsvekRichtung
tor xTangente :
Richtung
xTangente
.
G =
Richtung
xTangente (7)
Gibt es eine direkte Verbindung zwischen Fahrzeug und
Zielpunkt, ist Sektor 2 aktiv. Dann gilt:
xDistanz
= xZiel − xFahr
Ziel
xDistanz
Ziel
.
G =
Distanz xZiel (8)
Um beim Austreten der Gradientenlinien aus dem Sicherheitskreis einen kontinuierlichen Übergang zu den Gradientenlinien der Sektoren 1 und 2 zu erreichen, wurde
ein Radius Rslid eingeführt. In dem dadurch entstehenden Kreisring zwischen R und Rslid findet eine gewichtete
Überlagerung unter Verwendung des Wichtungsfaktors α
zwischen den Gradienten außerhalb und innerhalb des Kreises nach der Beziehung
α=
|xFahr −xHind |−R
Rslid −R
G = α GSektor1_2 + (1 − α) GSektor3
Außerhalb des
Innerhalb des
Kreises
Kreises
(9)
statt. Bild 15 zeigt ein so erzeugtes Gradientenfeld.
3.3 Einbeziehung der
Geschwindigkeitsinformationen
Bild 14: Einteilung des Operationsgebietes in Sektoren.
Unter realen Umweltbedingungen kann es vorkommen,
dass ein Hindernis sich bewegt (beschrieben durch vHind )
oder eine starke Seeströmung vStrömung vorhanden ist. In
solchen Fällen ist es sinnvoll, diese Geschwindigkeitsinformationen bei der Generierung der Gradientenlinien mit
einfließen zu lassen. So soll es möglich sein, ein Ausweichmanöver schon früher zu beginnen, wenn sich ein
Hindernis auf das Fahrzeug zu bewegt oder eine starke
Rückenströmung vorhanden ist. In beiden Fällen wird dadurch ein mögliches Kollidieren durch unzureichendes Reagieren vermieden. Eine Möglichkeit, dies zu erreichen, ist
die Vergrößerung der Sicherheitszone in Richtung einer
521
at 11/2004
ANWENDUNGEN
Bild 16: Verformung der Sicherheitszone.
resultierenden Geschwindigkeit vres , welche durch die folgende Beziehung beschrieben wird:
vres = vHind − vStrömung .
(10)
Die Sicherheitszone wird damit von ihrer Kreisform mit
dem Radius R in eine Ellipse überführt (siehe Bild 16).
Die geometrischen Maße der so entstandenen Ellipse werden durch die nachfolgenden Gleichungen bestimmt:
aEllipse = R (1 + vrel )
bEllipse = R (1 + vrel )
y −1 vres
θEllipse = tan
.
x
vres
(11)
Der Koeffizient vrel beschreibt das Verhältnis zwischen dem
Betrag der resultierenden Geschwindigkeit |vres | und der
vorgegebenen Marschgeschwindigkeit v Marsch des Fahrzeuges und wird berechnet aus:
vres vrel =
.
(12)
v Marsch
Das Zentrum der Ellipse wird durch den Zusammenhang
cos θEllipse R vrel
xHind_vel = xHind +
(13)
sin θEllipse R vrel
beschrieben. Die Berechnung der Gradientenlinien für die
entstandene elliptische Form des Sicherheitsgebietes erfolgt
auf der Basis der Ausführungen im Abschnitt 3.5.
3.4 Anwendung für mehrere Hindernisse
Bei den bisherigen Ausführungen wurde nur ein einzelnes Hindernis im Operationsgebiet betrachtet. Sind mehrere
vorhanden, muss darauf geachtet werden, dass sich die
Sicherheitsbereiche der einzelnen Hindernisse nicht überschneiden. Lässt sich dies nicht vermeiden, müssen die
entsprechenden Hindernisse durch eine gemeinsame Sicherheitszone abgedeckt werden [18].
Bei der Bestimmung des Gradienten werden nur die Gradientenlinien des dem Fahrzeug nächstgelegenen Hindernisses verwendet. Dies führt dazu, dass bei der Durchfahrung
522
Bild 17: Vereinfachte Bestimmung von dLinie .
eines Hindernisparcours ein Umschalten zum jeweils aktuellen Gradientenlinienfeld erfolgt. Um beim Übergang
zwischen zwei Gradientenfeldern einen homogenen Verlauf
zu erzielen, ist es notwendig, statt des binären Umschaltens
ein ,,kontinuierliches“ Umschalten durchzuführen. In [18]
wurde ein Bereich entlang der Grenzlinie zweier benachbarter Gradientenlinienfelder definiert (d Linie_max ), in welchem sich die Gradienten der einzelnen Felder mittels eines
Wichtungsfaktors α linear überlagern. Dieser Wichtungsfaktor wurde proportional zum Fahrzeugabstand von der
Grenzlinie gewählt. Eine vereinfachte Bestimmung dieses
Abstandes kann durch (14) auf Grundlage von Bild 17 erfolgen. Es gilt:
d Linie =
d 2Fahr_n − d 2Fahr_m
2dm_n
.
(14)
Die Abstände d Fahr_n und d Fahr_m beschreiben die kürzeste
Entfernung von der aktuellen Fahrzeugposition zum jeweiligen Hindernis.
Der resultierende Gradient bestimmt sich so durch die folgenden Beziehungen:


 GHind_m für d Linie > d Linie_max
(15)
G = GHind_n für d Linie < −d Linie_max


αGHind_m + (1 − α) GHind_n für |d Linie | < d Linie_max
mit dem Wichtungsfaktor α
d Linie
α = 0,5 1 +
.
d Linie_max
(16)
3.5 Anwendung bei elliptischen Sicherheitszonen
Bei den vorhergehenden Ausführungen wurde vorausgesetzt, dass ein Hindernis durch einen Kreis beschrieben
wird. Da durch die Kreisform viele Objekte ungünstig
beschrieben werden, ist eine elliptische Form vorteilhafter. Die Anpassung des vorgestellten Verfahrens an eine
elliptische Form wäre sehr rechenaufwändig und bei Ein-
M. Eichhorn: Ein Hindernisvermeidungssystem für ein Autonomes Unterwasserfahrzeug
at 11/2004
Bild 18: Schritte der Transformation.
beziehung der Geschwindigkeitsinformation (Abschnitt 3.3)
für nichtkreisförmige Hindernisse gar nicht realisierbar.
Deshalb wird eine Transformation durchgeführt, welche
eine gedrehte Ellipse mit der Position xEllipse in einen
im Koordinatenursprung liegenden Kreis überführt. Die
Berechnung der Gradientenlinien erfolgt dann für kreisförmige Hindernisse, wie in Abschnitt 3.2 beschrieben
und anschließender Rücktransformation. Die Transformation für einen beliebigen Punkt x in diesem Bildbereich
setzt sich so aus mehreren Teilschritten zusammen (siehe
Bild 18):
1. Translation des Punktes um die Position xEllipse . (Verschiebung der Ellipse in den Koordiantenursprung des
Bildbereiches.)
xtrans = x − xEllipse
(17)
Rückskalierung:
aEllipse
Grescal =
0
Rückrotation:
cos θEllipse
G=
sin θEllipse
0
bEllipse
G̃
− sin θEllipse
(20)
cos θEllipse
Grescal .
(21)
3.6 Test des Verfahrens
Abschließend soll das neu entwickelte Verfahren der geometrischen Konstruktion mit dem Verfahren der harmonischen Dipolpotentiale verglichen werden. Dazu wurde ein
Hindernisparcours, der in Bild 20 dargestellt ist, definiert.
2. Rotation des Punktes um den Rotationswinkel der Ellipse θEllipse . (Rotation der Ellipse zur Erreichung einer
achsenparallelen Lage der Ellipse im Bildbereich.)
cos θEllipse
sin θEllipse
xtrans_rot =
xtrans
(18)
− sin θEllipse cos θEllipse
3. Skalierung des Punktes mit den inversen Werten der
halben Haupt- und Nebenachse (aEllipse und bEllipse ) der
Ellipse. (Erreichung einer Kreisform für die Ellipse mit
R=1.)


1
0
 aEllipse


x̃ = 
(19)

1  xtrans_rot .
0
bEllipse
Nach Durchführung dieser Transformation können die eigentlichen Berechnungen im Bildbereich durchgeführt werden. Der hierbei berechnete Gradient G muss anschließend
wieder vom Bildbereich in den Originalbereich rücktransformiert werden (20), (21). Es gilt:
Bild 19: Auswertung der Sollkursraten r .
523
at 11/2004
ANWENDUNGEN
Bild 20: Wege durch einen Hindernisparcours.
Das Fahrzeug soll mit einer Marschgeschwindigkeit von
2 m/s durch diesen Parcours fahren. Es zeigte sich, dass
bei Verwendung des geometrischen Verfahrens die Sollkursrate r (Drehgeschwindigkeit des Sollkurses) wesentlich
geringere Maximalwerte als das Verfahren der harmonischen Dipolpotentiale besitzt (siehe Bild 19). Dies ist für
den praktischen Einsatz ein wichtiges Kriterium, da das
eingesetzte Fahrzeug schnellen Sollkursänderungen nicht
folgen kann, was zum Abweichen von der Gradientenlinie
und damit zu einer möglichen Kollision führt. Des Weiteren
bewirkt jede schnelle Sollkursänderung eine Vergrößerung
des Navigationsfehlers. Schon aus diesem Grund sollten
solche Manöver vermieden werden. Die benötigte Weglänge zum Durchfahren des Parcours beträgt beim Geometrischen Verfahren bis zu 9% weniger als bei der Methode
der harmonischen Dipolpotentiale. Die Trajektorienverläufe
des geometrischen Verfahrens sind der Form von optimalen
Wegen, wie sie in [20] unter Verwendung einer Evolutionsstrategie generiert wurden, sehr ähnlich.
4 Zusammenfassung
gegebenen Hindernisform (elliptischer Zylinder) und den
rechentechnischen Restriktionen. Die durchgeführten Tests
zeigten die Echtzeitfähigkeit der Graphenmethoden bei der
Wegeplanung.
Das vorgestellte neue Verfahren zur geometrischen Konstruktion von Gradientenlinien für die Reaktive Ausweichsteuerung verbindet die Vorteile des Verfahrens der künstlichen harmonischen Dipol-Potentiale mit den Forderungen
einer weg- und stellenergieoptimalen Fahrweise. Die Seeströmung sowie eine mögliche Geschwindigkeit der Hindernisse wurden bei der Konstruktion der Gradientenlinien
durch Bildung einer Ersatzform für das Hindernis auf einfache Weise berücksichtigt.
Weiterführende Darlegungen zu dem in diesen Artikel vorgestellten Hindernisvermeidungssystem erfolgen in [21].
Die Implementierung der vorgestellten Algorithmen auf der
Zielplattform und die Tests am AUV Simulator werden bis
zum Herbst 2004 abgeschlossen sein. Anschließend finden
die ersten Freiwasserversuche mit dem AUV statt.
Danksagung
In diesem Artikel wurde ein Konzept zur Führung eines
Unterwasserfahrzeuges in Ausweichsituationen vorgestellt.
Dieses Konzept wurde für das AUV ,,DeepC“ entwickelt.
Die besonderen Merkmale des Fahrzeuges (vorhandene Rechenleistung und Sensorik, Fahrcharakteristik und Manövrierfähigkeit) bildeten die Hauptkriterien bei der Auswahl
und Entwicklung der Algorithmen.
Diese Arbeit ist ein Teilgebiet des aktuellen Forschungsprojektes
,,DeepC“, welches durch das BMBF gefördert wurde. (Förderkennzeichen: 03SX104E). Ich möchte mich bei Prof. J. Wernstedt bedanken,
welcher mir die Möglichkeit gab, dieses interessante Thema zu bearbeiten, bei Marco Jacobi für die softwaretechnische Unterstützung und den
regen Erfahrungsaustausch bei der Entwicklung der Graphenmethoden
und bei meinem Kollegen Divas Karimanzira für die gute Zusammenarbeit und Hilfe während des Projektes.
Durch den Einsatz von Graphenmethoden zur Ermittlung
eines Routenvorschlages in der Wegeplanungsebene konnte
die Forderung nach einer energieoptimalen Fahrweise leicht
berücksichtigt werden. Die Einbeziehung der Seeströmung
in die Kostenfunktion ermöglicht es, Gebiete mit starker
Seeströmung von der Routenplanung auszuschließen.
Literatur
Die Auswahl der untersuchten Methoden zur Generierung
eines geometrischen Graphen erfolgte auf Basis der vor-
524
[1] M. Eichhorn: An Obstacle Avoidance System for an Autonomous Underwater Vehicle. in Proceedings of the International Symposium on Underwater Technology, Taipei, Taiwan,
April 20–23 2004.
[2] http://www.deepc-auv.de/deepc/DeepC.htm.
[3] Förderprojekt des BMBF: DeepC. Aktiv autonomes Unterwasserfahrzeug für große Tauchtiefen. Förderkennzeichen:
03SX104E.
M. Eichhorn: Ein Hindernisvermeidungssystem für ein Autonomes Unterwasserfahrzeug
[4] D. Brutzman, T. Healey, D. Marco und B. MxGhee: The
Phoenix Autonomous Unterwater Vehicle. In: Kortenkamp, D., Bonasso, P., & Murphy, R., editors, AI-Based
Mobile Robots, chapter 13. MIT/AAAI Press. 1997.
[5] E.W. Dijkstra: A Note on Two Problems in Connexion with
Graphs, Numerische Mathematik, 1, pp. 269–271, 1959.
[6] N.J. Nilsson: Problem-Solving Methods in Artificial Intelligence, McGraw-Hill, 1971.
[7] A. Stentz: The focussed D∗ Algorithm for Real-Time Replanning. In: Proceedings of the International Joint Conference on Artificial Intelligence, Montreal, Canada, August
1995.
[8] G. Dudek und M. Jenkin: Computational principles of mobile robotics. New York, USA: Cambridge University Press,
2000.
[9] P.J. Schneider und D.H. Eberly: Geometric Tools for Computer Graphics. San Fancisco, USA: Morgan Kaufmann,
2003.
[10] A.E. Bryson und Y.-C. Ho: Applied Optimal Control. USA:
Ginn and Company, 1969.
[11] M. Papageorgiou: Optimierung: statische, dynamische, stochastische Verfahren für die Anwendung. München, Germany, R. Oldenbourg Verlag, 1991.
[12] http://www.sbs.com.
[13] J.G. Siek, L.-Q. Lee und A. Lumsdaine: The Boost Graph
Library: User Guide and Reference Manual. New York,
USA: Addison Wesley, 2002.
[14] http://www.boost.org.
[15] http://www.borland.com.
at 11/2004
[16] http://msdn.microsoft.com/visualc.
[17] R. Klein: Algorithmische Geometrie. Bonn, Germany:
Addison-Wesley-Longman, 1997.
[18] J. Guldner: Lokale Kollisionsvermeidung für mobile Roboter mittels künstlicher harmonischer Dipol-Potentiale. at –
Automatisierungstechnik, Volume 45, Issue 01, pp. 24–35
1997.
[19] J. Guldner: Intelligentes hierarchisches Regelungskonzept
für autonome mobile Robotersysteme. Düsseldorf, Germany:
VDI-Verlag, 1995.
[20] K. Watanabe, M.M.A. Hashem und K. Izumi: ,,Global Path
Planning of Mobile Robots as an Evolutionary Control Problem“, European Control Conference, Karlsruhe, Germany,
1999.
[21] M. Eichhorn: Fahrzeugführung in Sondersituationen: Promotion A, Technische Universität Ilmenau, in Vorbereitung.
Manuskripteingang: 18. Mai 2004.
Dipl.-Ing. Mike Eichhorn ist wissenschaftlicher
Mitarbeiter am Institut für Automatisierungs- und
Systemtechnik der Technischen Universität Ilmenau.
Hauptarbeitsfelder: Modellierung und Steuerung
mobiler Systeme, Mechatronik, Fuzzy-Control, Softwareentwicklung und Implementierung.
Adresse: Technische Universität Ilmenau, Institut
für Automatisierungs- und Systemtechnik, Postfach
100565, 98684 Ilmenau, Tel.: +49-(3677)-69-1421,
Fax: +49-(3677)-69-1434,
E-Mail: [email protected]
Prädiktive Regelung
Modellbasierte prädiktive
Regelung
Eine Einführung für Ingenieure
2004. 355 Seiten
€ 49,80
ISBN 3-486-27523-2
Oldenbourg Wissenschaftsverlag
Rosenheimer Straße 145
D-81671 München
Telefon 089 / 450 51-0
Fax 089 / 450 51-204
Bestellungen: http://www.oldenbourg-verlag.de
Das erste deutschsprachige Buch zu diesem Thema.
Das Buch bietet eine Einführung in die modellbasierte prädiktive Regelungen einschließlich ihrer Anwendungen in der industriellen Prozessautomatisierung.
Ausgewählte Anwendungsbeispiele zeigen dem Leser
die Möglichkeiten und den Nutzen dieser Technologie
auf.
Es richtet sich vor allem an jetzige und zukünftige
Anwender in der Industrie auf den Gebieten Anlagenplanung und -errichtung, Prozessleittechnik, Prozessführung und Informationstechnik, ist aber auch
für Studierende höherer Semester der Fachrichtungen
Automatisierungs- und Verfahrenstechnik und für in
der Forschung tätige Wissenschaftler von großem
Interesse.
Oldenbourg
Rainer Dittmar / Bernd-Markus Pfeiffer
525