A method for planning the motions of autonomous vehicles moving on general terrains is presented that obtains the geometric path and vehicle speeds that minimize motion time considering vehicle dynamics, terrain topography, obstacles, and surface mobility. The terrain is represented by a smooth cubic B patch, and the geometric path consists of a B spline curve mapped to the surface. The time-optimal motions are computed by first obtaining the best obstacle-free path from all paths represented by a uniform grid. This path is further optimized using a local optimization procedure, using the optimal motion time along the path as the cost function and the control points of a B spline as the optimizing parameters. Examples are presented that demonstrate the method for a simple dynamic model of a vehicle moving on mountainous terrain.>