Complexity Results for Agent Design Problems
Paul E.S. Dunne, Michael R. Laurence, Michael Wooldridge · 2003
Abstract — The Agent Design problem involves determining whether or not it is possible to construct an agent capable of accomplishing a given task in a given environment. The simplest examples of such tasks are where an agent is required to bring about some goal (achievement tasks) or where an agent is required to maintain some invariant condition (maintenance tasks). Previous work has considered the complexity of achievement and maintenance agent design problems for a range of environmental properties. In this paper, we investigate the computational complexity of the agent design problem in three further settings. First, we investigate the issue of tasks that are specified as Boolean combinations of achievement and maintenance tasks. Second, we investigate the extent to which an agent’s information about the history of the environment in which it operates affects the complexity of the problem: in the bounded agent design problem, an agent is constrained to have a 0, 1, or k> 1 bound on what it is permitted to “remember ” about the history of the system. Finally, we investigate the complexity of stochastic agent design problems, where we ask whether there is an agent that has a probability of success at least p. Index Terms — multiagent systems, computational complexity. I.