Features

Action-Based Discretization for AI Search

Submarine Channel Problem

The Submarine Channel Problem is not unlike a Sega videogame of the 1980's called Frogger. A submarine seeks a path through a channel such that it avoids being detected by a number of patrolling ships. We have chosen this problem because, like the n²-1 sliding tile puzzles, it can serve as a benchmark easily scalable to greater difficulty.

	Figure 4: Submarine Channel Problem

In the Submarine Channel Problem, the submarine starts at position (x, y) = (0, 0) with eastward heading and at full stop. To the east along an east-west channel of width w (centered along y=0) are n ships patrolling across the width of the channel. This is pictured in Figure 4.

Each ship j has an inner detection radius ri,j and an outer detection radius r_o,j. Within a proximity of r_i,j, ship j will detect the submarine and the submarine will be penalized with a detection penalty. Within a proximity of r_o,j and beyond r_i,j, the submarine incurs a proximity penalty scaling linearly from 0 at the outer radius to the full detection penalty at the inner radius. Beyond the outer radius, there is no penalty. If the submarine collides with the sides of the channel, there is a collision penalty. In the case of collision or detection, the submarine is halted and allowed no further legal moves. The first ship patrols at an x-offset xOffset₁ = r_o,1. Each ship k thereafter has xOffset_k = xOffsetk_-1 + 3_ri,_k-1 + r_i,k. Ship k has a patrolling route defined by cycling linearly between the following points: (xOffset_k, w/2_-ri,k), (xOffset_k+2r_i,k, w/2_-ri,k ), (xOffset_k +2r_i,k, -w/2_+ri,k), and (xOffset_k, -w/2 + r_i,k). Each ship begins at a given percentage along this cycle. For n ships, the goal states are all states within the channel with x > xOffset_n + 2r_i,n + r_o,n, i.e. all channel points to the right of the rightmost outer detection radius.

The submarine can travel in eight headings (multiples of p/4 radians), and three speeds: full speed, half speed, and full stop. Together these define 17 distinct actions the submarine can take at any point which it has incurred neither collision nor full detection penalty. (Since we assume discrete, instantaneous changes to headings and speeds, all full stop actions are effectively equivalent.) Each ship travels at a single predefined speed.

Random, Uniform, and Dispersed Discretization

Generalizing the submarine channel problem for DADAT search, we allow any heading and any speed up to the maximum. Thus an action, i.e. changing heading and speed, can be thought of as picking a point in a circular region with the radius being the maximum speed. The center point is a full stop, and any other point indicates a heading and speed (in polar coordinates).

Faced with this freedom of choice in our search algorithms, we present three ways of performing dynamic action parameter discretization. First, we can randomly choose parameters with independent uniform distributions over headings and speeds. Second, we can take a fixed uniform discretization as described above and rotate it by a random angle. Third, we can seek to generate a discretization with action parameters as “far” from each other as possible. We call this last technique “dispersed discretization”.

The basic idea of “dispersed” discretization is to take a number of randomly sampled points from the action region and simulate them as if they were point charges mutually repelling each other with force proportional to the inverse square of their distance. The point dispersion algorithm pseudo-code is as follows:

DISPERSE (REGION, SAMPLES, WEIGHT, DECAY, ITERATIONS)
FOR I = 1 to SAMPLES
   X[I] := random point in REGION
FOR I = 1 to ITERATIONS
   FOR J = 1 to SAMPLES
      DX[J] := 0
      FOR K = 1 to J
         DIFFERENCE := X[K] – X[J]
         DISTANCE := SQRT(X[J]2 + X[K]2)
         DX[J] := DX[J] – DIFFERENCE/(DISTANCE3)
         DX[K] := DX[K] + DIFFERENCE/(DISTANCE3)
   FOR J = 1 to SAMPLES
      DX[J] := WEIGHT * DX[J]
      X[J] := X[J] + DX[J]
      IF X[J] not in REGION,
         reassign X[J] to the closest point in the REGION
   WEIGHT := WEIGHT * DECAY
RETURN X

We used a repulsion factor of 0.008 and a repulsion factor decay of 0.93 for 20 iterations. These values were chosen empirically based on a small number of trials with the submarine action region. In future work, we would desire these dispersion parameters to be rapidly self-adapting to the size of the region and the number of sampled points.

Experimental Results

For these experiments, we have chosen w=1 length unit. The outer radius of each ship is 0.2w. The inner radius of each ship is 0.1w. The maximum velocity of the submarine is w/(1 time unit). All ship velocities are also w/(1 time unit). Ships are started at random percentages through their patrol cycles. The detection and collision penalties are set at 10000. In each experimental trial we generated a random 10-ship submarine channel problem. A successful trial found a solution within 10 seconds of search. For each initial time delay Dt we ran 100 trials.

