Agent-based Modelling with Statecharts

Studying the behaviour of spatially distributed systems using collections of interacting Statecharts

Contents:

• Team
• Motivation
• Proposal/Requirements
• Design/Models
• Implementation
• Experiments
• Conclusions
• References
• Presentation
• Interesting Asides

Team

Nabeelah Ali is the sole team member for this project.

Motivation

Emergent behaviour is the complex behaviour and patterns that arise out of many simple interactions. Examples of emergent behaviour can be seen everywhere: for example, in the flocking of birds, ant colonies, and weather patterns. In the case of the flocking of birds, birds are agents that follow simple rules - the pattern that emerges is the familiar V shape.

This project will be concerned with using Harel Statecharts to model the behaviour of individual agents. Statecharts are a modelling formalism that allow superstate and concurrent states, allowing for detailed description of agent behaviour.

For this project, the spreading of disease in a spatially-distributed system will be studied.

Proposal/Requirements

The system will be a cellular automaton, with the behaviour of each cell/agent specified by a Statechart.

The requirements of the system are as follows:

• The behaviour of individual agents can be specified with a Statechart.
• The Statechart can then be imported into a 2D layout.
• Collections of Statecharts can interact in a 2D layout.
• Feedback on the system's state is provided to the user graphically.
• The system should be a discrete-event system, as updates are triggered by Statechart's time advances and event triggers.

Design

I propose to use the funcitonality of AToM3 to create the Statecharts that will model the behaviour of the agents (in this case of disease-spreading, the agents are people). Statecharts can compile through AToM3 to Python code, whereby the Statechart becomes a class whose functionality can be used.

The second part will then be to create a 2D spatial layout that allows the agents to move about it. Proximity to other agents will dictate what events are triggered. These triggered events are broadcast to the Statechart, which will react by changing states or completing whatever other behaviour is dictated. This part will be coded in Python, using Numpy for array-handling, and pygame for visual relaying information back to the user.

Implementation

A ZIP | TAR of the project files can be downloaded. To run the files, Python, as well as the numPy and pyGame extensions, are needed. The main file is simpleDisease.py, run this to run the simulation. It is not recommended that it be run through IDLE, as IDLE and pyGame don't much like each other. Instead, the file should be run via the UNIX command line, DOS Prompt on Windows, or a more pyGame friendly editor like drPython. It is liberally commented to allow for easy reading and self-documenting.

The 2D layout for the agents is implemented as a numpy array. When agents reach one end of the canvas, the continue on the other end. The agents move one square in a random direction when the move action occurs on their corresponding Statecharts.

The script initially asks the user to input values for several variables relating to the simulation. The GUI the intializes and the simuulation runs for the specified time period.

Here is a screenshot of the program running, with grid size set to 30x30 and 100 agents.

To see the program running without needing the proper extensions, in an AVI format, view a demo here[9.55MB]. At the end of the simulation, the script prints out the total number of agents that are healthy, infected and dead.

When creating Statecharts to model disease behaviour, the following triggers and actions can be used:

Triggers:

AFTER(x)   # Time-delay. Replace x with appropriate number.
start      # Occurs when the Statechart is initialized.
infection  # Occurs when agent is next to an infected agent.
immunized  # Can be manually triggered to immunize agents.
healthy    # Broadcast when makeHealthy() runs.
dead       # Broadcast when die() runs.
infected   # Broadcast when makeInfected() runs.

Actions:

controller=[PARAMS]       # Must be used in the first transition.
controller.move()         # Move in a random direction.
controller.makeHealthy()  # Change state ->healthy.
controller.makeInfected() # Change state ->infected.
controller.die()          # Change to 'dead' state.
controller.bury()         # Remove agent from screen.

To create a Statechart, use the DCharts meta-model in AToM3. After drawing up the Statechart using the permissible triggers and actions listed above (and make sure to include the trigger start with the action controller=[PARAMS] to initialize the simulation properly), click on the generate .des button. Save the .des file in the same directory as simpleDisease.py, then when asked whether to compile the DES file immediately, click 'Configure compiler'. Select the Python path, and then press OK. In the dialog box that follows, type in -l python --ext and then click OK. Done!

Here is an example of a Statechart that determines disease behaviour for an agent:

Experiments

Three experiments were carried out, to view the effects of:

• Population density: how the disease spreading is affected by people:number of grid unit ratio.

Three simulations were run, each with grid size 30x30 and initially probability of being infected 0.2. Both simulations were run for 5 minutes. In one, 50 agents were present, 150 in the second, while 400 were present in the third to simulate overcrowding. The same disease Statechart was used for both (the Statechart presented at the end of the last section).

Simulation	Total Pop	Healthy	Infected	Dead	% of Pop. Affected	Screenshot
1	50	36	0	14	38.8	click
2	150	24	0	126	84.0	click
3	400	0	0	400	100	click




• Changing the time required to be cured of the disease: In a real-world scenario, this would model the effects of treating affected patients sooner rather than later.

The same parameters were used as Simulation 2 above. The only different is that the time-advance required to go from infected to healthy was changed from 15s to 7s.

Simulation	Recovery time (s)	Total Pop	Healthy	Infected	Dead	% of Pop. Affected
4	7	150	149	0	1	< 1
5	15	150	24	0	126	84



• Changing how the disease spreads

To show the effects of how dramatically a simple change can affect the effects of the disease, in the following model, in Simulation 7 the Statechart makes agents continually susceptible (even after recovering from the disease they can catch it again), while in Simulation 8, after recovery, the agents are no longer susceptible.

Simulation	Total Pop	Healthy	Infected	Dead	% of Pop. Affected
7	150	24	0	126	84.0
8	150	78	0	72	48.0

Conclusions

The advantages of combining a Statechart with cellular automaton formalism include:

• The ability to define detailed behaviour for agents. The complexity of the behaviour and states is not limited. At the same time, one can observe the behaviour that arises from combining many agents with complex behaviour.
• The behaviour of the disease can be modified without having to change the Python script. AToM3 is a graphical modelling tool that can be used to create the statecharts that define the behaviour of each agent.
• Easy and quick to vary parameters and view changes on the behaviour of the system.

The merging of statechart + cellular automaton formalisms gives rise to a new formalism than can be extended to many fields to view the effects of agents with complex behaviour.

References

David Harel, Statecharts: A visual formalism for complex systems. Science of Computer Programming, 8(3):231–274, June 1987.

Presentation

Download a copy of the presentation in PDF format.

Interesting Asides

A mushroom take on John Conway's Game of Life [click]