Friday, 14 May 2010

Pedestrian Playground

Looking through one of my favourite books, Critical Mass, I came across a page I had been meaning to do some research into. The section of the book was on cellular automata, and the creation of complexity from simple rules. I mentioned a few posts ago about a paper I had read about solving the Travelling Salesman problem using ants. The travelling salesman solves the problem of getting between a number of towns using the shortest route possible. This is all well and good but the travelling salesman has an absolute answer, and in my opinion that immediately makes the problem slightly less interesting. The randomness of the human psyche is far more exciting, and the pedestrian motion created when you bring large groups of people together are often quite surprising. Take a look at the image below for example; the trails connect 3 points of interest

around a park. None of the paths join any of the 3 target locations in the most efficient way, yet after years of trampling down grass, and the slow fading of former trails, the most desired route (on average) is the one seen here.

Obviously park planners would have a much easier job keeping their lawns meticulous if they could somehow predetermine where people were most likely to walk, thus keeping pedestrians on the paths, and not trampling their grass. This problem is slightly more subtle than the travelling salesman, there are in fact  many solutions and they depend on a huge number of factors: how many people want to go to each destination, how fast does grass regrow, how fast does a path form, how many people commute along the paths each day, do people have to walk uphill, is there a fence...? Obviously the list goes on for quite a while, after all humans are not predictable, but we can still create a simple model.

The screenshots below show the main interface of my application, just click the first image to launch it. The number of target towns, and the number of people can be changed, as can the size of random fluctuations in direction, the effect of the destination on the direction walked, and the effect of the route on the direction walked. Two factors called visibility, and distance factor also affect the likelyhood that a pedestrian will take the most direct route to their destination. Have a play around with the factors and see if you can reproduce the pattern seen above.

In the below examples you can see paths merging, even though this is not the most efficient route for anyone. The first image still has some "visibility", the second has absolutely none, people just tend to congregate randomly, but it does make a nice pattern, and the third shows path splitting, where two similar but separate routes form spontaneously.

No comments:

Post a Comment