Approaches for heuristically biasing RRT growth

This paper presents several modifications to the basic rapidly-exploring random tree (RRT) search algorithm. The fundamental idea is to utilize a heuristic quality function to guide the search. Results from a relevant simulation experiment illustrate the benefit and drawbacks of the developed algorithms. The paper concludes with several promising directions for future research.

1 Introduction

Rapidly-exploring random trees (RRT) have been shown to provide an efficient method for solving planning problems with kino-dynamic constraints [5]. Frazzoli adapted RRTs for real time planning for an autonomous helicopter operating in the presence of moving obstacles [3]. More recently, Bruce adapted RRTs for use with a robotic soccer team [2]. In both of these examples, there is only a binary evaluation of whether space is free or impassable. In many applications, however, it is important to consider a continuum of costs between completely free space and impassable obstacles. This is particularly relevant in the case of planning for outdoor mobile robots where terrain characteristics vary greatly. Algorithms such as D* [6] account for terrain variability but they require a discretization of the state and action space which may be infeasible for some problems. Figure 1: The RRT Algorithm.