«The Robotics Institute Carnegie Mellon University Pittsburgh, PA 15213 May 13, 2005 Submitted in partial fulfillment of the requirements for the ...»
Constraints for drive actions are optional. However, it may be useful to constrain driving to below a maximum slope, to avoid hazardous terrain, or to times and headings that keep the sun disk out of the field of view of the navigation cameras.
1. Note that for omni-directional vehicles, the drive action must define an explicit function for vehicle orientation.
Solar Charge - An action to enable stationary solar-powered battery charging. Being a stationary action, the solar charge action must target a duration or a target energy. At minimum, the action must call on two rover components a solar array to collect energy, and a battery to store incoming energy. The vehicle heading for a solar charge can be defined to optimize the incoming solar energy over the duration, as a function of terrain slope, absolute time, and the orientation of the solar array with respect to the rover frame.
As for drive actions, constraints for solar charge actions are optional, but can be added to limit their use to certain state conditions (e.g. only when the sun is visible).
Hibernate - An action to enable stationary operations at low power levels. This action is actually a variation of the Solar Charge action, but uses different Rover Model components (e.g. low power electronics), has potentially a different duration target, and employs a different set of constraints (e.g. Nighttime).
Science Data Collection - An action to model the activity of science data collection within a single position grid cell.
Since the action remains within a single position cell, Science Data Collection is also a variation on the Solar Charge action. It uses Rover Model components to approximate the power of various instruments, overhead electronics power, and perhaps power for limited locomotion about the site. The activated constraints for this action type would have to match the requirements of the particular measurements being employed. One could envision designing constraints to impose lighting conditions, certain geometric conditions, or even thermal conditions at the site.
Via Point - A placeholder action, inserted at a goal position, that has no effect on state, but satisfies the goal of reaching a particular position. The following section explains why this type of action can be useful.
4.2.5 Mission Specification Set The Mission Specification encodes the basic objectives for the planning run - the starting conditions for the plan and a list of goals to be achieved.
MISSION-DIRECTED PATH PLANNINGThe rover start specification defines the start position and time in World Model coordinates, and the current resource levels, defined by the Rover Model, that cannot be exceeded by the starting resource levels of any feasible path.
The goal specification is a fully-ordered goal sequence, each defining, at minimum, the position of the goal and the goal action - an action defined in the Action Set that must be executed at the goal position to achieve the goal. Often, a mission will specify science or exploration activities at specific locations, or resting points for overnight periods.
The previous section described Science Data Collection and Hibernation actions for these times. In other cases, a goal will purely be a via point en route to some other location. In this case, Via Point action can be used. As with any action, goal actions can constrain the states over which the actions are legal, via the Constraint Set. Optionally, goals can independently specify allowable termination time bounds or minimum resource levels.
4.2.6 Incremental Search Engine The five TEMPEST models collectively define the ISE planning domain - the state space (IPARMS and DPARMS), the arc parameters (APARMS) and arc transition functions, the objective and heuristic functions, the start and goals and other domain-specific functions (see Figure 4-4). For greater detail on ISE, please refer to Chapter 3.
MISSION-DIRECTED PATH PLANNING FOR PLANETARY ROVER EXPLORATION
The ISE state space derives primarily from the states variables defined by the World Model and Rover Model. At minimum, the World Model contributes two position dimensions X and Y, and an absolute time dimension T. The position variables X and Y form the ISE IPARMS. The time dimension T is the only required DPARMS parameter.
TEMPEST time units are seconds, but time equivalence class partitions are application-specific and typically far more coarse, for example 10-30 minutes.
The Rover Model contributes metric resource parameters. Resource parameters can either be DPARMS and limited under local constraints or, in circumstances where the resource value relates directly to path cost, they can be represented as global constraint parameters within the objective function (see Sections 3.1.3-3.1.5 for more detail). The resource of choice in this thesis is rover battery energy; however, TEMPEST could be re-configured to plan for other resources, like component life, margin on thermal thresholds, or onboard memory.
The TEMPEST Action Set and Constraint Set collectively define arc parameters (APARMS) and arc transition functions β and Φ. Actions in the Action Set define the change in state given an initial or final state. The Constraint Set determines the conditions under which actions are legal or illegal, enabling the arc transition functions to reject violating arcs. In general, ISE uses APARMS to store all parameters that influence arc transitions. TEMPEST uses APARMS exclusively to encode parameters that are expected to change during plan execution, and hence prompt replanning. The static parameters are stored in a data structure universally accessible by the state transition functions.
The Mission Specification defines the goal states and actions and the start state for the ISE search. Recall that ISE plans paths to one or more goal states. As will be shown in later sections, TEMPEST assigns multiple, time-distributed goal states to goals that can be feasibly completed over more than one time equivalence class. During search, each time-distributed goal state is treated independently and can be expanded to yield new states. The start state specification defines the termination conditions for the search - encoded in the ISE function feasible ( X ).
The path cost functions h ( X ) and g ( X, Y ) depend indirectly on the Mission Specification. The Mission Specification defines which cost is important to the planning problem. In the purest sense of mission-directed planning, as defined in the Introduction, cost is in terms of the reward earned through achieving mission goals. However, in many circumstances other costs based on resource parameters or other variables have direct mission relevance. This thesis does not address reward-based planning. That said, TEMPEST would not require significant modification to couch all goals and path costs in terms of reward.
4.3 Algorithm This section describes how TEMPEST uses ISE to solve for plans. The basic unit of TEMPEST planning is the path segment (or segment for short) - the interval between a pair of goal positions for which a plan must be solved. For
MISSION-DIRECTED PATH PLANNINGeach segment, TEMPEST creates a separate instantiation of ISE that is dedicated to solving that sub-problem. Each ISE instance must be initialized with goal and start information. Once initialized, TEMPEST uses the ISE instances to generate paths between goals. Sections 4.3.3 and 4.3.3 describe the initialization and planning algorithms for a single goal. Sections 4.3.4 through 4.3.6 build on this base case to handle multiple goals and goals with completion time bounds.
4.3.1 Definitions Table 4-4 lists a number of other informal definitions for symbols and functions that appear later in the algorithm listings., Table 4-4: Informal Definitions of Symbols and Functions Used in the TEMPEST Algorithm Description
4.3.2 Single-Goal Planning In TEMPEST single-goal planning problem (Figure 4-5), the basic objective is to solve for an optimal plan that travels from a start S to a goal G, and executes a goal action before terminating. TEMPEST initializes a single segment planner in a function INIT_SEGMENT ( S, G ). The algorithm for INIT_SEGMENT ( S, G ) appears in Table 4-5.
Before describing single-goal planning, we introduce Figure 4-6, which has six frames depicting TEMPEST singlegoal segment initialization and planning. Each frame is a plot of time (horizontal) versus progress fraction F P (vertical). The origin of each plot represents the start state, with a time just before the start time ts, and a distance of zero.
MISSION-DIRECTED PATH PLANNINGOn the distance axis, the high point represents the Euclidean distance to the goal. The slope of a trace in a plot indicates the speed of progress towards the goal. The time axis may span one or more days, as denoted by the light and shaded regions corresponding to “noon” and “midnight”. The following paragraphs refer to these plot diagrams to illustrate the TEMPEST algorithm.
Function INIT_SEGMENT ( S, G ) begins at Table 4-5, line L1 by defining the allowable plan start time interval T s, which is exactly ∆T res in duration and centered on the start time. This is depicted graphically in Figure 4-6a) by the short, thick line segment surrounding the start time. Line L2 computes the minimum distance R between the start and goal. Lines L3 and L4 compute the minimum possible and maximum allowable goal completion times for the segment. The maximum allowable time accounts for the worst-case traverse duration and the goal action duration, starting from the close of the start time interval. In contrast, the minimum possible time starts at the opening of the start time interval, but neglects the goal action duration. This allows for the possibility that the goal action is abandoned during execution. Figure 4-6a) depicts the maximum speed line (more steep) and minimum speed line (less steep) that define these times - dashed lines that ascend from the limits of the start time interval.
These times are endpoints for two time intervals that are used repeatedly in TEMPEST planning - the reachable time bounds T reach and the allowable time bounds Tallow (line L5). The reachable time bound opens at the earliest possible goal completion time and extends to infinity. It represents physically possible outcomes. The allowable time bound has an unlimited lower bound, but sets an upper limit on times considered for the search. The goal completion time interval T g is computed as the intersection of the reachable and allowable completion times (line L6). In Figure 4-6a), the thick, horizontal line segment at the goal distance shows the range of allowable goal completion times.
Note that the goal time interval extends beyond the maximum traverse time to account for the goal action duration.
It is important to note that although a minimum average rover speed is used to limit the range of allowable goal completion times, TEMPEST does not further limit the average speed of paths. Figure 4-6b) shows the feasible distance/ time space as bounded by two lines - the original line of maximum rover speed, defining the earliest reachable approach; and a second, new line extending downward from the latest possible goal position arrival time (at the same speed), defining the latest allowable approach to the goal.
The final step in initialization is to create the ISE instance for the path search. Once initialization is complete, the segment is ready for planning. The function PLAN_SINGLE_GOAL ( S, G ), as defined informally in Table 4-6, begins by defining goals at the goal position but evenly spread over the goal completion time interval, separated by times equal to the DPARMS time equivalence class resolution ∆Tres (see lines L10-L13, and Figure 4-6c, where the distributed goals are represented as a string of cells spread across the goal completion time interval). The time interval between goals reflects the DPARMS resolution limit in ISE. Recall that during a search, the ISE resolution pruning mechanism eliminates redundant states according to the objective function and the better ( X, Y ) function (see Chapter 3.). In general, two goal states in the same DPARMS class would be found to be redundant at the outset. Therefore, goals cannot usefully be spaced more closely than the DPARMS equivalence class resolution.
Once ISE is supplied with goal states, PLAN_SINGLE_GOAL ( S, G ) makes a single query to ISE using the function GET_PATH_COST ( S ) with the start state and start time interval (Table 4-6, lines L15-L16). This query calls on either the BESTPCOST or BESTDPARMS modes to find the optimal path from the start to one of the time-distributed goals. In Figure 4-6, frames d) through f) depict the search. Initially, the goal states are the only states in the ISE