# A Doxastic Characterisation of Autonomous Decisive Systems††thanks:  This
work is partly funded by the German Research Council (DFG) as part of the
project “Integrated Socio-technical Models for Conflict Resolution and Causal
Reasoning”, grant no. FR 2715/5-1, DA 206/12-1

Astrid Rakow Carl von Ossietzky University, 26129 Oldenburg, Germany
<EMAIL_ADDRESS>
###### Abstract

A highly autonomous system (HAS) has to assess the situation it is in and
derive beliefs, based on which, it decides what to do next. The beliefs are
not solely based on the observations the HAS has made so far, but also on
general insights about the world, in which the HAS operates. These insights
have either been built in the HAS during design or are provided by trusted
sources during its mission. Although its beliefs may be imprecise and might
bear flaws, the HAS will have to extrapolate the possible futures in order to
evaluate the consequences of its actions and then take its decisions
autonomously. In this paper, we formalize an _autonomous decisive system_ as a
system that always chooses actions that it currently believes are the best. We
show that it can be checked whether an autonomous decisive system can be built
given an application domain, the dynamically changing knowledge base and a
list of LTL mission goals. We moreover can synthesize a belief formation for
an autonomous decisive system. For the formal characterization, we use a
doxastic framework for safety-critical HASs where the belief formation
supports the HAS’s extrapolation.

##  1 Introduction

Nowadays highly autonomous systems (HASs) are already able to work within
complex environments as e.g. the autonomous Tesla cars and the NASA’s
helicopter “Ingenuity” demonstrate. On the other hand, these systems have to
satisfy high safety standards. This is especially so for human cyberphysical
systems, where humans and autonomous systems symbiotically cooperate [24].
Accidents like [18, 21] show that there is still a long way to go before the
high safety standards can be reliably implemented.

A HAS faces the great challenge of making good decisions despite an
overwhelmingly complex and dynamic environment. In order to decide what to do
next, a HAS builds a belief about its current situation, usually by combining
incoming sensor data with prior data. As this data is often incomplete and
data from different sources may be contradictory, the HAS can never be sure of
its current state and thus deems several variants of the situation possible.
The HAS extrapolates the possible futures that might develop from the current
situation. Therefore, it simulates its action alternatives on a world model
that describes the impact of its actions as well as how the environment might
evolve. Hence, a HAS has to take decisions based on beliefs that concern its
past, present and future and that can only approximate the real world.

In this paper, we focus on safety critical systems and formalize the notion of
autonomous-decisive system. We call a system autonomous-decisive, if it can
choose its actions based on the contents of its beliefs and then achieves its
goals within the intended application domain. We formalize the notion within a
game-theoretic doxastic framework, where we use the possible worlds semantics
[12] to represent the beliefs of a system. A so-called _belief formation
function_ specifies the belief for a given history of perceptions and the
current knowledge base. The latter holds knowledge and hard beliefs. It
captures constraints that an engineer chooses to enforce on the system’s
beliefs (e.g. insights about the application domain) as well as statements
that the HAS gets from trusted sources during its mission. As we focus on
safety-critical systems, we use a two-player zero-sum reactive game. That is,
we consider the environment as adversarial and the system has to operate
successfully irrespective of the environment’s choices. By considering the
belief formation itself as a special kind of observation-based strategy, we
can synthesize a witness belief formation that enables a HAS to autonomously
achieve its goals.

Conceptually, the presented formalization will be useful in the early design,
where simple and abstract models are considered and decisions about the
resources of a system like its sensors and capabilities are made. The
formalism is applicable to any system that has to take autonomous decisions.
We imagine that the application domain and the mission goals are formally
described. When during the design the possible beliefs of the system have been
fixed, our framework can be used to examine whether the system can
successfully take autonomous decisions within the targeted application domain.
When the setting does not allow to decide autonomously, the design of its
possible beliefs, the system’s sensing capabilities or actions might have to
be adjusted. In certain cases, even the model of the application domain has to
be revised [9].

#### Outline

Next we introduce the ingredients of our formal framework. In Sect. 3 we
formalize autonomous-decisive systems as systems that are able to take
decisions based on their internal assessment of the situation. We prove that
it is decidable whether such a system exists for a given application domain,
available knowledge/hard beliefs, possible beliefs and mission goals. In Sect.
4 we present related and future work and conclude in Sect. 5.

##  2 Ingredients of our Doxastic Framework

In this section, we will introduce the ingredients our framework alongside a
running example. As a toy example, we consider the set-up as sketched in Fig.
1(a) where two cars are on separate lanes heading towards each other. The left
car is called ego and is our HAS. It has to avoid collisions and it has to
take the left turn. The right car, other, is uncontrolled (from ego’s
perspective).

###  2.1 A World

We assume that the HAS’s intended application domain is captured via a Kripke
structure, modelling static and dynamic objects and their interactions. This
so called _design-time world_ ${{W}}_{D}$ captures the information about the
application domain as well as test criteria that the HAS has to master as part
of the development and certification process.

######  Definition 2.1.

world Formally, a _world_ ${W}$ is a labelled Kripke structure
${W}=(\textit{S},\textit{Ed},\mathit{L},\textit{I})$, where S is the set of
states, $\textit{Ed}\subseteq\textit{S}\times\textit{S}$ are edges between
states, $\mathit{L}=\mathit{L}_{\textit{S}}\cup\mathit{L}_{\textit{Ed}}$ where
$\mathit{L}_{\textit{Ed}}=\textit{Ed}\rightarrow{2^{\textit{Act}}}$ labels
edges with a subset of the finite set of actions Act and
$\mathit{L}_{\textit{S}}:\textit{S}\rightarrow{2^{\textit{{AP}}}}$ labels
states with valuations of a finite set of Boolean propositions AP, and
$\textit{I}\subseteq\textit{S}$ is the set of initial states.
$\textit{Act}=\textit{Act}_{\textit{ego}}\times\textit{Act}_{\textit{env}}$ is
a set of tuples defining the simultaneous actions of our autonomous agent ego
and its environment env, which may include other agents. We assume that the
transition relation is defined for all states and actions, i.e.,
$\forall\textit{s}\in\textit{S},\forall
a\in\textit{Act},\exists\mathit{e}\in\textit{Ed}:a\in\mathit{L}_{\textit{Ed}}(\mathit{e})$.

In order to express that an action is not enabled at s, ${W}$ can transition
into a dedicated state $\textit{s}_{\textsf{undef}}$ that is accordingly
labelled.111In this paper any strategy has hence to avoid
$\textit{s}_{\textsf{undef}}$. A sequence of states
$\mathit{\pi}=\textit{s}_{0}\textit{s}_{1}\ldots\textit{s}_{n}\in\textit{S}^{*}\cup\textit{S}^{\omega}$
is a _path_ in ${W}$ iff $\forall i,0\leq
i<|\mathit{\pi}|:(\textit{s}_{i},\textit{s}_{i+1})\in\textit{Ed}$.
$\mathit{\pi}(i)$ is the state $\textit{s}_{i}$, $\mathit{\pi}_{\leq m}$
denotes the prefix $\textit{s}_{0}\ldots\textit{s}_{m}$ and
$\textit{last}(\mathit{\pi})$ is the last state of a finite path
$\mathit{\pi}$. $\mathit{\pi}$ is initial iff $s_{0}\in\textit{I}$.

######  Example 2.2.

A world In our running example, the actions of ego are f, “moving one step
forward if possible”, t, “turn and move one step forward”. Other is either a
slow car and moves one tile forward, if possible, or it is a fast car. In that
case, it moves two positions forward, if it is at its initial position, else
it moves one tile forward, if possible. Other’s actions are f and F, “move two
positions forward”. The actions of ego and other are annotated by pale blue
and dark blue arrows in Fig. 1(a).

The propositions
$\textit{{AP}}_{\textit{pos}}=\textit{{AP}}_{x_{e}}\cup\textit{{AP}}_{y_{e}}\cup\textit{{AP}}_{x_{o}}$
with $\textit{{AP}}_{x_{e}}=\\{x_{e}=i|1\leq i\leq 4\\}$,
$\textit{{AP}}_{y_{e}}=\\{y_{e}=i|1\leq i\leq 3\\}$,
$\textit{{AP}}_{x_{o}}=\\{x_{o}=i|1\leq i\leq 4\\}$ encode the positions of
the two cars, where $x_{e}=i$ and $y_{e}=i$ represent the horizontal and
vertical position of ego, and $x_{o}=i$ represents the horizontal position of
other. Its vertical position is always two. Other’s car type is encoded via
the propositions slow (s) and fast (f). We assume that ego cannot observe
other’s car type directly, but it has sensors perceiving other’s colour, which
is either red or blue. The proposition blue (red, fast, slow) is true, iff
other is a blue (red, fast, slow) car. The propositions bluep and redp encode
what ego perceives as other’s colour. They are used to modeling ego’s
imperfect colour recognition, while the propositions blue and red encode the
true colour of other. We assume that ego’s colour perception works correctly,
when ego and other are less than two tiles apart, otherwise the sensor
switches colours ($\textsf{blue}_{p}=\neg\textsf{blue}$,
$\textsf{red}_{p}=\neg\textsf{red}$). Let $\textit{{AP}}_{\textit{cartype}}$
be the set $\\{\textsf{fast, slow, blue, red, blue${}_{p}$, red${}_{p}$}\\}$.
The propositions in our example are hence
$\textit{{AP}}=\textit{{AP}}_{\textit{pos}}\cup\textit{{AP}}_{\textit{cartype}}\cup\\{\textsf{undef}\\}$,
where undef labels the sink state.

(a) Sketch of the world

(b) World model

Figure 1: A simple world ${{W}}_{D}$.

Figure 1(b) shows the Kripke structure of our design time world. States are
labelled with the propositions that hold in the respective state. The label
$\mathsf{abcdef}\in\mathbb{N}^{3}\times\\{f,s\\}\times\\{b,r\\}\times\\{b_{p},r_{p}\\}$
encodes that $x_{e}=a,y_{e}=b,x_{o}=c$ are true and other’s car type is d, its
colour is e whereas the perceived colour is f. The valuations of all other
propositions are false. Likewise, the label undef encodes that the only valid
proposition is undef. Edges are labelled with sets of actions. We omit the
sets’ brackets. For example, the label ff denotes the set $\\{\textsf{ff}\\}$,
that contains the one action ff, where ego and other simultaneously move one
step forward, if possible. Actions that are not enabled at a state lead to the
sink state $\textit{s}_{\textsf{undef}}$. We omit the sink state and sink
transitions in the sections that follow.

###  2.2 Goal List

Our HAS, ego, has to achieve a prioritized list of goals during a manoeuvre. A
_goal_ $\varphi$ is a linear-time temporal logic (LTL) formula [4]. We denote
the temporal operators “globally” by $\Box$, “eventually” by $\Diamond$,
“next” by $\mathsf{X}$ and “until” by $\mathsf{U}$. We interpret the LTL
formulae over (infinite) traces, which are infinite sequences
$t=t_{0}t_{1}\ldots\in(2^{\textit{{AP}}})^{\omega}$ of valuations of AP.
Satisfaction of an LTL formula $\varphi$ by a trace $t$ is denoted as
$t\models\varphi$. A _goal list_ $\psi=(\Phi,\textit{prio})$ consists of a set
$\Phi$ of LTL formulae and a priority function
$\textit{prio}:\Phi\rightarrow\\{1,\ldots,|\Phi|\\}$ where $\varphi\in\Phi$ is
more important than $\varphi^{\prime}\in\Phi$ iff
$\textit{prio}(\varphi)<\textit{prio}(\varphi^{\prime})$. We say that a trace
$t$ satisfies $\psi$ with priority up to $n$ if $n$ is the highest priority up
to which $t$ satisfies all goals of $\psi$, i.e., $t\models\varphi$ for all
$\varphi\in\Phi$ with $\textit{prio}(\varphi)\leq n$. A set of traces $T$
satisfies $\psi$ up to $n$, if all $t\in T$ satisfy $\psi$ up to a priority
$m$ with $n\leq m$ and $n$ is the greatest such priority. For convenience we
extend goal lists to include the trivial goal true, i.e.,
$\textsf{true}\in\Phi$ and $\textit{prio}(\textsf{true})=0$.

######  Example 2.3.

