Skip navigation.

Mars Rover Motion Planning

Mars rovers face a hazardous environment for navigation. Although the Martian surface has been mapped, those maps are far less detailed than terrestrial maps, and the terrain on Mars is unstructured. A rover may encounter rocks, which can damage equipment or produce a high-centering condition in which the rover cannot get sufficient traction to get unstuck. The rover may also encounter loose soil. The Mars Exploration Rover, Spirit, became stuck in such soft soil and has been unable to break free. Slopes with loose soil present another kind of challenge, since the rover may slide downhill as it traverses a path.

These hazards present challenges in perception, modeling, and planning. This work focuses on the planning problem for Mars rovers. Suppose we are able to accurately detect such hazards at short range using the rover's vision system and that we can predict how the rover will interact with these arbitrarily-placed hazards? Our planner must be able to incorporate these high-fidelity terrain interaction models and generate a set of useful motions that approximate all possible motions through the observable area around the rover.

The Lattice Planner is an extension of grid-based planners. It defines a state lattice that is discretized in all state parameters of interest, such as position, heading, curvature, and velocity. A trajectory generator is used to precompute feasible motions between states in the lattice in the absence of obstacles. The states define nodes in a graph, where edges describe motions. Importantly, the state is consistent between inbound and outbound edges at each node, so that any traversal of the graph describes a feasible sequence of motions for the rover to execute. At runtime, the states may be perturbed according to prevailing conditions. For example, a state may be moved further downhill to accommodate slip, or the heading angle may be perturbed up-slope to cancel out slip.

The state lattice graph, which is generated using a combination of offline and online computation, represents the set of possible motions of the rover down to the resolution of the lattice. A graph search algorithm such as A* or D* may then be employed to find efficient, feasible motions through the environment. A traversal of the path then gives precisely the action sequence needed to execute the desired motion.


  • Mihail Pivtoraiko, Ross A. Knepper, and Alonzo Kelly, “Differentially Constrained Mobile Robot Motion Planning in State Lattices,” Journal of Field Robotics, 26(3): 308-333 (2009). [PDF]
  • Ross A. Knepper and Alonzo Kelly, "High Performance State Lattice Planning Using Heuristic Look-Up Tables," in Proceedings of the IEEE International Conference on Intelligent Robots and Systems (IROS), Beijing, China, October 2006. [PDF]
  • Thomas M. Howard, Ross A. Knepper, and Alonzo Kelly, “Constrained Optimization Path Following of Wheeled Robots in Natural Terrain,” in Proceedings of the International Symposium on Experimental Robotics (ISER), Rio de Janeiro, Brazil, July 2006. [PDF]
  • Mihail Pivtoraiko, Ross A Knepper, and Alonzo Kelly, “Optimal, Smooth, Nonholonomic Mobile Robot Motion Planning in State Lattices,” Tech. report CMU-RI-TR-07-15, Robotics Institute, Carnegie Mellon University, May 2007. [PDF]


CMU Robotics Institute Project