# Learning energy-efficient driving behaviors by imitating experts

Abdul Rahman Kreidieh1,2, Zhe Fu2, and Alexandre M. Bayen2 1Corresponding
author, email<EMAIL_ADDRESS>of California, Berkeley

###### Abstract

The rise of vehicle automation has generated significant interest in the
potential role of future automated vehicles (AVs). In particular, in highly
dense traffic settings, AVs are expected to serve as congestion-dampeners,
mitigating the presence of instabilities that arise from various sources.
However, in many applications, such maneuvers rely heavily on non-local
sensing or coordination by interacting AVs, thereby rendering their adaptation
to real-world settings a particularly difficult challenge. To address this
challenge, this paper examines the role of imitation learning in bridging the
gap between such control strategies and realistic limitations in communication
and sensing. Treating one such controller as an “expert”, we demonstrate that
imitation learning can succeed in deriving policies that, if adopted by 5% of
vehicles, may boost the energy-efficiency of networks with varying traffic
conditions by 15% using only local observations. Results and code are
available online at https://sites.google.com/view/il-traffic/home.

##  I Introduction

Autonomous driving systems have the potential to vastly improve the quality
and efficiency of existing transportation systems. With fast reaction times
and socially optimal behaviors, _automated vehicles_ (AVs) can improve the
road capacity and traffic flow stability of existing networks [1, 2, 3, 4, 5],
as well as reduce instances of vehicle collisions and similar incidents
brought about by human errors [6]. The promise of such systems, however, is
seldom witnessed in practice [7, 8], highlighting the challenge that lies
ahead.

For the condition of addressing traffic flow instabilities in highway
networks, longitudinal motion planning systems have been at the core of the
conversation [9, 10]. Even in _mixed-autonomy_ settings, whereby only a subset
of vehicles act as AVs, such systems have been demonstrated to provide
significant improvements to both network throughput and energy-efficiency. In
their seminal work, for instance, the authors of [3] empirically demonstrate
that even at low penetration rates, AVs driving at the equilibrium free-flow
speed of a single-lane ring road can effectively stabilize traffic conditions
for all vehicles involved, reducing system-level fuel consumption by $40$% in
the process. Such maneuvers, however, rely on prior knowledge of free-flow
conditions, or access to non-local sensing and communication apparatuses from
which to estimate them [11], making these maneuvers difficult to adapt to
arbitrary highway networks.

In this paper, we demonstrate that _imitation learning_ (IL) techniques can
help alleviate the need for non-local traffic state estimates in expertly
designed AV controllers. Looking to multi-lane highways in particular, we
construct a controller inspired by the work of [3] that dissipates the
formation of stop-and-go traffic, but relies on downstream information to do
so. Next, we apply IL to the controller and validate that such techniques,
when properly deployed, can learn patterns in locally observable features that
negate the need for such information, resulting in AV driving policies that
operate as if they are knowledgeable of the state of downstream traffic. These
findings suggest that techniques such as IL can serve an important role in
adapting traffic smoothing controllers to limitations that arise in the real
world.

The primary contributions of this paper are:

  * •

We design a controller (serving as the expert) that, through some degree of
non-local sensing, dissipates the formation of stop-and-go waves within open
highway networks.

  * •

We identify key limitations in both the expert model and training procedure
that limit the efficacy of IL and describe methods for addressing them. These
include introducing temporal reasoning through the state representation and
modifying the expert to allow it to recover from errors.

  * •

Finally, we study the performance and robustness of the imitated policies,
demonstrating that the policy succeeds at nearly perfectly matching the
performance of the expert without the need for non-local state information.

The remainder of this paper is organized as follows. Section II provides an
overview of imitation learning and mixed-autonomy traffic. Section III
outlines the problem setup, expert, and IL approach. Section IV presents the
findings and results of computational experiments over a wide variety of
traffic states and compares the performance of the expert and imitated
policies. Finally, Section V provides concluding remarks and potential avenues
for future work.

##  II Related Work

###  II-A Traffic congestion and mixed-autonomy traffic

Traffic congestion is a state of traffic characterized by slower speeds,
longer trip times, and increased instances of vehicular queuing. The presence
of such phenomena degrades the quality and efficiency of existing networks,
resulting in reduced fuel efficiency [12] and increased incidents of road rage
[13] and vehicle-to-vehicle collisions [14]. As a result, solutions for such
phenomena have been of primary interest within the transportation community.

The present study focuses on a form of congestion common to typical highways.
Within these settings, congestion appears as _stop-and-go waves_ ,
characterized by periodic, sudden, and at times sharp oscillations in driving
speeds. Interestingly, these waves emerge even in the absence of external
disturbances. For example, in simplified networks such as ring roads, small
fluctuations arising from heterogeneities in human driving behaviors can
produce higher amplitude oscillations by following vehicles as they break
harder to avoid unsafe settings [15]. This response, termed _string
instability_ [16], results in the formation of stop-and-go waves as
oscillations propagate deeper through a platoon.

The presence of string instabilities in human driving highlights a potential
benefit for upcoming automated driving systems. In particular, if properly
implemented, AVs can reduce the effects of such instabilities amongst one
another [17], and by influencing the behaviors of neighboring vehicles may
succeed at mitigating congestion in _mixed autonomy_ settings, where only a
subset of vehicles are automated. In [3], for instance, the authors
demonstrate that stop-and-go waves in ring road settings can be dampened by
operating as few as 5% of vehicles at the effective _equilibrium speed_ of the
network. The control strategy applied to the AVs, termed the _Follower
Stopper_ , acts as a velocity controller, navigating the speeds of automated
vehicles to a predefined desired speed $U$ (set to the equilibrium speed)
while maintaining a safe gap with the vehicle ahead. Following this model, the
command velocity $v^{\text{cmd}}$ of an AV is defined as:

