# Embedded nonlinear model predictive control for obstacle avoidance using
PANOC

Ajay Sathya, Pantelis Sopasakis, Ruben Van Parys, Andreas Themelis, Goele
Pipeleers and Panagiotis Patrinos 1A. Sathya, R. Van Parys and G. Pipeleers
are with the Dept. of Mechanical Engineering, meco research group, KU Leuven,
3001 Leuven, Belgium.2P. Sopasakis, A. Themelis and P. Patrinos are with the
Dept. of Electrical Engineering (esat-stadius), KU Leuven, 3001 Leuven,
Belgium.The work of the these authors was supported by the Research Foundation
Flanders (FWO) PhD fellowship 1196818N; FWO research projects G086518N and
G086318N; KU Leuven internal funding StG/15/043; Fonds de la Recherche
Scientifique – FNRS and the Fonds Wetenschappelijk Onderzoek – Vlaanderen
under EOS Project no 30468160 (SeLMA). R. Van Parys is a PhD fellow of the
Research Foundation Flanders (FWO-Flanders).

###### Abstract

We employ the proximal averaged Newton-type method for optimal control (PANOC)
to solve obstacle avoidance problems in real time. We introduce a novel
modeling framework for obstacle avoidance which allows us to easily account
for generic, possibly nonconvex, obstacles involving polytopes, ellipsoids,
semialgebraic sets and generic sets described by a set of nonlinear
inequalities. PANOC is particularly well-suited for embedded applications as
it involves simple steps, its implementation comes with a low memory footprint
and its fast convergence meets the tight runtime requirements of fast
dynamical systems one encounters in modern mechatronics and robotics. The
proposed obstacle avoidance scheme is tested on a lab-scale autonomous
vehicle.

###### Index Terms:

Embedded optimization, Nonlinear model predictive control, Obstacle avoidance.

##  I Introduction

###  I-A Background and Contributions

Autonomous navigation in obstructed environments is a key element in emerging
applications such as driverless cars, fleets of automated vehicles in
warehouses and aerial robots performing search-and-rescue expeditions. Well-
known approaches for finding collision-free motion trajectories are graph-
search methods [1], virtual potential field methods [2] or methods using the
concept of velocity obstacles [3].

Recent motion planning research focuses on optimization-based strategies.
Here, an optimal motion trajectory is sought while collision-avoidance
requirements are imposed as constraints thereon. There is a broad range of
such formulations. The most straightforward approach constrains the Euclidean
distance between the vehicle and obstacle centers [4]. This, however, only
allows to separate spheres and ellipsoids as the computation of distances from
arbitrary sets is generally not an easy operation.

Other approaches demand the existence of a hyperplane between the vehicle and
obstacle at each time instant [5, 6]. This allows the separation of general
convex sets. Some methods formulate the collision avoidance requirement by
mixed-integer constraints [7]. These types of problems are, however,
cumbersome to solve in real-time. For some specific problem types it is
possible to transform the system dynamics such that collision-avoidance
translates into simple box constraints on the states [8, 9].

Model predictive control (MPC) is a powerful control strategy where control
actions are computed by optimizing a cost function which is chosen in order to
achieve a control task. Constraints on states, inputs and outputs can be
seamlessly incorporated into such a framework. When the system dynamics is
linear, the constraints are affine and the cost functions are quadratic, the
associated optimization problem is a quadratic program. There exists a mature
machinery of convex optimization algorithms [10, 11] which are fast, robust
and possess global convergence guarantees which can be used to solve these
problems.

Nevertheless, the dynamics of most systems of interest are better modeled by
nonlinear equations and constraints are often nonconvex. This situation is
very common in obstacle avoidance involving nonconvex optimization problems.
These are commonly solved using sequential quadratic programming (SQP) [10]
and interior point (IP) methods [12] which are not well-suited for embedded
applications with tight runtime requirements. Nonlinear MPC is often performed
using the real-time iteration scheme proposed in [13] which trades speed for
accuracy and is accompanied by global convergence guarantees under certain
assumptions.

For an algorithm to be suitable for an embedded implementation, it needs to
involve only simple steps. This deems methods of the forward-backward-
splitting (FBS) type [14], such as the proximal gradient method [15, Sec.
2.3], appealing candidates. FBS-type algorithms can be used to solve nonlinear
optimal control problems with simple input constraints via first eliminating
the state sequence and expressing the cost as a function of the sequence of
inputs alone — the so-called single shooting formulation. However, despite its
simplicity, FBS, like all first-order methods, can exhibit slow convergence.
Its convergence rate is at best Q-linear with a Q-factor close to one for ill-
conditioned problems such as most nonlinear MPC problems.

In this work we propose a new modeling framework for generic constraints which
can accommodate general nonconvex sets. The proposed methodology assumes that
the obstacles are described by a set of nonlinear inequalities and does not
require the computation of projections or distances to them. Then, the
obstacle avoidance constraints are written as a nonlinear equality constraint
involving a smooth function which, in turn, is relaxed using a penalty
function.

The resulting problems are solved using PANOC, a proximal averaged Newton-type
method for optimal control, which was recently proposed in [16]. Gradients of
the cost function can be efficiently computed using automatic differentiation
toolboxes such as CasADi. The algorithm is simple to implement, yet robust,
since it combines projected gradient iterations with quasi-Newtonian
directions to achieve fast convergence.

The proposed framework is tested on a number of simulation scenarios where we
show that it is possible to avoid obstacles of complex shape described by
nonlinear inequalities. PANOC is compared with SQP and IP methods and is found
to be significantly faster. Furthermore, we present experimental results on a
lab-scale robotic platform which runs a C implementation of PANOC.

###  I-B Notation

Let $\N$ be the set of nonnegative integers, $\N_{[k_{1},k_{2}]}$ be the set
of integers in the interval $[k_{1},k_{2}]$ and $\barre=\Re\cup\\{+\infty\\}$
be the set of extended real numbers. For a matrix $A\in\Re^{m\times n}$, we
denote its transpose by $A^{\scriptstyle\top}$. For $x\in\Re$, we define the
operator $\plus{x}=\max\\{x,0\\}$. For a nonempty closed convex set
$U\subseteq\Re^{n}$, the projection onto $U$ is the operator
$\operatorname{\Pi}_{U}(v)=\operatorname*{\arg\\!\min}_{u\in U}\|u-v\|$. The
distance from the set $U$ is defined as $\operatorname{dist}_{U}(v)=\inf_{u\in
U}\|u-v\|$. The class of continuously differentiable functions
$f{}:{}\Re^{n}\to\Re$ is denoted by $C^{1}$. The subset of $C^{1}$ of
functions with Lipschitz-continuous gradient is denoted as $C^{1{},{}1}$. We
use the notation $C^{1{},{}1}_{{L}}$ for $C^{1{},{}1}$ functions with
$L$-Lipschitz gradients.

##  II NMPC for obstacle avoidance

###  II-A Problem statement

Kinematic equations lead to continuous-time nonlinear dynamical systems of the
form $\dot{x}=f_{c}(x,u,t)$ where $x\in\Re^{n_{x}}$ is the system state,
typically a vector comprising of position, velocity and orientation data, and
$u\in\Re^{n_{u}}$ is the control signal. We assume that the position
coordinates $z\in\Re^{n_{d}}$ are part of the state vector. The continuous-
time dynamics can be discretized (for instance, using an explicit Runge-Kutta
method) leading to a discrete-time dynamical system of the form

$x_{k+1}=f_{k}(x_{k},u_{k}).$ (1)

As it is typically the case in practice, we assume that
$f_{k}:\Re^{n_{x}}\times\Re^{n_{u}}\to\Re^{n_{x}}$ are smooth mappings.

The objective of the navigation controller is to steer the controlled vehicle
from an initial state $x_{0}$ to a target state $x_{\mathrm{ref}}$, typically
a position in space together with a desired orientation. At the same time, the
vehicle has to avoid certain, possibly moving, obstacles which are described
by open sets $O_{kj}\subseteq\Re^{n_{d}}$, $j\in\N_{[1,q_{k}]}$, each
described by

$O_{kj}=\\{z\in\Re^{n_{d}}{}:{}h_{kj}^{i}(z)>0,i\in\N_{[1,m_{kj}]}\\}.$ (2)

Sets $O_{kj}$ need not be convex. Obstacle avoidance constraints can be
concisely written as

$z_{k}\notin O_{kj},\text{ for }j\in\N_{[1,q_{k}]}.$ (3)

Moreover, the vehicle is only allowed to move in a domain which is described
by the inequalities

$g_{k}(x_{k},u_{k})\leq 0,$ (4)

where $g_{k}:\Re^{n_{x}}\times\Re^{n_{u}}\to\Re^{n_{c}}$ is a $C^{2}$ mapping
and $\leq$ is meant in the element-wise sense. Control actions $u_{k}$ are
constrained in a closed compact set $U_{k}$, that is

$u_{k}\in U_{k},$ (5)

on which it is easy to project and hereafter shall be assumed to be convex.
Sets $U_{k}$ often represent box constraints of the form
$U_{k}=\\{u\in\Re^{n_{u}}{}:{}u_{\mathrm{min}}\leq u\leq u_{\mathrm{max}}\\}$.

###  II-B Nonlinear model predictive control

Nonlinear model predictive control problems arising in obstacle avoidance can
be written in the following form

$\displaystyle\operatorname*{minimize}\quad$
$\displaystyle\ell_{N}(x_{N})+\sum_{k=0}^{N-1}\ell_{k}(x_{k},u_{k}),$ (6a)
$\displaystyle\operatorname*{subject\ to}\quad$ $\displaystyle x_{0}=x,$ (6b)
$\displaystyle x_{k+1}=f_{k}(x_{k},u_{k}),\,k\in\N_{[0,N-1]},$ (6c)
$\displaystyle u_{k}\in U_{k},\,k\in\N_{[0,N-1]},$ (6d) $\displaystyle
z_{k}\notin O_{kj},\,j\in\N_{[1,q_{k}]},\,k\in\N_{[0,N]}$ (6e) $\displaystyle
g_{k}(x_{k},u_{k})\leq 0,\,k\in\N_{[0,N]},$ (6f) $\displaystyle
g_{N}(x_{N})\leq 0.$ (6g)

The stage costs $\ell_{k}:\Re^{n_{x}}\times\Re^{n_{u}}\to\Re$ for
$k\in\N_{[0,N-1]}$ in (6a) are $C^{1{},{}1}$ functions penalizing deviations
of the state from the reference (destination and orientation) and may be taken
to be quadratic functions of the form
$\ell(x_{k},u_{k})=(x_{k}-x_{\mathrm{ref}})^{{\scriptscriptstyle\top}}Q_{k}(x_{k}-x_{\mathrm{ref}})+(u_{k}-u_{\mathrm{ref}})^{{\scriptscriptstyle\top}}R_{k}(u_{k}-u_{\mathrm{ref}})$.
The terminal cost $\ell_{N}:\Re^{n_{x}}\to\Re$ in (6a) is a $C^{1{},{}1}$
function such as
$\ell_{N}(x_{N})=(x_{N}-x_{\mathrm{ref}})^{{\scriptscriptstyle\top}}Q_{N}(x_{N}-x_{\mathrm{ref}})$.

###  II-C Reformulation of obstacle avoidance constraints

Consider an obstacle described as the intersection of a finite number of
strict nonlinear inequalities

$O=\\{z\in\Re^{n_{d}}{}:{}h^{i}(z)>0,i\in\N_{[1,m]}\\},$ (7)

where $h^{i}:\Re^{n_{d}}\to\Re$ are $C^{1{},{}1}$ functions. The constraint
$z\notin O$ — cf. (6e) — is satisfied if and only if

$h^{i_{0}}(z)\leq 0,\,\text{for some}\,i_{0}\in\N_{[1,m]},$ (8)

or, equivalently, $\plus{h^{i_{0}}(z)}^{2}=0$. This constraint can then be
encoded as

$\psi_{O}(z)\dfn\tfrac{1}{2}\prod_{i=1}^{m}\plus{h^{i}(z)}^{2}=0.$ (9)

We have expressed the obstacle avoidance constraints as a nonlinear equality
constraint. We should remark that, unlike approaches based on the distance-to-
set function [17], function $\psi_{O}$ in (9) is a $C^{1}$ function of $z$.
Indeed, $\psi_{O}$ is differentiable in $\Re^{n_{d}}\setminus O$ (and equal to
$0$), it is differentiable in $O$ with gradient

$\nabla\psi_{O}(z)=\begin{cases}\sum\limits_{i{}={}1}^{m}h^{i}(z)\prod\limits_{j{}\neq{}i}\\!(h^{j}(z))^{2}\nabla
h^{i}(z),&\text{if}\,x{}\in{}O,\\\ 0,&\text{otherwise.}\end{cases}$ (10)

Note that $\nabla\psi_{O}$ on the boundary of $O$ vanishes, so it is
everywhere continuous. If, additionally, $O$ is bounded, $\psi_{O}$ is
$C^{1,1}$.

The formulation of Eq. (9) can be used for obstacles described by quadratic
constraints of the form
$O=\\{z\in\Re^{n_{d}}{}:{}1-(z-c)^{\scriptscriptstyle\top}E(z-c)>0\\},$ such
as balls and ellipsoids. Then, the associated equality constraint becomes
$\plus{1-(z-c)^{\scriptscriptstyle\top}E(z-c)}^{2}=0.$ Polyhedral obstacles of
the form
$O=\\{z\in\Re^{n_{d}}{}:{}b_{i}-a_{i}^{{\scriptscriptstyle\top}}z>0,\in\N_{[1,m]}\\},$
with $b_{i}\in\Re$ and $a_{i}\in\Re^{n_{d}}$, can also be accommodated by the
constraint
$\prod_{i=1}^{m}\plus{b_{i}-a_{i}^{\scriptscriptstyle\top}z}^{2}=0.$

Equation (9) can also be used to describe general nonconvex constraints such
as ones described by semi-algebraic sets where $h^{i}(z)$ are polynomials as
well as any other obstacle which is available in the aforementioned
representation.

Obstacle avoidance constraints (9) are equivalent to the existence of
$t\in\Re^{m}$ so that

$\displaystyle\min\\{t_{1},\ldots,t_{m}\\}=0,$ (11a) $\displaystyle
h^{i}(z)\leq t_{i},\text{ for }i\in\N_{[1,m]}.$ (11b)

This observation reveals a link to vertical complementarity constraints which
have been studied extensively in the literature [18, 19].

###  II-D Relaxation of constraints

Due to the fact that modeling errors and disturbances may lead to the
violation of imposed constraints and infeasibility of the MPC optimization
problem, it is common practice in MPC to replace state constraints by
appropriate penalty functions known as soft constraints. Quadratic penalty
functions are often used for this purposes revealing a clear link between this
approach and the quadratic penalty method in numerical optimization [15, Sec.
4.2.1].

Equality constraints, such as the ones arising in the reformulation of the
obstacle avoidance constraints in Section II-C, can be relaxed by means of
soft constraints. Indeed, constraints of the form $\Phi_{k}(z_{k})=0$,
$k\in\N_{[1,N]}$, where $\Phi_{k}:\Re^{n_{d}}\to\Re_{+}$ are $C^{2}$
functions, can be relaxed by introducing the penalty functions
$\tilde{\Phi}_{k}(z_{k})=\eta_{k}\Phi_{k}(z_{k})$ for some weight factors
$\eta_{k}>0$.

That said, constraints like (9) for a set of time-varying obstacles
$O_{kj}=\\{z\in\Re^{n_{d}}{}:{}h_{kj}^{i}(z)>0,i\in\N_{[1,m_{kj}]}\\}$, with
$j\in\N_{[1,q_{k}]}$, can be relaxed by the appending the following term in
the original cost function

$\tilde{h}_{k}(z_{k})=\sum_{j=1}^{q_{k}}\eta_{kj}\prod_{i=1}^{m_{kj}}\plus{h^{i}_{kj}(z)}^{2},$
(12)

for some positive weight factors $\eta_{kj}>0$.

Note that the proposed approach for dealing with obstacle avoidance
constraints requires only a representation of the obstacles in the generic
form (7) and does not call for the computation of distances to the obstacles
as in distance-based methods [4, 17], nor does it require the obstacles to be
convex sets.

Similarly, inequality constraints of the form $g_{k}(x_{k},u_{k})\leq 0$ and
$g_{N}(x_{N})\leq 0$ can be relaxed by introducing the penalty functions
$\tilde{g}_{k}(x,u)=\beta_{k}\plus{g_{k}(x,u)}^{2}$ and
$\tilde{g}_{N}(x)=\beta_{N}\plus{g_{N}(x)}^{2}$ for positive weights
$\beta_{k}>0$, $k\in\N_{[0,N]}$.

We may now relax the state constraints in (6) by defining the modified stage
cost and terminal cost functions

$\displaystyle\tilde{\ell}_{k}(x,u)$
$\displaystyle=\ell_{k}(x,u)+\tilde{g}_{k}(x,u)+\tilde{h}_{k}(z_{k}),$
$\displaystyle\tilde{\ell}_{N}(x)$
$\displaystyle=\ell_{N}(x)+\tilde{g}_{N}(x),$

leading to the following relaxed optimization problem without state
constraints

$\displaystyle\operatorname*{minimize}\quad$
$\displaystyle\tilde{\ell}_{N}(x_{N})+\sum_{k=0}^{N-1}\tilde{\ell}_{k}(x_{k},u_{k}),$
(13a) $\displaystyle\operatorname*{subject\ to}\quad$ $\displaystyle x_{0}=x,$
(13b) $\displaystyle x_{k+1}=f_{k}(x_{k},u_{k}),\,k\in\N_{[0,N-1]},$ (13c)
$\displaystyle u_{k}\in U_{k},\,k\in\N_{[0,N-1]},$ (13d)

###  II-E NMPC problem formulation

In this section we cast the nonlinear MPC problem (6) as

$\operatorname*{minimize}\limits_{u\in{}U}\,\ell(u),$ (14)

where the optimization is carried out over vectors
$u=(u_{0},\ldots,u_{N-1})\in\Re^{n}$, with $n=Nu_{u}$ and $U\dfn U_{0}\times
U_{1}\times\cdots\times U_{N-1}$ and $\ell:\Re^{n}\to\Re$ is a real-valued
$C^{1{},{}1}_{{L_{\ell}}}$ function.

We introduce the following sequence of functions $F_{k}:\Re^{n}\to\Re^{n_{x}}$
for $k\in\N_{[0,N-1]}$

$\displaystyle F_{0}(u)$ $\displaystyle=x,$ (15a) $\displaystyle F_{k+1}(u)$
$\displaystyle=f_{k}(F_{k}(u),u_{k}).$ (15b)

Define the smooth function $\ell:\Re^{n}\to\Re$

$\ell(u)\dfn\tilde{\ell}_{N}(F_{N}(u))+\sum_{k=0}^{N-1}\tilde{\ell}_{k}(F_{k}(u),u_{k}).$
(16)

The gradient of function $\ell$ in (16) can be computed by means of the
reverse mode of automatic differentiation (also known as adjoint method or
backpropagation) as shown in Alg. 1 [20].

Algorithm 1 Automatic differentiation for $\ell$ in (16)

0: $x_{0}\in\Re^{n_{x}}$, $u\in\Re^{n}$.

0: $\ell(u)$, $\nabla\ell(u)$

1: $\ell(u){}\leftarrow{}0$

2: for $k=0,\ldots,N-1$ do

3: $x_{k+1}{}\leftarrow{}f_{k}(x_{k},u_{k})$,
$\ell(u){}\leftarrow{}\ell(u)+\tilde{\ell}_{k}(x_{k},u_{k})$

4: $\ell(u){}\leftarrow{}\ell(u)+\tilde{\ell}_{N}(x_{N})$,
$p_{N}{}\leftarrow{}\nabla\tilde{\ell}_{N}(x_{N})$

5: for $k=N-1,\ldots,0$ do

6:
$p_{k}{}\leftarrow{}\nabla_{x_{k}}f_{k}(x_{k},u_{k})p_{k+1}+\nabla_{x_{k}}\tilde{\ell}_{k}(x_{k},u_{k})$

