Qualitative relational mapping and navigation for planetary rovers

• Large scale spaces can be mapped by mobile robots using qualitative relationships.
• Allows mobile robots to determine landmark positions without global information.
• Qualitative relations can be extracted from sets of monocular images.
• Mapped spaces can be re-traversed using a graph-based approach.
• Performance is evaluated using Monte Carlo tests on randomly generated maps.

This paper presents a novel method for qualitative mapping of large scale spaces which decouples the mapping problem from that of position estimation. 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. This process allows a mobile robot to extract information about landmark positions using a set of minimal sensors in the absence of GPS. A novel measurement method based on camera imagery is presented which extends previous work from the field of Qualitative Spatial Reasoning. A Branch-and-Bound approach is taken to solve a set of non-convex feasibility problems required for generating off-line operator lookup tables and on-line measurements, which are fused into the map using an iterative graph update. 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 a data-driven simulation is presented for a robot traversing the Jet Propulsion Laboratory Mars Yard while building a relational map. These results demonstrate that the system can be effectively used to build a map sufficiently complete and accurate for long-distance navigation as well as other applications.