Prioritized Goals We formalize collision freedom as
$\varphi_{c}=\Box(x_{e}=2\land y_{e}=2\Rightarrow x_{o}\not=2)$, and
$\varphi_{t}=\Diamond(y_{e}=3)$ expresses that ego eventually does the turn.
In order to rule out that disabled transitions are taken, we use the goal
$\varphi_{u}=\Box\neg\textsf{undef}$. The priorities are given by
$\textit{prio}(\varphi_{u})=1,\textit{prio}(\varphi_{c})=2,\textit{prio}(\varphi_{t})=3$.

Let us now take a closer look at what ego should do in order to accomplish its
goals. If other is slow, then ego should not take the turn, but instead it
should drive straight on, in order to avoid the collision. If other is fast,
then ego can take the turn and accomplish all its goals.

###  2.3 Observations

Ego, being highly autonomous, will take decisions based on the beliefs that it
has constructed about the world in which it operates. Ego derives its beliefs
from the observations made so far and the knowledge/hard beliefs it has about
the world.

A world is usually only partially perceivable by ego via observations.
_Observations_ $\mathcal{O}$ are propositions of ${{W}}_{D}$ whose valuations
ego can assess and that represent e.g. sensor readings or received messages
from other agents. Observations shed light on ${{W}}_{D}$, but they do not
have to be truthful, as illustrated in 2.2, where initially bluep,redp were
switched and hence ego does not perceive the correct colour all the time.
Nevertheless, a HAS has to reason about the current state of the world based
on its past observations. Let $P$ be a set of propositions,
$P\subseteq\textit{{AP}}$. We call $h$ a ($P$-)_history_ of a state s, if
there is an initial path $\mathit{\pi}$ of ${W}$ leading to s and
$h=h_{0}h_{1}\ldots h_{n}$ is the sequence of state labels along
$\mathit{\pi}$, $h_{i}=\mathit{L}(\mathit{\pi}(i))\cap P,\forall i,0\leq i\leq
n$. We denote the set of $P$-histories as $\mathbb{H}_{P}$. We say $h$ is
_observable_ iff $P\subseteq\mathcal{O}$.

######  Example 2.4.

Observable History In our example ego cannot observe other’s position due to a
broken distance sensor, but it can observe its own position and the colour of
other, so that
$\mathcal{O}:=\textit{{AP}}_{x_{e}}\cup\textit{{AP}}_{y_{e}}\cup\\{\textsf{undef,
{blue}${}_{p}$, {red}${}_{p}$}\\}$. Given the world of Fig. 1(b),
$h\,=\,$114sbr${}_{p},$213sbb${}_{p},$312sbbp,411sbbp is the history along the
path s1,s2,s3,s5 wrt AP, whereas 11rp,21bp,31bp,41bp is the observable history
wrt $\mathcal{O}$.

###  2.4 Beliefs

A belief describes what ego currently thinks. For instance, ego may think that
it saw an approaching vehicle and that this vehicle is a slow car (or a fast
car). Depending on the type of car, ego will imagine different possible future
evolutions of the current situation.

######  Definition 2.5.

belief, reality A _belief_ $B$ is the set of alternative realities that ego
currently deems possible, $B=\\{{r}_{0},\ldots,{r}_{n}\\}$. A _reality_ is a
pair ${r}=({W},\textit{S}_{c})$ of a _(possible) world_ ${W}$ and a set of
believed current state $\textit{S}_{c}\subseteq\textit{S}$, where any current
state is reachable from one initial state but no initial state is reachable
from a current state.

A reality describes possible pasts, current states and futures: pasts are
captured by the set of paths between initial states I and current states
$\textit{S}_{c}$, the possible futures are paths from the current states.

######  Example 2.6.

Alternative Realities and Beliefs To illustrate the notion of belief as
introduced above, let us consider two alternative realities of ego in Fig.
2(a)+(b). The believed past is marked by framing state labels.
(a) ego is at $b_{0}$, other is slow (b) ego is at $c_{1}$, other is fast.
Figure 2: Two alternative realities of ego  The alternative reality of (a)
describes that other is slow and that ego itself is at the initial state
$b_{0}$ of that world. In (b) other is fast and ego is at $c_{1}$, the
“second” state of that world. The believed history is 114fr,212fr. Since a
belief is a set of alternative realities, singletons of either (a) or (b) form
a belief. Also, the set of (a) and (b) forms a belief, where ego thinks both
alternatives are possible.

Note, ego may believe in possible worlds that are substantially different from
${{W}}_{D}$, since it usually captures the real world by simplified concepts
and rules, that may reflect the inner workings of the application domain only
coarsely but sufficiently. Since a HAS has only finite resources, we assume
that the set of _possible beliefs_ $\mathbb{B}$ and the set of _possible
worlds_ ${\mathbb{W}}:=\bigcup_{(\textit{S}_{c},{W})\in\mathbb{B}}{W}$ are
finite. The choice of $\mathbb{B}$ constitutes a design decision within the
development process of the HAS.

######  Example 2.7.

Possible Beliefs $\mathbb{B}$ Our ego has been designed to represent a certain
set of scenarios, for which it can evaluate what to do by extrapolating the
future. Figures 3(a)-(d) sketch a set of the alternative realities via their
initial set-up. The other car may be fast or slow, the road may be up to 6
tiles long, the intersection may be at $x=2$ or $x=3$, and the start position
of other varies from $x=4$ to $x=6$. Note, that ${{W}}_{D}$ of Fig. 1 is
described by Fig. 3 (a).

(a)

(b)

(c)

(d)

Figure 3: Sketch of ego’s possible beliefs. If other is fast, it uses the
dashed arrow at first and then the solid arrows. If it is slow, it uses the
solid arrow.

Let ego’s possible beliefs $\mathbb{B}$ be the beliefs that canonically evolve
from these initial scenarios.

###  2.5 Knowledge/Hard Beliefs

Knowledge/Hard Beliefs are statements with which an engineer equips a system
during the system design or that are provided by certain trusted sources (e.g.
a traffic control system) during the HAS’s mission. We think of statements
like $(\varphi_{a})$ _“In settled areas the speed limit is
$50\text{\,}\mathrm{k}\mathrm{m}\mathrm{/}\mathrm{h}$”_, $(\varphi_{b})$ _“I
will be on the highway for the next 20 mins.”_ or rules like $(\varphi_{c})$
_“If A promises to give way, I can rely on it.”_. We specify these statements
via an LTL variant, which we call Belief-LTL (BLTL). A BLTL formula $\varphi$
is an LTL formula that is preceded by either the operator $\mathsf{K}$ or
$\mathsf{B}$. $\mathsf{K}\varphi$ reads as _“ego believes that it knows
$\varphi$”_. A belief $B$ satisfies $\mathsf{K}\varphi$,
$B\models\mathsf{K}\varphi$, if in all alternative realities of $B$, $\varphi$
holds on all traces of all initial paths. Note, $\mathsf{K}\varphi$ may hold,
although $\varphi$ may not hold on ${{W}}_{D}$. $\mathsf{B}\varphi$ is defined
as $\neg\mathsf{K}\neg\varphi$ and reads as _“ego believes that $\varphi$ is
possible”_. Likewise, we define $\mathsf{K}^{c}$ or $\mathsf{B}^{c}$ on traces
from current states. A finite set of BLTL formulae constitutes a _knowledge
base_ $\mathcal{K}\in\mathbb{K}$. A belief $B$ satisfies ${\mathcal{K}}$,
$B\models\mathcal{K}$, if $B\models\varphi$ holds for all
$\varphi\in\mathcal{K}$. We assume that ego’s knowledge base varies over time.
Therefore, we extend the labelling function $\mathit{L}$ by
$\mathit{L}_{\mathbb{K}}:\textit{S}\rightarrow\mathbb{K}$ specifying the
available knowledge base at a state. Given a history $h$, $\mathcal{K}_{h}$
denotes the knowledge base of $\textit{last}(h)$.

######  Example 2.8.

A Knowledge Base Let ego have the following knowledge base $\mathcal{K}$ at
all states.

  1. 1.

$\varphi_{z}=\mathsf{K}\Box((\neg x_{o}=5\land\neg
x_{o}=6)\lor\textsf{undef})$ (other is at most at $x=4$),

  2. 2.

$\varphi_{t}=\mathsf{K}\Box(\neg
x_{e}=2\Rightarrow(y_{e}=1\lor\textsf{undef}))$ (a turn may only be possible
at $x=2$),

  3. 3.

$\varphi_{i}=\mathsf{K}\,x_{e}=1$ (ego starts at $x=1$) and

  4. 4.

$\varphi_{ct}=\mathsf{K}\Box\bigwedge_{t\in\\{\textsf{slow,
fast}\\}}(t\Rightarrow\mathsf{X}(t\lor undef))\land(\neg
t\Rightarrow\mathsf{X}(\neg t\lor\textsf{undef}))$ (the initial car type does
not change).

###  2.6 Belief Formation

Ego updates its beliefs e.g. when it gets new information from its sensors, a
clock tick or a message from another agent. The belief formation function
$\mathcal{B}$ captures formally how ego builds its belief.

######  Definition 2.9.

belief formation function, knowledge-consistent The belief formation function
$\mathcal{B}$,
$\mathcal{B}:\mathbb{H}_{\mathcal{O}}\times\mathbb{K}\rightarrow\mathbb{B}$,
specifies the belief $B$ that ego derives after perceiving history $h$ of
observations $\mathcal{O}\subseteq\mathbb{O}$ and while trusting in
$\mathcal{K}_{h}$.

We call a belief formation function $\mathcal{B}$ _knowledge-consistent_ , if
its beliefs satisfy the current knowledge base, i.e.,
$\mathcal{B}(h,\mathcal{K}_{h})\models\mathcal{K}_{h}$ for all $h$.

Note, that $\mathit{L}_{\mathbb{K}}$ is a mean to define a relation between
ego’s beliefs and the ground truth, when the belief formation is knowledge-
consistent. In that case we can for instance specify that the formed beliefs
have to be consistent with the last two observations, or with messages of the
traffic control system.

For a history of observations $h=h_{0}h_{1}\ldots h_{n}$ and a history of
knowledge bases
$\mathcal{K}=\mathcal{K}_{0}\mathcal{K}_{1}\ldots\mathcal{K}_{n}$, we denote
by $\bar{\mathcal{B}}(h,\mathcal{K})$ the resulting history of beliefs,
$\mathcal{B}(h_{0},\mathcal{K}_{0})\mathcal{B}(h_{0}h_{1},\mathcal{K}_{1})\ldots\mathcal{B}(h_{0}h_{1}\ldots
h_{n},\mathcal{K}_{n})$. We usually write $\mathcal{B}(h)$ instead of
$\mathcal{B}(h,\mathcal{K}_{h})$. Likewise, we write $\bar{\mathcal{B}}(h)$
for $\bar{\mathcal{B}}(h,\mathcal{K})$.

######  Example 2.10.

Knowledge-Consistent Belief Formation Let us now see how ego’s belief
formation could be like. Let ego have the knowledge base $\mathcal{K}$ of 2.8
and let ego also be convinced that a red car is fast, while a blue car is
slow, i.e.,
$\varphi_{b}=\Box(\textsf{fast}\Leftrightarrow\textsf{red}_{p})\land\Box(\textsf{slow}\Leftrightarrow\textsf{blue}_{p})$,
so all states of ${{W}}_{D}$ are labelled with
$\mathcal{K}^{\prime}:=\mathcal{K}\cup\varphi_{b}$ by
$\mathit{L}_{\mathbb{K}}$. In order to satisfy $\mathcal{K}$, only beliefs
sketched in (a) of Fig. 3 remain possible. The initial belief of a knowledge-
consistent belief formation has to consist of the alternative realities
depicted in Fig. 4(a)+(c). When ego in the real world scenario of Figure 4(b)
incorrectly perceives that other is blue, it will form $B_{b}$, the belief of
Figure 4(a). $B_{b}$ expresses that ego thinks it knows that other is blue and
hence a slow car, although it is red in the real world. It moreover captures
ego’s expectation of how the future will develop. Similarly, Fig. 4(c) shows
the belief $B_{r}$, which ego forms, when it is in the real world scenario of
Fig. 4(d) and incorrectly perceives that other is red.

(a)  Alternative reality: Other is slow

(b) Real world: Other is fast

(c)  Alternative reality: Other is fast

(d) Real world:
Other is slow

Figure 4: The two alternative realities of ego at its initial state (a)+(c);
the real world scenarios (c)+(d) with observable values in bold face type.

