Crowd Simulation

Software Framework: OpenFrameworks

2010-11-17T05:04:00.000-08:00

I'm going to take a software engineering point of view in this post. To come up with any type of model or simulation, it is a good idea to start with a software framework.

A software framework according to Wikipedia is 'an abstraction in which common code providing generic functionality can be selectively overridden or specialized by user code'. Software frameworks facilitate the development of software, and allow the developer to focus on the software requirements rather than the low level details of providing a working system that allows access to the hardware. This, in turn, reduces development time.
For the short term, it would more than likely increase the development time, as there is a learning curve involved which needs additional time. In the long run, once the framework is learned, future projects can be a lot quicker to complete, as the need to concern ourselves with the low level details is diminished.

There are several types of frameworks available for C++ such as SDL, OpenFrameworks, Qt, etc., I'll focus on OpenFrameworks today. A few projects made using OpenFrameworks is below (clicking on it will take you to the project site on OpenFrameworks):

OpenFrameworks is a library that is designed for 'creative coding'. The library is wrapped with glut which is a windowing library. This wrapping I feel is quite a good choice, as it works really well with OpenGL. The OpenGL red book bases its code on glut as well.

If you've used Processing, OpenFrameworks certainly draws parallels with it. The website that provides the reference to the commands of the framework is also very similar. Processing users would feel right at home, there's also a wiki that provides an orientation to OpenFrameworks that can be quite handy.
What I like about this framework is that it wraps several other libraries to provide a very good interface. OpenGL is used for the graphics, as I mentioned works well with glut. freeImage which is a popular library for image I/O and processing is also included. Even quicktime which is good for playing video.
I currently use SDL, but after having a look at OpenFrameworks, I'm considering using it. Looks like a very good framework to use, and the learning curve doesn't seem too high after having used Processing previously. At the same time, there is already a lot of articles and a whole community available for SDL. I'll discuss SDL in another post. OpenFrameworks does indeed look like a very good software framework indeed.

Tube Strike: A changed Macro-System

2010-11-10T07:35:00.000-08:00

The recent tube strike and a discussion with one of my professors has led me to think about micro and macro systems as a whole, and in turn simulations working within these constraints.

First of all, let me say a little about a normal working day and what happens during this time. We have a fully working transport system, a nice sunny day (or mostly grey, in London at least!), a phenomena, if you'd allow me to call it that, takes place i.e., commuting. Individuals work, that's how the economy and you, as an individual survive and provide for yourself, and your family. So, we have people who commute to and from work everyday. What happens during the commute? Each individual, makes an independent decision in order to reach their work destination. How they get there is based on personal choice, which is generally ruled by the amount of time it would take to get to work, the distance to workplace, and the number of changes that are required. This decision gets refined as the individual finds him / her self making the most efficient decision to reach the workplace.

Each individual takes these similar independent decisions becoming routine over time. Aggregating all these independent decisions together, we get people moving around, and a pattern develops as the micro-system stabilises, in which ways people move to commute to and from work. These hundreds of independent decisions are taking place within the constraints of a macro-system. The macro-system in play here is the transport system, and these individuals actually play by the rules set out by the macro-system in place here.

A macro-system can be defined here as a large system within which micro-systems are contained. Therefore, here, we have the transport system as the large macro-system, and the individuals as the micro-systems which are contained within this large system, and taking their independent decisions within the constraints set out by it.

Now, we have a tube strike, like the one on 3 November 2010. What happens here?! The large macro-system changes. Most tube lines don't work, sever delays on lines that do, more buses on routes, cycles being transported more frequently to fill up empty slots. This creates havoc in the micro-system, but it doesn't fail. In fact, what happens is that the micro-system adjusts the way it works within the new constraints set out by the macro-system in play, and then we have the same individuals making their renewed complete independent decisions, again taking into account the most efficient way to get to work by finding the lines / buses / boats that are working, and taking those transport links, or replacing it with cycles or cars. We now have a micro-system changing, but in a way that individuals still get to work, but using the new constraints set out by the macro-system at play, and they work within these constraints. Complaints? Yes....Impossible? No, not at all!

