#  Hybrid Feedback Control Design for Non-Convex Obstacle Avoidance

Mayur Sawant, Ilia Polushin, and Abdelhamid Tayebi This work was supported by
the National Sciences and Engineering Research Council of Canada (NSERC),
under the grants RGPIN-2020-06270 and RGPIN-2020-0644.M. Sawant, I. Polushin
and A. Tayebi are with the Department of Electrical and Computer Engineering,
Western University, London, ON N6A 3K7, Canada. (e-mail: msawant2, ipolushi,
atayebi@uwo.ca). A. Tayebi is also with the Department of Electrical
Engineering, Lakehead University, Thunder Bay, ON P7B 5E1, Canada. (e-mail:
atayebi@lakeheadu.ca).

###### Abstract

We develop an autonomous navigation algorithm for a robot operating in two-
dimensional environments containing obstacles, with arbitrary non-convex
shapes, which can be in close proximity with each other, as long as there
exists at least one safe path connecting the initial and the target location.
An instrumental transformation that modifies (virtually) the non-convex
obstacles, in a non-conservative manner, is introduced to facilitate the
design of the obstacle-avoidance strategy. The proposed navigation approach
relies on a hybrid feedback that guarantees global asymptotic stabilization of
a target location while ensuring the forward invariance of the modified
obstacle-free workspace. The proposed hybrid feedback controller guarantees
Zeno-free switching between the move-to-target mode and the obstacle-avoidance
mode based on the proximity of the robot with respect to the modified
obstacle-occupied workspace. Finally, we provide an algorithmic procedure for
the sensor-based implementation of the proposed hybrid controller and validate
its effectiveness via some numerical simulations.

##  I Introduction

Autonomous navigation, the problem of designing control strategies to guide a
robot to its goal while avoiding obstacles, is one of the fundamental problems
in robotics. One of the widely explored techniques in that regard is the
artificial potential fields (APF) [1] in which interplay between an attractive
field and a repulsive field allows the robot, in most of the cases, to safely
navigate towards the target. However, for certain inter-obstacle arrangements,
this approach is hampered by the existence of undesired local minima. The
navigation function (NF) based approach [2], which is directly applicable to
sphere world environments [3, 4], mitigates this issue by restricting the
influence of the repulsive field within a local neighbourhood of the obstacle
by means of a properly tuned parameter, and ensures almost111 Almost global
convergence here refers to the convergence from all initial conditions except
a set of zero Lebesgue measure. global convergence of the robot towards the
target location. To extend the applicability of the NF approach to
environments containing more general convex and star-shaped obstacles, one can
employ the diffeomorphic mappings developed in [3] and [5]. However, the
application of these diffeomorphic mappings requires a global knowledge of the
environment.

The NF-based approach was extended in [6] to environments containing curved
obstacles. The authors established sufficient conditions on the eccentricity
of the obstacles to guarantee almost global convergence to a neighborhood
surrounding the a priori unknown target location. This approach is applicable
to convex obstacles with smooth and sufficiently curved boundaries. In [7],
the authors presented a methodology for the design of a harmonic potential-
based NF that ensures almost global convergence to the target location in a
priori known environments that are diffeomorphic to the point world. This work
was subsequently extended in [8] to unknown environments using a sensor-based
approach. However, similar to the approach in [6], it is assumed that the
shapes of the obstacles become known when the robot visits their respective
neighborhoods.

In [9], the authors proposed a feedback controller based on Nagumo’s theorem
[10, Theorem 4.7], for autonomous navigation in environments with general
convex obstacles. The forward invariance of the obstacle-free space is ensured
by projecting the ideal velocity control vector (pointing towards the target)
onto the tangent cone at the boundary of the obstacle whenever it points
towards the obstacle. In [11], a control barrier function-based approach was
used for robot navigation in an environment with a single spherical obstacle.
It was shown that this approach does not guarantee global convergence to the
target location due to the existence of an undesired equilibrium.

In [12], a reactive power diagram-based approach was introduced for robots
navigating in a priori unknown environments. This approach guarantees almost
global asymptotic stabilization of the target location, provided that the
obstacles are sufficiently separated and strongly convex. This approach was
further extended in [13] to handle partially known non-convex environments,
where it is assumed that the robot possesses geometrical information about the
non-convex obstacles but lacks knowledge of their precise locations within the
workspace. However, due to the topological obstruction induced by the motion
space in the presence of obstacles for any continuous time-invariant vector
fields [2], the above-mentioned approaches provide at best almost global
convergence guarantees.

In [14], a time-varying vector field planner was proposed for the navigation
of a single robot in a sphere world. This planner leverages prescribed
performance control techniques to achieve predetermined convergence to a
neighborhood of the target location from any initial position, while ensuring
obstacle avoidance. In [15], hybrid control techniques were employed to
achieve robust global regulation to a target while avoiding a single spherical
obstacle. This approach was extended in [16] to the problem of steering a
group of planar robots to a neighborhood of an unknown source (emitting a
signal with measurable intensity), while avoiding a single obstacle. In [17],
the authors proposed a hybrid control law to globally asymptotically stabilize
a class of linear systems while avoiding neighbourhoods of unsafe points. In
[18] and [19], hybrid control techniques were employed to enable the robot to
operate in the obstacle-avoidance mode when in close proximity to an obstacle
or in the move-to-target mode when located away from obstacles. These
strategies bear resemblance to bug algorithms [20], which are commonly used
for point robot path planning. In [19, Definition 2], the proposed hybrid
controller is applicable for known $n-$dimensional environments with
sufficiently disjoint elliptical obstacles. On the other hand, in [18,
Assumption 10], the obstacles are assumed to be smooth and sufficiently
separated from each other. In [21], the authors proposed a discontinuous
feedback control law for autonomous robot navigation in partially known two-
dimensional environments. When a known obstacle is encountered, the control
vector aligns with the negative gradient of the Navigation Function (NF).
However, when close to an unknown obstacle, the robot moves along its
boundary, relying on the local curvature information of the obstacle. This
method is limited to point robots and, similar to [18], assumes smooth
obstacle boundaries without sharp edges. In our earlier work [22], we proposed
a hybrid feedback controller design to address the problem of autonomous robot
navigation in planar environments with arbitrarily shaped convex obstacles.

In the present work, which has been initiated in our preliminary conference
paper [23], we consider the autonomous robot navigation problem in a two-
dimensional space with arbitrarily-shaped non-convex obstacles which can be in
close proximity with each other. Unlike [12], [19] and [22], wherein the robot
is allowed to pass between any pair of obstacles, we require the existence of
a safe path joining the initial and the target location, as stated in
Assumptions 1 and 2. The main contributions of the present paper are as
follows:

  1. 1)

Asymptotic stability: the proposed autonomous navigation solution ensures
asymptotic stability of the target location for the robot operating in planar
environments with arbitrary non-convex obstacles.

  2. 2)

Arbitrarily-shaped obstacles: there are no restrictions on the shape of the
non-convex obstacles such as those mentioned in [6], [12], [19], and their
proximity with respect to each other e.g., see [18, Assumption 10], [19,
Definition 2], except for the mild feasibility Assumptions 1 and 2.

  3. 3)

Applicable in a priori unknown environments: the proposed obstacle avoidance
approach can be implemented using only range scanners (e.g., LiDAR) without an
a priori global knowledge of the environment which satisfies Assumptions 1 and
2.

The remainder of the paper is organized as follows. In Section II, we provide
the notations and some preliminaries that will be used throughout the paper.
The problem is formulated in Section III. The design of the obstacle reshaping
operator is provided in Section IV, and the proposed hybrid control algorithm
is presented in Section V. The stability and safety guarantees of the proposed
navigation control scheme are provided in Section VI. A sensor-based
implementation of the proposed obstacle avoidance algorithm, using 2D range
scanners (LiDAR), is given in Section VII. Simulation results are presented in
Section VIII, and some final concluding remarks are given in Section IX.

##  II Notations and Preliminaries

###  II-A Notations

The sets of real and natural numbers are denoted by $\mathbb{R}$ and
$\mathbb{N}$, respectively. We identify vectors using bold lowercase letters.
The Euclidean norm of a vector $\mathbf{p}\in\mathbb{R}^{n}$ is denoted by
$\lVert\mathbf{p}\rVert$, and an Euclidean ball of radius $r>0$ centered at
$\mathbf{p}$ is represented by
$\mathcal{B}_{r}(\mathbf{p})=\\{\mathbf{q}\in\mathbb{R}^{n}|\lVert\mathbf{q}-\mathbf{p}\rVert\leq
r\\}.$ Given two vectors $\mathbf{p}\in\mathbb{R}^{2}$ and
$\mathbf{q}\in\mathbb{R}^{2}$, we denote by
$\measuredangle(\mathbf{p},\mathbf{q})$ the angle from $\mathbf{p}$ to
$\mathbf{q}$. The angle measured in counter-clockwise manner is considered
positive, and vice versa. Given two locations
$\mathbf{p},\mathbf{q}\in\mathbb{R}^{n}$, the notation
$\textbf{path}(\mathbf{p},\mathbf{q})$ represents a continuous path in
$\mathbb{R}^{n}$, which joins these locations. A set
$\mathcal{A}\subset\mathbb{R}^{n}$ is said to be pathwise connected if for any
two points $\mathbf{p},\mathbf{q}\in\mathcal{A}$, there exists a continuous
path, joining $\mathbf{p}$ and $\mathbf{q}$, that belongs to the same set
i.e., there exists a $\textbf{path}(\mathbf{p},\mathbf{q})\subset\mathcal{A}$
[24, Definition 27.1]. For two sets
$\mathcal{A},\mathcal{B}\subset\mathbb{R}^{n}$, the relative complement of
$\mathcal{B}$ with respect to $\mathcal{A}$ is denoted by
$\mathcal{A}\setminus\mathcal{B}=\\{\mathbf{a}\in\mathcal{A}|\mathbf{a}\notin\mathcal{B}\\}$.
Given a set $\mathcal{A}\subset\mathbb{R}^{n}$, the symbols
$\partial\mathcal{A},\mathcal{A}^{\circ}$, $\mathcal{A}^{c}$ and
$\bar{\mathcal{A}}$ represent the boundary, interior, complement and the
closure of the set $\mathcal{A}$, respectively, where
$\partial\mathcal{A}=\bar{\mathcal{A}}\backslash\mathcal{A}^{\circ}$. The
number of elements in a set $\mathcal{A}$ is given by
$\mathbf{card}(\mathcal{A})$. Let $\mathcal{A}$ and $\mathcal{B}$ be subsets
of $\mathbb{R}^{n}$, then the dilation of $\mathcal{A}$ by $\mathcal{B}$ is
denoted by
$\mathcal{A}\oplus\mathcal{B}=\\{\mathbf{a}+\mathbf{b}|\mathbf{a}\in\mathcal{A},\mathbf{b}\in\mathcal{B}\\},$
and the erosion of $\mathcal{A}$ by $\mathcal{B}$ is denoted by
$\mathcal{A}\ominus\mathcal{B}=\\{\mathbf{x}\in\mathbb{R}^{n}|\mathbf{x}+\mathbf{b}\in\mathcal{A},\forall\mathbf{b}\in\mathcal{B}\\}$
[25]. Additionally, the set $\mathcal{B}$ is referred to as a structuring
element. Given a positive scalar $r>0$, the $r-$dilated version of the set
$\mathcal{A}\subset\mathbb{R}^{n}$ is denoted by
$\mathcal{D}_{r}(\mathcal{A})=\mathcal{A}\oplus\mathcal{B}_{r}(\mathbf{0})$.
The $r-$neighbourhood of the set $\mathcal{A}$ is denoted by
$\mathcal{N}_{r}(\mathcal{A})=\mathcal{D}_{r}(\mathcal{A})\setminus\mathcal{A}^{\circ}$.

###  II-B Projection on a set

Given a closed set $\mathcal{A}\subset\mathbb{R}^{n}$ and a point
$\mathbf{x}\in\mathbb{R}^{n}$, the Euclidean distance of $\mathbf{x}$ from the
set $\mathcal{A}$ is evaluated as

$d(\mathbf{x},\mathcal{A})=\underset{\mathbf{q}\in\mathcal{A}}{\min}\lVert\mathbf{x}-\mathbf{q}\rVert.$
(1)

The set $\mathcal{PJ}(\mathbf{x},\mathcal{A})\subset\mathcal{A}$, which is
defined as

$\mathcal{PJ}(\mathbf{x},\mathcal{A})=\\{\mathbf{q}\in\mathcal{A}|\lVert\mathbf{x}-\mathbf{q}\rVert=d(\mathbf{x},\mathcal{A})\\},$
(2)

is the set of points in $\mathcal{A}$ that are at the distance of
$d(\mathbf{x},\mathcal{A})$ from $\mathbf{x}$. If
$\mathbf{card}(\mathcal{PJ}(\mathbf{x},\mathcal{A}))$ is one, then the element
of the set $\mathcal{PJ}(\mathbf{x},\mathcal{A})$ is denoted by
$\Pi(\mathbf{x},\mathcal{A})$.

###  II-C Sets with positive reach

Given a closed set $\mathcal{A}\subset\mathbb{R}^{n}$, the set
$\text{Unp}(\mathcal{A})$, which is defined as

$\text{Unp}(\mathcal{A})=\\{\mathbf{x}\in\mathbb{R}^{n}|\textbf{card}(\mathcal{PJ}(\mathbf{x},\mathcal{A}))=1\\},$
(3)

denotes the set of all $\mathbf{x}\in\mathbb{R}^{n}$ for which there exists a
unique point in $\mathcal{A}$ nearest to $\mathbf{x}$. Then, for any
$\mathbf{x}\in\mathcal{A}$, the reach of set $\mathcal{A}$ at $\mathbf{x}$,
denoted by $\textbf{r}(\mathcal{A},\mathbf{x})$ [26, Pg 55], is defined as

$\mathbf{r}(\mathcal{A},\mathbf{x}):=\sup\\{r\geq
0|\mathcal{B}_{r}^{\circ}(\mathbf{x})\subset\text{Unp}(\mathcal{A})\\}.$ (4)

The reach of set $\mathcal{A}$ is then given by

$\textbf{reach}(\mathcal{A}):=\underset{\mathbf{x}\in\mathcal{A}}{\inf}\mathbf{r}(\mathcal{A},\mathbf{x}).$
(5)

If a closed set has reach greater than or equal to $r>0$, then any location
less than $r$ distance away from the set will have a unique closest point on
the set.

###  II-D Geometric sets

####  II-D1 Line

Let $\mathbf{p}\in\mathbb{R}^{n}$ and
$\mathbf{q}\in\mathbb{R}^{n}\setminus\\{\mathbf{0}\\}$, then a line passing
through the point $\mathbf{p}$ in the direction of the vector $\mathbf{q}$ is
defined as

$\mathcal{L}(\mathbf{p},\mathbf{q}):=\left\\{\mathbf{x}\in\mathbb{R}^{n}|\mathbf{x}=\mathbf{p}+\lambda\mathbf{q},\lambda\in\mathbb{R}\right\\}.$
(6)

####  II-D2 Line segment

Let $\mathbf{p}\in\mathbb{R}^{n}$ and $\mathbf{q}\in\mathbb{R}^{n}$, then a
line segment joining $\mathbf{p}$ and $\mathbf{q}$ is denoted by

$\mathcal{L}_{s}(\mathbf{p},\mathbf{q}):=\left\\{\mathbf{x}\in\mathbb{R}^{n}|\mathbf{x}=\lambda\mathbf{p}+(1-\lambda)\mathbf{q},\lambda\in[0,1]\right\\}.$
(7)

####  II-D3 Hyperplane

Given $\mathbf{p}\in\mathbb{R}^{n}$ and
$\mathbf{q}\in\mathbb{R}^{n}\setminus\\{\mathbf{0}\\}$, a hyperplane passing
through $\mathbf{p}$ and orthogonal to $\mathbf{q}$ is given by

$\mathcal{P}(\mathbf{p},\mathbf{q}):=\\{\mathbf{x}\in\mathbb{R}^{n}|\mathbf{q}^{\intercal}(\mathbf{x}-\mathbf{p})=0\\}.$
(8)

The hyperplane divides the Euclidean space $\mathbb{R}^{n}$ into two half-
spaces i.e., a closed positive half-space
$\mathcal{P}_{\geq}(\mathbf{p},\mathbf{q})$ and a closed negative half-space
$\mathcal{P}_{\leq}(\mathbf{p},\mathbf{q})$ which are obtained by substituting
‘$=$’ with ‘$\geq$’ and ‘$\leq$’ respectively, in the right-hand side of (8).
We also use the notations $\mathcal{P}_{>}(\mathbf{p},\mathbf{q})$ and
$\mathcal{P}_{<}(\mathbf{p},\mathbf{q})$ to denote the open positive and the
open negative half-spaces such that
$\mathcal{P}_{>}(\mathbf{p},\mathbf{q})=\mathcal{P}_{\geq}(\mathbf{p},\mathbf{q})\backslash\mathcal{P}(\mathbf{p},\mathbf{q})$
and
$\mathcal{P}_{<}(\mathbf{p},\mathbf{q})=\mathcal{P}_{\leq}(\mathbf{p},\mathbf{q})\backslash\mathcal{P}(\mathbf{p},\mathbf{q})$.

####  II-D4 Convex cone

Given $\mathbf{c}\in\mathbb{R}^{n}$,
$\mathbf{p}_{1}\in\mathbb{R}^{n}\setminus\\{\mathbf{c}\\}$, and
$\mathbf{p}_{2}\in\mathbb{R}^{n}\setminus\\{\mathbf{c}\\}$, a convex cone with
its vertex at $\mathbf{c}$ and its edges passing through $\mathbf{p}_{1}$ and
$\mathbf{p}_{2}$ is defined as

$\displaystyle\mathcal{C}(\mathbf{c},\mathbf{p}_{1},\mathbf{p}_{2}):=\\{$
$\displaystyle\mathbf{x}\in\mathbb{R}^{n}|\mathbf{x}=\mathbf{c}+\lambda_{1}(\mathbf{p}_{1}-\mathbf{c})+\lambda_{2}(\mathbf{p}_{2}-\mathbf{c}),$
(9) $\displaystyle\forall\lambda_{1}\geq 0,\forall\lambda_{2}\geq 0\\}.$

####  II-D5 Conic hull [27, Section 2.1.5]

Given a set $\mathcal{A}\subset\mathbb{R}^{n}$ and a point
$\mathbf{x}\in\mathbb{R}^{n}$, the conic hull
$\mathcal{CH}(\mathbf{x},\mathcal{A})$ for the set $\mathcal{A}$, with its
vertex at $\mathbf{x}$ is defined as

$\mathcal{CH}(\mathbf{x},\mathcal{A}):=\bigcup_{\mathbf{p},\mathbf{q}\in\mathcal{A}}\mathcal{C}(\mathbf{x},\mathbf{p},\mathbf{q}).$
(10)

The conic hull $\mathcal{CH}(\mathbf{x},\mathcal{A})$ is the smallest convex
cone with its vertex at $\mathbf{x}$ that contains the set $\mathcal{A}$ i.e.,
$\mathcal{A}\subset\mathcal{CH}(\mathbf{x},\mathcal{A}).$

###  II-E Tangent cone and Normal cone

Given a closed set $\mathcal{A}\subset\mathbb{R}^{n}$, the tangent cone to
$\mathcal{A}$ at a point $\mathbf{x}\in\mathbb{R}^{n}$ [10, Def 4.6] is
defined by

