On the Computational Complexity of Designing Bounded Agents
Michael R. Laurence, Paul E.S. Dunne, Michael Wooldridge · 2003
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).