Trimer covers in the triangular grid:

twenty mostly open problems

James Propp, UMass Lowell

November 10, 2022

###### Abstract

Physicists have studied the asymptotics of the trimer model on the triangular
lattice but have not given exact results for finite subgraphs of the
triangular lattice analogous to known solutions of the dimer model on finite
subgraphs of various lattices. Here I introduce finite subgraphs of the
triangular lattice that will be of interest to enumerative combinatorialists
inasmuch as the precise number of trimer covers appears to be given by exact
formulas in many cases.

##  1 Introduction

If $G=(V,E)$ is a finite graph, a trimer on $G$ is a three-element subset of
$V$ whose induced subgraph in $G$ is connected, and a trimer cover is a
partition of $V$ into trimers. Solving the trimer model for $G$ means counting
the possible trimer covers.

Physicists have studied the asymptotics of the trimer model on the triangular
lattice and obtained formulas for the entropy in various regimes (see e.g.
[VeNi]). These results can be seen as analogous to formulas for the entropy of
dimer models on various kinds of finite graphs; the original dimer results,
due to Temperley and Fisher [TeFi] and Kasteleyn [Kast], were proved using the
determinant method, while other approaches were used in more recent work such
as [EKLP]. These rigorously proved exact formulas have no counterpart in the
literature on trimers.

Here I introduce finite subgraphs of the triangular lattice that should
interest enumerative combinatorialists inasmuch as the number of trimer covers
appears to be given by exact formulas in many cases. This is a companion to
the talk I gave at the Open Problems in Algebraic Combinatorics conference on
May 18, 2022; the slides and video can be accessed through the conference
website at http://www.samuelfhopkins.com/OPAC/opac.html.

Consider the complex plane tiled by unit hexagonal cells centered at 1,
$\omega$, and $\omega^{2}$ (here and hereafter $\omega$ always denotes a
primitive 3rd root of unity); the cell centered at $\alpha$ has corners at
$\alpha\pm 1$, $\alpha\pm\omega$, and $\alpha\pm\omega^{2}$. Given positive
integers $a,b$ satisfying $2\leq a\leq 2b$ and $2\leq b\leq 2a$, we define the
$\boldsymbol{(a,b)}$-benzel as the union of the cells that lie fully inside
the hexagon with vertices $a\omega+b$, $-a\omega^{2}-b$,
$a\omega^{2}+b\omega$, $-a-b\omega$, $a+b\omega^{2}$, and
$-a\omega-b\omega^{2}$ (a hexagon centered at 0 with threefold rotational
symmetry whose side-lengths alternate between $2a-b$ and $2b-a$, degenerating
to a triangle when $a=2b$ or $b=2a$), as shown in Figure 1 for $a=4$, $b=6$.
We lose no generality in assuming $2\leq a\leq 2b$ and $2\leq b\leq 2a$, since
the $(a,b)$-benzel as defined above coincides with the $(a,a-b)$-benzel when
$a>2b$ and with the $(b-a,b)$-benzel when $b>2a$, the former satisfying $a\leq
2(a-b)$ and the latter satisfying $b\leq 2(b-a)$.

Figure 1: The (4,6)-benzel and its enclosing hexagon.

Here is an alternative description of benzels in terms of the centers of the
cells using barycentric coordinates relative to the triangle with vertices 1,
$\omega$, and $\omega^{2}$. Each cell’s center point $\alpha$ belongs to
$\mathbb{Z}[\omega]$ and can be represented by the unique
$(i,j,k)\in\mathbb{Z}^{3}$ satisfying $i+j\omega+k\omega^{2}=\alpha$ and
$i+j+k=1$ (here and hereafter $i$ never denotes a primitive 4th root of
unity). Then the $(a,b)$-benzel consists of those cells whose centers
$(i,j,k)$ satisfy $-(a\\!-\\!1)\leq j\\!-\\!i,k\\!-\\!j,i\\!-\\!k\leq
b\\!-\\!1$. Figure 2 shows the (4,6)-benzel with its cells marked with the
barycentric coordinates of their respective center points.

Figure 2: Barycentric coordinates for the cells of the (4,6)-benzel.

Let $V=\\{(i,j,k)\in\mathbb{Z}^{3}\ :\ i+j+k=1,\ -(a\\!-\\!1)\leq
j\\!-\\!i,k\\!-\\!j,i\\!-\\!k\leq b\\!-\\!1\\}$. Given $(i_{1},j_{1},k_{1})$
and $(i_{2},j_{2},k_{2})$ in $V$, join $(i_{1},j_{1},k_{1})$ and
$(i_{2},j_{2},k_{2})$ by an edge when
$|i_{1}\\!-\\!i_{2}|+|j_{1}\\!-\\!j_{2}|+|k_{1}\\!-\\!k_{2}|=2$ (that is, when
the unit hexagons centered on those two vertices share an edge). This is the
$\boldsymbol{(a,b)}$-benzel graph.

The $(a,b)$-benzel has threefold rotational symmetry but for most $a,b$ it
does not have bilateral symmetry. Exchanging $a$ and $b$ corresponds to
reflecting the benzel across a horizontal axis (or if one prefers across an
axis making a 60 degree angle with the horizontal axis).

We consider tilings of the $(a,b)$-benzel by way of five sorts of prototiles,
which we may translate but not rotate. These prototiles (shown in Figure 3)
are the right(-pointing) stone, the left(-pointing) stone, the vertical bone,
the rising bone, and the falling bone. The right stone is a benzel
(specifically, the (2,2)-benzel) but the left stone is not. Dually we form
spanning subgraphs of the $(a,b)$-benzel graph whose connected components all
consist of three vertices. Figure 4 shows a tiling of the (9,9)-benzel and the
associated trimer cover of the (9,9)-benzel graph.

Figure 3: The five prototiles: the right stone, the left stone, the vertical
bone, the rising bone, and the falling bone. Figure 4: The (9,9)-benzel tiled
by stones and bones and the associated trimer cover of the (9,9)-benzel graph.

Conway and Lagarias studied such tilings (calling stones and bones $T_{2}$ and
$L_{3}$ tiles respectively). They showed that for any simply-connected region
in the hexagonal grid that can be tiled by stones and bones, the total area of
the right stones minus the total area of the left stones does not depend on
the specific tiling but only depends on the region being tiled. This is the
Conway-Lagarias invariant of the region. It can be shown (see the companion
article [KiPr]) that the area of the $(a,b)$-benzel (as measured by the number
of tiles) is given by

$\begin{array}[]{ll}(-a^{2}+4ab-b^{2}-a-b)/2&\mbox{if $a+b\equiv 0$ or 2 (mod
3)},\\\ (-a^{2}+4ab-b^{2}-a-b+2)/2&\mbox{if $a+b\equiv 1$ (mod 3)}\\\
\end{array}$

while the value of the Conway-Lagarias invariant is

$\begin{array}[]{ll}(3a^{2}-6ab+3b^{2}-a-b)/2&\mbox{if $a+b\equiv 0$ (mod
3)},\\\ (-a^{2}+4ab-b^{2}-a-b+2)/2&\mbox{if $a+b\equiv 1$ (mod 3)},\\\
(3a^{2}-6ab+3b^{2}+a+b-2)/2&\mbox{if $a+b\equiv 2$ (mod 3).}\\\ \end{array}$

(The expressions in Theorem 2 of [KiPr] have opposite sign because the benzels
in that article are mirror images of the benzels considered here.) Note that
when $a+b\equiv 1$ (mod 3), the Conway-Lagarias invariant is equal to the area
of the benzel so that the tiling must consist entirely of right-pointing
stones; for instance, this is the case with the (4,6)-benzel shown earlier.

