COSC Decision and Control Project Page

Decision and Control Project: Urban Traffic Prediction and Management

The objective of this work has been to develop layers of control and optimization modules for the purpose of urban traffic management. We utilize the Semantic Control Paradigm to model both macro-level (traffic control) as well as micro-level (vehicle path planning and steering control). A Semantic Controller consists of three modules for Identification, Goal selection and Adaptation respectively (Figures 1a-b).

A model of the highway system, based on historical data provided by Missouri Highway and Transportation Department (MoHTD), has been developed. The prediction and planning system is evaluated using the traffic flow data from nine sensors located on the highway located in the St. Louis Metropolitan area.

The pre-processor consists of codes for calculation of correlation coefficients and Radial Basis Function Neural Network (RBFNN) training algorithm. RBFNNs are trained to predict traffic volumes at nine sensor stations located along the major highways in the St. Louis area. As a part of the training algorithm, the auto-correlation coefficient and the cross-correlation coefficient between sensors are used to select inputs to the RBFNN for each sensor. After the input data have been selected, the K-means algorithm, width estimation and least mean square algorithm are performed to complete the RBFNN training. System Identifier consists of an incident detection rule-based system, a volume estimator for nodes and/or links without sensors, and a speed-volume lookup table for speed estimation.

The Goal Selector handles traffic routing for maximum use of available road network capacity; the Goal Selector consists of two sub-modules, one for traffic management in signaled streets and another module for highway traffic control (advisory). The Adapter copes with changes as well as providing micro-level drivers' support for shortest path routing and steering control (an in-vehicle driver's assistance). In summary, The Identifier has a stochastic prediction module, rules for incident detection, and a radial basis function neural network-based estimator. The Goal Selector consists of Shortest-Path algorithms and a discrete-event-dynamical-system simulation of signaled intersections. The control laws in the Adapter are developed for two situations:

vehicle control within a platoon, and
neurocontrol of a single vehicle.

There are currently nine permanent sensors deployed in several locations on some of the major highways in the area. Figure 3 depicts a facsimile of the St. Louis highway network with marked locations for the sensor stations; it is also our graphical user interface.

From a modeling point of view the problem of dynamic traffic flow assignment can be viewed as the prediction of the behavior of traffic flow where the flow varies both temporally and spatially. The temporal nature of the flow is evident in data shown in Figures 4 and 5; e.g., Figure 4 corresponds to eastbound traffic along I-70 near the City of St. Louis. As a result of this some fundamental issues arise when attempting to model traffic flow, namely:

Where to place traffic flow sensors?
How to characterize the traffic flow?
How to manage the traffic load?
What on-line estimators to use for system identification and parameter estimation?
How to perform vehicle routing and adjust traffic signals?
How to formulate traffic flow? e.g., as interconnected pipes with adjustable valves, or as discrete event dynamics; a system approach versus a mathematical programming and combinatorial optimization.

Accomplishments:

Traffic Estimation and Prediction:

Kalman Filter approach;

Box-Jenkins algorithm;

Radial Basis Function Neural Networks (RBFNNs).

Shortest-Path algorithms

Dijkstra's;

A* search;

L2Queue.

Sensor Mix and Placement

Operations Research: Nonlinear Integer Goal Programing

Discrete Event Dynamical System: Perturbation analysis, Objective Fcn., Sensor Capability Modeling, Performance Evaluation

Incident Detection and Localization

Neuro-Fuzzy Rule-Based System

Comparisons with McMaster's, Minn., and CA algorithms

Performance Measures

Detection rate

False-alarm rate

Mean time to detect

An Illustrative Example:

Our radial basis function neural network consists of a total of 72 neurons. There are 6 input nodes (previous traffic flow) and 1 output (predicted traffic flow). For illustration, let us consider the sensor 605 East (I-70 east bound in Figure 3). After all the autocorrelations and cross-correlations between the 605 East bound and other sensors' have been calculated, the highest 6 correlation coefficients were used as input to the neural network. The 6 centers for each neuron were then calculated using K-means clustering algorithm. After the centers were computed, the width of each neuron was calculated and then we proceeded with the weight training via the least mean squared method.

