The quantity $(-I_{6}^{\text{inflow,$E_{4}X_{8}$}})^{\text{polar caps}}_{k=1}$
is simply (B.1) evaluated for $k=1$, with the convention that the sums over
$i$ with range $1$ to $k-1$ be simply dropped. The quantity
$(-I_{6}^{\text{inflow,$E_{4}X_{8}$}})^{\text{$S^{4}$}}$ is the $E_{4}X_{8}$
contribution to anomaly inflow for an (unorbifolded) $S^{4}$ fibered over the
Riemann surface. The rationale behind (122) is that the central region can be
obtained starting from $S^{4}$ and removing the polar caps without orbifold,
which are captured as the special case $k=1$ of the computation of the
previous subsection.

The quantity $(-I_{6}^{\text{inflow,$E_{4}X_{8}$}})^{\text{$S^{4}$}}$
corresponds to a special case of the Bah-Beem-Bobev-Wecht (BBBW) setup
Bah:2012dg , which is in general parameterized by two integer twist parameters
$q_{1}$, $q_{2}$, subject to the constraint $q_{1}+q_{2}=-\chi/2$. In this
work, we are turning off the flavor twist parameter $\zeta$ (governing a twist
of the $\varphi$ isometry along the Riemann surface), which corresponds to the
case $q_{1}=q_{2}=-\chi/2$. Both the $E_{4}^{3}$ and the $E_{4}X_{8}$
contributions to anomaly inflow were studied for general $q_{1}$, $q_{2}$ in
Bah:2019rgq , with the results

$\displaystyle(-I_{6}^{\text{inflow, $E_{4}^{3}$}})^{\text{$S^{4}$}}$
$\displaystyle=\frac{2}{3}\,N^{3}\,(q_{1}\,n_{1}\,n_{2}^{2}+q_{2}\,n_{2}\,n_{1}^{2})\
,$ (123) $\displaystyle(-I_{6}^{\text{inflow,
$E_{4}X_{8}$}})^{\text{$S^{4}$}}$
$\displaystyle=-\frac{N}{24}\,(q_{1}\,n_{1}+q_{2}\,n_{2})\,p_{1}(TW_{4})+\frac{N}{6}\,(q_{1}\,n_{1}^{3}+q_{2}\,n_{2}^{3})$
$\displaystyle\phantom{=\
}-\frac{N}{6}\,(q_{1}\,n_{1}\,n_{2}^{2}+q_{2}\,n_{2}\,n_{1}^{2})\ .$

The quantities $n_{1}$, $n_{2}$ are the first Chern classes of the external
gauge fields associated with the $U(1)^{2}$ isometry of the $S^{4}$ fibration
over $\Sigma_{g}$ that is visible for generic $q_{1}$, $q_{2}$. The relation
to the background fields $F_{2}^{\psi}$, $F_{2}^{\varphi}$ considered in this
work is

$n_{1}=\frac{1}{4}\,\frac{F_{2}^{\psi}}{2\pi}+\frac{1}{2}\,\frac{F_{2}^{\varphi}}{2\pi}\
,\qquad
n_{2}=\frac{1}{4}\,\frac{F_{2}^{\psi}}{2\pi}-\frac{1}{2}\,\frac{F_{2}^{\varphi}}{2\pi}\
.$ (124)

We are now in a position to write down the final answer for the $E_{4}X_{8}$
contribution to anomaly inflow. This quantity is the sum of (B.1) and (122),
with $(-I_{6}^{\text{inflow,$E_{4}X_{8}$}})^{\text{$S^{4}$}}$ extracted from
(123) with the identifications (124) and $q_{1}=q_{2}=-\chi/2$. In conclusion,
we arrive at

$\displaystyle-I_{6}^{\text{inflow, $E_{4}X_{8}$}}$
$\displaystyle=-\frac{N\,\chi}{24}\,\frac{F_{2}^{\psi}}{2\pi}\,\bigg{(}\frac{F_{2}^{\varphi}}{2\pi}\bigg{)}^{2}+\frac{N\,\chi}{24}\,\bigg{[}3\,\bigg{(}\frac{F_{2}^{\psi}}{2\pi}\bigg{)}^{2}-p_{1}(TW_{4})\bigg{]}\,\sum_{i=1}^{k-1}\bigg{(}\frac{F_{2}^{\mathrm{N}_{i}}}{2\pi}-\frac{F_{2}^{\mathrm{S}_{i}}}{2\pi}\bigg{)}$
$\displaystyle\phantom{=\
}+\frac{F_{2}^{\psi}}{2\pi}\,p_{1}(TW_{4})\,\bigg{[}-\frac{N\,\chi}{96}\,(k^{2}-2)+\frac{1}{12}\,\sum_{i=1}^{k-1}\Big{(}N_{\widetilde{\beta}_{i}}+N_{\widetilde{\gamma}_{i}}\Big{)}\bigg{]}$
$\displaystyle\phantom{=\
}+\bigg{(}\frac{F_{2}^{\psi}}{2\pi}\bigg{)}^{3}\,\bigg{[}\frac{N\,\chi}{48}\,(k^{2}-1)-\frac{1}{6}\,\sum_{i=1}^{k-1}\Big{(}N_{\widetilde{\beta}_{i}}+N_{\widetilde{\gamma}_{i}}\Big{)}\bigg{]}\
.$ (125)

###  B.3 Comparison with Bah:2019vmq

The full inflow anomaly polynomial $-I_{6}^{\rm inflow}$ for general $k$,
including the $E_{4}X_{8}$ contribution evaluated above, agrees with the
results of Bah:2019vmq  for $k=2$. To verify this, one needs to perform a
redefinition of flux parameters and external gauge fields. The quantities in
Bah:2019vmq  are related to those in this paper and Bah:2021brs  as in the
following table.

notation of Bah:2019vmq  |  | notation of this work and Bah:2021brs
---|---|---
$N_{\mathrm{N}}$ | $=$ | $-N_{\mathrm{S}_{1}}$
$N_{\mathrm{S}}$ | $=$ | $+N_{\mathrm{N}_{1}}$
$c_{1}^{\mathrm{N}}$ | $=$ | $\displaystyle-\frac{F_{2}^{\mathrm{S}_{1}}}{2\pi}+\frac{(N\,\chi-N_{\mathrm{S}_{1}})(N\,\chi-N_{\mathrm{N}_{1}}-N_{\mathrm{S}_{1}})}{2\,N\,\chi\,(2\,N\,\chi-N_{\mathrm{N}_{1}}-N_{\mathrm{S}_{1}})}\,\frac{F_{2}^{\psi}}{2\pi}$
$c_{1}^{\mathrm{S}}$ | $=$ | $\displaystyle+\frac{F_{2}^{\mathrm{N}_{1}}}{2\pi}+\frac{(N\,\chi-N_{\mathrm{N}_{1}})(N\,\chi-N_{\mathrm{N}_{1}}-N_{\mathrm{S}_{1}})}{2\,N\,\chi\,(2\,N\,\chi-N_{\mathrm{N}_{1}}-N_{\mathrm{S}_{1}})}\,\frac{F_{2}^{\psi}}{2\pi}$
$c_{1}^{\psi}$ | $=$ | $\displaystyle\frac{1}{2}\,\frac{F^{\psi}}{2\pi}$
$p_{1}^{\varphi}$ | $=$ | $\bigg{(}\displaystyle\frac{F_{2}^{\varphi}}{2\pi}\bigg{)}^{2}$

##  Appendix C Anomaly inflow computation for the torus case

We derive in this appendix the $E_{4}^{3}$ contribution to the inflow anomaly
polynomial, $I_{6}^{\text{inflow,$E_{4}^{3}$}}$, for the case of genus one,
following the general philosophy adopted by Bah:2021brs  for the construction
of the higher-genus inflow anomaly polynomial. We are going to describe only
the essential elements which distinguish this computation from the original
one, and we refer the reader to Bah:2021brs  for a detailed discussion of the
formalism.

The Euler characteristic of the torus is $\chi=2-2g=0$, so it makes the
topological twist of the $\mathrm{U}(1)_{\psi}$ bundle trivial while
preserving $\mathcal{N}=1$ supersymmetry Bah:2015fwa ; Bah:2017wxp .
Specifically, the global angular forms associated with the isometries reduce
respectively to

$(D\psi)^{\mathrm{g}}=d\psi+A_{1}^{\psi}\,,\qquad(D\varphi)^{\mathrm{g}}=d\varphi-L\,(d\psi+A_{1}^{\psi})+A_{1}^{\varphi}\,.$
(126)

Cohomology class representatives of $H^{2}(M_{6})$ and $H^{4}(M_{6})$ can be
written as

$\displaystyle\omega_{2,\alpha}$
$\displaystyle=(dW_{0,\alpha}^{\psi}+L\,dW_{0,\alpha}^{\varphi})\wedge\frac{d\psi}{2\pi}+dW_{0,\alpha}^{\varphi}\wedge\frac{D\varphi}{2\pi}+W_{0,\alpha}^{\Sigma}V_{2}^{\Sigma}\,,$
(127) $\displaystyle\Omega_{4}^{\alpha}$
$\displaystyle=dT_{1}^{\alpha}\wedge\frac{d\psi}{2\pi}\wedge\frac{D\varphi}{2\pi}+(dU_{0,\psi}^{\alpha}+L\,dU_{0,\varphi}^{\alpha})\wedge\frac{d\psi}{2\pi}\wedge
V_{2}^{\Sigma}+dU_{0,\varphi}^{\alpha}\wedge\frac{D\varphi}{2\pi}\wedge
V_{2}^{\Sigma}\,,$ (128)

where $W_{0,\alpha}^{\Sigma}$ is a constant such that $\omega_{2,\alpha}$ is
closed. Note especially that the expression for $\Omega_{4}^{\alpha}$ is not
the same as the naïve $\chi=0$ limit of (B.17) in Bah:2021brs , otherwise the
flux quanta $N_{i}=\int_{\mathcal{C}_{4,i}}N_{\alpha}\Omega_{4}^{\alpha}$ for
$i=1,2,\dots,2k$ are ill-defined. This is also necessary so as to recover the
sum rules,

$\sum_{i=1}^{2k}a_{i}^{\alpha}=0\,,\qquad\sum_{i=1}^{2k}\ell_{i}a_{i}^{\alpha}=0\,,$
(129)

that are consistent with their higher-genus cousins. As a reminder, we choose
to parameterize a given basis of (co)homology classes using the expansion
coefficients,

$\mathcal{C}_{4,\mathrm{C}}=a_{\mathrm{C}}^{\alpha}\,\mathcal{C}_{4,\alpha}\,,\quad\mathcal{C}_{4,i}=a_{i}^{\alpha}\,\mathcal{C}_{4,\alpha}\,,\quad\mathcal{C}_{2}^{\Sigma,i}=b^{\Sigma,i}_{\alpha}\,\mathcal{C}_{2}^{\alpha}\,,\quad\mathcal{C}_{2}^{i}=b^{i}_{\alpha}\,\mathcal{C}_{2}^{\alpha}\,,$
(130)

where the various cycles are introduced in section 2. These coefficients can
be expressed in terms of various auxiliary differential forms defined earlier,

$a_{\mathrm{C}}^{\alpha}=\int_{\partial M_{2}}T_{1}^{\alpha}\,,\quad
a_{i}^{\alpha}=U_{0,\varphi}^{\alpha}(t_{i+1})-U_{0,\varphi}^{\alpha}(t_{i})\,,\quad
b^{\Sigma,i}_{\alpha}=W_{0,\alpha}^{\Sigma}\,,\quad
b^{i}_{\alpha}=W_{0,\alpha}^{\varphi}(t_{i+1})-W_{0,\alpha}^{\varphi}(t_{i})\,.$
(131)

Recall that the four-form flux $E_{4}$ (restricting only to continuous zero-
form symmetries) can be expanded as follows,

$E_{4}=N_{\alpha}\big{(}\Omega_{4}^{\alpha}\big{)}^{\mathrm{g}}+N_{\alpha}\big{(}\Omega_{2,I}^{\alpha}\big{)}^{\mathrm{g}}\,\frac{F_{2}^{I}}{2\pi}+N(\omega_{2,\alpha})^{\mathrm{g}}\,\frac{F_{2}^{\alpha}}{2\pi}+N_{\alpha}\Omega_{0,IJ}^{\alpha}\,\frac{F_{2}^{I}}{2\pi}\frac{F_{2}^{J}}{2\pi}+N\omega_{0,\alpha
I}\,\frac{F_{2}^{I}}{2\pi}\frac{F_{2}^{\alpha}}{2\pi}\,.$ (132)

One can show that the following choice of forms,

$\begin{gathered}\Omega_{2,\psi}^{\alpha}=(dX_{0}^{\alpha}-LT_{1}^{\alpha})\wedge\frac{d\psi}{2\pi}-T_{1}^{\alpha}\wedge\frac{D\varphi}{2\pi}+U_{0,\psi}^{\alpha}V_{2}^{\Sigma}\,,\\\
\Omega_{2,\varphi}^{\alpha}=(dU_{0,\varphi}^{\alpha}+L\,dY_{0}^{\alpha}+T_{1}^{\alpha})\wedge\frac{d\psi}{2\pi}+dY_{0}^{\alpha}\wedge\frac{D\varphi}{2\pi}+U_{0,\varphi}^{\alpha}V_{2}^{\Sigma}\,,\\\
\Omega_{0,\psi\psi}^{\alpha}=X_{0}^{\alpha}\,,\qquad\Omega_{0,\psi\varphi}^{\alpha}=\frac{1}{2}\,U_{0,\varphi}^{\alpha}\,,\qquad\Omega_{0,\varphi\varphi}^{\alpha}=Y_{0}^{\alpha}\,,\end{gathered}$
(133)

are compatible with the closure and regularity constraints on $E_{4}$.
Applying the convention

$N_{\alpha}N_{\beta}\mathcal{J}_{I}^{\alpha\beta}=0$ (134)

for each $I\in\\{\psi,\varphi\\}$, we can uniquely fix the reference values,

