\section{Introduction}
The success of deep learning in the recent decade relies on the availability of abundant annotated data for training. In real-world applications, the acquisition of sufficient training data can be difficult or even impossible. One technique to address the training data sparsity issue is transfer learning which aims to explore and transfer knowledge learned from the source domain to the target domain. There are usually more annotated data in the source domain than those in the target domain within which the task to solve resides. \textit{Zero-shot learning} \cite{wang2017zero,wang2017alternative,xian2019f} and \textit{domain adaptation} \cite{wang2019unifying,wang2020unsupervised} are two well-formulated transfer learning problems that have attracted much attention in the recent decade.

Traditional supervised learning methods have the limitation in that they can only recognize \textit{seen classes} (observed) for which labelled samples are available during training. In contrast, zero-shot learning aims to recognize samples from not only seen classes but also novel unseen classes (unobserved) for which no training samples are available during training \cite{wang2017zero}. To this end, side information of both seen and unseen classes from a \textit{source domain} (in contrast to the \textit{target domain} where the recognition task resides) is needed to model the between-class relations. In zero-shot visual recognition, class-level semantic attributes or word vectors are usually adopted as the side information in the source domain (i.e. semantic representation space) whilst the image classification task is addressed in the target domain (i.e. visual representation space) \cite{wang2017alternative}.

Domain adaptation is a technique aiming to mitigate the distribution discrepancy between source and target domains so that the knowledge learned from annotated source domain samples can be applied in the target domain \cite{wang2019unifying,wang2020unsupervised}. In this sense, zero-shot learning can be seen as a specific type of domain adaptation problem where the source domain provides per-class samples while the target domain provides training samples only for certain seen classes. In practice, however, existing domain adaptation approaches to unsupervised, supervised or semi-supervised domain adaptation in literature are not readily applicable to the current zero-shot learning problem setting. The underlying reason for this is twofold. On one hand, current zero-shot learning problems are constrained to have only class-level semantic representations in the source domain hence it is extremely difficult to learn sufficient knowledge for seen to unseen classes transfer \cite{wang2017alternative,wang2019unifying}. On the other hand, most domain adaptation approaches take advantage of a certain number of target domain samples (either labelled or not) during training which hinders its application in scenarios where such target domain samples are not available for all classes. To fill in this gap, zero-shot domain adaptation problems have been studied in \cite{peng2018zero,wang2019conditional,ishii2020partially} assuming that there are plenty of labelled samples in the source domain for all concerned classes, whilst labelled samples are available for only a subset of seen classes in the target domain. However, these studies restrict the capability of recognition in the unseen class space. As agreed in the zero-shot learning literature, generalized zero-shot learning, in which the recognition of both seen and unseen classes in the target domain is required, is more practically useful. In the same spirit, we take one step further in this paper to address a novel Generalized Zero-Shot Domain Adaptation (GZSDA) problem arising from many real-world applications.

In the scenario of image classification,  the relations of the novel generalized zero-shot domain adaptation problem with traditional zero-shot learning and unsupervised/supervised domain adaptation problems are illustrated in Table \ref{table:definition}.
The data imbalance across domains and classes poses more challenges to the GZSDA problem hence existing approaches to either zero-shot learning or domain adaptation tend to bias to either seen classes or the source domain.

To attack the data imbalance issue in the GZSDA problem, we present a novel Coupled Conditional Variational Autoencoder (CCVAE) solution by generating unseen data in the target domain to re-balance the training data. Specifically, the proposed CCVAE is able to transform source domain samples into associated projections within the target domain without loss of class information and vice versa. As a result, target domain samples of unseen classes can be generated from the corresponding source domain samples and used to train a classifier for all classes in a traditional supervised learning manner. The CCVAE works in the feature space rather than the image pixel space to reduce the complexity and challenge of image generation since the goal of GZSDA is image classification rather than image generation.
Following this outline, the contributions of this paper can be summarized as follows:
\begin{compactitem}
\item[--] a novel Generalized Zero-Shot Domain Adaptation (GZSDA) problem is formulated and studied for the first time extending the prior definitions of ZSDA problems in this domain from \cite{peng2018zero,wang2019conditional}; such a GZSDA problem is more realistic and also more challenging to solve.
\item[--] a novel Coupled Conditional Variational Autoencoder (CCVAE) model is proposed to address the GZSDA problem extending and outperforming the prior work of \cite{wang2019unifying}; the proposed CCVAE integrates the benefits of feature transformation and feature generation in one framework.
\item[--] a new multi-domain dataset arising from real-world applications is collected, annotated and released for domain adaptation research; it comprises of cross spectral image domains (i.e. dual-energy colour-mapped X-ray and regular colour photograph) which are not present in other datasets.
\item[--] extended experimentation is performed on two benchmark datasets in addition to a bespoke X-ray security checkpoint dataset to validate the effectiveness of the proposed CCVAE in GZSDA problems both against established benchamrks and in terms of real-world applicability; and also its superiority to a variety of contemporary methods in the field.
\end{compactitem}

\section{Related Work}\label{sec:related}
We review closely related work to our study from the perspective of zero-shot learning, domain adaptation and zero-shot domain adaptation and summarize the relationship to existing research topics and approaches in Table \ref{table:definition}.

\textbf{Domain Adaptation}\\
Existing domain adaptation approaches \cite{wang2019unifying,wang2020unsupervised} try to align the marginal distributions across source and target domains \cite{wang2020unsupervised} or to learn domain-invariant representations \cite{pei2018multi} so that labeling information available in the source domain can be explored to guide the learning of a classifier in the target domain or a latent common space.
Fine-grained class-wise adaptation across domains has been employed by promoting the alignment of conditional distributions as an additional constraint \cite{long2018conditional}.
For unsupervised domain adaptation, this can be implemented by pseudo-labeling \cite{chen2019progressive,wang2020unsupervised} given the access to unlabelled target domain samples for all classes. However, in the scenario of zero-shot domain adaptation, class-wise adaptation forms the primary challenge that we address in this work due to the lack of samples for unseen classes in the target domain regardless of labelled or unlabelled.

\begin{table*}[!thp]
    \centering

        \centering
        \caption[]{A comparison of generalized zero-shot domain adaptation with other related research topics.}
        \label{table:definition}
        \resizebox{0.9\textwidth}{!}
            \begin{tabular}{l|l|l|l}
                \hline
                \multirow{2}{*}{Research Problem} & \multicolumn{2}{c|}{Training} &Testing\\
                \cline{2-4}
                & Source & Target & Target \\ \hline
                \specialcell{Unsupervised Domain Adaptation\\ (UDA, \cite{wang2019unifying, wang2020unsupervised})} & labelled samples for all classes & \specialcell{unlabelled samples for all classes \\ (same as testing)} &  all classes \\ \hline
                \specialcell{Supervised Domain Adaptation\\ (SDA, \cite{motiian2017unified})} & labelled samples for all classes & \specialcell{labelled samples for all classes \\ (a small number)} & all classes\\ \hline
                \specialcell{Zero-Shot Learning (ZSL, \cite{wang2017zero})} & per-class representations for all classes & labelled samples for seen classes & unseen classes\\ \hline
                \specialcell{Generalized ZSL (GZSL, \cite{mishra2018generative})} & per-class representations for all classes & labelled samples for seen classes & all classes \\\hline
                \specialcell{Zero-Shot Domain Adaptation\\ (ZSDA, \cite{peng2018zero,wang2019conditional,ishii2019zero})} & \specialcell{unlabelled samples for seen classes and \\ labelled samples for unseen classes} & unlabelled samples for seen classes & unseen classes \\ \hline
                \textbf{\specialcell{Generalized Zero-Shot Domain\\ Adaptation (GZSDA, this paper)}} & labelled samples for all classes & labelled samples for seen classes & all classes \\
                \hline
            \end{tabular}%
        }%
    }
\end{table*}

\textbf{Zero-Shot Learning}\\
The most popular approaches to zero-shot learning are based on generative model such as Generative Adversarial Networks (GAN) \cite{xian2019f} and Varitional Autoencoders (VAE) \cite{mishra2018generative}. The generative models are trained to generate image features for specific classes given the corresponding class-level semantic representations (i.e. attributes or word vectors). Subsequently, a classifier can be trained using the combined real and generated data covering both seen and unseen classes.
On intrinsic limitation of ZSL is that the class-level attributes or word vectors in the source domain restrict the capability of representing the intra-class variability.
Alternatively, the class-level semantic representations in zero-shot learning can be replaced by more informative labelled samples in a source domain where such labelled samples are easy to collect and annotate. This leads to the very novel zero-shot learning problem we focus on in this paper. Existing zero-shot learning methods \cite{xian2019f,mishra2018generative} can not be directly applied to this problem since the source domain information appears in a different modality, whilst the ideas of generating synthetic image features for unseen classes will be employed and extended in our approach (Section \ref{sec:method}).

\textbf{Zero-Shot Domain Adaptation}\\
Very limited prior work has addressed zero-shot domain adaptation problems.
Yang et al. \cite{yang2015zero} attempted to address the issue where multiple source domains and the target domain are determined by a vector of continuous variables. Here there is no data available for the target domain but the corresponding control variables are known as prior knowledge. The transfer learning across source and target domains can be explicitly modelled by such control variables.
Similar assumptions are made by \cite{ishii2019zero} which assumes that prior knowledge of attribute information exists (e.g., time, angle, gender, age, etc.) characterizing the difference between source and target domains.
In contrast, we aim to address a more generic problem without the need of these control variables relating source and target domains.
The problem we try to address in this work is more similar to that in \cite{peng2018zero,wang2019conditional,ishii2020partially} which instead restrict the recognition to unseen classes. Moreover, paired task-irrelevant data (i.e. seen class data in this context) from source and target domains are required during training in \cite{peng2018zero} and \cite{wang2019conditional} and such correspondences may not exist in the labelled samples from seen classes in most real cases. We lift these restrictions and focus on the GZSDA problem without the need of either control variables or paired training samples.

\section{Method} \label{sec:method}
In this section, we first describe the problem settings of Generalized Zero-Shot Domain Adaptation and subsequently our proposed solution to this problem.

Our proposed framework consists of three steps as illustrated Figure \ref{fig:ccvae_framework} (full details in Section \ref{sec:ccvae}). Step one trains a feature extractor using all the labelled training data from both domains. In the second step, a Coupled Conditional Variational Autoencoder is trained using image features extracted in step one and will be used to generate synthetic features in the target domain. With the combination of these synthetic features and features extracted from real trainig images, a classifier is trained and used for image classification in the target domain.
\begin{figure}
    \centering
    {\includegraphics[width=0.8\textwidth]{./ccvae_diagram_v2.pdf}}
    {\caption{Our proposed Coupled Conditional Variational Autoencoder (CCVAE) framework.}
    \label{fig:ccvae_framework}}
\end{figure}

\subsection{Problem Formulation of Generalized Zero-Shot Domain Adaptation}

