  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.
