# Co-existence of charge density wave and anti-ferromagnetic coupling in the
spin-chain compound Ba6Cr2S10

Jianhua Zhu1,2 These authors contributed equally to this work.
<EMAIL_ADDRESS>Jianfeng Zhang3,4 These authors contributed equally to this
work.  Yilin Zhang1 Devashibhai Adroja5,6 Huancheng Yang4 Xiancheng Wang3
Changqing Jin3 Ji Chen1,7,8<EMAIL_ADDRESS>Wei Wu2<EMAIL_ADDRESS>1School of Physics, Peking University, Chengfu Road 209, Haidian, Beijing
100871, China  2UCL Department of Physics and Astronomy and London Centre for
Nanotechnology, University College London, Gower Street, London WC1E 6BT
3Beijing National Laboratory for Condensed Matter Physics, Institute of
Physics, Chinese Academy of Sciences, Beijing 100190, China  4Key Laboratory
of Quantum State Construction and Manipulation (Ministry of Education), Renmin
University of China, Beijing, 100872, China  5ISIS Neutron and Muon Facility,
STFC, Rutherford Appleton Laboratory, Chilton, Didcot, Oxford, OX11 0QX,
United Kingdom  6Highly Correlated Matter Research Group, Physics Department,
University of Johannesburg, Auckland Park 2006, South Africa
7Interdisciplinary Institute of Light-Element Quantum Materials
and Research Center for Light-Element Advanced Materials, Peking University,
Beijing 100871, P. R. China  8Frontiers Science Center for Nano-
Optoelectronics, Peking University, Beijing 100871, P. R. China

###### Abstract

Here we have performed detailed first principles calculations for the
electronic structure and magnetic properties of Ba6Cr2S10 to study the origin
of the anti-ferromagnetic exchange interaction between spins on Cr ions for
the spin-chain compound Ba6Cr2S10 synthesised recently. Most importantly, we
have found the co-existence of a charge density wave phase along one line and
an anti-ferromagnetic spin chain along another. The dimerization of sulfur
atoms loosely bonded with Ba atoms drives the system into an insulating state
owing to the formation of charge density wave. Meanwhile, the small size of
the effective Hubbard $U$ parameter ($\sim 0.5$ eV) due to electrostatic
screening mainly accounts for the anti-ferromagnetic ground state. This co-
existence equips us with a platform to tune the charge and spin degrees of
freedom independently. Moreover, there exists a next-nearest-neighbouring
anti-ferromagnetic interaction along the chain, which could bring forward spin
frustration and hence quantum spin liquid.

##  I Introduction

In one dimension (1D), quantum fluctuations become more important as compared
with the thermal ones at sufficiently low temperature and can be manifested in
quantum spin liquid[1], quantum tunnelling [2], fractional edge states [3],
and topological order [4, 5]. Quasi-1D spin chains can provide a fascinating
physical platform not only to the study of low-dimensional physics but also
long-range quantum entanglement [6, 7]. One-dimensional Majorana zero-mode
bound states share the same central charge of $\frac{1}{2}$ with that in the
1D Ising model with transverse magnetic field, as suggested by the conformal
field theory [8, 9]. One of the most interesting temperature regions is
probably where the three-dimensional ordering is not yet established but the
temperature is lower than the Curie intercept $\theta_{p}$ originating from
the exchange interaction within the spin chains, provided intra-chain coupling
is much stronger than inter-chain, which could lead to quantum spin liquid
[1]. Moreover, magnetic toroidal moments - an interesting dipole moment that
violates both the spatial and time inversion symmetries can be found in
ordered spin systems, for example in 1D [10, 12], orbital loop current [13,
14], and wheel-shaped molecules such as Dy6 [15, 16]. Quasi-1D anti-
ferromagnetic (AFM) dimerized spin chains can be used to realize polar
toroidal moments in solid state [10, 11, 12]. 1D spin chains can also find
applications in quantum information processing; quantum communications through
1D AFM spin chains have been proposed to realise quantum state transfer
between the chain ends [17]. Molecular single-chain magnets can have many
potential applications in spintronics and magnetism [18].

Recently the compounds consisting of spin chains, either organic or inorganic,
have attracted much attention for magnetism and spintronics. Organic spin-
chain compounds, in which spin chains weakly interact with each other, can
form in phthalocyanine-based molecular chains such as cobalt phthalocyanines
[19, 20, 21, 22, 23, 24, 25, 26, 27]. More broadly speaking, organic single
chain magnets, which can explore chemical synthesis and different building
blocks for magnetic spin units, have comparable functionalities to single
molecule magnets, thus pointing to many potential applications in spintronics
and quantum computing [18]. There are many molecular material candidates for
single chain magnets, such as [Mn(TPP)O2PPhH]$\cdot$H2O (TPP = meso-
tetraphenylporphyrin), apart from the phthalocyanine-based spin chains [28].
For inorganic compounds, the AMX3 and B3MM’O6 (A = Cs/Rb, B = alkaline-earth
metal, M/M’ = transition metals, X = halides) compounds form large families of
spin chain compounds, which have exhibited interesting low-dimensional
magnetic behaviour, as observed in elastic or inelastic neutron scattering
experiments [29, 30, 31]. CsCoBr3 and Ca3Co2O6 consist of strongly coupled
Ising chains, which are vertical to the triangular lattice plane [32]. The
spins in the chain in CsCoBr3 are anti-ferromagnetically coupled, while those
in Ca3Co3O6 are ferromagnetically arranged [32]. Especially the B3MM’O6
compound family has complex magnetic structures, multiple exchange
interactions between spins on the transition-metal ions. In some compounds,
$4d$/$5d$ orbitals will be involved, which implies that the spin-orbit
interaction will play an important role in magnetic properties such as spin
anisotropy [31]. For B3MM’O6 compounds, Sr3ZnRhO6[33], Sr3CuIrO6[34],
Sr3CuRhO6[35], Ca3CoRhO6[36], and Sr3NiIrO6[31] have been extensively studied,
showing interesting magnetic properties such as magnetisation jumps and
anisotropic exchange interactions. Furthermore, when there are two different
types of magnetic atoms in the chain ($3d/4d$ or $3d/5d$), the system exhibits
hidden magnetic transition well below the long range ordering and the origin
of this is still an open debate [37].

Hf5Sn3Cu-anti type ternary compounds A3BX5 (A = alkali earth metal, B =
transition metal and X = chalcogen) are a typical spin chain compound family
that also are candidates for one-dimensional ferrotoidic chains [11, 12].
Recently, we have also studied the magnetism in the ferromagnet La3MnAs5, and
found that this compound consists of spin chains coupled via itinerant
electrons [38]. Here we report the theoretical studies from first principles
for a newly synthesized spin-chain compound Ba6Cr2S10 (BCS) under high-
pressure and high-temperature conditions. BCS has hexagonal lattice structure
in which the spin chain consisting of Cr atoms is along the $c$-axis, as shown
in Fig.1(a). In terms of chain structures, BCS has face-sharing octahedrons
formed by sulfur atoms, which is similar to the AMX3 and B3MM’O6. Our
calculations show that the dimerisation along the chain induced mainly by the
octahedrons formed by the S atoms will lead to anti-ferromagnetic ground state
and thus ferro-toroidic ground state. In addition, our calculations show an
both charge density wave and orbital ordering on Cr atoms along the chain due
to the dimerized peculiar face-sharing octahedral structure. The small size of
the Hubbard-$U$ parameter suggests a significant screening effect from the
surrounding atoms. The remaining discussion falls into three sections. In §II,
we introduce the computational methods. In §III, we present our results and
discuss them. In §IV, we draw some general conclusions.

Figure 1: (Colour online.) (a) The crystal structure of BCS is shown. Ba is in
green, Cr is in blue, and S is in yellow. Cr atoms, bonded by S atoms, form
octahedron-face-sharing chains along the $c$-axis (illustrated by a blue
line). S1 and S2 label the sulfur atoms for those forming ligands with Cr and
those loosely bonded with Ba (lablled by $\times$; the red line illustrates
the S chain), respectively. We have also provided the atomic charges for the S
atoms loosely bonded with Ba. The nearest-neighboring exchange interactions
$J_{\text{NN}}^{1}$ and $J_{\text{NN}}^{2}$, and the next-nearest-neighboring
exchange interaction $J_{\text{NNN}}$ have been indicated as well. (b) Spin
densities on Cr suggest the orbital ordering on Cr along the chain. Due to the
zig-zag ligand, the Cr orbitals will alternate along the $c-$axis.

##  II Methods

First-principles density functional theory (DFT) calculations have been
performed to study the electronic structure and magnetic properties of BCS
using the projector augmented wave (PAW) method [39] implemented in the VASP
package [40, 41]. The standard generalised-gradient approximation for the
exchange-correlation functional - Perdew-Burke-Ernzerhof (PBE) - has been
chosen for all the calculations [42]. The kinetic energy cutoff of the plane-
wave basis was set to be 350 eV. A $8\times 8\times 6$ $k$-point mesh was used
for the Brillouin zone (BZ) sampling. The Fermi level was broadened by the
Gaussian smearing method with a width of 0.05 eV. The self-consisten-field
(SCF) converging process is accelerated by using Broyden’s second method [43].
For the structure without dimerisation, we have adopted the crystal structure
of La3MnAs5 by replacing La, Mn, As using Ba, Cr, and S, and then optimized
the crystal structure [38]. The band structure was plotted as the high-
symmetry points in the first Brilloin zone of a hexagonal lattice, i.e.,
$\Gamma(0,0,0)\rightarrow M(\frac{1}{2},0,0)\rightarrow
K(\frac{2}{3},\frac{1}{3},0)\rightarrow\Gamma(0,0,0)\rightarrow
A(0,0,\frac{1}{2})\rightarrow L(\frac{1}{2},0,\frac{1}{2})\rightarrow
H(\frac{2}{3},\frac{1}{3},\frac{1}{2})\rightarrow A(0,0,\frac{1}{2})$.

