# Sizing and Profitability of Energy Storage for Prosumers in Madeira,
Portugal

Md Umar Hashmi1, Jonathan Cavaleiro2, Lucas Pereira3, and Ana Bušić1  1 INRIA
and the Computer Science Dept. of Ecole Normale Supérieure, CNRS, PSL
University, Paris, France  2 ITI, LARSyS, M-ITI Funchal, Madeira  3 ITI,
LARSyS, Técnico Lisboa and prsma.com, Funchal, Portugal

###### Abstract

This paper proposes a framework to select the best-suited battery for co-
optimizing for peak demand shaving, energy arbitrage and increase self-
sufficiency in the context of power network in Madeira, Portugal. Feed-in-
tariff for electricity network in Madeira is zero, which implies consumers
with excess production should locally consume the excess generation rather
than wasting it. Further, the power network operator applies a peak power
contract for consumers which imposes an upper bound on the peak power seen by
the power grid interfaced by energy meter. We investigate the value of storage
in Madeira, using four different types of prosumers, categorized based on the
relationship between their inelastic load and renewable generation. We observe
that the marginal increase in the value of storage deteriorates with increase
in size and ramping capabilities. We propose the use of profit per cycle per
unit of battery capacity and expected payback period as indices for selecting
the best-suited storage parameters to ensure profitability. This mechanism
takes into account the consumption and generation patterns, profit, storage
degradation, and cycle and calendar life of the battery. We also propose the
inclusion of a friction coefficient in the original co-optimization
formulation to increase the value of storage by reducing the operational
cycles and eliminate low returning transactions.

##  I Introduction

Renewable integration will increase opportunities for consumers in power
networks for reducing their local cost of consumption [1]. Energy storage co-
optimization is becoming popular with the possibility of doing more than one
dedicated task without undermining the profit of storageby performing each
task at a time. Authors in [2] show that co-optimizing profit leads to higher
than doing one or few of tasks together.

In our prior work [3] we introduced power network rules in Madeira and show
the profitability of a battery for a local prosumer. In this paper, we explore
the dependencies of inelastic load and renewable generation size on the
storage parameters and its profitability. Energy storage performing dedicated
roles may not be profitable. Authors in [4], [5] show that batteries are not
profitable if only used for energy arbitrage. Authors in [6] observe that the
profit made by storage performing only arbitrage is sensitive to the ratio of
selling and buying price of electricity. It is observed that as this ratio
goes to zero, the value of storage increase for cases where the prosumer has
inelastic consumption. Thus in the context of Madeira energy storage can help
in increasing installed renewable generation as excess generation is not
compensated and in this case, a battery can be used to locally increase self-
sufficiency for the prosumer. It is noteworthy that the co-optimization of
energy storage usage has been extensively researched due to the high cost of
batteries. In Table I we list some of the works in this area. In this paper,
we use energy storage for performing energy arbitrage, increase self-
sufficiency and facilitate peak demand shaving.

Authors in [7] observe that peak demand shaving for discharge period of more
than an hour is not profitable. For Madeira the Peak Power Contracts (PPCs)
are applied for the instantaneous power level in the time-scale of seconds,
thus use of storage for peak shaving is reasonable. Authors in [8] propose
battery cycle life optimization for prolonging the operational life of the
storage. Authors in [9, 10] propose sizing of energy storage in context of a
microgrid using mixed-integer programming. [9] consider microgrid reliability
for sizing and [10] use storage devices for spinning reserves. Authors in [11]
consider storage sizing in the context of wind power applications. In this
paper, we provide a framework for identifying storage profitability battery
for prosumers.

TABLE I: Co-optimization of energy storage Paper | Co-optimizing for
---|---
[12] | PV integration support, peak shaving, frequency regulation
[13], [14, 15] | Arbitrage and frequency regulation
[2, 16] | Peak shaving and frequency regulation
[17] | Arbitrage, congestion relief and curtailment reduction
[18] | Arbitrage with power factor correction.

Li-Ion battery life is measured in cycle and calendar life. In [19] the
operational life of a battery is increased by matching calendar life
degradation with the ageing degradation of the battery. Extending this idea
and taking the depth-of-discharge (DoD) of the battery authors in [20] propose
a way to measure the cycles of operation of the battery. It is highlighted
that the nonlinear relationship between cycle life and DoD, [21, 8],
encourages us to use this methodology to calculate storage returns per cycle.
In this paper, we improve the factor profit per cycles proposed in [20] to
make it independent of storage capacity. This new factor along with expected
payback period of the battery can be used for identifying the expected break-
even profit per cycle, thus by comparing these two scalars we can comment on
the profitability of a battery.

Further, battery prices are falling with more research in this domain, which
will promote increased usage of batteries in power networks. Historically, the
cost of battery fell by 85% from 2010 to 2018, reaching an average price of
$176/kWh. The price of an average Li-Ion battery pack is projected to be
around $94/kWh by 2024 and $62/kWh by 2030 [22].

The key contributions of this paper are:
$\quad\bullet$ Index for measuring the profitability of Li-Ion battery: Taking
into account storage parameters and profit, we propose using profit per cycle
per unit capacity and expected payback period as the factors for selecting
storage parameters ensuring profitability. These factors take into account
battery degradation, profit, cycle and calendar life of the battery. For
calculating operational cycles we use algorithm DoDofVector proposed in [20].
$\quad\bullet$ Numerical evaluation: Based on consumer load and renewable
generation consumer are categorized into four categories. Using these four
categories of prosumers we use the data collected for June 2019 and apply
time-of-use (ToU) rates and Peak Power Contract (PPC) improvement to identify
the marginal value of storage. We observe that a smaller sized and ramping
capability storage is profitable in all four categories.
$\quad\bullet$ Observations: Using data and numerical results we make the
following observations which can be generally of interest:

  * •

The marginal value of storage reduces with increase in size and ramping
capability.

  * •

Under zero-feed-in tariff, a higher average net-load significantly improves
the profit prosumer can make.

This paper is organized as follows. In Section II we introduce the Madeira
data collection initiative under H2020 project SMILE. In Section III we
provide the system description, battery model and we summarize the co-
optimization formulation proposed in [3] and extend this formulation for
controlling cycles of operation for increasing the operational life of the
battery. In Section IV we present an algorithm for identifying the
profitability of a battery. In Section V we present the numerical results.
Section VI concludes the paper.

Figure 1: Location of the four prosumers in Madeira used in this work

##  II Context and Data Collection in Madeira

In the Madeira archipelago, since 2014, prosumers are not allowed to inject
the excess energy to the local grid. This imposition is owing to the isolated
nature of the Madeira electric grid that is very sensitive to variations in
the energy produced by RES. Yet, while this technical restriction helps to
maintain grid stability, it is also leading to a stagnation in the number of
prosumers. For example, as of this writing, there are only 49 solar PV
prosumers registered in Madeira island (an average of about 0.6 kWp installed
capacity), in a universe of 270,000 residents [3, 23]. Inclusion of energy
storage along with over-sizing renewables at consumer end have the potential
to increase renewable installations in the island.

The development of better control strategies for battery energy storage is one
of the goals of the H2020 SMILE, https://www.h2020smile.eu, Project, an
European Union co-funded project. Under the scope of this project, PV
production ($PV$) and power consumption ($Load$) measurements were taken from
14 prosumers in the island [24, 25]. The monitored prosumers are categorized
into four categories, based on their inelastic load and PV generation: (C1) PV
generation slightly more than the inelastic load leading to some waste of
excess generation, (C2) consumer actively managing the load to match the
instantaneous PV generation thus reducing the production wastage, (C3) PV
generation is comparable to the magnitude of inelastic load with significantly
higher average net-load compared to other cases considered and (C4) PV
generation is significantly more than the inelastic load leading to
significant amount of energy wastage. The location of these prosumers are
shown on the map of Madeira in Fig. 1.

