Robot tour planning with high determination costs

Abstract

In der Automobilindustrie spielt die Computerisierung eine immer größer werdende Rolle. Deshalb und aus Kostengründen ist es vorteilhaft, die auftretenden Prozesse mit mathematischen Methoden zu optimieren. Nur so kann auch automatisch sofort auf Änderungen des Produktionsprozesses reagiert werden. In der vorliegenden Arbeit wird hierzu ein Beitrag geleistet, indem sogenannte Schweißzellen studiert werden, in denen mehrere Roboterarme gleichzeitig Schweißpunkte an demselben Werkstück vornehmen. Dabei sind die Touren dieser Schweißroboter so zu planen, dass die notwendigen Schweißpunkte in möglichst kurzer Zeit abgefahren werden, ohne dass es zu Kollisionen zwischen den Robotern kommt. Wissenschaftlich gesehen besteht diese Optimierungsaufgabe, das "Welding Cell Problem", aus Aspekten zweier klassischer Bereiche der Mathematik: Es hat auf der einen Seite Ähnlichkeiten mit dem berühmten "Problem des Handlungsreisenden", in dem eine optimale kollisionsfreie Reihenfolge der Punkte bestimmt werden muss. Auf der anderen Seite enthält es auch klassische Elemente der Bewegungsplanung und -optimierung der Robotik. Im ersten Teil der Arbeit werden die eher praktischen Probleme des Welding Cell Problems untersucht. In diesem Zusammenhang stellen wir einen Algorithmus vor, der die beiden Teile dieses Problems kombiniert, indem die kontinuierliche Bewegungsplanung direkt in den branch-and-price-Prozess des diskreten Teils integriert wird. Da die Trajektorienberechnung rechnerisch viel aufwändiger ist als die diskrete Optimierung, wurde bei diesem Ansatz besonderer Wert darauf gelegt, unnötige Pfadberechnungen zu vermeiden. Dieser Ansatz führt auch zu der wichtigen theoretischen Frage, wie viele dieser Berechnungen im Minimum erforderlich sind um eine optimale Lösung garantieren zu können. Diese Frage wird im zweiten Teil genauer analysiert. Dazu werden einige klassische kombinatorische Probleme (kürzeste Wege, minimal spannende Bäume und das Problem des Handlungsreisenden) in diesem sogenannten Uncertainty-Szenario betrachtet. Am Ende ist es so möglich einen Approximationsalgorithmus für das TSP mit Unsicherheiten anzugeben, der in Erwartung nur O(n) solcher exakter Distanzberechnungen benötigt. Dieses Problem ähnelt dem "U-Bahn-Problem", bei dem das gesamte U-Bahnnetz einer Großstadt in möglichst kurzer Zeit durchfahren werden muss. Im letzten Kapitel beschrieben wir deshalb einen branch-and-cut Algorithmus, der durch das Hinzufügen von Kurzzyklusungleichungen in der Lage ist, eine optimale Lösung des U-Bahn-Problems für eine Metropole - hier am Beispiel von Berlin - in weniger als einer Sekunde zu berechnen.