The symmetry group for BCS is $P\overline{6}2c$. The experimental lattice
parameters are $a=b=9.1371\mathrm{\AA}$, $c=12.3175\mathrm{\AA}$,
$\alpha=\beta=90^{\circ}$, and $\gamma=120^{\circ}$. In our calculations, the
lattice constants and internal atomic positions were allowed to relax until
all the forces on atoms were smaller than 0.01 eV/Å. The optimized lattice
constants are: $a_{o}=b_{o}=9.27\mathrm{\AA}$ and $c_{o}=12.44\mathrm{\AA}$,
which agree well with the experimental measurements [12]. Notice that there
are two types of S atoms including (i) ligands for Cr (S1) and (ii) loosely
bonded with Ba forming another chain (S2), as shown in Fig.1(a). We have also
found the S atoms loosely bonded with Ba are non-uniformly dimerized, as shown
in Fig.1(a). We have computed the intra-chain nearest-neighbouring (NN) and
next-nearest-neighbouring (NNN) exchange interactions. Notice that the NN
exchange interactions are different for the neighbouring exchange
interactions; we distinguished them by $J_{\text{NN}}^{1}$ and
$J_{\text{NN}}^{2}$ as labeled in Fig.1(a). The $U$-parameter has also been
added (DFT+U) to work out the dependence of exchange interactions on $U$. A
set of values of $U$ from $0$ to $2$ eV with increments of 0.5 eV were used
for the DFT+U calculations. The spin-orbit interaction (SOI) was included into
the spin-polarized calculations to understand the non-collinear magnetic
configuration. In all our calculations we have kept the spin in the $ab$
plane. To validate our DFT+U+SOI results, we have also performed hybrid-
exchange DFT calculations using HSE06 functional, implemented in VASP [44].

##  III Results and discussion

The computed band structures for BCS with dimerisation and without are shown
in Fig.2 (a) and (b), respectively. The optimized dimerisation for Cr was only
$0.005\ \mathrm{\AA}$ in our calculations. By contrast, the dimerized S2-type
atoms play a dominant role for a magnetic insulating state. In Fig.2(b), for
the BCS structure without dimerisation, we can see a significant band
dispersion originating from sulfur atoms crossing the band gap, leading to a
metallic state. The band dispersion across the band gap is along
$\Gamma(0,0,0)\rightarrow A(0,0,\frac{1}{2})$ \- the chain direction, which is
consistent with the dimerization that is also along the $c-$axis. The
dimerisation of S2 atoms will open up a band gap - a typical characteristics
for the Peierls transition to a charge density wave (CDW) phase in one
dimension [45, 46], which is closely related to quantum fluid state in 1D.
This CDW phase has been illustrated clearly by the atomic charge labeled in
Fig.1(a). The atomic charges for the S2 atoms are 3.74$e$, 3.74$e$, 3.66$e$,
and 3.66$e$, respectively. This unequal charges are due to the nonuniform
dimerizations; the distance between the top (bottom) two S atoms is 2.61
(2.23) $\AA$. The dimerization also brings forward localized spins that can be
seen clearly in Fig.1(b), suggesting the orbital ordering on Cr along the
chain.

Figure 2: (Colour online.) A comparison between the band structures of the
crystal structures with dimerisation and without. We can clearly see the clear
Peierls transition to a CDW, which is due to the S ligands rather than Cr
atoms. The calculations here were performed without $U$.

We have also computed the spin-polarised projected band structure for BCS with
dimerisation, as shown in Fig.3. The spin-up band structures are plotted in
(a), while the spin-down band structures are plotted in (b). For (c) and (d),
we have contributions from both spin-up and spin-down for S1 and S2
projections, respectively. The band structure projected onto the Cr atoms for
spin up is shown in (a), in which the dominant projections are at
$E-E_{F}\sim-0.5$ eV, i.e., 0.5 eV below the Fermi surface. The projections to
the S1 and S2 types of atoms (Fig.3c and d) labelled in Fig.1(a) suggest that
S1 and S2 atoms contribute to the same energy range as Cr atoms, thus leading
to strong hybridisation between Cr and S1-type atoms.

Figure 3: (Colour online.) The spin-polarised band structures projected to Cr
and S, which clearly dominates the bands near the Fermi energy.

We found that the magnetic anisotropy energies (MAE) calculated here as the
total-energy difference between the spin configurations along $c$\- and
$a$-axes. The energy difference computed here in VASP is comparable to 0.1
meV, which is beyond the limit of the general accuracy for the DFT
calculations by using VASP. We therefore leave this for further investigation.
We speculate that the high accuracy of VASP could lead to a small energy
difference. In addition, this nearly degenerate magnetic ground state ($<1$
meV) could lead to interesting physics through quantum fluctuations between
these two spin configurations.

Table 1: Exchange interactions,band gaps and $d$-orbital levels near the Fermi energy as a function of Hubbard-$U$ parameters.  $U$ (eV) | 0 | 0.5 | 1.0 | 1.5 | 2.0
---|---|---|---|---|---
$J_{\mathrm{NN}}^{1}$ (meV) | 14.5 | 11.7 | 9.4 | 7.5 | 5.9
$J_{\mathrm{NN}}^{2}$ (meV) | 17.0 | 14.0 | 11.5 | 9.3 | 7.6
$J_{\mathrm{NNN}}$ (meV) | 0.7 | 0.5 | 0.2 | 0.1 | 0
Band gap (eV) | 1.00 | 1.04 | 1.06 | 1.08 | 1.09
$d$-orbital lower levels (eV) | -0.4 | -0.6 | -0.7 | -0.9 | -1.1
$d$-orbital upper levels (eV) | 1.3 | 1.3 | 1.3 | 1.3 | 1.3
$d$-orbital gap (eV) | 1.7 | 1.9 | 2.0 | 2.2 | 2.4

We have also performed the DFT+U+SOI calculations implemented in VASP to study
the dependence of exchange interactions between the spins on the Cr ions on
the on-site Coulomb $U$ parameter. Here we have adopted a spin Hamiltonian as
follows,

$\displaystyle\hat{H}$ $\displaystyle=$ $\displaystyle\sum_{\langle
i,j\rangle\in\mathrm{NN,1}}J^{1}_{\mathrm{NN}}\hat{s}_{i}\cdot\hat{s}_{j}+\sum_{\langle
i,j\rangle\in\mathrm{NN,2}}J^{2}_{\mathrm{NN}}\hat{s}_{i}\cdot\hat{s}_{j}$
$\displaystyle+\sum_{\langle
i,j\rangle\in\mathrm{NNN}}J_{\mathrm{NNN}}\hat{s}_{i}\cdot\hat{s}_{j}$

Positive exchange interaction implies AFM coupling, where negative for FM
couplings. To extract the exchange interactions in eq.III, we have performed
the total energy calculations for four spin configurations on Cr atoms,
including $|1\rangle=|\uparrow,\uparrow,\uparrow,\uparrow\rangle$,
$|2\rangle=|\uparrow,\downarrow,\uparrow,\downarrow\rangle$,
$|3\rangle=|\uparrow,\downarrow,\downarrow,\uparrow\rangle$, and
$|4\rangle=|\uparrow,\uparrow,\downarrow,\uparrow\rangle$. Our calculations
confirm that the state $|2\rangle$ is the ground state, which is consistent
with the experimentally determined magnetic structure and calculations for BCS
[12]. The exchange interactions in eq.III can then be computed according to

$\displaystyle J_{\text{NN}}^{1}$ $\displaystyle=-\frac{\Delta
E_{31}}{4S^{2}}-2J_{\text{NNN}}$ (2) $\displaystyle J_{\text{NN}}^{2}$
$\displaystyle=-\frac{\Delta E_{21}}{4S^{2}}-J_{\text{NN}}^{1}$ $\displaystyle
J_{\text{NNN}}$ $\displaystyle=\frac{\Delta E_{21}}{8S^{2}}-\frac{\Delta
E_{41}}{4S^{2}}$

Figure 4: (Colour online.) We have computed the bare on-site Coulomb
interaction $U_{\text{bare}}$ by using the linear response of the electron
populations on $d$-orbitals as shown in the figure. The SCF (NSCF)
calculations are plotted in red (blue). The gradients of the lines correspond
to the charge susceptibilities.

.

Figure 5: (Colour online.) The PDOS projected onto Ba (black), Cr (red), and S
(blue) is shown. We can see the significant overlaps between Cr and S near the
Fermi energy, suggesting strong bondings between them. A further detailed
check at the Fermi energy suggests S is dominant.

.

All the computed band gaps ($\sim 1$ eV) are larger than the experimental
observed ($0.559$ \- $0.843$ eV) as shown in Table.1. This discrepancy could
be due to a few aspects. The functional used could overestimate the
dimerization during the geometry optimization process. The accuracy of the
experimental band gap could be affected by defects. We can also see the very
weak dependence of the band gap on the $U$-parameter, suggesting the band gap
is dominated by dimerized S1 atoms and associated electron hopping strength.
Moreover, based on the comparison of band gap, we could not find the optimal
$U$ parameter through band-gap calculations. Moreover, we have also computed
the projected density of states (PDOS) for all the atomic species, as shown in
Fig.4. We have found that the contributions from S atoms are dominant at the
Fermi energy. The weak dependence of band gap on $U$ togehther with the PDOS
suggests sulfur contributions are dominant over the Fermi energy and the band
gap, which is consistent with the picture in which sulfur dimerization induces
CDW.

