heightadjust=object [table]style=plaintop figureboxfigure[][]
tableboxtable[][]

#  Adversarial Retriever-Ranker for Dense Text Retrieval

Hang Zhang1, Yeyun Gong2, Yelong Shen3, Jiancheng Lv1, Nan Duan2, Weizhu Chen3
1College of Computer Science, Sichuan University,
2Microsoft Research Asia, 3Microsoft Azure AI
hangzhang_scu<EMAIL_ADDRESS>
<EMAIL_ADDRESS><EMAIL_ADDRESS>Work is done during
internship at Microsoft Research Asia.Corresponding author

###### Abstract

Current dense text retrieval models face two typical challenges. First, they
adopt a siamese dual-encoder architecture to encode queries and documents
independently for fast indexing and searching, while neglecting the finer-
grained term-wise interactions. This results in a sub-optimal recall
performance. Second, their model training highly relies on a negative sampling
technique to build up the negative documents in their contrastive losses. To
address these challenges, we present Adversarial Retriever-Ranker (AR2), which
consists of a dual-encoder retriever plus a cross-encoder ranker. The two
models are jointly optimized according to a minimax adversarial objective: the
retriever learns to retrieve negative documents to cheat the ranker, while the
ranker learns to rank a collection of candidates including both the ground-
truth and the retrieved ones, as well as providing progressive direct feedback
to the dual-encoder retriever. Through this adversarial game, the retriever
gradually produces harder negative documents to train a better ranker, whereas
the cross-encoder ranker provides progressive feedback to improve retriever.
We evaluate AR2 on three benchmarks. Experimental results show that AR2
consistently and significantly outperforms existing dense retriever methods
and achieves new state-of-the-art results on all of them. This includes the
improvements on Natural Questions R@5 to $77.9\%$ ($+2.1\%$), TriviaQA R@5 to
$78.2\%$ ($+1.4\%$), and MS-MARCO MRR@10 to $39.5\%$ ($+1.3\%$). Code and
models are available at https://github.com/microsoft/AR2.

##  1 Introduction

Dense text retrieval (Lee et al., 2019; Karpukhin et al., 2020) has achieved
great successes in a wide variety of both research and industrial areas, such
as search engines (Brickley et al., 2019; Shen et al., 2014), recommendation
system (Hu et al., 2020), open-domain question answering (Guo et al., 2018;
Liu et al., 2020), etc. A typical dense retrieval model adopts a dual-encoder
(Huang et al., 2013) architecture to encode queries and documents into low-
dimensional embedding vectors, with the relevance between query and document
being measured by the similarity between embeddings. In real-world dense text
retrieval applications, it pre-computes all the embedding vectors of documents
in the corpus, and leverages the approximate nearest neighbor (ANN) (Johnson
et al., 2019) technique for efficiency. To train a dense retriever,
contrastive loss with negative samples is widely applied in the literature
(Xiong et al., 2021; Karpukhin et al., 2020). During training, the model
utilizes a negative sampling method to obtain negative documents for a given
query-document pair, and then minimizes the contrastive loss which relies on
both the positive document and the sampled negative ones (Shen et al., 2014;
Chen et al., 2017; Radford et al., 2021).

Recent studies on contrastive learning (Xiong et al., 2021; Karpukhin et al.,
2020) show that the iterative “hard-negative” sampling technique can
significantly improve the performance compared with “random-negative” sampling
approach, as it can pick more representative negative samples to learn a more
discriminative retriever. In the work (Qu et al., 2021), it suggests
leveraging cross-encoder model to heuristically filter “hard-negative” samples
to further improve performance and shows the importance of sampling technique
in the contrastive learning.

On the other hand, the model architecture of dual-encoders enables the
encoding of queries and documents independently which is essential for
document indexing and fast retrieval. However, this ignores the modeling of
finer-grained interactions between queries and documents which could be a sub-
optimal solution in terms of retrieval accuracy.

(a) Retriever

(b) Ranker

Figure 1: Illustration of two modules in AR2. (a) Retriever: query and
document are encoded independently by a dual-encoder. (b) Ranker:
concatenated, jointly encoded by a cross-encoder.

Motivated by these phenomena, we propose an Adversarial Retriever-Ranker (AR2)
framework. The intuitive idea of AR2 is inspired by the “retriever-ranker”
architecture in the classical information retrieval systems. AR2 consists of
two modules: a dual-encoder model served as the retrieval module in Figure
1(a) and a cross-encoder model served as the ranker module in Figure 1(b). The
cross-encoder model takes the concatenation of a query and document as input
text, and can generate more accurate relevance scores compared with the dual-
encoder model, since it can fully explore the interactions between the query
and document through a self-attention mechanism using a conventional
transformer model (Vaswani et al., 2017; Guo et al., 2020). Instead of
training “retriever-ranker” modules independently in some IR systems (Manning
et al., 2008; Mitra & Craswell, 2017), AR2 constructs a unified minimax game
for training the retriever and ranker models interactively, as shown in Figure
2.

Figure 2: Illustration of the AR2 training pipeline. $q$, $d$, and
$\mathbb{D}_{q}^{-}$ represent the query, positive document, and retrieved
documents, respectively.

In particular, AR2 adopts a minimax objective from the adversarial game
(Goodfellow et al., 2014) where the retrieval model is optimized to produce
relevant documents to fool the ranker model, whereas the ranker model learns
to distinguish the ground-truth relevant document and retrieved ones by its
opponent retrieval model. Within the adversarial “retriever-ranker” training
framework, the retrieval model receives the smooth training signals from the
ranker model which helps alleviate the harmful effects of “false-negative”
issues. For example, a “false-negative” example which is rated as high-
relevance by the ranker model, will also be granted with high probability by
retrieval model in order to fool the ranker, meanwhile the ranker model with
better generalization capability is more resistant to label noises compared to
the retrieval model.

In the empirical studies of AR2, we further introduce a distillation
regularization approach to help stabilize/improve the training of the
retriever. Intuitively, the retriever would converge to sharp conditional-
probabilities over documents given a query within the adversarial training
framework, i.e., high retrieval probabilities for the top relevant documents
and near-zero retrieval ones for the rest. However, it is not a desirable
property as it might impede exploring different documents during training.
Thus, we incorporate the distillation loss between the retriever and ranker
models as a smooth term for further improvement.

In experiments, we evaluate AR2 on three widely used benchmarks for dense text
retrieval: Natural Questions, Trivia QA and MS-MARCO. Experimental results
show that AR2 achieves state-of-the-art performance on all these datasets.
Meanwhile, we provide a comprehensive ablation study to demonstrate the
advantage of different AR2 components.

##  2 PRELIMINARIES

Dense Text Retrieval:  We mainly consider a contrastive-learning paradigm for
dense text retrieval in this work, where the training set consists of a
collection of text pairs. ${C}=\\{(q_{1},d_{1}),...,(q_{n},d_{n})\\}$. In the
scenario of open-domain question answering, a text pair $(q,d)$ refers to a
question and a corresponding document which contains the answer. A typical
dense retrieval model adopts a dual encoder architecture, where questions and
documents are represented as dense vectors separately and the relevance score
$s_{\theta}(q,d)$ between them is measured by the similarity between their
embeddings:

$s_{\theta}(q,d)=\left\langle E(q;\theta),E(d;\theta))\right\rangle$ (1)

where $E(\cdot;\theta)$ denotes the encoder module parameterized with
$\theta$, and $\left\langle\cdot\right\rangle$ is the similarity function,
e.g., inner-product, Euclidean distance. Based on the embeddings, existing
solutions generally leverage on-the-shelf fast ANN-search (Johnson et al.,
2019) for efficiency.

A conventional contrastive-learning algorithm could be applied for training
the dual encoders (Shen et al., 2014; Chen et al., 2017; Liu et al., 2020).
For example, given a training instance $(q,d)$, we select $n$ negative
irrelevant documents $(d^{-}_{1},...,d^{-}_{n})$ (denoted as
$\mathbb{D}^{-}_{q}$) to optimize the loss function of the negative log
likelihood of the positive document:

$L_{\theta}(q,d,\mathbb{D}^{-}_{q})=-\text{log}\frac{e^{\tau
s_{\theta}(q,d)}}{e^{\tau s_{\theta}(q,d)}+\sum_{i=1}^{n}e^{\tau
s_{\theta}(q,d^{-}_{i})}}$ (2)

where $\tau$ is a hyper-parameter to control the temperature. Previous works
(Shen et al., 2014; Chen et al., 2017; Liu et al., 2020) present an effective
strategy on negative document sampling, called “In-Batch Negatives” where
negative documents are randomly sampled from a collection of documents which
are within the same mini-batch as question-document training pairs.

Recently, some studies e.g., ANCE (Xiong et al., 2021) and Condenser (Gao &
Callan, 2021b), have shown that selecting “hard-negatives” in the training can
significantly improve the retrieval performance in open-domain question
answering. For example, instead of sampling negative document randomly, “hard-
negatives” are iteratively retrieved through previous checkpoints of the dual
encoder model. However, a more recent work RocketQA (Qu et al., 2021)
continues to point out that the retrieved “hard-negatives” could potential be
“false-negatives” in some cases, which might limit the performance.

Generative Adversarial Network: GANs have been widely studied for generating
the realistic-looking images in computation vision (Goodfellow et al., 2014;
Brock et al., 2018). In the past few years, the idea of GANs has been applied
in information retrieval (Wang et al., 2017). For example, IRGAN (Wang et al.,
2017), proposes a minimax retrieval framework which constructs two types of IR
models: a generative retrieval model and a discriminative retrieval model. The
two IR models are optimized through a minimax game: the generative retrieval
model generates relevant documents that look like ground-truth relevant
documents to fool the discriminative retrieval model, whereas the
discriminative retrieval model learns to draw a clear distinction between the
ground-truth relevant documents and the generated ones made by its opponent
generative retrieval model. The minimax objective is formulated as:

$J^{G^{*},D^{*}}=\text{min}_{\theta}\text{max}_{\phi}\text{E}_{d\sim
p_{\text{true}}(\cdot|q)}\left[\text{log}{D_{\phi}(d,q)}\right]+\text{E}_{d^{-}\sim
G_{\theta}(\cdot|q)}\left[\text{log}{\left(1-D_{\phi}(d^{-},q)\right)}\right]$
(3)

where $G_{\theta}(\cdot|q)$ and $D_{\phi}(d^{-},q)$ denote the generative
retrieval model and discriminative retrieval model in IRGAN, respectively. It
is worth noting the original IRGAN model doesn’t work for dense retrieval
tasks as it doesn’t contain the dual-encoder model for document indexing or
fast retrieval.

