The ability of mobile robots to generate feasible trajectories online is an important requirement for their autonomous operation in unstructured environments. Many path generation techniques focus on generation of time- or distance-optimal paths while obeying dynamic constraints, and often assume precise knowledge of robot and/or environmental (i.e. terrain) properties. In uneven terrain, it is essential that the robot mobility over the terrain be explicitly considered in the planning process. Further, since significant uncertainty is often associated with robot and/or terrain parameter knowledge, this should also be accounted for in a path generation algorithm. Here, extensions to the rapidly exploring random tree (RRT) algorithm are presented that explicitly consider robot mobility and robot parameter uncertainty based on the stochastic response surface method (SRSM). Simulation results suggest that the proposed approach can be used for generating safe paths on uncertain, uneven terrain. © 2009 IEEE.