The calculated exchange interactions were tabulated in Table.1. We can see
that the intra-chain exchange interactions will decreases as $U$ increases,
which implies the exchange mechanism could be dominated by super-exchange
($\propto\frac{1}{U}$). The NN and NNN exchange interactions along the chain
are AFM, which suggests a weak spin frustration in one dimension. Due to the
strong quantum fluctuations in 1D, this could result in quantum spin liquid.
On the other hand, we can also derive the experimental intra-chain coupling
from the magnetic measurement of $\theta_{p}$ = -714 K [12] by using the mean-
field expression for
$\theta_{p}=-\frac{2S(S+1)}{3}(J_{\text{NN}}^{1}+J_{\text{NN}}^{2}-2J_{\text{NNN}})$
[48, 47] with $S=\frac{3}{2}$. Based on this mean-field approach, we have
found the optimal effective Hubbard-$U$ parameter ($U_{\text{opt}}$) is $\sim
0.5$ eV. In the mean time, we have also computed the bare $U$ parameter
($U_{\text{bare}}$) by using the linear-response method described in Ref.[49],
i.e., $U_{\text{bare}}=\frac{1}{\chi}-\frac{1}{\chi_{0}}$. Here
$\chi=\frac{dQ}{dV}$ is the SCF charge response to the change of electric
spherical potential applied to the $d-$orbitals. On the other hand, $\chi_{0}$
is the NSCF charge response. The gradients of the red ($\chi$) and blue (
$\chi_{0}$) lines in Fig.4 are $0.124$ and $\sim 0.451$, respectively, leading
to a $U_{\text{bare}}=5.8$ eV. We can see that $U_{\text{opt}}$ is one order
smaller than $U_{\text{bare}}$, which could be due to the screening effect
from the Coulomb interaction between sites ($V$) and Hund’s exchange
interaction $J_{\text{H}}$. The recent estimate suggested $J$ for Cr is
between $0.5$ and $0.93$ eV [50, 51]. An estimate of $V$ with a Cr-Cr distance
$\sim 3.1\ \AA$, which will lead to a Coulomb interaction
$\sim\frac{1}{6}\text{Hartree}\simeq 4.5$ eV. Therefore, $U_{\text{opt}}\simeq
U_{\text{eff}}=U_{\text{bare}}-V-J_{\text{H}}$, in which the effective Hubbard
$U$ results from the screening effect from inter-site Coulomb interaction and
Hund’s exchange. Our further calculations with $U=5.8$ eV show that the
ground-state magnetic structure will change to the ferromagnetic state
($|1\rangle$), which is inconsistent with the experimental observation [12].
Another theoretical work based on basis-independent constrained random-phase
approximation [52] has suggested the fully screened $U$-parameter for Cr due
to metallic elements is $\sim 1$ eV for Y(Sr)XO3 (X = transition metals),
further supporting the small size of $U_{\text{eff}}$ here if taking into
account the Hund’s exchange (in the order of 0.1 eV). In addition, we have
summarized the $d$-orbital levels in Table.1 and the gap between highest
occupied (lower) and the lowest unoccupied (upper) $d$-bands. This gap is also
rather weakly dependent on the $U$ parameter, suggesting the existence of
screening effect on $U$. This screening effect reduces the effective on-site
Coulomb interaction, strengthening the super-exchange interaction
($\propto\frac{1}{U_{\text{eff}}}$), thus leading to an AFM ground state. The
computed bandwidth (W) for the upper $d$-band is $\simeq 0.4$ eV, resulting in
a small ratio of $\frac{U}{W}\simeq 1.25$. Thus, owing to the small size of
$U$, BCS could be close to the boundary between correlated metal and Mott
insulator, in which there is rich physics [53] such as quantum spin liquid.
Our HSE06 DFT calculations further confirmed our DFT+U+SOI results from the
following three perspectives. First, the exchange interactions computed by
HSE06 is AFT with a magnitude of $33$ meV, consistent with the DFT+U+SOI
calculation. The overestimation of the exchange interaction is characteristic
for hybrid-exchange functional [54]. Secondly, based on the analysis of forces
on the S atoms along the S2 chain, we have found similar geometry formation of
the chain, thus also leading to a CDW along S2, which supports our DFT+U+SOI
calculations. Thirdly, the band gap computed using HSE06 is $\sim 0.6$ eV,
which agrees well with the measurement shown in the Appendix.

##  IV Conclusions

In summary, we have computed the electronic structure and magnetic properties
of the spin chain compound Ba6Cr2S10 based on DFT+U+SOI methods. Our
calculations suggest an electrostatic screening effect reduces $U$
significantly ($U\simeq 0.5$ eV), leading to an AFM ground state. The spin
densities on Cr atoms suggest an orbital ordering along the Cr chain. In
addition, the sulfur atoms loosely bonded with Ba play an important role in
the dimerisation, which leads to a CDW phase and an insulating ground state.
Ba6Cr2S10 could be close to the boundary between the Mott insulator and
correlated metal due to the small effective $U$. Overall we found the co-
existence of CDW and AFM along different chains, which is not only rare in the
literature, but also provides independent tunability over charge and spin
degrees of freedom. In addition, the AFM NNN exchange interaction could lead
to spin frustration and hence quantum spin liquid state.

## Data Availability

All the data that support the findings of this study are available from the
corresponding author upon reasonable request.

## References

  * [1] A. M. Tsvelik, Quantum Field Theory in Condensed Matter Physics, Cambridge University Press, 2010.
  * [2] S. Abel, N. Chancellor, and M. Spannowsky, Phys. Rev. D 103, 016008 (2021).
  * [3] S. Mishra, G. Catarina, F. Wu, R. Ortiz, D. Jacob, K. Eimre, J. Ma, C. A. Pignedoli, X. Feng, P. Ruffieux, J. Fernández-Rossier and R. Fasel, Nature 598, 287 (2021).
  * [4] F. D. M. Haldane, Phys. Rev. Lett. 50, 1153 (1983).
  * [5] X. Chen, Z. Gu, and X. Wen, Phys. Rev. B 82, 155138 (2010).
  * [6] X. Chen, Z. Gu, and X. Wen, Phys. Rev B 83, 035107 (2011).
  * [7] W. Wu and A. J. Fisher, arXiv: 2011.06899 (2020).
  * [8] P. Calabrese and J. Cardy, J. Stat. Mech. P06002 (2004).
  * [9] G. A. R. van Dalum, A. K. Mitchell, and L. Fritz, Phys. Rev. B 102, 041111(R) (2020).
  * [10] C. Ederer and N. A. Spaldin, Phys. Rev. B 76, 214404 (2007).
  * [11] J. Zhang, A. C. Komarek, M. Jin, X. C. Wang, Y. T. Jia, J. F. Zhao, W. M. Li, Z. W. Hu, W. Peng, X. Wang, L. H. Tjeng, Z. Deng, R. Z. Yu, S. M. Feng, S. J. Zhang, M. Liu, Y.-F. Yang, H.-j. Lin, C.-T. Chen, X. D. Li, J. L. Zhu, C. Q. Jin, Phys. Rev. Mater. 5, 054606 (2021).
  * [12] J. Zhang, X. Wang, L. Zhou, G. Liu, D. T. Adroja, I. Silva, F. Demmel, D. Khalyavin, J. Sannigrahi, H. S. Nair, L. Duan, J. Zhao, Z. Deng, R. Yu, X. Shen, R. Yu, H. Zhao, J. Zhao, Y. Long, Z. Hu, H. Lin, T. Chan, C. Chen, W. Wu, and C. Jin, Adv. Mater. 34, 2106728 (2022).
  * [13] C. M. Varma, C. M. (2006), Phys. Rev. B 73, 155113 (2006).
  * [14] B. Fauqué, Y. Sidis, V. Hinkov, S. Pailhés, C. T. Lin, X. Chaud, and P. Bourges, Phys. Rev. Lett. 96, 197001 (2006).
  * [15] L. Ungur, S. K. Langley, T. N. Hooper, B. Moubaraki, E. K. Brechin, K. S. Murray, L. F. Chibotaru, J. Am. Chem. Soc. 134, 18554 (2012).
  * [16] J. F. Wu, X. L. Li, M. Guo, L. Zhao, Y. Q. Zhang, J. K. Tang, Chem. Commun., 54, 1065 (2018).
  * [17] S. Bose, Contemporary Physics, 48, 13 (2007).
  * [18] L. Bogani, A. Vindigni, R. Sessolia and D. Gatteschi, J. Mater. Chem., 18, 4750 (2008).
  * [19] S. Heutz, C. Mitra, Wei Wu, A. J. Fisher, A. Kerridge, A. M. Stoneham, A. H. Harker, J. Gardener, H.-H. Tseng, T. S. Jones, C. Renner, and G. Aeppli, Adv. Mater. 19, 3618 (2007).
  * [20] W. Wu, A. Kerridge, A. H. Harker and A. J. Fisher, Phys. Rev. B 77, 184403 (2008).
  * [21] H. Wang, S. Mauthoor, S. Din, J. A. Gardener, R. Chang, M. Warner, G. Aeppli, D. W. McComb, M. P. Ryan, Wei Wu, A. J. Fisher, A. M. Stoneham and S. Heutz, ACS Nano 4, 3921 (2010).
  * [22] W. Wu, A. J. Fisher, and N. M. Harrison, Phys. Rev. B 84, 024427 (2011).
  * [23] M. Serri, W. Wu, L. Fleet, N. M. Harrison, C. W. Kay, A. J. Fisher, C. Hirjibehedin, G. Aeppli, S. Heutz, Nat. Commun. 5, 3079 (2014).
  * [24] W. Wu, N. M. Harrison, and A. J. Fisher, Phys. Rev. B 88, 024426 (2013).
  * [25] W. Wu, N. M. Harrison, and A. J. Fisher, Phys. Rev. B (Rap. Comm.) 88, 180404(R) (2013).
  * [26] W. Wu, A. J. Fisher, and N. M. Harrison, Phys. Rev. B 88, 224417 (2013).
  * [27] W. Wu, J. Phys. Cond. Matt. 26, 296002 (2014).
  * [28] K. Bernot, J. Luzon, R. Sessoli, A. Vindigni, J. Thion, S. Richeter, D. Leclercq, J. Larionova, and A. van der Lee, J. Am. Chem. Soc. 130, 1619 (2008).
  * [29] W. B. Yelon, D. E. Cox, and M. Eibschütz, Phys. Rev. B 12, 5007 (1975).
  * [30] S. Agrestini, L. C. Chapon, A. Daoud-Aladine, J. Schefer, A. Gukasov, C. Mazzoli, M. R. Lees, and O. A. Petrenko, Phys. Rev. Lett. 101, 097207 (2008).
  * [31] S. Toth, W. Wu, D. T. Adroja, S. Rayaprol, E. V. Sampathkumaran, Phys. Rev. B 93, 174422 (2016).
  * [32] M. Mao, B. D. Gaulin, R. B. Rogge, and Z. Tun, Phys. Rev. B 66, 184432 (2002).
  * [33] A. D. Hillier, D. T. Adroja, W. Kockelmann, L. C. Chapon, S. Rayaprol, P. Manuel, H. Michor, and E. V. Sampathkumaran, Phys. Rev. B 83, 024414 (2011).
  * [34] W.-G. Yin, X. Liu, A. M. Tsvelik, M. P. M. Dean, M. H. Upton, J. Kim, D. Casa, A. Said, T. Gog, T. F. Qi, G. Cao, and J. P. Hill, Phys. Rev. Lett. 111, 057202 (2013).
  * [35] E. V. Sampathkumaran, N. Mohapatra, S. Rayaprol, and K. K. Iyer, Phys. Rev. B 75, 052412 (2007).
  * [36] T. Basu, K. Iyer, K. Singh, K. Mukherjee, P. Paulose, and E. Sampathkumaran, Appl. Phys. Lett. 105, 102912 (2014).
  * [37] E. Lefrançois, L. C. Chapon, V. Simonet, P. Lejay, D. Khalyavin, S. Rayaprol, E. V. Sampathkumaran, R. Ballou, and D. T. Adroja, Phys. Rev. B 90, 014408 (2014).
  * [38] L. Duan, X. C. Wang, J. Zhang, Z. Hu, J. F. Zhao, Y. G. Feng, H. L. Zhang, H.-J. Lin, C. T. Chen, W. Wu, Z. Li, R. Wang, J. F. Zhang, T. Xiang, and C. Q. Jin, Phys. Rev. B 106, 184405 (2022).
  * [39] P. E. Bl$\ddot{\text{o}}$chl, Phys. Rev. B 50, 17953 (1994).
  * [40] G. Kresse and J. Furthm$\ddot{\text{u}}$ller, Comput. Mater. Sci 6, 15 (1996).
  * [41] G. Kresse and J. Furthm$\ddot{\text{u}}$ller, Phys. Rev. B 54, 11169 (1996).
  * [42] J. P. Perdew, K. Burke, and M. Ernzerhof, Phys. Rev. Lett. 77, 3865 (1996).
  * [43] D. D. Johnson, Phys. Rev. B 38, 12807 (1988).
  * [44] A. V. Krukau, O. A. Vydrov, A. F. Izmaylov, G. E. Scuseria, J. Chem. Phys. 125, 224106 (2006).
  * [45] H. Fröhlich, Proceedings of the Royal Society of London. Series A. Mathematical and Physical Sciences 223, 296 (1954).
  * [46] G. Grüner, Rev. Mod. Phys. 60, 1129 (1988).
  * [47] A. Schrön, C. Rö dl, and F. Bechstedt, Phys. Rev. B 82, 165109 (2010).
  * [48] W. Nolting and A. Ramakanth, Quantum Theory of Magnetism (Springer, Berlin, 2009).
  * [49] Matteo Cococcioni and Stefano de Gironcoli, Phys. Rev. B 71, 035105 (2005).
  * [50] A. Molina-Sá nchez, G. Catarina, D. Sangalli and J. Ferná ndez-Rossier, J. Mater. Chem. C, 8, 8856 (2020).
  * [51] D. Grieger and F. Lechermann, Phys. Rev. B 90, 115115 (2014).
  * [52] F. Aryasetiawan, K. Karlsson, O. Jepsen, and U. Schönberger, Phys. Rev. B 74, 125106 (2006).
  * [53] G. Kotliar, S. Y. Savrasov, K. Haule, V. S. Oudovenko, O. Parcollet, and C. A. Marianetti, Rev. Mod. Phys. 78, 865 (2006).
  * [54] A Stroppa and G Kresse, New J. Phys. 10, 063020 (2008).

## ACKNOWLEDGEMENTS

JHZ, YLZ, and JC acknowledge the funding from the National Natural Science
Foundation of China under Grant No. 92165101. WW wishes to acknowledge the
funding support from STFC UK.

## Author Contributions

WW contributed to the concept of the paper. JHZ, JFZ, WW, YLZ, and JC
performed the theoretical analysis. DA, XCW and CQJ contributed to the
experimental part. All the authors wrote the paper.

## Competing Interests

The authors declare no competing interests.

##  Appendix A Band gap measurement

The band gap of BCS has been determined experimentally by measuring the
electrical resistance as a function of temperature. We have measured the
resistance at rather high temperature (375-400 K) as it is too large to
measure at lower temperature. Then we fitted the data to a model
$\ln(R)=\ln(R_{0})+E_{g}/2k_{B}T$, where $R$ is the resistance, $E_{g}$ is the
band gap, $k_{B}$ is the Boltzmann constant, and $T$ is temperature. We have
fitted the first and second half of data using two separate linear model,
which shows the band gap of BCS is between $0.559\pm 0.009$ and $0.843\pm
0.004$ eV.

Figure A.1: (Colour online.) The experimental data (blue points) are linearly
fitted separately. The two gradients of the fittings are $6.485\pm 0.108$ and
$9.777\pm 0.051$, leading to a band-gap range between $0.559\pm 0.009$ and
$0.843\pm 0.004$ eV.


# Navigation with Large Language Models:
Semantic Guesswork as a Heuristic for Planning

Dhruv Shahβ†, Michael Equiβ†, Blazej Osinskiω, Fei Xiaγ, Brian Ichterγ, Sergey
Levineβγ
βUC Berkeley, γGoogle DeepMind, ωUniversity of Warsaw

###### Abstract

Navigation in unfamiliar environments presents a major challenge for robots:
while mapping and planning techniques can be used to build up a representation
of the world, quickly discovering a path to a desired goal in unfamiliar
settings with such methods often requires lengthy mapping and exploration.
Humans can rapidly navigate new environments, particularly indoor environments
that are laid out logically, by leveraging semantics — e.g., a kitchen often
adjoins a living room, an exit sign indicates the way out, and so forth.
Language models can provide robots with such knowledge, but directly using
language models to instruct a robot how to reach some destination can also be
impractical: while language models might produce a narrative about how to
reach some goal, because they are not grounded in real-world observations,
this narrative might be arbitrarily wrong. Therefore, in this paper we study
how the “semantic guesswork” produced by language models can be utilized as a
guiding heuristic for planning algorithms. Our method, Language Frontier Guide
(LFG), uses the language model to bias exploration of novel real-world
environments by incorporating the semantic knowledge stored in language models
as a search heuristic for planning with either topological or metric maps. We
evaluate LFG in challenging real-world environments and simulated benchmarks,
outperforming uninformed exploration and other ways of using language models.

> Keywords: navigation, language models, planning, semantic scene
> understanding

††† These authors contributed equally. Videos and code:
sites.google.com/view/lfg-nav/

##  1 Introduction

Navigation in complex open-world environments is conventionally viewed as the
largely geometric problem of determining collision-free paths that traverse
the environment from one location to another. However, real-world environments
possess _semantics_. Imagine navigating an airport to get to a terminal: your
prior knowledge about the way such buildings are constructed provides
extensive guidance, even if this particular airport is unfamiliar to you.
Large language models (LLMs) and various language embedding techniques have
been studied extensively as ways to interpret the semantics in user-specified
_instructions_ (e.g., parsing “go to the television in the living room” and
grounding it in a specific spatial location), but such models can provide much
more assistance in robotic navigation scenarios by capturing rich semantic
knowledge about the world. For instance, when looking for a spoon in an unseen
house, the LLM can produce a “narrative” explaining why going towards a
dishwasher may eventually lead you to find the spoon, and that the robot
should prioritize that direction. This is similar to how a person might
imagine different ways that the available subgoals might lie on the path to
the goal, and start exploring the one for which this ”narrative” seems most
realistic. However, since language models are not _grounded_ in the real
world, such models do not know the spatial layout of the robot’s surroundings
(e.g., there is a couch that the robot needs to circumnavigate). To utilize
the semantic knowledge in language models to aid in embodied tasks, we should
not just blindly _follow_ the language model suggestions, but instead use them
as proposals or navigational heuristics. In this paper, we study how that
might be accomplished.

Figure 1: In constrast to methods that use LLM plans directly, Language
Frontier Guide (LFG) uses a language model to _score_ subgoal candidates, and
uses these scores to guide a heuristic-based planner.

We study this idea in the context of visual navigation, where a robot is
tasked with reaching a goal denoted by a natural language query $q$ (see Fig.
1) in a _novel_ environment using visual observations. The robot has no prior
experience in the target environment, and must explore the environment to look
for the goal. While narratives generated by an LLM may not be sufficient for
navigation by themselves, they contain useful cues that can be used to
_inform_ or _guide_ the behavior of the underlying navigation stack for the
language navigation task (e.g., by choosing between collision-free subgoal
proposals that avoid the couch and lead to the ice tray). We show that this
idea can be combined with frontier-based exploration, where the robot
maintains a set of unvisited locations at its frontier, _grounds_ them in text
using a vision-language model (VLM), and _scores_ the unvisited subgoals by
using LLM reasoning.

We propose Language Frontier Guide, or LFG, a method for leveraging the
reasoning capabilities of LLMs to produce a _search heuristic_ for guiding
exploration of previously unseen real-world environments, combining the
strengths of search-based planning with LLM reasoning. LFG is agnostic of the
memory representation and planning framework, and can be combined with both
(i) a geometric navigation pipeline, building a metric map of the environment
for planning and using a hand-designed controller, as well as (ii) a learning-
based navigation pipeline, building a topological map for planning and using a
learned control policy, yielding a versatile system for navigating to open-
vocabulary natural language goals. Our experiments show that LFG can identify
and predict simple patterns in previously unseen environments to accelerate
goal-directed exploration. We show that LFG outperforms other LLM-based
approaches for semantic goal-finding in challenging real-world environments
and on the Habitat ObjectNav benchmark.

##  2 Related Work

Vision-based navigation: Navigation is conventionally approached as a largely
geometric problem, where the aim is to map an environment and use that map to
find a path to a goal location [1]. Learning-based approaches can exploit
patterns in the training environments, particularly by learning vision-based
navigation strategies through reinforcement or imitation [2, 3, 4, 5, 6, 7].
Our work is also related to PONI [7], which uses a learned potential function
to prioritize frontier points to explore; instead, we use a language model to
rank these points. Notably, these methods do not benefit from prior semantic
knowledge (e.g., from the web), and must rely entirely on patterns discovered
from offline or online navigational data. Our aim is specifically to bring
semantic knowledge into navigation, to enable robots to more effectively
search for a goal in a new environment.

Semantic knowledge-guided navigation: Prior knowledge about the semantics of
indoor environments can provide significantly richer guidance. With the advent
of effective open-vocabulary vision models [8, 9], some works have recently
explored incorporating their semantic knowledge into models for navigation and
other robotic tasks with the express aim of improving performance at
_instruction following_ [10, 11, 12, 13, 14]. In general within robotics, such
methods have either utilized pre-trained vision-language representations [15,
16, 17], or used language models directly to make decisions [18, 19, 20, 21,
22, 23]. Our aim is somewhat different: while we also focus on language-
specified goals, we are primarily concerned with utilizing the semantics in
pre-trained language models to help a robot figure out how to actually reach
the goal, rather than utilizing the language models to more effectively
interpret a language instruction. While language models can output reasonable
substeps for temporally extended tasks in some settings [24, 25], there is
contradictory evidence about their ability to actually plan [26], and because
they are unaware of the observations and layout in a particular environment,
their “plans” depend entirely on the context that is provided to them. In
contrast to prior work, our approach does not rely on the language model
producing a _good_ plan, but merely a heuristic that can bias a dedicated
planner to reach a goal more effectively. In this way, we use the language
models more to produce _suggestions_ rather than actual plans.

LLM-guided navigation: Some works have sought to combine predictions from
language models with either planning or probabilistic inference [27, 14], so
as to not rely entirely on forward prediction from the language model to take
actions. However, these methods are more aimed at filtering out _infeasible_
decisions, for example by disallowing actions that a robot is incapable of
performing, and still focus largely on being able to interpret and process
instructions, rather than using the language model as a source of semantic
hints. In contrast, by incorporating language model suggestions as heuristics
into a heuristic planner, our approach can completely override the language
model predictions if they are incorrect, while still making use of them if
they point the way to the goal.

Another branch of recent research [28, 29, 30] has taken a different approach
to ground language models, by making it possible for them to read in image
observations directly. While this represents a promising alternative approach
to make language models more useful for embodied decision making, we believe
it is largely orthogonal and complementary to our work: although vision-
language models can produce more grounded inferences about the actions a robot
should take, they are still limited only to _guessing_ when placed in
unfamiliar environments. Therefore, although we use ungrounded language-only
models in our evaluation, we expect that our method could be combined with
vision-language models easily, and would provide complementary benefits.

