|
|
 |
 |
 | | | | |
 |
|||
 |
||||||
          |
 |
 |
||||
|
Action-Based Discretization for AI SearchAs computer gaming reaches ever-greater heights in realism, we can expect the complexity of simulated dynamics to reach further as well. To populate such gaming environments with agents that behave intelligently, there must be some means of reasoning about the consequences of agent actions. Such ability to seek out the ramifications of various possible action sequences, commonly called “lookahead”, is found in programs that play chess, but there are special challenges that face game programmers who wish to apply AI search techniques to complex continuous dynamical systems. In particular, the game programmer must “discretize” the problem, that is, approximate the continuous problem as a discrete problem suitable for an AI search algorithm. As a concrete example, consider the problem of navigating a simulated submarine through a set of static obstacles. This continuous problem has infinite possible states (e.g. submarine position and velocity) and infinite possible trajectories. The standard approach to discretize the problem is to define a graph of “waypoints” between which the submarine can easily travel. A simple waypoint graph can be searched, but this approach is not without significant disadvantages. First, the dynamics of such approximate navigation are not realistic. It’s still common to see massive vehicles in computer games turn about instantly and maintain constant velocity at all times. When considering acceleration in agent behavior, there’s a quick realization that the notion of a “waypoint” becomes far more complex. For example, a vehicle with realistic physical limitations cannot ignore momentum and turn a tight corner at any velocity. A generalized waypoint for such a system would contain not only a position vector, but a velocity vector as well, doubling the dimensions of the waypoint. If waypoint density is held constant, memory requirements grow exponentially with the waypoint dimensions. The second disadvantage is that relevant state can incorporate many factors beyond waypoints in a dynamic environment. If the programmer wishes the submarine to pilot around moving obstacles, state dimensionality is further increased along with an exponential increase of the memory requirements for our state-based discretization. An alternative way to look at the discretization of continuous search problems makes no attempt to discretize the search space at all. Instead, the programmer focuses on two separate discretization issues: discretizing action parameters (choosing a set of ways to act), and discretizing action timing (choosing when to act). When high-dimensionality of the state space makes it infeasible to perform a state-based discretization for search, an action-based discretization can provide a feasible solution if the computer agent control interface is low dimensional with few discrete action alternatives. Even so, action-based discretization is not trivial. In our submarine example, an action-based approach might sample control parameters that affect positional and angular velocity. The choice of the sample is not obvious, and crucial to the effectiveness of search. Additionally, the programmer needs to choose good timing of control actions. If time intervals between actions are too short/long, search is too shallow/deep in time and behavior is thus shortsighted/inadequately responsive. This paper reviews state-of-the-art search algorithms (e.g. Epsilon-Admissible Iterative-Deepening A* and Recursive Best-First Search), and presents new action-based discretization search algorithms that perform action parameter and action timing discretization for the user. In particular, we show how new iterative-refinement approaches provide better, more robust performance than previous algorithms with fixed action-timing discretization. Finally, we compare three different means of action-parameter discretization, including a dispersion technique that generates an approximate uniform sampling of closed action-spaces. Action-Based DiscretizationArtificial Intelligence search algorithms search discrete systems, yet we live and reason in a continuous world. Continuous systems must first be discretized, i.e. approximated as discrete systems, to apply such algorithms. There are two common ways that continuous search problems are discretized: state-based discretization and action-based discretization. State-based discretization becomes infeasible when the state space is highly dimensional. Action-based discretization becomes infeasible when there are too many degrees of freedom. Interestingly, biological high-degree-of-freedom systems are often governed by a much smaller collection of motion primitives [Mataric, 2000]. We focus here on action-based discretization. Action-based discretization consists of two parts: (1) action parameter discretization and (2) action timing discretization, i.e. how and when to act. See Figure 1. The most popular form of discretization is uniform discretization. It is common to sample possible actions and action timings at fixed intervals. For the following algorithms, we focus on action-timing discretization. Experimental evidence of this paper and previous studies [Neller, 2000] suggests that a fixed uniform discretization of time is not advisable for search if one has a desired solution cost upper bound. Rather, a new class of algorithms that dynamically adjust action timing discretization can yield significant performance improvements over static action timing discretization.
Iterative-refinement algorithms use a simple means of dynamically adjusting the time interval between search states. We will present the results of an empirical study of the performance of different search algorithms as one varies the initial time interval between search states. We formalize our generalization of search, describe the algorithms compared, present our chosen class of test problems, and present the experimental results.
|
||||||||||||||||||||||||
|
|
Action-Based
Discretization for AI Search
Features
