Research Statement for Scott D. Anderson

Simulation is increasingly important to empirical computer science, as computer programs are designed for task environments that are difficult or expensive to test directly. For example, robots may be used for scientific operations in space or for cleanup operations in toxic waste dumps. My research is in empirical artificial intelligence (AI), studying how AI agents confront complex problems in realistic, albeit simulated, environments. Because environmental processes continue while the agents are thinking, there is a natural time-pressure on the agents: they cannot think for as long as they might like to. One illustration is the PHOENIX environment, in which the agents are firefighters, planning and acting to put out fires in a simulation of Yellowstone National Park.

Simulators for such environments need to specify the correspondence between an agent's computation and the passage of time in the simulation. Almost every such simulator defines that correspondence using the CPU time of the agent's computation. Unfortunately, the resulting simulations have unwanted variance, due to inaccuracies in measuring CPU time, and are machine-dependent, limiting the ability to replicate results. Furthermore, for an agent to be able to think about and schedule its own cognitive activities (called deliberation scheduling), there must be an explicit representation of the duration of cognitive actions.

My dissertation work implements a simulation substrate to support empirical research with embedded agents (agents acting in environments). (This research is the centerpiece of a pending DARPA contract, which I drafted the proposal for.) The substrate provides a complete programming language for defining agents. A database of durations of language primitives defines the correspondence between cognitive activity and simulation time. New primitives can be added to the duration database, allowing simpler models to be defined for high-level activities of the agent. For example, expanding a search node might be an important cognitive activity of an agent, implemented by the expand function. The duration of expanding a node can either be defined by the primitives executed by expand or expand can be added to the database as a new primitive, with its own duration. Researchers can vary that duration to determine its effect on performance and on an agent's plans.

A language with defined durations solves the variance, machine-dependence and replicability problems. In addition, it allows introspection by an agent. That is, an agent can use the defined durations to estimate the duration of its cognitive activities, to plan how to solve the problem, and thereby letting it act effectively under time pressure. Furthermore, the duration database lets cognitive scientists use the language to implementing cognitive models, where the duration models are independent of any computer platform.

Finally, my simulation substrate allows a greater range of experiment designs, because simulation states can be reconstructed, allowing alternate futures to be explored from a state. For example, by running many trials from a single state, we can estimate the probability of failure from that state, or of a decision in that state. It also promotes sharing of domains (environments) among researchers, since it is a domain-independent substrate upon which domains are built.

My future research will continue to be in empirical AI. My interests span real-time computing, scheduling, planning (and replanning), and embedded agents. Simulation is also central to my research. It is an indispensable tool in empirical AI, because it allows experimentation in domains that are either too difficult, expensive or dangerous to use directly or would lack the necessary experimental control. In the near future, I intend to implement and experiment with a number of planning and scheduling algorithms, to see how they perform in realistic domains, which have large state spaces and stochastic processes. I am particularly interested in their degradation as time-pressure increases. I will also be looking at robustness of plans as a function of the uncertainty of the environment: how long do plans stay on track, and how do they fail as they get off track?

My current research is in two areas. The first is interleaved planning and execution using incomplete versions of classical goal-regression planners. The planners are incomplete because they do not search for a finished plan, but stop planning when an executable action is found. The second area is simulation environments to support real-time planning. The simulation environments need to provide easy extensibility and easy implementation of planners. Back to my home page