Qualitative Map Learning Based on Co-visibility of Objects

Takehisa Yairi, Koichi Hori

Abstract

This paper proposes a unique map learning method for mobile robots based on the co-visibility information of objects—that is, whether two objects are visible at the same time from the robot's current position. The method estimates empirical distances among objects using a simple heuristic: a pair of objects observed together more frequently is likely located closer together. These distances are then used to compute object coordinates via Multidimensional Scaling (MDS). The results demonstrate that this method produces qualitatively accurate maps using only primitive information and remains robust against object recognition errors.

Introduction

In autonomous robotics, traditional mapping often relies on Simultaneous Localization and Mapping (SLAM), which requires high computational power to calculate precise metric coordinates. However, many tasks only require a qualitative understanding of the environment, such as knowing the relative layout of landmarks.

The proposed CoviMap algorithm addresses this by building maps from scratch using "primitive" co-visibility data. By noticing which objects appear in the same frame most often, a robot can infer the spatial structure of its environment without needing to know its own exact location or using complex distance sensors.

Methodology

The CoviMap approach is built on the philosophical pillar that temporal and spatial proximities are approximately equivalent for a randomly exploring agent. The process follows four main stages:

  1. Observation & Exploration: The robot moves randomly, taking 360-degree panoramic snapshots and recording visible unique objects.
  2. Co-visibility Frequency: It calculates the Jaccard coefficient ($f_{i,j}$) for every pair of objects, representing the ratio of simultaneous sightings to total sightings.
  3. Empirical Distance: These frequencies are converted into distances using a logarithmic function. High co-visibility implies a short distance.
  4. Multidimensional Scaling (MDS): This statistical technique translates the table of relative distances into a set of 2D coordinates.
The CoviMap workflow: from raw panoramic images to an estimated qualitative map.

If certain objects are never seen together, the system employs a Triangle Inequality Constraint (TIC) to estimate their distance based on intermediate objects, ensuring the map remains cohesive.

Experimental Setup

The method was validated using the Cyberbotics WEBOTS simulator. The environment consisted of a 1.5m x 1.5m field populated with 5 to 30 unique cylindrical objects. The robot was equipped with a panoramic camera and basic proximity sensors for obstacle avoidance. This setup allowed researchers to test the behavioral approach to data collection without the noise of complex real-world physics.

Results and Discussion

The core heuristic—that frequency of co-visibility correlates with spatial proximity—was confirmed through experimental data. As shown in the relationship between co-visibility and squared distance, objects seen together more often consistently reside closer to one another.

Empirical relationship between co-visibility frequency and the squared distance between objects.

Qualitative Accuracy and Robustness

Rather than metric precision, the study measured "Triangle Orientation" accuracy. If three objects are arranged counter-clockwise in reality, the map should reflect that same order. Key findings include:

  • Consistent Performance: Orientation error converged to a narrow range of 2.5% to 3.0% after approximately 1,000 steps, regardless of object density.
  • Rapid Learning: The fundamental qualitative structure of the map was captured within the first few hundred steps.
  • Error Tolerance: The system proved resilient to "brain farts"—recognition errors where the robot fails to see or misidentifies an object. Even with a 10% mis-recognition rate, the statistical nature of MDS smoothed out these glitches over time.

Conclusion

CoviMap demonstrates that useful spatial knowledge can be extracted from very simple visual cues. While the current model assumes a 360-degree field of view and uniform exploration, it provides a robust foundation for qualitative navigation. Future work will focus on adapting the algorithm for robots with narrower fields of view and developing methods to handle dynamic environments where objects may move over time.

Summary updated

Abstract

This paper proposes a unique map learning method for mobile robots based on the co-visibility information of objects i.e., the information on whether two objects are visible at the same time or not from the current position. This method first estimates empirical distances among the objects using a simple heuristics - "a pair of objects observed at the same time more frequently is likely to be located more closely together". Then it computes all the coordinates of the objects by multidimensional scaling (MDS) technique. In the latter part of this paper, it is shown that the proposed method is able to learn qualitatively very accurate maps though it uses only such primitive information, and that it is robust against some kinds of object recognition errors.
BibTeX
@inproceedings{yairi2003qualitative,
  author = {Takehisa Yairi and Koichi Hori},
  title = {{Qualitative Map Learning Based on Co-visibility of Objects}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2003},
  url = {https://openreview.net/forum?id=r1ZzJNzd-H},
}
Figure