Given a labelled dataset $\mathcal{D}^s = \{(x^s_i,y^s_i)\}, i = 1,2,...,n^s$ from the source domain $\mathcal{S}$, $x^s_i$ represents the $i$-th training sample (e.g., an image in our case) in the source domain, and $y^s_i \in \mathcal{Y} = \{1,2,...,C\}$ denotes the corresponding label, and $C$ is the number classes. In the target domain, a labelled dataset $\mathcal{D}^{t}=\{(x_i^{t},y_i^{t})\},i=1,2,...,n^{t}$ from the target domain $\mathcal{T}$. $x_i^{t}$ and $y_i^{t} \in \mathcal{Y}^{seen}$ are the $i$-th labelled sample and its label respectively. Note that $\mathcal{Y}^{seen} \subset \mathcal{Y}$, that is, labelled samples are available for only a subset of classes in the target domain. The label space $\mathcal{Y} = \mathcal{Y}^{seen} \cup \mathcal{Y}^{unseen}$ is shared by source and target domains. The task is to classify any given new instance $x$ from the target domain by learning an inference model $y=f(x) \in \mathcal{Y}$.

\subsection{Feature Extraction}
The key of our approach to the GZSDA problem is the generation of synthetic data for unseen classes in the target domain. Given the challenge of image generation in the pixel space \cite{xian2019f}, we choose to generate image features since the ultimate goal is image classification rather than image generation. To this end, we extract image features in the first step. As shown in Figure \ref{fig:ccvae_framework}, a shared deep Convolutional Neural Network (CNN) model is employed to extract features for images from both source and target domains. We use ResNet50 \cite{he2016deep} pre-trained on the ImageNet \cite{deng2009imagenet} as the feature extractor for object images in our experiments and AlexNet \cite{krizhevsky2012imagenet} trained from scratch using $\mathcal{D}^s$ and $\mathcal{D}^t$ for digits data. We will use $\bm{x}$ and $\bm{\tilde{x}}$ to denote the real and synthetically generated image features in the following sections.

\subsection{Coupled Conditional Variational Autoencoder}
\label{sec:ccvae}
\textbf{Variational Autoencoder}\\
The Variational Autoencoder \cite{kingma2013auto} encodes an input feature $\bm{x}$ into a distribution $p_{\theta}(\bm{z})$ (approximated by $q_{\Phi}(\bm{z}|\bm{x})$) from which the latent encoding vector $\bm{z}$ can be sampled and subsequently fed into the decoder to reconstruct the input feature $\tilde{\bm{x}}$.  The decoder can be parameterized by $p_{\theta}(\bm{x}|\bm{z})$. According to \cite{kingma2013auto}, the objective function for the VAE can be written as follows:
\begin{equation}\label{eq:vaeLoss}
\mathcal{J}_{VAE}(\Phi,\theta;\bm{x}) = -D_{KL}(q_{\Phi}(\bm{z}|\bm{x}) || p_{\theta}(\bm{z})) + \mathbb{E}_{q_{\Phi}(\bm{z}|\bm{x})} [\log p_{\theta}(\bm{x}|\bm{z}) ]
\end{equation}
where  $D_{KL}(p||q)$ is the Kullback-Leibler (KL) divergence between two distributions $p$ and $q$. The VAE is trained by maximizing $\mathcal{L}(\Phi,\theta;\bm{x})$ which can be interpreted as minimizing the reconstruction error and the KL divergence.

\textbf{Conditional VAE}\\
Conditional VAE (CVAE) was first proposed in \cite{sohn2015learning}. It allows for modeling multiple modes (e.g., classes) in conditional distribution of the target variable (e.g., reconstructed input $\bm{\tilde{x}}$) given input $\bm{x}$ and the condition $c$. The objective function of CVAE can be adapted from Eq.(\ref{eq:vaeLoss}) as follows:
\begin{equation}\label{eq:cvaeLoss}
\mathcal{J}_{CVAE}(\Phi,\theta;\bm{x},c) = -D_{KL}(q_{\Phi}(\bm{z}|\bm{x},c) || p_{\theta}(\bm{z})) + \mathbb{E}_{q_{\Phi}(\bm{z}|\bm{x},c)} [\log p_{\theta}(\bm{x}|\bm{z},c) ]
\end{equation}
In existing CVAE models \cite{mishra2018generative,yan2016attribute2image}, both the encoder $q_{\Phi}(\bm{z}|\bm{x},c)$ and the decoder $p_{\theta}(\bm{x}|\bm{z},c)$ are conditioned on the class information (e.g., class-wise attributes). In ZSL problem \cite{mishra2018generative}, the CVAE is trained using target domain data in the condition of class-wise attributes from the source domain. Each training sample in the target domain has its corresponding attribute vector as the condition in the CVAE model. However, in our GZSDA problem information from the source domain is represented by labelled samples rather than class-level representations. In addition, the cross-domain correspondence in the sample level is unavailable. The traditional CVAE is not applicable to this problem.

\textbf{Coupled Conditional VAE}\\
The challenge of GZSDA problem originates from the missing labelled samples for unseen classes in the target domain. We attempt to learn a generative model based on CVAE to generate synthetic features for unseen classes in the target domain. The generated features are required to be both class discriminative and domain discriminative. To these ends, the decoder $p(\bm{x}|\bm{z},c)$ in the CVAE is conditioned on domain labels to generate domain discriminative features whilst the latent codes $\bm{z}$  need to be class discriminative to generate class discriminative features.

The proposed CCVAE is illustrated in Figure \ref{fig:ccvae_framework} (step 2). It is composed of a pair of CVAE for the source and target domains respectively. In our work, we model both the encoders and decoders using fully-connected neural networks. We force two CVAE to have identical architectures with shared weights. As a result, the model degrades into one coupled CVAE trained on both source and target domain data.

During training, the encoder takes the concatenation of a feature vector $\bm{x^s}/\bm{x^t}$ from the source/target domain and its corresponding domain label $c(\bm{x})= s/t$ (represented by a one-hot 2-dimensional vector) as the input to estimate the latent code distribution $q(\bm{z}|\bm{x},c) = \mathcal{N}(\mu_{\bm{x}},\Sigma_{\bm{x}})$. Subsequently, a latent code $\bm{z}$ is sampled from $\mathcal{N}(\mu_{\bm{x}},\Sigma_{\bm{x}})$ and fed into the decoder with the same domain label $s/t$ as the condition to reconstruct the input as $\bm{\tilde{x}^s}/\bm{\tilde{x}^t}$. On the other hand, the sampled latent code $\bm{z}$ can also be decoded with the condition of the other domain label $t/s$ to generate the synthetic feature in a different domain as $\bm{\tilde{x}^{st}}/\bm{\tilde{x}^{ts}}$.

The model is trained by feeding paired source and target domain samples $\{\bm{x}^s,\bm{x}^t\}$ randomly selected from the same class. The loss function to minimize can be formulated as:
\begin{equation}\label{eq:ccvaeLoss}
\begin{aligned}
\mathcal{L}_{CCVAE}(\Phi,\theta;\bm{x^s},\bm{x^t}) = & (\mathcal{L}_{recon} \big(\bm{x^s},\bm{\tilde{x}^s}) + \mathcal{L}_{recon} (\bm{x^t},\bm{\tilde{x}^t})\big) \\
&+  \big(\mathcal{L}_{cross\_recon} (\bm{x^s},\bm{\tilde{x}^{ts}}) + \mathcal{L}_{cross\_recon} (\bm{x^t},\bm{\tilde{x}^{st}})\big)\\
& +  \lambda D_{KL}\big(\mathcal{N}(\mu_{\bm{x}},\Sigma_{\bm{x}}) || \mathcal{N}(\bm{0},\bm{I})\big)
\end{aligned}
\end{equation}
The first terms measure the reconstruction errors for both source and target domain samples. The second terms measure the cross-domain reconstruction errors. Although the samples in the pair of $\{\bm{x^s},\bm{\tilde{x}^{ts}}\}$ or $\{\bm{x^t},\bm{\tilde{x}^{st}}\}$ are from the same class, they are not necessarily two views of the same image. To reduce the cross-domain reconstruction errors, the encoder has to preserve class information in the latent code space. As a result, the use of cross-domain reconstruction loss $\mathcal{L}_{cross\_recon}$ facilitate the model to generate class discriminative features across domains.
For those $\bm{x}^s$ belonging to unseen classes, there is no valid target domain samples $\bm{x}^t$ from the same class. We use dummy features in practice and exclude the loss terms involving these dummy features.
The third term aims to reduce the KL divergence between the distributions of the latent code and a normal distribution. It serves as a regularization term in the same way as in the VAE model.
$\lambda$ is a hyper-parameter balancing the KL divergence and reconstruction errors. We use L2 loss for both $\mathcal{L}_{recon}$ and $\mathcal{L}_{cross\_recon}$. The effectiveness of different terms in Eq.(\ref{eq:ccvaeLoss}) will be further investigated and discussed in Section \ref{sec:experiments}.

\subsection{Target Image Classification} \label{sec:step3}
Once the CCVAE is trained, we can use it to generate synthetic features by the cross-domain reconstruction pipelines. Specifically, given a feature vector $\bm{x}^s$ (or $\bm{x}^t$), the model can generate $\bm{\tilde{x}^{st}}$ (or $\bm{\tilde{x}^{ts}}$) which should have the same class label as the input. In this way, we are able to generate synthetic features for unseen classes in the target domain with the source domain samples. We use real data $\mathcal{D}^s$ and $\mathcal{D}^t$ together with synthetically generated features from them to train a unified neural network classifier for all classes and both domains. The classifier is then used to classify test images.

\section{Experiments and Results}\label{sec:experiments}
As the first attempt to address the GZSDA problem, we present a benchmark on GZSDA with extensive experiments on three datasets. We compare our proposed CCVAE with baseline methods and state-of-the-art methods for zero-shot learning \cite{wang2017zero,mishra2018generative,wang2019unifying} which have been adapted to the GZSDA problem.

\subsection{Dataset}
\textbf{BaggageXray-20}\\
This dataset is collected for the purpose of automatic object recognition in aviation security baggage screening \footnote{The dataset will be publicly and openly realeased including annotations, at permanently hosted DOI.}. Compared with the prevalence of regular RGB images, X-ray images are rarely available and have significantly different appearances as shown in Figure \ref{fig:xray}. The dataset consists of two domains (i.e. colour mapped X-ray images and regular visible band photographic images) covering 20 object classes. There are 4620 and  3444 images in the X-ray and regular domains, respectively. We use ResNet101 pretrained on the ImageNet to extract 2048-dim features for images from both domains. To simulate the GZSDA problem setting, the 20 classes were randomly split into two subsets: 10 classes as the seen classes and the rest 10 classes as the unseen classes. Five random seen/unseen class splits were used in our experiments to get statistics of the experimental results. Two domain adaptation tasks (i.e. regular $\to$ X-ray and X-ray $\to$ regular) were employed in the experiments. When a domain serves as the source domain, all images are used to form the labelled source dataset $\mathcal{D}^s$ whilst for the domain serving as the target domain we randomly reserve 50\% of the images from each class for testing and the rest 50\% from seen classes form the labelled target dataset $\mathcal{D}^t$.
\begin{figure}
    \centering
    {\includegraphics[width=0.8\textwidth]{./domain-xray-rgb.pdf}}
    {\caption{Sample images from the BaggageXray-20 dataset (upper: regular; bottom: X-ray).}
    \label{fig:xray}}
\end{figure}

