Combining a Probabilistic Sampling Technique and Simple Heuristics to Solve the Dynamic Path Planning Problem

Probabilistic sampling methods have become very popular to solve single-shot path planning problems. Rapidly-exploring Random Trees (RRTs) in particular have been shown to be very efficient in solving high dimensional problems. Even though several RRT variants have been proposed to tackle the dynamic replanning problem, these methods only perform well in environments with infrequent changes. This paper addresses the dynamic path planning problem by combining simple techniques in a multi-stage probabilistic algorithm. This algorithm uses RRTs as an initial solution, informed local search to fix unfeasible paths and a simple greedy optimizer. The algorithm is capable of recognizing when the local search is stuck, and subsequently restart the RRT. We show that this combination of simple techniques provides better responses to a highly dynamic environment than the dynamic RRT variants.

1. Introduction

The dynamic path-planning problem consists in finding a suitable plan for each new configuration of the environment by recomputing a collision free path using the new information available at each time step [5]. This kind of problem can be found for example by a robot trying to navigate through an area crowded with people, such as a shopping mall or super-market. The problem has been addressed widely in its several flavors, such as cellular decomposition of the configuration space [12], partial environmental knowledge [11], high-dimensional configuration spaces [6] or planning with non-holonomic constraints [8]. However, simpler variations of this problem are complex enough that cannot be solved with deterministic techniques, and therefore they are worthy to study.