##  3 Method

In this section, we introduce the proposed adversarial retriever-ranker (AR2)
approach. It consists of two modules: the dual-encoder retriever module
$G_{\theta}$ as in Figure 1(a), and the cross-encoder ranker module $D_{\phi}$
as in Figure 1(b). $G_{\theta}$ and $D_{\phi}$ computes the relevance score
between question and document as follows:

$\displaystyle G_{\theta}(q,d)$
$\displaystyle=E_{\theta}(q)^{T}{E}_{\theta}(d)$ (4) $\displaystyle
D_{\phi}(q,d)$
$\displaystyle=\mathbf{w_{\phi}}^{T}E_{\phi}\left(\left[q,d\right]\right)$

where $E_{\theta}(\cdot)$ and $E_{\phi}(\cdot)$ are language model encoders
which can be initialized with any pre-trained language model,
$\mathbf{w_{\phi}}$ is the linear projector in $D_{\phi}$, and
$\left[q,d\right]$ is the concatenation of question and document.

In AR2, the retriever and ranker modules are optimized jointly through a
contrastive minimax objective:

$J^{G^{*},D^{*}}=\text{min}_{\theta}\text{max}_{\phi}\mathbf{E}_{\mathbb{D}^{-}_{q}\sim
G_{\theta}(q,\cdot)}\left[\text{log}p_{\phi}(d|q;\mathbb{D}_{q})\right]$ (5)

where $\mathbb{D}^{-}_{q}$:$\\{d^{-}_{i}\\}_{i=1}^{n}$ is the set of $n$
negative documents sampled by $G_{\theta}(q,\cdot)$ given $q$, and
$p_{\phi}(d|q;\mathbb{D}_{q})$ denotes the probability of selecting the
ground-truth document $d$ from the document set $\mathbb{D}_{q}$
($\mathbb{D}_{q}=\\{d\\}\cup\mathbb{D}^{-}_{q}$) by the ranker module
$D_{\phi}$;

$p_{\phi}(d|q;\mathbb{D}_{q})=\frac{e^{\tau
D_{\phi}(q,d)}}{\sum_{d^{\prime}\in\mathbb{D}_{q}}e^{\tau
D_{\phi}(q,d^{\prime})}}$ (6)

According to the objective function (Eqn. 5), the dual-encoder retrieval model
$G_{\theta}(q,\cdot)$ would try to sample the high-relevant documents to fool
the ranker model, whereas the ranker model $D_{\phi}(q,\cdot)$ is optimized to
draw distinctions between ground-truth passage and the ones sampled by
$G_{\theta}(q,\cdot)$. We present the illustration of the AR2 framework in
Figure 2. In order to optimize the minimax objective function, we adopt a
conventional iterative-learning mechanism to optimize the retriever and ranker
modules coordinately.

###  3.1 Training the Ranker $D_{\phi}$

Given the fixed retriever $G_{\theta}$, the ranker model $D_{\phi}$ is updated
by maximizing the log likelihood of selecting ground-truth $d$ from set
$\mathbb{D}_{q}$ given a query $q$:

$\displaystyle\phi^{*}$
$\displaystyle=\text{argmax}_{\phi}\text{log}p_{\phi}(d|q;\mathbb{D}_{q})$ (7)

where $\mathbb{D}_{q}$ consists of ground-truth document $d$ and negative
document set $\mathbb{D}^{-}_{q}$. $\mathbb{D}^{-}_{q}$ is sampled by
$G_{\theta}$ according to Eqn. 5. In experiments, we first retrieve top-$100$
negative documents, and then randomly sample $n$ examples from them to obtain
$\mathbb{D}^{-}_{q}$.

###  3.2 Training Retriever $G_{\theta}$

With fixing the ranker $D_{\phi}$, the model parameters $\theta^{*}$ for the
retriever $G_{\theta}$ is optimized by minimizing the expectation of log
likelihood of function. In particular, by isolating $\theta$ from the minimax
function (Eqn. 5), the objective for the retriever can be written as:

$\theta^{*}=\text{argmin}_{\theta}J^{\theta}=\mathbf{E}_{\mathbb{D}^{-}_{q}\sim
G_{\theta}(q,\cdot)}\left[\text{log}p_{\phi}(d|q;\mathbb{D}_{q})\right]$ (8)

However, it is intractable to optimize $\theta$ directly through Eqn. 8, as
the computation of probability $\mathbb{D}^{-}_{q}\sim G_{\theta}(q,\cdot)$
does not follow a close form. Thus, we seek to minimize an alternative upper-
bound of the loss criteria:

$J^{\theta}\leq\hat{J}^{\theta}=\mathbf{E}_{d^{-}\sim
p_{\theta}(\cdot|q;\mathbb{D}^{-}_{q})}\left[\text{log}p_{\phi}(d|q;\\{d,d^{-}\\})\right]$
(9)

The detailed deviation of Eqn. 9 is provided in the Appendix A.1. Therefore,
the gradient of parameter $\theta$ can be computed as the derivative of
$\hat{J}^{\theta}$ with respect to $\theta$:

$\displaystyle\nabla_{\theta}\hat{J}^{\theta}$
$\displaystyle=\mathbf{E}_{d^{-}\sim
p_{\theta}(\cdot|q;\mathbb{D}^{-}_{q})}\nabla_{\theta}\log
p_{\theta}(d^{-}|q;\mathbb{D}^{-}_{q})\left[\log
p_{\phi}(d|q;\\{d,d^{-}\\})\right]$ (10)

Here, the same approach is applied to obtain set $\mathbb{D}^{-}_{q}$ as in
Eqn. 7.

Regularization: we further introduce a distillation regularization term in
$G_{\theta}$’s training, which encourages the retriever model to distill from
the ranker model.

$\displaystyle J_{\mathcal{R}}^{\theta}$
$\displaystyle=H(p_{\phi}(\cdot|q;\mathbb{D}),p_{\theta}(\cdot|q;\mathbb{D}))$
(11)

$H(\cdot)$ is the cross entropy function. $p_{\phi}(\cdot|q;\mathbb{D})$ and
$p_{\theta}(\cdot|q;\mathbb{D})$ denote the conditional probabilities of
document in the whole corpus $\mathbb{D}$ by the ranker and the retriever
model, respectively. In practice, we also limit the sampling space over
documents to a fixed set, i.e.,
$\mathbb{D}_{q}=\\{d\\}\cup\mathbb{D}^{-}_{q}$. Thus the regularization loss
for the retriever model can be rewritten as:

$\displaystyle J_{\mathcal{R}}^{\theta}$
$\displaystyle=H\left(p_{\phi}(\cdot|q;\mathbb{D}_{q}),p_{\theta}(\cdot|q;\mathbb{D}_{q})\right)$
(12)

###  3.3 Index refresh

During each training iteration of retriever and ranker models in AR2, we
refresh the document index to keep the retrieved document set updated. To
build the document index, we take the document encoder from the retrieval
model to compute the embeddings $E(d;\theta)$ for every document $d$ from the
corpus: $d\in C$, and then build the inner-product based ANN search index with
FAISS tool.

In summary, Algorithm 1 shows the full implementation details of the proposed
AR2.

Algorithm 1 Adversarial Retriever-Ranker (AR2)

0: Retriever $G_{\theta}$; Ranker $D_{\phi}$; Document pool $\mathbb{D}$;
Training dataset $C$.

1: Initialize the retriever $G_{\theta}$ and the ranker $D_{\phi}$ with pre-
trained language models.

2: Train the warm-up retriever $G^{0}_{\theta}$ on training dataset $C$.

3: Build ANN index on $\mathbb{D}$

4: Retrieve negative samples on $\mathbb{D}$.

5: Train the warm-up ranker $D^{0}_{\theta}$

6: while AR2 has not converged do

7: for Retriever training step do

8: Sample $n$ documents $\\{d_{i}^{-}\\}_{n}$ from ANN index.

9: Update parameters of the retriever $G_{\theta}$.

10: end for

11: Refresh ANN Index.

12: for Ranker training step do

13: Sample $n$ hard negatives $\\{d_{i}^{-}\\}_{n}$ from ANN index.

14: Update parameters of the ranker $D_{\phi}$.

15: end for

16: end while

##  4 Experiments

###  4.1 Datasets

We conduct experiments on three popular benchmarks: Natural Questions
(Kwiatkowski et al., 2019), Trivia QA (Joshi et al., 2017), and MS-MARCO
Passage Ranking (Nguyen et al., 2016).

Natural Questions (NQ) collects real questions from the Google search engine
and each question is paired with an answer span and golden passages from the
Wikipedia pages. In NQ, the goal of the retrieval stage is to find positive
passages from a large passage pool. We report Recall of top-$k$ (R@k), which
represents the proportion of top k retrieved passages that contain the
answers.

Trivia QA is a reading comprehension corpus authored by trivia enthusiasts.
Each sample is a $\langle question,answer,evidence\rangle$ triple. In the
retrieval stage, the goal is to find passages that contain the answer. We also
use Recall of top-$k$ as the evaluation metric for Trivia QA.

MS-MARCO Passage Ranking is widely used in information retrieval. It collects
real questions from the Bing search engine. Each question is paired with
several web documents. Following previous works (Ren et al., 2021; Qu et al.,
2021), we report MRR@10, R@50, R@1k on the dev set. Mean Reciprocal Rank (MRR)
is the mean of Reciprocal Rank(RR) across questions, calculated as the
reciprocal of the rank where the first relevant document was retrieved.

###  4.2 Implementation Details

First step, we follow the experiments in Sachan et al. (2021b) and Gao &
Callan (2021a) to continuous pre-training the ERNIE-2.0-base model (Sun et
al., 2020) with Inverse Cloze Task (ICT) training (Lee et al., 2019) for NQ
and TriviaQA datasets, and coCondenser training (Gao & Callan, 2021a) for MS-
MARCO dataset.

Second step, we follow the experiment settings of DPR (Karpukhin et al., 2020)
to train a warm-up dual-encoder retrieval model $\mathbf{G^{0}}$. It is
initialized with the continuous pretrained ERNIE-2.0-based model we obtained
in step one. Then we train a warm-up cross-encoder model $\mathbf{D^{0}}$
initialized with the ERNIE-2.0-Large. $\mathbf{D^{0}}$ learns to rank the
Top-k documents selected by $\mathbf{G^{0}}$ with contrastive learning. The
detailed hyper-parameters in training are listed in Appendix A.3.

