# Trajectory Clustering Performance Evaluation: If we know the answer, it’s
not clustering

Mohsen Rezaie
Polytechnique Montréal
Montréal, Québec, Canada  Nicolas Saunier
Polytechnique Montréal
Montréal, Québec, Canada

###### Abstract

Advancements in Intelligent Traffic Systems (ITS) have made huge amounts of
traffic data available through automatic data collection. A big part of this
data is stored as trajectories of moving vehicles and road users. Automatic
analysis of this data with minimal human supervision would both lower the
costs and eliminate subjectivity of the analysis. Trajectory clustering is an
unsupervised task. It requires a measure to calculate similarity of the
trajectories, a clustering algorithm to extract the patterns and a measure to
evaluate its performance.

In this paper, we perform a comprehensive comparison of similarity measures,
clustering algorithms and evaluation measures using trajectory data from seven
intersections. We also propose a method to automatically generate trajectory
reference clusters based on their origin and destination points to be used for
label-based evaluation measures. Therefore, the entire procedure remains
unsupervised both in clustering and evaluation levels. Finally, we use a
combination of evaluation measures to find the top performing similarity
measures and clustering algorithms for each intersection. The results show
that there is no single combination of distance and clustering algorithm that
is always among the top ten clustering setups.

##### Keywords

trajectory clustering, unsupervised evaluation, similarity measure, traffic
pattern recognition

##  1 Introduction

Data collection and analysis is the basis for transport planning and traffic
management. Better serving users while minimizing the negative impacts of
transportation systems requires better data. From automatic traffic counting,
surveys, incident detection, road network state recognition to law enforcement
tasks, transport management tasks all benefit from increasing amounts of data
with good temporal and spatial coverage collected thanks to the advancements
in hardware and software technology [10]. Exploiting the full potential of the
massive data collected every day by Intelligent Transportation Systems (ITS)
requires automatic data management and analysis with minimum intervention from
human operators.

Whether the data collection be through fixed or moving sensors, e.g. on
vehicles or pedestrians, such as pole or drone mounted regular or infrared
cameras, radars, LIDARs and Global Navigation Satellite System (GNSS) devices
[4, 2, 19, 6], various kinds of sensors provide user trajectories, i.e. the
series of their positions over time. These trajectories are then processed in
various ways for many transport applications, as noted above.

In some data analysis tasks such as motion prediction, the expected answer of
the model for each trajectory is known, either retrospectively (for example in
the case of time series prediction) or through expert annotation. Such a task
is therefore supervised, i.e. a label is available for each trajectory. If the
label is a discrete variable, it is a classification task, while if it is
continuous, it is regression task. However, this is typically not the case for
many other tasks such as automatically learning OD matrices, identifying trip
patterns in the population, anomaly detection for example to spot incidents or
law violations [28, 3, 25, 41, 31, 23]. Such tasks consist in putting together
similar trajectories into subsets of the whole dataset using a similarity
measure or distance, also called clustering. These tasks are naturally
unsupervised, as a good partition of the dataset or clustering depends on the
application or purpose. Even when possible, annotation is time consuming,
costly, error-prone and can be subjective or ambiguous.

We refer to the combination of clustering algorithm, distance or similarity
metric and their parameters as the clustering setup. Finally, performance
measures are used to evaluate how well the clustering method is working.

Even though clustering algorithms are unsupervised by definition, a large body
of literature use labeled data to evaluate the performance of these models.
Since the performance of a given clustering setup may depend on each dataset
it is applied to, this approach means that some data must be labeled every
time to measure the performance on new data, which is impractical and negates
to some extent the need for clustering in the first place. This motivates our
exploration of unsupervised performance measures for trajectory clustering.

In this paper we propose a framework for a comprehensive search of suitable
trajectory-clustering setups with common unsupervised evaluation measures. We
also propose a method to generate reference clusters for trajectories based on
their origin and destination points to be used in supervised evaluation
measures. We then use the results from the performance measures (both
unsupervised and supervised) and combine them to generate a metric to compare
several popular trajectory distances and clustering algorithms. The remainder
of this paper is organized as follows. Section 2 outlines the prior literature
related to trajectory clustering and discusses how this research builds on the
prior work. Section 3 quickly introduces the similarity measures, clustering
algorithms and evaluation methods and then explains the steps of the proposed
comprehensive comparison and evaluation method. Section 4 discusses the
results and insights from testing the clustering algorithm on real-world data.
Section 5 describes the conclusions of this research and the proposed future
work.

##  2 Related Work

Trajectory-based road user detection, classification and tracking has been
deployed for different traffic problems in various environments such as road
user counting, speed measurement and movement detection (e.g. traffic
violation detection), road user interaction analysis and automatic incident
detection [11, 22, 31, 39].

A crucial part of time-series data clustering problems is choosing a suitable
measure of similarity or distance. There are two categories of similarity
measures used in time-series analysis: lock-step and elastic measures [16,
17]. “Lock-step measures compare fixed (one-to-one) pairs of elements” [17]
from input time series of the same length: well-known measures are the
Bhattacharyya distance, the Euclidean Distance (ED) and more generally the
distances derived from the $L_{p}$ norms. On the other hand, elastic measures
such as Dynamic Time Warping (DTW), distances based on Longest Common Sub-
Sequence (LCSS), Edit distance with Real Penalty (ERP), Edit Distance on Real
sequence (EDR) and Symmetric Segment-Path Distance (SSPD) can handle time-
series of different lengths. Among these similarity measures, LCSS and DTW are
very popular among researchers for their ability to compare trajectories with
different lengths [1, 29, 35, 7]. However, this flexibility in input length
usually comes at the cost of higher computational burden. For instance, the
computational burden for the ED and Bhattacharyya distances is $O(n)$ while
computing several elastic measures including DTW and LCSS are of $O(mn)$ where
$m$ and $n$ is the lengths of the input time-series [8].

A body of literature focuses on trajectory clustering, using different Machine
Learning (ML) approaches. Choong et al. used trajectory clustering for the
traffic surveillance at intersections [13]. They used Longest Common Sub-
Sequence (LCSS) for measuring similarity and then used Gaussian kernel
function to convert LCSS similarity into distance. K-means and Fuzzy C-Means
(FCM) are used for clustering and the results were compared against ground-
truth through the Rand Index (RI).

Fu et al. used average pair-wise distance of first N points of each pair of
trajectories to represent the dissimilarity of them, where N is the length of
the shorter trajectory [18]. Then they used two layer clustering based on FCM,
Spectral and hierarchical clustering algorithms and compared them against each
other. For evaluation of performances they used Tightness and Separation
Criterion (TSC) which is based on within and between cluster dispersion of
objects.

Zhao et.al [40] used Douglas-Peucker (DP) based compression to re-sample
marine trajectory data. DTW is then used to calculate distances between the
trajectories. Finally Density-Based Spatial Clustering of Applications with
Noise (DBSCAN) algorithm is used for clustering. A custom performance metric
based on ground-truth labels was used for evaluation of the method.

Belisle et al. worked on automatically counting vehicle movements at
intersections [5]. Their method consists of vehicle detection and tracking,
then trajectory clustering with a focus on parameter optimization. They used
LCSS as similarity measure and a customized clustering algorithm similar to
K-means. The algorithm picks trajectory prototypes to represent each cluster.
For optimization and evaluation purposes, traffic turning counts were used as
ground truth to calculate the Weighted Average Percentage Error (WAPE).

Even though different methods of similarity measurement and clustering
algorithms are applied in trajectory analysis and novel methods have been
purposed, unsupervised performance measurement is mostly overlooked. Given the
heuristic nature of clustering approaches and the concern about their
sensitivity to differing data characteristics, errors in data and also in
judgement [27], reiterating evaluation measurements for each site could be
essential.

In this study, we focus on providing a framework to use several internal and
external performance indices without ground-truth labels to facilitate easier
clustering evaluations. More specifically, we propose a method to generate
reference labels for supervised performance metrics and use a combination of
supervised and unsupervised performance measures.

##  3 Methodology

###  3.1 Clustering Setup

For each site of interest, let $D$ be the set of road user trajectories within
the boundaries of the site. Let each trajectory $M_{i}\in D$ be a time-ordered
sequence of $m_{i}$ time-stamped positions of road user $i$ as
$(x^{i}_{j},y^{i}_{j},t^{i}_{j})$ where $x^{i}_{j}$ and $y^{i}_{j}$ represent
the coordinates of the road user at timestamp $t^{i}_{j}$, ${1\leq j\leq
m_{i}}$.

Clustering algorithms split the dataset into groups with similar objects based
on a similarity or distance measure. According to the literature, we use the
terms ”distance” and ”dissimilarity” in their broad meaning to mention a
method that measures unlikeness of a pair of trajectories. Value of a distance
measure is essentially non-negative and the more alike a pair of trajectories
are, the lower is the distance value. On the other hand, a similarity measure
represents a method of comparing trajectories which assigns (still non-
negative) higher values when two trajectories are more alike [12].

(Dis)similarity Measures | Parameters | Experimental Values
---|---|---
DTW | - | -
LCSS | $r_{b}$ | 1, 2, 3, 5, 7, 10 m
EDR | $r_{b}$ | 1, 2, 3, 5, 7, 10 m
PF | $w$ | 0.01, 0.05, 0.1, 0.2, 0.3, 0.5
Hausdorff | - | -
SSPD | - | -
Table 1: Similarity measures

Table 1 shows an overview of the (dis)similarity measures used in this study
and their parameters. For all the measures in Table 1, the Euclidean distance
was used for calculating point-to-point distances. LCSS and EDR both have a
parameter $r_{b}$ which is the threshold on point distances to decide if two
points are close enough and may be part of their similar subsequence.

Since LCSS provides a similarity measure, we convert it to the distance
$d_{LCSS}$ as suggested by Vlachos et al. [38]:

$d_{LCSS}(M_{i},M_{j})=\frac{1-LCSS(M_{i},M_{j})}{min(m_{i},m_{j})}$ (1)

where $LCSS(M_{i},M_{j})$ is the LCSS similarity between trajectories $M_{i}$
and $M_{j}$, i.e. the lengths of the longest common subsequence between them.

Given a distance measure $d_{\alpha}$ with parameters $\alpha$, all distances
$d_{i,j}$ between all pairs of trajectories $<M_{i},M_{j}>$ in $D$ are
calculated and stored in matrix $T_{D,d_{\alpha}}$. The distance matrix
$T_{D,d_{\alpha}}$ is then used by a clustering algorithm $A^{1}$ with
parameters $\beta$ to split $D$ into $k$ groups. We define the clustering
setup as $\omega=(d,\alpha,A^{1},\beta,k)$. Even though there are algorithms
which do not use the whole matrix but rather some of its elements (e.g. DBSCAN
and spectral clustering), pre-computing the matrix saves time since it is used
repeatedly in our experiments for different clustering algorithms $A^{1}$ and
number of clusters $k$.

