The distributed and often decentralised nature of complex stochastic traffic systems having a large amount of distributed data can be represented well by multi-agent architecture. Traditional centralized data mining methods are often very expensive or not feasible because of transmission limitations that lead to the need of the development of distributed or even decentralized data mining methods including distributed parameter estimation and forecasting. We consider a system, where drivers are modelled as autonomous agents. We assume that agents possess an intellectual module for data processing and decision making. All such devices use a local kernelbased regression model for travel time estimation and prediction. In this framework, the vehicles in a traffic network collaborate to optimally fit a prediction function to each of their local measurements. Rather than transmitting all data to one another or a central node in a centralized approach, the vehicles carry out a part of the computations locally by transmitting only limited amount of data. This limited transmission helps the agent that experiences difficulties with its current predictions. We demonstrate the efficiency of our approach with case studies with the analysis of real data from the urban traffic domain.
Multi-agent systems (MAS) often deal with complex applications,
such as sensors, traffic, or logistics networks, and they offer a
suitable architecture for distributed problem solving. In such
applications, the individual and collective behaviours of the agents depend
on the observed data from distributed sources. In a typical distributed
environment, analysing distributed data is a non-trivial problem
because of several constraints such as limited bandwidth (in wireless
networks), privacy-sensitive data, distributed computing nodes, etc.
The distributed data processing and mining (DDPM) field deals with
these challenges by analysing distributed data and offers many
algorithmic solutions for data analysis, processing, and mining using
different tools in a fundamentally distributed manner that pays
careful attention to the resource constraints [
Traditional centralized data processing and mining typically
requires central aggregation of distributed data, which may not always
be feasible because of the limited network bandwidth, security
concerns, scalability problems, and other practical issues. DDPM
carries out communication and computation by analyzing data in a
distributed fashion [
In this study we focus on the urban traffic domain, where many traffic characteristics such as travel time, travel speed, congestion probability, etc. can be evaluated by autonomous agents-vehicles in a distributed manner. In this paper, we present a general distributed regression forecasting algorithm and illustrate its efficiency in forecasting travel time.
Numerous data processing and mining techniques were suggested
for forecasting travel time in a centralized and distributed manner.
Statistical methods, such as regression and time series, and artificial
intelligence methods, such as neural networks, are successfully
implemented for similar problems. However, travel time is affected by a
range of different factors. Thus, accurate prediction of travel time is
difficult and needs considerable amount of traffic data.
Understanding the factors affecting travel time is essential for improving
prediction accuracy [
We focus on non-parametric, computationally intensive estimation, i.e. Kernel-based estimation, which is a promising technique for solving many statistical problems, including parameter estimation. In our paper, we suggest a general distributed kernel-based algorithm and use it for forecasting travel time using real-world data from southern Hanover. We assume that each agent autonomously estimates its kernel-based regression function, whose additive nature fits very well with streaming real-time data. When an agent is not able to estimate the travel time because of lack of data, i.e., when it has no data near the point of interest (because the kernel-based estimation uses approximations), it cooperates with other agents. An algorithm for multi-agent cooperative learning based on based on transmission of the required data as a reply to the request of the agent experiencing difficulties was suggested. After obtaining the necessary data from other agents, the agent can forecast travel-time autonomously.
The travel-time, estimated in the DDPM stage, can serve as an
input for the next stage of distributed decision making of the intelligent
agents [
This study contributes in the following ways: It suggests (a) a decentralized kernel-based regression forecasting approach, (b) a regression model with a structure that facilitates travel-time forecasting; and it improves the application efficiency of the proposed approach for the current real-world urban traffic data.
The remainder of this paper is organized as follows. Section 2 describes the related previous work in the DDPM field for MAS, kernel density estimation, and travel-time prediction. Section 3 describes the current problem more formally. Section 4 presents the multivariate kernel-based regression model adopted for streaming data. Section 5 describes the suggested cooperative learning algorithm for optimal prediction in a distributed MAS architecture. Section 6 presents a case study and the final section contains the conclusions. 2.1
Systems
A strong motivation for implementing DDPM for MAS is given by
Da Silva et al. in [
Klusch at al. [
A common feature of all approaches is that they aim at
integrating the knowledge that is extracted from data at different
geographically distributed network sites with minimum network
communication and maximum local computations. Local computation is carried
out on each site, and either a central site communicates with each
distributed site to compute the global models or a peer-to-peer
architecture is used. In the case of the peer-to-peer architecture, individual
nodes might communicate with a resource-rich centralized node, but
they perform most tasks by communicating with neighbouring nodes
through message passing over an asynchronous network [
A distributed system should have the following features for the
efficient implementation of DDPM: the system consists of multiple
independent data sources, which communicate only through message
passing; communication between peers is expensive; peers have
resource constraints (e. g. battery power) and privacy concerns [
Typically, communication involves bottlenecks. Since
communication is assumed to be carried out exclusively by message passing,
the primary goal of several DDPM methods, as mentioned in the
literature, is to minimize the number of messages sent. Building a
monolithic database in order to perform non-distributed data processing
and mining may be infeasible or simply impossible in many
applications. The costs of transferring large blocks of data may be very
expensive and result in very inefficient implementations [
Moreover, sensors must process continuous (possibly fast) streams of data. The resource-constrained distributed environments of sensor networks and the need for a collaborative approach to solve many problems in this domain make MAS architecture an ideal candidate for application development.
In our study we deal with homogeneous data. However, a
promising approach to agent-based parameter estimation for partially
heterogeneous data in sensor networks was suggested in [
Continuous traffic jams indicate that the maximum capacity of a road
network is met or even exceeded. In such a situation, the modelling
and forecasting of traffic flow is one of the important techniques that
need to be developed [
There are several studies in which a centralized approach is used to
predict the travel time. The approach was used in various intelligent
transport systems, such as in-vehicle route guidance and advanced
traffic management systems. A good overview is given in [
On the other hand, a multi-agent architecture is better suited for
distributed traffic networks, which are complex stochastic systems.
Further, by using centralized approaches the system cannot adapt
quickly to situations in real time, and it is very difficult to
transmit a large amount of information over the network. In centralized
approaches, it is difficult or simply physically impossible to store
and process large data sets in one location. In addition, it is known
from practice that the most drivers rely mostly on their own
experience; they use their historical data to forecast the travel time [
Traffic information generally goes through the following three
stages: data collection and cleansing, data fusion and integration, and
data distribution [
The decentralized MAS approach for urban traffic network was
considered in [
For travel time forecasting different regression models can be
applied. Linear multivariate regression model for decentralized urban
traffic network was proposed in [
Kernel density estimation is a non-parametric approach for estimating the probability density function of a random variable. Kernel density estimation is a fundamental data-smoothing technique where inferences about the population are made on the basis of a finite data sample. A kernel is a weighting function used in non-parametric estimation techniques.
Let X1, X2, . . . , Xn be an iid sample drawn from some distribution with an unknown density f . We attempt to estimate the shape of f , whose kernel density estimator is
n
fˆh(x) = 1 X K
nh
i=1
x − Xi ,
h
(1)
where kernel K(• ) is a non-negative real-valued integrable function
satisfying the following two requirements: R ∞ K(u)du = 1 and
−∞
K(−u) = K(u) for all values of u; h > 0 is a smoothing
parameter called bandwidth. The first requirement to K(• ) ensures that the
kernel density estimator is a probability density function. The second
requirement to K(• ) ensures that the average of the corresponding
distribution is equal to that of the sample used [
A very suitable property of the kernel function is its additive
nature. This property makes the kernel function easy to use for
streaming and distributed data [
We consider a traffic network with several vehicles, represented as
autonomous agents, which predict their travel time on the basis of
their current observations and history. Each agent estimates locally
the parameters of the same traffic network. In order to make a
forecast, each agent constructs a regression model, which explains the
manner in which different explanatory variables (factors) influence
the travel time. A detailed overview of such factors is provided
in [
Let us consider a vehicle, whose goal is to drive through the definite road segment under specific environment conditions (day, time, city district, weather, etc.). Let us suppose that it has no or little experience of driving in such conditions. For accurate travel time estimation, it contacts other traffic participants, which share their experience in the requested point.
In this step, the agent that experiences difficulties with a forecast sends its requested data point to other traffic participants in the transmission radius. The other agents try to make a forecast themselves. In the case of a successful forecast, the agents share their experience by sending their observations that are nearest to the requested point. After receiving the data from the other agents, the agent combines the obtained results, increases its experience, and makes a forecast autonomously.
In short, decentralized travel-time prediction consists of three steps: 1) local prediction; 2) in the case of unsuccessful prediction: selection of agents for experience sharing and sending them the requested data point; 3) aggregation of the answers and prediction. 4
LOCAL PARAMETER ESTIMATION
The non-parametric approach to estimating a regression curve has
four main purposes. First, it provides a versatile method for exploring
a general relationship between two variables. Second, it can predict
observations yet to be made without reference to a fixed parametric
model. Third, it provides a tool for finding spurious observations by
studying the influence of isolated points. Fourth, it constitutes the
flexible method of substitution or interpolating between adjacent
Xvalues for missing values [
Let us consider a non-parametric regression model [
Y = m(x) + ǫ, where ǫ is the disturbance term such that E(ǫ| X = x) = 0 and V ar(ǫ| X = x) = σ2(x), and m(x) = E(Y | X = x). Further, let (Xi, Yi)in=1 be the observations sampled from the distribution of (X, Y ). Then the Nadaraya-Watson kernel estimator is mn(x) =
Pn
i=1 K Pn i=1 K x−Xi Yi h x−Xi h = pn(x) , qn(x) where K(• ) is the kernel function of Rd and h is the bandwidth. Kernel functions satisfy the restrictions from (1). In our case we have a multi-dimensional kernel function K(u) = K(u1, u2, . . . , ud), that can be easily presented with univariate kernel functions as: K(u) = K(u1) · K(u2) · . . . · K(ud). We used the Gaussian kernel in our experiments.
Network packets are streaming data. Standard statistical and data
mining methods deal with a fixed dataset. There is a fixed size n for
dataset and algorithms are chosen as a function of n. In streaming
data there is no n: data are continually captured and must be
processed as they arrive. It is important to develop algorithms that work
with non-stationary datasets, handle the streaming data directly, and
update their models on the fly [
This requires recursive windowing. The kernel density estimator has a simple recursive windowing method that allows the recursive estimation using the kernel density estimator: mn(x) = pn(x) = qn(x) pn−1(x) + K qn−1(x) + K x−Xn Yn h x−Xn h . 5
DECENTRALISED MULTI-AGENT
COOPERATIVE LEARNING ALGORITHM In this section, we describe the cooperation for sharing the prediction experience among the agents in a network. While working with (2) (3) (4) streaming data, one should take into account two main facts. The nodes should coordinate their prediction experience over some previous sampling period and adapt quickly to the changes in the streaming data, without waiting for the next coordination action.
Let us first discuss the cooperation technique. We introduce the following definitions.
Let L = { Lj | 1 ≤ j ≤ p} be a group of p agents. Each agent Lj ∈ L has a local dataset Dj = { (Xjc, Ycj )| c = 1. . . . , N j } , where Xjc is a d-dimensional vector. In order to underline the dependence of the prediction function (3) from the local dataset of agent Lj , we denote the prediction function by m[Dj ](x).
Consider a case when some agent Li is not able to forecast for i some d-dimensional future data point Xnew because it does not have i sufficient data in the neighbourhood of Xnew. In this case, it sends a request to other traffic participants in its transmission radius by sending the data point Xnew to them. Each agent Lj that has received i the request tries to predict m[Dj ](Xnew). If it is successful, it replies i to agent Li by sending its best data representatives Dˆ(j,i) from the neighbourhood of the requested point Xinew. Let us define Gi ⊂ L, a group of agents, which are able to reply to agent Li by sending the requested data.
To select the best data representatives, each agent Lj makes a ranking among its dataset Dj . It can be seen from (3) that each Ycj is taken with the weight wcj with respect to Xnew, where i wcj =
K Pn l=1 K
j Xinew−Xc h
j .
Xinew−Xl h The observations with maximum weights wcj are the best candidates for sharing the experience.
All the data Dˆ(j,i), Lj ∈ Gi received by agent Li should be verified, and duplicated data should be removed. We denote the new dataset of agent Li as Dniew = SLj ∈Gi Dˆ(j,i). Then, the kernel function of agent Li is updated taking into account the additive nature of this function: m[Dniew](x) = m[ Dˆ(j,i)](x) + m[Di](x).
(5) X
Lj ∈Gi
Finally, agent Li can autonomously make its forecast as m[Dniew](Xinew) for Xnew.
i 6
We simulated a traffic network in the southern part of Hanover (Germany). The network contains three parallel and five perpendicular streets, creating fifteen intersections with a flow of approximately 5000 vehicles per hour.
The vehicles solve a travel time prediction problem. They receive
information about the centrally estimated system variables (such as
average speed, number of stops, congestion level, etc.) for this city
district from TMC, combine it with their historical information, and
make adjustments according to the information of other participants
using the presented cooperative-learning algorithm. In this case, the
regression analysis is an essential part of the local time prediction
process. We consider the local kernel based regression model (3) and
implement the cooperative learning algorithm (5). The factors are
listed in Table 1. The selection and significance of these variables
was considered in [
We simulated 20 agents having their initial experience represented by a dataset of size 20 till each agent made 100 predictions, thus s 4 n o it a c inu 3 m m o c f ro 2 e b m u N 1 0
Time making their common experience equal to 2400. We assumed the maximal number of transmitted observations from one agent equals 2.
During the simulation, to predict more accurately, the agents used the presented cooperative learning algorithm that supported the communication between agents with the objective of improving the prediction quality. The necessary number of communications depends on the value of the smoothing parameter h. The average number of necessary communications is given in Figure 1. We can see the manner in which the number of communications decreased with the learning time. We varied h and obtained the relation between the communication numbers and h as a curve. The prediction ability of one of the agents is presented at Figure 2. Here, we can also see the relative prediction error, which decreases with time. The predictions that used communication between agents are denoted by solid triangles, and the number of such predictions also decreases with the time.
The goodness of fit of the system was estimated using a
crossvalidation technique. We assume that each agent has its own training
set, but it uses all observations of other agents as a test set, so we
use 20-fold cross-validation. To estimate the goodness of fit, we used
analysis of variance and generalized coefficient of determination R2
that provides an accurate measure of the effectiveness of the
prediction of future outcomes by using the non-parametric model [
Prediction after communication 5 .
2 rrr o itsneg .02 a frceo .15 e iltvaeR .01 5 . 0 0 .
0 y c n e u q e r F 0 8 0 6 0 4 0 2 0
Relative prediction error and communication frequency of a
single agent over time 0.75 0.80 0.90
0.95 0.85
R2 accuracy (presented by R2) and the number of necessary communications (presented by the percentage of not predicted observations), which depend on h. The point of trade-off should depend on the communication and accuracy costs.
R2 goodness of fit measure using cross-validation for the whole system for different h Characteristic of System
System average R2 Average % of not predicted observations h=2
A linear regression model [
In this study, the problem of travel-time prediction was considered. Multi-agent architecture with autonomous agents was implemented for this purpose. Distributed parameter estimation and cooperative learning algorithms were presented, using the non-parametric kernelbased regression model. We demonstrated the efficiency of the suggested approach through simulation with real data from southern Hanover. The experimental results show the high efficiency of the proposed approach. In future we are going to develop a combined approach that allows agent to choose between parametric and nonparametric estimator for more accurate prediction.
The research leading to these results has received funding from the European Union Seventh Framework Programme (FP7/2007-2013) under grant agreement No. PIEF-GA-2010-274881. We thank Prof. J. P. M u¨ller for useful discussions during this paper preparation.