Lei<EMAIL_ADDRESS>Yangguang<EMAIL_ADDRESS>Xin<EMAIL_ADDRESS>Dong<EMAIL_ADDRESS>Fenggang
<EMAIL_ADDRESS>Tsinghua University
Beijing, China SenseTime Research
Beijing, China Institute of Automation, Chinese Academy of Sciences
Beijing, China Neighbor Regularized Bayesian Optimization

# Neighbor Regularized Bayesian Optimization for Hyperparameter Optimization

###### Abstract

Bayesian Optimization (BO) is a common solution to search optimal
hyperparameters based on sample observations of a machine learning model.
Existing BO algorithms could converge slowly even collapse when the potential
observation noise misdirects the optimization. In this paper, we propose a
novel BO algorithm called Neighbor Regularized Bayesian Optimization (NRBO) to
solve the problem. We first propose a neighbor-based regularization to smooth
each sample observation, which could reduce the observation noise efficiently
without any extra training cost. Since the neighbor regularization highly
depends on the sample density of a neighbor area, we further design a density-
based acquisition function to adjust the acquisition reward and obtain more
stable statistics. In addition, we design a adjustment mechanism to ensure the
framework maintains a reasonable regularization strength and density reward
conditioned on remaining computation resources. We conduct experiments on the
bayesmark benchmark and important computer vision benchmarks such as ImageNet
and COCO. Extensive experiments demonstrate the effectiveness of NRBO and it
consistently outperforms other state-of-the-art methods.

##  1 Introduction

The performance of modern machine learning models highly depends on the good
choice of hyperparameters. Thus a system that can quickly and automatically
optimize the hyperparameters becomes more and more important nowadays. The
hyperparameter optimization problem is often regarded as a black-box
optimization problem, and the common solution is Bayesian optimization (BO)
[Golovin et al.(2017)Golovin, Solnik, Moitra, Kochanski, Karro, and Sculley,
Wu et al.(2019)Wu, Chen, Zhang, Xiong, Lei, and Deng, Eriksson et
al.(2019b)Eriksson, Pearce, Gardner, Turner, and Poloczek, Lindauer et
al.(2022)Lindauer, Eggensperger, Feurer, Biedenkapp, Deng, Benjamins, Ruhkopf,
Sass, and Hutter, Eggensperger et al.(2021)Eggensperger, Müller, Mallik,
Feurer, Sass, Klein, Awad, Lindauer, and Hutter, Daulton et al.(2021)Daulton,
Eriksson, Balandat, and Bakshy, Victoria and Maragatham(2021)].

Though existing BO algorithms have shown significant improvement compared with
the random search algorithm [Li et al.(2017)Li, Jamieson, DeSalvo,
Rostamizadeh, and Talwalkar, Falkner et al.(2018)Falkner, Klein, and Hutter],
BO could still converge slowly even collapse when the potential observation
noise is non-negligible. Specifically, the observation (a.k.a. performance) of
a model could fluctuate in a wide range even using the same hyperparameters,
which might mislead the surrogate model to overfit noisy observations. A
natural idea to solve the problem is to obtain reliable observations by
training repetitively. However, it will cause multiplied computational cost
which is unacceptable in heavy tasks. Another idea is to add noise assumptions
on the sample observations, while the noise assumptions without any prior will
decrease the fitting efficiency of the surrogate model.

To overcome the above difficulties, we propose a novel BO algorithm called
Neighbor Regularized Bayesian Optimization (NRBO). NRBO applies adaptive
regularization at different positions of the search space according to the
neighbor sample points. Specifically, the observation of a sample will be
smoothed by the observations of its neighbor samples. Then, the smoothed
observations are used to optimize the surrogate model. The regularization
could reduce the observation noise which has the same spirit as the k-nearest
neighbors algorithm [Fix and Hodges(1989)]. Thus, no repetitive training
phases are needed to get extra observations. Compared with directly
introducing a global noise assumption, this method can dynamically smooth
observations at different regions thus regularize the optimization.

The neighbor-based regularization algorithm needs to have as many samples as
possible at each desired area to obtain credible and stable statistics.
Therefore, we design a new density-based acquisition function, which can
adjust the acquisition reward according to the sample density of a certain
area. The proposed acquisition function adopts a stronger reward for the
sparse area where the density of observed samples is low. This design has two
advantages. First, it provides a more balanced sampling strategy that the
observed samples are distributed more evenly on the entire search space.
Second, it prevents the surrogate model from sticking into a local sub-optimal
solution prematurely.

Finally, we design a mechanism to dynamically adjust the regularization
strength and acquisition reward. This mechanism ensures that the framework
maintains a reasonable regularization strength and acquisition reward during
the Bayesian optimization process. The regularization strength and density
reward are positively correlated with the remaining computation resources. As
the search progresses, the regularization strength will be weakened to help
the model fit more subtle data patterns in finer spatial resolution. At the
same time, the density reward will also be weakened to balance the
exploration-exploitation trade-off and encourage the algorithm to converge at
the high-performance area when searching is about to end.

Extensive experiments demonstrate the effectiveness of our NRBO. NRBO achieves
the state-of-the-art performance on the bayesmark and six commonly used
computer vision tasks. For example, NRBO achieves 0.85%, 0.22%, 2.1% and 2.36%
higher accuracy on Stanfordcar, ImageNet, VOC and COCO datasets compared with
random search [Bergstra and Bengio(2012)]. We summarize our main contributions
in this paper as follows:

$\bullet$ We propose a novel Bayesian optimization method based on the
statistics of the neighbor observations, which can adaptively reduce the
observation noise and regularize the surrogate model.

$\bullet$ We propose a novel density-based acquisition function to provide
credible and stable statistics for Bayesian optimization process.

$\bullet$ We design a mechanism to dynamically adjust the regularization
strength and acquisition reward according to the remaining computation
resource. It helps to fit more subtle data patterns and balance the
exploration-exploitation trade-off as the optimization progresses.

##  2 Related Works

###  2.1 Model-free Method

The most straightforward approach to optimize the hyperparameters is the
model-free method. Grid search is one of the commonly used methods that can be
easily implemented and parallelized [Lerman(1980), Liashchynskyi and
Liashchynskyi(2019)]. It discretizes the search space into a mesh grid and
evaluates them all. The computation cost will explode exponentially as the
dimension or the resolution of the hyperparameter increases. Another model-
free approach is the Random search [Bergstra and Bengio(2012), Solis and
Wets(1981)]. Instead of traversing the discretized search space, random search
selects the candidate hyperparameter randomly. Although the Random Search and
the Grid Search seems to have similar efficiency, Random Search usually
performs better in a limited search budget in practice. The reason is that the
model performance is usually not distributed uniformly in the entire search
space. The Random Search samples a fixed number of parameter combinations from
the specified distribution, which improves system efficiency by reducing the
probability of wasting much time on a small poorly-performing region [Yang and
Shami(2020)].

###  2.2 Bayesian Optimization

In addition to the model-free approaches, the most popular method used in
hyperparameter optimization is Bayesian optimization [Golovin et
al.(2017)Golovin, Solnik, Moitra, Kochanski, Karro, and Sculley, Wu et
al.(2019)Wu, Chen, Zhang, Xiong, Lei, and Deng, Eriksson et
al.(2019b)Eriksson, Pearce, Gardner, Turner, and Poloczek, Daulton et
al.(2021)Daulton, Eriksson, Balandat, and Bakshy, Victoria and
Maragatham(2021), Shahriari et al.(2015)Shahriari, Swersky, Wang, Adams, and
De Freitas, Snoek et al.(2015)Snoek, Rippel, Swersky, Kiros, Satish, Sundaram,
Patwary, Prabhat, and Adams, Swersky et al.(2013)Swersky, Snoek, and Adams].
Instead of searching the hyperparameter in a pre-defined distribution,
Bayesian optimization can dynamically fit the observed data to determine the
next search place. Bayesian optimization algorithm runs a search loop that
iteratively fits the surrogate model and queries the acquisition function
[Snoek et al.(2012)Snoek, Larochelle, and Adams]. By fitting the observed
data, the surrogate model can predict the performance distribution throughout
the search space with prior distribution such as smoothness. The acquisition
function selects the promising regions that balance the exploration-
exploitation trade-off [Hazan et al.(2017)Hazan, Klivans, and Yuan]. A typical
Bayesian optimization algorithm is the Gaussian Process Bayesian Optimization
(GPBO) [Rasmussen(2003)]. GPBO utilizes the Gaussian process as the surrogate
model that can predict the performance in the search space as a jointly
Gaussian distribution. SMAC is another popular Bayesian optimization algorithm
that uses random forest as the surrogate model and ensembled regression trees
as the objective function [Hutter et al.(2011)Hutter, Hoos, and Leyton-Brown].
HEBO enhances the surrogate model through input warping and output
transformations and proposes a multi-objective acquisition function for
candidate selection [Cowen-Rivers et al.(2020)Cowen-Rivers, Lyu, Wang,
Tutunov, Jianye, Wang, and Ammar].

##  3 Method

###  3.1 Preliminaries

Hyperparameter optimization can be seen as a black-box optimization problem.
The searching process is started with a initial observation dataset
$\mathcal{D}_{0}$. Specifically, a batch of random hyperparameters
$\boldsymbol{x}_{0:m-1}$ are sampled at first. Then models with these
hyperparameters are trained and evaluated to get the observations
$\boldsymbol{y}_{0:m-1}$. The observation dataset $\mathcal{D}_{0}$ is
initialized by $\\{(\boldsymbol{x}_{0:m-1},\boldsymbol{y}_{0:m-1})\\}$. The
surrogate model $f_{\theta}$ will be trained for $N$ times to fit the
observation dataset $\mathcal{D}_{0}$, where $\theta$ is optimized by
minimizing the negative log marginal likelihood.

After fitting the surrogate model, we need to guess the best
$\boldsymbol{x^{*}}$ by proposing a new (batch of) sample point according to
acquisition function $f_{acq}$. Given an input sample point $\boldsymbol{x}$,
$f_{acq}$ calculates the priority of this sample point according to
probability distribution predicted by the surrogate model $f_{\theta}$. The
acquisition function is usually designed to balance the exploration-
exploitation trade-off. A novel sample point $\boldsymbol{\hat{x}}$ is
selected by $argmax_{\boldsymbol{x}\in\mathcal{X}}f_{acq}(\boldsymbol{x})$,
and in practice we discretize the continuous search space $\mathcal{X}$ into a
meshgrid points collection.

Once the novel sample point is selected, it will be evaluated on black-box by
training the machine learning models with the hyperparameter it represents.
Then the observation $\\{(\boldsymbol{\hat{x}},\hat{y})\\}$ will be added to
datasets $\mathcal{D}_{i}$ for the next iteration. When the main loop is over,
the algorithm returns the best-performing data point as the result.

Figure 1: Illustration of the NRBO algorithm. In two key progress of
acquisition and observation. Our method is different from the naive bayes
algorithm. In acquisition stage, we propose a density-based acquisition
function to accelerate the acquisition process, in which adjacent sample
points in the neighbor are considered. In observation stage, neighbor
regularized mechanism is introduced to smooth the observation noise and
release the burden of repetitive observation.