In this study, we used six popular clustering algorithms used for trajectory
clustering, namely, k-Medoids [30], agglomerative hierarchical clustering
[21], spectral clustering [36], Density-based spatial clustering of
applications with noise (DBSCAN) and Ordering Points To Identify The
Clustering Structure (OPTICS).

It is worth mentioning that DBSCAN and OPTICS do not take into account a
number of clusters as input. In these two cases, the number of clusters $k$ is
a result of the algorithm and cannot be controlled directly. The table 2
summarizes the clustering algorithms used in this study with their
corresponding parameters (in addition to the number of clusters when
possible).

Clustering Algorithm | Parameters
---|---
k-medoids | -
agglomerative clustering | $linkage\in\\{complete,average,single\\}$
spectral | -
DBSCAN |  $n_{z}^{min}$, $d_{z}$
OPTICS | $n_{z}^{min}$
Table 2: Clustering algorithms

Figure 1 shows an example of trajectories recorded from an intersection in
Atlanta, Georgia, after trajectory clustering.

Figure 1: Example of trajectories $D$ in an intersection after clustering.
Clusters are represented by different colors (in some cases the colors
assigned to different clusters are similar due to the limit on number of
colors while maintaining the contrast high enough to keep them visually
distinctive).

For the reasons highlighted in the introduction of cost, time and subjectivity
of manually labelling trajectory clusters, the focus of this work is on the
unsupervised evaluation of the performance of methods for trajectory
clustering. Besides, there is an inherent contradiction to the use of labels
for clustering: if labels can be unambiguously assigned, it means the task can
be supervised and is not a clustering task.

Thus, there are no reference to check the clustering results presented in
Figure 1. While we may visually confirm that the generated clusters are
meaningful and can be considered as representatives of different manoeuvres in
the intersection, this is not always the case. The clusters presented in
Figure 1 result from a clustering setup $\omega$ picked based on the results
of this work. Indeed, it is not trivial to make the choice of $\omega$ and the
best clustering setup may be different from one location or period to another
because of different characteristics of the road configuration and the road
user trajectories. The next sections introduce the performance metrics used in
this work and how supervised performance metrics can be used without ground
truth.

###  3.2 Unsupervised Performance Measure

There are several unsupervised performance metrics for clustering evaluation.
These metrics only rely on distance values to evaluate the clustering setup
$\omega$. The silhouette (S) [33] is one of these metrics which is widely used
in the literature for trajectory clustering evaluation [1]. It is defined for
each object $i$ as [33]:

$s_{i}=\frac{b_{i}-a_{i}}{max(a_{i},b_{i})}$ (2)

Where $a_{i}$ is the mean distance between the object $i$ and all other
objects within the same cluster, and $b_{i}$ is the smallest of the mean
distances between the object $i$ and the objects in another cluster (different
from the one object $i$ belongs to). The total clustering performance based on
the Silhouette $S$ is then calculated as the average silhouette coefficient
over all objects.

Other unsupervised performance measures like he Calinski-Harabasz Index (CHI)
[26] and the Davies-Bouldin Index (DBI) [14] cannot be used as they rely on
the computation of cluster centers as averages of all objects in each cluster,
which cannot be done simply for variable length vectors such as trajectories.

However, unsupervised performance measures such as Silhouette are mostly
suitable for comparison between clustering setups with the same algorithms
since they make assumptions about cluster structure [1]. Also, unsupervised
performance measures cannot reflect results expected for specific
applications. If an expected, even partial, reference clustering is known,
generating a result that matches this clustering may not yield the best
unsupervised performance measure.

We have observed that if two trajectories are mistakenly considered similar by
$A^{1}$ based on distance $d$, an unsupervised performance measure based on
$d$ may make the same mistake and confirm $A^{1}$’s decision. Figure 2 shows
an example case in which the silhouette method mistakenly confirms the
clustering results. As one can see, the cluster 1 should be split in two
groups, each being merged with either cluster 6 or 20. Thus, while we expect
several negative silhouette values for the trajectories in the first cluster,
they are mostly positive and confirm the clustering mistakes.

(a) Clustered trajectories with colors showing the closest cluster for each
trajectory, computed as the mean distance to all elements in that cluster.

(b) Silhouette values for trajectories in the clusters shown on the left

Figure 2: Example of error in clustered trajectories and their silhouette
values

###  3.3 Weak Trajectory Clustering Supervision using Origin-Destination

To overcome this problem, we suggest that beside using common unsupervised
evaluation measures, a method independent of the distance $d$ and trajectory
clustering algorithm $A^{1}$ be used to validate the result of trajectory
clustering. The method that we propose here is generating “reference”
trajectory clusters based on clustering simply the first and last points of
the trajectories (origins and destinations) and using these reference clusters
with supervised evaluation measures.

To do so, we extract the origins and destinations of the trajectories in $D$
and put them in two sets, respectively $D_{O}$ and $D_{D}$. The points in each
set are clustered using the Euclidean distance and the clustering algorithm
$A^{2}$, which may not be the same as $A^{1}$, with the parameters $\beta_{O}$
and $\beta_{D}$ and number of clusters $k_{O}$ and $k_{D}$, respectively. The
steps are provided in detail in Algorithm 1.

The elbow method is used to make good choices for $k_{O}$ and $k_{D}$, since
it is a popular technique in point clustering [24]. Figure 3 illustrates the
average distances $\bar{d}$ with respect to $k_{O}$ and $k_{D}$: in this case
we picked $k_{O}=8$ and $k_{D}=4$. The graphs are produced based on data from
an intersection in NGSIM dataset using the agglomerative hierarchical
clustering algorithm with average linkage as the merging criterion. Figure 4
depicts an example of the origin and destination clusters for the trajectories
in the same intersection. If the proportion of trajectories starting from
origin cluster $\phi_{O}$ and destination cluster $\phi_{D}$ is more than a
threshold $\epsilon=0.01$, i.e. over 1 % of all trajectories, the origin-
destination pair is deemed significant and we assign label $\phi_{OD}$ to the
corresponding trajectories.

Figure 3: Average distances for the datasets of origins (left) and
destinations (right) with respect to the number of clusters. The mean plus and
minus two standard deviations are computed over several replications of the
clustering algorithm for each number of clusters.

Figure 4: Trajectory origin (left) and destination (right) clusters with
$k_{O}=8$, $k_{D}=4$ and agglomerative hierarchical clustering algorithm with
average linkage.

Using these reference clusters, we calculate six additional performance
measures, namely, the completeness, homogeneity and Validity (V) measures
[32], the Adjusted Rand Index (ARI) [34], Adjusted Mutual Information (AMI)
[37] and Fowlkes-Mallows Index (FMI) [15]. These measures represent the
agreement or similarity between the reference clusters and the clusters $K$
generated by the given setup $\omega$, ignoring permutations of the clusters.
In particular, for ARI and FMI, the measures rely on the joint classifications
of object pairs, whether they are both in the same or different clusters in
the reference and $K$.

  * •

Completeness, homogeneity and V [32]: for a cluster assignment $K$, we define
entropy of $K$:

$H(K)=-\sum^{k}_{i=1}\frac{|C_{i}|}{n}.\log{\frac{|C_{i}|}{n}}$ (3)

The entropy $H(Ref)$ of the reference clusters $Ref$ is defined accordingly.
Let $k_{Ref}$ be the number of reference clusters. The conditional entropy is
also defined, for example of $Ref$ given $K$ $H(Ref|K)$:

$H(Ref|K)=-\sum^{k_{Ref}}_{r=1}\sum^{k}_{i=1}\frac{n_{r,i}}{n}.\log{\frac{n_{r,i}}{n_{i}}}$
(4)

Where $n_{r,i}$ is the number of objects belonging to reference cluster $r$
and cluster $i$. The conditional entropy $H(K|Ref)$ of $K$ given $Ref$ is
defined in a symmetric manner. We can then finally define the performance
measures completeness ($c$) and homogeneity ($h$), and $V$ as their harmonic
mean:

$\displaystyle c$ $\displaystyle=1-\frac{H(K|Ref)}{H(K)}$ (5) $\displaystyle
h$ $\displaystyle=1-\frac{H(Ref|K)}{H(Ref)}$ (6) $\displaystyle V$
$\displaystyle=\frac{(1+\beta)\times h\times c}{\beta\times h+c}$ (7)

We use $\beta=1$ to give equal weights to the completeness and homogeneity
measures.

  * •

Adjusted Mutual Information (AMI): we first define the probabilities
$P(r)=\frac{|Ref_{r}|}{n}$ and $P^{\prime}(i)=\frac{|C_{i}|}{n}$ of a randomly
picked object to belong respectively to reference cluster $r$ and cluster $i$,
and $P(r,i)=\frac{n_{r,i}}{n}$. We then define the Mutual Information (MI)
[37]:

$MI(Ref,K)=\sum^{k_{Ref}}_{r=1}\sum^{k}_{i=1}P(r,i)\log{\frac{P(r,i)}{P(r)P^{\prime}(i)}}$
(8)

Since the MI favors clustering with a higher number of clusters $k$, we use
the Adjusted Mutual Information (AMI) instead:

$AMI=\frac{MI-E[MI]}{mean(H(Ref),H(K))-E[MI]}$ (9)

Where $E[MI]$ is the expected value of the MI index [37].

  * •

the Adjusted Rand Index (ARI) is a simple, yet popular index used for external
clustering performance. It is defined as [34]:

$RI=\frac{a+b}{C^{n}_{2}}$ (10)

Where $a$ is the number of object pairs that are in same cluster in both $Ref$
and $K$, $b$ is the number of object pairs that are in different clusters in
both $Ref$ and $K$, and $C^{n}_{2}=\frac{n(n-1)}{2}$ is the total number of
object pairs in the dataset. For a random label assignment, RI is not
necessarily zero. Instead, we use the Adjusted Rand Index (ARI) which fixes
this issue using the expected value of RI $E[RI]$:

$ARI=\frac{RI-E[RI]}{max(RI)-E[RI]}$ (11)

  * •

the Fowlkes-Mallows Index (FMI) is also based on the classification of the
object pairs, considering two objects being in the same clusters in both
assignments as the positive class and two objects being in different ones as
the negative class. For such a binary classification problem, the numbers of
True Positives (TP), False Positives (FP) and False Negatives (FN) can be
counted and the Fowlkes-Mallows Index (FMI) is calculated as the geometric
mean of precision and recall: [15]:

$FMI=\frac{TP}{\sqrt{(TP+FP)(TP+FN)}}$ (12)

Table 3 provides an overview of the performance measures used in this work.

Evaluation Measures |  Need for Reference Clusters | Higher-the-better | Range
---|---|---|---
S | ✗ | ✓ | $[-1,1]$
completeness | ✓ | ✓ | $[0,1]$
homogeneity | ✓ | ✓ | $[0,1]$
V | ✓ | ✓ | $[0,1]$
AMI | ✓ | ✓ | $[-1,1]$
ARI | ✓ | ✓ | $[-1,1]$
FMI | ✓ | ✓ | $[0,1]$
Table 3: Evaluation metrics

The trajectory dataset was permuted $n=10$ times in order to make the results
more robust for each clustering setup $\omega$. For each clustering setup, the
mean and standard deviation are computed for each performance measure, to
compute intervals of the performance measures as the mean plus or minus two
standard deviations which are plotted in the result section.

Finally, we use a combination of these evaluation measures to identify top
performing clustering setups. For each performance measure $v$ and each
$\omega$ we calculate the average performance $\bar{v_{\omega}}$, and,
assuming t-student distributions (unknown standard deviation), we calculate
the lower bound of the confidence interval for 95 % confidence level
$v^{lower}_{\omega}$:

$v^{lower}_{\omega}=\bar{v}_{\omega}-t_{95\%,9}*\frac{\hat{\sigma}_{v,\omega}}{\sqrt{n}}$
(13)

Then for a given evaluation measure $v$, we use $v^{lower}_{\omega}$ to order
$\omega$ and assign rank $r_{v,\omega}$ to each setup $\omega$. Finally these
rankings are averaged over different evaluation measures $v$ to calculate the
combined performance of each clustering setup $\bar{r_{\omega}}$. A formal
description of the computation of the clustering performance is presented in
Algorithm 2.

input : Sets of trajectories $D$ with derived sets of origins $D_{O}$ and
destinations $D_{D}$, minimum and maximum number of clusters $k_{min}$ and
$k_{max}$, cluster size threshold $\epsilon$, clustering algorithm $A^{2}$

output : Set $\Phi_{OD}$ of trajectory clusters $\phi_{OD}$

1 for  _$k_{O}\in[k_{min},k_{max})$_ do

2 Cluster trajectories based on their origins using $A^{2}$ into $k_{O}$
clusters;

3 Let $\Phi_{O}$ be the set of all clusters $\phi_{O_{i}}$ with average center
$c_{O_{i}}$;

4 Calculate the average within-cluster sum of squares or average distance
$\bar{d}_{k_{O}}=\frac{\sum\limits^{k_{O}}_{i=1}{\sum_{p\in\phi_{O_{i}}}||p-c_{O_{i}}||}}{|D|}$
using the $L_{2}$ norm $||\ ||$;

5

6Draw the graph of $\bar{d}_{k_{O}}$ values against $k_{O}$;

7 Pick the $\tilde{k}_{O}$ where an unusual drop in the $\bar{d}$ values
occurs;

8 Repeat all the steps above for $D_{D}$ and pick $\tilde{k}_{D}$;

9 Split $D$ into $\tilde{k}_{OD}=\tilde{k}_{O}*\tilde{k}_{D}$ clusters
depending on the cluster of the origin and destination of each trajectory;

10return the set $\Phi_{OD}$ of all trajectory clusters $\phi_{OD}$ containing
at least $\epsilon$ trajectories;

Algorithm 1 Clustering trajectories based on their origins and destinations to
produce reference clusters

input : Sets of unsupervised and supervised performance evaluation measures
$V^{u}$ and $V^{s}$, number of iterations $n$, subset of trajectories
$\tilde{D}=\cup_{\phi_{OD}\in\Phi_{OD}}\phi_{OD}$

output : Average performance rank for the clustering setups $\bar{r_{\omega}}$

1 for  _each candidate $d_{\alpha}$_ do

2 Calculate distance matrix $T_{D,d_{\alpha}}$ with elements
$d_{i,j}=d_{\alpha}(M_{i},M_{j})$;

3 for  _$l\in[1,n]$_ do

4 Permute randomly $\tilde{D}$;

5 for  _each candidate clustering algorithms $A^{1}$, parameters $\beta$ and
number of clusters $k$_ do

6 Cluster $\tilde{D}$ with the setup $\omega=(d,\alpha,A^{1},\beta,k)$ ;

7 Let $\Phi_{l}$ be the set of resulting clusters;

8 For all $v\in V^{u}$ calculate performance measure
$v_{\omega,l}=v(\Phi_{l})$;

9 For all $v\in V^{s}$ calculate performance measure
$v_{\omega,l}=v(\Phi_{l},\Phi_{OD})$;

10

11

12for  _$v\in V^{u}\cup V^{s}$_ do

13 for  _each $\omega=(s,\alpha,A^{1},\beta,k)\in\Omega$_ do

14 Calculate average performance measure
$\bar{v}_{\omega}=\frac{\sum^{n}_{l=1}v_{\omega,l}(\Phi_{i})}{n_{iter}}$;

15 Calculate lower bound
$v^{lower}_{\omega}=\bar{v}_{\omega}-t_{95\%,9}*\hat{\sigma}_{v,\omega}$;

16

17 Order all clustering setups $\omega$ based on $v^{lower}_{\omega}$ and
assign rank $r_{v,\omega}$;

18

19for  _$\omega\in\Omega$_ do

20 Calculate average rank $\bar{r}_{\omega}=\frac{\sum_{v\in V^{u}\cup
V^{s}}{r_{v,\omega}}}{|V^{u}\cup V^{s}|}$

21

Algorithm 2 Computing the clustering performance measures with permutation of
the trajectory dataset

##  4 Experimental Results

All the codes developed in this work to produce the results are available
online under an open source license in a GitHub repository.

###  4.1 Datasets

We have have tested our framework on data from seven intersections from two
datasets:

####  4.1.1 NGSIM

The first dataset used in this work is extracted from a dataset made publicly
available by the Next Generation SIMulation (NGSIM) program [20]. It is a
popular dataset containing trajectory data collected at four sites in the U.S.
and used among traffic researchers for benchmarking their works. It consists
of positions of vehicles moving on or crossing the five lane Peachtree street
in Atlanta, Georgia . The data is recorded at 10 Hz during both the morning
and afternoon rush-hours from multiple synced cameras mounted on tall
buildings to cover the roads over several hundreds meters. The
(sub-)trajectories within the boundaries of four intersections were extracted
from this dataset. Figure 5(a) shows an aerial photo of intersection NGSIM 1.

####  4.1.2 inD

The second set of trajectories is from the intersection Drone (inD) dataset,
collected from three intersections in Aachen, Germany from 2017 to 2019 [9].
The trajectories are extracted from video recordings of around 20 minutes
collected via a drone-mounted camera at 25 Hz frame rate. Figure 5(b) shows an
aerial photo of intersection inD 2.

(a) Site map of intersection NGSIM 1 (one out of four)

(b) Site map of intersection inD 2 (one out of three)

Figure 5: An example of intersection for each of the two datasets

The table 4 gives a summary of sites used for the experimental results.

Site | Camera | Intersection Types | Traffic Lights
---|---|---|---
inD 1 | drone | 4-way | ✗
inD 2 | drone | 4-way | ✗
inD 3 | drone | T-intersection | ✗
NGSIM 1 | building | 4-way | ✓
NGSIM 2 | building | 4-way | ✓
NGSIM 3 | building | 4-way | ✓
NGSIM 4 | building | 4-way | ✓
Table 4: Site summary with their characteristics (multiple synced cameras were
mounted on buildings for the NGSIM datasets).

###  4.2 Performance Plots

Figure 6 shows the performance results for NGSIM 1 intersection based on the
EDR similarity measure with parameter $w=7$. Each of the plots in the figure
shows one of the seven performance measures as a function of the number of
clusters $k$ used in the clustering.

Figure 6: Performance results for the NGSIM 1 intersection based on EDR
similarity measure with parameter $w=7m$

Given seven intersections studied in this work, three distances $d$ with no
parameters and distances having a parameter with six tested parameter values
$\alpha$, there are $7*21=147$ figures similar to Figure 6. Given that the
general patterns observed here in Figure 6 is not necessarily shared in the
other 146 figures, analyzing such enormous amount of data and finding the best
clustering setup $\omega=(d,\alpha,A^{1},\beta,n_{A^{1}},k)$ is not feasible
through visual comparison of those 147 figures.

###  4.3 Performance Measure Combination

To summarize the information and ease the decision process on picking the best
setup, we want to combine the performance results. However, some evaluation
measures may be correlated with each other and including all of them
regardless of the correlations would over-emphasize the performance features
corresponding to these correlated measures. Figure 7 shows the correlations
between the seven performance measures for the NGSIM 1 intersection.

Figure 7: Correlation of the performance measures for the NGSIM 1 intersection

Based on correlation plots from the seven intersections, evaluation measures V
and homogeneity on the one hand, FMI and S on the other hand are highly
correlated together with absolute correlation values between them above 0.75
for all pairs of measures in all intersections. Therefore, we keep use S,
Completeness, Homogeneity, ARI and AMI for the combined metric.

The ten best setups for each site are picked based on the average rank
$\bar{r}_{\omega}$. The Figures 8 and 9 shows the top performing distances and
clustering algorithms for each site, more precisely the proportion of the 10
best setups in which each distance and algorithm appears. The first
observation is that there is no one clustering setup and not even a specific
distance measure or clustering algorithm that outperforms systematically the
others or at least always appears among the top ten best clustering setups for
all sites. Hierarchical clustering is the most common clustering algorithms
appearing in the top ten for all sites. Though not similarly frequent, the
spectral clustering algorithm is also showing some consistency in appearing
among the top performers in most, although not all, the sites. For distances,
SSPD and Hausdorff appear frequently, especially for the NGSIM datasets, while
the LCSS appears in the top ten for three inD datasets.

The second observation is that there are clear winners for specific sites.
Each site has one, up to three, algorithms or distances outperforming the
others (in some cases, LCSS or hierarchical clustering appear several times in
the top with different parameters). However, there is no clear pattern in
these observations across sites, whether some dataset characteristics may
explain to some extent the heterogeneity or whether trajectory clustering is
intrinsically sensitive to the input data.

inD intersection 1

inD intersection 2

inD intersection 3 Figure 8: Top performing similarity measures (left) and
trajectory clustering algorithms (right) on different inD sites

NGSIM intersection 1

NGSIM intersection 2

NGSIM intersection 3

NGSIM intersection 4 Figure 9: Top performing similarity measures (left) and
trajectory clustering algorithms (right) on different NGSIM sites

##  5 Conclusion

In this paper, we proposed a way to combine unsupervised and supervised
clustering performance metrics without any manual annotation of the
trajectories. Namely we tried six distances, three of them each tried with six
parameter values, i.e. a total of 21 distances, six clustering algorithms,
different numbers of clusters when used as input by some the clustering
algorithms ranging from 2 to 30 and used seven performance measures. We did
the experiments on seven intersections from two different datasets, collected
in different countries, different road types and through different data
collection methods.

Even though generally useful, unsupervised performance measures use the same
distance $d$ used in the clustering, and their results often align with the
clustering results As complementary performance measures, we proposed a method
to generate reference clusters based on the origins and destinations of the
trajectories to be used in supervised performance measures.

Finally, using a metric based on a combination of performance measures, we
picked the top performing distances and clustering algorithms. The results
show that there is no single combination of distance and clustering algorithm
that is always among the top ten clustering setups. There are distances that
performed better compared to the others in specific intersections, but none of
them are present among the top performers for every intersection. Among the
clustering algorithms, agglomerative hierarchical clustering was the only one
that was among the top performers in all seven intersections, though not
always with the same linkage type. Also the plots do not show a visual
dominance of it over other clustering algorithms.

