Article A general framework for assembly planning: the motion space approach Share on Authors: Dan Halperin Department of Computer Science, Tel Aviv University, Tel Aviv 69978, Israel Department of Computer Science, Tel Aviv University, Tel Aviv 69978, IsraelView Profile , Jean-Claude Latombe Department of Computer Science, Stanford University, Stanford, CA Department of Computer Science, Stanford University, Stanford, CAView Profile , Randall H. Wilson Eastman Kodak Company, Albuquerque, NM Eastman Kodak Company, Albuquerque, NMView Profile Authors Info & Claims SCG '98: Proceedings of the fourteenth annual symposium on Computational geometryJune 1998 Pages 9–18https://doi.org/10.1145/276884.276886Online:07 June 1998Publication History 8citation507DownloadsMetricsTotal Citations8Total Downloads507Last 12 Months1Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

Constraints on assembly plans vary depending on product, assembly facility, assembly volume, and many other factors. Assembly costs and other measures to optimize vary just as widely. To be effective, computer-aided assembly planning systems must allow users to express the plan selection criteria that apply to their products and production environments. We begin by surveying the types of user criteria, both constraints and quality measures, that have been accepted by assembly planning systems to date. The survey is organized along several dimensions, including strategic versus tactical criteria; manufacturing requirements versus requirements of the automated planning process itself; and the information needed to assess compliance with each criterion. The latter strongly influences the efficiency of planning. We then focus on constraints. We describe a framework to support a wide variety of user constraints for intuitive and efficient assembly planning. Our framework expresses all constraints on a sequencing level, specifying orders and conditions on part mating operations in a number of ways. Constraints are implemented as simple procedures that either accept or reject assembly operations proposed by the planner. For efficiency, some constraints are supplemented with special-purpose modifications to the planner's algorithms. Fast replanning enables an interactive plan-view-constrain-replan cycle that aids in constraint discovery and documentation. We describe an implementation of the framework in a computer-aided assembly planning system and experiments applying the system to a number of complex assemblies, including one with 472 parts.

Constraints on assembly plans vary depending on product, assembly facility, assembly volume, and many other factors. This paper describes the principles and implementation of a framework that supports a wide variety of user-specified constraints for interactive assembly planning. Constraints from many sources can be expressed on a sequences level, specifying orders and conditions on part mating operations in a number of ways. All constraints are implemented as filters that either accept or reject assembly operations proposed by the planner. For efficiency, some constraints are supplemented with special-purpose modifications to the planner's algorithms. Fast replanning enables a natural plan-view-constrain-replan cycle that aids in constraint discovery and documentation. We describe an implementation of the framework in a computer-aided assembly planning system and experiments applying the system to several complex assemblies.

The goal of assembly sequencing is to plan a feasible series of operations to construct a product from its individual parts. Previous research has investigated assembly sequencing under the assumption that parts have nominal geometry. This paper considers the case where parts have toleranced geometry. Its main contribution is an efficient procedure that decides if a product admits an assembly sequence with infinite translations (i.e. translations that can be extended arbitrarily far along a fixed direction), that is feasible for all possible instances of the components within the specified tolerances. If the product admits one such sequence, the procedure can also generate it. For the cases where there exists no such assembly sequence, another procedure is proposed which generates assembly sequences that are feasible only for some values of the toleranced dimensions. If this procedure produces no such sequence, then no instance of the product is assemblable. These two procedures are described for 2D assemblies made of polygonial parts and for 3D assemblies made of polyhedral parts. So far, only the first has been implemented (for the planar case). This work assumes a simple, but non-trivial tolerance language that falls short of capturing all imperfections of a manufacturing process. In particular, it assumes that faces and edges have perfect relative orientations. Thus, it is only one step towards dealing with tolerances in assembly sequencing.

This paper is a survey of constraints used in automated assembly planning, where "constraints" are interpreted broadly to include requirements, preferences, and suggestions to the planner. We list a large number of constraints that have appeared in the assembly planning literature and categorize them along several dimensions. These dimensions include strategic vs. tactical constraints; requirements vs. criteria to optimize vs. suggestions; and constraints encoding manufacturing requirements vs. those imposed by the automated planning process itself. We also consider the information needed to assess each constraint, particularly as it affects the efficiency of planning with the constraint. Finally, we present our planned framework for incorporating many of the surveyed constraints into an interactive version of the Archimedes assembly planner.

We describe the implementation and performance of Archimedes 2, an integrated mechanical assembly planning system. Archimedes 2 includes two planners, two assembly sequence animation facilities, and an associated robotic workcell. Both planners use fully 3 dimensional data. A rudimentary translator from high level assembly plans to control code for the robotic workcell has also been implemented. We can translate data from a commercial CAD system into input data for the system, which has allowed us to plan assembly sequences for many industrial assemblies. Archimedes 2 has been used to plan sequences for assemblies consisting of 5 to 109 parts. We have also successfully taken a CAD model of an assembly, produced an optimized assembly sequence for it, and translated the plan into robot code, which successfully assembles the device specified in the model.