7:
$\nabla_{u_{k}}\ell_{k}(u){}\leftarrow{}\nabla_{u_{k}}f_{k}(x_{k},u_{k})+\nabla_{u_{k}}\tilde{\ell}_{k}(x_{k},u_{k})$

Problem (14) is in a form that allows the application of the projected
gradient iteration

$u^{\nu+1}=T_{\gamma}(u^{\nu})\dfn\operatorname{\Pi}_{U}(u^{\nu}-\gamma\nabla\ell(u^{\nu})),$
(17)

with $\gamma>0$. In particular, if $\ell\in C^{1{},{}1}_{{L_{\ell}}}$ and
$\gamma<\nicefrac{{2}}{{L_{\ell}}}$, then all accumulation points of (17),
$u^{\star}$, are fixed points of $T_{\gamma}$ called $\gamma$-critical points,
that is [10, Prop. 2.3.2]

$u^{\star}=T_{\gamma}(u^{\star}).$ (18)

##  III Fast nonlinear MPC

The problem of finding a fixed point for $T_{\gamma}$ can be reduced to the
equivalent problem of finding a zero of the fixed-point residual operator
which is defined as the operator

$R_{\gamma}(u)=\tfrac{1}{\gamma}(u-T_{\gamma}(u)).$ (19)

This motivates the adoption of a Newton-type iterative scheme

$u^{\nu+1}=u^{\nu}-H_{\nu}R_{\gamma}(u^{\nu}),$ (20)

where $H_{\nu}$ are invertible linear operators, appropriately chosen so as to
encode first-order information about $R_{\gamma}$. This is done by enforcing
the _inverse secant condition_ $s^{\nu}=H_{\nu+1}y^{\nu}$, for
$s^{\nu}=u^{\nu+1}-u^{\nu}$ and
$y^{\nu}=R_{\gamma}(u^{\nu+1})-R_{\gamma}(u^{\nu})$ and can be obtained by
quasi-Newtonian methods such as the limited-memory BFGS (L-BFGS) method [10]
which is free from matrix operations, requires only a limited number of inner
products and is suitable for embedded implementations. The main weakness of
this approach is that convergence is only guaranteed in a neighborhood of a
$\gamma$-critical point $u^{\star}$. We shall describe a globalization
procedure which hinges on the notion of the forward-backward envelope
function.

###  III-A The Forward-Backward envelope function

The forward-backward envelope (FBE) is an exact, continuous, real-valued merit
function for (14) [21, 22, 16, 23, 24]. Function $\ell$ can be approximated at
a point $u\in U$ by the quadratic upper bound

$Q^{\ell}_{\gamma}(v;u)=\ell(u)+\nabla\ell(u)^{\scriptscriptstyle\top}(v-u)+\nicefrac{{1}}{{2\gamma}}\|u-v\|^{2}.$
(21)

The FBE is then defined as

$\varphi_{\gamma}(u)=\inf_{v\in U}Q^{\ell}_{\gamma}(v;u).$ (22)

This construction is illustrated in Fig. 1. Provided that it is easy to
compute the distance to $U$, the FBE can be easily computed by

$\varphi_{\gamma}(u)=\ell(u)-\tfrac{\gamma}{2}\|\nabla\ell(u)\|^{2}+\tfrac{1}{2\gamma}\operatorname{dist}_{U}^{2}(u-\gamma\nabla\ell(u)).$
(23)

Therefore, the computation of the FBE is of the same complexity as that of a
forward-backward step.

Figure 1: Construction of the FBE with $\gamma=0.15$ (red line) for the
function $\ell(u)=\sin(2u)$ over the set $U=[0,2]$ (thick blue line). The
dashed line shows the approximation of $\ell$ at a point $u$ by the quadratic
model $Q^{\ell}_{\gamma}(v;u)$. The value of FBE at $u$ is then given by
$\varphi_{\gamma}(u)=\inf_{v\in U}Q^{\ell}_{\gamma}(v;u)$. Note that the local
minima of $\ell$ over $U$ are exactly the local minima of $\varphi_{\gamma}$.

The FBE possesses several favorable properties, perhaps the most important
being that it is real-valued, continuous and for
$\gamma\in(0,\nicefrac{{1}}{{L_{\ell}}})$ shares the same (local/strong)
minima with the original problem (14). This means that (14) is reduced to an
unconstrained minimization problem. Moreover, if $\ell\in C^{2}$, then
$\varphi_{\gamma}\in C^{1}$ with
$\nabla\varphi_{\gamma}(u)=(I-\gamma\nabla^{2}\ell(u))R_{\gamma}(u)$.

###  III-B PANOC Algorithm

We employ the proximal averaged Newton-type method for optimal control, for
short PANOC, which was recently proposed in [16]. PANOC performs fast Newton-
type updates while an FBE-based linesearch endows it with global convergence
properties while it uses the same oracle as the projected gradient method.

Algorithm 2 PANOC algorithm for problem (14)

0: $\gamma\in(0,\nicefrac{{1}}{{L_{\ell}}})$, $L_{\ell}>0$,
$\sigma\in(0,\tfrac{\gamma}{2}(1-\gamma L_{\ell}))$, $u_{0}\in\Re^{n}$,
$x_{0}\in\Re^{n_{x}}$, L-BFGS memory length $\mu$.

1: for $\nu=0,1,\ldots$ do

2:
$\bar{u}^{\nu}{}\leftarrow{}\operatorname{\Pi}_{U}(u^{\nu}-\gamma\nabla\ell(u^{\nu}))$

3: $r^{\nu}{}\leftarrow{}\gamma^{-1}(u^{\nu}-\bar{u}^{\nu})$

4: $d^{\nu}\leftarrow-H_{\nu}r^{\nu}$ using L-BFGS

5: $u^{\nu+1}{}\leftarrow{}u^{\nu}-(1-\tau\\!_{\nu})\gamma
r^{\nu}+\tau\\!_{\nu}d^{\nu}$, where $\tau\\!_{\nu}$ is the largest number in
$\\{\nicefrac{{1}}{{2^{i}}}{}:{}i\in\N\\}$ such that
$\varphi_{\gamma}(u^{\nu+1}){}\leq{}\varphi_{\gamma}(u^{\nu})-\sigma\|r^{\nu}\|^{2}$
(24)

The iterative scheme, which is presented in Alg. 2, involves the computation
of a projected gradient point $\bar{u}^{\nu}$ in step 2 and an L-BFGS
direction $d^{\nu}$ in step 4. L-BFGS obviates the need to store or explicitly
update matrices $H_{\nu}$ in (20) by storing a number $\mu$ of past values of
$s^{\nu}$ and $y^{\nu}$. The computation of $d^{\nu}$ requires only inner
products which amount to a maximum of $4\mu n$ scalar multiplications. In step
5, the iterates are updated using a convex combination of the projected
gradient update direction $-\gamma R_{\gamma}(u^{\nu})$ and a fast quasi-
Newtonian direction $d^{\nu}$. The algorithm is terminated when
$\|R_{\gamma}(u^{\nu})\|_{\infty}$ drops below a specified tolerance.

In line 5, the backtracking line search procedure ensures that a sufficient
decrease condition is satisfied using the FBE as a merit function. Under mild
assumptions, eventually only fast updates are activated and updates reduce to
$u^{\nu{}+{}1}=u^{\nu}{}+{}d^{\nu}$. The sequence of fixed-point residuals
$\\{r^{\nu}\\}_{\nu\in\N}$ converges to $0$ square summably, while PANOC
produces sequences of iterates, $\\{u^{\nu}\\}_{\nu\in\N}$ and
$\\{\bar{u}^{\nu}\\}_{\nu\in\N}$, whose cluster points are $\gamma$-critical
points.

In absence of a Lipschitz constant $L_{\ell}$, the algorithm can be
initialized with an estimate, e.g.,
$L_{\ell}^{0}={\|\nabla_{u}\ell(u^{0}+\delta
u)-\nabla_{u}\ell(u^{0})\|}/{\|\delta u\|},$ where $\delta u\in\Re^{n}$ is a
small perturbation vector. Then, step 2 in Alg. 2 needs to be replaced by the
backtracking procedure of Alg. 3 which updates $L_{\ell}$, $\sigma$ and
$\gamma$.

Algorithm 3 Lipschitz constant backtracking

while
$\ell(\bar{u}^{\nu})>\ell(u^{\nu})-\gamma\nabla\ell(u^{\nu})^{\scriptscriptstyle\top}r^{\nu}+\nicefrac{{L_{\ell}}}{{2}}\|\gamma
r^{\nu}\|^{2}$ do

$L_{\ell}\leftarrow 2L_{\ell}$, $\sigma\leftarrow\nicefrac{{\sigma}}{{2}}$,
$\gamma\leftarrow\nicefrac{{\gamma}}{{2}}$

$\bar{u}^{\nu}{}\leftarrow{}\operatorname{\Pi}_{U}(u^{\nu}-\gamma\nabla\ell(u^{\nu}))$

Alg. 3 updates $L_{\ell}$, $\sigma$ and $\gamma$ only a finitely many times,
so, it does not affect the convergence properties of the algorithm.

In MPC, we may warm start the algorithm using the optimal solution of the
previous MPC instance. Unlike SQP and IP methods, PANOC does not require the
solution of linear systems or quadratic programming problems at every
iteration and it involves only very simple operations such as vector
additions, scalar and inner products. Additionally, PANOC converges globally,
that is, from any initial point $u^{0}\in\Re^{n}$.

##  IV Simulations

Figure 2: In-house developed mobile robot with trailer.

The proposed methodology is validated on the control of a mobile robot
carrying a trailer shown in Fig. 2. Assuming zero slip of the trailer wheels,
the nonlinear kinematics is

$\displaystyle\dot{p}_{x}$
$\displaystyle=u_{x}+L\sin\theta{}\cdot{}\dot{\theta},$ (25a)
$\displaystyle\dot{p}_{y}$
$\displaystyle=u_{y}-L\cos\theta{}\cdot{}\dot{\theta},$ (25b)
$\displaystyle\dot{\theta}$ $\displaystyle=\tfrac{1}{L}\left(u_{y}\cos\theta-
u_{x}\sin\theta\right),$ (25c)

