# Obstacle Avoidance via Hybrid Feedback

S. Berkane, A. Bisoffi, , D. V. Dimarogonas This research work is partially
supported by NSERC-DG RGPIN-2020-04759, the European Research Council (ERC),
the EU H2020 Co4Robots, the SSF COIN project, the Swedish Research Council
(VR) and the Knut och Alice Wallenberg Foundation. S. Berkane
<EMAIL_ADDRESS>is with the Department of Computer Science and
Engineering, University of Quebec in Outaouais, Gatineau, Canada. A. Bisoffi
<EMAIL_ADDRESS>is with ENTEG and the J.C. Willems Center for Systems and
Control, University of Groningen, Groningen, The Netherlands. D. V.
Dimarogonas<EMAIL_ADDRESS>is with the Division of Decision and Control
Systems, KTH Royal Institute of Technology, Stockholm, Sweden.

###### Abstract

In this paper we present a hybrid feedback approach to solve the navigation
problem of a point mass in the $n-$dimensional space containing an arbitrary
number of ellipsoidal shape obstacles. The proposed hybrid control algorithm
guarantees both global asymptotic stabilization to a reference and avoidance
of the obstacles. The intuitive idea of the proposed hybrid feedback is to
switch between two modes of control: stabilization and avoidance. The
geometric construction of the flow and jump sets of the proposed hybrid
controller, exploiting hysteresis regions, guarantees Zeno-free switching
between the stabilization and the avoidance modes. Simulation results
illustrate the performance of the proposed hybrid control approach for
2-dimensional and 3-dimensional scenarios.

##  I Introduction

For decades, the obstacle avoidance problem has been an active area of
research in the robotics and control communities [1]. In a typical robot
navigation scenario, the robot is required to reach a given goal (destination)
while not colliding with a set of obstacle regions in the workspace. Since the
pioneering work by Khatib [2], artificial potential fields have been widely
used in the obstacle avoidance problem since they offer the possibility to
combine the solution to the global find-path problem with a feedback
controller for the robot, thus, allowing the high-level planner to address
more abstract tasks. The idea is to generate an artificial potential field
that renders the goal attractive and the obstacles repulsive. Then, by
considering trajectories that navigate along the negative gradient of the
artificial potential field, one can ensure that the robot will reach the
desired target while avoiding to collide with the obstacles. However,
artificial potential field-based algorithms suffer from 1) the presence of
local minima preventing the successful navigation to the target point and 2)
arbitrarily large repulsive potential near the obstacles which are in conflict
with the inevitable actuator saturations.

The navigation function-based approach, which was initiated by Koditscheck and
Rimon [3] for sphere worlds [3, p. 414], solves both problems. It allows to
obtain artificial potential fields with the nice property that all but one of
the critical points are saddles with the remaining critical point being the
desired reference. Since then, the navigation function-based approach has been
extended in many different directions; e.g., for multi-agent systems [4, 5,
6], for unknown sphere words [7], and for focally admissible obstacles [8].
The major drawback of navigation functions is that they are not correct by
construction. In fact, navigation functions are theoretically guaranteed to
exist, but their explicit computation is not straightforward since they
require an unknown tuning of a given parameter to eliminate local minima.

Recently, Loizou [9] introduced the navigation transform that
diffeomorphically maps the workspace to a trivial domain called the point
world consisting of a closed ball with a finite number of points removed. Once
this transformation is found, the navigation problem is solved from almost all
initial conditions without requiring any tuning. In addition, the trajectory
duration is explicitly available, which provides a timed-abstraction solution
to the motion-planning problem. Similarly, the recent work in [10] uses the
so-called prescribed performance control to design a time-varying control law
that drives the robot, in finite time, from all initial conditions to some
neighborhood of the target while avoiding the obstacles. Another approach to
the navigation problem is through barrier functions (see [11] and references
therein), which are developed for nonlinear systems with state-space
constraints and ensure safety. Model predictive control approaches have been
also used for reactive robot navigation, e.g., [12, 13].

However, by using any of the approaches described above, it is not possible to
ensure safety from all initial conditions in the obstacle-free state space. As
pointed out in [3], the appearance of additional undesired equilibria is
unavoidable when considering continuous time-invariant vector fields. This is
a well known topological obstruction to global asymptotic stabilization by
continuous feedback when the free state space is not diffeomorphic to an
Euclidean space (see, e.g., [14, Thm. 2.2]). Furthermore, this problem is more
far-reaching since, by using a continuous feedback law, it is always possible
to find arbitrarily small adversarial (noise) signals acting on the vector
field, such that a set of initial conditions different from the target,
possibly of measure zero, can be rendered stable [15, Thm. 6.5]. To deal with
such limitations, the authors in [16] proposed a hybrid state feedback
controller, using Lyapunov-based hysteresis switching, to achieve robust
global asymptotic regulation in $\mathbb{R}^{2}$ to a target while avoiding a
single obstacle. This approach has been exploited in [17] to steer a planar
vehicle to the source of an unknown but measurable signal while avoiding an
obstacle. In [18] and [19], a hybrid control law was proposed to globally
asymptotically stabilize a class of linear systems while avoiding
neighbourhoods of unsafe isolated points in $\mathbb{R}^{n}$. Although such
hybrid approaches are promising, they are still challenged by constructing the
suitable hybrid feedback for higher dimensions and with more complex obstacles
shapes.

In this work, we propose a hybrid control algorithm for the global asymptotic
stabilization of a point mass moving in an arbitrary $n-$dimensional space
while safely avoiding obstacles that have generic ellipsoidal shapes, based on
the preliminary treatment of this problem for a single spherical obstacle in
[20]. The ellipsoids provide a tighter bounding volume than spheres, and in
our scheme this volume can be arbitrarily flat and close to the target, which
leads to a significant reduction in the level of conservatism compared, for
instance, to [21, Thm. 3] (as shown in Section VI).

Our proposed hybrid algorithm employs a hysteresis-based switching between the
avoidance controller and the stabilizing controller in order to guarantee
forward invariance of the obstacle-free region (corresponding to safety) and
global asymptotic stability of the reference position. We consider
trajectories in an $n-$dimensional Euclidean space and we resort to tools from
higher-dimensional geometry [22] to provide a construction of the flow and
jump sets where the different modes of operation of the hybrid controller are
activated. Furthermore, the hybrid control law guarantees a bounded control
input, it matches the stabilizing controller in arbitrarily large subsets of
the obstacle-free region by a suitable tuning of its parameters (hence
qualifying as minimally invasive), it can be readily extended to a non-point
mass vehicle and enjoys some level of inherent robustness to perturbations.
_Structure._ Preliminaries are in Section II. The navigation problem is
formulated in Section III. Our proposed hybrid control scheme is discussed in
Section IV. Section V presents the main result of forward invariance of the
obstacle-free space and global asymptotic stability of the target, together
with other desirable complementary properties. Numerical examples are in
Section VI. All the proofs are in the Appendix.

##  II Preliminaries

$\mathbb{N}$, $\mathbb{R}$ and $\mathbb{R}_{\geq}$ denote, respectively, the
set of nonnegative integers, reals and nonnegative reals. $\mathbb{R}^{n}$ is
the $n$-dimensional Euclidean space and $\mathbb{S}^{n}$ is the
$n$-dimensional unit sphere embedded in $\mathbb{R}^{n+1}$. Given the column
vectors $v_{1}\in{}^{n_{1}}$ and $v_{2}\in{}^{n_{2}}$, $(v_{1},v_{2})$ denotes
the stack vector
$\begin{bmatrix}v_{1}^{\top}&v_{2}^{\top}\end{bmatrix}^{\top}$. The Euclidean
norm of $x\in\mathbb{R}^{n}$ is defined as $\|x\|:=\sqrt{x^{\top}x}$ and the
geodesic distance between two points $x$ and $y$ on the sphere
$\mathbb{S}^{n}$ is defined by
$\mathbf{d}_{\mathbb{S}^{n}}(x,y):=\arccos(x^{\top}y)$ for all
$x,y\in\mathbb{S}^{n}$. For an arbitrary matrix $A\in\mathbb{R}^{n\times n}$,
$\lambda_{i}(A)$ denotes the $i$-th eigenvalue of $A$. If $A$ is a symmetric
matrix, then $\lambda_{\min}(A)$ and $\lambda_{\max}(A)$ denote, respectively,
the smallest and largest eigenvalues of $A$. Given a closed set
$\mathcal{A}\subset\mathbb{R}^{n}$, we define the distance to the set
$\mathcal{A}$ by $|x|_{\mathcal{A}}:=\inf_{y\in\mathcal{A}}\|x-y\|$. Given two
sets $\mathcal{A}$ and $\mathcal{B}$, we define the distance from
$\mathcal{A}$ to $\mathcal{B}$ by
$\mathbf{dist}(\mathcal{A},\mathcal{B}):=\inf\\{|a-b|\colon
a\in\mathcal{A},b\in\mathcal{B}\\}$. The closure, interior and boundary of a
set $\mathcal{A}\subset\mathbb{R}^{n}$ are denoted as
$\overline{\mathcal{A}},\mathcal{A}^{\circ}$ and $\partial\mathcal{A}$,
respectively. The relative complement of a set
$\mathcal{B}\subset\mathbb{R}^{n}$ with respect to a set $\mathcal{A}$ is
denoted by $\mathcal{A}\backslash\mathcal{B}$ and contains the elements of
$\mathcal{A}$ which are not in $\mathcal{B}$. In particular, we use
$\mathcal{A}^{\mathsf{c}}$ to denote the complement of $\mathcal{A}$ in
$\mathbb{R}^{n}$, i.e.,
$\mathcal{A}^{\mathsf{c}}=\mathbb{R}^{n}\backslash\mathcal{A}$. Given the sets
$\mathcal{A}$, $\mathcal{B}$ and $\mathcal{C}$, the following set identities
[23] will be used

$\displaystyle\\!\\!\\!\mathcal{A}\cup(\mathcal{B}\cap\mathcal{C})=(\mathcal{A}\cup\mathcal{B})\cap(\mathcal{A}\cup\mathcal{C})$
(1a)
$\displaystyle\\!\\!\\!\mathcal{A}\cap(\mathcal{B}\cup\mathcal{C})=(\mathcal{A}\cap\mathcal{B})\cup(\mathcal{A}\cap\mathcal{C})$
(1b)
$\displaystyle\\!\\!\\!(\mathcal{A}\cap\mathcal{C})\backslash(\mathcal{B}\cap\mathcal{C})=(\mathcal{A}\cap\mathcal{C})\backslash\mathcal{B}=\mathcal{A}\cap(\mathcal{C}\backslash\mathcal{B})$
(1c)
$\displaystyle\\!\\!\\!\mathcal{C}\backslash(\mathcal{A}\\!\cup\\!\mathcal{B})\\!=\\!(\mathcal{C}\backslash\mathcal{A})\\!\cap\\!(\mathcal{C}\backslash\mathcal{B}),\mathcal{C}\backslash(\mathcal{A}\\!\cap\\!\mathcal{B})\\!=\\!(\mathcal{C}\backslash\mathcal{A})\\!\cup\\!(\mathcal{C}\backslash\mathcal{B})$
(1d)
$\displaystyle\\!\\!\\!(\mathcal{A}\cup\mathcal{B})^{\mathsf{c}}\\!=\\!\mathcal{A}^{\mathsf{c}}\\!\cap\\!\mathcal{B}^{\mathsf{c}},(\mathcal{A}\cap\mathcal{B})^{\mathsf{c}}\\!=\\!\mathcal{A}^{\mathsf{c}}\\!\cup\\!\mathcal{B}^{\mathsf{c}},\mathcal{A}\backslash\mathcal{B}\\!=\\!\mathcal{A}\\!\cap\\!\mathcal{B}^{\mathsf{c}}$
(1e)
$\displaystyle\\!\\!\\!\overline{\mathcal{A}\cup\mathcal{B}}=\overline{\mathcal{A}}\cup\overline{\mathcal{B}},\,\overline{\mathcal{A}\cap\mathcal{B}}\subset\overline{\mathcal{A}}\cap\overline{\mathcal{B}},\,\mathcal{A}\backslash\overline{\mathcal{A}^{\mathsf{c}}}=\mathcal{A}^{\circ}$
(1f)
$\displaystyle\\!\\!\\!\mathcal{A}\subset\mathcal{B}\implies\overline{\mathcal{A}}\subset\overline{\mathcal{B}},\quad\partial\mathcal{A}^{\mathsf{c}}=\partial\mathcal{A}$
(1g)
$\displaystyle\\!\\!\\!\partial(\mathcal{A}\cup\mathcal{B})\subset(\partial\mathcal{A}\backslash\mathcal{B}^{\circ})\cup(\partial\mathcal{B}\backslash\mathcal{A}^{\circ})$
(1h)
$\displaystyle\\!\\!\\!\partial(\mathcal{A}\cap\mathcal{B})\subset(\partial\mathcal{A}\cap\overline{\mathcal{B}})\cup(\partial\mathcal{B}\cap\overline{\mathcal{A}}).$
(1i)

Two sets $\mathcal{A}$ and $\mathcal{B}$ are said to be disjoint if
$\mathcal{A}\cap\mathcal{B}=\emptyset$. They are said to be separated if
$\mathcal{A}\cap\overline{\mathcal{B}}=\emptyset=\overline{\mathcal{A}}\cap\mathcal{B}$.
The notion of separated sets is stronger than mere disjointness. If two sets
$\mathcal{A}$ and $\mathcal{B}$ are separated then we have [23, Exercise
1.3.A]

$\displaystyle\partial(\mathcal{A}\cup\mathcal{B})=\partial\mathcal{A}\cup\partial\mathcal{B}.$
(2)

The tangent cone to a set $\mathcal{K}\subset{}^{n}$ at a point $x\in{}^{n}$,
denoted $\mathbf{T}_{\mathcal{K}}(x)$, is defined as in [24, Def. 5.12 and
Fig. 5.4].

###  II-A Projections Maps

For $z\in\mathbb{R}^{n}\backslash\\{0\\}$, we define the following projection
maps:

$\pi^{\parallel}(z):=\tfrac{zz^{\top}}{\|z\|^{2}},\,\pi^{\perp}(z):=\\!I_{n}\\!-\tfrac{zz^{\top}}{\|z\|^{2}},\,\rho(z):=\\!I_{n}\\!-2\tfrac{zz^{\top}}{\|z\|^{2}}$
(3)

where $I_{n}$ is the $n\times n$ identity matrix. The map
$\pi^{\parallel}(\cdot)$ is the parallel projection map, $\pi^{\perp}(\cdot)$
is the orthogonal projection map [22], and $\rho(\cdot)$ is the reflector map
(also called Householder transformation). Consequently, for any
$x\in\mathbb{R}^{n}$, the vector $\pi^{\parallel}(z)x$ corresponds to the
projection of $x$ onto the line generated by $z$, $\pi^{\perp}(z)x$
corresponds to the projection of $x$ onto the hyperplane orthogonal to $z$ and
$\rho(z)x$ corresponds to the reflection of $x$ about the hyperplane
orthogonal to $z$. For $z\in{}^{n}\backslash\\{0\\}$, some useful properties
of these maps follow:

$\displaystyle\pi^{\parallel}(z)z$ $\displaystyle=z,$
$\displaystyle\pi^{\perp}(z)\pi^{\perp}(z)$ $\displaystyle=\pi^{\perp}(z),$
(4a) $\displaystyle\pi^{\perp}(z)z$ $\displaystyle=0,$
$\displaystyle\pi^{\parallel}(z)\pi^{\parallel}(z)$
$\displaystyle=\pi^{\parallel}(z),$ (4b) $\displaystyle\rho(z)z$
$\displaystyle=-z,$ $\displaystyle\rho(z)\rho(z)$ $\displaystyle=I_{n}.$ (4c)

We also define for $z\in{}^{n}\backslash\\{0\\}$ and $\theta\in\real$ the
parametric map

$\displaystyle\pi^{\theta}(z):=\cos^{2}(\theta)\pi^{\perp}(z)-\sin^{2}(\theta)\pi^{\parallel}(z),$
(5)

which can also be written (thanks to
$2\pi^{\perp}(z)-\rho(z)=2\pi^{\parallel}(z)+\rho(z)=I_{n}$) as

$\pi^{\theta}(z)=\tfrac{1}{2}\rho(z)+\tfrac{1}{2}\cos(2\theta)I_{n}.$ (6)

###  II-B Geometric Subsets of $\mathbb{R}^{n}$

####  II-B1 Line

A line is the one-dimensional subset of $\mathbb{R}^{n}$ described by the set

$\displaystyle\mathcal{L}(c,v)$
$\displaystyle:=\\{x\in\mathbb{R}^{n}:x=c+\lambda v,\lambda\in\mathbb{R}\\},$
(7)

which corresponds to the line passing by the point $c\in\mathbb{R}^{n}$ and
with direction parallel to $v\in\mathbb{R}^{n}\backslash\\{0\\}$. If in (7)
$\lambda\geq 0$ (respectively $\lambda\leq 0$), then we obtain the half-line
denoted by $\mathcal{L}_{\geq}(c,v)$ (respectively $\mathcal{L}_{\leq}(c,v)$).

####  II-B2 Hyperplane

A hyperplane is the $(n-1)$-dimensional subset of $\mathbb{R}^{n}$ described
by the set

$\displaystyle\mathcal{P}(c,v)$
$\displaystyle:=\\{x\in\mathbb{R}^{n}:v^{\top}(x-c)=0\\},$ (8)

which corresponds to the hyperplane that passes through a point
$c\in\mathbb{R}^{n}$ and has normal vector
$v\in\mathbb{R}^{n}\backslash\\{0\\}$. The hyperplane $\mathcal{P}(c,v)$
divides the Euclidean space $\mathbb{R}^{n}$ into two closed subsets
$\mathcal{P}_{\geq}(c,v)$ and $\mathcal{P}_{\leq}(c,v)$, which are obtained by
substituting the $=$ in (8) with $\geq$ and $\leq$, respectively.

####  II-B3 Sphere

A sphere is the $(n-1)$-dimensional subset of $\mathbb{R}^{n}$ described by
the set

$\displaystyle\mathcal{S}(c,r)$
$\displaystyle:=\\{x\in\mathbb{R}^{n}:\|x-c\|=r\\}$ (9)

where $c$ is the center of the sphere and $r\in\mathbb{R}_{\geq}$ is its
radius. The closed interior (respectively exterior) of the sphere, also called
a hyperball and denoted by $\mathcal{S}_{\leq}(c,r)$ (respectively
$\mathcal{S}_{\geq}(c,r)$), is obtained from (9) by substituting the $=$ with
$\leq$ (respectively $\geq$).

####  II-B4 Ellipsoid

For a positive definite matrix $E\in\mathbb{R}^{n\times n}$, a ellipsoid is
the $(n-1)$-dimensional subset of $\mathbb{R}^{n}$ described by the set

$\displaystyle\mathcal{E}(c,E)$
$\displaystyle:=\\{x\in\mathbb{R}^{n}:\|E(x-c)\|^{2}=1\\}$ (10)

where $c$ is the center of the ellipsoid and its $i$-th principal semi-axis is
the vector $\lambda_{i}^{-1}(E)v_{i}$, with $v_{i}$ the unit eigenvector
corresponding to the eigenvalue $\lambda_{i}(E)$. The closed interior
(respectively exterior) of the ellipsoid, denoted by $\mathcal{E}_{\leq}(c,E)$
(respectively $\mathcal{E}_{\geq}(c,E)$), is obtained from (10) by
substituting the $=$ with $\leq$ (respectively $\geq$).

###### Definition 1

Two ellipsoids $\mathcal{E}_{\leq}(c_{1},E_{1})$ and
$\mathcal{E}_{\leq}(c_{2},E_{2})$ are weakly disjoint if
$\mathcal{E}_{\leq}(c_{1},E_{1})\cap\mathcal{E}_{\leq}(c_{2},E_{2})=\emptyset$.

Explicit algebraic conditions to test weak disjointness of two ellipsoids can
be found in [25, Thm. 6] for $n=2$ and in [26, Thm. 8] for $n=3$.

###### Definition 2

Two ellipsoids $\mathcal{E}_{\leq}(c_{1},E_{1})$ and
$\mathcal{E}_{\leq}(c_{2},E_{2})$ are strongly disjoint if
$(\lambda_{\min}(E_{1}))^{-1}+(\lambda_{\min}(E_{2}))^{-1}<\|c_{1}-c_{2}\|$.

Strong disjointness means that the two smallest spherical balls containing the
ellipsoids are disjoint. Strong disjointness is more conservative than weak
disjointness.

####  II-B5 Cone

For a positive definite matrix $E\in\mathbb{R}^{n\times n}$, a cone is the
$(n-1)$-dimensional subset of $\mathbb{R}^{n}$ described by the set

$\mathcal{C}(c,\\!v,\\!\theta,\\!E)\\!:=\\!\\{x\in\mathbb{R}^{n}\\!\colon\\!\cos(\theta)\|Ev\|\|E(x-c)\|\\!=\\!v^{\top}\\!E^{2}(x-c)\\}$
(11)

where $c\in\mathbb{R}^{n}$ is its vertex,
$v\in\mathbb{R}^{n}\backslash\\{0\\}$ is its axis and $2\theta\in[0,\pi]$ is
its aperture. The cone defined here is sometimes referred to as nappe or half-
cone, as opposed to the double cone. The closed interior (respectively,
exterior) of the cone, denoted by $\mathcal{C}_{\leq}(c,v,\theta,E)$
(respectively $\mathcal{C}_{\geq}(c,v,\theta,E)$), is obtained from (11) by
substituting the $=$ with $\leq$ (respectively $\geq$). A normal vector to the
cone surface $\mathcal{C}(c,v,\theta,E)$ at $x$ is

$n(x):=E\pi^{\theta}(Ev)E(x-c),$ (12)

and can be obtained after squaring in (11) and taking the gradient. The next
fact will be used.

###### Lemma 1

Let $v_{1},v_{2}\in\mathbb{S}^{n-1}$ such that $v_{1}^{\top}v_{2}=\cos\theta$
for some $\theta\in(0,\pi]$. Let $\psi_{1},\psi_{2}\in[0,\pi/2]$ with
$\psi_{1}+\psi_{2}<\theta$. Then for each $c\in\mathbb{R}^{n}$ and
$E\in\mathbb{R}^{n\times n}$ positive definite,

$\displaystyle\mathcal{C}_{\leq}(c,E^{-1}v_{1},\psi_{1},E)\cap\mathcal{C}_{\leq}(c,E^{-1}v_{2},\psi_{2},E)=\\{c\\}.$

###  II-C Hybrid Systems Framework

We consider hybrid dynamical systems of the class [24], described through
constrained differential and difference inclusions for state $X\in{}^{n}$:

$\begin{cases}\dot{X}\in\mathbf{F}(X),&X\in\mathcal{F},\\\
X^{+}\in\mathbf{J}(X),&X\in\mathcal{J},\end{cases}$ (13)

