Any-com collision checking: Sharing certificates in decentralized multi-robot teams

We present an any-com algorithm that enables a decentralized team of robots to share the work of collision checking while each robot independently calculates its own motion plan. In our method “safety-certificates” (i.e., bounds on the collision-free subspace around each collision-checked point [1]), are shared among the team so that all robots can benefit from their encoded knowledge. Future points drawn from within a certificate are guaranteed to be safe; therefore, sharing certificates among team members reduces collision checking for all robots. Experiments demonstrate that our algorithm scales well vs. both team size and vs. communication quality.