# A Framework for Prescribed-Time Control Design via Time-Scale Transformation

Amir Shakouri  Member, IEEE  and Nima Assadian  Senior Member, IEEE The
authors are with the Department of Aerospace Engineering, Sharif University of
Technology, Tehran, Iran (e-mail<EMAIL_ADDRESS>assadian@sharif.edu).

###### Abstract

This letter presents a unified framework for the design of prescribed-time
controllers under time-varying input and state constraints for normal-form
unknown nonlinear systems with uncertain input gain. The proposed approach is
based on a time-domain mapping method by which any infinite-time system can be
corresponded to a prescribed-time system and vice versa. It is shown that the
design of a constrained nonasymptotic prescribed-time controller can be
reduced to the asymptotic control design for an associated constrained
infinite-time system. Faà di Bruno’s formula and Bell polynomials are used for
a constructive representation of the associated infinite-time system. The
presented results are not confined to a particular mapping function, which
adds to the flexibility of the proposed scheme. It is shown that necessary and
sufficient conditions on the uniform (practical) prescribed-time stability and
attractivity can be obtained as corollaries of the main result.

Prescribed-time control, state and input constraints, time-transformation
mapping, Faà di Bruno’s formula, Bell polynomials.

##  1 Introduction

The nonasymptotic control of linear and nonlinear systems has been a
challenging field of research over the past two decades, and different
approaches have been developed to tackle this problem. The user command over
the time of convergence divides the nonasymptotic schemes into three major
categories of finite-time, fixed-time, and prescribed-time methods. In the
finite-time approach, the system state converges to the origin at an unknown
finite time depending on the initial conditions. Fixed-time controllers
maintain the mentioned features of the finite-time methods, while in this
category, an upper bound can be estimated for the convergence time,
independently of the initial conditions. The prescribed-time control is a
time-varying scheme where the system is forced to converge precisely at the
commanded moment. The robustness of the prescribed-time controllers (PTCs)
against matched disturbances and their adjustable settling time has many
applications in practical engineering systems, especially when multiple time-
varying systems cooperate in a dynamically changing environment. The safety
and accuracy of uncertain industrial processes, aerospace systems, robotic
systems, etc., can be enhanced by imposing hard time constraints on the
control tasks.

The nonsmooth feedback control [1, 2] and the terminal sliding mode control
[3, 4, 5] are the most popular methods for finite-time control of nonlinear
systems. To deal with uncertainties, different approaches are used in the
literature for achieving an adaptive finite-time control and tracking scheme
[6, 7, 8]. The fixed-time control is first proposed for linear systems by
Polyakov [9]. Since then, many investigations have been carried out to solve
the fixed-time control problem of nonlinear systems. The non-singular terminal
sliding mode control is proposed in [10] for a class of second-order nonlinear
systems with matched disturbances. An output feedback scheme for disturbed
double-integrator systems is addressed in [11], while the stabilization of
high-order integrator systems with mismatched disturbances is studied in [12].

Prescribed-time stabilization of uncertain nonlinear systems is originally
proposed by Song et al. in [13]. In the prescribed-time control methods, a
time transformation mapping from the infinite time scale onto a desired finite
time scale has been the central idea to achieve a time-varying controller. The
controllers obtained through this approach have also demonstrated disturbance
suppressing behavior against non-vanishing and parametric uncertainties [14,
15]. A similar approach has been used in the literature, called the
generalized time transformation method [16], which essentially incorporates
the same idea. PTCs for systems with matched uncertainty and uncertain input
gain have been studied in [17, 18]. Prescribed-time stabilization with some
robustness to unmatched uncertainties and measurement noise is investigated in
[19, 20]. A class of PTCs with linear decay rate is proposed in [21] for
unknown nonlinear systems with uncertain input gain. In addition, input-
constrained PTCs are analyzed in [22]. PTC design using parametric Lyapunov
equations is studied in [23, 24]. The prescribed-time extremum seeking control
is proposed by [25], and the inverse optimality of PTCs is studied in [26].
Moreover, a predictor-feedback PTC for systems with input delay is proposed by
[27]. In terms of applications, the reader can refer to the PTCs developed for
robotic systems in [28, 29, 30] and those tested empirically in [31, 32].

This letter presents a unified framework for the prescribed-time control of
unknown nonlinear systems in the form of a chain of integrators with matched
unmodeled dynamics subject to time-varying state and input constraints. The
proposed approach is general so that the majority of the previous methods can
be considered particular types of the presented scheme. In fact, this letter
extends the design approach studied by the authors in [29] to higher-order
nonlinear systems. In this study, using Faà di Bruno’s formula and Bell
polynomials, we introduce a constructive method to represent the associated
infinite-time version of a prescribed-time system obtained by a user-defined
sufficiently differentiable time transformation mapping function. Then, we
show that the nonasymptotic prescribed-time control design can be reduced to
the conventional asymptotic infinite-time control design for the associated
infinite-time system. Also, we show how the constraints’ role is preserved
under the mapping process.

##  2 Preliminaries

###  2.1 Notations

Let $\mathbb{R}^{m,n}$ and $\mathbb{R}^{n}$ denote the space of $m\times n$
real matrices and $n$-dimensional vectors, respectively. The $n$-dimensional
identity matrix is denoted by $\mathbb{I}_{n}$. The $i$th entry of vector $r$
and the $ij$th entry of matrix $M$ are referred to by $r_{i}$ and $M_{ij}$,
respectively. The inverse and the transpose of matrix $M$ are denoted by
$M^{-1}$ (if the inverse exists) and $M^{T}$, respectively. The inverse
function of $f(\cdot)$ is denoted by $f^{-1}(\cdot)$ (if the inverse exists).
The $i$th derivative of function $f$ with respect to its argument is shown by
$f^{(i)}$. The space of continuous functions that have continuous first $r$
derivatives on their domain is denoted by $C^{r}$ and the space of functions
that are smooth on their domain are shown by $C^{\infty}$. The 2-norm (for
vectors and matrices) and the absolute value (for scalars) are denoted by
$\|\cdot\|$ and $|\cdot|$, respectively.

The binomial coefficient, indexed by a pair of integers $n$ and $m$, is
denoted by $\genfrac{(}{)}{0.0pt}{}{n}{m}$. The number of partitions of set
$\\{1,2,\ldots,n\\}$ with block sizes $c_{1},\ldots,c_{m}$ is referred to by
$\genfrac{(}{)}{0.0pt}{}{n}{c_{1},\ldots,c_{m}}$. The partial Bell polynomials
are denoted by $B_{n,m}(s_{1},s_{2},\ldots,s_{n-m+1})$ that can be recurrently
obtained as [33]:

$B_{n,m}=\sum_{1}^{n-m+1}\genfrac{(}{)}{0.0pt}{}{n-1}{m-1}s_{i}B_{n-i,m-1},$
(1)

such that $B_{0,0}=1$, $B_{n,0}=0$ for $n\geq 1$, and $B_{0,m}=0$ for $m\geq
1$111Subscript notations $X_{ij}$ and $Y_{i,j}$ should not be confused
throughout the letter as the former addresses an entry in matrix $X$, while
the latter denotes the dependency of $Y$ on two indices $i$ and $j$..

###  2.2 System description and problem statement

Consider a nonlinear system in its normal form as follows:

$\left\\{\begin{array}[]{lcl}\dot{x}_{i}&=&x_{i+1};\quad i=1,2,\ldots,n-1\\\
\dot{x}_{n}&=&f(x,u,t)+g(x,t)u\end{array}\right.,$ (2)

where $x=[x_{1},\ldots,x_{n}]^{T}\in\mathbb{R}^{n}$ and $u\in\mathbb{R}$ are
the state vector and the control input, respectively. Functions
$f(\cdot,\cdot,\cdot):\mathbb{R}^{n}\times\mathbb{R}\times[0,\infty)\rightarrow\mathbb{R}$
and $g(\cdot,\cdot):\mathbb{R}^{n}\times[0,\infty)\rightarrow\mathbb{R}$ stand
for the unknown dynamics and the known nonzero control input gain,
respectively. Note that any uncertainty in the input gain can be accounted in
function $f(x,u,t)$.

###### Assumption 1

Suppose that system (2) is controllable, its dimension is known, and there
exists a known set-valued function $\mathcal{F}(x,u,t)\subset\mathbb{R}$ such
that $f(x,u,t)\in\mathcal{F}(x,u,t)$ for all $x\in\mathbb{R}^{n}$,
$u\in\mathbb{R}$, and $t\in[0,\infty)$.

The main problem of the letter can be stated as follows:

###### Problem 1

Let $t_{0}$ denote the initial time and
$h(\cdot,\cdot,\cdot):\mathbb{R}^{n}\times\mathbb{R}\times[0,\infty)\rightarrow\mathbb{R}^{m}$
is defined by the user. Suppose that Assumption 1 holds. Find a function
$\pi(\cdot,\cdot,\cdot):\mathbb{R}^{n}\times[0,\infty)\times(0,\infty)\rightarrow\mathbb{R}$
and a set $\mathcal{T}\subseteq(0,\infty)$ such that for every
$\tau\in\mathcal{T}$ the closed-loop solution constructed by $u=\pi(x,t,\tau)$
and system (2) satisfies a feasible control objective as:

$h(x,u,t)\in\mathcal{H}(t),\hskip 5.69054pt\forall t\in[t_{0},t_{0}+\tau),$
(3)

where $\mathcal{H}\subseteq\mathbb{R}^{m}$ is an arbitrary set-valued function
of time.

Problem 1 seeks a PTC for an unknown nonlinear system where the control
objective is considered in its most general form, allowing a wide range of
constraints involving state, input, and time. For instance, time-varying input
and output constraints such as $|u|<\delta_{\mathrm{in}}(t)$ and
$|x_{1}|<\delta_{\mathrm{out}}(t)$ can be represented by $h=u$ and $h=x_{1}$
with $\mathcal{H}(t)=\\{h:|h|<\delta_{\mathrm{in}}(t)\\}$ and
$\mathcal{H}(t)=\\{h:|h|<\delta_{\mathrm{out}}(t)\\}$, respectively. Moreover,
by means of condition (3), user-defined decay rates (e.g., faster than
exponential) or maximum energy efforts (e.g., considering a functional
$h=\int_{t_{0}}^{t}(x^{T}(\nu)Qx(\nu)+u^{T}(\nu)Ru(\nu))\mathrm{d}\nu$) can be
imposed to the system.

###  2.3 Basic definitions and formulations

The definitions and formulas introduced in this subsection are frequently used
to present and prove the main results of this letter.

######  Definition 1 (see [29])

A $C^{n}$ function $\kappa(\cdot):[0,\tau)\rightarrow[0,\infty)$ is said to be
class $\mathcal{K}$ (or $\kappa\in\mathcal{K}(\tau)$) if $\dot{\kappa}(t)>0$,
$\kappa(0)=0$, and $\lim_{t\rightarrow\tau^{-}}\kappa(t)=\infty$. This class
is a special surjective form of a more general case used in the literature
under the same name (see [34, Definition 4.2]).

######  Definition 2 (see [29])

A $C^{n}$ function $\mu(\cdot):[0,\infty)\rightarrow[0,\tau)$ is said to be
class $\mathcal{M}$ (or $\mu\in\mathcal{M}(\tau)$) if its inverse function is
class $\mathcal{K}$ (i.e., $\mu^{-1}\in\mathcal{K}(\tau)$). Therefore, $\mu$
is a continuous function subject to $\dot{\mu}(t)>0$, $\mu(0)=0$, and
$\lim_{t\rightarrow\infty}\mu(t)=\tau$.

###### Example 1

The following function is of class $\mathcal{K}$ for any $a_{i}>0$, $b_{i}>1$,
and $n\geq 1$:

$\kappa(t)=-\sum_{i=1}^{n}a_{i}\log_{b_{i}}\left(1-\frac{t}{\tau}\right),$ (4)

and the following function is a class $\mathcal{M}$ function for any
$a_{i}>1$, $b_{i}>0$, and $n\geq 1$:

$\mu(t)=\frac{1}{n}\sum_{i=1}^{n}\tau(1-a_{i}^{-b_{i}t}).$ (5)

We use $s(\cdot):\mathbb{R}\rightarrow\mathbb{R}$ as a typical sufficiently
differentiable function in our definitions, which can be replaced by any other
functions such as $\kappa(t)$ and $\mu(t)$. Define the $n\times n$-dimensional
matrix-valued functional $\mathfrak{B}_{n}[s]$ acting on a $C^{n}$ function
$s(t)$ by the following entrywise rule:

$\mathfrak{B}_{n}[s]_{ij}=\left\\{\begin{array}[]{lcl}B_{i-1,j-1}(r_{1}[s],\ldots,r_{i-j+1}[s])&&j\leq
i\leq n\\\ 0&&\mathrm{otherwise}\end{array}\right.,$ (6)

with the functional

$r_{k+1}[s]=\frac{1}{\dot{s}^{k+1}(t)}\sum_{m=0}^{k}\frac{(-1)^{m}}{\dot{s}^{m}}R_{k,m}(s^{(2)},\ldots,s^{(k-m+2)}),$
(7)

where $R_{k,m}(s^{(2)},\ldots,s^{(k-m+2)})$ can be evaluated by the sum

$R_{k,m}=\frac{1}{m!}\sum\genfrac{(}{)}{0.0pt}{}{k+m}{c_{1},\ldots,c_{m}}\prod_{l=1}^{m}s^{(c_{l})},\
\mathrm{s.t.}\ R_{0,0}=1,$ (8)

in which the sum is taken over all integers $c_{l}\geq 2$, $l=1,\ldots,m$
satisfying $\sum_{l=1}^{i}c_{l}=k+m$.

In addition, define the $(n-1)$-dimensional vector-valued functional
$\mathfrak{b}_{n-1}[s]$ as follows:

$\mathfrak{b}_{n-1}[s]=[\mathfrak{B}_{n}[s]_{n,1},\ \ldots,\
\mathfrak{B}_{n}[s]_{n(n-1)}]^{T}.$ (9)

###### Example 2

It can be verified that $r_{1}[s(t)]=1/\dot{s}(t)$ and
$r_{2}[s(t)]=-s^{(2)}(t)/\dot{s}^{3}(t)$. Thus, matrix $\mathfrak{B}_{3}$ and
vector $\mathfrak{b}_{2}$ can be evaluated as:

$\mathfrak{B}_{3}[s(t)]=\left[\begin{array}[]{ccc}1&0&0\\\
0&\frac{1}{\dot{s}(t)}&0\\\
0&-\frac{{s}^{(2)}(t)}{\dot{s}^{3}(t)}&\frac{1}{\dot{s}^{2}(t)}\end{array}\right],$
(10) $\begin{split}\mathfrak{b}_{2}[s(t)]&=[0,\
-s^{(2)}(t)/\dot{s}^{3}(t)]^{T}.\end{split}$ (11)

Tables 1 and 2 present some evaluations of functionals $R_{i,j}$ and $r_{j}$,
respectively, enough for obtaining $\mathfrak{B}_{n+1}$ and $\mathfrak{b}_{n}$
for $n=1,\ldots,5$, useful for systems up to fifth-order.

TABLE 1: Evaluation of $R_{j,i}(s^{(2)},\ldots,s^{(j-i+2)})$.

$j$ $i$ | $0$ | $1$ | $2$ | $3$ | $4$
---|---|---|---|---|---
$0$ | $1$ |  |  |  |
$1$ | $0$ | $s^{(2)}$ |  |  |
$2$ | $0$ | $s^{(3)}$ | $(s^{(2)})^{2}$ |  |
$3$ | $0$ | $s^{(4)}$ | $10s^{(2)}s^{(3)}$ | $15(s^{(2)})^{3}$ |
$4$ | $0$ | $s^{(5)}$ | $15s^{(2)}s^{(4)}+10(s^{(3)})^{2}$ | $105(s^{(2)})^{2}s^{(3)}$ | $105(s^{(2)})^{4}$

TABLE 2: Evaluation of $r_{j}[s(t)]$.

Functional | Value
---|---
$r_{1}[s]$ | $\frac{1}{\dot{s}}$
$r_{2}[s]$ | $-\frac{s^{(2)}}{\dot{s}^{3}}$
$r_{3}[s]$ | $-\frac{s^{(3)}}{\dot{s}^{4}}+\frac{(s^{(2)})^{2}}{\dot{s}^{5}}$
$r_{4}[s]$ | $-\frac{s^{(4)}}{\dot{s}^{5}}+\frac{10s^{(2)}s^{(3)}}{\dot{s}^{6}}-\frac{15(s^{(2)})^{3}}{\dot{s}^{7}}$
$r_{5}[s]$ | $-\frac{s^{(5)}}{\dot{s}^{6}}+\frac{15s^{(2)}s^{(4)}+10(s^{(3)})^{2}}{\dot{s}^{7}}-\frac{105(s^{(2)})^{2}s^{(3)}}{\dot{s}^{8}}+\frac{105(s^{(2)})^{4}}{\dot{s}^{9}}$

##  3 Main Results

Consider the following theorem as the central result of this letter:

###### Theorem 1

Suppose that Assumption 1 holds. Let $t_{0}$ denote the initial time and
$\Delta t=t-t_{0}$. Also, let $\mu\in\mathcal{M}(\tau)$,
$\kappa=\mu^{-1}\in\mathcal{K}(\tau)$, and
$\pi_{0}(\cdot,\cdot):\mathbb{R}^{n}\times[0,\infty)\rightarrow\mathbb{R}$ be
sufficiently differentiable user-defined functions by which
$\pi(\cdot,\cdot,\cdot):\mathbb{R}^{n}\times[0,\infty)\times[0,\infty)\rightarrow\mathbb{R}$
is defined as follows:

$\pi(x,t,\tau)=\frac{\dot{\kappa}^{n}(\Delta
t)}{g(x,t)}\left(\pi_{0}(x_{\kappa},t_{\kappa})-\mathfrak{b}_{n}^{T}[\kappa(\Delta
t)]x\right),$ (12)

where

$x_{\kappa}=\mathfrak{B}_{n}[\kappa(\Delta t)]x,$ (13)
$t_{\kappa}=\kappa(\Delta t)+t_{0}.$ (14)

Then, the solution of system (2) under $u=\pi(x,t,\tau)$ for every
$f(x,u,t)\in\mathcal{F}(x,u,t)$ and $\tau\in\mathcal{T}$ with initial
condition $x(t_{0})$ satisfies $h(x,u,t)\in\mathcal{H}(t)$ for all
$t\in[t_{0},t_{0}+\tau)$ if and only if the solution of the following system:

$\left\\{\begin{array}[]{lcl}\dot{\xi}_{i}&=&\xi_{i+1};\hskip
11.38109pti=1,2,\ldots,n-1\\\ \dot{\xi}_{n}&=&\dot{\mu}^{n}(\Delta
t)f_{\mu}(\xi,t)+\pi_{0}(\xi,t)\end{array}\right.$ (15)

for every $f_{\mu}(\xi,t)\in\mathcal{F}(\xi_{\mu},u_{\mu},t_{\mu})$ and
$\tau\in\mathcal{T}$ with initial condition
$\xi(t_{0})=\mathfrak{B}_{n}[\kappa(\Delta t)]_{t=t_{0}}x(t_{0})$ satisfies:

$h(\xi_{\mu},u_{\mu},t_{\mu})\in\mathcal{H}(t_{\mu})$ (16)

for all $t\in[t_{0},\infty)$, where

$\xi_{\mu}=\mathfrak{B}_{n}[\mu(\Delta t)]\xi,$ (17)
$u_{\mu}=\frac{1}{g(\xi_{\mu},t_{\mu})}\left(\frac{\pi_{0}(\xi,t)}{\dot{\mu}^{n}(\Delta
t)}+\mathfrak{b}_{n}^{T}[\mu(\Delta t)]\xi\right),$ (18) $t_{\mu}=\mu(\Delta
t)+t_{0}.$ (19)

The following corollary elaborates on the application of Theorem 1 to PTC
design with a state-constrained performance objective.

###### Corollary 1

Suppose that Assumption 1 holds. Let $t_{0}$ denote the initial time, $\Delta
t=t-t_{0}$, $\mu\in\mathcal{M}(\tau)$, and
$\kappa=\mu^{-1}\in\mathcal{K}(\tau)$. Also, let
$\zeta(\cdot):[0,\tau)\rightarrow[0,\infty)$ be a user-defined function of
time. Then, for every $f(x,u,t)\in\mathcal{F}(x,u,t)$ and $\tau\in\mathcal{T}$
the solution of system (2) under $u=\pi(x,t,\tau)$ satisfies
$\|x(t)\|\leq\sigma\|x(t_{0})\|\zeta(\Delta t)$ for some $\sigma\geq 1$ at all
$t\in[t_{0},t_{0}+\tau)$ if and only if for every
$f_{\mu}(\xi,t)\in\mathcal{F}(\xi_{\mu},u_{\mu},t_{\mu})$ and
$\tau\in\mathcal{T}$ the solution of system (15) satisfies:

$\left\|\mathfrak{B}_{n}[\mu(\Delta
t)]\xi(t)\right\|\leq\sigma\|\mathfrak{B}_{n}[\mu(\Delta
t)]_{t=t_{0}}\xi(t_{0})\|\zeta(\mu(\Delta t))$ (20)

for some $\sigma\geq 1$ at all $t\in[t_{0},\infty)$.

######  Proof 3.2.

Given Theorem 1, one may consider $h(x)=\|x\|$ and $\mathcal{H}(t)=\\{h:0\leq
h\leq\sigma\|x(t_{0})\|\zeta(\Delta t)\\}$ which means that
$\mathcal{H}(t_{\mu})=\mathcal{H}(\mu(\Delta t)+t_{0})=\\{h:0\leq
h\leq\sigma\|x(t_{0})\|\zeta(\mu(\Delta t)\\}$. Therefore, according to (16),
one may find $\|\xi_{\mu}\|\in\mathcal{H}(t_{\mu})$ as a necessary and
sufficient condition, that is inequality (20).

For PTC design subject to a time-varying constraint on the control input,
Theorem 1 reduces to the following corollary.

######  Corollary 3.3.

Suppose that Assumption 1 holds. Let $t_{0}$ denote the initial time, $\Delta
t=t-t_{0}$, $\mu\in\mathcal{M}(\tau)$, and
$\kappa=\mu^{-1}\in\mathcal{K}(\tau)$. Also, let
$\upsilon(\cdot):[0,\tau)\rightarrow[0,\infty)$ be a user-defined function of
time. Then, for every $f(x,u,t)\in\mathcal{F}(x,u,t)$ and $\tau\in\mathcal{T}$
the solution of system (2) under $u=\pi(x,t,\tau)$ satisfies
$|u|\leq\upsilon(\Delta t)$ at all $t\in[t_{0},t_{0}+\tau)$ if and only if for
every $f_{\mu}(\xi,t)\in\mathcal{F}(\xi_{\mu},u_{\mu},t_{\mu})$ and
$\tau\in\mathcal{T}$ the solution of system (15) satisfies the following
condition at all $t\in[t_{0},\infty)$:

$\left|\frac{\pi_{0}(\xi,t)}{\dot{\mu}^{n}(\Delta
t)}+\mathfrak{b}_{n}^{T}[\mu(\Delta t)]\xi\right|\leq\upsilon(\mu(\Delta t)).$
(21)

######  Proof 3.4.

Consider $h(u)=|u|$ and define $\mathcal{H}(t)=\\{h:0\leq h\leq\upsilon(\Delta
t)\\}$. The rest is similar to the proof of Corollary 1.

In the following, we discuss the application of Theorem 1 to prescribed-time
stability/attractivity analysis.

######  Definition 3.5.

System (2) under controller $u=\pi(x,t,\tau)$ is called

  1. 1.

globally practically prescribed-time attractive at every $\tau\in\mathcal{T}$
with error $\varsigma>0$, if for every $\tau\in\mathcal{T}$ and
$x(t_{0})\in\mathbb{R}^{n}$ the solution of the system satisfies
$\lim_{t\rightarrow t_{0}+\tau^{-}}\|x(t)\|\leq\varsigma$.

  2. 2.

globally (uniformly) practically prescribed-time stable if it is globally
(uniformly) stable in the sense of Lyapunov and globally practically
prescribed-time attractive.

######  Corollary 3.6.

Suppose that Assumption 1 holds. Let $t_{0}$ denote the initial time, $\Delta
t=t-t_{0}$, $\mu\in\mathcal{M}(\tau)$, and
$\kappa=\mu^{-1}\in\mathcal{K}(\tau)$. The solution of system (2) under
$u=\pi(x,t,\tau)$ for every $f(x,u,t)\in\mathcal{F}(x,u,t)$ and
$\tau\in\mathcal{T}$ is

  1. 1.

globally (uniformly) stable if and only if for every
$f_{\mu}(\xi,t)\in\mathcal{F}(\xi_{\mu},u_{\mu},t_{\mu})$ and
$\tau\in\mathcal{T}$ system (15) is globally (uniformly) stable and for every
$\xi(0)\in\mathbb{R}^{n}$ there exists $\sigma(\xi(0))>0$ such that the
solution of system (15) satisfies $\left\|\mathfrak{B}_{n}[\mu(\Delta
t)]\xi(t)\right\|\leq\sigma(\xi(0))$ for all $t\in[t_{0},\infty)$.

  2. 2.

globally practically prescribed-time attractive at every $\tau\in\mathcal{T}$
with error $\varsigma>0$ if and only if for every
$f_{\mu}(\xi,t)\in\mathcal{F}(\xi_{\mu},u_{\mu},t_{\mu})$ and
$\tau\in\mathcal{T}$ the solution of system (15) satisfies:

$\lim_{t\rightarrow\infty}\left\|\mathfrak{B}_{n}[\mu(\Delta
t)]\xi(t)\right\|\leq\varsigma.$ (22)

  3. 3.

globally (uniformly) practically prescribed-time stable if and only if items 1
and 2 are met.

######  Proof 3.7.

Item 1: Consider $h(x)=x$ and define the set
$\mathcal{H}=\\{h:\|h\|<\delta\\}$. One can verify that according to Theorem
1, if for every $f_{\mu}(\xi,t)\in\mathcal{F}(\xi_{\mu},u_{\mu},t_{\mu})$ and
$\tau\in\mathcal{T}$ system (15) satisfies
$h(\xi_{\mu})=\mathfrak{B}_{n}[\mu(\Delta t)]\xi\in\mathcal{H}$ for
$\xi(t_{0})=\mathfrak{B}_{n}[\kappa(\Delta t)]_{t=t_{0}}x_{0}$, then for every
$f(x,u,t)\in\mathcal{F}(x,u,t)$ and $\tau\in\mathcal{T}$ system (2) under
$u=\pi(x,t,\tau)$ satisfies $h(x)\in\mathcal{H}$ but for $x(t_{0})=x_{0}$.
Therefore, under the conditions described above, since
$\mathfrak{B}_{n}[\kappa(\Delta t)]_{t=t_{0}}$ is positive-definite and
$\mathfrak{B}_{n}[\mu(\Delta t)]\xi$ is bounded, if for every $\delta>0$ there
exists $\varepsilon>0$ such that the solution of system (15) satisfies
$\|\xi(t_{0})\|=\|\mathfrak{B}_{n}[\kappa(\Delta
t)]_{t=t_{0}}x_{0}\|<\varepsilon\Rightarrow h(\xi_{\mu})\in\mathcal{H}$ (which
means that system (15) is stable), then for every $\delta$ there exists
$\epsilon>0$ such that the solution of system (2) satisfies
$\|x(t_{0})\|=\|x_{0}\|<\epsilon\Rightarrow h(x)\in\mathcal{H}$ (which means
that system (2) is stable). The uniformity can be concluded by observing the
fact that $\pi(x,t,\tau)$ only depends on $\Delta t$. Item 2: The practical
prescribed-time attractivity can be proved if one considers $h(x)=x$ and
$\mathcal{H}(t)=\\{h:\ \lim_{t\rightarrow
t_{0}+\tau^{-}}\|h\|\leq\varsigma\\}$. To satisfy $h(x)\in\mathcal{H}(t)$ for
system (2) under $u=\pi(x,t,\tau)$, system (15) should satisfy
$h(\xi_{\mu})=\mathfrak{B}_{n}[\mu(\Delta t)]\xi\in\mathcal{H}(t_{\mu})=\\{h:\
\lim_{t_{\mu}\rightarrow t_{0}+\tau^{-}}\|h\|\leq\varsigma\\}=\\{h:\
\lim_{\mu(\Delta t)\rightarrow\tau^{-}}\|h\|\leq\varsigma\\}=\\{h:\
\lim_{t\rightarrow\infty}\|h\|\leq\varsigma\\}$, that is equivalent to (22).
Item 3: The proof of this item is a direct result of Definition 3.5.

######  Remark 3.8.

Many PTCs proposed in the literature can be derived from Theorem 1222MATLAB®
codes and Simulink® models for some PTCs can be found in
https://github.com/a-shakouri/prescribed-time-control. For instance, the PTC
with linear decay that is studied in [21] can be obtained by considering an
exponential mapping function and implementing the conditions of Corollary 1
with $\zeta(\Delta t)=1-\Delta t/\tau$. Other prescribed-time stable
controllers can be obtained by the use of Corollary 3.6 with different mapping
functions to handle various disturbances with different growth rates.

######  Remark 3.9.

A practically prescribed-time attractive system is just prescribed-time
attractive when the error is zero $\varsigma=0$ (see [29, Definition 3]). In
this case, the singularity at $t=t_{0}+\tau$ is an inevitable problem for many
PTCs. However, since the error $\varsigma$ is also a user-defined parameter in
most cases, the practical PTC does not compromise the advantages of an ideal
PTC in the application, while it does not suffer from the singularity at the
convergence moment.

Theorem 1 and its corollaries lead to a process for PTC design, which is
summarized in the following algorithm:

######  Algorithm 1.

Let Assumption 1 is satisfied. Identify the dimension of the system $n$ and
the set $\mathcal{F}$. Reformulate the control objectives of the system (such
as state/input/output constraints) as defined in (3) in terms of function $h$
and set $\mathcal{H}$. Do the following steps:

  1. 1.

Select a class $\mathcal{M}$ function $\mu$.

  2. 2.

According to the system dimension $n$ and function $\mu$, obtain the
functionals $\mathfrak{B}_{n}[s]$ and $\mathfrak{b}_{n}[s]$ as described in
(6) and (9).

  3. 3.

Design an infinite-time controller $\pi_{0}(\xi,t)$ such that system (15)
satisfies the control objective (16) for every
$f_{\mu}(\xi,t)\in\mathcal{F}(\xi_{\mu},u_{\mu},t_{\mu})$. If unsuccessful, go
back to step 1 and select a different class $\mathcal{M}$ function or tune its
growth rate.

  4. 4.

Obtain $\kappa=\mu^{-1}$ and construct the PTC as described in (12)–(14).

The following example demonstrates how Algorithm 1 can be implemented to a
simple system.

######  Example 3.10.

Consider a scalar first-order system $\dot{x}=a(x,u,t)+bu+gu$. Function
$a(x,u,t)$ is an unknown non-vanishing but bounded disturbance. Constant $b$
is unknown and satisfies $|b|<|g|$. In terms of system (2), we have
$f(x,u,t)=a(x,u,t)+bu$, and $\mathcal{F}$ contains all functions $a(x,u,t)+bu$
such that the conditions on $a(x,u,t)$ and $b$ are met. The control objectives
are $|x(t)|\leq\phi|x(0)|$, $\phi>1$, and $\lim_{t\rightarrow\tau}|x(t)|=0$,
which can be formulated as $h=|x(t)|$ and $\mathcal{H}=\\{h:\
h\leq\phi|x(0)|,\ \lim_{t\rightarrow\tau}h\leq\sigma\\}$. As the system is
scalar, we have $n=1$, $\mathfrak{B}_{1}=1$, and $\mathfrak{b}_{1}=0$. We
choose $\kappa=-\ln\left(1-t/\tau\right)$, and correspondingly
$\mu=\tau(1-\exp(-t))$. Hence, system (15) reduces to
$\dot{\xi}=\tau\exp(-t)a+(b/g+1)\pi_{0}$ (which has a vanishing uncertainty
and an always positive control gain). We choose an infinite-time controller as
$\pi_{0}(\xi)=-\frac{\psi\xi}{(|\xi|-\phi|\xi(0)|)^{2}}$, $\psi>0$ that
satisfies $|\xi(t)|\leq\phi|\xi(0)|$ and $\lim_{t\rightarrow\infty}\xi(t)=0$.
Therefore, a PTC as $\pi(x,t)=-\frac{\psi x}{g(\tau-t)(|x|-\phi|x(0)|)^{2}}$
satisfies the control objectives of the main system. Fig. 1 shows the
simulation results for $a(x,u,t)=0.1-t^{3}\exp(-t)\sin(x/(u+0.001))$, $g=1$,
$b=-0.5$, $\phi=1.1$, $\psi=20$, and different values of convergence time
$\tau$ corresponding to initial condition $x(0)=1$.

Fig. 1: Simulation results for Example 3.10.

##  4 Proof of Theorem 1

Without loss of generality, we prove Theorem 1 for the case of unity input
gain $g(x,t)=1$. In the first step, we deal with the nominal system that is a
chain of integrators. Next, we find how the unmodeled term, $f(x,u,t)$,
affects the obtained results.

The following lemmas can be evaluated after considering Definitions 1 and 2:

######  Lemma 4.11 (see [29]).

The following statements hold for any functions $\kappa\in\mathcal{K}(\tau)$
and $\mu=\kappa^{-1}\in\mathcal{M}(\tau)$:

  1. 1.

$\dot{\kappa}(\cdot):[0,\tau)\rightarrow[0,\infty)$,
$\ddot{\kappa}(\cdot):[0,\tau)\rightarrow[0,\infty)$, and
$\lim_{t\rightarrow\tau^{-}}\dot{\kappa}(t)=\lim_{t\rightarrow\tau^{-}}\ddot{\kappa}(t)=\infty$.

  2. 2.

$\dot{\mu}(\cdot):[0,\infty)\rightarrow[0,\infty)$,
$\ddot{\mu}(\cdot):[0,\infty)\rightarrow(-\infty,0]$, and
$\lim_{t\rightarrow\infty}\dot{\mu}(t)=-\lim_{t\rightarrow\infty}\ddot{\mu}(t)=0$.

  3. 3.

The sum of two class $\mathcal{K}$ functions belongs to class $\mathcal{K}$,
and the sum of two class $\mathcal{M}$ functions divided by $2$ belongs to
class $\mathcal{M}$.

  4. 4.

Function $\dot{\mu}^{\alpha}(t)$ for $\alpha\geq 1$ is the derivative of a
class $\mathcal{M}$ function.

  5. 5.

Any exponential function of the form $\beta\exp(-\alpha t)$ with arbitrary
$\alpha>0$ can be the derivative of a class $\mathcal{M}(\tau)$ function if
and only if $\beta=\alpha\tau$.

Henceforth, for a function $s(\cdot)$, we use the following derivative
notations: $\dot{s}=\mathrm{d}s/\mathrm{d}t$ and
$\acute{s}=\mathrm{d}s/\mathrm{d}\mu$. To take the role of initial time
$t_{0}$ into account, let us define the operator $\Delta$ that acts on any
variable $s$ as $\Delta s=s-t_{0}$ (similar to $\Delta t=t-t_{0}$). Also, let
us define functions
$\tilde{\mu}(\cdot):[t_{0},\infty)\rightarrow[t_{0},t_{0}+\tau)$ and
$\tilde{\kappa}(\cdot):[t_{0},t_{0}+\tau)\rightarrow[t_{0},\infty)$ that are
functions $\mu\in\mathcal{M}$ and $\kappa\in\mathcal{K}$ which are shifted
$t_{0}$ units up and right:

$\displaystyle\tilde{\mu}(t)$ $\displaystyle=\mu(\Delta t)+t_{0},$ (23a)
$\displaystyle\tilde{\kappa}(\tilde{\mu})$
$\displaystyle=\kappa(\Delta\tilde{\mu})+t_{0}.$ (23b)

One can verify that $\tilde{\mu}$ is the inverse function of $\tilde{\kappa}$,
$\Delta\tilde{\mu}=\mu(\Delta t)$, and
$\Delta\tilde{\kappa}=\kappa(\Delta\tilde{\mu})$. Since
$\dot{\tilde{\mu}}(t)=\dot{\mu}(\Delta t)$ and
$\acute{\tilde{\kappa}}(\tilde{\mu})=\acute{\kappa}(\Delta\tilde{\mu})$, we
use the derivatives of $\mu(\Delta t)$ and $\kappa(\Delta\tilde{\mu})$ instead
of the derivatives of $\tilde{\mu}(t)$ and $\tilde{\kappa}(\tilde{\mu})$,
respectively.

Consider a chain of integrators under an input $u=\pi_{0}(\xi,t)$ as follows:

$\left\\{\begin{array}[]{lcl}\dot{\xi}_{i}&=&\xi_{i+1};\quad
i=1,2,\ldots,n-1\\\ \dot{\xi}_{n}&=&\pi_{0}(\xi,t)\end{array}\right..$ (24)

Let us map the solutions of system (24) from $[t_{0},\infty)$ onto
$[t_{0},t_{0}+\tau)$ with the following equivalent rules:

$\displaystyle\chi_{1}(\tilde{\mu}(t))$ $\displaystyle=\xi_{1}(t),\hskip
11.38109pt$ $\displaystyle t\in[t_{0},\infty),$ (25a)
$\displaystyle\xi_{1}(\tilde{\kappa}(\tilde{\mu}))$
$\displaystyle=\chi_{1}(\tilde{\mu}),\hskip 11.38109pt$
$\displaystyle\tilde{\mu}\in[t_{0},t_{0}+\tau).$ (25b)

Furthermore, we define $\mathrm{d}\chi_{i}/\mathrm{d}\tilde{\mu}=\chi_{i+1}$
and $\chi=[\chi_{1},\ldots,\chi_{n}]^{T}$. For evaluating the derivatives of
higher orders, consider the following lemmas:

######  Lemma 4.12 (Faà di Bruno’s formula).

Suppose $s_{1}(\cdot)$ and $s_{2}(\cdot)$ are sufficiently differentiable
functions. Then:

$\begin{split}\frac{\mathrm{d}^{i}}{\mathrm{d}t^{i}}s_{1}(s_{2}(t))=\sum_{j=1}^{i}s_{1}^{(j)}(s_{2}(t))B_{i,j}(s_{2}^{(1)}(t),\ldots,s_{2}^{(i-j+1)}(t)).\end{split}$
(26)

######  Proof 4.13.

This lemma is the Bell polynomial version of the well-known Faà di Bruno’s
formula, which is also known as Riordan’s formula [35].

######  Lemma 4.14.

Let $s_{1}(\cdot)$ and $s_{2}(\cdot)$ are sufficiently differentiable and
invertible functions such that $s_{1}$ is the inverse function of $s_{2}$,
i.e., $s_{1}(s_{2}(t))=t$. The following formula relates the $k$th-order
derivative of $s_{2}(t)$ to the derivatives of $s_{1}(s_{2})$:

$s_{2}^{(k)}(t)=r_{k}(s_{1}(s_{2})),$ (27)

where functional $r_{k}$ is defined in (7).

######  Proof 4.15.

Equation (27) is an extension of the Faà di Bruno’s formula presented in Lemma
4.12 for inverse functions. This version is proved in [36].

######  Lemma 4.16.

Let $\mathrm{d}\chi_{i}/\mathrm{d}\tilde{\mu}=\chi_{i+1}$, $i=1,\ldots,n$.
Suppose $\tilde{\mu}$ and $\chi_{1}$ are sufficiently differentiable functions
and equations (24) and (25a) hold. Then:

$\displaystyle\xi(t)$
$\displaystyle=\mathfrak{B}_{n}[\kappa(\Delta\tilde{\mu})]\chi(\tilde{\mu}),$
(28a) $\displaystyle\chi(\tilde{\mu})$
$\displaystyle=\mathfrak{B}_{n}[\mu(\Delta t)]\xi(t).$ (28b)

######  Proof 4.17.

To prove (28a), observe that given Lemma 4.12, by setting $s_{1}=\chi_{i}$ and
$s_{2}=\tilde{\mu}(t)$, one obtains:

$\begin{split}\xi_{i+1}(t)&=\chi_{i+1}(\tilde{\mu}(t))=\frac{\mathrm{d}^{i}}{\mathrm{d}t^{i}}\chi(\tilde{\mu}(t))\\\
&=\sum_{j=1}^{i}\chi^{(j)}(\tilde{\mu})B_{i,j}(\tilde{\mu}^{(1)}(t),\ldots,\tilde{\mu}^{(i-j+1)}(t)).\end{split}$
(29)

From Lemma 4.14, we have $\tilde{\mu}^{(k)}(t)=r_{k}(\kappa(\mu))$. Therefore,
using definition (6) and knowing that $\chi^{(j)}(\tilde{\mu})=\chi_{j+1}$, a
substitution yields identity (28a). The same procedure can be utilized for the
proof of (28b).

Observe that formulas (28a) and (28b) can also be stated in the following
component forms:

$\displaystyle\dot{\xi}_{n}(t)$
$\displaystyle=\frac{1}{\acute{\kappa}^{n}(\Delta\tilde{\mu})}\acute{\chi}_{n}(\tilde{\mu})+\mathfrak{b}_{n}^{T}[\kappa(\Delta\tilde{\mu})]\chi(\tilde{\mu}),$
(30a) $\displaystyle\acute{\chi}_{n}(\tilde{\mu})$
$\displaystyle=\frac{1}{\dot{\mu}^{n}(\Delta
t)}\dot{\xi}_{n}(t)+\mathfrak{b}_{n}^{T}[\mu(\Delta t)]\xi(t),$ (30b)

which yields the following identity:

$\dot{\mu}^{n}(\Delta t)\mathfrak{b}_{n}^{T}[\mu(\Delta
t)]\xi(t)=-\mathfrak{b}_{n}^{T}[\kappa(\Delta\tilde{\mu})]\chi(\tilde{\mu}).$
(31)

Moreover, one can verify that the infinite time scale $t$ can be expressed in
terms of a class $\mathcal{K}$ function with argument $\tilde{\mu}$ as
follows:

$t=\kappa(\Delta\tilde{\mu})+t_{0}.$ (32)

Substituting (28a), (30a), and (32) in system (24), the following system can
be obtained in terms of $\chi$ and $\tilde{\mu}$:

$\left\\{\begin{array}[]{lcl}\acute{\chi}_{i}&=&\chi_{i+1};\hskip
11.38109pti=1,2,\ldots,n-1\\\
\acute{\chi}_{n}&=&\acute{\kappa}^{n}(\Delta\tilde{\mu})\left(\pi_{0}(\chi_{\kappa},\tilde{\mu}_{\kappa})-\mathfrak{b}_{n}^{T}[\kappa(\Delta\tilde{\mu})]\chi\right)\end{array}\right.,$
(33)

where $\chi_{\kappa}=\mathfrak{B}_{n}[\kappa(\Delta\tilde{\mu})]\chi$ and
$\tilde{\mu}_{\kappa}=\kappa(\Delta\tilde{\mu})+t_{0}$. System (33) imitates
the infinite-time behavior of system (24) in a prescribed finite time interval
of $\tau$ such that the maximum and minimum of $\xi_{1}$ remains the same for
$\chi_{1}$. Observe that system (33) is the closed-loop response of system (2)
with $f=0$ and $g(x,t)=1$ under $u=\pi(x,t,\tau)$, when $x$ and $t$ are
replaced by $\chi$ and $\tilde{\mu}$.

Applying the disturbance term $f$ to system (33) and inverse mapping it from
$[t_{0},t_{0}+\tau)$ onto $[t_{0},\infty)$, yields the following system:

$\left\\{\begin{array}[]{lcl}\dot{\xi}_{i}&=&\xi_{i+1};\quad
i=1,2,\ldots,n-1\\\ \dot{\xi}_{n}&=&\dot{\mu}^{n}(\Delta
t)f(\xi_{\mu},u_{\mu},t_{\mu})+\pi_{0}(\xi,t)\end{array}\right.,$ (34)

where $\xi_{\mu}$, $u_{\mu}$, and $t_{\mu}$ are described in (17), (18), and
(19), respectively. Therefore, system (34) is a chain of integrators under a
(most likely vanishing) matched disturbance $\dot{\mu}^{n}(\Delta
t)f(\xi_{\mu},u_{\mu},t_{\mu})$ with $\pi_{0}(\xi,t)$ as an input signal.
Given Assumption 1, we know that
$f(\xi_{\mu},u_{\mu},t_{\mu})\in\mathcal{F}(\xi_{\mu},u_{\mu},t_{\mu})$. Since
variables $\xi_{\mu}$, $u_{\mu}$, $\pi_{0}(\xi,t)$, and
$t_{\mu}=\tilde{\mu}(t)$ are functions of $\xi$ and $t$, we rename
$f(\xi_{\mu},u_{\mu},t_{\mu})$ as $f_{\mu}(\xi,t)$ to be directly expressed in
terms of the system variables. As the final step, verify that according to the
developed formulas, an output signal of system (34) written as
$h(\xi_{\mu},u_{\mu},t_{\mu})$ evaluated at $t_{\mu}$, is equal to output
signal $h(x,u,t)$ of system (2) under $u=\pi(x,t,\tau)$ evaluated at $t$.

##  5 Conclusions

A general time-transformation methodology has been formulated, which unifies
the mapping approaches into a universal representation towards prescribed-time
control (PTC) design. In the light of the presented framework, it has been
shown that a nonasymptotic PTC design subject to any nonlinear control
objectives can be viewed as a traditional asymptotic control design for the
associated infinite-time system under a new set of control objectives.

## References

  * [1] Y. Hong, J. Huang, and Y. Xu, “On an output feedback finite-time stabilization problem,” _IEEE Transactions on Automatic Control_ , vol. 46, no. 2, pp. 305–309, 2001.
  * [2] Y. Hong, Y. Xu, and J. Huang, “Finite-time control for robot manipulators,” _Systems & Control Letters_, vol. 46, no. 4, pp. 243–253, 2002.
  * [3] V. Parra-Vega and G. Hirzinger, “Chattering-free sliding mode control for a class of nonlinear mechanical systems,” _International Journal of Robust and Nonlinear Control_ , vol. 11, no. 12, pp. 1161–1178, 2001.
  * [4] Y. Feng, X. Yu, and Z. Man, “Non-singular terminal sliding mode control of rigid manipulators,” _Automatica_ , vol. 38, no. 12, pp. 2159–2167, 2002\.
  * [5] S. Yu, X. Yu, B. Shirinzadeh, and Z. Man, “Continuous finite-time control for robotic manipulators with terminal sliding mode,” _Automatica_ , vol. 41, no. 11, pp. 1957–1964, 2005.
  * [6] Y. Hong, J. Wang, and D. Cheng, “Adaptive finite-time control of nonlinear systems with parametric uncertainty,” _IEEE Transactions on Automatic control_ , vol. 51, no. 5, pp. 858–862, 2006.
  * [7] J. Huang, C. Wen, W. Wang, and Y.-D. Song, “Design of adaptive finite-time controllers for nonlinear uncertain systems based on given transient specifications,” _Automatica_ , vol. 69, pp. 395–404, 2016.
  * [8] H. Li, S. Zhao, W. He, and R. Lu, “Adaptive finite-time tracking control of full state constrained nonlinear systems with dead-zone,” _Automatica_ , vol. 100, pp. 99–107, 2019.
  * [9] A. Polyakov, “Nonlinear feedback design for fixed-time stabilization of linear control systems,” _IEEE Transactions on Automatic Control_ , vol. 57, no. 8, pp. 2106–2110, 2011.
  * [10] Z. Zuo, “Non-singular fixed-time terminal sliding mode control of non-linear systems,” _IET control theory & applications_, vol. 9, no. 4, pp. 545–552, 2014.
  * [11] B. Tian, Z. Zuo, X. Yan, and H. Wang, “A fixed-time output feedback control scheme for double integrator systems,” _Automatica_ , vol. 80, pp. 17–24, 2017.
  * [12] B. Tian, H. Lu, Z. Zuo, and H. Wang, “Fixed-time stabilization of high-order integrator systems with mismatched disturbances,” _Nonlinear Dynamics_ , vol. 94, no. 4, pp. 2889–2899, 2018.
  * [13] Y. Song, Y. Wang, J. Holloway, and M. Krstic, “Time-varying feedback for regulation of normal-form nonlinear systems in prescribed finite time,” _Automatica_ , vol. 83, pp. 243–251, 2017.
  * [14] Y. Wang and Y. Song, “A general approach to precise tracking of nonlinear systems subject to non-vanishing uncertainties,” _Automatica_ , vol. 106, pp. 306–314, 2019.
  * [15] A. Irscheid, S. Bleymehl, and J. Rudolph, “Stabilisierung flacher systeme in vorgebbarer endlicher zeit,” _at - Automatisierungstechnik_ , vol. 69, no. 7, pp. 585–596, 2021.
  * [16] D. Tran and T. Yucelen, “Finite-time control of perturbed dynamical systems based on a generalized time transformation approach,” _Systems & Control Letters_, vol. 136, p. 104605, 2020.
  * [17] P. Krishnamurthy, F. Khorrami, and M. Krstic, “A dynamic high-gain design for prescribed-time regulation of nonlinear systems,” _Automatica_ , vol. 115, p. 108860, 2020.
  * [18] P. Krishnamurthy and F. Khorrami, “Prescribed-time stabilization of nonlinear systems with uncertain input gain and non-vanishing disturbances,” in _2020 European Control Conference (ECC)_. IEEE, 2020, pp. 1859–1864.
  * [19] Y. Chitour, R. Ushirobira, and H. Bouhemou, “Stabilization for a perturbed chain of integrators in prescribed time,” _SIAM Journal on Control and Optimization_ , vol. 58, no. 2, pp. 1022–1048, 2020.
  * [20] H. Ye and Y. Song, “Prescribed-time control of uncertain strict-feedback-like systems,” _International Journal of Robust and Nonlinear Control_ , vol. 31, no. 11, pp. 5281–5297, 2021.
  * [21] A. Shakouri and N. Assadian, “Prescribed-time control with linear decay for nonlinear systems,” _IEEE Control Systems Letters_ , vol. 6, pp. 313–318, 2021.
  * [22] K. Garg, E. Arabi, and D. Panagou, “Prescribed-time convergence with input constraints: A control Lyapunov function based approach,” in _2020 American Control Conference (ACC)_. IEEE, 2020, pp. 962–967.
  * [23] B. Zhou, “Finite-time stabilization of linear systems by bounded linear time-varying feedback,” _Automatica_ , vol. 113, p. 108760, 2020.
  * [24] B. Zhou and Y. Shi, “Prescribed-time stabilization of a class of nonlinear systems by linear time-varying feedback,” _IEEE Transactions on Automatic Control_ , 2021.
  * [25] J. I. Poveda and M. Krstic, “Non-smooth extremum seeking control with user-prescribed fixed-time convergence,” _IEEE Transactions on Automatic Control_ , 2021.
  * [26] W. Li and M. Krstic, “Stochastic nonlinear prescribed-time stabilization and inverse optimality,” _IEEE Transactions on Automatic Control_ , 2021.
  * [27] N. Espitia and W. Perruquetti, “Predictor-feedback prescribed-time stabilization of lti systems with input delay,” _IEEE Transactions on Automatic Control_ , 2021.
  * [28] Q. Cui, H. Cao, Y. Wang, and Y. Song, “Prescribed time tracking control of constrained Euler–Lagrange systems: An adaptive proportional–integral solution,” _International Journal of Robust and Nonlinear Control_ , 2021\.
  * [29] A. Shakouri and N. Assadian, “Prescribed-time control for perturbed Euler-Lagrange systems with obstacle avoidance,” _IEEE Transactions on Automatic Control_ , 2021.
  * [30] Y. Cao, J. Cao, and Y. Song, “Practical prescribed time control of Euler-Lagrange systems with partial/full state constraints: A settling time regulator-based approach,” _IEEE Transactions on Cybernetics_ , 2021\.
  * [31] Z. Wang, B. Liang, Y. Sun, and T. Zhang, “Adaptive fault-tolerant prescribed-time control for teleoperation systems with position error constraints,” _IEEE Transactions on Industrial Informatics_ , vol. 16, no. 7, pp. 4889–4899, 2019.
  * [32] K. Zhang, B. Zhou, H. Jiang, G. Liu, and G.-R. Duan, “Practical prescribed-time sampled-data control of linear systems with applications to the air-bearing testbed,” _IEEE Transactions on Industrial Electronics_ , 2021.
  * [33] L. Comtet, _Advanced combinatorics: The art of finite and infinite expansions_. Springer Science & Business Media, 2012.
  * [34] H. K. Khalil and J. W. Grizzle, _Nonlinear systems_. Prentice Hall, Upper Saddle River, NJ, 2002, vol. 3.
  * [35] W. P. Johnson, “The curious history of Faà di Bruno’s formula,” _The American Mathematical Monthly_ , vol. 109, no. 3, pp. 217–234, 2002\.
  * [36] ——, “Combinatorics of higher derivatives of inverses,” _The American Mathematical Monthly_ , vol. 109, no. 3, pp. 273–277, 2002.


# End-to-end Learning the Partial Permutation Matrix
for Robust 3D Point Cloud Registration

Zhiyuan Zhang1, Jiadai Sun1, Yuchao Dai1, Dingfu Zhou2, Xibin Song2, Mingyi
He1 Yuchao Dai is the corresponding author.

###### Abstract

Even though considerable progress has been made in deep learning-based 3D
point cloud processing, how to obtain accurate correspondences for robust
registration remains a major challenge because existing hard assignment
methods cannot deal with outliers naturally. Alternatively, the soft matching-
based methods have been proposed to learn the matching probability rather than
hard assignment. However, in this paper, we prove that these methods have an
inherent ambiguity causing many deceptive correspondences. To address the
above challenges, we propose to learn a partial permutation matching matrix,
which does not assign corresponding points to outliers, and implements hard
assignment to prevent ambiguity. However, this proposal poses two new
problems, _i.e_. existing hard assignment algorithms can only solve a full
rank permutation matrix rather than a partial permutation matrix, and this
desired matrix is defined in the discrete space, which is non-differentiable.
In response, we design a dedicated soft-to-hard (S2H) matching procedure
within the registration pipeline consisting of two steps: solving the soft
matching matrix (S-step) and projecting this soft matrix to the partial
permutation matrix (H-step). Specifically, we augment the profit matrix before
the hard assignment to solve an augmented permutation matrix, which is cropped
to achieve the final partial permutation matrix. Moreover, to guarantee end-
to-end learning, we supervise the learned partial permutation matrix but
propagate the gradient to the soft matrix instead. Our S2H matching procedure
can be easily integrated with existing registration frameworks, which has been
verified in representative frameworks including DCP, RPMNet, and DGR.
Extensive experiments have validated our method, which creates a new state-of-
the-art performance for robust 3D point cloud registration. The code will be
made public.

## Introduction

3D point cloud registration is a well-known task in 3D vision with wide
applications including object pose estimation (Wong et al. 2017), 3D
reconstruction (Deschaud 2018), simultaneous localization and mapping
(Shiratori et al. 2015; Ding and Feng 2019), _etc_. Although the increasingly
prosperous deep learning technique has achieved great success in point cloud
registration (Lu et al. 2019), how to obtain accurate correspondences for
robust registration remains a stubborn problem, which can be formulated as
solving a matching matrix to relate the input two point clouds. And each entry
indicates the point pair is a correspondence or not.

For ideal consistent point clouds, where the inputs are exactly the same
except for the pose, _i.e_. each point can find a corresponding point in the
other point cloud, the correspondences are built by searching a permutation
matching matrix, which implements the one-to-one matching principle. However,
in practical applications, input point clouds are usually not consistent due
to the outliers (_i.e_. the points without corresponding points). To handle
the outliers, a widely adopted strategy is to select reliable correspondences
after the initial matching (Choy, Dong, and Koltun 2020; Probst et al. 2019;
Pais et al. 2020; Deng, Birdal, and Ilic 2018b; Deng, Birdal, and Ilic 2018a;
Bai et al. 2021). Nonetheless, this remedial operation is complicated.
Alternatively, we propose to handle the outliers in the matching stage
synchronously. In this case, the desired matching matrix is turned to a
partial permutation matrix (notated as PPM) formulated by a binary matrix,
where the sum of row or column corresponding to inlier/outlier is one/zero.
PPM embeds two important principles: one-to-one matching and outliers pruning.
Unfortunately, existing hard assignment algorithms are not competent to
directly solve this PPM since they cannot distinguish inliers and outliers,
and they will solve a full rank permutation matrix assigning corresponding
points to outliers incorrectly.

Methods |  DCP (Soft matching) |  RPMNet (Soft matching) |  PRNet (Hard matching) |  Ours (Hard matching)
---|---|---|---|---
|  Matrix
---
Constraints
|  $m_{ij}\in[0,1]$
---
$\sum_{j}^{N_{\mathcal{Y}}}m_{ij}=1$
|  $m_{ij}\in[0,1]$
---
$\sum_{i}^{N_{\mathcal{X}}}m_{ij}\in[0,1]$
$\sum_{j}^{N_{\mathcal{Y}}}m_{ij}\in[0,1]$
|  $m_{ij}\in\\{0,1\\}$
---
$\sum_{j}^{N_{\mathcal{Y}}}m_{ij}=1$
|  $m_{ij}\in\\{0,1\\}$
---
$\sum_{i}^{N_{\mathcal{X}}}m_{ij}\in\\{0,1\\}$
$\sum_{j}^{N_{\mathcal{Y}}}m_{ij}\in\\{0,1\\}$
|  Matching
---
Results
|
---
|
---
|
---
|
---

Table 1: Comparison of learning-based point cloud registration methods based
on “soft” matching and “hard” matching. Points with different colors indicate
the source (green), target (blue), and virtual points (red). Connection line
indicates the correspondences. $m_{ij}$ is the entry of matching matrix
$\mathbf{M}\in\mathbb{R}^{N_{\mathcal{X}}\times N_{\mathcal{Y}}}$, where
$N_{\mathcal{X}}$, $N_{\mathcal{Y}}$ are size of the source and target. (The
matching result of ours is returned by $\text{SHM}_{\text{DCP}}$.)

Moreover, PPM is defined in the discrete space, and the hard assignment
algorithm is non-differentiable, which is fatal for the deep learning
pipeline. To address this issue, soft matching-based methods are proposed.
They relax the discrete matching matrix into a continuous one, where each
entry is either zero or one, and then the virtual points are achieved by
performing weighted average to replace the real corresponding points. However,
since the geometric constraint is ignored, the network does not learn the
underlying physics, which results in an inherent ambiguity making the
distribution of the virtual points degenerate seriously. DCP (Wang and Solomon
2019a) is a typical soft matching method, which suffers from this drawback as
shown in Table 1. RPMNet (Yew and Lee 2020) applies the Augmented-Sinkhorn
algorithm replying to outliers in the soft matching process, where the “trash
bin” strategy (Sarlin et al. 2020) is employed. However, the degeneration has
not been remitted. To avoid this ambiguity trap, DeepVCP (Lu et al. 2019)
takes an unconvincing assumption, _i.e_. accurate initial motion parameters
are provided as prior. PRNet (Wang and Solomon 2019b) and CorrNet3D (Zeng et
al. 2021) advocate turning the learned soft matching matrix to a hard matrix
by taking the most similar points as the corresponding points of the source
points. However, this strategy leads to the drawback of one-to-many matching.

In this paper, we first theoretically analyze the inherent ambiguity in these
soft matching-based methods, and then devote to achieving the real PPM matrix
to handle the outliers and prevent ambiguity synchronously for robust 3D point
cloud registration. However, as mentioned above, two problems block our pace.
1) Although it is well-known that the full rank permutation matrix can be
solved by existing hard assignment algorithms, how to solve a PPM has yet not
been explored; 2) PPM is defined in the discrete space, which is non-
differentiable. To resolve these issues, we design a dedicated soft-to-hard
(S2H) matching procedure consists of S-step: solving the soft matching matrix,
and H-step: projecting this soft matrix to the PPM. Specifically, we propose
to augment the profit matrix before the hard assignment to solve an augmented
permutation matrix, which is cropped to achieve the final real PPM. Moreover,
to guarantee end-to-end learning, we supervise the learned final PPM but
propagate the gradient to the soft matrix instead. Our matching procedure can
be easily integrated with existing 3D registration frameworks, which has been
verified in DCP, RPMNet, and DGR (Choy, Dong, and Koltun 2020). Extensive
experiments on benchmark datasets show that our method achieves state-of-the-
art performance.

Our main contributions can be summarized as follows:

  * •

We theoretically analyze the inherent ambiguity in the soft matching-based
methods, which causes serious degeneration of the learned virtual
corresponding points.

  * •

We propose a novel S2H matching procedure to learn the PPM, which handles the
outliers and prevents ambiguity synchronously. This matching procedure not
only solves a real PPM, but also guarantees end-to-end learning.

  * •

Remarkable performance on benchmark datasets verifies the proposed method,
which achieves state-of-the-art performance in robust 3D point cloud
registration.

## Related Works

Herein, we briefly review the learning-based point cloud registration methods.
More detailed summaries have been provided in (Rusinkiewicz and Levoy 2001;
Pomerleau, rancis Colas, and Siegwart 2015; Zhang, Dai, and Sun 2020).

Correspondences-free methods: These methods estimate the rigid motion by
comparing the global representations of input two point clouds, and generally
consist of two stages: global feature extraction and rigid motion estimation.
PointNetLK (Aoki et al. 2019) utilizes PointNet (Qi et al. 2017a) to extract
global features, and then a modified LK algorithm is applied to solve the
rigid motion. From the perspective of reconstruction, Huang _et al_. (Huang,
Mei, and Zhang 2020) utilize an encoder-decoder structure network to learn a
more comprehensive global feature.

Correspondences-based methods: These methods estimate the rigid motion based
on correspondences, which generally consists of feature extractor,
correspondences building, and rigid motion estimation modules. For feature
extractors, various well-designed networks are used, such as set abstraction
module (Qi et al. 2017b; Yew and Lee 2018), DGCNN (Wang et al. 2019; Wang and
Solomon 2019a), FCGF (Choy, Park, and Koltun 2019; Choy, Dong, and Koltun
2020), globally informed 3D local feature (Deng, Birdal, and Ilic 2018b),
KPConv (Thomas et al. 2019; Bai et al. 2020), capsule network (Zhao et al.
2020) and various rotation invariant features (Deng, Birdal, and Ilic 2018a;
Gojcic et al. 2019). With the rise of deep learning, learning-based feature
extractors have approached standard components, which can be integrated
easily. For correspondence building, both soft matching-based (Lu et al. 2019;
Wang and Solomon 2019a) and hard matching-based (Wang and Solomon 2019b)
methods are representative. (Yew and Lee 2020; Huang et al. 2021) build
correspondences on the identified inliers only. Besides, reliable
correspondences selection is the widely adopted subsequent step. It is
achieved by learning the reliability weight of each initial correspondence
(Pais et al. 2020; Choy, Dong, and Koltun 2020; Probst et al. 2019) or
selecting consistent correspondences (Deng, Birdal, and Ilic 2018b; Bai et al.
2021). For motion estimation, Procrustes (Gower 1975) is the most widely used
algorithm in (Wang and Solomon 2019b; Yew and Lee 2020). Recently, regressing
the motion parameters directly has become a new hot spot (Pais et al. 2020).

## Preliminaries

Given the source point cloud $\mathcal{X}=[\boldsymbol{x}_{i}]_{3\times
N_{\mathcal{X}}}$ and the target point cloud
$\mathcal{Y}=[\boldsymbol{y}_{j}]_{3\times N_{\mathcal{Y}}}$, where
$N_{\mathcal{X}}$ and $N_{\mathcal{Y}}$ represent the sizes of the two point
clouds, 3D point cloud registration aims at solving a rigid motion to best
align $\mathcal{X}$ with $\mathcal{Y}$. Here, we model the rigid motion by the
rotation matrix $\mathbf{R}\in SO(3)$ and the translation vector
$\mathbf{t}\in\mathbb{R}^{3}$. Since the Procrustes algorithm (Gower 1975) can
optimally solve the rigid motion based on the correspondences, point matching
becomes crucial, which is formulated as searching for a matching matrix
$\mathbf{M}=[m_{ij}]_{N_{\mathcal{X}}\times N_{\mathcal{Y}}}$ to relate the
source and target point clouds, and the entry $m_{ij}=1$ or $0$ indicates
point $\boldsymbol{x}_{i}$ and point $\boldsymbol{y}_{j}$ are correspondence
or not.

Ideally, $\mathcal{X}$ and $\mathcal{Y}$ are consistent, _i.e_. points in
$\mathcal{X}$ and $\mathcal{Y}$ are exactly one-to-one correspondence. In this
case, the matching matrix $\mathbf{M}$ is a permutation matrix, _i.e_.
$m_{ij}\\!\in\\!\\{0,1\\}$, $\sum_{i=1}^{N}m_{ij}\\!=\\!1,\forall j$ and
$\sum_{j=1}^{N}m_{ij}\\!=\\!1,\forall i$, where
$N_{\mathcal{X}}\\!=\\!N_{\mathcal{Y}}\\!=\\!N$. However, in practical
applications, outliers always exist without corresponding points. They
challenge the matching problem, and turn it into a special assignment problem
while the desired matching matrix becomes a PPM for outliers pruning. We
reformulate this special PPM $\mathbf{M}$ as,

$\displaystyle\\{\mathbf{M}$ $\displaystyle\ |\ m_{ij}\in\\{0,1\\};$ (1)
$\displaystyle\sum\nolimits_{i=1}^{N_{\mathcal{X}}}m_{ij}\\!\in\\!\\{0,1\\},\forall
j;\sum\nolimits_{j=1}^{N_{\mathcal{Y}}}m_{ij}\\!\in\\!\\{0,1\\},\forall i\\}.$

If the point is an inlier, the sum of the corresponding row/column equals to
1. Otherwise, the point is an outlier and the sum of the corresponding
row/column equals to 0.

### Ambiguity in soft matching-based methods

As introduced above, different from the hard matching-based methods that build
correspondences on the real points, the soft matching-based methods use the
virtual corresponding points instead. Specifically, these soft matching-based
methods generate a “soft map” between the source and target, _i.e_.
$\boldsymbol{x}_{i}\in\mathcal{X}$ is assigned to $\mathcal{Y}$ by a
probability vector. In this case, the matching matrix $\mathbf{M}$ becomes a
soft probability matrix $\mathbf{P}$. In DCP (Wang and Solomon 2019a),
$\mathbf{P}$ is a single stochastic matrix, where $p_{ij}\in[0,1]$,
$\sum_{i=1}^{N_{\mathcal{X}}}p_{ij}=1,\forall j$. In RPMNet (Yew and Lee
2020), $\mathbf{P}$ is optimized to a partial doubly stochastic matrix
(notated as PDSM) by the Augmented-Sinkhorn algorithm, where $p_{ij}\in[0,1]$,
$\sum_{i=1}^{N_{\mathcal{X}}}p_{ij}\leq 1,\forall j$ and
$\sum_{j=1}^{N_{\mathcal{Y}}}p_{ij}\leq 1,\forall i$. Then, the virtual
corresponding points $\mathcal{Y}^{\prime}$ are obtained by performing
weighted average on $\mathcal{Y}$ using $\mathbf{P}$, _i.e_.
$\mathcal{Y}^{\prime}=\mathcal{Y}\mathbf{P}^{\mathrm{T}}$.

However, there is an ambiguity trap here. The geometric constraints and
underlying physics are ignored by relaxing the hard matching matrix to a soft
probability matrix, hence, the distribution of virtual corresponding points is
not unique resulting in serious degeneration. We can conclude as follows. The
theoretical proof and more analysis are provided in supplementary materials.

######  Theorem 1.

Considering the consistent subset point clouds $\mathbf{X}$, $\mathbf{Y}$ with
ground truth motion $\mathbf{R}$, $\mathbf{t}$, there exists more than one
soft matching matrix $\mathbf{P}$ satisfying
$\mathbf{Y}\mathbf{P}^{\mathrm{T}}=\mathbf{R}\mathbf{X}+\mathbf{t}$.

Since there will be an infinite number of virtual point cloud distributions
corresponding to the same rigid motion, this inherent ambiguity will cause
serious degeneration of virtual points as shown in Table 1. Essentially, the
process of weighted average can also be regarded as a special deformation of
the point cloud. Although a seemingly good transformation estimation is
obtained (Yew and Lee 2020), this process violates the rigid motion
assumption, which cannot be supported by the Procrustes algorithm (Gower
1975).

## Soft-to-Hard Matching for Registration

Figure 1: Illustration of the S2H matching procedure in registration pipeline.
Given the source and target point clouds, the similarity matrix is obtained
based on the point features. Then, S2H is applied for the final PPM. Finally,
the rigid motion is estimated by the weighted Procrustes.

In this paper, we devote to solving a PPM to handle the outliers and prevent
the ambiguity synchronously and thus design a meticulous S2H matching
procedure. In this section, to clearly present S2H and how to integrate it
into existing registration pipeline, we give a pipeline example as shown in
Fig. 1, which consists of three core modules: feature extractor and similarity
matrix solving, S2H matching, and rigid transformation estimation. Finally,
the proposed loss function is also presented herein.

#### Feature Extractor and Similarity Matrix Solving.

To achieve robust point matching, distinguished descriptors are crucial. With
the rise of deep learning technique, many standard modules for deep features
are proposed. These feature extractors can be easily integrated into our
robust point cloud registration pipelines according to different requirements.

We denote the point features of the source and target as
$\Phi_{\mathcal{X}}\in\mathbb{R}^{N_{\mathcal{X}}\times
c},\Phi_{\mathcal{Y}}\in\mathbb{R}^{N_{\mathcal{Y}}\times c}$. $c$ is the
feature dimension. Then, based on a certain similarity metric _e.g_. scale dot
product attention (Vaswani et al. 2017), the similarity matrix is returned as
$\mathbf{S}=[s_{ij}]_{N_{\mathcal{X}}\times N_{\mathcal{Y}}}$, where each
entry $s_{ij}$ represents the similarity between points
$\boldsymbol{x}_{i}\in\mathcal{X}$ and $\boldsymbol{y}_{i}\in\mathcal{Y}$.

#### S2H Matching.

A well-known solution to hard matching is to formulate it as a special
assignment problem, _i.e_. zero-one integer programming problem. However, two
natural but challenging problems exist for learning-based pipeline. 1)
Existing integer programming algorithms usually achieve a row or column full
rank permutation matrix
($\text{rank}(\mathbf{M})\\!=\\!\min(N_{\mathcal{X}},N_{\mathcal{Y}})$) rather
than a PPM. It means all points of the source or target will be assigned
corresponding points without distinguishing inliers and outliers. 2) PPM is
defined in the discrete space, which is non-differentiable. This
characteristic is fatal for the deep learning pipeline. To solve these
problems, we propose to augment the profit matrix to solve the PPM and design
an S2H matching procedure for end-to-end learning as follows.

$\bullet$ Augmenting the profit matrix to solve PPM: Conventionally, the
matching task is formulated as a zero-one integer programming problem taking
the similarity matrix $\mathbf{S}$ as the profit matrix, _i.e_.,

$\mathbf{M}^{*}=\arg\mathop{\max}\limits_{\mathbf{M}\in\mathcal{M}_{N}}{<\mathbf{M},\mathbf{S}>}_{F},$
(2)

where $\mathcal{M}_{N}$ denotes the set of partial permutation matrices.
${<\mathbf{M},\mathbf{S}>}_{F}=\mathrm{trace}({\mathbf{M}}^{\mathbf{T}}\mathbf{S})$
denotes the (Frobenius) inner product. Note that the traditional assignment
algorithm will achieve a full rank permutation solution. In response to
outliers, we propose to augment the profit matrix by adding additional rows
and columns to solve an augmented permutation matrix. Then the PPM will be
returned by cropping this augmented permutation matrix as shown in Fig. 1.
Thus, the following two questions should be addressed properly.

1\. How many rows and columns should be added? In the Augmented-Sinkhorn
algorithm (Yew and Lee 2020), which solves a soft matching matrix, one row and
one column are added as “trash bin”. However, for partial permutation
matching, the number of rows and columns augmented to the profit matrix is
more crucial since it implies the upper bound of the number of outliers
potentially. Thus, we propose to supplement the original
${N_{\mathcal{X}}\times N_{\mathcal{Y}}}$ profit matrix to a
$(N_{\mathcal{X}}+N_{\mathcal{Y}})\times(N_{\mathcal{X}}+N_{\mathcal{Y}})$
matrix, which is a maximum redundant operation replying to the case of all
points are outliers. Specifically, as shown in Fig. 1, left upper is the
original matrix, right upper block is a ${N_{\mathcal{X}}\times
N_{\mathcal{X}}}$ diagonal matrix and left bottom block is a
${N_{\mathcal{Y}}\times N_{\mathcal{Y}}}$ diagonal matrix, and right bottom
block is a ${N_{\mathcal{Y}}\times N_{\mathcal{X}}}$ zero matrix.

2\. What value to set? As aforesaid, the right upper block and the left bottom
block are two diagonal matrices, what values should be set to these diagonal
positions? Note that these values are roughly used as thresholds to
distinguish outliers and inliers potentially. Meanwhile, we observe that in
the profit matrix, if the row/column corresponds to an outlier, the entries in
this row/column approximate a uniform distribution with low value, which means
the outliers have no similar points in another point cloud. Otherwise, if the
row/column corresponds to the inlier, in this row/column, the entries are
close to a unimodal distribution, which means the inlier has only one similar
point in another point cloud ideally. Thus, we propose to self-adaptively fill
the diagonal position with $\sigma$ according to the corresponding row/column
of the input profit matrix:
$\sigma\\!=\\!{1}/\operatorname{var}(\boldsymbol{v})$, $\boldsymbol{v}$ is the
corresponding row/column vector, and $\text{var}(\cdot)$ is the variance
function. In this case, for outlier, the filled value is large, which enforces
the learned augmented permutation matrix to make the value of this position as
one to gain more profit. For inlier, the filled value is low, the value of
this position in the learned augmented permutation matrix is enforced to zero.

$\bullet$ S2H matching in end-to-end learning: Since $\mathbf{M}$ is defined
in the discrete space, and the integer programming algorithm is non-
differentiable, we design the S2H matching procedure to guarantee end-to-end
learning. Specifically, S-step learns a soft matrix and H-step projects this
soft matrix to discrete solution space for final PPM.

S-step: To deal with the outliers, we use Augmented-Sinkhorn (Yew and Lee
2020) to obtain a soft matrix by adding an additional row and column of ones
to the input matrix during the Sinkhorn normalization. In Augmented-Sinkhorn,
the additional row and column are regarded as “trash bin”, and the matching
weights of outliers are expected to “flow” to these additional row and column
to distinguish outliers and inliers. Specifically, given the obtained
similarity matrix $\textbf{S}\in\mathbb{R}^{N_{\mathcal{X}}\times
N_{\mathcal{Y}}}$, this soft matrix
$\textbf{P}\in\mathbb{R}^{N_{\mathcal{X}}\times N_{\mathcal{Y}}}$ is achieved
by cropping the output $(N_{\mathcal{X}}+1)\times(N_{\mathcal{Y}}+1)$ matrix
as shown in Fig. 1. P is a PDSM.

H-step: The resultant PDSM $\mathbf{P}$ is still a soft matrix, and we project
it to PPM by applying the proposed profit matrix augmenting strategy to
$\mathbf{P}$ and solving this zero-one integer programming problem. In our
implementation, we chose the classical Hungarian algorithm (Kuhn 1955) to
solve this assignment problem. After cropping the output augmented matrix, the
final PPM $\mathbf{M}\in\mathbb{R}^{N_{\mathcal{X}}\times N_{\mathcal{Y}}}$ is
obtained.

For a clearer understanding, we stress the ingeniousness of the proposed S2H
matching structure from two folds:

1\. End-to-end learning. We propose a deceptive operation as shown in the left
of Fig. 2 to guarantee end-to-end learning. During the forward propagation,
the loss is calculated based on the learned PPM $\mathbf{M}$. However, during
the backward propagation, the gradient is not propagated to the PPM, but
directly skipped to the learned PDSM $\mathbf{P}$ instead. This ingenious
structure guarantees the accuracy of the calculated loss and the backward
propagation simultaneously.

2\. Hard Matching vs. S2H Matching. To solve a PPM, we give a more
straightforward hard matching method in the right of Fig. 2, which can also
make sense by learning $\mathbf{M}$ considering the augmented similarity
matrix as the profit matrix. Nonetheless, there is an obvious local
supervision risk in this case. That is, the gradient will be propagated to the
input similarity matrix directly if only use the hard matching. And the
correlation of entries, which is considered in the integer programming
process, is ignored in backward propagation. In other words, the loss
calculated from $m_{ij}$ can only supervise $s_{ij}$. This will result in only
a few sparse points being supervised by the ground truth and the remaining
positions will be trained without supervision. For example, assuming
$m_{ij}=1$, the gradient will be propagated to $s_{ij}$ directly, and enforce
the feature extractor to enlarge $s_{ij}$. However, the positions where
$m_{ij}=0$ are not supervised (refer to loss function section for more
details). Hence, the corresponding point features will not suppress their
similarity. An extreme result is that all entries of the similarity matrix are
very large since the point features lose the distinctiveness and each point in
$\mathcal{X}$ is very similar to all points in $\mathcal{Y}$. This will result
in a divergence of training.

Our S2H solution effectively avoids the local supervision risk by propagating
the gradient to all entries in S-step, _i.e_. the correlation of all entries
is reconsidered. As shown in the left of Fig. 2, during the backward
propagation, the similarity of the correct correspondence will be boosted,
meanwhile the similarity of the incorrect correspondence will be effectively
suppressed.

Figure 2: Comparison of our S2H matching (Left) and hard matching (Right).
Yellow and red lines represent the forward and backward propagation
respectively.

#### Weighted Procrustes.

When we get a PPM $\mathbf{M}$, the corresponding point set of $\mathcal{X}$
could be achieved as
$\mathcal{Y}^{\prime}=\mathcal{Y}\mathbf{M}^{\mathrm{T}}$. However, the
corresponding points of outliers in $\mathcal{Y}^{\prime}$ are obtained as
$[0,0,0]^{\mathrm{T}}$, which should be filtered out when estimating the
transformation. To this end, the weighted Procrustes algorithm is used here.
Given $\mathcal{X}$, $\mathcal{Y}^{\prime}$, the weight vector
$\boldsymbol{w}$ is obtained as
$\boldsymbol{w}=\sum_{j=1}^{N_{\mathcal{Y}}}{m_{ij}}$, where
$\boldsymbol{w}\in\\{0,1\\}^{N_{\mathcal{X}}}$.

Then, $\boldsymbol{w}$ is normalized to $\boldsymbol{\bar{w}}$. Inspired by
DGR (Choy, Dong, and Koltun 2020), the rigid motion is computed as follows:
$\mathbf{H}=\mathcal{Y}^{\prime}\mathbf{KWK}\mathcal{X}^{\mathrm{T}}$, where
$\mathbf{W}=\mathrm{diag}(\boldsymbol{\bar{w}})$,
$\mathbf{K}=\mathbf{I}-\sqrt{\boldsymbol{\bar{w}}}{\sqrt{\boldsymbol{\bar{w}}}}^{\mathrm{T}}$.
$\mathbf{I}$ is an identity matrix. Then,
$\mathbf{R}=\mathbf{U}\mathbf{E}\mathbf{V}^{\mathrm{T}}$,
$\mathbf{t}=(\mathcal{Y}^{\prime}-\mathbf{R}\mathcal{X})\mathbf{W}\mathbf{1}$,
where $\mathbf{U}\mathbf{D}\mathbf{V}^{\mathrm{T}}=\text{SVD}(\mathbf{H})$,
$\mathbf{1}=(1,...,1)^{\mathrm{T}}$ and
$\mathbf{E}=\mathrm{diag}(1,...,1,\det{(\mathbf{U})}\det{(\mathbf{V})})$.

#### Loss function.

In this paper, we supervise the matching matrix directly, which is defined as:

$\mathcal{L}_{1}=-\frac{{\sum_{i=1}^{N_{\mathcal{X}}}\sum_{j=1}^{N_{\mathcal{Y}}}\left({{m}_{ij}^{\text{pred}}{m}_{ij}^{\text{gt}}}\right)}}{{\sum_{i=1}^{N_{\mathcal{X}}}\sum_{j=1}^{N_{\mathcal{Y}}}\left({{m}_{ij}^{\text{gt}}}\right)}},$
(3)

where the superscript “pred” and “gt” represent the prediction and ground
truth respectively. It is noteworthy that when $m_{ij}^{\text{gt}}=1$,
$m_{ij}^{\text{pred}}$ is enforced to 1. But when $m_{ij}^{\text{gt}}=0$,
$m_{ij}^{\text{pred}}$ diverges without supervision. Moreover, due to the
introduction of augmentation operation, all points tend to be labeled as
outliers, which makes the learned PPM close to a full zero matrix. To avoid
this degeneracy, we encourage the number of inliers by:

$\mathcal{L}_{2}=-\frac{\sum_{i=1}^{N_{\mathcal{X}}}\sum_{j=1}^{N_{\mathcal{Y}}}(m_{ij}^{\text{pred}})}{N_{\mathcal{X}}+N_{\mathcal{Y}}}.$
(4)

Besides, we also supervise the final rigid motion, _i.e_.,

$\mathcal{L}_{3}=\|{\mathbf{R}^{\text{gt}}}^{\mathrm{T}}\mathbf{R}^{\text{pred}}-\mathbf{I}_{3}\|_{2}+\|\mathbf{t}^{\text{gt}}-\mathbf{t}^{\text{pred}}\|_{2},$
(5)

where $\mathbf{I}_{3}$ is a $3\times 3$ identity matrix. Then, our final loss
function is reached as
$\mathcal{L}=\lambda_{1}\mathcal{L}_{1}+\lambda_{2}\mathcal{L}_{2}+\lambda_{3}\mathcal{L}_{3}$,
the trade-off parameters are set to $\lambda_{1}=\lambda_{2}=\lambda_{3}=1$ in
this paper.

## Experiments and Evaluation

In this section, we evaluate the proposed S2H matching procedure in several
representative point cloud registration frameworks including DCP, RPMNet and
DGR, on benchmark datasets including ModelNet40 (Wu et al. 2015), 3DMatch
(Zeng et al. 2017) and KITTI (Geiger et al. 2013).

Implementation details. To validate the proposed matching method can be
generally integrated, we evaluate S2H matching within three typical
frameworks, _i.e_. DCP, RPMNet, and DGR, notated as $\text{SHM}_{\text{DCP}}$,
$\text{SHM}_{\text{RPMNet}}$, and $\text{SHM}_{\text{DGR}}$ respectively.
These three frameworks are typical and representative, where DCP and RPMNet
are soft matching-based methods using different feature extractors, and mainly
concentrate on the synthetic dataset, ModelNet40. DGR is a hard matching-based
method focusing on large-scale real datasets, 3DMatch and KITTI. Note that
PRNet (Wang and Solomon 2019b) also inherits the framework of DCP, which is
compared with $\text{SHM}_{\text{DCP}}$ herein. The complete loss is used in
$\text{SHM}_{\text{DCP}}$, $\text{SHM}_{\text{RPMNet}}$. Only
$\mathcal{L}_{3}$ is used in $\text{SHM}_{\text{DGR}}$. Refer to supplementary
materials for more details.

### Evaluation on synthetic dataset: ModelNet40

In this section, we validate our proposed S2H matching procedure with
$\text{SHM}_{\text{DCP}}$, $\text{SHM}_{\text{RPMNet}}$ on a synthetic
dataset, ModelNet40. Following DCP and RPNet, we construct a point cloud by
randomly sampling 1024 points, and then apply a rigid transformation to this
point cloud, where the rotation and translation are uniformly sampled from
$[0^{\circ},45^{\circ}]$ and $[-0.5,0.5]^{3}$ respectively along each axis.
Next, we randomly sample 768 points from the original point cloud and the
transformed point cloud as the source and target to ensure the random
distribution of the outliers.

In addition, following DCP and RPMNet, we test ours on two different dataset
settings. 1) Unseen categories (clean): ModelNet40 will be divided into
training and test splits based on the object category, _i.e_. the first 20
categories are selected for training and the rest categories for testing. 2)
Noisy data (noisy): For robustness testing, random Gaussian noise (_i.e_.,
$\mathcal{N}(0,0.01)$) is added to each point, while the sampled noise out of
the range of $[-0.05,0.05]$ will be clipped. The dataset splitting strategy is
the same as clean.

Matching. Accurate correspondences estimation is crucial for robust point
cloud registration. Here, we evaluate the constructed correspondences for a
clear comparison.

$\bullet$ Metric: We calculate the discrepancy between the predicted and the
ground truth corresponding points. The predicted corresponding points
$\mathcal{Y}_{\text{pred}}^{\prime}$ of $\mathcal{X}$ can be obtained by two
methods. First, based on the predicted matching matrix
$\mathbf{M}^{\text{pred}}$, $\mathcal{Y}_{\text{pred}}^{\prime}$ can be
obtained by
$\mathcal{Y}_{\text{pred}}^{\prime}={\mathcal{Y}\mathbf{M}^{\text{pred}\mathrm{T}}}$.
Second, inspired by the iteration strategy in ICP,
$\mathcal{Y}_{\text{pred}}^{\prime}$ can be obtained based on the predicted
transformation $\\{\mathbf{R}^{\text{pred}},\mathbf{t}^{\text{pred}}\\}$ and
nearest neighbor principle, _i.e_.
$\mathcal{Y}_{\text{pred}}^{\prime}=\text{NN}_{\mathcal{Y}}(\mathbf{R}^{\text{pred}}\mathcal{X}+\mathbf{t}^{\text{pred}})$,
where $\text{NN}_{\mathcal{Y}}(\cdot)$ solves the nearest neighbor point in
$\mathcal{Y}$. Given the ground truth corresponding points
$\mathcal{Y}_{\text{gt}}^{\prime}$, the root mean squared error (RMSE) and
mean absolute error (MAE) in Euclidean distance between
$\mathcal{Y}_{\text{pred}}^{\prime}$ and $\mathcal{Y}_{\text{gt}}^{\prime}$,
notated as RMSE(dis) and MAE(dis) are presented.

We also report the matching recall $(\%)$ based on a proposed self-adaptive
threshold,
${\tau_{i}}=({1}/{K}){\sum_{j=1}^{K}{{d_{\boldsymbol{y}_{\pi(i)}^{\prime},\boldsymbol{y}_{j}}}}}$,
where $\boldsymbol{y}_{\pi(i)}^{\prime}$ is the correct corresponding point of
$\boldsymbol{x}_{i}$,
$\boldsymbol{y}_{j}\in\text{KNN}_{\mathcal{Y}}(\boldsymbol{y}_{\pi(i)}^{\prime})$,
$\text{KNN}_{\mathcal{Y}}(\cdot)$ solves the K-nearest neighbor points
(exclude the self-point) in $\mathcal{Y}$ with pre-defined parameter $K$,
${d_{\boldsymbol{y}_{\pi(i)}^{\prime},\boldsymbol{y}_{j}}}$ is the distance
between $\boldsymbol{y}_{\pi(i)}^{\prime}$ and $\boldsymbol{y}_{j}$. To sum
up, for the $i$-th point, $\tau_{i}$ is computed as the average distance of
K-nearest points around the correct corresponding point in $\mathcal{Y}$. If
the distance between the correct corresponding point and the predicted one is
less than the threshold, this pair will be confirmed as a correct matching
pair.

Methods |  $\mathbf{RMSE(dis)}$ $\downarrow$ |  $\mathbf{MAE(dis)}$ $\downarrow$ |  $\mathbf{RMSE(dis)}$ $\downarrow$ |  $\mathbf{MAE(dis)}$ $\downarrow$
---|---|---|---|---
clean | noisy | clean | noisy | clean | noisy | clean | noisy
DCP-v2 | 0.500 | 0.466 | 0.705 | 0.657 | 0.088 | 0.095 | 0.078 | 0.095
PRNet | 0.311 | 0.303 | 0.357 | 0.351 | 0.046 | 0.057 | 0.023 | 0.036
$\text{SHM}_{\text{DCP}}$ | 0.106 | 0.188 | 0.027 | 0.082 | 0.033 | 0.053 | 0.008 | 0.019
RPMNet | 0.139 | 0.137 | 0.182 | 0.181 | 0.019 | 0.028 | 0.004 | 0.013
$\text{SHM}_{\text{RPMNet}}$ | 0.057 | 0.121 | 0.009 | 0.041 | 0.007 | 0.027 | 0.001 | 0.010

Table 2: Discrepancy based on predicted matching matrix (Left) and predicted
transformation, nearest neighbor principle (Right).

$\bullet$ Evaluation: In Table 2, we report RMSE(dis) and MAE(dis) results in
clean and noisy. For the discrepancy based on the predicted matching matrix,
our method improves the performance with a big margin in both DCP and RPMNet
frameworks. These obtained results are reasonable because the DCP-v2, RPMNet
are virtual point-based methods, where the corresponding points degenerate
seriously with a large distance to correct corresponding points. PRNet
presents weaker matching performance due to the one-to-many matching. For the
discrepancy based on the predicted transformation and nearest neighbor
principle, all methods achieve superior performance, whereas
$\text{SHM}_{\text{DCP}}$, $\text{SHM}_{\text{RPMNet}}$ remain the overall
best performance.

Besides, we also draw the matching recall with different thresholds in Fig. 3.
For the results based on the predicted matching matrix, the DCP-v2, RPMNet
fail to obtain accurate correspondences. And ours obtains the best results.
For the results based on the predicted transformation and nearest neighbor
principle, all methods achieve better performance, and
$\text{SHM}_{\text{DCP}}$, $\text{SHM}_{\text{RPMNet}}$ remain the best
performance.

Figure 3: Matching recall with different thresholds based on the predicted
matching matrix ((a-1), (a-2)) and the predicted transformation, nearest
neighbor principle ((b-1), (b-2)). (a-1), (b-1) are conducted in clean and
(a-2), (b-2) in noisy. The X-axis is the number of K-nearest points for
threshold, and $K=0$ means $\tau_{i}=0$.

Registration. In this section, we evaluate the rigid motion estimation
performance of $\text{SHM}_{\text{DCP}}$, $\text{SHM}_{\text{RPMNet}}$.

$\bullet$ Metric: Following DCP, RMSE and MAE between the ground truth and
prediction in Euler angle and translation vector are used as the evaluation
metrics here, notated as RMSE(R), MAE(R), RMSE(t) and MAE(t) respectively.

$\bullet$ Evaluation: The evaluation results are provided in Table 3. Both
$\text{SHM}_{\text{DCP}}$ and $\text{SHM}_{\text{RPMNet}}$ outperform the
hand-craft registration methods, ICP (Besl and McKay 1992), FGR (Zhou, Park,
and Koltun 2016). Furthermore, in clean, $\text{SHM}_{\text{DCP}}$ achieves
more accurate performance than DCP-v2 and PRNet in all metrics,
$\text{SHM}_{\text{RPMNet}}$ is more accurate than RPMNet in all metrics. In
noisy, we train and test ours and all baselines with noisy data. And the
methods with our S2H matching also achieves the best performance in these two
frameworks in all evaluation metrics. These evaluations validate the
improvement of our S2H matching, which creates a new state-of-the-art results.
More intuitively, we provide some qualitative registration performance in Fig.
4.

Methods |  $\mathbf{RMSE(R)}$ $\downarrow$ |  $\mathbf{MAE(R)}$ $\downarrow$ |  $\mathbf{RMSE(t)}$ $\downarrow$ |  $\mathbf{MAE(t)}$ $\downarrow$
---|---|---|---|---
clean | noisy | clean | noisy | clean | noisy | clean | noisy
ICP | 12.545 | 12.723 | 5.438 | 5.298 | 0.046 | 0.045 | 0.024 | 0.023
FGR | 20.042 | 40.829 | 7.203 | 21.065 | 0.035 | 0.060 | 0.019 | 0.039
DCP-v2 | 6.265 | 6.347 | 3.990 | 4.294 | 0.014 | 0.016 | 0.011 | 0.012
PRNet | 3.532 | 4.321 | 1.760 | 1.826 | 0.013 | 0.013 | 0.010 | 0.010
$\text{SHM}_{\text{DCP}}$ |  2.522 +28.60% |  3.886 +10.07% |  0.833 +52.67% |  1.510 +17.31% |  0.005 +61.54% |  0.006 +53.85% |  0.003 +70.00% |  0.004 +60.00%
RPMNet | 0.886 | 1.631 | 0.345 | 0.565 | 0.006 | 0.011 | 0.003 | 0.004
$\text{SHM}_{\text{RPMNet}}$ |  0.514 +41.99% |  1.456 +10.73% |  0.247 +28.41% |  0.378 +33.10% |  0.004 +33.33% |  0.008 +27.27% |  0.002 +33.33% |  0.003 +25.00%

Table 3: Registration perfomance on clean, noisy. Green notes the improvement
comparing with the second-top results.

Figure 4: For each pair of point clouds, left upper is the transformed source
using the predicted rigid motion and right bottom is the target. For a more
clear presentation of the outliers, we only sample the target of the input
pair, _i.e_. $N_{\mathcal{X}}=1024$, $N_{\mathcal{Y}}=768$. The same color
represents the correspondences, and black indicates the abandoned points. Ours
achieves advanced correspondences building and robust registration results in
such challenging cases.

$\bullet$ Time-efficiency: We counted the average inference time of learning-
based methods in Table 4. The experiments are conducted in noisy on ModelNet40
using a Xeon E5-2640<EMAIL_ADDRESS>CPU and a GTX 1080Ti. S2H matching-based
methods are slower because the integer programming algorithm is time-
consuming. $\text{SHM}_{\text{RPMNet}}$ is slower than
$\text{SHM}_{\text{DCP}}$ due to the iteration in RPMNet framework.

Methods | DCP | PRNet | $\text{SHM}_{\text{DCP}}$ | RPMNet | $\text{SHM}_{\text{RPMNet}}$
---|---|---|---|---|---
Time(ms) | 10.66 | 45.48 | 98.03 | 54.75 | 409.95

Table 4: Inference time comparison of learning-based methods.

### Evaluation on real indoor data: 3DMatch

In this part, we evaluate our S2H matching in $\text{SHM}_{\text{DGR}}$ on
real indoor dataset, 3DMatch (Zeng et al. 2017). $\text{SHM}_{\text{DGR}}$
takes the S2H matching replacing the original matching of DGR (Choy, Dong, and
Koltun 2020) (more details can be seen in supplementary materials). Following
DGR, the input point clouds have been voxelized with the voxel size of 5cm,
then each of them contains $\sim$50k points.

$\bullet$ Metric: For a fair comparison, we follow the protocols and
evaluation metrics of DGR here. The average Rotation Error (RE:
$\text{arccos}(({trace({\mathbf{R}^{\text{pred}}}^{-1}\mathbf{R}^{\text{gt}})-1)/2})\frac{180}{\pi}$),
average Translation Error (TE:
$\|\mathbf{t}^{\text{pred}}-\mathbf{t}^{\text{gt}}\|_{2}^{2}$), recall, and
time-efficiency are reported. Recall indicates the ratio of successful
pairwise registrations. Here, the successful pair is confirmed if the RE and
TE are smaller than pre-defined thresholds (_i.e_., RE$<$$15^{\circ}$,
TE$<$$30cm$).

Methods |  TE(cm) $\downarrow$ |  RE(deg) $\downarrow$ |  Recall(%) $\uparrow$ |  Time(s) $\downarrow$
---|---|---|---|---
ICP | 18.1 | 8.25 | 6.04 | 0.25
FGR | 10.6 | 4.08 | 42.7 | 0.31
Go-ICP | 14.7 | 5.38 | 22.9 | 771.0
Super4PCS | 14.1 | 5.25 | 21.6 | 4.55
RANSAC | 9.16 | 2.95 | 70.7 | 2.32
DCP-v2 | 21.4 | 8.42 | 3.22 | 0.07
PointNetLK | 21.3 | 8.04 | 1.61 | 0.12
DGR w/o safeguard | 7.73 | 2.58 | 85.2 | 0.70
DGR | 7.34 | 2.43 | 91.3 | 1.21
PointDSC | 6.55 | 2.06 | 93.28 | 0.09
$\text{SHM}_{\text{DGR}}$ | 6.41 | 1.75 | 91.7 | 37.2

Table 5: Evaluation on 3DMatch dataset.

$\bullet$ Evaluation: From the Table 5, we find that ICP achieves the weak
registration result since the dataset contains challenging sequences with
large motion while no reliable prior is provided. Super4PCS (Mellado, Aiger,
and Mitra 2014), and Go-ICP (Yang et al. 2015), which are sampling-based
algorithm and the variant of ICP with branch-and-bound search respectively,
present similar performance here. FGR and RANSAC perform better due to the
extracted point features. 3DRegNet (Pais et al. 2020) is also tested here,
however, it does not converge, which outputs the error above 30∘ and 1m. DGR
is the state-of-the-art learning-based method, which is designed for scene
data specifically. However, DGR also takes the most similar points as the
corresponding points ignoring the one-to-one matching principle.
$\text{SHM}_{\text{DGR}}$ achieves better registration performance including
transformation estimation and recall comparing with the original DGR. PointDSC
(Bai et al. 2021) achieves the best recall but the registration performance is
weaker than $\text{SHM}_{\text{DGR}}$.

### Evaluation on real outdoor data: KITTI

We evaluate $\text{SHM}_{\text{DGR}}$ on the real outdoor data, KITTI (Geiger
et al. 2013). Here, we also follow the protocols of DGR, where the evaluation
metrics are identical to the 3DMatch evaluation. The thresholds to confirm the
successful pair are set to 0.6m and 5∘. From Table 6, the
$\text{SHM}_{\text{DGR}}$ achieves the best performance with respect to rigid
transformation estimation and recall, which outperforms the original DGR and
the state-of-the-art method, PointDSC.

Methods |  TE(cm) $\downarrow$ |  RE(deg) $\downarrow$ |  Recall(%)$\uparrow$ | Time(s) $\downarrow$
---|---|---|---|---
FGR | 40.7 | 1.02 | 0.2 | 1.42
RANSAC | 25.9 | 1.39 | 34.2 | 1.37
FCGF | 10.2 | 0.33 | 98.2 | 6.38
DGR | 21.7 | 0.34 | 96.9 | 2.29
PointDSC | 20.94 | 0.33 | 98.20 | 0.31
$\text{SHM}_{\text{DGR}}$ | 9.32 | 0.28 | 99.3 | 52.4

Table 6: Evaluation on KITTI dataset.

### Ablation studies

End-to-end vs. post-processing. In this paper, we advocate learning the one-
to-one matching in an end-to-end manner, _i.e_. achieving the PPM in the
matching stage. Oppositely, another natural idea is to solve the PPM in post-
processing, _i.e_. using only the S-step to learn the soft matrix during the
training and adding the H-step during the test for the final hard matrix, PPM.
The comparison of these two ideas is given in Table 7, where the experiments
are conducted on ModelNet40. We can see that the end-to-end learning achieves
better results in all metrics because more accurate loss are calculated in
this pipeline.

Methods |  $\mathbf{RMSE(R)}$ $\downarrow$ |  $\mathbf{MAE(R)}$ $\downarrow$ |  $\mathbf{RMSE(t)}(\times 10^{-3})$ $\downarrow$ |  $\mathbf{MAE(t)}(\times 10^{-3})$ $\downarrow$
---|---|---|---|---
clean | noisy | clean | noisy | clean | noisy | clean | noisy
$\text{SHM}_{\text{DCP}}^{-}$ | 3.325 | 4.570 | 1.039 | 1.683 | 5.056 | 6.624 | 3.204 | 4.316
$\text{SHM}_{\text{DCP}}^{+}$ |  2.522 +24.15% |  3.886 +14.97% |  0.833 +19.83% |  1.510 +10.28% |  4.780 +5.46% |  5.758 +13.07% |  3.052 +4.74% |  3.774 +12.56%
$\text{SHM}_{\text{RPMNet}}^{-}$ | 0.760 | 1.537 | 0.270 | 0.449 | 4.927 | 10.120 | 2.356 | 3.602
$\text{SHM}_{\text{RPMNet}}^{-}$ |  0.514 +32.37% |  1.456 +5.27% |  0.247 +8.52% |  0.378 +15.81% |  3.883 +21.19% |  8.421 +16.79% |  2.328 +1.19% |  3.145 +12.69%

Table 7: Comparison between the end-to-end learning and post-processing
setting. “-” indicates the post-processing, and “+” indicates the end-to-end
learning.

Other important ablation studies. Due to the limitation of space, we provide
some other import experiments in supplementary materials, including the
robustness to different outliers generation strategy, the robustness to
different outliers ratio, the influence of different loss function
combinations, and more qualitative results of registration, _etc_.

## Conclusion

In this paper, we tackle the point matching problem in robust 3D point cloud
registration. First, we analyze the inherent ambiguity in soft matching-based
methods. Second, to resolve the ambiguity and handle the outliers in the
matching stage, we propose to learn the partial permutation matching (PPM)
matrix. To address the consequent problem that PPM is defined in non-
differentiable space and cannot be solved by existing hard assignment
algorithms, we design a soft-to-hard matching method. We have validated the
effectiveness by integrating it with various registration frameworks including
DCP, RPMNet, and DGR and conducting extensive experiments in both synthetic
data (ModelNet40) and real scan data (3DMatch and KITTI), which created a new
state-of-the-art performance for robust 3D point cloud registration. In the
future, we plan to extend our framework to non-rigid point cloud registration.

## Acknowledgments

This research was supported in part by National Key Research and Development
Program of China (2018AAA0102803) and National Natural Science Foundation of
China (61871325, 62001394, 61901387). Besides, this work was also sponsored by
Innovation Foundation for Doctor Dissertation of Northwestern Polytechnical
University.

## References

  * Aoki et al. (2019) Aoki, Y.; Goforth, H.; Srivatsan, R. A.; and Lucey, S. 2019.  PointNetLK: Robust & efficient point cloud registration using PointNet.  In _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition_ , 7163–7172.
  * Bai et al. (2021) Bai, X.; Luo, Z.; Zhou, L.; Chen, H.; Li, L.; Hu, Z.; Fu, H.; and Tai, C.-L. 2021\.  PointDSC: Robust Point Cloud Registration Using Deep Spatial Consistency.  In _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition_ , 15859–15869.
  * Bai et al. (2020) Bai, X.; Luo, Z.; Zhou, L.; Fu, H.; Quan, L.; and Tai, C.-L. 2020.  D3Feat: Joint Learning of Dense Detection and Description of 3D Local Features.  In _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_ , 6358–6366.
  * Besl and McKay (1992) Besl, P. J.; and McKay, N. D. 1992.  A method for registration of 3-D shapes.  _IEEE Transactions on Pattern Analysis and Machine Intelligence_ , 14(2): 239–256.
  * Choy, Dong, and Koltun (2020) Choy, C.; Dong, W.; and Koltun, V. 2020.  Deep Global Registration.  In _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition_ , 2511–2520.
  * Choy, Park, and Koltun (2019) Choy, C.; Park, J.; and Koltun, V. 2019.  Fully Convolutional Geometric Features.  In _Proceedings of the IEEE International Conference on Computer Vision_ , 8958–8966.
  * Deng, Birdal, and Ilic (2018a) Deng, H.; Birdal, T.; and Ilic, S. 2018a.  PPF-FoldNet: Unsupervised Learning of Rotation Invariant 3D Local Descriptors.  In _Proceedings of the European Conference on Computer Vision (ECCV)_ , 620–638. Springer.
  * Deng, Birdal, and Ilic (2018b) Deng, H.; Birdal, T.; and Ilic, S. 2018b.  PPFNet: Global Context Aware Local Features for Robust 3D Point Matching.  In _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_ , 195–205.
  * Deschaud (2018) Deschaud, J.-E. 2018.  IMLS-SLAM: scan-to-model matching based on 3D data.  In _Proceedings of the International Conference on Robotics and Automation_ , 2480–2485.
  * Ding and Feng (2019) Ding, L.; and Feng, C. 2019.  DeepMapping: Unsupervised map estimation from multiple point clouds.  In _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition_ , 8650–8659.
  * Geiger et al. (2013) Geiger, A.; Lenz, P.; Stiller, C.; and Urtasun, R. 2013.  Vision meets robotics: The kitti dataset.  _The International Journal of Robotics Research_ , 32(11): 1231–1237.
  * Gojcic et al. (2019) Gojcic, Z.; Zhou, C.; Wegner, J. D.; and Wieser, A. 2019.  The Perfect Match: 3D Point Cloud Matching With Smoothed Densities.  In _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition_ , 5545–5554.
  * Gower (1975) Gower, J. C. 1975.  Generalized procrustes analysis.  _Psychometrika._ , 40(1): 33–51.
  * Huang et al. (2021) Huang, S.; Gojcic, Z.; Usvyatsov, M.; Wieser, A.; and Schindler, K. 2021.  Predator: Registration of 3D Point Clouds With Low Overlap.  In _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_ , 4267–4276.
  * Huang, Mei, and Zhang (2020) Huang, X.; Mei, G.; and Zhang, J. 2020.  Feature-metric Registration: A Fast Semi-supervised Approach for Robust Point Cloud Registration without Correspondences.  In _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition_ , 11363–11371.
  * Kuhn (1955) Kuhn, H. W. 1955.  The Hungarian method for the assignment problem.  _Naval research logistics quarterly_ , 2(1-2): 83–97.
  * Lu et al. (2019) Lu, W.; Wan, G.; Zhou, Y.; Fu, X.; Yuan, P.; and Song, S. 2019.  DeepVCP: An End-to-End Deep Neural Network for Point Cloud Registration.  In _Proceedings of the IEEE International Conference on Computer Vision_ , 12–21.
  * Mellado, Aiger, and Mitra (2014) Mellado, N.; Aiger, D.; and Mitra, N. J. 2014.  Super 4PCS Fast Global Pointcloud Registration via Smart Indexing.  _Computer Graphics Forum_ , 33(5): 205–215.
  * Pais et al. (2020) Pais, G. D.; Ramalingam, S.; Govindu, V. M.; Nascimento, J. C.; Chellappa, R.; and Miraldo, P. 2020.  3DRegNet: A Deep Neural Network for 3D Point Registration.  In _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition_ , 7191–7201.
  * Pomerleau, rancis Colas, and Siegwart (2015) Pomerleau, F.; rancis Colas; and Siegwart, R. 2015.  A Review of Point Cloud Registration Algorithms for Mobile Robotics.  _Foundations and Trends in Robotics_ , 4(1): 1–104.
  * Probst et al. (2019) Probst, T.; Paudel, D. P.; Chhatkuli, A.; and Gool, L. V. 2019.  Unsupervised learning of consensus maximization for 3d vision problems.  In _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition_ , 929–938.
  * Qi et al. (2017a) Qi, C. R.; Su, H.; Mo, K.; and Guibas, L. J. 2017a.  Pointnet: Deep learning on point sets for 3d classification and segmentation.  In _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition_ , 652–660.
  * Qi et al. (2017b) Qi, C. R.; Yi, L.; Su, H.; and Guibas, L. J. 2017b.  Pointnet++: Deep hierarchical feature learning on point sets in a metric space.  In _Proceedings of the Advances in Neural Information Processing Systems_ , 5099–5108.
  * Rusinkiewicz and Levoy (2001) Rusinkiewicz, S.; and Levoy, M. 2001.  Efficient variants of the ICP algorithm.  In _Proceedings of the IEEE International Conference on 3D Digital Imaging and Modeling_ , 145–152.
  * Sarlin et al. (2020) Sarlin, P.; DeTone, D.; Malisiewicz, T.; and Rabinovich, A. 2020.  SuperGlue: Learning Feature Matching With Graph Neural Networks.  In _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition_ , 4937–4946.
  * Shiratori et al. (2015) Shiratori, T.; Berclaz, J.; Harville, M.; Shah, C.; Li, T.; Matsushita, Y.; and Shiller, S. 2015.  Efficient large-scale point cloud registration using loop closures.  In _Proceedings of the International Conference on 3D Vision_ , 232–240.
  * Thomas et al. (2019) Thomas, H.; Qi, C. R.; Deschaud, J.; Marcotegui, B.; Goulette, F.; and Guibas, L. J. 2019.  KPConv: Flexible and Deformable Convolution for Point Clouds.  In _ICCV_ , 6410–6419.
  * Vaswani et al. (2017) Vaswani, A.; Shazeer, N.; Parmar, N.; Uszkoreit, J.; Jones, L.; Gomez, A. N.; Kaiser, Ł.; and Polosukhin, I. 2017.  Attention is all you need.  In _Proceedings of the Advances in Neural Information Processing Systems_ , 5998–6008.
  * Wang and Solomon (2019a) Wang, Y.; and Solomon, J. M. 2019a.  Deep closest point: Learning representations for point cloud registration.  In _Proceedings of the IEEE International Conference on Computer Vision_ , 3523–3532.
  * Wang and Solomon (2019b) Wang, Y.; and Solomon, J. M. 2019b.  PRNet: Self-supervised learning for partial-to-partial registration.  In _Proceedings of the Advances in Neural Information Processing Systems_ , 8814–8826.
  * Wang et al. (2019) Wang, Y.; Sun, Y.; Liu, Z.; Sarma, S. E.; Bronstein, M. M.; and Solomon, J. M. 2019\.  Dynamic graph cnn for learning on point clouds.  _ACM Transactions on Graphics_ , 38(5): 1–12.
  * Wong et al. (2017) Wong, J. M.; Kee, V.; Le, T.; Wagner, S.; Mariottini, G. L.; Schneider, A.; Hamilton, L.; Chipalkatty, R.; Hebert, M.; Johnson, D. M. S.; Wu, J.; Zhou, B.; and Torralba, A. 2017.  SegICP: Integrated deep semantic segmentation and pose estimation.  In _Proceedings of the International Conference on Intelligent Robots and Systems_ , 5784–5789.
  * Wu et al. (2015) Wu, Z.; Song, S.; Khosla, A.; Yu, F.; Zhang, L.; Tang, X.; and Xiao, J. 2015.  3d shapenets: A deep representation for volumetric shapes.  In _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition_ , 1912–1920.
  * Yang et al. (2015) Yang, J.; Li, H.; Campbell, D.; and Jia, Y. 2015.  Go-ICP: A globally optimal solution to 3D ICP point-set registration.  _IEEE Transactions on Pattern Analysis and Machine Intelligence_ , 38(11): 2241–2254.
  * Yew and Lee (2018) Yew, Z. J.; and Lee, G. H. 2018.  3DFeat-Net: Weakly supervised local 3D features for point cloud registration.  In _Proceedings of the European Conference on Computer Vision_ , 630–646.
  * Yew and Lee (2020) Yew, Z. J.; and Lee, G. H. 2020.  RPM-Net: Robust Point Matching Using Learned Features.  In _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition_ , 11821–11830.
  * Zeng et al. (2017) Zeng, A.; Song, S.; Nießner, M.; Fisher, M.; Xiao, J.; and Funkhouser, T. A. 2017.  3DMatch: Learning Local Geometric Descriptors from RGB-D Reconstructions.  In _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition_ , 199–208.
  * Zeng et al. (2021) Zeng, Y.; Qian, Y.; Zhu, Z.; Hou, J.; Yuan, H.; and He, Y. 2021.  CorrNet3D: Unsupervised End-to-end Learning of Dense Correspondence for 3D Point Clouds.  In _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition_ , 6052–6061.
  * Zhang, Dai, and Sun (2020) Zhang, Z.; Dai, Y.; and Sun, J. 2020.  Deep learning based point cloud registration: an overview.  _Virtual Reality and Intelligent Hardware._ , 2(3): 222–246.
  * Zhao et al. (2020) Zhao, Y.; Birdal, T.; Lenssen, J. E.; Menegatti, E.; Guibas, L. J.; and Tombari, F. 2020.  Quaternion Equivariant Capsule Networks for 3D Point Clouds.  In _Proceedings of the European Conference on Computer Vision_ , 1–19.
  * Zhou, Park, and Koltun (2016) Zhou, Q.-Y.; Park, J.; and Koltun, V. 2016.  Fast global registration.  In _Proceedings of the European Conference on Computer Vision_ , 766–782.