Fractal Crowds

(From 1994 - Focus - updated  31st August 2007)

Keywords: simulating people, simulating crowds, simulating crowd dynamics

New Insight into crowd behaviour - It's fractal

In the flow : The movements of large crowds of people are not random but have distinct patterns as people head for their goal while "going with the flow".

When you are stuck in a big crowd at a pop concert or football match, it's hard to believe anything other than random pushing and shoving is going on. But according to Keith Still [Ref: Video BB14:RI2], a physics graduate and software specialist, the movement of a crowd can form beautiful mathematical patterns called fractals. Still picked up the first hint of these patterns at the Aids Awareness concert, held at Wembley Stadium in April 1992. Every so often the crowd would form a series of human chains. Then, just as suddenly, these would dissolve back into apparent chaos. Why were the edges moving faster than the middle? And why were the patterns so regular? He thought about it for a long time and decided that there had to be an underlying pattern. With the help of Patrick Carr, the Operations Manager at Wembley Stadium responsible for crowd safety and security, Still gathered data on crowd dynamics during this year's FA Cup Final. From a lookout point situated high above the player's tunnel they observed the 80,000-plus crowd swarming below, and later pored endlessly over hours of video footage. Different parts of the Wembley complex, such as the Arena and the Stadium, had completely different crowd flow patterns. But the patterns in each area stayed consistent. "We felt the solution had to be somehow fractal and that it could be modelled and hence predicted," says Still. The video study showed that people in a crowd do have a sense of direction, but their line of sight is obscured. So they follow other people, and compete for spaces as they appear, because it is far easier to just "go with the flow" - provided, of course, that it's heading in the right general direction - rather than to try and break in to a dense Crowd. As a result, lines of people form. Still took all the data he had gathered from observations and reduced it to a short algorithm and then applied it to a computer grid - with points representing people. The results were astonishing. Beautiful patterns, which Still christened "Orchids", suddenly grew and bloomed like flowers on the computer screen. "We were amazed that three lines of code could produce such a complexity," he marvels.

A close examination of the Orchids using a computer "zoom lens" showed that they were fractals - basic patterns that remain similar over a wide range of scales. [Ref: Focus Jul95 p62].

The Orchids have obvious applications in predicting crowd behaviour and crowd control. But Still thinks there is more to the new fractals than simply this, pointing to the sheer number of different patterns - over 800 billion that have been generated so far by his programme.  He says: "I think we have stumbled on something other than crowd movement - but what it is we just don't know."

Flower Power : When data gathered by observing the movement of crowds was reduced to an algorithm and applied to a computer grid, it produced patterns (above) that looked like blooming flowers. So far 800 billion different patterns have been generated.

Nov1994 page30.

Of Springs, Crowds, Crinkles and the Price of the Yen

The Economist 13 April 1996

After years of decorating bedroom walls, adorning t-shirts and illuminating trendy nightclubs, fractals are starting to become useful

How long is a coastline? This was a question much asked a decade ago by science journalists trying to explain the fad for fractal mathematics in the 1980s. The answer depends on how long the ruler is that you are trying to measure it with. As you look closer to the point where the land meets the water, a coastline gets longer as more and more kinks are seen in it. In fact, the small-scale view looks surprisingly like a miniature version of the large-scale one. It is, in the jargon, self-referential.

Dealing with this, and similar problems (what is the surface area of a cloud?) is the province of fractal mathematics, or the algebra of partial dimensions. A coastline is too non-linear to be a line one dimension but not substantial enough to be a surface (two dimensions). It is somewhere in between - one and a bit dimensions.

Back in the 1980s, it all seemed curious, but not, perhaps, all that useful (except for working out how clumpily matter is distributed in the universe or for modelling the growth of red algae). Like catastrophe theory, another of that decade's crazes, fractals strutted and fretted their hour upon the stage and then were heard no more. They are now making a comeback, as a combination of better mathematics and faster computers puts them in reach of people other than cosmologists and botanists.

The best developed fractal application is image compression. Even with computer memories doubling in capacity every 18 months or so, there is still a premium on space. So when pictures to be stored digitally can be cajoled into taking up less space on a hard disk than they might otherwise need, money can be made. Traditional compression methods can squeeze pictures only so far. For example, a maximum of 72 minutes of video can fit on a CD-ROM. Fractal compression can put more than two hours of film on to such a disk. It may soon allow movies to be transmitted over the Internet at something approaching their proper speeds.

