Straight-Line Path Following Control Problem Solution sec:Sol

In order to solve LFC problem, we proceed according to the solution strategy
outlined in the previous section.

Step 1: Integral line-of-sight reference vector field subsec:los Considering
the path $\mathcal{P}$ in eq:line, we propose a reference vector field for the
closed-loop dynamics that achieves the LFC problem objective. This vector
field is inspired from the ILOS path following laws for underactuated marine
craft control (see, e.g., caharija2016integral). In ILOS-based guidance
schemes, the cross-track error of the moving object to the desired path is
minimized while the controlled object is pointing at a moving target point on
the desired path (see Figure fig:los(a)). In addition to the cross track-error
to $\mathcal{P}$, ILOS-based guidance laws incorporate the integral of the
cross-track error using a dynamic variable $s$. In the presence of
disturbances that drive the microswimmer away from its desired path, embedding
the integral compensation dynamics via the dynamic variable $s$ will build up
a corrective action in the reference vector field.

0.18 [scale=0.30]./figures/ILOS.png 0.15 [scale=0.25]./figures/microBlock.png

Figure :  Figure :  Figure : (a) Integral line-of-sight reference vector field
and (b) block diagram of the ODS-based control scheme.

Given the LFC problem for the magnetic microswimmer, we propose the following
ILOS reference vector field

$\vx{v}^{\tx{d}}(\vx{p},s)=\alpha_{\text}{d}\vx{R}_{\theta_{\tx}{r}}\bmatrix\Delta_{\tx}{LOS}\\\
-|\vx{p}|\sin(\Delta\theta)-\sigma_{0}s,$ (1)

where $\alpha_{\text}{d}>0$ and the integral gain $\sigma_{0}>0$ are constant
design parameters, $\vx{p}$ is the position of the center of mass of the
microrobot with respect to the inertial frame $\mathcal{W}$, and the matrix
$\mathbf{R}_{\theta_{\tx{r}}}$ is the rotation matrix by $\theta_{\tx{r}}$.
The parameter $\Delta_{\tx}{LOS}>0$, which determines the point along
$\mathcal{P}$ at which the microrobot should be pointed (see Figure (a)), is
called the _look-ahead distance_. Furthermore, $s$ is a dynamic variable whose
dynamics are governed by

$\dot{s}=-k_{\text}{d}s+\Delta_{\tx{LOS}}\frac{|\vx{p}|\sin(\Delta\theta)}{(|\vx{p}|\sin(\Delta\theta)+\sigma_{0}s)^{2}+\Delta_{\tx{LOS}}^{2}},$
(2)

where the damping gain $k_{\text}{d}>0$ is a constant design parameter. Figure
(a) provides the geometric interpretation of the proposed ILOS guidance law in
eq:los and eq:losdynvar. The idea behind eq:los and eq:losdynvar is that the
integral of the cross-track error $\varepsilon=|\mathbf{p}|\sin(\Delta\theta)$
will allow the angle between $\vx{v}^{\tx{d}}(\vx{p},s)$ and $\mathcal{P}$ to
be non-zero when $\varepsilon=0$, i.e., when the microswimmer is moving on the
desired line. In particular, in the presence of disturbances driving the
microswimmer away from its path, the integral of the cross-track error will
build up to create a non-zero side-slip angle to follow the line. We can
rewrite the ILOS reference vector field in eq:los and eq:losdynvar in terms of
the cross-track error given by eq:output2 as

$\aligned\vx{v}^{\tx{d}}(\varepsilon,s)=\alpha_{\text}{d}\vx{R}_{\theta_{\tx}{r}}\bmatrix\Delta_{\tx}{LOS}\\\
-\varepsilon-\sigma_{0}s,\\\
\dot{s}=-k_{\text}{d}s+\Delta_{\tx{LOS}}\frac{\varepsilon}{(\varepsilon+\sigma_{0}s)^{2}+\Delta_{\tx{LOS}}^{2}}.$
(3)

We now derive the closed-loop dynamics of the cross-track error under the
effect of disturbances while assuming that there are no restrictions on the
control input magnitude. In the next section, we formally take into account
the angular velocity command input restrictions due to the step-out frequency
constraint. Considering the microswimmer’s dynamics in eq:eq_dyn, an estimate
$\hat{e}_{11}$ of the physical parameter $e_{11}$ in eq:e11 and an estimate
$\hat{\mathbf{d}}_{\mu}$ of the disturbance vector $\mathbf{d}_{\mu}$ in
eq:notation, and assuming that the control input has been chosen to be

$\mathbf{u}=\frac{1}{\hat{e}_{11}}\vx{v}^{\text}{d}-\frac{1}{\hat{e}_{11}}\hat{\mathbf{d}}_{\mu},$
(4)

we get the closed-loop dynamics

$\dot{\vx{p}}=\tfrac{e_{11}}{\hat{e}_{11}}\vx{v}^{\text}{d}+\vx{d}_{\mu}-\tfrac{e_{11}}{\hat{e}_{11}}\hat{\mathbf{d}}_{\mu}.$
(5)

If no knowledge of $e_{11}$ and $\mathbf{d}_{\mu}$ are available, one can
choose the estimates $\hat{e}_{11}=1$ and $\hat{\mathbf{d}}_{\mu}=\mathbf{0}$
in eq:nomCont. In deriving the cross-track error dynamics under ILOS-based
guidance laws and their stability properties, we assume that $\hat{e}_{11}=1$
and $\hat{\mathbf{d}}_{\mu}=\mathbf{0}$. Therefore, the dynamics of the cross-
track error in eq:output2 under the control law in eq:nomCont are given by

$\dot{\varepsilon}=e_{11}\alpha_{\tx{d}}\hat{\vx{e}}_{{}_{\theta_{\tx}{r}}}^{\perp^{\top}}\dot{\vx{p}}=\alpha_{\tx{d}}\hat{\vx{e}}_{{}_{\theta_{\tx}{r}}}^{\perp^{\top}}\big{(}\tfrac{e_{11}}{\hat{e}_{11}}\vx{v}^{\text}{d}+\vx{d}_{\mu}-\tfrac{e_{11}}{\hat{e}_{11}}\hat{\mathbf{d}}_{\mu}\big{)}.$
(6)

Using the ILOS guidance law $\vx{v}^{\text{d}}=\vx{v}^{\tx{d}}(\varepsilon,s)$
in eq:los2, assuming $\hat{e}_{11}=1$ and $\hat{\mathbf{d}}_{\mu}=\mathbf{0}$
(see Remark ), and noticing that
$\hat{\vx{e}}_{{}_{\theta_{\tx}{r}}}^{\perp^{\top}}\vx{R}_{\theta_{\tx}{r}}=[0,\,1]$,
we obtain

$\dot{\varepsilon}=\alpha_{\tx{d}}e_{11}(-\varepsilon-\sigma_{0}s)+\alpha_{\text}{d}d_{\mu}^{\perp},$
(7)

where
$d_{\mu}^{\perp}:=\hat{\vx{e}}_{{}_{\theta_{\tx}{r}}}^{\perp^{\top}}{\vx{d}}_{\mu}$.
Similarly, the dynamics of $z$ defined in eq:zeroState are found to be

$\dot{z}=e_{11}\alpha_{\tx{d}}\Delta_{\text{LOS}}+\alpha_{\text}{d}d_{\mu}^{\parallel},$

where
$d_{\mu}^{\parallel}:=\hat{\vx{e}}_{{}_{\theta_{\tx}{r}}}^{\top}{\vx{d}}_{\mu}$.
Consequently, the closed-loop dynamics of the helical microswimmer under the
control law eq:nomCont with $\hat{e}_{11}=1$ and
$\hat{\mathbf{d}}_{\mu}=\mathbf{0}$ (see Remark ) and the ILOS guidance law
$\vx{v}^{\text{d}}=\vx{v}^{\tx{d}}(\varepsilon,s)$ in eq:los2 are governed by

$\aligned\dot{\varepsilon}=-\alpha_{\tx{d}}\varepsilon-\alpha_{\tx{d}}\sigma_{0}s+\alpha_{\tx{d}}d_{\mu}^{\perp},\\\
\dot{s}=-k_{\text}{d}s+\Delta_{\tx{LOS}}\frac{\varepsilon}{(\varepsilon+\sigma_{0}s)^{2}+\Delta_{\tx{LOS}}^{2}},\\\
\dot{z}=\alpha_{\tx{d}}e_{11}\Delta_{\text{LOS}}+\alpha_{\text}{d}d_{\mu}^{\parallel}.$
(8)

As it can be seen from Equation eq:los3, the dynamics of $s$ have the property
that $\dot{s}\to-k_{\text}{d}s$ as $\varepsilon\to\infty$, implying that the
rate of integration will decrease with large cross-track errors. In
particular, the integral term will be less dominant when the cross-track error
is large, i.e., when the microswimmer is far from the desired line
$\mathcal{P}$. As stated in [caharija2016integral], such error-dependent
attenuation of integral action will reduce the risk of integrator wind-up and
its resulting performance limitations. In order to investigate the stability
properties of the cross-track error dynamics in eq:los3, we define the
following state and disturbance vectors

$\vx{x}:=\bmatrix\varepsilon\\\ s,\,\vx{d}_{\mu}^{\perp}:=\bmatrix
d_{\mu}^{\perp}\\\ 0.$ (9)

Using eq:los3, the dynamics of $\vx{x}$ can be written as

$\dot{\vx{x}}=\vx{A}\vx{x}+\vx{G}(\vx{x})\vx{x}+\alpha_{\text}{d}\vx{d}_{\mu}^{\perp},$
(10)

where

$\aligned\vx{A}:=-\alpha_{\text}{d}\bmatrix 1&\sigma_{0}\\\
0\frac{k_{\text}{d}}{\alpha_{\text}{d}},&\vx{G}(\vx{x}):=\frac{\Delta_{\tx{LOS}}}{\vx{x}^{\top}\vx{H}\vx{x}+\Delta_{\tx{LOS}}^{2}}\vx{B},\\\
\textcolor{black}{\vx{H}:=\bmatrix 1\sigma_{0}\\\
\sigma_{0}\sigma_{0}^{2}},\vx{B}:=\bmatrix 00\\\ 10.$ (11)

The following proposition describes the stability properties of the cross-
track error dynamics in eq:xCrossdyn and eq:xCrossdyn2 as well as the steady-
state velocity along $\mathcal{P}$. Consider the helical microswimmer dynamics
in eq:eq_dyn under the angular velocity control input eq:nomCont with
$\hat{e}_{11}=1$, $\hat{\mathbf{d}}_{\mu}=\mathbf{0}$, and the ILOS guidance
law $\vx{v}^{\text{d}}=\vx{v}^{\text{d}}(\mathbf{p},s)$ given by eq:los and
eq:losdynvar. Suppose that there exist symmetric positive definite matrices
$\mathbf{\Gamma}$ and $\mathbf{P}=\bmatrix p_{11}&p_{12}\\\ p_{12}p_{22}\;$
such that