where the flow map $\mathbf{F}:\mathbb{R}^{n}\rightrightarrows\mathbb{R}^{n}$
governs the continuous evolution, the flow set
$\mathcal{F}\subseteq\mathbb{R}^{n}$ dictates where continuous evolution can
occur. The jump map $\mathbf{J}:\mathbb{R}^{n}\rightrightarrows\mathbb{R}^{n}$
governs the discrete evolution, and the jump set
$\mathcal{J}\subseteq\mathbb{R}^{n}$ defines where discrete evolution can
occur. The hybrid system (13) is defined by its data and denoted
$\mathscr{H}=(\mathbf{\mathcal{F}},\mathbf{F},\mathcal{J},\mathbf{J})$.

A subset $\mathbb{T}\subset\mathbb{R}_{\geq}\times\mathbb{N}$ is a hybrid time
domain if it is a union of a finite or infinite sequence of intervals
$[t_{j},t_{j+1}]\times\\{j\\}$, with the last interval (if existent) possibly
of the form $[t_{j},T)$ with $T$ finite or $T=+\infty$. The ordering of points
on each hybrid time domain is such that $(t,j)\preceq(t^{\prime},j^{\prime})$
if $t<t^{\prime}$, or $t=t^{\prime}$ and $j\leq j^{\prime}$. A hybrid solution
is defined in [24, Def. 2.6]. A hybrid solution $\phi$ is maximal if it cannot
be extended and complete if its domain $\operatorname{dom}\phi$ (which is a
hybrid time domain) is unbounded.

##  III Problem Formulation

We consider a point mass vehicle moving in the $n$-dimensional Euclidean space
containing $I\in\mathbb{N}$ obstacles denoted by
$\mathcal{O}_{1},\cdots,\mathcal{O}_{I}$. For each

$i\in\\{1,\cdots,I\\}=:\mathbb{I},$

the obstacle $\mathcal{O}_{i}$ has an ellipsoidal shape such that
$\mathcal{O}_{i}:=\mathcal{E}_{\leq}(c_{i},E_{i})$, for some center
$c_{i}\in\mathbb{R}^{n}$ and some positive definite matrix
$E_{i}\in\mathbb{R}^{n\times n}$ defining the orientation and the shape of the
obstacle. The free workspace (obstacle-free region) is then defined by the
closed set

$\displaystyle\mathcal{W}:=\bigcap_{i^{\prime}\in\mathbb{I}}\mathcal{E}_{\geq}(c_{i^{\prime}},E_{i^{\prime}}).$
(14)

The vehicle is moving according to the dynamics

$\dot{x}=u,$ (15)

where $x\in\mathbb{R}^{n}$ is the state and $u\in\mathbb{R}^{n}$ is the
control input. The vehicle is required to stabilize its position to a target
position while avoiding the obstacles. Without loss of generality we consider
the target position to be $x=0$ (the origin).

###### Assumption 1

$n\geq 2$.

We consider $n\geq 2$ since for $n=1$ (i.e., the state space is a line),
global asymptotic stabilization with obstacle avoidance is infeasible.

###### Assumption 2

For all $i\in\mathbb{I}$, $\|E_{i}c_{i}\|>1$.

Assumption 2 requires that the target position $x=0$ is not inside any of the
obstacle regions $\mathcal{O}_{i}$, otherwise the considered navigation
problem would be infeasible.

###### Assumption 3

$\\{\mathcal{O}_{i}\\}_{i\in\mathbb{I}}$ are weakly pairwise disjoint.

In Assumption 3 we impose that there is no intersection region between the
obstacles. Otherwise, the union of the two intersecting obstacles forms
another region which might have a different shape than an ellipsoid. Our
_objectives_ in designing a control strategy are:

  * i)

the obstacle-free region $\mathcal{W}$ in (14) is forward invariant,

  * ii)

the target $x=0$ is globally asymptotically stable.

Objective i) guarantees that all solutions of the closed-loop system are
safely avoiding the obstacles by remaining in the obstacle-free region
$\mathcal{W}$ for all times while objective ii) corresponds to global
stabilization of the target.

##  IV Hybrid Control for Obstacle Avoidance

In this section, we propose a hybrid controller that switches suitably between
a stabilizing and an avoidance controller. Let us define a discrete variable

$m\in\\{-1,0,1\\}=:\mathbb{M}.$

The value $m=0$ corresponds to the activation of the stabilizing controller
and the values $m=-1$, $m=1$ correspond to the activation of one of the two
configurations of the avoidance controller. The avoidance controller depends
also on the current obstacle $\mathcal{O}_{i}$, as detailed in the next
sections.

###  IV-A Control Input

In this section we propose the feedback law for the control input $u$ in (15).
$u$ depends on the state $x\in\mathbb{R}^{n}$, the obstacle $i\in\mathbb{I}$
and the control mode $m\in\mathbb{M}$ as

$\displaystyle u=\kappa(x,i,m)$ (16)
$\displaystyle:=\begin{cases}-k_{0}x,&m=0,\\\
-k_{m}E_{i}^{-1}\pi^{\perp}(E_{i}(x-c_{i}))E_{i}(x-p_{m}^{i}),&m\in\\{-1,1\\},\end{cases}$

where $k_{-1},\,k_{0},\,k_{1}>0$ are the control gains for each control mode
$m\in\mathbb{M}$ and the points $p_{m}^{i}\in\mathbb{R}^{n}$, $m\in\\{-1,1\\}$
and $i\in\mathbb{I}$, are design parameters defined below. In the
stabilization mode ($m=0$), the control input in (16) steers $x$ towards the
origin under a state feedback. In the avoidance mode depicted in Fig. 1, the
control input minimizes the distance to the auxiliary attractive point
$p_{m}^{i}$ while maintaining a constant distance to the obstacle
$\mathcal{O}_{i}$.

Figure 1: Illustration of the projection-based avoidance controller. The
vehicle is attracted to the auxiliary point $p_{m}^{i}$ while sliding on a
neighbouring ellipsoid.

Indeed, the time derivative of $\|E_{i}(x-c_{i})\|^{2}$ along solutions of
$\dot{x}=\kappa(x,i,m)$ for $m\in\\{-1,1\\}$ and $i\in\mathbb{I}$, reads

$\displaystyle\tfrac{1}{2}\tfrac{d}{dt}\|E_{i}(x-c_{i})\|^{2}=(x-c_{i})^{\top}E_{i}^{2}\kappa(x,i,m)$
(17)
$\displaystyle=-k_{m}(x-c_{i})^{\top}E_{i}\pi^{\perp}(E_{i}(x-c_{i}))E_{i}(x-p_{m}^{i})=0$

by (4b). Then, if we activate the avoidance mode sufficiently away from the
obstacle, the avoidance feedback $u=\kappa(x,i,m)$ guarantees that the vehicle
does not hit the obstacle. Whereas the logic variable $i$ corresponds to
obstacle $\mathcal{O}_{i}$, the logic variable $m$ is selected according to a
hybrid mechanism that exploits a suitable construction of the flow and jump
sets as detailed in Section IV-B.

In order to clear the obstacle while approaching the desired target position
at the origin, we select the points $p_{1}^{i}$ and $p_{-1}^{i}$ in the region
between the obstacle and the origin, see Fig. 1. The motivation is that the
avoidance task is equivalent (up to a linear transformation) to a
stabilization problem on the unit sphere $\mathbb{S}^{n-1}$. Therefore, as
pointed out for instance in [27], global asymptotic stabilization cannot be
accomplished by only one continuous time-invariant controller, but it can be
by a hybrid feedback with at least two configurations. For this reason, we
consider two avoidance modes with $m=-1$ and $m=1$ and, hence, the points
$p_{1}^{i}$ and $p_{-1}^{i}$ must be distinct. More precisely, for
$\theta_{i}>0$ (which will be further bounded in Lemma 4), the points
$p_{1}^{i}$ and $p_{-1}^{i}$ are selected as

$\displaystyle p_{1}^{i}$
$\displaystyle\in\mathcal{C}(c_{i},-c_{i},\theta_{i},E_{i})\backslash\\{c_{i}\\},$
(18a) $\displaystyle p_{-1}^{i}$
$\displaystyle:=-E_{i}^{-1}\rho(E_{i}c_{i})E_{i}p_{1}^{i}.$ (18b)

By (18), $p_{-1}^{i}$ opposes $p_{1}^{i}$ diametrically with respect to the
cone axis (for $E_{i}=I_{n}$, $p_{-1}^{i}$ is obtained by an orthogonal
reflection) and also belongs to
$\mathcal{C}(c_{i},-c_{i},\theta_{i},E_{i})\backslash\\{c_{i}\\}$ as shown in
the next lemma.

###### Lemma 2

$p_{-1}^{i}\in\mathcal{C}(c_{i},-c_{i},\theta_{i},E_{i})\backslash\\{c_{i}\\}.$

Note that the results of the paper hold for any selection of the point
$p_{1}^{i}$ as long as it lies on the surface of the cone as in (18a). An
explicit guided choice for those points is given in Section VI for the 2D and
3D cases. Finally, further motivation about the choice of the avoidance
controller mode in (16) is detailed in Section IV-B and, in particular, in
Lemma 3, which is important for the construction of flow and jump sets.

###  IV-B Geometric Construction of the Flow and Jump sets

In this section we construct explicitly the flow and jump sets where the
stabilization and avoidance controllers are activated.

####  IV-B1 Safety Helmets

Our proposed construction of flow and jump sets is based on regions that have
the shape of a helmet, whose construction is now motivated. In the
stabilization mode $m=0$, the closed-loop system should _not_ flow when: 1)
$x$ is close enough to any of the obstacle regions
$\mathcal{E}_{\leq}(c_{i},E_{i})$ and 2) the vector field $-k_{0}x$ points
inside $\mathcal{E}_{\leq}(c_{i},E_{i})$. Otherwise, the vehicle ends up
hitting the obstacle $i$. Indeed, by computing the time derivative of
$\|E_{i}(x-c_{i})\|^{2}$ along solutions of the vector field $-k_{0}x$, we
obtain

$\displaystyle\tfrac{1}{2}\tfrac{d}{dt}\|E_{i}(x-c_{i})\|^{2}=-k_{0}x^{\top}E_{i}^{2}(x-c_{i})$
(19)
$\displaystyle=k_{0}c_{i}^{\top}E_{i}^{2}c_{i}/4-k_{0}(x-c_{i}/2)^{\top}E_{i}^{2}(x-c_{i}/2)$
$\displaystyle=k_{0}\|E_{i}\bar{c}_{i}\|^{2}\left(1-\|\bar{E}_{i}(x-\bar{c}_{i})\|^{2}\right)$

where $\bar{c}_{i}$ and $\bar{E}_{i}$ are defined as

$\displaystyle\bar{c}_{i}:={c_{i}}/{2},\quad\bar{E}_{i}:={2E_{i}}/(\|E_{i}c_{i}\|).$
(20)

(19) implies that the distance function $\|E_{i}(x-c_{i})\|^{2}$ decreases for
all $x$ in the closed set $\mathcal{E}_{\geq}(\bar{c}_{i},\bar{E}_{i})$.
Consider now Fig. 2 for a sketch of the next sets and for obstacle $i$, define
the helmet-shaped set

$\displaystyle\mathcal{H}^{*}_{i}:=\mathcal{E}(c_{i},E_{i})\cap\mathcal{E}_{\geq}(\bar{c}_{i},\bar{E}_{i}).$
(21)

$\mathcal{H}^{*}_{i}$ is the set of all points that lie on the boundary of the
obstacle $\mathcal{O}_{i}$ and generate a vector field pointing towards the
obstacle. Then, for obstacle $i$, we define the safety helmet as:

$\displaystyle\mathcal{H}_{i}(\epsilon,\nu):=\mathcal{E}_{\leq}(c_{i},\epsilon
E_{i})\cap\mathcal{E}_{\geq}(c_{i},E_{i})\cap\mathcal{E}_{\geq}(\bar{c}_{i},\nu\bar{E}_{i})$
(22)

for some parameters $\epsilon,\,\nu>0$. $\epsilon$ and $\nu$ determine the
thickness of the safety helmet by tuning the dilation/shrinking of the
ellipsoids $\mathcal{E}(c_{i},E_{i})$ and
$\mathcal{E}(\bar{c}_{i},\bar{E}_{i})$, thereby generating a dilated version
of $\mathcal{H}^{*}_{i}$. The safety helmet $\mathcal{H}_{i}(\epsilon,\nu)$
constitutes the main ingredient of our following constructions.

Figure 2: The helmet $\mathcal{H}_{i}^{*}$ in (21) (red) corresponds to all
boundary points where the stabilization vector field is pointing inside the
obstacle (grey). The safety helmet $\mathcal{H}_{i}(\epsilon,\nu)$ in (22)
(green) corresponds to an dilated version of $\mathcal{H}_{i}^{*}$.

####  IV-B2 Stabilization Mode $m=0$

Consider from now on Fig. 3 for a visualization of the sets we are introducing
in our construction. In stabilization mode ($m=0$), we create around each
obstacle $\mathcal{O}_{i}$ a safety helmet
$\mathcal{H}_{i}(\epsilon_{i},\nu_{i})$ which adds a safety layer to the given
obstacle. The controller mode must be switched to the avoidance mode whenever
the vehicle reaches this safety helmet. Specifically, we define for each
$i\in\mathbb{I}$, a jump set

$\displaystyle\mathcal{J}_{0}^{i}:=\mathcal{H}_{i}(\epsilon_{i},\nu_{i})\cap\mathcal{W},$
(23)

where $\epsilon_{i}\in(0,1)$ (dilating $\mathcal{E}_{\leq}(c_{i},E_{i})$ to
$\mathcal{E}_{\leq}(c_{i},\epsilon_{i}E_{i})$), and $\nu_{i}\in(1,\infty)$
(shrinking $\mathcal{E}_{\geq}(\bar{c}_{i},\bar{E}_{i})$ to
$\mathcal{E}_{\geq}(\bar{c}_{i},\nu_{i}\bar{E}_{i})$) and $\mathcal{W}$ is the
free workspace defined in (14). We emphasize that we consider the intersection
with $\mathcal{W}$ in (23) for convenience, but later we tune the parameters
such that $\mathcal{H}_{i}(\epsilon_{i},\nu_{i})\subset\mathcal{W}$, which
implies $\mathcal{J}_{0}^{i}$ will equal to
$\mathcal{H}_{i}(\epsilon_{i},\nu_{i})$. The selection of
$\mathcal{J}_{0}^{i}$ in (23) leads naturally to the following flow set of the
stabilization mode (corresponding to the closed complement of
$\mathcal{J}_{0}^{i}$ in the free workspace)

$\displaystyle\mathcal{F}_{0}^{i}:=\Big{(}\mathcal{E}_{\geq}(c_{i},\epsilon_{i}E_{i})\cup\mathcal{E}_{\leq}(\bar{c}_{i},\nu_{i}\bar{E}_{i})\Big{)}\cap\mathcal{W}.$
(24)

Finally, from (23) and (24), we take all the obstacles into account and define
the flow and jump sets for the stabilization mode $m=0$ as

$\mathcal{F}_{0}:=\Big{(}\bigcap\limits_{i\in\mathbb{I}}\mathcal{F}_{0}^{i}\Big{)}\times\mathbb{I},\qquad\mathcal{J}_{0}:=\Big{(}\bigcup\limits_{i\in\mathbb{I}}\mathcal{J}_{0}^{i}\Big{)}\times\mathbb{I}.$
(25)

Indeed, the stabilization mode can be selected when the state $x$ belongs to
the intersection of the sets $\mathcal{F}_{0}^{i}$ (and for _any_ obstacle
index $i\in\mathbb{I}$), and a jump to the avoidance mode can occur when the
state $x$ belongs to the union of the sets $\mathcal{J}^{i}_{0}$ (and for
_any_ obstacle index $i\in\mathbb{I}$). In other words, if during the
stabilization mode the vehicle reaches any one of the safety helmets, then the
controller jumps to one of the avoidance modes with $m$ equal to $-1$ or $1$.

Figure 3: 2D illustration of flow and jump sets considered in Sections IV-V
corresponding to obstacle $\mathcal{O}_{i}$ (in the presence of a second
obstacle $\mathcal{O}_{j}$). The stabilization-mode jump set
$\mathcal{J}_{0}^{i}$ (hatched red) is constructed by using the helmet
$\mathcal{H}_{i}(\epsilon_{i},\nu_{i})$, while the corresponding flow set
$\mathcal{F}_{0}^{i}$ is the complement of $\mathcal{J}_{0}^{i}$ in the free
workspace. For the avoidance mode we select $p_{1}^{i}$ and $p_{-1}^{i}$ to
lie on the cone $\mathcal{C}(c_{i},-c_{i},\theta_{i},E_{i})$ (solid brown
line). The avoidance flow set $\mathcal{F}_{m}^{i}$, with $m\in\\{-1,1\\}$,
corresponds to the helmet $\mathcal{H}_{i}(\delta_{i},\mu_{i})$ deprived of
the interior of the the cone region defined by
$\mathcal{C}(c_{i},c_{i}-p_{m}^{i},\psi_{i},E_{i})$ (solid purple line for
$m=-1$ and solid orange line for $m=1$). The corresponding jump set
$\mathcal{J}_{m}^{i}$ is the complement of $\mathcal{F}_{m}^{i}$ in the free
workspace.

####  IV-B3 Avoidance Mode $m\in\\{-1,1\\}$

We consider now the construction of flow and jump sets for the avoidance modes
$m\in\\{-1,1\\}$ and the specific obstacle $i\in\mathbb{I}$ with the aid of
Fig. 3. To highlight their motivation, we first define such flow sets and
state later the corresponding jump sets (see (28)). For each $i\in\mathbb{I}$
and $m\in\\{-1,1\\}$, the avoidance flow set is

$\displaystyle\mathcal{F}_{m}^{i}:=\mathcal{H}_{i}(\delta_{i},\mu_{i})\cap\mathcal{C}_{\geq}(c_{i},c_{i}-p_{m}^{i},\psi_{i},E_{i})\cap\mathcal{W},$
(26)

where $\delta_{i}\in(0,\epsilon_{i})$ (dilating
$\mathcal{E}_{\leq}(c_{i},\epsilon_{i}E_{i})$ to
$\mathcal{E}_{\leq}(c_{i},\delta_{i}E_{i})$), $\mu_{i}\in(\nu_{i},\infty)$
(shrinking $\mathcal{E}_{\geq}(\bar{c}_{i},\nu_{i}\bar{E}_{i})$ to
$\mathcal{E}_{\geq}(\bar{c}_{i},\mu_{i}\bar{E}_{i})$), and
$\psi_{i}\in(0,\pi/2]$. In the two configurations $m\in\\{-1,1\\}$ of the
avoidance of obstacle $i\in\mathbb{I}$, we want the vehicle to slide on the
safety helmet $\mathcal{H}_{i}(\delta_{i},\mu_{i})$ while maintaining a
constant distance to the obstacle. By selecting
$\delta_{i}\in(0,\epsilon_{i})$ and $\mu_{i}\in(\nu_{i},\infty)$, one obtains
a dilated version of $\mathcal{H}_{i}(\epsilon_{i},\nu_{i})$ used in
$\mathcal{J}_{0}^{i}$ and, thus, creates a hysteresis region useful to prevent
infinitely many consecutive jumps (Zeno behavior). However, the avoidance
vector field $\kappa(x,i,m)$ in (16) has some undesirable equilibria, which we
need to rule out from the flow sets $\mathcal{F}_{1}^{i}$ and
$\mathcal{F}_{-1}^{i}$. These are characterized in the next lemma.

###### Lemma 3

Let $c\in{}^{n}$, $p\in{}^{n}\backslash\\{c\\}$ and $E\in{}^{n\times n}$
positive definite. For each $x\in{}^{n}\backslash\\{c\\}$,
$\pi^{\perp}(E(x-c))E(x-p)=0$ if and only if $x\in\mathcal{L}(c,p-c)$.

For each $m\in\\{-1,1\\}$, $i\in\mathbb{I}$, we want solutions to eventually
leave the set $\mathcal{F}_{m}^{i}$ of the avoidance mode, so it is necessary
to select point $p_{m}^{i}$ and flow set $\mathcal{F}_{m}^{i}$ such that
$\mathcal{L}(c_{i},p_{m}^{i}-c_{i})\cap\mathcal{F}_{m}^{i}=\emptyset$ based on
Lemma 3, otherwise solutions could stay in avoidance mode indefinitely. This
motivates the intersection with the cone in (26), and the next lemma.

###### Lemma 4

For each $i\in\mathbb{I}$, define the quantities

$\displaystyle\underline{\delta}_{i}:=\|E_{i}c_{i}\|^{-\frac{1}{2}}$ (27a)
$\displaystyle\bar{\mu}_{i}(\delta_{i}):=\big{(}1-4\underline{\delta}_{i}^{2}(1-\underline{\delta}_{i}^{2}/\delta_{i}^{2})\big{)}^{-\frac{1}{2}}$
(27b)
$\displaystyle\bar{\theta}_{i}(\delta_{i},\mu_{i}):=\arccos\left(\frac{\underline{\delta}_{i}^{2}}{\delta_{i}^{2}}+\frac{1}{4\underline{\delta}_{i}^{2}}\left(1-\frac{1}{\mu_{i}^{2}}\right)\right)$
(27c)

and select the parameters $\delta_{i},\mu_{i},\theta_{i},\psi_{i}$ as in Table
I so that $\bar{\mu}_{i}(\delta_{i})$ and
$\bar{\theta}_{i}(\delta_{i},\mu_{i})$ are well-defined. Then, for each
$m\in\\{-1,1\\}$,
$\mathcal{L}(c_{i},p_{m}^{i}-c_{i})\cap\mathcal{F}_{m}^{i}=\emptyset$.

From the flow set in (26), we suitably define the jump set for the avoidance
mode, of an obstacle $i\in\mathbb{I}$ with configuration $m\in\\{-1,1\\}$, to
be the closed complement of $\mathcal{F}_{m}^{i}$ in the free workspace. For
$i\in\mathbb{I}$ and $m\in\\{-1,1\\}$,

$\displaystyle\mathcal{J}_{m}^{i}:=\Big{(}\mathcal{E}_{\geq}(c_{i},\delta_{i}E_{i})$
$\displaystyle\cup\mathcal{E}_{\leq}(\bar{c}_{i},\mu_{i}\bar{E}_{i})$ (28)
$\displaystyle\cup\mathcal{C}_{\leq}(c_{i},c_{i}\\!-\\!p_{m}^{i},\psi_{i},E_{i})\Big{)}\cap\mathcal{W}.$

Finally, the avoidance mode has overall flow and jump sets

$\displaystyle\mathcal{F}_{1}\\!$
$\displaystyle:=\bigcup\limits_{i\in\mathbb{I}}\left(\mathcal{F}_{1}^{i}\\!\times\\!\\{i\\}\right),$
$\displaystyle\mathcal{J}_{1}\\!$
$\displaystyle:=\bigcup\limits_{i\in\mathbb{I}}\left(\mathcal{J}_{1}^{i}\\!\times\\!\\{i\\}\right),$
(29a) $\displaystyle\mathcal{F}_{-1}\\!$
$\displaystyle:=\bigcup\limits_{i\in\mathbb{I}}\left(\mathcal{F}_{-1}^{i}\\!\times\\!\\{i\\}\right),$
$\displaystyle\mathcal{J}_{-1}\\!$
$\displaystyle:=\bigcup\limits_{i\in\mathbb{I}}\left(\mathcal{J}_{-1}^{i}\\!\times\\!\\{i\\}\right),$
(29b)