\textbf{Office-Home}\\
Office-Home \cite{venkateswara2017deep} is a dataset commonly used for domain adaptation. It consists of four domains: artistic images (Art), Clipart, Product images and Real-World images. There are 65 object classes in each domain with a total number of 15,588 images. We extract ResNet50 features in our experiments and divide these 65 classes into 35 seen classes and 30 unseen classes randomly and generated 5 different splits for calculating the statistics of results. Given four domains, there could be 12 different domain adaptation tasks among which we report results with \textit{ClipArt} as the source domain in this paper. The training and test dataset creation strategy is identical to BaggageXray dataset.

\textbf{MNIST/Fashion-MNIST/EMNIST (\textit{X}MNIST)}\\
We follow previous works on ZSDA \cite{peng2018zero,wang2019conditional} and conducted experiments using MNIST \cite{lecun1998gradient}, Fashion-MNIST (FMNIST) \cite{xiao2017fashion} and EMNIST \cite{cohen2017emnist} (denoted collectively as \textit{X}MNIST). These three datasets contain 10, 10 and 26 classes respectively. In MNIST and FMNIST datasets, there are 6000 and 1000 images in the training and test subsets for each class, respectively. In the EMNIST dataset, the number of training and test images per class are 4800 and 800 respectively.
All these three datasets contain gray images of the same size of 28$\times$28. We consider these gray images as in the \textit{Gray} domain from which we create another two domains \textit{Color} and \textit{Negative}. The \textit{Color} domain images were created using the method proposed in \cite{ganin2015unsupervised}. Specifically, for a given image $I$, a random patch $P$ of the same size was cropped from a color image in BSDS500 \cite{arbelaez2010contour} and the color version of $I$ is created by $I_c = |I-P|$ for all channels. The \textit{Negative} domain images are obtained by $I_n = 255 - I$.
There are 6 different combinations of 3 domains to form 6 domain adaptation tasks among which we report the representative results of \textit{Gray} $\to$ \textit{Color}, \textit{Color} $\to$ \textit{Gray} and \textit{Negative} $\to$ \textit{Color}. In each domain adaptation task, we choose any two datasets as the seen and unseen classes respectively. As a result, for each domain adaptation task there can be 6 sub-tasks with different combinations of seen and unseen datasets. AlexNet \cite{krizhevsky2012imagenet} was trained from scratch using the training data $\mathcal{D}^s$ and $\mathcal{D}^t$ to extract features for a specific adaptation task.

\subsection{Implementation Details}
The proposed method was implemented in PyTorch\footnote{The code will be released.} \cite{paszke2019pytorch}. Both the encoder and decoder were three-layer fully-connected neural networks. For BaggageXray-20 and Office-Home datasets, the VAE share the same architecture of $2048-512-64-64-512-2048$ where 64 is the dimension of the latent code $\bm{z}$. For \textit{X}MNIST datasets, the VAE has an architecture of $512-128-32-32-128-512$ where 512 is the dimension of features extracted in the first step and 32 is the dimension of the latent space. The ReLU layer was employed after each fully-connected layer for non-linearity. For the classifier in step 3, we used a simple two-layer linear neural network (no hidden layer) across all experiments.
We used the Adam optimizer to train the CCVAE with the learning rate of $1e-3$ for a fixed number of epochs (50 epochs for BaggageXray20 and Office-Home, 10 epochs for MNIST datasets). The value of $\lambda$ was dynamically adjusted by a gradual warm-up strategy \cite{goyal2017accurate} from 0 up to 0.2 to facilitate the model training.
\subsection{Experimental Results}
We compare the performance of CCVAE with three baseline models, two ZSL methods (i.e. BiDiLEL\cite{wang2017zero} and CADA-VAE \cite{schonfeld2019generalized}) adapted for GZSDA and one existing GZSDA method LPP \cite{wang2019unifying}. We do not consider the ZSDA methods in \cite{peng2018zero} and \cite{wang2019conditional} because the former requires paired images and the latter is innately unable to discriminate seen and unseen classes. \textbf{Source Only} uses only source domain data and the 1 Nearest Neighbor (1NN) classifier. The \textbf{Baseline(1NN/NN)} uses training data from both domains (i.e. $\mathcal{D}^{s}$ and $\mathcal{D}^{t}$) and a simple classifier 1NN or Neural Networks (NN) with the same architecture as that used in step 3 of CCVAE. The ZSL methods \textbf{BiDiLEL} and \textbf{CADA-VAE} are used by taking the class means of source samples as the class-level semantic representations.

Following the generalized ZSL works \cite{xian2019f}, we report the mean per-class classification accuracy for seen and unseen classes and their harmony mean ($Acc_{seen}$, $Acc_{unseen}$ and $H$) except for \textit{X}MNIST datasets we only report $H$ due to the limited space. Our experimental results are shown in Tables \ref{table:xray}-\ref{table:digits}. It can be seen from Table \ref{table:xray} that the discrepancy of data distribution between regular and X-ray domains is significant as the \textbf{Source Only} method achieves low accuracy on both adaptation tasks (Table \ref{table:xray}). When labelled target samples from seen classes are employed, the two baseline methods achieve much better performance on seen classes at the sacrifice of accuracy on the unseen classes. The ZSL method BiDiLEL generally performs well on seen classes but poorly on unseen classes due to the notorious issue of overfitting to the seen classes in GZSL. The GZSL method CADA-VAE is able to balance the performance on seen and unseen classes and hence achieves higher values of $H$ but is still outperformed by LPP and our proposed CCVAE due to the fact that the traditional ZSL methods cannot take advantage of the source domain data properly. The proposed CCVAE achieves the highest $H$ values by improving the recognition accuracy of unseen classes whilst maintaining the accuracy of seen classes. The experimental results on the Office-Home dataset (Table \ref{table:officehome}) show similar phenomenon observed on the BaggageXray dataset. CCVAE outperforms other comparative methods on three tasks in terms of $Acc_{unseen}$ and $H$.

In Table \ref{table:digits}, $H$ values are reported for 18 sub-tasks for \textit{X}MNIST datasets. The task of $Color \to Gray$ is an easy one so that even using source data only can achieve as good performance as other more advanced methods except the ZSL methods which, again, suffer from the issue of overfitting to seen classes hence result in low $H$ values. In terms of the other two tasks (i.e. $Gray\to Color$ and $Neg\to Color$) reported in Table \ref{table:digits}, our proposed CCVAE significantly outperforms the comparative methods in 10 out of 12 sub-tasks especially when there are more unseen classes (i.e. EMNIST with 26 classes serving as the unseen dataset).

In summary, our proposed CCVAE is able to handle the GZSDA problem effectively in varying settings across different datasets and outperforms contemporary methods consistently and more significantly in the most challenging scenarios.

\begin{table*}[!htbp]
    \centering

        \centering
        \caption[]{Experimental results (\%) on BaggageXray dataset with 10 unseen classes (mean and standard error of the mean (SEM) over five different seen/unseen class splits are reported).}
        \label{table:xray}
        \resizebox{0.6\columnwidth}{!}
            \begin{tabular}{l| ccc| ccc}
                \hline
                \multirow{2}{*}{Method} & \multicolumn{3}{c|}{Regular $\to$ Xray} &\multicolumn{3}{c}{Xray $\to$ Regular}\\
                \cline{2-7}
                & $Acc_{seen}$ & $Acc_{unseen}$ &  $H$ & $Acc_{seen}$ & $Acc_{unseen}$ &  $H$  \\ \hline
                Source Only&$23.4\pm3.0$ & $20.4\pm3.0$ & $20.2\pm0.7$&$47.9\pm4.0$ & $42.7\pm4.0$ & $43.7\pm1.3$\\
                Baseline(1NN)&$75.0\pm2.4$ & $1.9\pm0.5$ & $3.6\pm0.9$&$93.8\pm1.5$ & $12.6\pm1.3$ & $22.1\pm2.0$\\
                Baseline(NN) &$84.3\pm1.9$&$2.5\pm0.4$&$4.8\pm0.7$&$\bf 95.0\pm0.8$&$20.4\pm3.8$&$32.6\pm5.5$\\
                BiDiLEL \cite{wang2017zero} &$80.8\pm2.2$ & $8.2\pm0.4$ & $14.9\pm0.7$&$94.6\pm0.9$ & $2.8\pm0.6$ & $5.5\pm1.1$\\
                CADA-VAE \cite{schonfeld2019generalized} & $47.3\pm6.7$& $\bf 24.3\pm5.0$& $31.6\pm4.3$& $73.0\pm7.3$& $26.1\pm4.1$& $38.3\pm4.9$\\
                LPP \cite{wang2019unifying}&$\bf 85.7\pm1.6$ & $10.2\pm1.1$ & $18.1\pm1.7$&$92.9\pm1.3$ & $30.4\pm2.4$ & $45.6\pm2.9$\\
                CCVAE&$70.4\pm1.8$&$23.3\pm3.0$&$\bf 34.5\pm3.2$&$87.4\pm0.8$&$\bf 44.5\pm3.5$&$\bf 58.6\pm3.3$\\
                \hline
            \end{tabular}%
    }
}
\end{table*}

\begin{table*}[!htbp]
    \centering

        \centering
        \caption[]{Experimental results (\%) on Office-Home dataset with 30 unseen classes (mean and standard error of the mean (SEM) over five different seen/unseen class splits are reported).}
        \label{table:officehome}
        \resizebox{0.9\columnwidth}{!}
            \begin{tabular}{l|ccc|ccc|ccc}
                \hline
                \multirow{2}{*}{Method} & \multicolumn{3}{c|}{ClipArt $\to$ Art} &\multicolumn{3}{c|}{ClipArt $\to$ Product}&\multicolumn{3}{c}{ClipArt $\to$ RealWorld}\\
                \cline{2-10}
                & $Acc_{seen}$ & $Acc_{unseen}$ &  $H$  & $Acc_{seen}$ & $Acc_{unseen}$ &  $H$ & $Acc_{seen}$ & $Acc_{unseen}$ &  $H$  \\ \hline
                Source Only&$48.0\pm0.7$&$44.2\pm0.9$&$46.0\pm0.1$&$55.6\pm0.8$&$57.2\pm0.9$&$56.3\pm0.1$&$59.3\pm1.2$&$59.3\pm1.4$&$59.2\pm0.1$\\
                Baseline(1NN)&$61.0\pm0.2$&$32.3\pm0.9$&$42.2\pm0.8$&$85.3\pm0.5$&$44.6\pm1.1$&$58.6\pm0.9$&$81.0\pm1.6$&$45.3\pm1.1$&$58.0\pm0.7$\\
                Baseline(NN)&$72.6\pm0.4$&$33.0\pm1.3$&$45.3\pm1.1$
                &$88.2\pm0.3$&$50.0\pm1.6$&$63.8\pm1.3$
                &$86.7\pm0.6$&$48.5\pm1.6$&$62.1\pm1.2$\\
                BiDiLEL \cite{wang2017zero} &$\bf 74.7\pm0.8$&$4.5\pm0.4$&$8.4\pm0.8$&$\bf 89.5\pm0.3$&$6.0\pm0.7$&$11.2\pm1.2$&$\bf 87.3\pm0.8$&$5.0\pm0.6$&$9.4\pm1.0$\\
                CADA-VAE \cite{schonfeld2019generalized} & $53.3\pm1.5$& $27.9\pm3.0$& $36.5\pm2.5$& $77.7\pm1.0$& $37.7\pm1.6$& $50.7\pm1.6$& $73.0\pm2.4$& $43.7\pm1.5$& $54.7\pm1.1$\\
                LPP \cite{wang2019unifying} &$72.1\pm0.8$&$48.1\pm0.8$&$57.7\pm0.7$&$87.6\pm0.4$&$58.8\pm1.5$&$70.3\pm1.1$&$86.0\pm0.9$&$59.4\pm2.0$&$70.1\pm1.2$\\
                CCVAE   &$69.2\pm0.8$&$\bf 51.8\pm0.5$&$\bf 59.2\pm0.3$
                        &$85.4\pm0.5$&$\bf 63.6\pm1.7$&$\bf 72.8\pm1.0$
                        &$83.3\pm0.7$&$\bf 65.1\pm1.8$&$\bf 73.0\pm0.9$\\
                \hline
            \end{tabular}%
        }
    }
