Daniel A. Lazar

Road congestion induces significant costs across the world, and road network disturbances, such as traffic accidents, can cause highly congested traffic patterns. If a planner had control over the routing of all vehicles in the network, they could easily reverse this effect. In a more realistic scenario, we consider a planner that controls autonomous cars, which are a fraction of all present cars. We study a dynamic routing game, in which the route choices of autonomous cars can be controlled and the human drivers react selfishly and dynamically. As the problem is prohibitively large, we use deep reinforcement learning to learn a policy for controlling the autonomous vehicles. This policy indirectly influences human drivers to route themselves in such a way that minimizes congestion on the network. To gauge the effectiveness of our learned policies, we establish theoretical results characterizing equilibria and empirically compare the learned policy results with best possible equilibria. We prove properties of equilibria on parallel roads and provide a polynomial-time optimization for computing the most efficient equilibrium. Moreover, we show that in the absence of these policies, high demand and network perturbations would result in large congestion, whereas using the policy greatly decreases the travel times by minimizing the congestion. To the best of our knowledge, this is the first work that employs deep reinforcement learning to reduce congestion by indirectly influencing humans' routing decisions in mixed-autonomy traffic.

Traffic congestion has large economic and social costs. The introduction of autonomous vehicles can potentially reduce this congestion by increasing road capacity via vehicle platooning and by creating an avenue for influencing people's choice of routes. We consider a network of parallel roads with two modes of transportation: 1) human drivers, who will choose the quickest route available to them, and 2) a ride hailing service, which provides an array of autonomous vehicle route options, each with different prices, to users. We formalize a model of vehicle flow in mixed autonomy and a model of how autonomous service users make choices between routes with different prices and latencies. Developing an algorithm to learn the preferences of the users, we formulate a planning optimization that chooses prices to maximize a social objective. We demonstrate the benefit of the proposed scheme by comparing the results to theoretical benchmarks that, we show, can be efficiently calculated.

Traffic congestion has large economic and social costs. The introduction of autonomous vehicles can potentially reduce this congestion by increasing road capacity via vehicle platooning and by creating an avenue for influencing people's choice of routes. We consider a network of parallel roads with two modes of transportation: (i) human drivers, who will choose the quickest route available to them, and (ii) a ride hailing service, which provides an array of autonomous vehicle route options, each with different prices, to users. We formalize a model of vehicle flow in mixed autonomy and a model of how autonomous service users make choices between routes with different prices and latencies. Developing an algorithm to learn the preferences of the users, we formulate a planning optimization that chooses prices to maximize a social objective. We demonstrate the benefit of the proposed scheme by comparing the results to theoretical benchmarks which we show can be efficiently calculated.

When selfish users share a road network and minimize their individual travel costs, the equilibrium they reach can be worse than the socially optimal routing. Tolls are often used to mitigate this effect in traditional congestion games, where all vehicles contribute identically to congestion. However, with the proliferation of autonomous vehicles and driver-assistance technology, vehicles become heterogeneous in how they contribute to road latency. This magnifies the potential inefficiencies due to selfish routing and invalidates traditional tolling methods. To address this, we consider a network of parallel roads where the latency on each road is an affine function of the quantity of flow of each vehicle type. We provide tolls (which differentiate between vehicle types) which are guaranteed to minimize social cost at equilibrium. The tolls are a function of a calculated optimal routing; to enable this tolling, we prove that some element in the set of optimal routings has a lack of cycles in a graph representing the way vehicles types share roads. We then show that unless a planner can differentiate between vehicle types in the tolls given, the resulting equilibrium can be unboundedly worse than the optimal routing, and that marginal cost tolling fails in our setting.

In this work we propose a macroscopic model for studying routing on networks shared between human-driven and autonomous vehicles that captures the effects of autonomous vehicles forming platoons. We use this to study inefficiency due to selfish routing and bound the Price of Anarchy (PoA), the maximum ratio between total delay experienced by selfish users and the minimum possible total delay. To do so, we establish two road capacity models, each corresponding to an assumption regarding the platooning capabilities of autonomous vehicles. Using these we develop a class of road delay functions, parameterized by the road capacity, that are polynomial with respect to vehicle flow. We then bound the PoA and the bicriteria, another measure of the inefficiency due to selfish routing, for general networks with multiple source-destination pairs. We find these bounds depend on: 1) the degree of the polynomial in the road delay function and 2) the degree of asymmetry, the difference in how human-driven and autonomous traffic affect road delay. We demonstrate that these bounds recover the classical bounds when no asymmetry exists. We show the bounds are tight in certain cases and that the PoA b

