# Modified contact simplex iteration

Sergei Drozdov111email<EMAIL_ADDRESS>
###### Abstract

We study the iterations of the procedure of taking the contact simplex. We
define the concept of the root of the simplex, which is a homothety image of
contact simplex with a special coefficient greater than 1. The article shows
that once we iterate the root of a given simplex, the circumcenter sequence of
these simplices has two partial limits.

##  1 Introduction

Consider triangle $S,$ and its inscribed circle $C.$ Then the triangle formed
by the points of intersection of $S$ and $C$ is called the contact triangle
(also known as Gergonne triangle or intouch triangle) of $S$. If we iterate
the procedure of taking the contact triangle, the sequence obtained will
converge to the equilateral triangle (if the proper normalisation is applied).
This follows, for example, from the fact that on each step we switch from the
triangle with the angles
$\left(\frac{\pi}{3}+\alpha,\frac{\pi}{3}+\beta,\frac{\pi}{3}+\gamma\right)$
to the triangle with the angles
$\left(\frac{\pi}{3}-\frac{\alpha}{2},\frac{\pi}{3}-\frac{\beta}{2},\frac{\pi}{3}-\frac{\gamma}{2}\right)$.

Figure 1: Contact triangle iteration.

The same procedure for the euclidian simplex of the higher dimension is
discussed in [1], and for the tetrahedrons in [2]. As shown in these sources,
the sequence of simplices does not have a unique limit, but instead, the
iterations of the odd and even orders have two limits, that are, generally
speaking, different.

We modify the procedure slightly, and instead of normalizing contact
simplices, let them grow (in a special way). We prove the technical Lemma 3.1
and afterward the Theorem 4.1, which shows that the circumcenter sequence of
these simplices has two partial limits.

##  2 Root of the simplex definition

######  Definition 2.1.

Root. Let $S\subset\mathbb{R}^{n}$ be a nondegenerate simplex with $n+1$
vertex. Denote $S$ by $A_{1}A_{2}\dots A_{n+1}.$ Let $I$ and $r$ be the center
and the radius of inscribed sphere of $S$. Let the full-dimension face
opposite to $A_{i}$ be $\Delta_{i}$. $\forall i$ the inscribed sphere touches
$\Delta_{i}$ at some point $B_{i}.$ Let the radius of circumscribed sphere of
$S$ be $R,$ and consider space transformation $K$, which is the composition of
the inversion with radius $R$ and center $I$ and a central symmetry, centered
at point $I.$ Then, the simplex $K(B_{1})K(B_{2})\dots K(B_{n+1})$ is called
the root of the simplex $S.$ See Figure 2.

Denote it as $Root(S)$.

Figure 2: $Root(\triangle A_{1}A_{2}A_{3})=\triangle
K(B_{1})K(B_{2})K(B_{3})$.

######  Property 2.2.

Let $S\subset\mathbb{R}^{n}$ be a nondegenerate simplex and $T=Root(S).$ Then
$T$ is homothetic to the contact simplex of $S.$ And also, $I$ and
$\frac{R^{2}}{r}$ are the center and the radius of the circumscribed sphere of
$T.$

###### Proof.

In the notation of the Definition 2.1 the center and the radius of the
circumscribed sphere of the simplex $B_{1}\dots B_{n+1}$ are $I$ and $r.$
Simplex $B_{1}\dots B_{n+1}$ is the contact simplex of $A_{1}\dots A_{n+1}.$
The pointwise inversion image of $B_{1}\dots B_{n+1}$ is homothetic to
$B_{1}\dots B_{n+1}$ with the coefficient $\frac{R^{2}}{r^{2}}$. If the apply
central symmetry, centered at point $I,$ the resulting image is homothetic to
$B_{1}\dots B_{n+1}$ with the coefficient $-\frac{R^{2}}{r^{2}}$. Thus,
simplex $T$ has the circumscribed sphere with the same center $I$ and with the
radius equal $r\cdot\frac{R^{2}}{r^{2}}=\frac{R^{2}}{r}.$ ∎

We will further denote simplex $T$ by $C_{1}\dots C_{n+1}.$

######  Property 2.3.

In the notation of the Definition 2.1, $\forall i\neq j:1\leqslant
i,j\leqslant n+1$

$\overrightarrow{IC_{i}}\cdot\overrightarrow{IA_{j}}=-R^{2}$ (1)

###### Proof.

$\overrightarrow{IC_{i}}\cdot\overrightarrow{IA_{j}}=-\frac{R^{2}}{r^{2}}\cdot\overrightarrow{IB_{i}}\cdot\overrightarrow{IA_{j}},$
(2)

and since $I$ is the center of inscribed sphere of $S$, and so $IB_{i}\perp
B_{i}A_{j},$ we can continue:

$-\frac{R^{2}}{r^{2}}\cdot\overrightarrow{IB_{i}}\cdot\overrightarrow{IA_{j}}=-\frac{R^{2}}{r^{2}}\cdot
IB_{i}^{2}=-\frac{R^{2}}{r^{2}}\cdot r^{2}=-R^{2}$ (3)

∎

######  Property 2.4.

$I\in Int(T)$

###### Proof.

As it is shown in [3], in Theorem 3, the circumcenter of simplex $B_{1}\dots
B_{n+1}$ is an interior point of $B_{1}\dots B_{n+1}.$ So, since $T$ is
homothetic to $B_{1}\dots B_{n+1},$ the circumcenter of $T$ is an interior
point of $T.$ ∎

##  3 Root of the simplex contains the simplex circumscribed sphere

######  Lemma 3.1.

Let $S\subset\mathbb{R}^{n}$ be the simplex, and $T=Root(S).$ Then $T$
contains the circumscribed sphere of $S.$

###### Proof.

Figure 3: Statement of the Lemma 3.1 for the triangle ($n=2$): $\triangle
C_{1}C_{2}C_{3}$ contains the circumscribed circle of $\triangle
A_{1}A_{2}A_{3}.$

(Please notice that here we meet the circumscribed sphere of $S$ for the first
time. See Figure 3.)

Let again $S=A_{1}\dots A_{n+1},$ and denote $T$ by $C_{1}\dots C_{n+1}$. Let
$O$ and $I$ be the centers of the circumscribed and inscribed spheres of $S.$
Denote the hyperplane containing the full-dimension face of $T$, that is
opposite to $C_{i}$ by $\Gamma_{i}$. So

$\Gamma_{i}:=Lin\left<C_{1}\dots C_{i-1}C_{i+1}\dots C_{n+1}\right>.$ (4)

From the Property 1 $\forall j\neq
i\quad\overrightarrow{IC_{j}}\cdot\overrightarrow{IA_{i}}=-R^{2},$ where $R$
is the radius of circumscribed sphere of $S,$ so

$\Gamma_{i}=\left\\{X:\overrightarrow{IX}\cdot\overrightarrow{IA_{i}}=-R^{2}\right\\}.$
(5)

This leads to

$\Gamma_{i}\perp\overrightarrow{IA_{i}},$ (6)

and if we denote the intersection of $(IA_{i})$ and $\Gamma_{i}$ by $H,$ then

$\overrightarrow{IH}\cdot\overrightarrow{IA_{i}}=-R^{2},$ (7)

or in other words,

