In The Fourth International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS 05),

pp. 471-477, Utrecht, The Netherlands, July 2005.

Multiagent Traffic Management: An Improved Intersection

Control Mechanism

Kurt Dresner and Peter Stone

University of Texas at Austin
Department of Computer Sciences
Austin, TX 78712 USA
{kdresner, pstone}@cs.utexas.edu

ABSTRACT Multiagent Systems (MAS) is the subfield of AI that aims to pro-

Traffic congestion is one of the leading causes of lost productivity vide both principles for construction of complex systems involving
and decreased standard of living in urban settings. Recent advances multiple agents and mechanisms for coordination of independent
in artificial intelligence suggest vehicle navigation by autonomous agents’ behaviors [16]. In an earlier paper, we proposed an MAS-
agents will be possible in the near future. In a previous paper, we based approach to alleviating traffic congestion, specifically at in-
proposed a reservation-based system for alleviating traffic conges- tersections [3]. In this paper, we describe several ways in which
tion, specifically at intersections. This paper extends our prototype we have transformed that system into a more realistic and imple-
implementation in several ways with the aim of making it more mentable system.
implementable in the real world. In particular, we 1) add the abil- Current methods for enabling traffic to flow through intersections
ity of vehicles to turn, 2) enable them to accelerate while in the include building overpasses and installing traffic lights. However,
intersection, and 3) augment their interaction capabilities with a the former is very expensive and forbids turning, while the latter
detailed protocol such that the vehicles do not need to know any- can be quite inefficient, often requiring cars to remain stopped even
thing about the intersection control policy. The use of this protocol when no cars are present on the intersecting road.
limits the interaction of the driver agent and the intersection man- At this time, it is possible to create a small-scale system in which
ager to the extent that it is a reasonable approximation of reliable all cars are piloted by a central computer. Consider, for example,
wireless communication. Finally, we describe how different in- the task of controlling ten vehicles on an open factory floor. How-
tersection control policies can be expressed with this protocol and ever, growing such a system to handle an intersection in which a
limited exchange of information. All three improvements are fully city’s worth of cars might turn up would involve prohibitively ex-
implemented and tested, and we present detailed empirical results pensive and inefficient communication and control infrastructure.
validating their effectiveness. Here we aim to maximize the efficiency of moving cars through
intersections with minimal centralized infrastructure. We assume
that intersections can be outfitted with a simple wireless communi-
1. INTRODUCTION cation system and a protocol (which we introduce here) for com-
Traffic congestion is one of the leading causes of lost productiv- municating with oncoming traffic and giving permission for cars to
ity and decreased standard of living in urban settings. According pass.
to a recent study of 85 U.S. cities [17], annual time spent waiting In our system, vehicles must traverse intersections according to
in traffic has increased from 16 hours per capita to 46 hours per a set of parameters agreed upon by the vehicle and the intersection
capita since 1982. In the same period, the annual financial cost manager (as they do today by obeying red and green lights), but
of traffic congestion has swollen from $14 billion to more than otherwise are free to decide for themselves how to drive. Each
$63 billion (in 2002 US dollars). Each year, Americans burn ap- car is an autonomous agent, and in particular need not surrender
proximately 5.6 billion gallons of fuel while idling in heavy traffic. control to any centralized decision maker.
Recent advances in artificial intelligence suggest that autonomous Given the above assumptions, we have proposed a novel reservation-
vehicle navigation will be possible in the near future. Individual based system by which cars request and receive time slots from the
cars can now be equipped with features of autonomy such as cruise intersection during which they may pass [3]. While this system
control, GPS-based route planning [13, 15], and autonomous steer- showed the potential for a reservation-based system to drastically
ing [9, 11]. Once individual cars become autonomous, many of the improve the efficiency of intersections, it required driving agents to
cars on the road will have such capabilities, thus opening up the maintain a constant velocity in the intersection and forbade turning
possibility of autonomous interactions among multiple vehicles. (a very important part of intersections). Furthermore, it did not ad-
equately specify how they should interact. In this paper, we take
three large steps towards making the system implementable in the
real world. First, we augment it to allow turning. Second, we make
Permission to make digital or hard copies of all or part of this work for acceleration in the intersection possible, which allows us to sub-
personal or classroom use is granted without fee provided that copies are sume the stop sign policy within the reservation framework. Third,
not made or distributed for profit or commercial advantage and that copies we specify a protocol to govern the interactions of the vehicles and
bear this notice and the full citation on the first page. To copy otherwise, to
republish, to post on servers or to redistribute to lists, requires prior specific the intersection such that the vehicles do not need to know anything
permission and/or a fee. about the intersection control policy. The use of this protocol limits
AAMAS’05, July 25-29, 2005, Utrecht, Netherlands. the interaction of the driver agent and the intersection manager to
Copyright 2005 ACM 1-59593-094-9/05/0007 ...$5.00.
the extent that it is a reasonable approximation of reliable wireless 1. The agents should only communicate information which is
communication. Using this protocol, we detail how many every- necessary for the system to function properly.
day intersection control policies, such as the traffic light and the
stop sign can be encoded. 2. The agents should only have access to information that can
be reliably obtained with current technology.
2. THE ORIGINAL SYSTEM 3. Communication failure (dropped messages) should not vio-
Previously, we proposed a novel reservation-based multi-agent late the system’s safety properties.
approach to alleviating traffic, specifically at intersections. This
4. The vehicles should be treated as individual agents, and no
system consisted of two types of agents: intersection managers and
centralized controller should have any more control over them
driver agents. Each system consists of an intersection manager for
than necessary.
each intersection and a driver agent for each vehicle. Intersection
managers are responsible for directing the vehicles through the in- 5. The system should incorporate a simple communication pro-
tersection, while the driver agents are responsible for controlling tocol that allows agents to know only a minimal amount about
the vehicles to which they are assigned. To improve the throughput each other. As long as agents obey and understand the proto-
and efficiency of the system, the driver agents “call ahead” to the in- col, no extra information exchange or other interaction should
tersection manager and request space-time in the intersection. The be required.
intersection manager then determines whether or not these requests
can be met. Depending on the decision the intersection manager 6. Every vehicle should eventually make it through the intersec-
makes, the driver agent either records the parameters of the request tion (i.e. no deadlocks or starvation).
(the reservation) and attempts to meet them, or it makes another
request at a later time.
3.2 Acceleration in the Intersection
To determine whether or not a request can be met, the reserva- Our previous implementation of the reservation system made
tion manager simulates the journey of the vehicle across the inter- reservations for vehicles only at a constant velocity. This prop-
section, which it divides into a grid of n × n tiles. The parameter n erty is partly responsible (along with others discussed in Section 6)
is called the granularity of the reservation manager. At each time for the deadlocks their system experienced. With this restriction, if
step of the simulation, it determines which tiles the vehicle occu- a vehicle made a reservation at a low velocity, it would consume a
pies. If throughout this simulation, no required tile is occupied by large amount of space-time in the intersection. This, in turn, would
another vehicle (from a previous reservation), the manager reserves cause other vehicles to be delayed making their reservations (which
the tiles for this vehicle. would also be at low velocities). These slow-downs often led to
After creating a custom simulator, we evaluated the performance permanent deadlocks. By allowing acceleration in the intersection,
of the reservation system against two other intersection control our system always eventually recovers from slowdowns caused by
policies - the overpass and the traffic light. An intersection con- heavy traffic.
trol policy is a method the intersection managers use to determine Because the reservation manager can now return reservations
when specific vehicles are allowed in the intersection. Using the with accelerations, the problem becomes determining what those
simulator, we showed that using the reservation-based policy, ve- accelerations should be. By varying its accelerations just right, a
hicles crossing an intersection experience much lower delay (in- vehicle may be able to fit through a small opening in the intersec-
crease in travel time from the optimal) versus the traffic light. Fur- tion. Somehow, the intersection manager must choose the correct
thermore, we showed that the reservation-based policy drastically accelerations. We chose to use a very simple heuristic: the intersec-
increases the throughput of the intersection. For any realistic inter- tion manager first tries to have the entering vehicle accelerate to the
section control policy, there exists an amount of traffic above which maximum allowed velocity. If such a reservation is not possible, it
vehicles arrive at the intersection more frequently than they can go attempts to make a constant-velocity reservation. If the constant-
through the intersection. At this point, the average delay experi- velocity reservation also fails, the request is rejected. Using ac-
enced by vehicles travelling through the intersection grows without celeration in the intersection, along with the protocol presented in
bound. They demonstrated that compared to the traffic light, this Section 4, allows us to implement the stop sign policy within this
amount of traffic is much higher for the reservation system. In ad- reservation framework.
dition to our simulator applets1 Garcia and Vidal have implemented
applets reproducing the results2 .
3.3 Excess Information
Our previous work relied on the assumption that vehicles knew
each others’ positions and reservation statuses at all times. How-
3. IMPROVING THE ORIGINAL MODEL ever, it is not immediately obvious how any vehicle would get this
The results described in the previous section are very encourag- information in the real world. While exact position information
ing. In this section, we offer several ways to improve the system would be hard to come by, there is no reason to believe that ve-
with regard to flexibility, efficiency, and making it implementable hicles would have any access at all to the internal state of other
in the real world. vehicles around it (even ones in close proximity). An older model
vehicle interacting with a new model vehicle can not be expected
3.1 Desirable Properties to understand the newer model’s inner workings. Additionally, the
In order for the reservation-based mechanism to be both realis- manufacturer of the driver agent may not want other vehicles to
tic and practical, we believe that the following properties ought to know what goes on “under the hood.”
hold.
1 3.4 Unspecified Communication Between Driver
http://www.cs.utexas.edu/users/kdresner/
2004aamas Agents and Intersection Managers
2 Our previous paper [3] specified which agents govern which as-
http://jmvidal.cse.sc.edu/netlogomas/
TrafficManagementMendoza.html pects of their system, but they do not specify exactly how the agents
coordinate their efforts. Additionally, in their work, any driver 1. C ONFIRMATION — This message is a response to a vehicle’s
agent would have to understand what kind of intersection control R EQUEST (or C HANGE -R EQUEST) message. It can contain
policy the intersection manager was using in order to interact with a counter-offer by the intersection. The reservation param-
it. To address these issues, we created a detailed communication eters in this message are implicitly accepted by the vehicle,
protocol to govern and restrict the interactions of driver agents and and must be explicitly cancelled if the driver agent of the ve-
intersection managers. hicle does not approve. Note that this is safe to faulty com-
This protocol solved three problems at once. First, all infor- munication — the worst that can happen is that the intersec-
mation between the agents goes through one monitorable channel, tion reserves space that does not get used.
which makes it much easier to reason about. Second, by limiting
the interactions of the agents to a few message types, we can en- 2. R EJECTION — By sending this message, an intersection can
sure that no agent has an unrealistic amount of control over another. inform a vehicle that the parameters sent in the latest R E -
Third, the agents now have a way to communicate that is identical QUEST (or C HANGE -R EQUEST ) were not acceptable, and
for any intersection management policy or driver agent policy. A that the intersection either could not or did not want to make
vehicle can cross an intersection using a traffic light without know- a counter-offer. This message also contains a field indicat-
ing it is a traffic light. The traffic light speaks the same language ing whether or not the rejection was because the reservation
as a stop sign and a reservation system. The driver agent thus must manager requires the vehicle to stop at the intersection be-
have a behavior that works with all sorts of intersection control fore entering. This lets the driver agent know that it should
policies — that is, the driver agent must view the intersection as a not attempt any more reservations until it reaches the inter-
black box, and vice versa. section.
3. ACKNOWLEDGMENT — This message acknowledges the re-
4. PROTOCOL ceipt of a C ANCEL or R ESERVATION -C OMPLETED message.
We have created a protocol by which the agents can communi- 4.2 Protocol Actions
cate the bare minimum of information necessary to function appro-
priately. The protocol consists of several message types for each In addition to message types, the agents involved (the vehicles
kind of agent, as well as some rules governing when the messages and the intersection) must obey a set of rules. These are not entirely
should be sent and what sorts of guarantees accompany them. A unlike the rules that human drivers follow when driving.
detailed specification of the protocol including full syntax and se- 4.2.1 Vehicle Actions
mantics is available in our technical report [2]. In this section we
present those aspects that are essential to understanding the remain- These are the rules that the vehicles are expected to follow in
der of the paper. order to allow the intersection to function efficiently.

