3.1 Why agent-based traffic simulation

Traffic and transportation are attractive application domains for agent-based simulation for several reasons: for example, mobility is a highly relevant topic for societies. Hence, any improvement achieved using a new technology has effect on the daily life of many people as well as on the economy. Thus, traffic-related topics are on the agenda of many funding agencies. Often, traffic management and control approaches require traffic simulation for illustrating functionality or performance tests. On the other hand, traffic scenarios are ideal testbeds for new (general) algorithms as they are easily explainable, given that everybody has to deal with several aspects of mobility in his or her daily life. Also, dealing with traffic simulation is interesting from a methodological point of view due to many challenges ranging from questions on necessary level of detail and required knowledge, the presence of emergent phenomena, spatial distribution, or the integration of different goals present in traffic systems. Last, but not least, the scale of the system that needs to be treated is a challenge on its own.

Using agents as the basic metaphor for reproducing intelligent decision-making entities offers many advantages compared with conventional approaches in traffic simulation. First, it allows an elegant treatment of heterogeneous and variable structures in the agent population (e.g. individual drivers entering and leaving the system at given time periods), as well as in the transportation network (links may be deleted or created during a simulation and agents adapt to these changes). Second, it enables the modelling of complex information processing and decision making considering multiple factors and dynamic information (including anticipation, group behaviour, or learning and adaptive behaviour). An agent-based approach enables an intuitive integration of behavioural constraints throughout different levels and phases of the decision-making process. For example, in simulations related to multi-modal routing, a decision made by a given agent about taking a bus has consequences on further decisions of this agent. One consequence is that the option of using a car is no longer available for this particular agent in future decisions. Third, since every active entity is explicitly represented, they not only support distinct and elaborated visualization, but also permit modelling heterogeneity on different levels (e.g. based on different contexts, different parameter sets or even different architectures).

3.2 Alternative microscopic approaches to traffic simulation

The just mentioned features distinguish agent-based approaches to traffic simulation from more conventional microscopic ones. In the four-step model (Ortúzar & Willumsen, Reference Ortúzar and Willumsen2001), the initial phases basically consist of data collection and manipulation for determining the number of trips between locations, followed by the assignment phase, which connects a trip to a route resulting in the simulated load on the network. Further, depending on the objective of the study, a mobility simulation is used for determining the actual traffic flow data. Agent-based approaches can be used not only for each of these phases, but also to emulate the decision making across all involved aspects. For example, instead of identifying flows between areas where a significant share of the population resides and industrial areas for determining demand for transportation, an agent-based approach uses models for explicit individual decisions about why and where an agent wants to be. This means individual context-dependent decisions on locations, times, and activities. The most prominent methodology for modelling agent decision making is based on econometrics de Palma et al. (Reference de Palma, Ben-Akiva, Brownstone, Holt, Magnac, McFadden, Moffatt, Picard, Train, Wakker and Walker2008). Here, weights and parameters of an individual function for evaluating different alternatives in decision making are optimized for minimising the gap between measured (stated) and simulated distribution. The main outcome are the weights that describe preferences of the traffic participants. Some issues here refer to the required quality of input data, the limited complexity of the functions that can be estimated, as well as the transferability of results to similar scenarios.

Game-theoretic analysis can be seen as an alternative microscopic tool providing means for the analysis of interaction when the overall outcome depends on all individual decisions. Interactions are formulated as an abstract game, whose analysis is based on payoff matrices or functions describing the possible outcomes for the different participants. This allows the identification of equilibrium states that may predict the selection of rational actors. Examples of such methodology appear in Section 3.4: Using game-theoretic metaphors such as minority or congestion game, agents choose one alternative. Those that have selected the less-populated option win or receive the highest reward. When played repeatedly, those games provide a good abstract model for many traffic scenarios in which agents want to avoid selecting the alternative that is selected by the majority. Game-theoretic approaches in traffic scenarios cannot be separated from agent-based approaches. In particular, abstract scenarios such as the minority game are mostly tackled within the realm of agent-based simulation. Yet, in general, agent-based simulation is more powerful as also ‘irrational’ behaviour, decisions involving a lot of information, dependencies to other agents, etc. can be integrated into the model.

In traffic flow simulation, one can find a number of microscopic techniques. Highly elaborated car-following models involving vehicle dynamics and driver decision making such as the model by Gipps (Reference Gipps1981) are used in commercial tools (see Barceló, Reference Barceló2010) for a collection of contributions on various tools based on driving strategy models). Such models basically resemble elaborated automated cruise control algorithms for simulated vehicles with individual values for desired speed and acceleration or acceptable gaps to the preceding car. These models can be easily conceptualized as simple agent-based models. Yet, agent-based models can not only integrate higher level of decision making, but also more complex forms of information processing, which may involve more than headway gap and speed of the car ahead.

Another microscopic traffic simulations that aim at reproducing traffic flow are based on cellular automata. Space is segmented into cells whose state is updated based on the state of their neighbours following a set of update rules. A well-known model is described in Nagel and Schreckenberg (Reference Nagel and Schreckenberg1992), where the state of a cell represents the presence and speed of a vehicle on that cell. The positions of vehicles are updated based on four rules that express speed adaptation with respect to the gap between the agent and its preceding vehicle, and on a probabilistic deceleration rate.

It is interesting that cellular automata model are often described from an agent-based point of view, characterizing the behaviour of an active vehicle–driver unit instead of a spatial unit. Cellular automata can be implemented very efficiently, thus making them suitable for large-scale traffic flow simulations. However, the necessary complexity of the decision making captured in the state of a cell and the formulation of strictly local update rules can be quite challenging when involving more than the simple rules of the Nagel–Schreckenberg model.

