Application of Agent Technology to Traffic Simulation

Kutluhan Erol, Renato Levy, James Wentworth
Intelligent Automation Inc. Intelligent Automation Inc. Federal Highway Administration
kutluhan@i-a-i.com rlevy@i-a-i.com jameswentworth@fhwa.dot.gov
2 Research Pl #202 Rockville MD 20850 USA 6300 Georgetown Pike
Tel: +1 (301) 590 3155 Fax: +1 (301) 590 9414 McLean VA 22101 USA

 

Abstract

The economic impact of traffic management grows each day. Infrastructure improvements are costly, hence any such project must be carefully evaluated for its impact on the traffic. Emphasis on traffic simulation tools has increased in the last five years to help evaluate new traffic-control strategies, as well as planned road constructions. Building high-quality traffic simulations has several challenges, including computational performance, the accuracy of models in representing the traffic flow, and the difficulty of integration with advanced traffic management and traffic information systems. In this paper, we report on our work on an agent-based approach to traffic simulation, and how it addresses these issues. *

Keywords: traffic simulation, multi agent systems, distributed computing

Significance of Traffic Modeling and Simulation

The economic impact of traffic management grows each day. Well-designed and well-managed highway systems reduce the cost of transporting goods, cut energy consumption, and save countless person-hours of driving time. To reduce congestion, many countries have been investing heavily in building roads, as well as in improving their traffic control systems. The 1998 budget for Federal Highway Administration of USA is $19,680,000,000. Of this amount, $1,047,000,000 is allocated for congestion mitigation and air quality improvement [US Budget '98].

Infrastructure improvements are costly, hence any such project must be carefully evaluated for its impact on the traffic. Computer simulation models can be very valuable in making those evaluations in a cost-effective manner. Such models can be used to evaluate modifications not only under nominal conditions, but also under hypothetical scenarios that would be difficult to observe in the real world. For example, such a simulator can be used to predict congestion levels for future, based on demographic forecasts.

Emphasis on traffic simulation tools has increased in the last five years, and several packages such as CORSIM, CONTRAM, CORFLO, PARAMICS, have been implemented. A recent survey of such systems, reports several major problems including computational performance, the accuracy of models in representing the traffic flow, and the difficulty of integration with advanced traffic management and traffic information systems [Skabardonis 98].

We have been working on an agent-based approach to time-critical control and simulation. In this paper, we report our work on traffic simulation, and how it addresses the issues above. Details can be found in [Erol 98].

Agent Technology and Traffic Simulation

Traffic can be viewed as a complex system [Faieta et. al., Sanford]. Developing macro models is one of the primary approaches to modeling complex systems. Macro models follow a top-down approach, focusing on the observable behavior of a system. They try to define and regenerate the observable behavior in terms of aggregate, abstract parameters, and their probability distributions. In the case of traffic, the macro models are usually derived from fluid dynamics, and they involve aggregate parameters such as traffic volume and average speed on artilleries in a traffic network.

Simulations based on macro models have the advantage that run-time can be fairly short, as the computation is based on aggregate, abstract parameters. Macroscopic models are helpful when only a coarse prediction of conditions is sufficient, such as a motorist advance warning system.. Most aspects of complex systems, however, are highly nonlinear. Such systems are often extremely sensitive to initial conditions, and even infinitesimal perturbations to initial conditions can have arbitrarily large impact on the global system behavior. In the process of aggregating and abstracting information, macro models lose their sensitivity, and they capture the behavior of traffic only under idealistic conditions.

An alternative approach that can potentially produce better quality results is micro modeling. This is a bottom-up approach, where a complex system is viewed as a large set of small, interacting components. The main focus is on identifying the components in a system, discovering their local behaviors and the interactions among them. The global system behavior emerges from the local behaviors of the individual components, and their interactions. As reported in many articles in a wide range of domains [Reynolds, Mataric], very complex, realistic global behavior can be obtained from simple local behaviors. In the case of traffic, the research effort has focused on driver behavior, car following and lane changing models. In 1994, at the Turner-Fairbank Highway Research Center in McLean, Virginia, research was initiated to evaluate the emergent behavior approach to simulating traffic. A simple lane merge situation was successfully modeled showing that this modeling paradigm had the potential to capture traffic behavior quite well. The logic was simple, yet the vehicles behaved much as vehicles on the road behave with characteristic variations in acceleration and deceleration. A follow up study at the University of Arizona is developing an algorithm and prototype code to model vehicles and pedestrians using emergent behavior theory with emphasis on pedestrian-vehicle-intersection geometry interaction. The model would be used to determine crosswalk capacity, assist in developing signal timing plans, determine desirable crosswalk widths, and lengths, and aid in the geometric design of intersections. The simulation prototype will track operational efficiency and safety characteristics.

Two issues with micro simulation are computational performance, and software development cost. Micro simulations run at a very detailed level, emulating the behavior of every individual entity in the system, and thus they are computationally very intensive. Running a micro simulation of a metropolitan area traffic network involves mimicking the behavior of millions of cars, street lights, etc, and it can be very time consuming. Conventional software design and implementation principles and tools are tailored towards top-down approaches. They do not readily provide the support to define local behaviors of entities in a micro simulation, and their interactions [Levy et .al]. Neither they provide the tools for quick, efficient implementations. CORSIM, for instance, was implemented in FORTRAN, undoubtedly an excruciatingly painful task. Clearly, a new software paradigm was required.

Advances in distributed control and computer networks have culminated in the agent technology, a natural successor to the object-oriented paradigm. A multi agent system consists of autonomous pieces of software (agents) that not only encapsulate local information and algorithmic expertise as the objects do, but also local control and self-initiative. Agents interact by exchanging messages, and the global system behavior emerges from their interactions.

In recent years, a number of agent infrastructures with varying flavors and sophistication have been developed to facilitate the implementation of multi-agent systems. Some systems such as Voyager provide the bare bones of distributed communication, ISIS emphasizes fault-tolerent computing, Telescript focus on mobile computing; DMARS provides agents with deductive reasoning capabilities, and Cybele agent infrastructure [Erol] of Intelligent Automation Inc. focuses on large-scale systems capable of hosting thousands of agents.

Agent-Based Traffic Simulator

The traffic simulator described in this paper was initially implemented using JAVA communication mechanisms, and then implemented using Cybele 3.0. Services provided by Cybele significantly improved the development time and computational performance for the simulator.

Cybele provides location-independent high-performance communication among agents, agent migration, and load-balancing for computational resource allocation, as well as a detailed activity model for implementing interactions among agents. In Cybele Framework, agents are clustered into communities, and each agent community is hosted on a computer on the network. Inter agent communication utilizes subject-based addressing, a location-independent publish/subscribe paradigm. However, messages within a community arrive much faster than messages among communities.

The main entities in the traffic network are road segments, intersections, vehicles, traffic lights, signs and sensors, which are modeled as agents. The traffic network can be partitioned into regions, along geographical boundaries. Agents corresponding to entities in the same region are hosted together in the same agent community, so that they have a high-bandwidth, low latency communication among them. Vehicle agents are mobile: as they enter a new region, they will physically migrate to the agent community hosting that region.

Regions are highly autonomous. When simulation of a new region is deployed, it will automatically connect and synchronize with the adjoining regions already running, accepting incoming vehicles, and sending outgoing vehicles. If an adjoining region is not running at the time, the vehicles moving to that region are discarded. Incoming traffic from that region is emulated based on historical probability distributions. This approach allows flexible simulation of large traffic networks. Regions can be distributed to the computers on the network, and depending on the level of interest, each region can be simulated in detail in micro level, abstractly in macro level, or it may not even be simulated, by relying on probability distributions to model the traffic coming out of that region. Thus this approach helps integrate partitions of large traffic network simulations that use very different simulation techniques.

Intersection agents are responsible for controlling the flow of vehicle agents from one segment to the next. They operate the traffic lights. Intersection agents at the boundary of a region can act as sources or sinks when the adjoining region is not being simulated. In such a situation, the intersection will generate the incoming traffic using a probability distribution.

A vehicle agent contains the physical attributes of the vehicle such as length, acceleration, type, as well as the driver's characteristics, such as aggressiveness and route. It also includes the car-following and lane-changing behavior. In implementing those behaviors, the vehicle agent needs to continuously interact with the vehicles around it. In order to provide fast communication among interacting vehicle agents, vehicle agents are implemented as aglets, and hosted on the road segment agent that they travel on. An aglet has the same conceptual attributes and the behavior as an agent, except that fellow aglets hosted on the same agent can have very fast, shared-memory communication. The road segment agent monitors the position and the lane of the vehicles on it, and interfaces with the two intersection agents at either end. It also hosts the sensor and advisory-sign aglets.

Cybele provides an activity model, where different types of behaviors can be modeled as state-transition graphs, and integrated together within an agent. It allows composing complex agent behaviors from primitive behavior patterns using high-level design tools. This approach allows us to express sophisticated driving behaviors, and manipulate and modify those behaviors easily, even at run-time. It also helps to separate different activities of an agent, such as the car-following behavior of a vehicle agent, from its route planning. Thus we can easily delineate the emulation of the physical interactions and the control activities, work on them separately, and integrate them seamlessly. This supports our work on time-critical decision making and adaptive control strategies for traffic. Cybele also provides high-performance, multicast-communication mechanisms that facilitate building an animation component for the simulator, by tapping into the conversations among agents. The figure below depicts the simulation from four adjoining regions animated at run-time. It helps us observe congestion patterns and incidents.

This figure depicts the simulation from four adjoining regions animated at run-time. It helps us observe congestion patterns and incidents.

Conclusion and Future Work

In this paper, we have discussed the application of agent technology to traffic simulation. Our preliminary work in this area indicates that agent technology can significantly reduce the software development cost and time of implementing traffic simulators, when suitable tools, such as the Cybele agent infrastructure are utilized. Agent-based systems are inherently distributed. Cybele allows such systems to be executed over any number of heterogeneous computers on a network, enhancing their scalability. Very large traffic networks can be simulated by harnessing the computing power on a network. For accurate results, micro simulation models must capture the rich and diverse behavior of drivers. Activity structures of agents help us represent complex driver behavior, and support integration of sophisticated control strategies.

Future research directions include developing new techniques to automate the process of tuning an agent-based traffic simulator to a given locality, using the observed traffic data. The driver behaviors vary dramatically with geographic location, and change over time. Currently the process of fitting a simulation model to a given locality is a tedious, ad hoc procedure. Agent-based traffic models will also facilitate experimenting with distributed, adaptive traffic control strategies operating based on local information. Potential advantages to an agent-based approach to traffic control include reduction in congestion levels, improved robustness and reliability, and reduction in the traffic communication infrastructure. References

* This work was funded by FHWA Contract DTFH61-97-P-00240 to Intelligent Automation Inc. We thank Bradley Matthews and Brian Birtle for the GUI component.

FHWA
TFHRC Home | FHWA Home | Feedback

United States Department of Transportation - Federal Highway Administration