Based on these findings, we believe that the choice of similarity measure and
clustering algorithm greatly depends on the intersection type, environment and
road user behaviors. Therefore, we suggest that similar comparison procedures
be followed for new sites among the candidate setups. To facilitate this, we
have made all the essential codes developed in this work available online
under an open source license (GitHub repository).

A systematic search of the parameters of the clustering algorithms and
distances is needed to determine whether some results depend on the choice of
parameters. Further work is necessary to better characterize clustering
performance, e.g. based on domain specific tasks like origin-destination
clustering, and apply these to more datasets and better characterize the
factors that determine clustering performance.

## References

  * [1] Saeed Aghabozorgi, Ali Seyed Shirkhorshidi, and Teh Ying Wah.  Time-series clustering–a decade review.  Information Systems, 53:16–38, 2015.
  * [2] Constantinos Antoniou, Ramachandran Balakrishna, and Haris N Koutsopoulos.  A synthesis of emerging data collection technologies and their impact on traffic management applications.  European Transport Research Review, 3(3):139–148, 2011.
  * [3] Tharindu Bandaragoda, Daswin De Silva, Denis Kleyko, Evgeny Osipov, Urban Wiklund, and Damminda Alahakoon.  Trajectory clustering of road traffic in urban environments using incremental machine learning in combination with hyperdimensional computing.  In 2019 IEEE intelligent transportation systems conference (ITSC), pages 1664–1670. IEEE, 2019.
  * [4] Emmanouil Barmpounakis and Nikolas Geroliminis.  On the new era of urban traffic monitoring with massive drone data: The pneuma large-scale field experiment.  Transportation research part C: emerging technologies, 111:50–71, 2020.
  * [5] François Bélisle, Nicolas Saunier, Guillaume-Alexandre Bilodeau, and Sebastien le Digabel.  Optimized video tracking for automated vehicle turning movement counts.  Transportation Research Record, 2645(1):104–112, 2017.
  * [6] Marcin Bernas, Bartłomiej Płaczek, Wojciech Korski, Piotr Loska, Jarosław Smyła, and Piotr Szymała.  A survey and comparison of low-cost sensing technologies for road traffic monitoring.  Sensors, 18(10):3243, 2018.
  * [7] Philippe C Besse, Brendan Guillouet, Jean-Michel Loubes, and François Royer.  Review and perspective for distance-based clustering of vehicle trajectories.  IEEE Transactions on Intelligent Transportation Systems, 17(11):3306–3317, 2016.
  * [8] Jiang Bian, Dayong Tian, Yuanyan Tang, and Dacheng Tao.  A survey on trajectory clustering analysis.  arXiv preprint arXiv:1802.06971, 2018.
  * [9] Julian Bock, Robert Krajewski, Tobias Moers, Steffen Runde, Lennart Vater, and Lutz Eckstein.  The ind dataset: A drone dataset of naturalistic road user trajectories at german intersections.  In 2020 IEEE Intelligent Vehicles Symposium (IV), pages 1929–1934. IEEE, 2019.
  * [10] Michael Bommes, Adrian Fazekas, Tobias Volkenhoff, and Markus Oeser.  Video based intelligent transportation systems–state of the art and future development.  Transportation Research Procedia, 14:4495–4504, 2016.
  * [11] Norbert Buch, Sergio A Velastin, and James Orwell.  A review of computer vision techniques for the analysis of urban traffic.  IEEE Transactions on Intelligent Transportation Systems, 12(3):920–939, 2011.
  * [12] Shihyen Chen, Bin Ma, and Kaizhong Zhang.  On the similarity metric and the distance metric.  Theoretical Computer Science, 410(24-25):2365–2376, 2009.
  * [13] Mei Yeen Choong, Lorita Angeline, Renee Ka Yin Chin, Kiam Beng Yeo, and Kenneth Tze Kin Teo.  Vehicle trajectory clustering for traffic intersection surveillance.  In 2016 IEEE International Conference on Consumer Electronics-Asia (ICCE-Asia), pages 1–4. IEEE, 2016.
  * [14] David L Davies and Donald W Bouldin.  A cluster separation measure.  IEEE transactions on pattern analysis and machine intelligence, (2):224–227, 1979.
  * [15] Bernard Desgraupes.  Clustering indices.  University of Paris Ouest-Lab Modal’X, 1:34, 2013.
  * [16] Hui Ding, Goce Trajcevski, Peter Scheuermann, Xiaoyue Wang, and Eamonn Keogh.  Querying and mining of time series data: experimental comparison of representations and distance measures.  Proceedings of the VLDB Endowment, 1(2):1542–1552, 2008.
  * [17] Leonardo N Ferreira and Liang Zhao.  Time series clustering via community detection in networks.  Information Sciences, 326:227–242, 2016.
  * [18] Zhouyu Fu, Weiming Hu, and Tieniu Tan.  Similarity based vehicle trajectory clustering and anomaly detection.  In IEEE International Conference on Image Processing 2005, volume 2, pages II–602. Ieee, 2005.
  * [19] Ali Haghani, Masoud Hamedi, K Farokhi Sadabadi, Stanley Young, and Philip Tarnoff.  Freeway travel time ground truth data collection using bluetooth sensors.  Transportation Research Record, Journal of Transportation Research Board, 2160:60–68, 2010.
  * [20] John Halkias and James Colyar.  Next generation simulation fact sheet.  US Department of Transportation: Federal Highway Administration, 2006.
  * [21] Anil K Jain, M Narasimha Murty, and Patrick J Flynn.  Data clustering: a review.  ACM computing surveys (CSUR), 31(3):264–323, 1999.
  * [22] Zihan Kan, Luliang Tang, Mei-Po Kwan, Chang Ren, Dong Liu, and Qingquan Li.  Traffic congestion analysis at the turn level using taxis’ gps trajectory data.  Computers, Environment and Urban Systems, 74:229–243, 2019.
  * [23] Christos Katrakazas, Mohammed Quddus, Wen-Hua Chen, and Lipika Deka.  Real-time motion planning methods for autonomous on-road driving: State-of-the-art and future research directions.  Transportation Research Part C: Emerging Technologies, 60:416–442, 2015.
  * [24] Trupti M Kodinariya and Prashant R Makwana.  Review on determining number of cluster in k-means clustering.  International Journal, 1(6):90–95, 2013.
  * [25] Eonhye Kwon, Seongjong Noh, Moongu Jeon, and Daeyoung Shim.  Scene modeling-based anomaly detection for intelligent transport system.  In 2013 4th International Conference on Intelligent Systems, Modelling and Simulation, pages 252–257. IEEE, 2013.
  * [26] Ujjwal Maulik and Sanghamitra Bandyopadhyay.  Performance evaluation of some clustering algorithms and validity indices.  IEEE Transactions on pattern analysis and machine intelligence, 24(12):1650–1654, 2002.
  * [27] Glenn W Milligan and Martha C Cooper.  Methodology review: Clustering methods.  Applied psychological measurement, 11(4):329–354, 1987.
  * [28] Luís Moreira-Matias, João Gama, Michel Ferreira, João Mendes-Moreira, and Luis Damas.  Time-evolving od matrix estimation using high-speed gps data streams.  Expert systems with Applications, 44:275–288, 2016.
  * [29] Brendan Morris and Mohan Trivedi.  Learning trajectory patterns by clustering: Experimental studies and comparative evaluation.  In 2009 IEEE Conference on Computer Vision and Pattern Recognition, pages 312–319. IEEE, 2009.
  * [30] Hae-Sang Park and Chi-Hyuck Jun.  A simple and fast algorithm for k-medoids clustering.  Expert systems with applications, 36(2):3336–3341, 2009.
  * [31] Mohsen Rezaie, Zachary Patterson, Jia Yuan Yu, and Ali Yazdizadeh.  Semi-supervised travel mode detection from smartphone data.  In 2017 International Smart Cities Conference (ISC2), pages 1–8. IEEE, 2017.
  * [32] Andrew Rosenberg and Julia Hirschberg.  V-measure: A conditional entropy-based external cluster evaluation measure.  In Proceedings of the 2007 joint conference on empirical methods in natural language processing and computational natural language learning (EMNLP-CoNLL), pages 410–420, 2007.
  * [33] Peter J Rousseeuw.  Silhouettes: a graphical aid to the interpretation and validation of cluster analysis.  Journal of computational and applied mathematics, 20:53–65, 1987\.
  * [34] Jorge M Santos and Mark Embrechts.  On the use of the adjusted rand index as a metric for evaluating supervised classification.  In International conference on artificial neural networks, pages 175–184. Springer, 2009.
  * [35] Nicolas Saunier, Tarek Sayed, and Clark Lim.  Probabilistic collision prediction for vision-based automated road safety analysis.  In 2007 IEEE Intelligent Transportation Systems Conference, pages 872–878. IEEE, 2007.
  * [36] Jianbo Shi and Jitendra Malik.  Normalized cuts and image segmentation.  IEEE Transactions on pattern analysis and machine intelligence, 22(8):888–905, 2000.
  * [37] Nguyen Xuan Vinh, Julien Epps, and James Bailey.  Information theoretic measures for clusterings comparison: Variants, properties, normalization and correction for chance.  The Journal of Machine Learning Research, 11:2837–2854, 2010.
  * [38] Michail Vlachos, George Kollios, and Dimitrios Gunopulos.  Discovering similar multidimensional trajectories.  In Proceedings 18th international conference on data engineering, pages 673–684. IEEE, 2002.
  * [39] Jing Wang, Chaoliang Wang, Xianfeng Song, and Venkatesh Raghavan.  Automatic intersection and traffic rule detection by mining motor-vehicle gps trajectories.  Computers, Environment and Urban Systems, 64:19–29, 2017.
  * [40] Liangbin Zhao and Guoyou Shi.  A trajectory clustering method based on douglas-peucker compression and density for marine traffic pattern recognition.  Ocean Engineering, 172:456–467, 2019.
  * [41] Rong Zhen, Yongxing Jin, Qinyou Hu, Zheping Shao, and Nikitas Nikitakos.  Maritime anomaly detection within coastal waters based on vessel trajectory clustering and naïve bayes classifier.  The Journal of Navigation, 70(3):648, 2017.


# DiaLoc: An Iterative Approach to Embodied Dialog Localization

Chao Zhang Mohan Li Ignas Budvytis Stephan Liwicki
Toshiba Europe Ltd
<EMAIL_ADDRESS>
###### Abstract

