Communication-Aware Multi-robot Coordination with Submodular Maximization

Abstract

Submodular maximization has been widely used in many multi-robot task planning problems including information gathering, exploration, and target tracking. However, the interplay between submodular maximization and communication is rarely explored in the multi-robot setting. In many cases, maximizing the submodular objective may drive the robots in a way so as to disconnect the communication network. Driven by such observations, in this paper, we consider the problem of maximizing submodular function with connectivity constraints. Specifically, we propose a problem called Communication-aware Submodular Maximization (CSM), in which communication maintenance and submodular maximization are jointly considered in the decision-making process. One heuristic algorithm that consists of two stages, i.e. topology generation and deviation minimization is proposed. We validate the formulation and algorithm through numerical simulation. We find that our algorithm on average suffers only slightly performance decrease compared to the pure greedy strategy.