So, since ego’s perception is mistaken, ego is initially convinced that there
is a fast car, when there is a slow car and vice versa. Ego hence thinks that
it should do the turn, when it should not. But ego does not have to take the
decision whether to turn at that time. It first moves one tile forward, while
other simultaneously moves either one or two tiles forward. In both cases, ego
then perceives other’s colour correctly.

Let us say, in retrospective ego is aware of the faulty perception and
corrects its belief on other’s car type and colour. It updates the belief to
Fig. 5(a) when it is in the scenario Fig. 4(b), and to Fig. 5(b), when in Fig.
4(d). Figure 6 sketches the belief formation so far. The observed history 11rp
is mapped to belief B0,1 and 11b${}_{p}\mapsto$B0,2,
11rp,21b${}_{p}\mapsto$B1,1 and 11bp,21r${}_{p}\mapsto$B1,2. The sketched
belief formation is knowledge-consistent. Although ego changed its belief
about other’s type, $\varphi_{ct}$ holds for each formed belief.

(a)

(b)

Figure 5: Possible worlds

Since ego’s beliefs match now the reality, ego is able to assess the best
strategy. Ego can develop its strategy based on its sequence of beliefs,
arguing along the lines “Initially I thought the car is red and fast and that
it is a good idea to do the turn. Now I think the car is blue and slow and
then the turn is not good idea, since I would collide with other. Since I
believe, that my current belief matches the reality, I choose to drive
straight on.”

Figure 6: Sketch of a belief formation function

In the above example, the belief is made up of singletons of alternative
realities only. The next example illustrates the use of several alternative
realities.

######  Example 2.11.

Alternative Realities Let us assume that ego is unsure of its own initial
position, thinking that it may initially be at $x=1$ or $x=2$, as sketched in
Fig. 3(a)+(c). So ego deems two realities possible, when at state $s1$. In
both realities other is red, but in one reality, $r_{1}$, ego is at $x=1$, in
the other, $r_{2}$, at $x=2$. Similarly, ego deems two realities possible when
at $s6$.

Figure 7: Sketch of a belief formation function when ego is unsure of its
initial position

###  2.7 Doxastic Model

To summarize, a doxastic model $D$ is given by a tuple
(${{W}}_{D}$,$\psi$,$\mathbb{K}$,$\mathcal{O}$,$\mathbb{B}$,$\mathcal{B}$) of
the design-time world ${{W}}_{D}$, the prioritized list of goals $\psi$, the
knowledge bases $\mathbb{K}$, a set of observations $\mathcal{O}$, the set of
possible beliefs $\mathbb{B}$ of a HAS and a belief formation $\mathcal{B}$.
The belief formation describes how a system links observations made within the
world ${{W}}_{D}$ to the HASs inner representation of the world, i.e. the
beliefs $\mathbb{B}$ that a HAS can possibly build. The world ${{W}}_{D}$ is
considered as ground truth during the design. Later design steps have to take
care of the gap between ${{W}}_{D}$ and the real world.

##  3 Autonomous Decisions

In this section, we formalize what it means that ego decides autonomously. Ego
decides autonomously, if its decision is the result of ego’s simulative
assessment of its actions on content of its beliefs and the decision is
sensible wrt ego’s observations.

Our formalization hence distinguishes between autonomous systems –systems that
take decisions based on the belief content– and automatic systems –systems
that play out rule-based decisions that have been taken at design time. In
order to formalize _autonomous-decisive_ we contrast (i) strategies that have
access to ground-truth with (ii) strategies that can only observe the formed
beliefs, and (iii) strategies that run as simulation within the beliefs. The
different strategy notions are introduced step by step in the sequel and an
overview of the notions is given in Table 1.

###  3.1 Truth-Observing and Doxastic Strategies

In our framework, we use truth-observing strategies as reference of what would
be achievable, if ego could directly access the ground truth ${{W}}_{D}$ via a
set of propositions P. To this end, we say ego implements a _P -truth-
observing strategy_
${\textsf{s}_{t}}:(2^{\textit{{P}}})^{+}\rightarrow\textit{Act}_{\textit{ego}}$,
if ego chooses its actions based on the history of values of
$\textit{{P}}\subseteq\textit{{AP}}_{d}$ as observed in ${{W}}_{D}$.
Implementing ${\textsf{s}_{t}}$ means that ego decides what to do at a state
$\mathit{\pi}(i)$, reached via the path $\mathit{\pi}$ in ${{W}}_{D}$, based
on $\mathit{L}(\mathit{\pi}_{\leq i})|_{\textit{{P}}}$, i.e. based on the true
past values of P observed thus far. A truth-observing strategy
${\textsf{s}_{t}}$ together with a sequence of environment actions
$\textit{e}\in\textit{Act}_{\textit{env}}^{\omega}$ determines a set of
traces, $T(\textit{e},{\textsf{s}_{t}})$. Formally,
$T(\textit{e},{\textsf{s}_{t}})=\\{t_{0}t_{1}\ldots\in(2^{\textit{{AP}}_{D}})^{\omega}|\exists\textit{
path }\mathit{\pi}\textit{ from }\textit{I}_{D},\forall i\geq
0:t_{i}=\mathit{L}_{D}(\mathit{\pi}(i))\land
a_{i}:={\textsf{s}_{t}}(\mathit{L}_{D}(\mathit{\pi}_{\leq
i})|_{\textit{{P}}})\land(a_{i},\textit{e}(i))\in\mathit{L}_{D}(\mathit{\pi}_{i},\mathit{\pi}_{i+1})\\}$.

Since ego has no direct access to the ground truth, we also formalize that ego
decides based on the history of beliefs. At a state $\mathit{\pi}(i)$ in
${{W}}_{D}$ ego takes a decision based on the history of its beliefs
$b_{0}\ldots b_{i}$ that ego has built along $\mathit{\pi}_{\leq i}$. Ego
implements a doxastic strategy
${\textrm{s}_{d}}:\mathbb{B}^{+}\rightarrow\textit{Act}_{\textit{ego}}$ on
${{W}}_{D}$, if ego chooses its actions based on the history of its beliefs. A
strategy ${\textrm{s}_{d}}$ together with a sequence of environment actions
$\textit{e}\in\textit{Act}_{\textit{env}}^{\omega}$ determines a set of traces
in ${{W}}_{D}$, just like for truth-observing strategies. The set of traces is
$T(\textit{e},{\textrm{s}_{d}})=\\{t_{0}t_{1}\ldots\in(2^{\textit{{AP}}_{D}})^{\omega}|\exists\textit{
path }\mathit{\pi}\textit{ from }\textit{I}_{D},\forall i\geq
0:t_{i}=\mathit{L}_{D}(\mathit{\pi}(i))\land
a_{i}:={\textrm{s}_{d}}(\mathcal{B}(\mathit{\pi}_{\leq
i}))\land(a_{i},\textit{e}(i))\in\mathit{L}_{D}(\mathit{\pi}_{i},\mathit{\pi}_{i+1})\\}$.
Note that a doxastic strategy also depends on observations of the doxastic
model $D$ due to the belief formation $\mathcal{B}$ (cf. 2.9).

Since truth-observing and doxastic strategies both determine traces for a
given sequence of environment actions, we can compare them straight forwardly:
Ego achieves $\psi$ up to $n$ on ${{W}}_{D}$ by strategy s, if for all
$\textit{e}\in\textit{Act}_{\textit{env}}^{\omega}$ all $t\in
T(\textit{e},\textit{s})$ satisfy $\psi$ up to $n$. A strategy _s
$\psi$-dominates $\textit{s}^{\prime}$ on ${W}$_,
$\textit{s}^{\prime}\leq_{{W}}\textit{s}$, iff $\textit{s}^{\prime}$ achieves
$\psi$ up to $m$ and s up to $k\geq m$.

######  Example 3.1.

Truth-Observing and Doxastic Strategies As an example of a dominant P-truth-
observing strategy, let us consider the goal list of 2.3, the world model in
Fig. 1(b), $\textit{{P}}:=\\{x_{e},\textsf{slow},\textsf{fast}\\}$ and the
strategy ${\textsf{s}_{t}}$ that chooses to drive straight on, if other is
fast, and it chooses to turn, if other is slow (it maps $1s\mapsto f$,
$1s,2s\mapsto f$, $1s,2s,3s\mapsto f$, $1s,2s,3s,4s\mapsto f$, and $1f\mapsto
f$, $1f,2f\mapsto t$, …). Strategy ${\textsf{s}_{t}}$ achieves $\psi$ up to
$2$ and is a dominant (P-truth-observing) strategy, since in all cases
collision-freedom is guaranteed and in case the car is slow, no other strategy
is able to realize both, the turn and collision freedom.

Let us now define a doxastic strategy ${\textrm{s}_{d}}$ for a belief
formation, as sketched in Fig. 6. Let ${\textrm{s}_{d}}$ be a doxastic
strategy with $B_{0,1}\mapsto f$, $B_{0,1}\,B_{1,1}\mapsto f$, $\ldots$ and
$B_{0,2}\mapsto f$, $B_{0,2}\,B_{1,2}\mapsto t$, $\ldots$. Just like
${\textsf{s}_{t}}$, ${\textrm{s}_{d}}$ chooses to turn when other is fast
($B_{0,2}\,B_{1,2}\mapsto t$), and it chooses to drive straight on, if other
is slow ($B_{0,1}\,B_{1,1}\mapsto f$). As there is “no better” strategy,
${\textrm{s}_{d}}$ is dominant.

Next, we want to capture that ego chooses its actions based on the _content_
of its beliefs. In order to motivate our formalization, let us consider the
following example.

######  Example 3.2.

Decisions Not Based on the Belief Content We modify our running example
slightly: Let us assume the colour perception is severely broken and
permanently switches red to blue and vice versa. In Fig. 8 the changed world
model is given, and a belief formation is sketched, that derives a belief that
trusts in the colour perception, i.e., if the sensors say the other car is
red, then ego believes the other car is red.

Figure 8: Sketch of a belief formation function for severely broken colour
perception

Let ${\textrm{s}_{d}}^{\prime}$ be a doxastic strategy with $B_{0,1}\mapsto
f$, $B_{0,1},B_{1,2}\mapsto f$, $\ldots$ and $B_{0,2}\mapsto f$,
$B_{0,2},B_{1,1}\mapsto t$, $\ldots$. Just as ${\textsf{s}_{t}}$ and
${\textrm{s}_{d}}$, the strategy ${\textrm{s}_{d}}^{\prime}$ realizes a turn
on ${{W}}_{D}$, if other is fast ($B_{0,2},B_{1,1}\mapsto t$), and ego drives
straight on, if other is slow ($B_{0,1},B_{1,2}\mapsto f$). So
${\textrm{s}_{d}}^{\prime}$ is also dominant, but ${\textrm{s}_{d}}^{\prime}$
makes no sense from ego’s perspective. In case other is fast, ego believes
that other is slow, since it trusts its sensors. In this case, ego
extrapolates that doing the turn would cause a collision, but according to
${\textrm{s}_{d}}^{\prime}$, ego chooses to take the turn. Vice versa,
${\textrm{s}_{d}}^{\prime}$ chooses to drive straight on, when ego believes
other is fast and although ego extrapolates that taking the turn is alright.

###  3.2 Autonomous-decisive System

We now formalize what it means that ego decides based on the content of its
belief. Ego always chooses an action that belongs to a strategy that is
dominant in ego’s current belief $B$. To capture this formally, we introduce
the notion of _possible-worlds strategy_. A _possible-worlds strategy_ is a
function
${\textsf{s}_{\textsf{p}}}:{(2^{\textit{{AP}}_{B}})^{+}}\rightarrow\textit{Act}_{\textit{ego}}$
and it is simulated on the alternative realities of ego’s current belief $B$.
This results in “believed traces”. We define this set of traces in an
alternative reality ${r}=({W},\textit{S}_{c})\in B$ for a (believed) sequence
of environment actions
$\textit{e}\in\textit{Act}_{\textit{env}}^{\omega}({W})$ as
$T(\textit{e},{\textsf{s}_{\textsf{p}}},{r})=\\{t_{0}t_{1}\ldots\in(2^{\textit{{AP}}})^{\omega}|\exists\textit{
path }\mathit{\pi}\textit{ in }{W}\textit{ from }\textit{I}:\forall i\geq
0:t_{i}={\textsf{L}}(\mathit{\pi}(i))\land
a_{i}:={\textsf{s}_{\textsf{p}}}({\textsf{L}}(\mathit{\pi}_{\leq
i}))\land(a_{i},e(i))\in{\textsf{L}}({\mathit{\pi}}_{i},\mathit{\pi}_{i+1})\\}$.
We generalize the notion of $\psi$-dominance to possible-worlds strategies. A
possible-worlds strategy $\textsf{s}_{\textsf{p}}$ $\psi$-dominates a
possible-worlds strategy ${\textsf{s}_{\textsf{p}}}^{\prime}$ in $B$, if
$\textsf{s}_{\textsf{p}}$ $\psi$-dominates
${\textsf{s}_{\textsf{p}}}^{\prime}$ in all realities ${r}\in B$.

