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,TX78712USA

{kdresner,pstone}@cs.utexas.edu

ABSTRACT

Traffic congestion is one of the leading causes of lost productivity and decreased standard of living in urban settings.Recent advances in artificial intelligence suggest vehicle navigation by autonomous agents will be possible in the near future.In a previous paper,we proposed a reservation-based system for alleviating traffic conges-tion,specifically at intersections.This paper extends our prototype implementation in several ways with the aim of making it more implementable in the real world.In particular,we1)add the abil-ity of vehicles to turn,2)enable them to accelerate while in the intersection,and3)augment their interaction capabilities with a detailed protocol such that the vehicles do not need to know any-thing about the intersection control policy.The use of this protocol limits the interaction of the driver agent and the intersection man-ager to the extent that it is a reasonable approximation of reliable wireless communication.Finally,we describe how different in-tersection control policies can be expressed with this protocol and limited exchange of information.All three improvements are fully implemented and tested,and we present detailed empirical results validating their effectiveness.

1.INTRODUCTION

Traffic congestion is one of the leading causes of lost productiv-ity and decreased standard of living in urban settings.According to a recent study of85U.S.cities[17],annual time spent waiting in traffic has increased from16hours per capita to46hours per capita since1982.In the same period,the annualfinancial cost of traffic congestion has swollen from$14billion to more than $63billion(in2002US dollars).Each year,Americans burn ap-proximately5.6billion gallons of fuel while idling in heavy traffic. Recent advances in artificial intelligence suggest that autonomous vehicle navigation will be possible in the near future.Individual cars can now be equipped with features of autonomy such as cruise control,GPS-based route planning[13,15],and autonomous steer-ing[9,11].Once individual cars become autonomous,many of the cars on the road will have such capabilities,thus opening up the possibility of autonomous interactions among multiple vehicles. Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on thefirst page.To copy otherwise,to republish,to post on servers or to redistribute to lists,requires prior specific permission and/or a fee.

AAMAS’05,July25-29,2005,Utrecht,Netherlands.

Copyright2005ACM1-59593-094-9/05/0007...$5.00.

Multiagent Systems(MAS)is the subfield of AI that aims to pro-vide both principles for construction of complex systems involving multiple agents and mechanisms for coordination of independent agents’behaviors[16].In an earlier paper,we proposed an MAS-based approach to alleviating traffic congestion,specifically at in-tersections[3].In this paper,we describe several ways in which we have transformed that system into a more realistic and imple-mentable system.

Current methods for enabling traffic toflow through intersections include building overpasses and installing traffic lights.However, the former is very expensive and forbids turning,while the latter can be quite inefficient,often requiring cars to remain stopped even when no cars are present on the intersecting road.

At this time,it is possible to create a small-scale system in which all cars are piloted by a central computer.Consider,for example, the task of controlling ten vehicles on an open factoryfloor.How-ever,growing such a system to handle an intersection in which a city’s worth of cars might turn up would involve prohibitively ex-pensive and inefficient communication and control infrastructure. 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-cation system and a protocol(which we introduce here)for com-municating with oncoming traffic and giving permission for cars to pass.

In our system,vehicles must traverse intersections according to

a set of parameters agreed upon by the vehicle and the intersection manager(as they do today by obeying red and green lights),but otherwise are free to decide for themselves how to drive.Each car is an autonomous agent,and in particular need not surrender control to any centralized decision maker.

