Sensor-based Random Graph for multi-robot exploration

Image This video shows simulations and experiments of the SRG (Sensor-based Random Graph) algorithm for multi-robot exploration. The robots are equipped with a laser range-finder. Experiments with small-scale robots are showed.

The Multi-SRG method is a decentralized cooperative exploration strategy for mobile robots. A roadmap of the explored area, with the associate safe region, is built in the form of a compact data structure, called Sensor-based Random Graph. This is incrementally expanded by the robots by using a randomized local planner which automatically realizes a trade-off between information gain and navigation cost. Connecting structures, called bridges, are incrementally added to the graph to create shortcuts and improve the connectivity of the roadmap. Decentralized cooperation and coordination mechanisms are used so as to guarantee exploration efficiency and avoid conflicts. Simulations are presented to show the performance of the proposed technique.

The video is a summary of [1],[2],[3].

See also the exploration page for an overview on the topic.


  1. A. Franchi, Freda, L., Oriolo, G., and Vendittelli, M., A decentralized strategy for cooperative robot exploration, in ACM International Conference Proceeding Series, Proceedings of the 1st international conference on Robot communication and coordination, Athens, Greece, 2007, vol. 318.
  2. A. Franchi, Freda, L., Marchionni, L., Oriolo, G., and Vendittelli, M., Decentralized cooperative exploration: Implementation and experiments, in 10th Int. Conf. on Intelligent Autonomous Systems, Baden-Baden, Germany, 2008, pp. 348-355.
  3. A. Franchi, Freda, L., Oriolo, G., and Vendittelli, M., The Sensor-based Random Graph Method for Cooperative Robot Exploration, IEEE/ASME Transaction on Mechatronics, vol. 14, no. 2, pp. 163-175, 2009.