######  Example 3.3.

Possible-Worlds Strategy Consider the possible-worlds strategy that chooses to
turn, if other is fast, and to drive straight on, if other is slow, i.e.,
consider $\textsf{s}_{\textsf{p}}$ with $114fr\mapsto f$, $114fr,212fr\mapsto
t$, $114fr,212fr,221fr\mapsto f$, …, $114sb\mapsto f$,
$114sb,213sbb_{p}\mapsto f$, … In the belief $B_{0,1}$ of Fig. 8 ego thinks
that it is at the initial state $114fr$. Ego follows $\textsf{s}_{\textsf{p}}$
by choosing ${\textsf{s}_{\textsf{p}}}(114fr)=f$. In contrast, the belief
$B_{1,2}$ captures that ego thinks to have already made one move and is now at
state $212fr$. Ego follows $\textsf{s}_{\textsf{p}}$ by choosing
${\textsf{s}_{\textsf{p}}}(114fr,212fr)=t$.

Strategy tyes:
• _truth-observing strategy_
${\textsf{s}_{t}}:(2^{\textit{{P}}})^{+}\rightarrow\textit{Act}_{\textit{ego}}$
observes the ground truth world ${{W}}_{D}$ via
$\textit{{P}}\subseteq\textit{{AP}}_{{{W}}_{D}}$ and takes decisions based on
their history; serves as comparative reference of what is achievable given P
could be observed directly
• _doxastic strategy_
${\textrm{s}_{d}}:\mathbb{B}^{+}\rightarrow\textit{Act}_{\textit{ego}}$
observes the beliefs to take decisions and takes decisions based on their
history; represents the decision making of autonomous and automatic systems
• _possible-worlds strategy_
${\textsf{s}_{\textsf{p}}}:{(2^{\textit{{AP}}_{B}})^{+}}\rightarrow\textit{Act}_{\textit{ego}}$
captures how a HAS “simulates” its strategies within the alternative
realities; decisions are taken based on the believed history within the
respective alternative reality
A strategy s _$\psi$ -dominates_ $\textit{s}^{\prime}$,
$\textit{s}^{\prime}\leq\textit{s}$, iff $\textit{s}^{\prime}$ achieves $\psi$
up to $m^{\prime}$ but s achieves $\psi$ up to $m^{\prime}$ with
$m^{\prime}\leq m$.

Table 1: Strategy types & dominance in a nutshell

A peculiarity of possible-worlds strategies is, that they can be indecisive
for a belief: A belief may contain alternative realities encoding even
contradictory information. E.g. let us assume that ego is currently not sure
where its goal position is. In the alternative reality ${r}_{1}$ its goal
position is to its left while in ${r}_{2}$ the goal position is right of ego.
Ego’s strategy is to move to the left, when in ${r}_{1}$ and to move to the
right when in ${r}_{2}$. Since ego deems both realities possible, it cannot
decide whether to turn right or left.

######  Definition 3.4.

current-state decisive possible-worlds strategy, current-state choice A
possible-worlds strategy $\textsf{s}_{\textsf{p}}$ is _current-state decisive
in a belief $B$_, if $\textsf{s}_{\textsf{p}}$ specifies one and the same
action for all the believed current states of all alternative realities of
this belief, i.e.
$\exists\,a_{B}\in\textit{Act}_{\textit{ego}}$ such that
$\forall{r}=({W},\textit{S}_{c})\in B:\forall\textit{ paths }\pi\textit{ in
}{W}:\pi(0)\in\textit{I}\land\textit{last}(\pi)\in\textit{S}_{c}\Rightarrow{\textsf{s}_{\textsf{p}}}(\pi)=a_{B}$.
Let $\textit{Act}({\textsf{s}_{\textsf{p}}},B)$ denote the action $a_{B}$ that
${\textsf{s}_{\textsf{p}}}$ chooses at the current states
$\bigcup_{(.,\textit{S}_{c})\in B}\textit{S}_{c}$ of $B$. We call
$\textit{Act}({\textsf{s}_{\textsf{p}}},B)$ be the current-state choice of
$\textsf{s}_{\textsf{p}}$.

We can now define our notion of autonomous-decisive system. We consider a
system to be autonomous-decisive, if (i) it takes its decisions based on the
content of its beliefs and (ii) the resulting behaviour is sensible. We
capture (i) by requiring that there is a doxastic strategy ${\textrm{s}_{d}}$,
i.e., a strategy that can only observe the beliefs. Moreover,
${\textrm{s}_{d}}$ takes only actions that seem the best choice according to
the simulation within its beliefs. With other words, ${\textrm{s}_{d}}$ only
takes actions that are the current-state choice of a dominant, current-state
decisive possible-worlds strategy. We capture (ii) by requiring that
${\textrm{s}_{d}}$ does not perform worse than a strategy that decides based
on the made observations, i.e. ${\textrm{s}_{d}}$ is not $\psi$-dominated by a
$\mathcal{O}$-truth-observing strategy. We hence require that the belief
formation captures the gist of observations.

######  Definition 3.5.

doxastic system, autonomous-decisive system Let a doxastic model
$D=({{W}}_{D},\psi,\mathbb{K},$ $\mathcal{O},\mathbb{B},\mathcal{B})$ be
given.

A doxastic strategy ${\textrm{s}_{d}}$ is _autonomous-decisively_ achieving
$\psi$ up to $n$, if ${\textrm{s}_{d}}$ achieves $\psi$ up to $n$ and it
always follows dominant, current-state decisive possible-worlds strategies,
i.e.,
for all observed histories $h$, it holds that there is a dominant possible-
worlds strategy ${\textsf{s}_{\textsf{p}}}$ with
${\textrm{s}_{d}}(\bar{\mathcal{B}}(h))=\textit{Act}({\textsf{s}_{\textsf{p}}},\mathcal{B}(h))$
that is current-state decisive in $\mathcal{B}(h)$.

A _(doxastic) system_ is a pair $\mathcal{S}=(D,{\textrm{s}_{d}})$ of a
doxastic model $D$ and a doxastic strategy ${\textrm{s}_{d}}$. $\mathcal{S}$
is an _autonomous-decisive system_ , if there is an $n$ such that
${\textrm{s}_{d}}$ autonomous-decisively achieves $\psi$ up to $n$ and
${\textrm{s}_{d}}$ is not $\psi$-dominated by a $\mathcal{O}$-truth-observing
strategy.

######  Example 3.6.

Autonomous, Non-Autonomous, Automatic

Let us consider an example of an autonomous ego in the setting of Fig. 6,
where the sensor only initially switches colours, and consider the possible-
worlds strategy $\textsf{s}_{\textsf{p}}$ of 3.3 (turn, if other is fast, and
drive on, if other is slow). When ego initially evaluates its situation in
$s_{1}$ of ${{W}}_{D}$, it believes that the situation is as described by
$B_{0,1}$, i.e. other is a fast, red car. Ego can decide to follow
$\textsf{s}_{\textsf{p}}$ in $B_{0,1}$, as it seems a good choice –
$\textsf{s}_{\textsf{p}}$ is dominant and current-state decisive in $B_{0,1}$.
According to its extrapolation, it would move one step forward, and then it
would successfully take the turn. After actually moving forward, ego evaluates
the situation in $s_{2}$. In $s_{2}$ ego believes in $B_{1,1}$ reflecting that
ego now truthfully perceives other’s colour as blue (cf. 2.10). Again,
$\textsf{s}_{\textsf{p}}$ is a dominant current-state decisive possible-worlds
strategy and determines f as the next move. Along this line, it is easy to see
that ego can implement a doxastic strategy ${\textrm{s}_{d}}$ that chooses the
action that $\textsf{s}_{\textsf{p}}$ determines for the respective
$\mathcal{B}(h)$.

For an example of a non-autonomous ego, we modify our running example
slightly. Let us assume that ego is unsure of its own initial position,
thinking that it may initially be at $x=1$ or $x=2$, as sketched in Fig. 7.
Let a belief formation be given that evolves the initial beliefs $B_{0,3}$ and
$B_{0,4}$ analogously to 2.10, that is, ego perceives the correct colour after
moving one step forward. The possible-worlds strategy
$\textsf{s}_{\textsf{p}}$ is still a dominant strategy but not current-state
decisive, since for example in $B_{0,3}$ ego would do the turn at $s1$ due to
reality $r_{2}$, and it would also drive straight on due to $r_{1}$. Hence,
there is no dominant possible-worlds strategy in $B_{0,3}$ that is able to
determine one action. Ego cannot decide autonomously.

Note that we nevertheless can specify a dominant doxastic strategy
${\textrm{s}_{d}}$ for this case, but its actions are not chosen based on the
belief content: Ego chooses to turn after one step when its initial belief was
$B_{0,4}$ ($B_{0,4},B_{1,4}\mapsto t$), otherwise it drives straight on. This
strategy is dominant and could be used to build an _automatic_ system, where
ego just plays out ${\textrm{s}_{d}}$. Such a strategy might be useful when an
engineer knows that ego will start from $x=1$ but did not equip ego with this
information.

A system that is not autonomous-decisive cannot determine by itself which
action is currently appropriate. A goal for the design of a HAS is to ensure
that a system is autonomous-decisive.

######  Theorem 3.7 (Autonomous Decisiveness).

Let $D=({{W}}_{D},\psi,\mathcal{K},\mathcal{O},\mathbb{B})$, a doxastic model
without belief formation function, be given.

We can decide whether there is a knowledge-consistent belief formation
$\mathcal{B}$ and a doxastic strategy ${\textrm{s}_{d}}$ such that
$\mathcal{S}=(D,\mathcal{B},{\textrm{s}_{d}})$ is an autonomous-decisive
system that achieves $\psi$ up to $n$. If such $\mathcal{B}$ and
${\textrm{s}_{d}}$ exist, we can synthesize them.

###### Proof Sketch 1

We build a Kripke structure ${{W}}_{D}^{\prime}$ such any truth-observing
strategy ${\textsf{s}_{t}}$ in ${{W}}_{D}^{\prime}$ encodes a belief formation
$\mathcal{B}$ and a doxastic strategy ${\textrm{s}_{d}}$, such that
$\mathcal{B}$ is knowledge-consistent and ${\textrm{s}_{d}}$ always follows
dominant, current-state decisive possible-worlds strategies, and if
${\textsf{s}_{t}}$ achieves $\psi$ up to $n$, also ${\textrm{s}_{d}}$ does.

We first determine the set of actions $\textit{Act}(B)$ that an autonomous-
decisive system can choose when currently having the belief
$B=\\{{r}_{1},\ldots,{r}_{n}\\}\in\mathbb{B}$. An action $a$ can only be
chosen by a doxastic strategy of an autonomous-decisive system, if it is
chosen by a dominant, current-state decisive possible-worlds strategy
$\textsf{s}_{\textsf{p}}$ for the current states of $B$ (cf. 3.5). Note that
there may be several dominant possible-worlds strategies for $B$. We build a
single reality ${r}_{B}$ by the disjoint union of all alternative realities
${r}_{B}:=((\dot{\bigcup}_{r_{i}}\\{\textit{S}_{i}\\},\dot{\bigcup}_{r_{i}}\textit{Ed}_{i},\dot{\bigcup}_{r_{i}}\mathit{L}_{i},\dot{\bigcup}_{r_{i}}\textit{I}_{i}),\dot{\bigcup}_{r_{i}}\\{{\textit{S}_{c}}_{i}\\})$.
If necessary, we can make the realities disjoint by renaming their states but
keeping their structure. In order to judge how well a current-state decisive,
possible-worlds strategy has to perform in order to be dominant, we determine
the maximal $n_{\textit{m}}$ up to which $\psi$ can be achieved by any
possible-worlds strategy. Therefore, we check whether we can synthesize a
strategy in ${r}_{B}$ that achieves $\psi$ up to $n_{\textit{m}}=n$ down to
$n_{\textit{m}}=0$, if necessary [22]. Note that in the worst case only the
trivial goal true, i.e. $n_{\textit{m}}=0$, can be achieved. In order to check
whether $a$ is chosen by a dominant, current-state decisive strategy, we first
check whether $a$ is enabled at all current states of ${r}_{B}$. If $a$ is
enabled, we make $a$ the only choice at the current states. Therefore, we
build the modified Kripke structure ${r}_{B,a}$. We replace all arcs from the
current states of ${r}_{B}$ that are not labelled with $a$ by arcs leading to
$\textit{s}_{\textsf{undef}}$. If we can synthesize a strategy ${r}_{B,a}$
that achieves $\psi$ up to $n_{\textit{m}}$, $a$ is a current-state choice of
that current-state decisive, possible-worlds strategy. By iterating over all
actions, we collect the set of the actions Act($B$).

