Kinodynamic planning in a structured and time-varying 2-D workspace

Abstract

A trajectory planning problem called the highway problem is discussed. It consists of planning a time-optimal trajectory for a mobile robot which is travelling in a structured workspace amidst moving obstacles and is subject to constraints on its velocity and acceleration. In a structured workspace there are lanes characterized by one-dimensional curves along which the mobile robot can move. The mobile robot has to follow a lane, but it may also shift from its lane to an adjacent one. An efficient method which determines an approximate time-optimal solution to the highway problem is presented. The approach consists of discretizing time and selecting the accelerations to be applied to the mobile robot among a discrete set. These hypotheses make it possible to define a grid in the mobile robot's time-state space, i.e. the state space augmented in the time dimension. This grid is then searched to find a solution.< <ETX xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">&gt;</ETX>