  This paper considers the problem of planning trajectories for a team of
sensor-equipped robots to reduce uncertainty about a dynamical process.
Optimizing the trade-off between information gain and energy cost (e.g.,
control effort, distance travelled) is desirable but leads to a non-monotone
objective function in the set of robot trajectories. Therefore, common
multi-robot planning algorithms based on techniques such as coordinate descent
lose their performance guarantees. Methods based on local search provide
performance guarantees for optimizing a non-monotone submodular function, but
require access to all robots' trajectories, making it not suitable for
distributed execution. This work proposes a distributed planning approach based
on local search and shows how lazy/greedy methods can be adopted to reduce the
computation and communication of the approach. We demonstrate the efficacy of
the proposed method by coordinating robot teams composed of both ground and
aerial vehicles with different sensing/control profiles and evaluate the
algorithm's performance in two target tracking scenarios. Compared to the naive
distributed execution of local search, our approach saves up to 60%
communication and 80--92% computation on average when coordinating up to 10
robots, while outperforming the coordinate descent based algorithm in achieving
a desirable trade-off between sensing and energy cost.
