Dissertation
Fachgebiet Mess- und Regelungstechnik, Schriftenreihe "Mess- und Regelungstechnik der Universität Kassel" (FB 15 / Maschinenbau)
Schriftenreihe Mess- und Regelungstechnik der Universität Kassel (Fachgebiet Mess- und Regelungstechnik)
Multi-Robot Task Allocation for Inspection Problems with Cooperative Tasks Using Hybrid Genetic Algorithms
Abstract
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.
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.
Additional Information
Zugl.: Kassel, Univ., Diss. 2014Collections
kup - kassel university press (Digitale Bibliotheksdienste)Fachgebiet Mess- und Regelungstechnik, Schriftenreihe "Mess- und Regelungstechnik der Universität Kassel" (FB 15 / Maschinenbau)
Schriftenreihe Mess- und Regelungstechnik der Universität Kassel (Fachgebiet Mess- und Regelungstechnik)
Citation
@phdthesis{urn:nbn:de:hebis:34-2014101646126,
author={Liu, Chun},
title={Multi-Robot Task Allocation for Inspection Problems with Cooperative Tasks Using Hybrid Genetic Algorithms},
school={Kassel, Universität, FB 15, Maschinenbau},
year={2014}
}
0500 Oax 0501 Text $btxt$2rdacontent 0502 Computermedien $bc$2rdacarrier 1100 2014$n2014 1500 1/eng 2050 ##0##urn:nbn:de:hebis:34-2014101646126 3000 Liu, Chun 4000 Multi-Robot Task Allocation for Inspection Problems with Cooperative Tasks Using Hybrid Genetic Algorithms / Liu, Chun 4030 4060 Online-Ressource 4085 ##0##=u http://nbn-resolving.de/urn:nbn:de:hebis:34-2014101646126=x R 4204 \$dDissertation 4170 Schriftenreihe Mess- und Regelungstechnik der Universität Kassel ;; 4 7136 ##0##urn:nbn:de:hebis:34-2014101646126
2014-10-16T06:51:47Z 2014-10-16T06:51:47Z 2014 urn:nbn:de:hebis:34-2014101646126 http://hdl.handle.net/123456789/2014101646126 Zugl.: Kassel, Univ., Diss. 2014 eng kassel university press Urheberrechtlich geschützt https://rightsstatements.org/page/InC/1.0/ 620 Multi-Robot Task Allocation for Inspection Problems with Cooperative Tasks Using Hybrid Genetic Algorithms Dissertation 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. open access Liu, Chun 148 Seiten Schriftenreihe Mess- und Regelungstechnik der Universität Kassel ;; 4 Kassel, Universität, FB 15, Maschinenbau Kroll, Andreas (Univ.-Prof. Dr.-Ing.) Jakob, Wilfried (Dr.-Ing.) 978-3-86219-551-0 Schriftenreihe Mess- und Regelungstechnik der Universität Kassel 4 2014-09-09 true Schriftenreihe Mess- und Regelungstechnik der Universität Kassel Naturwissenschaft, Technik, Informatik, Medizin Dissertation Softcover 17 x 24
The following license files are associated with this item:
:Urheberrechtlich geschützt