The set of 5 prototiles has $2^{5}-1=31$ nonempty subsets, and for each, we
can ask in how many ways it is possible to tile the $(a,b)$-benzel, that is,
find translates of the prototiles whose interiors are disjoint and whose union
is the benzel. There is some redundancy here. Because the benzel has threefold
rotational symmetry, and because 120 degree rotations preserve the two stones’
orientation (right versus left), the number of tilings depends only on (a)
whether right stones are allowed, (b) whether left stones are allowed, and (c)
how many of the three kinds of bones are allowed (0, 1, 2, or 3). Thus there
are really only $(2)(2)(4)-1=15$ tiling problems to consider. For $0\leq
i,j\leq 1$ and $0\leq k\leq 3$ we define $T_{ijk}(a,b)$ as the number of ways
to tile the $(a,b)$-benzel if the set of allowed prototiles contains the right
stone iff $i=0$, contains the left stone iff $j=0$, and contains $k$ of the
bones. We say that such a tiling is an $i,j,k$ tiling.

It is not hard to show (using the aforementioned rotational symmetry) that for
each of the 15 cases, $T_{ijk}(a,b)=T_{ijk}(b,a)$. It is also not hard to show
that the $(n,2n)$-benzel is the same as the $(n,2n-1)$-benzel and the
$(n,2n-2)$-benzel. Consequently, in the tables that follow we will often
assume $2\leq a\leq 2b-2$ and $2\leq b\leq 2a-2$.

It is also easy to show that when $i=0$ and $a+b\equiv 2$ (mod 3),
$T_{ijk}(a,b)=0$. That is because in this case the Conway-Lagarias invariant
is $(3(a-b)^{2}+(a+b-2))/2>0$, implying that every tiling of the
$(a,b)$-benzel must have at least one right-pointing stone.

David desJardins wrote a general purpose program TilingCount that I used to
enumerate tilings of regions with various sets of allowed prototiles. This led
to the questions and conjectures that appear below. I am happy to share the
code and the data on which my conjectures are based (some of which appear in
the Appendix). Here is a map of the first eighteen problems presented in this
article as they relate to those fifteen cases. Rows describe which stones are
allowed; columns describe how many bones are allowed.

$\begin{array}[]{c|c|c}&\rm Two\ kinds\ of\ bones&\rm Three\ kinds\ of\
bones\\\ \hline\cr\rm No\ stones&\mbox{(no tilings exist)}&\mbox{type 003:
prob.\ 1}\\\ \hline\cr\rm Left\ stones&\mbox{type 012: probs.\ 2--
3}&\mbox{type 013: prob.\ 4}\\\ \hline\cr\rm Right\ stones&\mbox{type 102:
prob.\ 5}&\mbox{type 103: probs.\ 6--7}\\\ \hline\cr\rm Both\ kinds\ of\
stones&\mbox{type 112: probs.\ 8--13}&\mbox{type 113: probs.\ 14--
18}\end{array}$

(This table omits cases where the number of allowed bone prototiles is zero or
one; in such situations at most one tiling exists, even when both stone
prototiles are allowed.)

Benzels behave differently according to whether $a+b$ is 0, 1, or 2 (mod 3),
so in what follows we will often divide conjectures into these three cases.

In the cases where only two kinds of bone tiles are permitted, the allowed
tilings can be viewed as ribbon tilings, as in [Pak]; indeed, this was the
mode of presentation employed in [CoLa], with four of the five prototiles
being depicted as ribbons. Switching over to the ribbon tilings presentation
has already yielded solutions to problems 2 and 3 in [DLPY], and is likely to
provide leverage on other problems in the first column of the table.

##  2 No stones, three kinds of bones

Prior to the conference, I was able to show that if an $(a,b)$-benzel can be
tiled by bones, then we must have $a=k(3k-1)/2$ and $b=k(3k+1)/2$ (or vice
versa) for some $k\geq 2$. Several attending students found a proof that this
necessary condition is also sufficient. (Note that such benzels belongs to the
case $a+b\equiv 0$ (mod 3).) Jesse Kim found the most complete solution,
providing an explicit proof that the tiling he described works for all $k$. It
appears that the number of such tilings grows exponentially in $k^{4}$ (see
Appendix 1 for the data).

Problem 1: Find an exact formula for $T_{003}(k(3k-1)/2,k(3k+1)/2)$.

Of course, even short of an exact formula, any method of determining the
number of tilings that is more efficient than brute-force enumeration (e.g., a
recurrence relation) would be of interest.

See [KiPr] for more discussion of no-stones tilings of benzels.

##  3 Left stones, two kinds of bones

Figure 5 shows the values of $T_{012}(a,b)$ for $a,b\leq 10$.

$\begin{array}[]{c|ccccccccc}a\backslash b&2&3&4&5&6&7&8&9&10\\\ \hline\cr
2&0&&&&&&&&\\\ 3&&{\bf 2}&0&&&&&&\\\ 4&&0&0&{\bf 2}&0&&&&\\\ 5&&&{\bf
2}&0&0&0&0&&\\\ 6&&&0&0&{\bf 8}&0&0&0&0\\\ 7&&&&0&0&0&{\bf 8}&0&0\\\
8&&&&0&0&{\bf 8}&0&0&0\\\ 9&&&&&0&0&0&{\bf 48}&0\\\ 10&&&&&0&0&0&0&0\\\
\end{array}$ Figure 5: Values of $T_{012}(a,b)$.

Problem 2: Is it true that $T_{012}(3n,3n)=2^{n}n!$ for $n\geq 1$?

Problem 3: Is it true that $T_{012}(3n+1,3n+2)=2^{n}n!$ for $n\geq 1$?

Comment: Note that by $a,b$ symmetry the formula implies
$T_{012}(3n+2,3n+1)=2^{n}n!$. Henceforth we will omit such corollaries without
comment.

Comment: Colin Defant, Rupert Li, Benjamin Young and I worked on problem 2
during the conference and later succeeded in solving Problems 2 and 3; see
[DLPY]. We were also able to verify that the pattern of entries equal to 0 and
1 in Figures 5 and 7 persists for all larger values of $a$ and $b$.

##  4 Left stones, three kinds of bones

Figure 6 shows the values of $T_{013}(a,b)$ for $a,b\leq 10$.

$\begin{array}[]{c|ccccccccc}a\backslash b&2&3&4&5&6&7&8&9&10\\\ \hline\cr
2&0&&&&&&&&\\\ 3&&{\bf 3}&0&&&&&&\\\ 4&&0&0&{\bf 9}&0&&&&\\\ 5&&&{\bf
9}&0&0&{\bf 2}&0&&\\\ 6&&&0&0&{\bf 144}&0&0&0&0\\\ 7&&&&{\bf 2}&0&0&{\bf
1143}&0&0\\\ 8&&&&0&0&{\bf 1143}&0&0&{\bf 825}\\\ 9&&&&&0&0&0&{\bf 73454}&0\\\
10&&&&&0&0&{\bf 825}&0&0\\\ \end{array}$ Figure 6: Values of $T_{013}(a,b)$.

When $a$ and $b$ are such that the Conway-Lagarias invariant is strictly
positive, the $(a,b)$-benzel cannot be tiled by bones and left stones; the
corresponding entries in the table must be zero. On the other hand, when $a$
and $b$ are such that the Conway-Lagarias invariant is negative or zero, the
entries in the table are observed to be positive, though I see no reason for
concluding that they are.

Problem 4: Is it true that when the Conway-Lagarias invariant associated with
the $(a,b)$-benzel is negative or zero, tilings of type 013 exist?

Comment: In fact, in this regime (and in the regimes described in succeeding
sections), the number of tilings appears to grow as an exponential function of
the area of the region being tiled, at least when the asymptotic ratio of $a$
to $b$ is chosen properly.

