Trajectory Planning Amidst Moving Obstacles: Path-Velocity Decomposition Revisited

Abstract

This paper addresses trajectory planning in dynamic workspaces, for a robot subject to dynamic constraints and moving in a dynamic workspace. The case of a car-like robot A with bounded velocity and acceleration, moving in a dynamic two-dimensional workspace is considered. The solution proposed is an extension of the path-velocity decomposition that addresses motion planning in two complementary stages: (a) planning a geometric path and (b) planning the velocity along this path. Path-velocity decomposition is a practical way to address trajectory planning in dynamic workspaces since it decomposes the original problem into two more simple sub-problems. However, it presents a serious drawback: it cannot find a solution if a moving obstacle stops right on the computed path. A possible answers to this problem were to consider a set of candidate paths. The answer proposed in this paper makes use of the novel concept of adjacent paths. (like adjacent lanes of the roadway). A set of adjacent paths, one of which leads A to its goal, are computed. Then, assuming that A is able to freely shift from one path to an adjacent one, the motion of A along and between these paths is determined so as to avoid the moving obstacles while respecting 's dynamic constraints. The fact that it is possible to switch several times between two adjacent paths makes this approach more flexible and more powerful than one considering candidate paths.