rule. The same result holds more generally for the class of maximum binary
constraint satisfaction problems (like Max-2SAT, Max Directed Cut, and
others). We have not made any attempt currently to optimize the exponent of
$\log n$ in the bound, but we believe that with a more careful analysis the
true exponent will be low. There are several interesting open questions raised
by this work. We list some of them below.

1\. Can our bounds be improved to polynomial? In the case of the 1-FLIP
algorithm in the full perturbation model (i.e. when all edges of $K_{n}$ are
perturbed) a polynomial bound was proved in [23]. Can a similar result be
shown for 2-FLIP and SWAP?

2\. Can our results be extended to the structured smoothed model, i.e., when
we are given a graph $G$ and only the edges of $G$ are perturbed? In the case
of 1-FLIP we know that this holds [22, 25], but 2-FLIP is much more
challenging.

3\. We saw in this paper how to analyze local search when one move flips
simultaneously two nodes. This is a qualitative step up from the case of
single flips, that creates a number of obstacles which had to be addressed.
This involved the introduction of nontrivial new techniques in the analysis of
the sequence of moves, going from sets to graphs. Dealing with local search
that flips 3 or more nodes will require extending the methods further to deal
with hypergraphs. We hope that our techniques will form the basis for handling
local search algorithms that flip multiple nodes in one move, e.g. $k$-FLIP
for higher $k$, and even more ambitiously powerful methods like Kernighan-Lin
that perform a deep search in each iteration and flip/swap an unbounded number
of nodes.

4\. Can our results be extended to Max $k$-Cut or $k$-Graph Partitioning where
the graph is partitioned into $k>2$ parts? In the case of 1-FLIP for Max
$k$-Cut quasi-polynomial bounds were shown in [24].

5\. Can similar results be shown for Max-CSP with constraints of higher
arities, for example Max 3SAT? No bounds are known even for 1-FLIP. In fact,
analyzing 1-FLIP for Max 3SAT seems to present challenges that have
similarities with those encountered in the analysis of 2-FLIP for Max 2SAT and
Max Cut, so it is possible that the techniques developed in this paper will be
useful also in addressing this problem.

##  Appendix A Missing Proofs from Section 2

See 2.3

###### Proof.

Note that $\tau_{i}(u)=\gamma_{i}(u)$, $\tau_{j}(u)=\gamma_{j}(u)$, and by
definition,
$\textsf{imprv}_{\tau_{0},\mathcal{S}}(i)=\textsf{imprv}_{\gamma_{0},\mathcal{S}}(i)^{*}$
is the projection of $\textsf{imprv}_{\gamma_{0},\mathcal{S}}(i)$ on
$E(\mathcal{S})$.

Thus, for any edge $e\in E(\mathcal{S})$, $w_{e}$ is the same as
$(\tau_{i}(u)\cdot\textsf{imprv}_{\tau_{0},\mathcal{S}}(i)-\tau_{j}(u)\cdot\textsf{imprv}_{\tau_{0},\mathcal{S}}(j))_{e}$.
For any edge $e\notin E(\mathcal{S})$, if $e=\\{v_{1},v_{2}\\}$ doesn’t
contain $u$, the improvement vectors are 0 on $e$ and correspondingly
$w[u,i,j]_{e}=0$. For the last case, let us assume $e=\\{u,v\\}$ where $v$ is
inactive. We have that

$\textsf{imprv}_{\gamma_{0},\mathcal{S}}(i)_{e}=\gamma_{i-1}(v)\gamma_{i-1}(u)=-\gamma_{i-1}(v)\gamma_{i}(u)\
\text{ \& }\
\textsf{imprv}_{\gamma_{0},\mathcal{S}}(j)_{e}=-\gamma_{j-1}(v)\gamma_{j}(u).$

Since $v$ is not active, $\gamma_{i}(v)=\gamma_{0}(v)$ for any $i\in[\ell]$.
So, we get that

$(\gamma_{i}(u)\cdot\textsf{imprv}_{\gamma_{0},\mathcal{S}}(i)-\gamma_{j}(u)\cdot\textsf{imprv}_{\gamma_{0},\mathcal{S}}(j))_{e}=-\gamma_{i-1}(v)+\gamma_{j-1}(v)=0.$

This finishes the proof of the lemma. ∎

See 2.9

###### Proof.

Again recall that $\tau_{i}(u)=\gamma_{i}(u)$, $\tau_{j}(u)=\gamma_{j}(u)$,
and by definition,
$\textsf{imprv}_{\tau_{0},\mathcal{S}}(i)=\textsf{imprv}_{\gamma_{0},\mathcal{S}}(i)^{*}$
is the projection of $\textsf{imprv}_{\gamma_{0},\mathcal{S}}(i)$ on
$E(\mathcal{S})$.

Thus, for edge $e\in E(\mathcal{S})$, $w[C]_{e}$ is the same as
$\sum_{j\in[t]}b_{j}\cdot\textsf{imprv}_{\tau_{0},\mathcal{S}}(c_{j})_{e}$.
For edge $e\notin E(\mathcal{S})$, if $e$ doesn’t contain $u_{i}$ for any
$i\in[t]$, the improvement vectors are 0 on $e$ and correspondingly
$w[C]_{e}=0$. For the last case, let us assume $e=(u,v)$ where $v$ is
inactive. Then we have (where index $0$ corresponds to $t$)

$\displaystyle\sum_{j\in[t]}b_{j}\cdot\textsf{imprv}_{\gamma_{0},\mathcal{S}}(c_{j})_{e}=$
$\displaystyle\sum_{i\in[t]:u_{i}=u}\Big{(}b_{i-1}\textsf{imprv}_{\gamma_{0},\mathcal{S}}(c_{i-1})_{e}+b_{i}\textsf{imprv}_{\gamma_{0},\mathcal{S}}(c_{i})_{e}\Big{)}$
$\displaystyle=$
$\displaystyle\sum_{i\in[t]:u_{i}=u}\Big{(}-b_{i-1}\gamma_{c_{i-1}-1}(v)\gamma_{c_{i-1}}(u_{i})-b_{i}\gamma_{c_{i}-1}(v)\gamma_{c_{i}}(u_{i})\Big{)}.$

Since $v$ is inactive,
$\gamma_{c_{i-1}-1}(v)=\gamma_{c_{i}-1}(v)=\gamma_{0}(v)$. Each term above is
equal to

$-\gamma_{0}(v)(b_{i-1}\gamma_{c_{i-1}}(u_{i})+b_{i}\gamma_{c_{i}}(u_{i}))=0.$

This finishes the proof of the lemma. ∎

##  Appendix B Rank Invariance of Improving vectors over Initial Configuration

In this section we prove that the rank of the improvement vectors for the set
of $\emph{1-move}(\mathcal{S})$, $\emph{2-move}(\mathcal{S})$,
$\textsf{arcs}(\mathcal{S})$ and $\textsf{cycles}(\mathcal{S})$ is independent
of the initial configuration $\gamma_{0}$ of the vertices.

###### Proof of Lemmas 2.4, 2.8 & 2.10.

We start by recalling the following useful facts:

######  Fact B.1.

Let $\gamma_{0},\gamma_{0}^{\prime}\in\\{\pm 1\\}^{n}$ be two arbitrary
initial configurations. Then, it holds that

$\gamma_{0}(v)\gamma_{0}^{\prime}(v)=\gamma_{i}(v)\gamma_{i}^{\prime}(v)\quad\text{
for any }i\in[\ell],$

where $\gamma_{i},\gamma_{i}^{\prime}$ is obtained from
$\gamma_{i-1},\gamma_{i-1}^{\prime}$ by flipping nodes in $\mathcal{S}_{i}$,
for a move sequence $\mathcal{S}=(\mathcal{S}_{1},\ldots,\mathcal{S}_{\ell})$.

######  Fact B.2.

Let $A$ be a $(k_{1}\times k_{2})$ real-valued matrix $A$ and $B,C$ are full-
rank $(k_{1}\times k_{1})$ and $(k_{2}\times k_{2})$ squared matrices
correspondingly. Then, it holds that
$\textsf{rank}(A)=\textsf{rank}(A^{\top})$ and
$\textsf{rank}(A)=\textsf{rank}(BAC)$.

Let
$\mathcal{M}_{\emph{$1$-move}}(\gamma_{0},\mathcal{S}),\mathcal{M}_{\emph{$2$-move}}(\gamma_{0},\mathcal{S})$
be the matrices whose columns are the improvement vectors of $1$-move for a
given initial configuration $\gamma_{0}$ and let
$\mathcal{M}_{\emph{$1$-move}}(\gamma_{0},\mathcal{S}),\mathcal{M}_{\emph{$2$-move}}(\gamma_{0},\mathcal{S})$
be the submatrices of
$\mathcal{M}_{\emph{$1$-move}}(\tau_{0},\mathcal{S}),\mathcal{M}_{\emph{$2$-move}}(\tau_{0},\mathcal{S})$
including only the rows which correspond to $E(\mathcal{S})$.

Schematically, we have that for the _1-move_ case:

$\mathcal{M}_{\emph{$1$-move}}(\tau_{0},\mathcal{S})=\begin{bmatrix}&\vdots&\\\
\cdots&(\textsf{imprv}_{\tau{0},\mathcal{S}}(\mathcal{S}_{k}=\\{u\\})_{e=\\{u,v\\}}=\tau_{k-1}(u)\tau_{k-1}(v)&\cdots\\\
&\vdots&\\\
\cdots&(\textsf{imprv}_{\tau{0},\mathcal{S}}(\mathcal{S}_{k}=\\{u\\})_{e=\\{z,w\\}}=0&\cdots\\\
&\vdots&\\\ \end{bmatrix}_{|E(\mathcal{S})|,|\emph{1-move}(\mathcal{S})|}$

and for the _2-move_ case:

$\mathcal{M}_{\emph{$2$-move}}(\tau_{0},\mathcal{S})=\begin{bmatrix}&\vdots&\\\
\cdots&(\textsf{imprv}_{\tau{0},\mathcal{S}}(\mathcal{S}_{k^{\prime}}=\\{u,v\\})_{e=\\{u,v\\}}=0&\cdots\\\
\cdots&(\textsf{imprv}_{\tau{0},\mathcal{S}}(\mathcal{S}_{k^{\prime}}=\\{u,v\\})_{e=\\{u,z\\}}=\tau_{{k^{\prime}}-1}(u)\tau_{{k^{\prime}}-1}(z)&\cdots\\\
\cdots&(\textsf{imprv}_{\tau{0},\mathcal{S}}(\mathcal{S}_{k^{\prime}}=\\{u,v\\})_{e=\\{v,w\\}}=\tau_{{k^{\prime}}-1}(v)\tau_{{k^{\prime}}-1}(w)&\cdots\\\
&\vdots&\\\
\cdots&(\textsf{imprv}_{\tau{0},\mathcal{S}}(\mathcal{S}_{k^{\prime}}=\\{u,v\\})_{e=\\{z,w\\}}=0&\cdots\\\
&\vdots&\\\ \end{bmatrix}_{|E(\mathcal{S})|,|\emph{2-move}(\mathcal{S})|}$

Notice that we can derive
$\mathcal{M}_{\emph{$1$-move}}(\tau_{0}^{\prime},\mathcal{S}),\mathcal{M}_{\emph{$2$-move}}(\tau_{0}^{\prime},\mathcal{S})$
by multiplying
$\mathcal{M}_{\emph{$1$-move}}(\tau_{0},\mathcal{S}),\mathcal{M}_{\emph{$2$-move}}(\tau_{0},\mathcal{S})$
from left by the squared diagonal $|E_{n}|\times|E_{n}|$ matrix
$\mathcal{D}[\tau_{0},\tau_{0}^{\prime}]$ such that

$\mathcal{D}[\tau_{0},\tau_{0}^{\prime}]_{(e,e)=((u,v),(u,v))}=\tau_{0}(u)\tau_{0}^{\prime}(u)\tau_{0}(v)\tau_{0}^{\prime}(v)\text{
and }\mathcal{D}[\tau_{0},\tau_{0}^{\prime}]_{(e,e^{\prime})}=0\text{ for
$e\neq e^{\prime}$.}$

Indeed, we have that for an entry $(e,k)$ representing an edge $e=(u,v)$ and
the $k$-th $\mu$-move

$\displaystyle(\mathcal{D}[\tau_{0},\tau_{0}^{\prime}]\mathcal{M}_{\emph{$\mu$-move}}(\tau_{0},\mathcal{S}))_{e,k}$
$\displaystyle=$
$\displaystyle\begin{cases}\tau_{0}(u)\tau_{0}^{\prime}(u)\tau_{0}(v)\tau_{0}^{\prime}(v)\tau_{k}(u)\tau_{k}(v)&\text{if
}\mathcal{M}_{\emph{$\mu$-move}}(\tau_{0},\mathcal{S}))_{e,k}=\tau_{k}(u)\tau_{k}(v)\\\
0&\text{if
}\mathcal{M}_{\emph{$\mu$-move}}(\tau_{0},\mathcal{S}))_{e,k}=0\end{cases}$
$\displaystyle\overset{\footnotesize Fact~{}\ref{fact:config-invariance}}{=}$
$\displaystyle\begin{cases}\tau_{k}(u)\tau_{k}^{\prime}(u)\tau_{k}(v)\tau_{k}^{\prime}(v)\tau_{k}(u)\tau_{k}(v)&\text{if
}\mathcal{M}_{\emph{$\mu$-move}}(\tau_{0},\mathcal{S}))_{e,k}=\tau_{k}(u)\tau_{k}(v)\\\
0&\text{if
}\mathcal{M}_{\emph{$\mu$-move}}(\tau_{0},\mathcal{S}))_{e,k}=0\end{cases}$

Since $\tau_{i}(v)^{2}$ equals 1 for any $v\in V_{n}$ for every $i\in[\ell]$,
we get that

$\displaystyle(\mathcal{D}[\tau_{0},\tau_{0}^{\prime}]\mathcal{M}_{\emph{$\mu$-move}}(\tau_{0},\mathcal{S}))_{e,k}$
$\displaystyle=$
$\displaystyle\begin{Bmatrix}[l]\tau_{k}^{\prime}(u)\tau_{k}^{\prime}(v)&\text{if
}\mathcal{M}_{\emph{$\mu$-move}}(\tau_{0},\mathcal{S}))_{e,k}=\tau_{k}(u)\tau_{k}(v)\\\
0&\text{if
}\mathcal{M}_{\emph{$\mu$-move}}(\tau_{0},\mathcal{S}))_{e,k}=0\end{Bmatrix}=(\mathcal{M}_{\emph{$\mu$-move}}(\tau_{0}^{\prime},\mathcal{S}))_{e,k}$

for any $\mu\in\\{1,2\\}$. Since $\mathcal{D}[\tau_{0},\tau_{0}^{\prime}]$ is
a full-rank matrix, leveraging Fact B.2, the above argument proves that
$\textsf{rank}(\mathcal{M}_{\emph{$\mu$-move}}(\tau_{0},\mathcal{S}))$ is
independent of the initial configuration.

More interestingly, in order to prove Lemma 2.4, it suffices to prove that the
rank of the column matrix with the improvement vectors of arcs is independent
of the initial configuration. In fact, let

$M_{\textsf{arcs}(\mathcal{S})}(\tau_{0},\mathcal{S}))=\begin{bmatrix}\vdots&&\vdots&&\vdots\\\
\textsf{imprv}_{\tau_{0},\mathcal{S}}(\alpha_{1})&\cdots&\textsf{imprv}_{\tau_{0},\mathcal{S}}(\alpha_{k})&\cdots&\textsf{imprv}_{\tau_{0},\mathcal{S}}(\alpha_{|\textsf{arcs}(\mathcal{S})|})\\\
\vdots&&\vdots&&\vdots\end{bmatrix}$

By definition, we have that for any $\alpha\in\textsf{arcs}(\mathcal{S})$:

$\textsf{imprv}_{\tau_{0},\mathcal{S}}(\alpha)=\tau_{i}(u)\cdot\textsf{imprv}_{\tau_{0},\mathcal{S}}(i)-\tau_{j}(u)\cdot\textsf{imprv}_{\tau_{0},\mathcal{S}}(j)\in\mathbb{Z}^{E(\mathcal{S})},$

or equivalently
$M_{\textsf{arcs}(\mathcal{S})}(\tau_{0},\mathcal{S}))=\mathcal{M}_{\emph{$1$-move}}(\tau_{0},\mathcal{S}))\cdot\mathcal{T}(\tau_{0},\mathcal{S})$,
where $\mathcal{T}(\tau_{0},\mathcal{S})$ is a sparse
($|\emph{1-move}(\mathcal{S})|\times|\textsf{arcs}(S)|$) rectangular matrix
such that

$\mathcal{T}(\tau_{0},\mathcal{S})_{k-\text{th
\emph{1-move}},\alpha=(i,j)}=\begin{cases}(-1)^{\tfrac{(k-i)}{(j-i)}}\tau_{k}(u)&k\in\\{i,j\\}\\\
0&\text{otherwise}\end{cases},\text{ where $u$ is the corresponding node of
arc $\alpha$.}$

Schematically, we have that matrix ${\mathcal{T}(\tau_{0},\mathcal{S})}$
includes the
$(\tau_{i}(node(\alpha)),-\tau_{j}(node(\alpha)))_{\alpha=(i,j)\in\textsf{arcs}(\mathcal{S})}$
pairs expanded to $\\{0,\pm 1\\}^{\emph{1-move}(\mathcal{S})}$ .

$\footnotesize{\mathcal{T}(\tau_{0},\mathcal{S})}=\begin{bmatrix}0&\tau_{i}(node(\alpha_{1}=(i,j)))&0&\cdots&-\tau_{j}(node(\alpha_{1}=(i,j)))&0&\cdots&0\\\
\vdots&0&\vdots&\vdots&0&&&\vdots\\\ \vdots&\vdots&0&\vdots&\vdots&&&\vdots\\\
0&0&\tau_{i^{\prime}}(node(\alpha_{arcs(\mathcal{S})})=(i^{\prime},j^{\prime})))&0&\cdots&\tau_{i^{\prime}}(node(\alpha_{arcs(\mathcal{S})})=(i^{\prime},j^{\prime})))&0&0\end{bmatrix}^{\top}$

Again, notice that we can derive $\mathcal{T}(\tau_{0}^{\prime})$ by
multiplying $\mathcal{T}(\tau_{0})$ from right by the squared diagonal
$|\textsf{arcs}(S)|\times|\textsf{arcs}(S)|$ matrix $\mathcal{D^{\prime}}$
such that

