«The Robotics Institute Carnegie Mellon University Pittsburgh, PA 15213 May 13, 2005 Submitted in partial fulfillment of the requirements for the ...»
Based on the approach of Bobrow et al. , the technique splits the time-optimal problem into two by first determining the top several minimum distance paths, and then optimizing each of their velocity profiles using kinematics, dynamics and dynamic constraints. An obvious disadvantage with this sequential approach is that the minimum-distance path is not necessarily the time-optimal path. Aside from the approach used to optimize the path, an interesting feature of the approach is the use of B-spline patches and B-splines to model the terrain and paths, repectively. These continuous parametric functions enable a smooth integration of trajectories, but prevent optimization using gradient descent since the parameters to be optimized are the control points for the spline curves.
MISSION-DIRECTED PATH PLANNING FOR PLANETARY ROVER EXPLORATION
Another approach, by Pai and Reissell, represents terrain at multiple resolutions using wavelets, and plans paths hierarchically from the coarsest to finest maps . The authors show that when applying wavelet filters in natural terrain, the wavelet coefficients in smooth areas shrink quickly at greater filtering levels (i.e. at higher resolutions), while in rough terrain, coefficients persist through many iterations. Therefore, in smoother areas, the lower-resolution wavelet levels match the original data well, while in rough areas, the coarse levels model the original terrain with significant error. Under this observation, the authors use an error measure at coarse terrain levels, a quantity that falls directly from the wavelet filtering operation, as a metric for terrain smoothness. Using the smooth terrain metric, the planning algorithm seeks smoothness-optimal paths at the lowest resolution, and then advances to higher resolutions in an “anytime” manner to refine the original path. The authors also examine various means of computing cumulative path cost, and derive a generalized worst cost function that heuristically prefers safest paths. Under experiments using digital elevation models of actual terrain, the algorithm appears to select the best paths through terrain. The approach here is novel, and potentially very useful in this work as a means of terrain analysis. However, it takes a heuristic rather than model-based approach to cost calculations, so is difficult to use in conjunction with power estimation that is required of an energy-cognizant path planner.
As mentioned in Section 2.1.1, grid-based representations suffer from memory inefficiency and the restriction of motion to paths between cell centers (or grid vertices). Another body of work plans paths on terrain approximated by polygonal regions with homogenous properties. This representation efficiently maps homogeneous regions and allows motion to occur in arbitrary directions. Richbourg et al.  introduce a technique for finding optimal paths, in terms of energy expense, where costs within the regions are isotropic - where the path cost per unit distance does not vary with path heading. They show that optimal paths consist of straight line segments across regions and direction changes between regions governed by Snell’s Law from optics literature. This restriction of paths to Snell’s Law trajectories, combined with several pruning rules, enables an efficient search of the region-wise continuous space for optimal paths. Rowe and Ross  extend this work, again for minimum energy expense paths, to travel through regions of anisotropic costs - where legal directions on sloping terrain are defined by maximum vehicle power limitations, sideslope tipover, and downhill braking. They prove that optimal paths can only cross these regions in one of four ways and, as in , that direction changes between regions must follow Snell’s Law. Sun and Reif  apply an efficient discretization to the polygonal region boundaries, using Steiner points, and a more efficient search algorithm, to display good search performance on maps of natural terrain.
In another extension of the work by Richbourg, et al., Rowe and Lewis  describe a method for defining paths for both land and airborne vehicles to either minimize or maximize visibility with respect to fixed observers (e.g. representing beneficial resources or enemy observers) while minimizing path cost in terms of an energy metric. The planner divides the free space into convex visibility regions, defined by visibility to each observer, and assumes each of these volumes to be homogeneous in terms of both energy and visibility costs. Assuming linear costs, the authors
apply the Snell’s Law model to path propagation and minimum-cost path angle transitions between regions. Though interesting, the method appears more directed towards flight, and in its quest to abide by Snell’s Law, uses overly simplistic, linear cost models. However, to its credit, the method does raise the issue of effective space decomposition, and addresses the balance between visibility and energy costs.
Several robots have used the D* algorithm ,, in conjunction with the Morphin local planner (Section 2.7.1) to drive autonomously on rough terrain over long distances. Local maps derived from stereo camera data are also used to populate a cost map in D* based upon estimated terrain traversability. D* produces an optimal path to a global goal position, given all available information. Unlike Morphin, which assigns infinite cost to unknown regions, D* planners have historically been designed to assign zero cost to areas with no existing data. Typically these no-data regions are at the field-of-view limits of the cameras, and will ultimately contain data as the rover gets closer. As new data is introduced, D* efficiently re-plans by repairing only those regions affected by the changes.
Hence the optimal global path updates with each stereo image set, typically several times per second. The local obstacle avoidance and global planner each vote with their respective arcs; the higher-value arc is sent as a command to the rover controller. A relative weight factor allows operators to tune the behavior of the robot. Weights emphasizing obstacle avoidance will steer further from obstacles, but may avoid legal paths through narrow passages. Conversely, boosting the weight of the global path planner improves the likelihood of finding paths, but also increases the chances of collision with obstacles. The combination of local and global path planning has proven itself in many natural terrain rover experiments , , .
Of recent popular interest is the DARPA Grand Challenge automated racing contest. In 2004, teams developed vehicles and software systems to drive autonomously 143 miles in under 10 hours on a combination of rough roads and off-road conditions. Though no team completed the course, Urmson et al. describe Sandstorm, the system that drove further and faster than all other competing vehicles . Teams were supplied the race route only 3 hours prior to the start of the race, in the form of GPS waypoints spaced an average of 89 meters apart, maximum speed limits, and maximum allowable corridors of travel. Sandstorm path planning was a mixed-initiative system that combined automated route generation on a regular grid at 1 meter resolution to follow the GPS points while staying within corridor bounds and minimizing travel on unknown and poor road conditions, subsequent automated route vectorization to compress and simplify the plan representation, and human inspection, correction and smoothing of paths using various graphical interface tools. Automated planning used coarse road classifications, as well as distance from the center of the drive corridor, as a basis for driving cost. It appears that a velocity profile was selected in a separate step after route planning. Onboard GPS and a scanned laser enabled Sandstorm to follow the course 7.4 miles at speeds up to 36 miles per hour. This system clearly did not freely select its global route, but rather connected pre-selected waypoints and established a speed profile that would enable completion of the route within the race deadline.
MISSION-DIRECTED PATH PLANNING FOR PLANETARY ROVER EXPLORATION
Despite their applicability to long-distance path planning, none of these approaches considers time-dependent costs.
For example, though the representation of terrain using homogeneous cost regions and Snell’s Law in  is attractive, it is not clear how to extend the model when cost regions are time-varying. Furthermore, the cases that seek minimum-energy paths ignore sources of incoming energy, such as solar energy. They minimize resource costs, but none models renewable resources where a balance must be achieved between input, output and storage. As a result, none can predict how a finite battery capacity might prevent certain paths, or how resource collection might extend the set of feasible paths. However, in terms of operational utility, the efficient re-planning provided by D*based planners is clearly advantageous.
2.8 Planning and Scheduling In an entirely different vein of research, the artificial intelligence community has evolved two related fields - planning and scheduling - whose overarching goal is to create feasible sequences of activities that start from a set of preexisting conditions and achieve a desired set of goal conditions. Planning decomposes high-level goals into atomiclevel activities that collectively achieve the goals. There may be many alternate ways to break tasks into subtasks, and activities may have complex interrelationships that prevent loose ordering. Scheduling takes a set of activities and determines an ordering that respects constraints and resource demands to accomplish an overall task.
Automated activity planning and scheduling software has been successfully deployed on spacecraft and prototype planetary rovers. The Remote Agent Experiment demonstrated automated planning and scheduling onboard the Deep Space 1 spacecraft , . The planner/scheduler software (PS) accessed a database of long-term mission objectives and planned concurrent activity schedules over multi-day planning horizons. The PS derived planning problems by taking goals relevant to the planning horizon and projecting initial spacecraft conditions to the anticipated plan execution time. Beginning with an incomplete plan, the PS searched over plan space, adding constraints and subgoals where necessary and reordering activities, to create full partially-ordered plans. The PS also maintained onboard state predictions, for example resource levels, under the same model as activities in primitives collectively termed tokens.
ASPEN was developed to automate planning and scheduling for spacecraft and rovers . The software uses a most-committed, local, heuristic iterative repair approach to decompose high-level mission goals into concurrent action sequences that respect operational and resource constraints. Because the search is not systematic, there is no guarantee that all combinations of actions will be searched exhaustively, or that disadvantageous sequences will not be examined more than once. However, ASPEN achieves planning, scheduling and resource management at far less computational expense than for more flexible, exhaustive approaches. The ASPEN system and the derivative CASPER system each produced coordinated activity schedules, based on science and engineering team requests, for the JPL Rocky 7 rover (see Figure 2-2). The activity planners repair plans in response to changing goals and other
unexpected events. Rover activity scheduling considers resources and environment effects (e.g. day/night cycle, sun angle), but demonstrates only loose coupling to path planning. ASPEN calls a path planner that is ignorant of absolute time and resources to estimate the duration of small traverses. ASPEN’s primary focus is on conflict resolution through event rescheduling or reordering. Furthermore, ASPEN and CASPER essentially react to evolving initial state and updated mission goals. Neither has the ability to plan in anticipation of a range of possible outcomes, and so cannot build in contingency branches to plans.
2.8.1 Contingency Planning Contingency planning is addressed by Bresina and Washington under the Contingent Rover Language (CRL) and the propagation of expected utility distributions . Combining the action condition structure of classical planning and conditional rewards characteristic of decision-theoretic planning, the authors present a means of efficiently evaluating contingent branches in an existing plan. The method specifies probability distributions on execution times for all events, and defines local rewards conditioned on action success or failure. Valid action execution is defined under start, wait-for, maintain and end conditions, which include requirements on initial available resources. The method assumes knowledge of resource availability as a function of time. Given an existing plan with conditional branches, the algorithm first forward-propagates distributions of possible action start times, given action duration distributions and conditional requirements on actions, to establish temporal bounds on outcomes. Then, it backward-propagates distributions of utility from the branch endpoints, restricting computation to the time distributions. The resulting util
MISSION-DIRECTED PATH PLANNING FOR PLANETARY ROVER EXPLORATION
ity distributions specify the expected value of executing each branch, conditioned on start time. The advantage under this approach is that the utility distributions remain valid regardless of the temporal outcome of actions, as long as the resource bound model also remains valid. Though this approach pre-supposes a profile of resource availability, it estimates contingent branch utility factoring in whether actions can be legally executed. An extension of contingent planning that reasoned about uncertainty in activity time and resource consumption, using CRL and the Pico planner (based on EUROPA ), was used to successfully demonstrate multi-target single-cycle instrument placement on the K9 rover .