\end{table*}

\begin{table*}[!htbp]
    \centering

        \centering
        \caption[]{Experimental results on \textit{X}MNIST datasets (mean and standard deviation of $H$ over five trials are reported).}
        \label{table:digits}
        \resizebox{0.7\columnwidth}{!}
            \begin{tabular}{l|l|cccccc}
                \hline
                \multirow{2}{*}{Domains} &\multirow{2}{*}{Method} & \multicolumn{2}{c}{Seen: MNIST} & \multicolumn{2}{c}{Seen: FMNIST} & \multicolumn{2}{c}{Seen: EMNIST}\\
                \cline{3-8}
                & &  FMNIST & EMNIST & MNIST & EMNIST & MNIST & FMNIST\\
                \hline
                \multirow{7}{*}{$Gray \to Color$}& Source Only & $7.3 \pm 0.1$ & $2.5 \pm 0.1$ & $6.1 \pm 0.2$ & $3.5 \pm 0.1$ & $2.2 \pm 0.1$ & $3.3 \pm 0.1$ \\
                & Baseline (1NN)& $46.3 \pm 0.6$ & $30.2 \pm 0.4$ & $38.2 \pm 0.5$ & $17.1 \pm 0.2$ & $51.8 \pm 0.7$ & $47.6 \pm 0.4$ \\

                & Baseline (NN) & $50.0\pm0.1$& $36.2\pm0.1$& $47.9\pm0.1$& $27.5\pm0.1$& $42.7\pm0.1$& $42.5\pm0.1$\\
                & BiDiLEL \cite{wang2017zero} & $39.9 \pm 2.0$ & $35.8 \pm 1.1$ & $30.6 \pm 1.9$ & $13.9 \pm 1.4$ & $52.8 \pm 1.9$ & $37.6 \pm 1.6$ \\
                & CADA-VAE \cite{schonfeld2019generalized} & $39.2\pm1.9$& $35.5\pm1.3$& $30.0\pm3.5$& $19.3\pm1.6$& $46.3\pm1.1$& $43.3\pm0.6$\\
                & LPP \cite{wang2019unifying} & $61.3 \pm 0.5$ & $43.5 \pm 0.6$ & $58.8 \pm 0.4$ & $39.1 \pm 0.4$ & $68.8 \pm 0.3$ & $\bf 58.8 \pm 0.2$ \\
                & CCVAE& $\bf 63.9\pm0.2$& $\bf 61.4\pm0.0$& $\bf 68.1\pm1.1$& $\bf 45.4\pm0.3$& $\bf 71.8\pm0.4$& $53.8\pm2.0$\\
                \hline
                \multirow{7}{*}{$Color \to Gray$}& Source Only & $86.5 \pm 0.6$ & $89.0 \pm 0.3$ & $87.1 \pm 0.6$ & $81.4 \pm 0.6$ & $89.6 \pm 0.3$ & $80.8 \pm 0.3$ \\
                & Baseline (1NN)& $85.6 \pm 0.5$ & $87.6 \pm 0.3$ & $90.9 \pm 0.2$ & $85.2 \pm 0.2$ & $90.7 \pm 0.1$ & $82.8 \pm 0.5$ \\

                & Baseline (NN) & $\bf 89.6\pm0.0$& $89.1\pm0.0$& $\bf 92.5\pm0.0$& $\bf 87.8\pm0.0$& $91.0\pm0.0$& $\bf 86.9\pm0.0$\\
                & BiDiLEL \cite{wang2017zero} & $29.0 \pm 2.6$ & $31.8 \pm 2.1$ & $18.7 \pm 2.9$ & $10.1 \pm 3.4$ & $53.7 \pm 4.3$ & $38.9 \pm 2.7$ \\
                & CADA-VAE \cite{schonfeld2019generalized} & $39.1\pm2.2$& $38.9\pm2.7$& $47.3\pm4.5$& $31.2\pm5.1$& $52.9\pm2.0$& $45.8\pm4.4$\\
                & LPP \cite{wang2019unifying} & $86.6 \pm 0.2$ & $80.3 \pm 0.2$ & $90.9 \pm 0.1$ & $81.3 \pm 0.3$ & $85.2 \pm 0.4$ & $81.5 \pm 0.3$ \\
                & CCVAE& $88.6\pm0.1$& $\bf 90.2\pm0.1$& $92.0\pm0.0$& $87.1\pm0.0$& $\bf 91.9\pm0.0$& $85.8\pm0.1$\\

                \hline
                \multirow{7}{*}{$Neg. \to Color$}& Source Only& $5.1 \pm 0.3$ & $1.9 \pm 0.1$ & $5.0 \pm 0.4$ & $1.4 \pm 0.0$ & $1.8 \pm 0.1$ & $2.7 \pm 0.0$  \\
                & Baseline (1NN) & $41.4 \pm 0.9$ & $28.8 \pm 0.6$ & $25.5 \pm 0.5$ & $9.6 \pm 0.1$ & $64.9 \pm 0.4$ & $46.9 \pm 1.1$ \\

                & Baseline (NN)& $49.7\pm0.1$& $36.7\pm0.2$& $44.5\pm0.1$& $23.9\pm0.2$& $55.9\pm0.0$& $40.8\pm0.1$\\
                & BiDiLEL \cite{wang2017zero} & $36.6 \pm 2.6$ & $31.3 \pm 1.1$ & $27.0 \pm 2.1$ & $13.5 \pm 0.8$ & $50.9 \pm 1.7$ & $36.6 \pm 1.7$  \\

                &CADA-VAE \cite{schonfeld2019generalized}& $39.3\pm1.7$& $34.5\pm1.8$& $26.7\pm1.4$& $18.4\pm4.6$& $42.7\pm1.1$& $41.0\pm0.9$\\
                & LPP \cite{wang2019unifying} & $68.1 \pm 0.6$ & $45.2 \pm 0.6$ & $54.1 \pm 0.8$ & $30.5 \pm 0.4$ & $69.2 \pm 0.2$ & $\bf 66.7 \pm 0.2$ \\
                & CCVAE & $\bf 70.6\pm0.4$& $\bf 63.2\pm0.5$& $\bf 68.4\pm1.1$& $\bf 46.9\pm0.9$& $\bf 72.4\pm1.0$& $62.0\pm1.4$\\
                \hline
            \end{tabular}%
        }
    }
\end{table*}

\section{Discussion and Conclusion}\label{sec:conclusion}
The key to GZSDA is to overcome the overfitting to seen classes so that ZSDA methods such as \cite{wang2019conditional} and generic generative models such as CycleGAN \cite{zhu2017unpaired} do not apply. LPP achieves this goal by mapping the source and target data into a common subspace of lower dimension with a unified linear projection. However, it only works well when the domain shift is not significant. Moreover, the solution to LPP involves the eigen-decomposition of a matrix relating to the number of training samples hence is not scalable.

The generative models (e.g., CADA-VAE and CCVAE) address the overfitting issue by generating synthetic data for the unseen classes. Our proposed CCVAE was inspired by CADA-VAE and has a similar framework but is essentially different from it. Firstly, CADA-VAE generates features from class-wise attribute vectors, restricting the intra-class variations of the synthetic features whilst CCVAE generates features from individual samples. Secondly, CADA-VAE employs domain-specific VAE for source and target domains whilst CCVAE uses a unified VAE to promote the preserving of class information in the latent space. As a result, to generate both domain and class discriminative features, the generative model in CADA-VAE is conditioned on class information whilst CCVAE is conditioned on domain information. Finally, CCVAE is used to generate not only target domain features but also source domain features to augment the real training data and a unified classifier is trained for both domains in CCVAE (Step 3).

In conclusion, our proposed CCVAE is an effective approach to the GZSDA problems. In addition, our proposed BaggageXray dataset provides a challenging test bed for future researches in GZSDA as well as other domain adaptation problems given the fact it arises from a real-world application in aviation security screening and the unique spectral X-ray imagery.

\section{Broader Impacts}
This work addresses a problem arising from real-world applications. The traditional ZSL problem setting has its intrinsic limitation in that the class-level semantic representations are insufficient to model the intra-class variability. In contrast, GZSDA provides a possibility of recognizing novel classes without the need of training data for these classes in the target domain. For example, in the X-ray based aviation security screening application, the definition of threat objects evolves rapidly since the terrorists never stop devising new weapons/explosive-devices. Automatic threat recognition algorithms used in the checkpoint can be updated conveniently without collecting X-ray data of new threat items which is usually the most time-consuming procedure \cite{wang2019approach}.

The other potential application is cross-scene (e.g., day and night, rainy and foggy) adaptation of perception algorithms in autonomous driving. One issue in the object detection for autonomous driving is the long-tail distribution problem. It is even difficult to handle this issue in adverse weather conditions  \cite{bijelic2018benchmarking} where GZSDA can be employed to transfer knowledge learned from daytime/sunny domain to night/rainy/foggy domain so as to avoid collecting the same amount of data for training.


\section{Introduction}
There are two types of quantum walks: continuous-time and discrete-time. In a continuous quantum walk, the evolution is usually determined by the adjacency matrix or the Laplacian matrix of the graph. Hence, certain properties of the walk, such as perfect state transfer, uniform mixing and fractional revival, translate into properties of the graph (see, for example, \cite{Godsil2012,Chan2013,Chan2018}). On the other hand, the transition matrix of a discrete quantum walk is a product of two non-commuting sparse unitary matrices, whose sizes usually equal the number of arcs of the graph. Moreover, the choice of these sparse matrices is not unique. Such freedom leads to various models of discrete quantum walks (see, for example, \cite{Aharonov2000,Szegedy2004,Kendon2003,Portugal2015}); however, the relation between graph properties and walk properties is less clear.

In this paper, we study a discrete quantum walk formalized by Kendon \cite{Kendon2003}. The transition matrix is a product of two matrices: the arc-reversal matrix, which maps an arc $(a, b)$ to the arc $(b, a)$, and a Grover coin matrix, which sends an arc $(a, b)$ to certain linear combination of the outgoing arcs of vertex $a$. Over the past few years, investigation of this model on specific families of graphs has received an increased attention. For example, Konno et al \cite{Konno2019} characterized the positive support of the $m$-th power of the transition matrix for regular graphs with girth greater than $2m-1$, and Yoshie \cite{Yoshie2019} characterized certain distance regular graphs on which this walk is periodic. Following their notion, we will refer to this walk as the \textsl{Grover walk}.

The graphs we consider in this paper are distance regular. Let $U$ be the transition matrix of a Grover walk. Then $U^2$ is the transition matrix of another discrete quantum walk defined by Szegedy \cite{Szegedy2004}. We show that if our graph $X$ is distance regular of diameter $d$ with invertible adjacency matrix, then
\[U^2 = \exp(t_1 S_1) \exp(t_2 S_2) \cdots (\exp(t_d S_d)),\]
where $S_i$ is the skew-adjacency matrix of the $i$-th distance digraph of the line digraph of $X$. Moreover, $S_i$ and $S_j$ commute. This reveals an interesting connection between discrete quantum walks on graphs and continuous quantum walks on oriented graphs.

\section{Grover Walks}
To gather more combinatorial insights into the Grover walk, we start this section with an alternative definition given by Godsil and Guo \cite{Godsil2010Guo}.

Throughout, let $X$ be a $k$-regular graph. We will replace each edge $\{a,b\}$ of $X$ by two arcs $(a,b)$ and $(b,a)$. The \textsl{line digraph} of $X$, denoted $\LD(X)$, is the digraph whose vertices are the arcs of $X$, and $(a,b)$ is adjacent to $(c,d)$ in $\LD(X)$ if $b=c$. Note that the adjacency in $\LD(X)$ is not a symmetric relation. In Figure \ref{fig_LDK3}, we illustrate $K_3$ and its the line digraph.
\begin{figure}[h]
	\centering
\begin{minipage}{0.5\textwidth}
\includegraphics[width=6cm]{K3}
\end{minipage}%
\begin{minipage}{0.5\textwidth}
\includegraphics[width=6cm]{LD}
\end{minipage}
\caption{A Planar Embedding of $K_4$}
\label{fig_LDK3}
\end{figure}

Let $A(\LD(X))$ denote the $01$-adjacency matrix of $\LD(X)$. Let $R$ denote the \textsl{arc-reversal matrix}, that is, the permutation matrix on the arcs that maps $(a,b)$ to $(b,a)$. We define the \textsl{transition matrix} of the Grover walk on $X$ to be
\[U:= \frac{2}{k} A(\LD(X)) -R.\]

For those who are familiar with the original description of the Grover walk, we show the equivalence between these two definition. To this end, we introduce two more matrices, $D_t$ and $D_h$, whose rows are indexed by the vertices of $X$, and columns by the arcs of $X$:
\[(D_t)_{u, ab} = \begin{cases}
1,\quad u=a\\
0,\quad \text{otherwise}
\end{cases}\]
and
\[(D_h)_{u, ab} = \begin{cases}
1,\quad u=b\\
0,\quad \text{otherwise}
\end{cases}\]
We sometimes refer to $D_t$ as the \textsl{tail-arc} incidence matrix, and $D_h$ the \textsl{head-arc} incidence matrix. It is not hard to verity the following.

\begin{lemma}\label{lem_props}
Let $X$ be a $k$-regular graph. The incidence matrices $D_t$ and $D_h$ satisfy the following identities.
\begin{enumerate}[(i)]
\item $D_t R = D_h$
\item $D_tD_t^T = D_hD_h^T=kI$
\item $D_tD_h^T = D_hD_t^T = A(X)$
\item $D_h^TD_t = A(\LD(X))$
\qed
\end{enumerate}
\end{lemma}

Hence,
\begin{align*}
U &= \frac{2}{k}A(\LD(X)) - R\\
&= \frac{2}{k} D_h^TD_t - R\\
&=R\left(\frac{2}{k}D_t^TD_t-I\right),
\end{align*}
where $\frac{2}{k}D_t^TD_t-I$ is precisely the coin matrix.

\section{Distances in digraphs}
Given a digraph $Y$, let $\dist_Y(a,b)$ denote the distance in $Y$ from $a$ to $b$. Note that in general $\dist_Y(a,b)\ne \dist_Y(b,a)$.

There is a simple relation between the distances in a graph and the distances in its line digraph.

\begin{lemma}\label{lem_dist}
Let $(a,b)$ and $(c,d)$ be two arcs of $X$. Then
\[\dist_{\LD(X)}((a,b),(c,d)) =\begin{cases}
\dist_X(b,c)-1,\quad \text{if }(a,b)=(c,d)\\
\dist_X(b,c)+1,\quad \text{otherwise}.
\end{cases}\]
\end{lemma}
\proof
The case where $(a,b)$ coincides with $(c,d)$ is trivial. Suppose $(a,b)$ is different from $(c,d)$. If there is a dipath $u_0=b, u_1, u_2, \cdots, u_m=c$ in $X$ from $b$ to $c$, then $(a, u_0), (u_0, u_1), (u_1,u_2),\cdots, (u_m, d)$ is a dipath in $\LD(X)$ from $(a,b)$ to $(c,d)$. This shows
\[\dist_{\LD(X)}((a, b), (c, d)) \le \dist_X(b,c)+1\]
Now, suppose  $(a, u_0), (u_0, u_1), (u_1,u_2),\cdots, (u_m, d)$ is a shortest dipath in $\LD(X)$ from $(a,b)$ to $(c,d)$. Then for any $i\ne j$, we have $u_i\ne u_j$, as otherwise we could have removed the portion from $(u_i, u_{i+1})$ to $(u_{j-1}, u_j)$ to get a shorter dipath. Hence, $u_0,u_1,u_2,\cdots,u_m$ is a dipath in $X$ from $b$ to $c$, and so
\[\dist_X(b,c)\ge \dist_{LD(X)}((a,b),(c,d))-1.\tag*{\sqr53}\]

\section{Distance regular graphs and their line digraphs}
A graph is \textsl{distance regular} if for any two vertices $u$ and $v$ at distance $\ell$, the number of vertices at distance $i$ from $u$ and distance $j$ from $v$ is a constant $p_{ij}^{\ell}$, which depends only on the distances $i$, $j$ and $\ell$. The parameters $p_{ij}^{\ell}$ are called the \textsl{intersection numbers}.

Suppose our graph $X$ is distance regular of diameter $d$. Let $A_i=A(X_i)$ denote the adjacency matrix of its $i$-th distance graph. It is well-known that
\[\{\seq{A}{0}{1}{d}\}\]
forms an association scheme (see, for example, \cite[Ch 12]{Godsil1993}). In particular, each eigenprojection $E_r$ of $A(X)$ is a linear combination of $\seq{A}{0}{1}{d}$:
\[E_r = \frac{1}{|V(X)|} \left(q_r(0) A_0 + q_r(1) A_1 +\cdots + q_r(d)A_d \right);\]
the parameters $q_r(i)$ are constants called the \textsl{dual eigenvalues}. Moreover, for any $i$ and $j$,
\[A_i A_j = \sum_{\ell=0}^d p_{ij}^{\ell} A_{\ell}.\]

We can generalize distance regularity to digraphs. A digraph $Y$ is \textsl{distance regular} if for any two vertices $u$ and $v$ with
$\dist_Y(u,v)=\ell$, the number of vertices $w$ such that $\dist_Y(u,w)=i$ and $\dist_Y(w,v)=j$ depends only on the distances $i$,$j$ and $\ell$; we denote this number by $m_{ij}^{\ell}$.

Now, we are ready to show that the line digraph of a distance regular graph is distance regular.

\begin{lemma}\label{lem_drdg}
Let $X$ be a distance regular graph. Let $Y=\LD(X)$ be its line digraph. Then $Y$ is a distance regular digraph. Moreover, for any $i$ and $j$, we have $m_{ij}^{\ell} = m_{ji}^{\ell}$.
\end{lemma}
\proof
Let $(a,b)$ and $(c,d)$ be two arcs of $X$. We count arcs $(x,y)$ that are at distance $i$ from $(a,b)$ and from which $(c,d)$ is at distance $j$.

We will prove the case where $i,j\ge 1$; the other cases follow from a similar argument. By Lemma \ref{lem_dist}, we are counting elements in the set
\[\Phi:=\{(x,y): \dist_X(b,x)=i-1, \dist_X(y, c)=j-1, \dist_X(x,y)=1\}.\]
On the other hand,
\[(A_{i-1} A_1 A_{j-1})_{bc} = \sum_x \sum_y (A_{i-1})_{bx} (A_1)_{xy} (A_{j-1})_{yc}=\@ifstar{\oldabs}{\oldabs*}{\Phi}.\]
Since $X$ is distance regular, there are intersection numbers $p_{1,j-1}^{m}$ and $p_{i-1,m-1}^{\ell}$ such that
\begin{align*}
A_{i-1} A_1 A_{j-1} &= A_{i-1} \sum_{m} p_{1,j-1}^{m} A_{m}\\
&=\sum_{\ell} \sum_{m} p_{i-1,m-1}^{\ell} p_{1,j-1}^{m} A_{\ell}.
\end{align*}
Therefore, the size of $\Phi$ is a constant $m_{ij}^{\ell}$ that depends only on $i$, $j$ and $\ell$. By Lemma \ref{lem_dist}, $\ell$ is determined by the distance from $(a,b)$ to $(c,d)$. Finally, since $A_{i-1}$ commutes with $A_{j-1}$, we have $m_{ij}^{\ell} = m_{ji}^{\ell}$.
\qed

Let $Y$ be a digraph. The $i$-th \textsl{distance digraph} of $Y$, denoted $Y_i$, has the same vertex set as $Y$, and vertex $a$ is adjacent to vertex $b$ in $Y_i$ if $\dist_Y(a,b)=i$.  One consequence of Lemma \ref{lem_drdg} is that the $01$-adjacency matrices of the distance digraphs of $\LD(X)$ commute, if $X$ is distance regular. Moreover, we have a formula for these adjacency matrices.

\begin{lemma}\label{lem_form}
Let $X$ be a distance regular graph. Let $A_i$ be the adjacency matrix of its $i$-th distance graph. Let $Y=\LD(X)$. Let $Y_i$ be the $i$-th distance digraph of $Y$. Then $A(Y_0)=I$, $A(Y_2) = D_h^T A_1 D_t-I$, and for $i= 1,3,\cdots,d+1$, $A(Y_i) = D_h^T A_{i-1} D_t $.
\qed
\end{lemma}

Using Lemma \ref{lem_form}, we can verify two properties of $A(Y_i)$, one of which we have already seen.
\begin{corollary}\label{cor_props}
Let $X$ be a distance regular graph. Let $Y=\LD(X)$. Let $Y_i$ be the $i$-th distance digraph of $Y$. Then the following statements hold.
\begin{enumerate}[(i)]
\item $A(Y_0), A(Y_1), \cdots,A(Y_{d+1})$ sum to $J$.
\item $Y$ is distance regular.
\end{enumerate}
\end{corollary}
\proof
We prove (i); the other statement follows similarly. By Lemma \ref{lem_form},
\[\sum_{i=0}^{d+1}A(Y_i) = I + (D_h^TA_0D_t) + (D_h^TA_1D_t-I) + \sum_{i=2}^dD_h^TA_{i-1}D_t\]
which reduces to $D_h^TJ D_t$. Since each column of $D_h$ or $D_t$ has exactly one non-zero entry, we have $D_h^TJD_t=J$.
\qed

Given a digraph $Y$, let $S(Y)$ denote its \textsl{skew-adjacency matrix}, that is,
\[S(Y) = A(Y) - A(Y)^T.\]
Note that $A(Y)$ and $A(Y)^T$ may not have disjoint supports, so the underlying oriented graph of $S(Y)$ may differ from $Y$. We illustrate this situation in Figure \ref{fig_supp}.