###  3.2 Neighbor Regularized Bayesian Optimization

Figure 1 shows a brief illustration of our NRBO. The main innovations of NRBO
can be summarized as: a novel regularization to reduce the observation noise
(section 3.2.1), a density-based acquisition function to adjust the
acquisition reward (section 3.2.2) and a dynamic adjustment of the
regularization strength and acquisition reward according to the remaining
computation resource (section 3.2.3).

####  3.2.1 Neighbor-based regularization

In the context of Bayesian optimization, the algorithm maintains an
observation dataset $\mathcal{D}_{i}$ at any iteration $i$, which consists of
all sampled hyperparameters as well as their corresponding observation
received from the black box. To regularize the surrogate model, we define

$\overline{y_{j}}=\frac{\sum_{k}^{N_{D}}P_{j}(\boldsymbol{x}_{k})\cdot
y_{k}}{\sum_{k}^{N_{D}}P_{j}(\boldsymbol{x}_{k})},\\\ \quad
P_{j}(\boldsymbol{x}_{k})=\left\\{\begin{array}[]{ll}1&\qquad\|\boldsymbol{x}_{j}-\boldsymbol{x}_{k}\|\leq\sigma_{1}\\\
0&\qquad\|\boldsymbol{x}_{j}-\boldsymbol{x}_{k}\|>\sigma_{1}\end{array}\right.$
(1)

where $N_{D}$ is the number of samples in $\mathcal{D}_{i}$,
$P_{j}(\boldsymbol{x}_{k})$ is a filter function that keeps the points in the
neighbor of $\boldsymbol{x}_{j}$ with $\sigma_{1}$ as radius.
$\overline{y_{j}}$ is the observation smoothed by its neighbor sample
observations, and we have a smoothed observation dataset
$\overline{\mathcal{D}_{i}}=\\{(\boldsymbol{x}_{l},\overline{y_{l}})\\}_{l=0:N-1}$.
Different from naive Bayes, the surrogate model is regularized by fitting the
$\overline{\mathcal{D}_{i}}$ instead of ${\mathcal{D}_{i}}$.

Here we give a brief analysis on neighbor-based regularization. Firstly, NRBO
smoothes each observation by taking the neighbor observations into account. In
this way, NRBO can efficiently regularize the model without repetitive
training. In practice, the computation burden of repetitive training is
unacceptable because each observation needs to re-train the entire model.
Secondly, the strength of regularization is determined by the statistical
properties of all sample points lie in the neighbor area. As the variance of
observations increase, NRBO will also impose stronger regularization. Compared
with simply modeling noise with $y=f(x)+\eta$ that regularize the model evenly
throughout the entire search space, the NRBO regularization mechanism is more
adaptive and effective. Note that in practice, $\sigma_{1}$ moves according to
the searching progress, we will discuss it in section 3.2.3.

####  3.2.2 Density-based acquisition function

As demonstrated in section 3.2.1, NRBO imposes adaptive regularization by
adopting neighbor sample observations. Obviously, to make the NRBO works more
efficiently, we need to increase the density of the sample points for a more
reliable and stable statistics. If there exists no other observed sample point
lies in the neighbor area of a certain point, NRBO degenerates into a normal
Bayesian optimization without any regularization in this area.

Based on the above analysis, we propose a density-based strategy to adjust the
acquisition function. Our baseline acquisition function is the multi-objective
acquisition ensemble (MACE) proposed in HEBO [Cowen-Rivers et al.(2020)Cowen-
Rivers, Lyu, Wang, Tutunov, Jianye, Wang, and Ammar]. The proposed density-
based acquisition function can be formally denoted as:

$min(-f_{EI}-g_{d}(\boldsymbol{x})S_{EI};\
-f_{PI}-g_{d}(\boldsymbol{x})S_{PI};\
f_{UCB}-g_{d}(\boldsymbol{x})S_{UCB}),\quad
g_{d}(\boldsymbol{x})=e^{-f_{n}(\boldsymbol{x},\sigma_{2})}\\\ $ (2)

where $f_{EI}$, $f_{PI}$ and $f_{UCB}$ are three widely-used myopic
acquisition functions. $S_{EI}$, $S_{PI}$ and $S_{UCB}$ are norm items that
represent the standard deviation of acquisition values of all candidate points
in search space. We follow HEBO [Cowen-Rivers et al.(2020)Cowen-Rivers, Lyu,
Wang, Tutunov, Jianye, Wang, and Ammar] to define and use these symbols,
please refer to HEBO for more details. Different from HEBO, we introduce new
adjustment items $g_{d}$. In equation 2, function $f_{n}$ returns the number
of sample points in $D_{i}$ that lies in the neighbor area of point
$\boldsymbol{x}$. $\sigma_{2}$ is the radius that defines the neighbor range.

With adjustment item $g_{d}$, the acquisition value of the candidate point
$\boldsymbol{x}$ can be adjusted by the density of its observed adjacent
sample points in $D_{i}$, thus $g_{d}$ can be regarded as density reward. It
will highly pump the acquisition value in the area that has fewer observed
points in dataset $D_{i}$, and encourage the solver to search this sparse
area.

Equipped with the density-based adjustment strategy, observed sample points in
$D_{i}$ will distribute more evenly to enhance the efficiency of the neighbor-
based regularization. Note that in practice, $\sigma_{2}$ also moves according
to the searching progress and we will discuss it in section 3.2.3.

####  3.2.3 Dynamic regularization strength and density reward

In Eq 1, we adopt a fixed $\sigma_{1}$ to smooth the observations and
regularize the surrogate model. In practice, we use a dynamic $\sigma_{1}$ to
weaken the strength of the regularization as the search progresses.

At the beginning of the search process, we adopt a larger $\sigma_{1}$ to
strengthen the smoothness. This helps the model to fit the observation dataset
with lower resolution and concentrate more on long-range trends in the entire
search space. As the search progresses, the $\sigma_{1}$ will gradually
decrease to weaken the regularization, encouraging the model to fit more
details when the solver is more close to the optimal solution. Specifically,
we can rewrite the filter function in equation 1 as follows:

$P_{j}(\boldsymbol{x}_{k})=\left\\{\begin{array}[]{ll}1&\textrm{\qquad$\|\boldsymbol{x}_{j}-\boldsymbol{x}_{k}\|\leq\sigma_{1}(i)$}\\\
0&\textrm{\qquad$\|\boldsymbol{x}_{j}-\boldsymbol{x}_{k}\|>\sigma_{1}(i)$}\end{array}\right.\quad\sigma_{1}(i)=\sigma_{1}^{0}+(1-i/N)*\sigma_{1}^{1}$
(3)

where $\sigma_{1}^{0}$ is the base regularization strength, $i$ is the current
optimization iteration and $N$ is the total number of the optimization
iteration. The neighbor radius will starts at $\sigma_{1}^{0}+\sigma_{1}^{1}$
and end up in $\sigma_{1}^{0}$.

Similarly, we also adopt a dynamic $\sigma_{2}$ in Eq 2, the difference is
that it moves in an opposite direction. At the beginning of the search
process, we use a relatively smaller $\sigma_{2}$ to encourage the algorithm
to search the entire search space especially the sparse area that contains
fewer observed points. Then the $\sigma_{2}$ will gradually decrease the
density reward and rebalance the exploration-exploitation trade-off. Formally,
we re-write the equation 2 as

$g_{d}(\boldsymbol{x})=e^{-f_{n}(\boldsymbol{x},\sigma_{2}(i))},\quad\sigma_{2}(i)=\sigma_{2}^{0}+i/N*\sigma_{2}^{1}$
(4)

It helps the search process to get rid of the local optimal at very beginning
and finally rebalance the exploration and exploitation to the normal state
because the adjustment item value $g_{d}$ will finally tend to be zero
throughout the entire search space, making the searching process easier to
converge on the optimal point.

##  4 Experiments

We conduct extensive experiments on both conventional BO benchmark bayesmark
and some commonly used computer vision benchmarks such as ImageNet [Krizhevsky
et al.(2012)Krizhevsky, Sutskever, and Hinton], COCO [Lin et al.(2014)Lin,
Maire, Belongie, Hays, Perona, Ramanan, Dollár, and Zitnick]. We first compare
NRBO against several state-of-the-arts BO methods on both bayesmark (section
4.1) and computer vision benchmarks (section 4.2). Then we conduct a more
detailed ablation study to demonstrate the impact of each component of NRBO in
section 4.4. In addition, we present some qualitative visualization of NRBO in
section 4.5.

Method | MLP_digits | RF_breast | SVM_digits | SVM_wine | ada_breast | ada_digits | linear_breast | $Avg.\\_score$ | $Avg.\\_norm$
---|---|---|---|---|---|---|---|---|---
Random | 98.63 | 92.07 | 94.95 | 81.19 | 93.75 | 69.26 | 89.27 | 90.93 | 1.07
Hyperopt | 100.29 | 96.50 | 96.87 | 88.72 | 98.96 | 73.87 | 92.85 | 96.53 | 0.411
Opentuner | 100.76 | 92.07 | 98.43 | 92.61 | 98.96 | 100.21 | 94.39 | 93.16 | 0.81
Nevergrad | 100.11 | 98.83 | 100.07 | 70.30 | 98.96 | 76.09 | 94.55 | 93.95 | 0.72
Pysot | 101.13 | 95.34 | 97.56 | 99.87 | 95.83 | 96.55 | 97.80 | 98.34 | 0.20
Skopt | 100.08 | 98.60 | 96.86 | 96.24 | 93.75 | 76.79 | 89.88 | 96.23 | 0.45
Turbo | 101.10 | 96.74 | 98.53 | 100 | 95.83 | 91.45 | 97.56 | 98.28 | 0.20
HEBO | 101.38 | 97.67 | 101.70 | 96.24 | 98.96 | 112.88 | 95.82 | 99.94 | 0.01
NRBO | 101.49 | 100.00 | 103.53 | 103.63 | 100.00 | 113.01 | 101.01 | 100.34 | -0.04
Table 1: The performance of 9 optimizers on bayesmark benchmark. We list the
average loss score(denoted as Avg.score) and normalized mean score(denoted as
Avg.norm) for all 108 tasks in bayesmark benchmark.

###  4.1 Results on Bayesmark

Bayesmark111https://github.com/uber/bayesmark benchmark contains 6 standard
datasets (breast, digits, iris, wine, boston, diabetes) and 9 commonly used
machine learning models (DT, MLP-ADAM, MLP-SGD, RF, SVM, ADA, KNN, Lasso,
Linear). Each model has two variants for classification and regression.
Combining these datasets and models, there are 108 tasks to evaluate the
hyperparameter optimization algorithms.

We adopt two official metrics to measure the performance on Bayesmark. The
loss score metric for each task is calculated by $100*(1-loss)$ . The
normalized mean score first calculates the performance gap between
observations and the global optimal point, then normalize it by the gap
between random search results and the optimal. Table 1 shows the performance
of NRBO and other 8 commonly used hyperparameter optimizers, including random
search, hyperopt [Bergstra et al.(2013)Bergstra, Yamins, and Cox], opentuner
[Ansel et al.(2014)Ansel, Kamil, Veeramachaneni, Ragan-Kelley, Bosboom,
O’Reilly, and Amarasinghe], pysot [Eriksson et al.(2019a)Eriksson, Bindel, and
Shoemaker], skopt [Timgates42(2020)], turbo [Eriksson et al.(2019b)Eriksson,
Pearce, Gardner, Turner, and Poloczek], nevergrad [Rapin and Teytaud(2018)]
and HEBO [Cowen-Rivers et al.(2020)Cowen-Rivers, Lyu, Wang, Tutunov, Jianye,
Wang, and Ammar]. We also select 7 tasks in bayesmark and plot the
optimization process in detail at figure 2. NRBO starts to surpass other
optimizers at the 9-th iteration and stays ahead till the end of the
optimization. The results indicate that NRBO converges faster and reaches
better final score.

Figure 2: The convergence progress of different methods. The results indicate
that NRBO converges faster and reaches better score on both bayesmarks and CV
tasks. For VOC task, score represents the AP50 metric.

###  4.2 Results on Computer Vision Tasks

In this section, we show the experiment results about different hyperparameter
optimization algorithms used on common computer vision tasks. We only choose
three optimization algorithms including random search, HEBO and our NRBO due
to the high cost of computer vision tasks on both time and resource.

Our computer vision experiments include classification task and detection
task. For the classification task, we use ResNet-18 [He et al.(2016)He, Zhang,
Ren, and Sun] and train it on ImageNet [Krizhevsky et al.(2012)Krizhevsky,
Sutskever, and Hinton], CIFAR10 [Krizhevsky et al.(2009)Krizhevsky, Hinton, et
al.], CIFAR100 [Krizhevsky et al.(2009)Krizhevsky, Hinton, et al.] and
Stanford Cars [Krause et al.(2013)Krause, Stark, Deng, and Fei-Fei] datasets.
Four hyperparameters including momentum, weight decay, label smooth and
learning rate compose a 4-dimension searching space. For the detection task,
we use RetinaNet [Lin et al.(2017)Lin, Goyal, Girshick, He, and Dollár] and
train it on Pascal VOC [Everingham et al.(2010)Everingham, Van Gool, Williams,
Winn, and Zisserman] and MS-COCO2017 [Lin et al.(2014)Lin, Maire, Belongie,
Hays, Perona, Ramanan, Dollár, and Zitnick] datasets. The searching space is
also composed of 4 hyperparameters including momentum, weight decay, positive
IoU thresh and negative IoU thresh.

The best detection results with different hyperparameter optimization
algorithms are shown in table 2, where HEBO performs better than random search
on COCO, and NRBO performs best on both VOC and COCO datasets. These results
are consistent with those in bayesmark benchmark, demonstrating the
effectiveness of our proposed method.

Method | ImageNet | VOC | CIFAR10 | CIFAR100 | Stanford Car | COCO
---|---|---|---|---|---|---
Random | 62.00 | 75.02 | 95.28 | 81.96 | 87.09 | 31.56
HEBO | 62.07(+0.07) | 74.88(-0.14) | 95.35(+0.07) | 81.91(-0.05) | 87.56(+0.47) | 32.34(+0.78)
NRBO | 62.22(+0.22) | 77.12(+2.10) | 95.43(+0.15) | 82.16(+0.20) | 87.94(+0.85) | 33.92(+1.36)
Table 2: Experiment results on computer vision tasks. The positive numbers in
parentheses represent absolute improvements relative to Random Search.

The classification results are shown in table 2. It is seen that the
performance of HEBO is close to the naive random search. This may be caused by
a relatively flat performance landscape near the optimal solution in search
space, and even a random search could have a high probability of getting a
good result. Compared to bayesmark and COCO, the output of the ImageNet
experiments with a specific hyperparameters is more stable. Therefore, the
NRBO could hardly benefit from the regularization. Even in this case, NRBO
still surpasses the HEBO on all four classification tasks.

###  4.3 Full-training Results of Computer Vision Tasks

Since the hyperparameter optimization needs repetitive trials, the computation
cost is unaffordable on large-scale datasets. To overcome the computation
resource limitation, in large computer vision datasets ImageNet and COCO, we
optimize the hyperparameter on proxy tasks with 60% of total iterations for
only 20 trials. Then we use the hyperparameters optimized on the proxy task
for a full training to verify whether the NRBO is still in the lead. We repeat
each optimizer 4 times for stable and convincing results.

Classification The configuration is same as ImageNet experiments in section
4.2, except that the learning rate of proxy task decreases at 25000th,
50000th, and 75000th iteration and ends at 80000th iteration. In full-training
task, the learning rate schedule time is set as 37500, 75000, and 112500.
Training ends at the 125000th iteration. As shown in table 3, the average
accuracy of NRBO surpasses HEBO and random search by 0.37 and 0.33
respectively in the full-training setting.

Detection The configuration is same as COCO experiments in section 4.2. In
full-training task, the learning rate drops at the 9th and 12th epoch.
Training ends at the 14th epoch. As shown in table 3, the mAP of NRBO
surpasses HEBO and random search by 2.29 and 1.37 respectively in the full-
training setting.

Experiments above demonstrate that the hyperparameters searched by the small
proxy task can be transfered to the full-training task.

Exp. Index | Task | Random | HEBO | NRBO
---|---|---|---|---
1 | proxy | 67.268 | 65.808 | 66.490
full | 68.324 | 67.660 | 68.362
2 | proxy | 65.644 | 67.258 | 66.972
full | 67.858 | 68.642 | 68.562
3 | proxy | 66.290 | 66.908 | 67.058
full | 67.668 | 68.494 | 68.446
4 | proxy | 66.916 | 66.116 | 67.020
full | 68.638 | 67.848 | 68.606
Avg. | proxy | 66.530 | 66.523 | 66.885
full | 68.122 | 68.161 | 68.494

Exp. Index | Task | Random | HEBO | NRBO
---|---|---|---|---
1 | proxy | 32.283 | 32.070 | 34.853
full | 34.549 | 34.438 | 36.952
2 | proxy | 32.085 | 32.334 | 33.231
full | 33.773 | 34.609 | 35.634
3 | proxy | 31.705 | 33.571 | 34.410
full | 34.123 | 35.997 | 36.199
4 | proxy | 30.147 | 31.395 | 33.222
full | 32.487 | 33.585 | 35.307
Avg. | proxy | 31.555 | 32.343 | 33.929
full | 33.733 | 34.657 | 36.023

Table 3: (Left) Proxy task and full-training task results on ImageNet. (Right)
Proxy task and full-training task results on COCO.

###  4.4 Ablation Study

In this section, we analyze the efficiency of each component proposed in NRBO.
We first conduct experiments with a variant NRBO that cancels the density-
based acquisition function. If we further cancel the regularization mechanism
proposed in section 3.2.1, the NRBO will degenerate to a normal HEBO
optimizer.

Figure 3 left shows the performance of HEBO, variant NRBO that without
density-based acquisition function and a full NRBO. We can find that the
variant NRBO still outperforms the basic HEBO within a wide range of
computation resource settings. The variant NRBO significantly surpasses the
HEBO from the tenth to the twelfth iteration. As the optimization progresses,
the variant NRBO and HEBO finally reach the tie in the end. Note that the full
NRBO still outperforms the HEBO at the end of the optimization. It suggests
that the density-based acquisition function helps the optimizer jump out of
the local optimal and leads to a better solution.

Figure 3: (Left) Ablation study for regularization and acquisition function.
HEBO denotes the NRBO w/o regularization and density-based acquisition reward.
HEBO+REG denotes the NRBO w/o density-based acquisition reward. (Right)
Ablation study for dynamic regularization and acquisition function. Static
NRBO denotes the NRBO w/o dynamic regularization and acquisition function.

We also compare the NRBO with its variant that cancels the dynamic
regularization strength and density reward described in section 3.2.3. Figure
3 right shows that, without the dynamic regularization strength and density
reward, the performance of NRBO deteriorates severely as the optimization
progresses. This is reasonable because always keeping a strong regularization
will prevent the surrogate model from fitting the subtle patterns at the high-
performance area where the search process is close to optimal. In addition, a
fixed density-based acquisition reward encourages the optimizer to explore
rather than exploit. It will also prevent the optimizer from a detailed search
in the high-performance area.

###  4.5 Qualitative Visualization

In this section we visualize the effectiveness of regularization on an example
dataset. We compare the standard Gaussian process Bayesian optimizer with a
neighbor-based regularized optimizer on different noise levels. The search
space is normalized to $[0,1]$ and the neighbor radius for regularization is
set to 0.1. The example dataset is generated with $sin(2\pi x)+cos(2\pi
y)+\epsilon\sigma$, where $\epsilon$ is the noise level and $\sigma\sim
N(0,1)$.

As shown in Figure 4, in the first row, both of them fit the dataset well when
the noise level is 0. When the noise level is set to 0.4, standard Gaussian
process model starts to overfit the noise data and its output tends to be
sharp and unstable. If we further increase the noise level to 0.8, the
standard Gaussian process model completely collapsed. Meanwhile, the
regularized model still outputs a smooth prediction that is very close to the
ground truth.

Figure 4: Fitting surrogate model on the same dataset with different nosise
level. From left to right: Gradually increased noise level $\epsilon$, from
$0$ to $0.8$. Top row: A typical Bayesian optimization with Gaussian process
and Matern Kernel. Bottom row: Neighbor regularized Bayesian optimization.

##  5 Conclusion

We propose a novel hyperparameter optimization algorithm NRBO in this work. We
first propose a neighbor-based regularization to smooth sample observations by
the neighbor statistics. To further improve the stability of the neighbor
statistics, we propose a density-based acquisition function. In addition, an
adjustment mechanism is adopted to adjust the regularization strength and
acquisition reward based on the remaining computation resources. Extensive
experiments demonstrate NRBO could accelerate the convergence of
hyperparameter optimization and reduce the risk of collapse.

## References

  * [Ansel et al.(2014)Ansel, Kamil, Veeramachaneni, Ragan-Kelley, Bosboom, O’Reilly, and Amarasinghe] Jason Ansel, Shoaib Kamil, Kalyan Veeramachaneni, Jonathan Ragan-Kelley, Jeffrey Bosboom, Una-May O’Reilly, and Saman Amarasinghe.  Opentuner: An extensible framework for program autotuning.  In _Proceedings of the 23rd international conference on Parallel architectures and compilation_ , pages 303–316, 2014.
  * [Bergstra and Bengio(2012)] James Bergstra and Yoshua Bengio.  Random search for hyper-parameter optimization.  _Journal of machine learning research_ , 13(2), 2012.
  * [Bergstra et al.(2013)Bergstra, Yamins, and Cox] James Bergstra, Daniel Yamins, and David Cox.  Making a science of model search: Hyperparameter optimization in hundreds of dimensions for vision architectures.  In _International conference on machine learning_ , pages 115–123. PMLR, 2013.
  * [Cowen-Rivers et al.(2020)Cowen-Rivers, Lyu, Wang, Tutunov, Jianye, Wang, and Ammar] Alexander I Cowen-Rivers, Wenlong Lyu, Zhi Wang, Rasul Tutunov, Hao Jianye, Jun Wang, and Haitham Bou Ammar.  Hebo: Heteroscedastic evolutionary bayesian optimisation.  _arXiv e-prints_ , pages arXiv–2012, 2020.
  * [Daulton et al.(2021)Daulton, Eriksson, Balandat, and Bakshy] Samuel Daulton, David Eriksson, Maximilian Balandat, and Eytan Bakshy.  Multi-objective bayesian optimization over high-dimensional search spaces.  _CoRR_ , abs/2109.10964, 2021.  URL https://arxiv.org/abs/2109.10964.
  * [Eggensperger et al.(2021)Eggensperger, Müller, Mallik, Feurer, Sass, Klein, Awad, Lindauer, and Hutter] Katharina Eggensperger, Philipp Müller, Neeratyoy Mallik, Matthias Feurer, René Sass, Aaron Klein, Noor H. Awad, Marius Lindauer, and Frank Hutter.  Hpobench: A collection of reproducible multi-fidelity benchmark problems for HPO.  In Joaquin Vanschoren and Sai-Kit Yeung, editors, _Proceedings of the Neural Information Processing Systems Track on Datasets and Benchmarks 1, NeurIPS Datasets and Benchmarks 2021, December 2021, virtual_ , 2021.
  * [Eriksson et al.(2019a)Eriksson, Bindel, and Shoemaker] David Eriksson, David Bindel, and Christine A Shoemaker.  pysot and poap: An event-driven asynchronous framework for surrogate optimization.  _arXiv preprint arXiv:1908.00420_ , 2019a.
  * [Eriksson et al.(2019b)Eriksson, Pearce, Gardner, Turner, and Poloczek] David Eriksson, Michael Pearce, Jacob Gardner, Ryan D Turner, and Matthias Poloczek.  Scalable global optimization via local bayesian optimization.  _Advances in Neural Information Processing Systems_ , 32:5496–5507, 2019b.
  * [Everingham et al.(2010)Everingham, Van Gool, Williams, Winn, and Zisserman] M. Everingham, L. Van Gool, C. K. I. Williams, J. Winn, and A. Zisserman.  The pascal visual object classes (voc) challenge.  _International Journal of Computer Vision_ , 88(2):303–338, June 2010.
  * [Falkner et al.(2018)Falkner, Klein, and Hutter] Stefan Falkner, Aaron Klein, and Frank Hutter.  Bohb: Robust and efficient hyperparameter optimization at scale.  In _International Conference on Machine Learning_ , pages 1437–1446. PMLR, 2018.
  * [Fix and Hodges(1989)] Evelyn Fix and Joseph Lawson Hodges.  Discriminatory analysis. nonparametric discrimination: Consistency properties.  _International Statistical Review/Revue Internationale de Statistique_ , 57(3):238–247, 1989.
  * [Golovin et al.(2017)Golovin, Solnik, Moitra, Kochanski, Karro, and Sculley] Daniel Golovin, Benjamin Solnik, Subhodeep Moitra, Greg Kochanski, John Karro, and David Sculley.  Google vizier: A service for black-box optimization.  In _Proceedings of the 23rd ACM SIGKDD international conference on knowledge discovery and data mining_ , pages 1487–1495, 2017.
  * [Hazan et al.(2017)Hazan, Klivans, and Yuan] Elad Hazan, Adam Klivans, and Yang Yuan.  Hyperparameter optimization: A spectral approach.  _arXiv preprint arXiv:1706.00764_ , 2017.
  * [He et al.(2016)He, Zhang, Ren, and Sun] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun.  Deep residual learning for image recognition.  In _Proceedings of the IEEE conference on computer vision and pattern recognition_ , pages 770–778, 2016.
  * [Hutter et al.(2011)Hutter, Hoos, and Leyton-Brown] Frank Hutter, Holger H Hoos, and Kevin Leyton-Brown.  Sequential model-based optimization for general algorithm configuration.  In _International conference on learning and intelligent optimization_ , pages 507–523. Springer, 2011.
  * [Krause et al.(2013)Krause, Stark, Deng, and Fei-Fei] Jonathan Krause, Michael Stark, Jia Deng, and Li Fei-Fei.  3d object representations for fine-grained categorization.  In _4th International IEEE Workshop on 3D Representation and Recognition (3dRR-13)_ , Sydney, Australia, 2013.
  * [Krizhevsky et al.(2009)Krizhevsky, Hinton, et al.] Alex Krizhevsky, Geoffrey Hinton, et al.  Learning multiple layers of features from tiny images.  2009\.
  * [Krizhevsky et al.(2012)Krizhevsky, Sutskever, and Hinton] Alex Krizhevsky, Ilya Sutskever, and Geoffrey E Hinton.  Imagenet classification with deep convolutional neural networks.  _Advances in neural information processing systems_ , 25:1097–1105, 2012.
  * [Lerman(1980)] PM Lerman.  Fitting segmented regression models by grid search.  _Journal of the Royal Statistical Society: Series C (Applied Statistics)_ , 29(1):77–84, 1980.
  * [Li et al.(2017)Li, Jamieson, DeSalvo, Rostamizadeh, and Talwalkar] Lisha Li, Kevin Jamieson, Giulia DeSalvo, Afshin Rostamizadeh, and Ameet Talwalkar.  Hyperband: A novel bandit-based approach to hyperparameter optimization.  _The Journal of Machine Learning Research_ , 18(1):6765–6816, 2017.
  * [Liashchynskyi and Liashchynskyi(2019)] Petro Liashchynskyi and Pavlo Liashchynskyi.  Grid search, random search, genetic algorithm: A big comparison for nas.  _arXiv preprint arXiv:1912.06059_ , 2019.
  * [Lin et al.(2014)Lin, Maire, Belongie, Hays, Perona, Ramanan, Dollár, and Zitnick] Tsung-Yi Lin, Michael Maire, Serge Belongie, James Hays, Pietro Perona, Deva Ramanan, Piotr Dollár, and C Lawrence Zitnick.  Microsoft coco: Common objects in context.  In _European conference on computer vision_ , pages 740–755. Springer, 2014.
  * [Lin et al.(2017)Lin, Goyal, Girshick, He, and Dollár] Tsung-Yi Lin, Priya Goyal, Ross Girshick, Kaiming He, and Piotr Dollár.  Focal loss for dense object detection.  In _Proceedings of the IEEE international conference on computer vision_ , pages 2980–2988, 2017.
  * [Lindauer et al.(2022)Lindauer, Eggensperger, Feurer, Biedenkapp, Deng, Benjamins, Ruhkopf, Sass, and Hutter] Marius Lindauer, Katharina Eggensperger, Matthias Feurer, André Biedenkapp, Difan Deng, Carolin Benjamins, Tim Ruhkopf, René Sass, and Frank Hutter.  SMAC3: A versatile bayesian optimization package for hyperparameter optimization.  _J. Mach. Learn. Res._ , 23:54:1–54:9, 2022.
  * [Rapin and Teytaud(2018)] J. Rapin and O. Teytaud.  Nevergrad - A gradient-free optimization platform.  https://GitHub.com/FacebookResearch/Nevergrad, 2018.
  * [Rasmussen(2003)] Carl Edward Rasmussen.  Gaussian processes in machine learning.  In _Summer school on machine learning_ , pages 63–71. Springer, 2003\.
  * [Shahriari et al.(2015)Shahriari, Swersky, Wang, Adams, and De Freitas] Bobak Shahriari, Kevin Swersky, Ziyu Wang, Ryan P Adams, and Nando De Freitas.  Taking the human out of the loop: A review of bayesian optimization.  _Proceedings of the IEEE_ , 104(1):148–175, 2015\.
  * [Snoek et al.(2012)Snoek, Larochelle, and Adams] Jasper Snoek, Hugo Larochelle, and Ryan P Adams.  Practical bayesian optimization of machine learning algorithms.  _Advances in neural information processing systems_ , 25, 2012.
  * [Snoek et al.(2015)Snoek, Rippel, Swersky, Kiros, Satish, Sundaram, Patwary, Prabhat, and Adams] Jasper Snoek, Oren Rippel, Kevin Swersky, Ryan Kiros, Nadathur Satish, Narayanan Sundaram, Mostofa Patwary, Mr Prabhat, and Ryan Adams.  Scalable bayesian optimization using deep neural networks.  In _International conference on machine learning_ , pages 2171–2180. PMLR, 2015.
  * [Solis and Wets(1981)] Francisco J Solis and Roger J-B Wets.  Minimization by random search techniques.  _Mathematics of operations research_ , 6(1):19–30, 1981.
  * [Swersky et al.(2013)Swersky, Snoek, and Adams] Kevin Swersky, Jasper Snoek, and Ryan P Adams.  Multi-task bayesian optimization.  _Advances in neural information processing systems_ , 26, 2013.
  * [Timgates42(2020)] Timgates42.  scikit-optimize, 2020.
  * [Victoria and Maragatham(2021)] A Helen Victoria and G Maragatham.  Automatic tuning of hyperparameters using bayesian optimization.  _Evolving Systems_ , 12(1):217–223, 2021.
  * [Wu et al.(2019)Wu, Chen, Zhang, Xiong, Lei, and Deng] Jia Wu, Xiu-Yun Chen, Hao Zhang, Li-Dong Xiong, Hang Lei, and Si-Hao Deng.  Hyperparameter optimization for machine learning models based on bayesian optimization.  _Journal of Electronic Science and Technology_ , 17(1):26–40, 2019.
  * [Yang and Shami(2020)] Li Yang and Abdallah Shami.  On hyperparameter optimization of machine learning algorithms: Theory and practice.  _Neurocomputing_ , 415:295–316, 2020.


# An almost globally convergent observer for visual SLAM without persistent
excitation

Bowen Yi, Chi Jin, Lei Wang, Guodong Shi and Ian R. Manchester This paper is
supported by the Australian Research Council. B. Yi, L. Wang, G. Shi and I.R.
Manchester are with Australian Centre for Field Robotics & Sydney Institute
for Robotics and Intelligent Systems, The University of Sydney, Sydney, NSW
2006, Australia. C. Jin is with DJI Innovation Inc., Shenzhen 518057, China.
<EMAIL_ADDRESS>
###### Abstract

In this paper we propose a novel observer to solve the problem of visual
simultaneous localization and mapping (SLAM), only using the information from
a single monocular camera and an inertial measurement unit (IMU). The system
state evolves on the manifold $SE(3)\times\mathbb{R}^{3n}$, on which we design
dynamic extensions carefully in order to generate an invariant foliation, such
that the problem is reformulated into online _constant parameter_
identification. Then, following the recently introduced parameter estimation-
based observer (PEBO) and the dynamic regressor extension and mixing (DREM)
procedure, we provide a new simple solution. A notable merit is that the
proposed observer guarantees almost global asymptotic stability requiring
neither persistency of excitation nor uniform complete observability, which,
however, are widely adopted in most existing works with guaranteed stability.

##  I Introduction

Simultaneous localization and mapping (SLAM) is a fundamental problem widely
studied in the robotics community, as well as in the field of navigation [8,
14]. In SLAM, two main aims are concerned to be accomplished
concurrently—mapping an unknown environment, and online estimating the pose,
i.e. attitude and position, of a mobile robot, thus making SLAM an important
part for unmanned systems in the absence of absolute positioning systems.

The main approaches to address this problem may generally be classified into
two categories. The first one is within the probabilistic and optimization
framework, assuming Gaussian noises and processes, and then formulating the
problem as maximum likelihood estimation, which generally has nonlinear least
squares solutions, e.g. GraphSLAM [22] and the SLAM++ framework [9]. An
alternative is to obtain estimation from an asymptotic convergence
viewpoint—known as filtering—by using recursive algorithms. It includes
extended Kalman filter (EKF)-SLAM and many modern algorithms, e.g. FastSLAM,
which combines EKF and particle filtering [17]. An essential part of these
algorithms is their convergence and consistency analysis, the success of which
relies on first-order approximation of systems dynamics [8]. It sometimes
yields satisfactory performance, but may have inconsistency issues when
starting from a bad initial guess, in particular for large applications, which
is caused by small domains of attraction in terms of linearization—invoking
high nonlinearity of the associated dynamics. In the last few years, the
nonlinear control community shows great interests to SLAM, providing
alternatives via nonlinear observer design to address the problem. Indeed,
SLAM can be regarded as the problem of state observation of a nonlinear system
living on the manifold $SE(3)\times\mathbb{R}^{3n}$. On the other hand,
nonlinear observer for systems on manifolds is a well established topic, with
special emphasis to matrix Lie groups [10, 12, 15]. Some very recent papers
[14, 21, 5] give several solutions to the _robo-centric_ SLAM problem, i.e.,
estimating landmark coordinates in the body-fixed frame, for which the
dynamics can be transformed into linear time-varying (LTV) systems, thus
avoiding the approximation error from linearization. Then, the Kalman-Bucy
filter is applicable to provide _globally_ convergent estimation, if the robot
movement guarantees uniform complete observability (UCO). It is well known
that the UCO of an LTV system is equivalent to a persistency of excitation
(PE) condition [20].

In this paper, we propose a new observer-based solution to visual SLAM, a case
with only bearing measurement of landmarks available. Similar problems were
recently studied in [23], in which the authors introduce a constructive
observer design to visual SLAM by lifting to a new symmetry Lie group
$\mathbb{VSLAM}(3)$ in order to make the output function equivariant. Since
the system is not strongly differentially observable, in order to be able to
achieve asymptotic stability, some PE conditions are required for the robot
trajectory. Besides [14, 23], some PE or UCO-type assumptions are also
indispensable in some related problems, e.g., locolization using range or
direction measurements [6], velocity estimation using normalized measurement
[4], and the non-stationary Perspective-$n$-Point (PnP) problem [7].
Intuitively, these assumptions impose relative motion between the robot and
the landmarks, the uniformity of which should hold w.r.t. time. However, such
assumptions may not be satisfied in many scenarios, such as, robots stopping
in specific tasks, and landmarks appearing in the field of camera only during
a finite interval, which validates neither the PE nor UCO conditions. Under
these circumstances, the estimates of existing SLAM observers cannot converge
to their values; and the observers may even diverge in the presence of
measurement noise. Overcoming these problems are one of the motivations of the
paper. Our main contributions are

  * C1

Showing that visual SLAM observer design can be translated into online
parameter estimation, and then solved by the recently introduced parameter
estimation-based observer (PEBO) [18], guaranteeing invariance and almost
global convergence, in contrast to the locality in EKF-SLAM methods;

  * C2

Providing a simple visual SLAM observer, which is robust vis-à-vis measurement
noise, and enjoys low computation burden;

  * C3

Removing the PE condition required in some recent results, e.g., [4, 14, 23,
21, 7], the practical importance of which can hardly be overestimated, since
it is usually the case in many tasks.

The remainder of the paper is organized as follows. In Section II we will
present some preliminaries, notations and the kinematic model used in the
paper, as well as giving the mathematical problem formulation. In Section III,
a novel visual SLAM observer will be designed. It will be followed by some
simulation results in Section IV. Finally, the paper is wrapped up by a brief
concluding remark. A version with full details of the proofs can be found in
[24].

##  II Problem Formulation and Preliminaries

###  II-A Notations

We use $SO(3)$ to represent the special orthogonal group, and
${\mathfrak{so}}(3)$ is the associated Lie algebra as the set of skew-
symmetric matrices satisfying $SO(3)=\\{R\in\mathbb{R}^{3\times
3}|R^{\top}R=I_{3},~{}\det(R)=1\\}$. The unit sphere is denoted as ${\cal
S}^{2}=\\{x\in\mathbb{R}^{3}|~{}|x|=1\\}$. Given $a\in\mathbb{R}^{3}$, we
define the operator $(\cdot)_{\times}$ as

$a_{\times}:=\begin{bmatrix}0&-a_{3}&a_{2}\\\ a_{3}&0&-a_{1}\\\
-a_{2}&a_{1}&0\end{bmatrix}\in{\mathfrak{so}}(3).$

We also consider the special Euclidean group denoted as $SE(3)=\\{{\cal
T}(R,x)\in\mathbb{R}^{4\times 4}|R\in SO(3),~{}x\in\mathbb{R}^{3}\\}$ with

${\cal T}(R,x)=\begin{bmatrix}R&x\\\ 0&1\end{bmatrix}.$ (1)

The Lie algebra of $SE(3)$ is defined as

${\mathfrak{se}}(3):=\left\\{A\in\mathbb{R}^{4\times
4}\Bigg{|}A=\begin{bmatrix}\Omega_{\times}&v\\\
0&0\end{bmatrix},\Omega_{\times}\in\mathfrak{so}(3),v\in\mathbb{R}^{3}\right\\}.$

For any $x\in\mathbb{R}^{3}$, $a\times x$ is the vector cross product,
satisfying $a_{\times}x=a\times x$. We define a wedged mapping
$U^{\vee}=\begin{bmatrix}\Omega_{\times}&v\\\ 0&0\end{bmatrix}$ for a vector
$U:=\mbox{col}(\Omega,v)\in\mathbb{R}^{6}$. Given $A\in\mathbb{R}^{n\times n}$
and $S\in\mathbb{R}^{n\times n}_{\succeq 0}$, the Frobenius norm is defined as
$\|A\|=\sqrt{\mbox{tr}(A^{\top}A)}$, and $S^{1\over 2}$ and
$\mbox{adj}\\{A\\}$ represent the matrix square root and the adjugate matrix,
respectively. We use $|\cdot|$ to denote Euclidean norms of vectors or its
induced matrix norm. For any $x\in\mathbb{R}^{3}/\\{0\\}$, its projector is
defined as $\Pi_{x}:=I_{3}-{1\over|x|^{2}}xx^{\top},$ which projects a given
vector onto the subspace orthogonal of $x$. $\epsilon_{t}$ represents
exponentially decaying terms with proper dimensions. When clear from context,
the arguments and subscripts are omitted. Before closing this subsection, let
us recall below the notations of PE and interval excitation (IE). Obviously,
IE is significantly weaker than PE, not requiring uniformity in time.

######  Definition 1.

Given a bounded signal $\phi:\mathbb{R}_{+}\to\mathbb{R}^{n}$, it is

  * -

$(T,\delta)$-PE, if $\int_{t}^{t+T}\phi(s)\phi^{\top}(s)ds\succeq\delta I_{n}$
for some $T>0,\delta>0$ and all $t\geq 0$.

  * -

$(t_{0},t_{c},\delta)$-IE if there exist $t_{0}\geq 0$ and $t_{c}\geq 0$ such
that $\int_{t_{0}}^{t_{0}+t_{c}}\phi(s)\phi^{\top}(s)ds\succeq\delta I_{n}$
for some $\delta>0$. $\triangleleft$

Nomenclature $\hat{(\cdot)}$ Estimate of a variable or state $\tilde{(\cdot)}$
Estimation error $I_{n}$ ${n\times n}$ identity matrix $x\in\mathbb{R}^{3}$
Robot position $v\in\mathbb{R}^{3}$ Translational velocity in $\\{{\cal B}\\}$
$\Omega\in\mathbb{R}^{3}$ Rotational velocity in $\\{{\cal B}\\}$ $R\in SO(3)$
Robot attitude matrix $X\in SE(3)$ Rigid-body pose $X:={\cal T}(R,x)$
$z_{i}\in\mathbb{R}^{3}$ Position of the $i$-th landmark in $\\{{\cal I}\\}$
$y_{i}\in\mathbb{R}^{3}$ Bearing vector of the $i$-th landmark in $\\{{\cal
B}\\}$ $\mathbb{P}_{a}(\cdot)$ Skew-symmetric projector
$\mathbb{P}_{a}(A)={A-A^{\top}\over 2}$ $\small\\{{\cal I},{\cal B},{\cal
V},{\cal E}\\}$ Inertial, body, virtual, and estimate frames

###  II-B Kinematic model and visual SLAM problem

The kinematics of a robot with rigid body is given by

$\displaystyle\dot{x}=Rv,\quad\dot{R}=R\Omega_{\times}.$ (2)

All the definitions of symbols and the spaces where they live in can be found
in Nomenclature. We assume that there are $n$ landmarks appearing in the field
view of camera, the coordinates $z_{i}$ of which in $\\{{\cal I}\\}$ are
constant, thus satisfying

$\dot{z}_{i}=0,\quad i\in{\cal N}:=\\{1,\ldots,n\\}\subset\mathbb{N}.$ (3)

We assume that $v$ and $\Omega$ are uniformly bounded for $t\in[0,+\infty)$,
and the kinematic model is forward complete. The time derivative of $X:={\cal
T}(R,x)$ is

$\dot{X}=XU^{\vee}$ (4)

with $U=\mbox{col}(\Omega,v)$ containing rotational and translational
velocities. From some simple geometry identities, the point-type landmarks in
$\\{{\cal B}\\}$ verify $x^{{\cal B}}=R^{\top}(z_{i}-x).$ In visual SLAM only
monocular cameras and IMUs are equipped on robotics, thus only landmark
bearings being measurable. Without loss of generality, we assume that the
camera frame coincides with $\\{{\cal B}\\}$. Then, the output is exactly the
bearing

$y_{i}=h_{i}(X,Z)=R^{\top}{z_{i}-x\over|z_{i}-x|},\quad i\in{\cal N}.$ (5)

It is clear that the unit vector $[z_{i}-x]/|z_{i}-x|\in{\cal S}^{2}$ contains
the orientation of the relative vector $(z_{i}-x)$. For convenience, we write
$Y:=[~{}y_{1}~{}|~{}\ldots~{}|~{}y_{n}~{}]$ and
$Z:=\mbox{col}(z_{1},\ldots,z_{n}).$

Problem 1. (_visual SLAM observer_) Consider the kinematics (2) with the
output $Y$, and assume that $U$ is measured via IMUs. Design an observer

$\displaystyle\dot{\hat{\eta}}=F(\hat{\eta},Y,U),\quad(\hat{X},\hat{Z})=H(\hat{\eta},Y)$
(6)

with $\hat{X}\in SE(3)$ and $\hat{Z}\in\mathbb{R}^{3n}$, guaranteeing

$\lim_{t\to+\infty}\big{[}|\hat{X}(t)-X(t)|+|\hat{Z}(t)-Z|\big{]}=0.$ (7)

##  III Main Results

In this section, we will design an almost globally convergent observer to
achieve (7), by means of PEBO.

###  III-A Key algebraic identities

The key step in PEBOs is to generate invariant foliations among the system
states and dynamic extension [18]. Here we construct a dynamic extension

$\dot{X}_{e}=X_{e}U^{\vee},\qquad X_{e}:={\cal T}(Q,\xi)$ (8)

with $X_{e}\in SE(3)$, which can be regarded as a virtual robot in $\\{{\cal
V}\\}$. We have the following.

######  Lemma 1.

Consider the dynamics (2) and (8). The dynamic extension (8) is forward
complete, and there exists a constant matrix $X_{c}={\cal T}(Q_{c},\xi_{c})\in
SE(3)$ satisfying

$X_{e}(t)\equiv X_{c}X(t),\quad\forall t\geq 0.$ (9)

###### Proof.

Defining an error variable $E(X,X_{e}):=X_{e}X^{\top}$ and calculating its
time derivative, we may verify the claim. See [24] for more details.
$\triangleleft$

The above lemma shows that the open-loop dynamic extension (8) and the
kinematics (2) admit a linear relationship (9)—more precisely, there is a
constant rigid transformation between the frames $\\{{\cal I}\\}$ and
$\\{{\cal V}\\}$—by means of which we reformulate the state estimation of
$X(t)$ into the problem of online _constant_ parameter identification of
$X_{c}\in SE(3)$. We define the coordinates of all the landmarks $z_{i}$ in
$\\{{\cal V}\\}$ as

$z_{i}^{v}:=\xi+QR^{\top}(z_{i}-x),\quad\forall i\in{\cal N}.$ (10)

A key observation is that the transformation (9) of the ambient from $\\{{\cal
I}\\}$ to $\\{{\cal V}\\}$ does not change the _relative_ transformation from
a robot to a landmark.

######  Lemma 2.

Consider the dynamics (2) and (8). The landmark coordinates $z_{i}^{v}(t)$
$(i\in{\cal N})$ in $\\{{\cal V}\\}$ are _constant_ , verifying

$z_{i}^{v}=\xi_{c}+Q_{c}z_{i}.$ (11)

The landmark bearings in $\\{{\cal V}\\}$, defined as

$y_{i}^{v}:=Q^{\top}{z_{i}^{v}-\xi\over|z_{i}^{v}-\xi|},\quad i\in{\cal N},$
(12)

are _measurable_ , i.e., $y_{i}^{v}(t)\equiv y_{i}(t),~{}\forall t\geq 0.$

###### Proof.

Invoking (9) and the definition (10), we have

$\displaystyle z_{i}^{v}$
$\displaystyle=[\xi_{c}+Q_{c}x]+[Q_{c}R]R^{\top}[z_{i}-x]=\xi_{c}+Q_{c}z_{i},$

which is clearly constant. About the second claim, we have
$y_{i}^{v}=Q^{\top}{QR^{\top}(z_{i}-x)\over|QR^{\top}(z_{i}-x)|}=R^{\top}{z_{i}-x\over|z_{i}-x|}=y_{i},$
($i\in{\cal N}$), where we have used (10) in the first equation.
$\triangleleft$

As shown in Lemma 2, the landmark coordinates $z_{i}^{v}$ in $\\{{\cal V}\\}$
are constant. Despite being quite simple, the above lemmata, show the
estimation of time-varying systems state may be translated into online
parameter estimation of $X_{c}$ and $z_{i}^{v}$. To the best of our knowledge,
such a fact has not been used in SLAM observer design before, which, however,
provides the possibility to relax significantly the PE or UCO assumptions in
existing algorithms. In the sequel, we will show how to design a globally
convergent observer.

###  III-B Landmarks Observer in $\\{{\cal V}\\}$

Now we are able to construct linear regressor equations (LREs) of constant
$z_{i}^{v}$. From (12) it yields

$\displaystyle
Qy_{i}={z_{i}^{v}-\xi\over|z_{i}^{v}-\xi|}~{}\implies~{}Qy_{i}[Qy_{i}]^{\top}(z_{i}^{v}-\xi)=z_{i}^{v}-\xi.$

Noting that $y(t)$ is a unit vector, we thus obtain the LREs

$q_{i}(t)=\Pi_{Q(t)y_{i}(t)}\cdot z_{i}^{v},$ (13)

by defining measurable signals $q_{i}:=\Pi_{Qy_{i}}\cdot\xi$, where we have
used the fact $\bar{y}_{i}(t)\equiv y_{i}(t)$ introduced in Lemma 2. It is
also easy to verify the following equivalence for some $\delta^{\prime}>0$.

$\displaystyle\quad\Pi_{Qy_{i}}^{{1\over
2}}\in(\delta^{\prime},T)\mbox{-PE}~{}\iff~{}\int_{t}^{t+T}\Pi_{Qy_{i}}ds\succeq\delta
I_{3},~{}\forall t\geq 0.$

The widely used PE or UCO-type assumptions in the existing visual SLAM
observers, intuitively, require that all landmarks appear in the view filed of
the camera persistently, and the robot keeps moving w.r.t. the landmarks,
which in general can hardly be guaranteed in practice. In the following, we
will show that with the LREs (13) these restrictive excitation assumptions can
be relaxed using the recently introduced DREM technique [1]. We first
introduce some linear filters to generate a new LRE. To be precise, for each
$i\in{\cal N}$ introducing an ${\cal L}_{\infty}$ operator ${\cal H}_{i}:{\cal
L}^{3}_{\infty}\to{\cal L}^{3}_{\infty}$ to (13), and then obtaining the
extended (E)LRE

${\cal H}_{i}[q_{i}](t)=\Big{[}\begin{aligned} {\cal
H}_{i}[\Pi_{i,1}](t)~{}\Big{|}~{}{\cal H}_{i}[\Pi_{i,2}](t)~{}\Big{|}~{}{\cal
H}_{i}[\Pi_{i,3}](t)\end{aligned}\Big{]}z_{i}^{v}$

where the symbols $\Pi_{i,j}$ ($j=\\{1,2,3\\}$) are used with a slight abuse
of notation, to denote the $j$-th column of the matrix $\Pi_{Q(t)y_{i}(t)}$.
Here, we adopt the LTV operator of the form

${\cal H}_{i}(p,t)[\cdot]={\alpha_{i}\over
p+\alpha_{i}}[\Pi_{Q(t)y_{i}(t)}(\cdot)]$ (14)

with $\alpha_{i}>0$ and $p:=d/dt$ the differential operator. One of its state
space realization is known as Kreisselmeier’s ELRE [11]—written as K-ELRE in
the paper—which is given by

$\displaystyle{\dot{q}}_{i}^{e}$
$\displaystyle=-\alpha_{i}q_{i}^{e}+\alpha_{i}\Pi_{Qy_{i}}^{\top}q_{i}$ (15)
$\displaystyle\dot{\Phi}_{i}$
$\displaystyle=-\alpha_{i}\Phi_{i}+\alpha_{i}\Pi_{Qy_{i}}^{\top}\Pi_{Qy_{i}}$

with the system states
$(q_{i}^{e},\Phi_{i})\in\mathbb{R}^{3}\times\mathbb{R}^{3\times 3}_{\succeq
0}$ for $i\in{\cal N}$. It is straightforward to obtain the K-ELRE

$q_{i}^{e}(t)=\Phi_{i}(t)z_{i}^{v}+\epsilon_{t}.$ (16)

Then, we mix the regressors (16) to get three decoupled, _scalar_ regressors
for each $i\in{\cal N}$, that is pre-multipying the adjugate matrix
$\mbox{adj}\\{\Phi_{i}(t)\\}$ to the both sides, thus obtaining

$Y_{i,j}(t)=\Delta_{i}(t)z_{i,j}^{v}+\epsilon_{t},\quad i\in{\cal
N},\;j\in\\{1,2,3\\}$ (17)

with the definitions
$Y_{i,j}:=\mbox{adj}\\{\Phi_{i}\\}q_{i}^{e},~{}\Delta_{i}:=\det\\{\Phi_{i}\\}$
and $Y_{i}:=\mbox{col}(Y_{i,1},Y_{i,2},Y_{i,3}).$ We are in position to
present a novel landmark observer in $\\{{\cal V}\\}$, which only requires a
strictly weaker condition than PE.

######  Proposition 1.

(Mapping) The landmark observer

$\displaystyle\dot{\chi}_{i}$
$\displaystyle=\Delta_{i}(Y_{i}-\Delta_{i}\chi_{i}),\quad\chi_{i}(0)=\chi_{i,0}$
(18) $\displaystyle\dot{\omega}_{i}$
$\displaystyle=-\Delta_{i}^{2}\omega_{i},\quad\omega_{i}(0)=1$
$\displaystyle\dot{\hat{z}}_{i}^{v}$
$\displaystyle=\gamma_{i}\Delta_{i}^{e}\left[Y_{i}+k_{\tt
I}^{i}\big{(}\chi_{i}-\omega_{i}\chi_{i,0}\big{)}-\Delta_{i}^{e}\hat{z}_{i}^{v}\right]$

with (15) and

$\Delta_{i}^{e}:=\Delta_{i}+k_{\tt I}^{i}(1-\omega_{i}),$ (19)

$\gamma_{i}>0$ and $k_{\tt I}^{i}>0$ ($\quad i\in{\cal N}$), guarantees

  * 1)

(Internal stability) All the internal states are bounded.

  * 2)

