# Combining Adversaries with Anti-adversaries in Training

Xiaoling Zhou, Nan Yang, Ou Wu Corresponding author.

###### Abstract

Adversarial training is an effective learning technique to improve the
robustness of deep neural networks. In this study, the influence of
adversarial training on deep learning models in terms of fairness, robustness,
and generalization is theoretically investigated under more general
perturbation scope that different samples can have different perturbation
directions (the adversarial and anti-adversarial directions) and varied
perturbation bounds. Our theoretical explorations suggest that the combination
of adversaries and anti-adversaries (samples with anti-adversarial
perturbations) in training can be more effective in achieving better fairness
between classes and a better tradeoff between robustness and generalization in
some typical learning scenarios (e.g., noisy label learning and imbalance
learning) compared with standard adversarial training. On the basis of our
theoretical findings, a more general learning objective that combines
adversaries and anti-adversaries with varied bounds on each training sample is
presented. Meta learning is utilized to optimize the combination weights.
Experiments on benchmark datasets under different learning scenarios verify
our theoretical findings and the effectiveness of the proposed methodology.

## Introduction

Apart from the standard generalization error (also known as natural error),
robust generalization error (also known as robust error) has received great
attention in recent years. A deep neural network with a low robust error can
cope well with adversarial attacks. Adversarial training is an effective
technique to reduce the robust error of a model (Wong, Rice, and Kolter 2020;
Bai and Luo 2021). Given a model $f(\cdot)$ and a sample $\boldsymbol{x}$
associated with a label $y$, classical adversarial training methods (Madry et
al. 2018; Goodfellow, Shlens, and Szegedy 2014) first generate an adversary
(i.e., adversarial example) $\boldsymbol{x}_{\text{adv}}$ for $\boldsymbol{x}$
with the following optimization:

${\boldsymbol{x}_{\text{adv}}}=\boldsymbol{x}+\arg\mathop{\max}\limits_{\left\|\boldsymbol{\delta}\right\|\leq\epsilon}\ell(f(\boldsymbol{x}+\boldsymbol{\delta}),y),$
(1)

where $\ell(\cdot,\cdot)$ is a loss function, $\boldsymbol{\delta}$ is the
perturbation term, and $\epsilon$ is the perturbation bound. Adversaries are
then leveraged as the training data to learn a more robust model. A number of
variations for adversarial training have been proposed in recent literature.
Zhang et al. (2019) decomposed the robust error into the natural and boundary
errors. They developed a new method, namely, TRADES, to obtain a better
tradeoff between standard generalization and robustness. Wang et al. (2020)
proposed a misclassification-aware adversarial training method to focus on the
misclassified examples.

In addition to the design of new methods, theoretical studies have been
conducted to explore the effectiveness and ineffectiveness of adversarial
training (Bai and Luo 2021). Yang et al. (2020) concluded that existing
adversarial methods cannot achieve an ideal tradeoff between accuracy and
robustness due to the insufficient smoothness (Xie et al. 2020) and
generalization properties of classifiers trained by these methods. They
pointed out that customized optimization methods or better network
architectures should be proposed. Xu et al. (2021) revealed that adversarial
training introduces severe unfairness between different categories. Thus, they
developed a new method that sets varied perturbation bounds for each class,
resulting in better fairness. Different from these studies, we conjectured
that one possible reason leading to unsatisfied tradeoff and fairness is that
not all training samples should be perturbed adversarially. For instance,
adversaries of noisy samples may harm the model performance (Uesato et al.
2019), and these samples should be perturbed in the anti-adversarial direction
to reduce their negative influence on model optimization. Zhu et al. (2021)
re-annotated pseudo labels for possible noisy samples before generating
adversaries for them. The generated adversaries are actually perturbed anti-
adversarially in binary classification tasks. In this study, samples with
anti-adversarial perturbations are called anti-adversaries111The anti-
adversary defined by Alfarra et al. (2022) is different from ours. They
utilize anti-adversaries to deal with attacks, whereas we aim to improve
robustness, accuracy, and fairness. ($\boldsymbol{x}_{\text{at-adv}}$)

${\boldsymbol{x}_{\text{at\text{-}adv}}}=\boldsymbol{x}+\arg\mathop{\min}\limits_{\left\|\boldsymbol{\delta}\right\|\leq\epsilon}\ell(f(\boldsymbol{x}+\boldsymbol{\delta}),y).$
(2)

This study conducts a comprehensive theoretical analysis of adversarial
training in the presence of two different perturbation directions (adversarial
and anti-adversarial) and varied bounds. Several typical learning scenarios
are considered, including classes with different learning difficulties,
imbalance learning, and noisy label learning. Our theoretical findings reveal
that the perturbation directions and bounds can remarkably influence the model
training. The combination of adversaries and anti-adversaries with varied
bounds can improve the fairness among classes and achieve a better tradeoff
between accuracy and robustness. Accordingly, a general objective that
combines adversaries and anti-adversaries is constructed for adversarial
training. A meta learning-based method is then proposed to optimize this
objective, in which the perturbation direction and bound of each training
sample is adjusted in accordance with its learning characteristics during
training. Our experimental results show that the combining strategy
outperforms state-of-the-art adversarial training methods. Our experimental
observations are in accordance with our theoretical findings.

The contributions of our study are as follows:

  * •

To the best of our knowledge, this is the first work that combines adversaries
and anti-adversaries in training. A comprehensive theoretical analysis is
conducted for the role of the combination strategy with varied perturbation
bounds222Existing theoretical studies presume that the perturbation bounds are
identical for all training samples. under three typical learning scenarios.

  * •

A new objective is established for adversarial training by combining
adversaries and anti-adversaries. Meta learning is utilized to solve the
optimization, and the perturbation direction and bound for each training
sample are determined in accordance with its learning characteristics, such as
training loss and margin.

Figure 1: (a) Variation of performance gaps between classes as $\rho$
increases. (b) Scope of the classification boundary of different manners. The
values of parameters are $K\\!=\\!2$, $\eta\\!=\\!2$, $\epsilon\\!=\\!0.2$,
and $\sigma\\!=\\!1$. The bounds for class “$+1$” and “$-1$” are denoted as
$\rho_{+}\times\epsilon$ and $\rho_{-}\times\epsilon$
($-\eta/\epsilon<\rho_{+},\rho_{-}<\eta/\epsilon$), respectively.
$\rho_{+}(\rho_{-})<0$ denotes that class “$+1(-1)$” is anti-adversarially
perturbed. The online material provides the formulas of boundaries. (c)
Logistic regression classifier boundaries (natural and robust) on simulated
data in Eq. (3). (d) Logistic regression classifier boundaries (natural and
robust with different directions).

## Related Work

### Tradeoff and Fairness in Adversarial Training

Recent studies on adversarial training focus on the tradeoff between accuracy
and robustness. Efforts (Raghunathan et al. 2019; Zhang et al. 2019, 2020;
Yang et al. 2021) have been made to reduce the natural errors of the
adversarially trained models, such as adversarial training with
semi/unsupervised learning and robust local feature (Song et al. 2020). Rice
et al. (2020) systematically investigated the role of various techniques used
in deep learning for achieving a better tradeoff, such as cutout, mixup, and
early stopping, where early stopping is found to be the most effective. This
investigation was also confirmed by Pang et al. (2021). Unfairness is also a
problem caused by adversarial training. Xu et al. (2021) trained a robust
classifier to minimize error and stressed it to satisfy two fairness
constraints. Several studies (Ding et al. 2020; Cheng et al. 2020; Balaji,
Goldstein, and Hoffman 2019) adaptively tune the perturbation bounds for each
sample with the inspiration that samples near the decision boundary should
have small bounds.

### Meta Learning

Meta learning has aroused great interest in recent years. Existing meta
learning methods can be divided into three categories, namely, metric-based
(Snell, Swersky, and Zemel 2017; Sung et al. 2018), model-based (Santoro et
al. 2016), and optimizing-based (Finn, Abbeel, and Levine 2017; Nichol,
Achiam, and Schulman 2018) methods. The algorithm we adopted that is inspired
by Model-Agnostic Meta-Learning (Finn, Abbeel, and Levine 2017) belongs to the
optimizing-based methods. The data-driven manner of meta optimization is
always utilized to learn the sample weights or the hyperparameters (Ren et al.
2018; Shu et al. 2019).

## Theoretical Investigation

This section conducts theoretical analyses to assess the influence of two
different perturbation directions and varied bounds on adversarial training in
three typical binary classification cases. Proofs are presented in the online
material.

### Notation

We denote the sample instance as $\boldsymbol{x}\in\mathcal{X}$ and
$y\in\mathcal{Y}$ as the label, where $\mathcal{X}\subseteq\mathbb{R}^{d}$
indicates the instance space, and $\mathcal{Y}=\\{-1,+1\\}$ indicates the
label space. The classification model $f$ is a mapping from the input data
space $\mathcal{X}$ to the label space $\mathcal{Y}$. It can be parametrized
by using linear classifiers or deep neural networks. The overall natural error
of $f$ is denoted as
$\mathcal{R}_{\text{nat}}(f)\\!:=\\!\operatorname{Pr}(f(\boldsymbol{x})\\!\neq\\!y)$.
The overall robust error is denoted as
$\mathcal{R}_{\text{rob}}(f)\\!:=\\!\operatorname{Pr}(\exists\boldsymbol{\delta}~{}||\boldsymbol{\delta}||\\!\leq\\!\epsilon,\text{s.t.}f\left(\boldsymbol{x}+\boldsymbol{\delta}\right)\\!\neq\\!y)$.

### Case I: Classes with Different Difficulties

In this case, the binary setting established by Xu et al. (2021) is followed.
The data from each class follow a Gaussian distribution $\mathcal{D}$ that is
centered on $\boldsymbol{\theta}$ and $\boldsymbol{-\theta}$, respectively. A
$K$-factor difference is found between two classes’ variances:
$\sigma_{+1}:\sigma_{-1}=K:1$ and $K>1$. The data follow

