@InProceedings{wooldridge00a,
  author =	 {Michael Wooldridge},
  title =	 {The Computational Complexity of Agent Design
                  Problems},
  googleid =	 {I5u6TbUDwc8J:scholar.google.com/},
  booktitle =	 {Proceedings of the Fourth International Conference
                  on Multi-Agent Systems ({ICMAS} 2000)},
  year =	 2000,
  editor =	 {E. Durfee},
  month =	 {July},
  publisher =	 {{IEEE} Press},
  abstract =	 {This paper investigates the computational complexity
                  of a fundamental problem in multi-agent systems:
                  given an environment together with a specification
                  of some task, can we construct an agent that will
                  successfully achieve the task in the environment? We
                  refer to this problem as agent design. Using an
                  abstract formal model of agents and their
                  environments, we begin by investigating various
                  possible ways of specifying tasks for agents, and
                  identify two important classes of such
                  tasks. Achievement tasks are those in which an agent
                  is required to bring about one of a specified set of
                  goal states, and maintenance tasks are those in
                  which an agent is required to avoid some specified
                  set of states. We prove that in the most general
                  case the agent design problem is PSPACE-complete for
                  both achievement and maintenance tasks. We briefly
                  discuss the automatic synthesis of agents from task
                  environment specifications, and conclude by
                  discussing related work and presenting some
                  conclusions.},
  keywords =     {multiagent aose},
  url =
                  {http://jmvidal.cse.sc.edu/library/wooldridge-icmas2000a.ps},
  cluster = 	 {14970250713584278307}
}