(Element-wise monotonicity) For $\forall t_{a}\geq t_{b}\geq 0$,

$|\hat{z}_{i,j}^{v}(t_{a})-z_{i,j}^{v}|\leq|\hat{z}_{i,j}^{v}(t_{b})-z_{i,j}^{v}|,\quad
j\in\\{1,2,3\\}.$

  * 3)

(GES under IE) Assuming that $\Pi_{Qy_{i}}$ is
$(t_{0,i},t_{c,i},\delta_{i})$-IE, the origin of the error dynamics of
$\tilde{z}^{v}_{i}:=\hat{z}_{i}^{v}-z_{i}^{v}$ is globally exponentially
stable.

###### Proof.

The time derivative of $(\chi_{i}-z_{i}^{v})$ is given by

$\dot{\aoverbrace[L1R]{\chi_{i}-z_{i}^{v}}}=-\Delta_{i}^{2}(t)(\chi_{i}-z_{i}^{v}),$

which is an LTV dynamics, with $\Delta_{i}$ a scalar bounded signal. Its
solution is

$\displaystyle\chi_{i}(t)-z_{i}^{v}$
$\displaystyle=\exp\bigg{(}-\int_{0}^{t}\Delta_{i}(s)^{2}ds\bigg{)}(\chi_{i}(0)-z_{i}^{v})$
$\displaystyle=\omega(t)(\chi_{i,0}-z_{i}^{v})$