\begin{figure}[h]
	\centering
\begin{minipage}{0.5\textwidth}
\includegraphics[width=6cm]{LD}
\end{minipage}%
\begin{minipage}{0.5\textwidth}
\includegraphics[width=8cm]{LDnorev}
\end{minipage}
\caption{$\LD(K_3)$ and the underlying oriented graph of $S(\LD(K_3))$}
\label{fig_supp}
\end{figure}

Two properties of $S(Y_i)$ follow from Lemma \ref{lem_form} and Corollary \ref{cor_props}.
\begin{corollary}\label{cor_SY}
Let $X$ be a $k$-regular distance regular graph. Let $Y_i$ be the $i$-th distance digraph of $\LD(X)$. The following statements hold.
\begin{enumerate}[(i)]
\item $S(Y_0),S(Y_1),\cdots,S(Y_{d+1})$ are linearly dependent.
\item For $i,j=0,1,\cdots,d+1$,
\[S(Y_i) S(Y_j) = S(Y_j) S(Y_i).\tag*{\sqr53}\]
\end{enumerate}
\end{corollary}

\section{Spectral decomposition}
Let $X$ be a distance regular graph of diameter $d$. Let $U$ be the transition matrix of the Grover walk on $X$. In this section, we derive some properties of the eigenprojections of $U$.

We first cite a result from \cite{Zhan2019}.

\begin{theorem}\label{thm_spd}
Every non-real eigenvalue of $U$ comes from an eigenvalue of $A(X)$. More specifically, let $\lambda$ be an eigenvalue of $A(X)$ that is neither $k$ nor $-k$. Let $E_{\lambda}$ be the orthogonal projection onto the $\lambda$-eigenspace of $X$. Suppose $\lambda=k\cos(\theta)$ for some real number $\theta$. Then $e^{i\theta}$ is an eigenvalue of $U$ with eigenprojection
\[F_{\theta_+} = \frac{1}{2k \sin^2(\theta)} (D_t - e^{i\theta} D_h)^T E_{\lambda} (D_t - e^{-i\theta} D_h),\]
and $e^{-i\theta}$ is an eigenvalue of $U$ with eigenprojection
\[F_{\theta_-}=\frac{1}{2k\sin^2(\theta)} (D_t - e^{-i\theta} D_h)^T E_{\lambda} (D_t - e^{i\theta} D_h).\tag*{\sqr53}\]
\end{theorem}

As a consequence, for any non-real eigenvalue $e^{i\theta}$ of $U$, the difference $F_{\theta_+} - F_{\theta_-}$ is an imaginary scalar multiple of some real skew-symmetric matrix.

\begin{corollary}\label{cor_Fdiff}
Let $\lambda$ be an eigenvalue of $A(X)$ that is neither $k$ nor $-k$. Let $E_{\lambda}$ be the orthogonal projection onto the $\lambda$-eigenspace of $X$. Suppose $\lambda = k\cos(\theta)$ for some real number $\theta$. Let $F_{\theta_+}$ and $F_{\theta_-}$ be the $e^{i\theta}$-eigenprojection and the $e^{-i\theta}$-eigenprojection, respectively. Then $F_{\theta_+} - F_{\theta_-}$ is an imaginary scalar multiple of
\[D_t^TE_{\lambda} D_h - D_h^T E_{\lambda} D_t. \tag*{\sqr53}\]
\end{corollary}

We now fix a $\lambda$ that satisfies the condition in Corollary \ref{cor_Fdiff}, and set
\[S_{\lambda} := D_t^TE_{\lambda} D_h - D_h^T E_{\lambda} D_t.\]
We show that if $X$ is distance regular, then $S_{\lambda}$ is a linear combination of the skew adjacency matrices of the distance digraphs of $\LD(X)$.

\begin{lemma}\label{lem_span}
Let $X$ be a distance regular graph of diameter $d$. Let $Y = \LD(X)$. Let $Y_i$ be the $i$-th distance digraph of $Y$. Then
\[S_{\lambda} \in \mathrm{span} \{S(Y_1),S(Y_2),\cdots,S(Y_d)\}\]
\end{lemma}
\proof
Recall that $E_{\lambda}$ lies in the span of $\{A_i:i=0,1,\cdots,d\}$. By the formula
\[S_{\lambda} = D_t^TE_{\lambda} D_h - D_h^T E_{\lambda} D_t,\]
we see $S_{\lambda}$ lies in the span of $\{S(Y_i):i=0,1,\cdots,d+1\}$. Moreover, Corollary \ref{cor_SY} shows that $S(Y_0), S(Y_1),\cdots,S(Y_{d+1})$ are linearly dependent. Hence
\[S_{\lambda} \in \mathrm{span} \{S(Y_1),S(Y_2),\cdots,S(Y_d)\}.\tag*{\sqr53}\]

\section{Factoring $U^2$}
Let $X$ be a $k$-regular distance regular graph. Let $U$ be the transition matrix of the Grover walk on $X$. We can write the spectral decomposition of $U$ as
\[U = \sum_r e^{i\theta_r} F_r,\]
for some real numbers $\theta_r \in(-\pi, \pi]$. Thus
\[U^2 = \sum_r e^{2i\theta_r} F_r.\]
From Theorem \ref{thm_spd}, we see that if $\theta_r\in(0,\pi)$, then $k\cos (\theta)$ is an eigenvalue of $A(X)$.

Now, we assume in addition that $A(X)$ is invertible. It follows that $\pm i$ are not eigenvalues of $U$, that is, $-1$ is not an eigenvalue of $U^2$. Hence, we have
\[U^2=  \exp(iH),\]
where
\[H = 2 \sum_{r: 0<\theta_r<\pi} (F_r- \comp{F_r}).\]
Our discussion in the last section shows that $H$ is a linear combination of the skew-adjacency matrices of the distance digraphs of $\LD(X)$.

\begin{theorem}
Let $X$ be a distance regular graph with diameter $d$. Let $U$ be the transition matrix of the Grover walk on $X$. Let $Y_i$ be the $i$-th distance digraph of $\LD(X)$. If $A(X)$ is invertible, then there are real scalars $\seq{t}{1}{2}{d}$ such that
\[U^2 = \exp(t_1S(Y_1)) \exp(t_1 S(Y_2))\cdots \exp(t_d S(Y_d)).\]
\end{theorem}
\proof
We have
\[U^2 = \exp(iH)\]
where
\[H = 2 \sum_{r: 0<\theta_r<\pi} (F_r- \comp{F_r}).\]
By Lemma \ref{lem_span}, $H$ is a linear combination of $S(Y_1), S(Y_2),\cdots,S(Y_d)$. By Corollary \ref{cor_SY}, these skew-adjacency matrices commute, so we can factor $U^2$ into the desired form.
\qed

If we rewrite $\exp(t_iS(Y))$ in the above theorem as $\exp(i t_i (iS(Y_i)))$, then we have the transition matrix of a continuous quantum walk on an oriented graph, evaluated at time $t_i$. Thus, for a distance regular graph with diameter $d$ and invertible adjacency matrix, the Grover walk on it factors into at most $d$ continuous quantum walks on the distance digraphs of $\LD(X)$. In particular, a discrete quantum walk on $K_n$ is equivalent to a continuous quantum walk on its line digraph.

\begin{corollary}
Let $U$ be the Grover walk on $K_n$. Then there is a real scalar $t$ such that
\[U^2 = \exp(t S(\LD(K_n))).\tag*{\sqr53}\]
\end{corollary}

The Grover walk on an invertible strongly regular graph factors into at most two continuous quantum walks. For the Petersen graph $P$, the factors of $U^2$ are continuous quantum walks on the oriented graphs shown in Figure \ref{fig_LDPet}.

\begin{figure}[h]
	\centering
\begin{minipage}{0.5\textwidth}
\includegraphics[width=6cm]{LDPet}
\end{minipage}%
\begin{minipage}{0.5\textwidth}
\includegraphics[width=6cm]{LDPet2}
\end{minipage}
\caption{Underlying oriented graphs of $S(\LD(P))$ and $S(\LD(P)_2)$}
\label{fig_LDPet}
\end{figure}

Finally, we remark here that not all $d$ distance digraphs may show up in the factorization. For example, if $U$ is the Grover walk of the $3$-cube $Q_3$, and $Y_2$ is the second distance digraph of $\LD(Q_3)$, then there is a scalar $t$ such that $U^2 = \exp(t S(Y_2))$.

\section{Future work}
In this paper, we showed a connection between a discrete quantum walk on an invertible distance regular graph and some continuous quantum walks on the distance digraphs of its line digraph. It will be interesting to translate properties on the discrete side, such as perfect state transfer, into properties on the continuous side, and vice versa.

Our factorization relies on the ``lift" from the eigenspaces of the graph to the eigenspaces of the transition matrix, as stated in Theorem \ref{thm_spd}. With a similar argument, we can factor discrete quantum walks on other graphs with nice eigenspaces. We plan to work on this problem for Cayley graphs.

\section{Acknowledgment}
The author would like to thank Ada Chan for her inspiring discussion.

\bibliographystyle{amsplain}


\section{Introduction}

When a group of mobile agents, such as service robots or video game characters, operates in the shared environment one of the key challenges they face is arriving at their target locations while avoiding collisions with the obstacles and each other. In general two approaches to solve this problem, i.e. multi-agent navigation, can be identified: centralized and decentralized.

The centralized approaches rely on a central planner that constructs a joint multi-agent plan utilizing the full knowledge of the agents' states. When the plan is constructed each agent follows it and if the execution is perfect or near-perfect collisions are guaranteed not to happen. Centralized planning can be carried out in such a way that the joint plan is guaranteed to be optimal\footnote{Typically, optimal centralized planers rely on the discretization of the workspace thus the solutions they provide are optimal w.r.t. the used space/time discretization.}. Non-optimal yet computationally efficient centralized planners do exist as well.

\begin{figure}[t]
    \centering
    \includegraphics[width=0.55\linewidth]{intro.pdf}
    \caption{An example of possible deadlock in the vicinity of narrow passage.}
    \label{fig:intro}
\end{figure}

Decentralized approaches do not rely on the central planner. Instead each agent plans its trajectory individually and resolves conflicts at the execution stage, i.e. an agent reactively avoids collisions relying on the local observations and/or communication. Such approach naturally fits to numerous scenarios with heterogeneous agents, limited communication/visibility etc. It also scales well to large number of agents however it does not guarantee optimality. Moreover, no guarantees that each agent will reach its goal can be provided. The main reason for that is that each agent is egoistic in pursuing its goal this can lead to a deadlock. Consider a scenario shown on \figurename~\ref{fig:intro} when agents have to swap sides using a tight passage connecting the rooms. If they approach the passage nearly at the same time they will be stuck. For all of them to safely move through at least one of the agents has to step back and let other agent go. Thus, some form of cooperative behaviour (which is explicitly or implicitly centralized) is vital for accomplishing the mission.

