Fractal branching ultra-dexterous robots (Bush robots)
NASA ACRP Quarterly Report, February 1997, Hans Moravec
ADVANCED CONCEPTS RESEARCH PROJECTS
PR-Number 10-86888 Appropriation: 806/70110
CMU Cooperative Agreement NCC7-7
December 1, 1996 - February 27, 1997
Fractal branching ultra-dexterous robots
Carnegie Mellon University
5000 Forbes Avenue
Pittsburgh, PA 15213
February 20, 1997
R = MD
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.
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.
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.
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.
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
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.