Slides
This paper presents a self-stabilizing distributed algorithm to recover a large number of robots safely in a single location. In our previous work, we designed a distributed algorithm, called DMLST, that constructed a maximum-leaf spanning tree for physical routing, such that interior robots remained stationary and leaf robots moved. However, DMLST algorithm failed in practice when the robots lost their communication frequently. In this paper, we extend our approach to k-DMLST recovery algorithm. This algorithm provides that each robot is connected to the goal location through k trees instead of one tree. This redundancy provides stronger network connectivity during recovery. We also propose an efficient navigation algorithm for the motion of robots which guarantees forward progress during the recovery. We test k-DMLST recovery algorithm and compare with basic recovery and DMLST recovery algorithms. While basic recovery algorithm fails in all experiments, and DMLST recovery is not successful in few trials. However, the k-DMLST recovery efficiently recovers all robots in simulations and more than 90% of robots in a real experiment.