BIB-VERSION:: CS-TR-v2.0
ID:: CORNELLCS//TR94-1429
ENTRY:: 1994-06-27
ORGANIZATION:: Cornell University, Computer Science Department
LANGUAGE:: English
TITLE:: Analyzing Teams of Cooperating Mobile Robots
AUTHOR:: Donald, Bruce Randall
AUTHOR:: Jennings, James 
AUTHOR:: Rus, Daniela 
DATE:: June 1994
PAGES:: 8
ABSTRACT::
In [Don4], we described a manipulation task for cooperating mobile robots that 
can push large, heavy objects. There, we asked whether explicit local and 
global communication between the agents can be removed from a family of 
pushing protocols. In this paper, we answer in the affirmative. We do so by 
using the general methods of [Don4] analyzing information invariants. We 
discuss several measures for the information complexity of the task of pushing 
with cooperating mobile robots, and we present a methodology for creating new 
manipulation strategies out of existing ones. We develop and analyze 
synchronous and asynchronous manipulation protocols for a small team of 
cooperating mobile robots that can push large boxes. The protocols we describe 
have been implemented in several forms on the Cornell mobile robots in our 
laboratory.
END:: CORNELLCS//TR94-1429
BODY::
Analyzing Teams of
Cooperating Mobile Robots*
Bruce Randall Donald
James Jennings
Daniela Rus
TR 94-1429
June 1994
Department of Computer Science
Cornell University
Ithaca, NY 14853-7501
* Support for this work is provided in part by the NSF under grants No. lRl-90O0532,
IRI-9006137, by ONR under contracts No. N00014-92-J-1989 and N00014-92-J-39,
by a Presidential Young Investigator award, and by the Air Force office of Sponsored
Research, the Mathematical Sciences Institute, Intel Corporation, and AT&T Bell
Laboratories.
Analyzing Teams of Cooperating Mobile Robots1
Bruce Randall Donald			James Jennings			Daniela Rus
Robotics & Vision Laboratory
C??mputer Science Department
Cornell University
Ithaca, New York
Abstract
In [Don4J, we described a manipulation task for coop-
erating mobile robots that can push large, heavy objects.
There, we asked whether explicit local and global corn-
munication between the agents can be removed from a
family of pushing protocols. In this paper, we answer
in the affirmative. We do so by using the general meth-
ods of [Don4J analyzing informatton invanants. We dis-
cuss several measures for the information complexity of
the task of pushing with cooperating mobile robots, and
we present a methodology for creating new manipulation
strategies out of existing ones. We develop and analyze
synchronous and asynchronous manipulation protocols for
a small team of cooperating mobile robots than can push
large boxes. The protocols we describe have been imple-
mented in several forms on the Cornell mobile robots in
our laboratory.
1 Introduction
In this paper, we develop and analyze synchronous and
asynchronous manipulation protocols for a small team of
cooperating mobile robots than can push large boxes. The
boxes are typically several robot diameters wide, and 1-
2 times the mass of a single robot, although the robots
have also pushed couches that are heavier (perhaps 2-4
times the mass, and 8 x 3 robot diameters in size). We
build on the ground-breaking work of (Mason, EM] and
others on planar sensorless manipulation. Our work dif-
fers from previous work on pushing in several ways. First,
the robots and boxes are on a similar dynamic and spatial
scale. Second, a single robot is not always strong enough
to move the box by itself (specifically, its "strength" de-
pends on the effective lever arm). Third, we do not as-
sume the robots are globally coordinated and controlled.
Fourth, our protocols assume neither that the robot has a
geometric model of the box, nor that the first moment of
the friction distribution is known. Instead, the robot com-
bines sensorimotor experiments and manipulation strate-
1Support for this work is provided in part by the NSF under.
grants No. IRI-880239O, IR1-9000532, IRI-9006137, by ONR
under contracts No. NOOO1?92-J-19S9 and Nooo1492-J-39,
by a Presidential Young Investigator award, and by the Air
Force Office of Sponsored Research, the Mathematical Sciences
Institute, Intel Corporation, and AT&T Bell laboratories.
gies to infer the necessary information (the experiments
have the flavor of [JR]). Finally, the pushing literature
generally regards the ?pushers" as moving kinematic con-
straints. In our case, because (i) there are at least two
robot pushers and (ii) the robots are less massive than
the box, the robots are really "force-appliers" in a system
with significant friction. In this sense, our task is in some
ways closer in flavor to dynamic manip?!ation [ML], even
though the box dynamics are essentially quasi-static.
We develop a framework for analysis and synthesis,
based on information invariants (Don4], to reveal these
assumptions and expose the information structure of the
task. We believe our theory has implications for the
parallelization of manipulation tasks on spatially dis-
tributed teams of cooperating robots. To develop a par-
allel manipulation strategy, we start with a perfectly syn-
chronous protocol (one with global coordination and con-
trol). Next, in distributing it among cooperating, spa-
tially separated agents, we relax it to a MPMD2 protocol
with local communication and partial synchrony. Finally,
`11 exolicit			ication. The final nrotocols
we remove &			uffimull.
are essentially "uniform" in that the same program runs
on each robot. However, the result is asynchronous, and
hence it cannot be characterized as exclusively SPMD3
nor MPMD. Ultimately, the robots must be viewed as
communicating implicitly through the task dynamics, and
this implicit communication confers a certain degree of
synchiony on our protocols.
1.1 The Big Picture
Our goal here is to investigate the information re-
quirements for the pushing tasks. This paper uses
the theoretical framework and methodology introduced
in [Don,Don4]. A central theme to previous work [Don]
has been to determine what information is required to
solve a task, and to direct a robot's actions to acquire
that information to solve it. Key questions concern: (a)
How much internal state should the robot retain? (b)
How many cooperating agents are required, and how much
communication between them is necessary? (c) How can
the robot change (side-effect) the environment in order
to record state or sensory information to perform a task?
(d) How much information is provided by sensors? (e)
2Multiple Program, Multipk Data
3Single Program, Multiple Data
How much computation is required by the robot? and (f)
How much information is provided by the task mechanics?
These questions can be difficult. Structured environ-
ments, such as those found around industrial robots, con-
tribute towards simplifying the robot's task because a
great amount of information is encoded, often implicitly,
into both the environment and the robot's control pr?
gram. These encodings are difficult to measure. We wish
to quantify the information encoded in the assumption
that (say) the mechanics are quasi-static, or that the envi-
ronment is not dynamic. In addition to determining how
much "information" is encoded in the assumptions, we
may ask the converse: how much "information" must the
control system or planner compute? Successful manipu-
lation strategies often exploit properties of the (external)
physical world (e.g., compliance) to reduce uncertainty
and hence gain information. Often, such strategies ex-
ploit mechanical computation, in which the mechanics of
the task circumscribes the possible outcomes of an action
by dint of physical laws. Executing such strategies may
require little or no computation; in contrast, planning or
simulating these strategies may be computationaily ex-
pensive. Since d'?ring execution we may witness very lit-
tle "computation" in the sense of "aigorithm," traditional
techniques from computer science have been difficult to
apply in obtaining meaningful upper and lower bounds
on the true task complexity. We hope that a theory of
information invariants can be used to measure the sensi-
tivity of plans to particular assumptions about the world,
and to minimize those assumptions where possible.
In our quest for an intrinsic measure of the informa-
tion requirements of a task, we are inspired by Erdmann's
monograph on sensor design (Erd3i, and the information
invariants that Erdmann introduced to the robotics com-
munity in 1989 (Erd2]. We also observe that rigorous
examples of information invariants can be found in the
theoretical literature from as far back as 1978 (see, for
example, [BK, Kozi). This work was motivated by
the theoretical attack on perceptual equivalence begun
by [DJ] and by the experimental studies of [JRj. Hor-
swill [Horsj has developed a semantics for sensory sys-
tems that models and quantifies the kinds of assumptions
a sensori-computational program makes about its envi-
ronment. He also gives source-t?source transformations
on sensori-computational "circuits." The paper (Don4]
discusses the semantics of sensor systems. This formalism
is used to explore some properties of what we call sit?ated
sensor systems and describes a way to transform sensori-
computational systems. When one can be transformed
into another, we say the latter can be "reduced" to the
former, and we call the transformation a "reduction." We
also derive algebraic algorithms for reducing one sensor to
another. This machinery is only necessary if one wishes
to automate the transformation process; it is quite easy to
calculate reductions "by hand," using pencil and paper.
The goals outlined here are ambitious and we have ?nly
taken a small step towards them. There are several things
we have learned. We can determine a lot about the infor-
mation structure of a task by (i) parallelizing it and (ii) at-
tempting to replace explicit communication with commu-
nication "through the world". Communication "through
the world" takes place when a robot changes the environ-
ment and that change can be sensed by another robot.
Here we give two different protocols (strategies) for a 2-
robot pushing task: one protocol uses explicit commu-
nication and the other makes use of an encoding in the
task mechanics of the same information. Our approach
of quantifying the information complexity in the task me-
chanics involves viewing the world dynamics as a set of
mechanically implemented "registers" and "data paths".
This permits certain kinds of de facto communication be-
tween spatially separated robots. This `equivalence" of
task mechanics and communication is operational in fla-
vor, and we are still exploring its generality.
We believe that, by spatially distributing resources
among collaborating agents, the information characteris-
tics of a robot tas? ?r,' made explicit. That is, by asking,
Ho" can this task I irformed by a team of robots? one
may highlight the information structure. In robotics, the
evidence for this is, so far, largely anecdotal. In computer
science, one often learns a lot about the structure of an
algorithmic problem by parallelizing it; we argue that a
similar methodology is useful in robotics and illustrate
our methodology for the pushing task.
1.2 Outline
We discuss questions (a) --H (f) from Section 1.1 for an
experiment with communicating robots. We foreground
the task of pushing an object, using two communicating
robots who need to infer the position of the first moment
of the friction distribution with respect to their lines of
pushing (see Figure la). We present, analyze and com-
pare th `re pusing protocols using the tools introduced
in !Don4i. We do so by rigorously comparing embed-
ded sensori-computational systems, under the notion of
red"ction, which attempts to quantify when we can "effi-
ciently" build one sensor out of another. We also sketch
a general methodology for developing distributed manip-
ulation protocols. Our methods generalize to other ma-
nipulation tasks and to larger teams of robots [DJR].
2 Pushing with Two Communicating Mobile
Robots
2.1 Three Pushing Protocols
Consider the task whose goal is to push a box B in
a straight line. Figure la depicts one robot (the reader
should picture a robot manipulator, or gripper) executing
this task. The robot consists of two rigidly connected
fingen L and R; for example, they could be the fingers
of a parallel-jaw gripper. One complication involves the
micr?mechanical variations in the slip of the box on the
table [Masi. This phenomenon is very hard to model, and
hence it is difficult to predict the results of a one-fingered
push; we will only obtain a straight-line trajectory when
the center of friction (COF) lies on the line of pushing.
However, with a tw?fingered push, the box will translate
in a straight line so long as the COF lies between the
fingers. An advantage of the tw?finger pushing strategy
is that the COF can move some and the fingers can keep
pushing, since we only need ensure the COF lies in some
region C (see Figure la), instead of on a line. If the COF
M
A			_
B
A
Figure 1: (a) the "tw?finger" pushing task vs. (b) the two
robot pushing task. The goal is to push the block B in a
straight line.
moves outside C, then the fingers can move sideways to
?captur&' it again. We have implemented the control loop
described as Protocol 0 on our PUMA (see Figure 2). The
basic idea is to sense the reaction torque r about the point
o in Figure la. If r = 0, push forward in direction l'- If
r < 0 move the fingers in z; else move the fingers in --H:.
Repeat:
measure(r)
case (r = 0) ?
push(p)
(r < 0) ?
move(R)
(r > 0) ?
move(L)
Figure 2: Protocol 0 (for a twofingered gripper).
From the mechanics perspective it might appear we
are done. However, it is difficult to overstate how crit-
ically Protocol 0 above relies on global communication
and control. Now, consider the analogous pushing task
in Figure ib, in which mobile robots perform the push-
ing. The robots in our lab are autonomous and equipped
with a ring of 12 simple Polaroid ultrasonic sonar sen-
sors. Each robot has onboard processors for control and
programming. We equip each robot with 12 infra-red
modems/sensors, arrayed in a ring about the robot body.
Each modem consists of an emitter-detector pair. In ad-
dition, each robot has a ring of one-bit contact ("bump")
sensors.
We assume the following: (1) robots can sense the rel-
ative orientation of objects with which they are in con-
tact [JR]; (2) robots know that they are on the same flat
face of the object; (3) both robots know the direction of
pushing, p; and (4) robots can synchronize their veloci-
ties.
?xi(O)
Figure 4: Protocol I(QS). The normal to the box face is
denoted by n. The : axis is parallel to the direction of push-
ing p. The lines of pu?h ? are distance 2r apart (perpendicular
distance). 9 is the an?I?' between n and p.
The pushing strategy described as Protocol 0 can be
approximated by observing the following (see Figures ib,
3). Each robot can measure its applied force (fi or
and communicate this data to the other. This allows the
robots to compute the net torque r about a point in be-
tween the two robots, and from the sign of this quantity,
to infer the location of the first moment of the friction
distribution of the box. If the first moment of the fric-
tion distribution is between the two lines of pushing, each
robot continues pushing alone the line p. If there is a pos-
itive net torque, the instantaneous center of friction is to
the left of both robots. - In this situation, the left robot
is in contact with the box, while the right robot may or
may not be in contact. The left robot can "recapture"
the center of friction between the two lines of pushing by
moving left along the face of the box (move(L)). If the
right robot is not in contact with the box (the predicate
(break?) returns TRUE) it executes a guarded-move (mo-
tion until contact) in the direction p. Otherwise this robot
takes the null action, ?. The case when the net torque is
negative is symmetric. We call this Protocol I (see Figures
ib, 3).
A variant of this protocol can be derived for a quasi-
static (QS) system. Here, relative displacements along the
line of pushing p are measured instead of forces. Figure 4
shows a configuration where the two robots originate at
positions :i(O) and :2(0), respectively. Their locations
at time t are :1(t) and :2(t). In this protocol (Figure
5), the initial locations of the robots are communicated
to determine their offset S0. S0 "specifies" (or better,
pa?meterizea) the pushing task: this offset determines
the pushing direction p relative to the initial orientation
of the box face. The robots exchange location informa-
tion successively at each loop iteration; this information
Left Robot
Repeat:
measure(/i)
case
Communication			Right Robot
Repeat.
measure(/?)
r = r1 x fi --H r2 X /2
LR (sign(r))
case
= 0) ?			= 0) ?
push(p)			push(p)
(r < 0) ?			(T > 0) ?
if(breax?)			if(break?)
guarded-move (p)			guarded-move(p)
else ?			else ?
(r> 0) ?			(r <0) ?
move(L)			move( R)
Figure 3: Protocol I
is used to infer the direction of motion of the box. We
call this Protocol I(QS) (see Figures 4, 5).
n p
o ??
n			p
0
Figure 6: Protocol II.
R
We now derive a different version of Protocol I(QS) by
observing that the information needed to determine the
motion of the box (i.e. So and 5) is related to the an-
gle 0 between the normal to the face of the box n and
the direction of pushing p as follows: 2r tan 00 = 5o and
2r tan 0 = 5 (see Figures 4, 6, 7). Moreover, we observe
that the tangent function is monotonic and sign preserv-
ing; this means we can adapt the control system to servo
on 0 instead of 5, without knowing r. Specifically, the
robots measure 0o (the initial angle between n and p;
see tJRi), and compare this value to the angle 0(t) mea-
sured at time tin order to infer the direction of motion
of the box. The sign of the change in this angle defines
the sense of the rotation of the box. The robots adjust
their pushing location on the face of the box accordingly.
This is an example of how the robots can use the task
ri of emlidt ___ icatic `termip
svnarnlcs ?nste?			commulk - - ? ?u u?			x
their next actions. We call this pushing strategy Protocol
II (Figure 7).
2.2 Comparing the Protocols
Now, we ask, how do protocols I, I(QS), and II com-
pare to one another with respect to the questions (a)
(f) posed above? We first note that the three protocols
require different sensing capabilities. Protocol I relies on
force sensing, Protocol I(QS) relies on position sensing,
and Protocol II relies on orientation sensing. Next we
observe that the robots must coordinate to find locations
that result in a stable pushing along p. This coordina-
tion is accomplished differently in the three protocols. In
Protocol I and Protocol I(QS) the robots synchronize by
exchanging their sensed values. Robots executing Proto-
col I require communicating log/i bits to transmit the
value of force fi, and 2 bits to transmit the sign of the
torque r. Robots executing Protocol I(QS) require log ri
bits to transmit the value of the distance Zi, and 2 bits
to transmit the sign of a. In Protocol II there is no ex-
?licit communication and the synchronization is realized
through the world, by monitoring the change in the angle
0 between the normal to the face and the pushing direc-
tion. In other words, the robots infer the motion of the
object by decoding changes in the task mechanics. Thus,
?Iq T ?nrI T(OS? relv on di			frati'bile
pWtoc?			--H- -`			rect commuiL????on. w			-
protocol II does not. The internal state requirements of
the three strategies are also different. Protocol I requires
no internal state. Protocol I(QS) requires a register to
record the value 5o. Protocol II requires a register to
record the value 0o.
We can get a deeper understanding of the relationship
between these protocols by attempting to "transform" or
"reduce" one to the other. We do so below.
3 Reductions and Transformations
We present here a very brief summary of our model
of sensori-computational systems, which we view as cir-
cuits." (See (Don4] for a full treatment of these concepts.)
We model the circuits as graphs. Vertices correspond to
Left Robot
measure(x1 (0))
Repeat:
measure(r1 (t))
case
Communication			Right Robot
measure(x? (0))
[mR (zi(O))			= x2(O) --H xi(0)
Repeat:
mi
= x2(t) --H xi(t)
s = sign(? --H
LR (s)
case
= 0) ?			(5 = 0) ?
push (p)			push(p)
= --H1) ?			(s = --H1) ?
move(R)			move( R)
= 1) ?			(s = 1) ?
move(L)			move(L)
Figure 5: Protocol I (Quasi-Static) The cue for breaking contact is not shown; it can be handled as in Figure 3.
Left Robot			Right Robot
00 0(0)			0o --H 0(0)
Repeat:			Repeat
case			case
(break?) ?			(break?) ?
gnarded-rnove(p)			g,tarded-nove(p)
(0(t) Oo) ?			(0(t) Oo) ?
push(p)			push(p)
(0(t) > 0o) ?			(0(t) > Oo) ?
move(L)
(0(t) <Oc) ?			(0(t) <Oo) ?
move(R)
Figure 7: Protocol II. This protocol is "almost uniform," and can be made uniform by changing the e lines (e) to MovE(L) and
(**) to MovE(R). Note that "uniform" does not quite imply SPMD, since the protocols run asynchronously.
different sensori-computational components of the system
(what we will call "resources" below). Edges correspond
to "data paths" through which information passes. Dif-
ferent immersions of these graphs correspond to different
spatial allocation of the "resources." We also define an
operator + as a way to "combine" sensori-computational
systems. Below we use the term "sensor si,stem" to mean
"senson-compatational s?tem" where it is mellifluous.
3.1 Situated Sensor Systems
Definition 3.1 A labelled graph ? is a directed graph
(V, E) with vertices V and edges E, together with a la-
belling ?nction that assigns a label to each verte: and
edge. ?here there is no ambigaity, we denote the labelling
f?nction by .
See Figures 8-9 for illustrations for the circuits--Hthat
is, the sensor systems for protocols I (QS) and II, We will
use the terms protocol to refer to the computer programs
in Figures 5-7, and circvit for the sensor systems in Fig-
ures 8-9. In the figures, the components correspond to
boxes: ODOM is an odometer, the "signal"4 coming out
of this box is the odometry reading. The box ? performs
subtraction, the boxes :i(0) and are registers, and
they implement internal state. The part of the circuit Ia-
belIed case interfaces to the control part of the circuits,
which is the same for both protocols. For technical rea-
sons, we define a resource called "output." Each sensor
system must have exactly one vertex with this label. The
output vertex of the sensor system is where the output of
the sensor is measured.
4We use "signaI? as a metaphor; our circuits are strictly
digital. Either message or stream would be better, but both
have distracting religious connotations,
Definition 3.2 A sensor system S is represented by a
labelled graph (V, E). Each vefle: is labelled with a com-
ponent. Each edge is labelled with a connection.
n?,V??ruVQ
ruVi
comm(?j)
(6)			in,lt2? rUfl2
Comm (,)
(6')
0
0			0
0
0
L R
Figure 8: Sensor system P.I(QS), a circuit for Protocol I
(QS). This circuit shows one possible implementation of the
protocol. Figures 8-9 do not show how to handle lost of contact
(i.e., the (break?) cue), but this circuitry is euily added, and
is the same for both P.I(QS) and P.11.
INIT is one bit of state, and RUN= INIT. The small
crossed circles (?) that these bits run into are gates; the
I input must be 1 for the signal to pass.
Connections are like data-paths in that they carry in-
formation; a connection's label represents the information
that will be sent along that path. We adopt the conven-
tion that two components can communicate without an
(explicit) connection when they are spatially colocated.
Consider a sensor system with vertices V. For each
vertex v in V, we assume there is a configuration space
C. A point in this space C represents the configuration
of the component.
Definition 3.3 A situated (or immersed) sensor system
S is a sensor system S = (V, E), together with an im-
mersion ? : V C of the vertices. If v E V, then we
call ?v) the configuration of the vertex v. When there is
no ambigvity, we also call ?(v) the configuration of the
component ?(v).
We can now define what it means for two systems to
be equivalent:
Definition 3.4 Given two sensor systems 5 and Q, we
say Q simulates 5 if the o?tpat of Q is the same as the
ovtpvt of 5. In this case we write 5 "` Q. More gen-
erally, s'Lppose we write (S, ?) "-` (U, ?) for two sitaated
sensor systems. This is clearly well-defined when ? and
V			--HV
V-			`V-
V			VS
(5)
5			5
L a
Figure 9: Sensor system P.11, a circuit for Protocol II.
are total. Now, sappose t? ` t ? and ? are partial, leav-
ing anspecified the configarat'ons of components ?(v) of S
and e(v) of U. Then the definition is taken to mean that
(U,'k) simalates (S, ?) for any configaration of v and u.
3.2 Permutation
Definition 3.5 Let S = (S,?) be a sitaated sensor sys-
tem. A permutation S of S is a sitaated sensor system
(S,??) sa?ch that the domain ??1C of ? and the doma'n
??1C of? are the same.
We can also consider an alternate model, called edge
permatation, where the edge connectivity changes. Con-
sider a graph with vertices V and edges E. Start with any
bijection 0, : V2 V2. We call 0, an edge permatat:on,
since it induces the restriction map 0,?? : E 0,(E) on
the edge set E. In this paper we will restrict our edge
permutations to class edge permutation, in which we seg-
regate edges into two classes, and permute only within a
class.5 The two classes, internal and ezternal, correspond
to communication within and between (respectively) par-
ticular subcircuits. A subcircuit may represent, e.g. a
single mobile robot.
We define a graph permatation to be a vertex permu-
tation followed by an edge permutation.
Let (It, ?) be a situated sensor system. A graph per-
mutation of Ii is given by It. = (It, (?,0,)) where ? is a
vertex permutation, and 0, is an edge permutation.
3.3 Combination
Definition 3.6 Consider two graphs ? = (V, E) and
= (V', E'). We define the combination ? + ?` of g
and?' tobe?+?'=(VUW,EUE').
We may define + on sensor systems (Definition 3.2)
by lifting the definition for graphs. We may define + on
two immersed graphs whenever the immersions are com-
patible. An immersion ? of g and an immersion ? of g'
are said to be compatible when the two immersions agree
5Clue edge permutation leaves unchanged the complexity
bounds and the lemmu of [Don4).
on the intersection V n v' (for total immersions) or more
generally, on 4i-1C fl ?-1C (for partial functions). The
definition of --H is analagous.
3,4 Reductions, Calibration, and Codesignation
As we observed in [Don], calibration exploits external
state. Calibration complexity, defined formally in [Don4],
measures how much information we add to a sensor sys-
tem when we install and calibrate it. Installing a sensor
system may require physically establishing some spatial
relation between two components of the system. In this
case we say the two components codesignate by the spa-
tial relation. More generally, we may have to establish a
relation between a component and a reference frame in
the world.
Definition 3.7 We write 5 < Q when (1) Q sim?ates
5 (5 ? Q), (2) 5 dominates Q in calibration complexity,
and (3) the manmam bandwidth of 5 is at least that of Q
(def. 3.9 below).
Definition 3.8 We write 5 < Q if there exists a
(graph) perm?tation Q of sensor system Q s?ch that
3.5 Reductions using Communication
Definition 3.9 We define the internal (resp., external)
bandwidth of a sensor system S to be the greatest band-
width of any internal (resp., external) edge in S. The raw
output size ofS is the size of the valae it o?tpats. We
define the maximurn bandwidth of S to be the greatest of
the internal bandwidth, external bandwidth, and the raw
oatpat size of S.
We define COMM(S) to be CoMM(2k) where k is the
maximam bandwidth (Definition 3.9) of 5; we treat I: as
an upper bound on relative intrinsic oatpat complexity of
5.
Definition 3.10 Consider ta'o sensor systems 5 and Q.
We say 5 is efficiently reducible to Q if
5 < Q + COMM(S).
In this case we write 5 <i Q.
The sensor system (Q+CoMM(5)) from the definition
may be implemented as the sensor system Q permuted in
an arbitrary way, plus one extra data path whose band-
width is that of the largest flow in 5.?
The reduction <i (Definition 3.10) is a ?1-wir? reduc-
tion. It does not appear to be transitive. The reduction
< (Definition 3.8) is a "0-wire"reduction. It is transitive
for simple sensor systems (Don4]. We could analogously
define a k-wire redaction <k by modi?ring the equation
in definition 3.10 to read 5 < Q + k COMM(S), where
k times
k COMM(S) denotes COMM(S) + ... + COMM(S).
6See proof in [Don4].
4 Comparing Protocols Using Reductions
We now apply the ideas above to compare our proto-
cols, P.I(QS) and P.11 (the circuits in Figures 5--H7).
Theorem 4.1 Let P.11, P.I(QS), ODOM, and 0 be the sen-
sor systems defined as above, Then,
P.11			<k P.I(QS) --H 2ODOM + 0			(1)
for k = 1. Moreover, eq. (1) does not hold for k = 0.
Proof: Consider the sensor system U obtalned by remov-
ing both odometers from circuit P.I(QS), and adding a
0-source:
IA = P.I(QS) --H 2ODOM + 0.			(2)
Now, consider permutations of IA, and recall Defini-
tion 3.8. We first ask whether P.11 can be reduced to IA
using <?. That is P II < IA? First, we note that we can
move around the registers and ?s from IA to situate all
the components of P.11. We also have some leftover compo-
nents and wires). P.11 requires two sign boxes; however,
the SGN box just selects out the sign bit. To build the
extra sign box we can just ignore the other bits, or we can
use the leftover hardware from IA to build a small circuit
to simulate SGN - We need to argue that a register big
enough to ho x,(0) will also hold 0o; this follows from
2rtan0(t) = S(t), or from "decalibration" (Hors]. Next,
we see that we can permute the internal edges of IA to
wire up the components of P.11 in sita--Hinternally. What
about externally?
Permuting the external wiring almost works, but not
quite. IA has two external data paths, (b') and (b), with
bandwidth 2 bits and log Ax1 bits (resp) (Figure 8). Now,
since we only allow class edge permutation (as in Sec-
tion 3.2), we must permute external edges to external
edges and internal edges to internal edges. Therefore, in
Figure 9, the edge (b) from IA will suffice as a datapath
from 0(t) to R, since it has adequate bandwidth. How-
ever, the datapath (b') from IA does not have adequate
bandwidth to carry information from 0(t) to L. In order
to build P.11 from IA, we must add another external data
path cOMM(.) from 0(t) to L. Now, what is the argument
to CoMM(.)? This data path must have bandwidth of at
least the relative intrinsic output complexity of P.11, or
log AO bits. Hence we may parameterize this new edge by
writing COMM(P.II), following Section 3.5. Hence, we see
that
P.11			< (IA + COMM(P.fl))'.			(3)
Therefore by Definition 3.8,
P.11			< IA + cOMM(P.II),			(4)
so using Definition 3.10, we have P.11 Si IA Hence we
conclude
(5)
P.11 <-i P.I(QS) --H 2ODOM +0,
which implies eq. (1) as desired. 0
This formalizes our intuition that, by removing odom-
etry but adding relative normal sensing, we can accom-
plish the pushing task without explicit communication.
More precisely, we show how to build one circuit P.11 "ef-
ficiently" out of the other (U). To transform P.I(QS) into
P.11, the operators + and --H quantify what resources we
add and delete. Relative information complexity allows
us to measure the effective communication "through the
world." The permutation quantifies the redistribution of
resources.
5 Computing Reductions
Theorem 4.1 is a proof done "by hand." That is, we
can in principle determine that eq. (1) holds (for k > 0)
by showing--H"by hand" --Hthe existence of a suitable per-
mutation. It is somewhat surprising that we can in fact
automate this process: [Don4] gives algorithms for decid-
ing the relation <i. More precisely, given suitable en-
codings of two sensor systems S and U, we can computa-
tionally decide whether S <1 U [Don4]. The algorithm is
too complicated to describe here. The basic idea involves
employing the theory nf real closed fields with bounded
quantification.
6 Conclusion
We hope that by analyzing the manipulation protocols
presented in this paper, we have been able to reveal the
information structure of the cooperative pushing task. In
our laboratory, multiple mobile robots are executing these
strategies and others for both pushing and reorientation
of large objects tDJRl. In analyzing the results of our
experiments, we have demonstrated precise equivalences
between different types of sensing, communication, and
internal and external state, by reducing one sensor system
to another; the nature of these equivalences is conditioned
by the task.
We may ask at this time any number of specific ques-
tions about th? theory of information invariants and the
application of tltat theory. For example, can we record
"programs" in the world in the same way we may exter-
nalize state? Is there a "universal" manipulation circuit
which can read these programs and perform the correct
strategy to accomplish a task? Such a mechanism might
lead to a robot which could infer the correct ni anipulation
action by performing sensori-motor experiments, thus ob-
viating the need for the specific protocols we have ana-
lyzed here.
We think that information invariants can ??`r?.' as a
framework in which to measure the capabilities r robot
systems, to quantify their power, and to reduce their
fragility with respect to assumptions that are engineered
into the control system or the environment. We believe
that the equivalences that can be derived between com-
munication, internal state, external state, computation,
and sensors, can prove valuable in determining what in-
formation is required to solve a task, and how to direct a
robot's actions to acquire that information to solve it.
Bibliography
[BIK] Blum, M. and Kozen, D. On the power of the
compass (or, why ma?es are easier to search than ?raphs),
Proc, 19th Symp. Found, Computer Science, Ann Arbor, MI.
pp- 132-42 (1978).
[Don] Donald, B. R. Information Invariants in Robotics,
Parts I and II, IEEE International Conference on Robotics and
Automation, Atlanta, GA. (1993).
[Don4] Donald, B. R. On Information Invariants in
Robotics, Cornell Computer Science Department Technical Re-
port TR 93-1341. (1993).
[DJ] Donald, B. R. and J. Jennings Construc-
tive Recogntzability for Task-Directed Robot Programming,
Jour. Robotics and Autonomous Systems, (9), No 1,
Elsevier/North-Holland pp. 41-74. (1992).
[DJR] Donald, B. IR., J. Jennings, and D. Rus E:peri-
mental Information Invariants for Cooperating Autonomovs
Mobile Robots, International Joint Conference on Artificial
Intelligence (IJCAI) Workshop on Dynamically Interacting
Robots. Chambery, France (Aug 28) (1993).
[Erd2] Erdmann, M. On Probabilistic Strategies for Robot
Tasks, Ph.D. thesis, MIT Department of EECS, MIT A.I. Lab,
Cambridge MIT-AI-TR 1155 (1989).
(Erd3] Erdmann, M. Action Subservient Sensing and De-
sign, IEEE ICRA, Atlanta. See also the Carnegie-Mellon re-
port CMU-CS-92-116. (1993).
[EM] Erdmann, M., and M. Mason, `An Exploration of
Sensorless Manipulation", IEEE International Conference on
Robotics and Automation, San Francisco, April, 1986.
[Gri] Grigoryev D. Yu., "Complexity of Deciding Tarski
Algebra" Jour. Symbolic Computation, 5, (1), (1988), pp. 65-
108.
[Hors] Horswiii, I. Analvsis of Adaptation and Environ-
ment, Submitted to Artificial Intellig?'nce (1992).
[JR] Jennings, J. and Rus, D. Active Model Acquisition
for Near-Sensorless Manipuiation with Mobile Robots, The
lASTED International Conference on Robotics and Manufac-
turing, Oxford, UK (1993).
[Koz] Kozen, D. Autoinata and Planar Graphs, Pundamen-
tals of Computing Theory, Proc. Conference on Algebraic,
Arithmetic, and categorical methods in Computation Theory
(Berlin) ed. L. Budach, Akademie Verlag (1979).
[Mas] Mason, M. T. 1986. Mechanics and Planning of
Manipulator Pushing Operations. International Journal of
Robotics Research 5(3).
[ML] Mason, M. and Lynch, K. D?amic Manipulation,
Proc. of the 1993 IEEE/RSJ Int. Conf. on Intelligent Robots
and Systems, Yokohama, Japan, July 2630 (1993).
[Rus] Rns, D. "Fine Motion Planning for Dexterous Manipu-
lation", PhD. Thesis a'asilable as CU-CS-TR 92-1323 (August)
from Comp. Sci. Dept., Cornell University, 1992.
Acknowledgment. Many key ideas in this paper arose in dis-
cussions with Tom? Losan?P?res, Mike Erdmann, Matt Ma-
son, and Ronitt Rubinfeld. The robots and experimental de-
vices described herein were built in our lab by Jim Jennings,
Russell Brown, Jonathan Rees, Cralg Becker, Mark Battisti.
and Kevin Newman; these ideas could never have come to
light without their help. Debbie Lee Smith, Amy Briggs, and
KarI-Freidrich Bo?hringer made suggestions and helped draw
the other figures, and we are very grateful to them for their
help.