For this paper, one prosumer was selected from each category. The PPC,
installed solar PV capacity, and the monthly totals of each prosumer for June
2019 are presented in Table II.

In Table II, $PV_{Loads}$ is the amount of solar PV production that is
consumed directly by the loads, $PV_{Grid}$ is the amount of solar PV
production injected into the grid (hereby considered wasted production since
there is no feed-in tariff), $Grid_{Loads}$ is the amount of power from the
grid that is consumed by the loads, and $Savings$ is the amount of saving due
to the installation of the solar PV (assuming a fixed cost of 0.16 Euro per
kWh).

Fig. 2 shows the relationship between PV and inelastic load for the selected
prosumers. U2, U3, and U12 are domestic prosumers. U8 is a commercial
prosumer, a small family restaurant.

Figure 2: PV and inelastic load for 4 types of prosumers C1, C2, C3 and C4 TABLE II: Indices of load and generation for U2, U3, U8, U12 for June 2019 Case | UPAC | Contracted | Installed | PV | Load | $PV_{Load}$
---|---|---|---|---|---|---
| ID | Power (kVA) | PV (kWp) | (kWh) | (kWh) | (kWh)
C1 | U2 | 6.9 | 1.5 | 180 | 459 | 121
C2 | U3 | 5.75 | 1 | 120 | 360 | 113
C3 | U8 | 20.7 | 3.92 | 610 | 1969 | 531
C4 | U12 | 6.9 | 3 | 305 | 306 | 145
Case | UPAC | $PV_{Grid}$ | $Grid_{Load}$ | Savings | Average | Average
| ID | (kWh) | (kWh) | (Euros) | PV (W) | Load (W)
C1 | U2 | 59.64 | 338 | 19.30 | 251 | 637
C2 | U3 | 6.85 | 247 | 21.19 | 168 | 501
C3 | U8 | 78.53 | 1438 | 85.09 | 848 | 2736
C4 | U12 | 160 | 162 | 26.37 | 424 | 426

##  III System Model and Storage Co-Optimization

In this section, we present the system and battery model and the summarize the
co-optimization formulation developed in [3]. We extend this formulation for
limiting storage cycles of operation using a friction coefficient.

###  III-A System and Battery Model

We consider operation over a total duration $T$, divided into $N$ steps
indexed by $\\{1,...,N\\}$. The duration of each step is denoted as $h$.
Hence, $T=hN$. At time instant $i$, the information available is the end user
consumption $d_{i}$, the renewable generation ${r}_{i}$ and the storage energy
output $s_{i}$. The load without storage is denoted as $z_{i}=d_{i}-r_{i}.$
The load seen by grid is denoted as $L_{i}=d_{i}-r_{i}+s_{i}.$

Battery Model: The efficiency of charging and discharging is denoted by
$\eta_{ch},\eta_{dis}\in(0,1]$, respectively. The change in energy level of
the battery is denoted as $x_{i}$=$h\delta_{i}$, where $\delta_{i}$ denotes
storage ramp rate at time instant $i$, such that
$\delta_{i}\in[\delta_{\min},\delta_{\max}],\forall i$. The energy output of
storage in the $i^{\text{th}}$ instant is given by
$s_{i}=\frac{[x_{i}]^{+}}{\eta_{ch}}-\eta_{dis}[x_{i}]^{-}$, where
$[x]^{+}$=$\max(0,x)$ and $[x]^{-}$=$-\min(0,x)$. The ramping constraint
induce limits on $s_{i}$ given by

$s_{i}\in[\delta_{\min}h\eta_{dis},\delta_{\max}h/\eta_{ch}],\quad\forall
i.\vspace{-3pt}$ (1)

The energy stored in the battery is denoted as $b_{i}$, defined as
$b_{i}=b_{i-1}+x_{i}$. Battery capacity constraint is given as

$b_{i}\in[b_{\min},b_{\max}],\quad\forall i.\vspace{-3pt}$ (2)

where $b_{\min}$ and $b_{\max}$ are minimum and maximum permissible battery
charge levels respectively. We use xC-yC notation to represent the
relationship between ramp rate and battery capacity. xC-yC implies battery
takes 1/x hours to charge and 1/y hours to discharge completely.

###  III-B Cost of the battery with inverter

The cost of inverter depends on the rated apparent power output capability.
Based on cost of 6 kW SMA Sunny Boy 2.0, the cost per kW of inverter is 100
euros/kWh [26]. The cost of Li-Ion battery is assumed to have two components:
(a) capacity cost and (b) ramping capability cost, similar to [27]. The cost
of battery (with inverter) for per kWh in euros is given as

$\text{Battery Cost}=300+{0.25}~{}{\max(x,y)}100~{}~{}\text{per
kWh},\vspace{-4pt}$ (3)

where $x,y$ denotes the charging and discharging rates as described in the
battery model xC-yC.

###  III-C Co-optimization formulation

The power network in Madeira impose time-of-use (ToU) electricity prices for
consumption, applies peak power restriction and imposes zero feed-in-tariff.
The ToU price considered is shown in Fig. 3. The PPC contracts have 8 levels:
3.45, 4.6, 5.75, 6.9, 10.35, 13.8, 17.25 and 20.7 kVA for LV prosumers with
per day cost as 0.1643, 0.2132, 0.2590, 0.3080, 0.4532, 0.5981, 0.7436 and
0.8892 respectively. The detailed consumer contracts in Madeira are summarized
in [3]. The co-optimization formulation is developed in [3] and given as

$\displaystyle(P_{opt})~{}~{}~{}$
$\displaystyle\mathmakebox[\widthof{$\underset{\displaystyle
s_{i}}{\mathrm{subject~{}to}}$}][l]{\underset{\displaystyle
s_{i}}{\mathrm{minimize}}}\quad\sum_{i=1}^{N}{p}_{\text{elec}}(i)\theta_{i}(s_{i})h$
(4a)
$\displaystyle\mathmakebox[\widthof{$\underset{\displaystyle\phantom{s_{i}}}{\mathrm{subject~{}to}}$}][c]{{\mathrm{subject~{}to}}}$
Ramping constraint, $\displaystyle Eq.~{}\ref{constraintramp}$ , (4b) Capacity
constraint, $\displaystyle Eq.~{}\ref{constraintcapacity}\vspace{-4pt},$ (4c)
$\displaystyle\text{Self-sufficiency,}~{}~{}\theta_{i}(s_{i})$
$\displaystyle\geq 0\vspace{-4pt},$ (4d)
$\displaystyle\text{Arbitrage,}~{}~{}\theta_{i}(s_{i})$
$\displaystyle\geq[z_{i}+s_{i}]\vspace{-4pt},$ (4e) $\displaystyle\text{Peak
shaving,}~{}~{}[z_{i}+s_{i}]/h$ $\displaystyle\leq
P_{\max}^{set}\vspace{-4pt}$ (4f)

where $\theta_{i}(s_{i})=\max(0,z_{i}+s_{i})$. The peak power threshold,
$P_{\max}^{set}$, is selected close to the power level
($P_{\max}+\delta_{\min}$), subject to
$P_{\max}^{set}\geq(P_{\max}+\delta_{\min})$. $P_{\max}^{set}$ is selected by
the electricity consumer as a PPC contract with the utility in Madeira. Note
that this formulation prioritizes self-consumption over arbitrage.

###  III-D Co-optimization with control of cycles

