Path Planning in Repetitive Environments

Abstract

In this paper we discuss path planning in a special class of dynamic environments, namely repetitive environments, in which the motions of the moving obstacles are periodic (i.e. repetitive). For such environments it is possible to generate a roadmap in a preprocessing stage, which can be used multiple times to quickly solve individual planning queries. This in contrast to general dynamic environments, whose transitoriness invalidates the premise that a preprocessed roadmap can be used multiple times. Our approach is suitable for any robot with any number of degrees of freedom in two- and three dimensional workspaces, and applications can be found, amongst others, in virtual environments and computer games. I. I NTRODUCTION Path planning is of great importance in various fields such as robotics and virtual environments. The problem is generally formulated as finding a path for a robot between two query configurations that avoids collisions with the obstacles in the environment. Most research has focused on the problem of path planning in static environments, where the geometry of the environment is known in advance and the obstacles do not move. Many solutions to this problem have been presented, most of them being probabilistic (8), (9). They can roughly be subdivided into two classes: single-shot and multiple-shot. Single-shot approaches aim to solve a single planning query as fast as possible. The most popular method is the Rapidly- exploring Random Tree (RRT)-approach (7), where a random tree of possible paths is grown outward from the start until it can be connected to the goal configuration. Multiple-shot approaches do some (relatively expensive) preprocessing on the environment, such that (multiple) individual path planning queries can be answered quickly. They are useful when ex- pectedly many queries will be done in the same environment. The most well-known approach is the Probabilistic Roadmap (PRM)-method (6), (12). In the preprocessing stage, it gen- erates a roadmap that represents the connectivity of the fre e space by connecting randomly sampled configurations with straight-line paths. Individual queries are then answered by connecting the start and goal to the roadmap, and searching for a shortest path (using e.g. Dijkstra's). Both PRM and RRT are proven to be probabilistically complete, and have successfully been used in complex, high-dimensional configuration space s. The extension of the path planning problem to dynamic