Box-Jenkins auto-regression integrated moving average (ARIMA) is a traditional regression techniques for time-series forecasting. It consists of three basic components: Autoregressive (AR(p)) component, Moving average (MA(q)) component and Integration (I)component. An AR of order p, AR(p) can be expressed as:

.
An MA of order q, MA(q) can be expressed as:

where

is the error term at time t. Integration is the number of differences needed to take in a time-series to achieve stationarity. An ARIMA(p,q,d) includes both AR and MA terms in the time-series, where p is the order of the autoregression, q is the order of the moving average and d is the number of differences taken.

The task was then to use identification tools to identify the appropriate order for each three basic ARIMA model components. The identification task is usually complex and time consuming. We compared the results of the RFBNN prediction vs. those of the Box-Jenkins method; the RMS error for the RBFNN was one order of magnitude smaller than that of the ARIMA model. As illustrated in Figures 7a-c, the RBFNN yields a better result than the ARIMA model. The training time took less than 5 minutes on a Pentium 100 computer. The code is implemented in Borland C++.

Shortest-Path Algorithms for Street/Highway Traffic Management

Street/highway databases are typically organized as a set of nodes (vertices) and arcs (edges). A computational complexity summary of several exact solution methods for shortest-path problems (SPP) is given in Table 1. The number of vertices in the graph is n, and the number of edges is m.

Dijkstra's SP Requires 3n(n-1)/2 operations; O(n2) running time. A label-setting method.
Partitioning Algorithm O(nm), with modification O(n2). A label-correcting method.
Dijkstra's Two-Tree Algorithm A bi-directional search; Dijkstra's algorithm generated about 50 percent of all vertices to find a SP from s to t; the two-tree method generated 6 percent of the vertices. Good for problems where repeated solutions of SPP are needed.
L-2queue (Pape-All Dest) O(n2m); Storage 4n+2m. A label-correcting method.
S-Heap (Heap-All Dest) O(m log n); Storage 5n+2m.Uses a binary heap, label-correcting method.
Heap-Select-Dest A modification of S-Heap; single origin, multiple destination.
PSA(primal sequential all pairs) O(n3); finds shortest distances between all pairs of vertices. Performed well for transportation problems: took 20% to 35% less time than L-deque or S-Dial.
Table 1 - Computational Complexity Summary for Various Exact Solution Methods

Dijkstra's SP	Requires 3n(n-1)/2 operations; O(n2) running time. A label-setting method.
Partitioning Algorithm	O(nm), with modification O(n2). A label-correcting method.
Dijkstra's Two-Tree Algorithm	A bi-directional search; Dijkstra's algorithm generated about 50 percent of all vertices to find a SP from s to t; the two-tree method generated 6 percent of the vertices. Good for problems where repeated solutions of SPP are needed.
L-2queue (Pape-All Dest)	O(n2m); Storage 4n+2m. A label-correcting method.
S-Heap (Heap-All Dest)	O(m log n); Storage 5n+2m.Uses a binary heap, label-correcting method.
Heap-Select-Dest	A modification of S-Heap; single origin, multiple destination.
PSA(primal sequential all pairs)	O(n3); finds shortest distances between all pairs of vertices. Performed well for transportation problems: took 20% to 35% less time than L-deque or S-Dial.
Table 1 - Computational Complexity Summary for Various Exact Solution Methods

In our work on inter and intra-city travel we have implemented and tested several algorithms. The performance of these algorithms was evaluated for the city of St. Louis with the number of vertices, n, equal to 9,105 and the number of edges, m, equal to 28,702. For example, for a portion of St. Louis City with 379 vertices, and 996 edges, the pre-processing took 9 to 10 seconds, whereas the computation of the path using the L2Q algorithm took an average of 0.107 seconds. For the complete graph of St. Louis City, with 9,105 vertices and 28,702 edges, the preprocessing took about 1.6 hours, and the L2Q algorithm took only 4.1 seconds to compute the shortest path.