Note that the formulations discussed previously do not consider battery life
that is affected by charge-discharge cycles. Battery manufacturers measure the
life of a battery using two indices: cycle life and calendar life. Cycle life
denotes the number of cycles a battery can operate at a certain depth-of-
discharge before reaching its end-of-life or EoL (EoL is reached when battery
capacity reduces to 80% of its initial rated capacity in Wh). Similarly,
calendar life denotes the maximum probable age that the battery can be
operational before reaching EoL. Following our prior work [20], we define a
friction function for the active power to model the degradation due to cycles
of operation as
$P_{\text{fric}}^{i}=\frac{[P_{B}^{i}]^{+}}{\eta_{\text{fric}}}-{[P_{B}^{i}]^{-}\eta_{\text{fric}}}.$
In the original formulation ($P_{opt}$) the constraint Eq. 4e is modified as
$\theta_{i}{\geq[z_{i}+P_{\text{fric}}^{i}]}$. The friction coefficient takes
a value from 1 to 0. $\eta_{\text{fric}}$ needs to be tuned so as the
operational life is increased by matching calendar and cycle degradation [20].
If the battery is not over operating then $\eta_{\text{fric}}$ is set to 1.
For cases where the battery is over-performing, the low returning transactions
is eliminated by decreasing value of $\eta_{\text{fric}}$.

##  IV Energy storage profitability

We propose a mechanism for ensuring storage profitability considering battery
cycle and calendar life, thus in effect considering battery degradation.
Algorithm BatteryProfitability provides the steps to identify storage
profitability. For more than one battery is profitable, in such a case it will
depend on the prosumer on whether they prioritize payback period or the
returns per cycle.

Inputs:
$\eta_{\text{ch}},\eta_{\text{dis}},\delta_{\max},\delta_{\min},b_{\max},b_{\min}$,
$b_{0}$, $h,N,T,i=0$

1:Calculate total storage profit, $G_{T}$, by solving $P_{opt}$ over the
instants, $N_{total}$, based on load, price and renewable generation,

2:Calculate equivalent 100% DoD cycles denoted as $N_{cyc}^{100}$ using
DoDofVector proposed in [20],

3:Calculate $G_{cyc}=G_{T}/(N_{cyc}^{100}~{}~{}b_{\text{rated}})$,

4:Calculate $P_{cyc}=G_{cyc}-C_{cyc}$, where $C_{cyc}$ is the per cycle (100%)
cost of the battery,

5:Calculate the Expected Payback Period (ExPB) in years
$=(B_{cost}N_{total})/(G_{T}N_{year})$, where $B_{cost}$ denotes the battery
cost and $N_{year}$ denotes number of samples in a year,

6:Battery is profitable if $P_{cyc}>0$ and ExPB $<$ Calendar life of the
battery.

Algorithm 1 BatteryProfitability

##  V Numerical Results

For the numerical simulations we use the battery parameters listed in Table
III. The characteristics of the four prosumers are described in Figure 2 and
Table II. Simulations are performed for the month of June 2019.

The performance indices used for evaluation are:
$\quad\bullet$ Arbitrage and self-sufficiency gains ($G_{arb}$);
$\quad\bullet$ Peak shaving gains ($G_{\text{PD}}$): difference between
nominal PPC and the new PPC contract after adding storage;
$\quad\bullet$ Total gains ($G_{\text{T}}$): is the sum of $G_{arb}$ and
$G_{\text{PD}}$,
$\quad\bullet$ Gains per cycle ($G_{cyc}$): In prior work [20] we develop a
mechanism to measure the number of cycles of operation based on DoD of energy
storage operational cycles.
$\quad\bullet$ Profit per cycle ($P_{cyc}$): is the profit battery owner makes
per cycle compared to the per cycle cost of the battery ($C_{cyc}$);
$P_{cyc}=G_{cyc}-C_{cyc}$;
$\quad\bullet$ Expected payback period (ExPB): is the linear extrapolation of
the payback period compared to $G_{\text{T}}$. ExPB $=C_{bat}/G_{\text{T}}$
$\quad\bullet$ Self-sufficiency (SS): calculated using the total energy
consumed, PV generation and storage output,
$\quad\bullet$ Wasted energy: The surplus production is wasted energy is
measured in kWh.

We consider the battery cycle life equals 4000 cycles at 100% DoD. Using this
description the euros per cycle per rated battery capacity for different
ramping batteries are listed in Table IV. Considering the calendar life equals
7 years, the battery should perform $\approx$47.6 cycles per month in order to
last 7 years and make more than the values listen in Table IV to be
profitable.

TABLE III: Battery Parameters $b_{\min}$, $b_{\max}$, $b_{0}$ |  10%, 100%, 50% of $b_{\text{rated}}$
---|---
$b_{\text{rated}}$ | 1, 2, 5 kWh
$\eta_{\text{ch}}=\eta_{\text{dis}}$ | 0.95
$\delta_{\max}=-\delta_{\min}$ |  0.25 $b_{\text{rated}}$ W for 0.25C-0.25C,
|  $b_{\text{rated}}$ W for 1C-1C, 2$b_{\text{rated}}$ W for 2C-2C
Figure 3: Time-of-use (ToU) electricity prices TABLE IV: Storage profitability with different ramping per kWh Battery | Inverter | Battery | Battery Cost |  euros/cycle/$b_{\text{rated}}$
---|---|---|---|---
Model | Cost/kWh | Cost/kWh |  ($C_{\text{bat}}$/kWh) |  ($C_{\text{cyc}}$)
0.25C-0.25C | 25 | 400 | 425 | 0.1062
1C-1C | 100 | 600 | 700 | 0.1750
2C-2C | 200 | 700 | 900 | 0.2250

###  V-A Co-Optimization and storage profitability

The co-optimization results for each prosumer are presented in Tables V, VI,
VII and VIII. U2, U3, U8 and U12 belong to categories C1, C2, C3 and C4,
respectively.

TABLE V: (C1) U2: PV generation slightly more than inelastic load Case | $G_{\text{PD}}$ | $G_{T}$ | $P_{\text{cyc}}$ | Cycles | ExPB | SS | Waste
---|---|---|---|---|---|---|---
Euro | Euro |  |  | (years) | (%) | (kWh)
Load + PV | - | - | - | - | - | 26.82 | 57.4
1 kWh Battery
0.25C-0.25C | 0 | 10.13 | 0.1675 | 37.01 | 3.50 | 31.91 | 30.12
1C-1C | 1.39 | 13.79 | 0.0867 | 52.70 | 4.23 | 33.56 | 18.59
2C-2C | 2.85 | 15.48 | 0.0536 | 55.56 | 4.84 | 33.69 | 15.39
2 kWh Battery
0.25C-0.25C | 1.39 | 15.83 | 0.0798 | 42.53 | 4.47 | 34.96 | 12.97
1C-1C | 2.85 | 19.26 | 0.0355 | 45.75 | 6.06 | 35.85 | 5.15
2C-2C | 2.85 | 19.33 | -0.016 | 46.24 | 7.76 | 35.88 | 3.96
5 kWh Battery
0.25C-0.25C | 1.39 | 22.46 | 0.0288 | 33.27 | 7.88 | 36.38 | 0.39
1C-1C | 2.85 | 24.67 | -0.0295 | 33.91 | 11.82 | 36.29 | 0.19
2C-2C | 2.85 | 24.67 | -0.0795 | 33.91 | 15.20 | 36.29 | 0.18

The best-suited battery is selected based on: (P1) profit per cycle per unit
capacity, (P2) cycles of operation and (P3) expected payback period.

The best-suited battery for U2, U3, U8 and U12 are marked in bold in Tables V,
VI, VII, and VIII respectively. For battery installation to make sense the
value of $P_{\text{cyc}}$ should be positive and ExPB should be lower than 7
years (i.e. the calendar life of battery). For prosumer U2 5 batteries satisfy
the feasibility criteria. However, the best-suited battery will vary with
preference. For instance if payback period is priority the U2 should select 1
kWh 0.25C-0.25C battery. Note that the marginal value of storage decreases
with increase in ramping capability and charge capacity. Thus if $P_{cyc}$ is
used to select the battery then slowest ramping battery with smallest capacity
will be selected.

The self-sufficiency increases with increase in battery capacity and ramping
capability thus the wasted excess generation decreases.