$\mathcal{D}^{\prime}[\tau_{0},\tau_{0}^{\prime}]_{(\alpha,\alpha)=((i,j),(i,j))}=\tau_{0}(u)\tau_{0}^{\prime}(u)\text{
where $u$ is the node of $\alpha$ and
}\mathcal{D}^{\prime}[\tau_{0},\tau_{0}^{\prime}]_{(\alpha,\alpha^{\prime})}=0\text{
for $\alpha\neq\alpha^{\prime}$.}$

Indeed, we have that for an entry $(k,\alpha)$ representing an arc
$\alpha=(i,j)$ and the $k$-th $1$-move

$\displaystyle(\mathcal{T}(\tau_{0})\mathcal{D}^{\prime}[\tau_{0},\tau_{0}^{\prime}])_{k,\alpha}$
$\displaystyle=$
$\displaystyle\begin{Bmatrix}[l]\tau_{0}(u)\tau_{0}^{\prime}(u)\tau_{i}(u)=\tau_{i}(u)\tau_{i}^{\prime}(u)\tau_{i}(u)=\tau_{i}^{\prime}(u)&\text{if
}(\mathcal{T}(\tau_{0}))_{k,\alpha}=\tau_{i}(u)\\\
-\tau_{0}(u)\tau_{0}^{\prime}(u)\tau_{j}(u)=\tau_{j}(u)\tau_{j}^{\prime}(u)\tau_{j}(u)=-\tau_{j}^{\prime}(u)&\text{if
}(\mathcal{T}(\tau_{0}))_{k,\alpha}=-\tau_{j}(u)\\\ 0&\text{if
}(\mathcal{T}(\tau_{0}))_{k,\alpha}=0\end{Bmatrix}=(\mathcal{T}(\tau_{0}^{\prime}))_{k,\alpha}$

where first equality leverages Fact B.1 and the second one uses the fact
$\tau_{i}(v)^{2}$ equals 1 for any $v\in V_{n}$ for every $i\in[\ell]$. To
sum-up, it holds that

$\displaystyle M_{\textsf{arcs}(\mathcal{S})}(\tau_{0}^{\prime},\mathcal{S}))$
$\displaystyle=\mathcal{M}_{\emph{$1$-move}}(\tau_{0}^{\prime},\mathcal{S}))\cdot\mathcal{T}(\tau_{0}^{\prime},\mathcal{S})=\left(\mathcal{D}[\tau_{0},\tau_{0}^{\prime}]\mathcal{M}_{\emph{$1$-move}}(\tau_{0},\mathcal{S}))\right)\cdot\left(\mathcal{T}(\tau_{0},\mathcal{S})\mathcal{D}^{\prime}[\tau_{0},\tau_{0}^{\prime}]\right)$
$\displaystyle=\mathcal{D}[\tau_{0},\tau_{0}^{\prime}]\left(\mathcal{M}_{\emph{$1$-move}}(\tau_{0},\mathcal{S}))\right)\cdot\mathcal{T}(\tau_{0},\mathcal{S}))\mathcal{D}^{\prime}[\tau_{0},\tau_{0}^{\prime}]=\mathcal{D}[\tau_{0},\tau_{0}^{\prime}]M_{\textsf{arcs}(\mathcal{S})}(\tau_{0}^{\prime},\mathcal{S}))\mathcal{D}^{\prime}[\tau_{0},\tau_{0}^{\prime}]$

Given that $\mathcal{D}^{\prime}[\tau_{0},\tau_{0}^{\prime}]$ and
$\mathcal{D}[\tau_{0},\tau_{0}^{\prime}]$ are full-rank matrices, leveraging
Fact B.2, we can prove that the above argument proves that
$\textsf{rank}(\mathcal{M}_{\textsf{arcs}(S)}(\tau_{0},\mathcal{S}))$ is
independent of the initial configuration.

Now, in order to prove Lemma 2.8, we recall the definition of a dependent
cycle $C$ of size $t$, namely let
$C=\left(c_{1}=\\{u_{1},u_{2}\\},c_{2}=\\{u_{2},u_{3}\\}\ldots,c_{t}=\\{u_{t},u_{1}\\}\right)$
in a move sequence $\mathcal{S}$. For an initial configuration
$\tau_{0}\in\\{\pm 1\\}^{V(\mathcal{S})}$, we say that cycle is _dependent_
with respect to $\tau_{0}$ if there exists $b\in\\{\pm 1\\}^{t}$ such that

$\begin{bmatrix}\tau_{1}(u_{1})&0&\cdots&\cdots&0&\tau_{t}(u_{1})\\\
\tau_{1}(u_{2})&\tau_{2}(u_{2})&\cdots&\cdots&\cdots&0\\\
0&\tau_{2}(u_{3})&\tau_{3}(u_{3})&\cdots&\cdots&0\\\
\vdots&\vdots&\ddots&\ddots&\ddots&0\\\
\vdots&\vdots&\vdots&\ddots&\ddots&0\\\
0&0&0&0&\tau_{t-1}(u_{t})&\tau_{t}(u_{t})\end{bmatrix}\begin{bmatrix}b_{1}\\\
b_{2}\\\ \vdots\\\ \vdots\\\ \vdots\\\ b_{t}\end{bmatrix}=\begin{bmatrix}0\\\
\vdots\\\ \vdots\\\ \vdots\\\ \vdots\\\
0\end{bmatrix}\equiv\Delta(\tau_{0})\cdot b=0_{t}$

Again, notice that we can derive $\Delta(\tau_{0}^{\prime})$ by multiplying
$\Delta(\tau_{0})$ from left by the squared diagonal $|C|\times|C|$ matrix
$\mathcal{D^{\prime\prime}}$ such that

$\mathcal{D^{\prime\prime}}[\tau_{0},\tau_{0}^{\prime}]_{(u_{k},u_{k}^{\prime})}=\tau_{0}(u)\tau_{0}^{\prime}(u)\text{
for $k=k^{\prime}$ and
}\mathcal{D^{\prime\prime}}[\tau_{0},\tau_{0}^{\prime}]_{(u_{k},u_{k}^{\prime})}=0\text{
for $k\neq k^{\prime}$.}$

Indeed, we have that for an entry $(k,c_{i})$ representing a 2-_move_
$c_{i}=\\{u_{i\mod t},u_{i+1\mod t}\\}$ and the $u_{k}$-th node of the cycle
$C$:

$\displaystyle(\mathcal{D}^{\prime\prime}[\tau_{0},\tau_{0}^{\prime}]\Delta(\tau_{0}))_{k,c_{i}}$
$\displaystyle=$
$\displaystyle\begin{Bmatrix}[l]\tau_{0}(u_{k})\tau_{0}^{\prime}(u_{k})\tau_{i}(u_{k})=\tau_{i}(u_{k})\tau_{i}^{\prime}(u_{k})\tau_{i}(u_{k})=\tau_{i}^{\prime}(u_{k})&\text{if
}(\Delta(\tau_{0}))_{k,c_{i}}=\tau_{i}(u_{k})\\\ 0&\text{if
}(\Delta(\tau_{0}))_{k,c_{i}}=0\end{Bmatrix}=(\Delta(\tau_{0}^{\prime}))_{k,c_{i}}$

Since $\mathcal{D}^{\prime\prime}[\tau_{0},\tau_{0}^{\prime}]$ is full-rank
matrix, we get that
$\hbox{}(\Delta(\tau_{0}))=\hbox{}(\Delta(\tau_{0}^{\prime}))$. Therefore if
there exists a non-zero vector $b$ such that $\Delta(\tau_{0})\cdot b=0$ then
$\Delta(\tau_{0}^{\prime})\cdot b=0$ as well, completing the proof for Lemma
2.8.

For the last case of Lemma 2.10, we start by the following observations:

  1. 1.

If $\Delta(\tau_{0})\cdot b=0$, then for any $b^{\prime}=\lambda b$, it also
holds that $\Delta(\tau_{0})\cdot b^{\prime}=0$ for any non-zero $\lambda$
constant.

  2. 2.

If $\Delta(\tau_{0})\cdot b=0$ and $b_{k}=0$ for some $k\in[t]$, then $b$ is
the zero vector, $b=0$.

  3. 3.

More precisely, the vector that belong to the (right) null space of
$\Delta(\tau_{0})$, i.e., all the vectors $b$ such that $\Delta(\tau_{0})\cdot
b=0$, are of the following form:

$\Delta(\tau_{0})\cdot b=0\Leftrightarrow
b=b_{1}\cdot\left(1,-\frac{\tau_{c_{1}}(u_{2})}{\tau_{c_{2}}(u_{2})},\cdots,(-1)^{k-1}\frac{\prod_{i\in[2:k]}\tau_{c_{i-1}}(u_{i})}{\prod_{i\in[2:k]}\tau_{c_{i}}(u_{i})},\cdots,(-1)^{t-1}\frac{\prod_{i\in[2:t]}\tau_{c_{i-1}}(u_{i})}{\prod_{i\in[2:t]}\tau_{c_{i}}(u_{i})}\right)^{\top}$

  4. 4.

The term
$\frac{\prod_{i\in[2:k]}\tau_{c_{i-1}}(u_{i})}{\prod_{i\in[2:k]}\tau_{c_{i}}(u_{i})}$
is independent of the initial configuration.

Items (1)-(3) are simple linear algebras derivation. Item (4) holds since

