RG-Trees: Trajectory-Free Feedback Motion Planning Using Sparse Random Reference Governor Trees

Sampling based methods resulted in feasible and effective motion planning algorithms for high dimensional configuration spaces and complex environments. A vast majority of such algorithms as well as their application rely on generating a set of open-loop trajectories first, which are then tracked by feedback control policies. However, controlling a dynamic robot to follow the planned path, while respecting the spatial constraints originating from the obstacles is still a challenging problem. There are some studies which combine statistical sampling techniques and feedback control methods which address this challenge using different approaches. From the feedback control theory perspective, Reference Governors proved to be a useful framework for constraint enforcement. Very recently, Arslan and Koditschek (2017) introduced a feedback motion planner that utilizes Reference Governors that provably solves the motion planning problem in simplified spherical worlds. In this context, here we propose a "trajectory-free" novel feedback motion planning algorithm which combines the two ideas: random trees and reference governors. Random tree part of the algorithm generates a collision-free region as a set of connected simple polygonal regions. Then, reference governor part navigates the dynamic robot from one region to the adjacent region in the tree structure, ensuring it stays inside the current region and asymptotically reaches to the connected region. Eventually, our algorithm robustly routes the robot from the start location to the goal location without collision. We demonstrate the validity and feasibility of the algorithm on simulation studies.