Wireless Sensor and Actuator Networks: Algorithms and Protocols for Scalable Coordination and Data Communication

9.8 DISPERSION OF AUTONOMOUS MOBILE ROBOTS

McLurkin and Smith (2004) studied dispersion of autonomous mobile robots. The problem is to disperse a large swarm of robots into a space of interest to increase their area coverage while maintaining their network connectivity. The main ideas of their algorithms are as follows. Robots move opposite to vector sum of their forces toward neighbors. Frontier robots move forward. To prevent disconnections and oscillations, and preserve connectivity with two children, leaf robots also preserve coverage of initial area and keep the near robots stationary while the frontier moves.

Two dispersion algorithms, called disperseUniformly and frontierGuidedDispersion, were proposed in McLurkin and Smith (2004). These algorithms are run alternately on the swarm of robots. The disperseUniformly is to spread robots evenly, while the frontierGuidedDispersion algorithm is to direct robots toward unexplored areas. In the disperseUniformly algorithm, the basic idea is to direct robots using boundary conditions to limit the dispersion. Physical walls and a maximum dispersion distance between any two robots, r_safe, are used as boundary conditions to help prevent the swarm from spreading too thin and fracturing into multiple disconnected components. Each robot is directed away from the vector sum of the relative positions {p₁, …, p_c} of its c closest neighbors. The magnitude of the velocity vector is:

where I_i is an indicator function and v_max is the maximum ...