A Market-Inspired Approach for Intersection Management in Urban Road Traffic Networks

Matteo Vasirani; Sascha Ossowski

Source-linked AI summary

A Market-Inspired Approach for Intersection Management in Urban Road Traffic Networks

Matteo Vasirani, Sascha Ossowski

arXiv:1401.5851v1Jan 23, 2014cs.GTcs.MA

TL;DR

Urban congestion motivates decentralised ITS mechanisms for autonomous vehicles interacting with intelligent infrastructure. The paper extends reservation-based intersection control with combinatorial auctions, competitive traffic assignment, and an adaptive combination of both. High-value bidders experience about 30% lower individual delays, while the integrated network strategy produces more balanced traffic and lower average travel times.

Problem
Urban traffic congestion motivates more efficient management of existing road networks through decentralised intelligent transportation systems.
Method
The paper combines combinatorial-auction reservation allocation at intersections with competitive, demand-adaptive traffic assignment across intersection networks.
Results
High-value bidders experienced about 30% lower individual delays than low-value bidders, while the integrated strategy generated a more balanced network and lower average travel times.
Takeaways & Limitations
Market-inspired control can allocate intersection resources according to drivers’ valuations while distributing traffic more evenly across the network.
Takeaways & Limitations
The auction raises a fairness concern because richer drivers may travel faster than poorer drivers on public infrastructure, and Walrasian auctions rely on strict assumptions difficult to implement in traffic.

Abstract

from arXiv · show

Traffic congestion in urban road networks is a costly problem that affects all major cities in developed countries. To tackle this problem, it is possible (i) to act on the supply side, increasing the number of roads or lanes in a network, (ii) to reduce the demand, restricting the access to urban areas at specific hours or to specific vehicles, or (iii) to improve the efficiency of the existing network, by means of a widespread use of so-called Intelligent Transportation Systems (ITS). In line with the recent advances in smart transportation management infrastructures, ITS has turned out to be a promising field of application for artificial intelligence techniques. In particular, multiagent systems seem to be the ideal candidates for the design and implementation of ITS. In fact, drivers can be naturally modelled as autonomous agents that interact with the transportation management infrastructure, thereby generating a large-scale, open, agent-based system. To regulate such a system and maintain a smooth and efficient flow of traffic, decentralised mechanisms for the management of the transportation infrastructure are needed. In this article we propose a distributed, market-inspired, mechanism for the management of a future urban road network, where intelligent autonomous vehicles, operated by software agents on behalf of their human owners, interact with the infrastructure in order to travel safely and efficiently through the road network. Building on the reservation-based intersection control model proposed by Dresner and Stone, we consider two different scenarios: one with a single intersection and one with a network of intersections. In the former, we analyse the performance of a novel policy based on combinatorial auctions for the allocation of reservations. In the latter, we analyse the impact that a traffic assignment strategy inspired by competitive markets has on the drivers route choices. Finally we propose an adaptive management mechanism that integrates the auction-based traffic control policy with the competitive traffic assignment strategy.

1. Introduction

The paper extends reservation-based intersection control with AI and agent technologies for autonomous vehicles. It studies combinatorial-auction allocation at single intersections and market-inspired traffic assignment across intersection networks.

1. Introduction: The paper extends Dresner and Stone’s reservation-based intersection control to improve its effectiveness and applicability for autonomous vehicles.The approach assumes vehicles can interact with regulating traffic infrastructure.
1. Introduction: At a single intersection, the proposed policy models reservation requests as bids over space-time slots and seeks to maximise the accepted bids’ overall value.The paper adapts winner determination and an auction protocol to real-time and safety constraints.
1. Introduction: For intersection networks, the paper models managers as competitive reservation suppliers whose prices adapt to demand and influence driver route choices.The strategy treats traffic assignment as a distributed choice problem involving selfish driver agents.
1. Introduction: The paper ultimately combines competitive traffic assignment with auction-based intersection control into an adaptive market-inspired traffic-management mechanism.The article therefore addresses both reservation allocation at individual intersections and route distribution across networks.

