PED Home Page
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.