Action-Based Discretization for AI Search
Dr. Todd W. Neller*
Department of Computer Science Gettysburg College Campus Box 402 Gettysburg, PA 17325-1486 Introduction As 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.…show more content… Rather, a new class of algorithms that dynamically adjust action timing discretization can yield significant performance improvements over static action timing discretization.
Figure 1: Action-based 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. Dynamic Action Timing Discretization We will assume that the action parameter discretization, i.e. which action parameters are sampled, is already given. From the perspective of the search algorithm, the action discretization is static (cannot be varied by the algorithm). However, action timing discretization is dynamic (can be varied by the algorithm). For this reason, we will call such searches "SADAT searches" as they have Static Action and Dynamic Action Timing discretization. SADAT searches are different than classical AI searches in only one respect. An action (i.e. operator) additionally takes a time delay parameter indicating how much time will pass before the next action is taken. For dynamical systems where timing is relevant, this is an important generalization. A SADAT search problem is made up of four parts:
