Skip to main content Skip to navigation

Department of Computer Science

Empirical Modelling Project Ideas 2003/04

(This document was originally written April 22nd 2002 by Chris Roe and Ashley Ward, revised by Meurig Beynon on 13th May 2003 and moved to a new home by Ashley Ward on April 25th 2005.)

The list of projects below is classified under five headings: Refinements to Tools, Communication and Maintenance of EM models, Applications of EM, EM Principles from a Computer Systems Perspective, and Reflection on EM. These suggested topics complement those listed on the personal webpages of Meurig Beynon (see http://www.dcs.warwick.ac.uk/~wmb/projects03.html) and Steve Russ (see http://www.dcs.warwick.ac.uk/~sbr/projects00.html), whom you should consult for further details and potential supervision.

The topics listed here may suggest ideas that you can adapt to suit your personal interests, or serve as a starting point for your project work. In practice, because of the open-ended exploratory nature of model-building in EM, it has been common for students to devise their own projects, possibly in the process of tackling one of the suggested topics. Several of these proposals are best appreciated when considered in conjunction with models in the EM projects archive, or other models that have yet to be entered into the archive that can be obtained on request. Papers that relate to some of the topics can be found in the local /dcs/empublic/papers directory (as indexed on the Conference and journal papers page), and a series of weekly meetings to support EM project students will be organised by WMB and SBR throughout the first term of 2003-4.

Refinements to Tools

1. Applying the agent-oriented parser

The TkEden interpreter allows the use of the definitive notation EDEN, a notation for line drawing (DoNaLD), a notation for windowing layout (SCOUT) and a notation for three-dimensional modelling (Sasami). It is possible to switch between these notations on input either by clicking on a radio button in the input window or by typing %donald, %scout etc prior to entering definitions.

Chris Brown's 3rd year project [CB2000] developed an agent-oriented parser which allows the creation of new notations 'on the fly' within the EDEN interpreter. This parser has been refined through Antony Harfield's 3rd year project [AH2001] so as to create a powerful parser-building environment that makes the development of new notations much simpler. We can use the agent-oriented parser (AOP) to create our own notations which are more domain specific and give them their own radio button for use through the interpreter. There have been a few examples of this technique that have already been implemented. The best known is the SQL-EDDI environment which contains notations for the use of a relational algebra style language, and some variants of SQL to investigate concepts in relational databases. Other case studies that have been written include a parser for Logo, a clown movement language, a more advanced windowing language, a notation for specifying systolic arrays etc etc. The opportunities for this tool are still relatively unexplored and are very broad.

There are several possible projects that might deploy the agent-oriented parser in implementing notations. Some suggestions are:

i) write new parsers for DoNaLD, SCOUT and Sasami

ii) re-implement the EDDI parser with simpler actions that do not introduce unnecessary intermediate variables, and/or extend the SQL-EDDI environment to include other relational query languages, such as QUEL, or possibly Date and Darwen's D language

