# Conductance oscillation in surface junctions of Weyl semimetals

Xi-Rong Chen  These authors contributed equally to this work National
Laboratory of Solid State Microstructures and department of Physics, Nanjing
University, Nanjing, 210093, China  Collaborative Innovation Center of
Advanced Microstructures, Nanjing University, Nanjing 210093, China  Guangze
Chen  These authors contributed equally to this work Department of Applied
Physics, Aalto University, 02150, Espoo, Finland  Yue Zheng  National
Laboratory of Solid State Microstructures and department of Physics, Nanjing
University, Nanjing, 210093, China  Collaborative Innovation Center of
Advanced Microstructures, Nanjing University, Nanjing 210093, China  Wei Chen
Corresponding author<EMAIL_ADDRESS>National Laboratory of Solid State
Microstructures and department of Physics, Nanjing University, Nanjing,
210093, China  Collaborative Innovation Center of Advanced Microstructures,
Nanjing University, Nanjing 210093, China  D. Y. Xing  National Laboratory of
Solid State Microstructures and department of Physics, Nanjing University,
Nanjing, 210093, China  Collaborative Innovation Center of Advanced
Microstructures, Nanjing University, Nanjing 210093, China

###### Abstract

Fermi arc surface states, the manifestation of the bulk-edge correspondence in
Weyl semimetals, have attracted much research interest. In contrast to the
conventional Fermi loop, the disconnected Fermi arcs provide an exotic 2D
system for exploration of novel physical effects on the surface of Weyl
semimetals. Here, we propose that visible conductance oscillation can be
achieved in the planar junctions fabricated on the surface of Weyl semimetal
with a pair of Fermi arcs. It is shown that Fabry-Pérot-type interference
inside the 2D junction can generate conductance oscillation with its
visibility strongly relying on the shape of the Fermi arcs and their
orientation relative to the strip electrodes, the latter clearly revealing the
anisotropy of the Fermi arcs. Moreover, we show that the visibility of the
oscillating pattern can be significantly enhanced by a magnetic field
perpendicular to the surface taking advantage of the bulk-surface connected
Weyl orbits. Our work offers an effective way for the identification of Fermi
arc surface states through transport measurement and predicts the surface of
Weyl semimetal as a novel platform for the implementation of 2D conductance
oscillation.

##  I introduction

Weyl fermion is a massless fermionic particle with definite chirality named
after Hermann Weyl Weyl (1929), which is proposed originally as a candidate
for fundamental particles. Though it plays an important role in quantum theory
and the standard model, the verification of Weyl fermion in high-energy
physics remains elusive Armitage  _et al._ (2018); Kajita (2016); McDonald
(2016). Recently, Weyl fermion has been observed unexpectedly in an
alternative form as quasi-particle excitations in a class of condensed matter
materials called Weyl semimetals (WSMs) Wan  _et al._ (2011), thereby
inspiring research activities on Weyl physics and opening a new avenue for
exploration of relativistic Weyl fermion in solid-state physics Murakami
(2007); Burkov and Balents (2011); Weng  _et al._ (2015); Huang  _et al._
(2015a); Lv  _et al._ (2015a); Xu  _et al._ (2015a, b, c, 2016); Deng  _et
al._ (2016); Yang  _et al._ (2015); Huang  _et al._ (2016); Tamai  _et al._
(2016); Jiang  _et al._ (2017); Belopolski  _et al._ (2016); Lv  _et al._
(2015b). In contrast to its high energy counterpart, the exotic properties of
Weyl fermion in solid-state physics are usually manifested as anomalous
transport and optical phenomena Zyuzin and Burkov (2012); Aji (2012); Son and
Spivak (2013); Chernodub  _et al._ (2014); Zhou  _et al._ (2013); Burkov
(2015); Ma and Pesin (2015); Zhong  _et al._ (2016); Spivak and Andreev
(2016); Hirschberger  _et al._ (2016); Huang  _et al._ (2015b); Shekhar  _et
al._ (2015); Du  _et al._ (2016); Wang  _et al._ (2016a); Zhang  _et al._
(2016).

One unique feature of the WSMs is the existence of Fermi arc (FA) surface
states at its boundaries Wan  _et al._ (2011), without any high-energy
counterpart. According to the no-go theorem Nielsen and Ninomiya (1981a, b),
the Weyl points in a WSM must appear in pairs with opposite chirality Nielsen
and Ninomiya (1983), with FA spanning between each pair in the surface
Brillouin zone Wan  _et al._ (2011). Such disconnected FAs are the fingerprint
of WSMs Huang  _et al._ (2015a); Lv  _et al._ (2015a); Xu  _et al._ (2015a, b,
c, 2016); Deng  _et al._ (2016); Yang  _et al._ (2015); Huang  _et al._
(2016); Tamai  _et al._ (2016); Jiang  _et al._ (2017); Belopolski  _et al._
(2016); Lv  _et al._ (2015b), which play a key role in the identification of
WSMs in experiment Lv  _et al._ (2015a); Xu  _et al._ (2015a, b, c, 2016);
Deng  _et al._ (2016); Yang  _et al._ (2015); Huang  _et al._ (2016); Tamai
_et al._ (2016); Jiang  _et al._ (2017); Belopolski  _et al._ (2016). Most
experiments on Weyl semimetals focus on the angle-resolved photoemission
spectroscopy, in which the existence of FAs has been confirmed. Recent
progress have also shown that the configurations of the FAs are sensitive to
the details of the sample boundary Morali  _et al._ (2019); Yang  _et al._
(2019); Ekahana  _et al._ (2020), thus opening the possibility for engineering
FAs and exploring their novel effects and potential applications through
surface device fabrication and transport measurements. In contrast to the
photoemission spectroscopy experiments, the surface transport measurement has
the advantage of extracting useful information of the spatially distribution
of the surface states Chen  _et al._ (2018a, 2020); Zheng  _et al._ (2020).

Figure 1: (Color online).(a) Schematic illustration of the planar normal metal
(N)-FA-normal metal (N) on the top surface of a WSM slab and scattering of
particles at the interface. The trajectories of electrons(solid circles) are
sketched as solid lines, where the colors of them denote that they belong to
different $k_{z}$ regions. (b) Two regions $\rm{I}$ and $\rm{II}$ for left
incident electrons are defined by the transverse momentum $k_{z}$. (c) The
corresponding band structures for a fixed $k_{z}$ of the two regions. The red
lines denote the FA top surface states and black arrows indicate the moving
directions.

In this work, we propose that novel 2D conductance oscillation stemming from
Fabry-Pérot-type interference can be realized in the planar normal metal-FA-
normal metal (NFAN) junctions on the surface of the WSM. The junctions consist
of two strip normal metal electrodes mediated by a pair of FA surface states
in between as shown in Figs. 1(a) and 1(b). Our main findings in this work
are: (i) Shorter and less curved FAs can lead to more visible conductance
oscillation stemming from a weaker dephasing effect between different
transverse channels. (ii) The oscillation pattern of the conductance strongly
relies on the relative orientation between the FAs and the strip electrodes
denoted by the azimuthal angle $\theta$ in Fig. 1(b). (iii) The visibility of
the conductance oscillation can be significantly enhanced by a magnetic field
perpendicular to the planar junctions due to the existence of the magnetic
Weyl orbit. Our work shows that FA surface states offer a novel platform to
observe 2D conductance oscillation in addition to the existing systems such as
graphene Young and Kim (2008); Rickhaus  _et al._ (2013); Grushina  _et al._
(2013); Oksanen  _et al._ (2014); Campos  _et al._ (2012); Varlet  _et al._
(2014) and the inverted InAs/GaSb double quantum well Karalic  _et al._
(2020). The orientation dependence and the field modulation of the conductance
provide a unique signature of the FAs, which can be used for identifying WSMs
through transport approach.

The rest of this paper is organized as follows: in Sec. II, we present
effective models for a time-reversal ($\mathcal{T}$)-symmetric WSM and its FA
surface states. We then show that a general oriented FA can be described by
applying a rotation transformation of the effective Hamiltonian. Based on the
effective models and using the Green’s function approach, we show analytically
the existence of oscillations in the conductance spectra of a NFAN junctions
on the WSM surface in Sec. III, and support the analytical results with
numerical simulations on the lattice model. In Sec. IV we show the dependence
of such oscillation on the relative orientation of the FAs to the normal
metals with numerical means. In Sec. V we show that the oscillation can be
enhanced by applying a magnetic field perpendicular to the WSM surface.
Finally, we give a brief summary in Sec. VI.

Figure 2: (Color online). Top rows illustrate the FAs with different curvature
and length, where the relevant parameters are (a) $k_{0}=0.6\,\rm nm^{-1}$,
$d=1.5\,\rm eV\,nm^{2}$ (b) $k_{0}=0.6\,\rm nm^{-1}$, $d=0.3\,\rm eV\,nm^{2}$
and (c) $k_{0}=0.4\,\rm nm^{-1}$, $d=1.5\,\rm eV\,nm^{2}$. (d)-(f) Middle rows
illustrate the corresponding analytical results of the transmission
coefficient $\widetilde{T}(\theta=0)$ as a function of $\varepsilon$ and
$k_{z}$. (g)-(i) Bottom rows exhibit the corresponding conductance $\sigma$
after integrates over $k_{z}$. The other parameters are set as $a=1\rm nm$,
$R_{1}=R_{2}=1$, $M_{1}=1.25\,\rm eV\,nm^{2}$ and $k_{1}=1.2\,\rm nm^{-1}$.

##  II $\mathcal{T}$-symmetric Weyl semimetal and FA surface states

We adopt the following effective two-band $k\cdot p$ model, which describes a
$\mathcal{T}$-symmetric Weyl semimetal with four Weyl points Chen  _et al._
(2020); Zheng  _et al._ (2020):

$H_{W}^{0}(\bm{k})=M_{1}(k^{2}_{1}-k^{2}_{x})\sigma_{x}+v_{y}k_{y}\sigma_{y}+M_{2}(k^{2}_{0}-k^{2}_{y}-k^{2}_{z})\sigma_{z},$
(1)

where $v_{y}$ is the velocity in the $\hat{y}$ direction, $M_{1,2}$ and
$k_{0,1}$ are model parameters, $\sigma_{x,y,z}$ are the Pauli matrices in the
pseudo-spin space. The valence and conduction bands cross linearly at four
Weyl points $\bm{k}_{W}=(\pm k_{1},0,\pm k_{0})$. The low-energy Hamiltonian
near the Weyl points are $h_{W}(\bm{k})=\pm
2M_{1}k_{1}k_{x}\sigma_{x}+v_{y}k_{y}\sigma_{y}\pm
2M_{2}k_{0}k_{z}\sigma_{z}.$ We are interested in the topologically-protected
FA surface states on the open surface in the $\hat{y}$ direction. They are
confined by $|k_{z}|<k_{0}$ and can be described by

$H_{\text{Arc}}^{0}(k_{x})=M_{1}(k_{x}^{2}-k_{1}^{2}),$ (2)

with two straight FAs defined by $k_{x}=\pm k_{1}$. Generically, FAs in real
materials are curved, we introduce a dispersion term
$\epsilon(k_{z})=d(k_{z}^{2}-k_{0}^{2})$ to capture that feature and the total
Hamiltonian of the surface states are

$H_{\text{Arc}}(\bm{k})=H_{\text{Arc}}^{0}(k_{x})+\epsilon(k_{z}),$ (3)

with the in-plane wave vector $\bm{k}=(k_{x},k_{z})$.

One important feature of the FAs is its strong anisotropy. In the planar
junctions, the relative orientation between the FAs and the normal of the
strip electrodes denoted by the angle $\theta$ [Fig. 1(b)] strongly affects
the physical results. In the long wave-length limit, we can apply a rotational
transformation to the effective Hamiltonian Eq. (1) of WSM to describe such an
effect while fixing the direction of the electrodes at the same time. A
rotation about the $\hat{y}$-axis by an angle $\theta$ is described by

$H_{W}(\bm{k},\theta)=H_{W}^{0}(U_{y}^{-1}\bm{k})$ (4)

with the rotation operator Chen  _et al._ (2013)

$U_{y}(\theta)=\left({\begin{matrix}\cos\theta&0&\sin\theta\\\ 0&1&0\\\
-\sin\theta&0&\cos\theta\end{matrix}}\right).$ (5)

The locations of Weyl points determined by $H_{W}(\bm{k},\theta)=0$ are
transferred to
$U_{y}(\theta)\bm{k}_{W}=\pm(k_{1}\cos\theta+k_{0}\sin\theta,0,-k_{1}\sin\theta+k_{0}\cos\theta)$
and the FAs terminated at these points rotate accordingly [cf. Fig. 1(b)]. In
the next section, we show the conductance oscillation in the planar junctions
with the dispersion (3), and in Sec. IV we show the dependence of such
oscillation on the orientation of the FAs based on the discrete version of
Hamiltonian (4).

##  III Conductance oscillation in NFAN junctions

The WSM surface with FA states is a novel 2D system, which differs from other
systems with closed Fermi loops. The disconnected nature of FA may lead to the
absence of back-scattering channels in surface transport Zheng  _et al._
(2020). In particular, consider the NFAN junctions as shown in Fig. 1(a) with
the FA having an azimuthal angle $\theta$ relative to the normal metal
electrodes [Fig.1(b)]. In region I of the surface Brillouin zone, there exists
two counter-propagating channels at the Fermi surface [Fig. 1(c)], thus
enabling back-scattering; In contrast, in region II, there exists a single
chiral channel [Fig. 1(d)], and back-scattering is prohibited. Interestingly,
the ratio between region I and region II depends solely on the relative
orientation $\theta$. We show first the existence of conductance oscillation
with $\theta=0$ in this section, and investigate its $\theta$ dependence in
the next section.

###  III.1 Analytical calculation

We investigate the ballistic transport in the NFAN junctions using the Green’s
function method. We consider the case $\theta=0$ first, where all conducting
channels are of type I in the surface Brillouin zone [cf. Fig. 1]. The surface
Hamiltonian is captured by $H_{\text{Arc}}(\bm{k})$ in Eq. (3). The tunneling
Hamiltonian

$H_{T}=\sum_{p,\alpha=1,2}T_{\alpha}d_{p,\alpha}^{\dagger}\psi(x_{\alpha})+H.c.,$
(6)

is adopted to describe the coupling between the FA surface states and the
normal electrods where $T_{\alpha}$ is the tunneling strength between the
surface states and the $\alpha$-electrode [cf. Fig. 1(a)], $d_{p,\alpha}$ is
the Fermi operator in the $\alpha$-terminal with momentum $p$, and
$\psi(x_{\alpha})$ is the field operator of the surface states at each
terminal located at $x_{\alpha}$.

For the planar junctions with good quality of the strip electrodes the
transverse momentum $k_{z}$ is approximately conserved during scattering. The
differential conductance (without spin degeneracy) per unit length of the
strip electrodes is the summation over transmissions in all $k_{z}$ channels
as

$\sigma(\varepsilon)=\frac{e^{2}}{h}\int_{-k_{0}}^{k_{0}}\widetilde{T}(\varepsilon,k_{z})dk_{z},$
(7)

with $\varepsilon$ the electron energy. The range of integration is limited by
the spreading of FAs in the $k_{z}$ direction. The $k_{z}$-dependent
transmission function $\widetilde{T}(\varepsilon,k_{z})$ can be calculated by
the non-equilibrium Green’s function method through Datta (1997)

$\displaystyle\widetilde{T}(\varepsilon,k_{z})={\rm
Tr}[\Gamma_{1}G^{R}\Gamma_{2}G^{A}],$ (8)

where $\Gamma_{1,2}$ are linewidth functions of the leads and $G^{R,A}$ are
the full retarded/advanced Green’s function. For a given energy $\varepsilon$
and transverse momentum $k_{z}$, there are two counter-propagating channels
with momenta $\pm k_{x}^{0}$ and
$k_{x}^{0}(\varepsilon,k_{z})=\sqrt{k_{1}^{2}+\frac{\varepsilon-d(k_{z}^{2}-k_{0}^{2})}{M_{1}}}$.
The bare Green’s functions can be obtained as

$\displaystyle{g}_{\varepsilon}^{R}(x^{\prime},x)$
$\displaystyle=[{g}_{\varepsilon,k_{z}}^{A}(x,x^{\prime})]^{*}={g}_{\varepsilon,k_{z}}^{R}(x,x^{\prime})$
(9) $\displaystyle=-\pi i\rho_{S}(\varepsilon,k_{z})e^{ik_{0}(x^{\prime}-x)},$

with $\rho_{S}=\frac{1}{4\pi M_{1}k_{x}^{0}}$. The full Green’s function and
the linewidth function can be calculated in the standard way by taking into
account the tunneling term $H_{T}$, which gives

$\begin{split}{G}_{\varepsilon}^{R}(x_{2},x_{1})&=\frac{{g}_{\varepsilon}^{R}(x_{2},x_{1})}{(1+R_{1})(1+R_{2})-R_{1}R_{2}f_{\varepsilon}(x_{2},x_{1})},\\\
\Gamma_{\alpha}(x,x^{\prime},\varepsilon)&=2\pi\rho_{\alpha}(\varepsilon)|T_{\alpha}|^{2}\delta(x-x_{\alpha})\delta(x^{\prime}-x_{\alpha}).\end{split}$
(10)

where $f_{\varepsilon}(x_{2},x_{1})=e^{2ik_{0}(x_{2}-x_{1})}$,
$R_{\alpha}(\varepsilon)=\pi^{2}\rho_{S}(\varepsilon)\rho_{\alpha}(\varepsilon)|T_{\alpha}|^{2}$
and $\rho_{\alpha}$ is the density of states of the leads. We have assumed
that $T_{\alpha}$ and $\rho_{\alpha}$ are $k_{z}$-independent such that
$\Gamma_{\alpha}$ has no $k_{z}$ dependence. We have also neglected the
$k_{z}$ dependence of $\rho_{S}$ that does not qualitatively change the
result. The transmission coefficient in Eq. (8) reduces to

$\displaystyle\widetilde{T}(\varepsilon,k_{z})$
$\displaystyle=\frac{4R_{1}R_{2}}{|(1+R_{1})(1+R_{2})-R_{1}R_{2}f_{\varepsilon}(x_{2},x_{1})|^{2}}.$
(11)

The Fabry-Pérot-type interference is indicated by the coherence factor
$f_{\varepsilon}(x_{2},x_{1})$ in the transmission function, which induces the
oscillation of $\widetilde{T}$ with varying $\varepsilon$. It also exhibits a
$k_{z}$ dependence, meaning that different transverse channels can have a
relative phase shift; see Fig. 2. From the expression of the conductance (7),
one can infer that a strong dephasing between the $k_{z}$ channels will
suppress the overall oscillation of the conductance by phase averaging. This
is the main reason why the Fabry-Pérot oscillation of the conductance in a 2D
metal is hard to implement Karalic  _et al._ (2020). In contrast to a closed
Fermi surface, the terminated FAs can effectively reduce the dephasing effect,
so that the FA surface states provide a promising 2D platform to implement
conductance oscillation. From the physical picture above, we can infer that
FAs with smaller curvature and shorter length result in more visible
oscillation, that is verified in Fig. 2.

###  III.2 Numerical simulation

Figure 3: (Color online). Top rows illustrate the FA spectra with different
curvature and length, where the relevant parameters are (a) $k_{0}=0.6\,\rm
nm^{-1}$, $V=1.0\,\rm eV$ (b) $k_{0}=0.6\,\rm nm^{-1}$, $V=0.2\,\rm eV$ and
(c) $k_{0}=0.4\,\rm nm^{-1}$, $V=1.0\,\rm eV$. (d)-(f) Middle rows illustrate
the corresponding numerical results of the transmission coefficient $T$ as a
function of $\varepsilon$ and $k_{z}$. (g)-(i) Bottom rows exhibit the
corresponding conductance $\sigma$ after integrates over $k_{z}$. The other
parameters are $a=1\,\rm nm$, $U_{1}=U_{2}=1.0\,\rm eV$,
$M_{1}=M_{2}=1.25\,\rm eV\,nm^{2}$, $v_{y}=0.66\,\rm eV\,nm$, $k_{1}=1.2\,\rm
nm^{-1}$, $C=0.5\,\rm eV\,nm^{2}$, $\mu_{N}=1.0\,\rm eV$, and $t_{N}=0.5\,\rm
eV\,nm^{2}$.

Next, we perform numerical simulation of the conductance oscillation on the
lattice model. Assuming that the size of both strip electrodes in the
$\hat{z}$-direction is much larger than the Fermi wavelength and their
boundaries are smooth enough, then the transverse momentum $k_{z}$ is
approximately conserved during scattering and can be regarded as a parameter.
In this way, the numerical calculation is reduced to a set of 2D slices
labeled by $k_{z}$. For $|k_{z}|<k_{0}$, a pair of edge states emerge under
the open boundary condition [Fig. 1(c)]. By the substitutions
$k_{i=x,y,z}\rightarrow\frac{1}{a}\sin k_{i}a$ and
$k_{i}^{2}\rightarrow\frac{2}{a^{2}}(1-\cos k_{i}a)$ while keeping $k_{z}$ as
a parameter, we obtain the lattice version of the Hamiltonian (1) as

$\displaystyle\mathcal{H}_{W}(k_{z})$ $\displaystyle=$
$\displaystyle\sum_{i}c_{i}^{\dagger}H_{ii}c_{i}+\sum_{i}(c_{i}^{\dagger}H_{i,i+a_{x}}c_{i+a_{x}}+H.c.)$
(12) $\displaystyle+$
$\displaystyle\sum_{i}(c_{i}^{\dagger}H_{i,i+a_{y}}c_{i+a_{y}}+H.c.),$

where $c_{i}=(c_{i,\uparrow},c_{i,\downarrow})$ is the Fermi operator on site
$i=(i_{x},i_{y})$ with two pseudo-spin components, $a_{x}=(a,0)$ and
$a_{y}=(0,a)$ are the unit vectors along the $\hat{x}$ and $\hat{y}$
direction, respectively, with $a$ the lattice constant. $H_{ii}$ and
$H_{i,i+a_{x}(a_{y})}$ are $2\times 2$ block matrices and take the explicit
forms as

Figure 4: (Color online).(a)-(c)Upper panel: FA spectra for different
azimuthal angles $\theta$. (d)-(f)Middle panel: Corresponding transmission
probability as a function of $\varepsilon$ and $k_{z}$. (g)-(i)Lower panel:
Corresponding differential conductance after summing over all the transverse
channels $k_{z}$. The other parameters are the same as those in Fig.3(g).

$\begin{split}H&{}_{ii}=M_{1}(k_{1}^{2}-\frac{2}{a^{2}})\sigma_{x}+M_{2}(k_{0}^{2}-\frac{4}{a^{2}}+\frac{2}{a^{2}}\cos
k_{z}a)\sigma_{z},\\\ H&{}_{i,i+a_{x}}=\frac{M_{1}}{a^{2}}\sigma_{x},\quad
H_{i,i+a_{y}}=\frac{v_{y}i}{2a}\sigma_{y}+\frac{M_{2}}{a^{2}}\sigma_{z}.\end{split}$
(13)

The configuration of FAs on the top surface can be revealed by the spectra
function
$\mathcal{A}(\varepsilon)=-\frac{1}{\pi}\text{Im}g_{W}^{R}(\varepsilon)$ in
the top layer at $\varepsilon=0$, with $g_{W}^{R}(\varepsilon,k_{x},k_{z})$
the retarded Green’s function calculated by the lattice model of the Weyl
semimetal under open boundary condition in the $\hat{y}$-direction; see Fig.
3(a). To simulate the FAs in real materials Ekahana  _et al._ (2020);
Koepernik  _et al._ (2016); Belopolski  _et al._ (2017); Haubold  _et al._
(2017), we have introduced an on-site potential $V$ on the top layer of the
WSM lattice to introduce surface dispersion that yields curved FAs Chen  _et
al._ (2020); Zheng  _et al._ (2020).

