IEEE Robotics & Automation Magazine - September 2019 - 79

leads to the second objective of this contribution, namely, presenting a set of findings that are reproducible by a third party.
In light of the increasing attention measurable robotics is
attracting, this article represents a first attempt to present a
reproducible study based on Gazebo.
Motivation
Consider a service robot that must deliver an item in an
unknown environment, for example, an office floor it never
entered before and about which it has no prior knowledge
other than the fact that it is an office environment. For
example, the robot may have to deliver an envelope to the
copy room or put a package on the desk in Mr. Chairman's
office. Not having preliminary knowledge about where these
places are located, the robot should then explore the environment until it recognizes it has reached the desired site.
Next, it should deposit the goods it is supposed to deliver,
travel back to the entrance, and leave. Exploration is an integral component of this task; if the robot is doing this job as
part of a series of deliveries, it is important to finish the task
quickly to increase the number of tasks completed in a set
amount of time.
Exploration is one of the fundamental abilities of an autonomous robot operating in an unknown environment. In its
most studied form, this means building a spatial model of the
environment, and central to the task is the decision process of
determining where to move next. A classic early solution to
this problem is frontier-based exploration [1], an approach
inherently tied to using occupancy grid maps to represent
space. In this case, a frontier is defined as the boundary
between explored and unexplored space, and the rationale is
that, by moving toward large frontiers, a robot will be quicker
in discovering additional unknown areas.
Other possible approaches are based on random exploration or variations of the frontier-based approach. For
example, distance to frontiers may be considered to break
ties between equally large frontiers. In many of these
approaches, the temporal dimension is not explicitly considered. That is, while heuristics are introduced to expedite
the exploration process, time is most often not an explicit
metric or constraint.
In this article, we deviate from the existing literature by
considering three modifications to the basic setting.
1) First, we assume the robot does not build a metric model of
the environment, such as an occupancy grid map, but rather a topological model with semantic annotations. This is
called a toposemantic model and will be further discussed
later.
2) Second, the robot's objective is not to build a spatial model
per se but to explore the unknown environment until a target location is discovered. The model is functional regarding this objective (e.g., to avoid revisiting areas already
explored). To this end, we assume that the target location is
provided in a format compatible with the sensor capabilities of the robot, so that it can detect when the desired site
has been reached.

3) Finally, we introduce a temporal constraint, i.e., a time T
such that the exploration task is considered not solved if,
after time T, the robot has still not reached the location it
is seeking.
Exploration is a fundamental ability in mobile robotics
that has been extensively studied over the last three decades.
With the current explosive growth in robotics applications,
the area continues to increase, particularly in terms of extensions and special cases of exploration not studied earlier. In
this article, we consider the topic of efficient exploration using
a semantic topological-oriented map. Efficient, in this case,
means that a robot is expected to complete its assigned task
within a given temporal deadline. To accomplish this, the
robot does not build a metric map but rather incrementally
constructs a topological model, where the environment is
represented by a graph.
We opt for topological models for various reasons. First, it
is known that humans make use of topological models for
spatial awareness and navigation [2]. Second, there is an interest in moving away from representations like occupancy grid
maps that are tightly integrated with range finders. Finally,
topological maps are more compact and use less memory.
To handle temporal deadlines, at least two approaches are
available. First, we could combine multiple objectives (e.g.,
time, safety, and explored area) into a single objective function, for example, with a linear combination; second, we
could plan using standard methods like Markov decision processes. Instead, we rely on our recent planning algorithms
using constrained Markov decision processes (CMDPs). This
approach allows optimizing with respect to one objective (for
example, reaching a goal), while satisfying one or more constraints, such as time to completion and probability of collision. It has the advantage of not requiring a combination of
intrinsically heterogeneous quantities.
Related Work
Exploration is one of the main challenges for robots facing a
new environment, and there is no consensus on the best strategy and representation. Ultimately, these issues are application specific and still constitute an active research domain, as
witnessed by continued publications in this area. Vidal et al.
recently studied robotic underwater exploration [3], while
Dang et al. proposed a method using the visual saliency of
objects and the environment to drive the robot toward salient
objects using a 3D occupancy map [4]. Other authors have
recently proposed using deep reinforcement learning, including topological and structural information about a building,
to improve exploration [5].
While metric maps and occupancy grid maps are common in multiple applications, new approaches have been
developed, and topological and semantic maps have shown
the potential for use in complex applications (see [6] for a relatively recent survey). Multiple labeling methods and scene
recognition [7] have been proposed, with the main goal of
getting a good understanding of the objects and their relationships [8], [9]. For indoor environments, Quattrini et al. used
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