Queueing simulation is another efficient technique for traffic flow simulation that abstracts the actual decision making during driving on a link by capturing the time that a vehicle–driver unit stays on a particular link based on its position in a queue. For an example, see Charypar et al. (Reference Charypar, Nagel and Axhausen2007). Queueing simulation can be seen as an intermediate solution between microscopic and macroscopic simulation paradigms. Vehicle–driver units are passively moved through the system, that is, there is no active decision making while driving. Nevertheless, it is very efficient and fits well an agent-based approach for other levels of decision making. The agent-based traffic simulator MATSim (www.matsim.org) uses a queueing approach for simulating the actual movement combined with an agent-based demand generation and departure time, mode, and route choice, as described in the next section.

3.3 Agent-based travel demand simulation

Traditionally, determining the travel demand is the initial phase in all traffic simulation. It deals with the need for transportation infrastructure as the basic simulation input. The output of travel demand calculations is the number of trips from an origin to a destination, eventually also considering departure times. Determining travel demand is traditionally a data-driven activity based on demographic data, statistics about workplaces and households, car ownership, etc. Whereas trip-based approaches were prevailing in the past, activity-based approaches are becoming more and more important. In these, the daily schedule of typical human that belongs to a particular behaviour class is reproduced. It consists of activities that happen at particular locations. In order to simulate changing in locations, trips are added to the overall plan. After this, origin, destination, and also departure time can be determined based on the respective trip connecting two activities (Bhat & Koppelman, Reference Bhat and Koppelman2003; Timmermans, Reference Timmermans2005).

Agents and activity-based approaches perfectly fit together. Simulating activities planned and executed by agents enables the analysis of traffic systems on a more detailed level and thus a wider range of transportation policies:

• • Increasing complexity related to socio-economic properties and other sources of heterogeneity can be handled as decision-makers and their properties are explicitly represented.

• • Individual adaptation and learning of daily plans can be used for acquiring realistic and optimized plans.

• • Integration of interactions between agents can be included: for example, using social network models, but also between members of the same household.

• • Integration of other levels of decision making such as mode and route choice as well as actual driving and potential delays gives immediate feedback on the feasibility of the (remaining) daily plan.

Therefore, it is not surprising that a number of agent-based concepts and implementations for travel demand models exist.

Rindsfüser et al. (Reference Rindsfüser, Klügl and Freudenstein2004) propose a model of an intelligent agent for adapting daily activity schedule with respect to external events. The starting point is the definition of an habitual daily program as a coarse pattern for a traveller's activity schedule. This is extended and adapted over the simulated day in reaction to the traffic situation, meetings with friends, etc. This ‘re-scheduling’ model illustrates the necessity of flexible human decision making for producing realistic daily plans. Although a first prototype could produce realistic plans, the agent model was not applied in a large, realistic setting.

Auld and Mohammadian (Reference Auld and Mohammadian2012) separate activity generation from activity planning (configuration) and scheduling (the actual execution during simulation) into a dynamic decision-making framework related to activity and travel planning. The model is grounded on empirical studies. Similarly, Sun et al. (Reference Sun, Arentze and Timmermans2012) provide additional grounding dealing with flexible information handling and uncertainties in decision making.

In contrast to this, the activity-based travel demand module of the aforementioned MATSim—the so-called MATSim-T module (Balmer et al., Reference Balmer, Rieser, Meister, Charypar, Lefebre and Nagel2009)—does not try to resemble the planning process. Rather, it is based on a set of fully elaborated daily plans that are iteratively adapted. This makes an activity-based approach feasible for large-scale cases, such as a simulation of the complete Zürich area. In MATSim-T, each agent possesses a set of fully elaborated daily schedules, including details of the route choice to connect two (or more) locations. Schedules of all agents are simulated using a queueing simulation for actually producing realistic simulated travel times on the road network. Travel times and costs are then evaluated using a fitness measure and optimized by means of genetic algorithms for adapting the plans. In a next iteration, the agent uses the evaluations to select one of the plans for execution. Modules are available, for example, for the selection of destinations (Horni et al., Reference Horni, Scott, Balmer and Axhausen2009, Reference Horni, Nagel and Axhausen2011). The optimal schedule is then taken as the most realistic one.

Grether et al. (Reference Grether, Chen, Rieser, Beuck and Nagel2008) have used MATSim-T to illustrate the usefulness of an agent-based simulation to evaluate time-dependent tolls in road pricing. They were able to show the effects of an afternoon toll in some roads in central Zürich. Such a detailed analysis is only possible if the simulation is able to capture decisions at different times of a day, as well as the different activities and travel needs of agents that can adapt their complete daily plan to avoid (or not) certain areas at certain times.

The idea of agent- and activity-based demand generation coupled to traffic simulation was also transferred to the simulation of commercial vehicles delivering goods in an urban environment (Joubert et al., Reference Joubert, Fourie and Axhausen2010).

The research team around T. Arentze and H. Timmermans have developed activity-based models for travel demand generation grounded on existing theories in psychology and economics. In Arentze and Timmermans (Reference Arentze and Timmermans2008), the focus is on the allocation of tasks and budget within households for elaborating the activity schedule at household level. In Arentze and Timmermans (Reference Arentze and Timmermans2005), they propose the use of Bayesian networks and their adaptation for developing a model of mental maps as an individual representation of the user's environment. These mental maps typically contain incomplete and incorrect information. Using a form of cognitive learning, the authors aimed at overcoming drawbacks in previous works on activity-based travel demand, in which choice sets were often specified in an ad hoc way. Their approach was then extended in Han et al. (Reference Han, Arentze, Timmermans, Janssens and Wets2009), here dealing with dynamic location choice sets based on a combination of different forms of learning and psychological theories such as Bayesian learning or social comparison theories.

