quote

# PeRP: Personalized Residual Policies For Congestion Mitigation
Through Co-operative Advisory Systems

Aamir Hasan1, Neeloy Chakraborty∗1, Haonan Chen∗1, Jung-Hoon Cho2,
Cathy Wu2, and Katherine Driggs-Campbell1 * denotes equal contribution.1A.
Hasan, N. Chakraborty, H. Chen, and K. Driggs-Campbell are with the Department
of Electrical and Computer Engineering at the University of Illinois Urbana-
Champaign. Emails: {aamirh2, neeloyc2, haonan2<EMAIL_ADDRESS>Cho is
with the MIT Laboratory for Information & Decision Systems (LIDS) and the
Department of Civil and Environmental Engineering (CEE) at the Massachusetts
Institute of Technology, Email<EMAIL_ADDRESS>Wu is with the MIT
Laboratory for Information & Decision Systems (LIDS), the Department of Civil
and Environmental Engineering (CEE), and the Institute for Data, Systems, &
Society (IDSS) at the Massachusetts Institute of Technology, Email:
<EMAIL_ADDRESS>
###### Abstract

Intelligent driving systems can be used to mitigate congestion through simple
actions, thus improving many socioeconomic factors such as commute time and
gas costs. However, these systems assume precise control over autonomous
vehicle fleets, and are hence limited in practice as they fail to account for
uncertainty in human behavior. Piecewise Constant (PC) Policies address these
issues by structurally modeling the likeness of human driving to reduce
traffic congestion in dense scenarios to provide action advice to be followed
by human drivers. However, PC policies assume that all drivers behave
similarly. To this end, we develop a co-operative advisory system based on PC
policies with a novel driver trait conditioned Personalized Residual Policy,
PeRP. PeRP advises drivers to behave in ways that mitigate traffic congestion.
We first infer the driver’s intrinsic traits on how they follow instructions
in an unsupervised manner with a variational autoencoder. Then, a policy
conditioned on the inferred trait adapts the action of the PC policy to
provide the driver with a personalized recommendation. Our system is trained
in simulation with novel driver modeling of instruction adherence. We show
that our approach successfully mitigates congestion while adapting to
different driver behaviors, with 4 to 22% improvement in average speed over
baselines. 111Additional material and code is available at the project
webpage: https://sites.google.com/illinois.edu/perp

##  I Introduction

Traffic congestion is a leading cause of urban mobility issues such as long
commute times and increased fuel consumption [1, 2]. These problems also have
a severe economic impact on everyday living [3]. Thus, alleviating congestion
(i.e. congestion mitigation) is paramount to improving multiple facets of
modern society. Simple speed management techniques through speed and
acceleration advice have been shown to improve safety while reducing
congestion [4, 5]. However, these methods utilize generic speed limits that
are independent of important dynamic factors such as the number of vehicles on
the road.

Autonomous vehicles (AVs) trained to operate optimally can also be used for
congestion mitigation [6]. For example, Stern et al. showed that a single AV
can reduce stop-and-go waves and thus reduce emissions in a closed-loop
traffic setting [7]. However, current AV systems are immature in non-idealized
settings, particularly in scenarios involving a large number of agents that
are ubiquitous in traffic scenarios [8, 9]. The same policies that control AVs
can be modified for use in shared control schemes to aid in congestion
mitigation [10]. Particularly, co-operative advisory systems where drivers are
provided instructions by these optimally trained policies can be utilized to
provide near optimal performance [11]. These policies can utilize simple
methods to interact with drivers such as direct integration into smartphone
applications (e.g. navigation apps) or through in-car interfaces (e.g. head-up
displays).

Figure 1: PeRP augments general advised instructions to provide personalized
recommendations to drivers of varying driving styles (e.g. an aggressive
driver (a) or conservative driver (b)) to mitigate congestion (c).

AV policies trained with Reinforcement Learning (RL) can also successfully
stabilize traffic flow and mitigate the formation of stop-and-go waves [6,
12]. For example, Sridhar et al. use piecewise constant (PC) policies to
mitigate congestion by explicitly learning _human compatible_ policies [11].
This modeling is achieved through their PC constraint, where actions are held
for some duration, defined as the hold-length, to allow drivers to adjust
their action to the provided advice. While these policies are designed to be
easy to follow, they assume a one-solution-for-all paradigm where all drivers
behave similarly. However, we can adapt these PC policies to produce
personalized residual policies that account for variances in human behavior.

To this end, we propose a class of Personalized Residual Policies, PeRP, that
condition the advised action on an inferred driver trait. Figure 1 shows an
overview of our PeRP. We utilize a variational autoencoder to perform
unsupervised trait inference on how drivers follow instructions. The inferred
driver traits and actions by the base policy are used to create a personalized
advised action that can be followed by drivers without significant load to
mitigate congestion. Thus, making our policy agnostic to different driver
behaviors. We verify the effectiveness of our policy in simulation using a
novel driver instruction-following model. Most notably, we model how drivers
follow advice imperfectly.

Our main contributions are:

  1. 1.

A novel Personalized Residual Policy for congestion mitigation through co-
operative advisory systems.

  2. 2.

A simulation framework for modeling driver responses to advisory systems in
on-road settings11footnotemark: 1.

  3. 3.

A novel unsupervised driver trait inference model that encodes how drivers
follow advice provided to them.

This paper is organized as follows. In Section II, we describe relevant work.
Section III contains preliminary information required to aid in understanding
our proposed method that is detailed in Section IV. We present our experiments
and discuss results in Sections V and VI, respectively. Finally, we provide
our conclusions and avenues for future work in Section VII.

##  II Related Work

###  II-A RL for designing Congestion Mitigation Strategies

With the advancement of model-free deep RL, many policies have been developed
to mitigate traffic congestion and reduce emissions. These policies are used
to improve throughput in traffic systems [13, 14, 15, 6] and developing eco-
driving strategies in a myriad of road settings [16, 17, 18]. Particularly,
Jayawardana et al. design interpretable decision tree policies and supervision
models that perform at the same level as the RL based policies to mitigate
congestion in urban scenarios [17]. Alternatively, Wu et al. propose a general
modular learning framework to analyze the impact of AVs on traffic flow [6].
To the same effect, Sridhar and Wu introduce PC policies to mitigate
congestion and stabilize traffic [11]. PC policies achieve human compatibility
by using the notion of an action extension parameter, where an action is held
for some guidance hold-length, $\delta$, that dictates the control frequency
[19]. Theoretical analysis on such human-compatible guidance derives
conditions that directly relate the advice provided to the drivers with the
stability of traffic flow [20]. While these PC policies are immensely useful,
they assume that all drivers co-operate and react to the guidance similarly.
In this work, we address these caveats by deriving residual policies that use
learned driver reactions to the given guidance. We provide a summary of PC
policies in Section III-B as they are the base policies for our class of
residual policies.

###  II-B Residual Policy Learning

Residual Policy Learning (RPL) is grounded in two main facets: (1) utilising a
base policy to produce an approximate solution and (2) learning a corrective
term to mitigate inaccuracies in the base policy and handle potential
variations [21, 22, 23]. RPL represents a biased exploration strategy towards
the state distribution of the initial policy as it is used to learn corrective
values for control parameters or actions [24, 25, 26, 27]. For example, Rana
et al. employ RPL for low-level controllers to achieve fine-grained skill
adaptation, thus enabling downstream RL agents to adapt to unseen environment
variations [28]. Similarly, Zhang et al. utilize RPL to enhance a modified
artificial potential field (MAPF) policy for high-speed autonomous racing that
uses RPL to guide exploration [29]. However, the residual policies are not
adaptable as they do not assimilate to controllers that have minor differences
from the trained controller. In contrast, our residual policy, PeRP, is
conditioned on a learned driver trait. This conditioning enables the
adjustment of the output action based on different driver behaviors and can
thus effectively handle the nuances in human-autonomy teaming.

###  II-C Driver Trait Inference

Factors such as driving experience, personal preferences, fatigue, and levels
of distraction impact how people drive [30]. As it is paramount to tailor
driver-centric autonomous systems to these factors, Driver Trait Inference
(DTI) is a booming field of study with applications in driver intent
estimation [31, 32], vehicle trajectory prediction [33, 34], and mulit-agent
path planning [35, 36, 37]. Popular approaches to DTI can be decomposed into
combinations of supervised and unsupervised methods. Supervised approaches
require discrete labels during training which significantly hinders the
accuracy of the model during evaluation, as drivers may act with out of
distribution traits at test time [37]. In contrast, unsupervised learning
methods fit a continuous distribution over unlabeled driver traits from
trajectories and show that a compressed latent representation can inform
lower-level planning [35, 36]. Other works use a combination of unsupervised
learning and RL to estimate the strategies or traits of other agents for
better interactions [38, 39, 40]. We chose to preform DTI with an Variational
Autoencoder based model as unsupervised methods can handle out of distribution
inputs without significant errors while being more data efficient [41, 36].

In early experiments, we found that the latent encodings on the inference of
context-aware behavioral traits was more useful for downstream RL policies
than the inference of Intelligent Driver Model (IDM) [42] parameters that are
used in works by Morton et al. [35]. Thus, our DTI models the preferred action
offset from the advised action output by the base policy. Intuitively, when
drivers are provided speed advice, they will either be (1) conservative and
drive slower than the advised speed, (2) aggressive and drive over the advised
speed, or (3) follow the advised speed as closely as possible. Our trait
inference model is thus designed to capture this phenomena to inform the
downstream personalizaton task.

##  III Preliminaries

###  III-A Problem Definition

Consider a road network with $N$ vehicles, where a single ego vehicle is
driven by a human following some guidance, while $N-1$ vehicles are driven by
humans without any advice. Given the current state of the ego vehicle $s\in S$
and an advised action $a^{advised}\in A$, the driver of the ego vehicle takes
action $a^{driver}\in A$ according to some policy $\pi^{driver}:~{}S~{}\times
A~{}\rightarrow~{}A$, where $S$ and $A$ are the predefined state and action
spaces for the road network, respectively. Similarly, each driver $i$ of the
$N-1$ vehicles, takes in the current state of their vehicle $s^{i}\in S$ and
applies an action $a^{i}\in A$ according to a policy $\pi^{i}(s):S\rightarrow
A$.

$a^{driver}\sim\pi^{driver}(s,a^{advised})$ $a^{i}\sim\pi^{i}(s)\forall
i\in\\{1,...,N-1\\}$

We seek to find a policy, $\pi(s):S\rightarrow A$ that provides the advised
action, $a^{advised}$, to the ego driver that mitigates congestion in the
network. In this work, we choose to model the action as a speed action.
Without loss of generality, the same techniques can be applied to acceleration
actions as the system is agnostic to the type of action.

Theoretically, policies that are dependent on the network parameters that
produce a constant speed action can mitigate congestion [7, 6]. However, these
policies assume static environments and are not practically permissible to be
followed by drivers due to the nuances of human behavior (e.g. reaction time).
We encapsulate these diverse behaviors by the driver policy, $\pi^{driver}$.
Note that for the remainder of this paper, we refer to the ego vehicle and its
driver as the driver or agent interchangeably.

###  III-B Piecewise Constant Policies (PCP)

Humans require a few seconds ($\approx 2-3s$) to perceive and act on the
instructions provided to them [43, 44]. PC policies aim to incorporate this
delay in action propagation by holding an action for a specified length of
time, $\delta$. Formally, PC policies for providing instructions to drivers
can be defined as an episodic Markov Decision Process (MDP). An episodic MDP:
$\mathcal{M}$, is defined as, $\mathcal{M}=(S,A,P,R,H,\delta,\gamma)$, where
$S$ is the state space, $A$ is the action space, $P:S\times A\rightarrow S$
represents the transition probabilities, $r(a,s)\in R:S\times
A\rightarrow\mathbb{R}$ is the reward function for a state-action pair
$(s,a)$, $H$ represents the horizon, $\delta$ represents the number of
timesteps an action is held, and $\gamma\in[0,1)$ is the discount factor.

For PC policies we define the state $s\in S^{PCP}$, with regards to the ego
vehicle as:

$s=\left(\frac{v_{ego}}{v_{max}},\frac{v_{leader}}{v_{max}},\frac{h_{leader}}{h_{max}}\right)$

where $v_{ego}$ is the speed of the ego vehicle, $v_{leader}$ is the speed of
the vehicle leading the ego vehicle, $h_{leader}$ is the headway distance
between the ego vehicle and its leader, $v_{max}$ is the maximum speed allowed
on the track, and $h_{max}$ is the maximum possible distance between the two
vehicles. We assume a fully observable state, $s\in S^{PCP}$, for the agent.
The action space for PC policies is defined as $A^{PCP}=\\{0,...,A_{max}\\}$,
a discrete set of $\alpha$ equally spaced speeds in m/s, where $\alpha\text{
and }A_{max}$ are hyperparameters. The reward function used for the PC
policies is the speed of the ego vehicle, $R^{PCP}=v_{ego}=a^{driver}$. We
assume the driver has exact control over the speed of the ego vehicle. The
average speed of all vehicles would also function as a good reward function as
the two definitions would produce similar policies. However, the latter
definition assumes full observability of the environment and is thus
unrealistic.

At each timestep, $t$, the PC policy, $\pi^{PCP}(s_{t}):S^{PCP}\rightarrow
A^{PCP}$, chooses an action $a^{PCP}_{t}\in A^{PCP}$ that represents the speed
to be held for $\delta$ timesteps that maximizes the reward function,
$R^{PCP}$. We refer the readers to the work by Sridhar et al. and Li et al.
for an in-depth analysis of PC policies and their robust nature [11, 20].

While the above definition uses speed as its action space, the original work
by Sridhar et al. uses acceleration. We choose speed as our action space since
humans find it easier to perceive and follow advice in terms of speed over
acceleration [45]. This change in action type retains all theoretical claims
made about the robustness of PC Policies.

Additionally, PC policies assume that human drivers follow instructions
presented to them perfectly, i.e. $\pi^{driver}(s,a^{PCP})=a^{PCP}$. While
this assumption alleviates training and modeling concerns, it is not
pragmatic. Studies conducted on the perception and effectiveness of speed
limits have shown that drivers do not follow advice perfectly [46], but
instead offset from the advised speeds depending on the nature of the driving
scenario. We posit that these different driving styles should be considered
while designing advisory systems. Thus, we introduce a driver trait inference
module to capture the variations in how drivers follow instructions.

##  IV Method

Figure 2: An overview of our co-operative advisory system: PeRP appends a
residual action, $a^{PeRP}$, to the PCP action, $a^{PCP}$, while conditioned
on the driver trait, $z$, to produce an advised action, $a^{advised}$. The
driver considers the advised action and takes an action $a^{driver}$ in the
environment.

In this section we describe the different modules in our proposed system.
First, we introduce driver traits and summarize our trait inference model.
Then, we introduce PeRP, our personalized residual policy for co-operative
advisory systems. Figure 2 shows the general architecture of our proposed
system.

###  IV-A Driver Policy Model

The inference of driving styles benefits advisory systems as all drivers do
not behave identically [30, 42, 35, 36]. A survey conducted by Mannering
confirmed that drivers do not strictly adhere to speed limits, but instead
drive at higher speeds [46]. Motivated by this case of speed limits, we define
our driver trait as the drivers’ preferred offset from the advised speed
action. In our case, we capture whether the driving speed is 2.5 or 5 m/s
($\approx$5 or 10 mph) over or under the advised action. Specifically, the
traits are: if the driver is driving {5m/s below, 2.5m/s below, at, 2.5m/s
above, 5m/s above} the advised speed.

We choose these five different traits to encompass the instruction following
behaviors of a majority of drivers. As drivers cannot maintain perfect speeds,
we model these traits as deviations from the advised action with Gaussian
distributions with the means $\text{trait}_{\mu}=\\{-5,-2.5,0,2.5,5\\}$ and
variance 1, respectively. Formally, this can be defined as:

$\pi^{driver}(s,a^{advised})=a^{advised}+k\text{ where
}k\sim\mathcal{N}(\text{trait}_{\mu},1)$

We assume perfect driver reaction time but imperfect instruction following. We
abstain from including driver reaction times in the traits in order to limit
the scope of the personalization. Additionally, we assume that all other
drivers on the road behave similarly and follow an Intelligent Driver Model
(IDM) [42]. We believe this is a justified assumption as the main focus of
this work is to mitigate congestion using a single driver and their trait,
while excluding all other drivers in the system. However, our model can easily
be modified to assign different traits for all drivers.

###  IV-B Driver Trait Inference (DTI)

Figure 3: The Driver Trait Inference VAE Model. The input trajectory
$\boldsymbol{x}$ is encoded as $z_{\mu}$ and $z_{\sigma}$ before
parameterization as $z$ using the encoder network. The decoder network uses
this latent vector $z$ to reconstruct the input trajectory as
$\boldsymbol{\hat{x}}$.

We capture the different driver traits discussed above in an unsupervised
manner through a Variational Autonecoder (VAE) based model [41]. Figure 3
summarizes the architecture of our VAE. The input to the DTI model is a
sequence of states of the agent, $\boldsymbol{x}=\\{x_{1},x_{2},..,x_{T}\\}$,
where each $x_{t}\in S^{PCP}$ and $T$ is the observation period. The VAE model
first uses an encoder, consisting of a recurrent $\text{LSTM}_{E}$ layer and
two fully connected layers, $f_{\mu}$ and $f_{\sigma}$, to encode the input
trajectory $\boldsymbol{x}$ to a mean vector, $z_{\mu}$, and a log variance
vector, $z_{\sigma}$.

$z_{\mu}=f_{\mu}(e)\text{ and }z_{\sigma}=f_{\sigma}(e),\text{ where
}e=\text{LSTM}_{E}(\boldsymbol{x})$

We parameterize the latent vector using $z_{\mu}$ and $z_{\sigma}$ to produce
$z\in\mathbb{R}^{l}$, where $l$ is the latent space dimension [41].

$z=z_{\mu}+\epsilon\cdot exp(z_{\sigma}),\text{ where
}\epsilon\sim\mathcal{N}(0,1)$

During training, the latent vector is processed with a decoder, consisting of
a recurrent $\text{LSTM}_{D}$ layer and a fully connected layer, $f_{dec}$, to
produce a reconstructed trajectory
$\boldsymbol{\hat{x}}=\\{\hat{x}_{1},\hat{x}_{2},...,\hat{x}_{T}\\}$. Each
element $\hat{x}_{t}$ is given by:

$\hat{x}_{t}=f_{dec}(h_{t})$

where $h_{t}$ is the hidden state from $\text{LSTM}_{D}$ at time $t$. We
choose LSTMs for the recurrent layers in the model due to their capability
learning patterns in sequences while handling variable-length sequences [47,
33].

The VAE model is encouraged to reconstruct the input trajectory while ensuring
that the latent vectors follow a standard normal distribution by optimising
the loss function:

$\mathcal{L}_{DTI}=\beta_{\text{recon}}\cdot{\left\|\boldsymbol{\hat{x}}-\boldsymbol{x}\right\|}_{2}+\beta_{\text{KL}}\cdot
D_{\text{KL}}(z_{\mu},z_{\sigma})$

where $D_{\text{KL}}(\mu,\sigma)$ is the KL divergence between any Gaussian
distribution $\mathcal{N}(\mu,\sigma)$ and the standard normal distribution
$\mathcal{N}(0,1)$, and $\beta_{\text{recon}}$ and $\beta_{\text{KL}}$ are
hyperparameters.

During evaluation and usage with PeRP, the decoder network is omitted.
Therefore, at each timestep $t$, the DTI module,
$f_{trait}:\mathbb{R}^{T\times|S^{PCP}|}\rightarrow\mathbb{R}^{l}$ uses the
sequence of states,
$\boldsymbol{x_{t}}=\\{x_{t-T},x_{t^{-}(T-1)},..,x_{t}\\}$, to produce a
latent vector $z_{t}$ that indicates the driver’s trait.

###  IV-C Personalized Residual Policies (PeRP)

The inference of the driver’s trait allows us to learn a residual policy from
PC policies to provide personalized advice. The same definition of an episodic
MDP, $\mathcal{M}$, from Section III-B can be used to define our Personalized
Residual Policies with the following modifications. The state, $s^{PeRP}\in
S^{PeRP}=S^{PCP}\times A^{PCP}\times\mathcal{L}$, is a (3 + 1 + $l$)
dimensional tuple with observed state $s\in S^{PCP}$, the PCP action,
$a^{PCP}\in A^{PCP}$, and the driver trait, $z\in\mathbb{R}^{l}$.

$s^{PeRP}=\left(s,a^{PCP},z\right)$

The action space is a continuous bounded real space
$A^{PeRP}=[-\epsilon,\epsilon]$, where $\epsilon$ is a hyperparameter. The
reward function, $R^{PeRP}$ is defined as:

$R^{PeRP}=a^{driver}-|a^{driver}-a^{PCP}|$

The first term in this reward function aims at ensuring the dissipation of
stop-and-go traffic waves, similar to $R^{PCP}$. The second term in the reward
function aims at reducing the difference between the action performed by the
driver and the PCP action. We posit that an action that reduces this
difference, ensures independence to driving styles and thus allows for a more
co-operative advisory system.

At each timestep, $t$, the PeRP,
$\pi^{PeRP}(s_{t},a^{PCP}_{t},z_{t}):S^{PeRP}\rightarrow A^{PeRP}$, chooses a
residual action $a^{PeRP}_{t}\in A^{PeRP}$. Then the action to be held for
$\delta$ timesteps to mitigate congestion is
$a^{advised}_{t}=a^{PCP}_{t}+a^{PeRP}_{t}$. This advised action,
$a^{advised}_{t}$, can be provided to the driver to reduce congestion and
thereby improve emission rates in a co-operative manner. See Algorithm 1 for
more details.

To train and evaluate both PC policies and PeRP, we employ a warm-up period of
$W$ timesteps in each rollout. During the warm-up period, all vehicles are
controlled by IDM to generate stop-and-go traffic waves. After the warm-up
period, the speed at which the ego vehicle is driven at is determined by the
driver policy acting upon the advised action. The action is provided to SUMO
and is then propagated in simulation.

Intuitively, personalized PC policies could be trained from scratch. However,
the training time for these PC policies makes this approach inefficient. We
aim to improve performance by using the already trained PC policies without
additional overhead in terms of training time. We show that our PeRP achieves
improvements while being trained for significantly fewer steps than the PC
policy, thus imposing minimal overhead on training.

Finally, we note that PeRP is also a PC policy as it assumes that actions will
be held for $\delta$ timesteps to account for driver reaction and adjustment
periods. We assume that the driver trait does not change during the hold-
length as it is unlikely for human traits to change within such a short
duration.

Input: Piecewise constant policy: $\pi^{PCP}$, Driver policy: $\pi^{driver}$,
Driver Trait Inference model: $f_{\text{trait}}$, Learning rate: $\lambda$,
Hold Length: $\delta$, Warm-up time: $W$, Horizon: $H$, Observation length:
$T$, Maximum training iterations: $n_{max}$

Initialize $\pi^{PeRP}_{\theta}$

$iter\leftarrow 0$

while  _$iter\leq n_{max}$ and not converged_ do

$s_{t}\leftarrow$ Reset environment

for  _$t\in\\{1,...,W\\}$_ do

Sample $a_{t}\sim IDM(s_{t})$

Execute action $a_{t}$ in environment

Observe $s_{t+1}$

end for

while  _$t\leq W+H$_ do

Sample $a^{PCP}_{t}\sim\pi^{PCP}(s_{t})$

$z_{t}\leftarrow f_{\text{trait}}(\\{s_{t-T},...,s_{t}\\})$

Sample $a^{PeRP}_{t}\sim\pi^{PeRP}_{\theta}(s_{t},a^{PCP}_{t},z_{t})$

$a^{advised}_{t}\leftarrow a^{PCP}_{t}+a^{PeRP}_{t}$

for  _$\tilde{t}\in\\{1,...,\delta\\}$_ do

Sample
$a_{t+\tilde{t}}\sim\pi^{driver}(s_{t+\tilde{t}},a^{advised}_{t+\tilde{t}})$

Execute action $a_{t+\tilde{t}}$ in environment

Observe $s_{{t+\tilde{t}}+1},r_{t+\tilde{t}}$

end for

$t\leftarrow t+\delta$

end while

Estimate loss $L_{\theta}(\theta)$ using $\\{s_{W},...,s_{W+H}\\}$,
$\\{a_{W},...,a_{W+H}\\}$, and $\\{r_{W},...,r_{W+H}\\}$

$\theta\leftarrow\theta-\lambda\nabla_{\theta}L_{\theta}(\theta)$

$iter\leftarrow iter+1$

end while

Algorithm 1 The PeRP algorithm

##  V Experiments

###  V-A Environment Setup

All experiments were carried out in simulation11footnotemark: 1 using the Flow
framework for RL based on SUMO [48, 49]. Every timestep in the simulation was
equivalent to 0.1 seconds. The actions implemented by the agent are provided
to SUMO and are internally propagated to take effect in the next step. We set
the $min_{gap}$ parameter for the ego vehicle to be 0. Thus, the policy is
required to learn to avoid collisions with the leader by controlling the speed
of the agent. If a collision occurs during a rollout, the episode is ended
with 0 reward.

Our experiments involve vehicles driving on the canonical single-lane circular
track as is standard in many related works [11, 7]. Our track has a
circumference of 640m with $N=40$ vehicles on the road. The ego vehicle is
controlled by the driver model detailed in Section IV-A following the
instructions of the policy. The other 39 "human" drivers on the track are
controlled by IDM [42]. Each vehicle on the track is 5m long. We assume that
every vehicle always has a leader. The maximum speed, $A_{max}$, was set to
35m/s based on empirical simulation results for all policies as it is unlikely
for vehicles to reach this speed given the initial conditions.

Even though the PeRP is designed to handle changing driver traits, the traits
were kept constant for a rollout to prevent drastic changes leading to
unrealistic simulation e.g.: the trait shifting from $\text{trait}_{\mu}=5$ to
$\text{trait}_{\mu}=-5$ between consecutive action extension periods.

We carried out analysis and experiments for hold-lengths:
$\delta\in\\{10,20,50,100\\}$. We choose these particular values to provide a
wide range of possible extensions to test our system at the extremes.

###  V-B Piecewise Constant Policies

Policies were trained for each $\delta$ with $\alpha=18$ actions and
$A_{max}=35$ m/s in the action space $A^{PCP}$. Each policy was trained as a
multi-layer perceptron, with hidden layers of shape $(64,64)$ for 1000
iterations using TRPO [50]. Each iteration had a warm-up period of 1000 steps
and a horizon of 2000 steps. A $\gamma=0.99$ and a learning rate of $0.0001$
resulted in the best performing policies. Only the best performing policies
for each $\delta$ were used as bases for DTI and PeRP. All other parameters
were kept consistent with those presented by Sridhar et al. [11]. All PC
policies were trained using an Intel Xeon Platinum 8260 processor and 4 CPUs
provided by the MIT SuperCloud [51].

###  V-C Driver Trait Inference

Dataset: We train the DTI model on a dataset collected in simulation using the
driver policy model introduced in Section IV-A following advice from the PC
policies trained above. All states after the warm-up period of 600 steps are
collected for 50 iterations for a horizon of 1000 steps for each PCP. In
total, we collected 36,750 driving trajectories of length $T=20$ with equal
distribution amongst the five driving traits. We perform an 80-20 train-
evaluation dataset split for the collected trajectories.

Training: We train our VAE model with a latent space size of $l=2$, with both
encoder and decoder networks as single layer LSTMs with hidden and cell sizes
of 32. Our best performing model was obtained by training for 100 epochs or
until convergence with learning rate of 0.0001, batch size of 16,
$\beta_{\text{recon}}=1$, and $\beta_{\text{KL}}=0.0001$. All models were
trained on the HAL Cluster using a single Nvidia V100 GPU [52].

TABLE I: Results comparing the performance of our baselines with PeRP

Policy | $\delta=10~{}(1\text{s})$ |  | $\delta=20~{}(2\text{s})$ |  | $\delta=50~{}(5\text{s})$ |  | $\delta=100~{}(10\text{s})$
---|---|---|---|---|---|---|---
| Avg. Speed$(\uparrow)$ | Avg. Std$(\downarrow)$ |  | Avg. Speed$(\uparrow)$ | Avg. Std$(\downarrow)$ |  | Avg. Speed$(\uparrow)$ | Avg. Std$(\downarrow)$ |  | Avg. Speed$(\uparrow)$ | Avg. Std$(\downarrow)$
Optimal | 8.650 | - |  | - | - |  | - | - |  | - | -
OSL | 6.764 | 1.768 |  | - | - |  | - | - |  | - | -
PCP | 7.891 | 1.477 |  | 8.206 | 1.635 |  | 7.527 | 1.901 |  | 6.449 | 1.847
V-RP | 8.031 | 1.513 |  | 8.220 | 1.620 |  | 7.638 | 2.023 |  | 6.576 | 1.944
TA-RP | 8.055 | 1.454 |  | 8.222 | 1.627 |  | 7.816 | 1.967 |  | 6.467 | 2.016
PeRP∗ | 8.077 | 1.449 |  | 8.235 | 1.588 |  | 7.848 | 1.953 |  | 6.704 | 1.842

###  V-D Personalized Residual Policies

Training: The PeRPs were trained and evaluated for each of the PC policies
with a warm-up period of 600 steps and a horizon of 4000 steps. Similar to PC
policies, each PeRP was trained as a Multi-layer perceptron, with hidden
layers of shape $(64,64)$. All policies were trained for 200 iterations using
TRPO [50]. A $\gamma=0.99$ and a learning rate of $0.0001$ resulted in the
best performing policies. The action space bound, $\epsilon$, for $A^{PeRP}$
was set to 6m/s as values between $[-6,6]$ capture 87% of the the driver
policies offset. Lastly, PeRP uses an observation window of $T=20$ for the
trait inference. We note that while the DTI model and PeRP could be trained
simultaneously, they were trained separately to avoid compounding errors.

Baselines: We evaluate our PeRPs against four baselines: (1) Optimal Speed
Limit (OSL): The policy that outputs a constant action calculated based on the
network parameters verified to maximize the average speed of all vehicles. For
our network, this action was a speed of 8.65 m/s. This policy is equal to one
that is trained for $\delta=\infty$ and is analogous to a policy that always
advises the speed limit; (2) Piecewise Constant Policy: The base policy for
PeRP and the other RL based baselines; (3) Vanilla Residual Policy (V-RP): A
simple residual policy that aims at offsetting the base PC policy without any
trait knowledge; (4) Trait Aware Residual Policy (TA-RP): A residual policy
conditioned on the ground truth driver trait. We expect this model to have the
best performance due to its ground truth input.

Metrics: We evaluate the PeRPs and their baseline variants on two metrics: (1)
Average Speed: The average speed of all the vehicles on the road. A standard
metric where a high average speed indicates less congestion; (2) Average
Standard Deviation of Speed: The average of the standard deviation in speed
over all iterations. A lower value indicates less congestion.

##  VI Results and Discussion

###  VI-A Driver Trait Inference

Figure 4: A visualisation of the latent space of the driver trait inference
VAE on the validation dataset. We show the latent points for the different
trait means, $\text{trait}_{\mu}$, in different colors.

Figure 4 shows the latent space for the validation dataset. The VAE model is
successful in clustering the trajectories of the different driving styles. We
do not achieve fully separate clusters as is expected with unsupervised
models. However, the clusters for the different traits are noticeably distinct
with minor overlap. We omit an analysis of the reconstructed trajectories as
they have little impact on the PeRPs.

###  VI-B Personalized Residual Policies

Table I shows our quantitative results for the best performing models
evaluated for 100 iterations. Note that, the same PC policy was used for each
$\delta$ for all the baselines dependent upon a PC policy i.e. the V-RP, TA-
RP, and PeRP were trained using the same PC policy that they are compared
against for a particular $\delta$.

We observe that PeRP indeed outperforms the baseline models as evidenced by
the high average speeds with low average standard deviations in speed as seen
in Table I. The residual policies with driver trait inference, TA-RP, do not
perform proportionately with PeRP. We suspect that this under-performance is
due to differences in exploration during training. Meanwhile, all policies
significantly outperform the OSL. This difference in performance can be
attributed to the online nature of the RL policies that adapt guidance rather
than advising a constant action like the OSL. In addition, all policies except
OSL successfully avoid collisions. Some baselines incurred collisions in 4% of
evaluation scenarios on average. However, PeRP and PCP were both careful to
have 0 collisions in all evaluation iterations for $\delta=\\{20,50\\}$.
Iterations where collisions occur were omitted during calculation of the
metrics shown in Table I. We present collisions and emissions results in
supplementary material 11footnotemark: 1.

Additionally, the performance of the policies is severely dependent on the
hold-length chosen. A small $\delta$ would place too much load on the driver
and change the action too frequently for it to be followed by the driver.
Conversely, a large $\delta$ would require holding an action that is no longer
the near optimal action for the driving scenario. Thus, we conjecture that
there exists an optimal $\delta^{*}$ that allows for drivers to adapt to the
advised actions while providing the most updated advice. From Table I, it is
clear that such an optimal $\delta^{*}$ exists when looking at each policy’s
performance individually. In our case, $\delta=20$ that corresponds to a hold-
length of 2s. We speculate further that this optimal $\delta^{*}$ would depend
on the network parameters and the number of cars.

As a hold-length of 1s is impractical, the results for that hold-length do not
provide substantial inference when compared to larger hold-lengths. These
results are included solely to allow for comparison with previous work that
utilizes AVs. For more practical $\delta$s (20, 50), PeRP consistently
outperforms the baselines. As expected, a hold-length of 10s is too large and
leads to significant detriment in performance. All policies also perform well
in the case of $\delta=1$11footnotemark: 1. This $\delta$ corresponds to a
completely online scenario where there is no action extension. The policies’
performance for this $\delta$ showed similar albeit slightly worse performance
with metrics aligning with those of $\delta=10$. However, a $\delta$ of 1 is
even more impractical than $\delta=10$ as human controlled actions cannot
change in $0.1$s.

PeRP achieves an improvement of 22% over standard speed limit guidance (OSL)
and 4% over guidance provided by PC policies for $\delta=5$s. Comparisons on
the average standard deviation also show similar results with the PeRP policy
for $\delta=2$s achieving improvements of 10% over OSL and 3% over PC
policies. While these results are promising and significant, we emphasize that
they were obtained completely in simulation, without a human-in-the-loop.
Therefore, we encourage the evaluation of these policies with user studies for
further analysis.

##  VII Conclusion and Future Work

In this paper, we present PeRP, a novel Personalized Residual Policies for
congestion mitigation. We demonstrate the efficacy of our model in a robust
simulation study and showcase its ability to adapt to different driving
styles. Particularly, we utilize a novel driver trait inference model to
capture nuances in driver behaviors towards following instructions to
condition our residual policy. Our PeRPs show improvements over all baselines,
including PC Policies.

This advancement was built on four assumptions which can be relaxed to open
the following avenues for future work: (1) More robust policies should be
trained with careful modeling for the driver policy, $\pi^{driver}$, that
consider driver reaction times and distractions; (2) As Piecewise Constant
Policies have empirically been shown to be robust to lane changes, extending
PeRP to account for these changes would further increase its applicability;
(3) Designing and testing PeRPs where multiple agents receive instructions
simultaneously would drastically improve congestion mitigation and would
provide a realizable bridge towards a fully AV controlled traffic setting; (4)
As our policies are trained and evaluated completely in simulation, a human-
in-the-loop user study would provide further credence to the claims showcased
here. While naturalistic driving studies would be ideal, driving simulator
studies can be performed without considerable effort using the CARLA driving
simulator [53]. Particularly, works that have integrated the flow framework
with CARLA can be used to easily test our model [45]. As shown in this paper,
future work in advisory algorithms can mitigate congestion by compensating for
users’ diverse following behavior.

## References

  * [1] United States. Environmental Protection Agency. Office of Policy, _Inventory of US greenhouse gas emissions and sinks: 1990-2020_. United States Environment Protection Agency, 2020\.
  * [2] M. Barth and K. Boriboonsomsin, “Real-world carbon dioxide impacts of traffic congestion,” _Transportation Research Record_ , vol. 2058, pp. 163–171, 2008\.
  * [3] P. Goodwin, “The economic costs of road traffic congestion,” 2004.
  * [4] L. Carnis and E. Blais, “An assessment of the safety effects of the french speed camera program,” _Accident Analysis & Prevention_, vol. 51, pp. 301–309, 2013.
  * [5] C. G. Wilmot and M. Khanal, “Effect of speed limits on speed and safety: A review,” _Transport Reviews_ , vol. 19, no. 4, pp. 315–329, 1999.
  * [6] C. Wu, A. R. Kreidieh, K. Parvate, E. Vinitsky, and A. M. Bayen, “Flow: A modular learning framework for mixed autonomy traffic,” _IEEE Transactions on Robotics_ , 2021.
  * [7] R. E. Stern, S. Cui, M. L. Delle Monache, R. Bhadani, M. Bunting, M. Churchill, N. Hamilton, R. Haulcy, H. Pohlmann, F. Wu, B. Piccoli, B. Seibold, J. Sprinkle, and D. B. Work, “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.
  * [8] N. Kalra and S. M. Paddock, _Driving to Safety: How Many Miles of Driving Would It Take to Demonstrate Autonomous Vehicle Reliability?_ RAND Corporation, 2016.
  * [9] V. V. Dixit, S. Chand, and D. J. Nair, “Autonomous vehicles: Disengagements, accidents and reaction times,” _PLOS ONE_ , vol. 11, no. 12, pp. 1–14, 12 2016.
  * [10] M. Marcano, S. Díaz, J. Pérez, and E. Irigoyen, “A review of shared control for automated vehicles: Theory and applications,” _IEEE Transactions on Human-Machine Systems_ , vol. 50, pp. 475–491, 2020.
  * [11] M. Sridhar and C. Wu, “Piecewise constant policies for human-compatible congestion mitigation,” in _IEEE International Intelligent Transportation Systems Conference_ , 2021.
  * [12] C. Wu, A. Kreidieh, E. Vinitsky, and A. M. Bayen, “Emergent behaviors in mixed-autonomy traffic,” in _Conference on Robot Learning_ , 2017.
  * [13] A. R. Kreidieh, C. Wu, and A. M. Bayen, “Dissipating stop-and-go waves in closed and open networks via deep reinforcement learning,” in _IEEE International Conference on Intelligent Transportation Systems_ , Nov 2018, pp. 1475–1480.
  * [14] E. Vinitsky, K. Parvate, A. Kreidieh, C. Wu, and A. Bayen, “Lagrangian Control through Deep-RL: Applications to Bottleneck Decongestion,” in _IEEE International Conference on Intelligent Transportation Systems_ , Nov 2018, pp. 759–765.
  * [15] Z. Yan and C. Wu, “Reinforcement Learning for Mixed Autonomy Intersections,” in _IEEE International Intelligent Transportation Systems Conference_ , Sep 2021, pp. 2089–2094.
  * [16] V. Jayawardana and C. Wu, “Reinforcement learning for eco-lagrangian control at intersections,” in _European Control Conference_ , 2022.
  * [17] V. Jayawardana, A. Landler, and C. Wu, “Mixed Autonomous Supervision in Traffic Signal Control,” in _IEEE International Intelligent Transportation Systems Conference_ , Sep 2021, pp. 1767–1773.
  * [18] M. Wegener, L. Koch, M. Eisenbarth, and J. Andert, “Automated eco-driving in urban scenarios using deep reinforcement learning,” _Transportation Research Part C: Emerging Technologies_ , vol. 126, p. 102967, 2021.
  * [19] A. M. Metelli, F. Mazzolini, L. Bisi, L. Sabbioni, and M. Restelli, “Control Frequency Adaptation via Action Persistence in Batch Reinforcement Learning,” in _Proceedings of the 37th International Conference on Machine Learning_ , Nov 2020, pp. 6862–6873.
  * [20] S. Li, R. Dong, and C. Wu, “Integrated Analysis of Human-compatible Control for Traffic Flow Stability,” Jan 2023. [Online]. Available: http://arxiv.org/abs/2301.04043
  * [21] P. Abbeel, M. Quigley, and A. Y. Ng, “Using inaccurate models in reinforcement learning,” in _Proceedings of the 23rd International Conference on Machine Learning_ , 2006.
  * [22] Y. Jiang, J. Sun, and C. K. Liu, “Data-augmented contact model for rigid body simulation,” in _Proceedings of The 4th Annual Learning for Dynamics and Control Conference_ , ser. Proceedings of Machine Learning Research, vol. 168, 23–24 Jun 2022, pp. 378–390.
  * [23] A. Zeng, S. Song, J. Lee, A. Rodriguez, and T. Funkhouser, “Tossingbot: Learning to throw arbitrary objects with residual physics,” _Trans. Rob._ , vol. 36, no. 4, p. 1307–1319, Aug 2020.
  * [24] A. Ajay, J. Wu, N. Fazeli, M. Bauzá, L. P. Kaelbling, J. B. Tenenbaum, and A. Rodriguez, “Augmenting physical simulators with stochastic neural networks: Case study of planar pushing and bouncing,” _IEEE/RSJ International Conference on Intelligent Robots and Systems_ , pp. 3066–3073, 2018\.
  * [25] C. Schaff and M. R. Walter, “Residual policy learning for shared autonomy,” _Proceedings of Robotics: Science and Systems_ , 2020.
  * [26] T. Silver, K. R. Allen, J. Tenenbaum, and L. P. Kaelbling, “Residual policy learning,” _CoRR_ , vol. abs/1812.06298, 2018.
  * [27] T. Johannink, S. Bahl, A. Nair, J. Luo, A. Kumar, M. Loskyll, J. A. Ojea, E. Solowjow, and S. Levine, “Residual reinforcement learning for robot control,” in _2019 International Conference on Robotics and Automation_ , 2019.
  * [28] K. Rana, M. Xu, B. Tidd, M. Milford, and N. Suenderhauf, “Residual skill policies: Learning an adaptable skill-based action space for reinforcement learning for robotics,” in _Proceedings of The 6th Conference on Robot Learning_ , ser. Proceedings of Machine Learning Research, vol. 205, 14–18 Dec 2023, pp. 2095–2104.
  * [29] R. Zhang, J. Hou, G. Chen, Z. Li, J. Chen, and A. Knoll, “Residual policy learning facilitates efficient model-free autonomous racing,” _IEEE Robotics and Automation Letters_ , vol. 7, pp. 11 625–11 632, 2022.
  * [30] K. Brown, K. Driggs-Campbell, and M. J. Kochenderfer, “A taxonomy and review of algorithms for modeling and predicting human driver behavior,” _arXiv preprint arXiv:2006.08832_ , 2020.
  * [31] N. Deo, A. Rangesh, and M. M. Trivedi, “How would surround vehicles move? A unified framework for maneuver classification and motion prediction,” _IEEE Trans. Intell. Veh._ , vol. 3, no. 2, pp. 129–140, 2018.
  * [32] K. Gillmeier, F. Diederichs, and D. Spath, “Prediction of ego vehicle trajectories based on driver intention and environmental context,” in _IEEE Intelligent Vehicles Symposium_ , 2019, pp. 963–968.
  * [33] Z. Huang, A. Hasan, K. Shin, R. Li, and K. Driggs-Campbell, “Long-term pedestrian trajectory prediction using mutable intention filter and warp lstm,” _IEEE Robotics and Automation Letters_ , vol. 6, no. 2, pp. 542–549, 2020.
  * [34] J. Liu, Y. Luo, H. Xiong, T. Wang, H. Huang, and Z. Zhong, “An integrated approach to probabilistic vehicle trajectory prediction via driver characteristic and intention estimation,” in _IEEE Intelligent Transportation Systems Conference_ , 2019, pp. 3526–3532.
  * [35] J. Morton and M. J. Kochenderfer, “Simultaneous policy learning and latent state inference for imitating driver behavior,” in _IEEE International Conference on Intelligent Transportation Systems_ , 2017.
  * [36] S. Liu, P. Chang, H. Chen, N. Chakraborty, and K. Driggs-Campbell, “Learning to navigate intersections with unsupervised driver trait inference,” in _IEEE International Conference on Robotics and Automation_ , 2022.
  * [37] X. Ma, J. Li, M. J. Kochenderfer, D. Isele, and K. Fujimura, “Reinforcement learning for autonomous driving with latent state inference and spatial-temporal relationships,” in _IEEE International Conference on Robotics and Automation_ , 2021.
  * [38] A. Xie, D. Losey, R. Tolsma, C. Finn, and D. Sadigh, “Learning latent representations to influence multi-agent interaction,” in _Proceedings of the 2020 Conference on Robot Learning_ , ser. Proceedings of Machine Learning Research, vol. 155, 16–18 Nov 2021, pp. 575–588.
  * [39] W. Z. Wang and A. Shih, “Influencing towards stable multi-agent interactions,” in _Conference on Robot Learning_ , 2021.
  * [40] S. Parekh, S. Habibian, and D. P. Losey, “Rili: Robustly influencing latent intent,” 2022.
  * [41] D. Kingma and M. Welling, “Auto-encoding variational bayes.” in _Conference on Learning Representations_ , 2014.
  * [42] 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.
  * [43] P. Droździel, S. Tarkowski, I. Rybicka, and R. Wrona, “Drivers’ reaction time research in the conditions in the real traffic,” _Open Engineering_ , vol. 10, no. 1, pp. 35–47, 2020.
  * [44] R. S. Jurecki, T. L. Stańczyk, and M. J. Jaśkiewicz, “Driver’s reaction time in a simulated, complex road incident,” _Transport_ , vol. 32, no. 1, pp. 44–54, 2017.
  * [45] A. Hasan, N. Chakraborty, C. Wu, and K. Driggs-Campbell, “Towards co-operative congestion mitigation,” in _Proceedings of the ‘Shared Autonomy in Physical Human-Robot Interaction: Adaptability and Trust Workshop‘ at the IEEE International Conference on Robotics and Automation_ , 2022\.
  * [46] F. Mannering, “An empirical analysis of driver perceptions of the relationship between speed limits and safety,” _Transportation Research Part F: Traffic Psychology and Behaviour_ , vol. 12, pp. 99–106, 2009.
  * [47] A. Hasan, P. Sriram, and K. Driggs-Campbell, “Meta-path analysis on spatio-temporal graphs for pedestrian trajectory prediction,” in _IEEE International Conference on Robotics and Automation_ , 2022.
  * [48] C. Wu, A. R. Kreidieh, K. Parvate, E. Vinitsky, and A. M. Bayen, “Flow: A modular learning framework for mixed autonomy traffic,” _IEEE Transactions on Robotics_ , vol. 38, no. 2, pp. 1270–1286, 2022.
  * [49] 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 _The 21st IEEE International Conference on Intelligent Transportation Systems_ , 2018.
  * [50] J. Schulman, S. Levine, P. Abbeel, M. Jordan, and P. Moritz, “Trust region policy optimization,” in _Proceedings of the 32nd International Conference on Machine Learning_ , ser. Proceedings of Machine Learning Research, vol. 37, 07–09 Jul 2015, pp. 1889–1897.
  * [51] A. Reuther, J. Kepner, C. Byun, S. Samsi, W. Arcand, D. Bestor, B. Bergeron, V. Gadepally, M. Houle, M. Hubbell, M. Jones, A. Klein, L. Milechin, J. Mullen, A. Prout, A. Rosa, C. Yee, and P. Michaleas, “Interactive supercomputing on 40,000 cores for machine learning and data analysis,” in _2018 IEEE High Performance extreme Computing Conference_ , 2018, pp. 1–6.
  * [52] V. Kindratenko, D. Mu, Y. Zhan, J. Maloney, S. H. Hashemi, B. Rabe, K. Xu, R. Campbell, J. Peng, and W. Gropp, “Hal: Computer system for scalable deep learning,” in _Practice and Experience in Advanced Research Computing_ , ser. Pearc ’20, 2020, p. 41–48.
  * [53] A. Dosovitskiy, G. Ros, F. Codevilla, A. Lopez, and V. Koltun, “CARLA: An open urban driving simulator,” in _Proceedings of the 1st Annual Conference on Robot Learning_ , 2017, pp. 1–16.


# Optimization of BDD-based
Approximation Error Metrics Calculations

Vojtech Mrazek  Brno University of Technology, Faculty of Information
Technology
Brno, Czech Republic
<EMAIL_ADDRESS>
###### Abstract

Software methods introduced for automated design of approximate
implementations of arithmetic circuits rely on fast and accurate evaluation of
approximate candidate implementations. To accelerate the evaluation of circuit
error, we propose four novel algorithms for the exact worst-case and mean
absolute error analysis based on Binary Decision Diagrams. As these algorithms
do not compute any absolute values in the characteristic function, which
basically compares a candidate approximate circuit with a golden circuit, the
error evaluation is significantly faster than the standard BDD-based error
analysis. On average, the proposed algorithms are three times faster (in some
cases, 30 times faster) than the baseline for 8- to 32-bit approximate adders.
These results were obtained from more than 49 thousand runs with different
configurations of the method. The proposed error evaluation algorithms are
available as an open-source software https://github.com/ehw-fit/bdd-
evaluation.

###### Index Terms:

approximate computing, error calculation, binary-decision diagrams

##  I Introduction

Minimizing power consumption is one of the most significant objectives for
current digital circuit design. In many applications, such as image or signal
processing, the users are also often willing to accept certain errors if they
are accompanied by reduced power consumption or other improvements. This
paradigm, called approximate computing [1], systematically tries to find the
best trade-offs between the quality of output and hardware parameters such as
area, power consumption, or latency. One of the most widely used methods is
replacing the standard arithmetic circuits with approximate implementations
[1]. The circuit approximation techniques can be classified as manual (e.g.,
[2]) and automated (e.g., [3, 4]). From a broader perspective, the automated
methods usually provide better trade-offs between the error and other circuit
parameters. These methods typically start with an exact circuit and modify it
using the following iterative scheme: (i) generate candidate approximate
circuits, (ii) evaluate these circuits, and (iii) select the best candidate
for the next iteration. As many candidate circuits are usually generated, it
is essential to quickly analyze their error [4].

Let $f:\mathbb{B}^{n}\rightarrow\mathbb{B}^{m}$ be an $n$-input $m$-output
Boolean function that describes the correct functionality (the accurate
function) and $f^{\prime}:\mathbb{B}^{n}\rightarrow\mathbb{B}^{m}$ be an
approximation of it with error $\varepsilon$, formally $\forall
x\in\mathbb{B}^{n}:f(x)\approx
f^{\prime}(x);f^{\prime}(x)=f(x)+\varepsilon(x)$. If there is no analytical
model of the error function $\varepsilon$ (which can, in fact, be easily
derived only for a few approximation techniques such as bit-truncation), the
error of $f^{\prime}$ has to be determined for all possible input
combinations, i.e. $|\mathbb{B}^{n}|=2^{n}$. The evaluation time grows
exponentially with $n$, but can effectively be reduced by parallel circuit
simulation [5] or formal verification techniques such as SAT, BDDs or
algebraic solvers [4, 6].

The formal verification techniques achieve very good performance for the error
evaluation [4]. However, some of them do not scale for some types of circuits
or error metrics. For example, SAT solving is applicable for determining the
worst-case error but useless for the mean error. BDD-based methods are not
applicable to structurally complex circuits such as multipliers.

In this paper, we deal with efficient error analysis methods using BDDs. The
calculation is based on the so-called characteristic function $|f-f^{\prime}|$
represented as a Boolean equation [7]. Keszocze [6] introduced a technique
that does not need to compute the absolute value which represents the
performance bottleneck. On the other hand, this algorithm assumes that
$\forall x:f^{\prime}(x)\leq f(x)$ and can produce only such solutions that
satisfy this assumption. However, this assumption is not realistic is general-
purpose approximation engines (such as [4]) in which arbitrary candidate
approximations must be evaluated.

This paper aims to propose new algorithms for the exact error analysis that
further simplify the characteristic function without postulating any specific
constraint on the evaluated function $f^{\prime}$.

We propose four error calculation algorithms (two for the worst-case error and
two for the mean-absolute error). These algorithms omit the absolute value
calculation while the average error evaluation time is reduced $3\times$
compared to the standard BDD-based approach. Moreover, they also reduce the
memory complexity, and in some cases, the speedup is $10-30\times$.

The proposed error analysis algorithms were employed in a circuit
approximation method based on CGP, which is inspired in [4]. In our
experiments, the error evaluation was executed for billions of adders. The
resulting approximate adders exhibit better trade-offs than the approximate
adders published in the EvoApprox library [8]. All approximate implementations
are available for download (TBD). The C++ implementation of the error analysis
algorithms is provided as an open-source software https://github.com/ehw-
fit/bdd-evaluation.

##  II Approximate computing

Approximate computing aims to introduce an error into a software or hardware
implementation. It can be done on various levels: algorithmic, functional, or
physical. We focus on the functional approximation (i.e., modification of
Boolean functions describing the logic behavior of digital circuits) of
arithmetic circuits that may be used as basic building blocks in complex
systems.

###  II-A Error metrics

There are various application-independent error metrics used in the literature
[2]. The _worst-case arithmetic error_ , sometimes denoted as _error
magnitude_ or _error significance_ , is defined as

$e_{wce}(f,f’)=\max_{\forall x\in\mathbb{B}^{n}}|int(f(x))-int(f’(x))|,$ (1)

where $int(x)$ represents a function $int:\mathbb{B}^{m}\rightarrow\mathbb{Z}$
returning an integer value of the $m$-bit binary vector $x$. Typically, a
natural unsigned binary representation is considered, i.e.
$int(x)=\sum_{i=1}^{m}{2^{i}\cdot x_{i}}$. The worst-case error represents the
fundamental metric that is useful to guarantee that the approximate output
differs from the correct output by at most the error bound $e$.

The _average-case arithmetic error_ (also known as _mean absolute error_) is
defined as the sum of absolute differences in magnitude between the original
and approximate circuit, averaged over all inputs:

$e_{mae}(f,f’)=2^{-n}\sum_{\forall
x\in\mathbb{B}^{n}}{|int(f(x))-int(f’(x))|}.$ (2)

Note that the values produced by the “absolute” error metrics $e_{mae}$ and
$e_{wce}$ can be very high. Hence, these values can be expressed relatively to
the output range, using division by $2^{m}-1$, i.e. the maximal output value.

In the metric error formulas, the enumeration of all possible input vectors is
present. For $n$ greater than approx. 24, it is not feasible to enumerate
$\mathbb{B}^{n}$ in a reasonable time even when a highly parallel circuit
simulator is employed.

This issue can partly be eliminated by utilizing a formal verification
approach for the error calculation. Formal techniques typically construct a
virtual miter circuit to compute the characteristic function. Reduced Ordered
Binary Decision Diagrams (BDD) or SAT solving-based methods were employed in
the area of approximate circuits. ROBDDs are suitable for the formal error
analysis of less complex circuits (such as adders) for which the BDD does not
grow exponentially with $n$. SAT solving can effectively handle determining
the worst-case error for up to 32-bit multipliers but does not provide
suitable results for other error metrics. Details of BDDs are elaborated in
Section II-C.

###  II-B Automated design techniques

The automated approximation algorithms iteratively modify a given accurate
circuit to achieve the best trade-off between the error and other circuit
parameters. The most recent algorithms use various approaches for circuit
representation and error evaluation. Soeken et al. proposed an algorithm that
directly modifies the BDD [7, 6]. This algorithm satisfies the assumption of
the fast error evaluation, but its design space is limited. Another approach
is to use some internal circuit representation. Hashemi et al. divided the
original circuit into subcircuits and approximated each of them. Finally, the
error was evaluated for many candidate solutions [3]. A specific internal
circuit representation is used in Cartesian Genetic Programming (CGP) [4]
which is a heuristic design-space exploration algorithm. Candidate circuits
are represented as directed acyclic graphs in a fixed grid of nodes. The
algorithm randomly changes the connections between nodes and the nodes’
functions. It uses the following fitness function for a given error metric $e$
(e.g., $e_{mae}$ or $e_{wce}$) and the acceptable error threshold $\tau$

$\mathbf{F}(f^{\prime})=\begin{cases}size(f^{\prime})&\text{if
}e(|f-f^{\prime}|)\leq\tau\\\ \infty&\text{otherwise}\\\ \end{cases}.$ (3)

This algorithm starts with an accurate solution and reduces its size while
keeping the error constraint satisfied. The result of the search is the
smallest circuit satisfying the constraint $\tau$.

###  II-C BDDs

This work exploits the Reduced Ordered Binary Decision Diagrams (ROBDDs, also
referred to as BDDs). ROBDD is a canonical rooted acyclic graph-based
representation of a Boolean function, where each node represents either an
input variable or terminal node, and the edges represent the value assignment.
There are two terminal nodes – true and false. ROBDDs have been traditionally
used to solve the equivalence checking problem due to their canonical property
(i.e., the ROBDDs of two logic functions are isomorphic if the functions are
functionally equivalent and the input variables have the same order). The
tools, developed for constructing and manipulating ROBDDs, can exactly answer
the following questions: (1) whether a variable (signal) in the circuit is
satisfiable, i.e., whether an input vector exists which generates a true value
of the signal; and (2) the probability that a selected variable is true.
Although these questions are answered fast (by finding some paths in the
ROBDD), the construction of the ROBDD is not trivial, and in some circuits
such as multipliers, the ROBDDs grow exponentially with $n$.

Since there is no significant difference in the performance of major tools
operating with ROBDDs [9], we selected BuDDy and CUDD tools, which also
support dynamic variables reordering for evaluation. In these tools, the BDD
node is represented by a structure. Starting with an input node, these tools
allow adding new nodes by applying logical operations
($\neg,\wedge,\vee,\oplus,\dots$) to two existing nodes. Therefore, one can
construct an arbitrary Boolean function.

####  II-C1 Conventions and notations

Henceforth, we denote an $n$-input $m$-output Boolean function as $f$. Without
loss of generality the functions can be represented by the BDDs
$f=(f_{n},f_{n-1},\dots f_{2},f_{1})$ where each output bit $f_{i}$ is a BDD
node. For integer functions, $f_{\mathrm{sign}}$ denotes the sign bit $f_{n}$.

For one-output function (i.e., BDD node) the tools can provide the probability
that a selected node $f_{i}$ is true

$\mathrm{\\#SAT}(f_{i})=2^{-n}\cdot|\\{x:f_{i}(x)=\textrm{True}\\}|$

and a Boolean value $\mathrm{SAT}(f_{i})$ answering whether the node $f_{i}$
becomes true for any input.

We also implemented two arithmetic Boolean functions as BDDs. The Addition
function $\mathrm{add}(a,b)$ creates a Ripple-carry adder with output nodes of
functions $a$ and $b$ as inputs. Similarly, subtraction
$\mathrm{subtract}(a,b)$ is constructed in the same way, but the $b$ outputs
are inverted, and the carry input is set. Note that the input vectors must be
(sign-) extended to handle both signed and unsigned variants of $a$ and $b$.

####  II-C2 Existing algorithms (BASELINE)

In [7], Soeken et al. proposed the error analysis based on calculating
characteristic function $r=|f(x)-f^{\prime}(x)|$. For the resulting vector $r$
they calculate the maximal (wce) and average (mae) values. Their best-
performing algorithm is based on a binary search (Alg. 1). Firstly, the values
are subtracted (ln. 1), which is captured by a signed function $\varepsilon$,
and the absolute value is obtained (unsigned $r$). The absolute value has to
deal with the two’s complement and increments the value if the result is
negative (ln. 4). The binary search starts with the MSB, computes the worst-
case error $wce$ and also the function $\mu:\mu(x)=1$ if and only if
$r(x)=wce$.

Input : Functions $f$ and $f^{\prime}$ as ROBDDs

Output : Worst-case error ($wce$)

$\varepsilon\leftarrow\mathrm{subtract}(f,f^{\prime})$ ;

// subtract results

1

2for  _$i\leftarrow 1$ to $|\varepsilon|-1$_ do

$r_{i}\leftarrow\varepsilon_{i}\oplus\varepsilon_{\mathrm{sign}}$ ;

// absolute value

3

$r\leftarrow\mathrm{add}(r,\\{\varepsilon_{\mathrm{sign}}\\})$ ;

// two’s complement

4

5$\mu\leftarrow$ True;

6 $wce\leftarrow 0$;

7 for  _$i\leftarrow|r|$ to $1$ _ do // binary search

8 if  _$\mathrm{SAT}(\mu\wedge r_{i})$_ then

9 $wce\leftarrow wce+2^{i-1}$;

10 $\mu\leftarrow\mu\wedge r_{i}$;

11

12

13return $wce$;

Algorithm 1 Baseline WCE calculation using two’s complement

The average (mean absolute error) is calculated (Alg. 2) with the same
characteristic function $r$. The weighted sum of positive-bit probabilities is
computed. Finally, the sum is divided by $2^{n}$ while $n$ is the number of
inputs of functions $f$ and $f^{\prime}$.

Input : Functions $f$ and $f^{\prime}$ as ROBDDs

Output : Mean absolute error ($mae$)

$\varepsilon\leftarrow\mathrm{subtract}(f,f^{\prime})$ ;

// subtract results

1

2for  _$i\leftarrow 1$ to $|\varepsilon|-1$_ do

$r_{i}\leftarrow\varepsilon_{i}\oplus\varepsilon_{\mathrm{sign}}$ ;

// absolute value

3

4

$r\leftarrow\mathrm{add}(r,\\{\varepsilon_{\mathrm{sign}}\\})$ ;

// two’s complement

5

6$mae\leftarrow 0$;

7 for  _$i\leftarrow 1$ to $|r|$_ do

8 $mae\leftarrow mae+2^{i-1}\cdot\mathrm{\\#SAT}(r_{i})$ ;

9

10return $mae$ ;

Algorithm 2 Baseline MAE calculation using two’s complement

Keszocze showed that the subtraction and absolute value calculation are the
most time-consuming parts of the evaluation [6],. He also proposed a fast
algorithm for determining the MAE without the characteristic function. This
algorithm needs to satisfy a condition that $\forall x:f^{\prime}(x)\leq
f(x)$. Automated iterative approximation algorithms typically cannot satisfy
this condition, therefore, we are not able to employ this algorithm in a CGP-
based approximation engine.

##  III Proposed MAE and WCE calculation

We present improvements of the baseline error evaluation algorithms to omit
the absolute value calculation. We propose two approaches — one replaces the
absolute value by approximation in ones’ complement, the second one handles
the positive and negative branches separately.

###  III-A Ones’ complement (ONES’)

In the baseline Algorithms 1,2 (ln. 4), the increment of $r$ vector by a sign
bit is needless. In the proposed algorithm (Alg. 3), we omitted this addition.
We obtain the exact $wce$ for positive $r$; and ${wce}$ decreased by $1$ if
the maximal error is in the negative $r$. Because this condition is expressed
in the MSB node of $\varepsilon$, the error can be compensated (ln. 10 - 11).

Input : Functions $f$ and $f^{\prime}$ as ROBDDs

Output : Worst-case error (${wce}$)

$\varepsilon\leftarrow\mathrm{subtract}(f,f^{\prime})$ ;

// subtract results

1

2for  _$i\leftarrow 1$ to $|\varepsilon|-1$_ do

$r_{i}\leftarrow\varepsilon_{i}\oplus\varepsilon_{\mathrm{sign}}$ ;

// absolute value

3

4

5$\mu\leftarrow$ True;

6 $wce\leftarrow 0$;

7

8for  _$i\leftarrow|r|$ to $1$ _ do // binary search

9 if  _$\mathrm{SAT}(\mu\wedge r_{i})$_ then

10 $wce\leftarrow wce+2^{i-1}$;

11 $\mu\leftarrow\mu\wedge r_{i}$;

12

13

14

15if  _$\mathrm{SAT}(\mu\wedge\varepsilon_{\mathrm{sign}})$_ then //
complement corr.

16 $wce\leftarrow wce+1$ ;

17

18return $wce$;

Algorithm 3 Proposed WCE calculation using ones’ complement

A similar approach is used in the average error calculation (Alg. 4). The
error by 1 can be corrected by adding the proportion of negative numbers
$\varepsilon$, i.e. $\mathrm{\\#SAT}(\varepsilon_{\mathrm{sign}})$ (ln. 7).

Input : Functions $f$ and $f^{\prime}$ as ROBDDs

Output : Mean absolute error ($mae$)

$\varepsilon\leftarrow\mathrm{subtract}(f,f^{\prime})$ ;

// subtract results

1

2for  _$i\leftarrow 1$ to $|\varepsilon|-1$_ do

$r_{i}\leftarrow\varepsilon_{i}\oplus\varepsilon_{\mathrm{sign}}$ ;

// absolute value

3

4

5$mae\leftarrow 0$;

6 for  _$i\leftarrow 1$ to $|r|$_ do

7 $mae\leftarrow mae+2^{i-1}\cdot\mathrm{\\#SAT}(r_{i})$ ;

8

9

$mae\leftarrow mae+\mathrm{\\#SAT}(\varepsilon_{\mathrm{sign}})$ ;

// correction

10 return $mae$ ;

Algorithm 4 Proposed MAE calculation using ones’ complement

###  III-B Omitting the absolute values (NOABS)

The second proposed approach exploits the fact that we can build two BDD trees
for the resulting vector $\varepsilon$ — one for the positive part
$\neg\varepsilon_{\mathrm{sign}}\wedge\varepsilon_{i}$ and one for the
negative part $\varepsilon_{\mathrm{sign}}\wedge\varepsilon_{i}$. The worst-
case error calculation is shown in Alg. 5. Since the absolute error is
calculated using XOR operations which make the resulting BDDs more complex,
the WCE value is calculated directly from the signed result of subtraction
$\varepsilon$. If the sign bit is negative, a binary search of the maximal
value is performed as $wce_{p}$. On the other hand, the negative part is
transformed to searching the minimal value $wce_{n}$. The subtraction result
$\varepsilon$ is expressed as two’s complement. Therefore, the negative
$wce_{n}$ is incremented by 1, and the maximal value is returned (ln. 14).

Input : Functions $f$ and $f^{\prime}$ as ROBDDs

Output : Worst-case error ($wce$)

$\varepsilon\leftarrow\mathrm{subtract}(f,f^{\prime})$ ;

// subtract results

1

/* positive error */

2 $\mu_{p}\leftarrow\neg\varepsilon_{\mathrm{sign}}$;

3 $wce_{p}\leftarrow 0$;

4 for  _$i\leftarrow|\varepsilon|-1$ to $1$ _ do // binary search

5 if  _$\mathrm{SAT}(\mu_{p}\wedge\varepsilon_{i})$_ then

6 $wce_{p}\leftarrow wce_{p}+2^{i-1}$;

7 $\mu_{p}\leftarrow\mu_{p}\wedge\varepsilon_{i}$;

8

9

10

/* negative error */

11 $\mu_{n}\leftarrow\varepsilon_{\mathrm{sign}}$;

12 $wce_{n}\leftarrow 0$;

13 for  _$i\leftarrow|\varepsilon|-1$ to $1$ _ do // binary search

14 if  _$\mathrm{SAT}(\mu_{n}\wedge\neg\epsilon_{i})$_ then

15 $wce_{n}\leftarrow wce_{n}+2^{i-1}$;

16 $\mu_{n}\leftarrow\mu_{n}\wedge\neg\varepsilon_{i}$;

17

18

19return $\max(wce_{p},wce_{n}+1)$;

Algorithm 5 Proposed WCE calculation without the absolute value (NOABS)

The mean average error calculation (Alg. 6) employs two BDD trees — for the
positive part anded with the unset sign bit $\neg\varepsilon_{\mathrm{sign}}$
and for the negative inverted anded with a set sign bit
$\varepsilon_{\mathrm{sign}}$. The negative part introduces an error by one,
which can easily be compensated by adding the probability at line 6.

Input : Functions $f$ and $f^{\prime}$ as ROBDDs

Output : Mean absolute error ($mae$)

$\varepsilon\leftarrow\mathrm{subtract}(f,f^{\prime})$ ;

// subtract results

1 $mae\leftarrow 0$;

2 for  _$i\leftarrow 1$ to $|\varepsilon|-1$_ do

3 $mae\leftarrow
mae+2^{i-1}\cdot\mathrm{\\#SAT}(\varepsilon_{i}\wedge\neg\varepsilon_{\mathrm{sign}})$
;

4 $mae\leftarrow
mae+2^{i-1}\cdot\mathrm{\\#SAT}(\neg\varepsilon_{i}\wedge\varepsilon_{\mathrm{sign}})$
;

5

6

$mae\leftarrow mae+\mathrm{\\#SAT}(\varepsilon_{\mathrm{sign}})$ ;

// complement corr.

7 return $mae$ ;

Algorithm 6 Proposed MAE calculation without the absolute value (NOABS)

All the proposed algorithms follow the scheme of WCE and MAE calculation
introduced by Soeken et al. [7] However, the absolute value calculation is
partially (in ones’) or totally (in noabs) transformed from the BDD function
to mathematical corrections.

##  IV Experiments

###  IV-A Experimental setup

To evaluate the quality of the proposed error calculation algorithms, we
employed them in the CGP-based approximation of adders (both signed and
unsigned). The overall scheme of the approximation engine is given in Figure
1. In the search loop, tens of thousands of candidate approximate adders were
generated and their errors calculated. We collected all results and analyzed
them statistically.

Figure 1: Experimental setup of CGP-based search engine employing the proposed
error calculation algorithms.

The key component of the calculation is the BDD library, which provides an
abstraction to BDD trees. It implements the functions deciding the
satisfiability $\mathrm{SAT}(d)$ and calculating the probability
$\mathrm{\\#SAT}(d)$. We compared two state-of-the-art libraries — BuDDy and
CuDD. The cache memory of BuDDy was set to $10^{7}$ accordingly to the
documentation. Similarly, default size of CuDD cache ($2^{18}=262,144$) was
used.

The maximal allowed MAE and WCE errors that are the key parameters of CGP
exponentially vary from 2 to $0.2\cdot 2^{n+1}$ (20% of the output range). As
a CGP seed, three adder types are considered: carry-look-ahead, carry-skip,
and ripple-carry adders, unsigned and signed versions, for bit-widths 8 to 32
(of each operand). Since the CGP approximation is a stochastic approach, 5
independent runs are executed for each setup. Finally, the best adders are
synthesized using Synopsys Design Compiler with 45 nm technology.

All experiments were executed on a computer cluster with nodes having 2 CPU
Intel Xeon E5-2670 2,6 GHz, 16-core, 20 MB cache, and 64 GB RAM. Each run was
a single thread (with 2 GB of memory), and 32 runs were executed on the node.
In total, 49,716 independent runs were performed to evaluate the above-
mentioned setups.

###  IV-B CGP Approximation with BDD-based error evaluation

Table I shows that BuDDy library leads to a faster error evaluations than
CuDD, except the baseline algorithm for 32-bit adders. The results are
aggregated over all the error thresholds. On average, CuDD is 2x slower than
BuDDy. The addition of 8 inputs ($n$) leads to a 4-20x slow down for both
libraries.

TABLE I: The average evaluation time [s] for different BDD libraries

Error | Bit-width | Baseline | Ones’ | Noabs
---|---|---|---|---
| $n/2$ | BuDDy | CuDD | BuDDy | CuDD | BuDDy | CuDD
MAE | 8 | 0.0001 | 0.0003 | 0.0001 | 0.0002 | 0.0001 | 0.0003
12 | 0.0009 | 0.0017 | 0.0003 | 0.0009 | 0.0004 | 0.0013
16 | 0.0044 | 0.0084 | 0.0013 | 0.0039 | 0.0017 | 0.0056
20 | 0.1818 | 0.2066 | 0.0063 | 0.0223 | 0.0113 | 0.1041
24 | 1.4713 | 1.8158 | 0.2438 | 0.6416 | 0.3537 | 0.8289
32 | 7.3208 | 6.1494 | 3.5416 | 4.7556 | 4.1580 | 4.7180
WCE | 8 | 0.0001 | 0.0002 | 0.0001 | 0.0001 | 0.0001 | 0.0001
12 | 0.0007 | 0.0010 | 0.0002 | 0.0005 | 0.0002 | 0.0005
16 | 0.0038 | 0.0051 | 0.0011 | 0.0023 | 0.0009 | 0.0018
20 | 0.0446 | 0.0910 | 0.0055 | 0.0114 | 0.0038 | 0.0072
24 | 0.8281 | 0.9924 | 0.1044 | 0.1896 | 0.0267 | 0.0657
32 | 5.4822 | 4.1673 | 2.2896 | 2.8677 | 2.0623 | 2.2698

Henceforth, only the BuDDy library is used in the following experiments. Table
II shows the average evaluation time for different error evaluation
algorithms. Both proposed implementations achieve significant speedup compared
to the baseline implementation. On the average, the ones’ implementation
performs better for MAE calculation, but WCE calculation is executed faster
without the absolute value (noabs). We can see an enormous speedup for 20-bit
and 24-bit adders for MAE and WCE, respectively. This is caused by the fact
that the proposed algorithms produce smaller BDD trees that can fit the cache.
Increasing the cache size could move this peek for larger sizes, but we are
also limited by CPU caches and RAM.

TABLE II: An average evaluation time and speedup with BuDDy library

Error | Bit-width | Evaluation time [s] | Speedup
---|---|---|---
| $n/2$ | baseline | ones’ | noabs | ones’ | noabs
MAE | 8 | 0.0001 | 0.0001 | 0.0001 | 2.58$\times$ | 1.91$\times$
12 | 0.0009 | 0.0003 | 0.0004 | 3.11$\times$ | 2.21$\times$
16 | 0.0044 | 0.0013 | 0.0017 | 3.47$\times$ | 2.55$\times$
20 | 0.1818 | 0.0063 | 0.0113 | 28.76$\times$ | 16.06$\times$
24 | 1.4713 | 0.2438 | 0.3537 | 6.03$\times$ | 4.16$\times$
32 | 7.3208 | 3.5416 | 4.1580 | 2.07$\times$ | 1.76$\times$
WCE | 8 | 0.0001 | 0.0001 | 0.0001 | 2.37$\times$ | 2.48$\times$
12 | 0.0007 | 0.0002 | 0.0002 | 2.84$\times$ | 3.19$\times$
16 | 0.0038 | 0.0011 | 0.0009 | 3.33$\times$ | 4.20$\times$
20 | 0.0446 | 0.0055 | 0.0038 | 8.13$\times$ | 11.89$\times$
24 | 0.8281 | 0.1044 | 0.0267 | 7.93$\times$ | 31.04$\times$
32 | 5.4822 | 2.2896 | 2.0623 | 2.39$\times$ | 2.66$\times$

We separately analyzed the impact of signed and unsigned versions of adders.
The signed adders need the subtractor in the characteristic function to be
extended by one bit. This extension slows down the error calculation by 3 -
17% for the proposed algorithms.

###  IV-C Error characterisation of 16-bit adders

We analyzed the behavior of the proposed error calculation algorithms in the
design of 16-bit approximate adders in greater detail. The average evaluation
time depends on the selected error analysis algorithm, error threshold, and
the seed circuit. Figure 2 shows the average evaluation time for different
error thresholds. The slowest evaluations are in the middle part of thresholds
regardless of the evaluation algorithm. It is caused by the following: (i) For
small thresholds, the BDDs representing $f^{\prime}$s are not much different
from the golden circuits $f$.(ii) For large thresholds, BDDs representing
$f^{\prime}$s are simplified (because of the approximation), and their sizes
are reduced. We can see the proposed algorithms achieved significantly faster
evaluations than the baseline.

Figure 2: Effect of the threshold value $\tau$ on the average evaluation time
in CGP-based approximations.

One of the inputs of the approximation algorithm is the seed circuit. This
circuit acts as a parent while all candidate solutions are derived using a
chain of mutations. We use this circuit as a golden circuit $r$ in the
characteristic function $\varepsilon=f-f^{\prime}$. Interestingly, the speed
is not related to the size of the circuit (CLA:171, CSkA: 129, and RCA: 77
nodes, signed versions have two additional nodes). Although the RCA is the
smallest one (and produces more approximated circuits), the evaluation speed
is lower.

Figure 3: Effect of selected seed and golden model implementation for the
average evaluation speed

We analyzed the error-metric evaluation for all resulting approximate
implementations of 16-bit adders using considered BDD-based algorithms. Figure
4 illustrates the execution time and the total number of created BDD nodes for
three main parts of the error evaluation procedure. The part named loading
represents transforming the netlist of functions $f$ and $f^{\prime}$ into
BDDs. The second part, called subtracting, consists of the ripple-carry
subtractor creation. The last part, called calculating, includes building BDDs
that represent the calculation of the absolute value and the final evaluation.
We can see that the first part is negligible in contrast to the subtracting
and calculating parts. The baseline implementation has an enormous proportion
of the calculating part, but the number of BDD nodes is relatively smaller.
However, the overall evaluation time roughly correlates with the number of BDD
nodes.

Figure 4: Time spent and number of created nodes in three steps of the error
calculation algorithms. Error probability $e_{ep}$ [7] is included for
complexity illustration.

###  IV-D Synthesis and comparison to SoA

The resulting approximate adders are synthesized to obtain hardware parameters
(we focus on energy). Both error metrics are evaluated. Figure 5 shows trade-
offs between $e_{wce}$ and the energy. In addition to the area estimation in
the fitness function (eq. 3), we also used CGP with the area-delay product
(ADP) in the fitness function. However, this setup did not improve the results
in terms of energy. The resulting approximate adders outperform relevant
approximate adders published in the EvoApproxLib library [8]). Moreover, we
designed larger approximate adders, including the signed and unsigned variants
that are not included in the library. These circuits were introduced to the
new version of EvoApproxLib.

Figure 5: Comparison of synthesized circuits designed with CGP with two
fitness functions using proposed error calculations.

##  V Conclusion

We proposed new BDD-based algorithms for the fast error evaluation of
approximate adders and subtractors. Compared with the baseline implementation,
these algorithms reduced the evaluation time 3x times on average. Moreover,
they do not need any assumption about $f^{\prime}$. These algorithms enabled
us to accelerate the approximate circuit design process. Our future work will
be devoted to adapting the principle for different arithmetic error metrics
and the application of the proposed circuits.

Acknowledgement This work has been supported the Czech Science Foundation
grant (GJ20-02328Y).

## References

  * [1] J. Han and M. Orshansky, “Approximate computing: An emerging paradigm for energy-efficient design,” in _2013 18th IEEE European Test Symposium (ETS)_ , 2013, pp. 1–6.
  * [2] H. Jiang, C. Liu, L. Liu, F. Lombardi, and J. Han, “A review, classification, and comparative evaluation of approximate arithmetic circuits,” _J. Emerg. Technol. Comput. Syst._ , vol. 13, no. 4, Aug. 2017.
  * [3] S. Hashemi, H. Tann, and S. Reda, “Blasys: approximate logic synthesis using boolean matrix factorization,” in _DAC’18_. IEEE, 2018.
  * [4] M. Češka, J. Matyaš _et al._ , “Approximating complex arithmetic circuits with formal error guarantees: 32-bit multipliers accomplished,” in _ICCAD’17_ , 2017, pp. 416–423.
  * [5] R. Hrbacek and L. Sekanina, “Towards highly optimized cartesian genetic programming: From sequential via simd and thread to massive parallel implementation,” in _GECCO ’14_ , 2014.
  * [6] O. Keszocze, “Bdd-based error metric analysis, computation and optimization,” _IEEE Access_ , vol. 10, pp. 14 013–14 028, 2022.
  * [7] M. Soeken, D. Große, A. Chandrasekharan, and R. Drechsler, “Bdd minimization for approximate computing,” Jan 2016, pp. 474–479.
  * [8] V. Mrazek, R. Hrbacek _et al._ , “Evoapprox8b: Library of approximate adders and multipliers for circuit design and benchmarking of approximation methods,” in _DATE’17_.
  * [9] T. van Dijk, E. M. Hahn _et al._ , “A comparative study of bdd packages for probabilistic symbolic model checking,” in _Dependable Software Engineering: Theories, Tools, and Applications_ , 2015, pp. 35–51.