Third step, we iteratively train the ranker (AR2-$\mathbf{D}$) model
initialized with ERNIE-2.0-large and the retriever (AR2-$\mathbf{G}$)
initialized with $\mathbf{G}^{0}$ according to Algorithm 1. The number of
training iterations is set to 10. During each iteration of training, the
retriever model is scheduled to train with 1500 mini-batches, while the ranker
model is scheduled to train with 500 mini-batches. The document index is
refreshed after each iteration of training. The other hyper-parameters are
shown in Appendix A.3.

All the experiments in this work run on 8 NVIDIA Tesla A100 GPUs. The
implementation code of AR2 is based on Huggingface Transformers (Wolf et al.,
2020) utilizing gradient checkpointing (Chen et al., 2016),
Apex111https://github.com/NVIDIA/apex, and gradient accumulation to reduce GPU
memory consumption.

| Natural Questions | Trivia QA | MS-MARCO
---|---|---|---
| R@5 | R@20 | R@100 | R@5 | R@20 | R@100 | MRR@10 | R@50 | R@1k
BM25 (Yang et al., 2017) | - | 59.1 | 73.7 | - | 66.9 | 76.7 | 18.7 | 59.2 | 85.7
GAR (Mao et al., 2021a) | 60.9 | 74.4 | 85.3 | 73.1 | 80.4 | 85.7 | - | - | -
doc2query (Nogueira et al., 2019b) | - | - | - | - | - | - | 21.5 | 64.4 | 89.1
DeepCT (Dai & Callan, 2019) | - | - | - | - | - | - | 24.3 | 69.0 | 91.0
docTTTTTquery (Nogueira et al., 2019a) | - | - | - | - | - | - | 27.7 | 75.6 | 94.7
DPR (Karpukhin et al., 2020) | - | 78.4 | 85.3 | - | 79.3 | 84.9 | - | - | -
ANCE (Xiong et al., 2021) | - | 81.9 | 87.5 | - | 80.3 | 85.3 | 33.0 | - | 95.9
RDR (Yang & Seo, 2020) | - | 82.8 | 88.2 | - | 82.5 | 87.3 | - | - | -
ColBERT (Khattab & Zaharia, 2020) | - | - | - | - | - | - | 36.0 | 82.9 | 96.8
RocketQA (Qu et al., 2021) | 74.0 | 82.7 | 88.5 | - | - | - | 37.0 | 85.5 | 97.9
COIL (Gao et al., 2021) | - | - | - | - | - | - | 35.5 | - | 96.3
ME-BERT (Luan et al., 2021) | - | - | - | - | - | - | 33.8 | - | -
Joint Top-k (Sachan et al., 2021a) | 72.1 | 81.8 | 87.8 | 74.1 | 81.3 | 86.3 | - | - | -
Individual Top-k (Sachan et al., 2021a) | 75.0 | 84.0 | 89.2 | 76.8 | 83.1 | 87.0 | - | - | -
PAIR (Ren et al., 2021) | 74.9 | 83.5 | 89.1 | - | - | - | 37.9 | 86.4 | 98.2
DPR-PAQ (Oğuz et al., 2021) |  |  |  |  |  |  |  |  |
-$\text{BERT}_{base}$ | 74.5 | 83.7 | 88.6 | - | - | - | 31.4 | - | -
-$\text{RoBERTa}_{base}$ | 74.2 | 84.0 | 89.2 | - | - | - | 31.1 | - | -
Condenser (Gao & Callan, 2021b) | - | 83.2 | 88.4 | - | 81.9 | 86.2 | 36.6 | - | 97.4
coCondenser (Gao & Callan, 2021a) | 75.8 | 84.3 | 89.0 | 76.8 | 83.2 | 87.3 | 38.2 | - | 98.4
AR2-$G^{0}$ | 69.7 | 80.8 | 87.1 | 74.4 | 81.7 | 86.6 | 34.8 | 84.2 | 98.0
AR2-$G$ | 77.9 | 86.0 | 90.1 | 78.2 | 84.4 | 87.9 | 39.5 | 87.8 | 98.6

Table 1: The comparison of the first-stage retrieval performance on Natural
Questions test set, Trivia QA test set, and MS-MARCO dev set. The results of
the first two blocks are from published papers. If the results are not
provided, we mark them as “-”.

###  4.3 Results

Performance of Retriever AR2-$\mathbf{G}$: The comparison of retrieval
performance on NQ, Trivia QA, and MS-MARCO are presented in Table 1.

We compare AR2-$\mathbf{G}$ with previous state-of-the-art methods, including
sparse and dense retrieval models. The top block shows the performance of
sparse retrieval methods. BM25 (Yang et al., 2017) is a traditional sparse
retriever based on the exact term matching. DeepCT (Dai & Callan, 2019) uses
BERT to dynamically generate lexical weights to augment BM25 Systems.
doc2Query (Nogueira et al., 2019b), docTTTTTQuery (Nogueira et al., 2019a),
and GAR (Mao et al., 2021a) use text generation to expand queries or documents
to make better use of BM25. The middle block lists the results of strong dense
retrieval methods, including DPR (Karpukhin et al., 2020), ANCE (Xiong et al.,
2021), RDR (Yang & Seo, 2020), RocketQA (Qu et al., 2021), Joint and
Individual Top-k (Sachan et al., 2021a), PAIR (Ren et al., 2021), DPR-PAQ
(Oğuz et al., 2021), Condenser (Gao & Callan, 2021b). coCondenser (Gao &
Callan, 2021a), ME-BERT (Luan et al., 2021), CoIL (Gao et al., 2021). These
methods improve the performance of dense retrieval by constructing hard
negative samples, jointly training the retriever and downstream tasks, pre-
training, knowledge distillation, and multi-vector representations.

The bottom block in Table 1 shows the results of proposed AR2 models.
AR2-$\mathbf{G^{0}}$ refers to the warm-up retrieval model in AR2 (details can
be found in section 4.2) which leverages the existing continuous pre-training
technique for dense text retrieval tasks. i.e., it shows a better performance
compared with DPR (Karpukhin et al., 2020) and ANCE (Xiong et al., 2021), etc
approaches that do not adopt the continuous pre-training procedure. We also
observed that AR2-$\mathbf{G}$: the retrieval model trained with the adversary
framework, significantly outperforms the warm-up AR2-$\mathbf{G^{0}}$ model,
and achieves new state-of-the-art performance on all three datasets.

###  4.4 Analysis

[2]

Table 2: Performance of rankers before and after AR2 training on NQ test set.

Retriever | Ranker | R@1 | R@5 | R@10
---|---|---|---|---
AR2-$\mathbf{G^{0}}$ | - | 48.3 | 69.7 | 76.2
AR2-$\mathbf{D^{0}}$ | 60.6 | 78.7 | 82.6
AR2-$\mathbf{D}$ | 64.2 | 79.0 | 82.6
AR2-G | - | 58.7 | 77.9 | 82.5
AR2-$\mathbf{D^{0}}$ | 61.1 | 80.1 | 84.3
AR2-$\mathbf{D}$ | 65.6 | 81.5 | 84.9

Table 3: Performance of AR2-G on NQ test set with different negative sample
size $n$.

| R@1 | R@5 | R@20 | R@100 | Latency
---|---|---|---|---|---
$n$=1 | 56.3 | 76.4 | 85.3 | 89.7 | 210ms
$n$=5 | 57.8 | 76.9 | 85.3 | 89.7 | 330ms
$n$=7 | 58.0 | 77.2 | 85.2 | 89.7 | 396ms
$n$=11 | 58.0 | 77.1 | 85.4 | 89.8 | 510ms
$n$=15 | 57.8 | 77.3 | 85.6 | 90.1 | 630ms

In this section, we conduct a set of detailed experiments on analyzing the
proposed AR2 training framework to help understand its pros and cons.

Performance of Ranker AR2-$\mathbf{D}$: To evaluate the performance of ranker
AR2-$\mathbf{D}$ on NQ, we first retrieve the top-$100$ documents for each
query in the test set with the help of dual-encoder AR2-$\mathbf{G}$ model,
and then re-rank them with the scores produced by the AR2-$\mathbf{D}$ model.
The results are shown in Table 3. “-” represents without ranker.
AR2-$\mathbf{D}^{0}$ refers to the warm-up ranker model in AR2. The results
show that the ranker obtains better performance compared with only using
retriever. It suggests that we could use a two-stage ranking strategy to
further boost the retrieval performance. Comparing the results of
AR2-$\mathbf{D}$ and AR2-$\mathbf{D}^{0}$, we further find that the ranker
AR2-$\mathbf{D}$ gets a significant gain with adversarial training.

Impact of Negative Sample Size: In the training of AR2, the number of negative
documents $n$ would affect both the model performance and training time. In
Table 3, we show the performance and the training latency per batch with
different negative sample size $n$. In this setting, we evaluate AR2 without
the regularization term. We observe the improvement over R@1 and R@5 by
increasing $n$ from $1$ to $7$, and marginal improvement when keep increasing
$n$ from $7$ to $15$. The latency of training per batch is almost linear
increased by improving $n$.

[2]

Figure 3: NQ R@5 on the number of iteration for both the AR2-retriever and the
AR2-ranker.

Figure 4: The comparison of ANCE and AR2 on NQ test set.

[2]

Table 4: Comparison of AR2 and IRGAN.

| R@1 | R@5 | R@20 | R@100
---|---|---|---|---
AR2 | 58.7 | 77.9 | 86.0 | 90.1
IRGAN | 55.2 | 75.2 | 84.5 | 89.2

Table 5: Effect of regularization in AR2.

| R@1 | R@5 | R@20 | R@100 | Entropy
---|---|---|---|---|---
AR2-$\mathbf{G}$ | 58.7 | 77.9 | 86.0 | 90.1 | 2.10
– w/o R | 57.8 | 77.3 | 85.6 | 90.1 | 1.70

Retriever | Ranker | R@1 | R@5 | R@10 | R@20 | R@50 | R@100
---|---|---|---|---|---|---|---
$\text{GAR}^{+}$ (Mao et al., 2021a) | - | 46.8 | 70.7 | 77.0 | 81.5 | - | 88.9
$\text{GAR}^{+}$ (Mao et al., 2021a) | BERT | 51.4 | 67.6 | 75.7 | 82.4 | - | 88.9
$\text{GAR}^{+}$ (Mao et al., 2021a) | BART | 55.2 | 73.5 | 78.5 | 82.2 | - | 88.9
$\text{GAR}^{+}$ (Mao et al., 2021a) | RIDER | 53.5 | 75.2 | 80.0 | 83.2 | - | 88.9
AR2-$\mathbf{G}$ | - | 58.7 | 77.9 | 82.5 | 86.0 | 88.5 | 90.1
AR2-$\mathbf{G}$ | AR2-$\mathbf{D}$ | 65.6 | 81.5 | 84.9 | 87.2 | 89.5 | 90.1
Table 6: The results of the second-stage ranking on Natural Questions test
set. Note that we copy the numbers of the first block from the RIDER paper
(Mao et al., 2021b).

