|
| EPSRC Reference: |
GR/R45338/01 |
| Title: |
Distributed Simulation of Agent-Based Systems (Acronym: PDES-MAS) |
| Principal Investigator: |
Dr G Theodoropoulos |
| Other Investigators: |
|
| Researcher Co-investigator: |
|
| Project Partner: |
|
| Department: |
School of Computer Science |
| Organisation: |
University of Birmingham |
| Scheme: |
Standard Research |
| Starts: |
05 November 2001 |
Ends: |
04 July 2005 |
Value (£): |
212,511
|
| EPSRC Research Topic Classifications: |
| ICT Networks and Distributed Systems |
|
|
| EPSRC Industrial Sector Classifications: |
| Aerospace, Defence and Marine |
Environment |
| Creative Industries |
Information Technologies |
|
| Related Grants: |
|
| Panel History: |
|
|
Summary |
There has been considerable recent interest in agent-based systems, systems based on autonomous software and/or hardware components (agents) which cooperate within an environment to perform some task. Agents are increasingly being applied in a wide range of areas including telecomms, business process modelling, computer games, control of mobile robots and military simulations. While agents offer great promise, adoption of this new technology has been hampered by the limitations of current development tools and methodologies. Design and implementation remains largely experimental, and experimental approaches are likely to remain important for the foreseeable future. In this context, simulation has a key role to play in the development of agent-based systems, allowing the agent designer to learn more about the behaviour of the system or to investigate the implications of alternative architectures. However, the computational requirements of simulations of agent-based systems far exceed the capabilities of conventional sequential von Neumann computer systems and parallel simulation emerges as a viable solution to this problem. However, work to date has largely ignored recent work in simulation methodology and systems, and has tended to employ various ad-hoc approaches to parallel simulation, and, as a result, the simulations often have relatively poor performance, limiting the nature and scope of the experiments that can be performed. The proposal aims to develop appropriate algorithms and techniques to support the efficient decentralised, event driven parallel simulation of agent based systems.
|
| Final Report Summary |
We have developed a framework for the optimistic distributed simulation of multi-agent systems. The framework represents agents as Agent Logical Processes (ALPs) while the shared state is decomposed in a tree-shape hierarchical structure of Communication Logical Processes (CLPs), which is dynamically reconfigured to reflect the logical topology of the model. We have done a detailed theoretical analysis of the ways in which agents in a MAS simulation interact with the shared state (the agent's environment) and we developed a model of the shared state based on tuple spaces. We have developed a state migration and load-balancing algorithm, which minimises the cost of managing and accessing shared state, in order to optimize the performance of the simulation, based on appropriate performance and cost metrics we have defined for that purpose. Two approaches were developed for routing data access queries in the simulation, namely the address-based and the range-based routing algorithms. These algorithms target target both individual data items (ID query) and selected data items overlapping query windows (Range query). The project also developed two adaptive synchronisation algorithms. The first of these algorithms uses the notion of Critical Accesses and a window-based throttling mechanism to constrain execution of the Agent Logical Processes while the second algorithm uses a decision theoretic approach to delay incoming read events which are likely to be rolled back. The effectiveness of all the algorithms we developed in the project was investigated experimentally using trace-driven simulation. For this purpose, event traces from standard agent benchmarks such as Tileworld and Boids were collected for a wide range of simulation parameters. The algorithms and techniques, which form the main outputs of the project have led to the development of a distributed simulation kernel based on MPI.
|
| Further Information: |
http://www.cs.bham.ac.uk/research/pdesmas/ |
| Organisation Website: |
http://www.bham.ac.uk |
|
|