by noting the solution $\omega_{i}(t)=\exp(-\int_{0}^{t}\Delta_{i}(s)^{2}ds).$
It yields

$\chi_{i}(t)-\omega_{i}(t)\chi_{i,0}=[1-\omega_{i}(t)]z_{i}^{v},$ (20)

in which we underscore that $\chi_{i},\omega_{i}$ and $\chi_{i,0}$ ($t\geq 0$)
are all available in observer design. In this way, we get new scalar LREs (20)
involving the “integral” information of $\Delta_{i}$. Combining (20) and (17),
we obtain new linear regressors

$Y_{i}+k_{\tt I}^{i}(\chi_{i}-\omega_{i}\chi_{i,0})=\Delta_{i}^{e}z_{i}^{v},$
(21)

in which $z_{i}^{v}$ are the unknown constant parameters.

By defining the estimation error $\tilde{z}^{v}_{i}=\hat{z}_{i}^{v}-z_{i}^{v}$
we have111Since the exponentially decaying term $\epsilon_{t}$ has no effect
on stability, we omit it in the sequel analysis.

$\dot{\tilde{z}}_{i}^{v}=-\gamma_{i}(\Delta_{i}^{e})^{2}\tilde{z}_{i}^{v}.$
(22)

To verify the first claim, we choose the Lyapunov function $V={1\over
2}\sum_{i=1}^{n}\left(|\tilde{z}_{i}^{v}|^{2}+|\chi_{i}-z_{i}^{v}|^{2}+|\omega_{i}|^{2}\right),$
satisfying