$\mathbf{T}_{\mathcal{A}}(\mathbf{x}):=\left\\{\mathbf{w}\in\mathbb{R}^{n}\bigg{|}\underset{\tau\rightarrow
0^{+}}{\text{lim inf
}}\frac{d(\mathbf{x}+\tau\mathbf{w},\mathcal{A})}{\tau}=0\right\\}.$ (11)

The tangent cone to the set $\mathcal{A}$ at $\mathbf{x}$ is the set that
contains all the vectors whose directions point from $\mathbf{x}$ either
inside or tangent to the set $\mathcal{A}$. Given a tangent cone to a set
$\mathcal{A}$ at a point $\mathbf{x}$, the normal cone to the set
$\mathcal{A}$ at the point $\mathbf{x}$, as defined in [26, Pg 58], is given
by

$\mathbf{N}_{\mathcal{A}}(\mathbf{x}):=\left\\{\mathbf{p}\in\mathbb{R}^{n}\big{|}\mathbf{p}^{\intercal}\mathbf{w}\leq
0,\forall\mathbf{w}\in\mathbf{T}_{\mathcal{A}}(\mathbf{x})\right\\}.$ (12)

The next two lemmas provide some properties of the sets with positive reach,
which will be used in the paper.

######  Lemma 1.

Given a closed set $\mathcal{A}\subset\mathbb{R}^{n}$, we define the set
$\mathcal{G}=\left(\mathcal{A}\oplus\mathcal{B}_{\alpha}^{\circ}(\mathbf{0})\right)^{c}.$
If $\textbf{reach}(\mathcal{A})\geq\alpha$, then
$\textbf{reach}(\mathcal{G})\geq\alpha$.

###### Proof.

See Appendix -B. ∎

######  Lemma 2.

Consider a closed set $\mathcal{A}\subset\mathbb{R}^{n}$ and scalars
$\alpha\geq\beta\geq 0$. If $\textbf{reach}(\mathcal{A})\geq\alpha,$ then
$\textbf{reach}(\mathcal{D}_{\beta}(\mathcal{A}))\geq\alpha-\beta.$

###### Proof.

See Appendix -C. ∎

###  II-F Hybrid system framework

A hybrid dynamical system [28] is represented using differential and
difference inclusions for the state $\mathbf{\xi}\in\mathbb{R}^{n}$ as
follows:

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

where the flow map $\mathbf{F}:\mathbb{R}^{n}\rightrightarrows\mathbb{R}^{n}$
is the differential inclusion which governs the continuous evolution when
$\mathbf{\xi}$ belongs to the flow set $\mathcal{F}\subseteq\mathbb{R}^{n}$,
where the symbol ‘$\rightrightarrows$’ represents set-valued mapping. The jump
map $\mathbf{J}:\mathbb{R}^{n}\rightrightarrows\mathbb{R}^{n}$ is the
difference inclusion that governs the discrete evolution when $\mathbf{\xi}$
belongs to the jump set $\mathcal{J}\subseteq\mathbb{R}^{n}$. The hybrid
system (13) is defined by its data and denoted as
$\mathcal{H}=(\mathcal{F},\mathbf{F},\mathcal{J},\mathbf{J}).$

A subset $\mathbb{T}\subset\mathbb{R}_{\geq 0}\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\\},$ where the last interval (if existent) is
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 $\phi$ is maximal if it cannot be
extended, and complete if its domain dom $\phi$ (which is a hybrid time
domain) is unbounded.

##  III Problem Formulation

We consider a disk-shaped robot operating in a two dimensional, compact,
arbitrarily-shaped (possibly non-convex) subset of the Euclidean space
$\mathcal{W}\subset\mathbb{R}^{2}$. The workspace $\mathcal{W}$ is cluttered
with a finite number of compact, pairwise disjoint obstacles
$\mathcal{O}_{i}\subset\mathcal{W},i\in\\{1,\ldots,b\\},b\in\mathbb{N}$.  We
define obstacle $\mathcal{O}_{0}:=(\mathcal{W}^{\circ})^{c}$ as the complement
of the interior of the workspace. The robot is governed by single integrator
dynamics

$\mathbf{\dot{x}}=\mathbf{u},$ (14)

where $\mathbf{x}$ is the location of the center of the robot and
$\mathbf{u}\in\mathbb{R}^{2}$ is the control input. The task is to reach a
predefined obstacle-free target location from any obstacle-free region while
avoiding collisions. Without loss of generality, consider the origin
$\mathbf{0}$ as the target location.

We define the obstacle-occupied workspace as
$\mathcal{O}_{\mathcal{W}}:=\bigcup_{i\in\mathbb{I}}\mathcal{O}_{i},$ where
the set $\mathbb{I}:=\\{0,1,...,b\\}$, contains indices corresponding to the
disjoint obstacles. The obstacle-free workspace is denoted by
$\mathcal{W}_{0}$, where, given $y\geq 0$, the $y-$eroded version of the
obstacle-free workspace i.e., $\mathcal{W}_{y}$ is defined as

$\mathcal{W}_{y}:=\mathbb{R}^{2}\setminus\mathcal{D}_{y}(\mathcal{O}_{\mathcal{W}}^{\circ})\subset\mathcal{W}_{0}.$
(15)

Let $r>0$ be the radius of the robot and $r_{s}>0$ be the minimum distance
that the robot should maintain with respect to any obstacle for safe
navigation. Hence, $\mathcal{W}_{r_{a}}$, with $r_{a}=r+r_{s}$, is a free
workspace with respect to the center of the robot i.e.,
$\mathbf{x}\in\mathcal{W}_{r_{a}}\iff\mathcal{B}_{r_{a}}(\mathbf{x})\subset\mathcal{W}_{0}$.
Since the obstacles can be non-convex and can be in close proximity with each
other, to maintain the feasibility of the robot navigation, we make the
following assumption:

Figure 1: Two examples of workspaces that do not satisfy Assumption 1.

######  Assumption 1.

The interior of the obstacle-free workspace w.r.t. the center of the robot
i.e., $\mathcal{W}_{r_{a}}^{\circ}$ is pathwise connected, and
$\mathbf{0}\in\mathcal{W}_{r_{a}}^{\circ}$.

According to Assumption 1, from any location in the set $\mathcal{W}_{r_{a}}$,
there exists at least one feasible path to the target location. We require the
origin to be in the interior of the set $\mathcal{W}_{r_{a}}$ to ensure its
stability, as discussed later in Theorem 1. Since we require the interior of
the set $\mathcal{W}_{r_{a}}$ to be pathwise connected, the environments, such
as the ones showed in Fig. 1, which do not satisfy Assumption 1, are invalid.

Figure 2: (a) The original obstacle $\mathcal{O}_{i}\subset\mathbb{R}^{2}$.
(b) Dilation of obstacle $\mathcal{O}_{i}$ by a structuring element
$\mathcal{B}_{\alpha}^{\circ}(\mathbf{0}),\alpha>0$. (c) Erosion of the
dilated obstacle
$\mathcal{O}_{i}\oplus\mathcal{B}_{\alpha}^{\circ}(\mathbf{0})$ by the same
structuring element $\mathcal{B}_{\alpha}^{\circ}(\mathbf{0})$.

The obstacle-avoidance strategy, which will be detailed later in Section V,
requires a unique closest point on the obstacle-occupied workspace from the
robot’s center. This condition is not always satisfied in the case of non-
convex and closely positioned obstacles. Constructing convex hulls around the
non-convex obstacles is conservative solution since it makes much of the
obstacle-free workspace non-available for navigation. Therefore, in Section
IV, we will introduce an obstacle reshaping technique that generates a
modified obstacle-occupied workspace $\mathcal{O}_{\mathcal{W}}^{M}$, in a
less conservative manner (without necessarily convexifying the obstacles), in
a way that ensures uniqueness of the closest point on
$\mathcal{O}_{\mathcal{W}}^{M}$ from the robot’s center.

Similar to $\mathcal{W}_{y}$ in (15), the $y-$eroded modified obstacle-free
workspace, which is denoted by $\mathcal{V}_{y}$, is defined as

$\mathcal{V}_{y}:=\mathbb{R}^{2}\setminus\mathcal{D}_{y}(\mathcal{O}_{\mathcal{W}}^{M})^{\circ},$
(16)

where $y\geq 0$. Hence, the set $\mathcal{V}_{r_{a}}$ denotes the modified
obstacle-free workspace with respect to the center of the robot. We construct
$\mathcal{O}_{\mathcal{W}}^{M}$ such that the modified obstacle-free workspace
$\mathcal{V}_{r_{a}}$ is a subset of the original obstacle-free workspace
$\mathcal{W}_{r_{a}}$, as stated with more details later in Remark 6.

Given a target location in the interior of the obstacle-free workspace, i.e.,
$\mathbf{0}\in(\mathcal{W}_{r_{a}})^{\circ}$, as stated in Assumption 1, we
aim to design a hybrid feedback control law such that:

  1. 1.

the set $\mathcal{V}_{r_{a}}$ is forward invariant.

  2. 2.

the target location $\mathbf{x}=0$ is globally asymptotically stable.

As it is going to be shown later, the obstacle reshaping procedure guarantees
that if the target location belongs to $(\mathcal{W}_{r_{a}})^{\circ}$ then it
also belongs to $\mathcal{V}_{r_{a}}$.

We use hybrid feedback control techniques [28] to develop a navigation scheme
for the robot operating in environments that satisfy Assumption 1. The design
process can be summarized as follows:

  1. 1.

the proposed hybrid navigation scheme involves two modes of operation for the
robot: move-to-target and obstacle-avoidance. The design of the obstacle
avoidance strategy requires a unique projection onto the unsafe region within
its close proximity. However, ensuring this uniqueness can be challenging in
cases where obstacles have arbitrary shapes and are in close proximity to one
another. Hence, before implementing the hybrid navigation scheme, we first
transform the obstacle-occupied workspace using an obstacle-reshaping
operator, as discussed later in Section IV, to obtain the modified obstacle-
occupied workspace. This operator transforms the obstacle-occupied workspace
and guarantees the uniqueness of the projection of the robot’s center onto the
modified obstacle-occupied workspace in its $\alpha$-neighbourhood, where the
parameter $\alpha$ is chosen as per Lemma 5.

  2. 2.

when the center of the robot is outside the $\alpha$-neighbourhood of the
modified obstacle-occupied workspace or the nearest disjoint modified obstacle
does not intersect with its straight path to the target location, the robot
moves straight towards the target in the move-to-target mode.

  3. 3.

when the center of the robot enters the $\alpha-$neighbourhood of the modified
obstacle that is obstructing its straight path towards the target location,
the robot switches to the obstacle-avoidance mode.

  4. 4.

in the obstacle-avoidance mode, to avoid collision, the robot moves parallel
to the boundary of the nearest modified obstacle until it reaches the location
at which the following two conditions are satisfied: 1) the robot is closer to
the target location than the location where it entered in the obstacle-
avoidance mode; 2) the straight path towards the target from that location
does not intersect with the nearest disjoint modified obstacle. At this
location, the robot switches back to the move-to-target mode.

  5. 5.

later in Lemma 6, we show that the target location belongs to the modified
obstacle-free workspace, and from any location away from the interior of the
modified obstacle-occupied workspace, there exists a feasible path towards the
target location. Hence, with a consecutive implementation of steps $2-4$ for
the environment with modified obstacle-occupied workspace, we guarantee
asymptotic convergence of the center of the robot to the target location.

In the next section, we provide the transformation that modifies the obstacle-
occupied workspace $\mathcal{O}_{\mathcal{W}}$ which satisfies Assumption 1,
such that the robot always has a unique closest point on the modified
obstacle-occupied workspace inside its $\alpha-$neighbourhood.

##  IV Obstacle reshaping

Given an obstacle-occupied workspace $\mathcal{O}_{\mathcal{W}}$ that
satisfies Assumption 1, the objective of the obstacle-reshaping task is to
obtain a modified obstacle-occupied workspace $\mathcal{O}_{\mathcal{W}}^{M}$
such that every location less than $\alpha-$distance away from the set
$\mathcal{O}_{\mathcal{W}}^{M}$ has a unique closest point on the set. The
choice of the parameter $\alpha$ is crucial for the successful implementation
of the proposed navigation scheme, as stated later in Lemma 5. For now, we
assume that $\alpha>0$ such that the $\alpha-$eroded obstacle-free workspace
$\mathcal{W}_{\alpha}$ is not an empty set. The obstacle-reshaping operator
$\mathbf{M}$ is defined as

$\mathbf{M}(\mathcal{O}_{\mathcal{W}},\alpha)=(\mathcal{O}_{\mathcal{W}}\oplus\mathcal{B}_{\alpha}^{\circ}(\mathbf{0}))\ominus\mathcal{B}_{\alpha}^{\circ}(\mathbf{0})=:\mathcal{O}_{\mathcal{W}}^{M}.$
(17)

The operator $\mathbf{M}$ first dilates the obstacle-occupied workspace
$\mathcal{O}_{\mathcal{W}}$ using the open Euclidean ball of radius $\alpha$
centered at the origin as the structuring element, and then erodes the dilated
set using the same structuring element, resulting in the modified obstacle-
occupied workspace $\mathcal{O}_{\mathcal{W}}^{M}$. This process is similar to
the closing operator commonly used in the field of mathematical morphology
[25]. Note that the proposed modification scheme is applicable to
$n-$dimensional environments. Next, we discuss some of the features of the
obstacle-reshaping operator $\mathbf{M}.$

######  Remark 1.

Consider the modified obstacle-occupied workspace
$\mathcal{O}_{\mathcal{W}}^{M}$ obtained after applying the operator
$\mathbf{M}$ on the obstacle-occupied workspace $\mathcal{O}_{\mathcal{W}}$
with $\alpha>0.$ Some of the features of the obstacle-reshaping operator
$\mathbf{M}$, as stated in [29, Table 1], are as follows:
Idempotent: the application of the transformation $\mathbf{M}$ to a modified
obstacle $\mathcal{O}_{\mathcal{W}}^{M}$ with the same structuring element
(the open Euclidean ball $\mathcal{B}_{\alpha}^{\circ}(\mathbf{0})$), does not
change the set $\mathcal{O}_{\mathcal{W}}^{M}$ i.e.,

$\mathbf{M}(\mathbf{M}(\mathcal{O}_{\mathcal{W}},\alpha),\alpha)=\mathbf{M}(\mathcal{O}_{\mathcal{W}},\alpha)=\mathcal{O}_{\mathcal{W}}^{M}.$
(18)

Extensive: the modified set always contains the original set i.e.,
$\mathcal{O}_{\mathcal{W}}\subset\mathcal{O}_{\mathcal{W}}^{M}.$
Increasing: for any subset $\mathcal{A}\subset\mathcal{O}_{\mathcal{W}}$, the
modified set $\mathcal{A}^{M}$ always belongs to the modified set
$\mathcal{O}_{\mathcal{W}}^{M}$ i.e.,
$\mathcal{A}^{M}\subset\mathcal{O}_{\mathcal{W}}^{M}.$

Notice that, by duality of dilation and erosion [25, Theorem 25], the dilation
of a set, with an open Euclidean ball centered at the origin as the
structuring element, is equivalent to the erosion of the complement of that
set with the same structuring element. This allows us to provide alternative
representations of the proposed obstacle-reshaping operator, as stated in the
next remark.

######  Remark 2.

The $\alpha-$eroded obstacle-free workspace $\mathcal{W}_{\alpha}$, defined
according to (15), is equivalent to the complement of the set obtained after
dilating the obstacle-occupied workspace $\mathcal{O}_{\mathcal{W}}$ with the
open Euclidean ball of radius $\alpha$ centered at the origin
$\mathcal{B}_{\alpha}^{\circ}(\mathbf{0})$ i.e.,
$\mathcal{W}_{\alpha}=(\mathcal{O}_{\mathcal{W}}\oplus\mathcal{B}_{\alpha}^{\circ}(\mathbf{0}))^{c}$.
Therefore, by duality of dilation and erosion [25, Theorem 25], the modified
obstacle-occupied workspace is equivalent to the complement of the set
obtained after dilating $\mathcal{W}_{\alpha}$ by the open Euclidean ball of
radius $\alpha$ centered at the origin
$\mathcal{B}_{\alpha}^{\circ}(\mathbf{0})$. In other words,

$\mathbf{M}(\mathcal{O}_{\mathcal{W}},\alpha)=(\mathcal{W}_{\alpha}\oplus\mathcal{B}_{\alpha}^{\circ}(\mathbf{0}))^{c}=\mathcal{W}_{\alpha}^{c}\ominus\mathcal{B}_{\alpha}^{\circ}(\mathbf{0}).$
(19)

The operator $\mathbf{M}$ does not guarantee a unique projection onto the
modified obstacle from every point in its $\alpha-$neighbourhood. To
illustrate this fact, we consider an environment with two obstacles
$\mathcal{O}_{\mathcal{W}}=\mathcal{O}_{i}\cup\mathcal{O}_{j}$ such that
$d(\mathcal{O}_{i},\mathcal{O}_{j})<2\alpha,$ as shown in Fig. 3. In Fig. 3b,
one can see that the operation $\mathbf{M}(\mathcal{O}_{\mathcal{W}},\alpha)$
has fused these obstacles into a single set, represented in black. However,
depending on the arrangement of the obstacles, it may happen that even though
$d(\mathcal{O}_{i},\mathcal{O}_{j})<2\alpha$, the modified obstacle-occupied
workspace $\mathcal{O}_{\mathcal{W}}^{M}$ contains two disjoint modified
obstacles which are less than $2\alpha$ distance apart from each other, as
shown in Fig. 3a. In this case, it is possible to find a location $\mathbf{x}$
less than $\alpha$ distance away from the set $\mathcal{O}_{\mathcal{W}}^{M}$
which has multiple closest points on the set $\mathcal{O}_{\mathcal{W}}^{M}$,
as shown in Fig. 3a.

Observe that in Fig. 3a, the open Euclidean balls of radius $\alpha$ centered
at the locations $\mathbf{c}_{1}$ and $\mathbf{c}_{2}$ intersect each other.
Hence, when the set
$\mathcal{O}_{\mathcal{W}}\oplus\mathcal{B}_{\alpha}^{\circ}(\mathbf{0})$ is
eroded to obtain the modified obstacle-occupied workspace (17), two disjoint
modified obstacles are obtained, even though
$d(\mathcal{O}_{i},\mathcal{O}_{j})<2\alpha$. As a result, at the location
$\mathbf{x}$ inside the $\alpha-$dilated modified obstacle, one can get
multiple projections, as shown in Fig. 3a.

Figure 3: Workspace with two obstacles
$\mathcal{O}_{\mathcal{W}}=\mathcal{O}_{i}\cup\mathcal{O}_{j}$ such that
$d(\mathcal{O}_{i},\mathcal{O}_{j})<2\alpha$. Left figure shows that the set
$\mathcal{O}_{\mathcal{W}}^{M}$ is not a connected set. Right figure shows
that the set $\mathcal{O}_{\mathcal{W}}^{M}$ is a connected set.

To guarantee a unique projection onto the modified obstacle from all locations
inside its $\alpha-$neighbourhood, we require the following assumption on the
obstacle-occupied workspace:

######  Assumption 2.

$\forall\mathbf{x}\in\partial\mathcal{W}_{\alpha},$ the intersection
$\mathbf{N}_{\mathcal{W}_{\alpha}}(\mathbf{x})\cap\mathcal{B}_{2\alpha}(\mathbf{x})\subset\mathcal{D}_{\alpha}(\mathcal{O}_{\mathcal{W}}),$
where $\alpha>r_{a}$ such that the set $\mathcal{W}_{\alpha}$, which is
defined according to (15), is not empty.

