Fractal branching ultra-dexterous robots (Bush robots)
NASA ACRP Quarterly Report, February 1997, Hans Moravec



NASA
ADVANCED CONCEPTS RESEARCH PROJECTS
PR-Number 10-86888 Appropriation: 806/70110
CMU Cooperative Agreement NCC7-7

Quarterly Report
for
December 1, 1996 - February 27, 1997







Fractal branching ultra-dexterous robots
(Bush robots)



Hans Moravec
Jesse Easudes


Carnegie Mellon University
Robotics Institute
5000 Forbes Avenue
Pittsburgh, PA 15213
USA




February 20, 1997


Table of Contents



Summary 3

Project Description 4

Fractal Finger Placement 10

Configuring Robot Bushes 13

References 14

Appendix 1: Bush Robot Grips 15

Appendix 2: Bush Robot Configurator 16

Appendix 3: Actuator Survey 17





Summary


This report is for the first quarter of Fractal branching ultra-dexterous robots, Bush robots for short. Much of the quarter was spent developing tools, including programs to construct, evaluate and draw bush robot configurations, and to examine fingertip placement patterns. We did a preliminary survey of actuators possibly suitable for mechanical implementations. Questions seemingly without end remain.

Early in February, we acquired a Silicon Graphics O2 computer, with R10000 processor, on with which we intend to simulate bush robots and display robot animations.

In the first two months of the quarter, only the principal investigator (Hans Moravec) participated in the project. A staff engineer (Jesse Easudes) with several years experience designing robots with mechanical design software (ProEngineer) joined in the last month of the period. A graduate student (Frank Dellaert) has expressed interest in doing a related project in the coming quarter.

Project Description


We are investigating an idea that would give robots dexterity greatly exceeding that of humans. A robot would be built to resemble an animated bush, its largest part being a stem with swiveling branches, but its potency arising from myriad swift microscopic, perhaps nanoscale, fingers after many levels of branching. It may have a completely regular structure, each subtree being a miniature version of the wholewhat has been called a fractal. With myriads of independent fingers, the smallest moving at high frequencies, the device could sense and effect the three dimensional physical world in parallel, manipulating it faster and with more resolution than images are manipulated by modern computer graphics. So far this bush robot idea has received only back-of-the-envelope attention. We propose to investigate the mathematics of the idea, to derive fairly detailed optimizations of the design and control for sample applications, which we will illustrate in simulations. We also plan to produce a preliminary mechanical design for a modest version having about 4 levels of branching and 16 end effectors. If the design looks promising, we may suggest building one in a future proposal.

Motivation

Most present day remote controlled and robot arms fall short of human dexterity, especially in their viselike hands, which are unable to manipulate complicated objects, or apply the combinations of forces needed to accomplish some simple tasks. These limitations, among others, exclude them from many interesting applications in construction, repair and exploration.

Some research manipulators achieve better dexterity by imitating the structure of the human hand, often at the expense of precision, strength, reliability and especially economy. Robot hands with three, four and five dexterous fingers have demonstrated the ability to roll eggs, twirl batons and tie knots.

There are imaginable tasks (for instance, those requiring simultaneously maneuvering together more than three uncooperative components in a precise way) for which even human dexterity is inadequate. Today, most are never attempted, while a few are approximated using specialized tools and fixtures.

Finer Fingers

It may be possible in future to leapfrog the dexterity not only of conventional mechanical manipulators, but of human hands. Consider the following observation.

Once upon a time, the most complex animal was a worm. The stick-like shape was poorly adapted for manipulation and even locomotion. Then these stick-like animals grew smaller sticks, called legs, and locomotion was much improved, although they were still poor at manipulating. Then the smaller sticks grew yet smaller sticks, and hands, with manipulating fingers were invented and precise manipulation of the environment became possible.

Generalize the concept. Visualize a robot that looks like a tree, with a big stem, repeatedly branching into thinner, shorter and more numerous twigs, finally ending up in vast numbers of microscopic cilia. Each intermediate branch would have several degrees of freedom of sensed and controlled motion. Though each branch would be a rigid mechanical object, the overall structure would have an organic flexibility because of the huge numbers of degrees of freedom. At the outer extremes, the machine would have an enormous number of individually positionable and naturally swift manipulators, coordinated for simultaneous execution of otherwise unimaginable tasks by signals and power from the central regions.