$\displaystyle\dot{V}$
$\displaystyle=-\sum_{i=1}^{n}\left[\gamma_{i}(\Delta_{i}^{e})^{2}|\tilde{z}_{i}^{v}|^{2}+\Delta_{i}^{2}|\chi_{i}-z_{i}^{v}|^{2}+\Delta_{i}^{2}\omega_{i}^{2}\right]\leq
0.$

Thus, the system is internally stable.

The second claim can be easily verified invoking $\Delta_{i}^{e}$ are scalar
signals. Recalling the dynamics of $\tilde{z}_{i}^{v}$, the last claim is
equivalent to verify $\Delta_{i}^{e}\in\mbox{PE}$. To simplify presentation,
we neglect the index $i$ of the IE condition from the $i$-th landmark. From
the IE assumption of $\Pi_{Qy_{i}}$, there exist
$t_{0},t_{c},\delta\in\mathbb{R}_{+}$ such that
$\int_{t_{0}}^{t_{0}+t_{c}}\Pi_{Q(s)y_{i}(s)}\Pi_{Q(s)y_{i}(s)}^{\top}ds\geq\delta
I_{3},$ since $\Pi_{Qy_{i}}$ is symmetric. Noting (15) in the K-ELRE, we can
verify

$\displaystyle\Phi_{i}(t_{0}+t_{c})\succeq$
$\displaystyle\int_{t_{0}}^{t_{0}+t_{c}}e^{-\alpha_{i}(t_{0}+t_{c}-s)}\Pi_{Q(s)y_{i}(s)}^{\top}\Pi_{Q(s)y_{i}(s)}ds$
$\displaystyle\succeq$ $\displaystyle
e^{-\alpha_{i}t_{c}}\int_{t_{0}}^{t_{0}+t_{c}}\Pi_{Q(s)y_{i}(s)}^{\top}\Pi_{Q(s)y_{i}(s)}ds$
$\displaystyle\succeq$ $\displaystyle\delta e^{-\alpha_{i}t_{c}}I_{3}.$