Comparison with IRGAN: The original IRGAN (Wang et al., 2017) doesn’t work for
dense text retrieval tasks as it does not contain the dual-encoder retrieval
model for fast document indexing and search. However, it provides an
conventional GAN framework for training the generative and discriminative
models jointly for IR tasks. To compare the proposed AR2 with IRGAN, we
replaced the generative and discriminative models in IRGAN with the retriever
and ranker models in AR2, respectively. Therefore, with the configuration of
the same model architectures for generator (retriever) and discriminator
(ranker), The performance of the retriever is shown in Table 5. We see that
AR2 outperforms IRGAN significantly.

Effect of Regularization: To study the effectiveness of regularization, we
conducted ablation studies by removing the regularization term in the training
of retrieval model. In Table 5, “R” refers to the regularization item, it
shows that the regularization approach helps to improve the R@1 and R@5
evaluation metrics. In additional, we compute the average entropy of
distribution $p_{\theta}(\cdot|q,d,\mathbb{D}_{q})$ on the NQ test set, where
$\mathbb{D}_{q}$ is the retrieved top-$15$ documents. The average entropy
measures the sharpness of distribution $p_{\theta}(\cdot|q,d,\mathbb{D}_{q})$.
In experiments, the average entropies for with R and w/o R in AR2-$\mathbf{G}$
are $2.10$ and $1.70$ respectively. This indicates that the regularization
term could help smooth the prediction of probabilities in the retriever.

Visualization of the Training Procedure: We visualize the changes of R@5
during the AR2-G training. The result is shown in Figure 4. We see that as
adversarial iteration increases, the R@5 of both AR2-retriever and AR2-ranker
also gradually increases. AR2-retriever has the most significant improvement
(about 4.5%) after the first iteration. While the training advances closer to
the convergence, the improvement of R@5 also gradually slows down. In the end,
AR2-retriever is improved by approximately 8% and AR2-ranker is improved by
approximately 3%.

Adversarial Training versus Iterative Hard-Negative Sampling: To give a fair
comparison of AR2 and ANCE (Xiong et al., 2021), we retrain the ANCE model by
initializing it with the same warm-up AR2-$\mathbf{G^{0}}$ which leverages the
advantage of the continuous pre-training technique. In experiments, ANCE
trains the retriever with an iterative hard-negative sampling approach instead
of adversarial training in AR2. In Figure 4, we observe that AR2 steadily
outperforms ANCE during training in terms of R@5 and R@10 evaluation metrics
with the same model-initialization. It shows that AR2 is a superior training
framework compared with ANCE.

Performance of the Pipeline: We evaluate the performance of the retrieve-then-
rank pipeline on NQ dataset. The results are shown in Table 6.
$\text{GAR}^{+}$ is a sparse retriever which ensembles GAR (Mao et al., 2021a)
and DPR (Karpukhin et al., 2020). BERT (Nogueira & Cho, 2019), BART (Nogueira
et al., 2020), and RIDER (Mao et al., 2021b) are three ranking methods. BERT
ranker is a cross-encoder, which makes a binary relevance decision for each
query-passage pair. BART ranker generates relevance labels as target tokens in
a seq2seq manner. RIDER re-ranks the retrieved passages based on the lexical
overlap with the top predicted answers from the reader. The results show that
AR2 pipeline significantly outperforms existing public pipelines.

##  5 Related work

Text Retrieval: Text retrieval aims to find related documents from a large
corpus given a query. Retrieval-then-rank is the widely used pipeline (Huang
et al., 2020; Zou et al., 2021).

For the first stage retrieval, early researchers used sparse vector space
models, e.g., BM25 (Yang et al., 2017). Recently, some works improve the
traditional sparse retriever with neural network, e.g., Dai & Callan (2019)
use BERT to dynamically generate term weights, doc2Query (Nogueira et al.,
2019b), docTTTTTQuery (Nogueira et al., 2019a), and GAR (Mao et al., 2021a)
use text generation to expand queries or documents to make better use of BM25.

Recently, dense retrieval methods have become a new paradigm for the first
stage of retrieval. Various methods have been proposed to enhance dense
retrieval, e.g., DPR (Karpukhin et al., 2020) and ME-BERT (Luan et al., 2021)
use in-batch negatives and construct hard negatives by BM25; ANCE (Xiong et
al., 2021), RocketQA (Qu et al., 2021), and ADORE (Zhan et al., 2021) improve
the hard negative sampling by iterative replacement, denoising, and dynamic
sampling, respectively; PAIR (Ren et al., 2021) leverages passage-centric
similarity relation into training object; FID-KD (Izacard & Grave, 2020) and
RDR (Yang & Seo, 2020) distill knowledge from reader to retriever; Guu et al.
(2020) and Sachan et al. (2021b) enhance retriever by jointly training with
downstream tasks. Some researchers focus on the pre-training of dense
retrieval, such as ICT (Lee et al., 2019), Condenser (Gao & Callan, 2021b) and
Cocondenser (Gao & Callan, 2021a).

For the second stage ranking, previous works typically use cross-encoder based
methods. The cross-encoder models which capture the token-level interactions
between the query and the document (Guo et al., 2016; Xiong et al., 2017),
have shown to be more effective. Various methods are proposed to enhance
ranker, e.g., Nogueira & Cho (2019) use BERT to make a binary relevance
decision for each query-passage pair; Nogueira et al. (2020) adopt BART to
generate relevance labels as target tokens in a seq2seq manner; Khattab &
Zaharia (2020) and Gao et al. (2020) adopt the lightweight interaction based
on the representations of dense retrievers to reduce computation. However,
negative samples are statically sampled in these works. In AR2, negative
samples for training the ranker will be dynamically adjusted with the
progressive retriever.

Generative Adversarial Nets: Generative Adversarial Nets (Goodfellow et al.,
2014) have been widely studied in the generation field, i.e., image generation
(Brock et al., 2018) and text generation (Yu et al., 2017). With a minimax
game, GAN aims to train a generative model to fit the real data distribution
under the guidance of a discriminative model. Few works study GAN to text
retrieval. A related work is IRGAN (Wang et al., 2017). It proposes a minimax
retrieval framework that aims to unify the generative and discriminative
retrieval models.

##  6 Conclusion

In this paper, we introduce AR2, an adversarial retriever-ranker framework to
jointly train the end-to-end retrieve-then-rank pipeline. In AR2, the
retriever retrieves hard negatives to cheat the ranker, and the ranker learns
to rank the collection of positives and hard negatives while providing
progressive rewards to the retriever. AR2 can iteratively improve the
performance of both the retriever and the ranker because (1) the retriever is
guided by the progressive ranker; (2) the ranker learns better through the
harder negatives sampled by the progressive retriever. AR2 achieves new state-
of-the-art performance on all three competitive benchmarks.