where $\mathcal{F}_{m}^{i}$ and $\mathcal{J}_{m}^{i}$ ($m\in\\{-1,1\\}$) are
defined in (26) and (28). Indeed, _each_ obstacle $i$ gives rise, for the
avoidance mode, to a specific flow (jump) set with two configurations
$\mathcal{F}_{1}^{i}$ and $\mathcal{F}_{-1}^{i}$ ($\mathcal{J}_{1}^{i}$ and
$\mathcal{J}_{-1}^{i}$), as we motivated in this section.

TABLE I: Selection of the design parameters of (30), with $i\in\mathbb{I}$. Parameter |  Selection |  Parameter |  Selection
---|---|---|---
$\delta_{i}$ |  $(\underline{\delta}_{i},1)$ |  $\epsilon_{i}$ |  $(\delta_{i},1)$
$\mu_{i}$ |  $(1,\bar{\mu}_{i}(\delta_{i}))$ |  $\nu_{i}$ |  $(1,\mu_{i})$
$\theta_{i}$ |  $(0,\bar{\theta}_{i}(\delta_{i},\mu_{i}))$ |  $\bar{\psi}_{i}$ |  $(0,\theta_{i})$
$k_{0}$, $k_{1}$, $k_{-1}$ |  $(0,+\infty)$ |  $\psi_{i}$ |  $(0,\bar{\psi}_{i})$
|  |  $p^{i}_{1}$, $p^{i}_{-1}$ |  as in (18)

###  IV-C Hybrid Mode Selection

In this section we define the hybrid switching strategy that permits a Zeno-
free transition between the different control modes. The hybrid selection of
the logical variables $i\in\mathbb{I}$ and $m\in\mathbb{M}$ is implemented in
the hybrid system

$\displaystyle\left\\{\begin{aligned} \dot{x}&=\kappa(x,i,m)\\\
\dot{\aoverbrace[L1R]{i}}&=0\\\ \dot{m}&=0\end{aligned}\right.$
$\displaystyle(x,i,m)\in\mathcal{F}$ (30a)
$\displaystyle\left\\{\begin{aligned} x^{+}&=x\\\
\left[\begin{smallmatrix}i^{+}\\\
m^{+}\end{smallmatrix}\right]&\in\mathbf{L}(x,i,m)\end{aligned}\right.$
$\displaystyle(x,i,m)\in\mathcal{J}$ (30b) where $\kappa(x,i,m)$ is the
control input as defined in (16) and the flow and jump sets are given by
$\displaystyle\mathcal{F}$
$\displaystyle:=\bigcup\limits_{m\in\mathbb{M}}\left(\mathcal{F}_{m}\\!\times\\!\\{m\\}\right),$
$\displaystyle\mathcal{J}$
$\displaystyle:=\bigcup\limits_{m\in\mathbb{M}}\left(\mathcal{J}_{m}\\!\times\\!\\{m\\}\right).$
(30c) with $\mathcal{F}_{m}$ and $\mathcal{J}_{m}$ being defined in (25) for
$m=0$ and in (29a)-(29b) for $m\in\\{-1,1\\}$. We define now the (set-valued)
jump map $\mathbf{L}$ in (30b). To this end, for $i\in\mathbb{I}$ and
$m\in\\{-1,1\\}$, define the sets $\mathcal{C}^{i}_{m}$ as
$\displaystyle\mathcal{C}^{i}_{m}:=\mathcal{C}_{\geq}(c_{i},c_{i}-p^{i}_{m},\bar{\psi}_{i},E_{i})$
(30d) which corresponds to the region outside the cone with vertex at $c_{i}$,
axis $c_{i}-p_{m}^{i}$ and aperture $2\bar{\psi}_{i}$, where $\bar{\psi}_{i}$
is a design parameter selected below. The jump map $\mathbf{L}$ for
$m\in\\{-1,1\\}$ is then defined as
$\mathbf{L}(x,i,-1):=\mathbf{L}(x,i,1):=\\{\left[\begin{smallmatrix}i\\\
0\end{smallmatrix}\right]\\},$ (30e) i.e., when jumping to stabilization mode,
the obstacle index $i$ is not used in the control law $\kappa$ in (16) and
consequently is not updated. The jump map $\mathbf{L}$ for $m=0$ is
$\mathbf{L}(x,i,0):=\left\\{\left[\begin{smallmatrix}i^{\prime}\\\
m^{\prime}\end{smallmatrix}\right]\colon
x\in\mathcal{J}^{i^{\prime}}_{0},m^{\prime}\in\mathbf{M}(x,i^{\prime})\right\\}$
(30f) where $\mathbf{M}$ is defined, based on (30d), as
$\displaystyle\mathbf{M}(x,i):=\begin{cases}\\{-1\\}&x\in\mathcal{C}^{i}_{-1}\backslash\mathcal{C}^{i}_{1}\\\
\\{1\\}&x\in\mathcal{C}^{i}_{1}\backslash\mathcal{C}^{i}_{-1}\\\
\\{-1,1\\}&x\in\mathcal{C}^{i}_{-1}\cap\mathcal{C}^{i}_{1}.\\\ \end{cases}$
(30g) $\mathbf{L}(\cdot,\cdot,0)$ captures that when jumping from the
stabilization mode $m=0$, the suitable avoidance mode of obstacle
$i^{\prime}\in\mathbb{I}$ with configuration $m^{\prime}\in\\{-1,1\\}$ is
selected based on the position $x$ of the vehicle ($m^{\prime}$, in
particular, is selected based on whether $x$ is within the cone region
$\mathcal{C}^{i^{\prime}}_{-1}$ or $\mathcal{C}^{i^{\prime}}_{1}$). A
necessary condition to implement our hybrid controller is that the jump map is
nonempty, for which we have the next lemma.

###### Lemma 5

Select the parameters $\bar{\psi}_{i}$ and $\psi_{i}$ as in Table I. Then, the
set $\mathbf{L}(x,i,m)$ is nonempty for all $(x,i,m)\in\mathcal{J}$.

For compact notation, we write flow and jump maps as

$\displaystyle(x,i,m)$
$\displaystyle\mapsto\mathbf{F}(x,i,m):=(\kappa(x,i,m),0,0)$ (30h)
$\displaystyle(x,i,m)$
$\displaystyle\mapsto\mathbf{J}(x,i,m):=(x,\mathbf{L}(x,i,m)),$ (30i)

and the overall state of the hybrid system as

$\xi:=(x,i,m)\in\mathbb{R}^{n}\times\mathbb{I}\times\mathbb{M}.$ (30j)

This completes the description of the hybrid controller in (30). The
selections we made in this section for the parameters of (30) are summarized
in Table I.

##  V Main Result

In this section, we show that the hybrid controller achieves forward
invariance (Section V-A) and global asymptotic stability (Section V-B)
(related to the objectives in Section III), as well as some complementary
properties (Section V-C).

The mild regularity conditions satisfied by the hybrid system (30), as in the
next lemma, allows us to invoke useful results on hybrid systems in the proof
of our results.

###### Lemma 6

The hybrid system with data $(\mathcal{F},\mathbf{F},\mathcal{J},\mathbf{J})$
satisfies the hybrid basic conditions in [24, Assumption 6.5].

###  V-A Forward Invariance

In this section, we show that all generated solutions are complete and safe.
Since the state $x$ must evolve always within the free workspace $\mathcal{W}$
in (14) regardless of the logic variables $i$ and $m$, we seek forward
invariance of the set $\mathcal{K}$ defined as:

$\mathcal{K}:=\bigcap_{i^{\prime}\in\mathbb{I}}\mathcal{E}_{\geq}(c_{i^{\prime}},E_{i^{\prime}})\times\mathbb{I}\times\mathbb{M}=\mathcal{W}\times\mathbb{I}\times\mathbb{M}.$
(31)

The next lemma shows that the union of flow and jump sets covers exactly the
obstacle-free state space $\mathcal{K}$ and that solutions cannot leave
$\mathcal{K}$ through jumps.

###### Lemma 7

$\mathcal{F}\cup\mathcal{J}=\mathcal{K}$ and
$\mathbf{J}(\mathcal{J})\subset\mathcal{K}$.

Forward invariance of $\mathcal{K}$ is proven in the next theorem.

###### Theorem 1

Under Assumptions 1-3, consider the hybrid system (30) with parameters
selected as in Table I. Assume also that the controller parameters
$\delta_{i}$ are tuned so that the ellipsoids
$\\{\mathcal{E}_{\leq}(c_{i},\delta_{i}E_{i})\\}_{i\in\mathbb{I}}$ are weakly
pairwise disjoint. Then, the obstacle-free set $\mathcal{K}$ in (31) is
forward invariant.

The existence of tuning parameters $\delta_{1},\dots,\delta_{I}$ satisfying
the weak pairwise disjointness of the sets
$\\{\mathcal{E}_{\leq}(c_{i},\delta_{i}E_{i})\\}_{i\in\mathbb{I}}$ is
guaranteed by Assumption 3, which implies that weak pairwise disjointness
holds when $\delta_{i}=1$ for all $i\in\mathbb{I}$. Hence, by a continuity
argument, we can always tune each $\delta_{i}$ sufficiently close to $1$ in
order to guarantee the weak pairwise disjointness of the dilated obstacles
$\\{\mathcal{E}_{\leq}(c_{i},\delta_{i}E_{i})\\}_{i\in\mathbb{I}}$. Note that
algebraic tests of weak pairwise disjointness (provided in [25, Thm. 6] for
$n=2$ and in [26, Thm. 8] for $n=3$) can be used for this tuning purpose.

###  V-B Global Asymptotic Stability

In this section we show that from all initial conditions in the free
workspace, all solutions converge asymptotically to the origin. To this end,
we define the notion of _sufficient disjointness_ of a set of ellipsoids,
which is slightly stronger than weak disjointness but less conservative than
strong disjointness, and guarantees that each obstacle is avoided at most one
time. The motivation behind the assumption of sufficient disjointness is that
the ellipsoids considered here can be arbitrarily large and flat, which might
lead to long detours during the avoidance mode that take the vehicle far away
from the origin. In this case, specific configurations of the obstacles exist
such that from a set of initial conditions, the vehicle does not converge to
the origin although it remains safe. Similarly, in the Bug $0$ planning
algorithm [28], termination (i.e., convergence to the target) is not _always_
guaranteed since the algorithm is designed to “walk toward the target whenever
you can” [28]. Our hybrid feedback shares a similar philosophy since the
vehicle jumps from avoidance to stabilization mode whenever the stabilization
controller generates a vector field not pointing towards the obstacle (see
(19)). To proceed, the next lemma characterizes the intersection of two
ellipsoids of interest.

###### Lemma 8

Consider an arbitrary $i\in\mathbb{I}$. For $\underline{\delta}_{i}$,
$\delta\mapsto\bar{\mu}_{i}(\delta)$ and
$(\delta,\mu)\mapsto\bar{\theta}_{i}(\delta,\mu)$ defined in (27), let
$\delta\in[\underline{\delta}_{i},1]$, $\mu\in[1,\bar{\mu}_{i}(\delta)]$ and
$\vartheta_{i}(\delta,\mu)$ be such that

$\cos(\vartheta_{i}(\delta,\mu)):=\frac{1-\cos(\bar{\theta}_{i}(\delta,\mu))\underline{\delta}_{i}^{2}}{\sqrt{(1+\mu^{-2})/2-\delta^{-2}\underline{\delta}_{i}^{4}}}.$
(32)

The expression in (32) is well-defined and positive, and

$\mathcal{E}(c_{i},\delta
E_{i})\cap\mathcal{E}(\bar{c}_{i},\mu\bar{E}_{i})\subset\mathcal{C}(0,c_{i},\vartheta_{i}(\delta,\mu),E_{i}).$
(33)

Let us consider for each obstacle $i\in\mathbb{I}$ the sphere
$\mathcal{S}(0,\bar{r}_{i})$ with center at the origin and radius
$\bar{r}_{i}$ defined by the next quadratic optimization problem

$\displaystyle\bar{r}_{i}^{2}:=$
$\displaystyle\min\|x\|^{2}\quad\textrm{subject to }$ $\displaystyle
x\in\mathcal{H}^{*}_{i}$ (34)

where $\mathcal{H}^{*}_{i}$ is the helmet defined in (21). The radius
$\bar{r}_{i}$ defines the minimum distance from the helmet
$\mathcal{H}^{*}_{i}$ to the origin. Let $x$ be a point belonging to the
intersection of the two ellipsoids $\mathcal{E}(c_{i},E_{i})$ and
$\mathcal{E}(\bar{c}_{i},\bar{E}_{i})$. Taking $\delta$ and $\mu$ equal to $1$
in Lemma 8, one obtains $x\in\mathcal{C}(0,c_{i},\bar{\vartheta}_{i},E_{i})$
with

$\cos(\bar{\vartheta}_{i}):=\cos(\vartheta_{i}(1,1))=\sqrt{1-\|E_{i}c_{i}\|^{-2}},$
(35)

from (32), (27c) and (27a). Now, let us define the set

$\mathcal{R}^{*}_{i}:=\mathcal{C}(0,c_{i},\bar{\vartheta}_{i},E_{i})\cap\mathcal{S}_{\geq}(0,\bar{r}_{i})\cap\mathcal{E}_{\geq}(c_{i},E_{i})\cap\mathcal{E}_{\leq}(\bar{c}_{i},\bar{E}_{i}),$
(36)

whose geometry is sketched in Fig. 4. Intuitively speaking, it is a subset of
all points on the cone $\mathcal{C}(0,c_{i},\bar{\vartheta}_{i},E_{i})$ that
have a distance to the origin greater than the distance $\bar{r}_{i}$ of the
helmet $\mathcal{H}^{*}_{i}$ to the origin. The idea is that the vehicle
should not to start avoiding another obstacle while it is still in
$\mathcal{R}^{*}_{i}$, otherwise there is no guarantee that the number of
times the vehicle avoids the obstacles is bounded and that global attractivity
holds. This motivates the next definition.

###### Definition 3

The ellipsoids $\\{\mathcal{E}(c_{i},E_{i})\\}_{i\in\mathbb{I}}$ are
sufficiently pairwise disjoint if they are weakly pairwise disjoint and

$\forall i,i^{\prime}\in\mathbb{I}\text{ with }i\neq
i^{\prime},\quad\mathcal{R}^{*}_{i}\cap\mathcal{E}_{\leq}(c_{i^{\prime}},E_{i^{\prime}})=\emptyset.$
(37)

Figure 4: Different types of disjointness introduced in the paper with set
$\mathcal{R}_{i}^{*}$ (orange, see (36)). For global attractivity, sufficient
disjointness is asked.

Now, let us introduce the ingredients for a dilated version of
$\mathcal{R}^{*}_{i}$ as in (39) below and refer to Fig. 5. First, consider
the escape annulus cone where solutions escape from the avoidance mode by
applying the stabilization vector field. This region lies between the two
cones $\mathcal{C}(0,c_{i},\vartheta_{i}(1,\mu_{i}),E_{i})$ and
$\mathcal{C}(0,c_{i},\vartheta_{i}(\delta_{i},\mu_{i}),E_{i})$ which are
related, according to Lemma 8, to the intersections
$\mathcal{E}(c_{i},E_{i})\cap\mathcal{E}(\bar{c}_{i},\mu_{i}\bar{E}_{i})$ and
$\mathcal{E}(c_{i},\delta_{i}E_{i})\cap\mathcal{E}(\bar{c}_{i},\mu_{i}\bar{E}_{i})$,
respectively. Second, consider for each obstacle $i\in\mathbb{I}$ the ball
$\mathcal{S}_{\geq}(0,r_{i})$ where the radius $r_{i}$ is defined by the
quadratic optimization problem

$\displaystyle r_{i}^{2}:=$ $\displaystyle\min\|x\|^{2}\quad\textrm{subject to
}$ $\displaystyle x\in\mathcal{H}_{i}(\delta_{i},\mu_{i}).$ (38)

Note the following on (38). 1) The safety helmet
$\mathcal{H}_{i}(\delta_{i},\mu_{i})$ is compact and, hence, the solution to
(38) exists. 2) For each $i\in\mathbb{I}$, $r_{i}>0$. Indeed, for each
$i\in\mathbb{I}$,
$\|\delta_{i}E_{i}c_{i}\|=\delta_{i}\underline{\delta}_{i}^{-2}>\delta_{i}\underline{\delta}_{i}^{-1}>1$
by Assumption 2 and the selection of $\delta_{i}$ in Table I, so that
$0\notin\mathcal{E}_{\leq}(c_{i},\delta_{i}E_{i})$ and in turn
$0\notin\mathcal{H}_{i}(\delta_{i},\mu_{i})$
($\mathcal{H}_{i}(\delta_{i},\mu_{i})\subset\mathcal{E}_{\leq}(c_{i},\delta_{i}E_{i})$).
Hence, since $\mathcal{H}_{i}(\delta_{i},\mu_{i})$ is compact there exists
$r_{i}>0$ such that $\|x\|\geq r_{i}$ for all
$x\in\mathcal{H}_{i}(\delta_{i},\mu_{i})$. Finally, we can define the
considered dilated version of $\mathcal{R}^{*}_{i}$ as

$\mathcal{R}_{i}(\delta_{i},\mu_{i}):=\mathcal{S}_{\geq}(0,r_{i})\cap\mathcal{E}_{\geq}(c_{i},\delta_{i}E_{i})\cap\mathcal{E}_{\leq}(\bar{c}_{i},\bar{E}_{i})\\\
\cap\mathcal{C}_{\geq}(0,c_{i},\vartheta_{i}(1,\mu_{i}),E_{i})\cap\mathcal{C}_{\leq}(0,c_{i},\vartheta_{i}(\delta_{i},\mu_{i}),E_{i}).$
(39)

Figure 5: Safety helmet $\mathcal{H}_{i}(\delta_{i},\mu_{i})$ (green) and the
corresponding escape region $\mathcal{R}_{i}(\delta_{i},\mu_{i})$ (orange).
The region $\mathcal{R}_{i}(\delta_{i},\mu_{i})$ must not intersect with any
other jump set $\mathcal{J}_{0}^{i^{\prime}}$, $i^{\prime}\neq i$, to avoid
starting another avoidance while the distance to target has not yet decreased.

###### Lemma 9

Assume that the obstacles $\\{\mathcal{O}_{i}\\}_{i\in\mathbb{I}}$ are
sufficiently pairwise disjoint. Then, for each $i\in\mathbb{I}$, there exist
$\delta_{i}^{*},\mu_{i}^{*}$ such that for all
$\delta_{i}\in(\delta_{i}^{*},1)$ and $\mu_{i}\in(1,\mu_{i}^{*})$, we have

$\forall i^{\prime},i^{\prime\prime}\in\mathbb{I},i^{\prime}\neq
i^{\prime\prime},\,\,\mathcal{R}_{i^{\prime}}(\delta_{i^{\prime}},\mu_{i^{\prime}})\cap\mathcal{E}_{\leq}(c_{i^{\prime\prime}},\delta_{i^{\prime\prime}}E_{i^{\prime\prime}})=\emptyset.$
(40)

Property (40) of Lemma 9 will be used to show global attractivity.
Intuitively, we require that after avoiding an obstacle, the distance $\|x\|$
to the target decreases before the vehicle reaches the proximity of another
obstacle. Although the bounds $\delta_{i}^{*}$ and $\mu_{i}^{*}$ are not
defined explicitly for generic ellipsoids, the parameters $\delta_{i}$ and
$\mu_{i}$ can be tuned offline. Now, we are ready to state our main result for
this section.

###### Theorem 2

Consider the hybrid system (30) under the same assumptions as Theorem 1.
Assume also that the obstacles $\\{\mathcal{O}_{i}\\}_{i\in\mathbb{I}}$ are
sufficiently pairwise disjoint, and $\delta_{i}$ and $\mu_{i}$ are tuned such
that (40) holds. Then, the set
$\mathcal{A}:=\\{0\\}\times\mathbb{I}\times\mathbb{M}$ is globally
asymptotically stable for (30) and the number of jumps is bounded.

For spherical obstacles, we show next that the extra tuning of the parameters
to satisfy (40) is not needed.

###### Theorem 3

(Spherical obstacles) Let $E_{i}=\lambda_{i}I_{n}$ for all $i\in\mathbb{I}$.
Under the same assumptions as Theorem 1, the set
$\mathcal{A}:=\\{0\\}\times\mathbb{I}\times\mathbb{M}$ is globally
asymptotically stable for (30) and the number of jumps is bounded.

###  V-C Complementary Properties

In this section we present four relevant complementary properties of the
proposed hybrid law for obstacle avoidance.

####  V-C1 Bounded Control

First, we can show that $x$ remains always in a given ball. Indeed, let
$\mathcal{S}_{\leq}(0,r_{b})$, with $r_{b}>0$, be the smallest ball containing
all the dilated ellipsoids $\mathcal{E}(c_{i},\delta_{i}E_{i})$ (which must
exist since these ellipsoids are compact). During stabilization mode the
distance $\|x\|$ is decreasing and during avoidance mode the vehicle stays
within the dilated ellipsoids $\mathcal{E}(c_{i},\delta_{i}E_{i})$. Then, it
is guaranteed that from all $x(0,0)\in\mathcal{S}_{\leq}(0,r_{b})$,
$x(t,j)\in\mathcal{S}_{\leq}(0,r_{b})$ for all $(t,j)\in\operatorname{dom}x$.
Moreover, since the projection matrix $\pi^{\perp}(E_{i}(x-c_{i}))$ has
eigenvalues in $0$ and $1$, it follows that we can upper bound the control
input in (16) by $\|u\|\leq k\alpha(r_{b}+p)$ where
$k=\max\\{k_{1},k_{0},k_{-1}\\}$,
$\alpha=\max_{i\in\mathbb{I}}(\lambda_{\max}(E_{i})/\lambda_{\min}(E_{i}))$
and $p=\max_{i\in\mathbb{I}}\|p_{1}^{i}\|$. The control gains can then be
tuned to satisfy the inherent practical saturation of the actuators.

####  V-C2 Semiglobal Preservation

The second property is the so-called semiglobal preservation property [18,
§II]. This property is desirable when the original controller parameters are
optimally tuned and the controller modifications imposed by the presence of
the obstacles should be as minimal as possible. Such a property is also
accounted for in the quadratic programming formulation of [29, III.A.]. We
summarize this property for our case in the next proposition.

###### Proposition 1

Be $\epsilon\in(0,1)$ and
$\mathcal{W}_{\epsilon}:=\bigcap_{i^{\prime}\in\mathbb{I}}\mathcal{E}_{\geq}(c_{i^{\prime}},\epsilon
E_{i^{\prime}})$. There exist controller parameters such that the control law
matches, in $\mathcal{W}_{\epsilon}$, the stabilization feedback $u=-k_{0}x$
($k_{0}>0$) used in the absence of obstacles.

####  V-C3 Non-point Mass Vehicles