$v^{\text{cmd}}=\begin{cases}0&\text{if }h_{\alpha}\leq\Delta x_{1}\\\
v\frac{\Delta x-\Delta x_{1}}{\Delta x_{2}-\Delta x_{1}}&\text{if }\Delta
x_{1}\leq h_{\alpha}\leq\Delta x_{2}\\\ v+(U-v)\frac{\Delta x-\Delta
x_{2}}{\Delta x_{3}-\Delta x_{2}}&\text{if }\Delta x_{2}\leq
h_{\alpha}\leq\Delta x_{3}\\\ U&\text{otherwise}\end{cases}$

(1)

where $v=\text{min}(\text{max}(v_{l},0),U)$ and $\Delta x_{k}$ is defined as:

$\Delta x_{k}=\Delta x_{k}^{0}+\frac{1}{2d_{k}}(\Delta v_{-})^{2},\ \ k=1,2,3$
(2)

where $\Delta v_{-}=\min(\Delta v,0)$ is the negative arm of difference
between the speed of the lead vehicle and the AV. This intermediary desired
speed in then converted to approach acceleration or torque commands via some
form of lower-level control. In this paper, we exploit this final controller
when designing our congestion-mitigating expert. The parameters used for this
model are provided in Table I.

(a) Network configuration

(b) Human-driven baseline

(c) Expert controller performance

Figure 1: An illustration of the explored network. Top: We explore the
application of congestion-mitigating strategies on a section of the I-210
network. Bottom left: In the absence of automation, restrictions to the
outflow of vehicles from a slower-moving downstream edge result in the
formation of stop-and-go waves. Bottom right: To mitigate congestion, we
design an expert inspired by the Follower Stopper. This expert, which exploits
downstream information from the network, can succeed in reducing the
propagation of waves.

| Intelligent Driver Model (IDM)
---|---
Parameter | $v_{0}$ | $T$ | $a$ | $b$ | $\delta$ | $s_{0}$ | $\epsilon$
Value | $30$ | $1$ | $1.3$ | $2.0$ | $4$ | $2$ | $\mathcal{N}(0,0.3)$

| Follower Stopper
---|---
Parameter | $\Delta x_{1}^{0}$ | $\Delta x_{2}^{0}$ | $\Delta x_{3}^{0}$ | $d_{1}$ | $d_{2}$ | $d_{3}$ | $a_{\max}$
Value | $4.5$ | $5.25$ | $6.0$ | $1.5$ | $1.0$ | $0.5$ | $1$

TABLE I: Model parameters

###  II-B Imitation learning

Imitation learning (IL) refers to a class of algorithms that attempt to
develop a policy $\pi_{\theta}(s_{t}):\mathcal{S}\to\mathcal{A}$, parametrized
by $\theta$, that matches the behavior of an expert $\pi^{*}$ through
demonstrations of the performance of the expert within an environment. Let
$\mathcal{D}=\left\\{(s_{i},a_{i})\right\\}_{i=1}^{N}$ denote a dataset of
(state, action) demonstrations provided by an expert. In this setting, the
objective of an IL algorithm is to solve the problem:
$\theta:=\text{argmin}_{\theta}\left[\mathbb{E}_{\mathcal{D}}\left[\mathcal{L}(\pi_{\theta}(s_{i}),a_{i})\right]\right]$,
where $\mathcal{L}(\cdot,\cdot)$ is a distance metric between the predicted
and expert action. For this work, we use a mean-square error loss function.

Imitation learning, and its role in autonomous driving, has grown rapidly
since its initial deployment via ALVINN [18]. Nowadays, IL methods in
autonomous driving have become valuable tools for model compression. In [19],
for instance, these methods are used to compress computationally complex AV
control strategies based on model-predictive control (MPC) into faster neural
network representations. More broadly, IL has been actively being explored as
a means of reducing the complexity of ruled-based approaches for autonomous
driving into relatively simple end-to-end models trained to replicate the
behaviors of human drivers [20, 21]. These findings and similar ongoing work
highlight the potential benefits and adaptability of IL within the domain of
driving. Taking inspiration from the above studies, we explore the ability of
IL to compress behaviors of AV models reliant on knowledge from non-local
state information into policies that are more conducive for real-world
settings.

##  III Experimental Setup

In this section, we detail the considered problem and design an expert
controller which, using non-local estimates of traffic, can dissipate the
formation and propagation of congestion in the considered setting. We then
present an IL paradigm through which the presented controller can be redefined
to dissipate congestion in arbitrary traffic conditions using only locally
perceptible state information.

###  III-A Network configuration

We explore the problem of designing congestion-mitigating strategies for AVs
in multi-lane highways. The network considered, see Figure 1(a), is a
simulation of a $1$-mile section of the I-210 network in Los Angeles,
California. This network has been the topic of considerable research in recent
years, with various studies aiming to identify and reconstruct the source of
congestion within it [22, 23]. This paper in particular builds on the work of
[24], which explores the role of mixed-autonomy traffic systems in improving
the energy-efficiency of vehicles within I-210.

Within this network, congestion is generated via an imbalance between the
inflow and outflow conditions. In particular, high inflow rates matching peak
demand intervals are provided from the leftmost edge, and outflow rates are
restricted via a reduced speed limit within the rightmost $100$ m. These
restrictions serve to model various downstream effects, including from slow-
moving or stopping bottlenecks and downstream arterial or merges networks. The
overall imbalance increases the density of the network, which coupled with
string-instabilities in human-driver dynamics111To model string instabilities
within the network, we use the _Intelligent Driver Model_ (IDM) [25]. The
specific model parameters are in Table I. results in the onset of stop-and-go
traffic. Figure 1(b) depicts this behavior in the fully human-driven setting.

###  III-B Dissipating stop-and-go waves via non-local sensing

To dissipate the emergence of stop-and-go waves within this network in mixed-
autonomy settings, we seek to adapt to the work of [3] (see Section II-A) to
multi-lane highways. To do so, we must first define a distribution of desired
speeds that consistently dissipate the formation of waves within the network.
For the problem explored within this paper, we take inspiration from ramp-
metering systems for traffic signal control [26, 27]. Through such systems,
free-flow conditions in high-demand, throughput-restricted networks are
sustained by bounding the inflow of vehicles below a network’s breakdown
capacity. Similarly, by driving near the outflow conditions of a given
network, AVs can restrict the flow of vehicles upstream, thereby preventing
the buildup of dense traffic and formation of subsequent stop-and-go waves. We
accordingly choose to set the desired speed $U$ of AVs within the Follower
Stopper to match the downstream speed of the network.

