ANCHOR - Self-configuring robotic network

Abstract

A challenging task for a robotic radio network is to establish the connectivity among a set of entities (humans or radio nodes) in an unknown environment with minimum number of robots. The main difficulty is that the locations of the entities and the radio connectivities between the physical locations are not known in advance. We represent the problem by a topological graph of locations with known access links but unknown radio links (to be discovered dynamically) and develop a novel ANCHOR algorithm for a set of distributed autonomous robots to self-organize a radio network to connect the given entities using the least number of robots. We prove in theory that the algorithm is complete and only requires robots to travel O(n <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sup> ) nodes in a graph size of n. We also experiment the algorithm in simulation and the results shows a better performance with the use of increasing number of robots.