«The Robotics Institute Carnegie Mellon University Pittsburgh, PA 15213 May 13, 2005 Submitted in partial fulfillment of the requirements for the ...»
Figure 3-7a and d show the paths from both cases. Interestingly, the BESTDPARMS solution is shorter in duration than the BESTPCOST solution (4864 units) and yet wanders more by taking more steps (272 steps versus 158). The BESTPCOST solution, because it is penalized at every step for plan length and the better ( X, Y ) function prioritizes shorter duration, deviates little from the direct diagonal path between the start and goal (8 additional steps above the minimum 150). Meanwhile, the BESTDPARMS solution is not penalized for extra steps, as long as the duration falls below the maximum. The path loiters aimlessly for some duration at the upper right of the plot and deviates from the direct diagonal for the remainder, all in order to seek low-cost energy states.
The progress distance plots in Figure 3-7c and f illustrate the tendency of the BESTDPARMS plan to be more indirect than the BESTPCOST counterpart. In Figure 3-7c, note that the progress trajectory heads at a steady slope towards the goal. In contrast, the trajectory of the BESTDPARMS solution (Figure 3-7f) oscillates at the beginning (corresponding to the period of loiter near the start) and then makes a slow but more direct approach to the goal for the remainder of the steps.
Despite being penalized for plan length, the BESTPCOST plan does a better job at minimizing energy requirements over the path. Figure 3-7b and e show the energy profiles for both solutions. In the plots, the curves rise in anticipation of a future energy cost. The curves rest at zero when energy costs are negative (net battery charging), and descend when costs are positive (net battery discharge). The BESTPCOST solution results in lower minimum required battery charge averaged over time (16.3 units versus 25.9 units) and a smaller peak energy requirement (91 versus 99 units). Presumably, this is because energy is treated directly in the objective function of the BESTPCOST approach, and indirectly through state dominance and resolution pruning in the BESTDPARMS approach.
Figure 3-7: Qualitative Comparison of Planned Routes and Energy Profiles between BESTPCOST Mode (a and b) with BESTDPARMS Mode (c and d) with Tmax=TBESTPCOST Figure 3-8 continues the study, with two more examples of BESTDPARMS solutions. In these tests, the BESTDPARMS solutions were given more freedom by raising the upper bound on plan duration to 2 times the BESTPCOST
duration (BESTDPARMS Case B, shown in Figure 3-8a, b, c) and 3 times the BESTPCOST duration (BESTDPARMS Case C, in Figure 3-8d, e, f). Observe first that the Case B path in Figure 3-8a loiters over a wider area than the solution in Case A in Figure 3-7d. The progress plot for Case B in Figure 3-8c confirms this - it oscillates more than the solution from Case A. This behavior results from the greater upper bound in plan duration - the plan is 440 steps long instead of 272. Interestingly, the extra duration allowed for the Case C path in Figure 3-8d does not appear to cause path further path growth from the Case B path in Figure 3-8a. The progress plots indicate differently. The progress plot for Case C (Figure 3-8f) shows an even greater period of oscillation over Case B (Figure 3-8c), even though the path didn’t change from the shorter plan. The explanation is that the plan traverses the same ground more than once before moving to the goal. The planner has evidently determined the optimal loiter pattern.
The energy plots further substantiate this claim. Observe that the energy profile for Case B (Figure 3-8b) has a period of relatively low values (shown with a bracket labeled “1”) corresponding to the early part of the oscillatory behavior in the progress plot below it. This interval is followed by a sequence that completes the oscillatory steps and then continues to the goal (shown with a bracket labeled “2”). Looking closely at the Case C plot, one observes that these identical profiles also appear there. Profile 1 repeats four times in the Case C solution, and the last of these is followed by Profile 2 which continues to the goal1. Apparently, ISE determines the optimal path to the goal (by following Profile 2), and the optimal loiter pattern (Profile 1), which it repeats as many times as possible prior to moving to the goal. The longer the plans are allowed to be, the longer the plans linger near the start state in the optimal loiter pattern. This strategy yields improvements in time-averaged energy requirements for longer plans - the Case A, B, and C averages are 25.9, 22.1 and 18.4 units respectively. Note that none of the BESTDPARMS solutions can match the energy performance of the BESTPCOST solution.
In conclusion, it is important to state that these results are particular to the specific parameters used for the tests.
Tests done on other cost maps and under different DPARMS time resolutions resulted in different behaviors. However, for this domain, tests do seem to display several patterns. The BESTPCOST approach yields more direct paths and better time-averaged energy solutions. Interestingly, the direct paths do not typically correspond to the minimum-time path. To meet the time-averaged energy performance of the BESTPCOST solution, a BESTDPARMS solution seems to require far greater time to repeatedly follow an optimal loiter pattern that drives the average energy lower.
1. A portion of Profile 2 also appears at the end of the energy plot for BESTDPARMS Case A, in Figure 3-7b.
Figure 3-8: Qualitative Comparison of Planned Route, Energy Profile and Progress Distance between BESTDPARMS Mode with Tmax=2TBESTPCOST (a through c) and Tmax=3TBESTPCOST (d through f)
if time and energy costs are selected differently, for example with larger contiguous regions of low or high cost? Are there other objective functions that better achieve desired results? These questions are reserved for future work.
4. Mission-Directed Path Planning This chapter describes the challenges posed by mission-directed path planning and introduces the TEMPEST planner, a central development of the thesis, that meets many of these challenges. The chapter defines several algorithms of increasing sophistication that enable planning in a domain combining spatial, temporal and resource dimensions, and shows how the advantageous qualities of ISE are leveraged to achieve efficient performance. Finally, the chapter demonstrates TEMPEST in a simulated multi-goal mission. TEMPEST enacts contingency planning to survive overnight in response to an unanticipated but necessary detour.
4.1 Problem Definition The principal goal of path planning is to determine a feasible or optimal route between one position and another.
What qualifies as feasible or optimal varies with the specific application problem. Mission-directed path planning seeks to derive routes for rovers exploring planetary surfaces. In contrast to other planners developed for planetary surface motion, mission-directed path planning is intended to plan over comparatively larger scales and over longer durations. Furthermore, where a majority of planetary-oriented work focuses on obstacle avoidance, the missiondirected planning domain seeks a much stronger connection with other important factors in mission planning - time, resources, operational constraints and mission returns. The following sections examine the central issues in this new domain.
4.1.1 Terrain Interaction and Obstacle Avoidance Planetary navigation requires a robot to travel over terrain while avoiding features that impede progress to a goal position. Terrain features that might pose difficulties for navigation span a continuum of spatial dimension, from rocks at or below the scale of a vehicle to mountains many orders of magnitude larger. Much of the prior work has addressed obstacle detection, classification and avoidance for terrain features near the scale of a vehicle, called local navigation. In contrast, this work concentrates on the other end of the scale spectrum - global navigation.
MISSION-DIRECTED PATH PLANNING
In the local planning problem, kinematics and dynamics are central in determining whether terrain is trafficable. In wheeled vehicle configurations, the wheel diameter often strongly influences the size of obstacles the vehicle can drive over. A vehicle’s steering scheme limits the minimum radius of curvature it can follow while driving. In some cases, dynamics are also important - a vehicle might use its forward momentum to aid in surmounting a steep slope and a fast-moving vehicle must consider its speed, center of mass and traction with the ground in evaluating the safety of candidate steering arcs. Since local navigation considers the area near the vehicle, it is often practical to represent the terrain in at a resolution smaller than the vehicle footprint. At this high resolution, path planning must consider the vehicle size and the radii of turns.
For practical reasons, global navigation de-emphasizes vehicle kinematics and dynamics. Data of the resolution required by local navigation are rarely globally available, and representing large regions at small scale is computationally impractical. Absence of high resolution data means that typical kinematic and dynamic effects cannot be adequately modeled. Global terrain is often represented at a granularity at or above the size of the vehicle. Rocks and holes at the rover scale might be totally ignored in the global context, and turning arcs might be completely encompassed within a single terrain model cell. Dynamics might affect the traversal of a small slope, but would not significantly impact the ascent of a large slope. Often, global navigation represents the vehicle as a point, and analyzes global terrain data solely in terms of gross characteristics - elevation, slope, mean obstacle density, etc.
One immediate impact of ignoring kinematics and dynamics is that the state space parameters need not include joint angles, velocities or accelerations. This makes it computationally tractable to consider other state variables like time and energy in planning.
Navigation in the large scale demands a new set of considerations. Large scale terrain units include hills, valleys, mountains, canyons and craters. In the local navigation problem, it is often convenient to classify rocks as obstacles that cannot be traversed and hence must be avoided at all cost. At the global scale, while a planner might reasonably classify steep-sided canyons or mountains as intraversible, it cannot rule out navigation over smoothly varying hills and valleys. Rather than classify entire features as obstacles, the global path planner must consider how a vehicle is affected by gross terrain properties. For example, to determine whether an area is traversable, a planner might evaluate terrain slope, vehicle heading and vehicle mass properties to determine the likelihood of tipover; gross terrain roughness to determine likely vehicle speed and mechanism wear and tear; and slope, heading, roughness and soil cohesion to estimate locomotion power. Rather than prevent access to large areas on a map, the mission-directed approach seeks to provide models of access to as much of the terrain as possible1.
1. A problem that local and global planetary navigation share is that the places most interesting to explore and the places most challenging to navigate are often the same.
Large scale terrain affects more than just vehicle locomotion. Large positive terrain features occlude sunlight and prevent direct line-of-sight visibility to the Earth or orbiting relay spacecraft. Loitering next to a large hill could significantly reduce the duration of a communications pass or inhibit solar battery re-charging, but might keep an overheating vehicle sufficiently cool. Going to high elevation might enable a rover to view lower surrounding terrain, and might improve visibility to communications assets. Gross slope of the local terrain influences the angle of antennas or solar arrays on the rover. Driving on one side of a ridge might point a solar array towards the sun, affording a vehicle extra hours of driving time. It is the intent of this work to capture these added effects in the navigation planning process.
4.1.2 Temporal Planning The planetary exploration domain is dynamic. Planetary motion affects sunlight, shadows, solar flux and visibility to communications assets like orbiting spacecraft or Earth-based ground stations. Local environmental parameters change as a vehicle moves from place to place. A vehicle expends and collects resources at rates that vary as a functions of the activity and the environment.
To date, path planners intended for planetary surface exploration have ignored time. Local planetary navigation planners have had two principal objectives - first, to avoid obstacles that might harm the vehicle; and second, to follow a minimum distance (or minimum time) path to a goal position. Neither objective forces a consideration of time - rock obstacles are static, and the minimum-distance path to a goal is determined entirely by the placement of obstacles in the local environment. For short-distance traverses, where local terrain parameters remain roughly constant, activity planning and scheduling software can adequately incorporate time-varying effects into predictions of daylight, shadowing and resource profiles.
In contrast, route selection in a mission-directed context must consider time. Mission success depends on having adequate resources, whose availability varies with time and position (i.e. route). Mission activities must often satisfy time-varying geometric constraints or time-based operational constraints - traverses in advance of these activities must not prevent them from being met. Depending on terrain conditions, two separate paths of equal distance might require vastly different amounts of time to follow - traversing flat, smooth terrain with few obstacles might take far less time than traveling on terrain covered with obstacles that must be either avoided or carefully crossed. In such cases, one cannot ignore time and adequately address path planning.