There is no loss of generality in considering a point-mass vehicle in this
work. Let us rather consider that the vehicle has some volume, e.g., bounded
by $\mathcal{S}_{\leq}(x,r_{v})$. Then, for the navigation scenario to be
feasible, the radius $r_{v}$ of the vehicle needs to be smaller than the
smallest distance between the obstacles, i.e., for all
$i,i^{\prime}\in\mathbb{I}$ with $i\neq i^{\prime}$,
$r_{v}<\mathbf{dist}(\mathcal{E}_{\leq}(c_{i},E_{i}),\mathcal{E}_{\leq}(c_{i^{\prime}},E_{i^{\prime}}))$.
For the safety of the vehicle during the stabilization mode, selecting the
parameter $\epsilon_{i}$ as $\epsilon_{i}<(1+\lambda_{\max}(E_{i})r_{v})^{-1}$
is sufficient (in addition to Table I) to guarantee that the vehicle starts
the avoidance mode away from the obstacle. Indeed, under this condition, it is
easy to show that for all $x\in\mathcal{E}_{\geq}(c_{i},\epsilon_{i}E_{i})$
(i.e., the vehicle center is outside the dilated ellipsoid
$\mathcal{E}(c_{i},\epsilon_{i}E_{i})$) and for all
$x^{\prime}\in\mathcal{S}_{\leq}(x,r_{v})$, one has
$x^{\prime}\in\mathcal{E}_{\geq}(c_{i},E_{i})$, which guarantees safety of the
whole volume of the vehicle.

####  V-C4 Robustness

The constructed hybrid controller guarantees some level of robustness to
perturbations (e.g., in the form of measurement noise). Hysteresis switching
is one of the typical ways to ensure robustness to measurement noise, and
hysteresis switching is indeed behind the designed hybrid feedback, in
particular the hysteresis regions of flow and jump sets in Section IV-B and
the logical selections of the jump sets in Section IV-C. More generally,
fundamental results in [24, Chap. 7] guarantee structurally that global
asymptotic stability of $\mathcal{A}$ in Theorem 2 is also uniform (by [24,
Thm. 7.12]) and robust (by [24, Thm. 7.21]) with respect to perturbations
since $\mathcal{A}$ is a compact set and the hybrid basic conditions are
satisfied as in Lemma 6.

##  VI Simulations

We illustrate the effectiveness of the proposed hybrid control strategy
through two simulation scenarios. The first scenario considers $9$ obstacles
in $2$D (see Fig. 6) while the second one considers $5$ obstacles in $3$D (see
Fig. 7). For both cases, Table I provides a suitable order to choose the
parameters for each $i\in\mathbb{I}$, as follows.

  1. 1)

For $\underline{\delta}_{i}$ in (27a), select $\delta_{i}$ and $\epsilon_{i}$
so that $\underline{\delta}_{i}<\delta_{i}<\epsilon_{i}<1$;

  2. 2)

For $\delta_{i}$ and $\bar{\mu}_{i}(\delta_{i})$ in (27b), select $\nu_{i}$
and $\mu_{i}$ so that $1<\nu_{i}<\mu_{i}<\bar{\mu}_{i}(\delta_{i})$ (possibly
iterating steps 1) and 2) so that $\delta_{i}$ and $\mu_{i}$ satisfy (40));

  3. 3)

For $\delta_{i}$, $\mu_{i}$ and $\bar{\theta}_{i}(\delta_{i},\mu_{i})$ in
(27c), select $\psi_{i}$, $\bar{\psi}_{i}$ and $\theta_{i}$ so that
$0<\psi_{i}<\bar{\psi}_{i}<\theta_{i}<\bar{\theta}_{i}(\delta_{i},\mu_{i})$.

Any parameter selection according to this guideline guarantees our results,
and can be carried out keeping in mind the physical interpretation illustrated
in Section IV-B for these parameters. The gains are $k_{0}=k_{1}=k_{-1}=1/4$
and determine the speed of convergence of the scheme. By (18a), the point
$p_{1}^{i}$ can be selected arbitrarily as long as it is on
$\mathcal{C}(c_{i},-c_{i},\theta_{i},E_{i})\backslash\\{c_{i}\\}$. A suitable
choice is given by

$p_{1}^{i}=\pi^{\perp}(E_{i}^{-1}\mathbf{R}(\theta_{i})E_{i}c_{i})c_{i}$ (41)

where $\mathbf{R}(\theta_{i})$ is the standard $2\times 2$ rotation matrix
with angle $\theta_{i}$ or the standard $3\times 3$ axis-angle rotation matrix
with angle $\theta_{i}$ and an arbitrary vector of $\mathbb{S}^{2}$ as axis.
The idea behind (41) is to project $c_{i}$ on the plane orthogonal to a
rotated version of $c_{i}$, in order to obtain the point lying on the cone and
closest to the origin. Having all points $p_{m}^{i}$ close enough to the
origin is an effective way so that $k_{0}$, $k_{1}$, $k_{-1}$ can take the
same values and yield comparable speeds for avoidance and stabilization,
independently of the obstacles.

Figure 6: Plot (at time $t=0.5$ and $t=30$ seconds) of the $2$-dimensional
trajectory of the vehicle starting at different initial conditions.

Fig. 6 (Fig. 7, respectively) shows that the solution generated by the closed
loop hybrid system avoids the $2$D obstacles ($3$D obstacles, respectively)
and Fig. 8 shows the convergence of solutions to the origin. Complete
simulation videos for the $2$D and $3$D cases can be found at
https://youtu.be/CnXJlhzlzd8, https://youtu.be/4mzTXPR6D9Y.

Finally, we note that for the very obstacle configuration of the 2D scenario,
the state-of-the-art approach of navigation functions [3, 21] cannot be
applied since the condition [21, Thm. 3, Eq. (23)] is violated for all
obstacles except obstacle $\mathcal{O}_{5}$, where [21, Eq. (23)] intuitively
corresponds to the fact that obstacles are not too flat and not too close to
the target position. ([21, Eq. (23)] is violated for all obstacles of the 3D
scenario.) Moreover, navigation function approaches require tuning a parameter
sufficiently large ($k$ in [21, Eq. (17) and Remark 5]), which may conflict
with actuator limitations. Instead, our approach provides a clear tuning
guideline for all parameters (given in this section) and actuator limitations
can be taken into account (see Section V-C1).

Figure 7: Plot (at time $t=30$ seconds) of the $3$-dimensional trajectory of
the vehicle starting at different initial conditions.

Figure 8: Plot of the position norm $\|x\|$ versus time showing the
convergence of the solutions to the origin from the considered initial
conditions.

##  VII Conclusions

We proposed a novel hybrid feedback on $\mathbb{R}^{n}$ to solve the obstacle
avoidance problem for arbitrarily flat ellipsoidal obstacles. Our control
strategy ensures global asymptotic stabilization to the target and safety
(thus, successful navigation from all initial conditions) while guaranteeing a
Zeno-free switching between the avoidance and stabilization modes. Moreover,
the control input remains bounded (in particular, arbitrarily close to any
obstacle) and matches semi-globally in the free-state space the nominal
feedback used in the absence of obstacles.

Future work will be devoted to considering more complex vehicle dynamics
(e.g., under-actuated and second-order dynamics) and more generic obstacle
shapes (e.g., convex obstacles). Furthermore, although our scheme considers
static obstacles to obtain formal guarantees for global asymptotic stability
and safety, extending this approach to deal with unknown environments is an
interesting research direction that we aim at pursuing in the future.

In the appendix, an equation number over an (in)equality indicates which
equation has been used to obtain the (in)equality.

####  -1 Proof of Theorem 1

Define $\mathbf{S}_{\mathscr{H}}(\mathcal{K})$ as the set of all maximal
solutions $\phi$ to $\mathscr{H}$ with $\phi(0,0)\in\mathcal{K}$. Each
$\phi\in\mathbf{S}_{\mathscr{H}}(\mathcal{K})$ has range
$\operatorname{rge}\phi\subset\mathcal{K}=\mathcal{F}\cup\mathcal{J}$ by Lemma
7 and the definition of hybrid solution [24, p. 124], so $\mathcal{K}$ is
forward pre-invariant [30, Def. 3.3]. The set $\mathcal{K}$ is in fact forward
invariant [30, Def. 3.3] if for each $\xi\in\mathcal{K}$ there exists one
solution and each $\phi\in\mathbf{S}_{\mathscr{H}}(\mathcal{K})$ is complete,
which we show in the rest of the proof through [24, Prop. 6.10]. In the rest
of the proof, let

$\mathcal{F}_{0}^{*}:=\bigcap_{i\in\mathbb{I}}\mathcal{F}_{0}^{i},\quad\mathcal{J}_{0}^{*}:=\bigcup_{i\in\mathbb{I}}\mathcal{J}_{0}^{i}.$
(42)

###### Lemma 10

Under the assumptions of Theorem 1, we have for each $i\in\mathbb{I}$ and
$m\in\\{-1,1\\}$

$\displaystyle\mathcal{J}_{0}^{i}=\mathcal{H}_{i}(\epsilon_{i},\nu_{i}),$
(43a)
$\displaystyle\mathcal{F}_{m}^{i}=\mathcal{H}_{i}(\delta_{i},\mu_{i})\cap\mathcal{C}_{\geq}(c_{i},c_{i}-p_{m}^{i},\psi_{i},E_{i}),$
(43b)
$\displaystyle\partial\mathcal{F}_{0}^{*}\backslash\mathcal{J}_{0}^{*}\subset\bigcup_{i\in\mathbb{I}}\big{(}\mathcal{E}(c_{i},E_{i})\backslash\mathcal{E}_{\geq}(\bar{c}_{i},\bar{E}_{i})\big{)},$
(43c) $\displaystyle\begin{aligned}
\partial\mathcal{F}_{m}^{i}\backslash\mathcal{J}_{m}^{i}\subset&\mathcal{E}(c_{i},E_{i})\backslash(\mathcal{E}_{\leq}(\bar{c}_{i},\mu_{i}\bar{E}_{i})\\\
&\cup\mathcal{C}_{\leq}(c_{i},c_{i}\\!-\\!p_{m}^{i},\psi_{i},E_{i})).\end{aligned}$
(43d)

First, let us show that the viability condition

$\displaystyle\mathbf{F}(x,i,m)\cap\mathbf{T}_{\mathcal{F}}(x,i,m)\neq\emptyset$
(44)

holds for all $(x,i,m)\in\mathcal{F}\backslash\mathcal{J}$. Let
$(x,i,m)\in\mathcal{F}\backslash\mathcal{J}$, which implies by (30c) that
$(x,i)\in\mathcal{F}_{m}\backslash\mathcal{J}_{m}$ for some $m\in\mathbb{M}$,
and divide into the cases $m=0$ and $m\in\\{-1,1\\}$. When $m=0$, from (25)
there exists $i\in\mathbb{I}$ such that
$x\in\mathcal{F}_{0}^{*}\backslash\mathcal{J}_{0}^{*}$. If
$x\in(\mathcal{F}_{0}^{*})^{\circ}\backslash\mathcal{J}_{0}^{*}$ (hence, $x$
is in the interior of $\mathcal{F}_{0}^{*}$), then
$\mathbf{T}_{\mathcal{F}_{0}^{*}}(x)=\mathbb{R}^{n}$, so that
$\mathbf{T}_{\mathcal{F}}(\xi)=\mathbb{R}^{n}\times\\{0\\}\times\\{0\\}$ and
(44) holds. If $x\in\partial\mathcal{F}_{0}^{*}\backslash\mathcal{J}_{0}^{*}$,
which satisfies the set inclusion (43c), the weak pairwise disjointness of
$\\{\mathcal{E}(c_{i},E_{i})\\}_{i\in\mathbb{I}}$ yields:

$\displaystyle x\in\mathcal{E}(c_{i},E_{i}),\,i\in\mathbb{I}$ (45)
$\displaystyle\mathbf{T}_{\mathcal{F}}(x,i,0)=\mathcal{P}_{\geq}(0,E_{i}^{2}(x-c_{i}))\times\\{0\\}\times\\{0\\}.$

By (19) and $x\notin\mathcal{E}_{\geq}(\bar{c}_{i},\bar{E}_{i})$ by (43c), we
obtain

$-\\!k_{0}x^{\top}\\!E_{i}^{2}(x\\!-\\!c_{i})=k_{0}\|E_{i}\bar{c}_{i}\|^{2}\\!\left(1\\!-\\!\|\bar{E}_{i}(x-\bar{c}_{i})\|^{2}\right)\\!>\\!0,$
(46)

hence, $\kappa(x,i,0)\in\mathcal{P}_{\geq}(0,E_{i}^{2}(x-c_{i}))$ in (45), and
(44) holds for $m=0$. When $m\in\\{-1,1\\}$, we have $i\in\mathbb{I}$ and
$x\in\partial\mathcal{F}_{m}^{i}\backslash\mathcal{J}_{m}^{i}$, which
satisfies the set inclusion (43d), and so

$\mathbf{T}_{\mathcal{F}}(x,i,m)=\mathcal{P}_{\geq}(0,E_{i}^{2}(x-c_{i}))\times\\{0\\}\times\\{0\\}.$
(47)

$\kappa(x,i,m)\in\mathcal{P}_{\geq}(0,E_{i}^{2}(x-c_{i}))$ in (47) because

$-k_{m}(x-p_{m}^{i})^{\top}E_{i}\pi^{\perp}(E_{i}(x-c_{i}))E_{i}(x-c_{i})=0,$
(48)

so the viability condition (44) holds for $m\in\\{-1,1\\}$ as well.

Second, we apply [24, Prop. 6.10]. By it and (44), there exists a nontrivial
solution to $\mathscr{H}$ from each initial condition in $\mathcal{K}$. Finite
escape times can only occur through flow. They can neither occur for $x$ in
the set $\mathcal{F}_{-1}^{i}\cup\mathcal{F}_{1}^{i}$ ($\mathcal{F}_{-1}^{i}$
and $\mathcal{F}_{1}^{i}$ are bounded by their definitions in (26)) nor for
$x$ in the set $\mathcal{F}_{0}^{*}$ because they would make $x^{\top}x$ grow
unbounded, and this would contradict that $\tfrac{d}{dt}(x^{\top}x)\leq 0$ by
the definition of $\kappa(x,i,0)$ and by (30a). So, all maximal solutions do
not have finite escape times. By Lemma 7,
$\mathbf{J}(\mathcal{J})\subset\mathcal{K}=\mathcal{F}\cup\mathcal{J}$. Hence,
by [24, Prop. 6.10], all maximal solutions are complete.

####  -2 Proof of Theorem 2

We prove global asymptotic stability of $\mathcal{A}$ by [24, Def. 7.1]. For
each $i\in\mathbb{I}$,
$\|\delta_{i}E_{i}c_{i}\|=\delta_{i}\underline{\delta}_{i}^{-2}>\delta_{i}\underline{\delta}_{i}^{-1}>1$
by Assumption 2 and the selection of $\delta_{i}$ in Table I, so
$0\notin\mathcal{E}_{\leq}(c_{i},\delta_{i}E_{i})$. As a consequence, there
exists $\varepsilon^{*}>0$ such that the ball
$\mathcal{S}_{\leq}(0,\varepsilon^{*})$ does not intersect with any of the
dilated obstacles $\mathcal{E}_{\leq}(c_{i},\delta_{i}E_{i})$. It can be shown
easily that for each $\varepsilon\in[0,\varepsilon^{*}]$, the set
$\mathcal{S}:=\mathcal{S}_{\leq}(0,\varepsilon)\times\mathbb{I}\times\mathbb{M}$
is forward invariant because $\mathcal{S}_{\leq}(0,\varepsilon)$ is disjoint
from $\mathcal{J}_{0}^{*}$ and the component $x$ of solutions evolves, after
at most one jump, with the stabilization mode $\dot{x}=-k_{0}x$. Thanks to
forward invariance of $\mathcal{S}$, stability of $\mathcal{A}$ for (30) is
immediate from [24, Def. 7.1]. Let us prove global attractivity of
$\mathcal{A}$.Before that, we need the next intermediate result.

###### Lemma 11

There exists $\sigma>0$ such that for all solutions $\xi=(x,i,m)$ with
$\xi(t,j)\in\mathcal{F}_{l}\times\\{l\\}$ for some $l\in\\{-1,1\\}$ and
$(t,j)\in\operatorname{dom}\xi$, there exists
$(s,\ell)\in\operatorname{dom}\xi$ such that $(s,\ell)\succeq(t,j)$ and

$\|x(s,\ell)\|\leq\|x(t,j)\|-\sigma.$ (49)

Now, for each solution $\xi$ to (30), there exists a finite time
$(T,J)\succeq(0,0)$ after which the solution does not evolve with the
avoidance controller any longer, i.e., $m(t,j)=0$ for all $(t,j)\succeq(T,J)$.
Otherwise, there would exist a sequence of hybrid times
$\\{(t_{k},j_{k})\\}_{k=0}^{\infty}$ such that
$\xi(t_{k},j_{k})\in\mathcal{F}_{l_{k}}\times\\{l_{k}\\}$ with
$l_{k}\in\\{-1,1\\}$ and this would imply by Lemma 11 that
$\|x(t_{k+1},j_{k+1})\|\leq\|x(t_{k},j_{k})\|-\sigma$ for all
$k\in\mathbb{N}$. This is indeed a contradiction as it would lead to
$\|x(\cdot,\cdot)\|$ becoming negative. Then, the solution $\xi$ enters the
stabilizing mode $m=0$ after $(T,J)$ and its flow map $\dot{x}=-k_{0}x$
guarantees in turn global attractivity. Moreover, $J$ is the maximum number of
jumps of the hybrid system since any extra jump will cause $m$ to take values
in $\\{-1,1\\}$, which is not possible after $(T,J)$.

####  -3 Proof of Theorem 3

To prove the theorem, it is sufficient to show that for spherical obstacles
the result of Lemma 11 holds. The proof of Lemma 11 under the assumptions of
Theorem 3 is the same up to (85). From (85) we have
$x(t^{\prime},j+1)=x(t^{\prime},j)\in\tilde{\mathcal{P}}_{m(t^{\prime},j),3}^{i(t^{\prime},j)}(\delta,\psi)$,
$i(t^{\prime},j+1)=i(t^{\prime},j)=:\iota$ and $m(t^{\prime},j)=0$. However,
since $x(t,j)$ and $x(t^{\prime},j+1)$ both belong to
$\mathcal{E}(c_{\iota},\delta E_{\iota})$, we can write
$\|x(t,j)-c_{\iota}\|^{2}=\|x(t^{\prime},j+1)-c_{\iota}\|^{2}$ (since
$E_{\iota}=\lambda_{\iota}I_{n}$) and hence

$\displaystyle\|x(t,j)\|^{2}-2c_{\iota}^{\top}x(t,j)=\|x(t^{\prime},j+1)\|^{2}-2c_{\iota}^{\top}x(t^{\prime},j+1).$
(50)

$x(t^{\prime},j+1)\in\tilde{\mathcal{P}}_{0,3}^{\iota}(\delta,\psi)\subset\mathcal{E}(\bar{c}_{\iota},\mu_{\iota}\bar{E}_{\iota})$
implies also that

$c_{\iota}^{\top}x(t^{\prime},j+1)=\|x(t^{\prime},j+1)\|^{2}+(1-\mu_{\iota}^{-2})\|\bar{c}_{\iota}\|^{2},$

thus, with (50), we have

$c_{\iota}^{\top}x(t,j)=\frac{\|x(t,j)\|^{2}+\|x(t^{\prime},j+1)\|^{2}}{2}+(1-\mu_{\iota}^{-2})\|\bar{c}_{\iota}\|^{2}.$

However, since
$x(t,j)\in\mathcal{E}_{\geq}(\bar{c}_{\iota},\mu_{\iota}\bar{E}_{\iota})$, we
have

$c_{\iota}^{\top}x(t,j)\leq\|x(t,j)\|^{2}+(1-\mu_{\iota}^{-2})\|\bar{c}_{\iota}\|^{2},$

and, hence, $\|x(t^{\prime},j+1)\|^{2}\leq\|x(t,j)\|^{2}$ must hold. Also, by
(85), $x(t^{\prime},j+1)\in\mathcal{E}(c_{\iota},\delta
E_{\iota})\cap\mathcal{E}(\bar{c}_{\iota},\mu_{\iota}\bar{E}_{\iota})$, and,
by Lemma 8,
$x(t^{\prime},j+1)\in\mathcal{C}(0,c_{\iota},\vartheta_{\iota}(\delta,\mu_{\iota}),E_{\iota})$.
In view of Step 2 of the proof of Lemma 11, both the sets
$\mathcal{E}_{\leq}(\bar{c}_{\iota},\bar{E}_{\iota})$ and
$\mathcal{C}(0,c_{\iota},\vartheta_{\iota}(\delta,\mu_{\iota}),E_{\iota})$ are
forward invariant under the stabilization flow map for $x$, i.e., $-k_{0}x$.
Since the obstacles are weakly disjoint, the solution then flows in
$\mathcal{E}_{\leq}(\bar{c}_{\iota},\bar{E}_{\iota})\cap\mathcal{C}(0,c_{\iota},\vartheta_{\iota}(\delta,\mu_{\iota}),E_{\iota})$
until it reaches the set $\mathcal{E}(c_{\iota},\delta_{\iota}E_{\iota})$ at
$(t^{\prime\prime},j+1)$. Since flow with stabilization mode decreases the
distance to the origin we have

$\|x(t^{\prime\prime},j+1)\|^{2}\leq\|x(t^{\prime},j+1)\|^{2}\leq\|x(t,j)\|^{2}$

Also, the solution must flow after $(t^{\prime\prime},j+1)$ up to some
$(s,j+1)$ with the stabilization mode (since obstacles are weakly disjoint)
such that at least $\sigma_{1}$ in (86) is traversed, i.e.,

$\|x(s,j+1)\|^{2}+\sigma_{1}\leq\|x(t^{\prime\prime},j+1)\|^{2}\leq\|x(t,j)\|^{2}.$

This proves Lemma 11 and in turn Theorem 2.

####  -4 Proof of Proposition 1

Note preliminarily that thanks to $\epsilon<1$,
$\mathcal{W}_{\epsilon}\subset\mathcal{W}$ in (14). It is sufficient to show
that the closed loop system under the proposed hybrid feedback cannot flow
except with stabilization mode $m=0$ when $x\in\mathcal{W}_{\epsilon}$.
Indeed, if in Table I we further constrain $\delta_{i}$ as
$\delta_{i}\in(\max(\underline{\delta}_{i},\epsilon),1)$ for all
$i\in\mathbb{I}$, then
$\mathcal{F}_{m}^{i}\subset\mathcal{H}(\delta_{i},\mu_{i})\subset\mathcal{E}_{\leq}(c_{i},\delta_{i}E_{i})\subset\mathcal{E}_{\leq}(c_{i},\epsilon
E_{i})$ and
$\mathcal{E}_{\leq}(c_{i},\delta_{i}E_{i})\neq\mathcal{E}_{\leq}(c_{i},\epsilon
E_{i})$. Therefore, we have
$\mathcal{F}_{m}^{i}\cap\mathcal{W}_{\epsilon}=\emptyset$ for all
$i\in\mathbb{I}$ and $m\in\\{-1,1\\}$. This implies that solutions cannot flow
with the avoidance mode when $x$ belongs to $\mathcal{W}_{\epsilon}$ and must
then flow with the stabilization mode.