According to Assumption 2, for any location $\mathbf{x}$ on the boundary of
the $\alpha-$eroded obstacle-free workspace $\mathcal{W}_{\alpha}$, the
intersection between the normal cone to the set $\mathcal{W}_{\alpha}$ at
$\mathbf{x}$ and the Euclidean ball of radius $2\alpha$ centered at
$\mathbf{x}$ always belongs to the $\alpha-$dilated version of the obstacle-
occupied workspace. Observe Fig. 4a for the diagrammatic representation of a
two-dimensional workspace that do not satisfy Assumption 2. The inter-obstacle
arrangement shown in Fig. 4b satisfies Assumption 2.

Unlike [12, Assumprtion 1], [4, Assumprtion 2], and [19, Section V-C3],
Assumption 2 does not impose restrictions on the minimum separation between
any pair of obstacles and allows obstacles to be non-convex. If fact, if one
assumes (as in the above mentioned references) that the obstacles are convex
and the minimum separation between any pair of obstacles is greater than
$2r_{a}$, then Assumption 2 along with Assumption 1 are satisfied, as stated
later in Proposition 44.

Figure 4: Workspace with two obstacle
$\mathcal{O}_{\mathcal{W}}=\mathcal{O}_{i}\cup\mathcal{O}_{j}$ such that
$d(\mathcal{O}_{i},\mathcal{O}_{j})<2\alpha$. Left figure shows an obstacle-
occupied $\mathcal{O}_{\mathcal{W}}$ that does not satisfy Assumption 2. Right
figure shows an obstacle-occupied workspace $\mathcal{O}_{\mathcal{W}}$ that
satisfies Assumption 2.

Next, we show that if the obstacle-occupied workspace
$\mathcal{O}_{\mathcal{W}}$ satisfies Assumptions 1 and 2, then from any
location in the $\alpha-$neighbourhood of the modified obstacle-occupied
workspace $\mathcal{O}_{\mathcal{W}}^{M}$, obtained using (17), the projection
onto this modified obstacle-occupied workspace is always unique.

######  Lemma 3.

Let Assumptions 1 and 2 hold, then, for all locations $\mathbf{x}$ less than
$\alpha$ distance away from the modified obstacle-occupied workspace, there is
a unique closest point from $\mathbf{x}$ to the set
$\mathcal{O}_{\mathcal{W}}^{M}$ i.e.,
$\forall\mathbf{x}\in\mathcal{D}_{\alpha}((\mathcal{O}_{\mathcal{W}}^{M})^{\circ}),\textbf{card}(\mathcal{PJ}(\mathbf{x},\mathcal{O}_{\mathcal{W}}^{M}))=1.$

###### Proof.

See Appendix -D. ∎

Notice that in Fig. 3b, even though initially obstacles were disjoint, the
obstacle-reshaping operator combined them into one pathwise connected modified
obstacle-occupied workspace. In fact, for the obstacle-occupied workspace that
satisfies Assumption 2, if two obstacles are less than $2\alpha$ distance
apart, then the modified obstacle set obtained for the union of these two
obstacles is a connected set. Next, we elaborate on this feature of the
proposed obstacle-reshaping operator.

For each obstacle $\mathcal{O}_{i},i\in\mathbb{I},$ we define the following
set:

$\mathcal{O}_{i,\alpha}=\bigcup_{k\in\mathbb{I}_{i,\alpha}}\bigcup_{j\in\mathbb{I}_{k,\alpha}}\mathcal{O}_{j},$
(20)

where, for $k\in\mathbb{I},$ the set $\mathbb{I}_{k,\alpha}$, which is defined
as

$\mathbb{I}_{k,\alpha}=\\{j\in\mathbb{I}|d(\mathcal{O}_{k},\mathcal{O}_{j})<2\alpha\\},$
(21)

contains the indices corresponding to obstacles that are at distances less
than $2\alpha$ from obstacle $\mathcal{O}_{k}.$ According to (20) and (21),
the distance between any proper subset of the obstacle set
$\mathcal{O}_{i,\alpha}$ and its relative complement with respect to the same
set, is always less than $2\alpha.$ In other words, if
$\mathcal{O}_{\mathbb{C}}\subset\mathcal{O}_{i,\alpha}$ and
$\mathcal{O}_{\mathbb{D}}=\mathcal{O}_{i,\alpha}\setminus\mathcal{O}_{\mathbb{C}},$
then the distance
$d(\mathcal{O}_{\mathbb{C}},\mathcal{O}_{\mathbb{D}})<2\alpha.$ If
$\mathcal{O}_{j}\subset\mathcal{O}_{i,\alpha},j\in\mathbb{I}\setminus\\{i\\}$,
then $\mathcal{O}_{i,\alpha}=\mathcal{O}_{j,\alpha}$. Next, we show that the
modified obstacle-occupied set $\mathcal{O}_{i,\alpha}^{M}$, for any
$i\in\mathbb{I}$, is a connected set.

######  Lemma 4.

Let Assumptions 1 and 2 hold, then the modified obstacle-occupied set
$\mathcal{O}_{i,\alpha}^{M}$, for any $i\in\mathbb{I},$ is a connected set.

###### Proof.

See Appendix -E ∎

According to Lemma 4, if the modified obstacle-occupied workspace contains two
disjoint modified obstacles, then the distance between these two modified
obstacles will always be greater than or equal to $2\alpha.$

######  Remark 3.

When the obstacle is non-convex, the modified obstacle obtained using the
operator $\mathbf{M}$, defined in (17), always occupies less workspace as
opposed to the convex hull [27, Section 2.1.4] of the same obstacle. Although,
one obtains a unique projection onto the convex hull of a given obstacle
within its $\alpha-$neighbourhood, the use of the convex hull renders most of
the obstacle-free workspace unavailable for the robot’s navigation, as shown
in Fig. 5. Moreover, if a given obstacle $\mathcal{O}_{i}$ is convex, then the
modified obstacle $\mathcal{O}_{i}^{M}$ obtained using (17) for any $\alpha>0$
is equal to the original obstacle $\mathcal{O}_{i}$ i.e.,
$\mathcal{O}_{i}^{M}=\mathcal{O}_{i}.$

Since, as per Lemma 3, from any location less than $\alpha$ distance away from
the modified obstacle-occupied workspace $\mathcal{O}_{\mathcal{W}}^{M}$, the
projection on the set $\mathcal{O}_{\mathcal{W}}^{M}$ is unique, one can roll
up an Euclidean ball of radius at most $\alpha$ on the boundary
$\partial\mathcal{O}_{\mathcal{W}}^{M}$, as stated in [30, Definition 11].
This motivates an alternative procedure to obtain the boundary of the modified
obstacle-occupied workspace when the obstacle-occupied workspace
$\mathcal{O}_{\mathcal{W}}$ is two-dimensional, by having a virtual ring of
radius $\alpha$ rolling on the boundary of the set
$\mathcal{O}_{\mathcal{W}}$, as stated in the next remark.

Figure 5: Left figure shows the original obstacle
$\mathcal{O}_{i}\subset\mathbb{R}^{2}$. Middle figure shows the modified
obstacle $\mathcal{O}_{{i}}^{M}=\mathbf{M}(\mathcal{O}_{i},\alpha)$ obtained
using (17). Right figure shows the convex hull $\text{conv}(\mathcal{O}_{i})$
for the obstacle $\mathcal{O}_{i}$.

######  Remark 4.

Given an obstacle-occupied workspace
$\mathcal{O}_{\mathcal{W}}\subset\mathbb{R}^{2}$, satisfying Assumptions 1 and
2, one can construct the modified obstacle
$\mathcal{O}_{i,\alpha}^{M}=\mathbf{M}(\mathcal{O}_{i,\alpha},\alpha)$, where
$i\in\mathbb{I},$ by rotating a virtual ring, of radius $\alpha$ and center
$\mathbf{c}$, around the set $\mathcal{O}_{i,\alpha}$, just touching the set
$\mathcal{O}_{i,\alpha}$, while ensuring that the ring does not intersect with
the interior of that set, as shown in Fig. 7. Then, based on the number of
projections of the location $\mathbf{c}$ on the obstacle set
$\mathcal{O}_{i,\alpha}$ i.e.,
$\mathbf{card}(\mathcal{PJ}(\mathbf{c},\mathcal{O}_{i,\alpha}))$, we construct
the boundary of the modified obstacle set $\partial\mathcal{O}_{i,\alpha}^{M}$
as follows:

  * •

if the ring $\partial\mathcal{B}_{\alpha}(\mathbf{c})$ is touching the set
$\mathcal{O}_{i,\alpha}$ at a single location, then include that location in
the set $\partial\mathcal{O}_{i,\alpha}^{M}$. That is, if
$\mathbf{card}(\mathcal{PJ}(\mathbf{c},\mathcal{O}_{i,\alpha}))=1$, then
$\Pi(\mathbf{c},\mathcal{O}_{i,\alpha})\in\partial\mathcal{O}_{i,\alpha}^{M}$.

  * •

if the ring $\partial\mathcal{B}_{\alpha}(\mathbf{c})$ is simultaneously
touching the set $\mathcal{O}_{i,\alpha}$ at more than one location, then
include in the set $\partial\mathcal{O}_{i,\alpha}^{M}$ the part of the ring
$\partial\mathcal{B}_{\alpha}(\mathbf{c})$ which intersects the conic hull of
the set $\mathcal{PJ}(\mathbf{c},\mathcal{O}_{i,\alpha})$ with its vertex at
$\mathbf{c}$. That is, if
$\mathbf{card}(\mathcal{PJ}(\mathbf{c},\mathcal{O}_{i,\alpha}))>1$, then
$\mathcal{Y}(\mathbf{c})\subset\partial\mathcal{O}_{i,\alpha}^{M}$, where the
set $\mathcal{Y}(\mathbf{c})$ is given by

$\mathcal{Y}(\mathbf{c})=\mathcal{CH}(\mathbf{c},\mathcal{PJ}(\mathbf{c},\mathcal{O}_{i,\alpha}))\cap\partial\mathcal{B}_{\alpha}(\mathbf{c}).$
(22)

We consider the modified obstacle-occupied workspace
$\mathcal{O}_{\mathcal{W}}^{M}\subset\mathcal{W}$ to be the region that the
robot should avoid. The set $\mathcal{V}_{r_{a}}$, defined in (16), represents
the modified obstacle-free workspace for the center of the robot.

We require the set $\mathcal{V}_{r_{a}}$ to be a pathwise connected set.
However, the pathwise connectedness of the set $\mathcal{V}_{r_{a}}$ mainly
depends on the value of the parameter $\alpha.$ For example, see Fig. 6 in
which the set $\mathcal{V}_{r_{a}}$ is not connected due to improper selection
of the parameter $\alpha$. To that end, we require the following lemma:

Figure 6: The left figure shows an original workspace where a feasible path
exists from location $\mathbf{x}$ to the origin. The right figure shows the
modified workspace obtained using (17) with some $\alpha>r_{a}$, where there
is no feasible path from the location $\mathbf{x}$ to the origin.

######  Lemma 5.

Under Assumption 1, there exists $\bar{\alpha}>r_{a}$ such that for all
$\alpha\in(r_{a},\bar{\alpha}]$ the following conditions are satisfied:

  1. 1.

the $\alpha-$eroded obstacle-free workspace $\mathcal{W}_{\alpha}$ is a
pathwise connected set,

  2. 2.

the distance between the origin and the set $\mathcal{W}_{\alpha}$ is less
than ${\alpha}-r_{a}$.

###### Proof.

See Appendix -F. ∎

Next, we show that if we choose the parameter $\alpha$, which is used in (17)
and (16) to obtain the set $\mathcal{V}_{r_{a}}$, as per Lemma 5, then the set
$\mathcal{V}_{r_{a}}$ is pathwise connected and the origin belongs to its
interior.

######  Lemma 6.

If the parameter $\alpha$, which is used in (17), is chosen as per Lemma 5,
then the modified obstacle-free workspace w.r.t. the center of the robot
$\mathcal{V}_{r_{a}}$ is pathwise connected and
$\mathbf{0}\in\mathcal{V}_{r_{a}}^{\circ}.$

###### Proof.

See Appendix -G ∎

This concludes the discussion on the formulation and features of the obstacle-
reshaping operator $\mathbf{M}$ (17), which is applicable to $n-$dimensional
Euclidean subsets of $\mathbb{R}^{n}$. Next, we provide the hybrid control
design for the robot operating in a two-dimensional workspace i.e.,
$\mathcal{W}\subset\mathbb{R}^{2}.$

Figure 7: An obstacle-occupied workspace $\mathcal{O}_{\mathcal{W}}$ with
three obstacles $\mathcal{O}_{i},\mathcal{O}_{j}$ and $\mathcal{O}_{k}$, and
the boundary of the modified obstacle $\mathcal{O}_{i,\alpha}^{M}$ obtained
using a virtual ring with radius $\alpha$, where
$\mathcal{O}_{i,\alpha}=\mathcal{O}_{i}\cup\mathcal{O}_{j}\cup\mathcal{O}_{k}$,
see (20). A video can be seen here https://youtu.be/mylrTOtYOSY.

##  V Hybrid Control for Obstacle Avoidance

In the proposed scheme, similar to [19], depending upon the value of the mode
indicator $m\in\\{-1,0,1\\}=:\mathbb{M},$ the robot operates in two different
modes, namely the move-to-target mode $(m=0)$ when it is away from the
modified obstacles and the obstacle-avoidance mode $(m\in\\{-1,1\\})$ when it
is in the vicinity of an modified obstacle. In the move-to-target mode, the
robot moves straight towards the target, whereas during the obstacle-avoidance
mode the robot moves around the nearest modified obstacle, either in the
clockwise direction $(m=1)$ or in the counter-clockwise direction $(m=-1)$. We
utilize a vector joining the center of the robot and its projection on the
modified obstacle-occupied workspace to select between the modes and assign
the direction of motion while operating in the obstacle-avoidance mode.

###  V-A Hybrid control Design

The proposed hybrid control $\mathbf{u}(\mathbf{x},\mathbf{h},m)$ is given by

$\displaystyle\mathbf{u}(\xi)$
$\displaystyle=-\kappa_{s}(1-m^{2})\mathbf{x}+\kappa_{r}m^{2}\mathbf{v}(\mathbf{x},m),$
(23a) $\displaystyle\underbrace{\begin{matrix}\mathbf{\dot{h}}\\\
\dot{m}\end{matrix}\begin{matrix}[l]=\mathbf{0}\\\
=0\end{matrix}}_{\xi\in\mathcal{F}},\quad\underbrace{\begin{bmatrix}\mathbf{h}^{+}\\\
m^{+}\end{bmatrix}\in\mathbf{L}(\xi)}_{\xi\in\mathcal{J}},$ (23b)

where $\kappa_{s}>0$, $\kappa_{r}>0$ and
$\xi=(\mathbf{x},\mathbf{h},m)\in\mathcal{V}_{r_{a}}\times\mathcal{V}_{r_{a}}\times\mathbb{M}=:\mathcal{K},$
is the composite state vector. In (23a), $\mathbf{x}\in\mathcal{V}_{r_{a}}$ is
the location of the center of the robot. The state
$\mathbf{h}\in\mathcal{V}_{r_{a}}$, referred to as a hit point, is the
location of the center of the robot when it enters in the obstacle-avoidance
mode. The discrete variable $m\in\mathbb{M}$ is the mode indicator. The update
law $\mathbf{L}(\xi)$, used in (23b), which allows the robot to switch between
the modes, is discussed in Section V-C. The symbols $\mathcal{F}$ and
$\mathcal{J}$ denote the flow and jump sets related to different modes of
operations, respectively, whose constructions are provided in Section V-B.
Next, we provide the design of the vector
$\mathbf{v}(\mathbf{x},m)\in\mathbb{R}^{2}$, used in (23a).

The vector $\mathbf{v}(\mathbf{x},m)$ is defined as

$\mathbf{v}(\mathbf{x},m)=\begin{bmatrix}0&m\\\
-m&0\end{bmatrix}\frac{\mathbf{x}-\Pi(\mathbf{x},\mathcal{O}_{\mathcal{W}}^{M})}{\lVert\mathbf{x}-\Pi(\mathbf{x},\mathcal{O}_{\mathcal{W}}^{M})\rVert},$
(24)

where $\Pi(\mathbf{x},\mathcal{O}_{\mathcal{W}}^{M})$ is the point on the
modified obstacle-occupied workspace $\mathcal{O}_{\mathcal{W}}^{M}$ which is
closest to the center of the robot $\mathbf{x}$, as defined in Section II-B.
As per Lemma 3, if the center of the robot $\mathbf{x}$ is inside the
$\alpha-$neighbourhood of the set $\mathcal{O}_{\mathcal{W}}^{M}$, then
$\Pi(\mathbf{x},\mathcal{O}_{\mathcal{W}}^{M})$ is unique. When the robot
operates in the obstacle-avoidance mode, the vector $\mathbf{v}(\mathbf{x},m)$
allows it to move around the nearest obstacle either in the clockwise
direction $(m=1)$ or in the counter-clockwise direction $(m=-1)$. Next, we
discuss the design of the flow set $\mathcal{F}$ and the jump set
$\mathcal{J}$, used in (23).

###  V-B Geometric construction of the flow and jump sets

Figure 8: The left figure shows the partitioning of the region
$\mathcal{N}_{\gamma}(\mathcal{D}_{r_{a}}(\mathcal{O}_{i}^{M}))$ into the
landing region
$\mathcal{R}_{l}=\mathcal{R}_{l,1}\cup\mathcal{R}_{l,2}\cup\mathcal{R}_{l,3}$,
and the exit region
$\mathcal{R}_{e}=\mathcal{R}_{e,1}\cup\mathcal{R}_{e,2}\cup\mathcal{R}_{e,3},$
using (25) and (27). The right figure shows the partitioning of the exit
region into three sub-regions namely the always exit region $\mathcal{R}_{a}$,
the clockwise exit region $\mathcal{R}_{1}$, and the counter-clockwise exit
region $\mathcal{R}_{-1},$ using (28), (30) and (31), respectively.

When the robot operates in the move-to-target mode, in the modified free
workspace, its velocity is directed towards the target location. If any
connected modified obstacle $\mathcal{O}_{i,\alpha}^{M},i\in\mathbb{I}$, is on
the line segment $\mathcal{L}_{s}(\mathbf{x},\mathbf{0})$ connecting the
robot’s location with the target location, then the robot, operating in the
move-to-target mode, will enter the $\alpha-$neighbourhood of that modified
obstacle (i.e., $d(\mathbf{x},\mathcal{O}_{i,\alpha}^{M})\leq\alpha$) from the
landing region $\mathcal{R}_{l}$, as depicted in Fig. 8. The parameter
$\alpha$ is chosen as per Lemma 5. The landing region is defined as

$\mathcal{R}_{l}:=\bigcup_{i\in\mathbb{I}}\mathcal{R}_{l}^{i},$ (25)

where, for each $i\in\mathbb{I}$, the set $\mathcal{R}_{l}^{i}$ is given by

