Efficient path planning in changing environments

This paper addresses the problem of path planning in environments in which some of the obstacles can change their positions. It uses the popular PRM method for navigating a robot through an environment. One of the key features of PRM is that it moves the major part of the calculations involved in the path planning process to the preprocessing phase. After that, paths can be extracted very quickly (in a query phase) usually without any noticeable delay. While very successful in many applications, doing most of the work in a preprocessing phase restricts the environment to be static i.e. obstacles are not allowed to change their configurations after the preprocessing phase. In this paper we describe and evaluate an algorithm based on PRM that does allow obstacles to change their configuration after preprocessing while still allowing for a quick query phase.

I. Introduction

The Probabilistic Roadmap Method (PRM) [9] has become one of the leading path planning techniques in the field of robotics, both in virtual and real-world contexts. Recently its applications have extended to the domain of computer-assisted training, advanced gaming [12], [8] and biology (see e.g. [13]). Its main features are its simplicity, allowing for almost instantaneous queries, extensibility to higher dimensions and the broad range of problem types to which it is applicable. The PRM method works by sampling collision-free configurations and by connecting these by collision-free local paths (created by a local planner). A graph (the roadmap) is thus formed that aims at representing the connectedness of the free space. If the roadmap adequately represents this connectedness, a path between two collision-free configurations can be computed efficiently. An important property of the PRM planner is that the major part of the computations are done in a preprocessing phase. After this preprocessing phase, paths can be extracted quickly in a query phase allowing for interactive performance.