An algorithm is presented for wheeled mobile robot trajectory generation that achieves a high degree of generality and efficiency. The generality derives from numerical linearization and inversion of forward models of propulsion, suspension, and motion for any type of vehicle. Efficiency is achieved by using fast numerical optimization techniques and effective initial guesses for the vehicle controls parameters. This approach can accommodate such effects as rough terrain, vehicle dynamics, models of wheel-terrain interaction, and other effects of interest. It can accommodate boundary and internal constraints while optimizing an objective function that might, for example, involve such criteria as obstacle avoidance, cost, risk, time, or energy consumption in any combination. The algorithm is efficient enough to use in real time due to its use of nonlinear programming techniques that involve searching the space of parameterized vehicle controls. Applications of the presented methods are demonstrated for planetary rovers.
Amar, F. B. , Bidaud, Ph. , and Ouezdou, F. B. (1993). On modeling and motion planning of planetary vehicles . Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems, Vol. 2, pp. 1381–1386 .
2.
Angelova, A. , Matthies, L. , Helmick, D. , and Perona, P. (2006). Slip prediction using visual information . In Proceedings of Robotics Science and Systems, Philadelphia, USA.
3.
Baker, D. (1989). Exact solutions to some minimum-time problems and their behavior near inequality state constraints . IEEE Transactions on Automatic Control, 34(1): 103–106 .
4.
Barraquand, J. and Latombe, J. C. (1989). On nonholonomic mobile robots and optimal maneuvering . Revue d'Intelligence Artificielle, 3(2): 77–103 .
5.
Betts, J. T. (1998). Survey of numerical methods for trajectory optimization . Journal of Guidance, Control, and Dynamics, 21(2): 193–207 .
6.
Biesiadeki, J. , Leger, C. , and Maimone, M. (2005). Tradeoffs between directed and autonomous driving on the mars exploration rovers . Proceedings of the International Symposium on Robotics Research, San Francisco, USA.
7.
Bonnafous, D. , Lacroix, S. , and Simeon, T. (2001). Motion generation for a rover on rough terrain . Proceedings of the IEEE/RSJ International Conference on Intelligent Robotics and Systems, Vol. 2, pp. 784–789 .
8.
Brockett, R. W. (1981). Control theory and singular riemann geometry. In New Directions in Applied Mathematics. New York: Springer-Verlag , pp. 11–27.
9.
Canny, J. , Donald, B. , Reif, J. , and Xaiver, P. (1988). On the complexity of kinodynamic planning . Proceedings of the 29th IEEE Symposium on Foundations of Computer Science, pp. 306–318 .
10.
Cherif, M. (1999). Motion planning for all-terrain vehicles: a physical modeling approach for coping with dynamic and contact interaction constraints . IEEE Transaction on Robotics and Automation, 15(2): 202–218 .
11.
Cherif, M. , Laugier, Ch. , Milesi-Bellier, Ch. , and Faverjon, B. (1994). Planning the motions of an all-terrain vehicle by using geometric and physical models . Proceedings of IEEE International Conference on Robotics and Automation, Vol. 3, pp. 2050–2056 .
12.
Delingette, H. , Herbert, M. , and Ikeuchi, K. (1991). Trajectory generation with curvature constraint based on energy minimization . Proceedings of the IEE-RSJ International Conference on Intelligent Robots and Systems, Vol.1, pp. 206–211 .
13.
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 .
14.
Faiz, N. , Agrawal, S. , and Murray, R. (2001). Differentially flat systems with inequality constraints: an approach to real-time feasible trajectory generation . Journal of Guidance, Control, and Dynamics, 24(2): 219–227 .
15.
Fliess, M. , Levine, J. , Martin, Ph. and Rouchon, P. (1995). Flatness and defect of nonlinear systems: introductory theory and examples. International . Journal of Control, 61(6): 1327–1361 .
16.
Gaw, D. and Meystel, A. (1986). Minimum-time navigation of an unmanned mobile robot in a 2½D world with obstacles . Proceedings of the IEEE International Conference on Robotics and Automation, Vol. 3, pp. 1670–1677 .
17.
Heinzinger, G. , Jacobs, P. , Canny, J. , and Paden, B. (1990). Time-optimal trajectories for a robot manipulator: A provably good approximation algorithm . In Automatic Control Conference.
18.
Howard, T. M. and Kelly, A. (2006). Trajectory and spline generation for all-wheel steering mobile robots . Proceedings of the IEEE/RSJ International Conference on Intelligent Robotics and Systems, Beijing, China, October.
19.
Howard, T. M. and Kelly, A. (2005a). Trajectory generation on rough terrain considering actuator dynamics. Field and Service Robotics 2005, Port Douglas, Australia , July.
20.
Howard, T. M. and Kelly, A. (2005b). Terrain-adaptive generation of optimal continuous trajectories for mobile robots. International Symposium on Artificial Intelligence, Robotics, and Automation in Space 2005, Munich, Germany , October.
21.
Howard, T. M.Knepper, R. A. , and Kelly, A. (2006). Constrained optimization path following of wheeled mobile robots in natural terrain. International Symposium on Experimental Robotics 2006, Rio de Janeiro, Brazil , July.
22.
Jacobs, P. and Canny, J. (1989). Planning smooth paths for mobile robots . Proceedings of the IEEE International Conference. on Robotics and Automation, pp. 2–7 .
23.
Jackson, J. W. and Crouch, P. E. (1991). Curved path approaches and dynamic interpolation . IEEE Aerospace and Electronic Systems Magazine, 6(2): 8–13 .
24.
Kalmár-Nagy, T. , D'Andrea, R. , and Ganguly, P. (2004). Nearoptimal dynamic trajectory generation and control of an omnidirectional vehicle . Robotics and Autonomous Systems, 46: 47–64 .
25.
Kanayama, Y. and Miyake, N. (1985). Trajectory generation for mobile robots . Proceedings of the International Symposium on Robotics Research, pp. 16–23 .
26.
Kanayama, Y. and Hartman, B. I. (1989). Smooth local path planning for autonomous vehicles . Proceedings of the International Conference on Robotics and Automation, Vol. 3, pp. 1265–1270 .
27.
Kelly, A. and Nagy, B. (2003). Reactive nonholonomic trajectory generation via parametric optimal control . International Journal of Robotics Research, 22(7-8): 583–601 .
28.
Kim, S. K. and Tilbury, D. M. (2001). Trajectory generation for a class of nonlinear systems with input and state constraints . Proceedings of the American Control Conference, Vol. 6, pp. 4908–4913 .
29.
Komoriya, K. and Tanie, K. (1989). Trajectory design and control of a wheel-type mobile robot using B-spline curve . In Proceedings of the IEE-RSJ International Conference on Intelligent Robots and Systems, pp. 398–405 .
30.
Lacze,A. , Moscovitz,Y. , DeClaris, N. and Murphy, K. (1998). Path planning for autonomous vehicles driving over rough terrain . Proceedings of the 1998 IEEE ISIC/CIRA/ISAS Joint Conference. More detail required
31.
Laumond, J. P. , Taix, M. , and Jacobs, P. (1990). A motion planner for car-like robots based on a mixed global/local approach. IEEE International Workshop on Intelligent Robots and Systems, Tsuchira, Japan , pp. 765–773.
32.
Laumond, J. P. (1995). Nonholonomic motion planning via optimal control . Proceedings of the Workshop on Algorithmic Foundations of Robotics, San Francisco, USA, pp. 227–238 .
33.
Lin, C. S. , Chang, P. R. and Luh, J.Y. S. (1983). Formulation and optimization of cubic polynomial joint trajectories for industrial robots . IEEE Transactions on Automatic Control, AC-23: 1066–1074 .
34.
Murray, R. and Sastry, S. (1998). Nonholonomic motion planning: steering using sinusoids . IEEE Transactions on Automatic Control, 38: 700–716 .
35.
Nagy, B. and Kelly, A. (2001). Trajectory generation for carlike robots using cubic curvature polynomials. Field and Service Robotics 2001 (FSR '01), June.
36.
Nesnas, I. , Maimone, M. and Das, H. (2000). Rover maneuvering for autonomous vision-based dexterous manipulation . IEEE Conference on Robotics and Automation, San Francisco, CA, Vol. 3, pp. 2296–2301 .
37.
Pivtoraiko, M. and Kelly, A. (2005). Efficient contstrained path planning via search in state lattices. International Symposium on Artificial Intelligence, Robotics, and Automation in Space, Munich, Germany .
38.
Reeds, J. A. and Shepp, L. A. (1990). Optimal paths for a car that goes both forward and backward . Pacific Journal of Mathematics, 145(2): 367–393 .
39.
Reuter, J. (1998). Mobile robot trajectories with continuously differentiable curvature: an optimal control approach . Proceedings of the IEEE/RSI Conference on Intelligent Robots and Systems, Victoria, BC, October, Vol. 3, pp. 38–43 .
40.
Shiller, Z. and Chen, J. C. (1990). Optimal motion planning of autonomous vehicles in three-dimensional terrains . Proceedings of the IEEE International Conference on Robotics and Automation, Cincinnati, Vol. 1., pp. 198–203 .
41.
Shiller, Z. and Gwo, Y. R. (1991). Dynamic motion planning of autonomous vehicles . IEEE Transactions on Robotics and Automation, 7(2): 241–249 .
42.
Shin, D. H. and Singh, S. (1990). Path generation for robot vehicles using composite clothoid segments. Tech Report, CMU-RI-TR-90-31, The Robotics Institute, Carnegie Mellon University .
43.
Tarokh, M. and McDermott, G. (2005). Kinematics modeling and analyses of articulated rovers. Technical Report No. CS/10/2005.
44.
Tilbury, D. , Laumond, J. P. , Murray, R. , Sastry, S. and Walsh, G. (1992). Steering car-like systems with trailers using sinusoids . Proceedings of the IEEE International Conference. on Robotics and Automation, Vol. 3, pp. 1993–1998 .