Taken far enough, the smallest fingers operate at nanoscale, able to shape matter at the atomic level. Compared to the free-floating, self-powered, self-directed nanobots envisioned by others, each nano finger in a bush robot would be a simple device, controlled, coordinated and powered by mechanically connected computers and energy sources located in the direction of its stem. Bush robots may provide a uniform, top down, incremental bridge to nanotechnology. Macroscopic machines with a few levels of branching could be built today, and could exhibit human-like dexterity. As microtechnology advances, the number of branching levels could be increased with ever finer sub-fingers. An ultimate nanoscale bush robot might begin with a stem a meter in length and a few centimeters in diameter, able to move with a one second timescale. At 30 levels of branching, one might find a billion fingers each a micron long, able to move at a megahertz. At 50 levels, there could be 1015 fingers, each a nanometer long, and in principle able to move at gigahertz rates, if not constrained by exotic physical effects.

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 S2n, 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 = 1/sqrt(2)) 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.

The simulation part of the project (whose results may be obtained in slower than real time, and often only for tiny fragments of complete bush) may address questions of mechanical strength and speed, power storage and computational requirements only superficially (there are, after all, so many interesting questions besides those). We propose also to undertake a paper mechanical design of a primitive, few level, bush, which should help focus on some of the practical considerations. We also plan to survey the micromechanics field and speculate on developments that would make more advanced robot bushes possible.


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 sqrt(B) - 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.

Appendix 1 gives some examples of 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 is 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.

In future we will investigate irregular covers, as well as further exploring uses of the regular ones.


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. Appendix 2 shows several robot bushes and configuration, and the program that configured them.

Appendix 2 also shows some more physically complete robot configurations generated by a mechanical design program, and Appendix 3 contains a survey of possible actuators, courtesy of Kevin Dowling, a graduate student completing a thesis on serpentine locomotion.

References

Complex-plane-filling number systems are introduced in:

Knuth, Donald E., The Art of Computer Programming, volume 2, Seminumerical Algorithms, Addison Wesley, 1969, page 172.

The idea of tree-structured (dendritic) robots is unexplored. Some lessons can be learned from other configurations with many actuators, especially tentacle or snake-like robots. An excellent reference is:

Shigeo Hirose, Biologically Inspired Robots: snake-like locomotors and manipulators, Oxford University Press, New York, 1993.
Qualitative descriptions of the bush robot idea are found in:

Hans Moravec, Mind Children: the future of robot and human intelligence, Harvard University Press, 1988.

Marvin Minsky, Will Robots Inherit the Earth?, Scientific American, v271n4, October 1994, pp. 108-113.

Fictional portrayals of bush robots are found in

Robert L. Forward, Flight of the Dragonfly, Timescape Books, 1984.
Robert L. Forward, Rocheworld, Baen Books, 1985.
Robert L. Forward and Julie Forward Fuller, Return to Rocheworld, Baen Books, 1990.
Robert L. Forward and Martha D. Forward, Ocean Under the Ice, Baen Books, 1994.
Robert L. Forward and Martha D. Forward, Marooned on Eden, Baen Books, 1995.
Robert L. Forward and Martha D. Forward, Rescued from Paradise, Baen Books, 1995.

Harry Harrison and Marvin Minsky, The Turing Option, Warner Books, 1992.

a very attenuated form of bush robot is seen in the two-level branching of the manipulators on the EVA pods in the film 2001: A Space Odyssey, Stanley Kubrick and Arthur C. Clarke, 1967.


APPENDIX 1

Bush Robot Grips

Successful and Unsuccessful Regular Fractal Covers



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).

The first line of each caption defines the mapping. B is the base of the system, equivalent to the branching factor of the corresponding robot. D is 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.


APPENDIX 2

Bush Robot Configurator


The robot configurator 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.

This Appendix shows several robot bushes and configuration, and the program that configured them. It also shows some more physically complete robot configurations generated by a mechanical design program


APPENDIX 3

Actuator Survey




A survey of possible actuators, courtesy of Kevin Dowling, a graduate student completing a thesis on serpentine locomotion. Snake robots consist of a large number of similar joints, and thus share some of the opportunities and problems of bush robots.