Multi-agent simulation modeling issues

Constructing a multi-agent simulation is, at least initially, a rather straightforward process: One takes some simulation substrate, e.g. a 2-dimensional plane or a road network, populates it with agents, and gives them rules how they behave. Since the intention is to simulate the real world rather than some artificial system, much of the information can be taken from the real world.

It may be worth noting that this approach is usually rather obvious to people with a background in physics or computer science, and is often somewhat counter-intuitive for people with a background in economics. The reason is that much of physics and computer science trains people to think of systems in terms of individual interacting units, whereas economics has a tendency to think about the economic system in terms of aggregated quantities, such as demand and supply, which are decoupled from individual actors. As the ideal gas law in physics demonstrates, these views are not incongruous; in fact, much of the progress in physics in recent years is owed to the derivation of macroscopic laws from microscopic rules. Yet, it is our feeling that much of economic theory including traffic is not accustomed to this microscopic view.

The advantage of the microscopic, agent-based view is that, at least in principle, it can be made arbitrarily realistic. One can start with rather simple models and simulations, and every time some effect is not captured, one can add more details and thus eventually capture the desired effect. Nevertheless, there are obvious limits to this: Coding all these details takes time and effort; the knowledge, for example about human behavior, may not be sufficient; the necessary input data for all the details, for example certain demographic characteristics, may not be available.

The main purpose of the microscopic description in multi-agents system is to reveal and to forecast properties of the system that cannot be deduced only from a model of the physical system or from a set of assumptions about human behavior. Indeed, the simulations aim to bring explanations that arise from the interaction between a physical environment and the decisions of agents regarding their evolution in that environment. Also, because of the complexity of the physical environment, the interaction between the agents is not trivial and cannot be expected to be modeled by a simple law (e.g. congestion in traffic networks). Therefore, multi-agent simulations of systems with a physical reality generically consist of at least two components (Fig. 1; Ferber, 1999, Chap. 4):

• 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.2).