####  -5 Proof of Lemma 1

Let $x_{l}\in\mathcal{C}_{\leq}(c,E^{-1}v_{l},\psi_{l},E)\backslash\\{c\\}$,
$l=1,2$, and be otherwise arbitrary. Define then
$z_{l}:=E(x_{l}-c)/\|E(x_{l}-c)\|\in\mathbb{S}^{n-1}$ for $l=1,2$. Hence,
$z_{l}\in\mathcal{S}_{l}:=\mathcal{C}_{\leq}(0,v_{l},\psi_{l},I_{n})\cap\mathbb{S}^{n-1}$,
$l=1,2$. For $l=1,2$, $z_{l}$ satisfies, by (11), $\cos(\psi_{l})\leq
z_{l}^{\top}v_{l}$, and consequently
$\mathbf{d}_{\mathbb{S}^{n-1}}(v_{l},z_{l})\leq\psi_{l}$. It follows from the
triangle inequality that
$\theta=\mathbf{d}_{\mathbb{S}^{n-1}}(v_{1},v_{2})\leq\mathbf{d}_{\mathbb{S}^{n-1}}(v_{1},z_{1})+\mathbf{d}_{\mathbb{S}^{n-1}}(z_{1},z_{2})+\mathbf{d}_{\mathbb{S}^{n-1}}(v_{2},z_{2})\leq\mathbf{d}_{\mathbb{S}^{n-1}}(z_{1},z_{2})+\psi_{1}+\psi_{2}.$
Hence, in view of the condition $\psi_{1}+\psi_{2}<\theta$,
$\mathbf{d}_{\mathbb{S}^{n-1}}(z_{1},z_{2})>0$. This fact implies that the
compact sets $\mathcal{S}_{1}$ and $\mathcal{S}_{2}$ (and in turn
$\mathcal{C}_{\leq}(c,E^{-1}v_{l},\psi_{l},E)\backslash\\{c\\}$, $l=1,2$) are
disjoint.

####  -6 Proof of Lemma 2

First, by (18b) and (3) we have

$\displaystyle
p_{-1}^{i}-c_{i}=-E_{i}^{-1}\rho(E_{i}c_{i})E_{i}(p_{1}^{i}-c_{i})\text{,
hence }$ (51)
$\displaystyle\|E_{i}(p_{-1}^{i}-c_{i})\|^{2}\overset{\eqref{eq:difference}}{=}(p_{1}^{i}-c_{i})^{\top}E_{i}\rho(E_{i}c_{i})\rho(E_{i}c_{i})E_{i}(p_{1}^{i}-c_{i})$
$\displaystyle\hskip
10.0pt\overset{\eqref{eq:propLine3}}{=}(p_{1}^{i}-c_{i})^{\top}E_{i}^{2}(p_{1}^{i}-c_{i})=\|E_{i}(p_{1}^{i}-c_{i})\|^{2}$
(52)

(so that $p^{i}_{1}\neq c_{i}$ implies $p^{i}_{-1}\neq c_{i}$). Based on (11)
for $\mathcal{C}(c_{i},-c_{i},\theta_{i},E_{i})$, one has

$\displaystyle-
c_{i}^{\top}E_{i}^{2}(p_{-1}^{i}-c_{i})\overset{\eqref{eq:difference}}{=}c_{i}^{\top}E_{i}\rho(E_{i}c_{i})E_{i}(p_{1}^{i}-c_{i})$
$\displaystyle\quad\overset{\eqref{eq:propLine3}}{=}-c_{i}^{\top}E_{i}^{2}(p_{1}^{i}-c_{i})\\!\overset{\eqref{eq:p_1}}{=}\\!\cos(\theta_{i})\|E_{i}(-c_{i})\|\|E_{i}(p_{1}^{i}-c_{i})\|$
$\displaystyle\quad\overset{\eqref{eq:equalnorm}}{=}\cos(\theta_{i})\|E_{i}(-c_{i})\|\|E_{i}(p_{-1}^{i}-c_{i})\|.$

This concludes by (11) that
$p_{-1}^{i}\in\mathcal{C}(c_{i},-c_{i},\theta_{i},E_{i})\backslash\\{c_{i}\\}$.

####  -7 Proof of Lemma 3

As for the $\Longrightarrow$ implication, let
$x\in\mathbb{R}^{n}\backslash\\{c\\}$ be such that
$\pi^{\perp}(E(x-c))E(x-p)=0$, which is equivalent to
$\pi^{\perp}(E(x-c))E(p-c)=0$. By substituting the definition of
$\pi^{\perp}(\cdot)$ in (3), one obtains
$\|E(x-c)\|^{2}(p-c)=\big{(}(p-c)^{\top}E^{2}(x-c)\big{)}(x-c)$. This very
equation excludes that $(p-c)^{\top}E^{2}(x-c)=0$ since $E$ is positive
definite, $x\neq c$, and $p\neq c$ by assumption. So, letting
$\lambda=\|E(x-c)\|^{2}/\big{(}(p-c)^{\top}E^{2}(x-c)\big{)}$ in (7), one
deduces that $x\in\mathcal{L}(c,p-c)$. The $\Longleftarrow$ implication is
straightforward.

####  -8 Proof of Lemma 4

The quantities in (27b)-(27c) are well-defined. Indeed, we have for (27b) that
$1-4\underline{\delta}_{i}^{2}(1-\underline{\delta}_{i}^{2}/\delta_{i}^{2})=(2\underline{\delta}_{i}^{2}-1)^{2}+4\underline{\delta}_{i}^{4}(\delta_{i}^{-2}-1)>0$
thanks to $\delta_{i}\in(\underline{\delta}_{i},1)$. Moreover, by
$\mu_{i}\in(1,\bar{\mu}_{i}(\delta_{i}))$, the argument of the $\arccos$ in
(27c) belongs to $(0,1)$, so $\bar{\theta}_{i}(\delta_{i},\mu_{i})$ is also
well-defined. Now, define

$\displaystyle\hat{\mathcal{F}}_{m}^{i}:=$
$\displaystyle\mathcal{E}_{\leq}(c_{i},\delta_{i}E_{i})\cap\mathcal{E}_{\geq}(\bar{c}_{i},\mu_{i}\bar{E}_{i})\cap$
(53)
$\displaystyle\mathcal{C}_{\geq}(c_{i},c_{i}-p_{m}^{i},\psi_{i},E_{i})\cap\mathcal{E}_{\geq}(c_{i},E_{i})\supset\mathcal{F}_{m}^{i}.$

By proving that for each $i\in\mathbb{I}$ and $m\in\\{-1,1\\}$

$\mathcal{L}(c_{i},p_{m}^{i}-c_{i})\cap\hat{\mathcal{F}}_{m}^{i}=\emptyset,$
(54)

the claim of the lemma is also proven. We prove then (54) for an arbitrary
$i\in\mathbb{I}$ and an arbitrary $m\in\\{-1,1\\}$. For this proof, select the
following angle $\psi_{i}^{\prime}$ as _any_ angle
$\psi_{i}^{\prime}\in(0,\psi_{i})$. First, let us show that the following set
inclusions hold

$\displaystyle\mathcal{L}_{\leq}(c_{i},p_{m}^{i}-c_{i})\subset\mathcal{C}_{\leq}(c_{i},c_{i}-p_{m}^{i},\psi_{i}^{\prime},E_{i}),$
(55a)
$\displaystyle\mathcal{L}_{\geq}(c_{i},p_{m}^{i}-c_{i})\subset\mathcal{C}(c_{i},-c_{i},\theta_{i},E_{i}).$
(55b)

Let $x\in\mathcal{L}_{\leq}(c_{i},p_{m}^{i}-c_{i})$. Then there exists
$\lambda\leq 0$ such that $x-c_{i}=\lambda(p_{m}^{i}-c_{i})$. Such $x-c_{i}$
verifies the condition
$\cos(\psi_{i}^{\prime})\|E_{i}(c_{i}-p_{m})\|\|E_{i}(x-c_{i})\|\leq(c_{i}-p_{m}^{i})^{\top}E^{2}(x-c_{i})$
corresponding to
$\mathcal{C}_{\leq}(c_{i},c_{i}-p_{m},\psi_{i}^{\prime},E_{i})$ by simple
computations for any $0<\psi_{i}^{\prime}<\psi_{i}$ (since
$\cos(\psi_{i}^{\prime})\leq 1$). This proves (55a). Now, let
$x\in\mathcal{L}_{\geq}(c_{i},p_{m}^{i}-c_{i})$. Then there exists
$\lambda\geq 0$ such that $x-c_{i}=\lambda(p_{m}^{i}-c_{i})$. Such $x-c_{i}$
verifies the condition
$\cos(\theta_{i})\|E_{i}(-c_{i})\|\|E_{i}(x-c_{i})\|=-c_{i}^{\top}E_{i}^{2}(x-c_{i})$
corresponding to $\mathcal{C}(c_{i},-c_{i},\theta_{i},E_{i})$ by simple
computations using that
$\cos(\theta_{i})\|E_{i}(-c_{i})\|\|E_{i}(p_{m}^{i}-c_{i})\|=-c_{i}^{\top}E_{i}^{2}(p_{m}^{i}-c_{i})$
(corresponding to $p_{m}^{i}\in\mathcal{C}(c_{i},-c_{i},\theta_{i},E_{i})$
from (18a) and Lemma 2). This proves (55b). Second, from (55) one has

$\displaystyle\\!\\!\\!\\!\\!\hat{\mathcal{F}}_{m}^{i}\cap\mathcal{L}(c_{i},p_{m}^{i}-c_{i})$
$\displaystyle\\!\\!\\!\\!\\!\\!=(\hat{\mathcal{F}}_{m}^{i}\cap\mathcal{L}_{\leq}(c_{i},p_{m}^{i}-c_{i}))\cup(\hat{\mathcal{F}}_{m}^{i}\cap\mathcal{L}_{\geq}(c_{i},p_{m}^{i}-c_{i}))$
$\displaystyle\\!\\!\\!\\!\\!\\!\\!\subset\\!\\!(\hat{\mathcal{F}}_{m}^{i}\\!\cap\\!\mathcal{C}_{\leq}(c_{i},c_{i}\\!-\\!p_{m}^{i},\psi_{i}^{\prime},E_{i}))\\!\cup\\!(\hat{\mathcal{F}}_{m}^{i}\\!\cap\\!\mathcal{C}(c_{i},\\!-c_{i},\theta_{i},E_{i}))$
(56)

and we prove that the two intersections in (56) are empty. Since
$0<\psi_{i}^{\prime}<\psi_{i}$, one obtains readily from the definition of the
cone in (11) that

$\mathcal{C}_{\geq}(c_{i},c_{i}-p_{m}^{i},\psi_{i},E_{i})\cap\mathcal{C}_{\leq}(c_{i},c_{i}-p_{m}^{i},\psi_{i}^{\prime},E_{i})=\\{c_{i}\\}.$

This relationship and the definition of $\hat{\mathcal{F}}_{m}^{i}$ in (53)
imply that the first intersection in (56) is empty. We show now that the
second intersection in (56) is also empty. Let
$x\in\hat{\mathcal{F}}_{m}^{i}\cap\mathcal{C}(c_{i},-c_{i},\theta_{i},E_{i})$.
So,

$\displaystyle
c_{i}^{\top}E_{i}^{2}(x-c_{i})\overset{\eqref{eq:ci,Ei}}{=}-(x-c_{i})^{\top}\\!E_{i}^{2}(x-c_{i})$
$\displaystyle\qquad+\tfrac{1}{4}c_{i}^{\top}\\!E_{i}^{2}c_{i}\,(x\\!-\\!\bar{c}_{i})^{\top}\\!\bar{E}_{i}^{2}(x\\!-\\!\bar{c}_{i})-\tfrac{1}{4}c_{i}^{\top}\\!E_{i}^{2}c_{i}$
$\displaystyle=-\|E_{i}(x-c_{i})\|^{2}+\tfrac{1}{4}\|E_{i}c_{i}\|^{2}\|\bar{E}_{i}(x-\bar{c}_{i})\|^{2}-\tfrac{1}{4}\|E_{i}c_{i}\|^{2}$
$\displaystyle\geq-\frac{1}{\delta_{i}^{2}}-\frac{1}{4}\|E_{i}c_{i}\|^{2}\Big{(}1-\frac{1}{\mu_{i}^{2}}\Big{)}$
(57)

where the bound holds since $x\in\hat{\mathcal{F}}_{m}^{i}$ implies
$x\in\mathcal{E}_{\leq}(c_{i},\delta_{i}E_{i})$ and
$x\in\mathcal{E}_{\geq}(\bar{c}_{i},\mu_{i}\bar{E}_{i})$. We continue (57) as

$\displaystyle
c_{i}^{\top}E_{i}^{2}(x-c_{i})\geq-\frac{1}{\delta_{i}^{2}}-\frac{1}{4}\|E_{i}c_{i}\|^{2}\Big{(}1-\frac{1}{\mu_{i}^{2}}\Big{)}$
$\displaystyle\overset{\eqref{eq:bar theta},\eqref{eq:bar
delta}}{=}-\cos(\bar{\theta}_{i}(\delta_{i},\mu_{i}))/\underline{\delta}_{i}^{2}\overset{\eqref{eq:bar
delta}}{=}-\cos(\bar{\theta}_{i}(\delta_{i},\mu_{i}))\|E_{i}c_{i}\|$
$\displaystyle\geq-\cos(\bar{\theta}_{i}(\delta_{i},\mu_{i}))\|E_{i}c_{i}\|\|E_{i}(x-c_{i})\|$
(58)

since $\cos(\bar{\theta}_{i}(\delta_{i},\mu_{i}))\geq 0$ and
$\|E_{i}(x-c_{i})\|\geq 1$ ($x\in\hat{\mathcal{F}}_{m}^{i}$ implies
$x\in\mathcal{E}_{\geq}(c_{i},E_{i})$). It is also
$x\in\mathcal{C}(c_{i},-c_{i},\theta_{i},E_{i})$. So,

$\displaystyle c_{i}^{\top}E_{i}^{2}(x-c_{i})$
$\displaystyle=-\cos(\theta_{i})\|E_{i}c_{i}\|\|E_{i}(x-c_{i})\|$ (59)
$\displaystyle<-\cos(\bar{\theta}_{i}(\delta_{i},\mu_{i}))\|E_{i}c_{i}\|\|E_{i}(x-c_{i})\|$

from the bound on $\theta_{i}$ in Table I. (58) and (59) contradict each
other, so the second intersection in (56) is _also_ empty. Then, (54) is
proven.

####  -9 Proof of Lemma 5

Given (30e)-(30f), we just need to show that $\mathbf{L}(x,i,0)\neq\emptyset$
for all $(x,i)\in\mathcal{J}_{0}$. This holds if we show, as we do in the rest
of the proof, that for each $x\in{}^{n}$ and $i\in\mathbb{I}$,
$\mathbf{M}(x,i)\neq\emptyset$. First, we show that
$\cap_{m=-1,1}\mathcal{C}_{\leq}(c_{i},c_{i}-p_{m}^{i},\bar{\psi}_{i},E_{i})=\\{c_{i}\\}$
for each $i\in\mathbb{I}$. To this end, note that
$p_{1}^{i}\in\mathcal{C}(c_{i},-c_{i},\theta_{i},E_{i})$ by (18a), and this
implies
$\cos^{2}(\theta_{i})\|E_{i}c_{i}\|^{2}\|E_{i}(p^{i}_{1}-c_{i})\|^{2}=(c_{i}^{\top}E_{i}^{2}(p^{i}_{1}-c_{i}))^{2}$
or, equivalently,

$(p^{i}_{1}-c_{i})^{\top}E_{i}\pi^{\theta_{i}}(E_{i}c_{i})E_{i}(p^{i}_{1}-c_{i})=0.$
(60)

Introduce then $v^{i}_{m}:=E_{i}(c_{i}-p_{m}^{i})/\|E_{i}(c_{i}-p_{m}^{i})\|$
for $m\in\\{-1,1\\}$, and compute

$\displaystyle(v^{i}_{1}$
$\displaystyle)^{\top}v^{i}_{-1}=\frac{(p_{1}^{i}-c_{i})^{\top}E_{i}^{2}(p_{-1}^{i}-c_{i})}{\|E_{i}(p_{1}^{i}-c_{i})\|\|E_{i}(p_{-1}^{i}-c_{i})\|}$
$\displaystyle\overset{\eqref{eq:equalnorm}}{=}-\frac{(p_{1}^{i}-c_{i})^{\top}E_{i}\rho(E_{i}c_{i})E_{i}(p_{1}^{i}-c_{i})}{\|E_{i}(p_{1}^{i}-c_{i})\|^{2}}$
$\displaystyle\overset{\eqref{eq:piTheta:3}}{=}-\frac{(p_{1}^{i}-c_{i})^{\top}E_{i}(2\pi^{\theta_{i}}(E_{i}c_{i})-\cos(2\theta_{i})I_{n})E_{i}(p_{1}^{i}-c_{i})}{\|E_{i}(p_{1}^{i}-c_{i})\|^{2}}$
$\displaystyle\overset{\eqref{eq:implied by p_1 on
cone}}{=}\frac{\cos(2\theta_{i})(p_{1}^{i}-c_{i})^{\top}E_{i}^{2}(p_{1}^{i}-c_{i})}{\|E_{i}(p_{1}^{i}-c_{i})\|^{2}}=\cos(2\theta_{i})$

Then, by Lemma 1 and $2\bar{\psi}_{i}<2\theta_{i}$,
$\cap_{m=-1,1}\mathcal{C}_{\leq}(c_{i},c_{i}-p_{m}^{i},\bar{\psi}_{i},E_{i})=\\{c_{i}\\}$.
Second, note that

$\cup_{m=-1,1}\mathcal{C}_{>}(c_{i},c_{i}-p_{m}^{i},\bar{\psi}_{i},E_{i})=\\\
\big{(}\cap_{m=-1,1}\mathcal{C}_{\leq}(c_{i},c_{i}-p_{m}^{i},\bar{\psi}_{i},E_{i})\big{)}^{\mathsf{c}}={}^{n}\backslash\\{c_{i}\\}.$
(61)

Therefore, we have

$\cup_{m=-1,1}\mathcal{C}^{i}_{m}\overset{\eqref{eq:Cim}}{=}\cup_{m=-1,1}\mathcal{C}_{\geq}(c_{i},c_{i}-p_{m}^{i},\bar{\psi}_{i},E_{i})=\mathbb{R}^{n}$
(62)

since $\cup_{m=-1,1}\mathcal{C}^{i}_{m}$ is a superset of the set in (61) and
contains $c_{i}$. So, for each $x\in{}^{n}$ and $i\in\mathbb{I}$,
$\mathbf{M}(x,i)\neq\emptyset$ in (30g).

####  -10 Proof of Lemma 6

$\mathcal{F}$ and $\mathcal{J}$ are closed subsets of
${}^{n}\times\\{-1,0,1\\}$. $\mathbf{F}$ is continuous on $\mathcal{F}$.
$\mathbf{J}(x,i,m)\neq\emptyset$ for each $(x,i,m)\in\mathcal{J}$ thanks to
Lemma 5 and $\mathbf{J}$ has a closed graph relative to $\mathcal{J}$ because,
in particular, the construction in (30g) allows $\mathbf{M}$ to be set-valued
whenever $x\in\cap_{m=-1,1}\mathcal{C}^{i}_{m}$. Then, $\mathbf{J}$ is outer
semicontinuous and locally bounded relative to $\mathcal{J}$.

####  -11 Proof of Lemma 7

If we prove that $\forall i\in\mathbb{I},\,m\in\\{-1,1\\}$

$\Big{(}\bigcap\limits_{i^{\prime}\in\mathbb{I}}\mathcal{F}_{0}^{i^{\prime}}\Big{)}\cup\Big{(}\bigcup\limits_{i^{\prime}\in\mathbb{I}}\mathcal{J}_{0}^{i^{\prime}}\Big{)}\\!=\\!\mathcal{W}\\!=\\!\mathcal{F}_{m}^{i}\cup\mathcal{J}_{m}^{i}$
(63)

then (25), (29a), (29b) imply straightforwardly
$\mathcal{F}_{0}\cup\mathcal{J}_{0}=\mathcal{W}\times\mathbb{I}=\mathcal{F}_{1}\cup\mathcal{J}_{1}=\mathcal{F}_{-1}\cup\mathcal{J}_{-1}$
and, in turn, (30c) implies
$\mathcal{F}\cup\mathcal{J}=\mathcal{W}\times\mathbb{I}\times\mathbb{M}=:\mathcal{K}$.
Therefore, we just need to prove (63) in the remainder. For each
$i\in\mathbb{I}$ and $m\in\\{-1,1\\}$,

$\mathcal{F}_{m}^{i}\cup\mathcal{J}_{m}^{i}\overset{\eqref{eq:F-11i},\eqref{eq:J^i_m}}{=}\Big{(}\mathcal{E}_{\leq}(c_{i},\delta_{i}E_{i})\cap\mathcal{E}_{\geq}(\bar{c}_{i},\mu_{i}\bar{E}_{i})\\\
\cap\mathcal{C}_{\geq}(c_{i},c_{i}-p_{m}^{i},\psi_{i},E_{i})\cap\mathcal{W}\Big{)}\cup\Big{(}\big{(}\mathcal{E}_{\geq}(c_{i},\delta_{i}E_{i})\cup\mathcal{E}_{\leq}(\bar{c}_{i},\mu_{i}\bar{E}_{i})\\\
\cup\mathcal{C}_{\leq}(c_{i},c_{i}\\!-\\!p_{m}^{i},\psi_{i},E_{i})\big{)}\cap\mathcal{W}\Big{)}=\mathcal{W}.$
(64)

We are left with proving
$\big{(}\bigcap\limits_{i^{\prime}\in\mathbb{I}}\mathcal{F}_{0}^{i^{\prime}}\big{)}\cup\big{(}\bigcup\limits_{i^{\prime}\in\mathbb{I}}\mathcal{J}_{0}^{i^{\prime}}\big{)}\\!=\\!\mathcal{W}$
in (63). First, note that for each $i^{\prime}$,
$\mathcal{H}_{i^{\prime}}\\!(\epsilon_{i^{\prime}},\nu_{i^{\prime}})\\!\cap\\!\mathcal{W}=\mathcal{E}_{\leq}(c_{i^{\prime}},\epsilon_{i^{\prime}}E_{i^{\prime}})\cap\mathcal{E}_{\geq}(\bar{c}_{i^{\prime}},\nu_{i^{\prime}}\bar{E}_{i^{\prime}})\cap\mathcal{W}$
and, hence,

