The Computational Complexity of Boolean and Stochastic Agent Design Problems

摘要

The Agent Design problem involves determining whether or not it is possible to construct an agent capable of satisfying a given task specification in a particular environment. The simplest examples of such specifications are where an agent is required to bring about some goal or where an agent is required to maintain some invariant condition. Both cases can be viewed as identifying a set of states with a single propositional variable, x, so that the tasks are specified by formulae x (reach one of the states represented by x) or x (avoid all of the states represented by x). In previous work, the complexity of agent design problems expressed by single argument propositional formulae has been systematically investigated for a range of different types of environments. It was shown that the complexity of the problem varies from NL-complete in the best case to undecidable in the worst. In this paper, we extend these previous results by investigating the effect on problem complexity of allowing tasks for agents to be specified as arbitrary propositional formulae of n variables. We show that, in those settings where Agent Design is PSPACE or NP-complete the general problem is "no more difficult", i.e., remains in PSPACE or NP. In contrast, a number of the settings for which there were polynomial-time methods become NP-complete when considering more general task specifications. Finally, we investigate the complexity of stochastic agent design problems, where we require an agent that has a "better than evens" chance of success: we show that complexity results for the "guaranteed success" cases carries across to stochastic instances.