It implies $\Delta(t_{0}+t_{c})\geq\delta_{0}:=(\delta
e^{-\alpha_{i}t_{c}})^{3}.$ From the continuity of differential equations,
there exist small $\tau>0$ and $\varepsilon>0$ such that

$\displaystyle\footnotesize\int_{t_{0}+t_{c}-\tau}^{t_{0}+t_{c}}\Delta_{i}(s)ds\geq\sqrt{\varepsilon}\implies$
$\displaystyle\int_{0}^{t}\Delta_{i}^{2}(s)ds\geq{1\over\tau}\varepsilon,~{}\forall
t\geq t_{c}$ $\displaystyle\implies$ $\displaystyle 1-\omega_{i}\geq
1-e^{-{1\over\tau}\varepsilon},~{}\forall t\geq t_{c}$ $\displaystyle\implies$
$\displaystyle\Delta_{i}^{e}=\Delta_{i}+k_{\tt
I}^{i}(1-\omega_{i})\in\mbox{PE}$

where we used $\Delta_{i}\geq 0$, $\forall t\geq 0$ and the Cauchy-Schwarz
inequality for integrals. $\triangleleft$

Some remarks are made below about the proposed design.

  * R1

The success of the proposed landmark observer relies on the new scalar LREs
(21)—motivated by [19]—which satisfy the PE condition. It combines two parts,
namely, the first contains information in the current small “interval”
invoking the K-ELRE generated by the filter (15), and the second one consists
of historical data using an integral operation to generate the “state
transmission function” $\omega(t)$. Here, the parameters $k_{\tt I}^{i}$ are
adopted to play a role of weighting between them.