$\aligned\vx{A}^{\top}\vx{P}+\vx{P}\vx{A}=-\vx{\Gamma},\\\
\lambda_{\text{min}}(\vx{\Gamma})>\frac{p_{12}+\sqrt{p_{12}^{2}+p_{22}^{2}}}{\Delta_{\text{LOS}}}.$
(12)

Then, under $d_{\mu}^{\perp}=0$, the cross-track error dynamics in
eq:xCrossdyn are globally exponentially stable (GES). Moreover, if
$d_{\mu}^{\parallel}=0$, $\dot{\vx{p}}(t)\to
e_{11}\alpha_{\tx{d}}\Delta_{\tx{LOS}}\hat{\mathbf{e}}_{{}_{\theta_{\text}{r}}}$
as $t\to\infty$. Furthermore, if
$\lambda_{\text{min}}(\vx{\Gamma})>\tfrac{p_{12}}{\Delta_{\text{LOS}}}+\sqrt{p_{12}^{2}+p_{22}^{2}}(\alpha_{\text}{d}+\tfrac{1}{\Delta_{\text{LOS}}})$,
the cross-track error dynamics in eq:xCrossdyn are input-to-state stable
(ISS). Consequently, if $\|\vx{d}_{\mu}\|_{\infty}<d^{\ast}$ for some constant
$d^{\ast}>0$, then $[\varepsilon,\,s]^{\top}$ will converge to the ball
$\mathcal{B}_{d^{\ast}\lambda_{\text{max}}(\mathbf{P})/\lambda_{\text{min}}(\mathbf{P})}(\mathbf{0})$.
Proof. Consider the quadratic Lyapunov function candidate

$V(\vx{x}):=\vx{x}^{\top}\vx{P}\vx{x},$ (13)

and compute its derivative $\dot{V}(\vx{x}):=\tfrac{\partial
V}{\partial\vx{x}}\dot{\vx{x}}$ along the trajectories of the error dynamics
in eq:xCrossdyn to obtain

$\aligned\dot{V}(\vx{x})&=\vx{x}^{\top}(\vx{A}^{\top}\vx{P}+\vx{P}\vx{A})\vx{x}+\frac{\Delta_{\tx{LOS}}}{\vx{x}^{\top}\vx{H}\vx{x}+\Delta_{\tx{LOS}}^{2}}\vx{x}^{\top}(\vx{B}^{\top}\vx{P}+\\\
\vx{P}\vx{B})\vx{x}+2\alpha_{\text}{d}\vx{x}^{\top}\vx{P}\vx{d}_{\mu}^{\perp}.$
(14)

Using the Rayleigh’s inequality, we have
$\dot{V}(\vx{x})\leq-\lambda_{\text{min}}(\vx{\Gamma})|\vx{x}|^{2}+\frac{\Delta_{\tx{LOS}}\lambda_{\text{max}}(\vx{B}^{\top}\vx{P}+\vx{P}\vx{B})}{\lambda_{\text{min}}(\vx{H})|\vx{x}|^{2}+\Delta_{\tx{LOS}}^{2}}|\vx{x}|^{2}+2\alpha_{\text}{d}\vx{x}^{\top}\vx{P}\vx{d}_{\mu}^{\perp}$.
Since black$\lambda_{\text{min}}(\mathbf{H})=0$,
$\lambda_{\text{max}}(\vx{B}^{\top}\vx{P}+\vx{P}\vx{B})=p_{12}+\sqrt{p_{12}^{2}+p_{22}^{2}}$,
and from eq:stabCond, it can be seen that

$\dot{V}(x)\leq-\big{(}\lambda_{\text{min}}(\vx{\Gamma})-\tfrac{p_{12}+\sqrt{p_{12}^{2}+p_{22}^{2}}}{\Delta_{\tx{LOS}}}\big{)}|\vx{x}|^{2}+2\alpha_{\text}{d}\vx{x}^{\top}\vx{P}\vx{d}_{\mu}^{\perp}.$
(15)

Hence, $V(\mathbf{x})$ in eq:Vcandid is a Lyapunov function for the cross-
track error dynamics, which satisfies
$\tfrac{1}{2}\lambda_{\text{min}}(\mathbf{P})|\mathbf{x}|^{2}\leq
V(\mathbf{x})\leq\tfrac{1}{2}\lambda_{\text{max}}(\mathbf{P})|\mathbf{x}|^{2}$
for all $\mathbf{x}$. Additionally, since $V(\mathbf{x})$ is radially
unbounded (i.e., $V(\mathbf{x})\to\infty$ as $|\mathbf{x}|\to\infty$), when
$\vx{d}_{\mu}^{\perp}=\mathbf{0}$, the origin $\mathbf{x}=\mathbf{0}$ is
globally exponentially stable (GES) for the cross-track error dynamics (see
Theorem 4.10 in [Khalil-2002]). Furthermore, since
$[\varepsilon,\,s]^{\top}\to\mathbf{0}$ as $t\to\infty$, we have
$\Delta\theta=0$. Therefore, on $\mathcal{P}$ where $\varepsilon=0$, it can be
seen that

$\vx{v}^{\tx{d}}(\mathbf{p},\,0)\Big{|}_{\mathbf{p}\in\mathcal{P}}=\alpha_{\tx{d}}\mathbf{R}_{\theta_{\tx}{r}}\bmatrix\Delta_{\tx}{LOS}\\\
0=\alpha_{\tx{d}}\Delta_{\tx}{LOS}\hat{\mathbf{e}}_{{}_{\theta_{\text}{r}}}.$
(16)

Consequently, using eq:ssVel in eq:closed1 when
$d_{\mu}^{\parallel}=d_{\mu}^{\perp}=0$, it can be seen that
$\dot{\vx{p}}(t)\to
e_{11}\alpha_{\tx{d}}\Delta_{\tx{LOS}}\hat{\mathbf{e}}_{{}_{\theta_{\text}{r}}}$
as $[\varepsilon,\,s]^{\top}\to\mathbf{0}$ when $t\to\infty$. Since the
derivative of the quadratic Lyapunov function $V(\mathbf{x})$ in eq:Vcandid
along the trajectories of the cross-track error dynamics satisfies
$\dot{V}(x)\leq-\big{(}\lambda_{\text{min}}(\vx{\Gamma})-\tfrac{p_{12}+\sqrt{p_{12}^{2}+p_{22}^{2}}}{\Delta_{\tx{LOS}}}-\sqrt{p_{12}^{2}+p_{22}^{2}}\alpha_{\text}{d}\big{)}|\vx{x}|^{2},\,\text{forall}|\mathbf{x}|\geq\|\vx{d}_{\mu}^{\perp}\|_{\infty}.$
Therefore, if
$\lambda_{\text{min}}(\vx{\Gamma})>\tfrac{p_{12}}{\Delta_{\text{LOS}}}+\sqrt{p_{12}^{2}+p_{22}^{2}}(\alpha_{\text}{d}+\tfrac{1}{\Delta_{\text{LOS}}})$,
the closed-loop dynamics are ISS and convergence to
$\mathcal{B}_{d^{\ast}\lambda_{\text{max}}(\mathbf{P})/\lambda_{\text{min}}(\mathbf{P})}(\mathbf{0})$
holds (see Theorem 4.19 in in [Khalil-2002]). $\blacksquare$ The following
corollary follows from Proposition . Assume the conditions in Proposition .
Then, under $\mathbf{d}_{\mu}=\mathbf{0}$, the set
$\mathcal{P}\times\\{s=0\\}$ is an invariant set for the microswimmer closed-
loop dynamics under the control law eq:nomCont with $\hat{e}_{11}=1$,
$\hat{\mathbf{d}}_{\mu}=\mathbf{0}$, and the ILOS guidance law
$\vx{v}^{\text{d}}=\vx{v}^{\text{d}}(\mathbf{p},s)$ given by eq:los and
eq:losdynvar. Furthermore, once the path $\mathcal{P}$ in eq:line is made
invariant, the speed of the microswimmer along $\mathcal{P}$ is

$v^{\star}=e_{11}\alpha_{\tx{d}}\Delta_{\tx{LOS}}.$ (17)

It is possible to further simplify the conditions in eq:stabCond in a way that
we obtain inequality constraints on the design parameters $k_{\tx}{d}$,
$\alpha_{\tx}{d}$, $\sigma_{0}$, and $\Delta_{\text{LOS}}$. blackFirst, it can
be shown that the roots $r_{i},\;i=1,2$, of the quadratic polynomial
$P(\lambda)=\lambda^{2}-\big{(}\frac{k_{\tx}{d}}{\alpha_{\tx}{d}}+\frac{p_{11}}{p_{12}}+\frac{\sigma_{0}p_{22}}{p_{12}}\big{)}\lambda+\frac{\sigma_{0}p_{11}p_{22}}{p_{12}^{2}}-\frac{1}{4}\Big{(}\frac{\sigma_{0}p_{11}}{p_{12}}+(1+\frac{k_{\tx}{d}}{\alpha_{\tx}{d}})\frac{p_{22}}{p_{12}}\Big{)}^{2}$
satisfy the relationship $\lambda_{i\Gamma}=2\alpha_{\tx}{d}p_{12}r_{i}$,
$i=1,\;2$ with $\lambda_{i\Gamma}$ being the eigenvalues of $\Gamma$ in
eq:stabCond. Next, by computing the eigenvalues of $\Gamma$ via finding the
roots of $P(\cdot)$ and under the simplifying assumption $p_{11}=p_{22}$, it
can be shown that the two inequalities

$\frac{k_{\tx}{d}}{\alpha_{\tx}{d}}\geq
0,\;(\sigma_{0}\alpha_{\tx}{d}\Delta_{\text{LOS}})^{2}+2\alpha_{\tx}{d}\Delta_{\text{LOS}}(1+\frac{k_{\tx}{d}}{\alpha_{\tx}{d}})\leq
1$ (18)

guarantee that the conditions in eq:stabCond are satisfied.

##  Step 2: ODS-based quadratic program

In this section, we present a feedback control solution for the microrobot LFC
problem based on the optimal decision strategy (ODS) framework
[spong1986control]. Considering the ILOS-based reference vector field in
eq:los and eq:losdynvar, it is clear from Proposition  that if the control
input $\mathbf{u}$ is designed such that the closed-loop dynamics are driven
by the ILOS-based guidance law, then the LFC problem objective is achieved.
However, the step-out frequency limitation