TABLE VI: (C2) U3: Active load management to reduce excess generation Case | $G_{\text{PD}}$ | $G_{T}$ | $P_{\text{cyc}}$ | Cycles | ExPB | SS | Waste
---|---|---|---|---|---|---|---
Euro | Euro |  |  | (years) | (%) | (kWh)
Load + PV | - | - | - | - | - | 32.71 | 2.72
1 kWh Battery
0.25C-0.25C | 0 | 7.57 | 0.1715 | 27.26 | 4.68 | 32.73 | 0.01
1C-1C | 0 | 8.13 | 0.0197 | 41.76 | 7.18 | 32.53 | 0
2C-2C | 0 | 8.14 | -0.0318 | 42.13 | 9.21 | 32.52 | 0
2 kWh Battery
0.25C-0.25C | 0 | 9.74 | 0.0791 | 26.28 | 7.27 | 32.09 | 0
1C-1C | 0 | 10.07 | 0.0065 | 27.74 | 11.59 | 32.04 | 0
2C-2C | 0 | 10.07 | -0.0436 | 27.76 | 14.90 | 32.04 | 0
5 kWh Battery
0.25C-0.25C | 0 | 13.92 | 0.0189 | 22.25 | 12.72 | 30.66 | 0
1C-1C | 0 | 14.02 | -0.05 | 22.43 | 20.80 | 30.64 | 0
2C-2C | 0 | 14.02 | -0.1 | 22.43 | 26.75 | 30.64 | 0
TABLE VII: (C3) U8: Comparable generation and load with average load higher then C1,C2 and C4 Case | $G_{\text{PD}}$ | $G_{T}$ | $P_{\text{cyc}}$ | Cycles | ExPB | SS | Waste
---|---|---|---|---|---|---|---
Euro | Euro |  |  | (years) | (%) | (kWh)
Load +PV | - | - | - | - | - | 28.02 | 58.14
1 kWh Battery
0.25C-0.25C | 0 | 35.62 | 0.8589 | 36.91 | 0.99 | 28.71 | 40.68
1C-1C | 0 | 39.42 | 0.4543 | 62.64 | 1.48 | 29.42 | 22.69
2C-2C | 0 | 40.02 | 0.3765 | 66.53 | 1.87 | 29.57 | 17.88
2 kWh Battery
0.25C-0.25C | 0 | 40.04 | 0.2941 | 50.01 | 1.77 | 29.21 | 27.27
1C-1C | 0 | 44.36 | 0.1842 | 61.75 | 2.63 | 29.79 | 10.73
2C-2C | 4.31 | 48.70 | 0.1774 | 60.51 | 3.08 | 29.79 | 9.09
5 kWh Battery
0.25C-0.25C | 0 | 50.44 | 0.1117 | 46.30 | 3.51 | 29.90 | 4.80
1C-1C | 4.31 | 58.64 | 0.1106 | 41.06 | 4.97 | 29.80 | 1.54
2C-2C | 4.31 | 58.65 | 0.0598 | 41.18 | 6.39 | 29.80 | 1.36
TABLE VIII: (C4) U12: PV generation significantly more than inelastic load Case | $G_{\text{PD}}$ | $G_{T}$ | $P_{\text{cyc}}$ | Cycles | ExPB | SS | Waste
---|---|---|---|---|---|---|---
Euro | Euro |  |  | (years) | (%) | (kWh)
Load + PV | - | - | - | - | - | 47.84 | 158.1
1 kWh Battery
0.25C-0.25C | 0 | 8.57 | 0.1922 | 28.69 | 4.13 | 56.91 | 126.13
1C-1C | 0 | 9.49 | 0.1107 | 33.22 | 6.15 | 57.72 | 115.66
2C-2C | 0 | 9.56 | 0.0739 | 35.55 | 7.85 | 57.84 | 106.63
2 kWh Battery
0.25C-0.25C | 0 | 13.41 | 0.0566 | 41.19 | 5.28 | 65.00 | 97.50
1C-1C | 0 | 13.84 | 0.0214 | 35.23 | 8.43 | 65.77 | 81.94
2C-2C | 0 | 13.86 | -0.0116 | 32.47 | 10.82 | 65.80 | 70.04
5 kWh Battery
0.25C-0.25C | 0 | 18.28 | -0.007 | 36.85 | 9.69 | 74.90 | 53.58
1C-1C | 0 | 18.71 | -0.0758 | 37.72 | 15.59 | 75.66 | 31.16
2C-2C | 0 | 18.70 | -0.1257 | 37.66 | 20.05 | 75.65 | 27.41

###  V-B Friction Coefficient

The friction coefficient can help in reducing the cycles of operation for
cases where the battery is performing more number of cycles compared to the
value which matches the calendar life degradation. For equalizing cycle and
calendar life degradation of the battery, it should perform $\approx 47.6$
cycles in 1 month (considering 4000 as cycle life at 100% DoD and 7 years as
calendar life). From Tables V, VI, VII, and VIII it is clear that inclusion of
friction coefficient for limiting cycles of operation is only relevant for 1
and 2 kWh batteries for U8 and 1 kWh battery for U2, as for these case the
battery is operating more number of cycles than the optimal value of 47.6
cycles in a month (marked in red). Table IX compares the tuned friction
coefficients for batteries which performed more cycles than expected. Note
that friction coefficient can only reduce cycles of operation, therefore it is
only applicable when the battery is over-performing. Inclusion of
$\eta_{\text{fric}}$ for over-performing batteries increases $P_{cyc}$,
however, also increases ExPB.

TABLE IX: Friction Coefficient. Battery | $\eta_{\text{fric}}$ | Profit | $P_{cyc}$ | SS | Waste | Cycles | ExPB
---|---|---|---|---|---|---|---
Model |  | euros |  | (%) | (kWh) |  | yrs.
For prosumer U2
1kWh,1C-1C | 0.796 | 12.85 | 0.0962 | 32.45 | 25.70 | 47.38 | 4.54
1kWh,2C-2C | 0.797 | 14.45 | 0.0796 | 32.53 | 24.99 | 47.44 | 5.19
For prosumer U8
1kWh,1C-1C | 0.796 | 38.17 | 0.6805 | 29.33 | 26.82 | 44.62 | 1.53
1kWh,2C-2C | 0.796 | 38.50 | 0.5829 | 29.37 | 25.16 | 47.65 | 1.95
2kWh,1C-1C | 0.9398 | 43.98 | 0.3143 | 29.67 | 13.71 | 52.29 | 1.61
2kWh,1C-1C | 0.9397 | 43.47 | 0.3286 | 29.73 | 14.34 | 43.17 | 2.68
2kWh,2C-2C | 0.9397 | 47.85 | 0.3228 | 29.76 | 12.91 | 43.68 | 3.13

##  VI Conclusion

The profitability of investment in storage is a crucial factor for deciding
future investment in batteries. In this paper, we co-optimize storage in the
context of power network norms in Madeira. The batteries are used for
performing energy arbitrage, increasing self-sufficiency and peak demand
reduction.

The proposed formulation prioritizes self-sufficiency over energy arbitrage,
thus minimizing the excess production at the prosumer end. Four types of
prosumers are selected based on the different relationship between inelastic
load and renewable generation to identify the value of storage.

It is observed that the marginal value of installing battery decreases with
storage size and ramping capability. We observe that value of storage for an
average net-load comparable to storage ramping rate leads to profits several
folds higher than for otherwise. Faster ramping batteries perform much more
number of cycles which deteriorates the profit made per 100% DoD cycles per
unit of storage capacity making such batteries financially unviable.

We propose the inclusion of friction coefficient which reduces the cycles of
operation by eliminating storage operations for low returning transactions
thus increasing the profit per cycle per unit of storage capacity and makes
such batteries more profitable, however, it increases the payback period.

## Acknowledgment