Activities are not planned or scheduled in isolation: social interactions are relevant for joint activities, coordinated activities, social influence on preferences or information exchange. Ettema et al. (Reference Ettema, Arentze and Timmermans2011) illustrate the relevance of social interactions in activity-based simulation; Hackney and Marchal (Reference Hackney and Marchal2011) describe a tool that allows the analysis of the effect of social connectivity and location on activity and travel choices. Ronald et al. (Reference Ronald, Arentze and Timmermans2011) analyse the influence of different interaction protocols on number, frequency, and type of activities when more than one simulated individual is deciding about an activity. Also the influence of social networks on destination choice and thus on traffic demand has been tested, as in Han et al. (Reference Han, Arentze, Timmermans, Janssens and Wets2011) and Horni et al. (Reference Horni, Nagel and Axhausen2011).

An earlier approach to activity-based travel demand modelling was suggested by Rindt et al. (Reference Rindt, Marca and McNally2002): the Contract Net Protocol was used for negotiation about participation in an activity. Unfortunately, the paper does not provide enough details to assess how this highly dynamic activity generation process could be integrated into a larger traffic simulation process; nevertheless, it gives an interesting bottom-up alternative to other highly refined approaches.

A non-activity-based approach for travel demand modelling is described in Zhang and Levinson (Reference Zhang and Levinson2004). Their model generates travel demand from interaction between travellers, node, and link agents. Travellers aim at finding and reaching an activity that is associated to a node agent. Link agents manage a set of reachable activities together with shortest paths and costs for connecting them. Thus, this model combines trip generation with route assignment, rather than dividing them as in conventional approaches. As the previous model, this approach illustrates what can be done directly based on the agent concept. It remains to be tested whether it produces a valid output when applied to real-world settings.

One of the decisions that is usually tackled in the context of travel demand modelling is departure time choice. The relation between this choice and congestion is analysed in McBreen et al. (Reference McBreen, Jensen and Marchal2006). Special attention is paid to the influence of homogeneity or heterogeneity of agents decision making on the overall dynamics. Their results indicate that only models that are capable of considering heterogeneous agents can produce robust outcomes.

3.4 Agent-based simulation of traffic-related choice

A second group of agent-based models deals with traffic-related choice. These choices may be made on different levels of granularity: from destination and departure time choice, mode, and route choice, to choice related to lane change. In such models, the agents (repeatedly) select an option out of a set of alternatives. The result of these decision processes are particular outcomes or utilities for the decision maker. For sake of clarity and because it is an important choice dimension, we focus on route choice. We remark, however, that route and mode choice can be integrated and performed simultaneously.

The research area of discrete choice analysis deals with such choice processes, by adapting micro-level decision functions or weights from a macro-level point of view, aligning empirical survey data and stochastic choice results. In contrast to this, an agent-based approach is usually bottom-up, starting from explicit individual, context-depending behaviours. Agent-based approaches are particularly relevant when networks are dynamic, when dynamic information is available, or when there is not enough specific data available for using an econometric approach. In this case, an agent-based simulation may integrate the agents’ immediate reaction to the changed environment (including other drivers). Also, complex information from different sources can be included into route choice decision making as the agent-based modelling allows integrating sophisticated decision making with individual preferences or socio-economic background.

3.5 Agent-based traffic flow simulation

Depending on the objective of the investigation under course, simulation of route and mode choice is not sufficient. In some cases it may even be irrelevant. Most of the previously discussed models deal with time granularity of, say, 1 day. These are useful for, for example, calculating travel times. On the other hand, the traffic flow simulations discussed next operate with a time granularity of 1 minute or less. There are several possible applications for such models: First, a valid reproduction of traffic flow can directly address traffic phenomena like the emergence of traffic jams based on driving behaviour, showing the effects of or speed limits, among others. Other examples are the prediction of traffic situations or interpolation of the current traffic state between distant located sensors. As every vehicle is treated as a distinct entity, individual-based emission of pollutants can be calculated if data related to a heterogeneous population of vehicles are available. Finally, agent-based simulation of traffic flow is very attractive for visualization of details, also generating background traffic for (immersive) traffic simulators in which a human subject virtually participates in traffic. There are even games as, for example, ‘Cities In Motion’Footnote ¹ using this level of traffic simulation.

This level of traffic simulation already is and will continue to be highly relevant for testing future communication infrastructures such as V2X (a generalization of V2V) communication and ad hoc networks, future infrastructures for safe and informed driving, etc. Many of the approaches discussed in the next section reproduce, as realistically as possible, situations such as how simulated drivers approach a traffic signal. Clearly, although sometimes relevant, routing is not the focus of this research. In the following, we tackle only those simulations studies with a focus on driver behaviour. Further examples of the use of the mentioned communication infrastructure in conjunctions with simulation based on new technologies appear in Sections 4.7–4.9.

In order to realize fine-grained microscopic simulation, several agent-based concepts and models have been suggested. Many works related to agent-based car-following models were motivated by the simplicity and elegance of cellular automata-based models of traffic flow, such as the model by Nagel and Schreckenberg (Reference Nagel and Schreckenberg1992). This cellular automata can be easily coined as an agent-based model describing the decision making of a simulated driver with only a few rules depending on the gap to the preceding vehicle and some additional random delay. Also, continuous car following characterized as driving strategy models can be coined as very simple agent-based modelling (see also Section 3.2). In these, a vehicle–driver unit adapts its speed depending on the distance and speed to the preceding entity.