$|\mathbf{u}(t)|\leq\Omega_{\tx{SO}},$ (19)

on the rotational frequency of the helical microswimmer about its axis
constrains the magnitude of the angular velocity command input $\mathbf{u}$.
Using the ODS framework, we will address this constraint. ODS-based control is
a pointwise optimal control solution that, in the context of our problem,
minimizes the deviation between the vector field of the microswimmer open-loop
dynamics in eq:eq_dyn and the ILOS-based reference vector field in eq:los and
eq:losdynvar, while respecting the step-out frequency constraint in eq:ineq.
In order to state the ODS-based control scheme for the microswimmer, let
$\mathbf{p}(t,t_{0},\mathbf{p}_{0},\mathbf{u}(t))$, or
$\mathbf{p}(t,\mathbf{u}(t))$ or $\mathbf{p}(t)$ for short, denote the
solution to eq:eq_dyn corresponding to the control input
$t\mapsto\mathbf{u}(t)$ and initial position $\mathbf{p}_{0}$ at time $t_{0}$.
For each solution $\mathbf{p}(t)$, we define the set of permissible velocity
vectors $C_{t}$ to be the translation by $\mathbf{p}(t)$ of the set

$C(\mathbf{p}(t)):=\big{\\{}\mathbf{v}(t,\mathbf{w})\in\mathbb{R}^{2}\big{|}\mathbf{v}=\mathbf{d}_{\mu}+e_{11}\mathbf{w},\;|\mathbf{w}|\leq\Omega_{\text{SO}}\big{\\}}.$
(20)

Therefore, for any control input $\mathbf{u}(t)$ that respects the step-out
frequency constraint in eq:ineq, the velocity of the microswimmer lies in the
set $C(\mathbf{p}(t))$ (see Figure ). In the case of the microrobot LFC, we
choose the ODS-based control law $\mathbf{u}(t)$ in a way that at each time
$t$, the instantaneous velocity of the microswimmer is “nearest” to the ILOS-
based guidance law $\mathbf{v}^{\tx{d}}\big{(}\mathbf{p}(t),s(t)\big{)}$ given
by eq:los, eq:losdynvar in the norm on $\mathbb{R}^{2}$ defined by some
positive definite matrix $\mathbf{Q}$. In other words, the ODS-based control
law at each $t$ is the minimizing solution to

$\aligned\underset{\mathbf{v}\in
C(\mathbf{p}(t))}{\text{min.}}\;\Big{\\{}\big{[}\mathbf{v}-\mathbf{v}^{\tx{d}}\big{(}\mathbf{p}(t),s(t)\big{)}\big{]}^{\top}\mathbf{Q}\big{[}\mathbf{v}-\mathbf{v}^{\tx{d}}\big{(}\mathbf{p}(t),s(t)\big{)}\big{]}\Big{\\}}.$
(21)

The minimization problem in eq:permissible2 is equivalent to the explicit
minimization in $\mathbf{u}(t)$,

$\aligned\underset{\mathbf{u}}{\text{min.}}\;&\Big{\\{}\big{[}e_{11}\vx{u}(t)+{\vx{d}}_{\mu}(t)-\mathbf{v}^{\tx{d}}(\mathbf{p}(t),s(t))\big{]}^{\top}\mathbf{Q}\\\
\big{[}e_{11}\vx{u}(t)+{\vx{d}}_{\mu}(t)-\mathbf{v}^{\tx{d}}(\mathbf{p}(t),s(t))\big{]}\Big{\\}}\\\
\text{subjectto}\;\;\;|\mathbf{u}(t)|\leq\Omega_{\text{SO}},$ (22)

[scale=0.30]./figures/ODS_general.png

Figure : Geometric interpretation of optimal decision strategy.

which, in turn, can be shown to be equivalent to the QP

$\aligned\underset{\vx{u}}{\text{min.}}\;&\big{\\{}\frac{1}{2}\vx{u}^{\top}\mathbf{A}_{\mu}\vx{u}+\vx{G}^{\top}_{\mu}(\vx{p},s)\vx{u}\big{\\}}\\\
\text{subjectto}\;\;\;\vx{u}^{\top}\vx{u}\leq\Omega_{\text{SO}}^{2},$ (23)

where

$\textcolor{black}{\aligned\vx{A}_{\mu}:=e_{11}^{2}\vx{Q},\\\
\vx{G}_{\mu}(\vx{p},s):=\frac{-\vx{A}_{\mu}}{e_{11}}\big{(}\vx{d}_{\mu}-\vx{v}^{\tx{d}}(\vx{p},s)\big{)},}$
(24)

The QP in eq:ODS, which involves minimizing a quadratic over a sphere, is
called a trust region subproblem (TRS) [hager2001minimizing]. It is well-known
from the TRS literature (see, e.g., Theorem 1.1 in [adachi2017solving]) that
$\vx{u}$ is a solution to the TRS in eq:ODS _if and only if_ there exists
$\lambda^{\ast}\geq 0$ such that — u^∗— ≤Ω_SO,
(A_μ \+ λ^∗I) u^∗= -G_μ(p,s),
λ^∗(Ω_SO - — u^∗—) = 0,
A_μ \+ λ^∗I ⪰0. Using proper state transformations, it is possible to restate
the ODS problem in eq:tempODS such that $\vx{Q}$ becomes diagonal. In the rest
of this paper and without loss of generality, we assume that $\vx{Q}$ in the
ODS problem in eq:tempODS has the diagonal form
$\vx{Q}=\text{diag}\\{q_{1},\,q_{2}\\}$, where $q_{1}>0$ and $q_{2}>0$ are
design parameters. The following proposition provides the solutions to the TRS
in eq:ODS and eq:ODS2. Consider the QP in eq:ODS with the matrix
$\mathbf{Q}=\text{diag}\\{q_{1},\,q_{2}\\}$. Then, the optimal pointwise
angular velocity control input, which solves eq:ODS, is given by

$\vx{u}^{\ast}(\vx{p},s)=\cases{-}\vx{A}^{-1}_{\mu}\vx{G}_{\mu}(\vx{p},s)&\text{if}\;|\vx{u}^{\ast}|<\Omega_{\text{SO}}\\\
-\big{(}\vx{A}_{\mu}+\lambda^{\ast}\vx{I}\big{)}^{-1}\vx{G}_{\mu}(\vx{p},s)\text{if}\;|\vx{u}^{\ast}|=\Omega_{\text{SO}}$
(25)

where $\vx{A}_{\mu}$ and
$\vx{G}_{\mu}(\vx{p},s)=[G_{1\mu}(\vx{p},s),\,G_{2\mu}(\vx{p},s)]^{\top}$ are
defined in eq:ODS2, and $\lambda^{\ast}$ is a non-negative root to the
following algebraic equation

$\frac{G_{1\mu}^{2}(\vx{p},s)}{\big{(}e_{11}^{\textcolor{black}{2}}q_{1}+\lambda^{\ast}\big{)}^{2}}+\frac{G_{2\mu}^{2}(\vx{p},s)}{\big{(}e_{11}^{\textcolor{black}{2}}q_{2}+\lambda^{\ast}\big{)}^{2}}=\Omega_{\text{SO}}^{2}.$
(26)

Furthermore, the angular velocity control input $\vx{u}^{\ast}(\vx{p})$ will
be absolutely continuous if and only if
$q_{1}=q_{2}=\tfrac{1}{\Omega_{0}e_{11}^{2}}$ for some $\Omega_{0}>0$, and
given by

$\vx{u}^{\ast}(\vx{p},s)=\cases{-}\Omega_{0}\vx{G}_{\mu}(\vx{p},s)&\text{if}\;|\vx{G}_{\mu}(\vx{p},s)|<\frac{\Omega_{SO}}{\Omega_{0}}\\\
-\Omega_{\text{SO}}\frac{\vx{G}_{\mu}(\vx{p},s)}{|\vx{G}_{\mu}(\vx{p},s)|}\text{if}\;|\vx{G}_{\mu}(\vx{p},s)|\geq\frac{\Omega_{SO}}{\Omega_{0}}$
(27)

Proof. Consider the necessary and sufficient conditions in eq:TRSiff2. Suppose
that $|\vx{u}^{\ast}|<\Omega_{\text{SO}}$. Then, according to eq:c,
$\lambda^{\ast}=0$. Hence, under $|\vx{u}^{\ast}|<\Omega_{\text{SO}}$ and from
eq:b, it can be seen that
$\vx{u}^{\ast}(\vx{p},s)=-\vx{A}^{-1}_{\mu}\vx{G}_{\mu}(\vx{p},s)$. Next,
suppose $|\vx{u}^{\ast}|=\Omega_{\text{SO}}$. From eq:b, it follows that

$\vx{u}^{\ast}=-\big{(}\vx{A}_{\mu}+\lambda^{\ast}\vx{I}\big{)}^{-1}\vx{G}_{\mu}(\vx{p},s).$
(28)

In order to find the constant $\lambda^{\ast}$ in the previous equation, we
use eq:temp11 to get

$\vx{u}^{\ast\top}\vx{u}^{\ast}=\vx{G}_{\mu}(\vx{p},s)^{\top}\big{(}\vx{A}_{\mu}+\lambda^{\ast}\vx{I}\big{)}^{-2}\vx{G}_{\mu}(\vx{p},s).$
(29)

Since

$(\vx{A}_{\mu}+\lambda^{\ast}\vx{I})^{-1}\vx{G}_{\mu}(\vx{p},s)=\bmatrix\frac{G_{1\mu}(\vx{p},s)}{e_{11}^{\textcolor{black}{2}}q_{1}+\lambda^{\ast}}\\\
\frac{G_{2\mu}(\vx{p},s)}{e_{11}^{\textcolor{black}{2}}q_{2}+\lambda^{\ast}},$
(30)

the right hand side of the equation in eq:temp22 is equal to
$\tfrac{G_{1\mu}^{2}(\vx{p},s)}{\big{(}e_{11}^{\textcolor{black}{2}}q_{1}+\lambda^{\ast}\big{)}^{2}}+\tfrac{G_{2\mu}^{2}(\vx{p},s)}{\big{(}e_{11}^{\textcolor{black}{2}}q_{2}+\lambda^{\ast}\big{)}^{2}}$.
Therefore, since $\vx{u}^{\ast\top}\vx{u}^{\ast}=\Omega_{\text{SO}}^{2}$, the
constant $\lambda^{\ast}$ satisfies eq:temp22 if the algebraic equation in
eq:algSol holds. Next, we define

