Empirical Modelling Project Ideas 2012/13
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. Since most of these project proposals offer open-ended scope for extension, many provide a suitable basis both for final year and masters level projects. (Attendance at the CS405 Introduction to Empirical Modelling module would normally be a prerequisite for taking on a masters project in this area.) The topics suggested here complement those listed on the personal webpages of Meurig Beynon (see http://www.dcs.warwick.ac.uk/~wmb/projects07.html) and Steve Russ (see projects09.pdf), whom you should consult for further details and potential supervision.
Note that though Empirical Modelling has been developed exclusively at Warwick, and is not a recognised practice in the software industry, the intellectual and technical skills that it develops are useful and transferable. These include basic skills in procedural programming that are sometimes neglected when introducing novices to object-oriented programming. The more specialised technical projects may also involve learning about other languages, such as C and tcl/tk, and new subject areas such as educational technology. Please bear in mind though that the best EM projects are not necessarily the most technically sophisticated. Many highly successful projects involve an extended process comprising a very large number of relatively simple modelling steps; what makes them distinctive is the quality and subtlety of the development process and the extent to which the modeller's imagination is engaged ever more and more fully as the modelling activity develops.
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 2007-8. A useful general introduction to Empirical Modelling that touches on all aspects of its broad agenda is Karl King's recent MSc thesis Uncovering Empirical Modelling. Karl did a third-year project on an Empirical Modelling theme in 2003-4 and stayed on to do his MSc the following year.
The most topical approach to EM tool development is an Open Source project that aims to integrate Js-EDEN (see below) with CADENCE. This project has attracted the interest of several former students who had a significant role in developing the current EM tools, and is being led by Tim Monks and Nick Pope. Contributing to this work could either involve small-scale but novel prototyping exercises for proof-of-concept or involve addressing larger technical projects similar to those that can be found here which were first conceived with Cadence alone in mind.
Many of the projects listed here date from a few years back, and in some instances are no longer so topical - for instance, the web-enabling of EDEN (see 1.4) is now well-advanced, as represented by Web EDEN (from 2008) and JsEden (2011). They still give useful hints as to what R&D directions may be worth pursuing however. In many cases, new possibilities for exploratory studies are opened up as a result of the new features afforded by Cadence and JsEden.
1. Refinements to Tools
1.1 Implement DoNaLD using the Agent-Oriented Parser
DoNaLD is a definitive notation 2D line drawings and is used in the tkeden tool. The current implementation is in the C language and the language parser code is generated using the Bison parser generator tool. The Agent-Oriented Parser (the "AOP") is available in the tkeden tool for the development of notations. The aim of this project would be to reimplement the DoNaLD notation using the AOP, eliminating the dependence on an aging C parser (with its own set of problems!). As a supplementary goal of your implementation of the DoNaLD definitive notation, you may wish to consider addressing some of its limitations as a line-drawing notation, such as the absence of layering. It might also be useful to critique the AOP, examining its technical limitations and efficiency issues, and suggesting ways to address them.
Variants of this project might involve making a similar reimplementation of Scout, the other principal notation directly supported by the EDEN interpreter using the C language, or using the AOP to implement 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. A prototype implementation of the ARCA parser exists, but is not as yet fully integrated into EDEN.)Yet another possibility might be to apply the strategy used to implement the AOP in EDEN to implement a traditional LR-parser - such as Bison generates for DoNaLD - directly in EDEN.
1.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.
1.3 Empirical Modelling Interaction Analyser
The principal tool for Empirical Modelling - tkeden - has a simple interaction logger in the form of a command history. It is hard to analyse how a model has been constructed by just looking at this history. For instance, it is hard to locate similar patterns of interaction when they are scattered across the entire definitive script. What is more, a sophisticated analysis of activity is essential in order to turn the raw interaction data into useful information. The aim of this project is to implement a better logger for tkeden, together with an log analyser. Potential extensions and applications for this project include:
- Making use of the log analyser to analyse collaborative modelling interaction history in dtkeden.
- Replaying the interactions as they have been captured. It would be desirable to allow different replay modes - e.g. fully automated, partly automated, pause and resume.
This project would help to develop a variety of skills, to include: Empirical Modelling, C/C++, Tcl/Tk, pattern matching.
1.4 Empirical Modelling over the Internet
One obstacle to the wider adoption of Empirical Modelling is the overhead involved in downloading tkeden and appropriate models, and the subsequent difficulty for remote and uninitiated user-developers of knowing how to go beyond the most naive and obvious kinds of interaction with them. Making it possible to use tkeden directly as an interactive utility available over the Internet (similar to the Google spreadsheet utility) might help to generate wider interest, and open up new possibilities for educating and interacting with external users.
1.5 Developing a flexible interface for the Eden interpreter
In the present version of the eden interpreter, the organisation of screens buttons is described in tk/tcl, and accordingly is relatively hard to reconfigure. Since the development of the Gel notation by Antony Harfield, it has become possible in principle to configure an interface in an open fashion by using a definitive notation that is itself being interpreted by eden. One existing application of this technique can be found in the presentation environment, developed by Antony Harfield as an exemplar for Gel, and illustrated in use in graphicspresHarfield2007. The idea behind this proposed project is to exploit the scope for reconfiguring interfaces that Gel affords more fully. This could (e.g) help to make it easy for the modeller to set up an initial configuration for the eden interface so that is suited to some specific demonstration or development role. More radically, and in keeping with the broader objectives for open model-making in EM, the configuration of the eden interface could be dynamically changed accorded to context, either to reflect the current role being played by the modeller (e.g. as in 'debugging' vs 'executing' vs 'explaining'), or to reflect different modes and situations relating to the model currently under construction (e.g. changing the visibility, size and configuration of windows according to what observables, dependencies and agencies are topical in a specific situation).
1.6 Developing a JavaScript implementation of the Eden interpreter
In his MSc dissertation (2011), Tim Monks describes an EDEN-like environment that includes a prototype implementation of the EDEN interpreter in JavaScript. There are many potential advantages in pursuing this style of implementation for EDEN - not least because of the considerable difficulty of maintaining the current interpreter, which makes heavy use of tk/tcl libraries.
2. Communication and Maintenance of EM Models
2.1 A demonstration tool for Empirical Modelling
DemoMaker is a tk/tcl tool for use in conjunction with tkeden. It is a prototype that allows interactions with an EM model to be recorded and replayed. This is particularly relevant where the documentation of EM project work is concerned, since it is often hard to reproduce 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.
2.2 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..
2.3 Support for teaching Empirical Modelling
The EM principles and tools can be difficult to grasp if you have no one to introduce them to you. Various presentation-style models exist that are useful for the beginner. More introductory models could be developed, using eden, to educate the beginner in using EM principles and tools. The EM presentation environment, created by Antony Harfield, provides a suitable platform for such development. (See graphicspresHarfield2007 for an example of its use.) This project will be a way to acquire skills in Empirical Modelling and to learn about educational technology.
2.4 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. Documentation would involve a study of how the LSD notation can be used to give an account of potential agent interactions, and developing an interface for constructing and storing LSD accounts in conjunction with models.
3. Applications of EM
3.1 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.
3.2 Using large displays in Empirical Modelling
For those of us old enough to have made use of the large display areas afforded by arrays of blackboards, the space available on electronic devices is by comparison frustratingly small. The modes of interaction with that space are also much more restricted in many respects, especially where opportunistic on-the-fly annotation and extension of display artefacts is concerned. In principle - subject to technologies for creating much larger display areas becoming available - EM has potential to address the issues of managing and organising large spaces in a flexible manner and of allowing a hybrid mode of interaction that combines the qualities of automated and manually developed display.
One way of coming to understand the issues involved in exploiting EM in managing large displays is to carry out a variety of experiments. Ideas for suitable experimental activities that could make effective use of large displays (such as the big screen in CS101) include:
1. Exploring models and visualising the structure of models
2. Learning about EM, as a tool for introducing EM in an integrated environment
3. Demonstrating models as in the EM Presentation Environment.
Activity of this nature could be complemented by appropriate tool development, but this is not essential. Much can be learnt by experimenting with existing tools and environments.
3.3 Language-learning artefacts
Computer resources to support language learning are common but many follow a specific preconceived structured approach to introducing vocabulary and grammar. Using Empirical Modelling principles, you could build some language-learning artefacts that encourage language aquisition through exploring some artefact (in a way that is perhaps closer to language learning in real life). One of the key principles might be implementing dependencies to connect interactions with an artefact with combinations of words, as is illustrated in an elementary fashion in Variation 9 in the JUGS poster that can be found in kaleidoscopeBeynon2005 .
3.4 Supporting Collaborative Drawing with Wii Remotes
This project would combine and consolidate upon various prototypes that have been constructed by EM research students in recent years. Karl King has developed DrawScout and DrawSlide as a part of his MSc research in 2005. Eric Chan has extended Karl's model to allow a group of modellers to construct Scout components collaboratively in a distributed environment. Antony Harfield has developed tkeden support for Nintendo's Wii Console's Remote Controls. This makes it possible for modellers to use Wii Remote Controls as input devices in the tkeden (or dtkeden) environment.
The proposed project would provide support for a group of modellers equipped with Wii Remote Controls as input devices to create drawings collaboratively through making donald or sasami definitions both in a distributed environment and in a co-located environment (e.g. using the wall display in CS101). Relevant skills that will be developed through tackling this project are Empirical Modelling, C/C++ and Tcl/Tk.
3.5 Empirical Modelling for multi-agent simulations
Empirical Modelling is in principle well-adapted to modelling the interactions between agents with reference to matters of perception and interpretation. Where this has been successfully exploited to date, the focus has been on a relatively small number of agents and on a subtle analysis of the observables and dependencies that mediate their interaction. Significantly this analysis has not been carried out prior to the model-building but has been developed in conjunction with the model-making activity. (Contrast class-based object-oriented programming environments, which are well-suited to constructing multi-agent simulations involving large numbers of agents whose interactions obey fixed and often simple rules, and where the interest is in emergent behaviour.)
In order to break new ground in this area, it would be useful to build on what has been achieved in models such as antnavigationKeer2005 and roadtrafficStein2005 . Suitable subjects might be detailed modelling of individual roles in a team game context (such as that of a goalkeeper, a tennis umpire or a fielder in cricket). Improvements in representing the interface to such an agent might be achieved through exploiting visualisation using the Sasami notation and the use of Wii remotes for interaction. It would also be of interest to operate in domains where the scope for evolutionary development in EM is fully exploited, as in constructing open-ended games where the rules can be modified on-the-fly. One possible specific application, such as has been conceived by researchers at Joensuu Finland in connection with their ongoing work in Africa, might be the development of an educational game to simulate the potential impact of AIDS on a small community.
3.6 Distributed implementation of existing tkeden models
The development of dtkeden - a distributed variant of tkeden - makes it possible to improve the structure and the performance of many 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.
3.7 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. The aim of this project is to explore the potential of the LSD Engine by adapting existing scripts and developing new ones. Some initial work would be required to recompile the existing version of the LSD engine so that it executes under a more modern Windows operating system, and to further explore and document its capabilities.
3.8 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).
3.9 Interfacing to an interactive FRep modelling system
The aim of this project is to explore the possibilities for integrating EM tools (e.g. such as Cadence, EDEN or JsEden) with a free state-of-the-art geometric modelling system that is based on 'function representation (FRep)' principles. This is the fully functioning interactive FRep modelling system called Symvol for Rhino - Maker that has been issued by the Uformia company in Norway. The system is currently implemented as a plug-in to Rhinoceros, but will be a standalone application in the future. This project will involve collaboration with Alexander Pasko and Valery Adzhiev of the HyperFun project (www.hyperfun.org) at the National Centre for Computer Animation (NCCA) in Bournemouth.
4. EM Principles from a Computer Systems Perspective
4.1 Modelling with Nintendo Wii Controllers
A modified version of the Empirical Modelling tool tkeden makes use of any number of Nintendo Wii Controllers as input devices. Each Wiimote offers button, 3D acceleration and 2D pointing information that can be interpreted in the tkeden environment. There are many possible projects that could benefit from Wiimote support, for example:
Prototyping games: The Wii emphasises games that are simple and addictive. Investigate the potential for using tkeden for prototyping games, using the Wiimote.
Using the Wiimote for learning physical skills: The Wiimote can add a physical aspect to learning a skill that a mouse and keyboard cannot achieve. Investigate the potential for using tkeden and Wiimotes for modelling situations where a physical skill is involved, for example, kicking a football or taking a penalty kick.
We welcome your own imaginative ideas for using Wiimotes in Empirical Modelling.
4.2 "Real-time" (RT) tkeden
We can link tkeden to some hardware e.g. 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. Relevant issues to be considered include: how to specfiy real-time aspects of dependency, and how to adapt the tkeden tool for real-time use.
4.3 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.
4.4 Implementing a karaoke system
A karaoke system provides media management, media playback, synchronised lyric and/or sub-title display, remote control extension, etc. To develop a karaoke system using EM principles and tools is a challenging project. You will have to develop some API functions for the tkeden environment using the C programming language, and then develop the karaoke system using tkeden.
5. Reflection on EM
5.1 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 (cf. pjawnsMartin2003) 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.
5.2 Comparison and evaluation: EM principles and tools in context
There are many commercial packages and tools that have points of connection with EM. They include general-purpose tools such as Excel, VB, Perl etc and more specialist tools such as Mathematica, Matlab, Geometer's Sketchpad, Labview, Imagine-Logo, AgentSheets, Sibelius, Sonar etc. 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. These case-studies would include (relatively small) applications of some of the above tools that - typically, but not necessarily, through the development of EM artefacts 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.
5.3 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 tools, together with proposals for how these can be redeemed through reworking models or refining tools.