## References

  * Brickley et al. (2019) Dan Brickley, Matthew Burgess, and Natasha Noy.  Google dataset search: Building a search engine for datasets in an open web ecosystem.  In _WWW_ , 2019.
  * Brock et al. (2018) Andrew Brock, Jeff Donahue, and Karen Simonyan.  Large scale gan training for high fidelity natural image synthesis.  In _ICLR_ , 2018.
  * Chen et al. (2017) Danqi Chen, Adam Fisch, Jason Weston, and Antoine Bordes.  Reading wikipedia to answer open-domain questions.  In _ACL_ , 2017.
  * Chen et al. (2016) Tianqi Chen, Bing Xu, Chiyuan Zhang, and Carlos Guestrin.  Training deep nets with sublinear memory cost.  _arXiv preprint arXiv:1604.06174_ , 2016.
  * Dai & Callan (2019) Zhuyun Dai and Jamie Callan.  Deeper text understanding for ir with contextual neural language modeling.  In _SIGIR_ , 2019.
  * Gao & Callan (2021a) Luyu Gao and Jamie Callan.  Unsupervised corpus aware language model pre-training for dense passage retrieval.  _arXiv preprint arXiv:2108.05540_ , 2021a.
  * Gao & Callan (2021b) Luyu Gao and Jamie Callan.  Is your language model ready for dense representation fine-tuning?  _arXiv preprint arXiv:2104.08253_ , 2021b.
  * Gao et al. (2020) Luyu Gao, Zhuyun Dai, and Jamie Callan.  Modularized transfomer-based ranking framework.  In _EMNLP_ , 2020.
  * Gao et al. (2021) Luyu Gao, Zhuyun Dai, and Jamie Callan.  COIL: revisit exact lexical match in information retrieval with contextualized inverted list.  In _NAACL-HLT_ , 2021.
  * Goodfellow et al. (2014) Ian Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio.  Generative adversarial nets.  _NIPS_ , 2014.
  * Guo et al. (2018) Daya Guo, Duyu Tang, Nan Duan, Ming Zhou, and Jian Yin.  Dialog-to-action: Conversational question answering over a large-scale knowledge base.  2018\.
  * Guo et al. (2020) Daya Guo, Shuo Ren, Shuai Lu, Zhangyin Feng, Duyu Tang, Shujie Liu, Long Zhou, Nan Duan, Alexey Svyatkovskiy, Shengyu Fu, et al.  Graphcodebert: Pre-training code representations with data flow.  _arXiv preprint arXiv:2009.08366_ , 2020.
  * Guo et al. (2016) Jiafeng Guo, Yixing Fan, Qingyao Ai, and W Bruce Croft.  A deep relevance matching model for ad-hoc retrieval.  In _CIKM_ , 2016.
  * Guu et al. (2020) Kelvin Guu, Kenton Lee, Zora Tung, Panupong Pasupat, and Mingwei Chang.  Retrieval augmented language model pre-training.  In _ICML_ , 2020.
  * Han et al. (2020) Shuguang Han, Xuanhui Wang, Mike Bendersky, and Marc Najork.  Learning-to-rank with bert in tf-ranking.  _arXiv preprint arXiv:2004.08476_ , 2020.
  * Hu et al. (2020) Linmei Hu, Siyong Xu, Chen Li, Cheng Yang, Chuan Shi, Nan Duan, Xing Xie, and Ming Zhou.  Graph neural news recommendation with unsupervised preference disentanglement.  In _ACL_ , 2020.
  * Huang et al. (2020) Jui-Ting Huang, Ashish Sharma, Shuying Sun, Li Xia, David Zhang, Philip Pronin, Janani Padmanabhan, Giuseppe Ottaviano, and Linjun Yang.  Embedding-based retrieval in facebook search.  In _KDD_ , 2020.
  * Huang et al. (2013) Po-Sen Huang, Xiaodong He, Jianfeng Gao, Li Deng, Alex Acero, and Larry Heck.  Learning deep structured semantic models for web search using clickthrough data.  In _CIKM_ , 2013.
  * Izacard & Grave (2020) Gautier Izacard and Edouard Grave.  Distilling knowledge from reader to retriever for question answering.  _arXiv preprint arXiv:2012.04584_ , 2020.
  * Johnson et al. (2019) Jeff Johnson, Matthijs Douze, and Hervé Jégou.  Billion-scale similarity search with gpus.  _IEEE Transactions on Big Data_ , 2019.
  * Joshi et al. (2017) Mandar Joshi, Eunsol Choi, Daniel S. Weld, and Luke Zettlemoyer.  Triviaqa: A large scale distantly supervised challenge dataset for reading comprehension.  In _ACL_ , 2017.
  * Karpukhin et al. (2020) Vladimir Karpukhin, Barlas Oguz, Sewon Min, Patrick S. H. Lewis, Ledell Wu, Sergey Edunov, Danqi Chen, and Wen-tau Yih.  Dense passage retrieval for open-domain question answering.  In _EMNLP_ , 2020.
  * Khattab & Zaharia (2020) Omar Khattab and Matei Zaharia.  Colbert: Efficient and effective passage search via contextualized late interaction over bert.  In _SIGIR_ , 2020.
  * Kwiatkowski et al. (2019) Tom Kwiatkowski, Jennimaria Palomaki, Olivia Redfield, Michael Collins, Ankur P. Parikh, Chris Alberti, Danielle Epstein, Illia Polosukhin, Jacob Devlin, Kenton Lee, Kristina Toutanova, Llion Jones, Matthew Kelcey, Ming-Wei Chang, Andrew M. Dai, Jakob Uszkoreit, Quoc Le, and Slav Petrov.  Natural questions: a benchmark for question answering research.  _Trans. Assoc. Comput. Linguistics_ , 7:452–466, 2019.
  * Lee et al. (2019) Kenton Lee, Ming-Wei Chang, and Kristina Toutanova.  Latent retrieval for weakly supervised open domain question answering.  In _ACL_ , 2019.
  * Liu et al. (2020) Dayiheng Liu, Yeyun Gong, Jie Fu, Yu Yan, Jiusheng Chen, Daxin Jiang, Jiancheng Lv, and Nan Duan.  Rikinet: Reading wikipedia pages for natural question answering.  In _ACL_ , 2020.
  * Luan et al. (2021) Yi Luan, Jacob Eisenstein, Kristina Toutanova, and Michael Collins.  Sparse, dense, and attentional representations for text retrieval.  _Transactions of the Association for Computational Linguistics_ , 9:329–345, 2021.
  * Manning et al. (2008) Christopher D. Manning, Prabhakar Raghavan, and Hinrich Schütze.  _Introduction to Information Retrieval_.  Cambridge University Press, Cambridge, UK, 2008.  ISBN 978-0-521-86571-5.
  * Mao et al. (2021a) Yuning Mao, Pengcheng He, Xiaodong Liu, Yelong Shen, Jianfeng Gao, Jiawei Han, and Weizhu Chen.  Generation-augmented retrieval for open-domain question answering.  In _ACL_ , 2021a.
  * Mao et al. (2021b) Yuning Mao, Pengcheng He, Xiaodong Liu, Yelong Shen, Jianfeng Gao, Jiawei Han, and Weizhu Chen.  Reader-guided passage reranking for open-domain question answering.  In _Findings of ACL/IJCNLP_ , 2021b.
  * Mitra & Craswell (2017) Bhaskar Mitra and Nick Craswell.  Neural models for information retrieval.  _CoRR_ , abs/1705.01509, 2017.  URL http://arxiv.org/abs/1705.01509.
  * Nguyen et al. (2016) Tri Nguyen, Mir Rosenberg, Xia Song, Jianfeng Gao, Saurabh Tiwary, Rangan Majumder, and Li Deng.  Ms marco: A human generated machine reading comprehension dataset.  In _CoCo@ NIPS_ , 2016.
  * Nogueira & Cho (2019) Rodrigo Nogueira and Kyunghyun Cho.  Passage re-ranking with bert.  _arXiv preprint arXiv:1901.04085_ , 2019.
  * Nogueira et al. (2019a) Rodrigo Nogueira, Jimmy Lin, and AI Epistemic.  From doc2query to doctttttquery.  _Online preprint_ , 2019a.
  * Nogueira et al. (2019b) Rodrigo Nogueira, Wei Yang, Jimmy Lin, and Kyunghyun Cho.  Document expansion by query prediction.  _arXiv preprint arXiv:1904.08375_ , 2019b.
  * Nogueira et al. (2020) Rodrigo Nogueira, Zhiying Jiang, and Jimmy Lin.  Document ranking with a pretrained sequence-to-sequence model.  _arXiv preprint arXiv:2003.06713_ , 2020.
  * Oğuz et al. (2021) Barlas Oğuz, Kushal Lakhotia, Anchit Gupta, Patrick Lewis, Vladimir Karpukhin, Aleksandra Piktus, Xilun Chen, Sebastian Riedel, Wen-tau Yih, Sonal Gupta, et al.  Domain-matched pre-training tasks for dense retrieval.  _arXiv preprint arXiv:2107.13602_ , 2021.
  * Qu et al. (2021) Yingqi Qu, Yuchen Ding, Jing Liu, Kai Liu, Ruiyang Ren, Wayne Xin Zhao, Daxiang Dong, Hua Wu, and Haifeng Wang.  Rocketqa: An optimized training approach to dense passage retrieval for open-domain question answering.  In _NAACL-HLT_ , 2021.
  * 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, Gretchen Krueger, and Ilya Sutskever.  Learning transferable visual models from natural language supervision.  _CoRR_ , abs/2103.00020, 2021.
  * Ren et al. (2021) Ruiyang Ren, Shangwen Lv, Yingqi Qu, Jing Liu, Wayne Xin Zhao, Qiaoqiao She, Hua Wu, Haifeng Wang, and Ji-Rong Wen.  PAIR: leveraging passage-centric similarity relation for improving dense passage retrieval.  In _Findings of ACL/IJCNLP_ , 2021.
  * Sachan et al. (2021a) Devendra Singh Sachan, Mostofa Patwary, Mohammad Shoeybi, Neel Kant, Wei Ping, William L. Hamilton, and Bryan Catanzaro.  End-to-end training of neural retrievers for open-domain question answering.  In _ACL/IJCNLP_ , 2021a.
  * Sachan et al. (2021b) Devendra Singh Sachan, Siva Reddy, William Hamilton, Chris Dyer, and Dani Yogatama.  End-to-end training of multi-document reader and retriever for open-domain question answering.  _arXiv preprint arXiv:2106.05346_ , 2021b.
  * Shen et al. (2014) Yelong Shen, Xiaodong He, Jianfeng Gao, Li Deng, and Grégoire Mesnil.  Learning semantic representations using convolutional neural networks for web search.  In _WWW_ , 2014.
  * Sun et al. (2020) Yu Sun, Shuohuan Wang, Yukun Li, Shikun Feng, Hao Tian, Hua Wu, and Haifeng Wang.  Ernie 2.0: A continual pre-training framework for language understanding.  In _AAAI_ , 2020.
  * Vaswani et al. (2017) Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Lukasz Kaiser, and Illia Polosukhin.  Attention is all you need.  In _NIPS_ , 2017.
  * Wang et al. (2017) Jun Wang, Lantao Yu, Weinan Zhang, Yu Gong, Yinghui Xu, Benyou Wang, Peng Zhang, and Dell Zhang.  Irgan: A minimax game for unifying generative and discriminative information retrieval models.  In _SIGIR_ , 2017.
  * Wolf et al. (2020) Thomas Wolf, Lysandre Debut, Victor Sanh, Julien Chaumond, Clement Delangue, Anthony Moi, Pierric Cistac, Tim Rault, Rémi Louf, Morgan Funtowicz, Joe Davison, Sam Shleifer, Patrick von Platen, Clara Ma, Yacine Jernite, Julien Plu, Canwen Xu, Teven Le Scao, Sylvain Gugger, Mariama Drame, Quentin Lhoest, and Alexander M. Rush.  Transformers: State-of-the-art natural language processing.  In _EMNLP_ , 2020.
  * Xiong et al. (2017) Chenyan Xiong, Zhuyun Dai, Jamie Callan, Zhiyuan Liu, and Russell Power.  End-to-end neural ad-hoc ranking with kernel pooling.  In _SIGIR_ , 2017.
  * Xiong et al. (2021) Lee Xiong, Chenyan Xiong, Ye Li, Kwok-Fung Tang, Jialin Liu, Paul N. Bennett, Junaid Ahmed, and Arnold Overwijk.  Approximate nearest neighbor negative contrastive learning for dense text retrieval.  In _ICLR_ , 2021.
  * Yang et al. (2017) Peilin Yang, Hui Fang, and Jimmy Lin.  Anserini: Enabling the use of lucene for information retrieval research.  In _SIGIR_ , 2017.
  * Yang & Seo (2020) Sohee Yang and Minjoon Seo.  Is retriever merely an approximator of reader?  _arXiv preprint arXiv:2010.10999_ , 2020.
  * Yu et al. (2017) Lantao Yu, Weinan Zhang, Jun Wang, and Yong Yu.  Seqgan: Sequence generative adversarial nets with policy gradient.  In _AAAI_ , 2017.
  * Zhan et al. (2020) Jingtao Zhan, Jiaxin Mao, Yiqun Liu, Min Zhang, and Shaoping Ma.  Repbert: Contextualized text embeddings for first-stage retrieval.  _arXiv preprint arXiv:2006.15498_ , 2020.
  * Zhan et al. (2021) Jingtao Zhan, Jiaxin Mao, Yiqun Liu, Jiafeng Guo, Min Zhang, and Shaoping Ma.  Optimizing dense retrieval model training with hard negatives.  In _SIGIR_ , 2021.
  * Zou et al. (2021) Lixin Zou, Shengqiang Zhang, Hengyi Cai, Dehong Ma, Suqi Cheng, Shuaiqiang Wang, Daiting Shi, Zhicong Cheng, and Dawei Yin.  Pre-trained language model based ranking in baidu search.  In _KDD_ , 2021.

