The automatic generation of (dis)assembly sequences for complex technical products is a challenging field. Complex products like vehicles consist of numerous different components. Determining the sequence using a brute-force-approach by testing all components for disassembly one after another in a loop until all components are disassembled is laborious and costly. In industrial scenarios, a large proportion of the components are fasteners. In this paper, we propose a new framework which improves the disassembly sequencing generation by prioritizing fasteners during planning. Our proposed framework comprises a preprocessing in which fasteners are identified with a convolutional neural network within a dataset and a procedure that preferentially and automatically checks fasteners for disassembly. The algorithm takes initial and unavoidable collisions of the fasteners into account. We show the effectiveness of our approach on real-world data from the automotive industry. A new synthetic dataset of fasteners for training neural networks is available.

We present the first realization of an assembly sequence planning framework for large-scale and complex 3D real-world CAD scenarios. Other than in academic benchmark data sets, in our scenario each assembled part is allowed to contain flexible fastening elements and the number of assembled parts is quite high. With our framework we are able to derive a meaningful assembly priority graph for the parts. Our framework divides the disassembly motion of each part into a NEAR- and a subsequent FAR planning phase and uses existing specialized motion planners for each phase. To reduce the number of unsuccessful motion planning requests we use a general Voronoi diagram graph and a novel collision perceiving method which significantly speed up our framework. At the end, we create an assembly priority graph to indicate which parts must be disassembled before others. In our experiments, we show that our framework is the first one which is able to generate a priority graph for a representative data set from the automotive industry. Moreover, the reported disassembly motions for the individual parts are shorter and can be computed faster than with other state-of-the-art frameworks.

Automatic disassembly planning for complex industrial products like vehicles checks the expandability of components already at early stages of design. For a fast computation of collision-free disassembly paths, sampling-based rigid body motion planning is used in the literature. However, in real-world scenarios there are circumstances that prevent the finding of plausible collision-free disassembly paths with these conventional motion planners. The most difficult problem is that many components have deformable fastening elements that are modeled in a relaxed state and often as a part of the rigid object. The fastening elements cause unavoidable collisions of the component with its environment along the actual disassembly path. In this paper, we present Iterative Mesh Modification Planning (IMMP). Given the information about fastening elements in advance, our method applies a controlled iterative process of geometric deformations and planning attempts to the component to be disassembled. With this process, we are able to disassemble the component from its installed position with a conventional rigid body motion planner taking fastening elements and also overpressure into account. We demonstrate the effectiveness of our method on real-world planning scenarios from the automotive industry.

Developing neural networks for supervised multi-class classification has become important for theory and practice. An essential point is the design of the underlying network. Beside single-network approaches there are several multi-class patterns which decompose a classification problem into multiple sub-problems and derive systems of neural networks. We show that existing multi-class patterns can be improved by a new and simple labeling scheme for the training of the sub-problems. We efficiently derive a class hierarchy which is optimized for our labeling scheme and, unlike most of existing works, has no schematic restrictions. Based on that we introduce a hierarchical multi-class pattern, called ConfusionTree-pattern, which is able to reach high classification accuracies. Our experiments show that our multi-class ConfusionTree-pattern reaches state-of-the-art results regarding performance and efficiency.

One major challenge in Assembly Sequence Planning (ASP) for complex real-world CAD-scenarios is to find an appropriate disassembly path for each assembled part. Complex real-world scenes are characterized by a large installation space. There each part has many different possible disassembly paths that differ in length and clearance. However, due to tight packing in the installation space, these paths can contain narrow passages. Therefore a motion planner is needed that is able to globally search for a reasonable path and to locally overcome narrow passages. Moreover, since motion planning requests are executed in the ASP context over and over again for many parts, both for those that can be disassembled in the next step and for those that cannot be yet, the motion planner has to be reliably fast.We present a new rigid body motion planner, called Expansive Voronoi Tree (EVT), which is optimized for complex ASP scenarios. The EVT estimates a globally reasonable path using a General Voronoi Diagram of the complete scene. With a novel EST-based sampling strategy, which is the contribution of this paper, it then locally explores the environment along the estimated path. The EVT automatically adapts to different clearance situations. It passes wide environments quickly and samples densely at narrow passages.We compare our EVT to state of the art motion planners which use different sampling strategies on a real-world data set consisting of a large subset of a car. The experiments show that the EVT is reliably many times faster and delivers shorter paths.

