  This paper presents a novel method for qualitative mapping of large scale
spaces. The proposed framework makes use of a graphical representation of the
world in order to build a map consisting of qualitative constraints on the
geometric relationships between landmark triplets. A novel measurement method
based on camera imagery is presented which extends previous work from the field
of Qualitative Spatial Reasoning. Measurements are fused into the map using a
deterministic, iterative graph update. A Branch-and-Bound approach is taken to
solve a set of non-convex feasibility problems required for generating on-line
measurements and off-line operator lookup tables. A navigation approach for
travel between distant landmarks is developed, using estimates of the Relative
Neighborhood Graph extracted from the qualitative map in order to generate a
sequence of landmark objectives based on proximity. Average and asymptotic
performance of the mapping algorithm is evaluated using Monte Carlo tests on
randomly generated maps, and data-driven simulation results are presented for a
robot traversing the Jet Propulsion Laboratory Mars Yard while building a
relational map. Simulation results demonstrate an initial rapid convergence of
qualitative state estimates for visible landmarks, followed by a slow tapering
as the remaining ambiguous states are removed from the map.