The work by Burmeister et al. (Reference Burmeister, Doormann and Matylis1997) can be seen as one of the first agent architectures for traffic simulation, despite the fact that it tackles mostly the reactive driving level in form of an agent-based car-following behaviour. A survey on driving models can be found in Kesting et al. (Reference Kesting, Treiber and Helbing2009). Suggestions for driver models reproducing individual driving styles (with respect to individual parameters like preferred speed, acceptable gap to the preceding vehicle, acceleration rate, reaction times) can be found in Ehlert and Rothkrantz (Reference Ehlert and Rothkrantz2001). The vision in their work was to create more realistic traffic scenarios by including more heterogeneity in the model of the drivers.

A similar simulation goal can be found in Paruchuri et al. (Reference Paruchuri, Pullalarevu and Karlapalem2002), which describes a traffic simulation with different types of drivers (aggressive, cautious) in a situation where drivers do not need to adhere to traffic rules (chaotic intersection).

Other traffic simulators focus on simulating movement behaviour through intersections. For example, Doniec et al. (Reference Doniec, Mandiau, Piechowiak and Espié2008) rely on behaviour-based rules for the agents moving through intersections where actions that violate norms may result in traffic accidents. Espié and Auberlet (Reference Espié and Auberlet2007) show that standard car-following models lack anticipation beyond the immediately preceding entity for showing realistic behaviour especially in situations with ramp lanes. Their simulation model ARCHISIM allows complex agent-centric perception for realistic driving models; recent versions focus on realistic environmental representation involving also the perception of non-standard situations with emergency vehicles or unexpected obstacles (Ksontini et al., Reference Ksontini, Espié, Guessoum and Mandiau2012). Traffic accidents and improvement of pedestrian safety also motivate the work of Waizman et al. (Reference Waizman, Shoval and Benenson2012) who use a 3D model with detailed agent manoeuvre behaviour and analysis of driver or pedestrian agents perception. Luo and Boloni (Reference Luo and Boloni2012) focus on detailed perception models for simulating driving strategies with lane changes. Benenson and Martens (Reference Benenson and Martens2008) require a realistic traffic flow simulation for the task of reproducing the search behaviour of drivers for free parking places in the residential areas of Tel Aviv. Agents move through the network and may or may not find free parking places.

There is a variety of agent-based microscopic traffic flow simulators, dealing with different levels of behaviours, in different configurations and granularity of traffic networks. It seems that their number has increased a lot during the last decade, thus is not possible to discuss each of them. We expect an increasing number of such traffic simulators, with more and more attractive visualization features, as the complexity involved in their implementation is decreasing. A recent trend—mainly for coping with scalability in large-scale simulations—are multi-level models such as suggested in Navarro et al. (Reference Navarro, Flacher and Corruble2011) for urban (pedestrian) simulation, or attempts to use Graphics Processing Unit (GPU) computing (Strippgen & Nagel, Reference Strippgen and Nagel2009).

3.6 From traffic simulators to testbeds

Testing or benchmarking novel management and control approaches of traffic signals, toll policies, V2X communication, etc. are big drivers of traffic flow simulation. Only few traffic flow simulators exist that allow manipulation of different components in a flexible way as needed by research. Commercial as well as non-commercial microscopic flow simulation tools (see Barceló, Reference Barceló2010) for a compendium about the currently most important simulators)—such as VISSEMFootnote ², PARAMICSFootnote ³, AIMSUNFootnote ⁴ or SUMOFootnote ⁵—provide only restricted access to the actual controllers and simulation infrastructure. Barceló et al. (Reference Barceló, Codina, Casas, Ferber and García2004) discuss which elements are necessary in a traffic simulation testbed, whereas Timóteo et al. (Reference Timóteo, Araújo, Rossetti and Oliveira2012) describe the TraSMAPI infrastructure for providing an uniform access to a traffic simulator.

4.1 Classical algorithms and software

Optimization of traffic signal controllers in an off-line way is the basis of well-established algorithms such as TRANSYT (Robertson, 1969), which generates optimal coordinated plans for fixed-time operation. Of course the main drawback of this method is that plans are computed for a static situation, based on historical data. SCOOT—Split Cycle and Offset Optimization Technique (Hunt et al., Reference Hunt, Robertson, Bretherton and Winton1981)—is similar to TRANSYT but is traffic-responsive (uses data from buried detectors). SCATS—Sydney Coordinated Adaptive Traffic System (Lowrie, Reference Lowrie1982)—is also based on real-time data. The main difference to SCOOT is that it is a hierarchical system. Similar frameworks that are, however, decentralized are Prodyn (Henry et al., Reference Henry, Farges and Tuffal1983), OPAC (Gartner, Reference Gartner1983), and UTOPIA (Di Taranto, Reference Di Taranto1989). TUC—Traffic-responsive Urban Traffic Control (Diakaki et al., Reference Diakaki, Papageorgiou and Aboudolas2002)—models traffic flow using a variant of the store-and-forward control model to compute control policies in an efficient way.

The strengths of TRANSYT, SCOOT, and SCATS are their reliability, robustness, and large number of deployed systems. However, they also have some drawbacks. The simplest methodology for creating a signal-timing makes several assumptions, including the existence of a default value for saturation flow (normally one that reflects ‘typical’ conditions). However, this seldom happens in real-world cases. Besides this and the issue of cost and maintenance, there are several other reasons why those approaches may fail. In traffic networks without well-defined traffic flow patterns, for example, morning and afternoon peaks, that approach may not be effective. This is clearly the case in big cities where the business centers are no longer located exclusively down-town. Also, in some cities, ‘secondary’ streets turned out to be as important as traditional arterials due to saturation of main arterials and/or to the use of navigation systems (which may consider secondary streets in the suggested route). Traffic patterns can also be affected by accidents, floods, snow, etc. Finally, a priori determination of the appropriate signal plans for the different times of the day is a complex task that requires a lot of domain knowledge.