$\displaystyle\big{(}\bigcap\limits_{i^{\prime}\in\mathbb{I}}\mathcal{F}_{0}^{i^{\prime}}\big{)}\cup\big{(}\bigcup\limits_{i^{\prime}\in\mathbb{I}}\mathcal{J}_{0}^{i^{\prime}}\big{)}=\bigcap_{i^{\prime}\in\mathbb{I}}\Big{(}\big{(}\mathcal{E}_{\geq}(c_{i^{\prime}},\epsilon_{i^{\prime}}E_{i^{\prime}})$
$\displaystyle\quad\cup\mathcal{E}_{\leq}(\bar{c}_{i^{\prime}},\nu_{i^{\prime}}\bar{E}_{i^{\prime}})\big{)}\cap\mathcal{W}\Big{)}\cup\bigcup_{i^{\prime}\in\mathbb{I}}\Big{(}\mathcal{H}_{i^{\prime}}(\epsilon_{i^{\prime}},\nu_{i^{\prime}})\cap\mathcal{W}\Big{)}$
$\displaystyle=\Big{(}\\!\bigcap_{i^{\prime}\in\mathbb{I}}\\!\\!\big{(}\mathcal{E}_{\geq}(c_{i^{\prime}},\epsilon_{i^{\prime}}E_{i^{\prime}})\cup\mathcal{E}_{\leq}(\bar{c}_{i^{\prime}},\nu_{i^{\prime}}\bar{E}_{i^{\prime}})\big{)}$
$\displaystyle\quad\cup\bigcup_{i^{\prime}\in\mathbb{I}}\\!\\!\big{(}\mathcal{E}_{\leq}(c_{i^{\prime}},\epsilon_{i^{\prime}}E_{i^{\prime}})\\!\cap\\!\mathcal{E}_{\geq}(\bar{c}_{i^{\prime}},\nu_{i^{\prime}}\bar{E}_{i^{\prime}})\big{)}\\!\Big{)}\\!\cap\\!\mathcal{W}\\!=\\!{}^{n}\\!\cap\\!\mathcal{W}\\!=\\!\mathcal{W}.$

From $\mathcal{F}\cup\mathcal{J}=\mathcal{K}$, the definition of $\mathcal{K}$
in (31) and $x^{+}=x$ in the jump map $\mathbf{J}$, it follows immediately
that $\mathbf{J}(\mathcal{J})\subset\mathcal{K}$.

####  -12 Proof of Lemma 8

The intersection of $\mathcal{E}(c_{i},\delta E_{i})$ and
$\mathcal{E}(\bar{c}_{i},\mu\bar{E}_{i})$ corresponds to the two quadratic
equations

$\begin{cases}\delta^{2}\|E_{i}(x-c_{i})\|^{2}=1\\\
\mu^{2}\|\bar{E}_{i}(x-\bar{c}_{i})\|^{2}=1\end{cases}.$ (65)

By expanding squares and using (20), (65) is equivalent to

$\begin{cases}\|E_{i}x\|^{2}-2c_{i}^{\top}E_{i}^{2}x+\|E_{i}c_{i}\|^{2}-\delta^{-2}=0\\\
\|E_{i}x\|^{2}-c_{i}^{\top}E_{i}^{2}x+\|E_{i}c_{i}\|^{2}(1-\mu^{-2})/4=0\end{cases}.$

Solving for $\|E_{i}x\|^{2}$ and $c_{i}^{\top}E_{i}^{2}x$, we obtain using
(27a)

$\begin{cases}\|E_{i}x\|^{2}=\|E_{i}c_{i}\|^{2}\big{(}(1+\mu^{-2})/2-\delta^{-2}\underline{\delta}_{i}^{4}\big{)}\\\
c_{i}^{\top}E_{i}^{2}x=\|E_{i}c_{i}\|^{2}\big{(}(3+\mu^{-2})/4-\delta^{-2}\underline{\delta}_{i}^{4}\big{)}\end{cases}$
(66)

and both right-hand sides of (66) are positive because

$\displaystyle\begin{aligned}
&(1+\mu^{-2})/2-\delta^{-2}\underline{\delta}_{i}^{4}\\\
&\quad\geq(1+\bar{\mu}_{i}(\delta)^{-2})/2-\delta^{-2}\underline{\delta}_{i}^{4}\overset{\eqref{eq:bar
mu}}{=}1-2\underline{\delta}_{i}^{2}+\delta^{-2}\underline{\delta}_{i}^{4}\\\
&\quad=(\underline{\delta}_{i}^{2}-1)^{2}+\underline{\delta}_{i}^{4}(\delta^{-2}-1)\geq(\underline{\delta}_{i}^{2}-1)^{2}>0\end{aligned}$
(67a) $\displaystyle\begin{aligned}
&(3+\mu^{-2})/4-\delta^{-2}\underline{\delta}_{i}^{4}\geq(3+\bar{\mu}_{i}(\delta)^{-2})/4-\delta^{-2}\underline{\delta}_{i}^{4}\\\
&\quad=1-\underline{\delta}_{i}^{2}>0,\text{ by
Assumption~{}\ref{assumption:obstacle}}.\end{aligned}$ (67b)

From (66), one obtains with some computations

$\displaystyle\frac{c_{i}^{\top}E_{i}^{2}x}{\|E_{i}c_{i}\|\|E_{i}x\|}\\!\overset{\eqref{eq:solving
for cone
quantities}}{=}\\!\frac{\|E_{i}c_{i}\|^{2}\big{(}(3\\!+\\!\mu^{-2})/4\\!-\\!\delta^{-2}\underline{\delta}_{i}^{4}\big{)}}{\|E_{i}c_{i}\|\|E_{i}c_{i}\|\sqrt{(1\\!+\\!\mu^{-2})/2\\!-\\!\delta^{-2}\underline{\delta}_{i}^{4}}}$
(68) $\displaystyle\overset{\eqref{eq:bar
theta}}{=}\\!\\!\\!\frac{1-\cos(\bar{\theta}_{i}(\delta,\mu))\underline{\delta}_{i}^{2}}{\sqrt{(1+\mu^{-2})/2-\delta^{-2}\underline{\delta}_{i}^{4}}}.$

For
$\mu\in[1,\big{(}1-4\underline{\delta}_{i}^{2}(1-\underline{\delta}_{i}^{2}/\delta^{2})\big{)}^{-\frac{1}{2}}]$
and $\delta<1$, we can prove

$\\!\\!\\!\\!\frac{1-\cos(\bar{\theta}_{i}(\delta,\mu))\underline{\delta}_{i}^{2}}{\sqrt{(1+\mu^{-2})/2-\delta^{-2}\underline{\delta}_{i}^{4}}}\\!=\\!\frac{(3+\mu^{-2})/4-\delta^{-2}\underline{\delta}_{i}^{4}}{\sqrt{(1+\mu^{-2})/2-\delta^{-2}\underline{\delta}_{i}^{4}}}\\!<\\!1$
(69)

(e.g., set $\chi:=(1+\mu^{-2})/2$, obtain the bounds of $\chi$ from the bounds
of $\mu$, substitute $\chi$ in (69), and note that the obtained quadratic
inequality holds true for such bounds of $\chi$ due to $\delta<1$). Because of
(67a), (67b) and (69), the expression in (32) is well-defined and positive.
Since (68) yields

$\displaystyle\frac{c_{i}^{\top}E_{i}^{2}x}{\|E_{i}c_{i}\|\|E_{i}x\|}=\frac{1-\cos(\bar{\theta}_{i}(\delta,\mu))\underline{\delta}_{i}^{2}}{\sqrt{(1+\mu^{-2})/2-\delta^{-2}\underline{\delta}_{i}^{4}}}\overset{\eqref{eq:cosine
expr}}{=}\cos(\vartheta_{i}(\delta,\mu)),$

(33) holds as well by the cone definition in (11).

####  -13 Proof of Lemma 9

The obstacles $\\{\mathcal{O}_{i}\\}_{i\in\mathbb{I}}$ are sufficiently
pairwise disjoint, so (37) holds. Moreover, the sets
$\mathcal{R}_{i^{\prime}}(\delta_{i^{\prime}},\mu_{i^{\prime}})$ in (39) and
$\mathcal{E}_{\leq}(c_{i^{\prime\prime}},\delta_{i^{\prime\prime}}E_{i^{\prime\prime}})$
are bounded, and for
$\delta_{i^{\prime}},\delta_{i^{\prime\prime}},\mu_{i^{\prime}}\to 1$,
$\mathcal{R}_{i^{\prime}}(\delta_{i^{\prime}},\mu_{i^{\prime}})$ and
$\mathcal{E}_{\leq}(c_{i^{\prime\prime}},\delta_{i^{\prime\prime}}E_{i^{\prime\prime}})$
reduce respectively to $\mathcal{R}^{*}_{i^{\prime}}$ and
$\mathcal{E}_{\leq}(c_{i^{\prime\prime}},E_{i^{\prime\prime}})$. By a
continuity argument, there exist parameters $\delta_{i}^{*}$ and $\mu_{i}^{*}$
such that the lemma holds.

####  -14 Proof of Lemma 10

We prove the claim for arbitrary $i\in\mathbb{I}$ and $m\in\\{-1,1\\}$. Let us
prove (43a)-(43b). Thanks to the weak pairwise disjointness of
$\\{\mathcal{E}_{\leq}(c_{i},\delta_{i}E_{i})\\}_{i\in\mathbb{I}}$ we have
$\mathcal{E}_{\leq}(c_{i},\delta_{i}E_{i})\cap\mathcal{E}_{\geq}(c_{i^{\prime}},\delta_{i^{\prime}}E_{i^{\prime}})=\mathcal{E}_{\leq}(c_{i},\delta_{i}E_{i})$
for all $i^{\prime}\neq i$. Then,
$\mathcal{E}_{\leq}(c_{i},\delta_{i}E_{i})\cap\mathcal{W}=\mathcal{E}_{\leq}(c_{i},\delta_{i}E_{i})\cap\mathcal{E}_{\geq}(c_{i},E_{i}),$
which implies by (26) that $\mathcal{F}_{m}^{i}$ satisfies (43b). By a similar
argument, $\mathcal{J}_{0}^{i}$ satisfies (43a) as well.

Let us prove (43c). Write the complement of $\mathcal{F}_{0}^{*}$ as

$\displaystyle\\!\\!\\!\\!\\!(\mathcal{F}_{0}^{*})^{\mathsf{c}}\overset{\eqref{eq:F0J0star}}{=}\big{(}\bigcap_{i\in\mathbb{I}}\mathcal{F}_{0}^{i}\big{)}^{\mathsf{c}}\overset{\eqref{eq:set
identities}}{=}\bigcup_{i\in\mathbb{I}}\big{(}\mathcal{F}_{0}^{i}\big{)}^{\mathsf{c}}$
(70)
$\displaystyle\\!\\!\\!\\!\\!\overset{\eqref{eq:F0i}}{=}\bigcup_{i\in\mathbb{I}}\Big{(}\big{(}\mathcal{E}_{\geq}(c_{i},\epsilon_{i}E_{i})\cup\mathcal{E}_{\leq}(\bar{c}_{i},\nu_{i}\bar{E}_{i})\big{)}\cap\mathcal{W}\Big{)}^{\mathsf{c}}$
$\displaystyle\\!\\!\\!\\!\\!\overset{\eqref{eq:set
identities}}{=}\bigcup_{i\in\mathbb{I}}\big{(}\mathcal{E}_{\geq}(c_{i},\epsilon_{i}E_{i})\cup\mathcal{E}_{\leq}(\bar{c}_{i},\nu_{i}\bar{E}_{i})\big{)}^{\mathsf{c}}\cup\mathcal{W}^{\mathsf{c}}$
$\displaystyle\\!\\!\\!\\!\\!\overset{\eqref{eq:W}}{=}\bigcup_{i\in\mathbb{I}}\mathcal{E}_{<}(c_{i},\epsilon_{i}E_{i})\cap\mathcal{E}_{>}(\bar{c}_{i},\nu_{i}\bar{E}_{i})\cup\bigcup_{i\in\mathbb{I}}\mathcal{E}_{<}(c_{i},E_{i})$
$\displaystyle\\!\\!\\!\\!\\!=\\!\bigcup_{i\in\mathbb{I}}\big{(}\mathcal{E}_{<}(c_{i},\epsilon_{i}E_{i})\cap\mathcal{E}_{>}(\bar{c}_{i},\nu_{i}\bar{E}_{i})\big{)}\cup\mathcal{E}_{<}(c_{i},E_{i})$
$\displaystyle\\!\\!\\!\\!\\!=\\!\bigcup_{i\in\mathbb{I}}(\mathcal{E}\\!_{<}\\!(c_{i},\\!\epsilon_{i}E_{i})\\!\cup\\!\mathcal{E}\\!_{<}\\!(c_{i}\\!,E_{i}))\\!\cap\\!(\mathcal{E}\\!_{>}\\!(\bar{c}_{i},\nu_{i}\bar{E}_{i})\\!\cup\\!\mathcal{E}\\!_{<}\\!(c_{i},\\!E_{i}))$
$\displaystyle\\!\\!\\!\\!\\!=\\!\bigcup_{i\in\mathbb{I}}\mathcal{E}_{<}(c_{i},\epsilon_{i}E_{i})\cap(\mathcal{E}_{>}(\bar{c}_{i},\nu_{i}\bar{E}_{i})\cup\mathcal{E}_{<}(c_{i},E_{i}))$

because $\epsilon_{i}<1$. Thanks to the weak pairwise disjointness of
$\\{\mathcal{E}(c_{i},\delta_{i}E_{i})\\}_{i\in\mathbb{I}}$ and
$\delta_{i}<\epsilon_{i}$, the sets
$\\{\mathcal{E}_{<}(c_{i},\epsilon_{i}E_{i})\cap(\mathcal{E}_{>}(\bar{c}_{i},\nu_{i}\bar{E}_{i})\cup\mathcal{E}_{<}(c_{i},E_{i}))\\}_{i\in\mathbb{I}}$
can actually be proven to be pairwise separated. Then, we can use (2) to
obtain the boundary of the set $\mathcal{F}_{0}^{*}$ as

$\displaystyle\partial\mathcal{F}_{0}^{*}=\partial\big{(}(\mathcal{F}_{0}^{*})^{\mathsf{c}}\big{)}$
$\displaystyle\overset{\eqref{eq:complement of
F_0star}}{=}\partial\Big{(}\bigcup_{i\in\mathbb{I}}\mathcal{E}_{<}(c_{i},\epsilon_{i}E_{i})\cap(\mathcal{E}_{>}(\bar{c}_{i},\nu_{i}\bar{E}_{i})\cup\mathcal{E}_{<}(c_{i},E_{i}))\Big{)}$
$\displaystyle\overset{\eqref{eq:boundary of separated
sets}}{=}\bigcup_{i\in\mathbb{I}}\partial\left(\mathcal{E}_{<}(c_{i},\epsilon_{i}E_{i})\cap(\mathcal{E}_{>}(\bar{c}_{i},\nu_{i}\bar{E}_{i})\cup\mathcal{E}_{<}(c_{i},E_{i}))\right)$
$\displaystyle\overset{\eqref{eq:set
identities}}{\subset}\bigcup_{i\in\mathbb{I}}\Big{(}\partial\mathcal{E}_{<}(c_{i},\epsilon_{i}E_{i})\cap\overline{\mathcal{E}_{>}(\bar{c}_{i},\nu_{i}\bar{E}_{i})\cup\mathcal{E}_{<}(c_{i},E_{i})}$
$\displaystyle\hskip
12.0pt\cup\partial\big{(}\mathcal{E}_{>}(\bar{c}_{i},\nu_{i}\bar{E}_{i})\cup\mathcal{E}_{<}(c_{i},E_{i})\big{)}\cap\overline{\mathcal{E}_{<}(c_{i},\epsilon_{i}E_{i})}\Big{)}$
$\displaystyle\overset{\eqref{eq:set
identities}}{\subset}\bigcup_{i\in\mathbb{I}}\bigg{(}\mathcal{E}(c_{i},\epsilon_{i}E_{i})\cap\big{(}\mathcal{E}_{\geq}(\bar{c}_{i},\nu_{i}\bar{E}_{i})\cup\mathcal{E}_{\leq}(c_{i},E_{i})\big{)}$
$\displaystyle\hskip
12.0pt\\!\cup\\!\Big{(}\\!\big{(}\mathcal{E}(\bar{c}_{i},\nu_{i}\bar{E}_{i})\backslash\mathcal{E}_{<}(c_{i},\\!E_{i})\big{)}\\!\cup\\!\big{(}\mathcal{E}(c_{i},\\!E_{i})\backslash\mathcal{E}_{>}(\bar{c}_{i},\nu_{i}\bar{E}_{i})\big{)}\\!\Big{)}$
$\displaystyle\hskip
24.0pt\\!\cap\\!\mathcal{E}_{\leq}(c_{i},\\!\epsilon_{i}E_{i})\\!\bigg{)}$
$\displaystyle=\bigcup_{i\in\mathbb{I}}\Big{(}\\!\big{(}\mathcal{E}(c_{i},\epsilon_{i}E_{i})\\!\cap\\!\mathcal{E}_{\geq}(\bar{c}_{i},\nu_{i}\bar{E}_{i})\big{)}\\!\cup\\!\big{(}(\mathcal{E}(\bar{c}_{i},\nu_{i}\bar{E}_{i})\backslash\mathcal{E}_{<}(c_{i},E_{i}))$
$\displaystyle\hskip
12.0pt\cap\mathcal{E}_{\leq}(c_{i},\epsilon_{i}E_{i})\big{)}\cup\big{(}\mathcal{E}(c_{i},E_{i})\backslash\mathcal{E}_{>}(\bar{c}_{i},\nu_{i}\bar{E}_{i})\big{)}\Big{)}=:\bigcup_{i\in\mathbb{I}}\mathcal{P}_{0}^{i}$

(43c) is finally proven in (74), for which we note that: (a)
$\mathcal{J}_{0}^{*}$ is simplified into
$\cup_{i\in\mathbb{I}}\mathcal{H}_{i}(\epsilon_{i},\nu_{i})$ thanks to (43a);
(b)
$\mathcal{P}_{0}^{i}\cap\mathcal{H}_{i^{\prime}}(\epsilon_{i^{\prime}},1)=\emptyset$
for all $i\neq i^{\prime}$; (c) most of the sets in the next-to-last
expression are empty, so the last expression follows.

Let us prove (43d). First, note that by (43b) and (22)

$\displaystyle\mathcal{F}_{m}^{i}=\mathcal{E}_{\leq}(c_{i},\delta_{i}E_{i})\cap\mathcal{E}_{\geq}(c_{i},E_{i})$
$\displaystyle\hskip
56.9055pt\cap\mathcal{E}_{\geq}(\bar{c}_{i},\mu_{i}\bar{E}_{i})\cap\mathcal{C}_{\geq}(c_{i},c_{i}-p_{m}^{i},\psi_{i},E_{i}),$

which is an intersection of four closed sets. By successive applications of
(1i) and (1f), the boundary of $\mathcal{F}_{m}^{i}$ satisfies

$\displaystyle\partial\mathcal{F}_{m}^{i}\subset\bigcup_{k\in\\{1,2,3,4\\}}\mathcal{P}_{m,k}^{i}$
(71)

with the following definitions

$\displaystyle\mathcal{P}_{m,1}^{i}:=\mathcal{E}(c_{i},\delta_{i}E_{i})\cap\mathcal{E}_{\geq}(c_{i},E_{i})\cap\mathcal{E}_{\geq}(\bar{c}_{i},\mu_{i}\bar{E}_{i})$
$\displaystyle\hskip
113.81102pt\cap\mathcal{C}_{\geq}(c_{i},c_{i}-p_{m}^{i},\psi_{i},E_{i})$ (72a)
$\displaystyle\mathcal{P}_{m,2}^{i}:=\mathcal{E}_{\leq}(c_{i},\delta_{i}E_{i})\cap\mathcal{E}(c_{i},E_{i})\cap\mathcal{E}_{\geq}(\bar{c}_{i},\mu_{i}\bar{E}_{i})$
$\displaystyle\hskip
113.81102pt\cap\mathcal{C}_{\geq}(c_{i},c_{i}-p_{m}^{i},\psi_{i},E_{i})$ (72b)
$\displaystyle\mathcal{P}_{m,3}^{i}:=\mathcal{E}_{\leq}(c_{i},\delta_{i}E_{i})\cap\mathcal{E}_{\geq}(c_{i},E_{i})\cap\mathcal{E}(\bar{c}_{i},\mu_{i}\bar{E}_{i})$
$\displaystyle\hskip
113.81102pt\cap\mathcal{C}_{\geq}(c_{i},c_{i}-p_{m}^{i},\psi_{i},E_{i})$ (72c)
$\displaystyle\mathcal{P}_{m,4}^{i}:=\mathcal{E}_{\leq}(c_{i},\delta_{i}E_{i})\cap\mathcal{E}_{\geq}(c_{i},E_{i})\cap\mathcal{E}_{\geq}(\bar{c}_{i},\mu_{i}\bar{E}_{i})$
$\displaystyle\hskip
113.81102pt\cap\mathcal{C}(c_{i},c_{i}-p_{m}^{i},\psi_{i},E_{i}).$ (72d)

Second, note that since $\mathcal{F}_{m}^{i}$ is closed,
$\partial\mathcal{F}_{m}^{i}\subset\mathcal{F}_{m}^{i}\subset\mathcal{W}$, and
hence
$\partial\mathcal{F}_{m}^{i}\backslash\mathcal{W}\subset\mathcal{W}\backslash\mathcal{W}=\emptyset$.
By this fact, we can write that

$\displaystyle\partial\mathcal{F}_{m}^{i}\backslash\mathcal{J}_{m}^{i}\overset{\eqref{eq:J^i_m}}{=}\partial\mathcal{F}_{m}^{i}\backslash\bigg{(}\Big{(}\mathcal{E}_{\geq}(c_{i},\delta_{i}E_{i})\cup\mathcal{E}_{\leq}(\bar{c}_{i},\mu_{i}\bar{E}_{i})$
$\displaystyle\qquad\cup\mathcal{C}_{\leq}(c_{i},c_{i}\\!-\\!p_{m}^{i},\psi_{i},E_{i})\Big{)}\cap\mathcal{W}\bigg{)}$
$\displaystyle\overset{\eqref{eq:set
identities}}{=}\partial\mathcal{F}_{m}^{i}\backslash\mathcal{W}\cup\partial\mathcal{F}_{m}^{i}\backslash\Big{(}\mathcal{E}_{\geq}(c_{i},\delta_{i}E_{i})\cup\mathcal{E}_{\leq}(\bar{c}_{i},\mu_{i}\bar{E}_{i})$
$\displaystyle\qquad\cup\mathcal{C}_{\leq}(c_{i},c_{i}\\!-\\!p_{m}^{i},\psi_{i},E_{i})\Big{)}$
$\displaystyle=\partial\mathcal{F}_{m}^{i}\backslash\Big{(}\\!\mathcal{E}_{\geq}(c_{i},\delta_{i}E_{i})\\!\cup\\!\mathcal{E}_{\leq}(\bar{c}_{i},\mu_{i}\bar{E}_{i})\\!\cup\\!\mathcal{C}_{\leq}(c_{i},c_{i}\\!-\\!p_{m}^{i},\psi_{i},E_{i})\\!\Big{)}$
$\displaystyle\overset{\eqref{eq:boundary:Fmi}}{\subset}\Big{(}\cup_{k\in\\{1,2,3,4\\}}\mathcal{P}_{m,k}^{i}\Big{)}\backslash\Big{(}\mathcal{E}_{\geq}(c_{i},\delta_{i}E_{i})\cup\mathcal{E}_{\leq}(\bar{c}_{i},\mu_{i}\bar{E}_{i})$
$\displaystyle\qquad\cup\mathcal{C}_{\leq}(c_{i},c_{i}\\!-\\!p_{m}^{i},\psi_{i},E_{i})\Big{)}$
$\displaystyle\overset{\eqref{eq:set
identities}}{=}\cup_{k\in\\{1,2,3,4\\}}\Big{(}\mathcal{P}_{m,k}^{i}\backslash\Big{(}\mathcal{E}_{\geq}(c_{i},\delta_{i}E_{i})\cup\mathcal{E}_{\leq}(\bar{c}_{i},\mu_{i}\bar{E}_{i})$
$\displaystyle\qquad\cup\mathcal{C}_{\leq}(c_{i},c_{i}\\!-\\!p_{m}^{i},\psi_{i},E_{i})\Big{)}\Big{)}$
$\displaystyle\overset{\eqref{eq:set
identities}}{\subset}\cup_{k\in\\{1,2,3,4\\}}\Big{(}\big{(}\mathcal{P}_{m,k}^{i}\backslash\mathcal{E}_{\geq}(c_{i},\delta_{i}E_{i})\big{)}$
$\displaystyle\qquad\cap\big{(}\mathcal{P}_{m,k}^{i}\backslash\mathcal{E}_{\leq}(\bar{c}_{i},\mu_{i}\bar{E}_{i})\big{)}\\!\cap\\!\big{(}\mathcal{P}_{m,k}^{i}\backslash\mathcal{C}_{\leq}(c_{i},c_{i}\\!-\\!p_{m}^{i},\psi_{i},E_{i})\big{)}\Big{)}.$

