46th Lunar and Planetary Science Conference (2015)
W. Fink1,2, V. R. Baker3,4, M. Flammia1, and M. A. Tarbell1,2, 1Visual & Autonomous Exploration Systems Research Laboratory (http://autonomy.arizona.edu), Dept. of Electrical & Computer Engineering, 2Dept. of Aerospace
& Mechanical Engineering, 3Dept. of Hydrology & Water Resources, 4Lunar & Planetary Laboratory, University of
Arizona, Tucson, AZ, USA, [email protected], [email protected], [email protected],
[email protected]
Introduction: The Mars Science Laboratory
(MSL) mission delivered the Curiosity rover to the
“Bradbury Landing” site in Gale Crater, Mars, on August 6, 2012. Prior to landing and in the course of the
mission, orbital mapping of terrain types was employed to facilitate mission planning, both for deciding
targets for investigation and for anticipating issues of
traversing terrains, including: problems of steep slopes,
such as on, e.g., the slip faces of sand dunes or potentially wheel-damaging zones of rugged rock.
The MSL mission pursued the goal of exploring
Mars habitability by initially traversing eastward toward the Gelneig area in order to sample lacustrine
mudstone beds at Yellowknife Bay [1]. This initial
phase of the mission did not encounter any problematic
terrains. On sol 324 the rover completed the investigation of Yellowknife Bay and began a year-long southwestward traverse toward the primary mission destination of Aeolis Mons (informally named “Mount
Sharp”), a 5-km high mound of sedimentary rocks.
Starting about sol 400, after traversing a total distance of about 3 km, repeated surface imaging of Curiosity’s wheels revealed an alarming increase in the rate
of damage, principally in the form of dents, punctures,
and tears (Fig. 1), which potentially could prematurely
terminate the mission. Teams were formed to investigate (1) the mechanical operation of the wheels and
their interaction with rugged terrain, (2) mapping of
terrain textures from orbital and rover images, and (3)
experiments on rover test beds [2]. The worst wheel
damage was found to result from pyramidal-shaped,
sharp-edged pebbles, which at 8-11 mm in diameter
were small enough to fit between the wheel grousers
[3]. Damage occurred when the rover was passing over
areas of jagged caprock composed of sharp-edged, cmsized hard rock clasts, and lacking a protective mantle
of finer sediments [4].
The mission team used combined orbit-derived interpretation of surface roughness with ground-based
observations of rock abundance and soil/rock surface
characteristics to work out criteria for identifying the
least rover-wheel-damaging terrains. These criteria
were then used to laboriously plot out paths of minimal
potential damage for the traverse to Mount Sharp.
As of this writing, the Curiosity rover reached the
base of Mount Sharp, and proposed routes to ascend
the mountain will encounter a new range of terrain
types. This may lead to new surprises in regard to potentially damaging zones that will need to be traversed.
Traverse-Optimizing Planner: The above challenges can be addressed by the Rover TraverseOptimizing Planner (RTOP): an automated system
which rapidly generates ideal traverses using a multivariate stochastic optimization algorithm based on 3D
terrain data in the presence of numerous simultaneous
constraints. Effective long-term traverse planning for
planetary rovers requires consideration of the 3D terrain context; for this reason, the 2D path planning and
navigation algorithms typically employed for this purpose, such as Dijkstra's [5], Depth First Search (DFS)
[6], and A* (e.g., [7, 8]), are applicable only to controlled, static, flat environments. Thus they are not
optimal, if at all applicable, in the 3D context of longterm traverse planning for planetary rovers.
RTOP employs a Stochastic Optimization Framework (SOF; [9]; Fig. 2) for traverse planning. SOF has
previously been used for operating robotic arms with N
Degrees Of Freedom (N-DOF) [10]. This framework,
in addition to being computationally bounded and less
compute intensive, has the advantage of accounting for
much less well-defined and constantly changing realworld environments, e.g., as might be encountered by a
Mars or lunar rover.
One of the integral elements of the SOF is its efficient Simulated Annealing algorithm [10, 11]. A SOF
efficiently samples the parameter space intrinsic to a
model, process, or system by (1) repeatedly running
the model, process, or system, and (2) comparing the
respective outcomes against a desired outcome. This
comparison results in a fitness measure. The goal of
the SOF is to optimize this fitness measure in the presence of constraints, by using, e.g., Simulated Annealing algorithms [11] as the optimization engine.
The RTOP optimizes the overall traverse by minimizing the Euclidian distance between the rover start
and target locations. Moreover, the SOF does not
merely generate the shortest distance, but instead allows the traverse to “meander” while optimizing for
the respective mission constraint(s), e.g., shortest trav-
46th Lunar and Planetary Science Conference (2015)
erse based on 3D Euclidian distance measure, smoothest traverse with respect to terrain roughness, least
altitude change, or any combination of these.
Once a valid rover traverse has been determined
via the above stochastic optimization procedure using
Simulated Annealing [10, 11], a deterministic clean-up
procedure is engaged to prune the “raw” traverse to its
shortest connected path among the points visited by the
rover. This pruned traverse is then compared against
the respective optimization constraint(s), and the global optimization continues until either a user-defined
number of overall traverses has been reached, or a satisfactory traverse has been found.
Discussion: The Rover Traverse-Optimizing Planner (RTOP) can optimize for an open-ended set of
multi-objective deployment scenarios. For a planetary
rover: (a) lowest number of deployment segments; (b)
shortest traverse based on 3D Euclidian Distance
measure (Fig. 3); (c) smoothest traverse, i.e., traverse
through mostly benign terrain; (d) traverse with smallest average roughness; (e) traverse with smallest slopechange, i.e., least altitude changes; (f) traverse with
smallest average slope-change; (f) any combination of
the above, e.g., for smoothest and shortest traverse.
Additionally, an overarching “main traverse” can
be broken into multiple segments, each with its own
combination of optimization parameters. This is essential since a rover may traverse many diverse types of
terrain, and may have different goals while traversing
each segment. Additional constraints which are supported by the terrain data can be added directly to the
system to be optimized. Numerous alternate and Pareto-optimal [10] traverses can be generated for each
deployment scenario. RTOP allows for frequent, ondemand replanning of traverses/missions according to
real time ground-truth in-situ assessment of terrain data
traversability by a deployed rover (e.g., Curiosity on
Mars). RTOP’s capability of providing Pareto-optimal
solutions for deployment scenarios supports versatile
and critical mission-planning for current and future
robotic planetary surface exploration.
References: [1] Grotzinger J. P. et al. (2014) Science, 343, doi: 10.1126/science.1242777. [2] Vasavada
A. R. et al. (2014) JGR Planets, 119, 1134-1161. [3]
Yingst R. A. et al. (2014) Geo Soc of America Abstracts with Programs, 46, 498. [4] Yingst R. A.
(2014) personal communication. [5] Dijkstra E. W.
(1959) Numerische Mathematik, 1, 269-271. [6] Knuth
D. E. (1997) “The Art Of Computer Programming”,
Vol 1. 3rd ed, Boston: Addison-Wesley, ISBN 0-20189683-4, OCLC 155842391. [7] Hart P. E. et al.
(1968) IEEE Trans Systems Science and Cybernetics
SSC4. 2, 100-107. [8] Hart P. E. et al. (1972) SIGART
Newsletter, 37, 28-29. [9] Fink W. (2008) Proc. SPIE,
6960, 69600N (2008); DOI:10.1117/12.784440. [10]
Fink W. et al. (2010) J Field Robotics, 27, 268-280.
[11] Kirkpatrick S. et al. (1983) Science, 220, 671-680.
Fig. 1. Left: An example of the rover encountering a
sharp rock that does not move. Right: Evidence of a
damaged wheel. [Image Credit: NASA/JPLCaltech/MSSS].
Fig. 2. Functional schematic of a Stochastic Optimization Framework (SOF; after [9]): The SOF efficiently
samples the entire model/process/system-intrinsic parameter space by repeatedly running the respective
model/process/system forward and by comparing the
outcomes against a desired outcome, which results in a
fitness to be optimized.
Fig. 3. Example shortest rover traverse obtained with
RTOP in a 3D altitude map.