Funding from grants: ANR under ANR-16-CE05-0008, EU H2020 under GA 731249, and
FCT under UID/EEA/50009/2019 are gratefully acknowledged.

## References

  * [1] M. U. Hashmi, D. Muthirayan, and A. Bušić, “Effect of real-time electricity pricing on ancillary service requirements,” in _9th e-Energy_. ACM, 2018, pp. 550–555.
  * [2] Y. Shi, B. Xu, D. Wang, and B. Zhang, “Using battery storage for peak shaving and frequency regulation: Joint optimization for superlinear gains,” _IEEE Transactions on Power Systems_ , vol. 33, no. 3, pp. 2882–2894, 2018\.
  * [3] M. U. Hashmi, L. Pereira, and A. Bušić, “Energy storage in madeira, portugal: Co-optimizing for arbitrage, self-sufficiency, peak shaving and energy backup,” _arXiv preprint arXiv:1904.00463_ , 2019.
  * [4] D. Kiedanski, M. U. Hashmi, A. Busic, and D. Kofman, “Sensitivity to forecast errors in energy storage arbitrage for residential consumers,” in _SmartGridComm_ , Beijing, P.R. China, Oct. 2019.
  * [5] M. U. Hashmi, A. Mukhopadhyay, A. Bušić, and J. Elias, “Optimal control of storage under time varying electricity prices,” in _SmartGridComm_. IEEE, 2017, pp. 134–140.
  * [6] M. U. Hashmi, A. Mukhopadhyay, A. Busic, J. Elias, and D. Kiedanski, “Optimal storage arbitrage under net metering using linear programming,” in _SmartGridComm_ , Beijing, P.R. China, Oct. 2019.
  * [7] A. Oudalov, R. Cherkaoui, and A. Beguin, “Sizing and optimal operation of battery energy storage system for peak shaving application,” in _Power Tech, 2007 IEEE Lausanne_. IEEE, 2007, pp. 621–625.
  * [8] J. Shen, S. Dusmez, and A. Khaligh, “Optimization of sizing and battery cycle life in battery/ultracapacitor hybrid energy storage systems for electric vehicle applications,” _IEEE Trans. on industrial informatics_ , vol. 10, no. 4, pp. 2112–2121, 2014.
  * [9] S. Bahramirad, W. Reder, and A. Khodaei, “Reliability-constrained optimal sizing of energy storage system in a microgrid,” _IEEE Trans. on Smart Grid_ , vol. 3, no. 4, pp. 2056–2062, 2012.
  * [10] S. Chen, H. B. Gooi, and M. Wang, “Sizing of energy storage for microgrids,” _IEEE Trans. on Smart Grid_ , vol. 3, no. 1, pp. 142–151, 2011.
  * [11] T. K. Brekken, A. Yokochi, A. Von Jouanne, Z. Z. Yen, H. M. Hapke, and D. A. Halamay, “Optimal energy storage sizing and control for wind power applications,” _IEEE Transactions on Sustainable Energy_ , vol. 2, no. 1, pp. 69–77, 2010.
  * [12] O. Mégel, J. L. Mathieu, and G. Andersson, “Scheduling distributed energy storage units to provide multiple services,” in _PSCC_. IEEE, 2014.
  * [13] R. Walawalkar, J. Apt, and R. Mancini, “Economics of electric energy storage for energy arbitrage and regulation in new york,” _Energy Policy_ , vol. 35, no. 4, pp. 2558–2568, 2007.
  * [14] K. Anderson and A. El Gamal, “Co-optimizing the value of storage in energy and regulation service markets,” _Energy Systems_ , vol. 8, no. 2, pp. 369–387, 2017.
  * [15] B. Cheng and W. Powell, “Co-optimizing battery storage for the frequency regulation and energy arbitrage using multi-scale dynamic programming,” _IEEE Trans. on Smart Grid_ , 2016.
  * [16] C. D. White and K. M. Zhang, “Using vehicle-to-grid technology for frequency regulation and peak-load reduction,” _Journal of Power Sources_ , vol. 196, no. 8, pp. 3972–3980, 2011.
  * [17] Y. Dvorkin, R. Fernandez-Blanco, D. S. Kirschen, H. Pandžić, J.-P. Watson, and C. A. Silva-Monroy, “Ensuring profitability of energy storage,” _IEEE Transactions on Power Systems_ , vol. 32, no. 1, pp. 611–623, 2016\.
  * [18] M. U. Hashmi, D. Deka, A. Busic, L. Pereira, and S. Backhaus, “Arbitrage with power factor correction using energy storage,” _arXiv preprint arXiv:1903.06132_ , 2019.
  * [19] M. U. Hashmi and A. Busic, “Limiting energy storage cycles of operation,” in _GreenTech_. IEEE, 2018, pp. 71–74.
  * [20] M. U. Hashmi, W. Labidi, A. Bušić, S.-E. Elayoubi, and T. Chahed, “Long-term revenue estimation for battery performing arbitrage and ancillary services,” in _SmartGridComm_. IEEE, 2018.
  * [21] R. D. Mackley, D. M. Anderson, J. N. Thomle, and C. E. Strickland, “Technical and economic assessment of solar photovoltaic for groundwater extraction on the hanford site,” PNNL, Richland, WA (United States), Tech. Rep., 2015.
  * [22] “A behind the scenes take on lithium-ion battery prices,” BloombergNEF article, 2019. [Online]. Available: https://tinyurl.com/y3xbu8xt
  * [23] L. Pereira and J. Cavaleiro, “On the Value Proposition of Battery Energy Storage in Self-Consumption Only Scenarios: A Case-Study in Madeira Island,” in _IECON 2019 - 45th Annual Conference of the IEEE Industrial Electronics Society_ , Lisbon, Portugal, Oct. 2019.
  * [24] Prsma, M-ITI, EEM, and ACIF-CCIM, “Data Collection, Modelling, Simulation and Decision,” European Commission, Funchal, Portugal, Technical report 4.3, Jun. 2018.
  * [25] Prsma, EEM, M-ITI, ACIF-CCIM, LIBAL, and DTU, “Detailed Plan of Action for the DSM Demonstrator,” European Commission, Funchal, Portugal, Technical report 4.6, Jul. 2018.
  * [26] “Sma sunny boy 2.0 cost,” 2019. [Online]. Available: https://tinyurl.com/yxc8td25
  * [27] C. Z. Todd Aquino and C. Koss, “Energy storage technology assessment (prepared for public service company of new mexico); hdr report no. 10060535-0zp-c1001,” 2017. [Online]. Available: https://tinyurl.com/y2aeugef


Counting Clean Words According to the Number of Their Clean Neighbors

Shalosh B. EKHAD and Doron ZEILBERGER

In fond memory of Marko Petkov${\breve{s}}$ek (1955-2023), a great summer and
enumerator

Preface

