IEEE Robotics & Automation Magazine - September 2019 - 80

semantic information combined with geometric information
to improve the exploration of a map, with privileged areas
defined by humans as first goals for the robots [10].
Temporal deadlines in robotics have been extensively studied for scheduling and coordination tasks, for example, when
multiple robots must coordinate their actions so that the relative temporal ordering becomes relevant [11], [12]. We
recently studied a class of multiobjective planning problems
where the temporal deadline becomes an additional constraint to be met while optimizing some other objective function, as, for example, the probability of successfully reaching a
location or gathering some data [13]-[15]. These methods
are the foundation of the planning method we consider.
Background on Spatial Representation and
Planning Under Temporal Constraints
Semantic Topological-Oriented Maps
Here, we define semantic topological-oriented maps (or
toposemantic maps, for brevity) as an extension of the classic definition of topological maps. Topological maps model
space as a graph G = ^V, E h, with vertices representing
places and edges modeling the ability to move between the
places represented by the vertices. Our model builds upon
two assumptions. First, indoor environments are normally
subdivided into corridors and rooms arranged along
orthogonal directions. This observation was previously
made and exploited in [10]. Second, we assume that the
robot is equipped with a device providing absolute orientation (a compass).
Starting from these two hypotheses, without loss of generality, we assume that the walls and corridors of the building
are arranged along the four cardinal directions, abbreviated as
N (north), S (south), E (east), and W (west). An oriented
topological map exploits these assumptions to define the

relations "to the right of" and "to the left of" between vertices
in the graph. Vertices in a graph may have degree 1 (rooms or
corridor dead ends), 2 (corridors), 3 (T junctions), or 4 (fourway intersections). Thanks to the compass, each edge can
then be labeled as E-W or N-S, depending on its direction.
Accordingly, two adjacent vertices are said to be along the
N-S direction if the edge connecting them has the N-S label;
we similarly define adjacent vertices along the E-W direction.
To define the relationships "to the right/left of" for elements
aligned along the N-S direction, we assume that the robot
faces W, whereas for elements along the E-W direction we
assume the robot faces N.
Figure 1 illustrates this approach. The three vertices on the
left are along the E-W direction. Based on our assumption
that the robot points north to define left/right relationships,
vertex c1a is to the left of c1b, and c1b is to the right of c1a.
On the right, c2b is to the right of c2c and to the left of c2a.
The following definition formalizes the structure of a map.

Definition 1
A semantic topological-oriented map is defined as
M = ^V, E, L, D, Sh where the following are the case:
● ^ V, E h are the vertices and edges of a directed graph.
● L: V " m assigns a unique semantic label to each vertex,
with m being a finite set.
● D : E " " E - W, N - S , is a function assigning a direction to each edge.
● S: E " " L, R , is a function assigning a label L (to the
left of) or R (to the right of) to each edge. The oriented
edge is to the left/right of the vertex it originates from
(see Figure 2).
● If e = ^ v i, v j h ! E is an edge from v i to v j and S^ e h = L,
then el = ^v j, v ih ! E, and S^elh = R. Likewise,
e ^v i, v jh ! E / S^ e h = R & el = ^v j, v ih ! E / S^elh = L.
● For each couple of adjacent vertices, D ^ v i, v j h = D ^ v j, v j h .
The last two conditions establish
two consistency constraints. If it is
N/Right
possible to go from v i to v j along one
N/Right
direction (say, N-S), then it is possic1b
c1a
c2a
ble to go from v j to v i along the
W/Left E/Right
same direction but the opposite oriS/Left
W/Left
E/Right
entation (such as S-N). Second, if
c2a
there is an edge from v i to v j indicatS/Left
ing that v j is to the left of v i, then
there must also exist the opposite
c2b
c2b
Room 1
edge from v j to v i, indicating that v i
c1a
c1b c1c
is to the right of v j .
Collectively, the algorithms proc2c
viding L, S, and D will be in the
following, indicated as the Inter(a)
(b)
(c)
section Detection System (IDS).
Thanks to recent advances in percepFigure 1. (a) Three adjacent vertices along the E-W direction, with c1a to the left of c1b
tion [16], we assume that the IDS
and c1c to the right of c1b. (b) Three vertices along the N-S direction, with c2a to the
can recognize whether a detected
right of c2b and c2c to the left of c2b. (c) Here, there are two adjacent vertices along
intersection or corridor is new or
the E-W direction (c1a to the left of c1b), room 1 to the left of c1b, and two adjacent
vertices along N-S, with c2a to the right of c2b and room 1 to the left of c2b.
revisited. Figure 2 shows how a

80

*

IEEE ROBOTICS & AUTOMATION MAGAZINE

*

SEPTEMBER 2019
IEEE Robotics & Automation Magazine - September 2019

Table of Contents for the Digital Edition of IEEE Robotics & Automation Magazine - September 2019