• The component(s) which compute(s) the strategies of the agents. This includes for example mode/route choice, activity scheduling, reaction to congestion, choice of residence, choice of workplace, etc. (see Sec. 2.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 modules can, as discussed in Sec. 2.4 on learning, react to this information.

Such a setup still gives no guarantee that the mobility simulation has any relation to the real world. It is however now possible to construct the mobility simulation with principles borrowed from the natural and engineering sciences, where there is much more experience with the simulation of realistic systems. In contrast, the strategy generation modules can be designed with principles from Artificial Intelligence and/or Psychology.

Abbildung 1: Strategic layer, physical layer. Note that a traffic management center is just another strategic entity that communicates with entities in the physical system (such as adaptive traffic lights).

Abbildung 2: Strategic/physical layer vs. demand/supply simulation.

[] []

Fig. 2 shows how the strategic/physical level approach relates to the often used demand/supply dichotomy. The typical inclusion of the mobility simulation into the supply side leads to a rather asymmetric picture (Fig. 3(a)). An alternative interpretation is to reduce ``demand'' and ``supply'' to their strategic dimensions, and let the simulation of the physical level be the neutral ``referee'' or ``moderator'' that calculates the consequences of the demand and supply strategies. This leads to a much more symmetric picture (Fig. 3(b)). In this interpretation, the decision to build a road would be a strategic decision on the supply side. But once the road is built, it becomes a part of the physical environment. It should be noted that such an approach is not inconsistent with trends in Economics, where it is increasingly noted that, between demand and supply, there is a market with its own mechanisms and mechanics, which need to be explicitly modeled for many aspects of Economics (Shubik, personal communication).

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:

• A ``complete'' strategy (in the sense of game theory) would be one that contains all the responses to all possible conditions that a traveler could encounter during the run of the mobility simulation. In general, it is neither computationally possible nor behaviorally realistic to compute such a complete strategy. Instead, one typically implements some kind of learning system, by which the agents learn to 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 simultaneously, agents will revise their plans, these plans will be executed again, etc. Issues related to learning will be treated in Sec. 2.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 (see Sec. 2.1).

Initial and boundary conditions

As was just mentioned, any simulation needs boundary and initial conditions. Boundary conditions are the data that does not change during the simulation, such as (possibly) the transportation system, the demographic characteristics of the population, or the land use. Similarly, a simulation needs to be started somehow, which provides the initial conditions. For example, one could start with a certain population and then evolve it through the course of the simulation.

In the context of multi-agent travel behavior simulations, the most important pieces of data are probably:

• Physical layer. This refers to the typical nodes and links of the road network, but also to information about public transit, about pedestrian travel possibilities, etc.

• Census data or synthetic population data. The population of agents that the multi-agent travel behavior simulation is run on or starts from needs to be generated somehow. It is therefore necessary to either store the input data into the synthetic population generation module, or the synthetic population itself.

• Land use data. An important aspect of activity-based demand generation is the location choice for activities, since activities at different locations are connected by travel.

• Study configurations. For each simulation run, there needs to be configuration files that define the run. This includes the scenario files that are used, but also simulation parameters such as the spatial resolution of the simulation.

The storing of survey data is not part of this text; this is treated in other sessions of the conference. However, micro-simulations of travel behavior clearly depend on behavioral parameters that are obtained from the evaluation of surveys. For the purposes of this text it will be assumed that such parameters are obtained from elsewhere, and that they are stored as part of the synthetic population or as part of the study configuration.

The mobility simulation

As said above, the mobility simulation refers to the simulation of the physical transportation system. It computes what happens to the agents' strategies when they are confronted with (a synthetic version of) the real physical world. With respect to a conference on travel behavior research, the mobility simulation is maybe not of prime importance. Yet, there is an increasing number of voices arguing that issues of ``artificial intelligence'' cannot be decoupled from the physical system. This ``embodiment hypothesis'' means, for travel behavior, that any results from a travel behavior model need to be submitted to some version of the real world to make sense. Typical issues that become clear when submitting strategies to such a ``real world evaluation'' are that the strategy could have been incomplete, or that the execution under real physical constraints leads to a much different behavior than anticipated.

The extreme of this would be to have some robotic lab where miniature travelers move through a toy traffic system. Short of this, one can use a simulation of the physical system as a proxy for embodiment. If, as suggested above, the simulation of the physical system is programmed by a totally different team than the simulation of the strategy generation, then there is some hope that the strategy will also make sense in the real world.

Beyond these aspects, a precise discussion of mobility simulation techniques is not critical to this paper. Suffice it to say that it is now possible to write virtual reality simulation systems, where the analyst can either look at a virtual reality version of the world as an independent observer, or he/she can participate as a traveler, e.g. as a driver. Yet, although such simulation systems are feasible, for many investigations they are too slow, too costly, and to extensive to program and to maintain. In such situations, it is often possible to use a much simpler method. In order to maintain the multi-agent approach, it is possible to have each agent represented individually in such a simulation, but apart from that many details from reality can be neglected and a useful result can still be obtained. Examples of such simulations in the transportation field are DYNEMO (Schwerdtfeger, 1987), DYNAMIT (DYNAMIT-www, accessed 2003), DYNASMART (DYNASMART-www, accessed 2003), or the queue model (Gawron, 1998b; Gawron, 1998a).

Strategy generation

The mobility simulation computes the physical aspects of movement, such as limits on capacity, storage, or speed. In particular it computes the aspects of interaction, such as congestion. The mobility simulation needs information about where travelers enter and leave the network, which turns travelers take at intersections, etc. As mentioned earlier, these aspects can be called plans, or strategies. For the transportation simulation, this means that travelers know where they are going, when they want to be there, and the route they want to take to get there. This kind of strategic knowledge is in stark contrast to, say, the simulation of ants in an ant-hill. It also makes the simulation design considerably more demanding, since the generation and handling of strategies is a whole problem of its own. Our own approach to this problem, as said before, is to allow a distributed design, that is, mobility simulation and strategy generation should be separated as much as possible, and in fact we also intend to have more than one strategy generation module in the future. This is further discussed in Sec. 3.7.

Important strategy generation modules for transportation applications are route generation, activity generation, car ownership models, housing choice, commercial location choice, land use changes, etc. Such models and modules are discussed in much breadth and depth at other places in this conference. Integrating such models into a multi-agent simulation framework is in principle once more straightforward. In practice, however, there are several issues that need to be considered:

• The unit of analysis needs to be consistent. The typical unit of analysis in a multi-agent travel behavior simulation is the traveler; an alternative would be the household. Once all modules agree on the unit of analysis, it is relatively easy to treat information consistently. If modules use different units of analysis, then information will get lost in the conversion. For example, during a conversion of agent-based activity chains to an origin-destination matrix one will lose any information about effects along the time axis (a person running late in the morning may carry the delay through the day), and one will lose any connection to demographic characteristics.

• There needs to be some standardization of what each module expects. For example, it seems that there is now some agreement that a typical daily plan consists of an activity schedule, consisting of a sequence of activity types, together with location and time information. Furthermore, activities at different locations are connected by trips, for which information such as mode and route is given. As long as there is essential agreements on the hierarchy of these elements, different modules can work together.

• Computational issues. These will be discussed in Sec. 3.

Some modules of an activity-based travel simulation system are shown in Fig. 3. It is plausible to assume that, from left to right, each module adds more specific agent data. For example:

• The population generation module determines age, gender, income, and home location (e.g. Beckman et al., 1996).

• The activity pattern module adds an activity pattern, such as home-work-shop-home.

• The activity location module locates those activities.

• The activity timing module decides how long each activity takes, and when the daily activity plan is started, and adds that timing information.

• The mode/route choice module determines and adds the mode of transportation and the route.

• Finally, the mobility simulation executes all plans of all agents simultaneously according to the specifications.

This is just an example of such a simulation system. Modules can be combined (such as all the activity-generation modules (e.g. Arentze et al., 2000; Kitamura, 1996; Bowman, 1998)) or decomposed (such as mode choice and route choice), and other modules will have to be added (such as car ownership). Nevertheless, it should be visible from the example how each individual module adds information, thus making the agent strategy more and more complete from one module to the next.

Abbildung 3: Some modules of an activity-based travel behavior simulation system.

The long-term goal here is to define data exchanges so that these systems can work together. In the past, the famous origin-destination (OD) matrices had exactly that effect: Demand generation modules knew what output to construct, and assignment modules knew what input to expect. It is both possible and necessary that agent-based simulation packages will reach the same level of interoperability.

Adaptation, learning and feedback

Introduction

Above, in particular in Fig. 3, it was implied that the generation of agents' strategies is a linear process, going from synthetic population via activities to mode/route choice. It is probably clear to everybody that in practice there is also backward causality. For example, congestion is the result of (the execution of) plans, but plans are based on (the anticipation of) congestion.

Therefore, feedback mechanisms have to link the different modules. Multi-agent systems intend to implement these mechanisms by mimicking the actual response of human agents, not by simply linking modules artificially. Unfortunately, most of the methodology to model these reactions is missing.

General issues of learning

Learning is not included in one of the mainstays of travel behavior research, the random utility model (Ben-Akiva and Lerman, 1985). How does learning enter the picture? Laying out a theory of learning agents is beyond the scope of this paper, but some aspects are worth noting:

• First, it makes sense to distinguish between single-agent learning, and system-wide co-evolution. Single-agent learning concerns a single agent when faced with the environment. In order to make scientific progress, it makes sense to assume that environment as stationary, i.e. that some underlying statistical distributions do not change over time. In contrast, system-wide co-evolution is concerned with the dynamics of a system in which many agents learn simultaneously.

• Within single-agent behavior, one can differentiate between behavior based on a scoring function (utility, fitness, prospect theory, etc.) and behavior based on symbol processing (for example following signs in an airport). There is in fact a related dichotomy between utility-based models and process models in activity scheduling.

• For single-agent behavior based on a scoring function, one can either assume that the agent is capable of ``constructing'' the optimal solution, or that the agent attempts to improve the value of this function from one period to the next. If the improvement algorithm converges to the optimal solution, and if one is just interested in the converged result, then constructing the solution is just a short-cut for learning it. ``Fuzzifying'' the choice, for example via the well-known $p_i \propto e^{\beta \, U_i}$, does not change the principal argument. These remarks show, at least intuitively, the connection between random utility theory and single-agent evolutionary modeling: Under certain conditions, the single-agent evolutionary algorithm will just converge to the random utility result.

  If however one is interested in the transients, or if one assumes that an agent eventually stops improving even if the best solution is not reached, then the two methods are no longer equivalent.

• When many agents learn simultaneously, one obtains a co-evolutionary dynamic system. It does not make a fundamental difference if agents are capable of constructing the optimal solution (``best reply'') or if their behavior is given by some other rule: Since all agents co-evolve simultaneously, a strategy that was a best reply at some period is in general not a best reply at some other time. In consequence, even agents that individually follow random utility theory or some other best reply behavior will still generate a complicated co-evolutionary learning system.

  Such a co-evolutionary learning system is a dynamical system. Depending on its exact properties (deterministic or stochastic, Markovian or not, etc.), it can display a large range of behaviors, for example (e.g. Cantarella and Cascetta, 1995; Hofbauer and Sigmund, 1998; Bottom, 2000; Watling, 1996): convergence to a fixed point, convergence to a periodic attractor, chaos, convergence to fixed probabilities in phase space, ergodicity, broken ergodicity, etc.

• It makes some sense to look at how this problem is approached traditionally. The traditional concept is the Nash Equilibrium (NE). As is well known, a system is at a Nash Equilibrium if no agent can improve by unilaterally changing its strategy. In the context of what has been said above, this means that all agents are using a best reply.

  The Nash Equilibrium concept is related to the co-evolutionary system by the fact that, if the single-agent learning converges to an individually optimal solution, then a fixed point of the co-evolutionary system is a Nash Equilibrium (Hofbauer and Sigmund, 1998). However, remember that the co-evolutionary learning system can display a much richer variety of behaviors than just convergence to a fixed point.

• It is interesting to note that, although the NE is a normative concept (the system is at a NE if ...), most if not all algorithms to actually find a NE in static assignment are iterative. That is, they have some resemblance to iterative learning, except that the iterations are set up to fulfill some mathematical property, such as guaranteed convergence, which means that they explicitly do not model human behavior.

• As a last point, let us mention within-day replanning. The idea of within-day replanning is easy to formulate: If an agent encounters something unexpected during the day (such as unexpected congestion, or an ice-cream stand during a warm day), the agent should be able to adapt its plan immediately (Axhausen, 1990; Doherty and Axhausen, 1998). This is in principle straightforward to implement, although there are some performance issues for large scale scenarios and parallel implementations (Sec. 3.7). It is however important to note that such an implementation is not automatically consistent with evolutionary game theory, which is the basis for nearly all theory of co-evolutionary dynamics that we know.

  This problem has to do with timescales of adaptation: If a traffic management center announces tolls (slow adaptation) and travelers react to the announcement (fast adaptation), then the result may be different from a traffic management center that adapts tolls within minutes (fast adaptation) and without announcement while travelers can only react to some average toll they encounter over the course of several trials. In static game theory, the problem is known as sequential games, multi-stage games, or Stackelberg games.

After this tour d'horizon through some aspects of feedback within agent-based behavioral models, let us look at some specific implementations. The purpose of presenting those is to anchor the discussion about computational methods in what is possible today, and then look from there to what may be possible in the future.

``Basic'' agent-based feedback

A possible version to model learning is as follows:

1. The system begins with an initial set of strategies, one per agent, based on free speed travel times, which represent a network with no congestion.

2. The mobility simulation is executed with the current set of strategies.

3. Some fraction $f$ of the population requests new strategies which replace the old strategies.

4. This cycle (i.e. steps 2 through 3) is repeated until some kind of stopping criterion is reached.

Many variations of this are possible (Lohse, 1997; Kaufman et al., 1991; Boyce et al., 1997). For example, the new strategies could be best replies to the previous iteration or to some average of the previous iterations. The latter can for example be obtained from exponential smoothing, i.e. $\overline T(n) = \alpha \, T(n) + (1-\alpha) \, \overline T(n-1)$, where $n$ is the iteration index, $\overline T$ is the value that is used for any strategy computations, and $0 < \alpha \le 1$ determines how much ``new'' information $T$ is included in each iteration. If is also possible to follow random utility theory and to chose between many options based on, say, $e^{\beta \, U_i}$.

According to what was said earlier, the choice of the learning models and their free parameters interacts with the behavior that the system will display. For example, a small replanning fraction $f$, averaging over previous iterations, or some small value of $\beta$ either force the system to a fixed point or to relatively small cycles. Doing the opposite leads to cycles or possibly to chaotic behavior. Yet, one does not want to select $f$ and/or $\alpha$ too small since then relaxation of the system toward the attractor (if this is what is desired) will be too slow. Heuristically, combining, in each iteration, 90% of ``old'' information with 10% of ``new'' information (i.e. $f=0.1$ or $\alpha=0.1$) seems to work well.

Multiple strategies per agent

A ``best reply'' strategy means that a replanning agent can construct the optimal response to a given situation of the environment. An example is the selection of a shortest path in a time-dependent network. In complex systems, the assumption that agents perform such strategy selection seems unreasonable because it contradicts the cognitive ability of humans: travelers cannot discriminate, following the same example, two paths that differ by one second. Nevertheless, best reply strategies are appealing because we can borrow much from Operation Research and Computer Science to implement the decision model. The approach of random utility theory relaxes these assumptions by assigning higher probabilities to strategies with higher outcomes. By doing so, similar alternatives will be selected with similar probabilities. This theory has two main drawbacks: firstly, there is always a finite (though small) probability that agents are going to select a very low utility option; secondly, it is based on the assumption that users face or are aware of all the potential outcomes, which is also not realistic from the behavioral point of view. An alternative to these approaches is to borrow a method from Complex Adaptive Systems, where possible solutions are permanently added and removed. The system then choses between those solutions with probabilities that may resemble random utility theory. An implementation of this may look as follows (Raney and Nagel, 2003; Raney and Nagel, 2002):

1. The system begins with an initial set of strategies, one per agent, and the mobility simulation is executed with those strategies.

2. Each agent measures the performance of his/her strategy based on the outcome of the simulation. In contrast to the basic approach, this information is stored for all the agents, associated with the strategy that was used.

3. A fraction of the population requests new strategies from some arbitrary external strategy generation module. Agents which request/receive new strategies select those for execution.

4. Agents who did not request new strategies choose a previously tried strategy, by comparing the performance values for the different strategies. For example, they use a multinomial logit model $p_i \propto e^{\beta U_i}$ for the probability $p_i$ to select strategy $i$, where $U_i$ is the utility (score) of option $i$ and $\beta$ is an empirical constant.

5. The mobility simulation is executed with the selected strategies.

6. This cycle (i.e. steps 2 through 5) is repeated until some stopping criterion is met.

An advantage of simulating the memory of agents is that the overall system is more realistic and in fact more stable from the numerical point of view. It has also the advantage to relax considerably the design constraints of the modules that generate the strategies. These modules can produce strategies that are suboptimal and in limited number. They will be evaluated by the agents that perform their own trial-and-error process. It is especially useful when the constraints put on a deterministic algorithm would not be met (e.g. selection of the best path with multiple criteria like minimum delay and maximum sight-seeing). An important drawback, though, is that the learning process by trial-and-error can be extremely slow (i.e. agents would need several lifetimes to build a realistic choice set). An obvious answer to this problem is to model also the exchange of information between agents. Again, models are missing there and research efforts are needed into that direction.

The ``multiple strategies'' approach brings our agent-based simulation closer to a classifier system as known for Complex Adaptive Systems (Stein and others, several volumes, since 1988). From here, alternative methods of agent learning, such as Machine Learning or Artificial Intelligence, can be explored. Similarly, one can explore different assumptions about the cognitive abilities of the human agent: How far do agents remember (e.g. Markov process of order $n$)? How much do they value recent experiences? Is there some risk evaluation or are the outcomes considered as deterministic? How far do agents anticipate the future outcome of the system (under/over shooting)?

Backward compatibility to 4-step process

So far, this paper has discussed multi-agent simulations for travel behavior simulation without much connection to established methodologies, notably the 4-step process (Ortúzar and Willumsen, 1995). Yet, given the large investments, in terms of data, training, and software, of some metropolitan planning organizations into the 4-step process, it is unlikely and also undesirable to abandon those investments and to start over with an agent-based approach. It is therefore important to discuss possible transition paths.

Fortunately, such a transition path is possible, and it is in fact possible to obtain meaningful results on every step along the way.

From agent-based to 4-step

The first part of the argument consists of the observation that it is always possible to obtain 4-step process inputs and outputs from the agent-based approach: It is possible to aggregate the results of the activity generation into OD matrices; it is possible to separate those OD matrices by mode; it is possible to obtain those OD matrices for any desired time slice, including hourly, AM/PM peak, or daily; and it is possible to obtain link volumes or link travel times from the mobility simulation.

This makes it possible, for example, to use activity-based demand generation and to feed it into the route assignment part of the 4-step process, a path that is indeed in the process of being implemented in several cities (e.g. Portland/OR, San Francisco, Ohio). A possible disadvantage of this approach is that the information that is available at the activity-generation level, e.g. demographic data or tight activity chains, will get lost in the process: After the activity chain is translated into trips, it is perfectly possible that a person leaves an activity location before it arrives!

A more troubling problem is that it does not really make sense to feed time-dependent activity chains into a static assignment model. A short answer is to use dynamic traffic assignment (DTA) models instead and to feed them with time-dependent OD matrices. However, this leads to a discussion with many facets, and discussing all of them in detail goes beyond the scope of this paper. Some of these issues are listed here:

• Since it does not make sense to aggregate activity-based demand into a single 24-hour OD matrix, static assignment models used in conjunction with activity-based demand generation are usually in some way time dependent: At the minimum, separate assignments are run for the important periods of the day (e.g. early morning, AM peak, off-peak, etc.). Alternatively, some assignment models have an explicit time-dependent mechanism in which they move unfinished trips forward into the next time slice (e.g. Kaufman et al., 1991; Friedrich et al., 2000).

• Most of the DTA models suffer from the same shortcoming as static assignment models, i.e. that their representation of congested traffic including queue built-up is wrong since they do not represent the congested branch of the fundamental diagram. In addition, while static assignment models have the very nice ``uniqueness'' feature (under certain conditions), much less is known about the mathematical features of the dynamic versions.

• There is now increasing awareness of the fact that the congested branch of the fundamental diagram should be represented correctly in what is now called the ``network loading model'', and several models are implementing space constraints and queue built-up (``physical queues'') (DYNAMIT-www, accessed 2003; DYNASMART-www, accessed 2003; Schwerdtfeger, 1987; Gawron, 1998a). In general, this requires to disaggregate the OD matrix into individual trips. Mathematical uniqueness properties of Nash Equilibrium assignment almost certainly do not exist with such models (Daganzo, 1998).

• DTA models are mainly concerned about short-term operational predictions and therefore have focused on the detailed description of congestion and vehicle movements. In doing so, the computational overhead prevents most of them of modeling the city-wide scale required by transportation planning.

• DTA models often calibrate ``raw'' dynamic OD matrices against traffic counts, potentially in real-time. Unfortunately, this breaks the feedback loop between agent decisions and system performance since there is no behavior explanation to the time-dependency of the input flows: Trips in the OD matrix are changed because the emergent result does not match the observation, rather than because of some behavioral reaction. This is a typical case where the ``time series analysis/black box'' approach for practical operations conflicts with the idea of building of model from first principles.

  In other words: DTA models may be a much better starting point for dynamic network loading models than stepwise extensions of the 4-step volume-based link cost function. However, with DTA models one needs to be careful that one only uses the pieces that are behaviorally justified while omitting those which are just there to make the DTA models operational in a real-time real-world context.

• Finally, most of the models mentioned above do not represent flexible agent features such as dependencies along the time axis, or replanning during the day.

• It is worth mentioning that network loading models with physical queues can be made completely agent-based without needing any additional input data. That is, the early perception that agent-based traffic simulation models are always extremely data hungry is not correct.

• If however a more realistic representation of the traffic dynamics is desired, then a more realistic network loading model can easily be used for any of the approaches.

A somewhat different path is followed by METROPOLIS (de Palma and Marchal, 2002; de Palma and Marchal, 2001), a dynamic traffic simulator that is partly agent-based: travelers with individual characteristics perform mode, departure time and route choice in a time-dependent context. Instead of making the demand generation time-dependent by going all the way to activity-based demand generation, it takes instead the conventional morning or afternoon peak period OD matrix as a starting point, and then self-consistently generates the whole temporal structure of the peak period. This is done by assuming that trips going to certain destinations (such as where workplaces are) have certain time constraints, and then applying a model for departure time choice for those trips (see Fig. 4). This approach allows to capture time-dependent trade-off between congestion and activity schedules constraints for the morning or the evening peak. However, it does not provide a complete description of daily tours and their schedules as the outcome of individual choices.

A big advantage of this approach is that it is more ``agent-based'' than standard assignment but does not need the full agent-based demand generation or any other procedure to generate time-dependent OD matrices. Our own practical experience suggests that, given current technology and implementation status, applying METROPOLIS to a new scenario takes a small number of days, while applying our agent-based approach on a new scenario takes several months.

Abbildung 4: The data sets hierarchy of METROPOLIS. The demand is segmented in an arbitrary number of OD matrix/User type pairs to capture trips with different purposes or morning and evening peaks.

From 4-step to agent-based

The reverse journey, i.e. obtaining agent-based data from the 4-step process, is less straightforward. The problem is that when going from agent-based to 4-step, information gets lost. This implies that in the reverse direction, from 4-step to agent-based, some information needs to be generated, or a decision needs to be made to ignore it. For example, it is perfectly possible to go from OD matrices to activity-based plans by just making up a virtual person for each trip in the OD matrix. However, in contrast to the fully agent-based approach, information about trip chaining will get lost, i.e. a delay in the morning, which may cause further delays throughout the day in the agent-based approach, will not have any consequences once converted into an OD matrix.

Theoretical justification of aggregated models

From a theoretical perspective, it is clear that the fully agent-based approach has many advantages over the 4-step process. It is less clear that those advantages will make a difference in practice. For example, experiments with METROPOLIS (Marchal, 2003) have shown that changing from vertical queues (with infinite vehicle storage on a link) to horizontal queues (with finite storage) leads to a lot of changes in traffic volumes at the individual link level. However, we observed that travel time structure of whole paths in the system was not very much affected as long as agents are allowed to perform within-day re-planning at each intersection. And since for many economic variables such as system performance, the travel time structure is the most important model result, this may be sufficient for many types of analysis. On the other hand, link volumes are critical to, say, emissions, and therefore in this case a more disaggregated simulation is a necessity.

This argument implies, confirmed by our experience (de Palma et al., 2001), that the classical static assignment usually fails to provide both consistent travel times and volumes at the same time for congested systems. In practice, static models are calibrated against traffic counts to produce realistic volumes. However, this leads to unrealistic travel times on congested links because the volume-delay functions do not work well above the capacity threshold.

It would be good to have more systematic versions of such results, i.e. a systematic understanding of when the assignment approach yields a useful approximation of the real world and when not. Such an understanding may eventually be achieved by diligent work comparing assignment models, agent-based simulations, and measurements from reality. (An obvious way to proceed is to have benchmark cases and more thorough validation studies.) Such an approach is in some sense similar to the approach in Statistical Physics, where much if not all of the aggregated laws of thermodynamics or fluid-dynamics can be derived from microscopic models. That is, there is a microscopic theory, but in practice often the aggregated approaches are used. However, because of the microscopic understanding, the limitations of the aggregated approaches are well known, and it is also known which corrective terms to use in order to push the envelope of validity.

A big advantage of a good microscopic foundation of aggregate models would be that one could continue using them in cases where computational, human, or data resources are not sufficient for an agent-based model.

Multi-scale models

Once the capabilities and limitations of the aggregated models are better understood, one could also look into multi-scale modeling. This would couple high-resolution agent-based models in core areas of interest with lower-resolution aggregated models in boundary areas, significantly reducing computing times. Such approaches are pursued in many areas of science and engineering, for example in weather forecasting, where the ``world model'' results are used as time-dependent boundary conditions for regional models. Note however that a deep understanding of the multi-scale characteristics is necessary to make this a success. If, to take again an example from weather forecasting, the cold front moves faster in one model than in the other, there will be strong artifacts at the boundaries, potentially modifying the whole system dynamics. Such artifacts need to be understood and avoided before multi-scale modeling can be made a success.

Summary

This part of the paper has sketched the modeling issues that are related to multi-agent simulations. It is clear that multi-agent simulations of traveler behavior consist of many modules that need to cooperate. This text has emphasized the differences between the physical layer (the mobility simulation) and the mental layer (the strategy generation), as well as the importance of adaptation, learning, and feedback. Finally, it was discussed how agent-based approaches relate to the established 4-step process, implying that the transition from 4-step to agent-based can be done via continuous evolution rather than via an abrupt revolution.

Comparing agent-based to existing models, a striking difference is that in agent-based models much emphasis is put on the modularity of the overall model and on its ability to capture actual human behavior. Another important aspect is the heterogeneity of the methods that have to co-exist. We mentioned them: the mobility layer borrows much from Physics while the strategic layer borrows from a vast spectrum of disciplines: Complex Systems, Machine Learning, Economics, Psychology, Operation Research, etc. This raises several obvious questions about the computational implementation. These will be addressed in Sec. 3.