Tech Reports

ULCS-03-020

On the Computational Complexity of Designing Bounded Agents

Michael Laurence, Paul E. Dunne and Michael Wooldridge

Abstract

In this paper, we determine the computational complexity of the agent design problem for several classes of bounded agents. Agent design is the problem of determining, for a given representation of an environment and representation of a task to be carried out in this environment, whether it is possible to construct an agent that can be guaranteed to accomplish the task in the environment. Previous research has determined the complexity of the agent design problem for various classes of environment and task, but where the agent was permitted perfect recall of prior events. In this paper, we investigate the complexity of the problem for agents that have various bounds placed on their memory. Specifically, we determine the complexity of the agent design problem for reactive agents, (which must make a decision about what to do based solely on the current environment state), k-reactive agents (which must make a decision based on the last k environment states), and oblivious agents (which have no information about the environment at all).

For each technical report listed here, copyright and all intellectual property rights remain with the respective authors. Copyright is effective from the year of publication in each case. By downloading a file from this page, you agree to use it only for purposes of research and scholarship. Any other use of this material or storage of it in any medium or its sale or distribution in any form is expressly forbidden without prior written permission from the authors concerned.