$\displaystyle\mathcal{R}_{l}^{i}:=\\{$
$\displaystyle\mathbf{x}\in\mathcal{N}_{\gamma}(\mathcal{D}_{r_{a}}(\mathcal{O}_{i,\alpha}^{M}))|\mathbf{x}^{\intercal}(\mathbf{x}-\Pi(\mathbf{x},\mathcal{O}_{i,\alpha}^{M}))\geq
0,$ (26)
$\displaystyle\mathcal{L}_{s}(\mathbf{x},\mathbf{0})\cap\left(\mathcal{D}_{r_{a}}(\mathcal{O}_{i,\alpha}^{M})\right)^{\circ}\neq\emptyset\\},$

where $\gamma\in(0,\alpha-r_{a})$. Given a set
$\mathcal{A}\subset\mathbb{R}^{n}$ and a scalar $r>0$, the $r-$neighbourhood
of the set $\mathcal{A}$ is denoted by
$\mathcal{N}_{r}(\mathcal{A})=\mathcal{D}_{r}(\mathcal{A})\setminus(\mathcal{A})^{\circ}.$

Notice that for a connected modified obstacle
$\mathcal{O}_{i,\alpha}^{M},i\in\mathbb{I}$, the landing region
$\mathcal{R}_{l}^{i}$, defined in (26), is the intersection of the following
two regions:

  1. 1.

the region where the line segment $\mathcal{L}_{s}(\mathbf{x},\mathbf{0})$,
which joins the center of the robot and the target location, intersects with
the interior of the $r_{a}-$dilated connected modified obstacle
$\mathcal{D}_{r_{a}}^{\circ}(\mathcal{O}_{i,\alpha}^{M})$. Hence, if the robot
moves straight towards the target in this region, it will eventually collide
with the modified obstacle $\mathcal{O}_{i,\alpha}^{M}.$

  2. 2.

the region where the inner product between the vectors $\mathbf{x}$ and
$\mathbf{x}-\Pi(\mathbf{x},\mathcal{O}_{i,\alpha}^{M})$ is non-negative, as
shown in Fig. 9. Notice that, when the robot moves straight towards the target
in this region, its distance from the modified obstacle
$\mathcal{O}_{i,\alpha}^{M}$ i.e., $d(\mathbf{x},\mathcal{O}_{i,\alpha}^{M})$
does not increase. To understand this fact, observe that if for any
$\mathbf{x}\in\mathcal{N}_{\gamma}(\mathcal{D}_{r_{a}}(\mathcal{O}_{i,\alpha}^{M}))$,
$\mathbf{x}^{\intercal}(\mathbf{x}-\Pi(\mathbf{x},\mathcal{O}_{i,\alpha}^{M}))\geq
0$, then
$-\mathbf{x}\in\mathbf{T}_{\mathcal{D}_{d(\mathbf{x},\mathcal{O}_{i,\alpha}^{M})}(\mathcal{O}_{i,\alpha}^{M})}(\mathbf{x})=\mathcal{P}_{\leq}(\mathbf{0},\mathbf{x}-\Pi(\mathbf{x},\mathcal{O}_{i,\alpha}^{M}))$
i.e., the robot, moving straight towards the target in this region, does not
leave the region
$\mathcal{D}_{d(\mathbf{x},\mathcal{O}_{i,\alpha}^{M})}(\mathcal{O}_{i,\alpha}^{M})$.
The notation
$\mathbf{T}_{\mathcal{D}_{d(\mathbf{x},\mathcal{O}_{i,\alpha}^{M})}(\mathcal{O}_{i,\alpha}^{M})}(\mathbf{x})$
denotes the tangent cone to the set
$\mathcal{D}_{d(\mathbf{x},\mathcal{O}_{i,\alpha}^{M})}(\mathcal{O}_{i,\alpha}^{M})$
at $\mathbf{x}.$

Figure 9:  Partitions of the neighbourhood of the modified obstacle
$\mathcal{O}_{i,\alpha}^{M}$ based on the value of the inner product between
the two vectors $-\mathbf{x}$ and
$\mathbf{x}-\Pi(\mathbf{x},\mathcal{O}_{i,\alpha}^{M})$ and the tangent cone
to the set
$\mathcal{D}_{d(\mathbf{x},\mathcal{O}_{i,\alpha}^{M})}(\mathcal{O}_{i,\alpha}^{M})$
at $\mathbf{x}$. (a) The vector $-\mathbf{x}$ is pointing inside the tangent
cone. (b) The vector $-\mathbf{x}$ is pointing outside the tangent cone.

According to (26), due to the intersection of the above-mentioned two regions,
the landing region $\mathcal{R}_{l}^{i}$ excludes a set of locations from the
region
$\mathcal{N}_{\gamma}(\mathcal{D}_{r_{a}}(\mathcal{O}_{i,\alpha}^{M}))$, for
which the inner product between the vectors $\mathbf{x}$ and
$\mathbf{x}-\Pi(\mathbf{x},\mathcal{O}_{\mathcal{W}}^{M})$ is negative and the
line segment $\mathcal{L}_{s}(\mathbf{x},\mathbf{0})$ intersects with the
interior of the set $\mathcal{D}_{r_{a}}(\mathcal{O}_{i,\alpha}^{M})$, for
example see the regions $\mathcal{R}_{e,1}$ and $\mathcal{R}_{e,2}$ in Fig. 8.
Even though the robot does not have a line-of-sight towards the target
location, as long as it moves straight towards the target in these regions,
its distance from the modified obstacle $\mathcal{O}_{i,\alpha}^{M}$ i.e.,
$d(\mathbf{x},\mathcal{O}_{i,\alpha}^{M})$ increases. To understand this fact,
observe that if for any
$\mathbf{x}\in\mathcal{N}_{\gamma}(\mathcal{D}_{r_{a}}(\mathcal{O}_{i,\alpha}^{M}))$,
$\mathbf{x}^{\intercal}(\mathbf{x}-\Pi(\mathbf{x},\mathcal{O}_{i,\alpha}^{M}))$
is negative, then
$-\mathbf{x}\notin\mathbf{T}_{\mathcal{D}_{d(\mathbf{x},\mathcal{O}_{i,\alpha}^{M})}(\mathcal{O}_{i,\alpha}^{M})}(\mathbf{x})=\mathcal{P}_{\leq}(\mathbf{0},\mathbf{x}-\Pi(\mathbf{x},\mathcal{O}_{i,\alpha}^{M}))$
i.e., the robot, moving straight towards the target in this region, does not
enter the region
$\mathcal{D}_{d(\mathbf{x},\mathcal{O}_{i,\alpha}^{M})}(\mathcal{O}_{i,\alpha}^{M}).$
Due to this property, we include these locations in the region called an exit
region, wherein the robot can operate in the move-to-target mode, as discussed
next.

When the robot operates in the obstacle-avoidance mode in the $\gamma-$
neighbourhood of the modified obstacle-occupied workspace, it will switch to
the move-to-target mode from the exit region, which is defined as follows:

$\mathcal{R}_{e}:=\overline{\mathcal{N}_{\gamma}(\mathcal{D}_{r_{a}}(\mathcal{O}_{\mathcal{W}}^{M}))\setminus\mathcal{R}_{l}}.$
(27)

According to (25), (26) and (27), the exit region is a combination of
following two regions:

  1. 1.

the region where the inner product
$\mathbf{x}^{\intercal}(\mathbf{x}-\Pi(\mathbf{x},\mathcal{O}_{\mathcal{W}}^{M}))$
is non-positive. As discussed earlier, when the robot moves straight towards
the target in this region, its distance from the unsafe region does not
decrease.

  2. 2.

the region where the inner product
$\mathbf{x}^{\intercal}(\mathbf{x}-\Pi(\mathbf{x},\mathcal{O}_{\mathcal{W}}^{M}))$
is positive and the line segment $\mathcal{L}_{s}(\mathbf{x},\mathbf{0})$,
which joins the robot’s location and the target location, does not intersect
with the nearest modified obstacle. Hence, the robot can move straight towards
the target and safely leave the $\alpha-$neighbourhood of this connected
modified obstacle.

As shown in Fig. 8 (left), for a modified non-convex obstacle
$\mathcal{O}_{i,\alpha}^{M},i\in\mathbb{I}$, the exit region is not a
connected set. Consider a situation, wherein the robot is moving in the
clockwise direction with respect to the set $\mathcal{O}_{i,\alpha}^{M}$ in
the landing region $\mathcal{R}_{l,1}$. If the robot were to start moving
straight towards the target after entering the exit region
$\mathcal{R}_{e,1}$, it will re-enter the region $\mathcal{R}_{l,1}$,
resulting in multiple simultaneous switching instances. Similar situation can
occur for the robot moving in the counter-clockwise direction with respect to
the set $\mathcal{O}_{i,\alpha}^{M}$ in the landing region
$\mathcal{R}_{l,2}$, if it moves straight towards the target after entering
the exit region $\mathcal{R}_{e,2}.$ On the other hand, if the robot enters in
the region $\mathcal{R}_{e,3}$, then, irrespective of the direction of motion
around the obstacle, it can safely move straight towards the target and leave
the $\gamma-$neighbourhood of the modified obstacle
$\mathcal{O}_{i,\alpha}^{M}.$

Hence, as shown in Fig. 8 (right), based on the angle between the vectors
$\mathbf{x}$ and $\mathbf{x}-\Pi(\mathbf{x},\mathcal{O}_{\mathcal{W}}^{M})$,
and the presence of a line-of-sight to the target location with respect to the
nearest disjoint modified obstacle, we divide the exit region
$\mathcal{R}_{e}$ into three sub-regions $\mathcal{R}_{a}$, $\mathcal{R}_{1}$
and $\mathcal{R}_{-1}$, referred to as the always exit region, the clockwise
exit region and the counter-clockwise exit region, respectively, as follows:

The always exit region $\mathcal{R}_{a}$ is defined as

$\mathcal{R}_{a}:=\bigcup_{i\in\mathbb{I}}\mathcal{R}_{a}^{i},$ (28)

where, for each $i\in\mathbb{I}$, the set $\mathcal{R}_{a}^{i}$, which is
given by

$\mathcal{R}_{a}^{i}:=\\{\mathbf{x}\in\mathcal{R}_{e}|\mathcal{L}_{s}(\mathbf{x},\mathbf{0})\cap\left(\mathcal{D}_{r_{a}}(\mathcal{O}_{i,\alpha}^{M})\right)^{\circ}=\emptyset\\},$
(29)

contains the locations from the exit region $\mathcal{R}_{e}$ such that the
line segments joining them to the origin do not intersect with the interior of
the $r_{a}-$dilated modified obstacle
$\mathcal{D}_{r_{a}}(\mathcal{O}_{i,\alpha}^{M}).$

The clockwise exit region $\mathcal{R}_{1}$ is defined as

$\mathcal{R}_{1}:=\left\\{\mathbf{x}\in\mathcal{R}_{e}\setminus\mathcal{R}_{a}|\measuredangle\left(\mathbf{x},\mathbf{x}-\Pi(\mathbf{x},\mathcal{O}_{\mathcal{W}}^{M})\right)\in\left[\pi,2\pi\right]\right\\},$
(30)

and the counter-clockwise exit region $\mathcal{R}_{-1}$ is defined as

$\mathcal{R}_{-1}:=\left\\{\mathbf{x}\in\mathcal{R}_{e}\setminus\mathcal{R}_{a}|\measuredangle\left(\mathbf{x},\mathbf{x}-\Pi(\mathbf{x},\mathcal{O}_{\mathcal{W}}^{M})\right)\in\left[0,\pi\right]\right\\}$
(31)

where, given two vectors $\mathbf{p},\mathbf{q}\in\mathbb{R}^{2},$ the
notation $\measuredangle(\mathbf{p},\mathbf{q})$ indicates the angle measured
from $\mathbf{p}$ to $\mathbf{q}$. The angle measured in the counter-clockwise
direction is considered positive, and vice versa.

While moving in the clockwise direction around the modified obstacle, the
robot is allowed to move straight towards the target only if its center is in
the region $\mathcal{R}_{1}\cup\mathcal{R}_{a}$. Whereas, the robot moving in
the counter-clockwise direction around the modified obstacle should move
straight towards the target only if its center is in the region
$\mathcal{R}_{-1}\cup\mathcal{R}_{a}$. Next, we provide the geometric
constructions of the flow set $\mathcal{F}$ and the jump set $\mathcal{J}$,
used in (23).

####  V-B1 Flow and jump sets (move-to-target mode)

As discussed earlier, if the robot, which is moving straight towards the
target, is on a collision path towards a connected modified obstacle
$\mathcal{O}_{i,\alpha}^{M}$, for some $i\in\mathbb{I}$, then it will enter
the $\gamma-$neighbourhood of this modified obstacle through the landing
region. Hence, the jump set of the move-to-target mode for the state
$\mathbf{x}$ is defined as

$\mathcal{J}_{0}^{\mathcal{W}}:=\mathcal{N}_{\gamma_{s}}(\mathcal{D}_{r_{a}}(\mathcal{O}_{\mathcal{W}}^{M}))\cap\mathcal{R}_{l},$
(32)

where $\gamma_{s}\in[0,\gamma)$. For robustness purposes (with respect to
noise), we introduce a hysteresis region by allowing the robot, operating in
the move-to-target mode inside the $\gamma-$neighbourhood of the set
$\mathcal{O}_{\mathcal{W}}^{M}$, to move closer to the set
$\mathcal{O}_{\mathcal{W}}^{M}$ before switching to the obstacle-avoidance
mode.

The flow set of the move-to-target mode for the state $\mathbf{x}$ is then
defined as

$\mathcal{F}_{0}^{\mathcal{W}}:=\left(\mathcal{W}\setminus\left(\mathcal{D}_{r_{a}+\gamma_{s}}(\mathcal{O}_{\mathcal{W}}^{M})\right)^{\circ}\right)\cup\mathcal{R}_{e}.$
(33)

Notice that the union of the jump set (32) and the flow set (33) exactly
covers the modified robot-centred obstacle-free workspace
$\mathcal{V}_{r_{a}}$ (16). Refer to Fig. 11 for the representation of the
flow and jump sets related to the obstacle-occupied workspace
$\mathcal{O}_{\mathcal{W}}^{M}$. Next, we provide the construction of the flow
and jump sets for the obstacle-avoidance mode.

####  V-B2 Flow and jump sets (obstacle-avoidance mode)

The robot operates in the obstacle-avoidance mode only in the
$\gamma-$neighbourhood of the modified obstacle-occupied workspace
$\mathcal{O}_{\mathcal{W}}^{M}.$ The mode indicator variable $m=1$ and $m=-1$
prompts the robot to move either in the clockwise direction or in the counter-
clockwise direction with respect to the nearest boundary of the set
$\mathcal{O}_{\mathcal{W}}^{M}$, respectively. As discussed earlier, for some
$m\in\\{-1,1\\},$ the robot should exit the obstacle-avoidance mode and switch
to the move-to-target mode only if its center belongs to the exit region
$\mathcal{R}_{m}\cup\mathcal{R}_{a}$.

To that end, we make use of the hit point $\mathbf{h}$ (i.e., the location of
the center of the robot when it switched from the move-to-target mode to the
current obstacle-avoidance mode) to define the jump set of the obstacle-
avoidance mode $\mathcal{J}_{m}^{\mathcal{W}}$ for the state $\mathbf{x}$ as
follows:

$\mathcal{J}_{m}^{\mathcal{W}}:=\left(\mathcal{W}\setminus(\mathcal{D}_{r_{a}+\gamma}(\mathcal{O}_{\mathcal{W}}^{M}))^{\circ}\right)\cup\mathcal{ER}_{m}^{\mathbf{h}},$
(34)

where $m\in\\{-1,1\\}$.

For some $m\in\\{-1,1\\}$ and the hit point
$\mathbf{h}\in\mathcal{V}_{r_{a}}$, the set $\mathcal{ER}_{m}^{\mathbf{h}}$ is
given by

$\mathcal{ER}_{m}^{\mathbf{h}}:=\\{\mathbf{x}\in\overline{\mathcal{R}_{m}\cup\mathcal{R}_{a}}\big{|}\lVert\mathbf{h}\rVert-\lVert\mathbf{x}\rVert\geq\epsilon\\},$
(35)

where $\epsilon\in(0,\bar{\epsilon}]$, with $\bar{\epsilon}>0$. This set
contains the locations from the exit region
$\mathcal{R}_{m}\cup\mathcal{R}_{a}$ which are at least $\epsilon$ units
closer to the target location than the current hit point.

Figure 10:  Effects of $\epsilon$, used in (35), on the construction of the
sets $\mathcal{ER}_{m}^{\mathbf{h}}$, for $m\in\\{-1,1\\}$ and a hit point
$\mathbf{h}\in\mathcal{J}_{0}^{\mathcal{W}}.$ The left figure shows that when
$\epsilon=\epsilon_{1}$, the sets
$\mathcal{ER}_{m}^{\mathbf{h}},m\in\\{-1,1\\},$ are non-empty. The right
figure shows that when $\epsilon=\epsilon_{2}$, the sets
$\mathcal{ER}_{m}^{\mathbf{h}},m\in\\{-1,1\\},$ are empty. Figure 11:  Flow
and jump sets $\mathcal{F}_{m}^{\mathcal{W}}$,
$\mathcal{J}_{m}^{\mathcal{W}}$, related to the set $\mathcal{O}_{i,\alpha}$
shown in Fig. 8. The left figure $(m=0)$ illustrates the case where the robot
operates in the move-to-target mode and moves straight toward the target
location. The middle figure $(m=1)$ illustrates the case where the robot,
operating in the obstacle-avoidance mode, moves in the clockwise direction
with respect to $\partial\mathcal{O}_{i,\alpha}^{M}.$ The right figure
$(m=-1)$ illustrates the case where the robot, operating in the obstacle-
avoidance mode, moves in the counter-clockwise direction with respect to
$\partial\mathcal{O}_{i,\alpha}^{M}.$

Since, according to Lemma 6, the target location belongs to the interior of
the modified obstacle-free workspace w.r.t. the center of the robot i.e.,
$\mathbf{0}\in(\mathcal{V}_{r_{a}})^{\circ}$, the existence of a positive
scalar $\bar{\epsilon}$ can be guaranteed. However, if one selects a very high
value for $\epsilon$, then for some connected modified obstacles
$\mathcal{O}_{i,\alpha}^{M},i\in\mathbb{I}$, the set
$\mathcal{ER}_{m}^{\mathbf{h}}\cap\mathcal{N}_{\gamma}(\mathcal{D}_{r_{a}}(\mathcal{O}_{i,\alpha}^{M}))$
will become empty, as shown in Fig. 10, and the robot might get stuck
(indefinitely) in the obstacle-avoidance mode in the vicinity of those
modified obstacles. Therefore, in the next lemma, we provide an upper bound on
the value of $\bar{\epsilon}$.

######  Lemma 7.

Under Assumptions 1 and 2, we consider a connected modified obstacle
$\mathcal{O}_{i,\alpha}^{M},i\in\mathbb{I}$. If
$\bar{\epsilon}\in(0,\epsilon_{h}]$, where

$\epsilon_{h}=\sqrt{\left(d(\mathbf{0},\mathcal{O}_{\mathcal{W}}^{M})^{2}-r_{a}^{2}\right)}-\left(d(\mathbf{0},\mathcal{O}_{\mathcal{W}}^{M})-r_{a}\right),$
(36)