2. Related Work

Related work covers traffic control, network traffic assignment, and distributed coordination of traffic-management devices. It distinguishes isolated control from coordinated network-level control and notes the difficulty of adapting to changing demand.

2. Related Work: Traffic control regulates access to disputed road resources using signals, detectors, surveillance, and communication devices.Intersection control is a major urban-road measure, while freeway control includes ramp metering and lane management.
2. Related Work: Traditional intersection strategies may optimise offline from historical data, whereas newer methods use real-time traffic volumes to adapt control.TRANSYT is cited as a historical-data strategy, while SCOOT uses real-time traffic volume.
2. Related Work: Traffic assignment distributes demand across a network, but unpredictable demand changes can congest some links while leaving capacity available on alternatives.The problem concerns demands between locations and network capacity.
2. Related Work: Traffic control and traffic assignment can be combined to account for interactions between signal policies and users’ route choices.This links local control decisions with network-level distribution of traffic.
2. Related Work: Coordinated control adapts multiple devices jointly to create smoother network-level flow, using distributed coordination techniques such as DCOP.Mediator agents can resolve conflicts among variables assigned to traffic-signal agents.

2.3 Time Perspective

ITS decision-making is divided into operational, tactical, and strategic time horizons. Existing AI-based systems mainly automate operational control, while some decision-support systems address tactical management and cooperative routing.

2.3 Time Perspective: Operational decisions address short-term intersection control, tactical decisions address medium-term route diversion and demand patterns, and strategic decisions concern long-term infrastructure planning.These levels distinguish when ITS applications make decisions.
2.3 Time Perspective: Many AI-based ITS automate operational road-traffic control, while tactical and strategic decisions remain mainly human activities.Some decision-support systems have begun addressing tactical questions.
2.3 Time Perspective: Cooperative systems support dynamic routing and traffic management by advising drivers and assigning traffic across the network.Collective route choices by selfish agents can nevertheless produce equilibria far from social-welfare optima.
2.3 Time Perspective: Domain and topological knowledge can structure ITS architectures and reasoning models through hierarchical, cooperative multiagent systems.Such systems divide traffic-signal control into subproblems handled by intelligent agents and integrate local strategies into a global plan.

2.6 Learning and Adaptation

Prior ITS research uses learning, self-organisation, and market mechanisms to adapt traffic control and assignment. The paper emphasises decentralised coordination while limiting the domain knowledge required by infrastructure agents.

2.6 Learning and Adaptation: Reinforcement-learning traffic-light agents can use aggregated vehicle waiting times to minimise overall intersection delay through local actions.The learning objective is global even though individual agents act locally.
2.6 Learning and Adaptation: Self-organising traffic lights use local interactions and separate flow and switching rules to produce emergent coordination patterns such as green waves.These mechanisms aim for efficient decentralised traffic-light control without direct communication.
2.6 Learning and Adaptation: Market-based traffic assignment has linked higher intersection-team profit with reduced average travel times, but learning the profit-maximising price vector requires many environmental interactions.The cited approach uses cooperative learning to coordinate prices across intersections.
2.6 Learning and Adaptation: Non-combinatorial auctions can create inefficient reservation assignments because only one bidder can receive a specific earliest time slot.This motivates richer allocation mechanisms for competing driver agents.
2.6 Learning and Adaptation: The paper focuses on operational traffic management and minimises the domain knowledge required to configure its models.Infrastructure agents need awareness of other infrastructure agents but not expert knowledge of the underlying traffic system.

3. Reservation-Based Intersection Control

The reservation-based system uses software agents to schedule vehicles through intersections, with FCFS allocation filtered by reservation distance to limit inefficient or deadlocking requests.