$\tilde{\lambda}:=\lambda^{\ast}+\Omega_{1},\tilde{\Omega}:=\Omega_{2}-\Omega_{1},\Omega_{1}:=q_{1}e_{11}^{\textcolor{black}{2}},\text{and}\Omega_{2}:=q_{2}e_{11}^{\textcolor{black}{2}}.$
(31)

Using the definitions in eq:tempn1, the algebraic equation in eq:algSol can be
transformed into the following equivalent quartic equation

$\tilde{\lambda}^{4}+2\tilde{\Omega}\tilde{\lambda}^{3}-\big{[}\tfrac{|\vx{G}_{\mu}(\vx{p},s)|^{2}}{\Omega_{\text{SO}}^{2}}-\tilde{\Omega}^{2}\big{]}\tilde{\lambda}^{2}-2\tilde{\Omega}G_{1\mu}^{2}(\vx{p},s)\tilde{\lambda}-\tilde{\Omega}^{2}=0.$
(32)

Also, using the definitions in eq:tempn1, the control input given by eq:rawSol
can be further simplified to

$\vx{u}^{\ast}(\vx{p},s)=\cases{-}[\frac{G_{1\mu}(\vx{p},s)}{\Omega_{1}},\;\frac{G_{2\mu}(\vx{p},s)}{\Omega_{2}}]^{\top}&\text{if}\;|\vx{u}^{\ast}(\vx{p},s)|<\Omega_{\text{SO}}\\\
-[\frac{G_{1\mu}(\vx{p},s)}{\tilde{\lambda_{0}}},\;\frac{G_{2\mu}(\vx{p},s)}{\tilde{\lambda_{0}}+\tilde{\Omega}}]^{\top}\text{if}\;|\vx{u}^{\ast}(\vx{p},s)|=\Omega_{\text{SO}}$
(33)

where $\tilde{\lambda_{0}}$ is a root of the quartic equation in eq:tempn2.
From a standard continuity argument, it can be deduced that
$\vx{u}^{\ast}(\cdot)$ is continuous for every $\vx{p}\in\mathbb{R}^{2}$ if
and only if

$\tilde{\lambda_{0}}=\Omega_{1}.$ (34)

Hence the pointwise optimal control input $\vx{u}^{\ast}(\cdot)$ is continuous
everywhere if and only if

$\lambda^{\ast}=0.$ (35)

Therefore, $q_{1}=q_{2}=\tfrac{1}{\Omega_{0}e_{11}^{\textcolor{black}{2}}}$,
for some $\Omega_{0}>0$. Consequently, the equation in eq:algSol gets reduced
to

$G_{1\mu}(\vx{p},s)^{2}+G_{2\mu}(\vx{p},s)^{2}=(\lambda^{\ast}+\tfrac{1}{\Omega_{0}})^{2}\Omega_{\text}{SO}^{2},$
(36)

From eq:tempAlg, it can be seen that

$\tfrac{|\vx{G}_{\mu}(\vx{p},s)|}{\Omega_{\text}{SO}}=\lambda^{\ast}+\tfrac{1}{\Omega_{0}}.$
(37)

where $\lambda^{\ast}=0$ due to eq:tempn5. Therefore, when
$|\vx{u}^{\ast}|=\Omega_{\text{SO}}$, the pointwise optimal control input
satisfies

$\vx{u}^{\ast}(\mathbf{p})=(\vx{A}_{\mu}+\lambda^{\ast}\vx{I})^{-1}\vx{G}_{\mu}(\vx{p},s)=\bmatrix\frac{G_{1\mu}(\vx{p},s)}{\tfrac{1}{\Omega_{0}}+\lambda^{\ast}}\\\
\frac{G_{2\mu}(\vx{p},s)}{\tfrac{1}{\Omega_{0}}+\lambda^{\ast}}.$ (38)

blackwhere $\lambda^{\ast}=0$ according to eq:tempn5. Consequently, the
equation in eq:temp44, when $|\vx{u}^{\ast}|=\Omega_{\text{SO}}$, is
equivalent to

$\vx{u}^{\ast}(\mathbf{p},s)=\frac{\Omega_{\text}{SO}}{|\vx{G}_{\mu}(\vx{p},s)|}\bmatrix
G_{1\mu}(\vx{p},s)\\\
G_{2\mu}(\vx{p},s)=\frac{\Omega_{\text}{SO}}{|\vx{G}_{\mu}(\vx{p},s)|}\vx{G}_{\mu}(\vx{p},s).$
(39)

Furthermore, if $|\vx{u}^{\ast}|<\Omega_{\text{SO}}$, then the pointwise
optimal control input is given by
$\vx{u}^{\ast}(\vx{p},s)=-\vx{A}^{-1}_{\mu}\vx{G}_{\mu}(\vx{p},s)$. Under
$q_{1}=q_{2}=\tfrac{1}{\Omega_{0}e_{11}^{\textcolor{black}{2}}}$, we have that
$\mathbf{A}_{\mu}=e_{11}^{\textcolor{black}{2}}q_{1}\mathbf{I}=\tfrac{1}{\Omega_{0}}\mathbf{I}$.
Therefore, if $|\vx{u}^{\ast}|<\Omega_{\text{SO}}$, then
$\vx{u}^{\ast}(\vx{p},s)=-\Omega_{0}\vx{G}_{\mu}(\vx{p},s)$. $\blacksquare$
One of the features of the ODS-based control solution to the microswimmer’s
LFC problem in eq:solFinal is that it is an absolutely continuous function of
the position of the microswimmer. Indeed, the pointwise optimal control input
in eq:solFinal is continuously differentiable for almost all values of the
microswimmer’s position $\mathbf{p}$ and the dynamic variable $s$.
Furthermore, it is a globally Lipschitz function of $\mathbf{p}$ and $s$. The
block diagram of our ODS-based control scheme is depicted in Figure (b) and
our solution to the LFC problem is summarized as follows:


$\displaystyle\frac{n}{k_{n}}\mathbb{P}\left(R_{1}(n)>yb(n/k_{n}),R^{\star}_{1}(n)\leq
yb(n/k_{n})\right)$
$\displaystyle+\frac{n}{k_{n}}\mathbb{P}\left(R^{\star}_{1}(n)>yb(n/k_{n}),R_{1}(n)\leq
yb(n/k_{n})\right)$ $\displaystyle\rightarrow$ $\displaystyle 0,\qquad\text{as
}n\rightarrow\infty,$

by Lemma 6.11. Hence we have proved (62) and the proof is complete. ∎

###  6.5 Consistency of the Hill estimator

In this section, we outline the steps required to obtain Theorem 3.2 from
Theorem 3.1. The steps are standard and closely follow the proof of Theorem
4.2 of [35].

###### Proof of Theorem 3.2.

The proof consists of a series of three steps.
Step 1: We prove that $R_{([k_{n}])}(n)/b(n/k_{n})\xrightarrow{p}1$ as
$n\rightarrow\infty$. The convergence in (17) and inversion [see Proposition
3.2 of 35] gives that as $n\rightarrow\infty$

$\displaystyle\frac{R_{([k_{n}y])}(n)}{b(n/k_{n})}\xrightarrow{p}y^{-1/\alpha}\qquad\text{in
}D(0,\infty].$ (63)

In particular, as $n\rightarrow\infty$

$\displaystyle\frac{R_{([k_{n}])}(n)}{b(n/k_{n})}\xrightarrow{p}1.$ (64)

Additionally,

$\displaystyle\left(\frac{1}{k_{n}}\sum_{i=1}^{n}\epsilon_{R_{i}(n)/b(n/k_{n})},\frac{R_{([k_{n}])}(n)}{b(n/k_{n})}\right)\Rightarrow\left(\nu_{\alpha},1\right)\qquad\text{in
}M_{+}((0,\infty]\times(0,\infty)),$ (65)

as $n\rightarrow\infty$.
Step 2: We now prove the weak convergence of $\hat{\nu}(\cdot)$ in (18). We
consider an operator $T:M_{+}((0,\infty])\times(0,\infty)\mapsto
M_{+}((0,\infty])$ defined by

$\displaystyle T(\mu,c)(A)=\mu(c,A).$ (66)

It is shown in the proof of Theorem 4.2 in [35] that $T$ is continuous at
$(\nu_{\alpha},1)$. Hence, applying the continuous mapping theorem to (65)
gives (18).
Step 3: We now conclude by proving consistency of the Hill estimator. Observe
that

$\displaystyle
H_{k_{n},n}=\int_{1}^{\infty}\hat{\nu}_{n}(y,\infty]\frac{dy}{y}.$

The mapping $f\in
D(0,\infty]\mapsto\int_{1}^{M}f(y)\frac{dy}{y}\in\mathbb{R}_{+}$ is almost
surely continuous so that (18) implies that

$\displaystyle\int_{1}^{M}\hat{\nu}_{n}(y,\infty]\frac{dy}{y}\xrightarrow{p}\int_{1}^{M}\nu_{\alpha}(y,\infty]\frac{dy}{y},$

as $n\rightarrow\infty$. Hence by the second converging together theorem, it
suffices to show that for any $\epsilon>0$

$\displaystyle\lim_{M\rightarrow\infty}\limsup_{n\rightarrow\infty}\mathbb{P}\left(\int_{M}^{\infty}\hat{\nu}_{n}(y,\infty]\frac{dy}{y}>\epsilon\right)=0,$

or, due to (64),

$\displaystyle\lim_{M\rightarrow\infty}\limsup_{n\rightarrow\infty}\mathbb{P}\left(\int_{M}^{\infty}\hat{\nu}_{n}(y,\infty]\frac{dy}{y}>\epsilon,\left|\frac{R_{([k_{n}y])}(n)}{b(n/k_{n})}-1\right|\leq\eta\right)=0,$

for some $\eta>0$. When
$\left|\frac{R_{([k_{n}y])}(n)}{b(n/k_{n})}-1\right|\leq\eta$, however,

$\displaystyle\hat{\nu}_{n}(y,\infty]\leq\nu_{n}(y(1-\eta),\infty].$

Hence by Markov’s inequality, it suffices to show that

$\displaystyle\lim_{M\rightarrow\infty}\limsup_{n\rightarrow\infty}\mathbb{E}\left[\int_{M}^{\infty}\hat{\nu}_{n}(y,\infty]\frac{dy}{y}\right]=0.$
(67)

See that

