Kinodynamic motion planning on roadmaps in dynamic environments

In this paper we present a new method for kinodynamic motion planning in environments that contain both static and moving obstacles. We present an efficient two-stage approach: in the preprocessing phase, it constructs a roadmap that is collision-free with respect to the static obstacles and encodes the kinematic constraints on the robot. In the query phase, it plans a time-optimal path on the roadmap that obeys the dynamic constraints (bounded acceleration, curvature derivative) on the robot and avoids collisions with any of the moving obstacles. We do not put any constraints on the motions of the moving obstacles, but we assume that they are completely known when a query is performed. We implemented our method, and experiments confirm its good performance.

I. Introduction

The problem we discuss in this paper is kinodynamic motion planning in dynamic environments. That is, planning a path for a robot from a start to a goal state in a two-or three-dimensional workspace that obeys the kinematic and dynamic constraints on the robot and avoids collisions with static and moving obstacles in the environment. We assume that the geometry and motions of the obstacles are given.