Heuristische Algorithmen zur automatischen Generierung von prozesszeitoptimierten Roboterprogrammen im Bereich von Multi-Robotersystemen

Processing Time Optimization for Multi-Robot Systems Using Heuristic Algorithms

Please always quote using this URN: urn:nbn:de:bvb:29-opus4-159014
  • Angesichts des demographischen Wandels und hohen Kostendrucks werden immer größere Anstrengungen unternommen, um Prozesse zu automatisieren. Dafür werden vermehrt Multi-Robotersysteme (MRS) eingesetzt, in denen mehrere Roboter zeitgleich in einer Zelle agieren, um standardisierte und wiederkehrende Aufgaben effizient und vollautomatisch abzuarbeiten. In der Automobilindustrie stellt dies aufgrund der hohen Komplexität in der Produktion eine große Herausforderung dar. Einerseits besteht eine enorme kombinatorische Vielfalt bei der Prozessauslegung. Dies beinhaltet die Aufteilung der Aufgaben auf die verfügbaren Roboter, die Festlegung der Bearbeitungssequenz und die Anpassung derAngesichts des demographischen Wandels und hohen Kostendrucks werden immer größere Anstrengungen unternommen, um Prozesse zu automatisieren. Dafür werden vermehrt Multi-Robotersysteme (MRS) eingesetzt, in denen mehrere Roboter zeitgleich in einer Zelle agieren, um standardisierte und wiederkehrende Aufgaben effizient und vollautomatisch abzuarbeiten. In der Automobilindustrie stellt dies aufgrund der hohen Komplexität in der Produktion eine große Herausforderung dar. Einerseits besteht eine enorme kombinatorische Vielfalt bei der Prozessauslegung. Dies beinhaltet die Aufteilung der Aufgaben auf die verfügbaren Roboter, die Festlegung der Bearbeitungssequenz und die Anpassung der Prozesseinstellungen. Andererseits erweist sich aufgrund der engen und dynamischen Roboterarbeitsräume die Bewegungsplanung als äußerst rechenintensiv. Ziel dieser Arbeit ist es daher, mit Hilfe von heuristischen Algorithmen den manuellen Aufwand für die Roboterprogrammerstellung zu minimieren und die Effizienz von Multi-Robotersystemen zu maximieren. Die in dieser Arbeit vorgestellten Verfahren zielen auf Prozesse ab, in denen Roboter einen vordefinierten Pfad folgen müssen, um eine Aufgabe auszuführen. Die Bewegungen zum Verbinden der Aufgaben können dahingegen auf einem beliebigen Pfad durchgeführt werden. Für die Bewegungsplanung wird der Probabilistic-Roadmap-Algorithmus implementiert. Dazu wird eine neue Abtaststrategie verwendet, um die Roboterarbeitsräume durch Graphen zu diskretisieren. Die vielversprechendsten Verbindungen zwischen den Aufgaben werden durch eine Metrik identifiziert und in einer Inzidenzliste abgespeichert. Jede Verbindung wird zusätzlich während der Erstellung des Graphen durch Simulated Annealing weiter optimiert. Für die Bewegungsplanung ist eine schnelle und präzise Kollisionserkennung dargelegt. Die oben genannte Problemformulierung wird in einem neuen Format beschrieben, wodurch sie auf ein Multiple-Depot-Multiple-Travelling-Salesmen-Problem (MDMTSP) mit einigen prozessspezifischen Nebenbedingungen abstrahiert werden kann. Auf diese Weise lässt sich jede Meta-Heuristik ohne hohem Anpassungsaufwand für die Lösungsfindung heranziehen. Für die Prozessoptimierung wird in dieser Arbeit eine neue Implementierung des genetischen Algorithmus angewendet, der in Kombination mit dem vorliegenden Format effizient eine Population mit gültigen Lösungen aufbaut. Zur Verbesserung der Konvergenzeigenschaft des genetischen Algorithmus werden verschiedene Methoden erarbeitet. Zum einen wird die Mutationsrate nach einer bestimmtem Vorschrift aktiv geregelt. Zum anderem wird ein Reactive-Search-Ansatz verfolgt, der die Auswahl geeigneter Prozesseinstellungen bevorzugt. Die Lösungsqualität des genetischen Algorithmus wird durch einen exakten Solver anhand eines Benchmark-Problems verifiziert. Für den Lastausgleich werden Aufgaben in Abhängigkeit ihrer Position relativ zu den Roboterarbeitsräumen geclustert, um unvorteilhafte Aufteilungen von vornherein auszuschließen, bei denen sich die Roboter gegenseitig blockieren. Die Algorithmen wurden auf ein reales Geschäftsproblem im Bereich der PVC-Versiegelung angewendet. Hierdurch ließen sich kollisionsfreie und abfahrbare Roboterprogramme generieren, die den nicht wertschöpfenden Anteil der Prozesszeit um bis zu 17% reduzieren können.show moreshow less
  • In the face of demographic change and high cost pressures, ever greater efforts are being made to automate processes. For this purpose, multi-robot systems (MRS) are increasingly used. In a MRS several robots act simultaneously in a cell in order to process standardized and recurring tasks efficiently and fully automated. In the automotive industry this is a major challenge due to the high level of complexity in production. On the one hand, there is an enormous combinatorial diversity in the process design. This includes the assignment of the tasks to the available robots, the selection of the processing sequence and the adjustment of the process settings. On the other hand, motionIn the face of demographic change and high cost pressures, ever greater efforts are being made to automate processes. For this purpose, multi-robot systems (MRS) are increasingly used. In a MRS several robots act simultaneously in a cell in order to process standardized and recurring tasks efficiently and fully automated. In the automotive industry this is a major challenge due to the high level of complexity in production. On the one hand, there is an enormous combinatorial diversity in the process design. This includes the assignment of the tasks to the available robots, the selection of the processing sequence and the adjustment of the process settings. On the other hand, motion planning proves to be computationally intensive because of narrow and dynamic robot workspaces. The aim of this work is therefore to minimize the manual effort for robot programming and maximize the efficiency of multi-robot systems with the help of heuristic algorithms. The solutions presented in this work target processes in which robots must follow a predefined path to perform a task. The path to connect the tasks, on the other hand, can be done following any path. For the motion planning, the probabilistic roadmap algorithm is implemented. Here, a new sampling strategy is used to discretize the robot workspaces through graphs. The most promising task connections are identified by a metric and stored in an incidence list. In addition, each connection is further optimized by simulated annealing during the creation of the graphs. A fast and precise collision detection is shown for the motion planning. The above problem formulation is described in a new format so that it can be abstracted to a multiple depot multiple traveling salesmen problem (MDMTSP) with some process-specific constraints. In this way, any meta-heuristic can be used without a high effort for adjustments. For process optimization, a new implementation of the genetic algorithm is applied in this work. In combination with the presented format, it efficiently generates a population with valid solutions. The convergence behavior of the genetic algorithm is improved by various methods. On the one hand, the mutation rate is actively regulated following a specific rule. On the other hand, a reactive search approach is used in order to privilege the selection of suitable process settings. The solution quality of the genetic algorithm is verified by an exact solver based on a benchmark problem. For load balancing, tasks are clustered according to their location relative to the robot workspaces. Doing this, bad task allocations, in which the robots block each other, are excluded from the outset. The algorithms were applied to a real business problem in the field of PVC sealing. It is possible to generate collision-free and executable robot programs that reduce the non-value-adding portion of the process time by up to 17%.show moreshow less

Download full text files

Export metadata

Additional Services

Share in Twitter Search Google Scholar Statistics
Metadaten
Author:Murad Muradi
Persistent identifiers - URN:urn:nbn:de:bvb:29-opus4-159014
Referee:Rolf Wanka, Martin Gugat
Advisor:Rolf Wanka
Document Type:Doctoral Thesis
Language:German
Year of publication:2021
Date of online publication (Embargo Date):2021/02/19
Publishing Institution:Friedrich-Alexander-Universität Erlangen-Nürnberg (FAU)
Granting institution:Friedrich-Alexander-Universität Erlangen-Nürnberg (FAU), Technische Fakultät
Acceptance date of the thesis:2021/01/22
Release Date:2021/03/01
Tag:Bewegungsplanung; Kollisionserkennung; Prozessoptimierung; Robotik; Rundreiseproblem
Load Balancing; Scheduling
Institutes:Technische Fakultät
Dewey Decimal Classification:0 Informatik, Informationswissenschaft, allgemeine Werke / 00 Informatik, Wissen, Systeme / 006 Spezielle Computerverfahren
open_access (DINI-Set):open_access
Licence (German):Keine Creative Commons Lizenz - es gilt der Veröffentlichungsvertrag und das deutsche Urheberrecht