$\displaystyle\mathbb{E}\left[\int_{M}^{\infty}\hat{\nu}_{n}(y,\infty]\frac{dy}{y}\right]\leq$
$\displaystyle\mathbb{E}\left[\int_{M}^{\infty}\nu_{n}(y(1-\eta),\infty]\frac{dy}{y}\right]$
$\displaystyle=$
$\displaystyle\mathbb{E}\left[\int_{M(1-\eta)}^{\infty}\nu_{n}(y,\infty]\frac{dy}{y}\right]$
$\displaystyle=$
$\displaystyle\int_{M(1-\eta)}^{\infty}\frac{n}{k_{n}}\mathbb{P}\left(R_{1}>yb(n/k_{n})\right)\frac{dy}{y}$
$\displaystyle\rightarrow$
$\displaystyle\int_{M(1-\eta)}^{\infty}y^{-\alpha-1}dy=\frac{1}{\alpha((1-\eta)M)^{\alpha}},$

which tends to $0$ as $M\rightarrow\infty$. Hence (67) holds and the proof is
complete. ∎

D. Cirkovic is supported by NSF Grant DMS-2210735. T. Wang is supported by the
National Natural Science Foundation of China Grant 12301660 and the Science
and Technology Commission of Shanghai Municipality Grant 23JC1400700.

## References

  * [1] [author] Albert, RékaR. and Barabási, Albert-LászlóA.-L. (2002). Statistical mechanics of complex networks. Reviews of Modern Physics 74 47\.
  * [2] [author] Albert, RékaR., Jeong, HawoongH. and Barabási, Albert-LászlóA.-L. (1999). Diameter of the world-wide web. Nature 401 130–131.
  * [3] [author] Barabási, Albert-LászlóA.-L. and Albert, RékaR. (1999). Emergence of scaling in random networks. Science 286 509–512.
  * [4] [author] Barabási, Albert-LászlóA.-L., Albert, RékaR. and Jeong, HawoongH. (2000). Scale-free characteristics of random networks: the topology of the world-wide web. Physica A: Statistical Mechanics and its Applications 281 69–77.
  * [5] [author] Basrak, BojanB. and Planinić, HrvojeH. (2019). A note on vague convergence of measures. Statistics & Probability Letters 153 180–186.
  * [6] [author] Bhattacharjee, ChinmoyC. and Schulte, MatthiasM. (2022). Large degrees in scale-free inhomogeneous random graphs. The Annals of Applied Probability 32 696–720.
  * [7] [author] Bollobás, BélaB., Janson, SvanteS. and Riordan, OliverO. (2007). The phase transition in inhomogeneous random graphs. Random Structures & Algorithms 31 3–122.
  * [8] [author] Britton, TomT., Deijfen, MariaM. and Martin-Löf, AndersA. (2006). Generating simple random graphs with prescribed degree distribution. Journal of Statistical Physics 124 1377–1397.
  * [9] [author] Chung, FanF. and Lu, LinyuanL. (2002). The average distances in random graphs with given expected degrees. Proceedings of the National Academy of Sciences 99 15879–15882.
  * [10] [author] Chung, FanF. and Lu, LinyuanL. (2002). Connected components in random graphs with given expected degree sequences. Annals of Combinatorics 6 125–145.
  * [11] [author] Cirkovic, DanielD. and Wang, TiandongT. (2024). Modeling Random Networks with Heterogeneous Reciprocity. Journal of Machine Learning Research 25 1–40.
  * [12] [author] Cirkovic, DanielD., Wang, TiandongT. and Resnick, Sidney IS. I. (2023). Preferential attachment with reciprocity: Properties and estimation. Journal of Complex Networks 11 cnad031.
  * [13] [author] Clauset, AaronA., Shalizi, Cosma RohillaC. R. and Newman, Mark EJM. E. (2009). Power-law distributions in empirical data. SIAM Review 51 661–703.
  * [14] [author] Das, BikramjitB., Mitra, AbhimanyuA. and Resnick, SidneyS. (2013). Living on the multidimensional edge: seeking hidden risks using regular variation. Advances in Applied Probability 45 139–163.
  * [15] [author] Das, BikramjitB. and Resnick, Sidney IS. I. (2011). Detecting a conditional extreme value model. Extremes 14 29–61.
  * [16] [author] Das, BikramjitB. and Resnick, Sidney IS. I. (2015). Models with hidden regular variation: generation and detection. Stochastic Systems 5 195–238.
  * [17] [author] Das, BikramjitB. and Resnick, Sidney IS. I. (2017). Hidden regular variation under full and strong asymptotic dependence. Extremes 20 873–904.
  * [18] [author] Dorogovtsev, Sergey NS. N., Goltsev, Alexander VA. V. and Mendes, José FFJ. F. (2008). Critical phenomena in complex networks. Reviews of Modern Physics 80 1275\.
  * [19] [author] Downey, Peter JP. J. and Wright, Paul EP. E. (2007). The ratio of the extreme to the sum in a random sequence. Extremes 10 249–266.
  * [20] [author] Drees, HolgerH., Janßen, AnjaA., Resnick, Sidney IS. I. and Wang, TiandongT. (2020). On a minimum distance procedure for threshold selection in tail analysis. SIAM Journal on Mathematics of Data Science 2 75–102.
  * [21] [author] Einmahl, John HJJ. H. and He, YiY. (2023). Extreme value inference for heterogeneous power law data. Available at SSRN 4447938.
  * [22] [author] Einmahl, John HJJ. H., He, YiY. et al. (2022). Extreme Value Inference for General Heterogeneous Data. CentER, Tilburg University.
  * [23] [author] Hill, Bruce MB. M. (1975). A simple general approach to inference about the tail of a distribution. The Annals of Statistics 1163–1174.
  * [24] [author] Hult, HenrikH. and Lindskog, FilipF. (2006). Regular variation for measures on metric spaces. Publications de l’Institut Mathématique 80 121–140.
  * [25] [author] Kallenberg, OlavO. (1973). Characterization and convergence of random measures and point processes. Zeitschrift für Wahrscheinlichkeitstheorie und Verwandte Gebiete 27 9–21.
  * [26] [author] Kulik, RafalR. and Soulier, PhilippeP. (2020). Heavy-tailed time series. Springer.
  * [27] [author] Kunegis, JérômeJ. (2013). Konect: the koblenz network collection. In Proceedings of the 22nd International Conference on World Wide Web 1343–1350.
  * [28] [author] Lindskog, FilipF., Resnick, Sidney I.S. I. and Roy, JoyjitJ. (2014). Regularly varying measures on metric spaces: Hidden regular variation and hidden jumps. Probability Surveys 11 270 – 314. 10.1214/14-PS231
  * [29] [author] Mason, David MD. M. (1982). Laws of large numbers for sums of extreme values. The Annals of Probability 754–764.
  * [30] [author] Mislove, AlanA., Marcon, MassimilianoM., Gummadi, Krishna PK. P., Druschel, PeterP. and Bhattacharjee, BobbyB. (2007). Measurement and analysis of online social networks. In Proceedings of the 7th ACM SIGCOMM Conference on Internet Measurement 29–42.
  * [31] [author] Newman, Mark EJM. E. (2003). The structure and function of complex networks. SIAM Review 45 167–256.
  * [32] [author] Norros, IlkkaI. and Reittu, HannuH. (2006). On a conditionally Poissonian graph process. Advances in Applied Probability 38 59–75.
  * [33] [author] O’Brien, George LG. L. (1980). A limit theorem for sample maxima and heavy branches in Galton–Watson trees. Journal of Applied Probability 17 539–545.
  * [34] [author] Resnick, SidneyS. and Stărică, CătălinC. (1995). Consistency of Hill’s estimator for dependent data. Journal of Applied Probability 32 139–167.
  * [35] [author] Resnick, Sidney IS. I. (2007). Heavy-tail phenomena: probabilistic and statistical modeling. Springer Science & Business Media.
  * [36] [author] Resnick, Sidney IS. I. (2008). Extreme values, regular variation, and point processes 4\. Springer Science & Business Media.
  * [37] [author] Tang, WenpinW. and Tang, FengminF. (2023). The Poisson binomial distribution—Old & new. Statistical Science 38 108–119.
  * [38] [author] van den Esker, HenriH., van der Hofstad, RemcoR. and Hooghiemstra, GerardG. (2008). Universality for the distance in finite variance random graphs. Journal of Statistical Physics 133 169–202.
  * [39] [author] van der Hofstad, RemcoR. (2013). Critical behavior in inhomogeneous random graphs. Random Structures & Algorithms 42 480–508.
  * [40] [author] Van Der Hofstad, RemcoR. (2017). Random graphs and complex networks 43\. Cambridge university press.
  * [41] [author] Voitalov, IvanI., van der Hoorn, PimP., van der Hofstad, RemcoR. and Krioukov, DmitriD. (2019). Scale-free networks well done. Physical Review Research 1 033034\.
  * [42] [author] Wang, TiandongT. and Resnick, SidneyS. (2023). Random networks with heterogeneous reciprocity. Extremes 1–39.
  * [43] [author] Wang, TiandongT. and Resnick, Sidney IS. I. (2019). Consistency of Hill estimators in a linear preferential attachment model. Extremes 22 1–28.
  * [44] [author] Wang, TiandongT. and Resnick, Sidney IS. I. (2023). 2RV+ HRV and Testing for Strong VS Full Dependence. arXiv preprint arXiv:2312.16332.


Knowledge Graph Question Answering using Graph-Pattern Isomorphism

September 2021

A]Daniel Vollmers

A]Rricha Jalota
A,D]Diego Moussallem
A]Hardik Topiwala
A]Axel-Cyrille Ngonga Ngomo
B,C]Ricardo Usbeck

Vollmers et al.
[A]Data Science Group, Paderborn University, Germany
[B]Fraunhofer IAIS, Dresden, Germany
[C]Universität Hamburg, Germany
[D]Globo, Rio de Janeiro, Brazil

Knowledge Graph Question Answering (KGQA) systems are often based on machine learning algorithms, requiring thousands of question-answer pairs as training examples or natural language processing pipelines that need module fine-tuning.
In this paper, we present a novel QA approach, dubbed TeBaQA. Our approach learns to answer questions based on graph isomorphisms from basic graph patterns of SPARQL queries. Learning basic graph patterns is efficient due to the small number of possible patterns.
This novel paradigm reduces the amount of training data necessary to achieve state-of-the-art performance. TeBaQA also speeds up the domain adaption process by transforming the QA system development task into a much smaller and easier data compilation task.
In our evaluation, TeBaQA achieves state-of-the-art performance on QALD-8 and delivers comparable results on QALD-9 and LC-QuAD v1.
Additionally, we performed a fine-grained evaluation on complex queries that deal with aggregation and superlative questions as well as an ablation study, highlighting future research challenges.

Question Answering, Basic Graph Pattern, Isomorphism, QALD

September 2021September 2021

§ INTRODUCTION

The goal of most Knowledge Graph (KG) Question Answering (QA) systems is to map natural language questions to corresponding SPARQL queries.
This process is known as semantic parsing <cit.> and can be implemented in various ways.
A common approach is to utilize query templates (alias graph patterns) with placeholders for relations and entities.
The placeholders are then filled with entities and relations extracted from a given natural language question <cit.> to generate a SPARQL query, which is finally executed.
Semantic parsing assumes that a template can be constructed or chosen to represent a natural language question's internal structure.
Thus, the KGQA task can be reduced to finding a matching template and filling it with entities and relations extracted from the question.

The performance of KGQA systems based on this approach depends heavily on the implemented query templates, which depend on the question's complexity and the KG's topology.
Consequently, costly hand-crafted templates designed for a particular KG cannot be easily adapted to a new domain.

In this work, we present a novel KGQA engine, dubbed TeBaQA.
TeBaQA alleviates manual template generation's effort by implementing an approach that learns templates from existing KGQA benchmarks. We rely on learning of templates based on isomorphic basic graph patterns.

The goal of TeBaQA is to employ machine learning and feature engineering to learn to classify natural language questions into isomorphic basic graph pattern classes.
At execution time, TeBaQA uses this classification to map a question to a basic graph pattern, i.e., a template, which it can fill and augment with semantic information to create the correct SPARQL query.

TeBaQA achieves state-of-the-art performance partially without any manual effort.
In contrast to existing solutions, TeBaQA can be easily ported to a new domain using only benchmark datasets, partially proven by our evaluation over different KGs and train-test-sets. We use a best-effort to work with the data at hand instead of either (i) requiring a resource-intensive dataset creation and annotation process to train deep neural networks or (ii) to hand-craft mapping rules for a particular domain.
Our contributions can be summarized as follows:

* We present TeBaQA, a QA engine that learns templates from benchmarks based on isomorphic basic graph patterns.

* We describe a greedy yet effective ranking approach for query templates, aiming to detect the best matching template for a given input query.

* We evaluate TeBaQA on several standard KGQA benchmark datasets and unveil choke points and future research directions.

The code is available at <https://github.com/dice-group/TeBaQA> and a demo of TeBaQA over encyclopedic data can be found at <https://tebaqa.demos.dice-research.org/>.
We also provide an online appendix which contains more details about our algorithms and their evaluations at <https://github.com/dice-group/TeBaQA/blob/master/TeBaQA_appendix.pdf>.

§ RELATED WORK

The domain of Knowledge Graph Question Answering has gained traction over the last few years. There has been a shift from simple rule-based systems to systems with more complex architectures that can answer questions with varying degrees of complexity. In this section, we provide an overview of the recent work.
We begin with approaches that took part in QALD challenge series <cit.>.

gAnswer2 <cit.> addresses the translation of natural language to SPARQL as a subgraph matching problem.
Following the rule-based paradigm, QAnswer <cit.> utilizes the semantics embedded in the underlying KG (DBpedia and Wikidata) and employs a combinatorial approach to create SPARQL queries from natural language questions. QAnswer overgenerates possible SPARQL queries and has to learn the correct SPARQL query ranking from large training datasets.

Second, we introduce approaches that rely on templates to answer natural questions over knowledge bases.
Hao et al. <cit.> introduced a pattern-revising QA system for answering simple questions. It relies on pattern extraction and joint fact selection, enhanced by relation detection, for ranking the candidate subject-relation pairs.
NEQA <cit.> is a template-based KBQA system like TeBaQA, which uses a continuous learning paradigm to answer questions from unseen domains. Apart from using a similarity-based approach for template-matching, it relies on user feedback to improve over time. QUINT <cit.> also suggests a template learning system that can perform on compositional questions by learning sub-templates.
KBQA <cit.> extracted 27 million templates for 2782 intents and their mappings to KG relations from a QA corpora (Yahoo! Answers).
The way these templates are generated and employed differs from that of TeBaQA. NEQA relies on active learning on sub-parts and thereby, possibly misses the semantic connection between question parts. KBQA learns many templates and can hence fail to generalize well to other domains or KB structures.

In 2019, Zheng et al. <cit.> use structural query pattern, a coarse granular version of SPARQL basic graph patterns which they later augment with different query forms and thus can generate also SPARQL query modifiers.
The closest work to ours is by Athreya et al. <cit.> based on a tree-based RNN to learn different templates on LC-QuAD v1 which the authors directly derive from the LC-QuAD v1 inherent SPARQL templates and thus cannot generalize to other KGs or datasets.
CONQUEST <cit.> is an enterprise KGQA system which also assumes the SPARQL templates are given. It then matches the questions and templates by vectorizing both and training one classifier, namely Gaussian Naïve Bayes.

QAMP <cit.> is an unsupervised message passing system using a similarly simple approach to information extraction as TeBaQA. QAMP outperforms QAnswer on LC-QuAD v1.
Recently, Kapanipathi et al. <cit.> present a system, dubbed NSQA, which is in pre-print. NSQA is based on a combination of semantic parsing and reasoning. Their modular approach outperforms gAnswer and QAnswer on QALD-9 as well as QAnswer and QAMP on LC-QuAD V1.
In contrast to seminal semantic parsing work, e.g., by Berant et al. <cit.>, we assume relatively small training data; thus, learning a generalization via semantic building blocks will not work and consequently learn the whole template on purpose.

Third, there are also other QA approaches which work with neural networks relying on large, templated datasets such as sequence-to-sequence models <cit.>.
However, we do not focus on this research direction in this work. We refer the interested reader to extensive surveys and overview papers such as <cit.>.

§ APPROACH

TeBaQA is based on isomorphic graph patterns, which can be extracted across different SPARQL queries and hence be used as templates for our KGQA approach. Figure <ref> provides an overview of TeBaQA's architecture and its five main stages:

First, all questions run through a Preprocessing stage to remove semantically irrelevant words and create a set of meaningful n-grams.
The Graph-Isomorphism Detection and Template Classification phase uses the training sets to train a classifier based on a natural language question and a SPARQL query by analyzing the basic graph pattern for graph isomorphisms.
The main idea is that structurally identical SPARQL queries represent syntactically similar questions.
At runtime, a question is classified into a ranked list of SPARQL templates.
While Information Extraction, TeBaQA extracts all critical information such as entities, relations and classes from the question and determines the answer type based on a KG-agnostic set of indexes.
In the Query Building phase, the extracted information are inserted into the top templats, the SPARQL query type is determined, and query modifiers are added.
The resulting SPARQL queries are executed, and their answers are compared with the expected answer type.  The subsequent Ranking is based on a combination of all information, the natural language question and the returned answers.

In the following, we present each of these steps in more detail. We use DBpedia <cit.> as reference KG for the sake of simplicity in our description.

TeBaQA architecture on the running example.

§.§ Question Preprocessing

There are often words that do not contribute any information to the answer to natural language questions.
Thus, we distinguish semantically relevant and irrelevant n-grams.
Irrelevant n-grams can lead to errors that could propagate through the architecture.
An example of this is the entity <dbr:The_The>[ is a prefix which stands for <http://dbpedia.org/resource/>]. If the word The were to be wrongly associated with this entity every time the occurs in a question, the system's performance would decrease severely.
However, irrelevant words are sometimes part of entities, e.g., <dbr:The_Two_Towers>, so we cannot always filter these words.
For this reason, we combine up to six neighboring words from the question to n-grams and remove all n-grams that contain stop words only.
To identify irrelevant words, we provide a stop word list that contains the most common words of a particular language that are highly unlikely to add semantic value to the sentence.
Additionally, TeBaQA distinguishes relevant and irrelevant n-grams using part-of-speech (POS) tags. Only n-grams beginning with |JJ|, |NN| or |VB| POS-tags are considered as relevant.
After this preprocessing step, TeBaQA maps the remaining n-grams to entities from DBpedia in the information extraction step.

§.§ Graph-Isomorphism Detection and Template Classification

TeBaQA classifies a question to determine each isomorphic basic graph pattern (BGP).
Since SPARQL is a graph-based query language <cit.>, the structural equality of two SPARQL queries can be determined using an isomorphism.
At runtime, TeBaQA can classify incoming questions to find the correct query templates, in which later semantic information can be inserted at runtime.

§.§.§ SPARQL BGP Isomorphism to Create Template Classes:

Using the training datasets, TeBaQA generates one basic graph pattern for each given question and its corresponding SPARQL query, see Figure <ref>.
Subsequently, all isomorphic SPARQL queries are grouped into the same class.
Now, each class contains semantically different natural language questions but structurally similar SPARQL queries.

[iri,anchor=center] (a) <ent>;
[var,anchor=center,right=2cm of a] (b) ?uri
edge[arrin] node[lab] <pred> (a);
[numcirc,left=0.2cm of a] 1;

[iri,anchor=center] (a) <ent>;
[var,anchor=center,right=2cm of a] (b) ?uri
edge[arrin] node[lab] <pred> (a);
[iri,anchor=center,right=2cm of b] (c) <ent2>
edge[arrin] node[lab] <pred2> (b);
[numcirc,left=0.2cm of a] 2;

[var,anchor=center] (a) ?uri;
[iri,anchor=center,right=2cm of a] (b) <ent>
edge[arrin] node[lab] <pred> (a);
[iri,anchor=center,below=0.8cm of a] (c) <ent2>
edge[arrin] node[lab] <pred2> (a);
[numcirc,left=0.2cm of a] 3;

[var,anchor=center] (a) ?x;
[iri,anchor=center,right=2cm of a] (b) <ent>
edge[arrin] node[lab] <pred> (a);
[iri,anchor=center,below=0.8cm of a] (c) <ent2>
edge[arrin] node[lab] <pred2> (a);
[var,anchor=center,below=0.8cm of b] (c) ?uri
edge[arrin] node[lab] <pred3> (a);
[numcirc,left=0.2cm of a] 5;

[iri,anchor=center] (a) <ent>;
[iri,anchor=center,below=0.8cm of a] (b) <ent2>
edge[arrin] node[lab] <pred> (a);
[numcirc,left=0.2cm of a] 6;

[var,anchor=center] (a) ?x;
[iri,anchor=center,right=2cm of a] (b) <ent>
edge[arrin] node[lab] <pred> (a);
[var,anchor=center,below=0.8cm of a] (c) ?uri
edge[arrin] node[lab] <pred2> (a);
[numcirc,left=0.2cm of a] 8;

[iri,anchor=center] (a) <ent>;
[var,anchor=center,right=2cm of a] (b) ?child
edge[arrin] node[lab] <pred> (a);
[var,anchor=center,right=2cm of b] (c) ?uri
edge[arrin] node[lab] <pred2> (b);
[numcirc,left=0.2cm of a] 4;

[var,anchor=centerr,below=0.8cm of a] (a1) ?uri;
[iri,anchor=center,right=2cm of a1] (b1) <ent>
edge[arrin] node[lab] <pred> (a1);
[numcirc,left=0.2cm of a1] 7;

All basic graph patterns used as classes for QALD-8 and QALD-9  which later become templates. Note, the depicted templates contain more than five examples in the training dataset. Our running example, "Who was the doctoral advisor of Albert Einstein?" belongs to template (1).

Two labeled graphs are isomorphic when a 1:1 relationship and surjective function is present between the nodes of the graphs, wherein the node labels, edge labels, and neighborhood relationships are preserved by the mapping <cit.>.

§.§.§ Question Features and Classification

Next, TeBaQA trains a classifier that uses all questions of an isomorphism class as input to calculate features for this class.  A feature vector holds all the information required to make a reliable statement about which question belongs to which class. The features can be seen in Table <ref>.

Features to map a question to an isomorphic basic graph pattern.

Feature     Type     Description

QuestionWord     Nominal     Adds the question word (e.g. Who, What, Give) as a feature.

EntityPerson     Boolean     Checks the named entity tags of the sentence to see if any persons are mentioned in it.

NumberOfToken     Numeric     Stores the number of tokens separated by spaces excluding punctuation.

QueryResourceType     Nominal     Categorizes the question based on a list of subject areas, e.g., film, music, book or city.

Noun     Numeric     Aggregates the number of nouns.

Number     Numeric     Indicates how often numbers occur in the question.

Verb     Numeric     Aggregates the number of verbs.

Adjective     Numeric     Aggregates the number of adjectives.

Comperative     Boolean     Indicates whether comparative adjectives or adverbs are included in the sentence.

TripleCandidates     Numerical     Estimates how many SPARQL triples are needed to answer the question based on the number of verbs, adjectives, and related nouns.

The features can be divided into semantic and syntactic features. QuestionWord, EntityPerson and QueryResourceType form the group of semantic features and represent particular content aspects of the question, e.g., persons or specific topics that are mentioned in the question. All other features describe the structure of the question.

Note, other features were investigated, which did not improve the model's recognition rate.
We report these features to aid future research in this area: 1) Cultural Categories: Mainly included music and movies, e.g., Who is the singer on the album The Dark Side of the Moon? and 2) Geographical entities: Questions in which countries or cities occur, as well as where questions, e.g., In which country is Mecca located?

