Introduction

The negative impacts of traffic, such as noise and other emissions, accidents, or waste of time in congestion, are recognized as problems. On the other hand, eliminating traffic is not an option: Mobility of goods is necessary for economic performance, and mobility of people corresponds to a desire of most humans. The latter is for example visible in the increasing share of leisure traffic. In this situation, two reactions are necessary:

• A search for better technologies.

• A consensus in society about the balance between desire for mobility, acceptance of negative impacts, and willingness to spend on better technologies.

One such technology is ITS.

The impact of any infrastructure change, including ITS, depends critically on people's behavior. Forecasting this impact, in particular in complex situations, is therefore a difficult problem. For ITS technology, this forecast is even more challenging since ITS has a dynamic component that bricks-and-mortar technologies do not possess: Individual route guidance or public variable message signs can change at any given point in time. In contrast, a new road, once open, will remain there for many years.

It is therefore critical that models of ITS treat human behavior in a meaningful way. One approach to this problem is to write simulation models which treat each traveler as a microscopic entity and to model that entity's reaction to the system directly. This is what is meant by the term ``multi-agent'' simulation (MASim). Optimally, such a system would model each individual traveler's space-time path through the virtual system; this would generate synthetic traffic sensor data that would be sent to the virtual traffic management centers; those centers would compute strategies (such as individual route guidance) and send them back to the agents; and then each individual agent would react to that information according to its individual behavioral profile. This approach would make the inclusion of behavioral diversity, for example based on attributes of the persons and/or the alternatives, conceptually easy to model.

Several challenges are connected to the successful application of MASim technology. The first one is the computer implementation of a full MASim system for transportation applications. Although this may seem unrelated to transportation, it is probably not: Computer implementation decisions have an impact on what is easy to model and what is not.

Next, human behavior needs to be modeled realistically. This is the topic of several other presentations of this workshop. One aspect of human behavior is human learning, for example the realistic day-to-day dynamics of how the system adapts after a major infrastructure change. In the past, this problem has been avoided by just considering the ``relaxed'' state that is reached once all learning has stopped - the assumptions were that this state would be close to a Nash Equilibrium (NE), that the NE would be unique, and that therefore the computational and modeling challenge was to reach that NE as quickly as possible, rather than to model human learning. This approach may no longer be possible with ITS technology.

A final challenge is the size of realistic systems: Metropolitan areas often consist of several millions of potential travelers, and all of them need to be simulated directly in order to make the MASim approach work. One might argue that one should start with smaller systems. The counter-argument to this is that the relevant systems are the large ones, and that the behavior of large systems may depend more on large scale collective effects and less on individual behavior.

This paper will discuss in some detail that a multi-agent simulation of large scale real-world scenarios is possible, and the techniques necessary to achieve this. It will also discuss that those techniques do not immediately transfer to en-route (within-day) replanning, which is nevertheless important for ITS. A possibility to simultaneously allow within-day replanning and efficient large scale computing is discussed near the end of the paper.

Let us make a remark on the difference between simulation-based ITS evaluation and simulation-based ITS application. In the first case, the ITS system, as a ``black box'', is plugged into the simulation system: The simulation system generates synthetic sensor output and communicate it to the ITS system; the ITS ``black box'' receives this data, computes its response, and send the corresponding measures, such as variable message signs, to the simulation system; the simulation system has the travelers react according the the behavioral rules. In this case, the MASim is used as an evaluation tool. An example of such an application, albeit not fully agent-based, is MITSIMLab (38).

In the second case, the MASim is used as a tool to generate the ITS system response in the first place. It could, for example, be used to help with state estimation, or to compute several forecasting scenarios as a function of different possible management strategies. Examples of such applications, albeit once more not fully agent-based, are DYNASMART (21) and DYNAMIT (20).

The remainder of this paper concentrates on how MASim could be used for the evaluation of ITS systems.

Multi-agent simulations of physical systems generically consist of at least two components (23, Chap. 4) (see Fig. 1):

• The component(s) which compute(s) the physical aspects of the system (such as excluded volume, limits on acceleration, etc.). This will be called the mobility simulation (see Sec. 2).

• The component(s) which compute(s) the strategic decisions of the agents. On the traveler's side, this includes the reaction to ITS technology, but also long-term aspects such as choice of residence or workplace location. Since ITS devices can also be treated as agents, strategies for those ITS devices can be computed in a similar way as strategies for the travelers.

  In general, there will be more than one strategy (plans) generation module. Typical examples of plans generation modules are departure time choice, or route choice.

  Strategy generation is shortly discussed in Sec. 3.

The specific distinction between the strategy generation and the mobility simulation is made because they need very different sets of tools, and people with experience in one do not always have experience in the other. For transportation applications, one needs to make both components useful for the real world. This can, in our view, best be achieved by completely separating the strategy generation from the mobility simulation. Then, strategies are submitted to the mobility simulation, which executes them and returns the strategies' performance. The strategy generation can, as discussed in Sec. 4 on learning, react to this information.

Such a setup is still no guarantee that the mobility simulation has any relation to the real world. However, it is now possible to construct the mobility simulation with principles from simulation as it is known in the natural and engineering sciences, where there is much more experience with the simulation of realistic systems.

In the transportation community, sometimes the terms ``demand simulation'' and ``supply simulation'' are used (see, e.g., its.mit.edu). They are not the same as our distinction: As can be seen in the schematic Fig. 1, the supply simulation combines the simulation of the physical system and the simulation of the traffic management strategies into one module. The distinction of supply and demand may be appealing from an economics perspective; from a computing perspective it is not: The simulation of the physical system is considerably different from simulations of strategy generation, and should therefore not be combined into a single conceptual module.

Figure 1: Components of a multi-agent simulation for traffic management.

Besides the mobility simulation and the strategy generation, there are two more components which are necessary to make the whole simulation work: a method to do learning/feedback, and initial/boundary conditions:

• In general, it is not possible compute complete strategies and then run the mobility simulation based on them, since it is computationally infeasible to compute a strategic answer to all possible conditions. Therefore, the simulation system needs to implement some kind of learning or feedback, by which the agents modify and improve their strategies. The most prominent example for this is the reaction to congestion: Agents will make tentative plans, the mobility simulation will execute them, agents will revise their plans, these plans will be executed again, etc. Issues related to learning will be treated in Sec. 4.

• Boundary conditions refers to all data that remains fixed throughout the simulation, such as the road network. Initial conditions are how the simulation is started. Examples of both will be described, with respect to the specific scenario of a simulation of ``all of Switzerland'', in Sec. 5. This section will also contain some comparison to real world measurements.

Sec. 6 will discuss computational aspects. In particular, it is of critical importance to make the whole iteration cycle computationally fast in order to be able to do systematic computational experiments. The paper is concluded by a longer section on future plans, and a summary.