Multimodal learning has advanced the performance for many vision-language
tasks. However, most existing works in embodied dialog research focus on
navigation and leave the localization task understudied. The few existing
dialog-based localization approaches assume the availability of entire dialog
prior to localizaiton, which is impractical for deployed dialog-based
localization. In this paper, we propose DiaLoc, a new dialog-based
localization framework which aligns with a real human operator behavior.
Specifically, we produce an iterative refinement of location predictions which
can visualize current pose believes after each dialog turn. DiaLoc effectively
utilizes the multimodal data for multi-shot localization, where a fusion
encoder fuses vision and dialog information iteratively. We achieve state-of-
the-art results on embodied dialog-based localization task, in single-shot
(+$7.08\%$ in Acc5@valUnseen) and multi-shot settings (+$10.85\%$ in
Acc5@valUnseen). DiaLoc narrows the gap between simulation and real-world
applications, opening doors for future research on collaborative localization
and navigation.

##  1 Introduction

Picture yourself becoming lost within a novel building during a visit to a
friend’s place of residence or work place. In this scenario, you reach out to
your friend and detail the elements of your environment. Through a series of
exchanges, it is anticipated that your friend will eventually figure out your
whereabouts. The completion of this collaborative endeavor depends on the
skillful use of targeted inquiries and unequivocal linguistic responses. In
this study, we formulate this task as an iterative embodied dialog
localization problem involving two agents: an Observer, randomly situated
within an environment, and a Locator, whose job is to localize the observer
with a provided top-down map through dialog.

Iterative embodied dialog localization is of clear relevance to numerous real-
world applications, including the utilization of mobile robots for search and
rescue operations [19, 17]. Nevertheless, it is worth noting that dialog-based
localization, in comparison to navigation, is still a relatively understudied
area. The dataset WAY sourced dialogs from human annotations and formulated
dialog-based localization through employing a full dialogue and a top-down map
to determine an agent’s precise location. The sparsity and problem formulation
pose however two challenges: Firstly, its utilization of multimodal
information to overcome information imbalances stemming from egocentric and
top-down viewpoints. Secondly, the dataset’s scarcity restricts the capacity
of trained models to generalize to unfamiliar environments.

Figure 1: Illustration of iterative embodied dialog localization. The locator
with top-down map and the observer with egocentric view engage in a
cooperative dialog to assist in determining the observer’s location. The
locator iteratively forms predictions to enhance the estimations. The
preceding dialog exchanges and cumulative predictions also influence the
manner in which the locator poses new questions. As depicted, the locator
predicts 3 possible locations based on the first turn. The second question is
asked to disambiguate the predictions and the correct location is predicted
given the answer from the observer.

In an initial attempt to address the challenge of localization through
embodied dialog, Hahn _et al_. [9] introduced a novel approach by framing the
task as an image-to-image problem. They adopted LingUNet network to predict
localization distribution. Language embedding generated by BiLSTM [10] is used
as conditional input to guide the learning of visual features. Leveraging a
dataset of human annotations, their approach assumes the availability of the
complete dialog prior to making predictions. However, this approach contrasts
with human intuition, as human localization predictions are characterized by
incremental refinement. As illustrated in Figure 1, the locator actively makes
location guesses as new dialog information arrives. This dynamic process is
also reflected in questioning: the locator poses new questions based on prior
dialog exchanges and their cumulative predictions. Therefore, developing a
localization technique capable of continual location estimation stands as a
fundamental cornerstone for realizing the practical application of cooperative
search and rescue.

Inspired by cooperative search and rescue we therefore introduce a novel
approach which we call _iterative embodied dialog localization_. This
formulation requires the locator to possess the capability of finding out the
observer’s location following each turn within the dialog. When compared to
existing approaches that consider the complete dialog, our iterative framework
offers several merits. Firstly, it operates with greater efficiency. During
the inference phase, it only processes a single turn of the dialog, as opposed
to the entire conversation. In practical application, this efficiency can
translate into time savings, or life savings, as the location can be estimated
or narrowed down to a few points before the conversation finishes. Secondly,
our approach exhibits enhanced generalization to novel locations. The risk of
over-fitting to training data is mitigated by not relying on complete dialogs
during the training process. Lastly, the intermediate predictions provide
vital cues for assessing uncertainty and are indispensable for tasks that
involve dialog generation, such as embodied visual dialog and cooperative
localization. In summary, this transition towards an iterative dialog-based
localization approach not only aligns with engineering perspectives but also
paves the way for improved performance and broader applicability across
various related tasks.

Multimodal learning, particularly through the integration of vision and
language, has emerged as a prominent topic in deep learning era. The paradigm
of Vision-Language Pre-training (VLP) [14, 13] has advanced the performance of
numerous vision-language tasks. VLP employs Transformers to acquire either
unimodal representations or fused multimodal representations. Inspired by
VLP’s success in multiple vision language understanding and generation tasks,
such as image captioning and Visual Question Answering(VQA), we embrace the
Transformer-based encoders. This forms the backbone for our novel multimodal
multi-shot localizer, which becomes the state of the art.

In summary, we make the following contributions: (i) We introduce an iterative
approach towards practical embodied dialog localization. This formulation
aligns with the intuitive behavior of a human locator who employs incremental
predictions to improve localization performance. (ii) We propose a novel
multimodal multi-shot localizer DiaLoc based on Transformer encoders. (iii) We
demonstrate state-of-the-art performance for embodied dialog localization. Our
proposed iterative solution exhibits enhanced generalization capabilities.
(iv) We showcase that the proposed approach posses the ability to rectify
previous prediction with new information and may help a human operator in
question formulation for search and rescue applications.

##  2 Related Work

#### Vision and Language

Vision and language understanding has been extensively explored across tasks
such as image captioning, visual question answering (VQA) and visual grounding
[4, 1, 24, 7]. The fusion of language and vision for recognition is also an
active domain. Notably, CLIP [20] effectively learns visual concepts through
natural language supervision. The fundamental insight is to employ natural
language as a versatile space for predictions, facilitating zero-shot
generalization and transfer learning.

In the context of language-driven tasks, LSeg [12] was proposed for language-
driven semantic image segmentation using flexible text embeddings. It allows
LSeg to generalize to unseen categories at test time. Delving into the
intersection of vision and language with navigation, Visual and language
navigation (VLN) combines visual and linguistic inputs to enhance robot
navigation in building-scale environments [2]. Moreover, vision and language
navigation in continuous environments (VLN-CE) is an instruction-guided
navigation task. It relaxes the assumptions inherent in the original VLN task,
striving to bridge the gap between simulated environments and real-world
scenarios. Instead of utilizing a labeled dataset with trajectories
annotations, LM-Nav [21] shows that a robotic navigation system can be
constructed purely from pre-trained models using CLIP and GPT-3 [4] without
any fine-tuning or language-annotated robot data.

Embodied Localization Estimating an agent’s position within the environment
forms a vital aspect of applications in embodied AI. Hahn _et al_. [9]
introduced the task of localization from embodied dialog (LED), leveraging the
WAY dataset containing approximately 10,000 dialogs curated by human
operators. The authors also proposed a baseline for LED based on LingUnet
[18], using a top-down map as input to predict location. Choosing an effective
map representation is a key consideration in this task. Unlike [9], Hann _et
al_. [8] proposed an Transformer-based method using navigation graph extracted
from Matterport3D [5]. In a similar vein to LED, Cooperative Vision-and-Dialog
Navigation (CVDN) [22] introduces a dataset consisting of dialogues where an
oracle assists a navigator in completing a navigation task. The baseline
approach adopts a sequence-to-sequence approach. Both WAY and CVDN are
constructed upon the Matterport3D dataset, albeit with different focuses: WAY
concentrates on localization, while CVDN focus on navigation. Further,
RobotSlang [3] brings a dataset that contains 169 dialogs between a human
directing a robot and another human offering guidance towards navigation
goals. Beyond multimodal localization, Text2Pos [11] delves into cross-modal
text to point cloud localization based on Kitti360 [15]. Within this context,
the proposed approach identifies positions specified by template-based
language descriptions of immediate surroundings within the environment
represented as a point cloud.

##  3 Iterative Embodied Dialog Localization

We first describe the task of iterative embodied dialog based localization.
Then, the architecture of our proposed model is introduced. These are followed
by the training objectives and implementation details.

Figure 2: DiaLoc-e: the proposed multi-shot multimodal architecture for
embodied dialog localization. The approach employs the image encoder and the
frozen text encoder to derive visual and linguistic unimodal embeddings. The
fusion encoder integrates the unimodal inputs to update the hidden state.
Multi-shot predictions are produced using the hidden state at varying
timesteps. The fusion encoder comprises $N$ blocks of Transformer encoder with
cross attention layer.

###  3.1 Task and Evaluation Metrics

We perform embodied localization using dialogs
$D=(L_{1},O_{1},...,L_{T},O_{T})$ and the global map $e$, here the human
dialog is represented by $T$ turns between the utterance of the locator
$L_{i}$ and the observer $O_{i}$. The goal is to predict the observer’s final
location $p_{T}$. Different from the previous approaches making a single
prediction at the end of the whole dialog, the proposed iterative approach
outputs multiple predictions for each turn $p_{1},...,p_{T}$. The goal is to
enhance communication efficacy and spatial understanding through a series of
information exchanges between the locator (top-down view) and the observer
(egocentric). To evaluate the localization error (LE), we follow [8] to use
geodesic distance instead of euclidean distance, as geodesic distance is more
meaningful for determining error across rooms. Pixel coordinate $p_{T}$ of the
location is snapped to the nearest way-point node $g_{T}$ before the
calculation of localization error as: $\text{LE}=||g_{T}-\hat{g}_{T}||^{2}$,
where $g_{T}$ is the ground-truth and $\hat{g}_{T}$ is the prediction. Binary
success rate for LE at threshold $k$ is also reported for represented values
such as 0m and 5m. We draw Cumulative Matching Characteristics (CMC) curves to
compare different approaches to characterize the holistic performance.

The WAY dataset [9] is used to evaluate the proposed method. It is split into
train (9,955), valSeen (305), valUnseen (579) and test sets (1,200). There
exists two evaluation protocols: floor-level [9] and building-level [8]. As
opposed to non-iterative methods, our proposed method focus on exploiting the
sequential context from a dialog and has the potential of stopping the dialogs
when predictions are accurate. Achieving the early-stopping requires the turn-
based locations since the observer is allowed to move during the dialogs. To
further improve the training efficiency, our method follows [9] and use the
floor-based setting assuming the known floor. We found that neither the target
floor information or the per-turn location is available from the test split
and hence not feasible for the evaluation purpose. As such, all methods are
trained using train split and validated using valSeen, and the performance on
valUnSeen is used to show the generalization in novel scenes.

There are two advantages of evaluating on the dialogs with known floor and
turn-based dense locations: (1) Comparing to methods that use all floors
during training, evaluating using the target floor map is efficient and easier
for us to investigate the iterative improvement; (2) With corresponding
locations at each turn of the dialog, we could measure the localization
performance at different timesteps. This is useful to quantify the potential
of early termination.

Compared to non-iterative embodied dialog localization, the new iterative
approach offers improved adaptability and accuracy. It enables agents to
progressively refine their spatial understanding through ongoing dialogs,
accommodating dynamic environments representation and nuanced contextual
information. This contrasts with the previous single-shot methods, and allows
for more effective training, better generalization to unseen environments, and
ultimately more practical embodied applications.

###  3.2 Architecture

