Kooperative Multi-Roboter-Wegplanung durch heuristische Prioritätsanpassung

Front Cover
Logos Verlag Berlin GmbH, 2008 - 170 pages

Sollen viele Roboter in einem System zusammenarbeiten, dann ist die Wegplanung der Roboter ein komplexes und bisher kaum gelöstes Problem. Leicht kann es geschehen, dass sich Roboter gegenseitig behindern, und die entstehenden Staus, Blockaden und Verklemmungen können das gesamte System zum Scheitern bringen. Die vorliegende Arbeit beschreibt nun ein neuartiges Verfahren, um dieses Problem zu lösen. Der vollständig verteilte, heuristische Algorithmus erlaubt es, die Bewegungen aller Roboter zu koordinieren und jedem Roboter den freien Weg zum Ziel zu ermöglichen. Dabei kommunizieren die Roboter untereinander und verhandeln über kritische Wegstellen, wobei sie sich gegenseitig kooperativ unterstützen. Durch ständige Überprüfung und Überarbeitung der Wegpläne ist das Verfahren sehr robust, und kann Störungen, Ausfälle und unvorhergesehene Ereignisse kompensieren. Der relativ geringe Berechnungs- und Kommunikationsaufwand erlaubt den Echtzeiteinsatz auch in Systemen mit einer sehr hohen Anzahl an Robotern, der Algorithmus ist problemlos skalierbar.

 

What people are saying - Write a review

We haven't found any reviews in the usual places.

Contents

EINLEITUNG
15
Eine typische Problemstellung für eine MultiRoboterWegplanung
16
STAND DER TECHNIK
21
Einordnung des CoDyAlgorithmus
36
DER CODYALGORITHMUS
37
Einfache Abbildung des optimalen Pfads in einer diskretisierten Umgebung
45
Beispiel für eine vollständig entwickelte Entfernungskarte
48
Ein Beispiel für eine zu klein gewählte Entfernungskarte
49
Lösung der Problemstellung
92
Problemstellung mit einer einzigen Ausweichmöglichkeit
93
Problemstellung bei einer Durchfahrt durch eine stehende Menge
94
Anfangsbelegung der Umgebungskarte
95
Überschreibung der Wegplanung
96
Wegalternativen
97
Beispiel mit Vermeidung sämtliche Konflikte
98
Prioritätsvergleich zwischen den Robotern
99