then, for every $\mathbf{h}\in\mathcal{J}_{0}^{\mathcal{W}}$ with
$d(\mathbf{h},\mathcal{O}_{i,\alpha}^{M})=\beta\in[r_{a},r_{a}+\gamma]$, and
any location
$\mathbf{p}\in\mathcal{PJ}(\mathbf{0},\partial\mathcal{D}_{\beta}(\mathcal{O}_{i,\alpha}^{M}))$,
the set
$\mathcal{H}_{\mathbf{p}}:=\mathcal{B}_{\delta}(\mathbf{p})\cap\mathcal{N}_{\gamma}(\mathcal{D}_{r_{a}}(\mathcal{O}_{i,\alpha}^{M}))\subset\mathcal{ER}_{m}^{\mathbf{h}},$
for some $m\in\\{-1,1\\}$ and $\delta=\min\\{\beta-
r_{a},d(\mathbf{0},\mathcal{O}_{\mathcal{W}}^{M})-r_{a}\\}$, where the set
$\mathcal{ER}_{m}^{\mathbf{h}}$ is defined in (35).

###### Proof.

See Appendix -H. ∎

According to Lemma 36, if the hit point belongs to the jump set of the move-
to-target mode associated with a connected modified obstacle
$\mathcal{O}_{i,\alpha}^{M}$ and $\epsilon\in(0,\bar{\epsilon}]$, where
$\bar{\epsilon}$ is chosen as per Lemma 36, then the set
$\mathcal{ER}_{m}^{\mathbf{h}}\cap\mathcal{N}_{\gamma}(\mathcal{D}_{r_{a}}(\mathcal{O}_{i,\alpha}^{M}))$
is non-empty. Hence, we initialize the robot in the move-to-target mode so
that the hit point will always belong to the jump set of the move-to-target
mode, as stated later in Theorem 1.

According to (34) and (35), while operating in the obstacle-avoidance mode
with some $m\in\\{-1,1\\}$, the robot can switch to the move-to-target mode
only when its center belongs to the exit region
$\mathcal{R}_{m}\cup\mathcal{R}_{a}$ and is at least $\epsilon$ units closer
to the target than the current hit point $\mathbf{h}.$ This creates a
hysteresis region and ensures Zeno-free switching between the modes. This
switching strategy is inspired by [31], which allows us to establish
convergence properties of the target location, as discussed later in Theorem
1.

We then define the flow set of the obstacle-avoidance mode
$\mathcal{F}_{m}^{\mathcal{W}}$ for the state $\mathbf{x}$ as follows:

$\mathcal{F}_{m}^{\mathcal{W}}:=\mathcal{R}_{l}\cup\overline{\mathcal{R}_{-m}}\cup\overline{\mathcal{R}_{m}\cup\mathcal{R}_{a}\setminus\mathcal{ER}_{m}^{\mathbf{h}}},$
(37)

where $m\in\\{-1,1\\}$. Notice that the union of the jump set (34) and the
flow set (37) exactly covers the modified robot-centred free workspace
$\mathcal{V}_{r_{a}}$ (16). Refer to Fig. 11 for the representation of the
flow and jump sets related to the modified obstacle-occupied workspace
$\mathcal{O}_{\mathcal{W}}^{M}$.

Finally, the flow set $\mathcal{F}$ and the jump set $\mathcal{J}$, used in
(23), are defined as

$\mathcal{F}:=\bigcup_{m\in\mathbb{M}}\mathcal{F}_{m},\quad\mathcal{J}:=\bigcup_{m\in\mathbb{M}}\mathcal{J}_{m},$
(38)

where for $m\in\mathbb{M},$ the sets $\mathcal{F}_{m}$ and $\mathcal{J}_{m}$
are given by

$\mathcal{F}_{m}:=\mathcal{F}_{m}^{\mathcal{W}}\times\mathcal{V}_{r_{a}}\times\\{m\\},\quad\mathcal{J}_{m}:=\mathcal{J}_{m}^{\mathcal{W}}\times\mathcal{V}_{r_{a}}\times\\{m\\},$
(39)

with $\mathcal{F}_{m}^{\mathcal{W}},\mathcal{J}_{m}^{\mathcal{W}}$ defined in
(33), (32) for $m=0$ and in (37), (34) for $m\in\\{-1,1\\}.$

Figure 12:  The figures show two possible paths that the robot, initialized at
$\mathbf{x}_{0}$, takes before converging to the origin. The left figure
illustrates a case in which the robot, operating in the obstacle-avoidance
mode, moves initially in the clockwise direction from $\mathbf{h}_{1}$ to
$\mathbf{l}_{1}$, and then in the counter-clockwise direction from
$\mathbf{h}_{2}$ to $\mathbf{l}_{2}$ with respect to the nearest point on the
modified obstacle $\mathcal{O}_{i,\alpha}^{M}$. The right figure illustrates a
case in which the robot, operating in the obstacle-avoidance mode, moves in
the clockwise direction with respect to the nearest point on the modified
obstacle $\mathcal{O}_{i,\alpha}^{M}$.

######  Remark 5.

Let us look at the case where the robot is moving in the
$\gamma-$neighbourhood of a connected modified obstacle
$\mathcal{O}_{i,\alpha}^{M}$, for some $i\in\mathbb{I}$. If the robot needs to
switch between the modes of operation multiple times before leaving the
$\gamma-$neighbourhood of the modified obstacle $\mathcal{O}_{i,\alpha}^{M}$,
then it should move in the same direction in the obstacle-avoidance mode i.e.,
either in the clockwise direction or in the counter-clockwise direction, to
avoid retracing the previously travelled path, as shown in Fig. 12b. In fact,
if the robot does not maintain the same direction of motion in the obstacle-
avoidance mode, while operating in the $\gamma-$neighbourhood of the connected
modified obstacle $\mathcal{O}_{i,\alpha}^{M}$, then it will retraces the
previously travelled path, as shown in Fig. 12a.

Next, we provide the update law $\mathbf{L}(\mathbf{x},\mathbf{h},m)$, used in
(23b).

###  V-C Update law $\mathbf{L}(\mathbf{x},\mathbf{h},m)$

The update law $\mathbf{L}(\xi)$, used in (23b), updates the value of the hit
point $\mathbf{h}$ and the mode indicator $m$ when the state
$(\mathbf{x},\mathbf{h},m)$ belongs to the jump set $\mathcal{J}$, which is
defined in Section V-B. When the robot, operating in the move-to-target mode,
enters in the jump set $\mathcal{J}_{0}$, defined in (32) and (39), the update
law $\mathbf{L}(\mathbf{x},\mathbf{h},0)$ is given as

$\mathbf{L}(\mathbf{x},\mathbf{h},0)=\left\\{\begin{bmatrix}\mathbf{x}\\\
z\end{bmatrix}\in\mathcal{V}_{r_{a}}\times\\{-1,1\\}\bigg{|}\xi\in\mathcal{J}_{0}\right\\}.$
(40)

Notice that, when the robot switches from the move-to-target mode to the
obstacle-avoidance mode, the coordinates of the hit point gets updated to the
current value of $\mathbf{x}$.

On the other hand, when the robot operating in the obstacle-avoidance mode,
enters in the jump set $\mathcal{J}_{m},m\in\\{-1,1\\}$, defined in (34) and
(39), the update law $\mathbf{L}(\mathbf{x},\mathbf{h},m),m\in\\{-1,1\\}$, is
given by

$\mathbf{L}(\mathbf{x},\mathbf{h},m)=\left\\{\begin{bmatrix}\mathbf{h}\\\
0\end{bmatrix}\bigg{|}\xi\in\mathcal{J}_{m},m\in\\{-1,1\\}\right\\}.$ (41)

When the robot switches from the obstacle-avoidance mode to the move-to-target
mode, the value of the hit point remains unchanged. This concludes the design
of the proposed hybrid feedback controller (23).

##  VI Stability Analysis

The hybrid closed-loop system resulting from the hybrid control law (23) is
given by

$\underbrace{\begin{matrix}\mathbf{\dot{x}}\\\ \mathbf{\dot{h}}\\\
\dot{m}\end{matrix}\begin{matrix}[l]=\mathbf{u}(\xi)\\\ =\mathbf{0}\\\
=0\end{matrix}}_{\dot{\xi}=\mathbf{F}(\xi)},{\xi\in\mathcal{F}},\quad\underbrace{\begin{matrix}\mathbf{x}^{+}\\\
\begin{bmatrix}\mathbf{h}^{+}\\\
m^{+}\end{bmatrix}\end{matrix}\begin{matrix}[l]=\mathbf{x}\vspace{0.16cm}\\\
\vspace{0.3cm}\in\mathbf{L}(\xi)\end{matrix}}_{\xi^{+}\in\mathbf{J}(\xi)},{\xi\in\mathcal{J}},$
(42)

where $\mathbf{u}(\xi)$ is defined in (23a), and the update law
$\mathbf{L}(\xi)$ is provided in (40), (41). The definitions of the flow set
$\mathcal{F}$ and the jump set $\mathcal{J}$ are provided in (38), (39). Next,
we analyze the hybrid closed-loop system (42) in terms of the forward
invariance of the obstacle-free state space
$\mathcal{K}:=\mathcal{V}_{r_{a}}\times\mathcal{V}_{r_{a}}\times\mathbb{M}$
along with the stability properties of the target set $\mathcal{A}$, which is
defined as

$\mathcal{A}:=\\{\mathbf{0}\\}\times\mathcal{V}_{r_{a}}\times\mathbb{M}.$ (43)

First, we analyze the forward invariance of the modified obstacle-free
workspace, which then will be followed by the convergence analysis.

For safe autonomous navigation, the state $\mathbf{x}$ must always evolve
within the set $\mathcal{V}_{r_{a}}$ (16). This is equivalent to having the
set
$\mathcal{K}:=\mathcal{V}_{r_{a}}\times\mathcal{V}_{r_{a}}\times\mathbb{M}$
forward invariant for the hybrid closed-loop system (42). This is stated in
the next Lemma.

######  Lemma 8.

Under Assumptions 1 and 2, for the hybrid closed-loop system (42), the
obstacle-free set
$\mathcal{K}:=\mathcal{V}_{r_{a}}\times\mathcal{V}_{r_{a}}\times\mathbb{M}$ is
forward invariant.

###### Proof.

See Appendix -I. ∎

Next, we show that if the robot is initialized in the move-to-target mode, at
any location in $\mathcal{V}_{r_{a}}$ and the parameter $\bar{\epsilon}$, used
in (35), is chosen as per Lemma 36, then it will safely and asymptotically
converge to the target location at the origin.

######  Theorem 1.

Consider the hybrid closed-loop system (42) and let Assumption 1 holds true.
Also, let Assumption 2 hold true for the parameter $\alpha$ chosen as per
Lemma 5. If $m(0,0)=0$ and $\bar{\epsilon}$, used in (35), is chosen as per
Lemma 36, then

  * i)

the obstacle-free set $\mathcal{K}$ is forward invariant,

  * ii)

$\mathbf{x}=\mathbf{0}$ is globally asymptotically stable in the modified
obstacle-free workspace w.r.t. the center of the robot $\mathcal{V}_{r_{a}},$

  * iii)

the number of jumps is finite.

###### Proof.

See Appendix -J. ∎

According to Theorem 1, we initialize the robot in the move-to-target mode to
ensure that when it switches to the obstacle-avoidance mode, the hit point
$\mathbf{h}$ belongs to the set $\mathcal{J}_{0}^{\mathcal{W}}.$ This allows
us to establish an upper bound on the value of the parameter $\bar{\epsilon}$
as given in Lemma 36, which is crucial to ensure that the robot, when
operating in the obstacle-avoidance mode, will certainly enter in the move-to-
target mode.

######  Remark 6.

Theorem 1 guarantees global asymptotic stability of the target location in the
modified set $\mathcal{V}_{r_{a}}$ and not in the original set
$\mathcal{W}_{r_{a}}$. Since the obstacle reshaping operator $\mathbf{M}$ is
extensive [29, Table 1] i.e.,
$\mathcal{O}_{\mathcal{W}}\subseteq\mathcal{O}_{\mathcal{W}}^{M}$, the set
$\mathcal{V}_{r_{a}}$ is a subset of the set $\mathcal{W}_{r_{a}}$ i.e.,
$\mathcal{V}_{r_{a}}\subseteq\mathcal{W}_{r_{a}}.$ Interestingly, if one
chooses the value of the parameter $\alpha$ close to $r_{a}$, then the region
occupied by the set $\mathcal{V}_{r_{a}}$ approaches the original set
$\mathcal{W}_{r_{a}}$. In other words, if $\mathcal{V}_{r_{a}}^{1}$ and
$\mathcal{V}_{r_{a}}^{2}$ are two modified obstacle-free workspaces obtained
for two different values of the parameter $\alpha_{1}$ and $\alpha_{2}$,
respectively, using (17) and (16), where
$\alpha_{1},\alpha_{2}\in(r_{a},\bar{\alpha}]$, $\alpha_{1}>\alpha_{2}$ and
$\bar{\alpha}$ defined as per Lemma 5, then the set
$\mathcal{V}_{r_{a}}^{1}\subseteq\mathcal{V}_{r_{a}}^{2}\subseteq\mathcal{W}_{r_{a}}$.
Hence, by selecting a smaller value of the parameter $\alpha$ one can
implement the proposed hybrid feedback controller (23) in a larger area.

Unlike [12, Assumprtion 1], [4, Assumprtion 2], and [19, Section V-C3],
Assumptions 1 and 2 do not impose restrictions on the minimum separation
between any pair of obstacles and allow obstacles to be non-convex. In
particular, Assumptions 1 and 2 are satisfied in the case of environments with
convex obstacles where the minimum separation between any pair of obstacles is
greater than $2r_{a}$, as discussed next.

######  Proposition 1.

Let the workspace $\mathcal{W}$ be a compact, convex subset of
$\mathbb{R}^{2}$. Let the obstacles
$\mathcal{O}_{i},i\in\mathbb{I}\setminus\\{0\\}$, be compact and convex, such
that $d(\mathcal{O}_{i},\mathcal{O}_{j})>2r_{a},\forall i,j\in\mathbb{I},i\neq
j$, and $\mathbf{0}\in\mathcal{W}_{r_{a}}^{\circ}$. Then Assumptions 1 and 2
hold true for all $\alpha\in(r_{a},\bar{\alpha}]$, where the parameter
$\bar{\alpha}$ is defined as

$\bar{\alpha}=\underset{i,j\in\mathbb{I},i\neq
j}{\min}d(\mathcal{O}_{i},\mathcal{O}_{j})/2.$ (44)

###### Proof.

See Appendix -L. ∎

The workspace that satisfies the conditions (commonly used in the literature)
in Proposition 44, also satisfies Assumptions 1 and 2. Notice that, since the
internal obstacles are convex, if one chooses $\alpha\in(0,\bar{\alpha}]$,
which is used in (17), where $\bar{\alpha}$ is defined in (44), then the
shapes of the internal convex obstacles remains unchanged in the modified
obstacle-occupied workspace. Hence, for any $\alpha\in(r_{a},\bar{\alpha}]$,
the set of locations that do not belong to the modified set
$\mathcal{V}_{r_{a}}$ always belongs inside the $\alpha-$neighbourhood of the
workspace obstacle $\mathcal{O}_{0}$ i.e., the set
$\mathcal{W}_{r_{a}}\setminus\mathcal{V}_{r_{a}}\subset\mathcal{D}_{\alpha}(\mathcal{O}_{0}).$

However, as the workspace is convex, if the robot is initialized in the move-
to-target mode, in the set $\mathcal{W}_{r_{a}}\setminus\mathcal{V}_{r_{a}}$,
it will initially move straight towards the target and enter the set
$\mathcal{V}_{r_{a}}$. Then, according to Lemma 8, the robot will continue to
move inside the set $\mathcal{V}_{r_{a}}$ and according to Theorem 1, will
asymptotically converge to the target location.

Next, we provide procedural steps to implement the proposed hybrid feedback
controller (23) for safe autonomous navigation in a priori known and a priori
unknown environments.

##  VII Sensor-based Implementation Procedure

We choose the origin as the target location. We initialize the center of the
robot in the interior of the set $\mathcal{W}_{r_{a}}$ and assume that the
value of parameter $\alpha$, defined in Lemma 5, is a priori known. The robot
is initialized in the move-to-target mode i.e., $m(0,0)=0$, as stated in
Theorem 1, and the hit point is initialized at the initial location of the
robot. We choose $\epsilon\in(0,\bar{\epsilon}],$ where $\bar{\epsilon}$ is
selected as per Lemma 36. The obstacles can have arbitrary shapes and can be
in close proximity with each other as long as Assumptions 1 and 2 are
satisfied.

Notice that the robot can have multiple closest points in the proximity of the
non-convex obstacles. This restrains it from implementing the rotational
control vector $\mathbf{v}(\mathbf{x},m)$, defined in (24), which is essential
for the safe motion in the obstacle-avoidance mode, as it requires a unique
closest point.

In the case where the obstacle-occupied workspace $\mathcal{O}_{\mathcal{W}}$
is a priori known, one can construct the modified obstacle-occupied workspace
$\mathcal{O}_{\mathcal{W}}^{M}$ in advance, using (17) and Remark 2. This
guarantees the uniqueness of the projection of the center of the robot onto
the unsafe region, inside its $\alpha-$neighbourhood, as stated Lemma 3.
Hence, the flow and jump sets, defined in (38), can be constructed before
initiating the motion. Then according to Theorem 1, the robot, with its center
initialized in the modified obstacle-free workspace, will converge to the
target location using the proposed hybrid feedback control law (23).

On the other hand, in an unknown environment, the modified obstacle-occupied
workspace cannot be obtained in advance. Therefore, motivated by the method
described in Remark 4, a virtual ring
$\partial\mathcal{B}_{v_{r}}(\mathbf{c})$ is constructed whenever the robot
enters the obstacle-avoidance mode, as described in Section VII-A. One should
ensure that the robot’s body is always enclosed by the ring, that the ring
does not intersect with the interior of the obstacle-occupied workspace, and
that the ring moves along with the robot in the obstacle-avoidance mode. Using
this ring, the robot can then anticipate the possibility of multiple
projections of its center onto the obstacle-occupied workspace and locally
modify the obstacle-occupied workspace to ensure that the projection of its
center onto the modified workspace is always unique, as discussed later in
Section VII-B.

Note that if the robot is initialized on the boundary of the obstacle-occupied
workspace such that its center has multiple closest points on the obstacle-
occupied workspace, then one cannot construct a virtual ring with a radius
greater than $r_{a}$ that not only encloses the robot’s body but also does not
intersect with the interior of the obstacle-occupied workspace. Consequently,
one should initialize the robot in the interior of the obstacle-free
workspace.

For safe navigation in a priori unknown environments, we assume that the robot
is equipped with a range-bearing sensor with angular scanning range of
$360^{\circ}$ and sensing radius $R_{s}>2\alpha.$ Similar to [22] and [9], the
range-bearing sensor is modeled using a polar curve
$r_{g}(\mathbf{x},\theta):\mathcal{W}_{r_{a}}\times[-\pi,\pi]\to[0,R_{s}],$
which is defined as

$r_{g}(\mathbf{x},\theta)=\min\left\\{R_{s},\underset{\begin{matrix}\mathbf{y}\in\partial\mathcal{O}_{\mathcal{W}}\\\
\text{atan2v}(\mathbf{y}-\mathbf{x})=\theta\end{matrix}}{\min}{\lVert\mathbf{x}-\mathbf{y}\rVert}\right\\}.$
(45)

