In this paper we present the minimum-time sequences of rotations and translations that connect two configurations of a rigid body in the plane. The configuration of the body is its position and orientation, given by (x , y, θ ) coordinates, and the rotations and translations are velocities (x , y, θ ) that are constant in the frame of the robot. There are no obstacles in the plane. We completely describe the structure of the fastest trajectories, and present a polynomial-time algorithm that, given a set of rotation and translation controls, enumerates a finite set of structures of optimal trajectories. These trajectories are a generalization of the well-known Dubins and Reeds—Shepp curves, which describe the shortest paths for steered cars in the plane.
Agarwal, P.K., Biedl, T., Lazard, S., Robbins, S., Suri, S. and Whitesides, S. ( 1998). Curvature-constrained shortest paths in a convex polygon . in SCG ’98: Proceedings of the fourteenth annual symposium on Computational geometry, New York: ACM pp. 392-401.
2.
Alterovitz, R., Branicky, M. and Goldberg, K. ( 2008). Motion planning under uncertainty for image-guided medical needle steering. The International Journal of Robotics Research , 27(11): 1361-1374.
3.
Balkcom, D.J., Kavathekar, P.A. and Mason, M.T. ( 2006). Time-optimal trajectories for an omni-directional vehicle . The International Journal of Robotics Research, 25(10): 985-999.
4.
Balkcom, D.J. and Mason, M.T. ( 2002). Time optimal trajectories for differential drive vehicles . The International Journal of Robotics Research, 21(3): 199-217.
5.
Barraquand, J. and Latombe, J.-C. ( 1993). Nonholonomic multibody mobile robots: Controllability and motion planning in the presence of obstacles. Algorithmica , 10: 121- 155.
6.
Chitsaz, H., LaValle, S.M., Balkcom, D.J. and Mason, M.T. ( 2006). Minimum wheel-rotation paths for differential-drive mobile robots. IEEE International Conference on Robotics and Automation.
7.
Chyba, M. and Haberkorn, T. ( 2005). Designing efficient trajectories for underwater vehicles using geometric control theory. 24rd International Conference on Offshore Mechanics and Artic Engineering, Halkidiki, Greece.
8.
Coombs, A.T. and Lewis, A.D. ( 2001). Optimal control for a simplified hovercraft model. SIAM Conference on Control and Its Applications: San Diego California .
9.
Craig, J.J. ( 1989). Introduction to Robotics: Mechanics and Control (2nd edn). Reading, MA, Addison-Wesley.
10.
Desaulniers, G. ( 1996). On shortest paths for a car-like robot maneuvering around obstacles. Robotics and Autonomous Systems, 17: 139-148.
11.
Donald, B., Levey, C., McGray, C., Paprotny, I. and Rus, D. ( 2006). An untethered, electrostatic, globally controllable MEMS micro-robot. Journal of Microelectromechanical Systems, 15(1): 1-15.
12.
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.
13.
Furtuna, A.A., Balkcom, D.J., Chitsaz, H. and Kavathekar, P. ( 2008). Generalizing the Dubins and Reeds-Shepp cars: fastest paths for bounded-velocity mobile robots. IEEE International Conference on Robotics and Automation, pp. 2533-2539.
14.
Hayet, J.-B., Esteves, C. and Murrieta-Cid, R. ( 2008). A motion planner for maintaining landmark visibility with a differential drive robot. Workshop on the Algorithmic Foundations of Robotics.
15.
Kalmár-Nagy, T., D’Andrea, R. and Ganguly, P. ( 2004). Near-optimal dynamic trajectory generation and control of an omnidirectional vehicle. Robotics and Autonomous Systems , 46: 47-64.
16.
LaValle, S.M. ( 2006). Planning Algorithms. Cambridge, Cambridge University Press.
17.
Lynch, K.M. and Mason, M.T. ( 1996). Stable pushing: mechanics, controllability, and planning . The International Journal of Robotics Research, 15(6): 533-556.
18.
Pontryagin, L.S., Boltyanskii, V.G., Gamkrelidze, R.V. and Mishchenko, E.F. ( 1962). The Mathematical Theory of Optimal Processes. New York, John Wiley & Sons.
19.
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.
20.
Reister, D.B. and Pin, F.G. ( 1994). Time-optimal trajectories for mobile robots with two independently driven wheels. The International Journal of Robotics Research, 13(1): 38- 54.
21.
Renaud, M. and Fourquet, J.-Y. ( 1997). Minimum time motion of a mobile robot with two independent acceleration-driven wheels. Proceedings of the 1997 IEEE International Conference on Robotics and Automation, pp. 2608-2613.
22.
Salaris, P., Belo, F.A.W., Fontanelli, D., Greco, L. and Bicchi, A. ( 2008). Optimal paths in a constarained image plane for purely image-based parking. IEEE/RSJ International Conference on Intelligent Robots and Systems, pp. 1673- 1680.
23.
Souères, P. and Boissonnat, J.-D. ( 1998). Optimal trajectories for nonholonomic mobile robots. Robot Motion Planning and Control, Laumond, J.-P. (ed.). Berlin, Springer, pp. 93- 170.
24.
Souères, P. and Laumond, J.-P. ( 1996). Shortest paths synthesis for a car-like robot. IEEE Transactions on Automatic Control, 41(5): 672-688.
25.
Sussmann, H. ( 1997). The Markov-Dubins problem with angular acceleration control . IEEE International Conference on Decision and Control, pp. 2639-2643.
26.
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 SYCON 91-10, Department of Mathematics, Rutgers University, New Brunswick, NJ, USA.
27.
Vendittelli, M., Laumond, J. and Nissoux, C. ( 1999). Obstacle distance for car-like robots. IEEE Transactions on Robotics and Automation, 15(4): 678-691.
