The shortest paths for a mobile robot are a fundamental property of the mechanism, and may also be used as a family of primitives for motion planning in the presence of obstacles. This paper characterizes shortest paths for differential-drive mobile robots, with the goal of classifying solutions in the spirit of Dubins curves and Reeds—Shepp curves for car-like robots. To obtain a well-defined notion of shortest, the total amount of wheel-rotation is optimized. Using the Pontryagin Maximum Principle and other tools, we derive the set of optimal paths, and we give a representation of the extremals in the form of finite automata. It turns out that minimum time for the Reeds—Shepp car is equal to minimum wheel-rotation for the differential-drive, and minimum time curves for the convexified Reeds—Shepp car are exactly the same as minimum wheel-rotation paths for the differential-drive. It is currently unknown whether there is a simpler proof for this fact.
Agarwal, P.K., Raghavan, P. and Tamaki, H. (1995). Motion planning for a steering constrained robot through moderate obstacles. Proceedings of the ACM Symposium on Computational Geometry, pp. 343-352.
2.
Balkcom, D.J. and Mason, M.T. (2002). Time optimal trajectories for bounded velocity differential drive vehicles. International Journal of Robotics Research, 21(3): 199-218.
3.
Balkcom, D.J., Kavathekar, P.A. and Mason, M.T. (2006). Time-optimal trajectories for an omni-directional vehicle. International Journal of Robotics Research, 25(10).
4.
Boissonnat, J.-D. and Lazard, S. (1996). A polynomial-time algorithm for computing a shortest path of bounded curvature amidst moderate obstacles. Proceedings of the ACM Symposium on Computational Geometry, pp. 242-251.
5.
Cesari, L.( 1983). Optimization Theory and Applications: Problems with Ordinary Differetial Equations. New York, NY, Springer.
6.
Chitsaz, H. and LaValle, S.M. (2007). Minimum wheel-rotation paths for differential-drive mobile robots among piecewise smooth obstacles. IEEE International Conference on Robotics and Automation.
7.
Chitsaz, H. et al. (2006a) Minimum wheel-rotation paths for differential-drive mobile robots. IEEE International Conference on Robotics and Automation.
8.
Chitsaz, H. et al. (2006b). An explicit characterization of minimum wheel-rotation paths for differential-drives. IEEE International Conference on Methods and Models in Automation and Robotics .
9.
Chyba, M. and Sekhavat, S. (1999). Time optimal paths for a mobile robot with one trailer. IEEE/RSJ International Conference on Intelligent Robots & Systems, Vol. 3, pp. 1669- 1674.
10.
Desaulniers, G., Soumis, F. and Laurent, J.-C. (1998). A shortest path algorithm for a car-like robot in a polygonal environment. International Journal of Robotics Research, 17(5): 512-530.
11.
Dubins, L.E. (1957). 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.
12.
LaValle, S.M. (2006). Planning Algorithms. Cambridge, UK, Cambridge University Press. Available at http://planning.cs.uiuc.edu/.
13.
Moutarlier, P., Mirtich, B. and Canny, J. (1996). Shortest paths for a car-like robot to manifolds in configuration space. International Journal of Robotics Research, 15(1).
14.
Pontryagin, L.S. et al. (1962). The Mathematical Theory of Optimal Processes . John Wiley.
15.
Reeds, J.A. and Shepp, L.A. (1990). Optimal paths for a car that goes both forwards and backwards. Pacific Journal of Mathematics, 145(2): 367-393.
16.
Reister, D.B. and Pin, F.G. (1994). Time-optimal trajectories for mobile robots with two independently driven wheels. International Journal of Robotics Research, 13(1): 38-54.
17.
Renaud, M. and Fourquet, J.Y. (1997). Minimum time motion of a mobile robot with two independent acceleration-driven wheels. IEEE International Conference on Robotics and Automation, pp. 2608-2613.
18.
Souères, P. and Boissonnat, J.-D. (1998). Optimal trajectories for nonholonomic mobile robots. Robot Motion Planning and Control , Laumond, J.-P. (ed). Springer, 1998, pp. 93- 170.
19.
Souères, P. and Laumond, J.P. (1996). Shortest paths synthesis for a car-like robot . IEEE Transactions on Automatic Control, 672-688.
20.
Sussmann, H. (1997). The Markov-Dubins problem with angular acceleration control. Proccedings of the 36th IEEE Conference on Decision and Control, San Diego, CA. IEEE Publications, pp. 2639-2643.
21.
Sussmann, H. and Tang, G. (1991). 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, Department of Mathematics, Rutgers University.
22.
Vendittelli, M., Laumond, J.P. and Nissoux, C. (1999). Obstacle distance for car-like robots. IEEE Transactions on Robotics and Automation, 15(4): 678-691.
23.
Vendittelli, M., Laumond, J.P. and Souères, P. (1999). Shortest paths to obstacles for a polygonal car-like robot. IEEE Conference on Decision & Control .
24.
Zelikin, M.I. and Borisov, V.F. (1994). Theory of Chattering Control. Boston, NJ, Birkhäuser.