$\displaystyle\small\underbrace{Y_{i}}_{\mbox{\footnotesize``current
interval''}}+~{}\underbrace{k_{\tt
I}^{i}[\chi_{i}-\omega_{i}\chi_{i,0}]}_{\footnotesize\mbox{historical
information}}=\Delta_{i}^{e}(t)z_{i}^{v}.$

  * R2

The obtained new LREs (20) may be replaced by other _pure integral_ action,
e.g., $\int_{0}^{t}Y_{i}(s)ds=\int_{0}^{t}\Delta_{i}(s)ds\cdot z_{i}^{v},$ in
order to make full use of the IE condition. It, however, may cause parts of
internal states in the observer unbounded as time goes to infinity, once
$\Delta_{i}$ satisfies the PE condition. $\triangleleft$

###  III-C Landmark and Pose Observer in $\\{{\cal I}\\}$

After obtaining the landmarks estimation in $\\{{\cal V}\\}$, we then need to
express it in $\\{{\cal I}\\}$, as well as to estimate the rigid body pose
$X={\cal T}(R,x)$. It is widely recognized that the full dynamics (2)-(3),
under the output functions (12), is not strongly differentially observable
[13]—a notion widely explored in high-gain observers [3]. The underlying
reason is clear that it is ambiguous to identify the origin of $\\{{\cal
I}\\}$ with only body-fixed bearing measurement, and angular/translational
velocities, see for example [25, 23] in which the estimation error converges
to a _quotient manifold_ rather than an isolated equilibrium. There are
generally two technical routes to circumvent such difficulties:

  * T1

Assuming the initial conditions of pose states $X(0)={\cal T}(R(0),x(0))$ in
the inertial frame $\\{{\cal I}\\}$.

  * T2

Incorporating the measurements in $\\{{\cal B}\\}$ of (at least) two vectors,
the inertial coordinates of which are _known_ in advance.

In the latter two known vectors provide information to transform the remainder
of the task into a rigid body pose estimation problem, which is widely studied
in the control literature [15, 2, 16]. However, the former coincides with the
“standard” definition of SLAM problems. With this consideration, we will
pursue the first route in the sequel. From now on, we assume the initial pose
$X(0)=X_{\star}:={\cal T}(R_{\star},x_{\star})\in SE(3)$ is _pre-selected_ ,
thus known, in order to “fix” the inertial frame $\\{{\cal I}\\}$. It is clear
that for (8) by choosing particular initial conditions we have

$\small\Big{[}\xi(0)=x_{\star},~{}Q(0)=R_{\star}\Big{]}~{}\implies~{}\Big{[}X(t)=X_{e}(t),~{}\forall
t\geq 0\Big{]}$

under _ideal circumstance_. This, however, is not practically applicable,
since the open-loop integral (8) may be problematic yielding _error
accumulation_. In this subsection, we introduce an approach to design a pose
observer and robustify the integral operation _vis-à-vis_ measurement noise.
Before continuing our design, we define the vectors
$r_{i}:=z_{i+1}-z_{i},~{}\forall i\in{\cal N}\backslash\\{n\\},$ and make the
following assumptions.

######  Assumption 1.

The origin of $\\{{\cal B}\\}$ never coincides with any landmarks for
$i\in{\cal N}$. There are at least three landmarks $z_{i}$ such that
$r_{i}\times r_{j}\neq 0,~{}\mbox{for~{}}i\neq j.$ These landmarks, without
loss of generality, are numbered in the first $n_{\ell}\geq 3$.

######  Assumption 2.

The locomotion of the robot guarantees that $\Pi_{Q(t)y_{i}(t)}$ is
$(t_{0,i},t_{c,i},\delta_{i})$-IE ($i\in{\cal N}$) along the trajectory $X(t)$
for all the landmarks to be mapped. Additionally, we assume a moment
$T_{\star}\geq{\mbox{max}}_{i\in\\{1,\ldots,n_{\ell}\\}}\\{t_{c,i}\\}>0$ is
known.

######  Proposition 2.

(Localization) Consider the kinematics (2) under Assumptions 1-2. The pose
observer