Given the above assumptions,we have proposed a novel reservation-based system by which cars request and receive time slots from the intersection during which they may pass[3].While this system showed the potential for a reservation-based system to drastically improve the efficiency of intersections,it required driving agents to maintain a constant velocity in the intersection and forbade turning (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 acceleration in the intersection possible,which allows us to sub-sume the stop sign policy within the reservation framework.Third, we specify a protocol to govern the interactions of the vehicles and the intersection such that the vehicles do not need to know anything about the intersection control policy.The use of this protocol limits the interaction of the driver agent and the intersection manager tothe extent that it is a reasonable approximation of reliable wireless communication.Using this protocol,we detail how many every-day intersection control policies,such as the traffic light and the stop sign can be encoded.

2.THE ORIGINAL SYSTEM

Previously,we proposed a novel reservation-based multi-agent approach to alleviating traffic,specifically at intersections.This system consisted of two types of agents:intersection managers and driver agents.Each system consists of an intersection manager for each intersection and a driver agent for each vehicle.Intersection managers are responsible for directing the vehicles through the in-tersection,while the driver agents are responsible for controlling the vehicles to which they are assigned.To improve the throughput and efficiency of the system,the driver agents“call ahead”to the in-tersection manager and request space-time in the intersection.The intersection manager then determines whether or not these requests can be met.Depending on the decision the intersection manager makes,the driver agent either records the parameters of the request (the reservation)and attempts to meet them,or it makes another request at a later time.

To determine whether or not a request can be met,the reserva-tion manager simulates the journey of the vehicle across the inter-section,which it divides into a grid of n×n tiles.The parameter n is called the granularity of the reservation manager.At each time step of the simulation,it determines which tiles the vehicle occu-pies.If throughout this simulation,no required tile is occupied by another vehicle(from a previous reservation),the manager reserves the tiles for this vehicle.

After creating a custom simulator,we evaluated the performance of the reservation system against two other intersection control policies-the overpass and the traffic light.An intersection con-trol policy is a method the intersection managers use to determine when specific vehicles are allowed in the intersection.Using the simulator,we showed that using the reservation-based policy,ve-hicles crossing an intersection experience much lower delay(in-crease in travel time from the optimal)versus the traffic light.Fur-thermore,we showed that the reservation-based policy drastically increases the throughput of the intersection.For any realistic inter-section control policy,there exists an amount of traffic above which vehicles arrive at the intersection more frequently than they can go through the intersection.At this point,the average delay experi-enced by vehicles travelling through the intersection grows without bound.They demonstrated that compared to the traffic light,this amount of traffic is much higher for the reservation system.In ad-dition to our simulator applets1Garcia and Vidal have implemented applets reproducing the results2.

3.IMPROVING THE ORIGINAL MODEL The results described in the previous section are very encourag-ing.In this section,we offer several ways to improve the system with regard toflexibility,efficiency,and making it implementable in the real world.

3.1Desirable Properties

In order for the reservation-based mechanism to be both realis-tic and practical,we believe that the following properties ought to hold.

1http://www.cs.utexas.edu/users/kdresner/ 2004aamas

2http://jmvidal.cse.sc.edu/netlogomas/ TrafficManagementMendoza.html

1.The agents should only communicate information which is

necessary for the system to function properly.

2.The agents should only have access to information that can

be reliably obtained with current technology.

3.Communication failure(dropped messages)should not vio-

late the system’s safety properties.

4.The vehicles should be treated as individual agents,and no

centralized controller should have any more control over them

than necessary.

5.The system should incorporate a simple communication pro-

tocol that allows agents to know only a minimal amount about

each other.As long as agents obey and understand the proto-

col,no extra information exchange or other interaction should

be required.

6.Every vehicle should eventually make it through the intersec-

tion(i.e.no deadlocks or starvation).

3.2Acceleration in the Intersection

Our previous implementation of the reservation system made reservations for vehicles only at a constant velocity.This prop-erty is partly responsible(along with others discussed in Section6) for the deadlocks their system experienced.With this restriction,if

a vehicle made a reservation at a low velocity,it would consume a large amount of space-time in the intersection.This,in turn,would cause other vehicles to be delayed making their reservations(which would also be at low velocities).These slow-downs often led to permanent deadlocks.By allowing acceleration in the intersection, our system always eventually recovers from slowdowns caused by heavy traffic.

Because the reservation manager can now return reservations with accelerations,the problem becomes determining what those accelerations should be.By varying its accelerations just right,a vehicle may be able tofit through a small opening in the intersec-tion.Somehow,the intersection manager must choose the correct accelerations.We chose to use a very simple heuristic:the intersec-tion managerfirst tries to have the entering vehicle accelerate to the maximum allowed velocity.If such a reservation is not possible,it attempts to make a constant-velocity reservation.If the constant-velocity reservation also fails,the request is rejected.Using ac-celeration in the intersection,along with the protocol presented in Section4,allows us to implement the stop sign policy within this reservation framework.

3.3Excess Information

Our previous work relied on the assumption that vehicles knew each others’positions and reservation statuses at all times.How-ever,it is not immediately obvious how any vehicle would get this information in the real world.While exact position information would be hard to come by,there is no reason to believe that ve-hicles would have any access at all to the internal state of other vehicles around it(even ones in close proximity).An older model vehicle interacting with a new model vehicle can not be expected

to understand the newer model’s inner workings.Additionally,the manufacturer of the driver agent may not want other vehicles to know what goes on“under the hood.”

3.4Unspecified Communication Between Driver

Agents and Intersection Managers

Our previous paper[3]specified which agents govern which as-pects of their system,but they do not specify exactly how the agentscoordinate their efforts.Additionally,in their work,any driver agent would have to understand what kind of intersection control policy the intersection manager was using in order to interact with it.To address these issues,we created a detailed communication protocol to govern and restrict the interactions of driver agents and intersection managers.

This protocol solved three problems at once.First,all infor-mation between the agents goes through one monitorable channel, which makes it much easier to reason about.Second,by limiting the interactions of the agents to a few message types,we can en-sure that no agent has an unrealistic amount of control over another. Third,the agents now have a way to communicate that is identical for any intersection management policy or driver agent policy.A vehicle can cross an intersection using a traffic light without know-ing it is a traffic light.The traffic light speaks the same language as a stop sign and a reservation system.The driver agent thus must have a behavior that works with all sorts of intersection control policies—that is,the driver agent must view the intersection as a black box,and vice versa.

4.PROTOCOL

We have created a protocol by which the agents can communi-cate the bare minimum of information necessary to function appro-priately.The protocol consists of several message types for each kind of agent,as well as some rules governing when the messages should be sent and what sorts of guarantees accompany them.A detailed specification of the protocol including full syntax and se-mantics is available in our technical report[2].In this section we present those aspects that are essential to understanding the remain-der of the paper.

4.1Message Types

The vehicles and intersection manager are each restricted to a few types of messages with which they must coordinate.

4.1.1Vehicle→Intersection

There are four types of messages that can be sent from vehicles to the intersection.

1.R EQUEST—This is the message a vehicle sends when it

does not have a reservation and wishes to make one.It con-tains the properties of the vehicle(ID number,performance, size,etc.)as well as some properties of the proposed reser-vation(arrival time,arrival velocity,type of turn,arrival lane, etc.).

2.C HANGE-R EQUEST—This is the message a vehicle sends

when it has a reservation,but would like to switch to a dif-ferent set of parameters.

3.C ANCEL—This is the message a vehicle sends when it no

longer desires its current reservation.

4.R ESERVATION-C OMPLETED—This message is used when

the vehicle has completed its traversal of the intersection.

This message can be used to collect statistics for each ve-hicle,which can be recorded in order to analyze and improve the performace of the intersection manager.

4.1.2Intersection→Vehicle

There are three types of messages that can be sent from the in-tersection to the individual vehicles.

1.C ONFIRMATION—This message is a response to a vehicle’s

R EQUEST(or C HANGE-R EQUEST)message.It can contain

a counter-offer by the intersection.The reservation param-

eters in this message are implicitly accepted by the vehicle, and must be explicitly cancelled if the driver agent of the ve-hicle does not approve.Note that this is safe to faulty com-munication—the worst that can happen is that the intersec-tion reserves space that does not get used.

2.R EJECTION—By sending this message,an intersection can

inform a vehicle that the parameters sent in the latest R E-QUEST(or C HANGE-R EQUEST)were not acceptable,and that the intersection either could not or did not want to make

a counter-offer.This message also contains afield indicat-

ing whether or not the rejection was because the reservation manager requires the vehicle to stop at the intersection be-fore entering.This lets the driver agent know that it should not attempt any more reservations until it reaches the inter-section.

3.A CKNOWLEDGMENT—This message acknowledges the re-

ceipt of a C ANCEL or R ESERVATION-C OMPLETED message.

4.2Protocol Actions

In addition to message types,the agents involved(the vehicles and the intersection)must obey a set of rules.These are not entirely unlike the rules that human drivers follow when driving.

4.2.1Vehicle Actions

These are the rules that the vehicles are expected to follow in order to allow the intersection to function efficiently.

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

tion.

2.If a vehicle is going to cross the intersection,it must do ev-

erything reasonable within its power to cross in accordance with the parameters included in the most recent C ONFIRMA-TION message it has received from the intersection.

3.If a vehicle sends another message before the intersection

manager has sent a response,the intersection manager may choose to ignore it.Thus,a vehicle should only send a mes-sage if it has received a response to its previous message.

4.If a vehicle has not yet entered the intersection and does not

have a reservation,it may send a R EQUEST message.If it has not yet entered the intersection and does have a reservation,it may send either a C HANGE-R EQUEST or C ANCEL message.

If it sends any of these messages when it is not allowed to, the intersection may choose to ignore them.

5.If a vehicle has a reservation and has successfully crossed

the intersection,it may send a R ESERVATION-C OMPLETED message.

6.If a vehicle receives a C ONFIRMATION message,it is consid-

ered to have a reservation.

4.2.2Intersection Actions

These are the rules representing the obligations the intersection manager is expected to fulfill.

1.When an intersection receives a R EQUEST message,it must

respond with either a C ONFIRMATION or a R EJECTION mes-sage.If it responds with a C ONFIRMATION message,it isguaranteeing that no cross-traffic will interfere with the ve-

hicle if it crosses the intersection in accordance with the pa-

rameters in the message.

2.When an intersection receives a C HANGE-R EQUEST mes-

sage,it must respond with either a C ONFIRMATION or a R E-

JECTION message.If it responds with a C ONFIRMATION

message,it is guaranteeing that no cross-traffic will interfere

with the vehicle if it crosses the intersection in accordance

with the parameters in the message.Any previous guaran-

tees are nullified.

3.When an intersection receives a C ANCEL message,it must

respond with an A CKNOWLEDGMENT message.Any guar-

antee that had been made to the sending vehicle is nullified.

5.INTERSECTION CONTROL POLICIES Using this protocol,we can express the control policies from our prior work as well as a new one,the stop sign.

5.1Overpass

The overpass accepts all R EQUEST and C HANGE-R EQUEST mes-sages exactly as they are,sending corresponding C ONFIRMATION messages(with reasonably large error values).This is good for testing purposes,but implementing the overpass with this protocol is only an academic exercise-there would be no reason for it in a real system(in fact it would be quite dangerous).

5.2Reservation System

message,the intersection simulates the journey of the vehicle with the supplied parameters.If the vehicle can make it through the intersection without using space-time reserved by another ve-hicle(or near another vehicle),the intersection generates a unique reservation ID,records the reservation,and sends a C ONFIRMA-TION message to the vehicle.If the vehicle cannot make it,the intersection responds with a R EJECTION message.

On receiving a C HANGE-R EQUEST,the intersection again sim-ulates the journey of the vehicle with the revised parameters.If the vehicle can make it through,the intersection removes the old reser-vation,generates a new ID,records the new reservation,and sends a C ONFIRMATION message to the vehicle.If the vehicle cannot make it,the intersection responds with a R EJECTION message(and the vehicle keeps its old reservation).

On receiving a C ANCEL or R ESERVATION-C OMPLETED mes-sage,the reservation system deletes the reservation associated with the reservation ID in the message,and responds with an A CKNOWL-EDGMENT message.

5.3Stop Sign

The stop sign is exactly like the a reservation system,except that it only accepts reservations from vehicles that are stopped at the intersection.Any other reservation requests are rejected with a message indicating the vehicle must stop at the intersection.

5.4Traffic Light

When the traffic light receives a R EQUEST message,it examines the arrival time in the message.It then calculates the next time after this that the light for the direction,turn,and lane of the sending vehicle will be green and responds with a C ONFIRMATION message that reflects this information(including errors that correspond to the beginning and end of the green light).6.NEW DRIVER AGENT

The above protocol is designed to place minimal restrictions on vehicle control.As a result,there remains a lot of freedom in cre-ating driver agents.Though our system does not depend on any specific driver agent implementation,we need at least one concrete instantiation in order to test it empirically.In this section we dis-cuss our extensions to our driver agent[3].

Previously,once a driver agent made a successful reservation(at its current velocity),it was forced to maintain that velocity until it reached the intersection.This is a major weakness for the system. If vehicles ever made reservations at very low velocities,not only did they consume a lot of valuable space-time in the intersection, but they also slowed down traffic behind them the rest of the way to the intersection.Repeated iterations of this scenario eventually 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 accelerate while in the intersection)is addressed via the protocol presented in Section4.