##  3 Problem Formulation and Overview

Our objective is to design a high-level planner that takes as input a natural
language query $q$ (e.g., “find the bedside table”), explores the environment
in search of the queried object, and commands a low-level policy to control a
robotic agent. To do this, we maintain an episodic memory of the environment
${\mathcal{M}}$ in the form of either (i) a 2D map of the environment, where
grid cells contain information about occupancy and semantic labels, or (ii) a
topological map of the environment, where nodes contain images captured by the
robot and corresponding object labels. One way to solve this task is Frontier-
Based Exploration (FBE) [31], where a robot maintains a set of unexplored
_frontiers_ in it’s memory, and explores randomly to reach the goal. _Can we
do better with access to LLMs?_

We distill the language-guided exploration task to a heuristic-based search
problem, where the robot must propose unvisited subgoals or waypoints, score
them, and then use a search algorithm (e.g., A*) to plan a path to the goal.
Thus, at the core of LFG is the task of _scoring_ subgoal proposals. Formally,
let’s assume we have the task by query $q$, a partially explored environment
stored in ${\mathcal{M}}$, and a set ${\mathcal{S}}$ of $n$ textual subgoal
proposals $s_{1},s_{2},\ldots,s_{n}$ (e.g., “a corner with a dishwasher and
refrigerator”, “a hallway with a door”, etc.). Our goal is to score these
subgoal proposals with $p(s_{i},q,{\mathcal{M}})$, the probability that the
candidate $s_{i}\in{\mathcal{S}}$ will lead to the goal $q$ given the current
state of the environment, described through ${\mathcal{M}}$.

We posit that we can leverage the semantic reasoning capabilities of LLMs by
prompting them to construct narratives about which semantic regions of the
environment are most (and least) likely to lead to the goal. While the
narrative itself might be ungrounded, since the LLM knows very little about
the environment, reasoning over objects and semantic regions of the
environment often generalizes very broadly. For example, even without seeing a
new apartment, a human would _guess_ that the dining area is close to the
kitchen. Hence, rather than directly using LLM scores for planning [25, 23],
we incorporate them as a goal-directed _heuristic_ to inform the search
process. This has two distinct advantages: (i) when the LLM is right, it
nudges the search towards the goal, and when it is wrong (or uncertain), we
can still default to the underlying FBE algorithm, allowing recovery from LLM
failures, and (ii) it allows us to combine the signal from LLMs with other
scores that may be more grounded, e.g. distance to subgoals, making the system
more versatile.

##  4 LFG: Scoring Subgoals by Polling LLMs

Figure 2: LFG scores subgoals with an empirical estimate of the likelihoods by
sampling an LLM $n_{s}$ times with both positive and negative prompts, and
uses chain-of-thought to obtain reliable scores. These scores are used by a
high-level planner as _heuristics_ to guide search. For full prompts, see
Appendix B.

Our aim in this section is to derive a scoring function from LLMs that takes a
textual description of subgoal candidates $s_{i}$ and the goal query $q$ as
inputs, and predicts task-relevant probability $p(s_{i},q,{\mathcal{M}})$,
conditioned on the episodic memory ${\mathcal{M}}$. While we may obtain this
from next-token likelihoods (or “logprobs”), they do not represent the desired
task-relevant probability $p(s_{i},q,{\mathcal{M}})$, and fail to assign
similar scores, say, to different subgoals that are semantically similar but
have different tokenizations (see our experiments in Section 6 for a
comparison). Furthermore, most capable LLMs of today are available through
APIs that do not expose the ability to query logprobs.111Most notably,
OpenAI’s Chat API for GPT-3.5 and GPT-4, Google’s PaLM API, and Anthropic’s
Claude API all do not support logprobs. And lastly, even if reliable logprobs
were available, they are incompatible with chain-of-thought prompting [32],
which we find to be crucial to success in spatial reasoning.

To overcome these challenges, LFG uses a novel approach to extract task-
relevant likelihoods from LLMs. Given candidate subgoal images, LFG uses a VLM
to obtain a textual subgoal desriptor $s_{i}$, which must be scored with the
LLM. LFG _polls_ the LLMs by sampling the most likely subgoal $n_{s}$ times,
conditioned on a task-relevant prompt. We then use these samples to
empirically estimate the likelihood of each subgoal. To get informative and
robust likelihood estimates, we use a chain-of-thought prompting (CoT)
technique [32], to improve the quality and interpretability of the scores, and
use a combination of positive and negative prompts to gather unbiased
likelihood estimates. Figure 2 outlines our scoring technique, with the full
prompt provided in Appendix B. We now describe the details of our scoring
technique.

Structured query: We rely on in-context learning by providing an example of a
structured query-response pair to the LLM, and ask it to pick the most likely
subgoal that satisfies the query. To sample a subgoal from ${\mathcal{S}}$
using a language model, we prompt it to generate a structured response, ending
with ‘‘Answer: i’’. This structure allows us to always sample a _valid_
subgoal, without having to ground LLM generations in the environment [24].

Positives and negatives: We find that only using positive prompts (e.g.,
“which subgoal is most likely to reach the goal”) leads to likelihood
estimates being uninformative for cases where the LLM is not confident about
any subgoal. To overcome this, we also use negative prompts (e.g., “which
subgoal is least likely to be relevant for the goal”), which allows us to
score subgoals by eliminating/downweighting subgoals that are clearly
irrelevant. We then use the difference between the positive and negative
likelihoods to rank subgoals.

Data: Subgoal descriptors $\\{l_{i}\forall s_{i}\in{\mathcal{S}}\\}$

1 pPrompt $\leftarrow$ PositivePrompt($\\{l_{i}\\}$)

2 nPrompt $\leftarrow$ NegativePrompt($\\{l_{i}\\}$)

3 pSamples $\leftarrow$ [sampleLLM(pPrompt) $*\,n_{s}$]

4 nSamples $\leftarrow$ [sampleLLM(nPrompt) $*\,n_{s}$]

5 pScores $\leftarrow$ sum(pSamples) / $n_{s}$

6 nScores $\leftarrow$ sum(nSamples) / $n_{s}$

return pScores, nScores

Algorithm 1 Scoring Subgoals with LFG

Chain-of-thought prompting: A crucial component of getting interpretable and
reliable likelihood estimates is to encourage the LLM to _justify_ its choice
by chain-of-thought prompting. As demonstrated in prior works, CoT elicits
interpretability and reasoning capabilities in LLMs, and while we don’t
explicitly use the generated reasonings in our approach (great future work
direction), we find that CoT improves the quality and consistency of the
likelihood estimates. Additionally, it also helps maintain interpretability,
to better understand why the LFG-equipped agent takes certain decisions.

In summary, we score subgoals by sampling the LLM multiple times and
empirically estimating the likelihood of each subgoal. We use a combination of
positive and negative prompts to get unbiased likelihood estimates, and use
chain-of-thought prompting to improve the quality and interpretability of the
scores (Figure 2). We will now discuss how these scores can be incorporated
into a navigation system as _search heuristics_.

##  5 LLM Heuristics for Goal-Directed Exploration

Figure 3: Overview of LFG for language-guided exploration. Based on the pose
and observations, LFG builds an episodic memory (topological or metric), which
is used by the heuristic-based exploration policy to rank adjacent clusters,
or subgoal frontiers. Navigation to the subgoal frontier is completed by a
low-level policy.

Given the LLM scoring pipeline outlined in the previous section, our key
insight is that we can incorporate these scores in a search-based planning
pipeline to _heuristically_ guide the search process. We instantiate LFG using
frontier-based exploration (FBE) and LLM scores generated via polling.

FBE: This method maintains a “map” of the seen parts of the environment, which
may be geometric [33] or topological [34], and a frontier separating it from
the unexplored parts. By navigating to the _nearest_ point of the frontier,
the robot explores new areas of the environment until it finds the goal object
or completes exploration without finding it. A standard FBE implementation is
presented in Algorithm 2 inblack text. The robot maintains either a 2D metric
map of its surroundings, or a topological map whose nodes are comprised of the
robot’s visual observations and edges represent paths taken in the
environment. Additionally, we also store semantic labels corresponding to
objects detected in the robot’s observations, which are used to ground the
observations in text.

At a fixed re-planning rate, the high-level planner computes its frontier
$f_{i}$ (Line 2), and picks the frontier point that is _closest_ to the
current location, i.e., maximizing the distance score (Line 2), and then
navigates to this frontier (Line 2). At any point in this process, if the
agent’s semantic detector detects an object of the same category as the query
$q$, it navigates directly to this object and the trajectory ends.

Incorporating LLM scores: Our method, LFG, extends FBE by using an additional
search heuristic obtained by polling LLMs for semantic “scores”. The
modifications to FBE are marked in purple in Algorithm 2. After enumerating
the frontiers, LFG uses the semantic labels from a VLM [35] to _ground_
subgoal images at each frontier $f_{i}$ (Line 2). These images are converted
into textual strings, and form the subgoal candidates $s_{i}$ that can be
scored using Algorithm 1. We associate each frontier point $f_{i}$ with the
nearest object cluster $c_{i}$ (Line 2), and compute LLM scores for each point
as follows:

$h(f_{i},q)=w_{p}\cdot\text{LLM}_{\text{pos}}(c_{i})-w_{n}\cdot\text{LLM}_{\text{neg}}(c_{i})-\text{dist}(f_{i},p),$
(1)

where $p$ is the current position of the agent, and $w_{p},w_{n}$ are
hyperparameters (see Appendix A.1). We then choose the frontier with the
highest score to be the next subgoal (Line 2), navigate to it using a local
controller, and repeat the planning process. Algorithm 2 outlines the general
recipe for integrating LLM scores as a planning heuristic. Please see Appendix
A for specific instantiations of this system with geometric and topological
maps, and more details about the referenced subroutines.

Data: $o_{0}$, Goal language query $q$

1 subgoal $\leftarrow$ None

2 while  _not done_ do

3 $o_{t}$ $\leftarrow$ getObservation()

4 episodicMemory $\leftarrow$ mappingModule($o_{t}$)

5 if  _$q$ in semanticMap_ then

6 subGoal $\leftarrow$ getLocation(episodicMemory, q)

7 else

8 if  _numSteps $\%\,\,\tau==0$_ then

// replanning

9 location $\leftarrow$ getCurrentLocation()

10 frontier $\leftarrow$ getFrontier(episodicMemory)

11 objectClusters $\leftarrow$ getSemanticLabels(episodicMemory, frontier)

