The Exploratory Advanced Research Program

A Primer for Agent-Based Simulation and Modeling in Transportation Applications

CHAPTER 5: Agent-Based: A System Paradigm Applied in the Transportation Field

Multi-Agent System - A Computational Method For The Distributed Systems

This section reviews ABMS in another methodological domain, that of AI, in which ABMS is viewed as one of the powerful computing technologies. Other than the transportation systems discussed in chapter 4, which are individual based models, that is, models that treat each individual person or traveler as an agent, ABMS scoped in this section is regarded as a method in system modeling. More specifically, the common feature found in such studies is that the inherent distribution allows for a natural decomposition of the complex system into multiple subsystems. The subsystems interact with each other following local rules to achieve a desired global goal. It is these subsystems that are modeled as agents, and the operation of agents is supported and managed by distributed software platforms known as MAS.

Since its inception around the mid-1980s, MAS has become a key concept and method in DAI.⁽¹¹⁴⁾ DAI is a subfield of AI dedicated to developing distributed solutions for complex problems regarded as requiring intelligence. DAI is closely related to MAS, and the use of the term MAS in those studies essentially describes an agent-based computational method of DAI.

The agent paradigm in AI is based on the notion of reactive, autonomous, internally motivated entities that inhabit dynamic, not necessarily fully predictable, environments. An agent is autonomous and decides for itself how to relate data to commands to achieve goals. According to the National Aeronautics and Space Administration (NASA),⁽¹¹⁵⁾ "Autonomy is the ability to function as an independent unit or element over an extended period of time, performing a variety of actions necessary to achieve predesigned objectives while responding to stimuli produced by the system."

DAI solves problems by using multiple cooperative agents. In these systems, control and information are often distributed among a set of collectively interactive subsystems and components, represented by agents. This reduces the complexity of each subsystem and allows subsystems to work in parallel and to speed up problem-solving. Each agent also has resource and knowledge limitations, which could limit the ability of a single agent system to solve large, complex problems. In general, the learning and cooperation of multiple agents contribute to improving the performance of the agent group as a whole and increasing the domain knowledge of the group. Under this concept, the MAS can aid in the distribution of the problem over the various agents (subsystems) that comprise the MAS and facilitate coordination of the activities of the integrated system when required.

MAS can be characterized by the interaction among many agents that are trying to solve a variety of problems in a cooperative fashion. Along with some AI, an intelligent agent could have some additional attributes that enable it to solve problems by itself, to understand information, to set up goals and intentions, to draw distinctions between situations, to generalize and synthesize ideas, to model the world they operate in and plan, and to evaluate alternatives. The problem-solving component of an intelligent agent can be a simple rule-based system, a neural network, or some fuzzy rules.

Learning and cooperation among neighborhood agents is one of the important features of MAS. Dowell and Bonnell⁽¹¹⁶⁾ classified the learning strategies into the following four categories:

• Control learning - Learning and adapting to work with other agents involves adjusting the control of each agent's problem-solving plan or agenda.
• Organization learning - Learning what type of information and knowledge each agent possesses allows for an increase in performance by specifying the long-term responsibilities of each agent.
• Communication learning - Learning what type of information, knowledge, reliability, and capability each agent possesses allows for an increase in performance by allowing improved communication.
• Group observation and discovery learning - Individual agents incorporate different information and knowledge.

Strength of MAS
Parunak⁽¹¹⁷⁾ listed the following characteristics for an ideal application of agent technology:

• Modular - Each entity has a well-defined set of state variables that is distinct from those of its environment, and the interface with the environment can be clearly identified.
• Decentralized - The application can be decomposed into stand-alone software processes capable of performing useful tasks without continuous direction from some other software process.
• Changeable - The structure of the application may change quickly and frequently.
• III-Structured - All information about the application is not available when the system is designed.
• Complex - The system exhibits many different behaviors, which may interact in sophisticated ways.

Bonabeau⁽²⁾ suggested that MAS is appropriate:

• When the interactions between the agents are complex, nonlinear, discontinuous, or discrete, and behavior of individuals cannot be clearly defined through aggregate transition functions.
• When the population is heterogeneous, each individual is different, and the behavior of agents is stochastic in nature.
• When the agents exhibit complex behavior, including learning adaptation.
• When activities are a more natural way of describing the system than processes. When the appropriate level of description or complexity is not known ahead of time.

Adler and Blue⁽¹¹⁸⁾ concluded, in summary, that the multiagent technology can significantly enhance the design and analysis of problem domains under the following three conditions:

• The problem domain is geographically distributed.
• The subsystems exist in a dynamic environment.
• The subsystems need to interact with each other flexibly.

It is believed that the domain of traffic and transportation systems is well-suited for an agent-based approach because of its geographically distributed and dynamically changing nature.^(119,120)

Weakness of MAS

Bernhardt⁽¹²¹⁾ summarized the weakness of modeling MAS as follows:

• Requires significant quantities of data and can be computationally intensive.
• Simulation of individual agents requires significant computational power, particularly when individual agents have complex characteristics and decisions, as with human beings.
• Often requires behavioral data, which may be difficult and costly to obtain.
• Difficult to validate such a model, particularly if the goal is prediction of behavior in an untested system.

In their review of transportation applications of MAS, Kikuchi et al.⁽¹²²⁾ summarized the features of MAS as follows:

• Local state and local knowledge dictate the actions of an agent. This means that individual agents do not make globally optimal decisions. Reconciling decisionmaking based on local knowledge with the desire to achieve globally optimal performance is a problem when agent-based modeling is used for system optimization.
• Of special concern, MAS may not be appropriate for control problems in which global constraints and objectives have to be satisfied.
• To apply MAS, the analyst needs to feel comfortable with the idea of delegating tasks to the agents, rather than controlling the tasks. The agents that work on behalf of the analyst eventually exhibit a self-organizing character.
• Calibration of parameters is difficult because how individual behavior affects overall behavior is not completely known.

MAS Practiced in Transportation Problems

MAS has been widely applied by both researchers and practitioners in a spectrum of disciplines, from biology, business, and computer simulation to social science, political science, and economic science. Knowledge of ABMS and the recognition of applications continue to expand (for comprehensive overviews of a variety of applications of MAS for traffic and transportation problems, see references 2, 123, and 124). This section summarizes part of the applications developed so far in the transportation field that apply to MAS. Note that the description of review in this chapter is mainly based on scientific papers in the published literature and does not suggest any level of development, maturity of application, or readiness to use, unless otherwise noted. Because interest in MAS continues to expand, the number of applications continues to grow as well.

From the traffic and transportation management perspective, the most appealing features characterized by MAS are autonomy, collaboration, and reactivity. Transportation systems modeled by MAS allow distributed subsystems to collaborate with each other to perform traffic control and management based on real-time traffic conditions.

In recent years, more and more agent-based traffic and transportation applications have been reported, including modeling and simulation,^(125-129) traffic control,^(130-139) traffic management frameworks (see references 114, 119, and 140-144), dynamic routing (see references 118, 140, and 145-147), congestion management,^(148,149) fleet management,^(150,151) rail traffic,^(152-155) and air traffic.^(156-158)

Most existing MAS seen in transportation problems present a general structural framework, as follows:

• A complex system (e.g., traffic network, transportation management system, or control system) composed of a set of interactive subsystems is in need of management.
• The system seeks to perform a global, or network-wide, improvement through synthesizing and guiding their cooperation in the distributed subsystems.
• The distributed subsystems are modeled as agents. These agents have their own local knowledge and rules for responding to stimuli, and they have logic to cooperate with their neighborhood agents in formulating their local strategies. Agents have abilities to achieve cooperation and acquire learning. The learning and cooperation mechanisms usually are key components in MAS.
• The agents submit their local plans and strategies to the master system processor, which coordinates all subsystems' plans to ensure a certain (acceptable) level of the global performance of the system. This process usually is modeled through a knowledge base. Learning and cooperation between the master system processor and subsystems could also be realized by agents through protocols.
• The system monitors the performance of each subsystem and assesses all proposals put forward by subsystem agents. It could achieve the overall improved performance by coordinating all subsystems.

