This paper presents a mobile robot planner that attempts to find minimum time path between two configurations on uneven outdoor terrain. The computed path is smooth, safe, and satisfies dynamic constraints. The terrain is modeled as a geometric surface, the robot is Segway Robotic Mobile Platform (RMP). It uses bidirectional rapidly exploring random trees (RRT's) on the terrain surface with nodes connected by continuous curvature trajectories. In standard RRT nodes are usually expanded by applying controls for a fixed duration. In our RRT implementation, the current path is extended with a short trajectory up to a specified maximum length. The trajectory parametrization is such that different sets of controls and control durations can be fitted to produce the same curve. Thus, the robot velocity profile can be readjusted "back in time" along previous RRT edges. An optimization algorithm is used to compute globally optimal velocity profile resulting in near minium time path while satisfying the dynamic constraints. We apply these methods to an interesting problem - robot finding its quickest path on a rough terrain while maintaining the safety of its load and itself.