**Abstract**: We are interested in building agents that can autonomously act to carry out complex tasks on
our behalf in complex environments. Although many software architecchtures for agents that can carry out
such decision-making have been proposed, comparatively little research has been devoted to the basic
computational problems that underpin the deployment of such agents. In previous work, we have
investigated the computational complexity of one such problem, known as "agent design". The agent
design problem is as follows: Given a specificaton of a task and an environment in which this task is to be
carried out, determine whether or not there exists an agent that can successfully carry out the task. For a
simple task specification language, we have been able to obtain results showing how the complexity of this
problem varies from PSPACE-complete in the worst case to NL-complete (and hence tractable) in the
best. In this project, we will consolidate and considerably extend this work. We will define a richer and more
general task specification language, allowing tasks to be specified as arbitrary boolean combinations of
"achievement" and maintenance goals. We will then systematically study the complexity of agent design
using this language and subsets of it; investigate its relationship to other tasks specification formalisms,
investigate the related problem of "agent verification" and its relationship to model checking, and finally,
undertake a systematic study of phase-transition phenomena in agent design. Given the high level of
interest in autonomous intelligent agents, the project is timely, and, as very little research has considered
applications of algorithmics to the agent field, it is extremely novel.

**Start**: Jan 1 2002

**End**: Dec 31 2004

**Value**: £155,598

EPSRC Reference: GR/R60836/01

Principal Investigator: Dr P.E. Dunne.

Co-investigator: Prof. M.J. Wooldridge.

**Abstract**:
The primary concern of the work is to produce a sound general basis for the analytic study and
exploitation of phase transition effects in hard combinatorial decision problems. The two principal benefits
that will result from such a basis are: an understanding of how such a phenomena may be exploited in the
design of classes of fast algorithms for such problems; and secondly, a general model within which novel
phase transition results can be derived. In order to address two potential objections to existing
experimental studies - that these do not reflect the properties of 'real-world' data and are unsuited to
problems lacking an 'obvious' parameter that characterises a phase transition - our work will also examine
different empirical frameworks for predicting phase transitions and develop models of probability
distributions that go some way to capturing properties of 'real' data for selected important combinatorial
problems.

**Start**: Oct 1 1997

**End**: Sep 30 2000

**Value**: £134,777

EPSRC Reference: GR/L77089/01

Principal Investigator: Dr P.E. Dunne.

Co-investigator: Prof. A.M. Gibbons.