# Multiagent Based Decentralized Traffic Light Control for Large Urban Transportation System

Authors: Yang Xu; Yulin Zhang; Ming Liu
Journal: Mathematical Problems in Engineering
 (2014)

---

## Abstract

Intelligent traffic control is an important issue of the modern
transportation system. However, in large-scale urban
transportation systems, traditional centralized coordination
methods suffer bottlenecks in both communication and computation.
Decentralized control is hard if there is very limited observation
to the whole network as evidences to support joint traffic
coordination decisions. In this paper, we proposed a novel
decentralized, multiagent based approach for massive traffic
lights coordination to promote the large-scale green
transportation. Considering that only the traffic from the
adjacent intersections may affect the state of a given
intersection one time ahead, the key of our approach is using the
observations of a local intersection and its neighbors as
evidences to support the traffic light coordination decisions.
Therefore, we can model the interactions as decentralized agents
coordinating with a decision theoretical model. Within a local
intersection, constraint optimizing agents are designed to
efficiently search for joint activities of the lights. Since this
approach involves only local intersection cooperation, it is well
scalable and easily implemented with small communication overhead.
In the last section, we present our software design on this
approach and based on our simulation, this approach is feasible to
a large urban transportation system.


---

## Body

## 1. Introduction

Building intelligent transportation techniques in large urban transportation systems is appealing to reduce fuel consumptions and transportation delays [1]. A key is to enable joint coordination between intersections so that continuous traffic can flow over several intersections in main directions with the least delays [2].To achieve this, extensive researches have been carried out. Traditional centralized coordination schemas, such as auction [3] and resource optimization [4], although have proven their performance to coordinate a number of intersections, they are infeasible to the large urban transportation system due to their computation and communication bottleneck shown in related literatures [5]. Existing works in decentralized traffic control suffer many limitations due to the nature of partial observability to the whole transportation network as well as its high dynamic traffic patterns. Historical data based approaches, such as reinforcement learning [6] and pattern discovery models [7], rely on the statistic pattern inferred to predict incoming traffics. However, they are incapable of managing dynamic traffic patterns dissimilar to the historical data, such as traffic accident or road maintenance. Some other works use dynamic programming to react to the dynamic real-time traffic according to the sensor readings, but the models are based on some impractical assumptions. For example, Robertson used a decentralized control schema but assumed that the sensor information within the whole area was easily obtained from centralized severs [8]. This may suffer a communication bottleneck in a huge urban area. Shenoda assumed that the coming vehicles follow a Poisson distribution to build a decentralized coordination algorithm [9], which is not always the case, for example, domain of emergency response in disasters. Xie et al. used fixed traffic signal phases to solve the conflicted traffic flows [10], which is not flexible to optimize concurrent traffic flows within the intersections.In this paper, we proposed a decentralized traffic control approach to enable green transportation in a large urban area. This approach is built based on a two-level hierarchical agent-based architecture toward robust and flexible coordination. In the top level, decentralized agents are modeled to coordinate with the neighbor intersections. In the bottom level, local agents within an intersection work cooperatively with a constraint optimization model. To enable the intelligent transportation, the key is that agents should make decisions based on the prospection of their local traffic state. Although it is infeasible for these agents to get the global state of the whole network to infer its next local state, we observed that only the traffic in their locally adjacent intersections can affect their coordination decision. Therefore, by closely interacting with their neighbors and sharing their local traffic states, each intersection may be able to gain a complete view of the states necessary to achieve decentralized control. Since this approach requires only the local state of neighbor intersections to cooperate, it is well scalable and easily implemented with small communication overhead.In our algorithm design, between intersections, we setup a decision theoretical model for decentralized coordination. Since the next-time traffic is solely determined by the current state of the local intersection and its actions, it is a Markov decision process (MDP) and each agent takes the states of adjacent intersections into consideration for their decision model. To solve the uncertainties in state transition functions, we built heuristics either from statistic data or from reinforcement learning so that middle agents are able to jointly choose their best actions to minimize traffic delays. In addition, local agents within an intersection handle the local traffic. The decision process within a local intersection is modeled as a constraint optimization problem (COP) where maximum traffic flow should get through but conflicted traffics should be avoided.In order to implement our software design, the key is to build each agent and implement the coordination by the interactions of the agents. In the top level, information agent is modeled for each intersection to maintain the local state that it needs to make decisions. In the bottom level, control agents within an intersection work cooperatively to solve the conflicts of different traffic flows. Middle agents are also built to coordinate all these control agents with the COP model. By building these two-level agents, the coordination between intersections is mainly achieved by the information agents, and the conflicts within each intersection are able to be solved by the middle agent and control agents. The system is implemented by RETSINA platform. In addition, it is simulated and the illustrated results proved the feasibility of our approach.


## 2. State of the Art

Many algorithms are designed to optimize the traffic of large urban transportation system in a decentralized manner. In order to achieve decentralized urban traffic control, the most straightforward approach is to generate optimal coordinated plans for fixed-time operation, such as TRANSYT [11]. However, due to the high dynamics in large urban transportation, this approach is hard to be adaptive to its real-time traffic.Historical data are widely used to generate adaptive algorithms. Pattern discovery models are developed by categorizing the historical traffic into different patterns and assigning an optimal traffic light control plan for each pattern. PCA and SVM methods are applied for feature extraction, training, and classification of network-level traffic patterns [12] so that sensors within the intersection can detect real-time traffic pattern and choose the predefined plan. But the traffic patterns known as a priori may not cover all the patterns in real domains. An alternative is to incrementally build new patterns by assuming that the traffic is relatively infrequently changing [13]. Reinforcement learning is a set of techniques that is always applied in this domain. Q-learning is applied to learn the control policy for single intersection from historical data [14]. Multiagent reinforcement learning is applied for all the agents to learn the control concurrently, but this approach is not scalable since the reward function is too large to be enumerated [6]. In addition, all these approaches are incapable of managing dynamic traffic patterns dissimilar to the historical data, such as traffic accident or road maintenance.In order to effectively respond to real-time traffic, close interactions between intersections are carried out to obtain the network-level traffic information and synchronize all the interactions over the network. Distributed constraint optimization problem (DCOP) is applied to formalize the synchronization of different intersections [15]. However, this approach is based on a centralized mediator to refer for all intersections in a given mediation session, which suffers communication and computation bottleneck when the network scales up. ADOPT and DPOP models are also carried out with either huge communication overload or retarded system response time [5].Some other approaches relax these interactions and synchronize only within local intersections to obtain a good policy. For example, Phase-by-phase system is developed to optimize traffic for local intersections by predicting the traffic flow merely from their neighbors, but this research is based on the assumption that the vehicles to an intersection follow a Poisson process, which is not always the case in the real domain [9]. Xie et al. model the urban traffic control as a synchronously operating scheduling problem [10]. Each intersection agent estimates its future traffic from its upstream neighbors to obtain a myopic projection if the traffic flow is characterized as a cluster sequence, which is inaccurate in real domain with unpredictable vehicle behaviors.


