[Back]


Diploma and Master Theses (authored and supervised):

B. Binder:
"Spatio-Temporal Prioritized Planning";
Supervisor: J. Blieberger, M. Bader; Institute of Computer Engineering, 2018; final examination: 2018-01-11.



English abstract:
Using robot fleets have gained popularity in recent years in industrial logistics applications because of their flexible field of application. Therefore, the issue arises how to coordinate these robots. A commonly used approach to this problem is Prioritized Planning, where a coordinator plans all robot's routes sequentially avoiding already planned ones. This thesis presents a new approach for prioritized multi robot path planning. The proposed planner works centralized and generates synchronized and deadlock-free routes for robots. Applying search algorithms on pixel-maps is expensive, therefore, pixel-maps are reduced to search graphs using voronoi distillation. A single robot path planner for use inside a prioritized multi robot path planner is designed. This single robot path planner constrains the creation of new routes by adding already planned ones to the used search graph. To find solutions in this graph the single robot path planner is able to take temporal and spacial constraints into account. Furthermore, potential collisions and deadlocks between robots are avoided by extending the search graph with additional segments if a collision is detected. The global multi robot path planner includes a priority and speed rescheduler as well, to solve specific scenarios which are hard to solve using prioritized path planning. Because the routes are generated time-dependently, they are post-processed to add synchronization markers in form of preconditions for every robot. These preconditions have to be met before a robot is allowed to enter a segment. Selected scenarios with multiple robots are used to compare the proposed planner with state of the art approaches in a simulated environment. Also scenarios are shown to be solvable with the proposed planner, which are not solvable with currently used approaches.

German abstract:
Kurzfassung
Mobile Roboter-Flotten werden aufgrund ihrer flexiblen Einsatzmöglichkeiten in Logisti-
kanwendungen immer beliebter. Mit dem Einsatz von Roboter-Flotten entsteht jedoch
die Notwendigkeit, die einzelnen Roboter in dieser Flotte zu koordinieren. Ein weit
verbreiteter Ansatz, um diese Problemstellung zu lösen, nennt sich "Prioritized Planning".
Hierbei generiert ein Routenplaner alle Routen der Roboter sequenziell und versucht
Überschneidungen mit bereits geplanten Roboter-Routen zu vermeiden.
Diese Diplomarbeit beschäftigt sich mit einem neuen Ansatz für solch einen "Prioritized
Planner". Der vorgestellte Planer erzeugt Routen für mehrere Roboter, welche zueinander
synchron abgearbeitet werden, um Kollisionen und Deadlocks zu vermeiden.
Zur Koordinierung von Robotern werden meist Pixel-Karten eingesetzt. Mit steigender
Pixelanzahl in den Karten wird die Planung der einzelnen Routen immer zeitintensiver.
Aus diesem Grund werden für den erzeugten Planer die Pixel-Karten auf einen Suchgra-
phen reduziert und somit die Dauer des Planungsprozesses verringert.
Es wird ein Planer für einzelne Roboter entwickelt, welcher fähig ist, bereits geplante
Routen von anderen Robotern in den Planungsprozess mit einzubinden. Diese Routen
werden in den Suchgraph des Planers integriert, um so das Ergebnis des nächsten Robo-
ters zu beeinflussen.
Weiters kann mit dem Planer die Verweildauer der einzelnen Roboter in einem Stre-
ckenabschnitt angepasst werden. Dadurch können gegebenfalls Wartezeiten integriert
werden. Sollten bei der Routenplanung dennoch Kollisionen zwischen Robotern auftreten,
können zusätzlich Pfad-Segmente in den Suchgraphen integriert und diese Kollisionen
somit vermieden werden.
Da die erzeugten Routen des Planers zeitabhängig sind, werden diese im Anschluss an den
Planungsprozess synchronisiert. Dabei werden für jeden Routenabschnitt Vorbedingungen
bestimmt, welche erfüllt sein müssen, bevor ein Roboter diesen Routenabschnitt befahren
darf.
Um diverse Szenarien zu lösen, die mit den derzeitig verwendeten "Prioritized Planning"-
Ansätzen nicht lösbar sind, kann der Planer bei fehlgeschlagenen Planungsversuchen den
Planungsprozess mit unterschiedlicher Reihenfolge und Geschwindigkeiten der Roboter
wiederholen.
Für die Evaluierung des neuen Planers, wird dieser mit den aktuell verwendeten Planer-
Ansätzen in einer simulierten Umgebung getestet und die Ergebnisse gegenübergestellt.
Weiters werden, durch den vorgestellten Planer lösbare Szenarien gezeigt, welche durch
aktuell verwendete "Prioritized Planner" nicht lösbar sind.

Keywords:
Robotk, Multi-Robot-Routing, Navigation,

Created from the Publication Database of the Vienna University of Technology.