Creating High-quality Roadmaps for Motion Planning in Virtual Environments

Our goal is to create road maps that are particularly suited for motion planning in virtual environments. We use our reachability roadmap method to compute an initial, resolution complete roadmap. This roadmap is small which keeps query times and memory consumption low. However, for use in virtual environments, there are additional criteria that must be satisfied. In particular, we require that the roadmap contains useful cycles. These provide short paths and alternative routes which allow for variation in the routes a moving object can take. We will show how to incorporate such cycles. In addition, we provide high-clearance paths by retracting the edges of the roadmap to the medial axis. Since all operations are performed in a preprocessing phase, high-quality paths can be extracted in real-time as is required in interactive applications

I. Introduction

In many virtual environments, paths have to be planned for entities to traverse from a start to a goal position in the virtual world. A common way to plan the path is to use an algorithm on a (low-resolution) grid. This search algorithm is popular because it always finds a shortest path in the roadmap if one exists. However, as contemporary virtual worlds can be very large, storing the grid and running the algorithm may consume a huge amount of memory which is not always available, in particular on systems with constrained memory such as console systems. In addition, the algorithm may consume too much processor time, especially when many paths have to be planned simultaneously. This will lead to stalls in interactive applications. Paths resulting from algorithms tend to have little clearance and can be aesthetically unpleasant, so care must be taken to smooth them.