##  Appendix A Appendix

###  A.1 Proof

Proof of Eqn. 9: Suppose $d^{-}_{i}\in\mathbb{D}_{q}^{-}$ is sampled by
$p_{\theta}(\cdot|q;\mathbb{D}^{-}_{q})$, thus

$\displaystyle J^{\theta}$ $\displaystyle=\mathbf{E}_{\mathbb{D}^{-}_{q}\sim
G_{\theta}(q,\cdot)}\left[\text{log}p_{\phi}(d|q;\\{d\\}\cup\mathbb{D}^{-}_{q})\right]$
(13) $\displaystyle\leq\mathbf{E}_{\mathbb{D}^{-}_{q}\sim
G_{\theta}(q,\cdot)}\left(\mathbf{E}_{d^{-}_{i}\sim
p_{\phi}(\cdot|q;\mathbb{D}^{-}_{q})}\left[\text{log}p_{\phi}(d|q;\\{d,d^{-}_{i}\\})\right]\right)$

where $\mathbb{D}^{-}_{q}$ indicates the set of negative documents sampled by
$G_{\theta}(q,\cdot)$. In practice, we approximate $\mathbb{D}^{-}_{q}$ by
sampling $n$ documents from the top-$K$ retrieved negative set. Therefore, we
could further obtain the following approximately equation in implementation.

$\displaystyle\approx\mathbf{E}_{d^{-}_{i}\sim
p_{\theta}(\cdot|q;\mathbb{D}^{-}_{q})}\left[\text{log}p_{\phi}(d|q;\\{d,d^{-}_{i}\\})\right]=$
$\displaystyle\hat{J}^{\theta}$ (14)

Proof of Eqn. 10:

$\displaystyle\nabla_{\theta}\hat{J}^{\theta}$
$\displaystyle=\nabla_{\theta}\mathbf{E}_{d^{-}_{i}\sim
p_{\theta}(\cdot|q;\mathbb{D}_{q}^{-})}\left[\text{log}p_{\phi}(d|q;\\{d,d^{-}_{i}\\})\right]$
(15)
$\displaystyle=\sum_{i}\nabla_{\theta}p_{\theta}(d^{-}_{i}|q;\mathbb{D}_{q}^{-})\left[\text{log}p_{\phi}(d|q;\\{d,d^{-}_{i}\\})\right]$
$\displaystyle=\sum_{i}p_{\theta}(d^{-}_{i}|q;\mathbb{D}_{q}^{-})\nabla_{\theta}\log
p_{\theta}(d^{-}_{i}|q;\mathbb{D}_{q}^{-})\left[\text{log}p_{\phi}(d|q;\\{d,d^{-}_{i}\\})\right]$
$\displaystyle=\mathbf{E}_{d^{-}_{i}\sim
p_{\theta}(\cdot|q;\mathbb{D}_{q}^{-})}\nabla_{\theta}\log
p_{\theta}(d^{-}_{i}|q;\mathbb{D}_{q}^{-})\left[\log
p_{\phi}(d|q;\\{d,d^{-}_{i}\\})\right]$

###  A.2 Efficiency Report

We list the time cost of training and inference in Table 7. The evaluation is
made with 8 NVIDIA A100 GPUs. The max step of ANCE training is from the ANCE’s
open-source website 222https://github.com/microsoft/ANCE.We estimate the
overall training time without taking account of the time of continuous pre-
training step and warming-up step.

Table 7: Comparison of Efficiency  | DPR | ANCE | AR2(n=15) | AR2(n=1)
---|---|---|---|---
Training |  |  |  |
Batch Size | 128 | 128 | 64 | 64
Max Step | 20k | 136k | 20k | 20k
BP for Retriever | 1.8h | 11h | 2.3h | 1h
BP for Ranker | - | - | 0.75h | 0.35h
Iteration Number | 0 | 10 | 10 | 10
Index Refresh | 0.5 | 0.5h | 0.5h | 0.5h
Overall | 1.85h | 16h | 9.1h | 6.4h
Inference |  |  |  |
Encoding of Corpus | 20min | 20min | 20min | 20min
Query Encoding | 40ns | 40ns | 40ns | 40ns
ANN Index Build | 2min | 2min | 2min | 2min
ANN Retrieval(Top-100) | 2ms | 2ms | 2ms | 2ms

###  A.3 Hyperparameters

Table 8: Hyperparameters for AR2 training. | Parameter | NQ | TriviaQA | MS-MARCO
---|---|---|---|---
| Max query length | 32 | 32 | 32
Default | Max passage length | 128 | 128 | 128
AR2-$G^{0}$ | Learning rate | 1e-5 | 1e-5 | 1e-4
Negative size | 255 | 255 | 127
Batch size | 128 | 128 | 64
Temperature $\tau$ | 1 | 1 | 1
Optimizer | AdamW | AdamW | AdamW
Scheduler | Linear | Linear | Linear
Warmup proportion | 0.1 | 0.1 | 0.1
Training epoch | 40 | 40 | 3
AR2-$D^{0}$ | Learning rate | 1e-5 | 1e-5 | 1e-5
Negative size | 15 | 15 | 15
Batch size | 64 | 64 | 256
Temperature $\tau$ | 1 | 1 | 1
Optimizer | AdamW | AdamW | AdamW
Scheduler | Linear | Linear | Linear
Warmup proportion | 0.1 | 0.1 | 0.1
Training step per iteration | 1500 | 1500 | 1500
Max step | 2000 | 2000 | 4000
| Learning rate | 1e-5 | 1e-5 | 5e-6
| Negative size | 15 | 15 | 15
| Batch size | 64 | 64 | 64
| Temperature $\tau$ | 1 | 1 | 1
| Optimizer | AdamW | AdamW | AdamW
| Scheduler | Linear | Linear | Linear
| Warmup proportion | 0.1 | 0.1 | 0.1
| Training step per iteration | 1500 | 1500 | 1500
| Max step | 15000 | 15000 | 15000
AR2-$G$ | Negative size | 15 | 15 | 15
| Learning rate | 1e-6 | 1e-6 | 5e-7
| Batch size | 64 | 64 | 64
| Temperature $\tau$ | 1 | 1 | 1
| Optimizer | AdamW | AdamW | AdamW
| Scheduler | Linear | Linear | Linear
| Warmup proportion | 0.1 | 0.1 | 0.1
| Training step per iteration | 500 | 500 | 500
AR2-$D$ | Max step | 5000 | 5000 | 5000

###  A.4 Model configuration and experiment settings

We list the detailed configuration of AR2 and baseline models in Table 9.

Table 9: Model configuration and experiment settings.

Model | Initial Model | Parameters |  Further Pretrain |  Additional Data
---|---|---|---|---
DPR (Karpukhin et al., 2020) | BERT-Base | 110M | - | -
ANCE (Xiong et al., 2021) | BERT/RoBERTa-Base | 110M/125M | - | -
RocketQA (Qu et al., 2021) |  ERNIE-2.0-Base ERNIE-2.0-Large |  110M 330M |  - - | 1.7 M
PAIR (Ren et al., 2021) |  ERNIE-2.0-Base ERNIE-2.0-Large |  110M 330M |  - - | 1.7 M
Individual Top-k (Sachan et al., 2021a) |  ERNIE-2.0-Base T5-Large |  110M 739M |  Yes - | -
coCondenser (Gao & Callan, 2021a) | BERT-Base | 110M | Yes | -
Our (AR2-G) (Retriever) | ERNIE-2.0-Base | 110M | Yes | -
Our (AR2-D) (Ranker) | ERNIE-2.0-Large | 330M | - | -

###  A.5 Ablation study on different initial models

Table 10 shows the results of our method with different initial models. We see
that ERNIE-Base as the initial model achieves a little better performance than
BERT-Base. And AR2-G using BERT-Base as the initial model still achieves
better performance than other methods under the same initial model. Meanwhile,
ICT pre-training improves the performance of AR2-G.

Table 10: Performance of AR2-G on NQ test set with different initial model | Initial Model | R@1 | R@5 | R@20 | R@100
---|---|---|---|---|---
DPR (Karpukhin et al., 2020) | BERT-Base | - | - | 78.4 | 85.3
ANCE (Xiong et al., 2021) | BERT-Base | - | - | 81.9 | 87.5
RocketQA (Qu et al., 2021) | ERNIE-Base | - | 74.0 | 82.7 | 88.5
PAIR (Ren et al., 2021) | ERNIE-Base | - | 74.9 | 83.5 | 89.1
AR2-G | BERT-Base | 56.7 | 76.1 | 85.0 | 89.3
AR2-G | ERNIE-Base | 57.2 | 76.6 | 85.3 | 89.8
AR2-G | ERNIE-Base w/ ICT | 58.7 | 77.9 | 86.0 | 90.1

###  A.6 Comparison with several existing approaches

Table 11 shows the comparison of AR2 and several existing retrieval
approaches. “Extra Label” refers to whether the answer label is used. AR2
jointly optimizes both the retriever and the ranker according to a principle
adversarial objective, which is the key difference with previous works.

Table 11: Comparison with existing approaches

Model | Extra Label |  Retriever-Ranker/ Retriever-Reader |  Adversarial Objective |  Update Hard Negatives
---|---|---|---|---
FID-KD (Izacard & Grave, 2020) | Yes | Yes | No | No
RDR (Yang & Seo, 2020) | Yes | Yes | No | No
RocketQA (Qu et al., 2021) | No | Yes | No | Yes
ANCE (Xiong et al., 2021) | No | No | No | Yes
RIDER (Mao et al., 2021b) | Yes | Yes | No | No
AR2 | No | Yes | Yes | Yes

###  A.7 Performance of the pipeline

Table 12 shows the performance of the retrieve-then-rank pipeline on Trivia QA
and MS-MARCO. From the results of Table 6 and Table 12, we find that the
ranker AR2-D improves the performance on all three benchmarks including NQ,
Trivia QA, and MS-MARCO. Meanwhile, the pipeline based on AR2 achieves state-
of-the-art performances on all benchmarks.

Table 12: The results of the second-stage ranking on Trivia QA and MS-MARCO.