It's the laws of the macro-system here. Micro-systems are contained within it, and they will change in order to work within the constraints of the macro-system, or even be influenced by it. An analogy with Ecological Systems Theory can also be drawn, but I'll leave that for another post!

This is the problem I wonder about when I'm designing my model, I need these micro behaviours to work within the constraints of the macro-system at play. Do I model the macro-system first, or model the micro-system and build a macro-system around it? It's the chicken or egg problem again here!

Pedestrian flow at Euston station

2010-06-08T04:28:00.000-07:00

A public discussion held recently at City Hall by Art on the Underground, about London journeys shows a good application of simulation of crowds. As you can see in the images below, London Underground studies people's movements through tube stations to see how they can help by regulating passenger flows through the placement of tickets gates and in turn improving the congestion.

The image above shows passenger flow before improving the congestion, simulated using Legion. The green dots are people entering, and red dots people exiting.

The flow improves considerably as can be seen once the ticket gates and hall layout were changed. The congestion is reduced as it provides more of a two lane flow of exiting and entering pedestrians. More details about the public discussion can be found on Going Underground's Blog

Paper: Aggregate Dynamics for Dense Crowd Simulation (2009)

2010-01-21T08:13:00.001-08:00

Ming Lin's latest work has been featured in the recent publication of SIGGRAPH Asia 2009. The author presents an innovative method that is able to simulate tens of thousands of agents at interative rates.

The work achieves these rates by combining a local behavioural model with a global planner such as Continuum Crowds or Adaptive elastic Roadmaps (AeRO).

Image taken from gamma.cs.unc.edu

The image above shows an overview of the algorithm. So how does this actually work?

First of all, as I mentioned this approach combines a local behaviour with a global planner. The global planner here computes the flow of agents around an environment. The steps are described below:

Each agent is given a position and a current velocity computed.
Using the global planner such as the roadmap based method or Continuum Crowds method, a preferred velocity is then computed for each agent.
The navigable area in the environment is divided into a discrete grid of cells. The flow of particle for each cell is computed, using the current velocity and density of agents in the cell.
For each agent, a new velocity is computed, by interpolating the flow velocity with the desired velocity weighted by the local density at each cell.
Velocities of agents are constrained in dense areas by the global particle flow. In coarser areas, the agent's velocity are influence less by the global flow, and more by the velocity for the cell.
Finally, collision detection is applied, as well as a minimum distance for each pair of individual agents, similar to the continuum crowds simulation.

Here's a video of the simulation:

Aggregate Dynamics for Dense Crowd Simulation

A good hybrid approach used here that decreases the computation time considerably to accomodate a very large number of agents at interactive rates. The Unilaterally Incompressibility Constraint (UIC) introduced here that allows the interpolation between the global and local approach is something that has interested me.

Oxford Circus 'X' Crossing opens

2009-11-02T08:28:00.000-08:00

As mentioned in a previous post about the Oxford Circus intersection getting a revamp, the intersection has finally been opened today after a number of months of the usual British roadworks. A picture of which can be seen below. A video can be found on a BBC news article here

It's interesting to see how a simulation has been transformed into reality, and the benefits it will bring for pedestrians through one of Europe's busiest intersections. I would also guess that the simulation certainly aided the arguments for benefits of having Oxford Circus get a revamp. I'm certain there must be many more examples that exist, where simulations aid urban planners or architects for such applications.

XBox 360 and GPGPU

2009-09-14T10:01:00.000-07:00

It seems Microsoft's console is jumping into the bandwagon of parallel computing using GPGPUs, with new research published that explores parallel computing using the graphics card of Microsoft's XBox 360.

Dr Simon Scarle, previously a Microsoft Rare Studio Software Engineer, who is now a researcher at Warwick University's WMG Digital Laboratory, used one of the XBox 360's GPUs to carry out research on how electrical signals around the heart moved around damaged cardiac cells.

Sony's PS3 has made the use of parallel computing from the very date of its release, with Stanford University's Folding@Home project, and has software development kits (SDK) for harnessing the parallel processing capability of the console.

On a previous post, I mentioned how the PS3's parallel computing capability has also been used to create a flocking simulation. It would be interesting to see if such simulations are, created on the X360, and to see if Microsoft will consider releasing an SDK to attract researchers and developers to use its console for this purpose.