## 3. Problem Description

A given traffic network can be modeled as an undirected graphG(V,E) shown in Figure 1, where V is the set of intersections and E is the set of roads between intersections. For any two intersections vi and vj, 〈vi,vj〉∈E represents that there is a road that vehicles can get through between vi and vj, and vi and vj are neighbors. Specifically, n(vi) is defined as all the neighbors of the intersection vi, and |n(vi)| is the number of roads connected to intersection vi. For example, in Figure 1, |n(v1)|=4 and |n(v4)|=3. For each road 〈vi,vj〉, there are |n(vi)|-1 turning directions toward vi, and each of them is called a lane. In Figure 1, there are 3 lanes of each road connecting to v1 and 2 lanes each to v13. The total number of lanes in vi can be calculated as |n(vi)|×(|n(vi)|-1). To be easily referred, the lane from intersection vj to intersection vk going through vi is written as Lnij(k), vk∈{n(vi)-vj}.Figure 1
Models of intersections in a given urban area.In each intersection, there are a number of vehicles stopping and waiting to go through. We assume that the number of vehicles waiting at laneLnij(k) at time t, written as Tfij(k,t), can be detected by video cameras installed at each intersection. Because it is unable to detect the waiting traffic one time ahead, Tfij(k,t+1) is unobservable.As shown in Figure2, in an intersection, each traffic light takes an action to control a specific lane. Specifically, at time t the action to control the vehicles on the lane directed from vj to vk at vi is written as £ij(k,t)∈{green,red}. Please note that yellow is not assigned to £ij(k,t) because yellow is a fixed interim status necessary from green to red and is not an independent action.Figure 2
Model of intersections in a transportation network.At each horizon, we model the transition function under the action of each traffic light£ij(k,t) as the waiting vehicles transferred from Tfij(k,t) to Tfij(k,t+1). It denotes that after each lane takes an action, waiting traffic gets through the intersection and new traffic arrives, and the waiting traffic is transferred to Tfij(k,t+1).Since green intelligent control is an intention that a series of traffic lights are coordinated to allow continuous traffic flow over several intersections in main directions [1], its control should allow more vehicles to go through the intersections with the least delay. To maximize the moving vehicles, the sum of vehicles in the waiting queues should be minimized. Therefore, the key is to minimize waiting vehicles in the next time step other than the myopic optimization in the current time. We define the utility function toward the intelligent control for the global transportation network as
(1)EU(G,t)=∑vi∈V∑vj∈n(vi)∑vk∈{n(vi)-vj}‍Tfij(k,t+1).
In this formula, the expected utilities of the cooperative transportation network G at time t (defined as EU(G,t)) are the sum of the waiting vehicles in front of intersections at time step t+1.Based on the expected utility function, the goal of cooperative traffic light control over the networkG is to find an optimal joint policy π* for traffic lights coordinating all the intersections so that the expected utility could be minimized. Consider
(2)π*(t)=argminJt_act(G,t)⁡EU(G,t),
where Jt_act(G,t) in the transportation network G at time t consists of all the independent activities of each lane over every intersection at that time. It can be written as
(3)Jtact(G,t)=⋃vi∈V⋃vj∈n(vi)⋃vk∈{n(vi)-vj}£ij(k,t).SinceTfij(k,t+1) is not observable, finding the optimal policy π* is intrinsically unsolvable in a large-scale transportation system [16].


## 4. Multiagent Based Traffic Control System

To solve the problem above, the key is to make the decisions to carry out the activities based on the prospection of local intersection state one time ahead. Although neither observation of the local state one time ahead nor accessing the global states of whole transportation network for inference is feasible, the estimation to the next local state of each intersection can still be made according to the following key characters in physical transportation networks.(i)
The state of the network at time stept+1 is solely determined by its state at time step t.(ii)
For any intersectionvi, its traffic flow is solely determined by the traffic flow arriving from its adjacent intersections.Therefore, only the traffic in local intersection and the neighbors can affect its next coordination decision. If close interaction between adjacent intersections can be made to share their local traffic states and inform neighbors in advance of the actions that they are going to carry out, we can build a decentralized traffic coordination to solve this urban traffic optimization problem in a myopic view.


### 4.1. Decentralized Multiagent System Design

According to this, our multiagent system design is illustrated as Figure3(a). Based on the analysis in Section 3, the urban traffic network is modeled as a graph. In the graph, each intersection is represented as a node and the road between them has been abstracted as a link. In the next level, since only the traffic of the local intersection and its adjacent intersections can affect its next coordination decision, each intersection has to share their states with their neighbors. For each intersection, we setup an information agent to share the states of the traffic of their lanes with the neighbors as well as receiving and publishing the adjacent intersection states to be used for the intersection’s local decisions.Decentralized multiagent based traffic light coordination architecture and implementation.
(a)
Multiagent traffic light coordination architecture design
(b)
System implementationIn the bottom level, control agents are responsible to solve their joint optimized decisions within the intersection. To achieve this, the multiagent system consists of three parts. As the first part, a blackboard is used to gather the information provided by its information agent, which are (1) current states of waiting traffic and traffic control actions from each adjacent intersection and (2) the states of waiting traffic of its own intersection. As the second part, each lane within the intersection is represented by a control agent to make decisions for its own lane and negotiate with the other control agent to solve the conflicts of different traffic flows. As the third part, a middle agent is built to coordinate local control agents to reach optimized joint decisions.The system implementation of our approach is illustrated by Figure3(b). We use the RETSINA platform to implement the multiagent system with the three basic agents as well as their agent communication language. In addition, we build algorithms for the agents to achieve green intelligent traffic coordination. Between intersections, since an intersection’s decision is only determined by the states of its local neighbors, we model the decision as a Markov decision process. Within each intersection, the decision process of the control agents is modeled as a constraint optimization problem (COP). In the rest of this section, we will introduce in detail the agent and algorithm designs.


### 4.2. Information Agent

In order to coordinate with neighbor intersections and gain the information required for decision, information agentIAi is built for intersection vi and we have IA={IA1,IA2,…IAi,…}, |IA|=|V|. Inherited from the transportation network, the logical network of the information agents follows the same connection of G and agent IAi has a set of neighbor information agents n(IAi)={IAj∣vj∈n(vi)}, which represents the information agents of vi’s adjacent intersections.At timet, agent IAi is able to gain the local state Tf(vi,t) of intersection vi:
(4)Tf(vi,t)=⋃vj∈n(vi)⋃vk∈{n(vi)-vj}Tfij(k,t).To make a rational decision toward decentralized traffic optimization, the intersection should know the traffic flows released from neighbor intersections before they arrive. In this case, the agentIAi has to gain a complete view of the local state of vi and the actions of their neighbors’ incoming action in advance. Hence the state of vi is defined as follows:
(5)Svi(t)=Tf(vi,t)⋃vj∈n(vi)Tf(vj,t)⋃vj∈n(vi)£j(t),
where £j(t) is the joint action of all the traffic lights, £j(t)=⋃vl∈n(vj)⋃vm∈{n(vj)-vl}£jl(m,t), and £jl(m,t) is the action for the traffic light controlling lane Lnjl(m) at time t. As Figure 4 shows, the local state obtained by the information agent is published on the blackboard for the agents within the intersection.Figure 4
Information processing between agents.In formula (5), the state of intersection vi is composed of the waiting traffic at the local intersection, those of its adjacent intersections as well as their actions to be carried out at t. Since the actions of the neighbors to be carried out at t should be shared in advance to gain the complete view of Svi(t), IAi as a neighbor of the other agents should have to share its action in advance as well. To break this deadlock, a practical protocol has been designed to estimate its action with £i+(t). The details of the decentralized coordination model of vi will be presented in Section 5.1. In addition, another key of this model is how to infer vi’s next-time local state Tf(vi,t+1) from its current local state, which will be addressed in Section 5.3.


### 4.3. Middle Agent and Control Agent

Within each intersection, there are conflicts between different traffic lights. Although it is possible forvi to make a decision for all the traffic lights within the intersection based on the fixed conflict-free traffic signal phases, it is not flexible to deal with unpredictable traffic patterns. Therefore, we build a middle agent and a set of control agents for each intersection. As Figure 4 illustrates, a control agent θij(k) is built for each traffic light to monitor and control traffic on lane Lnij(k). Before each round of decision, it monitors the waiting traffic on the lane and publishes it on the blackboard. After the local state is obtained by the information agent and published on the blackboard, all the control agents in the intersection work together to eliminate the conflict actions and provide local optimized activities £oci(t) for the middle agent. The middle agent MAi for intersection vi is responsible to initialize and coordinate all these control agents within the intersection and also choose the best joint action from the local optimized activities £oci(t).


### 4.4. Interactions between Agents

With the two-level multiagent system, their decentralized coordination is able to be achieved through the information processing process shown in Figure4. Firstly, the control agent monitors the waiting traffic at the lane and publishes it on the blackboard. Then the middle agent is able to estimate its current action £i+(t). In order to gain the local state, the information agent shares its waiting traffic and expected action with neighbors. After the local state is obtained and published on the blackboard, the control agents are able to cooperatively generate the conflict-free local optimized joint actions £oci(t) and the middle agent can choose the best action from £oci(t).


## 4.1. Decentralized Multiagent System Design

According to this, our multiagent system design is illustrated as Figure3(a). Based on the analysis in Section 3, the urban traffic network is modeled as a graph. In the graph, each intersection is represented as a node and the road between them has been abstracted as a link. In the next level, since only the traffic of the local intersection and its adjacent intersections can affect its next coordination decision, each intersection has to share their states with their neighbors. For each intersection, we setup an information agent to share the states of the traffic of their lanes with the neighbors as well as receiving and publishing the adjacent intersection states to be used for the intersection’s local decisions.Decentralized multiagent based traffic light coordination architecture and implementation.
(a)
Multiagent traffic light coordination architecture design
(b)
System implementationIn the bottom level, control agents are responsible to solve their joint optimized decisions within the intersection. To achieve this, the multiagent system consists of three parts. As the first part, a blackboard is used to gather the information provided by its information agent, which are (1) current states of waiting traffic and traffic control actions from each adjacent intersection and (2) the states of waiting traffic of its own intersection. As the second part, each lane within the intersection is represented by a control agent to make decisions for its own lane and negotiate with the other control agent to solve the conflicts of different traffic flows. As the third part, a middle agent is built to coordinate local control agents to reach optimized joint decisions.The system implementation of our approach is illustrated by Figure3(b). We use the RETSINA platform to implement the multiagent system with the three basic agents as well as their agent communication language. In addition, we build algorithms for the agents to achieve green intelligent traffic coordination. Between intersections, since an intersection’s decision is only determined by the states of its local neighbors, we model the decision as a Markov decision process. Within each intersection, the decision process of the control agents is modeled as a constraint optimization problem (COP). In the rest of this section, we will introduce in detail the agent and algorithm designs.


## 4.2. Information Agent

In order to coordinate with neighbor intersections and gain the information required for decision, information agentIAi is built for intersection vi and we have IA={IA1,IA2,…IAi,…}, |IA|=|V|. Inherited from the transportation network, the logical network of the information agents follows the same connection of G and agent IAi has a set of neighbor information agents n(IAi)={IAj∣vj∈n(vi)}, which represents the information agents of vi’s adjacent intersections.At timet, agent IAi is able to gain the local state Tf(vi,t) of intersection vi:
(4)Tf(vi,t)=⋃vj∈n(vi)⋃vk∈{n(vi)-vj}Tfij(k,t).To make a rational decision toward decentralized traffic optimization, the intersection should know the traffic flows released from neighbor intersections before they arrive. In this case, the agentIAi has to gain a complete view of the local state of vi and the actions of their neighbors’ incoming action in advance. Hence the state of vi is defined as follows:
(5)Svi(t)=Tf(vi,t)⋃vj∈n(vi)Tf(vj,t)⋃vj∈n(vi)£j(t),
where £j(t) is the joint action of all the traffic lights, £j(t)=⋃vl∈n(vj)⋃vm∈{n(vj)-vl}£jl(m,t), and £jl(m,t) is the action for the traffic light controlling lane Lnjl(m) at time t. As Figure 4 shows, the local state obtained by the information agent is published on the blackboard for the agents within the intersection.Figure 4
Information processing between agents.In formula (5), the state of intersection vi is composed of the waiting traffic at the local intersection, those of its adjacent intersections as well as their actions to be carried out at t. Since the actions of the neighbors to be carried out at t should be shared in advance to gain the complete view of Svi(t), IAi as a neighbor of the other agents should have to share its action in advance as well. To break this deadlock, a practical protocol has been designed to estimate its action with £i+(t). The details of the decentralized coordination model of vi will be presented in Section 5.1. In addition, another key of this model is how to infer vi’s next-time local state Tf(vi,t+1) from its current local state, which will be addressed in Section 5.3.


## 4.3. Middle Agent and Control Agent

Within each intersection, there are conflicts between different traffic lights. Although it is possible forvi to make a decision for all the traffic lights within the intersection based on the fixed conflict-free traffic signal phases, it is not flexible to deal with unpredictable traffic patterns. Therefore, we build a middle agent and a set of control agents for each intersection. As Figure 4 illustrates, a control agent θij(k) is built for each traffic light to monitor and control traffic on lane Lnij(k). Before each round of decision, it monitors the waiting traffic on the lane and publishes it on the blackboard. After the local state is obtained by the information agent and published on the blackboard, all the control agents in the intersection work together to eliminate the conflict actions and provide local optimized activities £oci(t) for the middle agent. The middle agent MAi for intersection vi is responsible to initialize and coordinate all these control agents within the intersection and also choose the best joint action from the local optimized activities £oci(t).


