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:
- Observation & Exploration: The robot moves randomly, taking 360-degree panoramic snapshots and recording visible unique objects.
- 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.
- Empirical Distance: These frequencies are converted into distances using a logarithmic function. High co-visibility implies a short distance.
- Multidimensional Scaling (MDS): This statistical technique translates the table of relative distances into a set of 2D coordinates.
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.
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