6.1Optimism and Pessimism

Unlike our previous implementation of the driver agent,our new agent does not calculate its reservation times using only its current velocity.In the prior work,the driver agent always made requests by calculating the time to get to the intersection at its current ve-locity,after which,it maintained that velocity until it was through the intersection.It does not matter how the vehicle reaches the intersection,as long as the vehicle arrives as scheduled.The be-havior as originally proposed can lead to serious problems when, for example,a vehicle makes a reservation while stuck behind a slower-moving vehicle.If the vehicle in front eventually acceler-ates,the other vehicle should be able to accelerate as well(possibly switching to an earlier reservation).

To utilize thisflexibility,we introduce the notion of an optimistic or pessimistic driver agent.An optimistic agent makes a reserva-tion assuming it will immediately get to accelerate to full speed.An agent which no longerfinds itself stuck behind a slower vehicle will become optimistic and attempt to make a new,earlier reservation.

A pessimistic agent assumes it will be stuck at its current velocity until it reaches the intersection.If an agent has to cancel its reser-vation because there is no way for it to arrive on time,it becomes pessimistic.Due to the relatively infrequent and smooth transi-tions through these situations,our driver agent can take advantage of improving circumstances without causing it to send excessive numbers of C HANGE-R EQUEST messages when things change. 6.2Cancellation and Communication Com-

plexity

Another change,very closely related to the previous section,is an improvement in the communication complexity of the model. In the initial model,the agent determined whether or not it could honor a reservation assuming it kept its present velocity for the re-mainder of the journey to the intersection.While this might keep things more up-to-date,it often caused a decelerating agent to make and cancel new reservations in rapid succession until it stopped de-celerating.In order to prevent this,the new agent only cancels a reservation if there is absolutely no physical way it could reach the intersection on time.If a person were a few minutes late in leaving for the airport,that person would not immediately cancel his or her flight entirely.On the contrary,that person would hope to make up lost time at some point before theflight left.Only when there was no hope of making it to the jetway on time would the person 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 somefixed 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 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 dangerous without the reservation-based mechanism.

For each experiment,the simulator simulates3lanes in each of the4cardinal directions.The total area modelled is a square with sides of250meters.The speed limit in all lanes is25meters per second.Figure1shows a screenshot of the graphical display.Each time step in the simulator represents.02seconds of real time.Dur-ing each time step,a vehicle is spawned with the given probability, each driver is given sensor input and a decision-making phase,the positions of each vehicle are updated based on the decisions of the driver,andfinally any vehicles that have left the area of the simu-lation are removed.Every configuration shown is run for100,000 steps in the simulator,which corresponds to approximately half an hour.Vehicles that are spawned in any given direction turn both right and left with probability.05.Unless otherwise specified,ve-hicles turning right are spawned in the right lane,whereas vehicles turning left are spawned in the left lane.Vehicles that are not turn-ing are distributed probabilistically amongst the lanes such that the traffic in each lane is as equal as possible.The reservation sys-tem in these simulations has a granularity of24and ensures that no two vehicles occupy the same tile within half a second of each other.Videos of the simulator running can be seen at http:// www.cs.utexas.edu/users/kdresner/2005aamas/. Once turns are allowed,delay does not work very well as a met-ric.There are many different paths through the intersection and amongst them are several different total distances.In addition,ve-hicles that are turning must slow down before making their turns, so they may take longer than the minimum time to go through the intersection,even under optimal conditions.Because of this,we have decided to simply measure the average time it takes a vehicle to go from afixed start point to afixed destination point.We refer to this time as the trip time.

Note that in the previous work,the traffic light was shown to have trip times of at least5seconds longer than optimal,even in scenarios with extremely light traffic.The absolute shortest time to go from start tofinish in this scenario is10seconds,which means that the average trip time for the traffic light would be at least15 seconds.

7.1The Overpass

In our last paper[3],we presented the overpass as the optimal solution to the intersection control problem.With the addition

of

Figure1:A screenshot of our simulator in action.

turns,a traditional overpass does not make sense.However,we would like an ideal-case solution in which cross-traffic does not affect the time it takes a vehicle to complete its journey.Thus,al-though it does not represent a true overpass,we still refer to this solution as“the overpass.”Vehicles are granted reservations at any time and they can pass through one another,however vehicles turn-ing may have to slow down in order to make the turn.

Although a lower bound on the trip time of a vehicle is10sec-onds,turning vehicles must slow to make the turn.Thus the average time for the overpass system as shown in Figure2is just above10 seconds.

10

10.5

11

11.5

12

12.5

13

13.5

14

14.5

15

0 0.01 0.02 0.03 0.04 0.05

T

o

t

a

l

t

r

i

p

t

i

m

e

(

s

)

Probability of spawning vehicle

Stop Sign

Traffic Light Minimum

Reservation System

Overpass

Figure2:Trip times for varying amounts of traffic for the reser-vation system,the stop sign,and the optimal“overpass”.

7.2The Reservation System

The reservation system performs very well,nearly matching the performance of the overpass system.At higher levels of traffic,the average trip time for a vehicle gets as high as10.35seconds,but is never more than1second above optimal.Under none of the tested conditions does the reservation system approach the trip times of the traffic light system in our previous work.

7.3The Stop Sign

Small intersections with slow-moving traffic tend not to be amenable to control by traffic lights.Light traffic can usually regulate itself

fairly effectively.For example,consider an intersection with a stop sign -all vehicles must come to a stop,but afterwards may proceed if the intersection is clear.In these situations,a stop sign is often much more efficient than a traffic light,because vehicles are never stuck waiting for a light to change when there is no cross-traffic.Because our new protocol enables us to define such a control pol-icy,we test how it compares to the other systems as well.Note that 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 does not perform as well as the reservation system or the overpass,but for low amounts of traffic,it still performs fairly well,with av-erage trip times only about 3seconds greater than optimal.As the traffic level increases,however,performance degrades.

7.4Allowing Turns from Any Lane

In traditional traffic systems,especially those with traffic lights,vehicles wishing to turn onto the cross street must do so from spe-cially designated turning lanes.This helps prevent cars that want to turn from holding up non-turning traffic.However,with a system like the reservation system,this restriction is no longer necessary.There is nothing inherent in the reservation system that demands vehicles turn from any specific lane,and thus we investigated these effects 3.As seen in Figure 3,relaxing this restriction in fact wors-ens performance.While one might think this allows the vehicles more flexibility,it on average increases the resources used by any one turning vehicle.By making left turns from the left lane and right turns from the right lane,vehicles both travel a shorter dis-tance and use reservation tiles that are less heavily used.

10

10.2

10.4

10.6

10.8 11

0 0.01

0.02 0.03 0.04 0.05

T o t a l t r i p t i m e (s )

Probability of spawning vehicle

Fixed Lane Any Lane

Figure 3:Comparison of the normal reservation system with turns to one allowing turning from any lane.

7.5Changes to the Driver Agent

As shown in Figure 4,the improvements to the driver agent dras-tically reduced both the average number of reservations made as well as the average number of messages transmitted.These data were collected using the same simulator settings as the rest of this section,but with a vehicle spawning probability of .02(approxi-mately 2000vehicles).For lower amounts of traffic,the effect was less pronounced.

8.DISCUSSION AND RELATED WORK

3

Videos of this can be seen at http://www.cs.utexas.edu/users/kdresner/2005aamas/.

Messages Reservations Before 560.85165.After

5.97 1.02

Figure 4:For a moderate amount of traffic,the average num-ber of messages sent and reservations made by driver agents before and after the improvements described in Section 6.

We have shown that our reservation system can be extended nat-urally to incorporate turning and accelerating in the intersection.Furthermore,we have shown that the reservation system can out-perform the stop sign,approaching optimal,at a wide range of traf-fic densities.Our communication protocol,which allows the sys-tem to subsume both the stop sign and the traffic light,solves some major concerns posed as detailed in our previous work [3].

One of these concerns was allowing the system to work with hu-man drivers,pedestrians,or cyclists.One can imagine a system that shifts to a traffic-light-like control policy (with physical lights)when it detects vehicles or pedestrians that cannot participate in the reservation system.These individuals could then interact with the intersection the way they do currently.Once the traffic con-sisted only of participating vehicles,the intersection manager could switch back to a more efficient reservation-based policy.

8.1Future Work

There are still many challenges and interesting questions to be answered in this domain.For example,we investigated the effects 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 lane.Furthermore,with the creation of a communication protocol,we can create more interesting driver agents and intersection man-agers.Both could involve machine learning.The inherent multi-agent nature of the domain makes it a good testbed for multi-agent learning research.The agents can be heterogenous,and the differ-ent types of agents (intersection managers and drivers)have differ-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 both of these use heuristics to find available reservations and reser-vation times,respectively.Applying machine learning techniques to these issues could increase the efficiency of the system even fur-ther.

8.2Related Work

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-tonomously,sharing the data they gather [14].The intersections then use this information to make both short-and long-term pre-dictions about the traffic and adjust accordingly.This approach still assumes human-controlled vehicles.Bazzan has used an ap-proach using both MAS and evolutionary game theory which in-volves multiple intersection managers (agents)that must focus not only on local goals,but also on global goals [1].

Work is also being done with regard to the control of the individ-ual vehicles.Hall´e and Chaib-draa have taken a MAS approach to collaborative driving by allowing vehicles to form platoons ,groups of varying degrees of autonomy,that then coordinate using a hier-archical driving agent architecture [4].While not focusing on in-tersections,Moriarty and Langley have shown that reinforcement

learning can train efficient driver agents for lane,speed,and route selection during freeway driving[7].

On real autonomous vehicles,Kolodko and Vlacic have created a primitive system for intersection control which is very similar to the granularity-1reservation system[6].

Actual systems in practice(not MAS)for traffic light optimiza-tion include TRANSYT[12],which is an off-line system requiring extensive data gathering and analysis,and SCOOT[5],which is an advancement over TRANSYT,responding to changes in traffic loads on-line.However,almost all of the methods in practice or discussed above still rely on traditional signalling systems.

9.CONCLUSION

This paper makes four main contributions.First,it augments a proposed intersection control mechanism to allow for moreflexible vehicle control,including turning and accelerating while in the in-tersection.Second,it introduces a detailed protocol by which vehi-cles and intersection managers can effectively and efficiently com-municate and coordinate their actions.Third,it describes a driver agent that makes good use of this protocol.Finally,it demonstrates how this augmented system,using the protocol,can still drastically outperform both the traffic light and the stop sign.

The mechanism is currently limited by the use of straightforward heuristics to calculate reservation parameters,both on the part of the intersection manager and the driver agents.However,this lim-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–1,March2005.

[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,December2004.

[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,pages530–537,New York,New York,USA,

July2004.

[4]S.Hall´e 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/August2003.

[7] D.Moriarty and P.Langley.Learning cooperative lane selection

strategies for highways.In Proceedings of the Fifeenth National

Conference on Artificial Intelligence,pages684–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 the30th ISATA-ATT/IST

Conference,1997.

[9] D.A.Pomerleau.Neural Network Perception for Mobile Robot

Guidance.Kluwer Academic Publishers,1993.[10]R.Rasche,R.Naumann,J.Tacken,and C.Tahedl.Validation and

simulation of decentralized intersection collision avoidance

algorithm.In Proceedings of IEEE Conference on Intelligent

Transportation Systems(ITSC97),1997.

[11] C.W.Reynolds.Steering behaviors for autonomous characters.In

Proceedings of the Game Developers Conference,pages763–782, 1999.

[12] D.I.Robertson.TRANSYT—a traffic network study tool.

Technical Report TRRL-LR-253,Transport and Road Research

Laboratory,1969.

[13]S.Rogers,C.-N.Flechter,and P.Langley.An adaptive interactive

agent for route advice.In O.Etzioni,J.P.M¨u ller,and J.M.

Bradshaw,editors,Proceedings of the Third International

Conference on Autonomous Agents(Agents’99),pages198–205,

Seattle,WA,USA,1999.ACM Press.

[14] D.A.Roozemond.Using intelligent agents for urban traffic control

control systems.In Proceedings of the International Conference on Artificial Intelligence in Transportation Systems and Science,pages 69–79,1999.

[15]T.Schonberg,M.Ojala,J.Suomela,A.Torpo,and A.Halme.

Positioning an autonomous off-road vehicle by using fused DGPS and inertial navigation.In2nd IFAC Conference on Intelligent

Autonomous Vehicles,pages226–231,1995.

[16]P.Stone and M.Veloso.Multiagent systems:A survey from a

machine learning perspective.Autonomous Robots,8(3):345–383, July2000.

[17]Texas Transportation Institute.2004urban mobility report,

September2004.Accessed at

http://mobility.tamu.edu/ums in December2004.下载本文