## 4.4. Interactions between Agents

With the two-level multiagent system, their decentralized coordination is able to be achieved through the information processing process shown in Figure4. Firstly, the control agent monitors the waiting traffic at the lane and publishes it on the blackboard. Then the middle agent is able to estimate its current action £i+(t). In order to gain the local state, the information agent shares its waiting traffic and expected action with neighbors. After the local state is obtained and published on the blackboard, the control agents are able to cooperatively generate the conflict-free local optimized joint actions £oci(t) and the middle agent can choose the best action from £oci(t).


## 5. Intelligent Traffic Control Algorithm

Based on our multiagent system design, we build algorithms for these agents to generate the optimal action£oci*(t) according to state Svi(t) and solve the constraints within the intersection. An overview of our traffic control algorithm is illustrated in Figure 5. For each intersection, before making the decision, it has to share its state of local waiting traffic and expected actions. Since the intersection’s next time state can be maintained with its information agent, a Markov decision process can be built for the decentralized traffic control as a conflict-free localized optimal action set. Secondly, we model this coordination within the intersection as a constraint optimization problem (COP). In order to solve these models, the key is to figure out the transition from the current local state Tfij(k,t) to its next local traffic state Tfij(k,t+1) one time ahead. Finally, we propose a heuristic algorithm for the local state transition function.Figure 5
Coordination model of local intersection.


### 5.1. Coordination between Intersections

In this section, we present the details on how agents in different intersections coordinate with each other, and what information is shared, so as to make their decentralized actions toward optimized decentralized traffic control. The key is that agents build their own local states to infer the states of their local intersections one time ahead. For a specific middle agentMAi, its decentralized control process is built as a decision theoretical model 〈Svi,£oci,T,Tf(vi)〉.(i)
State:Svi(t) is the intersection vi’s local state at t. It is built from the information received from their neighbors as well as the observation to the local traffic state.(ii)
Action: as explained in Section3, agent MAi is only able to choose the action from the available joint activities set £oci(t) worked out by its local agents Θi.(iii)
Transition functionT:S→Tf(vi) defines the transition from state Svi(t) to the local traffic state of vi at t+1 by the action.(iv)
Utility function is defined asTf(vi,t+1).M
A
i is to find its optimal policy πΔ:
(6)πΔ=argmin£oci(t)⁡Tf(vi,t+1).A key challenge of this model is that information agentIAi has to share its current joint action of all the traffic lights in the interaction with its neighbors one time ahead. And these joint actions of the neighbors are critical to build Svi(t), which in turn influences their own decision. Therefore, the agent has to make its decision based on sharing its decision result one time ahead and this looping process produces a deadlock.To break this deadlock, from formula (5), we observe that a heuristic protocol can be designed because adjacent intersections’ joint actions only contribute a small portion to the local state. Therefore, an estimated joint action £i+(t) to £i(t) can be defined to solve this deadlock, and formula (5) can be represented as
(7)Svi(t)=Tf(vi,t)⋃vj∈n(vi)Tf(vi,t)⋃vj∈n(vi)£j+(t).£
i
+
(
t
) can be estimated in many ways; a practical way is to estimate £i+(t) one time ahead according to the local state Tf(vi,t). Therefore, we design a practical algorithm as
(8)Tf(vi,t)⟶£i+(t),
where the action is determined by the number of waiting traffics of each lane in the intersection. Although it may be imprecise to estimate £i+(t) based on historical states, considering that the traffic moves continuously, £i+(t) cannot be significantly varied from £i(t).


### 5.2. Coordination within Intersection

In this section, we present how the control agentsΘi in an intersection vi are coordinated by middle agent MAi to build the local conflict-free joint activities set £oci(t). In order to solve the constraints within the intersection, the agents have two policies: fixed policy and dynamic policy. In the fixed policy, £oci(t) contains all the conflict-free joint actions, which are predefined. In the dynamic policy, the middle agent gives an order to the control agents and each agent proposes its preferred action according to the order.In this paper, we focus on the dynamic policy design, and the middle agent has to work out a set of orders for the control agents as their social conventions and start the negotiation from one control agent at each round to get a local joint action. There are also two ways to generate each of the order: random ordering and heavy traffic lane first. Random ordering initializes the order of control agents randomly. On the other way, the control agent with more waiting traffic is given a higher priority.Following a given order, all the control agents have to coordinate to work out the local optimized conflict-free joint policy. The coordination process of all the agents inΘi is built as a constraint optimization model 〈£i,{green,red},Ci〉.(i)
£i defines the variables of COP, where each variable is the traffic light action of £ij(k,t) worked out by θij(k).(ii)
Each£ij(k,t) is only chosen from a binary set {green,red}.(iii)
Ci is the binary constraint set predefined for vi by domain. For example, typical traffic conflictions in a four-way intersection can be illustrated in Figure 6, where any variables connected with a dash line cannot be green at the same time.Figure 6
Traffic conflictions in a four-way intersection.The utility function for each assignment of variableθij(k) can be formulated to help agent θij(k) to locally minimize the waiting traffic of its lane:
(9)EU(Tfij(k),£ij(k,t))=Tfij(k,t+1).
For each agent θij(k), its optimization policy is
(10)πΔΔ=argmin£ij(k,t)⁡Tfij(k,t+1).
According to this policy, we build a myopic heuristic mapping function as
(11)£ij(k,t)×Tfij(k+1)×∑vl∈n(vk)-vi‍Tfki(l,t)⟶[0,1].
In this equation, if θij(k) is more likely to help to reduce Tfij(k+1), the agent θij(k) is more likely to set £ij(k,t) as green. The pending downstream traffic Tfki(l,t) to the adjacent intersections should also be considered. Because if there is heavy traffic in the next intersection to go through, discharging more traffic there is not helpful and the lane is less likely to be set as green. In addition, to avoid any lane with very little waiting traffic being set as continuous red, we define that the continuous red phrase should not exceed Rmax⁡.The decision process of local agentsΘi is described in Algorithm 1. In this algorithm, MAi initiates an order for the control agents in Θi (line 1) and sets up a set of searches for £oci (line 2). For each search £oci[m], it randomly starts from an agent (line 4), and each agent θij(k) sequentially chooses its action £ocij(k,t+1) according to formula (11) (line 6). Since agents’ decisions are based on the probabilistic model, the optimal joint activities are not guaranteed in the searches. Therefore, we set the size of £oci bigger than the number of lanes in vi to increase the chance of optimization. However, it also increases the computation complexity for Θi.Algorithm 1:Decision process of Θi within intersection vi.
(1)orderi=Mi.generateOrder(Θi);
(2)Mi.SetupSearches(£oci);
(3)for all  £oci[m]∈£oci  do
(4)orderi.starter=RandomChoose(Θi);
(5)for all  θij(k)←orderi.next()  do
(6)£ocij(k,t)←Lottery(Tfij(k,t+1),Tf(vk,t));
(7)end for;
(8)end for;
(9)return  £oci;