|  | Trivia QA | MS-MARCO
---|---|---|---
Retriever | Ranker | R@1 | R@5 | R@10 | R@20 | MRR@10
RepBERT (Zhan et al., 2020) | RepBERT (Zhan et al., 2020) | - | - | - | - | 37.7
ME-HYBIRD (Luan et al., 2021) | ME-HYBIRD (Luan et al., 2021) | - | - | - | - | 39.4
ME-BERT (Luan et al., 2021) | ME-BERT (Luan et al., 2021) | - | - | - | - | 39.5
BM25 (Yang et al., 2017) | TFR-BERT (Han et al., 2020) | - | - | - | - | 40.5
$\text{GAR}^{+}$ (Mao et al., 2021a) | RIDER (Mao et al., 2021b) | 71.9 | 77.5 | 79.8 | 81.8 | -
AR2-G | - | 64.2 | 78.2 | 81.8 | 84.4 | 39.5
AR2-G | AR2-D | 73.0 | 82.1 | 84.1 | 85.8 | 43.2

###  A.8 Performance of the large-size model

Table 13 shows the results of AR2-G (Retriever) initialized with
ERNIE-2.0-Large (without continuous pre-training (ICT)). All baselines are
initialized by large-size model, and DPR-PAQ (Oğuz et al., 2021) utilizes a
large external corpus (65m question-answer pairs) to continue pre-training the
model; Individual Top-K (Sachan et al., 2021a) utilizes T5-Large model (739M
parameters vs 330M parameters ERNIE-2.0-Large) as reader to guide the
retriever. Compared with these baseline methods, AR2-G achieves a significant
performance improvement, which further demonstrates the effectiveness of AR2-G
(Retriever).

Table 13: The performance of large-size models on Natural Questions test set,  | Size | R@1 | R@5 | R@20 | R@100
---|---|---|---|---|---
DPR-PAQ${}_{\text{BERT}}$ (Oğuz et al., 2021) | Large | - | 75.3 | 84.4 | 88.9
DPR-PAQ${}_{\text{RoBERTa}}$ (Oğuz et al., 2021) | Large | - | 76.9 | 84.7 | 89.2
Individual Top-K (Sachan et al., 2021a) | Large | 57.5 | 76.2 | 84.8 | 89.8
AR2-G | Base | 58.7 | 77.9 | 86.0 | 90.1
AR2-G | Large | 61.1 | 78.8 | 86.5 | 90.4


# Weight-Based Exploration for Unmanned Aerial Teams Searching for Multiple
Survivors

Sarthak J. Shetty  Debasish Ghose  Department of Aerospace Engineering, Indian
Institute of Science, Bengaluru, India

###### Abstract

During floods, reaching survivors in the shortest possible time is a priority
for rescue teams. Given their ability to explore difficult terrain in short
spans of time, Unmanned Aerial Vehicles (UAVs) have become an increasingly
valuable aid to search and rescue operations. Traditionally, UAVs utilize
exhaustive lawnmower exploration patterns to locate stranded survivors,
without any information regarding the survivor’s whereabouts. In real life
disaster scenarios however, on-ground observers provide valuable information
to the rescue effort, such as the survivor’s last known location and heading.
In earlier work, a Weight Based Exploration (WBE) model, which utilizes this
information to generate a prioritized list of waypoints to aid the UAV in its
search mission, was proposed. This approach was shown to be effective for a
single UAV locating a single survivor. In this paper, we extend the WBE model
to a team of UAVs locating multiple survivors. The model initially partitions
the search environment amongst the UAVs using Voronoi cells. The UAVs then
utilize the WBE model to locate survivors in their partitions. We test this
model with varying survivor locations and headings. We demonstrate the
scalability of the model developed by testing the model with aerial teams
comprising several UAVs.

###### keywords:

Multi-robot systems , probabilistic exploration , path-planning , rescue
robotics

††journal: arXiv

##  1 Introduction

Floods cause damage to communities with loss to human life and infrastructure.
In recent years, several technological solutions, in areas such as dynamic
routing of resources [1] and monitoring of fast flowing waters [2], have been
proposed to mitigate the effects of such natural disasters [3], [4]. Given
their ability to rapidly traverse large areas affected by fast moving flood
waters, UAVs are becoming increasingly popular as an aid in rescue and
monitoring efforts [5], [6], [7]. During rescue efforts, UAVs traditionally
use the exhaustive lawnmower search pattern to explore a given area for
survivors. Albeit effective, this model requires a significant amount of time
to completely survey a given area and locate survivors. Such models do not
leverage valuable observations made by on-ground rescue personnel, such as the
survivor’s last known position and heading. In [6], a Weight-Based Exploration
(WBE) model, which leverages valuable information regarding the survivor, as
conveyed by on-ground observers, was described to generate a prioritized list
of waypoints for exploration to aid the UAV in its search for survivors. This
WBE model reduces the time taken by the UAV to locate survivors by nearly 215%
in Gazebo simulations and 75% in physical testing, in comparison to the
lawnmower model, using an off-the-shelf UAV [7].

In order to survey large areas effectively in a short span of time, the use of
UAV teams has been found to offer a possible viable solution [8]. In this
paper, the authors extend the WBE model to a team of UAVs, that collectively
explore a given area for multiple flood survivors.

The paper is organized as follows: The Weight-Based Exploration (WBE) model is
first described in Section 2. In Section 3, the use of WBE for multi-UAV teams
is described, followed by a description of the simulation environment and the
results of the simulations in Section 4. The paper is concluded in Section 5,
with a brief account of the paper’s contribution and suggestions for further
work.

##  2 The Basic Weight-Based Exploration Model and Extensions

The Weight-Based Exploration model, first described in [6], leverages the last
known position and heading of a survivor, as reported by an on-ground
observer, to generate a prioritized list of waypoints for exploration, which
enables a UAV to locate the survivor in a short time-span. Figure 1 is a
diagrammatic representation of this model for a single UAV case.

Figure 1: Diagrammatic Representation of Weight-Based Exploration for a single
UAV

In the WBE model, the coordinates lying along the direction of the survivor’s
heading receives the highest ”weight” and therefore the highest priority of
exploration. The second highest priority of exploration is assigned to the
quadrant on the left of the survivor’s heading and the quadrant on the right
receives the third highest priority. The priorities assigned to these two
quadrant are interchangeable. The direction opposite to the survivor’s
heading, is assigned the least priority of exploration. This differential
assignment of weights to the environment coordinates, based on their proximity
to the survivor’s location and heading, allows us to arrive at a list of
waypoints, where the highest weighted waypoints represent the most probable
location where the survivor might be present.

In Figure 1, the UAV initially performs the lawnmower exploration (path in
green, marked as i) to locate survivors. Once it receives information
regarding a survivor’s last known position and heading from the observer (red
circle, marked as ii), it breaks free from the lawnmower model and initiates
the WBE model (path in blue, marked as iii), starting from the survivor’s last
known position.

Table 1: Parameters of Monte-Carlo Simulations [6] Parameter | Value
---|---
Environment Size | 600 m x 600 m
Survivor Speed | 0.6 m/s and 2 m/s
UAV Max Speed | 12 m/s
UAV Search Radius | 18 m x 18 m
UAV Camera FOV | $None$
UAV Flight Time | 30 minutes
Height of UAV | 9 m
Observer Search Radius | 30 m
Number of observers | 30
Observer Positions | Randomized

In [6], Monte-Carlo simulations were used to assess the performance of the WBE
model against the lawnmower model with the 12 parameters given in Table 1.
These simulations were run on MATLAB.

(a)

(b)

Figure 2: Number of Simulations vs Average Decision Making Time and
Number of Simulations vs Total Iterations to Locate the Survivor [6]

The results from the Monte Carlo simulations are presented in Figure 2. Even
though the decision making time of the WBE model is greater than the lawnmower
model, the WBE model requires fewer number of iterations to locate the
survivor. In [7], this WBE model was further developed by devising a set of
equations for assigning the weights to the environment coordinates for
prioritization. These equations are presented below:

W1 $\displaystyle=(\emph{W\textsubscript{4}}N^{3})+N^{2}+N+1$ (1) W2
$\displaystyle=(\emph{W\textsubscript{1}}-1)/N$ (2) W3
$\displaystyle=(\emph{W\textsubscript{1}}-N-1)/N^{2}$ (3) W5
$\displaystyle=(\emph{W\textsubscript{1}}N)+1$ (4)

Here, $N$ is the number of iterations required to move from the survivor’s
last known position to the boundary of the search environment,
$W\textsubscript{1}$ is the weight assigned to the coordinates lying along the
direction of the survivor’s heading, $W\textsubscript{2}$ and
$W\textsubscript{3}$ are the weights assigned to the left and right of the
survivor heading, and $W\textsubscript{4}$ is the weight allotted to
coordinates lying opposite to the survivor’s heading. The weight
$W\textsubscript{4}$ is assigned the least non-negative integer value of 1.
$W\textsubscript{5}$ is given the highest weight value, assigned to the last
known position of the survivor. These equations prevent the erratic movement
of the UAV from one quadrant to another during the search operation. This
erratic path may arise due to conflicting priorities of exploration that was
observed in earlier variants of the WBE model.

The equations given above were used to generate waypoints in an example 18 m x
18 m environment, where the survivor was last reported at the 9 m x 9 m mark,
moving in the south-east direction. Due to the differential assignment of
weights to the coordinates, a color gradient can be observed across the
quadrants in the Density of Weight Map, which translates to a variation in
exploration priority in the Priority of Waypoints Map in Figure 3. This
improved model was then used to locate survivors in multiple simulated
environments and survivor configurations using Gazebo and ROS [7]. The
resulting survivor search-times for the WBE (_T W_) and lawnmower (_T L_)
models are presented in Table 2. The WBE model clearly outperforms the
lawnmower model. The WBE model was then physically implemented on an off-the-
shelf UAV, running a MAVROS node on a Pixhawk 1 autopilot. The survivor search
times of the WBE model were compared to that of a standard lawnmower model, in
a 10 m x 10 m area with the survivor located at the the 5 m x 5 m mark. While
the lawnmower model required a total of 261 seconds to locate the survivor,
the WBE model took 149 seconds, an improvement of 75% [7].

(a)

(b)

Figure 3: Density of Weights and Priority of Exploration Maps[7] Table 2: Search Times for Lawn-Mower and Weight-Based Exploration [7] Environment Size ($m^{2}$) |  _V s_ (m/s) |  _T L_ (s) |  _T W_ (s)
---|---|---|---
18 x 18 | 0.6 | 624 | 173
20 x 20 | 0.6 | 669 | 213
18 x 18 | 0.3 | 600 | 63
20 x 20 | 0.3 | 663 | 66

Given the improvement in performance of the WBE model, we adapted the WBE
model to run on a team of UAVs, involved in locating multiple survivors in the
given environment.

