#  GameOpt+: Improving Fuel Efficiency in Unregulated Heterogeneous Traffic
Intersections via Optimal Multi-agent Cooperative Control

Nilesh Suriyarachchi1, Rohan Chandra2, Arya Anantula2, John S. Baras3 and
Dinesh Manocha3,4 1Nokia Bell Labs, USA, 2Computer Science Department, The
University of Texas at Austin, Texas, USA, 3Electrical and Computer
Engineering Department, University of Maryland, College Park, Maryland, USA,
4Computer Science Department, University of Maryland, College Park, Maryland,
USA. Email<EMAIL_ADDRESS>
###### Abstract

Better fuel efficiency leads to better financial security as well as a cleaner
environment. We propose a novel approach for improving fuel efficiency in
unstructured and unregulated traffic environments. Existing intelligent
transportation solutions for improving fuel efficiency, however, apply only to
traffic intersections with sparse traffic or traffic where drivers obey the
regulations, or both. We propose GameOpt+, a novel hybrid approach for
cooperative intersection control in dynamic, multi-lane, unsignalized
intersections. GameOpt+ is a hybrid solution that combines an auction
mechanism and an optimization-based trajectory planner. It generates a
priority entrance sequence for each agent and computes velocity controls in
real-time, taking less than $10$ milliseconds even in high-density traffic
with over $10,000$ vehicles per hour. Compared to fully optimization-based
methods, it operates $100\times$ faster while ensuring fairness, safety, and
efficiency. Tested on the SUMO simulator, our algorithm improves throughput by
at least $25\%$, reduces the time to reach the goal by at least $70\%$, and
decreases fuel consumption by $50\%$ compared to auction-based and signaled
approaches using traffic lights and stop signs. GameOpt+ is also unaffected by
unbalanced traffic inflows, whereas some of the other baselines encountered a
decrease in performance in unbalanced traffic inflow environments.

##  I Introduction

Efficiency and safety are two of the core pillars defining a successful
transportation system. With regard to road infrastructure, safety targets
involve achieving a system capable of operating with zero collisions.
Efficiency targets are more complex and can be broadly broken into time and
energy. Efficiency in time involves getting from point to point in the least
amount of time, while efficiency in energy focuses on using the least amount
of fuel. Improvements in both time and energy efficiency can provide
significant economic gains in terms of reducing fuel used and minimizing time
wasted in traffic. In the United States in 2022, the average driver spent a
fuel cost of $\$546$ and a time spent cost of $\$869$ with $51$ hours spent on
the road111https://inrix.com/scorecard/. Even a $5\%$ improvement in
efficiency would then provide the US with at least a $\$16.5$ $bn$ economic
benefit.

In addition to the savings in fuel costs and time saved, it is also important
to consider the environmental gains. Fuel efficiency also results in a
reduction of greenhouse gas emissions which would help combat the ever-present
threat of global warming and climate change [1, 2]. Additionally, the
resulting reduction in air pollution would have a major impact on health
conditions, especially in urban areas where air quality is often poor. With
the dwindling supply of global crude oil, reducing overall fuel consumption
will also help buy additional time for renewable sources to become more
efficient and accessible [3].

Figure 1: GameOpt+: We present a new approach for improving fuel efficiency
via optimal real-time planning and control in dynamic, heterogeneous, multi-
agent unsignalized intersections. We show that at identical input traffic flow
levels, our approach results in the most fuel efficient traffic flow.

Fuel efficiency can be achieved in multiple ways such as optimizing the path
of travel, minimizing acceleration and braking steps, and through vehicle
design involving engine efficiency, aerodynamics, and energy regeneration [4].
The global effort to push for hybrid and electric vehicles has also helped
push the efficiency bar forward. While the task of improving vehicular design
generally lies in the hands of automobile manufacturers, improvements to
vehicle trajectories often require infrastructure and regulatory support.
Since the majority of fuel efficiency gains can generally be expected from the
second category it is essential that road infrastructure systems become more
intelligent and capable.

Intelligent transportation systems (ITS) [5, 6, 7, 8] utilize sensors,
cameras, and communication systems to gather information about traffic
conditions and optimize traffic flow by adjusting traffic signals to help
reduce delays and improve fuel efficiency [9]. While these sensors can measure
factors such as vehicle speed, traffic volume, and congestion, the
installation of sufficient sensors is often cost-prohibitive [10]. In terms of
control capabilities, traditionally transportation systems have been limited
to simple methods such as traffic signals and variable speed limits [11].
However, the advent of Connected Autonomous Vehicles (CAVs) is about to
revolutionize the sensing and control capabilities of an intelligent
transportation system. CAVs have a multitude of onboard sensors such as
cameras and rangefinders which allow them to accurately track the state of
surrounding traffic. They also possess advanced communication systems which
allow them to share this information with each other as well as with
infrastructure facilities [12]. Finally, in terms of control, CAVs can
accurately plan trajectories and execute consistent maneuvers with high levels
of predictability. They can also follow commands or guidelines set by the
infrastructure control facilities in an ITS [12]. As such, by leveraging the
capabilities of CAVs, modern transportation systems would possess a
significantly higher degree of sensing and control capability. These increased
capabilities allow the control systems of ITS to pursue more sophisticated and
better-performing control methods which leads to improved efficiency and
safety.

Physical bottlenecks such as traffic intersections and highway merge junctions
as well as phenomena such as traffic shock waves play a major role in reduced
safety and increased congestion on road networks [13, 14]. Of these, often the
most challenging scenario is the unregulated traffic intersection, i.e.
intersections with no stop sign or traffic light. Unregulated intersections
are responsible for a significant portion of road accidents, with $40\%$ of
all crashes, $50\%$ of serious collisions, and $20\%$ of fatalities occurring
there [15]. To address this issue, the concept of connected autonomous
vehicles (CAVs) equipped with vehicle-to-infrastructure (V2I) communication
has emerged. By introducing additional sensing and actuation points, these
CAVs enable the development of new algorithms to tackle unregulated
intersections. Successful applications of this approach include handling
complex traffic bottlenecks like highway merging and traffic shock waves[16,
17, 18]. Recent research has explored leveraging cooperation among CAVs to
achieve safe, fair, and efficient intersection control, drawing on various
fields such as game theory, auctions, optimization, and deep learning.
However, no single solution has demonstrated the ability to satisfy all four
key considerations: safety, efficiency, fairness, and real-time operation.
Safety involves preventing collisions, efficiency focuses on maximizing
intersection capacity, fairness requires equitable treatment of all agents,
and real-time computation is crucial for adapting to dynamic changes in this
fast-paced environment.

The problem of controlling intersections for multiple agents can be divided
into two main phases. The planning phase focuses on determining the optimal
entrance sequence, the order in which vehicles should enter the intersection.
The control phase involves generating safe trajectories for all vehicles to
follow in order to adhere to the selected sequence. The resulting target
trajectories are then transmitted to each vehicle’s local controller for
execution. However, selecting the sequence becomes increasingly challenging as
the number of vehicles grows, leading to an exponential increase in
possibilities. This complexity is further compounded in multi-lane scenarios
where multiple vehicles can enter the intersection simultaneously without
conflicts to maximize efficiency. Practical intersection scenarios are also
dynamic, meaning that the number of vehicles requesting to cross the
intersection changes over time. Finally, we must also consider the impact of
heterogeneous vehicles. Different types of vehicles differ in their dynamics
and requirements.

###  I-A Related Work

####  I-A1 Solutions for Improving Fuel Efficiency

Several approaches have been aimed at efficiency improvements for autonomous
vehicles. By communicating traffic signal information to vehicles, an
optimization-based control algorithm can be utilized to predict an efficient
velocity trajectory [19]. The objectives were selected to improve efficiency
by reducing idle time at stoplights, arriving at green lights with minimal
braking, and cruising at the desired speed. Another optimization-based
technique for intersection management focused on using cooperative adaptive
cruise control to minimize delays at intersections [20]. The approach
demonstrated that the reduction of delays at intersections led to significant
savings in fuel consumption.

In relatively recent approaches, platoons (a group with a leading vehicle and
following vehicles) are used to increase driving stability and reduce air
resistance between vehicles which minimizes wasted gasoline. Additionally,
reinforcement learning is utilized to calculate optimal start-to-end paths
with the storage and computation load on network edges [21]. In creating the
routes, the vehicles consider the fuel efficiency of a route as a key factor.

####  I-A2 Towards Navigating Unregulated Traffic Intersections

Previous studies have explored the use of auction mechanisms for navigating
unsignalized intersections in real time while ensuring fairness and
feasibility [22, 23]. However, these mechanisms are limited to static
scenarios with a fixed number of participating agents, resulting in subpar
efficiency and throughput when the number of vehicles is variable. Incentive-
compatible auctions, such as the mechanism proposed by Sayin et al. [24],
allocate turns to agents based on their distance from the intersection and the
number of passengers in their vehicles. Likewise, Carlino et al. [23] and Rey
et al. [25] propose a similar approach but employ a monetary-based bidding
strategy. Buckman et al. [26] incorporate a driver behavior model [27] into a
first-in, first-out framework to account for human social preferences. More
recently, Chandra et al. [22, 28, 29, 30] introduced an auction mechanism
based on the driving behavior of the agents.