In this paper, we consider disassembly scenarios for real-world 3D CAD-data, where each component is defined by a triangle mesh. For a fast construction of collision-free disassembly paths, common approaches use sampling-based rigid body motion planning which is well studied in the literature. One fact that has so far received little attention is that in industrial disassembly scenarios components are often attached to each other with flexible fastening elements like clips. In the planning process, the fastening elements show the following characteristics: 1) They can cause complex non-linear disassembly paths. 2) They are often deformable. 3) They are usually modeled in a relaxed state and as an unknown part of the rigid mesh. That leads to the problem that unavoidable collisions occur during the planning process. Hence, the localization of the fastening elements and the integration of this information into the motion planning process is crucial for an automatic disassembly.We present a new geometric solution to extract salient features of 3D meshes which is specialized to find the fastening elements within the otherwise rigid mesh. Our approach measures a vertex-based surface feature using a local Gauss map in combination with a local thickness computation of the mesh. We compare our surface feature to state-of-the-art mesh saliency methods on various examples. Further, we integrate this measure of per-vertex saliency into a motion planning process and demonstrate the effectiveness of our result on real-world planning scenarios from the automotive industry.

One major challenge in Assembly Sequence Planning (ASP) for complex real-world CAD-scenarios is to find appropriate disassembly paths for all assembled parts. Such a path places demands on its length and clearance. In the past, it became apparent that planning the disassembly path based on the (approximate) General Voronoi Diagram (GVD) is a good approach to achieve these requirements. But for complex real-world data, every known solution for computing the GVD is either too slow or very memory consuming, even if only approximating the GVD.We present a new approach for computing the approximate GVD and demonstrate its practicability using a representative vehicle data set. We can calculate an approximation of the GVD within minutes and meet the accuracy requirement of some few millimeters for the subsequent path planning. This is achieved by voxelizing the surface with a common error-bounded GPU render approach. We then use an error-bounded wavefront propagation technique and combine it with a novel hash table-based data structure, the so-called Voronoi Voxel History (VVH). On top of the GVD, we present a novel approach for the creation of a General Voronoi Diagram Graph (GVDG) that leads to an extensive roadmap. For the later motion planning task this roadmap can be used to suggest appropriate disassembly paths.

In sampling-based 3D rigid body motion planning one of the major subroutines is collision detection. Especially for problems with narrow passages many samples have to be checked by a collision detection algorithm. In this application, the runtime of the motion planning algorithm is dominated by collision detection and the samples have the very specific characteristic that many of them are in collision and have small penetration volumes. In our work, we introduce a data structure and an algorithm that makes use of this characteristic by combining well-known data structures like a distance field and an octree with the swap algorithm by Llanas et al. For 3D rigid body motion planning with narrow passages, our approach achieves a speedup of up to 5.0 compared to well-established collision detection libraries like the Proximity Query Package (PQP) and the Flexible Collision Library (FCL).

Nowadays sampling-based motion planners use the power of randomization to compute multidimensional motions at high performance. Nevertheless the performance is based on problem-dependent parameters like the weighting of translation versus rotation and the planning range of the algorithm. Former work uses constant user-adjusted values for these parameters which are defined a priori. Our new approach extends the power of randomization by varying the parameters randomly during runtime. This avoids a preprocessing step to adjust parameters and moreover improves the performance in comparison to existing methods in the majority of the benchmarks. Our method is simple to understand and implement. In order to compare our approach we present a comprehensive experimental analysis about the parameters and the resulting performance. The algorithms and data structures were implemented in our own library RASAND, but we also compare the results of our work with OMPL [12] and the commercial software Kineo™ Kite Lab [15].

