RRT-blossom: RRT with a local flood-fill behavior

This paper proposes a new variation of the RRT planner which demonstrates good performance on both loosely-constrained and highly-constrained environments. The key to the planner is an implicit flood-fill-like mechanism, a technique that is well suited to escaping local minima in highly constrained problems. We show sample results for a variety of problems and environments, and discuss future improvements

I. Introduction

Path and motion planning has been a much studied problem over the past two decades, whose appeal stems from its applicability to many diverse areas, spanning industrial robot locomotion, object manipulation, autonomous actors in computer animation, and even protein folding and drug design. In the past decade two approaches have become eminently popular: Probabilistic Roadmaps (PRMs) [1] and Rapidly-expanding Random Trees (RRTs) [2], both of which are based on stochastic search strategies.