|
Introduction
Features
Algorithms
Objectives
Multi-Resolution Modeling
Test Cases
Collaboration
Future Work
Introduction
We define the general three-dimensional component layout
problem as:
Given a set of three dimensional objects of arbitrary geometry
and an available space (possibly the space of a container), find a placement
for the objects within the space that achieves the design objectives, such
that none of the objects interfere (i.e., occupy the same space), while
satisfying optional spatial and performance constraints on the objects.
Component layout plays an important role in the design and
usability of many engineering artifacts. Engineering artifacts of today
are becoming increasingly detailed, resulting in continuous competitive
pressure to increase complexity, decrease size, and reduce the design cycle
time. As the availability of user-configured designs is becoming more prevalent;
the layout of these one-of-a-kind designs must be individually configured,
requiring fast computational procedures. To date, computer support of such
layout tasks has only focused on representation and manual manipulation
of the shapes. We provide a technique that can solve general layout problems
faster with greater consideration of alternatives.
Features
 |
Optimizes the location of objects in Euclidean space while
optimizing the objectives and satisfying given constraints.
|
|
Handles objects of any geometry.
|
|
Handles perturbations in 6 dimensional space (3 translations
& 3 rotations).
|
|
Provides visual feedback to the user as it is optimizing
the placement.
|
|
Interfaces with commercial CAD packages like ProEngineer.
|
|
Conforms with standard OOD practices, coded in C++.
|
Algorithms
The 3D layout space is nonlinear and combinatorial, making
it difficult to find an algorithm that is both efficient and capable of
finding the global, or at least good local, optimum. We have adapted simulated
annealing algorithm and pattern direct search algorithm as the search methods.
Simulated Annealing
Simulated annealing algorithm is a stochastic
optimization technique introduced by Kirkpatrick et al. In summary,
within the algorithm an initial design state is chosen and the value of
the objective function for the state is evaluated. A step is taken to a
new state by applying a move, or operator, from an available move set.
This new state is evaluated. If the step leads to an improvement in the
objective function, the new state is accepted. If the step leads to an
inferior state, the step may still be accepted with some probability. This
probability is a function of a decreasing parameter called temperature.
The temperature is controlled by an annealing schedule. We use adaptive
annealing schedules and dynamically modified move selections to improve
the efficiency of the algorithm.
Extended Pattern Direct Search
Pattern direct search algorithms are a subset of direct
search algorithms introduced by Hooke and Jeeves, and recently researched
by Torczon et al. The search algorithms follow a series of exploratory
moves defined by pattern matrices to walk through a design space to search
for a stationary point. They rely exclusively on the direct comparison
of function values during search. We introduced extensions to the algorithms
to incorporate domain-specific knowledge and to give them a stochastic
flavor. The results show a one-to-two orders of magnitude improvement in
run time over simulated annealing algorithm with equivalent quality solutions.
Objectives
Different layout problems have different goals, or objectives.
We have formulated several objectives as options with our algorithm. Among
them are:
|
maximization of packing density
|
|
minimization of routing costs
|
|
maximization of assemblability
|
|
minimization of configuration costs
|
|
minimization of center of gravity
|
|
optimization of performance measures
|
Multiple objectives can be considered concurrently; each
goal is added to a weighted multi-objective function. Constraints that
can be articulated are added to the objective function as penalty terms.
Multi-Resolution Modeling
Of the primary objective function terms considered, the single
most computationally expensive one to evaluate is the interference detection
and quantification between components. To minimize overall run time, we
use hierarchical octree models to approximate geometry of components and
obtain interference calculations in reasonable time.
An octree is an approximation of an object at various
levels of resolution based on successive binary division along each coordinate
direction. Each division in 3D space divides a cube into eight cubes. We
classify each cube at each level of division as white, black and gray --
white cubes indicate that no part of the actual object sits inside that
cube, black indicates that the entire cube rests inside the original object
and gray indicates a partial intersection. Figure 1 illustrates three levels
of decomposition of a model in 2D.
Figure 1: Three levels of decomposition of a model in 2D
Test Cases
8-Cube Packing
|
 |
Packing 8 cubes of dimensions 20x20x20 into a container of dimensions
40x40x40
Each cube is unconstrained in all 6 degrees of freedom
Average time taken: 9 seconds |
64-Cube Packing
|
 |
Packing 64 cubes of dimensions 20x20x20 into a container of dimensions
80x80x80
Each cube has 6 degrees of freedom
Average time taken : 20 minutes |
Lunar Rover Packing
|
 |
Packing of the components of a lunar rover for a low center of gravity
|
18-Cogwheel Packing
|
 |
Packing of 18 cog wheels into a cubic container. Note that cogwheels
are non-convex, and must mesh in order to pack properly.
Average time taken: 2.5 minutes |
Saturn Car Engine Compartment Layout
|
 |
11 components and 26 constraints
Average time taken: 17 seconds |
Heat Pump Layout and Routing
|
 |
Concurrent layout and routing (routes not shown except in the last
snapshot)
7 components, 6 routes and 2 constraints
Average time taken: 3 seconds |
Heat Pump Layout and Routing with Vibration Analysis
|
 |
Concurrent layout and routing (routes not shown except in the last
snapshot)
7 components, 6 routes and 2 constraints
Vibration analysis of the routes is done concurrently by calling
finite element analysis package
Average time taken: 5 minutes |
Puzzle
|
 |
To piece the uniquely shaped puzzles together |
Automotive Transmission Layout
|
 |
The container is half of the cross-section of a transmission housing
The blue rectangles represent gearsets and the red ones the clutches
Clutches are shapeable components whose sizes are determined by the design
requirements and their position in the transmission assembly. Notice that the
red rectangles change size as they move around. 10 route connections between the
components are required. The layout, routing and the sizing of the components
are done concurrently
Average time taken: 5 seconds |
Trunk Packing
|
 |
Packing the SAE standard luggage
set into an arbitrary automobile trunk.
A subset of the luggage set should be selected because the trunk can not hold
the whole set. The objective is to maximize the trunk space usage while
minimize the components' overlap and protrusion in order to get a physically
valid solution. |
Collaboration
We invite additional companies to work with us in applying
this technology to their layout problem.
For more information contact:
Jonathan Cagan
Professor of Mechanical Engineering
Carnegie Mellon University
(412)268-3713
jon.cagan@cmu.edu
Prof.
Cagan's homepage
Future Work
Current extensions include incorporation of various analysis/simulation
into the layout algorithm, modification of the search strategy to best
meet specific classes of problems, and investigation into new applications
of the basic search mechanisms.
|
