# Learning to Exploit Elastic Actuators for Quadruped Locomotion

Antonin Raffin1, Daniel Seidel1, Jens Kober2, Alin Albu-Schäffer1, João
Silvério1, Freek Stulp1 1 German Aerospace Center (DLR), Robotics and
Mechatronics Center (RMC), Münchner Str. 20, 82234 Weßling, Germany2 Delft
University of Technology, Cognitive Robotics Department, The Netherlands

###### Abstract

Spring-based actuators in legged locomotion provide energy-efficiency and
improved performance, but increase the difficulty of controller design. While
previous work has focused on extensive modeling and simulation to find optimal
controllers for such systems, we propose to learn model-free controllers
directly on the real robot. In our approach, gaits are first synthesized by
central pattern generators (CPGs), whose parameters are optimized to quickly
obtain an open-loop controller that achieves efficient locomotion. Then, to
make this controller more robust and further improve the performance, we use
reinforcement learning to close the loop, to learn corrective actions on top
of the CPGs. We evaluate the proposed approach on the DLR elastic quadruped
bert. Our results in learning trotting and pronking gaits show that
exploitation of the spring actuator dynamics emerges naturally from optimizing
for dynamic motions, yielding high-performing locomotion, particularly the
fastest walking gait recorded on bert, despite being model-free. The whole
process takes no more than 1.5 hours on the real robot and results in natural-
looking gaits.

##  I Introduction

Robots with elastic actuators, such as DLR’s bert [1] (Fig. 1), are a
promising alternative to their rigid counterparts [2, 3], especially for
legged locomotion [4, 5, 6, 7]. In addition to the passive compliance that
protects them from collisions, the elastic elements provide energy storing and
improved efficiency if properly used. The design of controllers that fully
exploit the intrinsic dynamics of compliantly actuated robots remains a
challenge, requiring high amounts of time and system-specific knowledge [8].
In this work, we address the problem of obtaining efficient controllers for
the locomotion of elastically-actuated robots by formulating controller design
as a learning problem.

###  I-A Related Work

Quadruped robots. In recent years, several works studied quadruped locomotion
controllers on different hardware platforms (ANYmal, A1 Unitree, …). Even
though some of these have elastic actuators (e. g. ANYmal [9] or Mini Cheetah
[10]), their stiffness is high compared to bert (see Section II-A) leaving
little room to exploit the advantages of the actuators’ elasticity in control.

Figure 1: Compliantly actuated DLR quadruped bert jumping in place.

Reinforcement learning for locomotion. Obtaining locomotion controllers is
commonly based on fast simulators and massive parallelism [11, 12] and
consists of learning the controllers in simulation and subsequently deploying
them on real hardware [13, 14]. Learning in simulation, however, requires an
accurate model of the robot [15], complex reward engineering, and there is no
guarantee that a controller working in simulation can be deployed on the real
robot. Heavy randomization and generation of diverse training environments
help mitigate these issues [16, 12], but still requires engineering efforts to
find the right balance between environments too hard to solve and ones that do
not transfer to the real robot. Our key difference from many previous
approaches is that we learn directly on the real hardware, without the need to
transfer from simulation to reality. To our knowledge, this is also the first
time that reinforcement learning is used directly on a quadruped with elastic
actuators.

Training on real robot. Thanks to more robust hardware [17] and more sample-
efficient algorithms [18, 19, 20, 21], learning directly on the real hardware
in only a few hours is now possible [22, 23]. Despite these advances, training
on real robots can nevertheless be time-consuming and often does not yield
natural-looking gaits [19, 20]. In the present work, we aim both at reducing
the training time (and thus the robot wear and tear) and obtaining gaits that
look natural by 1) providing domain knowledge in the form of central pattern
generators and 2) exploiting the natural dynamics of the robot, in particular
its elastic joints. In order to mitigate model mismatch or simulation-to-
reality gaps, we choose to apply a model-free learning approach directly on
the real hardware.

CPGs and Reflex-Based Controllers. Inspired by biology, central pattern
generators (CPGs) have been proposed for locomotion [24, 25, 26, 27]. They
generate gaits that look natural but require careful parameter tuning, usually
done in simulation. In this work, we rely on a CPG model to represent the
open-loop motion policy that is later improved with reinforcement learning.
Another possibility to obtain dynamic gaits in elastically-actuated robots is
to rely on reflex-based controllers [1, 28, 29], whose parameters also require
further optimization. Our research is applicable to both CPG and reflex-based
controllers, as we automate the parameter optimization and improve robustness
and performance with a learned reactive controller. Our approach achieves the
fastest walking gait on the bert hardware (0.34 m/s vs 0.25 m/s in [28]).

Comparison to CPG-RL and PMTG. Parallel to our work is the CPG-RL method [27],
which can be viewed as a special case of Policies Modulating Trajectory
Generators (PMTG) [30] where the residual component is removed. In CPG-RL and
PMTG, the parameters of the trajectory generator are dynamically updated by an
RL agent. Both approaches focus primarily on simulation and therefore rely on
domain randomization to ensure performance during real-world testing. Despite
sharing architectural similarities, unlike CPG-RL and PMTG, our research
emphasizes the unique challenges and benefits associated with learning
controllers for quadruped robots with elastic actuators. While CPG-RL employs
a massively parallel simulator with 4096 virtual robots, we train directly on
a single real robot, concluding that its elastic actuators indeed provide
additional robustness and performance over rigid equivalents. Furthermore, we
challenge the statement made in the PMTG paper that “despite the pre-
optimization, the TG itself cannot provide stable forward locomotion since it
lacks the feedback from the robot”: our results show that an optimized open-
loop controller is sufficient for forward motion on the real hardware.

Feedforward and Feedback Control. The integration of feedforward (open-loop)
and feedback (closed-loop) control is a well-established practice in
engineering [31, 32, 33], also known as residual learning [34] in the RL
community. This approach combines the benefits of fast computation and
robustness to sensor noise offered by open-loop control with the ability of
closed-loop control to address model inaccuracies and respond to disturbances.
In our work, we adopt this architecture by utilizing a bio-inspired open-loop
control strategy based on central pattern generators (CPGs) and augmenting it
with reinforcement learning to enhance performance and robustness.
Importantly, both components of our control system are model-free and
optimized directly on the real robot, enabling us to fully leverage the
intrinsic dynamics of the elastic robot.

###  I-B Contributions

In summary, the main contributions of our paper are:

  * •

an approach to design locomotion controllers for robots with elastic actuators
(Section III) that combines CPGs, black-box optimization and reinforcement
learning, achieving the fastest walking gait for the bert platform,

  * •

an experimental verification that the learned controllers exploit the
elasticity of the actuators (Section IV), and

  * •

showing that controllers can be learned directly on the real elastic robot in
less than one hour, without the need for complex reward engineering or
massively parallel simulation [12] (Section IV).

##  II Background

In this section, we provide an overview of DLR’s elastic quadruped bert,
metrics for monitoring spring usage, as well as central pattern generators – a
cornerstone of our proposed approach – including the CPG parameters that we
aim to optimize.

###  II-A DLR quadruped bert

