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 = MD     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 Bn x S 2n , 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 BN fingertips, any one of which can be specified with log(BN) = 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 /((B3)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 F1) fingers are tangent to the disk at their tips. Call the disk angle they subtend, part of a right triangle that defines = atan(F1/R ). By symmetry, the segment of the larger (length F 2) branch between its tangent and the smallest finger has length F1, and its subtended angle = . The remaining segment has length F2-F1, and its angle = atan((F2-F1)/R). Fingertip to fingertip subtends an angle . By symmetry, the left half tree subtends . Thus + + = .

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

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

Rmax(B = 2, D = 1, L = 1) = 0
Rmax(B = 2, D = 1, L = 2) =

The equations for L=3 are analogous:

FIGURE 2



= atan(F1/R )
a2 = atan(F1/R ) + atan((F2-F1)/R )
a3 = atan((F2-F1)/R ) + atan((F3-F2+F1)/R )

+ a2 + a3 = 2 atan(F1/R) + 2 atan((F2-F1)/R) + atan((F3-F2+F1)/R ) =

For general L , the relation becomes (EQ1 )



For a two-dimensional (B = 2, D = 1) robot, Fk = 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, Fk = 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: