26-11-2012, 12:41 PM
A computational market for distributed control of urban road traffic systems
A computational market.pdf (Size: 4.91 MB / Downloads: 35)
Abstract
In the last decade, economic approaches based on
computational markets have been proposed as a paradigm for the
design and the control of complex socio-technical systems, such as
urban road traffic systems. The control problem of an urban road
traffic system can be modelled as a distributed resource allocation
problem, in order to apply market-based techniques as solution
method. In this work, we design a competitive computational
market, where driver agents trade the use of the capacity inside
the intersections with intersection manager agents. We show how
the market dynamics influence the drivers’ behaviour, leading to
a more efficient use of the urban road traffic system, in terms
of lower average travel times and less congestion.
INTRODUCTION
Controlling a large-scale system such as an urban road
traffic system is not a trivial task, due to its unpredictability
and uncertainty. The optimal control of flows in any traffic
network, including road traffic ones, is a well-known NPhard
problem [18], which means that the time required to find
an optimal solution increases faster than polynomially with
the network size. Due to this NP-hardness, traditional control
techniques usually consist in an off-line search for the best
control strategy for typical situations that traffic planners faced
in the past. Unfortunately, fluctuations in dynamic systems are
usually huge, and therefore the resulting control strategy is
optimised for a situation that is true on average but that never
occurs in any single instant [16].
RELATED WORKS
The problems and challenges posed by the road traffic and
transportation domain have attracted scientists and experts
from different fields. The solutions proposed by the scientific
community to alleviate traffic congestion and increase safety
span from improving the management systems, by a major use
of IT systems, to the automation of the vehicles and the road
infrastructure.
In recent years, there is an increasing interest in applying
agent-based techniques for traffic control [3][4][11][25]. Urban
road traffic control appears to be a particularly promising
application area for agent technology. In [14] intelligent traffic
light agents create green waves in a particular direction by
solving distributed constraint optimisation problems. In [15]
the traffic light agents learn in a coordinated way the best
signal plans. In [16] a self-organising approach is presented,
which leads to emergent coordination patterns and achieves
an efficient, decentralised traffic light control. Still, in these
approaches only the entities that govern the intersection control
devices (traffic lights) are modelled as agents, while drivers are
only considered insofar as they are a part of the traffic flow
through the road network.
DESIGN OF A COMPUTATIONAL MARKET
Motivation
The objective of this work is designing a competitive
computational market for the control of an urban road traffic
system. Two types of actors are operating in this market:
1) software agents that act on behalf of human drivers and
acquire the right to cross the intersections of an urban road
network, and 2) intersection manager agents that govern the
intersections and provide such rights. The ultimate goal of
such a market is enhancing mobility and reducing travel times.
The advantages of such an approach are manifold. Having
the possibility of adjusting prices, intersection manager agents
have a powerful lever to control a system whose components
are otherwise hard to influence. Furthermore, the pricing
policies have different effects on different groups of drivers
(e.g., business drivers or leisure drivers [26]), thus allowing
for control strategies targeted at specific types of drivers.
Intersection manager model
In our model, each intersection manager competes with all
the others for the provision of the resource it supplies. Our
goal as market designers is to enforce the attainment of the
general market equilibrium, a situation where the amount of
resources sought by the buyers is equal to the amount of
resources provided by the suppliers. The price vector p that
corresponds to the general market equilibrium is in general
computed through a walrasian auction. This type of auctions,
introduced by Walras in 1874 [27], involves a set of buyers B
and a set of suppliers V. The auction proceeds as follows. At
time t, each buyer of the set B notifies to the suppliers of the
set V the quantity of resources she is willing to buy, given the
actual price vector pt. In fact, the quantity of goods a buyer is
willing to buy depends on the prices of such goods. Similarly,
also the quantity of goods a supplier is willing to provide
depends on the actual prices that such goods can be sold at
in the market. With this information, each supplier computes
the difference between the buyers’ demand for the resource
she provides and the supply of such resource. If there is
excess supply, the prices are lowered, whilst if there is excess
demand the prices are raised.
Driver agent model
First, we informally define how the driver agent acts on
behalf of the human driver that wants to travel from her origin
to her destination, and then more formally in terms of choice
set and decision-making functions.
When a human driver travels through an urban road network,
she competes for the use of a scarce resource with the
other human drivers. This resource is allocated through a market
where driver agents and intersection managers participate
as buyers and suppliers respectively. As said in section III-B,
we assume that each vehicle is equipped with a driver agent
that acts on behalf of the human driver. In particular, such
personal agent is in charge of choosing a route r and trading
with the intersection managers that regulate the intersections
of the route r. From the perspective of the driver agents, a
route r is characterised by two attributes.
SIMULATION ENVIRONMENT
To evaluate our approach we implemented a simulator
based on the mesoscopic model of Schwerdtfeger [23]. In
this model, the dynamic of a vehicle is governed by the
average traffic density on the link it traverses rather than the
behaviour of other vehicles in the immediate neighbourhood
as in microscopic models.
The network is divided into stretches with similar characteristics
(number of lanes . . . ), which in turn are divided into
links of typically 500 meters length for which constant traffic
condition is assumed. This assumption means that, given the
link density (lk), a link’s mean speed u(lk) is calculated
using the speed-density function. A speed-density function is
a function that is used to estimate the mean speed of a link as
a function of the density on that link. There are several speeddensity
functions in the traffic flow literature [10].
CONCLUSION
In this paper we studied how the problem of controlling
an urban road traffic system can be modelled as a competitive
market, where driver agents and infrastructure agents trade the
intersection capacity. The empirical evaluation showed how
the market dynamics affect the driver agent decision making,
contributing to generate benefits by means of lower average
travel time and less congestion.