##  5 Right stones, two kinds of bones

Figure 7 shows the values of $T_{102}(a,b)$ for $a,b\leq 10$.

$\begin{array}[]{c|ccccccccc}a\backslash b&2&3&4&5&6&7&8&9&10\\\ \hline\cr
2&1&&&&&&&&\\\ 3&&0&1&&&&&&\\\ 4&&1&{\bf 2}&0&1&&&&\\\ 5&&&0&1&{\bf
4}&0&1&&\\\ 6&&&1&4&0&1&{\bf 10}&0&1\\\ 7&&&&0&1&{\bf 8}&0&1&\bf{28}\\\
8&&&&1&10&0&1&{\bf 24}&0\\\ 9&&&&&0&1&24&0&1\\\ 10&&&&&1&28&0&1&{\bf 48}\\\
\end{array}$ Figure 7: Values of $T_{102}(a,b)$.

Problem 5: Is it true that

$T_{102}(n+3k,2n+3k-1)=\prod_{i=1}^{k}\frac{(2i)!(2i+2n-2))!}{(i+n-1)!(i+n+k-1)!}$

for $k\geq 0$ and $n\geq 1$ (except $(k,n)=(0,1))$?

Comment: This formula and the $a,b$ symmetry relation together provide a
conjectural enumeration of tilings of type 102 of the $(a,b)$-benzel for all
$a,b$ satisfying $a+b\equiv 2$ (mod 3).

Comment: Three special cases merit special attention. When $k=1$, the right-
hand side of the equation is twice the $n$th Catalan number; when $n=1$, the
right-hand side of the equation is $2^{k}k!$; and when $n=2$, the right-hand
side of the equation is $2^{k}(k+1)!$.

##  6 Right stones, three kinds of bones

Figure 8 shows the values of $T_{103}(a,b)$ for $a,b\leq 10$.

$\begin{array}[]{c|ccccccccc}a\backslash b&2&3&4&5&6&7&8&9&10\\\ \hline\cr
2&1&&&&&&&&\\\ 3&&{\bf 0}&1&&&&&&\\\ 4&&1&7&{\bf 0}&1&&&&\\\ 5&&&0&1&33&{\bf
2}&1&&\\\ 6&&&1&33&0&1&164&{\bf 21}&1\\\ 7&&&&2&1&666&0&1&864\\\
8&&&&1&164&0&1&12430&0\\\ 9&&&&&21&1&12430&0&1\\\
10&&&&&1&864&0&1&655721\end{array}$ Figure 8: Values of $T_{103}(a,b)$.

Problem 6: Is is true that $T_{103}(n,2n-3)=(3n+3)(3n-7)!/(n-5)!(2n-1)!$ for
$n\geq 5$? (The formula works for $n=3$ and $n=4$ if one treats $1/(-1)!$ and
$1/(-2)!$ as 0.)

Aside from the fact that Problems 2 and 6 involve different prototile sets,
the two problems differ in another important way: in problem 2 we have
$b/a\rightarrow 1$ as $n\rightarrow\infty$ while in problem 6 we have
$b/a\rightarrow 2$ as $n\rightarrow\infty$. In the former case we say that the
sequence is associated with a central diagonal of the table of values while in
the latter case we say that the sequence is associated with a peripheral
diagonal (recall that $a/b$ and $b/a$ cannot exceed 2).

In parallel with the observations that preceded Problem 4, note that when the
Conway-Lagarias invariant of a benzel is strictly negative, the benzel cannot
be tiled by bones and right-pointing stones; the corresponding entries in the
table must be zero. On the other hand, when $a$ and $b$ are such that the
Conway-Lagarias invariant is positive or zero, the entries in the table are
observed to be positive, though I see no reason for concluding that they are.

Problem 7: Is it true that when the Conway-Lagarias invariant associated with
the $(a,b)$-benzel is positive or zero, tilings of type 103 exist?

##  7 Both stones, two kinds of bones

Figure 9 shows the values of $T_{112}(a,b)$ for $a,b\leq 10$.

$\begin{array}[]{c|ccccccccc}a\backslash b&2&3&4&5&6&7&8&9&10\\\ \hline\cr
2&1&&&&&&&&\\\ 3&&{\bf 2}&1&&&&&&\\\ 4&&1&{\bf 4}&{\bf 6}&1&&&&\\\
5&&&6&1&{\bf 16}&{\bf 22}&1&&\\\ 6&&&1&16&{\bf 48}&1&{\bf 68}&{\bf 90}&1\\\
7&&&&22&1&{\bf 224}&{\bf 512}&1&{\bf 304}\\\ 8&&&&1&68&512&1&{\bf
3360}&6736\\\ 9&&&&&90&1&3360&{\bf 15360}&1\\\ 10&&&&&1&304&6736&1&{\bf
168960}\\\ \end{array}$ Figure 9: Values of $T_{112}(a,b)$.

Here are the first few values of $T_{112}(3n,3n)$, given in factored form:

$\begin{array}[]{c}2^{1},\\\ 2^{4}\>3^{1},\\\ 2^{10}\>3^{1}\>5^{1},\\\
2^{16}\>7^{1}\>11^{1}\>13^{1},\\\ 2^{28}\>3^{2}\>7^{1}\>13^{1}\>17^{1},\\\
2^{38}\>3^{2}\>11^{1}\>17^{2}\>19^{2},\\\
2^{50}\>5^{1}\>11^{2}\>13^{1}\>17^{1}\>19^{2}\>23^{2},\\\
2^{64}\>3^{3}\>5^{4}\>11^{1}\>13^{2}\>19^{1}\>23^{3}\>29^{1},\\\
2^{84}\>3^{4}\>5^{3}\>13^{2}\>17^{1}\>23^{2}\>29^{3}\>31^{2},\dots\end{array}$

Problem 8: With $T(n)$ denoting $T_{112}(3n,3n)$ is the second quotient
$T(n)T(n+2)/T(n+1)^{2}$ equal to

$\frac{256(2n+3)^{2}(4n+1)(4n+3)^{2}(4n+5)}{27(3n+1)(3n+2)^{2}(3n+4)^{2}(3n+5)}$

for $n\geq 1$?

Comment: David desJardins found the pattern governing the numbers $T(n)$, with
assistance from Christian Krattenthaler, Greg Kuperberg and other members of
the domino listserv. The same is true for Problem 10.

Here are the first few values of $T_{112}(3n+1,3n+1)$, given in factored form:

$\begin{array}[]{c}2^{2},\\\ 2^{5}\>7^{1},\\\ 2^{10}\>3^{1}\>5^{1}\>11^{1},\\\
2^{17}\>7^{1}\>11^{1}\>13^{2},\\\ 2^{30}\>3^{1}\>13^{1}\>17^{2}\>19^{1},\\\
2^{38}\>3^{1}\>11^{1}\>17^{2}\>19^{3}\>23^{1},\dots\end{array}$

With $T(n)=T_{112}(3n+1,3n+1)$ with $n\geq 1$, it appears that $T(n)$ has no
prime factor greater than or equal to $4n$.

Problem 9: Find a formula governing this sequence.

Here are the first few values of $T_{112}(3n+1,3n+2)$, given in factored form:

$\begin{array}[]{c}2^{1}\>3^{1},\\\ 2^{9},\\\
2^{9}\>3^{1}\>5^{1}\>7^{1}\>11^{1},\\\ 2^{25}\>3^{1}\>7^{1}\>13^{1},\\\
2^{28}\>3^{2}\>11^{1}\>13^{1}\>17^{2}\>19^{1},\\\
2^{50}\>3^{1}\>11^{1}\>17^{1}\>19^{2}\>23^{1},\\\
2^{49}\>3^{2}\>5^{2}\>11^{2}\>13^{2}\>17^{1}\>19^{2}\>23^{3},\\\
2^{81}\>3^{3}\>5^{4}\>13^{2}\>23^{2}\>29^{2}\>31^{1},\dots\end{array}$

