# Deep Reinforcement Learning Graphs: Feedback Motion Planning via Neural
Lyapunov Verification

Armin Ghanbarzadeh, , Esmaeil Najafi

###### Abstract

Recent advancements in model-free deep reinforcement learning have enabled
efficient agent training. However, challenges arise when determining the
region of attraction for these controllers, especially if the region does not
fully cover the desired area. This paper addresses this issue by introducing a
feedback motion control algorithm that utilizes data-driven techniques and
neural networks. The algorithm constructs a graph of connected reinforcement-
learning based controllers, each with its own defined region of attraction.
This incremental approach effectively covers a bounded region of interest,
creating a trajectory of interconnected nodes that guide the system from an
initial state to the goal. Two approaches are presented for connecting nodes
within the algorithm. The first is a tree-structured method, facilitating
”point-to-point” control by constructing a tree connecting the initial state
to the goal state. The second is a graph-structured method, enabling ”space-
to-space” control by building a graph within a bounded region. This approach
allows for control from arbitrary initial and goal states. The proposed
method’s performance is evaluated on a first-order dynamic system, considering
scenarios both with and without obstacles. The results demonstrate the
effectiveness of the proposed algorithm in achieving the desired control
objectives.

###### Index Terms:

Deep Reinforcement Learning, Feedback Motion Control, Sequential Control,
Lyapunov Stability, Neural Networks.

##  I Introduction

This study addresses the challenge of controlling underactuated nonlinear
dynamic systems characterized by input saturation and bounded states. Existing
methodologies involve the linearization of such systems and the subsequent
design of controllers, albeit with the limitation that the resultant
controller is only effective in the vicinity of the system’s origin. In
contrast, data-driven approaches, particularly those leveraging Reinforcement
Learning (RL), offer a promising avenue for addressing this limitation. RL,
employing deep function approximators, can effectively design controllers
tailored to highly nonlinear systems. However, it is essential to acknowledge
certain drawbacks associated with these algorithms. Firstly, they entail a
substantial computational cost, posing challenges in real-time applications.
Furthermore, a critical limitation lies in the absence of explicit
confirmation of stability following the computation of an RL controller.
Consequently, users are left with an inherent uncertainty regarding the
viability of the controller within a specific region, commonly referred to as
the Region of Attraction (RoA). This lack of information regarding the
controller’s effective operational domain constitutes a noteworthy concern in
the practical application of RL-based control strategies.

In order to facilitate the applicability of linear controllers to nonlinear
systems, the concept of sequential control has been introduced, as outlined in
[1]. This approach involves the initial design of linear controllers without
explicit consideration of their RoA. Subsequently, each controller undergoes
evaluation to ascertain its respective RoA. The subsequent controller is then
designed with the deliberate intention of having its RoA situated within the
preceding domain, while concurrently stabilizing a distinct point within the
operational state space of the system. This iterative process, referred to as
synthesis, involves the continued design of these local controllers, and by
following the trajectory they define, the system can progress from an initial
state to a desired state. The path-following mechanism employed by these
sequential controllers can be analogously likened to a ball descending through
sequentially arranged funnels, as illustrated in Figure 1. Each funnel’s
mouth, or preimage, corresponds to the RoA of the associated controller. Upon
traversing through a funnel, the ball transitions to the next one, and this
process repeats until the system reaches its intended goal [2].

(a)  Figure 1: Illustration of the sequential controllers path following akin
to a ball descending through funnels. Each controller is only active outside
the domains of lower controllers. The lowest controller stabilizes the system
at the final destination. Each funnels preimage represents the RoA of the
corresponding controller, adopted from [1]

Various algorithms have been developed to address the challenges of
efficiently and safely planning trajectories for robots. Classical algorithms
such as A* [3] and Dijkstra’s algorithm [4] have laid the foundation, but
recent advancements have introduced a plethora of novel approaches.

Randomized motion planning methods have emerged as powerful tools in the field
of robotics and autonomous systems, offering efficient solutions to complex
path planning problems [5, 6]. These methods, often rooted in probabilistic
algorithms, introduce an element of randomness to the planning process,
enabling robots to navigate through dynamic and uncertain environments.
Notable among these techniques is the Rapidly-exploring Random Tree (RRT) [7]
algorithm which has the ability to efficiently explore configuration spaces by
randomly sampling feasible paths. Additionally, variants such as RRT* [8],
RRT*-Smart [9], and A*-RRT [10] have further improved upon the original
framework, addressing issues related to optimality and computational
efficiency. LQR-RRT a was proposed as a kinodynamic variant for complex or
underactuated dynamics [11]. Fast Marching Trees (FMT) [12] is a variant of
the RRT algorithm designed to efficiently explore and plan paths in high-
dimensional configuration spaces. FMT combines ideas from the Fast Marching
Method with the probabilistic nature of RRT. The algorithm iteratively grows a
tree from the starting configuration, favoring regions with lower cost-to-go
values. FMT is particularly well-suited for applications in motion planning
for robotic systems operating in dynamic and challenging environments.
Probabilistic Roadmap (PRM) [13], a widely employed randomized motion planning
method in robotics, constructs a graph representation of the configuration
space through random sampling and collision checking. PRM has various
variants, including PRM* [14], which enhances optimality by refining the
roadmap over iterations demonstrating adaptability and efficiency in
navigating complex and high-dimensional environments.

In the field of controlling dynamic systems, a common issue that arises after
trajectory planning is that designing controllers for these paths can be
tricky and less effective compared to other trajectory options. A more recent
solution involves using feedback motion planning algorithms, which tackle both
path planning and controller design simultaneously. [15] used a combination of
local trajectory optimizers and a stabilizing technique called Linear
Quadratic Regulator (LQR) with random starting points. The method proposed
exploring the solution space thoroughly in hops of finding the best overall
solution. [16] suggested a control design approach using ”patchy Lyapunov
functions.” This method stabilizes the system by strategically covering the
state space with a set of locally effective control functions and ensuring
stability through a switching feedback control.

The method proposed in this work is motivated from the RoA-based planning
method proposed in [17], in which the authors propose a feedback motion-
planning algorithm that leverages rigorously computed stability regions to
construct a sparse tree of LQR-stabilized trajectories. The resulting non-
linear feedback policy exhibits a region of attraction that ”probabilistically
covers” the entire controllable subset of the state space. This paper
endeavors to integrate advancements in data-driven methodologies for the
control of nonlinear dynamic systems, with a particular focus on the
application of RL to formulate local controllers within the state space.
Utilizing neural Lyapunov networks, the determination of the RoA for these
controllers is facilitated, thereby achieving stabilization of the local
controller. The principal contributions of this study encompass:

  1. 1.

Implementation of model-free data-driven controllers for the stabilization of
dynamic systems, executed in a sequential and localized fashion.

  2. 2.

Validation of the attraction boundary of sequential controllers based on the
Lyapunov stability criterion, employing Neural Networks as Lyapunov function
approximators derived from empirical data obtained from the system.

  3. 3.

Introduction of a tree-based methodology that constructs a hierarchical tree
of controllers to navigate from an initial state to a goal state.

  4. 4.

Introduction of a graph-based approach that establishes an interconnected
graph of controllers, enabling the traversal from any initial state to a goal
state within a bounded region of interest.

  5. 5.

Presentation of methodologies for integrating obstacle avoidance strategies
within the design of controller sequences.

