Loading…
Robot tour planning with high determination costs
Routing under uncertainty
Welz, Wolfgang A.
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.
The automotive industry of today is characterized by an increasing importance of computerization and robotic automation. In order to adapt to the highly flexible production as fast as possible, it is crucial to optimize these processes with mathematical methods.
In this thesis we study one particular optimization problem as it occurs for welding cells. In these cells several robots perform spot welding tasks on the same component within the cycle time. Given the data of the workpiece, the task is to find a feasible sequence of weld points as well as to arrange the trajectory planning for all robots such that the robot arms do not collide with each other.
As for many real-world problems, it is hard to represent this Welding Cell Problem in its entirety by one "scientific" field of research alone. The Welding Cell Problem, on the one hand, has similarities to the famous travelling salesman problem, as it is necessary to determine the best order in which the welding tasks should be processed. On the other hand, it also contains
traditional elements of robot motion planning and optimization.
In the first part of the thesis the practical aspects of the Welding Cell Problem are discussed. In this context we propose a constraint integer programming formulation that efficiently integrates the robot motion planning into a branch-and-price approach for the underlying routing problem.
As the exact trajectory calculations are usually computationally much more expensive, this algorithm focuses on reducing the number of exact trajectory computations required for a feasible solution. Aside from this combination, especially the computational performance of the underlying combinatorial pricing problem is discussed.
This integrated approach leads to the important theoretical problem to minimize the number of exact distance queries while, at the same time, the optimality of the solution needs to be maintained. This question is discussed in the second part.
We explore several of the most famous combinatorial optimization problems (shortest paths, minimum spanning tree and the Travelling Salesman Problem) within this particular uncertainty setting to combine them into an algorithm that is guaranteed to find an approximation algorithm for the TSP under uncertainty that only requires O(n) edge updates in expectation.
This problem relates to the the famous rapid transit challenge, where the entire subway network of a metropolitan area needs to be traversed as fast as possible. Here, techniques that were originally developed in the context of a preprocessing strategy for the Welding Cell Problem can be used for a branch-and-cut approach that uses subtour elimination constraints to compute the optimal tour for the Berlin subway challenge in less than a second.