Our good friend and collaborate, Marko Petkov${\breve{s}}$ek ([PWZ]), passed
away on March 23, 2023, and we already wrote a eulogy [Z], and donated to the
Online Encyclopedia of Integer Sequences in his memory (See
https://oeisf.org/donate and search for Petkovsek). However we believe that we
can do more than that to commemorate Marko. We looked through his list of
publications, and found the delightful article [KMP] by Marko, joint with
Sandi Klav${\breve{z}}$ar and Michel Mollard, and realized that the beautiful
methodology that they used to solve one very specific enumeration problem is
applicable to a wide class of enumeration problems of the same flavor. More
important, since Marko was such an authority in symbolic computation, we
decided to implement the method, and wrote a Maple package

https://sites.math.rutgers.edu/~zeilberg/tokhniot/Marko.txt ,

that can very fast answer these kind of questions. In particular as we will
soon see, Theorem 1.1 of [KMP] can be gotten (in its equivalent form in terms
of generating functions stated as $f(x,y)$ on top of p. 1321) by typing

WtEs( $\\{0$,1 $\\}$,$\\{$[1,1]$\\}$,y,x,3); .

Our Maple package, Marko.txt, gives, in $0.057$ seconds, the answer

$-{x^{2}y^{2}-x^{2}y-xy-1\over x^{3}y^{2}-x^{3}y-x^{2}y-xy+1}\quad.$

The Problem Treated so Nicely by Klav${\bf{\breve{z}}}$ar, Mollard, and
Petkov${\breve{s}}$ek

There are $2^{n}$ vertices in the $n$-dimensional unit cube $\\{0,1\\}^{n}$
and every such vertex has exactly $n$ neighbors (i.e. vertices with Hamming
distance $1$ from it). The Fibonacci lattice consists of those vertices whose
$01$ vector avoids two consecutive $1$s, in other words of words in the
alphabet $\\{0,1\\}$ avoiding as a consecutive subword the two-letter word
$11$. Such words are called Fibonacci words, and there are, not surprisingly,
$F_{n+2}$ of them (why?).

Each such word has $n$ neighbors, but some of them are not Fibonacci words.
The question answered so elegantly in [KMP] was:

For any given $n$ and $k$, How many Fibonacci words of length $n$ are there
that have exactly $k$ Fibonacci neighbors? Calling this number $f_{n,k}$,
[KMP] derived an explicit expression for it, that is equivalent to the
generating function (that they also derived)

$f(x,y)\,=\,\sum_{n,k\geq
0}\,f_{n,k}\,x^{n}\,y^{k}\,=\,-{x^{2}y^{2}-x^{2}y-xy-1\over
x^{3}y^{2}-x^{3}y-x^{2}y-xy+1}\quad.$

They also considered the analogous problem for Lucas words that consists of
Fibonacci words where the first and last letter can’t both be $1$. This
problem is also amenable to far-reaching generalization, but will not be
handled here.

The general Problem

Input:

$\bullet$ A finite alphabet $A$ (In the [KMP] case $A=\\{0,1\\}$).

$\bullet$ A finite set of words $M$, (of the same length) in the alphabet $A$.
(In the [KMP] case $M$ is the singleton set $\\{11\\}$).

Definition: A word in the alphabet $A$ is called clean if it does not have, as
consecutive substring, any of the members of $M$.

In other words writing $w=w_{1}\dots w_{n}$, a word is dirty if there exists
an $i$ such that $w_{i}w_{i+1}\dots w_{i+k-1}\in M$. For example if
$A=\\{1,2,3\\}$ and $M=\\{123,213\\}$, then $12212312$ is dirty while
$111222333$ is clean.

To get the set of clean words of length n in the alphabet A and set of
‘mistakes’ M, type, in Marko.txt,

CleanWords(A,M,n); .

For example, to get the Fibonacci words of length $3$ type:

CleanWords($\\{$ 0,1 $\\}$,$\\{$ [1,1] $\\}$ , 3);, getting:

$\\{$[0, 0, 0], [0, 0, 1], [0, 1, 0], [1, 0, 0], [1, 0, 1]$\\}$ .

The problem of the straight enumeration of clean words is handled very
efficiently via the Goulden-Jackson cluster algorithm [NZ], but it is not
suitable for the present problem of weighted enumeration.

Definition: Two words of the same length in the alphabet $A$ are neighbors if
their Hamming distance is $1$, in other words, $u=u_{1}\dots u_{n}$ and
$v=v_{1}\dots v_{n}$ are neighbors if there exists a location $r$ such
$u_{i}=v_{i}$ if $i\neq r$ and $u_{r}\neq v_{r}$.

For example if $A=\\{1,2,3\\}$, the set of neighbors of $111$ is

$\\{211,311,121,131,112,113\\}\quad.$

Obviously every word of length $n$ in the alphabet $A$ has $n\cdot(|A|-1)$
neighbors.

However, if $w$ is a clean word, some of its neighbors may be dirty, so if
there is one typo, it can become dirty, and that would be embarrassing (Oops,
embarrassing is already dirty). While the word, duckling is clean, not all its
neighbors are clean.

To see the number of clean neighbors of a word w in the alphabet A and set of
mistakes M, type

NCN(w,A,M);

Output: Having fixed the (finite) alphabet $A$, and the finite set of
forbidden substrings $M$ (all of the same length), let $f_{n,k}$ be the number
of clean words in the alphabet $A$ of length $n$ having $k$ clean neighbors.
Compute the bi-variate generating function

$f(x,y):=\sum_{n,k\geq 0}f_{n,k}x^{n}\,y^{k}\quad.$

It would follow from the algorithm (inspired by the methodology of [KMP], but
vastly generalized) that this is always a rational function of $x$ and $y$.

This is implemented in procedure

WtEs(A,M,y,x,MaxK),

where MaxK is a ‘maximum complexity parameter’. See the beginning of this
article for the case treated in [KMP]. For a more complicated example, where a
word is clean if it avoids the substrings $000$ and $111$, type

WtEs( $\\{$ 0,1 $\\}$, $\\{$ [1,1,1],[0,0,0] $\\}$,y,x,5);

getting, immediately:

${2x^{5}y^{4}-4x^{5}y^{3}+2x^{5}y^{2}-2x^{4}y^{3}+4x^{4}y^{2}-2x^{4}y-y^{2}x^{3}+2x^{3}y-4x^{2}y^{2}-x^{3}+2x^{2}y+x^{2}-2xy+x-1\over
y^{2}x^{3}-x^{3}+x^{2}+x-1}\,.$

If you want to keep track of the individual letters, rather than just the
length, use the more general procedure

WtEg(A,M,x,y,t,MaxK).

Reverse-Engineering the beautiful Klav${\bf{\breve{z}}}$ar-Mollard-
Petkov${\bf{\breve{s}}}$ek Proof and Vastly Generalizing It

In fact, the authors of [KMP] proved their results in two ways, and only the
second way used generatingfunctionology. Even that part argued directly in
terms of the (double) sequence $f_{n,k}$ itself, and only at the end of the
day, took the (bi-variate) generating function.

A more efficient, and streamlined, approach is to forgo the actual bi-sequence
and operate directly with weight-enumerators. Let ${\cal C}(A,M)$ be the
(‘infinite’) set of words in the alphabet $A$, avoiding, as consecutive
substrings, the members of $M$, and for each word $w$ in ${\cal C}(A,M)$,
define the weight, $Weight(w)$ by

$Weight(w)=x^{length(w)}\,y^{NCN(w)}\quad.$

For example, for the original case of $A=\\{0,1\\}$ and $M=\\{11\\}$,

$Weight(10101)\,=\,x^{5}\,y^{3}\quad.$

We are interested in the weight-enumerator

$f(x,y):=Weight({\cal C}(A,M))=\sum_{w\in{\cal C}(A,M)}Weight(w)\quad.$

Once you have it, and you are interested in a specific $f_{n,k}$, all you need
is to take a Taylor expansion about $(0,0)$ and extract the coefficient of
$x^{n}y^{k}$.

Let ${\cal C}(A,M)^{(i)}$ be the subset of ${\cal C}(A,M)$ of words of length
$i$, and pick a positive integer $k$. For any word $v\in{\cal C}(A,M)^{(k)}$,
let ${\cal C}_{v}(A,M)$ be the set of words in ${\cal C}(A,M)$ of length $\geq
k$ that start with $v$. Obviously

${\cal C}(A,M)=\bigcup_{i=0}^{k-1}{\cal
C}(A,M)^{(i)}\,\,\cup\,\,\bigcup_{v\in{\cal C}(A,M)^{(k)}}{\cal
C}(A,M)_{v}\quad.$

We can decompose ${\cal C}(A,M)_{v}$ as follows

${\cal C}(A,M)_{v}\,=\,\bigcup_{a\in A}\,{\cal C}(A,M)_{va}\quad,$

where, of course ${\cal C}(A,M)_{va}$ is empty if appending the letter $a$
turns the clean $v$ into a dirty word. Now, writing $v=v_{1}\dots v_{k}$, and
for $a\in A$ the computer verifies whether the difference

$NCN(v_{1}\dots v_{k}aw)-NCN(v_{2}\dots v_{k}aw)\quad$

is always the same, for any $v_{1}\dots v_{k}aw\in{\cal C}(A_{M})_{va}$. The
way we implemented it is to test it for sufficiently long words, and then in
retrospect have the computer check it ‘logically’, by looking the at the
difference in the number of clean neighbors that happens by deleting the first
letter $v_{1}$. Let’s call this constant quantity $\alpha(v,a)$.

It follows that we have a system of $|{\cal C}(A,M)^{(k)}|$ equations with
$|{\cal C}(A,M)^{(k)}|$ unknowns.

$Weight({\cal C}(A,M)_{v})\,=\,\sum_{{{a\in A}\atop{va\in{\cal
C}(A,M)}}}xy^{\alpha(v,a)}Weight({\cal C}(A,M)_{v_{2}\dots v_{k-1}a})\quad.$

After the computer algebra system (Maple in our case) automatically found all
the $\alpha(v,a)$, and set up the system of equations, we kindly asked it to
solve it, getting certain rational functions of $x$ and $y$. Finally, our
object of desire, $f(x,y)$, is given by

$Weight({\cal C}(A,M))\,=\,\sum_{i=0}^{k-1}Weight({\cal
C}(A,M)^{(i)})\,+\,\sum_{v\in{\cal C}(A,M)^{(k)}}Weight({\cal
C}(A,M)_{v})\quad.$

This is implemented in procedure WtEs(A,M,y,x,MaxK).

If you also want to keep track of the individual letters, having the variable
$t$ take care of the length, the equations are

$Weight({\cal C}(A,M)_{v})\,=\,\sum_{{{a\in A}\atop{va\in{\cal
C}(A,M)}}}x_{v_{1}}ty^{\alpha(v,a)}Weight({\cal C}(A,M)_{v_{2}\dots
v_{k-1}a})\quad.$

This is implemented in procedure WtEg(A,M,x,y,t,MaxK).

Sample output

$\bullet$ If you want to see the bi-variate generating functions for words in
the alphabet $\\{0,1\\}$, avoiding $i$ consecutive occurrences of $1$, for
$2\leq i\leq 6$, see

https://sites.math.rutgers.edu/~zeilberg/tokhniot/oMarko1.txt .

Note that the original case was $i=2$.

$\bullet$ If you want to see the bi-variate generating functions for words in
the alphabet $\\{0,1\\}$, avoiding $i$ consecutive occurrences of $1$, and $i$
consecutive occurrences of $0$, for $3\leq i\leq 6$, see

https://sites.math.rutgers.edu/~zeilberg/tokhniot/oMarko2.txt .

$\bullet$ If you want to see all such generating functions (still with BINARY
words) for all possible SINGLE patterns of length 3,4,5 (up to symmetry), look
at:

https://sites.math.rutgers.edu/~zeilberg/tokhniot/oMarko3.txt .

The front of this article contains numerous other output files, but you dear
reader, can generate much more!

Conclusion

The value of the article [KMP], that inspired the present article, is not so
much with the actual result, that in hindsight, thanks to our Maple package,
is trivial, but in the human-generated ideas and methodology that enabled one
of us to generalize it to a much more general framework.

References

[KMP] Sandi Klav${\breve{z}}$ar, Michel Mollard and Marko
Petkov${\breve{s}}$ek, The degree sequence of Fibonacci and Lucas cubes,
Discrete Math. 311 (2011) 1310-1322. https://www-fourier.ujf-
grenoble.fr/~mollard/soumis/DegSeqSubmit.pdf

[NZ] John Noonan and Doron Zeilberger, The Goulden-Jackson Cluster Method:
Extensions, Applications, and Implementations, J. Difference Eq. Appl. 5
(1999), 355-377.
https://sites.math.rutgers.edu/~zeilberg/mamarim/mamarimhtml/gj.html .

[PWZ] Marko Petkov${\breve{s}}$ek, Herbert S. Wilf, and Doron Zeilberger,
“A=B”, A.K. Peters, 1996. https://www2.math.upenn.edu/~wilf/AeqB.pdf .

[Z] Doron Zeilberger, Marko Petko${\breve{s}}$v${\breve{s}}$ek (1955-2023), My
A=B Mate , Personal Journal of Shalosh B. Ekhad and Doron Zeilberger, April
14, 2023.
https://sites.math.rutgers.edu/~zeilberg/mamarim/mamarimhtml/mpm.html .

Shalosh B. Ekhad, c/o D. Zeilberger, Department of Mathematics, Rutgers
University (New Brunswick), Hill Center-Busch Campus, 110 Frelinghuysen Rd.,
Piscataway, NJ 08854-8019, USA. Email: ShaloshBEkhad at gmail dot com .

Doron Zeilberger, Department of Mathematics, Rutgers University (New
Brunswick), Hill Center-Busch Campus, 110 Frelinghuysen Rd., Piscataway, NJ
08854-8019, USA. Email: DoronZeil at gmail dot com .

April 21, 2023.


# Novel Intent Detection and Active Learning Based Classification (Student
Abstract)