12 ${LLM}_{pos},{LLM}_{neg}\leftarrow$ ScoreSubgoals(objectClusters)

13 scores $\leftarrow$ []

14 for  _point in frontier_ do

15 distance $\leftarrow$ DistTo(location, point)

16 scores[point] $\leftarrow$ – distance

17 closestCluster $\leftarrow$ getClosestCluster(objectClusters, point)

18 $i\leftarrow$ clusterID(closestCluster)

19 if  _dist(closestCluster, point) $<\delta$_ then

// incorporate language scores

20 scores[point] $\leftarrow w_{p}\cdot$ ${LLM}_{pos}$ [$i$] -
$w_{n}\cdot{LLM}_{neg}$ [$i$] - distance

21

22 subgoal $\leftarrow$ argmax(scores)

23

24 numSteps $\leftarrow$ numSteps $+1$

25 goTo(subGoal)

Algorithm 2 Instantiating LFG for Goal-Directed Exploration

##  6 System Evaluation

We now evaluate the performance of LFG for the task of goal-directed
exploration in real-world environments, and benchmark its performance against
baselines. We instantiate two systems with LFG: a real-world system that uses
a topological map and a learned control policy, and a simulated agent that
uses a geometric map and a deterministic control policy. Our experiments show
that both these systems outperform existing LLM-based exploration algorithms
by a wide margin, owing to the high quality scores incorporated as search
heuristics.

###  6.1 Benchmarking ObjectNav Performance

We benchmark the performance of LFG for the task of object-goal navigation on
the Habitat ObjectNav Challenge [36], where the agent is placed into a
simulated environment with photo-realistic graphics, and is tasked with
finding a query object from one of 10 categories (e.g., “toilet”, “bed”,
“couch” etc.). The simulated agent has access to egocentric RGBD observations
and accurate pose information. We run 10 evaluation episodes per scene and
report two metrics: the average success rate, and success weighted by optimal
path length (SPL), the default metrics for the benchmark. Since LFG requires
no training, we do not use the training scenes from HM3D.

We compare to three classes of published baselines: (i) learning-based
baselines that learn navigation behavior from demonstrations or online
experience in the training scenes [37] on up to 2.5B frames of experience,
(ii) search-based baselines [38, 33], and (iii) LLM-based baselines that do
not use the training data directly, but leverage the semantic knowledge inside
foundation models to guide embodied tasks [39, 18].

Figure 4: Qualitative example of a negative score influencing the agent’s
decision. LFG discourages the agent from exploring the bedroom and living
room, leading to fast convergence toward the goal, whereas FBE fails. The CoT
reasoning given by the LLM is shown in purple, justifying its score. Figure 5:
Qualitative example of LFG in real. LFG reasons about floor plans in the
environment it is searching. In this apartment experiment, LFG believes that a
bathroom is more likely to be found near a bedroom rather than a kitchen, and
guides the robot towards the bedroom, successfully reaching the goal.

Evaluating LFG on the HM3D benchmark, we find that it significantly
outperforms search and LLM-based baselines (Table 1). Greedy LLM struggles on
the task due to several LLM planning failures, causing the episodes to fail.
LFG significantly outperforms the vanilla FBE baseline by leveraging semantic
priors from LLMs to score subgoals intelligently. Comparing to learning-based
baselines, we find that LFG outperforms most of them and closely matches the
state-of-the-art on the task, proving the competence of our polling and
heuristic approach. Figure 4 shows an example of the LFG agent successfully
reaching the goal by using chain-of-thought and negative prompting.

L3MVN [39], which uses a combination of LLMs and search, performs slightly
better than FBE, but is unable to fully leverage the semantics in LLMs. While
being similar to LFG, it suffers from two key limitations: (i) it uses a small
language model (GPT-2), which likely does not contain strong semantic priors
for the agent to leverage, and (ii) it uses a simple likelihood-based scoring
scheme, which we show below is not very effective. Another closely related
work, LGX [18], uses a variant of greedy LLM scoring, and hence fails to
perform reliably on the benchmark.

Probing deeper into the strong performance of LFG, we ablated various
components of our scoring pipeline and studied the change in performance. Note
that LGX (Greedy) and L3MVN (No CoT, Logprobs) can be seen as ablations of
LFG. Table 2 shows that modifying both the prompting and scoring mechanisms
used by LFG lead to large drops in performance. Most notably, scoring via
polling ($+7.8\%$) and CoT ($+6.6\%$) are both essential to the strong
performance of LFG. Furthermore, we find that using only positive prompts also
hurts performance ($-4.7\%$). Popular approaches for using LLMs for planning
are significantly outperformed by LFG: Greedy ($-14.5\%$) and Logprobs
($-8.5\%$). Figure 4 shows an example of the LFG agent successfully reaching
the goal by using CoT and negative prompting.

Setup: For these experiments, we mimic the semantic mapping pipeline of the
best-performing baseline on the benchmark [38, 33], and integrate LFG with the
geometric map. The simulated agent builds a 2D semantic map of its
environment, where grid cells represent both occupancy and semantic labels
corresponding to objects detected by the agent. Prior work has shown that
state-of-the-art vision models, such as DETIC, work poorly in simulation due
to rendering artifacts [33]; hence, we use ground-truth semantic information
for all simulated baselines to analyze navigation performance under perfect
perception.

###  6.2 Real-world Exploration with LFG

To show the versatility of the LFG scoring framework, we further integrated it
with a heuristic-based exploration framework that uses topological graphs for
episodic memory [34]. We compare two published baselines: a language-agnostic
FBE baseline [40], and an LLM-based baseline that uses the language model to
greedily pick the frontier [18].

We evaluate this system in two challenging real-world environments: a
cluttered cafeteria and an apartment building (shown in Figures 3 and 5). In
each environment, the robot is tasked to reach an object described by a
textual string (e.g., “kitchen sink” or “oven”), and we measure the success
rate and efficiency of reaching the goal. Episodes that take longer than 30
minutes are marked as failure. While we only tested our system with goal
strings corresponding to the 20,000 classes supported by our object detector
[35], this can be extended to more flexible goal specifications with the rapid
progress in vision-language models.

We find that the complexity of real-world environments causes the language-
agnostic FBE baseline to _time out_ , i.e., the robot is unable to reach the
goal by randomly exploring the environment. Both LLM baselines are able to
leverage the stored semantic knowledge to guide the exploration in novel
environments, but LFG achieves 16% better performance. Figure 5 shows an
example rollout in a real apartment, where the robot uses LFG to reach the
toilet successfully.

Setup: We instantiate LFG in the real-world using a previously published
topological navigation framework [34] that builds a topological map of the
environment, where nodes correspond to the robot’s visual observations and
edges correspond to paths traversed in the environment. This system relies on
omnidirectional RGB observations and does not attempt to make a dense
geometric map of the environment. To obtain “semantic frontiers” from the
omnidirectional camera, we generate $n_{v}=4$ _views_ and run an off-the-shelf
object detector [35] to generate rich semantic labels describing objects in
these views. The robot maintains a topological graph of these views and
semantic labels, and picks the frontier view with the highest score (Algorithm
2, Line 2) according to LFG. The robot then uses a Transformer-based policy
[6, 41] to reach this subgoal. For more implementation details, see Appendix
A.3.

Method | Success | SPL | Data
---|---|---|---
DD-PPO [37] | 27.9 | 14.2 | 2.5B
FBE [33] | 61.1 | 34.0 | 0
SemExp [38] | 63.1 | 0.29 | 10M
OVRL-v2 [42] | 64.7 | 28.1 | 12M
Greedy LLM [18] | 54.4 | 26.9 | 0
L3MVN [39] | 62.4 |  | 0
LFG (Ours) | 68.9 | 36.0 | 0

Table 1: LFG outperforms all LLM-based baselines on HM3D ObjectNav benchmark,
and can achieve close to SOTA performance without any pre-training.

| Method | Success | $\Delta$
---|---|---|---
LFG (Full) | 68.9 | –
Prompting |  |
| No CoT | 62.3 | (6.6)
| Only Positives | 64.2 | (4.7)
Scoring |  |
| Random | 61.1 | (7.8)
| Logprobs | 60.4 | (8.5)
| Ask | 62.4 | (6.5)

Table 2: We find that CoT prompting with positives and negatives, combined
with polling, are essential to achieve the best performance.

##  7 Discussion

We presented LFG, a method for utilizing language models for _semantic
guesswork_ to help navigate to goals in new and unfamiliar environments. The
central idea in our work is that, while language models can bring to bear rich
semantic understanding, their ungrounded inferences about how to perform
navigational tasks are better used as suggestions and heuristics rather than
plans. We formulate a way to derive a heuristic score from language models
that we can then incorporate into a planning algorithm, and use this heuristic
planner to reach goals in new environments more effectively. This way of using
language models benefits from their inferences when they are correct, and
reverts to a more conventional unguided search when they are not.

Limitations and future work: While our experiments provide a validation of our
key hypothesis, they have a number of limitations. First, we only test in
indoor environments in both sim and real yet the role of semantics in
navigation likely differs drastically across domains – e.g., navigating a
forest might implicate semantics very differently than navigating an apartment
building. Exploring the applicability of semantics derived from language
models in other settings would be another promising and exciting direction for
future work. Second, we acknowledge that multiple requests to cloud-hosted
LLMs with CoT is slow and requires an internet connection, severely limiting
the extent of real-world deployment of the proposed method. We hope that
ongoing advancements in quantizing LLMs for edge deployment and fast inference
will address this limitation.

#### Acknowledgments

This research was partly supported by AFOSR FA9550-22-1-0273 and DARPA ANSR.
The authors would like to thank Bangguo Yu, Vishnu Sashank Dorbala, Mukul
Khanna, Theophile Gervet, and Chris Paxton, for their help in reproducing
baselines. The authors would also like to thank Ajay Sridhar, for supporting
real-world experiments, and Devendra Singh Chaplot, Jie Tan, Peng Xu, and
Tingnan Zhang, for useful discussions in various stages of the project.