In this work we present an algorithmic pipeline that combines decentralized and centralized approaches to multi-agent navigation. Within this pipeline each agent constructs and follows its path individually. When a pattern leading to potential deadlock is detected a locally-confined multi-agent path finding is invoked, i.e. agents that appear to be involved in a deadlock are identified and a joint safe plan for these agents is constructed. After executing this plan all involved agents switch back to the decentralized mode. We use \textsc{Theta*}~\cite{daniel2010theta}, \textsc{ORCA*}~\cite{van2011reciprocal}, \textsc{Push and Rotate}~\cite{de2014push} for individual path planing, local collision avoidance and multi-agent path finding respectively. Meanwhile, the suggested pipeline is not limited to these algorithms and other algorithmic components may be used instead of the aforementioned methods as well. We extensively study the suggested approach in simulation and show that the suggested approach leads to much better results compared to fully decentralized method that does not utilize multi-agent path finding.

\section{Related Work}

The approaches to multi-agent navigation can be roughly divided into the two groups: centralized and decentralized \cite{xuan2002multi}. The centralized approaches assume that a central planner is available that possess all the information about the agents and the environment and plans for a joint collision-free solution. Naive application of such search algorithms as \textsc{A*}~\cite{hart1968formal}, i.e. planning in the full joint configuration space, which is a cardinal product of the individual configuration spaces, is impractical as the search space grows exponentially in the number of agents. However there exist techniques that greatly reduce the search effort, such as subdimensional expansion~\cite{wagner2015subdimensional}, conflict-based search~\cite{sharon2015conflict} to name a few. The latter technique is very popular nowadays and there exist a large variety of CBS planners that improve the performance of the original algorithm or extend it in numerous ways, e.g. in~\cite{barer2014suboptimal} a sub-optimal version of \textsc{CBS} is presented, the work~\cite{andreychuk2019multi} planning in continuous time is considered etc. All these algorithms are designed with the aim of minimizing cost of the result solution. At the same time, when large cost of the solution is acceptable one can use extremely fast polynomial algorithms, e.g. \textsc{Push and Rotate}~\cite{de2014push}. Finally, a prioritized approach~\cite{vcap2015prioritized, yakovlev2019prioritized} is also a common choice in numerous cases. Prioritized planners are fast and typically provide solutions of reasonably low cost (very close to optimal in many cases). Their main drawback is that they are incomplete in general.

The decentralized approaches do not rely on the full knowledge of the agents' states and the environment and assume that each agent utilizes only the information available to it locally~\cite{dimarogonas2007decentralized, xuan2002multi}. One of the common ways to solve multi-agent navigation problem under a decentralized setting is to plan individual paths for each agent, e.g. by a heuristic search algorithm such as \textsc{Dijkstra}~\cite{dijkstra1959note}, \textsc{A*}~\cite{hart1968formal}, \textsc{Theta*}~\cite{daniel2010theta}, and then let all agent follow their paths. To avoid collisions algorithms of the ORCA-family are typically used~\cite{van2011reciprocal, snape2014smooth, snape2010smooth, alonso2013optimal}. Another techniques that rely on buffered Voronoi cells~\cite{zhou2017fast} or various reinforcement learning techniques~\cite{chen2017decentralized, long2018towards} to avoid collisions can also be employed. In general decentralized approaches are prone to deadlocks and do not guarantee that each agent will reach its destination.

In this work we combine both decentralized and centralized methods into a coherent multi-agent navigation pipeline striving to combine the best of two worlds: flexibility and scalability of the decentralized navigation and completeness of the centralized planning.

\section{Problem Statement}

Consider a set of $n$ agents moving through 2D workspace, $W \in \mathds{R}^2$, composed of the free space and the obstacles: $W=W_{free} \cup O$. Each obstacle, $o \in O$, is a bounded subset in $W$. Every agent, $i$, is modelled as a disk of radius $r_i$. The state of an agent is defined by its position and velocity: $(\mathbf{p}_i, \mathbf{V}_i)$. The latter is bounded:  $||\mathbf{V}_i|| \leq V_i^{max} \in \mathds{R}^+$, i.e. maximum speed of each agent is given.

Let $T=0, \Delta t, 2 \Delta t, ...$ be the discrete time ($\Delta t = const$). For the sake of simplicity assume that $\Delta t = 1$, thus the timeline is $T=0, 1, 2, ...$. At each moment of time an agent can either move or wait (the latter can be considered as moving with the velocity being zero). We neglect inertial effects and assume that an agent moves from one location to the other following a straight line defined by its current velocity. We also assume perfect localization and execution.

At each time step agent knows \emph{i}) its own position, \emph{ii}) positions of all the obstacles, \emph{iii}) states of the neighboring agents. The latter are the agents that are located withing a radius $R_i$. This radius models a communication range of an agent, i.e. we assume that an agent $i$ can communicate with other neighboring agents and acquire any information from them. For the sake of exposition we will refer to this range as to the visibility range further on.

A spatio-temporal path for an agent is, formally, a mapping: $\pi: T \rightarrow W_{free}$. It can also be represented as a sequence of agent's locations at each time step: $\pi=\{\pi_0, \pi_1, ...\}$. In this work we are interested in converging paths, i.e. paths by which an agent reaches a particular location and never moves away from it. This can be formulated as follows: $\exists k \in T: \pi_{k+t} = \pi_k \: \forall t>1$.

The path for the agent $i$ is valid w.r.t. velocity constraints and static obstacles \emph{iff} the following conditions hold:
\begin{equation*}
  \begin{split}
        ||\pi_{t+1} - \pi_{t} || \leq V_i^{max} \Delta t, \; \forall t \in \overline{0,k-1}
        \\
        \rho (\pi_t, o) > r_i, \; \forall o \in O, \; \forall t \in \overline{0,k},
    \end{split}
\end{equation*}

where $\rho (\pi_t, o)$ stands for the distanceto the closest obstacle.

Consider now the two paths for distinct agents: $\pi^i, \pi^j$. They are called conflict-free if they are valid and the agents following them never collide, that is:
\begin{equation*}
        ||\pi^i_{t} - \pi^j_{t'} || \leq r_i + r_j, \; \forall t \in \overline{0,k^i}, t' \in \overline{0,k^j}.
\end{equation*}

The set of paths $\Pi = \{\pi^1, ..., \pi^n\}$, one for each agent, is conflict-free if any pair of paths forming this set is conflict-free.

\textbf{The problem} we are considering in this paper can now be formulated as follows. Given $n$ start and goal locations at each time step for each agent choose a velocity s.t. the agent reaches the goal at some time step, the agent never collides with static obstacles and other agents, that is the resultant set of paths $\Pi$ is conflict-free.

\section{Method}
Our approach relies on three algorithmic components: individual planning, path following with collision avoidance and locally-confined multi-agent path finding in case of potential deadlocks. We will now describe all these components.

\subsection{Individual Path Finding}

\begin{figure}[t]
    \centering
    \includegraphics[width=0.55\textwidth]{trajectory.pdf}
    \caption{Finding a path for an individual agent: a) the workspace of an agent; b) tesselation of the workspace into the grid and two paths on that grid: the one that was found by \textsc{A*} (in orange) and the one that was found by \textsc{Theta*} (in blue). We use \textsc{Theta*} paths in this work.}
    \label{fig:traj}
\end{figure}

To find a valid path for an agent that avoids static obstacles we reduce path planning problem to graph search. We employ regular square grids~\cite{yap2002grid} as the discretized workspace representation as they are easy-to-construct and informative graph models widely used for navigation purposes. To create a grid we tessellate the workspace into the square cells and mark each cell either blocked or traversable depending on whether this cell overlaps with any of the obstacle or not (see~\figurename~\ref{fig:traj} on the right). To find a path on the grid we utilize \textsc{Theta*}~\cite{daniel2010theta} algorithm. It's a heuristic search algorithm of the \textsc{A*} family which augments the edge set of the graph on-the-fly by allowing any-angle moves, i.e. the moves between non-adjacent vertices, conditioned that such moves do not lead to the collisions with the obstacles. As a result, paths found by \textsc{Theta*} are typically shorter than the ones found by \textsc{A*} and contain less waypoints. The difference between these two types of paths is clearly visible on~\figurename~\ref{fig:traj}. Both \textsc{Theta*} and \textsc{A*} paths are collision-free, while the former contains 7 intermediate waypoints and the latter -- only 2 of them.

\subsection{Path Following with Collision Avoidance.}

Having the individual paths for all agent the considered multi-agent navigation problem can be naively solved as follows. At each time step an agent chooses such a velocity that it is directed towards the next waypoint on a path and its magnitude is maximal. In other words, agents move along the constructed paths as fast as they can without any temporal waits and spatial deviations. Obviously, such an approach leads to numerous collisions in practice. Instead, we rely on a more advanced method called Optimal Reciprocal Collision Avoidance (\textsc{ORCA})~\cite{van2011reciprocal}. This method is designed to move an agent safely towards its local goal (current waypoint of a path) by reactively adjusting the velocity profile at each timestep. When choosing a velocity \textsc{ORCA} relies on local observations: only other moving agents that are located within a visibility range and static obstacles are taken into account. We tie together individual path planning and path following with collision avoidance in the following fashion.

\begin{figure}[t]
    \centering
    \includegraphics[width=\textwidth]{currgoal.pdf}
    \caption{Goal-setting for \textsc{ORCA}. (a) Waypoint $A$ is the local goal of the agent 1. (b) The agent 1 deviates from the original trajectory in order to avoid collision with the agent 2, the line-of-sight to the local goal is lost, re-planning is triggered and the new waypoint, $C$, is added to the path, it becomes the current local goal. (c) $C$ is reached, next local goal is $A$. (d) The agent safely moves towards $A$ without any deviation as no other moving agents interfere with its plan.}
    \label{fig:currgoal}
\end{figure}

The waypoints that comprise an individual path (the one found by \textsc{Theta*}) form a sequence of the local goals for \textsc{ORCA} and an agent always moves towards its current local goal until the latter is reached. When it happens next waypoint from the path becomes the local goal and \textsc{ORCA} is re-invoked. It is noteworthy, that when an agent moves to the current goal it may significantly deviate from the original path's segment (due to other moving agents forcing \textsc{ORCA} to do so). Thus, it may appear that the local goal can no longer be reached via the straight-line segment, which is a crucial condition for ORCA to operate appropriately. We detect such patterns and trigger re-planning from the current agent's position to the local goal with \textsc{Theta*}. New waypoints are added to sequence of the local goals as a result. The condition that there is a visible connection between any pair of waypoints now holds and ORCA continues. An illustration of the overall process is presented in~\figurename~\ref{fig:currgoal}.

\subsection{Multi-agent Path Finding for Avoiding the Deadlocks.}

Path planning and collision avoidance mechanisms described so far can be attributed as non-cooperative, i.e. each agent pursues its own goal and does not take the goals of other agents into account. In general this can lead to deadlocks. A typical scenario when such a deadlock occurs is depicted on \figurename~\ref{fig:area} on the left. Here all four agents have to come through the tight passage nearly at the same time. In such case \textsc{ORCA} is forced to set the velocity of each agent to zero to avoid the collisions. Thus, no agent is moving and a deadlock occurs. To avoid this we include a multi-agent path finding (MAPF) algorithm into the navigation pipeline with the aim of building a set of locally coordinated collision-free paths. Conceptually, when an agent detects a pattern that leads to a potential deadlock it switches to a coordinated path planning mode and forces its neighboring agents to do so. Upon entering this mode involved agents create a joint conflict-free plan and execute it. After they switch back to the independent execution mode.