Problem 10: With $T(n)$ denoting $T_{112}(3n+1,3n+2)$, is it true that
$T(n)T(n+3)/T(n+1)T(n+2)$ is always equal to

$\frac{65536(2n+3)(2n+5)^{2}(2n+7)(4n+3)(4n+5)^{2}(4n+7)^{2}(4n+9)^{2}(4n+11)}{729(3n+2)(3n+4)^{3}(3n+5)^{2}(3n+7)^{2}(3n+8)^{3}(3n+10)}$

for $n\geq 1$?

Here are the first few values of $T_{112}(3n-1,3n)$, given in factored form:

$\begin{array}[]{c}1^{1},\\\ 2^{4},\\\ 2^{5}\>3^{1}\>5^{1}\>7^{1},\\\
2^{16}\>11^{1}\>13^{1},\\\ 2^{19}\>3^{1}\>7^{1}\>11^{1}\>13^{2}\>17^{1},\\\
2^{39}\>3^{1}\>17^{2}\>19^{2},\\\
2^{37}\>5^{1}\>11^{2}\>13^{1}\>17^{2}\>19^{3}\>23^{2},\dots\end{array}$

With $T(n)=T_{112}(3n-1,3n)$ with $n\geq 1$, it appears that $T(n)$ has no
prime factor greater than or equal to $4n$.

Problem 11: Find a formula governing this sequence.

We now switch from central diagonals to peripheral diagonals.

Problem 12: Is it true that $T_{112}(n+2,2n+1)$ is the $n$th large Schröder
number (see sequence A006318 in the OEIS) for $n\geq 1$?

Problem 13: Is it true that $T_{112}(n+2,2n)$ is always the number of “royal
paths in a lattice of order $n$” (see sequence A006319 in the OEIS) for $n\geq
1$?

##  8 Both stones, three kinds of bones

Finally we come to the most permissive situation: all prototiles are allowed.

Figure 10 shows the values of $T_{113}(a,b)$ for $a,b\leq 10$.

$\begin{array}[]{c|ccccccccc}a\backslash b&2&3&4&5&6&7&8&9&10\\\ \hline\cr
2&1&&&&&&&&\\\ 3&&3&1&&&&&&\\\ 4&&1&10&{\bf 18}&1&&&&\\\ 5&&&18&1&{\bf
84}&{\bf 142}&1&&\\\ 6&&&1&84&459&1&{\bf 724}&{\bf 1266}&1\\\
7&&&&142&1&5766&19057&1&{\bf 6516}\\\ 8&&&&1&724&19057&1&380597&1077681\\\
9&&&&&1266&1&380597&3759277&1\\\ 10&&&&&1&6516&1077681&1&185961668\\\
\end{array}$ Figure 10: Values of $T_{113}(a,b)$.

Problem 14: Is it true that $T_{113}=1$ when $a+b$ is 1 (mod 3)? (Note that
$a+b\equiv 1$ is the situation in which the Conway-Lagarias invariant
coincides with the area of the region being tiled, so that all the tiles must
be right-pointing stones.)

Comment: This problem is resolved in the affirmative by Theorem 1.1 of [DLPY].

It is disappointing that the data for $a+b\not\equiv 1$ (mod 3) do not suggest
exact conjectures. On the other hand, it is intriguing that congruence
phenomena occur, analogous to Cohn’s 2-adic continuity theorem proved in
[Cohn] and conjectural 2-adic phenomena of a similar kind discussed in [Pro].

Problem 15: Is $T_{113}(n,2n-4)$ 2-adically continuous as a function of $n\geq
5$?

Comment: The sequence appears to be constant mod 2, constant mod 4, 2-periodic
mod 8, and 8-periodic mod 16 (with repeating pattern 4, 4, 4, 4, 4, 12, 4,
12). The case $n=4$ breaks the pattern.

Problem 16: Is $T_{113}(n,2n-3)$ 2-adically continuous as a function of $n\geq
4$?

Comment: The sequence appears to be constant mod 2, constant mod 4, 2-periodic
mod 8, and 8-periodic mod 16 (with repeating pattern 2, 14, 2, 14, 10, 6, 10,
6). The case $n=3$ breaks the pattern.

At the OPAC 2022 meeting, David Speyer suggested that one might use a
different definition of a trimer, namely, a path consisting of three vertices
and two edges. Thus, each stone would correspond to three different trimers
according to which 2 of the 3 possible edges one used. Equivalently, one could
use the original definition of a trimer, with the proviso that each stone will
count with weight 3. This changes the enumerations listed above in cases where
both kinds of stones are allowed (the Conway-Lagarias invariant forces every
tiling to have the same weight as every other if only one kind of stone is
allowed) but the new numbers do not satisfy any nice patterns, with one
exception: in the case where all prototiles are allowed, using stones of
weight 3 seems to give rise to the 2-adic continuity phenomenon we saw in
Problems 11 and 12.

Let $T_{ijk}(a,b;3)$ denote the weighted sum of the $i,j,k$ tilings of the
$(a,b)$-benzel as defined near the end of section 1, where a tiling with $m$
stones has weight $3^{m}$.

Problem 17: Is $T_{113}(n,2n-4;3)$ 2-adically continuous as a function of
$n\geq 5$?

Comment: The sequence appears to be constant mod 2, constant mod 4, constant
mod 8, and 8-periodic mod 16 (with repeating pattern 4, 4, 12, 12, 4, 12, 12,
4). The case $n=4$ breaks the pattern.

Problem 18: Is $T_{113}(n,2n-3;3)$ 2-adically continuous as a function of
$n\geq 4$?

Comment: The sequence appears to be constant mod 2, constant mod 4, 2-periodic
mod 8, and 8-periodic mod 16 (with repeating pattern 14, 6, 10, 2, 6, 14, 2,
10). The case $n=3$ breaks the pattern.

##  9 Miscellaneous

The next problem is not enumerative; it is an old structural problem that has
gone unresolved for decades. There are two natural kinds of “2-flips” that can
turn one stones-and-bones tiling into another; the first trades two stones of
opposite sign for two bones, and the second trades a stone and a bone for a
stone of the same orientation and a bone of a different orientation; see
Figure 11.

Figure 11: 2-flips for changing a trimer cover.

Problem 19: Can every tiling of a finite simply-connected region using stones
and bones be mutated into every other such tiling by means of a succession of
2-flips?

Comment: It is known that the hypothesis that the region be simply-connected
cannot be dropped. It is also known that if one restricts to tilings of type
112 (that is, if one prohibits one of the three orientations of bones), then
the claim is true; Sheffield proved an equivalent claim in the context of
ribbon tilings [Shef].

In closing, we turn to the regions that Conway, Lagarias, and Thurston
originally studied: triangles of hexagonal cells, with $n$ cells on each side
(“$T_{n}$ regions”). All three authors showed that if one uses stones alone,
$T_{n}$ can be tiled by $T_{2}$’s (that is, by stones) precisely when $n$ is
congruent to 0, 2, 9, or 11 (mod 12). (In our notation, these are tilings of
type 110; such tilings were not discussed above since for benzels they are not
very interesting from an enumerative perspective.)