1. A vehicle may not enter the intersection without a reserva-

4.1 Message Types tion.
The vehicles and intersection manager are each restricted to a
few types of messages with which they must coordinate. 2. If a vehicle is going to cross the intersection, it must do ev-
erything reasonable within its power to cross in accordance
4.1.1 Vehicle → Intersection with the parameters included in the most recent C ONFIRMA -
There are four types of messages that can be sent from vehicles TION message it has received from the intersection.
to the intersection.
3. If a vehicle sends another message before the intersection
manager has sent a response, the intersection manager may
1. R EQUEST — This is the message a vehicle sends when it choose to ignore it. Thus, a vehicle should only send a mes-
does not have a reservation and wishes to make one. It con- sage if it has received a response to its previous message.
tains the properties of the vehicle (ID number, performance,
size, etc.) as well as some properties of the proposed reser- 4. If a vehicle has not yet entered the intersection and does not
vation (arrival time, arrival velocity, type of turn, arrival lane, have a reservation, it may send a R EQUEST message. If it has
etc.). not yet entered the intersection and does have a reservation, it
may send either a C HANGE -R EQUEST or C ANCEL message.
2. C HANGE -R EQUEST — This is the message a vehicle sends If it sends any of these messages when it is not allowed to,
when it has a reservation, but would like to switch to a dif- the intersection may choose to ignore them.
ferent set of parameters.
5. If a vehicle has a reservation and has successfully crossed
3. C ANCEL — This is the message a vehicle sends when it no the intersection, it may send a R ESERVATION -C OMPLETED
longer desires its current reservation. message.
6. If a vehicle receives a C ONFIRMATION message, it is consid-
4. R ESERVATION -C OMPLETED — This message is used when
ered to have a reservation.
the vehicle has completed its traversal of the intersection.
This message can be used to collect statistics for each ve- 4.2.2 Intersection Actions
hicle, which can be recorded in order to analyze and improve
These are the rules representing the obligations the intersection
the performace of the intersection manager.
manager is expected to fulfill.
4.1.2 Intersection → Vehicle 1. When an intersection receives a R EQUEST message, it must
There are three types of messages that can be sent from the in- respond with either a C ONFIRMATION or a R EJECTION mes-
tersection to the individual vehicles. sage. If it responds with a C ONFIRMATION message, it is
 guaranteeing that no cross-traffic will interfere with the ve- 6. NEW DRIVER AGENT