The DLR quadruped bert [1] (shown in Fig. 1) is a cat-sized quadruped robot
with series elastic actuators (SEA). The legs are attached to the trunk
through the hip axis, while the motors are located inside the trunk and
connected by belt drives. Each leg consists of a hip and a knee joint and is
composed of two segments of equal length of approximately 8cm. The total mass
of the robot is about 3.1kg. As depicted in Fig. 2, motors are connected to
the links via a linear torsional spring with constant stiffness $k\approx
2.75\text{Nm}/\text{rad}$. We use the deflection of the spring to estimate the
external torque applied to each joint:

$\tau_{i}=k(\theta_{i}-q_{i})$ (1)

where $\theta$ is the motor position before the spring and $q$ the joint
position.

Figure 2: Model of the compliantly actuated leg (left) and a serial elastic
actuator (right).

bert is equipped with very soft springs relative to its weight and lever arm,
i. e. $2.75\text{Nm}/\text{rad}$, compared to for instance StarlETH [9] with
20cm link length, total weight of 23kg and $k{=}70\text{Nm}/\text{rad}$. This
means that e. g. when standing in a default position with joints at $30\deg$,
bert can be pushed into joint limits without motor movement, while StarlETH
can be pushed into its springs only minimally. This makes bert suitable for
exploiting its springs as energy storage: forces required to load the springs
are quite low and occur during normal gait motions.

When released at the right time, the stored energy can be converted into
kinetic energy (joint velocity). This can lead to improved task performance.
We formally define metrics to quantify the spring usage in the next section.

###  II-B Metrics

Objective functions of learning methods typically describe tasks (e. g. move
forward as fast as possible), and do not enforce explicit usage of the
compliant actuators. To measure if the learned controllers exploit the
capability of the elastic robot, we define metrics that quantify the spring
usage.

By storing and releasing energy, springs allow joints to reach much higher
velocities than the motors [2]. The peak joint velocity usually has a delay
compared to the peak motor velocity. Therefore, we propose to compare the
ratio between maximum joint and motor velocity over a trajectory for each
joint:

$_{/}i=\frac{\max_{t}{\dot{q}_{i}}}{\max_{t}{\dot{\theta}_{i}}}.$ (2)

Intuitively, if the springs are fully exploited, the ratio /should be greater
than one (rigid robot baseline), meaning that the energy is stored and
released at the right moment.

Finally, we also monitor the potential and kinetic energy to better understand
how energy is transferred and how the learned controllers utilize the elastic
actuators. We only consider the kinetic energy related to the task (movement
of the center of mass) and therefore do not plot the rotational kinetic
energy.

###  II-C Central pattern generators (CPGs) for legged locomotion

CPGs are a common tool used for generating open-loop policies for locomotion
[35]. We rely on an implementation based on a system of four coupled nonlinear
oscillators [36, 25, 26] (one per leg) that have phase-dependent frequencies.
The equation of one oscillator in polar coordinates is [37]:

$\displaystyle\dot{\rho_{i}}$ $\displaystyle=a(\mu-\rho_{i}^{2})\rho_{i}$ (3)
$\displaystyle\dot{\varphi_{i}}$
$\displaystyle=\omega+\sum_{j}\,\rho_{j}\,c_{ij}\,\sin(\varphi_{j}-\varphi_{i}-\Phi_{ij})$
$\displaystyle\omega$
$\displaystyle=\begin{cases}{\color[rgb]{0.04296875,0.4453125,0.5234375}\definecolor[named]{pgfstrokecolor}{rgb}{0.04296875,0.4453125,0.5234375}\omega_{\text{swing}}}&\text{if
$\sin(\varphi_{i})>0$}\\\
{\color[rgb]{0.52734375,0.1796875,0.61328125}\definecolor[named]{pgfstrokecolor}{rgb}{0.52734375,0.1796875,0.61328125}\omega_{\text{stance}}}&\text{otherwise}\end{cases}$

where $\rho_{i}$ and $\varphi_{i}$ are the amplitude and phase of oscillator
$i$, $\omega$ is the frequency of oscillations in rad/s, $\sqrt{\mu}$ is the
desired amplitude,
${\color[rgb]{0.04296875,0.4453125,0.5234375}\definecolor[named]{pgfstrokecolor}{rgb}{0.04296875,0.4453125,0.5234375}\omega_{\text{swing}}}$
and
${\color[rgb]{0.52734375,0.1796875,0.61328125}\definecolor[named]{pgfstrokecolor}{rgb}{0.52734375,0.1796875,0.61328125}\omega_{\text{stance}}}$
are the frequencies of the swing and stance phases. $a$ is a positive constant
that controls the rate of convergence to the limit cycle. The weights $c_{ij}$
and phase biases $\Phi_{ij}$ define the couplings between oscillators.

The output of each oscillator determines the foot trajectory in Cartesian
space (cf. Fig. 3). The coupling matrix $\Phi$ therefore determines the gait.
For instance, for trotting [38, 39] (foot pattern displayed in Fig. 5), the
front right leg is in phase with the hind left leg, and they have a half-cycle
offset with the other diagonal (front left with hind right).

Figure 3: The parameters of the CPG gait that are optimized.

As shown in Fig. 3, the trajectory of each leg $i$ depends on four parameters
that have to be tuned: ground clearance
${\color[rgb]{0.359375,0.58203125,0.05078125}\definecolor[named]{pgfstrokecolor}{rgb}{0.359375,0.58203125,0.05078125}\Delta
z_{\text{clear}}}$ and penetration
${\color[rgb]{0.8515625,0.28125,0.05859375}\definecolor[named]{pgfstrokecolor}{rgb}{0.8515625,0.28125,0.05859375}\Delta
z_{\text{pen}}}$, step length
${\color[rgb]{0.37109375,0.23828125,0.76953125}\definecolor[named]{pgfstrokecolor}{rgb}{0.37109375,0.23828125,0.76953125}\Delta
x_{\text{len}}}$, swing
${\color[rgb]{0.04296875,0.4453125,0.5234375}\definecolor[named]{pgfstrokecolor}{rgb}{0.04296875,0.4453125,0.5234375}\omega_{\text{swing}}}$
and stance
${\color[rgb]{0.52734375,0.1796875,0.61328125}\definecolor[named]{pgfstrokecolor}{rgb}{0.52734375,0.1796875,0.61328125}\omega_{\text{stance}}}$
frequencies. We convert the output of one oscillator $i$ to a desired foot
trajectory following:

$\displaystyle x_{\text{des},i}$
$\displaystyle={\color[rgb]{0.37109375,0.23828125,0.76953125}\definecolor[named]{pgfstrokecolor}{rgb}{0.37109375,0.23828125,0.76953125}\Delta
x_{\text{len}}}\cdot\rho_{i}\cos(\varphi_{i})$ (4) $\displaystyle
z_{\text{des},i}$ $\displaystyle=\Delta z\cdot\rho_{i}\sin(\varphi_{i})$
$\displaystyle\Delta z$
$\displaystyle=\begin{cases}{\color[rgb]{0.359375,0.58203125,0.05078125}\definecolor[named]{pgfstrokecolor}{rgb}{0.359375,0.58203125,0.05078125}\Delta
z_{\text{clear}}}&\text{if $\sin(\varphi_{i})>0$
({\color[rgb]{0.04296875,0.4453125,0.5234375}\definecolor[named]{pgfstrokecolor}{rgb}{0.04296875,0.4453125,0.5234375}swing})}\\\
{\color[rgb]{0.8515625,0.28125,0.05859375}\definecolor[named]{pgfstrokecolor}{rgb}{0.8515625,0.28125,0.05859375}\Delta
z_{\text{pen}}}&\text{otherwise
({\color[rgb]{0.52734375,0.1796875,0.61328125}\definecolor[named]{pgfstrokecolor}{rgb}{0.52734375,0.1796875,0.61328125}stance}).}\end{cases}$