Figure 1(c) depicts the performance of the aforementioned controller for an AV
penetration rate of 5%. Seen here, the AVs succeed at dissipating the
formation of stop-and-go waves, resulting in more uniform driving speeds
across the network. This is true for a range of downstream boundaries
conditions where stop-and-go congestion occurs and results in significant
reductions to energy consumption. This solution, however, requires knowledge
of downstream information, which may be unavailable. In the following
subsection, we explore methods for subverting this limitation via IL.

###  III-C Absolving the dependence on non-local states

In this paper, we aim to determine whether control strategies similar to the
one presented previously may be derived from features observable to individual
AVs. Specifically, for a given AV $\alpha$, we seek to design a controller
$\pi_{\theta}(v_{\alpha},h_{\alpha},v_{l})$ which maps actions by the expert
Follower Stopper controller $a_{\text{FS}}(v_{\alpha},h_{\alpha},v_{l},U)$
solely to the variables $v_{\alpha}$, $v_{l}$, $h_{\alpha}$, while abolishing
the reliance on the non-local desired speed term $U$. To do so, we explore the
use of the IL methods described in Section II while treating the Follower
Stopper as the expert. This process introduces several challenges that must be
addressed. We describe the two most prominent challenges and introduce
techniques to mitigate them in practice.

####  III-C1 Challenge #1: Unobservability of downstream state

The first of these challenges accounts for the absence of non-local
observations for the imitated policy. The use of purely local observations
confounds the expert’s behavior across varying downstream conditions, thereby
making specialization to unique downstream events difficult. In response to
this challenge, we hypothesize that local historical data can be exploited to
estimate traffic flow properties further downstream. In particular,
fluctuations in driving speeds from the perspective of an AV, or the act of
approaching or moving away from a lead vehicle over time, may provide useful
information on the effective equilibrium speed of a given network in relation
to one’s own. To validate this assumption, we introduce additional temporal
information to the state space of the imitated policy. Specifically, we
concatenate to the original observation of an AV the past $N$ states,
collected at a sampling rate of $\Delta t$. For this problem, the following
constants are chosen: $N=5$ and $\Delta t=2$.

Figure 2: Behavior of the Follower Stopper when following a leader with and
without gap recovery. The original controller, in green, cannot address gaps
after an error is introduced. Conversely, the modified controller, in orange,
tends towards its prior trajectory.

(a) Without gap recovery

(b) Without temporally extended observations

(c) Final approach

Figure 4: Spatio-temporal comparison of the imitated model for an inflow rate
of $2100$ veh/hr/lane and downstream speed limit of $5$ m/s. a) When gap-
recovery is not enforced within the expert, AVs learn to form large gaps with
their leaders whenever possible, resulting in the emergence of more pronounced
waves in adjacent lanes. b) When additional temporal knowledge is not
provided, the imitated policy does performs well, but fails to dissipate waves
as frequently as the expert. c) The final approach succeeds in identifying and
driving at the effective speed of the network, and in doing so dissipates the
vast majority of emerging stop-and-go waves in each individual lane.

####  III-C2 Challenge #2: Recovering from errors

The second of these limitations accounts for features within the expert that
are non-conducive for IL. In many driving applications (e.g. lane-keeping
[28]), IL methods rely on demonstrations of how to recovery from non-optimal
or erroneous trajectories to produce safe and robust behaviors. For
longitudinal driving tasks explored here, errors emerge in the form of large
gaps. In particular, at the early stages of training, the imitated policy
often does not produce actions that maintain the speed desired by the expert,
instead slowing down and allowing its leader to outpace it. While this is to
be expected, the Follower Stopper does not inform policies how to recover from
such errors, instead opting to maintain a constant speed despite the magnitude
of the gap ahead. As a result, the presence of such errors and the absence of
labels that correct for them introduces an incentive to maintain large
headways, which may result in additional undesirable behaviors.

In order to address this challenge, we introduce an additive term to the final
condition of the expert, thereby informing the AVs to reduce the gap when
large values emerge. The modified Follower Stopper command speeds is:

$v^{\text{cmd}}=\begin{cases}0&\text{if }\Delta x\leq\Delta x_{1}\\\
v\frac{\Delta x-\Delta x_{1}}{\Delta x_{2}-\Delta x_{1}}&\text{if }\Delta
x_{1}\leq\Delta x\leq\Delta x_{2}\\\ v+(U-v)\frac{\Delta x-\Delta
x_{2}}{\Delta x_{3}-\Delta x_{2}}&\text{if }\Delta x_{2}\leq\Delta x\leq\Delta
x_{3}\\\ U{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}+\
c(\Delta x-\Delta x_{3})^{2}}&\text{otherwise}\end{cases}$

(3)

where $c$ is a constant term that toggles the rate at which recovery occurs,
and is set to $0.001$ in future experiments.

Figure 2 depicts the performance of the original and modified Follower Stopper
in the presence of gap-inducing errors. The benefit of this modification
becomes evident under this setting, with the modified controller clearing the
gap and the original failing to do so.

###  III-D Simulation and training procedure

Experiments are conducted in Flow [29], an open-source framework designed to
enable the integration of machine learning tools with microscopic simulations
of traffic. Within Flow, simulations of the I-210 are executed in SUMO [30]
with step sizes of $0.4$ sec/step and are warmed-started for $3600$ sec to
allow for the onset of congestion before being run within the training
procedure an additional $600$ sec. Each simulation is initialized with a
random set of boundary conditions, sampled from a distribution of [$1900$,
$2300$] veh/hr/lane in increments of $50$ for the inflow conditions, and [$5$,
$7$] m/s in increments of $1$ for the downstream speed limit. Once the warmup
period is finished, $5$% of vehicles are replaced with AVs whose actions are
sampled either from the expert or policy to mimic a similar penetration rate.

For all experiments in this paper, we use DAgger [31] for imitating the
desired behavior by the expert. We initialize the expert dataset with
$30\text{k}$ samples extracted from $20$ rollouts of the expert for varying
inflow rate and downstream speed limit conditions and, after each training
epoch, aggregate the dataset with $7.5\text{k}$ new samples from states
visited by the imitated policy. This is repeated for $100$ training epoch for
a total of $750\text{k}$ samples. Finally, a Multi-Layer Perceptron is used
with hidden layers $(32,32,32)$ and a ReLU non-linearity. This policy is
updated using Adam [32] with a learning rate of $0.001$ and batch size of
$128$, and dropout [33] is employed to allow for increased robustness.

##  IV Numerical Results

In this section, we present numerical results for the expert and imitated
policy presented in the previous section. Through these results, we aim to
answer the following:

  1. 1.

Does the imitated policy succeed in improving the traffic stability and
energy-efficiency of vehicles within the network for different traffic
conditions?

  2. 2.

Is the introduction of temporal reasoning and gap recovery to the imitated and
expert models, respectively, needed for proper training to occur?

  3. 3.

Is the imitated policy robust to unseen variations in network and human-driver
behaviors?

Imitation learning runs for the various experimental setups are executed over
$5$ seeds, and the training performance is averaged and reported across all
seeds to account for stochasticity between simulations and policy
initialization.

###  IV-A Performance comparison

Figure 4(c) depicts the spatio-temporal performance of the imitated policy for
a unique traffic state. As we can see, the learned behavior largely succeeds
in mitigating the frequency and intensity of stop-and-go waves that arise in
the fully human-driven setting (see Figure 1(b)), resulting in more uniform
driving speeds throughout the network. Moreover, this behavior closely matches
that by the expert in Figure 1(c), suggesting that the imitation procedure was
successful.

The performance of the imitated policy in comparison to the expert is further
elucidated in Figure 6. Within this figure, we compare the ability for both
the expert and imitated policy to improve the energy-efficiency of the studied
network based on two metrics: 1) a model of energy consumption, in miles per
gallon, fitted to Toyota RAV4 emission data [24], and 2) the magnitude of
accelerations by both the human and automated vehicles within the network. We
also compare the throughput of the network (in veh/hr/lane) to ensure any
improvements to the energy-efficiency of the network do not emerge at the cost
of mobility. As we can see, the energy-efficiency of both the expert and
imitated policy match one another very closely, producing values of $34.5$ mpg
and $34.4$ mpg respectively in terms of energy consumption (a $15$%
improvement over the baseline value of $29.6$ mpg), and values of $0.242$ m/s2
and $0.240$ m/s2 respectively in terms of fluctuations in speed (a $60$%
reduction over the baseline value of $0.604$ m/s2). The two also only
experience very minor reductions in network throughput of around $2$%,
suggesting that the improvements to energy do not come at the cost of
mobility. Remarkably, from the perspective of the imitated policy, this
behavior emerges in the absence of non-local (downstream) knowledge of the
state of traffic, demonstrating the potential for imitation learning to
augment and even improve the quality of existing AV control strategies.

.

Baseline (no control)

Expert

Imitated (current
timestep)

Imitated (current +
previous timesteps)

.Energyefficiency

.Acceleration

.Outflow rate

Figure 6: Performance of different models for different traffic conditions.
Both the expert model (Follower Stopper) and imitated policies provide
significant improvements to both energy-efficiency and the frequency and
magnitude of accelerations without significantly degrading network throughput.
This is true for all sampled inflow / downstream speed limit pairs.

###  IV-B Ablation studies

Next, we explore the effect of the various augmentations presented in Section
III-C on the performance of the resultant policy. Figure 4 depicts the learned
behaviors when a number of the proposed methods are removed from the training
procedure. In the absence of gap recovery during the training procedure, the
imitated policy produces undesirable large gaps in several lanes as marked by
the red circles. These gaps, coupled with the lane-change dynamics of human
vehicles, produce distributions of highly dense traffic in adjacent lanes that
enable the further propagation of congestion, thereby negating the desired
behaviors of the AVs as congestion mitigators. Alternatively, when gap
recovery is enforced through the expert model but only the current time step
is perceived through the input observation space, gaps do disappear and waves
are further dissolved, however, the regularity at which waves emerge is
greater than is experienced when additional temporal information is provided
to the imitated model.

The performance gap when temporally extended state information is not provided
is further highlighted in Figure 6. As seen in this figure, the use of current
time-step information does perform well in terms of the studied energy-
consumption model and network throughput when compared to the expert model.
The disparity, however, is evident in terms of fluctuations in vehicle speeds,
producing average acceleration/deceleration values of $0.278$ m/s2, $15$%
greater than the expert model and imitated model with temporally extended
information. This concurs with the increased emergence of waves in Figure 4,
and in the presence of vehicles with different energy emission properties may
result in a degradation in the energy-efficiency of the network in comparison
to more fine-tuned models. These findings reinforce the notion that temporal
reasoning is needed to properly imitate models that utilize non-local state
information.

###  IV-C Robustness to unseen phenomena

Finally, we explore the robustness of imitated behaviors to unseen variations
to the task at training time. In particular, we explore two types of
variations. For one, we alter the penetration rate of AVs to determine whether
the changes to the dynamics associated with such values negatively degrade the
performance of the policy. Next, we look to variations in the responsiveness
and aggressiveness of the car-following and lane-change models, respectively.
Specifically, for the car-following behaviors, we alternate the maximum
acceleration, or $a$ term, which controls the human’s ability to respond to
existing waves. Conversely, for the lane-change model, we modify the lane-
change frequency parameter of the model, with larger values of this parameter
resulting in more aggressive lane changes by the human drivers.

Figure 8 depicts the performance of the baseline, expert, and imitated
policies for the aforementioned variations in simulation parameters. For the
variations in AV penetration rate, we explore the influence of varying
downstream speed limits as well but set the inflow rate to a fixed value of
$2100$ veh/hr/lane for each run. Moreover, for the variations in human-driver
model parameters, we restrict the analysis to a single pair of boundary
conditions of $2100$ veh/hr/lane and $5$ m/s. As we can see from this figure,
the imitated policies generalize well to different penetration rates, reducing
slightly for low penetration rates of $2.5$%, but outperforming the expert at
higher penetration rates. For modifications to the human-driver models, a
performance gap does begin to emerge between the expert and imitated policy
for large changes to the parameters; however, the imitated policy does
continue to outperform the human-driven baseline for all regions in which the
expert outperforms as well. The gap is also reduced once temporally extended
state information is introduced, further highlighting the benefit of this
approach.

Baseline (no control)

Expert

Imitated (current
timestep)

Imitated (current +
previous timesteps)

.

Figure 8: Generalizability of the learned policy to different AV penetration
rates (top) and human-driver conditions (bottom). The original training regime
is bordered in red. We find that the imitated policy generalizes relatively
well, continuing to outperform the baseline in all settings. The policy
imitated with additional temporal information also succeeds in generally
better outside its training scheme.

##  V Conclusion

This paper explores the problem of designing congestion-mitigating control
strategies for automated vehicles in mixed-autonomy highways. For one, it
demonstrates that such strategies can be achieved by aligning the speeds of a
number of vehicles with the effective speed of downstream traffic, thereby
preventing the onset of dense traffic. Next, through imitation learning it
demonstrates that such strategies can be mapped to observations that are
locally perceivable to individual vehicles, producing a purely decentralized
controller that does not require feedback from non-local sources. This final
behavior is shown to improve the energy-efficiency of the explored network for
values as high as $15$% while effectively eliminating the presence of most
waves.

As a topic of ongoing work, we aim to determine whether similar control design
strategies can be applied to real-world driving settings. In particular, we
aim to validate the performance of this control strategy on trajectories of
human driving provided by the real world.

## Acknowledgments

This material is based upon work supported by the U.S. Department of Energy’s
Office of Energy Efficiency and Renewable Energy (EERE) award number CID DE-
EE0008872. The views expressed herein do not necessarily represent the views
of the U.S. Department of Energy or the United States Government.

## References

  * [1] Z. Wadud, D. MacKenzie, and P. Leiby, “Help or hindrance? the travel, energy and carbon impacts of highly automated vehicles,” _Transportation Research Part A: Policy and Practice_ , vol. 86, pp. 1–18, 2016.
  * [2] A. Talebpour and H. S. Mahmassani, “Influence of connected and autonomous vehicles on traffic flow stability and throughput,” _Transportation Research Part C: Emerging Technologies_ , vol. 71, pp. 143–163, 2016.
  * [3] R. E. Stern, S. Cui, M. L. Delle Monache, R. Bhadani, M. Bunting, M. Churchill, N. Hamilton, H. Pohlmann, F. Wu, B. Piccoli _et al._ , “Dissipation of stop-and-go waves via control of autonomous vehicles: Field experiments,” _Transportation Research Part C: Emerging Technologies_ , vol. 89, pp. 205–221, 2018.
  * [4] C. Wu, A. Kreidieh, E. Vinitsky, and A. M. Bayen, “Emergent behaviors in mixed-autonomy traffic,” in _Conference on Robot Learning_. PMLR, 2017, pp. 398–407.
  * [5] A. R. Kreidieh, C. Wu, and A. M. Bayen, “Dissipating stop-and-go waves in closed and open networks via deep reinforcement learning,” in _2018 21st International Conference on Intelligent Transportation Systems (ITSC)_. IEEE, 2018, pp. 1475–1480.
  * [6] M. Blanco, J. Atwood, S. M. Russell, T. Trimble, J. A. McClafferty, and M. A. Perez, “Automated vehicle crash rate comparison using naturalistic data,” Virginia Tech Transportation Institute, Tech. Rep., 2016.
  * [7] G. Gunter, D. Gloudemans, R. E. Stern, S. McQuade, R. Bhadani, M. Bunting, M. L. Delle Monache, R. Lysecky, B. Seibold, J. Sprinkle _et al._ , “Are commercially implemented adaptive cruise control systems string stable?” _IEEE Transactions on Intelligent Transportation Systems_ , 2020.
  * [8] J. Claybrook and S. Kildare, “Autonomous vehicles: No driver… no regulation?” _Science_ , vol. 361, no. 6397, pp. 36–37, 2018.
  * [9] H. Zhou and J. Laval, “Longitudinal motion planning for autonomous vehicles and its impact on congestion: A survey,” _arXiv preprint arXiv:1910.06070_ , 2019.
  * [10] S. Siri, C. Pasquale, S. Sacone, and A. Ferrara, “Freeway traffic control: A survey,” _Automatica_ , vol. 130, p. 109655, 2021.
  * [11] T. Seo, A. M. Bayen, T. Kusakabe, and Y. Asakura, “Traffic state estimation on highway: A comprehensive survey,” _Annual reviews in control_ , vol. 43, pp. 128–151, 2017.
  * [12] M. Treiber, A. Kesting, and C. Thiemann, “How much does traffic congestion increase fuel consumption and emissions? applying a fuel consumption model to the ngsim trajectory data,” in _87th Annual Meeting of the Transportation Research Board, Washington, DC_ , 2008, p. 71.
  * [13] D. A. Hennessy and D. L. Wiesenthal, “Traffic congestion, driver stress, and driver aggression,” _Aggressive Behavior: Official Journal of the International Society for Research on Aggression_ , vol. 25, no. 6, pp. 409–423, 1999.
  * [14] P. Marchesini and W. A. M. Weijermars, _The relationship between road safety and congestion on motorways_. SWOV Institute for Road Safety Research Leidschendam, Netherlands, 2010.
  * [15] Y. Sugiyama, M. Fukui, M. Kikuchi, K. Hasebe, A. Nakayama, K. Nishinari, S.-i. Tadaki, and S. Yukawa, “Traffic jams without bottlenecks—experimental evidence for the physical mechanism of the formation of a jam,” _New journal of physics_ , vol. 10, no. 3, p. 033001, 2008.
  * [16] D. Swaroop and J. K. Hedrick, “String stability of interconnected systems,” _IEEE transactions on automatic control_ , vol. 41, no. 3, pp. 349–357, 1996\.
  * [17] X.-Y. Lu, J. K. Hedrick, and M. Drew, “Acc/cacc-control design, stability and robust performance,” in _Proceedings of the 2002 American Control Conference (IEEE Cat. No. CH37301)_ , vol. 6. IEEE, 2002, pp. 4327–4332.
  * [18] D. A. Pomerleau, “Alvinn: An autonomous land vehicle in a neural network,” CARNEGIE-MELLON UNIV PITTSBURGH PA ARTIFICIAL INTELLIGENCE AND PSYCHOLOGY …, Tech. Rep., 1989.
  * [19] L. Sun, C. Peng, W. Zhan, and M. Tomizuka, “A fast integrated planning and control framework for autonomous driving via imitation learning,” in _Dynamic Systems and Control Conference_ , vol. 51913. American Society of Mechanical Engineers, 2018, p. V003T37A012.
  * [20] M. Bansal, A. Krizhevsky, and A. Ogale, “Chauffeurnet: Learning to drive by imitating the best and synthesizing the worst,” _arXiv preprint arXiv:1812.03079_ , 2018.
  * [21] F. Codevilla, M. Müller, A. López, V. Koltun, and A. Dosovitskiy, “End-to-end driving via conditional imitation learning,” in _2018 IEEE International Conference on Robotics and Automation (ICRA)_. IEEE, 2018, pp. 4693–4700.
  * [22] G. Gomes, A. May, and R. Horowitz, “Congested freeway microsimulation model using vissim,” _Transportation Research Record_ , vol. 1876, no. 1, pp. 71–81, 2004.
  * [23] F. Dion, J. Butler, L. Hammon, and Y. Xuan, “Connected corridors: I-210 pilot integrated corridor management system concept of operations,” _California PATH, Berkeley, CA_ , 2015.
  * [24] J. W. Lee, G. Gunter, R. Ramadan, S. Almatrudi, P. Arnold, J. Aquino, W. Barbour, R. Bhadani, J. Carpio, F.-C. Chou _et al._ , “Integrated framework of vehicle dynamics, instabilities, energy models, and sparse flow smoothing controllers,” _arXiv preprint arXiv:2104.11267_ , 2021.
  * [25] M. Treiber, A. Hennecke, and D. Helbing, “Congested traffic states in empirical observations and microscopic simulations,” _Physical review E_ , vol. 62, no. 2, p. 1805, 2000.
  * [26] M. Papageorgiou, H. Hadj-Salem, J.-M. Blosseville _et al._ , “Alinea: A local feedback control law for on-ramp metering,” _Transportation Research Record_ , vol. 1320, no. 1, pp. 58–67, 1991.
  * [27] M. Papageorgiou and A. Kotsialos, “Freeway ramp metering: An overview,” _IEEE transactions on intelligent transportation systems_ , vol. 3, no. 4, pp. 271–281, 2002.
  * [28] M. Bojarski, D. Del Testa, D. Dworakowski, B. Firner, B. Flepp, P. Goyal, L. D. Jackel, M. Monfort, U. Muller, J. Zhang _et al._ , “End to end learning for self-driving cars,” _arXiv preprint arXiv:1604.07316_ , 2016.
  * [29] C. Wu, A. Kreidieh, K. Parvate, E. Vinitsky, and A. M. Bayen, “Flow: A modular learning framework for autonomy in traffic,” _arXiv preprint arXiv:1710.05465_ , 2017.
  * [30] D. Krajzewicz, J. Erdmann, M. Behrisch, and L. Bieker, “Recent development and applications of sumo-simulation of urban mobility,” _International journal on advances in systems and measurements_ , vol. 5, no. 3&4, 2012.
  * [31] S. Ross, G. Gordon, and D. Bagnell, “A reduction of imitation learning and structured prediction to no-regret online learning,” in _Proceedings of the fourteenth international conference on artificial intelligence and statistics_. JMLR Workshop and Conference Proceedings, 2011, pp. 627–635.
  * [32] D. P. Kingma and J. Ba, “Adam: A method for stochastic optimization,” _arXiv preprint arXiv:1412.6980_ , 2014.
  * [33] N. Srivastava, G. Hinton, A. Krizhevsky, I. Sutskever, and R. Salakhutdinov, “Dropout: a simple way to prevent neural networks from overfitting,” _The journal of machine learning research_ , vol. 15, no. 1, pp. 1929–1958, 2014.


# Fast Bitmap Fit: A CPU Cache Line friendly memory allocator for single
object allocations

Dhruv Matani, Gaurav Menghani

###### Abstract

Applications making excessive use of single-object based data structures (such
as linked lists, trees, etc…) can see a drop in efficiency over a period of
time due to the randomization of nodes in memory. This slow down is due to the
ineffective use of the CPU’s L1/L2 cache. We present a novel approach for
mitigating this by presenting the design of a single-object memory allocator
that preserves memory locality across randomly ordered memory allocations and
deallocations.

##  1 Introduction

Numerous applications make use of data structures that allocate single objects
(i.e. objects of a fixed size). For example linked lists (singly/doubly
linked), trees (balanced/unbalanced), etc… all allocate nodes of a fixed size.
These nodes contain both metadata (pointers to other nodes) as well as data
(the actual values being stored).

Over the course of the application’s lifetime, the application may create,
update, and delete such data structures. Sorting or reversing a linked list
changes the order of these nodes, and balanced trees typically move nodes
around quite a bit.