hicle if it crosses the intersection in accordance with the pa- The above protocol is designed to place minimal restrictions on
rameters in the message. vehicle control. As a result, there remains a lot of freedom in cre-
ating driver agents. Though our system does not depend on any
2. When an intersection receives a C HANGE -R EQUEST mes- specific driver agent implementation, we need at least one concrete
sage, it must respond with either a C ONFIRMATION or a R E - instantiation in order to test it empirically. In this section we dis-
JECTION message. If it responds with a C ONFIRMATION cuss our extensions to our driver agent [3].
message, it is guaranteeing that no cross-traffic will interfere Previously, once a driver agent made a successful reservation (at
with the vehicle if it crosses the intersection in accordance its current velocity), it was forced to maintain that velocity until it
with the parameters in the message. Any previous guaran- reached the intersection. This is a major weakness for the system.
tees are nullified. If vehicles ever made reservations at very low velocities, not only
did they consume a lot of valuable space-time in the intersection,
3. When an intersection receives a C ANCEL message, it must but they also slowed down traffic behind them the rest of the way
respond with an ACKNOWLEDGMENT message. Any guar- to the intersection. Repeated iterations of this scenario eventually
antee that had been made to the sending vehicle is nullified. contribute to deadlocking the system. In fact, the authors point out
that their system did deadlock under certain circumstances for this
very reason. The other part of this problem (that vehicles cannot
5. INTERSECTION CONTROL POLICIES accelerate while in the intersection) is addressed via the protocol
Using this protocol, we can express the control policies from our presented in Section 4.
prior work as well as a new one, the stop sign.
6.1 Optimism and Pessimism
5.1 Overpass Unlike our previous implementation of the driver agent, our new
The overpass accepts all R EQUEST and C HANGE -R EQUEST mes- agent does not calculate its reservation times using only its current
sages exactly as they are, sending corresponding C ONFIRMATION velocity. In the prior work, the driver agent always made requests
messages (with reasonably large error values). This is good for by calculating the time to get to the intersection at its current ve-
testing purposes, but implementing the overpass with this protocol locity, after which, it maintained that velocity until it was through
is only an academic exercise - there would be no reason for it in a the intersection. It does not matter how the vehicle reaches the
real system (in fact it would be quite dangerous). intersection, as long as the vehicle arrives as scheduled. The be-
havior as originally proposed can lead to serious problems when,
5.2 Reservation System for example, a vehicle makes a reservation while stuck behind a
slower-moving vehicle. If the vehicle in front eventually acceler-
message, the intersection simulates the journey of the vehicle ates, the other vehicle should be able to accelerate as well (possibly
with the supplied parameters. If the vehicle can make it through switching to an earlier reservation).
the intersection without using space-time reserved by another ve- To utilize this flexibility, we introduce the notion of an optimistic
hicle (or near another vehicle), the intersection generates a unique or pessimistic driver agent. An optimistic agent makes a reserva-
reservation ID, records the reservation, and sends a C ONFIRMA - tion assuming it will immediately get to accelerate to full speed. An
TION message to the vehicle. If the vehicle cannot make it, the
agent which no longer finds itself stuck behind a slower vehicle will
intersection responds with a R EJECTION message. become optimistic and attempt to make a new, earlier reservation.
On receiving a C HANGE -R EQUEST, the intersection again sim- A pessimistic agent assumes it will be stuck at its current velocity
ulates the journey of the vehicle with the revised parameters. If the until it reaches the intersection. If an agent has to cancel its reser-
vehicle can make it through, the intersection removes the old reser- vation because there is no way for it to arrive on time, it becomes
vation, generates a new ID, records the new reservation, and sends pessimistic. Due to the relatively infrequent and smooth transi-
a C ONFIRMATION message to the vehicle. If the vehicle cannot tions through these situations, our driver agent can take advantage
make it, the intersection responds with a R EJECTION message (and of improving circumstances without causing it to send excessive
the vehicle keeps its old reservation). numbers of C HANGE -R EQUEST messages when things change.
On receiving a C ANCEL or R ESERVATION -C OMPLETED mes-
sage, the reservation system deletes the reservation associated with 6.2 Cancellation and Communication Com-
the reservation ID in the message, and responds with an ACKNOWL - plexity
EDGMENT message.
Another change, very closely related to the previous section, is
an improvement in the communication complexity of the model.
5.3 Stop Sign In the initial model, the agent determined whether or not it could
The stop sign is exactly like the a reservation system, except honor a reservation assuming it kept its present velocity for the re-
that it only accepts reservations from vehicles that are stopped at mainder of the journey to the intersection. While this might keep
the intersection. Any other reservation requests are rejected with a things more up-to-date, it often caused a decelerating agent to make
message indicating the vehicle must stop at the intersection. and cancel new reservations in rapid succession until it stopped de-
celerating. In order to prevent this, the new agent only cancels a
5.4 Traffic Light reservation if there is absolutely no physical way it could reach the
When the traffic light receives a R EQUEST message, it examines intersection on time. If a person were a few minutes late in leaving
the arrival time in the message. It then calculates the next time after for the airport, that person would not immediately cancel his or her
this that the light for the direction, turn, and lane of the sending flight entirely. On the contrary, that person would hope to make
vehicle will be green and responds with a C ONFIRMATION message up lost time at some point before the flight left. Only when there
that reflects this information (including errors that correspond to the was no hope of making it to the jetway on time would the person
beginning and end of the green light). actually cancel the reservation.
 Reducing the communication complexity of the system is very
