Large-scale stochastic optimization for agent-based traffic simulations

Project partner

CoLab, ETH Zürich

IVT staff

K. Meister
K.W. Axhausen

Client

ETH Zurich

Duration

10/2005 - 9/2008

Abstract

We propose the development of novel algorithms for the optimization of large scale agent based models of complex physical systems with an emphasis on its application to traffic simulations.

Agent-Based Modeling (ABM) of complex systems entails interactions among a collection of autonomous entities called agents. In adaptive models the agents are capable of altering their behaviour, depending on the system that they represent, as they react to the macro scale structures emerging from their interactions.

The advent of large scale parallel computer architectures, for which ABM are highly suitable, presents the possibility of studying microscopic phenomena using detailed microscopic descriptions, such as ABMs. Microscopic descriptions are well suited to problems for which no suitable mesoscopic or macroscopic description is available such as in well established atomistic models (as in molecular dynamics for chemistry and engineering) and in systems inherently linked with microscopic descriptions (as in the proposed case of traffic simulations). Traffic is a representative of a complex system composed of a large number of individual components with spontaneously forming spatially and temporally varying structures.

ABMs can complement relevant macroscale descriptions of transportation problems providing a bottomup approach to the simulation of these phenomena. This bottom-up approach constitutes the strength as well as the weakness of ABM, as the validity of the model can only be assessed after the macroscale behaviour of the system has emerged and has been validated with available experimental data.
The development of suitable agent interaction rules relies on optimization algorithms or adaptive learning procedures. As ABM involve large numbers of interacting entities the resulting optimization problem is of very high dimension. The high dimensionality of the problem along with issues such as the heterogeneity of agent interactions provides for a challenging optimization problem.

In transportation science, over the past ten years, a number of sophisticated large-scale models have been developed in order to understand the emergence of traffic jams and the factors influencing individual travel behavior. In parallel, innovative technologies, such as GPS, have been developed and deployed to acquire, in real-time, large volumes of data relevant to transportation systems such as traffic flow measurements over metropolitan areas. The modeling of these systems often involves tuning of its parameters in an ad-hoc manner in order to simulate real world problems. The goal of this proposal is to develop stochastic optimization techniques that take advantage of large scale parallel computer architectures as well as of domain knowledge and data specific to the transportation problem.

In this framework, our research aims at extending stochastic optimization algorithms to solve large scale stochastic problems, and in particular to minimize the differences between the outputs of agent based traffic simulations and real-world measurements. We envision that this process will increase the predictive power of traffic models and will accelerate the discovery of underlying properties of the studied system. We plan to use machine learning techniques and EAs in order to solve these challenging parameter identification and calibration problems. The developed methodologies will be suitable to solve a number of large-scale, stochastic non-linear, non-convex, optimization problems.

The objectives of our research are :

• to develop state-of-the-art EAs to solve large-scale and stochastic non-linear optimization problems and

• to implement these methods in order to improve agent-based traffic prediction models in the identification of simulation parameters to reproduce conditions observed in real-time andthe dynamic analysis of long-term patterns to identify structural changes in the system.
  

We believe that the developed optimization techniques, will not only be specific to the transportation problem, but they are developed so as to provide a more general framework for the optimization of large scale ABMs.

Publications

Meister, K., M. Balmer und K. W. Axhausen (2005) An improved replanning module for agent-based micro simulations of travel behavior, Arbeitsberichte Verkehr- und Raumplanung, 303, IVT, ETH Zürich, Zürich. Download

Further information

Research database project 15678