The strip electrodes can be described by an effective Hamiltonian
$H_{N}(\bm{k})=(C\bm{k}^{2}-\mu_{N})\sigma_{0}$, with $C$ the parameter
related to the effective mass, $\mu_{N}$ the chemical potential, and
$\sigma_{0}$ the identity matrix. The lattice model for the electrodes can be
obtained in a similar way as

$\mathcal{H}_{N}(k_{z})=\sum_{j}d_{j}^{\dagger}\lambda_{j}d_{j}-\frac{C}{a^{2}}\sum_{j}(d_{j}^{\dagger}d_{j+a_{x}}+d_{j}^{\dagger}d_{j+a_{y}}+H.c.),$
(14)

where $d_{j}=(d_{j,\uparrow},d_{j,\downarrow})$ is the Fermi operator, and
$\lambda_{j}=2C(3-\cos k_{z}a)/a^{2}-\mu_{N}$.

The whole system for a given $k_{z}$ is described by $\mathcal{H}_{W}(k_{z})$
and $\mathcal{H}_{N}(k_{z})$ and the coupling between them which is captured
by the tunneling between the outmost lattice layers with a strength $t_{N}$.
The thickness of the WSM and the electrodes in the $\hat{y}$-direction is
$100\,\rm nm$ and $40\,\rm nm$, respectively. The width of the hopping area in
the $\hat{x}$-direction is $W=30\,\rm nm$, and the separation between two
electrodes is $L=180\,\rm nm$ [cf. Fig. 1(a)]. Two on-site potentials $U_{1}$
and $U_{2}$ are introduced at the boundary of the N electrodes to simulate the
interface barrier or the momentum mismatch in the heterostructure. Both the
WSM and electrodes connect to the leads extended to infinity in the
$\pm\hat{x}$ directions. The transmission $T(k_{z},\varepsilon)$ between two
electrodes is calculated using the KWANT program Groth  _et al._ (2014). The
overall conductance by summing up all the transverse channels can be obtained
as

$\sigma(\varepsilon)=\frac{e^{2}}{h}\int_{-k_{0}}^{k_{0}}T(k_{z},\varepsilon)dk_{z}.$
(15)

In the case of $\theta=0$, the FAs with different curvature and length are
shown in Figs. 3(a)-3(c). The corresponding results of the transmission
probability $T(k_{z},\varepsilon)$ and the differential conductance
$\sigma(\varepsilon)$ are plotted in Figs. 3(d)-3(f) and Figs. 3(g)-3(i),
respectively. One can see from Fig. 3 that less curved and shorter FAs result
in more visible conductance oscillation, in which the dephasing effect between
transverse channels becomes weaker as revealed by the length and curvature of
the bright stripes in the transmission pattern in Figs. 3(d)-3(f). These
results are in coincidence with the analytical calculations in Fig.2.

Figure 5: (Color online).(a) FA spectrum for azimuthal angle $\theta=0$, and
electrons slide along the FA driven by the Lorentz force. (b) Trajectories of
electrons in real space corresponding to the left panel. (c) Resolution of the
conductance as a function of the magnetic field, where $B_{C}$ is the
saturated magnetic field. The transmission probability as a function of
$\varepsilon$ and $k_{z}$ with (d) $B=0$ (e) $B=0.4B_{C}$ (f) $B=0.8B_{C}$.
(g)-(i)The corresponding conductance after summing over all the transverse
channels $k_{z}$ for different magnetic fields in the $\hat{y}$ direction. The
other parameters are the same for those in Fig.3(g).

##  IV Orientation dependent conductance spectra

In the above section, we have seen that the shape of the FAs strongly affect
the oscillation pattern of the conductance. In addition, FAs can also have
diverse orientations relative to the normal of the strip electrodes with
$\theta\neq 0$. Experimentally, this can be achieved by fabricating the strip
electrodes along intended directions and theoretically, this can be described
by the effective model $H_{W}(\bm{k},\theta)$ in Eq. (4) with a finite
rotation while keeping the normal of the electrodes fixed to the
$\hat{x}$-direction.

The numerical calculation is performed on the discretized version of
Hamiltonian $H_{W}(\bm{k},\theta)$ in the same way as that in the previous
section. Again, the momentum $k_{z}$ is taken as a parameter. In Figs.
4(a)-4(c), we plot the FAs with different azimuthal angles $\theta$. One can
see that the rotation of the effective Hamiltonian causes corresponding
rotated FAs. The transmission probabilities $T(k_{z},\varepsilon)$ as a
function of energy $\varepsilon$ and $k_{z}$ are shown in Figs. 4(d)-4(f). One
can see that there in general exist two distinct regions in the transmission
pattern as shown in Fig. 4(e) excepted for two limiting cases $\theta=0$ in
Figs. 4(d) and $\theta\geq\tan^{-1}(k_{0}/k_{1})$ 4(f). Specifically, the
regions with stripe structures and nearly uniform strength correspond to
region I and II in Fig. 1(b), respectively. In region I, backscattering
channels are available which induces interference and oscillation of the
transmission, while in region II, the transport channels are chiral with a
high transmission without oscillation. The amounts of $k_{z}$ channels in
region I and II vary with $\theta$, which is clearly revealed in the
conductance spectra in Figs. 4(g-i). As $\theta$ increases from zero, the
oscillation of conductance becomes less visible, stemming from that the ratio
between the numbers of $k_{z}$ channels in region I and II becomes smaller.
When $\theta$ exceeds the threshold $\tan^{-1}(k_{0}/k_{1})$ [Fig. 4(c)], all
electrons reside in region $\rm{II}$ and the conductance exhibits a plateau
structure without any oscillation as shown in Fig. 4(i). Such a transition
from oscillation to plateau structure in the conductance spectra provides a
clear manifestation of the highly anisotropic nature of the FAs, and therefore
can serve as its unique signal. Although we elucidate such an effect based on
a specific model in Eq. (4), the underlying physics should generally hold for
other WSMs with more complicated FA configurations. The shape of FAs and the
relative amount of $k_{z}$ channels lying in region I and II are of most
importance for the main results.

##  V magnetic field effect

In this section, we show that the visibility of the conductance oscillation
can be well improved by a magnetic field in the $\hat{y}$-direction. We focus
on the case $\theta=0$ and the results are shown in Fig. 5. The Landau gauge
$\bm{A}=(0,0,-Bx)$ is adopted such that the Peierls substitution
$\bm{k}\rightarrow-i\bm{\nabla}-e\bm{A}/\hbar$ (with $e>0$) retains the
$k_{z}$ conservation. For a small magnetic field which satisfies $B\ll\hbar
k_{0,1}/(ea)$, it only introduces a smooth modification of the mass term in
Eq. (1). Such a pseudo-spin dependent potential contributes an additional
phase factor in the transmission function $T(k_{z},\varepsilon,B)$, which
causes a shift of the pattern in the $k_{z}$-direction as can be seen in Figs.
5(d-f). A constant gauge term $\delta A$ can always be added to the vector
potential as $\bm{A}^{\prime}=(0,0,-Bx+\delta A)$, which is equivalent to an
overall shift of $k_{z}$. The physical results of the conductance spectra
should not rely on such freedom of gauge choice by noting that the Hamiltonian
is a periodic function of $k_{z}$, so that an overall shift of $k_{z}$ by
$\delta A$ has no effect after integration. The magnetic field effect can also
be well understood by the semiclassical picture of Lorentz force. The Lorentz
force drives electrons sliding along the FAs [Fig. 5(a)] which corresponds to
the curved trajectory in real space [Fig. 5(b)].

Remarkably, because that FAs are terminated at the Weyl points, some of the
electrons nearby can transfer into the chiral Landau bands of the bulk states
and dissipate due to the surface-bulk connection at the Weyl points Potter
_et al._ (2014) as illustrated by the dashed green circles in Fig. 5(a)Zheng
_et al._ (2020). As a result, these electrons can not reach the right
electrode and do not contribute to the conductance. Therefore, the magnetic
field effectively reduces the number of $k_{z}$ channels and thus the
dephasing effect, which is reflected in Figs. 5(d)-5(f) that the interference
patterns get narrower in the $k_{z}$-direction as $B$ increases. Accordingly,
one can see in Figs. 5(g)-5(i) that as $B$ increases, the magnitude of the
conductance reduces due to the loss of surface electrons; However, the
oscillation of the conductance becomes more visible stemming from weaker
dephasing. To quantify the visibility of conductance oscillation, we introduce
the resolution defined as follows

$R=\sum_{i}^{8}\frac{\sigma_{i}^{\text{max}}-\sigma_{i}^{\text{min}}}{\sigma_{i}^{\text{max}}+\sigma_{i}^{\text{min}}},$
(16)

where $\sigma_{i}^{\text{max}}$ and $\sigma_{i}^{\text{min}}$ are the
neighbouring maximum and minimum values of the conductance. We choose the most
visible eight oscillating periods to calculate the resolution and plot $R$ as
a function of $B$ in Fig. 5(c). We see that the resolution increases
significantly with increasing magnetic field, indicating that the observation
of 2D Fabry-Pérot interference can be facilitated by applying a magnetic
field, in stark contrast to other 2D electronic systems Young and Kim (2008);
Rickhaus  _et al._ (2013); Grushina  _et al._ (2013); Oksanen  _et al._
(2014); Campos  _et al._ (2012); Varlet  _et al._ (2014); Karalic  _et al._
(2020). Such a novel effect can also be used as a direct evidence of FAs.

We remark that there exists a critical magnetic field $B_{c}=\hbar K_{z}/(eL)$
in the calculation, above which all the incident electrons in the FA surface
states will transfer into the bulk and no surface transport occurs. Here,
$K_{z}$ is the span of the FA in the $k_{z}$ direction [Fig. 5(a)] and $L$ is
the distance between the two electrodes [Fig. 1(a)]. For parameters
$K_{z}=1.2\,\rm nm^{-1}$ and $L=180\,\rm nm$ adopted in Fig. 5, we have
$B_{c}\simeq 4.4$ Tesla.

##  VI discussion and summary

We would like to discuss the experimental realization of our proposal. The
surface NFAN junctions can be achieved by state-of-the-art fabrication
techniques Li  _et al._ (2020); Chen  _et al._ (2018b); Ghatak  _et al._
(2018). The WSM with a pair of FAs is a crucial building block in our
proposal, which has been reported in $\rm NbIrTe_{4}$ Ekahana  _et al._
(2020); Koepernik  _et al._ (2016); Belopolski  _et al._ (2017); Haubold  _et
al._ (2017), $\rm WP_{2}$ Yao  _et al._ (2019), $\rm MoTe_{2}$ Wang  _et al._
(2016b), and $\rm YbMnBi_{2}$ Borisenko  _et al._ (2019). The main results
still hold for other materials with more FAs as long as the two regions of
transmission can be well defined. During the calculation, for simplicity, we
set the chemical potential being zero in the WSM to have a vanishing density
of the bulk states. In real materials with finite density of states, our main
conclusions remain unchanged as long as the FAs and the bulk states are well
separated in the surface Brillouin zone. The presence of bulk states will only
cause certain leakage of surface electrons, but will not change the present
qualitative results.

To summarize, we have investigated the 2D conductance oscillation in the
planar NFAN junctions on the WSM surface, which provides a unique transport
signature of the FAs. It is found that (i) Shorter and less curved FAs can
lead to more visible conductance oscillation; (ii) A crossover from
oscillation to plateau structure of the conductance spectra can be implemented
by changing the orientation of the planar junctions; (iii) The magnetic field
can significantly enhance the visibility of the oscillation pattern which is
unique for the FA surface states. Therefore, our work offers an effective way
for the identification of FA surface states through transport measurement. It
also introduces a new platform to realize interesting 2D conductance
oscillation induced by Fabry-Pérot-type interference.

###### Acknowledgements.

