Skip to content

Group Marching Tree: Sampling-Based Approximately Optimal Motion Planning on GPUs

Authors: Brian Ichter, Edward Schmerling, Marco Pavone

Published: 2017 (Conference Paper)

Source: IEEE International Conference on Robotic Computing (IRC)

Algorithm: GMT*

arXiv: 1705.02403

DOI: 10.1109/IRC.2017.7926542

Summary

GMT* adapts FMT*'s lazy dynamic-programming tree expansion for massively parallel execution on GPUs by replacing the sequential expansion of the single minimum-cost sample with simultaneous expansion of the entire group of active samples whose cost falls below an increasing threshold. This group approximation introduces a bounded suboptimality constant but eliminates sequential data structures and reduces thread divergence. Achieves ~10 ms planning on desktop GPUs and ~30 ms on embedded GPUs.

Abstract

This paper presents a novel approach, named the Group Marching Tree (GMT*) algorithm, to planning on GPUs at rates amenable to application within control loops, allowing planning in real-world settings via repeated computation of near-optimal plans. GMT*, like the Fast Marching Tree (FMT) algorithm, explores the state space with a "lazy" dynamic programming recursion on a set of samples to grow a tree of near-optimal paths. GMT*, however, alters the approach of FMT with approximate dynamic programming by expanding, in parallel, the group of all active samples with cost below an increasing threshold, rather than only the minimum cost sample. This group approximation enables low-level parallelism over the sample set and removes the need for sequential data structures, while the "lazy" collision checking limits thread divergence---all contributing to a very efficient GPU implementation. While this approach incurs some suboptimality, we prove that GMT* remains asymptotically optimal up to a constant multiplicative factor. We show solutions for complex planning problems under differential constraints can be found in ~10 ms on a desktop GPU and ~30 ms on an embedded GPU, representing a significant speed up over the state of the art, with only small losses in performance. Finally, we present a scenario demonstrating the efficacy of planning within the control loop (~100 Hz) towards operating in dynamic, uncertain settings.

Primary

Paper arxiv.org

Standard

arXiv Abstract 1705.02403 arXiv PDF 1705.02403 arXiv HTML 1705.02403 DOI 10.1109/IRC.2017.7926542

Alternate

ieeexplore.ieee.org ieeexplore.ieee.org stanfordasl.github.io PDF stanfordasl.github.io GitHub: StanfordASL/GMT github.com

Tags

  • Motion planning

  • Kinodynamic planning

  • Sampling-based planning

  • Real-time planning

  • Approximate optimality

  • GPU

  • Parallelized

  • GMT*

  • FMT*