Crowd modelling
Model behaviour

Mar 5th 2009
From The Economist print edition
Software: Simulating the behaviour of crowds of people, or swarms of animals, has both frivolous and important uses


New Line Cinema An army of orcs from the “Lord of the Rings” trilogy

THE warmongering orcs depicted in the “Lord of the Rings” trilogy are evil, unpleasant creatures that leave death and destruction in their wake. But if you find yourself in a burning building a few years from now, they might just save your life. That is because the technology used to make hordes of these menacing, computer-generated monsters move convincingly on screen turns out to be just what is needed to predict how crowds of humans move around inside buildings. Engineers and architects hope that they will be able to improve building safety by modelling how people behave in the event of a fire.

The simulation of the behaviour of crowds of people and swarms of animals (not just mythological ones) is also being applied to many other unusual situations, from designing better closed-circuit television (CCTV) security systems to managing the traffic of ships in harbours. The same technology has also been used to improve the understanding of archaeological ruins and to model entire ecosystems in order to design wildlife-management strategies.

When the first film in the “Lord of the Rings” trilogy was released in 2001, much was made of its heavy reliance on computer-generated imagery (CGI). But what was perhaps most impressive were the epic battle scenes, which broke new ground in special effects by showing huge numbers of characters with an unprecedented degree of detail and realism. For this the trilogy’s director, Peter Jackson, largely has Stephen Regelous to thank. Mr Regelous is the founder of Massive Software, based in Auckland, New Zealand. His firm’s software made it possible to generate as many as half a million virtual actors in a single shot, each behaving in an independent and plausible manner.


The same approach can also be used to model how people move through buildings

That is because every character was, in effect, given a brain, says Diane Holland, Massive’s chief executive. Each one was modelled as a software “agent” with its own desires, needs and goals, and the ability to perceive the environment and respond to the immediate surroundings in a believable way. Any given orc, for example, could work out which other fighters on the battlefield were in its line of sight, and hence whether it should flee or attack. This produced far more realistic results than orchestrating the motions of the digital extras in a scripted, choreographed way.

Nate Wittasek, the leader of the Los Angeles Fire Engineering Group at Arup, an engineering firm, was one of many people impressed by the realism of the battle scenes. A former firefighter, he realised that the same technology might be just what he had been looking for to model how people behave during a blaze—something that is increasingly being incorporated into the design of large buildings. Using computational models of crowds, it is possible to set up various scenarios and evaluate how the occupants move through the building.

The trouble is that the software that is used to do this generally treats people like particles in a fluid, says Mr Wittasek. “It assumes people behave like water flowing through a pipe,” he says. “They move at constant flow rates, heading for the nearest exits. But that’s not realistic.” Human behaviour is in fact far more complex and often quite irrational. When fleeing a fire people will often try to retrace their steps and leave the building by the way they came in, rather than heading for the nearest exit—even if it is much closer.
Send for the orcs

Similarly, on hearing a fire alarm many people do absolutely nothing. It is only when they see direct evidence of a fire, such as smoke or flames, that they act, says Mr Wittasek. How people respond to a fire also depends on their age, size and physical condition. Modelling people as a smooth-flowing fluid fails to capture such basic features, says Mr Wittasek. “We have all this great physics for figuring out how heat moves in a building, but what we lack is how people behave,” he says. “If we understand that better, then we can inform our designs better.”

So Mr Wittasek has been applying Massive’s crowd-modelling technology to building safety. The underlying software is essentially the same, says Ms Holland. Agents in both situations take account of what other agents around them are doing, for example. But for Arup’s purposes, several tweaks were added. In particular, agents were given the ability to find their way around an environment. In a five-second shot during a battle scene, an agent does not have time to learn anything. But a 45-minute evacuation scenario, says Ms Holland, is “an altogether different animal”. The agents need to be able to remember their surroundings, and to plan routes accordingly, as they navigate the environment looking for a safe escape. This means reprogramming the goal-seeking software that drives the agent. “The brain design of the movie agents focuses on how they will react to particular stimuli and situations, such as deflecting an incoming battle axe, and finding an enemy,” says Ms Holland.