This work was supported by the National Natural Science Foundation of China
under Grant No. 12074172 (W.C.), the startup grant at Nanjing University
(W.C.), the State Key Program for Basic Researches of China under Grants No.
2017YFA0303203 (D.Y.X.) and the Excellent Programme at Nanjing University.

## References

  * Weyl (1929) H. Weyl, Proceedings of the National Academy of Sciences of the United States of America 15, 323 (1929).
  * Armitage  _et al._ (2018) N. P. Armitage, E. J. Mele, and A. Vishwanath, Rev. Mod. Phys. 90, 015001 (2018).
  * Kajita (2016) T. Kajita, Rev. Mod. Phys. 88, 030501 (2016).
  * McDonald (2016) A. B. McDonald, Rev. Mod. Phys. 88, 030502 (2016).
  * Wan  _et al._ (2011) X. Wan, A. M. Turner, A. Vishwanath, and S. Y. Savrasov, Phys. Rev. B 83, 205101 (2011).
  * Murakami (2007) S. Murakami, New Journal of Physics 9, 356 (2007).
  * Burkov and Balents (2011) A. A. Burkov and L. Balents, Phys. Rev. Lett. 107, 127205 (2011).
  * Weng  _et al._ (2015) H. Weng, C. Fang, Z. Fang, B. A. Bernevig, and X. Dai, Phys. Rev. X 5, 011029 (2015).
  * Huang  _et al._ (2015a) S.-M. Huang, S.-Y. Xu, I. Belopolski, C.-C. Lee, G. Chang, B. Wang, N. Alidoust, G. Bian, M. Neupane, C. Zhang, _et al._ , Nature communications 6, 1 (2015a).
  * Lv  _et al._ (2015a) B. Q. Lv, H. M. Weng, B. B. Fu, X. P. Wang, H. Miao, J. Ma, P. Richard, X. C. Huang, L. X. Zhao, G. F. Chen, Z. Fang, X. Dai, T. Qian, and H. Ding, Phys. Rev. X 5, 031013 (2015a).
  * Xu  _et al._ (2015a) S.-Y. Xu, I. Belopolski, N. Alidoust, M. Neupane, G. Bian, C. Zhang, R. Sankar, G. Chang, Z. Yuan, C.-C. Lee, S.-M. Huang, H. Zheng, J. Ma, D. S. Sanchez, B. Wang, A. Bansil, F. Chou, P. P. Shibayev, H. Lin, S. Jia, and M. Z. Hasan, Science 349, 613 (2015a).
  * Xu  _et al._ (2015b) S.-Y. Xu, N. Alidoust, I. Belopolski, Z. Yuan, G. Bian, T.-R. Chang, H. Zheng, V. N. Strocov, D. S. Sanchez, G. Chang, _et al._ , Nature Physics 11, 748 (2015b).
  * Xu  _et al._ (2015c) S.-Y. Xu, I. Belopolski, D. S. Sanchez, C. Zhang, G. Chang, C. Guo, G. Bian, Z. Yuan, H. Lu, T.-R. Chang, P. P. Shibayev, M. L. Prokopovych, N. Alidoust, H. Zheng, C.-C. Lee, S.-M. Huang, R. Sankar, F. Chou, C.-H. Hsu, H.-T. Jeng, A. Bansil, T. Neupert, V. N. Strocov, H. Lin, S. Jia, and M. Z. Hasan, Science Advances 1 (2015c), 10.1126/sciadv.1501092.
  * Xu  _et al._ (2016) N. Xu, H. Weng, B. Lv, C. E. Matt, J. Park, F. Bisti, V. N. Strocov, D. Gawryluk, E. Pomjakushina, K. Conder, _et al._ , Nature communications 7, 1 (2016).
  * Deng  _et al._ (2016) K. Deng, G. Wan, P. Deng, K. Zhang, S. Ding, E. Wang, M. Yan, H. Huang, H. Zhang, Z. Xu, _et al._ , Nature Physics 12, 1105 (2016).
  * Yang  _et al._ (2015) L. Yang, Z. Liu, Y. Sun, H. Peng, H. Yang, T. Zhang, B. Zhou, Y. Zhang, Y. Guo, M. Rahn, _et al._ , Nature physics 11, 728 (2015).
  * Huang  _et al._ (2016) L. Huang, T. M. McCormick, M. Ochi, Z. Zhao, M.-T. Suzuki, R. Arita, Y. Wu, D. Mou, H. Cao, J. Yan, _et al._ , Nature materials 15, 1155 (2016).
  * Tamai  _et al._ (2016) A. Tamai, Q. S. Wu, I. Cucchi, F. Y. Bruno, S. Riccò, T. K. Kim, M. Hoesch, C. Barreteau, E. Giannini, C. Besnard, A. A. Soluyanov, and F. Baumberger, Phys. Rev. X 6, 031021 (2016).
  * Jiang  _et al._ (2017) J. Jiang, Z. Liu, Y. Sun, H. Yang, C. Rajamathi, Y. Qi, L. Yang, C. Chen, H. Peng, C. Hwang, _et al._ , Nature communications 8, 1 (2017).
  * Belopolski  _et al._ (2016) I. Belopolski, D. S. Sanchez, Y. Ishida, X. Pan, P. Yu, S.-Y. Xu, G. Chang, T.-R. Chang, H. Zheng, N. Alidoust, _et al._ , Nature communications 7, 1 (2016).
  * Lv  _et al._ (2015b) B. Lv, N. Xu, H. Weng, J. Ma, P. Richard, X. Huang, L. Zhao, G. Chen, C. Matt, F. Bisti, _et al._ , Nature Physics 11, 724 (2015b).
  * Zyuzin and Burkov (2012) A. A. Zyuzin and A. A. Burkov, Phys. Rev. B 86, 115133 (2012).
  * Aji (2012) V. Aji, Phys. Rev. B 85, 241101 (2012).
  * Son and Spivak (2013) D. T. Son and B. Z. Spivak, Phys. Rev. B 88, 104412 (2013).
  * Chernodub  _et al._ (2014) M. N. Chernodub, A. Cortijo, A. G. Grushin, K. Landsteiner, and M. A. H. Vozmediano, Phys. Rev. B 89, 081407 (2014).
  * Zhou  _et al._ (2013) J.-H. Zhou, H. Jiang, Q. Niu, and J.-R. Shi, Chinese Physics Letters 30, 027101 (2013).
  * Burkov (2015) A. A. Burkov, Journal of Physics: Condensed Matter 27, 113201 (2015).
  * Ma and Pesin (2015) J. Ma and D. A. Pesin, Phys. Rev. B 92, 235205 (2015).
  * Zhong  _et al._ (2016) S. Zhong, J. E. Moore, and I. Souza, Phys. Rev. Lett. 116, 077201 (2016).
  * Spivak and Andreev (2016) B. Z. Spivak and A. V. Andreev, Phys. Rev. B 93, 085107 (2016).
  * Hirschberger  _et al._ (2016) M. Hirschberger, S. Kushwaha, Z. Wang, Q. Gibson, S. Liang, C. A. Belvin, B. A. Bernevig, R. J. Cava, and N. P. Ong, Nature materials 15, 1161 (2016).
  * Huang  _et al._ (2015b) X. Huang, L. Zhao, Y. Long, P. Wang, D. Chen, Z. Yang, H. Liang, M. Xue, H. Weng, Z. Fang, X. Dai, and G. Chen, Phys. Rev. X 5, 031023 (2015b).
  * Shekhar  _et al._ (2015) C. Shekhar, A. K. Nayak, Y. Sun, M. Schmidt, M. Nicklas, I. Leermakers, U. Zeitler, Y. Skourski, J. Wosnitza, Z. Liu, _et al._ , Nature Physics 11, 645 (2015).
  * Du  _et al._ (2016) J. Du, H. Wang, Q. Chen, Q. Mao, R. Khan, B. Xu, Y. Zhou, Y. Zhang, J. Yang, B. Chen, _et al._ , Science China Physics, Mechanics & Astronomy 59, 657406 (2016).
  * Wang  _et al._ (2016a) Z. Wang, Y. Zheng, Z. Shen, Y. Lu, H. Fang, F. Sheng, Y. Zhou, X. Yang, Y. Li, C. Feng, and Z.-A. Xu, Phys. Rev. B 93, 121112 (2016a).
  * Zhang  _et al._ (2016) C.-L. Zhang, S.-Y. Xu, I. Belopolski, Z. Yuan, Z. Lin, B. Tong, G. Bian, N. Alidoust, C.-C. Lee, S.-M. Huang, _et al._ , Nature communications 7, 1 (2016).
  * Nielsen and Ninomiya (1981a) H. Nielsen and M. Ninomiya, Nuclear Physics B 185, 20 (1981a).
  * Nielsen and Ninomiya (1981b) H. Nielsen and M. Ninomiya, Nuclear Physics B 193, 173 (1981b).
  * Nielsen and Ninomiya (1983) H. Nielsen and M. Ninomiya, Physics Letters B 130, 389 (1983).
  * Morali  _et al._ (2019) N. Morali, R. Batabyal, P. K. Nag, E. Liu, Q. Xu, Y. Sun, B. Yan, C. Felser, N. Avraham, and H. Beidenkopf, Science 365, 1286 (2019).
  * Yang  _et al._ (2019) H. Yang, L. Yang, Z. Liu, Y. Sun, C. Chen, H. Peng, M. Schmidt, D. Prabhakaran, B. A. Bernevig, C. Felser, _et al._ , Nature communications 10, 1 (2019).
  * Ekahana  _et al._ (2020) S. A. Ekahana, Y. W. Li, Y. Sun, H. Namiki, H. F. Yang, J. Jiang, L. X. Yang, W. J. Shi, C. F. Zhang, D. Pei, C. Chen, T. Sasagawa, C. Felser, B. H. Yan, Z. K. Liu, and Y. L. Chen, Phys. Rev. B 102, 085126 (2020).
  * Chen  _et al._ (2018a) W. Chen, K. Luo, L. Li, and O. Zilberberg, Phys. Rev. Lett. 121, 166802 (2018a).
  * Chen  _et al._ (2020) G. Chen, O. Zilberberg, and W. Chen, Phys. Rev. B 101, 125407 (2020).
  * Zheng  _et al._ (2020) Y. Zheng, W. Chen, and D. Xing, arXiv preprint arXiv:2012.08066 (2020).
  * Young and Kim (2008) A. F. Young and P. Kim, Nature Physics 5, 222 (2008).
  * Rickhaus  _et al._ (2013) P. Rickhaus, R. Maurand, M. H. Liu, M. Weiss, K. Richter, and C. SchöNenberger, Nature Communications 4, 2342 (2013).
  * Grushina  _et al._ (2013) A. L. Grushina, D.-K. Ki, and A. F. Morpurgo, Appl. Phys. Lett. 102, 223102 (2013).
  * Oksanen  _et al._ (2014) M. Oksanen, A. Uppstu, A. Laitinen, D. J. Cox, M. F. Craciun, S. Russo, A. Harju, and P. Hakonen, Phys. Rev. B 89, 121414(R) (2014).
  * Campos  _et al._ (2012) L. C. Campos, A. F. Young, K. Surakitbovorn, K. Watanabe, T. Taniguchi, and P. Jarillo-Herrero, Nature Communications 3, 1239 (2012).
  * Varlet  _et al._ (2014) A. Varlet, M.-H. Liu, V. Krueckl, D. Bischoff, P. Simonet, K. Watanabe, T. Taniguchi, K. Richter, K. Ensslin, and T. Ihn, Phys. Rev. Lett. 113, 116601 (2014).
  * Karalic  _et al._ (2020) M. Karalic, A. Trkalj, M. Masseroni, W. Chen, and O. Zilberberg, Phys. Rev. X 10, 031007 (2020).
  * Chen  _et al._ (2013) W. Chen, L. Jiang, R. Shen, L. Sheng, B. G. Wang, and D. Y. Xing, EPL (Europhysics Letters) 103, 27006 (2013).
  * Datta (1997) S. Datta,  _Electronic transport in mesoscopic systems_ (Cambridge university press, 1997).
  * Koepernik  _et al._ (2016) K. Koepernik, D. Kasinathan, D. V. Efremov, S. Khim, S. Borisenko, B. Büchner, and J. van den Brink, Phys. Rev. B 93, 201101 (2016).
  * Belopolski  _et al._ (2017) I. Belopolski, P. Yu, D. S. Sanchez, Y. Ishida, T.-R. Chang, S. S. Zhang, S.-Y. Xu, H. Zheng, G. Chang, G. Bian, _et al._ , Nature communications 8, 1 (2017).
  * Haubold  _et al._ (2017) E. Haubold, K. Koepernik, D. Efremov, S. Khim, A. Fedorov, Y. Kushnirenko, J. van den Brink, S. Wurmehl, B. Büchner, T. K. Kim, M. Hoesch, K. Sumida, K. Taguchi, T. Yoshikawa, A. Kimura, T. Okuda, and S. V. Borisenko, Phys. Rev. B 95, 241108 (2017).
  * Groth  _et al._ (2014) C. W. Groth, M. Wimmer, A. R. Akhmerov, and X. Waintal, New Journal of Physics 16, 063065 (2014).
  * Potter  _et al._ (2014) A. C. Potter, I. Kimchi, and A. Vishwanath, Nature communications 5, 1 (2014).
  * Li  _et al._ (2020) C.-Z. Li, A.-Q. Wang, C. Li, W.-Z. Zheng, A. Brinkman, D.-P. Yu, and Z.-M. Liao, Nature communications 11, 1 (2020).
  * Chen  _et al._ (2018b) A. Q. Chen, M. J. Park, S. T. Gill, Y. Xiao, D. Reig-i Plessis, G. J. MacDougall, M. J. Gilbert, and N. Mason, Nature communications 9, 1 (2018b).
  * Ghatak  _et al._ (2018) S. Ghatak, O. Breunig, F. Yang, Z. Wang, A. A. Taskin, and Y. Ando, Nano letters 18, 5124 (2018).
  * Yao  _et al._ (2019) M.-Y. Yao, N. Xu, Q. S. Wu, G. Autès, N. Kumar, V. N. Strocov, N. C. Plumb, M. Radovic, O. V. Yazyev, C. Felser, J. Mesot, and M. Shi, Phys. Rev. Lett. 122, 176402 (2019).
  * Wang  _et al._ (2016b) Z. Wang, D. Gresch, A. A. Soluyanov, W. Xie, S. Kushwaha, X. Dai, M. Troyer, R. J. Cava, and B. A. Bernevig, Phys. Rev. Lett. 117, 056805 (2016b).
  * Borisenko  _et al._ (2019) S. Borisenko, D. Evtushinsky, Q. Gibson, A. Yaresko, K. Koepernik, T. Kim, M. Ali, J. van den Brink, M. Hoesch, A. Fedorov, _et al._ , Nature communications 10, 1 (2019).


