Authors:	Dorn, Sebastian
Advisor:	Schömer, Elmar
Title:	Assembly sequence planning for complex real-world CAD data
Online publication date:	9-Sep-2022
Year of first publication:	2022
Language:	english
Abstract:	This work investigates algorithms for digital assembly sequence planning. The focus here is on finding feasible assembly sequences for a real-world data set from the automotive industry. Flexible fastening elements that have to be deformed when being disassembled, a large workspace in which the components are located and a very high number of assembled parts push conventional assembly sequence algorithms to their technical and temporal limits when it comes to real-world data. In three consecutive chapters of this work, we investigate how to push these boundaries into the feasible range, meaning that we are conducting pioneering research into the calculation of feasible assembly sequences for real-world data. The first part of this thesis presents an approximation of a general Voronoi diagram which subdivides the workspace at the maximum clearance. We combine a common voxel propagation algorithm with a novel memory-saving data structure. We then discuss different ways to extract a general Voronoi diagram graph. This graph is a roadmap which provides a roughly estimated translational disassembly path for assembled parts, called Voronoi path. The second part of this work introduces our new path planner Expansive Voronoi Tree (EVT). For a given part, the EVT searches along the according Voronoi path for a collision-free disassembly path, consisting of arbitrary translations and rotations. Our experiments show that the EVT finds shorter paths more reliably within shorter calculation time than conventional path planning algorithms. In the third part, we present our framework for finding feasible assembly sequences. We are the first to calculate feasible assembly sequences for a real-world data set. By using two new algorithms, we detect parts that are still enclosed, which significantly reduces the number of path planning requests and, in turn, calculation time. Our framework divides the disassembly process for an assembled part into a NEAR- and FAR planning phase. Using the path planner from Hegewald et al. (2022) which is designed for deformable fasteners, we unlock parts in the NEAR range and then, in the FAR planning phase, navigate them to a nearby goal position using our EVT. The disassembly paths found are then presented in our new, informative and easy-to-read Assembly Priority Graph. Compared to other representation methods our graph is compact but also shows a high number of feasible assembly sequences. This graph is the result of the interplay of all previously mentioned findings and thus the final result of this work. In dieser Arbeit werden Algorithmen zur virtuellen Montageplanung untersucht. Der Fokus liegt hierbei auf dem Finden von zulässigen Montagereihenfolgen für einen Realdatensatz aus der Automobilbranche. Flexible Befestigungselemente, welche während des Ausbauprozesses deformiert werden müssen, ein großer Arbeitsraum, in dem sich die Bauteile befinden sowie die sehr große Anzahl von Montageteilen bringen die gängigen Montagesequenz-Algorithmen bei Realdaten an ihre technischen und zeitlichen Grenzen. In dieser Arbeit werden diese Grenzen in drei aufeinander aufbauenden Kapiteln zum Machbaren hin verschoben, so dass wir als Erste zulässige Montagesequenzen für Realdaten berechnen können. Im ersten Teil der Arbeit wird die Approximation eines general Voronoi diagrams vorgestellt, welches den Arbeitsraum an den Stellen mit maximalem Freiraum unterteilt. Der Voxel-propagierende Algorithmus arbeitet auf unserer neuartigen, Arbeitsspeicher sparenden Datenstruktur. Anschließend diskutieren wir verschiedene Möglichkeiten einen general Voronoi diagram graph zu extrahieren. Dieser Graph wird als Straßennetz interpretiert, welches einen grob geschätzten, translatorischen Ausbaupfad (sogenannter Voronoi Pfad) für montierte Bauteile liefert. Der zweite Teil der Arbeit stellt unseren neuartigen Pfadplaner Expansive Voronoi Tree (EVT) vor. Dieser sucht für ein Bauteil anhand seines Voronoi Pfades nach einem kollisionsfreien Ausbaupfad, welcher aus beliebigen Translationen und Rotationen besteht. Unsere Experimente zeigen, dass der EVT schneller und zuverlässiger kürzere Pfade findet als gängige Pfadplanungsalgorithmen. Im dritten Teil stellen wir unser Framework zum Finden von zulässigen Montagesequenzen vor. Wir sind die Ersten, die für einen Realdatensatz zulässige Montagesequenzen berechnen können. Wir erkennen mit zwei neuartigen Algorithmen aktuell noch eingeschlossene Bauteile, verringern somit die Anzahl von Pfadplanungsanfragen und folglich die Berechnungsdauer enorm. Unser Framework unterteilt den Demontagevorgang von einem montierten Bauteil in einen Nah- und Fernbereich. Wir lösen mit dem für deformierbare Befestigungselemente ausgelegten Pfadplaner von Hegewald u. a. (2022) Bauteile im Nahbereich und navigieren diese anschließend mittels unserem EVT im Fernbereich zu einer nahegelegenen Zielposition.
DDC:	004 Informatik 004 Data processing
Institution:	Johannes Gutenberg-Universität Mainz
Department:	FB 08 Physik, Mathematik u. Informatik
Place:	Mainz
ROR:	https://ror.org/023b0x485
DOI:	http://doi.org/10.25358/openscience-7536
URN:	urn:nbn:de:hebis:77-openscience-e5b831e2-4128-44e8-9046-c4018814c7ed9
Version:	Original work
Publication type:	Dissertation
License:	CC BY
Information on rights of use:	https://creativecommons.org/licenses/by/4.0/
Extent:	xvi, 110 Seiten, Illustrationen, Diagramme
Appears in collections:	JGU-Publikationen