ERCIM News No.46, July 2001 [contents]
by Heinz Mühlenbein, Ulrich Bartling and Uwe Beyer
The computing power of large PC clusters has made possible the implementation of computer systems which process hundreds of thousands of individual agents in real-time. This is designated an Artificial Reality System (ARS) if the system is in continuous interaction with the real system via sensor data. An ARS is a detailed image of the real system on the computer, and can be used for analysis, planning, and control. Even prediction is possible if part of the ARS can be cloned and made to run faster than real-time. Researchers at the Institute of Autonomous Intelligent Systems of GMD have developed a new technology for implementing AR systems. This technology has been used to develop a large ARS, called City-Traffic. The demonstrator version simulates the traffic of the city centre of Bonn.
New computer models are essential in understanding todays world. Research and development that relates to mapping real-world systems into computer systems has so far concentrated on the visual presentation of objects (virtual reality). It is now moving to augmented reality and artificial reality. Augmented reality shows real objects in more detail than can be perceived in reality. Artificial reality models the dynamic behaviour of a set of real objects. Thus virtual, augmented and artificial reality systems show true reality from different perspectives.
Artificial reality means reproducing the real world in detail on computers. Furthermore, the artificial and real systems can be made to interact. The state of the real system is continuously monitored by thousands of sensors (in the case of City-Traffic by induction loops, floating car data etc). At intervals of, say, three minutes, the states of the real system and the artificial system are compared. In a process similar to relaxation in mathematics, the state of the artificial system is kept almost identical to the state of the real system.
Short-term prediction is done as follows. Every six minutes, for example, the ARS creates a child which then runs faster than real-time. Thus, if the child runs ten times faster than real-time, in two minutes it can make a prediction for the traffic situation twenty minutes in the future.
For the implementation of artificial reality systems, the potential of multi-agent systems has steadily grown. Here, every agent represents a sub-unit of the system. Depending on the context considered, these sub-units could be local processes, components, individuals, species, cars, firms etc. The agents may interact directly or indirectly on different time scales and/or spatial scales.
Research in artificial reality at the GMD started with a theoretical investigation of networks of agents. We then designed an architecture called the Flip-Tick Architecture (FTA) to facilitate the implementation of artificial reality systems. This research has been funded since 1994 by the Real World Computing Partnership financed by METI from Japan.
The origins of the Flip-Tick Architecture (FTA) are based on several well-known organisational principles, software architectures and hardware structures. Major contributing factors to the development of FTA include:
The central processing units of FTA are fine-grained software agents called actors (up to 800 000 per host on a 256 MB PC). Actors read typed data containers (called tags) from a special memory called a tagboard, and write tags to tagboards for later use. An FTA implementation can have many tagboards (up to 30 000 per host) and each actor has access to any tagboard. A tagboard has two faces - the face with data accessible for reading (read-only) and the face with the new data (write-only). The FTA architecture is cycle-oriented. After a cycle, the tagboards are flipped. The data read in the previous cycle is erased. The data written is now available for reading. The efficient implementation of FTA on a PC cluster was a considerable technological software challenge.
|City-Traffic consists of a monitoring system, an information system, a control system, and a prediction system. The system is intended to run continuously in a traffic control center.|
Previous investigations on traffic dynamics have mainly concentrated on freeway traffic, and therefore deal with phenomena like traffic jams, stop-and-go traffic, etc. Quite a different situation exists in cities, where we do not have a large number of cars heading in one direction, but rather a large number of cars with very different destinations and driver schedules. A suitable way to implement such a real-world situation on computers uses agents representing individual cars, which move on a detailed map of the real city road system.
For the implementation of a commercial artificial reality system we started a project with the city of Bonn. The following information is used as an input for the system: road maps with intersections, traffic lights on intersections, average number of cars per home in a certain area, and time-dependent traffic density.
The traffic light system of the city of Bonn produces online information about the current flow of traffic. The system is not able to identify or distinguish individual cars. There is no information about individual starting or destination points of traffic members. Thus City-Traffic simulates the same amount of traffic, but not individual routes. The online information is used to continuously update the state of the artificial reality system.
We have recently completed a simulation of the city ring of Bonn. For the traffic of the whole urban area we will use a PC Cluster of 24 processors. With this configuration we will achieve an execution time of two hours real-time per 24 hours of real traffic in Bonn. A further function of City-Traffic is an information system where citizens can access actual traffic information via the internet. The information system also makes routing proposals. The total system is shown in the figure.
In addition to the particular situation of Bonn, our computer program is set up to handle even larger cities, with up to 20,000 intersections, up to 40,000 road sections, and up to 200,000 cars moving at the same time.
The research has been funded by the Real World Computing Partnership financed by METI from Japan.
Heinz Mühlenbein GMD
Tel: +49 2241 142405