Allocation algorithms that are commonly used on these systems (e.g. first
fit[3], best fit, cached, etc…) optimized for allocation/deallocation speed,
and may keep these nodes around in a random order (or the order in which they
were returned). This problem is especially exacerbated in allocators that
implement arenas and keep small allocated objects around for immediate future
use[1]. The next time memory is requested, it comes back in a random order,
and even a simple operation such as a linear traversal of a newly created
linked list can be much slower when the memory returned by the allocator is in
a random order. This is because the memory could be in different cache lines
and may not all fit in the CPU’s L1/L2 cache. Furthermore, if the object size
itself is small, then the CPU’s L1/L2 cache may be wasted by pulling in memory
that is entirely unused.

Previous research on using a software look-aside buffer has been done to
mitigate these effects for linked lists[2]. However, these approaches are
complex, introduce implementation overhead, and don’t scale to all single-
object based data structures.

We discuss a simple and elegant approach for an efficient single object memory
allocator which ensures that repeated allocation/deallocation cycles of memory
in random order don’t affect future allocations, which will be serviced in a
cache friendly manner. Further, this structure can be exploited by the
application by requesting memory that is ”close” to an already allocated
memory block. This is beneficial if the application expects both nodes in the
data structure to be needed together. For example, if the user wishes to
insert an element into an existing linked list in the middle, it can pass in
the address of the previous (or next) node (hint) in the list and the
allocator should attempt to service this request by returning a memory address
(node) as close as the provided ”hint”.

###  1.1 Pseudo-code highlighting a problematic case

The pseudo-code below shows an example of how memory is allocated, used,
deallocated, and then allocated again resulting in poor memory locality and
cache performance for a simple data structure such as a linked list.

    List lst = {}; // empty list.

    // Populate the list.
    for (i = 0; i < 10000; ++i) {
      // Insert a random number in the range [0..100] into the list.
      lst.append(random(100));
    }

    // Iterate over all the elements of the list.
    // it is an iterator into the linked list lst.
    for (it = lst.begin(); it != lst.end(); ++it) {
      // This will access memory in the order returned by the
      // allocator. Typically, for the first use, this is in address
      // order.
      print(it.value());
    }

    // Sort the list in ascending order of element value.
    lst.sort();

    // Return memory for linked list nodes back to the allocator.
    lst.clear();

    // Populate the list again.
    for (i = 0; i < 10000; ++i) {
      // Insert a random number in the range [0..100] into the list.
      // This time around, the memory returned by the allocator
      // could be either in memory order or in the order returned
      // by List::clear(). If it’s the latter, then consecutive nodes
      // in the linked list will be randomly ordered.
      lst.append(random(100));
    }

    // Iterate over all the elements of the list.
    // it is an iterator into the linked list lst.
    for (it = lst.begin(); it != lst.end(); ++it) {
      // This will access memory in the order returned by the
      // allocator. If the memory address of the nodes is random,
      // this will thrash the cache, and negatively impact the
      // application’s running time due to an increase in CPU
      // cache misses.
      print(it.value());
    }

###  1.2 The impact of memory locality

Modern CPUs have L1/L2 caches to make references to main memory faster for
data that can be stored in the CPU cache. Access to data in the L1 and L2
caches can be 200x and 15x faster than access to main memory[4].

Access Type | Latency (ns) | Relative to Main Memory Reference
---|---|---
L1 cache reference | 0.5 ns | 200x
L2 cache reference | 7 ns | 15x
Main memory reference | 100 ns | 1x

Hence, it’s very much preferred to keep as much of the active data set in the
CPU’s L1/L2 cache. Once data is in the cache, every attempt should be made to
use as much of it as possible. Alternatively, we should attempt to lay the
data out in memory such that data used together in time is laid out close
together in space (in memory).

Additionally, application inefficiencies resulting from inefficient placement
of data are very hard to detect and reason about [1, 10]. Hence, every effort
must be made to ensure that programming abstractions support effective data
locality by design.

##  2 Previous Work

###  2.1 General Purpose Memory Allocators

General purpose memory allocators have been built and studied for a long time.
There are some popular algorithms that are used very commonly.

  1. 1.

First Fit[5]: Typically implemented to optimize for allocation speed at the
expense of memory fragmentation.

  2. 2.

Best Fit[6]: Typically implemented to minimize memory fragmentation at the
expense of allocation speed.

  3. 3.

Binary Buddy[5]: Memory returned in sizes that are the closest power of 2
greater than or equal to the requested memory size.

  4. 4.

Bitmap Fit[7]: Bitmaps are used to keep track of fixed-size memory blocks that
are free/used. Bitmaps need to be scanned to locate free memory of a specified
size that is a multiple of the block size. The implementation relies on
specific processor instructions related to bit manipulation, and the run-time
cost is linear in the worst case. There have been more efficient variants
proposed[8], but these remain fairly complex in terms of implementation
complexity.

###  2.2 Single Object Memory Allocators

The most commonly used single object allocation strategy employs the use of
buckets. These are lists of memory chunks of a fixed size, bucketed by size.
Typically, the buckets are either multiples of a fixed page size or memory
blocks that are powers of 2. This strategy results in efficient
allocation/deallocation cost, but suffers from the problem of randomizing
memory blocks over the lifetime of a long running application, since these
free lists are maintained in the order in which memory was returned back to
the memory allocator.

This paper builds on prior work which describes a bitmap allocator[9] that has
the desirable memory-locality/cache-friendliness properties, but not the
desirable efficient running time in the worst-case.

##  3 The Fast Bitmap Fit Data Structure

###  3.1 Advantages relative to linked-free-lists

  1. 1.

No need to access user-memory: The Fast Bitmap Fit allocator maintains
metadata separate from the data blocks. A an allocator that uses arenas and
free-lists uses an intrusive linked list to chain together free blocks of the
same size. This means that a traversal of the linked list necessarily needs to
bring in the memory that will be returned to the user into the CPU’s cache.

  2. 2.

No memory alignment requirements: Since the Fast Bitmap Fit allocator
maintains a bitmap in a separate part of the memory, the user-memory doesn’t
need to align memory to pointer-size width (which is necessary in case the
free-list pointers need to be maintained in the same location as the memory
block to be returned to the user). Even $1$-byte blocks can truly be allocated
and returned to the calling application. This means no forced internal
fragmentation because no lower-bound is imposed by the allocator itself on the
size of each user-returnable memory block.

