«The Robotics Institute Carnegie Mellon University Pittsburgh, PA 15213 May 13, 2005 Submitted in partial fulfillment of the requirements for the ...»
ditions while operating; a Local Navigator that used stereo camera data to locate and avoid hazardous local terrain while seeking a goal; and TEMPEST which took the sole responsibility of mission planning. A rudimentary mission executive (ME) coordinated mission-related data passing between these modules, and received and distributed Mission Specifications from the Operator Interface (OI). Figure 6-2 illustrates the basic set of inter-module communications relating to mission-level path planning and execution. Designed as a placeholder for future, more sophisticated
MISSION-DIRECTED PATH PLANNING FOR PLANETARY ROVER EXPLORATION
executive modules, the ME adopted a simple, hierarchical state machine architecture. It enacted a collection of monitors to keep track of system state while planning or executing plans: the Plan Request Monitor, Plan Execution Monitor, Drive Monitor, and Charge Monitor.
6.4.4 Sequence of Operations The mission focus in LITA 2003 was navigation to a single distant goal. Mission Specifications, consisting of the goal position and required arrival battery energy level were sent via the OI. Upon receiving a Mission Specification, the ME determined the current robot position and time state, and requested a plan beginning at that state and terminating at the specified goal state. TEMPEST found and returned an optimal plan to the ME. For each action in the plan, the ME triggered one of two Action Monitors.
The Drive Monitor computed parameters for a 10 meter by 30 meter goal region surrounding the next position waypoint (see Figure 6-3), and sent them to the Local Navigator for execution. Using the goal region as its global goal, the Local Navigator pursued this region while avoiding obstacles it detected. Once Hyperion was within the region, the Local Navigator signaled its arrival, terminating the Action Monitor. The Charge Monitor stopped the rover and waited for the assigned Charge duration before terminating.
Figure 6-3: Plans and executed paths. TEMPEST plans assigned the location of periodic goal regions. Goal regions gave the Local Navigator flexibility in selecting the specific path between waypoints.
During plan execution, at the scheduled arrival time for each plan waypoint, the HM performed a one-time check to confirm the robot was on time. If the rover was more than a fixed distance from the waypoint at the scheduled arrival time, the HM notified the ME that the waypoint was “missed”. Receiving this notification, the ME terminated the
ROBOTIC ASTROBIOLOGYexecution of the current plan, and commanded TEMPEST to re-plan from the current rover state to the goal in the original Mission Specification.
6.4.5 Planning Approach Table 6-1 summarizes the planning parameters used in the LITA 2003 experiments. Notably, TEMPEST was re-configured from Arctic field experiments to take advantage of the composite objective function approach (see Section 3.1.6 and Approach 2 in Section3.4.2). By representing the battery energy state variable within the objective function, the energy dimension used in Arctic experiments could be removed from the ISE DPARMS. At each state transition in the ISE search, a path would incur the corresponding positive or negative energy cost, plus the path length cost increment, defined as the absolute value of the greatest charge (negative cost) possible over the entire search space. The result was a dramatic improvement in planning speed that enabled TEMPEST to perform initial planning repeatedly throughout a day’s experiments, if necessary. Recall, however, that in removing energy from the state space, ISE was no longer complete - solutions deleted from consideration early in the search on the basis of cost could not be resurrected if ISE failed to find a feasible solution downstream. In practice, this did not prevent TEMPEST from finding solutions.
Perhaps more important than the dimensionality reduction was incorporating ISE state update re-planning into TEMPEST. In the Arctic, TEMPEST generated a single plan for a 24-hour traverse. If operational delays prevented staying on schedule, as occurred in Experiment 2, the robot relied on human teleoperation to recover. A prime ambition for the LITA project was to obviate the need for periodic teleoperation. Re-planning in response to evolving rover state created a “safety net” in case of schedule deviations, a likely occurrence during robot experiments. Another objective from prior work was to demonstrate a richer representation of rover, actions and constraints.
6.5 Results 2003 Over April 17 through 20 and April 24 through 26, TEMPEST generated 27 plans and 83 re-plans. These experiments indicate qualitatively and quantitatively that TEMPEST planning sought longer than minimum length routes to avoid costly regions of the state space. Other analysis indicates that TEMPEST produced plans that were mildly unstable with respect to specific route, but exhibited clear arrival time stability. Most notably, TEMPEST enabled one traverse of over 1 kilometer, and many traverses of several hundred meters.
6.5.1 Path Length TEMPEST’s grid representation of position state interferes with the ability to produce shortest-distance paths, as described in Section 4.5. Recall that for a given ratio of ∆x to ∆y, the minimum increase in path length above the Euclidean distance is given by the representation factor f R. Figure 6-4 examines the ratio of plan distance to Euclidean map distance for plans generated on April 20 through April 26 of the 2003 experiment to determine whether the grid representation was dominant in extending path length beyond the minimum. The horizontal axis spans the range of the absolute value of ∆x/∆y, representing an East-West heading on the left, a Northeast-Southwest or NorthwestSoutheast (diagonal) heading at the center, and a North-South heading on the right. The vertical axis spans the range of the plan distance D plan divided by the Euclidean or map distance D map. From Section 4.5, recall that this ratio is equal to the multiplication of the representation factor fR and the avoidance factor f A. The curve at the bottom of the
ROBOTIC ASTROBIOLOGYplot shows the representation factor for the range of ratios of ∆x and ∆y. Therefore, the ratio of the point value to the curve value beneath it is the avoidance factor fA.
Figure 6-4: Avoidance Factor and Representation Factor for LITA 2003: The points suggest that avoidance was often dominant in determining path length.
Observe that all the plans fall barely to the right of center, confirming that routes traveled principally in a North-South direction, but with a slant from Northwest to Southeast. More interestingly, though several points fall very close to the minimum curve, most paths are much longer. This indicates a large avoidance factor and suggests that the eightconnected representation was not the principal contributor to path length extension for most of the plans. For the paths not near the minimum eight-connected curve, obstacle avoidance, energy cost minimization and constraint satisfaction contributed to path length extension, often significantly.
6.5.2 Large-Scale Terrain Avoidance TEMPEST demonstrated large-scale hazard avoidance on several occasions. The planning for April 25 suggests subtlety. Figure 6-5a shows the sequence of plans and executed paths for the day. At first glance, the initial northeast heading taken by the plans is mysterious. Why did the planner force this detour rather than a more direct route to the goal? The answer appears to lie in slope avoidance. By plotting the same path over a contour map of the magnitude
of-gradient (slope) field (see Figure 6-6b), we observe that the path avoids steeper slopes to its left, and then turns toward the goal at a break in this higher slope region.
Figure 6-5: Plan and re-plan routes from April 25 on an elevation contour map, and a close-up with contours of constant slope. The initial plans seem to have located a break in steeper slopes.
ROBOTIC ASTROBIOLOGYcoupling between the direction of travel and solar power in Hyperion’s Arctic configuration, allowing the rover much more freedom of motion and schedule with little or no penalty. Furthermore, the solar flux in the Atacama was sufficiently high in April, during daylight, to sustain the highest-power operations indefinitely. Shadows only occurred very near sunset, so only intersected paths when operations were coming to a close. The planning models verify this TEMPEST executed plans never included Charge or Hibernation actions. Finally, due to an undiscovered software bug, the telemetry logs did not log TEMPEST plan messages. Alternate records of plans, used to reconstruct plans from April 20 and later, did not include the battery energy variable of the plans. Unfortunately, this lack of data prevented determining when and where planning predicted energy-rich and energy-poor conditions.
6.5.4 Plan Monitoring and Re-Planning A primary goal of the field experiment was to test re-planning in the context of rover operations and plan stability. As mentioned earlier, TEMPEST called upon state update re-planning. The Health Monitor provided simple plan execution monitoring, and was the sole trigger of re-planning.
Figure 6-7: Rover Average Speed vs. Re-Plan Frequency. Operational delays often caused the HM to trigger re-planning. The solid lines in a) show average rover speed over a Drive action. The dashed lines are the average rover speed over the particular plan or re-plan execution. Speeds below the TEMPEST rover model speed (plans 2, 5, 7) caused re-plan events, shown in b). Blank regions in plot b) are human-designated suspensions of operation to enact manual fault recovery.
As position state estimation was quite accurate, the major cause of re-plan requests was deviation of average rover speed from the rover model, shown in Figure 6-7 for plans executed on April 25. The figure illustrates the connection
between rover speed and HM re-planning requests1. Figure 6-7a plots speed as a function of time. The TEMPEST rover model speed is the constant, thin dashed line. The series of numbered brackets indicates the time spans for the execution of successive plans and re-plans. The solid traces for each plan show the average rover speed over the execution of each Drive action. Note that on several occasions, Hyperion stopped for long periods of time (end of plans 4, 5, 6, 8). These were not due to Charge actions, but reflect periods where the rover encountered irrecoverable faults and could not continue executing the plan. The dash-dot traces for each plan show the average rover speed over the entire plan or re-plan execution. Note that for plans 3 and 9, the average rover speed over a plan exceeds the speed assumed by the TEMPEST model, and in plans 2, 5, 6, 7 and 8, coinciding with faults that stopped the rover, the speed is much lower than predicted by the model.
Meanwhile, Figure 6-7b shows the timing of important plan execution events, denoted by vertical lines. The long solid lines correspond to TEMPEST initial planning runs, and the long dashed lines are re-plan events. The shorter, thinner lines correspond to when the Mission Executive sent waypoints to the Local Navigator. TEMPEST was manually terminated several times during the day after long operational delays (after plans 3, 4, 6 and 8). However, it is clear from plans 2, 5 and 7 that re-plans correlate well with periods of slow average driving speeds. The figure also underlines a logic error in the Health Monitor that overlooked faster-than-expected rover speed for re-planning. In no case does faster-than-predicted rover speed trigger a re-plan (see plans 3 and 9).
6.5.5 Plan Stability Plan stability is determined by the degree to which plans vary in response to evolving initial rover state during a mission execution. Stable planning yields few changes in route or schedule with minor deviations from the current plan, and yields predictable changes for greater deviations. Unstable planning results in erratic behavior. A planner that exhibits stability enables mission operators to better predict the range of possible plan solutions without a exhaustive check. Whether planning is stable would also influence whether and how a planner might be integrated with other planners as a component within a greater autonomy software architecture. For example, if re-plans typically entail a total re-specification of the mission timeline, it might not be computationally practical to plan beyond the first action.
Stable planning might permit a longer projection.
1. The gaps in data indicate time spans where autonomy was disabled by human operators to enact manual recovery actions from software or operational faults.