When people pick routes to minimize their travel time, the total experienced delay, or social cost, may be significantly greater than if people followed routes assigned to them by a social planner. This effect is accentuated when human drivers share roads with autonomous vehicles. When routed optimally, autonomous vehicles can make traffic networks more efficient, but when acting selfishly, the introduction of autonomous vehicles can actually worsen congestion. We seek to mitigate this effect by influencing routing choices via tolling. We consider a network of parallel roads with affine latency functions that are heterogeneous, meaning that the increase in capacity due to to the presence of autonomous vehicles may vary from road to road. We show that if human drivers and autonomous users have the same tolls, the social cost may be arbitrarily worse than when optimally routed. We then prove qualities of the optimal routing and use them to design tolls that are guaranteed to minimize social cost at equilibrium. To the best of our knowledge, this is the first tolling scheme that yields a unique socially optimal equilibrium for parallel heterogeneous network with affine latency functions.

Autonomous vehicles have the potential to increase the capacity of roads via platooning, even when human drivers and autonomous vehicles share roads. However, when users of a road network choose their routes selfishly, the resulting traffic configuration may be very inefficient. Because of this, we consider how to influence human decisions so as to decrease congestion on these roads. We consider a network of parallel roads with two modes of transportation: (i) human drivers who will choose the quickest route available to them, and (ii) ride hailing service which provides an array of autonomous vehicle ride options, each with different prices, to users. In this work, we seek to design these prices so that when autonomous service users choose from these options and human drivers selfishly choose their resulting routes, road usage is maximized and transit delay is minimized. To do so, we formalize a model of how autonomous service users make choices between routes with different price/delay values. Developing a preference-based algorithm to learn the preferences of the users, and using a vehicle flow model related to the Fundamental Diagram of Traffic, we formulate a planning optimization to maximize a social objective and demonstrate the benefit of the proposed routing and learning scheme.

Traffic congestion has large economic and social costs. The introduction of autonomous vehicles can potentially reduce this congestion, both by increasing network throughput and by enabling a social planner to incentivize users of autonomous vehicles to take longer routes that can alleviate congestion on more direct roads. We formalize the effects of altruistic autonomy on roads shared between human drivers and autonomous vehicles. In this work, we develop a formal model of road congestion on shared roads based on the fundamental diagram of traffic. We consider a network of parallel roads and provide algorithms that compute optimal equilibria that are robust to additional unforeseen demand. We further plan for optimal routings when users have varying degrees of altruism. We find that even with arbitrarily small altruism, total latency can be unboundedly better than without altruism, and that the best selfish equilibrium can be unboundedly better than the worst selfish equilibrium. We validate our theoretical results through microscopic traffic simulations and show average latency decrease of a factor of 4 from worst-case selfish equilibrium to the optimal equilibrium when autonomous vehicles are altruistic.

We study routing behavior in transportation networks with mixed autonomy, that is, networks in which a fraction of the vehicles on each road are equipped with autonomous capabilities such as adaptive cruise control that enable reduced headways and increased road capacity. Motivated by capacity models developed for such roads with mixed autonomy, we consider transportation networks in which the delay on each road or link is an affine function of two quantities: the number of vehicles with autonomous capabilities on the link and the number of regular vehicles on the link. We particularly study the price of anarchy for such networks, that is, the ratio of the total delay experienced by selfish routing to the socially optimal routing policy. Unlike the case when all vehicles are of the same type, for which the price of anarchy is known to be bounded, we first show that the price of anarchy can be arbitrarily large for such mixed autonomous networks. Next, we define a notion of asymmetry equal to the maximum possible travel time improvement due to the presence of autonomous vehicles. We show that when the degree of asymmetry of all links in the network is bounded by a factor less than 4, the price of anarchy is bounded. We also bound the bicriteria, which is a bound on the cost of selfishly routing traffic compared to the cost of optimally routing additional traffic. These bounds depend on the degree of asymmetry and recover classical bounds on the price of anarchy and bicriteria in the case when no asymmetry exists. Further, we show with examples that these bound are tight in particular cases.