where the state vector $x=(p_{x},p_{y},\theta)$ comprises the coordinates
$p_{x}$ and $p_{y}$ of the trailer and the heading angle $\theta$. The input
$u=(u_{x},u_{y})$ is a velocity reference which is tracked by a low-level
controller. The distance between the center of mass of the trailer and the
fulcrum connecting to the towing vehicle is $L=0.5\,\mathrm{m}$. In Fig. 3 we
present four obstacle avoidance scenarios involving, among other, obstacles
described by polynomial and trigonometric functions. The system dynamics given
in (25) is discretized using the fourth-order Runge-Kutta method and we use
memory $\mu=10$ for the L-BFGS directions in Alg. 2.

Figure 3: Four obstacle avoidance scenarios using PANOC. The red x mark
denotes the destination point and various lines are trajectories from
different initial points. The dashed lines correspond to enlargements of
obstacles which are circumscribed by thick green lines. (First row) Obstacle
avoidance with circular and rectangular obstacles, (Down, left) Enlarged
obstacle defined by $O=\\{(x,y){}:{}y>x^{2},y<1+\nicefrac{{x^{2}}}{{2}}\\}$
and (Down, right) Enlarged obstacle defined by
$O=\\{(x,y){}:{}y>2\sin(-\nicefrac{{x}}{{2}}),y<3\sin(\nicefrac{{x}}{{2}}-1),1{<}x{<}8\\}$.
Figure 4: Comparison of runtime to solve the NMPC problem for four solvers:
PANOC, IPOPT and fmincon’s SQP algorithm (for the single and multiple shooting
formulations) and projected gradient (ForBES implementation). These timings
correspond to the navigation problem presented in Fig. 3 (upper right
subfigure), starting from the initial point
$x_{0}=(-0.1,-0.2,\nicefrac{{\pi}}{{5}})$ and with $N=50$. The tolerance was
set to $3\cdot 10^{-3}$ for all solvers. All solvers are warm-started with
their previous solution.

The single shooting formulation of Section II is solved with PANOC, the
interior point solver IPOPT, the forward-backward splitting (FBS)
implementation of ForBES and the SQP of MATLAB’s fmincon. The problem was also
brought in a multiple shooting formulation where obstacle avoidance
constraints were imposed as in (9) and it was solved using IPOPT and SQP. A
comparison of runtime is shown in Fig. 4. All simulations were executed on an
Intel i5-6200U CPU with $12\,\mathrm{GB}$ RAM machine running Ubuntu 14.04.
PANOC exhibits very low runtime and outperforms all other solvers by
approximately two orders of magnitude.

##  V Experimental results and discussion

|  |  |
---|---|---|---
Figure 5: Point-to-point motion of a holonomic robot with a trailer. The robot
avoids a circular and rectangular obstacle indicated with the green lines. The
predicted position trajectories are represented in blue and the target
position is indicated with the red cross.

The proposed NMPC algorithm is validated on an in-house mobile robot with a
trailer (Fig. 2). The robot has four independent DC motors with Mecanum
wheels, which render it holonomic. A low-level microcontroller implements a
velocity controller for each motor. Therefore, from a high-level perspective,
the robot can be treated as a velocity-steered holonomic device. A trailer is
attached to the robot and the angle between robot and trailer is measured with
a rotary potentiometer. A ceiling camera detects the robot’s absolute position
and orientation using a marker attached on top of the robot. This information
is sent to the robot over Wi-Fi and is merged with local encoder measurements
to retrieve a fast and accurate estimate of its pose. An Odroid XU4 platform
runs the NMPC algorithm on board the robotic platform. PANOC is implemented in
C following the C89 standard without external dependencies and can, therefore,
be readily executed on embedded systems. The C code for performing Alg. 1 was
generated using the AD tool CasADi [25].

The NMPC algorithm is used to steer the vehicle to a desired destination and
trailer orientation $x_{\mathrm{ref}}=(3.77,1.40,0.0)$. The system dynamics is
discretized using the Euler method. A quadratic cost function is employed with
$Q_{k}=Q_{N}=0.1\cdot I_{3}$ and $R_{k}=0.01\cdot I_{2}$. Box constraints are
imposed on the inputs with
$u_{\mathrm{min}}=-0.8\,\nicefrac{\mathrm{m}}{\mathrm{s}}$ and
$u_{\mathrm{max}}=0.8\,\nicefrac{\mathrm{m}}{\mathrm{s}}$. The obstacles are
modelled as discussed in Section II-C and are slightly enlarged for safety so
as to completely avoid collisions. A horizon length of $N{}={}50$ is used and
the NMPC control rate is $10\,\mathrm{Hz}$. Fig. 5 shows the resulting motion
of the robot and the predicted position trajectories at four time instants.
PANOC is terminated when $\|r^{\nu}\|_{\infty}\leq 10^{-6}$ or if the number
of iterations reaches $500$. The number of iterations $\bar{\nu}$, the solving
time $t_{\mathrm{s}}$ on the Odroid XU4 and the norm of the fixed point
residual at termination at each time instant $k$ are shown in Fig. 6.

Additional material and videos from the experiments are found at https://kul-
forbes.github.io/PANOC.

Figure 6: Number of iterations $\bar{\nu}$, solve time $t_{s}$ and final
residual $\|r^{\nu}\|_{\infty}$ for each NMPC cycle.

##  VI Conclusions and research directions

We proposed a novel framework which enables us to encode nonconvex obstacle
avoidance constraints as a smooth nonlinear equality constraint. This offers a
flexible modeling framework and allows the formulation of nonlinear MPC
problems with obstacles of complex nonconvex geometry. The resulting MPC
problem is solved with PANOC which has favorable theoretical convergence
properties and outperforms state-of-the-art NLP solvers. This framework was
tested using a C89 implementation of PANOC on a lab-scale system.

Future work will focus on the development of a proximal Lagrangian framework
for the online adaptation of the weight parameters in the obstacle avoidance
penalty functions — cf. (12) — so that (predicted) constraint violations,
modeled by $\tilde{h}(z_{k})$, are below a desired tolerance. Moreover, the
use of semismooth Newton directions in PANOC will lead to quadratic
convergence and superior performance [21].

## References

  * [1] O. Takahashi and R. J. Schilling, “Motion planning in a plane using generalized voronoi diagrams,” _IEEE Trans. Rob. Autom._ , vol. 5, no. 2, pp. 143–150, Apr 1989.
  * [2] J. Minguez, F. Lamiraux, and J.-P. Laumond, _Motion Planning and Obstacle Avoidance_. Cham: Springer, 2016, pp. 1177–1202.
  * [3] D. Bareiss and J. van den Berg, “Generalized reciprocal collision avoidance,” _Int. J. Robot. Res._ , vol. 34, no. 12, pp. 1501–1514, 2015.
  * [4] P. Wang and B. Ding, “A synthesis approach of distributed model predictive control for homogeneous multi-agent system with collision avoidance,” _Int. J. Control_ , vol. 87, no. 1, pp. 52–63, 2014.
  * [5] T. Mercy, R. V. Parys, and G. Pipeleers, “Spline-based motion planning for autonomous guided vehicles in a dynamic environment,” _IEEE Trans. Control Syst. Technol._ , vol. PP, no. 99, pp. 1–8, 2017.
  * [6] F. Debrouwere, W. Van Loock, G. Pipeleers, M. Diehl, J. De Schutter, and J. Swevers, “Time-optimal path following for robots with object collision avoidance using Lagrangian duality,” in _9th IEEE Int. Workshop Rob. Mot. Conntrol (RoMoCo)_ , 2013, pp. 186–191.
  * [7] B. Alrifaee, M. G. Mamaghani, and D. Abel, “Centralized non-convex model predictive control for cooperative collision avoidance of networked vehicles,” in _IEEE ISIC_ , Oct 2014, pp. 1583–1588.
  * [8] J. V. Frasch, A. Gray, M. Zanon, H. J. Ferreau, S. Sager, F. Borrelli, and M. Diehl, “An auto-generated nonlinear MPC algorithm for real-time obstacle avoidance of ground vehicles,” in _Eur. Control Conf._ , 2013, pp. 4136–4141.
  * [9] V. Turri, A. Carvalho, H. E. Tseng, K. H. Johansson, and F. Borrelli, “Linear model predictive control for lane keeping and obstacle avoidance on low curvature roads,” in _IEEE Intell. Transp. Syst. Conf._ , Oct 2013, pp. 378–383.
  * [10] J. Nocedal and S. J. Wright, _Numerical Optimization_. Springer New York, 2006.
  * [11] S. Boyd and L. Vandenberghe, _Convex optimization_. Cambridge university press, 2004.
  * [12] A. Wächter and L. T. Biegler, “On the implementation of an interior-point filter line-search algorithm for large-scale nonlinear programming,” _Mathem. Progr._ , vol. 106, no. 1, pp. 25–57, Mar 2006.
  * [13] M. Diehl, H. G. Bock, and J. P. Schlöder, “A real-time iteration scheme for nonlinear optimization in optimal feedback control,” _SIAM J. Contr. Optim._ , vol. 43, no. 5, pp. 1714–1736, 2005.
  * [14] H. Attouch, J. Bolte, and B. F. Svaiter, “Convergence of descent methods for semi-algebraic and tame problems: proximal algorithms, forward–backward splitting, and regularized Gauss–Seidel methods,” _Math. Progr._ , vol. 137, no. 1, pp. 91–129, Feb 2013.
  * [15] D. P. Bertsekas, _Nonlinear programming_. Athena Scientific, 1999.
  * [16] L. Stella, A. Themelis, P. Sopasakis, and P. Patrinos, “A simple and efficient algorithm for nonlinear model predictive control,” in _IEEE CDC_ , Melbourne, Australia, 2017.
  * [17] E. Gilbert and D. Johnson, “Distance functions and their application to robot path planning in the presence of obstacles,” _IEEE J. Rob. Autom._ , vol. 1, no. 1, pp. 21–30, Mar 1985.
  * [18] H. Scheel and S. Scholtes, “Mathematical programs with complementarity constraints: Stationarity, optimality, and sensitivity,” _Math. Op. Res._ , vol. 25, no. 1, pp. 1–22, 2000.
  * [19] Y.-C. Liang and G.-H. Lin, “Stationarity conditions and their reformulations for mathematical programs with vertical complementarity constraints,” _J. Optim. Theory Appl._ , vol. 154, no. 1, pp. 54–70, 2012.
  * [20] J. C. Dunn and D. P. Bertsekas, “Efficient dynamic programming implementations of Newton’s method for unconstrained optimal control problems,” _J. Optim. Theory & Appl._, vol. 63, no. 1, pp. 23–38, 1989.
  * [21] P. Patrinos, L. Stella, and A. Bemporad, “Forward-backward truncated Newton methods for convex composite optimization,” _arXiv:1402.6655_ , Feb. 2014\.
  * [22] L. Stella, A. Themelis, and P. Patrinos, “Forward-backward quasi-Newton methods for nonsmooth optimization problems,” _Comput. Optim. Appl._ , vol. 67, no. 3, pp. 443–487, Jul 2017.
  * [23] A. Themelis, L. Stella, and P. Patrinos, “Forward-backward envelope for the sum of two nonconvex functions: Further properties and nonmonotone line-search algorithms,” _ArXiv preprint_ , jun 2016.
  * [24] P. Patrinos and A. Bemporad, “Proximal Newton methods for convex composite optimization,” in _IEEE CDC_ , Dec 2013, pp. 2358–2363.
  * [25] J. Andersson, “A general-purpose software framework for dynamic optimization,” PhD thesis, KU Leuven, Dept. Electr. Eng. (ESAT/SCD) & Optimization in Engineering Center, October 2013.