It should be noted that many MAS applied in the transportation domain and reviewed in this chapter have been developed outside of the United States. The level of complexity of MAS applications in the transportation domain also reviewed in this chapter appears far less frequently than the agent-based transportation platforms discussed in chapter 4.

MAS Applied in Traffic Management

Traffic management herein refers to a management framework, rather than a comprehensive system with its complete subcomponents. Signal control and route choice components could be ingredients of a management framework but are discussed separately because of their complexities. A selection of MAS applications in traffic management are highlighted in the following examples.

Cooperative Traffic Management and Route Guidance System (CTMRGS), USA^(118,140)

CTMRGS is a cooperative, distributed MAS that assists in the improvement of dynamic routing and traffic management. Agents represent both individual drivers and the system operator. Allocation of network capacity and distribution of traffic advisories are performed by agents that act on behalf of information service providers (ISP). Drivers are ultimately responsible for making travel choices, but ISPs provide advice so that the two entities behave cooperatively, satisfying their own objectives simultaneously. Such a negotiation between an ISP and driver agents seeks a more efficient route allocation across time and space. Drivers' route choice behavior utilizes a knowledge base. An ISP uses a set of utility functions to evaluate the route proposals put forward by drivers.

Tomas and Garcia,⁽¹⁴⁹⁾ Spain

Tomas and Garcia⁽¹⁴⁹⁾ conducted research to study the incident management plan. When an incident is detected offline, a set of traffic management strategies is developed. The implementation of these strategies usually involves negotiations among several traffic administrations. A set of agents, who represent different traffic management operators, share information to produce a knowledge base and communicate with each other to produce a strategy for managing an offline incident scenario on a non-urban road.

TRYS/TRYSA2 (Tráfico, Razonamiento y Simulación/Tráfico, Razonamiento y Simulación Autonomous Agents), Spain⁽¹⁴²⁾

TRYS/TRYSA2 is an agent-based architecture for intelligent traffic management systems. A set of traffic management operators is represented and modeled by agents; proposals of agents are modeled as knowledge-based, or rule-based. Management plan proposals are put forward by different agents who can negotiate and coordinate through heuristic-based artificial intelligent algorithms. The system is reported to support real-time traffic management in the urban motorway network in Barcelona.

CLAIRE, France⁽¹⁵⁹⁾

CLAIRE is a traffic management system based on Automatic Control and AI. Congestions of the system could be ameliorated by traffic engineering methods, modeled as an operator agent, to propose congestion-mitigation strategies. Proposals of an operator are modeled by knowledge-based AI methods.

CARTESIUS (Coordinated Adaptive Real-Time Expert System for Incident Management in Urban Systems), Germany⁽¹⁴⁸⁾

CARTESIUS is a multiagent architecture for the provision of real-time decision support to a traffic operations center for coordinated, interjurisdictional traffic congestion management on freeway and arterial networks. CARTESIUS is composed of two interacting knowledge-based systems that perform cooperative reasoning and resolve conflicts for the analysis of nonrecurring congestion and the online formulation of integrated control plans.

MAS Applied in Dynamic Route Guidance

The following examples outline applications of MAS in dynamic route guidance.

TRACK-R (TRaffic Agent City for Knowledge-based Recommendation), Spain⁽¹⁶⁰⁾

TRACK-R is an agent aiming to generate and sort possible routes to determine the optimum route for a car driver going from one city to another. To generate this information, the TRACK-R agent infers a knowledge base, composed by a partial instantiation of a traffic ontology. Every TRACK-R agent is responsible for a geographical area. If the network involves different areas but with shared elements, the related TRACK-R agents will communicate with each other to achieve a joint recommendation.

Dia,⁽¹⁴⁵⁾ Australia

