arXiv:1312.2526v1  [cs.RO]  9 Dec 2013
Connectivity maintenance by robotic Mobile Ad-hoc NETwork
Vaibhav Kumar Mehta, Filippo Arrichiello
Abstract— The problem of maintaining a wireless communi-
cation link between a fixed base station and an autonomous
agent by means of a team of mobile robots is addressed in
this work. Such problem can be of interest for search and
rescue missions in post disaster scenario where the autonomous
agent can be used for remote monitoring and first hand
knowledge of the aftermath, while the mobile robots can be
used to provide the agent the possibility to dynamically send
its collected information to an external base station. To study
the problem, a distributed multi-robot system with wificommu-
nication capabilities has been developed and used to implement
a Mobile Ad-hoc NETwork (MANET) to guarantee the required
multi-hop communication. None of the robots of the team
possess the knowledge of agent’s movement, neither they hold
a pre-assigned position in the ad-hoc network but they adapt
with respect to the dynamic environmental situations. This
adaptation only requires the robots to have the knowledge of
their position and the possibility to exchange such information
with their one-hop neighbours. Robots’ motion is achieved by
implementing a behavioural control, namely the Null-Space
based Behavioural control, embedding the collective mission
to achieve the required self-configuration. Validation of the ap-
proach is performed by means of demanding experimental tests
involving five ground mobile robots capable of self localization
and dynamic obstacle avoidance.
I. INTRODUCTION
Multi-robot systems have received an increasing attention
in the last decades due to the advantages they present with re-
spect to a single robot in terms of fault tolerance, flexibility in
mission execution, and possibility to use distributed sensing
and actuation. The work [12] presents an overview on multi-
robot systems focusing on aspects like system architecture,
communication, task allocation, and applications; while the
work [11] deals with distributed intelligence issues and intro-
duces a classification based on exhibited interactions. Recent
researches in this field are mainly focused on distributed
and cooperative robotic systems [8], i.e., systems where each
robot interacts only with its neighbours and, together, they
generate the global behaviour of the team. The work [10]
presents an overview on networked robots, that is, multiple
robots that cooperate by network communication, and it
explores the research challenges due to the interaction among
control, communication and perception.
In the rescue robotics scenario, the use of a single robot
with a multitude of sensing capabilities has been studied
and practised at large. Currently most of the robots in the
search and rescue domain are human operated; while the
Vaibhav
Kumar
Mehta
is
a
graduate
student
at
the
School
of
Engineering
and
Science
of
Jacobs
University
Bremen,
Germany,
v.mehta@jacobs-university.de
F. Arrichiello is with the Department of Electrical and Information
Engineering, University of Cassino and Southern Lazio, Via G. Di Biasio
43, 03043, Cassino (FR), Italy, f.arrichiello@unicas.it
need of well-trained operator is sometimes a requirement
by the unpredictable conditions commonly found in disaster
sites (collapsed buildings, gaps, holes, flooding ...), this
limits the deployment of such robots readily. Even with
the availability of autonomous ones, in situations where
network capabilities are lacking the possible area to be
explored is drastically reduced. Thus, the use of distributed
networked robots make them very suitable for search and
rescue scenarios, extending the range of communication and
providing large scale surveillance at the same time. But
dealing with networked robots poses the challenging problem
of connectivity maintenance, i.e., performing autonomous
missions while keeping the communication network formed
by the robots/agents globally connected.
In reference [13] a group of mobile robots is required
to maintain a wireless ad-hoc network by resorting to a
distributed algorithm; each robot computes a first-order pre-
diction of the network topology and, according to a proper
cost function, estimates the position where the probability to
maintain network connectivity is the largest. A behaviour-
based approach is used in [15] to encourage a team of
robots in maintaining a connected communication network
during an exploration mission; the robots that form a bridge
connection, i.e., a link whose removal disconnects the net-
work, are forced to implement a connectivity-behaviour task.
Reconfiguration aimed at implementing a fault-tolerant bi-
connected configuration is proposed in [7]. Decentralized
estimation procedure, based on graph theory, are used in [16]
to allow each agent to track the algebraic connectivity of a
time-varying graph; such measure of graph connectivity has
been used in [14] for the connectivity maintenance problem,
and in [9] in the framework of teleoperation of groups of
UAVs (Unmanned Aerial vehicles).
In this paper we focus on the application where an au-
tonomous agent, e.g., a robot or a human operator, navigates
inside an area where communication infrastructure is lacking;
even so, the agent is required to constantly communicate
with a fixed base station. In the absence of other/stationary
network devices, the explorable area would be limited by
the maximum range of peer-to-peer wireless communication
between the agent and the base station. Indeed, the presence
of a set of autonomous mobile robotic devices that establish
a wireless MANET and act as relays will be of signifi-
cant importance to increase, via multi-hop, the maximum
explorable area. The considered mobile devices are ground
robots (aerial robots can be considered as-well) that are able
to autonomously reconfigure without knowing in advance
the motion of the leading agent. Each robot acts both as
a host and a router, and it can directly communicate with
(A)
PSfrag replacements
base station
mobile antennas
agent
(B)
PSfrag replacements
base station
mobile antennas
agent
(C)
PSfrag replacements
base station
mobile antennas
agent
(D)
PSfrag replacements
base station
mobile antennas
agent
Fig. 1: Sketch of the problem to be solved.
robots/systems in its transmission range, i.e., its one-hop
neighbours. The communication between the base station and
the agent is thus achieved by data packets relayed over a
sequence of intermediate nodes (the robots) using a store-
and-forward multi-hop transmission principle.
Following the preliminary results in [4], [5], in this paper
we propose a distributed control approach to solve the afore
mentioned problem using a behaviour-based technique and a
task activation strategy related to realistic characteristics of
routing algorithms for mesh network. The proposed approach
has been validated via challenging experimental tests in large
indoor environment with a team of five ground mobile robots.
II. CONNECTIVITY MAINTENANCE STRATEGY
Consider the scenario in Figure 1, one autonomous agent
(in blue) is moving according to a specific strategy that
is unknown to the other devices. During the mission, the
wireless communication connectivity between the agent and
the fixed base station should be permanently guaranteed by a
team of n support mobile robots (in grey) that are required to
realize an ad-hoc network and to increase the navigational
coverage area of the agent. The maximum communication
range between agent and base station is shown in Fig. 1B .
We propose a distributed motion control strategy for the
support robots to allow the autonomous agent accomplish
its mission. Specifically, the support robots are required to
simultaneously achieve multiple tasks like avoiding obstacles
and collisions, generating a connected ad-hoc network for
relaying the data from the lead agent to base station, and
keeping the connectivity to the network. Moreover, they
are required to use information from their on-board sensors
and to exchange messages exclusively with their immediate
neighbours in the established ad-hoc network.
The control policy is generated on the basis of the infor-
mation available to the robot. In particular, we assume that
each network node runs a routing protocol for ad-hoc/mesh
networks, and that each robot has access to its dynamic
routing table (any routing protocol is permissible). Thus,
analysing the routing table, each robot can extract network
layer information (ip address) about all other accessible
robots inside the communication network (considering both
one-hop and multi-hop), moreover, it can extrapolate what
are the directly connected nodes (one-hop), and, for the non
immediate neighbours, the first hop towards them. Figure 2
shows an example of routing table available to one of the
robots in an assigned configuration; from the case in figure,
robot 5 can infer from its routing table that it can directly
communicate with robot 3, 4 and with the agent, and it knows
that it can communicate with robots 1, 2 and the base station
through robot 3 as the first hop.
In order to send messages to the base station, the au-
tonomous agent elaborates information from its routing table
and sends the message to the first hop towards the base. It-
eratively, the robots on the path, that are the robots receiving
the message originated by the agent (see Fig. 3), are required
to forward it until it reaches the base station.
PSfrag replacements
base station
mobile antennas
agent
Fig. 2: Routing table available to one of the robots in an
assigned configuration.
The forwarding strategy allows the robots to dynamically
realize if they belong to the path from the lead agent to
the base or not, and to adopt different motion strategies
accordingly. Robots belonging to the path are mainly re-
quested to keep connectivity with the previous and successor
robots along the path simultaneously allowing it to stretch;
moreover, they have to recover global connectivity if it
gets lost. Robots not belonging to the path are required to
remain connected to the network and place themselves so
that they can become part of the path whenever required.
The motion directives to the robots are generated referring
to a behaviour based technique, namely the Null-Space based
Behavioural (NSB) control, that composes a set of prioritized
task functions describing the elementary behaviours.
PSfrag replacements
base station
mobile antennas
agent
Fig. 3: Communication path from agent to base station.
III. NULL-SPACE BASED BEHAVIORAL CONTROL
The NSB is a behaviour-based approach for robotic sys-
tems developed by some of the authors of this paper. The
main idea of the approach is to describe the mission through
a set of elementary behaviours, to define a task function for
each behaviour and to use a projection mechanism (based on
the null-space projection matrix) to compose them following
their priority order. The behaviours are combined so that the
lower priority behaviours do not affect the higher priority
ones. The null-space projection matrix of a behaviour filters
out the velocity components of the lower priority ones that
would affect its functionality. A detailed description of this
approach extends beyond the scope of this paper, but can be
found in [1], [3], [2]. In the following, we briefly recall the
main methodology of the approach and the task functions
realized for the specific mission.
Lets define the position of the jth robot as pj
=
xj
yj
T and the generic task variable to be controlled as
σ ∈Rm a function of the position:
σ = f(pj)
(1)
The corresponding differential relationship is:
˙σ = ∂f(pj)
∂pj
vj = J(pj)vj
(2)
where J ∈Rm×2 is the robot configuration-dependent task
Jacobian matrix and vj ∈R2 is the robot velocity.
The motion directives to the robot, i.e. velocity reference
commands, are elaborated as:
vd,j = J†( ˙σd + Λ˜σ)
(3)
where J† = JT(JJT)−1, Λ is a suitable constant positive-
definite matrix of gains and ˜σ = σd −σ is the task error.
Let us consider the mission for the jth robot composed
by multiple elementary tasks. Using the subscript i referring
to the ith task quantities for the jth robot, on the analogy of
the above equation, the ith task velocity is computed as
vi = J†
i( ˙σi,d + Λi ˜σi).
(4)
If the subscript i also denotes the degree of priority of the
task with, e.g., Task 1 being the one with highest-priority,
the final motion command to the robot is modified into:
vf,j = v1 + N 1,1v2 + N 1,2v3,
(5)
where N 1,k is the projection matrix into the null-space of
the task 1 to k. In particular, defining J1,k as
J1,k =


