Distributed Path Planning for Collective Transport Using Homogeneous Multi-robot Systems

We present a scalable distributed path planning algorithm for transporting a large object through an unknown environment using a group of homogeneous robots. The robots are randomly scattered across the terrain and collectively sample the obstacles in the environment in a distributed fashion. Given this sampling and the dimensions of the bounding box of the object, the robots construct a distributed configuration space. We then use a variant of the distributed Bellman-Ford algorithm to construct a shortest-path tree using a custom cost function from the goal location to all other connected robots. The cost function encompasses the work required to rotate and translate the object in addition to an extra control penalty to navigate close to obstacles. Our approach sets up a framework that allows the user to balance the trade-off between the safety of the path and the mechanical work required to move the object. The path is optimal given the sampling of the robots and user input parameters. We implemented our algorithm in both simulated and real-world environments. Our approach is robust to the size and shape of the object and adapts to dynamic environments.