The question we ask is, how many such tiling are there? Sequence A334875 in
the OEIS gives the answers for many small values of $n$. If we look at the
prime factorizations of the answers, we notice that the exponent of the prime
2 is creeping upward. Specifically, the multiplicity of the prime 2 in the
factorizations of the nonzero terms in this sequence goes 0, 0, 1, 3, 2, 3, 4,
3, 4, 3, 5, 8, 6, 8, …. This is a priori surprising, since the probability
that a “random” positive integer is divisible by $2^{m}$ decreases
exponentially as $m$ increases.

Problem 20: As $n$ goes to infinity within the set of natural numbers
congruent to 0, 2, 9, or 11 (mod 12), does the number of tiling of $T_{n}$ by
stones converge 2-adically to 0?

##  10 Appendix

Here are some of the empirical data on which the conjectures stated in this
article are based.

Note: This article will undergo an “appendectomy” once the relevant sequences
are in the OEIS.

Problem 1: $T_{003}(k(3k-1)/2,k(3k+1)/2)$ for $2\leq k\leq 4$: 2, 42705,
7501790059160666750.

Problem 2: $T_{012}(3n,3n)$ for $1\leq n\leq 6$: 2, 8, 48, 384, 3840, 46080.

Problem 3: $T_{012}(3n+1,3n+2)$ for $1\leq n\leq 6$: 2, 8, 48, 384, 3840,
46080.

Problem 5: The conjecture is true for $0\leq k\leq 5$, $1\leq n\leq 5$.

Problem 6: The conjecture is true for $5\leq n\leq 16$.

Problem 8: $T_{112}(3n,3n)$ for $1\leq n\leq 9$:

$\begin{array}[]{l}2,48,15360,65601536,3737426853888,\\\
2839095978202497024,28748176693620694822420480,\\\
3879520049632381491007256002560000,\\\
6976271067658190025590579601863413334016000.\end{array}$

The conjecture is true for $1\leq n\leq 7$.

Problem 9: $T_{112}(3n+1,3n+1)$ for $1\leq n\leq 7$: 4, 224, 168960,
1705639936, 229940737867776, 413561647491497066496,
9918120959299139713735065600.

Problem 10: $T_{112}(3n+1,3n+2)$ for $1\leq n\leq 8$:

$\begin{array}[]{l}6,512,591360,9160359936,1897011087409152,\\\
5244422625774526267392,\\\ 193403358706333224417833779200,\\\
95098462720808932931887549372170240000.\end{array}$

Problem 11: $T_{112}(3n-1,3n)$ for $1\leq n\leq 7$: 1, 16, 3360, 9371648,
347950546944, 172066422921363456, 1133503548832944876421120.

Problem 12: The conjecture is true for $1\leq n\leq 15$.

Problem 13: The conjecture is true for $1\leq n\leq 15$.

Problem 14: The conjecture is true for $a+b\leq 28$.

Problem 15: $T_{113}(n,2n-4)$ for $3\leq n\leq 14$: 1, 10, 84, 724, 6516,
60900, 586404, 5777916, 57952212, 589381020, 6060195316, 62863155972.

Problem 16: $T_{113}(n,2n-3)$ for $3\leq n\leq 14$: 3, 18, 142, 1266, 12030,
118650, 1198230, 12296202, 127633590, 1336133730, 14079114270, 149124688482.

Problem 17: $T_{113}(n,2n-4;3)$ for $3\leq n\leq 14$:

$\begin{array}[]{l}3,102,10260,3267540,3272495580,10170919805580,\\\
97112573496153540,2829427113881208115260,\\\ 250440846963119234063024220,\\\
67143197168392738521628168122420,\\\
54411613647618445838464808052508179060,\\\
133085560953741266360779763637716021767185540.\end{array}$

Problem 18: $T_{113}(n,2n-3;3)$ for $3\leq n\leq 14$:

$\begin{array}[]{l}9,270,27110,8798490,8980383330,28344705113430,\\\
273927748387623390,8057418594145673168610,\\\ 718650987298253553656580570,\\\
193874673319110717570773876192670,\\\
157927323459469084048485672225266775510,\\\
387962431958247267773527802272080627127318890.\end{array}$

Acknowledgments: I am grateful to the organizers of OPAC 2022 for inviting me
to give this presentation. I also think Colin Defant, Rupert Li, and Ben Young
for useful conversations.

References

[Cohn] Henry Cohn, 2-adic behavior of numbers of domino tilings, Electronic
Journal of Combinatorics 6 (1999), #R14.

[CoLa] John Conway and Jeffrey Lagarias, Tiling with polyominoes and
combinatorial group theory, J. Combin. Theory (Ser. A) 53 (1990), no. 2,
183–208.

[DLPY] Colin Defant, Rupert Li, James Propp, and Benjamin Young, Tilings of
benzels via the abacus bijection, submitted to Combinatorial Theory;
https://arxiv.org/abs/2209.05717.

[EKLP] Noam Elkies, Greg Kuperberg, Michael Larsen, and James Propp,
Alternating sign matrices and domino tilings, J. Algebraic Combin. 1 (1992),
no. 2, 111–132; J. Algebraic Combin. 1 (1992), no. 3, 219–234.

[Kast] Pieter Kasteleyn, The statistics of dimers on a lattice, I: The number
of dimer arrangements on a quadratic lattice, Physica 27 (1961), 1209–1225.

[KiPr] Jesse Kim and James Propp, A pentagonal number theorem for tribone
tilings, in preparation. http://arxiv.org/abs/2206.04223

[Pak] Igor Pak, Ribbon tile invariants, Trans. Amer. Math. Soc. 352 (2000),
no. 12, 5525–5561.

[Pro] James Propp, Some 2-adic conjectures concerning polyomino tilings of
Aztec diamonds, in preparation.

[Shef] Scott Sheffield, Ribbon tilings and multidimensional height functions,
Trans. Amer. Math. Soc. 354 (2002), no. 12, 4789–4813.

[TeFi] Harold Neville Temperley and Michael Fisher, Dimer problem in
statistical mechanics – an exact result, Phil. Mag. J. Theor. Exp. Appl. Phys.
6 (1961) no. 68, 1061–1063.

[Thur] William Thurston, Conway’s tiling groups, Amer. Math. Monthly 97
(1990), no. 8, 757–773.

[VeNi] Alain Verberkmoes and Bernard Nienhuis, Bethe Ansatz solution of
triangular trimers on the triangular lattice, Phys. Rev. E 63 (2001), 066122.


Design of a Teleoperated Robotic Bronchoscopy System for Peripheral Pulmonary Lesion Biopsy

This work was supported by National Natural Science Foundation of China (U21A20480, 61950410618). Corresponding authors: Lei Wang and Olatunji Mumini Omisore. (Email<EMAIL_ADDRESS>and omisore@siat.ac.cn).

^1 Research Centre for Medical Robotics and Minimally Invasive Surgical Devices, Shenzhen Institutes of Advanced Technology, Chinese Academy of Sciences, Shenzhen, 518055, China.

^2 Shenzhen College of Advanced Technology, University of Chinese Academy of Sciences, Beijing 100049, China.

