While recent progress in video-text retrieval has been advanced by the exploration of better representation learning, in this paper, we present a novel multi-space multi-grained supervised learning framework, , to learn an aligned representation space shared between the video and the text for video-text retrieval.
The shared aligned space is initialized with a finite number of concept clusters, each of which refers to a number of basic concepts (words).
With the text data at hand, we are able to update the shared aligned space in a supervised manner using the proposed similarity and alignment losses.
Moreover, to enable multi-grained alignment, we incorporate frame representations for better modeling the video modality and calculating fine-grained and coarse-grained similarity.
Benefiting from learned shared aligned space and multi-grained similarity, extensive experiments on several video-text retrieval benchmarks demonstrate the superiority of  over existing methods.

§ INTRODUCTION

As a fundamental task in visual-language understanding <cit.>, video-text retrieval (VTR) <cit.> has attracted interest from academia and industry.
Although recent years have witnessed the rapid development of VTR with the support from powerful pretraining models <cit.>, improved retrieval methods <cit.>, and video-language datasets construction <cit.>, it remains challenging to precisely match video and language due to the raw data being in heterogeneous spaces with significant differences.

Current VTR research <cit.> mainly aims to learn a joint feature space across modalities and then compares representations in this space.
However, as the video and text representations often come from modality-independent encoders, it is challenging to directly compare and calculate the similarities between representations of different modalities from different encoders.
To alleviate the mismatch caused by heterogeneous encoders and data formats, <cit.> proposed to align modalities in a common space filled with learned concepts without supervision.
However, because of the unsupervised design, these concepts are either randomly initialized or updated in an unsupervised fashion, which blocks the power of that aligned space.
We argue that learning a shared aligned space with supervision is a promising way to improve video-text retrieval.

Our proposed supervised multi-space multi-grained aligning framework for video-text retrieval maps sentence, video, and frame representations to a shared aligned space to obtain aligned sentence, video, and frame representations.
Then, it calculates coarse- and fine-grained similarities to fully explore the power of the aligned space which is learned in a supervised fashion.
“Original space” represents the space containing the representations generated from modality-dependent encoders.
“Rep” refers to representation.

In this work, we propose a Supervised Multi-space multi-grained Alignment framework for VTR, namely , in which the aligned space is updated under the supervision of the video-text data at hand.
Specifically, we initialize a finite number of concept clusters by clustering a large number of basic concepts (words) to form the fine-grained aligned space.
In return, each concept cluster is composed of several words, which improves the interpretability of the model.
Then, we can match the text and video representations effectively
by projecting the video representation from the video encoder and text to this fine-grained aligned space.
The aligned sentence (text) representations can be obtained by looking up the abstract concept clusters.
To obtain aligned video representations, we first calculate the cosine similarity between the video representations and the abstract concept clusters.
Next, by summing up all the abstract concept clusters with the weight of the cosine similarity between video representation and concept clusters, we obtain the aligned video representations.
Furthermore, we design adapted similarity loss functions to update the representations of these abstract concepts, pushing the representations of text and video as close as possible in the shared aligned space.
This shared aligned space design not only improves the performance on VTR, but also allows us to interpret what the models have learned.

Recently, <cit.> demonstrated that incorporating fine-grained video representations (such as frame or segment representations) with high-level video features can further improve retrieval performance.
Inspired by their work, we further project frame representations into our designed aligned space.
Compared to high-level video representations, frame representations can be mapped to more detailed concepts, which enriches the overall video representations.
In this way, we have frame, video, and sentence representations from the aligned space and the original space, enabling us to calculate multi-space multi-grained (fine-grained and coarse-grained) similarity for exploring the potential of supervised aligned space.

Finally, to evaluate the effectiveness of our proposed , we conducted experiments on several video-text benchmarks, , MSR-VTT <cit.>, MSVD <cit.>, and ActivityNet <cit.>.
Benefiting from multi-grained and multi-space similarity, our proposed  outperforms previous methods on most of the benchmarks without requiring any additional data during training.

In summary, our contributions are as follows:

* We propose the shared aligned space to alleviate the problem of mismatched representations from different modalities, which arises from the raw data being in heterogeneous spaces and the heterogeneous design of modality-dependent encoders.

* Our proposed  achieves SOTA performance on several metrics across three VTR benchmarks.

* Detailed analysis reveals the importance of shared aligned space and multi-grained similarity.
Besides, we demonstrate that the design of shared aligned space and multi-grained similarity significantly impacts retrieval performance.

* We will open-source the code for facilitating future research.

§ RELATED WORKS

Video-Text Retrieval (VTR), which involves cross-modal alignment and abstract understanding of temporal images (videos), has been a popular task as a fundamental task of language-grounding problems.
Most existing conventional video-text retrieval frameworks <cit.> focus on learning powerful representations for video and text and extracting separated representations.
For example, in <cit.>, videos and texts are encoded using convolutional neural networks and a bi-GRU <cit.> while mean pooling is employed to obtain multi-level representations.
MMT <cit.> uses a cross-modal encoder to aggregate features extracted by temporal images, audio, and speech for encoding videos.
Following that, MDMMT <cit.> further utilizes knowledge learned from multi-domain datasets to improve performance empirically.
Further, MIL-NCE <cit.> adopts Multiple Instance Learning and Noise Contrastive Estimation for end-to-end video representation learning, addressing the problem of visually misaligned narrations from uncurated videos.

The illustration of representation generation in our proposed supervised multi-space multi-grained alignment framework, namely .
Specifically, for multi-space alignment, we employ a shared aligned space which is consisted of a number of concept clusters.
The shared aligned space could be updated in a supervised manner during the training procedure, leading to the construction of a fine-grained aligned space. “$\otimes$” refers to the calculation in Eqs. (<ref>), (<ref>), and (<ref>).

With the success of self-supervised pretraining methods <cit.>, vision-language pretraining <cit.> on large-scale unlabeled cross-modal data has shown promising performance in various tasks, , image retrieval, image caption and video retrieval.
Inspired by this, recent works <cit.> have attempted to pretrain or fine-tune video-text retrieval models in an end-to-end manner.
CLIPBERT <cit.>, as a pioneer, proposes to sparsely sample video clips for end-to-end training to obtain clip-level predictions and then summarize them.
Frozen in time <cit.> uses end-to-end training on both image-text and video-text pairs data by uniformly sampling video frames.
CLIP4Clip <cit.> finetunes models and investigates three similarity calculation approaches for video-sentence contrastive learning on CLIP <cit.>.
Further, TS2-Net <cit.> proposes a novel token shift and selection transformer architecture that adjusts the token sequence and selects informative tokens in both temporal and spatial dimensions from input video samples.
Later, DiscreteCodebook <cit.> propose to align modalities in a space filled with concepts, which are randomly initialled and unsupervisedly updated, while VCM <cit.> propose to construct a space with unsupervisedly clustered visual concepts.

However, due to the unsupervised design, these concepts are either randomly initialized or updated unsupervisedly, which limits the potential of that aligned space.
Meanwhile, these methods only perform the coarse-grained video-text similarity.
In comparison, our proposed  learn the aligned space in a supervised manner, using the supervision of text annotation, and calculate frame-sentence similarity for multi-space multi-grained alignment.

§ METHODS

In this section, we introduce our proposed framework for video-text retrieval, which aligns language and video in a shared aligned space.
Usually, in the video-text retrieval task, we have a set of examples $\{(\video_{i}, \text_{i})\}_{i \in [N]}$, where $N$ is the number of examples that are usually of two modalities video and language.

§.§ General Video-Text Retrieval Paradigm

In this part, we present a general video-text retrieval framework used by previous methods <cit.>.
With this paradigm, we can obtain three representations for different modalities from the original space, , frame representation $\framefeature$, video representation $\videofeature$, and sentence representation $\sentencefeature$ by modality-dependent encoders.

Frame and video representations:
Given a video $\video$, several video frames are first sampled as the inputs of the frame encoder to obtain the frame features $\framefeature \in \mathbb{R}^{n_{\text{frame}}\times d}$, where $n_{frame}$ is the number of frames and $d$ is the dimension of features.
As the frame representations $\framefeature$ are extracted through sampling, to explore the temporal correlation among different frames, we employ a temporal encoder to aggregate frame representations.
With the temporal encoder and the frame representations $\framefeature$, we obtain the video representations $\videofeature \in \mathbb{R}^{1\times d}$.

Sentence representation:
Given a sentence $\text$, we use a text encoder to obtain the text representation $∈ℝ^1×d$.

\subsection{Fine-Grained Shared Aligned Space}

The key to the video-text retrieval task is to precisely align representations from different modalities.
However, due to the heterogeneous encoder architectures and data formats of different modalities, it is difficult to align directly.
Therefore, instead of directly enforcing the representations to be aligned, we propose aligning them in a shared space which is constructed by $n_c$ concept clusters $C ∈ℝ^n_c ×d$.
Each concept cluster $𝐜$ represents several basic concepts.
Moreover, to supervise the updates of shared align space, we utilize the human-annotated knowledge at hand, \ie, text annotation in the paired video-text data.

\smallskip \noindent
\textbf{Initialization}.
First, with the embedding layer $f_emb$ of the text encoder, we map all the words into embeddings.
But as the number of words is relatively large (for example, in Clip, the number of sub-words is approximately 30k)
, we next cluster embeddings into $n_c$ clusters using KNN and represent all the words by their cluster's centers (concept clusters $C$).
Consequently, each concept cluster $𝐜$ represents a bunch of similar basic concepts (words), enabling fine-grained alignment.
The mapping from words to concepts is denoted by $h_w2c ∈[n_words] →{0,1}^n_c ×1$.
Now, $n_c$ concept clusters have been initialized.

\smallskip \noindent
\textbf{Obtaining the aligned sentence representation}.
For text, as the caption is at hand, we can directly
tokenize the sentences into words and look up the corresponding concepts in $𝐜$.
The aligned sentence representation $∈ℝ^1 ×d$ is obtained by averaging all the representations of concepts that are fetched with the surface form of the sentence.
\begin{equation}
\vspace{-0.3em}
\sentencecodebook = sim^{\text\top} C / |\text|\,,\label{eq:sentencecodebook}
\vspace{-0.3em}
\end{equation}
where $||$ is the number of words in $$ and $sim^{\text} = \sum_{\word \in \text}h_{w2c}(\word)$ is a vector with the length of $n_{c}$.

Obtaining the aligned video representation.
We first calculate the cosine similarity $\videocodebooksim \in \mathbb{R}^{1\times n_{c}}$ between the video representations and concept clusters $C$ as $\videocodebooksim_{j} = \operatorname{cos}(\videofeature, \mathbf{c}_{j}), \forall j \in [n_c]$, where $\videocodebooksim_{j}$ is the $j$-th element of $\videocodebooksim$ and $\operatorname{cos}$ is the cosine similarity.
Next, aligned video representations are obtained by

\begin{align}\small
\vspace{-0.3em}
\label{eq: videocodebook}\videocodebook &= \videocodebooksim C / \|\videocodebooksim\|_1 \,.
\vspace{-2em}
\end{align}

