«The Robotics Institute Carnegie Mellon University Pittsburgh, PA 15213 May 13, 2005 Submitted in partial fulfillment of the requirements for the ...»
Automated path planning was a central research topic of the project. Research into path planning for planetary exploration had to date focused on local navigation. Sun-synchronous navigation was by definition concerned with global issues as well as issues distinctly outside the realm of obstacle avoidance - terrain features that cast shadows and interrupt travel, the temporal effects of planetary rotation and maintaining sun synchrony, and energy management.
The field expedition conducted component and system-level tests on Devon Island in July of 2001. It culminated in two 24-hour, multi-kilometer long experiments designed to prove the concept of sun-synchronous navigation. In both experiments, the objective was to operate over long distances under solar power, with minimal human intervention, and to return to the start position 24 hours later with equal or higher battery state-of-charge than at the beginning. As the ambition was to prove a navigation strategy, no science or exploration activities were pursued by the rover.
The results for both experiments are described later in this chapter. Before detailing the approach for planning or the experimental results, the next sections briefly describe the operational environment on Devon Island, the Hyperion robot, and the software architecture used in the tests.
5.3.1 Devon Island Devon Island is extremely well-suited to testing sun-synchrony. The test site was at approximately 90 ° W longitude and 75 ° North latitude - above the Arctic Circle and hence appropriate for regional sun-synchrony. In the summer months, much of the terrain is uncovered by snow or ice, exposing terrain texture that is essential for local navigation using stereo vision. Also, it is largely devoid of plant life that would also otherwise complicate automated obstacle detection algorithms not designed for seeing brush, grass or trees. Though much of the terrain is smooth, there are significant small and large scale terrain obstacles to prohibit the ideal, circular sun-synchronous path. The Arctic sun provides about 850 W/m2 of power, sufficient power for locomotion, and yet little enough to provide a challenge for solar-powered rover designers.
5.3.2 Hyperion Rover Hyperion was designed and built under the Sun-Synchronous Navigation project. The rover is approximately 2.4 meters long and 2.0 meters wide , on the scale of the rover proposed for the Mars Science Laboratory mission slated for 2009. In its configuration in the Arctic, its mass was 156 kg, 18 kg lighter than the NASA Mars Exploration Rovers1. It is solar-powered, and employs a 3.5 m2 solar array of roughly 10% overall efficiency, and lead acid batteries that provide roughly two hours of locomotion power without recharging. For sensing, Hyperion made use of a stereo camera pair mounted on the front mast, and made minimal use of a scanning laser designed to provide an
1. Hyperion carried no science instruments, little communications electronics, no thermal control and no mechanical hardware to enable it to stow into a small volume and deploy for operations.
SUN-SYNCHRONOUS NAVIGATIONextra layer of security against obstacle collisions. For this project, stereo camera-based local obstacle detection software enabled the rover to drive at a maximum speed of 30 cm/s, or 1080 m/hr.
Hyperion’s solar array is fixed in orientation, pointing to the left side at an elevation angle of 22 ° to optimize solar incidence over the day. Fixing the solar array orientation greatly simplified the rover mechanical design. Enabling a large solar panel to rotate but keeping it stiff under driving and wind-induced loads requires a very substantial gimbal mechanism. Also, the rover design using a gimballed array must keep the panel’s swept volume clear of protruding components. Interestingly, though, the fixed solar array places a much heavier burden on automated planning energy collection becomes highly coupled to driving direction.
5.3.3 Software Architecture One of the objectives of the rover design was to develop software that would enable a high degree of autonomy.
Given the rapid pace of development for Hyperion, it was recognized early that the system was not likely to be fully autonomous in the first year. It was also understood that low and high-level testing benefits from an architecture that permits an operator to select the degree of control autonomy based on the task at hand. Hyperion’s software architecture was designed to provide “sliding autonomy”, from manual control of individual motors on one end of a spectrum, to fully autonomous operations on the other.
TEMPEST was Hyperion’s off-board Mission Planner (MP). This early version of TEMPEST was substantially slower than the current version, and did not yet incorporate ISE re-planning. Because it could not yet respond to state or model updates during execution, there was no reason to integrate it into the online software. TEMPEST was run off-line to produce plans that were used for an entire 24-hour experiment. Despite the off-line distinction, TEMPEST provided an autonomous capability to the human operators.
An Operator Interface (OI) utilized a graphical user interface and a direct communications link to send commands and receive telemetry from the robot. Noticeably absent from the software architecture is an executive process to control and monitor the progress of plans. Human operators assumed this role via the OI. Plan Drive target waypoints were sent individually and manually to the rover at the times specified in the plan.
Between periodic manual interventions to send plan actions, Hyperion performed local navigation autonomously.
The Local Navigator module used stereo vision to detect obstacles in its path, and called upon the D* algorithm to find optimal paths to the waypoints designated in the TEMPEST plans . Local Navigator goals were goal regions rather than points. TEMPEST, as a global planner operating on coarse maps, cannot precisely designate goals.
Therefore, it is inappropriate to treat goals as precise when passed to the Local Navigator. Furthermore, point goals are likely to be placed in the midst of intraversible terrain, preventing the rover from achieving them. Local Navigator goal regions were rectangular regions whose long axis was perpendicular to vector between the rover and the goal point, 30 meters wide and 10 meters deep. In practice this led to a behavior in goal seeking that maintained better solar array sun pointing if local obstacles diverted the rover from its original course.
5.3.4 Planning Problem The main objective of system-level experiments was to demonstrate 24-hour solar-powered operations over as large a circuit as possible, and to complete the circuit with the same or more battery charge than the at the start. Rather than fully selecting the route and distance for the sun-synchronous circuits, TEMPEST addressed a sub-problem. Visual inspection of the terrain on Devon Island revealed that there were many terrain hazards smaller in scale than could be represented by the elevation map (25 meters spatial resolution), particularly steep-sided riverbeds. Furthermore, Hyperion’s local navigation system was not sufficiently capable of autonomously detecting and avoiding these same unrepresented hazards. Wisely, the team elected to perform the system-level experiments by pre-surveying a benign sequence of via points, using a handheld GPS. Adjacent points were separated by varying distances, but typically by hundreds of meters.
TEMPEST was responsible for selecting the specific route between the sequential via points, separated by roughly 250 meters on average. More interestingly, because the route was partially selected by humans, the planning problem became principally one of selecting the route timing to optimize battery energy management.
5.4 Planning Approach Sun-synchronous planning was performed using TEMPEST, albeit a very early version. Because of the early stage of development, many planning details were different than described in Chapter 4. Despite the differences, the terminology and notions presented in Chapter 4 are sufficient to describe a majority of the approach. Table 5-1 summarizes the TEMPEST parameters used for the field experiment.
Planning closely mimicked the sequential goal planning problem described in Chapter 4, with each pre-designated via point acting as a Via Point goal (see Chapter 4, Section 4.2.4). TEMPEST used a four-dimensional search space under the ISE BESTDPARMS mode (see Chapter 3) to find the path requiring the least initial energy, subject to an upper bound on mission duration. The objective function, used to compute path costs relative to the upper bound, minimized total plan duration. Given the problem of sun-synchrony, TEMPEST constrained plans to be under 24 hours. Under that upper bound, TEMPEST found the plan with the lowest battery energy. Finally, because the underlying objective was to achieve lowest energy paths, the ISE dominance mechanism (see section 3.2.3) was used to remove energy-dominated states from consideration.
However, TEMPEST deviated significantly from the algorithm and methods described Chapter 4. As mentioned earlier, a principal objective of planning for sun-synchrony is to determine the optimal start time. This conflicts with the method in Chapter 4 in which the start time is presumed to be known. To determine the optimal start time, a user designated a 24-hour time interval representing the allowable range of start times. Segment initialization followed the general approach listed in the INIT_SEGMENTS ( S, Γ, k ) function of Chapter 4, but with an important distinction.
Rather than projecting the latest allowable time to the final goal, then using the fastest possible speed to set the latest allowable times for earlier segments, TEMPEST imposed the slowest allowable time on all goals in the sequence.
Referring to Figure 4-8, rather than imposing time interval bounds as shown in frame b), this early version of TEMPEST imposed the limits shown by the dashed lines in frame a), a much more conservative approach. However, coupled with the 24-hour start time interval, TEMPEST was still very free to pursue a wide range of time profiles.
In planning, rather than using a single query for the first plan segment, TEMPEST performed start queries over the entire start interval as it would for an intermediate segment. Rather than use the objective function to distinguish between plan solution over the start window, TEMPEST used a series of heuristics to find the best path. We define
the set of candidate plans derived from repeated start queries over the 24-hour start time interval to be:
where each plan is defined by waypoints at listed in Chapter 4, Equations 4-1 and 4-2. TEMPEST applied three heuristics to select the optimal plan from the list of candidates:
Get Minimum Initial Energy Plans: Given the definition of energy ei at each waypoint, a low initial energy corresponds to the least initial battery charge required to achieve the goal state:
SUN-SYNCHRONOUS NAVIGATIONGet Minimum Peak Energy Plans: The peak energy in a plan represents the greatest demand on the battery over the
traverse. Finding the minimum peak energy minimizes the peak demand on battery reserves:
Get Earliest Start Time Plan: Given a list of available start times, in many cases it is operationally sound to select
the first opportunity path, leaving fallback options in the event of failure:
Note that not all start times may be feasible, and that there may be one or more ranges of feasible start times. These
are determined automatically by TEMPEST. The heuristics were applied sequentially as a composite selection criterion to produce the optimal solution:
In words, the composite criterion first selects on the basis of minimum initial energy requirement. From those paths, it selects on minimum peak requirement on energy over the path. From those plans remaining, it selects the one that departs the earliest.
5.5 Experiment 1 Results Table 5-2 summarizes the results of Experiment 1 mission planning and execution. Experiment 1 was the first system level sun-synchronous navigation trial of the project. The execution of the planned route was highly successful, proving the feasibility of the strategy. The following subsections analyze the TEMPEST plan generated for the experiment, and provide the results from its successful execution.
5.5.1 Planning Though the rover was capable of driving at 1080 m/hour, the first experiment was designed with a conservative target distance. The planned total distance was 5.6 km, to be covered in just under 24 hours, for an average speed of 236 m/ hour, or 22% of the maximum.
The field team pre-designated 19 Via Point goals to guide Hyperion away from hazardous mid-scale terrain hazards.
The separation between goals was on average 269 meters. Figure 5-5 shows the Via Point goals and the selected route superimposed on a contour map of the terrain. The route progresses clockwise through the Via Points, starting just above the bottom right extremity of the circuit.
The Via Point goals were selected to guide the robot away from hazards that might be difficult for the robot to detect.
The positioning of the Via Points indicates how hazardous terrain prevented an ideal circular path. Streambeds ran along the outside of both diagonal legs of the route, and a rocky promontory rose just West of the northwest end of the route. The pre-designated Via Points steered clear of these terrain hazards, but forced an elongated shape for the path circuit - a major deviation from the ideal circle. Long, straight paths prevent a fixed-orientation solar array from tracking the sun. The challenge for TEMPEST was to select the route and timing to maintain battery energy despite inevitable solar array mispointing.