3. Reservation-Based Intersection Control: Intersection managers schedule vehicle crossings, while driver agents autonomously operate vehicles and submit reservation requests containing arrival, lane, speed, and turn information.The protocol uses messages between driver and intersection-manager agents.
3. Reservation-Based Intersection Control: The study uses a deliberately basic reservation system without acceleration, safety buffers, or edge tiles so that allocation policies can be compared fairly.The same basic intersection model is used across experimental scenarios.
3.1 Protocol: FCFS grants conflicting space-time reservations to the first request received, but can reject many compatible vehicles when one early request conflicts with all others.The policy is simple and information-efficient but can be inefficient in extreme request orders.
3.2 Reservation Distance: Without filtering, a following vehicle could reserve disputed slots first, physically block the leading vehicle, and create mutual blockage.The deadlock arises because the leading vehicle cannot cross without its own reservation, while the follower cannot use its reservation behind it.
3.2 Reservation Distance: Reservation distance filters requests using estimated vehicle distance, derived from reported arrival time and speed, to prevent blocking situations from degenerating into deadlocks.The policy maintains a lane-specific maximum request distance and rejects requests beyond it; the heuristic does not guarantee that blocking never occurs.

4. Single Intersection

At a single intersection, reservation allocation can target lower average delay, but drivers’ differing valuations of travel time motivate allocating contested resources by value rather than request order.

4. Single Intersection: Single-intersection control allocates reservations among drivers to maximize an objective such as minimizing average delay.FCFS is the simplest policy for this allocation problem.
4. Single Intersection: Because drivers value travel time and delay differently, an intersection manager may allocate disputed resources to agents that value them most rather than simply serving the first request.The motivation is to account for heterogeneous driver preferences during resource assignment.

4.1 Auction-Based Policy

The auction policy represents reservation requests as bids for conflicting intersection space-time bundles and uses a bounded winner-determination process to select accepted reservations in real time.

4.1.1 Auctioned Resources: The auction allocates intersection space at particular times, representing each reservation request as a bundle of discrete space-time items.Because drivers need bundles rather than isolated items, the allocation is combinatorial.
4.1.2 Bidding Rules: Drivers’ arrival time, speed, lane, and turn determine the requested bundle, while the additional reservation parameter is the bid value.The intersection manager can infer the required slots from the request parameters.
4.1.3 Auction Policy: Each auction round collects bids for a fixed interval, runs winner determination, and confirms the reservations in the resulting winner set.Bids arriving during winner determination are deferred to the next round.
4.1.4 Winner Determination Algorithm: Winner determination is time-bounded because complete optimal algorithms are unsuitable for real-time execution, so the policy uses an anytime stochastic search.The algorithm runs a one-second loop and updates the best solution found so far.
4.1.4 Winner Determination Algorithm: Previously granted low-valued bids can block later high-valued bids, requiring the affected driver to slow down and resubmit a bid.The authors report that the resulting bid-delay effect is negligible in practice despite the theoretical possibility of worsening.

4.2 Simulation Environment

The evaluation uses a microscopic, discrete intersection simulator with fixed lanes and an Intelligent Driver Model to represent vehicle motion and car-following behavior.

4.2 Simulation Environment: The simulator models a grid divided into 3 m lanes and 0.25 m tiles, with vehicles represented as 2 m × 4 m rectangles and assigned preferred speeds of 30–50 km/h.Origins and destinations are generated randomly.
4.2 Simulation Environment: Vehicles remain in their pre-assigned lanes because the approach link is short, so the simulation requires car-following but no lane-changing model.Vehicle dynamics use the Intelligent Driver Model.
4.2 Simulation Environment: In the model, a, g, v, v_p, s_0, and T denote acceleration, deceleration, actual speed, preferred speed, minimum gap, and time headway.These quantities parameterize free-road acceleration and car-following behavior.
4.2 Simulation Environment: The Intelligent Driver Model combines acceleration toward preferred speed with braking based on the gap to the front vehicle.The preferred distance changes dynamically when vehicles approach slower traffic.

4.3 Experimental Results

The experiments test whether combinatorial auctions reduce delay for higher-valued bids while examining their effects on overall intersection performance. Results show lower delays for moderate-to-high bids, but increased demand raises average delay and rejected requests under the auction policy.