Finally, we simplify this expression through the following facts

$\displaystyle\mathcal{P}_{m,1}^{i}\backslash\mathcal{E}_{\geq}(c_{i},\delta_{i}E_{i})=\emptyset,\quad\mathcal{P}_{m,3}^{i}\backslash\mathcal{E}_{\leq}(\bar{c}_{i},\mu_{i}\bar{E}_{i})=\emptyset$
(73)
$\displaystyle\mathcal{P}_{m,4}^{i}\backslash\mathcal{C}_{\leq}(c_{i},c_{i}\\!-\\!p_{m}^{i},\psi_{i},E_{i})=\emptyset,$

which are an immediate consequence of (72) and yield

$\displaystyle\partial\mathcal{F}_{m}^{i}\backslash\mathcal{J}_{m}^{i}\overset{\eqref{eq:empty
set
differences}}{\subset}\mathcal{P}_{m,2}^{i}\backslash\Big{(}\mathcal{E}_{\geq}(c_{i},\delta_{i}E_{i})\cup\mathcal{E}_{\leq}(\bar{c}_{i},\mu_{i}\bar{E}_{i})$
$\displaystyle\quad\cup\mathcal{C}_{\leq}(c_{i},c_{i}\\!-\\!p_{m}^{i},\psi_{i},E_{i})\Big{)}$
$\displaystyle\overset{\eqref{eq:set
identities}}{=}\\!\mathcal{P}_{m,2}^{i}\\!\cap\\!\Big{(}\\!\mathcal{E}_{\geq}(c_{i},\\!\delta_{i}E_{i})\\!\cup\\!\mathcal{E}_{\leq}(\bar{c}_{i},\\!\mu_{i}\bar{E}_{i})\\!\cup\\!\mathcal{C}_{\leq}(c_{i},\\!c_{i}\\!-\\!p_{m}^{i},\\!\psi_{i},\\!E_{i})\\!\Big{)}^{\mathsf{c}}$
$\displaystyle\overset{\eqref{eq:set
identities}}{=}\\!\mathcal{P}_{m,2}^{i}\cap\mathcal{E}_{<}(c_{i},\\!\delta_{i}E_{i})\cap\mathcal{E}_{>}(\bar{c}_{i},\\!\mu_{i}\bar{E}_{i})\cap\mathcal{C}_{>}(c_{i},\\!c_{i}\\!-\\!p_{m}^{i},\\!\psi_{i},\\!E_{i})$
$\displaystyle=\\!\mathcal{E}_{<}(c_{i},\\!\delta_{i}E_{i})\\!\cap\\!\mathcal{E}(c_{i},\\!E_{i})\\!\cap\\!\mathcal{E}_{>}(\bar{c}_{i},\\!\mu_{i}\bar{E}_{i})\\!\cap\\!\mathcal{C}_{>}(c_{i},c_{i}-p_{m}^{i},\\!\psi_{i},\\!E_{i})$
$\displaystyle=\\!\mathcal{E}(c_{i},E_{i})\cap\mathcal{E}_{>}(\bar{c}_{i},\mu_{i}\bar{E}_{i})\cap\mathcal{C}_{>}(c_{i},c_{i}-p_{m}^{i},\psi_{i},E_{i})$
$\displaystyle\overset{\eqref{eq:set
identities}}{=}\\!\mathcal{E}(c_{i},E_{i})\backslash(\mathcal{E}_{\leq}(\bar{c}_{i},\mu_{i}\bar{E}_{i})\cup\mathcal{C}_{\leq}(c_{i},c_{i}-p_{m}^{i},\psi_{i},E_{i})).$

$\displaystyle\partial\mathcal{F}_{0}^{*}\backslash\mathcal{J}_{0}^{*}\subset\Big{(}\bigcup_{i\in\mathbb{I}}\mathcal{P}_{0}^{i}\Big{)}\backslash\Big{(}\bigcup_{i\in\mathbb{I}}\mathcal{H}_{i}(\epsilon_{i},\nu_{i})\Big{)}=\bigcup_{i\in\mathbb{I}}\\!\Big{(}\\!\mathcal{P}_{0}^{i}\backslash\\!\bigcup_{i^{\prime}\in\mathbb{I}}\\!\big{(}\mathcal{H}_{i^{\prime}}(\epsilon_{i^{\prime}},\nu_{i^{\prime}})\big{)}\\!\Big{)}=\bigcup_{i\in\mathbb{I}}\\!\Big{(}\\!\bigcap_{i^{\prime}\in\mathbb{I}}\\!\big{(}\mathcal{P}_{0}^{i}\backslash\mathcal{H}_{i^{\prime}}(\epsilon_{i^{\prime}},\nu_{i^{\prime}})\big{)}\\!\Big{)}=\bigcup_{i\in\mathbb{I}}\\!\Big{(}\\!\mathcal{P}_{0}^{i}\backslash\mathcal{H}_{i}(\epsilon_{i},\nu_{i})\cap\\!\bigcap_{i^{\prime}\in\mathbb{I},i^{\prime}\neq
i}\\!\mathcal{P}_{0}^{i}\\!\Big{)}$ (74)
$\displaystyle\\!\\!\\!=\\!\bigcup_{i\in\mathbb{I}}\big{(}\mathcal{P}_{0}^{i}\backslash\mathcal{H}_{i}(\epsilon_{i},\nu_{i})\big{)}=\bigcup_{i\in\mathbb{I}}\Big{(}\\!\big{(}\mathcal{E}(c_{i},\epsilon_{i}E_{i})\cap\mathcal{E}_{\geq}(\bar{c}_{i},\nu_{i}\bar{E}_{i})\big{)}\\!\cup\\!\big{(}(\mathcal{E}(\bar{c}_{i},\nu_{i}\bar{E}_{i})\backslash\mathcal{E}_{<}(c_{i},E_{i}))\cap\mathcal{E}_{\leq}(c_{i},\epsilon_{i}E_{i})\big{)}\\!\cup\\!(\mathcal{E}(c_{i},E_{i})\backslash\mathcal{E}_{>}(\bar{c}_{i},\nu_{i}\bar{E}_{i}))\\!\Big{)}\backslash\mathcal{H}_{i}(\epsilon_{i},\nu_{i})$
$\displaystyle\\!\\!\\!=\\!\bigcup_{i\in\mathbb{I}}\Big{(}\big{(}\mathcal{E}(c_{i},\epsilon_{i}E_{i})\cap\mathcal{E}_{\geq}(\bar{c}_{i},\nu_{i}\bar{E}_{i})\big{)}\cup\big{(}(\mathcal{E}(\bar{c}_{i},\nu_{i}\bar{E}_{i})\backslash\mathcal{E}_{<}(c_{i},E_{i}))\cap\mathcal{E}_{\leq}(c_{i},\epsilon_{i}E_{i})\big{)}\cup(\mathcal{E}(c_{i},E_{i})\backslash\mathcal{E}_{>}(\bar{c}_{i},\nu_{i}\bar{E}_{i}))\Big{)}\cap\mathcal{H}_{i}(\epsilon_{i},\nu_{i})^{\mathsf{c}}$
$\displaystyle\\!\\!\\!=\\!\bigcup_{i\in\mathbb{I}}\\!\Big{(}\\!\big{(}\mathcal{E}(c_{i},\\!\epsilon_{i}E_{i}\\!)\\!\cap\\!\mathcal{E}_{\geq}(\bar{c}_{i},\\!\nu_{i}\bar{E}_{i}\\!)\big{)}\\!\cup\\!\big{(}(\mathcal{E}(\bar{c}_{i},\\!\nu_{i}\bar{E}_{i}\\!)\backslash\mathcal{E}_{<}(c_{i},\\!E_{i}\\!))\\!\cap\\!\mathcal{E}_{\leq}(c_{i},\\!\epsilon_{i}E_{i}\\!)\big{)}\\!\cup\\!(\mathcal{E}(c_{i},\\!E_{i}\\!)\backslash\mathcal{E}_{>}(\bar{c}_{i},\\!\nu_{i}\bar{E}_{i}\\!))\\!\Big{)}\\!\cap\\!\big{(}\mathcal{E}_{>}(c_{i},\\!\epsilon_{i}E_{i}\\!)\\!\cup\\!\mathcal{E}_{<}(\bar{c}_{i},\\!\nu_{i}\bar{E}_{i}\\!)\\!\cup\\!\mathcal{E}_{<}(c_{i},\\!E_{i}\\!)\big{)}$
$\displaystyle\\!\\!\\!=\\!\bigcup_{i\in\mathbb{I}}\\!\Big{(}\\!\mathcal{E}(c_{i},\epsilon_{i}E_{i})\cap\mathcal{E}_{\geq}(\bar{c}_{i},\nu_{i}\bar{E}_{i})\cap\mathcal{E}_{>}(c_{i},\epsilon_{i}E_{i})\Big{)}\\!\cup\\!\Big{(}\\!\mathcal{E}(c_{i},\epsilon_{i}E_{i})\cap\mathcal{E}_{\geq}(\bar{c}_{i},\nu_{i}\bar{E}_{i})\cap\mathcal{E}_{<}(\bar{c}_{i},\nu_{i}\bar{E}_{i})\Big{)}\\!\cup\\!\Big{(}\mathcal{E}(c_{i},\epsilon_{i}E_{i})\cap\mathcal{E}_{\geq}(\bar{c}_{i},\nu_{i}\bar{E}_{i})\cap\mathcal{E}_{<}(c_{i},E_{i})\Big{)}$
$\displaystyle\qquad\cup\Big{(}\big{(}\mathcal{E}(\bar{c}_{i},\nu_{i}\bar{E}_{i})\backslash\mathcal{E}_{<}(c_{i},E_{i})\big{)}\cap\mathcal{E}_{\leq}(c_{i},\epsilon_{i}E_{i})\cap\mathcal{E}_{>}(c_{i},\epsilon_{i}E_{i})\Big{)}\cup\Big{(}\big{(}\mathcal{E}(\bar{c}_{i},\nu_{i}\bar{E}_{i})\backslash\mathcal{E}_{<}(c_{i},E_{i})\big{)}\cap\mathcal{E}_{\leq}(c_{i},\epsilon_{i}E_{i})\cap\mathcal{E}_{<}(\bar{c}_{i},\nu_{i}\bar{E}_{i})\Big{)}$
$\displaystyle\qquad\cup\Big{(}\big{(}\mathcal{E}(\bar{c}_{i},\nu_{i}\bar{E}_{i})\backslash\mathcal{E}_{<}(c_{i},E_{i})\big{)}\cap\mathcal{E}_{\leq}(c_{i},\epsilon_{i}E_{i})\cap\mathcal{E}_{<}(c_{i},E_{i})\Big{)}\cup\Big{(}\big{(}\mathcal{E}(c_{i},E_{i})\backslash\mathcal{E}_{>}(\bar{c}_{i},\nu_{i}\bar{E}_{i})\big{)}\cap\mathcal{E}_{>}(c_{i},\epsilon_{i}E_{i})\Big{)}$
$\displaystyle\qquad\cup\Big{(}\big{(}\mathcal{E}(c_{i},E_{i})\backslash\mathcal{E}_{>}(\bar{c}_{i},\nu_{i}\bar{E}_{i})\big{)}\cap\mathcal{E}_{<}(\bar{c}_{i},\nu_{i}\bar{E}_{i})\Big{)}\cup\Big{(}\big{(}\mathcal{E}(c_{i},E_{i})\backslash\mathcal{E}_{>}(\bar{c}_{i},\nu_{i}\bar{E}_{i})\big{)}\cap\mathcal{E}_{<}(c_{i},E_{i})\Big{)}=\bigcup_{i\in\mathbb{I}}\mathcal{E}(c_{i},E_{i})\backslash\mathcal{E}_{\geq}(\bar{c}_{i},\nu_{i}\bar{E}_{i}).$

####  -15 Proof of Lemma 11

We divide the proof into steps. Step 1: For each $i\in\mathbb{I}$ and
$m\in\\{-1,1\\}$, $\delta\in[\delta_{i},1]$ and
$\psi\in[\psi_{i},\bar{\psi}_{i})$, consider the sets

$\displaystyle\begin{aligned}
&\tilde{\mathcal{F}}^{i}_{m}(\delta,\psi)\\!:=\mathcal{E}_{\leq}(c_{i},\delta
E_{i})\cap\mathcal{E}_{\geq}(c_{i},E_{i})\cap\mathcal{E}_{\geq}(\bar{c}_{i},\mu_{i}\bar{E}_{i})\\\
&\qquad\cap\mathcal{C}_{\geq}(c_{i},c_{i}-p_{m}^{i},\psi,E_{i}).\end{aligned}$
(75a) $\displaystyle\begin{aligned}
&\tilde{\mathcal{P}}^{i}_{m,3}(\delta,\psi):=\mathcal{E}_{\leq}(c_{i},\delta
E_{i})\cap\mathcal{E}_{\geq}(c_{i},E_{i})\\\
&\qquad\cap\mathcal{E}(\bar{c}_{i},\mu_{i}\bar{E}_{i})\cap\mathcal{C}_{\geq}(c_{i},c_{i}-p_{m}^{i},\psi,E_{i})\end{aligned}$
(75b)

Each maximal solution $x$ to the flow-only hybrid system

$\dot{x}=\kappa(x,i,m)=:\mathfrak{u}(x),\quad
x\in\tilde{\mathcal{F}}^{i}_{m}(\delta,\psi)$ (76)

has $T={\sup}_{t}\operatorname{dom}x<+\infty$ and
$x(T)\in\tilde{\mathcal{P}}^{i}_{m,3}(\delta,\psi)$. We first prove that $T$
is finite. Consider the following nonnegative function
$\mathbf{V}(x):=\tfrac{1}{2}\|E_{i}(x-p_{m}^{i})\|^{2}$. Simple computations,
(16), and (4a) yield that for all
$x\in\tilde{\mathcal{F}}_{m}^{i}(\delta,\psi)$

$\displaystyle\langle$ $\displaystyle\nabla\mathbf{V}(x),\kappa(x,i,m)\rangle$
$\displaystyle\\!=\\!-k_{m}(x-p_{m}^{i})^{\top}E_{i}\pi^{\perp}(E_{i}(x-c_{i}))E_{i}(x-p_{m}^{i})$
$\displaystyle\\!=\\!-k_{m}\|\pi^{\perp}(E_{i}(x-c_{i}))E_{i}(x-p_{m}^{i})\|\\!<\\!-\mathfrak{e}\\!<\\!0,$

where $\mathfrak{e}>0$ follows from
$\pi^{\perp}(E_{i}(x-c_{i}))E_{i}(x-p_{m}^{i})$ vanishing only for
$x\in\mathcal{L}(c_{i},p_{m}^{i}-c_{i})$ (Lemma 3), and
$\mathcal{L}(c_{i},p_{m}^{i}-c_{i})$ is separated by a positive distance from
$\tilde{\mathcal{F}}_{m}^{i}(\delta,\psi)$ (Lemma 4). Then, $T$ is finite,
otherwise $\mathbf{V}$ evaluated along solutions would become negative. In
order to show $x(T)\in\tilde{\mathcal{P}}^{i}_{m,3}(\delta,\psi)$, we resort
to a viability argument based on tangent cones. To this end, we need the next
lemma.

###### Lemma 12

For all
$x\in\tilde{\mathcal{F}}_{m}^{i}(\delta,\psi)\backslash\tilde{\mathcal{P}}^{i}_{m,3}(\delta,\psi)$,

$\displaystyle\mathfrak{u}(x)$
$\displaystyle\in\mathbf{T}_{\mathcal{E}_{\leq}(c_{i},\delta E_{i})}(x)$ (77a)
$\displaystyle\mathfrak{u}(x)$
$\displaystyle\in\mathbf{T}_{\mathcal{E}_{\geq}(c_{i},E_{i})}(x)$ (77b)
$\displaystyle\mathfrak{u}(x)$
$\displaystyle\in\mathbf{T}_{\mathcal{E}_{\geq}(\bar{c}_{i},\mu_{i}\bar{E}_{i})}(x)$
(77c) $\displaystyle\mathfrak{u}(x)$
$\displaystyle\in\mathbf{T}_{\mathcal{C}_{\geq}(c_{i},c_{i}-p_{m}^{i},\psi,E_{i})}(x).$
(77d)

$\tilde{\mathcal{F}}^{i}_{m}(\delta,\psi)$ in (75a) is the intersection of
four closed sets: if

$\displaystyle\mathfrak{u}(x)\in$
$\displaystyle\mathbf{T}_{\mathcal{E}_{\leq}(c_{i},\delta
E_{i})}(x)\cap\mathbf{T}_{\mathcal{E}_{\geq}(c_{i},E_{i})}(x)$ (78)
$\displaystyle\cap\mathbf{T}_{\mathcal{E}_{\geq}(\bar{c}_{i},\mu_{i}\bar{E}_{i})}(x)\cap\mathbf{T}_{\mathcal{C}_{\geq}(c_{i},c_{i}-p_{m}^{i},\psi,E_{i})}(x),$

then
$\mathfrak{u}(x)\in\mathbf{T}_{\tilde{\mathcal{F}}^{i}_{m}(\delta,\psi)}(x)$
by the next fact, which is an immediate corollary of [31, Thm. 5].

######  Fact 1 ([31, Thm. 5])

Let $v\in\mathcal{A}\cap\mathcal{B}$ with $\mathcal{A}$, $\mathcal{B}$ closed
subsets of n. Suppose
$\mathbf{T}_{\mathcal{A}}(v)\cap(\mathbf{T}_{\mathcal{B}}(v)^{\circ})\neq\emptyset$.
Then,
$\mathbf{T}_{\mathcal{A}\cap\mathcal{B}}(v)\supset\mathbf{T}_{\mathcal{A}}(v)\cap\mathbf{T}_{\mathcal{B}}(v)$.

The condition (78) has been checked in Lemma 12 for each
$x\in\tilde{\mathcal{F}}_{m}^{i}(\delta,\psi)\backslash\tilde{\mathcal{P}}^{i}_{m,3}(\delta,\psi)$,
hence

$\mathfrak{u}(x)\in\mathbf{T}_{\tilde{\mathcal{F}}^{i}_{m}(\delta,\psi)}(x)\quad\forall
x\in\tilde{\mathcal{F}}_{m}^{i}(\delta,\psi)\backslash\tilde{\mathcal{P}}^{i}_{m,3}(\delta,\psi).$
(79)

Then, it can only be $x(T)\in\tilde{\mathcal{P}}^{i}_{m,3}(\delta,\psi)$,
otherwise the solution could be further extended by viability results such as
[24, Lemma 5.26(b)].

Step 2: For each $i\in\mathbb{I}$, both the sets
$\mathcal{E}_{\leq}(\bar{c}_{i},\bar{E}_{i})$ and
$\mathcal{C}(0,c_{i},\vartheta_{i}(\delta,\mu_{i}),E_{i})$
($\delta\in[\delta_{i},1]$) are forward invariant under the vector field
$-k_{0}x$. For $x\in\mathcal{E}(\bar{c}_{i},\bar{E}_{i})$, we have

$\displaystyle-
k_{0}x^{\top}\bar{E}_{i}^{2}(x-\bar{c}_{i})\\!\overset{\eqref{eq:ci,Ei}}{=}\\!-\tfrac{k_{0}}{2}\|\bar{E}_{i}x\|^{2}\\!-\\!\tfrac{k_{0}}{2}x^{\top}\bar{E}_{i}^{2}(x-c_{i})$
(80)
$\displaystyle\overset{\eqref{eq:dist_to_c_decreases}}{=}-\tfrac{k_{0}}{2}\|\bar{E}_{i}x\|^{2}+\tfrac{k_{0}}{2}\big{(}1-\|\bar{E}_{i}(x-\bar{c}_{i})\|^{2}\big{)}$
$\displaystyle=-\tfrac{k_{0}}{2}\|\bar{E}_{i}x\|^{2}\leq 0,$

where the last equality follows from
$x\in\mathcal{E}(\bar{c}_{i},\bar{E}_{i})$. Therefore,
$\\{-k_{0}x\\}\in\mathcal{P}_{\leq}(0,\bar{E}_{i}^{2}(x-\bar{c}_{i}))=\mathbf{T}_{\mathcal{E}(\bar{c}_{i},\bar{E}_{i})}(x)$.
For $x\in\mathcal{C}(0,c_{i},\vartheta_{i}(\delta,\mu_{i}),E_{i})$, we have

$\displaystyle-
k_{0}x^{\top}E_{i}\pi^{\vartheta_{i}(\delta,\mu_{i})}(E_{i}c_{i})E_{i}x=0.$
(81)

Therefore,
$\\{-k_{0}x\\}\in\mathcal{P}(0,E_{i}\pi^{\vartheta_{i}(\delta,\mu_{i})}(E_{i}c_{i})E_{i}x)=\mathbf{T}_{\mathcal{C}(0,c_{i},\vartheta_{i}(\delta,\mu_{i}),E_{i})}(x)$
(cf. (12)). Forward invariance follows then from the classical Nagumo’s
theorem.

Step 3: Proof of (49). Let
$\xi(t,j)=(x(t,j),i(t,j),m(t,j))\in\mathcal{F}_{l}\times\\{l\\}$ with
$l\in\\{-1,1\\}$ and $(t,j)\in\operatorname{dom}\xi$. Hence, by (38),

$\|x(t,j)\|\geq r_{i(t,j)}>0$ (82)

thanks to the discussion below (38). We further divide into mutually exclusive
subcases.