iii) write a parser for the ARCA notation. (The ARCA notation was the first definitive notation to be designed at Warwick early in the 1980's by Meurig Beynon and Nader Fahranak: it can be used to display and manipulate combinatorial diagrams, and features in several EM models.)

References

  • CB2000 - C.Brown (2000) - An agent-based parsing system in EDEN.
  • AH2001 - A Harfield (2001) - Extending the agent-oriented parser.

2. Re-implementing the Abstract Definitive Machine

The Abstract Definitive Machine (ADM) was originally developed by Beynon, Slade and Edward Yung in 1988. It is a vehicle for agent-oriented modelling and simulation of concurrent systems. There is no entirely satisfactory implementation of the ADM, and present methods of development involve an initial translation to tkeden that is out of keeping with the interactive style of model-building in tkeden. The aim of this project would be to study existing implementations and design issues, and explore the prospects for a new implementation. This could take advantage of features of tkeden that have been developed much more recently, such as the potential for distribution (dtkeden), the use of EDDI, and the AOP.

3. Developing a visual interface editor for Scout

One of the most tedious tasks in developing tkeden models is specifying interactive actions in Scout windows, such as pressing and releasing mouse buttons or keys, and reading and changing the text in a window. Although low-level observables can be used to implement these actions, this is difficult and inconvenient for the modeller to do in a comprehensible way.

This project is to implement a VB-like editor by means of which we can create Scout windows and buttons by direct manipulation using drag and drop techniques.

Communication and Maintenance of EM Models

4. A slide presentation notation

Tkeden has been used to implement presentation environments in which conventional slides can be mixed with demonstrations of models in the same window. This has advantages over the 'usual' style of presentation, which is based on combining Powerpoint slides with demonstrations of software stored elsewhere on the computer. The design of a notation to enable slide presentations to be created and edited would reduce the time needed to prepare such materials. It would also require a careful analysis of the possible uses to which this type of tool may be put.

5. A demonstration tool for Empirical Modelling

DemoMaker is a tk/tcl tool for use in conjunction with tkeden. It helps to address the difficulties we have in recording the patterns of interaction with an EM model that have most significance for the modeller. DemoMaker allows interactions with tkeden models to be recorded, annotated and replayed. This project will explore the use of DemoMaker in illustrating EM principles. The first stage of the project would be to fix bugs in the current version of DemoMaker using Tcl/Tk (a multi-platform GUI environment). It would then be possible to focus on creating some useful demos, with an accompanying sound track "video" that might reflect the developer's commentary on the model-building activity. Such demos could either be based on existing EM models, or on new models developed with specific topics (such as the use of DoNaLD, or the principles of 'cognitive layering') in mind.

6. A projects database model

The EMpress system currently exists as a database in the EDDI notation. An interface needs to be created so that users can find the projects that interest them from this database. The database itself also needs expansion to cover all of the printed materials that the EM group has. If this is successful further work can be done to generalise to implementing Microsoft Access in tkeden.

7. A definitive file system

The aim of this project is to develop an environment in which dependencies between files can be conveniently maintained. Such an environment could be used to store a definitive script together with up-to-date versions of variants of the script. These variants could have a role in documenting the script and/or represent alternative views in a concurrent engineering context. By way of analogy, think of a 'make' process being continually active, compiling files, analysing log files etc..

8. Libraries to support EM

There are many different ways in which models generated by EM can be adapted and reused. The aim of this project is to explore ways in which reusable components can be developed and documented. Possible examples of reusable components could include conventional objects, special purpose functions and templates.

Applications of EM

9. Empirical Modelling for education

There are potentially many ways in which EM principles can be applied in education.

Possible topics in this area include:

  • Simulations to recreate historical events, such as railway accidents or battles.
  • Simulations to illustrate engineering principles and mechanisms.
  • Simulations to demonstrate rule-based protocols, e.g. in sport or law.
  • Computer aided learning environments, e.g. for teaching algorithms, elementary programming and mathematics.
  • Computer assisted assessment based on interactive evaluation of models constructed using EM principles.
  • Models to support presentation and analysis of plays and novels.
  • The use of EM models to represent metaphor, analogy and blending (ref: The Literary Mind - Mark Turner).
  • The development of EM models for special needs use.

10. Collaborative working with definitive scripts over the Internet

The Internet introduces exciting possibilities for distributed modelling and simulation using definitive scripts. This project is to investigate and implement a system whereby many modellers/experimenters can work together on a model over the Internet.

11. Empirical Modelling for multi-agent distributed simulations

Motivations

Have you ever considered how the behaviour of a large group of interacting entities is determined? How do colonies of ants find and utilise food sources whilst avoiding danger? How do traffic jams form and what is their behaviour over time? How do crowds of people behave?

Massively parallel simulations

These situations are all similar in that they are made up of large numbers of interacting agents. Agents interact locally with one another and with their environment according to very simple rules, but the emergent behaviour of a large group can be far more complex. In educational computing research these decentralised simulations (i.e those which have no central control) have been used and programmed by children investigating questions similar to those posed above.

Project Objectives

The aim of this project is to investigate the best way to implement multi-agent simulations using Empirical Modelling principles developed here at Warwick. In this context we are taking 'multi-agent' to mean 50+ agents. Implementation of case studies to show how these principles work in practice is an integral part of this project. Once a simulation has been built it can be used as the basis for investigating whether Empirical Modelling principles and techniques are more appropriate than other paradigms for creating and exploring these massively distributed simulations.

Some Resources

12. Distributed implementation of existing tkeden models

The development of a client-server variant of tkeden makes it possible to improve the structure and the performance of existing tkeden models. Candidate case-studies for investigation include cricket, multi-user games (such as the Great Game of Britain), billiards and variants of the vehicle cruise control simulations.

13. Software development using the LSD Engine

The LSD Engine is a multi-agent modelling environment that was developed as an alternative approach to software development for reactive systems. The development was carried out in Moscow under the direction of Valery Adzhiev, and the engine runs under Windows NT. It takes LSD scripts, which you supplement with priorities for action synchronization, and animates them. This project is to explore the potential of this machine by adapting existing scripts and developing new ones.

14. Agent-oriented modelling for air traffic control

The aim of this project is to investigate the application of agent-oriented modelling principles developed in EM to the specification of air traffic control protocols. The principal focus will be on constructing LSD specifications to capture the rules set down in the official air traffic control handbook. Complementary work could involve simulation using tkeden and/or the LSD Engine. Though there has been significant progress in tackling this project in previous work, there are still interesting new issues to be addressed.

See Stefanos Tsitsibassos's MSc project report for some previous work on this idea, and subsequent projects by Marcos Xenophontos (2000-1) and James Coin (2002-3)

EM Principles from a Computer Systems Perspective

15. "Real time" (RT) tkeden

We can link tkeden to some hardware eg a pendulum or a buggy. Issues arising include: Can we guarantee to meet RT deadlines (guarantee that the dependency maintenance will only take a maximum time t per step)? A definitive script lends itself to static analysis: the system should be able to tell when it is not able to meet its deadlines and warn the user. We can implement RT inputs by polling or interrupts, and assume clock tick at a given frequency, and consider what different platforms cope with.

16. "Low level" or "embedded" EM

EM and embedded systems might match up quite well as we aim to make use of primitives that are more meaningful in the real world anyway. Possible systems to be developed include: a Hoover clock, or football playing robots with little fan and ping pong balls. For related references see Rodney Brooks's work, and variants of LOGO. A possible implementation strategy involves modelling on a "big" system, then using prototype translation tools that have been developed in the past, such as def2proc, and another filter, say proc2c, before compiling for the target system. This could be based on Rod Moore's COA buggies. An alternative implementation route involves writing a low level Definition Maintainer to control hardware.

17. Development and use of the DAM machine

This project will build on James Allderidge's DoNaLD to DAM compiler (1997). The DAM (Definitive Assembler Maintainer) machine is written in ARM code for execution on the Acorn RISC PC platform. Possible extensions to Allderidge's project include greater dynamism in the compilation process and/or the compilation of additional definitive notations.

There is potentially scope for experimental and creative use of the DAM machine. Possible case-studies include the implementation of heapsort, direct screen driving and definitive addressing.

Reflection on EM

18. Comprehension and re-use of EM models

Understanding EM models poses quite different challenges from normal program comprehension. Experimental interaction with models plays a significant role. The aim of this project is to reflect on the qualities and weaknesses of EM models as they are currently being developed and documented. A suitable focus for the project might be the eight versions of the Pjawns board game that were created for the practical assignment in CS405 in 2002-3; analysing these with a view to identifying principles for comprehension and re-use that could then be applied to the construction of a tournament, and for the development of a 'supermodel' that combines the best qualities of each of the individual models. Analysis of other simpler EM models would be a necessary prerequisite activity, but the emphasis in this project would be on 'EM-user' interaction, reflection and documentation rather than large scale model-building.

19. Comparison and evaluation: EM principles and tools in context

There are many commercial packages and tools that have points of connection with EM. In evaluating EM, there is a need for us to be aware of the qualities and power of existing packages, and where the principles and tools they employ differ and overlap. The aim of this project is to develop small case studies that enable us to assess EM principles and tools in relation to other approaches. Examples might include: (relatively small) applications of Excel, Mathematica, Matlab, Labview, AgentSheets, VB, Perl etc that - typically, but not necessarily, through the development of EM models to address them - serve to shed light on the strengths and weaknesses of EM. For this project, the final report would take the form of a critique of EM, with recommendations concerning respects in which EM principles and tools can be improved.

20. Assessment and quality assurance for EM models

This is your opportunity to influence the assessment of your own third year project even as you are doing it! The aim of the project is to develop principles, tools and techniques that can be used to assess the quality of EM models, such as might be applied in particular to determine which of the many models in the EM archive are most faithful to EM principles, and make the most effective and authentic use of the EM tools. There are a number of aspects to the project that could be developed: devising extensions to existing models that allow them to be viewed and manipulated in the way that an assessor might wish to treat them, supplying metrics to record the number of definitions, building special-purpose tools to strip away the automatic agency so as to expose the primitive experimental interaction that normally precedes automation, specifying testing strategies that can be used to assess families of models such as the eight versions of the Pjawns game mentioned above. This project could include some examples of poor use of EM principles and tools, together with proposals for how these can be redeemed through reworking models or refining tools.