inproceedings [fieldset=publisher, null] [fieldset=urldate, null]
[fieldset=volume, null] [fieldset=pages, null]

#  Rapidly-exploring Random Forest: Adaptively Exploits Local Structure with
Generalised Multi-Trees Motion Planning

Tin Lai† Correspondence to<EMAIL_ADDRESS>
†School of Computer Science, The University of Sydney, Australia.

###### Abstract

Sampling-based motion planners perform exceptionally well in robotic
applications that operate in high-dimensional space. However, most works often
constrain the planning workspace rooted at some fixed locations, do not
adaptively reason on strategy in narrow passages, and ignore valuable local
structure information. In this paper, we propose Rapidly-exploring Random
Forest (rrf*)—a generalised multi-trees motion planner that combines the rapid
exploring property of tree-based methods and adaptively learns to deploys a
Bayesian local sampling strategy in regions that are deemed to be bottlenecks.
Local sampling exploits the local-connectivity of spaces via Markov Chain
random sampling, which is updated sequentially with a Bayesian proposal
distribution to learns the local structure from past observations. The trees
selection problem is formulated as a multi-armed bandit problem, which
efficiently allocates resources on the most promising tree to accelerate
planning runtime. rrf* learns the region that is difficult to perform tree
extensions and adaptively deploys local sampling in those regions to maximise
the benefit of exploiting local structure. We provide rigorous proofs of
completeness and optimal convergence guarantees, and we experimentally
demonstrate that the effectiveness of rrf*’s adaptive multi-trees approach
allows it to performs well in a wide range of problems.

##  I Introduction

Motion planning is one of the fundamental methods for robots to navigate and
integrate with the real-world. Obstacles and physical constraints are
ubiquitous regardless of the type of robotic applications, and we wish to
safely and efficiently navigate the robot from some initial state to a target
state. Sampling-based motion planners (SBPs) are of a class of robust methods
to perform motion planning. SBPs do no need to explicitly construct the often
intractable high-dimensional Configuration Space (_C-space_). SBP samples _C-
space_ randomly for valid connections and iteratively builds a roadmap of
connectivity. SBPs are guaranteed to find a solution if one exists [1].
Further developments on SBPs had granted _asymptotic optimality_ [2]—a
guarantee that the solution will converge, in the limit, to the optimal
solution.

Figure 1:  Overview illustration of rrf* using multiple trees to adaptively
plans on the current most promising tree, which rapidly explores visible space
and exploits local structures with Bayesian local sampling. Green and red
nodes refers to the initial $q_{\text{init}}$ and target $q_{\text{target}}$
configuration; teal and purple trees are the rooted
$T_{\text{init}},T_{\text{target}}$ and local trees respectively. Orange
hatched circles are the current states of local samplers sampling for their
respective local trees. rrf* learns to creates new local trees in highly
constrained regions that are hard to extend from root trees, of which will be
benefited from proposing informed samples through Bayesian local sampling.

One of the fundamental issues with SBPs lies in SBP’s approach—the exceedingly
low likelihood of sampling within narrow passages. Intuitively, regions with
low visibility will have a low probability to be randomly sampled. Therefore,
when SBPs perform roadmap-based planning by random sampling and creating
connections in _C-space_ , highly constrained regions become problematic as
they limit the connectivity of free space [3, 4]. Narrow passages severely
restrict the performance of SBPs because SBPs throw away the unlikely samples
that do fall within narrow passages if the tree failed to expand.
Consequently, narrow passages will bottleneck the tree’s growth until a series
of tree expansions had successfully created connections within the restricting
narrow passages.

Our contribution is an incremental multi-trees SBP—Rapidly-exploring Random
Forest (rrf*)—that learns from sampling information and adjust planning
strategy accordingly. We formulate rrf* to learns regions that are likely to
be bottlenecked and adaptively deploys Bayesian local sampling to exploits _C-
space_ ’s local structure. Unlike previous local SBPs that deploy local trees
everywhere regardless of the nearby region’s complexity, rrf* utilises the
rapid growth of the rooted trees approach for open spaces and adaptively uses
local trees within bottlenecks. Bayesian local sampling tackles the narrow
passage problem by performing sequential Markov chain Monte Carlo (MCMC)
random walks within the passage, and at the same time, updates its proposal
distribution from sampled outcomes. In additions, rrf* plans with multiple
trees and allocates planning resources on the most promising tree by the
reward signal from our multi-armed bandit formulation. We provide rigorous
proofs on completeness and optimal convergence guarantees. Experimentally, we
show that rrf* achieves superior results in a wide range of scenarios,
especially, rrf* yields high sample efficiency in highly constrained _C-
space_.

##  II Related Work

One of the most influential works on SBPs is Probabilistic Roadmap (prm),
which creates a random roadmap of connectivity that can be reused [5].
Rapidly-exploring Random Tree (rrt) [6] follows a similar idea but instead
uses a tree structure to obtain a more rapid single-query solution. Most SBPs
minimises some cost, e.g., distance metric or control cost. Therefore, prm∗
[7] and rrt* [8] are introduced that exhibit _asymptotic optimal_ guarantee.
The runtime performance of SBPs had been one of the main focus in existing
works. For example, to address the narrow passage problem, some planners focus
the random sampling to specific regions in _C-space_ [9]. Such an approach
often requires some technique to discover narrow passages, e.g., using bridge
test [10], space projection [11], heuristic measures of obstacles boundary
[12, 13], and densely samples at discovered narrow regions [14, 15, 16]. There
are also sampling techniques that improve sampling efficiency by using a
restricted or learned sampling distribution [17, 18, 19, 20], which either
formulate some regions for generating samples or deploy a machine learning
approach to learn from experience. However, while those approaches improved
sampling efficiency, they do not directly address the limited visibility issue
within narrow passages.

Some planners had employed a multi-tree approach to explore _C-space_ more
efficiently. For example, growing bidirectional trees can speed up the
exploration process because tree extensions at different origin are subject to
a different degree of difficulty [21]. Potential tree locations can be
searched with the bridge test, followed by a learning technique to model the
probability of tree selection [22]. Local trees had been employed for growing
multiple trees in parallel [23, 4]. However, current approaches utilise local
trees regardless of the complexity of the nearby regions. While those
approaches had improved sampling efficiency, it would be more beneficial to
deploy local planners dependent on the _C-space_ complexity adaptively.
Several SBPs had utilised Markov Chain Monte Carlo (MCMC) for local planning,
as it allows utilisation of information observed from previous samples [24].
Monte Carlo random walk planner searches free space by constructing a Markov
Chain to propose spaces with high contributions [25]. The roadmap of a PRM can
be formulated as the result of simultaneously running a set of MCMC
explorations [26]. Therefore, the connectives between feasible states can be
modelled as a chain of samples walking within the free space. Our proposing
rrf* exploits this property by utilising a Bayesian approach in proposing
chained samples by sequentially updating our belief on the space that are
deemed to be bottlenecks.

##  III Rapidly-exploring Random Forest

Motion planning’s objective is to construct a feasible trajectory from an
initial configuration $q_{\text{init}}$ to a target configuration
$q_{\text{target}}$, where $q\in C\subseteq\mathbb{R}^{d}$ denotes a state the
_C-space_ and $d\geq 2$ is the dimensionality. The obstacle spaces
$C_{\text{obs}}$ denotes the set of invalid states, and the set of free space
$C_{\text{free}}$ is defined as the closure set $\text{cl}(C\setminus
C_{\text{obs}})$. In motion planning, there is often some cost function that
the planner wants to optimise.

######  Problem 1 (Asymptotic optimal planning)

Given $C$, $C_{\text{obs}}$, a pair of initial $q_{\text{init}}$ and target
$q_{\text{target}}$ configurations, a _cost function_
$\mathcal{L}_{c}\colon\sigma\to[0,\infty)$, and let $\Gamma(C_{\text{free}})$
denotes the set of all possible trajectories in $\text{cl}(C_{\text{free}})$.
Find a solution trajectory $\sigma^{*}$ that exhibits the minimal cost. That
is, find $\sigma^{*}$ such that $\sigma^{*}(0)=q_{\text{init}}$,
$\sigma^{*}(1)=q_{\text{target}}$, and
$\mathcal{L}_{c}(\sigma^{*})=\min_{\sigma\in\Gamma(C_{\text{free}})}\mathcal{L}_{c}(\sigma)$.

###  III-A High-level description

Figure 2:  Illustration of rrf* performing Bayesian local sampling for a local
tree. The spherical proposal distribution is overlaid on the local sampler as
a blue curve, which is sequentially learned after 10 previous failed samples
(purple arrows). The transparent grey arrows illustrates the likelihood of
sampling 20 times from the probability distribution shown.