important for two reasons. First, if fewer total messages are sent,
the bandwidth required to send messages is lower; thus, given the
available bandwidth, messages are much less likely to be delayed
or lost — events which might negatively affect the system’s ef-
ficiency. Second, many of the messages (like the R EQUEST and
C HANGE -R EQUEST messages) directly result in intense computa-
tion by the intersection manager. Because the resources of the inter-
section manager are limited, it can only process these messages at
some fixed rate. In order to regulate the driver agents, we envision
that some sort of charge (perhaps a micropayment) will be levied
for each message. In this case, reducing the number of messages
sent will be a priority for driver agents.

7. EMPIRICAL RESULTS
In this section, we evaluate the performance of our improved
reservation system for varying amounts of traffic and varying per-
centages of turning vehicles. Additionally, we show results for the Figure 1: A screenshot of our simulator in action.
new stop sign control policy as implemented under our protocol.
We then compare these to results from an earlier paper regarding
standard traffic lights. Finally, we experiment with allowing vehi-
cles to turn from any lane — something that would be extremely turns, a traditional overpass does not make sense. However, we
dangerous without the reservation-based mechanism. would like an ideal-case solution in which cross-traffic does not
For each experiment, the simulator simulates 3 lanes in each of affect the time it takes a vehicle to complete its journey. Thus, al-
the 4 cardinal directions. The total area modelled is a square with though it does not represent a true overpass, we still refer to this
sides of 250 meters. The speed limit in all lanes is 25 meters per solution as “the overpass.” Vehicles are granted reservations at any
second. Figure 1 shows a screenshot of the graphical display. Each time and they can pass through one another, however vehicles turn-
time step in the simulator represents .02 seconds of real time. Dur- ing may have to slow down in order to make the turn.
ing each time step, a vehicle is spawned with the given probability, Although a lower bound on the trip time of a vehicle is 10 sec-
each driver is given sensor input and a decision-making phase, the onds, turning vehicles must slow to make the turn. Thus the average
positions of each vehicle are updated based on the decisions of the time for the overpass system as shown in Figure 2 is just above 10
driver, and finally any vehicles that have left the area of the simu- seconds.
lation are removed. Every configuration shown is run for 100,000
steps in the simulator, which corresponds to approximately half an 15
Stop Sign
hour. Vehicles that are spawned in any given direction turn both 14.5 Traffic Light Minimum
Reservation System
right and left with probability .05. Unless otherwise specified, ve- 14 Overpass