These issues show that simple off-line or even on-line optimization of the synchronization in arterials alone cannot cope with changing traffic patterns. This happens because traffic is a highly dynamic process, thus the optimal signal plan can hardly be determined in advance. Given the increasing volume of traffic, more flexible and robust approaches are necessary. In the next sections, we deal with agent-based traffic control and management approaches, which differ on their degrees of sophistication as well as on their scopes.

4.2 Optimization of single traffic controllers

In the work by Kosonen (Reference Kosonen2003), various agents interact in a single intersection using fuzzy inference. Each phase is modelled as an agent that can change the lights of the group to green when required by the volume of traffic and when permitted by other agents. Hence, there is a need for negotiation between agents about how to operate together. Although the focus seems to be on intra-controller coordination, Kosonen mentions that agents can also negotiate with neighbouring intersections, both upstream and downstream, by means of exchange of local traffic and control data. The paper does not provide more details about how the fuzzy control is performed when it comes to negotiate with neighbouring agents. Thus, the challenge here is how to integrate fuzzy control with coordination of agents, especially when it comes to solve both the local and the coordinated optimization problems.

Also Koźlak et al. (Reference Koźlak, Dobrowolski, Kisiel-Dorohinicki and Nawarecki2008) have proposed a multiagent system to control traffic signals based on intersection managers (IMs; called intersection coordinators). Besides these managers, agents are also in charge of predicting future traffic conditions.

4.3 Optimization of network of controllers

In the next subsections, a more complex family of optimization problems is addressed, namely optimization of networks of agents located at neighbouring intersections. This departures from optimization of single controller and poses an extra problem because agents can either ignore other agents (and hence incur in sub-optimal solutions, at least from the point of view of the system-level performance), or coordinate with neighbour agents. Coordination is a key issue in multiagent systems and many propositions exist that can lead to improvement of performance in networks of controllers. It seems that a favourite technique is the use of communication to exchange data about traffic states and control actions. However, there is no obvious protocol that prescribes how the non-local information should be integrated with the local one. For instance what should be done when conflicts arise? This is the case if, for example, there is a request from a neighbour and this request is not compatible with the local actions an agent is trying to implement to solve its own local optimization problem.

Besides communication-based approaches, other popular ones are: (i) organizing control agents in a hierarchical structure so that conflicts are solved at an upper level; (ii) letting agents learn how to control their local environments or coordinate their actions; (iii) let agents self-organize. The first still needs communication at some extents (though less than a pure communication-based approach). The other two approaches, which appear in Sections 4.4 and 4.5, respectively, present the potential drawback that the time taken to learn or self-organize may be incompatible with the dynamics of the environment. In the particular case of learning-based approaches, unless agents receive utilities for their actions that are aligned with the global objectives of the system, the performance at global level tends to be poor.

4.4 Learning-based approaches: the compromise between independent versus centralized learning

A popular approach related to control of traffic signals is to let one or more agents learn a policy for mapping states to actions by observing the environment and selecting actions. Thus, most of the proposed approaches deal with reinforcement learning where the control problem is modelled by means of a Markov decision process (MDP). Depending on the actual formulation of the MDP, it may not be computationally feasible to solve the problem because the space of state-action pairs grows exponentially. This is due either to the discretization regarding the number of states in a single intersection, or to the number of intersections, or both. Solutions for this problem have been proposed in two directions. First, instead of modelling the whole problem of n intersections in a single MDP, one may use n independent learners. Second, it is possible to use function approximation to deal with the size of the space state. The former is a popular approach because it has the advantage of scaling to a large number of agents. However, because agents learn independently in an environment where other agents are doing the same, this approach may lead to global inefficiency or at least sub-optimality.

Next some of the proposed approaches are reviewed; we start with those based on a local, independent perspective of single agents, and later move to approaches based on multiagent learning or at least on some kind of interaction or coordination between the involved agents.

One of the first works dealing with reinforcement learning for traffic control was based on stochastic games (Camponogara & Kraus, Reference Camponogara and Kraus2003). The emphasis is on applying one of the following policies: uniformly random policy (assigns the same probability to all actions available to an agent); best-effort policy (lets traffic flow from the lane with the longest queue); and one achieved by using Q-learning. For the experiments, two intersection agents were used. Depending on the traffic conditions, if both agents implement Q-learning, there is a significant reduction in the waiting time.

In Silva et al. (Reference Silva, Basso, Bazzan and Engel2006), authors propose the use of model-based instead of model-free approaches to deal with the highly dynamic and non-stationary nature of traffic flow patterns. In this approach, it is assumed that flow patterns are non-stationary but they can be nearly divided in stationary dynamics that need not to be known a priori. Each model is assigned to an optimal policy (which is a mapping from traffic patterns to signal plans), and to an estimation of the quality of a given partial model. The creation of new models is controlled by a continuous evaluation of the prediction errors generated by each partial model. This model contains an estimated transition function and also an estimated reward function. If the environment changes and a local policy turns suboptimal (congestion increases over a threshold), then the system creates a new model. Whenever possible, the system reuses existing models instead of creating new ones. Although this mechanism was tested in a network of nine traffic signals, it remains an independent learning method and thus an extension is necessary to tackle joint states and joint actions.

In Prashanth and Bhatnagar (Reference Prashanth and Bhatnagar2011), the learning problem is solved in a centralized way, that is, a single MDP models all involved controllers. Thus, it is restricted to a grid of 3 × 3 controllers. Clearly, the centralized MDP poses a limitation for real-world applications. On the other hand, the authors focus on an important problem, namely the high dimension of the space state, by using a function approximation technique.