The paper is structured as follows: In Section II, foundational principles of
deep RL controllers are introduced, along with background on Lyapunov
stability theory and steps for designing neural networks to approximate
Lyapunov functions. Section III establishes the groundwork for the proposed
algorithm, highlighting the pivotal role of nodes in deep RL-based controllers
and explaining the methodology for training and stabilizing these controllers.
Two approaches for interconnecting nodes, forming either a tree (Section IV)
or a graph (Section V) of interconnected controllers, are presented, enabling
the tracing of a trajectory to attain a goal state, with details of
implementation and evaluation of the algorithms on a two-dimensional input-
saturated dynamic system to demonstrate their effectiveness. Section VI
addresses addresses the main differences of each approach, and and provides a
comparison of both methods advantages and trade-offs. Finally, Section VII
concludes with a reflective summary of the research contributions.

##  II Background

Since the controllers synthesized in this work are Data-driven RL based
controllers, the need for neural based Lyapunov functions arise. When paired
together, this gives us a powerful tool to control and calculate the
applicable region without the need of explicit system dynamics, thus enabling
us to chain the controllers in sequence.

###  II-A Deep Reinforcement Learning

In the domain of control and reinforcement learning,

an agent is tasked with the challenge of selecting a sequence of actions to
maximize the cumulative reward. This challenge is formalized as a Markov
desision process (MDP) [18], defined by the tuple $(S,A,F,R)$. Here, $S$
represents the state space, $A$ denotes the action space, $R:S\times
A\to\mathbb{R}$ is the reward function, and $F:S\times A\to S$ describes the
state transition function, revealing the dynamics of the system. A policy,
denoted as $\pi_{\theta}:S\to P(A)$, is employed to make action selections at
each state within the MDP. Typically stochastic, the policy is characterized
by $\theta\in\mathbb{R}^{n}$, where $\theta$ is a vector encompassing $n$
parameters. The agent employs this policy to interact with the MDP, resulting
in a trajectory of states, actions, and rewards denoted as
$\tau_{1:T}=s_{0},a_{0},r_{0},\ldots,s_{T},a_{T},r_{T}:S\times
A\times\mathbb{R}$. The primary goal of the agent is to compute a policy that
maximizes the cumulative discounted reward across the trajectory obtained
through policy sampling. This goal is conceived as the performance objective

$J(\pi_{\theta})=\mathop{\mathbb{missing}}{E}\limits_{\tau\sim\pi_{\theta}}\left[{\sum\limits_{t=0}^{T}{{\gamma^{t}}R_{t}}}\right],$
(1)

where $\gamma$ is a discount factor often set close to 1. Policy methods, a
subset of RL algorithms, are specifically crafted to directly obtain the
optimal target policy $\pi^{*}$. This approach differs from value-based
methods [19, 20], which first require the estimation of value functions. While
value-based methods focus on approximating the value of states or state-action
pairs, policy methods directly aim to find the optimal policy that dictates
the agent’s actions in various states. This distinction in approach reflects a
fundamental divergence in the strategies employed by these two classes of RL
algorithms. The distinctive feature of policy-based methods lies in their
capacity for direct optimization through gradient ascent techniques, involving
the calculation of the gradient of the performance metric concerning the
policy parameters [21]

${\nabla_{\theta}}J({\pi_{\theta}})=\mathop{\mathbb{missing}}{E}\limits_{\tau\sim\pi_{\theta}}\left[{\sum\limits_{t=0}^{T}{\nabla_{\theta}}\log\pi_{\theta}(a_{t}|s_{t}){{\hat{A}}_{t}}}\right],$
(2)

where ${\hat{A}}_{t}={\hat{Q}}_{t}-{\hat{V}}_{t}$ is an estimator of the
advantage function at timestep $t$.

Within policy gradient methods, policy update involves making incremental
adjustments in the parameter space to optimize the objective function.
Nonetheless, modest changes in the parameter space may yield substantial
alterations in the policy distribution, potentially leading to worse results.
To address this challenge and ensure convergence, it becomes necessary to
intermittently constrain the adjustments in the parameter space. The Trust
Region Policy Optimization (TRPO) algorithm [22] addresses this concern by
introducing a penalty term based on the Kullback-Leibler (KL) divergence
constraint between the updated and the previous policy. Another approach,
implemented in the Proximal Policy Optimization (PPO) [23], maintains the
advantages of TRPO while proposing a more straightforward implementation
through a revised objective function. The ”Clipped Surrogate Objective” used
in PPO is

$L^{CLIP}(\theta)=\mathop{\mathbb{missing}}{E}\limits_{\tau\sim\pi_{\theta}}\left[\min(r_{t}(\theta){\hat{A}}_{t},\mathrm{clip}(r_{t}(\theta),1-\epsilon,1+\epsilon){\hat{A}}_{t})\right],$
(3)

where
$r_{t}{\theta}=\frac{\pi_{\theta}(a_{t}|s_{t})}{{\pi_{\theta}}_{\mathrm{old}}(a_{t}|s_{t})}$
is the probability ratio of an policy and $\epsilon$ is a hyperparamter (e.g.
$\epsilon=0.2$) that sets the bounds of the probability ratio. The employed
objective function systematically applies parameter update clipping,
selectively restraining updates only when they would degrade the probability
and disregarding changes that result in an enhancement of the objective
function.

In many practical decision-making problems, the states $s$ within the MDP are
characterized by high dimensionality, such as images captured by a camera or
raw sensor data from a robot, rendering conventional RL algorithms
ineffective. Deep RL algorithms integrate deep learning techniques to address
such complex MDPs, often representing the policy $\pi(a|s)$ or value functions
through neural networks. These approaches have demonstrated remarkable
efficacy, outperforming alternative methods across various tasks and achieving
performance levels comparable to or surpassing those of professional human
operators [24]. In this study, the PPO algorithm has been employed, utilizing
deep neural networks for both policy and value network approximations. PPO is
a popular model-free on-policy policy gradient method which is simpler to
implement compared to similar performing algorithms, still being sample-
efficient, showing robust convergence, generalizing to different tasks and
environments as well as being parallelizable and fast with regards to the
wall-clock time [25, 26, 27]. Additional details on the network architecture
are provided in Section III.

###  II-B Lyapunov Neural Network

A dynamic system of dimensionality $n$ is described by the differential
equation $\dot{x}=f_{u}(x)$, with an initial condition of $x(0)=x_{0}$. Here,
$f_{u}:\mathcal{D}\to\mathbb{R}^{n}$ represents a continuous vector field,
where $\mathcal{D}\in\mathbb{R}^{n}$ is an open set containing the origin,
defining the system’s state space. The feedback control is governed by a
continuous time-invariant function $u:\mathbb{R}^{n}\to\mathbb{R}^{m}$, which
is incorporated into the full dynamics expressed by $f_{u}$. According to the
stability criteria outlined in [28], an equilibrium point $x^{*}$ is
asymptotically stable if there exists a function
$V:\mathbb{R}^{n}\to\mathbb{R}$ that satisfies the following conditions:

$V(x^{*})=0;~{}\mathnormal{and}~{}\forall
x\in\mathcal{D}\setminus{x^{*}},V(x)>0~{}\mathnormal{and}~{}\nabla_{f_{u}}V(x)<0,$
(4)

then $V$ is called a Lyapunov function. The Lie derivative of a continuously
differentiable function $V$ over a vector field $f_{u}$ is defined as

$\nabla_{f_{u}}V(x)=\sum\limits_{i=1}^{n}{\frac{{\partial
V}}{{\partial{x_{i}}}}}\frac{{d{x_{i}}}}{{dt}}.$ (5)

The challenge in Lyapunov stability analysis resides in the identification of
a suitable Lyapunov function for a given system. This function must adhere to
the specific conditions to guarantee the stability of the system.

Various computational methods for identifying Lyapunov functions are surveyed
in [29]. When the system dynamics are polynomial or can be effectively
approximated by polynomials, an efficient approach involves computing a
Lyapunov function through Semi-Definite Program (SDP) [30]. The Lyapunov
function can be further constrained to a Sum-of-Squares (SOS) polynomial [31].
Other methodologies for computing RoAs encompass the maximization of a measure
of RoA volume along system trajectories [32]. Additionally, there are
sampling-based techniques that extend stability information from discrete
points to continuous regions [33, 34].