The most critical parameters for an elastically-actuated quadruped are the
swing and stance duration, as they should match the natural dynamics of the
robot [40, 41].

Tuning these variables manually is time-consuming and usually results in
suboptimal choices. Therefore, we automate their tuning using black-box
optimization (BBO) and run the optimization directly on the real robot,
avoiding any model mismatch. In the following section, we explain the use of
BBO and how it fits into our proposed framework.

##  III Online learning for legged locomotion

To learn a locomotion controller for the elastic legged robot, we combine two
model-free methods. We first optimize the parameters of a selected gait
(generated from a CPG) to quickly obtain an open-loop controller that works in
the nominal case without disturbances. Then, we refine the controller and make
it more robust to perturbations by learning a reinforcement learning (RL)
controller that adds offsets to the CPG output. The entire optimization
process – depicted in Fig. 4 – is conducted directly on the real robot,
removing the need for modeling, accurate simulators or simulation-to-reality
transfer.

Figure 4: Overview of the proposed approach: CPG parameters are first
optimized using BBO, then a RL controller is trained on top and outputs
corrective actions.

CPGs provide a compact representation of limb end-effector trajectories (Eq.
4) that can be adjusted via the set of parameters $\alpha$ shown in Fig. 3:

$\alpha=\set{{\color[rgb]{0.359375,0.58203125,0.05078125}\definecolor[named]{pgfstrokecolor}{rgb}{0.359375,0.58203125,0.05078125}\Delta
z_{\text{clear}}},{\color[rgb]{0.8515625,0.28125,0.05859375}\definecolor[named]{pgfstrokecolor}{rgb}{0.8515625,0.28125,0.05859375}\Delta
z_{\text{pen}}},{\color[rgb]{0.37109375,0.23828125,0.76953125}\definecolor[named]{pgfstrokecolor}{rgb}{0.37109375,0.23828125,0.76953125}\Delta
x_{\text{len}}},{\color[rgb]{0.04296875,0.4453125,0.5234375}\definecolor[named]{pgfstrokecolor}{rgb}{0.04296875,0.4453125,0.5234375}\omega_{\text{swing}}},{\color[rgb]{0.52734375,0.1796875,0.61328125}\definecolor[named]{pgfstrokecolor}{rgb}{0.52734375,0.1796875,0.61328125}\omega_{\text{stance}}}}.$
(5)

###  III-A Open-loop policy learning with black-box optimization (BBO)

In BBO, the goal is to find a set of parameters $\alpha\in\mathbb{R}^{n}$ that
minimizes an objective function $f:\mathbb{R}^{n}\rightarrow\mathbb{R}$,

$\alpha^{*}=\operatorname*{arg\,min}_{\alpha}{f(\alpha)}.$ (6)

A BBO algorithm only has access to function evaluations of $f$. It treats $f$
as a black box and does not make any assumption about it (e. g. $f$ can be
non-differentiable). In our case, each function evaluation corresponds to one
trial (or episode) on the robot for a given set of CPG parameters $\alpha$.

We use $f$ to quantify how much a set of CPG parameters satisfies a desired
goal. We will describe the objective functions we choose for each task in
Section III-C.

###  III-B Closing the loop with reinforcement learning

Reinforcement learning (RL) is similar to BBO but has access to the immediate
reward $r_{t}$ that composes the objective function, when it’s available,
making it more sample-efficient. Formally, an agent interacts with its
environment and generates trajectories $\zeta_{\pi}$ that follow a policy
$\pi$. By progressively updating its policy, the agent learns to maximize its
cumulative (discounted) reward:

$\sum_{t}\operatorname{\mathbb{E}}_{\zeta_{\pi}}\left[\gamma^{t}r_{t}\right]$
(7)

where $\gamma\in[0,1)$ is the discount factor and represents a trade-off
between maximizing short-term and long-term rewards.

While the BBO algorithm optimizes the parameters of the gait generated by the
coupled oscillators, the RL agent learns a reactive controller $\pi$ as a set
of corrective actions per leg $i$ defined as
${\color[rgb]{0.09375,0.390625,0.671875}\definecolor[named]{pgfstrokecolor}{rgb}{0.09375,0.390625,0.671875}\bm{\pi}_{i}=\left[\pi_{x,i}\left({\mathbf{s}_{t}}\right),\pi_{z,i}\left({\mathbf{s}_{t}}\right)\right]}$.
The learned policy $\pi$ adjusts desired foot positions produced by the CPG
(Eq. 4) given the current state of the robot ${\mathbf{s}_{t}}$, closing the
control loop:

$\displaystyle x_{\text{des},i}$
$\displaystyle={\color[rgb]{0.65234375,0.1171875,0.30078125}\definecolor[named]{pgfstrokecolor}{rgb}{0.65234375,0.1171875,0.30078125}\Delta
x_{\text{len}}\cdot\rho_{i}\cos(\varphi_{i})}+{\color[rgb]{0.09375,0.390625,0.671875}\definecolor[named]{pgfstrokecolor}{rgb}{0.09375,0.390625,0.671875}\pi_{x,i}({\mathbf{s}_{t}})}$
(8) $\displaystyle z_{\text{des},i}$
$\displaystyle={\color[rgb]{0.65234375,0.1171875,0.30078125}\definecolor[named]{pgfstrokecolor}{rgb}{0.65234375,0.1171875,0.30078125}\Delta
z\cdot\rho_{i}\sin(\varphi_{i})}+{\color[rgb]{0.09375,0.390625,0.671875}\definecolor[named]{pgfstrokecolor}{rgb}{0.09375,0.390625,0.671875}\pi_{z,i}({\mathbf{s}_{t}})}$

###  III-C Task Specification

In this work, we focus on two dynamic gaits: trotting and pronking (jumping in
place).

#### Trotting

The first task we are interested in is to obtain a fast walking trot, where we
optimize for mean forward speed ($f(\alpha)=-\frac{\Delta x}{\Delta t}$). We
define the immediate reward as the distance traveled between two timesteps
along the desired axis (${r_{t}}=\dot{x}_{\text{robot}}$).

After optimization, we further evaluate the five best performing candidates
for more episodes. This post-processing step is key to filtering out the
evaluation noise, i. e. it helps to find parameters that lead to reliable
gaits.

Figure 5: Trotting gaits for a 2-second period. Dark colors represent stance
phases, light colors swing phases.

#### Pronking

The second task is to jump in place (pronk) without falling or drifting from
the starting position. In a pronking gait, all legs are synchronized: they all
take off and land at the same time (as seen in Fig. 6). The step length is set
to zero in that case. We penalize angular velocity for roll and yaw, distance
to the starting point and reward velocity along the $z$ axis (aligned with
gravity field):
${r_{t}}=w_{1}|\dot{z}|-w_{2}(\dot{\psi}_{\text{roll}}^{2}+\dot{\psi}_{\text{yaw}}^{2})-w_{3}\Delta_{xy}^{2}$,
where $w_{1,2,3}$ are weights chosen in a way that the primary reward
$|\dot{z}|$ has a higher magnitude than the secondary costs. We define the
objective function for the BBO as the total reward per episode
($f(\alpha)=-\sum_{t}{r_{t}}$).