Step 3a: $\xi(t,j)\in(\mathcal{F}_{l}\cap\mathcal{J}_{l})\times\\{l\\}$ and
the solution jumps. By (30b) and (30e), $\xi(t,j+1)=(x(t,j),i(t,j),0)$.
Depending on $x(t,j)$, either the solution never jumps again or reaches the
set $\mathcal{J}_{0}^{*}$ in (42) at some $(t^{\prime},j+1)$. Consider the
former case. The flow map for $x$ in (30a) ensures
$x(\tau,j+1)=\exp(-k_{0}(\tau-t))x(t,j)$ for all $\tau\geq t$. By (82), $s\geq
t$ exists such that
$\|x(s,j+1)\|=\min_{i^{\prime}\in\mathbb{I}}r_{i^{\prime}}/2\\!=:\\!\sigma_{0}\\!>\\!0$.
So,

$\|x(s,j+1)\|+\sigma_{0}=\min_{i^{\prime}\in\mathbb{I}}r_{i^{\prime}}\leq
r_{i(t,j)}\leq\|x(t,j)\|$ (83)

and the claim of the proposition is proven. Consider the latter case, i.e.,
there exist $t^{\prime}\geq t$ and $i^{\prime}\in\mathbb{I}$ such that
$x(t^{\prime},j+1)\in\mathcal{J}_{0}^{i^{\prime}}\subset\mathcal{J}_{0}^{*}$.
$\mathcal{J}_{0}^{i^{\prime}}$ is a shrinking of the set
$\mathcal{F}^{i^{\prime}}_{1}\cup\mathcal{F}^{i^{\prime}}_{-1}$ by
construction of the flow and jump sets (cf. (23) and (26), where the union of
the cones from (26) gives n from the same arguments yielding (62)). Then, by
Lemma 5, there exist $l^{\prime}$ such that
$\xi(t^{\prime},j+2)\in(\mathcal{F}_{l^{\prime}}\backslash\mathcal{J}_{l^{\prime}})\times\\{l^{\prime}\\}$
and the solution is forced to flow as in Step 3b below.

Step 3b: $\xi(t,j)\in(\mathcal{F}_{l}\backslash\mathcal{J}_{l})\times\\{l\\}$
and the solution flows. If
$x(t,j)\in\mathcal{F}^{i}_{l}\backslash\mathcal{J}^{i}_{l}$, there exists
$\delta\in(\delta_{i},1]$ and $\psi\in(\psi_{i},\bar{\psi}_{i})$ such that
$x(t,j)\in\tilde{\mathcal{F}}^{i}_{l}(\delta,\psi)$ as defined in (75a). From
the facts

$\displaystyle\mathcal{H}_{i}(\delta,\mu_{i})\cap\mathcal{E}_{\geq}(c_{i},\delta_{i}E_{i})=\emptyset$
(84a) $\displaystyle\begin{aligned}
\mathcal{C}_{\geq}(c_{i},c_{i}-p_{l}^{i},\psi,E_{i})\cap\mathcal{C}_{\leq}(c_{i},&c_{i}-p_{l}^{i},\psi_{i},E_{i})\\\
&=\\{c_{i}\\}\notin\mathcal{E}_{\geq}(c_{i},E_{i}),\end{aligned}$ (84b)

$\tilde{\mathcal{F}}_{l}^{i}(\delta,\psi)\cap\mathcal{J}_{l}^{i}$ is a subset
of $\tilde{\mathcal{P}}_{l,3}^{i}(\delta,\psi)$ because

$\displaystyle\tilde{\mathcal{F}}_{l}^{i}(\delta,\psi)\cap\mathcal{J}_{l}^{i}=\mathcal{E}_{\leq}(c_{i},\delta
E_{i})\cap\mathcal{E}_{\geq}(c_{i},E_{i})$ $\displaystyle\hskip
11.38092pt\cap\mathcal{E}_{\geq}(\bar{c}_{i},\mu_{i}\bar{E}_{i})\cap\mathcal{C}_{\geq}(c_{i},c_{i}-p_{l}^{i},\psi,E_{i})\cap\mathcal{J}_{l}^{i}$
$\displaystyle\subset\mathcal{H}_{i}(\delta,\mu_{i})\cap\mathcal{C}_{\geq}(c_{i},c_{i}-p_{l}^{i},\psi,E_{i})$
$\displaystyle\hskip
11.38092pt\cap\big{(}\mathcal{E}_{\geq}(c_{i},\delta_{i}E_{i})\cup\mathcal{E}_{\leq}(\bar{c}_{i},\mu_{i}\bar{E}_{i})\cup\mathcal{C}_{\leq}(c_{i},c_{i}-p_{l}^{i},\psi_{i},E_{i})\big{)}$
$\displaystyle=\big{(}\mathcal{H}_{i}(\delta,\mu_{i})\cap\mathcal{C}_{\geq}(c_{i},c_{i}-p_{l}^{i},\psi,E_{i})\cap\mathcal{E}_{\geq}(c_{i},\delta_{i}E_{i})\big{)}$
$\displaystyle\hskip
11.38092pt\cup\big{(}\mathcal{H}_{i}(\delta,\mu_{i})\cap\mathcal{C}_{\geq}(c_{i},c_{i}-p_{l}^{i},\psi,E_{i})\cap\mathcal{E}_{\leq}(\bar{c}_{i},\mu_{i}\bar{E}_{i})\big{)}$
$\displaystyle\hskip
11.38092pt\cup\\!\big{(}\mathcal{H}_{i}(\delta,\mu_{i})\\!\cap\\!\mathcal{C}_{\geq}(c_{i},c_{i}\\!-\\!p_{l}^{i},\psi,E_{i})\\!\cap\\!\mathcal{C}_{\leq}(c_{i},c_{i}\\!-\\!p_{l}^{i},\psi_{i},E_{i}))\big{)}$
$\displaystyle\overset{\eqref{eq:auxiliary for intersection of tilde F^i_l and
J^i_l}}{=}\mathcal{H}_{i}(\delta,\mu_{i})\cap\mathcal{C}_{\geq}(c_{i},c_{i}-p_{l}^{i},\psi,E_{i})\cap\mathcal{E}_{\leq}(\bar{c}_{i},\mu_{i}\bar{E}_{i})$
$\displaystyle=\mathcal{E}_{\leq}(c_{i},\delta
E_{i})\\!\cap\\!\mathcal{E}_{\geq}(c_{i},E_{i})\\!\cap\\!\mathcal{E}(\bar{c}_{i},\mu_{i}\bar{E}_{i})\\!\cap\\!\mathcal{C}_{\geq}(c_{i},c_{i}\\!-\\!p^{i}_{l},\psi,E_{i})$
$\displaystyle\overset{\eqref{eq:tilde
P^i_m3}}{=}\tilde{\mathcal{P}}_{l,3}^{i}(\delta,\psi).$ (85)

This fact combined with Step 1, shows that the solution leaves the set
$\mathcal{F}_{l}^{i}$ in finite time through the set
$\tilde{\mathcal{P}}_{l,3}^{i}(\delta,\psi)$, where it jumps. Then, we have
$x(t^{\prime},j+1)=x(t^{\prime},j)\in\tilde{\mathcal{P}}_{m(t^{\prime},j),3}^{i(t^{\prime},j)}(\delta,\psi)$,
$i(t^{\prime},j+1)=i(t^{\prime},j)=:\iota$ and $m(t^{\prime},j)=0$. Then, by
(85), $x(t^{\prime},j+1)\in\mathcal{E}(c_{\iota},\delta
E_{\iota})\cap\mathcal{E}(\bar{c}_{\iota},\mu_{\iota}\bar{E}_{\iota})$, and,
by Lemma 8,
$x(t^{\prime},j+1)\in\mathcal{C}(0,c_{\iota},\vartheta_{\iota}(\delta,\mu_{\iota}),E_{\iota})$.
We have shown in Step 2 that both the sets
$\mathcal{E}_{\leq}(\bar{c}_{\iota},\bar{E}_{\iota})$ and
$\mathcal{C}(0,c_{\iota},\vartheta_{\iota}(\delta,\mu_{\iota}),E_{\iota})$ are
forward invariant under the stabilization flow map for $x$, i.e., $-k_{0}x$.
Since the obstacles are weakly disjoint, the solution then flows in
$\mathcal{E}_{\leq}(\bar{c}_{\iota},\bar{E}_{\iota})\cap\mathcal{C}(0,c_{\iota},\vartheta_{\iota}(\delta,\mu_{\iota}),E_{\iota})$
until it reaches the set $\mathcal{E}(c_{\iota},\delta_{\iota}E_{\iota})$ at
$(t^{\prime\prime},j+1)$. We either have
$\|x(t^{\prime\prime},j+1)\|<r_{\iota}$ or $\|x(t^{\prime\prime},j+1)\|\geq
r_{\iota}$. Consider the former case. Define

$\sigma_{1}\\!:=\\!\\!\\!\min_{{i,i^{\prime}\in\mathbb{I},\,i\neq
i^{\prime}}}\\!\\!\\!\mathbf{dist}(\mathcal{E}_{\leq}(c_{i},\delta_{i}E_{i}),\mathcal{E}_{\leq}(c_{i^{\prime}},\delta_{i^{\prime}}E_{i^{\prime}}))>0,$
(86)

which is positive because obstacle are compact, pairwise disjoint sets. Since
$x(t^{\prime\prime},j+1)\in\mathcal{E}(c_{\iota},\delta_{\iota}E_{\iota})$ and
the obstacles are weakly pairwise disjoint, the solution can only flow up to
the time $(s,j+1)$ such that $\sigma_{1}$ is traversed, i.e.,

$\|x(s,j+1)\|+\sigma_{1}\leq\|x(t^{\prime\prime},j+1)\|<r_{\iota}\leq\|x(t,j)\|,$
(87)

and the claim of the proposition is proven. Consider the latter case, i.e.,
$\|x(t^{\prime\prime},j+1)\|\geq r_{\iota}$. Then, the definition of the set
$\mathcal{R}_{\iota}(\delta_{\iota},\mu_{\iota})$ in (39) implies that
$x(t^{\prime\prime},j+1)\in\mathcal{R}_{\iota}(\delta_{\iota},\mu_{\iota})$.
However, thanks to (40), the solution can only flow with stabilization mode
while in $\mathcal{R}_{\iota}(\delta_{\iota},\mu_{\iota})$, so that
$(t^{\prime\prime\prime},j+1)$ exists such that
$\|x(t^{\prime\prime\prime},j+1)\|=r_{\iota}$. Define

$\sigma_{2}:=\min_{i,i^{\prime}\in\mathbb{I},i\neq
i^{\prime}}\mathbf{dist}(\mathcal{R}_{i}(\delta_{i},\mu_{i}),\mathcal{E}_{\leq}(c_{i^{\prime}},\delta_{i^{\prime}}E_{i^{\prime}}))>0,$
(88)

which is positive because the considered sets are compact and pairwise
sufficiently disjoint. Before a jump to avoidance mode at $(s,j+1)$ can occur,
we have

$\|x(s,j+1)\|+\sigma_{2}\leq\|x(t^{\prime\prime\prime},j+1)\|=r_{\iota}\leq\|x(t,j)\|.$
(89)

Step 3c: $\xi(t,j)\in(\mathcal{F}_{l}\cap\mathcal{J}_{l})\times\\{l\\}$ and
the solution flows. The solution cannot flow forever, as established in Step
1. If it flows until its component $x$ reaches the set
$\mathcal{P}_{l,3}^{i(t,j)}(\delta_{i(t,j)},\psi_{i(t,j)})$, the second part
of the argument of Step 3b still applies, in particular (87) or (89). If it
jumps beforehand, Step 3a applies. Then we do not have circularity. By
combining (83), (87) and (89), (49) is proven with
$\sigma:=\min\\{\sigma_{0},\sigma_{1},\sigma_{2}\\}>0$.

####  -16 Proof of Lemma 12

As for (77a), we have that $\mathbf{T}_{\mathcal{E}_{\leq}(c_{i},\delta
E_{i})}(x)$ is either n for $x\in\mathcal{E}_{<}(c_{i},\delta E_{i})$ or
$\mathcal{P}_{\leq}(0,E_{i}^{2}(x-c_{i}))$ for $x\in\mathcal{E}(c_{i},\delta
E_{i})$. For all $x\in\mathcal{E}_{\leq}(c_{i},\delta
E_{i})\supset\tilde{\mathcal{F}}_{m}^{i}(\delta,\psi)$,
$\mathfrak{u}(x)\in\mathcal{P}(0,E_{i}^{2}(x-c_{i}))$ (see (48)), so (77a) is
proven. A similar argument yields (77b). As for (77c), we note that

$\displaystyle\tilde{\mathcal{F}}_{m}^{i}(\delta,\psi)\backslash\tilde{\mathcal{P}}^{i}_{m,3}(\delta,\psi)\\!\\!=\\!\mathcal{E}_{\leq}(c_{i},\\!\delta
E_{i})\\!\cap\\!\mathcal{E}_{\geq}(c_{i},\\!E_{i})$ (90) $\displaystyle\hskip
15.0pt\\!\cap\\!\mathcal{E}_{\geq}(\bar{c}_{i},\\!\mu_{i}\bar{E}_{i})\\!\cap\\!\mathcal{C}_{\geq}\\!(c_{i},c_{i}\\!-\\!p_{m}^{i},\psi,E_{i})\backslash\Big{(}\mathcal{E}_{\leq}(c_{i},\delta
E_{i})$ $\displaystyle\hskip
15.0pt\\!\cap\\!\mathcal{E}_{\geq}\\!(c_{i},E_{i})\\!\cap\\!\mathcal{E}(\bar{c}_{i},\mu_{i}\bar{E}_{i})\\!\cap\\!\mathcal{C}_{\geq}(c_{i},c_{i}-p_{m}^{i},\psi,E_{i})\Big{)}$
$\displaystyle\overset{\eqref{eq:set
identities:c}}{=}\mathcal{E}_{\leq}(c_{i},\delta
E_{i})\cap\mathcal{E}_{\geq}(c_{i},E_{i})\cap\mathcal{E}_{>}(\bar{c}_{i},\mu_{i}\bar{E}_{i})$
$\displaystyle\hskip
15.0pt\cap\mathcal{C}_{\geq}(c_{i},c_{i}-p_{m}^{i},\psi,E_{i}).$

Then, for all
$x\in\tilde{\mathcal{F}}_{m}^{i}(\delta,\psi)\backslash\tilde{\mathcal{P}}^{i}_{m,3}(\delta,\psi)$,
$\mathbf{T}_{\mathcal{E}_{\geq}(\bar{c}_{i},\mu_{i}\bar{E}_{i})}(x)={}^{n}$
thanks to (90), and this proves (77c). As for (77d), we have that
$\mathbf{T}_{\mathcal{C}_{\geq}(c_{i},c_{i}-p_{m}^{i},\psi,E_{i})}(x)$ is
either n for $x\in\mathcal{C}_{>}(c_{i},c_{i}-p_{m}^{i},\psi,E_{i})$ or
$\mathcal{P}_{\geq}(0,n^{i}_{m}(x))$ for
$x\in\mathcal{C}(c_{i},c_{i}-p_{m}^{i},\psi,E_{i})$ with
$n_{m}^{i}(x):=E_{i}\pi^{\psi}(E_{i}(c_{i}-p_{m}^{i}))E_{i}(x-c_{i})$ by (12).
If we prove that $\mathfrak{u}(x)^{\top}n_{m}^{i}(x)\geq 0$ for all
$x\in\mathcal{C}(c_{i},c_{i}-p_{m}^{i},\psi,E_{i})\supset\tilde{\mathcal{F}}_{m}^{i}(\delta,\psi)$,
then (77d) holds. Indeed, this last step follows from

$\displaystyle\\!\mathfrak{u}(x)^{\top}\\!\cdot
n_{m}^{i}(x)\\!=\\!-k_{m}(x-p_{m}^{i})^{\top}\\!E_{i}\pi^{\perp}(E_{i}(x-c_{i}))E_{i}^{-1}$
(91) $\displaystyle\qquad\quad\cdot
E_{i}\pi^{\psi}(E_{i}(c_{i}-p_{m}^{i}))E_{i}(x-c_{i})$
$\displaystyle=k_{m}(p_{m}^{i}-c_{i})^{\top}E_{i}\pi^{\perp}(E_{i}(x-c_{i}))$
$\displaystyle\qquad\quad\cdot\pi^{\psi}(E_{i}(c_{i}-p_{m}^{i}))E_{i}(x-c_{i})$
$\displaystyle\overset{\eqref{eq:def:piTheta},\eqref{eq:proj-refl-
maps}}{=}k_{m}(p_{m}^{i}-c_{i})^{\top}E_{i}\pi^{\perp}(E_{i}(x-c_{i}))$
$\displaystyle\qquad\quad\cdot\big{(}\cos^{2}(\psi)I_{n}-\pi^{\parallel}(E_{i}(c_{i}-p_{m}^{i}))\big{)}E_{i}(x-c_{i})$
$\displaystyle=-k_{m}(p_{m}^{i}-c_{i})^{\top}E_{i}\pi^{\perp}(E_{i}(x-c_{i}))$
$\displaystyle\qquad\quad\cdot\pi^{\parallel}(E_{i}(c_{i}-p_{m}^{i}))E_{i}(x-c_{i})$
$\displaystyle\overset{\eqref{eq:proj-refl-
maps}}{=}k_{m}(c_{i}-p_{m}^{i})^{\top}E_{i}\pi^{\perp}(E_{i}(x-c_{i}))E_{i}(c_{i}-p_{m}^{i})$
$\displaystyle\qquad\quad\cdot(c_{i}-p_{m}^{i})^{\top}\\!E_{i}^{2}(x-c_{i})\|E_{i}(c_{i}-p_{m}^{i})\|^{-2}\\!\geq
0$

because for all $x\in\mathcal{C}(c_{i},c_{i}-p_{m}^{i},\psi,E_{i})$, one has
$x\in\mathcal{P}_{\geq}(c_{i},E_{i}^{2}(c_{i}-p_{m}^{i}))$.

## References

  * [1] M. Hoy, A. S. Matveev, and A. V. Savkin, “Algorithms for collision-free navigation of mobile robots in complex cluttered environments: a survey,” _Robotica_ , vol. 33, no. 3, pp. 463–497, 2015.
  * [2] O. Khatib, “Real-time obstacle avoidance for manipulators and mobile robots,” in _Autonomous robot vehicles_. Springer, 1986, pp. 396–404.
  * [3] D. E. Koditschek and E. Rimon, “Robot navigation functions on manifolds with boundary,” _Advances in applied mathematics_ , vol. 11, no. 4, pp. 412–442, 1990.
  * [4] H. G. Tanner and A. Kumar, “Formation stabilization of multiple agents using decentralized navigation functions.” in _Robotics: Science and systems_ , vol. 1, 2005, pp. 49–56.
  * [5] D. V. Dimarogonas, S. G. Loizou, K. J. Kyriakopoulos, and M. M. Zavlanos, “A feedback stabilization and collision avoidance scheme for multiple independent non-point agents,” _Automatica_ , vol. 42, no. 2, pp. 229–243, 2006.
  * [6] G. Roussos and K. J. Kyriakopoulos, “Decentralized and prioritized navigation and collision avoidance for multiple mobile robots,” in _Distributed Autonomous Robotic Systems_. Springer, 2013, pp. 189–202.
  * [7] G. Lionis, X. Papageorgiou, and K. J. Kyriakopoulos, “Locally computable navigation functions for sphere worlds,” in _IEEE International Conference on Robotics and Automation_ , 2007, pp. 1998–2003.
  * [8] I. Filippidis and K. J. Kyriakopoulos, “Navigation functions for focally admissible surfaces,” in _Amer. Control Conference_ , 2013, pp. 994–999.
  * [9] S. G. Loizou, “The navigation transformation,” _IEEE Trans. on Robotics_ , vol. 33, no. 6, pp. 1516–1523, 2017.
  * [10] C. Vrohidis, P. Vlantis, C. P. Bechlioulis, and K. J. Kyriakopoulos, “Prescribed time scale robot navigation,” _IEEE Robotics and Automation Letters_ , vol. 3, no. 2, pp. 1191–1198, 2018.
  * [11] A. D. Ames, X. Xu, J. W. Grizzle, and P. Tabuada, “Control barrier function based quadratic programs for safety critical systems,” _IEEE Trans. Automat. Contr._ , vol. 62, no. 8, pp. 3861–3876, 2017.
  * [12] P. Falcone, F. Borrelli, J. Asgari, H. E. Tseng, and D. Hrovat, “A real-time model predictive control approach for autonomous active steering,” _Nonlinear Model Predictive Control for Fast Systems, Grenoble, France_ , p. 7, 2006.
  * [13] M. Defoort, A. Kokosy, T. Floquet, W. Perruquetti, and J. Palos, “Motion planning for cooperative unicycle-type mobile robots with limited sensing ranges: A distributed receding horizon approach,” _Robotics and autonomous systems_ , vol. 57, no. 11, pp. 1094–1106, 2009.
  * [14] F. Wilson Jr, “The structure of the level surfaces of a Lyapunov function,” _Journal of Differential Equations_ , 1967.
  * [15] R. G. Sanfelice, _Robust hybrid control systems_. University of California, Santa Barbara, 2007.
  * [16] R. G. Sanfelice, M. J. Messina, S. E. Tuna, and A. R. Teel, “Robust hybrid controllers for continuous-time systems with applications to obstacle avoidance and regulation to disconnected set of points,” in _Amer. Control Conference_ , 2006, pp. 3352–3357.
  * [17] J. I. Poveda, M. Benosman, A. R. Teel, and R. G. Sanfelice, “A hybrid adaptive feedback law for robust obstacle avoidance and coordination in multiple vehicle systems,” in _Amer. Control Conference_ , 2018, pp. 616–621.
  * [18] P. Braun, C. M. Kellett, and L. Zaccarian, “Unsafe point avoidance in linear state feedback,” _IEEE Conference on Decision and Control_ , 2018.
  * [19] ——, “Explicit construction of robust avoidance controllers for linear systems,” 2018, available from https://hal.archives-ouvertes.fr/hal-01893027.
  * [20] S. Berkane, A. Bisoffi, and D. V. Dimarogonas, “A hybrid controller for obstacle avoidance in an $n$-dimensional euclidean space,” in _Europ. Control Conference_ , 2019, pp. 764–769.
  * [21] S. Paternain, D. E. Koditschek, and A. Ribeiro, “Navigation functions for convex potentials in a space with convex obstacles,” _IEEE Trans. Automat. Contr._ , vol. 63, no. 9, pp. 2944–2959, 2018.
  * [22] C. D. Meyer, _Matrix analysis and applied linear algebra_. SIAM, 2000.
  * [23] R. Engelking, _General topology_. Heldermann, 1989.
  * [24] R. Goebel, R. G. Sanfelice, and A. R. Teel, _Hybrid Dynamical Systems: modeling, stability, and robustness_. Princeton University Press, 2012.
  * [25] Y.-K. Choi, W. Wang, Y. Liu, and M.-S. Kim, “Continuous collision detection for two moving elliptic disks,” _IEEE Trans. on Robotics_ , vol. 22, no. 2, pp. 213–224, 2006.
  * [26] W. Wang, J. Wang, and M.-S. Kim, “An algebraic condition for the separation of two ellipsoids,” _Computer aided geometric design_ , vol. 18, no. 6, pp. 531–539, 2001.