## References

  * DeSouza and Kak [2002] G. N. DeSouza and A. C. Kak.  Vision for mobile robot navigation: A survey.  _IEEE transactions on pattern analysis and machine intelligence_ , 24(2):237–267, 2002.
  * Anderson et al. [2018] P. Anderson, Q. Wu, D. Teney, J. Bruce, M. Johnson, N. Sünderhauf, I. Reid, S. Gould, and A. van den Hengel.  Vision-and-language navigation: Interpreting visually-grounded navigation instructions in real environments.  In _IEEE Conference on Computer Vision and Pattern Recognition_ , pages 3674–3683, 2018.
  * Savinov et al. [2018] N. Savinov, A. Dosovitskiy, and V. Koltun.  Semi-parametric topological memory for navigation.  _arXiv preprint arXiv:1803.00653_ , 2018.
  * Hirose et al. [2019] N. Hirose, F. Xia, R. Martín-Martín, A. Sadeghian, and S. Savarese.  Deep visual MPC-policy learning for navigation.  _IEEE Robotics and Automation Letters_ , 2019.
  * Shah et al. [2022] D. Shah, A. Sridhar, A. Bhorkar, N. Hirose, and S. Levine.  GNM: A General Navigation Model to Drive Any Robot.  In _arXiV_ , 2022.
  * Shah et al. [2023] D. Shah, A. Sridhar, N. Dashora, K. Stachowicz, K. Black, N. Hirose, and S. Levine.  ViNT: A Foundation Model for Visual Navigation.  In _7th Annual Conference on Robot Learning (CoRL)_ , 2023.
  * Ramakrishnan et al. [2022] S. K. Ramakrishnan, D. S. Chaplot, Z. Al-Halah, J. Malik, and K. Grauman.  Poni: Potential functions for objectgoal navigation with interaction-free learning.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pages 18890–18900, 2022.
  * Chen et al. [2022] X. Chen, X. Wang, S. Changpinyo, A. Piergiovanni, P. Padlewski, D. Salz, S. Goodman, A. Grycner, B. Mustafa, L. Beyer, et al.  Pali: A jointly-scaled multilingual language-image model.  _arXiv preprint arXiv:2209.06794_ , 2022.
  * Radford et al. [2021] A. Radford, J. W. Kim, C. Hallacy, A. Ramesh, G. Goh, S. Agarwal, G. Sastry, A. Askell, P. Mishkin, J. Clark, et al.  Learning transferable visual models from natural language supervision.  In _International Conference on Machine Learning_ , 2021.
  * Majumdar et al. [2020] A. Majumdar, A. Shrivastava, S. Lee, P. Anderson, D. Parikh, and D. Batra.  Improving vision-and-language navigation with image-text pairs from the web.  In _Computer Vision–ECCV 2020: 16th European Conference, Glasgow, UK, August 23–28, 2020, Proceedings, Part VI 16_ , pages 259–274. Springer, 2020.
  * Majumdar et al. [2022] A. Majumdar, G. Aggarwal, B. Devnani, J. Hoffman, and D. Batra.  Zson: Zero-shot object-goal navigation using multimodal goal embeddings.  _arXiv preprint arXiv:2206.12403_ , 2022.
  * Chen et al. [2022] B. Chen, F. Xia, B. Ichter, K. Rao, K. Gopalakrishnan, M. S. Ryoo, A. Stone, and D. Kappler.  Open-vocabulary queryable scene representations for real world planning.  _arXiv preprint arXiv:2209.09874_ , 2022.
  * Huang et al. [2022] C. Huang, O. Mees, A. Zeng, and W. Burgard.  Visual language maps for robot navigation.  _arXiv preprint arXiv:2210.05714_ , 2022.
  * Shah et al. [2022] D. Shah, B. Osinski, B. Ichter, and S. Levine.  LM-nav: Robotic navigation with large pre-trained models of language, vision, and action.  In _Annual Conference on Robot Learning (CoRL)_ , 2022.
  * Shridhar et al. [2021] M. Shridhar, L. Manuelli, and D. Fox.  Cliport: What and where pathways for robotic manipulation.  In _Proceedings of the 5th Conference on Robot Learning (CoRL)_ , 2021\.
  * Shafiullah et al. [2023] N. M. M. Shafiullah, C. Paxton, L. Pinto, S. Chintala, and A. Szlam.  Clip-fields: Weakly supervised semantic fields for robotic memory, 2023\.
  * Jatavallabhula et al. [2023] K. Jatavallabhula, A. Kuwajerwala, Q. Gu, M. Omama, T. Chen, S. Li, G. Iyer, S. Saryazdi, N. Keetha, A. Tewari, J. Tenenbaum, C. de Melo, M. Krishna, L. Paull, F. Shkurti, and A. Torralba.  Conceptfusion: Open-set multimodal 3d mapping.  _arXiv_ , 2023.
  * Dorbala et al. [2023] V. S. Dorbala, J. F. J. Mullen, and D. Manocha.  Can an Embodied Agent Find Your ”Cat-shaped Mug”? LLM-Based Zero-Shot Object Navigation, 2023.
  * Mees et al. [2023] O. Mees, J. Borja-Diaz, and W. Burgard.  Grounding language with visual affordances over unstructured data, 2023\.
  * Singh et al. [2022] I. Singh, V. Blukis, A. Mousavian, A. Goyal, D. Xu, J. Tremblay, D. Fox, J. Thomason, and A. Garg.  Progprompt: Generating situated robot task plans using large language models, 2022.
  * Xie et al. [2023] Y. Xie, C. Yu, T. Zhu, J. Bai, Z. Gong, and H. Soh.  Translating natural language to planning goals with large-language models.  _arXiv preprint arXiv:2302.05128_ , 2023.
  * Ding et al. [2023] Y. Ding, X. Zhang, C. Paxton, and S. Zhang.  Task and motion planning with large language models for object rearrangement, 2023.
  * Lin et al. [2023] K. Lin, C. Agia, T. Migimatsu, M. Pavone, and J. Bohg.  Text2motion: From natural language instructions to feasible plans, 2023\.
  * Huang et al. [2022] W. Huang, P. Abbeel, D. Pathak, and I. Mordatch.  Language models as zero-shot planners: Extracting actionable knowledge for embodied agents.  In _International Conference on Machine Learning (ICML)_ , 2022.
  * Ichter et al. [2022] B. Ichter, A. Brohan, Y. Chebotar, C. Finn, K. Hausman, A. Herzog, D. Ho, J. Ibarz, A. Irpan, E. Jang, R. Julian, D. Kalashnikov, S. Levine, Y. Lu, C. Parada, K. Rao, P. Sermanet, A. T. Toshev, V. Vanhoucke, F. Xia, T. Xiao, P. Xu, M. Yan, N. Brown, M. Ahn, O. Cortes, N. Sievers, C. Tan, S. Xu, D. Reyes, J. Rettinghouse, J. Quiambao, P. Pastor, L. Luu, K.-H. Lee, Y. Kuang, S. Jesmonth, K. Jeffrey, R. J. Ruano, J. Hsu, K. Gopalakrishnan, B. David, A. Zeng, and C. K. Fu.  Do as i can, not as i say: Grounding language in robotic affordances.  In _Annual Conference on Robot Learning (CoRL)_ , 2022.
  * Valmeekam et al. [2023] K. Valmeekam, A. Olmo, S. Sreedharan, and S. Kambhampati.  Large language models still can’t plan (a benchmark for llms on planning and reasoning about change), 2023.
  * Huang et al. [2023] W. Huang, F. Xia, D. Shah, D. Driess, A. Zeng, Y. Lu, P. Florence, I. Mordatch, S. Levine, K. Hausman, and B. Ichter.  Grounded decoding: Guiding text generation with grounded models for robot control, 2023.
  * Jiang et al. [2022] Y. Jiang, A. Gupta, Z. Zhang, G. Wang, Y. Dou, Y. Chen, L. Fei-Fei, A. Anandkumar, Y. Zhu, and L. Fan.  Vima: General robot manipulation with multimodal prompts.  _arXiv preprint_ , 2022.
  * Huang et al. [2023] S. Huang, L. Dong, W. Wang, Y. Hao, S. Singhal, S. Ma, T. Lv, L. Cui, O. K. Mohammed, B. Patra, Q. Liu, K. Aggarwal, Z. Chi, J. Bjorck, V. Chaudhary, S. Som, X. Song, and F. Wei.  Language is not all you need: Aligning perception with language models, 2023.
  * Driess et al. [2023] D. Driess, F. Xia, M. S. M. Sajjadi, C. Lynch, A. Chowdhery, B. Ichter, A. Wahid, J. Tompson, Q. Vuong, T. Yu, W. Huang, Y. Chebotar, P. Sermanet, D. Duckworth, S. Levine, V. Vanhoucke, K. Hausman, M. Toussaint, K. Greff, A. Zeng, I. Mordatch, and P. Florence.  Palm-e: An embodied multimodal language model.  In _arXiv preprint_ , 2023.
  * Yamauchi [1997] B. Yamauchi.  A frontier-based approach for autonomous exploration.  In _IEEE International Symposium on Computational Intelligence in Robotics and Automation (CIRA)_ , 1997.
  * Wei et al. [2022] J. Wei, X. Wang, D. Schuurmans, M. Bosma, B. Ichter, F. Xia, E. H. Chi, Q. V. Le, and D. Zhou.  Chain of thought prompting elicits reasoning in large language models.  In _Neural Information Processing Systems (NeurIPS)_ , 2022.
  * Gervet et al. [2023] T. Gervet, S. Chintala, D. Batra, J. Malik, and D. S. Chaplot.  Navigating to objects in the real world.  _Science Robotics_ , 2023.
  * Shah and Levine [2022] D. Shah and S. Levine.  Viking: Vision-based kilometer-scale navigation with geographic hints.  In _Robotics: Science and Systems (RSS)_ , 2022.
  * Zhou et al. [2022] X. Zhou, R. Girdhar, A. Joulin, P. Krähenbühl, and I. Misra.  Detecting twenty-thousand classes using image-level supervision.  In _17th European Conference on Computer Vision (ECCV)_ , 2022.  doi:10.1007/978-3-031-20077-9_21.
  * Yadav et al. [2022] K. Yadav, S. K. Ramakrishnan, J. Turner, A. Gokaslan, O. Maksymets, R. Jain, R. Ramrakhya, A. X. Chang, A. Clegg, M. Savva, E. Undersander, D. S. Chaplot, and D. Batra.  Habitat challenge 2022.  https://aihabitat.org/challenge/2022/, 2022.
  * Wijmans et al. [2020] E. Wijmans, A. Kadian, A. Morcos, S. Lee, I. Essa, D. Parikh, M. Savva, and D. Batra.  DD-PPO: Learning Near-Perfect PointGoal Navigators from 2.5 Billion Frames.  In _International Conference on Learning Representations (ICLR)_ , 2020.
  * Chaplot et al. [2020] D. S. Chaplot, H. Jiang, S. Gupta, and A. Gupta.  Semantic curiosity for active visual learning.  In _ECCV_ , 2020.
  * Yu et al. [2023] B. Yu, H. Kasaei, and M. Cao.  L3mvn: Leveraging large language models for visual target navigation, 2023\.
  * Shah et al. [2021] D. Shah, B. Eysenbach, N. Rhinehart, and S. Levine.  Rapid exploration for open-world navigation with latent goal models.  In _5th Annual Conference on Robot Learning_ , 2021.
  * Sridhar et al. [2023] A. Sridhar, D. Shah, C. Glossop, and S. Levine.  NoMaD: Goal Masked Diffusion Policies for Navigation and Exploration.  In _arXiv_ , 2023.
  * Yadav et al. [2023] K. Yadav, A. Majumdar, R. Ramrakhya, N. Yokoyama, A. Baevski, Z. Kira, O. Maksymets, and D. Batra.  Ovrl-v2: A simple state-of-art baseline for imagenav and objectnav, 2023\.

