Message-passing strategy for decentralized connectivity maintenance in multiagent surveillance

In multiagent surveillance missions, a group of agents monitors some points of interest to provide situational awareness. For agents with local communication capabilities, one way to transmit the surveillance information to a base is streaming by the instantaneous data via multihop communications over a connected network. However, a connected communication network may become disconnected if some agents leave the surveillance area (for example, for refueling). This paper presents a locally applicable, efficient, and scalable strategy that guarantees a connected communication network between the baseandthe agentsinthe face ofany agent removal. The proposed decentralized strategy is based on a sequence of local replacements, which are initiated by the agent leaving the network. It is shown that the replacement sequence always ends with the relocation of an agent, for which the absence from its current position does not disconnect the network. Furthermore, the optimality (that is, the minimum number of replacements) of the proposed scheme is improved by incorporating a local criticality notion in the decision mechanism. Finally, the cases are considered in which some agents are not allowed to execute a replacement, and it is shown that the proposed strategy maintains a connected communication network, even in the presence of such constraints.