Simulating Crowd Behaviour with Multi-Agent Systems
Paul Bradley
April 2007
Abstract
This report details research into the field of crowd simulation with particular emphasis upon the use of multi-agent systems as a means to improve earlier work. An algorithm developed by Victor Blue and Dr. Jeffrey Adler is taken and extended to include an increased number of factors and converted to a more decentralised, multi-agent approach. These algorithms are then implemented with the JAS toolkit.
This report also details a first hand field study carried out to collect evidence of real world crowd situations. An empirical analysis is then carried out on both the simulations and field study to draw conclusions as to the success of the algorithms implemented.
Acknowledgements
For their particular help and guidance throughout this work I would like to thank the following;
· Professor Chris Jones, project supervisor for help and guidance throughout.
· Michele Sonnessa for particular help with understanding the JAS
· Victor Blue and Dr. Jeffrey Adler, upon whose research a significant portion of this project is based.
2. Current Methods of Crowd Simulation
2.1 Blue and Adler’s Simulation
5. Blue and Adler Implementation
5.1 The Blue and Adler Rule Set
5.2.1 Building of the environment in CrowdSimModel
5.2.2 Building of actions in CrowdSimModel
5.2.4 Overall algorithm design in CrowdSimAgent
5.2.5 Collection of Statistics
6.1 Areas of expansion on Blue and Adler
6.3.1 Building of events in CrowdSimMultiAgentModel
6.3.2 Algorithm design in CrowdSimMultiAgent
7.2 Comparison of Algorithms with Field Study
8.2.2 Success of Implementation Method
1. Introduction
In recent years an emerging field of research has become the concept of ‘social simulation’. This area of interest is concerned with modelling to better understanding circumstances and environments that can occur within everyday life and more importantly the interaction of people within these environments.
This project will specifically focus on a field of study known as crowd simulation. Primarily this area is concerned with the movement and flow of pedestrians or “agents” within a specific crowded environment or location. There are a great number of reasons why such an area should be given a significant level of analysis and warrant the development of simulations, primarily due to the high number of potential stakeholders in the results and conclusions that can be drawn.
In modern society there are a high number of circumstances in which we see large numbers of people converging in one location. Here, we see individuals attempting to move through a finite space such that each individual can best meet their own needs of achieving their desired journey goal as easily and quickly as possible. Such environments can, and indeed have, led to great disaster and often due to no other external factors other than a sheer volume of individuals and the restricted space in which they are located.
Sporting events are a perfect example of such a situation where a knowledge and understanding of crowd dynamics can be advantageous. At the Hillsborough football ground in Sheffield, UK in April of 1989, 96 people were killed and 766 were injured (Hillsborough Justice Campaign, 2004) due to a high density of people in one section of the stadium being crushed. An investigation later found that on the day of the football match the entry turnstiles were being used to capacity and a high number of fans were building up outside. A decision to open a gate usually only used for exiting fans meant there was a sudden influx of people to one small part of the ground. Police would normally have directed fans to other entrances once this area filled up but their failure to do so on this occasion led to spectators at the front of the stand being pressed against fencing and the crush ensuing. It was the actions of the police and the design of the ground that were blamed most on that day, a better knowledge of crowd behaviour could have helped the police and stadium architects to have better foreseen and ultimately dealt with such a situation.
Emergency situations also lend themselves to a heightened state of urgency for all those involved and can often lead to disaster. In May of 2004 at least 6 women and many more were injured after a stampede ensued at a clothing factory in Dhaka, Bangladesh. What was only a minor fire caused a surge of workers to head for stairways and fire exits causing a fatal crush (Crowd Dynamics Ltd., 2005). This is a perfect example of a situation where building infrastructure that normally operates adequately falls down significantly when used in a way that differs to normal usage and as such was perhaps not considered by architects.
Clearly, a poor understanding of crowd movement can have a number of consequences ranging from the tragic to the highly undesirable with regard to satisfactory time scales for certain movement and capacity. These circumstances often occur through no misconduct of any individuals within the crowd but merely the dynamics that occur when each individual has their own intentions and needs that they wish to fulfil over and above those around them.
However, through analysis of both people and the circumstances in which they move, it can be possible to build a computer simulation of such situations. Through testing of this simulation with a range of data to represent various environments, it can be possible to draw both empirical and more qualitative conclusions.
My key objective is to develop my own simulation of the movement of a large number of pedestrians that can act as a means for collection of statistical data for a range of user-defined circumstances.
I hope to initially study current methods of simulation. I will look at the range of implementation methods, the advantages and disadvantages of each approach and how they differ. I also hope to conduct a field study into crowd behaviour by collecting first hand data of naturally occurring crowd movement. This research and study will then be used to aid the design and implementation of my own simulation. Finally I will conduct experiments upon my simulation to allow for direct statistical comparison with both the field research and other simulation methods.
2. Current Methods of Crowd Simulation
A number of papers already detail methods by which crowds and more generally pedestrian flows can be modelled with computer simulation.
One such method is that of a ‘social force’ model proposed by Helbing and Molnar (1995), this focuses on an attempt to give each pedestrian modelled an ability to determine their behavioural strategies based on experience and to act in a way that each pedestrian feels is the best way to deal with a particular situation. This came after an analysis of crowds suggested that although they may seem chaotic, each individual actually acts in a fairly predictable way and this could be represented through equations of motion. In this sense, all pedestrian motion can be regarded as being governed by a ‘social force’. This method has the advantage of being able to allow for a very wide range of variables, inherently present in any real world situation. The model also treats the simulation variables in a less discrete way to other simulation methods – again, in a manner more akin to actual human behaviour. However, this causes a significant downside in the form of a high computational overhead and an increased difficulty in implementation.
Hoogendoorn and Bovy (2000) propose a gas-kinetic model. This approach is similar to that of a social force model in that equations that describe the motion of each individual pedestrian are formulated. More specifically however, these equations relate to explicit attributes of the agent and how it interacts with those around it, specifically in terms of acceleration and deceleration as well as a changing angle of movement due to pedestrian interaction. Again, such a solution can become quite complex and it is highly dependent on the level of detail to which one models each possible interaction. An increased difficulty in implementation and high computational overhead are also issues to consider, balanced by an increasingly accurate simulation with the possibility to be expanded to consider a wide range of influences.
However, currently very popular methods are those that harness the power of cellular automata. Blue and Adler (1998, 2000) have produced a number of papers developing their algorithms for movement of groups of pedestrians in the discrete lattice world of a cellular automaton (CA). Proposed in these papers are a set of discrete and relatively simple rules that are implemented on a two dimensional grid of possible locations for pedestrians. The overall concept of CA will be explored in more detail later. This has become a very popular method for a number of reasons. Primarily, it is a concept that can be explained and understood with ease and as such allows for many others to develop their ideas in further research without a large amount of initial work. CA solutions also have the ability to accurately simulate situations with a surprisingly small ‘rule set’ for how each individual within the scenario behaves based on the location and behaviour of those around them. Other benefits of this system are a relatively low level of computational overhead and generally speaking, ease of implementation. Disadvantages of such an approach, as commented on by Bierlaire et al, 2003, can be that discrete rule sets implemented can appear restrictive and not complex enough to accurately represent the diverse real world. It is also argued that a two-dimensional lattice environment does not do enough to accurately represent the non-discrete scenarios, movements and people involved.
Some implementations also consider harnessing the power of a multi-agent system. Dijkstra et al, 2001 used such a method combined with cellular automata as they believed “a multi-agent system offers the promise of simulating autonomous individuals and the interaction between them”. The fundamental concept behind a multi-agent system is that each agent is programmed independently of any other and behaves based on its observations of the environment and behaviour of other agents around it. For this reason it can help to directly represent concepts in the real world such as differing goals amongst agents and emergent behaviour of a complete system based on a high number of interactions of agents with relatively small sets of rules. I will discuss the concept of a multi-agent system in more detail later.
2.1 Blue and Adler’s Simulation
Through earlier research I have been particularly interested in the work of Blue and Adler. Their papers describe very prescribed methods of crowd simulation through the use of CA. The idea of implementing my simulation based on this concept is very attractive for a number of reasons. The relatively low levels of computational complexity as explained earlier lend themselves to a self contained desktop application. As I hope to use the simulation to run experiments and collect a range of statistical data, an ability to quickly generate and execute different models is highly desirable. I believe a lightweight, less demanding implementation method can help in this respect. I am also particularly interested in the concept of a multi-agent (MA) system. This is an idea that is not explored in the Blue and Adler approach but that I feel deserves analysis, especially in comparison to other methods. It is also a way in which I feel the standard CA approach can be improved and help answer to some of its critics.
I will now take a closer look at the concepts of cellular automata and multi-agent systems.
2.2 Cellular Automata
Cellular automata are a useful method of allowing very complex and not easily predictable scenarios to be formed. On the face of it, they are a very simplistic model, but when used under the right circumstances can represent diverse emergent behaviour.
The basic premise is that a two-dimensional lattice is used to represent a discrete number of locations. Each of these locations can then be in one of a number of states, typically only two, at any point in time. Then, over time, a rule set exists that determines how the states of each location in the lattice change, depending on the state of neighbouring cells. Crucially, every cell follows the same rules for updating. This has the beneficial effect of a small set of rules giving rise to potentially complex outputs as cells interact with one another. As Blue and Adler (1998) put it;
“Only the local rules and the sequencing of their use are coded, leaving the many autonomous interactions on the cell matrix to create the emergent macroscopic results.”
One of the most popular implementations of CA is known as the Game of Life (Callahan 2005). Here, a simulation is modelled to show how fascinating macroscopic patterns of behaviour can occur from a very small set of rules.
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
3 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
4 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
5 |
|
|
|
|
|
|
Figure 1. Game of Life Cellular automaton
showing evolution of a design over 5 generations
Figure 1 represents a Game of Life implementation and how a basic shape ‘evolves’ over four time units before returning back to its original shape. Each time until is known as a generation in the evolution of the behaviour. This layout has the effect of the shape ‘walking’ across the screen as it loops through these generations, at each step following the same rule set as to how each cell should behave.
The Game of Life stipulates that each cell can only be in one of two states; populated or unpopulated, whether a cell is populated or unpopulated in the next time frame depends solely on the current state of the 8 adjacent cells or ‘neighbours’ surrounding it. The rule set used in the Game of Life is as follows;
For a space that is 'populated':
Each cell with one or no neighbours dies, as if by loneliness.
Each cell with four or more neighbours dies, as if by overpopulation.
Each cell with two or three neighbours survives.
For a space that is 'unpopulated':
Each cell with three neighbours becomes populated.
It can be clearly seen this is a very compact rule set, yet when executed, the range in macroscopic patterns that arise is truly fascinating.
One deviation from the pure concept of a CA that many simulations need to make is the idea of each occupied cell representing some ‘agent’ which at every time step “moves” as opposed to merely existing or not. In the Game of Life example, cells become occupied or unoccupied based on present circumstances, with each occupied state merely represented with a coloured cell but with no real concept of an object which changes position. In a situation whereby occupied cells in fact represent an object in the physical world, one must ensure that this is adequately represented so that conservation of agents is maintained. This also ensures the movement of an individual agent can be monitored as each can be programmed to have knowledge of its previous ‘movements’, albeit more specifically knowledge of previous locations occupied.
Later I will look specifically at how Blue and Adler used CA and specifically the rule set they implemented.
2.3 Multi-Agent Systems
Multi-agent systems (MAS) are at their heart, as stated by Wooldridge (2002), a method of enabling a number of ‘agents’ to work within an environment so that each can fulfil their own, potentially differing goals while at the macroscopic level achieving some resultant overall behaviour. Sycara (1998) states that;
“The characteristics of MASs are that
(1) each agent has incomplete information or capabilities for solving the problem and, thus, has a limited viewpoint;
(2) there is no system global control;
(3) data are decentralized;
(4) computation is asynchronous.”
Wooldridge also specifically defines an agent as being;
“…a computer system that is situated in some environment, and that is capable of autonomous action in this environment in order to meet its design objectives.”
There is some debate over what exactly constitutes an agent, for example, in the instance of crowd simulation we are more concerned by each agent representing a human pedestrian as opposed to a complete computer system. However, it follows clearly that in this instance the environment is the region within the boundaries of some simulated area in which the pedestrian can move. Similarly, the autonomous action of a pedestrian is the human’s ability to perceive and react to its surroundings and design objectives will represent an individuals desire to traverse a particular scenario to reach their desired location.
Wooldridge also explains that the power of a multi-agent system comes from each agent’s ability to sense input from its environment and choose an appropriate action based on this information. This action will itself affect the environment and therefore its future actions and the future actions of other agents. For this reason every agent can be seen as having partial control or influence over the environment and indirectly its own behaviour, but none will have complete control. As Sycara states above, another key feature is the completely decentralised nature of execution. Every agent has equal control over its behaviour and this may be influenced by other agents but never controlled by them.
A simple example of a single agent could be seen as a thermostat. This device can sense its environment and perform an action to help control that environment. In this instance detect temperature as too high or too low and turn heating on or off accordingly. The close relationship between artificial intelligence and the MAS concept can be seen here in a very basic way. The thermostat could be regarded as autonomous as it requires no human intervention; it is merely programmed to know how to react to certain environments in order to fulfil its design goals.
When specifically considering pedestrians within a crowd simulation it is clear how a multi-agent system could provide an interesting paradigm in which to develop a system and analyse its effectiveness. In this instance each agent would be acting selfishly to meet their own personal goals as opposed to a unified group of agents working together for a single objective of the overall system. Each agent will have some limited knowledge of the environment, that is, an awareness of other agents in its local vicinity but no universal understanding of all other agents. This will allow each agent to plot what it believes to be the most advantageous future action for itself based on localised observations and regardless of the global behaviour.
2.4 Research Conclusions
I have analysed a number of current methods for simulating crowd behaviour and researched a few of the techniques in greater detail. This has helped me to understand the advantages and limitations of these approaches and help me to decide upon a method by which I hope to analyse this problem.
As earlier explained I have an interest in the Blue and Adler approach and feel an ability to extend this model and enable comparison between implementations and field work is appealing. It is highly beneficial that Blue and Adler specify the exact ‘rule set’ upon which their implementations are based. A direct development of their simulation will therefore be possible and ready to be tested under the same conditions as my own developed system. I am of course aware of the criticism that some have for CA based models, as discussed above. However, I believe that from a research point of view, the discrete set of rules upon which the behaviour of CA are based allows for easy comparison of algorithms based on specific attributes and behaviours. One can implement a specific new characteristic into the rule set and see how this affects the overall behaviour.
Blue and Adler’s approach outlined above has centralised control. That is, when implemented, every location on the lattice is visited and the rules for movement are implemented on those containing pedestrians. Once new locations have been found for all pedestrians, the lattice is updated to show this new arrangement. This level of control can be criticised for being too authoritative and unrealistic, in a real life scenario there is no controlling force telling each individual where to move next. For this reason, I am particularly interested in the concept of a multi-agent system to better represent individuals within a simulation that have their own needs and requirements. These agents will then attempt to find a best method for fulfilling those needs based only on their own ability to perceive and interact with the environment. One other criticism could be that the Blue and Adler rule set has a high reliance on chance to solve any decision where an agent believes two choices are equally good. I hope to extend this part of the simulation to look at other factors that Blue and Adler don’t consider and use those to aid agent decisions. I will later state and explore the Blue and Adler rule set itself in more detail.
3. Field Study
3.1 Collection of Data
Before attempting to better understand this particular social phenomenon I believe it is essential to conduct research to specifically look first hand at examples of crowd movement. I felt it highly useful to be able to both confirm work undertaken by others as well as investigate my own aspects of what I hoped to simulate. Being able to observe the movement of pedestrians first hand has a number of benefits. Fundamentally, one can use the data collected for two key purposes – to help formulate a model upon which a simulation is based or to help ratify an already existing or newly developed model. Observing the behaviour you hope to simulate allows one to develop a better understanding for the roots of overriding emergent behaviour as well as the origins of certain attributes of other simulations.
A useful viewing position on Queen Street, Cardiff was found to view the movement of pedestrians. The location in question was particularly helpful as it is a part of a road where pedestrians tend to move in just two opposing directions, either directly up or down the road. This type of movement, as opposed to a more complex form with a greater variation in direction and goals for each agent, allows for easier analysis of specific aspects of behaviour.
Over the course of an afternoon, I
filmed a number of fixed camera sequences with all external variables kept
constant to the best of my ability – including the density of people and
weather conditions that could affect behaviour. With the use of a fixed
landmark in the form of the paving slabs over which the pedestrians were
walking, I
|
had a useful reference point to calculate the distance travelled within
particular time steps.
Figure 2 shows the widths of paving slabs superimposed for clarity. The figure shows the same scene at one second intervals from each other and five particular pedestrians tracked between each time step. Considering negligible movement to the side, the displacement of each pedestrian at each time step can be easily calculated from the paving slab landmark.
Figure 3. A frame from Cardiff, Queen Street with pavement slabs superimposed.
For later analysis concerning comparison of pedestrians’ speed and density it is also useful to accurately calculate the average density of individuals in this scenario. Figure 3 shows the paving slabs superimposed in both directions to allow for an estimation of the total size of the area in question, compared to the number of individuals within it. Here, the central area is calculated to be 7.7m x 6.3m, with a total of 15 people present within this area at that time, an estimate of 0.3 people per square meter can be calculated. This process was repeated for a number of other moments within the film sequence and an average density of 0.43 people per square meter calculated.
A second field study focused more closely on the behaviour of a large crowd. A useful viewing position was found to observe a set of main gates at the Millennium Stadium, Cardiff. Once again, a static camera filmed an approximately 15 minute sequence observing individuals exiting the stadium. The match in question (Cardiff Vs Leicester, October 29th 2006) was not attended by a capacity crowd, and as such there was a significant variation in the number of individuals leaving from different exits.
Figure 4. View of individuals exiting the Millennium Stadium, a significant difference in density of the crowd can be seen either side of a central barrier.
Figure 4 shows clearly this variation, with gate 2 to the right dispelling a much higher volume of people to gate 3 in the centre. This variation allows for an interesting study into the variation in pedestrian speed with respect to the density of their surroundings.
Figure 5 shows the tracking of a number of pedestrians over 3 time steps of 4 seconds each. Here, each coloured line shows the movement of one particular individual with the coloured circles on the lines showing their specific location at each time step.
Figure 5. An example of individuals tracked over three time steps, each four seconds apart. Each coloured line represents one pedestrian and each coloured dot represents the pedestrian’s specific location at a time step.
3.2 Field Study Results
Prior to my development of a simulation I will focus my analysis of collected field data on helping to understand the connection between average speed of pedestrians against the density of their surrounding area. I will also perform further analysis after implementation of a simulation to help ratify aspects of what I hope to develop.
Figure 6. A diagram to aid the estimation of crowd density in the two regions by calculating a number of localised densities and obtaining an average. * shows an area obscured and so discounted from the study
Figure 6 shows clearly the two differing areas of density, segmented into areas of a useful size so as to estimate local density and obtain an average for that area. The number of individuals within each area was found, to eliminate confusion with pedestrians in more than one segment, the area the majority of the top of a head was considered to be in was the area in which they were counted. Each square represents an area of 1.9m2 and so for the lower area of density an average occupancy of 4.6 people in each area corresponds to a density of 2.4persons/m2 and similarly for the higher density region a value of 8.4persons/m2.
With the aid of my tracking diagram shown in Figure 5, I can now develop an estimate for pedestrian speeds in these two areas. With the knowledge that each location tracked in that diagram took place at four second intervals and with the use of a reference to estimate a scale of 0.6m for every 1cm, average speed was easily calculable, full raw data can be found in Appendix A1. Within the less populated region an average speed of 0.45m/s was found, contrasted with 0.20m/s in the higher density area.
A similar analysis was carried out to estimate average density and speed of pedestrians in the Queen Street study. Here, it was possible to observe a much higher range of individuals and so better analyse the range of speeds acquired, the raw data here can also be observed in Appendix A1. It can be seen that an average density of 0.4persons/m2 was found and an overall average speed of 1.10m/s. Each of the 36 samples acquired were tabulated such that the frequency of occurrence of speeds within each range were collected and a graph to represent this distribution could be formed (Appendix A2). A standard deviation of all the speeds collected of 0.17m/s was calculated. This standard deviation concurs well with studies by Fruin (1971) who estimated a value of 0.15, however it has been quoted to be as high as 0.3 (Older 1968). Lovas (1994) quotes an average speed of pedestrians at 1.35m/s, an appreciable amount higher than my estimate of 1.10m/s. The graphical representation of the speed frequencies shows a loosely bell shaped curve but with a steep central peak consistent with the low standard deviation.
Overall it appears there is a wide range of values concerning the speed and distribution of speeds of pedestrians and I believe this is due to a number of factors. The motion of pedestrians is a social phenomenon that occurs almost ubiquitously in everyday life. For this reason, individuals’ behaviour can alter dramatically depending on the circumstances in which they find themselves. For example, ones behaviour and priorities when socialising may differ greatly to behaviour exhibited while at work. The motion of pedestrians in the Queen Street study, who are primarily shopping, regarded generally as a relaxing leisure activity, may display different attributes to individuals traversing say, a corridor at work. When the motives for your actions change it is surely inevitable that the actions themselves change, albeit subconsciously, for this reason I remain confident the data I have collected accurately represents the circumstances I have analysed.
I have now obtained data regarding speed and density comparisons for three distinct areas, the two levels of crowd density in the Millennium Stadium study and the Queen Street analysis. Bringing this data together we can now take a look at how density affects agent speed. Appendix A1 shows the raw values from all three tabulated and the corresponding graph in Appendix A3. It is clear that crowd density is having a significant impact upon average pedestrian speeds, with an increase in density restricting the speeds of individuals. Although only observing across three different values, where a greater range would help notably, conclusions can be drawn. It would appear the difference between pedestrians with an almost unobstructed path to those with even a small amount of disturbance from other pedestrians is significant. It also follows that at high levels of density, agent speed has already been greatly reduced and even a significant increase in density has little impact on speed.
Some of these findings will later help shape the simulation I hope to develop. I will also collect further data to help confirm the success or otherwise of my simulation after implementation. Therefore, further analysis and efforts to fully understand all the issues concerned with my field study will be further explored later.
4. Specification and Design
4.1 Specification
To ensure a functional and usable system that can be of genuine interest in the field of crowd simulation, I will make certain a number of key requirements are fulfilled and that a considered design process is undertaken.
I will develop what I hope to be a toolkit to enable research into the area in question. The primary feature will be a graphical representation of the crowd movement. This will take the form of the cellular automaton and locations within this either marked as occupied or not – representing the pedestrians within the crowd, or ‘agents’. I will implement a system whereby a simulation is run over discrete time units, with one update of the locations of agents upon every time unit – or ‘tick’. I will ensure the simulation has a means to keep track of these ticks so that timed simulations can be carried out as well as an ability to measure distances travelled by particular agents over a given time frame.
The simulation itself will consist of a one-dimensional passage of user defined length and width; agents will traverse this path moving in one direction only. Conservation of the agents will be maintained by ensuring that the simulation logically loops round so that as an agent moves of the end of the passage it returns to the start. This ensures that the total number of agents within the simulation will always remain constant and avoid the need to feed new agents into the simulation to keep a constant flow.
This passage described above will be a cellular automaton. The environment will consist entirely of a discrete number of cellular positions within an overall lattice. Therefore, the height and width of the environment will be defined precisely as the number of cells high and wide the user wishes.
Figure 7 shows the basic format the
simulation will take. Grey cells in this figure represent an obstacle that
agents can not pass through. In this case they line the edges of the passage to
mark the boundary of the environment which no one can exceed.
|
|
|||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
Figure 7. An example of a cellular automaton to be used in this simulation. Agents will pass from left to right, once “dropping off” the end of the lattice they will continue back at the left side. Each square represents one cell.
4.2 Requirements
There are a number of specific functions that I hope to implement; the extent to which I am able to implement these will enable me to later judge the success of my system.
From a user point of view there are a number of features that I believe are essential to any such simulation. A method by which a user can, with ease, define attributes of a specific model they wish to run without need to edit or recompile source code is needed. These attributes include the dimensions of the environment as well as the number of agents they wish to include within a particular simulation. Other functions that I will ensure the user can control regard the actual execution of the time ticks within the model. An ability to start and stop the running of the simulation, control the speed at which it runs as well as step through just one time tick at a time is required. Figure 8 shows a use case diagram that represents these usage requirements of the system.
From a user point of view, the collection of statistics is also an important function. My implementation will require a means to collect and store in a reasonable format, data concerning the simulation run. To aid the comparison with my field work I will collect statistics that correspond to measures of flow and agent speed that I have already analysed.
Aside from control aspects, users will also
be provided with a graphical representation of the simulation. The CA will be
displayed and the locations of all agents within the model at any time will be
clearly visible, as will their movement at each simulation tick.
From a non-functional point of view there are also some issues to consider. The computational complexity of the implementation should be kept to a minimum as with an increase in the number of agents within any model, the required processing will inevitably increase. It is important that models can be built, executed, viewed and statistics collected in a timely manner. Factors concerning maintainability and usability are also an issue. The interface should conform to industry standards concerning usability as well as an ability for future work and research to be carried out to extend and further analyse my work, maintainability of the code I produce is therefore essential.
With respect to the algorithms of movement that will be developed, there are also requirements to be met to ensure a study that is of academic interest. As previously stated I will ensure an accurate implementation of Blue and Adler’s rule set is coded to operate within my system. I will then extend this rule set to also design and implement a purely multi-agent based approach. As already stated I will also ensure this new rule set has less reliance on chance when arbitrating between a tie break for equally good potential next moves.
4.3 Method of Implementation
In order to implement such a simulation I have a number of design choices to make. Firstly, I could code the entire simulation from scratch. This would involve ensuring a functioning representation of a CA, the development of agents that could traverse this as well as a number of controls to enable the system to fulfil the user requirements. A usable graphical user interface would also need to be ensured so that statistical analysis and setting up of simulations can be carried out with ease.
Alternatively, there are a number of available open source toolkits that aid the development of simulations such as the one I hope to form. The selection and use of such a toolkit could prove very helpful to the overall success of my simulation. I hope the main emphasis of this study to be the development and analysis of the algorithms for movement of agents. With limited time constraints I believe the use of a third party toolkit can help me to reduce the time required to build a stable interface and ensure all usability requirements are fulfilled. This will allow me greater time for the development and coding of the specific algorithms of movement.
I studied the modelling toolkit REPAST (Collier et al. 2003). A significant advantage of the Recursive Porous Agent Simulation Toolkit is it is implemented in a range of languages allowing me great flexibility in choice of implementation method. This toolkit uses the library of object-orientated classes defined as part of the Swarm Development Group (Johnson 2006). Swarm’s class libraries are specifically written to enable the development of agent based models, the goal of the organisation is to group a number of different models defined as “agent based” into one common language and programming approach. The key disadvantage of REPAST is that I feel it is a very heavy weight application for the type of simulation I hope to create. As previously discussed, CA simulations are by definition not normally too computationally complex and the main functions from a toolkit that I require are merely the ability to implement such a system and control the running simulation.
Alternatively the Java Agent-Based Simulation Library (Sonnessa 2006) is a candidate. This is also based on the Swarm library but also includes a number of other fully tested third party libraries to improve the ease with which models can be built. The JAS focuses on discrete-event simulations such as the one I hope to develop. One disadvantage is that this toolkit is not widely used and outside of its development community has not seen a great take up in use for simulation studies. However, I believe this is due to the relatively new existence of it and the number of research areas that perhaps require the greater functionality afforded by the more comprehensive toolkits that I don’t need. I therefore feel the JAS gives me the best compromise between the ability to provide the required interface features and still the control to develop a simulation based on rule sets that I define. The use of the JAS will require me to learn how to make the most from its class libraries and how to effectively run my simulations through it, balanced by the decreased time programming usability features and boilerplate code.
4.4 Testing of Requirements
To ensure that all requirements outlined are successfully met, I will ensure a period of testing after implementation is carried out. This testing will not only ensure the functionality of the system with respect to bugs in code and well handled exceptions but also testing against the above requirements. For example, to ensure a pure MAS is developed I plan to check my developed algorithm against the check list stated earlier by Sycara (1998). With respect to functional requirements I will simply ensure that all features outlined above are met and with the use of well selected test data that no bugs exist within the system.
4.5 Implementation Strategy
I will develop my system with an agile development process. Fundamentally there will be two iterations, a process of design, build and test for the Blue and Adler rule set followed by the same process to implement my multi-agent extension upon this. As I am implementing my source code to be run within the JAS, I will have the opportunity to code and test my simulation as it is developed. For this reason I envisage my general development methodology being one of small incremental versions of my code being executed within the JAS as coding takes place, building up to a fully operational simulation.
5. Blue and Adler Implementation
5.1 The Blue and Adler Rule Set
As previously discussed, I will initially take the Blue and Adler rule set as stated in their 1998 paper Emergent Fundamental Pedestrian Flows From Cellular Automata Microsimulation and model this within the JAS. The rule set (which can be found in full in Appendix B) states the behaviour that each agent follows at every time step within the constraints of the CA in which they move. The rules dictate two key forms of movement, lane changes and forward movement. Lane change operations are those that control the movement of the agent sideways, from the perspective of the agent. That is, in the direction perpendicular to the agent’s actual desired movement forward. These allow an agent to change the route it takes from one location to another so as to avoid other, potentially slower moving agents. Forward movement is the progression of the agent in the direction in which it is ultimately attempting to travel, the initial lane movements occur so as to maximise this movement forward. Figure 9 clarifies these types of movement.
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Lane Change |
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Forward Movement |
||||
|
|
|
|
|
|
Figure 9. An example of the difference between lane change and forward movement behaviours upon an agent, shown in grey.
The rule set in Appendix B therefore, defines 4 discrete updates upon the simulation at each time tick;
1.
Lane Change Calculation
Rules 1 – 4 define the calculation of which lane is the most optimal.
2.
Lane Change Movement
After rule 4 the optimal lane is known and the agent is moved to this lane.
3.
Forward Movement Calculation
Rule 5 defines the calculation of the maximal distance forward the agent is
going to be able to move.
4.
Forward Movement Move
At the end of rule 5 the agent is moved forward to the cell that represents the
maximal distance forward possible.
Each of these updates occur in parallel over all the agents in the environment. That is, the simulation ‘visits’ all agents four times, on each visit they all perform the relevant update. This means that, for example, all agents calculate their optimum lane change behaviour prior to executing this behaviour by actually moving. However, this has one problematic side effect in that two agents could decide upon the same lane movement location and then on actually moving to this location a collision would occur. For this reason, rules 1a and 1b ensure that a lane is only assigned as unoccupied if there is no agent currently in it or in a position whereby one could move into it. This is implemented by checking both the current status of an adjacent lane (1 cell to the right or left) as well as the status of the lane beyond that (2 cells to the right or left). Rules 2, 3 and 4 state the method used to choose the lane in which to move based on those set to not be occupied by earlier rules. This is based on calculating for each lane the one with the maximal distance ahead of it to the next nearest agent. If there exists a clear maximal choice that lane is chosen, else Rule 4 defines tie break scenarios to choose between lanes of equal maximal distance, favouring the idea that if possible, an agent will remain in its current lane.
Blue and Adler also define the nominal speeds of their agents to not all be equal. As discussed in my observations in my field study, there is a marked difference in speed across a number of pedestrians and this is often the basis for emergent crowd behaviour. Faster moving individuals can find themselves ‘stuck’ behind slower moving pedestrians and attempting to overtake them. For this reason Blue and Adler define three classes of pedestrians with different nominal speeds. Within their experiments they class 90% of agents to be at a standard pace of 3 cells per time tick (how these distances relate to speeds in reality will be discussed later), and a further two groups of 5% of agents at 2 and 4 cells per tick speed respectively. When calculating lane movement, it is an agent’s ability to best fulfil its need to travel at this speed that determines which lane to choose.
Figure 10 now shows a scenario and how the Blue and Adler approach would deal with this within one simulation tick. Figure 11 represents the rule set as a UML activity diagram, from the point of view of one agent calculating its next move. The four discrete updates are shown separated with dotted lines. The algorithm dictates that all actions between the dotted lines are executed for every agent before moving on.
|
Update 1: Lane Change Calculation |
|||||||
|
|
|
|
2 |
|
|
|
|
|
|
1 |
|
3 |
|
|
|
|
|
|
|
|
|
4 |
|
|
|
|
|
|
|
|
|
|
|
|
|
Agent 1 : Current Lane - Max Distance Ahead = 1 Right Lane Unoccupied – Max Distance Ahead = 2 |
|||||||
|
Agent 2 : Current Lane – Max Distance Ahead = 3 Right Lane Occupied |
|||||||
|
Agent 3 : Current Lane – Max Distance Ahead = 3 Right Lane Unoccupied - Max Distance Ahead = 0 |
|||||||
|
Agent 4 : Left Lane Unoccupied – Max Distance Ahead = 3 Current Lane - Max Distance Ahead = 3 Right Lane Unoccupied – Max Distance Ahead = 3 |
|||||||
|
Update 2: Lane Change Movement |
|||||||
|
|
|
|
2 |
|
|
|
|
|
|
1 |
|
3 |
|
|
|
|
|
|
1 |
|
|
4 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||
|
Update 3: Forward Movement Calculation |
|||||||
|
|
|
|
|
|
|
|
|
|
|
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Update 4: Forward Movement Move |
|||||||
|
|
|
|
2 |
|
|
2 |
|
|
|
1 |
|
3 |
|
|
3 |
|
|
|
1 |
|
1 |
4 |
|
|
4 |
|
|
|
|
|
|
|
|
|
2
1
4
Figure 10. The four update steps that occur within one simulation tick of the Blue and Adler approach. Every agent, shown in grey, is assumed to have nominal speed of 3 cells forward. The direction of movement is from left to right. At update one the lane chosen based on rules 2, 3 and 4 of the rule set are shown in bold.
Figure 11. UML activity diagram to represent the process each agent undertakes at each simulation tick to calculate the next move based on Blue and Adler’s algorithm. Dotted lines denote the boundary between the 4 updates.
5.2 Simulation Coding
A period of development time was set aside at the start of the process of coding this simulation to ensure a full understanding of the JAS. I made certain that I was familiar with a number of the packages that were distributed with the built in API and had an understanding for what classes I would be required to implement and extend in order for the JAS to perform as I required.
Figure 12 shows a class diagram that was formed to represent the main classes that would work to form the simulation. The four classes across the middle of this diagram (CrowdSimAgent, CrowdSimObstacle, CrowdSimModel and CrowdSimObserver) are the four key classes I would be required to implement from scratch. Each of these have relationships with other standard JAS implemented classes as shown. Full details of this API can be found at the JAS website (Sonnessa 2006).
Code stubs for the classes I would require were created in accordance to the class diagram. Each class I implemented had a specific role;
CrowdSimAgent
This class represents a single agent within the simulation, it contains the algorithms for movement stated in Blue and Adler’s rule set. It is these rules that the agent will use upon each simulation tick to calculate and move to its next position. An instance of this class is created for every agent required within a particular simulation. This class extends Turtle, a built in JAS class that represents an agent with the ability to move across an object grid. The Turtle class provides methods to set the heading of an agent, move it forward upon the grid a set number of cells and so on. This class implements the ISimEventListener interface, this is a requirement of an agent class such as this. This gives the class the ability to receive notifications of an event, and therefore the ability to execute code within the class upon that event. In the case of my implementation, an event notification occurs 4 times every tick to trigger the agent to execute each of the updates that occur at every simulation step, explained previously. This class also implements the IColored interface, this ensures the class is asked what colour representation it requires when graphically rendered, allowing for agents of different nominal speeds to be represented differently.
Figure 12. UML class diagram to represent all key classes involved in the implementation of Blue and Adler’s algorithm.
CrowdSimObstacle
This class represents an obstacle within the simulation through which an agent can not pass. As with CrowdSimAgent, this class extends Turtle and implements IColored giving it similar behavioural properties to the CrowdSimAgent. This means it can be positioned within an object grid and therefore be perceived by other agents, as well as be represented as a particular colour to characterise it in the graphical interface.
CrowdSimModel
This class represents the overall model, that is, the crowd simulation itself. Every simulation within the JAS requires a class such as this that extends SimModel. This class must overwrite two methods, setParameters() and buildModel(). CrowdSimModel has overall control of the simulation and the setParameters() method is called as soon as the simulation is loaded into memory, its function is to collect the parameters to be used, potentially from the user. In this instance, the CrowdSimModel will use a ParameterFrame to collect user defined parameters from the user. The buildModel() method is executed when the user chooses to actually run the simulation once loaded. In my case this will be used to create an object grid (ObjGrid) and instantiate instances of CrowdSimAgent and CrowdSimObstacle upon this grid. This method then builds the ‘actions’ which will occur at each simulation tick, in this instance 4 actions will be formed that will message the CrowdSimAgent being called with which type of update must occur each time it is executed.
CrowdSimObserver
This class defines the graphical representation of the simulation formed with the CrowdSimModel class. This is a very similar class to CrowdSimModel as it also extends SimModel, but this overwrites buildModel() to instantiate a LayerObjGridDrawer that is able to provide a graphical representation of the ObjGrid, and instances of CrowdSimObstacle and CrowdSimAgent defined in CrowdSimModel.
All source code for the completed four classes can be found in Appendix C. I will now examine areas of the implemented code that are of particular interest and discuss the development that surrounds them.
5.2.1 Building of the environment in CrowdSimModel
As previously discussed, the buildObjects() method of CrowdSimModel initially sets up the overall simulation by instantiating the lattice for the CA and creating and placing on this, the agents and obstacles.
//A random location is chosen for the agent on the ObjGrid
int xLocation = Sim.getRnd().getIntFromTo(0, worldXSize-1);
int yLocation = Sim.getRnd().getIntFromTo(0, worldYSize-1);
while (found == false)
if(lattice.countObjectsAt(xLocation, yLocation)!=0){
xLocation = Sim.getRnd().getIntFromTo(0, worldXSize-1);
yLocation = Sim.getRnd().getIntFromTo(0, worldYSize-1);
}else{
found = true;
}
}
The above code extract from the buildObjects method shows clearly the way in which, for each agent to be created, a location is found. This location is determined by an initial random choice of X and Y positions and following a check to see if this location is available, the procedure either continues and will use these values to place the agent or loops to select random locations until an available one is found.
5.2.2 Building of actions in CrowdSimModel
public void buildActions(){
SimGroupEvent s;
//Create and event list and add each of the four events to it, along
//with the type of event
s = eventList.scheduleGroup(0, 1);
s.addCollectionEvent(agentList,CrowdSimAgent.LANE_CHANGE_CALCULATE);
s.addCollectionEvent(agentList,CrowdSimAgent.LANE_CHANGE_MOVE);
s.addCollectionEvent(agentList,CrowdSimAgent.FORWARD_MOVEMENT_CALCULATE);
s.addCollectionEvent(agentList,CrowdSimAgent.FORWARD_MOVEMENT_MOVE);
}
The above code extract is the complete buildActions method from CrowdSimModel. It can be seen here that an eventList is formed to hold each of the four events that occur in every simulation tick. Each of these will be executed in turn at each tick and consist of a call to the performAction method of the CrowdSimAgent class as this implements the ISimEventListener. Static integer variables within this class are referenced in the eventList so that when the performAction method is called the particular event being currently executed is available. Further detail of the performAction method will be discussed later.
5.2.3 Setting of Parameters
The required overwriting of the setParameters method in CrowdSimModel due to its implementation of the SimModel obtains the parameters for a particular simulation.
public void setParameters(){
ParameterFrame fr = new ParameterFrame(this, "CrowdSim parameters",new File(path + "CrowdSimAgent.pForm.xml"));
addSimWindow(fr);
}
The above code extract shows how the setParameters method uses a ParameterFrame to obtain simulation parameters from the user. This occurs immediately the simulation is loaded and clearly before the buildModel method is executed as this method will require details of the parameters set here. The ParameterFrame takes details from an external XML file as to the format of the parameters it is required to collect.
<Param name="worldYSize" type="2" minValue="0" maxValue="150" order="1" description="The world's height.">12</Param>
<Param name="worldXSize" type="2" minValue="0" maxValue="250" order="2" description="The world's width.">40</Param>
The above extract from the CrowdSimAgent.pForm.xml file shows how the parameters for the height and width are defined. Maximum and minimum as well as default values and a description of the parameter are set.
5.2.4 Overall algorithm design in CrowdSimAgent
The CrowdSimAgent class contains the performAction method, which, as already discussed is a required method for all classes implementing ISimEventListener as it is this method that is called upon every event in a simulation tick.
public void performAction(int actionType){
//Determine the type of update and perform actions appropriately.
switch(actionType){
case 0:
laneChanges();
break;
case 1:
setXY(getX(),getY()+getLaneMovement());
break;
case 2:
forwardMovement();
break;
case 3:
int xAfter = getNextXPos(getX(),getForwardMovement());
setXY(xAfter, getY());
//Increment counter to track number of simulation
//'ticks' passed
count++;
//Increment the total number of steps this agent has
//moved if tick counter is greater than 1000
if(count>1000){
numberOfSteps = numberOfSteps+getForwardMovement();
}
//After 10000 simulation ticks processed, output
//data to file
if(count == 11000){
output(agentID+", "+numberOfSteps);
}
}
}
The performAction method above shows clearly the four update types that occur. The actionType parameter passed to the method is the static integer variable assigned to an event when added to the eventList as shown earlier. This allows the switch statement shown to execute the code required for that type of update. Observing the full source code in Appendix C will show the full extent of all the methods within this class to fully implement the rule set, some are now looked at here in more detail. This method also shows calls to the output method to record the number of steps taken by agents during certain simulation ticks, this will be explained further later.
public Boolean getLeftLaneFree(){
if( (theLattice.get(getX(),getY()-1) instanceof CrowdSimAgent)||
( (getY()-2 >=1) && (theLattice.get(getX(),getY()-2) instanceof CrowdSimAgent))){
return false;
}else if(theLattice.get(getX(),getY()-1) instanceof CrowdSimObstacle){
return false;
}else{
return true;
}
}
The above code extract shows the implementation of rule 1a of the Blue and Adler rule set. It can be seen clearly that if the location one to the left, or two to the left (if within the lattice boundary) is occupied with a CrowdSimAgent the method returns false. Similarly if the location one to the left is occupied with a CrowdSimObstacle, the method returns false to represent that the left lane of that cell is occupied. In any other circumstance it will return true.
//If all three lanes ahead are equal
if((leftIn == currentIn) && (leftIn == rightIn) && (currentIn == rightIn)){
rand = (Sim.getRnd().getIntFromTo(0,9));
//A three way random choice with 80/10/10 split favouring
//remaining in the same lane.
if(rand >= 2){
newLane = 0;
}else if(rand == 1){
newLane = 1;
}else{
newLane = -1;
}
The above code extract represents part of rule 4 of the Blue and Adler rule set. It can be seen that the IF statement tests to see if all three lane distances (leftIn, currentIn and rightIn) are equal, then the tie break occurs to randomly choose the new lane. In this case a random integer between 0 and 9 inclusive is chosen and with an 80/10/10 split favouring remaining in the same lane, the new lane value is assigned accordingly. The newLane integer variable stores the new lane value as the integer offset from the current lane. Therefore an assignment to the current lane is represented with setting this variable to the value 0 and for a left or right lane, -1 and 1 respectively.
public int getNextXPos(int xPosIn, int distance){
int newPos = 0;
if(xPosIn+distance >= worldXSize){
return distance-(worldXSize-xPosIn);
}else{
newPos = xPosIn+distance;
}
return newPos;
}
As explained previously, to ensure the conservation of all agents, the simulation is logically an infinite length passageway with agents moving off one end and looping back to the start. The above method shows part of how it was ensured this conservation occurred by making certain that the next X position an agent occupied would either be ahead of it by the appropriate distance or if looped back to the start, still moved the equivalent distance. Passing this method an agent’s current X-position and the distance it wishes to move returns the new X-position of the agent.
5.2.5 Collection of Statistics
public void output(String textToOutput){
try {
BufferedWriter out = new BufferedWriter(new FileWriter("data.txt",true));
out.write(textToOutput);
out.newLine();
out.close();
} catch (IOException e) {
}
}
The above method, output, is called from the actionPerformed method which was shown previously. This method takes a String variable as a parameter and will append this to the data.txt file on a new line. The String value passed is always in the form of the agentID number followed by a comma and the piece of data for that particular simulation tick, e.g. the number of steps forward moved. This allows the file to be used as a comma separated values file and loaded into a spreadsheet application for statistical analysis.
Screenshots of the simulation environment can be found in Appendix D, including the appearance of the program when obtaining parameters from the user through to the execution of a simulation.
5.3 Testing
I will now conduct a series of tests to ensure the crowd movement simulated is behaving in the expected manner and executes bug free for a wide range of data. This testing will focus solely on the assurance that implemented code is bug free and conforms to the prescribed rule set, non-functional testing to ensure the fulfilment of requirements will occur later.
|
Test Name: |
Maximum Crowd Size Test |
|
Description: |
A test to simulate an attempt to have a greater number of agents within the lattice than it can possibly hold. |
|
Parameters Used: |
Lattice total world size set to 20 x 20, when allowing for obstacles (simulation boundary) there are 360 possible locations for agents. Number of agents set to 400. |
|
Expected Output: |
Simulation will reduce the number of agents to one less than total possible, in this case 359. |
|
Actual Output: |
As expected |
|
|
|
|
Pass/Fail? |
PASS |
|
Test Name: |
Invalid Crowd Size Test |
|
Description: |
A test to simulate an attempt to have a negative number of agents within the crowd. |
|
Parameters Used: |
Lattice total world size set to 20 x 20, number of agents set to -1. |
|
Expected Output: |
The value of -1 is invalid based on the rules set in the parameters XML file, the input will automatically reject this when it is entered and revert to its previous value. |
|
Actual Output: |
As expected |
|
|
|
|
Pass/Fail? |
PASS |
|
Test Name: |
Execution of Simulation and Observe Exceptions at Low Density |
|
Description: |
A test to execute the simulation with one agent over 1,000,000 simulation ticks and observe any thrown exceptions. |
|
Parameters Used: |
Lattice total world size set to 20 x 20. Number of agents set to 1. |
|
Expected Output: |
Simulation will execute over the full number of time ticks with no exceptions thrown. |
|
Actual Output: |
As expected, no exceptions thrown. |
|
|
|
|
Pass/Fail? |
PASS |
|
Test Name: |
Execution of Simulation and Observe Exceptions at High Density |
|
Description: |
A test to execute the simulation with a high number of agents over 1,000,000 simulation ticks and observe any thrown exceptions. |
|
Parameters Used: |
Lattice total world size set to 20 x 20. Number of agents set to 250. |
|
Expected Output: |
Simulation will execute over the full number of time ticks with no exceptions thrown. |
|
Actual Output: |
As expected, no exceptions thrown. |
|
|
|
|
Pass/Fail? |
PASS |
The following tests consist of executing particular scenarios with agents placed in a particular arrangement. This required slight alteration of source code to place agents in specific locations and remove the random choice. These tests all assume one class of pedestrian at nominal speed of 3 units per simulation tick. Scenarios referenced here can be seen in Appendix E.
|
Test Name: |
Execution of Scenario 1 |
|
Description: |
A test to execute a specific scenario and observe if outcome matches the theoretical outcomes based on the rule set. Each scenario will be executed 20 times, in every instance the scenario after one simulation step must be one of the potential next scenarios to pass. |
|
Parameters Used: |
Input scenario 1 (Appendix E) |
|
Expected Output: |
Expected potential next scenarios for scenario 1 (Appendix E) |
|
Actual Output: |
In all cases one of the 3 potential next scenarios was the actual state after one time step. |
|
|
|
|
Pass/Fail? |
PASS |
|
Test Name: |
Execution of Scenario 2 |
|
Description: |
A test to execute a specific scenario and observe if outcome matches the theoretical outcomes based on the rule set. Each scenario will be executed 20 times, in every instance the scenario after one simulation step must be one of the potential next scenarios to pass. |