  We provide a distributed coordination paradigm that enables scalable and
near-optimal joint motion planning among multiple robots. Our coordination
paradigm contrasts with current paradigms that are either near-optimal but
impractical for replanning times or real-time but offer no near-optimality
guarantees. We are motivated by the future of collaborative mobile autonomy,
where distributed teams of robots will coordinate via vehicle-to-vehicle (v2v)
communication to execute information-heavy tasks like mapping, surveillance,
and target tracking. To enable rapid distributed coordination, we must curtail
the explosion of information-sharing across the network, thus limiting robot
coordination. However, this can lead to suboptimal plans, causing overlapping
trajectories instead of complementary ones. We make theoretical and algorithmic
contributions to balance the trade-off between decision speed and optimality.
We introduce tools for distributed submodular optimization, a diminishing
returns property in information-gathering tasks. Theoretically, we analyze how
local network topology affects near-optimality at the global level.
Algorithmically, we provide a communication- and computation-efficient
coordination algorithm for agents to balance the trade-off. Our algorithm is up
to two orders faster than competitive near-optimal algorithms. In simulations
of surveillance tasks with up to 45 robots, it enables real-time planning at
the order of 1 Hz with superior coverage performance. To enable the
simulations, we provide a high-fidelity simulator that extends AirSim by
integrating a collaborative autonomy pipeline and simulating v2v communication
delays.