rrf* uses multiple trees to adaptively explores and exploits different regions
of _C-space_. Traditional approaches use only a single tree rooted at
$q_{\text{initial}}$ to construct a roadmap of connected configurations. The
tree grows outwards by sampling random configurations that create a new
connection to the closest node. Since the tree expansion is limited to a local
scope bounded by the neighbourhood visibility of the frontier tree nodes, such
an approach will often reject updates from valid samples when there exists no
free route from the closest existing node towards the sampled configuration.
rrf* overcomes this limitation by addressing the sampling-based motion
planning problem with a divide-and-conquer approach. rrf* follows the approach
in [27] which uses local trees for Bayesian local sampling. However, instead
of purely using Markov Chain to plan within _C-space_ [27], rrf* adaptively
locates difficult regions for tree extensions and only proposes new local
trees when local planning is beneficial. rrf* uses two rooted trees and
reformulate the spawning of local-trees as an adaptive selection process.
Previous work replaces the motion planning problem entirely with Markov
Chains; however, we argue that the most effective approach relies on deploying
the most appropriate strategy in specific regions. As a result, rrf* is biased
more on exploration in regions that contain lots of free space, whereas in
restricted bottlenecks, rrf* will adaptively deploy local sampling within
narrow passages.

rrf* formulates the tree-selection problem as a multi-armed bandit (MAB)
problem. Using a MAB approach helps develop an adaptive selection strategy
that actively selects the tree that is more promising in tree extensions. MAB
allows rrf* to focus its resources on trees that are more likely to
successfully expand and switch to the local sampling approach when it is more
profitable.

###  III-B Learning Local Sampling with Bayesian Updates

We model the local sampling procedure as a Markovian process. A local
planner’s state $\Theta_{t}$ refers to its spatial location and
$C_{\text{obs}}$ nearby at step $t$. It cannot be directly observed, but we
can observe the outcome by sampling a direction $x_{\text{new}}$ from the
local planner’s current location $q_{t}$ at $t$ and use $x_{\text{new}}$ to
extends towards a nearby configuration $q_{\text{new}}$. The observation
outcome is said to be successful if
$\sigma_{\mathchoice{\vbox{\halign{#\cr\rightarrowfill@{\scriptstyle}\crcr\nointerlineskip\cr$\hfil\displaystyle
q_{n}q_{\text{new}}\hfil$\crcr}}}{\vbox{\halign{#\cr\rightarrowfill@{\scriptstyle}\crcr\nointerlineskip\cr$\hfil\textstyle
q_{n}q_{\text{new}}\hfil$\crcr}}}{\vbox{\halign{#\cr\rightarrowfill@{\scriptscriptstyle}\crcr\nointerlineskip\cr$\hfil\scriptstyle
q_{n}q_{\text{new}}\hfil$\crcr}}}{\vbox{\halign{#\cr\rightarrowfill@{\scriptscriptstyle}\crcr\nointerlineskip\cr$\hfil\scriptscriptstyle
q_{n}q_{\text{new}}\hfil$\crcr}}}}\in C_{\text{free}}$, where the notation
$\sigma_{\mathchoice{\vbox{\halign{#\cr\rightarrowfill@{\scriptstyle}\crcr\nointerlineskip\cr$\hfil\displaystyle
q_{i}q_{j}\hfil$\crcr}}}{\vbox{\halign{#\cr\rightarrowfill@{\scriptstyle}\crcr\nointerlineskip\cr$\hfil\textstyle
q_{i}q_{j}\hfil$\crcr}}}{\vbox{\halign{#\cr\rightarrowfill@{\scriptscriptstyle}\crcr\nointerlineskip\cr$\hfil\scriptstyle
q_{i}q_{j}\hfil$\crcr}}}{\vbox{\halign{#\cr\rightarrowfill@{\scriptscriptstyle}\crcr\nointerlineskip\cr$\hfil\scriptscriptstyle
q_{i}q_{j}\hfil$\crcr}}}}$ denote the connection between the configurations
$q_{i}$ and $q_{j}$. We use a Bayesian approach in our work to sequentially
update and improve our proposal distribution based on the observed outcomes.

When a local sampler at state $\Theta_{t}$ is expanding a local tree via
Bayesian local sampling, it draws a direction $x_{t,i}$ from a proposal
distribution $\mathcal{Q}_{t}$ and extend towards $x_{t,i}$, where $i$ denotes
the $i$th attempt to extends the connection. If it is unsuccessful, the local
planner remains at state $\Theta_{t}$, and another sample is drawn from the
updated proposal distribution
$x_{t,i+1}\sim\mathcal{Q}_{t}(x\>|\>x_{t-1},\mathcal{X}_{i+1})$, where
$x_{t-1}$ is the previous successful direction and $\mathcal{X}_{i+1}$ is the
set of all previously failed directions at iteration $i+1$. Whereas if the
extension towards $x_{t,i}$, we say that $x_{t}:=x_{t,i}$ (the successful
direction at $t$), and local planner will transits to state $\Theta_{t+1}$ and
proceed to draws sample from
$x_{t+1,1}\sim\mathcal{Q}_{t+1}(x\>|\>x_{t},\mathcal{X}_{1})$ in the next
iteration, where $\mathcal{X}_{1}:=\emptyset$. Therefore, the update follows
the Bayesian updating scheme where $f_{\text{posterior}}\propto
f_{\text{prior}}\cdot f_{\text{likelihood}}$ and subsequently uses current
posterior as the next prior.

rrf* uses the von-Mises Fisher distribution [28]
$f(\boldsymbol{x}\>|\>\boldsymbol{\mu},\kappa)$ as the initial prior
$f_{\text{prior}}$ with $\boldsymbol{\mu}$ being the previous successful
direction. After observing the sampling outcome, we use a likelihood function
to reduce the probability to sample again in the previously failed directions.
The likelihood function is formulated as
$f_{\text{likelihood}}(x\>|\>x^{\prime})\propto\big{(}1-k(x,x^{\prime})\big{)}$,
where $k$ is the kernel function to incorproate failure information from
$\mathcal{X}$. We can write the posterior of the proposal distribution for
local sampler at state $\Theta_{t}$ as

$\displaystyle\mathcal{Q}_{t}(x\>|\>x_{t-1},\mathcal{X}_{i})$
$\displaystyle=\frac{\mathcal{Q}_{t}(x\>|\>x_{t-1},\mathcal{X}_{i-1})\left(1-\beta\cdot
k(x,x^{\prime}_{i-1})\right)}{\alpha_{i}},$ (1)

where $x^{\prime}_{i-1}\in\mathcal{X}_{i}=\set{x^{\prime}_{1},\ldots
x^{\prime}_{i-1}}$ for $i>1$, $\beta$ is a scalar that controls the influence
of the kernel, and $\alpha_{i}$ is the normalising factor. Note that
$\mathcal{Q}_{i}(x\>|\>x_{i-1},\mathcal{X}_{1})$ reduces to
$f_{\text{prior}}(x\>|\>x_{i-1})$ as $\mathcal{X}_{1}:=\emptyset$. We use the
periodic squared exponential [29] to sequentially incorporate past sampled
results into $\mathcal{Q}$, given by
$k(x,x^{\prime})=\sigma^{2}\exp({-{2\sin^{2}(\pi(x-x^{\prime})/p)}/{\lambda^{2}}}),$
where $\lambda$ is the length scale, $\sigma$ is a scaling factor, and
$p=2\pi$ is the period of repetition. Fig. 2 illustrates an example of the
sequentially updated distribution $\mathcal{Q}$ after 10 failed samples.

###  III-C Maximising Successes with Multi-Armed Bandit

The tree selections process is formulated as a MAB problem to maximise
resource allocation. Each tree $T_{i}\in\mathcal{T}$ is located at some
configuration in $C_{\text{free}}$, which exhibits varying degree of
complexity dependent on its surroundings. Hence, there are often some trees in
$\mathcal{T}$ that exhibit a higher success tree expansion rates than others.
Using MAB scheduler helps to bias the exploration of the trees rooted at
$q_{\text{init}}$ and $q_{\text{target}}$ when there are abundant free spaces
(usually results in a faster initial solution), or rrf* can create local trees
for local-connectivity exploitation when _C-space_ is highly restricted (helps
to plan within narrow passages). Because spaces with complex surroundings
(narrow passages) can utilise local-connectivity information to exploits
obstacles’ structure (as discussed in section III-B); whilst areas with high
visibility allow us to allocate more resources on rapid exploring.

We formalise the tree selections in rrf* as a Mortal MAB [30] with non-
stationary reward sequences [31]. Each arm $a_{i}\in A$ is a stateful local
sampler that transverse within $C_{\text{free}}$, with state at time $t$
denoted as $a_{i,t}$ that consists of the spatial location, previous
successful direction and the number of failed expansions. At each $t$ it
samples $C$ to makes an observation $o_{t}$ and receives a reward
$R(a_{i,t})$. We consider discrete time and Bernoulli arms, with arms success
probability at time $t$ formulated as

$\forall{i\in\\{1,...,k\\}}\colon\mathbb{P}(a_{i,t}\mid a_{i,t-1},o_{t-1}).$
(2)

We consider the arms as independent random variables with
$\mathbb{P}(a_{i,t})$ having non-stationary distribution dependent on its
previous samples. The reward $R(a_{i,t})$ is a functional mappings of the
current state of the local sampler to a real value reward, where

$R(a_{i,t})=\begin{cases}1&\text{if $a_{i,t}$ located in $C_{\text{free}}$}\\\
0&\text{otherwise}.\end{cases}$ (3)

The reward sequence $R(a_{i,1}),\ldots,R(a_{i,t})$ is a stochastic sequence
with unknown payoff distributions and can changes rapidly according to the
complexity of _C-space_. Each arm has a stochastic lifetime after which they
would expire due to events such as running into a dead-end or stuck in a
narrow passage. In practice we prune away an arm $a_{i}$ if it is deemed
unprofitable when its success probability $\mathbb{P}(a_{i,t}\mid
a_{i,t-1},o_{t-1})$ is lower than some threshold $\eta$. The action space to
create new local trees is infinite, but we identify high potential areas to
spawn new arms through learning areas in $C_{\text{free}}$ that exhibit
frequent failed tree-extension attempts.

###  III-D Implementation

Input: $q_{\text{init}},q_{\text{target}},N,k,\epsilon,\eta$

Initialise:
$\mathcal{T}\leftarrow\\{\;T_{\text{init}}(V=\\{q_{\text{init}}\\},E=\emptyset),\,T_{\text{target}}(V=\\{q_{\text{target}}\\},E=\emptyset)\;\\}$;
$A\leftarrow$ Initialise arms; $n\leftarrow 1$;

1 while  _$n\leq N$_ do

2

3 $\mathcal{T},A\leftarrow\texttt{ProposeLocalTree}(\mathcal{T},A,k,\epsilon)$

4 $T_{i},a_{i}\leftarrow\texttt{PickTreeMAB}(\mathcal{T},A)$

5

6 if  _$T_{i}\in\set{T_{\text{init}},T_{\text{target}}}$_ then

7 $q_{\text{rand}}\leftarrow$ SampleFree

8 $q_{\text{closest}}\leftarrow$ closest node in $T_{i}$

9 $q_{\text{new}}\leftarrow$ $q_{\text{closest}}$ with $\epsilon$ step towards
$q_{\text{rand}}$

10

11 else

12 $q_{\text{closest}}\leftarrow$ current location of local sampler in $T_{i}$

13 $q_{\text{new}}\leftarrow$ samples for $T_{i}$ locally via MCMC

14

15 if
_$\sigma_{\mathchoice{\vbox{\halign{#\cr\rightarrowfill@{\scriptstyle}\crcr\nointerlineskip\cr$\hfil\displaystyle
q_{\text{closest}}\;q_{\text{new}}\hfil$\crcr}}}{\vbox{\halign{#\cr\rightarrowfill@{\scriptstyle}\crcr\nointerlineskip\cr$\hfil\textstyle
q_{\text{closest}}\;q_{\text{new}}\hfil$\crcr}}}{\vbox{\halign{#\cr\rightarrowfill@{\scriptscriptstyle}\crcr\nointerlineskip\cr$\hfil\scriptstyle
q_{\text{closest}}\;q_{\text{new}}\hfil$\crcr}}}{\vbox{\halign{#\cr\rightarrowfill@{\scriptscriptstyle}\crcr\nointerlineskip\cr$\hfil\scriptscriptstyle
q_{\text{closest}}\;q_{\text{new}}\hfil$\crcr}}}}\in C_{\text{free}}$_ then