The result is Massive Insight, a software package that makes it possible to create agents and program their behaviour preferences using simple graphical tools. The agents do not look terribly exciting: they resemble simple stick figures that move through a three-dimensional environment. But what really matters is how they behave, as far as Mr Wittasek is concerned. Although the figures do not appear to have legs, they move as if they do, becoming hindered in a stampede, for example, if others have fallen to the ground. The agents also have human-like vision and hearing, so they will only head towards an exit that they can see or remember. And they capture some of the subtleties of individual and group behaviour, says Mr Wittasek. People who have hitherto ignored a fire alarm are more likely to respond if they see other people around them heading for the exits, for example.



The software is still not quite ready for commercial use, but Mr Wittasek has been testing it using computer models of the newly redesigned Los Angeles County Museum of Art, and plans to do the same with the forthcoming Guggenheim museum in Abu Dhabi. So far this has just involved testing the software, says Mr Wittasek; the results have not been fed back to influence the buildings’ design. But it has demonstrated that the software does indeed work, and allows a range of different types of character to be modelled, from first-time visitors to the building (who are easily disoriented) to informed employees who can act as stewards and shepherd people to the exits. There is also a degree of random variation between characters of a particular type. “Their actions aren’t choreographed, so each time you run it you get different results,” says Mr Wittasek. This makes it possible to carry out timed evacuations and spot possible design problems that can hinder evacuation, he says. “It’s helping us to predict human behaviour, as opposed to predicting flow,” he says.
The wisdom of crowds

Taking a similar approach is Demetri Terzopoulos, a computer scientist at the University of California in Los Angeles. He is using agents to simulate the behaviour of commuters passing through Pennsylvania Station in New York. His agents have memory, but they also have a sense of time and the ability to plan ahead. An agent entering the station will typically seek out the ticket office, stand in line to buy a ticket, and then perhaps kill some time watching a street performer if he has a few minutes before his train arrives, says Dr Terzopoulos. If he is running late, by contrast, he may try to push his way to the front of the ticket line before sprinting for the platform.

Dr Terzopoulos’s research has shown that agents can simulate complex behaviours with great realism. Working with Qinxin Yu, a graduate student, Dr Terzopoulos has modelled how people behave in public when someone collapses. People crowd around to help, and some agents will even remember if they recently saw a police officer nearby, and run to get help, he says. Such realism is useful in the development of automated CCTV systems. Using real cameras for such research would raise privacy concerns, so he is making agent simulations available instead to researchers who are training cameras to detect unusual behaviour. Another intriguing application is to help archaeologists study ancient ruins. Using a model of the Great Temple of Petra in Jordan, Dr Terzopoulos has evaluated how it would have been used by the people who built it. He has concluded that the temple’s capacity had previously been greatly overestimated.

Agents need not even represent humans. Massive has been working with BMT Asia Pacific, a marine consultancy, to model the behaviour of the thousands of ships operating in Hong Kong harbour. This involves simulating the behaviour of the ships themselves, each of which may be under the control of several people, says Richard Colwill of BMT. And rather than assuming that everyone will adhere to the maritime traffic code, which determines who has right of way, it can incorporate acts of bravado and incompetence. “We get about 150 collisions each year in Hong Kong,” says Mr Colwill. His firm plans to use the software to determine which traffic-management strategies will be least disruptive during the construction of an immersed road tunnel that will need to be lowered into the harbour.

The technology can also be used to model animal behaviour. Massive is working with researchers at the University of Southern California (USC) School of Cinematic Arts and the Wrigley Institute for Environmental Studies, both in Los Angeles, to model animal behaviour on the conservation island of Santa Catalina, 20 miles off the coast. One aim of the research is to develop effective culling strategies for the island’s bison population. These were introduced 85 years ago to make a silent movie and have since overrun the island and damaged local vegetation, say Eric Hanson, a professor at USC. The software will also be used to model other mammals and birds on the island.

As agent software becomes better able to capture complex real-world behaviour, other uses for it are sure to emerge. Indeed, this could soon become a crowded field.

http://www.economist.com/...d=13174313

I'm gonna wait and read this post when it comes out in paperback...