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



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

Quarterly Report
for
March 1, 1997 - May 31, 1997







Fractal branching ultra-dexterous robots
(Bush robots)



Hans Moravec
Frank Dellaert


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




May 20, 1997





Table of Contents



Summary 3

Optimal Robot Geometry 4

Maximum Grip Size with Branching Level 6

Two-dimensional bush robot prototype 10

Configuration by Simulated Annealing 12

Appendix 13



Summary


This is the second quarterly report for “Fractal branching ultra-dexterous robots.”

In this quarter we settled on three-way branching (B=3, D=2) as the most promising geometry for further investigation, because it offers statically rigid grips, and unique inverse kinematics, when all fingertip positions are determined.

We've begun investigating general constraints on bush robot grips. By considering spheres as first order approximations to arbitrary objects (they encode size, but no other aspect of shape), we've derived formulas relating the number of bush levels necessary to securely hold an object as a function of the ratio of the object radius to the length of the end fingers.

We are preparing for the construction of a two-dimensional physical prototype, primarily to help us develop some physical intuition about bush robots. For expediency, we will use remote control servos, driven by a small multiplexer board directed by a serial line from our computer. A range of servos will be installed in the joints of a (B=2, D=1) robot (which is the analog, in two dimensions, of a (B=3, D=2) robot in three dimensions). It will lie flat on a tiltable desktop-scale low friction surface. The design is constrained mainly by the sizes, torques and speeds of available servos. We expect to exhibit at least a four-level bush.

If the fingertips are not fixed, each contributes up to three unconstrained degrees of freedom. Frank Dellaert has investigated simulated annealing to position the fingers. By superimposing an attraction between the fingertips and a surface to be grasped, and a repulsion between the fingers, we can create an energy function that, when minimized, spreads the fingers fairly uniformly over the surface. So far, we've conducted several experiments in configuring two dimensional robots, successful enough to encourage us to begin implementation of a more practical 3D robot annealing package. We've been using our new Silicon Graphics computer to run the code, and display the results, and have made some available via the world wide web.

Background and definitions for notation in this report can be found in the first quarterly report for the project.
Optimal Robot Geometry

In this quarter we settled on three-way branching (B=3, D=2) as the most promising geometry for further investigation, because it offers statically rigid grips, and unique inverse kinematics, if all fingertip positions are determined. The reasoning follows.

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 in the first quarterly report. 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.

The 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 1/sqrt 3. 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 a1, part of a right triangle that defines a1 = atan(F1/R). By symmetry, the segment of the larger (length F2) branch between its tangent and the smallest finger has length F1, and its subtended angle a2a = a1. The remaining segment has length F2–F1, and its angle a2b = atan((F2–F1)/R). Fingertip to fingertip subtends an angle P. By symmetry, the left half tree subtends p/2. Thus a1 + a2a + a2b = p/2.

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 a1 = p/2, and a1 = p/6 = atan(F1/R), and

R = F1 / tan(p/6) = sqrt 3 F1


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) = sqrt 3


The equations for L=3 are analogous:

FIGURE 2



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

a1 + a2 + a3 = 2 atan(F1/R) + 2 atan((F2–F1)/R) + atan((F3–F2+F1)/R)
= p/2

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. We will attempt to find such a solution in the next reporting period. 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.

Two-Dimensional Bush Robot Prototype


There are too many uncertainties, at this early stage of the project, to undertake the design and construction of a full three-dimensional bush robot prototype. We would, however, like to gain some experience with the physical properties of such a thing. We will soon build simulations, but anticipate these will be slow and of limited realism. As a supplement, we have started the design of a much less mechanically challenging two-dimensional bush. It will allow us to quickly physically verify many proposed motion and manipulation techniques.

In three dimensions, we have settled on a (B=3, D=2) robot, that is, one that branches 3 ways at each level, with a scaling factor of 1/sqrt 3, giving the
end fingers a dimension of 2, allowing them to cover a surface uniformly, without overlap. A major advantage of the configuration is that when the three fingers of a final level twig are affixed to a surface, they form a rigid three-sided pyramid. The next level, built on three such groups, is a larger rigid structure, and so on to the root of the bush. Besides making for very strong grips, the rigidity means the configuration of each node is determined, and easily solvable, from the position of its three sub-nodes.

The closest analogy in two dimensions is a (B=2, D=1) robot, 2 way branching, scaling factor 1/2, whose fingers can cover a line uniformly. Each finger pair forms a rigid triangle when affixed to a line, resulting in a rigid truss work when all fingers are fixed. We will lay a (B=2, D=1) robot on a low friction surface, probably riding on ball casters. When we lay the surface flat, the effect of gravity will be absent. We can introduce gravity slowly by tilting the surface towards the vertical.

We plan to actuate the joints with commercial remote control servos, driven by a small multiplexer board directed by a serial line from our computer. Such servos are available over at least a 4:1 size range. For proper scaling, each reduction by two in size should be accompanied by a doubling in angular speed and a reduction in torque by a factor of four. We will select our servos to approximate these ratios as closely as possible.

To make the arms of the bush as compact as possible, we will stack the box-shaped servos above one another at each joint, with the narrow dimension across the width of the branch, as illustrated in the following diagram.


Configuration by Simulated Annealing




If a bush robot's fingertips are not fixed, each contributes up to three unconstrained degrees of freedom. Frank Dellaert has investigated using simulated annealing to position the fingers. By superimposing an attraction between the fingertips and a surface to be grasped, and a repulsion between the fingers, we can create an energy function that, when minimized, spreads the fingers fairly uniformly over the surface. By "shaking" the solution at various scales, the annealing process explores both local and global minima.

So far, we've conducted a few experiments in configuring two dimensional robots, successful enough to encourage us to implement a more practical 3D robot annealing package. This work has introduced us to tools on our new Silicon Graphics computer that will be useful in that and related tasks.

A more colorful and animated version of the text report is available on the Web at.

http://www.ius.cs.cmu.edu/IUS/usrp1/dellaert/projects/bush/index.html


APPENDIX

Programs and Notes
for Simulated Annealing