It would certainly be a cost saving way of carrying out research that requires parallel computations, rather than the traditional use of clustered PCs or setting up a network of PCs.

Simulation of Starlings flocking behaviour using captured 3D video recordings of Starlings in flight

2009-08-25T08:33:00.000-07:00

I was quite interested to find this flocking simulation of starling's on MIT's Physics arXiv blog.

I mentioned Reynold's flocking behaviour model in an earlier post, it's nice to see progress has been made in creating more accurate simulations by actually capturing 3D recordings using stereographic photography of real starlings in flight.

These video recordings that were published last year has actually allowed Charlotte Hemelrijk at the University of Groningen to create a flocking model, and vary the parameters that closely match real flight recordings of the starlings.

These birds have very complex rules creating this self-organising behaviour, and the researchers seem to have been able to take apart the rules that govern them. These rules also govern other species such as fish, insects and even human crowds, and will likely give further insight into crowd behaviour, and allow for more accurate simulations of human crowds.

I'll be looking forward to seeing a video of this flocking simulation.

XFlow: Fluid simulation tool

2009-08-24T12:49:00.001-07:00

I've just come across XFlow, from NextLimit, which is an accurate fluid simulation tool. It uses a particle based method, instead of a computational grid that are used in other Computational Fluid Dynamics (CFD) tools.

The interesting part of this tool is that they have explored other fields, where CFD can be applied to. As they use a particle based method, it is well suited for applying to simulation for complex systems. Examples include:

1. Traffic Simulation
2. Cell Simulation
3. Crowd Simulation

For the crowd simulation application, the particles can represent the pedestrians in different conditions, which can then be applied to scenarios such as emergency evacuation.

Layar: Augmented Reality Browser - Google Android Platform

2009-08-18T10:46:00.000-07:00

I've just come across this Augmented reality browser available as an app on the Google Android Market. This is not actually an app, but a platform, which has provided its own API. Therefore, developers can create their own augmented reality layers on top of the browser. This addition of layers over the application brings huge potential in crowd sourced content, and the various other uses that are possible such as augmented reality tour guides, tourist information, social networks, points of interest, transport, etc.,

There can be some more exotic approaches that can be applied to this kind of platform, such as augmented reality games, although, they have been around for a while (mainly GPS location based games), this takes it to a whole new level.

I also wonder about the possibility of using this platform to study crowd behaviour of tourism and leisure activities. These types of behaviour have been traditionally very hard to model, and as this platform will mainly be focussed on these kinds of activities, it would give an insight into the behaviour. Although, getting user permission to gather such data would be an issue in itself.

Netlogo to 3D Max: Code

2009-05-19T09:41:00.000-07:00

Based on the pseudocode for the Netlogo to 3DMax implementation, I have now decided to post a short tutorial on exporting the Netlogo traffic simulation to 3DMax. This tutorial will mainly cover the output of the turtles and visualising it in 3DMax.

Netlogo (traffic grid simulation):

For the turtles, I output during runtime, therefore, open the file at the first tick, keep writing, and close the file at the last tick, depending on how many ticks you would want to output, in my case 500.

if ticks = 0 [file-open "myfile.txt"]
ask turtles [
              file-write xcor file-type " " file-show ycor
            ]
if ticks >= 500 [file-close]

This will output in the form:

-12 (turtle: 2) 11
-17 (turtle: 0) 5
-4 (turtle: 1) -8

I didn't find a simple way just to output only the turtle id number, so I manually delete the brackets and text using find and replace, giving me an output as seen below:

-12 2 11
-17 0 5
-4 1 -8

Now our next step is to import it into 3DMax. Once the output file has been stored, the script below can be run, and on clicking the 'Make' button, locate the output file, and it will create the animation.

The code works by importing the Netlogo output file into an array. It can be found here.

I have commented the code in order to explain what is happening at each step.

Running this script will result in the animation shown in my previous post. To get the road patches, and traffic lights in 3DMax, the code can be extended further to store the patches and traffic light states in arrays for each frame, once imported from the Netlogo output.

Update: As pointed out by a reader, there is actually a simple way to output only the turtle id number using the command:

ask turtles [print who]

Therefore, the Netlogo output above can be obtained by using the following command

ask turtles 
[
file-type word xcor " " file-type word who " " file-print ycor
]

Big, Fast Crowds on the Sony PlayStation 3

2009-04-25T06:07:00.001-07:00

Craig Reynolds first introduced flocking to the computer graphics area by creating the Boids artificial life simulation in 1986. It was a computer model of coordinated animal motion such as bird flocks or fish schools, that allowed for collision avoidance and goal seeking. This model has had various applications such as bat swarms and penguin flocks in the movie 'Batman Returns'. A video of the early model can be seen below, further details can be found here

The above model has a complexity of O(n²), as each boid needs to consider each other boid in order to determine whether its a nearby flockmate. The complexity can be reduced to O(n), by the use of spatial hashing that keeps the boids sorted according to their location, and therefore, increase the population of the boids.

Craig now works for the US R&D group of Sony Computer Entertainment. Recently he created a crowd simulation on the Sony PlayStation 3, which extends from the very early model above. As spatial hashing is used in order to accomodate large numbers of agents, here, it forms the basis of a scalable multi-processor approach to create large, fast crowd simulations. The PlayStation 3 has Cell processor, which consists of a Power Processor Unit (PPU), multiple Synergistic Processor Units (SPU) - 6 available to the model, and an RSX GPU. The model makes use of this architecture to spatially subdivide regions, and use the multiple SPUs to update a number of regions in parallel, accelerating the crowd simulation. The model has been able to incorporate 15,000 agents running at 60fps. A video can be seen by clicking the picture below:

It is interesting to see how different architectures can be used to create crowd simulations, and how the parallel processing nature of today's video games consoles, make them low-cost and high performance platforms for parallel execution. I will be looking forward to see other general purpose applications of the Sony PS3.

GPU Crowd Simulation

2009-04-20T09:57:00.000-07:00

This is a conference sketch by Shopf, J., Oat, C., Barczak, J., presented in Siggraph Asia 2008.

I've been talking about how I am looking into creating a crowd simulation on the GPU. The sketch states that, to their knowledge it is the first implementation of a massive crowd simulation entirely on the GPU. A video clip of the simulation can be seen by clicking the picture below, and the slides of their Siggraph Asia 2008 presentation can be found here.

The implementation consists of a simulation of 65,000 agents at realtime frame rates. They have used a framework that combines a continuum-based global path planner (similar to the continnuum crowds post I did earlier), with a local avoidance model at a finer scale.

This also allows the level of detail to change as the view is scaled. There are other conference sketches by ATI, such as 'GPU Tesselation for Detailed, Animated Crowds', and 'GPU-Based Scene Management for Rendering Large Crowds' that must have been used in the simulation.

These sketches give an interesting insight into the capabilities of the GPU for simulating massive crowds, and how the level of detail can be varied based on the scale.

Pedestrian model for a Tokyo style intersection of Oxford Circus

2009-04-14T12:12:00.000-07:00

As has been recently announced, Oxford circus is to get a pedestrian-friendly revamp. Here is a video of a pedestrian model, first referred to me by Duncan Smith, a PhD student at CASA. The model consists of 5000 people, where a particle-based system was used to run the simulation. These particles were then replaced by animated people.

The model was created by designhive, and a map of the redesign can be seen here.

Here, the pedestrian and traffic simulation models are combined with a 3D Studio Max model of the Oxford Circus proposals, which makes this finished video very realistic.

This is a type of application, where a 3D visualisation of the model can be used to enhance the communication of ideas, and making it more accessible to others.

Continuum Crowds

2009-04-14T06:30:00.000-07:00

This is a paper by Treuille, A. Cooper, S., and Popović, Z, presented in Siggraph 2006.
It's a real time crowd model based on continuum dynamics. The motion of crowds is controlled by a dynamic potential field, which allows it to avoid moving obstacles without the need of explicit collision avoidance. Their paper and video can be downloaded here.

This paper presents a lot of potential in creating a real time crowd simulation with large crowds. It would be interesting to see other implementations of this technique.

Netlogo to 3DMax: Pseudocode