Figure 6: Pronking gaits for a 2-second period.

In all tasks, the RL agent receives as input ${\mathbf{s}_{t}}$ the current
joint positions, velocities, torques, linear acceleration and angular velocity
(from the IMU), and the desired foot position generated by the CPG controller.
The action space corresponds to offsets for each foot in Cartesian space.

##  IV Results

We evaluate our approach on two locomotion tasks (trotting and pronking) to
answer the following questions:

  * •

Can we quickly learn a controller directly on the real elastic robot?

  * •

How does the learned controller exploit the elastic actuators?

  * •

What do we gain by learning CPG parameters with BBO?

  * •

What is the added value of closing the loop with RL?

  * •

Is CPG needed or is RL from scratch enough?

###  IV-A Setup

During training only, we use an external tracking system that provides robot
absolute position and orientation at $60\text{Hz}$. Each trial has a timeout
of $5\text{s}$ and terminates earlier if the robot reaches the tracking limits
or if the quadruped falls over. We use a treadmill of one by three meters to
limit the need of manual intervention. The treadmill is also the tracked area
usable by the robot.

To tune the parameters of the open-loop controller, we use Bayesian
optimization, as it is sample efficient in low-dimensional search spaces [22].
We use the TPE [42] implementation from the Optuna [43] library. For
reinforcement learning we choose TQC, a sample-efficient off-policy algorithm
[44], with smooth exploration [23] to remove the need for a low-pass filter.
We run RL experiments using the RL Zoo [45] framework and Stable-Baselines3
[46] library (with tuned hyperparameters from [23]).

The agent is trained at $30\text{Hz}$ but can be evaluated at $60\text{Hz}$
(limited by the tracking system). The CPG parameters are optimized during 45
minutes for the trotting experiment and 25 minutes for the pronking one (250
and 160 trials respectively). The RL controller is then trained on top during
one hour. For safety, the motor velocities are capped at
$\dot{\theta}_{\max}=4\text{rad/s}$.

Hand-tuned Baseline. We use parameters tuned by hand by a human experimenter
familiar with the elastic quadruped as a baseline. The experimenter was given
the same time and search space as the BBO algorithm, as well as an explanation
of the meaning and importance of each parameter.

RL Baseline. When learning from scratch, we use the setting described in [19]
to be able to learn a controller in minutes, using 10 gradient steps per
control step. The action space is extended to be similar in task space to the
one used by the CPG controller.

###  IV-B Fast Trotting

Without the need for a simulator or prior knowledge, the automatic tuning with
BBO quickly finds good parameters for trotting in less than an hour with the
real robot. Looking at the optimization history in Fig. 7, the algorithm
discovers parameters that match the hand-tuned performance in less than 5
minutes (30 trials, a trial takes around $10\text{s}$ on average, accounting
for resets) and parameters that exceed $0.20\text{m/s}$ in 10 minutes (60
trials).

Figure 7: Optimization history plot for trotting (45 minutes).

After only 40 minutes of optimization, the gains are significant for the
trotting gait (cf. Table I): with the same maximum motor velocity, the
quadruped trots 70% faster, reaching a mean speed of $0.26\text{m/s}$ (vs.
$0.15\text{m/s}$ with hand-tuned parameters).

Closing the loop with reinforcement learning helps to further improve
performance111We used bootstrap confidence intervals to test for statistical
significance.. Both with the hand-tuned and the optimized CPG, the robot trots
significantly faster (20% and 30% faster respectively). The combination of
optimized CPG + RL gives the best results ($0.34\text{m/s}$), and the hand-
tuned CPG + RL does not reach the performance of the optimized CPG gait
($0.19\text{m/s}$). This is also the fastest walking speed achieved on the
bert platform (the previous record was 0.25 m/s in [28]).

| RL | CPG | CPG + RL
---|---|---|---
|  | hand-tuned | optimized | hand-tuned | optimized
Speed (m/s) $\uparrow$ | 0.14 | 0.15 | 0.26 | 0.19 | 0.34
Mean /$\uparrow$ | 1.4 +/- 0.1 | 1.4 +/- 0.1 | 1.9 +/- 0.1 | 1.6 +/- 0.1 | 2.0 +/- 0.3

TABLE I:  Results for the fast trotting experiment. The optimized gait trots
70% faster that the hand-tuned controller and exploit more the springs. RL
from scratch merely achieves the hand-tuned CPG performance. RL on top of CPG
further improves the performance.

We display in Fig. 5 the patterns and in Figs. 8(a) and 8(b) the trotting
gaits for the hand-tuned and optimized parameters (CPG only). The main
difference is a longer swing phase ($0.29\text{s}$ vs. $0.14\text{s}$ for the
hand-tuned one) and larger step length
(${\color[rgb]{0.37109375,0.23828125,0.76953125}\definecolor[named]{pgfstrokecolor}{rgb}{0.37109375,0.23828125,0.76953125}\Delta
x_{\text{len}}}{=}5\text{cm}$ vs. $2.5\text{cm}$). However, increasing the
step length alone does not result in a faster gait. Only in combination with
appropriate adjustment of the other parameters, the speed can be increased.

Concerning joint and motor velocities, the optimized controller reaches higher
peak joint velocities for the same peak motor velocities (Table I). The peak
joints velocities are almost twice the one of the motors ($=/2.0$ vs. $1.4$
for the hand-tuned) showing the potential of springs for locomotion. In fact,
as seen in Fig. 9, the peak in joint velocity $\dot{q}$ corresponds to a
sudden decrease in the spring potential energy: the energy of the spring is
converted into kinetic energy. The main difference between the results of
hand-tuned and optimized parameters is the timing of this conversion. For the
learned controller, it happens when the motor velocity $\dot{\theta}$ is still
at its peak B, while for the hand-tuned one, it happens when the motor
velocity has already started to decrease A.

(a) Hand-tuned trotting gait ($0.15\text{m/s}$).

(b) Optimized trotting gait ($0.26\text{m/s}$).

Figure 8: Hand-tuned and optimized trotting gaits for a 2-second period.

A

B

Figure 9: Joint and motor velocity of the front right foot while trotting for
a 2-second period. Darker background represents stance phase. Blue and orange
dotted lines represent maximum joint and motor velocities, respectively.

###  IV-C Is RL from scratch sufficient?

Table I also shows the result of learning to walk from scratch with RL on the
real robot. As shown in the accompanying video, the RL controller learns to
walk in 10 minutes only, but the performance plateaus afterward. The RL
controller barely reaches the hand-tuned CPG performance ($0.14\text{m/s}$),
and this translates into less use of the springs ($\approx/1.4$).

This experiment illustrates the shortcomings of learning from scratch. RL
would require extensive reward engineering [13, 11] to achieve natural-looking
gaits similar to the open-loop CPG (e. g. adding a foot clearance reward). The
gait learned by RL is also unpredictable: since we only optimize for the
forward speed, it does not have to trot, but could for example, pronk. On the
other hand, the gaits produced by the CPG controller encode basic primitives
for walking (e. g. foot clearance does not need to be specified in the
reward), and the coupling matrix gives control over the gait type. Learning
from scratch with RL is more dangerous for the hardware, as any kind of
movement of the legs is allowed, and the smoothness of the controller must be
enforced to not damage the motors with high frequency control output.

