By Ian Stewart (1998)
'I know who you are.' Jack Cohen, an avid science fiction fan and freelance alien designer, has just been introduced to my new research student. 'You're Hari Seldon.'
Jack is referring to Isaac Asimov' s science fiction series Foundation, in which Seldon was the genius behind 'psychohistory' - a mathematical scheme for predicting the behaviour of large groups of people. But Seldon was frail, bald, and walked with a limp, whereas G. Keith Still is solidly-built biker and vigorous with short dark hair. Nevertheless, Jack has a point, for Keith shares Seldon's fascination with the mathematics of 'the human conglomerate'. And his own entirely factual scientific brainchild is Legion, a method for predicting crowd movements which would have turned Hari Seldon's bright blue eyes green with envy.
Why would anybody want to predict crowd movements? Over the years there have been a series of major disasters involving crowds. In the UK the most notorious is the Hilisborough disaster of April 1989, where 96 people at a soccer match were crushed to death against barriers that had been intended to protect them. The problem arose when a large crush built up around the entrance before the match, and the main doors were opened, funnelling the crowd into an already packed stadium. An effective technique for modelling crowd flow would make it possible to test alternative barrier configurations, eliminate dangerous ones, and anticipate possible problems and work out ways of handling them safely.
After several years of intense effort, Keith has finally created a system that predicts crowd flow patterns. He originally called it Legion: 'my name is Legion, for I am many.' I recognize the quote as being from the Bible (where it actually reads 'for we are many') but Keith tells me that he stole it from the cult TV science fiction series Red Dwarf. Legion can model sports stadiums, railroad stations, supermarkets, airports, high-rise city blocks, and cruise liners. Architects can use it to work out how people will move through their buildings, even when they exist only on paper or in a computer's memory, allowing them to pinpoint problems and eliminate them before a brick is laid. Organisers of rock concerts can use it to experiment with layouts for safety barriers, to find ones that really do improve safety.
In fact, it was a rock concert that started it all. 'I remember the exact moment my life changed,' Keith tells me. 'It was 4 o'clock in the afternoon on 20 April 1992.' He had been stuck in the same crowd for four hours, at the top of the stairs outside gate C of Wembley Stadium, still waiting to get inside. Wembley, Britain's premier sports venue, is best known for hosting the annual Football Association Cup Final, the climax of the soccer season, but on this occasion Keith was there for the Freddie Mercury Tribute Concert for AIDS Awareness. And seventy thousand other people were there too, which is why Keith had been stuck for so long. The crowds weren't flowing very quickly.
Actually, he realized, that wasn't true. They just weren't flowing where he was standing. Keith started watching the flow patterns more carefully; they were moving in a funny flow pattern. He couldn't understand why he wasn't moving too. He thought that if he could figure it out he could get in more quickly.
People were coming up the embankment beside the stairs, flowing past him, and passing through the turnstiles. The turnstiles were creating a bottleneck, and Keith was in the middle of it. Had the crowd been sand flowing through an egg-timer, then out in the middle of the flow would have been the best place to be. Sand near the walls would be slowed down by friction; sand far away from the walls would flow fastest. But people, he suddenly realized, did not flow like sand. They moved fastest near the walls. And because they were moving, he wasn't.
Eventually he got in. And spent the entire concert watching the crowds, trying to work out what made them tick, trying to understand how they flowed. The next day he dug out the scientific literature on crowd flow. Everybody modelled it like the flow of fluids - or sand in an egg-timer. This assumption had the advantage that all of the huge literature on fluid flow, and the software for simulating it, could be brought to bear. The disadvantage was that the answers would all be wrong.
'That was the revelation,' Keith says.
Sitting on his desk was $40,000 worth of virtual reality equipment, which he had sold his car and re-mortgaged his house to buy, and he desperately needed to get some return on his investment. An idea struck him: why not simulate real crowd behaviour? There were plenty of potential markets for such a system - builders worried about fire regulations, stadium operators wanting to avoid dangerous incidents, designers of supermarket car parks.
So he started to rethink, from the ground up, the problem of modelling a moving crowd. It was hard. He didn't know the literature, he didn't know the vocabulary. He read everything he could find: crowd interaction, psychology, spread of fires, and 'egress theory' - which studied how people exit buildings in an emergency. He gave a talk about egress at the Fire Research Station in Borehamwood. 'They seemed to be impressed but I knew that my system was too rigid - it had too many rules.'
There had to be a simpler approach. 'At that point,' says Keith, 'I saw a TV programme on "Antichaos".' I nod knowledgeably: I had taken part in it. Antichaos is another word for Complexity Theory, a school of thought particularly associated with the Santa Fe Institute. My main interest is chaos: antichaos is its flipside. In a chaotic system, simple rules produce very complicated behaviour. In a complex system, simple rules generate 'emergent' behaviour, in which the whole somehow transcends the sum of its parts. Although the emergent phenomenon itself often seems simple - hence the name 'antichaos' - there is no realistic way to track its detailed causes. A standard example of emergence is the stock market, where the rational actions of individual traders can cause the entire market to crash unexpectedly, an outcome that none of them wants. Revolutions, political upheavals, evolution, the behaviour of ecosystems, the growth of living organisms - even consciousness itself- can all be viewed as emergent phenomena.
Keith realized that a crowd was a complex system, and that his attempts to simulate its emergent features were fully in line with the thinking out on the research frontiers. He was not alone, he wasn't crazy as many of his friends seemed to think, and there were people he could talk to. There were books to read - among them my own book about chaos: Does God Play Dice? This intrigued Keith: crowd movements look chaotic, but the message of the book was that there may be hidden order in apparent chaos. And one feature of the 'Antichaos' programme particularly fascinated him: the work of Craig Reynolds on 'boids', computer birds that flew in flocks as a consequence of a few very simple rules.
A flock is just a crowd of birds.
'Yes!' Keith shouts, demonstrating flocking behaviour with his hands. 'I was right!' But to him there was something funny about boids. He couldn't pin it down, but the rules didn't have quite the right feel.
The science was starting to hum, but the finances weren't. He needed a business plan, something to grab people's attention. What was the most emotive issue concerning crowds? There had just been an extremely nasty fire in Bradford City soccer ground, where an entire stand had turned into an inferno in less than four minutes. People had been killed, trapped in a dead end while trying to escape. Keith contacted the Fire Research Station and the Fire Services College at Moreton-in-the-Marsh. An article in the Times newspaper about his early crowd models secured a job with a company that made fire ventilation systems. There he developed the VEgAS system (Virtual Egress Analysis and Simulation) which modelled egress from burning buildings. It was runner-up for the Innovation of the Year Award for 1992. The steady job paid off his debts, but the nine-to-five atmosphere was no good for research. Worse, he had run into an apparently insuperable obstacle: his VR platform could handle only 225 people - not enough for a realistic crowd.
He needed more computing power, he thought. When the new ultra-fast Intel Pentium(tm) chip came on the market, he eagerly anticipated a big improvement, but to his disappointment the system was still only capable of handling 225 people. Keith didn't realize it at the time, but he was up against a notorious problem in computer programming: intractability. When the VR system 'moved' objects around it had to do so without them interpenetrating. It did this by checking each object against all the others whenever it was moved. So every time it updated the screen display it looked at every possible pair of objects. As the number of objects grew, the number of pairs grew much faster. For example with 10 objects there are 45 pairs, but with 100 objects there are nearly five thousand.
Many problems of this kind are 'NP-complete', meaning that everybody believes them to be insoluble, even though nobody can prove it. 'Fortunately I didn't know this,' says Keith, 'or I would probably have given up.' The surprise is that he didn't anyway, for at that point his life pretty much fell apart. He collapsed after a major presentation and spent a week in hospital. Then his wife left him. To cap it all, as soon as he returned to work his back went. Scar tissue from a previous operation to remove two disks had built up around his spine, trapping the spinal cord. He couldn't move his legs.
What happened next was a real-life Robert the Bruce experience. Confined to bed, lying flat on his back, his attention was drawn to a long cobweb dangling from the ceiling by a window, its shadow cast on a nearby wall. As the air circulated, complex waves travelled along the cobweb. What intrigued Keith was that the motion of the shadow seemed simpler than that of the web. Maybe you could understand some aspects of a complex system without knowing absolutely everything about it. Maybe the movements of crowds were 'shadows' of some other aspect of reality. He wanted to follow up that idea immediately, but stuck in bed all he had was his imagination, and he was forced to simplify his approach. This paid off in spades, because it dawned on him that people do not think about everything in the same building before they move - they can only react to what they see. They look at the empty space, and move into that. 'They only needed to check the stuff that wasn't there,' he says, with a strong sense of irony. 'That led me to a concept that I call "information space". To move objects efficiently in VR they shouldn't interrogate each other. They should interrogate the space around them to find out whether there's anything nearby that should be avoided.' Fine in principle, but how to make it work? After two months of painful recuperation Keith packed up his equipment, and walked out on his job. He went straight to Wembley Stadium and befriended the Operations Manager, Pat Carr. Keith showed Pat his VR demos and asked to be taught about crowds. 'He put me in the middle of a boisterous crowd - baptism by fire! 'This will teach you about crowds," he said. I survived - but only just. After that Pat realized I was serious about my research.'
Keith stared at black-and-white video footage from 48 CCTV cameras for hundreds of hours. One day he found himself on the roof near where he had been stuck at the Freddie Mercury concert - but by now he had studied so many crowds that he found himself doing time-lapse photography in his head, a fundamental shift of viewpoint. Breakthrough! It was as if each person left a kind of 'wake' behind them, a trail showing where they had just been. Instead of chaos, Keith saw elements of order. 'Military precision,' he says with satisfaction - which is appropriate, because he and Pat were soon to be joined by Mark Briggs of Event Security. Mark and Pat had both been soldiers, buddies in the Coldstream Guards where Mark had been awarded the British Empire Medal for bravery.
What kind of order did Keith see? 'Long lines of people passing between each other, patterns that broke up and reformed, broke up and reformed... For the next two months I watched video footage from security cameras, and realized that the same patterns would form in the same places, no matter what the event.' This told him that the key to crowd dynamics was not the intricacies of human psychology, but the universal mathematical patterns formed by individuals that moved and interacted with each other in some surrounding geometry. The geometry, in fact, was the most important feature.
The insights were coming now, but Keith's health was still poor and his mental state was somewhat overexcited. He ended up in a state of near exhaustion at his doctor's surgery, brandishing a copy of Does God Play Dice?, gibbering about 'Ian Stewart would understand.' He wanted to see me. The doctor told him to see a psychiatrist instead.
Keith grins, and tells me a Zen poem:
When the sky is clear, the sun appears.
When the earth is parched, the rain may fall.
You can open your heart and speak out,
But it's useless to talk to pigs and fish.
'The trouble was, I was talking to pigs and fish.' He was trying to talk mathematics to non-mathematicians. 'It was like talking a foreign language that I didn't understand - bits of things would make sense to people I talked to, but not the big picture.
The real problem was my math - it was too static.' He needed to find a new kind of geometry, one that would represent not just what a crowd was doing at one instant, but its entire history.
A new geometry...
March 1994 brought an article in New Scientist magazine about something called symplectic geometry, one ingredient of chaos theory. 'Symplectic' just means 'complex', but its mathematical associations are those of the complex numbers, in which minus one has a square root. In symplectic space a line is always at right angles to itself. Symplectic geometry includes velocities as well as positions, it is a geometry of motion. Well, he needed a new geometry, and since this one was on offer... He entered some sample formulas into his computer, trying to use symplectic geometry to model the motion of individuals in crowds. Suddenly, on the screen, in vivid colour, growing before his eyes, were the most striking, mysterious, and downright beautiful images that he'd ever seen. There were hundreds of them, thousands, millions. Every new 'seed' number that he fed his computer produced a new and different image.
'It's life, Jim, but not as we know it.'
Human crowds do not flow in beautiful, intricate mathematically regular patterns. This was some kind of idealized mathematical crowd flow, in which the individuals used fixed formulas to make their decisions instead of sizing up their surroundings and lunging into the most likely gap.
The images, he realized, were fractals - shapes with a detailed structure on all scales of magnification. Benoit Mandelbrot's concept of fractals, and his computer-generated images, were famous worldwide, but these looked new and different. Keith initially called them 'orchid fractals' because that's what the first one looked like, and he formed a spin-off company to exploit them. It was called FMIG Ltd - 'Fast Moving Interactive Graphics,' he insists with a straight face, though the scuttlebutt offers a more colourful interpretation. Orchids didn't solve the crowd problem, not on their own, but they had the right flavour, and Keith saw their discovery as a huge step forward. Finally he had caught a glimpse of the right mathematical framework.
One thing orchids did was open his eyes to a useful way to program the geometry of crowds. He had been reading and writing information to the computer's screen display, mainly because it was the biggest chunk of free memory around. But now he watched that information assembling itself into geometric patterns. Typically orchids would begin by looking chaotic but end looking ordered. They were a form of self-ordering system, like those studied in complexity theory. Their order came solely from the interactions of the individuals - there was no overall master plan.
It was a vital clue to the self-ordered patterns that flickered into existence in a crowd, only to disappear again...
It was like boids, self-organizing into flocks, sweeping majestically round virtual obstacles in their self-contained computer world, breaking and reforming... It was the shadow of the cobweb.
At last having something tangible to demonstrate, he arranged to talk to me. I remember the meeting vividly. Keith brought sheaves of wonderful images... a program that let you create your own orchids, swirling madly and colourfully over the screen, growing before your eyes... and some crazy idea that all this had something to do with crowds. I played with the orchids, I saw things that reminded me of chaos theory and other things that reminded me of absolutely nothing I had ever seen before. We got quite excited, but after Keith had left it seemed to me that something was lacking. I just couldn't see any connection with crowds. So I wrote him a letter, which he treasures - it enshrines what is probably the biggest blunder of my scientific career. So far. '"I can't see it leading anywhere interesting in a mathematical sense," 'Keith quotes gleefully from memory. I look suitably sheepish. 'I was devastated when I read that,' he continues. Then he grins. 'But only for a few minutes. I realized that I couldn't have explained it properly.'
We stayed in touch, on a casual basis. I busied myself on other things; Keith kept plugging away at crowd dynamics. At Christmas he flew to the USA to visit his friends Jeanette and Michael Crawford, but on New Year's Eve he ended up in hospital - a complication from previous operations. When he had recovered enough, Jeanette and Michael took him up a mountain to watch the golden eagles. 'There I sat, doped to the eyeballs with medication, while some eagles collectively attacked their prey. "Magnificent," I thought. Then I suddenly understood that despite the complex organization of their behaviour, it was self-organized from simple rules for individuals and interactions. "Wow! It's not just crowds. Simple internal rules can generate complex behaviour in all of nature, all things."
Watching the eagles, Keith saw what had bothered him about 'boids'. The rules for boid movement included, in mathematical guise, the explicit instruction 'form a flock'. But that wasn't what real birds did. They didn't know they were supposed to form a flock - they just did it anyway. Their flocking behaviour emerged from interactions between individuals, it wasn't built in as a common objective. And the same was true for the patterns of movement in crowds. He needed to develop boid-like systems of rules, but without explicit flocking instructions, and make them fit the behaviour of people.
By early 1995 he was back in the UK, now in possession of all the pieces of the puzzle. Fitting them together was still technically tricky, but it was clear what the general structure of the system should look like. In the abstract, it was exactly like the rules that generated orchids - and that was the connection with crowds. Orchids were a form of alien crowd life, generated by the right kind of mathematics but using the wrong rules; crowds were generalized orchids. He realised that the name was wrong, these were xenofractals, they changed structure as they developed.
What is the common structure? It has several parts. All individuals have some kind of objective - such as 'get as near as possible to the stage' or 'go to the bar'. They have form: size and shape. They have internal variables such as maximum and minimum speeds - senior citizens do not move as rapidly as teenagers. They obey rules of interaction - stay out of everybody else's 'personal space', try to take a step in roughly the right direction. Finally, and crucially, they function within an environment - the geometry of the surrounding building. The dynamic patterns of crowd movement must somehow be created by this structure. Crowds aren't random, and they aren't chaotic: they are emergent.
The idea was not confined to crowds. The same abstract structure applied, with suitably modified rules and terminology, to almost anything. Individuals, groups, ecologies. Evolution. Cars on a freeway network. Baggage in an airport. Trolleys in a supermarket. The movement and division of cells in a growing organism. Stock market transactions. The idea was vast in concept, but it was still woolly round the edges. Computational intractability was the main obstacle - what use is a model of crowd flow that can only handle a few hundred people? Keith was excited, but I remained unconvinced.
What cracked it, for me, was a curious side issue - a practical application of XenoFractals that had absolutely nothing to do with crowds. Keith realized that they were an ideal security device for checks and similar documents. The key was the enormous diversity of XenoFractals: each 'seed' number produced a totally different fractal image. Suppose you took all the data on a check - name of payee, amount, date, whatever. Encode it into a seed number, together with the coordinates of a tiny 'window', the size of a postage stamp compared to a XenoFractal the size of the galaxy. Use the seed to generate an fractal image and view it through the window: draw the result on the check. if anybody tampers with the check, they have to redraw the corresponding image. But if they don't know the rules - and those, although simple, are a commercial secret - then they can't work out what the image should be. And working backwards by analysing the images for checks with known entries seems to be a non-starter - literally like searching for a postage stamp in a galaxy.
At that time I had become involved in the launch of a new satellite TV channel, European Business News. My role was to present short science items with a business slant. Keith's xenofractal security method was just what we wanted, so we put a short program item together.
Now I started taking xenofractals very seriously indeed: I could see their potential, even if I was still unsure about their relation to crowds. Keith talked to me during the program and revealed some of his new discoveries; shortly afterwards, I signed him up as my research student at Warwick University. There wasn't actually much work for me to do, but it cemented our professional relationship and gave Keith the right to talk to me, and anybody else at Warwick, regularly.
As things turned out, it was scarcely necessary, although Keith reckons it did help preserve his sanity. The first time he came to see me, he had solved everything. His ideas on 'information space' had gelled into a software package - Legion. Legion could handle crowds with a quarter of a million individuals, in real time. He had stripped the whole problem right down to its basic elements. The people and their surroundings were stored in computer memory. Each person (Keith prefers 'entity') could interrogate its information space (Keith's term is 'fractal landscape') and decide whether it was another person, a wall, or just empty space. Then it would react accordingly. The rules of movement were simple but clever, based upon thousands of hours of observations of real crowds. Each simulated person was equipped with some idea of where they wanted to go. Different people might have different objectives, and those objectives could change with time - for example half an hour after visiting the bar they would want to visit the bathroom. Each individual would navigate through information space towards its objective, trying not to bump into anything along the way.
The beauty of the idea is that the immediate vicinity of an individual is the same size whether there are ten people in the crowd or a million. This means that the computation of interactions with other objects is proportional to the size of the crowd: it does not grow far more rapidly, as it did in the VR routines he had been using.
This is how Keith's Algorithm gets round NP-completeness. In crowds, the key interactions are short-range.
Keith's Algorithm had turned into a fully-fledged design tool called Legion. The user can set up the geometry of the building; determine objectives for each person in the crowd; adjust internal functions to suit different types of crowd - children, elderly people, mothers with babies; choose how many of each; determine how fast they can move and react. The system plots out the crowd flow and monitors any interesting variables. In particular it works out the 'space utilization' - how many people visit a given region of floor in a given time. Space utilization is important in commercial applications because areas that are seldom occupied are, in effect, wasted space. You can change the building's geometry and see what effect it has on the crowds. Or, having packed your building with people, you can simulate an emergency, watch them evacuate the building, and see how long it took them and whether any dangerous jams built up. If the result is unsatisfactory, you re-design the layout accordingly and try again - the ultimate 'what if?' design tool.
One surprise is that although the motion of any individual in a real crowd is irregular and unpredictable, simulations show that the overall flow pattern is remarkably insensitive to changes in individual behaviour. For example 'intelligent' and 'random' strategies to find the best place to move to next produce virtually identical overall flows, even though individuals are moving according to very different rules in the two cases. The main determining factor turns out to be the geometry of the building. This is analogous to fluid flow in one respect: a real fluid is composed of many individual molecules, which bounce off each other erratically. The flow pattern modelled by the mathematician's equations does not describe the motions of the individual molecules: it describes the overall flow, and again it is the geometry that matters.
Legion has already been used commercially, for example to model crowd flow in a typical station on the London underground. The study was commissioned by Westinghouse Cubic Ltd (now Cubic Transportations Limited), who make ticket barriers for such stations. The mathematical model was calibrated against many hours of video footage to check whether the simulations corresponded quantitatively to the actual flows. They did. 'Look at these,' says Keith, handing me a sheaf of photos of people passing across the station's tiled floor. 'Every one of them stepping on the exact same tile that we predicted.'
Legion passed another test when it simulated a crowd leaving a Bon Jovi concert at Wembley Stadium and predicted that the pitch would take 14 minutes 30 seconds to clear. The actual time taken was 15 minutes. This feat becomes more impressive when you realize that the pitch clears only when most of the crowd have already made their way through the complex geometry of the surrounding building.
The kind of insights that come out of the work include ways to speed up flows by - paradoxically - putting in extra barriers. (Usually the problem is to slow down the crowd without it building up to dangerous densities, but for emergency evacuation speed is essential.) Extra barriers - suitably positioned - improve the flow because each person in a crowd creates a virtual wake behind them, a space that the person behind can move into, thereby creating another space behind them, and so on. However, this wake is interrupted if somebody moves in from the side. People beside a barrier experience fewer interactions - the barrier protects them from being jostled by others on that side. So with the right barriers in place, the crowd splits up into long, rapidly moving chains of people. A central barrier in front of a fire door can increase the flow by up to 75 per cent if you know where to put it.
Another discovery is that the speed of flow through a door is nonlinear - it is not merely proportional to the door's width. In fact a one-foot increase in the width of a door can double the flow rate through it. And Myriad has correctly predicted how front-of-stage crowds build up at rock concerts and the 'dead zones' created by obstacles such as sound stages in the auditorium.
Legion, and his later analysis suite, Myriad, is an architect's, and insurer's, dream - an entirely practical tool for taking a building, real or under design, and trying different configurations of passages, doors, and barriers to see what keeps the flow of the crowd safest.
Moreover, Myriad is compatible with commercial VR, CAD, and drafting packages. Previous methods were mostly inspired guesswork and a lot of hope, based on limited experience; nothing remotely as effective existed before Keith discovered the key mathematical structures for describing crowd flow as a complex system and analysing it efficiently by computer. And the theory behind Myriad offers the potential for making ever more accurate predictions of crowd behaviour. By retaining the same overall structure, but adapting the interactive rules, it will be possible to develop equally accurate models of many other complex interactive systems in the real world - such as shoals of fish feeding in an ocean - and model them in real time.
One day, soon, it will become a legal requirement that all new architectural designs must be tested in simulation for emergency egress before construction starts. Architects already walk through VRML models of new buildings that exist only inside their computer. Soon they will be accompanied on their travels by a veritable Myriad of virtual companions, and they will be able to experience exactly what would happen if their brainchild caught fire, or if a barrier collapsed under the weight of numbers as crowds of teeny-boppers struggled to greet their latest idol at the airport.
Hari Seldon's words in Prelude to Foundation sum up's up Keith crowd models perfectly:
'A tool that might make it possible to identify what was good and what was bad for humanity. With it, decisions we would make would be less blind'.
***************************************************************************************************
Since this article was written several development tools have been created and Keith now focusses on teaching and training crowd managers. His courses are run around the world. Keith he developed, and ran, an MSc in Crowd Safety and Risk Analysis. Ssee www.CrowdRisks.com