Search methodologies for node recovery in robotic swarms

Groups of autonomous robots become increasingly useful as the mission complexity they can handle increases. However, in a mobile ad hoc network, there are continually communication failures due to changing environmental conditions and of course hardware problems, both temporary and permanent. For this work, we envision a heterogeneous robotic swarm with both "general" nodes that perform mission tasks, and "support" nodes that help maintain the connectivity of the communication network. At any given time, there are likely to be multiple network link failures, so the placement of support nodes becomes an optimization problem: where will the support nodes be most effective. In a realistic scenario, this optimization problem would be solved constantly as robots move around and the network topology changes, so the technique used must be both efficient, and close to optimal. This paper describes the study of three optimization methods particle swarm optimization, hill climbing, and tabu search to solve this problem. We find that particle swarm optimization provides the best solutions, but takes a little bit more time to execute than tabu search or hill climbing.