We present an extension of snap roundingfrom straight-line segments (see Guibas and Marimont, 1998)to Bézier curves of arbitrary degree, and thus the first method for geometric roundingof curvilinear arrangements.Our algorithm takes a set of intersecting Bézier curvesand directly computes a geometric rounding of their true arrangement, without the need of representing the true arrangement exactly.The algorithm's output is a deformation of the true arrangementthat has all Bézier control points at integer pointsand comes with the same geometric guarantees as instraight-line snap rounding: during rounding, objects do not movefurther than the radius of a pixel, and features of thearrangement may collapse but do not invert.

An algorithm is presented for the geometric analysis of an algebraic curve f(x, y) = 0 in the real affine plane. It computes a cylindrical algebraic decomposition (CAD) of the plane, augmented with adjacency information. The adjacency information describes the curve's topology by a topologically equivalent planar graph. The numerical data in the CAD gives an embedding of the graph.

We present the first exact, complete and efficient implementation that computes for a given set P=p1,...,pn of quadric surfaces the planar map induced by all intersection curves p1∩ pi, 2 ≤ i ≤ n, running on the surface of p1. The vertices in this graph are the singular and x-extreme points of the curves as well as all intersection points of pairs of curves. Two vertices are connected by an edge if the underlying points are connected by a branch of one of the curves. Our work is based on and extends ideas developed in [20] and [9].Our implementation is complete in the sense that it can handle all kind of inputs including all degenerate ones where intersection curves have singularities or pairs of curves intersect with high multiplicity. It is exact in that it always computes the mathematical correct result. It is efficient measured in running times.

We consider the problem of computing a representation of the plane graph induced by one (or more) algebraic curves in the real plane. We make no assumptions about the curves, in particular we allow arbitrary singularities and arbitrary intersection. This problem has been well studied for the case of a single curve. All proposed approaches to this problem so far require finding and counting real roots of polynomials over an algebraic extension of Q, i.e. the coefficients of those polynomials are algebraic numbers. Various algebraic approaches for this real root finding and counting problem have been developed, but they tend to be costly unless speedups via floating point approximations are introduced, which without additional checks in some cases can render the approach incorrect for some inputs.We propose a method that is always correct and that avoids finding and counting real roots of polynomials with non-rational coefficients. We achieve this using two simple geometric approaches: a triple projections method and a curve avoidance method. We have implemented our approach for the case of computing the topology of a single real algebraic curve. Even this prototypical implementation without optimizations appears to be competitive with other implementations.

The Bentley-Ottmann sweep-line method can be used to compute thearrangement of planar curves provided a number of geometricprimitives operating on the curves are available. We discuss themathematics of the primitives for planar algebraic curves of degreethree or less and derive efficient realizations. As a result, weobtain a complete, exact, and efficient algorithm for computingarrangements of cubic curves. Conics and cubic splines are specialcases of cubic curves. The algorithm is complete in that it handles all possibledegeneracies including singularities. It is exact in that itprovides the mathematically correct result. It is efficient in thatit can handle hundreds of curves with a quarter million of segmentsin the final arrangement.

We present two approaches to the problem of calculating a cell in a 3- dimensional arrangement of quadrics. The first approach solves the problem using rational arithmetic. It works with reductions to planar arrangements of algebraic curves. Degenerate situations such as tangential intersections and self-intersections of curves are intrinsic to the planar arrangements we obtain. The coordinates of the intersection points are given by the roots of univariate polynomials. We succeed in locating all intersection points either by extended local box hit counting arguments or by globally characterizing them with simple square root expressions. The latter is realized by a clever factorization of the univariate polynomials. Only the combination of these two results facilitates a practical and implementable algorithm.

The treatment of curved algebraic surfaces becomes more and more the f ocus of attention in Computational Geometry. We present a video that illustrates the computation of the convex hull of a set of ellipsoids. The underlying algorithm is an application of our work on determining a cell in a 3-dimensional arrangement of quadrics, see \cite{ghs-ccaq-01}. In the video, the main emphasis is on a simple and comprehensible visualization of the geometric aspects of the algorithm. In addition, we give some insights into the underlying mathematical problems.