Reconfiguration algorithms for mobile robotic networks

For a deployed mobile robotic network to function usefully, the robots should have the capability to adjust their positions, while maintaining the network connectivity. In this paper, we present algorithms that allows a robot to decide when it is feasible for it to move to a desired point by adjusting its own positions (and the positions of some other robots in the network), while maintaining all the network connectivity constraints. Under the assumption of a disc model of communication, we show that the problem can be formulated as a convex optimization (or feasibility) problem (actually a second order cone program). Thus, the problem can be solved in polynomial time by centralized interior point algorithms. However, this requires the robot to have knowledge of the position of all the nodes in the network. Our main contribution is the development of an incremental algorithm, that solves the feasibility problem (of whether the robot can move to its desired goal) by obtaining the information about the position of the robots and their immediate neighbors only if they are required to move. We present simulation results comparing the performance of the centralized algorithm with the incremental algorithm for randomly generated networks. From simulation results, we observe that the time required by the incremental algorithm to solve the feasibility problem is relatively independent of the size of the network.