Time-Optimal Trajectories

Table of contents

Problem

For specified a pair of start and final positions and orientations, what is the time-optimal trajectory to link them for a mobile robot with its dynamic and kinematic constraints in the unobstructed plane?

The motivations for studying this problem are both for practical applications and for theoretical challenges. For practical applications, an effective algorithm or the knowledge on structures of the fastest paths can help for the effective design of motion planning and control in the obstructed environment.

For theoretical interest, the analysis of this problem was a significant example for the development of modern geometric optimal control theory Sussmann91. Moreover, from studying other types of robots, does there exist a generic mechanism or technique for the determination of the time optimal trajectories for such these systems? What are the characteristics of the systems
which is able to be addressed by this generic mechanism and
technique?

Methodology

  • Before using Pontryagin Maximum Principle (PMP)
    • Dubins (1957) gave a sufficient set of paths, i.e. a set which always contains the optimal trajectories, for a Dubins car Dubins57.
    • Reeds and Shepp (1990) gave a sufficient set of paths for RS car by advanced calculus Reeds90.
  • Basic methods
    • Local reasoning: by modern geometric optimal control theory= Pontryagin Maximum Principle(PMP)+Lie algebra
      the sufficient family: the set contains all optimal trajectories types between any two configurations.

      cf.Sussmann91

    • Global reasoning: by the partition of the configuration space
      optimal synthesis: the particular optimal trajectory type between two specified configurations.

      cf.Souères96

  • More techniques

But the algorithms for determination of the exact optimal trajectory between two specified configurations need more techniques.

  • For differential drive robots, given start and final configurations, the optimal trajectory type can be easily identified, and then the corresponding exact optimal trajectory can be determined easily. But for another wheeled robots, the optimal trajectory type cannot be easily determined, even when the optimal trajectory type is known, the corresponding exact optimal trajectory is not easily determined. cf.Balkcom02
  • For steered car-like robots, differential drive robots and omnidirectional robots, the optimal trajectories can be described by motion of the robot relative to a switching line in the plane. But how to determine this switching line is an open problem. cf.Balkcom06
  • For steered car-like robots, local reasoning focuses on the rotation rules for a defined switching-related vector in a special coordinate system which is built according to properties of the switching structure. A proposition is derived: if the start and final positions and rotation directions of this vector are known, then the exact optimal trajectory is uniquely determined directly. Does there exist such proposition for other wheeled robots? If such proposition exists, is it easy or feasible to determine the start and final switching vectors? cf.Wang07

Subproblems

Completed problems

An algorithm has been achieved to determine an exactly time-optimal trajectory to link any specified start and final configurations.

Such algorithms only are presented for steered cars and differential drive robots with kinematic constraints and bounded velocities.

Link to:

Wheeled robots
Admissible control
Differential drive robots

The locomotion system of differential drive robots constitutes by two parallel driving wheels each being controlled independently.

Time-optimal trajectories for a differential drive robot

Steered Car-like robots

The steered car-like robot has the steering wheels which control the direction of vehicle.

Time-optimal trajectories for a car-like robot

Left are four kinds of the steered car-like robots with different admissible controls which are bounded.

Dubins, RS and Simple car have a bound on its angle of steering.

RS, Simple car and CRS have the equivalent time-optimal
trajectories.

Problems under consideration

  • The time-optimal trajectories for omnidirectional robots: a complete and minimal classification of the optimal trajectories are presented. Future: What is the time-optimal trajectories for specified start and final configurations.cf.Balkcom06
  • The time-optimal trajectories for Hilare-like mobile robots: cf.Soueres98
  • The time-optimal trajectories for the Dubins airplane: cf.Chitsaz07

Open problems

  • Are there techniques, which combined with modern geometric optimal control theory, can obtain the time-optimal trajectories for the wheeled robots with different constrains.
  • If such techniques exist, what are the characteristics of a system such that these techniques can be used to achieve the optimal trajectories?

References

L. E. Dubins. On curves of minimal length with a constraint on average curvature and with prescribed initial and terminal positions and tangents. American Journal of Mathematics, 79:497-516, 1957.

J. A. Reeds and L. A. SheppOptimal paths for a car that goes both forwards and backwards. Pacific Journal of Mathematics, 145(2):367-393, 1990.

H. Sussmann, G. Tang,Shortest Paths for the Reeds-Shepp Car: a Worked Out Example of the Use of Geometric Techniques in Nonlinear Optimal Control, Technical Report SYNCON 91-10, Dept. of Mathematics, Rutgers University, Piscataway, NJ, 1991.

P. Souères and J.-P. Laumond,
Shortest Paths Synthesis for a Car-Like Robot. IEEE Transactions on Automatic Control, vol. 41, no. 5, 1996, pp 672-688.

P. Souères and J.-D. Boissonnat. Optimal trajectories for nonholonomic mobile robots. In J.-P. Laumond, editor, Robot Motion Planning and Control, pages 93-170. Springer, 1998.

Subproblems

D. Balkcom and M. Mason.
Time optimal trajectories for differential drive vehicles.International Journal of Robotics Research, 21(3):199-217, 2002.

D. Balkcom and M. Mason.
Extremal trajectories for bounded velocity mobile robots. In IEEE International Conference on Robotics and Automation, 2002.

D. Balkcom and M. Mason.
Time optimal trajectories for bounded velocity differential drive robots. In IEEE International Conference on Robotics and Automation, 2000.

D. Balkcom and M. Mason.Time-optimal Trajectories for an Omni-directional Vehicle,The International Journal of Robotics Research, Vol. 25, No. 10, 985-999 (2006)

H. Chitsaz and S. M. LaValle.
Time-optimal paths for a Dubins airplane. In Proceedings IEEE Conference Decision and Control, New Orleans, LA, USA, Dec. 12-14, 2007 pp:2379-2384.

H.Wang, Y. Chen and P. Souères, An Efficient Algorithm Involving the Canonical Switching Structure to Compute Minimum-length Trajectories for a Car, submitted to IEEE Transactions on Robotics.

H. Wang, Y. Chen and P. Souères, An Efficient Geometric Algorithm to Compute Time-Optimal Trajectories for a Car-Like Robot, Proceedings of the 46th IEEE Conference on Decision and Control, New Orleans, LA, USA, Dec. 12-14, 2007 pp:5383-5388.

Discussions and comments

  • So far we only consider the wheeled robots. What are the
    problems of the fastest paths for other kinds of robots?
  • Please give your opinions and
    advice on the considering problems and open problems.

Group members

If you are interested in this topic, please join us and added your name and email below.

Jean-Paul Laumond

Matthew T. Mason;

Philippe Souères;

Huifang Wang: elizabethhw@gmail.com