Autonomous vehicle navigation has also seen the application of game-theoretic
approaches [31, 32, 22]. Li et al. [31] employ a stackelberg game where one
agent assumes the role of the leader, following the first-out (FIFO)
principle, while the other agent acts as a follower. In contrast, Tian et al.
[32] adopt a recursive $k-$level approach, deriving strategies at each level
from previous levels. However, in these approaches, all agents, except the ego
agent at the first level, are treated as static entities.

Although optimization-based methods offer safety guarantees by computing
optimal trajectories, their practical implementation in real-time is hindered
by high computational costs. Existing approaches address this limitation by
making unrealistic assumptions. Rios-Torres et al. [16, 33] propose a real-
time solution to the optimization problem using Hamiltonian analysis, but this
approach does not extend well to fully constrained problems. Computation is
also limited to scenarios with fewer vehicles on single-lane roads, excluding
turning at intersections, to enable near real-time calculations [34, 35, 36].
In our previous work [17], Suriyarachchi et al. applied a hybrid control
approach combining rules and optimization to achieve real-time performance in
the context of highway merging. However, relying solely on rule-based sequence
selection leads to sub-optimal solutions.

Deep learning techniques, including reinforcement learning [37, 38, 39, 40]
and recurrent neural networks [41, 42, 43, 44], have been utilized to train
planning and control policies for agents approaching intersections. However,
these policies often struggle to generalize effectively across different
environments and lack guarantees regarding safety and fairness. Additionally,
most learning methods face challenges when applied to dynamic scenarios
involving multiple agents for planning and control.

In our previous work, we developed GameOpt [45], a hybrid planning and control
algorithm for navigating unsignalized dynamic intersections by combining
auctions with optimal control. Key features of GameOpt+ involved the
computation of a game-theoretic-based safe, fair, and efficient intersection
merge sequence with a corresponding optimization-based control strategy that
could function in real-time. The system was shown to handle multiple input
lanes ad varying levels of traffic flow. Despite its evident advantages over
prior methods for navigation at unregulated intersections, GameOpt+ did not
account for heterogeneous vehicles. Different types of vehicles differ in
their fuel capacity and requirements.

###  I-B Main Contributions:

We propose a novel approach, called GameOpt+, that uses game theory and
optimization to improve fuel efficiency.

  * •

GameOpt+ simulates heterogeneous vehicles that have different lengths,
velocities, and accelerations.

  * •

GameOpt+ also incorporates driver preference/aggressiveness that influences
speed and fuel usage.

##  II Intersection Control Formulation

Optimal vehicle flow at unregulated intersections maximizes fuel efficiency.
We define optimal vehicle flow via the following characteristics:

  1. 1.

Fairness: The velocities, $v_{i}$, determined should maximize utility for all
agents and encourage incentive compatibility.

  2. 2.

Safety: The trajectories produced by the optimizer should ensure collision-
free paths.

  3. 3.

Efficiency: The algorithm as a whole should optimize throughput, time-to-goal,
and fuel efficiency.

  4. 4.

The planning and control system should not rely on accessing the objective or
utility functions of other agents.

  5. 5.

The planning and control system should not assume a dynamics model; instead,
it should calculate dynamics for each agent based on a simple forward motion
model.

To initiate the process, the initial stage entails establishing the physical
attributes of an unsignalized intersection, along with comprehending the
dynamics and control mechanisms of the involved CAVs.

###  II-A Modeling the Physical Intersection

An unsignalized intersection is characterized as a four-way crossing with no
traffic signals or right-of-way regulations and can be either single-lane or
multi-lane. In our work, we present an example of a single-lane intersection
in Fig. 2. To facilitate control and coordination, we define a control zone of
length $L_{c}$ along each arm of the intersection. Within this control zone,
vehicles can exchange state information and receive actuation commands through
V2I communication protocols. For the purpose of this research, we assume ideal
conditions with zero transmission delay and a flawless V2I communication
channel. The center of the intersection, known as the conflict zone, poses a
risk of collisions. The number of vehicles present in the control zone of
roads $0,1,2,3$ is represented by $n_{1},n_{2},n_{3},n_{4}$, respectively,
with the total number of vehicles in the control zone being
$n=n_{1}$+$n_{2}$+$n_{3}$+$n_{4}$.

Figure 2: Regions of interest: We highlight the control zone in which vehicles
communicate with the control tower and the conflict zone in which vehicles
cross over to their desired target road.

The vehicles operating within the intersection have the autonomy to make their
own decisions, including choosing to turn left, turn right, or proceed
straight. It is possible to adjust the input flow rate of vehicles in each
control zone of the intersection, as well as the proportion of vehicles opting
to turn left, turn right, or go straight. The input flow rate is varied in the
range of $2,000$ to $10,000$ vehicles per hour, with the generation of
vehicles following a Poisson distribution.

###  II-B Vehicle Dynamics and modeling

In real-world scenarios, vehicle dynamics are hard to model accurately due to
their non-linearity. Standard practice in control theory suggests the use of a
local controller, $z_{i}$, that produces low-level controls for the
longitudinal and lateral motion of a vehicle according to the following
equation,

$\frac{\delta s_{i}}{\delta t}=\mathcal{F}(t,s_{i},z_{i}).$ (1)

Figure 3: GameOpt+ overview: Our approach begins by reading in the positions
and velocities of all agents in the control zone (blue). Our approach is
hybrid; in the planning phase, GameOpt+ collect the bids from every agent and
generate an optimal priority sequence (Section III-A). In the controls phase,
we use an optimization-based trajectory planner to compute the optimal
velocity for each agent that satisfies the priority order while simultaneously
guaranteeing safety and real-time performance (Section III-C).

Here, we represent $\mathcal{F}$ as the unknown non-linear dynamic function.
$s_{i}$ denotes the distance of the agent $i$ from the intersection measured
in the Frenet coordinate system.

Dynamics: Since $\mathcal{F}$ is generally unknown, we define the high-level
dynamics by the following velocity control scheme:

$\displaystyle\frac{\delta s_{i}}{\delta t}$ $\displaystyle=v_{i}$ (2)
$\displaystyle v_{i}(t)$ $\displaystyle=\bm{u}_{i}(t)$

for $i\in\\{1,\ldots,n\\}$.

Control variables: The control input, $\bm{u}_{i}(t)$, represents the command
velocity for vehicle $i$. We compute the optimal value for $\bm{u}_{i}(t)$
with respect to safety, efficiency and reachability guarantees described in
the following sections.

State vector: In addition to $s_{i}(t)$ and $v_{i}(t)$, we assign an indicator
variable $l^{c}_{i}(t)\in\\{0,1,\ldots,L_{n}-1\\}$, which signifies which lane
the vehicle is currently in, with $L_{n}$ representing the number of lanes on
each road. We also obtain the length $l_{i}$, and maximum acceleration
$a^{max}_{i}$ and deceleration $a^{min}_{i}$ capabilities of each CAV $i$. In
a scenario of multi-arm multi-lane intersections, we need to identify which
direction each vehicle intends to take through the intersection. Therefore, we
allocate each vehicles in the control zone into a group $G_{i}$ based on its
desired trajectory (origin road and intended direction) as shown in section
III-B, in order to resolve conflicts inside the intersection.

Handling heterogeneous vehicles: When dealing with heterogeneous multi-class
traffic we find that different classes of vehicles can have significantly
different goals. Some classes may prefer to prioritize reaching their
destination and speed while others would prefer to maintain fixed speeds and
not perform too many acceleration tasks in order to save fuel. For example, an
ambulance cares more about speed maximization, while a large semi-trailer
truck would rather minimize its overall acceleration tasks due to the
relatively large fuel costs associated with these actions. In addition to
vehicle class we find that other factors such as total waiting time, current
speed and individual vehicle intent or aggressiveness plays a major role in
what features each car prioritizes. In order to achieve a more optimal control
solution it is necessary that each vehicle should be treated differently based
on its specific needs. As such we assign a vehicle type $c_{i}$ which depends
on the class of vehicle and a driver preference (aggressiveness) value
$d_{i}$, which takes a value from $0$ to $1$ indicating a vehicles bias
towards either driving as fast as possible $(\text{towards }1)$ or reducing
fuel usage $(\text{towards }0)$. We also include the waiting time $w_{i}(t)$
indicating how long it has been since the vehicle entered the control zone.

The CAVs are thereby completely defined by the state vectors:

$\bm{\Phi}_{i}(t)=[s_{i}(t),v_{i}(t),l^{c}_{i}(t),w_{i}(t),c_{i},d_{i},G_{i},l_{i},a^{max}_{i},a^{min}_{i}]^{\top}$
(3)

for $i\in\\{1,\ldots,n\\}$. We also define a parameter tuple
$M_{s}=\\{M_{sr},M_{sl}\\}$, which represent the safety margins needed to
prevent rear-end and lateral collisions.

###  II-C Dynamic Traffic Intersection Planning & Control Problem

The dynamic traffic intersection problem involves computing suitable,
collision-free, continuous trajectories for all vehicles approaching an
intersection to achieve efficient and fair traffic flow. This problem can be
formulated as an optimal control problem, with the objective of computing the
optimal command velocities $\bm{u}_{i}$ for each CAV $i\in\\{1,\ldots,n\\}$,
resulting in the minimization of the maximum time taken by each CAV to cross
the intersection:

$\displaystyle\leavevmode\nobreak\ \leavevmode\nobreak\
\min_{\\{\bm{u}_{i}\\}}\leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \max_{i}\leavevmode\nobreak\ t_{f}^{i}$ (4)
$\displaystyle
s.t.\quad\quad\mathcal{C}(\\{\bm{\Phi}_{i}\\},\bar{v},\mathbb{S}(M_{s}))$

where $t_{f}^{i}$ is the intersection crossing time of vehicle $i$.
$\mathcal{C}$ is a set of constraints, discussed in Section III-C, that depend
on the state vectors $\\{\bm{\Phi}_{i}\\}$ of the CAVs, and safety
requirements $\mathbb{S}(M_{s})$ which prevent collisions between vehicles.

Equation 4 is, however, intractable to optimize directly because it implicitly
assumes that agents are navigating the intersection according to the optimal
priority order, $q^{*}$. Equation 4 can be equivalently solved by optimizing
jointly over sequences, $q$, and the control velocities, $\bm{u}_{i}$, needed
to implement the sequence.

$\displaystyle\leavevmode\nobreak\ \leavevmode\nobreak\
\min_{\\{\bm{u}_{i},q\\}}\leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\
\sum_{i=1}^{n}\lambda(\bm{u}_{i}-\bar{v})^{2}+(1-\lambda)(\bm{u}_{i}-v_{i})^{2}$
(5) $\displaystyle
s.t.\quad\quad\mathcal{C}(\\{\bm{\Phi}_{i}\\},\bar{v},\mathbb{S}(M_{s}),q)$

where $\bar{v}$ is the speed limit. We solve this optimization problem in
Section III-C.

Intractability of Equation (5): The optimal control velocities, $\bm{u}_{i}$,
depend on the sequence order $q$ of the vehicles entering the conflict zone.
The naive solution is to solve a mixed-integer optimization problem for every
possible entrance sequences $q$ by performing an exhaustive search. This
process involves two sub-problems—generating a sequence $q$ followed by
computing the optimal velocity commands $\bm{u}_{i}$ for that sequence. The
total number of possible sequences $q$ grows exponentially with the number of
vehicles in the control zone which would take the form
$\mathcal{O}\left(\frac{(n_{1}+n_{2}+n_{3}+n_{4})!}{n_{1}!n_{2}!n_{3}!n_{4}!}\right)$,
where $n$=$n_{1}$+$n_{2}$+$n_{3}$+$n_{4}$ is the number of vehicles in the
control zone. Therefore, current methods to solve Equation 5 are intractable.

We propose the use of auctions to obtain an optimal priority sequence order
$q^{*}$ in $\mathcal{O}\left(n\log n\right)$ time, significantly reducing the
combinatorial runtime complexity of the mixed-integer formulation. We run the
optimization over $\bm{u}_{i}$ for the selected optimal sequence $q^{*}$ which
can be solved in real time.

###  II-D Sponsored Search Auctions

Sponsored search auctions (SSAs) are a game-theoretic mechanism that are used
extensively in internet search engines for the purpose of internet advertising
[46]. In an SSA, there are $K$ items to be allocated among $n$ agents. Each
agent $a_{i}$ has a private valuation $\bm{v}_{i}$ and submits a bid
$\bm{b}_{i}$ to receive at most one item of value $\bm{\alpha}_{i}$. A
strategy is defined as an $n$ dimensional vector,
$\bm{b}=(\bm{b}_{i}\cup\bm{b}_{-i})$, representing the bids made by every
agent. $\bm{b}_{-i})$ denotes the bids made by all agents except $a_{i}$.
Furthermore, let $\bm{b}_{1}>\bm{b}_{2}>\ldots>\bm{b}_{K}$ and
$\bm{\alpha}_{1}>\bm{\alpha}_{2}>\ldots>\bm{\alpha}_{K}$. The allocation rule
is that the agent with the $i^{\textrm{th}}$ highest bid is allocated the
$i^{\textrm{th}}$ most valuable item, $\bm{\alpha}_{i}$. The utility
$\bm{u}_{i}$ [46] incurred by $a_{i}$ is given as follows,

$\bm{u}_{i}(\bm{b}_{i})=\bm{v}_{i}\bm{\alpha}_{i}-\sum_{j=i}^{k}\bm{b}_{j+1}\left(\bm{\alpha}_{j}-\bm{\alpha}_{j+1}\right).$
(6)

In the equation above, the quantity on the left represents the total utility
for $a_{i}$ which is equal to value of the allocated goods $\bm{\alpha}_{i}$
minus a payment term. The first term on the right is the value of the item
obtained by $a_{i}$. The second term on the right is the payment made by
$a_{i}$ as a function of bids $\bm{b}_{j>i}$ and their allocated item values
$\bm{\alpha}_{j}$. We refer the reader to Chapter $3$ in [46] for a derivation
and detailed analysis of Equation 6.

In our approach, we re-cast Equation 6 through the lens of a human driver.
More specifically, the term $\bm{v}_{i}\bm{\alpha}_{i}$ denotes the time
reward gained by driver $a_{i}$ by moving on her turn. The payment term
represents a notion of risk [47] associated with moving on that turn. It
follows that an allocation of a conservative agent to a later turn (smaller
$\bm{\alpha}$) also presents the lowest risk and vice-versa.

##  III GameOpt+

The overall approach is depicted in Figure 3, showcasing the flow of
computation. Initially, the positions, velocities, and initial bids from all
agents within the control zone are acquired through V2I communication (Section
II). Subsequently, in the planning phase, this information, together with the
processed bids, is utilized to generate an optimal priority order or sequence,
dictating the order of agent entry into the intersection (Section III-A).
Moving into the control phase, our approach employs an optimization-based
trajectory planner to determine the optimal velocity for each agent (Section
III-C). This optimization process ensures adherence to the priority order,
while simultaneously upholding safety and real-time performance guarantees.

###  III-A Game: Selecting a Priority Order, $q$

Choosing an optimal ordering for agents to navigate unsignalized traffic
scenarios is equivalent to allocating each agent a turn in which they would
cross the intersection. Such an allocation depends on the incentives of the
agents which, in many cases, are not known apriori. Auctions model the
incentives of agents in unsignalized traffic scenarios using an optimal
combination of bidding, allocation, and payment strategies. In the rest of
this section, we present the auction framework for generating an optimal
priority order, followed by an analysis of its fairness.

The Sponsored Search Auction (SSA), as detailed in Section II-D, presents an
optimal mechanism for generating a priority order for agents. This algorithm
allows the agent with the highest priority bid to navigate the scenario first,
followed by the agent with the next highest priority, and so on. With a
polynomial runtime, dominated by sorting the agents’ bids, the SSA is an
efficient solution [48]. In GameOpt [45], agents’ bids were based on a single
dimension - the current kinematics of each agent. However, in this work, we
propose a more advanced bidding language where agents can submit multi-
dimensional bids, expressing their preferences using various features or
currencies such as driver behavior-based [22], distance-based [26], and time-
based [23].

Formally, we represent the set of bidding currencies as $\mathscr{F}^{m}$,
where $f\in\mathscr{F}^{m}$ denotes an $m$-dimensional feature vector
comprising bidding currency values. We further define
$\Omega^{m}\subseteq\mathbb{R}^{m}$ as the space of coefficient vectors
$\omega\in\Omega^{m}$. A master bid,
$\bm{b}_{i}:\mathscr{F}^{m}\times\Omega^{m}\longrightarrow\mathbb{R}$, is then
generated and passed on to the SSA. To address multi-agent dynamic traffic, we
implement an overflow strategy where, if an agent with a higher priority is
behind an agent with a lower priority, the former transfers a portion of their
bid to the latter, similar to the Social Forces model.

Typically, SSAs employ a single bidding currency in their frameworks, reducing
the space of bidding strategies to $\mathscr{F}^{1}$. Although some recent
studies [49, 50] propose extensions that allow bidding on multiple slots or
keywords, these auctions still utilize a single currency (bidding over
keywords). However, utilizing a single bidding currency poses several
challenges, primarily that if an agent has a specific budget $B$ for multiple
keywords and spends $90\%$ of $B$ towards a high-profile keyword, they may not
have sufficient funds left to bid on other keywords.

In contrast, multi-currency bidding strategies theoretically allow agents to
realize multiple budgets and thus, expand their power to express their
preferences. However, multi-currency bidding strategies are challenging to
implement in practice, as many currencies lack constraints, and the dimension
of the space $\mathscr{F}^{m}$ grows exponentially with $m$.

In this work, we propose a method for handling multi-currency bidding
strategies. Specifically, we consider the features _time to intersection_
($T^{i}_{I}$), _distance to intersection_ ($D^{i}_{I}$), _waiting time_
($W^{i}_{I}$), and _driver preference or assertiveness_ ($A^{i}_{I}$). Thus
the full feature (bidding currency) set is defined as
$f=[T^{i}_{I},D^{i}_{I},W^{i}_{I},A^{i}_{I}]$, each of which constitutes a
continuous feature, with $m=4$. The master bid $\bm{b}_{i}$ is then computed
as follows:

$\bm{b}_{i}=\omega^{\top}f$ (7)