\begin{figure}[t]
    \centering
    \includegraphics[width=0.6\textwidth]{local.pdf}
    \caption{Switching to coordinated mode. (a) Agent 1 detects its local goal, $A$, and 3 other agents within its visibility zone. (b) Based on the current positions and individual paths of agents 1-4 a local grid-map for multi-agent path-finding is identified as well as start and goal locations for each agent.}
    \label{fig:area}
\end{figure}

Switching to the coordinated mode is triggered if both local goal $A$ and $k$ other agents appear in the visibility range of some agent (here $k$ is the predefined threshold set up by the user). The latter forms a list of coordinated agents that include: itself, its neighboring agents and their neighboring agents as well. All these agents now share the information about their current states (positions and velocities) and individual paths with each other. Thus each agent constructs the same information model and uses it for operation, so no explicit centralized controller is introduced.

Based on the current positions of the agents, the boundaries of the area in which the joint collision-free plan will be built are estimated. This is done as follows. The minimum and maximum $x$- and $y$-positions across all agents are identified. These four coordinates define a square which is inflated by a visibility radius of the agent that has initiated switching to the coordinated mode. This square is translated to the grid which was originally used for the individual path planning. The resulting grid now becomes a local map for multi-agent path finding (it is depicted on~\figurename~\ref{fig:area}b in grey). It might appear that two or more coordinated planning areas are separately constructed by different groups of agents close to each other. In this case those areas are combined into a single one and all agents become members of a single coordinated group.

After the grid map for multi-agent path finding is constructed each agent chooses its MAPF start and MAPF goal on that grid. The start cell is the one closest to the current location of the agent. If it coincides with the start of another agent or it is blocked by an obstacle a breadth-first search graph traversal is invoked from this cell to find a close un-blocked position which becomes a start. Goal locations are identified in the similar way. First, a current local goal (path's waypoint) is identified. If it coincides with $A$ the next waypoint is chosen. If the selected waypoint lies inside the planning area then the cell which contains it become the MAPF goal. If the waypoint is outside an area, i.e. at least its $x$- or $y$- coordinate is greater/less than the corresponding maximum/minimum values of the planning area, then this coordinate is replaced by the maximum or minimum value of the corresponding coordinate.

After the start and goal positions of the agents are fixed, an appropriate MAPF solver is invoked to obtain a solution, i.e. a set of sequences of moves between the grid cells and, possibly, wait actions, -- one sequence per each agent. For the sake of simplicity we assume that all MAPF actions, i.e. move and wait, are of the uniform duration. This duration is chosen in such a way that the constraints on the agents' maximum moving speed are not violated. In this work we utilize \textsc{Push and Rotate}~\cite{de2014push} for multi-agent path planning algorithm as it is very fast and scales well to large number of agents. We did not choose an optimal solver, such as \textsc{CBS}~\cite{sharon2015conflict}, because of its high computational budget. Using a prioritized planner is also not an option as prioritized MAPF solvers do not guarantee completeness.

When a MAPF problem is solved each agent starts moving towards its chosen MAPF-start position on a grid (with ORCA collision avoidance activated). When all agents are at their start positions synchronous execution of the plan begins. At this stage no collisions are guaranteed to happen (assuming perfect execution) so ORCA is not used. When all agent reach their MAPF-goals they switch back to the individual mode, i.e. continue path following to their next waypoint on a global path with \textsc{ORCA} as described in previous section.

In case some agent, $i$, which is not involved in the plan execution, gets inside the boundaries of the planning area and interferes with the coordinated agents, i.e. this agent appears in any coordinated agent's visibility range, the execution of the coordinated plan is stopped, the agent $i$ is added to the list of coordinated agents and the plan is recomputed.

Similarly, if an agent $i$, which is involved in the plan execution, gets inside into the visibility zone of an agent $j$, which is also involved in the execution of plan, but belongs to another group of coordinated agents, then these two coordinated groups are merged and re-planning is triggered.

\section{Experimental Evaluation}

\begin{figure}[t]
    \centering
    \begin{subfigure}[b]{0.3\textwidth}
        \includegraphics[width=\textwidth]{gap.png}
        \label{fig:map3}
        \caption{}
    \end{subfigure}
    \begin{subfigure}[b]{0.3\textwidth}
        \includegraphics[width=\textwidth]{room64.png}
        \label{fig:map1}
        \caption{}
    \end{subfigure}
    \begin{subfigure}[b]{0.3\textwidth}
        \includegraphics[width=\textwidth]{room32.png}
        \label{fig:map2}
        \caption{}
    \end{subfigure}
    \caption{Maps used for experimental evaluation. (a) Map comprised of two rooms connected by narrow passages. (b) and (c) Maps of the indoor environment composed of numerous rooms connected by narrow passages.}
    \label{fig:maps}
\end{figure}

The proposed method was implemented in C++\footnote{\url{https://github.com/PathPlanning/ORCA-algorithm/tree/Deadlocks}} and its experimental evaluation was carried out on a laptop running macOS 10.14.6 based on Intel Core i5-8259U (2.3 GHz) CPU and with 16 GB of RAM.

We used two types of grid maps, i.e. the maps composed of the free/blocked cells, for the experiments (see~\figurename~\ref{fig:maps}). First, we generated maps that were comprised of two open areas (rooms) separated by a wall with tight passages (doors) in it. The number of passages varied from 1 to 4, thus 4 different maps of that type were generated in total. The overall size of each map was $64 \times 64$. We refer to these maps as to the \texttt{gaps} maps. Second, we took two maps from the \textit{MovingAI}~\cite{stern2019multi} benchmark. They represent indoor environments composed of numerous rooms connected by passages. The first map of that type has a size of $64 \times 64$ and was comprised of 16 rooms (9 of them of the size $15 \times 15$, 1 --  $14\time14$ and the rest -- $14 \times 15$ or $15 \times 14$). The size of the second map was $32 \times 32$ and it was composed of the 64 rooms of the size $3 \times 3$. The latter two maps, referred to as \texttt{rooms} further on, are depicted on~\figurename~\ref{fig:maps}b-c.

\begin{figure}[t]
    \centering
    \begin{subfigure}[b]{0.4\textwidth}
        \includegraphics[width=\textwidth]{SR_fr1_new-eps-converted-to.pdf}
        \label{fig:SR1}

    \end{subfigure}
    \begin{subfigure}[b]{0.4\textwidth}
        \includegraphics[width=\textwidth]{SR_fr2_new-eps-converted-to.pdf}
        \label{fig:SR2}

    \end{subfigure}

    \begin{subfigure}[b]{0.4\textwidth}
        \includegraphics[width=\textwidth]{SR_fr3_new-eps-converted-to.pdf}
        \label{fig:SR3}

    \end{subfigure}
    \begin{subfigure}[b]{0.4\textwidth}
        \includegraphics[width=\textwidth]{SR_fr4_new-eps-converted-to.pdf}
        \label{fig:SR4}

    \end{subfigure}

    \caption{Success rate for \texttt{gaps} maps.}
    \label{fig:SRgaps}
\end{figure}

Start/goal locations on each map were generated as follows. For the \texttt{gaps} maps we always generated half of the start/goal locations in the left open area and the other half in the right one. So, to accomplish the mission, agents have to navigate between the two areas via the passages in the wall. For the \texttt{rooms} maps we picked start/goal locations randomly. For each map we created 250 different scenarios. Each scenario is a list of 40 start/goal locations for the agents. While testing the scenarios were used in the following fashion. First, we invoke the algorithm on 5 (first) start/goal pairs of a scenario, then we increased this number by 5 and invoke the algorithm again and so on until the number of agents reaches 40. At this time the scenario was considered to be processed and we moved to the next one.

We compared the suggested approach, referred to as \textsc{ORCA*+P\&R}, to the one that does not utilize deadlock detection and multi-agent path finding, referred to as \textsc{ORCA*}. For both versions we set the radius of each agent to be equal to 0.3 of the cell size. We also introduced an additional 0.19 safe-buffer for individual path finding and collision avoidance. For \textsc{ORCA*+P\&R} the number of neighbours for an agent required to switch to the coordinated mode was set to $k=3$.

At each run the maximum number of simulation steps was limited to 12 800. If by that time the agents fail to reach their goals, i.e. at least one agent was not on its target position or at least one agent collided with another agent or static obstacle, the run was considered to be \textit{failure}. If all agents managed to safely reach their goals the run was acknowledged as \textit{success}. The main metric that we were interested in was the \textit{success rate} i.e. the percentage of tasks that result with  \textit{success} out of all tasks attempted to be solved.

\begin{figure}[t]
    \centering
    \begin{subfigure}{0.4\textwidth}
        \includegraphics[width=\textwidth]{SR_rooms64_new-eps-converted-to.pdf}
        \label{fig:room64}

    \end{subfigure}
    \begin{subfigure}{0.4\textwidth}
        \includegraphics[width=\textwidth]{SR_rooms32_new-eps-converted-to.pdf}
        \label{fig:room32}

    \end{subfigure}

    \caption{Success rate for \texttt{rooms} maps.}
    \label{fig:SRrooms}
\end{figure}

Success rates for \textsc{ORCA*+P\&R} and \textsc{ORCA*} are shown on~\figurename~\ref{fig:SRgaps} and \ref{fig:SRrooms}. As one can see the selected environments are very challenging for \textsc{ORCA*} and its success rate is very low for large number of agents on all the maps. The most challenging environments are the one with  1 passage on a \texttt{gaps} map and the one with 64 rooms on \texttt{rooms} map. As expected on all maps \textsc{ORCA*+P\&R} successfully solved profoundly more instances compared to the baseline. For example, for the challenging \texttt{gaps} map with 1 passage the success rate for \textsc{ORCA*+P\&R} was 95\% for 20 agents while the one for \textsc{ORCA*} was 0\%. The difference in success rate for \texttt{rooms} maps is also clearly visible but less pronounced. We hypothesise that the main reason for that, as well as the reason for \textsc{ORCA*+P\&R} not to achieve 100\% success in general, is the imposed time limit. The plans created by the \textsc{Push and Rotate} algorithm may have contained numerous actions and that prevented the agents to reach their goals before the timestep limit exhausted. One of the possible solutions to avoid this will be substituting  \textsc{Push and Rotate} to another MAPF solver which creates plans containing less actions. However the solvers that are explicitly aimed at minimizing duration of the plan have much higher computational budget, so finding a right substitution is a challenging task for future research.

Overall, the results of the experiments clearly show that adding a locally-confined multi-agent path finding into the navigation pipeline significantly increase the chance that all agents will reach their goal locations and mission, thus, be accomplished.

\section{Conclusion}

In this paper we have studied a multi-agent navigation problem and suggested a decentralized approach that supplements the individual path planning and collision avoidance with the deadlock detection and multi-agent path finding. We implemented the proposed navigation pipeline and compared it the to the baseline, showing that adding the aformentioned components significantly increases the chances of agents safely arriving to the target destinations even in the congested environments with tight passages. An appealing direction of future work is the advancement of the deadlock detection procedure by making it less ad-hoc, as well as experimenting with different multi-agent path finding algorithms. Another direction for future research is evaluating the suggested approach on real robots.

\subsubsection{Acknowledgements}
The reported study was funded by RFBR and BRFBR, project number 20-57-00011. We would also like to thank Ilya Ivanashev for his implementation of \textsc{Push and Rotate}.

\bibliographystyle{splncs04}