$\displaystyle\tilde{U}_{0,\psi}(t_{1})$
$\displaystyle=\frac{1}{N}\sum_{i=2}^{2k}\Big{[}N_{i}+\ell_{i}\big{(}\tilde{Y}_{0,\varphi}(t_{i+1})-\tilde{Y}_{0,\varphi}(t_{i})\big{)}\Big{]}\sum_{j=1}^{i-1}(\ell_{i}-\ell_{j})N_{j}\,,$
(135) $\displaystyle\tilde{U}_{0,\varphi}(t_{1})$
$\displaystyle=\frac{1}{N}\bigg{[}\sum_{i=1}^{2k}\ell_{i}N_{i}\tilde{Y}_{0,\varphi}(t_{i+1})+\sum_{i=2}^{2k}\ell_{i}\big{(}\tilde{Y}_{0,\varphi}(t_{i+1})-\tilde{Y}_{0,\varphi}(t_{i})\big{)}\sum_{j=1}^{i-1}N_{j}\bigg{]}\,,$
(136)

where we used the shorthand notation $N_{i}=N_{\alpha}a_{i}^{\alpha}$,
$\tilde{U}_{0,\psi}=N_{\alpha}U_{0,\psi}^{\alpha}$,
$\tilde{U}_{0,\varphi}=N_{\alpha}U_{0,\varphi}^{\alpha}$,
$\tilde{Y}_{0}=N_{\alpha}Y_{0}^{\alpha}$.

The resulting inflow anomaly polynomial can be written as