Finally, we do not consider approaches that train a controller in simulation
[12, 11]. We want to fully exploit the real robot dynamics and be able to
quickly reuse the approach on other robots without the expensive cost of
bridging the gap between simulation and reality each time.

###  IV-D Stabilizing Pronking

For the pronking task, the BBO algorithm discovers multiple good sets of
parameters in less than 10 minutes (60 trials), as seen in the optimization
history in Fig. 10. The hand-tuned and optimized CPG parameters both allow the
robot to jump in place, but the open-loop controller rapidly fails when the
robot roll angle increases, either as a consequence of an applied perturbation
or the interaction with the floor.

Figure 10: Optimization history plot for pronking (30 minutes).

By closing the loop between the robot state and actions, the reinforcement
learning controller helps mitigate this issue, as summarized in Table II. Here
we see that the solution with RL results in no failures. The qualitative
difference is highlighted in the accompanying video. The quadruped also jumps
more in place (less drift with respect to the starting position) while keeping
the same jumping height.

As for the trotting experiment, adding RL on top of the hand-tuned CPG
improves performance but does not match the optimized controller.

We show in Fig. 6 the patterns for the hand-tuned and optimized pronking gaits
(CPG only), and in Fig. 11 the robot jumping in place. The optimized
parameters are quite different from the hand-tuned ones: the swing phase is
shorter ($0.10\text{s}$ vs. $0.18\text{s}$ for the hand-tuned one) and stance
phase longer ($0.22\text{s}$ vs. $0.15\text{s}$), and the ratio between the
two is inverted (swing phase shorter than the stance phase).

1

2

3

4

5

6

7

8

Figure 11: Pronking gait (max jump height: $0.1\text{m}$).

The energy evolution in Fig. 12 demonstrates how elastic properties of the
actuators are exploited. The robot first crouches on the floor (decrease in
gravitational potential energy), compressing and loading the spring C. To
jump, it then pushes all its legs against the floor, while at the same time
releasing the energy stored in the springs. This energy is converted both into
kinetic energy (the robot reaches its maximum speed shortly after takeoff D)
and gravitational potential energy. After reaching the maximum height E, the
gravitational potential energy is converted back into kinetic energy before
the robot lands and the jumping cycle starts again.

CDE

Figure 12: Energy evolution while pronking for a 2-second period.

The main difference between the hand-tuned and optimized parameters is the
maximum spring potential energy. This results in higher jumps for the
optimized controller (higher peak in gravitational potential energy in Fig.
12). Finally, compared to trotting, the peak joint velocity is higher for
pronking ($=/3.5$ vs. $1.8$) as the leg springs are synchronously compressed
and released. As shown in Table II, the peak joint velocity is on average
$3.5$ the maximum velocity reached by the motors for the optimized parameters,
versus $2.9$ for the hand-tuned ones.

| CPG | CPG + RL
---|---|---
| hand-tuned | optimized | hand-tuned | optimized
Mean reward ($10^{3}$) $\uparrow$ | 1.0 +/- 0.1 | 1.4 +/- 0.2 | 1.4 +/- 0.1 |  1.6 +/- 0.1 (+60%)
Drift $\Delta_{xy}$ cost $\downarrow$ | 1.3 +/- 0.1 | 1.5 +/- 0.1 | 1.3 +/- 0.1 | 1.3 +/- 0.1
Angular vel. cost $\downarrow$ | 204 +/- 6 | 194 +/- 14 | 183 +/- 10 | 160 +/- 10
Max height (cm) $\uparrow$ | 7.3 | 9.3 | 8.1 | 9.4
Failures | 1 failure | 1 failure | no failure | no failure
Mean /$\uparrow$ | 2.9 +/- 0.2 | 3.3 +/- 0.2 | 3.2 +/- 0.2 |  3.5 +/- 0.3 (+20%)

TABLE II: Results for the jumping in place experiment, on 5 evaluation
episodes. Failures occur without external perturbations.

##  V Conclusion

We have shown that by integrating central pattern generators with black-box
optimization and reinforcement learning, it is possible to learn efficient and
natural-looking gaits directly on a real elastic quadruped robot. This is done
without the need for complex reward engineering or massively parallel
simulation. In particular, the learned gaits exploit the natural dynamics of
the robot, enabling efficient storage and release of energy in the springs, a
behavior that emerged naturally during training without needing to be
accounted for in the reward. This enabled DLR’s quadruped bert to achieve the
fastest walking speed ever recorded.

Learning directly on the real robot comes with its own challenges. Each
experiment must be carefully designed to achieve sample efficient training
(choice of action and search space, hyperparameters); trials on the real robot
cannot be parallelized. Like simulation-to-reality approaches, running
software on real hardware requires expertise to ensure the robot’s safety and
is time-consuming. However, with our approach, once training is complete, no
additional step is required for deployment. Although we focus here on
individual gaits, our future research will address the discovery of novel
behaviors, especially when adapting to new and unseen environments.

## Acknowledgment

This work was funded by the EU’s H2020 Research and Innovation Programme under
grant numbers 951992 (VeriDream) and 835284 (M-Runners). We thank Milan
Hermann and Florian Loeffl for their help with the hardware.

