Multi‐Robot Task Allocation for Inspection Problems with Cooperative
Tasks Using Hybrid Genetic Algorithms
C. Liu. Schriftenreihe Mess- und Regelungstechnik der Universität Kassel, Dissertation, (September 2014)
In dieser Dissertation werden Methoden zur optimalen Aufgabenverteilung
in Multirobotersystemen (engl. Multi-Robot Task Allocation – MRTA)
zur Inspektion von Industrieanlagen untersucht. MRTA umfasst die
Verteilung und Ablaufplanung von Aufgaben für eine Gruppe von Robotern
unter Berücksichtigung von operativen Randbedingungen mit dem Ziel,
die Gesamteinsatzkosten zu minimieren. Dank zunehmendem technischen
Fortschritt und sinkenden Technologiekosten ist das Interesse an
mobilen Robotern für den Industrieeinsatz in den letzten Jahren stark
gestiegen. Viele Arbeiten konzentrieren sich auf Probleme der Mobilität
wie Selbstlokalisierung und Kartierung, aber nur wenige Arbeiten
untersuchen die optimale Aufgabenverteilung. Da sich mit einer guten
Aufgabenverteilung eine effizientere Planung erreichen lässt (z.
B. niedrigere Kosten, kürzere Ausführungszeit), ist das Ziel dieser
Arbeit die Entwicklung von Lösungsmethoden für das aus Inspektionsaufgaben
mit Einzel- und Zweiroboteraufgaben folgende Such-/Optimierungsproblem.
Ein neuartiger hybrider Genetischer Algorithmus wird vorgestellt,
der einen teilbevölkerungbasierten Genetischen Algorithmus zur globalen
Optimierung mit lokalen Suchheuristiken kombiniert. Zur Beschleunigung
dieses Algorithmus werden auf die fittesten Individuen einer Generation
lokale Suchoperatoren angewendet. Der vorgestellte Algorithmus verteilt
die Aufgaben nicht nur einfach und legt den Ablauf fest, sondern
er bildet auch temporäre Roboterverbünde für Zweiroboteraufgaben,
wodurch räumliche und zeitliche Randbedingungen entstehen. Vier alternative
Kodierungsstrategien werden für den vorgestellten Algorithmus entworfen:
Teilaufgabenbasierte Kodierung: Hierdurch werden alle möglichen Lösungen
abgedeckt, allerdings ist der Suchraum sehr groß. Aufgabenbasierte
Kodierung: Zwei Möglichkeiten zur Zuweisung von Zweiroboteraufgaben
wurden implementiert, um die Effizienz des Algorithmus zu steigern.
Gruppierungsbasierte Kodierung: Zeitliche Randbedingungen zur Gruppierung
von Aufgaben werden vorgestellt, um gute Lösungen innerhalb einer
kleinen Anzahl von Generationen zu erhalten. Zwei Umsetzungsvarianten
werden vorgestellt. Dekompositionsbasierte Kodierung: Drei geometrische
Zerlegungen wurden entworfen, die Informationen über die räumliche
Anordnung ausnutzen, um Probleme zu lösen, die Inspektionsgebiete
mit rechteckigen Geometrien aufweisen. In Simulationsstudien wird
die Leistungsfähigkeit der verschiedenen hybriden Genetischen Algorithmen
untersucht. Dazu wurde die Inspektion von Tanklagern einer Erdölraffinerie
mit einer Gruppe homogener Inspektionsroboter als Anwendungsfall
gewählt. Die Simulationen zeigen, dass Kodierungsstrategien, die
auf der geometrischen Zerlegung basieren, bei einer kleinen Anzahl
an Generationen eine bessere Lösung finden können als die anderen
untersuchten Strategien. Diese Arbeit beschäftigt sich mit Einzel-
und Zweiroboteraufgaben, die entweder von einem einzelnen mobilen
Roboter erledigt werden können oder die Zusammenarbeit von zwei Robotern
erfordern. Eine Erweiterung des entwickelten Algorithmus zur Behandlung
von Aufgaben, die mehr als zwei Roboter erfordern, ist möglich, würde
aber die Komplexität der Optimierungsaufgabe deutlich vergrößern.