Ankan Mullick

###### Abstract

Novel intent class detection is an important problem in real world scenario
for conversational agents for continuous interaction. Several research works
have been done to detect novel intents in a mono-lingual (primarily English)
texts and images. But, current systems lack an end-to-end universal framework
to detect novel intents across various different languages with less human
annotation effort for mis-classified and system rejected samples. This paper
proposes NIDAL (Novel Intent Detection and Active Learning based
classification), a semi-supervised framework to detect novel intents while
reducing human annotation cost. Empirical results on various benchmark
datasets demonstrate that this system outperforms the baseline methods by more
than 10% margin for accuracy and macro-F1. The system achieves this while
maintaining overall annotation cost to be just $\sim$ 6-10% of the unlabeled
data available to the system.

## Introduction

With the emerging new intents in the system, the conversational agents need to
be retrained in order to identify these newer intents aka novel classes. Also
as time progresses, the overall accuracy of identifying the known intents for
the user queries should not be compromised. Currently, if a user utterance
belongs to one of the known intents but the confidence score is low, these are
called rejected utterances. It is infeasible to label all the new instances
because of the sheer volume, and hence an effective mechanism to reduce human
annotation cost would be required. To address these issues, in this work, a
semi-supervised setting is adopted to identify known and novel intent classes.
Corresponding to this problem setting, it starts with an initial labelled
training data which consists of a set of known intents and a large unlabelled
data that comprises of known and novel intent classes. The evaluation is
performed on a predefined test set that consists of all the known and novel
classes.

In the last decade, researchers have focused on out of domain class detection
and explored various active learning methods in various scenarios to improve
classification and lowering the human annotation effort. Novel Class
Detection: Some advanced approaches are developed to explore class emergence
problem in data stream like SEEN (Zhu and Li 2020), Zero-Shot-OOD (Tan et al.
2019) and SENC-MaS (Mu et al. 2017) but there is less focus on novel intent
detection. Active Learning: ModAL (Danka and Horvath 2018) propose various
active learning (AL) strategies to improve system accuracy. (Tian and Lease
2011) develop a maximal marginal uncertainty based AL model. But, these are
not focused on rejected utterances.

In this work, an end-to-end framework is proposed to identify novel intents
with increased in-domain class detection accuracy while handling system
rejected utterances.

## Dataset

NIDAL approach is compared with similar models and evaluated across several
standard public dataset in NLU domain - SNIPS (Coucke et al. 2018), ATIS (Tur,
Hakkani-Tür, and Heck 2010) and Facebook Multi-lingual (Schuster et al. 2018).
This framework is language agnostic and performs significantly well on all the
datasets.