In order to judge how well the doxastic strategy ${\textrm{s}_{d}}$ has to
perform, we determine the maximal $n_{\textit{m}}$ up to which $\psi$ can be
achieved by any $\mathcal{O}$-truth-observing strategy in ${{W}}_{D}$. If
$n_{\textit{m}}<n$, then there is no ($\mathcal{B}$,${\textrm{s}_{d}}$) such
that $\mathcal{S}$ achieves $\psi$ up to $n$. Hence let $n\leq
n_{\textit{m}}$. We build the modified Kripke structure ${{W}}_{D}^{\prime}$
as follows. If ${{W}}_{D}$ has an $a$-labelled arc from a state s labelled, we
keep it only if there is a belief $B\in\mathbb{B}$ with
$a\in{\textit{Act}(B)}$ and $B\models\mathit{L}_{\mathbb{K}}(\textit{s})$ [8].
Otherwise, we redirect the arc to $\textit{s}_{\textsf{undef}}$. We synthesize
a dominant strategy ${\textsf{s}_{t}}$ on ${{W}}_{D}^{\prime}$ [22]. We derive
the belief formation $\mathcal{B}$ from ${\textsf{s}_{t}}$ by
$\mathcal{B}(h):=B$ for a belief $B$ with
${\textsf{s}_{t}}(h)\in\textit{Act}(B)$. We define ${\textrm{s}_{d}}$ to be
the doxastic strategy defined by
${\textrm{s}_{d}}(\bar{\mathcal{B}}(h)):={\textsf{s}_{t}}(h)$. In case
${\textsf{s}_{t}}$ achieves $n$, $\mathcal{S}$ is an autonomous-decisive
system. Otherwise the truth-observing strategies perform better. $\square$

##  4 Related and Future Work

Epistemology is the theory of knowledge and concerned with information-
processing and cognitive success [11, 25]. Doxastic means “relating to belief”
[10]. By using the term “doxastic”, we want to stress that our formalism
focuses on beliefs. Note in particular that an alternative reality can vary
arbitrarily from the ground truth ${{W}}_{D}$, and a HAS does not necessarily
believe that the ground truth is even possible. In the epistemic logic
literature, the semantics of doxastic languages are often given via _doxastic
models_ , that are special Kripke structures [13]. A doxastic model
$(S,v,\rightarrow_{i})$ consists of a set of nodes $S$ representing possible
worlds $w$, a valuation function $v:S\rightarrow 2^{\textit{{AP}}}$ for the
set of atomic facts AP and a belief relation $\rightarrow_{i}$ for each player
$i$, that specifies “$i$ deems $w^{\prime}$ possible in $w$” if “$w$
$\rightarrow_{i}$ $w^{\prime}$”. With other words, the belief of $i$ at $w$ is
defined as the worlds accessible via the agent $i$’s belief relation,
$\rightarrow_{i}$ [13, 20]. In this paper, we use complex possible worlds
instead of the plain nodes of a Kripke structure. Our alternative realities
encode the believed histories, the current states and possible futures. A HAS
uses alternative realities to simulate its strategy in order to decide on its
current action. In our framework, a reality constitutes an extensive form two-
player zero-sum game, where the winning condition is defined by the list of
LTL goals. While the possible-world strategies have perfect information on the
beliefs, the belief formation, which we also regard as a strategy, is based on
partial observations and the currently available knowledge/hard beliefs.

A couple of epistemic temporal logics have been suggested for specifying
aspects of knowledge throughout time for multi-agent systems. These logics
combine temporal logics with knowledge operators, like KCTL [5], KCTL∗ or
HyperCTL${}^{*}_{lp}$ [7]. They are interpreted over Kripke structures. But
since an agent $i$ has its local view, only certain propositions are assumed
to be observable, so that an observational equivalence relation $\sim_{i}$ on
the traces arises. “Agent $i$ knows $\varphi$” then means that $\varphi$ holds
on all $i$-equivalent initial traces. The alternating time temporal logics
(ATL) [2] has been developed for reasoning about what agents can achieve by
themselves or in groups throughout time. In ATL, the path quantifiers of CTL
are replaced by modalities that allow to quantify paths in the control of
groups of agents. ATL is interpreted over concurrent game structures (CGS),
which are labelled state transition systems. By adding a knowledge operator,
ATL has been extended to an epistemic variant, ATEL [16]. To this end the
concurrent game is extended by an observational equivalence relation per agent
modelling the agent’s limited view. In contrast to be above logics, a BLTL
formula is interpreted on a belief $B$, i.e. a set of alternative realities.
Since the set of possible beliefs $\mathbb{B}$ is finite, a formula
$\mathsf{K}\varphi$ means the finite conjunction $\bigwedge_{{r}\in
B}{r}\models\varphi$. But just like the logics above, we assume that a HAS can
only partially observe the ground truth – our doxastic strategies cannot
distinguish between histories that are observational equivalent. Our beliefs,
however, cannot straightforwardly be expressed in terms of an equivalence on
the ground truth, since an alternative reality may be a distinct Kripke
structure and a belief does not have to include the ground truth.

The field of epistemic planning is concerned with computing plans (“a finite
succession of events” [19]) that achieve the desirable state of knowledge from
a given current state of knowledge [6]. DEL, dynamic epistemic logic, is a
formalism to describe planning tasks succinctly by a semantic and action model
based approach. Epistemic models capture the knowledge state of the agents,
and epistemic action models describe how these are transformed. An evolution
results from a stepwise application of the available actions. In [19]
distributed synthesis of observational-strategies for multiplayer games are
considered. While ATEL and DEL allow for reasoning about a combination of
knowledge and strategies, we are interested in the belief _formation_. We ask
whether there exists a belief formation that justifies a strategy that
successfully achieves temporal goals within a given ground truth world.

Properties of belief formation are studied in the field of belief revision and
update. Belief revision is done when a new piece of information contradicts
the current information, and it aims to determine a consistent belief set.
Belief updates may be necessary when the world is dynamic [14]. The works in
this field are concerned with rational belief formation, following e.g. some
guiding principle like making minimal changes [14]. In our work, we consider
very general belief formation functions, since we focus on HASs. The belief of
a HAS may be determined by a composition of different components, and there
may not necessarily be an entity that ensures that the resulting belief is
rational. We imagine that during the design, requirements regarding the
rationality might be specified. So, approaches examining whether an
appropriate belief formation exists might be valuable tools for the
development of HASs.

BDI agents are rational agents with the mental attitudes of belief (B), desire
(D) and intention (I) [23]. Beliefs describe what information the agent has,
desires represent the agent’s motivational state and specify what the agent
would like to achieve, while intentions represent the currently chosen course
of action. These attitudes allow an agent balancing between deliberation about
its course of action and its commitment to the chosen course of action. In our
framework, an agent deliberates about its course of action at each state. We
do not enforce commitment to a certain course of action, as we are interested
in whether some belief formation exists. Nevertheless, the framework
conceptually allows capturing notions of commitment, and we plan to examine
these in future work. Basically, a chosen action represents a set of believed
best possible world strategies. These can be considered as the current intent.
So, a notion of commitment could require that (some) strategies of the
previous belief are still best strategies in the current belief. An engineer
may then specify when a HAS should be committed.

In this paper, we call a system autonomous-decisive, if it can choose its
actions based on its belief content, i.e., when it always chooses actions that
it believes can be extended to a best strategy. The concept that an agent
adjusts its actions following the believed most promising strategy is
certainly not new. For instance in [26], Wang et al. present an approach to
motion planning for autonomous cars in competitive scenarios. Ego solves
iteratively several rounds of trajectory optimization, whose fixed point
represents a Nash equilibrium in the trajectory space of all cars. In [3], a
two player game with communication is considered, and a generic framework is
defined that uses belief revision techniques to take the communication into
account. Player B makes announcements and then player A revises its
preferences by analysing what its best response would be.

Although we motivated our term of _autonomous-decisive_ by referring mostly to
HASs, we think the term is not limited to systems of a high level of autonomy,
like level 3 to 5 of the norm SAE J3016. Our notion characterizes how a system
takes decisions, while the SAE levels classify the interaction between driver
and system. A lot of works characterize notions of autonomous systems. For
instance, [15] focuses on the challenges of a foundation for autonomous
systems. According to the authors, autonomous behaviour embodies five
autonomous behavioural functions: perception, model update, goal management
and planning and self-adaptation. They further state that decision-making is a
central aspect and at the very heart of autonomous system engineering. In this
paper, we clearly focus on decision-making. The paper [27] explores the
intelligence and system foundations of autonomous systems. According to the
authors, autonomy aggregates hierarchically from reflexive, imperative and
adaptive intelligence. They consider autonomy as a property that enables a
system to change their behaviour in response to unanticipated events during
operation (thereby following [28]) and “without human intervention” (following
[17]). Our notion of autonomous-decisiveness ensures that no human
intervention is necessary for the decision-making. As our ego can only
partially observe the world, one might argue that behaviour is unexpected,
when observations of the ground truth do not match with the extrapolation of
prior beliefs. When ego adjusts its beliefs and adopts its behaviour, it hence
autonomously adjusts to unexpected events. We rather envision a different
research emphasis to approach his topic. In order to characterize ego’s
ability to adjust to unexpected events, we envision to develop notions of
strategic/belief formation robustness that specify when an application domain
differs too much from the envisioned design time domain to allow ego taking
autonomous decisions.

Moreover, we plan to use the framework to tackle the question “What is
relevant for the HAS?”, capturing the trade-off between observations and
knowledge when the belief formation is given.

##  5 Conclusion

In this paper, we are concerned with safety critical systems that autonomously
assess their situation and decide what to do based on this assessment. Such
HASs operate in overwhelmingly complex environments and have to deal with
partial observability and distorted perceptions. They construct an inner
representation of the world that is based on insights of the world and
develops over time, when new observations are made. We develop a doxastic
framework in order to formalize, what it means that such a system autonomously
takes decisions. In contrast to automatic systems, that decide based on their
beliefs how to play out pre-determined strategies, a system decides
autonomously, if it chooses an action that is justified by extrapolation of
the system’s beliefs. Given a prioritized list of LTL goals, a given design
context modelled as Kripke structure and given it has been decided on the
build-in knowledge and the system’s possible beliefs, it is decidable whether
a belief can be formed that enables a system to autonomously achieve its goals
and we can synthesize a witness. We consider this work as a start to examining
belief formation with respect to HAS’s strategic success.

#### Acknowledgements

I like to thank the anonymous reviewers for their valuable comments.