Fractal compression, developed by Michael Barnsley of Iterated Systems, in Atlanta, Georgia, makes use of self-referential information in the pictures. Recurring patterns in an image are identified, regardless of size, and a single copy is stored. Information about their actual size and position is held elsewhere. The result is a particularly efficient method of packing pictures away.

Fractals have also started to earn their keep in more humble industries than the movies. Making springs, for example, is beset by a recurrent problem. Since spring makers have no reliable way of telling whether a particular batch of wire will make a good spring. they have had to test each batch separately by coiling it into springs. Wire that fails this test is coiled again using more lenient settings until it passes or until it is judged too poor for spring making.

A device called the "fracmat" should do away with this batch-processing. Developed in Britain by Ian Stewart, his team at Warwick University and the Spring Research and Manufacturers Association, this allows single wires to be tested quickly and reliably. Fracmat comprises a pair of motors, a long rod and a laser micrometer all wired into a personal computer.

Wrapping a sample wire around the rod produces a long coil whose individual turns are variably spaced. This spacing is the tell-tale sign of the wire's quality: low quality wire is randomly spaced, higher grades more regularly. Plotting the distance between adjacent turns against the distance between the immediately preceding pair of turns produces a fractal which mimics the underlying structure of the wire - self reference again. Perfect wire would have turns with exactly the same separation, and the resulting fractal shape would be a point - which has no dimensions. Messy wire produces a smeared-out shape, which is wider and taller.

One of Dr Stewart's students, who missed out on the joys of spring making, was Keith Still. Mr Still has developed his own breed of fractal - the "orchid" - which can be used to model the way in which crowds leave confined spaces such as rock concerts and sporting events.

It is hard to model a crowd using traditional mathematics. Though a single person will leave a room simply by walking in a straight line to the door, it is much harder to say how 500, let alone 50,000, people will leave a football stadium. Traditional mathematics tends to collapse when faced with so many variables. The problem rapidly becomes too complex to solve in a reasonable time.

Basic orchid fractals behave like a well-ordered, rational crowd - one without the inherent confusion caused by people moving at different speeds, walking in the wrong direction or simply standing about. Of course, crowds are hardly models of good behaviour, so Mr Still added random elements, to simulate human characteristics, back into the system. The result is Legion, a system that can simulate a crowd of up to 250,000 people using orchid fractals.

Mr Still found what security managers at large events have long known: that those on the edges of a crowd surging to an exit will get to it more quickly. However, he also found that a triangle-shaped gridlock, with one apex at the door, spreads rapidly back into the room. Earlier models of crowds, which treated them as if they were solid lumps, or worse, fluids, had failed to spot this feature. So, surprisingly, had stadium designers. In fractal-speak, this triangular dead zone is awake, a point of stability in the sea of complexity. Dead zones can be moved - or new wakes created - and crowd movements increased by, counter-intuitively, adding barriers such as handrails or pillars.

The most speculative use of fractals is in foreign-currency markets. For many years, mathematicians have tried and failed to capture the intricacies of financial markets in mathematical models. But fractals do have some plausibility as a tool. Market movements seem to demonstrate the fractal trait of self-similarity. And the dealers themselves - a group of people all attempting to do the same thing (maximise profit, while minimising loss) look suspiciously, at least in mathematical terms, like a crowd of people making for the same exit.

Like a crowd, the individual actions of most buyers and sellers make little difference to the market as a whole. But big perturbations - central-bank intervention, for example - can act like pillars, creating a different fractal wake. So, in just the same way that Legion is used to predict how a virtual crowd will leave an as-yet-unbuilt stadium, Mr Still's system might be used to predict underlying trends in, for example, dollar-yen transactions.

Mr Still found that by piping 1994 and 1995 yen and dollar transactions through his fractals he could distil some kind of underlying order from the chaos of the market. Dramatic falls and rises - known, technically speaking, as discontinuities - in dollar-yen prices were anticipated by a jitter in his orchid fractals. Like a fire spreading through a building, bad news takes time - even if only a fraction of a second - to respond to. Those closest to the fire respond quickly, but the crowd as a whole takes time to adjust.

A basic principle of financial economics is that it is impossible, in any market that assimilates information efficiently, to predict the future price of a security on the basis of its past price. Nonetheless, says Mr Still, inefficiencies do remain: by looking at the behaviour of orchid fractals it may be possible to detect jitters that occur just before a discontinuity is reflected by the market, even though currency traders, surrounded by television screens and computer terminals, are inundated by real-time information. It is in that impenetrable forest of information that Mr Still hopes his orchids of knowledge will flourish, by telling people the only two things they actually need to know. When things are going up, and when down.

Source: The Economist 13 April 1996