Method FB-EN FB-ES FB-TH ATIS SNIPS Acc Mac F1 Acc Mac F1 Acc Mac F1 Acc Mac
F1 Acc Mac F1 SEEN* 84.9 86.2 75.4 79.8 71.9 77.5 84.3 71.4 85.8 86.2 Zero-
Shot-OOD* 86.7 87.4 62.1 70.1 68.6 72.1 84.8 81.7 87.4 88.5 SENC-MaS* 82.3
83.9 69.4 70.5 64.6 72.8 80.1 69.4 82.0 81.4 NIDAL 98.0 93.1 91.5 96.1 92.5
89.5 92.1 88.9 97.9 95.5

Table 1: Overall Accuracy (Acc) and Macro average F1-score on Facebook-
English, Spanish, Thai, ATIS and SNIPS Datasets. * - advantage to these
baselines, since they do not distinguish between multiple novel intents.

## Approach

The framework “NIDAL” is divided into two major components - novel intent
detection and active learning. The Novel Intent Detection module detects out-
of-domain samples on unlabelled data and the active learning based known
intent classification, handles the rejected utterances ensuring higher overall
accuracy on the known intents.

Neural Model ($\mathcal{M}$): The JointBERT (Chen, Zhuo, and Wang 2019) is
used as the learning model for intent classification.English uncased BERT-Base
model is used as the base model for JointBERT. For other languages, bert-base-
multilingual-uncased model is used. The best results can be obtained when the
model is trained for 10 epochs and the learning rate is $5e-5$.

Part 1: Novel Intent Detection (NID): The algorithm for Novel Intent Detection
consists of the following Steps: Step 1 - Cycle 0: With the initial labelled
data ($\mathcal{L}$), consisting of examples only from the known intent set, a
Neural Model ($\mathcal{M}$) is trained. Step 2 - Out-Of-Domain Sample
Detection (OOD-SD): MSP (Hendrycks and Gimpel 2018) algorithm is considered to
detect Out-Of-Domain samples $\mathcal{U^{\prime}}$ on the Unlabelled Data
($\mathcal{U}$). Step 3 - Labeling of Novel Intents: $m\%$ of the OOD samples
is considered $\mathcal{U^{\prime}}$ for manual annotation
($\mathcal{U}^{\prime}_{m}$). Experiments are done with various labeling
strategies to add the rest of the OOD samples back to Cycle 0 training set
($\mathcal{L}$). Step 4 - Cycle 1: $\mathcal{M}$ is re-trained on the modified
training set to perform prediction on the Test Set.

Part 2: Active Learning (AL): Next, an active learning based framework is
devised to take care of rejected utterances with a low confidence. The
algorithm is as follows: Step 1 - Cycle 1: The retrained Neural Model
($\mathcal{M}$) is used to predict intent scores on the unlabelled dataset
after removing OODs ($\mathcal{U}_{rem}$). Step 2 - Cycle 1: A pre-defined
threshold ($\mathcal{TH}$) is set, and the samples with score $<\mathcal{TH}$
are then fed XGBoost (XGB) classifier and the prediction score is used to
identify their labels (auto-corrected). Samples which are rejected again, are
manually annotated. These auto-corrected and annotated samples are added back
to the labelled data and removed from the unlabelled data. Step 3 - Cycle 2:
The Neural Model ($\mathcal{M}$) is re-trained with updated labelled dataset
and redo step 1-2 for the same threshold value. Step 4: This approach is run
for $2\leq K\leq 5$ cycles.

## Experimental Results

Softmax Prediction Probability (MSP) is used to predict out-of-domain samples
based on the softmax prediction scores. Different threshold values on top of
Neural Model ($\mathcal{M}$) is set to identify rejected utterances and
optimum results are obtained when threshold is set to 75% of maximum
classification probability score for a particular dataset. These rejected
utterances are passed through XGBoost (XGB) classifier for auto-correction.
The rest of the samples (i.e. XGB rejected) are annotated manually. These auto
corrected and manually annotated samples are removed from the unlabelled set
and added back to labelled dataset, $L$ for retraining purposes. Thus the
auto-correction criteria, saves significant human labeling cost.

The results for Novel Intent Detection and Active Learning (NIDAL) in terms of
accuracy and macro f1 score for various english (Facebook-English [FB-EN],
SNIPS, ATIS) and non-english data (Facebook-Thai [FB-TH] and Facebook-Spanish
[FB-ES]) are shown in Table 1.

Competing Baselines: Experiments are done with modified versions of various
existing methods to compare NIDAL - SEEN (Zhu and Li 2020), Zero-Shot-OOD (Tan
et al. 2019) and SENC-MaS (Mu et al. 2017). Experiments are done with
different variations of baselines (parameter and hyperparameter tuning) and
the best results are reported. Since, all these methods can only detect one
novel class at a time, when considering the multiple novel intents in test set
as a single novel class for these methods and report the accuracy and macro-F1
considering the various known classes and a novel class for the same. The
results for different baselines are shown in Table 1. It is observed that the
annotation cost varies from 6-10% samples of the unlabelled data. Considering
the huge gains in performance, this is a reasonable annotation cost trade-off.
These experiments show that given the same amount of human labeling, this
framework works much better than the baselines.

## Conclusion

This paper proposes NIDAL, an end-to-end framework for detection of novel
intents, as well as to handle system rejected utterances using an active
learning framework. Experiments are performed on various benchmark datasets
and the results consistently show the efficacy of the proposed framework.
Specifically, it achieves large and consistent gains in performance with a
small human annotation cost across different datasets. One future step is to
extend this work on diverse domains (like finance, technology, healthcare
etc.).

## References

  * Chen, Zhuo, and Wang (2019) Chen, Q.; Zhuo, Z.; and Wang, W. 2019.  BERT for Joint Intent Classification and Slot Filling.  arXiv:1902.10909.
  * Coucke et al. (2018) Coucke, A.; Saade, A.; Ball, A.; et al. 2018.  Snips Voice Platform: an embedded Spoken Language Understanding system for private-by-design voice interfaces.  arXiv:1805.10190.
  * Danka and Horvath (2018) Danka, T.; and Horvath, P. 2018.  modAL: A modular active learning framework for Python.  _arXiv preprint arXiv:1805.00979_.
  * Hendrycks and Gimpel (2018) Hendrycks, D.; and Gimpel, K. 2018.  A Baseline for Detecting Misclassified and Out-of-Distribution Examples in Neural Networks.  arXiv:1610.02136.
  * Mu et al. (2017) Mu, X.; Zhu, F.; Du, J.; Lim, E.; and Zhou, Z.-H. 2017.  Streaming classification with emerging new class by class matrix sketching.  In _AAAI Conference_.
  * Schuster et al. (2018) Schuster, S.; Gupta, S.; Shah, R.; and Lewis, M. 2018.  Cross-lingual transfer learning for multilingual task oriented dialog.  _arXiv preprint arXiv:1810.13327_.
  * Tan et al. (2019) Tan, M.; Yu, Y.; Wang, H.; Wang, D.; Potdar, S.; Chang, S.; and Yu, M. 2019.  Out-of-domain detection for low-resource text classification tasks.  _arXiv preprint arXiv:1909.05357_.
  * Tian and Lease (2011) Tian, A.; and Lease, M. 2011.  Active learning to maximize accuracy vs. effort in interactive information retrieval.  In _ACM SIGIR conference_ , 145–154.
  * Tur, Hakkani-Tür, and Heck (2010) Tur, G.; Hakkani-Tür, D.; and Heck, L. 2010.  What is left to be understood in ATIS?  In _2010 IEEE Spoken Language Technology Workshop_ , 19–24. IEEE.
  * Zhu and Li (2020) Zhu, Y.-N.; and Li, Y.-F. 2020.  Semi-Supervised Streaming Learning with Emerging New Labels.  In _AAAI Conference_.