## References

  * [1]
  * [2] Rajeev Alur, Thomas A. Henzinger & Orna Kupferman (2002): _Alternating-Time Temporal Logic_.  J. ACM 49(5), p. 672–713, 10.1145/585265.585270.
  * [3] Guillaume Aucher, Bastien Maubert, Sophie Pinchinat & François Schwarzentruber (2015): _Games with Communication: From Belief to Preference Change_.  In: PRIMA 2015: Principles and Practice of Multi-Agent Systems, Springer, pp. 670–677, 10.1007/978-3-319-25524-8_50.
  * [4] Christel Baier & Joost-Pieter Katoen (2008): _Principles of Model Checking_ , chapter 5, pp. 229–239.  The MIT Press.
  * [5] Mario Benevides, Carla Delgado, Carlos Pombo, Luis Lopes & Ricardo Ribeiro (2008): _A Compositional Automata-based Approach for Model Checking Multi-Agent Systems_.  Electronic Notes in Theoretical Computer Science 195, pp. 133–149, 10.1016/j.entcs.2007.08.030.  Proc. of the Brazilian Symposium on Formal Methods (SBMF 2006).
  * [6] Thomas Bolander (2017): _A Gentle Introduction to Epistemic Planning: The DEL Approach_.  In: Proc. of the 9th Workshop on Methods for Modalities, M4M@ICLA 2017, EPTCS 243, pp. 1–22, 10.4204/EPTCS.243.1.
  * [7] Laura Bozzelli, Bastien Maubert & Sophie Pinchinat (2015): _Unifying Hyper and Epistemic Temporal Logics_.  In: Foundations of Software Science and Computation Structures, Springer, pp. 167–182, 10.1007/978-3-662-46678-0_11.
  * [8] Edmund M Clarke, Orna Grumberg & Doron A. Peled (1999): _Model checking_.  MIT Press, 10.1002/9780470050118.ecse247.
  * [9] Werner Damm & Bernd Finkbeiner (2011): _Does It Pay to Extend the Perimeter of a World Model?_ In: FM 2011: Formal Methods, Springer, pp. 12–26, 10.1007/978-3-642-21437-0_4.
  * [10] Collins English Dictionary (2022): _doxastic_.  Available at www.collinsdictionary.com/de/worterbuch/englisch/doxastic.
  * [11] Collins English Dictionary (2022): _epistemics_.  Available at www.collinsdictionary.com/de/worterbuch/englisch/epistemics.
  * [12] Ronald Fagin, Joseph Y. Halpern, Yoram Moses & Moshe Y. Vardi (2003): _Reasoning About Knowledge_.  MIT Press, 10.7551/mitpress/5803.001.0001.
  * [13] Paolo Galeazzi & Emiliano Lorini (2016): _Epistemic logic meets epistemic game theory: a comparison between multi-agent Kripke models and type spaces_.  Synthese 193(7), pp. 2097–2127, 10.1007/s11229-015-0834-x.
  * [14] Peter Gärdenfors (1992): _Belief Revision_ , chapter Belief Revision: An Introduction, pp. 1–28.  Cambridge University Press, 10.1017/CBO9780511526664.001.
  * [15] David Harel, Assaf Marron & Joseph Sifakis (2020): _Autonomics: In search of a foundation for next-generation autonomous systems_.  Proceedings of the National Academy of Sciences 117(30), pp. 17491–17498, 10.1073/pnas.2003162117.
  * [16] Wiebe van der Hoek & Michael Wooldridge (2002): _Tractable Multiagent Planning for Epistemic Goals_.  In: Proc. of the 1st Int. Joint Conference on Autonomous Agents and Multiagent Systems: Part 3, AAMAS ’02, Association for Computing Machinery, p. 1167–1174, 10.1145/545056.545095.
  * [17] Ming Hou, Simon Banbury & Catherine Burns (2014): _Intelligent Adaptive Systems: An Interaction-Centered Design Perspective_.  CRC Press, 10.1201/b17742.
  * [18] Timothy B. Lee: _Self-driving cars – How terrible software design decisions led to Uber’s deadly 2018 crash_.  Available at arstechnica.com/cars/2019/11/how-terrible-software-design-decisions-led-to-ubers-deadly-2018-crash.
  * [19] Bastien Maubert, Aniello Murano, Sophie Pinchinat, François Schwarzentruber & Silvia Stranieri (2020): _Dynamic Epistemic Logic Games with Epistemic Temporal Goals_.  CoRR abs/2001.07141, 10.3233/FAIA200088.
  * [20] John-Jules Ch. Meyer (2003): _Modal Epistemic and Doxastic Logic_.  In: Handbook of Philosophical Logic, Springer, pp. 1–38, 10.1007/978-94-017-4524-6_1.
  * [21] Dorde Petrovic, Radomir Mijailovic & Dalibor Pesic (2020): _Traffic Accidents with Autonomous Vehicles: Type of Collisions, Manoeuvres and Errors of Conventional Vehicles’ Drivers_.  Transport Infrastructure and systems in a changing world. Towards a more sustainable, reliable and smarter mobility. TIS Roma 2019 Conference Proceedings 45, pp. 161–168, 10.1016/j.trpro.2020.03.003.
  * [22] A. Pnueli & Roni Rosner (1989): _On the synthesis of a reactive module_.  Automata Languages and Programming 372, pp. 179–190, 10.1145/75277.75293.
  * [23] Anand S. Rao & Michael P. Georgeff (1998): _Decision Procedures for BDI Logics_.  Journal of Logic and Computation 8(3), pp. 293–343, 10.1093/logcom/8.3.293.
  * [24] David Romero, Peter Bernus, Ovidiu Noran, Johan Stahre & Åsa Fast-Berglund (2016): _The Operator 4.0: Human Cyber-Physical Systems & Adaptive Automation Towards Human-Automation Symbiosis Work Systems_.  In: Advances in Production Management Systems. Initiatives for a Sustainable World, Springer, pp. 677–686, 10.1007/978-3-319-51133-7_80.
  * [25] The University of Sheffield (2021): _Epistemology_.  Available at www.sheffield.ac.uk/philosophy/research/themes/epistemology.
  * [26] Mingyu Wang, Zijian Wang, John Talbot, J. Christian Gerdes & Mac Schwager (2021): _Game-Theoretic Planning for Self-Driving Cars in Multivehicle Competitive Scenarios_.  IEEE Transactions on Robotics 37(4), pp. 1313–1325, 10.1109/TRO.2020.3047521.
  * [27] Yingxu Wang, Konstantinos N. Plataniotis, Sam Kwong, Henry Leung, Svetlana Yanushkevich, Fakhri Karray, Ming Hou, Newton Howard, Rodolfo A. Fiorini, Paolo Soda, Edward Tunstel, Jianmin Wang & Shushma Patel (2019): _On Autonomous Systems: From Reflexive, Imperative and Adaptive Intelligence to Autonomous and Cognitive Intelligence_.  In: 2019 IEEE 18th International Conference on Cognitive Informatics & Cognitive Computing, pp. 7–12, 10.1109/ICCICC46617.2019.9146038.
  * [28] David Watson & David Scheidt (2005): _Autonomous systems_.  Johns Hopkins APL Technical Digest (Applied Physics Laboratory) 26, pp. 368–376.  Available at www.jhuapl.edu/Content/techdigest/pdf/V26-N04/26-04-Watson.pdf


# Lithium-Ion Battery Charging Schedule Optimization to Balance
Battery Usage and Degradation

Jacob Azoulay and Nico Carballal
Stanford University
AA222: Engineering Design Optimization
<EMAIL_ADDRESS>—<EMAIL_ADDRESS>

###### Abstract

> This work optimizes a lithium-ion battery charging schedule while
> considering a joint revenue and battery degradation model. The study extends
> the work of Meheswari et. al. to encourage battery usage/charging at optimal
> intervals depending on energy cost forecasts. This paper utilizes central
> difference Nesterov momentum gradient descent to come to optimal charging
> strategies and deal with the non-linearities of the battery degradation
> model. This optimization strategy is tested against constant, random varied
> price forecasts and a novel Gaussian process cost forecasting model.
> Contrary to many other papers regarding battery charging, formulating
> schedule optimization as a multivariate optimization problem provides
> meaningful insight to the inherent balance between these two competing
> objectives.

## Problem Statement

With increased electrification of devices and machinery used in our daily
lives, there is an increased importance placed on energy storage, usage
efficiency, and replenishment. Batteries are ubiquitous, varying in size,
capacity, and type. In an ideal world, appliances that run on batteries would
be able to transfer 100% of their energy to power the device. Furthermore, the
batteries would hold a maximal charge with no leakage overtime and the maximum
charge capacity would not degrade over the lifetime of the battery. An ideal
battery would also be capable of instantly recharging.

Of course, batteries are prone to inefficiencies; however, it is possible to
optimize battery life, performance, and recharging time within certain
constraints. The primary optimization objective considered in this paper is
battery degradation, which is influenced primarily by charge rate and state of
charge (SOC). Furthermore, to formulate a comprehensive model which encourages
battery use, a competing energy cost minimization objective will be
introduced, transforming the problem into a multi-objective optimization
problem.

Various related works have been conducted analyzing the relationship between
several battery performance specifications. Lei et al., for instance,
determined a tradeoff between lithium-ion battery degradation rate and energy
loss using first order approximations of energy dissipation [1]. Similarly,
Maheshwari et al. determine a battery degradation model that can be used to
predict battery performance depending on specified battery parameters [2].
Several other papers analyze the correlation between battery performance and
battery material, usage environment, and various other factors [3] [4]. Even
factors such as weather [5] and general maintenance [6] have been examined in
context of battery performance.

## Motivation

While much research has been conducted in maximizing battery efficiency, very
few papers have developed a robust model of short or long term degradation of
lithium-ion batteries, let alone consider battery degradation in the first
place. The study performed in this paper is greatly inspired by the work of
Maheshwari et al. which introduced a lithium-ion battery degradation model
based on empirical data and testing. Our paper, however, attempts to solve the
proposed problem using different optimization approaches which are robust to
non-linearities in the model [2].

Long term battery capacity degradation for lithium-ion batteries can be
attributed to exogenous factors, such as environment temperature and age, and
endogenous factors, such as SOC and operating current. Because oftentimes
external factors contributing to battery degradation are more difficult to
control for, this paper only considers internal factors when modeling the
degradation.

Maheshwari et al. use experimental data of Sony US18650V3 lithium-ion
batteries, pictured in Figure 1, to demonstrate the correlation between
capacity degradation and charge rate [2]. Additionally, the paper showed the
interwoven non-linear dependence between SOC, charge rate, and degradation.
Because batteries are typically retired when their maximum capacity decreases
to 80%, better understanding these relationships will help model and optimize
for prolonging battery lifetimes.

Figure 1: Two lithium-ion Sony US18650V3 batteries examined in this study [2].

## Approach

The goal of our project is to determine a battery charging/usage schedule that
minimizes the long-term battery capacity degradation and the overall cost of
charging the battery while still using the battery. As such, the problem will
be modeled as a multi-objective non-linear optimization problem. To formulate
a charging schedule, a finite time horizon between one-half day to two days,
discretized into one-hour time steps, will be considered. At each time step,
the design variables are charge (or discharge) rate $P_{t}^{b}$ for that given
time interval. The final model output will be a sequence of charge rates
which, if implemented at each corresponding time step, will minimize battery
capacity degradation and minimize the cost of charging the battery according
to the objective function.

The objective function of interest will be formulated as follows:

$f(\textbf{P})=w_{C}\times C+(1-w_{C})\times D$ (1)

where $C$ is total cost specified in the Cost Model Section, $D$ is total
degradation specified in the Battery Degradation Model section, $w_{C}$ is the
cost weighting factor, and $1-w_{C}$ is the degradation weighting factor. The
goal is to minimize both cost and degradation. A Pareto frontier can then be
produced by sweeping through various values of $w_{C}\in[0,1]$.

### Battery Degradation Model

Because the charging schedule is composed of discrete time steps, total
degradation $D$ will be the sum of the degradation experienced at each time
step:

$D=\sum_{t}^{T}d_{t}$

where $d_{t}$ represents the degradation at time $t\in\\{1,...,T\\}$.

The degradation model described below is inspired by [2]. Maheshwari et. al
have relevant tables and a much more in-depth description of each variable.
This paper matches the conventions used by [2].

The SOC of the battery is updated at each time interval depending on the SOC
of the previous state and on the total charge.

$SOC_{t}=SOC_{t-1}+\frac{P_{t}^{b}\times\Delta T}{V_{nom}\times I_{1C}}$

$P_{t}^{b}$ is the battery charge rate at time $t$, $\Delta T$ is the time
interval of each step, $V_{nom}$ is the nominal operating voltage assumed to
be constant, and $I_{1C}$ is the battery’s 1C rate also assumed to be
constant. Values for $\Delta T$, $V_{nom}$, and $I_{1C}$ used in this study
are tabulated in Table 1.

Parameter |  Value
---|---
$\Delta T$ |  1 hr
$V_{nom}$ |  3.7 V
$I_{1C}$ |  2.15 A
$P^{b,max}$ |  5 W
Table 1: Model parameters assumed in this study.