# Analysis on noncompact manifolds and Index Theory: Fredholm conditions and
Pseudodifferential operators

Ivan Beschastnyi  CIDMA, University of Aveiro, Campus Santiago, 3810-193,
Aveiro, Portugal<EMAIL_ADDRESS>,  Catarina Carvalho  CEAFEL, Dep.
Matemática, Instituto Superior Técnico, University of Lisbon, Av. Rovisco
Pais, 1049-001 Lisbon, Portugal<EMAIL_ADDRESS>,
Victor Nistor  Université de Lorraine, CNRS, IECL, F-57000 Metz, France
<EMAIL_ADDRESS>and  Yu Qiao  School of Mathematics and
Statistics, Shaanxi Normal University, Xi’an, 710119, China<EMAIL_ADDRESS>
###### Abstract.

We provide Fredholm conditions for compatible differential operators on
certain Lie manifolds (that is, on certain possibly non-compact manifolds with
nice ends). We discuss in more detail the case of manifolds with cylindrical,
hyperbolic, and Euclidean ends, which are all covered by particular instances
of our results. We also discuss applications to Schrödinger operators with
singularities of the form $r^{-2\gamma}$, $\gamma\in\mathbb{R}_{+}$.

I.B and C.C were supported by FCT–Fundação para a Ciência e Tecnologia, under
projects UIDB/04106/2020 and UIDB/04721/2020, respectively. V.N. was supported
by ANR grant OpART and Y.Q was supported by NSFC (11971282).

##  1\. Introduction

We review in this note an approach to _Analysis on non-compact manifolds_ that
is based on _Lie algebras of vector fields_ and _compactifications of
manifolds._ This note is a revised and enhanced version of the talk delivered
by V.N. at the “Methusalem Colloquium and Geometric Analysis Seminar,” at
Ghent University, in June 2022. The mathematical results included here are
based, to a large extent, on the paper [4], but they are also enhanced by
recent results from [3]. Among the questions that we will touch upon are:

  * •

the invertibility of differential operators (Hadamard well-posedness),

  * •

the regularity of solutions of elliptic PDEs,

  * •

the construction of the algebras of pseudodifferential operators containing
the inverses of the elliptic operators in question, and, most notably,

  * •

the _Fredholm alternative,_ the topic around which we organize our paper.

_Informally stated,_ our main result on the Fredholm alternative is:

######  Theorem 1.1.

On a “nice” manifold, an adapted (pseudo)differential operator is _Fredholm_
if, and only if,

  1. (i)

it is _elliptic_ and

  2. (ii)

_all its “limit operators” are invertible._

A more formal statement will be included below (Theorem 3.3). In the above
result, by “elliptic” we mean a pseudodifferential operator whose principal
symbol is invertible outside of the zero section. On a compact manifold, there
are no “limit operators,” and the Fredholm property reduces to ellipticity. In
the non-compact case, the _limit operators do appear and play an important
role._ The appearance of limit operators is thus one of the main differences
between the analysis on compact and on non-compact manifolds. A large part of
this note is devoted to presenting a more formal version of the above theorem
(Theorem 1.1), as well as to explaining what the statement of that theorem
becomes for some standard classes and then for some new classes of manifolds.
We consider in this regard manifolds that have ends that are asymptotically of
one of the following forms:

(i) cylindrical, (ii) hyperbolic, or (iii) Euclidean (more general: conical).
In particular, we pay special attention to the description and properties of
the limit operators for these manifolds. The new type of examples is related
to Schrödinger operators with potentials with non-integer order singularities
at the origin. These examples rely on a generalization of the setting of [4]
that leads to more general pseudodifferential calculi [3].

There are many reasons to study Fredholm operators, one being that they are
useful also in obtaining _well-posedness results_ , for instance, by the
following paradigm: to prove that an operator $P$ is invertible, it suffices
to prove that it is Fredholm, that it has index zero, and that it has
vanishing kernel. An example where this procedure was used is in the paper by
M. Mitrea and M. Taylor [13] studying the layer potentials on smooth
subdomains of compact manifolds. Our results can thus be used to extend the
work of Mitrea and Taylor to some non-compact manifolds [7].

Let us stress that, although we are advertising mostly smooth (non-compact)
manifolds, the results presented here can be useful also for
(pseudo)differential operators on singular spaces, since one can treat
singular spaces by doing analysis on their smooth part, which is regarded as a
non-compact manifold, possibly with a different metric, usually conformally
equivalent to the original one. This is the case with _the passage from a
manifold with conical points to a manifold with cylindrical ends,_ which was
classically done via the so called “Kondratiev transform” $r=e^{t}$ and is
explained in the text.

Compared to the original talk, we have removed some repetitions and we have
included some additional details, examples, and results; we have tried,
however, to maintain as much as possible the style (and idiosyncrasies) of the
original talk. In particular, the plan of the presentation is to successively
discuss the Fredholm alternative and related topics for:

  1. (i)

_Smooth, compact manifolds_ (the classical case).

  2. (ii)

_Manifolds with cylindrical ends_ (an almost classical case). The main
examples here are the Laplacian in polar and generalized spherical
coordinates.

  3. (iii)

_Other classes of manifolds_ , for which we stress the similarities and
differences to manifolds with cylindrical ends. The main examples here are the
Laplacian in cylindrical coordinates and in flat, Euclidean coordinates.

As in the original talk (in any talk, for that matter), it was not realistic
to include a complete list of references. This is unfortunate, because very
many people have worked on analysis on non-compact manifolds. Since we are not
including enough references, let us stress that, _unless explicitly stated
otherwise,_ none of the results below belong to us. We thank Cipriana Anghel,
Sergiu Moroianu, Elmar Schrohe, and Jörg Seiler for useful discussions.

##  2\. Motivation and some classical results

Let us see what Theorem 1.1 becomes in some classically well-understood cases,
namely those of compact manifolds and of manifolds with cylindrical ends.

###  2.1. A classical case: smooth, compact manifolds

For pedagogical reasons, it will be useful to recall first the Fredholmness
result on smooth, compact manifolds without boundary. For simplicity, we will
assume from now on that all our manifolds are _smooth and complete Riemannian_
(except the manifolds with conical points). Thus we can define the Sobolev
spaces on these manifolds using the powers of the Laplacian. Let $P$ be an
order $m$, classical, pseudodifferential operator on a compact manifold $M$.
Then $P:H^{s}(M)\to H^{s-m}(M)$ is bounded. In general, we will consider
operators acting between sections of vector bundles $E$ and $F$. The following
result is classical:

######  Theorem 2.1.

Assume that $M$ is _smooth, compact, without boundary,_ and that $P$ is an
order $m$, classical, pseudodifferential operator. Then $P:H^{s}(M;E)\to
H^{s-m}(M;F)$ is _Fredholm_ if, and only if, it is _elliptic._

We stress again that, in the compact case, _there are no limit operators._ As
we will see in the next subsection, this is _not_ the case in the non-compact
case.

###  2.2. Motivating example: cylindrical ends

The simplest, motivating example of a non-compact manifold is that of a
manifold with _cylindrical ends._ We begin with three examples before giving
the formal definition.

####  2.2.1. Polar coordinates

The Laplacian on $\mathbb{R}^{2}$ in _polar coordinates_ $(r,\theta)$ is

$\Delta_{\mathbb{R}^{2}}u\,=\,r^{-2}\big{(}(r\partial_{r})^{2}u+\partial_{\theta}^{2}u\big{)}.$

Ignoring $r^{-2},$ we obtain the differential operator
$(r\partial_{r})^{2}+\partial_{\theta}^{2}$ acting on $[0,\infty)\times
S^{1}\ni(r,\theta),$ which is a _degenerate elliptic_ differential operator
acting on a manifold with boundary. We follow Melrose’s observation [11] that
this operator is generated by the vector fields

$r\partial_{r}\ \mbox{ and }\ \partial_{\theta}\,,$

which are tangent to the boundary $\\{0\\}\times S^{1}$, an observation that
will be useful in generalizations.

This example can be treated with the help of the _Kondratiev transform_
$t=\log r,$ which transforms $r\partial_{r}$ into $\partial_{t}.$ The operator
$(r\partial_{r})^{2}+\partial_{\theta}^{2}$ then becomes
$\partial_{t}^{2}+\partial_{\theta}^{2}$. Let $S^{n-1}$ be the _unit sphere_
in $\mathbb{R}^{n}.$ The Kondratiev transform maps the domain
$(0,\infty)\times S^{1}$ to $\mathbb{R}\times S^{1}$. The advantage of the
Kondratiev transform is that the resulting operator
$\partial_{t}^{2}+\partial_{\theta}^{2}$ is nothing but
$\Delta_{\mathbb{R}\times S^{1}},$ the _Laplacian_ for the metric
$(dt)^{2}+(d\theta)^{2}$ on $\mathbb{R}\times S^{1}$. The Fourier transform in
$t$ maps $\partial_{t}$ to $i\tau$ and hence it maps
$\partial_{t}^{2}+\partial_{\theta}^{2}$ to $-\tau^{2}+\partial_{\theta}^{2}.$
In turn, this operator can be understood via the spectral theory of
$\partial_{\theta}^{2}$ on $S^{1}$, which is well known. Anticipating,
$\mathbb{R}\times S^{1}$ is the simplest non-trivial example of a “manifold
with cylindrical ends.” For general manifolds with cylindrical ends, the
Fourier transform will be applied not to the operator itself, but rather to
its limit operators, which are also $\mathbb{R}$-invariant operators.

####  2.2.2. The Black-Scholes operator

An example that can be treated similarly is that of

$\partial_{t}u\,+\,\,\frac{\sigma^{2}}{2}(x\partial_{x})^{2}u+\Big{(}r-\frac{\sigma^{2}}{2}\Big{)}x\partial_{x}u-ru\,,$

the _Black-Scholes operator_. This example is, in a certain sense, even
simpler than that of the Laplace operator in polar coordinates, since it is an
example in one dimension.

####  2.2.3. Generalized spherical coordinates

A related example is the _Schrödinger operator_
$\Delta_{\mathbb{R}^{n}}+Z/\rho$ on $\mathbb{R}^{n},$ $Z\in\mathbb{C}$, in
(generalized) spherical coordinates $(\rho,x^{\prime})\in(0,\infty)\times
S^{n-1}$:

$-\Big{(}\Delta_{\mathbb{R}^{n}}+Z\rho^{-1}\Big{)}u\,=\,-\rho^{-2}\big{(}(\rho\partial_{\rho})^{2}u+(n-2)\rho\partial_{\rho}u+\Delta_{S^{n-1}}u+Z\rho
u\big{)}.$

In this example, the operator is considered on $[0,\infty)\times S^{n-1}$ and
is generated by $\rho\partial_{\rho}$ and vector fields independent of $\rho$
(which yield the Laplacian on the sphere $S^{n-1}$). The relevant geometry for
this operator is again that of manifolds with cylindrical ends, since it can
be generated by vector fields that are tangent to the boundary $\\{0\\}\times
S^{n-1}$ of $[0,\infty)\times S^{n-1}$. Note that, after ignoring the factor
$\rho^{-2}$, the resulting operator no longer has a singular potential. This
example can also be treated via the Kondratiev and Fourier transforms.

####  2.2.4. Manifolds with cylindrical ends

Let us now describe the general setting encompassing the previous three
examples. Let $\overline{M}$ be a _smooth, compact manifold with boundary_
$\partial\overline{M}$ and let $r\geq 0$ be a smooth function on
$\overline{M}$ such that $\partial\overline{M}=r^{-1}(0)$ and $dr\neq 0$ on
$\partial\overline{M}$. Up to Lipschitz equivalence, a _manifold with
cylindrical ends_ is one that is isometric to
$M:=\overline{M}\smallsetminus\partial\overline{M}$ endowed with a metric
that, near the boundary, is of the form

(1) $g_{cyl}\,:=\,\frac{dr^{2}}{r^{2}}+h\,,$

where $h$ is a semi-definite tensor that restricts to a true metric on
$\partial\overline{M}$. In local coordinates $x=(r,x_{2},\ldots,x_{n})$ near
the boundary, the Sobolev spaces $H^{m}(M;g_{cyl})$ associated to the metric
$g_{cyl}$ identify with the Babuška-Kondratiev (or weighted Sobolev) spaces

(2) $\mathcal{K}_{a}^{m}(M)\,:=\,\\{r^{\alpha_{1}-a}\partial^{\alpha}u\in
L^{2}(M),\,|\alpha|\leq m\\}$

with $a=\dim(\overline{M})/2$. These function spaces (for all $a$) arise
naturally if we study the manifold with conical points $\overline{M}/\sim$,
where $\sim$ collapses each component of $\partial\overline{M}$ to a point.

Let us now turn to the definition of _differential operators._ Assume, first
that $\overline{M}=[0,\infty)\times\mathbb{R}^{n}\ni(r,x^{\prime})$ and let
$\alpha=(\alpha_{1},\alpha_{2},\ldots,\alpha_{n})=(\alpha_{1},\alpha^{\prime})\in\mathbb{Z}_{+}^{n+1}$
be a generic multi-index. Then the “right differential operators” for the
cylindrical ends geometry are the _totally characteristic differential
operators_ $P$ of the form

(3) $P\,=\,\sum_{|\alpha|\leq
m}a_{\alpha}(r,x^{\prime})(r\partial_{r})^{\alpha_{1}}\partial_{x^{\prime}}^{\alpha^{\prime}}\,.$

Let us endow $M$ with the metric $\frac{(dr)^{2}}{r^{2}}+(dx^{\prime})^{2}$.
Then, the Laplacian for this metric is a totally characteristic differential
operator. Furthermore, after the Kondratiev transform $r=e^{t}$, this metric
becomes just the usual Euclidean metric on
$\mathbb{R}^{n+1}\ni(t,x^{\prime})$. On the other hand, the differential
operator $P$ becomes

(4) $P\,=\,\sum_{|\alpha|\leq
m}a_{\alpha}(e^{t},x^{\prime})\partial_{t}^{\alpha_{1}}\partial_{x^{\prime}}^{\alpha^{\prime}}\,,$

which has the property that its coefficients have limits
$a_{\alpha}(0,x^{\prime})$ as $t\to-\infty$. This leads us to an important new
ingredient, namely the “$b$-normal” (simply, “normal”) operator

(5) $\tilde{P}\,:=\,\sum_{|\alpha|\leq
m}a_{\alpha}(0,x^{\prime})\partial_{t}^{\alpha_{1}}\partial_{x^{\prime}}^{\alpha^{\prime}}\,,$

obtained by “freezing the coefficients” at $t=-\infty$. The normal operator is
an important instance of a “limit operator” mentioned earlier. (Notice that
$r\partial_{r}$ was replaced with $\partial_{t}$, so we have used the
Kondratiev transform implicitly.) The Fourier transform in $t$ then yields the
_indicial family_
$\widehat{P}(\tau):=\sum_{\alpha}a_{\alpha}(0,x^{\prime})(i\tau)^{\alpha_{1}}\partial_{x^{\prime}}^{\alpha^{\prime}}\,.$
Similar constructions ($\tilde{P}$ and $\widehat{P}$) can be defined on any
manifold with cylindrical ends by localization, and we obtain a normal
operator for each connected component $L$ of the boundary
$\partial\overline{M}$ of $\overline{M}$. We have the following (almost
classical) result [8, 12, 17]:

######  Theorem 2.2.

Let $D$ be an order $m$, totally characteristic differential operator on
$\overline{M}$. The map $D:H^{s}(M;E,g_{cyl})\to H^{s-m}(M;F,g_{cyl})$ is
Fredholm if, and only if,

  1. (i)

it is elliptic and

  2. (ii)

all its normal operators are invertible $H^{s}(L;E)\to H^{s-m}(L;F)$.

An approach to the analysis on manifolds with cylindrical ends is via the
$b$-calculus of Melrose [11] and Schulze [17]. See also [9].

Figure 1. The construction of a manifold with cylindrical ends.

##  3\. Fredholm operators on manifolds with nice ends (Lie manifolds)

The Laplace operator in cylindrical coordinates in $\mathbb{R}^{3}$ or the
Schrödinger operators with singular potentials of the form $Z\rho^{-2\gamma}$,
$\gamma\in\mathbb{R}_{+}\smallsetminus\\{0,1/2,1\\}$, do not fit into the
framework of manifolds with cylindrical ends. This raises the question of
defining compatible pseudodifferential calculi and obtaining the associated
Fredholm alternative (or Fredholm conditions) on more general manifolds. It
does not seem possible to obtain convenient characterizations of Fredholm
operators on general non-compact manifolds. We will thus restrict ourselves to
a class of non-compact manifolds, which we will call “nice manifolds” for the
purpose of this paper. This class of manifolds consists of manifolds with nice
ends and are, for the most part, “Lie manifolds,” a class of manifolds that we
introduce next. While we do not define precisely which manifolds are nice
(this is rather technical, see [3, 4]), we do discuss several examples, among
which the ones mentioned in the introduction, namely manifolds with
(asymptotically): cylindrical ends, hyperbolic ends, and Euclidean ends.

###  3.1. Lie manifolds

We now introduce and discuss Lie manifolds, their geometry, and, most
importantly, their _associated differential operators._

####  3.1.1. Definition of Lie manifolds

Assume that we are given a compact manifold with corners $\overline{M}$, whose
interior is $M:=\overline{M}\smallsetminus\partial\overline{M}$, and a
subspace

(6)
$\mathcal{V}\subset\mathcal{V}_{b}(\overline{M})\,:=\,\\{X\in\mathcal{C}^{\infty}(\overline{M};T\overline{M})\mid
X\mbox{ \emph{tangent} to all faces of }\overline{M}\\}\,.$

######  Definition 3.1 ([1]).

The pair $(\overline{M},\mathcal{V})$ is a Lie manifold if:

  1. (i)

$\mathcal{V}\subset\mathcal{V}_{b}(\overline{M})$ is closed under the Lie
bracket $[\;,\;]$;

  2. (ii)

$\mathcal{V}$ is a finitely-generated, projective
$\mathcal{C}^{\infty}(\overline{M})$–module;

  3. (iii)

$\mathcal{C}^{\infty}_{c}(M;TM)\subset\mathcal{V}$ (recall that
$M:=\overline{M}\smallsetminus\partial\overline{M}$).

This definition is based on earlier, similar constructions due to Connes,
Cordes, Kondratiev, Mazzeo, Mazya, Melrose, Plamenevskij (a relevant old
article with Mazya is described in [14]), Schrohe, Schulze, Skandalis, and
many others. Informally, a Lie manifold $(\overline{M},\mathcal{V})$ is a
manifold $M$ with:

  1. (i)

a _compactification_ $\overline{M}$ such that
$M=\overline{M}\smallsetminus\partial\overline{M},$ whose role is to control
the behavior at infinity of the coefficients of our differential operators,
and

  2. (ii)

