| EPSRC Reference: |
GR/R60836/01 |
| Title: |
Algorithmics for Agent Design & Verification |
| Principal Investigator: |
Dunne, Dr PE |
| Other Investigators: |
|
| Researcher Co-Investigators: |
|
| Project Partners: |
|
| Department: |
Computer Science |
| Organisation: |
University of Liverpool |
| Scheme: |
Standard Research (Pre-FEC) |
| Starts: |
01 April 2002 |
Ends: |
31 March 2005 |
Value (£): |
155,598
|
| EPSRC Research Topic Classifications: |
|
| EPSRC Industrial Sector Classifications: |
|
| Related Grants: |
|
| Panel History: |
|
|
Summary on Grant Application Form |
|
We are interested in building agents that can autonomously act to carry out complex tasks on our behalf in complex environments. Allthough many software architecchtures for agents that can carry out such decision-making have been proposaed, comparatively little research has been devoted to the basic computational problems that uinderpin 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 th task. For a simple task specification language, we have been able to obtain results showing how the complexity of this problem varies from PSPACE- completein 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 arbititrary 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 it's relationship to other tasks specification formalisms, investigate the related problem of agent verification and it's relationship to model checking, and finally, undertake a systematic study of phase transitions 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.
|
|
Key Findings |
|
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
|
|
Potential use in non-academic contexts |
|
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
|
|
Impacts |
|
| Description |
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk |
| Summary |
|
| Date Materialised |
|
|
|
|
Sectors submitted by the Researcher |
|
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
|
| Project URL: |
|
| Further Information: |
|
| Organisation Website: |
http://www.liv.ac.uk |