Source-linked AI summary
Capacity-aware back-pressure traffic signal control
Jean Gregoire, Xiangjun Qian, Emilio Frazzoli, Arnaud de La Fortelle, Tichakorn Wongpiromsarn
TL;DR
Back-pressure control assumes unbounded queues, whereas real finite capacities can cause pressure saturation, non-work-conservation, and congestion propagation. This paper introduces capacity-aware normalized pressures that account for queue capacities while retaining distributed O(1) control. The method is proved to ensure work conservation and simulations indicate improved performance under bounded queues, although congestion necessarily propagates above the network’s capacity region.
Problem
Back-pressure control assumes unbounded queue capacities, but finite capacities can cause pressure saturation, loss of work conservation, and congestion propagation.
Method
The paper normalizes node pressures using queue capacities so full queues exert the same maximal pressure independently of capacity.
Results
Normalized pressure functions are proved to ensure work conservation, and simulations confirm improved performance under bounded queue constraints while preserving distributed control and O(1) complexity.
Takeaways & Limitations
Capacity-aware back-pressure retains back-pressure’s distributed and O(1) implementation benefits while addressing finite-capacity congestion effects.
Takeaways & Limitations
Above the network’s capacity region, congestion eventually propagates and controlling interactions across congested junctions has exponential complexity.
Abstract
from arXiv · showhide
The control of a network of signalized intersections is considered. Previous work demonstrates that the so-called back-pressure control provides stability guarantees, assuming infinite queues capacities. In this paper, we highlight the failing of current back-pressure control under finite capacities by identifying sources of non work-conservation and congestion propagation. We propose the use of a normalized pressure which guarantees work conservation and mitigates congestion propagation, while ensuring fairness at low traffic densities, and recovering original back-pressure as capacities grow to infinity. This capacity-aware back-pressure control allows to improve performance as congestion increases, as indicated by simulation results, and keeps the key benefits of back-pressure: ability to be distributed over intersections and O(1) complexity.
I. INTRODUCTION
Signalized-intersection networks require adaptive control to respond to changing traffic, while back-pressure control offers reactive, distributed operation but assumes unbounded queues. This paper models finite-capacity queues and proposes normalized pressures to retain back-pressure’s scalability while addressing blocking and congestion propagation.
- Motivation: Traffic signals coordinate conflicting vehicle flows by selecting feasible phases over time.Adaptive control is needed because changing arrival rates make fixed schedules inefficient.
- Existing control: Back-pressure uses current queue lengths to select phases reactively and provides stability guarantees under its queue-capacity assumptions.Its control law is based on feedback rather than a fixed schedule.
- Problem: Finite queues can cause blocking when upstream queues fill, allowing congestion to propagate and potentially create deadlocks.Current back-pressure algorithms assume unbounded queue capacities.
- Proposed direction: Normalized pressures make full queues exert the same maximal pressure regardless of capacity, while preserving distributed control and O(1) complexity.The normalization is intended to decrease blocking probability.
- Model: The network is represented as a directed queuing graph whose links are partitioned among signalized junctions and whose nodes maintain routed vehicle queues.This overlays junction structure onto a standard queuing-network model.
B. Arrival and routing processes
Vehicles enter nodes through exogenous arrivals and move through the network through endogenous transfers. Routing ratios describe the long-term fractions assigned to destination queues, with departures represented by the residual rate.
- Arrivals: Exogenous arrivals A_a(k) enter node N_a during time slot k and are not controlled.The arrival process is assumed rate-convergent with long-term rate λ_a.
- Transfers: Endogenous transfers move vehicles between nodes through network links during each slot.The transfer quantity is denoted f_ca(k) for vehicles moving from N_c to N_a.
- Routing: Routing ratio r_ab specifies the long-term fraction of vehicles entering N_a that are assigned to queue Q_ab, while the residual represents exits from N_a.Routing ratios need not sum to one because some vehicles leave the network.
C. Phase-based control
Signal control selects feasible phases that determine service between input and output nodes. Transfers are constrained both by vehicles available at slot start and by downstream capacity, which can block movement into full nodes.
- Phase selection: Each signalized junction activates one phase from a finite set of feasible phases during each time slot.A global phase combines the selected local phase at every junction.
- Service: When phase p_i is active, μ_ab(p_i) specifies the maximum vehicles transferable from N_a to N_b during that slot.Different global phases produce different service vectors.
- Transfer constraints: Only vehicles present at a queue at the beginning of a slot can leave during that slot, and full downstream nodes cannot accept additional vehicles.These two constraints limit actual transfers even when a phase grants right-of-way.
III. FAILING OF BACK-PRESSURE CONTROL UNDER BOUNDED QUEUES CONSTRAINTS
Under bounded queues, conventional back-pressure computes phases from queue-based pressure differences but can lose its key guarantees because linear pressures saturate at capacity-dependent levels.
- Back-pressure selects each junction’s phase from current queue lengths through a feedback control law.The control maps the network state to a phase at every time slot.
- Back-pressure requires only aggregated queue lengths and binary vehicle-presence indicators, supporting distributed implementation with O(1) complexity.The method is also associated with stability optimality under infinite capacities.
- The algorithm computes input and output pressures, nonnegative pressure differences, and phase-specific weighted pressure release before selecting the maximizing phase.With linear pressures, a node’s pressure equals its queue length; vehicle-presence indicators gate candidate flows.
- With bounded queues and linear pressure functions, pressure saturates at different capacity-dependent levels, which can cause loss of work conservation and congestion propagation.This is the central failure mechanism examined under finite capacities.
B. Loss of work conservation
With bounded queues, conventional back-pressure is not work-conserving in general: it may select a blocked phase even when another feasible phase could serve vehicles.
- A control is work-conserving when any available input-to-output transfer with downstream space ensures that the junction works.Loss of work conservation indicates inefficiency.
- Under bounded queues, back-pressure is not work-conserving in the general case.This result is stated as Theorem 1.
- When the selected downstream queue is full, back-pressure can choose a phase whose transfers are infeasible even though another feasible phase would enable service.In the example, phase pab is selected while phase pcd would have allowed the server to work.
- The failure arises because linear pressure functions compare capacity-saturated pressures without accounting for whether the selected transfer can actually enter a full downstream queue.The figure illustrates this loss of work conservation under linear pressure functions.
- The resulting inefficiency can initiate congestion propagation.The paper identifies this consequence immediately after establishing the loss of work conservation.
C. Congestion propagation and deadlocks
Loss of work conservation can propagate congestion through neighboring nodes and, in the worst case, produce deadlocks under back-pressure control.
- Congestion may propagate both to a node that has right-of-way but cannot empty because of downstream congestion and to a node without right-of-way.The two propagation paths arise from the same loss of work conservation.
- When Nb is full, fab(k) becomes zero, so Na is not emptied; Nc is also not emptied because the selected phase gives it no right-of-way.The figure example therefore shows congestion spreading to both Na and Nc.
- In the worst case, congestion propagation can lead to deadlocks.The paper depicts this outcome in Figure 6.
- Normalized pressures are proposed to enforce work conservation and mitigate congestion propagation under limited queue capacities.The approach is intended to address the propagation mechanism described in this section.
1) Purpose of a convex pressure:
The paper motivates convex, capacity-aware pressure functions to reflect increasing congestion costs, normalize full queues, preserve fairness at low density, and recover back-pressure behavior as capacities grow.
- Convex pressure makes each additional vehicle increasingly consequential as a node approaches full occupancy.The marginal pressure rises with queue size.
- Normalized pressures assign maximal pressure to full queues and zero pressure to empty queues, preventing unusable downstream links from attracting flow.A full downstream node cannot accept additional vehicles, so upstream pressure differences must not favor that link.
- Relative pressure Qa/Ca is insufficient because it is not strictly convex and gives smaller-capacity nodes larger marginal pressure at low density.The proposed normalization is therefore more complex than simple capacity scaling.
- Fairness requires uniform marginal pressure across nodes at low traffic density, while infinite-capacity recovery requires pressure to be linear when Qa/Ca approaches zero.Under these conditions, normalized control recovers original back-pressure when queues remain far below capacity.
- The paper proposes a convex normalized pressure satisfying capacity awareness, low-density fairness, and asymptotic recovery of back-pressure.These criteria define the pressure design developed in the following section.
B. Example of normalized pressure
The example pressure is linear at low occupancy, convex as occupancy rises, and normalized to one above the congestion threshold; the resulting control is work-conserving under stated assumptions.
- B. Example of normalized pressure: At low occupancy, the proposed pressure is linear, supporting fairness and the stability requirement associated with back-pressure.It is approximately Qa/C∞ in this regime.
- B. Example of normalized pressure: The pressure function is convex, so its slope increases as occupancy grows, and it equals 1 whenever Qa is at least Ca.The congestion threshold determines where pressure becomes normalized.
- B. Example of normalized pressure: The parameters m and C∞ control the transition from linear behavior and the low-occupancy slope, under capacities below C∞ and m greater than 1.A node with capacity C∞ has linear pressure.
- C. Work-conservation: Normalized pressure ensures work conservation by resolving the deadlock illustrated in Figure 8.The paper then proves work conservation under convex normalized pressure.
- C. Work-conservation: Under increasing pressures in [0,1], Pa(0)=0, Pa(Ca)=1, and the specified tie-breaking rule, normalized back-pressure is work-conserving.The theorem assumes ties favor phases with available upstream vehicles and downstream space.
- C. Work-conservation: The proof argues that any selected phase that idles despite an available feasible movement would have zero pressure weight, so the feasible phase should be selected instead.The tie-breaking condition handles the equality case.
V. SIMULATION RESULTS
The simulation section compares capacity-aware back-pressure with current back-pressure and a non-optimized fixed-cycle traffic light.
- The evaluation compares capacity-aware back-pressure, current back-pressure, and a non-optimized fixed-cycle traffic light.The fixed-cycle controller serves as a reference.
A. Simulation setup
The simulations use SUMO on a non-uniform bidirectional road network with varied intersection types and traffic scenarios, implementing three controllers with matched random seeds.
- A. Simulation setup: The experiments use SUMO, a microscopic, inter- and multi-modal, space-continuous, time-discrete traffic simulator.The control schemes interact with SUMO through real-time queue measurements and traffic-light updates.
- A. Simulation setup: The simulated network is non-uniform, bidirectional, and contains roads with one or two lanes plus dedicated left-turn lanes.These lane differences produce four intersection types.
- A. Simulation setup: Traffic flows are generated with ActivityGen using city population, spatial population distribution, working zones, and peak-period patterns.The scenario places habitation in the northern area and work zones in the southern area.
- A. Simulation setup: The implementation compares current back-pressure, capacity-aware back-pressure, and a reference fixed-cycle controller using queue measurements from loop detectors.Capacity is computed from lane length, vehicle length, and minimum gap; a lane capacity equals its length divided by 7.5.
- A. Simulation setup: Each complete test run evaluates the three controllers under four populations while using the same ActivityGen random seed for comparability.The population is the varied experimental condition.
B. Results and analysis
Capacity-aware back-pressure improves performance as traffic load increases while preserving distributed control and O(1) complexity. Its benefits are limited when arrival rates exceed the network’s capacity region, and future performance depends on driver-routing feedback.
- Performance under increasing load: For populations of 33000 and 39000, capacity-aware back-pressure outperforms standard back-pressure, whereas their performance is similar at 27000.At 10000, all schemes perform similarly; both back-pressure schemes outperform fixed-cycle control at 27000.
- Mechanism and congestion: Normalized pressure functions ensure work-conservation and tend to mitigate congestion propagation under bounded queue capacities.The approach addresses pressure saturation at queues that have reached maximum capacity.
- Preserved properties: The capacity-aware approach preserves distributed control over junctions and O(1) complexity.These are identified as key properties of back-pressure control.
- Limitations: Above the capacity region, congestion will eventually propagate through the network, creating congested areas where group-based junction control may be needed.Interactions among blocked junctions make such control exponentially complex.
- Future perspectives: Future back-pressure research should account for driver routing responses to traffic-signal decisions because these responses may stabilize or destabilize the queuing network.The relevant feedback loop concerns routing choices influenced by right-of-way decisions.