Given the issue of computation complexity of centralized MDP versus sub-optimality of independent learning, a recent trend is to let controllers learn independently but allow them to interact and combine their policies. This way one may depart from total centralization, as well as from total independence, and find a compromise between these two extremes. We now discuss some of these tentatives. These are mostly based on agents being able to coordinate their actions by means of several techniques such as communication of advice, collaboration, supervised learning, etc.

The question of how heterogeneous groups of agents can benefit from communication to improve their learning skills was investigated by Nunes and Oliveira (Reference Nunes and Oliveira2004) in which information from several sources during learning is used in a simplified traffic control problem. Members of a team of agents may communicate among them or with members of other teams that are solving similar problems in different areas. Different types of agents use various techniques such as neural networks and heuristics.

Exchange of information by independent controllers is also tackled by Oliveira and Bazzan (Reference de Oliveira and Bazzan2009) where controller agents may or may not benefit from exchanging information. Thus, this work analyses how agents can benefit from sharing information as well as the consequences of this cooperation in the performance of the traffic system. Authors show that having information is not sufficient if the other agents are not acting in a coordinated way; extra information can have a negative effect in the learning process if the information is unnecessary. Also, noise in the traffic patterns and the inter-dependencies among the agents’ actions are relevant factors to consider when there is a need to decide between using shared information, using only local information, or an in-between solution.

The work of Kuyer et al. (Reference Kuyer, Whiteson, Bakker and Vlassis2008) also focus on cooperative learning and explicit coordination among agents, that is, joint actions among them are considered. However, this leads to an increase in complexity. Thus, some simplifying assumptions must be made. In this case, authors assumed that the coordination takes place only among direct neighbours in the network. Under this assumption, the global coordination problem may be decomposed into a set of local coordination problems and can be solved with the use of coordination graphs as proposed by Guestrin et al. (Reference Guestrin, Lagoudakis and Parr2002). To find the optimal joint actions in such graphs authors apply an algorithm that estimates the optimal joint action. This work assumes that relationships among controllers are restricted to their direct neighbourhoods. However, in traffic this is not always the case. Although coordination graphs can be extended to other kinds of neighbourhoods, this approach has problems handling a high number of agents in each graph. Moreover, it is not clear what happens when controllers belong to more than one coordination graph as in this case the policies learned by the controllers in different graphs are conflicting.

In Bazzan et al. (Reference Bazzan, de Oliveira and da Silva2010), a layered architecture is proposed where supervisor agents are in charge of a small group of controller agents. This tries to balance the number of joint versus independent actions using a kind of organizational control in line with the work by Zhang et al. (Reference Zhang, Abdallah and Lesser2009).

4.5 Self-organizing progressive systems

As mentioned previously, one way to achieve progressive systems is to let agents self-organize regarding the decision about which green waves form. The issue of non-communication between traffic signals and local interaction was especially popular until some years ago when the cost of communication (e.g. wireless) was prohibitive.

In this sense, Oliveira et al. (Reference de Oliveira, Ferreira and Bazzan2004) have proposed an approach based on swarm intelligence. Each intersection controller behaves like a social insect. Signal plans are seen as tasks to be performed by the insect without any centralized control or task allocation mechanism. Stimuli to perform a task or, sometimes, to change tasks, are provided by the vehicles that continuously produce ‘pheromone’ while waiting for green lights. Thus, the volume of traffic coming from one direction can be evaluated by the intersection agent, and this may trigger some signal plan switching. Experiments have shown that the agents achieve synchronization without any central management. However, the time needed to converge to a stable coordination can be high, which is a negative aspect especially in highly dynamic environments.

A similar idea appears in Helbing et al. (Reference Helbing, Lämmer and Lebacque2005) where vehicles can synchronize traffic signals and organize green waves. Also in Gershenson (Reference Gershenson2007), traffic signals self-organize by means of three methods, also with no direct communication between them. It is shown that the adaptation to traffic conditions reduces waiting times and number of stopped vehicles.

Bazzan (Reference Bazzan2005) has used techniques of evolutionary game theory and stochastic games, in which there is no explicit communication among agents: traffic signal agents act in a dynamic environment having only local knowledge. However, these agents perform experimentation and receive a reward that depends also on the experimentation performed elsewhere in the neighbourhood. Stochastic events that may take place in the network are modelled by mutations. During the learning process, a fitness for each strategy is computed and influences the next generation of strategies that are used by the agents. Depending on the frequency of the stochastic events, agents are able to coordinate better towards the global goal. Results have shown that in scenarios where the volume of vehicles is nearly equal in both directions, the central progression does not perform well compared with the agent-based mechanism, because the latter is adaptive. A shortcoming of the approach is that payoff matrices (or at least the utilities and preferences of the agents) are required, that is, these figures have to be explicitly formalized by the designer of the system. This makes the approach time-consuming when many different options of coordination are possible. Thus, a challenge here is how to design mechanisms for large-scale of networks.

In Prothmann et al. (Reference Prothmann, Tomforde, Branke, Hähner, Müller-Schloer and Schmeck2011), an observer/controller architecture for signal control is proposed. This effort appears within the framework of organic computing (Schmeck, Reference Schmeck2005). The idea is that a signal controller is the system under investigation, while an observer monitors the local traffic demand and evaluates the performance of the active signal plan. Based on the observations, the controller selects and optimizes signal plans by means of a two-levelled learning mechanism. In level 1, signal plans are selected on-line from a previous learnt mapping. This relies on a variant of a learning classifier system (XCS). Level 2 is in charge of optimizing the available signal plans when an unknown demand arises. This optimization is achieved by means of evolutionary algorithms. This approach was tested in isolated intersections as well as in progressive systems and with the inclusion of self-organized routing.