Emails:(xy.chen7; xh.xiong1; j.jiang; xm.wang2; p.li1; wk.duan; wj.du; tolu; omisore<EMAIL_ADDRESS>
Xing-Yu Chen^1^0000-0003-1164-9537, Member, IEEE,
Xiaohui Xiong^1,2^0009-0003-1910-5101,
Jie Jiang^1^0000-0002-6062-542X,
Xuemiao Wang^1^0009-0006-3365-714X,

Peng Li^1^0009-0007-4166-3029,
Toluwanimi Oluwadara Akinyemi^1,2^0000-0002-5598-8971,
Wenke Duan^1^0000-0001-7509-7538,
Wenjing Du^1^0000-0002-0571-3398,

Olatunji Mumini Omisore^1,*^0000-0002-9740-5471, Senior Member, IEEE,
and Lei Wang^1,*^0000-0002-7033-9806, Senior Member, IEEE

Bronchoscopy with transbronchial biopsy is a minimally invasive and effective method for early lung cancer intervention. Robot assisted bronchoscopy offers improved precision, spatial flexibility, and reduced risk of cross-infection. This paper introduces a novel teleoperated robotic bronchoscopy system and a three-stage procedure derived for robot-assisted bronchoscopy. The robotic mechanism allows for translation, rotation, bending of a bronchoscope, and as well as the control of a novel variable stiffness catheter for tissue sampling. Rapid prototype of the robotic system has been fully developed and characterized with in-silico and in-vivo animal experiments in this study. We conducted the studies to evaluate the robot's design concept and feasibility of usage for transbronchial biopsy. The results demonstrate the potential of the proposed robotic bronchoscopy system in enhancing accuracy and safety during bronchoscopy procedures.

Robotic bronchoscopy, Robot assisted surgery, Teleoperation

§ INTRODUCTION

Lung cancer is the third most common cancer, and it has a significantly high morbidity and mortality rates worldwide. This medical condition has been consistently related to an annual death toll of 1.9 million people in the last five years [1]. This type of cancer usually start with the development of peripulmonary nodules in the lungs. Thus, early detection and treatment of pulmonary nodules are sought for effective clinical intervention. This is leading to complete cures for many early-stage lung cancer patients thus reducing the death rates of lung cancer [2]. The conventional methods of carrying out lung biopsy involve the use of percutaneous or bronchoscopic needles [3]. Typically, percutaneous needle biopsy involves inserting a needle into the lung lesion through the chest skin to obtain biopsy tissue. Clinical practice and evaluation shows that percutaneous needle biopsy carries a high risk of complications such as pneumothorax and significant bleeding [4]. Consequently, transbronchial biopsy an alternative as it is done through minimal invasion and possess relatively lower risks [5].

Robotic technology with improved precision, spatial flexibility, and dexterity has the potential to enhance minimal invasive surgeries [6]. Robot-assisted minimal invasive surgeries (RAMIS) enable faster, safer, and more convenient navigation of surgical tools for intraluminal, endoluminal and transluminal interventions without the need for multiple or wide incisions [7]. The absence of large incisions during RAMIS offers numerous advantages such as improved cosmology due to small incision or no visible scarring, reduced postoperative pain, and avoidance of general anesthesia for patients [8]. Similarly, doctors are able to perform different interventions without been exposed to the operational risks [9]. Recently, there have been notable advancements in the development of robot-assisted bronchoscopy systems. A prominent example is the Monarch™ platform (Auris Health, Redwood City, USA). The system incorporates inner bronchoscope and outer sheath equipped with electromagnetic (EM) for teleoperated navigation guidance. Ion™ Endoluminal System (Intuitive Surgical, Sunnyvale, CA, USA) is another iconic bronchoscopy platform used for the intervention of peripulmonary nodules. Rather than using EM, the system employs shape-sensing technology for tool navigation. Typically, shape-sensing Bragg grating fiber and video scope are utilized for navigation guidance during interventions. A common drawback is the lack of direct visualization system during tissue sampling with these systems [10]. The recently FDA approved Galaxy™ system developed by Noah Medical (San Carlos, USA) offers real-time navigation and lesion updates through tomosynthesis during lung interventions. It is worthnoting that the latter is augmented with a readily available C-arm for fluoroscopy; thus, exposing surgeons to X-ray radiation which are capable of causing surgeons head and neck cancer [11][12].

In addition to commercially available robotic bronchoscopy systems, there have been notable academic efforts in the development of robots for transbronchial lung biopsy. Swaney et al. proposed a robotic system utilizing concentric tube and a steerable needle with magnetic tracking, enabling precise movement through the bronchial wall [13]. Similarly, Amack et al. designed a concentric tubular robot with a compact, modular, and multi-stage mechanism to deploy a steerable needle through a standard flexible bronchoscope [14]. Duan et al. developed a bronchoscope robot with a small end-effector composed of a nickel-titanium tube, achieving three degrees of freedom motion [15]. These research efforts have predominantly focused on innovating mechanical structures with focus on novel designs for continuum robots or flexible robots. The transbronchial robots adopted unique design typologies, and offer range of functionalities that contribute to the advancement RAMIS in lung cancer interventions. Taken an alternative path, we have designed a robotic system for intraluminal bronschoscopy. This paper is aimed to present the design details of the robotic system and characterization of its functionalities. Typically, the platform integrates a new robotics mechanism equipped with various biopsy tools which can be used to coordinate a three-stage bronchoscopy routine. The procedure follows initial insertion of a bronchoscope robot, dynamic adjustment of variable stiffness catheters (VS-Catheters), and tissue sampling. To ensure accurate positioning, an endoscopic video and EM tracking fused navigation system is employed. The feasibility and practicality of the proposed robotic system are assessed through simulations and in-vivo experiments.

§ MATERIAL AND METHODS

The system consists of a teleoperated surgical robot designed for trans-respiratory diagnosis, along with a corresponding master-slave control system.

§.§ System Overview

Fig. <ref>robot illustrates the proposed bronchoscopy robotic system. Our architecture follows mounting the actual tool manipulator on a passive robotic arm to ensure stability during teleoperation by surgeons. For a typical bronchoscopy intervention, the manipulator will be positioned adjacent to a patient with the EM tracking system located next to them. Thus, the robotic system can the simulate surgeons' realistic operating mode during the intervention. During the procedure, the surgeon holds a tablet console to control a flexible visual bronchoscope, inserts a flexible tube into the patient's mouth, and utilizes the robot for advancements, rotations, and adjustment of the bending angle of the front end of the flexible bronchoscope. The robot also enables control of the biopsy forceps for feeding and tissue sampling. Surgical tools such as biopsy forceps, biopsy needles, and cytologic brushes reach the target position through a 2.6 mm-diameter working channel.

Illustration of the bronchoscopy system mounted on a robotic arm, a trachea guide apparatus is inserted into patient's mouth to stabilize interventional direction.

§.§ Bronchoscope Manipulator

The robotic system incorporates various components as shown in Fig. <ref>structure, including a flexible bronchoscope, bronchial biopsy instruments, VS-Catheters, and several tablets functioning as master consoles (Microsoft Surface Pro 8). The instructions from surgeons are wirelessly transmitted to robot controller through TCP/IP protocol. Subsequently, the robot responds to surgeons' commnads by navigating the flexible bronchoscope along a given trajectory. In addition, the robot utilizes multimodal navigation, combining EM tracking and visual navigation, to accurately locate the position of the bronchoscope in real time. Employing a multi-operator strategy, the robot is controlled through scheduling arrangement and weight distribution, which enables mentor surgeons and trainee surgeons observe the same surgical site and collaboratively control the surgical instruments simulatanously.

Based on analysis of the flexible bronchoscopy tools, the mechanism is designed to replicate the conventional way of steering bronchoscope and biopsy forceps during manual intervention. The design of the embedded system is based on our advancement in endovascular interventional surgical robot[16]. Following the structure of bronchoscopy robot (in Fig. <ref>structure), we installed a  Nvidia® Jetson AGX Orin$^\text{TM}$ Developer Kit, which is programmed for controlling the electric slider (Panasonic®, Osaka, Japan), rotary motor (Orientalmotor®, Tokyo, JP), motor drivers, gear sets, and biopsy forceps. Unlike existing robotic bronchoscopy systems, our newly proposed system integrates a commercial bronchoscope in operating room to improve cost efficiency and reduce usage complexity.

Structure of the bronchoscope robot.

Robotic Bronchoscopy System. (A) Robot and bronchus phantom; (B) Biopsy forceps manipulator; (C) Bronchoscopic video. (D) EM-Sensor based navigation system; (E) Embedded control system, electrical devices and motors; (F) Biopsy forceps and VS-Catheters delivery device.

The bronchoscope (UEWorld™, Xianju, China) used in our work can be replaced easily by other flexible endoscopes. This videoscope has an external diameter of 5.2 mm and working channel of 2.6 mm, with the ability of $160^{\circ}$ upward and $130^{\circ}$ downward bending angle. Commercial biopsy forceps can be installed in the forceps container. Several motors are mounted with friction wheel to deliver biopsy forceps and VS-Catheters, as shown in Fig. <ref>System.

§.§ Multimodal Navigation System

We have installed 6-DoF EM sensors to enable real-time navigation, tracking, and three-dimensional localization of the surgical instruments. For this purpose, an EM tracking system (NDI Aurora, Waterloo, Canada) with a field generator that produces EM field with known geometry, is integrated with the robotic system. This provides information about the position and orientation (roll, pitch, and yaw) of the EM sensor. To integrate endoscopic video and EM tracking information, a multimodal navigation system is employed, utilizing the open-source software CustusX[17]. The software includes a toolbox of navigation features, image-processing algorithms, and connections to external hardware for image-guided therapy. By combining images, tracked surgical instruments, and computer display, a comprehensive navigation system is created, enabling real-time identification of the direction and position of the tip of the bronchoscope.

§.§ Variable Stiffness Catheter

A catheter with variable stiffness is designed and utilized to facilitate the extension of surgical instruments through the working channel of an endoscope, thereby reducing the potential risk of unintentional tissue penetration [18]. The catheter design was aimed to maintain optimal flexibility for seamless traversal of tortuous intra-luminal pathways in the human body, while also ensuring sufficient rigidity to provide adequate support during tissue biopsy. Specifically, we developed novel VS-Catheter which is composed of low melting point alloy (LMPA) to enhance the catheter's flexibility in the context of RAMIS and expand the accessible area for bronchoscopic biopsy forceps. Unlike the bronchoscope, the VS-Catheter can be inserted into narrower bronchi and offers more flexible control with dynamic stiffness. The VS-Catheter consists of a hollow flexible inner tube and an outer tube incorporating an interlayer infused with LMPA (Field's metal) at a temperature of 47°C. Additionally, a heat-generating resistance wire is helically wound around the flexible inner tube. This wire serves the purpose of melting the Field's metal, thereby providing variable stiffness functionality to the catheter. The resistance wire and the Field's metal together constitute a stiffness measurement circuit, and a controller-based methodology is employed to achieve continuous adjustability of the catheter's stiffness.

