Recently a planetary rover returned important scientific information from Mars. More ambitious missions are planned. New planning methods are required that allow rovers to explore challenging areas with a high level of autonomy. This paper presents a planning methodology based on a physics-based model of the rover and environment. Plans are developed that allow a rover to perform a mission while explicitly considering constraints such as power, actuator, wheel slip, and vehicle stability limits. Results obtained from detailed rover simulations are presented.