This study by Dia proposed an agent-based method to model individual driver behavior when subject to the influence of real-time traffic information. A set of survey data was used to calibrate the multinomial logit model for en route quantitative delay information. Several other multinomial logit models were also developed. The results were used to identify the relevant factors and their suitable value for implementation in the agent-based behavioral models. The driver-vehicle units were modeled as autonomous software components that can each be assigned a set of goals to achieve and a database of knowledge computing preferences concerning the driving task.

Bazzan et al.⁽¹⁶¹⁾ and Wahle et al.,⁽¹⁴⁶⁾ Germany

Studies conducted by Bazzan et al.⁽¹⁶¹⁾ and Wahle et al.⁽¹⁴⁶⁾ modeled the impact of real-time information on traffic patterns by using an agent-based model, with special attention to investigating different types of information and their specific effects on traffic patterns. Each driver is an agent, characterized by its goals, resources, and behavior. In the proposed architecture, drivers' behavior is described based on BDI. Traffic models are modeled by a standard cellular automata method.

MAS Applied in Signal Control

The following examples highlight applications of MAS in signal control.

Agent-Based Dynamic Activity Planning and Travel Scheduling (aDAPTS), USA^(114,162)

aDAPTS uses a hierarchical architecture that was developed for intelligent control systems to divide an agent-based control system's structure into three levels: organization, coordination, and execution. A global traffic operation center develops and maintains various control agents for interactive traffic control, road incident detection, and other transportation activities. The agent organization level mainly performs reasoning and planning for task sequences and organizes control agents to achieve specified goals. The agent coordination level is the interface between the organization and execution levels. The agent execution level consists of hardware and software units for deploying, replacing, hosting, and running control agents. Generally this level consists of many field-programmable and configurable devices and is distributed among local area network-linked local systems connected by wide area networks.

HUTSIG, Finland⁽¹³⁶⁾

Developed by the Helsinki University of Technology (HUT), the HUTSIG system is incorporated in a microsimulator called HUTSIM. Each signal operates individually as an agent in HUTSIM, negotiating with its neighborhood signals about the control strategy. The decisionmaking of the agents is based on fuzzy inference that allows a combination of various aspects like fluency, economy, environment, and safety. Area signal control stands on top of individual signals with the goal of minimizing overall delay, which requires cooperation between individual controllers to achieve better performance in the area.

Choy et al.,⁽¹³³⁾ Singapore

Choy et al.⁽¹³³⁾ introduced a multiagent architecture for real-time coordinated signal control in an urban traffic network. The multiagent architecture consists of three hierarchical layers of controller agents: intersection, zone, and regional controllers. Each controller agent is implemented by applying AI concepts (e.g., fuzzy logic, neural network, and evolutionary algorithm). With the fuzzy rule as a base, each individual controller agent recommends an appropriate signal policy at the end of each signal phase. An online reinforcement learning module is used to update the knowledge base and inference rules of the agents.

Botelho,⁽¹³¹⁾ Portugal

This study introduced an interaction control structure with respect to the agents in a traffic-monitoring MAS. The goals of the agent are acquired by three mechanisms: an agent's innate goals, reception of requests in interagent communication, and subgoaling. Agents do not have the same goals irrespective of their current contexts. The system applies conditional goals to build agents with context-dependent goals.

Summary

With respect to MAS, as applied to transportation problems, the review in the prior sections summarizes the following propositions:

• In most of the reviewed transportation applications, MAS is a system method in the paradigm of AI and DAI.
• MAS is a useful tool to model interaction, coordination, and learning of a set of interactive subsystems; it is a decentralized method that simplifies dynamics among subsystems.
• To achieve a global or network-wide objective of the transportation system, MAS could be applied in a hierarchical structure. The higher level agent (system) investigates the performance of a group (subsystems) and has the ability, through agent coordination, to adjust the goals or actions of agents in its group. The global knowledge that informs and activates the coordination mechanism could be modeled by a knowledge base.
• The intelligence of an agent (subsystem) usually is modeled by AI technologies (e.g., rule-based, knowledge-based, or fuzzy rules).
• Because most applied MAS for transportation problems use methods of DAI, they may have less consideration to human behavior (i.e., an agent is a decentralized subsystem rather than an individual traveler).