Dynamic Trajectory Planning, Path-Velocity Decomposition and Adjacent Paths

This paper addresses Dynamic Trajectory Planning, which is defined as Motion Planning for a robot A moving in a dynamic workspace W, i.e. with moving obstacles. Besides A is subject both to kinematic constraints and dynamic constraints. We consider the case of a car-like robot A with bounded velocity and acceleration, moving in a dynamic workspace W = IR 2 . Our approach is an extension to the Path-Velocity Decomposition [Kant and Zucker, 1986]. We introduce the concept of adjacent paths and we use it within a novel planning schema which operates in two complementary stages: (a) Paths Planning and (b) Trajectory Planning. In Paths Planning, a set of adjacent paths, one of which leading A to its goal, are computed. These paths are collision-free with the stationary obstacles and respect A's kinematic constraints. In Trajectory Planning, knowing that A is able to shift from one path to an adjacent one freely, we determine the motion of A along and between these paths so as to avoid the..