Efficient Traffic Simulation Using Agents within the Global Cellular Automata Model

Abstract

We present a mapping of the well known Nagel-Schreckenberg algorithm for traffic simulation onto the Global Cellular Automata (GCA) model using agents. The GCA model consists of a collection of cells which change their states synchronously depending on the states of their neighbors like in the classical CA (Cellular Automata) model. In contrast to the CA model the neighbors can be freely and dynamically selected at runtime. The vehicles are considered as agents that are modeled as GCA cells. An agent is linked to its agent in front, and an empty cell is linked to its agent behind. In the current generation t the position of an agent is already computed for the generation t+2. Thereby the agents movements and all cell updates can directly be calculated as defined by the cell rule. No searching of specific cells during the computation is necessary. Compared to an optimized CA algorithm (with searching for agents) the GCA algorithm executes significantly faster, especially for low traffic densities and high vehicle speeds. Simulating one lane with a density of 10% on an FPGA multiprocessor system resulted in a speed-up (measured in clock ticks) of 14.75 for a system with 16 NIOS II processors.