hicles turning right are spawned in the right lane, whereas vehicles 13.5
Total trip time (s)

turning left are spawned in the left lane. Vehicles that are not turn- 13
ing are distributed probabilistically amongst the lanes such that the 12.5
traffic in each lane is as equal as possible. The reservation sys- 12
tem in these simulations has a granularity of 24 and ensures that 11.5
no two vehicles occupy the same tile within half a second of each 11
other. Videos of the simulator running can be seen at http://
10.5
www.cs.utexas.edu/users/kdresner/2005aamas/.
10
Once turns are allowed, delay does not work very well as a met- 0 0.01 0.02 0.03 0.04 0.05
ric. There are many different paths through the intersection and Probability of spawning vehicle

amongst them are several different total distances. In addition, ve-

hicles that are turning must slow down before making their turns, Figure 2: Trip times for varying amounts of traffic for the reser-
so they may take longer than the minimum time to go through the vation system, the stop sign, and the optimal “overpass”.
intersection, even under optimal conditions. Because of this, we
have decided to simply measure the average time it takes a vehicle
to go from a fixed start point to a fixed destination point. We refer
to this time as the trip time. 7.2 The Reservation System
Note that in the previous work, the traffic light was shown to The reservation system performs very well, nearly matching the
have trip times of at least 5 seconds longer than optimal, even in performance of the overpass system. At higher levels of traffic, the
scenarios with extremely light traffic. The absolute shortest time to average trip time for a vehicle gets as high as 10.35 seconds, but is
go from start to finish in this scenario is 10 seconds, which means never more than 1 second above optimal. Under none of the tested
that the average trip time for the traffic light would be at least 15 conditions does the reservation system approach the trip times of
seconds. the traffic light system in our previous work.