To preserve battery health, manufacturers often recommend charging below a
maximum charging rate $P^{b,max}$. Additionally, by definition, a battery’s
SOC must lie between zero and one-hundred percent. As such, $P_{t}^{b}$ and
SOC will be constrained such that

  * •

$\lvert P_{t}^{b}\rvert\leq P^{b,max}=5W$

  * •

$0\leq SOC_{t}\leq 100$

for all $t$.

Degradation for the battery considered in this study is highly dependant on
SOC at the time of charge. For instance, charging a battery from $80\%$ to
$100\%$ will result in greater degradation than charging the battery from
$40\%$ to $60\%$ assuming the charge rate is constant. Because the degradation
scheme is highly non-linear and battery specific, the degradation at varying
SOC has been determined experimentally by Maheshwari et al. [2]. The values
recorded assume a constant current rate of 1C. The degradation at a 1C rate
$d_{t}^{1C}$ at intermediate SOC can thus be interpolated from the recorded
data.

To facilitate the evaluation of $d_{t}^{1C}$, the authors of [2] developed a
cumulative distribution graph from which $d_{t}^{1C}$ can easily be
calculated. The graph in Figure 2 is a function of SOC on the x-axis and
cumulative degradation on the y-axis. The equation to extract $d_{t}^{1C}$ is:

$d_{t}^{1C}=\lvert\delta_{t}^{1C}-\delta_{t-1}^{1C}\rvert$

Figure 2: Cumulative degradation function determined experimentally to
calculate $d_{t}^{1C}$.

The obtained $d_{t}^{1C}$ value must then be scaled depending on current
$i_{t}$. Higher current leads to higher degradation, therefore a scaling
factor $\psi_{t}$ correlated to current is introduced, accounting for this
dependence. At $i_{t}=0$ (0C), $\psi_{t}=0$, indicating no degradation at zero
load. At a current rate of 1C, $\psi_{t}=1$ by definition. Determined
experimentally, $\psi_{t}=1.2956$ at a current rate of 2C. The model will
estimate intermediary values of $\psi_{t}$ using linear interpolation. The
graph of $\psi_{t}$ as a function of current rate can be seen in Figure 3. The
mathematical formulations are as follows:

$i_{t}=\frac{\lvert P_{t}^{b}\rvert}{V_{nom}\times I_{1C}}$

$\psi_{t}(i_{t})=\begin{cases}i_{t}&\text{if }0\leq i\leq 1\\\
1+0.2956i_{t}&\text{if }1\leq i\leq 0\end{cases}$

Figure 3: Current dependent scaling factor $\psi$ determined experimentally.
Intermediary values for $\psi$ are calculated using linear interpolation.

Final degradation incurred $d_{t}$ is determined using the following equation:

$d_{t}=\left(\frac{d_{t}^{1C}+\psi_{t}}{2}\right)^{2}-\left(\frac{d_{t}^{1C}-\psi_{t}}{2}\right)^{2}$

### Cost Model

The cost model from the objective function is formulated to encourage battery
usage

$C=\sum_{t}^{T}P_{t}^{b}\times\lambda_{t}$

where $P_{t}^{b}$ is the power to/from the battery during a trading interval.
A trading interval, $t,$ is a period of time in which the price of energy,
$\lambda_{t}$, is fixed. For this paper, trading intervals of an hour are
considered — meaning that prices are discretely changed at every hour
interval.

Because energy usage is inherently inefficient, an inefficiency factor,
$\eta=.95$, is selected such that $P_{t}^{b,ch}=\eta P_{t}^{m,ch}$ and
$P_{t}^{b,dis}\eta=P_{t}^{m,dis}$, where $P_{t}^{m}$ is the power input/output
of the market and $P_{t}^{b}$ is the power input/output directly of the
battery.

This cost model necessitates the price of energy over the entire trading
period, $T$, at each trading interval, $\lambda_{t}$. A baseline constant
price, $\lambda_{t}=p_{const}$ is tested first to ensure proper convergence.
Next, random prices are tested. Lastly, a Gaussian Process fitting and
sampling strategy is tested in the next section to predict and optimize to
real data.

### Cost Model Prediction

The application of Gaussian processes for energy forecasting has been well-
studied to allow for more advanced energy management techniques [7][8].

Given previous days’ energy price data, this paper aims to model the next
day’s forecast for energy prediction while also quantifying uncertainty in the
prediction [9]. For a given current hour $h_{i}$, we accumulate the previous
$m$ data points, $\boldsymbol{H}=[h_{i-m},\dots,h_{i-1}]$ for hourly energy
usage in MW, $\boldsymbol{E}=[E_{i-m},\dots,E_{i-1}]$, from [10]. We aim to
predict the next $n$ hours, $\boldsymbol{H^{*}}=[h_{i},\dots,h_{i+n}]$, energy
usage to base our optimization on
$\boldsymbol{\hat{E}}=[\hat{E_{i}},\dots,\hat{E_{i+n}}]$ along with
quantifying our uncertainty.

The posterior distribution of our model can be formulated as follows:

$\displaystyle\boldsymbol{\hat{E}}\mid\boldsymbol{E}\sim\mathcal{N}(\boldsymbol{\mu}),\boldsymbol{\Sigma})$
(2)

where $\boldsymbol{\mu}$ and $\boldsymbol{\Sigma}$ are defined as:

$\displaystyle\boldsymbol{\mu}=m(\boldsymbol{H^{*}})+K(\boldsymbol{H^{*}},\boldsymbol{H})K(\boldsymbol{H},\boldsymbol{H})^{-1}(\boldsymbol{E}-m(\boldsymbol{H}))$
$\displaystyle\boldsymbol{\Sigma}=K(\boldsymbol{H^{*}},\boldsymbol{H^{*}})-K(\boldsymbol{H^{*},\boldsymbol{H}})K(\boldsymbol{H},\boldsymbol{H})^{-1}K(\boldsymbol{H},\boldsymbol{H^{*}})$

$m(X)$ is the mean function, which represents prior knowledge about the
function. In this, we encode the information about the previous $m$ hours. For
our purpose, we utilize the mean of the previous days’ energy prices to
predict the mean of the next days’ energy prices. For a time step, $k>i$, the
prediction would look like,

$\displaystyle
m(X_{k})=\frac{\sum_{j=i-m}^{i}E_{j}[h_{k}==h_{j}]}{\sum_{j=i-m}^{i}1[h_{k}==h_{j}]}$

$K(X,X^{*})$ is the kernel function, which controls smoothness of the
function. It is constructed to measure the relation between different input
values. Since energy usage is periodic in nature, with a period occurring
every 24 hours, consideration must be taken for both the relationship of the
periodic data while placing higher priority on recent data. With this in mind,
we utilize the locally periodic kernel function from [11].

$SQ_{exp}(x,x^{\prime})=exp\left(-\frac{(x-x^{\prime})^{2}}{2\times
l_{exp}^{2}}\right)$
$K(x,x^{\prime})=\sigma^{2}exp\left(\frac{-2sin^{2}(\pi|x-x^{\prime}|/\rho)}{l_{per}^{2}}\right)SQ_{exp}(x,x^{\prime})$
(3)

where $l_{exp}=24$, $l_{per}=\frac{3}{7}$, $\rho=24$, $\sigma=1000$. The
$\rho$ value of $24$ illuminates that energy cycle usage have periods of 24
hours, and the $\sigma$ value of $1000$ accounts for the magnitude of values
in the energy usage dataset we utilize which tracks energy usage in MW for
every hour [10]. After fitting a Gaussian model to predict the next day’s
energy usage, we scale this proportionately to create a model for energy
prices, $p$, based on simple supply-and-demand:
$\hat{p}[\frac{\$}{kWh}]=\frac{\hat{E}}{80000}$ and
$p[\frac{\$}{kWh}]=\frac{E}{80000}$.

Figure 4: Demonstrates the general trend of the locally periodic kernel.

This formulation allows for two important results:

  1. 1.

Uncertainty grows smallest when closest to the last recorded data (i.e. the
prediction at i will be most confident).

  2. 2.

Uncertainty and mean have a periodic relation with values from the previous
days

### Curve Sampling

Sampling is done according to Equation 2 with
$\mathcal{N}(\boldsymbol{\mu},\boldsymbol{\Sigma})$. In order to require a
smoother fit, numpy’s polynomial fitting toolbox [12] is used to fit the
sampled data to a $n^{th}$ order polynomial. This was attempted along with
utilizing scipy’s curve fitting toolbox [13] to a sinusoidal function.
Ultimately, polynomial fitting was chosen to allow for locally periodic
behavior as modelled by the kernel definition.

As can be seen in Figure 5, samples for the next two days can deviate slightly
but follow a locally periodic trend. The most variation occurs near
$h_{i}=48$, where the fewest measured values are near. Given the definition
for the Kernel function, this is to be expected.

Figure 5: Given the previous three days of energy prices (depicted above), a
Gaussian process is constructed using the defined Kernel: $K(X,X^{\prime})$,
and five samples were collected and plotted (below) according to
$\mathcal{N}(\mu,\boldsymbol{\Sigma})$. Note the higher variance the farther
from $h_{0}$ and the general periodic trend.

### Consumer Modelling

There are two types of consumers to consider, the average consumer, and the
risk-averse consumer. The average consumer will optimize over the predicted
mean, $\boldsymbol{\mu}$, calculated from the Gaussian process while the risk-
averse consumer will take $n_{s}$ samples and optimize over the worst case. An
example of the risk-averse consumer is shown in Figure 6.

Figure 6: Risk-Averse Consumer Sampling chooses to optimize over the sample
for the worst case situation: $n_{s}$ = 10

### Optimization Methods

The multi objective function $f(\textbf{P})$ as defined in Equation 1 is a
non-linear and non-differentiable function. These properties largely arise
because of the quadratic function to calculate $d_{t}$ and the experimentally
determined piece-wise functions for $d_{t}^{1C}$ and $\psi_{t}$. Furthermore,
absolute value functions create cusps at which the function is non-
differentiable. As a result, optimization methods requiring analytical
gradients cannot be used. While linear programming, which in many cases can
find true global optima, could be viable if the model were linearized like in
[2], doing so would obfuscate the nonlinear intricacies introduced by the
model.

Moreover, the optimization method must consider the constraints on $P_{t}^{b}$
and $SOC_{t}$ discussed in the previous sections.

The model ultimately achieved best results using central difference Nesterov
momentum gradient descent with a quadratic constraint penalty. While
computationally expensive considering the high dimensional design space,
numerical gradient calculation is quite accurate and relatively
straightforward to apply even to non-linear and non-differentiable functions.
The quadratic penalty method further simplifies the problem by transforming a
constrained optimization problem to an unconstrained one. The resulting
objective function is as follows:

$\min_{\textbf{P}}f(\textbf{P})+\rho\times p_{q}(\textbf{P})$ (4)

where P is the $12$ dimensional design variable, $f(\textbf{P})$ is the
original multi-objective as formulated in Equation 1, $\rho$ is the penalty
scaling factor and $p_{q}(\textbf{P})$ is the quadratic penalty calculation,
which is formulated below.

$p_{q}(\textbf{P})=\sum_{t}^{T}\max(SOC_{t}-100,0)^{2}+\min(SOC_{t},0)^{2}+\max(\lvert
P_{t}^{b}\rvert-P^{b,max},0)^{2}$ (5)

Through experimentation with hyperparameters, it was found that this
optimization method converged in about 1000 iterations. To avoid becoming
stuck at local optima, several trials were conducted with randomly initialized
starting points.

## Results

### Baseline

The baseline method to which results will be compared is conducted assuming
constant energy prices. The preliminary results are also a good indication of
a properly implemented model and optimization method. These results are
plotted in Figure 7.

Depending on the weighting factor $w_{C}$, the output charging schedule varies
greatly. When $w_{C}=0.0$, the model reduces to a single objective
optimization problem, with the only aim of minimizing battery degradation. As
a result, the intuitive yet trivial proposed charging schedule is to never
charge or discharge, resulting in zero degradation and a static SOC.