J1
J2
...
Jk

,
(6)
the null-space projection matrix N 1,k is elaborated as
N 1,k =

I −J†
1,kJ1,k

.
(7)
where I is the identity matrix of proper dimensions. Re-
markably, above eq. has a nice geometrical interpretation.
Each task velocity is computed as if it were acting alone;
then, before adding its contribution to the vehicle velocity,
a lower-priority task is projected onto the null space of
the immediately higher priority tasks so as to remove those
velocity components that would conflict with it.
IV. CONNECTIVITY MAINTENANCE TASK FUNCTIONS
In order to define specific task functions for the connectiv-
ity maintenance problem, we assume that the communication
capabilities are mainly effected by the relative distances
among the network nodes, i.e., the devices can communicate
if their relative distance is lower than a certain threshold.
In future research, we will consider more realistic models
for the wireless channel and we will use specific metrics for
e.g., Received Signal Strength Indicator (RSSI) or Packet
Loss Percentage; moreover, we will consider effects of
the communication environment (as multi-path, noise, and
attenuation of signal strength if the devices are not in line
of sight). Here, the considered task functions are:
• Distance from a point. This task function moves the
robot at a certain distance Dd from a point p1. Therefore
the task function is defined as
σp = ∥p −p1∥∈R,
(8)
and σp,d = Dd. Then, it holds
Jd = ˆrT ∈R1×2
(9)
where ˆr =
p−p1
∥p−p1∥is the unit vector aligned with the
point-to-robot direction. Therefore, the task output is a
velocity, in the robot-to-point direction, that keeps the
robot at an assigned distance to it.
• Equal distance from two points. This task function
moves the robot so as to keep equal distance from two
points p1, p2. The task function is defined as
σe = ∥p −p1∥2 −∥p −p2∥2 ∈R,
the corresponding Jacobian is
Je = 2

