IEEE Robotics & Automation Magazine - September 2019 - 82

determine the primitive a to be executed from the current
vertex. Termination may happen because the robot reaches
the desired local target v or the global target G but also if the
global temporal deadline expires. In this case, the robot
returns a failure.
Because the robot starts
with an empty map, it initially randomly moves
The topological frontier
around until it has K vertices in the graph. In all of
algorithm sorts all nodes
our experiments de by the number of outgoing scribed in the following,
K is fixed to three. Finally, in algorithm 3, we
unexplored edges, and
show how the overall
exploration task is solved.
it randomly selects one
After creating the initial
map M, the robot enters
among those with the
a loop that continues
until either the global
highest number of
temporal deadline T
expires or the robot sucoutgoing edges.
ceeds in reaching G. At
every iteration, the function ExplorationNext returns the vertex v toward which to
move and a temporal deadline t d, i.e., how much time the
robot should spend to reach v. To determine these two quantities, ExplorationNext uses the current map, as well as the
variable time, indicating how much time passed since the task
started. As time grows, more stringent temporal deadlines t d
will be returned. The robot then attempts to navigate to the
assigned vertex v and, once there, randomly picks an outgoing
edge and follows it until the IDS indicates that a new vertex
has been reached.
Exploration Algorithms
We now discuss five different strategies that can be used to
guide the robot through its exploration task. Each of these
approaches represents a different way to select the vertex v
returned by the function ExplorationNext used in algorithm 3. At the end of the section, we also discuss how we set
the temporal deadline t d .
Algorithm 2: Navigation algorithm
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.

82

*

Algorithm NavigateToVertex ^v, t d h
CMDP ! BuildCMDP ^ M, v, t d, Pf h
r * ! Solve ^CMDP h
while time 1 T
v c ! current vertex
if v c = G then
return Global Success
if v c = v then
return Local Success
a ! r * ^v c h
execute a
return Failure

IEEE ROBOTICS & AUTOMATION MAGAZINE

*

SEPTEMBER 2019

Random Strategy Exploration
The random exploration strategy is our baseline approach. It
returns a random vertex among all vertices with one or more
outgoing unvisited edges, i.e., edges toward v z . If there is
more than one vertex with unvisited edges, a uniform probability distribution is used to make a choice. It is easy to prove
that this strategy will eventually explore the entire environment, but it is likely to be inefficient.
Topological Frontier
Topological frontier is the analog of the well-known frontierbased exploration algorithm. In frontier-based exploration,
frontiers are defined as the regions on the boundary between
explored and unexplored space, and the robot then moves to
a frontier to expand the explored space. In our topological
domain, the boundary between known and unknown parts of
the environment is identified by unexplored edges. Accordingly, the topological frontier algorithm sorts all nodes by the
number of outgoing unexplored edges, and it randomly
selects one among those with the highest number of outgoing
edges. In this latter case, a uniform distribution among all of
the candidates is used.
Topological Frontier With
Normalized Distances
In the topological case, the cost to move to a vertex in the
graph is set to the number of edges in the path connecting
the current vertex to a target location. To consider distances in the topological frontier algorithm, we choose a
closer vertex when one or more equivalent ones are present. To combine heterogeneous quantities (the number of
outgoing unexplored edges and distances), we use a linear
combination of normalized quantities (see, e.g., [19]) to
assign a value to each vertex in the map. We then select
the vertex maximizing this metric. To be specific, let
V 1 V be the set of vertices with one or more outgoing
unexplored edges. For each vertex v ! V, we compute
the following quantity:
S^v h = c

deg ^ v h
d^v h
- ^1 - ch
,
maxdeg ^vlh
max d ^vlh
vl ! V

vl ! V

Algorithm 3: Global exploration algorithm
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.

Algorithm ExplorationTask ^T, Gh
M ! InitializeGraph ()
while time 1 T do
v, t d ! ExplorationNext ^ M, time h
flag ! NavigateToVertex^v, t d h
if flag = Local Success then
Pick random edge of type ^v, v zh out of v
Follow edge e of type ^v, v zh and find new node vl
CreateNewNode ^v l , edges h
else
return flag
return Failure
IEEE Robotics & Automation Magazine - September 2019

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