Visibility-based multi-agent deployment in orthogonal environments

Abstract

This paper addresses the problem of deploying a group of robotic agents equipped with omnidirectional vision in a simply connected orthogonal environment to achieve complete visibility. The agents are point masses with discrete-time first- order dynamics with no prior knowledge of the environment. Each agent can sense distances to the environment boundary and to other agents within line-of-sight. Communication is possible only between collocated agents. The agents operate asynchronously. The paper also addresses the problem of complete visibility deployment under the additional constraint that the visibility graph of the final agent locations is connected. We provide distributed algorithms that are guaranteed to solve the above problems if a sufficient number of agents are available. Remarkably, this number is identical to the number assuming complete prior knowledge of the environment. A final contribution of the paper is the characterization of the robustness properties of the algorithms to agent failures in the case of deployment with connectivity constraints.