Time-optimal Vehicle Trajectories
 |
We have derived the time optimal trajectories for a bounded velocity differential drive vehicle in the unobstructed plane. Differential drive means the vehicle is like a conventional wheelchair, using two independently driven wheels to maneuver in the plane. Bounded velocity means that the wheel angular velocities are bounded, but may be discontinuous. Under these assumptions, it turns out that time optimal trajectories exist for all choices of start and goal, and are composed of straight lines alternating with turns about the center of the vehicle. Optimal trajectories contain at most three straights and two turns. There are a number of other restrictions, leading to a set of 40 different combinations arranged in 9 different symmetry classes. The simplest motion to a generic goal is a turn-straight-turn: turn to face the goal, roll straight forwards to the goal, and turn to the goal orientation. In more interesting cases, the optimal trajectory contains a turn at an intermediate point. The key results presented in the IJRR article (below, 1) are:
Some plots of reachable balls are shown on the left. The vehicle starts at the origin, facing along the x axis. In fixed time, the vehicle cannot move very far to the left or right, since this would require parallel parking. This can be seen in the diagram; the contour of each ball is elongated in the x direction, the easiest direction in which to travel. As time goes to infinity, the ball becomes a cylinder, since all of the cost of rotation of the robot is upper-bounded — the sum of turning angles in an optimal trajectory is never greater than 180 degrees. The WAFR paper presented some of our early work, and also describes an interesting geometric (equation-free!) algorithm for visually determining the optimal trajectory between any two configurations. The time optimal trajectories are only known for three classes of mobile vehicle — our diff drive and two models of steered cars (Dubins and Reeds-Shepp). In fact, the basic system models are the same for all three classes; only the control bounds are different. The 2002 ICRA paper explores the similarities and differences between the optimal trajectories for these models, and describes some characteristics that the optimal trajectories for other bounded-velocity models must have. |
