The role of computer animation in visualizing the behavior of simulation models of complex processes and systems is described. The results of a demonstration project applying this technique to transportation planning are reported and analyzed. The study involved the modeling and display of passenger flow in a subway station. It was carried out by using SIMULOGO, a new discrete-event simulation language, and ZAPP, a new computer animation system, which are discussed in the paper. Planned extensions and elaborations of these facilities to provide a comprehensive and responsive environment for transportation systems modeling are outlined.
IN February 1974, the Ontario Ministry of Transportation and Communications awarded the first phase of a contract to the Toronto industrial design firm of Kuypers Adamson Norton Ltd. (KAN) with the intent of achieving a method of defining and evaluating those aspects of the physical environment in transit systems that affect passenger behavior. This method was to be used as a basis for potential improvements in efficiency, safety, and comfort of passenger travel. We, in the Computer Systems Research Group, were in turn asked by KAN if the computer animation techniques we had been developing could make an additional contribution to this goal. Therefore, we performed the demonstration project discussed in this paper. However, the paper attempts to go beyond this specific project and explore the role of computer-animated simulation models in transportation planning.
Simulation is the physical or mathematical modeling of a hypothetical or real structure, process, or system. The model is a representation or imitation of that system. It usually abstracts or emphasizes particular characteristics of interest. It is often dynamic; that is, it exhibits the system's changes through time.
Reduced-scale physical models of airplane wings are placed in wind tunnels to study the effect of their shape on turbulence and vorticity. Ball-and-stick models of molecules are used by chemists for visualization purposes in research and teaching. Mathematical models are often expressed as differential equations or as finite difference equations. They may be deterministic, in which case the outcome is completely specified by the inputs; they may be stochastic, in which case the outcome is partially determined by chance.
The implications of mathematical models are most easily derived by expressing them as computer programs. These programs are called computer simulation models [1] [2]. Deterministic computer models have been used to simulate the dynamics of the solar system and of man-made satellites. A joint project of the Massachussetts Institute of Technology (MIT) and the Club of Rome recently developed a computer model of world growth expressed in terms of five basic elements and their interactions: population, agriculture, natural resources, industrialization, and pollution [3]. Stochastic computer models are often used to simulate job shops and computer systems.
Models facilitate the understanding of complex processes. They are used to predict and to control the future. They allow the alternative designs to be evaluated before a system is built and the implications of proposed system changes to be studied in advance. One need not make a real change to see what happens; disastrous consequences of a suggested course of action can be predicted and avoided.
Furthermore, models facilitate the rational discussion of complex processes by policy makers and planners by providing a medium in which assumptions must be made explicit so that they are accessible for debate and further analysis.
Animation is the pictorial dynamic modeling of a hypothetical or real structure, process, or system. An animation sequence is a series of pictures that portray the system's dynamic behavior through time. Hence animation is a useful cognitive tool for visualizing and aiding the comprehension of complex processes. Since its inception, conventional animation has been plagued by the high costs and slow turnaround that result from producing 24 individual frames/sec of film. Reducing this burden is one of the goals of computer animation. Computer animation consists of a variety of techniques and processes in which the computer assists in the production of a movie [4] [5].
In one common process, the animator constructs a movie by writing a program in a language containing picture-generating subprograms [6]. This program produces a magnetic tape that contains an encoded description of images and motions. Another computer then interprets the tape and draws the images on a cathode ray tube, from which they are focused onto film.
In another computer animation process, a sequence can be created and viewed in real time directly at an interactive graphics terminal [7] [8]. The animator defines, either free-hand or algorithmically, the images, movements, and dynamics that make up a film; the computer immediately plays back the resulting movie for evaluation. Thus animation for the first time becomes spontaneous and immediate.
The temptation to integrate computer simulation and computer animation capabilities into one system is compelling [9] [10]. Visual sequences depicting the behavior of a system could then be produced semiautomatically from the model. One could literally see the model behave. This would aid in validating the model and also deepen the modeler's intuition and understanding of the underlying system.
These animation models could be produced and used in two very different ways. First, the animation can be displayed directly at an interactive graphics console. This aids significantly in tuning the model. Various hypotheses may quickly be explored, and flawed ones rejected. Second, the sequences can be recorded on film. These hard copy visual records are useful forms of model documentation and aid further discussion, analysis, and evaluation by planners and policy makers.
Transportation systems consist of large collections of moving entities such as people, vehicles, and goods. Movements of the component entities are governed by, or may be described by, a complex set of rules or interactions. These rules may be expressed in terms of such phenomena as individual preferences, routing decisions, signaling and switching mechanisms, equipment availability, and resource allocation strategies. Transportation planners attempt to optimize these systems in terms of performance criteria such as minimizing cost, maximizing flow or system use, or maximizing passenger happiness, safety, and comfort.
Clearly such systems are complex both in space and in time. Hence computer simulation models would seem to be an appropriate tool for expressing characterizations of transportation systems, and animated representations would seem to be useful for visualizing, comprehending the structure of, and refining these characterizations ([11] [12] [13]).
We attempted to model the one-way passenger flow pattern observed during morning high-density periods in a portion of the Bay Street subway station in Toronto. This study was carried out as a small contribution to the KAN undertaking mentioned earlier in the paper. KAN gathered the data, and we used and suggested some of the initial explanatory hypotheses. In discussing the model, we intend neither to present it in detail nor to claim its validity; its use here is only to serve as a specific example with which we can present and discuss the simulation and animation techniques.
Our model deals with the following aspects of passenger movement in the station: A train arrives; passengers disembark from one of a set of doors, proceed along the platform, make a level change by a staircase or an escalator, and finally choose one turnstile by which to depart from the station.
The model is discrete and stochastic. The former implies that state changes are computed only at significant instants in the simulation. The latter implies that these state changes are in part determined randomly.
The only active components of the simulation are the trains and the passengers. Each of these is modeled as an independent process. In the context of one station, trains simply arrive, open their doors, and depart. Disembarking passengers exhibit a little more behavior, however. Their actions as they move through the station are structured in the following ways.
Passengers are created while on the train. At that time they are assigned (based on some subjective observations of real stations) an attribute indicating their desire to move quickly through the station. In the model this is called speed even though it is used to modify their strategies as well as their basic velocity.
In choosing which train door a passenger exits from, several assumptions are made. It is assumed that faster passengers will attempt to optimize their strategy and, therefore, will tend to exit through doors closest to the level change. Slower passengers are assumed to use little strategy and, therefore, are distributed uniformly across all doorways.
After choosing a doorway, the passenger requests use of that doorway. The model of the doorway is such that only two passengers may occupy it at once, and a maximum rate of 1.5 passengers/sec is achieved.
Passengers are assigned a time to move along the platform to the level change based on their speed and their distance from the level change. Although a weak attempt was made to simulate the effects of crowd congestion by using a penalty scheme based on the number of train doors ahead of a passenger, passenger-to-passenger collision avoidance was not simulated.
The general assumption made at the level change is that all passengers will use the escalator instead of the stairs if the difference between escalator queue length and stair queue length is small enough. A second assumption is that faster passengers will tend to take the stairs more often; i.e., they will take the stairs even when the difference between the escalator queue and the stair queue is very small. The queues result from the specific rates that are enforced for both the stairs and the escalator.
The time for moving up the stairs or escalator is a function of the passenger's speed and the loading of the device.
In the current model, passengers choose which of six turnstiles to use as soon as they reach the top of the level change. This choice is based strictly on the observed distribution at the real station, a model that yields unnatural queuing because the queue length is not a factor in the decision. A potentially better strategy, to be used in the next pass at the model, will make the choice functional of queue length and turnstile desirability, the latter being an indicator of how close the turnstile is to the passenger's most direct path to his or her destination.
The computer simulation model was developed, and three sets of data were run through it. The results are visualized in the following films:
The visual output from the first run pointed out some weaknesses in the model.
Sample frames from films 1, 2, and 3, in which the model is run with two trains discharging passengers, are shown in Figures 1, 2, 3, and 4. The animation technique is further described later.
The method used to carry out the demonstration project is described in what follows.
A computer simulation model is generally expressed as a program written in a computer language. The use of a special-purpose simulation language facilitates the development and realization of the model. We have developed an extremely useful, yet simple, new modeling language, SIMULOGO [14]. SIMULOGO is a simulation extension of LOGO, a student programming language developed at MIT. and Bolt Beranek and Newman, Inc. ([15] [16]). SIMULOGO is described later; the Bay Street model expressed as a SIMULOGO program is in the Appendix.
The publish paper does not include an Appendix.
Execution of the computer simulation produces a time trace, that is, the details of all relevant aspects of system behavior through time. The trace is then used as input to another computer program, this one written in the ZAPP language. ZAPP, the zoom-animate-pan package, is a system for the production of computer-animated films ([17] [18]). The ZAPP program produces a film showing the model behaving through time.
SIMULOGO was designed as a simple but extremely useful tool that could be used by students in designing their own simulations. The premise was that more is to be learned by writing a simulation than by using one. The resulting language turned out to be more than a good student language. Because it is easy to learn and read, it is useful for real problems involving communication with non-computer-oriented designers. With relatively little instruction, a transportation planner should be able to converse directly in terms of the SIMULOGO model.
The SIMULOGO subway station model is available in Xerox form at cost of reproduction and handling from the Transportation Research Board. When ordering, refer to XS-63, TRR 557.
LOGO is an interactive conversational language. The user enters commands by a computer terminal; the LOGO machine executes them, carrying out the appropriate action. If the user enters TYPE 'HA HA', the computer responds by typing HA HA.
The user may also define new commands or procedures as they are called. For example,
TO LAUGH
10 TYPE 'HA HA'
20 TYPE 'HO HO'
This procedure definition extends the repertoire of actions the computer can carry out. From now on, when the user enters LAUGH, the computer responds with HA HA and HO HO. Furthermore, these new commands can be used to define still other commands. For example,
TO LAUGH A LOT
10 LAUGH
20 GOTO LINE 10
This procedure will continue in an infinite loop typing 'HA HA HO HO' until the escape key is hit.
LOGO procedures can have arguments and may return a value, e.g., SUM OF 5 AND 6. In this case, 5 and 6 are taken as arguments, and the value 11 is returned. Note that OF and AND are noise words and are only added for readability. The value returned by SUM may be used as an argument for another procedure, e.g., TYPE PRODUCT OF 10 AND SUM OF 5 AND 6. At the terminal, 110 is typed.
Note that, in the subway station example, several procedures are defined. TWO_TRAINS behaves like a command and is used to start the simulation. The procedure PLATFORM TIME DISTRIBUTION takes three arguments, DOOR, SPEED, and DIRECTION, and returns a value functional of these arguments by the OUTPUT command. Each such value is the length of time spent on the platform by a particular passenger (emerging with a given speed from a given door from a train moving in a given direction).
LOGO deals with two kinds of data, words and sentences. A word is any character string not containing a blank. A sentence is a sequence of words separated by blanks. Data are included literally in program text by enclosing them in single quotes. (Integer numbers are an exception; they are words that do not need to be quoted.) Thus 'HA', 'DOOR', and 2 are words, and 'HA HA' and '17 11 5' are sentences.
Any LOGO word may be a LOGO variable. The command MAKE performs the assignment of a value to a variable; e.g., MAKE 'ESCALATOR LOAD' 0 causes ESCALATOR LOAD to be a LOGO variable with value 0. To get the value of a variable, one encloses it in slashes, i.e., /ESCALATOR LOAD/. This would return a 0.
Two concatenation procedures exist in LOGO, WORD OF, and SENTENCE OF. The former takes two words and combines them into a single word; e.g., WORD OF 'BREAKPOINT' AND 'FAST' returns 'BREAKPOINTFAST'. The latter combines words into sentences or sentences into longer sentences.
Conditional branching and looping within the program is done by a truth flag. Consider the following example taken from the object TRAIN:
30 passenger starting loop
32 .....
34 DECREMENT 'PASSENGERS' BY 1
36 TEST GREATERP/PASSENGERS/0
38 IF TRUE GOTO LINE 30
The function GREATERP takes two numeric arguments and returns the value 'TRUE' if the first is greater than the second, 'FALSE' if it is otherwise. The command TEST sets the LOGO truth flag according to the value of its single argument. 'IF TRUE' simply checks the truth flag and, if it is 'TRUE', executes the remainder of the statement. Thus, if the value of 'PASSENGERS' is 90 when this loop is first entered, then line 32 will be executed 90 times.
Note that comments (nonexecutable statements) are delimited by asterisks; e.g., *this is a comment*.
Processes are used to simulate those things that are active in a simulation. Each passenger and train in the subway simulation is represented by its own process. Processes appear to execute in parallel and asynchronously. A process consists of a procedural statement that defines its actions and some private data that contain its attributes. For example, each subway train has certain actions that may be described procedurally and that are common to all trains. It also has some unique attributes such as direction and number of passengers. A single SIMULOGO process definition (OBJECT TRAIN) is sufficient to describe the behavior of all trains in the model. Similarly, each passenger's behavior is described by the program OBJECT PASSENGER although each passenger will be characterized by his or her own values of direction, speed, and doorway of train exit.
Processes are defined in the same way as commands or procedures. For example,
OBJECT PASSENGER
10 )
20 )
. ) SIMULOGO statements describing
. ) the action of a passenger
. )
END )
Processes are created by using the primitive 'NEW'. Thus the main program (TO TWO_TRAINS) creates a station process (OBJECT BAY_STATION) and two train processes (OBJECT TRAIN). Each train in turn creates the requisite number of passenger processes (OBJECT PASSENGER).
When created, processes are passive. To become active, they must be scheduled in the agenda with an activation time. The agenda is a queue of processes ordered according to the time of next activation. In the Bay Street model, all processes are scheduled when created. For example, START A NEW 'TRAIN' 'EAST' '115' AT NOW causes the eastbound train to be activated immediately; that is, at the current instant of simulated time. However, START A NEW 'TRAIN' 'WEST' '90' AT 20 causes the westbound train to be activated 20 units of simulated time later. Active processes are made temporarily passive by using the WAIT command. These intervals where the processes are suspended correspond to regions of the simulation between decision points, such as moving along the platform or up the escalator.
Another mechanism, the RESOURCE, exists in SIMULOGO for process activation and control. A RESOURCE is simply a variable representing how many units of acertain resource are available. Two special operators manipulate these variables. REQUEST 'resource' checks if any of the resource is available. If so, it decrements the variable by 1, and the calling process continues. Otherwise, the process is suspended and enters a queue waiting for the resource. RELEASE 'resource' increments the amount of the resource available. If processes are queued up for the resource, it restarts the first one.
Resources are used in the simulation to enforce flow restrictions. The entrance to the escalator can be considered a resource of value 2 since two people can enter it at a time. The following sequence, executed by each person getting on the escalator, enforces a fixed rate of two passengers/sec:
.
.
.
430 REQUEST 'ESCALATOR'
432 WAIT 1
433 RELEASE 'ESCALATOR'
.
.
.
SIMULOGO has several built-in procedures that behave as random variables, including DISCRETE 'sentence of numbers'. This returns an index into the histogram distribution indicated by the sentence of numbers; e.g., DISCRETE '10 80 10' returns the numbers 1, 2, or 3 with probabilities 0.10, 0.80, and 0.10 respectively. In addition, NORMAL 'mean' 'standard deviation' returns a value from a normal distribution.
Although the reader lacking extensive computer experience will not be able to understand, solely on the basis of the prior discussion, all the details of the SIMULOGO program included in the Appendix, its basic structure may be comprehensible.
The sample main program, TWO_TRAINS, first activates an instance of BAY_STATION, and this sets up most of the specific numerical assumptions embodied in one run of the model. The MAKE command at line 810 of BAY_STATION, for example, initializes the ESCALATOR resource to a value of 2. TWO_TRAINS then activates one instance of TRAIN, and then, 20 sec of simulated time later, a second instance of TRAIN is activated. These trains in turn activate 115 and 90 instances of PASSENGER respectively. (This happens at line 32 of TRAIN.) The PASSENGER program is structured to show the five phases of passenger behavior discussed previously.
Although SIMULOGO is used as an interactive conversational language, the current implementation did not facilitate direct inclusion of animation capabilities. Hence a time trace of all relevant events occurring in each simulation run was output from SIMULOGO via the RECORD, WRITE, and HISTORY commands, as can be observed in the Appendix.
These data were input to a specially tailored ZAPP program that produced the movie. The ZAPP program contained all relevant aspects of station geometry including locations at which passenger events occurred, for example, the foot of the stairs. The ZAPP program carried out a graphical simulation in which it tracked the motion of each train and each passenger through time, interpolating positions between events where required. It finally produced an encoded snapshot of the modeled environment for each twenty-fourth of a second of simulated time. These encoded snapshots were transferred to 16-mm movie film by the special software that drives our microfilm recorder. The resulting film exhibits spatial and temporal properties roughly corresponding to behavior observed in the station.
The evolution of the model and the film demonstrate the sense in which a graphically mediated computer simulation system provides an environment for the rational discussion of transit phenomena and a tool for evolving a more precise understanding of them ([19]). Animating a model enables us to visualize intricate spatial and temporal relationships that result from a complex set of assumptions. It is difficult to imagine any other presentational technique that provides equal assistance toward visualization, comprehension, and insight.
As our understanding of the simulated phenomenon increases, this understanding is documented specifically and openly in the model and is subject to further analysis and debate. Insofar as the model can be substantiated as valid, it can then be used as a predictive tool to aid policy decisions, for example, in determining whether six turnstiles are required or three are sufficient in a particular site.
We are making no claims for the completeness or validity of the current model. Rather we stress the model's deficiencies and our ability in the simulation language to explore new hypotheses for correcting these deficiencies.
The original SIMULOGO model itself was written in about a day; simple corrections and variations can usually be expressed in minutes. For instance, the change resulting from observing that too many people wait for the stairs even though the queue for the stairs becomes longer than that for the escalator was carried out by a slight alteration to the procedure BREAKPOINT. The variations in which three turnstiles were closed were carried out by setting three of the numbers in line 610 of OBJECT BAY_STATION to 0.
This ease of use does not currently apply to variations in station geometry or to the graphical representation used. These are embedded somewhat rigidly in the animation program, and moderate changes would take hours rather than minutes. Furthermore, the separation of the simulation and the animation in two separate computer systems causes redundancy and awkwardness of expression.
Experience in the demonstration project suggests guidelines for the design of a more comprehensive, responsive, and cost-effective environment for applying computer-animated simulations in transportation planning.
Planners should be able to build a computer model interactively, obtaining feedback at every point about the syntactic validity of the formulation and about the implications of the model.
Simulation and animation should be specified and controlled in an integrated fashion in a single system. Animations of a model should be available at any time to aid in visualizing its implications. Other more traditional techniques of representing the results of a simulation, such as statistics, histograms, and graphs, should also be available.
There should be flexible and natural tools for defining and modifying all aspects and constraints, including geometrical, of the environment being simulated.
The advantage of a discrete simulation such as that obtained with SIMULOGO over a continuous simulation is that computations are made only for discrete, relatively widely spaced instants of simulated time. One saves money by sacrificing resolution in simulated time, hopefully without loss of predictive validity. Yet the animation requires an effectively continuous simulation anyway, so the modeler should always be able to control the temporal resolution and cost of each computation.
Simulations will nonetheless be costly and time-consuming. Yet many runs of a model repeat common subcomputations over and over. Methods of saving computation and restarting without recomputing are needed to facilitate cost-effective modeling.
There has been much computer science work on simulation languages but regrettably little on simulation systems and environments. The precise syntactic form in which one models a queue is not nearly so important as the set of tools with which modelers define, refine, visualize, and document their assumptions and understanding. Issues of interactivity and ease of use, lucidity and vividness of representation and presentation, and ultimately cost effectiveness must be paramount in future designs.
If these design issues are tackled responsibly and imaginatively, we predict a bright future for the tools described in this paper. They are not relevant just to subways but to transit stations of all kinds and to the flow of crowds through arenas and conventions centers, high-rise office buildings, and hospitals. The computer-animated simulation model couples one's analytical abilities as augmented by the computer and one's intuitive and visualization skills as augmented by film so that they may be used for planning and design.
The substantial contribution of Eric Onasick, who programmed the animation, and the collaboration of Jan Kuypers and Ian Norton, whose firm suggested the problem, collected the data, and formulated the original modeling hypotheses, are gratefully acknowledged. We are thankful to Ben Barkow and to Les Mezei for critical comment and enthusiastic support. This work was funded primarily by the National Research Council and in part by the Ontario Ministry of Transportation and Communications through a contract to Kuypers Adamson Norton Ltd.
1. H Maisel, G Gnugnoli, Simulation of Discrete Stochastic Systems, Science Research Associates, 1972.
2. J Reitman, Computer Simulation Applications, John Wiley, 1971.
3. D H Meadows, D L Meadows, J Handers, W W Behrens III, The Limits of Growth, Universe Books, 1972.
4. K C Knowlton, Computer-Animated Movies,. Emerging Concepts in Computer Graphics, W A Benjamin, 1968, pp. 343-370.
5. J Halas, ed, Computer Animation. Hastings House, New York, 1974.
6. K C Knowlton, A Computer Technique for Producing Animated Movies, Proc, SJCC 1964 , pp. 67-87.
7. R M. Baecker, Interactive Computer-Mediated Animation, MIT. Project MACTR-61, April 1969.
8. R M. Baecker, Picture-Driven Animation, SJCC 1969, pp. 273-288.
9. R M. Baecker, Computer Animation: An Aid in Visualizing Complex Processes, Canadian Datasystems, March 1973, pp. 30-32.
10. M Alemparte, D Chheds, D Seeley, Walker, W, Interacting With Discrete Simulation Using On Line Graphic Animation. Conference on Computer Graphics and Interactive Techniques, Boulder, Colorado, July 1974.
11. F J Sarno, Computer Animated Simulation of Traffic Flow Proc., ACM Urban Symposium, 1969.
12. L Goodman. Final Report: Morgantown System Simulation Analysis Urban Mass Transportation Administration, US Dept of Transportation, Rept.
13. G W Harju, L R Bush, R F Kramer, H S Porjes, An Advanced Computer Concept for Freeway Traffic Flow Modelling, Summer Simulation Conference of Aerospace Corp, San Diego, June 14 to 16, 1972.
14. T R Horsley, A Student Simulation Language, Department of Computer Science, Univ of Toronto, MSc thesis, 1974.
15. W Feurzeig et al, LOGO Report Series, Bolt Beranek and Newman, Inc, Cambridge, Mass.
16. S Papert et al, LOGO Report Series, MIT Artificial Intelligence Project, Cambridge, Mass.
17, M Guerin, A System for Computer Animated Film Production in a Batch Processing Environment, Department of Computer Science, Univ of Toronto, MSc thesis, Oct. 1973.
18, R Baecker, M Guerin, and M. Tilson, A Computer Animation Facility for Research and Educational Filmmaking.
19. R Baecker, producer, Computer-Animated Transit Models, Dynamic Graphics Project, Computer Systems Research Group, Univ of Toronto, 10-min black-and-white silent film, 1975.