16 Join $q_{\text{new}}$ to all $T_{i}\in\mathcal{T}$ within
$\epsilon$-distance

17 if  _$q_{\text{new}}$ joined to $T_{\text{init}}$_ then
Rewire(_$T_{\text{init}}$_)

18 Update location of $a_{i}$ to $q_{\text{new}}$

19 $n\leftarrow n+1$

20

21 Updates $T_{i},a_{i}$ probability

$\triangleright$ Remove local tree with low prob

22 if  _$T_{i}\not\in\\{T_{\text{init}},T_{\text{target}}\\}$ and
$\mathbb{P}(a_{i})<\eta$_ then

23 $A\leftarrow A\setminus\\{a_{i}\\}$

24

25

Algorithm 1 rrf* Algorithm

Algorithm 1 illustrates the overall flow of the rrf* algorithm. The planner
begins by initialising two trees rooted at $q_{\text{init}}$ and
$q_{\text{target}}$, similar to Bidirectional RRT [21]. Then, arms are
initialised into $A$, which stores the trees’ success probability, and
subsequently used in the PickTreeMAB multi-armed bandit subroutine in Alg. 1.
rrf* explores _C-space_ by picking $a_{i}\in A$ and its corresponding
$T_{i}\in\mathcal{T}$ based on how likely it is for the $T_{i}$ tree extension
to be successful. Am arm $a_{i}$ is drawn from a multinomial distribution with
each $a_{i}\in A$ having probability formulated by eq. 2. Then, if $T_{i}$ is
a tree rooted at either $q_{\text{init}}$ or $q_{\text{target}}$ (Alg. 1), the
standard tree-based planning procedure is followed—a random free configuration
$q_{\text{rand}}$ is uniformly and randomly sampled with SampleFree, followed
by searching for the closest node in $T_{i}$ and attempting to extend the node
towards $q_{\text{rand}}$ by an $\epsilon$ distance. On the other hand, if
$T_{i}$ is a local tree we utilise local sampling to exploit local structure
(Alg. 1). Local sampling incorporates past successes by utilising a Bayesian
sequential updates procedure (section III-B), which uses a MCMC random walker
that constructs a chained sampling with the sequentially learned proposal
distribution $\mathcal{Q}$ in eq. 1 to propose $q_{\text{new}}$. In both
cases, if the connection from $q_{\text{closest}}$ to $q_{\text{new}}$ is
valid then the connection will be added to $T_{i}$ accordingly. Whenever we
add a new node to $T_{i}$, we search its nearby $\epsilon$ radius for nodes
from other trees and merges both trees (Alg. 1). This procedure naturally
combines trees as part of the tree expansions process, which gradually reduces
the number of local trees as the roadmap fills $C_{\text{free}}$. If a new
node or tree is joined to the root tree $T_{\text{init}}$, the standard rewire
procedure is performed to guarantees asymptotic optimality (see [7] for
details on Rewire). Finally, rrf* updates the arm $a_{i}$’s success
probability and will discard the local sampler if its probability is lower
than some threshold $\eta$, e.g., when the local sampler is stuck in some
dead-end. The tree $T_{i}$ will remain to be in $\mathcal{T}$ for future
connections, but the arm $a_{i}$ will be discarded such that there will be no
local sampler actively performing local sampling for $T_{i}$.

Algorithm 2 shows the subroutine to propose new local tree locations. Local
trees are only created when a constrained location with high potential are
proposed in Alg. 2, where $p_{\text{potential}}$ denotes the probability that
the proposing location will be benefited from local sampling. Numerous
different techniques can be used for this proposal procedure. For example, (i)
location’s proposal can be supplied by the user, (ii) by laying prior and
using Bayesian optimisation to sequentially update the posterior, or (iii)
directly learned by neural networks through past experiences. In our
experiments, we implemented a simple cluster-based technique that is quick to
compute. The location proposer identifies regions that have a considerable
amount of samples $q_{\text{rand}}\in C_{\text{free}}$ that repeatedly failed
to connect to existing trees and propose those regions based on the failure
density. Our approach utilises sample information that is readily available
without extra effort, which results in a non-trivial performance gain. The
location proposer does not need to be perfect, but proposing regions near
narrow passages will significantly enhance the effectiveness of exploiting
local structures.

##  IV Analysis

In this section, we analyse the behaviour of the rrf* algorithm and its
algorithmic tractability. In additions, we provide proof of completeness and
optimality guarantee.

####  IV-1 Tractability of Planning with Local Trees

Although rrf* creates new local trees to explore narrow passages, tractability
is retained as the number of local trees is bounded.

###### Assumption 1

The free space $C_{\text{free}}\subseteq C$ is a finite set.

######  Theorem 1 (Termination of creating new local trees)

Let Assumption 1 hold. Then, the accumulative number of local trees
$n_{\text{local-tree}}$ for any given _C-space_ is always finite. That is,
there exists a constant $\varphi\in\mathbb{Z},\varphi\geq 0$ such that
$n_{\text{local-tree}}\leq\varphi$ for any given $C$.

###### Proof:

From Alg. 2, if there exists other $T_{i}\in\mathcal{T}$ within $\epsilon$
distance (Alg. 2), the proposing configuration will be joined to the existing
local tree $T_{i}$ and no new tree will be created (Alg. 2). Hence, every new
local tree $T_{j}$ must be at least $\epsilon$-distance away from
$T_{i}\in\mathcal{T}$ where $T_{i}\neq T_{j}$. We can formulate each node in
$T_{i}\in\mathcal{T}$ as a $d$-dimensional volume hypersphere with $\epsilon$
radius centred at the node. In the limiting case, $C_{\text{free}}$ will be
completely filled by the volume of $\epsilon$-balls. Let $\epsilon(q)$ denotes
the $\epsilon$-ball of $q$, and $V_{t}$ be the set of all nodes from all trees
$T\in\mathcal{T}$ at iteration $t$. Then, the above statement is formally
stated as $\lim_{t\to\infty}C_{\text{free}}\setminus\bigcup_{q\in
V_{t}}\epsilon(q)=\emptyset.$ Therefore, $n_{\text{local-tree}}$ is upper
bounded by the number of $\epsilon$-balls that fully fills $C_{\text{free}}$.
It is immediate that if $C_{\text{free}}$ is a finite set, $n_{\text{local-
tree}}$ will always be bounded by a constant. ∎

1 function  _$\textnormal{{ProposeLocalTree}}(\mathcal{T},A,k,\epsilon)$_

2 if  _$|A| <k$_ then

3 $q_{\text{local}},p_{\text{potential}}\leftarrow$ Propose new local tree
location

4 if  _$p_{\text{potential}} >\delta_{\text{threshold}}$_ then

5 Join $q_{\text{local}}$ to all $T\in\mathcal{T}$ within $\epsilon$-distance

6 if  _Not joined to existing tree_ then

7 $T\leftarrow G(V=\\{q_{\text{local}}\\},E=\emptyset)$

8 $\mathcal{T}\leftarrow\mathcal{T}\cup\\{T\\}$

9 $A\leftarrow$ Add new local sampler $a$ to $A$

10

11

12

return _$\mathcal{T},A$_

$\triangleright$ new local tree is added

13

Algorithm 2 Propose new local tree

####  IV-2 Joining of Local Trees

Local trees that are connectable are guaranteed to be eventually connected.

######  Theorem 2 (see [22])

Let $C_{\text{free}}^{\prime}\subseteq C_{\text{free}}$ be a connected free
space. Select $k$ configurations $q_{1},...,q_{k}$ randomly from
$C_{\text{free}}^{\prime}$ including $q_{\text{init}}$ and
$q_{\text{target}}$. Set $q_{1},...,q_{k}$ as root nodes and extend $k$ trees
from these points. Let $n$ be the total number of nodes that all these trees
extended, and $\gamma\in\mathbb{R}$ be a real number in $(0,1]$. If $n$
satisfies

$\begin{split}n\geq\,&k(\alpha\beta\epsilon)^{-1}\ln[4(1-\epsilon)]\ln\\{3\ln[2k^{2}(1-\epsilon)]/\gamma\beta\\}\\\
&+k\mu(C_{\text{free}})/\mu(C)\ln(3k^{2}/2\gamma)\end{split}$ (4)

then the probability that each pair of these $k$ trees can be attached
successfully is at least $1-\gamma$.

###### Proof:

Due to space constrains, see [22] for full proof. ∎

######  Theorem 3 (Joining of local trees)

Let $T_{i},T_{j}\in\mathcal{T}$ be instances of local trees in
$C_{\text{free}}^{\prime}$ where $T_{i}\neq T_{j}$. If there exists a feasible
trajectory to connect $T_{i}$ to $T_{j}$, it is guaranteed that both trees
will joined as a single tree as $t\to\infty$.

###### Proof:

Theorem 1 states that the number of local trees is finite. Hence, in the
limiting case, all local trees satisfy the real-valued bound given by Theorem
2. ∎

(a) Intel lab

(b) Maze

(c) 4D rover arm

(d) 6D manipulator

Figure 3: Environments. (3(a)) Intel lab map data and with a point mass robot
as baseline. (3(b)) Cluttered maze environment with extremely limited
visibility. (3(c)) Rover arm with two spatial dimensionality and two
rotational joints. (3(d)) Manipulator with six rotational joints for an object
pickup task.

####  IV-3 Probabilistic Completeness

rrf* attains probabilistic completeness as its number of uniform random
samples approaches infinity.

######  Theorem 4 (Infinite random sampling)

Let $n_{i,t}$ denotes the number of uniformly random configurations used for
creating new node in rrf* at time $t$. The number $n_{i,t}$ always increases
without bound, i.e., as $t\to\infty$, $n_{i,t}\to\infty$.

###### Proof:

As stated in theorem 1, as $t\to\infty$ there will be no new local trees being
created. Therefore, the behaviour of rrf* sampling will be dominated by Alg. 1
Alg. 1 to Alg. 1 when all local trees in $\mathcal{T}$ are joined to
$T_{\text{init}}$. Therefore, rrf* will be reduced to use SampleFree to
samples uniformly in $C_{\text{free}}$. ∎

###### Theorem 5

Let $n^{\textsc{rrf}\textsuperscript{*}}_{t}$ and
$n^{\textsc{rrt}\textsuperscript{*}}_{t}$ be the number of uniformly random
configurations sampled at time $t$ for rrf* and rrt* respectively. There
exists a constant $\phi\in\mathbb{R}$ such that
$\lim_{t\to\infty}\mathbb{E}[n^{\textsc{rrf}\textsuperscript{*}}_{t}/n^{\textsc{rrt}\textsuperscript{*}}_{t}]\leq\phi.$

###### Proof:

There exist two different sampling schemes being employed in rrf*. The (i)
_uniform random sampling_ in Alg. 1 Alg. 1, and (ii) _exploitative local
sampling_ in Alg. 1. The total number of exploitative local sampling
$n_{\text{local-samp}}$ by MCMC in (ii) is the summation of each local
sampler’s sampled configurations $n_{\text{local-
samp}}=\sum_{i=1}^{|\mathcal{T}|}n_{i,t}$. Deriving from Theorem 1, since the
number of local trees in the lifetime of rrf* is bounded by a constant, the
number of local sampling $n_{\text{local-samp}}$ will also be bounded by a
constant. On the other hand, Theorem 4 states that the number of uniformly
sampled configurations in (i) is unbounded and approaches infinity. Therefore,
the ratio of the total number of uniformly random configurations between rrf*
and rrt* will be bounded by at most a constant as the behaviour of rrf* will
converge to rrt* as $t\to\infty$. ∎

With Theorems 4 and 5, the _probabilistic completeness_ of rrf* is immediate.

######  Theorem 6 (Probabilistic Completeness)

rrf* inherits the same probabilistic completeness of rrt*, i.e.,
$\lim_{i\to\infty}\mathbb{P}(\\{\sigma(i)\cap
q_{\text{target}}\neq\emptyset\\})=1$.

