|
|
 |
 |
 | | | | |
 |
|||
 |
||||||
          |
 |
 |
||||
|
Action-Based Discretization for AI SearchSphere Navigation Search ProblemSince SADAT search algorithms will generally only be able to approximate optimal solutions, it is helpful to test them on problems with known optimal solutions. Richard Korf proposed the problem of navigation between two points on the surface of a sphere as a simple benchmark with a known optimal solution. Our version of the problem is given here. The shortest path between two points on a sphere is along the great-circle path. Consider the circle formed by the intersection of a sphere and a plane through two points on the surface of the sphere and the center of the sphere. The great-circle path between the two points is the shorter part of this circle between the two points. The great-circle distance is the length of this path. Our state space is the set of all positions and headings on the surface of a unit sphere along with all nonnegative time durations for travel. Essentially, we encode path cost (i.e. time) in the state in order to define the goal states. The initial state is arbitrarily chosen to have position (1,0,0) and velocity (0,1,0) in spherical coordinates, with no time elapsed initially. The action ai, 0<i<7 takes a state and time duration, and returns a new state and the same time duration (i.e. cost = time). The new state is the result of changing the heading i*p/4 radians and traveling with unit velocity at that heading on the surface of the unit sphere. If the position reaches a goal state, the system stops evolving (and incurring cost). The set of goal states includes all states that are both (1) within Îd great-circle distance from a given position pg, and (2) within ,t time units of the optimal duration to reach such positions. Put differently, the first requirement defines the size and location of the destination, and the second requirement defines how directly the destination must be reached. Position pg is chosen at random from all possible positions on the unit sphere with all positions being equally probable. If d is the great-circle distance between (1,0,0) and pg, then the optimal time to reach a goal position at unit velocity is d - Îd. Then the solution cost upper bound is d - Îd + Ît. Experimental ResultsIn these experiments, we vary only the initial time delay Dt between search states and observe the performance of the algorithms we have described. For Î-IDA* and Î-RBFS, the initial Dt is the only Dt for search. The iterative-refinement algorithms search using the harmonic refinement sequence Dt, Dt/2, Dt/3, …, and are limited to 1000 refinement iterations. Experimental results for success rates of search are summarized in Figure 3. Each point represents 500 trials over a fixed, random set of sphere navigation problems with Îd = .0001 and ,t computed as 10 percent of the optimal time. Thus, the target size for each problem is the same, but the varying requirement for solution quality means that different delays will be appropriate for different search problems. Search was terminated after 10 seconds, so the success rate is the fraction of time a solution was found within this allotted time. In this empirical study, means and 90 percent confidence intervals for the means were computed with 10000 bootstrap resamples. Let us first compare the performance of iterative-refinement (IR) Î-RBFS and Î-RBFS. To the left of the graph, where the initial Dt0 is small, there is no difference between the two algorithms. This region of the graph indicates conditions under which a solution is found within 10 seconds on the first iteration or not at all. There is no iterative-refinement in this region; the time complexity of the first iteration leaves no time for another. At about Dt0 = .1, we observe that IR Î-RBFS begins to have a significantly greater success rate than Î-RBFS. At this point, the time complexity of search allows for multiple iterations, and thus we begin to see the benefits of iterative-refinement.
Where the success rate of IR Î-RBFS begins to fall, the distribution of first 1000 Dt's begins to fall outside of the region where solutions can be found. With our refinement limit of 1000, the last iteration uses a minimal Dt = Dt0/1000. The highest Dt0 trials fail not because time runs out. Rather, the iteration limit is reached. However, even with a greater refinement limit, we would eventually reach a Dt0 where the iterative search cost incurred on the way to the good Dt range would exceed 10 seconds. Comparing IR Î-RBFS with IR DFS, we first note that there is little difference between the two for large Dt0. For 3.16<Dt0<100, the two algorithms are almost always able to perform complete searches of the same search contours through all iterations up to the first iteration with a solution path. The largest statistical difference occurs at Dt0 = 316 where IR DFS's success rate is 4.4 percent higher. We note that our implementation of IR DFS has a faster node-expansion rate, and that Î-RBFS's Î-admissibility necessitates significant node re-expansion. For these Dt0's, the use of IR DFS trades off ,-optimality for speed and a slightly higher success rate. For low-to-mid-range Dt0 values, however, we begin to see the efficiency of Î-RBFS over DFS with node ordering as the first iteration with a solution path presents a more computationally costly search. Since the target destination is so small, the route that actually leads through the target destination is not necessarily the most direct route. Without a perfect heuristic where complex search is necessary, Î-RBFS shows its strength relative to DFS. Rarely will problems be so unconstrained and offer such an easy heuristic as this benchmark problem, so IR Î-RBFS will be generally be better suited for all but the simplest search problems. Comparing IR Î-RBFS with Î-IDA*, we note that Î-IDA* performs relatively poorly over all Dt0. What is particularly interesting is the performance of Î-IDA* over the range where IR Î-RBFS behaves as Î-RBFS, i.e. where no iterative-refinement takes place. Here we have empirical confirmation of the significant efficiency of Î-RBFS over Î-IDA*. In summary, iterative-refinement algorithms are statistically the same as or superior the other searches over the range of Dt0 values tested. IR Î-RBFS offers the greatest average success rate across all Dt0. With respect to Î-RBFS, IR Î-RBFS offers significantly better performance for Dt0 spanning more than four orders of magnitude. These findings are in agreement with previous empirical studies concerning a submarine detection avoidance problem [Neller, 2000]. This is significant for search problems where reasonable values for Dt are unknown. This is also significant for search problems where reasonable values for Dt are known and one wishes to find a solution more quickly and reliably. This performance comes at a reasonable price for many applications. Lack of knowledge of a good time discretization is compensated for by knowledge of a suitable solution cost upper bound. Dynamic Action Parameter DiscretizationHaving looked at some methods for performing dynamic action timing discretization, we will now focus on dynamic action parameter discretization. Now we will assume that the action timing discretization, i.e. when actions are taken, is already given. From the perspective of the search algorithm, the action timing discretization is static (cannot be varied by the algorithm). However, the action parameter discretization is dynamic (can be varied by the algorithm). For this reason, we will call such searches "DASAT searches" as they have Dynamic Action and Static Action Timing discretization. DASAT are different than classical AI searches in only one respect. There
are infinite ranges of action parameters. In the context of navigation,
the choice of a heading change can come from an infinite continuum of
angle choices 0 - 2 A DASAT search problem is made up of four parts:
Given this generalization, the state space is generally infinite, and the optimal path can generally only be approximated through a sampling of possible paths through the state space. When both action parameter and action timing discretizations are dynamic, we call such searches “DADAT” searches. The following experiments were performed with DADAT searches using a form of iterative-refinement depth-first search and three different forms of action parameter discretization.
|
||||||||||||||||||||||||
|
|
Features
