E>
Optimization in Distributed Assembly
Jonathan Kelly
Department of Computer Science
University of Southern California
Los Angeles, California, USA 90089
jonathsk@robotics.usc.edu
Hong Zhang
Department of Computer Science
University of Alberta
Edmonton, Alberta, Canada T6G 2E1
zhang@cs.ualberta.ca
Abstract Distributed assembly is the process by which a
group of agents interact to build a coherent structure or pattern
from individual components. In this paper, we present a dis-
tributed assembly model in which simple agents assemble blocks
on a two-dimensional grid
graph formalism
using simple rules.
maintain
guarantees
while signicantly reducing the sensing requirements for the
agents involved.
Experiments show that our optimization approach outper-
forms competing algorithms by a wide margin,
in the literature.
to optimize for a wide variety of structures.
I. I
NTRODUCTION
Distributed assembly is the process by which a group of
agents interact to assemble a coherent structure or pattern from
individual components.
This is a broad denition that includes intelligent self-
assembly, where agents may be the individual structural com-
ponents, as well as the domain of by
Distributed assembly is ubiquitous in natural systems across
a range of spatial scales, ranging from the molecular ma-
chinery inside living cells to the to highly-organized nesting-
building activities of many social insect societies.
swarm intelligence. self-assembly have in common
capture the essential features of these domains. without any
direct agent-to-agent communication.
Our goals are twofold. We wish to determine how a group
of locally-interacting agents with limited capabilities can
be instructed to reliably assemble complex two-dimensional
structures, without any global coordination or control.
wish to minimize the sensing requirements for the agents
involved.
most current manufacturing processes proceed in a linear or
near-linear way, assembly line. Parallelizing an assembly task
is usually desirable, as it potentially leads to faster building
vis a vis linear, sequential construction. However, without
global synchronization and control, parallelism introduces a
coordination problem. We can easily guarantee that a linear
process will proceed correctly there is only one way it
can proceed. But with tens or hundreds of agents working in
different locations at the same time, how can we guarantee
that the actions of one or more agents dont delay, or worse,
prevent, the group from reaching its (or our) goal?
how we can design the local interactions such that a
desirable global result is produced.
determine the minimum amount of information to instruct
the
changes in molecular conformation, for example.
our primary contribution in this paper is the algorithm
presented in section V signicantly reduces
have not yet attempted to quantify how many labels (tile
types, states), are required we seek to minimize the number
of labels that appear in the a ruleset which uniquely assembles
a desired structure.
The term label is used to emphasize the fact that the state
of a block must be externally recognizable by other assembly
agents in its neighborhood.
different that linear assembly processes, where components
are usually attached in a xed, linear sequence.
can be considered as a recognition problem, or as a data
compression problem. expect the optimization algorithm pre-
sented here to be useful in
nanorobotics
has a direct impact on the reliability of the assembly
process.
formations, manufacturing
local to global problem
waiting for certain local congurations to appear ... actually
speeds up construction.
contribute to the theory of distributed assembly, recent
results converging
produce
the
desired
behaviors
in
complex,
locally-
interacting systems.
problem is NP-hard.
reduce the required number while ensuring that any spa-
tiotermporal ordering constraints are respected
The remainder of the paper is organized as follows. In
Section II we discuss related work. Section III describes our
distributed assembly model, while Section IV formalizes the
idea of coordination among agents. Section ?? describes our
optimization algorithm, the primary contribution of the paper.
We give experimental results in Section VI and discuss those
results in Section VII. Finally, we offer some conclusions and
directions for future research in Section VIII.
II. R
ELATED
W
ORK
transition rule set compiler, which takes as input . ensuring
that the resulting rules will assemble the desired structure, no attempt is made to optimize the ruleset.
originally inspired by the work of Bonabeau et al.
social insect nest construction . In [?] quantify structured
shapes.
active assembly Arbuckle.
assemble into linear structures, . Parker and Zhang execute
a simple algorithm is able to clear an area.
III. A M
ODEL FOR
D
ISTRIBUTED
A
SSEMBLY
In our distributed assembly model, individual construc-
tion agents move randomly and asynchronously on a two-
dimensional grid, transporting and attaching square blocks
together to form a desired target structure (or simply target).
Each grid cell may be either empty or completely lled by
a single block; we ignore the spatial extent of the agents
themselves, and assume that an agent is able to t within
one cell. Assembly begins with a single seed block, whose
location on the grid is xed at an arbitrary origin. Positions of
the remaining blocks in the target are specied relative to the
seed. A cell has four adjacent neighbors to the North, East,
South and West; all agents share a global sense of orientation
such that they agree on the directions of adjacent cells. We
model the assembly of connected structures only, in which
every block in the target is adjacent to a least one other block.
Although all blocks have the same size and shape, each
may be identied by an assigned label, selected from the set
of natural numbers. Initially, the seed is given a label of 1,
and all other blocks are unlabeled. For convenience, we use
the label zero to identify unoccupied cells. As an agent moves
between empty cells, it compares the labels on blocks within
its sensing neighborhood, dened as the four adjacent cells,
with entries in an internal lookup table of assembly rules;
together, the rules in the table form an assembly rule set, and
encode all the information required to build the target. The
table is identical for the agents.
Each assembly rule consists of a binding congurations
that triggers an assembly action, and a resultant label. A
binding conguration is a four-tuple enumerating a) which
cells adjacent to the agent must be occupied, and b) what labels
must appear on blocks in the occupied cells. When a binding
conguration is encountered, the agent attaches a block with
a specic resultant label, dened by the rule, to the structure
at the agents current position. The attachment is irreversible
assembly actions are never undone.
Our assembly model is compatible with the model described
by Jones and Matari´c in [1], except for the following differ-
ences. We allow up to three cells in any binding conguration
to contain labeled blocks, instead of two, and disallow dont
care entries within a conguration. The binding conguration
that denes a rule must be fully specied, and it must match
the agents sensing neighborhood exactly for the rule to be
activated. Together, these changes allow us to remove the
restriction on, and expand the variety of structures that may
be assembled.
S
(a)
(b)
(c)
(d)
1
2
3
4
5
6
7
8
9
10
11 12
1
2
2
2
2
2
2
2
2
2
3
3
Fig. 1.
Stuff
IV. S
PATIOTEMPORAL
O
RGANIZATION
a fundamental question . That is, what is the minimum
amount of information that must be embedded in the ruleset
to ensure that
stated differently, how can we minimize the sensing require-
ments.
A. Consistent Rule Sets and Assembly Ordering
Because agents actions are random, the exact sequence
in which blocks are added to a growing structure cannot
be determined in advance in most cases. However, although
the individual steps may vary, the process cannot be entirely
unconstrained the geometry of the structure will often dictate
that certain spatiotemporal constraints be respected, to avoid
allowing the assembly of one part of the structure prevent the
assembly of other parts. Any sequence of assembly steps that
produces the desired nal structure is called a valid sequence.
For example, when building a 3 x 3 solid square, starting in the
lower left-hand corner, it does not matter if .... For a structure
to remain connected, every block except for the seed must
have an associated set of one to three adjacent predecessor
blocks, which need to be in place before the new block can
be attached.
Formally, a valid sequence of assembly steps leading to the
correct result forms a partial ordering over the blocks in the
target. We call this partial ordering an assembly ordering, and
represent it as a directed acyclic graph, called an assembly
graph. There is a vertex in the graph for each block in the
target, and a directed edge from vertex i to vertex j if the
corresponding block b
i
is adjacent to block b
j
and b
i
is a
predecessor of b
j
. An example assembly graph for the target
in Figure 1<i>a is shown in 1<i>b.
We wish to generate a consistent rule set
1
that assembles
the target structure only at any time, and for any possible
series of local interactions, the blocks in the growing structure
should form a subset of the blocks in the target. To ensure
consistency, it is sufcient for the rule set to: respect the assembly ordering constraints, enforcing the
requirement that all adjacent predecessors are in place
1
This