Which using the coefficients $\omega_{k}$ where $k\in\\{1,\dots,m\\}$ can also
be written as,

$\bm{b}_{i}=\omega_{1}*T^{i}_{I}+\omega_{2}*D^{i}_{I}+\omega_{3}*W^{i}_{I}+\omega_{4}*A^{i}_{I}$
(8)

Next, we describe the equations for computing each bidding feature. Recall
that $s_{i}(t)$ measures the distance of agent $i$ from the intersection, and
we use $\tau_{i}(t)=s_{i}(t)/v_{i}(t)$ to denote the time in which $i$ shall
reach the intersection based on its current velocity and $s_{i}(t)$. The
bidding capacity of vehicles should be higher when they are closer to the
intersection in terms of time and distance. Therefore, the features
$T^{i}_{I}$ and $D^{i}_{I}$ for agent $i$ are computed as follows:

$T^{i}_{I}=(c_{1}-\tau_{i}(t))$ (9) $D^{i}_{I}=(c_{2}-s_{i}(t))$ (10)

where $c_{1}$ and $c_{2}$ are constants representing maximum bounds on control
zone length and time to intersection respectively. Next, agents specify a
preference for waiting in queue for a long time, by the cumulative time it has
been waiting in the control zone $w_{i}(t)$ (available in vehicle state vector
in equation (3)). Feature $W^{i}_{I}$ is then set as $W^{i}_{I}=w_{i}(t)$.
Finally, agents also express their behavior through a driver preference
assertiveness feature $A^{i}_{I}$. For these features vehicles with higher
waiting time and higher preference have a higher bidding capacity. The
computation of the preference feature $A^{i}_{I}$ additionally incorporates
the effects of heterogeneous vehicle types. Therefore, different classes of
vehicles will have varying bounds on their preference bidding capacity
$A^{i}_{I}$. For example, on a scale of 1 to 10, emergency vehicles would have
the highest bidding range of {7 to 10} and passenger cars would have a lower
range such as {1 to 5}. Therefore the maximum bidding capacity within the
driver preference assertiveness feature $A^{i}_{I}$ is dependant on the
vehicle class. This allows vehicles with higher priority needs to be given
preference over other vehicle classes during the sequence order generation
phase. Here, the actual vehicle class $c_{i}$ and individual driver preference
$d_{i}$ is available in the vehicle state vector in equation (3).

By using the combined master bid obtained for each CAV $i$ as shown in
equation (8), a sponsored search auction is conducted to generate the final
feasible merging sequence $q$. Here, vehicles with higher combined bids would
get the opportunity to pass through the intersection before vehicles with
lower bids. As the bidding system is directly linked to the dynamics of the
system, the sequence generated by the auction ensures that vehicles higher up
in the sequence have the dynamic capability to pass the intersection before
vehicles lower down in the sequence. Certain other features such as the
overflow strategy discussed also play a roll in ensuring the overall
feasibility of the generated sequence.

#### Generation of multiple feasible sequences

Thus far we described the method of generating a single feasible sequence $q$,
using the set of bidding currencies as $\mathscr{F}^{m}$, and the space of
coefficient vectors $\omega\in\Omega^{m}$. The choice of coefficients
$\omega_{k}$ where $k\in\\{1,\dots,m\\}$, is a tuning parameter available to
the central controller which can be changed in order to generate multiple
feasible sequences. It is difficult to tell which sequence would be truly
optimal in terms of maximizing vehicle throughput while minimizing fuel
consumption at this stage. Therefore it is the responsibility of the Game
subsystem (section ) of the control system, to generate a suitable collection
of candidate feasible sequences to be tested by the optimization Opt subsystem
(section ) for optimality. Thus, each of the candidate sequences $q$,
generated in Game, will be fed into the optimization Opt subsystem in parallel
to find the best sequence $q^{*}$, whose corresponding target command
velocities would be sent to each CAV in the control zone.

#### Fairness Analysis of $q$

Looking at the game-theoretic aspect, fairness is achieved when no agent has
an incentive to “cheat” meaning that each agent’s dominant strategy is to bid
their true valuation, denoted as $\bm{\zeta}_{i}$. This principle, known as
incentive compatibility, aims to encourage traffic agents to truthfully bid
their actual value ($\bm{b}_{i}=\bm{\zeta}_{i}$) as the optimal strategy [46].
Chandra et al. [22] demonstrated that Single-Stage Auctions (SSAs) implemented
in static intersections with one agent per arm are incentive-compatible. We
expand the theoretical framework of static SSAs to dynamic intersections
involving multiple vehicles, considering the occurrence of overflow when a
lower-priority vehicle obstructs a higher-priority one.

In [22], the authors show that the sponsored search auction is game-
theoretically optimal for static intersections consisting of $1$ vehicle on
each arm of the intersection. In this work, we extend the proof for dynamic
traffic intersections where we must take into account three factors–$(i)$
multiple vehicles on each arm of the intersection and $(ii)$ lower priority
vehicles blocking higher priority vehicles, and $(iii)$ providing waiting time
rewards to agents.

######  Theorem III.1.

Incentive compatibility for dynamic intersections: For each agent $i$ for
$i=1,2,\ldots,n$ and $n=n_{1}+n_{2}+n_{3}+n_{4}$ where $n_{j}$ represents the
number of vehicles on the $j^{\textrm{th}}$ arm, bidding
$\bm{b}_{i}=\bm{\zeta}_{i}$ is the dominant strategy.

###### Proof.

  1. 1.

Use SSA to compute an ordering over all agents. But this can generate false
bids overbids and underbids.

  2. 2.

For example, an agent may be assigned to go second on account of a higher
priority vehicle.

  3. 3.

But the latter vehicle may not even conflict with the first vehicle.
Conversely, agent $i$ might be asked to go first, risking a collision.

  4. 4.

Therefore, it is important to identify conflicting and non-conflicting lane
groups. Run the SSA in conflicting groups only.

  5. 5.

At this point, we can say that since we have optimized conflicting groups and
non-conflicting groups do not collide anyways, the resulting auction is
incentive-compatible

∎

The next desired property in a fair auction is welfare maximization [46] which
maximizes the total time reward (Section II-D) earned by every agent. We show
that SSAs maximize social welfare for dynamic intersections as well.

######  Theorem III.2.

Welfare maximization for dynamic intersections: Social welfare of an auction
is defined as $\sum_{i}\bm{\zeta}_{i}\bm{\alpha}_{i}$ for each agent $i$ for
$i=1,2,\ldots,n$ and $n=n_{1}+n_{2}+n_{3}+n_{4}$ where $n_{j}$ represents the
number of vehicles on the $j^{\textrm{th}}$ arm. Bidding
$\bm{b}_{i}=\bm{\zeta}_{i}$ maximizes social welfare for every agent.

###### Proof.

We can show that welfare is maximum for each set of conflicting lane group. We
need to show that social welfare of the system is maximized when the welfare
of each individual conflicting lane group is maximized. Our proof is based on
induction. Base case ($n=1$): for $n=1$, this reduces to the static auction
case [22]. Hypothesis: Suppose the current system consists of $n>1$
conflicting groups and that the social welfare of this system is maximized.
Then we want to show that the addition of $\lvert n+1\rvert$ agents (belonging
to the $(n+1)^{\textrm{th}}$) conflicting group also maximizes social welfare
of the system. Now, welfare of system with $n$ conflicting groups is

$\sum_{i=1}^{n}\sum_{j=1}^{\lvert i\rvert}\zeta^{i}_{j}\alpha^{i}_{j}$

From the hypothesis, we know that the above is maximum. Now if the
$(n+1)^{\textrm{th}}$ conflicting group is added, then we can maximize that
using the static SSA auction [22]. The resulting sum is a sum of two optimized
terms, so the resulting welfare of the system remains maximum. ∎

Finally, we propose a novel strategy to address overflow by transferring a
portion of the higher priority agent’s bid to the lower priority agent i. We
denote such a transfer by $(\hat{a},\hat{b}=a\xrightarrow{c}b)$, where
$\hat{a}=a-c,\hat{b}=b+c$. More formally,

######  Theorem III.3.

Overflow prevention: In a current SSA, suppose there exists
$(i,j)\in[n_{k}]\times[n_{k}],k=1,2,3,4$, such that
$\bm{\zeta}_{i}>\bm{\zeta}_{j}$ and $s_{i}[t]>s_{j}[t]$. Let
$\bm{\hat{\zeta}}_{i},\bm{\hat{\zeta}}_{j}=(\bm{\zeta}_{i}\xrightarrow{q}\bm{\zeta}_{j})$.
If

$q<\bm{\zeta}_{i}\left(1-\frac{\alpha_{i+m}}{\alpha_{i}}\right)-\sum_{s=i}^{i+m-1}\bm{\zeta}_{s+1}\left(\frac{\alpha_{s}-\alpha_{s+1}}{\alpha_{i}}\right),$

the new SSA with $\bm{\hat{\zeta}}_{i},\bm{\hat{\zeta}}_{j}$ as the new
priority values for $i,j$ is incentive compatible.

###### Proof.

The difference in utility for agent $i$ by transferring some of her valuation
to agent $j$ is given by the following equation. Here, we assume that by
executing this transfer, agent $i$ gained a jump of $m$:

$\begin{split}\Delta
u=(v_{k}-q)\alpha_{k}-\big{[}&v_{k+1}(\alpha_{k}-\alpha_{k+1}+v_{k+2}(\alpha_{k+1}-\alpha_{k+2}+\ldots\\\
&+v_{k+m}(\alpha_{k+m-1}-\alpha_{k+m})\big{]}-v_{k}\alpha_{k+m}\\\
\end{split}$ (11)

Rearranging the terms, $\Delta u>0$ if,

$\begin{split}&v_{k}(\alpha_{k}-\alpha_{k+m})-\sum_{j=k}^{k+m-1}v_{j+1}(\alpha_{j}-\alpha_{j+1})>q\alpha_{k}\\\
\implies&q<v_{k}(1-\frac{\alpha_{k+m}}{\alpha_{k}})-\frac{1}{\alpha_{k}}\sum_{j=k}^{k+m-1}v_{j+1}(\alpha_{j}-\alpha_{j+1})\\\
\end{split}$ (12)

∎

As a final remark, Carlino et al. [23] show that multiplying a bid by a
waiting time reward does not change the incentive compatibility of the
auction. We defer the proofs of Theorems III.1, III.2, and III.3 to [51].

###  III-B Multi-lane Intersection Planning and Control

An essential feature of our approach is its effectiveness in efficiently
managing traffic flow in multi-lane intersections. However, transitioning from
a single-lane to a multi-lane setting presents unique challenges. Assumptions
that hold true in single lanes, such as the presence of only one vehicle at a
time in the conflict zone, no longer hold in multi-lane scenarios. To address
this, we introduce a classification system that groups all vehicles in the
control zone ($G_{i}$) based on their intended trajectory, including the
origin road and their intention. Each group is denoted as x-y: x=road_num,
y=intention (with intention values assigned as: 0=right_turn, 1=go_straight,
2=left_turn). For instance, a vehicle from road 1 intending to make a left
turn would belong to group 1-2. In Fig. 4(a), we illustrate the possible
trajectories for vehicles in each lane and the corresponding labeling used to
assign groups based on these trajectories, indicated on each lane.

(a) Multi-lane intersection structure with lane-based groups

Lane group | No-conflict group set
---|---
0-1 | 0-2, 1-1, 2-2
0-2 | 0-1, 1-2, 3-1
1-1 | 0-1, 1-2, 3-2
1-2 | 0-2, 1-1, 2-1
2-1 | 1-2, 2-2, 3-1
2-2 | 0-1, 2-1, 3-2
3-1 | 0-2, 2-1, 3-2
3-2 | 1-1, 2-2, 3-1

(b) Non-conflicting trajectory groups at intersection

Figure 4: Conflict handling at multi-lane intersections. We propose a novel
strategy for conflict handling using vehicle grouping based on non-colliding
trajectories.

We observe that vehicle groups intending to make right turns at the
intersection (groups 0-0, 1-0, 2-0, 3-0) do not create conflicts with any
other groups. As a result, these groups are granted unrestricted entry into
the intersection, and the optimization constraints outlined in III-C reflect
this allowance. However, it is crucial for the remaining lane groups to
determine which other groups can also enter the intersection simultaneously
without causing conflicts. We refer to this collection as the ”non-conflicting
group set” for each corresponding main lane group, as demonstrated in Table
4(b). For instance, let’s consider the main lane group 0-1. The groups with
trajectories that do not clash with this main group include 0-2, 1-1, and 2-2,
along with all the right turn groups (0-0, 1-0, 2-0, 3-0). Essentially, this
implies that vehicles belonging to the non-conflicting group set of a main
lane group can enter the intersection concurrently with a vehicle from the
main lane group itself. It’s important to note that the right turn at
intersection groups (0-0, 1-0, 2-0, 3-0) are inherently considered non-
conflicting and are automatically included in the non-conflicting groups list
for all vehicle groups. The determination of non-conflicting groups is
predicated on the assumption that vehicles approaching the conflict zone have
already completed any necessary lane changes strategically.

###  III-C Opt: Computing Optimal Velocities

The Optimization Problem:

Based on the priority sequence $q$ from Section III-A, the optimal command
velocities, $\bm{u}_{i}$, for each vehicle $i$ in the control zone are
computed by optimizing Equation 5 for the fixed sequence $q$. The objective
function restated:

$\mathcal{J}(\bm{u}_{i}|q)=\min_{\\{\bm{u}_{i}\\}}\sum_{i=1}^{n}\lambda(\bm{u}_{i}-\bar{v})^{2}+(1-\lambda)(\bm{u}_{i}-v_{i})^{2}$
(13)

The first quadratic term of Equation 13 prevents $\bm{u}_{i}$ from deviating
from the speed limit $\bar{v}$ (results in improved throughput). Thus each
vehicle will attempt to maximize its velocity within limits. The second
quadratic term minimizes the control effort applied to optimize fuel
efficiency. This term minimizes the selection of control goals resulting in
strong acceleration and deceleration tasks. The parameter $\lambda$ offers a
trade off between these two competing terms and provides a method to tune and
prioritize one term over the other.

As described in section II-B, when we are dealing with heterogeneous traffic
it becomes increasingly important to treat individual vehicles differently
depending on their needs and priorities. There are two main types of
priorities we consider in this research. The first type is the Speed Priority
($P^{s}_{i}$), which represents each vehicles desire to maximize its
individual velocity. The second type is the Speed Variation Priority
($P^{v}_{i}$), which represents each vehicles desire to minimize variations to
its current speed, thereby minimizing acceleration tasks and overall fuel
consumption. Based on the vehicle class $c_{i}$ and vehicle preference
$d_{i}$, a priority assignment node computes these two types of priorities
($P^{s}_{i},P^{v}_{i}$) for each vehicle $i$ in the control zone. Each vehicle
depending on its class $c_{i}$ has upper and lower bounds on its priority
values. The exact value assigned within these class bounds takes into account
each vehicle’s individual preference $d_{i}$. While the $\lambda$ parameter in
Equation (13) provides a way to trade off between speed maximization and fuel
savings it only does so in a global sense. In order for each individual
vehicle to adjust its preference towards speed maximization or fuel savings,
we introduce the two priority terms ($P^{s}_{i},P^{v}_{i}$) into the objective
function resulting in the following updated objective function:

$\mathcal{J}(\bm{u}_{i}|q)=\min_{\\{\bm{u}_{i}\\}}\sum_{i=1}^{n}\lambda
P^{s}_{i}(\bm{u}_{i}-\bar{v})^{2}+(1-\lambda)P^{v}_{i}(\bm{u}_{i}-v_{i})^{2}$
(14)

Here, each individual vehicle $i$, can affect the bias towards either
throughput or fuel savings depending on its own individual preferences
captured in its two priority values. This allows for a more optimal solution
which can cater to the individual needs of each vehicle. Below we discuss
constraints on safety and the influence of $q$ on Equation (14).

Constraints on Safety and Compliance with $\mathbf{q}$:

We consider both longitudinal (rear-end) collisions in the control zone and
collisions in the conflict zone. Rear-end collisions along each of the lanes
in the control zone are prevented by ensuring all vehicles in the same lane
maintain a safe distance between each other. Formally,

$\Big{|}s_{j}^{k}(t+1)-s_{j\prime}^{k}(t+1)\Big{|}\geq l_{j}+M_{sr}$ (15)

for all $k$ lanes in the control zone and for all agents $j,j\prime$ with
$j\neq j\prime$ in the $k^{\textrm{th}}$ lane. $l_{j}$ represents the length
of the agent $j$ and $M_{sr}$ is a safety margin added to maintain a safe gap
between vehicles and to account for imperfections in sensing and actuation. We
compute the future position $s_{i}(t+1)$ using,

$s_{i}(t+1)=s_{i}(t)-\Delta t\left(\frac{v_{i}(t)+\bm{u}_{i}(t)}{2}\right)$
(16)

Here, $\Delta t$ is defined as the planning time step of the controller.

Next, we also need to ensure that no collisions occur inside the conflict
zone. This task reduces to ensuring no vehicles belonging to conflicting lane
groups (III-B) enter the intersection simultaneously. Therefore, for each
vehicle $i$ in the sequence $q$, paired with a vehicle $j$ in a conflicting
group where $i$ has higher priority over $j$, we add the constraint,

$t_{c}^{i}+\frac{(l_{i}+M_{sl})}{\bm{u}_{i}}\leq t_{c}^{j}$ (17)

where $t_{c}^{i}=\frac{s_{i}(t+1)}{\bm{u}_{i}}$ represents the time at which
$i$ would arrive at the intersection. The above constraint ensures that
command velocities $\bm{u}_{i}$ are chosen such that vehicles proceed through
the conflict zone in the order of the sequence under consideration $q$. Note
that this constraint is applied to every conflicting pair of vehicles; non-
conflicting vehicles are allowed to enter the intersection at the same time,
increasing the efficiency of the system. The safety margin $M_{sl}$
corresponds to the width of the intersection and prevents lateral collisions
occurring when conflicting vehicles cross the intersection.

The safety constraints with respect to ordering $q$ in Equations (15) and (17)
result in an intractable mixed-integer quadratic programming (MIQP)
optimization problem. This problem is further compounded due to lane indexing,
which introduces a new variable indicating the agent’s lane. We remove the
dependency over the lane index by separating the constraints for each lane and
using the multi-lane conflict resolution scheme introduced in III-B. This
results in simplification of Equations (15) and (17), reformulating the
original MIQP as a quadratic programming (QP) optimization problem; this QP
can be solved in real-time. More formally, Equation (15) can be simplified as,

$\displaystyle\bm{u}_{j}^{k}-\bm{u}_{j+1}^{k}\geq$
$\displaystyle\left(v_{j+1}^{k}-v_{j}^{k}\right)$ (18)
$\displaystyle+\frac{2}{\Delta
t}\left(s_{j}^{k}-s_{j+1}^{k}+l_{j}+M_{sr}\right)$

for all $k$ lanes in the control zone and for all $j,j+1$ consecutive vehicles
belonging to lane $k$. And Equation (17) can be simplified as,

$\bm{u}_{j}\left(s_{i}-\frac{\Delta
t}{2}.v_{i}+l_{i}+M_{sl}\right)\leq\bm{u}_{i}\left(s_{j}-\frac{\Delta
t}{2}.v_{j}\right)$ (19)

for all vehicles $i$ in sequence $q$ and for all vehicles $j$ in a conflicting
group to vehicle $i$.

Finally, we enforce reachability by bounding the command velocities by the
speed limit, $\bar{v}$, as well as the acceleration and breaking capabilities
of each individual vehicle.

$0\leq\bm{u}_{i}(t)\leq\bar{v}$ (20) $a^{min}_{i}\Delta
t\leq\bm{u}_{i}(t)-v_{i}(t)\leq a^{max}_{i}\Delta t$ (21)

Solving Opt: The constraints (18), (19), (20), and (21) are provided to Opt
with objective function given by Equation (14), which is solved numerically
using Gurobi (version 9.1.2) [52].

The output of this objective function includes the computed target
$\bm{u}_{i}$ command velocities for each CAV $i$ and the minimum objective
value achieved for the sequence tested $q$. This information is saved for
evaluation in the next step.

Obtaining optimal sequence $q^{*}$ and command velocities $\bm{u}_{i}^{*}$

Once all the optimization processes for each merging sequence $q$, generated
in section III-A are completed, we analyze their output data to determine the
optimal sequence $q^{*}$ and command velocities $\bm{u}_{i}^{*}$. We compare
the objective values achieved for each tested sequence $q$, and the sequence
providing the minimum objective value is deemed to be the optimal sequence
$q^{*}$. The corresponding command velocities $\bm{u}_{i}$ are then deemed to
be the optimal target command velocities $\bm{u}_{i}^{*}$.

The optimal target $\bm{u}_{i}^{*}$ command velocities are then transmitted to
each of the CAVs in the control zone. Note that we do not consider delays in
communication and assume data is transmitted instantaneously via V2I
communication. The low-level controller on-board each CAV then computes the
acceleration or deceleration needed, to achieve the desired $\bm{u}_{i}$
command velocity within the control time ($\Delta t$) duration.

Finally, a key feature of our approach is that it is robust to drift in the
executed control. Our approach operates at a cycle frequency of $100$ ms after
which new command velocities are obtained, updating the previous controls.
Therefore, any deviation between optimal control and the executed control is
erased during every $100$ ms update cycle.

##  IV Experiments and Results

In this section, we evaluate the capabilities of our approach, study the
impact of varying environmental parameters, and compare against other real-
time methods.

###  IV-A Experiment Setup

We evaluate the performance of GameOpt+ in a multi-lane four-arm intersection
simulation using the SUMO platform [53] with the following parameters; Control
zone length ($L_{c}$) = $150$m, Speed limit ($\bar{v}$) = $20$m/s Objective
trade-off ($\lambda$) = $0.7$, Safety margins: $M_{sr}$ = $2.0$ and $M_{sl}$ =
$25.0$. The high-level controller uses the TraCI traffic controller interface
to communicate with the simulation. All simulations and optimization
algorithms run on a personal computer with an Intel i7-8750H CPU and 32GB of
RAM.

###  IV-B Evaluation Metrics and Baselines

The key performance metrics used to evaluate control algorithms are
_throughput_ (number of vehicles that can travel through the intersection per
min), _time-to-goal_ (average time vehicles spend in the control zone) and
_fuel consumption_. We also add the metric of _CO2 consumption_ as carbon
emissions are an important criterion in overall vehicle emissions.
Furthermore, to showcase the performance in the presence of heterogeneous
vehicles, we include separate results on _time-to-goal of EVs_ (Emergency
Vehicles) and _fuel consumption of trucks_. To showcase the properties and
appropriately assess the performance of GameOpt+, we compare it with three
other real-time capable baseline approaches using the same inputs. The first
is an auction framework where the bidding strategy is based on the order in
which agents arrive at the intersection, similar to the FIFO principle. To
test the limits of our approach, we also compare against well-tuned traffic
lights (light timing set to maximize performance), a well-established signaled
intersection traffic management system. Additionally, we compare against
another baseline which is a gap-based adaptive traffic light control strategy.
This adaptive strategy allows traffic lights to dynamically adapt to current
traffic conditions in the incoming lanes of an intersection by prolonging
traffic phases whenever a continuous stream of traffic is detected. We refer
to these baselines as Stop-sign, Traffic-Light, and Actuated-Traffic-Light. We
refer to our method as Coop-control. Note that the Krauss vehicle following
model was used in these comparisons.

###  IV-C Performance analysis of GameOpt+

(a) Throughput comparison

(b) Time to goal comparison

Figure 5: Performance in terms of throughput and time-to-goal in comparison to
baselines, with increasing vehicle input flow rate.

The results of these experiments for the two main traffic performance metrics
of throughput and time spent are shown in figure 5. It is observed that our
method (Coop-control) significantly improves performance relative to the
traffic light-based methods with the relative improvement in performance
increasing with increasing input flow rate. This follows our intuition that
advanced multi-agent control methods provide a significant advantage when
congestion is high. At low congestion levels, even simpler methods are often
sufficient. The Stop-sign method’s performance however is very poor even at
moderately high input flow rates. In fact beyond a certain vehicle flow rate,
due to the low throughput in the Stop-sign method, the input lanes become
fully packed and it is impossible to increase the input flow rate any further.
Our proposed Coop-control method is observed to provide improvements to
_throughput_ of around $25\%$ over the Traffic-Light and Actuated-Traffic-
Light methods and around $137\%$ improvement over the Stop-sign method as
shown in figure 5(a). Additionally, as shown in figure 5(b), our Coop-control
method improves the average time spent by vehicles (_time-to-goal_) by around
$70\%$ over the Traffic-Light and Actuated-Traffic-Light methods and around
$83\%$ over the Stop-sign method.

Here, we find that both the timed Traffic-Light and Actuated-Traffic-Light
methods offer similar performance which shows how well the timing on the
Traffic-Light method has been tuned to match the rate of vehicle inflow on
each of the intersections input arms.

(a) Fuel Consumption comparison

(b) CO2 emissions comparison

Figure 6: Performance in terms of fuel consumption and CO2 emissions in
comparison to baselines, with increasing vehicle input flow rate.

The key indicators we consider for efficiency in terms of environmental
factors are total fuel consumption and CO2 emissions. The performance of our
Coop-control method for these metrics is shown in figure 6, where we observe
significant improvements over baseline methods. Once again we observe that the
level of improvement increases at higher input vehicle flow rates. In figure
6(a), we observe a $50\%$ and $80\%$ reduction in fuel consumption relative to
the Traffic-Light and Stop-sign methods respectively. The same trend is
observed for CO2 emissions in figure 6(b), where we see a reduction of $50\%$
and $80\%$ relative to the Traffic-Light and Stop-sign methods respectively.
This ability of our method to reduce fuel usage and CO2 emissions by such
significant margins could have a major impact on overall environmental
sustainability. In our Coop-control method fewer vehicles are forced to
unnecessarily slow down and speed up which equates to less fuel usage to cover
the same distance. Additionally, when acceleration is necessary the control
algorithm attempts to minimize the amount of acceleration required.

(a) EV Time to goal comparison

(b) Truck Fuel Consumption comparison

Figure 7: Performance in terms of emergency vehicle time-to-goal and truck
fuel consumption in comparison to baselines, with increasing vehicle input
flow rate.

To showcase our method’s ability to handle heterogeneous traffic we also show
a comparison of the performance impact for the two major edge cases of
emergency vehicles minimizing their _time-to-goal of EVs_ and the minimizing
of _fuel consumption of trucks_. In a system where each vehicle’s actions can
affect the other neighboring vehicles, these two goals of minimizing time and
fuel consumption are generally opposing each other. However as shown in figure
7, our method can successfully minimize both metrics in order to satisfy the
individual needs of each vehicle class. Over the standard benchmark of the
Traffic-Light method, our Coop-control algorithm is shown to provide
reductions of around $75\%$ and $54\%$ for _time-to-goal of EVs_ and _fuel
consumption of trucks_ respectively. When compared to figures 5(b) and 6(a),
we see that EVs face fewer relative delays than the rest of the traffic and
trucks relatively consume less fuel than the rest of the traffic.

####  IV-C1 Impact of unbalanced traffic inflow on GameOpt+

A major benefit of our method is its ability to adapt to dynamic changes to
the input vehicle flow rate on each of the input arms of the intersection.
When all the arms have equal input flow the system is symmetrical and we
consider the input flow to be balanced. However, when the input flow rate on
one or more of the arms is noticeably higher than the others, we consider the
input flow to be unbalanced. To evaluate our method’s robustness to unbalanced
traffic inflow we conduct experiments where the amount of traffic originating
in the horizontal lanes (from West to East or vice versa) is gradually
increased relative to the traffic originating in the vertical lanes (from
North to South or vice versa). We then plot the same performance metrics
against the increasing ratio of horizontal lane to vertical lane traffic. Note
that in these experiments, to allow for accurate comparisons, the flow rates
on each arm are adjusted so that the overall total input flow rate remains
fixed at $5200\leavevmode\nobreak\ veh/hr$.

(a) Throughput comparison with unbalanced inflow

(b) Time to goal comparison with unbalanced inflow

Figure 8: Performance in terms of throughput and time-to-goal in comparison to
baselines, with unbalanced vehicle input flow rate. Total flow rate fixed at
$5200\leavevmode\nobreak\ veh/hr$.

The effect of unbalanced traffic inflow on throughput and time spent is
presented in figure 8. Our proposed Coop-control method is unperturbed by
changes in the traffic inflow balance. Both the throughput and time spent
remain steady under increasingly unbalanced input flow when our proposed Coop-
control method is used. The timed Traffic-Light approach is the most affected
method, with performance dropping by about $20\%$ and $45\%$ in throughput and
time spent when the balance between horizontal and vertical lanes changes from
$1:1$ to $4:1$. This is expected since the Traffic-Light method timing is
tuned to handle a symmetric load of traffic. As such, in symmetric inflow
conditions ($1:1$) the Traffic-Light performs equivalent to the Actuated-
Traffic-Light method which is designed to adapt to possible changes in traffic
symmetry. Therefore we see a lesser performance drop of around $5\%$ in
throughput in the Actuated-Traffic-Light method when the traffic becomes more
unbalanced. While the Stop-sign method generally performs much worse than its
competitors, we observe an interesting phenomenon of improved performance when
the traffic flow becomes increasingly unbalanced. The Stop-sign method is
inherently designed to handle unbalanced traffic as and when required. When
the traffic is more unbalanced, then the traffic moving through the
intersection is less diverse in terms of possible directions it takes. As such
the vehicles moving in the majority-use directions can pass the intersection
with less waiting especially when they belong to non-conflicting groups. This
is the primary reason the stop sign method performs better when traffic is
less balanced with around a $10\%$ improvement in throughput in more
unbalanced traffic.

(a) Fuel Consumption comparison with unbalanced inflow

(b) CO2 emissions comparison with unbalanced inflow

Figure 9: Performance in terms of fuel consumption and CO2 emissions in
comparison to baselines, with unbalanced vehicle input flow rate. Total flow
rate fixed at $5200\leavevmode\nobreak\ veh/hr$.

The same observations hold in terms of fuel consumption and CO2 emissions as
shown in figure 9. Our Coop-control method which offers the best performance
also maintains this performance irrespective of the balance of traffic flow.
The Traffic-Light shows the highest performance degradation while the
Actuated-Traffic-Light method lies somewhat in between. As in the earlier case
the Stop-sign method performance improves in unbalanced traffic and is
actually capable of achieving fuel consumption related performance equivalent
to the Traffic-Light method in the extreme unbalanced traffic condition.

(a) EV Time to goal comparison with unbalanced inflow

(b) Truck Fuel Consumption comparison with unbalanced inflow

Figure 10: Performance in terms of emergency vehicle time-to-goal and truck
fuel consumption in comparison to baselines, with unbalanced vehicle input
flow rate. Total flow rate fixed at $5200\leavevmode\nobreak\ veh/hr$.

Finally, as shown in figure 10, we find that these same observed trends hold
in the specific heterogeneous vehicle cases of emergency vehicle time to goal
and truck fuel consumption.

Overall we identify that our Coop-control method demonstrates high levels of
robustness to changes in the balance of input traffic flow. It not only
exhibits the highest performance among all other competing methods but is also
able to maintain this level of performance irrespective of the level of
symmetry in the input traffic flow.

##  V Conclusion, Limitations, and Future Work

We introduce GameOpt+, our innovative hybrid solution for cooperative control
at dynamic, multi-lane, unsignalized intersections. Our algorithm combines an
auction mechanism for generating a priority entrance sequence with an
optimization-based trajectory planner to determine optimal velocity commands
aligning with the sequence. This unique approach enables real-time computation
capabilities in high-density multi-lane traffic while ensuring efficiency,
safety, and fairness. Through extensive testing on the SUMO platform, we
validate that GameOpt+ enhances throughput by approximately $25\%$, reduces
time spent by $70\%$, and decreases fuel consumption by $50\%$ compared to
auction-based and signaled approaches involving traffic lights and stop signs.
Additionally, unlike the traffic light baselines which had performance drops,
GameOpt+ is unaffected by unbalanced traffic flow environments. Notably, our
results demonstrate that GameOpt+ operates at remarkable real-time speeds
($<10$ milliseconds), surpassing prior methods by at least $100\times$.

There are several avenues for further research in this domain. One area of
focus would involve investigating various types of auctions to enhance
flexibility in managing intersection control. Different priority orderings of
vehicles can be more efficient for different scenarios. Additionally, it would
be valuable to explore the effects of imperfect communication on the
algorithm’s performance. Real-world systems encounter disruptions and unstable
communication lines, so replicating this would help in creating a more robust
solution. Furthermore, reproducing the information processing capabilities and
delays of the sensors onboard the vehicles would generate a more realistic
simulation.

## References

  * [1] K. O. Yoro and M. O. Daramola, “Co2 emission sources, greenhouse gases, and the global warming effect,” in _Advances in carbon capture_. Elsevier, 2020, pp. 3–28.
  * [2] A. Mikhaylov, N. Moiseev, K. Aleshin, and T. Burkhardt, “Global climate change and greenhouse effect,” _Entrepreneurship and Sustainability Issues_ , vol. 7, no. 4, p. 2897, 2020.
  * [3] M. J. B. Kabeyi and O. A. Olanrewaju, “Sustainable energy transition for renewable and low carbon grid electricity generation and supply,” _Frontiers in Energy research_ , vol. 9, 2022.
  * [4] C. A. Romero, P. Correa, E. A. Ariza Echeverri, and D. Vergara, “Strategies for reducing automobile fuel consumption,” _Applied Sciences_ , vol. 14, no. 2, p. 910, 2024.
  * [5] R. Chandra, U. Bhattacharya, A. Bera, and D. Manocha, “Densepeds: Pedestrian tracking in dense crowds using front-rvo and sparse features,” in _2019 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)_. IEEE, 2019, pp. 468–475.
  * [6] R. Chandra, U. Bhattacharya, T. Randhavane, A. Bera, and D. Manocha, “Roadtrack: Tracking road agents in dense and heterogeneous environments,” 2019.
  * [7] R. Chandra, “Towards autonomous driving in dense, heterogeneous, and unstructured traffic,” Ph.D. dissertation, University of Maryland, College Park, 2022.
  * [8] T. Guan, J. Wang, S. Lan, R. Chandra, Z. Wu, L. Davis, and D. Manocha, “M3detr: Multi-representation, multi-scale, mutual-relation 3d object detection with transformers,” in _Proceedings of the IEEE/CVF winter conference on applications of computer vision_ , 2022, pp. 772–782.
  * [9] J. Guerrero-Ibáñez, S. Zeadally, and J. Contreras-Castillo, “Sensor technologies for intelligent transportation systems,” _Sensors_ , vol. 18, no. 4, p. 1212, 2018.
  * [10] R. Chandra, X. Wang, M. Mahajan, R. Kala, R. Palugulla, C. Naidu, A. Jain, and D. Manocha, “Meteor: A dense, heterogeneous, and unstructured traffic dataset with rare behaviors,” in _2023 IEEE International Conference on Robotics and Automation (ICRA)_. IEEE, 2023, pp. 9169–9175.
  * [11] S. S. S. M. Qadri, M. A. Gökçe, and E. Öner, “State-of-art review of traffic signal control methods: challenges and opportunities,” _European transport research review_ , vol. 12, pp. 1–23, 2020.
  * [12] W. Liu, M. Hua, Z. Deng, Z. Meng, Y. Huang, C. Hu, S. Song, L. Gao, C. Liu, B. Shuai _et al._ , “A systematic survey of control techniques and applications in connected and automated vehicles,” _IEEE Internet of Things Journal_ , 2023.
  * [13] M. Eom and B.-I. Kim, “The traffic signal control problem for intersections: a review,” _European transport research review_ , vol. 12, pp. 1–20, 2020.
  * [14] W. Junhua, L. Boya, Z. Lanfang, and D. R. Ragland, “Modeling secondary accidents identified by traffic shock waves,” _Accident Analysis & Prevention_, vol. 87, pp. 141–147, 2016.
  * [15] O. Grembek, A. A. Kurzhanskiy, A. Medury, P. Varaiya, and M. Yu, “Introducing an intelligent intersection,” _Intelligent Transportation Systems Reports_ , no. 13, 2018.
  * [16] J. Rios-Torres and A. A. Malikopoulos, “A survey on the coordination of connected and automated vehicles at intersections and merging at highway on-ramps,” _IEEE Transactions on Intelligent Transportation Systems_ , vol. 18, no. 5, pp. 1066–1077, 2017.
  * [17] N. Suriyarachchi, F. M. Tariq, C. Mavridis, and J. S. Baras, “Real-time priority-based cooperative highway merging for heterogeneous autonomous traffic,” in _2021 IEEE International Transportation Systems Conference (ITSC)_ , 2021, pp. 2019–2026.
  * [18] N. Suriyarachchi and J. S. Baras, “Shock wave mitigation in multi-lane highways using vehicle-to-vehicle communication,” in _2021 IEEE 94th Vehicular Technology Conference (VTC2021-Fall)_ , 2021, pp. 1–7.
  * [19] B. Asadi and A. Vahidi, “Predictive cruise control: Utilizing upcoming traffic signal information for improving fuel economy and reducing trip time,” _IEEE Transactions on Control Systems Technology_ , vol. 19, no. 3, pp. 707–714, 2011.
  * [20] I. H. Zohdy, R. K. Kamalanathsharma, and H. Rakha, “Intersection management for autonomous vehicles using icacc,” in _2012 15th International IEEE Conference on Intelligent Transportation Systems_ , 2012, pp. 1109–1114.
  * [21] C. Chen, J. Jiang, N. Lv, and S. Li, “An intelligent path planning scheme of autonomous vehicles platoon using deep reinforcement learning on network edge,” _IEEE Access_ , vol. 8, pp. 99 059–99 069, 2020.
  * [22] R. Chandra and D. Manocha, “Gameplan: Game-theoretic multi-agent planning with human drivers at intersections, roundabouts, and merging,” _IEEE Robotics and Automation Letters_ , 2022.
  * [23] D. Carlino, S. D. Boyles, and P. Stone, “Auction-based autonomous intersection management,” in _16th International IEEE Conference on Intelligent Transportation Systems (ITSC)_. IEEE, 2013, pp. 529–534.
  * [24] M. O. Sayin, C.-W. Lin, S. Shiraishi, J. Shen, and T. Başar, “Information-driven autonomous intersection control via incentive compatible mechanisms,” _IEEE Transactions on Intelligent Transportation Systems_ , vol. 20, no. 3, pp. 912–924, 2018.
  * [25] D. Rey, M. W. Levin, and V. V. Dixit, “Online incentive-compatible mechanisms for traffic intersection auctions,” _European Journal of Operational Research_ , 2021.
  * [26] N. Buckman, A. Pierson, W. Schwarting, S. Karaman, and D. L. Rus, “Sharing is caring: Socially-compliant autonomous intersection negotiation,” 2020.
  * [27] W. Schwarting, A. Pierson, J. Alonso-Mora, S. Karaman, and D. Rus, “Social behavior for autonomous vehicles,” _Proceedings of the National Academy of Sciences_ , vol. 116, no. 50, pp. 24 972–24 978, 2019.
  * [28] R. Chandra, U. Bhattacharya, T. Mittal, A. Bera, and D. Manocha, “Cmetric: A driving behavior measure using centrality functions,” _arXiv preprint arXiv:2003.04424_ , 2020.
  * [29] R. Chandra, U. Bhattacharya, T. Mittal, X. Li, A. Bera, and D. Manocha, “Graphrqi: Classifying driver behaviors using graph spectrums,” _arXiv preprint arXiv:1910.00049_ , 2019.
  * [30] R. Chandra, A. Bera, and D. Manocha, “Using graph-theoretic machine learning to predict human driver behavior,” _IEEE Transactions on Intelligent Transportation Systems_ , vol. 23, no. 3, pp. 2572–2585, 2021.
  * [31] N. Li, Y. Yao, I. Kolmanovsky, E. Atkins, and A. R. Girard, “Game-theoretic modeling of multi-vehicle interactions at uncontrolled intersections,” _IEEE Trans. on Intelligent Transportation Systems_ , 2020.
  * [32] R. Tian, N. Li, I. Kolmanovsky, Y. Yildiz, and A. R. Girard, “Game-theoretic modeling of traffic in unsignalized intersection network for autonomous vehicle control verification and validation,” _IEEE Transactions on Intelligent Transportation Systems_ , 2020.
  * [33] A. A. Malikopoulos and L. Zhao, “Optimal path planning for connected and automated vehicles at urban intersections,” in _IEEE Conference on Decision and Control (CDC)_ , 2019, pp. 1261–1266.
  * [34] Y. Bian, S. E. Li, W. Ren, J. Wang, K. Li, and H. X. Liu, “Cooperation of multiple connected vehicles at unsignalized intersections: Distributed observation, optimization, and control,” _IEEE Transactions on Industrial Electronics_ , vol. 67, no. 12, pp. 10 744–10 754, 2020.
  * [35] H. Pei, Y. Zhang, Y. Zhang, and S. Feng, “Optimal cooperative driving at signal-free intersections with polynomial-time complexity,” _IEEE Transactions on Intelligent Transportation Systems_ , pp. 1–13, 2021.
  * [36] S. A. Fayazi and A. Vahidi, “Mixed-integer linear programming for optimal scheduling of autonomous vehicle intersection crossing,” _IEEE Transactions on IV_ , vol. 3, no. 3, pp. 287–299, 2018.
  * [37] A. P. Capasso, P. Maramotti, A. Dell’Eva, and A. Broggi, “End-to-end intersection handling using multi-agent deep reinforcement learning,” _arXiv preprint arXiv:2104.13617_ , 2021.
  * [38] A. Mavrogiannis, R. Chandra, and D. Manocha, “B-gap: Behavior-rich simulation and navigation for autonomous driving,” _IEEE Robotics and Automation Letters_ , vol. 7, no. 2, pp. 4718–4725, 2022.
  * [39] ——, “B-gap: Behavior-guided action prediction and navigation for autonomous driving,” _arXiv preprint arXiv:2011.03748_ , 2020.
  * [40] A. J. Sathyamoorthy, J. Liang, U. Patel, T. Guan, R. Chandra, and D. Manocha, “Densecavoid: Real-time navigation in dense crowds using anticipatory behaviors,” in _2020 IEEE International Conference on Robotics and Automation (ICRA)_. IEEE, 2020, pp. 11 345–11 352.
  * [41] J. Roh, C. Mavrogiannis, R. Madan, D. Fox, and S. S. Srinivasa, “Multimodal trajectory prediction via topological invariance for navigation at uncontrolled intersections,” _arXiv preprint arXiv:2011.03894_ , 2020.
  * [42] R. Chandra, U. Bhattacharya, A. Bera, and D. Manocha, “Traphic: Trajectory prediction in dense and heterogeneous traffic using weighted interactions,” in _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition_ , 2019, pp. 8483–8492.
  * [43] R. Chandra, U. Bhattacharya, C. Roncal, A. Bera, and D. Manocha, “Robusttp: End-to-end trajectory prediction for heterogeneous road-agents in dense traffic with noisy sensor inputs,” in _ACM Computer Science in Cars Symposium_ , 2019, pp. 1–9.
  * [44] R. Chandra, T. Guan, S. Panuganti, T. Mittal, U. Bhattacharya, A. Bera, and D. Manocha, “Forecasting trajectory and behavior of road-agents using spectral clustering in graph-lstms,” _IEEE Robotics and Automation Letters_ , vol. 5, no. 3, pp. 4882–4890, 2020.
  * [45] N. Suriyarachchi, R. Chandra, J. S. Baras, and D. Manocha, “Gameopt: Optimal real-time multi-agent planning and control for dynamic intersections,” in _2022 IEEE 25th International Conference on Intelligent Transportation Systems (ITSC)_. IEEE, 2022, pp. 2599–2606.
  * [46] T. Roughgarden, _Twenty lectures on algorithmic game theory_. Cambridge University Press, 2016.
  * [47] M. Wang, N. Mehr, A. Gaidon, and M. Schwager, “Game-theoretic planning for risk-aware interactive agents,” _IROS_ , 2020.
  * [48] T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, _Introduction to algorithms_ , 2009.
  * [49] X. Du, M. Su, X. Zhang, and X. Zheng, “Bidding for multiple keywords in sponsored search advertising: Keyword categories and match types,” _Information Systems Research_ , vol. 28, no. 4, pp. 711–722, 2017.
  * [50] R. Colini-Baldeschi, S. Leonardi, M. Henzinger, and M. Starnberger, “On multiple keyword sponsored search auctions with budgets,” _ACM Transactions on Economics and Computation (TEAC)_ , vol. 4, no. 1, pp. 1–34, 2015.
  * [51] GameOpt, “Gameopt project supplementary material,” 2022. [Online]. Available: https://gamma.umd.edu/gameopt
  * [52] L. Gurobi Optimization, “Gurobi optimizer reference manual,” 2021. [Online]. Available: http://www.gurobi.com
  * [53] P. A. Lopez, M. Behrisch, L. Bieker-Walz, J. Erdmann, Y.-P. Flötteröd, R. Hilbrich, L. Lücken, J. Rummel, P. Wagner, and E. Wießner, “Microscopic traffic simulation using sumo,” in _IEEE International Conference on Intelligent Transportation Systems_. IEEE, 2018.