##  Appendix A Implementation Details

###  A.1 Hyperparameters

| Parameter | Value
---|---|---
$\tau$ | Replanning Rate | 1
$\delta$ | Language Influence Threshold | 2m
$n_{s}$ | Number of LLM Samples | 10
$w_{p}$ | Weight of Positive Scores | 300
$w_{n}$ | Weight of Negative Scores | 150
| Max Time Steps | 500
Table 3: Hyperparameters

###  A.2 Computational Resources

Parameter | Value
---|---
LLM | gpt-3.5-turbo222We use GPT-3.5 for all our experiments. We found GPT-4 to be slightly better at spatial reasoning, but the rate limits of GPT-4 were unworkable for us (200 RPM/40K TPM v/s 3500 RPM/90K TPM for GPT-3.5).
Evaluation Runtime | 5 hours
Compute Resources | $4\times V100$
Total LLM Tokens | 30M
Average API Cost | 15 USD
Table 4: Parameters and resources required to run one evaluation round of LFG
on the benchmark.

###  A.3 Real World Results

Generating Prompts: For both topological and geometric maps we use hand
engineered methods for clustering objects in ways that the LLM can efficiently
reason over. For geometric maps we implement two functions: $parseObjects$ and
$clusterObjects$. In our implementation, $parseObejcts$ filters the geometric
map and identifies the cluster centers among each class. $clusterObjects$
takes the cluster centers and performs agglomerative clustering with a
threshold of 6 meters, which is roughly the size of one section of a standard
house. For topological maps we rely on the configuration of the four cameras
to automatically perform parsing and clustering. In our implementation all the
objects detected in each frame from either the front, left, right, or rear
facing cameras is considered a single cluster.

Perception: For the hardware, we use a locobot base with a four HD logitech
web cameras that are positioned at 90 degrees relative to each other. At each
step of LFG each of four cameras is recorded and frames are semantically
annotated. LFG directly uses these frames to determine if the robot should
continue to move forward, turn left, turn right, or turn around a full 180
degrees. To improve the performance of our system we choose to whitelist a
subset of the 20,000 classes. This reduces the size of the API calls to the
language models and helps steer the LLM to focus on more useful information.
Following is the complete whitelist used in our experiments:

  * •

toaster

  * •

projector

  * •

chair

  * •

kitchen table

  * •

sink

  * •

kitchen sink

  * •

water faucet

  * •

faucet

  * •

microwave oven

  * •

toaster oven

  * •

oven

  * •

coffee table

  * •

coffee maker

  * •

coffeepot

  * •

dining table

  * •

table

  * •

bathtub

  * •

bath towel

  * •

urinal

  * •

toilet

  * •

toilet tissue

  * •

refrigerator

  * •

automatic washer

  * •

washbasin

  * •

dishwasher

  * •

television set

  * •

sofa

  * •

sofa bed

  * •

bed

  * •

chandelier

  * •

ottoman

  * •

dresser

  * •

curtain

  * •

shower curtain

  * •

trash can

  * •

garbage

  * •

cabinet

  * •

file cabinet

  * •

monitor (computer equipment)

  * •

computer monitor

  * •

computer keyboard

  * •

laptop computer

  * •

desk

  * •

stool

  * •

hand towel

  * •

shampoo

  * •

soap

  * •

drawer

  * •

pillow

Low-level Policy: The low-level policy running on the robot is the NoMaD goal-
conditioned diffusion policy trained to avoid obstacles during exploration and
determine which frontiers can be explored further [41].

High-level Planning: For real-world experiments, we follow the setup of ViKiNG
[34], where the agent runs a simple frontier-based exploration algorithm and
incorporates the LLM scores as _goal-directed heuristics_ to pick the best
subgoal frontier. For simulation experiments, we use a geometric map coupled
with frontier-based exploration, following the setup of Chaplot et al. [38].
Algorithms 3 and 4 summarize the high-level planning module in both cases.

Data: $o_{0}$, Goal language query $q$

1 subgoal $\leftarrow$ None

2 while  _not done_ do

3 $o_{t}$ $\leftarrow$ getObservation()

4 frontierPoints $\leftarrow$ mappingModule($o_{t}$)

5 if  _$q$ in frontierPoints_ then

6 turnTowardGoal(frontierPoints)

7 else

8 if  _numSteps $\%\,\,\tau==0$_ then

9 location $\leftarrow$ getCurrentLocation()

10 ${LLM}_{pos},{LLM}_{neg}\leftarrow$ scoreFrontiers(frontierPoints) scores
$\leftarrow$ []

11 for  _point in frontier_ do

12 distance $\leftarrow$ distTo(location, point)

13 scores[point] $\leftarrow$ $w_{p}\cdot{LLM}_{pos}$ [$i$] -
$w_{n}\cdot{LLM}_{neg}$ [$i$] - distance

14 subgoal $\leftarrow$ argmax(scores)

15 numSteps $\leftarrow$ numSteps $+1$

16 goTo(subGoal)

17

18

Algorithm 3 Instantiating LFG with Topological Mapping

Data: $o_{0}$, Goal language query $q$

1 subgoal $\leftarrow$ None

2 while  _not done_ do

3 $o_{t}$ $\leftarrow$ getObservation()

4 obstacleMap, semanticMap $\leftarrow$ mappingModule($o_{t}[\text{depth}]$,
$o_{t}[\text{semantic}]$)

5 if  _$q$ in semanticMap_ then

6 subGoal $\leftarrow$ getLocation(semanticMap, q)

7 else

8 if  _numSteps $\%\,\,\tau==0$_ then

// replanning

9 location $\leftarrow$ getCurrentLocation()

10 frontier $\leftarrow$ getFrontier(obstacleMap)

11 objects $\leftarrow$ parseObjects(semanticMap)

12 objectClusters $\leftarrow$ clusterObjects(objects)

13 ${LLM}_{pos},{LLM}_{neg}\leftarrow$ ScoreSubgoals(objectClusters)

14 scores $\leftarrow$ []

15 for  _point in frontier_ do

16 distance $\leftarrow$ distTo(location, point)

17 scores[point] $\leftarrow$ – distance

18 closestCluster $\leftarrow$ getClosestCluster(objectClusters, point)

19 $i\leftarrow$ clusterID(closestCluster)

20 if  _dist(closestCluster, point) $<\delta$_ then

// incorporate language scores

21 scores[point] $\leftarrow w_{p}\cdot$ ${LLM}_{pos}$ [$i$] -
$w_{n}\cdot{LLM}_{neg}$ [$i$] - distance

22

23 subgoal $\leftarrow$ argmax(scores)

24

25 numSteps $\leftarrow$ numSteps $+1$

26 goTo(subGoal)

Algorithm 4 Instantiating LFG with Geometric Mapping

###  A.4 More Experiment Rollouts

Figure 6 shows an example where the negative scoring is essential to LFG’s
success. Figures 7 and 8 show examples of LFG deployed in a previously unseen
apartment and an office building, successfully exploring the environments to
find an oven and a kitchen sink.

Figure 6: Tolerance to LLM failures. An example rollout of LFG compensating
for LLM failure. FBE takes over in this case and eventually succeeds, whereas
the Greedy agent fails. Figure 7: LFG in an unseen apartment. The robot starts
in the same starting location and environment as 5, and is tasked with finding
an oven. LFG guides the robot towards the kitchen appliances, rather than the
bedroom door, and successfully leads to the oven. Figure 8: LFG in an unseen
office building. The agent looks for a sink in an open-plan office building.
Despite erroneous detections, the robot continues exploring the environment,
with LFG guiding it towards frontiers containing appliances found in a cafe.
The robot successfully finds the sink despite imperfect detections.

##  Appendix B Prompts

###  B.1 Positive Prompt

⬇

You are a robot exploring an environment for the first time. You will be given
an object to look for and should provide guidance of where to explore based on
a series of observations. Observations will be given as a list of object
clusters numbered 1 to N.

Your job is to provide guidance about where we should explore next. For
example if we are in a house and looking for a tv we should explore areas that
typically have tv’s such as bedrooms and living rooms.

You should always provide reasoning along with a number identifying where we
should explore. If there are multiple right answers you should separate them
with commas. Always include Reasoning: <your reasoning> and Answer: <your
answer(s)>. If there are no suitable answers leave the space afters Answer:
blank.

Example

User:

I observe the following clusters of objects while exploring a house:

1. sofa, tv, speaker

2. desk, chair, computer

3. sink, microwave, refrigerator

Where should I search next if I am looking for a knife?

Assistant:

Reasoning: Knifes are typically kept in the kitchen and a sink, microwave, and
refrigerator are commonly found in kitchens. Therefore we should check the
cluster that is likely to be a kitchen first.

Answer: 3

Other considerations

1. Disregard the frequency of the objects listed on each line. If there are multiple of the same item in a cluster it will only be listed once in that cluster.

2. You will only be given a list of common items found in the environment. You will not be given room labels. Use your best judgement when determining what room a cluster of objects is likely to belong to.

###  B.2 Negative Prompt

⬇

You are a robot exploring an environment for the first time. You will be given
an object to look for and should provide guidance of where to explore based on
a series of observations. Observations will be given as a list of object
clusters numbered 1 to N.

Your job is to provide guidance about where we should not waste time
exploring. For example if we are in a house and looking for a tv we should not
waste time looking in the bathroom. It is your job to point this out.

You should always provide reasoning along with a number identifying where we
should not explore. If there are multiple right answers you should separate
them with commas. Always include Reasoning: <your reasoning> and Answer: <your
answer(s)>. If there are no suitable answers leave the space afters Answer:
blank.

Example

User:

I observe the following clusters of objects while exploring a house:

1. sofa, tv, speaker

2. desk, chair, computer

3. sink, microwave, refrigerator

Where should I avoid spending time searching if I am looking for a knife?

Assistant:

Reasoning: Knifes are typically not kept in a living room or office space
which is what the objects in 1 and 2 suggest. Therefore you should avoid
looking in 1 and 2.

Answer: 1,2

Other considerations

1. Disregard the frequency of the objects listed on each line. If there are multiple of the same item in a cluster it will only be listed once in that cluster.

2. You will only be given a list of common items found in the environment. You will not be given room labels. Use your best judgement when determining what room a cluster of objects is likely to belong to.