Figure 5 summarizes experimental results comparing the performance of random, uniform, and dispersed discretization techniques used with a form of iterative-refinement depth-first search. Note that the dispersed discretization rate of success exceeds that of the other discretization techniques.

Looking over a number of dispersed discretizations, one quickly notices that more points are repelled to the edge than in the uniform discretization. Although not a probable configuration, any number of points placed at even intervals around the edge would be in equilibrium. With repulsion parameters given above, it was typical to see 12 or more points along the edge of the circle with five or fewer points dispersed internally. Empirically, extreme parameters represented by the edge of the circular action region are more likely to appear in optimal solutions. We hypothesize that having extra edge action choices aids in finding better approximations to optimal solutions.

	Figure 5: Varying initial delay with different action parameter discretizations.

Furthermore, in this problem domain, searches of faster submarine trajectories (i.e. with discretizations having more maximal velocities) will have lesser search depths to solutions if such speedy solution trajectories exist. Since search depth affects search time complexity exponentially, we likely benefit from a discretization with more maximal velocity values.

One key lesson in this and other experiments of [Neller, 2000] is that behaviors of greatest interest often occur at extreme parameter values. Another key lesson is that an automated discretization technique outperformed one hand-chosen by researchers (uniform). Not only can such discretization techniques reduce the discretization burden of the programmer; they may also yield superior discretizations.

Conclusions

Artificial Intelligence search algorithms search discrete systems. To apply such algorithms to continuous systems, such systems must first be discretized, i.e. approximated as discrete systems. Action-based discretization requires that both action parameters and action timing be discretized.

The empirical study concerning sphere navigation provided insight into the importance of searching with dynamic time discretization. Iterative-refinement algorithms are given an initial time delay Dt₀ between search states and a solution cost upper bound. Such algorithms iteratively search to this bound with successively smaller Dt until a solution is found.

Iterative-refinement ,-admissible recursive best-first search (IR Î-RBFS) was shown to be similar or superior to all other searches studied for Dt₀ spanning over five orders of magnitude. With respect to Î-RBFS (without iterative-refinement), a new ,-admissible variant of Korf's recursive best-first search, IR Î-RBFS offers significantly better performance for Dt₀ spanning over four orders of magnitude.

Iterative-refinement algorithms are important for search problems where reasonable values for Dt are unknown or known and one wishes to find a solution more quickly and reliably. The key tradeoff is that of knowledge. Lack of knowledge of a good time discretization is compensated for by knowledge of a suitable solution cost upper bound. If one knows a suitable solution cost upper bound for a problem where continuous time is relevant, an iterative-refinement algorithm such as IR Î-RBFS is recommended.

Finally, in the context of a submarine detection avoidance problem, we introduced a dispersed discretization technique for dynamically choosing action parameters. The resulting discretization was superior to a uniform discretization chosen by researchers.
Here we have presented a few techniques for dynamically discretizing both action parameters and action timings of continuous search problems with empirical evidence of their benefits. We see this work as providing first steps in a class of algorithms that will prove important in the application of AI search algorithms to continuous problem domains.

Bibliography

Korf, R. E. 1985. Depth-first iterative-deepening: an optimal admissible tree search. Artificial Intelligence 27(1):97-109.

Korf, R. E. 1993. Linear-space best-first search. Artificial Intelligence 62:41-78.

Mataric, M. J. 2000. Sensory-motor primitives as a basis for imitation: Linking perception
to action and biology to robotics. In Nehaniv, C., and Dautenhahn, K., eds., Imitation in Animals and Artifacts. Cambridge, MA, USA: MIT Press. See also USC technical report IRIS-99-377.

Neller, T. W. 2000. Simulation-Based Search for Hybrid System Control and Analysis, Ph.D. Dissertation, Stanford University, Palo Alto, CA, USA. Also available as Stanford Knowledge Systems Laboratory technical report KSL-00-15 at www.ksl.stanford.edu.

Russell, S., and Norvig, P. 1995. Artificial Intelligence: a Modern Approach. Upper Saddle River, NJ, USA: Prentice Hall.

______________________________________________________

[Back To] Action-Based Discretization for AI Search

join | contact us | advertise | write | my profile
news | features | companies | jobs | resumes | education | product guide | projects | store



Copyright © 2003 CMP Media LLC

privacy policy | terms of service