Multi-Robot Motion Planning in Confined Spaces

 
hardwareRobots2.png
 

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.

 
 Push-Swap-Wait Algorithm

Push-Swap-Wait Algorithm

 

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.

 Multi-Robot Planning in 3D Cluttered Space

Multi-Robot Planning in 3D Cluttered Space

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.