where $\text{atan2v}(\mathbf{q})=\text{
atan2}(q_{2},q_{1}),\mathbf{q}=[q_{1},q_{2}]^{\intercal}$. The notation
$r_{g}(\mathbf{x},\theta)$ represents the distance between the center of the
robot $\mathbf{x}$ and the boundary of the unsafe region
$\partial\mathcal{O}_{\mathcal{W}}$, measured by the sensor, in the direction
defined by the angle $\theta.$ Given the location $\mathbf{x},$ along with the
bearing angle $\theta$, the mapping
$\lambda(\mathbf{x},\theta):\mathcal{W}_{r_{a}}\times[-\pi,\pi]\to\mathcal{W}_{0},$
which is given by

$\lambda(\mathbf{x},\theta)=\mathbf{x}+r_{g}(\mathbf{x},\theta)[\cos(\theta),\sin(\theta)]^{\intercal},$
(46)

evaluates the Cartesian coordinates of the detected point.

Using (45) and (46), the distance between the center of the robot
$\mathbf{x}\in\mathcal{W}_{r_{a}}$ and the unsafe region
$\mathcal{O}_{\mathcal{W}}$ i.e., $d(\mathbf{x},\mathcal{O}_{\mathcal{W}})$ is
calculated as follows:

$d(\mathbf{x},\mathcal{O}_{\mathcal{W}})=r_{g}(\mathbf{x},\theta),$ (47)

where $\theta\in\Theta$. The set $\Theta$, which is defined as

$\Theta=\left\\{\theta_{p}\in[-\pi,\pi]\bigg{|}\theta_{p}=\underset{\theta\in[-\pi,\pi]}{\text{arg
min }}r_{g}(\mathbf{x},\theta)\right\\},$ (48)

contains bearing angles such that the range measurement (45) in the directions
defined by these bearing angles gives the smallest value when compared to the
values obtained in any other directions. Then, the set of projections of the
location $\mathbf{x}$ onto the unsafe regions i.e.,
$\mathcal{PJ}(\mathbf{x},\mathcal{O}_{\mathcal{W}})$ is given by

$\mathcal{PJ}(\mathbf{x},\mathcal{O}_{\mathcal{W}})=\left\\{\lambda(\mathbf{x},\theta)|\forall\theta\in\Theta\right\\}.$
(49)

For a given location of the robot $\mathbf{x}$, the set $\partial\mathcal{O}$,
which is defined as

$\partial\mathcal{O}=\\{\lambda(\mathbf{x},\theta),\theta\in[-\pi,\pi]|r_{g}(\mathbf{x},\theta)<R_{s}\\},$
(50)

contains the locations in the sensing region that belong to the boundary of
the unsafe region. The robot moving straight towards the target will collide
with the obstacle-occupied workspace if the following condition holds true:

$\partial\mathcal{O}\cap\square(\mathbf{x},\mathbf{0})\neq\emptyset,$ (51)

where the notation $\square(\mathbf{x},\mathbf{0})$ represents a rectangle, as
shown in Fig. 13, with its vertices located at
$\mathbf{x}_{1},\mathbf{x}_{-1},\mathbf{0}_{1}$ and $\mathbf{0}_{-1}$, which
are evaluated as

$\displaystyle\begin{bmatrix}\mathbf{x}_{z}\\\
\mathbf{0}_{z}\end{bmatrix}=\begin{bmatrix}\mathbf{x}\\\
\mathbf{0}\end{bmatrix}+zr_{a}\begin{bmatrix}\mathbf{I}\\\
\mathbf{I}\end{bmatrix}\begin{bmatrix}\cos\theta_{d}\\\
\sin\theta_{d}\end{bmatrix},z\in\\{-1,1\\},$ (52)

where $\mathbf{I}$ is a $2\times 2$ identity matrix, and
$\theta_{d}=\pi/2+\text{atan2v}(\mathbf{x})$ The robot moving in the move-to-
target mode can infer the possibility of a collision with the unsafe region by
verifying the condition in (51). Next, we provide a procedure, summarized in
Algorithm 2, which allows robot to identify whether the state
$(\mathbf{x},\mathbf{h},m)$ belongs to the jump set or not.

Figure 13: Construction of the rectangle $\square(\mathbf{x},\mathbf{0})$
based on the location of the robot and the target location at the origin.

###  VII-A Switching to the obstacle-avoidance mode

Since the robot is initialized in the move-to-target mode, it will initially
move towards the target, under the influence of the stabilizing control vector
$-\kappa_{s}\mathbf{x},\kappa_{s}>0.$ Suppose, there exists an obstacle-
occupied workspace $\mathcal{O}_{\mathcal{W}}$ such that the line segment
$\mathcal{L}_{s}(\mathbf{x},\mathbf{0})$ intersects with the landing region
i.e.,
$\mathcal{L}_{s}(\mathbf{x},\mathbf{0})\cap\mathcal{R}_{l}\neq\emptyset.$ This
can be identified by evaluating the inner product between the vectors
$\mathbf{x}$ and $\mathbf{x}-\Pi(\mathbf{x},\mathcal{O}_{\mathcal{W}})$,
according to (26) and (49), and by verifying the condition given in (51).
Eventually, the robot moving straight towards the target will enter the
$\beta-$neighbourhood of the obstacle-occupied workspace, where
$\beta\in(r_{a},\alpha)$, i.e.,
$d(\mathbf{x},\mathcal{O}_{\mathcal{W}})=\beta$ such that one of the following
two cases holds:

Case A: there is a unique projection of the robot’s center onto the obstacle-
occupied workspace i.e.,
$\bf{card}(\mathcal{PJ}(\mathbf{x},\mathcal{O}_{\mathcal{W}}))=1.$

Case B: there are more than one projections of the robot’s center onto the
obstacle-occupied workspace i.e.,
$\bf{card}(\mathcal{PJ}(\mathbf{x},\mathcal{O}_{\mathcal{W}}))>1$, and
$-\mathbf{x}\in\mathcal{CH}(\mathbf{x},\mathcal{PJ}(\mathbf{x},\mathcal{O}_{\mathcal{W}}))$.

First, we consider case A. Since
$\mathcal{L}_{s}(\mathbf{x},\mathbf{0})\cap\mathcal{R}_{l}\neq\emptyset$, the
robot has to switch to the obstacle-avoidance mode. However, before that, it
needs to construct a virtual ring $\partial\mathcal{B}_{v_{r}}(\mathbf{c})$ to
locally modify the obstacle-occupied workspace to ensure the uniqueness of the
projection of its center onto the unsafe region. We locate the center of the
virtual ring $\partial\mathcal{B}_{v_{r}}(\mathbf{c})$ i.e., $\mathbf{c}$
using the following formula:

$\mathbf{c}=\Pi(\mathbf{x},\mathcal{O}_{\mathcal{W}})+(r_{a}+\gamma)\frac{\mathbf{x}-\Pi(\mathbf{x},\mathcal{O}_{\mathcal{W}})}{\lVert\mathbf{x}-\Pi(\mathbf{x},\mathcal{O}_{\mathcal{W}})\rVert},$
(53)

where $\gamma\in(\beta-r_{a},\alpha-r_{a})$ such that
$\text{card}(\mathcal{PJ}(\mathbf{c},\mathcal{O}_{\mathcal{W}}))=1$ and
$\Pi(\mathbf{c},\mathcal{O}_{\mathcal{W}})=\Pi(\mathbf{x},\mathcal{O}_{\mathcal{W}})$.
Then, the radius $v_{r}$ of the virtual ring
$\partial\mathcal{B}_{v_{r}}(\mathbf{c})$ is set to $r_{a}+\gamma$. The robot
then sets $\gamma_{s}=\beta-r_{a}$, and enters in the obstacle-avoidance mode
i.e., switches $m$ to $+1$ or $-1$. At this instance, we assign the current
location as the hit point $\mathbf{h}$, as per (40). Case A is illustrated in
Fig. 14a.

Now, we consider case B. We set $\mathbf{c}$ to be the current location of the
robot’s center i.e., $\mathbf{c}=\mathbf{x}$, and $v_{r}=\beta.$ Since the
robot has multiple projections on the obstacle-occupied workspace
$\mathcal{O}_{\mathcal{W}}$, it indicates the presence of a non-convex
obstacle in its immediate neighbourhood, as shown in Fig. 14b. Hence, to
ensure the uniqueness of the projection of the center of the robot onto the
unsafe region, we augment the boundary of the obstacle-occupied workspace with
a curve $\mathcal{Y}$, which is defined as

$\mathcal{Y}=\partial\mathcal{B}_{v_{r}}(\mathbf{c})\cap\mathcal{CH}(\mathbf{c},\mathcal{PJ}(\mathbf{c},\mathcal{O}_{\mathcal{W}})).$
(54)

The curve $\mathcal{Y}$ is the section of the virtual ring
$\partial\mathcal{B}_{v_{r}}(\mathbf{c})$ that belongs to the conic hull
$\mathcal{CH}(\mathbf{c},\mathcal{PJ}(\mathbf{c},\mathcal{O}_{\mathcal{W}})).$
Notice that the curve $\mathcal{Y}$ belongs to the boundary of the modified
obstacle $\mathbf{M}(\mathcal{O}_{\mathcal{W}},v_{r})$, as per Remark 4. We
treat this curve as a part of the boundary of the unsafe region i.e.,
$\partial\mathcal{O}_{\mathcal{W}}\leftarrow\partial\mathcal{O}_{\mathcal{W}}\cup\mathcal{Y}.$

The robot has not yet switched to the obstacle-avoidance mode, and is moving
straight towards the target inside the previously constructed virtual ring
$\partial\mathcal{B}_{v_{r}}(\mathbf{c})$, along the line segment
$\mathcal{L}_{s}(\mathbf{c},\mathbf{0})$. Since
$\mathcal{B}_{r_{a}}(\mathbf{x})\subset\mathcal{B}_{v_{r}}(\mathbf{c}),$ after
moving straight towards the target, the robot will have unique projection on
the curve $\mathcal{Y}$ and hence on the unsafe region
$\mathcal{O}_{\mathcal{W}}$. Then the robot will switch to the obstacle-
avoidance mode, according to case A.

Figure 14:  Illustration of two possible situations that can occur when the
robot, while operating in the move-to-target mode, enters in the
$\beta-$neighbourhood of the obstacle occupied workspace
$\mathcal{O}_{\mathcal{W}}$, $\beta\in(r_{a},\alpha).$ The left figure shows
the scenario where
$\mathbf{card}(\mathcal{PJ}(\mathbf{x},\mathcal{O}_{\mathcal{W}}))=1$. The
right figure represents the situation where
$\mathbf{card}(\mathcal{PJ}(\mathbf{x},\mathcal{O}_{\mathcal{W}}))>1.$

###  VII-B Moving in the obstacle-avoidance mode

We use a virtual ring $\partial\mathcal{B}_{v_{r}}(\mathbf{c})$ to ensure a
unique projection in the obstacle-avoidance mode. This ring anticipates
multiple projections and enables local modification of the obstacle-occupied
workspace to maintain uniqueness of the projection of the robot’s center.

Note that when the robot switches from the move-to-target mode to the
obstacle-avoidance mode, it is enclosed by the virtual ring i.e.,
$\mathcal{B}_{r_{a}}(\mathbf{x})\subset\mathcal{B}_{v_{r}}(\mathbf{c}).$
Hence, if the virtual ring $\partial\mathcal{B}_{v_{r}}(\mathbf{c})$ touches
the obstacle-occupied workspace $\mathcal{O}_{\mathcal{W}}$ at only one
location i.e.,
$\textbf{card}(\mathcal{PJ}(\mathbf{c},\mathcal{O}_{\mathcal{W}}))=1$, then
$\Pi(\mathbf{x},\mathcal{O}_{\mathcal{W}})=\Pi(\mathbf{c},\mathcal{O}_{\mathcal{W}}).$
Then, the robot can successfully implement the rotational control vector
$\mathbf{v}(\mathbf{x},m)$. To ensure that the robot’s body is always enclosed
by the virtual ring, we update the location of the center $\mathbf{c}$ as
follows:

$\mathbf{c}=\Pi(\mathbf{x},\mathcal{O}_{\mathcal{W}})+v_{r}\frac{\mathbf{x}-\Pi(\mathbf{x},\mathcal{O}_{\mathcal{W}})}{\lVert\mathbf{x}-\Pi(\mathbf{x},\mathcal{O}_{\mathcal{W}})\rVert},$
(55)

where $v_{r}$ is defined when the robot switches from the move-to-target mode
to the current obstacle-avoidance mode, as discussed in Section VII-A.

When the virtual ring touches the obstacle-occupied workspace at multiple
locations, it indicates the presence of a non-convex obstacle in the immediate
neighbourhood of the robot, as shown in Fig. 15. In this case, the robot
should use the projection of its center onto the part of the ring that
intersects with the conic hull
$\mathcal{CH}(\mathbf{c},\mathcal{PJ}(\mathbf{c},\mathcal{O}_{\mathcal{W}}))$
i.e., onto the set $\mathcal{Y}$, defined in (54), as the closest point. Note
that since
$\mathcal{B}_{r_{a}}(\mathbf{x})\subset\mathcal{B}_{v_{r}}(\mathbf{c}),$ the
projection $\Pi(\mathbf{x},\mathcal{Y})$, which is used to implement the
rotational control vector $\mathbf{v}(\mathbf{x},m)$, is unique.

Figure 15: A scenario in which, for the robot operating in the obstacle-
avoidance mode, the virtual ring $\partial\mathcal{B}_{v_{r}}(\mathbf{c})$
encounters more than one intersection point with the obstacle-occupied
workspace $\mathcal{O}_{\mathcal{W}}$ i.e.,
$\mathbf{card}(\mathcal{PJ}(\mathbf{c},\mathcal{O}_{\mathcal{W}}))>1.$

###  VII-C Switching to the move-to-target mode

When the robot, operating in the obstacle-avoidance mode, with some
$m\in\\{-1,1\\}$, reaches the location $\mathbf{x}$, which is $\epsilon$ units
closer to the target location than the current hit point $\mathbf{h}$, and
belongs to the exit region $\mathcal{R}_{m}\cup\mathcal{R}_{a}$, defined in
(28), (30) and (31), it switches to the move-to-target mode by setting $m=0$.

Algorithm 1 General implementation of the proposed hybrid control law (23).

1: Set target location at the origin $\mathbf{0}.$

2: Initialize $\mathbf{x}(0,0)\in\mathcal{W}_{r_{a}}$,
$\mathbf{h}(0,0)=\mathbf{x}(0,0)$ and $m(0,0)=0$. Choose $\bar{\epsilon}$
according to Lemma 36, and initialize $\epsilon\in(0,\bar{\epsilon}].$ Select
${\alpha}>0$ according to Lemma 5, and choose $\beta\in(r_{a},\alpha)$.

3: Measure $\mathbf{x}$.

4: if $m=0$, then

5: Implement Algorithm 2.

6: if $\xi\in\mathcal{J}_{0}$, then

7: Update $(\mathbf{h},m)\leftarrow\mathbf{L}(\mathbf{x},\mathbf{h},m)$ using
(40).

8: end if

9: end if

10: if $m\in\\{-1,1\\}$, then

11: Implement Algorithm 2.

12: if $\xi\in\mathcal{J}_{m}$, then

13: Update $(\mathbf{h},m)\leftarrow\mathbf{L}(\mathbf{x},\mathbf{h},m)$ using
(41).

14: end if

15: end if

16: if $m\in\\{-1,1\\}$, then

17: Measure $\Pi(\mathbf{x},\mathcal{O}_{\mathcal{W}})$ using (49).

18: Locate $\mathbf{c}$ using (55).

19: if $\mathbf{card}(\mathcal{PJ}(\mathbf{c},\mathcal{O}_{\mathcal{W}}))>1$,
then

20: Construct $\mathcal{Y}$ using (54).

21: Assign
$\partial\mathcal{O}_{\mathcal{W}}\leftarrow\partial\mathcal{O}_{\mathcal{W}}\cup\mathcal{Y}.$

22: end if

23: end if

24: Execute $\mathbf{u}(\mathbf{x},\mathbf{h},m)$ (23), used in (42).

25: Go to step 3.

Algorithm 2 Sensor-based identification of the jump set.

1: Measure $d(\mathbf{x},\mathcal{O}_{\mathcal{W}})$ (47), and
$\mathcal{PJ}(\mathbf{x},\mathcal{O}_{\mathcal{W}})$ (49).

2: if $m=0$, then

3: if $d(\mathbf{x},\mathcal{O}_{\mathcal{W}})\leq\beta$ then

4: if $\mathbf{card}(\mathcal{PJ}(\mathbf{x},\mathcal{O}_{\mathcal{W}}))=1$,
then

5: if
$\mathbf{x}^{\intercal}(\mathbf{x}-\Pi(\mathbf{x},\mathcal{O}_{\mathcal{W}}))\geq
0$, then

6: Identify $\partial\mathcal{O}$ using (51).

7: Construct $\square(\mathbf{x},\mathbf{0})$ using (52).

8: if $\partial\mathcal{O}\cap\square(\mathbf{x},\mathbf{0})\neq\emptyset$
then

9: $\xi\in\mathcal{J}_{0}.$

10: Set $\gamma_{s}=\beta-r_{a}.$

11: Choose $\gamma\in(\gamma_{s},\alpha-r_{a})$.

12: Set $v_{r}=r_{a}+\gamma.$

13: Locate $\mathbf{c}$ using (53).

14: end if

15: end if

16: else

17: if
$-\mathbf{x}\in\mathcal{CH}(\mathbf{x},\mathcal{PJ}(\mathbf{x},\mathcal{O}_{\mathcal{W}}))$,
then

18: Set $\mathbf{c}=\mathbf{x}$ and $v_{r}=\beta$.

19: Construct $\mathcal{Y}$ using (54).

20: Assign
$\partial\mathcal{O}_{\mathcal{W}}\leftarrow\partial\mathcal{O}_{\mathcal{W}}\cup\mathcal{Y}.$

21: end if

22: end if

23: end if

24: end if

25: if $m\in\\{-1,1\\}$ then

26: if $d(\mathbf{x},\mathcal{O}_{\mathcal{W}})<r_{a}+{\alpha},$ then

27: if $\mathbf{x}\in\mathcal{R}_{m}\cup\mathcal{R}_{a}$, defined in (28),
(30) and (31), then

28: if $\lVert\mathbf{x}\rVert\leq\lVert\mathbf{h}\rVert-\epsilon,$ then

29: $\xi\in\mathcal{J}_{m}$.

30: end if

31: end if

32: else

33: $\xi\in\mathcal{J}_{m}$.

34: end if

35: end if

##  VIII Simulation Results

In this section, we present simulation results for a robot navigating in a
priori unknown environments. In simulations discussed below, the robot is
assumed to be equipped with a range-bearing sensor (e.g. LiDAR) with an
angular scanning range of $360^{\circ}$ and sensing radius $R_{s}=3m$. The
angular resolution of the sensor is chosen to be $1^{\circ}$. The simulations
are performed in MATLAB 2020a.

In the first simulation scenario, we consider an unbounded workspace i.e.,
$\mathcal{O}_{0}=\emptyset$, with $3$ non-convex obstacles, as shown in Fig.
16. The robot with radius $r=0.3m$ is initialized at $[-16,4]^{\intercal}$.
The target is located at the origin. The minimum safety distance $r_{s}=0.1m$.
The parameter $\alpha=0.8m$ is known a priori, as per Lemma 5. We set the gain
values $\kappa_{s}$ and $\kappa_{r}$, used in (23), to be $0.5$ and $2$,
respectively. The parameter $\epsilon$, which is essential for the design of
the jump set of the obstacle-avoidance mode as given in (34) and (35), is set
to be $0.1m.$