Experimental setup: Traffic demand was varied by changing the expected number of vehicles generated per origin-destination pair over 60-second intervals using a Poisson distribution.Vehicles were spawned for 30 minutes, with the tested demand levels reported in Table 1.
Experimental setup: The winner-determination procedure ran for one second per auction, followed by a one-second bid-collection interval.Incoming bids were also received concurrently during algorithm execution.
Bid-delay relation: 49.8% of drivers bid above the mean, and delays decrease sensibly for bids from 100 to 150 cents before settling above 1000 cents.Figure 7 reports travel-time versus bid value across traffic demands, with 95% confidence intervals.
Fairness and rejection: Reservation-distance preprocessing prevents a driver’s bid from being rejected indefinitely, although repeatedly rejected vehicles can experience greater delays than higher-paying drivers.Once a vehicle reaches the intersection edge, its updated reservation distance gives it priority to submit its preferred bid in the next time step.
Aggregate performance: The auction policy rewards drivers who value reservations most, but at higher traffic demand it increases average delay relative to FCFS.A high-valued bid can displace multiple overlapping bids, allowing one vehicle to pass while others slow down and retry.
Fairness and rejection: The auction policy raises a fairness question because drivers able to pay more may travel faster on public road infrastructure.The paper notes that auction revenue could instead contribute more to maintaining and extending that infrastructure.

4.4 Discussion

The auction policy prioritizes drivers with higher valuations, reducing their individual delays but increasing average travel times. Its performance is constrained by dynamic, uncertain traffic conditions and limited auction-design options.

4.4 Discussion: About 30% less individual delay is experienced by drivers submitting high-value bids than by drivers submitting low-value bids.The policy allocates disputed intersection resources according to drivers’ valuations rather than simply maximizing granted reservations.
4.4 Discussion: Greater average travel times create a social cost because the policy does not maximize the number of granted reservations.This trade-off may limit applicability under high traffic loads, where additional demand-reduction mechanisms are needed.
4.4 Discussion: High load reduces reservation distance, so even wealthy drivers may wait until they are close enough to participate in an auction.Reservation distance is the maximum distance from which a driver may request a reservation.
4.4 Discussion: No zero-delay outcome is guaranteed because dynamic traffic and noisy arrival-time estimates can force winning agents to resubmit bids.A resubmitted bid enters an auction with a different set of competing bidders, so the agent may not win again.
4.4 Discussion: Urban traffic limits winner-determination and payment designs, while first-price payments may encourage bids below drivers’ true valuations.The authors prioritize winner determination and use submitted bids as prices; extending truthful combinatorial payments is computationally difficult.

5. Network of Intersections

The paper extends reservation-based intersection control to networks by using market-inspired traffic assignment to influence drivers’ route choices. Intersection managers supply reservations, while drivers choose routes as buyers in the market.

5. Network of Intersections: Traffic assignment is treated as a distributed choice and allocation problem in which markets mediate drivers’ route choices and road-capacity allocation.The network extension focuses on multiple intersections rather than the single-intersection bid-value decision.
5. Network of Intersections: Intersection managers act as reservation providers and drivers act as buyers who select routes using the prices of required reservations.The market is designed so that infrastructure-side managers influence route allocation through reservation prices.

5.1 Competitive Traffic Assignment (CTA)

Competitive traffic assignment uses continuously updated reservation prices to influence routes across a network of intersections. In evaluation, CTA generally reduces travel times and congestion relative to FCFS, though its effects vary by route and intersection.