$\displaystyle I_{6}^{\text{inflow,$E_{4}^{3}$}}=$
$\displaystyle\sum_{i=1}^{2k}\tilde{u}_{i}\bigg{[}\big{(}\tilde{U}_{0,\varphi}+\ell_{i}\tilde{Y}_{0}\big{)}\bigg{[}X_{0}+\frac{1}{2}\,\ell_{i}\big{(}\tilde{U}_{0,\varphi}+\ell_{i}\tilde{Y}_{0}\big{)}\bigg{]}\bigg{]}^{t_{i+1}}_{t_{i}}\bigg{(}\frac{F_{2}^{\psi}}{2\pi}\bigg{)}^{\\!3}$
$\displaystyle+\sum_{i=1}^{2k}\bigg{[}\frac{1}{2}\,\ell_{i}\tilde{U}_{0,\varphi}^{3}+\tilde{u}_{i}\bigg{(}\tilde{X}_{0}+\ell_{i}\tilde{U}_{0,\varphi}+\frac{1}{2}\,\ell_{i}^{2}\tilde{Y}_{0}\bigg{)}\tilde{Y}_{0}\bigg{]}^{t_{i+1}}_{t_{i}}\bigg{(}\frac{F_{2}^{\psi}}{2\pi}\bigg{)}^{\\!2}\frac{F_{2}^{\varphi}}{2\pi}$
$\displaystyle+\sum_{i=1}^{2k}\ell_{i}\bigg{[}\bigg{(}\tilde{U}_{0,\varphi}^{2}+\frac{1}{2}\,\tilde{u}_{i}\tilde{Y}_{0}\bigg{)}\tilde{Y}_{0}\bigg{]}^{t_{i+1}}_{t_{i}}\frac{F_{2}^{\psi}}{2\pi}\bigg{(}\frac{F_{2}^{\varphi}}{2\pi}\bigg{)}^{\\!2}$
$\displaystyle+\sum_{i=1}^{2k}\frac{1}{2}\bigg{[}\tilde{U}_{0,\varphi}\tilde{Y}_{0}\big{(}\tilde{U}_{0,\varphi}+\ell_{i}\tilde{Y}_{0}\big{)}\bigg{]}^{t_{i+1}}_{t_{i}}\bigg{(}\frac{F_{2}^{\varphi}}{2\pi}\bigg{)}^{\\!3}$
$\displaystyle+\sum_{i=1}^{2k}N\bigg{[}W_{0,\alpha}^{\psi}\tilde{U}_{0,\varphi}\tilde{X}_{0}+\tilde{u}_{i}\Big{[}W_{0,\alpha}^{\varphi}\tilde{X}_{0}+w_{\alpha,i}\big{(}\tilde{U}_{0,\varphi}+\ell_{i}\tilde{Y}_{0}\big{)}\Big{]}$
$\displaystyle\phantom{+\sum_{i=1}^{2k}N\bigg{[}\
}+b^{\Sigma}_{\alpha}\ell_{i}\bigg{[}\tilde{X}_{0}\tilde{Y}_{0}+\frac{1}{2}\big{(}\tilde{U}_{0,\varphi}+\ell_{i}\tilde{Y}_{0}\big{)}^{2}\bigg{]}\bigg{]}^{t_{i+1}}_{t_{i}}\bigg{(}\frac{F_{2}^{\psi}}{2\pi}\bigg{)}^{\\!2}\frac{F_{2}^{\alpha}}{2\pi}$
$\displaystyle+\sum_{i=1}^{2k}N\bigg{[}\frac{1}{2}\big{(}w_{\alpha,i}+\ell_{i}W_{0,\alpha}^{\varphi}\big{)}\tilde{U}_{0,\varphi}^{2}+\ell_{i}w_{\alpha,i}\tilde{u}_{i}Y_{0}+\frac{1}{2}\,b^{\Sigma}_{\alpha}\big{(}\tilde{U}_{0,\varphi}+\ell_{i}\tilde{Y}_{0}\big{)}^{2}\bigg{]}^{t_{i+1}}_{t_{i}}\frac{F_{2}^{\psi}}{2\pi}\frac{F_{2}^{\varphi}}{2\pi}\frac{F_{2}^{\alpha}}{2\pi}$
$\displaystyle+\sum_{i=1}^{2k}N\bigg{[}\ell_{i}W_{0,\alpha}^{\varphi}\tilde{U}_{0,\varphi}\tilde{Y}_{0}+b^{\Sigma}_{\alpha}\bigg{(}\tilde{U}_{0,\varphi}+\frac{1}{2}\,\ell_{i}\tilde{Y}_{0}\bigg{)}\tilde{Y}_{0}\bigg{]}^{t_{i+1}}_{t_{i}}\bigg{(}\frac{F_{2}^{\varphi}}{2\pi}\bigg{)}^{\\!2}\frac{F_{2}^{\alpha}}{2\pi}$
$\displaystyle+\sum_{i=1}^{2k}N^{2}\bigg{[}\tilde{u}_{i}\bigg{(}W_{0,\alpha}^{\psi}+\frac{1}{2}\,\ell_{i}W_{0,\alpha}^{\varphi}\bigg{)}W_{0,\beta}^{\varphi}+b^{\Sigma}_{\alpha}w_{\beta,i}\big{(}\tilde{U}_{0,\varphi}+\ell_{i}\tilde{Y}_{0}\big{)}\bigg{]}^{t_{i+1}}_{t_{i}}\frac{F_{2}^{\psi}}{2\pi}\frac{F_{2}^{\alpha}}{2\pi}\frac{F_{2}^{\beta}}{2\pi}$
$\displaystyle+\sum_{i=1}^{2k}N^{2}\ell_{i}\bigg{[}\frac{1}{2}\,W_{0,\alpha}^{\varphi}W_{0,\beta}^{\varphi}\tilde{U}_{0,\varphi}+b^{\Sigma}_{\alpha}W_{0,\beta}^{\varphi}\tilde{Y}_{0}\bigg{]}^{t_{i+1}}_{t_{i}}\frac{F_{2}^{\varphi}}{2\pi}\frac{F_{2}^{\alpha}}{2\pi}\frac{F_{2}^{\beta}}{2\pi}$
$\displaystyle+\sum_{i=1}^{2k}\frac{N^{3}}{2}\,b^{\Sigma}_{\alpha}\ell_{i}\bigg{[}W_{0,\beta}^{\varphi}W_{0,\gamma}^{\varphi}\bigg{]}^{t_{i+1}}_{t_{i}}\frac{F_{2}^{\alpha}}{2\pi}\frac{F_{2}^{\beta}}{2\pi}\frac{F_{2}^{\gamma}}{2\pi}\,,$
(137)

subject to the condition that $N_{\alpha}F_{2}^{\alpha}=0$. The values of the
various auxiliary functions evaluated at any $t_{i}$ are given by

$\displaystyle\ell_{i}$ $\displaystyle=\begin{cases}\displaystyle
i-\frac{k}{2}&\mathrm{if}\ 1\leq i\leq k\,,\\\\[8.61108pt]
\displaystyle\frac{3k}{2}-i&\mathrm{if}\ k+1\leq i\leq 2k\,,\end{cases}$ (138)
$\displaystyle\tilde{u}_{i}$
$\displaystyle=\tilde{U}_{0,\psi}(t_{1})+\ell_{i}\tilde{U}_{0,\varphi}(t_{1})+\sum_{j=1}^{i-1}(\ell_{i}-\ell_{j})N_{j}\,,$
(139) $\displaystyle\tilde{U}_{0,\psi}(t_{i})$
$\displaystyle=\tilde{U}_{0,\psi}(t_{1})-\sum_{j=1}^{i-1}\ell_{j}N_{j}\,,$
(140) $\displaystyle\tilde{U}_{0,\varphi}(t_{i})$
$\displaystyle=\tilde{U}_{0,\varphi}(t_{1})+\sum_{j=1}^{i-1}N_{j}\,,$ (141)
$\displaystyle\tilde{Y_{0}}(t_{i})$
$\displaystyle=\begin{cases}\displaystyle\frac{N}{2k}&\,\mathrm{if}\ 1\leq
i\leq k\,,\\\\[8.61108pt] \displaystyle-\frac{N}{2k}&\,\mathrm{if}\ k+1\leq
i\leq 2k\,,\end{cases}$ (142) $\displaystyle\tilde{X_{0}}(t_{i})$
$\displaystyle=-\sum_{j=1}^{i-1}\Big{[}\ell_{j}N_{j}+\ell_{j}^{2}\big{(}\tilde{Y_{0}}(t_{j+1})-\tilde{Y_{0}}(t_{j})\big{)}\Big{]}\,,$
(143) $\displaystyle W_{0,\alpha}^{\psi}(t_{i})$
$\displaystyle=\frac{\ell_{i}w_{\alpha,i-1}-\ell_{i-1}w_{\alpha,i}}{\ell_{i}-\ell_{i-1}}\,,$
(144) $\displaystyle W_{0,\alpha}^{\varphi}(t_{i})$
$\displaystyle=\frac{w_{\alpha,i}-w_{\alpha,i-1}}{\ell_{i}-\ell_{i-1}}\,,$
(145)

and in a Poincaré-dual basis of (co)homology classes as introduced in section
2, we have

$w_{\alpha,i=1,\dots,k-1}=-\delta_{\alpha,\mathrm{N}_{i}}\,,\quad
w_{\alpha,i=k+1,\dots,2k-1}=-\delta_{\alpha,\mathrm{S}_{2k-i}}\,,\quad
w_{\alpha,k}=w_{\alpha,2k}=0\,,\quad
b^{\Sigma}_{\alpha}=\delta_{\alpha,\mathrm{C}}\,.$ (146)

A prescription (3.3) is provided in the main text to obtain an inflow anomaly
polynomial that has a well-defined $\chi=0$ limit. It turns out that we can
exactly reproduce this anomaly polynomial by taking (137) and carrying out the
replacements,

$\begin{gathered}\frac{F_{2}^{\psi}}{2\pi}=2c_{1}(R^{\prime})\,,\qquad\frac{F_{2}^{\varphi}}{2\pi}=-kc_{1}(t)\,,\\\
\frac{F_{2}^{\mathrm{N}_{i}}}{2\pi}=c_{1}(\widetilde{\beta}_{i})-2N_{\widetilde{\beta}_{i}}c_{1}(R^{\prime})\,,\qquad\frac{F_{2}^{\mathrm{S}_{k-i}}}{2\pi}=-c_{1}(\widetilde{\gamma}_{i})+2N_{\widetilde{\gamma}_{i}}c_{1}(R^{\prime})\,,\\\
N_{\mathrm{N}_{i}}=\sum_{j=1}^{k-1}(\mathsf{A}_{k-1})_{ij}\,N_{\widetilde{\beta}_{j}}\,,\qquad
N_{\mathrm{S}_{k-i}}=\sum_{j=1}^{k-1}(\mathsf{A}_{k-1})_{ij}\,N_{\widetilde{\gamma}_{j}}\,.\end{gathered}$
(147)

To conclude, this independent derivation for genus one from first principles
confirms the validity of using (3.3) to acquire an inflow anomaly polynomial
for arbitrary $g\geq 1$, including the case $\chi=0$.

##  Appendix D Change of basis between flavor and resolution flux quanta

From the perspective of an 11d flux background probed by an M5-brane stack,
the flux quanta $N_{\alpha}$ appearing in the expansion of $E_{4}$ represent
the amount of flux threading the 4-cycles $\mathcal{C}_{4,\alpha}$. Therefore,
it is natural to express these flux quanta with respect to a (co)homology
basis determined by an intuitive choice of 4-cycles, namely,

$\mathcal{C}_{4,\alpha=\mathrm{N}_{1},\dots,\mathrm{N}_{k-1}}=\mathcal{C}_{4}^{i=1,\dots,k-1}\,,\quad\mathcal{C}_{4,\alpha=C}=\mathcal{C}_{4}^{\mathrm{C}}\,,\quad\mathcal{C}_{4,\alpha=\mathrm{S}_{1},\dots,\mathrm{S}_{k-1}}=\mathcal{C}_{4}^{i=2k-1,\dots,k+1}\,,$
(148)

as in (12). One can then proceed to define the “natural” basis 2-cycles
$\mathcal{C}_{2}^{\alpha}$ to be those that are Poincaré-dual to these basis
4-cycles. For simplicity, the basis of (co)homology classes described above
will hereafter be referred to as the “resolution flux basis.” On the other
hand, as explained in section 3.3, the starting point for the basis implicitly
used in the compactification of the 6d $\mathcal{N}=(1,0)$ theories is instead
an intuitive set of basis 2-cycles,

$\big{(}\mathcal{C}_{2}^{\alpha=\mathrm{N}_{1},\dots,\mathrm{N}_{k-1}}\big{)}^{\prime}=\mathcal{C}_{2}^{i=1,\dots,k-1}\,,\quad\big{(}\mathcal{C}_{2}^{\alpha=C}\big{)}^{\prime}=\mathcal{C}_{2}^{\mathrm{C}}\,,\quad\big{(}\mathcal{C}_{2}^{\alpha=\mathrm{S}_{1},\dots,\mathrm{S}_{k-1}}\big{)}^{\prime}=\mathcal{C}_{2}^{i=2k-1,\dots,k+1}\,,$
(149)

where $\mathcal{C}_{2}^{\mathrm{C}}$ is defined to be the Poincaré dual of
$\mathcal{C}_{4,\mathrm{C}}=M_{4}$. The rest of the basis 4-cycles
$(\mathcal{C}_{4,\alpha})^{\prime}$ can be similarly defined to be the
Poincaré duals of $(\mathcal{C}_{2}^{\alpha})^{\prime}$. We will hereafter
refer to this basis of (co)homology classes as the “flavor flux basis.”

In this appendix we find the transformation matrix that relates the resolution
flux basis and the flavor flux basis. Using the relations following from
Poincaré duality and regularity of the basis two-forms in appendix C of
Bah:2021brs , we can express the basis 2-cycles $\mathcal{C}_{2}^{\alpha}$ in
the resolution flux basis in terms of familiar 2-cycles. Let us start with the
case of $k=2$. One finds that

$\begin{gathered}\mathcal{C}_{2}^{\Sigma,1}=\mathcal{C}_{2}^{\Sigma,2}=\chi\,\mathcal{C}_{2}^{\mathrm{N}_{1}}+\mathcal{C}_{2}^{\mathrm{C}}\,,\qquad\mathcal{C}_{2}^{\Sigma,3}=\mathcal{C}_{2}^{\Sigma,4}=\chi\,\mathcal{C}_{2}^{\mathrm{S}_{1}}+\mathcal{C}_{2}^{C}\,,\\\
\mathcal{C}_{2}^{i=1}=2\,\mathcal{C}_{2}^{\mathrm{N}_{1}}\,,\qquad\mathcal{C}_{2}^{i=2}=\mathcal{C}_{2}^{i=4}=-\mathcal{C}_{2}^{\mathrm{N}_{1}}+\mathcal{C}_{2}^{\mathrm{S}_{1}}\,,\qquad\mathcal{C}_{2}^{i=3}=-2\,\mathcal{C}_{2}^{\mathrm{S}_{1}}\,,\end{gathered}$
(150)

which can be inverted to give

$\displaystyle\mathcal{C}_{2}^{\mathrm{N}_{1}}$
$\displaystyle=\frac{1}{2}\,\mathcal{C}_{2}^{i=1}\,,$ (151)
$\displaystyle\mathcal{C}_{2}^{\mathrm{C}}$
$\displaystyle=\mathcal{C}_{2}^{\Sigma,1}-\frac{\chi}{2}\,\mathcal{C}_{2}^{i=1}=\mathcal{C}_{2}^{\Sigma,3}+\frac{\chi}{2}\,\mathcal{C}_{2}^{i=3}\,,$
$\displaystyle\mathcal{C}_{2}^{\mathrm{S}_{1}}$
$\displaystyle=-\frac{1}{2}\,\mathcal{C}_{2}^{i=3}\,.$

Meanwhile, the basis 2-cycles in the flavor basis are

$\displaystyle\big{(}\mathcal{C}_{2}^{\mathrm{N}_{1}}\big{)}^{\prime}$
$\displaystyle=\mathcal{C}_{2}^{i=1}=2\,\mathcal{C}_{2}^{\mathrm{N}_{1}}\,,$
(152) $\displaystyle\big{(}\mathcal{C}_{2}^{\mathrm{C}}\big{)}^{\prime}$
$\displaystyle=\mathcal{C}_{2}^{\mathrm{C}}\,,$
$\displaystyle\big{(}\mathcal{C}_{2}^{\mathrm{S}_{1}}\big{)}^{\prime}$
$\displaystyle=\mathcal{C}_{2}^{i=3}=-2\,\mathcal{C}_{2}^{\mathrm{S}_{1}}\,,$

so we can express the basis transformation compactly as
$(\mathcal{C}_{2}^{\alpha})^{\prime}=(\mathcal{R}_{2}^{-1})^{\alpha}_{\beta}\,\mathcal{C}_{2}^{\beta}$
where

$\mathcal{R}_{2}^{-1}=\begin{pmatrix}2&0&0\\\ 0&1&0\\\ 0&0&-2\end{pmatrix}\,.$
(153)

The orthonormal pairing between cycles and cohomology representatives is
preserved if
$(\omega_{2,\beta})^{\prime}=(\mathcal{R}_{2})^{\alpha}_{\beta}\,\omega_{2,\alpha}$,
such that

$\int_{(\mathcal{C}_{2}^{\alpha})^{\prime}}(\omega_{2,\beta})^{\prime}=\int_{(\mathcal{R}_{2}^{-1})^{\alpha}_{\gamma}\,\mathcal{C}_{2}^{\gamma}}(\mathcal{R}_{2})^{\delta}_{\beta}\,\omega_{2,\delta}=(\mathcal{R}_{2}^{-1})^{\alpha}_{\gamma}\,(\mathcal{R}_{2})^{\delta}_{\beta}\,\delta^{\gamma}_{\delta}=\delta^{\alpha}_{\beta}\,.$
(154)

Demanding Poincaré duality between the 2-cycles
$(\mathcal{C}_{2}^{\alpha})^{\prime}$ and some set of 4-cycles
$(\mathcal{C}_{4,\alpha})^{\prime}$ amounts to requiring

$\delta^{\alpha}_{\beta}=\int_{M_{6}}(\Omega_{4}^{\alpha})^{\prime}\wedge(\omega_{2,\beta})^{\prime}=\int_{M_{6}}(\mathcal{R}_{4})^{\alpha}_{\gamma}\,\Omega_{4}^{\gamma}\wedge(\mathcal{R}_{2})_{\beta}^{\delta}\,\omega_{2,\delta}=(\mathcal{R}_{4}\mathcal{R}_{2})^{\alpha}_{\beta}\,,$
(155)

which means that the 4-cycles that are Poincaré-dual to the basis 2-cycles in
the flavor basis can be expressed as
$(\mathcal{C}_{4,\alpha})^{\prime}=(\mathcal{R}_{4}^{-1})^{\alpha}_{\beta}\,\mathcal{C}_{4,\beta}$
with

$\mathcal{R}_{4}^{-1}=\mathcal{R}_{2}=\begin{pmatrix}\displaystyle\frac{1}{2}&0&0\\\\[6.45831pt]
0&1&0\\\\[6.45831pt] 0&0&\displaystyle-\frac{1}{2}\end{pmatrix}\,.$ (156)

As discussed in appendix D of Bah:2021brs , the flux quanta associated with
the new and old bases of 4-cycles are related by
$N_{\alpha}^{\prime}=(\mathcal{R}_{4}^{-1})_{\alpha}^{\beta}\,N_{\beta}$ to
make the inflow anomaly polynomial invariant, and hence we get666Note that the
requirement of having no topological mass term associated with $\gamma_{4}$ in
the inflow anomaly polynomial is preserved, i.e.
$N_{\alpha}^{\prime}(F_{2}^{\alpha})^{\prime}=(\mathcal{R}_{4}^{-1})_{\alpha}^{\gamma}N_{\gamma}\,(\mathcal{R}_{2}^{-1})^{\alpha}_{\delta}F_{2}^{\delta}=(\mathcal{R}_{2}\mathcal{R}_{2}^{-1})^{\gamma}_{\delta}N_{\gamma}F_{2}^{\delta}=N_{\alpha}F_{2}^{\alpha}=0$,
assuming that we only restrict to the zero-form symmetries and also follow the
convention that $N_{\alpha}N_{\beta}\mathcal{J}_{I}^{\alpha\beta}=0$.

$N_{\mathrm{N}_{1}}^{\prime}=\frac{1}{2}\,N_{\mathrm{N}_{1}}\,,\qquad
N_{\mathrm{C}}^{\prime}=N_{\mathrm{C}}=N\,,\qquad
N_{\mathrm{S}_{1}}^{\prime}=-\frac{1}{2}\,N_{\mathrm{S}_{1}}\,.$ (157)

As noted previously, in order to preserve positivity of the flux quanta an
additional overall sign flip must be included in the basis transformation on
southern quantities.

We now move on to the case of $k=3$. By repeating the same exercise as before,
we derive that in the resolution flux basis,

$\displaystyle\mathcal{C}_{2}^{\mathrm{N}_{1}}$
$\displaystyle=\frac{1}{3}\big{(}2\,\mathcal{C}_{2}^{i=1}+\mathcal{C}_{2}^{i=2}\big{)}\,,$
(158) $\displaystyle\mathcal{C}_{2}^{\mathrm{N}_{2}}$
$\displaystyle=\frac{1}{3}\big{(}\mathcal{C}_{2}^{i=1}+2\,\mathcal{C}_{2}^{i=2}\big{)}\,,$
$\displaystyle\mathcal{C}_{2}^{\mathrm{C}}$
$\displaystyle=\mathcal{C}_{2}^{\Sigma,1}-\frac{\chi}{2}\big{(}2\,\mathcal{C}_{2}^{i=1}+\mathcal{C}_{2}^{i=2}\big{)}\,,$
$\displaystyle\mathcal{C}_{2}^{\mathrm{S}_{2}}$
$\displaystyle=-\frac{1}{3}\big{(}2\,\mathcal{C}_{2}^{i=4}+\mathcal{C}_{2}^{i=5}\big{)}\,,$
$\displaystyle\mathcal{C}_{2}^{\mathrm{S}_{1}}$
$\displaystyle=-\frac{1}{3}\big{(}\mathcal{C}_{2}^{i=4}+2\,\mathcal{C}_{2}^{i=5}\big{)}\,.$

On the other hand, the basis 2-cycles in the flavor flux basis are

$\displaystyle\big{(}\mathcal{C}_{2}^{\mathrm{N}_{1}}\big{)}^{\prime}$
$\displaystyle=\mathcal{C}_{2}^{i=1}=2\,\mathcal{C}_{2}^{\mathrm{N}_{1}}-\mathcal{C}_{2}^{\mathrm{N}_{1}}\,,$
(159) $\displaystyle\big{(}\mathcal{C}_{2}^{\mathrm{N}_{2}}\big{)}^{\prime}$
$\displaystyle=\mathcal{C}_{2}^{i=2}=-\mathcal{C}_{2}^{\mathrm{N}_{1}}+2\,\mathcal{C}_{2}^{\mathrm{N}_{2}}\,,$
$\displaystyle\big{(}\mathcal{C}_{2}^{\mathrm{C}}\big{)}^{\prime}$
$\displaystyle=\mathcal{C}_{2}^{\mathrm{C}}\,,$
$\displaystyle\big{(}\mathcal{C}_{2}^{\mathrm{S}_{2}}\big{)}^{\prime}$
$\displaystyle=\mathcal{C}_{2}^{i=4}=-2\,\mathcal{C}_{2}^{\mathrm{S}_{2}}+\mathcal{C}_{2}^{\mathrm{S}_{1}}\,,$
$\displaystyle\big{(}\mathcal{C}_{2}^{\mathrm{S}_{1}}\big{)}^{\prime}$
$\displaystyle=\mathcal{C}_{2}^{i=5}=\mathcal{C}_{2}^{\mathrm{S}_{2}}-2\,\mathcal{C}_{2}^{\mathrm{S}_{1}}\,,$

so the corresponding basis transformation matrix is

$\mathcal{R}_{2}^{-1}=\begin{pmatrix}2&-1&0&0&0\\\ -1&2&0&0&0\\\ 0&0&1&0&0\\\
0&0&0&-2&1\\\ 0&0&0&1&-2\end{pmatrix}\,.$ (160)

The flux quanta in the two bases are then related by

$\begin{gathered}N_{\mathrm{N}_{1}}^{\prime}=\frac{1}{3}(2N_{\mathrm{N}_{1}}+N_{\mathrm{N}_{2}})\,,\qquad
N_{\mathrm{N}_{2}}^{\prime}=\frac{1}{3}(N_{\mathrm{N}_{1}}+2N_{\mathrm{N}_{2}})\,,\qquad
N_{\mathrm{C}}^{\prime}=N\,,\\\
N_{\mathrm{S}_{2}}^{\prime}=-\frac{1}{3}(2N_{\mathrm{S}_{2}}+N_{\mathrm{S}_{1}})\,,\qquad
N_{\mathrm{S}_{1}}^{\prime}=-\frac{1}{3}(N_{\mathrm{S}_{2}}+2N_{\mathrm{S}_{1}})\,.\end{gathered}$
(161)

Following the analogous exercise for $k\geq 4$, one can inductively find that
the basis transformation matrix $\mathcal{R}_{2}^{-1}$ is given by

$\mathcal{R}_{2}^{-1}=\begin{pmatrix}\mathsf{A}_{k-1}&0&0\\\ 0&1&0\\\
0&0&-\mathsf{A}_{k-1}\end{pmatrix}\,,$ (162)

where $\mathsf{A}_{k-1}$ is the Cartan matrix of $\mathfrak{su}(k)$. Note that
this formula applies also to $k=2$ and $k=3$.

To summarize, the flux quanta $N_{\mathrm{N}_{i}},N_{\mathrm{S}_{i}}$ in the
resolution flux basis can be expressed in terms of the flux quanta
$N_{\mathrm{N}_{i}}^{\prime},N_{\mathrm{S}_{i}}^{\prime}$ in the flavor flux
basis as

$N_{\mathrm{N}_{i}}=\sum_{i=1}^{k-1}(\mathsf{A}_{k-1})_{ij}\,N_{\mathrm{N}_{j}}^{\prime}\,,\qquad
N_{\mathrm{S}_{i}}=-\sum_{i=1}^{k-1}(\mathsf{A}_{k-1})_{ij}\,N_{\mathrm{S}_{j}}^{\prime}\,,$
(163)

Alternately, we have

$N_{\mathrm{N}_{i}}^{\prime}=\sum_{i=1}^{k-1}(\mathsf{A}_{k-1}^{-1})_{ij}\,N_{\mathrm{N}_{j}}\,,\qquad
N_{\mathrm{S}_{i}}^{\prime}=-\sum_{i=1}^{k-1}(\mathsf{A}_{k-1}^{-1})_{ij}\,N_{\mathrm{S}_{j}}\,,$
(164)

where the inverse $\mathsf{A}_{k-1}$ given by Wei_2017

$(\mathsf{A}_{k-1}^{-1})_{i}^{j}=\mathrm{min}\\{i,j\\}-\frac{ij}{k}\,.$ (165)

We can thus interpret the flux quanta identifications in (3.3) as a change of
basis between a natural 4-cycle and a natural 2-cycle basis, along with a
reversal of indexing and sign flip in the south to preserve positivity of the
fluxes, i.e.

$N_{\widetilde{\beta}_{i}}=N_{\mathrm{N}_{i}}^{\prime}\,,\qquad
N_{\widetilde{\gamma}_{i}}=-N_{\mathrm{S}_{k-i}}^{\prime}\,.$ (166)

## References

  * (1) D. Gaiotto, _N=2 dualities_ , _JHEP_ 08 (2012) 034 [0904.2715].
  * (2) D. Gaiotto, G.W. Moore and A. Neitzke, _Wall-crossing, Hitchin Systems, and the WKB Approximation_ , 0907.3987.
  * (3) K. Maruyoshi, M. Taki, S. Terashima and F. Yagi, _New Seiberg Dualities from N=2 Dualities_ , _JHEP_ 09 (2009) 086 [0907.2625].
  * (4) F. Benini, Y. Tachikawa and B. Wecht, _Sicilian gauge theories and N=1 dualities_ , _JHEP_ 01 (2010) 088 [0909.1327].
  * (5) I. Bah and B. Wecht, _New N=1 Superconformal Field Theories In Four Dimensions_ , _JHEP_ 07 (2013) 107 [1111.3402].
  * (6) I. Bah, C. Beem, N. Bobev and B. Wecht, _AdS/CFT Dual Pairs from M5-Branes on Riemann Surfaces_ , _Phys. Rev. D_ 85 (2012) 121901 [1112.5487].
  * (7) I. Bah, C. Beem, N. Bobev and B. Wecht, _Four-Dimensional SCFTs from M5-Branes_ , _JHEP_ 06 (2012) 005 [1203.0303].
  * (8) D. Gaiotto and S.S. Razamat, _$\mathcal{N}=1$ theories of class ${\mathcal{S}}_{k}$_, _JHEP_ 07 (2015) 073 [1503.05159].
  * (9) S. Franco, H. Hayashi and A. Uranga, _Charting Class $\mathcal{S}_{k}$ Territory_, _Phys. Rev. D_ 92 (2015) 045004 [1504.05988].
  * (10) M. Del Zotto, C. Vafa and D. Xie, _Geometric engineering, mirror symmetry and $6{\mathrm{d}}_{\left(1,0\right)}\to 4{\mathrm{d}}_{\left(\mathcal{N}=2\right)}$_, _JHEP_ 11 (2015) 123 [1504.08348].
  * (11) S.S. Razamat, C. Vafa and G. Zafrir, _4d $\mathcal{N}=1$ from 6d (1, 0)_, _JHEP_ 04 (2017) 064 [1610.09178].
  * (12) I. Bah, A. Hanany, K. Maruyoshi, S.S. Razamat, Y. Tachikawa and G. Zafrir, _4d $\mathcal{N}=1$ from 6d $\mathcal{N}=\left(1,0\right)$ on a torus with fluxes_, _JHEP_ 06 (2017) 022 [1702.04740].
  * (13) H.-C. Kim, S.S. Razamat, C. Vafa and G. Zafrir, _E-String Theory on Riemann Surfaces_ , _Fortsch. Phys._ 66 (2018) 1700074 [1709.02496].
  * (14) J.J. Heckman, D.R. Morrison, T. Rudelius and C. Vafa, _Atomic Classification of 6D SCFTs_ , _Fortsch. Phys._ 63 (2015) 468 [1502.05405].
  * (15) P. Agarwal, I. Bah, K. Maruyoshi and J. Song, _Quiver tails and $\mathcal{N}=1$ SCFTs from M5-branes_, _JHEP_ 03 (2015) 049 [1409.1908].
  * (16) K. Maruyoshi and J. Song, _Enhancement of Supersymmetry via Renormalization Group Flow and the Superconformal Index_ , _Phys. Rev. Lett._ 118 (2017) 151602 [1606.05632].
  * (17) K. Maruyoshi and J. Song, _$\mathcal{N}=1$ deformations and RG flows of $\mathcal{N}=2$ SCFTs_, _JHEP_ 02 (2017) 075 [1607.04281].
  * (18) E. Nardoni, _4d SCFTs from negative-degree line bundles_ , _JHEP_ 08 (2018) 199 [1611.01229].
  * (19) P. Agarwal, A. Sciarappa and J. Song, _$\mathcal{N}$ =1 Lagrangians for generalized Argyres-Douglas theories_, _JHEP_ 10 (2017) 211 [1707.04751].
  * (20) S. Benvenuti and S. Giacomelli, _Lagrangians for generalized Argyres-Douglas theories_ , _JHEP_ 10 (2017) 106 [1707.05113].
  * (21) S. Giacomelli, _RG flows with supersymmetry enhancement and geometric engineering_ , _JHEP_ 06 (2018) 156 [1710.06469].
  * (22) G. Zafrir, _On the torus compactifications of Z 2 orbifolds of E-string theories_, _JHEP_ 10 (2019) 040 [1809.04260].
  * (23) J. Chen, B. Haghighat, S. Liu and M. Sperling, _4d $N$=1 from 6d D-type $N$=(1,0)_, _JHEP_ 01 (2020) 152 [1907.00536].
  * (24) C. Hwang, S.S. Razamat, E. Sabag and M. Sacchi, _Rank $Q$ E-String on Spheres with Flux_, 2103.09149.
  * (25) J.P. Gauntlett, D. Martelli, J. Sparks and D. Waldram, _Supersymmetric AdS(5) solutions of M theory_ , _Class. Quant. Grav._ 21 (2004) 4335 [hep-th/0402153].
  * (26) I. Bah and F. Bonetti, _Anomaly Inflow, Accidental Symmetry, and Spontaneous Symmetry Breaking_ , _JHEP_ 01 (2020) 117 [1910.07549].
  * (27) I. Bah, F. Bonetti, E. Leung and P. Weck, _M5-branes Probing Flux Backgrounds_ , 2111.01790.
  * (28) I. Bah, _AdS5 solutions from M5-branes on Riemann surface and D6-branes sources_ , _JHEP_ 09 (2015) 163 [1501.06072].
  * (29) D. Freed, J.A. Harvey, R. Minasian and G.W. Moore, _Gravitational anomaly cancellation for M theory five-branes_ , _Adv. Theor. Math. Phys._ 2 (1998) 601 [hep-th/9803205].
  * (30) J.A. Harvey, R. Minasian and G.W. Moore, _NonAbelian tensor multiplet anomalies_ , _JHEP_ 09 (1998) 004 [hep-th/9808060].
  * (31) I. Bah, F. Bonetti, R. Minasian and E. Nardoni, _Anomalies of QFTs from M-theory and Holography_ , _JHEP_ 01 (2020) 125 [1910.04166].
  * (32) S.M. Hosseini, K. Hristov, Y. Tachikawa and A. Zaffaroni, _Anomalies, Black strings and the charged Cardy formula_ , _JHEP_ 09 (2020) 167 [2006.08629].
  * (33) K. Ohmori, H. Shimizu, Y. Tachikawa and K. Yonekura, _Anomaly polynomial of general 6d SCFTs_ , _PTEP_ 2014 (2014) 103B07 [1408.5572].
  * (34) J.P. Gauntlett, E. O Colgain and O. Varela, _Properties of some conformal field theories with M-theory duals_ , _JHEP_ 02 (2007) 049 [hep-th/0611219].
  * (35) D. Gaiotto and J. Maldacena, _The Gravity duals of N=2 superconformal field theories_ , _JHEP_ 10 (2012) 189 [0904.4466].
  * (36) E. Witten, _Some comments on string dynamics_ , in _STRINGS 95: Future Perspectives in String Theory_ , pp. 501–523, 7, 1995 [hep-th/9507121].
  * (37) O.J. Ganor, D.R. Morrison and N. Seiberg, _Branes, Calabi-Yau spaces, and toroidal compactification of the N=1 six-dimensional E(8) theory_ , _Nucl. Phys. B_ 487 (1997) 93 [hep-th/9610251].
  * (38) A. Hanany and E. Witten, _Type IIB superstrings, BPS monopoles, and three-dimensional gauge dynamics_ , _Nucl. Phys. B_ 492 (1997) 152 [hep-th/9611230].
  * (39) I. Brunner and A. Karch, _Branes and six-dimensional fixed points_ , _Phys. Lett._ B409 (1997) 109 [hep-th/9705022].
  * (40) J.D. Blum and K.A. Intriligator, _Consistency conditions for branes at orbifold singularities_ , _Nucl. Phys._ B506 (1997) 223 [hep-th/9705030].
  * (41) J.D. Blum and K.A. Intriligator, _New phases of string theory and 6-D RG fixed points via branes at orbifold singularities_ , _Nucl. Phys._ B506 (1997) 199 [hep-th/9705044].
  * (42) K.A. Intriligator, _New string theories in six-dimensions via branes at orbifold singularities_ , _Adv. Theor. Math. Phys._ 1 (1998) 271 [hep-th/9708117].
  * (43) I. Brunner and A. Karch, _Branes at orbifolds versus Hanany Witten in six-dimensions_ , _JHEP_ 03 (1998) 003 [hep-th/9712143].
  * (44) A. Hanany and A. Zaffaroni, _Branes and six-dimensional supersymmetric theories_ , _Nucl. Phys. B_ 529 (1998) 180 [hep-th/9712145].
  * (45) K.A. Intriligator and B. Wecht, _The Exact superconformal R symmetry maximizes a_ , _Nucl. Phys. B_ 667 (2003) 183 [hep-th/0304128].
  * (46) D.M. Hofman and J. Maldacena, _Conformal collider physics: Energy and charge correlations_ , _JHEP_ 05 (2008) 012 [0803.1467].
  * (47) S. Benvenuti, S. Franco, A. Hanany, D. Martelli and J. Sparks, _An infinite family of superconformal quiver gauge theories with sasaki-einstein duals_ , _Journal of High Energy Physics_ 2005 (2005) 064–064.
  * (48) D. Anselmi, D.Z. Freedman, M.T. Grisaru and A.A. Johansen, _Nonperturbative formulas for central functions of supersymmetric gauge theories_ , _Nucl. Phys._ B526 (1998) 543 [hep-th/9708042].
  * (49) D. Anselmi, J. Erlich, D.Z. Freedman and A.A. Johansen, _Positivity constraints on anomalies in supersymmetric gauge theories_ , _Phys. Rev. D_ 57 (1998) 7570 [hep-th/9711035].
  * (50) L. Qi and K. Lay Teo, _Multivariate polynomial minimization and its application in signal processing_ , _J. of Global Optimization_ 26 (2003) 419–433.
  * (51) M. Cvetic, H. Lu, D.N. Page and C.N. Pope, _New Einstein-Sasaki spaces in five and higher dimensions_ , _Phys. Rev. Lett._ 95 (2005) 071101 [hep-th/0504225].
  * (52) M. Cvetic, H. Lu, D.N. Page and C.N. Pope, _New Einstein-Sasaki and Einstein spaces from Kerr-de Sitter_ , _JHEP_ 07 (2009) 082 [hep-th/0505223].
  * (53) H.-C. Kim, S.S. Razamat, C. Vafa and G. Zafrir, _Compactifications of ADE conformal matter on a torus_ , _JHEP_ 09 (2018) 110 [1806.07620].
  * (54) G.W. Gibbons, C.N. Pope and H. Romer, _Index Theorem Boundary Terms for Gravitational Instantons_ , _Nucl. Phys._ B157 (1979) 377.
  * (55) I. Bah, A. Passias and A. Tomasiello, _AdS 5 compactifications with punctures in massive IIA supergravity_, _JHEP_ 11 (2017) 050 [1704.07389].
  * (56) Y. Wei and Y.M. Zou, _Inverses of cartan matrices of lie algebras and lie superalgebras_ , _Linear Algebra and its Applications_ 521 (2017) 283–298 [1711.01294].


# Automatic Calibration for an Open-source Magnetic Tactile Sensor

Lowiek Van den Stockt1∗, Remko Proesmans1∗ and Francis wyffels1 1Lowiek Van
den Stockt, Remko Proesmans and Francis wyffels are with the IDLab-AIRO
research lab at Ghent University – imec, Technologiepark-Zwijnaarde 126, 9052
Zwijnaarde, Belgium. Remko Proesmans is a predoctoral fellow of the Research
Foundation Flanders (FWO) under grant agreement no. 1S15923N. This work was
also partially supported by the euROBIn Project (EU grant number 101070596).
<EMAIL_ADDRESS>Van den Stockt and Remko Proesmans made equal
contributions to this work.

###### Abstract

Tactile sensing can enable robots to perform complex, contact-rich tasks.
Magnetic sensors offer accurate three-axis force measurements while using
affordable materials. Calibrating such a sensor involves either manual data
collection, or automated procedures with precise mounting of the sensor
relative to an actuator. We present an open-source magnetic tactile sensor
with an automatic, in situ, gripper-agnostic calibration method, after which
the sensor is immediately ready for use. Our goal is to lower the barrier to
entry for tactile sensing, fostering collaboration in robotics. Design files
and readout code can be found at https://github.com/LowiekVDS/Open-source-
Magnetic-Tactile-Sensor.

###### Index Terms:

Tactile sensing, Sensor-based Control, Open-source

##  I Introduction

Tactile sensing in robotics is crucial for contact-rich tasks like food
picking [1] and in-hand manipulation [2]. Widespread sensor modalities include
piezoresistive, capacitive, barometric, optical and magnetic sensing. Among
these, magnetic sensors can be made with readily available materials and
components while providing accurate three-axis force measurements [3]. They
work by suspending small magnets [3, 4, 5, 6, 7], coils [8], or distributed
magnetic substrates [9, 10] above a grid of Hall sensors.

Typically, a data-driven calibration procedure is performed to interpret the
data from such sensors. In [3, 4, 5], a human presses the magnetic sensor
against a force/torque (F/T) sensor to capture calibration data. Other work
proposes automated procedures: [10, 8, 9] use a robot equipped with an F/T
sensor to press down on the magnetic sensor in a predefined grid, whereas [7]
has the magnetic sensor pressing down on a load cell mounted to a moving
platform.

Schmitz et al. [3, 4, 5] have commercialised three-axis tactile fingertips
based on magnetic sensing, greatly incentivising further research in tactile
sensing. However, the monetary cost can still be a hurdle for other groups to
adopt these sensors. In the spirit of democratising tactile sensors, we are
developing open-source three-axis force sensors: here, we present a baseline
fingertip with a 2-by-2 taxel grid. To make adoption in other research groups
as straightforward as possible, we propose an automatic calibration procedure
with the sensor already mounted to the robot that will make use of it. This
way, the sensor is ready for use immediately after calibration, as opposed to
previous work [7, 10, 8, 9].

##  II Sensor design

At the heart of the fingertip design, shown in Fig. 1, lies a printed circuit
board (PCB) with a 2-by-2 grid of MLX90393 Hall effect sensors connected to an
I2C bus. A dome structure similar to [3, 5] is printed in Flexible FLGR02
resin using a Formlabs Form 2 printer. Cylindrical magnets with a height of
$1\text{\,}\mathrm{mm}$ and diameter of $1.5\text{\,}\mathrm{mm}$ are
superglued into the domes, and the dome structure itself is glued to the PCB.
A cover for the PCB is 3D printed in PLA using a Prusa i3 MK3. Optionally, a
smooth contact surface for grasping can be cast onto the cover using Silicone
Addition Colorless 50 by Silicones and More. Fig. 2 shows the mould used.
Crucially, a mock PCB is inserted into the cover during curing. The domes on
the mock PCB are shorter than the resin domes. This way, when the mock PCB is
removed and the resin domes are inserted after curing, an air gap surrounds
each dome. The air gap ensures that the force applied to the silicone surface
is transferred to the resin domes. Finally, the cover is bolted to a PLA
backing (Fig. 1). The backing is designed to fit a Robotiq 2F-85 or 2F-140
gripper, but we also provide a coupling to fit Robotiq fingertips to Schunk
EGU and EGK grippers.

Figure 1: Fingertip structure. The magnets are glued into the domes, the domes
are glued onto the PCB. The PCB is pressed between the cover and backing, and
the cover is bolted to the backing. Figure 2: Mould for silicone pour. The
domes on the mock PCB are shorter than the resin-printed domes, such that
after removal of the mock PCB and insertion of the PCB with resin domes, an
air cavity is present all around each dome.

##  III Automatic Calibration

###  III-A Hardware Setup

The robotic arm on which the gripper is mounted should feature an F/T sensor.
In this work, we used a Schunk EGK 40-MB-M-B and a UR3e collaborative arm. A
custom probe, see Fig. 3, is mounted externally to the robot. The probe is
constructed from an aluminium 1515 profile with D-shaped slots and several
3D-printed PLA parts. The probe tip is shaped such that it fits on top of one
of the resin domes. It is important that both the probe tip and the mounting
of the probe to the table are rigid.

Figure 3: Calibration probe assembly. The probe tip perfectly fits a taxel
dome.

###  III-B Calibration Methodology

Calibration is done in situ, meaning the fingertip is mounted on the robot
that will make use of it. At first, the cover (see Fig. 1) should not have a
silicone pad. If desired, the cover can easily be replaced after calibration
without removing the fingertip from the gripper. The procedure is gripper-
agnostic. Only the direction of the probe tip expressed in the base frame of
the robot should be known.

First, the robot is placed in the vicinity of the sensor, with the fingertip
facing the probe tip. The robot then touches the probe with the front, the
side and the top of the fingertip. Contact is observed from the F/T readings.
Knowing the dimensions of the fingertip, the probe can be localised. The robot
subsequently presses one of the resin domes into the probe and exerts a
predefined set of forces, see the green annotations in Fig. 4, while recording
both the F/T and the Hall sensor readings. This is repeated for each taxel.
The F/T data is averaged over a moving window of 100 samples or
$240\text{\,}\mathrm{ms}$. A linear interpolation is applied to account for
different readout frequencies of the Hall and F/T sensors.

Polynomial features up to the third degree are extracted from the Hall
readings. An 80%/20% train-test split is randomly sampled and a least squares
linear regressor is fitted on the train set. The result is a model per taxel
that takes in the X, Y and Z components of the magnetic field and predicts the
three components of the force ($F_{x}$, $F_{y}$, $F_{z}$) applied to the
taxel.

##  IV Results

For each taxel, Table I gives the coefficient of determination ($R^{2}$) and
the mean squared error (MSE) of the model when applied to the test set. Fig. 4
additionally shows both the true and predicted forces for taxel 3. We note
that the predicted force curves rise comparatively slowly to the ground truth.
We believe this is due to the mechanical hysteresis of the resin-printed
domes.

Figure 4: F/T Readings and model predictions for taxel 3. TABLE I: Test scores for each taxel Taxel | $R^{2}$ | MSE [N2]
---|---|---
0 | 0.81162 | 1.10555
1 | 0.80103 | 0.97162
2 | 0.84808 | 0.88912
3 | 0.84431 | 0.92823
Average | 0.82626 | 0.97363

##  V Conclusion

We presented an open-source design for a magnetic tactile fingertip and have
developed an automatic, gripper-agnostic, in situ calibration strategy. The
calibration method only requires a probe to be mounted along a known direction
w.r.t. the base frame of the robot. A polynomial model trained on the magnetic
sensor data shows an average $R^{2}$ of 0.83 and an average MSE of 0.97 N2. In
future work, we will open-source a modular fingertip design featuring tactile
surfaces with 4-by-8, 1-by-4, and 2-by-2 taxel grids. In addition, we aim to
compensate for hysteresis and to examine a second calibration stage that can
account for mechanical and magnetic coupling. Our goal is to lower the barrier
to entry of tactile sensors and encourage their adoption across robotics labs.

## References

  * [1] R. Yagawa, R. Ishikawa, M. Hamaya, K. Tanaka, A. Hashimoto, and H. Saito, “Learning food picking without food: Fracture anticipation by breaking reusable fragile objects,” in _2023 IEEE International Conference on Robotics and Automation (ICRA)_ , 2023, pp. 917–923.
  * [2] Z.-H. Yin, B. Huang, Y. Qin, Q. Chen, and X. Wang, “Rotating without seeing: Towards in-hand dexterity through touch,” 2023.
  * [3] T. P. Tomo, M. Regoli, A. Schmitz, L. Natale, H. Kristanto, S. Somlor, L. Jamone, G. Metta, and S. Sugano, “A new silicone structure for uskin—a soft, distributed, digital 3-axis skin sensor and its integration on the humanoid robot icub,” _IEEE Robotics and Automation Letters_ , vol. 3, no. 3, pp. 2584–2591, 2018.
  * [4] H. Kristanto, P. Sathe, A. Schmitz, C. Hsu, T. P. Tomo, S. Somlor, and S. Sugano, “Development of a 3-axis human fingertip tactile sensor based on distributed hall effect sensors,” in _2019 IEEE-RAS 19th International Conference on Humanoid Robots (Humanoids)_ , 2019, pp. 1–7.
  * [5] P. Sathe, A. Schmitz, T. P. Tomo, S. Somlor, S. Funabashi, and S. Shigeki, “Fingertac - an interchangeable and wearable tactile sensor for the fingertips of human and robot hands,” in _2023 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)_ , 2023, pp. 10 813–10 820.
  * [6] K. Dai, X. Wang, A. Rojas, E. Harber, Y. Tian, N. Paiva, J. Gnehm, E. Schindewolf, H. Choset, V. Webster-Wood, and L. Li, “Design of a biomimetic tactile sensor for material classification,” in _2022 International Conference on Robotics and Automation (ICRA)_ , 2022, pp. 10 774–10 780.
  * [7] T. Le Signor, N. Dupré, and G. F. Close, “A gradiometric magnetic force sensor immune to stray magnetic fields for robotic hands and grippers,” _IEEE Robotics and Automation Letters_ , vol. 7, no. 2, pp. 3070–3076, 2022.
  * [8] S. Xie, Y. Zhang, M. Jin, C. Li, and Q. Meng, “High sensitivity and wide range soft magnetic tactile sensor based on electromagnetic induction,” _IEEE Sensors Journal_ , vol. 21, no. 3, pp. 2757–2766, 2021.
  * [9] Y. Yan, Z. Hu, Z. Yang, W. Yuan, C. Song, J. Pan, and Y. Shen, “Soft magnetic skin for super-resolution tactile sensing with force self-decoupling,” _Science Robotics_ , vol. 6, no. 51, p. eabc8801, 2021.
  * [10] R. Bhirangi, T. Hellebrekers, C. Majidi, and A. Gupta, “Reskin: versatile, replaceable, lasting tactile skins,” in _2021 Conference on Robotic Learning (CoRL)_ , 2021.


