Planning Constrained Motion

Anyone who has ever tried to parallel park understands the problem of planning constrained motion. We study the complexity of motion planning for objects that are constrained to move in a fashion similar to the way an automobile moves. The model is an "oriented point" moving in a two-dimensional world with polygonal obstacles. The point can move in the direction of its orientation, or it can turn left or right, but it has a fixed minimum radius of curvature. Given a source placement (a position and an orientation) and a target placement, we ask if there is a path from source to target satisfying the radius of curvature constraint and avoiding all obstacles. We show that this question is decidable.