Multi-Robot Motion Planning in Confined Spaces

This work builds off the Push-Swap-Wait algorithm presented by Dexter Scobee and Adam Wiktor in their thesis [PDF]. Scobee, Wiktor, and the LAIR worked to formalize this decentralized and complete algorithm for multi-robot motion planning in confined spaces, test it in hardware on the Jaguar Lite platform, and presented the results at the IROS 2014 conference.

The Push-Swap-Wait algorithm is a scalable, decentralized, and complete approach for multi-robot motion planning in confined spaces. The algorithm decomposes an environment into a tree of discrete positions. The proof is given for cases where the environment can be expressed as a tree with more leaf nodes than the number of robots navigating through it. Each robot independently computes its plan and communicates with nearby robots to share information.

Preliminary work has focused on building paths using a probabilistic road map (PRM) algorithm. Robots then randomly enter the environment at one hub with a desired destination, and randomly choose whether to follow the previously made path for this environment or to try to make a new path using PRM. If the path it makes improves upon the original one, it swaps out the old highway for this new one. A video of this simulation is shown here.

Starting Spring 2017, LAIR has been using Genetic Programming (GP) to generate Multi-Robot Motion Planning (MRMP) algorithms. The generated algorithms are decentralized and local. Unlike most other MRMP algorithms, the generated algorithms do not only solve individual scenarios; the generated algorithms are general enough to solve most MRMP scenarios. We compare the performance of the GP generated MRMP algorithms to Push-Swap-Wait, another MRMP algorithm developed by LAIR.