$\frac{\prod_{i\in[2:k]}\tau_{c_{i-1}}(u_{i})}{\prod_{i\in[2:k]}\tau_{c_{i}}(u_{i})}=\frac{\prod_{i\in[2:k]}\tau_{c_{i-1}}(u_{i})}{\prod_{i\in[2:k]}\tau_{c_{i}}(u_{i})}\times\underbrace{\frac{\prod_{i\in[2:k]}\tau^{\prime}_{c_{i-1}}(u_{i})\tau_{c_{i-1}}(u_{i})}{\prod_{i\in[2:k]}\tau^{\prime}_{c_{i}}(u_{i})\tau_{c_{i}}(u_{i})}}_{=1\text{
from Fact~{}\ref{fact:config-
invariance}}}=\frac{\prod_{i\in[2:k]}\tau^{\prime}_{c_{i-1}}(u_{i})}{\prod_{i\in[2:k]}\tau^{\prime}_{c_{i}}(u_{i})}$

Hence, if $b$ is a cancelling vector with $b_{1}=1$, then from items
(1),(2),(3),(4) we have that $b$ is unique for every cycle $C$ and independent
initial configuration $\tau_{0}$.

More interestingly, in order to prove Lemma 2.10, it suffices to prove that
the rank of the column matrix with the improvement vectors of cycles is
independent of the initial configuration. In fact, let

$M_{\textsf{cycles}(\mathcal{S})}(\tau_{0},\mathcal{S}))=\begin{bmatrix}\vdots&&\vdots&&\vdots\\\
\textsf{imprv}_{\tau_{0},\mathcal{S}}(C_{1})&\cdots&\textsf{imprv}_{\tau_{0},\mathcal{S}}(C_{k})&\cdots&\textsf{imprv}_{\tau_{0},\mathcal{S}}(C_{|\textsf{cycles}(\mathcal{S})|})\\\
\vdots&&\vdots&&\vdots\end{bmatrix}$

By definition, we have that for any $C\in\textsf{cycles}(\mathcal{S})$:

$\textsf{imprv}_{\tau_{0},\mathcal{S}}(C=(c_{1},\cdots,c_{t}))=\sum_{j\in[t]}b_{j}(C)\cdot\textsf{imprv}_{\tau_{0},\mathcal{S}}(c_{j}).$

or equivalently
$M_{\textsf{cycles}(\mathcal{S})}(\tau_{0},\mathcal{S}))=\mathcal{M}_{\emph{$2$-move}}(\tau_{0},\mathcal{S}))\cdot\mathcal{B}(\mathcal{S})$
where $\mathcal{T}(\tau_{0},\mathcal{S})$ is a sparse
($|\emph{2-move}(\mathcal{S})|\times|\textsf{cycles}(S)|$) rectangular matrix
such that

$\mathcal{B}(\mathcal{S})_{\rho-\text{th
\emph{$2-$move}},C}=\begin{cases}b_{\rho}(C)&c_{\rho}\in C\\\
0&\text{otherwise}\end{cases},\text{ where $u$ is the corresponding node of
arc $\alpha$.}$

Schematically, we have that matrix ${\mathcal{B}(\mathcal{S})}$ includes the
$(b(C))_{C\in\textsf{cycles}(\mathcal{S})}$ vectors expanded to $\\{0,\pm
1\\}^{\emph{2-move}(\mathcal{S})}$ .

$\footnotesize{\mathcal{B}(\mathcal{S})}=\begin{bmatrix}0&b_{1}(C_{1})&0&b_{\rho}(C_{1})&0&b_{|C_{1}|}(C_{1})&0&\cdots&0\\\
b_{1}(C_{2})&0&\cdots&b_{\rho^{\prime}}(C_{2})&\vdots&0&\cdots&b_{|C_{2}|}(C_{2})&0\\\
&0&\cdots&&\vdots&&\cdots&&0\\\
b_{1}(C_{|\textsf{cycles}(\mathcal{S})|})&b_{\rho^{\prime\prime}}(C_{|\textsf{cycles}(\mathcal{S})|})&0&\cdots&\cdots&0&\cdots&b_{|C_{|\textsf{cycles}(\mathcal{S})}|}(C_{|\textsf{cycles}(\mathcal{S})|})&0\\\
\end{bmatrix}^{\top}$

Having noticed the above ones, it is easy to see that
$\textsf{rank}(\mathcal{M}_{\textsf{arcs}(S)}(\tau_{0},\mathcal{S}))$ is
independent of the initial configuration, since

$\displaystyle\mathcal{M}_{\textsf{arcs}(S)}(\tau_{0}^{\prime},\mathcal{S})$
$\displaystyle=\mathcal{M}_{\emph{$2$-move}}(\tau_{0}^{\prime},\mathcal{S})\cdot{\mathcal{B}(\mathcal{S})}=(\mathcal{D}[\tau_{0},\tau_{0}^{\prime}]\cdot\mathcal{M}_{\emph{$2$-move}}(\tau_{0},\mathcal{S})){\mathcal{B}(\mathcal{S})}$
$\displaystyle=\mathcal{D}[\tau_{0},\tau_{0}^{\prime}]\cdot(\mathcal{M}_{\emph{$2$-move}}(\tau_{0},\mathcal{S}){\mathcal{B}(\mathcal{S})})=\mathcal{D}[\tau_{0},\tau_{0}^{\prime}]\cdot\mathcal{M}_{\textsf{arcs}(S)}(\tau_{0},\mathcal{S}).$

Thus, by Fact B.2 we get that
$\textsf{rank}(\mathcal{M}_{\textsf{arcs}(S)}(\tau_{0},\mathcal{S}))=\textsf{rank}(\mathcal{M}_{\textsf{arcs}(S)}(\tau_{0}^{\prime},\mathcal{S}))$,
concluding also the proof of Lemma 2.10. ∎

## References

  * [1] Daniel A Spielman and Shang-Hua Teng.  Smoothed analysis of algorithms: Why the simplex algorithm usually takes polynomial time.  Journal of the ACM (JACM), 51(3):385–463, 2004.
  * [2] René Beier and Berthold Vöcking.  Random knapsack in expected polynomial time.  In Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, pages 232–241, 2003.
  * [3] Matthias Englert, Heiko Röglin, and Berthold Vöcking.  Smoothed analysis of the 2-opt algorithm for the general tsp.  ACM Transactions on Algorithms (TALG), 13(1):1–15, 2016.
  * [4] Heiko Röglin and Berthold Vöcking.  Smoothed analysis of integer programming.  Mathematical programming, 110(1):21–56, 2007.
  * [5] Daniel Dadush and Sophie Huiberts.  A friendly smoothed analysis of the simplex method.  In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, pages 390–403, 2018.
  * [6] Aditya Bhaskara, Moses Charikar, Ankur Moitra, and Aravindan Vijayaraghavan.  Smoothed analysis of tensor decompositions.  In Proceedings of the forty-sixth annual ACM symposium on Theory of computing, pages 594–603, 2014.
  * [7] Brendan Farrell and Roman Vershynin.  Smoothed analysis of symmetric random matrices with continuous distributions.  Proceedings of the American Mathematical Society, 144(5):2257–2261, 2016.
  * [8] Avrim Blum and John Dunagan.  Smoothed analysis of the perceptron algorithm for linear programming.  2002\.
  * [9] David Arthur, Bodo Manthey, and Heiko Röglin.  Smoothed analysis of the k-means method.  Journal of the ACM (JACM), 58(5):1–31, 2011.
  * [10] David Arthur and Sergei Vassilvitskii.  Worst-case and smoothed analysis of the icp algorithm, with an application to the k-means method.  In 2006 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS’06), pages 153–164. IEEE, 2006.
  * [11] Vidyashankar Sivakumar, Steven Wu, and Arindam Banerjee.  Structured linear contextual bandits: A sharp and geometric smoothed analysis.  In International Conference on Machine Learning, pages 9026–9035. PMLR, 2020.
  * [12] Shant Boodaghians, Joshua Brakensiek, Samuel B Hopkins, and Aviad Rubinstein.  Smoothed complexity of 2-player nash equilibria.  In 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS), pages 271–282. IEEE, 2020.
  * [13] Shant Boodaghians, Rucha Kulkarni, and Ruta Mehta.  Smoothed efficient algorithms and reductions for network coordination games.  In Thomas Vidick, editor, 11th Innovations in Theoretical Computer Science Conference, ITCS 2020, January 12-14, 2020, Seattle, Washington, USA, volume 151 of LIPIcs, pages 73:1–73:15. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020.
  * [14] René Beier, Heiko Röglin, Clemens Rösner, and Berthold Vöcking.  The smoothed number of pareto-optimal solutions in bicriteria integer optimization.  Mathematical Programming, pages 1–37, 2022.
  * [15] Lirong Xia.  The smoothed possibility of social choice.  Advances in Neural Information Processing Systems, 33:11044–11055, 2020.
  * [16] David S. Johnson, Cecilia R. Aragon, Lyle A. McGeoch, and Catherine Schevon.  Optimization by simulated annealing: An experimental evaluation; part i, graph partitioning.  Oper. Res., 37(6):865–892, 1989.
  * [17] M.R. Garey, D.S. Johnson, and L. Stockmeyer.  Some simplified np-complete graph problems.  Theor. Comput. Sci., pages 237–267, 1976.
  * [18] Brian W. Kernighan and Shen Lin.  An efficient heuristic procedure for partitioning graphs.  Bell Syst. Tech. J., 49(2):291–307, 1970.
  * [19] David S Johnson, Christos H Papadimitriou, and Mihalis Yannakakis.  How easy is local search?  Journal of Computer and System Sciences, 37(1):79–100, 1988.
  * [20] Alejandro A Schäffer and Mihalis Yannakakis.  Simple local search problems that are hard to solve.  SIAM journal on Computing, 20(1):56–87, 1991.
  * [21] Robert Elsässer and Tobias Tscheuschner.  Settling the complexity of local max-cut (almost) completely.  In International Colloquium on Automata, Languages, and Programming, pages 171–182. Springer, 2011.
  * [22] Michael Etscheid and Heiko Röglin.  Smoothed analysis of local search for the maximum-cut problem.  ACM Trans. Algorithms, 13(2):25:1–25:12, March 2017.
  * [23] Omer Angel, Sébastien Bubeck, Yuval Peres, and Fan Wei.  Local max-cut in smoothed polynomial time.  In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, pages 429–437. ACM, 2017.
  * [24] Ali Bibak, Charles Carlson, and Karthekeyan Chandrasekaran.  Improving the smoothed complexity of flip for max cut problems.  In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 897–916. SIAM, 2019.
  * [25] Xi Chen, Chenghao Guo, Emmanouil V. Vlatakis-Gkaragkounis, Mihalis Yannakakis, and Xinzhi Zhang.  Smoothed complexity of local max-cut and binary max-csp.  In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020, page 1052–1065, New York, NY, USA, 2020. Association for Computing Machinery.
  * [26] Charles M. Fiduccia and Robert M. Mattheyses.  A linear-time heuristic for improving network partitions.  In Proceedings of the 19th Design Automation Conference, pages 175–181. ACM/IEEE, 1982.
  * [27] Heiko Röglin.  The complexity of Nash equilibria, local optima, and Pareto optimal solutions.  PhD thesis, Aachen, Techn. Hochsch., Diss., 2008, 2008.


# A Surrogate Model Framework for Explainable Autonomous Behaviour

Konstantinos Gavriilidis  Heriot-Watt University
Edinburgh, United Kingdom
<EMAIL_ADDRESS>Andrea Munafo  SeeByte Ltd.
Edinburgh, United Kingdom
<EMAIL_ADDRESS>Wei Pang  Heriot-Watt University
Edinburgh, United Kingdom
<EMAIL_ADDRESS>Helen Hastie  Heriot-Watt University
Edinburgh, United Kingdom
<EMAIL_ADDRESS>
###### Abstract

Adoption and deployment of robotic and autonomous systems in industry are
currently hindered by the lack of transparency, required for safety and
accountability. Methods for providing explanations are needed that are
agnostic to the underlying autonomous system and easily updated. Furthermore,
different stakeholders with varying levels of expertise, will require
different levels of information. In this work, we use surrogate models to
provide transparency as to the underlying policies for behaviour activation.
We show that these surrogate models can effectively break down autonomous
agents’ behaviour into explainable components for use in natural language
explanations.

###### Index Terms:

Explainable Agents, Human-In-The-Loop Application, Surrogate Model, Feature
Contribution.

##  I Introduction

Robotic and autonomous systems are at the stage where we are seeing them being
adopted more frequently in a variety of environments, such as ground vehicles
for inspection of disaster sites, or underwater for pipeline inspection. It is
important that humans are kept in the loop in these operations and are able to
intervene as necessary. However, this comes with challenges, such as
underwater vehicles having limited bandwidth to broadcast updates [1].
Transparency and the ability to explain actions and decisions are key factors
for safety, accountability and adoption [2]. However, these are non-trivial to
implement, given the complexity of autonomous systems and the ‘blackbox’
nature of neural-based models.

Platform-specific explanation interfaces normally require a basic
understanding of an agent’s behaviour space ($B$), possible states ($S$) and
decision-making ($D$) to comprehend its capabilities and what could be
described to operators. Furthermore, user studies are necessary to recognise
which behaviours may be certainly valid and appropriate but might perhaps
confuse the operator. This can lead to mission aborts and inaccurate mental
models [3].

These user studies and explanation methods also need to adapt to the
stakeholder. The IEEE Standard for Transparency of Autonomous Systems (P7001)
[2], defines a number of stakeholder groups from the expert operator, to the
general public and lawmakers. They all require different types of information
and level of detail to be included in the explanation.

Furthermore when working with commercial entities, they are continuously
developing their autonomous models, adding new behaviours or states as
required for new use cases and customers. If we are to provide accurate, up-
to-date explanations, the explanation module will also need continuous
updating, requiring considerable time and effort.

Here, we propose a generic method using surrogate models for generating
autonomy-agnostic explanations that can be used without a deep understanding
of the underlying autonomy and can be easily updated. Specifically addressing
the following research questions:

  * •

RQ1: How robust are surrogate models in approximating a complex deterministic
agent’s policy for behaviour activation?

  * •

RQ2: Can these surrogate models be used to effectively generate explanations?

  * •

RQ3: How is the performance affected when going from simulated data to real
trials with real vehicles tested in a realistic environment?

Figure 1: Unmanned Surface Vehicles (USVs) Heron (left) and Philos (right)
used during the trials on Charles River in Boston.

For the remainder of this paper, in Section II we mention previous work, which
has impacted our approach and in Section III we describe our use case and the
explanation types that our framework provides. In Section IV, we describe the
functionality of components, such as the surrogate models or the feature
contribution estimators in the pipeline architecture. Finally, in Section V,
we report the performance of the surrogate models in simulations and how it is
affected during the trial or when new behaviours are incremented.

Figure 2: Empirical decision tree for behaviour activation derived by a domain
expert.

##  II Related Work

Explanation Frameworks: Explainable agency has been introduced as a trait of
robots to define what properties a transparent robot should have conceptually.
Among these traits are the ability to explain (i) plan generation, (ii)
executed actions and (iii) replanning in a user-friendly fashion [4]. Looking
at previous work on explainable agency, the whole process can be broken down
into three main parts, explanation generation, explanation communication and
explanation reception [5]. For explanation communication, previous studies
have looked into how robots could explain themselves as people do by including
reasons for intentional and causes for unintentional behaviours [6]. Further
studies investigate the desired verbosity of explanations in different
scenarios [7, 8] and various types of explanations, which can be provided to a
user from an explainable planning perspective [9].

Explainable Artificial Intelligence: The right of users to receive
explanations about a robot’s behaviour is supported by government regulations
and the recommended direction is the development of transparent robotics [2],
e.g. through the use of interpretable models [10]. Machine learning models
differ in terms of simulatability, decomposability and algorithmic
transparency [11]. In the case of opaque models, explanation methods should be
applied to them to disambiguate their functionality. Explanation methods fall
into two categories depending on the way they are applicable to a black-box
model, namely Model-specific and Model-agnostic [12]. Surrogate models can
belong to either category, depending on their intended use and are useful for
deriving the causality behind any prediction. LIME [13] accomplishes this by
locally approximating the model around a given prediction. SHAP [14] generates
Shapley values, which indicate the contribution of each feature to the
difference between the initial belief of a model and its actual prediction.
Another option to highlight causal relationships is through counterfactuals,
where several feature contributions can help the user understand the
relationship between feature values and the corresponding predictions [15].
However, surrogate models are not always consistent and, as a result,
robustness has been introduced as a metric that represents how stable
explanations are when inputs are slightly modified [16].

Explainable Robotics: In Sakai and Nagai [17], the relationship between XAI
and explanations for transparent robotics is defined. Existing work has
examined the use of both algorithmically transparent models and the
combination of opaque models with posthoc explanation methods to explain
robotic failures [18]. The decision-making of reinforcement learning agents
has also been explained either with the use of surrogate models [19, 20] or
the generation of Shapley values to explain robot grasping [21]. Focusing more
on explanation communication and reception, the studies in Thielstrom et al.
[22] and Robb et al. [23] present videos of robotic failures along with
explanations to users. Meanwhile, in Das et al. [24], natural language
explanations are generated with a Neural Translation Network to improve human
assistance in fault recovery. Each approach performed a corresponding user
study to evaluate how explanations affect the mental model of users.

Continuing our effort in [25], we have developed a framework that retrieves
data from deterministic agents and, with model selection, finds the optimal
classifier for behaviour prediction. Depending on the transparency of the
intermediate model, we capture the causality behind behaviours either by
directly analysing the model or with the application of a posthoc explainer.

Knowledge Representation and Verbalisation: Knowledge representations have
always played an important role in the unification or the completion of
knowledge for autonomous agents. In Li et al. [26], an ontology is used to
tackle the issue of information heterogeneity and to facilitate collaboration
between underwater robots. Additionally, in Gavriilidis et al. [27] an
ontology is used to relate sensor readings to hardware errors and make a new
plan, while a ROS listener retrieves and verbalises these outcomes with a
surface realiser. Furthermore, Suh et al. [28] use a multilayered ontology to
complement the perception of a household robot for object recognition and
assist with its localisation. At the same time, knowledge representations play
an important role in Natural Language Generation. In [29], a Neural Language
Model efficiently transforms Wikipedia infoboxes into biography summaries,
while in [30] a fine-tuned T5 model generates sentences just by connecting
plain utterances from concept sets. On the other hand, Ghosal [31] collected a
dialogue reasoning dataset, where additional context is incorporated into
utterances to teach a T5 model to make more intuitive transitions in dialogue.
This type of data-driven natural language generation is out of scope for the
work described here, but is clearly an area for future use, particularly with
the advent of more advanced large language models such as GPT-4 [32].

##  III Use Case and Explanation Types

The use case examined here is a hybrid autonomy, that combines a ROS-based
deterministic agent with a reactive agent, prioritising behaviours through
multi-objective optimization for the maritime domain. Specifically, our
scenarios focus on Unmanned Surface Vehicles (USV) and Autonomous Underwater
Vehicles (AUV), as illustrated in Figure 1. This work was done in
collaboration with industry partner SeeByte Ltd, who have developed an
autonomous agent for driving such vehicles for a variety of maritime
applications, such as inspection. To have an initial understanding of the
autonomous agent and how it selects a behaviour, we interviewed in-depth a
domain expert from the company. From this interview, we derived an abstract
definition of behaviour decision-making in a tree format. This empirical
decision tree is illustrated in Figure 2.