## References

  * [1] D. Seidel, M. Hermann, T. Gumpert, F. C. Loeffl, and A. Albu-Schäffer, “Using elastically actuated legged robots in rough terrain: Experiments with DLR quadruped bert,” in _2020 IEEE Aerospace Conference_ , 2020, pp. 1–8.
  * [2] N. Mansfeld, M. Keppler, and S. Haddadin, “Speed gain in elastic joint robots: An energy conversion-based approach,” _IEEE Robotics and Automation Letters_ , vol. 6, no. 3, pp. 4600–4607, 2021.
  * [3] F. Bjelonic, J. Lee, P. Arm, D. Sako, D. Tateo, J. Peters, and M. Hutter, “Learning-based design and control for quadrupedal robots with parallel-elastic actuators,” _IEEE Robotics and Automation Letters_ , 2023\.
  * [4] R. M. Alexander, “Three uses for springs in legged locomotion,” _The International Journal of Robotics Research_ , vol. 9, no. 2, pp. 53–61, 1990.
  * [5] M. Grimmer, M. Eslamy, S. Gliech, and A. Seyfarth, “A comparison of parallel- and series elastic elements in an actuator for mimicking human ankle joint in walking and running,” in _2012 IEEE International Conference on Robotics and Automation_ , 2012, pp. 2463–2470.
  * [6] F. Ruppert and A. Badri-Spröwitz, “Learning plastic matching of robot dynamics in closed-loop central pattern generators,” _Nature Machine Intelligence_ , vol. 4, no. 7, pp. 652–660, 2022.
  * [7] P. Kormushev, B. Ugurlu, D. G. Caldwell, and N. G. Tsagarakis, “Learning to exploit passive compliance for energy-efficient gait generation on a compliant humanoid,” _Autonomous Robots_ , vol. 43, no. 1, pp. 79–95, 2019\.
  * [8] M. Keppler, D. Lakatos, C. Ott, and A. Albu-Schäffer, “Elastic structure preserving (esp) control for compliantly actuated robots,” _IEEE Transactions on Robotics_ , vol. 34, no. 2, pp. 317–335, 2018.
  * [9] M. Hutter, C. Gehring, M. Bloesch, M. A. Hoepflinger, C. D. Remy, and R. Siegwart, “StarlETH: A compliant quadrupedal robot for fast, efficient, and versatile locomotion,” in _Adaptive Mobile Robotics_. World Scientific, 2012, pp. 483–490.
  * [10] B. Katz, J. D. Carlo, and S. Kim, “Mini cheetah: A platform for pushing the limits of dynamic quadruped control,” _2019 International Conference on Robotics and Automation (ICRA)_ , pp. 6295–6301, 2019.
  * [11] T. Miki, J. Lee, J. Hwangbo, L. Wellhausen, V. Koltun, and M. Hutter, “Learning robust perceptive locomotion for quadrupedal robots in the wild,” _Science Robotics_ , vol. 7, no. 62, p. eabk2822, 2022.
  * [12] N. Rudin, D. Hoeller, P. Reist, and M. Hutter, “Learning to walk in minutes using massively parallel deep reinforcement learning,” in _Conference on Robot Learning_. PMLR, 2022, pp. 91–100.
  * [13] J. Lee, J. Hwangbo, L. Wellhausen, V. Koltun, and M. Hutter, “Learning quadrupedal locomotion over challenging terrain,” _Science robotics_ , vol. 5, no. 47, p. eabc5986, 2020.
  * [14] A. Kumar, Z. Fu, D. Pathak, and J. Malik, “Rma: Rapid motor adaptation for legged robots,” 2021.
  * [15] J. Hwangbo, J. Lee, A. Dosovitskiy, D. Bellicoso, V. Tsounis, V. Koltun, and M. Hutter, “Learning agile and dynamic motor skills for legged robots,” _Science Robotics_ , vol. 4, no. 26, p. eaau5872, 2019.
  * [16] Z. Fu, A. Kumar, J. Malik, and D. Pathak, “Minimizing energy consumption leads to the emergence of gaits in legged robots,” 2021.
  * [17] D. Büchler, S. Guist, R. Calandra, V. Berenz, B. Schölkopf, and J. Peters, “Learning to play table tennis from scratch using muscular robots,” _IEEE Transactions on Robotics_ , 2022.
  * [18] K. Chatzilygeroudis, V. Vassiliades, F. Stulp, S. Calinon, and J.-B. Mouret, “A survey on policy search algorithms for learning robot controllers in a handful of trials,” _IEEE Transactions on Robotics_ , vol. 36, no. 2, pp. 328–347, 2019.
  * [19] L. Smith, I. Kostrikov, and S. Levine, “A walk in the park: Learning to walk in 20 minutes with model-free reinforcement learning,” 2022.
  * [20] P. Wu, A. Escontrela, D. Hafner, K. Goldberg, and P. Abbeel, “Daydreamer: World models for physical robot learning,” 2022.
  * [21] T. Hiraoka, T. Imagawa, T. Hashimoto, T. Onishi, and Y. Tsuruoka, “Dropout q-functions for doubly efficient reinforcement learning,” in _International Conference on Learning Representations_ , 2022.
  * [22] R. Calandra, A. Seyfarth, J. Peters, and M. P. Deisenroth, “Bayesian optimization for learning gaits under uncertainty,” _Annals of Mathematics and Artificial Intelligence_ , vol. 76, no. 1, pp. 5–23, 2016.
  * [23] A. Raffin, J. Kober, and F. Stulp, “Smooth exploration for robotic reinforcement learning,” in _Conference on Robot Learning_ , 2021.
  * [24] A. Crespi and A. J. Ijspeert, “Online optimization of swimming and crawling in an amphibious snake robot,” _IEEE Transactions on Robotics_ , vol. 24, no. 1, pp. 75–87, 2008.
  * [25] L. Righetti and A. Ijspeert, “Pattern generators with sensory feedback for the control of quadruped locomotion,” in _2008 IEEE International Conference on Robotics and Automation_. Pasadena, USA: IEEE, 2008, pp. 819–824.
  * [26] M. Ajallooeian, S. Pouya, A. Sproewitz, and A. J. Ijspeert, “Central pattern generators augmented with virtual model control for quadruped rough terrain locomotion,” in _2013 IEEE international conference on robotics and automation_. IEEE, 2013, pp. 3321–3328.
  * [27] G. Bellegarda and A. J. Ijspeert, “CPG-RL: Learning central pattern generators for quadruped locomotion,” _IEEE Robotics and Automation Letters_ , 2022 (Accepted).
  * [28] D. Lakatos, K. Ploeger, F. Loeffl, D. Seidel, F. Schmidt, T. Gumpert, F. John, T. Bertram, and A. Albu-Schäffer, “Dynamic locomotion gaits of a compliantly actuated quadruped with slip-like articulated legs embodied in the mechanical design,” _IEEE Robotics and Automation Letters_ , vol. 3, no. 4, pp. 3908–3915, 2018.
  * [29] A. Schmidt, B. Feldotto, T. Gumpert, D. Seidel, A. Albu-Schäffer, and P. Stratmann, “Adapting highly-dynamic compliant movements to changing environments: A benchmark comparison of reflex-vs. cpg-based control strategies,” _Frontiers in Neurorobotics_ , vol. 15, 2021.
  * [30] A. Iscen, K. Caluwaerts, J. Tan, T. Zhang, E. Coumans, V. Sindhwani, and V. Vanhoucke, “Policies modulating trajectory generators,” in _Conference on Robot Learning_. PMLR, 2018, pp. 916–926.
  * [31] G. C. Goodwin, S. F. Graebe, and M. E. Salgado, _Control System Design_ , 1st ed. USA: Prentice Hall PTR, 2000.
  * [32] K. J. Astrom and R. M. Murray, _Feedback Systems: An Introduction for Scientists and Engineers_. USA: Princeton University Press, 2008.
  * [33] C. Della Santina, M. Bianchi, G. Grioli, F. Angelini, M. Catalano, M. Garabini, and A. Bicchi, “Controlling soft robots: balancing feedback and feedforward elements,” _IEEE Robotics & Automation Magazine_, vol. 24, no. 3, pp. 75–83, 2017.
  * [34] T. Johannink, S. Bahl, A. Nair, J. Luo, A. Kumar, M. Loskyll, J. A. Ojea, E. Solowjow, and S. Levine, “Residual reinforcement learning for robot control,” in _2019 International Conference on Robotics and Automation (ICRA)_. IEEE, 2019, pp. 6023–6029.
  * [35] A. J. Ijspeert, “Central pattern generators for locomotion control in animals and robots: A review,” _Neural Networks_ , vol. 21, no. 4, pp. 642–653, 2008, robotics and Neuroscience.
  * [36] L. Righetti, J. Buchli, and A. J. Ijspeert, “Dynamic hebbian learning in adaptive frequency oscillators,” _Physica D: Nonlinear Phenomena_ , vol. 216, no. 2, pp. 269–281, 2006.
  * [37] A. J. Ijspeert, A. Crespi, D. Ryczko, and J.-M. Cabelguen, “From swimming to walking with a salamander robot driven by a spinal cord model,” _science_ , vol. 315, no. 5817, pp. 1416–1420, 2007.
  * [38] M. Hildebrand, “Symmetrical gaits of horses,” _Science_ , vol. 150, no. 3697, p. 701–708, 1965.
  * [39] Z. E. Bhatti, “Gait analysis and biomechanics of quadruped motion for procedural animation and robotic simulation,” 2017.
  * [40] C. Della Santina, D. Lakatos, A. Bicchi, and A. Albu-Schaeffer, “Using nonlinear normal modes for execution of efficient cyclic motions in articulated soft robots,” in _International Symposium on Experimental Robotics_. Springer, 2020, pp. 566–575.
  * [41] A. Albu-Schäffer and C. Della Santina, “A review on nonlinear modes in conservative mechanical systems,” _Annual Reviews in Control_ , vol. 50, pp. 49–71, 2020.
  * [42] J. Bergstra, R. Bardenet, Y. Bengio, and B. Kégl, “Algorithms for hyper-parameter optimization,” in _Advances in Neural Information Processing Systems_ , J. Shawe-Taylor, R. Zemel, P. Bartlett, F. Pereira, and K. Weinberger, Eds., vol. 24. Curran Associates, Inc., 2011.
  * [43] T. Akiba, S. Sano, T. Yanase, T. Ohta, and M. Koyama, “Optuna: A next-generation hyperparameter optimization framework,” in _Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining_, ser. KDD ’19. New York, NY, USA: Association for Computing Machinery, 2019, p. 2623–2631.
  * [44] A. Kuznetsov, P. Shvechikov, A. Grishin, and D. Vetrov, “Controlling overestimation bias with truncated mixture of continuous distributional quantile critics,” in _Proceedings of the 37th International Conference on Machine Learning_ , ser. ICML’20. JMLR.org, 2020.
  * [45] A. Raffin, “Rl baselines3 zoo,” 2020.
  * [46] 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\.