Previously, LED [9] formalized embodied dialog localization as one image-to-
image translation problem. The whole dialog is used as conditional input to
the encoder-decoder network. Unlike LED, we argue that multi-turn predictions
happened at the end of each turn are crucial for the applications such as
search and rescue. This also resembles the way how human performs dialog-based
localization. To reduce this gap, we adopt Transformer [23] backbone for the
new task. Inspired by recent work on multimodal learning [14, 13]. Our design
features an image backbone which interacts with dialog input iteratively.
Location predictions are made at multiple timesteps. We now describe the
network architecture details as shown in Figure 2.

Unimodal Encoders. To obtain unimodal embeddings, we use Transformer-based
encoder for both vision and language inputs. Vision transformers (ViT) pre-
trained on ImageNet is used as the image encoder for top-down map $e$. We
fine-tune ViT to generate the visual embedding $V\in R^{M,C}$, where $M=196$
is the number of visual tokens. Input map is resized to $224\times 224$. To
encode dialog $D=(L_{1},O_{1},\cdots,L_{T},O_{T})$ of $T$ turns, we adopt the
pre-trained Bert [6] as the text encoder. The dialog $D$ is represented as
features $L\in R^{N,C}$, where $N=100$ is the max token length. Note that the
feature dimension $C$ is 768 for both ViT and BERT.

Multimodal Encoder. Given visual and text embeddings $V$ and $L$, we employ a
stack of Transformer blocks as the multimodal encoder $\Phi$. Each block
consists of 12 sequential modules of self-attention (SA), cross-attention (CA)
and feed-forward (FF) layers. The cross-attention layer is introduced for the
purpose of multimodal fusion. Specifically, text embedding of current turn
$L_{t}$ is used to create query $Q$ via a MLP, while the map embedding $V$
provides key $K$ and value $V$. The output of multimodal encoder is hidden
state $S\in R^{M,C}$ and has the same dimension as visual embedding $V$. A
detailed illustration of the fusion encoder is shown in Figure 2.

Prediction Head. Multimodal encoder fuses dialog input and visual map
representations to output the current state $S_{t}$ at turn $t$. Using $S$ as
input, a prediction head including multiple convolution and deconvolution
layers is trained to produce location heatmap $H\in R^{h,w}$. The heatmap $H$
is finally up-sampled to the same size as target $\tilde{H}\in
R^{h_{0},w_{0}}$ for loss caculation. At inference stage, the predicted
location in image space is obtained via
$\hat{p}=\text{Argmax}(\text{Softmax}(H))$.

Multi-shot Multimodal Localizer. We now discuss two fusion variants for multi-
shot localization. The distinction mainly lies in how previous hidden state
$S_{t-1}$ are intergrated with new dialog input $L_{t}$. In Figure 2, the
_explicit_ variant, dubbed DiaLoc-e, is illustrated. The map embedding $V$ is
directly processed at each timestep and is fused with the hidden state $S$
before being fed into the fusion encoder via: $S_{t}=\Phi(V\odot
S_{t-1},L_{t})$. The hidden state $S$ is initialized to $\mathbf{1}$ and
serves as the prior for the visual map. For the _implicit_ variant, DiaLoc-i,
depicted in Figure 3, it iteratively updates the hidden state via
$S_{t}=\Phi(S_{t-1},L_{t})$ thus ensuring that the final state $S_{T}$ are
conditioned on all dialog turns $(L_{1},..,L_{T})$.

Figure 3: DiaLoc-i: the proposed localizer variant with implicit fusion
design. The hidden state is continuously updated with dialog information at
each timestep.

###  3.3 Loss Function

Starting with single-shot case, given the prediction $H$ and the target
$\tilde{H}$, we train the model to minimize the KL-divergence between the
predicted location distribution and the ground-truth location. Similar to [9],
Gaussian smoothing with standard deviation of 3m is applied to the ground-
truth $\tilde{H}$. The single-shot loss function is:

$L_{ss}(H,\tilde{H})=\log(\tilde{H})(\log\tilde{H}-\log(\text{Softmax}(H)))$
(1)

To adapt to our multi-shot approach, we simply apply single-shot loss to all
predictions $\textbf{H}=H_{t=1}^{T}$ made at $t\in[1,T]$. Additionally, the
multiple losses are weighted summed to provide the following multi-shot loss:

$L_{ms}(\textbf{H},\tilde{H})=\frac{1}{T}\sum_{t=1}^{T}L_{ss}(H_{t},\tilde{H})\alpha^{T-t}$
(2)

where $\alpha\in[0,1]$ is the decay factor. The idea of applying decay is to
penalize less for early predictions due to incomplete dialog context.

However, there is still a risk of over-fitting when intermediate predictions
$H_{t}$ where $t<T$ are toned down with the decay factor. Specifically we note
that it is often unreasonable to find the true location after a single,
ambiguous dialog turn. Unfortunately, however, The KL-divergence loss with the
ground-truth target encourages peaky predictions and leads to over-confident
prediction at early timesteps. To alleviate this issue, we introduce an
auxiliary loss $L_{aux}$. The aim of this term is to promote the diversity of
early predictions and avoid unreasonable early filtering of false positives.
The loss function is defined as:

$L_{aux}(\textbf{H},\tilde{H})=\frac{1}{T}\sum_{t=1}^{T}L_{mse}(\text{Sigmoid}(H_{t})\odot\tilde{H}_{mask},\tilde{H})$
(3)

where $\tilde{H}_{mask}$ is the binary mask of target where $\tilde{H}>0$.
Sigmoid function is applied to $H_{t}$ to produce the probability scores of
location. Mean squared loss $L_{mse}$ is used to measure the prediction error.

We combine the multi-shot loss $L_{ms}$ and the auxiliary loss $L_{aux}$ to
get the final loss:

$L(\textbf{H},\tilde{H})=L_{ms}(\textbf{H},\tilde{H})+\beta
L_{aux}(\textbf{H},\tilde{H})$ (4)

where $\beta$ as the weight factor. We set $\beta=1.0$ for our method except
ablation studies.

###  3.4 Training Details

In training, both top-down map and ground-truth target are resized to
$224\times 224$. Color jittering, random cropping with ratio $[0,9,1.0]$ and
scale $[0,75,1.0]$, and random rotation of $180^{\circ}$ are used for data
augmentation. ViT-base pretrained on ImageNet-21k and Bert-base-uncased are
used as unimodal encoders. We keep BERT encoder frozen in training. We train
all models up to 30 epochs, with batch size 16. We use AdamW [16] as the
optimizer and set the learning rate to $2e-5$.

##  4 Experiments

First, we conduct several ablation studies aimed at validating the design
choices, including the depth of multimodal encoders, fusion variants, and the
effect of the decay factor. Additionally, we delve into the evaluation of the
auxiliary loss to support its efficacy. From the perspective of data
augmentation, we observe that incorporating synthetic dialogs generated by
ChatGPT API 111https://api.openai.com/v1/chat/completions contributes to
performance enhancement. Second, we proceed to compare our proposed methods
with the baseline approaches in both single-shot and multi-shot modes. This
include quantitative results as well as qualitative samples. Lastly, we
provide a detailed examination of multi-shot performance, offering a fine-
grained analysis of the results.

###  4.1 Ablations

#### Depth of multimodal encoder.

We first study the effect of depth of the multimodal encoder in Table 1. We
ablate this with the implicit fusion variant as shown in Figure 2. Results
show that depth=3 gives the best performance in unseen set when vision encoder
is frozen. When ViT is fine-tuned, the performance using more blocks drops.
The best unseen Acc5 is 47.09 using depth=1. Overall, fine-tuning ViT improves
the performance a lot because ViT needs to adapt to the top-down map visual
input.

ViT | Depth | valSeen | valUnseen
---|---|---|---
LE$\downarrow$ | Acc5$\uparrow$ | LE$\downarrow$ | Acc5$\uparrow$
Frozen | 1 | 9.29 | 47.18 | 10.54 | 33.27
3 | 9.45 | 43.43 | 9.26 | 38.23
6 | 9.41 | 47.50 | 9.54 | 37.72
Fine-tune | 1 | 7.62 | 57.37 | 9.09 | 47.09
3 | 7.73 | 58.01 | 9.35 | 42.06
6 | 8.44 | 55.12 | 10.02 | 39.61
Table 1: Ablation on depth of multimodal encoders. DiaLoc-i is used in this
ablation with decay $\alpha=0$.

Fusion variants and decay factor. We have proposed two variants to perform
multimodal fusion in Section 3.2. DiaLoc-i updates the visual hidden state
using dialog input recursively, while DiaLoc-e fuses the original map
embedding with the hidden state using multiply fusion operation. To
investigate how the two fusion variants perform, we report the results in
Table 2. For both variants (depth=3), we fine-tune the ViT. The results show
that implicit fusion performs better on valSeen set, while explicit fusion
works better on valUnseen. Implicit fusion leverages shared hidden state and
has higher risk of over-fitting. Using fixed map embedding and learnable
hidden state, explicit fusion shows better generalization. We also find that
using non-zero decay factor leads to lower accuracy due to the early
convergence.

Method | Decay | valSeen | valUnseen
---|---|---|---
LE$\downarrow$ | Acc5$\uparrow$ | LE$\downarrow$ | Acc5$\uparrow$
DiaLoc-i | 0.0 | 7.73 | 58.01 | 9.35 | 42.06
0.5 | 7.95 | 54.68 | 9.74 | 36.48
1.0 | 8.20 | 55.31 | 9.75 | 33.61
DiaLoc-e | 0.0 | 8.99 | 50.32 | 9.10 | 41.60
0.5 | 9.51 | 54.68 | 9.76 | 41.10
1.0 | 8.91 | 51.56 | 9.21 | 37.95
Table 2: Ablation on fusion schemes and the decay factor. Both DiaLoc variants
use depth=3 without auxiliary loss.

Impact of auxiliary loss. We ablate the impact of using auxiliary loss as
defined in Eq 3. We train the model with depth as 1 with varying decay factor
of KL-divergence term. For each decay choice, the same model is trained with
($\beta$=1) and without ($\beta$=0) using auxiliary loss. Results are shown in
Table 3, combining the two losses helps to improve the performance
consistently across all setups.

Decay $\alpha$ |  Aux $\beta$ | DiaLoc-e | DiaLoc-i
---|---|---|---
valSeen | valUnseen | valSeen | valUnseen
LE$\downarrow$ |  Acc5$\uparrow$ |  LE$\downarrow$ |  Acc5$\uparrow$ |  LE$\downarrow$ |  Acc5$\uparrow$ |  LE$\downarrow$ |  Acc5$\uparrow$
0.0 | 0.0 | 7.81 | 57.18 | 9.99 | 37.89 | 7.54 | 58.65 | 9.61 | 34.19
1.0 | 7.76 | 58.01 | 9.56 | 40.23 | 7.39 | 60.57 | 9.19 | 38.58
0.5 | 0.0 | 7.95 | 54.68 | 9.74 | 36.48 | 7.16 | 58.97 | 9.98 | 36.41
1.0 | 6.76 | 63.46 | 9.58 | 40.01 | 7.79 | 60.25 | 10.54 | 32.53
1.0 | 0.0 | 8.20 | 55.31 | 9.75 | 33.61 | 7.99 | 56.41 | 11.01 | 34.36
1.0 | 7.92 | 58.65 | 8.99 | 42.06 | 7.55 | 59.29 | 10.42 | 36.47

