Pick-and-place process sequencing for transformation of rasterized 3D structures

The problem

Buildings can be put together from bricks or prefabricated components; in the same way, a structure can be assembled from equal-sized parts, or voxels, by pick-and-place (PnP): a machine picks up one part and places it somewhere else. The paper frames the task as transforming one rasterized structure (the source) into another (the destination). Building from a material palette is the special case in which the source is the palette. The question is which sequence of moves the machine should follow so that the total work is as small as possible.

Two things make this hard. Deciding which part goes where is an assignment problem: a brute-force search compares n! sequences, and the structures in the experiments have about 2,250 to 2,550 voxels each. The cheapest mapping is also not necessarily executable. The machine studied here is a Cartesian robot with at least three axes and a vacuum suction gripper that holds parts by their top surface, so it can only pick or place a voxel on the top surface of a structure.

How it works

The input is a closed triangle mesh for each shape. Each mesh is rasterized into voxels, with a flood fill to mark the interior. The two voxel models are then aligned, and the remaining work is motion sequencing: deciding which voxel moves where, and in which order.

1. Align and classify. The structures are assumed to be aligned vertically already, and only horizontal translation is searched, exhaustively, to maximise their overlap. Voxels present only in the source are Movers (M), voxels present only in the destination are Voids (V), and overlapped voxels stay in place. If there are more M than V or the other way round, the extra voxels go to or come from a palette, a linear stack.
2. Cost of one move. Moving M_i to V_j costs c_ij = |x_j − x_i| + |y_j − y_i| + 2z_max − z_i − z_j, measured in voxel sizes (Eq. 1). The part is lifted to the clearance plane z_max, moved in x and y only at that height to avoid collisions, and lowered onto V_j.
3. Hungarian method on the full cost matrix. The costs of every M–V pair form an n × n matrix. The Hungarian method, with time complexity O(n³), returns the n pairs with the minimum total cost. This Global Optimization Strategy (GOS) gives a lower bound on the total cost, not a valid motion sequence.
4. Top-access constraint. Lowest-cost pairs do not necessarily lead to a feasible sequence. In the paper’s eight-voxel example, one minimum-cost pairing (total cost 27) can be executed in a suitable order, but an equally cheap alternative deadlocks after two moves.
5. Local Optimization Strategy (LOS). LOS builds the cost matrix only from the M and V on the top surfaces and applies the Hungarian method to it; when there are more M than V, it leaves some M out of that stage. The M left out are those that make the total cost of the chosen pairs minimum. The resulting pairs can be moved in any order. The top surfaces are then updated and the process repeats until all M have been moved. In the example, LOS needs two stages and its total cost, 27, happens to equal the lower bound.

The paper compares LOS with two further strategies that also produce valid sequences. The Greedy Selection Strategy (GSS) uses the same top-surface cost matrix but, without the Hungarian method, moves only the single lowest-cost pair at each step. The Random Selection Strategy (RSS) moves a random top-surface pair at each step.

Results

The strategies were tested on eight models (wall, pyramid, starfish, cube, igloo, castle, stairs and the Eiger mountain), rasterized to similar sizes of 2,250 to 2,550 voxels, by transforming every model into every other. Times are for a C++ program on an Intel Core i3-2310M 2.10 GHz PC with 8 GB of RAM. The amount of work depends on the number of M–V pairs, not on the number of voxels: pyramid → wall needs 1,643 pairs, but pyramid → igloo only 325, because the two shapes are more similar and align better. In cost, GOS is best because it gives the lower bound, but its pairs do not define a motion sequence and are sometimes not feasible at all. LOS is second, and its stages define the sequence directly; GSS is slightly worse than LOS but clearly better than RSS. In time, RSS is fastest, GSS and LOS are similar, and GOS, which runs the Hungarian method once on one huge matrix, is the slowest. The authors conclude that LOS gives an appealing balance between cost and processing time, and that it outperforms the other strategies that generate feasible sequences.

Repeating starfish → castle at six resolutions, from 139 to 2,016 M–V pairs, the total cost grows about linearly with the number of pairs, and so does the time of every strategy except GOS. Although LOS uses the O(n³) Hungarian method, its time does not grow cubically with resolution. All results come from computer simulation. The top-surface constraint also rules out overhanging structures, such as a room with a ceiling or a wall with windows; the authors suggest that the LOS approach, which first selects the voxels that satisfy the constraints and then optimizes the M–V pairs, can carry over to other parts and constraints.