#  Energy-aware Multi-UAV Coverage Mission Planning with Optimal Speed of
Flight

Denys Datsko, Frantisek Nekovar, Robert Penicka, Martin Saska Manuscript
received: August, 15, 2023; Revised October, 14, 2023; Accepted January, 11,
2024.This paper was recommended for publication by Editor Chao-Bo Yan upon
evaluation of the Associate Editor and Reviewers’ comments. The authors are
with the Multi-robot Systems Group, Faculty of Electrical Engineering, Czech
Technical University in Prague, Czech Republic (http://mrs.felk.cvut.cz/).
This work has been supported by the Czech Science Foundation (GAČR) under
research project No. 23-06162M, and by the European Union under the project
Robotics and Advanced Industrial Production (reg. no.
CZ.02.01.01/00/22_008/0004590), and by CTU grant no.
SGS23/177/OHK3/3T/13.Digital Object Identifier (DOI):
10.1109/LRA.2024.3358581.

###### Abstract

This paper tackles the problem of planning minimum-energy coverage paths for
multiple UAVs. The addressed Multi-UAV Coverage Path Planning (mCPP) is a
crucial problem for many UAV applications such as inspection and aerial
survey. However, the typical path-length objective of existing approaches does
not directly minimize the energy consumption, nor allows for constraining
energy of individual paths by the battery capacity. To this end, we propose a
novel mCPP method that uses the optimal flight speed for minimizing energy
consumption per traveled distance and a simple yet precise energy consumption
estimation algorithm that is utilized during the mCPP planning phase. The
method decomposes a given area with boustrophedon decomposition and represents
the mCPP as an instance of Multiple Set Traveling Salesman Problem with a
minimum energy objective and energy consumption constraint. The proposed
method is shown to outperform state-of-the-art methods in terms of
computational time and energy efficiency of produced paths. The experimental
results show that the accuracy of the energy consumption estimation is on
average 97% compared to real flight consumption. The feasibility of the
proposed method was verified in a real-world coverage experiment with two
UAVs.

###### Index Terms:

Aerial Systems: Applications; Path Planning for Multiple Mobile Robots or
Agents; Planning, Scheduling and Coordination

## Supplementary Material

Video: https://youtu.be/S8kjqZp-G-0
Code: https://github.com/ctu-mrs/EnergyAwareMCPP

##  I Introduction

The Coverage Path Planning (CPP) is frequently needed for deployment of
autonomous Unmanned Aerial Vehicles (UAVs) in applications including
agriculture [1], animal population counting [2], post-earthquake assessment
[3], disaster management [4], and structure inspection [5]. The goal of the
CPP is to find paths that cover the entirety of a given Area Of Interest (AOI)
with the onboard sensor’s footprint. This means covering AOI with the field of
view of a camera sensor or, for example, covering the area with sufficiently
dense measurements from LiDAR.

Figure 1:  Stitched images taken by two UAVs in a real-world experiment of the
proposed energy-aware coverage path planning method together with the photos
of used UAVs. The white polygon represents the area of interest, the red
triangle is a no-fly zone and the green lines are the flown trajectories of
the UAVs.

Most common optimized objective of CPP with UAVs is the path length [6].
However, one of the main limitations of multi-rotor UAVs is the restricted
battery capacity, thus limited flight time. Path length minimization does not
directly minimize the energy consumption, as short coverage trajectories with
lots of turns require more acceleration, thus energy, than trajectories with
mainly straight segments. Selection of suitable velocity is also important, as
low velocities lead to energy wasted to defy gravity without covering much
distance, while high velocities leads to increased aerodynamic drag.
Optimizing the energy consumption can lead to shorter overall mission times
and/or fewer battery replacements, essential in time-limited applications [2].
While few existing approaches minimize energy consumption [7, 8], they only
consider single-UAV CPP, do not operate with arbitrary AOI, and require many
measurements to estimate the energy consumption for a specific UAV. This is
due to the complexity of calculating energy consumption, which is a limiting
factor for quick evaluation of many possible paths needed for the CPP
planning.

The CPP problem can be represented as the well-known NP-hard Traveling
Salesman Problem (TSP) to minimize a path that visits individual cells of
decomposed AOI [9]. Therefore, solution approximations are necessary to reach
reasonable computation times for large areas. Most recent algorithms [6]
decompose the area into smaller sub-polygons or into a grid pattern. Despite
that, the CPP is still a challenging problem, especially for the energy-aware
CPP with multiple robots. Each decomposed sub-polygon has to be covered with a
trajectory minimizing energy consumption, which depends on the flight speed
and an angle of the back-and-forth coverage trajectory pattern. The
decomposition has to account for the sub-polygons’ coverage energy, as their
distribution among multiple UAVs and the order of visit affect the final
energy consumption. These dependencies between the CPP stages (i.e. the area
decomposition, back-and-forth trajectory planning, multi-UAV sub-polygon
allocation, and sub-polygons’ visit ordering), make the energy-aware Multi-UAV
CPP a challenging problem. The allocation and ordering problems can be (for a
number of trajectories in each sub-polygon) naturally represented as Multiple
Set Traveling Salesman Problem (MS-TSP) [10], which is a multi-robot and
budget-constrained extension of the Generalized Traveling Salesman Problem
(GTSP) [11].

This letter proposes an energy-aware multi-UAV CPP algorithm that optimizes
the energy consumption of vehicle trajectories. We calculate an optimal flight
velocity that maximizes traveled distance [12] for a given UAV based on its
physical parameters. The energy consumption of the multi-UAV CPP solution is
minimized by using the optimal velocity for the coverage trajectories, and by
using our fast algorithm for estimating trajectory energy during the CPP
planning. The algorithm uses boustrophedon cellular decomposition [13], back-
and-forth sweeping patterns in each sub-polygon, the MS-TSP representation of
the multi-UAV CPP problem and proposed heuristic solver of the MS-TSP. By
using energy estimation during the planning, we can both minimize the energy
consumption and account for the energy consumption constraint imposed by the
battery capacity.

Contributions of this letter are as follows. We propose path energy
consumption as an objective in multi-UAV coverage path planning by utilizing
optimal flight speed [12]. We introduce a reduction of the CPP problem to MS-
TSP formulation. To the best of our knowledge, this is the first method that
directly considers battery capacity constraints during the CPP planning phase
to create feasible and energy-efficient multi-UAV missions. We verify the
method in real-world experiments with multiple UAVs in a visual-coverage
experiment depicted in Figure 1, and we show that the energy consumption
estimation of produced trajectories has on average 97% precision. Moreover,
our method outperforms the state-of-the-art methods [9, 14, 15] both in
minimizing energy consumption and computational time, although they solve a
similar problem without considering optimal speed, energy-aware planning or
even no-fly-zones [15]. Finally, all the methods described here are open-
sourced.

##  II Related Work

Various methods for solving the CPP have been surveyed in [16], and for CPP
with UAV applications more recently in [6]. They can be classified by
different methods of area decomposition. Some methods use exact cellular
decomposition combined with coverage patterns such as sweeping [9] or spiral
paths [8], while others [2] use approximate cellular decomposition and form a
graph from the resulting cells. The utilized boustrophedon cellular
decomposition [13] offers advantages, as shown in [9], due to usually fewer
sub-polygons being decomposed and thus smaller overhead on traveling between
them is needed.

The optimization objective of CPP in UAV applications can vary. Some works
optimize total flight path length [14, 2, 9] as in the Capacited Vehicle
Routing Problem (CVRP) [17], total vehicle flight time [9], number of vehicle
path turns [18] or the vehicle energy consumed by the UAV moving along the
optimized path [8]. In long-duration CPP flights, proper energy consumption
estimation is needed both to fully utilize the vehicle flight budget and to
eliminate mission preemption due to low battery charge. While some works focus
on power consumption in hover conditions, e.g. [19, 20], we opted to utilize
the method for estimation of energy consumption during a fast flight [12]
which minimizes the energy per covered distance.

Multi-vehicle generalizations of CPP are the Cooperative Coverage Path
Planning (CCPP) [21] for 3D visual inspection and the multi-vehicle Coverage
Path Planning (mCPP) [14] for area coverage. The latter utilizes Minimum
Spanning Tree (MST) to approximate cellular decomposition into a square grid
together with minimizing the number of turns for energy-efficient paths. The
algorithm uses Divide Areas based on Robot’s initial Positions (DARP)
algorithm [22] for the area decomposition. A recent work presents a Path
Optimization for Population Counting with Overhead Robotic Networks (POPCORN)
[2] for mCPP. The approach uses exact cellular decomposition with problem
representation as a series of satisfiability modulo theory instances
formulated similarly to [23]. The main objective of the algorithm is to
minimize vehicle path lengths. The work [2] was extended more recently in
[15], where a similar approach is used, but the original AOI is firstly split
to reduce computation times. The new approach, Split And Link Tiles (SALT)
[15], allows planning for large environments in a reasonable time as it is the
number of instances that grows instead of their complexity. However, splitting
the area and coverage of each sub-area separately leads to worse results in
terms of path length due to the constrained set of solutions.

A single-UAV approach that utilizes an exact cellular decomposition and back
and forth sweeping patterns is presented in [9], where multitude of coverage
paths are generated for each sub-cell. The problem of deciding which paths to
select in each sub-cell and in which order to connect them is converted to an
instance of a Generalized Traveling Salesman Problem (GTSP) [11], which is
solved exactly. The objective of the algorithm is to minimize vehicle flight
time, assuming UAV stops at each turning point with immediate acceleration
change and a trapezoidal speed profile.

A similar approach is also used in [24], where multi-regional CPP is
presented. The main distinction with the problem presented herein is that
regions may be spaced far apart from each other. The problem is reduced to the
Energy constrained Multiple TSP-CPP (EMTSP-CPP) and two approaches for solving
the problem are presented: Branch and Bound and Genetic Algorithm. The authors
show multiple numerical experiments with two objective functions: minimizing
the sum of route lengths and minimizing the maximum route length among all the
UAVs. However, the approach assumes constant velocity coverage, and the energy
constraint is only in the form of limited path length.

In contrast, our method models the UAV up to limited acceleration and uses the
optimal velocity to minimize the coverage energy for a given UAV. Moreover,
through accurate and fast energy consumption estimation used during CPP
planning, our method can directly use the energy constraints of the battery. A
comparison of the discussed approaches is summarized in Table I. There, the
main difference between ”Energy-efficient” and ”Energy-aware” fields is that
the former means minimizing a metric related to energy consumption (route
length, number of turns etc.) while the latter means taking into account
energy consumption directly.

TABLE I: Qualitative comparison of the related methods

| Our |  POPCORN+SALT[15] |  MST[14] |  GTSP[9] |  Spiral[8]
---|---|---|---|---|---
Multi-UAV | ✔ | ✔ | ✔ | ✗ | ✗
Energy-efficient | ✔ | ✔ | ✔ | ✔ | ✔
Energy-aware | ✔ | ✗ | ✗ | ✗ | ✔
Path length constraint | ✗ | ✔ | ✗ | ✗ | ✗
Path energy constraint | ✔ | ✗ | ✗ | ✗ | ✗
Arbitrary AOI | ✔ | ✔ | ✔ | ✔ | ✗
No-fly-zones | ✔ | ✗ | ✔ | ✔ | ✗

Figure 2:  Problem transformation into an MS-TSP instance. Each value
$w_{s\mathbf{x}}$ corresponds to the energy needed to perform sweeping pattern
$\mathbf{x}$. Each $w_{x,y}$ denotes the energy needed to get from the last
point of sweeping pattern $x$ to the first point of sweeping pattern $y$. Init
and End nodes represent UAV’s initial and end positions.

##  III Energy-aware multi-UAV coverage planning

We first present the high-level description of the proposed energy-aware
multi-UAV CPP algorithm in Sec. III-A. Afterward, energy consumption
estimation based on trajectory generation and the novel fast energy
consumption estimation algorithms are described, both leveraging the pen-and-
paper algorithm for calculating the optimal speed per traveled distance from
[12]. Finally, each part of the path-planning algorithm is described such as
the area decomposition based on Boustrophedon Cellular Decomposition (BCD)
[25], the novel problem conversion to MS-TSP instance, and the MS-TSP solver
extending the approach presented in [10].

###  III-A CPP algorithm

The proposed CPP algorithm is designed to plan paths for a specified amount of
UAVs as well as to minimize the number of paths (needed UAV flights) while the
maximum path energy stays below a user-defined limit. For the second case, the
planning is done several times, increasing the number of paths generated until
the constrained is met.

The method is summarized in Algorithm 1, where $N_{\text{UAV}}$ is the number
of UAVs, $E_{\text{bound}}$ is the upper bound on the largest path energy, and
$N_{min}$ is the minimum number of sub-polygons per UAV after decomposition. A
single planning step for a specified number of paths starts with a greedy
calculation of $N_{angles}$ best initial rotation angles for the input polygon
(see Section III-C). For each of those angles, an initial AOI is rotated by
that angle and decomposed using Boustrophedon Cellular Decomposition (BCD)
[25] into a set of non-overlapping polygons. If the number of polygons is
smaller than the user-defined limit ($N_{min}\cdot N_{paths}$), polygons with
the largest area are divided. For each of the resulting polygons, different
back-and-forth coverage paths with distinct sweeping angle are generated. Each
of these paths is then represented by a node in a weighted graph with a weight
equal to the estimated energy consumption of a UAV following that path. By
grouping all the graph nodes corresponding to the same sub-polygon into a set,
we can generate directed edges between each pair of nodes from different sets.
The weight of such edges is equal to the energy needed to move from the last
point of the source node path to the first point of the destination node path.
Finally, initial and end nodes that represent UAVs’ initial and end positions
are added. This process is depicted in Figure 2.

Input: AOI, $N_{\text{UAV}}$, $\text{UAV}\\_\text{parameters}$,
$E_{\text{bound}}$, $N_{\text{min}}$

Output: best_paths

1 best_paths = {}

2 $E_{\text{max}}=+\infty$ $\triangleright$ maximum path energy from
best_paths

3 $N_{\text{paths}}=N_{\text{UAV}}$ $\triangleright$ number of paths to
generate

4 while  _$E_{\mathrm{max}} >E_{\mathrm{bound}}$_ do

5 $E_{\text{max}}=+\infty;E_{\text{tot}}=+\infty$

6 get best rotation angles $best\\_angles$ (Sec. III-C)

7 for  _$a\in best\\_angles$_ do

8 sub_polygons = BCD(rotate(AOI, $a$))

9 divide sub_polygons into at least $N_{\text{min}}\cdot N_{\text{paths}}$
parts

10 MSTSP_nodes = {}

11 for  _$polygon\in$ sub_polygons_ do

12 $paths_{c}$ = get_coverage_paths($polygon$, $N_{\text{paths}}$)

13 $nodes\\_set$ = {}

14

15 for  _$path\in paths_{c}$_ do

16 add $path$ to $nodes\\_set$

17 add $nodes\\_set$ to MSTSP_nodes

18

19 construct MSTSP_instance from MSTSP_nodes

20 paths = solve(MSTSP_instance, UAV_parameters)

21 $E=\max_{p\in\text{paths}}\text{ path\\_energy}(p)$

22 if  _$E <E_{\mathrm{max}}$_ then

23 $E_{\text{max}}=E$

24 $E_{\text{tot}}=\sum_{p\in\text{paths}}\text{ path\\_energy}(p)$
$\triangleright$ sum of path energies over generated paths

25 best_paths = paths

26

27

28
$N_{\text{paths}}=\max\\{\text{ceil}(E_{\text{tot}}/E_{\text{bound}}),N_{\text{paths}}+1\\}$

29

Algorithm 1 Energy-aware multi-UAV CPP

After the transformation to MS-TSP, the instance is solved on the created
graph representation. The solver uses Greedy Randomized Adaptive Search
Procedure [26] with Greedy Random Search Procedure GRP for initial solution
generation followed by Tabu Search (TS) for searching for a better solution.
UAV paths are then recovered from the solution by replacing solution nodes
with corresponding coverage paths and edges with a path connecting two
adjacent paths.

###  III-B Estimation of path energy consumption

The estimation of path energy consumption is based on the pen-and-paper
algorithm introduced in [12]. Based on the UAV’s physical parameters, it can
estimate the optimal speed for maximizing the flight distance and power
consumption during either flying with such a speed or in hover conditions. The
optimal speed then minimizes the energy consumption of traveling along a
straight segment with a fixed distance. However, for energy consumption during
traveling along a path with turns and speed drops, the model has to be
extended. We use two different energy consumption estimation methods that are
different in accuracy and computation time:

  * •

estimation by generating a trajectory with Time-Optimal Path Parameterization
Based on Reachability Analysis (TOPPRA) [27],

  * •

our proposed energy consumption estimation based on path waypoints which does
not require trajectory generation and allows real-time planning on large
instances.

####  III-B1 Energy consumption estimation with TOPPRA

Even though the TOPPRA [27] is not originally designed for UAV trajectory
generation, it works well for our task under certain assumptions. The energy
consumption is estimated based on the UAV trajectory generated for the
coverage paths. In the beginning, the method uses a cubic spline [28]
interpolation of the path. Then, a time parametrization is found using the
TOPPRA using the optimal speed as a speed limit. The resulting trajectory is
sampled and the energy is calculated as the sum of kinetic energy differences
between each pair of neighboring points and the energy needed to keep moving
with the speed in each waypoint. The latter is calculated as either the power
spent on hover $P_{h}$ or during flight with the optimal speed $P_{r}$, both
calculated by the pen-and-paper algorithm [12]. For speeds between 0 and the
optimal velocity, the power consumption is approximated with the consumption
in hover. This is done due to the complexity of the speed-to-power consumption
relation and we show that this approximation works well in real-world
experiments described in section IV.

####  III-B2 Energy consumption estimation without trajectory generation

As computing a trajectory of long coverage paths is usually a time-consuming
task, we introduce a novel energy consumption estimation algorithm that does
not perform any trajectory generation. Accepting $N$ waypoints as an input,
the algorithm has a time complexity of $\mathcal{O}(N)$, which allows multiple
runs during the path planning phase.

Firstly, the turning properties of each turn are calculated considering the
situation depicted in Figure 3. There, the red vector, located along the $y$
axis, is the speed vector before the turn, the green one is the speed vector
after the turn and the gray vector represents the speed in the middle of the
turn. Speed is considered to change along the blue dashed line during the
turn. Value $v_{r}$ is the optimal speed for the longest range, obtained from
the pen-and-paper algorithm, $v_{in}$ is the maximum possible speed before the
turn, and $v_{ym}$ is the speed along $y$ axis in the middle of the turn. In
Fig. 3(b), the assumed turn trajectory (green line) is shown, together with
the original path marked with a solid black line, and the allowed deviation
area marked with dotted lines.

The main constraint here is the maximum allowed path deviation, which imposes
a constraint on the speed in the middle of the turn (gray vector in Fig.
3(a)). If it is large enough, the speed can change from red to green vectors
along a line, but in case of smaller deviation allowed, the UAV needs to slow
down before turning to not break the constraint.

For each turn, knowing the turning angle $\phi$, values of $v_{in}$ and
$v_{ym}$ are calculated as follows:

$\begin{split}&a_{x}=a_{max}\cdot cos(\phi/2),\hskip
20.00003pta_{y}=a_{max}\cdot sin(\phi/2),\\\ &dv_{x}=min(\sqrt{2\cdot
d_{max}a_{x}},\frac{cos(90\degree-\phi)v_{r}}{2}),\\\ &dv_{y}=tan(\phi/2)\cdot
dv_{x},\\\ &v_{ym}=\frac{dv_{x}}{tan(\phi/2)},\hskip
41.00012ptv_{in}=v_{ym}+dv_{y},\end{split}$ (1)

where $d_{max}$ is the maximal allowed deviation, $a_{max}$ is the
acceleration limit, $a_{x}$ and $a_{y}$ are the accelerations along $x$ and
$y$ axes respectively, $dv_{x}$ and $dv_{y}$ are differences between red and
grey vectors along $x$ and $y$ axes, respectively.

D. Datsko, F. Nekovar, R. Penicka and M. Saska, Energy-Aware Multi-UAV
Coverage Mission Planning With Optimal Speed of Flight, in IEEE Robotics and
Automation Letters, vol. 9, no. 3, pp. 2893-2900, March 2024,
https://doi.org/10.1109/LRA.2024.3358581. D. Datsko, F. Nekovar, R. Penicka
and M. Saska, Energy-Aware Multi-UAV Coverage Mission Planning With Optimal
Speed of Flight, in IEEE Robotics and Automation Letters, vol. 9, no. 3, pp.
2893-2900, March 2024, https://doi.org/10.1109/LRA.2024.3358581. (a)

D. Datsko, F. Nekovar, R. Penicka and M. Saska, Energy-Aware Multi-UAV
Coverage Mission Planning With Optimal Speed of Flight, in IEEE Robotics and
Automation Letters, vol. 9, no. 3, pp. 2893-2900, March 2024,
https://doi.org/10.1109/LRA.2024.3358581. D. Datsko, F. Nekovar, R. Penicka
and M. Saska, Energy-Aware Multi-UAV Coverage Mission Planning With Optimal
Speed of Flight, in IEEE Robotics and Automation Letters, vol. 9, no. 3, pp.
2893-2900, March 2024, https://doi.org/10.1109/LRA.2024.3358581. (b)

D. Datsko, F. Nekovar, R. Penicka and M. Saska, Energy-Aware Multi-UAV
Coverage Mission Planning With Optimal Speed of Flight, in IEEE Robotics and
Automation Letters, vol. 9, no. 3, pp. 2893-2900, March 2024,
https://doi.org/10.1109/LRA.2024.3358581. D. Datsko, F. Nekovar, R. Penicka
and M. Saska, Energy-Aware Multi-UAV Coverage Mission Planning With Optimal
Speed of Flight, in IEEE Robotics and Automation Letters, vol. 9, no. 3, pp.
2893-2900, March 2024, https://doi.org/10.1109/LRA.2024.3358581. (c)

Figure 3:  (a) velocity vectors during turn, (b) assumed turn trajectory, (c)
speed profile projected on path segment.

For each path segment between two turns, the speed of the UAV projected on a
path segment is assumed to have the profile depicted in Fig. 3(c). From this
assumption, depending on the specific situation (UAV can reach the optimal
speed on the segment, UAV can reach $max(v_{in1},v_{in2})$, but not $v_{r}$,
etc.), the flight time and energy consumption are found. For speeds between 0
and $v_{r}$, the power consumption is approximated with the energy in hover
similarly to the estimation with TOPPRA trajectories.

Here it can be seen that due to considering instant acceleration change and
ignoring the exact UAV position during turns that may lead to more complicated
trajectories, the algorithm has errors in energy consumption estimation. For
example, if on a path segment, the UAV can not reach the $v_{ym}$ speed before
the turn, it influences the initial speed on the next segment and further
ones. By taking into account each turn and segment separately, these relations
are ignored in the proposed algorithm. Nevertheless, the approximation is fast
which allows using it during the planning of CPP, and it is also accurate
enough as shown in real-world experiments described in section IV.

###  III-C Area decomposition

The first step of the proposed CPP algorithm previously summarized in Sec.
III-A is the area decomposition. For this purpose, the boustrophedon cellular
decomposition (BCD) [25] is used. As the algorithm implies traversing the AOI
points from left to right and creating vertical lines, the rotation of the
original AOI before decomposition leads to different decomposition results.
For estimation of the best initial rotation, the method described in [9] is
used. The area is decomposed using each of the boundary segment’s rotation as
the initial one, and each decomposition is evaluated using the cost function

$w=\sum_{i=1}^{m}y_{max,i}-y_{min,i},$ (2)

where $m$ is the number of sub-polygons, $y_{min,i}$ and $y_{max,i}$ are $y$
coordinates of lowermost and uppermost boundary points of $i$-th segment
correspondingly. Best $N_{angles}$ initial rotations minimizing the cost
function are then selected, and the whole path planning algorithm is run for
each of them separately. The $N_{angles}$ is a user-defined parameter and can
vary from 1 to the number of AOI boundary segments.

After the initial rotation is fixed, the AOI is again decomposed using BCD. In
the output, the number of sub-polygons $m$ should be $m\geq
N_{\text{UAV}}\cdot N_{min}$, where $N_{\text{UAV}}$ is the number of UAVs and
$N_{min}$ is the minimum number of sub-polygons per UAV, set by the user. If
and until this condition is not met, the largest sub-polygons are divided into
smaller ones.

The value $N_{min}$ is selected and tuned by the user for each specific
planning task. Setting it too large results in too many polygons after the
decomposition and sub-optimal coverage due to increased time of travel and
overlapping coverage between adjacent sub-polygons. On the other hand, setting
it too low can result in uneven work distribution among the UAVs.

###  III-D Sub-polygons coverage

Having the AOI decomposed into sub-polygons, multiple sweeping coverage paths
are generated for each of them. This algorithm step is based on a statistical
analysis showing that the most energy-efficient paths usually have sweeping
lines along the longest edge of the polygon. Therefore, for the $i$-th sub-
polygon $4\cdot min(N_{i,\text{feas}},N_{e})$ sweeping patterns are generated
along $min(N_{i,\text{feas}},N_{e})$ longest edges in feasible sweeping
directions. The ${N}_{i,\text{feas}}$ is the number of $i$-th feasible polygon
sweeping edges, and the ${N_{e}}$ is the maximum number of sweeping rotations
in each sub-polygon.

When creating sweeping paths along the chosen edge, the two possible start
points are located at each end of that edge at the distance $\frac{s}{2}$ from
it, where $s$ is the sweeping step. This leads to two corresponding end
locations that can also serve as start locations by changing each path’s
direction, leading to four possible sweeping paths. The sweeping direction is
feasible if vertical lines along this direction don’t leave polygon area (see
Figure 2 for an example).

###  III-E Conversion of the Multi-UAV CPP problem to MS-TSP instance

After having multiple sweeping coverage paths for sub-polygons, each is
assigned one graph node, where the weight of the node is equal to the energy
needed to fly along it. All of the nodes associated with same sub-polygon are
grouped into the same set. Edges connecting each pair of nodes from different
sets are added with the weight of an edge equal to the energy spent to travel
from the last point of the sweeping pattern associated with the source node to
the first point of the sweeping pattern associated with the destination node.
This process is depicted in Figure 2.

###  III-F MS-TSP solver

Considering that the number of nodes in generated graph may be large and that
the algorithm should obtain a solution in a short time just before the flight,
we utilize a meta-heuristic algorithm to quickly find possibly only a sub-
optimal solution. This algorithm is a modification of the Greedy Random
Adaptive Search Procedure (GRASP) meta-heuristics described in [10].

Figure 4:  Scenarios used for experimental evaluation of the proposed method.
Shade-of-green polygons represent fly-zones, red polygons are no-fly-zones,
and red dot markers represent UAVs’ initial positions. All values in the
scales are in meters.

Both the total energy consumption and the maximum energy spent by any of the
UAVs may be considered as a cost function for MS-TSP. However, both have their
respective drawbacks. The first can easily lead to uneven workload
distribution among the vehicles, while the second function might lead to
multiple solutions having the same cost, making the exploitation part of the
optimization procedure difficult. For this reason, both cost functions,
referred to as a tuple $(max\\_path\\_cost,average\\_path\\_cost)$, are used
in tandem. The maximum energy consumption is used for initial cost comparison,
and the average energy consumption is used in the case of two solutions having
the same cost.

Input: problem_instance

Output: instance_solution

1 $S_{\text{current}}$ = GRASP(problem_instance)

2 $S_{\text{best}}=S$

3 $i=0$ $\triangleright$ iterations without update

4 $T_{list}=\\{S\\}$ $\triangleright$ tabu list

5 while  _$i <i_{\mathrm{max}}$_ do

6 $N=$ solution_neighbourhood($S$)

7 $S_{\text{current}}=\operatorname*{arg\,min}_{S\in N\setminus
T_{\text{list}}}cost(S)$

8 if  _$cost(S_{\text{current}}) <cost(S_{\text{best}})$_ then

9 $S_{\text{best}}=S_{\text{current}}$

10

11

Algorithm 2 MS-TSP solver

The first step of the MS-TSP solver presented in Algorithm 2 is the Greedy
Random search Procedure (GRP) described in detail in [10]. It is used as the
initial solution generator where the solution is represented as a list of
paths with one path for every UAV. Each path is a list of graph nodes
representing the sweeping patterns and their ordering. Adaptive Tabu Search
(TS) is then used to improve the initial solution using four moves that search
through the solution neighborhood. The solution neighborhood generation uses
randomly one of the following four moves:

  1. 1.

Random shift: randomly choose a node and move it into a random position among
all paths.

  2. 2.

Best shift: Randomly choose a node. Iteratively find the best position for it
and move it there.

  3. 3.

Best swap: Randomly choose a node. Iteratively find the best node to swap it
with and swap them.

  4. 4.

Change direction: Randomly choose a node and replace it with a random node
from the same set.

After applying move procedures 1-3, the moved nodes are replaced with the best
(minimizing the cost function) nodes from the same set.

##  IV Results

For verification of the proposed method, experiments in simulation and in the
real world were performed. We first compare our approach with state-of-the-art
methods in simulation. Even though our method is the first and only one
directly minimizing energy consumption, the other methods minimize related
metrics such as the path length, that indirectly minimizes the consumption as
well. The same simulation experiments are also used to show the accuracy of
the proposed energy consumption estimation algorithm when compared to the
estimation based on the trajectory generation approach. Second, by conducting
a series of real-world experiments, we verify the accuracy of the path energy
consumption estimation based on generated trajectory combined with pen-and-
paper algorithm for power consumption calculation from [12].

All simulations were done on a computer with an Intel Core i7-10750H CPU with
16 GB of RAM and Ubuntu 20.04 OS. A custom build UAV based on Tarot T650111UAV
details - http://mrs.felk.cvut.cz/research/micro-aerial-vehicles frame (see
Figure 1 and [29]) was used for both real-world and simulation experiments.
The calculated optimal speed for the used UAV is
$8.39\text{\,}\mathrm{m}\mathrm{/}\mathrm{s}$, which is close to the maximum
speed at which the UAV with the MRS system [30] can fly autonomously. It was
also used in every simulation experiment as the maximum allowed speed input to
the trajectory generation algorithm. Values for motor and propeller efficiency
(needed for calculating the optimal speed and energy consumption [12]) were
taken from previous tests of the installed motor and propeller combination
(Tarot 4114 320KV motor with Tarot 1555 carbon fiber propeller)222Motor
parameters - https://ctu-mrs.github.io/docs/hardware/motor_tests.html. As a
result, for the energy estimation algorithm, the following parameters were
used:
$v_{r}=$8.39\text{\,}\mathrm{m}\mathrm{/}\mathrm{s}$,P_{h}=$426.03\text{\,}\mathrm{W}$,P_{r}=$465.23\text{\,}\mathrm{W}$$,
calculated with the pen-and-paper algorithm, and $a_{max}\leavevmode\nobreak\
=\leavevmode\nobreak\ $2\text{\,}\mathrm{m}\mathrm{/}\mathrm{s}^{2}$$. As for
other top-level algorithm parameters, $N_{angles}=7$, and the tuple
$(N_{min},N_{e})$ was set to $(4,4),(2,2),(1,3),(4,3),(4,3),(1,5)$ for
scenarios in Table II in this order.