The robot’s motion in the move-to-target mode is represented by the black-
coloured curves, whereas the red-coloured curves depict its motion in the
obstacle-avoidance mode. The locations $\mathbf{h}_{1}$ to $\mathbf{h}_{6}$
are the hit points where the robot switches from the move-to-target mode to
the obstacle-avoidance mode. Notice that the location of each hit point is
closer to the target location than the previous one, which ensures global
convergence of the robot to the target location, as stated in Theorem 1. Since
the robot moves parallel to the boundary of the unsafe region in the obstacle-
avoidance mode, it maintains a safe distance from the unsafe region, as shown
in Fig. 17. To avoid multiple projections onto the unsafe region, while
operating in the obstacle-avoidance mode, the robot constructs a virtual ring,
as explained in Section VII, and moves along its boundaries around the
obstacles $\mathcal{O}_{1}$ and $\mathcal{O}_{2}$. The complete simulation
video can be found at https://youtu.be/tRRUQNjLtGU.

Figure 16: Trajectory of a robot, initialized at $\mathbf{x}_{0}$, safely
converging to the target location at the origin. Figure 17:  Distance of the
robot’s center from the boundary of the obstacle-occupied workspace for the
simulation results shown in Fig. 16.

In the next simulation scenario, as shown in Fig. 18, we consider an
environment consisting of arbitrarily-shaped obstacles (possibly non-convex),
and apply the proposed hybrid controller (23) for a point robot navigation
initialized at 10 different locations in the obstacle-free workspace. The
target is located at the origin. The minimum safety distance $r_{s}=0.1m$ and
the parameter $\alpha=0.5m$. We set the gains $\kappa_{s}$ and $\kappa_{r}$,
used in (23a), to be 0.25 and 2, respectively. The parameter $\epsilon$ is set
to be $0.05m$.

Since the environment is a priori unknown and contains non-convex obstacles,
the robot maintains the same direction of motion when it moves in the
obstacle-avoidance mode to avoid retracing the previously travelled path, as
discussed in remark 5. This does not necessarily result in the robot
trajectories with the shortest lengths. The complete simulation video can be
found at https://youtu.be/OtHt-oQPg68.

Figure 18: Robot trajectories starting from different locations

Next, we consider an environment with unsafe region
$\mathcal{O}_{\mathcal{W}}$, consisting of $2$ non-convex obstacles
$\mathcal{O}_{1}$ and $\mathcal{O}_{2}$, that does not satisfy Assumption 2,
as shown in Fig. 19. The robot with radius $r=0.3m$ is initialized at
$[-6,3]^{\intercal}$. The target is located at the origin. The minimum safety
distance $r_{s}=0.1m$. The parameter $\alpha=1m$ is known a priori, as per
Lemma 5. We set the gain values $\kappa_{s}$ and $\kappa_{r}$, used in (23),
to be 0.5 and 2, respectively. The parameter $\epsilon$, used in (35), is set
to be $0.1m$.

Notice that even though the distance between the obstacles $\mathcal{O}_{1}$
and $\mathcal{O}_{2}$ is less than $2\alpha$, the modified obstacle-occupied
workspace $\mathcal{O}_{\mathcal{W}}^{M}$, obtained using (17), is not
connected. However, using the virtual ring construction mentioned in Section
VII-B, the robot maintains the uniqueness of its projection and moves safely
across the gap in the obstacle-avoidance mode, as shown in Fig. 19. The
complete simulation video can be found at https://youtu.be/T4xzo01_mkc.

Figure 19: Robot safely navigating towards the target (red dot) in an
environment that does not satisfy Assumption 2

###  VIII-A Gazebo simulation

The next simulation is performed using the Turtlebot3 Burger model in Gazebo.
The simulation runs on a computer, equipped with 4 GB RAM, running Ubuntu
20.04 with the ROS Noetic distribution installed, which we refer to as
Computer 1. The proposed hybrid controller is run in Matlab R2020a on another
computer running Windows 10, equipped with an Intel(R) i5-5200U CPU with a
clock speed of 2.20 GHz and 12 GB RAM, referred to as Computer 2.

The Turtlebot is equipped with a two-dimensional LiDAR scanner with a sensing
range of 1m. The angular scanning range and angular resolution are set to 360
degrees and 1 degree, respectively. The sensor measurements are assumed to be
affected by Gaussian noise with zero mean and a standard deviation of 0.01 m.
The maximum bounds on the linear velocity and angular velocity, denoted as
$\nu_{\max}$ and $\omega_{\max}$ respectively, are set to 0.15 m/s and 2.84
rad/s. The LiDAR scanning rate is set to 5 Hz.

At each iteration, the LiDAR measurements and pose information are sent from
Computer 1 to Computer 2. The control commands are then sent from Computer 2
to Computer 1. The execution time of the proposed hybrid controller is
approximately 5 ms. The sensor-based implementation of the proposed hybrid
navigation algorithm only requires the measurements acquired via a range-
bearing sensor. Since the size of the acquired sensor data is independent of
the surrounding environment, the code execution time will remain approximately
the same regardless of changes in the environment.

The Turtlebot can be represented with the following nonholonomic model:

$\displaystyle\dot{x}_{1}$ $\displaystyle=\nu\cos\theta,$ (56)
$\displaystyle\dot{x}_{2}$ $\displaystyle=\nu\sin\theta,$
$\displaystyle\dot{\theta}$ $\displaystyle=\omega,$

where $\mathbf{x}=[x_{1},x_{2}]^{\intercal}$ is the location of the center of
the robot and $\theta\in[-\pi,\pi)$ is the heading direction. The scalar
control variables $\nu$ and $\omega$ represent the linear and angular
velocities, respectively.

In practical applications, due to the discrete implementation of the control
law designed for a point-mass robot, the nonholonomic Turtlebot (when
operating in the obstacle-avoidance mode) may get very close to the obstacle
or exit the $\alpha$-neighborhood of the obstacle before getting closer to the
target location than the current hit point. To avoid this situation, we
introduce some minor modifications to the proposed hybrid control law to
ensure that the Turtlebot stays inside the $\alpha$-neighborhood of the
nearest obstacle when operating in the obstacle-avoidance mode. We replace the
vector $\mathbf{v}(\mathbf{x},m)$, used in (23a), with a modified vector
$\mathbf{v}_{mod}(\mathbf{x},m),$ which is defined as

$\mathbf{v}_{d}(\mathbf{x},m)=\begin{bmatrix}\lambda(\varrho(\mathbf{x}))&m(1-\lambda(\varrho(\mathbf{x}))^{2})\\\
-m(1-\lambda(\varrho(\mathbf{x}))^{2})&\lambda(\varrho(\mathbf{x}))\end{bmatrix}\mathbf{f}(\mathbf{x},m),$
(57)

where the vector-valued function $\mathbf{f}(\mathbf{x},m)$ is given by

$\mathbf{f}(\mathbf{x},m)=\frac{\mathbf{x}-\Pi(\mathbf{x},\mathcal{O}_{\mathcal{W}}^{M})}{\lVert\mathbf{x}-\Pi(\mathbf{x},\mathcal{O}_{\mathcal{W}}^{M})\rVert}.$
(58)

The scalar-valued function $\lambda(\varrho(\mathbf{x}))$ is evaluated as

$\lambda(\varrho(\mathbf{x}))=\begin{cases}\frac{0.25\eta-\varrho(\mathbf{x})}{0.25\eta},&0\leq\varrho(\mathbf{x})\leq
0.25\eta,\\\ 0,&0.25\eta\leq\varrho(\mathbf{x})\leq 0.75\eta,\\\
\frac{0.75\eta-\varrho(\mathbf{x})}{0.25\eta},&0.75\eta\leq\varrho(\mathbf{x})\leq\eta,\end{cases}$
(59)

where $\eta=\alpha-r_{a}$ and
$\varrho(\mathbf{x})=d(\mathbf{x},\mathcal{O}_{\mathcal{W}}^{M})-r_{a}$. The
continuous scalar-valued function $\lambda(\varrho(\mathbf{x}))\in[-1,1]$, for
all $\varrho(\mathbf{x})\in[0,\eta]$.

Notice that when $\lambda(\varrho(\mathbf{x}))=0$, the vector
$\mathbf{v}_{d}(\mathbf{x},m)$ equals to the vector
$\mathbf{v}(\mathbf{x},m)$, used in (23a). When the Turtlebot, while operating
in the obstacle-avoidance mode, moves closer to the boundary of the modified
obstacle-occupied workspace i.e., $\varrho(\mathbf{x})\to 0$,
$\lambda(\varrho(\mathbf{x}))\to 1$. As a result, the vector
$\mathbf{v}_{d}(\mathbf{x},m)\to\mathbf{f}(\mathbf{x},m)$ and the Turtlebot is
steered away from the unsafe region. On the other hand, if the center of the
Turtlebot moves closer to the boundary of the $\alpha-$neighbourhood of the
modified obstacle-occupied workspace i.e., $\varrho(\mathbf{x})\to\eta,$
$\lambda(\varrho(\mathbf{x}))\to-1$. Due to this, the vector
$\mathbf{v}_{d}(\mathbf{x},m)\to-\mathbf{f}(\mathbf{x},m)$ and the Turtlebot
is steered back inside the $\alpha-$neighbourhood of the modified obstacle-
occupied workspace.

Finally, given the modified hybrid control law $\mathbf{u}_{mod}$, obtained by
replacing $\mathbf{v}(\mathbf{x},m)$ by $\mathbf{v}_{mod}(\mathbf{x},m)$ in
(23a), the linear velocity $\nu$ and the angular velocity $\omega$ to be
applied to the Turtlebot are obtained as follows:

$\nu=\kappa_{\nu}\min\bigg{\\{}\lVert\mathbf{u}_{mod}\rVert\bigg{(}\frac{1+\cos(\theta-\theta_{d})}{2}\bigg{)}^{n},\nu_{\max}\bigg{\\}},$
(60) $\omega=-\kappa_{\omega}\omega_{\max}\sin(\theta-\theta_{d}),$ (61)

where $n>1$, $\kappa_{\nu}>0$ and $\kappa_{\omega}>0$. The angle $\theta$
represents the heading direction of the robot. The desired heading direction
is denoted by $\theta_{d}$, which is evaluated as
$\theta_{d}=\text{atan2v}(\mathbf{u}_{\text{mod}}).$ The expression
$\frac{1+\cos(\theta-\theta_{d})}{2}$ in (60) reduces the linear velocity of
the Turtlebot based on the disparity between its current heading direction
$\theta$ and the desired heading direction $\theta_{d}$.

We set the gains $\kappa_{s}$, $\kappa_{r}$, used in (23a), and
$\kappa_{\nu}$, $\kappa_{\omega}$, used in (60) and (61), to 1. The minimum
safety distance $r_{s}=0.03$ m and the parameter $\alpha=0.3$ m. Additionally,
the parameter $\epsilon$, used in (35), is set to 0.15 m. The target location
is set to the origin, represented by the light green dot, as shown in Fig. 20.
In Fig. 20a, the left figure shows the workspace setup in Gazebo with the
initial location of the Turtlebot, and the right figure shows the LiDAR sensor
measurements. The desired heading direction is denoted by the black arrow,
while the red arrow represents the current heading direction of the Turtlebot.
The Turtlebot and the target location are connected via a dotted red line.
When the Turtlebot moves straight towards the target location, it eventually
enters the $\alpha-$neighbourhood of the unsafe region and switches to the
obstacle-avoidance mode. In the obstacle-avoidance mode, it constructs a
virtual ring represented using the red dotted circle, as shown in Fig. 20b.
When the nearby obstacle workspace is convex in nature, the projection of the
center of the Turtlebot onto this workspace matches the intersection point
between the virtual ring and the nearby obstacle, which is represented by the
magenta coloured dot. In Fig. 20b, the black-dotted curve is a partial
boundary of the circle with its center at the origin and a radius of
$\lVert\mathbf{h}\rVert-\epsilon$, where $\mathbf{h}$ is the current location
of the hit point. According to (34), (35) and (39), the Turtlebot can switch
back to the move-to-target mode only if it is inside this circle. When the
nearby unsafe region is non-convex in nature, the virtual ring, which is
larger in size compared to the robot’s body, will have multiple intersections
with the obstacles, as shown in Fig. 20c. This prompts the Turtlebot to
project on the boundary of the virtual ring instead of the obstacle-occupied
workspace to maintain the uniqueness of the projection. In other words,
boundary of the virtual ring acts as the boundary of the modified obstacle, as
discussed in Remark 4. Finally, in Fig. 20d we can see the Turtlebot
approaching towards the target location at the origin. The complete simulation
video can be found at https://youtu.be/ZNeiS5qE00k.

Figure 20: Autonomous navigation of the Turtlebot in non-convex environment.

##  IX Conclusion

We proposed a hybrid feedback controller for safe autonomous navigation in
two-dimensional environments with arbitrary-shaped obstacles (possibly non-
convex). The obstacles can have non-smooth boundaries and large sizes and can
be placed arbitrarily close to each other provided the feasibility
requirements stated in Assumptions 1 and 2 are satisfied. The proposed hybrid
controller, endowed with global asymptotic stability guarantees, relies on an
instrumental transformation that virtually modifies the obstacles’ shapes such
that the uniqueness of the projection of the robot’s center onto the closest
obstacle is guaranteed - a feature that helps in the design of our obstacle-
avoidance strategy. The obstacle avoidance component of the control law (24)
utilizes the projection of the robot’s center onto the nearest obstacle.
Hence, it is possible to apply the proposed hybrid control scheme in a priori
unknown environments, as discussed in Section VII. It should be noted that the
trajectories generated by our algorithm may not necessarily correspond to the
shortest paths between the initial and final configurations, as shown in Fig.
18. Moreover, when the robot switches between the modes, the control input
vector (23a) changes value discontinuously. Designing a smooth feedback
control law that generates robot trajectories with the shortest lengths would
be an interesting extension of the present work. Other interesting extensions
consist in considering robots with second-order dynamics and three-dimensional
environments with non-convex obstacles.

###  -A Hybrid basic conditions

######  Lemma 9.

The hybrid closed-loop system (42) with the data
$(\mathcal{F},\mathbf{F},\mathcal{J},\mathbf{J})$ satisfies the hybrid basic
conditions stated in [28, Assumption 6.5].

###### Proof.

The flow set $\mathcal{F}$ and the jump set $\mathcal{J}$, defined in (38) and
(39) are closed subsets of
$\mathbb{R}^{2}\times\mathbb{R}^{2}\times\mathbb{M}$. The flow map
$\mathbf{F}$, given in (42), is continuous on $\mathcal{F}_{0}$. For each
$\mathbf{x}\in\mathcal{N}_{\beta}(\mathcal{D}_{r_{a}}(\mathcal{O}_{\mathcal{W}}^{M})),\beta\in[r_{a},\alpha),$
according to Lemma 3, the set
$\mathcal{PJ}(\mathbf{x},\mathcal{O}_{\mathcal{W}}^{M})$ is a singleton. Then,
for
$\mathbf{x}\in\mathcal{N}_{\beta}(\mathcal{D}_{r_{a}}(\mathcal{O}_{\mathcal{W}}^{M})),\beta\in[r_{a},\alpha)$,
$\Pi(\mathbf{x},\mathcal{O}_{\mathcal{W}}^{M})$ is continuous with respect to
$\mathbf{x}.$ As a result, $\mathbf{F}$ is continuous on
$\mathcal{F}_{m},m\in\\{-1,1\\}$. Hence $\mathbf{F}$ is continuous on
$\mathcal{F}.$ The jump map $\mathbf{J}$, defined in (42), is single-valued on
$\mathcal{J}_{m},m\in\\{-1,1\\}$ (41). Also, $\mathbf{J}$ has a closed graph
relative to $\mathcal{J}_{0}$ (39), as it is allowed to be set-valued whenever
$\mathbf{x}\in\mathcal{J}_{0}.$ Hence, according to [28, Lemma 5.10],
$\mathbf{J}$ is outer semi-continuous and locally bounded relative to
$\mathcal{J}$. ∎

###  -B Proof of Lemma 1

This proof is by contradiction. Let us assume that there exists a location
$\mathbf{x}$ such that $d(\mathbf{x},\mathcal{A})=\beta$, where
$\beta\in(0,\alpha)$, and the set $\mathcal{PJ}(\mathbf{x},\mathcal{G})$ is
not a singleton, where the closed set
$\mathcal{G}=(\mathcal{A}\oplus\mathcal{B}_{\alpha}^{\circ}(\mathbf{0}))^{c}$.
Hence, there exists at least two distinct points $\mathbf{p}_{1}$ and
$\mathbf{p}_{2}$ such that
$\mathbf{p}_{1},\mathbf{p}_{2}\in\partial\mathcal{G}\cap\mathcal{PJ}(\mathbf{x},\partial\mathcal{G}).$
Let the distance $d(\mathbf{x},\mathcal{G})=\eta.$

Since we have $\textbf{reach}(\mathcal{A})\geq\alpha$, the set
$\mathcal{PJ}(\mathbf{x},\mathcal{A})$ is a singleton. As a result, according
to [26, Lemma 4.5], the vector
$\frac{\mathbf{x}-\Pi(\mathbf{x},\mathcal{A})}{\lVert\mathbf{x}-\Pi(\mathbf{x},\mathcal{A})\rVert}\in\mathbf{N}_{\mathcal{A}}(\Pi(\mathbf{x},\mathcal{A}))$,
where $\mathbf{N}_{\mathcal{A}}(\Pi(\mathbf{x},\mathcal{A}))$ denotes the
normal cone to the set $\mathcal{A}$ at the point
$\Pi(\mathbf{x},\mathcal{A}).$ Furthermore, according to [26, Lemma 4.5], for
the location
$\mathbf{q}=\Pi(\mathbf{x},\mathcal{A})+\alpha\frac{\mathbf{x}-\Pi(\mathbf{x},\mathcal{A})}{\lVert\mathbf{x}-\Pi(\mathbf{x},\mathcal{A})\rVert}$,
the open Euclidean ball $\mathcal{B}_{\alpha}^{\circ}(\mathbf{q})$ does not
intersect with the set $\mathcal{A}$ i.e.,
$\mathcal{B}_{\alpha}^{\circ}(\mathbf{q})\cap\mathcal{A}=\emptyset.$ Hence, as
the set $\partial\mathcal{G}$ is the set of all points in $\mathbb{R}^{n}$
that are exactly at $\alpha$ distance away from the set $\mathcal{A}$, the
location
$\mathbf{q}\in\partial\mathcal{G}\cap\mathcal{L}(\mathbf{x},\Pi(\mathbf{x},\mathcal{A}))$.
Now, we consider two cases depending on the location of the point $\mathbf{q}$
on the line $\mathcal{L}(\mathbf{x},\Pi(\mathbf{x},\mathcal{A}))$ as follows:

Case 1:  $d(\mathbf{q},\Pi(\mathbf{x},\mathcal{A}))=\alpha\geq\beta+\eta$. In
this case,
$\mathcal{B}_{\eta}(\mathbf{x})\subset\mathcal{B}_{\alpha}(\Pi(\mathbf{x},\mathcal{A}))\subset\mathcal{D}_{\alpha}(\mathcal{A})$.
As $\textbf{card}(\mathcal{PJ}(\mathbf{x},\partial\mathcal{G}))>1$, the set
$\\{\mathbf{p}_{1},\mathbf{p}_{2}\\}\subset\partial\mathcal{B}_{\eta}(\mathbf{x})\cap\partial\mathcal{G}$.
Hence, there should be at least two points of contact between the sets
$\partial\mathcal{B}_{\eta}(\mathbf{x})$ and
$\partial\mathcal{B}_{\alpha}(\Pi(\mathbf{x},\mathcal{A}))$. Since
$\alpha\geq\beta+\eta$, the Euclidean ball $\mathcal{B}_{\eta}(\mathbf{x})$
can only touch the boundary of the Euclidean ball
$\mathcal{B}_{\alpha}(\Pi(\mathbf{x},\mathcal{A}))$ at no more that one point,
resulting in a contradiction.