Recent research has concentrated on leveraging neural networks to acquire
Lyapunov functions for controllers. In [35], the emphasis is on discrete-time
polynomial systems, utilizing neural networks to learn the region of
attraction associated with a given controller. Other learning-based approaches
for Lyapunov function determination include [36, 37, 38, 39]. In [40], the
focus extends to simultaneously learning both the control and the Lyapunov
function, providing provable guarantees of stability in larger regions of
attraction. This approach directly addresses non-polynomial continuous
dynamical systems, does not presume the availability of control functions
other than an initial state, and employs generic feed-forward network
representations without manual design. In order to train a Lyapunov neural
network, unlike conventional back propagation there are no true labels for the
output values of the network. The work in [40] proposes the ”Lyapunov Risk”
loss function as

$\begin{gathered}L^{\text{Lyapunov}}(\theta)=\\\
\mathop{\mathbb{missing}}{E}\limits_{x\sim\mathcal{D}}\left[\max{(0,-V_{\theta}(x))+\max{(0,\nabla_{f_{u}}V_{\theta}(x))}+V_{\theta}^{2}(x^{*})}\right].\end{gathered}$
(6)

This loss function may be employed for the training of a neural network using
empirical data, facilitating the acquisition of a stabilizing Lyapunov
function. Consequently, the derived Lyapunov function can be applied in
conjunction with sampling-based methods to obtain the RoA of the controller.

###  II-C System Dynamics

Simulation experiments on a two-dimensional toy problem have proven very
useful for understanding the dynamics of the algorithm. The control problem is
formulated as a two-dimensional first-order system of the form

$\begin{gathered}{{\dot{x}}_{1}}={f_{1}}({x_{1}},{x_{2}})+{u_{1}}\hfill\\\
{{\dot{x}}_{2}}={f_{2}}({x_{1}},{x_{2}})+{u_{2}}\hfill,\end{gathered}$ (7)

where $x=[x_{1},x_{2}]^{T}$ is the state vector. The function
$f=[f_{1},f_{2}]^{T}$ is obtained by taking the gradient of a potential
function $h(x_{1},x_{2})$ as

${f_{i}}({x_{1}},{x_{2}})={\nabla_{{x_{i}}}}h({x_{1}},{x_{2}})=\frac{{\partial
h({x_{1}},{x_{2}})}}{{\partial{x_{i}}}}.$ (8)

The potential function $h$ is defined as a sum of Gaussians in the form

$h({x_{1}},{x_{2}})=\sum\limits_{i=1}^{3}{{\alpha_{i}}\exp\left({\frac{{{{\left({{x_{1}}-{\mu_{i1}}}\right)}^{2}}+{{\left({{x_{2}}-{\mu_{i2}}}\right)}^{2}}}}{{2{\sigma_{i}}^{2}}}}\right)},$
(9)

with parameters given in Table I. The choice of dynamics $f$ is arbitrary and
was chosen to keep the dimension and complexity of the system low to avoid the
curse of dimensionality inherent to RL. The resulting vector field $f$ and
potential function $h$ are shown in Figure 2. The reward function during
training is defined in the form

$R(x,u)=-0.01e_{x}^{T}e_{x}-0.01u^{T}u$ (10)

with $e_{x}=x-x^{*}$ and $u=[u_{1},u_{2}]^{T}$. The control inputs are
saturated to verify $u_{i}\in[-0.5,0.5]$ and the states are normalized from
the original range $[-5,5]^{2}$ to $[-1,1]^{2}$.

TABLE I: Parameters of the potential function $h$ described in (9) $i$ | $\alpha_{i}$ | $\mu_{1}i$ | $\mu_{1}i$ | $\sigma_{i}$
---|---|---|---|---
1 | -0.1 | -1.4 | 2.5 | 1.8
2 | 0.2 | 1.3 | 2.2 | 1.5
3 | 0.3 | -3.4 | -2.5 | 2

(a)  (b)

Figure 2: Dynamics used for simulating the proposed controller. The potential
function $h$ is represented on the left side and its gradient that describes
the vector field $f$ is depicted on the right side for the range
$x_{1}\in[-5,5]$, $x_{2}\in[-5,5]$.

##  III Sequential RL controller with Neural Lyapunov certificate

In this study, we introduce two sequential control methodologies. The initial
approach, denoted as the Tree-Structured PPO Controller (TPC), employs a
hierarchical structure of interconnected controllers to guide the system from
an initial state to a predefined goal state. Within this framework, each
controller possesses a distinct equilibrium state and RoA, represented as
nodes in a tree structure. The system progresses sequentially through these
nodes until it reaches the desired goal state, treating the intermediate
states as milestones or sub-goals. However, a limitation of the TPC arises
when there is a change in the goal state, rendering the previously learned
controller nodes obsolete. Consequently, the design process requires
repetition, incurring computational expenses. Hence, the TPC can be regarded
as a ”point-to-point” controller, and its adaptability to changes in the goal
state may pose challenges.

To overcome this constraint, we also introduce an alternative approach known
as the Graph-Structured PPO Controller (GPC). In this graph-based method,
local controllers populate the entire valued state space, irrespective of the
initial and goal states. When a target goal state is selected, only a single
controller at that specific point requires training. The graph of controllers
can efficiently formulate a trajectory connecting any initial condition to the
goal state, thereby meeting the control requirements. As a result, the GPC is
characterized as a ”space-to-space” controller, offering advantages in
adaptability compared to the ”point-to-point” nature of the TPC.

In this section, we establish the foundational aspects of controller design
for a specified goal state, whether intermediate or final. The controller
design process remains consistent regardless of the chosen approach (TPC or
GPC). After identifying a suitable point as a node within the network, the
initial step involves designing and training a controller based on RL. This
controller aims to achieve local stabilization in the vicinity of the selected
node. For the implementation and evaluation of the proposed algorithms in this
study, we utilize the Stable-Baselines3 library (version 2.1.0) [41], a widely
employed reinforcement learning library. The PPO controller’s hyperparameters
employed in this study are detailed in Table II.

TABLE II: PPO Algorithm Hyperparameters Hyperparameter | Value
---|---
Policy network architecture | n - 128 - 64 - m
Value network architecture | n - 128 - 64 - 1
Activation function | LeakyReLU
Learning rate | 3$\times$10-4
Discount Factor ($\gamma$) | 0.99
Number of Epochs | 10
Batch Size | 256
Clip Parameter ($\epsilon$) | 0.2
Value Function Coefficient | 0.5
Number of parallel environments | 8
Train timesteps | 106

In the training phase of the controller, initial values are deliberately
chosen at random within an interval proximate to the selected equilibrium of
the controller. This intentional selection is aimed at ensuring the
controller’s robust learning capability in stabilizing initial conditions
within its local vicinity. This step is crucial, setting the foundation for
the subsequent computation of quantitative attraction certificates.

After the controller, represented by the RL agent, undergoes training, it
becomes crucial to identify a region within which the controller is effective
and can reliably stabilize any initial condition. Therefore, determining its
RoA becomes essential. In this study, the Lyapunov stability criterion is
employed to assess the stability of the designed controller. Neural networks
are trained to synthesize Control Lyapunov functions, acting as a form of
function approximation. The inputs to this network include the $n$-dimensional
states of the dynamic system, and the network outputs the computed Lyapunov
value for the given state ($V=V_{\theta}(x)$). By leveraging the previously
defined Lyapunov Risk Loss function, this network can be effectively trained.
Note that the Lie derivative term of the Lyapunov risk is approximated by