###  IV-A Validation in simulation

TABLE II: Comparison of our method with state-of-the-art for scenarios with three UAVs Scenario | $E_{b}[Wh]$ | Our |  POPCORN+SALT [15] |  DARP+MST[14]
---|---|---|---|---
$E_{o}[Wh]$ | $E_{t}[Wh]$ | $l[km]$ | $t_{c}[s]$ | $E_{o}[Wh]$ | $E_{t}[Wh]$ | $l[km]$ | $t_{c}[s]$ | $E_{o}[Wh]$ | $E_{t}[Wh]$ | $l[km]$ | $t_{c}[s]$
Cape | $+\infty$ | 202.2 | 206.6 | 36.1 | 11.3 | 298.5 | 284.7 | 46.8 | 50.2 | 209.7 | 200.0 | 34.7 | 33.9
Island | $+\infty$ | 12.7 | 11.8 | 1.6 | 0.4 | - | - | - | - | 13.3 | 12.2 | 1.5 | 5.4
Rectangle | $+\infty$ | 27.8 | 25.6 | 4.4 | 0.1 | 43.0 | 45.4 | 3.9 | 25.6 | 29.0 | 28.1 | 3.8 | 4.9
Complex 15 | $+\infty$ | 142.3 | 138.0 | 23.6 | 6.2 | - | - | - | - | 133.9 | 131.0 | 20.1 | 32.6
Complex 10 | $+\infty$ | 205.0 | 208.0 | 34.7 | 7.8 | - | - | - | - | 195.9 | 189.1 | 29.8 | 70.3
Simple | $+\infty$ | 65.1 | 62.5 | 10.5 | 0.0 | 132.5 | 125.4 | 11.1 | 170.7 | 72.7 | 68.5 | 9.3 | 12.2
Complex 10 | $130$ | 109.0 | 103.0 | 36.4 | 12.8 | - | - | - | - | - | - | - | -
TABLE III: Comparison of our method with state-of-the-art for scenarios with
one UAV

