The computational complexity of boolean and stochastic agent design problems

ABSTRACT

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, χ, so that the tasks are specified by formulae χ (reach one of the states represented by χ) or barx (avoid all of the states represented by χ). 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 η 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.

References

1. C. Baral, V. Kreinovich, and R. Trejo. Computational complexity of planning and approximate planning in presence of incompleteness. In Proceedings of the Sixteenth International Joint Conference on Artificial Intelligence (IJCAI-99), Stockholm, Sweden, 1999]]
2. T. Bylander. The computational complexity of propositional STRIPS planning. Artificial Intelligence, 69(1-2):165--204, 1994]]
3. P. E. Dunne and M. Wooldridge. The complexity of agent design problems: Determinism and history dependence, 2001. Submitted]]
4. L. P. Kaelbling, M. L. Littman, and A. R. Cassandra. Planning and acting in partially observable stochastic domains. Artificial Intelligence, 101:99--134, 1998]]
5. M. L. Littman, J. Goldsmith, and M. Mundhenk. The computational complexity of probabilistic planning. Journal of AI Research, 9:1--36, 1998]]
6. C. H. Papadimitriou. Computational Complexity. Addison-Wesley: Reading, MA, 1994]]
7. S. Russell and D. Subramanian. Provably bounded-optimal agents. Journal of AI Research, 2:575--609, 1995]]
8. M. Wooldridge. The computational complexity of agent design problems. In Proceedings of the Fourth International Conference on Multi-Agent Systems (ICMAS-2000), pages 341-348, Boston, MA, 2000]]
9. M. Wooldridge and P. E. Dunne. Optimistic and disjunctive agent design problems. In Y. Lespérance and C. Castelfranchi, editors, Proceedings of the Seventh International Workshop on Agent Theories, Architectures, and Languages (ATAL-2000), 2000]]

Index Terms

• Computing methodologies

  • Artificial intelligence

    • Control methods

    • Distributed artificial intelligence

    • Search methodologies

• Theory of computation

  • Design and analysis of algorithms

    • Algorithm design techniques

      • Dynamic programming

  • Models of computation

    • Abstract machines