We then investigated if this behaviour tree covers aspects of a mission in
simulation ahead of the real trial. The simulation scenario involves a
restricted coastal area on the River Charles in Boston, where two vehicles
collaborate to complete a mission. The versatile USV Heron performs each
objective according to the uploaded plan, while USV Philos inspects the area
to detect obstacles and notifies the other vehicle if something out of the
plan is found. Each mission contains a launch and recovery objective and a
number of survey or target objectives, where the vehicle needs to hold its
position for a default amount of time. Additionally, the obstacles are either
static (with locations specific to each mission but there for the duration),
or dynamic (i.e. appearing during the mission). In terms of capabilities, both
vehicles support 6 behaviours B = (wait, transit, survey, hold_position,
replanned_transit, avoid_obstacle) and they both run two autonomy models
simultaneously (one for each vehicle) in a master-slave architecture.

The following explanation types were derived in consultation with the expert
and captured in the empirical decision tree in Figure 2 and are listed here.

  1. E.1

Behaviour Causality describes how a robot selects its current behaviour or
action. Especially for operators, it can be difficult to comprehend how a
robot closely observes objects around it, updates its world model and acts
according to its goals. The utterances of this explanation usually entail the
name of the behaviour, its use and the cause of activation. Answers question:
Why did you do that?

  2. E.2

Replanning Clarification complements the previous category and covers cases
where unexpected outcomes arise and force the autonomy to alter its plan. Some
indicative examples are obstacle avoidance and platform integrity, where for
safety reasons the robot has to make a stop in a new location. Answers
question: Why do I need to replan at this point?

  3. E.3

Counterfactual Explanation allows the operator to ask the autonomy how it
would react if its internal state changed in a specific way. With this
functionality, the user can learn about alternative outcomes at any given
point and to better comprehend the underlying logic of the autonomous agent.
Answers question: What if?

##  IV Method

The overall pipeline architecture that goes from the autonomous vehicle to the
explanation interface is illustrated in Figure 3. Its aim is to act as a
wrapper application that does not disrupt the existing autonomy but clearly
conveys the approximated policy to users. For the ROSListening component, we
found the relevant ROS topics that provide the vehicle states needed to
predict exhibited behaviours (per the behaviour definition in Figure 2). We
then created a listener with two uses in mind: (i) data collection in
simulation and (ii) online behaviour prediction during plan execution. Using
the acquired data, we trained a number of classifier models as surrogate
autonomy models. These models predict which of the 6 behaviours the vehicle is
exhibiting. We investigated a number of classifiers with varying transparency
and compared the accuracy of the models.

If the highest accuracy model is transparent, we would directly extract the
feature contribution for each behaviour prediction. Otherwise, a post-hoc
explanation method would be applied to the opaque model to derive feature
contribution. Here, we examine both of these options. Finally, a knowledge
representation that contains this information is generated and fed into a
rule-based natural language explanation generator that conveys the same
content in a user-friendly format. These components are described in detail
below and represented in Algorithm 1.

Figure 3: Illustration of the proposed pipeline architecture, where a
Surrogate Model approximates agent policy and Feature Contribution is
estimated to detect behaviour causality. The output of this framework is an
explanation with content which originates from a Contextualised Concept Set.

1

Input: $\mathcal{UP}$: User Preference.

Input: $\mathcal{SD}$: State Dataset.

Output: $\mathcal{IKR}$: Intermediate Knowledge Representation.

Output: $\mathcal{SV}$: State Verbalisation.

2 begin

3 $\mathcal{UC}\leftarrow$ SelectUseCase($\mathcal{UP}$)

4 $D\leftarrow$ SplitAndEncode($\mathcal{SD},\mathcal{UP}$)

5 $\mathcal{M}\leftarrow$ TrainModel($\mathcal{D},\mathcal{UP}$)

6 $\mathcal{E}\leftarrow$ ConfigureExplainer($\mathcal{M},\mathcal{UP}$)

7 $s\leftarrow$ StartExecution($\mathcal{UC}$)

8

9 while  _not $s$ $\leftarrow$ $\emptyset$_ do

10 $p\leftarrow M$.Predict($s$)

11 $e\leftarrow E$.ExplainPrediction($p$)

12 $r\leftarrow$.GenerateRepresentation($p,e$)

13 $v\leftarrow$.VerbaliseRepresentation($r$)

14

15 if  _$\mathcal{UC}\leftarrow$ isFinished_ then

16 $i$ $\leftarrow\emptyset$

17 else

18 $s\leftarrow$ GetNextState()

19

20

21

22

Algorithm 1 Explanation Framework Workflow

###  IV-A The Data

We collected a Behaviour Causality Dataset from 10 simulations of missions.
For each simulation, we monitored eight ROS topics with a listener module
corresponding to five vehicle states where S = {ready_plan, current_objective,
progress_type, same_objective, obstacle_found} along with the corresponding
behaviour. Each mission lasted 22.5 minutes on average and resulted in a
dataset of 5056 data instances with 5 categorical features and a target value.

###  IV-B Surrogate Model Training and Selection

After data collection, we made a comparison of various models to decide on the
most suitable option for Behaviour Classification. Specifically, we tested
three algorithmically explainable models, which are robust for classification
with categorical features (K-Nearest Neighbours (KNN) [33], Categorical Naive
Bayes (CategoricalNB) [34] and Decision Tree[35]) and we also included two
more complex models (Support Vector Machine (SVM)[36], Multilayer Preceptron
(MLP) [37]) to check if there is a significant performance difference.

A total of 5 categorical features were given as input to each model
(ready_plan, current_obj, progress_type, same_obj, obstacle_found) to predict
the current behaviour of the vessel (wait, transit, survey, hold_position,
replanned_transit, obstacle_avoidance). Nested cross-validation was used to
select the best combination of hyperparameters for each model and to retrieve
unbiased metrics indicative of each model’s performance [38].

From the results in Table I, for the transparent models, it is clear that the
Decision Tree and Categorical Naive Bayes algorithms outperform KNN. With
regards the more opaque algorithms, SVM achieved similar performance to MLP
but with the latter performing slightly better at correctly classifying
behaviours. As for model training and evaluation, the time needed for
transparent models to do both was much shorter than for Neural Networks. Thus
going forward, we decided to use the decision tree (max_depth = 8,
max_leaf_nodes = 15) given that it has similar accuracy to more complex
models. Furthermore, its high transparency means that it can be used to verify
the validity of the surrogate framework for more opaque models, in case these
are used in future use cases and datasets.

Figure 4: Confusion matrix indicating classification performance per behaviour
with a Decision Tree during simulations.

Figure 4 provides a confusion matrix of the predictions of the decision tree
per behaviour. For transit, hold_pos and survey behaviours, there are some
false classifications due to some inconsistency between the progress_type
feature and the corresponding behaviour, which indicates that an internal
autonomy state could be missing. As for false classifications between
hold_pos, survey and obs_avoid behaviours, we noticed that even though
replanning is triggered and an obstacle is found, the vehicle finds a way to
perform its objective, however, the explanation framework misses this fact
probably because an internal autonomy state is missing once again.

Figure 5: Four continuous events from a single mission along with their
behaviour predictions and the corresponding explanations. Scenarios 1, 2 and 4
contain correctly predicted behaviours, while Scenario 3 demonstrates a false
prediction that has been encountered.

###  IV-C Explanation Layer

Once a trained surrogate model is in place to predict the corresponding
behaviour of a vehicle state, the feature contribution for the classification
of the behaviour is used as a basis for the causal reasoning explanation. One
way to do feature contribution is to examine the trained surrogate model
itself [13]. This is feasible for transparent models, such as the decision
tree chosen here, but not so for more complex models such as Neural Networks.
Opaque models such as Neural Networks may be needed in future applications as
the complexity of the autonomy increases and the datasets grow in size. For
these more complex models, an alternative is to use Shapley Values [14], which
has been shown to be a reliable and descriptive approach. Here, we follow this
latter method as a proof of concept. Each model has initially a prior belief
about what the expected value will be and a Shapley value describes how a
specific feature creates the difference between the expected and actual values
($E(x)-f(x)$).

###  IV-D Knowledge Representation and Explanation Generation

The final two components of the pipeline use, as input, the prediction of the
surrogate model along with the Shapley values estimated by the feature
contribution estimator. Based on the importance of each feature towards a
prediction, behaviour causality is inferred and this knowledge is represented
with contextualised concept sets. Contextualisation is incorporated with the
use of key-value pairs, as opposed to simple triplets to indicate the role of
each value. The end result is a knowledge base with
$(vessel,behaviour,causality,time)$ sets, which describe the sequence of
behaviours exhibited by the robot in JSON format. An example of a
contextualised concept set can be found in Figure 3, where the current
behaviour (Transit) and its trigger (Obstacle) can be distinguished. This
entry indicates that the current transit behaviour has a modified trajectory
that goes around the obstacle to avoid collision. With regards to natural
language generation, for each new entry in the Knowledge Base, the key-value
pairs are passed to a Surface Realiser, which produces an explanation that has
been syntactically checked with SimpleNLG [39].

