Topological Mapping and Navigation in Real-World Environments

We introduce the Hierarchical Hybrid Spatial Semantic Hierarchy (H2SSH), a hy-
brid topological-metric map representation. The H2SSH provides a scalable rep-
resentation of both small and large structures in the world, providing natural de-
scriptions of a hallway lined with offices as well as a cluster of buildings on a
college campus. By considering the affordances in the environment, we identify a
division of space into three distinct classes: path segments afford travel between
places at their ends, decision points present a choice amongst incident path seg-
ments, and destinations typically exist at the start and end of routes.

Constructing an H2SSH map of the environment requires understanding both its
local and global structure. We present a place detection and classification algo-
rithm to create a semantic map representation that parses the free space in the local
environment into a set of discrete areas representing features like corridors, inter-
sections, and offices. Using these areas, we use a probabilistic topological simul-
taneous localization and mapping algorithm based on lazy evaluation to estimate
a probability distribution over possible topological maps of the global environ-
ment. After construction, an H2SSH map provides the necessary representations
for navigation through large-scale environments. The local semantic map provides
a high-fidelity metric map suitable for motion planning in dynamic environments,
while the global topological map is a graph-like map that allows for route planning
using simple graph search algorithms.

For navigation, we have integrated the H2SSH with Model Predictive Equilib-
rium Point Control (MPEPC) to provide safe and efficient motion planning for
our robotic wheelchair, Vulcan. However, navigation in human environments en-
tails more than safety and efficiency, as human behavior is further influenced by
complex cultural and social norms. We show how social norms for moving along
corridors and through intersections can be learned by observing how pedestrians
around the robot behave. We then integrate these learned norms with MPEPC
to create a socially-aware navigation algorithm, SA-MPEPC. Through real-world
experiments, we show how SA-MPEPC improves not only Vulcan's adherence to
social norms, but the adherence of pedestrians interacting with Vulcan as well.