$\nabla_{f_{u}}V_{\theta}(x)\approx\sum\limits_{i=1}^{n}\frac{V_{\theta}(x_{i}+h)-V_{\theta}(x_{i})}{h}\frac{{d{x_{i}}}}{{dt}},$
(11)

the parameter $h=10^{-3}$ is introduced as a minute constant for the purpose
of approximating numerical derivatives. Throughout the training process, we
uniformly sample 103 initial conditions in close proximity to the controller’s
goal, thereby acquiring a training set comprising state-space points. The deep
learning model employed for the Lyapunov function in this study is implemented
using PyTorch (version 2.0.1) [42]. The hyperparameters of the network are
detailed in Table III.

TABLE III: Lyapunov Neural Network Hyperparameters Hyperparameter | Value
---|---
Network architecture | n - 100 - 100 - 1
Activation Functions | ReLU - ReLU - GELU
Optimizer | Adam
Learning Rate | 10-2
Batch Size | 32
Epochs | 50

After obtaining the Lyapunov function, it can be utilized to compute the RoA.
The RoA estimate is represented as a ball around each controller,
characterized by a specific radius $\eta$. To determine the maximum $\eta$ for
each controller, 103 uniformly distributed initial states are sampled in
increasing proximity (up to an upper bound $\eta_{\text{ub}}$) to the
equilibrium. These states are then evaluated using the Lyapunov network, and
the Lyapunov stability criterion ((4)) is verified. If all sampled points
satisfy the criteria, the sampling radius is incrementally increased. This
iterative process continues until counterexamples are identified in the
sampled points or until an upper bound is reached. The steps involved in
obtaining individual controllers for each selected node center are summarized
in Algorithm 1.

Algorithm 1 Reinforcement Learning-Based Controller Synthesis for Individual
Nodes

1:ppo_params, lyapunov_params, $\eta_{\text{ub}}$, $\delta\eta$

2:function NodeController($x_{k}$)

3: env $\leftarrow$ MDP with $x_{k}$ as target state $x^{*}$

4: $\pi_{\theta}\leftarrow\text{PPO}(\text{ppo\\_params})$

5: Train $\pi_{\theta}$

6: $X_{\text{train}}\leftarrow\text{sample }10^{4}\text{ points near }x_{k}$

7: $V_{\theta}\leftarrow\text{NN}(\text{lyapunov\\_params})$

8: Train $V_{\theta}$ with loss function (6)

9: $\eta\leftarrow 0$

10: while $\eta<\eta_{\text{ub}}$ do

11: $\eta\leftarrow\eta+\delta\eta$

12: $X_{\text{test}}\leftarrow\text{sample }10^{3}\text{ in dist.
}[\eta,\eta+\delta\eta]$ from $x_{k}$

13: Lyapunov_criteria $\leftarrow$ evaluate (4) on $X_{\text{test}}$ with
$V_{\theta}$

14: if Lyapunov_criteria not satisfied then

15: break

16: return $\pi_{\theta k}$, $\eta_{k}$

##  IV Tree-Structured PPO Controller

This section provides an overview of the foundations of the tree-based
algorithm. The controller leverages the PPO controller and the previously
outlined stabilization method to construct a tree of interconnected
controllers, facilitating reaching a specified goal from a given initial
state. Following the introduction of the algorithm’s structure, the subsequent
presentation and discussion will focus on experimental results conducted on a
two-dimensional dynamic system, shedding light on its effectiveness and
performance.

###  IV-A Design of Tree-Structured PPO Controller

The proposed algorithm begins by formulating a controller at the goal state
$x_{\text{goal}}$. Following a methodology akin to randomized planning
algorithms, the algorithm constructs a controller tree $\mathbf{T}$ through
random sampling within a defined region of the state space
$\mathcal{R}_{\text{bound}}$. The existing tree of controllers is then
expanded towards a randomly selected sample point $x_{k}$. Ensuring the
integrity of the chosen node is crucial; it must lie within the union of all
preceding controller RoAs, denoted as $\mathcal{R}_{k}$. This precaution is
taken to ensure that, after achieving stability at the node center, there
exists a node capable of progressing the trajectory toward the desired goal
state.

Another condition is imposed to prevent the chosen center point for a node
from being in close proximity to preceding node centers. This condition is
essential to guarantee the creation of sparse controllers that can effectively
cover the state space, thereby aiding in the identification of a suitable
trajectory. Let $\mathcal{C}_{k}$ denote the sets of all previous node
centers. A randomly sampled point $x_{k}$ is deemed an acceptable candidate
for the next node center only if it meets the condition

$\begin{gathered}\left(x_{k}\in\mathcal{R}_{\text{bound}}\right)\,\land\,\left(\exists
x_{i}\in\mathcal{C}_{k},\,{\left\|{x_{i}-x_{k}}\right\|_{2}}\geqslant\rho\right)\\\
\,\land\,\left(\forall
x_{\text{obstacle}}\in\mathcal{O},\,{\left\|{x_{k}-x_{\text{obstacle}}}\right\|_{2}}\geqslant\alpha\right),\end{gathered}$
(12)

where $\eta_{ub}/2<\rho<\eta_{lb}$ is selected such that the controllers
construct a sparse tree. The final constraint 12 is relevant in situations
where obstacle avoidance is a desired objective. In such instances, the
candidate point must adhere to the condition that it remains at a distance no
less than the clearance parameter $\alpha>[\eta_{ub}/2+r_{obs}]$ from the
center of all obstacles denoted as $x_{\text{obstacle}}$.

Upon adding a new ”node” to the tree, we learn a stabilizing controller
specifically for that node. The RoA for this controller is estimated using the
methodologies discussed earlier. It is crucial to confirm that the computed
RoA surpasses the specified lower bound $\eta_{\text{lb}}$. This verification
ensures that the formulated controller can effectively cover a significant
region within the state space. If the RoA falls short of this criterion, the
controller is rejected, and no further points are sampled in the vicinity of
the previously invalidated point.

In this phase, we determine the parent node for the selected point. Among all
nearby nodes that encompass the point $x_{k}$ within their RoA, we identify
the node closest to the point and set it as the parent node $i$. These
computations are performed backward, initiating from the goal and extending
into the state space until reaching the starting state. As a result, the
backward tree transforms into a complex network of local controllers with the
capability to attract initial conditions and guide them toward the goal, all
while providing formal certificates of stability for the nonlinear system. The
algorithm concludes when the starting state is enclosed within the constructed
trees region of attraction $\mathcal{R}_{k}$. The steps involved in designing
the TPC are summarized in Algorithm 2.

Algorithm 2 Sequential Control Algorithm Based on a Tree of Connected
Controllers (TPC)

1:$x_{\text{start}},x_{\text{goal}},\eta_{\text{lb}}$

2:$\pi_{\theta g}$, $\eta_{g}\leftarrow$ NodeController($x_{\text{goal}}$)

3:$\mathbf{T}\leftarrow\\{(x_{\text{goal}},\pi_{\theta
g},\eta_{g},\text{NULL})\\}$

4:for $k=1$ to $K$ do

5: $x_{k}\leftarrow\text{random sample}$

6: if $x_{k}$ satisfies (12) then

7: $\pi_{\theta k}$, $\eta_{k}\leftarrow$ NodeController($x_{k}$)

8: if $\eta_{k}>\eta_{lb}$ then

9: i $\leftarrow$ pointer to parent node in $\mathbf{T}$ containing $x_{k}$

10: $\mathbf{T}\leftarrow\mathbf{T}\cup\\{(x_{k},\pi_{\theta
k},\eta_{k},i)\\}$

11: if $x_{\text{start}}\in\mathcal{R}_{k}$ then

12: break

###  IV-B Result of Tree-Structured PPO Controller