### 5.3. Heuristic Transition Function

Although solving the scalable MDP for massive traffic lights control is mathematically feasible, the uncertainties on the state transition function resulted by unpredictable traffic in heavy traffic network will make the computation hard. There are three key factors:(i)
the unpredictable amount of traffic going through under a given green light;(ii)
the uncertainty of line choosing on the adjacent intersection when vehicles passed through a given intersection;(iii)
the unpredictable arriving time of given traffic arrived at the next intersection which depends on the congestion and road conditions as well as their distances between intersections.These factors may vary significantly under different traffic conditions. For simplicity and clarity of our model, we make the following two assumptions. Firstly, we assume that the traffic flow getting through the intersection follows the exponential queue discharge flow rate model [17]. In this case, during a green-light cycle Δi, the maximum number of vehicles getting through an intersection is denoted as h(Δi). Therefore, at each time t, the number of vehicles getting through lane Lnij(k) is denoted as Tdij(k,t), which could be estimated as If £ij(k,t)=green, during the green-light cycle Δi(12)Tdij(k,t)={Tfij(k,t),ifTfij(k,t)<h(Δi)h(Δi),otherwise,
otherwise, £ij(k,t)=red and Tdij(k,t)=0.Secondly, the probability for each vehicle to choose the lane could be estimated from historical statistics. In this paper, we assume that vehicles will evenly choose the lanes after it gets through an intersection. Thus, the probabilityPij(k) is
(13)∀vk∈n(vi),vj∈n(vi)-vk,Pij(k)=1|n(vi)|-1.With the assumptions above, we can establish the transition fromTfij(k,t) to Tfij(k,t+1). Observing that the number of vehicles on a given lane is determined by vehicles’ choice of lanes and the number of vehicles released by adjacent intersections in the last cycle, we will have
(14)Pij(k)×∑vl∈n(vj)-vi‍Tdjl(i,t).According to the real-time traffic condition, not all vehicles released from its adjacent intersections can arrive at the intersection at the end of the green phase. The number of vehicles arriving at intersectionvi on lane Lnij(k) is denoted as Tcij(k,t). If the weight of next road is wi,j, a function to predict the arriving ones within the traffic light period Δi can be proposed as
(15)Tcij(k,t)=g(Pij(k)×∑vl∈n(vj)-vi‍Tdjl(i,t),wi,j).With the number of vehicles to be released and the ones to arrive at the intersection, the transition function to update the waiting vehicles at next timeTfij(k,t+1) can be computed as
(16)Tfij(k,t+1)=Tfij(k,t)+Tcij(k,t)-Tdij(k,t).Algorithm2 presents the process of state transition of intersection vi from state t to the local state one time ahead t+1. For each lane Lnij(k), it firstly estimates the number of vehicles that can get through this intersection when the traffic light is set green according to formula (12) (line 2–6). Next, it calculates the probability of each line that the vehicles will choose (line 7). After the number of vehicles released from adjacent intersections and their lane choosing probability are figured out, the number of vehicles arriving at this lane at next time is able to be calculated according to formula (15) (line 8). Finally, according to the transition function (16), Tfij(k,t+1) could be solved (line 9). When all lanes’ one time ahead states are estimated, the local state at t+1 is worked out (line 11).Algorithm 2:Intersection vi’s transition process from current state to the local state one time ahead.
(1)for  Lnij(k)∈vi  do
(2)if  Tfij(k,t)<h(Δi)  then
(3)Tdij(k,t)=Tfij(k,t);
(4)else
(5)Tdij(k,t)=h(Δi);
(6)end if
(7)Pij(k)=1|n(vi)|-1
(8)calculate  Tcij(k,t)
(9)calculate  Tfij(k,t+1);
(10)end for
(11)return  Tf(vi,t+1);


## 5.1. Coordination between Intersections

In this section, we present the details on how agents in different intersections coordinate with each other, and what information is shared, so as to make their decentralized actions toward optimized decentralized traffic control. The key is that agents build their own local states to infer the states of their local intersections one time ahead. For a specific middle agentMAi, its decentralized control process is built as a decision theoretical model 〈Svi,£oci,T,Tf(vi)〉.(i)
State:Svi(t) is the intersection vi’s local state at t. It is built from the information received from their neighbors as well as the observation to the local traffic state.(ii)
Action: as explained in Section3, agent MAi is only able to choose the action from the available joint activities set £oci(t) worked out by its local agents Θi.(iii)
Transition functionT:S→Tf(vi) defines the transition from state Svi(t) to the local traffic state of vi at t+1 by the action.(iv)
Utility function is defined asTf(vi,t+1).M
A
i is to find its optimal policy πΔ:
(6)πΔ=argmin£oci(t)⁡Tf(vi,t+1).A key challenge of this model is that information agentIAi has to share its current joint action of all the traffic lights in the interaction with its neighbors one time ahead. And these joint actions of the neighbors are critical to build Svi(t), which in turn influences their own decision. Therefore, the agent has to make its decision based on sharing its decision result one time ahead and this looping process produces a deadlock.To break this deadlock, from formula (5), we observe that a heuristic protocol can be designed because adjacent intersections’ joint actions only contribute a small portion to the local state. Therefore, an estimated joint action £i+(t) to £i(t) can be defined to solve this deadlock, and formula (5) can be represented as
(7)Svi(t)=Tf(vi,t)⋃vj∈n(vi)Tf(vi,t)⋃vj∈n(vi)£j+(t).£
i
+
(
t
) can be estimated in many ways; a practical way is to estimate £i+(t) one time ahead according to the local state Tf(vi,t). Therefore, we design a practical algorithm as
(8)Tf(vi,t)⟶£i+(t),
where the action is determined by the number of waiting traffics of each lane in the intersection. Although it may be imprecise to estimate £i+(t) based on historical states, considering that the traffic moves continuously, £i+(t) cannot be significantly varied from £i(t).


## 5.2. Coordination within Intersection

In this section, we present how the control agentsΘi in an intersection vi are coordinated by middle agent MAi to build the local conflict-free joint activities set £oci(t). In order to solve the constraints within the intersection, the agents have two policies: fixed policy and dynamic policy. In the fixed policy, £oci(t) contains all the conflict-free joint actions, which are predefined. In the dynamic policy, the middle agent gives an order to the control agents and each agent proposes its preferred action according to the order.In this paper, we focus on the dynamic policy design, and the middle agent has to work out a set of orders for the control agents as their social conventions and start the negotiation from one control agent at each round to get a local joint action. There are also two ways to generate each of the order: random ordering and heavy traffic lane first. Random ordering initializes the order of control agents randomly. On the other way, the control agent with more waiting traffic is given a higher priority.Following a given order, all the control agents have to coordinate to work out the local optimized conflict-free joint policy. The coordination process of all the agents inΘi is built as a constraint optimization model 〈£i,{green,red},Ci〉.(i)
£i defines the variables of COP, where each variable is the traffic light action of £ij(k,t) worked out by θij(k).(ii)
Each£ij(k,t) is only chosen from a binary set {green,red}.(iii)
Ci is the binary constraint set predefined for vi by domain. For example, typical traffic conflictions in a four-way intersection can be illustrated in Figure 6, where any variables connected with a dash line cannot be green at the same time.Figure 6
Traffic conflictions in a four-way intersection.The utility function for each assignment of variableθij(k) can be formulated to help agent θij(k) to locally minimize the waiting traffic of its lane:
(9)EU(Tfij(k),£ij(k,t))=Tfij(k,t+1).
For each agent θij(k), its optimization policy is
(10)πΔΔ=argmin£ij(k,t)⁡Tfij(k,t+1).
According to this policy, we build a myopic heuristic mapping function as
(11)£ij(k,t)×Tfij(k+1)×∑vl∈n(vk)-vi‍Tfki(l,t)⟶[0,1].
In this equation, if θij(k) is more likely to help to reduce Tfij(k+1), the agent θij(k) is more likely to set £ij(k,t) as green. The pending downstream traffic Tfki(l,t) to the adjacent intersections should also be considered. Because if there is heavy traffic in the next intersection to go through, discharging more traffic there is not helpful and the lane is less likely to be set as green. In addition, to avoid any lane with very little waiting traffic being set as continuous red, we define that the continuous red phrase should not exceed Rmax⁡.The decision process of local agentsΘi is described in Algorithm 1. In this algorithm, MAi initiates an order for the control agents in Θi (line 1) and sets up a set of searches for £oci (line 2). For each search £oci[m], it randomly starts from an agent (line 4), and each agent θij(k) sequentially chooses its action £ocij(k,t+1) according to formula (11) (line 6). Since agents’ decisions are based on the probabilistic model, the optimal joint activities are not guaranteed in the searches. Therefore, we set the size of £oci bigger than the number of lanes in vi to increase the chance of optimization. However, it also increases the computation complexity for Θi.Algorithm 1:Decision process of Θi within intersection vi.
(1)orderi=Mi.generateOrder(Θi);
(2)Mi.SetupSearches(£oci);
(3)for all  £oci[m]∈£oci  do
(4)orderi.starter=RandomChoose(Θi);
(5)for all  θij(k)←orderi.next()  do
(6)£ocij(k,t)←Lottery(Tfij(k,t+1),Tf(vk,t));
(7)end for;
(8)end for;
(9)return  £oci;


## 5.3. Heuristic Transition Function

Although solving the scalable MDP for massive traffic lights control is mathematically feasible, the uncertainties on the state transition function resulted by unpredictable traffic in heavy traffic network will make the computation hard. There are three key factors:(i)
the unpredictable amount of traffic going through under a given green light;(ii)
the uncertainty of line choosing on the adjacent intersection when vehicles passed through a given intersection;(iii)
the unpredictable arriving time of given traffic arrived at the next intersection which depends on the congestion and road conditions as well as their distances between intersections.These factors may vary significantly under different traffic conditions. For simplicity and clarity of our model, we make the following two assumptions. Firstly, we assume that the traffic flow getting through the intersection follows the exponential queue discharge flow rate model [17]. In this case, during a green-light cycle Δi, the maximum number of vehicles getting through an intersection is denoted as h(Δi). Therefore, at each time t, the number of vehicles getting through lane Lnij(k) is denoted as Tdij(k,t), which could be estimated as If £ij(k,t)=green, during the green-light cycle Δi(12)Tdij(k,t)={Tfij(k,t),ifTfij(k,t)<h(Δi)h(Δi),otherwise,
otherwise, £ij(k,t)=red and Tdij(k,t)=0.Secondly, the probability for each vehicle to choose the lane could be estimated from historical statistics. In this paper, we assume that vehicles will evenly choose the lanes after it gets through an intersection. Thus, the probabilityPij(k) is
(13)∀vk∈n(vi),vj∈n(vi)-vk,Pij(k)=1|n(vi)|-1.With the assumptions above, we can establish the transition fromTfij(k,t) to Tfij(k,t+1). Observing that the number of vehicles on a given lane is determined by vehicles’ choice of lanes and the number of vehicles released by adjacent intersections in the last cycle, we will have
(14)Pij(k)×∑vl∈n(vj)-vi‍Tdjl(i,t).According to the real-time traffic condition, not all vehicles released from its adjacent intersections can arrive at the intersection at the end of the green phase. The number of vehicles arriving at intersectionvi on lane Lnij(k) is denoted as Tcij(k,t). If the weight of next road is wi,j, a function to predict the arriving ones within the traffic light period Δi can be proposed as
(15)Tcij(k,t)=g(Pij(k)×∑vl∈n(vj)-vi‍Tdjl(i,t),wi,j).With the number of vehicles to be released and the ones to arrive at the intersection, the transition function to update the waiting vehicles at next timeTfij(k,t+1) can be computed as
(16)Tfij(k,t+1)=Tfij(k,t)+Tcij(k,t)-Tdij(k,t).Algorithm2 presents the process of state transition of intersection vi from state t to the local state one time ahead t+1. For each lane Lnij(k), it firstly estimates the number of vehicles that can get through this intersection when the traffic light is set green according to formula (12) (line 2–6). Next, it calculates the probability of each line that the vehicles will choose (line 7). After the number of vehicles released from adjacent intersections and their lane choosing probability are figured out, the number of vehicles arriving at this lane at next time is able to be calculated according to formula (15) (line 8). Finally, according to the transition function (16), Tfij(k,t+1) could be solved (line 9). When all lanes’ one time ahead states are estimated, the local state at t+1 is worked out (line 11).Algorithm 2:Intersection vi’s transition process from current state to the local state one time ahead.
(1)for  Lnij(k)∈vi  do
(2)if  Tfij(k,t)<h(Δi)  then
(3)Tdij(k,t)=Tfij(k,t);
(4)else
(5)Tdij(k,t)=h(Δi);
(6)end if
(7)Pij(k)=1|n(vi)|-1
(8)calculate  Tcij(k,t)
(9)calculate  Tfij(k,t+1);
(10)end for
(11)return  Tf(vi,t+1);


## 6. Software Design

In this section, we present the multiagent system design as well as the information processing process. Our two-level agents are built based on RETSINA [18] for its advantage of the programming platform and multiagent coordination mechanism. RETSINA is developed by Robotics Institute of Carnegie Mellon University. It implements all the basic types of agents and the agent communication language (ACL) as well as the agent management service. In addition, RETSINA also provides a peer to peer interaction mechanism for the multiagent systems in a distributed infrastructure. It is implemented with C and C++, which could be easily encoded in embedded traffic control devices. In our multiagent system design, there are four key components.Information agent responds to share the local states with the other information agents of the adjacent intersections. It is implemented based on the RETSINA information agent, which carries out the specific task to communicate with other information agents by using ACL.Control agent is customized to make decisions for each lane that it represents. It is based on the RETSINA task agent to carry out the information process described in Algorithm2.Middle agent is also built based on RETSINA basic task agent. It responds to generate the order for the control agents within the intersection and choose the best policy to achieve joint decentralized control.Blackboard is a single instance for each intersection in the multiagent system. It is used to provide information publish service for all agents within the intersection.The multiagent traffic control system designed is illustrated in Figure7. In Figure 7(a), information agent inherits from RETSINA information agent. Both middle agent and control agent inherit from RETSINA task agent. All these agents have access to the blackboard component and the methods related to the cooperative decision. The interaction process in Figure 4 is presented as the sequence diagram illustrated in Figure 7(b). All the agents have their own threads and lifetime, and they interact with each other asynchronously. With the help of blackboard component, all these agents are able to publish and get the information critical to joint intelligent traffic coordination.Software engineering illustration of the multiagent system design.
(a)
Class diagram
(b)
Sequence diagram


## 7. Simulation and Results

In order to manifest the feasibility of our approach, we build an abstract traffic simulator for evaluation. The screen shot of the urban traffic simulator is shown in Figure8. In this simulator, we build a grid network with a number of intersections, where each intersection connects four adjacent intersections. Vehicles are simulated to go through the network but they have to wait in front of the intersections until the light of their lanes are green.Figure 8
The screen shot of the urban traffic simulator.In our simulation, we load different control schemas to control the traffic so that we can compare the performance with our design. In our experiment, the route of each vehicle is randomly produced and we choose three different schemas to control the traffic: our design labeled ascoordinate intelligent, local real-time traffic control policy labeled aslocal intelligent, and the traditional round-robin policy labeled asround robin. The local real-time traffic control policy (local intelligent) is based on the literature [15], whose objective is to release maximum waiting vehicles merely based on the local state of the interaction. We hypothesized that without the prospection one time ahead to build the intelligent control,local intelligent should perform worse than our approach.Round robin control policy assigns uniform time slices for all the conflict-free traffic signal phases, which are initialized in deployment. It schedules all these conflict-free traffic signal phases in periodic sequential order [19]. Sinceround robin schedules the traffic in a fixed control manner, ignoring the real-time traffic demand, it should perform the worst in unbalanced traffic. The results are compared with two criterions:(i)
the average traveling time for each vehicle to go through the transportation network;(ii)
the average number of waiting vehicles in front of intersections.


### 7.1. Traffic Control with Green-Wave Effect

When the traffic is sparse, the green-waved effect is the most straightforward way to test intelligent traffic control performance [20]. Therefore, we initialized a 5×5 grid transportation network and 10 vehicles are randomly generated from the margin of this network to get through under the three control schemas. The experimental results are shown in Figure 9. When there are only few vehicles in the network, inRound Robin schema, the vehicle not catching up green light has to wait although no vehicle goes the “green” lane. Because of one time ahead intelligent control,coordinate intelligent is easier to create the green wave effect that allows the coming vehicles to get through the intersection without stops. Therefore, both the waiting time and the number of waiting vehicles in thecoordinate intelligent schema are the least in both Figures 9(a) and 9(b).Results of green-wave effect.
(a)
The travelling time of all the vehicles
(b)
The number of waiting vehicles at each time


### 7.2. Traffic Control in Different Traffic Patterns

In urban transportation system, there are two typical traffic patterns [21]. The downtown rush hour emerges in the morning when a lot of vehicles are driven towards the town for work, while the uptown rush hour emerges in the afternoon when massive vehicles go the other way.We test our approach under these two typical traffic patterns. In this experiment, we initialized a5×5 grid network. In the downtown traffic pattern, we simulated 500 vehicles, which are evenly generated from the margin of the network, driving toward downtown within the initial 10 time steps, and as shown in Figure 10(a), the number of waiting vehicles reaches a peak between time steps 10 and 20 as they overload the intersections in the grid. Each traffic control schema is applied to route traffic to their destination and decrease the waiting traffics. Traditionalround robin way, which only works well in handling balanced traffic, has a poor performance in responding to the unbalanced traffic. As expected, with the one time ahead intelligent control, our approach performs best to have the mainstream traffic flows get through the intersections quickly. Both the average traveling time of those vehicles and the number of waiting vehicles in this schema stay the least as shown in Figure 10(b). In the next section, we also simulated 500 vehicles in an uptown traffic pattern, evenly generated from downtown, driving to spread out of the network. Similar to Figures 10(a) and 10(b), our schema works best in Figures 10(c) and 10(d).Results in two typical traffic patterns.
(a)
The number of waiting traffic in downtown traffic pattern
(b)
Travelling time in uptown traffic pattern
(c)
The number of waiting traffic in uptown traffic pattern
(d)
Travelling time in uptown traffic pattern
(e)
Travelling time of vehicles going against mainstream downtown traffic pattern
(f)
Travelling time of vehicles going against mainstream in uptown traffic patternSince the intelligent traffic control should always try to have the mainstream traffic flows go through the intersections with high priorities, we test whether this is the case in our design. In the two traffic patterns, we put 10 vehicles to be driven against the mainstream. Figure10(e) shows the average traveling time of the 10 vehicles to go uptown while there are 500 vehicles going downtown. Figure 10(f) shows the result of the 10 vehicles to go downtown while the 500 vehicles are going uptown. As expected, to evacuate the heavy traffic, bothlocal intelligent andcoordinate intelligent schemas have to give higher priorities to the mainstream and sacrifice the minority from the other direction. Therefore, as Figures 10(e) and 10(f) indicate, it costs more traveling time for the 10 vehicles to get through the network. Besides, the results also show that the evacuation ability ofcoordinate intelligent is higher thanlocal intelligent.


### 7.3. Traffic Control in Different Network Scales

In order to test the scalability of our intelligent control, we perform experiments in different scales of transportation networks. We initialized 500 vehicles in the network with two traffic patterns described in Section7.2. As shown in Table 1, when the scale of the network increases, it takes the vehicles more time to travel through this network. Due to the intelligent traffic control of our approach, it outperforms the other schemas.Table 1
The average traveling time of different traffic controls in different network scales.
Scale
Coordinate intelligent
Local intelligent
Round robin
Downtown traffic pattern
5
×
5
150.3
155.7
177.1
6
×
6
165.5
182.1
210.1
7
×
7
183.9
195.0
237.9
8
×
8
216.5
219.0
255.0
9
×
9
219.5
233.4
295.1
10
×
10
241.8
252.8
327.0
Uptown traffic pattern
5
×
5
121.7
146.9
166.6
6
×
6
177.0
206.4
236.0
7
×
7
195.5
237.7
269.6
8
×
8
257.7
298.9
336.7
9
×
9
288.1
334.2
394.2
10
×
10
359.6
401.2
478.2


### 7.4. Traffic Control in Different Traffics

In this section, we test our approach with different number of traffics. We initialized a5×5 grid network with 500 to 2500 vehicles to go through. As shown in Table 2, in two typical traffic patterns, heavy traffic is more likely to cause congestions with longer average traveling time for each vehicle. However, our approach performed best.Table 2
The average traveling time of different traffic controls with different number of vehicles.
Vehicle number
Coordinate intelligent
Local intelligent
Round robin
Downtown traffic pattern
500
149.7
160.3
175.7
1000
179.7
186.6
208.3
1500
222.6
230.2
240
2000
243.1
257.1
270.1
2500
241.4
281.1
293.9
Uptown traffic pattern
500
128.7
142.5
167.3
1000
138.8
181.9
221.2
1500
164.1
219.9
277.9
2000
180.4
240.9
328.7
2500
201.8
280.9
382.6


## 7.1. Traffic Control with Green-Wave Effect

When the traffic is sparse, the green-waved effect is the most straightforward way to test intelligent traffic control performance [20]. Therefore, we initialized a 5×5 grid transportation network and 10 vehicles are randomly generated from the margin of this network to get through under the three control schemas. The experimental results are shown in Figure 9. When there are only few vehicles in the network, inRound Robin schema, the vehicle not catching up green light has to wait although no vehicle goes the “green” lane. Because of one time ahead intelligent control,coordinate intelligent is easier to create the green wave effect that allows the coming vehicles to get through the intersection without stops. Therefore, both the waiting time and the number of waiting vehicles in thecoordinate intelligent schema are the least in both Figures 9(a) and 9(b).Results of green-wave effect.
(a)
The travelling time of all the vehicles
(b)
The number of waiting vehicles at each time


## 7.2. Traffic Control in Different Traffic Patterns

In urban transportation system, there are two typical traffic patterns [21]. The downtown rush hour emerges in the morning when a lot of vehicles are driven towards the town for work, while the uptown rush hour emerges in the afternoon when massive vehicles go the other way.We test our approach under these two typical traffic patterns. In this experiment, we initialized a5×5 grid network. In the downtown traffic pattern, we simulated 500 vehicles, which are evenly generated from the margin of the network, driving toward downtown within the initial 10 time steps, and as shown in Figure 10(a), the number of waiting vehicles reaches a peak between time steps 10 and 20 as they overload the intersections in the grid. Each traffic control schema is applied to route traffic to their destination and decrease the waiting traffics. Traditionalround robin way, which only works well in handling balanced traffic, has a poor performance in responding to the unbalanced traffic. As expected, with the one time ahead intelligent control, our approach performs best to have the mainstream traffic flows get through the intersections quickly. Both the average traveling time of those vehicles and the number of waiting vehicles in this schema stay the least as shown in Figure 10(b). In the next section, we also simulated 500 vehicles in an uptown traffic pattern, evenly generated from downtown, driving to spread out of the network. Similar to Figures 10(a) and 10(b), our schema works best in Figures 10(c) and 10(d).Results in two typical traffic patterns.
(a)
The number of waiting traffic in downtown traffic pattern
(b)
Travelling time in uptown traffic pattern
(c)
The number of waiting traffic in uptown traffic pattern
(d)
Travelling time in uptown traffic pattern
(e)
Travelling time of vehicles going against mainstream downtown traffic pattern
(f)
Travelling time of vehicles going against mainstream in uptown traffic patternSince the intelligent traffic control should always try to have the mainstream traffic flows go through the intersections with high priorities, we test whether this is the case in our design. In the two traffic patterns, we put 10 vehicles to be driven against the mainstream. Figure10(e) shows the average traveling time of the 10 vehicles to go uptown while there are 500 vehicles going downtown. Figure 10(f) shows the result of the 10 vehicles to go downtown while the 500 vehicles are going uptown. As expected, to evacuate the heavy traffic, bothlocal intelligent andcoordinate intelligent schemas have to give higher priorities to the mainstream and sacrifice the minority from the other direction. Therefore, as Figures 10(e) and 10(f) indicate, it costs more traveling time for the 10 vehicles to get through the network. Besides, the results also show that the evacuation ability ofcoordinate intelligent is higher thanlocal intelligent.


## 7.3. Traffic Control in Different Network Scales

In order to test the scalability of our intelligent control, we perform experiments in different scales of transportation networks. We initialized 500 vehicles in the network with two traffic patterns described in Section7.2. As shown in Table 1, when the scale of the network increases, it takes the vehicles more time to travel through this network. Due to the intelligent traffic control of our approach, it outperforms the other schemas.Table 1
The average traveling time of different traffic controls in different network scales.
Scale
Coordinate intelligent
Local intelligent
Round robin
Downtown traffic pattern
5
×
5
150.3
155.7
177.1
6
×
6
165.5
182.1
210.1
7
×
7
183.9
195.0
237.9
8
×
8
216.5
219.0
255.0
9
×
9
219.5
233.4
295.1
10
×
10
241.8
252.8
327.0
Uptown traffic pattern
5
×
5
121.7
146.9
166.6
6
×
6
177.0
206.4
236.0
7
×
7
195.5
237.7
269.6
8
×
8
257.7
298.9
336.7
9
×
9
288.1
334.2
394.2
10
×
10
359.6
401.2
478.2


## 7.4. Traffic Control in Different Traffics

In this section, we test our approach with different number of traffics. We initialized a5×5 grid network with 500 to 2500 vehicles to go through. As shown in Table 2, in two typical traffic patterns, heavy traffic is more likely to cause congestions with longer average traveling time for each vehicle. However, our approach performed best.Table 2
The average traveling time of different traffic controls with different number of vehicles.
Vehicle number
Coordinate intelligent
Local intelligent
Round robin
Downtown traffic pattern
500
149.7
160.3
175.7
1000
179.7
186.6
208.3
1500
222.6
230.2
240
2000
243.1
257.1
270.1
2500
241.4
281.1
293.9
Uptown traffic pattern
500
128.7
142.5
167.3
1000
138.8
181.9
221.2
1500
164.1
219.9
277.9
2000
180.4
240.9
328.7
2500
201.8
280.9
382.6


## 8. Conclusion and Future Work

In this paper, we presented a multiagent based decentralized traffic light coordination approach for large urban transportation system. In order to improve the control efficiency, we use the prospection of local state one time ahead to make rational decision and build a two-level multiagent architecture and intelligent traffic control algorithms to coordinate these agents. Experiments manifest that our approach is feasible and scalable to improve the decentralized traffic control efficiency.Although we are capable of dealing with some of the challenges, we leave many of the others in the future. Firstly, in our model we primarily considered video cameras as input sensors; however, more sensors should be considered as valuable inputs. Although those sensors are helpful to refine the model, as a challenge, they may also bring heavy computation. Secondly, traffic flow estimation methods should be polished to improve the efficiency. Moreover, deployment in real domain is the key to evaluate our approach.



---

*Source: 104349-2014-07-15.xml*