Architectures and Control of Networked Robotic Systems

chestpeeverAI and Robotics

Nov 13, 2013 (7 years and 11 months ago)


ugust 3,2013 23:33 PSP Book - 9.75in x 6.5in Handbook-Collective-Robotics
Architectures and Control of Networked
Robotic Systems
Nikolaus Correll,Daniela Rus
Networked robot systems are ensembles of robots that enhance their individ-
ual capabilities by sharing perception,computation and actuation capabilities with
each other to solve problems that an individual robot could not solve alone.In this
chapter,we focus on architectures and control of autonomous networked robot
systems that communicate wirelessly.We will ﬁrst provide an overviewover cur-
rent networked robot platforms spanning 3 orders of magnitude in size (frommil-
and that are networked using light,sound and radio.We will then describe classes
on reactive and deliberative algorithms for sharing perception,computation,and
actuation.The chapter is concluded with a summary of current challenges and
promising directions.
3.1 Introduction
A networked
robot systemis a systemcomprised of multiple robots in which
robots actively communicate with each other,sensors,or other computational
agents using some formof wireless communication.
chapter provides an overviewon technical properties of wireless commu-
nication,algorithms for networked robot systems,and their modeling and anal-
ysis.Rather than being a survey over the state of the art in networked robots,it
aims at illustrating its key concepts using selected representative platforms,algo-
rithms,and references.This chapter provides an overview over the properties of
light,sound and radio communication,mechanisms for mutual localization using
sound,radio and light,and an overview over reactive,deliberative and hybrid
control of networked robot systems and their analysis.
and Control of Networked Robotic Systems
Networked robot systems consist of teams of ground [Howard et al.(2006)],air
(Chapter??),under water vehicles (Chapter??),or combinations thereof [Hsieh
et al.(2008a)],andheterogeneous systems consisting of robots andsensor networks
[Correll et al.(2009a)].Networked robots are analogous to sensor networks [Es-
trin et al.(1999)],but allow individual nodes to be mobile and have manipulation
capabilities.The resulting robot network is thus able to adapt the spatial distri-
bution of its sensors and actuators,and actively modify its environment,leading
to additional challenges in coordination and control.On the hardware side,robot
networks not only require the capabilities for actuation and locomotion,but also
sensors that are able to determine the mutual position of the robots in dynamic
3.1.Instances of networked platforms for table-top/lab experiments ranging from systems-
on-a-chip of a fewmillimetres and communicating via infra-red to the smallest commercially available
robot running embedded Linux and supporting IEEE 802.11g.From left to right:The I-Swarm robot
(Chap.??),the Alice robot [Caprari and Siegwart (2005)],the e-puck [Mondada et al.(2009)],and the
Khepera III (K-TeamS.A.).
Instances of ground,underwater and aerial platforms are shown in Figs.3.1.,
3.2.and Fig.3.3..We selected these platforms as they are representative for spe-
ciﬁc communication infrastructure (light,acoustics,low and high bandwidth ra-
dio) and the order of magnitude of volume currently needed for their implemen-
tation.For instance low-range,low-bandwidth communication has been demon-
strated with robots as small as 2 mm x 2 mmm (see also Chap.??),whereas one
of the smallest platforms that implements IEEE 802.11g radio communication and
a Linux networking stack (Khepera III
) has a diameter of 12 cm.Similarly,long-
wave radio communication requires a certain minimumsize due to the necessary
length of the antenna [Kottege and Zimmer (2008)].
Applications for networked robot systems are generally focussing on increas-
ing the spatial resolution of sensing and actuating robots by mobility.Applications
such as assembly of structures [Yun et al.(2009)],environmental monitoring [Choi
et al.(2010)],inspection [Correll and Martinoli (2009)] and deployment of wire-
less networks [Correll et al.(2009b)] directly beneﬁt fromthe spatial distribution of
the networked system and the ability to conduct these tasks in parallel.Applica-
3.2.Instances of networked platforms for underwater operation that use sound,radio and
light for peer-to-peer communication.Seraﬁna [Kottege and Zimmer (2008)],Amour [Vasilescu et al.
(2005);Doniec et al.(2009)] and Slocum [Rudnick et al.(2004)].The Slocum glider is networked with
other robots using a centralized server with which it communicates when surfacing.
3.3.Instances of networked platforms for aerial operation that communicate using ZigBee and
IEEE 802.11g.Marvelis (Mohseni lab,CU Boulder),the UFO [Gurdan et al.(2006)],the SMAV [Hauert
et al.(2009)],and the NexStart UA[Frewand Brown (2008)].
3.4.Instances of networked robotics systems.Fromleft to right:The Distributed Robot Garden
at MIT CSAIL [Correll et al.(2009a)].The automated warehouse robots fromKIVAsystems,image cour-
tesy of Raffaelo D’Andrea.Robots interacting with visitors and people tracking systems in a shopping
mall [Shiomi et al.(2009)].
tions such as search [Lochmatter and Martinoli (2009)] and mapping [Howardet al.
(2006)] beneﬁt fromthe increased resolution of the robot system.Finally,applica-
tions such as data ferrying [Bhadauria and Isler (2009)] beneﬁt fromthe increased
mobility of the networked robot system.Some of these applications are depicted in
Fig.3.4.showing robots to coordinate tending of plants [Correll et al.(2009a)],per-
and Control of Networked Robotic Systems
forming pick-up and delivery tasks in a warehouse and guiding people in a shop-
ping mall [Shiomi et al.(2009)].Soccer-playing robots,which exemplify tightly
coordinated distributed sensing and actuation are treated in Chapter??.
3.2 Architecture:Communication and Localization
This section provides an overview over different communication technologies
commonly employed in networked robot systems including communication by
radio,light and sound as well as their fundamental properties.We then describe
mechanisms,algorithms and systems for mutual localization,which are an impor-
tant component of every networked robot systemas it allows themto reason and
coordinate spatially.
3.2.1 Communication
Two robots can communicate if they both are within a certain distance of each
other,leading to a disc model for communication in its most abstract form.This
model emerges from the assumption that the power of a signal that is traveling
from location p
to position p
fades exponentially with distance,approximately
following an Eq.[Chen and Kobayashi (2002)] of the form
− p
∥)[dBm] = P(r
)[dBm] −10α log
− p

