IEEE Robotics & Automation Magazine - September 2019 - 85

given deadline or collides with the environment while navigating. Overall, 3,000 independent tests were executed to
evaluate the five exploration strategies.
Table 1 summarizes the performance for the five exploration methods we propose. The columns give the starting location, temporal deadline expressed in seconds, time spent, and
success rate for each type of exploration: Random, Frontier,
Normalized Frontier, Semantic Strategy: Explore Corridors
First, and Semantic Strategy: Complete Corridors First. For
each combination of start location and temporal deadline, we
provide the success rate and the average time spent to reach
the target. The average time is given for successful runs only,
because unsuccessful runs may result from exceeding the
temporal deadline or because of collisions with the environment; therefore it would not be meaningful to average over
unsuccessful runs, too. Instead, Table 2 analyzes in greater
detail the causes of the failures for each strategy.
To facilitate the comparison, the results are also visually
compared in Figures 4 and 5. Unsurprisingly, the random
strategy is the most effective when starting from location A,
except when the shortest deadline is enforced. This is somewhat expected, given that other strategies tend instead to
expand the map in a principled way that may push them far
from the target location that is relatively close to A. Moving
farther from the target increases the time to complete the mission and, ultimately, the failure rate, as this translates into
increased chances to miss the temporal deadline or collide
with the environment. However, in the other cases, the random strategy is less effective and performs very poorly for the
most challenging case, which is C.

All things considered, the topological frontier with normalized distances appears to be most effective when the temporal
deadline is not too demanding. However, as the deadline
becomes more stringent, its advantage seems to vanish, and it
becomes more or less comparable to the topological frontier.
But the semantic strategies appear to offer a performance that
is less dependent on the
start location. One final
comment should be made
We have provided all of
regarding the success rates,
as they may appear to be
the resources to ensure
on the low end. This is
due to the fact that the
that a third party can fully
temporal deadlines are
strict, and this boosts the
reproduce our results-a
failure rates for all of the
algorithms. A strict temfirst in the area of
poral deadline is not only
harder to meet but also
reproducible robotics.
forces the CMDP planner
to utilize more aggressive
maneuvers, thus possibly also increasing the number of failures due to collisions with the environment.
Reproducing Our Research
The final contribution of this submission is in ensuring that
our research can be reproduced, as this is a topic of increasing importance in robotics. As noted in [20], "A study is
reproducible if you can take the original data and the computer code used to analyze the data and reproduce all of the

Success (%)

5,628

3,940

2,251

-20

563

100

120

2,899

272

2,030

477

1,160

680

Success (%)
-10

290

Success (%)
60
80

100

40 50

90 100

120

Random
Frontier
Normalized Frontier
Sem 1
Sem 2

Figure 4. The success percentage for all of the exploration strategies.

SEPTEMBER 2019

IEEE ROBOTICS & AUTOMATION MAGAZINE

IEEE Robotics & Automation Magazine - September 2019

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