Region-Guided and Sampling-Based Tree Search for Motion Planning With Dynamics

This paper presents a motion planner, termed Guided Sampling Tree (GUST), geared toward mobile robots with nonlinear dynamics and nonholonomic constraints operating in complex environments. GUST expands a tree of collision-free and dynamically feasible motions and uses a workspace decomposition to partition the motion tree into groups. GUST relies on shortest path distances in the workspace decomposition and penalty factors to identify candidate groups, which could result in rapid expansions of the motion tree toward the goal. The initial workspace decomposition and the partition of the motion tree are further refined during the search in order to improve the group selection and the motion-tree expansion. Experimental validation is provided using ground and aerial-vehicle models operating in complex environments. Comparisons with related work show statistically significant speedups with large effect sizes.