Section of
Final Report: NASA ACRP NCC7-7,
**Bush Robots**, *Hans Moravec, Jesse Easudes*

**2: Bush Geometry**

**Fractal Parameters**

Though not necessarily the optimum design, bush robots with
uniform structure are a good way to introduce some of the key ideas.
In a regular bush robot, subtrees are scaled miniatures of the whole
structure. The overall geometry of this class of bush robots is
defined by just a few parameters, primarily the branching factor
**B** , stating how many smaller twigs branch from each larger
twig, and the scaling factor **S** , giving the linear size ratio
of each smaller twig relative to its parent.

The **B** and **S** parameters define other
quantities, such as the robots fractal dimension **D**. The
dimension of an object can be inferred from its scaling properties.
For instance, a one-dimensional line becomes the equivalent of two of
the original line when its size is doubled. A two-dimensional square,
on the other hand, grows into an area encompassing four of its
original selves when its scale is doubled, and a three dimensional
cube grows to the size of eight of itself. This observation
generalizes to the formula

**R = M**^{D} or **D**
= log(**R**) / log(**M**)

where **R** is the replication factor, **M** is the
magnification factor and **D** is the dimension. Fractal objects
have the peculiar property that their dimension can have non-integer
values. In a mathematically idealized, unbounded bush robot, whose
branching goes on endlessly at both the small and large ends, it can
be seen that magnifying the whole robot by a factor of 1/**S** ,
then shifting our attention up one branching level to regain the
original scale, produces the equivalent of **B** copies of the
original-sized robot. The fractal dimension of the robot is
thus

**D** = log(**B**) / log(1/**S**)

Since **B** can be chosen to be any integer, and **S** any
value whatever, the fractal dimension can be set to anything. In
fact, values of **D** greater than 2 will not work for very many
levels, since they cause the cross section each smaller level of
branchlets to occupy more area (proportional to **B**^{n} x
**S 2**^{n} , where **n** is the level in the tree), forcing
increasingly severe crowding, then overlapping. **D** values of
exactly 2 allow a bush with unlimited branching to arrange its fingers
to exactly cover a surface, which may be a useful feature, for
instance in a robot that constructs solid objects layer by
layer.

A robot with **B** = 2 and **D** = 2 (thus **S** =
) can cover a surface in just two
distinct patterns, one corresponding to a straightforward rectangular
grid, the other to a fractal edged double dragon curve. Both patterns
are illustrated by the pose of such a robot in Figure 1 (rendered to
only 17 branching levels). Most of the upper portion shows fingers in
grid configurations, covering surfaces of various curvatures. The
quarter subtree at the bottom of the picture covers a surface in a
double-dragon pattern. A 1/8 subtree on the left is configured to
loosely fill a volume, leaving a fractal pattern of voids (as a
**D** = 2 robot must do to cover a higher dimensional
space).

Very high branching factors seem impractical, but the other
extreme of **B** = 2 is not necessarily best. Consider a property
we can call routing cost. A bush with a given **B** and **N**
levels of branching has **B**^{N} fingertips, any one of which can be
specified with log(**B**^{N}) = **N** log(**B**) quantity of
information (bits, if the logarithm base is 2). A signal from the
stem to one of these fingertips must pass through **N** levels,
each forking in to **B** alternate directions, of which it must
choose one, providing log(**B** ) of routing information in doing
so. If there is a cost in proportion to **B** in this decision
(eg. a rotation of a **B** -way switch), the cost/benefit ratio is
**B** /log(**B** ). The analytic minimum of this expression
happens when **B** = *e * (= 2.71828...). There is no obvious
way to implement non-integer values of **B** , but **B** =3 is
the best integer under this measure, better than either 2 or 4, which
score equally. **B ** = 3 gives access to the most number of
fingers for the least amount of routing distraction (the same analysis
minimizes the number of teeth in a cogwheel based counter). More
investigation may reveal if this property is actually of consequence,
but a **B** = 3, **D** = 2 robot is interesting in itself. It
has only one regular mapping into 2D surfaces, with a triangular
fractal boundary more symmetric than the double-dragon of **B**
= 2. Figure 2 shows such a robot.

**Beyond Geometry**

Fractal geometry is fundamental, but among the simplest
considerations in a bush robot design. Myriads of other issues have
hardly been formulated, but should emerge as we begin to build bush
robot simulations, and define mechanical implementations. A few of
the issues we expect to encounter emerge from contemplating particular
designs. A **B** =2, **D** = 1, **N** = 20 (call it a
[2,1,20]) robot would have a million end effectors, each one millionth
the scale of its trunk. We are led to ask what thickness is
appropriate for the elements, give some assumptions about the power
and energy density we expect in actuators, distributed power and
computation. Too thick, and the robots motion will be impeded, too
thin and there will not be enough room for adequate actuators and
processing. Perhaps the branches should taper or bulge. How many
degrees of freedom of motion are needed at each branch? Surely at
least pan and tilt at the base, and roll anywhere along the length.
Would a telescoping action be worth the complication, or could the
massively redundant articulation achieve the same effect with an
accordion pose? The answer probably depends on the overall geometry,
and how much excursion the pan and tilt joints can achieve.

Each robot branch moves the entire subtree that grows from it.
Fortunately the exponential shrinkage in scale over the levels limits
the total mass of that subtree. In a **B** = 2, **D** = 1 robot
the volume of a subtree is only 1/3 the volume of the branch that
supports it. A **B** = 2, **D** = 2 robot is something of a
worst case, with subtrees 2.4 times as massive as their supporting
branches, but a **B** = 3, **D** = 2 robot branch supports only
1.4 times its weight, and a **B** = 4, **D** = 2 branch carries
exactly its own weight. In general lowering **D** or increasing
**B** decreases the relative weight (whose exact value is **B**
/((**B**^{3})^{1/D} - **B**) ).

Assuming a constant power density across all scales, the smallest
branches of a [2,1,20] robot can move a million times as fast as its
trunk, possibly 1 MHz to the trunks 1 Hz. End motions might be
decomposed into low frequency, big excursion components produced by
the large branches, on which are superimposed high frequency, small
excursion corrections executed by upper branchlets, as in a series
expansion. On the other hand, there is much more volume for computer
power in the trunk than the fingers. This suggests motion control
that leans heavily towards elaborate planning near the trunk, and
simple, fast reactive control at the tips (with the reactive strategy
probably delivered from the trunk for each new purpose). Devising a
continuum of control strategies ranging from complex but slow for the
big end to simple and fast for the small ends may be one of the most
interesting and challenging tasks of the bush robot project. Not only
will bush robots bridge the gap between macrotechnology and
nanotechnology, they will stretch between the opposing camps of
model-based and reactive robotics! The bush robots tremendous range
of potential behavior will tax just about any control approach, from
precise control theory, to reflexive behavior, to cerebellum-type
learning, to genetic algorithms.

The many actuators on a bush robot, especially the vast array of
microscopic ones, would be excellent touch sensors if not only their
position, but the forces they exert are measured. The fingertips of
the [2,1,20] robot are like a million miniature stereo phonograph (or
scanning tunneling microscope) needles, each with a 1 MHz bandwidth,
giving an overall touch sensing bandwidth a million times greater than
the data rate of human vision! An interesting, and surely important,
behavior to simulate is the detailed scanning of objects, even moving
or flexible ones, using the whole tree linkage to follow the motion,
while maintaining highly precise position and force relationships
between millions of fingertips and the surface. A bush robot could
also, of course, manipulate and reconstruct a surface wholesale,
providing an even more interesting simulation challenge. Such
abilities would allow an advanced bush robot to reach into a
complicated piece of machinery (or biology), almost instantly feel out
the internal state, then rearrange things to effect an equally speedy
repair or upgrade.

**Fractal Finger Placement**

Grasping a surface is among the most fundamental functions of a
dexterous robot. Most conventional machines make do with a small
number large fingers. A bush robot would be able to exercise much
greater control and flexibility by holding with a surface of
controlled microscopic fingers. One way to ensure that the large
number of fingers are evenly distributed over an area is arrange them
in a surface-filling fractal covering that conforms with the branching
geometry of the robot.

There are a very limited number of perfectly regular
two-dimensional fractal coverings. There seem to be only two distinct
regular coverings for **B** = 2 robots, only one each for **B**
= 3 and **B** = 4, and none for larger **B** .

A fractal covering of a surface may viewed as a kind of number
system, mapping fingers of the robot to points on the plane. Each
higher level of the robot represents a successive lower fractional
digit position of the base **B** number system. Each branch
represents a choice of digit in a radix number expansion. Since all
branches are present, the robot can stand in for every possible
number. As the number of levels grows, the covering grows more dense,
tending to continuous as the level tends to infinity, exactly as
infinite decimal expansions represent a complete segment of the real
line.

To make a string of digits cover two dimensions rather than a one
dimensional line segment, one defines the digits and the positional
factors as complex numbers. The real and imaginary parts of the
resulting numbers define x and y positions on the surface. The system
can be regular only if the digit values are equally spaced. We do
this by placing them on equal positions on a unit circle in the
complex plane. In a base B system, a digit value of V maps to the
complex number exp(2 *i* V/**B**). Graphically:

As in conventional number systems, successive digit positions in
complex number systems have weights that are successive powers of a
radix. In conventional systems the radix is simply **B** , the
number of digit values. It is easy to show that a complex number
system can cover the plane only if it employs a complex radix whose
magnitude is - only thus is the
fractal dimension of the result 2. Possible phases for this radix do
not succumb to easy analysis. Essentially the magnitude controls the
scale of each successive digit, while the phase controls the rotation
of the above diagram from one digit to the next:

The diagram above shows the natural mapping of bush robot fingers
to covers of this kind. Each smaller circle is represented by a
higher level branch, whose shorter twigs have just enough reach to
cover it.

The following images show effective and ineffective covers. The
first line defines the mapping. **B** is the base of the system,
equivalent to the branching factor of the corresponding robot.
**D** , the fractal dimension, always set to be 2. **A** is the
phase of the complex radix, expressed as an angle in degrees. The
combinations (**B** = 2, **A** = 90°), (**B** = 2,
**A** = 45°), (**B** = 3, **A** = 90°), (**B** = 4,
**A** = 0°) are the only complete covers. (**B** = 4,
**A** = 90°) is equivalent to (**B** = 4, **A** = 0°),
representing only a permutation of the branch identifications at each
4 way split. Values of **B** greater than 4 cannot create covers,
because, at every scale, the lower order digits do not have enough
reach to fill the center of the circle stepped out by the high order
digit. The central holes remain unfilled.

**Best Two Dimensional Bush Robot Geometry**

In two dimensions, a robot with two-way branching (**B** =2)
forms a rigid truss work if its fingers are firmly affixed to a rigid
surface. The smallest fingers form triangles with the surface, whose
apexes, in turn provide anchors for V frames of the next larger
branches, and so on:

Surfaces could be held without the need to engage actuators on
segments within the truss, thus increasing strength and saving power.
The geometry also greatly simplifies the problem of configuring the
robot to contact a given surface. Once a pair of fingertip positions
have been chosen, the connecting vertex is constrained by the finger
lengths to one of two unique points, on either side of the line
joining the fingertips:

The choice between these two possibilities is often easy, for
instance if one lies inside and the other outside the object to be
held. Various relatively inexpensive strategies could be used to make
the decision in general. For instance, a program could pick the
vertex closest to the corresponding node in an "elastic" (or rubber
tree!) configuration described earlier. The elastic solver provides
approximate answers by stretching a simulated bush to place the
fingers at desired locations, then iteratively "relaxing" the bush,
allowing each branch to return towards its natural length, pulling
against its connecting branches.

A two-dimensional robot will have difficulties gripping large
objects unless its fractal dimension **D** is equal to 1. If
**D** is less than 1, the coverage of ever larger surfaces will
necessarily have ever larger gaps, and at some size the robot will
have insufficient fingers per unit length, and thus insufficient
strength and grip, to hold the object. If D is greater than 1, the
fingers will crowd and overlap as the size of the grasped object
grows. Only at **D** =1 can the finger density remain constant
independent of grip size. Altogether, (**B** = 2, **D** = 1)
seems a very good geometry for a two dimensional bush robot.

**Best Three Dimensional Bush Robot Geometry**

The same considerations in three dimensions lead to a (**B**
= 3, **D** = 2) geometry, meaning the scale from one level to the
next is . **D** = 2 because
the usual interaction with 3D objects is via their 2D surfaces, and
**D** = 2 allows a robot to uniformly grip a 2D surface of any size.
**B** = 3 because in 3D, a rigid anchored frame needs three
segments:

**Maximum Grip Size with Branching Level**

Searching for a configuration of a portion of a bush robot that
grips an object is effort wasted if no such configuration exists. For
instance, the object may be too large to hold with the available
fingers.

The size of an object, or its grasped portion, may be
characterized by a bounding sphere. Usually, an object will be
graspable if its bounding sphere could be securely held. A sphere
will be secure if its motion is constrained in all axes. The three
dimensional situation of a (**B** = 3, **D** =2) robot will be
addressed later, but basic insights can be had in the simpler two
dimensional analogy of a (**B** = 2, **D** = 1) robot.

In two dimensions, no disk can be held securely by a final tree
level without the possibility of slippage:

But, two levels of a tree can securely hold a disk, up to a
certain size:

Neglecting branch thickness for the moment, the maximum possible
**R** forces the holding segments to lie tangent to the disk, while
the smallest fingertips just reach opposite ends of a diameter:

**FIGURE 1**

The smallest (length **F**1) fingers are tangent to the disk
at their tips. Call the disk angle they subtend, part of a right triangle that
defines =
atan(**F**1/**R** ). By symmetry, the segment of the larger
(length **F**
2) branch between its tangent and the smallest finger has length
**F**1, and its subtended angle = . The remaining segment has length
**F**2-**F**1, and its angle
=
atan((**F**2-**F**1)/**R**).
Fingertip to fingertip subtends an angle
.
By symmetry, the left half tree
subtends . Thus
+
+
=
.

In a (**B** = 2, **D** =1) robot, **F**2 = 2 **F**1,
so **F**2-**F**1 = **F**1, and all the arctangents, and
thus all the *a* angles are equal.
Thus 3 =
, and =
=
,
and

**Define ****F**1 = 1, and indicate the number of branch levels by
**L** . The two previous results can then be expressed using the
notation:

**R**max(**B** = 2, **D** = 1, **L** = 1) = 0

**R**max(**B** = 2, **D** = 1, **L** = 2) =

**The equations for L=3 are analogous:**

**FIGURE 2**

= atan(**F**1/**R** )

*a*2 =
atan(**F**1/**R** ) + atan((**F**2-**F**1)/**R**
)

*a*3 = atan((**F**2-**F**1)/**R** ) +
atan((**F**3-**F**2+**F**1)/**R** )

+
*a*2 + *a*3 = 2 atan(**F**1/**R**) +
2 atan((**F**2-**F**1)/**R**) +
atan((**F**3-**F**2+**F**1)/**R** ) =

**For general ****L** , the relation becomes (**EQ1** )

**For a two-dimensional (****B** = 2, **D** = 1) robot,
**F***k* = 2^{-k}. The arctangents can be
absorbed into a single arctangent in this expression by repeatedly
applying the identity

atan(**X** ) + atan(**Y** ) = * *
atan((**X** +**Y** )/(**1**-**XY** ))

**With all but one trigonometric function removed, it may be
possible to solve the result as an algebraic equation, maybe with a
closed-form for ****R** . In any case, it is easy to solve
**EQ1** numerically by Newton's iterative method, and record the
results in a small table, one **R** value for each bush level. A
grasping algorithm would consult the table to find the minimum number
of bush levels needed to hold an object of given size.

**EQ1 ** applies equally to a three-dimensional robot. For our
favored (**B** =3, **D** =2) configuration, **F***k* =
3^{-k/2}. Instead of gripping at opposite ends of the diameter
of a circle, a three-dimensional **B** =3 robot would grip at three
equally spaced points around a circumference of a sphere. In other
respects, the situation is identical to the ones pictured in Figures 1
and 2:

**FIGURE 3**

**We began this analysis by ignoring the branch thickness. Its
effect, to good approximation, can be introduced after the fact by
simply subtracting the radius of the largest branch involved in a grip
from the radius of the maximal sphere that it can hold.**

**Choosing vertex directions in rigid bush grips**

**We investigated degrees of freedom that remain when the fingertip
positions of (****B** =2, **D** =1) bush robots in two dimensions
(or (**B** =3, **D** =2) robots in three dimensions) are fixed.
The positions of successively larger nodes in such setups are fixed at
the intersection of branch-length circles (or spheres) centered on the
previous layer of fixed nodes, resulting in statically rigid grips.
However, there are usually two such intersections, one corresponding
to a parent node being above, the other below, the plane of its
children:

The many binary choices accumulate to approximate many unconstrained
degrees of freedom as the number of levels of the bush grows.

**The following discussion centers on the two-dimensional
(****B** = 2, **D** = 1) robot for clarity, but the results generalize
trivially to the more interesting but harder to illustrate
(**B** = 3, **D** = 2) three dimensional case.

**In two dimensions, a robot with two-way branching (****B** = 2)
forms a rigid truss work if its fingers are firmly affixed to a rigid
surface. The smallest fingers form triangles with the surface, whose
apexes, in turn provide anchors for V frames of the next larger
branches, and so on. But each apex can be in one of two positions,
The number of apexes is exponential in the number of levels of the
tree, and the number of possible configurations is exponential in the
number of apexes. Thus there are
or about four billion possible configurations for the fingertip-fixed
five level bush shown, four of which are shown below:

The latter two illustrations show unacceptable configurations where
segments of the bush intersect one another. In fact, most possible
solutions suffer from this problem. Such problems exist in three
dimensions also, though with reduced probability (there is more elbow
room in 3D!). The most urgent problem in selecting manipulator
configurations for holding surfaces is to avoid intersecting the
object being held with structural parts of the manipulator. In
conventional manipulators, with a handful of segments and possible
configurations, its is usually simple to enumerate or search over the
possibilities to eliminate the problematic ones. This approach is not
reasonable for robots, with doubly-exponential number of
configurations.

**The "rubber tree" algorithm for configuring bush robots pretends
the robot is made of perfectly elastic members, which can be stretched
into position, then allows the members to iteratively relax to their
normal lengths. It starts by placing the smallest fingertips in their
destination positions. Each parent node at the next larger level of
the bush is then set to the mean location of all its children, and
this process is repeated at larger and larger scales until the root of
the bush is positioned. Since this initial configuration ignored
branch lengths, it usually leaves the bush in a highly stressed state.
A relaxation process then visits every vertex in the tree, and moves
it in a way that minimizes the stretch energy of the connected
members. The relaxation iteration is repeated perhaps a hundred
times, until most of the stretch is gone. The approximate solution
thus produced then guides an exact placement.**

**The exact placement stage also starts at the fingertips and works
its way to the root of the bush. Each first node up from the fingers
is positioned to the one of the two exact solutions that places it
closest to the corresponding node in the rubber tree approximation.
Then the nodes leading to those are positioned under the same
criterion, and so on.**

**The basic rubber-tree algorithm places the interior nodes of the
tree centrally inside the fingertip positions, paying no attention to
objects that might be in the volume. It was modified by superimposing
a repulsive forces to push nodes out**

and away from objects during
the relaxation process. Experiments with this technique then
suggested changes in the elastic parameters of the algorithm. The
original model resembled actual elasticity, in that the pull of
branches was proportional to their cross-sectional area and elongation
fraction. Under this model, the smallest fingers settled down with
much greater percentage elongation in the influence of the repulsion
than the thicker branches. Tuning the repulsion profiles with
distance from objects (currently modeled as spheres) and the relation
of elasticity and repulsion strength to branch size, eventually
produced a partially successful choice of node locations.

**The results can be seen in the next section, which includes 3D
images of an order 10 (****B** = 3, **D** = 2) bush robot with
59,049 fingers. Most of the fingers are placed appropriately, but
some penetrations can be seen in the smallest objects.

** Configuring Robot Bushes**

**The inverse kinematics problem, of finding the joint positions of
a robot arm that place the end effector in a desired position and
orientation, was once considered a hard problem in robotics,
especially for robots with redundant degrees of freedom. At worst, it
could involve an exhaustive search over all the combinatorial
possibilities. Today there are a number of adequate solutions for
simple arms, but the problem remains difficult if simultaneous goals
must be met, for instance putting an elbow in one region and the hand
in another. Bush robot potentially push this problem pushes the
problem to astronomical proportions.**

**We have found a computationally feasible approach. The
computation pretends the robot is made of perfectly elastic members,
which can be stretched into position, then allows the members to
iteratively relax to their normal lengths. If considerable stretch or
compression remains after a few tens of iterations, the robot
configuration is likely impossible. Impossible poses can be modified
into possible ones simply allowing every member to snap to its natural
length.**

**Our present robot configurator places the smallest fingertips in
their destination position. Each parent node at the next larger level
of the bush is then set to the mean location of all its children, and
this process is repeated at lower and lower levels until the root of
the bush is positioned. Since this initial configuration ignored
branch lengths, it usually leaves the bush in a highly stressed state.
A relaxation process then visits every vertex in the tree, and moves
it in a way that minimizes the local stretch energy. The relaxation
iteration is repeated a few tens of times, until most of the stretch
is gone.**

**Many issues remain unaddressed. For instance, the present simple
program ignores any intersections of members, or limits in joint
angles.**

**Triangulating Bush Robot Skin**

**It is possible to form a bush robot branch out of six triangles,
connecting a three-sided base to a smaller three-sided apex, rotated
about 60 degrees:**

**For a three-way branching robot, our preferred configuration, the
bases of three small branches can be perfectly joined to the apex of a
larger branch enclosing a tetrahedral-shaped void. The following
illustration shows this done to two levels of branching:**

**Note that in the above construction, only the six triangles in the
surface of each tapered branch are necessary to form the structure.
All other triangles, for instance the faces of the tetrahedron
internal to each joint, are only virtual.**

**There are six edges pairwise joining the six triangles in each
branch. Interestingly, these edges suggest a plausible implementation
for the mechanical actuation of actual working bush robots, using only
length-changing linear actuators.**

** Stewart Platform Branch Actuation**

**A Stewart platform is an elegant configuration of six linear
actuators in a circular triangulated truss that provides a full six
degrees of 3D translational and rotational freedom. The edges of our
bush robot skin triangulation are in the pattern of the actuators of a
Stewart platform. A Stewart platform allows the position and angles
of the apex plate (including the effective branch length) to be
changed over significant ranges, though it only provides about +/- 30°
axial rotation. Since many conceivable bush robot motions involve
multi-turn axial rotation oft one branch level or another, it may be
desirable to add a redundant axial rotor at the base of each joint.
Ignoring this refinement for the moment, here are two views of a
Stewart platform bush branch. Each cylindrical strut is assumed to be
a length-changing actuator like a piston or linear motor. The
equilateral triangular end plates are rigid, and the pivots freely
rotate:**

**An additional three equilateral triangles can be erected on the
apex triangle, turning it into a tetrahedron, and providing support
surfaces for the three smaller branches constituting the next level of
the tree:**

**Adding scaled-down versions of the structure gives us a two-level
actuated bush robot. Note that for this actuated structure, unlike
the bounding skin depictions, the internal tetrahedrons must exist to
give the structure essential rigidity. Of course, they need not be
solid, as shown, but could consist of simply an open rigid framework.
On the other hand, the enclosed tetrahedral volumes might be an ideal
place to package the energy storage and computation machinery needed
to control a real robot bush. Following are depictions of two-level
and three-level Stewart platform robot bushes:**