Methods for Parallel Computation of Motion Planning Structures

In this work, we show how to effectively combine a sampling-based method primarily designed for multiple query motion planning (Probabilistic Roadmap Method - PRM) with sampling-based tree methods primarily designed for single query motion planning (Expansive Space Trees, Rapidly Exploring Random Trees, and others) in a novel planning framework that can be efficiently parallelized. Our planner not only achieves a smooth spectrum between multiple query and single query planning but it combines advantages of both. Experiments show that our planner is capable of solving problems that cannot be addressed efficiently with PRM or single-query planners. A key advantage of the planner is that it is significantly more decoupled than PRM and sampling-based tree planners. Exploiting this property, we designed and implemented a parallel version of our planner. Our experiments show that our planner distributes well and can easily solve high-dimensional problems that exhaust resources available to single machines and cannot be addressed with existing planners.


Contribution

  • SRT provides a platform for efficiently solving high-dimensional motion planning problems.
  • SRT effectively combines two successful motion planning paradigms:
    • a powerful sampling-based method primarily designed for multiple query planning, Probabilistic RoadMap (PRM) method and
    • sampling-based tree methods that were primarily designed for single query planning, such as Expansive Space Trees (ESTs), Rapidly Exploring Random Trees (RRTs), and others.
  • SRT provides a smooth spectrum between single query and multiple query planning that combines the advantages of both.
  • SRT creates a roadmap of trees that integrates the global sampling properties of PRM with the local sampling properties of single query tree-based planners.
  • SRT's integration scheme results in a motion planner that is faster and more robust than PRM and single query tree-based planners, i.e., RRT, EST.
    • SRT offers the sampling-based tree planners it uses easier tree connections, since the candidate edges are selected from the closest neighbor clustering.
    • SRT retains the global sampling property of PRM and thus efficient sampling-based local expansion methods, such as RRT and EST, do not get trapped.
    • SRT significantly reduces the computational time required to solve high-dimensional motion planning problems. In many instances, SRT solves high-dimensional motion planning problems in a matter of a few minutes while other motion planners require several hours of computation.
  • SRT is considerably more decoupled than other planners, which allows for an efficient parallelization.


Results


Some common motion planning problems.


Experiments show that SRT is capable of solving problems that cannot be addressed efficiently with PRM or single-query planners even in the single-processor case. Furthermore, it has been experimentally shown that SRT distributes well and can easily solve high-dimensional problems that exhaust resources avaialble to single-machines and cannot be addressed with existing planners.

Check some videos where you can see paths computed by SRT for multiple rigid objects:

These are non-smoothed paths for kinematic problems with many degrees of freedom.


Related Publications


People Involved