Obtaining the aligned frame representation.
Similarly, the cosine similarity $\framecodebooksim \in$$ \mathbb{R}^{n_{frame} \times n_{c}}$ between the frame representations and concept clusters is calculated as $\framecodebooksim_{i,j} = \operatorname{cos}(\framefeature_{i}, \mathbf{c}_{j}), \forall i \in [n_{frame}], \forall j \in [n_{c}]$, where $\framecodebooksim_{i,j}$ is the $(i,j)$-th element of $\framecodebooksim$ and $\framefeature_{i}$ is the $i$-th row of $\framefeature$.
Next, aligned frame representations are obtained as

\begin{align}\small
\framecodebook &= \sum_{i \in [n_{frame}]} \framecodebooksim_{i} C / \|\framecodebooksim_{i}\|_1\label{eq: framecodebook}\,.
\end{align}

Finally, we have the aligned frame, video, and sentence representations $\framecodebook \in \mathbb{R}^{n_{frame} \times d}, \videocodebook \in \mathbb{R}^{1 \times d}, \sentencecodebook \in \mathbb{R}^{1 \times d}$ with the frame and video aligned space similarity $\framecodebooksim \in \mathbb{R}^{n_{frame} \times n_{c}}$ and $\videocodebooksim \in \mathbb{R}^{n_{c}}$ along with the sentence aligned space similarity (supervision) $sim^{\text}$.

The illustration of multi-grained similarity.
To enable multi-grained alignment, we calculate fine-grained (frame-sentence) and coarse-grained (video-sentence) similarity. Our preliminary experiments showed that the text encoder has a good ability to capture the semantics, so we only use the sentence representation to calculate the similarity.

§.§ Multi-Space Multi-Grained Similarity

In this part, we will demonstrate our method for calculating the similarities between data from two different modalities, as shown in Figure <ref>,
including the similarities in the original space and in shared aligned space.
With the availability of frame, video, and sentence representations from both the aligned space and the original space, we can now compute multi-space multi-grained (fine-grained and coarse-grained) similarity for better alignment.

§.§.§ Original Space Similarity

Video-Sentence similarity $\videotosentencesim$.
To obtain a fine-grained similarity, we use a learnable matrix $\videotosentenceattention \in \mathbb{R}^{d\times d}$ to focus on the discriminative features of video and sentence representations

\begin{equation*}
\small
\vspace{-0.3em}
\videotosentencesim =  \videofeature \videotosentenceattention \feature^{s\top}\,.
\vspace{-0.3em}
\end{equation*}

Frame-Sentence similarity $\frametosentencesim$.
To obtain a fine-grained similarity, we first calculate an instance-aware weight using the softmax function applied to the dot product of $\sentencefeature \feature^{f\top}$, and then use a learnable matrix $\frametosentenceattention \in \mathbb{R}^{n_{frame} \times n_{frame}}$ to focus on discriminative frames.
In this way, the similarity is calculated as

\begin{equation*}
\small
\frametosentencesim = \operatorname{softmax}(\sentencefeature \feature^{f\top}) \frametosentenceattention \framefeature \feature^{s\top}\,.
\vspace{-0.3em}
\end{equation*}

§.§.§ Shared Aligned Space Similarity

Video-Sentence shared aligned space similarity $\videotosentencecodebooksim$.
Similarly, to obtain a fine-grained similarity on the shared aligned space, we use a learnable matrix $\videotosentencecodebookattention \in \mathbb{R}^{d\times d}$ to focus on the discriminative features of aligned video and sentence representation. Now, the similarity is calculated as

\begin{equation*}
\small
\videotosentencecodebooksim = \videocodebook \videotosentencecodebookattention \feature^{s,c\top}\,.
\vspace{-0.3em}
\end{equation*}

Frame-Sentence shared aligned space similarity $\frametosentencecodebooksim$.
With instance-aware weights $\operatorname{softmax}(\sentencecodebook \feature^{f,c\top})$ and a learnable matrix $\frametosentencecodebookattention \in \mathbb{R}^{n_{frame} \times n_{frame}}$, we get the similarity between the aligned frame and sentence representations as

\begin{equation*}
\small
\frametosentencecodebooksim = \operatorname{softmax}(\sentencecodebook \feature^{f,c\top}) \frametosentencecodebookattention \framecodebook \feature^{s,c\top}\,.
\end{equation*}

§.§.§ Overall Similarity

The overall video-text similarity is defined as

\begin{equation*}
\vspace{-0.3em}
\sim = \frac{\frametosentencesim + \videotosentencesim + \frametosentencecodebooksim + \videotosentencecodebooksim}{4}\,.
\end{equation*}

§.§ Objective

The objective consists of three different losses.
The first component is similarity loss.
Following Clip4Clip <cit.>, we employ the symmetric InfoNCE loss over the similarity matrix to optimize the retrieval model as

\begin{align*}
\vspace{-0.3em}
\ell_{sim} = & \ell_{v2t} + \ell_{t2v} \\
= & - \frac{1}{N} \sum_{i \in [N]} \log \frac{\exp(\sim_{i,i})}{\sum_{j\in[N]} \exp(\sim_{i,j})}\\
& - \frac{1}{N} \sum_{i \in [N]} \log \frac{\exp(\sim_{i,i})}{\sum_{j\in[N]} \exp(\sim_{j,i})}\,,
\vspace{-0.3em}
\end{align*}

where $\sim_{i,j}$ is similarity between $i$-th video and $j$-th text and $N$ is the number of video-text paired data.

The second loss we minimize is the alignment loss, which encourages the model to learn to match the video and frame representations with the concept clusters that appear in text $\text$,
\begin{align*}
\vspace{-0.3em}
\ell_{align} = & - \frac{1}{N} \sum_{i \in [N]} \left\|\videocodebook - \sentencecodebook \right\|_2 \\
& + \left\| \frac{\sum_{j \in [n_{frame}]}\mathbf{r}_{c,j}^{f}}{n_{frame}}  - \sentencecodebook\right\|_2\,,
\vspace{-0.3em}
\end{align*}
where $𝐫_c,j^f$ is the $j$-th row of $$.

In addition, to match the aligned frame and video representations ($$ and $$) with the aligned sentence representations $$, we minimize the aligned similarity loss as
\begin{align*}
\ell_{alignsim} = & - \frac{1}{N} \sum_{i \in [N]} \left\|\videocodebooksim - \sentencecodebooksim \right\|_2 \\
& +  \left\| \frac{\sum_{j \in [n_{frame}]}\framecodebooksim_{j}}{n_{frame}}  - \sentencecodebooksim \right\|_2\,,
\end{align*}
where $sim_j^f$ is the $j$-th row of $$.

The overall objective is the linear combination of the above three losses as
\begin{equation*}
\vspace{-0.3em}
\ell = \ell_{sim} + \alpha \ell_{align} + \beta \ell_{alignsim}\,,
\vspace{-0.3em}
\end{equation*}
where $α$ and $β$ are hyperparameters controlling the trade-off between three losses.

\section{Experiments}

\subsection{Datasets and Baselines}