Functional variant of Polynomial Analogue
of Gandy’s Fixed Point Theorem

Andrey Nechesov

Sobolev Insitute of Mathematics, Novosibirsk

<EMAIL_ADDRESS>
Abstact In this work, a functional variant of the polynomial analogue of the
classical Gandy’s fixed point theorem is obtained. Sufficient conditions have
been found to ensure that the complexity of the recursive function does not go
beyond the polynomial.

Introduction In 2021, we proved a polynomial analogue of the classical Gandy’s
fixed point theorem [1]. This became an important impetus for the construction
of p-complete programming languages. And such a language was first built by us
in 2022. The main result of that work was: a solution of the problem $P=L$.
[2] Next are the followers of the works on building a new high-level language
and the idea of building a general programming methodology. But there was one
gap in our research: classes of recursive functions whose complexity was
polynomial were not described.

In this work we found sufficient conditions for such functions. In many ways,
the main ideas of this work are similar to the ideas that we used in the proof
of the polynomial analogue of Gandy’s fixed point theorem. But there are also
striking differences. Functions, as such, differ quite strongly from
predicates precisely in the multitude of their values. If a predicate is
either true or false, then a function can generally take on a variety of
values.

Moreover, even if there are not many values, but there is recursion and simple
multiplication, then powers and factorials may arise during the calculations,
which, of course, can violate the polynomial computational complexity of this
function. Therefore, finding these restrictions on recursive functions that
would be soft enough for the class of functions to be large, and at the same
time tough enough not to go beyond polynomiality, has been a problem for us
for the last 3 years, after the proof of the polynomial analogue Gandy’s fixed
point theorem in the case of predicate extensions.

In this work, we will inductively expand the function itself, and not the
truth set of the predicate, which fundamentally distinguishes these two
approaches.

Let <HW($\mathfrak{M}$),$\sigma$> – p-computable hereditary finite list
superstructure from [1].
Let $f_{1},\dots,f_{n}$ – p-computable functions and all $f_{i}$ in the
signature $\sigma$. Then we can define a new finite or countable generative
family of the terms $T_{i}$ of the signature $\sigma$ for each $f_{i}$:

$T_{i}=\\{t_{j}(x_{1},\dots,x_{k_{j}})\ |\ j\in N\\},\ i\in[1,\dots,n]$ (1)

by default we assume that any $f_{j}$ can be included in any term $t_{k}$ of
any family $T_{i}$.

Let also for each family of terms $T_{i}$ is defined p-computable function
$\gamma_{i}$:

$\gamma_{i}:HW(M)\to T_{i}\cup\\{false\\}$ (2)

By default, we assume that the false element $false\in M$. And in the future,
if the function $f(w)$ ($f\in\sigma$) takes the value $false$, then we will
denote this as $f(w)\uparrow$, and denote $f(w)\downarrow$ otherwise. The
domain of definition $dom(f)$ of a function $f$ will be considered to be all
elements $w$ on which $f(w)\downarrow$.

Define the extention $f^{(n+1)}_{i}$ for each $f^{(n)}_{i}$ (where
$f^{(0)}_{i}=f_{i}$) and

$f^{(n+1)}_{i}|_{dom(f^{(n)}_{i})}=f^{(n)}_{i}|_{dom(f^{(n)}_{i})}$ (3)

using a p-computable function $\gamma_{i}:HW(M)\to T_{i}\cup\\{false\\}$ such
that on (n+1)-iteration we have:

$f^{(n+1)}_{i}(w)=\left\\{\begin{array}[]{lr}f_{i}(w)\text{, if
}f_{i}(w)\downarrow,\text{ else }\\\
\gamma_{i}(w)^{\overline{x}}_{\overline{w}}\text{, if }\gamma_{i}(w)\neq
false\text{ and }|\overline{x}|=|\overline{w}|\\\ false\text{, otherwise
}\end{array}\right.$ (4)

and then we are expanding the function $f_{i}$ to $f^{(n+1)}_{i}$ and go to
the next iteration.

Define, $f\subseteq g\Leftrightarrow dom(f)\subseteq dom(g)\text{ and
}f|_{dom(f)}=g|_{dom(f)}$.

Using families of the terms $T_{i}$, p-computable functions $\gamma_{i}$ and
equality 4 we can define the operator:

$\Gamma^{<HW(\mathfrak{M}),\sigma>}_{f_{1},\dots,f_{n}}:\\{g|\ g:HW(M)\to
HW(M)\\}^{n}\to\\{g|\ g:HW(M)\to HW(M)\\}^{n}$ (5)

satisfying the following rules

$\Gamma^{<HW(\mathfrak{M}),\sigma>}_{f_{1},\dots,f_{n}}(g^{(k)}_{1},\dots,g^{(k)}_{n})=(g^{(k+1)}_{1},\dots,g^{(k+1)}_{n})$
(6)

where $g_{i}^{(k)}\subseteq g_{i}^{(k+1)}$.

The operator $\Gamma^{<HW(\mathfrak{M}),\sigma>}_{f_{1},\dots,f_{n}}$ is
monotonic and has the property of a fixed point $(g^{*}_{1},\dots,g^{*}_{n})$;
moreover, the fixed point is reached in $\omega$ steps:

$\Gamma^{<HW(\mathfrak{M}),\sigma>}_{f_{1},\dots,f_{n}}(f^{*}_{1},\dots,f^{*}_{n})=(f^{*}_{1},\dots,f^{*}_{n})$
(7)

where $g_{i}^{*}=g_{i}^{(\omega)}$, $i\in[1,\dots,n]$

Define a set of free variables of a term or formula as $V(t(\overline{x}))$
and $V(\varphi(\overline{x}))$ respectively, where
$\overline{x}=(x_{1},\dots,x_{n})$ for some $n\in N$. Denote
$V_{x}(\varphi(\overline{x},\overline{y}))$ and
$V_{y}(\varphi(\overline{x},\overline{y}))$ the set of variable $\\{x_{i}\\}$
such that $x_{i}\in V(\overline{x})$ and $\\{y_{i}\\}$ such that $y_{i}\in
V(\overline{y})$. Also denote fpor
$t^{\overline{y}}(\overline{x},\overline{y})$ is term where we replaced all
occurences $f_{j}(x_{i})$ on $y_{i}$ in the term
$t(\overline{x},\overline{y})$.

As in the case of the polynomial analogue of Gandy’s fixed point theorem, we
define the concept of a GNF-system as a tuple:

$GNF=(\Sigma,\sigma,\Omega,L,HW(M),\Omega,F,T,G)$

We will say that a GNF-system is a p-computable if the model
$HW(\mathfrak{M})$ is a p-computable, all $\gamma_{i}\in G$ is a p-computable
and if the following conditions are met:

  * •

if $f_{j}$ is included in some $t_{k}$ then only of the form $f_{j}(x_{i})$
for any $x_{i}$

  * •

$f_{j}(x_{i})$ and $f_{k}(x_{i})$ do not belong to any term simultaneosly for
any $x_{i}$

  * •

for any $t_{j}^{\overline{y}}(\overline{x},\overline{y})$ it’s not true that
there is such $i\in N$ that $x_{i}\in
V(t_{j}^{\overline{y}}(\overline{x},\overline{y}))$ and $y_{i}\in
V(t_{j}^{\overline{y}}(\overline{x},\overline{y}))$

  * •

for any $T_{k}$ there exists C and p such that for any $t_{j}\in T_{k}$
computational complexity $t(t_{j}^{\overline{y}}(\overline{x},\overline{y}))$
do not exceed $C\cdot(|\overline{x}|+|\overline{y}|)^{p}$

  * •

if $V_{y}(t_{j}^{\overline{y}}(\overline{x},\overline{y}))\neq\varnothing$
then the value of the term $|t_{j}^{\overline{y}}(\overline{w},\overline{l})|$
do not exceed $|\overline{w}|+|\overline{l}|$ for any $t_{j}\in T_{k}$, for
any evaluates $w_{i},l_{j}\in HW(M)$ of the tuples $\overline{x}$ and
$\overline{y}$ respectively.

$\textbf{Theorem (Functional variant of Polynomial Analogue}\\\ \textbf{ of
Gandy's Fixed Point Theorem)}:$ Let p-computable GNF-system with p-computable
initial functions $f_{1},\dots,f_{n}$ be given, then the smallest fixed point
$\Gamma(\overline{f})$ of the operator
$\Gamma^{<HW(\mathfrak{M}),\sigma>}_{f_{1},\dots,f_{n}}$ is p-computable.

Proof: By induction on the rank $r(w)$ of the element $w$ we prove two
statements simultaneously. First,

$|f_{i}(w)|\leq C\cdot|w|^{p}$ (8)

and second, that the computational complexity of the algorithm does not exceed
the following:

$t(f_{i}(w))\leq 36\cdot C^{p+1}\cdot(r(w)+1)\cdot|w|^{p^{2}+1}$ (9)

Base of induction: $n=0$. Then for some $a\in M$ we have $|f_{i}(a)|\leq
C\cdot|a|^{p}$ and $t(f_{i}(a))\leq C\cdot|a|^{p}$ because initial function
$f_{i}$ is a polynomial computable.
Step of induction: Let the statement be true for everyone $k<n$ then show that
for $k=n$:

If initial polynomial function $f(w)\downarrow$ then obviosly.
Else if $\gamma(w)=false$ then obviously.
Else if $\gamma(w)\neq false$ then consider two cases for $I=\\{i|y_{i}\in
t^{\overline{y}}_{j}(\overline{x},\overline{y})\\}$:
1) $I=\varnothing$ then by conditions for p-computable GNF-system:

$|f_{i}(w)|\leq|[\gamma(w)](\overline{w})|=|t_{j}(w_{1},\dots,w_{n})|\leq
C\cdot|w|^{p}$ (10)

and it is true by definition of p-computable GNF-system.

For complexion we have next:

$t(f_{i}(w))\leq
r_{in}+r_{\gamma_{i}}+t([\gamma_{i}(w)](\overline{w}))+r_{1}=t([\gamma_{i}(w)^{\overline{y}}](\overline{w}_{x},\overline{v}_{y}))+r_{1}+r_{in}+r_{\gamma_{i}}\leq$
$\leq
C\cdot(|\overline{w}_{x}|+|\overline{v}_{y}|)^{p}+r_{1}+r_{in}+r_{\gamma_{i}}\leq$
$\leq C\cdot|\overline{w}|^{p}+r_{1}+r_{in}+r_{\gamma_{i}}\leq 36\cdot
C^{p+1}\cdot(r(w)+1)\cdot|w|^{p^{2}+1}$ (11)

because $\overline{v}$ is empty and where

  * •

$r_{in}$ the complexity of checking the value of the initial function $f(w)$,
complexity does not exceed $C\cdot|w|^{p}$

  * •

$r_{\gamma_{i}}$ the complexity of the function $\gamma_{i}(w)$ for
construction the term $t_{j}(x_{1},\dots,x_{n})$, complexity does not exceed
$C\cdot|w|^{p}$

  * •

$r_{1}$ complexity of the replacement function which replace $f_{j}(w_{i})$ on
$v_{i}$.

2) if $I\neq\varnothing$ then:

$|f_{i}(w)|=|[\gamma_{i}(w)](\overline{w})|=|[\gamma_{i}(w)]^{\overline{y}}(\overline{w}_{x},\overline{v}_{y})|\leq|\overline{w}_{x}|+|\overline{v}_{y}|\leq
C\cdot|\overline{w}|^{p}$ (12)

where $v_{i}=f_{j_{i}}(w_{i})$ for $v_{i}\in\overline{v}_{y}$ and $|v_{i}|\leq
C\cdot|w_{i}|^{p}$ by induction.

For complexion we have next:

$t(f_{i}(w))\leq r_{\gamma_{i}}+t([\gamma_{i}(w)](\overline{w}))+r_{1}\leq
t([\gamma_{i}(w)^{\overline{y}}](\overline{w}_{x},\overline{v}_{y}))+r_{1}+r_{2}+r_{\gamma_{i}}+\sum_{i\in
I}t(f(w_{i}))\leq$ $\leq
C\cdot(C\cdot|w|^{p})^{p}+r_{1}+r_{2}+r_{\gamma_{i}}+\sum_{i=1}^{n}36\cdot
C^{p+1}\cdot(r(w)-1+1)\cdot|w_{i}|^{p^{2}+1}\leq$ $\leq 36\cdot
C^{p+1}\cdot(r(w)+1)\cdot|w|^{p^{2}+1}$ (13)

## References

  * [1] Goncharov, S.; Nechesov, A. Polynomial Analogue of Gandy’s Fixed Point Theorem. Mathematics 2021, 9, 2102. https://doi.org/10.3390/math9172102
  * [2] Goncharov, S.; Nechesov, A. Solution of the Problem P = L. Mathematics 2022, 10, 113. https://doi.org/10.3390/math10010113