Structure of proposed VS-Catheter, consist of hollow flexible tube fulfilled with LMPA and heating wire.

The structural design of the catheter exhibits simplicity, ease of manufacture, and cost efficiency. It utilizes Field's metal phase change technology to achieve controllable stiffness. Importantly, the cooling process of the catheter occurs naturally at the physiological temperature of the human body, eliminating the need for external stimuli and ensuring safety and reliability. The catheter incorporates two circuits: the heating circuit and the measurement circuit, enabling real-time adjustment of the catheter's stiffness to accommodate the intricate anatomical environment, thereby enhancing surgical safety.

§ NOVEL ROBOTIC BRONCHOSCOPY PROCEDURES

The complete procedures of robot-assisted bronchoscopy involve several steps.  These are acquisition of imaging data, segmentation, registration, and 3D construction of the bronchus, as shown in Fig. <ref>three_stage. The process begins with acquiring imaging data, typically through CT or MRI scans, to create a 3D map of the patient's airways. This map is integrated into the system to provide a visual representation of the surgical workspace. After the registration is complete, the physician utilizes the 3D map to plan bronchoscopy procedure. After setting up the robotic manipulator on the passive arm and calibrating it, the physician can remotely control the robotic system with the multimodal navigation system. The surgeon identifies location of suspicious areas of tumors or lesions, and determines the optimal route in bronchus to reach them.  Table <ref>table presents essential mechanical parameters of the bronchoscopic tools.

The application of the VS-Catheter involves a three-stage bronchoscopy surgical procedure, as shown in Fig. <ref>three_tools. In the first stage, the clinician maneuvers the robot to navigate the bronchoscope to a target site. The navigation process involves motions like translation, rotation, and tip bending. The VS-catheter is heated (under safe temperature 53°C) to decrease its stiffness. For stage two, the softened VS-catheter is inserted via the bronchoscope's working channel. Its dynamic stiffness can be adjusted based on factors like heartbeat and respiration. Compared to the bronchoscope, the VS-catheter can be inserted into thinner bronchi and provides more flexible control. Once the softened catheter reaches the precise location of the targeted lesion, the power supply to the heating resistance wire is discontinued, allowing the low-melting-point alloy to cool naturally and restore the catheter's stiffness. Lastly, tissue sampling is performed using the biopsy forceps manipulators in the third stage. The physician can thereby examine patient's airways, search for abnormalities or suspicious areas, and perform tissue biopsy for further testing. Surgeons have the capability to control these three-stage processes using tablets and tele-operate the robot. This emphasizes the importance of robotic surgery, as it enables surgeons to manipulate multiple medical tools without the need for shift changes, ensuring stability within the trachea.

Proposed three-stage bronchoscopy surgical procedures, with initial insertion, dynamic adjustment, and tissue sampling.

Three-stage bronchoscopy surgical procedure composed of robotic bronchoscope, VS-Catheter, and tissue sampling by biopsy forceps.

Essential Mechanical Parameters.

cell22 = Silver,
cell32 = Silver,
cell42 = Silver,
cell52 = Silver,
cell62 = Silver,

Idx.     Tool              Description                           Value

1        Bronchoscope      Outside Diameter                      5.2 mm

2        Bronchoscope      Inside Diameter (Working Channel)     2.6 mm

3        VS Catheter       Outside Diameter                      2.4 mm

4        VS Catheter       Inside Diameter                       1.2 mm

5       Biopsy forcep     Diameter                              1.0 mm

§ EVALUATION AND EXPERIMENT

We conducted in-silico and in-vivo experiments to demosntrate the usability of the  proposed robotic system for bronchoscopy procedures. The robot's model was imported from Solidworks into Adams View 2020 to analyze its mechanical transmission via dynamic simulation. The results in Fig. <ref>simulation(A) depict the change in velocity and acceleration over time during axial displacement of the bronchoscope. The velocity change follows a sinusoidal function, initially accelerating and then decelerating. The peak velocity reaches 30 $mm/s$ and the acceleration fluctuates within the range of 124.7 $mm/s^2$. This decreasing-then-increasing pattern allows the linear sliding table to smoothly reach the desired target position without being constrained by driving speed. Fig. <ref>simulation(B) presents discrete diagrams illustrating the speed changes of the worm gear under different driving speeds. It is evident that radial rotation is more stable at low speeds, while speed fluctuations become more pronounced at high speeds. This observation aligns with the actual operation of the worm during slow biopsy surgery. The driving speed (red circle) is maintained at approximately 1000 $d/s$. Fig. <ref>simulation(C) and (D) simulate the workspace and distribution probability of the endeffector using Cosserat theory in Matlab, respectively. These simulations provide insights into the range and likelihood of end-effector positions during the surgical procedure. Proper cooperation with the mechanical arm ensures that, in theory, the end effector can access all positions within the bronchi.

