Author: Andrew Keefe — **Author:** Andrew Keefe

Using multiple robots to search an area in order to generate a map is both faster and produces less errors than using a single robot, but there are many methods among the multiple agents to consider for them to work well together.

I developed a simple framework in Python to model agents and have them search a simple 2D map like the one shown below.

World map (yellow are walls, purple are open spaces)

Simulation Rules:

Robots start in the lower left corner at coordinate (9,1).
Each robot can “see” in the four adjacent directions up, down, left, right if a wall or an open space exists, and adds that information to its internal map.
If two or more robots are occupying the same grid location they combine their maps with each other.
Robots then decide which adjacent grid location to travel to, prioritizing unexplored grids over explored grids.
Simulation ends when one of the robots has a complete map or it times out.

The figure below shows a single robot, in blue, exploring 5 grid locations and generating its internal map. The green grid is the location the robot has decided to travel to next.

Single Robot vs Multiple Robots without Map Sharing

With a single robot the simulation averages over 400 steps. There are 53 grid squares and an optimal solution with one robot is 46 steps. The poor results are due to occasions when the robot gets stuck in an explored area and has trouble getting to an unexplored area. There were simulations where a robot required almost 2000 steps to complete the map.

Adding in multiple agents, still without map sharing, reduced the effects of a single robot getting stuck, though the more agents used the higher the cost. The figure below shows the number of agents and the corresponding average number of simulation steps required to complete the map.

Map Sharing

There are many methods for implementing map sharing. This simulation is rather ideal, in that the map combination occurs within the same simulation step as exploration so there’s no penalty, and only unexplored regions on a robots map are updated from other robots. Perception and localization were modeled as ideal, meaning there were no mistakes in the maps.

The figure below shows two maps being combined when one robot begins at grid (9,1) and the other at (9,9) and they meet in the middle and combine their maps.

Multi Robot Search with Map Sharing

For 2-20 agents I ran 500 simulations and calculated the mean number of simulation steps required to complete the map. Three agents produce the best results, as this is a relatively small map compared to the perception capability of the robots. These results, shown in the figure below, are weighted based on how many robots were used. As more and more robots are included, the inefficiency increases. One reason for this is because the robots all start in the same location. Otherwise the robots could be randomly spaced through the map and could converge on a complete map in only a few steps. It’s rare to distribute robots that way in real life however, and they tend to all originate from the same general location.

Observations

Improvements in decision making have been shown to improve the performance of exploration and mapping using distributed systems [1]. Though my algorithm uses a random-walk approach, other methods of exploration have been shown to have a large impact on performance.
My assumptions include error free localization and perception on the part of the robot agents. The simulation could be updated to utilize more realistic accuracies, perhaps based on an actual agent system. That way field experiments could be conducted to help validate the simulations, as with [2].
Communication between the agents was also simulated to be ideal. This often has a large impact on performance, as discussed in [1]. As range is increased beyond a single vertex, as in my experiment, I would expect an improvement in raw score, though for my simple map it may only reduce the most efficient number of agents from 3 to 2. A larger and more complex map should be developed in order to further test the framework and future algorithms.

Conclusions

Advances in the map sharing approaches when coupled with classic swarm architecture has been shown to provide a measurable reduction in the steps required to fully explore a given map. Simulations also show that, when the cost of operating multiple agents is taken into account, an optimal number of agents for the given map can be found.

References

1) Fox, D., Ko, J., Konolige, K., Limketkai, B., Schulz, D., & Stewart, B. (2006, July). Distributed Multirobot Exploration and Mapping. Proceedings of the IEEE, 94(7), 1325-1339.

2) Kegeleirs, M., Garzon, D., & Birattari, M. (2019). Random Walk Exploration for Swarm Mapping. Bruxelles: Institut de Recherches Interdisciplinaires et de Developpements en Intelligence Artificielle.

3) Wang, H., Jenkin, M., & Dymond, P. (2009). Graph Exploration with Robot Swarms. International Journal of Intelligent Computing and Cybernetics, 2(4), 818-845.