A survey of computational approaches to three-dimensional layout problems
Introduction
Component layout plays an important role in the design and usability of many engineering products. The layout problem is also classified under the headings of packing, packaging, configuration, container stuffing, pallet loading or spatial arrangement in the literature. The problem involves the placement of components in an available space such that a set of objectives can be optimized while satisfying optional spatial or performance constraints.
Whereas the technologies for circuit board and IC chip layout have advanced significantly during the past two decades and many commercial CAD tools have been available, the same is not to be said for 3-D mechanical layout methods and tools. While the number of components to be placed in a mechanical system is modest compared to that of a VLSI system, the increased combinatorial complexity over the two-dimensional layout problem and the geometric complexity of 3-D non-uniform components and container spaces make the mechanical layout synthesis a challenging task. Current tools available in practice to designers to aid in the general mechanical layout process mostly remain at the stages of physical or electronic models with the assistance of manual adjustment and visual feedback. The needs arising in the product layout and rapid prototyping for compact and complex products, quick turnaround time and efficient use of resources justify the development of effective layout synthesis methods for 3-D components of complex geometry.
The difficulty in automating the mechanical and electro-mechanical layout process stems from: (1) the modeling of the design objectives and constraints; (2) the efficient calculation of the objectives and constraints; (3) the identification of appropriate optimization search strategies.
A number of design goals can be modeled as layout objectives. Simulations may be necessary to test the thermal, stress or vibration properties of the package. In addition, a set of constraints often has to be satisfied to ensure the applicability of the layouts. Efficient calculations of objectives and constraints are necessary to solve the layout problem in reasonable time since the analyses of objectives and constraints can be computationally expensive and a large number of evaluations may be required to achieve convergence. The search space of the layout problem is non-linear and multi-modal, making it vital to identify a suitable algorithm to navigate the space and find good quality solutions.
Fig. 1 illustrates the major constituent parts for solving a generic layout problem. Geometric representations of components and the container space are necessary for the check of interference and clearance. Since the interference calculation between components of complex geometry is computationally expensive, different levels of detail may be desirable for coarse and refined evaluations at different stages of the problem solving process. The locations and orientations of components are the design variables to be determined. Rigid body transformation is utilized to record the position and orientation of each component in the global coordinate frame. The layout and packaging goals are usually formulated as objective functions. The objectives may reflect the cost, quality, performance and service requirements. Various constraints may be necessary to specify spatial relationships between components. A common constraint is no component overlap and no container protrusion. Other constraints may include the proximity or alignment between components. Topological connections are necessary if tube routing, for example, is involved in addition to the component placement. The specifications of components, objectives, constraints, and topological connections define a layout problem and an optimization search algorithm takes the problem formulation and identifies promising solutions by evaluating design alternatives and evolving design states. Analyses of objectives and constraints vary from problem to problem. However, the optimization search technique and geometric representation and the resulting interference evaluation are problem independent and are, thus, the focus for a generic layout tool.
This paper examines the characteristics of the layout space and provides a survey of the current state-of-the-art in technologies for the 3-D layout problem. The paper is organized as follows: Section 2 shows a fractal analysis of the layout space and a continuum of optimization search algorithms as a basis for further discussions on various search techniques and their effectiveness. Section 3 reviews the optimization algorithms and geometric representations utilized in the layout problem, the advantages and limitations of different methods, and suitable areas of applications. Section 4 discusses the key issues and strategies in building an effective and efficient layout synthesis tool.
Section snippets
Spectral density analysis of the layout space
It is generally agreed that the 3-D layout space is non-linear and multi-modal. The layout space is defined as the mathematical representation of the space of configurations mapped against the cost per configuration. Deterministic algorithms are unable to navigate such a space for globally near-optimal solutions, and stochastic algorithms are usually required for solutions of good quality. Are there any properties or regularities of the space that might help explain why some search methods are
Literature survey
The layout problem can have different formulations, but it is usually abstracted as an optimization problem. An assignment of the coordinates and orientations of components that minimizes the cost and satisfies certain placement requirements is sought. The problem can be viewed as a generalization of the quadratic assignment problem and therefore belongs to the class of NP-hard problems [13]. Consequently it is highly unlikely that exact solution to the general layout problem can be obtained in
Conclusions
Various optimization search algorithms and their representative layout implementations are summarized in this paper. Heuristic rule-based approaches and traditional optimization techniques can be used to solve a narrow class of layout problems efficiently, but they are not suitable for problems with non-linear, non-differentiable objective and constraint functions. Stochastic algorithms such as GA and SA algorithms are applicable to the general layout problem. However, a large number of
Jonathan Cagan is a Professor of Mechanical Engineering at Carnegie Mellon University, with appointments in Biomedical Engineering and Computer Science. His research, teaching, and consulting are in the area of design theory, methodology, automation, and practice. Dr Cagan is a Fellow of the American Society of Mechanical Engineers. He received his BS in 1983 and MS in 1985 from the University of Rochester, and his PhD in 1990 from the University of California at Berkeley, all in Mechanical
References (59)
- et al.
Nesting two-dimensional shapes in rectangular modules
Computer Aided Design
(1976) - et al.
A comparative evaluation of heuristics for container loading
European Journal of Operational Research
(1990) - et al.
A simulated annealing-based algorithm using hierarchical models for general three-dimensional component layout
Computer Aided Design
(1998) - et al.
average-case analysis of cutting and packing in two dimensions
European Journal of Operational Research
(1990) - et al.
Packing problems
European Journal of Operational Research
(1992) A typology of cutting and packing problems
European Journal of Operational Research
(1990)- et al.
A heuristic for packing boxes into a container
Computers and Operational Research
(1980) Shape annealing solution to the constrained geometric knapsack problem
Computer-Aided Design
(1994)- Baumgart BG. Geometric modeling for computer vision, PhD Thesis, Stanford University,...
- et al.
BOXTREE: a hierarchical representation for surfaces in 3D
An exact two-dimensional non-guillotine cutting tree search procedure
Operational Research
Optimal three-dimensional placement of heat generating electronic components
ASME Journal of Electronic Packaging
Genetic placement
An octree method for interference detection in computer aided 3-D packing
Advances in Design Automation 1994: Proceedings of the 20th ASME Design Automation Conference
A hybrid approach of heuristic and neural network for packing problems
Advances in Design Automation 1994: Proceedings of the 20th ASME Design Automation Conference
An octree based heuristic algorithm for 3-D packing
Advances in Design Automation 1994: Proceedings of the 20th ASME Design Automation Conference
Placement of shapeable blocks
Philips Journal of Research
Three-dimensional packing—solution approaches and heuristic development
International Journal of Production Research
A computer-based heuristic for packing pooled shipment containers
European Journal of Operational Research
Constructing discrete medial axis of 3-D objects
International Journal of Computational Geometry and Applications
OBBTree: a hierarchical structure for rapid interference detection
Direct search solutioin of numerical and statistical problems
Journal of the Association for Computing Machinery
Approximating polyhedra with spheres for time-critical collision detection
ACM Transactions on Graphics
Cited by (187)
A space layout design model for concept generation using Function-based spatial planning and structure dynamic deployment
2023, Advanced Engineering InformaticsOptimizing 3D Irregular Object Packing from 3D Scans Using Metaheuristics
2021, Advanced Engineering InformaticsA general approach to module-based plant design
2018, Chemical Engineering Research and DesignPart decomposition and assembly-based (Re) design for additive manufacturing: A review
2018, Additive ManufacturingCitation Excerpt :The traditional 2D and 3D packing problems have been proven to be NP-hard [93]. Therefore, heuristic-driven exhaustive or stochastic search algorithms including branch-and-bound [94], simulated annealing (SA) [95], and genetic algorithms (GA) [96] are often adopted [97]. The packing problems also have a wide range of applications including inventory management, transportation, and supply chains [98].
Thermally Driven Multi-Objective Packing Optimization Using Acceleration Fields
2024, Journal of Mechanical Design
Jonathan Cagan is a Professor of Mechanical Engineering at Carnegie Mellon University, with appointments in Biomedical Engineering and Computer Science. His research, teaching, and consulting are in the area of design theory, methodology, automation, and practice. Dr Cagan is a Fellow of the American Society of Mechanical Engineers. He received his BS in 1983 and MS in 1985 from the University of Rochester, and his PhD in 1990 from the University of California at Berkeley, all in Mechanical Engineering. Dr Cagan is the recipient of the National Science Foundation's NYI Award and the Society of Automotive Engineer's Ralph R. Teetor Award for Education. He is a member of the Phi Beta Kappa, Tau Beta Pi, and Sigma Xi National Honor Societies, and the ASME, AAAI, SAE, and AAEE Professional Societies. Dr Cagan is a registered Professional Engineer.
Kenji Shimada is Associate Professor in the Department of Mechanical Engineering and the Robotics Institute at Carnegie Mellon University. His research interests are in the areas of geometric modeling, computational geometry, computer graphics, and medical CAD. Prior to joining Carnegie Mellon, he was Manager of Graphics Applications at IBM Research, Tokyo Research Laboratory. Shimada received the IPSJ Yamashita Award and the Best Paper Award from NICOGRAPH in 1994, and an NSF CAREER Award in 2000. He holds a BS and MS from the University of Tokyo, and a PhD from the Massachusetts Institute of Technology.
Su Yin is a member of Engineering Mechanics Lab at General Electric Research & Development. She received her BS from University of Science and Technology of China in 1992, MS from California Institute of Technology in 1996, and PhD from Carnegie Mellon University in 2000, all in Mechanical Engineering. Her research interests include design automation and optimization, CAD interoperability, web-based product environment, and system and process integration.