5.1.1 CTA Pricing Strategy: The pricing strategy updates each intersection manager’s price from excess demand while allowing drivers to join and leave the market continuously.It adapts the Walrasian equilibrium idea to a traffic setting with dynamic participation and continuous transactions.
5.1.1 CTA Pricing Strategy: Managers treat demand above 50% of optimal link density as excess demand, using s(l) = 0.5 · µopt · ℓ(l) to raise prices and divert routes.Low-demand links are assigned zero minimum price, δ = 0.
5.1.4 Experimental Results: CTA reduces average travel time for 30 of 42 origin-destination pairs compared with FCFS, especially on the busiest routes.FCFS performs better on some less-demanded pairs when the preferred route already has free flow and CTA diverts traffic to slower alternatives.
5.1.4 Experimental Results: CTA keeps density below FCFS at critical intersections c3, c4, and c6, with only limited excess above optimal density at c4 and c6.The comparison is especially favorable at c4 and c6, where CTA exceeds optimal density only slightly and briefly.
5.1.4 Experimental Results: At c5, CTA produces a higher peak around 9:30 but exceeds optimal density later and returns below it earlier.The timing of the excess-density interval contributes to the lower integral reported for CTA.
5.1.4 Experimental Results: 70.24 veh · h/km versus 105.07 veh · h/km is the above-optimal-density integral under CTA and FCFS, respectively.The lower CTA value indicates less accumulated density above optimal levels over the evaluated interval.

5.2 An Integrated Mechanism for Traffic Management (CA-CTA)

The CA-CTA mechanism integrates combinatorial-auction reservation control with competitive traffic assignment, using adaptive reserve prices to manage route access and demand. Experiments compare it with FCFS and CTA on bid-dependent delay, route travel times, and network-wide average travel time.

CA-CTA mechanism: CA-CTA adapts intersection reserve prices to excess demand and accepts only bids above the current reserve price.Intersection managers raise prices when demand increases and lower them when demand decreases, while the underlying reservation allocation uses the combinatorial-auction policy.
CA-CTA mechanism: Drivers construct a route choice set whose intersections fall below their bid, then select the shortest route using estimated travel times and reserve prices.The route model represents each route as an ordered list of links with travel-time and reserve-price attributes.
Experimental results: Drivers bidding 150–200 cents reduced normalised delay by about 50% compared with drivers bidding below 50 cents.The inverse bid-delay relation indicates that the auction component rewards drivers submitting higher bids with lower delays.
Experimental results: CTA achieved the lowest average travel times, while CA-CTA slightly underperformed CTA but outperformed FCFS as network load increased.Both policies improved travel time relative to FCFS, whose shortest-route choices could produce worse network-wide routing.
Experimental results: CA-CTA reduced average travel time for more than 70% of origin-destination pairs versus FCFS, with gains exceeding 50% on busy routes O6-O2, O6-O3, and O7-O3.Losses exceeding 20% occurred especially on O5-O7 and O3-O2, where demand reduction was insufficient and auction social costs increased travel time.

6. Conclusions

The paper extends reservation-based intersection control with combinatorial auctions, competitive traffic assignment, and an integrated adaptive market mechanism. The conclusions report bid-dependent delay reductions alongside lower network-wide travel times, while identifying simplified driver behavior and absent vehicle-to-vehicle collaboration as future-work boundaries.

Contributions: The combinatorial-auction policy reduced delay for higher-bidding drivers but imposed greater average delays when traffic demand was high.This trade-off motivated combining auction-based intersection control with market-inspired traffic assignment.
Contributions: The traffic assignment strategy extended reservation-based control from a single intersection to a network by distributing traffic flow more effectively.The strategy addressed network traffic management from an adaptation perspective and was intended to make traffic control easier.
Integrated mechanism: The integrated mechanism distributed vehicles more homogeneously, lowered average travel times, and retained an inverse relation between bid value and delay.Demand-response reserve pricing reduced the auction policy’s social cost at intersections by lowering demand at particularly disputed locations.
Future work: The driver model considered route choice as utility maximisation and should be enriched to capture the complexity of urban traffic behaviour.Suggested extensions include a two-layer decision maker with reactive behaviour in addition to route choice.
Future work: The system modelled only vehicle–infrastructure interactions, leaving vehicle-to-vehicle collaboration outside the mechanism.Vehicle-to-vehicle communication could expand drivers’ action spaces through dynamically joining or abandoning vehicle coalitions.