Introduction
In the mid-1990s, autonomous mapping typically required expensive robotic platforms equipped with high-precision sensors. This paper explores an alternative approach: utilizing a "troupe" of small, low-cost robots to map unknown environments. The primary challenge in this context is managing the high levels of uncertainty stemming from noisy infrared (IR) sensors and significant odometry drift. To address this, the authors propose a mathematical framework based on possibility and necessity theory, which allows for a more nuanced representation of spatial knowledge compared to traditional probabilistic methods.
The Problem of Uncertainty and Ignorance
Standard probabilistic occupancy grids often struggle to distinguish between a cell that is likely empty and a cell about which the robot has no information. In a single-value system, a probability of 0.5 is ambiguous. The authors tackle this by employing two distinct measures for each grid cell:
- Necessity ($N$): The degree of certainty that an obstacle exists.
- Possibility ($\Pi$): The degree to which it is possible that an obstacle exists.
This dual-measure system allows for the explicit representation of "ignorance." At the start of an exploration mission, every cell is initialized with $N=0$ and $\Pi=1$, signifying total ignorance. As robots collect data, they update these values to reflect their findings, effectively separating the concepts of "known empty space" from "unexplored space."
Methods and Error Modeling
The research utilizes a fleet of simple robots (Figure 1) that rely on basic IR sensors and odometry. Because these sensors are prone to error, the researchers developed a statistical model of robot movement. They found that position error grows proportionally to distance traveled and turns made, forming an "error rectangle."
When a robot detects a wall, it does not simply mark a single point on the grid. Instead, it projects a "pyramid" of necessity values. The certainty is highest at the estimated center of the detection and tapers off toward the edges of the error rectangle. This "fuzzy" propagation naturally incorporates the robot's positional uncertainty into the global map.
Cooperative Communication and Map Fusion
The system employs a decentralized "gossip" protocol to share information. Robots move through the environment using various behavioral modes—Anxious, Normal, or Routine—and exchange their perceived maps whenever they encounter one another. This strategy treats information as a commodity. Even if individual robots fail or are lost, the collective map can be recovered as long as the data was shared with a peer that eventually returns to the base station. The host computer then fuses these partial maps using computationally efficient grid-based update rules (using max for necessity and min for possibility).
Key Results and Limitations
Experimental trials characterized the physical drift of the robots, finding an average error rectangle of 2.5 inches by 11 inches over a 10-foot straight run. In simulated office environments, the system successfully generated global maps from multiple robots. These maps clearly delineated the environment's layout, with certainty levels (represented by grey degradation) decreasing as robots moved further from their starting points.
Despite its success, the system has notable limitations:
- Orthogonal Constraint: The current logic is restricted to environments with walls at 90-degree angles.
- Sensor Range: The IR sensors have limited range and accuracy compared to modern Lidar systems.
Future work aims to move toward contour-based mapping and higher-level semantic understanding, such as identifying doors or corners, to improve the robustness of the generated maps.
Summary updated