###  3.2 The structure in detail

Let’s take a concrete example. Assume that the allocator pre-allocates space
for 8 objects of a fixed size $S$. Hence, we first allocate a memory block of
size $S\times 8$ bytes. Each one of these $8$ memory blocks will have an
associated bit indicating whether it is available $(0)$ or used $(1)$. These
$8$ bits will make up the leaf levels of a complete binary tree-structure.
This structure will have $8-1=7$ internal nodes, and hence $7$ additional bits
for internal nodes. In all, we need $8+7=15$ additional bits of data to store
metadata about which memory locations are available/used, and how to locate
them quickly.

The bitmap is shown graphically below, with bit positions ranging from $0$ to
$14$. This bitmap corresponds logically to the full binary tree also shown in
the image below.

Significance of a bit’s value: The bit at position $0$ is the root node of the
entire structure. If this bit has a value $0$, then it means that there is at
least one free memory location available in the structure. If this bit has a
value $1$, then it means that all the memory location in this structure are
occupied.

Left/Right Child Arithmetic: To find the left child of a node at index idx, we
go to the bit at position $\texttt{idx}\times 2+1$, whereas to find the right
child of the same node, we visit the bit at position $\texttt{idx}\times 2+2$.

###  3.3 The Allocate Operation

First, we start at the root (bit-$0$), and walk our way down left or right
(preferring the left sub-tree if there’s a free object available in the sub-
tree) till we reach a leaf node. In the example below, we start at node $0$,
and end up at node $7$.

Now, we mark node $7$ as unavailable by setting the bit at index $7$ to $1$,
and walk our way up the tree, always performing the logical $AND$ of sibling
nodes to determine the value of the parent node. Once we hit a node where we
didn’t update the value of the bit in that internal node, we can safely stop
propagating up to the root of the tree.

The graphic below shows one more allocate operation being performed where
another memory slot is marked as used.

The cost of each Allocate operation is $\Theta(\log{}n)$.

###  3.4 The Free/Deallocate Operation

Let’s assume we’re starting with a tree which has $6$ nodes used as shown
below.

Suppose the user requested to free the $6^{th}$ memory location (node $12$).
We’d start at bit number $12$ in our bitmap, and keep walking up, setting all
visited bits to $0$ as we walk up to the root. We can stop as soon as we find
a bit that is already $0$ since all bits above it (up to the root) will
already be $0$ by definition once we find an internal node with the value $0$.

The cost of each Free/Deallocate operation is $O(\log{}n)$.

###  3.5 Allocate with hint

Some applications may require allocating memory that is close to an already
piece of allocated memory because it is expected that both objects will be
used simultaneously. In such a scenario, it is beneficial for both the objects
to live on the same page that is cached in the CPU’s L1/L2 cache. This
allocator design supports this operation too to some degree.

The algorithm below isn’t guaranteed to find nodes as close to the target node
as possible, but assuming a full factor of 60%-80%, there’s a good chance that
one will find a node next to the provided ”hint” node’s address.

The general idea is to traverse down from the root of the tree, moving down in
the direction of the target (hint) node as long as there is a free node
available in that subtree. If there’s a choice to be made to go down the left
or right subtree, choose the side that has free nodes closer to the ”hint”
node’s location.

  * •

In the image below, the node $11$ is the ”hint” node.

  * •

We start at the root node $0$ and try to move down the tree toward the node
$11$ (right child).

  * •

When we get to node $2$, we notice that it’s occupied, and we back up and
instead go to node $1$ (left child of the root), which has a free node under
it.

  * •

Here, we need to choose which side we wish to explore first. We choose the
right child of this node (node $4$) since that node has children closer in
memory to the hint node (node $11$).

  * •

Again we move down the right child of node $4$ to node $10$ (which is a leaf
node), and stop here.

You can see that the node located is close in space (memory) to the hint node.

We now mark nodes as allocated as we did in the allocate method by walking up
the parents of the left node, performing a boolean AND of the use/free bits at
every level.

The cost of each Allocate-with-hint operation is $\Theta(\log{}n)$.

##  4 Conclusion

In this paper, we presented a data structure for a fast bitmap fit memory
allocation strategy, which supports allocation (with or without hint) in time
$\Theta(\log{}n)$, and free/deallocate in time $O(\log{}n)$. This is a
significant improvement over the cost for bitmap fit known so far.

In addition, this approach doesn’t mix data with metadata, so sequences of
allocate/free operations with no access to the data in between will incur no
additional cache activity.

Irrespective of what order the memory is returned back to the allocator,
subsequent allocations will always attempt to return objects in memory order
to maximize re-use of cached pages in the CPU’s L1/L2 caches.

## References

  * [1] Dirk Grunwald, Benjamin Zorn, Robert Henderson. Improving the Cache Locality of Memory Allocation, 1993.
  * [2] Gerald Bozman. The software lookasize buffer reduces search overhead with linked lists. Communications of the ACM, 27(3):222-227, March 1984
  * [3] Doug Lea. An efficient first-fit memory allocator.
  * [4] Jeff Dean, Designs, Lessons and Advice from Building Large Distributed Systems, 2009.
  * [5] Donald E. Knuth. Fundamental Algorithms, volume 1 of The Art of Computer Programming, chapter 2, pages 435-451. Addison Wesley, Reading, MA, 2nd edition, 1973.
  * [6] Paul R. Wilson, Mark S. Johnstone, Michael Neely, David Boles, Dynamic Storage Allocation: A Survey and Critical Review, 1995.
  * [7] Brian Stuart, Principles of Operating Systems: Design and Applications, 2008.
  * [8] M. Masmano, I. Ripoll, J. Real, A. Crespo, and A. J. Wellings. Implementation of a constant-time dynamic storage allocator, 2007.
  * [9] Dhruv Matani. The bitmap allocator, GNU libstdc++ manual, 2006.
  * [10] Yehuda Afek, Dave Dice, Adam Morrison. Cache Index-Aware Memory Allocation, 2011.