Eine einfache Hierarchisierung der linken Entfernungskarte
50
Ein Beispiel für einen einfachen RaumZeitKonfigurationsraum
53
Entfernungs und Umgebungskarte
54
Eine Erreichbarkeitskarte über einem eindimensionalem Raum
56
Kollision bei einer zu eng geplanten Bewegung
57
Beispiele für erweiterte Belegungen bei einer geplanten Bewegung
58
Die Wegplanung im Überblick
60
Ein Beispiel mit drei Robotern
62
Anpassung der Umgebungskarte
64
Übernahme von fremden Umgebungsinformationen
65
Vervollständigung der Wegplanungen
67
Wegplanung für Roboter R1
68
Interaktionsmuster für aktive Kooperation
69
Interaktionsmuster CoDyKooperation
71
Schema BlockadeKonflikt
72
Schema MehrfachWarteKonflikt
73
Ein Beispiel für eine Blockadesituation
76
Ein Beispiel für eine Totalblockade
77
Auflösung einer Totalblockade
79
Ein einfaches Beispiel für eine Prioritätsanpassung
80
Ablaufschema bei verketteter Berechnung
82
Die Grundsituation bei zwei entgegenkommenden Robotern
83
Ablaufschema bei paralleler Berechnung
85
Planungsablauf bei paralleler Berechnung
86
Ablaufschema bei versetzter Berechnung
87
Planungsablauf bei versetzter Berechnung
88
Eine Problemstellung ohne Hindernisse
89
Lösung der Problemstellung
90
Problemstellung mit zwei Wegmöglichkeiten
91
Optimierte Wegsuche
100
Beispielsituation mit ineffizientem Ablauf
101
Darstellung eines Roboters bei unterschiedlichen Zellgrößen
106
Beispiel mit Wahrscheinlichkeitsbelegungen
113
ERGEBNISSE
119
Die Oberfläche des MultiRoboterSimulationsprogramms
121
Ein Beispiel mit 32 Roboter mit zufälligen Zielen in einem Gangsystem
122
Beispiel mit 16 Robotern an einer Kreuzung
124
Ein Beispiel mit zwei Gruppen von sechs Robotern
126
Ein Beispiel mit 79 Robotern
128
Ein Beispiel mit zwei Gruppen von je 12 Robotern
130
Ausgangssituation für 6 gegen 6 lockere Vorbeifahrt
132
Ausgangssituation für 6 gegen 6 enge Vorbeifahrt
133
Ausgangssituation für 3 gegen 3 enge Vorbeifahrt
134
Ausgangssituation für 4 gegen 4 enge Vorbeifahrt
135
15FelderSchiebespiel als Kinderspielzeug
136
Vorbeifahrt zweier Roboter
137
Prioritätsdiagramm für eine einfache Verhandlungssituation
138
Prioritätsdiagramm in einer komplexen Verhandlungssituation
139
Aufbau und Struktur des neuen RoboterModells
140
Kamerabild der omnidirektionalen Kamera mit erster Merkmalserkennung
142
Experiment mit vier Robotern an einer Engstelle
146
Experiment mit zwei Paaren von Robotern
147
Robuster Ablauf einer Wegplanung
150
Graphendarstellung eines Verkehrsnetzes
155
Netzplan für ein Fahrerloses Transportsystem
156
ZUSAMMENFASSUNG UND AUSBLICK
159
LITERATURVERZEICHNIS
165
Copyright

Common terms and phrases

A*-Algorithmus Abbildung Algorithmus allerdings Anpassung Ansatz Anzahl von Robotern Aufwand Außerdem Ausweichen beide Roboter Beispiel benötigt Berechnung Berechnungsaufwand Berechnungsschritt Bereich bereits bestimmte beteiligten Roboter Bewegungen Bewegungsplanung Bewegungsschritte Blockade Breitensuche Carpin CoDy CoDy-Algorithmus deshalb Echtzeit einfache einzelnen Roboter Engstelle Entfernungskarte entsprechenden Erreichbarkeitskarte erreicht erste Roboter Fahrerlose Transportsysteme Fahrzeuge Fall gelöst geplanten Wege gesamte Graphen Größe heuristischen Informationen jeweils Karte Knoten Kommunikation komplexen Konfiguration Konfigurationsraum Konflikte konnte lokalen Umgebungskarte Lokalisation max max meist mobile Roboter möglich Multi-Agenten-System Multi-Roboter Multi-Roboter-System muss Nachrichten Objekte Objekterkennung Odometrie omnidirektionale Kamera Parameter Pfade planen Planung Platzkomplexität Position des Roboters prinzipiell Prioritätsangleichung Prioritätswerte Problem Probleme Problemstellung Raum-Zeit-Konfigurationsraum regelbasiertes System relativ Reservierungen RoboCup Robustheit schnell Schritt Sensorik siehe sinnvoll Situation Skalierbarkeit soll statischen Hindernisse Störungen System Systeme tatsächlich Umgebung unterschiedliche Verklemmungen verschiedenen verteiltes System verwendet Verwendung vollständig verteilt Vorbeifahrt Vorteil Wegplanung Wegpunkte Wegschritte Wegstrecke Wegsuche Wegzellen Weltmodell Wert Zeitbedarf Zeitkomplexität Zeitschritte Zellen Zellzerlegung zentralistischen Ziel Zielposition zusätzliche zwei Roboter

About the author (2008)


Bibliographic information