The Millibots Project

[ The Millibots | Localization | Example Scenario ]


Mapping and Exploration

The ability for a single robot to map any significant area is difficult, especially for robots at this scale. Even with its long-range sonars, the Millibot is limited to a detection range of only about 2 meters in a relatively tight cone. However, a group of Millibots can be equipped with similar sensors to cover more area than a single robot and in less time. During operation, each robot collects information locally about its surroundings. This data is transmitted to the team leader where it is used to build a local map centric to that robot. The team leader can utilize local map information to direct the Millibot around obstacles, investigate anomalies or generate new paths. The team leader can also merge the information from several local maps into a single global map to provide a complete view of the environment to the user.

We are using an occupancy grid method with a Bayesian update rule to combine sensor readings from different robots and from different time instances. In an occupancy grid, the environment is divided into homogeneous cells. For each cell, a probability of occupancy is stored. An occupancy value of zero corresponds to a free cell, a value of one corresponds to a cell occupied by an obstacle. Initially, nothing is known about the environment and all the cells are assigned a value of 0.5 (equally likely to be occupied or free).

The mapping algorithm uses a Bayesian update rule:

Equation above updates the occupancy probability for cell c, , based on the current sensor reading, , and the a priori probability, . Any sensor that can convert its data into a probability that a particular cell is occupied can be merged into the same map. This means that data generated by a short-range proximity detector can be merged with data from a sonar range module or even a camera.

Figure 7 represents an occupancy grid generated from a group of Millibots and a single team leader mapping a small room. For this experiment, each Millibot was equipped with a five-element proximity detector and a single sonar ranging module. The maps of each robot were merged to generate a complete map of the room.



Figure 7: Collaborative Mapping.




[ The Millibots | Localization | Example Scenario ]