Table 3: Ablation on auxiliary loss using explicit fusion variant DiaLoc-e. We
vary the decay factor $\alpha$ to train multiple versions of the model, with
and without the proposed auxiliary loss. DiaLoc-e generalizes (9/12 valUnseen)
better than DiaLoc-i (10/12 valSeen)

Dialog augmentation using LLM. We hypothesize that increasing the dialog
diversity during training could improve the performance because text encoder
is frozen in our work. We leverage GPT to study the effect of dialog
augmentation on the task. For each training sample, we prompt GPT API to
paraphrase the ground-truth dialog. During training, either the GPT version or
the ground-truth dialog is chosen randomly. Results in Table 4 show that using
extra data helps improve the performance for seen and unseen maps.

Method | Dialog | valSeen | valUnseen
---|---|---|---
LE$\downarrow$ | Acc5$\uparrow$ | LE$\downarrow$ | Acc5$\uparrow$
DiaLoc-e | GT | 8.91 | 51.56 | 9.21 | 37.95
GT+GPT | 7.07 | 60.00 | 9.09 | 40.71
Table 4: Ablation on using extra dialogs generated by GPT. DiaLoc-e is configured to use depth=3, $\alpha=1$, and $\beta=0$ LingUNet | Map | 1.63m | 14.42m | 5.19m | 6.01m
---|---|---|---|---|---
DiaLoc | GT | 1.88m | 16.58m | 5.19m | 4.66m
| val-seen 67 | Single-shot |  Multi-shot: $1/T$ | $2/T$ | $3/T$
LingUNet | Map | 9.72m | 2.08m | 2.08m | 3.74m
DiaLoc-e | GT | 4.32m | 2.64m | 1.56m | 1.56m
| val-unseen 245 | Single-shot |  Multi-shot: $1/T$ | $2/T$ | $3/T$
Figure 4: Qualitative results of single-shot and multi-shot location
predictions are presented. In the first column, the visual map is displayed
alongside its corresponding ground truth (GT) location. The second column
displays the single-shot predictions, with LingUNet results above and DiaLoc
results below. The last three columns showcase the multi-shot predictions.
Regarding the results of valseen case 67, DiaLoc effectively corrects the
prediction after the second turn, whereas LingUNet-ms produces noisy
distributions. For valUnseen case 245, both LingUNet and DiaLoc failed in the
single-shot mode. Nevertheless, in the multi-shot mode, DiaLoc succeeds in
refining the prediction. In contrast, LingUNet-ms converges towards an
incorrect area. Localization Error (LE) is displayed for the predictions.

###  4.2 Comparison to the SOTA

#### Single-shot and multi-shot.

In this section, we undertake a comparative analysis of our method with state-
of-the-art approaches in the LED task. For single-shot mode, LingUNet [9]
using complete dialog stands as the current SOTA method. We report the
geodesic distance performance using the author-provided code. We also adapt
BLIP [14] as BLIP-Res18 and BLIP(DiaLoc) to use dialogs as conditional input
for image-based localization task.

In the multi-shot mode, we adapt LingUNet similarly to our DiaLoc-i and
DiaLoc-e, enabling it to generate multi-shot predictions Specifically, the
fusion is implemented by multiplying the output (H1 preceding the final MLP)
with image features (F1). More details in Supp.Mat. We refer to this method as
LingUNet-i/e. Our proposed method is denoted as DiaLoc-i and DiaLoc-e,
reflecting the different fusion variants implicit and explicit respectively.
In alignment with [9], we report Acc0 and Acc5 as evaluation metrics for both
valSeen and valUnseen sets in Table 5.

Mode | Method | valSeen | valUnseen
---|---|---|---
Acc0 | Acc5 | Acc0 | Acc5
Single shot | LingUNet | 19.87 | 59.29 | 6.16 | 33.33
BLIP-Res18$\diamond$ | 13.44 | 50.82 | 6.73 | 34.71
BLIP(DiaLoc)$\dagger$ | 25.64 | 66.02 | 7.02 | 40.41
Multi shot | LingUNet-i | 4.32 | 24.16 | 3.25 | 20.21
LingUNet-e | 14.47 | 46.15 | 5.31 | 36.30
DiaLoc-i | 18.43 | 57.18 | 6.42 | 37.89
DiaLoc-e | 18.36 | 60.00 | 8.44 | 47.15
Table 5: Evaluations on WAY dataset under single-shot and multi-shot
scenarios. We configure DiaLoc-i and DiaLoc-e to use $d=3,\alpha=0,\beta=1$.
BLIP-Res18$\diamond$ and BLIP(DiaLoc)$\dagger$ are adapated so that the visual
branch is configured as the main backbone to predict heatmap. Figure 5: CMC
curves on WAY dataset. We depict the CMC curves for both our DiaLoc and
LingUNet for single-shot and multi-shot settings. DiaLoc consistently
outperforms the baseline. X-axis denotes the error threshold for LE and the
Y-axis denotes the success rate.

When utilizing the entire dialog both during training and inference, our
method outperforms LingUNet by a substantial margin. The improvement in Acc5
on the valUnseen is 7.08. This performance enhancement can be attributed to
the learning capabilities and flexibility of Transformers for both unimodal
and multimodal encoders.

In the context of the proposed multi-shot localization task, our evaluation
focuses on final prediction accuracy. First, in comparison to the mode using
complete dialogs, the performance of all methods exhibits a decline in the
valSeen set. Our methods demonstrate competitive performance in valSeen set.
Notably, DiaLoc-e surpasses all other methods in the valUnseen set,
demonstrating robust generalization and reasoning capabilities. It is also
noteworthy that LingUNet-ms performs well in the valUnseen set, even though
its performance drops in valSeen. This observation suggests that the proposed
iterative multi-shot approach effectively reduces the issue of over-fitting.

Considering computational complexity, there are significant savings when
switching from the one-shot to the multi-shot scenario, despite multi-shot
demanding multiple forward passes. Now, we compare the computational costs
during the dialog embedding stage with Bert. For a dialog with $T$ turns,
where each turn is encoded by $N$ tokens, the single-shot mode involves
$O(T^{2}N^{2})$ multiplications for self-attention computation. However, this
complexity is reduced to $O(N^{2})$ in the multi-shot mode.

Figure 6: Multi-shot localization error analysis. To study performance across
varied dialog length, we group samples based on their length $T$ and report LE
for each group. Within each sub-plot, the LE at $t$ where $1\leq t\leq T$ is
detailed. Our method depicts a trend that more turns is helpful to
localization while LingUNet shows mixed performance.

#### CMC Curves.

To conduct a more comprehensive assessment of the performance of proposed
method and the state-of-the-art method, We present the Cumulative Match
Characteristic (CMC) curves for both DiaLoc and LingUNet(ms) in Figure 5.
DiaLoc consistently outperforms the baseline in both single-shot and multi-
shot configurations. In valUnseen set, our multi-shot performance (red solid
line) also surpasses that of the single-shot baseline (cyan solid line) and
single-shot DiaLoc (blue solid line), showing improved performance in novel
environments.

#### Qualitative results.

In Figure 4, we show two examples along with the corresponding predictions
from the valSeen and valUnseen splits of WAY dataset comparing LingUNet with
DiaLoc. Our single-shot method yields more precise and concentrated
predictions. Regarding the multi-shot results, DiaLoc showcases the capability
to rectify its previous predictions by leveraging the most recent dialog
information as guidance.

###  4.3 Multi-shot Predictions Analysis

As one of the most attractive aspects, employing multi-shot localization holds
the potential to early terminate the dialog in real-world searching and rescue
applications. In this section, we analyze the performance of multi-shot
methods using dialog up to timestep $t$. There exist several ways to determine
the predicted locations. Examples encompass hard argmax and soft
threshholding. Similar to single-shot evaluation, we use argmax to identify
the top-1 location based on the predicted heatmap. Alternatively, soft
threshholding identifying a set of top-K locations with probabilities
surpassing the threshold. Subsequently, evaluation metrics such as Recall and
Precision can be employed for measuring the performance. For simplicity, we
adopt argmax as a straightforward way to evaluate the interim predictions,
presenting the results in Figure 6. This will be unfair if multiple peaks show
up, and one is true. It is worth looking at the prediction probability at
ground-truth pixel.

To comprehend performance across various dialog length $T$, we group samples
from valSeen and valUnseen based on their respective dialog length. Each plot
showcases the mean localization error (LE) for different sample groups. In
each sub-plot, the LE at $t/T$ where $1\leq t\leq T$ depicts the performance
using incomplete dialog. Our method consistently demonstrates a trend wherein
using more turns leads to decreased LE across valSeen and valUnseen split,
while LingUNet exhibits varied behavior. Another notable observation is that
both methods exhibit lower performance in the case of lengthier dialogs,
particularly struggling with dialogs comprising $T=6$ turns. Introducing new
turns does not yield performance improvements, and is possibly due to the
unbalanced training data.

##  5 Conclusion

Localization using dialog is an important task in the field of Embodied AI and
significant progress has been achieved thanks to the advancements in vision
and language learning. In this work, we propose a novel approach DiaLoc for
iterative dialog-based localization. The key idea is to overcome the
limitations of existing methods that requires entire dialog for localization.
We introduce DiaLoc, a multimodal localizer, to continually fuse visual and
dialog inputs for accurate location prediction. Our work narrows the gap
between simulation and real-world applications, opening doors for future work
on multimodal dialog generation and collaborative localization.

##  6 Supplementary Materials

#### Multi-shot Adaptation of LingUNet.

LingUNet was designed for single-shot dialog localization. To enable it works
for multi-shot scenario so that fair evaluation is possible under our
iterative formulation, we make optimal modifications according to our proposed
DiaLoc-e. Basically, the idea is to leverage hidden states of previous
iteration for future predictions. The adapted LingUNet-ms is illustrated in
Figure 7. Similar to our DiaLoc-e, the map embedding F1 generated by ResNet18
is fed to LingUNet alongside the dialog embedding to generate hidden states
H1. The hidden states is then used as input to predict location heatmaps. In
particular, at each timestep $t$, the hidden states of previous timestep
$\text{H}1_{t-1}$ is fused with F1 to integrate the dynamic prior information.

Figure 7: LingUNet-ms: the adapted multi-shot multimodal LingUNet for
iterative embodied dialog localization.

#### Dialog Augmentation using LLM.

In this section, we provide additional details for leveraging LLM to augment
localization dialogs in WAY dataset. We employ gpt-3.5-turbo-16k as the LLM
instance to rewrite the ground-truth dialogs of training set. We use the
prompt as “ Paraphrase the dialog”. We set the temperature to 0.6 and the
top-p to 0.5 in the API call.

