The Mercator Representation of Spatial Knowledge

Ernest DavisIJCAI 1983

Introduction

The MERCATOR system provides a framework for robots to construct "cognitive maps" of 2D environments from sequences of incomplete and noisy sensor readings. Developed to address the fundamental tension between local precision and global uncertainty, MERCATOR allows a machine to maintain precise local information—such as the exact width of a sidewalk—even when global information, like the robot's absolute coordinates within a city, remains vague. Traditional coordinate systems often fail in these scenarios by forcing precise values onto fuzzy data, leading to cascading errors. MERCATOR instead uses a hierarchical representation governed by formal truth-conditional semantics.

System Architecture

The MERCATOR architecture is designed to handle the transition from raw simulated data to a structured, persistent spatial representation.

The architectural structure of the MERCATOR system, showing the flow from simulation to the cognitive map.

As shown in Figure 1, the system consists of a simulator that provides vision and motion data, which is then processed by the "Matcher" and "Merger" components. These components are responsible for assimilating new observations into the "Cognitive Map," a hierarchical data structure that stores the robot's spatial knowledge. This structure allows the system to distinguish between physical boundaries and "knowledge edges"—the limits of what the robot has seen so far.

Spatial Representation and Methods

MERCATOR introduces several novel structural elements to represent spatial knowledge rigorously:

  • Bounds and Regions: Instead of simple lines, the system uses directed edges called "bounds" to indicate the "inside" of an object. A "region" is defined by a collection of these bounds and polygons.
  • Fuzz Ranges: To tolerate measurement errors, every length and orientation is stored as a range (e.g., "between 10 and 12 feet") rather than a single-point coordinate. This distinguishes "fuzz" (uncertainty) from "grain-size" (simplification error).
  • Joints and Hierarchy: Objects are linked via "joints" (relative perpendicular and parallel offsets) and organized in a Directed Acyclic Graph (DAG) based on containment. This hierarchy ensures that the robot only needs to process local data for most queries, maintaining computational efficiency.
A scene representation using polygons and directed bounds to indicate object orientation and containment.

Figure 4 illustrates how these polygons and bounds are used to define a scene. Arrowheads next to object names indicate the direction of the bounds, defining the spatial limits of features like roads and fields. This method allows for multi-resolution descriptions, such as treating a road as a 1D line for navigation but a 2D area for maintenance.

Evaluation and Key Results

The system was evaluated using simulated pastoral scenes containing fields, roads, sidewalks, and ponds. The input consisted of a sequence of "sensings" that the program matched and merged into its growing map. Key results include:

  • Computational Scalability: Search times grew slowly as the map size increased due to the containment hierarchy.
  • Robust Merging: The Matcher and Merger components successfully combined multiple fuzzy descriptions of the same area into a single, more accurate representation.
  • Qualitative Flexibility: MERCATOR proved capable of representing complex relationships that stymied earlier models, such as overlapping objects and multiply connected regions (objects with "holes").

Limitations and Future Work

Despite its strengths, MERCATOR has several limitations. It lacks a formal way to represent the absence of objects, relying instead on positive assertions. It is also strictly limited to 2D environments, leaving 3D challenges like multi-story buildings for future research. Additionally, the system assumes absolute compass orientation, a requirement that real-world robotic sensors often struggle to meet without significant drift.

Summary updated

BibTeX
@inproceedings{davis1983mercator,
  author = {Ernest Davis},
  title = {{The Mercator Representation of Spatial Knowledge}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {1983},
}
Figure