«The Robotics Institute Carnegie Mellon University Pittsburgh, PA 15213 May 13, 2005 Submitted in partial fulfillment of the requirements for the ...»
4.3.3 Single-Goal Re-Planning TEMPEST enables two types of re-planning - state update re-planning and model update re-planning. Invariably, mission execution does not follow plans precisely. Often, unforeseen operational events cause deviations from the route, schedule or resource guidelines. In response to these deviations, a user calls PLAN_SINGLE_GOAL ( S', G ) with the updated state. Since the segment goals are initialized, the function skips the goal setting steps and simply re-queries ISE with the updated initial rover state (L16). ISE extends its graph to the new state, yielding a new optimal plan.
There is no guarantee that the updated solution is similar to the original. This is state update re-planning.
Re-planning must also occur when changes in the World Model or Rover Model alter arc transitions, either in terms of state change or arc cost, as encoded through APARMS. Given model updates, TEMPEST reports the APARMS changes for each affected IPARMS state set to the ISE instance, and then calls PLAN_SINGLE_GOAL ( S, G ). ISE determines the states affected by the updates in GET_PATH_COST ( S' ) and repairs the nodes in the graph to reflect the new optimum. ISE, and hence TEMPEST, is efficient because it restricts its computations to the set of nodes affected by the changes.
Typically, new data about the world comes from rover sensors. Under the backwards-chaining search, the rover position is at a leaf node of the search graph. Therefore, local changes deriving from rover sensor data affect only the ends of the graph, and are inexpensive. In contrast, global World Model changes and basic changes to the Rover Model often affect a large portion of the search graph, and can lead to far more expensive searches (see Chapter 3. for experimental results).
18:00 00:00 06:00 12:00 18:00 00:00 06:00 12:00 18:00 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 12:00 18: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 00:00 06:00 12:00 18:00 06:00 12:00 00:00
Figure 4-6: Single-Goal Planning. a) Goal time interval definition; b) Reachable and allowable space; c) Goal states and start query; d) Progression of search from goal states; e) Completion of search; f) Optimal plan
MISSION-DIRECTED PATH PLANNING4.3.4 Sequential Goal Planning The TEMPEST sequential goal planning problem involves planning a path from a start state S through a sequence of goals Γ = G 1, …, G N (see Figure 4-7). In general, each goal is position-referenced action that must be executed before moving to the next goal. Each successive pair of goals in the sequence defines a segment. By chaining ISE searches in series, TEMPEST enables planning through a sequence of goals. TEMPEST creates a separate ISE instance for each segment. As with ISE search, TEMPEST sequential goal planning happens in backwards chaining order, from the last segment to first segment.
Sequential goal planning is similar to single goal planning, but differs in some important ways. Principally, the optimal solution for an arbitrary segment is not necessarily part of the optimal solution for the entire goal list. Therefore, it is incorrect to simply chain locally-optimal segments to form the globally-optimal solution. Instead, TEMPEST tracks multiple path candidates through all the segments, then solves for the optimal surviving candidate in the first segment. We describe the process below.
As with single-goal planing, TEMPEST begins by initializing the start and goal time intervals for all segments. This requires a new function, INIT_SEGMENTS ( S, Γ, k ), whose algorithm appears in Table 4-5. Figure 4-8 contains diagrams depicting the essential steps of sequential goal segment initialization and planning. As in Figure 4-6, the horizontal axes represent time. The vertical axes span all the goals, whose vertical separation corresponds to the distance between them. Each vertical interval between goals represents one of the “segments” of the total path. As with single-goal planning, the process for segment planning proceeds in backwards-chaining order, from the top right of the diagram to the bottom left.
Rather than initializing a single segment, the new function initializes the range of segments, in reverse order, from some final segment k, and through an earliest segment defined by next ( Γ ). In the first call to the function, next ( Γ ) is equal to 1 and k is given a value of N, the total number of segments. For re-planning, the limits take on different
Lines L21 through L24 define the minimum and maximum times for the final goal. The minimum distance to the final goal is now the sum over all minimum segment distances (L22). The minimum possible time is calculated in the identical way to single-goal planning. The maximum allowable time now takes into account the sum of goal action durations. This calculation is depicted graphically in Figure 4-8a). The line of fastest approach rises steeply from the opening of the start time interval, while the line of slowest allowable approach ascends more slowly, with pauses for each goal action. As before, these times define the reachable and allowable time ranges for the goal, whose set intersection becomes the final goal time interval.
The earlier segment goal time bounds are computed recursively from later goal time intervals. The first reachable time is computed by subtracting the minimum traverse time from the opening of the next goal interval (L26). The last allowable time is found by subtracting the fastest possible traverse and the duration of the next goal’s action from the closing of the next goal interval (L27). As with the final goal, an earlier goal time interval is the intersection of the reachable and allowable time bounds (L29). Figure 4-8b) shows the calculation graphically. From the final goal time interval, the line defining the earliest reachable bounds extends downwards without pause from the opening of the
MISSION-DIRECTED PATH PLANNING
final goal time interval, while the boundary defining the latest allowable times descend in stair-step fashion, pausing for each goal action. The function creates an ISE instance for each segment, and returns upon initializing the first remaining segment, given by next ( Γ ).
Once the segments are initialized, planning occurs in an updated function PLAN_SEQ_GOALS ( S, Γ ), defined in Table 4-8, and depicted in the remainder of Figure 4-8. Starting with the last unplanned segment, the function alternates between defining the ISE goal states and planning the segment. If the last unplanned segment is also the final segment, the goals are defined as in single-goal planning (L36-L39). Before moving on to earlier segments, the function proceeds to planning for the current segment. Recall that the locally optimal segment solution is not, in general, part of the global optimum. To account for this, TEMPEST generates a number of time-distributed plan solutions. First, it defines a start time interval for the segment, equal to the previous goal time interval (for all but the first segment - see L46), and equal to the overall plan start time interval for the first segment (L48). At regular intervals within the start time interval (the time DPARMS resolution equivalence resolution), PLAN_SEQ_GOALS ( S, Γ ) makes a query to ISE with GET_PATH_COST ( S ) (L49-L52). If the query results in a solution, the solution is recorded. If not, the function continues with next query. Figure 4-8c) shows the start state queries as discrete intervals over the start of the last segment. Figure 4-8d) shows how some of these queries result in feasible plan segments, while others do not1. Once all the query states are exhausted, the function continues on to the next earliest segment. However, if no solutions result from the queries, then there is no feasible plan for the problem.
To define the goals for earlier segments, the function copies the initial states and path costs from the following segment’s path solutions (L41-L43). Again, planning proceeds as a series of queries to an ISE planner, and may result in a list of plan segment solutions. The process repeats for all segments down to the next remaining segment (Figure 4-8e). The effect is to chain segment solutions together to build long, consistent plans one segment at a time. The earliest segment has only one valid start time interval, and so involves only one ISE query. The resulting solution is the global optimum for the sequential goal problem, depicted in Figure 4-8f).
4.3.5 Sequential Goal Re-Planning TEMPEST also provides re-planning for multi-goal traverses. This contrasts with single-goal re-planning in that model changes may affect more than one segment, and hence more than one ISE graph. TEMPEST must notify each affected ISE instance, but need only initiate re-planning from the latest affected segment. Note the analogy to modifications in a single ISE search - updates near the position of the rover tend to affect fewer segments than updates near the final goal, and hence are far cheaper to re-plan.
1. Note that some goal states and start states do not produce feasible solutions. Further note that each start state can only have one goal state (the optimal path is unique, barring ties), but that the optimal paths from several start states may all arrive at the same goal state.
18:00 00:00 06:00 12:00 18:00 00:00 06:00 12:00 18:00 00:00 06:00 12:00 18:00 00:00 06:00 12:00
00:00 06:00 12:00 00:00 06:00 12:00 18: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 18:00 00:00 18:00 00:00 06:00 12:00 18:00 06:00 12:00
Figure 4-8: Sequential Goal Planning. a) Final goal time interval definition; b) Previous segment goal time interval definitions; c) Segment goal states and start queries; d) Planning in last segment and generation of goal states for previous segment; e) Completion of planning; f) Optimal plan
MISSION-DIRECTED PATH PLANNING
An update procedure precedes re-planning. TEMPEST determines which segments are affected by updates that occur during plan execution. An update to the start state affects only the first remaining segment. Updates to models may affect one or more segments. Successfully completing a goal or abandoning a goal removes the corresponding segment from consideration in future planning. All segments affected by updates and all segments preceding the affected segments must be re-planned. The reason is that in a backwards search order, the solutions for earlier segments are based on solutions for later segments. Modifications to arc costs in a later segment in general alter the solutions for that segment, and hence the goals for the previous segment. So, a change in a later segment invalidates all earlier goal states. Once TEMPEST determines which segments are affected by updates, it deletes all but the last affected ISE instances, and calls INIT_SEGMENTS ( S, Γ, k ), where k is the index of the second-to-last affected segment, or last ( Γ ) – 1. Once the segments are re-initialized, a call to PLAN_SEQ_GOALS ( S, Γ ) initiates re-planning.
Each ISE instance repairs its search graph and yields plans, if feasible, for queries over the newly-defined start time intervals. The resulting plan, if any, is the optimum considering the new data.
4.3.6 Time-Bounded Sequential Goal Planning Often, legal goal completion is restricted to within fixed temporal bounds. For example, a communications opportunity may only be possible within a specific time range, or a scientific measurement might only be valuable during certain times of day. One approach to planning in these situations is to add constraints to the Constraint Set that define legal time ranges, associate those constraints with the goal actions, and perform sequential goal planning as described in the previous sections. Time constraints on goals can often drastically reduce the reachable state space. Forcing the ISE search to discover the reachable states both upstream and downstream of a time-limited goal is a wasteful activity in light of a priori knowledge.
Instead, the INIT_SEGMENTS ( S, Γ, k ) function can be modified to quickly propagate the effect of goal time constraints to earlier and later goals, thereby eliminating unreachable ranges of the goal time intervals that cannot contribute to feasible plans. This new function, INIT_TB_SEGMENTS ( S, Γ, k ), can substantially improve performance in finding the same optimal solutions as would be found using the earlier initialization algorithm. It is detailed in Table 4-9. A diagram of the new initialization procedure appears in Figure 4-9.
Figure 4-9a shows the same problem layout as in Figure 4-8a, but with the addition of goal time bounds for goal 2 and N-1, specified by the Mission Specification, that restrict the legal range of goal completion times. These goal bounds influence the initialization procedure in the following ways: they potentially further limit the closing time of later goal time intervals; they potentially further limit the closing times of earlier goal time intervals; and they directly limit the time interval for their associated goal.
As with INIT_SEGMENTS ( S, Γ, k ), the new initialization projects the reachable time range for the final goal using the maximum possible speed and shortest distance (L58, L59 and L72). It also projects an allowable time range for the final goal ( t max2 ) using the minimum allowable speed, the same distance, and the durations of goal actions (L65).
Figure 4-8a illustrates the result of these computations. However, the allowable time range may be further limited by the latest upstream mission-imposed goal time bounds. Consider that if an upstream goal is forced to finish earlier