In Figure 8, we show two examples from the train split of WAY. For each
example, we display the top-down map and the corresponding target on the left.
On the right size, the GT dialog is shown at the top within the blue box, and
the para-phased version is shown inside the orange box. In both cases, we can
see that GPT generates semantically consistent dialogs as the original
version. In the second case, GPT reduced the length of the original dialog
without changing the meaning. Note that, the GPT API does not use map
information at all and is purely text-based.

Figure 8: Examples of ground-truth dialogs and augmented version using LLM.

#### Multi-shot analysis via prediction confidence.

As one of the most attractive aspects, employing multi-shot localization holds
the potential to early terminate the dialog in real-world searching and rescue
applications. In this section, we analyze the performance of multi-shot
methods using dialog up to timestep $t$. In addition to the localization error
based on top-1 prediction, we employ prediction confidence as an alternative
in this analysis. Localization error as a metric will be unfair in case of
multiple peaks show up, and one is true positive. To overcome this issue,
given heatmap prediction, we report the pixel-wise probability at ground-truth
location in Figure 9. In summary, our method depicts a trend that more turns
is helpful to increase the confidence level at the desired location while
LingUNet shows a negative trend.

Figure 9: Multi-shot prediction confidence analysis. To study performance
across varied dialog length, we group samples based on their length $T$ and
report average prediction confidence for each group. Within each sub-plot, the
PC at $t$ where $1\leq t\leq T$ is detailed. Our method depicts a trend that
more turns is helpful to increase the confidence at the desired location while
LingUNet shows negative trend.

#### Inference runtime and memory usage.

One of the limitations of the proposed approach is the memory usage and
decreased inference efficiency. We evaluate DiaLoc-e (depth=1) in the multi-
shot mode on the valSeen split of WAY. The evaluation results are shown in
Table 6.

Method |  Image Size (height x width) |  Runtime (second) |  GPU Usage (MiB)
---|---|---|---
LingUNet-ms | 455 x 780 | 0.768 | 1,273
DiaLoc-e | 224 x 224 | 1.374 | 3,875
Table 6: Average runtime and memory usage comparison at inference time. Batch
size is set to 1 for both methods. A Nvidia Titan RTX 24gb is used for the
benchmarking.

#### Additional visualizations.

In Fig.10, we visualize additional localization predictions comparing LingUNet
and the proposed method. For both methods, single-shot and multi-shot variants
are evaluated. We now share our insights from these representative examples.

  * •

Val-seen 87: DiaLoc predicts the correct location while LingUNet failed in the
single-shot mode. LingUNet-ms produces noisy but correct predictions. In
contrast, DiaLoc is capable of generating concentrated multi-modal (not to be
confused with _multimodal learning_) predictions.

  * •

Val-seen 176: Both approaches give acceptable predictions in the single-shot
mode. In multi-shot mode, DiaLoc recovers from its initial incorrect
prediction, out of two possible guesses.

  * •

Val-unseen 224: DiaLoc succeeds while LingUNet fails in the single-shot. In
multi-shot mode, LingUNet-ms generates noisy predictions, while DiaLoc
continually refining its prediction and converging towards the correct
location in the end.

  * •

Val-unseen 327: In the single-shot mode, both methods failed. In the multi-
shot mode, LingUNet-ms converged to a few locations, but none matches the GT.
For our DiaLoc, the predictions are incrementally refined to the right area.

LingUNet | Map |  |  |  |
---|---|---|---|---|---
DiaLoc | GT |  |  |  |
| val-seen 87 | Single-shot | Multi-shot: $1/3$ | $2/3$ | $3/3$
LingUNet | Map |  |  |  |
DiaLoc |  |  |  |  |
| val-seen 176 | Single-shot | Multi-shot: $1/5$ | $3/5$ | $5/5$
LingUNet | Map |  |  |  |
DiaLoc | GT |  |  |  |
| val-unseen 224 | Single-shot | Multi-shot: $1/3$ | $2/3$ | $3/3$
LingUNet | Map |  |  |  |
DiaLoc | GT |  |  |  |
| val-unseen 327 | Single-shot | Multi-shot: $1/3$ | $2/3$ | $3/3$
Figure 10: Qualitative results of single-shot and multi-shot location
predictions are presented. In the first column, the top-down map is displayed
alongside its corresponding ground truth (GT) location. The second column
displays the single-shot predictions, with LingUNet results above and DiaLoc
results below. The last three columns showcase the multi-shot predictions.

## References

  * Alayrac et al. [2022] Jean-Baptiste Alayrac, Jeff Donahue, Pauline Luc, Antoine Miech, Iain Barr, Yana Hasson, Karel Lenc, Arthur Mensch, Katherine Millican, Malcolm Reynolds, et al.  Flamingo: a visual language model for few-shot learning.  _Advances in Neural Information Processing Systems_ , 35:23716–23736, 2022.
  * 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.  Vision-and-language navigation: Interpreting visually-grounded navigation instructions in real environments.  In _Proceedings of the IEEE conference on computer vision and pattern recognition_ , pages 3674–3683, 2018.
  * Banerjee et al. [2021] Shurjo Banerjee, Jesse Thomason, and Jason Corso.  The robotslang benchmark: Dialog-guided robot localization and navigation.  In _Conference on Robot Learning_ , pages 1384–1393. PMLR, 2021.
  * Brown et al. [2020] Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al.  Language models are few-shot learners.  _Advances in neural information processing systems_ , 33:1877–1901, 2020.
  * Chang et al. [2017] Angel Chang, Angela Dai, Thomas Funkhouser, Maciej Halber, Matthias Niessner, Manolis Savva, Shuran Song, Andy Zeng, and Yinda Zhang.  Matterport3d: Learning from rgb-d data in indoor environments.  _arXiv preprint arXiv:1709.06158_ , 2017.
  * Devlin et al. [2018] Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova.  Bert: Pre-training of deep bidirectional transformers for language understanding.  _arXiv preprint arXiv:1810.04805_ , 2018.
  * Driess et al. [2023] Danny Driess, Fei Xia, Mehdi SM Sajjadi, Corey Lynch, Aakanksha Chowdhery, Brian Ichter, Ayzaan Wahid, Jonathan Tompson, Quan Vuong, Tianhe Yu, et al.  Palm-e: An embodied multimodal language model.  _arXiv preprint arXiv:2303.03378_ , 2023.
  * Hahn and Rehg [2022] Meera Hahn and James M Rehg.  Transformer-based localization from embodied dialog with large-scale pre-training.  _arXiv preprint arXiv:2210.04864_ , 2022.
  * Hahn et al. [2020] Meera Hahn, Jacob Krantz, Dhruv Batra, Devi Parikh, James M Rehg, Stefan Lee, and Peter Anderson.  Where are you? localization from embodied dialog.  _arXiv preprint arXiv:2011.08277_ , 2020.
  * Huang et al. [2015] Zhiheng Huang, Wei Xu, and Kai Yu.  Bidirectional lstm-crf models for sequence tagging.  _arXiv preprint arXiv:1508.01991_ , 2015.
  * Kolmet et al. [2022] Manuel Kolmet, Qunjie Zhou, Aljoša Ošep, and Laura Leal-Taixé.  Text2pos: Text-to-point-cloud cross-modal localization.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pages 6687–6696, 2022.
  * Li et al. [2022a] Boyi Li, Kilian Q Weinberger, Serge Belongie, Vladlen Koltun, and Rene Ranftl.  Language-driven semantic segmentation.  In _International Conference on Learning Representations_ , 2022a.
  * Li et al. [2021] Junnan Li, Ramprasaath Selvaraju, Akhilesh Gotmare, Shafiq Joty, Caiming Xiong, and Steven Chu Hong Hoi.  Align before fuse: Vision and language representation learning with momentum distillation.  _Advances in neural information processing systems_ , 34:9694–9705, 2021.
  * Li et al. [2022b] Junnan Li, Dongxu Li, Caiming Xiong, and Steven Hoi.  Blip: Bootstrapping language-image pre-training for unified vision-language understanding and generation.  In _International Conference on Machine Learning_ , pages 12888–12900. PMLR, 2022b.
  * Liao et al. [2022] Yiyi Liao, Jun Xie, and Andreas Geiger.  Kitti-360: A novel dataset and benchmarks for urban scene understanding in 2d and 3d.  _IEEE Transactions on Pattern Analysis and Machine Intelligence_ , 45(3):3292–3310, 2022.
  * Loshchilov and Hutter [2017] Ilya Loshchilov and Frank Hutter.  Decoupled weight decay regularization.  _arXiv preprint arXiv:1711.05101_ , 2017.
  * Manuel et al. [2022] Melvin P Manuel, Mariam Faied, Mohan Krishnan, and Mark Paulik.  Robot platooning strategy for search and rescue operations.  _Intelligent Service Robotics_ , pages 1–12, 2022.
  * Misra et al. [2018] Dipendra Misra, Andrew Bennett, Valts Blukis, Eyvind Niklasson, Max Shatkhin, and Yoav Artzi.  Mapping instructions to actions in 3d environments with visual goal prediction.  _arXiv preprint arXiv:1809.00786_ , 2018.
  * Queralta et al. [2020] Jorge Pena Queralta, Jussi Taipalmaa, Bilge Can Pullinen, Victor Kathan Sarker, Tuan Nguyen Gia, Hannu Tenhunen, Moncef Gabbouj, Jenni Raitoharju, and Tomi Westerlund.  Collaborative multi-robot search and rescue: Planning, coordination, perception, and active vision.  _Ieee Access_ , 8:191617–191643, 2020.
  * Radford et al. [2021] Alec Radford, Jong Wook Kim, Chris Hallacy, Aditya Ramesh, Gabriel Goh, Sandhini Agarwal, Girish Sastry, Amanda Askell, Pamela Mishkin, Jack Clark, et al.  Learning transferable visual models from natural language supervision.  In _International conference on machine learning_ , pages 8748–8763. PMLR, 2021.
  * Shah et al. [2023] Dhruv Shah, Błażej Osiński, Sergey Levine, et al.  Lm-nav: Robotic navigation with large pre-trained models of language, vision, and action.  In _Conference on Robot Learning_ , pages 492–504. PMLR, 2023.
  * Thomason et al. [2020] Jesse Thomason, Michael Murray, Maya Cakmak, and Luke Zettlemoyer.  Vision-and-dialog navigation.  In _Conference on Robot Learning_ , pages 394–406. PMLR, 2020.
  * Vaswani et al. [2017] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Łukasz Kaiser, and Illia Polosukhin.  Attention is all you need.  _Advances in neural information processing systems_ , 30, 2017.
  * Wang et al. [2023] Wenhui Wang, Hangbo Bao, Li Dong, Johan Bjorck, Zhiliang Peng, Qiang Liu, Kriti Aggarwal, Owais Khan Mohammed, Saksham Singhal, Subhojit Som, et al.  Image as a foreign language: Beit pretraining for vision and vision-language tasks.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pages 19175–19186, 2023.