7.1 The Overpass 7.3 The Stop Sign

In our last paper [3], we presented the overpass as the optimal Small intersections with slow-moving traffic tend not to be amenable
solution to the intersection control problem. With the addition of to control by traffic lights. Light traffic can usually regulate itself
fairly effectively. For example, consider an intersection with a stop Messages Reservations
sign - all vehicles must come to a stop, but afterwards may proceed Before 560.85 165.89
if the intersection is clear. In these situations, a stop sign is often After 5.97 1.02
much more efficient than a traffic light, because vehicles are never
stuck waiting for a light to change when there is no cross-traffic. Figure 4: For a moderate amount of traffic, the average num-
Because our new protocol enables us to define such a control pol- ber of messages sent and reservations made by driver agents
icy, we test how it compares to the other systems as well. Note that before and after the improvements described in Section 6.
this system is much more efficient than an actual stop sign, because
once the vehicle has stopped at the intersection, the driver agent and
intersection can determine when the car may safely proceed more
precisely than a human driver. As shown in Figure 2, the stop sign We have shown that our reservation system can be extended nat-
does not perform as well as the reservation system or the overpass, urally to incorporate turning and accelerating in the intersection.
but for low amounts of traffic, it still performs fairly well, with av- Furthermore, we have shown that the reservation system can out-
erage trip times only about 3 seconds greater than optimal. As the perform the stop sign, approaching optimal, at a wide range of traf-
traffic level increases, however, performance degrades. fic densities. Our communication protocol, which allows the sys-
tem to subsume both the stop sign and the traffic light, solves some
7.4 Allowing Turns from Any Lane major concerns posed as detailed in our previous work [3].
In traditional traffic systems, especially those with traffic lights, One of these concerns was allowing the system to work with hu-
vehicles wishing to turn onto the cross street must do so from spe- man drivers, pedestrians, or cyclists. One can imagine a system
cially designated turning lanes. This helps prevent cars that want to that shifts to a traffic-light-like control policy (with physical lights)
turn from holding up non-turning traffic. However, with a system when it detects vehicles or pedestrians that cannot participate in
like the reservation system, this restriction is no longer necessary. the reservation system. These individuals could then interact with
There is nothing inherent in the reservation system that demands the intersection the way they do currently. Once the traffic con-
vehicles turn from any specific lane, and thus we investigated these sisted only of participating vehicles, the intersection manager could
effects3 . As seen in Figure 3, relaxing this restriction in fact wors- switch back to a more efficient reservation-based policy.
ens performance. While one might think this allows the vehicles
more flexibility, it on average increases the resources used by any 8.1 Future Work
one turning vehicle. By making left turns from the left lane and There are still many challenges and interesting questions to be
right turns from the right lane, vehicles both travel a shorter dis- answered in this domain. For example, we investigated the effects
tance and use reservation tiles that are less heavily used. of allowing the vehicle to turn from any lane, but we did not in-
vestigate what happens when vehicles are allowed to turn into any
11
Fixed Lane
lane. Furthermore, with the creation of a communication protocol,
Any Lane we can create more interesting driver agents and intersection man-
10.8 agers. Both could involve machine learning. The inherent multi-
agent nature of the domain makes it a good testbed for multi-agent
Total trip time (s)