Models |  Accuracy |  Precision |  Recall |  F1-Score |  Fit Time |  Score Time
---|---|---|---|---|---|---
Decision Tree |  0.8981 |  0.9464 |  0.8498 |  0.8712 |  25.0936 |  0.0025
CategoricalNB |  0.8247 |  0.8701 |  0.8616 |  0.8379 |  0.1127 |  0.0019
KNN |  0.6655 |  0.7806 |  0.8291 |  0.6953 |  4.8554 |  0.0721
SVM |  0.8846 |  0.9163 |  0.8378 |  0.8535 |  14.9298 |  0.0547
Multilayer Perceptron (MLP) |  0.8987 |  0.9459 |  0.8496 |  0.8707 |  147.8816 |  0.0075
TABLE I: Classification performance metrics across five different models
derived with nested cross-validation on simulation data. Transparent models
are at the top part of the table and opaque ones are at the bottom. Training
and score times (in seconds) are also included to indicate the effort for
acquiring a surrogate model in other similar use cases.

##  V Results and Discussion

With regards RQ1 and RQ2, as discussed above and in Table I, the surrogate
models have accuracies for behaviour prediction of around 90%. This could
further be further improved by training on more data both in simulation and
with real vehicles.

Even with this accuracy, we observed accurate explanations as give illustrated
in Figure 5. In this figure, we present four continuous scenarios from a
single mission along with the explanations which were generated. Scenario 1
involves a vessel moving to the launch point to retrieve the relative
positions of the objective areas and begins working on each objective. In this
case, the surrogate model correctly predicts the current behaviour by using
the progress_type, current_obj and same_obj features. To validate the results,
we also calculated the Shapley values, which highlight the current_obj as the
main contributor. In Scenario 2, while the vehicle is moving from the launch
point to the survey area, it encounters an obstacle and avoids it by changing
its trajectory. Behaviour prediction was also successful in this case, with
the model utilising progress_type, current_obj, same_obj and obstacle_found
features. In Scenario 3, a false explanation is generated, due to the value of
progress_type even though the survey has already started. Here, the features
used by the surrogate model are, progress_type, current_obj and same_obj,
while SHAP only attributes this prediction to the current objective. As for
Scenario 4, where the vessel performs a survey, the surrogate model can
immediately detect the new behaviour thanks to its unique progress_type, while
SHAP adds to the causality both current_obj and same_obj, which seem
reasonable causes in this case. An informal evaluation has been conducted but
a formal subject evaluation is future work.

###  V-A Going from Simulation to Real Trial

For RQ3, a real trial took place with two Unmanned Surface Vehicles
collaborating to complete a survey, while obstacles appeared in the dynamic
environment. As a result, we tested the surrogate model on a separate trial
test set consisting of 1331 instances with 5 features and corresponding
behaviours. Looking at the overall performance, an accuracy of 99% was
achieved showing the capability of the surrogate model to comprehend the
autonomous behaviour activations. See Figure 6 for the confusion matrix for
this test. The only errors observed are false classifications between the
survey and transit behaviours, which we attribute to a potential missing
vehicle state since the progress_type could not fully indicate the transition
between these two behaviours. Finally, the hold_position behaviour is missing
from Figure 6, because this objective was not used during the trial for
practical reasons.

Figure 6: Confusion matrix indicating classification performance per behaviour
with a Decision Tree during the real trial.

##  VI Conclusion and Future Work

With this work, a framework for approximating behaviour activations and
replanning of an autonomous agent with classification models has been
introduced. Our approach is capable of discovering the causality of autonomous
decisions with the estimation of feature contribution for each action
prediction. The main advantage of this framework is the storage of information
in generic knowledge representations such as concept sets which can be later
leveraged to produce user-friendly modalities such as natural language
explanations. Another advantage is that the framework is agnostic to the
autonomy model, making it reusable in different domains. Moving forward, we
plan on extending the functionality of this framework and investigating data-
driven language explanations such as large language models in order to
stochastically map knowledge representations to informative natural language
explanations about robotic behaviour. Further evaluation of explanations is
also required to examine the capacity of our approach to disambiguate robotic
behaviours.

## Acknowledgment

We would like to thank MIT’s AUV Lab and Laurence Boe from SeeByte Ltd for
their assistance with the simulator and the real trial. This work was also
funded and supported by the EPSRC Prosperity Partnership (EP/V05676X/1), the
UKRI Node on Trust (EP/V026682/1), EPSRC CDT on Robotics and Autonomous
Systems (EP/S023208/1), and Scottish Research Partnership in Engineering.

## References

  * [1] Paull, L., Saeedi, S., Seto, M. and Li, H., 2013. AUV navigation and localization: A review. IEEE Journal of oceanic engineering, 39(1), pp.131-149.
  * [2] Winfield, A.F., Booth, S., Dennis, L.A., Egawa, T., Hastie, H., Jacobs, N., Muttram, R.I., Olszewska, J.I., Rajabiyazdi, F., Theodorou, A. and Underwood, M.A., 2021. IEEE P7001: A proposed standard on transparency. Frontiers in Robotics and AI, 8, p.665729.
  * [3] Hastie, H., Liu, X. and Patron, P., 2017, November. Trust triggers for multimodal command and control interfaces. In Proceedings of the 19th ACM International Conference on Multimodal Interaction (pp. 261-268).
  * [4] Langley, P., Meadows, B., Sridharan, M. and Choi, D., 2017, February. Explainable agency for intelligent autonomous systems. In Proceedings of the AAAI Conference on Artificial Intelligence (Vol. 31, No. 2, pp. 4762-4763).
  * [5] Anjomshoae, S., Najjar, A., Calvaresi, D. and Främling, K., 2019. Explainable agents and robots: Results from a systematic literature review. In 18th International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2019), Montreal, Canada, May 13–17, 2019 (pp. 1078-1088). International Foundation for Autonomous Agents and Multiagent Systems.
  * [6] De Graaf, M.M. and Malle, B.F., 2017, October. How people explain action (and autonomous intelligent systems should too). In 2017 AAAI Fall Symposium Series.
  * [7] Kulesza, T., Stumpf, S., Burnett, M., Yang, S., Kwan, I. and Wong, W.K., 2013, September. Too much, too little, or just right? Ways explanations impact end users’ mental models. In 2013 IEEE Symposium on visual languages and human centric computing (pp. 3-10). IEEE.
  * [8] Garcia, F.J.C., Robb, D.A., Liu, X., Laskov, A., Patron, P. and Hastie, H., 2018, November. Explainable autonomy: A study of explanation styles for building clear mental models. In Proceedings of the 11th International Conference on Natural Language Generation (pp. 99-108).
  * [9] Fox, M., Long, D. and Magazzeni, D., 2017. Explainable planning. arXiv preprint arXiv:1709.10256.
  * [10] Wachter, S., Mittelstadt, B. and Floridi, L., 2017. Transparent, explainable, and accountable AI for robotics. Science robotics, 2(6), p.eaan6080.
  * [11] Arrieta, A.B., Díaz-Rodríguez, N., Del Ser, J., Bennetot, A., Tabik, S., Barbado, A., García, S., Gil-López, S., Molina, D., Benjamins, R. and Chatila, R., 2020. Explainable Artificial Intelligence (XAI): Concepts, taxonomies, opportunities and challenges toward responsible AI. Information fusion, 58, pp.82-115.
  * [12] Adadi, A. and Berrada, M., 2018. Peeking inside the black-box: a survey on explainable artificial intelligence (XAI). (pp.52138-52160). IEEE access.
  * [13] Ribeiro, M.T., Singh, S. and Guestrin, C., 2016, August. ” Why should i trust you?” Explaining the predictions of any classifier. In Proceedings of the 22nd ACM SIGKDD international conference on knowledge discovery and data mining (pp. 1135-1144).
  * [14] Lundberg, S.M. and Lee, S.I., 2017. A unified approach to interpreting model predictions. Advances in neural information processing systems, 30.
  * [15] Chou, Y.L., Moreira, C., Bruza, P., Ouyang, C. and Jorge, J., 2022. Counterfactuals and causability in explainable artificial intelligence: Theory, algorithms, and applications. Information Fusion, 81, pp.59-83.
  * [16] Alvarez-Melis, D. and Jaakkola, T.S., 2018. On the robustness of interpretability methods. arXiv preprint arXiv:1806.08049.
  * [17] Sakai, T. and Nagai, T., 2022. Explainable autonomous robots: A survey and perspective. Advanced Robotics, 36(5-6), pp.219-238.
  * [18] Alvanpour, A., Das, S.K., Robinson, C.K., Nasraoui, O. and Popa, D., 2020, August. Robot failure mode prediction with explainable machine learning. In 2020 IEEE 16th International Conference on Automation Science and Engineering (CASE) (pp. 61-66). IEEE.
  * [19] Gjærum, V.B., Strümke, I., Løver, J., Miller, T. and Lekkas, A.M., 2023. Model tree methods for explaining deep reinforcement learning agents in real-time robotic applications. Neurocomputing, 515, pp.133-144.
  * [20] Sieusahai, A. and Guzdial, M., 2021, October. Explaining deep reinforcement learning agents in the atari domain through a surrogate model. In Proceedings of the AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment (Vol. 17, No. 1, pp. 82-90).
  * [21] Remman, S.B. and Lekkas, A.M., 2021, June. Robotic lever manipulation using hindsight experience replay and shapley additive explanations. In 2021 European Control Conference (ECC) (pp. 586-593). IEEE.
  * [22] Thielstrom, R., Roque, A., Chita-Tegmark, M. and Scheutz, M., 2020, November. Generating explanations of action failures in a cognitive robotic architecture. In 2nd Workshop on Interactive Natural Language Technology for Explainable Artificial Intelligence (pp. 67-72).
  * [23] David A. Robb, Xingkun Liu, and Helen Hastie. 2023. Explanation Styles for Trustworthy Autonomous Systems: Extended Abstract. In Proc. of the 22nd International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2023), London, United Kingdom, May 29 – June 2, 2023, IFAAMAS.
  * [24] Das, D., Banerjee, S. and Chernova, S., 2020. Explainable AI for System Failures: Generating Explanations that Improve Human Assistance in Fault Recovery. arXiv preprint arXiv:2011.09407.
  * [25] Gavriilidis, K., Munafo, A., Hastie, H., Cesar, C., DeFilippo, M. and Benjamin, M.R., 2022. Towards Explaining Autonomy with Verbalised Decision Tree States. arXiv preprint arXiv:2209.13985.
  * [26] Li, X., Bilbao, S., Martín-Wanton, T., Bastos, J. and Rodriguez, J., 2017. SWARMs ontology: A common information model for the cooperation of underwater robots. Sensors, 17(3), p.569.
  * [27] Gavriilidis, K., Carreno, Y., Munafo, A., Pang, W., Petrick, R.P. and Hastie, H., 2021, August. Plan Verbalisation for Robots Acting in Dynamic Environments. In Proceedings of ICAPS 2021 Workshop on Knowledge Engineering for Planning and Scheduling.
  * [28] Suh, I.H., Lim, G.H., Hwang, W., Suh, H., Choi, J.H. and Park, Y.T., 2007, October. Ontology-based multi-layered robot knowledge framework (OMRKF) for robot intelligence. In 2007 IEEE/RSJ International Conference on Intelligent Robots and Systems (pp. 429-436). IEEE.
  * [29] Lebret, R., Grangier, D. and Auli, M., 2016. Neural text generation from structured data with application to the biography domain. arXiv preprint arXiv:1603.07771.
  * [30] Lin, B.Y., Zhou, W., Shen, M., Zhou, P., Bhagavatula, C., Choi, Y. and Ren, X., 2019. CommonGen: A constrained text generation challenge for generative commonsense reasoning. arXiv preprint arXiv:1911.03705.
  * [31] Ghosal, D., Shen, S., Majumder, N., Mihalcea, R. and Poria, S., 2022. CICERO: A Dataset for Contextualized Commonsense Inference in Dialogues. arXiv preprint arXiv:2203.13926.
  * [32] OpenAI, 2023. “GPT-4 Technical Report.”. arXiv preprint arXiv:2303.08774.
  * [33] Larose, D.T. and Larose, C.D., 2014. k‐nearest neighbour algorithm.
  * [34] Zhang, H., 2004. The optimality of naive Bayes. Aa, 1(2), p.3.
  * [35] Vega, F.A., Matías, J.M., Andrade, M.L., Reigosa, M.J. and Covelo, E.F., 2009. Classification and regression trees (CARTs) for modelling the sorption and retention of heavy metals by soil. Journal of Hazardous Materials, 167(1-3), pp.615-624.
  * [36] Hearst, M.A., Dumais, S.T., Osuna, E., Platt, J. and Scholkopf, B., 1998. Support vector machines. IEEE Intelligent Systems and their applications, 13(4), pp.18-28.
  * [37] Hinton, G.E., 1990. Connectionist learning procedures. In Machine learning (pp. 555-610). Morgan Kaufmann.
  * [38] Cawley, G.C. and Talbot, N.L., 2010. On over-fitting in model selection and subsequent selection bias in performance evaluation. The Journal of Machine Learning Research, 11, pp.2079-2107.
  * [39] Gatt, A. and Reiter, E., 2009, March. SimpleNLG: A realisation engine for practical applications. In Proceedings of the 12th European workshop on natural language generation (ENLG 2009) (pp. 90-93).