Case 2:  $\beta+\eta>d(\mathbf{q},\Pi(\mathbf{x},\mathcal{A}))=\alpha>\beta$.
Since $\mathbf{q}\in\partial\mathcal{G}$ and
$\mathbf{q}\in\mathcal{B}_{\eta}^{\circ}(\mathbf{x})$, the distance
$d(\mathbf{x},\mathcal{G})<\eta,$ which is a contradiction.

###  -C Proof of Lemma 2

The cases where $\beta=0$ and $\beta=\alpha$ are trivial. We analyze the case
where $\beta\in(0,\alpha)$. This proof is by contradiction. Let us assume that
there exists a location $\mathbf{x}$ such that the distance
$d(\mathbf{x},\mathcal{A})=\eta$, where $\eta\in(\beta,\alpha)$, and the set
$\mathcal{PJ}(\mathbf{x},\mathcal{D}_{\beta}(\mathcal{A}))$ is not a
singleton. Therefore, there exist at least two distinct points
$\mathbf{p}_{1}$ and $\mathbf{p}_{2}$ such that
$\mathbf{p}_{1},\mathbf{p}_{2}\subset\partial\mathcal{D}_{\beta}(\mathcal{A})\cap\mathcal{PJ}(\mathbf{x},\mathcal{D}_{\beta}(\mathcal{A})).$

Since $\textbf{reach}(\mathcal{A})=\alpha$, the points $\mathbf{p}_{1}$ and
$\mathbf{p}_{2}$, which belong to the set
$\partial\mathcal{D}_{\beta}(\mathcal{A})$, have unique projection on the set
$\mathcal{A}$ and the distance
$d(\mathbf{p}_{1},\Pi(\mathbf{p}_{1},\mathcal{A}))=d(\mathbf{p}_{2},\Pi(\mathbf{p}_{2},\mathcal{A}))=\beta$.
Moreover, as $\mathbf{x}\in\partial\mathcal{D}_{\eta}(\mathcal{A})$, the
distance
$d(\mathbf{x},\mathbf{p}_{1})=d(\mathbf{x},\mathbf{p}_{2})=\eta-\beta$, and
$d(\mathbf{x},\mathcal{A})=\eta$. Therefore, one has
$d(\mathbf{x},\Pi(\mathbf{p}_{1},\mathcal{A}))=d(\mathbf{x},\Pi(\mathbf{p}_{2},\mathcal{A}))=\eta.$
As a result, the locations
$\\{\Pi(\mathbf{p}_{1},\mathcal{A}),\Pi(\mathbf{p}_{2},\mathcal{A})\\}\subset\mathcal{PJ}(\mathbf{x},\mathcal{A}).$
Since $\eta\in(0,\alpha)$ and $\textbf{reach}(\mathcal{A})=\alpha$,
$\textbf{card}(\mathcal{PJ}(\mathbf{x},\mathcal{A}))=1$. Hence,
$\Pi(\mathbf{p}_{1},\mathcal{A})=\Pi(\mathbf{p}_{2},\mathcal{A})=\Pi(\mathbf{x},\mathcal{A}).$
This, by the application of triangular inequality, implies that
$\mathbf{p}_{1}=\mathbf{p}_{2}$, which is a contradiction.

###  -D Proof of Lemma 3

Note that the following statement: “for all locations $\mathbf{x}$ with
$d(\mathbf{x},\mathcal{O}_{\mathcal{W}}^{M})<\alpha$, where $\alpha\geq 0$,
the set $\mathcal{PJ}(\mathbf{x},\mathcal{O}_{\mathcal{W}}^{M})$ is
singleton”, is equivalent to having
$\textbf{reach}(\mathcal{O}_{\mathcal{W}}^{M})\geq\alpha,$ as defined in
Section II-C. According to Remark 2, the modified obstacle-occupied workspace
$\mathcal{O}_{\mathcal{W}}^{M}=\mathbf{M}(\mathcal{O}_{\mathcal{W}},\alpha)=(\mathcal{W}_{\alpha}\oplus\mathcal{B}_{\alpha}^{\circ}(\mathbf{0}))^{c}$,
where the set $\mathcal{W}_{\alpha}$ is closed subset of $\mathbb{R}^{n}$
(15). Therefore, if we prove that
$\textbf{reach}(\mathcal{W}_{\alpha})\geq\alpha$, then, according to Lemma 1,
we have $\textbf{reach}(\mathcal{O}_{\mathcal{W}}^{M})\geq\alpha$. To that
end, we prove the following fact:

Fact 1:  Let $\alpha>0$ such that the $\alpha-$eroded obstacle-free workspace
$\mathcal{W}_{\alpha}$, defined according to (15), is not an empty set. Then,
the following two statements are equivalent:

  1. 1.

$\forall\mathbf{x}\in\partial\mathcal{W}_{\alpha}$, the intersection
$\mathbf{N}_{\mathcal{W}_{\alpha}}(\mathbf{x})\cap\mathcal{B}_{2\alpha}(\mathbf{x})\subset\mathcal{D}_{\alpha}(\mathcal{O}_{\mathcal{W}},$

  2. 2.

$\textbf{reach}(\mathcal{W}_{\alpha})\geq\alpha$.

###### Proof.

First, we prove the forward implication $1)\implies 2)$ by using [26,
Proposition 4.14]. According to Assumption 2, the locations
$\mathbf{q}=\mathbf{x}+2\alpha\mathbf{n}\notin\mathcal{W}_{\alpha}^{\circ}$,
for all $\mathbf{n}\in\mathbf{N}_{\mathcal{W}_{\alpha}}(\mathbf{x})$, for all
$\mathbf{x}\in\partial\mathcal{D}_{\alpha}(\mathcal{O}_{\mathcal{W}}).$ Hence,
for any location $\mathbf{p}\in\mathcal{W}_{\alpha}$, the distance
$d\left(\mathbf{p}-\mathbf{x},\mathbf{T}_{\mathcal{W}_{\alpha}}(\mathbf{x})\right)\leq\frac{\lVert\mathbf{p}-\mathbf{x}\rVert^{2}}{2\alpha}.$
Then, according to [26, Proposition 4.14],
$\textbf{reach}(\mathcal{W}_{\alpha})\geq\alpha.$

Next, we prove the backward implication $2)\implies 1)$. Let $\mathbf{x}$ be
any location on the boundary of the set $\mathcal{W}_{\alpha}$ and
$\mathbf{n}$ be any unit vector in the normal cone to the set
$\mathcal{W}_{\alpha}$ at $\mathbf{x}$ i.e.,
$\mathbf{x}\in\partial\mathcal{W}_{\alpha}$ and
$\mathbf{n}\in\mathbf{N}_{\mathcal{W}_{\alpha}}(\mathbf{x}),\lVert\mathbf{n}\rVert=1$.
Since $\textbf{reach}(\mathcal{W}_{\alpha})\geq\alpha,$ according to [26,
Lemma 4.5], the open Euclidean ball $\mathcal{B}_{\alpha}^{\circ}(\mathbf{p})$
does not intersect with the set $\mathcal{W}_{\alpha}$ i.e.,
$\mathcal{B}_{\alpha}^{\circ}(\mathbf{p})\cap\mathcal{W}_{\alpha}=\emptyset$,
which implies that
$\mathcal{B}_{\alpha}(\mathbf{p})\subset\mathcal{D}_{\alpha}(\mathcal{O}_{\mathcal{W}})$,
where the location $\mathbf{p}=\mathbf{x}+\alpha\mathbf{n}$. As a result, the
location $\mathbf{x}+2\alpha\mathbf{n}\notin\mathcal{W}_{\alpha}^{\circ}$,
hence proved.∎

According to Fact 1, Assumption 2 implies that
$\textbf{reach}(\mathcal{W}_{\alpha})\geq\alpha$. Hence, according to Lemma 1
and Remark 2, we have
$\textbf{reach}(\mathcal{O}_{\mathcal{W}}^{M})\geq\alpha.$

###  -E Proof of Lemma 4

Let us assume that the modified obstacle $\mathcal{O}_{i,\alpha}^{M}$ is not a
connected set, then it implies that there exists two disjoint subsets
$\mathcal{M}_{1}\subset\mathcal{O}_{i,\alpha}^{M}$ and
$\mathcal{M}_{2}\subset\mathcal{O}_{i,\alpha}^{M}$ such that
$\mathcal{M}_{1}\cup\mathcal{M}_{2}=\mathcal{O}_{i,\alpha}^{M}$ and
$\mathcal{M}_{1}\cap\mathcal{M}_{2}=\emptyset,$ [24, Definition 16.1]. By
construction in (17), there exists two non-empty set
$\mathcal{O}_{\mathbb{C}}\subset\mathcal{O}_{i,\alpha}$ and
$\mathcal{O}_{\mathbb{D}}\subset\mathcal{O}_{i,\alpha}$ such that
$\mathcal{O}_{\mathbb{C}}\subset\mathcal{M}_{1}$,
$\mathcal{O}_{\mathbb{D}}\subset\mathcal{M}_{2}$ and
$\mathcal{O}_{\mathbb{C}}\cup\mathcal{O}_{\mathbb{D}}=\mathcal{O}_{i,\alpha}$.
Note that, the distance $d(\mathcal{M}_{1},\mathcal{M}_{2})$ can not be
greater than or equal to $2\alpha.$ Otherwise, as the operator $\mathbf{M}$ is
extensive, see Remark 18, it implies that
$d(\mathcal{O}_{\mathbb{C}},\mathcal{O}_{\mathbb{D}})\geq 2\alpha.$ However,
according to (20), the distance
$d(\mathcal{O}_{\mathbb{C}},\mathcal{O}_{\mathbb{D}})<2\alpha$. Hence, the
distance $0<d(\mathcal{M}_{1},\mathcal{M}_{2})<2\alpha.$ Therefore,
$\exists\mathbf{q}_{1}\in\mathcal{M}_{1}$ and
$\exists\mathbf{q}_{2}\in\mathcal{M}_{2}$ such that
$0<d(\mathbf{q}_{1},\mathbf{q}_{2})=d(\mathcal{M}_{2},\mathcal{M}_{2})<2\alpha$.
This implies, the location $\mathbf{q}=0.5\mathbf{q}_{1}+0.5\mathbf{q}_{2}$,
which belongs to the interior of the $\alpha-$dilated modified obstacle,
$\mathbf{q}\in\mathcal{D}_{\alpha}(\mathcal{O}_{i,\alpha}^{M})$, has multiple
closest points on the modified obstacle $\mathcal{O}_{i,\alpha}^{M}$, which
cannot be the case as per Lemma 3. Hence, the modified obstacle
$\mathcal{O}_{i,\alpha}^{M}$ is a connected set.

###  -F Proof of Lemma 5

According to Assumption 1, the set $\mathcal{W}_{r_{a}}^{\circ}$ is a pathwise
connected set. Hence, it is evident that there exist a scalar
$\bar{\delta}_{1}>r_{a}$ such that for all $\delta\in(r_{a},\delta_{1}]$ the
$\delta$ eroded obstacle-free workspace $\mathcal{W}_{\delta}$ is pathwise
connected. Assumption 1 also assumes that the target location at the origin is
in the set $\mathcal{W}_{r_{a}}^{\circ}$. Hence, the distance
$d(\mathbf{0},\mathcal{W}_{r_{a}})>0$. Then, it is straight forward to notice
that there exists $\bar{\delta}_{2}>r_{a}$ such that for any
$\delta\in(r_{a},\bar{\delta}_{2}]$ the distance
$d(\mathbf{0},\mathcal{W}_{\delta})<\delta-r_{a}.$ Then, one can choose
$\bar{\alpha}=\min\\{\bar{\delta}_{1},\bar{\delta}_{2}\\}$ to satisfy Lemma 5.

###  -G Proof of Lemma 6

Since the obstacle reshaping operator $\mathbf{M}$ is idempotent, we have
$\mathbf{M}(\mathcal{O}_{\mathcal{W}},\alpha)=\mathbf{M}(\mathcal{O}_{\mathcal{W}}^{M},\alpha)$.
Therefore, according to (17),
$\mathcal{O}_{\mathcal{W}}\oplus\mathcal{B}_{\alpha}^{\circ}(\mathbf{0})=\mathcal{O}_{\mathcal{W}}^{M}\oplus\mathcal{B}_{\alpha}^{\circ}(\mathbf{0})$.
As a result, according to (15) and (16), the $\alpha-$eroded obstacle-free
workspace $\mathcal{W}_{\alpha}$ is equivalent to the $\alpha-$eroded modified
obstacle-free workspace $\mathcal{V}_{\alpha}$. Hence, if one chooses $\alpha$
as per Lemma 5, then the set $\mathcal{V}_{\alpha}$ is pathwise connected. As
a result, the modified obstacle-free workspace w.r.t. the center of the robot
$\mathcal{V}_{r_{a}}$ is also pathwise connected. Moreover, according to Lemma
5, the distance between the origin and the set $\mathcal{V}_{\alpha}$ is less
than $\alpha-r_{a}$. Since the distance between the sets
$\partial\mathcal{W}_{\alpha}$ and $\partial\mathcal{W}_{r_{a}}$ is $\alpha-
r_{a}$, it is evident that the origin belongs to the interior of the modified
obstacle-free workspace w.r.t. the center of the robot $\mathcal{V}_{r_{a}}.$

###  -H Proof of Lemma 36

We consider a connected modified obstacle
$\mathcal{O}_{i,\alpha}^{M},i\in\mathbb{I}$, as stated in Lemma 4, and proceed
by proving the following two claims:

Claim 1: For every
$\mathbf{h}\in\mathcal{J}_{0}^{\mathcal{W}}\cap\partial\mathcal{D}_{\beta}(\mathcal{O}_{i,\alpha}^{M}),\beta\in[r_{a},r_{a}+\gamma_{s}]$
and any location
$\mathbf{p}\in\mathcal{PJ}(\mathbf{0},\partial\mathcal{D}_{\beta}(\mathcal{O}_{i,\alpha}^{M}))$,
the distance
$d(\mathbf{h},\mathcal{B}_{2\delta}(\mathbf{p}))\geq\epsilon_{h}$, where

$\epsilon_{h}=\sqrt{\left(d(\mathbf{0},\mathcal{O}_{\mathcal{W}}^{M})^{2}-r_{a}^{2}\right)}-d(\mathbf{0},\mathcal{D}_{r_{a}}(\mathcal{O}_{\mathcal{W}}^{M})),$

and $\delta=\min\\{d(\mathbf{0},\mathcal{O}_{\mathcal{W}}^{M})-r_{a},\beta-
r_{a}\\}.$

Claim 2: For $m\in\\{-1,1\\}$, the set
$\mathcal{H}_{\mathbf{p}}:=\mathcal{B}_{\delta}(\mathbf{p})\cap\mathcal{N}_{\gamma}(\mathcal{D}_{r_{a}}(\mathcal{O}_{i,\alpha}^{M}))\subset\mathcal{R}_{a},$
where the location $\mathbf{p}$ and the scalar parameter $\delta$ are defined
in claim 1 above.

Claim 1 states that for any connected modified obstacle
$\mathcal{O}_{i,\alpha}^{M}$, the distance between any point $\mathbf{h}$,
which is located in the jump set of the move-to-target mode associated with
this modified obstacle at some distance $\beta\in[r_{a},r_{a}+\gamma_{s}]$
from it i.e.,
$\mathbf{h}\in\mathcal{J}_{0}^{\mathcal{W}}\cap\partial\mathcal{D}_{\beta}(\mathcal{O}_{i,\alpha}^{M}),\beta\in[r_{a},r_{a}+\gamma_{s}]$,
and the Euclidean balls of radius $2\delta$ centered at the set of projections
of the target onto the set
$\partial\mathcal{D}_{\beta}(\mathcal{O}_{i,\alpha}^{M})$ is always greater
than or equal to $\epsilon_{h}$ i.e.,
$d(\mathbf{h},\mathcal{B}_{2\delta}(\mathbf{p}))\geq\epsilon_{h},$ where the
location
$\mathbf{p}\in\mathcal{PJ}(\mathbf{0},\mathcal{D}_{\beta}(\mathcal{O}_{i,\alpha}^{M}))$
and the scalar parameter $\delta=\min\\{\beta-
r_{a},d(\mathbf{0},\mathcal{O}_{i,\alpha}^{M})-r_{a}\\}.$

Claim 2 states that the set $\mathcal{H}_{\mathbf{p}}$, which represents the
intersection between the $\delta$-neighbourhood of the set of projections of
the target onto the set
$\partial\mathcal{D}_{\beta}(\mathcal{O}_{i,\alpha}^{M})$ i.e.,
$\mathcal{B}_{\delta}(\mathbf{p}),\mathbf{p}\in\mathcal{PJ}(\mathbf{0},\mathcal{D}_{\beta}(\mathcal{O}_{i,\alpha}^{M}))$
and the $\gamma-$neighbourhood of the dilated modified obstacle i.e.,
$\mathcal{N}_{\gamma}(\mathcal{D}_{r_{a}}(\mathcal{O}_{i,\alpha}^{M}))$ is
subset of the always exit region $\mathcal{R}_{a}$ (28). This implies that if
$\bar{\epsilon}\in(0,\epsilon_{h}]$, then the set
$\mathcal{H}_{\mathbf{p}}\subset\mathcal{ER}_{m}^{\mathbf{h}}$, where the set
$\mathcal{ER}_{m}^{\mathbf{h}}$ is defined in (35).

####  -H1 Proof of claim 1

We aim to obtain an expression for
$\lVert\mathbf{h}_{\beta}\rVert-\lVert\mathbf{p}_{\beta}\rVert$, for
$\beta\in[r_{a},r_{a}+\gamma_{s}]$, where

$\mathbf{h}_{\beta}=\underset{\mathbf{h}\in\mathcal{J}_{0}^{\mathcal{W}}\cap\partial\mathcal{D}_{\beta}(\mathcal{O}_{i,\alpha}^{M})}{\text{argmin
}}\lVert\mathbf{h}\rVert,$ (62)

and the location
$\mathbf{p}_{\beta}\in\mathcal{PJ}(\mathbf{0},\partial\mathcal{D}_{\beta}(\mathcal{O}_{i,\alpha}^{M}))$.

Now, depending on the shape of the obstacle there can be two possibilities as
follows:

Case A: When
$\mathbf{h}_{\beta}\in\partial\mathcal{D}_{\beta}(\mathcal{O}_{i,\alpha}^{M})\cap\mathcal{CH}(\mathbf{0},\mathcal{O}_{i,\alpha}^{M}),$
as shown in Fig. 21. Notice that the line segment joining the location
$\mathbf{h}_{\beta}$ and the origin passes through the modified obstacle
$\mathcal{O}_{i,\alpha}^{M}$ i.e.,
$\mathcal{L}_{s}(\mathbf{h}_{\beta},\mathbf{0})\cap\mathcal{O}_{i,\alpha}^{M}\neq\emptyset$.
Hence, a part of this line segment belongs to the modified obstacle