This chapter presented various techniques that are used in the component place-ment framework. While the methods are well known from computer graphics, some innovation was still needed to adapt them to the problem at hand.
Chapter 7
Component Placement
This chapter presents a framework for automatically placing 3D components in a container. The framework is applied to the problem of placing a faceplate and the associated components in an ear canal.
The problem of component placement is found in many disciplines, and with many names including 3D bin packing, container loading, pallet loading, 3D palletisation1, and printed circuit board layout [15, 45, 46, 47, 132, 147, 189, 197, 215, 225, 237, 239]. Generally, the problem can be formulated like this [46]:
Given a set of three-dimensional objects of arbitrary geometry and an available space, find a placement for the objects within the space that achieves the design objectives, such that none of the objects interferes, while satisfying optional spatial and performance con-straints on the objects.
Previous approaches are usually tailored to a specific application, thus limiting the problems that can be solved. Printed circuit board layout is an example of a specialised problem, where the components are limited to rectangles aligned
1The packing of goods on to small wooden platforms, or pallets, for ease of handling in shipment.
in 2D along orthogonal axes [45, 46]. Similar constraints exist for other ap-plications. As a curiosity, it is claimed that the physical placement of neural components in the brain appears consistent with a single, simple goal: minimise the cost of connections among the components [56].
Our problem can be formulated like this
Given an ear canal and a set of components, place the components in the ear canal, as would an expert operator.
Fulfilling this requires both insight in the routines, behaviour, and thoughts of the operator and a flexible framework for component placement. We therefore start by introducing a generic framework and later apply it to the problem stated above.
7.1 A Component Placement Framework
Instead of limiting the framework to a specific application, we formulate it as a set of steps, where each step can be tailored to the problem at hand.
Problem Analysis
The task is often to reproduce or improve results previously made by human operators. This could be the placement of engine parts in a car motor or the packing of a truck. Therefore, it is very beneficial to learn which methods the trained operators are using to solve the task.
Formulation of an Objective Function
Based on the expert operators’ experience and practical considerations an ob-jective function can be formulated. Evidently, the obob-jective function should be computable and since it will be evaluated often in the optimisation phase, it is preferable that it is not very complex to compute. An objective function can for example be a combination ofmaximisation of packing density,minimisation of routing costs2, minimisation of component heating [48], and minimisation
2Routing means to connect components using for example wires or tubes.
7.1 A Component Placement Framework 65 of electromagnetic field interference [46, 147, 215]. Furthermore, an objective function often involves distances and the amount of collision between the com-ponents.
A complication is to determine the weights used in the final objective function.
That is to select how much each term should influence the final solution. In addition, it can be beneficial to change the weights during the optimisation.
For example allowing collisions in the start and penalising them heavily in the end. In certain circumstances, it is possible to determine the weights using a leave-one-out study.
Determination of Hard Constraints
Some states are not acceptable and therefore hard constraints can be specified.
One hard constraint is for example that components must not overlap and must not be outside the container. Another example is that a container for liquid should have the opening upwards. It can be useful to formulate the hard con-straints so they are solely enforced in the end of the optimisation phase, since finding the global optimum often requires crossing illegal states.
Definition of the State Space and a Move Set
To be able to optimise the placement, it is necessary to define a set of movements for the components and thereby defining the state space that the optimisation algorithm navigates. In previous work, nearly all problems are constrained to finite state spaces meaning that each component is only allowed a finite set of movements [15, 46, 147, 215, 239]. These can for example be a translation of a given length or a fixed angular rotation around one of the coordinate axis, giving the component a limited number of degrees of freedom. Another possibility is to allow the components to move freely. Hence, the position of a component is controlled by six continuous parameters. In summary, there is a drastic increase in the dimension of the state space for each free component.
Initialisation
Normally there is the need for an initialisation step where the components are placed in a start state. This start-state should provide the optimisation algo-rithm with a starting guess, but does not need to fulfil any constraints.
Optimisation Strategy
Cagan et al. claim that the solution space of 3D layout problems is of fractal nature [47]. Deterministic algorithms are therefore not suitable for locating the global minimum, and stochastic algorithms are usually required for good quality solutions.
In the literature, several different optimisation strategies have been used to solve the problem. If the state space is limited and can be considered as a finite string of states a genetic algorithm approach can be chosen [132, 147].
Another option is the similar A-teams algorithm [215]. A popular optimisation strategy is simulated annealing [46, 57, 164, 172, 248]. A similar problem with a finite state space, where simulated annealing has been used to find approximate solutions is the travelling salesman problem [208].
When the state space is not finite, genetic algorithms and other algorithms that require that the state space can be formulated as a string cannot be used.
Instead, simulated annealing seems to be the best solution.
Validation
When the placement of the components has been optimised, there is a need for a validation of the result. In some cases, the final value of the objective function is enough. In other cases, a total sanity check of the final state is needed.