BIB-VERSION:: CS-TR-v2.0
ID:: CORNELLCS//TR94-1430
ENTRY:: 1994-06-27
ORGANIZATION:: Cornell University, Computer Science Department
LANGUAGE:: English
TITLE:: Information Invariants for Distributed Manipulation
AUTHOR:: Donald, Bruce Randall
AUTHOR:: Jennings, James 
AUTHOR:: Rus, Daniela 
DATE:: June 1994
PAGES:: 38
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 rellocating (a) - (e) among collaborating autonomous 
agents. We add a resource to (a) - (e) and ask: (f) How much information is 
provided by the task mechnics? 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 report on experiments to measure and analyze information 
invariants using a pair of cooperating mobile robots for manipulation 
experiments in our laboratory.
END:: CORNELLCS//TR94-1430
BODY::
Information Invariants for
Distributed Manipulation*
Bruce Randall Donald
James Jennings
Daniela Rus
TR 94-1430
June 1994
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. lRI-8802390, IRl-92000532, 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 N0001 4-
92-J-1989, and by NSF Contract IRI-9006137.
This paper is a revised version of a paper presented at the Workshop on the
Algorithmic Foundations of Robotics (WAFR), San Francisco, Feb. 17, 1993.
Information
Bruce Randall
Invariants for Distributed
Manipulation1
Donald, James Jennings, and Daniela Rus
Robotics & Vision Laboratory
Computer Science Department
Cornell University
Ithaca, New York
U.S.A
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) --H
among collaborating autonomous agents. We add a resource to (a) --H (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) --H (e). The protocols we describe here have been implemented in
several different forms, and report on experiments to measure and analyze information
invariants using a pair of cooperating mobile robots for manipulation experiments in
our laboratory.
1This 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. IRl?88o239O. IRI-9O00532, 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 0NR Contract NOOO1?92-J-1989, by 0NR Contract N00014-92-J.39, and by NSF Contract
IRI-9006137.
This paper is a revised version of a paper presented at the Workshop on the Algorithmic Foundations of Robotics (WAFR),
San Francisco, Feb. 17, 1993.
1 Introduction
In this paper, we develop and analyze synchronous and asynchronous manipulation protocols
for a small team of cooperating mobile robots than can push large boxes. The boxes are
typically several robot diameters wide, ?nd 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 dynamic 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 friction distribution is known. Instead, the robot combines sensorimotor
experiments 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 kinematic 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 really "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 structure of the task. We believe our theory
has implications for the parallelization of manipulation tasks on spatially distributed teams
of cooperating robots. To develop a parallel manipulation strategy, first we start with a
perfectly synchronous protocol with global coordination and control. Next, in distributing it
among cooperating, spatially separated agents, we relax it to an MPMD2 protocol with local
communication and partial synchrony. Finally, we remove all explicit communication. The
final protocols are asynchronous, and essentially "uniform," or SPMD2 the same program
runs on each robot. Ultimately, the robots must be viewed as communicating implicitly
through the task dynamics, and this implicit communication confers a certain degree of
synchrony on our protocols. Because it is both difficult and important to analyze the infor-
mation content of this implicit communication and synchronization, we are wielding a fairly
heavy hammer, namely the theory of information invariants.
1.1 The Big Picture
Our goal is to investigate the information requirements 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 review) has been to determine what infor-
mation is required to solve a task, and to direct a robot's actions to acquire that information
7SPMD (MPMD) = ?Sin?Le (MultipLe) ?Progr?m, Multiple Data.
2
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 information?
3. What properties of the world have a great effect on the fragility of a robot plan/program?
4. 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
industrial robots, contribute towards simplifying the robot's task because a great amount
of information is encoded, often ?mplic?tly, into both the environment and the robot's con-
trol program. These encodings (and their effects) are difficult to measure. We wish to
quantify the information encoded in the assumption that (say) the mechanics are quasi-
static, or that the environment is not dynamic. In addition to determining how much
information" is encoded in the assumptions, we may ask the converse: how much "in-
formation" must the control system or planner compute? Successful manipulation strate-
gies often exploit properties of the (external) physical world (eg, compliance) to reduce
uncertalnty and hence gain information. Often, such strategies exploit mechanical com-
putation, in which the mechanics of the task circumscribes the possible outcomes of an
action by dint of physical laws. Executing such strategies may require little or no com-
putation; in contrast, planning or simulating these strategies may be computationally ex-
pensive. Since during execution we may witness very little "computation" in the sense of
"algorithm," traditional techniques from computer science have been difficult to apply in
obtaining meaningful upper and lower bounds on the true task complexity. We hope that
a theory of information invariants can be used to measure the sensitivity of plans to par-
ticular assumptions about the world, and to minimize those assumptions where possible.
3
`ri
We would like to develop a notion of information invari-
ants for characterizing sensors, tasks, and the complex-
ity of robotics operations. We may view information
invariants as a mapping from tasks or sensors to some
measure of information. The idea is th?at this measure
characterizes the intrinsic information required to per-
form the task--Hif you will, a measure of complexity. For
example, in computational geometry, a rather success-
ful measure has been developed for characterizing input
sizes and upper and lower bounds for geometric algo-
rithms. Unfortunately, this measure seems less relevant
in robotics, although it remains a useful tool. Its ap-
parent diminished relevance in embedded systems re-
flects a change in the scientific culture. This change
represents a paradigm shift from offline to online algo-
rithms. Increasingly, robotics researchers doubt that we Figure 1: The Cornell mobile robot
may reasonably assume a strictly offline paradigm. For Note (mounted to bottom on
example, in the offline model, we might assume that the the I? Modems, and the bump sensors.
robot, on booting, reads a geometric model of the world LILY is very similar.
from a disk and proceeds to plan. As an alternative,
we would also like to consider online paradigms where the robot investigates the world and
incrementally builds data structures that in some sense represent the external environment.
Typically, online agents are not assumed to have an a pT%Ori 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
questions such as "what is the complexity of plan construction for a known environment,
given an a prn'om 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 capabilities, and how they are programmed. These examples and the pa-
pers [JR,Don,Don4] link our work to the recent but intense interest in online paradigms for
situated autonomous agents. In particular, in these papers, we discuss what kind of data
structures robots can build to represent the environment. We also discuss the externalization
of state, and the distmbution 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 considered or modeled in the online paradigm.
The chief lacuna in the armamentarium of devices for analyzing online strategies is a prin-
cipled theory of sensori-computational systems. We attempt to fill this gap in [Don,Don4j,
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 information invariants. When a measure of intrinsic information invariants
can be found, then it leads rather naturally to a measure of hardness or difficulty. 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.
4
Figure 2: TOMMY and LILY pushing a couch in a straight line, using an
asynchronous SPMD protocol requiring no explicit communication
In our quest for an intrinsic measure of the information requirements of a task, we are
inspired by Erdmann's monograph on sensor design [Erd3], and the information invariants
that Erdmann introduced to the robotics community in 1989 [Erd2]. We also observe that
rigorous examples of information invariants can be found in the theoretical literature from as
far back as 1978 (see, for example, [BK, 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, [Erd1, Don2, Can, Bri] for upper bounds). Rosenschein has
developed a theory of synthetic automata which explore the world and build data-structures
that are "faithful" to it [Ros]. His theory is set in a logical framework where sensors are
logical predicates. Perhaps our theory could be viewed as a geometric attack on a similar
problem. This work was motivated by the theoretical attack on perceptual equivalence begun
by [DJ] and by the experimental studies of [JR]. Horswill [Hors] has developed a semantics for
sensory systems that models and quantifies the kinds of assumptions a sensori-computational
program makes about its environment. He also gives source-to-source transformations on
sensori-computational "circuits." The paper [Don4] discusses the semantics of sensor sys-
tems. This formalism is used to explore some properties of what we call situated sensor
systems. [Don4] describes a way to transform sensori-computational systems. When one
can be transformed into another, we say the latter can be "reduced" to the former, and
we call the transformation a "reduction." We also derive algebraic algorithms for reduc-
ing one sensor to another. This machinery is only necessary if one wishes to automate the
transformation process; it is quite easy to calculate reductions "by hand," using pencil and
paper.
5
A'
In addition to the work discussed here in sec. 1,			mAy
for a detailed bibliographic essay on previous re- ;; )
search on the geometric theory of planning under )-w??
uncertainty, see, eg., [Doni] or [Don3].
The goals outlined here are ambitious and we
have only taken a small step towards them. The Figure 3: The box is being rotated by three
questions above provide the setting for our inquiry, cooperating autonomous (a) The motion of
but we are far from answering them. We hope that relative motion of the pushing robots, viewed in a
information invariants can serve as a framework in system of coordinates fixed on the box. The arrows
which to measure the capabilities of robot systems, illustrate the direction of the applied forces.
to quantify their power, and to reduce their fragility
with respect to assumptions that are engineered into the control system or the environment.
We believe that the equivalences that can be derived between communication, internal state,
external state, computation, and sensors, can prove valuable in determining what informa-
tion is required to solve a task, and how to direct a robot's actions to acquire that informa-
tion to solve it. There are several things we have learned. We can determine a lot about
the information structure of a task by (i) parallelizing it and (ii) attempting to replace ex-
plicit communication with communication "through the world" (through the task dynamics).
Communication "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 information. Our ap-
proach of quantifying the information complexity in the task mechanics involves viewing the
world dynamics as a set of mechanically implemented "registers" and "data paths". This
permits certain kinds of de facto communication between spatially separated robots. This
"equivalence" of task mechanics and communication is operational in flavor, and we are still
exploring its generality.
We believe that, by spatially distributing resources among cdlaborating agents, the in-
formation characteristics of a robot task are made explicit. That is, by asking, How can
this task be performed bu a team of robots? one may highlight the information structure. In
robotics, the evidence for this is, so far, largely anecdotal. In computer science, one often
learns a lot about the structure of an algorithmic problem by parallelizing it; we argue that
a similar methodology is useful in robotics.
It is very difficult to analyze the interaction of sensing, computation, communication
(a --H e) and mechanics (f) in distributed manipulation tasks. The analyses of [Don4] focus
on (a --H e), 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 remains to develop
a framework that treats action and sensing on an equal footing.
This paper draws extensively on the material reported in the draft monograph by Don-
ald [Don4], and announced in an abbreviated, preliminary version in [Donj. We reported on
our ideas on coordinated manipulation strategies in a preliminary form in [DJRi-2]
6
m?
Mm-
A
w4Th-??
A
A
Repeat
measure(r)
case			= 0) ?
push(p)
(r < 0) ?
rnove(R)
(r > 0) ?
move(L)
Figure 4: (a) the tw?finger pushing task vs. (b) the two robot Figure 5: Protocol 0 (for a tw?fingered gripper).
pushing task. The goal is to push the block B in a straight line.
1.1.1 Research Agenda
Robot builders make claims about robot performance 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 similar (or even identical) tasks may
look very different. 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 theory, which represents a systematic attempt to make
such comparisons based on geometric and physical reasoning. In [Don4], we operationalize
our analysis by making it computational; we give effective (albeit theoretical) procedures for
computing our comparisons. See sec. 5 for a summary.
We wish to rigorously compare embedded sensori-computational systems. To do so, we
define a "reduction" <i that attempts to quantify when we can "efficiently" build one sensor
out of another (that is, build one sensor using the components of another).3 Hence, we
write A <i 1? 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 relativized both to the information complexity of the sensori-computational
components of B, and to the bandwidth of A. This relativization circumvents some tricky
problems in measuring sensor complexity. In this sense, our "components" are analogous to
oracles in the theory of computation. 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 (datapaths) connecting their internal components. However,
our sensori-computational systems differ from computation-theoretic (CT) "circuits," in that
their spatial configuration--Hi.e., the spatial location of each component--His as important as
?<i is also called <a in [Don].
7
their connectivity.
We develop some formal concepts to facilitate the analysis. Permutation models the
permissible 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). Geometric codesignation constraints
further restrict the range of admissible permutations. L e., we do not allow arbitrary re-
location; instead, we can constrain resources to be "installed at the same location", such
as on a robot, or at a goal. Output communication formalizes our notion of "a little bit
of rewiring." When resources are permuted, we often find they must be reconnected using
"wires", or data-paths. If we separate previously colocated resources, we will often need to
add a communication mechanism to connect the now spatially separate components. Like
CT reductions, A <i B defines an "efficient" transformation on sensors that takes B to A.
However, we can give a generic algorithm for synthesizing our reductions (whereas no such
algorithm can exist for CT.)4 Whether such reductions are widely useful or whether there
exist better reductions is open; however we try to demonstrate the potential usefulness both
through examples and through general claims on algorithmic tractability. 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. (Comparison). 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. (Design). Suppose we are given a specification for A, and a "bag of parts" for B.
The bag of parts consists of boxes and wires. Each box is a sensori-computational
component ("black box") that computes a function of (i) its spatial location or pose
and (ii) its inputs. The "wires" have different bandwidths, and they can hook the
boxes together. Then, our algorithms decide, can we "embed" the components of B
so as to satisfy 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 using the bag of parts B?
4.
(Universat Reduction). Consider application 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 relativized
both to A and to B, it measures the "power" of the components of A relative 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?"
More specifically: Let 0 be a "configuration" of sensorimotor system A. Thus 0
encodes the spatial embedding of A as well as its wiring connectivity. Similarly, let P
be a configuration of system B. Let A(a) and B(P) denote systems A and B "installed"
4For example: no algorithm exists to decide the existence of a linear-space (or log-space, polynomial time, Thrin&
computable, etc.) reduction between two CT problems.
8
at these configurations. The gist of application 4 is that, we can decide whether or not
(Vot, ?P): A(o) ?i B(p).
1.2 Outline
We discuss questions (a) --H (f) from the Abstract for an experiment with communicating
robots. We consider the task of coordinated manipulation of large objects (particularly,
manipulation of a large box using a pair of communicating mobile robots). We foreground
the task of pushing an object, using two communicating robots who need to infer the position
of the first moment of the friction distribution with respect to their lines of pushing (see
Figure 4a). In [Don4], we asked whether explicit communication 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 communication, and we
analyze and compare the the protocols using the tools introduced in [Don4J. We believe our
methods generalize to other manipulation tasks and to larger teams of robots, but work is
still underway; for example, in [DJR1.2], we considered the task of coordinated manipulation
of large objects (particularly, rotations, or more accurately, "reorientations? 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.
2 Pushing with Two Communicating Mobile Robots
To introduce our ideas we consider a task involving two autonomous mobile robots. The two
robots must cooperate to push a box. Now, many issues related to information invariants can
be investigated in the setting of a single agent. However, one of our ideas is that, by spatially
distributing resources (a) --H (f) among collaborating agents, the information characteristics
of a task are made explicit. That is, by asking, How can this task be performed by 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 direction) with two agents. We first describe
a strategy 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.
2.1 Three Pushing Protocols
Consider the task whose goal is to push a box B in a straight line. Figure 4a depicts one
robot (the reader should picture a robot manipulator, 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
9
Left Robot
Repeat:
measure(fi)
Communication Right Robot
Repeat:
measure(f?)
mi
r = r1 x fi --H r2 x f2
LR (sign(r))
push(p)			push(p)
(r <0) ?			(r > 0) ?
if(break?)			if(break?)
guarded-move(p)			guarded-move(p)
else?			else?
(r> 0) ?			(r < 0) ?
move(L)			rnove( R)
M
Figure 6: Protocol I
Figure 7: The mechanical observables for Protocol I
it is difficult to predict the results of a one-fingered push; we will only obtain a straight-line
trajectory when the center of friction (COF) lies on the line of pushing. However, with a
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 4a), 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
Protocol 0 on our PUMA (see fig. 5). The basic idea is to sense the reaction torque T about
the point 0 in Figure 4a. If r = 0, push forward in direction y. If r < 0 move the fingers in
x; else move the fingers in --Hx.
From the mechanics perspective it might appear we are done. However, it is difficult to
overstate how critically Protocol 0 above relies on global communication and control. Now,
consider the analogous pushing task in Figure 4b. 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 1), but the details of their construction are not important. The
robots can move about by controlling motors attached to wheels. The robots are autonomous
10
and equipped with a ring of 12 simple Polaroid ultrasonic sonar sensors. 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, arrayed in a ring about the robot body. Each modem consists of
an emitter-detector pair. When transmitting or receiving, each modem essentially functions
like the remote control for home appliances (e.g., televisions). In addition, each robot has a
ring of one-bit contact ("bump") sensors.
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 flat face of the
object; (3) both robots know the direction of pushing, p; and (4) robots can synchronize
their velocities.5 In addition, (5) by examining the servo-loop in [RD], it is clear that we
can compute a measure 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 fol-
lowing (see Figs. 7, 6). Each robot can measure its applied 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 infer 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 "recapture" the center of friction between the two lines
of pushing by moving left along the face of the box (move(L)). If the right robot is not in
contact with the box (the predicate (break?) returns TRUE) it executes a guarded-move
(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 7, 6).
A variant of this protocol can be derived for a quasi-static (QS) system. Here, relative
displacements along the line of pushing p are measured instead of forces. Figure 9 shows
a configuration where the two robots originate at positions xi(O) and x2(O), respectively.
Their locations at time t are xi(t) and x2(t). In this protocol (Figure 8), the initial locations
of the robots are communicated to determine their offset ?o. ?o "specifies" (or better,
parameterizes) the pushing task: this offset determines the pushing direction p relative to
the initial orientation of the box face. The robots exchange location information successively
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 9, 8).
We now derive a different version of Protocol I(QS) by observing that the information
needed to determine the motion of the box (i.e. ?o and ?) is related to the angle () between
the normal to the face of the box n and the direction of pushing p as follows: 2r tan 0o =
and 2r tan 0 = ? (see Figures 9, 11, 10). Moreover, we observe that the tangent function
is monotonic and sign preserving; this means we can adapt the control system to servo on
5For 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 protocol for velocity synchronization is not hard to synthesize using our
methods; see sec. 7.1.
11
o 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 6(t) measured at time tin
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
rotation. The robots adjust their pushin?g location on the face of the box accordingly. This is
an example 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).
12
Left Robot
rneasure(ri (0))
Repeat:
rneasure(ri (t))
case
Communication			Right Robot
rneasure(z? (0))
LR (:i(0))
= :?(0) --H
Repeat:
rneasure(:?(t))
L??R (:i(t))
= z2(t) --H
s = ?gn(? --H
LR			(s)
case
= 0) ?
push(p)			push(p)
= --H1) ?			= --H1) ?
rnove(R)			rnove( R)
= 1) ?
move(L)			move(L)
Figure 8: Protocol I (Quasi.Static). The case for breaking contact is not shown; it can be handled as in fig. 6.
A
M
(?F ?)\ffi\
L :i(t)			x2(O)
? xi(O)
Figure 9: Protocol I(QS). The normal to the box face is
denoted by n. The: 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.
13
Left Robot			Right Robot
00 0(0)			00 0(0)
Repeat			Repeat
CUC
(break?) ?			(break?) ?
g'iarded-move(p)			guarded-move(p)
(0(t) 9o) ?			(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 P.11. This protocol is "almost uniform, and can be made uniform by changing the ? lines (*) to
MovE(L) and (**) to MovE(R). Note that uniform does not quite imply SIMD, since the protocols run asynchronously.
R
Figure 11: The mechanical observables for Protocol II.
14
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 Protocol I(QS) the robots
synchronize by exchanging their sensed values.
Robots executing Protocol I require communicating log k(f1) bits to transmit the value
of force fi, and 2 bits to transmit the sign of the torque r (k(b) denotes how many values a
variable b may take on). Robots executing Protocol I(QS) require log k(x1) bits to transmit
the value of the distance x1, 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 () 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 register to record the value ?o. Protocol II requires
a register to record the value 0o.
We can get a deeper understanding of the relationship between these protocols by at-
tempting 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 "circuits."
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 correspond to
different sensori-computational components of the system (what we will call "resources"
below). Edges correspond to "data paths" through which information passes. Different
immersions of these graphs correspond to different spatial allocation of the "resources." Our
idea involves asking: What information is added (or lost) in a sensor system when we change
its immersion? and What information is preserved 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
"sensori-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,
together with a labelling function that assigns a label to each vertex and edge. Where there
is no ambiguity, we denote the labelling function by ?.
Definition 3.2 A sensor system S is represented by a labelled graph (V, E). Each vertex is
labelled with a component. Each edge is labelled with a connection.
15
See figs. 12-13 for illustrations for the circuits that is, the sensor systems for protocols
I (QS) and II. We will use the terms protocol to refer to the computer programs in figs. 8-10,
and circuit for the sensor systems in figs. 12-13. It is clear that each circuit implements
its protocol. Now, ill Protocol I(QS) (fig. 8), there are three communications operations.
The first two (L R) use the same datapath; they simply refer to the first use, and to
subsequent use, of the same resource. In our circuits, we now restrict 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 correspond to boxes: ODOM
is an odometer, the "signal"6 coming out of this box is the odometry reading. The box
performs subtraction, the boxes zi(O) and ::::? are registers, and they implement internal
state. The part of the circuit labelled case interfaces to the control part of the circuits,
which is the same for both protocols.
One interesting resource is 0(t) in fig. 13--Hwe call this box a 0-sourc?it produces a signal
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 external "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 relative normal sensing [JR]. We
specify the pushing direction p, by specifying 0o (see fig. 10), the direction of p relative to
the box normal n(0) 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 normal to the box,
using the bounded-error algorithm of [JR]. Finally, the robot turns by angle 0o using pure
position control.
INIT is one bit of state, and RUN= INIT. The small crossed circles (?) that these bits run
into are gates; the I input must be 1 for the signal to pass. Thus in robot L in fig. 12,
if INIT= 1, then the odometer writes into the register x1(0). When INIT= 0, then the ?
component is fed 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 xi(0) is written. Whereas L requires one bit of state INIT0, R requires 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
represents the information that will be sent along that path. Connections carry data between
components. We adopt the convention that two components can communicate without an
(explicit) connection when they are spatially colocated. Now, in figs. 12-13, many of the
data paths are internal, i.e., L L or R R. The most interesting datapaths are the erternal
datapaths: the ???edge (b) labelled coMM(Axi), and the L ?edge (b') labelled COMM(s)
(b) has bandwidth logk(Ax1) bits, and (b') has bandwidth 2 bits.
Observe fig. 13. Here, there is a 0-source that is external to both robots. There are
two interesting external data paths from the 0-source, one to L marked COMM(.), and one
marked (b) to R. Both these datapaths have bandwidth logk(0(t)) bits.
Definition 3.3 Let b be a variable that ranges over all possible values that a sensor system
can compute. We call b the output of the system. Let k(b) be the number of values b can
?We use "signai" as a metaphor; our circuits are strictly digital. Either message or stream would be
better, but both have distracting religious connotations.
16
take on, and define log k(b) to be both the size of b and the output size of the sensor. The
output size is an upper bound on the bit-complexity of b. For example, if b takes on integer
values in the range [1,q], then k(b) = q, and logk(b) = logq. Now, suppose the information
b is communicated over a datapath e. We will assume that the information is communicated
repeatedly; without loss of generality, we take the unit of time to be the interval of the
occasion to communicate the information. Thus we can take the size of the output b to be
the bandwidth of e.
So far, we have defined components and connections operationally. We now give a formal
definition. Components and connections are defined by their simulation functions. Simula-
tion functions describe the behavior of both components and connections.
Consider a component ?(v) associated with vertex v. To simulate a component, we need
to know (i) its inputs and (ii) its configuration. Suppose a component has r inputs and
s outputs, each of which lies in some space R. Let C be the configuration space of the
component. A simulation function for a component ?(v) is a map7 ?? : R? x C Rs.
Now we connect the components together. Assume for a moment that all the components
have the same input-output structure as ?,, above (i.e., that r and 5 are fixed throughout the
system, but that the components themselves may perform different functions). We model
an edge e between vertices v and u by its label, ?(e) = b, and by a pair of integers, (i,j).
logk(b) is the bandwidth of the edge and the index i (resp. j) specifies to which of the r
outputs of C(v) (resp., 8 inputs of ?(u)) we attach e (1 < i < r and 1 < j <
Now, a simulation function for this edge e is taken to be a function ?? : R R. We
will usually restrict the edge functions to be the identify function (but they also check for
bandwidth, i.e., that the transmitted data has size no greater than logk(b)).
We also define a resource called the "output device." Each sensor system must have
exactly one vertex with this label, called the ouput vertex. The output vertex of the sensor
system is where the output of the sensor is measured. The simulation function for the output
device is the identity function, but the output value of this device defines the output value
of the sensor system.
A simulation function ?u for an entire sensor system U, then, is a collection of component
simulation functions such as ?? and edge simulation functions such as ??. The function ?u
simulates all the component simulation functions in the correct configuration, and simulates
routing the data between them using the edge simulation functions. We adopt the conven-
tion that two components can communicate without an (explicit) connection when they are
spatially colocated. When all these component and edge functions are semi-algebraic, then
the sensor simulation function ?u is also semi-algebraic (see Section 5).
Definition 3.4 Consider a sensor system U with simulation function ?u. The output value
of U at a particular configuration is the value ?u computes for that configuration. Hence the
output value of U is a function of U `s configuration.
The notions output value and output (Definition 3.3) are related as follows. The output
of U is a variable that ranges over all possible output values of U. Given another sensor
7Components that retain state can be modeled by a function ?? : R? x C x S RS )< s, where S is a store
that records the state. For example, a state element with k bits of state would be modeled with S = f 0, 1 ?k
Alternatively, S can be absorbed as a factor subspace in the configuration space of the component.
17
system V, we say the output of U is the same as the output of V when ?? and ?? are
identical.
Under this model, we can simulate trees of embedded sensorimotor computation. It is
also possible (in principle) to simulate more general graphs and systems with state, 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 explicit notion of time and blocking to model the (a)synchronous
arrival of data at a component. Such extensions are considered in [Jen94]; for now we restrict
our attention to trees, which suffice to model our examples. In general our discussion is
restricted to consider one clock-tick; however, generalizations are possible to consider the
time-varying behavior of the system [Jen94]. We will treat the circuits P.I(QS) and P.11
(below) as effectively being trees, and not graphs, even though there is data flow both from
R to L and L to R. This is because to a first order approximation, data does not not feed
back into the system.
To summarize: a component is a primitive device that computes a a function of (i)
its inputs and (ii) its configuration z E C. Each component is installed at a vertex of
communication graph with d vertices, whose edges are the connections described above. The
graph is immersed in a configuration space Cd, and the configuration z of a component is
the configuration of its vertex. More generally, components can be actuators. An actuator is
a component whose output forces the configuration of the graph to change or evolve through
a dynamics equation. If the configuration of the entire graph is z = ??.....,?.... , zd) E Cd,
then the dynamics equation models a mapping from the actuator component ?(v)'s output
at z to the tangent space TzCd to the configuration space. See [Jen94] for more discussion
of actuators. The actuator systems of our circuits are identical and in this paper we do not
consider them in detail. This actuator subsystem is represented by the elision CASE(S) ... in
figs. 12-13. The circuit for this system would look very much like a traditional plant diagram
from control engineering.
Weaker forms of sensori-computational equivalence are possible. If we define the state
of a sensor system U to be a pair (z, b) where z is the configuration of the system and b
is the output value at z, we can examine the equilibrium behavior of U as it evolves in
state space. Consider the Definition 3.6; let us call this strong simulation. By analogy, let
us say that a system U weakly simulates another system V when U and V have identical,
forward-attracting compact limit sets in state space.5 If we replace strong simulation (N=
in Definition 3.6) with weak simulation, all of our structural results go through mutatis
mutandis. The computational results also go through, if we can compute limit sets and their
properties (a difficult problem in general). Failing this, if we can derive the properties of
limit sets "by hand" then in principle, reductions using weak simulation instead of strong
simulation (N=) can also be calculated by hand.
In our sensor systems, there is no separate notion of "sensor inputs." Instead, the sensory
inputs are encoded in the configuration space.
81 am grateful to Dan Koditschek, who has suggested this formalism in his papers.
18
A
A
ii
Figure 12: Sensor system P.I(QS). This is a circuit for
Protocol I (QS). This circuit shows one possible
implementation of the protocol. Figs. 12-13 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.
3.2 Transformations as Reductions
4
4--;---
Figure 13: Sensor system P.11. This is a circuit for
Protocol II.
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, operationally 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 Protocol II, we demonstrated that
one implementation of such a sensor involves using some retalned 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 engineering fact. Below, we carefully define the operators + and --H,
and formalize the notions of simulation and efficient reduction, as well as permutation, etc.
Our reduction involves two concepts. The first is permutation, and it involves redis-
tributing resources 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 configuration of lower entropy.
The second concept is communication. It measures resource (b) (from the abstract). We
consider adding communication primitives of the form COMM(L R, info), which indicates
that L sends message info to R. Examples of this primitive are COMM(?x1) and COMM(S)
in fig. 12. 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 complexity to the system. In
effect, to transform system Protocol 0 into Protocol I(QS) (see figs. 5, 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 measure
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
19
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
system in its own right (albeit, a small one). Now, COMM(b) defines the graph with vertices
fui,u0i and a single edge e = (u1,u0) with ?(e) = b. The "head" vertex u0 of the edge
e = (ui, uo), is defined to be the output i'ertex of the sensor system COMM(b). The argument
(parameter) b to COMM(b) determines the bandwidth of e. Thus, for example, COMM(b)
specifies 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 k(b) bits to encode then k is the bandwidth
of e. Our model of communication is rather abstract. External communication is probably
not possible without buffering by either the sender or the receiver. 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
vertex v in V, we assume there is a configuration space C. A point in this space C represents
the configuration of the component.
Definition 3.5 A situated (or immersed) sensor system S is a sensor system S = (V, E),
together with an immersion ? : V C of the vertices. If v E V, then we call ?(v) the
configuration of the vertex v. When there is no ambiguity, we also call ?(v) the configuration
of the component ?(v).
A situated sensor system is essentially an immersed graph. If the map ? in def. 3.5 is
injective, then we call ? an embedding. Immersions need not be injective. Moreover, in order
to colocate vertices, it is necessary for immersions to be non-injective.
In def. 3.5, the immersion ? 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 domain of the immersion. We denote the domain of a (partial) immersion
?: V C by ?-1C. We denote its image by im ?
We can now define what it means for two systems to be equivalent:
Definition 3.6 Given two sensor systems 5 and Q, we say Q simulates 8 if the output of
Q is the same as the output of 8. In this case we write 8 N? Q More generally, suppose we
write
(1)
N=
for two situated sensor systems. Eq. (1) is clearly well-defined when ? and ? are total. Now,
suppose that ? and ? are partial, leaving unspecified the configurations of components ?(v)
of S and ?(u) of U. Then eq. (1) is taken to mean that (U, ?) simulates (S, ?) for any
configuration of v and u.
For def. 3.6, in the case where (say) ? is partial, we operationalize eq. (1) by rewriting it as
a statement about all extensions ? of ?. That is, we define ex ? to be the set of all extensions
of ?. Then, we write: "V? E ex ?, eq. (1) holds (with bars placed over the immersions)."
We treat ? similarly, with an inner universal quantifier, although codesignation constraints
(sec. 3.5) allow us to make the choice of extension ? of ? depend on the extension ? that is
bound by the outer quantifier. For example, def. 3.6 becomes, "for all configurations x E C
of v, for all configurations y E Ds(x) of u, eq. (1) holds." Here D5(x) is a set in C that varies
with x; the function Ds(.) models the codesignation constraints. Def. 3.6 can be generalized
to any number of "unbound" vertices; see eq. (8) and [Don4].
20
3.3 Permutation
We may consider two orthogonal kinds of permutation. In both models1 the vertex and edge
labels ?(v) and ?(e) never change. The first model is called vertex permutation, and is given
in def. 3.7. In this model, the vertices can move, and they drag the components and wires
with them. That is, the vertices move (under permutation), and as they move, the edges
follow.
Vertex permutation of a situated sensor system corresponds to the choice of a different
immersion with the same domain:
Definition 3.7 Let S = (S, ?) be a situated sensor system. A permutation s* of S is a
situated sensor system (S, ?*) such that the domain ?-`C of ? and the domain ??1c of ?
are the same.
For technical reasons, we also permit a permutation to change which vertex has the
"output device" label. Note that the definition of permutation (def. 3.7) also makes sense
for partial immersions. 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
vertices V and edges E. Start with any bijection a : V2 V2. We call a an edge permu-
tation, since it induces the restriction map ?i? : 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 permu-
tation followed by an edge permutation. In a graph permutation, the vertices and the edges
move independently. That is, vertices may move, but in addition, the edge connectivity may
change. To illustrate the different models, consider a sensor system U with three vertices
t v11 v21 v3 ? with labels ?v1) = Bj (i = 1,2,3). U has one edge e = (v11 v2) of bandwidth
k that connects B1 to B2. So, the B1 are the components of the system, and e is a datap-
ath. A vertex permutation U* of U would move the vertices (and therefore the components)
spatially, but in U*1 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 permuta-
tion a(U) could be a graph with one edge a(e) = (v21 v3), connecting v2 to v3 (and hence B2
to B3). But in a(U) no edge would connect v1 and v2. Finally, consider a graph permutation
U* of U. Suppose U* = a(Us), that is, U* is the vertex permutation U* followed by the
edge permutation a above. U* has the same edge connectivity as a(U). However, in U*1 the
vertices are immersed as in U*.
Let (U, ?) be a situated sensor system. A graph permutation ofU is given by U* = (U, ?)
where ? = (?, a), ? is a vertex permutation, and a is an edge permutation. In practice, we
wish to impose some restrictions on edge and graph permutation. For example, suppose we
have a sensor system U containing two cooperating and communicating mobile robots L and
R. The sensori-computational systems for L and R are modeled as circuits. The datapaths in
the system, in addition to bandwidth, have a type, of the form SOURCE?DESTINATION, where
both SOURCE and DESTINATION E ? L, R ?. (Maintaining exactly two physical locations
can be done using simple codesignation constraints). When permuting the edges of IA to
21
obtain t4*, 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 U*, 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
unchanged the complexity bounds and the lemmas of [Don4].
To summarize: vertex permutation preserves the graph topology whereas edge permuta-
tion 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 consequences of allowing different kinds of permutation 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.8 Consider two graphs ? = (V E) and ?` = (V', E'). We define the combi-
nation ? + ?` of g and ?` as follows:
? +? = (VuV',EuE').
We may define + on sensor systems (def. 3.2) by lifting the definition for graphs. We may
define + on two immersed graphs whenever the immersions are compatible. An immersion
? of ? and an immersion ? of ?` are said to be compatible when the two immersions agree
on the intersection V n V' (for total immersions) or more generally, on b-1C n ?-1C (for
partial functions). Similarly:
Definition 3.9 Consider two graphs g = (V, E) and ?` = (V', E'), where ?` is 5 subgraph
of ?. We define the difference ? --H g' of ? and ?` as follows:
Def. 3.9 may also be lifted to (partially) immersed graphs, and hence to situated sensor
systems.
3.5 Reductions, Calibration, and Codesignation
As we observed in [Don], calibration exploits external state. We wish to order systems on how
much information this external state (from calibration) yields, to obtain def. 3.10, below.
Calibration complexity is defined formally in [Don4]. Here is the basic idea. Calibration
complexity measures how much information we add to a sensor system when we install and
calibrate it. Installing a sensor system may require physically establishing some spatial
relation between two components of the system. In this case we say the two components
codesignate by the spatial relation. More generally, we may have to establish a relation
22
between a component and a reference frame in the world. Most generally, when we compare
two sensor systems 5 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 system is simple. When all the relations are semi-algebraic (s.a.),
we say the system is algebraically codesignated.
Definition 3.10 We write 5 < Q when
1. Q simulates 5 (5 N=
2. 5 dominates Q in calibration complexity, and
3. The maximum bandwidth of 5 is at least that of Q (def. 3.12).
Convention: We will now drop the notation ?, and use Q* to denote any graph permutation
of sensor system Q, as described above.
Definition 3.11 We write 5 <* Q if there exists some (graph) permutation Q5 of sensor
system Q such that 5 < Q*.
3.5.1 Relativized Information Complexity
Consider a sensor system with output z. The complexity of many sensors can essentially be
characterized using the size log k(z) of the output 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 internal bandwidth that is much higher
(log k(AO) or log k(Ax) bits). The output in some sense encodes that information. That is,
we may view the protocols as "recognizing" a "model" or a "signal" of size O(logk(?x))
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 k(Ax)
bits.9
Another idea is to observe that the actuator output p in PUsH(p) would be at a similar
resolution to the orientation sensing 0(t) or odometry x1(t). This argues that the "output"
of the protocol is something more like O(logk(p)) 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.'0 For example: consider a "grandmother" sensor. Such a sensor looks at a visual
field and outputs one bit, returning *t if the visual field contains a grandmother and #f if it
doesn't. Now, one view of the sensor interpretation problem is that of information reduction
and identification (compare [DJJ, which discusses hierarchies of sensor information). However
9To see that instrumenting AO and A: require the same number of bits, requires an argument like the decalibration"
lemmas of [Hors]. For this paper, we can see this from the relation 2r tan 0(t) =
10This discussion devolves to a suggestion of Sundar Narasimhan [Personal communication], for which we are very grateful.
23
consider a somewhat different perspective, that views sensors as model matchers. So, imagine
a computational process that calculates the probability P(G/V) of G (grandmother) given
V (the visual field) --H i.e., the probability that G is in the data (the visual field itself). The
sensor in the former case is something specific only to detecting grandmothers, 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 storing prior distributions. These distributions
bias it toward a fixed set of model classes. In principle, the stored distributions may be viewed
either as calibration or internal state. To quantify the absolute information complexity of
a sensor system, we need to measure the information complexity of model classes stored in
the prior distribution of the sensor. This could be very difficult.
Instead, we propose to measure a quantity called the maximum bandwidth of a sensor
system. Intuitively, this quantity is the maximum over all internal and external edge band-
widths (data-paths). That is:
Definition 3.12 We define the internal (resp. external) bandwidth of a sensor system S to
be the greatest bandwidth of any internal (resp. external) edge in S. The output size of S is
given by Definition 3.3. We define the maximum bandwidth to be the greater of the internal
bandwidth, external bandwidth, and the output size of S. We call a sensor system monotonic
if its internal and external bandwidths are bounded above by its output size.
The maximum bandwidth is an upper bound on the relative intrinsic output complexity
(relativized to the information complexity of the components (secs. 3 and 3.5.1)). We explore
this notion briefly below.
Maximum bandwidth is a measure of internal 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 sensor 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 powerful. 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 bandwidth we have for a black box is its 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 monotonic if its internal bandwidth is bounded
above by its 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(logk(p))
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 k(Ax) and log k(?O)
(resp.) Since 2r tan 0(t) = ?(t), we argue that these two systems have the same maximum
bandwidth.
24
3.5.2 Reductions using Communication
In light of this discussion, we now define the reduction <i from [Don], using relativized
information 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 complexity of 5. Measuring this (k) in general is
difficult, but we will treat the maximum bandwidth (def. 3.12) of 5 as an upper bound on k.
Definition 3.13 Consider two sensor systems 5 and Q. We say 5 is efficiently reducible
toQ if
5 <* Q + COMM(S).			(2)
In this case we write11 5 <i Q.
Now, permutation (the * operation) and combination (the + operation) "commute" for
compatible partial immersions. This is formalized as a "distributive" property in [Don4]. So,
for example, for any sensor systemS, we have ensured that S*+CoMM(.) = (S+COMM(.))*,
i.e., we can do the permutation and combination 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 bandwidth so that it still works when
we switch it (e) around using permutation. Hence, the sensor 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 appears that <i is not. To see this, suppose
that A <i B and B <i C. Then it appears that to reduce A to B we require one "extra
wire" (namely, COMM(A)), and that to reduce B to C we could require (another) extra wire
COMM(B), and therefore, in the worst case, to reduce A to C we could require two extra
wires. That is, it could be that A cannot reduce to C with fewer than two extra wires. We
have yet to find a non-artificial example of this lower bound but it appears to indicate that
<i is not transitive (even for simple sensor systems (sec. 3.5)).
Let us summarize. The reduction <i corresponds to a specific circuit transformation.
This transformation can be understood as follows. Let 5 be a monotonic sensor system with
output b. Let Q be another sensor system. We imagine Q as a "circuit" embedded in (say) the
plane. Let COMM(S) be a "sensor system" with one datapath e, that has bandwidth logk(b).
Then, adding output communication to Q can be viewed as the following transformation on
sensor systems: Q Q + COMM(S). The transformaton is parameterized by (the bandwidth
of) 5. The bounded-bandwidth datapath e can be spliced into Q anywhere. We note that
this transformation can be composed with permutation (in either order):
Q I,'			Q*			:?`			Q* + COMM(S)
II			II
Q I,' Q+COMM(S) I,' (Q+COMM(S))*.
11 <i is also called <s in [Don].
25
The reduction <i (def. 3.13) is a "i-wire" reduction. It does not appear to be transitive.
The- reduction ?? (def. 3.11) is a "0-wire" reduction. It is transitive for simple sensor
systems [Don4j. We could analogously define a 2-wire, or more generally, any k-wire reduction
<k by modifying eq. (2) in def. 3.13 to
5 <? Q + k COMM(S),			(2')
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 re-
ductions t <j liEN form a graded relation. Even though we believe that <i is not transitive (in
the elementary 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 <?io++j U. This follows from a lemma that the 0-wire reduction <o (called <? in def. 3.11)
is elementary transitive for simple sensor systems.
Consider the hierarchy of k-wire reductions ? <j liEN 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 transitive [Don4J.
4 Comparing Protocols Using Reductions
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
system ODOM to have one vertex, whose label is ODOM. It has a single component, an
odometer. Similarly, define the 0-source sensor system 0 to have a one vertex and a single
component 0(?), which is a 0-source. These systems can be installed (or better, spliced)
into" our circuits. Each black box comes with (simple) codesignation constraints. Vertex
ODOM must be installed on a robot (either L or R). So, its vertex codesignates with L or R.
Vertex e(t) must be installed at a location not on a robot. So, its ve?ex 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. Moreover, eq. (3) does not hold for k = 0.
Proof: Consider the sensor system U obtained by removing both odometers from circuit
P.I(QS), and adding a 0-source:
u = P.I(QS) --H 2oDoM +0.			(4)
Now, consider permutations of U, and recall def. 3.11. We first ask whether P.11 can be
reduced to U using <?. That is P II <? U? First, we note that we can move around the
registers and ?`s from U to situate all the components of P.11. We also have some leftover
components (and wires). P.11 requires two sign boxes; however, the SCN box just selects out
26
the sign bit. To build the extra sign box we can just ignore the other bits, or we can use the
leftover hardware from U to build a small circuit to simulate SCN. We need to argue that
a register big enough to hold xi(O) will also hold 0o; this follows from 2r tan 0(t) = ?(t), or
from "decalibration" [Hors]. Next, we see that we can permute the internal edges of U to
wire up the components of P.11 in situ internally. What about externally?
Permuting the external wiring almost works, but not quite. U has two external data
paths, (b') and (b), with bandwidth 2 bits and logk(?xi) bits (resp) (fig. 12). Now, since
we only allow 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. 13, the edge (b) from
U will suffice as a datapath from 0(t) to R, since it has adequate bandwidth. However, the
datapath (b') from U does not have adequate bandwidth to carry information from 0(t) to
L. In order to build P.11 from U, we must add another external data path coMM(.) from
0(t) to L. Now, what is the argument to coMM(.)? This data path must have bandwidth
of at least the relative intrinsic output complexity of P.11, or log k(A0) bits. Hence we may
parameterize this new edge by writing coMM(P.II), following sec. 3.5.1. Hence, we see that
Therefore by def. 3.11,
P.11 < (U + coMM(P.II))*
P.11 <? U + coMM(P.II),
so using def. 3.13, we have P.11 <i U. Hence we conclude
P.11 <i P.I(QS) --H 2oDoM +0,
which implies eq. (3) as desired. E]
(5)
(6)
(7)
This formalizes our intuition that, by removing odometry but adding relative normal
sensing, we can accomplish the pushing task without explicit communication. More pre-
cisely, we show how to build one circuit P.11 "efficiently" out of the other (U). To transform
P.I(QS) into P.11, the operators + and --H quantify what resources we add and delete. Rela-
tive information complexity allows us to measure the effective communication "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 existence of a suitable permutation. It is
somewhat surprising that we can in fact automate this process: [Don4] gives algorithms for
deciding the relation <1. More precisely, given suitable encodings of two sensor systems
S and U, we can computationally decide whether S <i U [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 involves employing the theory of real closed fields with bounded
quantification. Let us for a moment restrict our reductions to vertex permutation alone
(def. 3.7). First, suppose that S and U each have d vertices. Then an immersion of 8 can be
27
encoded as a point in Cd. More generally, a partial immersion ? whose domain contains 1 <d
vertices can be modeled as a point in c?. We can "guess" a (vertex) permutation ?? of ? by
existentially quantifying over the configurations of the 1 vertices inside ?`s domain. Hence,
the space of permutations of ?, denoted ?(?), is isomorphic to C1. Similarly, we can verify
a Tarski sentence for all extensions ? of ?, by universal quantification over the d --H 1 vertices
outside the domain of ?. Hence, the space of all extensions of ?, ex ?, is isomorphic to cd-t.
We will model (algebraic) codesignation constraints as a (possibly constant) semi-algebraic
(s.a.) mapping ? D(? taking an immersion ? to a s.a. set D(?) c cd. All these methods
generalize to graph permutation as well [Don4]. Now,
Definition 5.1 A simulation function ?u for U is a map ?u: cd R, where R the space
of outputs. We call the value ?u(?) E R of ?u on a sensor configuration ? to be the output
value or sensor value at ?.
Definition 5.2 We call a sensor systemU algebraic if it is algebraically codesignated (sec. ?.5),
has an algebraic configuration space C, and a semi-algebraic algebraic simulation function
How do we construct and permute simulation functions? Recall the discussion of sim-
ulation functions for components and connections aboye. To decide <? means to deciding
whether or not (5, ?) <? (U, ?). Hence we must decide whether there exists a permuta-
tion ?? of'k such that (S, ?) ?N (U, `k*) Computationally, this requires deciding the Tarski
sentence12
(????(?, V??ex? V?EDsF?flex?):
(8)
Here, Ds(.) models the codesignation constraints; they require the choice of extension ?? by
the inner quantifier to depend on the extension ? selected by the middle quantifier. When
comparing two sensor systems 5 and U, we typically must install and calibrate them in
some appropriate relative configuration--Hi.e., in the spatial relation that the codesignation
constraint Ds(.) encodes.
If we can decide <?, we can decide <i. Here is why: to decide ?<i, we must determine
whether (5, ?) <? (U, ip) + COMM(S), (def. 3.13). Recall the definition of compatibility for
partial immersions (sec. 3.4). We first observe that permutation (the * operation) and com-
bination (the + operation) "commute" for compatible partial immersions [Don4]. Our argu-
ments above for guessing extensions and permutations can be generalized mutatis mutandis
to compute the combination (def. 3.8) of two algebraic sensor systems. Since COMM(S) is a
constant-sized sensor system (2 vertices, one edge) with only a constant number of codesig-
nation constraints (at most 2), we may guess how to combine it with a permutation (IA, ?*)
of (5, ip) within the same time bounds given below in lemma 5.3 and eqs. (9--H10).
Let us suppose that IA and 5 are algebraic. Let us define the size d of IA to be the number
of vertices in IA. Let the simulation complexity n0 be the size of the simulation functions ?u
12We must also be able to compute dominance in calibration complexity (see def. 3.10). This can be done
independently, and much faster than eq. (8) can be decided; see [Don4].
28
and ?s. We let ?? measure the complexity of the codesignation constraints Ds(.) 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 al-
gebraic sensor systems. It runs in time polynomial in the simulation and codesignation
complexity (n0 + n?), and sub-doubly exponential in the size of the sensor systems. That is,
if the system has size d the time complexity is
(n0 + ?? )(?cd)0(1)			(9)
where r? is the dimension of the configuration space C for a single component. ?
Let us call U small if n? and ?? are only polynomially large in d, i.e., (n? + n?) =
Note that for "small" sensor systems, eq. (9) becomes
d(rcd)O(l)
(10)
Although complex, eq. (8) is simplified for presentation. The full Tarsid sentence also
contains codesignation constraints for the outer quantifiers, and is given in [Don4]. We must
warn that in sec. 5 we have examined a special case, where S and U are partially situated
(that is, the domains of ? and ? are non-empty). A powerful generalization is given in
app. A, where the sensor systems can be unsituated.
6 Sensitivity of the Model
We wish to explain whether or not our theory 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 changing our model of reduction (specifically,
permutation) slightly, to see how that affects our results. Second, we ask, what if the input
were ree?ncoded slightly differently? Would our results change a lot?
Specifically, we ask: how can we compare vertex permutation with graph permutation
(sec. 3.7)? 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 reduction 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 ree?ncode a sensor system so as to gain a lot of
"power" (information complexity).
[Don4] first derives the complexity bounds in lemma 5.3 and eq. (9--H10) for vertex permu-
tation. 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
permutations, 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 constants) [Don4].
We now address question (ii): does graph permutation give us a more powerful reduction?
We show:
29
Lemma 6.1 (The Clone Lemma) Graph permutation can be simulated using vertex permu-
tation, preceded by a linear time and linear space transformation of the sensor system.
Proof: Given a sensor system U 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 U 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 C' = (V', E') with labelling function e'. Let the cloning function cl: V ``? v
be an injective 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) = (cl(u),cl(v)). Edge labels are defined as follows: ?(d(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 E V. Otherwise, ?(v) returns the "identity" component,
which can be simulated as the identity function.13
Suppose IA has d = V vertices and El edges. This transformation adds only d vertices
and can be computed in time and space O(d + El). E]
Let us denote by cl(IA) the linear-space clone transformation of IA described in lemma 6.1.
Now consider any k-wire reduction <k (sec. 3.5.2). We see that:
Corollary 6.2 Let k E N. Suppose that for two sensor systems IA and V, we have V ?k IA
(using graph permutation). Then V <k cl(IA) (using only vertex permutation). ?
7 Experiments
Using information invariants, we have presented a formal post hoc analysis of two manip-
ulation protocols for a pushing task. However, we are also using these techniques in our
laboratory for synthesis, to develop new manipulation protocols and analyze their robustness
and information content. We believe that our techniques are useful both for transforming
protocols so as to 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 methods can give
valuable insights into the information structure of the task.
7.1 Removing Assumptions
The protocols we described depend critically on the assumption of velocity synchronization.
For example, let v1 and v2 be the speeds of the robots. Let Cp be the region between the
13The 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) = ? for v ? V. This version has the appeal of changing
the encoding without adding additional physical resources.
30
xi(O)
R
Figure 14: Two robots pushing a box. If
their speeds are equal, we can infer that the
COF is at Y, outside C,. However, if the
right robot is faster, it is possible that the
COF lies between the pushing rays at X.
Left Robot
init
Repeat
euure(?:1)
--H sit
Communication			Ri.ht Robot
so(:2(0))
init
Repeat.
m(it:2)
L?R (iti)
itsi - it52
s			.ign(?)
LR (s)
?v+sitn
Figure 15: A simplified version of protocol P.V. P.V
performs velocity synchronization, using explicit local
communication (it does not perform the pushing task!) The
velocity of each robot is incremented or decremented by a fixed
amount ?v, depending on which on which robot gets ahead.
This simplified version assumes that ?o = 0
pushing rays p. Consider the situation shown in fig. 14. One explanation is the the COF is
at location Y outside of Cp, and v1 = v2. But a second explanation is that the COF is at
X, inside Cp, and v2 > v1. Velocity synchronization (v1 = 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 synchronization from manipulation protocols is
analogous to removing explicit communication. The ideal protocol we started with assumed
global coordination and control--Hi.e., global velocity synchronization. Next, we developed a
velocity synchronization protocol P.V with explicit local communication. Given our analysis
above, it is very simple to develop such a protocol, and we give the basic idea in fig. 15. Next,
we "composed" it with protocol I(QS) abov&this corresponds to "splicing" the circuits for
P.V and P.I(QS) together. 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 special cases right.
Finally, we removed all explicit communication; again the robots communicate "through the
world" (through the task dynamics). We leave it as an exercise for the reader to develop the
resulting, communication-free protocol for box pushing without explicit communication or
synchronization.14 It was actually somewhat surprising to us that a uniform asynchronous
protocol with no explicit communication can be developed for this task.
14Hint: 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 contact. The need for this communication falls out of a synthesis similar to the one we presented.
However, a careful analysis then shows that even these two bits of (explicit) communication can be removed.
31
7.2 Reorienting Large Objects
We would like to show that our methods
Pushing			Reorien?s?ion
could also be useful ill engineering new pro-
tocols for difficult, multi-robot manipulation tasks.			P?n?n?n? 0			global coordination
In this direction, we have also considered three			Prutucol 1(QS)			A			and control
multi-mobot manipulation protocols for box re-			A			partial synchrony,
orientation (see fig. 3 and [DJR1-2]). We de-			MPMD
note them by A ,A, etc. For these proto-			Protn?ui II			uniform, SPMD,
cols, we started with the offline algoflthm A			A			asynchronous
of [Rus], which was designed for multi-fingered Figure 16: Summary of parallel manipulation
robot hands with global coordination. Next, we protocols.
developed a protocol A 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, A
we removed all explicit communication between agents, and allowed the robots to perform
simultaneous, asynchronous manipulation of the box. Protocol A has several advantages
over protocol A. Using protocol A, two robots (instead of three) suffice to rotate the box.
The protocol is "uniform" (SPMD) in that the same program (including the same termina-
tion predicate) runs on both robots. More interesting, in A it is no longer necessary for the
robots to have an a priori geometric model of the box--H whereas such a model is required for
A and A. 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.15
In terms of program development, synchrony, and communication, we have the following
approximate correspondence between these protocols:
We believe that a methodology for developing coordinated manipulation protocols is
emerging, based on the tools described in this paper, [DJRi-2], and [Don4]:
Developing Parallel Manipulation Protocols
1. Start with a sensorless [EM, EMV] or near-sensorless [Erd4, JR] manipulation pro-
tocol requiring global coordination of several "agents" (eg., fingers [Gol, Rus], or
"fences" [PS]). Examples; A above [Rus] or protocol 0 (fig. 5).
2. Distribute the protocol over spatially separated agents. Synchronize and coordinate
control using explicit local communication. Examples: Protocol I(QS), or A above.
3. Define a virtual sensoA6 that measures the key signal we wish to servo on. Example:
? (or better, s = sign(? --H ?o)) in P.I(QS) (fig. 8).
4. Find a way to implement this virtual sensor using concrete sensors on mechanical
observables. Example: n(t) in P.11 (fig. 11).
`5In particular, we have considerably improved the protocol A from [DJRl].
`6We use the term in the sense of [DJ]; others, particularly Henderson have used similar concepts.
32
Figure 17: TOMMY and LILY reorient a couch using an asynchronous SPMD protocol requiring no
explicit communication.
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
?????gi5t??fl 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 framework in which to measure the
capabilities of robot systems, to quantify their power, and to reduce their fragility with
respect to assumptions that are engineered into the control system or the environment. We
believe that the equivalences that can be derived between communication, 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
Our work raises a number of questions. For example, 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"
33
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 theoretical setting.
By analogy with CT reductions, we may define an equivalence relation =k, such that
A =k B when A <k B and B <k A. We may also ask, does a given class of sensori-
computational systems contain "complete" circuits, to which any member of the class may
be reduced? 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 can read these programs and perform the
correct strategy to accomplish a task? Such a mechanism might lead to a robot which could
infer the correct 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
domains of ? and ? are non-empty). A powerful generalization is given in [Don4J, where the
sensor systems can be unsituated. Using the ideas in sec. 5, we can give an "abstract" version
of permutation that is applicable to partially immersed sensor systems with codesignation
constraints. 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 different family of immersions, while respecting
the codesignation constraints. Since this corresponds to choosing a different region of Cd, the
picture of abstract permutation is really not that different from the computational model of
situated permutations discussed in sec. 5. Suppose a simple sensor system U has d vertices,
two of which are u and v. When there is a codesignation constraint for u and v, we write
that the relation u v must hold. This relation induces a quotient structure on Cd, and
the corresponding quotient map 7r: Cd Cd/(u v) "identifies" the two vertices u and v.
Similarly, we can model a non-codesignation constraint as a "diagonal" A C Cd that must be
avoided. Abstract permutation of U can be viewed as follows. Let Du = (Cd --H A)/(u N v).
Du is the quotient of (Cd --H A) under 7r. 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
--H A) ???E?(?).			(11)
Thus, in general, the group structure for the permutation must respect the quotient structure
for codesignation; correspondingly, we call such permutations valid. Below, we define the
"diagonal" A, precisely.
34
Now, an unsituated sensor system LI could be modeled using a partial immersion ?o
with an empty domain. In this case ex?0 = Cd and eq. (11) specializes to the single
equivalence class I Du 1 In this "singular" case, we can take several different approaches
to defining unsituated permutation. (i) We may define that ?o* = ?O Although consistent
with situated permutation, (i) is not very useful. We choose a different definition. For
unsituated permutation, we redefine ?(?o) and ex ?? in the special case where ?o has an
empty domain. (ii) When U is simple, we may define ?(?o) to be the set of colocations
of vertices of U. That is, let ....... ,xd) be a point in Cd, and define the jjth diagonal
= f(x1,... ,xd) Xj = Xj 1. Define permutation as a bijective self-map of the cells in the
arrangement generated by all such diagonals I ??i 1i,j=id So, ?(?o) is an arrangement
in Cd of complexity O(d2drc), ex?0* ? ?(?o) is a cell in the arrangement, and ?o* ? ex?0*
is a witness point in that cell. Hence ?o* is a representative of the equivalence class ex
As in situated permutation, unsituated permutation can be viewed as a self-map of the cells
I ex `ko* 1 or (equivalently) as a self-map of the witnesses I `ko* 1. Perhaps the cleanest way to
model our main examples (sec. 4) is to treat all the sensor 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 permutations. In
our examples (sec. 4), each guess (i.e., each unsituated permutation) corresponds to a choice
of which vertices to colocate.17
A.1 Example
Unsituated permutation is quite powerful. Consider deciding eq. (8) (in this example, we
only consider vertex permutation of simple sensor systems). In particular, we want to see
that (8) makes sense for unsituated permutation, when we replace ? by ?o, ? by ?, etc., to
obtain:
(3?o* E ?(`ko), V? E_ex?, VQ* E Ds(To) fl exQ*):
(8')
With situated permutation (8), we are restricted to first choosing the partial immersion
?, and thereby fixing a number of vertices of s. Next, we can permute U to be "near" these
vertices (this corresponds to the choice of 1p*). 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
equivalent" means, "with the same vertex ??
Unsituated permutation (8') allows us to do precisely what we want. In place of a partial
immersion ? for S, we begin with a witness point ? E Cd. ? represents an equivalence
class ex ?? of immersions, all of which colocate the same vertices as ??. So, ?o says which
vertices should be colocated, but not where. Now, given ?, the outer existential quantifier
in (8') chooses an unsituated permutation ?o* ofU. ?o* represents an equivalence class ex?0* of
L7The codesignation relation tL v, the quotient map r, 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.
35
immersions of IA, all of which colocate the same vertices of IA as ?? does. The other, disjoint
equivalence classes, are also subsets of cd; each equivalence class colocates different vertices
of IA, and the set of all such classes is ?(?o) (= ?(?o*)). Choice of ?o* selects which vertices
of IA to colocate. The codesignation constraint Ds(?) then enforces that, when measuring
the outputs of S and IA, we install them?in the same "place." More specifically; ? (given as
data) determines which vertices of S to colocate; choice of ?o* determines which vertices of
IA are colocated; construction of Ds(?) determines which vertices of IA and S are colocated.
Most specifically, given the configuration ? of S, Ds in turn defines a region Ds(?) in the
configuration space Cd of IA. This region constraints the necessary coplacements ?o* of IA
relative to (S, ?o)
Perhaps surprisingly, allowing unsituated permutation does not change the complexity
bounds of sec. 5 [Don4]
Bibliography
[BK] Blum, M. and Kozen, D. On the power of the compass (or, wh? mazes are easier to
search than graphs), Proc. 19th Symp. Found. Computer Science, Ann Arbor, MI, pp. 132-42
(1978).
[Bri] Briggs, Amy. An Efficient Algorithm for One-Step Compliant Motion Planning with
Unceflaint? Algorithmica, 8, (2), 1992. pp. 195-208.
[Can] John Canny On computabilit? of fine motion plans, IEEE ICRA, Scottsdale, AZ,
(1989)
[Cit] Canny, J., and J. Reif, "New Lower Bound Techniques for Robot Motion Planning
Problems", FOCS (1987).
[Don] Donald, B. it. Information Invariants in Robotics, Parts I and II, IEEE International
Conference on Robotics and Automation, Atlanta, GA. (1993).
[Doni] Donald, B. it. Robot Motion Planning, IEEE Trans. on Robotics and Automation,
(8), No. 2. (1992).
[Don2] Donald, B. it. The Complexity of Planar Compliant Motion Planning with Uncer-
tainty, Algorithmica, 5 (3), pp. 353-382 (1990).
[Don3] Donald, B. it. Error Detection and Recovery in Robotics, Lecture Notes in Com-
puter Science, Vol. 336, Springer-Verlag, New York (1989).
[Don4] Donald, B. it. On Information Invariants in Robotics, Cornell Computer Science
Department Technical Report TR 93-1341. To appear in Artificial Intelligence. (1993).
[DJ] Donald, B. it. and J. Jennings Constructive Recognizabihty for Task-Directed Robot
Programming, Jour. Robotics and Autonomous Systems, (9), No. 1, Elsevier/North-Holland
pp. 41-74. (1992).
[DJR1] Donald, B. it., J. Jennings, and D. Rus Experimental Information Invariants
for Cooperating Autonomous Mobile Robots, International Joint Conference on Artificial In-
telligence (IJCAI) Workshop on Dynamically Interacting Robots. Chambery, Prance (Aug
28) (1993).
36
[DJR2] Donald, B. R., J. Jennings, and D. Rus Towards a Theory of Information In-
variants for Cooperating Autonomous Mobile Robots, International Symposium on Robotics
Research (ISRR). Hidden Valley, PA (October 2, 1993). (1993).
[Erdi] Erdmann, M. Using Backprojections for Fine Motion Planning with Uncertainty,
IJRR Vol. 5 no. 1 (1986).
(Erd2] Erdmann, M. On Probabilistic Strategies for Robot Tasks, Ph.D. thesis, MIT De-
partment 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 Automation, San Prancisco, April, 1986.
[EMV] Erdmann, M., M. Mason, and G. Vane?c?ek 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 without 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 Mo-
tion Planning for Multiple Independent Objects; PSPACEHardness of the "Warehouseman`s
Problem." International Journal of Robotics Research. 3(4):76--H88.
(Hors] Horswill, I. Analysis of Adaptation and Environment, Submitted to Artificial In-
telligence (1992).
(JR] Jennings, J. and Rus, D. Active Model Acquisition for Near-Sensorless Manipulation
with Mobile Robots, The lASTED International Conference on Robotics and Manufacturing,
Oxford, UK (1993).
(Koz] Kozen, D. Automata and Planar Graphs, Pundamentals of Computing Theory,
Proc. Conference on Algebraic, Arithmetic, and categorical methods in Computation Theory
(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 Operations.
International Journal of Robotics Research 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).
37
[Nat] Natarajan, B. K. On Planning Assemblies, Proc. of the 4th Annual Symposium on
Computational Geometry, Urbana, filinois, June. pp. 299-308. (1988).
[PS] Peshkin, M. Planning Robotic Manipulation Strategies for Sliding Objects, Ph.D.
dissertation, Department of Physics, ?Carnegie-Mellon University (1986).
[RD] Rees, J. and B. R. Donald Program Mobile Robots in Scheme, Proc. IEEE Inter-
national Conference on Robotics and Automation, Nice, France (1992).
[Reif] Reif J., "Complexity of the Mover's Problem and Generalizations," Proc. 20th IEEE
Symp. FOCS, (1979).
[Ros] Rosenschein, S.J. S?nthesizing Information- Thacking Automata from Environment
Descriptions, Teleos Research TR No. 2 (1989).
[Rus] Rus, D. "Fine Motion Planning for Dexterous 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. Tom? suggested study-
ing the two-finger pushing task in 1987, and laid out a framework for analysis. Many of the ideas
in this paper develop suggestions of Mike Erdmann; in particular, he proposed the notion of cali-
bration complexity. Any perspicuous reader will notice our indebtedness to Mike's weltanschauung,
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 Newman; these
ideas could never have come to light without their help. Thanks to Loretta Pompilio for drawing
the illustration in figure 1. Debbie Lee Smith, Amy Briggs, and Karl-Preidrich B5hringer made
suggestions and helped draw the other figures, and we are very grateful to them for their help.
38