$\small\left\\{\begin{aligned}
\small\dot{\bar{z}}_{j}&=\rho_{j}\bar{\phi}_{j}\big{(}\bar{y}_{j}-\bar{\phi}_{j}^{\top}\bar{z}_{j}\big{)}\\\
\dot{\hat{Q}}_{c}&=-(w_{\tt vis})_{\times}\hat{Q}_{c}\\\
\dot{\hat{x}}&=\hat{R}v+\sum_{j=1}^{n_{\ell}}\sigma_{j}\big{(}\bar{z}_{j}-\hat{x}-\hat{Q}_{c}^{\top}(\hat{z}_{j}^{v}-\xi)\big{)},\end{aligned}\right.$
(23)

with parameters $\rho_{j},k_{j},\sigma_{j}>0$ $(j\in\\{1,\ldots,n_{\ell}\\})$,
variables
$\bar{r}_{j}=\bar{z}_{j+1}-\bar{z}_{j},~{}\hat{R}=\hat{Q}_{c}^{\top}Q$ and
$w_{\tt
vis}=\sum_{j=1}^{n_{\ell}-1}k_{j}\hat{r}_{j}^{v}\times(\hat{Q}_{c}\bar{r}_{j}),$

$\displaystyle\begin{bmatrix}\dot{\bar{y}}_{j}\\\
\dot{\bar{\phi}}_{j}\end{bmatrix}$ $\displaystyle=\left\\{\begin{aligned}
&\begin{bmatrix}\Pi_{Qy_{j}}(\xi-\xi(0)+Q(0)R_{\star}^{\top}x_{\star})\\\
\Pi_{Qy_{j}}Q(0)R_{\star}\end{bmatrix},&t\in[0,T_{\star}]\\\
&0,&t>T_{\star}\end{aligned}\right.$

and the landmark observer consisting of (18) and

$\hat{z}_{i}=\hat{Q}_{c}^{\top}(\hat{z}_{i}^{v}-\xi)-\hat{x},\quad i\in{\cal
N}$ (24)

achieve the task (7) almost globally.

###### Proof.

The proof can be found in [24]. $\triangleleft$

To illustrate the proposed design, we give the schematic block diagram in Fig.
1.

Figure 1: Block diagram of the proposed visual SLAM observer

##  IV Simulations

A robot is simulated from $x(0)=[1,1,2]^{\top}$ and the attitude
$R(0)=[\cos({\pi\over 6}),-\sin({\pi\over 6}),0;\sin({\pi\over
6}),\cos({\pi\over 6}),0;0,0,1]$, and we assume that the robot stopped at
$12$s with

$\footnotesize v=\left\\{\begin{aligned} {}&[1,0,0]^{\top}&t\in[0,12]\\\
&0_{3\times 1},&t\geq
12\end{aligned}\right.,\quad\Omega=\left\\{\begin{aligned}
{}&[0,0,-0.4]^{\top},&t\in[0,12]\\\ &0_{3\times 1},&t\geq
12\end{aligned}\right..$

It guarantees that all the landmarks satisfy the IE condition with $t_{0}=0$
and $t_{c}=12$s. We consider six landmarks and $n_{\ell}=3$. The initial
conditions in the observer are set as

$\small Q(0)=\begin{bmatrix}\cos({\pi\over 2})&-\sin({\pi\over 2})&0\\\
\sin({\pi\over 2})&\cos({\pi\over 2})&0\\\
0&0&1\end{bmatrix},~{}\hat{Q}_{c}(0)=I_{3},~{}\xi(0)=\begin{bmatrix}0\\\ 1\\\
1\end{bmatrix},$

$\hat{x}(0)=0_{3\times 1}$, and $q^{e}_{i}(0)=0_{3\times
1},~{}\Phi_{i}(0)=0_{3\times 3}$. The observer gains are selected as
$\alpha_{i}=5$, $\gamma_{i}=100$, $k_{\tt I}^{i}=20$ for $i\in{\cal N}$, and
$\rho_{j}=1$ for $j=1,2,3$. Simulation was done in Matlab/Simulink, with noise
added to measured velocities and bearings, generated by the block “Uniform
Random Number”. The pose estimation has a very good performance in Fig. 3 when
the trajectory does not guarantee the PE condition for landmarks. The landmark
observer in Proposition 1 can be used independently for mapping. Here, we
compare it to the landmark observer in [14], which requires the system being
UCO with sufficient excitation. The observer in [14] studies the case that the
landmark coordinates are expressed in $\\{{\cal B}\\}$, i.e., $z_{i}^{{\cal
B}}=R^{\top}\left(z_{i}-x\right),~{}i\in{\cal N},$ which are, indeed, time-
varying, the simulation results of which are shown in Fig. 4(a). In order to
make a fair comparison, we plot the evolution of the _norms_ of the
observation errors of $\tilde{z}_{i}$ of the proposed design and
$\tilde{z}^{{\cal B}}_{i}$ for the one in [14], since rotation does not affect
norms. The proposed landmark observer guarantees the estimation converging to
a relatively small neighbourhood of their true values in the absence of the PE
condition, and the small ultimate error is caused measurement noise, showing
good robustness. In Fig. 3, we observe that the estimates from the observer in
[14] stop converging at the moment $t_{0}+t_{c}=12$s with large errors. It is
interesting to note that the estimates diverge from that moment due to the
accumulation of noise, which is conspicuous by its absence in our proposed
design.

(a) $\hat{z}_{i}^{v}$ in $\\{{\cal V}\\}$

(b) $\hat{z}_{i}$ in $\\{{\cal I}\\}$

Figure 2: Landmark estimates $\hat{z}_{i}^{v}$ in $\\{{\cal V}\\}$ and
$\hat{z}_{i}$ in $\\{{\cal I}\\}$ without PE

(a) the attitude $R(t)$

(b) the position $x(t)$

Figure 3: Pose $X(t)$ and its estimate $\hat{X}(t)$ without the PE condition

(a) Landmark paths $z_{i}^{\mathcal{B}}$ and their estimation paths
$\hat{z}_{i}^{\mathcal{B}}$ in $\\{{\cal B}\\}$

(b) The landmark estimates $\hat{z}_{1}$ of the first landmark in the body
$\\{{\cal B}\\}$

(c) $|\tilde{z}_{i}^{v}|$ from the proposed landmark observer in Prop. 1

(d) $|\tilde{z}_{i}^{{\cal B}}|$ from the LTV Kalman filter in [14]

Figure 4: Comparison between the proposed design and [14]

##  V Conclusion

This paper introduces a novel visual SLAM observer design method. A key
observation is that the landmarks in the frame of dynamic extension are
constant, based on which we are able to get a set of linear regressors, and
then transform the problem into online parameter estimation. We extend the
PEBO methodology to the manifold $SE(3)\times\mathbb{R}^{3n}$, the unknown
“parameters” in our context being the landmark coordinates $z_{i}^{v}$ in
$\\{{\cal V}\\}$ together with the constant relative rigid transformation
$X_{c}$. A simple constructive design is provided, with guaranteed almost
global convergence, while significantly relaxing the strong PE or UCO-type
conditions required in the existing literature. As future work, it is of
practical interests to study the performance limitation from gyro noise and
bias, as well as the approach to robustify the proposed observer design.

##  VI Acknowledgement

Partial work has been done when the second author was with I3S-CNRS, France,
and he appreciates the fruitful discussions with Prof. Tarek Hamel.

## References

  * [1] S. Aranovskiy, A. Bobtsov, R. Ortega and A. Pyrkin, Performance enhancement of parameter estimators via dynamic regressor extension and mixing, IEEE Trans. on Automatic Control, vol. 62, pp. 3546–3550, 2016.
  * [2] S. Berkane, A. Abdessameud and A. Tayebi, Hybrid attitude and gyro-bias observer design on $SO(3)$, IEEE Trans. on Automatic Control, vol. 62, pp. 6044–6050, 2017.
  * [3] G. Besançon (Ed.), Nonlinear Observers and Applications, Springer, Berlin, 2007.
  * [4] E. Bjørne, E. F. Brekke, T. H. Bryne, J. Delaune and T. A. Johansen, Globally stable velocity estimation using normalized velocity measurement, Int. J. of Robotics Research, vol. 39, pp. 143–157, 2020.
  * [5] B. J. Guerreiro, P. Batista, C. Silvestre and P. Oliveira, Globally asymptotically stable sensor-based simultaneous localization and mapping, IEEE Trans. on Robotics, vol. 29, pp. 1380–1395, 2013.
  * [6] T. Hamel and C. Samson, Position estimation from direction or range measurements, Automatica, vol. 82, pp. 137–144, 2017.
  * [7] T. Hamel and C. Samson, Riccati observers for the nonstationary PnP Problem, IEEE Trans. on Automatic Control, vol. 63, pp. 726–741, 2018.
  * [8] S. Huang and G. Dissanayake, Convergence and consistency analysis for extended Kalman filter based SLAM, IEEE Trans. on Robotics, vol. 23, pp. 1036–1049, 2007.
  * [9] V. Ila, L. Polok, M. Solony and P. Svoboda, SLAM++: A highly efficient and temporally scalable incremental SLAM framework, Int. J. of Robotics Research, vol. 36, pp. 210–230, 2017.
  * [10] M. Izadi and A. K. Sanyal, Rigid body pose estimation based on the Lagrange-d’Alembert principle, Automatica, vol. 71, pp. 78–88, 2016.
  * [11] G. Kreisselmeier, Adaptive observers with exponential rate of convergence, IEEE Trans. on Automatic Control, vol. 22, pp. 2–8, 1977.
  * [12] C. Lageman, J. Trumpf and R. Mahony, Gradient-like observers for invariant dynamics on a Lie group, IEEE Trans. on Automatic Control, vol. 55, no. 2, pp. 367–377, 2010.
  * [13] K. W. Lee, W. S. Wijesoma and I. G. Javier, On the observability and observability analysis of SLAM, Proceeding of the 2006 IEEE/RSJ Int. Conf. on Intelligent Robots and Systems, pp. 3569–3574, 2006.
  * [14] P. Lourenço, P. Batista, P. Oliveira and C. Silvestre, A globally expoentially stable filter for bearing-only simultaneous localization and mapping with monocular vision, Robotics and Autonomous Systems, vol. 100, pp. 61–77, 2018.
  * [15] R. Mahony, T. Hamel and J.-M. Pflimlin, Nonlinear complementary filters on the special orthogonal group, IEEE Trans. on Automatic Control, vol. 53, no. 5, pp. 1203–1218, 2008.
  * [16] A. Moeini and M. Namvar, Global attitude/position estimation using landmark and biased velocity measurements, IEEE Trans. on Aerospace and Electronic Systems, vol. 52, pp. 852–862, 2016.
  * [17] M. Montemerlo and S. Thrun, FastSLAM: A Scable Method for the Simultaneous Localization and Mapping Problem in Robotics, vol. 27, New York, NY, USA, Springer, 2007.
  * [18] R. Ortega, A. Bobtsov, A. Pyrkin and S. Aranovskiy, A parameter estimation approach to state observation of nonlinear systems, Systems & Control Letters, vol. 85, 84–94, 2015.
  * [19] R. Ortega, A. Bobtsov, N. Nikolaev, J. Schiffer, D. Dochain, Generalized parameter estimation-based observers: Application to power systems and chemical-biological reactors, vol. 129, 109635, 2021
  * [20] S. Sastry and M. Bodson, Adaptive Control: Stability, Convergence and Robustness, Dover Publication, New York, 1989.
  * [21] F. Tan, W. Lohmiller and J.J. Slotine, Analytical SLAM without linearization, Int. J. of Robotics Research, vol. 36, pp. 1554–1578, 2017.
  * [22] S. Thrun and M. Montemerlo, The graph SLAM algorithm with applications to large-scale mapping of urban structures, Int. J. of Robotics Research, vol. 25, pp. 403–429, 2006.
  * [23] P. van Goor, R. Mahony, T. Hamel and J. Trumpf, Constructive observer design for visual simultaneous localisation and mapping, Automatica, vol. 132, 109803, 2021.
  * [24] B. Yi, C. Jin, L. Wang, G. Shi and I.R. Manchester, An almost globally convergent obserer for visual SLAM without persistent excitation, ArXiv Preprint, 2021. (arXiv:2104.02966)
  * [25] D. E. Zlotnik and J. R. Forbes, Gradient-based observer for simultaneous localization and mapping, IEEE Trans. on Automatic Control, vol. 63, pp. 4338–4344.