$\left\\{\begin{aligned} I\in[HA_{i}]\\\ |IH|\cdot|IA_{i}|=R^{2}.\\\
\end{aligned}\right.$ (8)

See Figure 4.

Figure 4: Point $H$ definition.

Now let’s consider the point $O,$ and let the projection of $O$ on
$\Gamma_{i}$ be $G.$ See Figure 5.

Figure 5: Point $G$ definition

$|HA_{i}|=|HI|+|IA_{i}|\geqslant 2\sqrt{|HI|\cdot|IA_{i}|}=2\sqrt{R^{2}}=2R.$
(9)

Since $|OA_{i}|=R,$ we can say:

$|A_{i}H|\leqslant|A_{i}O|+|OG|=R+|OG|$ (10) $|OG|\geqslant|A_{i}H|-R\geqslant
2R-R=R.$ (11)

It means that the open ball circumscribed around $S$ does not cross the plane
$\Gamma_{i}.$ The same holds for all $i=1,..,n+1.$ So, the ball does not cross
any of the faces of $T.$ The only part left is to show that it lies inside
$T,$ and not outside.

The hyperplane $\Gamma_{i}$ cuts the space in two half-spaces. Let $\Pi_{i}$
be the half-space containing the ball circumscribed around $S.$ The inscribed
ball of $S$ is contained inside the circumscribed ball of $S,$ so it also lies
in $\Pi_{i}.$ Then so does its center, point $I.$ So, $I\in\Pi_{i}.$ From the
Property 1, $I\in Int(T),$ so the half-space $\Pi_{i}$ contains not only $I,$
but also the whole simplex $T.$

So, $T=\cap_{i=1}^{n+1}\Pi_{i},$ and since $\forall i$ the half-space
$\Pi_{i}$ contains the circumscribed ball of $S,$ this ball is contained in
$T.$ ∎

######  Corollary 3.2.

Let $S\subset\mathbb{R}^{n}$ be a simplex with $n+1$ vertices. $T=Root(S).$
Let $(r_{1},R_{1})$ be the radii of inscribed and circumscribed spheres of
$S,$ and $(r_{2},R_{2})$ be the radii of inscribed and circumscribed spheres
of $T.$ Then

$\frac{r_{2}}{R_{2}}\geqslant\frac{r_{1}}{R_{1}}$ (12)

###### Proof.

From Property 2.2, $R_{2}=\frac{R_{1}^{2}}{r_{1}},$ from Lemma 3.1 the
circumscribed sphere of $S$ lies inside $T.$ Any sphere inside $T$ has radius
no larger than the radius of inscribed sphere of $T.$ So

$R_{1}\leqslant r_{2},$ (13)

and

$\frac{r_{2}}{R_{2}}=\frac{r_{2}}{\frac{R_{1}^{2}}{r_{1}}}=\frac{r_{1}r_{2}}{R_{1}^{2}}\geqslant\frac{r_{1}R_{1}}{R_{1}^{2}}=\frac{r_{1}}{R_{1}}.$
(14)

∎

######  Corollary 3.3.

Let $S_{1}\in\mathbb{R}^{n}$ be a simplex with $n+1$ vertices. For every
$k\geqslant 1$ define $S_{k+1}:=Root(S_{k}),$ and let $(r_{k},R_{k})$ be the
radii of inscribed and circumscribed spheres of $S_{k}.$ Then
$\frac{r_{k}}{R_{k}}$ converges as $k\to\infty.$ Also, denote
$\lim\limits_{k\to\infty}\frac{r_{k}}{R_{k}}=\rho,$ then $\forall
k\enskip\frac{r_{k}}{R_{k}}\leqslant\rho$

###### Proof.

$\frac{r_{k}}{R_{k}}$ is non-decreasing, and $\forall k\enskip r_{k}<R_{k}.$
So $\frac{r_{k}}{R_{k}}$ converges. ∎

######  Property 3.4.

In the notation as above,
$\lim\limits_{k\to\infty}\frac{r_{k}}{R_{k}}\leqslant\frac{1}{n-1}.$

###### Proof.

Since, for any $n+1-$vertex simplex in $\mathbb{R}^{n},$ with the radii of
inscribed and circumscribed spheres $r$ and $R$ holds
$\frac{r}{R}\leqslant\frac{1}{n-1},$ then for all $k$ holds
$\frac{r_{k}}{R_{k}}\leqslant\frac{1}{n-1},$ so the limit of
$\frac{r_{k}}{R_{k}}$ is smaller than or equals $\frac{1}{n-1}.$ ∎

######  Property 3.5.

In the notation as above, if $n=2$ ($S_{1}$ is a triangle), then
$\lim\limits_{k\to\infty}\frac{r_{k}}{R_{k}}=\frac{1}{2}.$

###### Proof.

If $n=2,$ the angles of $S_{k}$ converge to $\frac{\pi}{3},$ as $k\to\infty.$
In the neighborhood of the equilateral triangle, the factor of the radii of
inscribed and circumscribed circles of a triangle is a continuous function of
the angles. So this factor converges to the value of the factor in the
equilateral triangle. There it equals $\frac{1}{2}.$ ∎

##  4 Main result

######  Theorem 4.1.

Let $S_{1}\in\mathbb{R}^{n}$ be a simplex with $n+1$ vertices. For every
$k\geqslant 1$ define $S_{k+1}:=Root(S_{k}),$ and let $(I_{k},O_{k})$ be the
centers of inscribed and circumscribed spheres of $S_{k}.$ Then the sequences

$\left\\{O_{2k+1},k\in\mathbb{N}\right\\}\text{ and
}\left\\{O_{2k},k\in\mathbb{N}\right\\}$ (15)

converge as $k\to\infty.$

###### Proof.

Figure 6: Statement of the Theorem 4.1 for the triangle ($n=2$): given
$S_{1}=\triangle A_{1}A_{2}A_{3},$ point $O_{1}$ being its circumcenter, and
$O_{k}$ being the circumcenter of $Root^{k-1}(S_{1}),k>1,$ sequences
$O_{2},O_{4},O_{6},\dots$ and $O_{1},O_{3},O_{5},\dots$ both have limits in
$\mathbb{R}^{2}.$

(See Figure 6.)

From the Corollary 3.3 the sequence $\frac{r_{k}}{R_{k}}$ has its limit, let’s
call it $\rho.$ Then $\forall\varepsilon>0\enskip\exists K:\forall k\geqslant
K$ we have

$\rho\geqslant\frac{r_{k}}{R_{k}}\geqslant\rho(1-\varepsilon).$ (16)

Assume further that $\varepsilon<\frac{1}{1000}$ for all $k>K_{1},$ and
consider only these $k.$

1\. Estimate on $|I_{k}O_{k}|$ from above.

From Lemma 3.1 the circumscribed sphere of $S_{k}$ lies inside $S_{k+1},$ and
so does its center, point $O_{k}.$

So $O_{k}\in Int(S_{k+1}).$

Since $r_{k+1}\leqslant\rho R_{k+1},$ for any point $X\in Int(S_{k+1})$ the
simplex $S_{k+1}$ has a full-dimension face $\Gamma,$ such that
$dist(X,\Gamma)\leqslant\rho R_{k+1}.$

And so, for $X=O_{k}$ the simplex $S_{k+1}$ has a full-dimension face
$\Gamma,$ such that

$dist(O_{k},\Gamma)\leqslant\rho R_{k+1}.$ (17)

From the Property 2.2 we can get that:

$\rho R_{k+1}=\rho\frac{R_{k}^{2}}{r_{k}}.$ (18)

Using (16) we can continue:

$dist(O_{k},\Gamma)\leqslant\rho\frac{R_{k}^{2}}{r_{k}}\leqslant\frac{\rho
R_{k}}{\rho(1-\varepsilon)}=\frac{R_{k}}{1-\varepsilon}.$ (19)

Denote the vertex of $S_{k}$ corresponding to $\Gamma$ by $A$ ($\Gamma$ is a
face of $S_{k+1}$, not $S_{k}$, so it is not ”opposite” in the regular sense).

Let the projection of $O_{k}$ on $\Gamma$ be $G.$ Let the intersection of
$(AI_{k})$ and $\Gamma$ be $H.$ From (6) we know that $AH\perp\Gamma.$ See
Figure 7.

Figure 7: Points $G$ and $H$.

We will further write $R$ instead of $R_{k}.$ Remember that from (9) we have

$|AH|\geqslant 2R.$ (20)

Let the projection of $O_{k}$ on $AH$ be $X.$ See Figure 8.

Figure 8: Point $X$ definition.

From (19) we have:

$|XH|=|O_{k}G|=dist(O_{k},\Gamma)\leqslant\frac{R}{1-\varepsilon}.$ (21)

For $\varepsilon<\frac{1}{2}$ we get two corollaries from the combination of
(20) and (21): first is that, since $O_{k},X,A$ all lie in the same half-space
with respect to $\Gamma,$ $X$ lies inside the interval $[AH],$ and second is:

$|AX|=|AH|-|HX|\geqslant 2R-|HX|\geqslant
2R-\frac{R}{1-\varepsilon}=R\left(2-\frac{1}{1-\varepsilon}\right).$ (22)

There is now a lower bound on $\frac{|AX|}{R}.$ More specifically, we know,
that as $\varepsilon\to 0,\enskip\frac{|AX|}{R}\to 1.$ And also, $|AX|$ is a
cathetus in the right triangle $\triangle XAO_{k},$ with the hypothenuse
$O_{k}A$ equal $R.$ This allows estimating from above $\angle HAO_{k}.$

Let $\alpha:=\angle HAO_{k},$ then first, $\alpha<\frac{\pi}{2}.$ Since
$AX=R\cos\alpha:$

$R\cos\alpha\geqslant R\left(2-\frac{1}{1-\varepsilon}\right).$ (23)

From (23) we have:

$\cos\alpha\geqslant 2-\frac{1}{1-\varepsilon}$ (24)
$\alpha\leqslant\arccos\left(2-\frac{1}{1-\varepsilon}\right)$ (25)

(which means that $\alpha\to 0,$ as $\varepsilon\to 0$).

Let $O^{\prime}\in[AH]$ be a point, such that $|O^{\prime}A|=R.$ Such point
exists since $|AH|\geqslant 2R.$ See Figure 9.

Figure 9: Point $O^{\prime}$ definition.

$|O_{k}A|=|O^{\prime}A|=R.$ The length of the interval $[O_{k}O^{\prime}]$ is
no larger than the length of the arc
$\stackrel{{\scriptstyle\mbox{\large$\frown$}}}{{O_{k}O^{\prime}}}$ in the
circle with radius $R$ and center $A.$ Combining this with (25) we get:

$|O_{k}O^{\prime}|\leqslant R\alpha\leqslant
R\arccos\left(2-\frac{1}{1-\varepsilon}\right).$ (26)

The chapter’s goal is to estimate $|O_{k}I_{k}|$ from above, and we have an
estimate on $|O^{\prime}O_{k}|.$ Since
$|O_{k}I_{k}|\leqslant|O_{k}O^{\prime}|+|O^{\prime}I_{k}|,$ it is only left to
estimate $|O^{\prime}I_{k}|$ from above.

First, using that $\angle O_{k}XA=\frac{\pi}{2},$ and (21) we estimate $|AH|:$

$|AH|=|AX|+|XH|\leqslant R+|XH|\leqslant
R+\frac{R}{1-\varepsilon}=R\left(1+\frac{1}{1-\varepsilon}\right).$ (27)

Now, (8) says:

$|AI_{k}|\cdot|I_{k}H|=R^{2}.$ (28)

Let’s denote $|AI_{k}|-|AO^{\prime}|=|AI_{k}|-R,$ the oriented length of
$O^{\prime}I_{k}$ by $z.$ Then

$|AH|=|AI_{k}|+|I_{k}H|=|AI_{k}|+\frac{R^{2}}{|AI_{k}|}=R+z+\frac{R^{2}}{R+z}.$
(29)

Combining (27) and (29) we get:

$R+z+\frac{R^{2}}{R+z}\leqslant R\left(1+\frac{1}{1-\varepsilon}\right),$ (30)

and dividing both parts by $R,$ we write:

$1+\frac{z}{R}+\frac{1}{1+\frac{z}{R}}\leqslant 1+\frac{1}{1-\varepsilon},$
(31)

Denote $\frac{z}{R}$ by $y.$ So

$1+y+\frac{1}{1+y}\leqslant 1+\frac{1}{1-\varepsilon}.$ (32)

As we assumed, that $k>K_{1}$ in the beginning, and so
$\varepsilon<\frac{1}{1000},$ we can use the Taylor expansion for
$\varepsilon$, and write that

$1+\frac{1}{1-\varepsilon}=1+1+\varepsilon+\varepsilon^{2}+\dots\leqslant
2+2\varepsilon,$ (33)

and so:

$1+y+\frac{1}{1+y}\leqslant 2+2\varepsilon.$ (34)

As the denominator $1+y$ is larger than 0 (it is equal to
$\frac{|AI_{k}|}{R}$), we can multiply by $1+y$, and obtain:

$(1+y)^{2}+1\leqslant(1+y)(2+2\varepsilon),$ (35)

so

$y^{2}+2y+2\leqslant 2+2y+2\varepsilon y+2\varepsilon,$ (36)

so

$y^{2}-2\varepsilon y\leqslant 2\varepsilon,$ (37)

so

$(y-\varepsilon)^{2}\leqslant 2\varepsilon+\varepsilon^{2},$ (38)

so

$|y|\leqslant\sqrt{2\varepsilon+\varepsilon^{2}}+\varepsilon.$ (39)

Which is exactly the estimate on $\frac{|O^{\prime}I_{k}|}{R},$ that we wanted
to obtain:

$\frac{|O^{\prime}I_{k}|}{R}\leqslant\sqrt{2\varepsilon+\varepsilon^{2}}+\varepsilon.$
(40)

Now, combining inequalities (26) and (40), we get that if $k>K_{1}$ (and so
$\varepsilon<\frac{1}{1000}$):

$\frac{|O_{k}I_{k}|}{R}\leqslant\frac{|O_{k}O^{\prime}|+|O^{\prime}I_{k}|}{R}\leqslant\arccos\left(2-\frac{1}{1-\varepsilon}\right)+(\sqrt{2\varepsilon+\varepsilon^{2}}+\varepsilon).$
(41)

So

$\forall\delta>0\enskip\exists K:\forall
k>K\quad\frac{|I_{k}O_{k}|}{R_{k}}<\delta,$ (42)

or in other words:

$\forall\delta>0\enskip\exists K:\forall k>K\quad|I_{k}O_{k}|<\delta|R_{k}|.$
(43)

2\. Estimate on $|O_{k}O_{k+2}|$ from above. Now let’s show that $O_{k+2}$ is
close to $O_{k}.$ Denote $|O_{k}I_{k}|$ by $d.$ Let’s instead of $R_{k},$
again write $R$ for the radius of circumscribed sphere of $S_{k}.$ Consider
such $K_{2}>K_{1},$ that $\forall k>K_{2}$ holds $\frac{d}{R}<\frac{1}{1000}.$

Consider further only these $k>K_{2}.$

We will reuse the names of the points from the previous chapter, with only
difference, that $\Gamma$ can be any full-dimension face of $S_{k+1},$ not
only the one closest to $O_{k}$.

Figure 10: Estimate on $O_{k}O_{k+2}$ from above.

From (8) it follows:

$|AH|=|AI_{k}|+|I_{k}H|=|AI_{k}|+\frac{R^{2}}{|AI_{k}|}.$ (44)

From the triangle inequality for $\triangle I_{k}O_{k}A,$ we estimate
$|AI_{k}|:$

$R-d\leqslant|AI_{k}|\leqslant R+d,$ (45)

so, as $f(x)=x+\frac{R^{2}}{x}$ is convex for $x>0,$ and attains maximal value
on the interval at one of the intervals ends:

$|AH|\leqslant\max\left\\{(R+d)+\frac{R^{2}}{R+d},(R-d)+\frac{R^{2}}{R-d}\right\\}.$
(46)

Denote $\frac{d}{R}$ by $\delta.$ So, (46) is equivalent to:

$|AH|\leqslant
R\max\left\\{(1+\delta)+\frac{1}{1+\delta},(1-\delta)+\frac{1}{1-\delta}\right\\}.$
(47)

Remember that as $k>K_{2},$ we have $\delta<\frac{1}{1000},$ which leads to:

$\max\left\\{1+\delta+\frac{1}{1+\delta},1-\delta+\frac{1}{1-\delta}\right\\}\leqslant
2+2\delta^{2}.$ (48)

So

$|AH|\leqslant R(2+2\delta^{2}).$ (49)

On the other hand, since $|O_{k}X|\leqslant|O_{k}I_{k}|=d$ we get:

$|XA|=\sqrt{R^{2}-|O_{k}X|^{2}}\geqslant\sqrt{R^{2}-d^{2}}=R\sqrt{1-\delta^{2}}\geqslant
R(1-\delta^{2}).$ (50)

Point $X$ lies inside the interval $[AH]$: since otherwise
$d=|O_{k}O_{k+1}|\geqslant|AX|\geqslant R(1-\delta^{2}).$ (Reader may notice
that we have already shown in the previous chapter that $X$ lies on $[AH].$ We
did, but only for one face $\Gamma$ of $S_{k+1}.$) Now, combining inequalities
(49) and (50) we get

$|O_{k}G|=|AH|-|AX|\leqslant
R(2+2\delta^{2}-(1-\delta^{2}))=R(1+3\delta^{2})=R+\frac{3d^{2}}{R}.$ (51)

In the Lemma 3.1, in (11) we had a lower bound on $|O_{k}G|$, so together

$R\leqslant|O_{k}G|\leqslant R+\frac{3d^{2}}{R}.$ (52)

Starting from now let’s again write $R_{k},$ not $R.$

Let’s look again at the whole simplex $S_{k+1}$ (we used to only look at one
of its full-dimension faces, $\Gamma$). Its radius of inscribed sphere equals
$r_{k+1},$ and $I_{k+1}$ is its center of inscribed sphere. In the Lemma 3.1,
in (13), we’ve shown that

$r_{k+1}\geqslant R_{k}.$ (53)

Consider the smaller simplex $S^{\prime}_{k+1},$ that is homothetic to
$S_{k+1}$ with the coefficient $\frac{r_{k+1}-R_{k}}{r_{k+1}}$ (which is
greater or equal than 0) and center $I_{k+1}.$ Simplex $S^{\prime}_{k+1}$ can
be a single point. See Figure 11.

Figure 11: Simplices $S_{k+1}$ and $S^{\prime}_{k+1}$.

The radius of the inscribed sphere of $S^{\prime}_{k+1}$ is, by construction,
$r_{k+1}-R_{k}$, which is the distance from $I_{k+1}$ to any of the full-
dimension faces of $S^{\prime}_{k+1}.$ So, the distance between the parallel
full-dimension faces of $S_{k+1}$ and $S^{\prime}_{k+1}$ equals
$r_{k+1}-(r_{k+1}-R_{k})=R_{k}.$

We now aim to show, that this tiny simplex $S^{\prime}_{k+1}$ contains two
points, mentioned in the beginning of the chapter: $O_{k}$ and $O_{k+2}.$ It
is very simple with the point $O_{k+2},$ indeed, since
$S_{k+2}=Root(S_{k+1}),$ from the Property 2.2, points $I_{k+1}$ and $O_{k+2}$
coincide:

$I_{k+1}=O_{k+2},$ (54)

and $I_{k+1}$ is the center of inscribed sphere of $S^{\prime}_{k+1},$ so it
lies inside $S^{\prime}_{k+1}$.

Now fix some full-dimensional face of $S_{k+1},$ let’s call it $\Gamma.$ It
divides the space into two half-spaces, let’s denote one containing $S_{k+1}$
by $\Pi.$

Let the image of $\Gamma,$ after the homothety transforming $S_{k+1}$ into
$S^{\prime}_{k+1}$ be $\Gamma^{\prime},$ and the image of $\Pi$ be
$\Pi^{\prime}.$ Since $I_{k+1},$ the center of homothety lies in $\Pi,$ then
$\Pi^{\prime}\subset\Pi.$

From the Lemma 3.1 the circumscribed sphere of $S_{k}$ lies inside $S_{k+1},$
and so does its center, $O_{k}.$ So $O_{k}\in\Pi.$ The distance from $O_{k}$
to $\Gamma$ is in the interval $[R_{k};R_{k}+\frac{3d^{2}}{R_{k}}]$, see (52).
This means that since the distance between $\Gamma$ and $\Gamma^{\prime}$
equals $R_{k}$, that $O_{k}\in\Pi^{\prime},$ and distance from $O_{k}$ to
$\Gamma^{\prime}$ is smaller or equal than
$(R_{k}+\frac{3d^{2}}{R_{k}})-R_{k}=\frac{3d^{2}}{R_{k}}.$

Repeating this argument for all full-dimension faces of $S_{k+1},$ we obtain
that $O_{k}$ lies inside $S^{\prime}_{k+1},$ as $S^{\prime}_{k+1}$ is the
intersection of $n+1$ half-spaces in the family of $\Pi^{\prime}.$

Now, as we’ve shown that $O_{k},O_{k+2}\in S^{\prime}_{k+1},$ let’s prove that
this simplex is indeed small. First, if $S^{\prime}_{k+1}$ is a point, then
$|O_{k}O_{k+2}|=0,$ and any upper bound holds. If $S^{\prime}_{k+1}$ is not a
point, let’s continue.

The distance from $O_{k}$ to all full-dimension faces of $S^{\prime}_{k+1}$ is
no larger than $\frac{3d^{2}}{R_{k}}.$ This means that the radius of the
inscribed sphere of $S^{\prime}_{k+1}$ is no larger than
$\frac{3d^{2}}{R_{k}}$ The simplices $S_{k+1}$ and $S^{\prime}_{k+1}$ are
homothetic, so if the radii of inscribed and circumscribed spheres of
$S^{\prime}_{k+1}$ are $r^{\prime}_{k+1}$ and $R^{\prime}_{k+1},$ then from
(16):

$\frac{r^{\prime}_{k+1}}{R^{\prime}_{k+1}}=\frac{r_{k+1}}{R_{k+1}}\geqslant\rho(1-\varepsilon).$
(55)

So,

$R^{\prime}_{k+1}\leqslant\frac{r^{\prime}_{k+1}}{\rho(1-\varepsilon)}\leqslant\frac{3d^{2}}{\rho(1-\varepsilon)R_{k}},$
(56)

which means that since both $O_{k},O_{k+2}\in S^{\prime}_{k+1}$ then

$|O_{k}O_{k+2}|\leqslant
2R^{\prime}_{k+1}\leqslant\frac{6d^{2}}{\rho(1-\varepsilon)R_{k}}=\frac{6|O_{k}O_{k+1}|^{2}}{\rho(1-\varepsilon)R_{k}},\text{
for }k>K_{2}.$ (57)

And since for $k>K_{2}$ holds $\varepsilon<\frac{1}{2},$ then:

$|O_{k}O_{k+2}|\leqslant\frac{12|O_{k}O_{k+1}|^{2}}{\rho R_{k}},\text{ for
}k>K_{2}.$ (58)

3\. Sequence $\\{O_{2k},k\in\mathbb{N}\\}$ is a Cauchy sequence. We have shown
that points $O_{2k}$ and $O_{2k+2}$ are close to each other for sufficiently
large $k.$ If we also can show, that
$\sum\limits_{k=1}^{\infty}|O_{2k}O_{2k+2}|<\infty,$ this will lead to
$|O_{2k}O_{2l}|\to 0,\enskip k,l\to\infty,$ meaning that $O_{2k}$ is a Cauchy
sequence, and so, has a limit in $\mathbb{R}^{n}$

From Property (2.2) and Corollary (3.3) we know

$R_{k+1}=R_{k}\cdot\frac{R_{k}}{r_{k}}\geqslant\frac{R_{k}}{\rho}.$ (59)

So, since we know from the Property 3.4, that $\rho\leqslant\frac{1}{n-1}$,
then $R_{k}$ grows fast, more precisely :

$R_{k}\geqslant R_{1}\left(\frac{1}{\rho}\right)^{k-1}.$ (60)

Let $c:=\frac{12}{\rho},$ and denote $d_{k}:=|O_{k}O_{k+1}|.$

Then for $k>K_{2}$ from (58) we get:

$d_{k+1}=|O_{k+1}O_{k+2}|\leqslant|O_{k+1}O_{k}|+|O_{k}O_{k+2}|\leqslant
d_{k}+\frac{cd_{k}^{2}}{R_{k}}.$ (61)

Let $\varepsilon_{2}>0$ be a small real number, such that

$\frac{(1+c\varepsilon_{2})^{2}}{\frac{1}{\rho}}<\frac{1}{2}$ (62)

From (43) we have: for this $\varepsilon_{2}$ there exists such $K_{3}>K_{2},$
that for all $k>K_{3}$ holds:

$\frac{d_{k}}{R_{k}}\leqslant\varepsilon_{2},$ (63)

so for $k>K_{3}$ the combination of (61) and (63) gives:

$d_{k+1}\leqslant d_{k}+\frac{cd_{k}^{2}}{R_{k}}\leqslant
d_{k}+c\varepsilon_{2}d_{k}=(1+c\varepsilon_{2})d_{k},$ (64)

so for some large $C>0$ and for all $k$

$d_{k}\leqslant C(1+c\varepsilon_{2})^{k}.$ (65)

We can now continue the estimate on $|O_{k}O_{k+2}|,$ in (58), for $k>K_{2}.$
First, equivalently to (58):

$|O_{k}O_{k+2}|\leqslant\frac{cd_{k}^{2}}{R_{k}},$ (66)

then from (60) for all $k$:

$\frac{cd_{k}^{2}}{R_{k}}\leqslant\frac{cd_{k}^{2}}{R_{1}\left(\frac{1}{\rho}\right)^{k-1}},$
(67)

then from (65), for all $k:$

$\frac{cd_{k}^{2}}{R_{1}\left(\frac{1}{\rho}\right)^{k-1}}\leqslant\frac{c\cdot
C^{2}(1+c\varepsilon_{2})^{2k}}{R_{1}\left(\frac{1}{\rho}\right)^{k-1}}=\frac{c\cdot
C^{2}}{\rho
R_{1}}\left(\frac{(1+c\varepsilon_{2})^{2}}{\frac{1}{\rho}}\right)^{k}.$ (68)

So, for $k>K_{2}$:

$|O_{k}O_{k+2}|\leqslant\frac{c\cdot C^{2}}{\rho
R_{1}}\left(\frac{(1+c\varepsilon_{2})^{2}}{\frac{1}{\rho}}\right)^{k}.$ (69)

And from (62), for $k>K_{2}$:

$|O_{k}O_{k+2}|\leqslant\frac{c\cdot C^{2}}{\rho
R_{1}}\left(\frac{1}{2}\right)^{k}.$ (70)

The sum of the geometric progression with a ratio smaller than 1 is finite. So
the sequence $\\{O_{2k}\\}$ is a Cauchy sequence, and so it has a limit in
$\mathbb{R}^{n}.$

The same argument holds for $\\{O_{2k+1}\\},$ since it is the sequence of even
order circumcenters, with the starting simplex $S_{2}$ instead of $S_{1}.$ ∎

## References

  * [1] fedja (https://mathoverflow.net/users/1131/fedja), “Tetrahedron insphere iteration.” MathOverflow.  URL:https://mathoverflow.net/q/144581 (version: 2013-10-18).
  * [2] J. Brandts and M. Křížek, Duality of isosceles tetrahedra, 2019. J. Geom. (2019) 110:49, Springer Nature Switzerland AG, 2019.
  * [3] J. Brandts and M. Křížek, Simplicial Vertex-Normal Duality with Applications to Well-Centered Simplices. Numerical Mathematics and Advanced Applications ENUMATH 2017. ENUMATH 2017\. Lecture Notes in Computational Science and Engineering, vol 126. Springer, 2019.


# Into the Unknown:
Generating Geospatial Descriptions for New Environments

Tzuf Paz-Argaman  Bar-Ilan University  John Palowitch  Google Research  Sayali
Kulkarni  Google Research
Reut Tsarfaty  Bar-Ilan University  Google Research  Jason Baldridge  Google
Research

###### Abstract

Similar to vision-and-language navigation (VLN) tasks that focus on bridging
the gap between vision and language for embodied navigation, the new
_Rendezvous_ (RVS) task requires reasoning over allocentric spatial
relationships (independent of the observer's viewpoint) using non-sequential
navigation instructions and maps. However, performance substantially drops in
new environments with no training data. Using opensource descriptions paired
with coordinates (e.g., Wikipedia) provides training data but suffers from
limited spatially-oriented text resulting in low geolocation resolution. We
propose a large-scale augmentation method for generating high-quality
synthetic data for new environments using readily available geospatial data.
Our method constructs a _grounded knowledge-graph_ , capturing entity
relationships. Sampled entities and relations (``shop north of school'')
generate navigation instructions via (i) generating numerous templates using
context-free grammar (CFG) to embed specific entities and relations; (ii)
feeding the entities and relation into a large language model (LLM) for
instruction generation. A comprehensive evaluation on RVS, showed that our
approach improves the 100-meter accuracy by 45.83% on unseen environments.
Furthermore, we demonstrate that models trained with CFG-based augmentation
achieve superior performance compared with those trained with LLM-based
augmentation, both in unseen and seen environments. These findings suggest
that the potential advantages of explicitly structuring spatial information
for text-based geospatial reasoning in previously unknown, can unlock data-
scarce scenarios.

Meet me in the garden. Head northwest from St. Vincent de Paul Church for 2
intersections. The garden is right next to a fast-food restaurant. If you
reach a nail salon, you have gone too far.

Figure 1:  Our method for generating spatial descriptions samples from the
graph-map (top) a path (middle image, red line), a starting point (green
marker), a goal point (red marker), and prominent landmarks (black markers).
It then generates an instruction (bottom) from the spatial relations between
these entities.

##  1 Introduction

The ability to extract locations and paths from natural language descriptions
of spatial information holds immense significance. This capability proves
crucial in daily and disaster response scenarios, aiding the billions globally
lacking formal addresses UPU (2012); Abebrese (2019); Hu et al. (2023), and
enhancing Geographic Information Retrieval (GIR), particularly leveraging web-
based resources (Spink et al., 2002; Sanderson and Kohler, 2004).

Echoing the vision-and-language navigation (VLN) task's goal, of bridging the
gap between visual perception and natural language (NL) instructions for
embodied agents Ku et al. (2020), the recently introduced Rendezvous (RVS)
navigation task Paz-Argaman et al. (2024) seeks to achieve a similar
connection, but specifically between map representations and natural language
NL. While VLN focuses on navigating within an environment based on visual cues
and sequential instructions, RVS emphasizes the ability to utilize map
information and non-sequential, often allocentric language descriptions to
reach a specific target location. This shift from vision-centric instructions
to map-aided guidance presents unique challenges, including reasoning about
multiple spatial relationships simultaneously, inferring implicit actions from
language, and navigating without explicit verification or step-by-step
instructions.

However, there is a substantial gap between current models and the human
performance on the RVS task, particularly in new environments that lack human
annotated data. One approach to address this issue is to leverage naturally-
occurring open-source data such as Wikipedia. However, these sources lack
direct spatial information, which can result in models’ low performance Solaz
and Shalumov (2023). Synthesizing data using large language models (LLMs) is a
common method for addressing data scarcity in NLP (Yoo et al., 2021; Edwards
et al., 2021). However, for multimodal scenarios requiring precise spatial
relationships, accurately generating such data without introducing errors or
“hallucinations” (i.e., spurious relationships or entities), which severely
undermines the performance on the underlying downstream task, remains a
significant challenge.

We propose a method for generating high-quality synthetic data for new
environments using open-source geospatial data (Figure 1). Our method
constructs a grounded knowledge-graph of the environment, capturing spatial
relationships between entities. By sampling these entities, abstract shapes
like `blocks' (implicitly derived from street relationships), and relations
(e.g., `the garden is next to a restaurant'), we generate navigation
instructions by either (i) creating a large amount of templates via a
generative context-free grammar (CFG), in which we embed the precise entities
and relations sampled, or (ii) feeding the entities and relation into an LLM
which generates the instructions.

Extensive evaluation on the RVS dataset demonstrates the clear advantage of
our CFG-based method compared to the LLM approach. When navigating unseen
environments, our method achieves a remarkable 9.1% absolute increase in
100-meter accuracy and a substantial 39-meter decrease in median distance
error. Overall, our method helps close the human-AI performance gap in unseen
environments by 45.83% in 100m accuracy and a decrease of 1,183m in median
distance error. For the seen environment, our method results in an absolute
improvement of 19.56% in 100m accuracy and a decrease of 151m in median
distance error.

Figure 2: Instruction generation steps (for example presented in Figure 1):
(i) Template creation via CFG; (ii) replacing generic elements (in capital
letters) with specific landmarks and spatial relations (above the lines).

##  2 The Task

The Rendezvous (RVS, Paz-Argaman et al., 2024) task evaluates a system's
ability to follow human-generated, colloquial language navigation instructions
within a dense urban environment depicted by a map. The system is provided
with three inputs: (i) Detailed Map as Knowledge Graph: a comprehensive map of
the environment represented as a knowledge graph. This graph encodes spatial
relationships between landmarks and other relevant features. (ii) Explicit
Starting Point (Geo-coordinates): the starting location specified as a
latitude and longitude coordinate pair. (iii) Navigation Instruction: a
natural language instruction describing the target location's relative
position to landmarks and the starting point. This instruction leverages
colloquial language typically used in navigation scenarios. The RVS task
demands the system to process these inputs and generate the goal location's
coordinates within the defined map boundaries.

##  3 Proposed: Relational Augmentation

Our augmentation method aims to generate natural language location
descriptions that are both accurate and well grounded. To that end, we
leverage OpenStreetMap (OSM).111OpenStreetMap is a user-updated map of the
world – http://www.openstreetmap.org It involves three stages: (i) sampling
paths; (ii) calculating spatial relations between entities; and (iii)
generating instructions based on the spatial relations calculated in stage
(ii). We use the OSM-based graph provided in RVS for the first and second
parts and provide two methods for generating instructions based on the spatial
relations between entities calculated in that part.

###  3.1 Sampling paths

To generate RVS-like samples accurately, we follow the RVS sampling protocol.
We randomly sample small entities for the end point (the entity’s shape has a
maximum radius of 100 meters). For the start point, we randomly select an
entity that (i) is within 200–2000 meters of the end point; (ii) has a name or
type tag (e.g., a bookshop). This information allows us to refer to the entity
in the instruction by its definite description and not by its proper name.
Finally, we pick a route that is the shortest distance between the start and
end points.

###  3.2 Calculating Spatial Relations between Entities

Leveraging the Open Street Map (OSM) graph, we identify prominent landmarks
relevant to the sampled paths for inclusion in navigation instructions.
However, not all paths necessarily contain all types of landmarks and
features. For instance, if the navigation ends in a dead-end street, landmarks
beyond the leading path might not be relevant to the task. This section
details the criteria for landmark selection and the spatial relations computed
with respect to the start and end points, and the path.

#### Picking landmarks

We pick three different types of landmarks with a certain spatial relation
that will be referenced in the instruction: (i) landmarks close to the end
point (within 100 meters from it); (ii) landmarks along the route; and (iii)
landmarks that are on the same street as the goal location but beyond the
route, such that if the agent keeps on walking beyond the goal, it will reach
that landmark (“beyond landmark”). Priority for landmark selection is given to
those with the highest level of external recognition, as determined by the
following hierarchy: has a Wikipedia or Wikidata222Wikidata is Wikipedia’s
free, open, and interconnected knowledge base. https://www.wikidata.org/ link,
is a brand, is a tourism attraction, is an amenity, is a shop. We randomly
select all landmarks from the most prominent level found. If in the area there
are multiple landmarks of the same type, we group the landmarks according to
their type and quantity (e.g., `two book shops'). If a landmark is far (over
200 meters) from the end point and it has a proper name, we can use its proper
name in the text generation, e.g., ‘the Empire State Building’. If it is near
(less than 200 meters) the end point, we will always use the indefinite name
of the landmark, e.g., ‘a bookshop’.

#### Calculating spatial relations

The objective is to determine the spatial relationship between landmarks and
the end point. There are several ways to describe the relationship between two
entities, such as the number of blocks between them. The spatial relations
calculated are (i) allocentric relations, i.e., cardinal directions, between
landmarks, start and end points. Cardinal direction is calculated by the
bearing $\theta_{\text{degrees}}$ between two points (longitude, latitude),
$(x_{1},y_{1})$ and $(x_{2},y_{2})$:

$\begin{aligned}
\theta_{\text{radians}}&=(\tan^{-1}\left(\sin(\lambda_{2}-\lambda_{1})\cos(\varphi_{2}),\right.\\\
&\qquad\left.\cos(\varphi_{1})\sin(\varphi_{2})\right)\\\
&\qquad\left.-\sin(\varphi_{1})\cos(\varphi_{2})\cos(\lambda_{2}-\lambda_{1})\right)\\\
&\qquad\left.+360^{\circ})\mod 360^{\circ}\right)\\\
\theta_{\text{degrees}}&=\theta_{\text{radians}}\cdot\frac{180^{\circ}}{\pi}\end{aligned}$

(1)

Where $\lambda_{1}=\frac{x_{1}\cdot\pi}{180^{\circ}}$,
$\lambda_{2}=\frac{x_{2}\cdot\pi}{180^{\circ}}$,
$\varphi_{1}=\frac{y_{1}\cdot\pi}{180^{\circ}}$ and
$\varphi_{2}=\frac{y_{2}\cdot\pi}{180^{\circ}}$. Bearings
$\theta_{\text{degrees}}$ fall into different ranges, each with a
corresponding cardinal direction (e.g., `North-West'). (ii) Egocentric
relations between landmarks and end point to the path, e.g., `on the right
side'. To calculate egocentric relations, we rely on two key angles (Eq. 1):
the bearing of the path itself $\theta^{p}_{\text{degrees}}$, and the bearing
of the shortest imaginary line connecting the path to the landmark's point
$\theta^{l}_{\text{degrees}}$:

$\displaystyle\Delta\theta^{l-p}$
$\displaystyle=(\theta^{l}_{\text{degrees}}-\theta^{p}_{\text{degrees}})\mod
360^{\circ}$ (2) $\displaystyle\begin{cases}\text{`RIGHT'},&\text{if
}\Delta\theta^{l-p}<180^{\circ}\\\ \text{`LEFT'},&\text{otherwise}\end{cases}$

`LEFT' and `RIGHT' indicate the landmark’s position relative to the path.
(iii) The number of blocks and intersections the agent must pass through to
reach the end point. (iv) the end point's egocentric and allocentric position
on the block, e.g., `middle of the block' and `north-east corner of the
block'. Allocentric position on the block involves determining the bearing
(Eq. 1) of the path along the block and mapping it to cardinal direction as in
(i).

###  3.3 Data Generation

Based on the sampling and spatial relations' calculations we use two methods
to generate the instruction: via templates created with a CFG Chomsky (1956),
and via prompting an LLM --- for enlarging the vocabulary and the style of the
text.

#### CFG-based Method

Here the key idea is using a CFG to generate templates that can then be
adapted according to the sampled data. The CFG we design requires defining
terminal symbols (lexical elements), nonterminal symbols, and production
rules. The nonterminals contain the main parts of what a path description
contains, such as descriptions around the goal, along the path, what to avoid,
and so on. The terminals contain optional variations, for example, the verb
for the agent to proceed can be `go', `walk', and so on. The grammar creates
templates that are processed into instructions, as demonstrated in Figure 2.
For a given sampled path, we randomly pick a template that contains all the
landmark categories and spatial relations calculated for the path. We then
generate the instruction by replacing the variables in the chosen template
with the corresponding landmarks and spatial relations (e.g.,
`NUMBER_INTERSECTIONS' will be replaced with the actual number of
intersections the agent should walk).

#### Prompting LLMs

Using the aforementioned template-based instructions, we prompted an LLM to
`rephrase the subsequent navigation instruction, ensuring it explains how to
travel from the starting position to the destination: Navigation Instruction',
where the Navigation Instruction is an instruction based on the CFG generation
process. For example, based on the example in Figures 1 and 2 we get the
following sentence: `Head northwest from St. Vincent de Paul Church for 2
intersections. The garden is next to a fast-food restaurant.

##  4 Experimental Setup

###  4.1 Evaluation

We follow the RVS evaluation metrics: (i) 100m accuracy; (ii) 250m accuracy
for coarse-grained evaluation; (iii) mean absolute error distance (MAE); (iv)
median absolute error (Med.AE); (v) maximum absolute error (Max.AE); and (vi)
area under the curve (AUC) of the error distance. Here are the formulas for
evaluating set S with metrics (iii-vi):

$\text{MAE(S)}=\frac{1}{|S|}\sum_{s\in S}dist(loc(s),approx(s))$

(3)

$\text{Med.AE(S)}=\\{dist(loc(s),approx(s))|s\in S\\}_{\lfloor|S|/2\rfloor}$

(4)

$\text{Max.AE(S)}=max(\\{dist(loc(s),approx(s))|s\in S\\})$

(5)

$\text{AUC(S)}=\frac{\int_{0}^{\infty}(\log{dist(loc(s),approx(s))+\epsilon|s\in
S)\uparrow}ds}{\log{H_{max}}\cdot(|S|-1)}$

(6)

Where $\epsilon=1e-5$ and $H_{max}=20,037\cdot 10^{3}$, approximately the
maximum haversine distance.

###  4.2 Models for evaluation

#### T5-model

We test our augmentation method with T5 model, a transformer-based encoder-
decoder model designed with a text-to-text format Raffel et al. (2020). Both
encoder and decoder utilize multi-head, multi-layer self-attention mechanisms
Vaswani et al. (2017). Given input sequence text $X=(x_{1},...,x_{N})$ and a
starting point $p_{s}$, the encoder encodes the instruction and the starting
point's representation such that
$E^{l}=(e^{l}_{1},...,e^{l}_{N},e^{l}_{p_{s}})$ where $l\in L$, representing
the $L$ hierarchical encoded layers. The output of the final encoder layer is
a sequence of hidden vectors $H=(h_{1},...,h_{N},h_{p_{s}})$. The decoder
generates output tokens sequentially, predicting the probability
$p(p_{t}|p_{1:t-1},H)=\operatorname{softmax}(W_{o}\otimes h^{\prime}_{t})$ of
token $p_{t}$ at step $t$, based on the previous outputs and hidden state
$h^{\prime}_{t}$. Importantly, the model is trained with a pre-defined high-
level path $P$ that guides the generation process. This path starts at the
starting point, traverses through prominent landmarks ordered by their
direction relative to the goal, and eventually reaches the goal itself.

#### Non-learning Landmark Baseline

Predicts the location of a prominent landmark (defined in Sec. 3.2) in the map
within a radius of 1 kilometer.

| RVS | Aug-CFG | Aug-Prompt | Aug-WikiGeo
---|---|---|---|---
Avg. Text Length | 43.47 | 33.70 | 37.26 | 24.82
Avg.Entities | 3.98 | 4.01 | 4.00 | 2.20

Table 1:  Statistics over RVS, and augmentation data.

| Method | Training Set | 100m Accuracy | 250m Accuracy | MAE | Med.AE | Max.AE | AUC
---|---|---|---|---|---|---|---|---
|  [HTML]EFEFEFManhattan (Manh) Seen-city Development Results
1 | Human | NA | 88.12 | 95.64 |  00074 |  00004 | 2,996 | 0.10
2 | Landmark | NA | 0.54 | 5.26 |  00776 |  00815 | 1,384 | 0.39
3 | T5 | RVS Train-set |  000027.92 (0.39) |  000052.63 (0.45) |  00000362 (9) |  0000231 (3) |  00002,957 (641) |  00000.32 (0.00)
4 | T5 | Aug-WikiGeo Manh |  000000.00 (0.00) |  000001.54 (0.00) |  0001,085 (0) |  0001,124 (0) |  001,929 (0) |  00000.41 (0.00)
5 | T5 | Aug-CFG Manh |  000028.83 (0.63) |  000046.15 (0.77) |  00000668 (17) |  00000304 (27) |  000004,637 (2,207) |  00000.34 (0.00)
6 | T5 | Aug-Prompt Manh |  000021.32 (0.20) |  000037.01 (0.14) |  00000963 (17) |  00000658 (14) |  000006,731 (1,003) |  00000.36 (0.00)
7 | T5 | Aug-CFG Manh & RVS Train-set |  000045.97 (1.34) |  000064.01 (0.89) |  00000377 (32) |  00000121 (15) |  00005,317 (831) |  0000.3 (0.00)
|  [HTML]EFEFEFPittsburgh (Pitt) Unseen-Development Results
8 | Human | NA | 86.94 | 92.94 |  00099 |  0007 | 2,951 | 0.13
9 | Landmark | NA | 1.47 | 9.48 |  00677 |  0691 | 1,345 | 0.38
10 | T5 | RVS Train-set |  000000.49 (1.47) |  000002.34 (1.44) |  00001,171 (24) |  0001,107 (14) |  00004,701 (101) |  00000.41 (0.00)
11 | T5 | Aug-WikiGeo Pitt |  000000.00 (0.00) |  000002.05 (0.00) |  00000961 (0) |  0000955 (0) |  00001,912 (0.00) |  00000.40 (0.00)
12 | T5 | Aug-CFG Pitt |  0000046.63 (0.54) |  000063.73 (0.41) |  00000466 (5) |  0000120 (1) |  00005,251 (0.00) |  00000.31 (0.00)
13 | T5 | Aug-Prompt Pitt |  0000037.10 (0.49) |  000058.30 (0.34) |  00000492 (5) |  0000159 (1) |  005,251 (0) |  00000.32 (0.00)
14 | T5 | RVS Train-set & Aug-CFG Pitt |  0000046.24 (0.30) |  000062.85 (0.41) |  000000387 (17) |  0000116 (4) |  0005,162 (103) |  00000.30 (0.00)
|  [HTML]EFEFEFPhiladelphia (Phila) Unseen-city Zero-shot Results
15 | Human | NA | 93.64 | 97.97 |  00027 |  0003 | 2,708 | 0.05
16 | Landmark | NA |  01.02 |  07.90 |  00707 |  0713 | 1,384 | 0.38
17 | T5 | RVS Train-set |  0000000.26 (0.05) |  000001.80 (0.27) |  |  0001,362 (43)
---
0001,308 (35) |  00006,911 (454) |  00000.42 (0.00)
18 | T5 | RVS Train-set & Aug-CFG Phila |  000046.09 (0.50) |  000061.66 (0.00) |  0000579 (2) |  0000125 (3) |  00005,774 (715) |  00000.31 (0.01)

Table 2: Results are divided over RVS's test (Philadelphia) and development
sets (Manhattan and Pittsburgh). The distance errors are presented in meters.
For the learning models, we report the mean over three random initializations,
and the standard deviation (STD) is in brackets.

###  4.3 Data

#### RVS

The RVS (Paz-Argaman et al., 2024) dataset serves as a human-level benchmark
for the purpose of evaluating the ability to follow allocentric navigation
instructions based on a map. It consists of English navigation directives,
each paired with a start and end point. The data is divided into four distinct
sets: (i) Training-set \-- containing 7,000 instructions from Manhattan; (ii)
Seen-city development-set \-- containing 1,103 instructions from Manhattan;
(iii) Unseen-city development-set \-- containing 1,023 instructions from
Pittsburgh; (iv) Test-set \-- containing 1,278 instructions from Philadelphia.

The following datasets are all synthetically generated. We generated 200,000
instructions per dataset for each region, with the exception of Aug-WikiGeo:

#### Aug-CFG

Data created with the CFG method described in Section 3. The CFG method
created 194,721 templates with 15 production rules. The vocabulary contains
only unique 111 tokens. Table 1 shows that this method produces shorter
instructions than the RVS, but with more entities in each instruction. Figures
1 and 2 show an example of an instruction generated based on this method.

#### Aug-CFG-Allocentric

Data created with a CFG including templates with allocentric spatial relations
between entities. E.g., `the school is north of the bar'. The data contains
69,720 templates.

#### Aug-CFG-Egocentric

Data created using a CFG which contains templates with egocentric spatial
relations between entities, e.g., `the bar on your right'. The data contains
112,640 templates.

#### Aug-CFG-Minimal

This dataset leverages a minimal set of templates (64) to represent the full
range of entities and spatial relationships found in the Aug-CFG data. We
constructed Aug-CFG-Minimal using a greedy selection process. We began by
selecting the first template. Subsequently, we added templates that introduced
new spatial features not covered by the existing set. This process continued
until we reached a final set of 64 templates that comprehensively capture all
possible spatial features.

#### Aug-Prompt

Data generated by prompting PaLM2 Anil et al. (2023) with the prompting method
described in Section 3.333We use PaLM2 ‘models/text-bison-001’ - for more
details, see https://developers.generativeai.google Table 1 shows that this
method produces longer instructions than the CFG-based method but with fewer
entities.

| Method | Training Set | 100m Accuracy | 250m Accuracy | MAE | Med.AE | Max.AE | AUC
---|---|---|---|---|---|---|---|---
|  [HTML]EFEFEFManhattan (Manh) Seen-city Development Results
1 | T5 | Aug-CFG Manh |  000028.83 (0.63) |  000046.15 (0.77) |  00000668 (17) |  00000304 (27) |  000004,637 (2,207) |  00000.34 (0.00)
2 | T5 | Aug-CFG-Allocentric Manh |  000029.83 (1.22) |  000047.96 (2.95) |  00000681 (39) |  00000310 (66) |  0006,446 (88) |  00000.34 (0.01)
3 | T5 | Aug-CFG-Egocentric Manh |  000028.83 (0.38) |  000045.87 (0.13) |  00000751 (29) |  0000384 (5) |  0004,572 (77) |  00000.35 (0.00)
4 | T5 | Aug-CFG-Minimal Manh |  000023.21 (0.39) |  000039.62 (0.13) |  00000880 (12) |  00000567 (47) |  000005,463 (2,228) |  00000.36 (0.00)
5 | T5 | Aug-Dummy Manh |  00001.35 (0.13) |  00005.62 (0.13) |  000001,240 (28) |  000001,130 (41) |  000004,654 (0.00) |  00000.41 (0.00)
|  [HTML]EFEFEFPittsburgh (Pitt) Unseen-Development Results
6 | T5 | Aug-CFG Pitt |  0000046.63 (0.54) |  000063.73 (0.41) |  00000466 (5) |  0000120 (1) |  00005,251 (0.00) |  00000.31 (0.00)
7 | T5 | Aug-CFG-Allocentric Pitt |  0000045.94 (0.48) |  000063.64 (0.55) |  000000453 (18) |  0000119 (0) |  0004,835 (91) |  00000.31 (0.00)
8 | T5 | Aug-CFG-Egocentric Pitt |  0000043.01 (0.48) |  000060.22 (1.60) |  00000514 (2) |  0000131 (1) |  00006,034 (399) |  00000.31 (0.00)
9 | T5 | Aug-CFG-Minimal Pitt |  0000042.82 (2.07) |  000062.84 (0.20) |  000000479 (26) |  0000132 (3) |  000003,160 (1030) |  00000.31 (0.00)
10 | T5 | Aug-Dummy Pitt |  0000006.26 (0.83) |  000013.88 (1.04) |  000001,069 (6) |  00000933 (1) |  000003,197 (746) |  00000.39 (0.00)

Table 3: CFG-based Augmentation Ablation Results

#### Aug-WikiGeo

To facilitate a comparison with standard open-source location augmentation
methods, such as Wikipedia-based Krause and Cohen (2023), we generated the
comprehensive Wikigeo dataset by consolidating data from Wikipedia (pages and
backlinks), Wikidata (pages), and OpenStreetMap (entities). The data for
Manhattan (Manh., 255,663 samples), Pittsburgh (Pitt., 27,401 samples), and
Philadelphia (Phila., 52,367 samples) are generated based on the same regions
as in the evaluation. Table 1 shows that this method produces shorter
instructions and fewer entities than the CFG-based and prompting-based
methods.

#### Aug-Dummy

To assess the contribution of the text augmentation, as opposed to just
learning all possible paths from a known starting point, we use an
augmentation where the text does not convey any spatial details of the
location. To create the non-spatial text, we used PaLM2 by requesting it to
rephrase the sentence “Meet me here” and got a total of 31 versions. Path
sampling followed the method described in Section 3.1.

##  5 Results

###  5.1 Analysis of Quantitative Results

Table 2 shows the results of our experiments over RVS's seen-city development
set (Manh.), unseen-city development set (Pitt), and the unseen-city test set
(Phila.). For the seen environment (Manh.), training on synthetic data only
(line 5) outperforms human-annotated data (line 3). The gap is small, but if
the model is first trained on synthetic data and then on human data (line 7),
the gap is a 65% ratio in 100m accuracy and a 110m lower in Med.AE.

Training on real human data from other regions (lines 10, 17) fails to
translate to unseen environments like Pittsburgh and Philadelphia. However,
injecting region-specific synthetic data (line 12) dramatically boosts
performance: 46.14% higher 100m accuracy and 987m lower Med.AE. WikiGeo's
emphasis on local features sacrifices spatial relational understanding,
leading to lower performance on all development sets (lines 4, 11). However,
its superior max distance estimation (up to 2km) and lower distance error over
models trained on human-annotated data from a different region (lines 11 vs.
10), suggest a strong ability to learn path boundaries based on localized
information.

Aug-Prompt, while generating instructions with richer language and stylistic
diversity compared to Aug-CFG's template-based approach, exhibits a marked
decrease in performance (lines 6, 13 vs. lines 5, 12). Sampling 20
instructions from Aug-Prompt, we found that in two cases, the type of goal was
emitted, and in five cases, the model `hallucinated' -- adding incorrect
spatial relations. This indicates a potential trade-off between linguistic
complexity and the fidelity of spatial information within generated
instructions.

(a) Manhattan-dev: Accuracy

(b) Manhattan-dev: Distance Error

(c) Pittsburgh-dev: Accuracy

(d) Pittsburgh-dev: Distance Error

Figure 3: T5 performance (Y-axis) with varying AUG-CFG training samples
(X-axis). (a,b) RVS seen-city (Manhattan), (c,d) RVS unseen-city (Pittsburgh).

Table 3 examines variations of CFG-based augmentation. Consistent with the
emphasis on allocentric spatial relations in RVS, training on Aug-CFG-
Allocentric (lines 2, 7) surpasses Aug-CFG-Egocentric (lines 3, 8) in both
development sets. However, results are mixed regarding whether training on
Aug-CFG-Allocentric is better than training on Aug-CFG. In the seen
environment, Aug-CFG-Allocentric (line 2) outperforms Aug-CFG (line 1) in
accuracy but underperforms in error distance. In the unseen-environment
(Pittsburgh), the opposite is true -- Aug-CFG-Allocentric (line 7)
underperforms Aug-CFG (line 6) in accuracy and overperforms error distance.
This inconclusive evidence suggests potential value in investigating a single
data approach for tasks with varying demands, such as RUN's reliance on
egocentric relations.

Despite capturing identical spatial relations, Aug-CFG-Minimal's limited
stylistic variations and vocabulary size due to fewer templates hinder its
performance compared to Aug-CFG across both seen (line 1 vs. line 4) and
unseen (line 6 vs. line 9) sets. This suggests that the mere presence of
accurate spatial relations may not be sufficient for optimal model learning,
potentially due to insufficient exposure to diverse linguistic contexts and
syntactic structures.

Training on Aug-Dummy teaches the model only the optional paths from a
starting point, as the instruction is a dummy one. The poor results achieved
over Aug-Dummy in both seen and unseen environments (lines 5, 10), prove that
training on Aug-CFG allows the model to learn spatial relations from the
instructions. The Aug-Dummy for Pittsburgh results are better as Manhattan is
much denser in entities than Pittsburgh, thus, it contains more optional paths
from the starting point.

###  5.2 Data Quantity Impact

Figure 3 shows four graphs of T5 performance trained on different amounts of
AUG-CFG data. The results reveal a quality-quantity trade-off influencing T5's
performance. In seen cities (Figures 3(a) and 3(b)), 7,000 high-quality human
annotations (green lines) outperform 7,000 synthetic AUG-CFG samples (red
lines) in 100m accuracy (27.92% vs. 8.93%) and Med.AE (231m vs. 744m),
indicating that the human-annotated RVS data possesses substantially higher
quality than the synthetic data. The steep curve of the RVS train-set (green
lines) compared to the mild curve of AUG-CFG (red lines) further reinforces
this conclusion. However, this trend flips with 200K synthetic samples,
showcasing the power of quantity over quality when data is abundant. This
suggests ample data helps the model grasp the environment and spatial
relations. Additionally, while both RVS train-set (green line) and AUG-CFG
(red line) demonstrate strong performance, the combined AUG-CFG + RVS train-
set (blue line) exhibits a sustained upward trend, consistently surpassing the
green and red lines in both accuracy and distance error. This further
indicates that augmenting with a large amount of data can potentially enhance
performance beyond even high-quality human annotations. This approach offers a
promising solution for the data scarcity challenges often encountered in NLP
geospatial tasks.

In the unseen-city split (Figures 3(c) and 3(d)), the RVS train-set (green
line) exhibits steady improvements in accuracy and error distance despite
originating from a different region. This demonstrates that high-quality data,
even when geographically distinct, can benefit the model. However, the
significant performance gap between the RVS train-set (green) and AUG-CFG
(red) lines, even with equal data quantities, reaffirms the importance of
regionally-specific data. While the RVS train-set (green) slope nears AUG-CFG
(red line), its accuracy improvement remains significantly lagged (moderate
slope), suggesting the model primarily learns general directional
understanding rather than fine-grained spatial reasoning. Furthermore, the
combined AUG-CFG + RVS train-set (blue) offers only marginal gains over AUG-
CFG alone (red), indicating that the benefits of high-quality non-regional
data diminish when paired with large-scale augmentation.

###  5.3 Distribution Analysis

Figure 4 reports the performance of the various augmentation methods through
cumulative distribution functions (CDFs). These CDFs show the percentage of
inferences with error distances below a specific meter value (x-axis),
effectively capturing accuracy across all error values and exposing underlying
error distributions. Notably, CFG-based methods (AUG-CFG and its variants)
exhibit a remarkably similar distribution, characterized by a sharp accuracy
ascent up to approximately 200m. Aug-Dummy's curve (yellow) resembles a ray
emanating from the origin, suggesting a strong correlation with the path
distribution assimilated during training. Aug-WikiGeo's low-resolution nature
is evident in its CDF (pink). While it starts slow (2̃00m) and climbs faster
than the yellow line, its limited accuracy holds it back. It only catches up
to the CFG-based methods at 1̃500m, but then fizzles out (plateaus) before
they even reach their peak.

Figure 4: Cumulative distribution function (CDF) error. Augmentation impact on
distance error (meters).

##  6 Background and Related Work

Text-based navigation tasks constitute a multimodal challenge (Antol et al.,
2015; Paz-Argaman et al., 2020; Ji et al., 2022) demanding the integration of
language comprehension and environmental knowledge. This environment can be
either indoor, commonly represented through the agent's visual perception as
it navigates Anderson et al. (2018), or outdoor. For outdoor environments,
representation falls into three main categories: (i) _Visual Representation_
\--- similar to indoor settings, real-world imagery can be employed, with
agents learning the environment through street-view like exploration Anderson
et al. (2018); (ii) _Map-based Representation_ \--- agents navigate based on
map perception, as seen in studies utilizing maps as the primary input
Anderson et al. (1991); Paz-Argaman et al. (2024); and (iii) _Hybrid
Representation_ \--- a combination of visual and map information Vasudevan et
al. (2020); de Vries et al. (2018).

Realistically, we would like to learn to navigate based on text in new
environments, ones that our models did not train on before. Furthermore,
environments constantly change, such that we need to reacquaint our models
with these changes in order for them to stay relevant Zhang and Choi (2021).

Synthetic data generation, facilitated by LLMs, has become a prominent
approach in NLP to mitigate data Sahu et al. (2022); Stylianou et al. (2023).
This technique is particularly attractive due to its adaptability to various
tasks and its ability to generate substantial volumes of data, allowing for
robust model training and improved performance. Data generation has also been
applied to multimodal tasks, demonstrating performance close to that of human-
annotated data Bitton et al. (2021).

Previous works on vision and language navigation tasks (VLN) tried to tackle
the data scarcity issue by generating synthetic data with a generative model
trained with human annotated data Fried et al. (2018); Zhu et al. (2020);
Majumdar et al. (2020). However, the learned distribution was limited to the
environment the model was trained on. EnvEdit Li et al. (2022b) tackled the
VLN task by generating new environments and synthetic navigation instructions
in order to teach models to generalize to new environments. The new
environments created differ in style, appearance, or the configuration of the
objects. However, a lack of new objects hinders unseen object handling. Kamath
et al. (2023) leveraged image-to-image synthesis via a Generative Adversarial
Network (GAN) architecture Koh et al. (2023) to create new viewpoints for
existing environments and subsequently generate synthetic instructions for
these environments.

Several prior works have tackled unseen environments without employing data
generation: (i) _Entity abstraction_ \-- Paz-Argaman and Tsarfaty (2019)
propose learning spatial language independent of specific entities by linking
abstracted entities to the agent's perception. However, this approach is
limited to simple navigation tasks where the agent has limited perception
(i.e., line of sight). It struggles with complex tasks like RVS, which require
allocentric spatial reasoning. (ii) _cross-lingual augmentation_ \-- Li et al.
(2022a) leverage spatial data across different languages for augmentation.
However, it still requires some environment-specific annotations, even if not
in the target language. Additionally, geolocation tasks utilizing open-source
datasets like Wikipedia often rely on grid-based representations, suffering
from spatially unoriented descriptions. This leads to significant retrieval
errors exceeding tens of kilometers, limiting their accuracy Wing and
Baldridge (2011). (iii) _Graph-based representation_ \-- representing the
environment via a graph and learning the connection between environment and
language Paz-Argaman et al. (2023, 2024). This approach lacks promising
results due to challenges in encoding complex spatial relationships within a
graph format. Schumann and Riezler (2021) trained a neural network to generate
synthetic navigation instructions based on OpenStreetMap representations.
However, these instructions were limited to step-by-step, local line-of-sight
guidance. Furthermore, the model's performance was evaluated on unseen paths
within the same city it was trained on.

This work tackles the problem of generating synthetic instructions for unseen
environments, exemplified by the RVS dataset Paz-Argaman et al. (2024). We
propose two techniques: an LLM-based approach for its adaptability, and a CFG
rule-based approach for increased precision, highlighting the trade-off
between data-driven efficiency and human-crafted accuracy.

##  7 Conclusion

This work presents a novel data-augmentation solution for spatial NLP tasks.
Leveraging spatial relation extraction it generates a vast, albeit slightly
less refined, dataset compared to human annotations. This quantitative
advantage unlocks superior performance, as evidenced by a 44.54% absolute
improvement in 100m accuracy and a 1,170m reduction in median absolute error
distance on unseen environments in the RVS dataset. These results demonstrate
the effectiveness of our approach in handling novel environments with sparse
or no human data. Moreover, our CFG-based augmentation method offers adherence
to correct spatial relations, control over the content, and interpretability,
over LLMs in spatial descriptions and could serve as a future tool for
evaluation, detection, and mitigation of artifacts such as `hallucinations'.

## Limitations

#### Data Dependence

This paper presents a promising data augmentation method for enhancing NLP
tasks like outdoor geolocation and navigation. However, its effectiveness
hinges on accessing comprehensive geospatial data, which can be difficult to
find in indoor Anderson et al. (2018); Jain et al. (2019); Nguyen et al.
(2019); Thomason et al. (2020); Qi et al. (2020); Ku et al. (2020) and virtual
environments MacMahon et al. (2006); Yan et al. (2018); Misra et al. (2018);
Shridhar et al. (2020); Kim et al. (2020). Furthermore, the reliance on open-
source data introduces the risk of incompleteness or regional unavailability.

#### Rule-based Scalability vs. LLM-Generated Artifacts

In addition, the leading augmentation method (CFG-based) used in this study is
rule-based, which, while offering control, preciseness, and interpretability,
also requires careful rule design. Crafting effective rules can be time-
consuming, laborious, and require substantial expertise in the specific
domain. This complexity can limit the scalability and adaptability of the
method to new situations or contexts. Furthermore, encoding all necessary
knowledge into explicit rules can be challenging, especially for complex
domains. This can limit the method's ability to capture subtle nuances or
unforeseen situations. This approach also stands in contrast to the prevailing
augmentation methods, which are grounded in LLMs (Schick and Schütze, 2021;
Wang et al., 2022). Using LLMs to generate data for augmentation represents a
promising avenue but requires further research to address issues like
hallucinations, which are particularly critical in spatial descriptions.
Therefore, rule-based methods such as our CFG-based method, which are not
vulnerable to hallucination problems, could serve as a valuable tool for
future research exploring the evaluation, detection, and mitigation of such
artifacts in LLM-generated text. Furthermore, by comparing augmentations
generated using both methods on specific tasks, we might gain insights into
the types of artifacts introduced by LLMs and how rule-based methods can help
mitigate them.

#### Limited Perception: Lack of Visual Cues

Our study primarily relied on map-based knowledge for navigation tasks, which
deviates from how humans navigate in natural settings. Real-world navigation
often involves integrating both visual cues and spatial knowledge acquired
from maps, a complexity not fully captured in our current approach. While the
StreetLearn dataset Mirowski et al. (2019) offers Google Street View imagery
for the test environments over both the Manhattan and Pittsburgh regions in
the RVS setup, we did not leverage this visual information. Future research
could extend the scope of our study by integrating visual perception and map-
based knowledge into the text generation approach for augmentation.

#### Bridging the Human-AI Performance Gap

In spite of progress made in this research, a substantial gulf still separates
current models' performance from human performance in the RVS task. Even with
our augmentation methods, current models lag behind human performance by
47.55% and 42.15% in 100-meter accuracy for seen and unseen environments,
respectively. Bridging this gap presents a critical challenge and an exciting
opportunity for future research, potentially unlocking novel avenues for
pushing the boundaries of this task.

## Acknowledgements

This research has been funded by the European Research Council (ERC), grant
number 677352 and by a grant from the Israeli Science Foundation (ISF) number
670/23, for which we are grateful. The research was further supported by a
KAMIN grant from the Israeli Innovation Authority, and computing resources
kindly funded by a VATAT grant and via the Data Science Institute from Bar-
Ilan University (BIU-DSI). We are also grateful for the additional support
provided by a Google grant.

## References

  * Abebrese (2019) Kwasi Abebrese. 2019.  _Implementing street addressing system in an evolving urban center. A case study of the Kumasi metropolitan area in Ghana_.  Ph.D. thesis, Iowa State University.
  * Anderson et al. (1991) Anne H Anderson, Miles Bader, Ellen Gurman Bard, Elizabeth Boyle, Gwyneth Doherty, Simon Garrod, Stephen Isard, Jacqueline Kowtko, Jan McAllister, Jim Miller, et al. 1991.  The hcrc map task corpus.  _Language and speech_ , 34(4):351--366.
  * Anderson et al. (2018) Peter Anderson, Qi Wu, Damien Teney, Jake Bruce, Mark Johnson, Niko Sünderhauf, Ian Reid, Stephen Gould, and Anton Van Den Hengel. 2018.  Vision-and-language navigation: Interpreting visually-grounded navigation instructions in real environments.  In _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_ , pages 3674--3683.
  * Anil et al. (2023) Rohan Anil, Andrew M Dai, Orhan Firat, Melvin Johnson, Dmitry Lepikhin, Alexandre Passos, Siamak Shakeri, Emanuel Taropa, Paige Bailey, Zhifeng Chen, et al. 2023.  Palm 2 technical report.  _arXiv preprint arXiv:2305.10403_.
  * Antol et al. (2015) Stanislaw Antol, Aishwarya Agrawal, Jiasen Lu, Margaret Mitchell, Dhruv Batra, C Lawrence Zitnick, and Devi Parikh. 2015.  Vqa: Visual question answering.  In _Proceedings of the IEEE international conference on computer vision_ , pages 2425--2433.
  * Bitton et al. (2021) Yonatan Bitton, Gabriel Stanovsky, Roy Schwartz, and Michael Elhadad. 2021.  Automatic generation of contrast sets from scene graphs: Probing the compositional consistency of gqa.  _arXiv preprint arXiv:2103.09591_.
  * Chomsky (1956) Noam Chomsky. 1956.  Three models for the description of language.  _IRE Transactions on information theory_ , 2(3):113--124.
  * Edwards et al. (2021) Aleksandra Edwards, Asahi Ushio, Jose Camacho-Collados, Hélène de Ribaupierre, and Alun Preece. 2021.  Guiding generative language models for data augmentation in few-shot text classification.  _arXiv preprint arXiv:2111.09064_.
  * Fried et al. (2018) Daniel Fried, Ronghang Hu, Volkan Cirik, Anna Rohrbach, Jacob Andreas, Louis-Philippe Morency, Taylor Berg-Kirkpatrick, Kate Saenko, Dan Klein, and Trevor Darrell. 2018.  Speaker-follower models for vision-and-language navigation.  _Advances in Neural Information Processing Systems_ , 31.
  * Grover and Leskovec (2016) Aditya Grover and Jure Leskovec. 2016.  node2vec: Scalable feature learning for networks.  In _Proceedings of the 22nd ACM SIGKDD international conference on Knowledge discovery and data mining_ , pages 855--864.
  * Hu et al. (2023) Yingjie Hu, Gengchen Mai, Chris Cundy, Kristy Choi, Ni Lao, Wei Liu, Gaurish Lakhanpal, Ryan Zhenqi Zhou, and Kenneth Joseph. 2023.  Geo-knowledge-guided gpt models improve the extraction of location descriptions from disaster-related social media messages.  _International Journal of Geographical Information Science_ , pages 1--30.
  * Jain et al. (2019) Vihan Jain, Gabriel Magalhaes, Alexander Ku, Ashish Vaswani, Eugene Ie, and Jason Baldridge. 2019.  Stay on the path: Instruction fidelity in vision-and-language navigation.  _arXiv preprint arXiv:1905.12255_.
  * Ji et al. (2022) Anya Ji, Noriyuki Kojima, Noah Rush, Alane Suhr, Wai Keen Vong, Robert D Hawkins, and Yoav Artzi. 2022.  Abstract visual reasoning with tangram shapes.  _arXiv preprint arXiv:2211.16492_.
  * Kamath et al. (2023) Aishwarya Kamath, Peter Anderson, Su Wang, Jing Yu Koh, Alexander Ku, Austin Waters, Yinfei Yang, Jason Baldridge, and Zarana Parekh. 2023.  A new path: Scaling vision-and-language navigation with synthetic instructions and imitation learning.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pages 10813--10823.
  * Kim et al. (2020) Hyounghun Kim, Abhay Zala, Graham Burri, Hao Tan, and Mohit Bansal. 2020.  Arramon: A joint navigation-assembly instruction interpretation task in dynamic environments.  _arXiv preprint arXiv:2011.07660_.
  * Koh et al. (2023) Jing Yu Koh, Harsh Agrawal, Dhruv Batra, Richard Tucker, Austin Waters, Honglak Lee, Yinfei Yang, Jason Baldridge, and Peter Anderson. 2023.  Simple and effective synthesis of indoor 3d scenes.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 37, pages 1169--1178.
  * Krause and Cohen (2023) Amir Krause and Sara Cohen. 2023.  Geographic information retrieval using wikipedia articles.  In _Proceedings of the ACM Web Conference 2023_ , pages 3331--3341.
  * Ku et al. (2020) Alexander Ku, Peter Anderson, Roma Patel, Eugene Ie, and Jason Baldridge. 2020.  Room-Across-Room: Multilingual vision-and-language navigation with dense spatiotemporal grounding.  In _Conference on Empirical Methods for Natural Language Processing (EMNLP)_.
  * Li et al. (2022a) Jialu Li, Hao Tan, and Mohit Bansal. 2022a.  Clear: Improving vision-language navigation with cross-lingual, environment-agnostic representations.  _arXiv preprint arXiv:2207.02185_.
  * Li et al. (2022b) Jialu Li, Hao Tan, and Mohit Bansal. 2022b.  Envedit: Environment editing for vision-and-language navigation.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pages 15407--15417.
  * Loshchilov and Hutter (2017) Ilya Loshchilov and Frank Hutter. 2017.  Fixing weight decay regularization in adam.  _CoRR_ , abs/1711.05101.
  * MacMahon et al. (2006) Matt MacMahon, Brian Stankiewicz, and Benjamin Kuipers. 2006.  Walk the talk: Connecting language, knowledge, and action in route instructions.  _Def_ , 2(6):4.
  * Majumdar et al. (2020) Arjun Majumdar, Ayush Shrivastava, Stefan Lee, Peter Anderson, Devi Parikh, and Dhruv Batra. 2020.  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.
  * Mirowski et al. (2019) Piotr Mirowski, Andras Banki-Horvath, Keith Anderson, Denis Teplyashin, Karl Moritz Hermann, Mateusz Malinowski, Matthew Koichi Grimes, Karen Simonyan, Koray Kavukcuoglu, Andrew Zisserman, et al. 2019.  The streetlearn environment and dataset.  _arXiv preprint arXiv:1903.01292_.
  * Misra et al. (2018) Dipendra Misra, Andrew Bennett, Valts Blukis, Eyvind Niklasson, Max Shatkhin, and Yoav Artzi. 2018.  Mapping instructions to actions in 3d environments with visual goal prediction.  _arXiv preprint arXiv:1809.00786_.
  * Nguyen et al. (2019) Khanh Nguyen, Debadeepta Dey, Chris Brockett, and Bill Dolan. 2019.  Vision-based navigation with language-based assistance via imitation learning with indirect intervention.  In _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition_ , pages 12527--12537.
  * Paz-Argaman et al. (2023) Tzuf Paz-Argaman, Tal Bauman, Itai Mondshine, Itzhak Omer, Sagi Dalyot, and Reut Tsarfaty. 2023.  Hegel: A novel dataset for geo-location from hebrew text.  _arXiv preprint arXiv:2307.00509_.
  * Paz-Argaman et al. (2024) Tzuf Paz-Argaman, Sayali Kulkarni, John Palowitch, Reut Tsarfaty, and Jason Baldridge. 2024.  Where do we go from here? multi-scale allocentric relational inferencefrom natural spatial descriptions.  In _EACL2024_. Association for Computational Linguistics.
  * Paz-Argaman and Tsarfaty (2019) Tzuf Paz-Argaman and Reut Tsarfaty. 2019.  RUN through the streets: A new dataset and baseline models for realistic urban navigation.  In _Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP)_ , pages 6449--6455, Hong Kong, China. Association for Computational Linguistics.
  * Paz-Argaman et al. (2020) Tzuf Paz-Argaman, Reut Tsarfaty, Gal Chechik, and Yuval Atzmon. 2020.  ZEST: Zero-shot learning from text descriptions using textual similarity and visual summarization.  In _Findings of the Association for Computational Linguistics: EMNLP 2020_ , pages 569--579, Online. Association for Computational Linguistics.
  * Qi et al. (2020) Yuankai Qi, Qi Wu, Peter Anderson, Xin Wang, William Yang Wang, Chunhua Shen, and Anton van den Hengel. 2020.  Reverie: Remote embodied visual referring expression in real indoor environments.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pages 9982--9991.
  * Raffel et al. (2020) Colin Raffel, Noam Shazeer, Adam Roberts, Katherine Lee, Sharan Narang, Michael Matena, Yanqi Zhou, Wei Li, Peter J Liu, et al. 2020.  Exploring the limits of transfer learning with a unified text-to-text transformer.  _J. Mach. Learn. Res._ , 21(140):1--67.
  * Sahu et al. (2022) Gaurav Sahu, Pau Rodriguez, Issam Laradji, Parmida Atighehchian, David Vazquez, and Dzmitry Bahdanau. 2022.  Data augmentation for intent classification with off-the-shelf large language models.  In _Proceedings of the 4th Workshop on NLP for Conversational AI_ , pages 47--57, Dublin, Ireland. Association for Computational Linguistics.
  * Sanderson and Kohler (2004) Mark Sanderson and Janet Kohler. 2004.  Analyzing geographic queries.  In _SIGIR workshop on geographic information retrieval_ , volume 2, pages 8--10.
  * Schick and Schütze (2021) Timo Schick and Hinrich Schütze. 2021.  Generating datasets with pretrained language models.  _arXiv preprint arXiv:2104.07540_.
  * Schumann and Riezler (2021) Raphael Schumann and Stefan Riezler. 2021.  Generating landmark navigation instructions from maps as a graph-to-text problem.  In _Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics and the 11th International Joint Conference on Natural Language Processing (Volume 1: Long Papers)_ , pages 489--502, Online. Association for Computational Linguistics.
  * Shridhar et al. (2020) Mohit Shridhar, Jesse Thomason, Daniel Gordon, Yonatan Bisk, Winson Han, Roozbeh Mottaghi, Luke Zettlemoyer, and Dieter Fox. 2020.  Alfred: A benchmark for interpreting grounded instructions for everyday tasks.  In _Proceedings of the IEEE/CVF conference on computer vision and pattern recognition_ , pages 10740--10749.
  * Solaz and Shalumov (2023) Yuval Solaz and Vitaly Shalumov. 2023.  Transformer based geocoding.  _arXiv preprint arXiv:2301.01170_.
  * Spink et al. (2002) Amanda Spink, Bernard J Jansen, Dietmar Wolfram, and Tefko Saracevic. 2002.  From e-sex to e-commerce: Web search changes.  _Computer_ , 35(3):107--109.
  * Stylianou et al. (2023) Nikolaos Stylianou, Despoina Chatzakou, Theodora Tsikrika, Stefanos Vrochidis, and Ioannis Kompatsiaris. 2023.  Domain-aligned data augmentation for low-resource and imbalanced text classification.  In _European Conference on Information Retrieval_ , pages 172--187. Springer.
  * Thomason et al. (2020) Jesse Thomason, Michael Murray, Maya Cakmak, and Luke Zettlemoyer. 2020.  Vision-and-dialog navigation.  In _Conference on Robot Learning_ , pages 394--406. PMLR.
  * UPU (2012) UPU. 2012.  _Addressing the world – An address for everyone_.
  * Vasudevan et al. (2020) Arun Balajee Vasudevan, Dengxin Dai, and Luc Van Gool. 2020.  Talk2nav: Long-range vision-and-language navigation with dual attention and spatial memory.  _International Journal of Computer Vision_ , pages 1--21.
  * Vaswani et al. (2017) Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Łukasz Kaiser, and Illia Polosukhin. 2017.  Attention is all you need.  _Advances in neural information processing systems_ , 30.
  * de Vries et al. (2018) Harm de Vries, Kurt Shuster, Dhruv Batra, Devi Parikh, Jason Weston, and Douwe Kiela. 2018.  Talk the walk: Navigating new york city through grounded dialogue.  _arXiv preprint arXiv:1807.03367_.
  * Wang et al. (2022) Su Wang, Ceslee Montgomery, Jordi Orbay, Vighnesh Birodkar, Aleksandra Faust, Izzeddin Gur, Natasha Jaques, Austin Waters, Jason Baldridge, and Peter Anderson. 2022.  Less is more: Generating grounded navigation instructions from landmarks.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pages 15428--15438.
  * Wing and Baldridge (2011) Benjamin Wing and Jason Baldridge. 2011.  Simple supervised document geolocation with geodesic grids.  In _Proceedings of the 49th annual meeting of the association for computational linguistics: Human language technologies_ , pages 955--964.
  * Yan et al. (2018) Claudia Yan, Dipendra Misra, Andrew Bennnett, Aaron Walsman, Yonatan Bisk, and Yoav Artzi. 2018.  Chalet: Cornell house agent learning environment.  _arXiv preprint arXiv:1801.07357_.
  * Yoo et al. (2021) Kang Min Yoo, Dongju Park, Jaewook Kang, Sang-Woo Lee, and Woomyeong Park. 2021.  Gpt3mix: Leveraging large-scale language models for text augmentation.  _arXiv preprint arXiv:2104.08826_.
  * Yu et al. (2021) Jiahui Yu, Xin Li, Jing Yu Koh, Han Zhang, Ruoming Pang, James Qin, Alexander Ku, Yuanzhong Xu, Jason Baldridge, and Yonghui Wu. 2021.  Vector-quantized image modeling with improved vqgan.  _arXiv preprint arXiv:2110.04627_.
  * Zhang and Choi (2021) Michael JQ Zhang and Eunsol Choi. 2021.  Situatedqa: Incorporating extra-linguistic contexts into qa.  _arXiv preprint arXiv:2109.06157_.
  * Zhu et al. (2020) Wanrong Zhu, Xin Eric Wang, Tsu-Jui Fu, An Yan, Pradyumna Narayana, Kazoo Sone, Sugato Basu, and William Yang Wang. 2020.  Multimodal text style transfer for outdoor vision-and-language navigation.  _arXiv preprint arXiv:2007.00229_.

Exaples of CFG generated templates | Example of generated instruction from template |
---|---|---
| “Meet at the END_POINT. Go CARDINAL_DIRECTION
---
from MAIN_PIVOT for INTERSECTIONS intersections.
It will be near a NEAR_PIVOT. If you reach
BEYOND_PIVOT, you have gone too far.”
| “Meet at the library. Go north-east from Starbucks for two
---
intersections. It will be near a book store. If you reach a
Zara cloth shop, you have gone too far.”
| “Go CARDINAL_DIRECTION from MAIN_PIVOT for
---
BLOCKS blocks to arrive at the END_POINT, right
GOAL_POSITION. You will pass MAIN_NEAR_PIVOT
before reaching the destination. You've overshot the meeting
point if you reach BEYOND_PIVOT.”
| “Go east from Grace Church for 3 blocks to arrive at the
---
parking lot, right in the middle of the block. You will pass
Jefferson Market Garden before reaching the destination.
You've overshot the meeting point if you reach Chipotle.”
| “Go CARDINAL_DIRECTION from MAIN_PIVOT for
---
BLOCKS blocks to arrive at the END_POINT, right
GOAL_POSITION. You will see MAIN_NEAR_PIVOT
before reaching the destination. You've overshot the
meeting point if you reach BEYOND_PIVOT.”
| “Go east from Grace Church for 3 blocks to arrive at the
---
parking lot, right in the middle of the block. You will see
Jefferson Market Garden before reaching the destination.
You've overshot the meeting point if you reach Chipotle.”
| “Walk CARDINAL_DIRECTION and past MAIN_PIVOT
---
to reach the END_POINT. The END_POINT is not far
from NEAR_PIVOT.”
| “Walk north and past Washington Square Park to reach
---
the cafe. The cafe is not far from a tobacco shop.”
| “Head to MAIN_PIVOT and go CARDINAL_DIRECTION
---
and meet at the END_POINT, right GOAL_POSITION.”
| “Head to Washington Square Park and go north and meet
---
at the cafe, right on the southeast corner of the block.”

Table 4: Examples of navigation instructions and the Context-Free Grammar
(CFG)-derived templates they are created from.

Figure 5: The RVS model based on a T5 transformer and a graph representation
of the environment Paz-Argaman et al. (2024).

##  Appendix A Data Generation

Our CFG rules define navigation instructions by combining five key elements in
various orders:

  * •

Goal Description: This specifies the target location.

  * •

Main Path: It outlines the primary route using landmarks.

  * •

Approaching Goal: This details how to get close to the target.

  * •

Goal Landmarks: It describes landmarks relative to the final position.

  * •

Off-Path Awareness: This identifies elements to avoid while navigating.

Table 4 demonstrates five navigation instructions and their corresponding CFG-
templates.

##  Appendix B Models

We also test on the T5+Graph presented in RVS, which is a T5 model
incorporating an OSM-based graph representation of the environment.

###  B.1 The Graph Representation

A location can be represented by its position (where the location is) or by
its semantics (what is present at the location, e.g., `a bar'). Semantic
knowledge is crucial for grounding mentioned entities to their physical
references in the environment. To this end, we aim to represent the semantics
via the RVS map-graph. We use the RVS map-graph and connect each node to its
corresponding S2-cells. As the S2-geometry is a hierarchical structure, we
allow for multiple levels of S2-cells connections. Also there are edges
between neighboring S2-cells at a given level (see bottom part in Figure 5).
To learn an embedding for each S2-cell in the environment, we compute random
walks on the graph using node2vec algorithm (Grover and Leskovec, 2016).
Following Yu et al. (2021), we use linear projection to cluster the graph
embeddings into K categories using the k-means algorithm with cosine
similarity distance. A new token is assigned to each category and added to the
tokenizer's vocabulary. We perform multiple clusters and pass the graph's
tokens with the instruction's tokens to the transformer encoder.

###  B.2 Experimental Setup Details

#### The Graph Embedding

The graph was constructed using three levels of S2-Cells: 15, 16, and 17. At
level 16, each sub-graph consisting of four neighboring S2-Cells was fully
connected. All S2-Cells in the graph were linked to their parent S2-Cell based
on the S2-geometry's hierarchy (i.e., level 17 S2-Cells were connected to
level 16 S2-Cells and level 16 S2-Cells were connected to level 15 S2-Cells).
Extracted entities from OSM and Wikidata were linked to the smallest level 17
S2-Cell that encompassed their geometry. The node of the entity included
additional data such as their geometry, type and name of entity. Random walks
on the graph were performed using node2vec (Grover and Leskovec, 2016).

| Method | Training Set | 100m Accuracy | 250m Accuracy | MAE | Med.AE | Max.AE | AUC
---|---|---|---|---|---|---|---|---
|  [HTML]EFEFEFManhattan (Manh) Seen-city Development Results
1 | T5 | RVS Train-set |  000027.92 (0.39) |  000052.63 (0.45) |  00000362 (9) |  00000231 (3) |  00002,957 (641) |  00000.32 (0.00)
2 | T5+Graph | RVS Train-set |  000029.40 (1.18) |  000054.67 (1.04) |  00000357 (7) |  00000216 (8) |  00003,889 (826) |  00000.31 (0.01)
3 | T5 | Aug-CFG Manh |  000028.83 (0.63) |  000046.15 (0.77) |  00000668 (17) |  00000304 (27) |  000004,637 (2,207) |  00000.34 (0.00)
4 | T5+Graph | Aug-CFG Manh |  000030.25 (0.95) |  000048.11 (0.92) |  00000660 (24) |  00000299 (17) |  00004,447 (677) |  00000.34 (0.01)
5 | T5 | Aug-CFG Manh & RVS Train-set |  000045.97 (1.34) |  000064.01 (0.89) |  00000377 (32) |  00000121 (15) |  00005,317 (831) |  0000.3 (0.00)
6 | T5+Graph | Aug-CFG Manh & RVS Train-set |  00045.42 (0.9) |  0063.1 (1.41) |  00000388 (10) |  0000131 12) |  0003,162 (43) |  0000.3 (0.01)
|  [HTML]EFEFEFPittsburgh (Pitt) Unseen-Development Results
7 | T5 | RVS Train-set |  000000.49 (1.47) |  00002.34 (1.44) |  00001,171 (24) |  0001,107 (14) |  00004,701 (101) |  00000.41 (0.00)
8 | T5+Graph | RVS Train-set |  000000.49 (1.01) |  00002.91 (1.37) |  00001,067 (77) |  0001,039 (56) |  00004,102 (727) |  00000.40 (0.00)
9 | T5 | Aug-CFG Pitt |  000046.63 (0.54) |  00063.73 (0.41) |  0000466 (5) |  000120 (1) |  005,251 (0) |  00000.31 (0.00)
10 | T5+Graph | Aug-CFG Pitt |  000046.67 (1.45) |  0063.1 (1.59) |  0000474 (1) |  000119 (8) |  005,251 (0) |  00000.31 (0.00)
11 | T5 | RVS Train-set & Aug-CFG Pitt |  000046.24 (0.30) |  00062.85 (0.41) |  00000387 (17) |  000116 (4) |  00005,162 (103) |  00000.30 (0.00)
12 | T5+Graph | RVS Train-set & Aug-CFG Pitt |  000045.75 (0.62) |  063.93 (0) |  0000467 (7) |  000125 (1) |  00006,509 (755) |  00000.31 (0.00)

Table 5: T5+Graph Results: Results are divided over RVS's development sets.
The augmentations data used for training depends on the method and region that
corresponds to the evaluation region: Manhattan (Manh) and Pittsburgh (Pitt).
The distance errors are presented in meters. For the learning models, we
report the mean over three random initializations and the standard deviation
(STD) is in brackets.

For both T5-base models we use a pre-trained `T5-Base' model from Hugging Face
Hub, which is licensed under the Apache License 2.0. The T5 model was trained
on the Colossal Clean Crawled Corpus (C4, Raffel et al. (2020)). The cross-
entropy loss function was optimized with AdamW optimizer (Loshchilov and
Hutter, 2017). The hyperparameter tuning is based on the average results run
with three different seeds. We used a learning rate of 1e-4. The S2-cell level
was searched in [15, 16, 17, 18] and 16 was chosen. The number of clusters for
the quantization process was searched in [50, 100, 150, 200, 250] and 150 was
chosen. We used 2 quantization layers. Number of epochs for early stopping was
based on their average learning curve. We used the following parameters for
the node2vec algorithm: an embedding size of 1024, a walk length of 20, 200
walks, a context window size of 10, a word batch of 4, and 5 epochs.

##  Appendix C Additional Results

Table 5 demonstrates the performance of T5+Graph with CFG augmentation. The
T5+Graph model’s performance is improved by the CFG augmentation in both seen
and unseen environments (lines 2 vs 4, and lines 8 vs 10). In the seen
environment, T5+Graph with CFG augmentation achieves higher scores than T5
with CFG augmentation (lines 3 vs 4). However, there is no clear evidence to
suggest which model performs better when using CFG augmentation data in both
seen and unseen environments. This finding suggests that the explicit spatial
knowledge offered by CFG augmentation data provides an easier path to learn
spatial relations, making the graph information in T5+Graph redundant or even
detrimental.