(x2 −x1)
(y2 −y1)

and the desired value of the task function is σe,d = 0.
• Move to Goal. The move-to-goal task function moves
the robot toward an assigned goal:
σg = p ∈R2.
(10)
The desired values is σg,d = pg where pg are the
coordinates of the goal. Since Jg = J†
g = I ∈R2×2,
the output velocity is given by
vg = Λg(pg −p)
(11)
a vector in the goal direction proportional to the distance
from it.
• Obstacles and collision avoidance. In presence of a
point obstacle i.e. po in the advancing direction, the aim
of the task is to keep the robot at a safe distance from
it. Therefore the task function is similar to the Distance
from a point with difference that it is activated only if
the relative distance is under a threshold and the robot is
moving in the obstacle direction. The same task function
can be used also in presence of a linear obstacle with
the difference that the reference point po is the point of
the segment closest to p. For reference [6].
A proper combination of such task functions allows to
manage the robots to achieve the described mission. In par-
ticular, obstacle avoidance, when active, is always the higher
priority task since it is needed to preserve robot integrity;
however, it is activated only in proximity of obstacles or
other neighbouring robots detected by laser range finer or
received over wireless link. The other task functions are
activated depending on the state of the robots:
Robots belonging to the path are commanded to keep equal
distance form their predecessor and successor nodes; if they
loose the connectivity with their predecessor (i.e. the one
hop node towards the base) they have to move towards
their last known position. When the distance from prede-
cessor/successor node is greater than a certain percentage
of rmax (the maximum communication range of the device
in free space), the robot sends explicit help requests to
neighbouring robots that do not belong to the path (if any)
and asks one of them to get placed in the middle point
between itself and its predecessor/successor node; in this way
we facilitate the insertion of other nodes in the path.
Robots not belonging to the path should stay connected to the
network and remain available to join the path if requested.
A first solution could be to keep the same distance from
the base station and the first node of the route; alternative
solution could be to keep equal distance from the first hop
towards the base and the first hop towards the agent.
The description above has been coded in a Finite State
System activating the proper behaviours within the frame-
work of the NSB coordination strategy [2].
V. EXPERIMENTS
A. Experimental platform
The experimental validation has been made with a team
of five Khepera III mobile robots, by K-Team corporation,
that are small size (12 cm diameter) differential drive mo-
bile robots equipped with several proximity sensors (11 IR
sensors and 5 ultrasound sensors). The robots also have
an extension board, namely the Korebot II, an embedded
platform based on the gumstix Verdex PRO with a Marvell
PXA270 XScale processor @ 600 MHz, with 128 MB RAM
and 32 MB Flash memories. The Korebot II runs on standard
embedded Linux o.s. (Angstrom distribution, kernel 2.6) and
we used a specific C-library of basic functions developed by
the Distributed Intelligent Systems and Algorithms Labora-
tory, EPFL.
Fig. 4: Mobile robots Khepera III equipped with horizontal
laser scanner.
To improve the robots’ perception we equipped them with
Hokuyo Laser Range Finder (LRF) URG-04LX-UG01. The
LRF is connected to the Korebot II through USB and power
supply is provided by external batteries. The Hokuyo LRF
is apt in terms of weight, power consumption, range and
accuracy, to properly fit with Khepera III robots and help in
navigation in a structured environment. Each robot is able
to localize itself w.r.t. a known map by using a line-feature-
based Extended Kalman Filter presented in [6].
The Korebot board also allows robot-robot and, even-
tually, robot-pc communication, when embedded with an
IEEE 802.11 wireless card. In particular, the robots commu-
nicate through a wireless ad-hoc network built with the aim
to perform completely distributed experiments. For routing
and multi-hop communication we used specific linux func-
tions as ip forwarding and a routing protocol via olsrd
daemon. Specifically, olsr daemon is an implementation of
the Optimized Link State Routing protocol that allows mesh
routing for any network equipment. This protocol runs on
any wificard that supports ad-hoc mode, and it is widely
used and well tested. The protocol dynamically generates
the routing table of the mesh network; it is pro-active, table
driven and utilizes a technique called multi-point relaying
for optimized message flooding. Further details on the olsrd
implementation go beyond the scope of this paper, while it
is worth noticing that the olsrd dynamically generates the
routing tables as described in Sect. II.
It is worth noticing that the output of NSB control
is a linear velocity command considering the robot as a
spatial point; thus, to use it to control a non-holonomic
vehicle, as the Khepera III, the NSB output velocities are
passed to a Low-Level control that elaborates angular and
advancing velocities and, using odometric model parameters,
converts them to left/right wheel velocity commands. In the
implementation of the algorithm, the resulting velocity are
saturated to feed the system with limited amplitude signals.
B. Experimental results
In this section we present results of connectivity mainte-
nance experiments performed in an indoor environment (the
corridor of our institution). It is worth noticing that, despite
the small size of the robots, the dimension of the area is of the
order of 90 m; moreover, since point-to-point communication
range is of the order of 20−25 m, to navigate in the complete
environment keeping the communication with a base station
(at: [1.3, −1.5] m) multi-hop communication is required.
Five robots were used for the experiment. One of them (the
agent) was commanded to follow a set of way points spread
in the complete area; the others were used as support robots
to allow multi-hop relay communication. The motion strategy
of the agent, as well as its way points, are unknown to the
support robots; the only capability of the agent is to halt and
communicate its position once it looses connectivity with the
base (direct or multi-hop) and also to come back towards the
last known predecessor position if the connectivity is not re-
established in a certain amount of time.
Figure 5 shows multiple snapshots of the mission exe-
cution elaborated by post-processing robots data from the
experiment, in the form of localization estimates and routing
tables. From experimental evidence, the maximum range of
direct communication achievable with the fixed base and
one moving robot is effected by both relative distance and
line of sight; in fact, as soon as the agent crosses the first
intersection, the communication performance with the base
quickly decreases and eventually connectivity is lost. The
olsrd protocol requires a few seconds to find the multi-hop
connection and incorporate one of the support robots in the
path. Once a support robot is included in the path, it tries to
keep equal distance between the agent and the base, while
the other robots do the same but between the inserted support
robot and the base. It is worth noting that the autonomous
agent was finally able to reach the last way point as far as
almost 100 m from the base, and the team of robots was
able to dynamically configure in order to provide a proper
communication support to the agent. After reaching the last
way point, the agent tracks back to its starting position
following the same set of way points.
During the experiment, the agent was constantly required
to send data, eventually via multi-hop, to the base station (via
UDP/IP protocol). Figure 6 shows a plot of the packets lost
during the mission generated by checking the identification
numbers of the packets received from the base station. It
is worth noticing that the global number of packets lost
is very limited, and that the loss mainly occurred when a
PSfrag replacements
t[s]
Packet loss
0
0
5
10
100
200
300
400
Fig. 6: Packet loss during multi-hop transmission between
the last robot and the base station.
couple of nodes on the path were close to the maximum
communication range and the routing protocol was not
promptly able to find a new configuration.
The maximum speed for the agent and the support robots
was set to 0.2 m/s; the robots’ speed is bounded by the
limits of the localization algorithm running on board that
makes use of laser measurements and it was not lowered for
this experiment. The duration of the complete experiment
was of 700 s. The video at the following address shows an
animation, from experimental data, of the team motion
http://webuser.unicas.it/lai/robotica/video/manetexp.mp4
VI. CONCLUSIONS
In this work we have presented a distributed motion con-
trol strategy for a team of mobile robots to offer multi-hop
connectivity between a fixed base station and an autonomous
agent. The proposed strategy uses a behaviour-based ap-
proach and a dynamic task selection policy to generate
motion references for the robots using local information
from on-board sensor, communication with neighbours and
information from routing tables. The proposed strategy has
been successfully experimentally tested in large indoor en-
vironment using a team of five mobile robots realizing the
robotic Mobile Ad-hoc NETwork.
Future work will concern the refinement of the control
strategy to facilitate the introduction of nodes in the com-
munication path between agent and base station. Moreover,
we will consider to design complex paths in maze-like
environment, i.e., paths that are not driven by a gradient-
like policy but require more elaborated strategies to be com-
puted. Finally, we will consider communication performance
metrics as Radio Signal Strength Indication or Packet Loss
Percentage to overcome distance based task functions.
ACKNOWLEDGMENTS
The research leading to these results has received funding
from the Italian Government, under Grant FIRB - Futuro in
ricerca 2008 n. RBFR08QWUV (NECTAR project).
REFERENCES
[1] G. Antonelli, F. Arrichiello,
and S. Chiaverini.
The entrap-
ment/escorting mission: An experimental study using a multirobot
system.
IEEE Robotics and Automation Magazine (RAM). Special
Issues on Design, Control, and Applications of Real-World Multi-
Robot Systems, 15(1):22–29, March 2008.
1
2
3
4
5
Time: 103.0s
1
2
3
4
5
Time: 177.0s
1
2
3
4
5
Time: 197.2s
1
2
3
4
5
Time: 227.6s
1
2
3
4
5
Time: 258.0s
1
2
3
4
5
Time: 329.6s
1
2
3
4
5
Time: 410.3s
Fig. 5: Paths driven by the five robots during the robotic MANET experiment.
[2] G. Antonelli, F. Arrichiello, and S. Chiaverini.
The Null-Space-
based Behavioral control for autonomous robotic systems.
Journal
of Intelligent Service Robotics, 1(1):27–39, Jan. 2008.
[3] G. Antonelli, F. Arrichiello, and S. Chiaverini.
Experiments of
Formation Control With Multirobot Systems Using the Null-Space-
Based Behavioral Control.
IEEE Transactions on Control Systems
Technology, 17(5):1173–1182, Sept. 2009.
[4] G. Antonelli, F. Arrichiello, S. Chiaverini, and R. Setola.
A self-
configuring MANET for coverage area adaptation through kinematic
control of a platoon of mobile robots. In Proceedings 2005 IEEE/RSJ
International Conference on Intelligent Robots and Systems, pages
1332–1337, Edmonton, CA, Aug. 2005.
[5] G. Antonelli, F. Arrichiello, S. Chiaverini, and R. Setola. Coordinated
control of mobile antennas for ad-hoc networks. International Journal
of Modelling Identification and Control Special/Inaugural issue on
Intelligent Robot Systems, 1(1):63–71, 2006.
[6] F. Arrichiello, S. Chiaverini, and V.K. Mehta. Experiments of obstacles
and collision avoidance with a distributed multi-robot system.
In
Proceeding of the IEEE International Conference on Information and
Automation, pages 727–732, Shenyang, China, June 2012.
[7] P. Basu and J. Redi.
Movement control algorithms for realization
of fault-tolerant ad hoc robot networks. IEEE Network, 18(4):36–44,
2004.
[8] F. Bullo, J. Cort´es, and S. Mart´ınez. Distributed Control of Robotic
Networks. Applied Mathematics Series. Princeton University Press,
2009.
[9] P. Robuffo Giordano, A. Franchi, C. Secchi, and H.H. B¨ulthoff. Bilat-
eral teleoperation of groups of UAVs with decentralized connectivity
maintenance.
In Proceedings of the 2011 Robotics: Science and
Systems Conference, Los Angeles, USA, 2011.
[10] V. Kumar, D. Rus, and S. Sukhatme. Springer Handbook of Robotics,
chapter Networked Robots, pages 943–958. B. Siciliano, O. Khatib,
(Eds.), Springer-Verlag, Heidelberg, D, 2008.
[11] L.E. Parker.
Distributed intelligence: Overview of the field and its
application in multi-robot systems. Journal of Physical Agents, 2(1):5,
2008.
[12] L.E. Parker. Springer Handbook of Robotics, chapter Multiple Mobile
Robot Systems, pages 921–941.
B. Siciliano, O. Khatib, (Eds.),
Springer-Verlag, Heidelberg, D, 2008.
[13] B. Pimentel and M. Campos. Cooperative communication in ad hoc
networked mobile robots.
In Proceedings IEEE/RSJ International
Conference on Intelligent Robots and Systems, pages 2876–2881, Las
Vegas, NE, Oct. 2003.
[14] Lorenzo Sabattini, Nikhil Chopra, and Cristian Secchi.
On decen-
tralized connectivity maintenance for mobile robotic systems. In 2011
50th IEEE Conference on Decision and Control and European Control
Conference (CDC-ECC), pages 988–993. IEEE, 2011.
[15] J. Vazquez and C. Malcolm.
Distributed multirobot exploration
maintaining a mobile netwok. In Proceedings 2nd IEEE International
Conference on Intelligent Systems, volume 3, pages 113–118, Varna,
Bulgaria, June 2004.
[16] P. Yang, R.A. Freeman, G.J. Gordon, K.M. Lynch, S.S. Srinivasa,
and R. Sukthankar.
Decentralized estimation and control of graph
connectivity for mobile sensor networks. Automatica, 46(2):390–396,
2010.