In the initial simulation of the proposed algorithm, we tested the tree-
structured controller. The parameters used were $x_{\text{goal}}=[4,4]^{T}$
and $x_{\text{start}}=[-4,-4]^{T}$. The task assigned to the TPC controller
was to compute a tree of sequential controllers aimed at reaching the goal
state from the initial starting point. The completion of this task resulted in
a tree comprising a total of 23 nodes. During the training of all node
controllers (PPO agents), the resulting reward values are depicted in Figure
3a. These values represent an average across all computed nodes of the tree.
Notably, the rewards show a gradual saturation at -5, starting from an initial
reward of -15. Following the computation of controllers, a Lyapunov neural
network was trained for each individual node. This network is intended for use
in calculating the RoA for each node. The loss over 20 epochs of training the
network is visualized in Figure 3b.

(a)

(b)

Figure 3: (a) Average cumulative episode reward observed during the training
of the RL agent for the Tree-Structured PPO Controller. (b) Lyapunov Loss
trends throughout the training of the Lyapunov neural networks for computing
the region of attraction for each RL controller. The black line represents the
average among the 23 controllers, while the shaded region illustrates the
maximum and minimum bounds of the computed Rewards and Loss respectively.

The dynamics of the proposed tree-structured algorithm are depicted in Figure
4. The algorithm initiates at the goal state, formulating and stabilizing
local controllers while branching the tree within the bounded state space
region $\mathcal{R}_{\text{bound}}=[-5,5]^{2}$. With each step, the search
region expands until it encompasses the desired initial state. Snapshots of
the algorithm in action at 5 and 15 tree nodes are presented in Figure 4a and
Figure 4b, respectively. By the time the tree comprises 23 nodes, the entire
area covered by the tree $\mathcal{R}_{k}$ includes the starting state. In
Figure 4c, the path connecting the final node to the first calculated node is
highlighted, and all irrelevant branches are ”pruned,” resulting in a path
featuring 10 nodes. The system is capable of traversing a trajectory from the
nodes in sequence until reaching the globally desired equilibrium at
$x_{\text{goal}}$. Controller switching occurs when the system approaches the
equilibrium of a controller node, specifically when
$\left|{x(t)-x_{k}}\right|_{2}<0.01$. Finally, the trajectory of the system
following the nodes in the tree is illustrated in Figure 4d.

(a)

(b)

(c)

(d)

Figure 4: The Tree-Structured PPO Controller applied to the dynamic system
defined in (7). (a) Snapshot of the algorithm with 5 nodes. (b) Snapshot with
15 nodes. (c) Initial state reaching the covered space of the tree at 23
nodes, with irrelevant branches pruned. (d) Dynamic system trajectory
following the constructed controller tree. Red cross: goal state
$x_{\text{goal}}=[4,4]^{T}$; Green cross: starting state
$x_{\text{start}}=[-4,-4]^{T}$; Black square: bounded region
$\mathcal{R}_{\text{bound}}$; Blue dots: controller node center locations
$x_{k}$; Blue shaded region: individual node regions of attraction; Blue
dashed shaded region: overall region of attraction of the tree
($\mathcal{R}_{k}$); Black lines: connections (edges) between tree nodes;
Green line: system trajectory $x(t)$.

To showcase the algorithm’s obstacle avoidance capability, an additional
simulation is conducted with an obstacle present in the state space, as
depicted in Figure 5. The obstacle, centered at $x_{obstacle}=[2,0]^{T}$ with
a radius of 1, is taken into consideration. A clearance of $\alpha=2.5$ is set
to ensure the avoidance of node selection in close proximity to the obstacle.
Upon simulating the TPC algorithm in this obstacle-laden scenario, a tree
consisting of 18 nodes is generated. Following the pruning of irrelevant
branches, the final path between the start and goal states comprises 10 nodes,
as illustrated in Figure 5c. The system trajectory utilizing the controller is
visualized in Figure 5d.

(a)

(b)

(c)

(d)

Figure 5: The Tree-Structured PPO Controller applied to the dynamic system
defined in (7) with obstacle with radius 1 at $x_{\text{obstacle}}=[2,0]^{T}$.
(a) Snapshot of the algorithm with 5 nodes. (b) Snapshot with 11 nodes. (c)
Initial state reaching the covered space of the tree at 18 nodes, with
irrelevant branches pruned. (d) Dynamic system trajectory following the
constructed controller tree. Red cross: goal state
$x_{\text{goal}}=[4,4]^{T}$; Green cross: starting state
$x_{\text{start}}=[-4,-4]^{T}$; Black square: bounded region
$\mathcal{R}_{\text{bound}}$; Red circle: obstacle; Black dashed circle:
obstacle clearance; Blue dots: controller node center locations $x_{k}$; Blue
shaded region: individual node regions of attraction; Blue dashed shaded
region: overall region of attraction of the tree ($\mathcal{R}_{k}$); Black
lines: connections (edges) between tree nodes; Green line: system trajectory
$x(t)$.

##  V Graph-Structured PPO Controller

This section provides an overview of the foundations of the graph-based
algorithm. The controller leverages the PPO controller and the previously
outlined stabilization method to construct a graph of interconnected
controllers, facilitating goals from any initial states in the region of
interest. Following the introduction of the algorithm’s structure, the
subsequent presentation and discussion will focus on experimental results
conducted on a two-dimensional dynamic system, shedding light on its
effectiveness and performance.

###  V-A Design of Graph-Structured PPO Controller

This approach involves constructing a connected graph of controllers
$\mathbf{G}$ within a delimited region $\mathcal{R}_{\text{bound}}$ in the
state space. Once this interconnected graph is established, it facilitates the
generation of trajectories from any given initial condition to a desired goal
state. Similar to the TPC method, this technique entails the random selection
of points within the state space and the design of controllers at these
locations. The criteria for accepting a sampled point $x_{k}$ as a new node
candidate for the graph are identical to the constraints outlined in the tree-
based algorithm (12). The main departure from the previous algorithm lies in
the initialization of the graph. In contrast to the earlier approach where the
graph started at the goal state and expanded towards the initial state, the
current method evolves to create a sparse network of connected controllers
spanning the specified bounded region of the state space, regardless of the
desired initial and goal states. The algorithm concludes when no valid $x_{k}$
can be identified, signaling that the graph effectively covers the entire
designated region ($\mathcal{R}_{bound}\subseteq\mathcal{R}_{k}$).

After the creation of individual controllers, only one controller needs to be
generated at the desired goal state. Subsequently, a connected graph is
established, where each node is linked to all controller nodes containing the
node within their RoA, referred to as the valid nodes set $\mathbf{V}$. It is
essential to note that the edges are directional, reflecting the variation in
$\eta$ size within their respective RoA. In brief, if a controller center is
within another controller’s RoA, the reverse may not necessarily be true. To
navigate the graph from any initial state to the goal state controller,
shortest path finding algorithms can be employed. In this work, Dijkstra’s
algorithm [4] is utilized to determine the optimal path between controller
nodes in the final graph. The steps involved in designing the GPC are
succinctly outlined in Algorithm 3.

Algorithm 3 Sequential Control Algorithm Based on a Graph of Connected
Controllers (GPC)

1:$x_{\text{start}},x_{\text{goal}},\eta_{\text{lb}},\mathcal{R}_{bound}$

2:for $k=1$ to $K$ do

3: $x_{k}\leftarrow\text{random sample}$

4: if $x_{k}$ satisfies (12) then

5: $\pi_{\theta k}$, $\eta_{k}\leftarrow$ NodeController($x_{k}$)

6: if $\eta_{k}>\eta_{lb}$ then

7: $\mathbf{G}\leftarrow\mathbf{G}\cup\\{(x_{k},\pi_{\theta k},\eta_{k})\\}$

8: if $\mathcal{R}_{bound}\subseteq\mathcal{R}_{k}$ then

