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



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

Quarterly Report
for
June 1, 1997 - August 31, 1997







Fractal branching ultra-dexterous robots
(Bush robots)



Hans Moravec



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




August 25, 1997





Table of Contents




Summary 3


Section 1: Choosing vertex directions in rigid bush grips 4


Section 2: Graphical 3D presentation of high-order bush 7


Section 3: Shape memory actuation for bush robot prototypes 8


Appendix - latest “rubber tree” positioning program 11


Summary


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

In this quarter 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. We call one of these positive and the other negative. The many binary choices accumulate to approximate many unconstrained degrees of freedom as the number of levels of the bush grows. We devised approaches to making these choices to configure bush grips in desired ways.

The quality of our 3D graphical presentations of the bush has advanced, and the resulting images are proving useful in revealing strengths and weaknesses in the positioning approaches.

Last quarter we had looked into using remote control servos to build a two-dimensional working model of a bush. This alternative looks less attractive after more careful investigation. The size range of available servos is about 4:1 permitting only about five levels of (B=2, D=1) branching, or fewer in a three-dimensional bush. In a two dimensional bush, some of the servos’ bulk and weight can be “hidden” in the third dimension, but they seem unsuitable for three-dimensional versions. We are now considering a much lighter design using shape-memory wire does work in 3D. Among its innovations is a “digital” muscle design, and endpoint rather than actuator servoing.
1: Choosing vertex directions in rigid bush grips

In this quarter 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.

In the first quarterly report we described a “rubber tree” algorithm for configuring bush robots. The algorithm 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 latest results can be seen in the 3D bush robot images in the next section, which show an order 10 (B=3, D=2) with 59,049 fingers. Most of the fingers are placed appropriately, but some penetrations can be seen in the smallest objects.


2: Graphical 3D presentation of high-order bush



The following two pages show a side and bottom view of a (B=3, D=2) bush with ten levels of branching. The bush is shown holding 36 balls of various sizes, perhaps in preparation to juggle them.


The bush was configured by the rubber tree program included in the appendix, with each ball exerting a repulsion on nearby nodes during the relaxation. The algorithm mostly succeeded, but some penetrations of the ball by branchlets can be seen in the smallest balls on the right.


The 3D images were rendered by Silicon Graphics “Cosmoplayer” VRML (Virtual Reality Modeling Language) plugin for Netscape, running on a high end SGI Reality Engine, capable of over 500 MIPS of general purpose computing and several times that for 3D graphics. It took just short of five hours on this machine to set up an internal 3D data structure, which could then be viewed from various viewpoints in tens of seconds. Each extra level of the tree, which multiplied the number of fingers threefold, multiplied the rendering time ninefold.

The Juggler

Bush robot side Bush robot bottom



3: Shape memory actuation for bush robot prototypes


Last quarter we had looked into using remote control servos to build a two-dimensional working model of a bush. This alternative looks less attractive after more careful investigation. The size range of available servos is about 4:1 permitting only about five levels of (B=2, D=1) branching, or fewer in a three-dimensional bush. In a two dimensional bush, some of the servos’ bulk and weight can be “hidden” in the third dimension, but they seem unsuitable for three-dimensional versions.

We are now considering a much lighter design using shape-memory wire does work in 3D. The thin shape-memory wire can be stretched while cold, and returns to its shorter original length with great force when electrically heated. In 2D, the following simple arrangement of a branchlet has one degree of freedom at its base.



The design scales straightforwardly. Smaller branches can use smaller nitinol wires, larger ones can use thicker wires, or more wires pulling in parallel. The parallel arrangement may be desirable, because the wires can then be wired electrically in series, reducing the heating current (at the expense of increased voltage), and thus the thickness of the current supply cabling.

Three wires could give two degrees of freedom in a three-dimensional branch:



Rotation could be added via two extra wires acting at right angles on the upper plate, or vertically via a screw linkage. Alternatively, six wires in a zig-zag pattern could provide pan, tilt and limited roll control:



The sketches above suggest only discrete motion: two positions in the 2D case, three or six in the 3D version. Finer control could be achieved if the length of the shape-memory “muscles” could be specified to more than two lengths. One idea for doing this would tap a nitinol wire at binary submultiples of its length, so segments could be selectively shorted to selectively prevent heating:



In the diagram, let the number defined by 0.d1d2d3d4d5d6 be called D. If the overall wire has a natural length L, and a stretched length of S, then the length for a particular setting is given by

Length = D*(M-L) + L


Two such tapped wires, mechanically connected in an opposing pair as in the first diagram of this section, each switched with the (ones) complement of the other’s pattern, could be set to a desired position simply by loading the position (and its complement) into the shorting switches as a binary number.

This open-loop design would not compensate for sagging at each joint. Yet, the overall motion could be servoed by measuring critical end positions, and tweaking the open loop settings of some of the branches to compensate.

We are in the process of collecting design information of suitable shape memory materials and evaluating mechanical arrangements.







APPENDIX

“Rubber Tree”
Configuration Algorithm