«The Robotics Institute Carnegie Mellon University Pittsburgh, PA 15213 May 13, 2005 Submitted in partial fulfillment of the requirements for the ...»
The approaches also seek optimal energy paths in totally different ways. As explained in Section 3.1.7, both approaches must either limit plan length or promote shorter plans to avoid the problems of heuristic search for nonmonotonic costs. Approach 1 (4-D BESTDPARMS) seeks an optimal energy solution indirectly, since it uses a duration-based objective function as the mechanism for limiting plan duration. The objective function tracks the duration of candidate paths, and prevents paths that exceed a maximum duration. This prevents the search from lingering at states that provide negative costs. Under this limit, ISE uses state equivalence class pruning and state dominance to remove less desirable states. Within time-energy DPARMS classes, the better ( X, Y ) function favors states that have lower required energy. Within time DPARMS classes (but across energy DPARMS classes), the dominates ( X, Y ) function also favors states with lower required energy. The optimal solution in Approach 1 is one that falls below the given maximum path duration, and whose initial state is “best”.
MISSION-DIRECTED PATH PLANNING FOR PLANETARY ROVER EXPLORATION
Approach 2 (3-D BESTPCOST) contains energy directly in its objective function. The plan length cost in the composite objective function provides incentive to avoid lingering at regions of negative cost. The objective function applies a path length penalty K at every step in the path. This contrasts with Approach 1, which does not penalize extra steps as long as the plan duration is shorter than the given maximum. At any step in the Approach 2 search, the plan length cost K can potentially cancel out the resource cost ∆e. Consequently, there is no admissible heuristic to focus the search. Finally, in Approach 2, with energy removed from the DPARMS, no state dominance relationship exists. So, despite the advantage of having fewer dimensions to search, Approach 2 has fewer other mechanisms to help focus the search and to prune unnecessary states.
Approach 2 has some other disadvantages. Any arc transition must be a function of state (IPARMS and DPARMS) and action alone. Since the energy parameter e is not in the DPARMS, costs in Approach 2 cannot depend on energy.
In this particular domain, there are no costs that depend on energy, but in general this could be limiting. For example, it would be impossible to model a battery whose discharge rate is a function of its state of charge in the Approach 2 formulation.
More importantly, Approach 2 is incomplete (in the planning sense) with respect to energy. Reasoning about state, defined by position and time, does not consider energy. In the event that one branch of a search does not yield feasible paths, it cannot backtrack to different regions of the energy space, since it is not represented in the IPARMSDPARMS state. Paths that are eliminated due to high cost cannot be regenerated. In Approach 1, states that are dominated (and deleted) can be regenerated if it is discovered that the originally dominant states do not lead to a feasible solution. In practice, the incompleteness of Approach 2 does not interfere with finding paths in a wide range of situations.
Having introduced the example planning domain and the two candidate ISE approaches, the remaining sections assess the performance of ISE in response to various parameter changes. The tests to determine performance scaling with map size, DPARMS class resolution and branching factor (Sections 3.4.3 - 3.4.5) and to compare planning and re-planning (Section 3.4.6) all used Approach 2 (3-D BESTPCOST mode). Sections 3.4.7 and 3.4.8 compare the Approaches in terms of performance and solution quality. All tests were run on a Pentium 4, 2.99 GHz processor, with 1 GB of RAM.
3.4.3 Scaling With Map Size or Start-Goal Separation Map size refers to the number of IPARMS levels - the IPARMS dimensions of the 2-D spatial portion of the space.
The experiment varied the size of square maps ( x and y axes 50, 100, 150 and 200 cells each), with start and goal positions at opposite map corners. Tests measured the time required to solve the planning problem under increasingly large map sizes and start-goal separation, using Approach 2 described above. Twenty tests were run for each map
size, each on a different independently and pseudo-randomly-generated cost map. Figure 3-3 plots the ISE initial planning duration as a function of map size and confirms the intuition that a larger map size results in greater planning time. For each doubling of map dimension (quadrupling the number of IPARMS sets), the planning time increases roughly by a factor of 10. Computation should, in theory, be O ( N log N ) in the size of the search space.
However, this study does not examine increasing the IPARMS resolution but rather increasing the span of the IPARMS.
On the surface, doubling the span of IPARMS would be appear to quadruple the state space. However, the DPARMS time dimension is open ended; the DPARMS time dimension grows to contain all the states expanded in the search.
By expanding the size of the map, the distance between the start and goal increases, as does the duration of plans considered by a search. The size of the DPARMS time dimension is coupled to the distance between the start and goal position. An increase in the IPARMS dimensions actually increases the DPARMS span proportionally. The extra multiplicative effect seen in planning computation in Figure 3-3 may be explained by this coupling.
3.4.4 Scaling With Resolution An ISE user can vary the resolution for DPARMS equivalence classes. Recall that DPARMS equivalence classes group states that are considered sufficiently similar for resolution equivalence pruning (Section 3.2.2) and state dominance (Section 3.2.3) at each step in the search. They also define the resolution at which goal states can be specified, and the accuracy with which planning can match start state DPARMS parameters to actual initial conditions.
Tests in this study varied the resolution of the time variable DPARMS for various map sizes. As with the map size study, each combination of map size and resolution was tested 20 times, using 20 independently, randomly-generated cost maps. Figure 3-3 shows the performance benefit of decreasing resolution in the DPARMS. Given base time units, the study examined DPARMS equivalence class resolutions of 30, 60, 120 and 240 units per bin. Each curve in the plot corresponds to one of the resolutions. Each map size results in a different mean plan duration (the time the plan requires to travel from the start to the goal). Therefore, bin size represents a different fraction of the entire time DPARMS axis depending on the separation between goal and start. The number of 30 unit bins required to span the mean duration of plans was 27.7 for the 50-by-50 map, 62.8 for the 100-by-100 map, and 85.3 for the 150-by-150 map. The search will tend to populate approximately the number of time DPARMS bins required to span the solution. As shown in the plot, by halving the resolution at a given map size, the planning time decreases by a factor of between 2.4 and 2.7.
3.4.5 Scaling with Branching Factor The number of available transition arcs from each IPARMS state is application-specific. This number equates to a branching factor in the search graph that affects both performance and path cost. For Approach 2 (3-D BESTPCOST) planning, experiments recorded the time required to solve for a plan under two transition arc models - the original, eight-neighbor arc set, and a reduced, four-neighbor arc set in which arcs were restricted to horizontal and vertical motions. In both cases, the start and goal positions were on opposite corners of a square map. Twenty experiments were run for each combination of map size, DPARMS time resolution and branching factor.
In a standard state representation, with a fine resolution in the dependent variable, the branching factor determines the exponential rate of state proliferation. A larger branching factor would lead to exponentially more states. Figure 3-4 demonstrates the power of state resolution pruning, with the eight-connected planning shown in solid lines and the four-connected planning shown in dotted lines. Somewhat counter-intuitively, Figure 3-4 shows that the eight-connected state space requires nearly the same time as the four-connected case. For ISE, branching factor does not sub
stantially affect the time complexity of the search, because at each step, state resolution pruning discards states that are deemed inferior in each DPARMS state resolution bin. At each expansion step, the number of states in each IPARMS set remains roughly constant over the search, regardless of the branching factor. The number of states to expand depends more on the number of DPARMS equivalence bins are spanned by the search. ISE prevents the state explosion that would have occurred in a standard search, and yet represents dependent state variables at a fine resolution.
Figure 3-4: Time for Four and Eight Connected State Spaces for Approach 2 (BESTPCOST).
3.4.6 Re-Planning Performance ISE re-planning was designed to efficiently repair plans in response to changes in arc costs near the start state. A set of tests compared the time required to plan from scratch versus re-planning in response to changes on an existing cost map. Cost map updates were restricted to four modifications within 4 x 4 cell windows for various map sizes and DPARMS resolutions (30, 60, 120 and 240 time units). In each test, planning was first conducted on a base cost map.
The modifications were made to the costs on the original map, and re-planning repaired the initial ISE graph. The time required for the re-plan was compared against the time required to plan from scratch on the modified cost map.
MISSION-DIRECTED PATH PLANNING FOR PLANETARY ROVER EXPLORATION
Figure 3-5 compares the time to re-plan in comparison to planning from scratch, in response to cost updates near the start position. All cases show improvement over planning from scratch, especially at lower resolution. For larger map sizes, re-planning enables a factor of better than 100 speedup relative to initial planning. For smaller maps, modifications affect a greater portion of the entire map. The work of re-planning comes closer to replicating the work of initial planning, explaining the reduced benefits shown in the left side of the figure. Lower resolution in DPARMS axes reduces the influence of changes in the cost map on other DPARMS equivalence classes, thereby reducing the work to repair the graph.
Figure 3-5: Ratio of Re-Plan Time to Initial Plan Time for Approach 2 (3-D BESTPCOST). Re-planning shows one to two orders of magnitude improvement on speed over initial planning.
3.4.7 Scaling With Solution Approach Tests compared the time demands for the BESTDPARMS (4-D) mode and BESTPCOST (3-D) modes. Experiments demonstrate that varying the number of state parameter dimensions strongly affects the time demands of the algorithm. For these experiments, a set of 50 cost maps was generated for each combination of map size (50, 100 and 150 cells per IPARMS dimension) and DPARMS time resolution (60, 120 and 240 time units). First, the experiments ran Approach 2 on 50 maps to record the planning performance for 3-D search, as well as the durations of the resulting plan solutions for each cost map. The experiments then ran Approach 1 on the same 50 cost maps, using the Approach 2 solution plan duration as an upper bound on plan cost1.
INCREMENTAL SEARCHFigure 3-6 compares the time demands of Approach 1 (4-D BESTDPARMS) and Approach 2 (3-D BESTPCOST) for these experiments. The dotted lines correspond to Approach 1, and solid lines, to Approach 2. We immediately observe that the lower dimensionality of Approach 2 yields a sizeable time performance gain - for a given resolution and map size, Approach 2 is several times faster than Approach 1. This conforms to the notion that adding a dimension exponentially increases the number of states that a search must expand and represent in the search graph.
Figure 3-6: Comparison of Approach 1 and Approach 2 Time Performance
3.4.8 Qualitative Comparison of Approaches Figure 3-7 and Figure 3-8 illustrate the qualitative differences between Approach 1 (BESTDPARMS) and Approach 2 (BESTPCOST) through plots of path, energy and progress distance. The path plots show the physical route in XY space taken by the plan, starting at the start position in the upper right corner, to the goal in the lower left corner. In line with the description of ISE resource variables in Section 3.1.5, each energy plot shows the profile of minimum required energy in the battery in order to reach the goal, as a function of plan step. Progress distance is a measure of the direct progress made to toward the goal. It is calculated as the Euclidean distance between the start and goal,
1. Admittedly, this may have disadvantaged Approach 1 in terms of minimum energy solution, but provided a way to more evenly compare the two approaches. Section 3.4.8 suggests that Approach 1 is able to find shorter duration solutions than Approach 2 (making this a viable test strategy for performance tests), but that the shorter duration solutions are typically far inferior in terms of energy.
MISSION-DIRECTED PATH PLANNING FOR PLANETARY ROVER EXPLORATION
minus the Euclidean distance remaining to the goal from the current robot position (for a more detailed definition, consult Appendix 2). Under this definition, progress is only made when the radius between the robot and the goal is reduced. The progress plots show progress distance as a function of plan step.
Figure 3-7 compares the BESTPCOST mode (the left column of plots - Figure 3-7a, b, c) to the BESTDPARMS mode (the right column of plots - Figure 3-7d, e, f). In this experiment, the upper bound on plan duration for the BESTDPARMS approach was set to the duration of the BESTPCOST solution (5150 time units), as in the performance comparison of Section 3.4.7. This is the BESTDPARMS Case A.