IEEE Robotics & Automation Magazine - December 2010 - 29

Speed Selection
σi (0)

Heading Selection
σi (0)

Keep
Speed

ei3

ei3

ei3

Speed
Up

e1i

ei2

Turn
Toward
Formation

Slow
Down

Keep
Heading

e4i e 5
i

ei3
Head to
Formation
Position

e1i = Behind Its Formation Position

e4i = ¬ei3∧ Formation Moving

ei2 =
ei3 =

e5i = ¬ei3∧ Formation Fixed

In Front of Its Formation Position
In Formation Position
(a)

(b)

(c)

Figure 4. A behavior-based formation control protocol enabling a set of autonomous vehicles to achieve a common mission
goal (cf. [14]). (a) and (b) Protocols' automata and (c) example of system's evolution.
u
u

a discrete state ri 2 Ri , where Ri is the set of allowed
actions or decisions
a dynamic map fi describing how the agent's configuration is updated:

where ui is the input vector
a controller map gi that, based on the agent's current configuration qi and discrete state ri , returns the control value
ui ¼ gi (qi , ri );

u

a detector map di ¼ (di,1 , . . . , di, ji ) returning a binary
vector ei , whose jth component activates if a local condition di;j on the presence or absence of other agents in
Ai 's vicinity/neighborhood holds, i.e.,
ei ¼ di (qi , vi ),
where vi ¼ fqi1, . . . , qip g is the set of configuration vectors of Ai 's neighbors

vi
ξi

qi
ei = D (qi, vi, ξi)

ei

A
σi

ui
·
qi = f (qi, σi)
qi

ui = g (qi, σi)

H

qi

Figure 5. Architecture of a generic agent Ai following a
motion cooperation protocol P.
DECEMBER 2010

an automaton di describing how the agent's current
action ri is updated based on the event vector ei :
rþ
i ¼ di (ri , ei ):

As such, the behavior of a robotic agent Ai adhering to P is
described by the hybrid dynamics [20]

q_ i ¼ fi (qi , ui ),
u

u

&

(_qi , rþ
i ) ¼ Hi (qi , ri , qi1 , . . . , qip ),
qi (0) ¼ q0i , ri (0) ¼ r0i ,

where q0i and r0i are the initial configuration and discrete state,
respectively, and i1 ; . . . ; ip are the indices of Ai 's neighbors.
The architecture of an agent Ai adhering to the generic protocol is depicted in Figure 5.
We say that a cooperation protocol P is fully distributed if
it involves only local interaction within a maximum number
N of agents, i.e., ip N, where N is independent of the total
number n of agents.
As an example of successful application of the hybrid
automata theory, consider the problem of managing the traffic
of an unbounded number of unmanned aerial vehicles
described in [21]. Therein, Pallottino et al. proposed a motion
coordination protocol, involving of a set of fully decentralized
behaviors, whose correctness in terms of safety and deadlock
avoidance was proven through application of formal methods.
The protocol, known as generalized round-about policy
(GRP), realizes a scalable ðN ¼ 6Þ and reconfigurable multirobot system. Although the proof of correctness was given for
aerial vehicles with the same size, it is straightforward to extend
the result to vehicles with different sizes (see Figure 6).
Another example of multirobot system that can be formalized
according to the above protocol, and that we will consider in
more detail, is represented by n cars in a highway following a set
of traffic rules to avoid collisions (Figure 7). Car 01 initially slows
down due to the presence on its front lane of car 04, which, in
turn, turn right as its next right lane is free. Car 03 later starts a left
turn as car 01 occupies its immediate front lane and its next left
lane is free. Finally, car 02 slows down as its front lane is occupied
by car 04 and its next left lane is also occupied by the cars 00 and
IEEE Robotics & Automation Magazine

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