Using features above, it is possible to represent the question Who was the doctoral advisor of Albert Einstein? with the following vector:
[captionpos=b, basicstyle=,frame=single,basicstyle=]

TeBaQA trains a statistical classifier using the described features extracted from the input question and the isomorphic basic graph patterns as class labels.
A feature vector's target class can be determined by generating the basic graph pattern for the corresponding SPARQL query and assigning the class, which represents this pattern.
An evaluation can be found in Section <ref>.

§.§ Information Extraction

TeBaQA identifies entities, classes, and relations to fill the placeholders of a particular SPARQL template.
Since questions are shorter than usual texts, semantic entity linking tools such as DBpedia Spotlight <cit.> or MAG <cit.> do not perform correctly due to the lack of semantic context information.
For example, in Who was the doctoral advisor of Albert Einstein?, the word Einstein has to be linked to <dbr:Albert_Einstein> and not to any other person with that name.
For this reason, we apply a KB-agnostic search index-based approach to identify entity, relation and class candidates.  TeBaQA uses three indexes, which are created before runtime.

§.§.§ Entity Index
The entity index contains all entities from the target knowledge graph. To map an n-gram from the preprocessing step to an entity, TeBaQA queries against the index's label field. The index contains information about entities, relations and classes connected to the entity at hand.

§.§.§ Relation Index and Class Index

These two indexes contain all OWL classes and relations from a KG. The indexes are used to map n-grams to relations and classes of the ontologies of the KB.TeBaQA additionally indexes hypernyms and synonyms for all relations and classes.[The dictionary can be found at <https://github.com/dice-group/NLIWOD/tree/master/qa.annotation/src/main/resources> which was previously used by <cit.>]

Consider the question Who was the doctoral mentor of Einstein?. DBpedia contains only the relation <dbo:doctoralAdvisor>[<dbo:> stands for <http://dbpedia.org/ontology/>] and not <dbp:mentor>[<dbp:> stands for <http://dbpedia.org/property/>].
Through the synonym advisor of mentor, the relation <dbo:doctoralAdvisor> can be determined.
This example highlights the lexical and semantic gap between natural language and knowledge graphs.

§.§.§ Disambiguation

By querying the indexes for an n-gram, we get candidates for entities, relations and classes, whose labels contain all tokens of the n-gram.
Since a candidate's label may contain more tokens than the n-gram, we apply a Levenshtein-distance filter of 0.8 on the candidates.
All remaining candidates are used to fill a given template.

§.§ Query Building

§.§.§ Template Filling

For filling the templates, we facilitate the information about connected entities and connected relations for the found entities from the entity-index.
For the triples in a template, there are two cases:

1.) The triple contains one placeholder for an entity and one placeholder for a relation.
In this case, we resort to only the connected relation information from the entity index.
An entity candidate $e$ and a relation candidate $p$ are combined to a triple $<e,p,?v>$ or $<?v,p,e>$ if the set of connected relations $S(e)$ of the entity $e$ contains $p$ and if the connected n-grams do not contain each other.

2.) The triple contains only one placeholder for a relation $p'$. This case only occurs when at least one triple in the template matches case 1. We can utilize these triples to generate matching triples for the given triple.
Thus, we query the entity index and search for a set of entities $S(e')$ connected with the entity $e$ by the relation $p$.
All connected relations from the entities in $S(e')$ in the set of relation candidates and whose n-grams do not cover the n-grams of $e$ and $p$ are candidates for $p'$.

Each candidate SPARQL query is checked for consistency with the ontology. In general, there are query patterns that do not contain variables. This case only occurs in ask queries like Did Socrates influence Aristotle?. We ignore this case to keep simplicity and aware of the performance impact. To summarize, TeBaQA creates several candidate SPARQL queries per template and thus per question.

§.§.§ Query Modifiers and Query Types

To translate a question into a semantically equivalent SPARQL query, it is often not enough to recognize the entities, relations or classes in the question and insert them into a SPARQL query. For example, the question How many children did Benjamin Franklin have? asks for the number of children and not the concrete list.
Thus, we apply a rule-based look-up to add query modifiers and choose a query type. The supported modifiers are $COUNT$, if the question contains keywords like How many or How much, $Filter (?x<?y)$, if we identify comparatives and $ORDER\: BY\: [ASC (?x)\:  |\: DESC (?x)]\: LIMIT \:1$, if the question contains superlatives. Additionally, we support ASK-type questions, if keywords like Is or Are are identified.

Note, the templates and their respective basic graph pattern neither contain information about the query type nor information about query modifiers.
Thus, TeBaQA generates one SPARQL query per candidate SPARQL query for each cross-product of query type and modifier that is recognized.
The outcome is a list of executable queries for each input question.

§.§ Ranking

Since the conciseness of an answer plays a decisive role in QA in contrast to full-text search engines, only the answer that corresponds best to the user's intention should be returned.
Thus, all generated SPARQL queries and their corresponding answers are ranked.
This ranking is carried out in two steps.
First, we filter by 1) the expected answer type of the question in comparison to the actual answer type of the query and by 2) the cardinality of the result set. Second, TeBaQA ranks the quality of the remaining SPARQL queries.

§.§.§ Answer Type and Cardinality Check:

For certain types of answer sets, only those that match the question's expected answer type are considered for the next ranking step.
We empirically analyzed the benchmark datasets and derived a rule-based system for the most common expected answer type and their distinguishing features.

* Temporal questions usually begin with the question word When, e.g., When was the Battle of Gettysburg?. TeBaQA expects a date as the answer type.

* Decision questions mostly start with a form of Be, Do or Have. The possible answer type is boolean.

* Questions that begin with How much or How many can be answered with numbers. This also includes questions that begin with a combination of the question word How and a subsequent adjective such as How large is the Empire State Building?

If none of the above rules apply to a question, the result set's cardinality is checked. There are two cases:
First, when several answers are needed to answer a question fully. Consider Which ingredients do I need for carrot cake?, if only one answer is found for this question, it can be assumed that it is either wrong or incomplete.
Second, when there is only one answer to a question, e.g., In which UK city are the headquarters of the MI6?, an answer consisting of several entities would not be correct.

To recognize to which query type (ASK or SELECT) a question belongs, the first noun or the first compound noun after the question word is checked.
If they occur in the singular form, a single answer is needed to answer the question. For the above question In which UK city are the headquarters of the MI6?, the compound noun would be UK city. Since both words occur in the singular, it is assumed that only a single answer is required.
If the first noun or group of nouns occurs in the plural, this indicates that the question requires multiple answers. In the question Which ingredients do I need for carrot cake? the decisive word ingredients is in the plural.

However, the answer type of question may not be recognized correctly. For instance, if the question is grammatically correct but words whose singular form is identical to the plural form exist, such as news, we cannot determine the correct answer type. These issues will be tackled in future research.

Once the type of question and answer has been determined, all the answers whose type or cardinality does not match the question will be discarded.

§.§.§ Quality Ranking:

For the remaining SPARQL queries, TeBaQA calculates a $rating$ based on the sum of the individual scores of the bindings $B$ and the input question $phrase$. A binding $B$ is the mapping of entities, relations and classes to placeholders contained in one SPARQL query $q$.  To compute the relatedness factor $r$, the following factors are taken into account:

* Annotation Density: The annotation density measures that the more words from the sentence are linked to an entity, class or relation, the more likely it is that it corresponds to the intention of the user.  For the question What is the alma mater of the chancellor of Germany Angela Merkel? one candidate query may apply the binding <dbr:Angela>, while another query applies the binding <dbr:Angela_Merkel>. The former refers only to the word Angela. The latter refers to two words of the sentence: Angela Merkel and covers longer parts of the $phrase$.

* Syntactic Similarity: The syntactic similarity is an indicator of how similar a n-gram of the sentence and the associated binding are. For example, in the question Who is the author of the interpretation of dreams? the n-gram the interpretation of dreams can be linked with <dbr:The_Interpretation_of_Dreams> or <dbr:Great_Book_of_Interpretation_of_Dreams> among others. The former has a smaller Levenshtein distance and a greater syntactic similarity with the selected n-gram.

We cover both aspects with the following formulas:

\[ rating = \sum_{B \in q} r(B, phrase)\]

\[r(entity, phrase) = |words(phrase)| - levenshtein\_ratio(label(B), phrase)\]

