«The Robotics Institute Carnegie Mellon University Pittsburgh, PA 15213 May 13, 2005 Submitted in partial fulfillment of the requirements for the ...»
00:00 06:00 12:00 18:00 00:00 06:00 12:00
00:00 06:00 12:00 18:00 00:00 06:00
00:00 06:00 12:00 18:00 00:00 06:00 12:00 18:00 06:00 12:00 18:00 00:00 06:00 12:00 00:00
Figure 4-9: Initialization for Time-Bounded Sequential Goal Planning: a) Originally-specified reachable and allowable time limits; b) Earlier goal-imposed allowable time limit; c) Goal time interval definitions; d) Final segment goal states and query start states
MISSION-DIRECTED PATH PLANNING
Returning back to Table 4-9, in computing the final goal allowable time interval, the algorithm searches to find the last time-bounded goal in the goal sequence (L62 and L63). It projects the latest allowable time from the end of that goal time bounds to the final goal ( t max1, from L64), and keeps the minimum of t max1 and t max2 as the true closing time (L66 and L73). For earlier start intervals, the time bounds propagate from the next latest goal interval just as with INIT_SEGMENTS ( S, Γ, k ) (L70 and L71). The only difference is that the overall goal time interval is the intersection of three time ranges - the reachable, allowable and goal-limited time bounds.
Figure 4-8c shows the effect of the intersection. In the specific case of goal N-1, the latest allowable time falls later than the mission-imposed goal time bounds. The intersection removes a large time interval from the allowable unbounded sequential goal range from consideration. In the case of goal 2, the latest allowable time falls earlier than the mission-imposed bounds, causing the minimum allowable speed restriction to take precedence. For goal 1, no mission-imposed time bounds exist, and so again, the minimum allowable speed restriction takes precedence.
Importantly, if at any time during the initialization a goal time interval is computed to be empty, the mission, as specified, is infeasible.
The new initialization procedure is all that is required to enable TEMPEST to plan and re-plan for time-bounded sequential goals. Once segments are initialized, either prior to planning or in response to execution updates, PLAN_SEQ_GOALS ( S, Γ ) solves for the plan that obeys the temporal bounds on goal completion.
4.4 Plans TEMPEST plans consist of a fully-ordered sequence of state-action pairs, called waypoints, corresponding to the
states and arcs that follow the optimal path from the start state, through all intermediate goals, to one of the designated final goal states. A plan π with N waypoints takes the form:
Each state is an aggregation of the ISE IPARMS, DPARMS and auxiliary resource variables for the application. The corresponding action is the action departing from the state.
As a sequence of waypoints, a plan acts as a guide for path execution whose granularity is defined by the resolution of the spatial coordinates and the other state variables. Each action in the plan must be initiated as close as possible to the position and time of the waypoint. Each resource variable specifies the minimum resource level that must remain in order to satisfy all the goals in the plan, as described in Chapter 3, Section 3.1.5. A deviation from plan position greater than the spatial resolution of the map, or in timing greater than the time equivalence class resolution may justify re-planning. Similarly, if any resource falls below the recommended minimum level as dictated by the plan, successful re-planning is necessary to ensure mission completion.
4.5 Plan Evaluation In evaluating TEMPEST planning behaviors, it is useful to introduce some approaches for analyzing plans. Plan solutions are often difficult to interpret. Even when a planner produces formally correct and optimal plans, it is not immediately obvious whether plans display a desired behavior, how much of a behavior to attribute to artifacts of representation versus to good planning, or how to compare plans stemming from alternate approaches. This section presents some simple analysis tools that help with this problem.
4.5.1 Distance Plan distance is an important path planning measure. For many path planners, minimizing feasible path length is the single objective. Though minimizing path length is not the only objective for TEMPEST, it is still very important. In many cases, the shortest path is the least costly in terms of resources, mechanical stress and vehicle risk. This thesis introduces two factors that describe a plan’s increase in path length above the planar Euclidean distance between goals.
MISSION-DIRECTED PATH PLANNINGFigure 4-10: Representation Factor for Regular Four and Eight-Connected Grids Representation Factor f R : This factor encodes the ratio of the minimum distance possible under the planner’s state
representation ( D rep ) to the planar Euclidean map distance ( D map ) such that:
Representation factor encodes how much a planner’s underlying spatial representation contributes to an extension of path length beyond the minimum. Representation factor has a minimum value of 1, and a maximum value that depends on the system of spatial representation. TEMPEST uses a grid-based representation for terrain. Actions transition between cells in the grid and their eight nearest neighbors, forming an eight-connected graph. The minimum eight-connected plan distance between two points depends on the ratio of their relative grid distance in the xcoordinate (∆x) and the y-coordinate (∆y). When the start and goal lie along a common horizontal (∆x/∆y= ∞ ), vertical (∆x/∆y=0) or principle diagonal axis of the graph (∆x/∆y=1 or ∆x/∆y=-1), the minimum eight-connected distance
is equal to the Euclidean map distance between the points ( f R = 1 ). Since the eight-connected path cannot assume arbitrary headings, other ratios of ∆x-to-∆y produce indirect paths whose path lengths exceed the Euclidean distance between the points ( fR 1 ). Figure 4-10 plots f R for both four- and eight-connected motion on regular grids given the relative positioning of the start and goal. The four-connected graph, corresponding to the “Manhattan distance”, yields a worst-case error of 2 for two points directly on a diagonal. At worst, the eight-connected graph contributes a 8.2% increase in path length.
Avoidance Factor fA : This factor encodes the ratio of the plan distance ( D plan ) to the minimum distance possible
under the planner’s state representation ( D rep ) such that:
Avoidance factor captures the amount of extra distance, inserted by a planner, to avoid obstacles and sub-optimal regions. Its minimum value is one, and its maximum value is unbounded. It is important to note that an avoidance factor of 1 does not mean that the path it describes has not avoided obstacles or areas of high cost. In general, a path with the minimum representation distance D rep is not unique, and has many degrees of freedom with which to avoid obstacles or high cost areas. Observe in Figure 4-11 that the solid paths are all of minimum length under an eightconnected grid representation f A = 1, and yet avoid obstacles. The dashed path, however, covers more distance, and so has an avoidance factor greater than one.
For plans solved under an objective function that minimizes path length, avoidance factor will be greater than 1 only if obstacles prevent all paths yielding the minimum representation distance Drep between points. For objective functions that minimize some other quantity, like duration or energy expense, an avoidance factor greater than one may indicate a deviation in path to avoid a costly region.
MISSION-DIRECTED PATH PLANNING4.5.2 Time In temporal planning, where actions are not necessarily mobile, plan duration is a more appropriate measure of plan length than distance. For mobile actions, the distance factors in Section 4.5.1 also encode the increase in plan duration due to increased path length. Beyond this, stationary actions inserted into a plan also cause an increase in plan
duration. If the minimum map traverse time and total duration of goal actions are defined respectively as:
Slower driving speed and additional stationary actions inserted into the plan motivate the following additional factor:
Loiter Factor f L : This factor encodes the ratio of the minimum plan duration, considering traverse time and goal
action durations, to the actual plan duration, such that:
Loiter factor expresses the degree to which a plan specifies less-than-maximum driving speed or stationary actions beyond the goal actions.
4.6 Simulation Results 4.6.1 Re-Planning We present a sample planning problem to illustrate TEMPEST behaviors. A contour map in Figure 4-12 shows the elevation profile for synthesized terrain on a mock Martian surface. Mountains form a central pattern of valleys running in a North-South (up-down) direction, and a rounded crater lies to the northeast. The rover starts in the morning at the southeast corner of the map (“Start”), and must traverse to the northwest corner (“Goal 2”). Scientists designate a Via Point goal in the valley, “Goal 1”, to promote travel through the valley en route to the final destination. Mission engineers (or an onboard planner-scheduler) require the robot to reach Goal 2 with 100 W-hr of charge left for subsequent operations.
MISSION-DIRECTED PATH PLANNING FOR PLANETARY ROVER EXPLORATION
Unfortunately, the elevation map provided to the rover is incorrect. Its preliminary map indicates a clear exit from the valley system at its northern extreme, between two peaks. The actual terrain involves a far higher and steeper pass, beyond the locomotion capability of the rover.
In this example, a simple simulation of the mission demonstrates the value of TEMPEST. At each plan step, the simulated rover plans a path from its current state, then “executes” the first step of the plan through path integration. At each new point, the rover “senses” the local environment, detecting the actual elevation, slope and lighting of all cells within two pixels. Based on this new data, TEMPEST re-plans a path and the process continues.
Figure 4-12: Initial Plan Route: TEMPEST plans a path from “Start” at the southeast of the map, to Goal 1 in the valley in the center of the map, and then through the saddle point to Goal 2 in the northwest.
Figure 4-12 shows the initial TEMPEST plan route. With the exception of a few minor path deviations, the route follows a direct path from the start through each of the goals. Subsequent re-plans during “execution” yield similar routes. The solid red curve in Figure 4-14 shows the timing for the initial plan. The slope of the curve represents the rover speed toward Goal 2. One observes that it is only slightly slower than the theoretical fastest, straight-line approach, as shown by the steep dash-dot line. The red solid line in Figure 4-15 shows the required battery energy profile for the initial plan. The plan allows the robot to begin with an empty battery, and only requires increasing
MISSION-DIRECTED PATH PLANNINGcharge at the end of the plan to meet the Goal 2 requirement. This indicates that solar energy provides ample energy for locomotion.
The simulated rover reaches the Goal 1 Via Point and continues without stopping toward Goal 2. The nearest valley exit, according to its internal elevation map, lies to the northwest directly in line with its next goal. However, as it approaches the supposed low pass, the robot detects the steep, intraversible pass. Figure 4-13 shows the first substantial re-plan in the sequence, based on this discovery. With no escape to the northwest, TEMPEST selects the least expensive alternative - a detour through a narrow valley to the northeast (the blue dashed line). This new route is a significant departure from the original. The extra distance means that the robot cannot reach Goal 2 before sundown.
The original plan did not anticipate the extra burden of nightfall on battery reserves. However, TEMPEST determines a prolonged Charge action followed by overnight Hibernation will enable it to reach Goal 2 by late morning the following day. Figure 4-14 shows the rate of travel towards Goal 2 for the detour as a dashed blue line. Note that the robot must first reverse course, and then remains stationary for nearly 18 hours, first in sunlight (charging batteries),
then overnight (hibernating, in the shaded region). The following morning, the rover continues its course around the mountain, then moves to Goal 2.
Figure 4-14: Progress Distance vs. Time: The initial plan (shown in red) follows a very direct path (compare to the straight-line maximum speed curve). The re-plan detour (shown in blue) requires the rover to endure a night in hibernation, as shown by the flat region indicating no forward progress. In the morning of the following day, the rover resumes its course to Goal 2.