When assembling a product, humans, robots, and other automation employ a variety of tools to manipulate, attach, and test parts and subassemblies. This paper proposes a framework to represent and reason about geometric accessibility constraints for a wide variety of assembly tools. Central to the framework is a volume encoding a minimum space that must be free in an assembly state to apply a given tool, and constraints on the placement of that volume relative to the parts on which the tool acts. Determining whether a tool can be applied in a given assembly state is an instance of the FINDPLACE problem. In addition, we present more efficient methods to integrate the framework into assembly planning. For tools that are applied either before or after their target parts are mated, one method preprocesses a single tool application for all possible states of assembly. For tools applied after their target parts are mated, a complementary method guarantees polynomial-time assembly planning. We describe experiments with an initial implementation of the framework and a library of eight tools.

We study the following problem: Given a collection A of polyhedral parts in 3D, determine whether there exists a subset S of the parts that can be moved as a rigid body by an infinitesimal translation and rotation, without colliding with the rest of the parts, AS. A negative result implies that the object whose constituent parts are the collection A cannot be taken apart with two hands. A positive result, together with the list of movable parts in S and a direction of motion for S, can be used by an assembly sequence planner. This problem has attracted considerable attention within and outside the robotics community. We devise an efficient algorithm to solve this problem. Our solution is based on the ability to focus on selected portions of the tangent space of rigid motions and efficiently access these portions. The algorithm is complete (in the sense that it is guaranteed to find a solution if one exists), simple, and improves significantly over the best previously known solutions. We report experimental results with an implementation of our algorithm.

We consider the following problem that arises in assembly planning: given an assembly, identify a subassembly that can be removed as a rigid object without disturbing the rest of the assembly. This is the assembly partitioning problem. Specifically, we consider planar assemblies of simple polygons and subassembly removal paths consisting of a single finite translation followed by a translation to infinity. Such paths are typical of the capabilities of simple actuators in fixed automation and other high-volume assembly machines. We present a polynomial-time algorithm to identify such a subassembly and removal path. We discuss extending the algorithm to 3D, other types of motions typical in non-robotic automated assembly, and motions consisting of more than two translations.

This paper describes an interactive computer-aided assembly planning system that greatly reduces the human input required to construct assembly plans. The system takes a dual approach. First, most assembly operations are validated automatically from the CAD models of the assembly's parts using simple, fast techniques. Second, with each query the user is allowed to identify a set of parts that constrain a subassembly; the system uses this information to answer future queries automatically. This dual approach has proven quite powerful in experiments on real assemblies, reducing the number of queries by orders of magnitude over previous systems without sacrificing accuracy.>

In which order can a product be assembled or disassembled? How many hands are required? How many degrees of freedom? What parts should be withdrawn to allow the removal of a specified subassembly? To answer such questions automatically, important theoretical issues in geometric reasoning must be addressed. This paper investigates the planning of assembly algorithms specifying (dis) assembly operations on the components of a product and the ordering of these operations. It also presents measures to evaluate the complexity of these algorithms and techniques to estimate the inherent complexity of a product. The central concept underlying these planning and complexity evaluation techniques is that of a “non-directional blocking graph”, a qualitative representation of the internal structure of an assembly product. This representation describes the combinatorial set of parts interactions in polynomial space. It is obtained by identifying physical criticalities where geometric interferences among parts change. It is generated from an input geometric description of the product. The main application considered in the paper is the creation of smart environments to help designers create products that are easier to manufacture and service. Other possible applications include planning for rapid prototyping and autonomous robots.

The problem of partitioning an assembly of polyhedral objects into two subassemblies that can be separated arises in assembly planning. The authors describe an algorithm to compute the set of all translations separating two polyhedra with n vertices in O(n/sup 4/) steps and show that this is optimal. Given an assembly of k polyhedra with a total of n vertices, an extension of this algorithm identifies a valid translation and removable subassembly in O(k/sup 2/n/sup 4/) steps if one exists. Based on the second algorithm, a polynomial time method for finding a complete assembly sequence consisting of single translations is derived. An implementation incorporates several changes to achieve better average-case performances. Experimental results obtained for composite objects consisting of isothetic polyhedra are described.>

The problem of partitioning an assembly into two subassemblies that can be separated arises in assembly planning. We consider assemblies of rigid parts whose contacts are equivalent, in terms of motion constraints, to finite sets of point-plane contact constraints. This type of contact includes all stable contacts between polyhedra as well as the large majority of contacts seen in industrial assemblies. For such assemblies, we describe a general algorithm to And a subassembly that is free to rotate and translate a small distance from the rest of the assembly. For assemblies with m contacts described as k point-plane constraints, the algorithm has a worst-case time bound of 0(~k5).

The problem of generating assembly sequences strictly from the geometry of a goal assembly is addressed. The planner considers 2-D, polygonal parts and makes the usual assumptions about the monotony of partial assemblies, which allows an 'and/or' graph representation to be used. The problem of decreasing the number of geometric checks which must be done to test candidate assembly operations is also addressed. This is accomplished by replacing them with dependency checks which try to reuse previous geometric computations. The results of several experiments are shown.>