After all entities, classes, and relations used in a query have been evaluated and summed up, the rating is corrected down by 30% if more than 50 results are returned by the query, based on empirical observations in the datasets.

§ EVALUATION

§.§ Datasets

We performed the evaluation on the 8th and 9th Question Answering over Linked Data challenge training datasets (QALD-8 train <cit.> and  QALD-9 train <cit.>), which contain 220 (QALD-8) and 408 (QALD-9) heterogeneous training questions. Additionally, we evaluated on the two LC-QuAD <cit.> datasets with 4000 train and 1000 test questions and 24.000 train and 6.000 test questions, respectively. Across datasets, the questions vary in complexity since they also include comparatives, superlatives, and temporal aggregations. An example of a simple question is How tall is Amazon Eve?. A more complex example is How many companies were founded in the same year as Google? since it contains a temporal aggregation (the same year).
We created separate instances of TeBaQA for each of the training datasets and evaluated each instance on the corresponding test dataset.

§.§ Classification Evaluation

For the QALD-8 and QALD-9 datasets, eight classes were identified for each dataset, compare Figure <ref>.
For LC-QuAD v1 and LC-QuAD v2, TeBaQA identified 17 classes for both datasets. Since the two LC-QuAD datasets were constructed for more diversity, the classification is more challenging.
Note, we omitted classes with less than five examples in the training dataset. We are aware that we are trading our overall performance for classification accuracy.

To this end, we evaluated a variety of machine learning methods, which required questions to be converted into feature vectors.
In particular, we used the QALD-8 and QALD-9 training datasets as our training data and used 10-fold cross-validation to evaluate the computed models.
All duplicate questions and questions without SPARQL queries were removed from the training datasets.
We tested multiple machine learning algorithms with the WEKA framework[<https://www.cs.waikato.ac.nz/ml/weka/>] <cit.> on our training data using 10-fold cross-validation.
To achieve comparable results, TeBaQA uses only the standard configuration of the algorithms.
The macro-weighted F-Measure for one fold in cross-validation is calculated from the classes' F-Measures, weighted according to the size of the class.
After that, we calculated the average macro-weighted F-Measure across all folds.
On the QALD datasets, the algorithm RandomizableFilteredClassifier achieves the highest F-Measures of 0.523964 (QALD-8) and 0.528875 (QALD-9), respectively.
On LC-QuAD v1, we achieve a template classification f-measure of 0.400464 and 0.425953 on LC-QuAD v2
using a MultilayerPerceptron.
Consequently, we use the best performing classifiers for the end-to-end evaluation.

Similar experiments can be found in Athreya et al.'s work <cit.>.
The authors use a recurrent neural network, i.e., a tree-LSTM, to identify templates in LC-QuAD and achieve an accuracy of 0.828 after merging several template classes manually.

§.§ GERBIL QA Benchmark

For evaluation, we used the FAIR benchmarking platform GERBIL QA <cit.> to ensure future reproducibility of the experiments.

Table <ref> contains the results of selected Question Answering systems, measured against the QALD-8 and the QALD-9 test benchmarks[The links to our GERBIL-experiments can be found on our Github page: <https://github.com/dice-group/TeBaQA/blob/master/README.md>]. We focused on English questions only, as English is supported by all available QA systems at the time of these experiments. The macro value for Precision, Recall and F-Measure was selected. The evaluation was performed with GERBIL version 0.2.3 if possible. We report always the highest numbers if several papers reported numbers and evaluation with GERBIL was not possible.

Results of TeBaQA and other state-of-the-art QA systems for multiple datasets. * indicates F-1 measure instead of QALD F-Measure <cit.>. ** Numbers taken from the corresponding paper.

Precision     Recall      QALD  F-Measure     Avg. Time in s

gAnswer2 <cit.>     DBpedia    QALD-8        0.337     0.354     0.440    	4.548

QAnswer <cit.>     DBpedia    QALD-8         0.452     0.480     0.512     0.446

Zheng et al. <cit.>**         DBpedia    QALD-8    0.459      0.463    * 0.461    -

TeBaQA     DBpedia    QALD-8     0.476    	0.488     0.556     28.990

Elon <cit.>      DBpedia       QALD-9    0.049     0.053     0.100     0.219

gAnswer <cit.>     DBpedia     QALD-9     0.293     0.327     0.430     3.076

NSQA <cit.>**     DBpedia    QALD-9     0.314     0.322     *0.453     -

QAnswer <cit.>     DBpedia     QALD-9    0.261     0.267     0.289     0.661

QASystem <cit.>     DBpedia     QALD-9    0.097     0.116     0.200     1.014

Zheng et al. <cit.>**         DBpedia    QALD-9    0.458      0.471     *0.463    -

TeBaQA       DBpedia    QALD-9     0.241     0.245     0.374     5.049

NSQA <cit.>**           DBpedia    LC-QuAD v1    0.382       0.404       *0.383     -

QAMP <cit.>**              DBpedia    LC-QuAD v1     0.250      0.500       *0.330     0.720

QAnswer <cit.> **          DBpedia    LC-QuAD v1      0.590      0.380      *0.460       1.500

TeBaQA                                                  DBpedia    LC-QuAD v1   0.230     0.229     0.300     36.000

TeBaQA      Wikidata    LC-QuAD v2     0.140     0.136     0.227      –

On the QALD-8 benchmark, TeBaQA achieved the best results in terms of F-Measure by 5% QALD F-measure. Our average time is significantly larger than the other reported systems since the ranking mechanism gets activated and then fires several SPARQL queries after the initial null-retrieving SPARQL query.

On QALD-9, TeBaQA is in fourth place with a QALD F-Measure of 0.37. This implies that TeBaQA achieves comparable or partially better results than other semantic QA systems with a wide margin of possible improvements, as shown in the ablation study.
QALD-9 is a more challenging benchmark than QALD-8 since it contains many questions that require complex queries with more than two triples.
A more in-depth analysis shows that questions from QALD-9 often require complex templates that are not contained in the training queries or have only low support in the training set <cit.>. This mismatch leads to a high number of misclassifications and explains the limited performance on QALD-9 compared to QALD-8 and, thus, its limited generalization abilities to unseen templates.
Although we are not outperforming the state-of-the-art systems on QALD-9, TeBaQA a novel research avenue w.r.t. learning from data.

On the LC-QuAD dataset, which contains the most complex questions, TeBaQA achieves an F-Measure of 0.30. We ran this benchmark only once in our system and had some errors during runtime. We will further investigate the performance on LC-QuAD in our future research.
Note, we ran LC-QuAD only once through the system to test our independence of the dataset similar to the methodology of Berant et al. <cit.>.

To the best of our knowledge and after reaching out to the authors of LC-QuAD, we are the first system to evaluate on LC-QuAD v2. Since LC-Quad v2 uses Wikidata instead of DBpedia, we generated separate indexes for the Wikdata KG. The rest of the system remained unchanged. This shows, that TeBaQA can be easily adapted to other Knowledge Graphs.

§.§ SPARQL operation modifiers

The Achilles heel of most QA systems is their inability to deal with SPARQL operation modifiers, e.g., questions involving aggregations or superlatives <cit.>.
In contrast to those other systems, TeBaQA contains functionalities to identify the query type and other modifiers.
We analyzed the results of TeBaQA on these benchmark questions and found that TeBaQA was able to answer many of those questions, while other systems like QAswer and gAnswer fail on this; see supplementary material.

§.§ Ablation Study

Ablation study for TeBaQA on the QALD-9 test benchmark.

QA System                 Precision     Recall      Avg. Time     QALD F-Measure

Perfect classification     0.205     0.210     4.618     0.337

Perfect classification + EL     0.407     0.407     0.355     0.578

Perfect classification + ranking     0.245     0.257     4.029     0.399

Perfect EL     0.301     0.317     0.713     0.473

Perfect EL + ranking      0.302     0.320     0.653     0.477

Perfect ranking     0.258     0.270     6.281     0.405

Perfect classification + EL + ranking     0.407     0.407     0.251     0.578

We performed an ablation study to find the modules of TeBaQA's pipeline, which influence the end-to-end performance the most. Since the number of possible entities is roughly a magnitude larger than the number of relations and for the sake of experiment time, we omitted to test for perfect relation and class linking.

For the perfect classification experiment, the QALD F-Measure is lower than for the overall system, see Table <ref>.
Investigating the detailed outputs, TeBaQA selects the simple templates containing only one triple more often than the more complex templates because they have more instances, i.e., support, on the QALD-9 train dataset. In many cases, a simple query generates a result set that is a superset of the target result set and, in consequence, decreases the precision.

When TeBaQA fails to fill the correct complex template with the correct entities, the query result set is often disjoint from the target result set.
It is also reasonable that TeBaQA fails to fill the more complex templates due to missing or incorrect entity links.

Still, there is a gap in the system, which becomes evident when looking at the perfect classification plus ranking. Ranking gets only activated if the perfect template filled with semantic information does not retrieve any answer. That is, TeBaQA fails to find the correct modifiers or needs to circle through other semantic information candidates.

When the perfect classification is combined with perfect entity linking, the results reach a QALD F-measure of 0.58, which clearly would outperform any other system. The same happens if we add the perfect ranking. The results are the same in both cases because the ranking is most often not triggered since the perfect template is already filled correctly.

The strongest, single influence is the entity linking part, enabling TeBaQA to jump to 0.47 F-measure. We will tackle this challenging module in future work.

Regarding runtime, failing to find the perfect template and then iterating through the ranking, i.e., querying the SPARQL endpoint often, increases the average time needed significantly.

§ SUMMARY AND FUTURE WORK

We presented TeBaQA, a QA system which learns to map question to SPARQL template mappings using basic graph pattern isomorphisms.
TeBaQA significantly eases the domain/KB adoption process as it relies only on a benchmark dataset at its core.

In the future, we will evaluate TeBaQA on more heterogeneous KG benchmarks to identify further choke points. We will also improve the question classification and information extraction by using novel deep learning mechanism.

Acknowledgements We acknowledge the support of the Federal Ministry for Economic Affairs and Energy (BMWi) project SPEAKER (FKZ 01MK20011A), ScaDS.AI (01/S18026A) as well as the Fraunhofer Zukunftsstiftung project JOSEPH and the Eurostars Project PORQUE (FKZ 01QE2056C). This work was partially supported by the German Federal Ministry of Transport and Digital Infrastructure (BMVI) in the project LIMBO (no. 19F2029I) and by the German Federal Ministry of Education and Research (BMBF) in the project SOLIDE (no. 13N14456) within ’KMU-innovativ: Forschung für die zivile Sicherheit’ in particular ’Forschung für die zivile Sicherheit’.