10.6 learning research. The agents can be heterogenous, and the differ-
ent types of agents (intersection managers and drivers) have differ-
10.4
ent, but not necessarily opposing, goals.
We also see a large opportunity for more research in designing
more intelligent reservation systems and driver agents. Currently
10.2
both of these use heuristics to find available reservations and reser-
vation times, respectively. Applying machine learning techniques
10
0 0.01 0.02 0.03 0.04 0.05 to these issues could increase the efficiency of the system even fur-
Probability of spawning vehicle ther.

Figure 3: Comparison of the normal reservation system with 8.2 Related Work
turns to one allowing turning from any lane. Rasche and Naumann have worked extensively on decentralized
solutions to intersection collision avoidance problems [8, 10]. Many
approaches focus on improving current technology (systems of traf-
fic lights). For example, Roozemond allows intersections to act au-
7.5 Changes to the Driver Agent tonomously, sharing the data they gather [14]. The intersections
As shown in Figure 4, the improvements to the driver agent dras- then use this information to make both short- and long-term pre-
tically reduced both the average number of reservations made as dictions about the traffic and adjust accordingly. This approach
well as the average number of messages transmitted. These data still assumes human-controlled vehicles. Bazzan has used an ap-
were collected using the same simulator settings as the rest of this proach using both MAS and evolutionary game theory which in-
section, but with a vehicle spawning probability of .02 (approxi- volves multiple intersection managers (agents) that must focus not
mately 2000 vehicles). For lower amounts of traffic, the effect was only on local goals, but also on global goals [1].
less pronounced. Work is also being done with regard to the control of the individ-
ual vehicles. Hallé and Chaib-draa have taken a MAS approach to
8. DISCUSSION AND RELATED WORK collaborative driving by allowing vehicles to form platoons, groups
of varying degrees of autonomy, that then coordinate using a hier-
3 archical driving agent architecture [4]. While not focusing on in-
Videos of this can be seen at http://www.cs.utexas.
edu/users/kdresner/2005aamas/. tersections, Moriarty and Langley have shown that reinforcement
learning can train efficient driver agents for lane, speed, and route [10] R. Rasche, R. Naumann, J. Tacken, and C. Tahedl. Validation and
selection during freeway driving [7]. simulation of decentralized intersection collision avoidance
On real autonomous vehicles, Kolodko and Vlacic have created algorithm. In Proceedings of IEEE Conference on Intelligent
Transportation Systems (ITSC 97), 1997.
a primitive system for intersection control which is very similar to
[11] C. W. Reynolds. Steering behaviors for autonomous characters. In
the granularity-1 reservation system [6]. Proceedings of the Game Developers Conference, pages 763–782,
Actual systems in practice (not MAS) for traffic light optimiza- 1999.
tion include TRANSYT [12], which is an off-line system requiring [12] D. I. Robertson. TRANSYT — a traffic network study tool.
extensive data gathering and analysis, and SCOOT [5], which is Technical Report TRRL-LR-253, Transport and Road Research
an advancement over TRANSYT, responding to changes in traffic Laboratory, 1969.
loads on-line. However, almost all of the methods in practice or [13] S. Rogers, C.-N. Flechter, and P. Langley. An adaptive interactive
discussed above still rely on traditional signalling systems. agent for route advice. In O. Etzioni, J. P. Müller, and J. M.
Bradshaw, editors, Proceedings of the Third International
Conference on Autonomous Agents (Agents’99), pages 198–205,
9. CONCLUSION Seattle, WA, USA, 1999. ACM Press.
This paper makes four main contributions. First, it augments a [14] D. A. Roozemond. Using intelligent agents for urban traffic control
control systems. In Proceedings of the International Conference on
proposed intersection control mechanism to allow for more flexible Artificial Intelligence in Transportation Systems and Science, pages
vehicle control, including turning and accelerating while in the in- 69–79, 1999.
tersection. Second, it introduces a detailed protocol by which vehi- [15] T. Schonberg, M. Ojala, J. Suomela, A. Torpo, and A. Halme.
cles and intersection managers can effectively and efficiently com- Positioning an autonomous off-road vehicle by using fused DGPS
municate and coordinate their actions. Third, it describes a driver and inertial navigation. In 2nd IFAC Conference on Intelligent
agent that makes good use of this protocol. Finally, it demonstrates Autonomous Vehicles, pages 226–231, 1995.
how this augmented system, using the protocol, can still drastically [16] P. Stone and M. Veloso. Multiagent systems: A survey from a
machine learning perspective. Autonomous Robots, 8(3):345–383,
outperform both the traffic light and the stop sign. July 2000.
The mechanism is currently limited by the use of straightforward [17] Texas Transportation Institute. 2004 urban mobility report,
heuristics to calculate reservation parameters, both on the part of September 2004. Accessed at
the intersection manager and the driver agents. However, this lim- http://mobility.tamu.edu/ums in December 2004.
itation is a focus of our ongoing research. Once autonomous vehi-
cles become common, this mechanism may be useful for control-
ling real traffic.