9: break

10:$\mathbf{G}\leftarrow\mathbf{G}\cup\\{(x_{\text{goal}},\pi_{\theta
g},\eta_{g})\\}$

11:$\mathbf{V}$ $\leftarrow$ pointers to valid nodes in $\mathbf{G}$
containing each $x_{k}$

12:Trajectory $\leftarrow$
Dijkstra($x_{\text{start}},x_{\text{goal}},\mathbf{G},\mathbf{V}$)

###  V-B Result of Graph-Structured PPO Controller

The results of simulating the proposed GPC controller are presented in this
section. As previously stated, this controller is ”space-to-space”, so there
is no need of determining the starting and goal states in the initial stage of
controller design. Individual nodes are added in succession, spanning the
entirety of the bounded region after 37 nodes are added. During the training
of all node controllers (PPO agents), the resulting reward values are depicted
in Figure 6a. These values represent an average across all computed nodes of
the tree. Similar to the previous tree based approach, the rewards again show
a gradual saturation at -5, starting from an initial reward of -15. The
Lyapunov network loss over 20 epochs of training the network is visualized in
Figure 6b.

(a)

(b)

Figure 6: (a) Average cumulative episode reward observed during the training
of the RL agent for the Graph-Structured PPO Controller. (b) Lyapunov Loss
trends throughout the training of the Lyapunov neural networks for computing
the region of attraction for each RL controller. The black line represents the
average among the 37 controllers, while the shaded region illustrates the
maximum and minimum bounds of the computed Rewards and Loss respectively.

The algorithm’s operation is illustrated in Figure 7. Initially, it spans the
space, as depicted in Figure 7a, where the algorithm is shown with 15 nodes.
After the design reaches 37 nodes, filling the entire region of interest, this
phase of the algorithm concludes. Subsequently, the graph is generated by
connecting all possible adjacent nodes reachable from each node, as depicted
in Figure 7b. Notably, due to discrepancies in the sizes of RoA for different
nodes, not all connections are bidirectional. This becomes more apparent in a
later example involving the presence of an obstacle. After constructing the
GPC, the first example involves selecting a goal state at the point
$x_{\text{goal}}^{(1)}=[4,4]^{T}$ and three initial states at
$x_{\text{start}}^{(1a)}=[-4,-4]^{T}$,
$x_{\text{start}}^{(1b)}=[-3.5,2.25]^{T}$, and
$x_{\text{start}}^{(1c)}=[4.5,-3]^{T}$. Once each initial condition’s starting
node is determined, the Dijkstra algorithm calculates the shortest path from
that node to the desired goal node. The dynamic system then follows the
computed path between sequential controllers, similar to the TPC method
(Figure 7c).

To showcase the algorithm’s ability to adapt to changes in goal or initial
states, the states are modified to $x_{\text{goal}}^{(2)}=[-0.75,-1]^{T}$, and
three new initial states are chosen: $x_{\text{start}}^{(2a)}=[3.75,4]^{T}$,
$x_{\text{start}}^{(2b)}=[3,-3.75]^{T}$, and
$x_{\text{start}}^{(2c)}=[-4,-3.5]^{T}$, as illustrated in Figure 7d.

(a)

(b)

(c)

(d)

Figure 7: The Graph-Structured PPO Controller applied to the dynamic system
defined in (7). (a) Snapshot of the algorithm with 15 nodes. (b) Final graph
with the total 37 interconnected nodes and edges. (c) Experiment with
$x_{\text{goal}}^{(1)}=[4,4]^{T}$ and three initial states at
$x_{\text{start}}^{(1a)}=[-4,-4]^{T}$,
$x_{\text{start}}^{(1b)}=[-3.5,2.25]^{T}$, and
$x_{\text{start}}^{(1c)}=[4.5,-3]^{T}$. The sequence of controllers reaching
the goal is found using Dijkstra algorithm and is highlighted. (d) Experiment
with $x_{\text{goal}}^{(2)}=[-0.75,-1]^{T}$ and three initial states at
$x_{\text{start}}^{(2a)}=[3.75,4]^{T}$,
$x_{\text{start}}^{(2b)}=[3,-3.75]^{T}$, and
$x_{\text{start}}^{(2c)}=[-4,-3.5]^{T}$. Red cross: goal state
$x_{\text{goal}}$; Green/Yellow/Cyan cross: starting states
$x_{\text{start}}^{i}$; Black square: bounded region
$\mathcal{R}_{\text{bound}}$; Blue dots: controller node center locations
$x_{k}$; Blue shaded region: individual node regions of attraction; Blue
dashed shaded region: overall region of attraction of the graph
($\mathcal{R}_{k}$); Black lines: connections (edges) between graph nodes;
Green/Yellow/Cyan line: system trajectories $x^{i}(t)$.

To showcase the capabilities of the GPC controller in environments with
obstacles, a test is conducted similar to the previous section. An obstacle is
introduced at $x_{obstacle}=[2,0]^{T}$ with a radius of 1, and the clearance
parameter is set to $\alpha=2.5$. The completed graph, after adding 37 nodes,
is depicted in Figure 8b. Notably, many connections between nodes are
unidirectional, but a guarantee exists that there is a path between every pair
of nodes in the graph. The system trajectory, navigating from three initial
states at $x_{\text{start}}^{(1a)}=[-4,-4]^{T}$,
$x_{\text{start}}^{(1b)}=[-3.5,2.25]^{T}$, and
$x_{\text{start}}^{(1c)}=[4.5,-3]^{T}$ to the goal state
$x_{\text{goal}}^{(1)}=[4,4]^{T}$, is illustrated in Figure 8c. Similarly, the
trajectory from $x_{\text{start}}^{(2a)}=[3.75,4]^{T}$,
$x_{\text{start}}^{(2b)}=[3,-3.75]^{T}$, and
$x_{\text{start}}^{(2c)}=[-4,-3.5]^{T}$ to
$x_{\text{goal}}^{(2)}=[-0.75,-1]^{T}$ is shown in Figure 8d.

(a)

(b)

(c)

(d)

Figure 8: The Graph-Structured PPO Controller applied to the dynamic system
defined in (7) with obstacle with radius 1 at $x_{\text{obstacle}}=[2,0]^{T}$.
. (a) Snapshot of the algorithm with 15 nodes. (b) Final graph with the total
37 interconnected nodes and edges. (c) Experiment with
$x_{\text{goal}}^{(1)}=[4,4]^{T}$ and three initial states at
$x_{\text{start}}^{(1a)}=[-4,-4]^{T}$,
$x_{\text{start}}^{(1b)}=[-3.5,2.25]^{T}$, and
$x_{\text{start}}^{(1c)}=[4.5,-3]^{T}$. The sequence of controllers reaching
the goal is found using Dijkstra algorithm and is highlighted. (d) Experiment
with $x_{\text{goal}}^{(2)}=[-0.75,-1]^{T}$ and three initial states at
$x_{\text{start}}^{(2a)}=[3.75,4]^{T}$,
$x_{\text{start}}^{(2b)}=[3,-3.75]^{T}$, and
$x_{\text{start}}^{(2c)}=[-4,-3.5]^{T}$. Red cross: goal state
$x_{\text{goal}}$; Red circle: obstacle; Black dashed circle: obstacle
clearance; Green/Yellow/Cyan cross: starting states $x_{\text{start}}^{i}$;
Black square: bounded region $\mathcal{R}_{\text{bound}}$; Blue dots:
controller node center locations $x_{k}$; Blue shaded region: individual node
regions of attraction; Blue dashed shaded region: overall region of attraction
of the graph ($\mathcal{R}_{k}$); Black lines: connections (edges) between
graph nodes; Green/Yellow/Cyan line: system trajectories $x^{i}(t)$.