4.6 Approaches explicitly addressing demand

So far we have discussed traffic control approaches that focus on signal optimization and do not explicitly consider the demand. In the following, we discuss works aiming at the integrating both the demand and the control sides.

4.7 Lightless

Mandiau et al. (Reference Mandiau, Champion, Auberlet, Espié and Kolski2008) consider a single intersection, without traffic signals, having only stop signs as a two-player game played by autonomous vehicles approaching or entering the intersection. The actions available for the autonomous vehicles are to stop or to move; the types of games and corresponding payoffs are set depending on priority rules. The authors have performed tests for two agents, three agents, and with complex intersections (with a high number of conflicting movements). Results have shown that their model is able to reproduce the actual flow of vehicles. Limiting issues here are how to design such mechanisms to deal with large-scale networks.

The seminal work by Dresner and Stone (Reference Dresner and Stone2004) has proposed a reservation-based intersection control where autonomous vehicles try to cross an intersection without conventional traffic signals. In that publication, it was assumed that: autonomous vehicles are not allowed to turn, do not change lanes, and all begin travelling roughly at the same speed. The reservation is performed as follows. First, each autonomous vehicle informs the IM: the time it will arrive at the intersection, the velocity, direction, maximum and minimum acceleration, and other vehicles properties. Then, the IM simulates the journey of the autonomous vehicle given the IM's knowledge about other similar reservations. If the space requested by the autonomous vehicle (for a given timeslot) is already occupied, then the request is rejected, in which case the autonomous vehicle must decelerate and try again. If the request is accepted, it must be kept or cancelled by the autonomous vehicle (in case it cannot be met).

Some low-level issues left open were: what happens if the driver has to make last second changes, whether the autonomous vehicle is really committed to the deceleration, what happens if conventional vehicles participate in the system as well, and what happens outside the range of the IM after autonomous vehicle's have to decelerate in response to a denial of request. In order to cope with these issues, in Dresner and Stone (Reference Dresner and Stone2005, Reference Dresner and Stone2008), some of the previous assumptions were relaxed, especially the requirement that autonomous vehicles maintain a constant velocity in the intersection, and that they do not make turns. The improved protocol proposed is based on rules that the vehicles are expected to follow: a vehicle may not enter the intersection without a reservation; the vehicle must try to follow the actions prescribed by the IM; the autonomous vehicle cannot try to improve its own journey (as the manager will ignore a new request if the autonomous vehicle has already a reservation granted). Also, a modification in the protocol allows autonomous vehicles to share the system with conventional vehicles.

Finally, in Au et al. (Reference Au, Shahidi and Stone2011), a further management policy is proposed, which puts the request messages on hold and then process several requests at once, in order to avoid starvation at secondary roads.

That seminal approach by Dresner and Stone (Reference Dresner and Stone2004) plus its extensions have inspired other authors (see next section); major challenges are to address the low-level issues related to both fine grained activities of the driving task, and how to cope with mixed traffic (human and autonomous vehicles).

4.8 Market-based approaches

The reservation-based approach discussed in the previous section was also extended in Dresner and Stone (Reference Dresner and Stone2006) to address deadlocks and delays caused by drivers putting reservations in a suboptimal way because the IM processes requests on a first come, first served basis.

This has also inspired the work of Vasirani and Ossowski (Reference Vasirani and Ossowski2009, Reference Vasirani and Ossowski2011) where the reservation-based approach is extended to cover networks of intersections. The mechanism is market-based where drivers trade with the infrastructure agents in a virtual marketplace, purchasing reservations to cross intersections. Market rules were designed with the aim of aligning the global profit (revenues from the infrastructure use) with the social welfare (e.g. average travel time), in a way that, in situations of similar traffic load, an increase of the infrastructures monetary benefits usually implies a decrease of the drivers average travel times.

Schepperle and Böhm (Reference Schepperle and Böhm2007, Reference Schepperle and Böhm2009) propose an approach that takes the valuation of the drivers into account. The focus is on single intersections. In Schepperle and Böhm (Reference Schepperle and Böhm2007), a procedure is proposed, which consists of four steps: vehicle contacts the intersection; vehicle acquires an initial time slot to cross the intersection; if not satisfied, a vehicle can try to acquire a better time slot, this time from another vehicle; vehicles cross the intersection. In the second step, an auction (e.g. a second-price, sealed-bid) is run among the vehicles that do not yet possess a time slot. A variant is proposed in which a vehicle with a high valuation subsidize another vehicle that is located ahead and that is going to bid for a time slot but has a low valuation. Subsidizing vehicles ahead is expected to guarantee a better time slot for both vehicles. In the third step, vehicles arriving late can acquire time slots that have already been auctioned off. In Schepperle and Böhm (Reference Schepperle and Böhm2009), the authors explicitly discuss some challenges for making valuation-aware control systems operational.

Balan and Luke (Reference Balan and Luke2006) have proposed history-based controllers intended to provide a kind of global fairness. According to the authors, the original inspiration was to allow drivers informing the traffic signals whether they are in a hurry or not. In the history-based approach, information about vehicles’ immediate past histories is collected by the traffic signals, allowing them to communicate with other signals through the immediate histories of vehicles as these travel from intersection to intersection. They base their approach on the notion of historical fairness by allowing vehicles to store credits they receive when waiting at red lights, and cash the credits in when passing through intersections. Traffic signals base their decisions on the credits of various vehicles at the intersection. When a vehicle reaches its destination, it reports its average waiting time over all intersections and this is one metric used to assess the efficiency of the control. One issue is that vehicles have no interest in doing this and, if they do, there is no incentive to report the actual time taken.

4.9 Collaborative driving and cooperative car navigation

