IEEE Robotics & Automation Magazine - September 2011 - 84

R5r

P2

I4
R5l

R4l

I1

P1

R2l

R4r

P4

R2r

R3l

I3
R3r

I2

P5

P3
R1r

R1l

(a)
H2
P1

R1r

H1
P2

R5r

I1

R5l
R2r

R1l

L3
P3

R4r

L2
P4

R2l

I4

R4l
1

I3

R3l

I2

R3r

I3

L1 P5
(b)
Figure 6. The city for the case study. (a) The topology of the
city with the road, intersection, and parking lot labels. (b) The
transition systems Ti capturing the motion capabilities of the
robots, which are identical, except for the initial state (not
shown), and the requests that occur in the environment
(parking lots).

user (i.e., to enter the task specification) and to perform all
the computation necessary to generate the individual
deployment strategies. Once computed, these are sent to
the robots, which execute the task autonomously by interacting with the environment and communicating with
each other if necessary.
The abstraction process of the RULE platform proceeds as follows. The set of vertices v of the environment
graph is the set of labels assigned to the roads, intersections, and parking lots [see Figure 6(a)]. The edges of this
graph show how these regions are connected. We assume
that interrobot communication is possible only when the
robots are in the same parking lot. The motion capabilities of the (identical) robots are captured by a transition
system Ti illustrated in Figure 6(b). For example, at vertex
R5r , only one motion primitive follow_road is available,
which allows the robot to drive on the road. There is an
84

*

IEEE ROBOTICS & AUTOMATION MAGAZINE

*

SEPTEMBER 2011

outgoing transition from R5r , and it reaches I1 , which is
triggered by at_int AND green_light, where at_int is an
interrupt generated when the robot reaches the end of a
road at an intersection, and green_light is an interrupt
generated at the green color of the traffic light. As another
example, there are three motion primitives available at I1 :
turn_right_int, turn_left_int, and go_straight_int, which
allow the robot to turn right, left, or go straight through
an intersection. It can be seen that, by selecting a motion
primitive available at a vertex, the robot can correctly execute a run of Ti , given that it is initialized on a vertex of
Ti . This shows that an MS plan can be immediately implemented by a robot.
Assume that three robots, labeled as C1 , C2 , and C3 , are
available for deployment in the city with the topology from
Figure 6. Assume the set of service requests is
R ¼ fH1 , H2 , L1 , L2 , L3 g, where Li , i ¼ 1, 2, 3 are light
requests, which require only one robot and therefore
should be serviced in parallel, while Hi , i ¼ 1, 2 are heavy
and require the cooperation of multiple robots. The set of
requests is distributed as R1 ¼ fH1 , H2 , L1 g, R2 ¼
fH1 , H2 , L2 g, and R3 ¼ fH2 , L3 g, i.e., request H2 is shared
by all robots and H1 is shared by C1 and C2 .
Consider the following specification: " First service H1 ,
then either L1 or L2 , then H2 , then either L1 , L2 , or L3 and
then H2 , and finally both L1 and L3 in an arbitrary order."
Formally, this specification translates to the following RE
over R:
/ : H1 (L1 þ L2 )H2 (L1 þ L2 þ L3 )H2 (L1 L3 þ L3 L1 ):
Following the procedure, we outlined to generate a topdown solution, we first check if the specification is distributable (the answer is yes). We then generate an implementable team FSA, the local specifications, and a set of MS
plans for the team. By assuming that C1 , C2 , and C3 start in
R4r , R5r , and R1r , respectively, the MS plans for the three
robots are
MS plan for C1 :

R4r I4 R5r P2 H1 R5r I1 R2l I2 R3r P5 L1 R3r I3 R3l
I2 R2r I1 R1r P1 H2 P1 H2 R1r I2 R3r P5 L1

MS plan for C2 :

R5r P2 H1 R5r I1 R1r P1 H2 R1r I2 R3r I3 R3l P4 L2
R3l I2 R2r I1 R1r P1 H2
R1r P1 H2 P1 H2 R1r I2 R1l P3 L3

MS plan for C3 :

where the requests serviced in the MS plan of each robot
are written in bold. The MS plans can be read as follows:
Robot C1 starts at R4r , then it follows the run R4r I4 R5r P2 .
At P2 it waits until robot C2 arrives at P2 , then services
request H1 together with C2 (this is because H1 is a request
shared by C1 and C2 ). After H1 is serviced, the robot C1 follows the run R5r I1 R2l I2 R3r P5 , services request L1 by itself
(L1 is an independent request owned by C1 ), and so on.
We deploy the robots, and the snapshots of the deployment are shown in Figure 7. The movie of the deployment
is available at http://hyness.bu.edu/RULE_media.html.
http://hyness.bu.edu/RULE_media.html
Table of Contents for the Digital Edition of IEEE Robotics & Automation Magazine - September 2011