$\displaystyle y\stackrel{{\scriptstyle
u.a.r}}{{\sim}}\\{-1,+1\\},\quad\boldsymbol{\theta}=({\eta,\ldots,\eta})\in\mathbb{R}^{d},\eta>0,$
(3)
$\displaystyle\boldsymbol{x}\sim\left\\{\begin{array}[]{ll}\mathcal{N}\left(\boldsymbol{\theta},\sigma_{+1}^{2}\boldsymbol{I}\right),&\text{
if }y=+1,\\\
\mathcal{N}\left(-\boldsymbol{\theta},\sigma_{-1}^{2}\boldsymbol{I}\right),&\text{
if }y=-1.\end{array}\right.$

Class “$+1$” is harder because the optimal linear classifier will give a
larger error to class “$+1$” than class “$-1$”. Xu et al. (2021) proved that
adversarial training with an equal bound will exacerbate the performance gap
(including natural and robust errors) between classes and hurt the harder
class. We show that adversarial training with unequal bounds on two classes
can tune the performance gap and the tradeoff between the robustness and
accuracy of the model. Let $\sigma_{-1}=\sigma$. The following theorem is
first proposed.

###### Theorem 1

For a data distribution $\mathcal{D}$ in Eq. (3), assume that the perturbation
bounds of class “$-1$” and “$+1$” are $\epsilon$ and $\rho\times\epsilon$
($0\leq\epsilon,\rho{\epsilon}<{\eta}$), respectively. The natural errors of
the optimal robust linear classifier $f_{\text{rob}}$ for two classes are

$\begin{aligned}
&\mathcal{R}_{\text{nat}}\left(f_{\text{rob}},-1\right)=\operatorname{Pr}\left\\{\mathcal{N}(0,1)\leq
B-K\cdot\sqrt{B^{2}+q(K)}-\frac{\sqrt{d}}{\sigma}\epsilon\right\\},\\\
&\mathcal{R}_{\text{nat}}\left(f_{\text{rob}},+1\right)=\operatorname{Pr}\left\\{\mathcal{N}(0,1)\leq-K\cdot
B+\sqrt{B^{2}+q(K)}-\frac{\sqrt{d}\rho}{K\sigma}\epsilon\right.\\},\end{aligned}$

(4)

where
$B=\frac{2}{K^{2}-1}\frac{\sqrt{d}(\eta-\frac{\epsilon(1+\rho)}{2})}{\sigma}$,
and $q(K)=\frac{2\log K}{K^{2}-1}$.

The robust errors are shown in the online material. The natural and robust
errors change with different $\rho$ values. A corollary is derived in
accordance with Theorem 1.

###### Corollary 1

The data and perturbations in Theorem 1 are followed. When
$K<\exp({{d(\eta-\epsilon)^{2}}/{2\sigma^{2}}})$, the adversarially trained
model will increase and decrease the natural and robust errors of class “$-1$”
and class “$+1$”, with the increase in $\rho$, respectively.

Accordingly, the performance gaps of $\mathcal{R}_{\text{nat}}$ and
$\mathcal{R}_{\text{rob}}$ decrease with the increase in $\rho$, and better
fairness can be achieved, as shown in Fig. 1 (a). In Fig. 1 (c), the boundary
shifts toward the easy class “$-1$”. From Fig. 1 (b), adversarial training
with varied bounds contributes to larger scope of the boundary compared with
TRADES (Zhang et al. 2019). Thus, a better tradeoff can be attained.
Therefore, fairness and tradeoff can be tuned with different $\rho$ values.
Next, anti-adversaries are considered. Assume that samples in class “$-1$”
perform anti-adversarial perturbation. Similar to Theorem 1, a theorem
calculating the natural and robust errors is proposed as shown in the online
material. A corollary is then derived, indicating that the combination of
adversaries and anti-adversaries can tune the performance gap and tradeoff.

###### Corollary 2

For a data distribution $\mathcal{D}$ in Eq. (3), assume that class “$-1$” is
anti-adversarially perturbed with the bound $\epsilon$, and class “$+1$” is
adversarially perturbed with the bound $\rho\times\epsilon$
($0\leq\epsilon,\rho{\epsilon}<{\eta}$). When
$K<\exp({{d(\eta-\epsilon)^{2}}/{2\sigma^{2}}})$, the adversarially trained
model will increase and decrease the natural and robust errors of class “$-1$”
and class “$+1$”, with the increase in $\rho$, respectively.

In accordance with Corollaries 1 and 2, the adversarial training and the
combination strategy can nearly attain the same performance. However, the
combination strategy can contribute to the largest scope of the boundary, as
shown in Fig. 1 (b). Thus, the combination strategy is more effective in
achieving a better tradeoff and fairness theoretically. As shown in Figs. 1
(c) and (d), the combination strategy has a more pronounced effect under the
same bound (i.e., the same $\rho$), indicating that it needs smaller bounds
when the same performance is achieved. Thus, the combination strategy is more
efficient than only the adversarial perturbation, indicating that anti-
adversaries are valuable.

### Case II: Classes with Imbalanced Proportions

In this case, the two variances in Eq. (3) are assumed to be identical333The
case with different variances can be explored similarly., that is,
$\sigma_{+1}=\sigma_{-1}=\sigma$. However, $p(y=+1)$ ($p_{+}$) is no longer
equal to $p(y=-1)$ ($p_{-}$). Without loss of generality, let
$p_{+}:p_{-}=1:V$ and $V>1$.

Class “$-1$” is the majority category, and an optimal linear classifier will
give a smaller natural error for class “$-1$” than class “$+1$”, as proved in
the online material. Similarly, we proved that standard adversarial training
will exacerbate the performance gap between classes and hurt the smaller
class. We then show that adversarial training with unequal bounds on the two
classes will tune the performance gap between classes and the tradeoff between
robustness and accuracy. The following theorem is first proposed.

###### Theorem 2

For a data distribution $\mathcal{D}_{V}$ described above with the imbalance
factor $V$, assume that the perturbation bounds of classes “$-1$” and “$+1$”
are $\epsilon$ and $\rho\times\epsilon$
($0\leq\epsilon,\rho{\epsilon}<{\eta}$), respectively. The natural errors of
the optimal robust linear classifier $f_{\text{rob}}$ for the two classes are

$\begin{aligned}
&\mathcal{R}_{\text{nat}}\left(f_{\text{rob}},-1\right)=\operatorname{Pr}\left\\{\mathcal{N}(0,1)\leq-A-\frac{\log
V}{2A}-\frac{\sqrt{d}}{\sigma}\epsilon\right\\},\\\
&\mathcal{R}_{\text{nat}}\left(f_{\text{rob}},+1\right)=\operatorname{Pr}\left\\{\mathcal{N}(0,1)\leq-A+\frac{\log
V}{2A}-\frac{\sqrt{d}\rho}{\sigma}\epsilon\right\\},\end{aligned}$

(5)

where $A={\sqrt{d}(\eta-{\epsilon(1+\rho)}/{2})}/{\sigma}$.

A corollary is derived on the basis of Theorem 2.

###### Corollary 3

The data and perturbations in Theorem 2 are followed. When
$V<\exp({{d(\eta-\epsilon)^{2}}/{2\sigma^{2}}})$, the adversarially trained
model will increase and decrease the natural and robust errors of class “$-1$”
and class “$+1$”, with the increase in $\rho$, respectively.

From Corollary 3, the performance gaps between classes can be decreased with
different $\rho$ values. The boundary can be moved within the scope with
different $\rho$ values that covers the boundary of standard adversarial
training. Therefore, a better tradeoff can be attained by adversarial training
with varied bounds. Next, the anti-adversaries are considered. We assume that
samples in class “$-1$” perform anti-adversarial perturbation. Similar to
Theorem 2, a theorem that portrays the training occasion where the adversaries
and anti-adversaries are combined is proposed, as shown in the online
material. A corollary is then derived.

###### Corollary 4

For a data distribution $\mathcal{D}_{V}$ in Theorem 2, the perturbations in
Corollary 2 are followed. When
$V<\exp({{d(\eta-\epsilon)^{2}}/{2\sigma^{2}}})$, the adversarially trained
model will increase and decrease the natural and robust errors of class “$-1$”
and class “$+1$”, with the increase in $\rho$, respectively.

In accordance with Corollary 4, the performance gaps between classes can be
tuned by the combination strategy. In addition, it can contribute to the
larger scope of the classification boundary compared with only adversaries,
and a better tradeoff can be attained. When the same performance is achieved,
combining adversaries and anti-adversaries has a smaller bound. Therefore, the
combination strategy is more efficient than only the adversarial perturbation.
More details are presented in the online material.

### Case III: Classes with Noisy Labels

In this case, the two classes’ variances and prior probabilities are assumed
to be identical, that is, $\sigma_{+1}=\sigma_{-1}$ and $p_{+}=p_{-}$. Without
loss of generality, class “$-1$” is assumed to contain flipped noisy labels.
Two main conclusions are obtained. 1) The adversaries of noisy samples will
harm the tradeoff and fairness of the robust model. 2) If noisy samples are
anti-adversarially perturbed with a bound $\rho\times\epsilon$ and clean
samples are adversarially perturbed with a bound $\epsilon$, then the natural
and robust errors of class “$-1$” and class “$+1$” will be decreased and
increased with the increase in $\rho$, respectively. Thus, the combination
strategy with varied bounds is effective in achieving a lower performance gap
between classes and a better tradeoff between the accuracy and robustness on
noisy data. The relevant theorems are shown in the online material.

### Summarization

Our theoretical analysis comprehensively reveals that the perturbation
directions and bounds remarkably influence the generalization, robustness, and
fairness of the robust model under three typical learning scenarios.
Adversarial training with different perturbation directions and bounds can
better tune the performance gap between classes and the tradeoff between
robustness and accuracy. Existing studies ignored anti-adversaries that are
valuable. Thus, a new optimized objective considering anti-adversaries is
proposed.

## Methodology

Illuminated by the theoretical analysis, a new objective function is first
established. Accordingly, a meta learning-based method that combines
adversaries and anti-adversaries (CAAT) in training with a varied bound for
each sample is proposed to solve the optimization, as shown in Fig. 2.

Figure 2: Overall structure of CAAT. The red and green lines represent the
learning loops of the classifier network and weighting network, respectively.

### Proposed Objective Function

Ideally, the objective function that combines adversaries and anti-adversaries
can be formulated as

$\displaystyle\min_{{\boldsymbol{W}},\alpha,\beta}$
$\displaystyle\mathbb{E}_{\boldsymbol{x}}\\{\alpha_{\boldsymbol{x}}\ell\\!\left(f_{{}_{\boldsymbol{W}}}\left(\boldsymbol{x}_{\text{adv}}\right),y\\!\right)\\!+\\!\beta_{\boldsymbol{x}}\ell\\!\left(f_{{}_{\boldsymbol{W}}}(\boldsymbol{x}_{\text{at-
adv}}),y\\!\right)\\},$ (6)
$\displaystyle\text{s.t.}~{}\alpha_{\boldsymbol{x}}+\beta_{\boldsymbol{x}}=1~{}\text{and}~{}\alpha_{\boldsymbol{x}},\beta_{\boldsymbol{x}}\in\\{0,1\\},$

where $\boldsymbol{x}_{\text{adv}}$ and $\boldsymbol{x}_{\text{at-adv}}$ are
calculated by using Eqs. (1) and (2) with varied bound
$\epsilon_{\boldsymbol{x}}$ for each sample $\boldsymbol{x}$, respectively;
$\alpha_{\boldsymbol{x}}$ and $\beta_{\boldsymbol{x}}$ are the combination
weights; $f_{{}_{\boldsymbol{W}}}$ is the classifier network with the
parameter $\boldsymbol{W}$. When $\alpha_{\boldsymbol{x}}\equiv 1$, Eq. (6)
can be reduced to the objective of standard adversarial training.

To solve Eq. (6), we first assume that the values of $\alpha_{\boldsymbol{x}}$
and $\beta_{\boldsymbol{x}}$ depend on the training characteristics of sample
$\boldsymbol{x}$. Accordingly, their values are produced by a weighting
network $f_{\boldsymbol{\Omega}}$ (parameterized by $\boldsymbol{\Omega}$),
where its input is a series of training characteristics
$\boldsymbol{\zeta}_{\boldsymbol{x}}$ of $\boldsymbol{x}$ shown in Fig. 2.
$\ell(f_{{}_{\boldsymbol{W}}}(\boldsymbol{x}_{\text{adv}}),y)$ can be divided
into $\ell(f_{{}_{\boldsymbol{W}}}(\boldsymbol{x}),y)$ and
$\ell(f_{{}_{\boldsymbol{W}}}(\boldsymbol{x}),f_{{}_{\boldsymbol{W}}}(\boldsymbol{x}_{\text{adv}}))$
to achieve a better tradeoff between the accuracy and robustness (Zhang et al.
2019). To improve the fairness among classes, we further stress $f$ to satisfy
two fairness constraints following Ref. Xu et al.(2021). Thus, our adopted
objective function is

$\displaystyle\min_{{\boldsymbol{W}},{\boldsymbol{\Omega}}}$
$\displaystyle\mathbb{E}_{\boldsymbol{x}}\\{{\alpha_{\boldsymbol{x}}[\ell(f_{{}_{\boldsymbol{W}}}(\boldsymbol{x}),y)}+{\lambda\ell\left(f_{{}_{\boldsymbol{W}}}(\boldsymbol{x}),f_{{}_{\boldsymbol{W}}}\left(\boldsymbol{x}_{\text{adv}}\right)\right)}]$
(7)
$\displaystyle+{\beta_{\boldsymbol{x}}\ell\left(f_{{}_{\boldsymbol{W}}}(\boldsymbol{x}_{\text{at-
adv}}),y\right)}\\},$ $\displaystyle\text{ s.t.
}\left\\{\begin{array}[]{l}[\alpha_{\boldsymbol{x}},\beta_{\boldsymbol{x}}]=f_{\boldsymbol{\Omega}}(\boldsymbol{\zeta_{\boldsymbol{x}}}),\forall\boldsymbol{x}\in\mathcal{X},\\\
\mathcal{R}_{\text{nat}}(f_{{}_{\boldsymbol{W}}},c)-\mathcal{R}_{\text{nat}}(f_{{}_{\boldsymbol{W}}})\leq\tau_{1},\forall
c\in\mathcal{Y},\\\
\mathcal{R}_{\text{bdy}}(f_{{}_{\boldsymbol{W}}},c)-\mathcal{R}_{\text{bdy}}(f_{{}_{\boldsymbol{W}}})\leq\tau_{2},\forall
c\in\mathcal{Y},\end{array}\right.$

where $\mathcal{R}_{\text{bdy}}$ is the boundary error of the model, denoted
as
$\mathcal{R}_{\text{bdy}}(f_{{}_{\boldsymbol{W}}})=\operatorname{Pr}(\exists{\boldsymbol{x}_{\text{adv}}\in\mathbb{B}(\boldsymbol{x},\epsilon)},f_{{}_{\boldsymbol{W}}}(\boldsymbol{x}_{\text{adv}})\neq
f_{{}_{\boldsymbol{W}}}(\boldsymbol{x})\\}$;
$\mathcal{R}_{\text{nat}}(f_{{}_{\boldsymbol{W}}},c)=\operatorname{Pr}(f_{{}_{\boldsymbol{W}}}(\boldsymbol{x})\neq
y\mid y=c\\}$;
$\mathcal{R}_{\text{bdy}}(f_{{}_{\boldsymbol{W}}},c)=\operatorname{Pr}(\exists{\boldsymbol{x}_{\text{adv}}\in\mathbb{B}(\boldsymbol{x},\epsilon)},f_{{}_{\boldsymbol{W}}}(\boldsymbol{x}_{\text{adv}})\neq
f_{{}_{\boldsymbol{W}}}(\boldsymbol{x})\mid y=c\\}$; $f_{\boldsymbol{\Omega}}$
is a multilayer perception (MLP) network with a hidden layer and a
$\tau$-softmax layer:
$\text{Softmax}((\boldsymbol{h}\boldsymbol{\omega}+\boldsymbol{b})/\tau)$;
$\lambda>0$ is a regularization parameter that adjusts the influence of the
natural and boundary errors on the model; $\tau_{1}$ and $\tau_{2}$ are small
and positive predefined parameters. The approach for solving the two fairness
constraints is the same as that in Ref. Xu et al.(2021), where a Lagrangian is
formed.

Algorithm 1 CAAT

Input: #Iteration $T$, step sizes $\eta_{0}$, $\eta_{1}$, and $\eta_{2}$,
batch size $n$, meta batch size $m$, bound $\epsilon$, #iterations $K$ in
inner optimization, classifier network $f_{{}_{\boldsymbol{W}}}$, weighting
network $f_{\boldsymbol{\Omega}}$, $D^{\text{train}}$, $D^{\text{meta}}$.
Output: Trained robust network $f_{{}_{\boldsymbol{W}}}$.

1: Initialize networks $f_{{}_{\boldsymbol{W}}}$ and
$f_{\boldsymbol{\Omega}}$;

2: for $t=1$ to $T$ do

3: Sample $n$ and $m$ samples from $D^{\text{train}}$ and $D^{\text{meta}}$;

4: for $i=1$ to $n$ (in parallel) do

5:
$\boldsymbol{x}_{i}^{\text{adv}}\\!=\\!\boldsymbol{x}_{i}\\!+\\!0.001\mathcal{N}(0,I)$
and $\boldsymbol{x}_{i}^{\text{at-
adv}}\\!=\\!\boldsymbol{x}_{i}\\!+\\!0.001\mathcal{N}(0,I)$, where
$\mathcal{N}(0,I)$ is the Gaussian distribution;

6: Calculate the perturbation bound $\epsilon_{i}$ for sample
$\boldsymbol{x}_{i}$;

7: for $k=1$ to $K$ do

8:
$\boldsymbol{x}_{i}^{\text{adv}}\\!\\!\\!\leftarrow\\!\\!\\!\Pi_{\mathbb{B}(\boldsymbol{x}_{i},\epsilon_{i})}(\eta_{0}\\!\operatorname{sign}(\nabla_{\boldsymbol{x}_{i}^{\text{adv}}}\ell(f_{{}_{\boldsymbol{W}}}(\boldsymbol{x}_{i}),f_{{}_{\boldsymbol{W}}}(\boldsymbol{x}_{i}^{\text{adv}})))$$+\boldsymbol{x}_{i}^{\text{adv}})$,
where $\Pi$ is the projection operator;

9: $\boldsymbol{x}_{i}^{\text{at-
adv}}\\!\\!\\!\leftarrow\\!\\!\\!\Pi_{\mathbb{B}(\boldsymbol{x}_{i},\epsilon_{i})}(\\!-\\!\eta_{0}\\!\operatorname{sign}(\nabla_{\boldsymbol{x}_{i}^{\text{at-
adv}}}\ell(f_{{}_{\boldsymbol{W}}}(\boldsymbol{x}_{i}^{\text{at-
adv}}),y_{i}))$$+\boldsymbol{x}_{i}^{\text{at-adv}})$;

10: end for

11: end for

12: Formulate $\hat{\boldsymbol{W}}^{(t)}(\boldsymbol{\Omega})$ by Eq. (9);

13: Update $\boldsymbol{\Omega}^{(t+1)}$ by Eq. (10) and update
$\boldsymbol{W}^{(t+1)}$ by Eq. (11);

14: end for

### Extraction of Training Characteristics
($\boldsymbol{\zeta}_{\boldsymbol{x}}$)

Our theoretical investigation reveals that different training samples can have
different perturbation directions. The perturbation direction of a training
sample depends on a series of factors, including learning difficulty, class
proportion, and noise degree. Therefore, six training characteristics of each
training sample $\boldsymbol{x}$, namely, loss
($\boldsymbol{\zeta}_{{\boldsymbol{x}},1}$), margin
($\boldsymbol{\zeta}_{{\boldsymbol{x}},2}$), the norm of loss gradient for the
logit vector ($\boldsymbol{\zeta}_{{\boldsymbol{x}},3}$), the information
entropy of the softmax output ($\boldsymbol{\zeta}_{{\boldsymbol{x}},4}$),
class proportion ($\boldsymbol{\zeta}_{{\boldsymbol{x}},5}$), and the average
loss of each class ($\boldsymbol{\zeta}_{{\boldsymbol{x}},6}$), are extracted,
as shown in the extraction module in Fig. 2. The calculation detail of each
characteristic is shown in the online material.

### Perturbation Bound ($\epsilon_{\boldsymbol{x}}$) Calculation

We employ two types of varied bound in our framework. Following Ref. Xu et
al.(2021), the class-wise perturbation bound named ReMargin, which is suitable
for imbalanced data, is utilized. A sample-wise bound is proposed to handle
noise. It is inspired by the intuition that noisy samples have a large norm of
loss gradient in general and these samples should exhibit the greatest degree
of anti-adversarial training. Thus, the Grad-Based bound can be calculated as

$\epsilon_{\boldsymbol{x}}=(\alpha_{\boldsymbol{x}}\overline{\boldsymbol{g}}_{{\boldsymbol{x}}_{\text{adv}}}+\beta_{\boldsymbol{x}}\overline{\boldsymbol{g}}_{{\boldsymbol{x}}_{\text{at-
adv}}}+\varepsilon)\times\epsilon,$ (8)

where $\overline{\boldsymbol{g}}_{{\boldsymbol{x}}_{\text{adv}}}$ and
$\overline{\boldsymbol{g}}_{{\boldsymbol{x}}_{\text{at-adv}}}$ are the
normalized
$||\frac{\partial\ell(f_{{}_{\boldsymbol{W}}}(\boldsymbol{x}),f_{{}_{\boldsymbol{W}}}(\boldsymbol{x}_{\text{adv}}))}{\partial\boldsymbol{x}_{\text{adv}}}||_{2}$
and $||\frac{\partial\ell(f_{{}_{\boldsymbol{W}}}(\boldsymbol{x}_{\text{at-
adv}}),y)}{\partial\boldsymbol{x}_{\text{at-adv}}}||_{2}$, respectively.
$\epsilon$ is a predefined perturbation bound, and $\varepsilon$ is a
hyperparameter that is set to $0.9$ in our experiments. This bound is also
effective on imbalanced data because samples in tail classes have large norms
of loss gradient, and they should do the greatest degree of adversarial
training.

### Training with Meta-Learning

On the basis of the extracted characteristics and calculated bounds, an online
learning strategy is adopted to alternatively update $\boldsymbol{W}$ and
$\boldsymbol{\Omega}$ using a single optimization loop, as shown in Fig. 2.
Assume that we have a small amount of unbiased meta data
$D^{\text{meta}}\\!=\\!\\{\boldsymbol{x}^{\text{meta}}_{i},y^{\text{meta}}_{i}\\}_{i=1}^{M}$,
where $M\ll N$. Even if meta data are lacking, they can be compiled from the
training data $D^{\text{train}}$ (Zhang and Pfister 2021). The main steps are
shown below. Here, we ignore the regularization terms introduced by the
fairness constraints, while the online material provides the complete
formulas.

$\boldsymbol{\Omega}$ is treated as the to-be-updated parameter, and the
parameter of the updated classifier $\boldsymbol{W}$, which is a function of
$\boldsymbol{\Omega}$, is formulated. Stochastic gradient descent (SGD) is
utilized to optimize the training loss. Specifically, a minibatch of training
samples $\\{\boldsymbol{x}_{i},{y}_{i}\\}_{i=1}^{n}$ is selected in each
iteration, where $n$ is the size of the mini-batch. The updating of
$\boldsymbol{W}$ can be formulated as

$\begin{aligned}
&\hat{\boldsymbol{W}}^{(t)}(\boldsymbol{\Omega})=\boldsymbol{W}^{(t)}-\eta_{1}\frac{1}{n}\sum\nolimits_{i=1}^{n}\nabla_{{}_{\boldsymbol{W}}}\\{\alpha_{i}[\ell(f_{{}_{\boldsymbol{W}}}(\boldsymbol{x}_{i}),y_{i})+\\\
&\lambda\ell(f_{{}_{\boldsymbol{W}}}(\boldsymbol{x}_{i}),f_{{}_{\boldsymbol{W}}}(\boldsymbol{x}_{i}^{\text{adv}}))]+\beta_{i}\ell(f_{{}_{\boldsymbol{W}}}(\boldsymbol{x}_{i}^{\text{at-
adv}}),y_{i})\\}|_{{}_{\boldsymbol{W}^{(t)}}},\end{aligned}$

(9)

where $\eta_{1}$ is the step size. The parameter of the weighting network
$\boldsymbol{\Omega}$ after receiving feedback from the classifier network can
be updated on a minibatch of meta data as follows:

$\begin{aligned}
\boldsymbol{\Omega}&{}^{(t+1)}=\boldsymbol{\Omega}^{(t)}-\eta_{2}\frac{1}{m}\sum\nolimits_{i=1}^{m}\nabla_{\boldsymbol{\Omega}}[\ell^{\text{meta}}(f_{{}_{\hat{\boldsymbol{W}}^{(t)}(\boldsymbol{\Omega})}}(\boldsymbol{x}_{i}),y_{i})\\\
&+\lambda\ell^{\text{meta}}(f_{{}_{\hat{\boldsymbol{W}}^{(t)}(\boldsymbol{\Omega})}}(\boldsymbol{x}_{i}),f_{{}_{\hat{\boldsymbol{W}}^{(t)}(\boldsymbol{\Omega})}}(\boldsymbol{x}_{i}^{\text{adv}}))+\ell^{\text{meta}}(f_{{}_{\hat{\boldsymbol{W}}^{(t)}(\boldsymbol{\Omega})}}(\boldsymbol{x}_{i}^{\text{at-
adv}}),y_{i})]|_{\boldsymbol{\Omega}^{(t)}},\end{aligned}$

(10)

where $m$ and $\eta_{2}$ are the minibatch size of meta data and the step
size, respectively. The parameters of the classifier network are updated with
the obtained weights by fixing the parameters of the weighting network as
$\boldsymbol{\Omega}^{(t+1)}$:

$\begin{aligned}
&\boldsymbol{W}^{(t+1)}=\boldsymbol{W}^{(t)}-\eta_{1}\frac{1}{n}\sum\nolimits_{i=1}^{n}\nabla_{{}_{\boldsymbol{W}}}\\{\alpha_{i}[\ell(f_{{}_{\boldsymbol{W}}}(\boldsymbol{x}_{i}),y_{i})+\\\
&\lambda\ell(f_{{}_{\boldsymbol{W}}}(\boldsymbol{x}_{i}),f_{{}_{\boldsymbol{W}}}(\boldsymbol{x}_{i}^{\text{adv}}))]+\beta_{i}\ell(f_{{}_{\boldsymbol{W}}}(\boldsymbol{x}_{i}^{\text{at-
adv}}),y_{i})\\}|_{{}_{\boldsymbol{W}^{(t)}}}.\end{aligned}$

(11)

The steps of our CAAT method are shown in Algorithm 1.

## Experiments

| Avg. Nat. | Worst Nat. | Avg. Bdy. | Worst Bdy. | Avg. Rob. | Worst Rob.
---|---|---|---|---|---|---
PGD Adv. Training | 15.5 | 33.8 | 40.9 | 55.9 | 56.4 | 82.7
TRADES ($1/\lambda=1$) | 14.6 | 31.2 | 43.1 | 64.6 | 57.7 | 84.7
TRADES ($1/\lambda=6$) | 19.6 | 39.1 | 29.9 | 49.5 | 49.3 | 77.6
Baseline ReWeight | 19.2 | 28.3 | 39.2 | 53.7 | 58.2 | 80.1
FRL (ReWeight) | 16.0 | 22.5 | 41.6 | 54.2 | 57.6 | 73.3
FRL (ReMargin) | 16.9 | 24.9 | 35.0 | 50.6 | 51.9 | 75.5
FRL (ReWeight+ReMargin) | 17.0 | 26.8 | 35.7 | 44.5 | 52.7 | 69.5
CAAT (Grad-Based) | 14.6 | 23.6 | 14.4 | 23.3 | 28.6 | 48.1
CAAT (ReMargin) | 13.9 | 24.3 | 15.4 | 24.9 | 29.3 | 44.4
Table 1: Average and worstclass natural, boundary, and robust errors (%) for various algorithms on CIFAR10. Figure 3: (a): Ratio of adversaries in each class during training on standard CIFAR10. (b): Average loss of each class during training on standard CIFAR10. | Avg. Nat. | Avg. Bdy. | Avg. Rob.
---|---|---|---
PGD Adv. Training | 15.6 | 37.1 | 52.8
TRADES ($1/\lambda=1$) | 15.6 | 31.0 | 46.5
TRADES ($1/\lambda=6$) | 16.4 | 21.0 | 37.4
FRL (ReWeight) | 15.3 | 36.0 | 51.4
FRL (ReMargin) | 15.2 | 36.0 | 51.1
FRL (ReWeight+ReMargin) | 15.7 | 34.3 | 50.0
CAAT (Grad-Based) | 14.6 | 13.9 | 28.5
CAAT (ReMargin) | 14.7 | 14.7 | 29.4
Table 2: Average natural, boundary, and robust errors (%) for various
algorithms on CIFAR10 with 20% pair-flip noise.

Experiments are conducted to verify our theoretical findings and the
effectiveness of the proposed CAAT in improving the accuracy, robustness, and
fairness of the robust models.

### Experimental Settings

Benchmark adversarial learning datasets: CIFAR10 (Krizhevsky 2009) and SVHN
(Netzer et al. 2011) are adopted in our experiments, including the noisy and
imbalanced versions of the CIFAR data (Shu et al. 2019). For the two datasets,
PreAct-ResNet18 (He et al. 2016) and Wide-ResNet28-10 (WRN28-10) (Zagoruyko
and Komodakis 2016) are adopted as the backbone network. This section only
represents the results of PreAct-ResNet18. Others are presented in the online
material. The compared methods include three popular adversarial training
algorithms, namely, PGD (Madry et al. 2018), TRADES (Zhang et al. 2019), and
FRL (Xu et al. 2021). A debiasing method (Alekh et al. 2018) is also compared
which is to upweight the loss of the class with the largest robust error in
the training data. The results of TRADES and FRL are calculated by using the
codes in their official repositories.

The training and testing configurations used in Ref. Xu et al. (2021) are
followed. The number of iterations in an adversarial attack is set to 10.
Following Xu et al. (2021), 300 samples in each class with clean labels are
selected as the meta dataset, which helps us tune the hyperparameters and
train the weighting network. Adversarial training is trained on PGD attack
setting $\epsilon=8/255$ with cross-entropy loss. For our method and FRL
(ReMargin), the predefined perturbation bound is also set to $8/255$. All the
models are trained by using SGD with momentum 0.9 and weight decay $5\times
10^{-4}$. The value of $\lambda$ is selected in $\\{2/3,1,1.5,6\\}$. During
the evaluation phase, we report each model’s average and worstclass natural,
boundary, and robust error rates.

Figure 4: (a): Ratio of adversaries for noisy and clean samples on CIFAR10
with 20% uniform noise during training. (b): Average adversarial and anti-
adversarial perturbation bounds for clean and noisy samples during training.

### Experiments on Standard Dataset

Tables 1 shows the performance of our proposed CAAT and the compared methods
on standard CIFAR10. Those on SVHN are shown in the online material.
Considering that our training/testing configuration is the same as that in
Ref. Xu et al.(2021), the results of the above competing methods reported in
the FRL (Xu et al. 2021) paper are directly presented.

Figure 5: (a) and (b): Natural and robust errors for each class of different
methods on CIFAR10 with imbalance factor 10. (c) and (d): Natural and robust
errors for each class of different methods on CIFAR10 with imbalance factor
100.

From the results, our methods with two types of bound reduce the average
natural and robust errors under different degrees, indicating that CAAT
obtains better accuracy and robustness of the model. Compared with other
methods, CAAT decreases the average and worst robust error rates by 21% and
25% on CIFAR10. Baseline ReWeight can only decrease the worst intraclass
natural error but cannot equalize boundary or robust errors. FRL (Xu et al.
2021) has only a limited ability to reduce the worst boundary and robust
errors, resulting in limited fairness between classes. Our method more
effectively decreases the worst intraclass errors. Thus, CAAT achieves better
fairness among classes compared with other methods. Although FRL (ReWeight)
obtains the lowest worst natural error, it has large average and worst robust
errors, which is inferior to CAAT. Hard classes (classes with a large average
loss) have a higher ratio of adversaries than easy ones, as shown in Fig. 3,
which helps improve the performance of hard classes and effectively enhances
the fairness among classes. The same conclusions can also be obtained on the
SVHN dataset.

| Avg. Nat. | Avg. Bdy. | Avg. Rob.
---|---|---|---
PGD Adv. Training | 20.1 | 42.8 | 62.9
TRADES ($1/\lambda=1$) | 16.8 | 32.3 | 49.1
TRADES ($1/\lambda=6$) | 23.6 | 23.8 | 47.4
FRL (ReWeight) | 16.9 | 38.1 | 55.0
FRL (ReMargin) | 17.5 | 35.6 | 53.1
FRL (ReWeight+ReMargin) | 17.2 | 35.1 | 52.3
CAAT (Grad-Based) | 15.8 | 14.2 | 30.0
CAAT (ReMargin) | 16.2 | 13.7 | 29.9
Table 3: Average and worstclass natural, boundary, and robust errors (%) on
CIFAR10 with imbalance factor 10.

### Experiments of Noisy Classification

Two settings of corrupted labels, including uniform and pair-flip noises, are
adopted (Shu et al. 2019). The values of the noise ratio are set to $20\%$ and
$40\%$. CIFAR10 dataset, which is popularly used for the evaluation of noisy
labels, is adopted. Here, we only show the average errors of CIFAR10 with
$20\%$ pair-flip noise. Others are presented in the online material. From the
results in Table 2 and the online material, CAAT achieves the lowest average
and worst natural and robust errors, indicating that it obtains the best
generalization, robustness, and fairness compared with other methods.

As shown in Fig. 4 (a), most of the noisy samples are anti-adversarially
perturbed during training, which is in accordance with our theoretical
findings. From Fig. 4 (b), the average anti-adversarial perturbation bound for
noisy samples is the largest, implying that noisy samples exhibit the largest
degree of anti-adversarial training. Thus, the negative influence of noisy
samples can be decreased. The ratio of adversaries for clean samples increases
with the progress of training, demonstrating that clean samples are playing a
more important role than noisy ones during training.

### Experiments of Imbalanced Classification

The long-tailed version of CIFAR10 compiled by Cui et al. (2019) is utilized.
The values of the imbalance factor are set to $10$ and $100$. Here, we only
show the average results when the imbalance factor equals $10$. Others are
presented in the online material. Compared with other methods, CAAT achieves
the minimum average and worst natural and robust errors, as shown in Table 3.
As shown in Fig. 5, CAAT decreases the natural and robust errors for most
classes and achieves the lowest performance gap among different classes. We
also verify that the first head class has the lowest ratio of adversaries and
tail classes have a high ratio of adversaries, which is consistent with our
theoretical findings. The details are presented in the online material.

| Avg. Nat. (%) | Avg. Bdy. (%) | Avg. Rob. (%)
---|---|---|---
Setting I | 16.0 | 41.6 | 57.6
Setting II | 16.1 | 35.8 | 51.9
Setting III | 14.9 | 13.8 | 28.7
Setting IV | 13.9 | 15.4 | 29.3
Table 4: Ablation studies of CAAT on standard CIFAR10.

### Ablation Studies

Four variations of CAAT are considered, including adversarial training with
the same perturbation direction and bound (Setting I), adversarial training
with the same perturbation direction and different bounds (Setting II),
adversarial training with different perturbation directions (adversaries and
anti-adversaries) and the same bound (Setting III), and adversarial training
with different perturbation directions and bounds (Setting IV). PreAct-
ResNet18 is used. The results are shown in Table 4. Settings III and IV obtain
better performance compared with Settings I and II. Thus, the combination
strategy is more effective. Compared with Setting III, Setting IV further
decreases the average natural error, indicating that the varied bound is more
valid in some cases. The worst errors are shown in the online material.

## Conclusions

This study theoretically investigates the role of adversarial training with
different directions (adversarial and anti-adversarial) and bounds for the
robust model. Three typical occasions are considered, including classes with
different difficulties, imbalance learning, and noisy label learning. A series
of theoretical findings are obtained, illuminating a new objective function
that combines adversaries and anti-adversaries in training. Consequently, an
adversarial training framework (CAAT) is proposed to solve the objective, in
which meta learning is utilized to optimize the combined weights of the
adversary and anti-adversary for each sample in accordance with its learning
characteristics. Extensive experiments verify the rationality of our
theoretical findings and the effectiveness of CAAT in achieving better
accuracy, robustness, and fairness of the robust models compared with other
adversarial training methods.

## Acknowledgments

This study is partially supported by NSFC 62076178, TJF 22ZYYYJC00020, and
19ZXAZNGX00050.

## References

  * Alekh et al. (2018) Alekh, A.; Alekh, A.; Alekh, A.; Alekh, A.; and Alekh, A. 2018.  A Reductions Approach to Fair Classification.  In _ICML_ , 102–119.
  * Alfarra et al. (2022) Alfarra, M.; Pérez, J. C.; Thabet, A.; Bibi, A.; Torr, P. H. S.; and Ghanem, B. 2022.  Combating Adversaries with Anti-Adversaries.  In _AAAI_ , 1–13.
  * Bai and Luo (2021) Bai, T.; and Luo, J. 2021.  Recent Advances in Adversarial Training for Adversarial Robustness.  In _IJCAI_ , 4312–4321.
  * Balaji, Goldstein, and Hoffman (2019) Balaji, Y.; Goldstein, T.; and Hoffman, J. 2019.  Instance adaptive adversarial training: Improved accuracy tradeoffs in neural nets.  arXiv:1910.08051.
  * Cheng et al. (2020) Cheng, M.; Lei, Q.; Chen, P.-Y.; Dhillon, I.; and Hsieh, C.-J. 2020.  CAT: Customized Adversarial Training for Improved Robustness.  arXiv:2002.06789.
  * Cui et al. (2019) Cui, Y.; Jia, M.; Lin, T.-Y.; Song, Y.; and Belongie, S. 2019.  Class-Balanced Loss Based on Effective Number of Samples.  In _CVPR_ , 9260–9270.
  * Ding et al. (2020) Ding, G. W.; Sharma, Y.; Lui, K. Y. C.; and Huang, R. 2020.  MMA Training: Direct Input Space Margin Maximization through Adversarial Training.  In _ICLR_ , 1–34.
  * Finn, Abbeel, and Levine (2017) Finn, C.; Abbeel, P.; and Levine, S. 2017.  Model-Agnostic Meta-Learning for Fast Adaptation of Deep Networks.  In _ICML_ , 1856–1868.
  * Goodfellow, Shlens, and Szegedy (2014) Goodfellow, I. J.; Shlens, J.; and Szegedy, C. 2014.  Explaining and Harnessing Adversarial Examples.  arXiv:1412.6572.
  * He et al. (2016) He, K.; Zhang, X.; Ren, S.; and Sun, J. 2016.  Deep Residual Learning for Image Recognition.  In _CVPR_ , 770–778.
  * Krizhevsky (2009) Krizhevsky, A. 2009.  Learning Multiple Layers of Features from Tiny Images.  _Scandinavian Journal of Statistics_.
  * Madry et al. (2018) Madry, A.; Makelov, A.; Schmidt, L.; Tsipras, D.; and Vladu, A. 2018.  Towards Deep Learning Models Resistant to Adversarial Attacks.  In _ICLR_ , 1–18.
  * Netzer et al. (2011) Netzer, Y.; Wang, T.; Coates, A.; Bissacco, R.; Wu, B.; and Ng, A. Y. 2011.  Reading Digits in Natural Images with Unsupervised Feature Learning.  _Scandinavian Journal of Statistics_.
  * Nichol, Achiam, and Schulman (2018) Nichol, A.; Achiam, J.; and Schulman, J. 2018.  On First-Order Meta-Learning Algorithms.  arXiv:1803.02999.
  * Pang et al. (2021) Pang, T.; Yang, X.; Dong, Y.; Su, H.; and Zhu, J. 2021.  Bag of Tricks for Adversarial Training.  In _ICLR_ , 1–21.
  * Raghunathan et al. (2019) Raghunathan, A.; Xie, S. M.; Yang, F.; Duchi, J. C.; and Liang, P. 2019.  Adversarial Training Can Hurt Generalization.  arXiv:1906.06032.
  * Ren et al. (2018) Ren, M.; Zeng, W.; Yang, B.; and Urtasun, R. 2018.  Learning to Reweight Examples for Robust Deep Learning.  In _ICML_ , 6900–6909.
  * Rice, Wong, and Kolter (2020) Rice, L.; Wong, E.; and Kolter, J. Z. 2020.  Overfitting in adversarially robust deep learning.  In _ICML_ , 8093–8104.
  * Santoro et al. (2016) Santoro, A.; Bartunov, S.; Botvinick, M.; Wierstra, D.; and Wierstra, D. 2016.  Meta Learning With Memory-Augmented Neural Networks.  In _ICML_ , 2740–2751.
  * Shu et al. (2019) Shu, J.; Xie, Q.; Yi, L.; Zhao, Q.; Zhou, S.; Xu, Z.; and Meng, D. 2019.  Meta-Weight-Net: Learning an Explicit Mapping For Sample Weighting.  In _NeurIPS_ , 1917–1928.
  * Snell, Swersky, and Zemel (2017) Snell, J.; Swersky, K.; and Zemel, R. S. 2017.  Prototypical Networks For Few Shot Learning.  In _NeurIPS_ , 4078–4088.
  * Song et al. (2020) Song, C.; He, K.; Lin, J.; Wang, L.; and Hopcroft, J. E. 2020.  Robust Local Features for Improving the Generalization of Adversarial Training.  In _ICLR_ , 1–12.
  * Sung et al. (2018) Sung, F.; Yang, Y.; Zhang, L.; Xiang, T.; Torr, P. H.; and Hospedales, T. M. 2018\.  Learning To Compare: Relation Network For Few-Shot Learning.  In _CVPR_ , 1199–1208.
  * Uesato et al. (2019) Uesato, J.; Alayrac, J.-B.; Huang, P.-S.; Stanforth, R.; Fawzi, A.; and Kohli, P. 2019.  Are Labels Required for Improving Adversarial Robustness?  In _NeurIPS_ , 12214–12223.
  * Wang et al. (2020) Wang, Y.; Zou, D.; Yi, J.; Bailey, J.; Ma, X.; and Gu, Q. 2020.  Improving Adversarial Robustness Requires Revisiting Misclassified Examples.  In _ICLR_ , 1–14.
  * Wong, Rice, and Kolter (2020) Wong, E.; Rice, L.; and Kolter, J. Z. 2020.  Fast is better than free: Revisiting adversarial training.  In _ICLR_ , 1–17.
  * Xie et al. (2020) Xie, C.; Tan, M.; Gong, B.; Yuille, A.; and Le, Q. V. 2020.  Smooth Adversarial Training.  arXiv:2002.11242.
  * Xu et al. (2021) Xu, H.; Liu, X.; Li, Y.; Jain, A. K.; and Tang, J. 2021.  To be Robust or to be Fair: Towards Fairness in Adversarial Training.  In _ICML_ , 11492–11501.
  * Yang et al. (2021) Yang, S.; Guo, T.; Wang, Y.; and Xu, C. 2021.  Adversarial Robustness through Disentangled Representations.  In _AAAI_ , 3145–3153.
  * Yang et al. (2020) Yang, Y.-Y.; Rashtchian, C.; Zhang, H.; Salakhutdinov, R.; and Chaudhuri, K. 2020\.  A Closer Look at Accuracy vs. Robustness.  In _NeurIPS_ , 8588–8601.
  * Zagoruyko and Komodakis (2016) Zagoruyko, S.; and Komodakis, N. 2016.  Wide Residual Networks.  In _BMVC_ , 1–12.
  * Zhang et al. (2019) Zhang, H.; Yu, Y.; Jiao, J.; Xing, E. P.; Ghaoui, L. E.; and Jordan, M. I. 2019\.  Theoretically Principled Trade-off between Robustness and Accuracy.  In _ICML_ , 12907–12929.
  * Zhang et al. (2020) Zhang, J.; Xu, X.; Han, B.; Niu, G.; Cui, L.; Sugiyama, M.; and Kankanhalli, M. 2020\.  Attacks Which Do Not Kill Training Make Adversarial Learning Stronger.  In _ICML_ , 1–15.
  * Zhang and Pfister (2021) Zhang, Z.; and Pfister, T. 2021.  Learning Fast Sample Re-weighting Without Reward Data.  In _ICCV_ , 705–714.
  * Zhu et al. (2021) Zhu, J.; Zhang, J.; Han, B.; Liu, T.; Niu, G.; Yang, H.; Kankanhalli, M.; and Sugiyama, M. 2021.  Understanding the Interaction of Adversarial Training with Noisy Labels.  arXiv:2102.03482.


# Reinforcement Learning for Robot Navigation with Adaptive Forward Simulation
Time (AFST) in a Semi-Markov Model

Yu’an Chen, Ruosong Ye, Ziyang Tao, Hongjian Liu, Guangda Chen, Jie Peng, Jun
Ma,
Yu Zhang, Jianmin Ji∗, and Yanyong Zhang∗ School of Computer Science and
Technology, University of Science and Technology of China, Hefei, 230026,
China∗ Corresponding authors<EMAIL_ADDRESS>work is
partially supported by Guangdong Province R&D Program 2020B0909050001, Anhui
Province Development and Reform Commission 2020 New Energy Vehicle Industry
Innovation Development Project and 2021 New Energy and Intelligent Connected
Vehicle Innovation Project, and Shenzhen Yijiahe Technology R&D Co., Ltd.

###### Abstract

Deep reinforcement learning (DRL) algorithms have proven effective in robot
navigation, especially in unknown environments, by directly mapping perception
inputs into robot control commands. However, most existing methods ignore the
local minimum problem in navigation and thereby cannot handle complex unknown
environments. In this paper, we propose the first DRL-based navigation method
modeled by a semi-Markov decision process (SMDP) with continuous action space,
named Adaptive Forward Simulation Time (AFST), to overcome this problem.
Specifically, we reduce the dimensions of the action space and improve the
distributed proximal policy optimization (DPPO) algorithm for the specified
SMDP problem by modifying its GAE to better estimate the policy gradient in
SMDPs. Experiments in various unknown environments demonstrate the
effectiveness of AFST.

##  I Introduction

Autonomous robot navigation with complete maps has been extensively studied in
recent years [1]. However, in many real-world scenarios such as search and
rescue operations [2] or rapidly changing environments [3], global maps are
not always available. Conventional path-planning approaches [4, 5] heavily
rely on accurate, static models of the environment, making them ineffective
when such maps are unknown. Consequently, there is a need for robust
navigation approaches that can help robots navigate in unknown environments
using local perception.

In recent years, Deep reinforcement learning (DRL) algorithms have shown
promising results in navigation tasks in unknown environments [6, 7, 8]. These
data-driven methods learn navigation policies through trial-and-error
exploration combined with carefully designed reward signals. Typically, these
policies directly map perception inputs, such as 2D laser data or local
costmaps, to low-level control commands like translational and rotational
velocities. However, existing methods often overlook the local minima problem
111The local minima problem in robot navigation usually refers to a physical
situation where a robot gets trapped in a suboptimal state while trying to
navigate from its current location to a desired goal [9]., which is more
common and challenging in unknown environments. As a result, they can only
handle relatively simple environments without dead ends. This paper
investigates the use of DRL to address this problem by formulating the
navigation task differently.

Before presenting our method, we introduce two crucial parameters in
conventional navigation methods: forward simulation time (FST) and _control
interval_. FST represents the time for forward-simulating trajectories,
indicating how far ahead the robot plans. Control interval is the reciprocal
of the control frequency, determining the duration of executing each command.
Clearly, the smaller the control interval is, the more timely the robot can
react to its surroundings. However, there usually exists a “sweet value range”
for the choice of FST. If the FST is too small, the robot may be trapped in
local minimums due to short-term planning. Conversely, a longer FST makes it
challenging for the robot to navigate in obstacle-filled environments. Hence,
FST plays a critical role in the performance of classical navigation methods
[10, 11]. In most DRL-based navigation methods, the FST is set equal to the
control interval and they are both equal to a fixed-value action duration. As
mentioned above, these approaches will be plagued by the problems associated
with excessively large or small FST values. Therefore, we propose the
introduction of adaptive FST in DRL navigation, as illustrated in Fig. 1.

Figure 1: Motivation: In the scenarios with different obstacle distributions,
the robot has different ideal forward simulation time (which can be considered
as desired action duration in RL). Therefore, we propose Adaptive Forward
Simulation Time (AFST).

Similar to the idea of adaptive FST, there are existing works in reinforcement
learning that employ dynamic action repetition, allowing the agent to
calculate an action once and repeat it for multiple steps, which results in
lower planning frequency and improved real-time performance [12]. Moreover,
action repetition enables the transitions between distant advantageous states
with a single decision [13, 14]. These transitions are crucial for guiding the
robot to escape from local minimums.

Inspired by dynamic action repetition, we propose Adaptive Forward Simulation
Time (AFST), a DRL-based navigation method capable of handling complex unknown
environments with various obstacle distributions by dynamically adjusting the
FST. To appropriately model this planning problem with different action
durations, we formulate the navigation task as a Semi-Markov Decision Process
(SMDP) (SMDP) [15], where each action comprises three components:
translational velocity, rotational velocity, and duration.

To efficiently adapt the FST, we face the following two main challenges: the
larger volume of the continuous action space that needs to be sampled and the
difficulty in achieving stable improvement despite diverse action durations.
To address the first challenge, we introduce a transformation that converts
our 3D action space into a 2D trajectory parameter space (TP-space) [16]. This
conversion reduces the action space and improves the effectiveness of DRL
training. For the second challenge, we enhance the Distributed Proximal Policy
Optimization (DPPO) [17] for the SMDP problem. We achieve stable improvement
by better estimation of the policy gradient for SMDP. The default policy
estimator of DPPO, Generalized Advantage Estimation (GAE) [18], focuses on MDP
problems. Therefore, we revise the discount rate in GAE to suit our SMDP
problem. The extended GAE (EGAE) allows us to trade off variance and bias in
SMDPs, and we demonstrate that under certain circumstances, EGAE can
theoretically introduce no bias.

We extensively evaluate our approach in both simulated and real-world
scenarios to assess its effectiveness. The experimental results demonstrate
that AFST efficiently accomplishes navigation tasks in unknown environments.
To further validate our method, we conduct ablation experiments that highlight
the effectiveness of each component. Our contributions can be summarized as
follows:

  * •

We propose the first DRL-based navigation method modeled by a SMDP with
continuous action space.

  * •

We provide a transformation that converts the 3D action space to a 2D TP-space
and reduces the training difficulty.

  * •

We improve the DPPO algorithm for the specified SMDP problem by modifying its
GAE to better estimate the policy gradient in SMDPs

##  II Related Work

The navigation problem has been formulated as a SMDP problem before. In
previous work such as [19, 20], SMDP models were used. However, they all use
tabular reinforcement learning algorithms, which limits their state space and
action space. Hence, their generalization and practicability cannot be
compared with DRL-based methods.

DRL-based navigation approaches can be roughly divided into two categories:
methods with agent-level inputs and methods with sensor-level inputs. In
specific, methods with agent-level inputs [21, 22] require expensive motion
data of other robots (like velocities) for the states of the DRL model, and
methods with sensor-level inputs [6, 7, 8, 23, 24] consider sensor inputs as
the states of the DRL model. Our method follows sensor-level inputs.

Many existing methods with sensor-level inputs directly map the sensor-level
inputs into the robot’s low-level control commands. Thus, only transitions
between temporally adjacent states are allowed in their framework, which makes
it difficult to escape the local minimums. A few approaches [25, 26] try to
solve long-horizon tasks by selecting subgoals as actions and reaching
subgoals with a fine-tuned prior policy. These methods use a hierarchical
architecture which is an efficient way to decompose difficult tasks. However,
their performance heavily depends on the fixed prior policy which cannot be
improved during training and requires an extensive amount of engineering
effort. Differently, our policy is entirely learned from interactive
experience with little prior knowledge.

The difference between our method and normal DRL-based methods is that we
introduce the time dimension to the action space. This duration of executing
an action has a significant impact on the exploration efficiency and the
variance of value function estimation in DRL, which has been illustrated in
[13, 14].

##  III Preliminaries

###  III-A Semi-Markov Decision Process.

To treat temporal abstraction as a minimal extension of the reinforcement
learning framework, the theory of semi-Markov Decision Process (SMDP) [15] is
built. A SMDP is a tuple $(S,A,P,R,T,\gamma)$, where $S$ is the state space,
$A$ is the action space, $T$ is the transition time space, and
$\gamma\in(0,1]$ is the discount factor. We assume the environment has
transition dynamics $P\left(s^{\prime},\tau\mid s,a\right)$ which is unknown
to the agent, where $\tau$ represents the time between taking action $a$ in
observed state $s$ and arriving in the next state $s^{\prime}$ and can take a
new action. In general, we are given the reward function $r$ for the reward
after observing $s^{\prime}$. The goal throughout is to learn a policy
maximizing long-term expected rewards
$\mathbb{E}\left[\sum_{i=0}^{L-1}\gamma^{t_{i}}r_{t_{i}}\right]$ with a time
horizon $T=t_{L}$, where $r_{t_{i}}$ is the reward from action $a_{t_{i}}$,
$t_{0}=0$, $t_{i}=\sum_{j=0}^{i-1}\tau_{t_{j}}$, and $\tau_{t_{j}}$ is the
duration of action $a_{t_{j}}$ which is executed from $t_{j}$.

###  III-B Formulation of Navigation in SMDP.

In this paper, we specify the navigation task as a SMDP problem. Specifically,
an action $a$ is formulated as a triple $(v,\omega,d)$, where $v$ and $\omega$
denote the required translational and rotational velocities for the robot, and
$d$ denotes the execution duration for both velocities (i.e. FST). A state $s$
consists of the pose of the robot, i.e., $(x,y,\theta)$ for the robot’s
position $(x,y)$ and the orientation $\theta$, as well as the corresponding
observation of the robot at the position. If there is no collision during the
execution, then the robot would execute the velocities $v$ and $\omega$ for
the time interval $d$, which results in the next state $s^{\prime}$. However,
the robot may collide and end an action before completing its given execution
duration, which results in the transition dynamics $P\left(s^{\prime},\tau\mid
s,a\right)$, with $\tau\in[0,d]$ denoting the actual execution time. A policy
$\pi(a\mid s)$ specifies the probability of taking action $a$ at state $s$.
The reward function $r$ encourages the navigation policy to avoid collisions
and arrive at the target position as soon as possible.

###  III-C Trajectory Parameter Space with Velocities

To reduce the action space and increase the probability of sampling the
appropriate actions, we convert our 3D action space to a 2D trajectory
parameter space (TP-space) [27] for planning and convert the action back to 3D
for actual execution.

A trajectory parameter space is a 2D space where each point corresponds to a
drivable trajectory for a robot. The basic idea is that a sequence of robot’s
pose in 3D space $(x,y,\theta)$ can be charted employing 2D manifolds in the
parameter space of a family of trajectories.

In this paper, we consider differential-drive robots, which only move along
circular trajectories due to their movement restrictions. Then we improve the
original circular parameter trajectory generator (C-PTG)222The original C-PTG
assumes that the robot moves along the path with the maximum translational
velocity all the time, which ignores the kinematic constraint of rotational
velocities. Our revision not only considers this constraint but also removes
the assumption of translational velocity. [27] and uses a 2D virtual action
$(v^{\textit{TP}},\omega^{\textit{TP}})$ to parameterize the trajectories with
a predefined fixed time scale $\tau^{\textit{TP}}$. We call it virtual action
because $v^{\textit{TP}}$ and $\omega^{\textit{TP}}$ are virtual translational
and rotational velocities in TP-space, which are not limited by the actual
robot’s maximum translational velocity $v_{m}$ and rotational velocity
$\omega_{m}$.

Assume the robot starts from the initial point $(0,0)$ and executes the
virtual action $(v^{\textit{TP}},\omega^{\textit{TP}})$ for a time interval
$\tau^{\textit{TP}}$. The path that the robot moves along is the same as the
paths of the set $\Phi$ of executable actions, such that

$\Phi=\left\\{(v,\omega,d)\mid v\,d=v^{\textit{TP}}\,\tau^{\textit{TP}}\text{
and }\frac{v}{\omega}=\frac{v^{\textit{TP}}}{\omega^{\textit{TP}}}\right\\}.$

If we want the robot to move along this path in the shortest possible time, we
can convert the virtual action $(v^{\textit{TP}},\omega^{\textit{TP}})$ to a
unique executable action $(v,\omega,d)$, i.e.,

$\displaystyle v$ $\displaystyle=\frac{v^{\textit{TP}}}{k},$
$\displaystyle\omega$ $\displaystyle=\frac{\omega^{\textit{TP}}}{k},$
$\displaystyle d$ $\displaystyle=k\,\tau^{\textit{TP}},$ (1)

where $k$ is a real number, with
$k=\max(\frac{v^{\textit{TP}}}{v_{m}},\,\frac{\omega^{\textit{TP}}}{\omega_{m}})$.
In this way, we only need to consider the most efficient action $(v,\omega,d)$
for the navigation policy, instead of all possible actions in $\Phi$. Hence,
we reduce the action space.

##  IV Extending GAE for SMDP

In reinforcement learning, events (e.g., a robot collides) in the far future
are weighted less than events in the immediate future. In our scheme, an
action’s execution duration can determine when an event will take place in the
future, and thus also determine the event’s weight. However, original
generalized advantage estimation (GAE) [18] focuses on MDPs and does not
consider such impact of execution duration. To address this issue, we improve
GAE to estimate the policy gradient in SMDPs.

First, we introduce the definitions of the state value function
$V^{\pi_{\theta}}$, the state-action value function $Q^{\pi_{\theta}}$, and
the advantage function $A^{\pi_{\theta}}$ in SMDP, i.e.,

$\displaystyle V^{\pi_{\theta}}(s_{t_{i}})$
$\displaystyle=\mathbb{E}_{\rho\sim
p_{\theta}(\rho_{s_{t_{i}}})}\Big{[}\sum_{j=0}^{\infty}\gamma^{z_{i}^{j}}r_{t_{i+j}}\Big{]},$
$\displaystyle Q^{\pi_{\theta}}(s_{t_{i}},a_{t_{i}})$
$\displaystyle=\mathbb{E}_{\rho\sim
p_{\theta}(\rho_{{s_{t_{i}},a_{t_{i}}}})}\Big{[}\sum_{j=0}^{\infty}\gamma^{z_{i}^{j}}r_{t_{i+j}}\Big{]},$
$\displaystyle A^{\pi_{\theta}}(s_{t_{i}},a_{t_{i}})$
$\displaystyle=Q^{\pi_{\theta}}(s_{t_{i}},a_{t_{i}})-V^{\pi_{\theta}}(s_{t_{i}}),$

where $\rho_{s_{t_{i}}}$ (resp. $\rho_{s_{t_{i}},a_{t_{i}}}$) denotes the
episode starting from the state $s_{t_{i}}$ (resp. the state $s_{t_{i}}$ and
the action $a_{t_{i}}$), and
$z_{i}^{j}=t_{i+j}-t_{i}=\sum_{k=i}^{k=i+j-1}\tau_{t_{k}}$.

An advantage estimator $\hat{A}_{\rho}$ denotes the estimation of the
advantage function by considering the episode $\rho$. Given an approximate
state value function $\hat{V}$, for each $k\geq 1$ we define the advantage
function of $k$ step

$\hat{A}_{\rho}^{(k)}(s_{t_{i}},a_{t_{i}})=\sum_{j=0}^{k-1}\gamma^{z_{i}^{j}}\delta_{t_{i+j}}^{\hat{V}}=\\\
-\hat{V}(s_{t_{i}})+r_{t_{i}}+\gamma^{z_{i}^{1}}r_{t_{i+1}}+\cdots+\gamma^{z_{i}^{k-1}}r_{t_{i+k-1}}+\gamma^{z_{i}^{k}}\hat{V}(s_{t_{i+k}}),$

where $z^{j}_{i}=t_{i+j}-t_{i}$ and
$\delta_{t_{i+j}}^{\hat{V}}=r_{t_{i+j}}+\gamma^{z_{i+j}^{1}}\hat{V}(s_{t_{i+j+1}})-\hat{V}(s_{t_{i+j}})$.
In particular,

$\displaystyle\hat{A}_{\rho}^{(1)}(s_{t_{i}},a_{t_{i}})$
$\displaystyle=\delta_{t_{i}}^{\hat{V}},$
$\displaystyle\hat{A}_{\rho}^{(\infty)}(s_{t_{i}},a_{t_{i}})$
$\displaystyle=-\hat{V}(s_{t_{i}})+\sum_{j=0}^{\infty}\gamma^{z_{i}^{j}}r_{t_{i+j}}.$

Then we define EGAE $\hat{A}_{\rho}^{\text{EGAE}}$

$\displaystyle\hat{A}_{\rho}^{\text{EGAE}}(s_{t_{i}},a_{t_{i}})$
$\displaystyle=(1-\lambda)\left(\hat{A}_{\rho}^{(1)}(s_{t_{i}},a_{t_{i}})+\lambda\hat{A}_{\rho}^{(2)}(s_{t_{i}},a_{t_{i}})+\cdots\right)$
$\displaystyle=(1-\lambda)\left(\delta_{t_{i}}^{\hat{V}}+\lambda\left(\delta_{t_{i}}^{\hat{V}}+\gamma^{z_{1}^{i}}\delta_{t_{i+1}}^{\hat{V}}\right)+\cdots\right)$
$\displaystyle=\sum_{j=0}^{\infty}\gamma^{z_{i}^{j}}\lambda^{j}\delta_{t_{i+j}}^{\hat{V}},$

where $\lambda\in[0,1]$ is a hyperparameter representing the compromise
between bias and variance. Similar to GAE, the increase of $\lambda$ results
in the increase of the variance and the decrease of the bias. In the settings
of SMDPs, we prove that EGAE can theoretically be an estimator that introduces
no bias when $\lambda=1$ or $\hat{V}$ is accurate. The detailed derivation
process and more research on the properties of EGAE are presented in the
appendix333https://github.com/YohannnChen/AFST/blob/main/appendix.pdf. The
appendix material mentioned below can also be found at this link..

##  V Approach

In this section, we present details on how to apply Distributed Proximal
Policy Optimization (DPPO) [17] to the SMDP problem with the adoption of EGAE.
DPPO is a distributed implementation of Proximal Policy Optimization (PPO)
[28]. We consider DPPO in the paper as PPO and its extensions are widely
applied in DRL-based robot navigation due to their simplicity, stability, and
high sample efficiency [3, 7, 23, 25]. More importantly, it is a policy-based
DRL algorithm, which can learn stochastic policies. Notice that, for a
navigation policy that drives the robot in unknown environments, it would
frequently face aliased states [29] due to its partial observation of the
environment, while a stochastic policy can help the robot to address the
problem.

###  V-A Reinforcement Learning Components.

####  V-A1 _State_

a state $s_{t_{i}}$ consists of the egocentric local grid map $M_{t_{i}}$ and
the relative target pose $g_{t_{i}}$ of the robot as shown in the Fig. 3. In
our experiment, $M_{t_{i}}$ is generated from the data of a 2D laser scan with
a 180-degree horizontal Field of View (FOV), which encodes the robot’s shape
and observable appearances of nearby obstacles. We construct the egocentric
local grid map $M_{t_{i}}$ in the same way as [23].

####  V-A2 _Action_

an executable action $a_{t_{i}}$ for the robot is a triple
$(v_{t_{i}},\omega_{t_{i}},d_{t_{i}})$. We adopt the conversion illustrated in
Sec. III-C to reduce the action space. Here, we introduce the processing
process from 2D raw actions to 3D executable actions as shown in Fig. 3.
Firstly, the output of the last layer is added by a Gaussian noisy
$a_{t_{i}}^{logstd}$ for exploration. Then, we get the raw action
$a_{t_{i}}^{raw}$. Secondly, we specify an activation function with a modified
exponential linear unit (ELU) [30] to convert the raw action $a_{t_{i}}^{raw}$
to a 2D virtual action $a_{t_{i}}^{TP}$, where
$a_{t_{i}}^{raw}=(v^{\textit{raw}}_{t_{i}},\omega^{\textit{raw}}_{t_{i}})$,
$a_{t_{i}}^{TP}=(v^{TP}_{t_{i}},\omega^{TP}_{t_{i}})$,

$\displaystyle v^{TP}_{t_{i}}$
$\displaystyle=\left\\{\begin{array}[]{ll}0.2e^{5v^{\textit{raw}}_{t_{i}}-1}&\text{
if }v^{\textit{raw}}_{t_{i}}<0.2,\\\ v^{\textit{raw}}_{t_{i}}&\text{
otherwise, }\end{array}\right.$ (2) $\displaystyle\omega^{TP}_{t_{i}}$
$\displaystyle=\omega^{\textit{raw}}_{t_{i}}.$

We adopt the ELU as it can improve the robustness to noise when the robot
needs subtle movements to pass through dense obstacles. As shown in Fig. 2,
our ELU gradually saturate to zero when the argument gets smaller. We can
observe that the smaller the argument is, the slower the gradient vanishes,
which preserves ELU’s property of refining the granularity of small values.

Figure 2: Our modified ELU

This is why the ELU has the characteristic of soft saturation and improves the
robustness to noise. The parameters of the ELU influence the probability
distribution of the different actions sampled by the initial policy. Tested by
experiments, we find that the ELU’s parameters in Eq. (2) are preferable.
Finally, $a_{t_{i}}^{TP}$ can be converted to $a_{t_{i}}$ for execution by Eq.
(1).

####  V-A3 _Reward_

the reward $r_{t_{i}}$ consists of four components, i.e.,

$\displaystyle r_{t_{i}}$
$\displaystyle=r^{app}_{t_{i}}+r^{arr}_{t_{i}}+r^{col}_{t_{i}}+r^{step}_{t_{i}},$
$\displaystyle r^{app}_{t_{i}}$
$\displaystyle=\varepsilon_{a}\left(\left\|{l}_{t_{i-1}}-l_{g}\right\|-\left\|{l}_{t_{i}}-l_{g}\right\|\right),$
$\displaystyle r^{arr}_{t_{i}}$
$\displaystyle=\left\\{\begin{array}[]{ll}r_{arr}&\text{ if
}\left\|{l}_{t_{i}}-l_{g}\right\|<0.3,\\\ 0&\text{
otherwise,}\end{array}\right.$ $\displaystyle r^{coll}_{t_{i}}$
$\displaystyle=\left\\{\begin{array}[]{ll}r_{col}&\text{ if collision},\\\
0&\text{ otherwise,}\end{array}\right.$ $\displaystyle r^{step}_{t_{i}}$
$\displaystyle=-\varepsilon_{t}\tau_{t_{i}}-\varepsilon_{\tau}\tau^{\textit{TP}},$

where $l_{t_{i}}$ (resp. $l_{g_{t_{i}}}$) denotes the location of the robot
(resp. target $g_{t_{i}}$) at the current time $t_{i}$, $\tau_{t_{i}}$ denote
the actual execution duration of $a_{t_{i}}$, $r_{arr}>0$, $r_{col}<0$,
$\varepsilon_{a}>0$, $\varepsilon_{t}>0$, and $\varepsilon_{\tau}>0$ are
hyperparameters.

In particular, $r^{app}_{t_{i}}$ defines the penalty for departure from the
target, $r^{arr}_{t_{i}}$ defines the reward for arrival at the target,
$r_{col}$ defines the penalty for collisions, and $r^{step}$ defines a minor
penalty for each action. $\varepsilon_{t}$ is set to penalize the execution
time of the action, which encourages the robot to reach the goal faster.
$\varepsilon_{\tau}$ is the coefficient of a fixed penalty for every action,
which encourages the robot to reach the goal with fewer planning times. In our
experiment, we set $r_{arr}=500$, $r_{col}=-500$, $\varepsilon_{a}=200$,
$\varepsilon_{t}=12$, and $\varepsilon_{\tau}=10$.

Figure 3: We use DPPO to solve the navigation problem modeled in a SMDP. Above
is the architecture of our policy network. The input of the network is
$s_{t_{i}}$, which consists of the local grid map $M_{t_{i}}$ and the relative
target pose $g_{t_{i}}$. The output of the last layer is added by a Gaussian
noisy $a_{t_{i}}^{logstd}$ and gets the raw action $a_{t_{i}}^{raw}$. Then we
use a specified activation function with an ELU to process it and get the 2D
virtual action $a_{t_{i}}^{TP}$. Finally, we convert $a_{t_{i}}^{TP}$ to 3D
action $a_{t_{i}}$ for execution according to Eq. (1)

###  V-B Network Architecture.

The architecture of our policy network $\pi_{\theta}$ is shown in Figure 3.
Our value network has the same architecture as the policy network, except that
the last layer is modified to only output the value function $V_{\phi}$
without the Gaussian noise and the activation function.

###  V-C Training Process.

We replace GAE with EGAE in DPPO. Then the objective function for the policy
network $\pi_{\theta}$ is

$\displaystyle L^{\pi}_{\theta_{k}}(\theta)$
$\displaystyle=\mathbb{E}_{s,a\sim\theta_{k}}\Big{[}\min\Big{(}\frac{\pi_{\theta}(a\mid
s)}{\pi_{\theta_{k}}(a\mid s)}\hat{A}_{\rho}^{\text{EGAE}}(s,a),$
$\displaystyle\hskip
99.58464ptg(\epsilon,\,\hat{A}_{\rho}^{\text{EGAE}}(s,a))\Big{)}\Big{]},$
$\displaystyle g(\epsilon,\hat{A})$
$\displaystyle=\left\\{\begin{array}[]{ll}(1+\epsilon)\hat{A}&\text{ if
}\hat{A}\geqslant 0\\\ (1-\epsilon)\hat{A}&\text{
otherwise,}\end{array}\right.$

where $\theta_{k}$ denotes the parameters of the policy at the $k$th epoch and
$\epsilon$ is the clip ratio.

The objective function for the value network $V_{\phi}$ is

$\displaystyle L^{V^{\pi}}_{\phi}(\phi)$
$\displaystyle=-\mathbb{E}_{s,\rho_{s}\sim\pi}\Big{[}\Big{(}R(\rho_{s})-V_{\phi}(s)\Big{)}^{2}\Big{]},$

where $\rho_{s}$ denotes the episode starting from the state $s$ and $\phi$
denotes the parameters of the value function. $L^{\pi}_{\theta_{k}}(\theta)$
and $L^{V^{\pi}}_{\phi}(\phi)$ will both be estimated per iteration by all the
data in the experience buffer.

Algorithm 1 Adaptive Forward Simulation Time (AFST)

1: Initialize the policy network $\pi_{\theta}$, the value network $V_{\phi}$.

2: Clear the experience buffer _Buffer_.

3: for  _epoch_ $k=1,2,...,$ do

4:  _//collect data in parallel_

5: for  _step_ $i=0,1,...,T_{ep}$ do

6: $a_{t_{i}}^{raw}=\pi_{\theta}(s_{t_{i}});V_{t_{i}}=V_{\phi}(s_{t_{i}})$

7: Transfer $a_{t_{i}}^{raw}$ to $a_{t_{i}}$ according to Eq. (2), Eq. (1)

8: $s_{t_{i+1}},r_{t_{i}}=\emph{step}(a_{t_{i}})$

9: Add $(s_{t_{i}},a_{t_{i}}^{raw},r_{t_{i}},V_{t_{i}})$ to _Buffer_

10: $s_{t_{i}}\leftarrow s_{t_{i+1}}$

11: if $\emph{trajectory length}>T_{m}$ or _arrive_ or _collide_ then

12: Finish the current episode $\rho$ by $V_{t_{i+1}}=0$

13: Estimate $\hat{A}_{\rho}^{\text{EGAE}}(s_{t_{j}},a_{t_{j}})$ for all
$(s_{t_{j}},a_{t_{j}})$ in $\rho$

14: Add each $\hat{A}_{\rho}^{\text{EGAE}}(s_{t_{j}},a_{t_{j}})$ to _Buffer_

15: Add each $R(\rho_{s_{t_{j}}})$ to _Buffer_

16: $s_{t_{i}}=\emph{reset()}$

17: end if

18: end for

19: Update $\pi_{\theta}$ with $L^{\pi}_{\theta_{k}}(\theta)$ and
$lr_{\theta}$ for $E_{\pi}$ iterations

20: Update $V_{\phi}$ with $L^{V^{\pi}}_{\phi}(\phi)$ and $lr_{\phi}$ for
$E_{v}$ iterations

21: Clear _Buffer_

22: end for

As illustrated in Figure 4(a), we train the networks in environments that are
constructed by a customized simulator based on OpenCV with Algorithm 1. In
particular, the simulator can load an environment as a gray image, where
obstacles and robots are specified as corresponding pixels in the image. In
DPPO, the algorithm collects experiences in a distributed setting from
multiple environments where robots share the same navigation policy
$\pi_{\theta}$.

##  VI Experiments

In this section, we present the simulated and physical evaluation methods.
Their results both validate our hypothesis that AFST can achieve better
performance in complex unknown environments.

###  VI-A Implementation Details

We specify two modes to implement the navigation policy:

  * •

_Mode1_ : the _control interval_ is equal to FST, which means executing the
action as long as the algorithm plan ahead.

  * •

_Mode2_ : the _control interval_ is set to a fixed small value, which means
that no matter how long the FST is planned, the robot will replan the next
action after executing the current action for the fixed small interval.

In most cases, we use _Mode1_ , such as simulation training, simulation
testing, and physical experiments in static scenarios. _Mode2_ is used in
physical experiments with dynamic obstacles for better safety. We set the
fixed _control interval_ of _Mode2_ to $0.1s$.

In our experiments, we use a turtlebot2, a differential drive, a circular
robot with a radius of $0.17m$, the maximum velocities of which are
$v_{m}=0.6$ m/s and $\omega_{m}=0.9$ rad/s. The local grid maps are $6m\times
6m$. The robot is in the middle of the local map and can only perceive the
information around $3m$ thereby cannot plan too far ahead. These settings are
the same in both simulation and real-world experiments.

We train the AFST with hyperparameters listed in the appendix. In the
experiments, we find out that almost every value of $\tau^{\textit{TP}}$
results in a similar success rate444Detailed evaluations can be found in the
appendix.. Among the values of $\tau^{\textit{TP}}$, $0.4s$ is slightly
better. Both the policy and value networks are implemented in TensorFlow and
trained with the Adam optimizer on a computer with i7-9900 CPU and Nvidia
Titan RTX GPU. It takes around 10 hours to run about 1100 epochs in DPPO when
the networks converge in the training.

###  VI-B Simulated Experiments

####  VI-B1 Training and Testing Scenarios

(a) Sparse

(b) Dense

(c) Spiral

(d) Zigzag

(e) Hybrid

Figure 4: We consider five scenarios in our experiments and their global top
views are shown as above, where yellow curves denote the navigation paths of
the robot, the yellow dots denote the planning moment, the green boxes denote
the random region of the starting position, and the blue boxes denote the
random region of the target position. We can see in the red boxes that our
robot can adjust its forward simulation time to adapt to multiple spatial
features and obstacle densities. More importantly, our robot successfully
escapes the local minimums marked with red circles.

Figure 4 illustrates five different scenarios that are considered in our
experiments. Please note that we only consider environments in _sparse_
scenario as training environments and evaluate the performance in these five
scenarios:

  * •

_Sparse_ scenario is $10m\times 10m$ and randomly chooses locations for 6
randomly sized obstacles. The starting and the target positions of the robot
are also randomly chosen. So much randomness is to avoid overfitting.

  * •

_Dense_ scenario is $10m\times 10m$ and randomly choose locations for 32 small
obstacles. The starting and the target positions are also randomly chosen.

  * •

_Spiral_ scenario is $6m\times 6m$, using a spiral map with 5 small obstacles,
the starting, and the target positions are fixed.

  * •

_Zigzag_ scenario is $6m\times 6m$, using a zigzag map with 5 small obstacles,
where the starting and target positions are fixed.

  * •

_Hybrid_ scenario is $10m\times 10m$, combining the characteristics of _Dense_
and _Zigzag_ scenarios, where the locations of 32 obstacles, the starting, and
the target position are randomly chosen.

####  VI-B2 Comparison Baselines and Evaluation Metrics

We compare AFST with four baseline methods, i.e.,

  * •

_DWA_ : Dynamic Window Approach [10], an elegant and classical local planner,
with a fixed forward simulation time, which is set to 3s in our experiments.

  * •

_CAMDRL_ : Collision Avoidance via Map-Based Deep Reinforcement Learning
(CAMDRL) [23], a map-based robot navigation method with fixed action duration.
Its inputs of the network are local maps generated by the data of the laser.
The original GAE is applied to it.

  * •

_GO-DWA_ : Goal-Oriented Dynamic Window Approach (GO-DWA), a hierarchical
planning approach that selects subgoals as actions and reaches the subgoals
with DWA. We refer to the scheme and the action space of GO-MPC [25] and
replace its MPC with DWA.

  * •

_SDDQN_ : Semi-Markov DoubleDQN [31], a DRL-based method to solve SMDP
problems with discrete action space. We set the range of the translational
velocity $v\in\\{0,0.3,0.6\\}$, the rotational velocity
$\omega\in\\{-0.9,0,0.9\\}$, the planning duration
$d\in\\{0.4,0.8,1.2,1.6,2.0\\}$.

For a fair comparison, all methods share the same laser data as the input, all
DRL-based methods use the same reward function as AFST. The action duration in
CAMDRL is set to a fixed value of 0.4s as [23] does.

We use _success rate_ (SR) and _reach time_ (RT) to evaluate the performance.
The _success rate_ is the ratio of tests that the robot reaches its target
within 200 steps without any collision. The _reach time_ is the average time
taken by the robot to reach the target. The evaluation results of trajectory
length are presented in the appendix.

Table I: Evaluation results of different methods Metric | Method | #scenario |  |  |  | Average
---|---|---|---|---|---|---
|  | Sparse | Dense | Spiral | Zigzag | Hybrid
Success | DWA | 0.616 | 0.618 | 0 | 0 | 0.002 | 0.248
rate | CAMDRL | 0.782 | 0.760 | 0 | 0 | 0.542 | 0.418
(SR) | GO-DWA | 0.886 | 0.700 | 0.610 | 0.082 | 0.206 | 0.498
| SDDQN | 0.868 | 0.854 | 0.826 | 0.078 | 0.624 | 0.650
| AFST | 0.946 | 0.910 | 1.00 | 0.904 | 0.778 | 0.908
Reach | DWA | 39.8 | 20.4 | / | / | 37.6 | /
time | CAMDRL | 19.2 | 11.2 | / | / | 28.3 | /
(RT) | GO-DWA | 35.0 | 22.5 | 31.0 | 23.5 | 38.0 | 30.0
| SDDQN | 26.0 | 14.6 | 30.9 | 127 | 46.3 | 49.0
| AFST | 16.9 | 9.61 | 23.1 | 39.5 | 34.2 | 24.7
Table II: Results of an ablation study Metric | Method | #scenario |  |  |  | Average
---|---|---|---|---|---|---
|  | Sparse | Dense | Spiral | Zigzag | Hybrid
Success | -ELU | 0.936 | 0.840 | 0.990 | 0.532 | 0.556 | 0.771
rate | -2D-to-3D | 0.860 | 0.850 | 0.104 | 0 | 0.588 | 0.481
(SR) | -EGAE | 0.760 | 0.646 | 0.228 | 0 | 0.436 | 0.414
| -SMDP | 0.944 | 0.906 | 1.00 | 0.804 | 0.686 | 0.868
| AFST | 0.946 | 0.910 | 1.00 | 0.904 | 0.778 | 0.908
Reach | -ELU | 17.2 | 9.03 | 27.0 | 51.1 | 26.1 | 26.1
time | -2D-to-3D | 17.4 | 9.78 | 79.4 | / | 34.4 | /
(RT) | -EGAE | 17.5 | 9.16 | 33.4 | / | 31.2 | /
| -SMDP | 17.0 | 11.0 | 23.7 | 37.5 | 27.9 | 23.4
| AFST | 16.9 | 9.61 | 23.1 | 39.5 | 34.2 | 24.7

####  VI-B3 Testing Results

Table I summarizes the test results using _Mode1_. In every scenario, we
performed 500 tests for each model. We detail our observations below:

_The performance of DWA_ : DWA has inherent safety rules in that the robot is
only allowed to take collision-free actions (assuming obstacles are static).
However, DWA cannot achieve $100\%$ SR as the robot may get trapped in the
local minimum. This problem causes the SR of DWA to be decreased to zero in
some scenarios and its RT to be increased in others.

_The performance of CAMDRL_ : As a method with fixed action duration, CAMDRL
has a tolerable SR in _sparse_ and _dense_ scenarios as local minima areas
don’t occur very often with randomly located obstacles. However, it is
entirely trapped in the local minimums of _spiral_ and _zigzag_ scenarios, the
detailed analysis of this phenomenon is presented in the appendix. This
phenomenon is mitigated in _hybrid_ scenario as the sizes of their obstacles
are smaller than the ones in _zigzag_ scenario.

_The performance of GO-DWA_ : GO-DWA achieves a high SR in _sparse_ scenario.
However, we find out that it is difficult for GO-DWA to select an accurate
local goal between dense obstacles. In some cases, these local goals will
overlap with obstacles, which leads to the limited generalization of GO-DWA.

_The performance of SDDQN_ : SDDQN’s performance is the closest to AFST, which
indicates the advantage of using SMDP models. But its deterministic policy is
not as good at handling aliased states as stochastic policy as mentioned in
Sec. V. Besides, SDDQN’s discrete action space limits its generalization.
Therefore, SDDQN has a lower SR and longer RT than AFST in testing scenarios.

_The performance of AFST_ : AFST achieves the highest SR in all testing
scenarios. The high SR and the trajectories in Fig. 4 prove it can adjust the
FST to a proper small value when running through the narrow gaps (Fig. 4(a)),
and can adjust the FST to a proper big value when escaping the local
minimums(Fig. 4(d)). Although the SR of AFST in the training scenario is not
much higher than that of other methods, its SR in unseen testing scenarios is
distinctly higher, which indicates its excellent generalization. Moreover,
AFST has the shortest mean RT as it always moves with the maximum speed
according to Eq. (1) and can escape from local minimums with fewer failed
attempts.

####  VI-B4 Ablation Studies

We also conduct ablation studies to investigate the utility of several
modifications we propose in our scheme. Specifically, ‘-ELU’ means replacing
the modified ELU with the ReLu [32], ‘-2D-to-3D’ means directly outputting 3D
actions without the 2D-to-3D conversion, ‘-EGAE’ means replacing EGAE with
TD(0) in the settings of the SMDP, and ‘-SMDP’ means formulating the problem
as a lifted MDP555We can also model the problem with different action duration
as a MDP. Because the wall time between successive time steps is not forced to
be uniform in MDPs. The fixed discount rate $\gamma$ in ‘-SMDP’ is $0.99$. and
using GAE to evaluate the advantage function. The results are shown in Table
II. In general, we find the above modifications nearly all lead to performance
improvements.

Table III: Performance of methods in real-world scenarios Metrics | Method | #scenario |
---|---|---|---
|  | Scatter1 | Scatter2 | Spiral | Zigzag
Success | CAMDRL | 1.0 | 0.9 | 0 | 0
rate | AFST | 1.0 | 1.0 | 1.0 | 1.0
Planning | CAMDRL | 9.16 | 10.42 | / | /
time | AFST | 0.62 | 1.98 | 4.14 | 1.24
Reach | CAMDRL | 13.23 | 27.16 | / | /
time | AFST | 13.18 | 25.21 | 24.06 | 28.17

ELU has the characteristic of soft saturation, which improves the robustness
to noise. Therefore, ‘-ELU’ is less robust for long-distance navigation tasks
and can almost only achieve short-distance tasks. This is the reason why
‘-ELU’ has lower SR but shorter RT compared with AFST in _Dense_ and _Hybrid_
scenarios. Without the 2D-to-3D conversion, the action space would be much
larger, which makes it much harder to sample proper actions and learn
successful policies. Hence, the SR of ‘-2D-to-3D’ is low, indicating the
conversion’s effectiveness. TD(0) estimates the advantage function with a low
variance but high bias. Thus the performance of ‘-EGAE’ is poor. For the
detailed implementation, the only difference between ‘-SMDP’ and AFST is the
power of the discount rate. The experimental results show that ‘-SMDP’
achieves similar performance to AFST. In some scenarios, it is hard to
distinguish their effectiveness. However, MDPs can hardly evaluate the value
function on an equitable time scale as SMDPs. The rewards gained from
different execution duration will be multiplied by the same discount rate,
encouraging long-duration actions. Then, the policy of ‘-SMDP’ is a little
more aggressive than the one of AFST. Then, the average SR of ‘-SMDP’ is lower
than AFST and the average RT is shorter. The results of the ablation study
show that each of our components plays a considerable role in the algorithm.

Figure 5: We conduct real-world experiments on a TurtleBot 2 with a Kobuki
base using a Hokuyo UTM-30LX 2D LiDAR and an NVIDIA Jetson TX2 (shown in (a)).
We consider four static scenarios: Scattered1 (b), Scattered2 (c), Spiral (d),
Zigzag (e), and a dynamic scenario (f) (with dynamic obstacles and
pedestrians).

###  VI-C Physical Experiments

To further verify the generalization and effectiveness of our learning policy,
we deployed the trained model of AFST and CAMDRL to an actual differential-
drive robot in the real world as illustrated in Figure 5.

We placed paper boxes as obstacles to set up the test environments. To make a
fair comparison, we conducted quantitative experiments in the four static
scenarios and qualitative experiments in the dynamic scenario. In the static
scenarios, we implemented AFST using _Mode1_. For each method, we conducted 10
tests in every static scenario. As shown in Table III, AFST can reach the
target with less planning time than CAMDRL as AFST usually plans for a longer
execution duration per step and AFST’s network architecture is more
lightweight. Moreover, CAMDRL cannot get out of the local minimums in some
difficult scenarios. Hence, AFST can not only tackle more difficult navigation
tasks in unknown scenarios but also has the potential to navigate faster with
less computational overhead.

In addition, we also set up environments with dynamic obstacles and
pedestrians. In the _dynamic_ scenario, we use _Mode2_ to implement AFST. The
demonstration video on both simulation and real-world experiments can be found
at https://youtu.be/pgP5BQHFum4.

##  VII Discussions

###  VII-A Limitations and Future Works

####  VII-A1 _Dynamic collision avoidance_

In this paper, AFST only uses one frame of the local map for collision
avoidance thereby cannot extract any dynamic information, which makes it
inefficient for AFST to avoid dynamic obstacles. Besides, it is hard for the
robot to react to dynamic obstacles in a timely manner only training with
_Mode1_. We will further develop the potential of _Mode2_ in dynamic
scenarios.

####  VII-A2 _Robustness and safety_

Similar to many learning-based navigation methods, AFST is not as robust as
optimization-based methods. The inherent exploration capabilities of AFST help
it get out of local minimums, but it also increases the uncertainty of
obstacle avoidance. Therefore, AFST should be tested in more complex scenarios
and add more safety constraints in the future.

####  VII-A3 _Kinematical constraints and smoothness_

The transformation in TP-space assumes that the robot would move with the
maximum translational velocity or rotate with the maximum rotational velocity
in the environment, which is a common simplification for low-speed robots.
However, this assumption is unrealistic for high-speed robots. One of our
future works is to extend AFST for considering the Kinedynamics constraints of
the robot and the smoothness of its trajectories.

###  VII-B Conclusion

In this paper, we focus on robot navigation in unknown environments. To make
the robot adapt to more diverse obstacle distribution, we propose AFST, which
is the first DRL-based navigation method modeled by a SMDP with continuous
action space. We show that AFST outperforms several baseline schemes under
multiple scenarios both in simulation and the real world. We also conduct
ablation experiments to indicate the effectiveness of our components.

## References

  * [1] S. M. LaValle, _Planning algorithms_. Cambridge university press, 2006.
  * [2] F. Niroui, K. Zhang, Z. Kashino, and G. Nejat, “Deep reinforcement learning robot for search and rescue applications: Exploration in unknown cluttered environments,” _IEEE Robotics and Automation Letters_ , vol. 4, no. 2, pp. 610–617, 2019.
  * [3] E. Marchesini, D. Corsi, and A. Farinelli, “Benchmarking safe deep reinforcement learning in aquatic navigation,” in _Proceedings of the 34th International Conference on Intelligent Robots and Systems (IROS-2021)_. IEEE, 2021, pp. 5590–5595.
  * [4] B. Bonet and H. Geffner, “Planning as heuristic search,” _Artificial Intelligence_ , vol. 129, no. 1-2, pp. 5–33, 2001.
  * [5] J. Nasir, F. Islam, U. Malik, Y. Ayaz, O. Hasan, M. Khan, and M. S. Muhammad, “Rrt*-smart: A rapid convergence implementation of rrt,” _International Journal of Advanced Robotic Systems_ , vol. 10, no. 7, p. 299, 2013.
  * [6] L. Tai, G. Paolo, and M. Liu, “Virtual-to-real deep reinforcement learning: Continuous control of mobile robots for mapless navigation,” in _Proceedings of the 30th International Conference on Intelligent Robots and Systems (IROS-2017)_. IEEE, 2017, pp. 31–36.
  * [7] M. Pfeiffer, S. Shukla, M. Turchetta, C. Cadena, A. Krause, R. Siegwart, and J. Nieto, “Reinforced imitation: Sample efficient deep reinforcement learning for mapless navigation by leveraging prior demonstrations,” _IEEE Robotics and Automation Letters_ , vol. 3, no. 4, pp. 4423–4430, 2018\.
  * [8] E. Marchesini and A. Farinelli, “Discrete deep reinforcement learning for mapless navigation,” in _Proceedings of the 37th International Conference on Robotics and Automation (ICRA-2020)_. IEEE, 2020, pp. 10 688–10 694.
  * [9] M. Wang and J. N. Liu, “Fuzzy logic-based real-time robot navigation in unknown environment with dead ends,” _Robotics and autonomous systems_ , vol. 56, no. 7, pp. 625–643, 2008.
  * [10] D. Fox, W. Burgard, and S. Thrun, “The dynamic window approach to collision avoidance,” _IEEE Robotics & Automation Magazine_, vol. 4, no. 1, pp. 23–33, 1997.
  * [11] M. Keller, F. Hoffmann, C. Hass, T. Bertram, and A. Seewald, “Planning of optimal collision avoidance trajectories with timed elastic bands,” _IFAC Proceedings Volumes_ , vol. 47, no. 3, pp. 9822–9827, 2014.
  * [12] S. Sharma, A. Srinivas, and B. Ravindran, “Learning to repeat: Fine grained action repetition for deep reinforcement learning,” 2017.
  * [13] I. P. Durugkar, C. Rosenbaum, S. Dernbach, and S. Mahadevan, “Deep reinforcement learning with macro-actions,” _arXiv preprint arXiv:1606.04615_ , 2016.
  * [14] A. Lakshminarayanan, S. Sharma, and B. Ravindran, “Dynamic action repetition for deep reinforcement learning,” in _Proceedings of the 31th AAAI Conference on Artificial Intelligence (AAAI-2017)_ , vol. 31, no. 1, 2017.
  * [15] R. S. Sutton, D. Precup, and S. Singh, “Between mdps and semi-mdps: A framework for temporal abstraction in reinforcement learning,” _Artificial intelligence_ , vol. 112, no. 1-2, pp. 181–211, 1999.
  * [16] J.-L. Blanco, J. Gonzalez, and J.-A. Fernández-Madrigal, “The trajectory parameter space (tp-space): a new space representation for non-holonomic mobile robot reactive navigation,” in _2006 IEEE/RSJ International Conference on Intelligent Robots and Systems_. IEEE, 2006, pp. 1195–1200.
  * [17] N. Heess, D. TB, S. Sriram, J. Lemmon, J. Merel, G. Wayne, Y. Tassa, T. Erez, Z. Wang, S. M. A. Eslami, M. A. Riedmiller, and D. Silver, “Emergence of locomotion behaviours in rich environments,” _arXiv preprint arXiv:1707.02286_ , 2017.
  * [18] J. Schulman, P. Moritz, S. Levine, M. Jordan, and P. Abbeel, “High-dimensional continuous control using generalized advantage estimation,” in _Proceedings of the 4th International Conference on Learning Representations (ICLR-2016)_ , 2016.
  * [19] S. Mahadevan and N. Khaleeli, “Robust mobile robot navigation using partially-observable semi-markov decision processes,” _Internal report_ , 1999.
  * [20] O. Saha and P. Dasgupta, “Real-time robot path planning around complex obstacle patterns through learning and transferring options,” in _Proceedings of the 17th International Conference on Autonomous Robot Systems and Competitions (ICARSC-2017)_. IEEE, 2017, pp. 278–283.
  * [21] Y. F. Chen, M. Liu, M. Everett, and J. P. How, “Decentralized non-communicating multiagent collision avoidance with deep reinforcement learning,” in _Proceedings of the 34th International Conference on Robotics and Automation (ICRA-2017)_. IEEE, 2017, pp. 285–292.
  * [22] M. Everett, Y. F. Chen, and J. P. How, “Motion planning among dynamic, decision-making agents with deep reinforcement learning,” in _Proceedings of the 31th International Conference on Intelligent Robots and Systems (IROS-2018)_. IEEE, 2018, pp. 3052–3059.
  * [23] G. Chen, S. Yao, J. Ma, L. Pan, Y. Chen, P. Xu, J. Ji, and X. Chen, “Distributed non-communicating multi-robot collision avoidance via map-based deep reinforcement learning,” _Sensors_ , vol. 20, no. 17, p. 4836, 2020\.
  * [24] Y. Chen, G. Chen, L. Pan, J. Ma, Y. Zhang, Y. Zhang, and J. Ji, “Drqn-based 3d obstacle avoidance with a limited field of view,” in _Proceedings of the 34th International Conference on Intelligent Robots and Systems (IROS-2021)_. IEEE, 2021, pp. 8137–8143.
  * [25] B. Brito, M. Everett, J. P. How, and J. Alonso-Mora, “Where to go next: learning a subgoal recommendation policy for navigation in dynamic environments,” _IEEE Robotics and Automation Letters_ , vol. 6, no. 3, pp. 4616–4623, 2021.
  * [26] E. Chane-Sane, C. Schmid, and I. Laptev, “Goal-conditioned reinforcement learning with imagined subgoals,” in _Proceedings of the 38th International Conference on Machine Learning (ICML-2021)_. PMLR, 2021, pp. 1430–1440.
  * [27] J.-L. Blanco, J. González, and J.-A. Fernández-Madrigal, “Extending obstacle avoidance methods through multiple parameter-space transformations,” _Autonomous Robots_ , vol. 24, no. 1, pp. 29–48, 2008\.
  * [28] J. Schulman, F. Wolski, P. Dhariwal, A. Radford, and O. Klimov, “Proximal policy optimization algorithms,” _arXiv preprint arXiv:1707.06347_ , 2017\.
  * [29] D. Silver, “Lecture 7: Policy gradient,” _UCL Course on RL_ , 2015.
  * [30] D.-A. Clevert, T. Unterthiner, and S. Hochreiter, “Fast and accurate deep network learning by exponential linear units (ELUs),” 2016.
  * [31] S. Schmoll and M. Schubert, “Semi-markov reinforcement learning for stochastic resource collection,” in _Proceedings of the 30th International Conference on International Joint Conferences on Artificial Intelligence (IJCAI-2021)_ , 2021, pp. 3349–3355.
  * [32] V. Nair and G. E. Hinton, “Rectified linear units improve restricted boltzmann machines,” in _Proceedings of the 27th International Conference on Machine Learning (ICML-2010)_.