The other extreme, when $w_{C}=1.0$, transforms the model to a sole cost
minimizing function. The proposed charging schedule results in completely
discharging the battery by the end of the twelfth time interval. In order to
incentivize energy usage in the model, negative cost is incurred (equivalent
to gaining revenue) when the battery is discharged. The amount received is
$\eta\times\lambda_{t}$ where $\eta$ is less than $1.0$ and $\lambda_{t}$ is
the price of energy ($\frac{\$}{kWh}$) at time $t$. As such, under the
assumption of constant prices, discharging and charging back to the same SOC
will result in a positive cost. Thus, to gain the most revenue, the battery
must completely discharge any existing energy and never charge during the 12
time steps. This behavior is represented in Figure 7.

Lastly, setting $w_{C}$ to an intermediate value between $0.0$ and $1.0$
results in a charging schedule that attempts to optimize for both degradation
and cost.

It is important to note that multiple global optima can exist. For instance,
once again assuming constant prices, if $w_{C}$ is set to $1.0$ then a
charging schedule that discharges completely in one time step results in an
equivalent cost outcome to a charging schedule that discharges one twelfth of
the initial SOC at each of the twelve time steps.

Figure 7: Baseline SOC schedule and energy prices with constant prices for
three weighting factors. $w_{C}$ represents the weight placed on cost.

Apart from visualizing individual charging schedules proposed by the model, a
Pareto frontier curve can be generated by sweeping through various weighting
values corresponding to cost $C$ and degradation $D$. Figure 8 shows the curve
corresponding to the optimal objective function $f(\textbf{P})$ evaluations
for a given weight $w_{C}$ (and correspondingly a given weight
$w_{D}=1.0-w_{C}$). The point corresponding to $w_{C}=0.0$ shows zero incurred
cost and zero degradation, matching the respective constant charging schedule
in Figure 7.

To formulate using economics terminology, points on the frontier lie on a
curve of equal utility. That is, no points are dominated by any other point as
defined by Kochenderfer [9]. Moving along the curve is a matter of preference.

Figure 8: Baseline Pareto frontier with constant prices for various weighting
factors. $w_{C}$ represents the weight placed on cost.

### Varied Prices

While evaluating performance on a baseline model provides insight into how the
model operates, it is not the most representative of true energy prices. The
subsequent results relax the assumption of constant prices, producing proposed
charging schedules and a Pareto frontier.

Figure 9, like with the baseline model, shows three proposed charging
schedules for weights of $w_{C}=0.0,0.5,$ and $1.0$. For the $w_{C}=0.0$ case
in which only degradation is optimized for, the model dictates to never charge
or discharge. Regardless of what the energy prices may be, this will always be
the optimal charging strategy with this weighting factor.

The $w_{C}=1.0$ case, in which only cost is optimized for, demonstrates
extreme fluctuations in charge. More interestingly, the model takes advantage
of the lower energy prices and suggests to maximally charge during these
intervals. When energy prices increase, as in $t=5$, the battery is greatly
discharged, likely limited only by maximum power output $P_{b,max}$. During
intervals of high prices, discharging results in relatively higher revenue
gained than when prices are low. Then when prices are low, the model
encourages charging as a smaller cost is incurred.

The intermediate case of $w_{C}=0.5$ weights both cost and degradation
equally. As a result, the proposed charging strategy is a less aggressive
version than the one when $w_{C}=1.0$ and a more aggressive version than the
one when $w_{C}=0.0$.

Figure 9: Pareto frontier with randomly varied prices for various weighting
factors. $w_{C}$ represents the weight placed on cost.

Finally, the corresponding Pareto frontier can be seen in Figure 10.

Figure 10: Pareto frontier with randomly varied prices for various weighting
factors. $w_{C}$ represents the weight placed on cost.

### Predicted Prices

Utilizing the Gaussian Process model and treating the consumer as a risk-
averse consumer, we take $n_{s}=10$ samples and optimize over the worst case
scenario as shown in Figure 6. For this case, we optimize over the next 24
hours of predicted energy prices to emulate the real-world situation of having
to optimize and plan for the full next day of energy. The sampled prediction
is shown in Figure 11. Note, hour $h_{0}$ does not correlate to midnight. It
is a randomly chosen hour on any given day.

Figure 11: Worst Case sample for next 24 hours given previous 3 days of
energy, $n_{s}=10$

The results shown in Figure 12 demonstrate the extreme cases of $w_{c}=1.0$
and $w_{c}=0.0$, and it exemplifies the middle case of $w_{c}=0.56$. Similar
trends to the varied price schedule is demonstrated in Figure 9, where
charging is considered when future prices will be higher.

To exemplify the effect of changing $w_{c}$ even more drastically, Figure 13
is provided. The Pareto frontier curve is also provided in Figure 14.

Figure 12: Optimization of Worst Case Sample, $n_{s}=10$. Charging is shown to
be promoted for higher $w_{c}$ values when future prices are going to be
higher. Figure 13: Optimization of Worst Case Sample for several $w_{c}$
values. Higher values of $w_{c}$ are shown to prioritize charging more
aggressively while lower values are more cautious about battery degradation
which matches the optimization function defined in Equation 1. Figure 14:
Pareto Frontier Curve for Worst Case Optimization over a 24-hour Trading
Period.

## Discussion

From the results, it is evident that utilizing central difference Nesterov
momentum gradient descent is applicable for a variety of different cost
forecasts. For the situation in which costs remain constant, charging is
inefficient if the revenue function is considered as ”buying” and ”selling
back” to the market. Due to the $\eta$ inefficiency factor, $P_{t}^{b,ch}=\eta
P_{t}^{m,ch}$ and $\eta P_{t}^{b,dis}=P_{t}^{m,dis}$. Therefore, with constant
prices, it never makes sense to charge, regardless of the $w_{c}$ value as
revenue will be negative and the battery will degrade. Figure 7 demonstrates
this phenomenon, with the battery only discharging over the entire time
interval.

For the varied price forecast and the worst-case realistic price forecast,
charging is prioritized when future prices are predicted to be higher. An
intuitive manner of understanding this is that the buyer is ”buying” the
energy at a lower price and ”selling” it back to the market at a higher price.
If the price difference is large enough to overcome the $\eta$ inefficiency
factor, the buyer will still be encouraged to buy and then sell. This can be
seen in Figure 9 and Figure 12.

The Gaussian price modelling provides an important extension to the work of
[2]. By introducing uncertainty into the model, optimization can be done for
battery charging in the future. The locally periodic kernel of [11] proves to
be an effective way to model the periodic, varying pattern of costs over
24-hour cycles. The sampling performed over Gaussian distributions for future
costs simulates different cost forecasts, and different types of consumers can
choose how to optimize given those samples.

## Conclusion

This work extends the work done by [2]. The degradation model used by [2] in
conjunction with the revenue model (with associated inefficiencies) is an
effective manner to balance battery upkeep and encourage battery usage at
optimal intervals.

Instead of utilizing linearization techniques as [2] does, this paper utilizes
central difference Nesterov momentum gradient descent to come to optimal
charging strategies. Despite the large state space and high computation time,
this strategy proves effective in coming up with charging strategies for the
next $n$ trading intervals given knowledge of the cost forecast. Utilizing
baseline and randomly varied prices, charging strategies were demonstrated to
match intuition.

The cost forecast model was completed utilizing Gaussian Processes. The
utilization of a locally periodic kernel captures the periodic, yet varying,
structure of energy prices over 24-hour cycles. The formulated Gaussian
Process distribution is then sampled over and fit to a polynomial in order to
sample over the next $n$ trading intervals. This is shown to be an effective
manner of capturing future uncertainty for prices. Different types of
consumers can utilize the uncertainty of this specified Gaussian Process
distribution to decide how to proceed.

The results of the SOC schedule and energy price visualizations and the Pareto
frontier plots demonstrate the balance between battery degradation and the
revenue model. Point along the Pareto frontier can be thought of as values of
equal utility, in that no points are dominated by any other point. This
specification further allows adaptability for persons who have varying
priority of revenue vs. battery degradation depending on the use case.

## Future Work

As mentioned in [2], more work can be done to create a battery degradation
model as optimization focuses on battery usage have seldom considered this
important factor of the equation.

Furthermore, this work can be extended upon to integrate further optimization
over the generated Gaussian Process samples, instead of choosing just one
sample and optimizing over that. Applying a gradient measurement strategy from
[9] could allow for optimization while directly measuring and adapting to the
uncertainties of the future.

## Group Member Contributions

Jacob:

  * •

Implemented battery degradation model in Python

  * •

Added functionality for quadratic penalty method

  * •

Programmed finite differences calculation and gradient descent functions

  * •

Tuned hyperparameters for optimal performance

  * •

Produced graphs

Nico:

  * •

Experimented with kernels for Gaussian Process Model

  * •

Implemented GPM for energy prices

  * •

Integrated GPM model with optimization methods

  * •

Produced Graphs

## Appendix

A link to our GitHub can be found here.

## References

  * [1] Y. Lei, C. Zhang, Y. Gao, and T. Li, “Charging Optimization of Lithium-ion Batteries Based on Capacity Degradation Speed and Energy Loss,” Energy Procedia, vol. 152, pp. 544–549, Oct. 2018.
  * [2] A. Maheshwari, N. G. Paterakis, M. Santarelli, and M. Gibescu, “Optimizing the operation of energy storage using a non-linear lithium-ion battery degradation model,” Applied Energy, vol. 261, p. 114360, Mar. 2020.
  * [3] H. Fayaz, A. Afzal, A. D. M. Samee, M. E. M. Soudagar, N. Akram, M. A. Mujtaba, R. D. Jilte, M. T. Islam, U. Agbulut, and C. A. Saleel, “Optimization of Thermal and Structural Design in Lithium-Ion Batteries to Obtain Energy Efficient Battery Thermal Management System (BTMS): A Critical Review,” Archives of Computational Methods in Engineering, vol. 29, pp. 129–194, Jan. 2022.
  * [4] A. Masias, J. Marcicki, and W. A. Paxton, “Opportunities and Challenges of Lithium Ion Batteries in Automotive Applications,” ACS Energy Letters, vol. 6, pp. 621–630, Feb. 2021.
  * [5] A. Gharehghani, J. Gholami, P. Shamsizadeh, and S. Mehranfar, “Effect analysis on performance improvement of battery thermal management in cold weather,” Journal of Energy Storage, vol. 45, p. 103728, Jan. 2022.
  * [6] “The factors that impact ups battery life, https://www.sure-power.com/2013/01/factors-of-ups-battery-life/,” Jan. 2013.
  * [7] F. Lubbe, J. Maritz, and T. Harms, “Evaluating the Potential of Gaussian Process Regression for Solar Radiation Forecasting: A Case Study,” Energies, vol. 13, p. 5509, Oct. 2020.
  * [8] J. F. Lubbe, “Evaluating the Potential of Gaussian Process Regression for Data-driven Renewable Energy Management,” p. 128.
  * [9] M. J. Kochenderfer, Algorithms for Decision Making.  MIT Press, 2022.
  * [10] “Hourly energy consumption, https://www.kaggle.com/robikscube/hourly-energy-consumption.”
  * [11] D. K. Duvenaud, “Automatic Model Construction with Gaussian Processes,” p. 157.
  * [12] C. R. Harris, K. J. Millman, S. J. van der Walt, R. Gommers, P. Virtanen, D. Cournapeau, E. Wieser, J. Taylor, S. Berg, N. J. Smith, R. Kern, M. Picus, S. Hoyer, M. H. van Kerkwijk, M. Brett, A. Haldane, J. F. del Río, M. Wiebe, P. Peterson, P. Gérard-Marchant, K. Sheppard, T. Reddy, W. Weckesser, H. Abbasi, C. Gohlke, and T. E. Oliphant, “Array programming with NumPy,” Nature, vol. 585, pp. 357–362, Sept. 2020.
  * [13] P. Virtanen, R. Gommers, T. E. Oliphant, M. Haberland, T. Reddy, D. Cournapeau, E. Burovski, P. Peterson, W. Weckesser, J. Bright, S. J. van der Walt, M. Brett, J. Wilson, K. J. Millman, N. Mayorov, A. R. J. Nelson, E. Jones, R. Kern, E. Larson, C. J. Carey, İ. Polat, Y. Feng, E. W. Moore, J. VanderPlas, D. Laxalde, J. Perktold, R. Cimrman, I. Henriksen, E. A. Quintero, C. R. Harris, A. M. Archibald, A. H. Ribeiro, F. Pedregosa, P. van Mulbregt, and SciPy 1.0 Contributors, “SciPy 1.0: Fundamental Algorithms for Scientific Computing in Python,” Nature Methods, vol. 17, pp. 261–272, 2020.