e P(r
) is the reference power at distance r
from the emitter,and α is the
path loss exponent which is constant and a function of the environment.While the
exponent α is largely due to the so-called path-loss effect that corresponds to the en-
ergy lost while traveling through a mediumsuch as air or water,real radios are also
subject to multi-path fading,which is not reﬂected in Eq.3.1.Due to the uniform
emission of radio waves fromthe antenna and reﬂection of the signal fromobjects
in the environment,the actual signal will arrive via multiple paths.The resulting
interference can either be constructive or destructive,i.e.the overall amplitude is
increased when waves are in phase or decreased when waves are out of phase.
Thus,the multi-path effect is a small-scale effect that can be observed for variations
in distance that are in the order of a wavelength and small variations in position of
sender and receiver can drastically change the perceived signal strength.This phe-
nomenon can also be exploited to actively improve signal strength by exploring
various nearby locations,which has been demonstrated in [Lindh´e et al.(2007)].
The combined large-scale and smale-scale effects lead to a power density distribu-
tion quite different froma disc with uniformdistribution.Experimental results in
quasi-ideal experimental conditions,recorded using an unmanned aerial vehicle
(UAV) in a radio-free zone on a mesa in the Colorado prairie,is shown in Fig.3.5.
[Frew and Brown (2008)].The reader is referred to [mos (2009)] for a comprehen-
sive overviewon wireless signal propagation models in a robotic’s context,includ-
ing models that consider large-scale fading due to obstacles in the environment.
The obtainable signal strength S together with the background noise N now
Architecture:Communication and Localization
3.5.Left:Effective transmission power recorded by an UAV experiment in a “radio-free-zone”
courtesy of Eric Frew ([Frew and Brown (2008)]).Right:Absorption coefﬁcient of water from [Stomp
et al.(2007)].Absorption is lowest in the visual spectrum (super-imposed) and for very low frequen-
cies with wavelengths in the order of meters (not shown).Adapted by permission from Macmillan
Publishers Ltd:Nature,[Stomp et al.(2007)],copyright 2007.
governs the maximum throughput that can be obtained,which is known as the
Shannon-Hartley theorem.The Shannon-Hartley theoremprovides an upper bound
on the capacity C of an analog channel
C = Blog
(1 +
) (3.2)
with B the
bandwidth of the channel in Hertz,S the total received signal power
over the bandwidth measured in Watt,and N the total noise over the bandwidth
measured in Watt.Notice that bandwidth here refers to the actual frequency band
in which the signal operates.The ratio S/N is also known as the signal-to-noise
ratio.As S decreases while N remains constant with increasing distance,the ef-
fective communication range is limited by the desired capacity of the channel.In
practice modern wireless protocols therefore automatically switch data rates based
on the perceived signal-to-noise ratio and thus trade-off effective range with avail-
able channel capacity.For further information on the physical principles behind
path-loss and environment-speciﬁc models for radio communication the reader is
referred to [Seybold (2005)].
At a higher level,the reliability of communication (whether it be radio,light or
sound) is a function of the number of transceivers sharing the same channel and
the chosen channel access protocol and collision mitigation mechanisms,which is
beyond the scope of this chapter and the reader is referred to [Tanenbaum(2002)].
Assuring reliable communication in a multi-robot system,where transceivers often
have to compete with static infrastructure communicating on the same channel is
a major challenge both in robotics and in systems research. Radio
Trends in radio communication in networked robot system are highly correlated
with those in the personal computer industry,due to the easy availability of hard-
ware and software as well as the lowprice of a mass-market product.Particularly
noteworthy fromthis perspective are IEEE 802.11g (wireless LAN) and Bluetooth.
and Control of Networked Robotic Systems
The IEEE 802.11g standard,which was introduced in 2003,supports a set of dis-
crete data rates between 6 and 54 Mbit/s,which can be automatically chosen as
a function of the perceived signal-to-noise ratio (see above),allowing commodity
radios to communicate over distances of 300 m in open space.802.11g radios are
also available as USB sticks,Compact Flash,and SD cards,as well as as so-called
system-on-a-chip that combine the radio transceiver with a powerful MIPS proces-
sor in a single package,enabling stand-alone Wiﬁ systems using embedded Linux,
e.g.OpenWRT,for a fewdollars and the size of a credit card,see also [Correll et al.
(2009b)] for a robotic system using such hardware.Using IEEE 802.11g has the
advantage that standard networking protocols,such as TCP and UDP,and tools,
such as mesh-networking routing protocols,are readily available,although at cost
of a relatively high power consumption of 2 to 4 W.
Low-power alternatives to IEEE 802.11b are Bluetooth (IEEE 802.15.1) and Zig-
Bee (IEEE 802.15.4 deﬁning the physical and mediumaccess control layer),which
also operate at up to 2.4 GHz,although providing much lower data rates and
ranges.Due to the large variety of Bluetooth devices and ongoing evolution of
the standard,Bluetooth transceivers can provide ranges from1 to 100 mand data
transfer rates ranging fromhundreds of kbps to tens of MBs.ZigBee radios operate
in the range of 250 kbit/s per channel in the 2.4 GHz band,40 kbit/s per channel in
the 915 MHz band,and 20 kbit/s in the 868 MHz band.(The 2.4 GHz band is only
available in Europe,whereas ZigBee transceivers for the US market operate in the
868 and 915 MHz bands.) Transmission range is between 10 and 75 meters.Open-
source schematics of Bluetooth and Zigbee implementations are available for the
E-puck robot
,and ZigBee solutions have been integrated as small as 2 cmx 2 cm
in [Correll and Martinoli (2009)].
A major drawback of Bluetooth for networked robot applications is its lim-
itation to communicate with only 7 devices at a time in a master-slave hierarchy
calleda piconet,whereas mesh-networking stacks are available for ZigBee andhave
been used to network a swarmof quad-rotor helicopters in [Julian et al.(2009)]. Communication using Light
Communication using light,speciﬁcally in the infra-red part of the spectrum,has
found wide-spread application especially in miniature robotics due to its relatively
simple implementation,low cost,availability of peripherals such as remote con-
trols,and its potential for being multiplexed as a distance sensor.For instance the
miniature robot Alice [Caprari and Siegwart (2005)] uses its infra-red distance sen-
sors for directed infra-red communication up to 6 cm and data rates up to 4 Bps
and has the capability to receive commands froma conventional TV remote using
an additional receiver mounted on its top.Although light also provides higher
data rates with an appropriate coding scheme,e.g.the IrDA standard that was
popular on notebooks in the 90ies supported up to 16MBit/s,light is rarely used
for communication in networked robots as it requires a clear line-of-sight and is
cross-sensitive to sunlight.Advantages of light-based communication are when
the directional properties are actually desired,for example when used as a rela-
Architecture:Communication and Localization
range and bearing device (Sec.3.2.2),or when robots need to communicate
in a mediumthat strongly absorbs radio waves such as water (see Fig.3.5.for the
frequency-dependent absorption properties of water).Here,blue and green light
yield the best possible range [Doniec et al.(2009)],depending on the actual water
color. Communication using Sound
Sound is unlike light and radio not an electro-magnetic,but a pressure wave.Al-
though sound is also subject to multi-path fading and attenuation,sound waves
travel at only around 300 m/s as opposed to 300.000 km/s,making signal propa-
gation time a serious concern.Also,due to the lowfrequency that is feasible using
sound (fromthe audible spectrumin the order of Hz to thousands of kHz in ultra-
sound),the achievable data rate is intrinsically limited.Therefore,communication
using sound is of little importance in networked robot systems except for special-
ity applications such as range and bearing (Sec.3.2.2),human-robot interaction
and underwater communication.
3.2.2 Mutual Localization
Communication abilities are crucial for localization.Be it by receiving and tri-
angulating position information from Global Positioning System Satellites or by
exchanging range and bearing information with neighboring robots.This chap-
ter focusses on mutual localization,i.e.the capability of robots to localize each
other relative to each other.Mutual localization is a key capability of a networked
robotic system,as it allows it to reason and communicate about spatial data.Lo-
calization using communication devices works using two fundamentally different
approaches,time-of-ﬂight measurement and fading.This section focusses on ar-
chitectures for achieving relative range and bearing using sound,light and radio
in water and air.In a networked robot setup mutual observations can be further
reﬁned by sharing observations within the team,which allows for improved accu-
racy by sensor fusion [Howard et al.(2003)]. Localization using Sound
Localization using non-audible sound,e.g.Sonar,usually relies on the time-of-
ﬂight of a signal,and can be used for both mutual localization as well as collision
avoidance.As mutual localization using sound requires synchronized clocks,mu-
tual localization using sound is usually achieved in conjunction with some other
form of radio communication,which is emitted simultaneously and serves as a
reference event.The actual distance between two robots is then calculated using
the time-of-ﬂight,but bearing can only be estimated by triangulating distance in-
formation from multiple neighbors [Nagpal et al.(2003)].An implementation of
this idea is the Cricket localization system [Priyantha et al.(2000)] that has found
wide-spread use in localizing miniature robots.However,localization using sound
alone is uncommon in networked robot systems,except in underwater systems
due to the absorption coefﬁcient of water discussed above (see also Chapter??).
and Control of Networked Robotic Systems
Also,sound-based time-difference-of-arrival systems are prone to interferences
from neighboring devices,in particular when the sound pulses are not encoded
with information.For instance,in [Kottege and Zimmer (2008)] a system for un-
derwater range and bearing estimation is presented that relies on sound emissions
from a pair of projectors,which is received by a pair of hydrophones.Here,a
longwave radio is used together with a scheduling algorithm[Schill and Zimmer
(2007)] to ensure that only one AUV is broadcasting sound at a time in a local
neighborhood.Similar to the Cricket system,the radio signal is also used as syn-
chronization event for the time-of-ﬂight calculation. Localization using Infrared
Localization using infra-red is attractive for small-scale robot systems as it can be
implemented on very small footprints (see also Chap.??),uses little power,and
its intensity is strongly distance and direction related.For instance the Alice robot
[Caprari and Siegwart (2005)],encodes its 4-bit unique identiﬁcation number and
the bearing of the originating transceiver into messages,which allows robots to
identify a neighboring robot,estimate its distance,andcalculate its relative bearing
as well as the bearing of the other robot.A more capable systemhas been imple-
mented for the e-puck robot,providing 5kbps communication,1 cmin range and
in bearing at distances belowone meter and is available open-source [Gutierrez
et al.(2008)]. Localization using Radio
The proliferation of wireless radios on robots has made using radio for mutual lo-
calization popular.Challenges of this approach are the strong spatial dependence
of the perceived signal strength (see also Fig.3.5.) as well as the fact that radio
antennas employed for communication are usually omnidirectional and thus do
not allow to infer the direction of a signal.While multiple techniques exist to lo-
calize a mobile robot using static infra-structure [Bahl and Padmanabhan (2000)],
this chapter focusses on mutual localization of robots without relying on infras-
tructure in the environment.While localization techniques relying on sound and
light have found widespread use,localization only using radio is still in its infancy.
So far,algorithms rely solely on the large scale fading effects which lead to a re-
duced Radio Signal Strength Indication (RSSI) for growing distance and that can
be measured using commodity hardware.Due to the strongly non-linearities of
the effects underlying the perceived RSSI,distance estimates are crude and bear-
ing estimates relying on a single measurement are impossible.In fact,multi-path
fading effects can only be canceled out by actively moving around in the order
of a wave-length.Only then,RSSI values can be averaged to give a crude esti-
mate of range (see also [Lindh´e et al.(2007)]).Dantu and Sukhatme [Dantu et al.
(2009)] present an algorithm to estimate the bearing of a neighboring robot per-
forming multiple measurements (in the order of hundred) on 8 locations lying on
a circle with multiple meters diameter (2–5 m).By performing a principle com-
ponent analysis (PCA) of the covariance matrix of these measurements,the ﬁrst
Modeling and Control of Networked Robot Systems
of the covariance matrix lies along the direction with the highest vari-
ance and thus corresponds to the bearing of the other robot.Using this approach,
they show measurements that are around 20
accurate in bearing.For improv-
ing upon these results —which take multiple minutes to acquire and require the
other robot to remain static —[Dantu et al.(2009)] suggests to exploit small-scale
effects as demonstrated in [Kusy et al.(2007);Maroti et al.(2005)],which require
less motion to gather.Another promising direction is to use MIMO transceivers
with multiple antennas that have been originally designed to increase bandwidth
by spacedomain-multiplexing (beam-forming),which is an effect that can natu-
rally lead to an accurate bearing estimate.Similarly,localization using ultra-wind
band coding is of potential interest for the networked robotics community as it is
less susceptive to multi-path fading;Commercial systems that achieve 30cm ac-
curacy in 3D over up to 160m using this technology are available from Ubisense
Inc.although require at least two static sensors to pick up the signal of an active
transmitter for triangulation.
3.3 Modeling and Control of Networked Robot Systems
dination paradigms for networked robot systems can be classiﬁed into re-
active,deliberative and hybrid approaches,where hybrid approaches consist
of deliberative algorithms —in the simplest formimplemented by simple dis-
crete logic —that switches between different continuous,reactive dynamics.
all deliberative mechanisms are strictly speaking hybrid when im-
plemented on a robotic platform involving any sort of feedback control,e.g.for
motor control,a common assumption in deliberative systems is to abstract the dy-
namic aspects of the system away and to plan using a discrete representation of
the environment.
The choice of the control architecture drastically inﬂuences the performance of
the overall systemas well as what can be said about a systemanalytically.As a rule
of thumb,performance increases with the amount of deliberation and coordination
within the team.At the same time,deliberative algorithms that abstract the contin-
uous dynamics of the individual agents usually allow for making stronger guar-
antees on optimality and completeness.For instance,reactive systems are usually
shown to converge to a local minima but cannot guarantee optimality,whereas
an exhaustive search on a discrete state space can do so.The ﬂip side,however,
is that deliberation and coordination require sensing and communication abilities
that might be technically infeasible in a speciﬁc domain.For instance,micro-robots
such as the i-Swarmrobot (Fig.3.1.,left) will require reactive coordination due to
computational,sensing,and communication limitations,whereas the Linux-based
Khepera robot (Fig.3.1.,right) has the ability to reason on fast amounts of data.
As the performance is intrinsically limited by the quality of sensing and commu-
nication —which serves as the basis for deliberation —hardware capabilities are
in fact the limiting factor on performance and ﬁnding the right trade-off between
and Control of Networked Robotic Systems
systemcomplexity and resulting performance remains an interesting challenge.
3.6.Left:Reactive,hybrid and deliberative approaches can be loosely classiﬁed by the amount
of coordination and deliberation that they use.More coordination and deliberation will usually lead
to improved performance,but comes with increased requirements on sensing,computation,and com-
munication.Right:Performance (time to completion) of a distributed coverage task using a series of
deliberative algorithms with increasing communication and computational complexity [Correll and
Martinoli (2009)].Whereas providing global localisation and communication drastically increases per-
formance (from DCWL to DCL),near-optimal coordination using a market-based algorithm (MCR)
provides relatively small gain for massively higher communication and computation requirements as
the theoretically possible speed-up cannot be achieved with the limited sensors and actuators of the
The relation between planning,coordination,and performance with respect to
reactive,deliberative and hybrid coordination approaches is also showin Fig.3.6.,
left.Fig.3.6.,right,illustrates the trade-off between system complexity and per-
formance using data froman experiment in multi-robot coverage that is described
in [Correll and Martinoli (2009)].A team of 5 robots needs to cover (visit at least
once) an environment that is discretized into a 5x5 grid using different delibera-
tive algorithms.Performance increases consistently when augmenting simple in-
dividual planning (DCWL) by exchanging information on task progress within
the team(DCL) [Rutishauser et al.(2009)],and by market-based allocation (MCR)
of tasks based on a global metric [Amstutz et al.(2009)].Performance improve-
ments come at considerable cost,however:whereas exchanging information on
task progress requires global localization and communication to improve upon a
non-collaborative policy,up-front allocation of tasks requires orders of magnitude
more computation as the allocation problemis NP-hard [Amstutz et al.(2009)].In
addition,the effective performance increase is well below the theoretical expecta-
tion due to limited actuator accuracy (wheel-slip) of the Alice platform.Therefore,
the DCL approach might be an optimal trade-off between performance and system
complexity for this particular system.
Modeling and Control of Networked Robot Systems
3.3.1 Modeling
and Control of Reactive Systems
approaches are either described implicitly by heuristics that eventu-
ally lead to the desired behavior,but do not lead to analytically tractable trajec-
tories,or explicitly as distributed control law on a global cost function,which
allows to prove properties such as convergence and stability analytically.
simplest reactive controllers implement a direct mapping between the sen-
sors and the actuators of a robot and are known as Braitenberg vehicles.For this
kind of controllers,sensors can also include communication devices,and they can
be best formally described by artiﬁcial potential ﬁelds [Arkin (1998)] or virtual
physics [Spears et al.(2005)].Both approaches rely on the assumption that a reac-
tive controller accurately tracks a vector ﬁeld in the environment.The magnitude
and direction of these vector ﬁelds are a function of local sensing and communica-
tion.Formally,the vector ﬁeld can be described as a cost function J,leading with
the position of robot i to the feedback control law
= −
Different objectives,such as collision avoidance or tracking a desired shape,of a
robot can be overlaid,i.e.summed up in the cost function.For example,collision
avoidance between robot i and j that have distance r
is commonly (e.g.,[Mosh-
tagh et al.(2009)]) encoded as