* Yin  _et al._ (2016) H.-L. Yin, T.-Y. Chen, Z.-W. Yu, H. Liu, L.-X. You, Y.-H. Zhou, S.-J. Chen, Y. Mao, M.-Q. Huang, W.-J. Zhang, H. Chen, M. J. Li, D. Nolan, F. Zhou, X. Jiang, Z. Wang, Q. Zhang, X.-B. Wang, and J.-W. Pan, Physical Review Letters 117, 190501 (2016).
  * Lucamarini  _et al._ (2018) M. Lucamarini, Z. L. Yuan, J. F. Dynes, and A. J. Shields, Nature 557, 400 (2018).
  * Curty  _et al._ (2019) M. Curty, K. Azuma, and H.-K. Lo, npj Quantum Information 5, 64 (2019).
  * Ma  _et al._ (2018) X. Ma, P. Zeng, and H. Zhou, Physical Review X 8, 031043 (2018).
  * Lin and Lütkenhaus (2018) J. Lin and N. Lütkenhaus, Physical Review A 98, 042332 (2018).
  * Wang  _et al._ (2018) X.-B. Wang, Z.-W. Yu, and X.-L. Hu, Physical Review A 98, 062323 (2018).
  * Gisin  _et al._ (2004) N. Gisin, G. Ribordy, H. Zbinden, D. Stucki, N. Brunner, and V. Scarani, preprint quant-ph/0411022 (2004).
  * Stucki  _et al._ (2005) D. Stucki, N. Brunner, N. Gisin, V. Scarani, and H. Zbinden, Applied Physics Letters 87, 194108 (2005).
  * Stucki  _et al._ (2009) D. Stucki, N. Walenta, F. Vannel, R. T. Thew, N. Gisin, H. Zbinden, S. Gray, C. R. Towery, and S. Ten, New Journal of Physics 11, 075003 (2009).
  * Korzh  _et al._ (2015) B. Korzh, C. C. W. Lim, R. Houlmann, N. Gisin, M. J. Li, D. Nolan, B. Sanguinetti, R. Thew, and H. Zbinden, Nature Photonics 9, 163 (2015).
  * Huttner  _et al._ (1995) B. Huttner, N. Imoto, N. Gisin, and T. Mor, Physical Review A 51, 1863 (1995).
  * Brassard  _et al._ (2000) G. Brassard, N. Lütkenhaus, T. Mor, and B. C. Sanders, Physical Review Letters 85, 1330 (2000).
  * (32) ID Quantique SA, Geneva, Switzerland, http://www.idquantique.com.
  * Moroder  _et al._ (2012) T. Moroder, M. Curty, C. C. W. Lim, L. P. Thinh, H. Zbinden, and N. Gisin, Physical Review Letters 109 (2012).
  * Lavie and Lim (2022) E. Lavie and C. C.-W. Lim, Physical Review Applied 18, 064053 (2022).
  * Gao  _et al._ (2022) R.-Q. Gao, Y.-M. Xie, J. Gu, W.-B. Liu, C.-X. Weng, B.-H. Li, H.-L. Yin, and Z.-B. Chen, Optics Express 30, 23783 (2022).
  * Li  _et al._ (lack) M.-Y. Li, X.-Y. Cao, Y.-M. Xie, H.-L. Yin, and Z.-B. Chen, Physical Review Research 6, 013022 (2024).
  * González-Payo  _et al._ (2020) J. González-Payo, R. Trényi, W. Wang, and M. Curty, Physical Review Letters 125 (2020).
  * Waks  _et al._ (2006) E. Waks, H. Takesue, and Y. Yamamoto, Physical Review A 73, 012344 (2006).
  * Curty  _et al._ (2007) M. Curty, L. L. Zhang, H. K. Lo, and N. Lütkenhaus, Quantum Information and Computation 7, 665 (2007).
  * Tsurumaru (2007) T. Tsurumaru, Physical Review A 75, 062319 (2007).
  * Curty  _et al._ (2008) M. Curty, K. Tamaki, and T. Moroder, Physical Review A 77, 052321 (2008).
  * Curty  _et al._ (2004) M. Curty, M. Lewenstein, and N. Lütkenhaus, Physical Review Letters 92, 217903 (2004).
  * Trényi and Curty (2021) R. Trényi and M. Curty, New Journal of Physics 23, 093005 (2021).
  * Chefles (1998) A. Chefles, Physics Letters A 239, 339 (1998).
  * Chefles and Barnett (1998) A. Chefles and S. M. Barnett, Physics Letters A 250, 223 (1998).
  * Branciard  _et al._ (2007) C. Branciard, N. Gisin, N. Lütkenhaus, and V. Scarani, Quantum Information & Computation 7, 639 (2007).
  * Wehner  _et al._ (2008) S. Wehner, C. Schaffner, and B. M. Terhal, Physical Review Letters 100, 220502 (2008).
  * König  _et al._ (2012) R. König, S. Wehner, and J. Wullschleger, IEEE Transactions on Information Theory 58, 1962 (2012).
  * Damgård  _et al._ (2007) I. B. Damgård, S. Fehr, R. Renner, L. Salvail, and C. Schaffner, in  _Advances in Cryptology - CRYPTO 2007_ , edited by A. Menezes (Springer Berlin Heidelberg, Berlin, Heidelberg, 2007) pp. 360–378.
  * Wehner  _et al._ (2010) S. Wehner, M. Curty, C. Schaffner, and H.-K. Lo, Physical Review A 81, 052336 (2010).
  * Paris (1996) M. G. Paris, Physics Letters A 217, 78 (1996).
  * Laiho  _et al._ (2009) K. Laiho, M. Avenhaus, K. N. Cassemiro, and C. Silberhorn, New Journal of Physics 11, 043012 (2009).