Similarly, in-vivo animal experiment was carried out in a swine animal with a weight of 30 kg. The study was approved by Institutional
Review Board and Ethics Committee of Shenzhen Institutes of Advanced Technology (AAS 201205P).
As show in Figure <ref>animal, the robotic system place next the animal as described in <ref>systemdescription. The system was controlled by two operators using tablets with different priorities, one with full authority, another only with biopsy forceps control authority. Two EM sensors were attached to the swine's fore breast and the tip of the bronchoscope, respectively. We successfully performed a biopsy procedure in which small tissue was clamped and removed from the tertiary bronchus of the swine. The stiffness of the catheter was adjusted by energizing the resistance wire, providing adaptability based on the specific requirements of the procedure. The usability and effectiveness of the designed bronchoscopy surgical robot were demonstrated.
When taking a biopsy sample during the experiment, the presence of the VS-Catheter makes the biopsy process more stable, and the implementation of the VS-Catheter enabled more flexible control of the biopsy forceps within the bronchus.

Simulation results. (A) Translation simulation of endeffector; (B) Rotation simulation in different angular velocities; (C) Reachable workspace of endeffector; (D) Distribution probability of endeffector.

Proposed bronchoscopy system. (A) In-vivo experiment stage; (B) Intra-body navigation view of the bronchoscopy tools in swine's trachea.

§ CONCLUSION

This paper introduces a novel teleoperated robotic bronchoscopy system and three-stage bronchoscopy procedure with VS-Catheters. The feasibility of the proposed robotic system is explored through kinematic simulations and analysis of the reachable workspace. The experimental study has validated the design concept and the feasibility of proposed robotic system. However, it is important to note that further validation is required through comprehensive preclinical studies and additional in-vivo tests involving surgeons. These subsequent evaluations will provide more insights into the practicality and efficacy of the system in real-life surgical scenarios.

[1]
H. Sung, J. Ferlay, R. L. Siegel, M. Laversanne, I. Soerjomataram, A. Jemal,
and F. Bray, “Global cancer statistics 2020: Globocan estimates of incidence
and mortality worldwide for 36 cancers in 185 countries,” CA: A Cancer
Journal for Clinicians, vol. 71, no. 3, pp. 209–249, 2021.

[2]
N. T. Tanner, L. Yarmus, A. Chen, J. W. Memoli, H. J. Mehta, N. J. Pastis,
H. Lee, M. A. Jantz, P. J. Nietert, and G. A. Silvestri, “Standard
bronchoscopy with fluoroscopy vs thin bronchoscopy and radial endobronchial
ultrasound for biopsy of pulmonary lesions: a multicenter, prospective,
randomized trial,” Chest, vol. 154, no. 5, pp. 1035–43, 2018.

[3]
A. Agrawal, D. K. Hogarth, and S. Murgu, “Robotic bronchoscopy for pulmonary
lesions: a review of existing technologies and clinical data,” Journal
of thoracic disease, vol. 12, no. 6, p. 3279, 2020.

[4]
J. Cicenia, S. K. Avasarala, and T. R. Gildea, “Navigational bronchoscopy: a
guide through history, current use, and developing technology,”
Journal of Thoracic Disease, vol. 12, no. 6, p. 3263, 2020.

[5]
I. Y. Wan, T. P. Toma, D. M. Geddes, G. Snell, T. Williams, F. Venuta, and
A. P. Yim, “Bronchoscopic lung volume reduction for end-stage emphysema:
report on the first 98 patients,” Chest, vol. 129, no. 3, pp.
518–526, 2006.

[6]
O. M. Omisore, S. Han, L. Ren, Y. Al-Handarish, T. Igbe, and L. Wang, “A
teleoperated snake-like robot for minimally invasive radiosurgery of
gastrointestinal tumors,” in IEEE ICARSC, 2018, pp. 123–9.

[7]
O. M. Omisore, S. Han, L. Ren, N. Zhang, K. Ivanov, A. Elazab, and L. Wang,
“Non-iterative geometric approach for inverse kinematics of redundant
lead-module in a radiosurgical snake-like robot,” BioMedical
Engineering OnLine, vol. 16, no. 1, pp. 1–25, 2017.

[8]
Y. Zhou, H. Ren, M. Q.-H. Meng, Z. TSZ HO TSE, and H. Yu, “Robotics in natural
orifice transluminal endoscopic surgery,” Journal of Mechanics in
Medicine and Biology, vol. 13, no. 02, p. 1350044, 2013.

[9]
A. Di Lallo, R. Murphy, A. Krieger, J. Zhu, R. H. Taylor, and H. Su, “Medical
robots for infectious diseases: Lessons and challenges from the covid-19
pandemic,” IEEE Robotics & Automation Magazine, vol. 28, no. 1, pp.
18–27, 2021.

[10]
A. Kumar, J. D. Caceres, S. Vaithilingam, G. Sandhu, and N. K. Meena, “Robotic
bronchoscopy for peripheral pulmonary lesion biopsy: Evidence-based review of
the two platforms,” Diagnostics, vol. 11, no. 8, p. 1479, 2021.

[11]
K. Bhadra, O. B. Rickman, A. K. Mahajan, and D. K. Hogarth,
““tool-in-lesion” accuracy of galaxy system—a robotic electromagnetic
navigation bronchoscopy with integrated tool-in-lesion-tomosynthesis
technology: The match study,” Journal of Bronchology & Interventional
Pulmonology, pp. 10–1097.

[12]
O. M. Omisore, S. P. Han, L. X. Ren, G. S. Wang, F. L. Ou, H. Li, and L. Wang,
“Towards characterization and adaptive compensation of backlash in a novel
robotic catheter system for cardiovascular interventions,” IEEE
transactions on biomedical circuits and systems, vol. 12, no. 4, pp.
824–838, 2018.

[13]
P. J. Swaney, A. W. Mahoney, B. I. Hartley, A. A. Remirez, E. Lamers, R. H.
Feins, R. Alterovitz, and R. J. Webster III, “Toward transoral peripheral
lung access: Combining continuum robots and steerable needles,”
Journal of medical robotics research, vol. 2, no. 01, 2017.

[14]
S. Amack, M. Rox, J. Mitchell, T. E. Ertop, M. Emerson, A. Kuntz, F. Maldonado,
J. Akulian, J. Gafford, R. Alterovitz et al., “Design and control of
a compact modular robot for transbronchial lung biopsy,” in Medical
Imaging 2019: Image-Guided Procedures, Robotic Interventions, and Modeling,
vol. 10951.1em plus 0.5em minus 0.4emSPIE, 2019, pp. 114–121.

[15]
X. Duan, D. Xie, R. Zhang, X. Li, J. Sun, C. Qian, X. Song, and C. Li, “A
novel robotic bronchoscope system for navigation and biopsy of pulmonary
lesions,” Cyborg and Bionic Systems, vol. 4, p. 0013, 2023.

[16]
X. Chen, Y. Chen, W. Duan, T. O. Akinyemi, G. Yi, J. Jiang, W. Du, and O. M.
Omisore, “Design and evaluation of a learning-based vascular interventional
surgery robot,” Fibers, vol. 10, no. 12, p. 106, 2022.

[17]
C. Askeland, O. V. Solberg, J. B. L. Bakeng, I. Reinertsen, G. A. Tangen, E. F.
Hofstad, D. H. Iversen, C. Våpenstad, T. Selbekk, T. Langø
et al., “Custusx: an open-source research platform for image-guided
therapy,” International journal of computer assisted radiology and
surgery, vol. 11, pp. 505–519, 2016.

[18]
C. Chautems, A. Tonazzini, Q. Boehler, S. H. Jeong, D. Floreano, and B. J.
Nelson, “Magnetic continuum device with variable stiffness for minimally
invasive surgery,” Advanced Intelligent Systems, vol. 2, no. 6, p.
1900086, 2020.