Kavraki Lab

A Scalable and Distributed Platform for High-Dimensional Motion Planning

High-dimensional problems arising from complex robotic systems test the limits of current motion planners and require the development of efficient distributed motion planners that take full advantage of the available computational resources.

DSRT is a high-performance distribution of the Sampling-based Roadmap of Trees (SRT) motion planner. DSRT’s design is based on a multiple masters, multiple clients distribution. The clients are responsible for milestone and edge computations while the masters ensure that the load is distributed as evenly as possible among the clients. The masters arbitrate milestone ownership, edge selection, maintain the connected component data structure, and coordinate the activities of all the processors.

The distribution remains highly efficient obtaining near linear speedup for message-passing systems even when the computation is distributed over hundreds of processors. DSRT makes it possible to solve very high-dimensional problems that cannot be efficiently addressed with existing motion planners.

DSRT distribution architecture
Fig. DSRT is based on a multiple masters, multiple clients distribution, where several master processors cooperate with each-other to distribute the computation evenly among the client processors. DSRT achieves near linear speedup on hundreds of processors.