Scenario | Our |  GTSP[9]
---|---|---
$E_{o}[Wh]$ | $E_{t}[Wh]$ | $l[km]$ | $t_{c}[s]$ | $E_{o}[Wh]$ | $E_{t}[Wh]$ | $l[km]$ | $t_{c}[s]$
Cape | 479.6 | 477.3 | 29.2 | 0.0 | 621.9 | 628.0 | 36.7 | 2.2
Island | 31.9 | 30.8 | 1.4 | 0.1 | 36.5 | 35.3 | 1.6 | 0.4
Rectangle | 71.9 | 65.4 | 3.9 | 0.0 | 67.5 | 63.2 | 3.7 | 0.1
Complex 15 | 381.3 | 379.0 | 21.7 | 2.2 | 449.6 | 461.1 | 25.7 | 2.1
Complex 10 | 554.0 | 544.7 | 31.7 | 1.8 | 621.3 | 615.0 | 36.4 | 2.5
Simple | 171.5 | 171.9 | 9.8 | 0.0 | 167.6 | 156.0 | 9.7 | 0.4

TABLE IV: Comparison of real and estimated energy consumptions in real-world flights Experiment | $v_{max}[m/s]$ | $t[s]$ | $E_{\text{real}}[Wh]$ | $E_{\text{est}}[Wh]$ | $acc[\%]$
---|---|---|---|---|---
1 | 2 m/s | 132.0 | 14.65 | 15.06 | 97.27
2 | 4 m/s | 82.3 | 9.40 | 9.42 | 99.78
3 | 8 m/s | 58.0 | 6.60 | 6.89 | 95.79
4 | 10 m/s | 41.8 | 4.80 | 5.19 | 92.48
5 | 2 m/s | 204.0 | 23.14 | 23.27 | 99.44
6 | 4 m/s | 107.0 | 12.25 | 12.26 | 99.90
7 | 8 m/s | 70.8 | 8.01 | 8.36 | 95.63