##  3 Weight-Based Exploration for Multi-UAV Teams

The exploration model for multi-UAV teams comprises two modules: 1. Voronoi
Partitioning and 2. Weight-Based Exploration Model.

###  3.1 Voronoi Partitioning

Before the search operation begins, the entire environment space is divided
amongst the UAVs using the Voronoi Partitioning algorithm, presented below
(Equation 5). The starting locations of the UAVs are used as generator points
to create these partitions.

$R_{\textsubscript{k}}=\\{x\in X\>|\>d(x,k)\leq\>d(x,j)\>\forall\>k\neq j\\}$
(5)

Figure 4: Voronoi Partition of the Environment

In Equation 5, $R_{\textsubscript{k}}$ represents the subset of all points,
$x$ belonging to a space $X$, such that the distance to point $x$ from $k$,
$d(x,k)$, is less than the distance, $d(x,j)$, to any other point $j$, where
$j\neq k$.

Once the environment is partitioned, the UAVs explore only their respective
partitions, initially using the lawnmower model, and then the WBE model if
triggered by an observer. The Voronoi Partitions for a 20 m x 20 m environment
amongst a team of 5 UAVs is shown in Figure 4. In this example, the starting
positions of the 5 UAVs were (0, 0), (0, 19), (19, 0), (19, 19) and (9, 9).
The dimensions presented are for illustrative purposes and the speeds of the
UAVs are compatible to the dimension of the exploration space. These numbers
can be easily scaled up to represent real-life scenarios.

###  3.2 Weight-Based Exploration Model in Partitioned Search Space

Figure 5: Weight-Based Exploration with Multiple UAVs

Once the partitions have been generated, the UAVs commence their search for
the survivors. The diagrammatic representation is shown in Figure 5, where a
team of 5 UAVs are participating in the search for 5 survivors in their
respective colored partitions. The UAV in the blue partition, is triggered by
an on-ground observer (red circle), upon locating a survivor in its vicinity.
This UAV breaks off from the initial lawnmower model and heads to the highest
priority quadrant within its partition marked ’i’ and initiates the WBE model.
The UAV searches for the survivor only in its partition, while the rest of the
agents continue their lawnmower exploration, independently, unless triggered
by their observers.

In the following section, we describe the simulation environment and the
results of running the WBE model on multiple UAVs with varying survivor
configurations.

##  4 Simulation Environment and Results

We simulate the model on ROS using the Gazebo simulator, on a UAV team
comprising of 3DR Iris Quadcopters, running a MAVROS node on-board a Pixhawk 1
autopilot board. This configuration of the Quadcopter and autopilot is
selected as it closely resembles the physical hardware on which these models
will eventually be run.

(a)

(b)

Figure 6: ROS Simulation Environment and rqt_graph

Figure 6 shows the Gazebo environment with an example team of 5 UAVs that will
be performing the survivor search. Figure 6 also shows the rqt_graph for a 2
UAV team simulation, with the various UAV and survivor topics and nodes
generated during the simulation. A ROS observer_node alerts the UAVs of the
presence of a survivor in their vicinity.

Next, we present the results of the WBE model, with varying team
configurations, ranging from 3 to 5 UAVs. The environment surveyed by the UAVs
in each example is 20 m x 20 m. The survivor in each case moves linearly with
a velocity of 0.5 m/s in a prescribed direction. The UAVs investigate the
environment from a height of 2 m, with a field-of-view of $None$.

The 3-dimensional trajectory plot in each result section is accompanied by an
X-Y projection for a better view of the trajectories. Detailed variations in
the positions of both the UAVs and survivors are presented as well. The data
is plotted using the matplotlib [9] library for Python.

###  4.1 Three UAV Team

(a)

(b)

(c)

Figure 7: Trajectories and X-Y Projection for 3 UAVs and Survivors

Figure 8: Variation in Position for 3 UAVs and Survivors

We initialize 3 UAVs, located at (0, 0), (0, 19) and (19, 19). The survivors
are located at (5, 5), (5, 15) and (15, 15). As seen in Figure 7, UAV 1 and 2
are triggered by their observers due to the presence of survivors in their
vicinity. This causes UAV 1 and 2 to break off from the lawnmower exploration
and head to their survivors last known location and and initiate the WBE
model.

Due to the modular nature of the model, UAV 3 continues to perform the
lawnmower exploration, whereas UAVs 1 and 2 execute the WBE model until they
locate their survivor. Once the UAVs locate their survivor in their field-of-
view, they head back to their starting positions. The variation in the
positions for all the UAVs and survivors are presented in Figure 8.

###  4.2 Four UAV Team

(a)

(b)

(c)

Figure 9: Trajectories and X-Y Projection for 4 UAVs and Survivors

Figure 10: Variation in Position for 4 UAVs and Survivors

Figure 9 presents an aerial team with 4 UAVs, starting from (0, 0), (0, 19),
(19, 19) and (19, 0). Their corresponding survivors are located at (5, 5), (5,
15), (15, 15) and (15, 5). Observers alert UAVs 1, 3 and 4 of survivor’s in
their partitions. The UAVs initiate the weight-based exploration to locate
their moving survivors. As presented in earlier sections, the UAVs explore
only their own partitions.

UAV 2 continues with the lawnmower exploration, independent of the other UAVs,
since its observer did not detect any survivor in its vicinity. The variations
in the UAV and survivor positions during the simulation are presented in
Figure 10.

###  4.3 Five UAV Team

(a)

(b)

(c)

Figure 11: Trajectories and X-Y Projection for 5 UAVs and Survivors

Figure 12: Variation in Position for 5 UAVs and Survivors

A 5 UAV team involved in the search for 5 survivors in a 20 m x 20 m
environment is shown in Figure 11 and Figure 12. The UAVs start from (0, 0),
(0, 19), (19, 19), (19, 0) and (9, 9) respectively, with the corresponding
survivors located at (5, 5), (5, 15), (15, 15), (15, 5) and (8, 12).

Observers alert UAVs 1, 3 and 5 about the presence of survivors in their
partition. These UAVs initiate the weight-based exploration to locate their
survivors. UAVs 2 and 4 continue exploring their partitions using the
lawnmower model. Having successfully located their survivors using the WBE
model, the UAVs return to their starting location.

In this section, we have successfully demonstrated the scalability of the
weight-based model, when deployed on an aerial team comprising of multiple
UAVs. In each case, the model initially partitions the environment amongst the
UAVs, using their starting locations, and then initiates the exploration of
the environment. If an observer alerts the UAV of the presence of a survivor
in its vicinity, the UAV initiates the WBE model and begins locating the
survivor in its partition. Given the modular nature of the model, the
exploration model of a UAV remains unaffected by the exploration models of the
other UAVs in the team.

##  5 Conclusion and Future Work

In this paper we presented a development to the previously described Weight-
Based Exploration Model, to accommodate multi-UAV teams involved in search and
rescue operations. Such UAV teams can aid rescue efforts and significantly
reduce the time taken to investigate the given environment for survivors. In
this paper, we have presented results for the WBE model executed on aerial
teams with 3, 4 and 5 UAVs. However, with a sufficiently powerful system more
UAVs can be simulated simultaneously.

The model presented here explores the environment first by partitioning the
search space amongst the UAVs who then locate survivors in their respective
partitions. However, during physical implementation, UAVs are bound to have
varying battery levels which will dictate the size of the areas that they will
explore. We wish to develop the model so that factors such as battery levels
and endurance can be taken into account while generating the partitions.
Furthermore, agents can unexpectedly lose communication with each other or
with the ground station. In such cases the model should allow for the re-
partitioning of the environment amongst the remaining agents.

In the future, we will integrate the WBE model with a computer-vision
pipeline, trained on overhead images of humans to detect survivors. This would
enable a truly end-to-end autonomous solution, where the WBE model will be
used to locate survivors and then the computer-vision pipeline will identify
them and alert the search effort. We aim to physically test the multi-UAV
model integrated with the computer-vision pipeline, on off-the-shelf UAVs,
with the eventual goal of deploying multiple exploring agents in a real-life
flood scenario to aid rescue efforts.

## Acknowledgements

This work was partially supported by a Engineering and Physical Sciences
Research Council - Global Challenges Research Fund (EPSRC-GCRF), UK, multi-
institute grant (Grant Number: EP/P02839X/1).

## References

  * [1] A. Kashyap, D. Ghose, P. P. Menon, P. B. Sujit and K. Das,  ”UAV Aided Dynamic Routing of Resources in a Flood Scenario,”  International Conference on Unmanned Aircraft Systems (ICUAS), pp. 328-335, June 2019.
  * [2] T.M. Perks, A.J. Russell and A. R. Large,  ”Advances in flash flood monitoring using unmanned aerial vehicles (UAVs),”  Hydrology & Earth System Sciences, vol. 20, 2016.
  * [3] M. Silvagni, A. Tonoli, E. Zenerino and M. Chiaberge,  ”Multipurpose UAV for search and rescue operations in mountain avalanche events,”  Geomatics, Natural Hazards and Risk, pp. 18-33, 2007.
  * [4] P. Rudol and P. Doherty,  ”Human Body Detection and Geolocalization for UAV Search and Rescue Missions Using Color and Thermal Imagery,”  2008 IEEE Aerospace Conference, Big Sky, MT, pp. 1-8, 2008.
  * [5] D. Popescu, L. Ichim and F.Stoican,  ”Unmanned aerial vehicle systems for remote estimation of flooded areas based on complex image processing,”  Sensors, vol. 17, no. 3, pp. 446-470, 2017.
  * [6] R. Ravichandran, D. Ghose and K. Das,  ”UAV Based Survivor Search during Floods,”  International Conference on Unmanned Aircraft Systems (ICUAS), pp. 1407-1415, 2019.
  * [7] S.J. Shetty, R. Ravichandran, L.A. Tony, N.S. Abhinay, K. Das and D. Ghose,  ”Implementation of survivor detection strategies using drones,”  Unmanned Aerial Systems: Theoretical Foundation and Applications, in press.
  * [8] H. Hildmann and E. Kovacs,  ”Review: Using Unmanned Aerial Vehicles (UAVs) as Mobile Sensing Platforms (MSPs) for Disaster Response, Civil Security and Public Safety,”  MDPI AG Drones, vol. 3, no. 3, pages 59 - 82, 2019.
  * [9] J. D. Hunter,  ”Matplotlib: A 2D graphics environment”,  IEEE Computer Society Computing in Science & Engineering, vol. 9, no. 3, pp. 90-95, 2007.