| (3.4)
where d
is the desired distance between the robots and resulting in the gradient




This leads to a control lawof the form
= −k∇
) −

) (3.6)
with ϕ
) a location and communication dependent artiﬁcial potential ﬁeld,k
a proportional gain,and G
the set of neighbors of robot i.
Using a Lyapunov-style proof to show that lim
˙x → 0,often only for the
components of the controller tracking the global metric of interest,one can then
showthat the systemeventually reaches a local optimumof J.
For instance,[Schwager et al.(2009b)] derives a decentralized,adaptive con-
trol law to drive a network of mobile robots to an optimal sensing conﬁguration
(Fig.3.7.).The control lawis adaptive in that it uses sensor measurements to learn
the distribution of sensory information in the environment.It is decentralized in
that it requires only information local to each robot.The controller is then im-
proved by introducing a consensus algorithm to propagate sensory information
fromevery robot throughout the network.Convergence and consensus of param-
eters is proven with a Lyapunov-type proof.The controller with and without con-
sensus is demonstrated in numerical simulations.These techniques are suggestive
and Control of Networked Robotic Systems
3.7.Instances of networked robots that are coordinated by purely reactive,gradient-based
controllers.A robot swarmfor optimal coverage of a sensory function on the ground (left,[Schwager
et al.(2009b)]),in the air (middle,[Schwager et al.(2009a)]),and tracking a desired shape [Chaimowicz
et al.(2005)].The spatio-temporal behavior of these examples is exclusively governed by an artiﬁcial
potential ﬁeld and is achieved without any discrete state transitions on robot and teamlevel.
of broader applications of adaptive control methodologies to decentralized control
problems in unknown dynamic environments.
Other applications that have successfully been encoded using a global cost
function with a provably convergent feedback control law are ground coverage
using aerial cameras [Schwager et al.(2009a)] (Fig.3.7.,middle),assembly of truss
structures [Yun et al.(2009)],tracking of global formations [Chaimowicz et al.
(2005);Hsieh et al.(2008b)] (Fig.3.7.,right),and connectivity maintenance in a
networked robot system,[Hsieh et al.(2008a)],among others.The main challenges
with this approach are choosing a cost function that is convex with respected to
the desired ﬁnal conﬁguration of the robotic system,i.e.lends itself to a feedback
controller that controls a robot’s trajectory,and actually showing its convergence.
Another challenge with gradient-based approaches is the fact that usually only
convergence to a local optima can be proven,but not the degree of optimality that
this solution will achieve in the worst case.
3.3.2 Modeling and Control of Hybrid Systems
As soon as the dynamics of a robot contains discrete logic that let it switch be-
tween different continuous behaviors,we speak of a hybrid system.Early hybrid
controllers are the subsumption architecture [Brooks (1986)] where various reac-
tive behaviors subsume each other as a function of sensor input and the state of
the robot.While the subsumption architecture allows for implementing complex
behaviors with a minimumof computation,designing controllers is often difﬁcult
as the resulting behavior is emergent,in particular due to non-linear interaction
with other robots in the team.
Given a set of reactive robot controllers,each associatedwith a state q ∈ Q,with
Q a set of states,the robot controller can be described by Finite State Automaton
(FSA) that consist of a 5-tuple (Q,S,δ,q
• Q is a ﬁnite set of states
• S is a ﬁnite set of input symbols
• δ:QxS →S a transition function
Modeling and Control of Networked Robot Systems
• q
∈ Q the
initial state
• F a set of ﬁnal states
3.8.Instances of networked robots with hybrid reactive-deliberative controllers.Autonomous
deployment of wireless infrastructure ([Correll et al.(2009b)],left),distributed manipulation ([Martinoli
et al.(2004)],middle),and inspection of regular structures ([Correll and Martinoli (2006a)],right).The
spatio-temporal behavior of each of these systems is generated fromthe interplay of reactive controllers
and discrete state transitions at the individual controller level.
For instance,in the Stick-pulling experiment where a swarm of robots is con-
cerned with pulling sticks out of the ground and two robots are needed to success-
fully complete the task [Martinoli et al.(2004)] robots can be searching the arena
for a stick,avoiding other robots,pulling the stick,waiting for collaboration,and
completing the pull-out action in case a second robot joins them at their site.All
of these are discrete states of a FSA that are associated with continuous dynam-
ics such as randomly exploring the arena,avoiding other robots,or activating the
robot’s gripper.Input symbols of this system are events such as detection of a
stick,detection of a robot,or detection of another robot pulling on the stick,which
eventually lead to state transitions.
If the input symbols are probabilistic,this automaton reduces to a Markov
chain.Common assumptions are that the likelihood that a robot encounters sym-
bol σ ∈ S is p
,and the likelihood of the robot to be in state q is p
(kT),with k a
discrete time-step of the system with length T.This leads to the Master equation
that describes the likelihood to be in state q at time kT as
(kT +T) = p
(kT) +


(kT +T)p
′ (kT) − p
′ (kT)p
(kT)) (3.7)
with p