Acknowledgments
This research is supported in part by NSF CAREER award IIS-0237699.

10. REFERENCES
[1] A. L. C. Bazzan. A distributed approach for coordination of traffic
signal agents. Autonomous Agents and Multi-Agent Systems,
10(2):131–164, March 2005.
[2] K. Dresner and P. Stone. Multiagent traffic management: A protocol
for defining intersection control policies. Technical Report
UT-AI-TR-04-315, The University of Texas at Austin, Department of
Computer Sciences, AI Laboratory, December 2004.
[3] K. Dresner and P. Stone. Multiagent traffic management: A
reservation-based intersection control mechanism. In The Third
International Joint Conference on Autonomous Agents and
Multiagent Systems, pages 530–537, New York, New York, USA,
July 2004.
[4] S. Hallé and B. Chaib-draa. A collaborative driving system based on
multiagent modelling and simulations. Journal of Transportation
Research Part C (TRC-C): Emergent Technologies, 13:320–345,
2005.
[5] P. B. Hunt, D. I. Robertson, R. D. Bretherton, and R. I. Winton.
SCOOT - a traffic responsive method of co-ordinating signals.
Technical Report TRRL-LR-1014, Transport and Road Research
Laboratory, 1981.
[6] J. Kolodko and L. Vlacic. Cooperative autonomous driving at the
intelligent control systems laboratory. IEEE Intelligent Systems,
18(4):8–11, July/August 2003.
[7] D. Moriarty and P. Langley. Learning cooperative lane selection
strategies for highways. In Proceedings of the Fifeenth National
Conference on Artificial Intelligence, pages 684–691, Madison, WI,
1998. AAAI Press.
[8] R. Naumann and R. Rasche. Intersection collision avoidance by
means of decentralized security and communication management of
autonomous vehicles. In Proceedings of the 30th ISATA - ATT/IST
Conference, 1997.
[9] D. A. Pomerleau. Neural Network Perception for Mobile Robot
Guidance. Kluwer Academic Publishers, 1993.