\begin{table*}[ht!]
\centering
\resizebox{\textwidth}{!}{%
\begin{tabular}{lcccccccccc}
\toprule
\rowcolor{gray!30}             & \multicolumn{5}{c}{Text-to-Video Retrieval}                                        & \multicolumn{5}{c}{Video-to-Text Retrieval}                                        \\
\rowcolor{gray!30}             & R@1$\uparrow$ & R@5$\uparrow$ & R@10$\uparrow$ & MdR$\downarrow$ & MnR$\downarrow$ & R@1$\uparrow$ & R@5$\uparrow$ & R@10$\uparrow$ & MdR$\downarrow$ & MnR$\downarrow$ \\
\midrule
CLIP4Clip (ViT-B/32) & 44.5          & 71.4          & 81.6           & 2.0               & 15.3            & -             & -             & -              & -               & -               \\
Align\&Tell (ViT-B/32)         & 45.2          & 73.0          & 82.9           & 2.0             & -               & 43.4          & 70.9          & 81.8           & 2.0             & -               \\
CenterCLIP (ViT-B/32)    & 44.2          & 71.6          & 82.1           & 2.0               & 15.1            & \underline{42.8}          & {71.7}          & {82.2}           & 2.0               & {10.9}            \\
CLIP2TV (ViT-B/32)             & 45.6          & 71.1          & 80.8           & 2.0             & 15.0            & 43.9          & 70.9          & 82.2           & 2.0             & 12.0            \\
CLIP2Video (ViT-B/32)          & 45.6          & 72.6          & 81.7           & 2.0             & 14.6            & 43.5          & 72.3          & 82.1           & 2.0             & 10.2            \\
TS2-Net-seqTransf (ViT-B/32)   & \underline{47.0}          & \textbf{74.5}          & \textbf{83.8}           & 2.0             & \textbf{13.0}            & 45.3          & \textbf{74.1}          & \underline{83.7}           & 2.0             & \underline{9.2}             \\
X-CLIP-seqTransf (ViT-B/32)    & 46.1          & \underline{74.3}          & \underline{83.1}           & 2.0             & \underline{13.2}            & \underline{46.8}          & 73.3          & \textbf{84.0}           & 2.0             & \textbf{9.1}             \\
X-Pool (ViT-B/32)    & 46.9          & 72.8          & 82.2           & 2.0               & 14.3            & -             & -             & -              & -               & -               \\
\midrule
DiscreteCodebook (ViT-B/32)    & 43.4          & {72.3}          & 81.2           & -               & {14.8}            & 42.5          & 71.2          & 81.1           & -               & 12.0            \\
VCM (ViT-B/32)                 & 43.8          & 71.0          & -           & 2.0             & 14.3            & 45.1          & 72.3          & 82.3           & 2.0             & 10.7            \\
\rowcolor{gray!30}\ours\ (ViT-B/32)      & \textbf{49.1}   & 73.9   & 82.8   & 2.0    & 13.5    & \textbf{46.9}   & \underline{73.8}   & 82.1   & 2.0    & 9.3             \\
\bottomrule
CLIP4Clip (ViT-B/16) & 45.8*         & 74.3*         & 84.1*          & 2.0*              & -               & 43.2*         & 71.3*         & 82.0*          & 2.0*              & -               \\
Align\&Tell (ViT-B/16)         & 47.4          & 74.3          & 84.1           & 2.0             & -               & 45.3          & 73.5          & 83.7           & 2.0             & -               \\
CenterCLIP (ViT-B/16)    & 48.4          & 73.8          & 82.0           & 2.0               & 13.8            & \underline{47.7}          & 75.0          & 83.3           & 2.0               & 10.2            \\
CLIP2TV (ViT-B/16)             & 49.3          & 74.7          & 83.6           & 2.0             & \underline{13.5}            & 46.9          & 75.0          & \textbf{85.1}           & 2.0             & 10.0            \\
HiSE (ViT-B/16)      & 45.0          & 72.7          & 81.3           & 2.0             & -               & 46.6          & 73.3          & 82.3           & 2.0             & -               \\
TS2-Net (ViT-B/16)   & \underline{49.4}          & \underline{75.6}          & \textbf{85.3}           & 2.0             & \underline{13.5}            & 46.6          & 75.9          & \underline{84.9}           & 2.0             & \underline{8.9}             \\
X-CLIP (ViT-B/16)    & 49.3          & \textbf{75.8}          & \underline{84.8}           & 2.0             & \textbf{12.2}            & \textbf{48.9}          & \textbf{76.8}          & 84.5           & 2.0             & \textbf{8.1}             \\
\midrule
\rowcolor{gray!30}\ours\ (ViT-B/16)      & \textbf{49.8}          & 75.1          & 83.9           & 2.0             & \textbf{12.2}            & 47.3          & \underline{76.0}          & 84.3           & 2.0             & \underline{8.9}            \\
\bottomrule
\end{tabular}%
\vspace{-0.3cm}
\caption{Video-Text retrieval results on MSR-VTT. * represents data copied from Align\&Tell. The best results are marked in \textbf{bold}. The second best results are \underline{underlined}.}
\label{tab:msr-vtt}
\vspace{-0.3cm}
\end{table*}

\begin{table}[t!]
\centering
\resizebox{\columnwidth}{!}{%
\begin{tabular}{l|cccc}
\toprule
\rowcolor{gray!30}                              & \multicolumn{4}{c}{Text-to-Video Retrieval}                      \\
\rowcolor{gray!30}                               & R@1$\uparrow$ & R@5$\uparrow$ & R@10$\uparrow$ & MnR$\downarrow$ \\
\midrule
CLIP4Clip-MeanP (ViT-B/32)     & 46.2          & 76.1          & 84.6           & 10.0            \\
CLIP4Clip-seqTransf (ViT-B/32) & 45.2          & 75.5          & 84.3           & 10.3            \\
X-CLIP (ViT-B/32)              & 47.1          & \underline{77.8}          & -              & \underline{9.5}             \\
CLIP2VIDEO                     & 47.0          & 76.8          & 85.9           & 9.6             \\
HiSE                           & 45.9          & 76.2          & 84.6           & -               \\
X-Pool                         & \underline{47.2}          & 77.4          & \textbf{86.0}           & \textbf{9.3}             \\
\midrule
\rowcolor{gray!30}\ours (ViT-B/32)                         & \textbf{47.3}          & \textbf{78.8}          & \underline{85.7}           & \textbf{9.3}
\\
\bottomrule
\end{tabular}%
\vspace{-0.3cm}
\caption{Text-Video retrieval results on MSVD. The best results are marked in \textbf{bold}. The second best results are \underline{underlined}.}
\vspace{-0.3cm}
\label{tab:msvd}
\end{table}

\begin{table}[t!]
\centering
\resizebox{\columnwidth}{!}{%
\begin{tabular}{l|cccc}
\toprule
\rowcolor{gray!30}                               & \multicolumn{4}{c}{Text-to-Video Retrieval}                      \\
\rowcolor{gray!30}                               & R@1$\uparrow$ & R@5$\uparrow$ & R@10$\uparrow$ & MnR$\downarrow$ \\
\midrule
CLIP4Clip-MeanP (ViT-B/32)     & 40.5          & 72.4          &-& 7.4             \\
CLIP4Clip-seqTransf (ViT-B/32) & 40.5          & 72.4          & -               & 7.5             \\
Align\&Tell (ViT-B/32)         & 42.6          & 73.8          & -              & -               \\
X-CLIP (ViT-B/32)              & \underline{44.3}          & \underline{74.1}          & -              & 7.9             \\
TS2-Net                        & 41.0          & 73.6          & \underline{84.5}           & 8.4             \\
\midrule
VCM                            & 40.8          & 72.8          & -              & \underline{7.3}             \\
\rowcolor{gray!30}\ours (ViT-B/32)               & \textbf{45.0}          & \textbf{75.5}          & \textbf{85.7}           & \textbf{6.3}            \\
\bottomrule
\end{tabular}%
\vspace{-0.2cm}
\caption{Text-Video retrieval results on ActivityNet. The best results are marked in \textbf{bold}. The second best results are \underline{underlined}.}
\vspace{-0.3cm}
\label{tab: actnet}
\end{table}

To show the empirical efficiency of our \ours, we train models on MSR-VTT~\cite{DBLP:conf/cvpr/XuMYR16}, MSVD~\cite{chen-dolan-2011-collecting}, and ActivityNet~\cite{caba2015activitynet}.
For a fair comparison, we only compare our methods with methods that are based on CLIP~\cite{DBLP:conf/icml/RadfordKHRGASAM21}, \ie, Clip4Clip~\cite{DBLP:journals/ijon/LuoJZCLDL22}, CLIP2TV~\cite{DBLP:journals/corr/abs-2111-05610},
VCM~\cite{DBLP:conf/aaai/CaoW0022}, HiSE~\cite{DBLP:conf/mm/WangXHLJHD22},
Align\&Tell~\cite{9878037}, CenterCLIP~\cite{10.1145/3477495.3531950},
Implementation details and evaluation protocols are deferred to the Appendix.

\subsection{Main Results}

\smallskip \noindent
\textbf{MSR-VTT.}
As shown in Table~\ref{tab:msr-vtt}, \ours\ achieves the best R@1 on the text-to-video retrieval results using ViT-B/32 and ViT-B/16, outperforming the second-best method by $2.1$ and $0.4$, respectively.
The performance of \ours~on the video-to-text retrieval task is also comparable with previous methods, achieving the second-best results on R@1 and R@5 using ViT-B/32.
Moreover, we notice that only 3 out of 7 previous methods using ViT-B/16 outperform \ours \ with ViT-B/32 on the text-to-video retrieval, demonstrating the effectiveness of \ours.
Compared to DiscreteCodebook~\cite{liu-etal-2022-cross}, which aligns modalities in an unsupervised manner, \ours\ outperforms DiscreteCodebook on every metric.
Meanwhile, \ours\ also outperforms VCM~\cite{DBLP:conf/aaai/CaoW0022}, which constructs an aligned space with unsupervisedly clustered visual concepts, demonstrating the importance of supervising alignment in the aligned space.
This suggests that aligning modalities with fine-grained supervision is a promising approach to improve video-to-text retrieval performance.

\smallskip \noindent
\textbf{MSVD and ActivityNet.}
The results on MSVD and ActicityNet are shown in Tables~\ref{tab:msvd} and~\ref{tab: actnet}.
\ours\ achieves the best R@1 on text-video retrieval on two datasets with a slight improvement compared to the previous methods.
Besides, with the shared aligned space and multi-grained alignment, \ours\ also has the lowest MnR.

\subsection{Ablation Studies}
In this part, we present a series of ablation experiments to demonstrate the effectiveness of different components in \ours.
The results reported in this section are based on the MSR-VTT dataset.
To qualitatively validate the effectiveness of \ours, we present some retrieval examples in Figures~\ref{fig: V2T} and \ref{fig: T2V} in the Appendix.
Meanwhile, the evaluation of two proposed losses is deferred to the Appendix.

\subsubsection{Efficiency of Aligned Space}
\begin{table*}[h!]
\centering
\resizebox{\textwidth}{!}{%
\begin{tabular}{lcccccccccc}
\toprule
& \multicolumn{5}{c}{Text-to-Video Retrieval}                                        & \multicolumn{5}{c}{Video-to-Text Retrieval}                                        \\
& R@1$\uparrow$ & R@5$\uparrow$ & R@10$\uparrow$ & MdR$\downarrow$ & MnR$\downarrow$ & R@1$\uparrow$ & R@5$\uparrow$ & R@10$\uparrow$ & MdR$\downarrow$ & MnR$\downarrow$ \\
\midrule
\ours\ (ViT-B/32) w. SE                  &   47.3 & 73.5 & 82.0 & 2.0 & 13.3 & 45.6 & 73.4 & 82.4 & 2.0 & 9.1   \\
\ours\ (ViT-B/32) w. Emb     & 49.1   & 73.9   & 82.8  & 2.0    & 13.5    & 46.9   & 73.8   & 82.1   & 2.0    & 9.3             \\

\bottomrule
\end{tabular}%
\vspace{-0.3cm}
\caption{
Comparing the power of different aligned spaces on MSR-VTT.
``Emb'' and ``SE''  refers to the embedding space and semantic embedding space.
\label{tab: semantic embeddings}
\vspace{-0.3cm}
\end{table*}

\begin{table*}[h!]
\centering
\resizebox{\textwidth}{!}{%
\begin{tabular}{lcccccccccc}
\toprule
& \multicolumn{5}{c}{Text-to-Video Retrieval}                                        & \multicolumn{5}{c}{Video-to-Text Retrieval}                                        \\
& R@1$\uparrow$ & R@5$\uparrow$ & R@10$\uparrow$ & MdR$\downarrow$ & MnR$\downarrow$ & R@1$\uparrow$ & R@5$\uparrow$ & R@10$\uparrow$ & MdR$\downarrow$ & MnR$\downarrow$ \\
\midrule
\ours\ (ViT-B/32) w/o clustering concepts                  &  48.7 & 74.4& 83.0 & 2.0 & 13.4 & 46.7 & 73.3& 82.6 & 2.0 & 9.2 \\
\ours\ (ViT-B/32)      & 49.1   & 73.9   & 82.8  & 2.0    & 13.5    & 46.9   & 73.8   & 82.1   & 2.0    & 9.3             \\
\bottomrule
\end{tabular}%
\vspace{-0.3cm}
\caption{Ablation study on the effect of clustering when constructing the shared aligned space.}
\label{tab: not cluster}
\vspace{-0.5cm}
\end{table*}
\textbf{The choice of different aligned spaces}.
In order to determine which aligned space is better, we conduct experiments on MSR-VTT using two different aligned spaces, \ie, the embedding space, and semantic embedding space.
The embedding space is the one we use in \ours, while the semantic embedding space, is initialized by the representations of the last layer generated by the text encoder, with input consisting of a word and two SEP tokens.
The results are shown in Table~\ref{tab: semantic embeddings}.
By replacing the embedding initialization with the semantic embedding, the retrieval performance of \ours\ decreases, proving the superiority of embedding space over the semantic embedding space.

\begin{table}[t!]
\centering
\resizebox{\columnwidth}{!}{%
\begin{tabular}{l|ccc|ccc}
\toprule
\multirow{2}{*}{Size} & \multicolumn{3}{c|}{Text-to-Video Retrieval}                          & \multicolumn{3}{c}{Video-to-Text Retrieval}   \\
& R@1                     & R@5              & MnR & R@1                     & R@5              & MnR \\
\midrule
512                            & \underline{48.7}        & 73.0             & \textbf{12.9}  & 46.4                    & 72.8             & \textbf{9.0}   \\
1024                           & \textbf{49.1}           & \textbf{73.9}    & \underline{13.5}  & \underline{46.9}                    & \textbf{73.8}    & 9.3   \\
2048                           & 48.3                    & \textbf{73.9}    & \underline{13.5}  & \textbf{47.0}                    & 72.7             & \underline{9.1}   \\
4096                           & 47.6                    & \underline{73.6} & 13.6  & 46.8                    & \underline{73.4} & 9.3   \\ \midrule
DC (1024)    & 43.4          & 72.3                   & 14.8            & 42.5          & 71.2               & 12.0            \\
VCM                  & 43.8          & 71.0                & 14.3            & 45.1          & 72.3             & 10.7            \\
\bottomrule
\end{tabular}%
\vspace{-0.5cm}
\caption{Retrieval performance with different sizes of aligned space on the MSR-VTT dataset using \ours\ with ViT/B-32. ``DC'' represents DiscreteCodebook~\cite{liu-etal-2022-cross}, which also aligns modalities in an aligned space whose size is 1024 with ViT/B-32. The best results are marked in \textbf{bold}. The second best results are \underline{underlined}.}
\vspace{-0.3cm}
\label{tab:ablation codebook size}
\end{table}

\begin{table*}[ht!]
\centering
\resizebox{\textwidth}{!}{%
\begin{tabular}{cc|cc|ccccc|cccccc}
\toprule
\multicolumn{2}{c|}{Original Space} & \multicolumn{2}{c|}{Aligned Space} & \multicolumn{5}{c|}{Text-to-Video Retrieval}                                          & \multicolumn{5}{c}{Video-to-Text Retrieval}                                                                                \\
S-V    & S-F   & S-V       & S-F      & R@1$\uparrow$ & R@5$\uparrow$ & R@10$\uparrow$ & MdR$\downarrow$ & MnR$\downarrow$ & R@1$\uparrow$ & R@5$\uparrow$ & R@10$\uparrow$ & MdR$\downarrow$ & MnR $\downarrow$ \\\midrule
\Checkmark      &                  &                      &                                          & 42.8          & 72.0          & 82.3           & 2.0             & 15.0              & 41.9          & 71.1          & 81.5           & 2.0             & 11.1                                                             \\
\Checkmark      &                  & \Checkmark     &    & 43.3          & 70.5          & 81.4           & 2.0             & 15.6              & 42.5          & 71.0          & 80.9           & 2.0             & 11.9                                         \\

& \Checkmark     &                      &                     &  44.4          & 71.8          & 81.8           & 2.0             & 14.5              & 44.1          & 71.8          & 81.7           & 2.0             & 10.4                                                       \\
& \Checkmark     &                      & \Checkmark        & 44.8          & 72.1          & 81.7           & 2.0             & 15.9              & 41.7          & 70.2          & 79.6           & 2.0             & 10.8                                                          \\

\midrule
\Checkmark      &                  &                      & \Checkmark        & 42.9          & 72.3          & 81.6           & 2.0             & 15.2              & 42.0          & 70.9          & 81.1           & 2.0             & 11.0                                                         \\
& \Checkmark     & \Checkmark         &                     & 43.8          & 72.1          & 82.3           & 2.0             & 14.7              & 41.5          & 70.6          & 80.3           & 2.0             & 9.8                                                          \\
\midrule
\Checkmark      & \Checkmark     &                      &                     & 44.0          & 71.3          & 80.9           & 2.0             & 14.8              & 43.6          & 69.5          & 80.1           & 2.0             & 10.4                                                         \\

\Checkmark      & \Checkmark     & \Checkmark         &                     & 47.4          & 73.3          & 82.4           & 2.0             & 12.9              & 46.4          & 73.0          & 82.2           & 2.0             & 8.9                                                          \\
\Checkmark      & \Checkmark     &                      & \Checkmark        & 47.4          & 73.6          & 82.5           & 2.0             & 13.2              & 47.3          & 72.3          & 81.7           & 2.0             & 8.9                                                          \\
\Checkmark      & \Checkmark     & \Checkmark         & \Checkmark        &      49.1   & 73.9   & 82.8   & 2.0    & 13.5    & 46.9   & 73.8   & 82.1   & 2.0    & 9.3         \\
\bottomrule
\end{tabular}%
\caption{Retrieval performance with different similarities on MSR-VTT using \ours\ with the base model of ViT-B/32. ``S-V'' and ``S-F'' represent Sentence-Video (coarse-grained) and Sentence-Frame (fine-grained) similarities.}
\label{tab:ablation study similarity}
\end{table*}

\smallskip \noindent
\textbf{Size of aligned space. }
Another important factor to consider is the size of the aligned space.
When we have unlimited data to train models, a large aligned space is ideal.
However, when the data is limited, a large aligned space can lead to sparse gradients, resulting in most concepts not being able to be updated, while a small aligned space will restrict the retrieval ability as it becomes more challenging to distinguish between numerous data points.
The results of these experiments can be found in Table~\ref{tab:ablation codebook size}. We see that halving and doubling the size of the aligned space slightly decreases performance, which is reasonable.

\smallskip \noindent
\textbf{Impact of clustering}.
As \ours~clusters all the embeddings to initialize concept clusters, it is uncertain whether clustering will hinder the power of the shared aligned space.
Clustering can be useful to extract high-level abstract concepts and reduce noise.
However, it may also lead to a loss of information, which is important for fine-grained alignment.
Specifically, we compare the performance of \ours to that of a modified version, \ours w/o clustering concepts, which directly uses over 30k basic concepts to form the shared aligned space.
Quantitative results can be found in Table~\ref{tab: not cluster}.
The results show that without clustering, R@5, R@10, and MnR on text-to-video retrieval and R@10 and MnR on video-to-text retrieval are improved.
On one hand, as the number of concepts increases, similar basic concepts can be better separated, which leads to more accurate alignment.
On the other hand, the increase in the number of concepts may lead to sparse gradients, resulting in some concepts not being fully updated while others are over-updated.
This might cause some concepts to be under or over-represented, which might negatively impact the performance.
Therefore, it's important to find the balance between the number of concepts and clustering to achieve the best performance.

\subsubsection{Efficiency of Multi-Grained Similarities}
In order to fully evaluate the impact of multi-grained similarities, we conduct an ablation study to compare different variants of \ours.
The results of this study can be found in Table~\ref{tab:ablation study similarity}.
From these results, we can draw three conclusions,
\begin{itemize}
\item
Using multi-space and multi-grained similarities simultaneously achieves the best performance.
R@1 on text-to-video and video-to-text retrieval is significantly improved from 42.8 and 41.9 to 49.1 and 46.9, respectively.
\item
Multi-grained similarities are crucial for retrieval.
Using both coarse- and fine-grained alignments in the original space improved R@1 from 42.8 and 41.9 to 44.0 and 43.6 on text-to-video and video-to-text retrieval compared with only using coarse-grained alignment in the original space, respectively.
The same observation can be made from the results of the last three rows of Table~\ref{tab:ablation study similarity} in the aligned space.
However, using different types of similarities in two spaces harms performance, likely due to misalignment between the two spaces.
\item
The aligned space plays a crucial role in improving the alignment of modalities.
We observe that incorporating fine-grained (sentence-frame) similarities in the original space and aligned space can improve R@1 for text-to-video retrieval from 43.3 to 44.8 compared to only performing fine-grained similarities in the original space, respectively.
Similar observations can be obtained by incorporating coarse-grained (sentence-video) similarities in the original space and aligned space.
\end{itemize}

\subsubsection{Other Quantitative Results}

\begin{table}[t!]
\centering
\resizebox{\columnwidth}{!}{%
\begin{tabular}{l|c|ccc|ccc}
\toprule
\multirow{2}{*}{Base Model}           & \multirow{2}{*}{TE} & \multicolumn{3}{c|}{Text-to-Video} & \multicolumn{3}{c}{Video-to-Text} \\
&                     & R@1       & R@5       & MnR      & R@1       & R@5       & MnR     \\
\midrule
\multirow{2}{*}{ViT-B/32} &                     & 47.0      & 73.9      & 14.5       & 45.7      & 72.3      & 9.6       \\
& \Checkmark          & 49.1      & 73.9      & 13.5       & 46.9      & 73.8      & 9.3       \\
\midrule
\multirow{2}{*}{ViT-B/16} &   &   47.3&74.9&12.8&46.1&75.1&9.5      \\
&  \Checkmark         & 49.8      & 75.1      & 12.2       & 47.3      & 76.0      & 8.9       \\
\bottomrule
\end{tabular}%
\caption{Retrieval performance with or without the temporal encoder (``TE'') and with different base models.}
\vspace{-0.3cm}
\label{tab:temporal encoder and bigger model}
\end{table}

\textbf{Temporal encoder and the larger model.}
We also conduct experiments to investigate the effect of the temporal encoder and different base models of \ours.
The results are shown in Table~\ref{tab:temporal encoder and bigger model}.
With ViT-B/32, \ours\ with temporal encoder outperforms \ours \ without temporal encoder, because the temporal encoder (a small sequence transformer) is able to better model the temporal relation among different frames in a video.
Without the temporal encoder, models might not be able to summarize the information from multiple frames.
Besides, using a larger base model, such as ViT-B/16, further improves the performance of \ours, as a larger base model typically has better representation learning abilities benefiting this retrieval task as well.
Similar conclusions can be found in previous works \cite{DBLP:journals/ijon/LuoJZCLDL22,DBLP:conf/mm/MaXSYZJ22}.

\section{Conclusion}
In this paper, to better align video and text modalities, we proposed a multi-space, multi-grained video-text retrieval framework, namely \ours.
Specifically, \ours\ aligned different modalities in a fine-grained aligned space which is initialized with a finite number of concept clusters, that consisted of a number of basic concepts (words).
The shared aligned space was updated in a supervised fashion, enabling fine-grained alignment.
Besides, for multi-grained alignment, \ours\ employed frame (fine-grained) and video (coarse-grained) features in the video modality and calculated multi-grained similarity to encourage models to perform multi-grained aligning.
Finally, we conducted extensive experiments on three representative video-text retrieval benchmarks, showing the superiority of \ours.

\section*{Limitations}
In the future, it would be promising to seek more fine-grained alignment, such as instance-level or character-level alignment, for aligning different modalities.
Additionally, incorporating the relation between different instances and frames would be beneficial for the video-text retrieval problem.

\bibliography{anthology,custom}
\bibliographystyle{acl_natbib}
\clearpage

\appendix

\begin{table*}[h!]
\centering
\resizebox{\textwidth}{!}{%
\begin{tabular}{lcccccccccc}
\toprule
& \multicolumn{5}{c}{Text-to-Video Retrieval}                                        & \multicolumn{5}{c}{Video-to-Text Retrieval}                                        \\
& R@1$\uparrow$ & R@5$\uparrow$ & R@10$\uparrow$ & MdR$\downarrow$ & MnR$\downarrow$ & R@1$\uparrow$ & R@5$\uparrow$ & R@10$\uparrow$ & MdR$\downarrow$ & MnR$\downarrow$ \\
\midrule
\ours\ (ViT-B/32) w. multi-label classification                  &   47.0 & 73.6 & 82.9 & 2.0 & 12.5 & 45.5 & 73.8 & 82.8 & 2.0 & 8.7   \\
\ours\ (ViT-B/32) w. cosine     & 49.1   & 73.9   & 82.8  & 2.0    & 13.5    & 46.9   & 73.8   & 82.1   & 2.0    & 9.3             \\

\bottomrule
\end{tabular}%
\caption{Ablation study on the calculation of similarity between video and frame representations and cluster concepts.
\label{tab: mls}
\end{table*}

\begin{table*}[h!]
\centering
\resizebox{\textwidth}{!}{%
\begin{tabular}{lcccccccccc}
\toprule
& \multicolumn{5}{c}{Text-to-Video Retrieval}                                        & \multicolumn{5}{c}{Video-to-Text Retrieval}                                        \\
& R@1$\uparrow$ & R@5$\uparrow$ & R@10$\uparrow$ & MdR$\downarrow$ & MnR$\downarrow$ & R@1$\uparrow$ & R@5$\uparrow$ & R@10$\uparrow$ & MdR$\downarrow$ & MnR$\downarrow$ \\
\midrule
\ours\ (ViT-B/32) w/o anchor                  &   47.8&72.9&82.3&2.0&13.4&46.4&74.9&82.1&2.0&9.1   \\
\ours\ (ViT-B/32) w. anchor     & 49.1   & 73.9   & 82.8  & 2.0    & 13.5    & 46.9   & 73.8   & 82.1   & 2.0    & 9.3             \\

\bottomrule
\end{tabular}%
\caption{Ablation study on the instruction of text, \ie, generating $\sentencecodebook$ using the similarity or the text.
``w. anchor'' refers to obtain $\sentencecodebook$ by text as Eq.~\eqref{eq:sentencecodebook}.
``w/o anchor'' refers to obtain $\sentencecodebook$ by the similarity between sentence representations and concepts $C$ as Eq.~\eqref{eq: similarity sentence codebook}
\label{tab: wot gold}
\end{table*}

\begin{table*}[ht!]
\centering
\resizebox{\textwidth}{!}{%
\begin{tabular}{cc|ccccc|ccccc}
\toprule
&         & \multicolumn{5}{c|}{Text-to-Video Retrieval}                                       & \multicolumn{5}{c}{Video-to-Text Retrieval}                                         \\
$\ell_{align}$ & $\ell_{alignsim}$ & R@1$\uparrow$ & R@5$\uparrow$ & R@10$\uparrow$ & MnR$\downarrow$ & MeanR$\downarrow$ & R@1$\uparrow$ & R@5$\uparrow$ & R@10$\uparrow$ & MnR$\downarrow$ & MeanR$\downarrow$ \\ \midrule
&        & 48.0          & 72.9          & 82.4           & 2.0             & 13.5              & 45.4          & 73.2          & 82.1           & 2.0             & 9.3               \\
\Checkmark     &        & 48.0          & 73.5          & 82.7           & 2.0             & 13.4              & 47.1          & 74.2          & 82.9           & 2.0             & 9.1               \\
& \Checkmark    & 47.4          & 73.5          & 82.7           & 2.0             & 13.5              & 46.8          & 73.2          & 82.2           & 2.0             & 9.2               \\
\Checkmark     & \Checkmark    & 49.1          & 73.9          & 82.8           & 2.0             & 13.5              & 46.9          & 73.8          & 82.1           & 2.0             & 9.3               \\\bottomrule
\end{tabular}%
\caption{Ablation study of $\ell_{align}$ and $\ell_{alignsim}$ on MSR-VTT based on \ours~(ViT-B/32).}
\label{tab: two losses}
\end{table*}

\begin{table*}[ht!]
\centering
\resizebox{\textwidth}{!}{%
\begin{tabular}{cc|ccccc|ccccc}
\toprule
&         & \multicolumn{5}{c|}{Text-to-Video Retrieval}                                       & \multicolumn{5}{c}{Video-to-Text Retrieval}                                         \\
$\alpha$ & $\beta$ & R@1$\uparrow$ & R@5$\uparrow$ & R@10$\uparrow$ & MnR$\downarrow$ & MeanR$\downarrow$ & R@1$\uparrow$ & R@5$\uparrow$ & R@10$\uparrow$ & MnR$\downarrow$ & MeanR$\downarrow$ \\ \midrule
0.02     & 0.01    & 49.1          & 73.9          & 82.8           & 2.0             & 13.5              & 46.9          & 73.8          & 82.1           & 2.0             & 9.3               \\
\midrule
0.02     & 0.02    & 48.5          & 73.8          & 83.2           & 2.0             & 14.0              & 46.3          & 73.1          & 82.1           & 2.0             & 9.4               \\
0.02     & 0.05    & 47.6          & 72.7          & 82.4           & 2.0             & 14.0              & 45.8          & 74.0          & 82.2           & 2.0             & 9.2               \\
0.02     & 0.1     & 47.7          & 72.3          & 82.9           & 2.0             & 13.4              & 45.3          & 73.6          & 83.3           & 2.0             & 9.0               \\
\midrule
0.01     & 0.01    & 47.6          & 74.0          & 82.7           & 2.0             & 13.8              & 46.7          & 82.2          & 73.5           & 2.0             & 9.5               \\
0.05     & 0.01    & 48.1          & 73.6          & 83.1           & 2.0             & 13.2              & 46.3          & 72.9          & 82.7           & 2.0             & 9.1               \\
0.1      & 0.01    & 47.9          & 74.2          & 82.3           & 2.0             & 13.3              & 46.3          & 73.4          & 82.5           & 2.0             & 9.1               \\
\bottomrule
\end{tabular}%
\caption{Ablation study of $\alpha$ and $\beta$ on MSR-VTT based on \ours~(ViT-B/32).}
\label{tab: two losses changing}
\end{table*}

\begin{figure*}[t!]
\centering
\includegraphics[width=1\textwidth]{pics/V2T_examples.pdf}
\caption{Top-5 video-to-text retrieval results on MSR-VTT.
}\label{fig: V2T}
\end{figure*}

\begin{figure*}[t!]
\centering
\includegraphics[width=1\textwidth]{pics/T2V_examples.pdf}
\caption{Top-3 text-to-video retrieval results on MSR-VTT.
}\label{fig: T2V}
\end{figure*}

\section{Experiments}

\subsection{Datasets Details}

\textbf{MSR-VTT}~\cite{DBLP:conf/cvpr/XuMYR16} contains 10,000 videos with length varying from 10 to 32
seconds, each paired with about 20 human-labeled captions.
Following the evaluation protocol from previous works~\citet{DBLP:conf/eccv/YuKK18,DBLP:conf/iccv/MiechZATLS19}, we use the training-9k / test 1k-A splits for training and testing respectively.

\textbf{MSVD}~\cite{chen-dolan-2011-collecting} contains 1,970 videos with a split of 1200, 100, and 670 as the train, validation, and test set, respectively.
The duration of videos varies from 1 to 62 seconds.
Each video is paired with 40 English captions.

\textbf{ActivityNet}~\cite{caba2015activitynet} is consisted of 20,000 Youtube videos with 100,000 densely annotated descriptions.
For a fair comparison, following the previous setting~\cite{DBLP:journals/ijon/LuoJZCLDL22,DBLP:conf/eccv/Gabeur0AS20}, we concatenate all captions together as a paragraph to perform a video-paragraph retrieval task by concatenating all the descriptions of a video.
Performances are reported on the ``val1'' split of the ActivityNet.

\subsection{Implementation Details and Evaluation Protocols}

Following \citet{DBLP:journals/ijon/LuoJZCLDL22,DBLP:conf/mm/MaXSYZJ22}, we use a standard vision transformer~\cite{DBLP:conf/iclr/DosovitskiyB0WZ21} with $12$ layers which are initialized with the public CLIP~\cite{DBLP:conf/icml/RadfordKHRGASAM21} checkpoints.
We directly use the text encoder of CLIP as our text encoder which is also initialized with the public CLIP checkpoints.

We set the query, key, and value projection dimension size as $512$ to match CLIP’s output dimension and we initialize our logit scaling parameter $λ$ with the value from the pre-trained CLIP model.
All models are optimized for 5 epochs on MSR-VTT and MSVD, and for ActivityNet, the models are trained for 20 epochs. We use AdamW~\cite{DBLP:conf/iclr/LoshchilovH19} with a weight decay of 0.2 and decay the learning rate using a cosine schedule~\cite{DBLP:conf/iclr/LoshchilovH17}, following the method used in CLIP~\cite{DBLP:conf/icml/RadfordKHRGASAM21}.
For all experiments, we uniformly sample 12 frames from every video, resizing each frame to 224x224 as per previous works~\cite{DBLP:journals/ijon/LuoJZCLDL22,DBLP:conf/mm/MaXSYZJ22}.
we set $n_codes=1024$ following DiscreteCodebook~\cite{liu-etal-2022-cross}.
We set $α=0.02$ and $β=0.01$. To evaluate the retrieval performance of our proposed model, we use recall at Rank K (R@K, higher is better), median rank (MdR, lower is better), and mean rank (MnR, lower is better) as retrieval metrics, which are widely used in previous retrieval works~\cite{DBLP:conf/icml/RadfordKHRGASAM21,DBLP:journals/ijon/LuoJZCLDL22,DBLP:conf/mm/MaXSYZJ22}.

\subsection{Ablation Studies}

\textbf{Evaluating the calculation of similarity between video and frame representations and cluster concepts in \ours}.
In \ours, we use cosine similarity to calculate $sim^f$ and $sim^$.
Another way of calculating $sim^f$ and $sim^$ might be using multi-label classification.
To compare the effect of multi-label classification and cosine similarity, we conduct experiments using two multi-layer perceptrons (MLPs) with two layers and the $ReLU$ activation to predict the similarity between video and frame representations and cluster concepts.
Two MLPs are also trainable.
Quantitative results are shown in Table~\ref{tab: mls}.
Our quantitative results, shown in Table~\ref{tab: mls}, indicate that the use of MLPs decreases R@1 on text-to-video and video-to-text retrieval.
This suggests that cosine similarity is more suitable for VTR.

\textbf{Evaluating the importance of supervised alignment in \ours}.
In \ours, the aligned sentence representation $$ is obtained from the text as in Eq.~\eqref{eq:sentencecodebook}.
This process aligns the sentence representation based on the instruction of the text.
By doing so, the aligned sentence representation $$ can serve as the supervision (an anchor) for aligning video and frame features, providing a reference point for the alignment of different modalities.
To investigate the importance of placing an anchor $$ for better alignment, we compare it to obtaining aligned sentence representation through the similarity between concept clusters $C$ and sentence feature $r^$.
This alternative approach allows us to evaluate the effectiveness of using an anchor for alignment and to understand how it improves the performance of the model.
To investigate the alternative approach of obtaining aligned sentence representation without an anchor, we calculate the sentence aligned space similarity $sim^ ∈ℝ^1×n_c$ by calculating the cosine similarity between sentence representations and concepts as $sim^_j = cos(, C_j)$, where $sim^_j$ is the $j$-th element of $sim^$, $C_j$ is the $j$-th row of $C$, and $cos$ is the cosine similarity.
The aligned sentence representation $r^$ without the instruction of text is obtained by matrix multiplication as follows:
\begin{align}
\mathbf{r}^{\text} = sim^{\text} C / \|sim^{\text}\|_1 \label{eq: similarity sentence codebook},
\end{align}
where $sim^$ is the similarity between sentence representations and concepts.
The results of this comparison can be found in Table~\ref{tab: wot gold}. The experimental results show that with the ``anchor'', \ours\  can better align different modalities as R@1, R@5, and R@10 on text-to-video retrieval and R@1 on video-to-text retrieval have greatly improved, indicating that the supervised (anchor-based) alignment is crucial for better performance of the model.

\textbf{Effect of alignment and aligned similarity losses and hyperparameter sensitivity}.
To further demonstrate the effectiveness of the two proposed losses designed for aligning different modalities in the shared aligned space, we conduct experiments to compare the performance of these losses.
The quantitative results of these experiments are shown in Table~\ref{tab: two losses}.
The results indicate that adding both losses simultaneously achieves the best performance on the MSR-VTT dataset.
When using only one loss, the performance on text-to-video retrieval is comparable to the method without using both losses on text-to-video retrieval, but outperforms the method without the two losses on video-to-text retrieval.
Specifically, when using two losses, R@1 on text-to-video retrieval and video-to-text retrieval is improved by 1.1 and 1.5, respectively.
Additionally, all the other metrics, such as R@5 and R@10, are also improved, demonstrating the power of the two proposed losses in aligning different modalities in the shared aligned space.
To gain a better understanding of the sensitivity of \ours with respect to the two hyperparameters, $α$ and $β$, we conduct a series of experiments with different settings of $α$ and $β$ as shown in Table~\ref{tab: two losses}.
The results of these experiments demonstrate that, even with varying settings of $α$ and $β$, the video-text retrieval performance remains consistent, indicating that the model is robust and not highly sensitive to these hyperparameters.
This suggests that \ours is able to achieve good performance across a wide range of settings for these hyperparameters, making it easy to adjust and optimize for specific use cases.
Additionally, this also suggests that \ours is not overly dependent on precise values of these hyperparameters, and is instead able to leverage the more important underlying features and patterns in the data.

\subsection{Aligning examples}

To show the effectiveness of \ours, we illustrate some examples of video-to-text and text-to-video retrieval examples in Figures~\ref{fig: V2T} and \ref{fig: T2V}.
We notice that \ours\ is able to align some important concepts between video and text for precise retrieval.
For example, in the bottom-left video-to-text result (Figure~\ref{fig: V2T}), the biggest difference between the top 5 retrieved texts is ``football''.
By precisely capturing ``football'' in the video, \ours\ is able to give higher logits to the sentences that contain ``football''.
Additionally, in the last (bottom-right) text to video result (Figure~\ref{fig: T2V}), we notice that, by understanding ``man'' and ``discuss'', \ours\ is able to distinguish the top 3 retrieved videos and select the one in which a man appears.
This empirically shows that \ours\ performs well in visual and textual content understanding, benefiting from multi-space and multi-grained similarity.

\end{document}


# Safe and Efficient Navigation in Extreme Environments using
Semantic Belief Graphs

Muhammad Fadhil Ginting1, Sung-Kyun Kim2, Oriana Peltzer1, Joshua Ott1,
Sunggoo Jung2,
Mykel J. Kochenderfer1, and Ali-akbar Agha-mohammadi2 1Department of
Aeronautics & Astronautics, Stanford University, Stanford, CA, USA {ginting,
peltzer, joshuaott<EMAIL_ADDRESS>Jet Propulsion Laboratory,
California Institute of Technology, Pasadena, CA, USA {sung.kim, sunggoo.jung,
<EMAIL_ADDRESS>
###### Abstract

To achieve autonomy in unknown and unstructured environments, we propose a
method for semantic-based planning under perceptual uncertainty. This
capability is crucial for safe and efficient robot navigation in environment
with mobility-stressing elements that require terrain-specific locomotion
policies. We propose the Semantic Belief Graph (SBG), a geometric- and
semantic-based representation of a robot’s probabilistic roadmap in the
environment. The SBG nodes comprise of the robot geometric state and the
semantic-knowledge of the terrains in the environment. The SBG edges represent
local semantic-based controllers that drive the robot between the nodes or
invoke an information gathering action to reduce semantic belief uncertainty.
We formulate a semantic-based planning problem on SBG that produces a policy
for the robot to safely navigate to the target location with minimal traversal
time. We analyze our method in simulation and present real-world results with
a legged robotic platform navigating multi-level outdoor environments.

##  I Introduction

Consider a robot tasked to explore complex and unknown environments
autonomously. The environment can contain various mobility-stressing elements
such as rubble, stairs, slippery surfaces, and narrow passages (Fig. 1). To
navigate safely through these elements, the robot needs to identify the high-
level semantic information of the terrain, and adapt its motion planning
policy accordingly. However, making decisions based on semantics can be risky
because of the observation noise and uncertainty of semantic recognition. In
particular, in safety-critical systems, robot navigation using incorrect
semantic classification can lead to catastrophic outcomes. This work
investigates how to use semantic information robustly for planning in real-
world operation.

Figure 1: Boston Dynamics Spot quadrupeds endowed with NASA JPL’s NeBula
autonomy solution [1] explores challenging real-world environment by
traversing various terrains including: i) slippery passages, ii) stairs, iii)
rubble, and iv) narrow passages. Each domain requires a specific controller to
safely navigate the environment.

Semantic-based planning under uncertainty has three major challenges. The
first challenge is handling the uncertainty and misclassification from the
semantic detection. The second challenge is in building a semantic
representation that can be used for decision making and that is scalable to
model complex and large-scale environments. The third challenge is in folding
the semantic information into the robot planning and control framework that
typically relies on geometric information.

To address these challenges, we develop a method to model semantic information
for robot navigation and compute a semantic-based planning policy. We
introduce the Semantic Belief Graph (SBG) to jointly model geometric and
semantic information on the robot’s probabilistic roadmap (PRM) [2]. The nodes
in the SBG capture the uncertainty of semantic information. By capturing
semantic uncertainty, we can model a semantic-based local controller as the
SBG edges that enable the robot to choose a terrain-specific controller based
on the semantic-type of the terrain. Moreover, we include information
gathering actions in the SBG edges to model robot actions that can reduce
semantic information uncertainty. Additionally, we discuss how to formulate
the graph transition probabilities and semantic-dependent cost function. We
show policy computation in SBG is tractable for real-world navigation
problems.

Our technical contributions are as follows:

  1. 1.

We propose the Semantic Belief Graph (SBG), a geo-semantic-based
representation of a robot’s probabilistic roadmap in the environment.

  2. 2.

By representing the semantic information in the SBG, we can predict and
control the semantic uncertainty in planning rather than purely reacting to
the semantic detection.

  3. 3.

We propose a new motion planning architecture that incorporates semantic
information. By using high-level semantic information, this approach can
perform better in navigating environments that require switching between
terrain-specific controllers.

  4. 4.

We tested the proposed method on representative simulations and in the field
with a physical robot.

##  II Related Work

Semantic Representation. Several different approaches have been proposed for
representing the high-level semantic information used for planning and
navigation [3]. Some earlier works introduce multi-hierarchical [4] and
layered spatial representations [5]. Nuechter and Hertzberg present a semantic
3D mapping method built with onboard robotic sensors [6]. Nieto-Granda et al.
build semantic mapping by classifying regions of space [7]. There are also
several works in semantic-based SLAM to estimate 3D geometry of a scene with
semantic labels such as Kimera [8], SegMap [9], Semantic Fusion [10], and
Voxblox++ [11]. In our work, we consider a graph representation to capture the
semantic information and its uncertainty in the graph and associate the
information directly with the robot’s geometric roadmap. The sparsity of the
graph reduces the computational and memory requirements while capturing
relevant information for semantic-based planning.

Semantic-based planning for robot navigation. Semantic-based navigation
considers various planning problems and methods. Hahnheide et al. proposes
task planning under uncertainty by classifying semantics into three knowledge
layers for object search, mapping, and room categorization [12]. Kostavelis et
al. introduces a hierarchical navigation graph by building semantic maps that
consist of metric, topometric, sparse topological map, and augmented
navigation graphs [13]. Some works use learning-based methods by including
semantic information in deep reinforcement learning models [14] and imitation
learning [15]. In our work, in addition to using semantic knowledge for robot
path planning, we also consider the problem of changing robot locomotion
controllers based on semantics. Moreover, we also include semantic uncertainty
prediction into robot actions by modeling information gathering behavior.

Semantic-based controller switching. Our work is related to choosing suitable
controller profiles based on the semantic type of the traversed terrains.
Switching between controllers based on semantics is beneficial for efficient
and safe navigation. One example when controller switching is critical is
stair climbing because the robot needs to reliably identify stairs and perform
different locomotion [16, 17]. In legged robot navigation, switching between
gait controllers is used to safely walk on slippery surfaces [18] and maximize
multiple objectives [19]. In this work, we develop a general framework that
captures the semantic uncertainty of terrain detection and reasons over which
controller should be used.

##  III Problem Formulation

We first formulate the problem of semantic-based planning under uncertainty.

Geo-semantic state. We define a geo-semantic state that consists of a robot
geometric state and a terrain semantic state. A robot geometric state
$x_{k}\in\mathcal{X}$ is the geometric description of a robot state in the
environment. A semantic state $l_{k}\in\mathcal{L}$ is a type of terrain.
description in which the robot resides over. For example, in robot navigation,
useful semantic classes include stairs, flat ground, doorways, slippery
surfaces, and rubble. The geo-semantic state is defined as a tuple of the
robot and semantic state $(x_{k},l_{k})$

Semantic-based robot controller. Let $u_{k}\in\mathcal{U}$ denote the
semantic-based robot control. It contains controller parameters to enable the
robot to traverse a specific type of terrain safely and efficiently. The
process model $(x_{k+1},l_{k+1})=f(x_{k},l_{k},u_{k},w_{k})$ describes how the
geo-semantic state evolves as a function of the robot control and process
noise $w_{k}$.

Observation model. In a partially observable system, the true value of the
geo-semantic state is unknown and can only be inferred by the observation
variable $z_{k}\in\mathcal{Z}$. The observation model
$z_{k}=h(x_{k},l_{k},v_{k})$ encodes the relation between $(x_{k},l_{k})$ and
$z_{k}$, where $v_{k}$ is the observation noise.

Belief. As the system operates in a partially observable setting, we use
information state or belief $b_{k}\in\mathcal{B}$ as the data for decision
making in time step $k$. We define $b_{k}=p(x_{k},l_{k}\mid
z_{0:k},u_{0:k-1})$ as a conditional probability distribution over all
possible states given the history of observations and actions. Beliefs are
estimated with the belief evolution model:
$b_{k+1}=\tau(b_{k},u^{l}_{k},z_{k+1})$.

Policy and cost-to-go. The policy $\pi\in\Pi$ returns the next semantic-based
robot control $u_{k}$ given the belief $b_{k}$. To determine an optimal policy
$\pi^{*}$, we define a cost function $c(b,u)$ as a one-step cost of taking
action $u$ in $b$. A cost function can encode different metrics to be
minimized, for example, time to traverse a specific terrain using a specific
controller, control energy consumption, or computational resources. In this
formulation, the cost function calculates the traversal time. Taking an action
that risks the robot’s safety, such as robot falling down stairs, will incur a
high cost.

Semantic-based planning problem. We formulate the problem of semantic-based
planning as follows—given the current robot configuration $x_{S}$ and semantic
state $l_{S}$ and the goal configuration $x_{G}$, find an optimal policy
$\pi^{*}$ that moves the robot from $x_{S}$ to $x_{G}$ with minimal expected
time of traverse by selecting the best path and semantic-based controllers:

$\displaystyle\pi^{*}=\operatorname*{arg\,min}_{\pi\in\Pi}\mathbb{E}$
$\displaystyle\bigg{[}\sum_{k=0}^{T}c(b_{k},u_{k})\bigg{]}$ (1) s.t.
$\displaystyle b_{k+1}=\tau(b_{k},u_{k},z_{k+1})$ $\displaystyle
z_{k}=h(x_{k},l_{k},v_{k}),$ $\displaystyle
x_{0}=x_{S},l_{0}=l_{S},x_{T}=x_{G},$ $\displaystyle\forall k$
$\displaystyle\in\\{0,\ldots,T\\}.$

##  IV Semantic Belief Graph

In this section, we discuss the Semantic Belief Graph (SBG), a geo-semantic
information roadmap in the belief space. The SBG is defined as a tuple of
nodes and edges $(\mathcal{V},\mathcal{M})$. We first introduce the
formulation of SBG nodes $\mathcal{V}$ and edges $\mathcal{M}$. Then we
discuss how to model transition probabilities and graph costs. Finally, we
show how to find the graph policy and plan with the SBG.

###  IV-A SBG nodes

A node in SBG is a small region of belief $B^{i}$ around a sampled belief
$b^{i}$. In the SBG graph, we parameterized the geo-semantic belief into two
independent representations: a Gaussian geometric belief and a categorical
semantic belief.

Gaussian geometric belief. We assume the noise in the robot geometric belief
$x_{k}$ is a Gaussian. We denote the geometric random estimation vector by
$x^{+}$, whose distribution is $p(x_{k}^{+})=p(x_{k}\mid z_{0:k},u_{0:k-1})$.
The mean and covariance of $x^{+}$ is denoted by
$\hat{x}^{+}=\mathbb{E}[x^{+}]$ and
$P=\mathbb{E}[(x^{+}-\hat{x}^{+})(x^{+}-\hat{x}^{+})^{\intercal}]$
respectively. In SBG nodes, the Gaussian geometric belief is characterized by
the pair $(\hat{x}^{+},P)$.

Categorical semantic belief. The semantic random estimation vector $l^{+}$
follows a categorical distribution, whose distribution is
$p(l_{k}^{+})=p(l_{k}\mid z_{0:k},u_{0:k-1})$. For a finite number of the
semantic type $d_{l}$, $l^{+}$ can be represented as $(d_{l}+1)$-dimensional
vector denoted as $\hat{l}^{+}=[l^{1},l^{2},\ldots,l^{d_{l}},l^{unknown}]$
such that $l^{n}\geq 0$ $\forall n$ and $\sum_{n=1}^{d_{l}+1}l^{n}=1$. The
$unknown$ class is used when the semantic variable can not be classified to
any of the defined semantic classes.

Constructing SBG nodes. To construct SBG nodes $B$, we first sample PRM nodes
denoted by $\\{v^{j}\\}_{j=1}^{N}$ from the obstacle-free space [20]. We then
associate the nodes with the mean and covariance of the geometric belief. The
geometric covariance can be set according to the mission specification, for
example, setting a small covariance to align the robot to stairs with a small
tolerance. Then we associate the semantic belief by initializing the semantic
belief distribution with $unknown$ labels or with prior knowledge of the
environment if any.

###  IV-B SBG edges

We design the SBG edge as a local semantic-based controller. There are two
types of semantic-based controllers: i) navigation controller and ii)
information gathering controller. A semantic-based navigation controller,
denoted by $\mu_{n}^{ij}$ for an edge connecting nodes $B^{i}$ and $B^{j}$,
drives the robot from $B^{i}$ to $B^{j}$, using a low-level motion controller
designed to traverse terrain with a semantic type $l^{n}$. A semantic-based
information gathering controller, denoted by $\mu_{IG}^{i}$ for a self-loop
edge on $B^{i}$, performs an information gathering action to reduce the
uncertainty of the semantic classification on the current node $B^{i}$.

Figure 2: Visual representation of Semantic Belief Graph. Graph nodes in the
geo-semantic belief is denoted by $B^{i}$. The pie chart represents the
categorical belief distribution of the semantic type around the location of
the node. The graph edges represent terrain specific local controller
$\mu^{ij}_{l}$. The circular edge represents information gathering action
$\mu^{i}_{IG}$ to reduce semantic belief uncertainty.

###  IV-C Belief Transition Probabilities

Taking a local semantic-based controller results in updates in beliefs: _i)_
the geometric belief update due to the robot configuration changes by a
navigation controller $\mu_{n}^{ij}$, _ii)_ the semantic belief update due to
additional observation by an information gathering controller $\mu_{IG}^{i}$.
Such belief updates, i.e., belief transition probabilities, should be modeled
since the optimal policy depends on the geometric and semantic beliefs. In
this work, we assume the transition between geometric belief nodes using
controller $\mu^{ij}$ is deterministic, though it is possible to extend this
framework to account for failure probabilities [21].

To model the semantic belief transition probabilities, we sample a finite
number of semantic belief vectors $\hat{l}^{+}$. We assume the updated
semantic belief after information gathering actions will only reduce the
uncertainty of the belief and reveal the most probable semantic type. Let
$B_{k+1,j}^{i}$ denote a $j$-th sample of node $B^{i}$ at time-step $k+1$
after taking controller $\mu_{IG}^{i}$. Then the transition probability of the
action is defined as $P(B_{k+1,j}^{i}|B^{i}_{k},\mu^{i}_{IG})$. The transition
probability can be assumed uniform or learned from observation data.

###  IV-D Graph Cost

To find a policy on an SBG graph, we need to define the cost associated with
the graph edges and nodes. Let $C^{g}(B^{i},\mu)$ denote the cost of using
controller $\mu$ at node $B^{i}$. The graph cost $C^{g}(B^{i},\mu)$ sums all
one-step costs along the edge until it reaches the target node $B^{j}$ or
updated the semantic belief in current node $B^{i}$.

In particular, a semantic-based navigation controller $\mu^{ij}_{n}$ has a
different cost depending on the specified mission objective and type of
terrain traversed by the controller. In this work, we use traversal time to
determine the cost. Using a terrain-specific controller on the wrong type of
terrain incurs a higher cost as the robot locomotion will not be efficient on
the wrong terrain. As the robot does not know the true semantic type of the
terrain, $C^{g}(B^{i},\mu^{ij}_{n})$ is estimated by taking the expected value
of taking controller $\mu^{ij}_{n}$ over the semantic distribution:

$\displaystyle
C^{g}(B^{i},\mu^{ij}_{n})=\sum_{m=1}^{n_{d}+1}p(l^{m})C^{g}((x^{i},l^{m}),\mu^{ij}_{n}),$
(2)

###  IV-E Graph policy on SBG

We define a graph policy $\pi^{g}:\mathcal{V}\rightarrow\mathcal{M}$ as a
function that returns an edge for any given node in the graph. The edge is the
local controller $\mu$ that then controls the robot. Given a target node
$B^{goal}$, the graph policy $\pi^{g}$ can be seen as a planning tree that
drives the robot to $B_{goal}$ from any node in the SBG.

Graph cost to go. To choose the best graph policy, we define the optimal
graph-cost-to-go $J^{g}$ from every node. The cost-to-go from a given node
$B^{i}$ is equal to the cost of the next local controller $\mu$ and the
expected cost-to-go from the next node. The local controller is picked among
available edges $\mathcal{M}(i)$ connected to $B^{i}$. The dynamic programming
(DP) equations for this graph are

$\displaystyle J^{g}(B^{i})=$
$\displaystyle\min_{\mu\in\mathcal{M}(i)}C^{g}(B^{i},\mu)+J^{g}(B^{j})$ (3)
$\displaystyle\pi^{g}(B^{i})=$
$\displaystyle\operatorname*{arg\,min}_{\mu\in\mathcal{M}(i)}J^{g}(B^{i}).$
(4)

As there is a finite number of nodes in the graph, the DP equation can be
solved offline. Standard techniques can be used to solve the DP such as with
value/policy iteration methods.

Figure 3:  An example of a simple planning problem on SBG to move the robot
from the start node to the goal node. The top part of the graph shows possible
path to the goal, but initially the confidence of the stair on node
$B^{1}_{k}$ at time step k is low. Meanwhile the bottom part of the graph
shows a path through a rubble with a longer traversal time than moving through
the stair. The red box shows two most probable realization of the node
$B^{1}_{k+1}$ after taking information gathering action $\mu_{IG}$. The dashed
arrows through the top part of the graph shows the most likely path by taking
the best local controller policy on every node.

##  V Experimental Results

We first illustrate SBG construction and show planning results in a small
domain. Then, we present simulation results in a larger environment. Finally,
we report the results in a real-world scenario with JPL’s Boston Dynamic
legged robot.

###  V-A Constructing and planning with SBG in a small environment

In this experiment, we consider a planning problem of moving a robot to a goal
in a two-level environment represented as a roadmap.

System description. The geo-semantic state is composed of the 3D geometric
state and semantic state with four possible labels
$l=\\{\text{flat\\_ground},\text{stair},\text{rubble},\text{unknown}\\}$. The
action $u$ is generated from four possible local controllers: $\mu_{stair}$,
$\mu_{flat}$, $\mu_{rubble}$, and $\mu_{IG}$. The first three are controllers
to traverse specific types of terrain and $\mu_{IG}$ is the controller to
gather semantic information around the robot. In this experiment, the robot is
assumed to have accurate geometric localization. The robot observes the
semantic type as a categorical distribution of possible labels and the
accuracy of the semantic classification increases as the robot gets closer to
the observed semantic terrain.

SBG. The constructed SBG and computed policy is shown in Fig. 3. Every PRM
node is associated with a geo-semantic belief state. The closed-loop graph
policy is then computed with value iteration. We compute the optimal policy on
every node in the graph. In the planning phase, two new nodes are sampled to
account for the most possible outcome of the semantic label after the
information gathering action.

Benefits of planning with SBG. There are two key benefits by planning with
SBG. First, by reasoning about the uncertain information regarding possible
stairs in the environment, the robot can be directed to investigate a
potential stair that can lead to a shorter path to the goal. Second, by
considering the semantics of the terrain, the robot can plan to switch to
different controllers that are safer and more efficient for the specific
terrain type in the environment.

###  V-B Simulation Results

Figure 4: Course map of the simulation based on real-world urban environment
depicted by the photos on the bottom. Red dots on the map marked the location
of stairs and rubble. The most likely paths computed by all the methods are
overlaid on the map. The circular edges represent information gathering
action.

To show that our framework is applicable to complex real-world robot
navigation scenarios, we evaluate the planning performance in a simulated
urban environment of the SubT Challenge Final event. The urban part of the
course consists of 27 segments spanning around 300 m. The terrains and
environmental model are based on the DARPA Callout document, and we use the
same geo-semantic and controller model as the previous experiment.

We compare our method to two naive policies:

  1. 1.

Conservative policy: this policy only directs the robot to traverse terrains
with $>95\%$ semantic confidence $l^{i}$,

  2. 2.

Optimistic policy: this policy always assumes the most likely semantic type.

Fig. 4 shows the course map of the simulation and the paths computed by all
methods. Simulation statistics are provided in Table I and Fig. 5.

TABLE I: Simulation results of the experiment in Section V.B. The traversal time (in time steps) is the average time across 20 runs taken by the robot from the starting location to the goal by following a planning policy. The percentage of correct terrain-specific controller is computed for all edges in the computed graph policy, including edges not on the most-likely path to the target.  Planning policy | Percentage of correct controller | Traversal time
---|---|---
Our Approach | 93.9% | 18
Conservative | 100% | 22
Optimistic | 78.8% | 23
Figure 5:  The time breakdown of the traversal time in the simulation.

Traversal time. We first compare the efficiency of the traversal time. The
average traversal time of our method is shorter than other policies. The
conservative policy takes longer to traverse as it often performs information
gathering actions to correctly identify the terrain type. While the optimistic
policy takes longer because it uses the wrong controller for the suitable type
of terrain (e.g. it uses the rubble controller to walk slowly on flat
terrain). Our planning method on SBG balanced the two policies by accounting
for the expected cost to perform information gathering or choosing an
appropriate controller based on the semantic belief.

Efficient controller switching. We also compare the accuracy of the semantic-
based controller to the true semantics of the terrain. While the controller
accuracy of our planner is lower than the conservative policy, it balances the
information gathering actions and takes a more conservative policy to minimize
the overall traversal time. For example, in an area classified as rubble with
low confidence, it saves time by choosing a more conservative policy that
slows the robot movement rather than performing information gathering actions
in places that takes a longer time to identify the terrain type with greater
confidence.

Figure 6:  Top: Field experiment setup in a two-level outdoor environment by
using the NASA JPL Spot robot [22] and Spot’s stair climbing behavior. Bottom:
Visual representation of the policy computed with the SBG on Information
Roadmaps [20]. The red arrows show the most likely path from the starting
location (green square) to the goal (yellow star). The circular arrow
represents information gathering actions. Initially, the only path in the
graph between the starting and goal location is through the ramp. By
considering the path through nodes labeled with stairs, the robot chooses a
shorter path by climbing the stairs.

###  V-C Field Test Results

We tested our approach on the Boston Dynamics Spot legged robot in a two-level
outdoor area connected by stairs and ramp as shown in Fig. 6. The robot
geometric localization is provided by onboard LIDAR-based SLAM solution [23]
and the stairs are detected visually by the robot’s camera and using point
cloud segmentation around the robot. The robot has two different semantic-
based controllers to walk through flat-terrain and stairs. The robot is
assigned to move to a specific goal location on a different level. The prior
map is built by allowing the robot to explore the environment autonomously
[24].

The computed policy to the goal on the SBG directs the robot to visit the
closest stair to the goal location. Before attempting the stair climbing, the
robot performed information gathering actions. The information gathering
action directs the robot to pitch up to map the stair area and validate the
location of the stair with the local pointcloud. Using probabilistic semantic
information helps the robot to find a shorter path because without it the
robot will take a longer route through the ramp to reach the goal.

##  VI Conclusions

We presented our method for semantic-based planning under uncertainty with SBG
(Semantic Belief Graph). By capturing geo-semantic belief uncertainty, our
method can account for it in planning and actively reduce the semantic
uncertainty. The computed policy also selects the best terrain-based
controller on every SBG edge. We demonstrate the benefit of our approach for
time-efficient and safe motion planning in environments with a variety of
challenging terrain. We believe the proposed method is an important step to
integrate semantic knowledge for safe real-world robot navigation in such
complex environments.

## Acknowledgment

The work is partially supported by the Jet Propulsion Laboratory, California
Institute of Technology, under a contract with the National Aeronautics and
Space Administration (80NM0018D0004), and Defense Advanced Research Projects
Agency (DARPA), and funded through JPL’s Strategic University Research
Partnerships (SURP) program.

## References

  * [1] A. Agha, K. Otsu, B. Morrell _et al._ , “NeBula: TEAM CoSTAR’s Robotic Autonomy Solution that Won Phase II of DARPA Subterranean Challenge,” _Field Robotics_ , vol. 2, pp. 1432–1506, 2022.
  * [2] L. Kavraki, P. Svestka, J.-C. Latombe, and M. Overmars, “Probabilistic roadmaps for path planning in high-dimensional configuration spaces,” _IEEE Transactions on Robotics and Automation_ , vol. 12, no. 4, pp. 566–580, 1996.
  * [3] J. Crespo, J. C. Castillo, O. M. Mozos, and R. Barber, “Semantic information for robot navigation: A survey,” _Applied Sciences_ , vol. 10, no. 2, pp. 497–524, 2020.
  * [4] C. Galindo, A. Saffiotti, S. Coradeschi, P. Buschka, J.-A. Fernandez-Madrigal, and J. González, “Multi-hierarchical semantic maps for mobile robotics,” in _IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)_ , Edmonton, Canada, 2005.
  * [5] A. Pronobis and P. Jensfelt, “Large-scale semantic mapping and reasoning with heterogeneous modalities,” in _IEEE International Conference on Robotics and Automation (ICRA)_ , St. Paul, MN, 2012.
  * [6] A. Nüchter and J. Hertzberg, “Towards semantic maps for mobile robots,” _Robotics and Autonomous Systems_ , vol. 56, no. 11, pp. 915–926, 2008.
  * [7] C. Nieto-Granda, J. G. Rogers, A. J. Trevor, and H. I. Christensen, “Semantic map partitioning in indoor environments using regional analysis,” in _IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)_ , Taipei, Taiwan, 2010, pp. 1451–1456.
  * [8] A. Rosinol, A. Violette, M. Abate, N. Hughes, Y. Chang, J. Shi, A. Gupta, and L. Carlone, “Kimera: From SLAM to spatial perception with 3d dynamic scene graphs,” _The International Journal of Robotics Research_ , vol. 40, no. 12-14, pp. 1510–1546, 2021.
  * [9] R. Dube, A. Cramariuc, D. Dugas, H. Sommer, M. Dymczyk, J. Nieto, R. Siegwart, and C. Cadena, “Segmap: Segment-based mapping and localization using data-driven descriptors,” _The International Journal of Robotics Research_ , vol. 39, no. 2-3, pp. 339–355, 2020.
  * [10] J. McCormac, A. Handa, A. Davison, and S. Leutenegger, “Semanticfusion: Dense 3d semantic mapping with convolutional neural networks,” in _IEEE International Conference on Robotics and Automation (ICRA)_ , Singapore, 2017.
  * [11] M. Grinvald, F. Furrer, T. Novkovic, J. J. Chung, C. Cadena, R. Siegwart, and J. Nieto, “Volumetric instance-aware semantic mapping and 3d object discovery,” _IEEE Robotics and Automation Letters_ , vol. 4, no. 3, pp. 3037–3044, 2019.
  * [12] M. Hanheide, M. Göbelbecker, G. S. Horn, A. Pronobis, K. Sjöö, A. Aydemir, P. Jensfelt, C. Gretton, R. Dearden, M. Janicek _et al._ , “Robot task planning and explanation in open and uncertain worlds,” _Artificial Intelligence_ , vol. 247, pp. 119–150, 2017.
  * [13] I. Kostavelis, K. Charalampous, A. Gasteratos, and J. K. Tsotsos, “Robot navigation via spatial and temporal coherent semantic maps,” _Engineering Applications of Artificial Intelligence_ , vol. 48, pp. 173–187, 2016.
  * [14] W. Yang, X. Wang, A. Farhadi, A. Gupta, and R. Mottaghi, “Visual semantic navigation using scene priors,” in _International Conference on Learning Representations (ICLR)_ , New Orleans, Louisiana, 2019.
  * [15] A. Mousavian, A. Toshev, M. Fišer, J. Košecká, A. Wahid, and J. Davidson, “Visual representations for semantic target driven navigation,” in _IEEE International Conference on Robotics and Automation (ICRA)_ , 2019.
  * [16] D. M. Helmick, S. I. Roumeliotis, M. C. McHenry, and L. Matthies, “Multi-sensor, high speed autonomous stair climbing,” in _IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)_ , Lausanne, Switzerland, 2002.
  * [17] E. Mihankhah, A. Kalantari, E. Aboosaeedan, H. D. Taghirad, S. Ali, and A. Moosavian, “Autonomous staircase detection and stair climbing for a tracked mobile robot using fuzzy controller,” in _IEEE International Conference on Robotics and Biomimetics_ , Guangxi, China, 2009.
  * [18] S. Dey, D. Fan, R. Schmid, A. Dixit, K. Otsu, T. Touma, A. F. Schilling, and A.-A. Agha-Mohammadi, “PrePARE: Predictive proprioception for agile failure event detection in robotic exploration of extreme terrains,” in _IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)_ , 2022, pp. 4338–4343.
  * [19] M. Brandao, M. Fallon, and I. Havoutis, “Multi-controller multi-objective locomotion planning for legged robots,” in _IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)_ , Macau, China, 2019, pp. 4714–4721.
  * [20] S. Kim, A. Bouman, G. Salhotra, D. Fan, K. Otsu, J. Burdick, and A. Agha-mohammadi, “PLGRIM: Hierarchical value learning for large-scale exploration in unknown environments,” in _International Conference on Automated Planning and Scheduling (ICAPS)_ , Guangzhou, China, 2021.
  * [21] A. Agha-Mohammadi, S. Chakravorty, and N. M. Amato, “Firm: Sampling-based feedback motion-planning under motion uncertainty and imperfect measurements,” _International Journal of Robotics Research_ , vol. 33, no. 2, pp. 268–304, 2014.
  * [22] A. Bouman$*$, M. Ginting$*$, N. Alatur$*$, M. Palieri, D. Fan, T. Touma, T. Pailevanian, S. Kim, K. Otsu, J. Burdick, and A. Agha-mohammadi, “Autonomous Spot:long-range autonomous exploration of extreme environments with legged locomotion,” in _IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)_ , 2020.
  * [23] Y. Chang, K. Ebadi, C. E. Denniston, M. F. Ginting, A. Rosinol, A. Reinke, M. Palieri, J. Shi, A. Chatterjee, B. Morrell _et al._ , “Lamp 2.0: A robust multi-robot slam system for operation in challenging large-scale underground environments,” _IEEE Robotics and Automation Letters_ , vol. 7, no. 4, pp. 9175–9182, 2022.
  * [24] O. Peltzer, A. Bouman, S.-K. Kim, R. Senanayake, J. Ott, H. Delecki, M. Sobue, M. J. Kochenderfer, M. Schwager, J. Burdick _et al._ , “Fig-op: Exploring large-scale unknown environments on a fixed time budget,” in _IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)_ , 2022.