**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

(Bush robots)

Jesse Easudes

Robotics Institute

5000 Forbes Avenue

Pittsburgh, PA 15213

USA

February 20, 1997

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

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.

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.

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.

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 10

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

The

**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

A robot with

Very high branching factors seem impractical, but the other extreme of

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

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

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.

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

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

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 ¼

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.

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.

Complex-plane-filling number systems are introduced in:

Knuth, Donald E.,

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,

Qualitative descriptions of the bush robot idea are found in:

Hans Moravec,

Marvin Minsky,

Fictional portrayals of bush robots are found in

Robert L. Forward,

Robert L. Forward,

Robert L. Forward and Julie Forward Fuller,

Robert L. Forward and Martha D. Forward,

Robert L. Forward and Martha D. Forward,

Robert L. Forward and Martha D. Forward,

Harry Harrison and Marvin Minsky,

a very attenuated form of bush robot is seen in the two-level branching of the manipulators on the EVA pods in the film

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