a _Lie algebra_ of vector fields $\mathcal{V}\subset\mathcal{V}_{b}$ on this
compactification, whose role is to define the “nice” differential operators.

######  Remark 3.2.

Let $(\overline{M},\mathcal{V})$ be a Lie manifold. Saying that $\mathcal{V}$
is a projective $\mathcal{C}^{\infty}(\overline{M})$-module means that it is
stable under multiplication by functions in
$\mathcal{C}^{\infty}(\overline{M})$ and it has a basis around each point of
$\overline{M}.$ In particular, $\mathcal{V}$ is a complex vector space. Saying
that $\mathcal{C}^{\infty}_{c}(M;TM)\subset\mathcal{V}$ means that there are
no “obstructions in the interior” for the vector fields in $\mathcal{V}$.
Compact (smooth) manifolds and manifolds with cylindrical ends are Lie
manifolds. These and other examples will be discussed below in Section 3.3.

####  3.1.2. Lie manifolds and geometry

As in [1], since $\mathcal{V}$ is a projective
$\mathcal{C}^{\infty}(\overline{M})$-module, the Serre-Swan theorem gives the
existence of a vector bundle $A\to\overline{M}$ such that

(7) $\mathcal{V}\simeq\Gamma(\overline{M};A)\,.$

The Lie algebra structure on the sections of $A$ means that it is a _Lie
algebroid_. The inclusion $\mathcal{C}^{\infty}_{c}(M;TM)\subset\mathcal{V}$
means that $A=TM$ in the interior
$M:=\overline{M}\smallsetminus\partial\overline{M}$ of $\overline{M}$. Thus,
once we have chosen a metric on $A$, that metric will induce a metric on $TM$
(or, which is the same thing, on $M$). A metric obtained in this way will be
called _compatible_ , and is unique up to Lipschitz equivalence. For a smooth
bundle $E\to\overline{M}$, we define the Sobolev spaces $H^{s}(M;E)$ using the
powers of the Laplacian for any compatible metric.

####  3.1.3. Differential operators

Our main interest lies in the algebra

$\operatorname{Diff}_{\mathcal{V}}(\overline{M}),$

which consists of the differential operators generated by
$\mathcal{C}^{\infty}(\overline{M})$ and by derivatives in $\mathcal{V}$.
Given two vector bundles $E,F\to\overline{M}$, we have a similar definition of
$\operatorname{Diff}_{\mathcal{V}}(\overline{M};E,F)$, the set of differential
operators generated by
$\mathcal{C}^{\infty}(\overline{M};\operatorname{Hom}(E;F))$ and $\mathcal{V}$
acting on sections of $E$ with values sections of $F$. All the geometric
operators on $M$ with a compatible metric will belong to some space of the
form $\operatorname{Diff}_{\mathcal{V}}(\overline{M};E,F)$. For instance, the
Levi-Civita connection on $M$ extends to a differential operator in
$\operatorname{Diff}_{\mathcal{V}}(\overline{M};A,A^{*}\otimes A)$ (an
$A$-connection). Hence, since $\overline{M}$ is compact, its interior $M$ will
have bounded curvature (together with its covariant derivatives).

###  3.2. Formulation of the main result: Fredholm conditions on “nice”
manifolds

We are now closer to giving a precise statement for the Fredholm conditions in
theorem 1.1. Let $(\overline{M},\mathcal{V})$ be a Lie manifold and
$D\in\operatorname{Diff}_{\mathcal{V}}(\overline{M};E,F)$. If $D$ has order
$m$, then it defines a continuous map $D:H^{s}(M;E)\to H^{s-m}(M;F)$. To
$(\overline{M},\mathcal{V})$ and $D$ we associate:

  1. (i)

spaces $Z_{\alpha}$, $\alpha\in I$, the _orbits_ of $\mathcal{V}$ on
$\overline{M}$ (they do not dependent on $D$);

  2. (ii)

isotropy groups $G_{\alpha}$, $\alpha\in I$, (also independent of $D$); and

  3. (iii)

$G_{\alpha}$-invariant differential operator $D_{\alpha}$ on $Z_{\alpha}\times
G_{\alpha}$

as follows. Let ${\mathcal{V}_{x}}:=\\{X\in\mathcal{V}|\,X(x)=0\\}$ and
${I_{x}}:=\\{f\in\mathcal{C}^{\infty}(\overline{M})|\,f(x)=0\\},$ for
$x\in\partial\overline{M}$. Then $\mathcal{V}_{x}/I_{x}\mathcal{V}$ is a Lie
algebra and, for $x\in Z_{\alpha}$, $G_{\alpha}$ is the simply-connected Lie
group that integrates it:

$Lie(G_{\alpha})\,=\,{\mathcal{V}_{x}/I_{x}\mathcal{V}}\,.$

For each $\alpha\in I$, the operator $D_{\alpha}$ is obtained by restricting
$D$ to the orbit $Z_{\alpha}$ and letting the vector fields act on
$G_{\alpha}$ via the map $\mathcal{V}_{x}\to Lie(G_{\alpha})$. The operators
$D_{\alpha}$ are the _limit operators_. We can now formulate our main result
[3, 4]

######  Theorem 3.3.

Let $D\in\operatorname{Diff}_{\mathcal{V}}(\overline{M};E,F)$ be of order $m$
and assume that $(\overline{M},\mathcal{V})$ is “nice.” We have that
$D:H^{s}(M;E)\to H^{s-m}(M;F)$ is Fredholm if, and only if, $D$ is elliptic
and all $D_{\alpha}$, $\alpha\in I$, are invertible.

Our Lie manifold $(M,\mathcal{V})$ is _nice_ if there exists a _Hausdorff_ Lie
groupoid $\mathcal{G}$ such that

  * •

its Lie algebroid $A(\mathcal{G})\simeq A$ of Equation (7) (so
$\Gamma(\overline{M};A)=\mathcal{V}$) and

  * •

$\mathcal{G}$ satisfies the Effros-Hahn conjecture (a statement about
$C^{*}(\mathcal{G})$ that implies that the regular representations of
$C^{*}(\mathcal{G})$ determine its invertible elements).

The proof is obtained by considering the norm closure
$\overline{\Psi}^{0}(\mathcal{G})$ of the algebra of order zero
pseudodifferential operators on $\mathcal{G}$ [3, 4]. Let $\mathcal{K}$ be the
algebra of compact operators on $L^{2}(M)$. Recall that an operator is
Fredholm if, and only if, it is invertible modulo $\mathcal{K}$. We thus want
to characterize the invertible elements of
$\overline{\Psi}^{0}(\mathcal{G})/\mathcal{K}$. Since
$\overline{\Psi}^{0}(\mathcal{G})/C^{*}(\mathcal{G})\simeq\mathcal{C}(S^{*}A)$
via the principal symbol and $\mathcal{G}$ satisfies the the Effros-Hahn
conjecture, in addition to the principal symbol, it is enough to look at the
regular representations of $C^{*}(\mathcal{G})/\mathcal{K}$. Each of these
regular representations yields a limit operator. This completes the proof. A
useful property here is that nice manifolds are closed under general blow-ups
[3, 4].

Figure 2. Various types of singular spaces or domains that can be treated
using blow-ups and Lie manifolds and an example of a non-compact manifold that
has three types of ends: cylindrical, hyperbolic, and Euclidean.

###  3.3. Examples and applications

The example “zero” is that of a smooth, compact manifold without boundary $M$.
Then $M$ is a Lie manifold with $\overline{M}=M$ and
$\mathcal{V}=\Gamma(M;TM)$ (all smooth vector fields on $M$). In particular,
we have $A=TM$. The boundary $\partial\overline{M}:=\overline{M}\smallsetminus
M$ is empty, which is consistent with the fact that there are no limit
operators. Then Theorem 3.3 becomes simply the (well known) Theorem 2.1. Thus
the example of compact manifolds, while it fits our setting, is too simple to
illustrate the general theory, and hence we will concentrate next on other,
more relevant examples. In all our following examples, $\overline{M}$ will be
a smooth, compact manifold with boundary $\partial\overline{M}$ and we shall
concentrate on a tubular neighborhood
$U=[0,\epsilon)\times\partial\overline{M}\ni({r},y)$ of the boundary, because
the interior $M:=\overline{M}\smallsetminus\partial\overline{M}$ can be
treated with classical tools. Here are our main three examples:

  1. (i)

Let $\mathcal{V}:=\mathcal{V}_{b}$, the set of smooth vector fields on
$\overline{M}$ that are _tangent_ to the boundary $\partial\overline{M}$ of
$\overline{M}$, as before. We have
$\mathcal{V}_{b}=\mathcal{C}^{\infty}(\overline{M}){r\partial_{r}}+\sum\mathcal{C}^{\infty}(\overline{M}){\partial_{y}}$
on $U$, so the projectivity condition is satisfied and we obtain a Lie
manifold $(\overline{M},\mathcal{V}_{b})$. Any metric of the form
$g=r^{-2}(dr)^{2}+h$ as in Equation (1) will be compatible (with the Lie
manifold structure) on $M$, and hence $M$ is a _manifold with cylindrical
ends._ The bundle $A={}^{b}TM$ was considered by Melrose. The index set $I$
consists of the connected components of $\partial\overline{M}$ and
$G_{\alpha}=\mathbb{R}$. The differential operators
$\operatorname{Diff}_{\mathcal{V}}(\overline{M})$ are the totally
characteristic differential operators on $\overline{M}$ (already discussed)
and the limit operators $D_{\alpha}$ are the normal operators of $D$ defined
earlier.

  2. (ii)

Let next
$\mathcal{V}:=\mathcal{V}_{0}:=r\mathcal{C}^{\infty}(\overline{M};T\overline{M})$,
the set of smooth vector fields on $\overline{M}$ that _vanish_ at the
boundary $\partial\overline{M}$ of $\overline{M}$. Then
$\mathcal{V}_{0}=\mathcal{C}^{\infty}(\overline{M}){r\partial_{r}}+\sum\mathcal{C}^{\infty}(\overline{M}){r\partial_{y}}$
on $U$, so the projectivity condition is satisfied and, again,
$(\overline{M},\mathcal{V}_{0})$ is a Lie manifold. The choice of a metric on
$A$ (a compatible metric on $M$) makes the interior
$M:=\overline{M}\smallsetminus\partial\overline{M}$ of $\overline{M}$ a so
called asymptotically hyperbolic manifold, since the metric is of the form
$g=\frac{h}{{r^{2}}}$ with $h$ a true metric on $\overline{M}$. The orbits
$Z_{\alpha}\subset\partial\overline{M}$ are reduced to points (so
$I=\partial\overline{M}$) and
$G_{\alpha}=T_{\alpha}\partial\overline{M}{\rtimes}\mathbb{R}$, which is a
_non-commutative_ group (obtained as the semi-direct product from the action
of $\mathbb{R}$ on $T_{\alpha}\partial\overline{M}$ by dilations).

  3. (iii)

