Globally optimal rover traverse planning in 3D using Dijkstra's algorithm for multi-objective deployment scenarios

Wolfgang Fink, Victor R. Baker, Alexander J.W. Brooks, Michael Flammia, James M. Dohm, Mark A. Tarbell

Research output: Contribution to journalArticlepeer-review

22 Scopus citations


Currently, traverse/mission planning for deployed rovers (e.g., on Mars) requires planetary scientists to spend many hours on laborious surface terrain analysis in order to minimize some traverse aspects (e.g., distance) while maximizing others (e.g., smoothness). This is largely a manual process, but the results are at best functional compromises that balance various, potentially mutually exclusive optimization goals. The Globally Rover Traverse-Optimizing Planner (GRTOP) introduced here is an automated system that generates globally optimal traverses in 3D using a multi-objective variant of Dijkstra's algorithm based on terrain data. GRTOP makes it possible to quickly and accurately generate traverses that are simultaneously optimized for numerous constraints, including the lowest number of deployment steps, the shortest traverse based on 3D Euclidean distance, the smoothest traverse with respect to terrain roughness, the least altitude change, or any combination of these. Additional constraints, which are supported by the terrain data, can be added directly to the system. Numerous alternate, Pareto-optimal traverses can be generated for each deployment scenario. Depending on ground-truth in-situ assessment of terrain data traversability by a deployed rover (e.g., Curiosity), GRTOP allows for frequent re-planning of traverses/missions. GRTOP optimizes for traversability and mission safety, and, through more efficient roving-based reconnaissance, it ultimately generates a higher potential science return.

Original languageEnglish (US)
Article number104707
JournalPlanetary and Space Science
StatePublished - Dec 2019


  • Dijkstra's algorithm
  • Fractal landscape
  • Global pareto-optimal front
  • Multi-objective path optimization
  • Planetary rover traverse planning
  • Terrain traversability

ASJC Scopus subject areas

  • Astronomy and Astrophysics
  • Space and Planetary Science


Dive into the research topics of 'Globally optimal rover traverse planning in 3D using Dijkstra's algorithm for multi-objective deployment scenarios'. Together they form a unique fingerprint.

Cite this