IEEE Robotics & Automation Magazine - December 2010 - 28

Reaching a global agreement on
the presence of a misbehaving
robot is essential to neutralize or
reduce the threats that it may pose
to the society.
is decentralization, i.e., decisions should be made by each
agent autonomously and should be based on information
limited to a local neighborhood of each robot, reducing the
role of a central authority to the minimum necessary.
A system that relies on social behaviors to mitigate the excess
of individualism is intrinsically very sensitive to the possibility
that misbehaviors occur, either due to faults in some robots or
malicious programming of agents. Thus, security requirements
are crucial for a society of robots, which imply the capability to
detect, isolate, and neutralize the threat posed by misbehaving
robots (see e.g., [17], the articles on fault tolerance in robot
swarms [18] and on the ALLIANCE architecture [19], and
references therein). In a society of autonomous robots, intrusion
detection must also rely on information available locally and on
limited knowledge of a model for the behavior of other robots.
A common problem with overcautious security policies is
that they can make the system too stiff and ineffective. In a
heterogeneous robot society, a robot should not deem another
robot to be a malevolent intruder just because it behaves differently, as far as that behavior does not pose a threat. Hence, a
problem of detecting which type of behavior other robots in
the neighborhood is following, or which species they belong
to, is also in order.
In this article, we discuss the above challenges and present
work toward solving some of them. This article's first contribution is the formalization of a cooperation protocol by which
societies of interacting robots can be described at a suitable
abstraction level. We show examples of motion control protocols that guarantee collision avoidance for arbitrarily large
groups of heterogeneous robots and discuss intrusion detection
algorithms, which allow detection of deviance from such rules.

¬ei

The description of a local misbehavior detector, representing
the second contribution of the article, is also presented. We
also present algorithms to build a consensus view on the environment and on the integrity of peers, so as to improve the
overall security of the society of robots. Furthermore, we show
a biologically inspired example of social coordination protocol
enabling a group of antlike robots to cooperate during the foraging of the same group. This is based on the use of a local classifier by which individuals can distinguish neighboring robots
obeying to a different set of rules and thus belonging to a different species or social groups.

Social Behaviors as Hybrid Automata
Behavior-based societies of robots can be built by giving a set of
rules that each agent should follow, which are only based on local
information and communication between neighboring agents.
Such rules can usually be described in the form of an automaton,
with states corresponding to decisions or actions, and transitions
triggered by locally evaluated conditions. A first example of a
multirobot system that has conflicting individual goals but can
negotiate crossroads by following a set of elementary rules is
reported in Figure 3. The second example, where the mission
goal is shared among all the members of the society, is the formation control protocol proposed by Arkin [14] (Figure 4).
Although simple rule sets may well serve the purpose for a
limited number of robots, a problem may arise when the same
rule set is applied to larger and/or safety critical systems,
whether it can be guaranteed that vehicles will not get into
deadlocks or even crash into each other. To provide such guarantees, a formal description of behaviors is in order. One should
observe that, in dealing with physically embodied autonomous
agents such as robots, traditional automata theory is limited
because of the lack of expressivity power to model continuous
dynamics. The hybrid automata formalism and verification
techniques can be effectively used for that purpose.
A motion cooperation protocol P that can describe the
behavior of the individuals, A1 , . . . , An , of a robotic society
can be formalized as follows. For each robot Ai , the protocol
must specify:
u a configuration vector qi 2 Q, where Q is a configuration space

ei
ei

σi (0)

¬ei

ei = ″Right Street Occupied″
(a)

(b)

(c)

(d)

Figure 3. Autonomous laser-guided vehicles in a warehouse can efficiently move products, from carrier tapes to storage piles, and
avoid robot-robot and robot-human collisions, by following a very simple motion control protocol requiring that every robot give
way on its own right. (a) Protocols' automaton, (b) initial configuration, (c) intermediate configuration, and (d) final configuration.
28

IEEE Robotics & Automation Magazine

DECEMBER 2010

Table of Contents for the Digital Edition of IEEE Robotics & Automation Magazine - December 2010