Collaborative driving is the focus of DesJardins et al. (Reference Desjardins, Laumônier and Chaib-draa2009). The authors describe an agent-based cooperative architecture that aims at controlling and coordinating vehicles, also showing that reinforcement learning can be used for this purpose. A multi-layered architecture was presented, which relies on both an action layer and on a coordination layer: the former is used to manage low-level vehicle control actions such as braking, accelerating, or steering, while the latter is responsible for high-level action choice by integrating cooperative decision making between vehicles. In both layers, multiagent reinforcement learning techniques are used, showing that the integration of these techniques at all levels of the autonomous driving controller yields efficient results for vehicle control and coordination. This approach thus facilitates the efforts of the system's designer, as the complex details related to vehicle control and related to the numerous possibilities of inter-vehicle interactions are automatically handled by the learning algorithm.

As already mentioned in Section 3.4.2, Yamashita and Kurumatani (Reference Yamashita and Kurumatani2009) have proposed a cooperative car navigation system with route information sharing. Each vehicle transmits route information (current position, destination, and route to the destination) to a route information server and this estimates future traffic congestion using current congestion information. Estimates are then fed back to each vehicle, which uses them to re-plan its route. To evaluate the effect of the route information sharing system, two indexes are used: individual incentive and social acceptability. Results of the experiments have confirmed that a cooperative car navigation system with the route information sharing generally satisfied individual incentive and social acceptability, as well as had an effect on the improvement of traffic efficiency.

4.10 Agent-based management

Traffic management is another domain where there are opportunities for cooperating agents. This is probably due to the fact that agent-related technologies facilitate modularity, modelling, and simulation of management strategies. In this line, many tools, environments, and prototypes have been proposed. Apart from those already discussed in Section 3 (modelling and simulation), next we present some tentatives of developing integrated environments for traffic simulation and control, in order to better manage the traffic system as a whole.

In van Katwijk and van Koningsbruggen (Reference van Katwijk and van Koningsbruggen2002), concepts related to agents and multiagent systems were used to formulate examples of traffic management based especially on heterogeneous agents and system components. From the modelling perspective, BDI was suggested (see also Section 3.4) to represent and reason about agents’ knowledge. Also, for cooperative agents, a coordination protocol based on priority over resource allocation is discussed that helps the agents to distribute the flow of vehicles. Resources that agents can manipulate are mainly the flow of vehicles and allowed speed. Authors mention some kinds of resource-bounded decisions agents must make: amount of resource to request, time of the request, which priority the request has, contingency for non-granted requests and/or changes in priority order. The authors discuss the problems that are ultimately tied to conflict resolution and the problem of local versus global performance. They try to solve the latter by formulating a hierarchical organization where authority both solves conflicts and pursue global performance. There are, however, other solutions (see Section 4.3.2); in any case, these issues were tackled in the recent literature but remain partially unsolved. Thus, an obvious challenge here is how to solve conflicts that appear due to insufficient resources and about which model of organization to adopt, namely a hierarchical, authority-based one versus a totally decentralized with lesser commitment with global performance.

In van Katwijk et al. (Reference van Katwijk, van Koningsbruggen, De Schutter and Hellendoorn2005), a testbed for traffic management is presented, which intends to manage different levels of complexity, a diversity of policy goals, and different forms of traffic problems. Their testbed aims at rapid development of multiagent-based management and control, consisting of an interaction model, intelligence models, and a world model. The former aims at modelling interactions among the agents, mainly via communication (see for instance, problems that fit this testbed in Section 4.3.2). Intelligence models are supported by rule-based inference, and by Bayesian inference (to model uncertainty agents may have). Authors claim that these three components are useful to implement decentralized traffic concepts that were reported in the literature. However, a closer analysis seems to indicate that their work is particularly suitable for hierarchical organized controllers and for inter-controller coordination. Therefore an evident challenge is to extend this testbed to accommodate other kinds of organizations of controllers, intra-controller coordination (e.g. among phases or groups of phases that exist in an intersection ), as well as other forms of coordination such as those not explicitly based on communication (see Section 4.3.1).

In Wang (Reference Wang2008), an approach is presented as a generalization of the feedback control mechanism in control theory. Wang's approach (the TransWorld) is based on a connection between the actual transportation system and its artificial counterpart. This connection is manifold, that is, has many modes. In the learning and training mode, both the artificial and the actual systems are only loosely connected and the former serves as data center for learning operational procedures. In the experimentation and evaluation mode, the artificial system serves as a platform to conduct experiments and eventually predict the behaviour of the actual system. In the control and management mode, which is the most challenging one, both systems must be tightly connected (for instance, real-time connected). It is expected that the artificial system is able to replicate the actual behaviour. Eventual differences can be used to generate feedback control. The author emphasizes the need for parallel execution of both systems, and that the artificial one is seen as a generalization of adaptive control, whereas the AI-based artificial system replaces an analytic reference model.

The underlying idea of artificial transportation systems is also present in the MAS-T²er Lab (Rossetti et al., Reference Rossetti, Ferreira, Braga and Oliveira2008) project, which is based on agent programming that can deal with the social and behavioural models, such as those discussed in Section 3.4.

Regarding the management of systems that include or are based on autonomous vehicles, in Bazzan et al. (Reference Bazzan, do Amarante and da Costa2012), an agent- and market-based approach is proposed to manage a fleet of automated guided personal rapid transit vehicles (e.g. pods). This study considers some variants for both the processing of demands (trips) and for the routing. These variants are centralized versus decentralized, with or without en-route re-planning, and action based versus first in, first served basis. Results show, at least in some cases, the feasibility of a centralized service. However, communication as well as reliability and fault-tolerance are of course important issues.