Next: About this document ...
Large scale multi-agent simulations of transportation systems
N. Cetin, C. Gloor, K. Nagel, B. Raney, and A. Voellmy
Dept. of Computer Science, ETH Zürich,
CH-8092 Zürich, Switzerland
{cetin@inf, chgloor@inf, nagel@inf, raney@inf, res@vis}.ethz.ch
On a certain level of abstraction, human transportation systems do not
look very different from ant hills: Agent with different and mostly
uncoordinated goals move through the system, they interact where this
is necessary for their goals and where resources (e.g. walking or
driving space) becomes scarce, and somehow they contribute to make the
system ``function''.
For transportation systems, it is now possible to do direct
agent-based simulations of such systems with many millions of
travelers. Such a simulation does not only move the individual
travelers through the system according to their mode of transportation
(walk, car, etc.), but also integrates modules which simulate the
strategic decisions of the agents, such as the generation of their
daily schedule, or the selection of a route.
Typical such modules of a transportation simulation package are:
- Traffic simulation module - This is where travelers move
through the street network by walking, car, bus, train, etc.
(Fig. 1)
- Modal choice and route generation module - The travelers
in the traffic simulation usually know where they are headed; it is
the task of this module to decide which mode they take (walk, bus,
car, bicycle, ...) and which route.
- Activity generation module - The standard cause why
travelers are headed toward a certain destination is that they want
to perform a specific activity at that location, for example work,
eat, shop, pick someone up, etc. The activity generation module
generates synthetic daily plans for the travelers.
- Life style, housing, land use, freight, etc. - The above
list is not complete; it reflects only the most prominent modules.
For example, the whole important issue of freight traffic is
completely left out. Also, at the land use/housing level, there
will probably be many modules specializing into different
aspects.
In addition, there need to be initialization modules, such as the
synthetic population generation module, which takes census data
and generates disaggregated populations of individual people and
households. Similarly, it will probably be necessary to generate good
default layouts for intersections etc. without always knowing the
exact details.
Since we run large scenarios (a typical metropolitan region has
several million inhabitants), it is necessary to use parallel
computers. We use a Linux-based Beowulf cluster of 32 Pentium PCs.
The most compute-intensive part, and also the most difficult to
parallelize, is the traffic simulation. When using domain
decomposition, i.e. giving a different piece of the geographical area
to each CPU, we are able to reach computing speeds of 100 times faster
than real time. Because of some peculiarities of parallel speedup,
this number is predicted to be valid for nearly arbitrarily large
scenario sizes.
Figure:
Traffic jam in Portland
|
The above modules interact, and the interaction goes in both
directions: activities and routes generate congestion, yet (the
expectation of) congestion influences activities and routes. This is
typically solved via a relaxation method, i.e. modules are run
sequentially assuming that the others remain fixed, until the results
are consistent.
A typical way to implement this is a ``best reply'' strategy: Between
runs of the traffic simulation, a randomly selected 10% of the agents
will obtain new dayplans that would have been optimal for the previous
run. These agents will go into the next traffic simulation run using
the new plans, while all other agents keep the old plans.
Fig. 2 demonstrates a typical result for a test case.
The test scenario is that 50000 randomly distributed agents all
want to travel to Lugano (indicated by the circle). Initially (left
figure), they all attempt to use the freeways, since they all have
planned their trips not thinking about the others). After
49 iterations as described above, traffic is much more spread out
(right figure).
The advantage of the agent-based approach is that it can be made more
realistic. We are currently working in two directions:
- Agent database - Instead of having to accept the new
plan from the system, the agents keep old strategies and their
performance scores in a database. This has the advantage that
the plans generation mechanism can be considerably more creative,
since a badly performing plan will be ignored. Also, it is now
possible to have arbitrary individual performance measures. In
particular, it is possible to have performance measures for which
finding an optimal solution is difficult or impossible, but
behavioral heuristics (such as genetic algorithms) can be used.
- Within-day replanning - Real world travelers do not
only replan over night, but they change their plans during the day
or even during a trip, for example when they are caught in
unexpected congestion.
Within-day replanning becomes a challenging problem if one wants to
maintain parallel computing efficiency, and if one attempts to
structure the design so that different programming teams can
independently work on the different modules. We are currently
implementing this by having only ``low level intelligence'' of the
agents (such as collision avoidance, lane changing, reaction to
traffic lights) directly in the traffic simulation and do all the
strategic computation outside. The simulation will be coupled to the
strategic modules via messages.
Figure:
Result of day-to-day learning in a test example. The scenario
is a test case, using a network of Switzerland, where 50000
vehicles from all over the system start between 6am and 7am and
simultaneously attempt to reach a destination within the circle.
Green shows free flowing traffic; red shows traffic jams. LEFT:
Situation at 9:00am in the zeroth iteration. RIGHT: Situation
at 9:00am in the 49th iteration. Clearly, traffic has spread
out and the system is using more different routes in the 49th
iteration.
|
We are currently working on a simulation of all of Switzerland, that
is on a full, realistic traffic simulation of 24 hours of a typical
workday. In a first step, demand will come from traditional
origin-destination-matrices, which are provided by the Swiss
transportation authorities. Besides the traffic simulation, our
system will do the route learning. Once this is working, we will
include the learning of activities and daily plans into the
framework. Fig. 2
is an intermediate test result from this project.
For more information, please see http://www.inf.ethz.ch/~
nagel/ .
Next: About this document ...
Kai Nagel
2002-05-31