##  VI Tree-Structured vs. Graph-Structured Controller

A comprehensive comparison of the two proposed methods in this study is
outlined in Table IV. Addressing the question of ”When should each method be
used?” is pivotal. The primary distinction between the two methods lies in the
inherent structure of the controllers and the interconnection of nodes. The
TPC adopts a Tree structure, while the GPC employs a graph structure. Both
controllers consist of nodes with PPO controllers, and the design, training,
and stabilization of these controllers follow a similar approach. As
previously discussed, the key divergence in the learning process between the
controllers is the criteria for initiation and termination. In the case of
TPC, the process initiates by designing node controllers from the goal state,
branching out into the bounded state space until encompassing the start state.
On the other hand, GPC adds nodes to the graph regardless of the goal and
initial states. Its objective is to span the entire desired region with
locally stable controllers. Once the graph is constructed, a trajectory can be
defined, traversing sequentially through the controllers for any desired start
and goal state. Nodes in the tree structure exhibit a parent-child
relationship, where each node (excluding the root node or goal) has precisely
one parent. In contrast, the directed graph of GPC implies that each edge has
a direction, and connections between nodes can be bidirectional. Furthermore,
the graph is cyclic, containing cycles, in contrast to the acyclic nature of
the tree structure. Both methods choose node positions in a strategic manner
outlined before as to have the capability for obstacle avoidance.

The primary distinction lies in the computational cost associated with each
controller. As evidenced by the results, the tree controller is capable of
identifying a valid solution with fewer nodes. In the scenario without an
obstacle, the tree controller synthesized only 23 nodes, as opposed to the
graph, which required 37 nodes. Likewise, when an obstacle is present, the
tree controller synthesized 18 nodes compared to the graph’s 37 nodes. This
underscores the advantage of the TPC in rapidly finding solutions when a
single valid solution is crucial. Conversely, the GPC excels in situations
where the initial state may vary or remain unknown at the onset of
calculations. As mentioned earlier, once a tree is constructed, the tree
controller can only manage the initially defined state or a limited set of
initial conditions falling within the tree’s region of attraction. In
contrast, the graph, designed with nodes spanning the entire region of
interest, enables the controller to stabilize the system for any chosen
initial condition. A similar scenario arises when altering the goal state. The
tree controller necessitates a complete reconstruction from scratch, whereas
the graph controller simply adds a single node for the new goal state and
connects it to the existing graph.

A crucial aspect to consider is the sequence of controller switching. Trees
exhibit a hierarchical structure, featuring a designated root node (goal
state) that serves as the starting point for accessing all other nodes. Given
that each node has only one parent, the sequence of nodes leading from the
initial state to the goal state is clearly defined. In contrast, graphs lack
this inherent hierarchy, often possessing multiple paths between any two
nodes. To address this complexity, Dijkstra’s algorithm was employed to
determine the optimal node sequence between two states in the graph.

TABLE IV: Comparison of Tree-Structured PPO Controller and Graph-Structured PPO Controller Attribute | Tree-Structured PPO Controller | Graph-Structured PPO Controller
---|---|---
Controller structure | Tree | Graph
Node controllers | PPO | PPO
Directionality | No | Bidirectional
Obstacle avoidance | Yes | Yes
Upfront cost | Low | High
Initial-Goal states | (1 initial state) to (1 goal state) | (All initial states) to (1 goal state)
Cost of changing goal state | Whole tree must be reconstructed | Only 1 node must be added to the graph
Cost of changing initial state | Whole tree must be reconstructed | None
Pathfinding Algorithm | None | Dijkstra

##  VII Conclusion

This paper introduces a novel sequential control algorithm employing localized
PPO agents as nodes. To assess theRoA, Lyapunov stability criteria are
employed, with a neural network trained at each node to determine a locally
valid Lyapunov function. Notably, this approach eliminates the necessity for
explicit dynamics models, relying instead on data-driven techniques for
acquiring the node controller and stabilization. The paper proposes two
distinct algorithms for connecting node controllers to establish a sequential
controller. Firstly, a tree-structured method is presented for achieving
”point-to-point” control, facilitating motion control from an initial state to
a desired goal state. Additionally, a graph-structured approach is outlined
for scenarios requiring ”space-to-space” control. While the latter method
incurs an upfront computational cost, it offers the advantage of reusing the
structured graph in cases of changes in the desired goal state or initial
conditions. Both algorithms are equipped to handle obstacle avoidance
scenarios. This capability ensures that the algorithms can identify a tree (or
graph) of interconnected controllers that navigate around obstacles safely.
The effectiveness of the proposed controllers is demonstrated through
application to a two-dimensional first-order system. Results indicate the
algorithm’s ability to design a sequence of connected Reinforcement Learning
RL-based controllers, effectively addressing the control problem. However,
certain areas warrant further exploration. Future research avenues include the
incorporation of path-finding algorithms to optimize node selection,
particularly in higher-dimensional systems. Additionally, it is crucial to
evaluate the controller’s performance through experimentation on a test
platform. This would allow for a comprehensive examination of the control
framework in real-world operational scenarios, considering interactions and
noise dynamics between the robotic system and its environment.