The performance of our method compared to the existing approaches was
validated in simulations, together with the precision of the energy
consumption estimation. Three existing implementations of the state-of-the-art
approaches were used for comparison: POPCORN+SALT algorithms from [15]
implemented as a Python library; GTSP approach described in [9] and
implemented as a Robotic Operating System (ROS) node; and DARP+MST solution
approach [14] implemented in Java. Each algorithm was used to generate paths
for each of the test scenarios:

  * •

Cape: one of AOI used in [2], Cape Crozier on Ross Island in Antarctica, with
the same parameters as in [2],

  * •

Island: simple shape with one No-Fly-Zone (NFZ) in the middle, 8m coverage
footprint width,

  * •

Rect: a rectangle with no NFZ, 8m coverage footprint width,

  * •

Complex 15: complex shape with a NFZ, 15m coverage footprint width,

  * •

Complex 10: same shape as in the previous one, but 10m coverage footprint
width,

  * •

Simple: simple shape with no NFZ, 6m coverage footprint width.

The graphical overview of the test scenarios together with an example of
planned paths using our method is shown in Figure 4 with a scale in meters to
give a size reference.

The simulation results are shown in Table II for scenarios with three UAVs and
Table III for one UAV. In the tables, $E_{b}$ is the energy budget of each
UAV, $E_{o}$ is the maximum energy consumption among all the produced
trajectories estimated by our fast method without trajectory generation, and
$E_{t}$ is the maximum energy consumption estimated with the method based on
trajectory generation. Variable $l$ denotes the produced path length and
$t_{c}$ is the computation time. Some measurements for the SALT+POPCORN [15]
algorithm are skipped (marked ‘-’) as it is not possible to specify no-fly-
zones inside the AOI in the provided implementation. The energy consumption
was calculated with the same UAV physical parameters as in the real-world
experiments.

