Source-linked AI summary
Decentralized Signal Control for Urban Road Networks
Tung Le, Peter Kovacs, Neil Walton, Hai L Vu, Lachlan L Andrew, Serge S Hoogendoorn
TL;DR
Urban traffic congestion creates a need for more efficient and scalable signal control, while many existing optimization methods are centralized. This paper proposes a decentralized cyclic-phase BackPressure policy with estimated turning fractions, proves stability for feasible demands, and finds favorable throughput and congestion performance against distributed alternatives.
Problem
Urban congestion motivates efficient signal control, but many existing optimization approaches are centralized and decentralized methods need stronger scalability and stability evidence.
Method
The paper adapts BackPressure into a decentralized fixed-cycle policy with cyclic phases, local queue information, and online unbiased estimation of turning fractions.
Results
The proposed policy is reported to stabilize the network for the largest possible set of feasible arrival rates and to tend to outperform other distributed policies in throughput and congestion.
Takeaways & Limitations
Cyclic-phase BackPressure provides a decentralized traffic-signal strategy that preserves stability while ensuring predictable phase ordering and service for every phase.
Takeaways & Limitations
The analysis does not consider non-constant switching times, finite link travel times, or link capacities.
Abstract
from arXiv · showhide
We propose in this paper a decentralized traffic signal control policy for urban road networks. Our policy is an adaptation of a so-called BackPressure scheme which has been widely recognized in data network as an optimal throughput control policy. We have formally proved that our proposed BackPressure scheme, with fixed cycle time and cyclic phases, stabilizes the network for any feasible traffic demands. Simulation has been conducted to compare our BackPressure policy against other existing distributed control policies in various traffic and network scenarios. Numerical results suggest that the proposed policy can surpass other policies both in terms of network throughput and congestion.
1. Introduction
Urban congestion motivates scalable traffic-signal control, but many optimization approaches are centralized and lack formal stability guarantees. The paper adapts BackPressure to decentralized road networks with cyclic phases, estimated turning fractions, and provable stability, then evaluates it against distributed alternatives.
- Motivation: Centralized signal-optimization methods are often not scalable, motivating decentralized approaches that retain performance while improving scalability.The paper focuses exclusively on decentralized schemes as a path toward performance comparable with centralized techniques.
- Prior work: BackPressure requires no a priori traffic-demand knowledge, has provable stability under simplifying assumptions, and admits a simple distributed road-network implementation.A feasible traffic load is one for which some intersection splits prevent queues from building indefinitely.
- Contribution: The proposed strategy adapts BackPressure to traffic control while addressing weaknesses in prior road-network applications and retaining its stability property.The paper targets decentralized control for better infrastructure utilization and traffic-flow efficiency.
- Contribution: Cyclic phases replace erratic phase ordering by allocating strictly positive service time to every phase, reducing starvation concerns and making the sequence predictable.The authors motivate predictability for drivers and note that heavily backlogged roads could otherwise starve other roads.
- Contribution: Any unbiased estimator of turning fractions suffices for the proposed stability results, although the proofs use idealized assumptions and a general network model.This removes the requirement that each intersection know exact turning fractions in advance.
- Evaluation: Simulations compare the proposed policy with distributed alternatives across traffic and network settings, with performance varying by cycle length and decision frequency.Under optimal settings among the studied cases, cyclic and non-cyclic BackPressure achieved better throughput than the other policies.
- Results: The theoretical results interpret the policy as stabilizing the largest possible set of arrival rates, providing sufficient throughput for feasible demands.The paper presents stability results after introducing the queue-dynamics model and proposed policy.
2. Cyclic Phase BackPressure Traffic Signal Control
The policy models urban intersections with discrete cycles, queue measurements, service phases, stochastic turning, and external arrivals. It estimates turning fractions and allocates every phase positive green time, while assigning larger shares to phases with greater BackPressure weights.
- Network model: A service phase is a combination of in-roads served simultaneously, represented by service rates that are positive for green approaches and zero otherwise.Each junction has a set of available service phases.
- Network model: The model uses links to represent possible movements from an in-road at one junction to an in-road at a neighboring junction.In-roads can represent one or more lanes, including lanes with different turning options.
- Cycle structure: All junctions share a common cycle length, and each phase must receive non-zero service time within the next cycle.Allocated phase times cannot exceed the cycle after accounting for the model’s lost-time constraint.
- Queue information: Control decisions use measured queue lengths, which may differ from actual queues by bounded errors independent of the queues and other in-roads.Queue length denotes cars present at the beginning of each traffic cycle.
- Traffic dynamics: Traffic movements use turning proportions between linked in-roads, assumed time-independent and unaffected by observed queue lengths.The model treats cars within an in-road as homogeneous with respect to subsequent-junction choices.
- Traffic dynamics: External arrival rates may vary over time, allowing the model to represent changing traffic demand over the course of a day.Static arrival rates are a special case of the time-varying formulation.
- Policy: The policy estimates turning fractions online, computes phase weights from measured queues and estimates, and assigns cycle proportions to phases using those weights.The procedure forms unbiased estimates, calculates phase weights, and allocates the next cycle accordingly.
- Policy: BackPressure weights represent pressure from queues on downstream queues, so higher-weight phases receive larger green-time proportions while every phase remains served.Unlike highest-weight-only BackPressure, the proposed distribution is decentralized after junctions communicate queue sizes.
3. Mathematical Results - Stability of Cyclic Phase BackPressure Control Policy
The stability region A characterizes arrival rates that can be supported under the network’s service and switching constraints. Rates outside its closure are unstable under any policy, while the proposed policy is stable throughout A under the theorem’s conditions.
- 3.1. Stability Region and Queueing Stability: The stability region A consists of arrival rates compatible with feasible service proportions and departure rates under the network constraints.These constraints require accumulated arrivals to remain below potential departures, reserve time for switching and setup, and keep departures within allocated service rates.
- 3.2. Main Theoretical Results: Under independent identically distributed arrivals, any rate vector outside the closure of A is unstable under every policy.This establishes the outer boundary of what any control policy can stabilize.
- 3.2. Main Theoretical Results: If each cycle’s mean arrival rate remains ε inside A, Theorem 1 bounds the long-run average queue sizes and establishes stability.The result applies when there exists ε > 0 such that the cycle-specific mean arrival vector plus ε1 belongs to A.
- 3.2. Main Theoretical Results: The proposed policy is stable for the largest possible set of arrival rates and provides sufficient throughput whenever the network’s capacities permit it.The theorem also applies to time-varying traffic levels.
- 3.2. Main Theoretical Results: The peak-hour interpretation requires queues to remain stable even if peak demand continues indefinitely, which is stricter than long-term stability with post-peak clearing.Queues may instead build during a peak and empty afterward while remaining stable over the long term.
4. Numerical Results - Performance Evaluation and Design
The evaluation compares decentralized signal-control policies in small and large networks under varied cycle-time or decision-frequency settings. Cyclic-phase BackPressure generally achieves the strongest throughput and congestion performance, while parameter choice materially affects outcomes.
- Simulation settings: The simulations compare cyclic-phase BackPressure, standard BackPressure, proportional, and greedy decentralized policies in small and large networks.SUMO is used for a two-intersection network and a Melbourne CBD network with about 70 intersections.
- Small network results: In the small network, cyclic-phase BackPressure produces fewer total vehicles and higher throughput by reducing East-West green time when bottleneck link 3 is congested.This allocates more service to North-South traffic and reduces the impact of spillback from the second junction.
- Large network results: Cyclic-phase BackPressure has the lowest vehicle count and highest throughput in the large network, followed by standard BackPressure.Both BackPressure policies outperform proportional and greedy control under heavy congestion by accounting for downstream queue lengths.
- Large network results: BackPressure reduces congested links significantly in the large network, with cyclic-phase BackPressure included among the strongest-performing policies.A link is classified as congested when its queue exceeds 85% of capacity.
- Parameter design: The optimal setting differs by policy in the larger parameter study: proportional uses a 60-second cycle, while the other policies use 30 seconds.Non-optimal cycle lengths or decision frequencies increase congestion, and the cyclic-phase BackPressure policy performs especially well at 30 seconds.
5. Conclusion
The paper proposes a decentralized cyclic-phase BackPressure signal strategy using local queue information and evaluates it against distributed policies. Simulations indicate competitive or superior throughput and congestion performance, while several traffic-network factors remain for future work.
- Contribution: The proposed strategy uses decentralized BackPressure control based only on queue-size information local to each intersection.It uses cyclic phases and does not require prior traffic-demand knowledge or local turn-ratio knowledge.
- Contribution: Nonzero service time is allocated to every phase within each cycle, avoiding the erratic phase order associated with some existing BackPressure policies.The cyclic operation is intended to address potential unsafe operation from unpredictable phase ordering.
- Evaluation: Simulation compared cyclic-phase BackPressure with other distributed policies using small and large network topologies with fixed routings.The evaluation considered network throughput and congestion level.
- Results: Under the optimal settings studied, cyclic and non-cyclic BackPressure achieved better throughput than the other policies.Performance varied widely with parameters such as cycle length and decision frequency.
- Limitations: Non-constant switching times, finite link travel time, and link capacity were not considered and remain subjects for future work.These omissions define important boundaries on the reported evaluation and model.
Appendix A. Estimation of Turning Fractions
The appendix addresses estimation of traffic turning fractions, which previous BackPressure studies treated as known or precomputed. It proposes locally calculated flow information and requires an unbiased estimate under stated independence conditions.
- Motivation: Previous BackPressure studies assumed traffic turning fractions were explicitly known or calculated before policy implementation.The appendix identifies their estimation as an unresolved aspect of prior applications.
- Estimation method: Turning fractions can be estimated from recent locally calculated traffic-flow information over the last k service cycles.The proposed estimator uses measurements from recent service history.
- Estimation method: When turning fractions are stationary and independent of queue sizes, zero-mean measurement error yields an unbiased estimate of underlying turning probabilities.If the queue is empty, any estimate may be used to define the turning fraction.
- Assumptions: Historical or recent-data rules are acceptable when the estimate is unbiased and independent of the queue state history.The proportions may change on a larger time scale, and the estimate may be inconsistent, under these conditions.
Appendix B. Proof of the main stability result
This appendix introduces the assumptions and technical lemmas used to prove the paper’s main stability theorem. The proof relies on supplementary results including Proposition 1.
- Proof strategy: The proof of Theorem 1 begins by clarifying stochastic-model assumptions and technical lemmas.The technical lemmas and Proposition 1 are provided in a supplementary document.
Appendix B.1. Assumptions
The stability analysis imposes bounded service, stationary and queue-independent turning fractions, an invertibility condition, state-independent arrivals, and bounded queue-measurement error.
- Assumptions: The number of cars served from any in-road during one traffic cycle is bounded.This bounds per-cycle service in the stochastic model.
- Assumptions: Turning fractions are stationary and independent of queue lengths and previously served cars, and I − p̄ is invertible.These conditions support the model’s traffic-flow relationships.
- Assumptions: Arrivals are independent of the queue state, allowing average arrival rates into each junction to be defined.The assumption applies to the arrival process across time.
- Assumptions: Queue-size measurement error δ(t) is assumed to be bounded.The proof therefore excludes unbounded measurement-error behavior.
Appendix B.2. Lemmas
Appendix B.2 develops auxiliary lemmas that bound measurement-error effects, queue-weight changes, and optimization expressions used in the later stability proofs.
- Measurement error: Measurement-error lemmas relate the difference between true and measured queue weights to the error in measurement.The proof identifies weight differences caused by measurement error and derives bounds used repeatedly later.
- Auxiliary bounds: The lemmas establish bounds on queue-size increments and their conditional expectations.These bounds support subsequent arguments about the queue process and its weights.
- Queue threshold: A queue-size threshold K1 separates the empty-history case from queues large enough for conditional-expectation arguments.When queues are sufficiently large, Qi(t) can be taken outside the conditional expectation because it is known.
- Algebraic rearrangement: Lemma 6 reorders summations from in-roads to junctions and schedules, then collects terms by in-road.The rearrangement makes the later weight calculations more concise.
- Optimization bounds: Additional lemmas bound an optimization problem using vector inequalities, the positive inverse (I − ¯p)−1, convex combinations, and minimax ordering.The arguments also use entropy maximization by the uniform distribution to bound expected weights.
Appendix B.3. Proofs
Appendix B.3 proves that arrival rates outside the stability region make the road network unstable under every policy.
- Instability outside ¯A: Arrival rates outside the stability region ¯A imply the existence of a positive slack ǫ in the feasibility inequalities.The proof begins by selecting ǫ > 0 whenever ¯a /∈ ¯A.
- Instability outside ¯A: For any policy, long-run queue growth is determined by average arrivals minus average departures.The proof considers average service and departures for each queue and uses a suitable subsequence.
- Instability outside ¯A: At least one queue is unstable because the limiting queue-size terms are positive and one exceeds ǫ.This establishes a queue that eventually remains above a growing lower bound.
- Instability outside ¯A: Taking expectations yields network instability for arrival rates outside ¯A.The conclusion applies regardless of the policy considered.
Appendix B.4. Formal proof of Theorem 1
Appendix B.4 proves the main theorem by combining queue-distance bounds, weight bounds, measurement-error control, and earlier propositions.
- Theorem 1 proof: The proof of Theorem 1 starts from Proposition 2 and Lemma 3 to bound changes in the queue-size distance from zero.The argument takes expectations after applying the preceding bounds.
- Theorem 1 proof: A bound on wσ(Q(t)) controls the key weight term appearing in the proof.Proposition 2 supplies a constant K∗ for this purpose.
- Theorem 1 proof: The derivation expands the queue recursion using Lemmas 4 and 5, reorders summations using Lemma 6, and bounds measurement-error terms.The constant ˜K is introduced during the expansion, and the extra error term is incorporated into K∗.
- Theorem 1 proof: The preceding proposition provides the final ingredient for proving the paper’s main mathematical result, Theorem 1.The appendix explicitly transitions from Proposition 2 to the theorem proof.