####  IV-4 Asymptotic optimality planning

######  Theorem 7 (Asymptotic optimality)

Let $\sigma^{*}_{t}$ be rrf*’s solution at time $t$, and $c^{*}$ be the
minimal cost for problem 1. If a solution exists, then the cost of
$\sigma^{*}_{t}$ will converge to the optimal cost almost-surely. That is,
$\mathbb{P}\left(\left\\{\lim_{t\to\infty}c(\sigma^{*}_{t})=c^{*}\right\\}\right)=1.$

###### Proof:

From Theorem 3, all local trees in the same $C_{\text{free}}^{\prime}$ will
converge to a single tree. According to Theorem 4 there will be infinite
sampling available to improve that tree. Together with adequate rewiring
procedure at Alg. 1 Alg. 1 (see [7]), it is guaranteed that the solution will
converge to the optimal solution as $t\to\infty$. ∎

##  V Experimental Results

(a) Intel lab

(b) Maze

(c) Rover arm

(d) Manipulator

Figure 4:  Top to bottom are _time (seconds)_ , _cost_ , _invalid connections_
and _invalid obstacles_ against number of nodes. Each experiment is repeated
10 times, with each solid line and shaded region representing the mean and
$95\%$ confidence interval. _Invalid obstacles_ and _invalid connections_
refers to the number of invalid samples due to $q_{\text{rand}}\in
C_{\text{obs}}$ or intermediate collision, respectively. For the _cost_
metric, the line appears at the first instance that a solution is found.

(a) Sequence of trajectory executed by JACO arm

(b) Trajectory trail

Figure 5: Evaluation of rrf*’s algorithmic robustness on a JACO robotic arm.
(5(a)) Sequence of trajectory execution in a cluttered environment. (5(b))
Solution trajectory trail after planning with a time budget of five seconds.

We evaluate the performance of rrf* in various environments with a range of
degree of complexity, as shown in Fig. 3. _Intel lab_ and _maze_ are with a
point mass robot in $\mathbb{R}^{2}$ to plan a trajectory from some initial
configuration to a target configuration. _Rover’s arm_ also has a two-
dimensional spatial location, but with two additional rotational joints that
denote the rotational angles of the robot arm. The rover arm needs to navigate
while rotating its arm to avoid collisions. _Manipulator_ environment is a 6
dof TX90 robotic manipulator that operates in a 3D cluttered environment; with
a task to move the manipulator between two cupboards while holding a cup. The
environment contains many structures that restrict the manipulator’s movement.
Qualitatively, we evaluate rrf*’s algorithmic robustness by testing the
resulting trajectory in a real-world JACO arm (Fig. 5). In terms of
environment complexity, _maze_ (Fig. 3(b)) and _manipulator_ (Fig. 3(d)) are
highly cluttered due to the limited visibility and abundance of narrow
passages; whereas the other two environments contain more free space with
multiple homotopy classes of solution trajectories.

rrf* is evaluated against rrt* [7], bi-rrt∗ [21], rrdt∗ [4], and Informed rrt*
[17], implemented under the same planning framework in Python. Overall, rrf*
performs consistently across all environments regardless of its complexity.
rrf*’s performance is similar to rrdt∗ because both methods are using multiple
local trees to explore _C-space_. However, rrf* adaptively creates new local
trees only in regions deemed bottlenecks and coupled with a MAB selection that
balances choosing rooted trees or local trees that are promising. Therefore,
similar to bi-rrt∗ it inherits the benefit of obtaining fast solution in open
areas (e.g. see _cost_ metric in Figs. 4(a) and 4(c)), and similar to rrdt∗ it
obtains fast solution in cluttered areas (see _cost_ in Figs. 4(b) and 4(d)).
The runtime savings of rrf* comes from the reduced number of collision checks
by reducing invalid samples. Since both rrf* and rrdt∗ uses multiple trees to
explore _C-space_ , their metric of invalid connections and invalid obstacles
(bottom two rows of Fig. 4) are often the lowest among all others. However,
unlike rrdt∗, rrf* is adaptive to the current workspace with a heuristic to
only deploy local trees in highly constrained (section III-D). Therefore, the
performance of rrf* can be seen as a hybrid between traditional motion planner
and multi-trees planner; the same reason allows rrf* to quickly converges its
solution when compared to rrdt∗ (_cost_ in Fig. 4(d)).

##  VI Conclusion

We present rrf*, a generalised adaptive multi-tree approach for asymptotic
optimal motion planning. rrf* uses multiple local trees to adaptively utilise
a beneficial local sampling strategy when constrained regions are discovered.
Bayesian local sampling in a cluttered area allows rrf* to exploit local
structures and effectively tackle narrow passages. rrf* adaptively deploys
local sampling in restricted regions when necessary, which overcome the issue
of multi-trees approach having slow initial time in open spaces.

## References

  * [1] Lydia E. Kavraki, Mihail N. Kolountzakis and J.-C. Latombe  “Analysis of Probabilistic Roadmaps for Path Planning”  In _Proceedings of IEEE International Conference on Robotics and Automation_ , 1996  DOI: 10/d66p3t
  * [2] Mohamed Elbanhawi and Milan Simic  “Sampling-Based Robot Motion Planning: A Review”  In _IEEE Access_ 2, 2014, pp. 56–77  DOI: 10/gdkx6g
  * [3] David Hsu et al.  “On Finding Narrow Passages with Probabilistic Roadmap Planners”  In _Robotics: The Algorithmic Perspective: 1998 Workshop on the Algorithmic Foundations of Robotics_ , 1998
  * [4] Tin Lai, Fabio Ramos and Gilad Francis  “Balancing Global Exploration and Local-Connectivity Exploitation with Rapidly-Exploring Random Disjointed-Trees”  In _Proceedings of The International Conference on Robotics and Automation_ , 2019
  * [5] Lydia E. Kavraki, Petr Svestka, J.. Latombe and Mark H. Overmars  “Probabilistic Roadmaps for Path Planning in High-Dimensional Configuration Spaces”  In _IEEE Trans. Robot. Autom._ 12.4, 1996, pp. 566–580  DOI: 10/fsgth3
  * [6] Steven M. LaValle  “Rapidly-Exploring Random Trees: A New Tool for Path Planning”  In _TR 98-11 Comput. Sci. Dept Iowa State Univ._ , 1998
  * [7] S. Karaman and E. Frazzoli  “Incremental Sampling-Based Algorithms for Optimal Motion Planning”  In _Proceedings of Robotics: Science and Systems_ , 2010  DOI: 10.15607/RSS.2010.VI.034
  * [8] Sertac Karaman and Emilio Frazzoli  “Sampling-Based Algorithms for Optimal Motion Planning”  In _Int. J. Robot. Res._ 30.7, 2011, pp. 846–894  DOI: 10/c2wgw5
  * [9] Anna Yershova, Léonard Jaillet, Thierry Siméon and Steven M. LaValle  “Dynamic-Domain RRTs: Efficient Exploration by Controlling the Sampling Domain”  In _Proceedings of IEEE International Conference on Robotics and Automation_ , 2005
  * [10] Steven A. Wilmarth, Nancy M. Amato and Peter F. Stiller  “MAPRM: A Probabilistic Roadmap Planner with Sampling on the Medial Axis of the Free Space”  In _Proceedings of IEEE International Conference on Robotics and Automation_ , 1999
  * [11] Andreas Orthey and Marc Toussaint  “Rapidly-Exploring Quotient-Space Trees: Motion Planning Using Sequential Simplifications”, 2019  arXiv: http://arxiv.org/abs/1906.01350
  * [12] Liangjun Zhang and Dinesh Manocha  “An Efficient Retraction-Based RRT Planner”  In _Proceedings of IEEE International Conference on Robotics and Automation_ , 2008
  * [13] Junghwan Lee, OSung Kwon, Liangjun Zhang and Sung-eui Yoon  “SR-RRT: Selective Retraction-Based RRT Planner”  In _Proceedings of IEEE International Conference on Robotics and Automation_ , 2012
  * [14] David Hsu, Tingting Jiang, John Reif and Zheng Sun  “The Bridge Test for Sampling Narrow Passages with Probabilistic Roadmap Planners”  In _Proceedings of IEEE International Conference on Robotics and Automation_ , 2003
  * [15] Zheng Sun, D. Hsu, Tingting Jiang and H. Kurniawati  “Narrow Passage Sampling for Probabilistic Roadmap Planning”  In _IEEE Trans. Robot._ 21.6, 2005, pp. 1105–1115  DOI: 10/bh6v9h
  * [16] Wei Wang, Xin Xu, Yan Li and Jinze Song  “Triple RRTs: An Effective Method for Path Planning in Narrow Passages”  In _Adv. Robot._ 24.7, 2010, pp. 943  DOI: 10/fv9c9p
  * [17] Jonathan D. Gammell, Timothy D. Barfoot and Siddhartha S. Srinivasa  “Informed Sampling for Asymptotically Optimal Path Planning”  In _IEEE Trans. Robot._ 34.4, 2018, pp. 966–984  DOI: 10/gd5sp3
  * [18] Tin Lai and Fabio Ramos  “Learning to Plan Optimally with Flow-Based Motion Planner”, 2020  arXiv: http://arxiv.org/abs/2010.11323
  * [19] Brian Ichter, James Harrison and Marco Pavone  “Learning Sampling Distributions for Robot Motion Planning”  In _2018 IEEE International Conference on Robotics and Automation (ICRA)_ , 2018  DOI: 10/gf7t7z
  * [20] Guillaume Sartoretti et al.  “PRIMAL: Pathfinding via Reinforcement and Imitation Multi-Agent Learning”  In _IEEE Robot. Autom. Lett._ 4.3 IEEE, 2019, pp. 2378–2385  DOI: 10/ggzj7h
  * [21] James J. Kuffner and Steven M. LaValle  “RRT-Connect: An Efficient Approach to Single-Query Path Planning”  In _Proceedings of IEEE International Conference on Robotics and Automation_ , 2000
  * [22] Wei Wang, Lei Zuo and Xin Xu  “A Learning-Based Multi-RRT Approach for Robot Path Planning in Narrow Passages”  In _J. Intell. Robot. Syst._ 90.1-2, 2018, pp. 81–100  DOI: 10/gc7cqd
  * [23] Morten Strandberg  “Augmenting RRT-Planners with Local Trees”  In _Proceedings of IEEE International Conference on Robotics and Automation_ , 2004
  * [24] Weifeng Chen  “Motion Planning with Monte Carlo Random Walks”, 2015
  * [25] Hootan Nakhost, Jörg Hoffmann and Martin Müller  “Resource-Constrained Planning: A Monte Carlo Random Walk Approach.”  In _International Conference on Automated Planning and Scheduling (ICAP)_ , 2012
  * [26] Ibrahim Al-Bluwi, Thierry Siméon and Juan Cortés  “Motion Planning Algorithms for Molecular Simulations: A Survey”  In _Comput. Sci. Rev._ 6.4, 2012, pp. 125–143  DOI: 10/gdkx6f
  * [27] Tin Lai, Philippe Morere, Fabio Ramos and Gilad Francis  “Bayesian Local Sampling-Based Planning”  In _IEEE Robot. Autom. Lett._ 5.2 IEEE, 2020, pp. 1954–1961  DOI: 10/gg2n24
  * [28] Nicholas I. Fisher  “Statistical Analysis of Circular Data”  Cambridge University Press, 1995
  * [29] David JC MacKay  “Introduction to Gaussian Processes”  In _NATO ASI Ser. F Comput. Syst. Sci._ 168, 1998, pp. 133–166
  * [30] Deepayan Chakrabarti, Ravi Kumar, Filip Radlinski and Eli Upfal  “Mortal Multi-Armed Bandits”  In _Advances in Neural Information Processing Systems_ , 2009
  * [31] Omar Besbes, Yonatan Gur and Assaf Zeevi  “Stochastic Multi-Armed-Bandit Problem with Non-Stationary Rewards”  In _Advances in Neural Information Processing Systems_ , 2014