BIB-VERSION:: CS-TR-v2.0
ID:: CORNELLCS//TR93-1383
ENTRY:: 1993-10-14
ORGANIZATION:: Cornell University, Computer Science Department
LANGUAGE:: English
TITLE:: Towards a Theory of Information Invariants for Cooperating Autonomous 
        Mobile Robots
AUTHOR:: Donald, Bruce Randall
AUTHOR:: Jennings, James 
AUTHOR:: Rus, Daniela 
DATE:: September 1993
PAGES:: 28
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: 
(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? and (e) How much 
computation is required by the robot? To answer these questions, we develop a 
notion of information invariants. We develop a technique whereby one sensor 
can be constructed from others by adding, deleting, and reallocating 
(a) - (e) among collaborating autonomous agents. We add a resource to 
(a) - (e) and ask: (f) How much information is provided by the task 
mechanics? By answering this question, we hope to develop information 
invariants that explicitly trade-off resource (f) with resources (a) - (e). 
The protocols we describe here have been implemented in several different 
forms, and we will show a video reporting on experiments to measure and analyze
information invariants using a pair of cooperating mobile robots for
manipulation experiments in our laboratory.
END:: CORNELLCS//TR93-1383
BODY::
Towards a Theory of Information Invariants for
Cooperating Autonomous Mobile Robots*
Bruce Randall Donald
James Jennings
Daniela Rus
TR 93-1383
September 1993
Department of Computer Science
Cornell University
Ithaca, NY 14853-7501
*This paper describes research done in the Robotics and Vision Laboratory at Cornell
University. support for our robotics research is provided in part by the National
Science Foundation under grants No. IRI-8802390, lRI-9000532, and by a
Presidential Young Investigator award, and in part by the Air Force Office of
Sponsored Research, the Mathematical Sciences Institute, Intel Corporation, and
AT&T Bell laboratories. The third author has been supported by the Advanced
Research Projects Agency of the Defense Department under ONR Contract N00014-
92-J-1989, by ONR Contract N00014-92-J-39, and by NSF Contract lRI-9006137.
Towards a Theory of Information Invariants for
Cooperating Autonomous Mobile Robots1
Abstract
Bruce Randall Donald James Jennings
R?obotics & Vision Laboratory
Computer Science Department
Cornell University
Ithaca, New York
In [Don4], we described a manipulation task for Co-
operating mobile robots that can push large, heavy
objects. There, we asked whether explicit local and
global communication between the agents can be re-
moved from a family of pushing protocols. In this pa-
per, 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: (a) How much internal state
should the robot retain? (b) How many cooperat-
ing agents are required, and how much communica-
tion 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 sen-
sors? and (e) How much computation is required by
the robot? To answer these questions, we develop a
notion of information invariants. We develop a tech-
nique whereby one sensor can be constructed from
others by adding, deleting, and reallocating (a) --H
among collaborating autonomous agents. We add a
resource to (a) --H (e) and ask: (f) How much informa-
A shorter version of this paper will he presented at ISRR
(the International Symposium of Robotics Research), 0ct. 1
1993, Hidden Valley, PA.
This paper describes research done in the Robotics and Vision
Laboratory at Cornell University. Support for our robotics re-
search is provided in part by the National Science Foundation
under grants No. IRI-8802390, IRI-9000532, and by a Presi-
dential Young Investigator award, and in part by the Air Force
0ffice of Sponsored Research, the Mathematical Sciences In-
stitute, Intel Corporation, and AT&T Bell laboratories. The
third author has been supported by the Advanced Research
Projeds Agency of the Defense Department under 0NR Con-
tract N00014-92-J-1989, by 0NR Contract NOO()14-92-J-39,
and by NSF Contract IRI-9006137.
Daniela Rus
tion is provided by the task mechanics? By answer-
ing this question, we hope to develop information in-
variants that explicitly trade-off resource (f) with re-
sources (a) --H (e). The protocolswe describe here have
been implemented in several different forms, and we
will show a video at ISRR1 reporting on experiments
to measure and analyze information invariants using
a pair of cooperating mobile robots for manipulation
experiments in our laboratory.
Contents
2
3
Introduction			2
1.1			The Big Picture .			2
1.1.1 Research Agenda			.			5
1.2			0utline . . 			.			6
with Two Communicating Mobile
7
10
Pushing
Robots
2.1 Three Pushing Protocols
2.2 Comparing the Protocols
Reductions and Transformations
3.1 Situated Sensor Systems .
3.2 Transformations as Reductions
3.3 Permutation
3.4 Combination
3.5 Reductions, Calibration, and Codesignation
3.5.1 Relativized Information Complexity
3.5.2 Reductions using Communication
4 Comparing Protocols Using Reductions
5 Computing Reductions
6 Sensitivity of the Model
7 Experiments
7.1 Removing Assumptions
7.2 Reorienting Large 0bjects
8 Discussion
A What is Permutation?
A.1			Example			.			. .
11
11
13
14
15
16
16
17
18
19
21
22
22
23
24
25
26
1 Introduction
In this paper, we develop and analyze syn-
chronous and asynchronous manipulation pro-
tocols 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 differs
from previous work on pushing in several ways.
First, the robots and boxes are on a similar dy-
namic and spatial scale. Second, a single robot
is not always strong enough to move the box by
itself (specifically, its "strength" depends on the
effective lever arm). Third, we do not assume the
robots are globally coordinated and controlled.
(More precisely, we first develop protocols based
on the assumption that local communication is
possible, and then we subsequently remove that
communication via a series of source-to-source
transformations on the protocols). Fourth, our
protocols assume neither that the robot has a
geometric model of the box, nor that the first
moment of the center of friction is known. In-
stead, the robot combines sensorimotor experi-
ments and manipulation strategies to infer the
necessary information (the experiments have the
flavor of [JR]). Finally, the pushing literature
generally regards the "pushers" as moving kine-
matic constraints. 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 re-
ally "force-appliers" in a system with significant
friction. In this sense, our task is in some ways
closer in flavor to dynamic manipulation [ML],
even though the box dynamics are essentially
quasi-static.
Of course, our protocols rely on a number of
assumptions in order to work. We develop a
framework for analysis and synthesis, based on
information invariants [Don4], to reveal these
assumptions and expose the information struc-
ture of the task. We believe our theory has
implications for the parallelization of manipula-
tion tasks on spatially distributed teams of co-
operating robots. To develop a parallel manip-
ulation strategy, first we start with a perfectly
synchronous protocol. Next, in distributing it
among cooperating, spatially separated agents,
we relax it to a MIMD protocol with local com-
munication and partial synchrony. Finally, we
remove all explicit communication. The final
protocols 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 SIMD nor MIMD.
Lfltimately, the robots must be viewed as com-
municating implicitly through the task dynam-
ics, and this implicit communication confers a
certain degree of synchrony on our protocols. Be-
cause it is both difficult and important to analyze
the information content of this implicit commu-
nication and synchronization, we are wielding a
fairly heavy hammer, namely the theory of infor-
mation invariants.
1.1 The Big Picture
Our goal is to investigate the information re-
quirements for robot tasks. This paper uses
the theoretical framework introduced by Donald
in [Don,Don4]. A central theme to previous work
(see the survey article [Don1] for a detailed re-
view) 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:
1. What information is needed by a particular
robot to accomplish a particular task?
2. How may the robot acquire such informa-
tion?
3.
4.
What properties of the world have a
great effect on the fragility of a robot
plan/program?
What are the capabilities of a given robot
(in a given environment or class of environ-
ments)?
These questions can be difficult. Structured
environments, such as those found around indus-
trial robots, contribute towards simplifying the
robot's task because a great amount of informa-
tion is encoded, often implicitly, into both the
environment and the robot's control program.
These encodings (and their effects) are difficult
to measure. We wish to quantify the informa-
tion encoded in the assumption that (say) the
mechanics are quasi-static, or that the environ-
ment is not dynamic. In addition to determining
how much "information" is encoded in the as-
sumptions, we may ask the converse: how much
"information" must the control system or plan-
ner compute? Successful manipulation strategies
often exploit properties of the (external) physi-
cal world (eg, compliance) to reduce uncertainty
and hence gain information. Often, such strate-
gies exploit mechanical computation, in which
the mechanics of the task circumscribes the pos-
sible outcomes of an action by dint of physical
laws. Executing such strategies may require lit-
tle or no computation; in contrast, planning or
simulating these strategies may be computation-
ally expensive. Since during execution we may
witness very little "computation" in the sense
of "algorithm," traditional techniques from com-
puter science have been difficult to apply in ob-
taining meaningful upper and lower bounds on
the true task complexity. We hope that a theory
of information invariants can be used to measure
the sensitivity of plans to particular assumptions
about the world, and to minimize those assump-
tions where possible.
We would like to develop a notion of informa-
tion invariants for characterizing sensors, tasks,
and the complexity of robotics operations. We
may view information invariants as a mapping
from tasks or sensors to some measure of infor-
mation. The idea is that this measure charac-
terizes the intrinsic information required to per-
form the task if you will, a measure of com-
plexity. For example, in computational geom-
etry, a rather successful measure has been de-
veloped for characterizing input sizes and upper
and lower bounds for geometric algorithms. Un-
fortunately, this measure seems less relevant in
robotics, although it remains a useful tool. Its
apparent diminished relevance in embedded sys-
tems reflects a change in the scientific culture.
This change represents a paradigm shift from of-
fline to online algorithms. Increasingly, robotics
researchers doubt that we may reasonably as-
sume a strictly offline paradigm. For example,
in the offline model, we might assume that the
robot, on booting, reads a geometric model of
the world from a disk and proceeds to plan. As
an alternative, we would also like to consider on-
line paradigms where the robot investigates the
world and incrementally builds data structures
that in some sense represent the external envi-
ronment. Typically, online agents are not as-
sumed to have an a priorn' world model when the
task begins. Instead, as time evolves, the task
effectively forces the agent to move, sense, and
(perhaps) build data structures to represent the
world. From the online viewpoint, offline ques-
tions such as "what is the complexity of plan
construction for a known environment, given an
a priorn' world model?" often appear secondary,
if not artificial. In this paper, we describe two
working robots TOMMY and LILY, which may be
viewed as online robots. We discuss their ca-
pabilities, and how they are programmed. These
examples and the papers [JR,Don,Don4] link our
work to the recent but intense interest in on-
line paradigms for situated autonomous agents.
In particular, in these papers, we discuss what
kind of data structures robots can build to repre-
sent the environment. We also discuss the exter-
nalization of state, and the distrn'bation of state
through a system of spatially separated agents.
We believe it is profitable to explore online
paradigms for autonomous agents and sensori-
motor systems. However, the framework remains
to be extended in certain crucial directions. In
particular, sensing has never been carefully con-
sidered or modeled in the online paradigm. The
chief lacuna in the armamentarium of devices for
analyzing online strategies is a principled theory
of sensori-computational systems. We attempt
to fill this gap in [Don,Don4], where we provide
a theory of situated sensor systems. We argue
this framework is natural for answering certain
kinds of important questions about sensors. Our
theory is intended to reveal a system's informa-
tion invariants. When a measure of intrinsic in-
formation invariants can be found, then it leads
rather naturally to a measure of hardness or dif-
I)			9
ficulty. If these notions are truly intrinsic, then
these invariants could serve as "lower bounds"
in robotics, in the same way that lower bounds
have been developed in computer science.
In our quest for an intrinsic measure of the
information requirements of a task, we are in-
spired by Erdmann`s monograph on sensor de-
sign [Erd3], and the ?nformation invariants that
Erdmann introduced to the robotics community
in 1989 [Erd2]. We also observe that rigor-
ous examples of information invariants can be
found in the theoretical literature from as far
back as 1978 (see, for example, [BI&, Koz]). We
note that many interesting lower bounds (in the
complexity-theoretic sense) have been obtained
for motion planning questions (see, eg, [Reif,
HSS, Nat, CR]; see, eg, [Erdi, Don2, Can, Bri]
for upper bounds). Rosenschein has developed a
theory of synthetic automata which explore the
world and build data-structures that are "faith-
ful" to it [Ros]. His theory is set in a logical
framework where sensors are logical predicates.
Perhaps our theory could be viewed as a geo-
metric attack on a similar problem. This work
was motivated by the theoretical attack on per-
ceptual equivalence begun by [DJ] and by the
experimental studies of [JR]. Horswill [Hors] has
developed a semantics for sensory systems that
models and quantifles the kinds of assumptions
a sensori-computational program makes about
its environment. He also gives source-to-source
transformations on sensori-computational "cir-
cuits." The paper [Don4] discusses the seman-
tics of sensor systems. This formalism is used to
explore some properties of what we call situated
sensor systems. [Don4] describes a way to trans-
form sensori-computational systems. When one
can be transformed into another, we say the for-
mer can be "reduced" to the latter, and we call
the transformation a "reduction." We also de-
rive algebraic algorithms for reducing one sensor
to another. This machinery is only necessary if
one wishes to automate the transformation pro-
cess; it is quite easy to calculate reductions "by
hand," using pencil and paper.
In addition to the work discussed here in sec. 1,
for a detailed bibliographic essay on previous re-
search on the geometric theory of planning under
uncertainty, see, eg., [Don1] or [Don3].
The goals outlined here are ambitious and we
have only taken a small step towards them. The
questions above provide the setting for our in-
quiry, but we are far from answering them. We
hope that information invariants can serve as a
framework in which to measure the capabilities
of robot systems, to quantify their power, and
to reduce their fragility with respect to assump-
tions that are engineered into the control system
or the environment. We believe that the equiva-
lences that can be derived between communica-
tion, internal state, external state, computation,
and sensors, can prove valuable in determining
what information is required to solve a task, and
how to direct a robot's actions to acquire that in-
formation to solve it. There are several things we
have learned. We can determine a lot about the
information structure of a task by (i) paralleliz-
ing it and (ii) attempting to replace explicit com-
munication with communication "through the
world" (through the task dynamics). Commu-
nication "through the world" takes place when a
robot changes the environment and that change
can be sensed by another robot. In this paper
we give two different protocols (strategies) for a
2-robot pushing task: one protocol uses explicit
communication and the other makes use of an
encoding in the task mechanics of the same infor-
mation. Our approach of quantifying the infor-
mation complexity in the task mechanics involves
viewing the world dynamics as a set of mechani-
cally implemented "registers" and "data paths".
This permits certain kinds of de facto communi-
cation between spatially separated robots. This
"equivalence" of task mechanics and communi-
cation is operational in flavor, and we are still
exploring its generality.
We believe that, by spatially distributing re-
sources among collaborating agents, the infor-
mation characteristics of a robot task are made
explicit. That is, by asking, How can this task
be performed by a team of robots? one may high-
light 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 Jgorithmic problem by par-
allelizing it; we argue that a similar methodology
is useful in robotics.
It is very difficult to analyze the interaction
of sensing, computation, communication (a
and mechanics (f) in distributed manipulation
tasks. The analyses of [Don4] focus on (a --H
and each analysis is "parameterized" by the task.
This paper represents an attempt to integrate a
measure of the "information content of the task
mechanics" (f) into the theory. Nevertheless, the
theory is still biased towards sensing, and it re-
mains to develop a framework that treats action
and sensing on an equal footing.
This paper draws extensively on the mate-
rial reported in the draft monograph by Don-
ald [Don4], and announced in an abbreviated,
preliminary version in [Don]. We reported on our
ideas on coordinated manipulation strategies in
a preliminary form in [DJR].
1.1.1, Research Agenda
Robot builders make claims about robot per-
formance and resource consumption. In general,
it is hard to verify these claims and compare the
systems. We really think the key issue is that
two robot programs (or sensor systems) for sim-
ilar (or even identical) tasks may look very dif-
ferent. We discuss why it is hard to compare
the "power" of such systems. Our examples are
distinguished in that they permit relatively crisp
analytical comparisons: they represent the kinds
of theorems about information trade-offs that we
believe can be proved for sensorimotor systems.
The analyses in sec. 2 reveal trade-offs in terms
of resource consumption. We then ask, is there
a general theory quantifying the power gained
in such trade-offs? In sec. 3, we present a the-
ory, which represents a systematic attempt to
make such comparisons based on geometric and
physical reasoning. In [Don4], we operational-
ize our analysis by making it computational; we
give effective (albeit theoretical) procedures for
computing our comparisons. See sec. 5 for a sum-
mary.
We wish
to rigorously compare embedded
sensori-computational systems. To do so, we de-
fine a "reduction" ? i that attempts to quan-
tify when we can "efficiently" build one sensor
out of another (that is, build one sensor using
the components of another) 2 Hence, we write
A ?i B when we can build A out of B without
"adding too much stuff." The last is analogous to
"without adding much information complexity."
Our measure of information complexity is rela-
t?v?zed both to the information complexity of the
sensori-computational components of B, and to
the bandwidth of A. This relativization circum-
vents some tricky problems in measuring sensor
complexity. In this sense, our "components" are
analogous to oracles in the theory of computa-
tion. Hence, we write A ?i B if we can build
a sensorimotor system that simulates A, using
the components of B, plus "a little rewiring." A
and B are modeled as circuits, with wires (dat-
apaths) connecting their internal components.
However, our sensori-computational systems dif-
fer from computation-theoretic (CT) "circuits,"
in that their spatial configuration i.e., the spa-
tial location of each component is as important
as their connectivity.
We develop some formal concepts to facilitate
the analysis. Permutation models the permis-
sible ways to reallocate and reuse resources in
building another sensor. Intuitively, it captures
the notion of repositioning resources such as the
active and passive components of sensor systems
(e.g., infra-red emitters and detectors). Geomet-
ric codesignatiom constraints further restrict the
range of admissible permutations. Le., we do
not allow arbitrary relocation; instead, we can
constrain resources to be "installed at the same
location", such as on a robot, or at a goal. Out-
put communication formalizes our notion of "a
little bit of rewiring." When resources are per-
muted, we often find they must be reconnected
using "wires", or data-paths. If we separate pre-
viously colocated resources, we will often need to
add a communication mechanism to connect the
now spatially separate components. Like CT re-
ductions, A ?i B defines an "efficient" transfor-
mation on sensors that takes B to A. However,
we can give a generic algorithm for synthesiz-
ing our reductions (whereas no such algorithm
can exist for CT.)3 Whether such reductions are
2<i is also called < in Don, Don4].
3For example: no algorithm exists to decide the exis-
widely useful or whether there exist better reduc-
tions is open; however we try to demonstrate the
potential usefulness both through examples and
through general claims on algorithmic tractabil-
ity. We also give a "hierarchy" of reductions,
ordered on power, so that the strength of our
transformations can be quantified.
Our ideas have the following applications:
1.
(Co?pamson).			Given			two
sensori-computational systems A and B, we
can ask "which is more powerful?" (in the
sense of A ?i B, above).
2. (Transformation). We can also ask "Can B
be transformed into A?"
3.
4.
(Des??n). Suppose we are given a specifi-
cation for A, and a "bag of parts" for B.
The bag of parts consists of boxes and wires.
Each box is a sensori-computational compo-
nent ("black box") that computes a function
of (i) its spatial location or pose and (ii) its
inputs. The "wires" have different band-
widths, and they can hook the boxes to-
gether. Then, our algorithms decide, can we
"embed" the components of B so as to sat-
isfy the spec of A? The algorithms also give
the "embedding" (that is, how the boxes
should be placed in the world, and how they
should be wired together). Hence, we can
ask, can the spec of A be implemented us-
ing the bag of parts B?
(Universal Reduct?on). Consider applica-
tion 3, above. Suppose that in addition to
the spec for A, we are given an encoding of
A as a bag of parts, and an "embedding"
to implement that spec. Suppose further
that A ?i B. Since this reduction is rel-
ativized both to A and to B, it measures
the "power" of the components of A rela-
tive to the components in B. By universally
quantifying over the configuration of A, we
can ask, "can the components of B always
do the job of the components of A?"
tence of a linear-space (or log-space, polynomial time, Turing
computable, etc.) reduction between two CT problems.
More specifically: Let o? be a "configura-
tion" of sensorimotor system A. Thus ct en-
codes the spatial embedding of A as well as
its wiring connectivity. Similarly, let (3 be
a configuration of system B. Let A(a) and
B((3) denote systems A and B "installed"
at these configurations. The gist of appli-
cation 4 is that, we can decide whether or
not
1.2 Outline
(V?, il(3): A(cr) ?i B((3).
We discuss questions (a) --H (f) from the Ab-
stract for an experiment with communicating
robots. We consider the task of coordinated
manipulation of large objects (particularly, ma-
nipulation of a large box using a pair of com-
municating mobile robots). We foreground the
task of pushing an object, using two communi-
cating robots who need to infer the position of
the first moment of the friction distribution with
respect to their lines of pushing (see Figure 2a).
In [Don4], we asked whether explicit communi-
cation could be removed from this protocol (by
explicit" we mean local communication, such as
IR, or global communication, such as RF). In this
paper we give a protocol with no explicit com-
munication, and we analyze and compare the the
protocols using the tools introduced in [Don4].
We believe our methods generalize to other ma-
nipulation tasks and to larger teams of robots,
but work is still underway; for example, in [DJR],
we considered the task of coordinated manipula-
tion of large objects (particularly, rotations, or
more accurately, %eornenlat?ons" of a large box
using a team of communicating mobile robots).
There, we examined an offline strategy, in which
the robots have a geometric model of the object,
and an online strategy, in which they do not. In
sec. 7, we describe these strategies and sketch a
general methodology for developing distributed
manipulation protocols.
(a) Th Ia a
Figure 1: The box is being rotated by three co-
operating autonomous agents. (a) The motion
of the box viewed in world coordinates. (b) The
relative motion of the pushing robots, viewed in
a system of coordinates fixed on the box. The ar-
rows illustrate the direction of the applied forces.
2 Pushing with Two Communicating
Mobile Robots
To introduce our ideas we consider a task in-
volving two autonomous mobile robots. The two
robots must cooperate to push a box. Now, many
issues related to information invariants can be in-
vestigated in the setting of a single agent. How-
ever, one of our ideas is that, by spatially dis-
tributing resources (a) --H (f) among collaborating
agents, the information characteristics of a task
are made explicit. That is, by asking, Ilow cam
th%s task be performed b? a team of robots? one
may highlight the information structure.
Here is a preview of how we will proceed. The
goal of the pushing task is to move an object
along a straight line (called the pushing direc-
tion) with two agents. We first describe a strat-
egy for this task designed to be executed by a
manipulator with two rigidly connected fingers
and force feedback. We then propose variants of
this algorithm that are suitable for execution by
autonomous mobile robots. Finally, we compare
these strategies with respect to questions (a) --H
(f), posed in the Abstract.
a)
hi???
B
`a
R
Figure 2: (a) the "two-finger" pushing task vs.
(b) the two robot pushing task. The goal is to
push the block B in a straight line.
2.1 Three Pushing Protocols
Consider the task whose goal is to push a
box B in a straight line. Figure 2a depicts one
robot (the reader should picture a robot manipu-
lator, or gripper) executing this task. The robot
consists of two rigidly connected fingers L and
R; for example, they could be the fingers of a
parallel-jaw gripper. One complication involves
the micro-mechanical variations in the slip of the
box on the table [Mas]. This phenomenon is very
hard to model, and hence it is difficult to pre-
dict 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 push-
ing. However, with a two-fingered push, the box
will translate in a straight line so long as the
COF lies between the fingers. An advantage of
the two-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 2a), instead of on a line. If
the COF moves outside C, then the fingers can
move sideways to "capture" it again. We have
implemented the control loop described as Pro-
tocol 0 on our PUMA (see fig. 3). The basic idea
is to sense the reaction torque r about the point
o in Figure 2a. If T = 0, push forward in direc-
tion y. If T ? 0 move the fingers in x; else move
the fingers in --Hx.
Repeat : measure(?)
case			= 0) =
push(p)
<0) =
move(i?)
(T > 0) ?
move(L)
Figure 3: Protocol 0 (for a two-fingered gripper).
Figure 4: The mobile robot TOMMY. Note
(mounted top to bottom on the cylindrical en-
closure) the ring of sonars, the IR Modems, and
the bump-sensors. LILY is very similar.
From the mechanics perspective it might ap-
pear we are done. However, it is difficult to over-
state how critically Protocol 0 above relies on
global communication and control. Now, con-
sider the analogous pushing task in Figure 2b.
Each finger is replaced by an autonomous mobile
robot such as those described in [RD]. The robots
we have in mind are the Cornell mobile robots
(see Figure 4), but the details of their construc-
tion are not important. The robots can move
about by controlling motors attached to wheels.
The robots are autonomous and equipped with a
ring of 12 simple Polaroid ultrasonic sonar sen-
sors. Each robot has onboard processors for
control and programming. The description in
[RD] is augmented as follows. (This description
characterizes the robots in our lab). We equip
each robot with 12 infra-red modems/sensors, ar-
rayed in a ring about the robot body. Each mo-
dein consists of an emitter-detector pair. When
transmitting or receiving, each modem essen-
tially functions like the remote control for home
appliances (e.g., televisions). In addition, each
robot has a ring of one-bit contact ("bump") sen-
sors.
oo+ COF
L
r2
Figure 5: Protocol I
We assume the following: (1) robots can sense
the relative orientation of objects with which
they are in contact [JR]; (2) robots know that
they are on the same fiat face of the object; (3)
both robots know the direction of pushing, p;
and (4) robots can synchronize their velocities.4
In addition, (5) by examining the servo-loop
in [RD], it is clear that we can compute a mea-
sure of applied force by observing the applied
power, the position and velocity of the robot,
and the contact sensors.
The pushing strategy described as Protocol 0
can be approximated by observing the following
4For the pushing task, it suffices to assume that the robots
have identical control systems and can command the same
speeds. More generally, velocity synchronization requires that
the robots begin and end pushing at the same time; this can be
necessary for more complicated manipulation tasks. A proto-
col for velocity synchronization is not hard to synthesize using
our methods; see sec. 7.i.
0
Left Robot
Repeat:
measure(fi)
case
Communication			Right Robot
Repeat:
measure(f2)
[m(fi)
T r1 x fi --H r2 ? f2
LR (sign(?))
case
= 0) =
push(p)			push(p)
? 0) ?			(r> 0) =
if(break?)			if(break?)
guarded-move(p)			guarded-move(p)
else ?			else ?
(T > 0) =			(T < 0) =
move(L)			move(R)
Figure 6: Protocol I
Figure 7: Protocol I(QS). The normal to the box
face is denoted by n. The x axis is parallel to the
direction of pushing p. The lines of pushing are
distance 2r apart (perpendicular distance). 0 is
the angle between n and p.
(see Figs. 5, 6). Each robot can measure its ap-
plied force (fi or f2) and communicate this data
to the other. This allows the robots to compute
the net torque T about a point in between the two
robots, and from the sign of this quantity, to in-
fer the location of the first moment of the friction
distribution of the box. If the first moment of
the friction distribution is between the two lines
of pushing, each robot continues pushing alone
the line p. If there is a positive 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 "re-
capture" 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?) re-
turns TRUE) it executes a guarded-move (motion
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 5, 6).
A variant of this protocol can be derived for a
quasi-static (QS) system. Here, relative displace-
ments along the line of pushing p are measured
instead of forces. Figure 7 shows a configuration
where the two robots originate at positions xi(0)
and v2(0), respectively. Their locations at time
t are j"1(t) and x2(I). In this protocol (Figure 8),
the initial locations of the robots are communi-
cated to determine their offset ?o. ?o "specifies"
(or better, parameternzes) the pushing task: this
offset determines the pushing direction p rela-
tive to the initial orientation of the box face.
The robots exchange location information suc-
Left Robot			Communication			Right Robot
measure(xi (0))			measure(x2 (0))
Repeat:
measure(x1 (t))
case
[M (xi(t))
M(s)
= x2(O) --H xi(O)
Repeat:
measure(x2 (t))
= x2(t) --H xi(t)
s = sign(V --H
case
= 0) =
push(p)			push(p)
= --H1) =			= --H1) =
move(R)			move(R)
= 1) =			(s = 1) =
move(L)			inove(L)
Figure 8: Protocol I (Quasi-Static). The case for breaking contact is not shown; it can he handled as in fig. 6.
cessively at each loop iteration; this information
is used to infer the direction of motion of the box.
We call this Protocol I(QS) (see Figures 7, 8).
0;);
R
Figure 9: Protocol II.
We now derive a different version of Protocol
I(QS) by observing that the information needed
to determine the motion of the box (?.e. ?0 and
?) is related to the angle 0 between the nonnal to
the face of the box n and the direction of pushing
p as follows: 2r tan 0o = ?o and 2r tan 0 = ? (see
Figures 7, 9, 10). 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 ?, without knowing r.
Specifically, the robots measure 0o (the initial
angle between n and p; see [JR]), and compare
this value to the angle 0(t) measured at time t
in order to infer the direction of motion of the
box. A negative change in the value of this angle
implies a clockwise rotation of the box. A large
positive change implies a counterclockwise rota-
tion. The robots adjust their pushing location on
the face of the box accordingly. This is an exam-
ple of how the robots can use the task dynamics
instead of explicit communication to determine
their next actions. We call this pushing strategy
Protocol II (Figure 10).
2.2 Comparing the Protocols
Now, we ask, how do protocols I, I(QS), and
II compare to one another with respect to the
questions (a) --H (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 coordination is accomplished differently
in the three protocols. In Protocol I and Proto-
col I(QS) the robots synchronize by exchanging
their sensed values. Robots executing Protocol I
1 fl
Left Robot			Right Robot
0o 0(0)			0o 0(0)
Repeat :			Repeat
case			case
(break?) ?			(break?) ?
guarded-move(p)			guarded-move(p)
(0(t) 0o) ?			(0(t) 0o) ?
push(p)			push(p)
(0(t)  0o) ?			(0(t)  0o) ?
move(L)
(0(t) 0o) ?			(0(t) ? 0o) ?
move(R)
Figure 10: Protocol II. This protocol is almost uniform," and can be made uniform by changing the I lines (*) to Mov?(L) and
(**) to MovE(R). Note that "uniform" does not quite imply SIMD, since the protocols run asynchronously.
require communicating log fi bits to transmit the
value of force fi, and 2 bits to transmit the sign
of the torque T. Robots executing Protocol I(QS)
require log xi bits to transmit the value of the
distance xi, and 2 bits to transmit the sign of 5.
In Protocol II there is no explicit 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
direction, In other words, the robots infer the
motion of the object by decoding changes in the
task mechanics. Thus, protocols I and I(QS) rely
on direct communication, while 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 reg-
ister to record the value ?o. Protocol II requires
a register to record the value 0o.
We can get a deeper understanding of the rela-
tionship between these protocols by attempting
to "transform" or "reduce" one to the other. We
do so below.
3 Reductions and Transformations
We now formalize our model of sensori-
computational systems by viewing them as "cir-
cuits." The theory in secs. 3-6 is extracted
from [Don4], but the particular examples and
application (especially, claim 4.1) are new. We
model these circuits as graphs. Vertices cor-
respond to different sensori-computational com-
ponents of the system (what we will call "re-
sources" below). Edges correspond to "data
paths" through which information passes. Differ-
ent immersions of these graphs correspond to dif-
ferent spatial allocation of the "resources." Our
idea involves asking: What information is added
(or lost) in a sensor system when we change
its ?mmers?on? and What information is pre-
served under all immersions? We also define
an operator + as a way to "combine" sensori-
computational systems. The operation + is like
taking the union of two graphs. Below, we
use the term "sensor system" to mean "sensorn-
computational system" 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, to-
gether with a labelling function that assigns a la-
bel to each vertex and edge. Where there is no
ambiguity, we denote the labelling function by .
Definition 3.2 A sensor system 8 is repre-
sented by a labelled graph (V,E). Each vertex is
labelled with a component. Each edge is labelled
with a connection.
See figs. 11-12 for illustrations for the
circuits that is, the sensor systems for proto-
cols I (QS) and II. We will use the terms protocol
iRi?o?? --- ,ss
0
o+			0
L R
Figure 11: Sensor system P.I(QS). This is a circuit for Pro-
tocol I (QS). This circuit shows one possible implementation
of the protocol. Figs. 11-12 do not show how to handle lost
of contact (i.e., the (break?) case), but this circuitry is easily
added, and is the same for both P.I(QS) and P.11.
to refer to the computer programs in figs. 8-10,
and circuit for the sensor systems in figs. 11-12.
It is clear that each circuit implements its pro-
tocol. Now, in Protocol I(QS) (fig. 8), there are
three communications operations. The first two
use the same datapath; they simply re-
fer to the first use, and to subsequent use, of
the same resource. In our circuits, we now re-
strict the components to be the resources such
as those described in the figures; however, our
definitions could, we feel, be generalized to other
resources. In the figures, the components cor-
respond to boxes: ODOM is an odometer, the
"signal"5 coming out of this box is the odom-
etry reading. The box L performs subtraction
the boxes xi(O) and ?? are registers, and they
implement internal state. The part of the cir-
cuit labelled case interfaces to the control part
5We use "signal" as a metaphor; our circuits are
strictly digital. Either message or stream would be better,
but both have distracting religious connotations.
to
`s
L
Figure 12: Sensor system P.11. This is a circuit for Proto-
col II.
of the circuits, which is the same for both proto-
cols. For technical reasons, 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.
One interesting resource is 0(t) in fig. 12
we call this box a 0-source it produces a sig-
nal indicating relative orientation. [JR] describe
in detail how to implement a bounded-error 0-
source. Here is the basic idea. A 0-source is an
abstraction of relative normal sensing. It allows
the normal of the box to be treated as an ex-
ternal "register" that both robots may read and
write. We could implement an (approximate) 0-
source as follows. The robot has a ring of 1-bit
bump sensors. These are used to implement rela-
tive normal sensing [JR]. We specify the pushing
direction p, by specifying 0o (see fig. 10), the di-
rection of p relative to the box normal n(O) at
time 0. More specifically: at the beginning of
the task, each robot does a guarded move along
p until contact with the box. It then aligns nor-
mal to the box, using the bounded-error algo-
rithm of [JR]. Finally, the robot turns by angle
0o using pure position control.
INIT is one bit of state, and RUN--H--H INIT. The
small crossed circles (-.--) that these bits run into
are gates; the ? input must be 1 for the H signal
to pass. Thus in robot L in fig. 11, if INIT 1,
then the odometer writes into the register xi(O).
When INIT 0, then the L- component is fed
1 `1
the odometry input. We assume that numbers
are represented as signed integers. The SGN box
just selects out the sign bit. We omit the logic
to toggle INIT once the register ri(0) is written.
Whereas L requires one bit of state INIT0, R re-
quires two, due to the asymmetry of the protocol
P.I(QS). These are denoted INIT1 and INIT2.
Connections are like data-paths in that they
carry information; a connection's label repre-
sents the information that will be sent along that
path. Connections carry data between compo-
nents. We adopt the convention that two com-
ponents can communicate without an (explicit)
connection when they are spatially colocated.
Now, in figs. 11- 12, many of the data paths are
internal, i.e., L L or 1? H. The most inter-
esting datapaths are the external datapaths: the
L R edge (b) labelled COMM(Axi), and the
L H R edge (b') labelled COMM(S). (b) has band-
width log [Axi bits, and (b') has bandwidth 2
bits.
Observe fig. 12. Here, there is a 0-source that
is external to both robots. There are two in-
teresting external data paths from the 0-source,
one to L marked COMM(.), and one marked (b) to
R. Both these datapaths have bandwidth log 0(t)
bits.
3.2 Transformations as Reductions
In sec. 4, we give a proof (claim 4.1) and an
equation (3) relating the circuits P.I(QS) and
P.11. Intuitively, eq. (3) indicates that, opera-
tionally speaking, one could transform a system
which executes Protocol I(QS) into one which
executes Protocol II by removing the odometry
from both robots, and by adding a 0--Hsource,
which is a component that senses the orientation
of the manipulated object. In describing Pro-
tocol II, we demonstrated that one implementa-
tion of such a sensor involves using some retained
state (0o), and a relative orientation sensor such
as the bumper system described in [JR]. In fact,
equation (3) is a precise statement of this en-
gineering fact. Below, we carefully define the
operators + and --H, and formalize the notions
of simulation and eficient reduction, as well as
permutation, etc.
Our reduction involves two concepts. The first
is permutation, and it involves redistributing re-
sources in a sensor system, without consuming
new resources. Surprisingly, a redistribution of
resources can add information to the system. In
order for permutation to add information, it is
necessary for the sensor system to be spatially
distributed (as, for example, our circuits are).
When permutation gains information, it may be
viewed as a way of arranging resources in a con-
figuration of lower entropy.
The second concept is communication. It mea-
sures resource (b) (from the abstract). We con-
sider adding communication primitives of the
form COMM(L R, info), which indicates that L
sends message info to R. Examples of this prim-
itive are COMM(Ax1) and COMM(s) in fig. 11.
Like permutation, communication only makes
sense in a spatially distributed sensor system.
That is, because spatially colocated components
can communicate "for free" in our model, only
"external" datapaths add information complex-
ity to the system. In effect, to transform system
Protocol O into Protocol I(QS) (see figs. 3, 8),
we view it as a system composed of autonomous
collaborating agents L and R, each of which has
certain resources. The COMM(.) primitive above
we view as shared between L and R. We mea-
sure communication by counting the number of
agents and the bits required to transmit info.
This is the only kind of external communication
we will consider here (i.e., L R or L R); we will
abbreviate it by COMM(info) when the direction
is clear.
We can be sure of getting the semantics of
COMM(.) correct by treating it as a sensor sys-
tem in its own right (albeit, a small one).
Now, COMM(0) defines the graph with vertices
fu1,u0? and a single edge e (ui,u0) with
b. The "head" vertex Uo of the edge
e = (ui,u0), is defined to be the output vertex
of the sensor system COMM(b). The argument
(parameter) b to COMM(b) determines the band-
width of e. Thus, for example, COMM(b) spec-
ifies a graph with one edge e whose label is b.
This specifies that the edge is a datapath that
can carry information b if b requires k = log b
bits to encode then k is the bandwidth of e. Our
model of communication is rather abstract. Ex-
ternal communication is probably not possible
without buffering by either the sender or the re-
ceiver. coMM(.) should include this buffer to be
more realistic about modeling internal state.
We now formalize the ideas above. Consider
a sensor system with vertices V. For each ver-
tex v in V, we assume there is a configuration
space G. A point in this space C represents the
configuration of the component.
Definition 3.3 A situated (or immersed) sen-
sor system S is a sensor system 8 =
together with an immersion 4) : V 0 of the
vertices. If v E V, them we call 4)(v) the config-
uration ofthe vertex v. When there is no ambi-
guity, we also call 4)(v) the configuration of the
component (v)
A situated sensor system is essentially an im-
mersed graph. If the map 4) in def. 3.3 is injec-
tive, then we call 4) an embedding. Immersions
need not be injective. Moreover, in order to colo-
cate vertices, it is necessary for immersions to be
non-injective.
In def. 3.3, the immersion 4) may be a partial
(as opposed to total) function, indicating that we
do not specify the spatial configuration of those
components whose vertices are outside the do-
main of the immersion. We denote the domain
of a (partial) immersion 4) : V 0 by 4)-'G.
We denote its image by im 4).
We can now define what it means for two sys-
tems to be equivalent:
Definition 3.4 Given two sensor systems S
and Q, we say Q simulates S if the output of
Q is the same as the output of 5. In this case we
write 5 --H Q. More generally, suppose we write
(1)
for two situated sensor systems. Eq. (1) is clearly
well-defined when 4) and 4) are total. Now, sup-
pose that 4) and 4) are partial, leaving unspecified
the configurations of components `(v) of 8 and
?(u) of IA. Then eq. (1) is taken to mean that
(IA, 4)) simulates (8, 4)) for any configuration of
v and u.
For def. 3.4, in the case where (say) 4) is par-
tial, we operationalize eq. (1) by rewriting it as
a statement about all extensions 4) of 4). That is,
we define ex 4) to be the set of all extensions of 4).
Then, we write: "V4) c ex4), eq. (1) holds (with
bars placed over the immersions)." We treat 4)
similarly, with an inner universal quantifier, al-
though codesignation constraints (sec. 3.5) allow
us to make the choice of extension 4) of 4) de-
pend on the extension 4) that is bound by the
outer quantifier. For example, def. 3.4 becomes,
"for all configurations x E 0 of v, for all config-
urations y E Ds(x) of u, eq. (1) holds." Here
Ds(x) is a set in 0 that varies with x; the func-
tion D8(.) models the codesignation constraints.
Def. 3.4 can be generalized to any number of "un-
bound" vertices; see eq. (8) and [Don4].
3.3 Permutation
We may consider two orthogonal kinds of per-
mutation. In both models, the vertex and edge
labels (v) and (e) never change. The first
model is called verter permutation, and is given
in def. 3.5. In this model, the vertices can move,
and they drag the components and wires with
them. That is, the vertices move (under permu-
tation), and as they move, the edges follow.
Vertex permutation of a situated sensor system
corresponds to the choice of a different immer-
sion with the same domain:
Definition 3.5 Let ? = (8, 4)) be a situated sen-
sor system. A permutation ?? of ? is a situated
sensor system (8, 4)*) such that the domain 4)--Hlo
of 4) and the domain 4)*--H10 of 4)* are the same.
For technical reasons, we also permit a permu-
tation to change which vertex has the "output"
label. Note that the definition of permutation
(def. 3.5) also makes sense for partial immer-
sions. However, see the appendix for a discussion
of the semantics of permutation for unsituated
sensor systems.
We can also consider an alternate model,
called edge permutation, where the edge con-
nectivity changes. An edge permutation can
be modeled as follows. Consider a graph with
I A
vertices V and edges E. Start with any bijec-
tion a : V2 V2 We call a an edge per-
mutation, since it induces the restriction map
E a(E) on the edge set E. An edge
permutation says nothing about the immersion
of a graph.
We can also compose the models. We define
a graph permutation to be a vertex permutation
followed by an edge permutation. In a graph per-
mutation, the vertices and the edges move inde-
pendently. That is, vertices may move, but in
addition, the edge connectivity may change. To
illustrate the different models, consider a sensor
system ? with three vertices f vi, i'2, V3 ? with
labels (v?) Bj (i = 1,2,3). tA has one edge
e = (vi,v2) of bandwidth k that connects B1 to
B2. So, the Bj are the components of the system,
and e is a datapath. A vertex permutation tt?
of U would move the vertices (and therefore the
components) spatially, but in lt?, e would still
connect v1 and v2, (and therefore, B1 and B2).
An edge permutation a of U would change the
edge connectivity. So, for example, an edge per-
mutation a(U) could be a graph with one edge
a(e) = (v2, v?), connecting v2 to V3 (and hence
B2 to B3). But in a(U) no edge would connect
vi and v2. Finally, consider a graph permutation
t4* of U. Suppose U* = a(U*), that is, l? is
the vertex permutation lt? followed by the edge
permutation a above. ?? has the same edge con-
nectivity as a(t?). However, in lt*, the vertices
are immersed as in U*.
Let (?, ?) be a situated sensor system. A
graph permutation of It is given by It? = (It, ?)
where ?? = (?*, a), ?? is a vertex permuta-
tion, and a is an edge permutation. In prac-
tice, we wish to impose some restrictions on edge
and graph permutation. For example, suppose
we have a sensor system It containing two co-
operating and communicating mobile robots L
and R. The sensori-computational systems for
L and R are modeled as circuits. The datap-
aths in the system, in addition to bandwidth,
have a t?pe, of the form SOURCE?DESTINATION,
where both SOURCE and DESTINATION E ? L, 1?
(Maintaining exactly two physical locations can
be done using simple codesignation constraints).
When permuting the edges of It to obtain It*, it
makes sense to permute only edges of the same
type. More generally, we may segregate the edge
types into two classes, internal edges L			L and
R R, and external edges L			R and L			R. In
constructing It*, we may reallocate an internal
edge (of sufficient bandwidth) to connect any
two components where SOURCE=DESTINATION.
External edges (of sufficient bandwidth) can be
(re)used when SOURCE#DESTINATION. Hence, in
class edge permutation, we permute edges within
a type (or class). In this paper we will restrict
our edge permutations to this kind of class edge
permutation. Class edge permutation leaves un-
changed the complexity bounds and the lemmas
of [Don4].
To summarize: vertex permutation preserves
the graph topology whereas edge permutation
can move the edges around. Edge permutation
permits arbitrary rewiring (using existing edges).
It cannot add new edges, nor can it change their
bandwidth. In sec. 6, we discuss further the con-
sequences of allowing different kinds of permu-
tation on our model. There we show that graph
permutation can be permitted at no additional
cost" and without changing the power of our
systems very much.
3.4 Combination
Definition 3.6 Consider two graphs g = (V, E)
and g' = (V',E'). We define the combination
g + g' of g and G' as follows:
g + g' = (V u v', E u E').
We may define + on sensor systems (def. 3.2)
by lifting the definition for graphs. We may de-
fine + on two immersed graphs whenever the im-
mersions are compatible. An immersion b of ?
and an immersion ? of g' are said to be compat-
ible when the two immersions agree on the in-
tersection V n v' (for total immersions) or more
generally, on b?'CniP--H'C (for partial functions).
Similarly:
Definition 3.7 Consider two graphs g (V, E)
and g' = (V',E'), where g' is 5 subgraph of?.
We define the difference g --H g' of g and g' as
follows:
1 ?
?+g'= (V--Hv',E--HE').
Def. 3.7 may also be lifted to (partially) im-
mersed graphs, and hence to situated sensor sys-
tems.
3.5			Reductions			Calibration
Codesignation
and
As we observed in [Donj, calibration exploits
external state. We wish to order systems on how
much information this external state (from cali-
bration) yields, to obtain def. 3.8, below. Cali-
bration complexity is defined formally in [Don4].
Here is the basic idea. Calibration complexity
measures how much information we add to a sen-
sor system when we install and calibrate it. In-
stalling 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 spatial
relation. More generally, we may have to es-
tablish a relation between a component and a
reference frame in the world. Most generally,
when we compare two sensor systems S and Q,
we typically must install and calibrate them in
some appropriate relative configuration again,
in a spatial relation. When all these relations are
(in)equalities of configuration, we say the sys-
tem is simple. When all the relations are semi-
algebraic (s.a.), we say the system is algebraically
codesignated.
Definition 3.8 We write S ? Q when
1. Q simulates S (S Q), and
2. S dominates Q in calibration complexity.
Convention: We will now drop the notation ?,
and use Q* to denote any graph permutation of
sensor system Q, as described above.
Definition 3.9 We `write S ?? Q if there exists
some (?raph) permutation Q* of sensor system
Q such that S ?
3.5.1 Relativized Information Com-
plexity
Consider a sensor system that outputs the
value z. The complexity of many sensors can
essentially be characterized using the size log z
of the output value z. Let us now ask what is the
"output" of our protocols, and, more important,
what is its ??
Suppose we suggest that the output of each
system is at most 2 bits: the system's output
chooses between three motor control states, the
actions MovE(L), MovE(R), or PUsH(p). In
this case, we note that the sensor system has in-
ternal bandwidth that is much higher (log AO or
log Ax bits). The output in some sense encodes
that information. That is, we may view the pro-
tocols as "recognizing" a "model" or a "signal" of
size O(log Ax) bits, and subsequently "hashing"
that model to one of three equivalence classes.
This argues that perhaps the intrinsic output
complexity of the protocols should be more like
log Ax bits.6
Another idea is to observe that the actuator
output p in PUsH(p) would be at a similar reso-
lution to the orientation sensing 0(t) or odometry
x? (t). This argues that the "output" of the pro-
tocol is something more like O(logp) bits (since
the MovE(L/R) decision is indeed binary).
This discussion reveals a more general issue
with sensor systems. In particular, there are
sensor systems whose complexity cannot be well-
characterized by the number of bits of output.7
For example: consider a "grandmother" sensor.
Such a sensor looks at a visual field and out-
puts one bit, returning #t if the visual field con-
tains a grandmother and #f if it doesn't. Now,
one view of the sensor interpretation problem
is that of information reduction and identifica-
tion (compare [DJ], which discusses hierarchies
of sensor information). However consider a some-
what different perspective, that views sensors as
To see that instrumenting AO and Ax require the same
number of bits, requires an argument like the decalibration"
lemmas of Horsi. For this paper, we can see this from the
relation 2?tan9(t)
7This discussion devolves to a suggestion of Sundar
Narasimban Personal communication?, for which we are very
grateful.
model matchers. So, imagine a computational
process that calculates the probability P(C/V)
of G (grandmother) given V (the visual field)
i.e., the probability that 0 is in the data (the vi-
sual field itself). The sensor in the former case is
something specific only to detecting grandmoth-
ers, while the latter prefers to see a grandmother
as the model that best explains the current data.
The latter is a process that computes over model
classes. For example, this sensor might output
TIGER (when given a fuzzy picture that is best
explained as a tiger).
In short, one may view a sensor system as stor-
ing prior distributions. These distributions bias
it toward a fixed set of model classes. In prin-
ciple, the stored distributions may be viewed ei-
ther as calibration or internal state. To quantify
the absolute information complexity of a sensor
system, we need to measure the information com-
plexity of model classes stored in the prior distri-
bution of the sensor. This could be very difficult.
Instead, we propose to measure a quantity
called the maximum bandwidth of a sensor sys-
tem. Intuitively, this quantity is the maximum
over all internal and external edge bandwidths
(data-paths). That is:
Definition 3.10 We define the internal (resp.,
external) bandwidth of a sensor system 8 to be
the greatest bandwidth of any internal (resp., ex-
ternal) edge in 8. The raw output size of 8 is
the size of the value it outputs. We define the
maximum bandwidth of 8 to be the greater of
the internal bandwidth, external bandwidth, and
the raw output size of 8.
The maximum bandwidth is an upper bound
on the relative intrinsic output complexity (rela-
tivized to the information complexity of the com-
ponents (secs. 3 and 3.5.1)). We explore this no-
tion briefly below.
Maximum bandwidth is a measure of inter-
nal information complexity. The bandwidth is a
measure of information complexity only relative
to the sensori-computational components of the
system. For example, imagine that we had a sen-
sor system with a single component that outputs
one bit when it recognizes a complicated model
(say, a grandmother). The only data path in
the system has bandwidth one bit, because the
single component in the system is very power-
ful. So, even though the maximum bandwidth is
small, the absolute information complexity may
be large.
So, some sensors are black boxes. We call a
sensor system a black box if it is encoded as a
single component. The only measure of band-
width we have for a black box is its raw output
size. For example, the odometry system ODOM
and the 0-source system 0 in sec. 4 are black
boxes.
More generally, we call a sensor system mono-
tonic if its internal bandwidth is bounded above
by its raw output size. So, black box sensors
are trivially monotonic. All the sensor systems
in [Don4] are monotonic. If we believe that
the output size of our protocols is O(logp) bits,
then our sensor systems are also monotonic. If
we believe the output size is 2 bits, they are
not. In any case, the bandwidths of Protocols
I(QS) and II are log Ax and log AO (resp.) Since
2r tan 0(t) ?(t), we argue that these two sys-
tems have the same maximum bandwidth.
3.5.2 Reductions using Communica-
tion
In light of this discussion, we now define the
reduction ?i from [Don], using relativized infor-
mation complexity. Recall the construction of
COMM(.) as a sensor system (sec. 3.2). First, let
5 be a monotonic sensor system with output z.
In this case, we define COMM(S) to be COMM(z).
More generally, for (possibly) non-monotonic
sensors, we will let COMM(S) be COMM(2k)
where k is the relative intrinsic output complex-
ity of 5. Measuring this (k) in general is diffi-
cult, but we will treat the maximum bandwidth
(def. 3.10) of 5 as an upper bound on
Definition 3.11 Consider two sensor systems
5 and Q. We say Q is efficiently reducible to
5 if
(2)
5 <* Q + COMM(S).
In this case we write8 5 ?i Q.
s<? is also called < in [Don, Don4].
1)			1 ?
Now, permutation (the * operation) and corn-
bination (the + operation) "commute" for com-
patible partial immersions. This is formalized
as a "distributive" property in [Don4). So, for
example, for any sensor system 8, we have en-
sured that 8* + COMM(.) (8 + COMM(.))*,
i.e., we can do the permutation and combina-
tion in any order. Second we have ensured that
the combination operation + is commutative and
associative. Third, in the reduction ?i we have
given the single edge e in COMM(.) enough band-
width so that it still works when we switch it
(e) around using permutation. llence, the sen-
sor system (Q+COMM(S))* from eq. (2) may be
implemented as the sensor system Q permuted in
an arbitrary way, plus one extra data path whose
bandwidth is that of the largest flow in 5.
Observe that even when <? is transitive, it ap-
pears that ?i is not. To see this, suppose that
A ?i B and B ?i C. Then it appears that
to reduce B to A we require one "extra wire"
(namely, COMM(A)), and that to reduce C to B
we could require (another) extra wire COMM(B),
and therefore, in the worst case, to reduce C to
A we could require two extra wires. That is, it
could be that C cannot reduce to A with fewer
than two extra wires. We have yet to find a non-
artificial example of this lower bound but it ap-
pears to indicate that <i is not transitive (even
for simple sensor systems (sec. 3.5)).
Let us summarize. The reduction ?i
(def. 3.11) is a "i-wire" reduction. It does
not appear to be transitive. The reduction <?
(def. 3.9) is a "O-w?re" reduction. It is transi-
tive for simple sensor systems [Don4]. We could
analogously define a 2-wire, or more generally,
any k-w?re reduction ?k by modifying eq. (2) in
def. 3.11 to
5 ?? Q + k COMM(S), (2t)
k times
where k COMM(S) denotes coMM(S) + + coMM(s).
Since (?*) = (?o), this suggests a hierarchy of
reductions, indexed by k. The k-wire reductions
? ?i ?iEN form a graded relation. Even though we
believe that <i is not transitive (in the elemen-
tary sense), the hierarchy has graded transitivity
on simple sensor systems [Don4]. This means
that for any simple sensor systems 5, Q, and U,
if 5 ?? Q and Q <?j U, then 5 <i+j U. This
follows from a lemma that the 0-wire reduction
ro (called ?? in def. 3.9) is elementary transitive
for simple sensor systems.
Consider the hierarchy of k-wire reductions
?% Yi?N We say such a hierarchy collapses if
it is isomorphic to an elementary relation. In
particular, the hierarchy of k-wire reductions
(k > 0) collapses if ?i is elementary transi-
tive [Don4]
4 Comparing Protocols Using Reduc-
tions
We now apply the ideas above to compare
our protocols, P.I(QS) and P.11 (the circuits in
figs. 8--H10). First, we define two black boxes
(see sec. 3.5.1). Define the odometry sensor sys-
tem ODOM to have one vertex, whose label is
ODOM. It has a single component, an odome-
ter. Similarly, define the 0-source sensor system
O to have a one vertex and a single component
8(t), which is a 0-source. These systems can be
installed (or better, spliced) "into" our circuits.
Each black box comes with (simple) codesigna-
tion constraints. Vertex ODOM must be installed
on a robot (either L or I?). So, its vertex codesig-
nates with L or R. Vertex 8(t) must be installed
at a location not on a robot. So, its vertex cannot
codesignate with L or R. We now show:
Claim 4.1 Let P.11, P.I(QS), ODOM, and 0 be
the sensor systems defined as above. Then,
P.11 ?k P.I(QS) --H 2ODOM + 0 (3)
for k = 1. i?oreover, eq. (3) does not hold for
k =0.
Proof: Consider the sensor system IA obtained by
removing both odometers from circuit P.I(QS),
and adding a 0-source:
IA = P.I(QS) --H 2ODOM + 0.			(4)
I 0
Now, consider permutations of U, and recall
def. 3.9. We first ask whether U can be reduced
to P.11 using <?. That is Pil ?? IA? First,
we note that we can move around the registers
and fl's from IA to situate all the components
of P.11. We also have some leftover components
(and wires). P.11 requires two sign boxes; how-
ever, 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 hard-
ware from IA to build a small circuit to simu-
late SGN. We need to argue that a register big
enough to hold xi(0) will also hold 0o; this fol-
lows from 2r tan 0(t) lS(t), or from "decalibra-
tion" [Hors]. Next, we see that we can permute
the internal edges of IA to wire up the compo-
nents of P.11 in situ internally. What about ex-
ternally?
Permuting the external wiring almost works,
but not quite. IA has two external data paths,
(b1) and (b), with bandwidth 2 bits and log Ax1
bits (resp) (fig. 11). Now, since we only al-
low class edge permutation (as in sec. 3.3), we
must permute external edges to external edges
and internal edges to internal edges. Therefore,
in fig. 12, the edge (b) from IA will suffice as a
datapath from 0(t) to R, since it has adequate
bandwidth. However, the datapath (bt) from IA
does not have adequate bandwidth to carry in-
formation 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 ar-
gument to coMM(.)? This data path must have
bandwidth of at least the relative intrinsic out-
put complexity of P.11, or log A0 bits. Hence
we may parameterize this new edge by writing
coMM(P.II), following sec. 3.5.1. Hence, we see
that
P.11 < (IA + coMM(P.II))* (5)
Therefore by def. 3.9,
P.11 ?? IA + coMM(P.II),			(6)
so using def. 3.11, we have P.11 ?i IA. Hence we
conclude
which implies eq. (3) as desired. E
This formalizes our intuition that, by remov-
ing odometry but adding relative normal sensing,
we can accomplish the pushing task without ex-
plicit communication. More precisely, we show
how to build one circuit P.11 "efficiently" out of
the other (IA). To transform P.I(QS) into P.11,
the operators + and --H quantify what resources
we add and delete. Relative information com-
plexity allows us to measure the effective commu-
nication "through the world." The permutation
quantifies the redistribution of resources.
5 Computing Reductions
Claim 4.1 is a proof done "by hand." That is,
we can in principle determine that eq. (3) holds
(for k > 0) by showing--H"by hand" the exis-
tence of a suitable permutation. It is somewhat
surprising that we can in fact automate this pro-
cess: [Don4] gives algorithms for deciding the re-
lation <i. More precisely, given suitable encod-
ings of two sensor systems 8 and IA, we can corn-
putationally decide whether 8 <1 IA [Don4]. The
algorithm is too complicated to describe here.
We examine a special case to give a flavor for
it; many details are omitted. The basic idea in-
volves employing the theory of real closed fields
with bounded quantification. Let us for a mo-
ment restrict our reductions to vertex permuta-
tion alone (de 3.5). First, suppose that 8 and
IA each have d vertices. Then an immersion of
8 can be encoded as a point in cd. More gen-
erally, a partial immersion ? whose domain con-
tains 1 ? d vertices can be modeled as a point in
Ct. We can "guess" a (vertex) permutation ?? of
? by existentially quantifying over the configura-
tions of the 1 vertices inside ?`s domain. Hence,
the space of permutations of ?, denoted lS(?),
is isomorphic to C1. Similarly, we can verify a
Tarski sentence for all extensions ? of ?, by uni-
versal quantification over the d--H1 vertices outside
the domain of ?. Hence, the space of all exten-
sions of ?, ex ?, is isomorphic to cd?t. We will
model (algebraic) codesignation constraints as a
(possibly constant) semi-algebraic (s a.) map-
ping ? ,` D(?) taking an immersion ? to a
P.11 ?i P.I(QS) --H 2oDoM + 0,
(7)
s.a. set D(?) c Cd. All these methods gener-
alize to graph permutation as well [Don4). Now,
Definition 5.1 A simulation function ?u for 11
a map Q? : cd H R, where R the space of
outputs. We call the value Qu(?) c R of Q? on
a sensor configuration ? to be the sensor value at
Definition 5.2 We call a sensor system U
algebraic if it is algebraically codesignated
(sec. 3.5), has an algebraic configuration space
0, and a semi-algebraic algebraic simulation
function Q?.
How do we construct and permute simulation
functions? Consider a component ?(v) associated
with vertex v of ZA. To simulate a component, we
need to know (i) its inputs and (ii) its configu-
ration. Suppose a component has r inputs and s
outputs, each of which lies in some space R. Let
O be the configuration space of the component.
A simulation function for a component ?(v) is a
map 1l? : RT x 0 Rs.
Now we connect the components together. As-
sume for a moment that all the components have
the same input-output structure as ?v above
(i.e., that r and s are fixed throughout the sys-
tem, but that the components themselves may
perform different functions). We model an edge
e between vertices v and u by its label, ?(e) =
and by a pair of integers, (i,j). logb is the band-
width of the edge , and the index i (resp. j) spec-
ifies to which output of `(v) and (resp., input of
we attach e.
Now, a simulation function for this edge e is
taken to be a function Qe : R R. We will usu-
ally restrict the edge functions to be the iden-
tify function (but they also check for bandwidth,
i.e., that the transmitted data has size no greater
than log b). A simulation function Qu for an en-
tire sensor system then, is a collection of com-
ponent simulation functions such as ll? and edge
simulation functions such as Qe The function
QIA simulates all the component simulation func-
tions in the correct configuration, and simulates
routing the data between them using the edge
simulation functions. When all these component
and edge functions are semi-algebraic (s.a.), then
the sensor simulation function lls is also s.a.9
To decide ?? means to deciding whether or not
(8, b) <? (IA, 43). Hence we must decide whether
there exists a permutation 43* of 43 such that
(8, b) --H (IA, 43*). Computationally, this requires
deciding the Tarski sentence10
(1143* fi ?(43), V? c ex?, V43*c D87?) flex43*)
QsFb)			Qu(43*)
(8)
Here, D8(.) models the codesignation con-
straints; they require the choice of extension 43*
by the inner quantifier to depend on the exten-
sion b selected by the middle quantifier. When
comparing two sensor systems 8 and IA, we typ-
ically must install and calibrate them in some
appropriate relative configuration i.e., in the
spatial relation that the codesignation constraint
D8(.) encodes.
If we can decide ?? we can decide ?i. Here is
why: to decide ?i, we must determine whether
(8,?) ?? (IA, 43) t COMM(S), (def. 3.11). Re-
call the definition of compatibility for partial
immersions (sec. 3.4). We first observe that
permutation (the * operation) and combination
(the t operation) "commute" for compatible
partial immersions [Don4]. Our arguments above
for guessing extensions and permutations can
be generalized mutatis mutandis to compute the
combination (def. 3.6) of two algebraic sensor
systems. Since COMM(S) is a constant-sized
sensor system (2 vertices, one edge) with only
a constant number of codesignation constraints
9Under this model, we can simulate trees of embedded
sensorimotor computation. It is also possible (in princi-
ple) to simulate more general graphs, but in this case the
value at the output vertex may vary over time (even for a
fixed configuration). In this case we need some notion of
time and blocking to model the (a)synchronous arrival of
data at a component. This is an interesting extension for
the future; trees currently suffice to model our examples.
Note that circuits P.I(QS) and P.11 are effectively trees,
and not graphs, even though there is data flow both from
R to L and L to R. This is because data does not not
feed back into the system.
10We must also be able to compute dominance in cali-
bration complexity (see def. 3.8). This can be done inde-
pendently, and much faster than eq. (8) can be decided;
see [Don4j.
(at most 2), we may guess how to combine it
with a permutation (?,?*) of (s,?) within the
same time bounds given below in lemma 5.3 and
eqs. (9--H10).
Let us suppose that U and 8 are algebraic.
Let us define the size d of U to be the number of
vertices in ?. Let the simulation complexity n?
be the size of the simulation functions Qu and
?s. We let ?? measure the complexity of the
codesignation constraints D8(.) in (8). Then, we
can decide eq. (8) in the time bounds below:
Lemma 5.3 (Don4) There is an algorithm for
deciding the relations ?? and ?i for aigebraic
sensor systems. It runs in time polynomial in the
simulation and codesignation complexity (n? +
n?), and sub-doubly exponential in the size of
the sensor systems. That is, if the system has
size d the time complexity is
(n? + n?)(r?d)0(l)			(9)
where r? is the dimension of the configuration
space C for a single component. El
Let us call ? small if n? and nD are only poly-
nomially large in d, i.e., (n? +n?) = d0?'?. Note
that for "small" sensor systems, eq. (9) becomes
d(r?d)0(l)?			(10)
Although complex, eq. (8) is simplified for pre-
sentation. The full Tarski sentence also contains
codesignation constraints for the outer quanti-
fiers, and is given in [Don4]. We must warn that
in sec. 5 we have examined a special case, where
8 and U are partially situated (that is, the do-
mains of ? and ? are non-empty). A powerful
generalization is given in app. A, where the sen-
sor systems can be unsituated.
6 Sensitivity of the Model
We wish to explain whether or not our the-
ory has revealed some universal truth about
sensori-computational information invariants, or
whether the results are sensitive to the particular
encodings (circuits) we chose to analyze. How
sensitive is our model? We consider two ways
to investigate this issue. First, we try chang-
ing our model of reduction (specifically, permuta-
tion) slightly, to see how that affects our results.
Second, we ask, what if the input were reincoded
slightly differently? Would our results change a
lot?
Specifically, we ask: how can we compare
vertex permutation with graph permutation
(sec. 3.5)? In particular: (i) if we permit graph
permutation instead of vertex permutation, does
it change our complexity bounds? and (ii) does
graph permutation give us a more powerful re-
duction than vertex permutation? Question (i)
gives us some insight into the sensitivity of our
complexity bounds to the model of reduction we
use. Question (ii) sheds light on whether we can
cheaply and cleverly reincode a sensor system so
as to gain a lot of "power" (information complex-
ity).
[Don4] first derives the complexity bounds in
lemma 5.3 and eq. (9--H10) for vertex permuta-
tion. Next, [Don4] asks: how expensive it is to
compute the reductions <? and ?i using graph
permutation? By extending the configuration
space cd to include all possible edge permuta-
tions, we obtain an extended configuration space
of sufficiently low dimension that we still obtain
the same complexity bounds given in lemma 5.3
and eqs. (9--H10), (so long as r and 5 are con-
stants) [Don4].
We now address question (ii): does graph per-
mutation give us a more powerful reduction? We
show:
Lemma 6.1 (The Clone Lemma) Graph per-
mutation can be simulated using vertex permuta-
tion, preceded by a linear time and linear space
transformation of the sensor system.
Proof: Given a sensor system tA we "clone" all its
vertices, and attach the edges to the clones. The
cloned system simulates the original when each
vertex is colocated with its clone. Components
remain associated with original vertices. We can
move an edge independently of the components
it originally connected, by moving its vertices
(which are clones). Any graph permutation of
It can be simulated by a vertex permutation of
the cloned system.
More specifically: Given a graph G (V, E)
with labelling function , we construct a new
graph 0' (V', E') with labelling function ".
Let the cloning function cl: V # V be an in-
jective map from V into a universe of vertices V,
such that cl(V) n v ?. We lift cl to V2 and
then restrict it to E to obtain cl: E cl(V)2 as
follows: If e = (u,v), then cl(e) (d(u),cl(v)).
Edge labels are defined as follows: `(ci(e))
Finally we define V' V u cl(V) and E' =
cl(E). We define the labelling function " on V'
as follows. ?(v) = (v) when v ? V. Otherwise,
`(v) returns the "identity" component, which
can be simulated as the identity function.11
Suppose It has d = Vi vertices and JE edges.
This transformation adds only dvertices and can
be computed in time and space O(d+ El). EJ
Let us denote by cl(It) the linear-space clone
transformation			of			It			described
in lemma 6.1. Now consider any k-wire reduc-
tion <k (sec. 3.5.2). We see that:
Corollary 6.2 Let k E N. Suppose thatfor two
sensor systems It and ?, we have V ?k It (us-
%`ng graphpermutation). Then V <?k cl(It) (us?ng
only vertex permutation). ?
7 Experiments
Using information invariants, we have pre-
sented a formal post hoc analysis of two manipu-
lation protocols for a pushing task. However, we
are also using these techniques in our laboratory
for synthesis, to develop new manipulation pro-
tocols and analyze their robustness and informa-
tion content. We believe that our techniques are
useful both for transforming protocols so as to
`1The proof can be strengthened as follows. Recall that
two components can communicate without an (explicit)
connection when they are spatially colocated. Therefore
the proof goes through even if cloned vertices have no
associated components, that is, t'(v) I for v ? V. This
version has the appeal of changing the encoding without
adding additional physical resources.
0
Figure 13: Two robots pushing a box. If their
speeds are equal, we can infer that the COF is
at Y, outside Cp. However, if the right robot is
faster, it is possible that the COF lies between
the pushing rays at X
remove assumptions and thereby increase their
generality and robustness, and also to develop
new protocols for complex manipulation tasks.
We give examples of these application below, in
secs. 7.1 and 7.2. It is our belief that our meth-
ods can give valuable insights into the informa-
tion structure of the task.
7.1 Removing Assumptions
The protocols we described depend critically
on the assumption of velocity synchronization.
For example, let vi and v2 be the speeds of the
robots. Let 0p be the region between the pushing
rays p. Consider the situation shown in fig. 13.
One explanation is the the COF is at location
Y outside of Cp, and vi = v2. But a second
explanation is that the COF is at X, inside 0p,
and v2 > v1. Veiocity synchronization (vi = v2)
is key to ensuring that we can infer whether or
not the COF is in Cp.
We have used methods similar to those in
secs. 2-5 to develop protocols that do not require
synchronization. Removing explicit synchroniza-
Left R?bet
cit
- a
Comm?cic?tie			Right R?bet
??icit
R?p??t
LHR (Ac?)
A?2
LR (?)
+ A
Figure 14: A simplified version of protocol P.V.
P.V performs velocity synchronization, using ex-
plicit local communication (it does not perform
the pushing task!) The velocity of each robot is
incremented or decremented by a fixed amount
Av, depending on which on which robot gets
ahead. This simplified version assumes that
=0.
tion from manipulation protocols is analogous to
removing explicit communication. The ideal pro-
tocol we started with assumed global coordina-
tion and control i.e., global velocity synchro-
nization. Next, we developed a velocity synchro-
nization protocol P.V with explicit local commu-
nication. Given our analysis above, it is very
simple to develop such a protocol, and we give
the basic idea in fig. 14. Next, we "composed"
it with protocol I(QS) above--Hthis corresponds to
"splicing" the circuits for P.V and P.I(QS) to-
gether. This is slightly more difficult, but using
the techniques outlined in this paper, it it not too
hard to do a careful analysis and get all the spe-
cial cases right. Finally, we removed all explicit
communication; again the robots communicate
"through the world" (through the task dynam-
ics). We leave it as an exercise for the reader to
develop the resulting, communication-free pro-
tocol for box pushing without explicit commu-
nication or synchronization.12 It was actually
`2Hint: the easiest way to compose the control loops' is
to first add two bits of explicit communication. A one-bit
L R datapath tells R when L has broken contact. A
symmetric L R datapath tells L when R breaks con-
tact. The need for this communication falls out of a syn-
thesis similar to the one we presented. However, a careful
analysis then shows that even these two bits of (explicit)
communication can be removed.
somewhat surprising to us that a uniform asyn-
chronous protocol with no explicit communica-
tion can be developed for this task.
7.2 Reorienting Large Objects
We would like to show that our methods could
also be useful in engineering new protocols for
difficult, multi-robot manipulation tasks. In this
direction, we have also considered three multi-
mobot manipulation protocols for box reorienta-
tion (see fig. 1 and [DJR]). We denote them by
,?, etc. For these protocols, we started with
the offline algorithm ? of [Rusj, which was de-
signed for multi-fingered robot hands with global
coordination. Next, we developed a protocol ?
for three cooperating mobile robots with local IR
communication. In this protocol, only one robot
moves at a time, so, although the task has been
"parallelized", it is not "load-balanced." Finally,
we removed all explicit communication be-
tween agents, and allowed the robots to perform
simultaneous, asynchronous manipulation of the
box. Protocol  has several advantages over
protocol ?. Using protocol , two robots (in-
stead of three) suffice to rotate the box. The
protocol is "uniform" in that the same program
(including the same termination predicate) runs
on both robots. More interesting, in ? it is no
longer necessary for the robots to have an a pm-
ori geometric model of the box--H whereas such
a model is required for ? and ?. Of course,
various assumptions must hold for the task to
succeed the point of our analyses is to reveal
these assumptions. We are currently completing
such an analysis. `?
In terms of program development, synchrony,
and communication, we have the following ap-
proximate correspondence between these proto-
cols:
`3In particular, we have considerably improved the pro-
tocol ilit from [DJR].
U)?? ?9
P??hi?g			R???i??t?ti?
p??t??? 0			global coordination
i			and control
P?????I I(QS)			local IR comm,
partial synchrony,
MIMD
P,?'???I II			uniform,
"`I'			asynchronous
We believe that a methodology for developing
coordinated manipulation protocols is emerging,
based on the tools described in this paper, [DJR],
and [Don4]:
1.
2.
3.
4.
Developing Parallel Manipulation Protocols
Start with a sensorless [EM, EMV] or near-
sensorless [Erd4, JR] manipulation proto-
col requiring global coordination of sev-
eral "agents" (eg., fingers [Gol, Rus], or
"fences" [PS]). Examples: i above [Rus]
or protocol O (fig. 3).
Distribute the protocol over spatial sepa-
rated agents. Synchronize and coordinate
control using explicit local communication.
Examples: Protocol I(QS), or ? above.
Define a virtual senso?4 that measures the
key signal we wish to servo on. Example:
? (or better, s = sign(? --H ?o)) in P.I(QS)
(fig. 8).
Find a way to implement this virtual sen-
sor using concrete sensors on mechanical ob-
servables. Example: n(t) in P.11 (fig. 9).
5. Transform the communication between two
agents L and R into shared data structures.
6. Implement the shared data structures as
"mechanical registers." Example: 0(t) is a
"register" that L and R share.
We believe that our methods are useful for
developing parallel manipulation protocols. We
think that information invariants can serve as a
`4We use the term in the sense of [DJ]; others, particu
larly Bendersen have used similar concepts.
framework in which to measure the capabilities
of robot systems, to quantify their power, and
to reduce their fragility with respect to assump-
tions that are engineered into the control system
or the environment. We believe that the equiva-
lences that can be derived between communica-
tion, internal state, external state, computation,
and sensors, can prove valuable in determining
what information is required to solve a task, and
how to direct a robot's actions to acquire that
information to solve it.
8 Discussion
The analogy between our reductions and CT
reductions is tenuous in places; for example, to a
computer scientist it may appear (syntactically)
that our reductions go in the wrong direction.
However, (semantically) the opposite direction
does not appear to make sense, as a little thought
will show. Readers who are still uncomfortable
can define a new relation ?k such that A ?k B
when A <k B. More interesting, we may define
an equivalence relation k, such that A k B
when A ?k B and B ?k A.
Our work raises a number of questions. For ex-
ample, can robots "externalize," or record state
in the world? The answer depends not only on
the environment, but also upon the dynamics. A
juggling robot probably cannot. On a conveyor
belt, it may be possible (suppose "bad" parts are
reoriented so that they may be removed later).
However, it is certainly possible during quasi-
static manipulation by a single agent. In moving
towards multi-agent tasks and at least partially
dynamic tasks, we are attempting to investigate
this question in both an experimental and theo-
retical setting.
We may also ask, does a given class of sensori-
computational systems contain any circuits that
are "complete" for that class, in that they may be
reduced to any member of the class? Note that
the relation =k holds between any two complete
circuits.
Finally, can we record "programs" in the world
in the same way we may externalize state? Is
there a "universal" manipulation circuit which
D?? 0A
can read these programs and perform the correct
strategy to accomplish a task? Such a mech-
anism might lead to a robot which could infer
the correct manipulation action by performing
sensori-motor experiments.
Appendix
A What is Permutation?
In sec. 5 we examined a special case, where
S and U are partially situated (that is, the do-
mains of ? and ? are non-empty). A powerful
generalization is given in [Don4], where the sen-
sor systems can be unsituated. Using the ideas
in sec. 5, we can give an "abstract" version of
permutation that is applicable to partially im-
mersed sensor systems with codesignation con-
straints. Each set of codesignation constraints
defines a different arrangement in the space of
all immersions. Each cell in the arrangement, in
turn, corresponds to a region in Cd.
Permutation corresponds to selecting a dif-
ferent family of immersions, while respecting
the codesignation constraints. Since this corre-
sponds to choosing a different region of Cd, the
picture of abstract permutation is really not that
different from the computational model of situ-
ated permutations discussed in sec. 5. Suppose
a simple sensor system tt has d vertices, two of
which are u and v. When there is a codesigna-
tion constraint for u and v, we write that the
relation u v must hold. This relation induces
a quotient structure on Cd, and the correspond-
ing quotient map 7r : Cd Cd/(u v) "identi-
fies" the two vertices v and v. Similarly, we can
model a non-codesignation constraint as a "di-
agonal" A C 0d that must be avoided. Abstract
permutation of U can be viewed as follows. Let
= (Cd --H A)/(u v). Du is the quotient of
(Cd --H A) under r . For a partial immersion ??
to be chosen compatibly with the codesignation
constraints, we view permutation as a bijective
self-map of the disjoint equivalence classes
f r(exV?* --H A) J????(?).			(11)
Thus, in general, the group structure for the per-
mutation must respect the quotient structure for
codesignation; correspondingly, we call such per-
mutations valid. Below, we define the "diagonal"
A, precisely.
Now, an unsituated sensor system U could be
modeled using a partial immersion ?o with an
empty domain. In this case exv)0 = Cd and
eq. (11) specializes to the single equivalence class
f Du ?. In this "singular" case, we can take sev-
eral different approaches to defining unsituated
permutation. (i) ?`e may define that ?o*
Although consistent with situated permutation,
(i) is not very useful. We choose a different def-
inition. For unsituated permutation, we rede-
fine ?(V)o) and ex i[)o in the special case where
?o has an empty domain. (ii) When L4 is sim-
ple, we may define "`(v)o) to be the set of colo-
cations of vertices of iA. That is, let (x1,.. . ,xd)
be a point in Cd, and define the jjth diagonal
Aij = f(x1,... , rd) I x1 Xj ?. Define per-
mutation as a bijective self-map of the cells in
the arrangement generated by all (d2) such diago-
nals t Aij 1i4--H1d So, ?(?o) is an arrangement
in Cd of complexity o(d2dT?), ex?t C "`(v)o) is
a cell in the arrangement, and ?? E ex 43t is a
witness point in that cell. Hence v)t is a rep-
resentative of the equivalence class ex ??. As
in situated permutation, unsituated permutation
can be viewed as a self-map of the cells ? ex
or (equivalently) as a self-map of the witnesses
f v)t Y Perhaps the cleanest way to model our
main examples (sec. 4) is to treat all the sen-
sor systems as initially unsituated, yet respecting
all the (non)codesignation constraints. This may
be done by (1) "algebraically" specifying all the
codesignation constraints, (2) letting the domain
of each immersion be empty, (3) using (ii) above,
choose unsituated permutations that respect the
codesignation constraints. The methods of sec. 5
can be extended to guess unsituated permuta-
tions. In our examples (sec. 4), each guess (i.e.,
each unsituated permutation) corresponds to a
choice of which vertices to colocate.15
15The codesignation relation u v, the quotient map
Ir, the non-codesignation relation A, and definition (ii) of
unsituated permutation, can all be extended to algebraic
sensor systems using the methods of sec. 5.
A.1 Example
LTnsituated permutation is quite powerful.
Consider deciding eq. (8) (in this example, we
only consider vertex permutation of simple sen-
sor systems). In particular, we want to see
that (8) makes sense for unsituated permutation,
when we replace ? by ?o, b by 4)o, etc., to obtain:
? lS(?o), Vdo ?_ex?, V?0*_? Ds(?) n ex?o*)
(8')
With situated permutation (8), we are re-
stricted to first choosing the partial immersion
b? and thereby fixing a number of vertices of
8. Next, we can permute I" to be "near" these
vertices (this corresponds to the choice of ?*)
This process gets the colocations right, but at
the cost of generality; we would know that for
any `topologically equivalent" choice of ?, we
can choose a permutation ?? such that (8) holds.
For simple sensor systems, "topologically equiva-
lent" means, "with the same vertex colocations."
Unsituated permutation (8') allows us to do
precisely what we want. In place of a partial im-
mersion ? for 8, we begin with a witness point
?o C Cd. ?o represents an equivalence class ex
of immersions, all of which colocate the same ver-
tices as ?o. So, ?o says which vertices should be
colocated, but not where. Now, given ?o, the
outer existential quantifier in (8') chooses an un-
situated permutation ?? of U. ?o* represents an
equivalence class ex ?o* of immersions of L4, all of
which colocate the same vertices of U as ?? does.
The other, disjoint equivalence classes, are also
subsets of cd; each equivalence class colocates
different vertices of II', and the set of all such
classes is ?(?o) (= lS(?t)). Choice of ?o* selects
which vertices of tA to colocate. The codesigna-
tion constraint Ds(.) then enforces that, when
measuring the outputs of 8 and t4, we install
them in the same "place." More specifically: ?o
(given as data) determines which vertices of 8 to
colocate; choice of ?? determines which vertices
of U are colocated; construction of Ds(.) deter-
mines which vertices of U and 8 are colocated.
Most specifically, given the configuration bo of 8,
D8 in turn defines a region Ds(To) in the config-
uration space Cd of tI. This region constraints
the necessary coplacements ?o* of U relative to
(8, ?).
Perhaps surprisingly, allowing unsituated per-
mutation does not change the complexity bounds
of sec. 5 [Don4].
Bibliography
[BK] Blum, M. and Kozen, D. On the
power of the compass (or, why mazes are
easier to search than graphs), Proc. 19th
Symp. Found. Computer Science, Ann Arbor,
MI, pp. 132-42 (1978).
[Bri] Briggs, Ai?y. An Efficient Algorithm
for One-Step Compliant Motion Planning with
Uncertainty, Aigorithmica, 8, (2), 1992. pp. 195-
208.
[Canj John Canny On computability of fine
motion plans, IEEE ICRA, Scottsdale, AZ,
(1989)
[CR] Canny, J., and J. Reil, `New Lower
Bound Techniques for Robot Motion Planning
Problems", FOCS (1987).
[Don] Donald, B. R. Information Invariants
in Robotics, Parts I and H, IEEE International
Conference on Robotics and Automation, At-
lanta, GA. (1993).
[Doni] Donald, B. R. Robot Motion Plan-
ning, IEEE Trans. on Robotics and Automa-
tion, (8), No. 2. (1992).
[Don2] Donald, B. R. The Complexity of
Planar Compliant Motion Planning with Uncer-
tainty, Algorithmica, 5 (3), pp. 353-382 (1990).
[Don3j Donald, B. R. Error Detection and
Recovery in Robotics, Lecture Notes in Com-
puter Science, Vol. 336, Springer-Verlag, New
York (1989).
[Don4] Donald, B. R. On Information Invari-
ants in Robotics, Cornell Computer Science De-
partment Technical Report TR 93-1341. (1993).
[DJ] Donald, B. R. and J. Jennings Con-
structive Recognizability for Task-Directed Robot
Programming, Jour. Robotics and Autonomous
Systems, (9), No. 1, Elsevier/North-Holland pp.
41-74. (1992).
[DJR] Donald, B. R., J. Jennings, and
D. Rus Experimental Information Invariants
for Cooperating Autonomous Mobile Robots, In-
ternational Joint Conference on Artificial Intel-
ligence (IJCAI) Workshop on Dynamically In-
teracting Robots. Chambery, France (Aug 28)
(1993).
[Erdi] Erdmann, M. Using Backprojections
for Fine Motion Planning with Uncertainty,
IJRR Vol. 5 no. 1(1986).
[Erd2] Erdmann, M. On Probabilistic Strate-
gies for Robot Tasks, Ph.D. thesis, MIT Depart-
ment of EECS, MIT A.I. Lab, Cambridge MIT-
AI-TR 1155 (1989).
[Erd3] Erdmann, M. Action Subservient
Sensing and Design, IEEE ICRA, Atlanta. See
also the Carnegie-Mellon report CMU-CS-92-
116. (1993).
[Erd4] Erdmann, M. Randomization for
Robot Tasks: Using Dynamic Programming in
the Space of Knowledge States, Algorithmica
Vol. 10, Nos. 2/3/4, Aug/Sept/Oct. pp. 248-291
(1993).
[EM] Erdmann, M., and M. Mason, `?An
Exploration of Sensorless Manipulation", IEEE
International Conference on Robotics and Au-
tomation, San Francisco, April, 1986.
[EMV] Erdmann, M., M. Mason, and
G. Vanecek Mechanical Parts Orienting: The
Case of a Polyhedron on a Table, Algorithmica
Vol. 10, Nos. 2/3/4, Aug/Sept/Oct. pp. 266-247
(1993).
[Gol] Goldberg, K. Y Orienting Parts with-
out Sensors, Algorithmica Vol. 10, Nos. 2/3/4,
Aug/Sept/Oct. pp. 201-225 (1993).
[HSS] Hopcroft, J. E., Schwartz, J. T.,
and Sharir, M. 1984 On the Complexity of
Motion Planning for Multiple Independent Ob-
jects; PSPACFHardness of the `Warehouse-
man's Problem." International Journal of
Robotics Research. 3(4):76--H88.
[Hors] Horswill, I. Analysis of Adaptation
and Environment, Submitted to Artificial Intel-
ligence (1992).
[JR] Jennings, J. and Rns, D. Active Model
Acquisition for Near- Sensorless Manipulation
with Mobile Robots, The lASTED International
Conference on Robotics and Manufacturing, Ox-
ford, UK (1993).
[Koz] Kozen, D. Automata and Planar
Graphs, Fundamentals of Computing Theory,
Proc. Conference on Algebraic, Arithmetic,
and categorical methods in Computation The-
ory (Berlin) ed. L. Budach, Akademie Verlag
(1979).
[Lat] Latombe, J.-C. Robot Motion Planning,
Kluwer: New York (1991).
[LMT] Lozano-Pe'rez, T., Mason, M. T.,
and Taylor, R. H. Automatic Synthesis of
Fine-Motion Strategies for Robots, Int. J. of
Robotics Research, Vol 3, no. 1(1984).
[Mas] Mason, M. T. 1986. Mechanics
and Planning of Manipulator Pushing Opera-
tions. International Journal of Robotics Re-
search 5(3).
[ML] Mason, M. and Lynch, K. Dynamic
Manipulation, Proc. of the 1993 IEEE/RSJ
Int. Conf. on Intelligent Robots and Systems,
Yokohama, Japan, July 26-30 (1993).
[Nat] Natarajan, B. K. On Planning As-
semblies, Proc. of the 4th Annual Symposium
on Computational Geometry, Urbana, Illinois,
June. pp. 299-308. (1988).
[PS] Peshkin, M. Planning Robotic Manipula-
tion Strategies for Sliding Objects, Ph.D. disser-
tation, Department of Physics, Carnegie-Mellon
University (1986).
[RD] Rees, J. and B. R. Donald Program
Mobile Robots in Scheme, Proc. IEEE Interna-
tional Conference on Robotics and Automation,
Nice, France (1992).
[Reif] Reif J., "Comple?ty of the Mover?s
Problem and Generalizations," Proc. 20th IEEE
Symp. FOCS, (1979). Also in "Planning, Geom-
etry and Complexity of Robot Motion", ed. by
J. Schwartz, J. Hopcroft and M. Sharir, Ablex
publishing corp. New Jersey, (1987), Ch. 11,
pp. 267-281.
[Ros]			Rosenschein,			S.J.			Syn-
thesizing Information- Tracking Automata from
Environment Descriptions, Teleos Research TR
No. 2 (1989).
[Rns] Rus, D. "Fine Motion Planning for Dex-
terous Manipulation", PhD. Thesis available as
CU-CS-TR 92-1323 (August) from Comp. Sci.
Dept., Cornell University, 1992.
Acknowledgment and Historical Note. Many
key ideas in this paper arose in discussions with
Tomas Lozano-Pe'rez, Mike Erdmann, Matt Mason,
and Ronitt Rubinfeld. Toma's suggested studying the
two-finger pushing task in 1987, and laid out a frame-
work for analysis. Many of the ideas in this paper de-
velop suggestions of Mike Erdmann; in particular, he
proposed the notion of calibration comple?ty. Any
perspicuous reader will notice our indebtedness to
Mike's wcitanschauung, and to [Erd3]. The robots
and experimental devices described herein were built
in our lab by Jim Jennings, Russell Brown, Jonathan
Rees, Craig Becker, Mark Battisti, and Kevin New-
man; these ideas could never have come to light with-
out their help. Thanks to Loretta Pompilio for draw-
ing the illustration in figure 4. Debbie Lee Smith,
Amy Briggs, and Karl-Freidrich B5hringer made sug-
gestions and helped draw the other figures, and we
are very grateful to them for their help.