(kT +T) ∈ δ the conditional probability to transition fromstate q

to state
q [Correll (2007)].
Given Nrobots in the system,the Master equation leads itself to a rate equation
with N
(kT) describing the average number of robots in state q:
(kT) = Np
(kT) (3.8)
It turns out that the rate equation model (see also [Lerman et al.(2005)]) is a
powerful tool to study the collective behavior of a hybrid networked robot sys-
tem.For instance in [Martinoli et al.(1999)] and [Martinoli et al.(2004)] rate equa-
tion models have shown to provide qualitative and quantitative agreement with
experimental studies in which swarms of robots aggregated pucks in an arena and
collaboratively pulled sticks out of the ground,respectively.Similarly,[Correll
and Martinoli (2007)] demonstrates quantitative agreement between rate equation
and Control of Networked Robotic Systems
models and a simulated swarm-robotic aggregation task,and [Correll and Marti-
noli (2009)] provides an accurate model of a inspection task with a swarmof up to
40 miniature robots.Other examples include aggregation of sticks [Agassounon
et al.(2004)] or coalescence of networked robot swarms [Winﬁeld et al.(2008)]
where macroscopic equations provide a close match with simulation results.
Rate equation models can not only predict the population dynamics of the net-
worked robot swarm,but can also be used to optimize its control parameters.In
[Martinoli et al.(2004)] the rate equation model is used to estimate the optimal
waiting time in the Stick-Pulling experiment and also predicts a bifurcation in the
systemwhen there are more robots than sticks (a case which supports inﬁnite wait-
ing time without starvation).In [Correll and Martinoli (2006c)] rate equation mod-
els are used with a dynamic optimal control framework to ﬁnd optimal collabora-
tion policies in a swarm-robotic inspection experiment and a task allocation case
study [Correll (2008)].
Key challenges with this approach are stability of the rate equation systems,
in particular for large numbers of possible interactions between robots —which
lead to non-linear rate equations with strong coupling,and the inability of the
rate equation approach to capture rare events that have signiﬁcant impact on the
robotic system.Also,deriving the probabilities for state transitions in the system
fromgeometric properties of the environment and the robot controller is often in-
feasible.Here,systemidentiﬁcation [Correll and Martinoli (2006b)] is a promising
direction.Finally,the rate equation approach encounters difﬁculties with system
that have rare events that lead to drastic changes in the systembehavior,which are
better captured by stochastic modeling techniques such as Monte-Carlo simula-
tion.See also Section??of this book for an overview over rate equation-based
models including case-studies on object clustering and collaborative decision-
A different approach to modeling and control of hybrid systems is to describe
the discrete automaton and possible transitions between states using temporal
logic speciﬁcations [Kloetzer and Belta (2010)].This approach allows to separate
the continuous dynamics (given by the robot’s motion) of each state fromthe dis-
crete dynamics of state evaluation,and allows to leverage tools fromformal veri-
ﬁcation to prove properties of the system.
3.3.3 Modeling and Control of Deliberative Systems
A networked robotic systemreasons on a state-space representation that is exclu-
sively discrete.This is possible when the continuous robot dynamics and the com-
munication dynamics are neglible,i.e.operating with high reliability.For instance,
the KIVA warehouse robots (Fig.3.4.,middle) are coordinated on a grid-like en-
vironment where robots move fromcenter to center on a chessboard-like arrange-
ment.Using markers on the ﬂoor,the robots are able to localize with high accuracy
in a global coordinate system,which gives themthe ability to move fromcell to cell
with a high reliability.By this the multi-robot systemreduces to a centralized plan-
ning systemon a grid,which can be analyzed with classical tools fromalgorithm
analysis [Cormen et al.(2009)].For instance the shortest path for a robot fromone
Challenges in Networked Robotic Systems
to the other could be calculated using Dijkstra’s algorithm,and for N robots,
collision free paths can be calculated in R
space [Everett et al.(1994);Parsons and
Canny (1990)].Due to the high-level of abstraction in deliberative planning sys-
tems,the multi-robot coordination problembecomes accessible to a wide range of
methods from distributed algorithms that can provide provable correct solutions
to resource allocation,consensus among distributed processes,data consistency,
deadlock detection,leader election,among others [Lynch (1996)].
Deliberative algorithms fail,however,when the underlying continuous dy-
namics prove unreliable,and often times loose their analytical tractability when
improved by backup mechanisms that take possible robot failure into account (see
also [Parker (1998)] and Chap.??of this book).For instance in [Rutishauser et al.
(2009)] a teamof networked robots coordinates wirelessly to cover a grid-like envi-
ronment.Robots have the ability to localize andexchange information on coverage
progress.Using the Dijkstra algorithm,each robot calculates paths to the closest
uncovered cell on the grid.As communication,navigation,and localization are
unreliable the systemhas the following failure modes:coverage is redundant be-
cause robots fail to communicate,robots arrive late because they fail to navigate,
and robots exchange false information due to errors in localization.The algorithm
has therefore been adopted to maintain a probabilistic coverage map of the envi-
ronment and have robots move towards the closest cell with the lowest likelihood
of having been covered.[Rutishauser et al.(2009)] also shows how quantitative
correct predictions of the systembehavior can be obtained by calibrating the prob-
ability distributions of each failure mode.
As also the slightest uncertainty when executing a deliberative algorithmmight
break the system,veriﬁcation of networked systems with stochastic subsystems
(e.g.communication or actuation) is therefore a key challenge.
3.4 Challenges in Networked Robotic Systems
The science of networked robot systems lies at the intersection of mobility,con-
trol,and communication.Work focussing exclusively on control often has strong
assumptions on the perception and communication abilities as well as their re-
liability.Recent advances in high-speed 6-DOF tracking,small holonomic aerial
vehicles,and high-speed communication have enabled real-robot demonstrations
of powerful formal approaches for formation control,collective motion and cov-
erage,albeit relying on considerable infrastructure to overcome the limitations of
on-board sensing (e.g.[Michael et al.(2009)]).On the other end of the spectrumare
algorithms that are designed to explicitly deal with sensor and actuator noise by
using randomapproaches (e.g.[Martinoli et al.(2004)]) or deliberative approaches
that gracefully degrade to a randomized solution under inﬂuence of noise (e.g.
[Amstutz et al.(2009)]).In order to bring these two orthogonal approaches to-
gether,we require for one methods to provide formal,probabilistic guarantees
that allow to express systemperformance as a function of sensor and actuator re-
liability,and for another robust feedback controllers which stability is expressed
as a function of sensor accuracy,actuator reliability,and communication rate.See
and Control of Networked Robotic Systems
also Section??of this book.
A promising application for networked robot systems is sensor coverage con-
trol,i.e.exploiting mobility for increasing the resolution of a sensor network.This
ﬁeld is maturing rapidly and solutions that are provably convergent and adaptive
have been demonstrated on real robotic systems (e.g.[Schwager et al.(2009b)]).
Few research has focussed on networked robot systems that can actively modify
the environment based on sensor input.An instance of such a system is the dis-
tributedrobotic garden where robots respondto watering requests of plants nested
in sensing and communicating pots and thus create a feedback loop with the en-
vironment.In the future,such systems will need to combine identiﬁcation of the
underlying environmental model based on sensing with distributed control that
can drive the systemin a speciﬁc desired state.
Accurate mutual localization remains a key challenge.Current solutions rely-
ing on sound and light are susceptible to disturbance to cross-sensitivity and re-
quire substantial hardware investments,whereas radio-based and GPS-based sys-
tems lack the accuracy and bandwidth that allows for tight coordination.Promis-
ing directions are beam-forming MIMOantennas and small signal analysis.Before
beam-forming antennas are wide-spread available,however,currently available
systems that require mechanical rotation of a narrowbeamantenna are bulky and
(2009).Characterization and modeling of wireless channels for networked robotic and con-
trol systems —a comprehensive overview,in Proc.of the Int.Conf.on Intelligent Robots
and Systems (IROS) (St.Louis,MO).
Agassounon,W.,Martinoli,A.and Easton,K.(2004).Macroscopic modeling of aggrega-
tion experiments using embodied agents in teams of constant and time-varying sizes,
Auton Robot 17,2-3,pp.163–192.
Amstutz,P.,Correll,N.and Martinoli,A.(2009).Distributed boundary coverage with a
team of networked miniature robots using a robust market-based algorithm,Annals
of Mathematics and Artifcial Intelligence.Special Issue on Coverage,Exploration,and Search
Arkin,R.(1998).Behavior-Based Robotics (The MIT Press).
Bahl,P.and Padmanabhan,V.(2000).RADAR:An in-building RF-based user location and
tracking IEEE Infocom,Vol.2,pp.775–784.
Bhadauria,D.and Isler,V.(2009).Data gathering tours for mobile robots,in Proceedings of the
International Conference on Intelligent Robots and Systems (IROS) (St.Louis,MO,USA).
Brooks,R.A.(1986).A robust layered control system for a mobile robot,IEEE Journal of
Robotics and Automation RA-2,1,pp.14–23.
Caprari,G.and Siegwart,R.(2005).Mobile micro-robots ready to use:Alice,in Proc.of the
pp.3295– 3300.
Chaimowicz,L.,Michael,N.and Kumar,V.(2005).Controlling swarms of robots using
interpolatedimplicit functions,International Conference on Robotics,pp.2487 – 2492doi:
Chen,Y.and Kobayashi,H.(2002).Signal strength-based indoor geolocation,in IEEE Inter-
national Conference on Communicatins,Vol.1,pp.436–439.
Choi,J.,Lee,J.,Xu,Y.and Oh,S.(2010).Navigation strategies for swarmintelligence using
spatio-temproal gaussian processes,Special issue on Swarm Robotics,Neural Computa-
tion and Applications To appear.
Cormen,T.,Leiserson,C.,Rivest,R.and Stein,C.(2009).Introduction to Algorithms,Third
Edition (MIT Press).
Correll,N.(2007).Coordination schemes for distributed boundary coverage with a swarmof minia-
ture robots:synthesis,analysis and experimental validation,Ph.D.thesis,Ecole Polytech-
nique Federale de Lausanne (EPFL).
Correll,N.(2008).Parameter estimation and optimal control of swarm-robotic systems:A
case study in distributed task allocation,Proc.of the 2008 IEEE Int.Conf.on Robotics
and Automation (ICRA 2008),pp.3302 – 3307.
Soltero,D.,Tanner,M.,White,L.and Rus,D.(2009a).Building a distributed robot
garden,in IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)
Correll,N.and Martinoli,A.(2006a).Collective inspection of regular structures using a
swarm of miniature robots,in M.H.A.Jr.and O.Khatib (eds.),Proc.of the Ninth
Int.Symp.on Experimental Robotics (ISER),Springer Tracts in Advanced Robotics,Vol.21
Correll,N.and Martinoli,A.(2006b).System identiﬁcation of self-organized robotic
swarms,in 8th International Symposium on Distributed Autonomous Robotic Systems
Correll,N.and Martinoli,A.(2006c).Towards optimal control of self-organized robotic in-
spection systems,in In 8th International IFAC Symposium on Robot Control (SYROCO)
Correll,N.and Martinoli,A.(2007).Modeling self-organized aggregation in a swarm of
miniature robots,in Proc.of the IEEE 2007 International Conference on Robotics and Au-
tomation Workshop on Collective Behaviors inspired by Biological and Biochemical Systems.
Correll,N.and Martinoli,A.(2009).Multirobot inspection of industrial machinery,IEEE
Robotics &Automation Mag.16,1,pp.103 – 112.
Correll,N.,Rus,D.,Bachrach,J.and Vickery,D.(2009b).Ad-hoc wireless network coverage
with networked robots that cannot localize,in IEEE International Conference on Robotics
and Automation (Kobe,Japan),p.8 pages.
Dantu,K.,Goyal,P.and Sukhatme,G.S.(2009).Relative bearing estimation from com-
modity radios,in IEEE International Conference on Robotics and Automation (IEEE),pp.
Doniec,M.,Vasilescu,I.,Detweiler,C.,Rus,D.,Chitre,M.and Hoffmann-Kuhnt,M.(2009).
Aquaoptical:A lightweight device for high-rate long-range underwater point-to-
point communication,in In Proceedings of OCEANS,pp.papernumber 090601–157.
Estrin,D.,Govindan,R.,Heidemann,J.and Kumar,S.(1999).Next century challenges:
scalable coordination in sensor networks,in Proceedings of the 5th annual ACM/IEEE
international conference on Mobile computing and networking,pp.263–270.
Everett,H.R.,Gage,D.W.,Gilbreath,G.A.,Laird,R.T.and Smurlo,R.P.(1994).Real-world
issues in warehouse navigation,in Proceedings of the SPIE Conference on Mobile Robots
IX,Vol.2352 (Boston,MA),pp.629–634.
Frew,E.W.andBrown,T.X.(2008).Airborne communication networks for small unmanned
aircraft systems,Proceedings of the IEEE,Special Issue on Aviation Information Systems 96,
Gurdan,D.,Stumpf,J.,Achtelik,M.,Doth,K.,Hirzinger,G.and Rus,D.(2006).Energy-
efﬁcient autonomous four-rotor ﬂying robot controlled at 1khz,in The 2006 Interna-
tional Conference on Robotics and Automation.
Madrid,S.(2008).An open localisation and local communication embodied sensor,
Sensors 8,pp.7545–7563.
Hauert,S.,Zufferey,J.-C.and Floreano,D.(2009).Evolved swarming without positioning
information:an application in aerial communication relay.Autonomous Robots 26,pp.
Howard,A.,Matari´c,M.J.and Sukhatme,G.S.(2003).Putting the ‘i’ in ‘team’:An
ego-centric approach to cooperative localization,in IEEE International Conference on
Robotics and Automation (Taipei,Taiwan),pp.868–892,URL http://cres.usc.
d,A.,Parker,L.and Sukhatme,G.(2006).Experiments with a large heterogeneous
mobile robot team:Exploration,mapping,deployment and detection,Int.J.Robotics
Research 25,5-6,pp.431–448.
Hsieh,M.,Cowley,A.,Kumar,V.and Taylor,C.(2008a).Maintaining network connectivity
and performance in robot teams,Journal of Field Robotics 26,1–2,pp.111–131.
Hsieh,M.,Kumar,V.and Chaimowicz,L.(2008b).Decentralized controllers for shape gen-
eration with robotic swarms,Robotics 26,5,pp.691–701.
Julian,B.,Schwager,M.,Angermann,M.and Rus,D.(2009).Alocation-based algorithmfor
multi-hopping state estimations within a distributed robot team,in Proceedings of the
7th International Conference onField and Service Robotics (FSR 09) (Cambridge,MA).
Kloetzer,M.and Belta,C.(2010).Automatic deployment of distributed teams of robots from
temporal logic motion speciﬁcations,IEEE Transactions on Robotics 26,1,pp.48–61.
N.and Zimmer,U.(2008).Acoustical methods for azimuth,range and heading
estimation in underwater swarms,in Proceedings of Acoustics ’08,Palais des Congress,
Paris,France,29 June-4 July 2008 (Paris,France),p.5.
Kusy,B.,Sallai,J.,G.Balogh,A..L.,andJ.Tolliver,V.P.,DeNap,F.and Parang,M.(2007).
Radio interferometrictracking of mobile wireless nodes,inACMMobiSys,pp.139–151.
Lerman,K.,Martinoli,A.and Galstyan,A.(2005).Lect Notes Comput Sc 3342,pp.143–152.
Lindh´e,M.,Johansson,K.H.and Bicchi,A.(2007).An experimental study of exploiting
multipathfading for robot communications,in Proceedings of Robotics:Science and Sys-
tems,p.8 pages.
Lochmatter,T.and Martinoli,A.(2009).Experimental Robotics 11,Vol.54,chap.Tracking
Odor Plumes in a Laminar Wind Field with Bio-Inspired Algorithms,springer tracts
in advanced robotics edn.(Springer Verlag),pp.473–482.
Lynch,N.(1996).Distributed Algorithms (Morgan Kaufman).
Maroti,M.,Volgyesi,P.,Dora,S.,Branislav,K.,andA.Ledeczi,A.N.,Balogh,G.and Molnar,
K.(2005).Radio interferometric geolocation,in Proceedings of the 3rd internationalcon-
ference on Embedded networked sensor systems ACMSenSys,pp.1–12.
Martinoli,A.,Easton,K.and Agassounon,W.(2004).Modeling swarm robotic systems:A
case study in collaborative distributed manipulation,Int.J.Robot Res.23,4-5,pp.415–
Martinoli,A.,Ijspeert,A.and Mondada,F.(1999).Understanding collective aggregation
mechanisms:From probabilistic modelling to experiments with real robots,Robotics
and Autonomous Systems 29,1,pp.51–63.
Michael,N.,Fink,J.and Kumar,V.(2009).Cooperative manipulation and transportation
with aerial robots,in Proc.of Robotics:Science and Systems (Seattle,WA).
ferey,J.-C.,Floreano,D.and Martinoli,A.(2009).The e-puck,a robot designed for
education in engineering,inProc.9th Conference on Autonomous Robot Systems and Com-
Moshtagh,N.,Michael,N.,Jadbabaie,A.and Daniilidis,K.(2009).Vision-based,distributed
control laws for motion coordination of nonholonomic robots,IEEE Transactions on
Robotics 25,4,pp.851–860.
Nagpal,R.,Shrobe,H.and Bachrach,J.(2003).Organizing a global coordinate systemfrom
local information on an ad hoc sensor network,in International Conference on Informa-
tion Processing in Sensor Networks (IPSN).
Parker,L.E.(1998).ALLIANCE:An architecture for fault-tolerant multi-robotcooperation,
IEEE Transactions on Robotics and Automation 14,2,pp.220–240.
Parsons,D.and Canny,J.(1990).Amotion planner for multiple mobile robots,in Proc.IEEE
International Conference on Robotics and Automation,Vol.1,pp.8–13.
Priyantha,N.,Chakraborty,A.and Balakrishnan,H.(2000).The cricket location-support
system,in Proceedings of the 6th annual international conference on Mobile Computing and
Rudnick,D.L.,Davis,R.E.,Eriksen,C.C.,Fratantoni,D.M.and Perry,M.J.(2004).Under-
water gliders for ocean research,MarineTechnology Society Journal 38,1,pp.48–59.
Rutishauser,S.,Correll,N.and Martinoli,A.(2009).Collaborative coverage using a swarm
of networked miniature robots,Robotics &Autonomous Systems 57,5,pp.517–525.
Schill,F.and Zimmer,U.(2007).Pruning local schedules for efﬁcient swarm communica-
tion,in In Proc.of the IEEE International Symposium on Underwater Technology (UT ’07)
Schwager,M.,Julian,B.and Rus,D.(2009a).Optimal coverage for multiple hovering robots
with downward-facing cameras,in In Proc.of the International Conference of Robotics
and Automation (Kobe,Japan).
Schwager,M.,Rus,D.and Slotine,J.J.(2009b).Decentralized,adaptive coverage control for
networked robots,International Journal of Robotics Research 28,3,pp.357–375.
Seybold,J.S.(2005).Chapter 7:Near Earth Propagation Models,Vol.1 (John Wiley &Sons),pp.
Shiomi,M.,Kanda,T.,Glas,D.,Satake,S.,Ishiguro,H.and Hagita,N.(2009).Field trial
of networked social robots in a shopping mall,in Proceedings of the 2009 IEEE/RSJ
International Conference on Intelligent Robots and Systems (St.Louis,MO).
Spears,W.M.,Spears,D.F.,Heil,R.,Kerr,W.and Hettiarachchi,S.(2005).An overview
of physicomimetics,in Swarm Robotics,Lecture Notes in Computer Science,Vol.3342
Stomp,M.,Huisman,J.,Stal,L.and Matthijs,H.(2007).Colorful niches of phototrophic
microorganisms shaped by vibrations of the water molecule,The ISME Journal:Mul-
tidisciplinary Journal of Microbial Ecology 1,pp.271–282.
Tanenbaum,A.(2002).Computer Networks (Prentice Hall).
Vasilescu,I.,Varhavskaya,P.,Kotay,K.and Rus,D.(2005).Autonomousmodular optical
underwater robot (amour) design,prototype and feasibility study,in In Proceedings of
the International Conference on Robotics and Automation (ICRA) (Barcelona,Spain),pp.
Winﬁeld,A.,Liu,W.,Nembrini,J.and Martinoli,A.(2008).Modelling a wireless connected
swarmof mobile robots,SwarmIntell 2,2,pp.241–266.
Yun,S.,Schwager,M.and Rus,D.(2009).Coordinating construction of truss structures us-
ing distributed equal-mass partitioning,in Proc.of the 14th International Symposiumon
Robotics Research (Luzern,Switzerland).