## References

  * [1] R. R. Burridge, A. A. Rizzi, and D. E. Koditschek, “Sequential composition of dynamically dexterous robot behaviors,” _The International Journal of Robotics Research_ , vol. 18, no. 6, pp. 534–555, 1999.
  * [2] M. Mason, “The mechanics of manipulation,” in _Proceedings. 1985 IEEE International Conference on Robotics and Automation_ , vol. 2, 1985, pp. 544–548.
  * [3] P. E. Hart, N. J. Nilsson, and B. Raphael, “A formal basis for the heuristic determination of minimum cost paths,” _IEEE transactions on Systems Science and Cybernetics_ , vol. 4, no. 2, pp. 100–107, 1968.
  * [4] E. W. Dijkstra, “A note on two problems in connexion with graphs.” _Numerische Mathematik_ , vol. 1, pp. 269–271, 1959. [Online]. Available: http://eudml.org/doc/131436
  * [5] L. Kavraki and J.-C. Latombe, “Randomized preprocessing of configuration for fast path planning,” in _Proceedings of the 1994 IEEE International Conference on Robotics and Automation_. IEEE, 1994, pp. 2138–2145.
  * [6] J. Barraquand and J.-C. Latombe, “Nonholonomic multibody mobile robots: Controllability and motion planning in the presence of obstacles,” _Algorithmica_ , vol. 10, no. 2-4, pp. 121–155, 1993.
  * [7] S. M. LaValle, J. J. Kuffner, B. Donald _et al._ , “Rapidly-exploring random trees: Progress and prospects,” _Algorithmic and computational robotics: new directions_ , vol. 5, pp. 293–308, 2001.
  * [8] S. Karaman and E. Frazzoli, “Incremental sampling-based algorithms for optimal motion planning,” _Robotics Science and Systems VI_ , vol. 104, no. 2, pp. 267–274, 2010.
  * [9] F. Islam, J. Nasir, U. Malik, Y. Ayaz, and O. Hasan, “RRT*-smart: Rapid convergence implementation of RRT* towards optimal solution,” in _2012 IEEE international conference on mechatronics and automation_. IEEE, 2012, pp. 1651–1656.
  * [10] M. Brunner, B. Brüggemann, and D. Schulz, “Hierarchical rough terrain motion planning using an optimal sampling-based method,” in _2013 IEEE International Conference on Robotics and Automation_. IEEE, 2013, pp. 5539–5544.
  * [11] A. Perez, R. Platt, G. Konidaris, L. Kaelbling, and T. Lozano-Perez, “LQR-RRT*: Optimal sampling-based motion planning with automatically derived extension heuristics,” in _2012 IEEE International Conference on Robotics and Automation_. IEEE, 2012, pp. 2537–2542.
  * [12] L. Janson, E. Schmerling, A. Clark, and M. Pavone, “Fast marching tree: A fast marching sampling-based method for optimal motion planning in many dimensions,” _The International journal of robotics research_ , vol. 34, no. 7, pp. 883–921, 2015.
  * [13] L. E. Kavraki, P. Svestka, J.-C. Latombe, and M. H. Overmars, “Probabilistic roadmaps for path planning in high-dimensional configuration spaces,” _IEEE transactions on Robotics and Automation_ , vol. 12, no. 4, pp. 566–580, 1996.
  * [14] A. M. Ladd and L. E. Kavraki, “Measure theoretic analysis of probabilistic path planning,” _IEEE Transactions on Robotics and Automation_ , vol. 20, no. 2, pp. 229–242, 2004.
  * [15] C. Atkeson and B. Stephens, “Random sampling of states in dynamic programming,” _Advances in neural information processing systems_ , vol. 20, 2007.
  * [16] R. Goebel, C. Prieur, and A. R. Teel, “Smooth patchy control lyapunov functions,” _Automatica_ , vol. 45, no. 3, pp. 675–683, 2009.
  * [17] R. Tedrake, I. R. Manchester, M. Tobenkin, and J. W. Roberts, “Lqr-trees: Feedback motion planning via sums-of-squares verification,” _The International Journal of Robotics Research_ , vol. 29, no. 8, pp. 1038–1052, 2010\.
  * [18] R. S. Sutton and A. G. Barto, _Reinforcement learning: An introduction_. MIT press, 2018.
  * [19] V. Mnih, K. Kavukcuoglu, D. Silver, A. A. Rusu, J. Veness, M. G. Bellemare, A. Graves, M. Riedmiller, A. K. Fidjeland, G. Ostrovski _et al._ , “Human-level control through deep reinforcement learning,” _nature_ , vol. 518, no. 7540, pp. 529–533, 2015.
  * [20] T. P. Lillicrap, J. J. Hunt, A. Pritzel, N. Heess, T. Erez, Y. Tassa, D. Silver, and D. Wierstra, “Continuous control with deep reinforcement learning,” _arXiv preprint arXiv:1509.02971_ , 2015.
  * [21] R. S. Sutton, D. McAllester, S. Singh, and Y. Mansour, “Policy gradient methods for reinforcement learning with function approximation,” _Advances in neural information processing systems_ , vol. 12, 1999.
  * [22] J. Schulman, S. Levine, P. Abbeel, M. Jordan, and P. Moritz, “Trust region policy optimization,” in _International conference on machine learning_. PMLR, 2015, pp. 1889–1897.
  * [23] J. Schulman, F. Wolski, P. Dhariwal, A. Radford, and O. Klimov, “Proximal policy optimization algorithms,” _arXiv preprint arXiv:1707.06347_ , 2017\.
  * [24] V. Mnih, K. Kavukcuoglu, D. Silver, A. Graves, I. Antonoglou, D. Wierstra, and M. Riedmiller, “Playing atari with deep reinforcement learning,” _arXiv preprint arXiv:1312.5602_ , 2013.
  * [25] J. Gao, W. Ye, J. Guo, and Z. Li, “Deep reinforcement learning for indoor mobile robot path planning,” _Sensors_ , vol. 20, no. 19, p. 5493, 2020.
  * [26] O. Vinyals, I. Babuschkin, W. M. Czarnecki, M. Mathieu, A. Dudzik, J. Chung, D. H. Choi, R. Powell, T. Ewalds, P. Georgiev _et al._ , “Grandmaster level in starcraft ii using multi-agent reinforcement learning,” _Nature_ , vol. 575, no. 7782, pp. 350–354, 2019.
  * [27] C. Yu, A. Velu, E. Vinitsky, J. Gao, Y. Wang, A. Bayen, and Y. Wu, “The surprising effectiveness of ppo in cooperative multi-agent games,” _Advances in Neural Information Processing Systems_ , vol. 35, pp. 24 611–24 624, 2022.
  * [28] H. K. Khalil, “Lyapunov stability,” _Control systems, robotics and automation_ , vol. 12, p. 115, 2009.
  * [29] P. Giesl and S. Hafstein, “Review on computational methods for lyapunov functions,” _Discrete and Continuous Dynamical Systems-B_ , vol. 20, no. 8, pp. 2291–2331, 2015.
  * [30] S. P. Boyd and L. Vandenberghe, _Convex optimization_. Cambridge university press, 2004.
  * [31] P. A. Parrilo, _Structured semidefinite programs and semialgebraic geometry methods in robustness and optimization_. California Institute of Technology, 2000.
  * [32] D. Henrion and M. Korda, “Convex computation of the region of attraction of polynomial control systems,” _IEEE Transactions on Automatic Control_ , vol. 59, no. 2, pp. 297–312, 2013.
  * [33] R. Bobiti and M. Lazar, “A sampling approach to finding lyapunov functions for nonlinear discrete-time systems,” in _2016 European Control Conference (ECC)_. IEEE, 2016, pp. 561–566.
  * [34] E. Najafi, R. Babuška, and G. A. Lopes, “A fast sampling method for estimating the domain of attraction,” _Nonlinear dynamics_ , vol. 86, pp. 823–834, 2016.
  * [35] S. M. Richards, F. Berkenkamp, and A. Krause, “The lyapunov neural network: Adaptive stability certification for safe learning of dynamical systems,” in _Conference on Robot Learning_. PMLR, 2018, pp. 466–476.
  * [36] M. Seeger, “Gaussian processes for machine learning,” _International journal of neural systems_ , vol. 14, no. 02, pp. 69–106, 2004.
  * [37] F. Berkenkamp, R. Moriconi, A. P. Schoellig, and A. Krause, “Safe learning of regions of attraction for uncertain, nonlinear systems with gaussian processes,” in _2016 IEEE 55th Conference on Decision and Control (CDC)_. IEEE, 2016, pp. 4661–4666.
  * [38] F. Berkenkamp, M. Turchetta, A. Schoellig, and A. Krause, “Safe model-based reinforcement learning with stability guarantees,” _Advances in neural information processing systems_ , vol. 30, 2017.
  * [39] Y. Chow, O. Nachum, E. Duenez-Guzman, and M. Ghavamzadeh, “A lyapunov-based approach to safe reinforcement learning,” _Advances in neural information processing systems_ , vol. 31, 2018.
  * [40] Y.-C. Chang, N. Roohi, and S. Gao, “Neural lyapunov control,” _Advances in neural information processing systems_ , vol. 32, 2019.
  * [41] A. Raffin, A. Hill, A. Gleave, A. Kanervisto, M. Ernestus, and N. Dormann, “Stable-baselines3: Reliable reinforcement learning implementations,” _Journal of Machine Learning Research_ , vol. 22, no. 268, pp. 1–8, 2021\. [Online]. Available: http://jmlr.org/papers/v22/20-1364.html
  * [42] A. Paszke, S. Gross, F. Massa, A. Lerer, J. Bradbury, G. Chanan, T. Killeen, Z. Lin, N. Gimelshein, L. Antiga _et al._ , “Pytorch: An imperative style, high-performance deep learning library,” _Advances in neural information processing systems_ , vol. 32, 2019.

  *[RL]: Reinforcement Learning
  *[RoA]: Region of Attraction
  *[MDP]: Markov desision process
  *[TRPO]: Trust Region Policy Optimization
  *[KL]: Kullback-Leibler
  *[PPO]: Proximal Policy Optimization
  *[SDP]: Semi-Definite Program
  *[SOS]: Sum-of-Squares
  *[TPC]: Tree-Structured PPO Controller
  *[GPC]: Graph-Structured PPO Controller