To round up our podium, let
$\mathcal{V}\,:=\,\mathcal{V}_{sc}\,:=\,r\mathcal{V}_{b}\subset\mathcal{V}_{0}$.
From example (i), we see that
$\mathcal{V}_{sc}\,:=\,\mathcal{C}^{\infty}(\overline{M}){r^{2}\partial_{r}}+\sum\mathcal{C}^{\infty}(\overline{M}){r\partial_{y}}$
on $U$, so the projectivity condition is yet again satisfied to yield a Lie
manifold $(\overline{M},\mathcal{V}_{sc})$. Euclidean, asymptotically
Euclidean, and asymptotically conical spaces are modeled by this type of Lie
manifolds. The orbits $Z_{\alpha}=\\{\alpha\\}$ are again reduced to points
(so again $I=\partial\overline{M}$). However, this time,
$G_{\alpha}=T_{\alpha}\partial\overline{M}{\times}\mathbb{R}$ is
_commutative._

The Laplacian
$\Delta_{\mathbb{R}^{3}}u=r^{-2}\big{[}(r\partial_{r})^{2}u+\partial_{\theta}^{2}u+(r\partial_{z})^{2}u\big{]}$
in cylindrical coordinates $(r,\theta,z)\in[0,\infty)\times
S^{1}\times\mathbb{R}$ is closely related to the example (ii) above. Ignoring
the factor $r^{-2}$, the relevant operator is generated by the vector fields
$r\partial_{r},$ $\partial_{\theta},$ and $r\partial_{z},$ which are again
tangent to the boundary. This example was one of the original motivations to
considering a framework more general than that of manifolds with cylindrical
ends.

We conclude this section with an example that goes even beyond Lie manifolds.
Namely, let us we consider the Schrödinger operator with potential
$V=\rho^{-2\gamma}V_{0}$, with $V_{0}$ _smooth in generalized spherical
coordinates_ $(\rho,x^{\prime})$, $\rho\in[0,\infty)$, $x^{\prime}\in
S^{n-1}$, and $\gamma\geq 0$:

(8)
$\Delta+V\,=\,\rho^{-2}\big{[}(\rho\partial_{\rho})^{2}+(n-2)\rho\partial_{\rho}+\Delta_{S^{n-1}}+\rho^{2-2\gamma}V_{0}\big{]}$

Let us assume first that $2\gamma\in\\{0,1,2\\}$. Ignoring the factor
$\rho^{-2}$, the resulting operator

(9)
$(\rho\partial_{\rho})^{2}+(n-2)\rho\partial_{\rho}+\Delta_{S^{n-1}}+\rho^{2-2\gamma}V_{0}$

is in the $b$-calculus [11, 17]. This property can be used, among other
applications, to study the domain of $\Delta+V$ and the regularity of its
eigenfunctions. If $2\gamma\in\mathbb{R}\smallsetminus\\{0,1,2\\}$, the
operator $\Delta+V$ can still be studied with a modified pseudodifferential
calculus [3]. For instance, if $\gamma>1$ and if we write
$\Delta+V=\rho^{-2\gamma}\big{[}(\rho^{\gamma}\partial_{\rho})^{2}+(n-1-\gamma)\rho^{\gamma-1}\rho^{\gamma}\partial_{\rho}+\rho^{2\gamma-2}\Delta_{S^{n-1}}+V_{0}\big{]},$
then the resulting operator

(10)
$(\rho^{\gamma}\partial_{\rho})^{2}+(n-1-\gamma)\rho^{\gamma-1}\rho^{\gamma}\partial_{\rho}+\rho^{2\gamma-2}\Delta_{S^{n-1}}+V_{0}$

is in the $c_{\gamma,\gamma-1}$-calculus of [3] (recall that $V_{0}$ is smooth
in polar coordinates).

Other examples come from semi-Riemannian and sub-Riemannian geometry [2].

##  4\. Pseudodifferential operators and problems

Work related to the algebras $\Psi^{\infty}(\mathcal{G})$ used in the proof of
our main result was done by Androulidakis, Connes, Debord, Mazzeo, Melrose,
Monthubert, Ruzhansky, Schrohe, Schulze, Skandalis, and many others. See [1,
5, 6, 10, 15, 16] for references. In that case, $\Psi^{-\infty}(\mathcal{G})$
is the algebra generated by the conormal distributions of order $-\infty$ on
$A\to M$. In turn, $\Psi^{m}(\mathcal{G})$ is linearly generated by the
conormal distributions of order $m$ on $A\to M$ and by
$\Psi^{-\infty}(\mathcal{G}).$ A generalization of these algebras in contained
in [3]. In the case of manifolds with cylindrical ends, we have
$\mathcal{V}=\mathcal{V}_{b}$ and $\Psi^{\infty}(\mathcal{G})$ consists of the
properly supported operators in the $b$-calculus of Melrose and Schulze (and
hence, it is a dense algebra in a suitable topology). Similarly, for
asymptotically hyperbolic manifolds, $\mathcal{V}=\mathcal{V}_{0}$ and
$\Psi^{\infty}(\mathcal{G})$ consists of the properly supported operators in
the $0$-calculus of Mazzeo and Schulze. Finally, for asymptotically euclidean
manifolds, $\mathcal{V}=\mathcal{V}_{sc}$ and $\Psi^{\infty}(\mathcal{G})$
consists of the properly supported operators in the $SG$-calculus of Parenti
and Schrohe, the same calculus as the “scattering calculus” of Melrose.

###  4.1. Problems

We conclude by formulating two problems.

######  Problem 4.1 (Connes, Bohlen-Schrohe).

Find the index of a Fredholm operator $D\in\Psi^{m}(\mathcal{G}).$

######  Problem 4.2 (Baldare-Benameur-Lesch-V.N., Ruzhansky).

Let $G$ be a compact Lie group. Let $M$ be compact smooth connected with a $G$
action and $E$ be a $G$-bundle. Let $\overline{M}$ be the Albin-Melrose
compactification of the principal orbit bundle (for the $G$) action and
$\mathcal{G}$ be its Lie groupoid. Describe $\Psi^{m}(M;E)^{G}$ using
$\Psi^{m}(\mathcal{G})$ and the Ruzhansky calculus.

## References

  * [1] Ammann, B., Lauter, R., and Nistor, V. On the geometry of Riemannian manifolds with a Lie structure at infinity.  Int. J. Math. Math. Sci., 1-4 (2004), 161–193.
  * [2] Beschastnyi, I. Closure of the Laplace-Beltrami operator on 2d almost-Riemannian manifolds and semi-Fredholm properties of differential operators on Lie manifolds.  Result. Math. 78, 2 (2023), 56.  Id/No 59.
  * [3] Beschastnyi, I., Carvalho, C., Nistor, V., and Qiao, Y. Title.  Work in progress.
  * [4] Carvalho, C., Nistor, V., and Qiao, Y. Fredholm conditions on non-compact manifolds: theory and examples.  In Operator theory, operator algebras, and matrix theory, vol. 267 of Oper. Theory Adv. Appl. Birkhäuser/Springer, Cham, 2018, pp. 79–122.
  * [5] Connes, A. Noncommutative geometry.  Academic Press, San Diego, 1994.
  * [6] Debord, C., and Skandalis, G. Adiabatic groupoid, crossed product by $\mathbb{R}_{+}^{\ast}$ and pseudodifferential calculus.  Adv. Math. 257 (2014), 66–91.
  * [7] Grosse, N., Mirela, K., and Nistor, V. The l2-unique continuation property on manifolds with bounded geometry and the deformation operator.  Preprint 2023.
  * [8] Kondrat′ev, V. A. Boundary value problems for elliptic equations in domains with conical or angular points.  Transl. Moscow Math. Soc. 16 (1967), 227–313.
  * [9] Lauter, R., and Seiler, J. Pseudodifferential analysis on manifolds with boundary - a comparison of $b$-calculus and cone algebra.  In Oper. Theory Adv. Appl., vol. 125 of Adv. Partial Differ. Equ. 2001, pp. 131–166.
  * [10] Mazzeo, R. Elliptic theory of differential edge operators. I.  Commun. Partial Differ. Equations 16, 10 (1991), 1615–1664.
  * [11] Melrose, R. The Atiyah-Patodi-Singer index theorem. Research Notes in Mathematics (Boston, Mass.). 4. Wellesley, MA: A. K. Peters, Ltd.. xiv, 377 p. , 1993.
  * [12] Melrose, R., and Mendoza, G. Elliptic operators of totally characteristic type.  MSRI Preprint.
  * [13] Mitrea, M., and Taylor, M. Boundary layer methods for Lipschitz domains in Riemannian manifolds.  J. Funct. Anal. 163, 2 (1999), 181–251.
  * [14] Nazarov, S. A., and Plamenevsky, B. A. Elliptic problems in domains with piecewise smooth boundaries, vol. 13 of de Gruyter Expositions in Mathematics.  Walter de Gruyter & Co., Berlin, 1994.
  * [15] Ruzhansky, M., and Turunen, V. Pseudo-differential operators and symmetries, vol. 2 of Pseudo-Differential Operators. Theory and Applications.  Birkhäuser Verlag, Basel, 2010.  Background analysis and advanced topics.
  * [16] Schrohe, E. Fréchet algebra techniques for boundary value problems on noncompact manifolds: Fredholm criteria and functional calculus via spectral invariance.  Math. Nachr. 199 (1999), 145–185.
  * [17] Schulze, B.-W. Pseudo-differential operators on manifolds with singularities, vol. 24 of Studies in Mathematics and its Applications.  North-Holland Publishing Co., 1991.