It can be seen from Table II and Table III that the proposed fast energy
consumption estimation does not deviate from the method that uses trajectory
generation by more than 10% in all the cases. Moreover, for the CPP with one
UAV (see Table III), our method outperforms the GTSP [9] quite significantly
in energy consumption in four out of six test cases while having very similar
energy consumption in simple scenarios, which can be mostly explained by the
difference in implementation of algorithm parts. At the same time, our method
is faster in computation in five out of six cases. The better performance of
our method compared to the similar GTSP [9] is caused by minimizing the energy
consumption directly inside the algorithm instead of only after the CPP paths
are used to create flight trajectories.

Similarly, our algorithm with three UAVs (see Table II) is better than the
DARP+MST [14] method in terms of energy consumption in four cases, while still
being close in two others. This shows our method’s limitation in effectively
working with complex shapes. When the area has many complex structures, the
area decomposition may produce many small sub polygons, and during coverage,
some areas on the edges of those will be covered twice. The DARP algorithm
ensures that the number of sub areas after decomposition equals the number of
UAVs and that each has a point close to the start. Compared to POPCORN+SALT
[15], the proposed method is more energy-efficient in each of the three valid
cases. One of the advantages of our method is lower computation time in all
test cases. This is partially due to the cellular decomposition approach,
where the number of sub-polygons does not necessarily grow with an increased
AOI size or decreased sweeping step. However, it should also be considered
that the open-source implementations are written using different programming
languages and frameworks. With the energy constraint applied to one of the
scenarios (last row of Table II), our approach is the only one that can
adaptively adjust the number of produced paths (six in this case) to satisfy
it.

###  IV-B Real world experiments

We performed two types of real-world experiments, first to verify the energy
estimation accuracy, and second, to test the feasibility of the method in real
deployment with multiple UAVs. During the experiments, all CPP trajectories
were smoothed using the polynomial method described in [31]. After receiving
trajectories, the flight was fully autonomous, controlled by the MRS UAV
system [30, 32, 29] using linear Model Predictive Control [33], and running on
the onboard computer.

The precision of the energy estimation compared to the real consumption was
verified in a series of seven experiments using coverage paths with different
flight speeds. In each case, a coverage path for a simple polygon was
produced. While the polygon for coverage was slightly different for
experiments number 1-3 and the path was significantly shorter in experiment
number 4, in experiments 5, 6 and 7 UAV followed the same path. The results of
these experiments are shown in Table IV. There, $v_{max}$ is the maximum speed
bound, $t$ is the time of following the trajectory, $E_{real}$ is the measured
energy consumption using calibrated flight controller internal circuit,
$E_{est}$ is the estimated energy consumption, and $acc$ is the estimation
accuracy calculated as
${acc=100\cdot(1-\frac{|E_{real}-E_{est}|}{E_{real}})}$. The value of
$E_{est}$ was estimated by sampling the UAV trajectory produced by the
polynomial method [34] and running the algorithm described above. As can be
seen from the results, the average estimation accuracy was $97.18\%$, which we
consider to be accurate enough for real UAV deployment.

Finally, we test the feasibility of the proposed coverage planning in real
deployment with two UAVs. The overview of the AOI, generated paths, and
stitched images taken from cameras mounted on UAVs is shown in Figure 1.
Recording of the experiment together with the description of our method can be
found in the linked video https://youtu.be/S8kjqZp-G-0.

##  V Conclusions

We proposed a new energy-aware multi-UAV coverage path planning algorithm
based on exact cellular decomposition and MS-TSP formulation. This is, to the
best of our knowledge, the first solution that directly minimize the energy
consumption in the multi-UAV CPP. By introducing energy awareness during the
coverage path planning phase and by using optimal flight speed for coverage,
the proposed method can both minimize the energy consumption of the coverage
paths and constrain path energy consumption of a single path to allow
realistic missions with a limited battery capacity. We compared the approach
to the state-of-the-art methods on a set of simulation experiments, where it
outperformed them in a majority of cases in terms of energy consumption with
average energy savings from $0.4\%$ up to $40.4\%$. Our method also showed
better computational times in all but one test scenario. The proposed energy
consumption estimation was tested in real flights, where in each test its
accuracy was on average $97\%$. Moreover, the feasibility of the proposed
method was verified in a real coverage experiment with two UAVs.

## References

  * [1] L. C. Santos, F. N. Santos, E. J. Solteiro Pires _et al._ , “Path planning for ground robots in agriculture: a short review,” in _IEEE International Conference on Autonomous Robot Systems and Competitions (ICARSC)_ , 2020, pp. 61–66.
  * [2] K. Shah, G. Ballard, A. Schmidt _et al._ , “Multidrone aerial surveys of penguin colonies in antarctica,” _Science Robotics_ , vol. 5, p. 3000, 10 2020.
  * [3] A. Nedjati, G. Izbirak, B. Vizvari _et al._ , “Complete coverage path planning for a multi-uav response system in post-earthquake assessment,” _Robotics_ , vol. 5, no. 4, 2016.
  * [4] I. Maza, F. Caballero, J. Capitán _et al._ , “Experimental results in multi-uav coordination for disaster management and civil security applications,” _Journal of Intelligent & Robotic Systems_, vol. 61, no. 1, pp. 563–585, 2011.
  * [5] J. A. Guerrero and Y. Bestaoui, “Uav path planning for structure inspection in windy environments,” _Journal of Intelligent & Robotic Systems_, vol. 69, no. 1, pp. 297–311, Jan 2013.
  * [6] T. M. Cabreira, L. B. Brisolara, and P. R. Ferreira Jr., “Survey on coverage path planning with unmanned aerial vehicles,” _Drones_ , vol. 3, no. 1, 2019\.
  * [7] T. M. Cabreira, C. D. Franco, P. R. Ferreira _et al._ , “Energy-aware spiral coverage path planning for uav photogrammetric applications,” _IEEE Robotics and Automation Letters_ , vol. 3, no. 4, pp. 3662–3668, 2018\.
  * [8] C. Di Franco and G. Buttazzo, “Coverage path planning for uavs photogrammetry with energy and resolution constraints,” _Journal of Intelligent & Robotic Systems_, vol. 83, no. 3, pp. 445–462, 2016.
  * [9] R. Bähnemann, N. Lawrance, J. J. Chung _et al._ , “Revisiting boustrophedon coverage path planning as a generalized traveling salesman problem,” in _Proceedings of the 12th Conference on Field and Service Robotics_ , 2019, pp. 1–14.
  * [10] F. Nekovář, J. Faigl, and M. Saska, “Multi-tour set traveling salesman problem in planning power transmission line inspection,” _IEEE Robotics and Automation Letters_ , vol. 6, no. 4, pp. 6196–6203, 2021.
  * [11] M. Fischetti, J. J. S. González, and P. Toth, “The symmetric generalized traveling salesman polytope,” _Networks_ , vol. 26, no. 2, pp. 113–123, 1995\.
  * [12] L. Bauersfeld and D. Scaramuzza, “Range, endurance, and optimal speed estimates for multicopters,” _IEEE Robotics and Automation Letters_ , vol. 7, no. 2, pp. 2953–2960, 2022.
  * [13] H. Choset, “Coverage of known spaces: The boustrophedon cellular decomposition,” _Autonomous Robots_ , vol. 9, no. 3, pp. 247–253, 2000.
  * [14] S. Apostolidis, P. Kapoutsis, A. Kapoutsis _et al._ , “Cooperative multi-uav coverage mission planning platform for remote sensing applications,” _Autonomous Robots_ , vol. 46, pp. 1–28, 2022.
  * [15] K. Shah, A. Schmidt, G. Ballard _et al._ , “Large scale aerial multi-robot coverage path planning,” _Field Robotics_ , vol. 2, pp. 1971–1998, 2022\.
  * [16] E. Galceran and M. Carreras, “A survey on coverage path planning for robotics,” _Robotics and Autonomous Systems_ , vol. 61, no. 12, pp. 1258–1276, 2013.
  * [17] T. K. Ralphs, L. Kopman, W. R. Pulleyblank _et al._ , “On the capacitated vehicle routing problem,” _Mathematical programming_ , vol. 94, pp. 343–359, 2003.
  * [18] Y. Li, H. Chen, M. Joo Er _et al._ , “Coverage path planning for uavs based on enhanced exact cellular decomposition method,” _Mechatronics_ , vol. 21, no. 5, pp. 876–885, 2011.
  * [19] J. Hnidka and D. Rozehnal, “Calculation of the maximum endurance of a small unmanned aerial vehicle in a hover,” _IOP Conference Series: Materials Science and Engineering_ , vol. 664, no. 1, p. 012002, 2019.
  * [20] M. E. Lussier, J. M. Bradley, and C. Detweiler, _Extending Endurance of Multicopters: The Current State-of-the-Art_. AIAA, 2019.
  * [21] S. S. Mansouri, C. Kanellakis, E. Fresk _et al._ , “Cooperative coverage path planning for visual inspection,” _Control Engineering Practice_ , vol. 74, pp. 118–131, 2018.
  * [22] A. C. Kapoutsis, S. A. Chatzichristofis, and E. B. Kosmatopoulos, “Darp: Divide areas algorithm for optimal multi-robot coverage path planning,” _Journal of Intelligent & Robotic Systems_, vol. 86, no. 3, pp. 663–680, 2017.
  * [23] P. Surynek, “Simple direct propositional encoding of cooperative path finding simplified yet more,” in _Nature-Inspired Computation and Machine Learning_ , 11 2014, pp. 410–425.
  * [24] J. Xie and J. Chen, “Multiregional coverage path planning for multiple energy constrained uavs,” _IEEE Transactions on Intelligent Transportation Systems_ , vol. 23, no. 10, pp. 17 366–17 381, 2022.
  * [25] H. Choset and P. Pignon, “Coverage path planning: The boustrophedon cellular decomposition,” in _Field and Service Robotics_ , A. Zelinsky, Ed. London: Springer London, 1998, pp. 203–209.
  * [26] O. Guemri, A. Bekrar, B. Beldjilali _et al._ , “Grasp-based heuristic algorithm for the multi-product multi-vehicle inventory routing problem,” _4OR_ , vol. 14, no. 4, pp. 377–404, 2016.
  * [27] H. Pham and Q.-C. Pham, “A new approach to time-optimal path parameterization based on reachability analysis,” _IEEE Transactions on Robotics_ , vol. 34, no. 3, pp. 645–659, 2018.
  * [28] S. McKinley and M. Levine, “Cubic spline interpolation,” _College of the Redwoods_ , vol. 45, no. 1, pp. 1049–1060, 1998.
  * [29] D. Hert, T. Baca, P. Petracek _et al._ , “MRS drone: A modular platform for real-world deployment of aerial multi-robot systems,” _Journal of Intelligent & Robotic Systems_, vol. 108, no. 4, p. 64, Jul 2023.
  * [30] T. Baca, M. Petrlik, M. Vrba _et al._ , “The MRS UAV System: Pushing the Frontiers of Reproducible Research, Real-world Deployment, and Education with Autonomous Unmanned Aerial Vehicles,” _Journal of Intelligent & Robotic Systems_, vol. 102, no. 1, p. 26, 2021.
  * [31] M. Burri, H. Oleynikova, _et al._ , “Real-time visual-inertial mapping, re-localization and planning onboard mavs in unknown environments,” in _Intelligent Robots and Systems_ , Sept 2015.
  * [32] D. Hert, T. Baca, P. Petracek _et al._ , “MRS Modular UAV Hardware Platforms for Supporting Research in Real-World Outdoor and Indoor Environments,” in _International Conference on Unmanned Aircraft Systems_ , 2022.
  * [33] T. Baca, D. Hert, G. Loianno _et al._ , “Model predictive trajectory tracking and collision avoidance for reliable outdoor deployment of unmanned aerial vehicles,” in _IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)_ , 2018, pp. 6753–6760.
  * [34] C. Richter, A. Bry, and N. Roy, “Polynomial trajectory planning for aggressive quadrotor flight in dense indoor environments,” in _Robotics Research_ , 2016, pp. 649–666.