2009-04-05T06:52:00.000-07:00

As mentioned in an earlier post that I will be posting a pseudocode for a Netlogo to 3DMax implementation.
This pseudocode is mainly for the Netlogo traffic simulation, but I will try and make it as general as possible in order to use in other models.

Netlogo:
For each tick:
1. Output to file - x coordinate, turtle id, y coordinate

Please note, that when the data is exported into a text file, it will have other test such as 'turtle id:', all text needs to be deleted, and should leave you with 3 numbers. An example for 3 turtles (1 tick) can be seen below:

This creates a file that has the turtle id and locations for each tick. Now, our next step is to import it into 3DMax, but this time each tick represents a frame. I did this by creating a script that would store the data in an array for each frame.

3DMax:
1. Initialise an object (eg, box), for each turtle in the output file
2. Read in netlogo output file, and store xy coordinates for each object per tick in an array. (I stored the array in a 2D form [object id][xy coordinates])
3. Initialise positions of each object for first frame
4. While not end of array
5. Advance frame, and update object position corresponding to the object id in the array
6. Keep repeating step 5 till end of file is reached.
7. Render final animation

Same process for traffic lights, where each traffic light is a turtle in netlogo.

Book: Crowd Simulation By Daniel Thalmann, Soraia Raupp Musse, SpringerLink

2009-03-08T09:16:00.000-07:00

I will be occasionally posting details of books that I have come across, which some may find interesting.
This book gives a very good review of what is out there in the Crowd Simulation area. This includes different disciplines such as physics, sociology, computer science (as I mentioned in my first post), and the areas it's used in, such as the film and games industry, the academic research areas, planning, evacuation scenarios, and so on.

One of the authors, Daniel Thalmann, has quite a few publications in the Crowd simulation area, which can be found here
As I mentioned in my first post that I will be exploring some of the above mentioned areas. This book also interestingly mentions that 'despite the apparent breadth of the crowd simulation research basis, interdisciplinary exchange of ideas is rare; researchers in one field are usually not very aware of works done in other fields'. I find this point very interesting, and therefore, brings to mind that work in various fields may often be duplicated, although I havent yet come across duplicate work, it is worth bearing in mind. I welcome such a book that would explore work that has been carried out in different disciplines.

Netlogo to 3D Max: Visualisation

2009-03-08T08:39:00.000-07:00

The first few posts will be a catch up of what has been done so far. The first piece I worked on was a Netlogo to 3D Max implementation. This implementation is for a street level scale of a city. Although, 3D Max is used for crowd and particle simulations, in order to model these complex systems, an external package like Netlogo is used. Through the use of loose coupling with 3D Max, it allows us to easily visualise these systems.

The movie below was first posted on the Digital Urban blog. This was my first step to export a basic traffic model from Netlogo to 3D Max. The movements of the cars were first output into a file, the second step was to write a 3DS script to import these movements and animate them in 3D Max.

NetLogo to 3D Max - Proof of Concept from digitalurban on Vimeo.

I have noticed quite a few comments asking how this import was done. I will be posting a pseudocode soon, and will try and give a summary for each step.

Introduction

2009-03-07T08:20:00.001-08:00

As this is my first post, let me detail a little about me, and about this blog.
I am currently studying for a PhD in Crowd Simulation in the Centre of Advanced Spatial Analysis, University College London (UCL). I did an MSc in Vision, Imaging & Virtual Environments (VIVE) at UCL last year. I am in my 1st year of the PhD, and will be regularly updating this blog to include posts related to my work, work related to this area, and applications that I come across in the field.
My main aim for the PhD will be to create a real time scalable crowd simulation, therefore, allowing users to look at, for example, crowds in the city of london at varying scales, in real time.
This will be achieved using different architectures depending on the scale. The architectures I will be exploring will include disciplines in social science and computer science.
The work will carried out on the Graphical Processing Unit (GPU), concentrating on general purpose programming, i.e., GPGPU.
The reason I have chosen to use general purpose programming on the GPU, is because, there has been active research in this area over the last few years with the wide deployment of GPUs. The parallel processing of GPUs also gives us a distinct advantage to populate larger amounts of the city with agents, or a larger number of agents in a smaller area.