The Z^3-Method for Fast Path Planning in Dynamic Environments

Abstract

We present a method to plan collision free paths for robots with any number of degrees of freedom in dynamic environments. The method proved to be very efficient as it ommits a complete representation of the high dimensional search space. Its complexity is linear in the number of degrees of freedom. A preprocessing of the geometry data of the robot or the environment is not required. With the time as an additional dimension of the search space it is possible to use the method in known dynamic environments or for multiple robots sharing a common work space. Keywords: Path Planning, Dynamic Environments, Randomized Algorithms 1 Introduction The method presented in this paper is part of our research on intelligent and autonomous robot systems. An important component of such a system is a path planner that creates collision free and physically possible motions between positions that were planned on a higher, more abstract level. A path planner for practical use must be able to work fast ...