# Evolutionary-Based Online Motion Planning Framework for
Quadruped Robot Jumping

Linzhu Yue1, Zhitao Song1, Hongbo Zhang1, Xuanqi Zeng1, Lingwei Zhang2, and
Yun-Hui Liu1 1 L. Z. Yue, Z. T. Song, H. B. Zhang, X. Q. Zeng, and Y.-H. Liu
are with the Department of Mechanical and Automation Engineering, The Chinese
University of Hong Kong<EMAIL_ADDRESS>L. W. Zhang is with the Hong
Kong Centre for Logistics Robotics. * Corresponding author: Y.-H. Liu
<EMAIL_ADDRESS>InnoHK Clusters support this work via the Hong Kong
Centre of Logistics Robotics.

###### Abstract

Offline evolutionary-based methodologies have supplied a successful motion
planning framework for the quadrupedal jump. However, the time-consuming
computation caused by massive population evolution in offline evolutionary-
based jumping framework significantly limits the popularity in the quadrupedal
field. This paper presents a time-friendly online motion planning framework
based on meta-heuristic Differential evolution (DE), Latin hypercube sampling,
and Configuration space (DLC). The DLC framework establishes a
multidimensional optimization problem leveraging centroidal dynamics to
determine the ideal trajectory of the center of mass (CoM) and ground reaction
forces (GRFs). The configuration space is introduced to the evolutionary
optimization in order to condense the searching region. Latin hypercube
sampling offers more uniform initial populations of DE under limited sampling
points, accelerating away from a local minimum. This research also constructs
a collection of pre-motion trajectories as a warm start when the objective
state is in the neighborhood of the pre-motion state to drastically reduce the
solving time. The proposed methodology is successfully validated via real
robot experiments for online jumping trajectory optimization with different
jumping motions (e.g., ordinary jumping, flipping, and spinning).

##  I INTRODUCTION

A crucial aspect of a quadrupedal robot’s capacity to traverse various
terrains is its ability to perform jumping motions in tough natural
surroundings. To adapt to uneven terrains, many researchers have focused on
locomotion via diverse gaits (e.g., bounding, walking). Some works have
already yielded outstanding results, such as high-speed bounding in [1] and
[2]. However, crossing over unavoidable obstacles (e.g., deep canals and
roadblocks) usually requires a robust and high-performance jumping motion
controller. A core difficulty for quadruped jumping is generating trajectories
in real time under kino-dynamic constraints [3] (e.g., physical constraints).
[4] and [5] have already achieved unforgettable results. However, the
laborious calculation of offline trajectories makes it difficult or impossible
to apply to jobs involving frequent re-planning. This motivates the
development of a unified framework that satisfies online planning.

Figure 1:  Various jumping motion experiments to validate the proposed online
motion framework. (1) Two-leg vertical jumps with $\theta=\frac{\pi}{2}$. (2)
Back-flip jumps with $\theta=-2\pi$. (3) Back-flip jumps from 0.3 (m) height
platform (4) Four-leg vertical jumps reach the max height of 0.7 (m).

Some publications address jumping trajectory optimization issues subject to
complex kino-dynamics constraints using Reinforcement Learning (RL). The RL
approach has shown a remarkable capacity for complicated locomotion on legged
robots[6, 7, 8]. Recently, some works have used RL to deal with the jumping of
quadruped robots. Learned policies, inspired by cat landing behavior, were
used to control the robot’s posture in the landing phases.[9]. However, few
works are focusing on planning multiple complicated jumping motions using a
single policy.

Gradient-based trajectory optimization is a commonly employed optimization
method in robot jumping control. The MIT research uses gradient-based
optimization algorithms to assist the robots Cheetah 3 jump on a high desk
(0.76 (m)) and Mini-Cheetah to cover a variety of jumping motions with an
online 3-D jumping trajectory optimization approach[10, 11], respectively.
Similar to [12], they use collocation-based optimization to build offline
trajectories over dynamically-feasible barriers. Additionally, [13] utilized a
mixed-integer convex program to circumvent the reference motion limits;
however, this method must be optimized offline.

Heuristic algorithms can efficiently solve optimization problems with complex
constraints, which supplies a new approach for generating jumping motions.
Differential Evolution (DE) is a heuristic-based algorithm proposed by Storn
and Price [15]. DE algorithms have been utilized in robotics, signal
processing, and other industries to address complicated optimization problems
[20]. In our previous work, DE is employed to generate offline jumping
trajectories for a quadrupedal robot [16]. However, this offline approach is
inherently inferior for systems with online re-planning requirements.
Moreover, the technique called Latin hypercube sampling (LHS) can be used to
generate an initialization population for DE, increasing the convergence speed
in low-dimensional space (typically less than 20 dimensions)[18, 17].

In our work, we try to accelerate the DE algorithm through three techniques:
search space compressing without losing the jumping motion performance,
careful selection of the initial population, and a warm start by pre-
calculation. By adding the conditioned configuration space of the robot, the
smaller searching space enables the DE approach to reduce the population and
the number of iterations, hence accelerating the optimization time. The LHS
gives more uniform initial populations of the DE algorithm, which accelerates
away from the local minimum. Also, when the desired state is in close
proximity to solved states saved in the pre-motion library, pre-calculated
optimization variables can be shared with new evolution as a warm start. To
sum up, the DE algorithm based on C-space, LHS, optimization variables
transformation, and Pre-motion library is used to construct the proposed
framework.

In this work, we intend to answer the following questions: a) How to design a
time-friendly optimization framework for online motion planning using an
evolution-based technique? b) How do the configuration space, Latin hypercube
sampling, and optimization variables transformation accelerate the convergence
speed of the optimization? c) How to produce a series of trajectories for the
Pre-motion Library?

Our primary contributions can be shown as follows:

  1. 1.

A time-friendly online motion planning framework for quadruped jumping based
on the meta-heuristic Differential evolution, Latin hypercube sampling, and
Configuration space (DLC) algorithm is proposed, which can generate various
jumping trajectories online.

  2. 2.

We creatively combine configuration space, Latin hypercube sampling, and the
Pre-motion Library to reduce optimization time.

  3. 3.

The algorithm has been verified online by various jumps on a real quadruped
robot (see Fig. 1).

Moreover, the current study differs from our prior work [16] in that it only
addresses how to solve a quadruped robot jumping problem by an evolutionary
algorithm but does not consider how to overcome the time-consuming
restriction.

##  II Models and dynamics

The objective of this section is to present the centroidal dynamics and 2D
planar model for the DLC framework. The reduced-order dynamic model of jumping
motion treats the robot as a single rigid body (SRB) with a specified moment
of inertia for the optimization process. Moreover, this work considers the 2D
planar model (i.e., sagittal and coronal planes) to the framework as shown in
Fig. 2 and Fig. 3. The $\bm{x}$ presents the system state.

$\displaystyle\bm{x}:=[{\bm{P}_{C}^{T}}\quad{\bm{\Theta}^{T}}\quad{\bm{V}_{C}^{T}}\quad^{B}{\bm{\omega}^{T}}]^{T}\in\mathbb{R}^{12}$
(1a)
$\displaystyle{\bm{Q}}:=[{\bm{q}_{i}}\quad{\dot{\bm{q}}_{i}}]\in\mathbb{R}^{24}$
(1b)

where ${\bm{P}_{C}}\in\mathbb{R}^{3}$ is the position of the robot center of
mass (CoM) w.r.t inertial frame; ${\bm{\Theta}\in\mathbb{R}^{3}}$ represents
the Euler angles of the robot; ${\bm{V}_{C}\in\mathbb{R}^{3}}$ is the velocity
of the CoM. ${}^{B}{\bm{\omega}}\in\mathbb{R}^{3}$ is the angular velocity of
CoM represented in the robot frame $B$. $\bm{q}_{i}\in\mathbb{R}^{3}$ and
$\bm{\dot{}}{\bm{q}}_{i}\in\mathbb{R}^{3}$ are the joint angles and velocities
of each leg. $i$ is the number of feet. The GRFs
${\bm{u}}:=[{\bm{f}_{i}}]\in\mathbb{R}^{12},{\bm{f}_{i}}\in\mathbb{R}^{3}$ is
the dynamic system control input at each contact point acquired by
optimization. ${\bm{r}_{i}}$ is the vector from CoM to the robot foot. Then
the body net wrench $\mathcal{F}\in\mathbb{R}^{6}$ of the CoM is shown as
follows:

$\displaystyle\mathcal{F}=\left[\begin{array}[]{c}\bm{F}_{\textrm{c}}\\\
\bm{\tau}_{\textrm{c}}\end{array}\right]=\sum_{i=1}^{4}\left[\begin{array}[]{l}\bm{f}_{i}\\\
\bm{r}_{i}\times\bm{f}_{i}\end{array}\right],$ (6)

where $\bm{F}_{\textrm{c}}$ and $\bm{\tau}_{\textrm{{c}}}$ represent the total
force and torque of CoM. Moreover, the simplified model for jumping motions
decreases the 18 Degrees-of-Freedom (DoFs) to 7 (including 6 leg joints and an
angle of the jumping plane, see Fig. 3).

Then the equations of the centroidal dynamics model[22] are given in (7) along
with the coordinates defined in Fig. 2.

$\displaystyle\ddot{\bm{P}}_{C}(t)$
$\displaystyle=\frac{\sum_{i=1}^{4}\bm{f}_{i}}{m}-{\bm{g}}$ (7a)
$\displaystyle\frac{\mathrm{d}({\bm{I}\bm{\omega}})}{\mathrm{d}t}$
$\displaystyle=\bm{\tau}_{\textrm{c}}+\bm{0}_{3\times
1}\times(\mathrm{m}\cdot{}\bm{g}),$ (7b)

where ${\bm{g}}\in\mathbb{R}^{3}$ represents gravitational acceleration.
${{}^{B}\bm{I}}\in\mathbb{R}^{3\times 3}$ is the robot’s rotation inertial
tensor which is assumed as a constant in this work,
$\textrm{diag}(^{B}\bm{I})=[0.07,0.26,0.242]^{T}$. In addition, our framework
classifies jumping motions into four phases: four-foot contact, two-foot
contact, flying phase, and landing phase.

Figure 2: A model of a single rigid body (SRB) utilized in the framework for
optimization. The blue arrow represents the CoM to the plantar position
vector, while the red arrow represents the Ground Reaction Forces (GRFs).

Figure 3: 2D planar models schematic diagram used in DLC framework. (a) and
(b) represent the sagittal plane and coronal plane, respectively. The red
arrow indicates the GRFs of different jumping planes. The red area indicates
that the 2D planar model reduces the 18 DoFs for diverse jump motions to 7
DoFs. Figure 4: Overview of Online DLC optimization jumping framework, based
on LHS, DE, and C-space. The red dot line means using the trajectory from the
Pre-motion Library. The motion planning procedure is shown by the blue blocks.
The low-level controller is shown by the green blocks.

##  III Jumping Motion Planning Framework

To design a time-friendly optimization framework for online motion planning,
we improve the meta-heuristic Differential evolution algorithm by introducing
the Latin Sampling algorithm to replace the random initial population and the
Configuration space to further reduce the optimization algorithm’s search
domain. Additionally, the pre-motion library is also used as the warm-start.

###  III-A Optimization Formulation

The objective of this section is to build the optimization problem and
optimization objectives. Additionally, unlike the gradient-based method, our
evolutionary-based optimization framework’s cost function is a well-designed
priority hierarchical fitness function.

$\displaystyle\begin{aligned}
&\underset{D_{\textrm{opt}}}{\text{minimize}}&&10^{L}-\sum\limits_{n=3}^{L}(10^{n-3}\sigma_{n}W_{n})+W_{1}\zeta\\\
&\text{subject to}&&\bm{x}\left(k+1\right)=\bm{x}\left(k\right)+{\Delta
t}\dot{\bm{x}}\left(k\right)\\\
&&&\bm{\dot{}}{\bm{x}}_{k+1}=g(\bm{u}_{k},\bm{x}_{k})\\\
&&&\bm{x}_{k}\in\mathbb{X},k=1,2,\cdots,N\\\
&&&\bm{u}_{k}\in\mathbb{U},k=1,2,\cdots,N\\\
&&&\bm{q}_{k}\in\mathbb{Q},k=1,2,\cdots,N\\\
&&&\bm{x}\left(0\right)=\bm{x}_{0},\bm{x}\left(N\right)=\bm{x}_{\textrm{target}}\end{aligned}$
(8)

where $\zeta=\int_{0}^{T}(|\bm{\tau}(t)\bm{\dot{q}}(t)|)dt$ is the energy
consumption of the motion. $D_{\textrm{opt}}$ is the optimization variables
whose meaning and selection are elaborated in the next section.
${\sigma}_{n}\in\mathbb{R}$ is the differences between the system state
produced by the evolutionary algorithm optimization iteration process and the
feasible set specified by C-space. $W_{n}\in[0,1]$ is a weight that indicates
the significance of one constraint to the optimization problem. $N$ is the
evolution population number (ref to Algorithm 1); $L\in\mathbb{R}$ is the
total number of layering priority constraints. $\mathbb{X}$, $\mathbb{U}$ and
$\mathbb{Q}$ are the feasible sets according to kino-dynamics constraints.
$\bm{x}\left(0\right)$ and $\bm{x}\left(N\right)$ are the initial state and
the desired state for the robot;
$\bm{\dot{}}{\bm{x}}_{k+1}=g(\bm{u}_{k},\bm{x}_{k})$ represents the centroidal
dynamics combination form with respect to (7a) and (7b).

###  III-B Optimization Parameters and Transformation

The objective of this section is to design optimization variables for the DLC
framework of different jump motions. We utilize the system state as the
optimization variable instead of employing polynomial parameters.

Here, the scenario of front jumping in the sagittal plane illustrates how to
generate the optimization variables and do the optimization variables
transformation.
Assumption 1: The force along the y-axis is zero.
Assumption 2: Leg 0 and leg 1 has the equivalent force, the same as the rear
two legs. That is, $\bm{f}_{0}=\bm{f}_{1}$ and $\bm{f}_{2}=\bm{f}_{3}$.
Assumption 3: The x-axis force of the front and back feet are equal when
${t}\in[0,{t}_{1}]$. Based on the assumptions, the equation of GRFs of the
front jump can be simplified as follows:

$\displaystyle\bm{f}_{i}$
$\displaystyle=\left\\{\begin{array}[]{rcl}a_{1}t+a_{0}&&{{t}\in[0,{t}_{1}]}\\\
b_{2}t^{2}+b_{1}t+b_{0}&&{{t}\in\left[{t}_{1},{t}_{2}\right]}\\\
0&&{{t}\in\left[{t}_{2},{t}_{3}\right]}\end{array}\right.,$ (9d)
$\displaystyle\Lambda$ $\displaystyle=[a_{0},a_{1},b_{0},b_{1},b_{2}],$ (9e)

By using a 2D simplified model of front jumping motion, the robot state can be
represented as $\bm{s}_{\Omega}(t)=[x_{c},z_{c},\theta]$, where
$[x_{c},z_{c}]$ are the position of CoM and $\theta$ is the pitch angle. We
can get the analytical expression of ${\bm{s}_{\Omega}(t)}$ from GRFs given in
(9d) using the centroidal dynamics models. In addition, there are 12
polynomial coefficients for one jump motion according to assumption 2. The
robot’s state should then ideally be utilized for optimization. Furthermore,
to easily bound the $\Lambda$, we convert polynomial coefficients into
expressions based on $\bm{s}_{\Omega}(t)$. we choose robot states under four
time points together with three durations of different jumping phases
($[\frac{t_{1}}{2},t_{1},t_{2},t_{3}]$). Then, we can select the optimization
variables given in (10).

$\displaystyle\bm{D}_{\textrm{opt}}:=[\bm{s}_{\Omega}(\frac{t_{1}}{2}),\bm{s}_{\Omega}(t_{1}),\bm{s}_{\Omega}(t_{2}),t_{opt}]^{T}\in\mathbb{R}^{12},$
(10)

input :
$\bm{s}_{t},\bm{O}_{k},{\bm{D}}_{\textrm{res}}^{*},{\textrm{Maxgen}},NP,\bm{D}_{\textrm{opt}},r,\varepsilon$

1

output : ${\bm{D}_{\textrm{res}}}$

2 _$g\leftarrow
1,\bm{k}\leftarrow[{\bm{s}_{t}},{\bm{O}_{k}}],{\bm{s}_{m}\in\mathbb{R}^{12}\leftarrow\bm{D}_{\textrm{opt}}}$
_;

3

4 _$\bm{\Omega_{s}}\leftarrow\\{\bm{s}_{m}\ \arrowvert\ s_{m,1\sim
9}\in{\bm{\Omega}_{C}},s_{m,10\sim 12}\in{\bm{\Omega}_{T}}\\}$ _;

5

6 _$\bm{\Omega}_{s}^{*}\leftarrow\\{\bm{s}_{m}\in\bm{\Omega}_{s}\ \arrowvert\
\Arrowvert\bm{s}_{m}-{\bm{D}_{\textrm{res}}^{*}}\Arrowvert <{r}\\}$_;

7

8if  _$\Arrowvert\bm{s}_{t}-{\bm{s}_{t}^{*}}\Arrowvert_{2} <\varepsilon$_ then

9 _$\bm{s}_{m}(g)\leftarrow LHS({\bm{\Omega}_{s}},NP)$_ ;

10

11 else

12 _$\bm{s}_{m}(g)\leftarrow LHS({\bm{\Omega}^{*}_{s}},NP)$_ ;

13

14 end if

15while  _Fitness( $\bm{D}_{\textrm{res}}(g),{\bm{k}})>{\varepsilon}\ \bm{or}\
g<\rm{Maxgen}$_ do

16 for  _$m\leftarrow 1$ to $NP$_ do

17 _Mutation and Crossover_ ;

18 for  _$n\leftarrow 1$ to $12$_ do

19 $v_{m,n}(g)\leftarrow M(s_{m,n}(g))$;

20 $u_{m,n}(g)\leftarrow C(s_{m,n}(g),v_{m,n}(g))$;

21

22 end for

23  _Selection_ ;

24 if  _Fitness(
${\bm{U}}_{m}(g),{\bm{k}}$)$<$Fitness(${\bm{s}}_{m}(g),{\bm{k}}$)_ then

25 _${\bm{s}}_{m}(g)\leftarrow{\bm{U}_{m}(g)}$_ ;

26 if  _Fitness(
${\bm{s}}_{m}(g),{\bm{k}}$)$<$Fitness(${\bm{D}}_{\textrm{res}}(g),{\bm{k}}$)_
then $\bm{D}_{\textrm{opt}}\leftarrow{\bm{s}}_{m}(g)$ ;

27

28 else

29 ${\bm{s}_{m}(g)}\leftarrow\bm{s}_{m}(g)$;

30

31 end if

32

33 end for

34  _$g\leftarrow g+1$_ ;

35 end while

36

Algorithm 1 DLC Algorithm

###  III-C C-space and Kino-dynamic Constraints

This section aims to build the configuration space (C-space)x. We introduce
the kino-dynamic constraints including joint constraints, contact force
constraints, and friction constraints [16] to generate the C-space, which
makes this optimization problem lie in a much smaller searching region.
Inspired by Ding’s work[13], we search for
$\bm{s}_{\Omega}(\bm{t}_{\textrm{opt}})$ and $\bm{t}_{\textrm{opt}}$ of
$\bm{D}_{\textrm{opt}}$ in two independent spaces, configuration space
(C-space) $\bm{\Omega}_{C}\subset\mathbb{R}^{3}$ and time-space (T-space)
$\bm{\Omega}_{T}\subset\mathbb{R}^{3}$, respectively. The definition of
$\bm{\Omega}_{C}$ and $\bm{\Omega}_{T}$ are as follows:

$\displaystyle\begin{aligned}
\bm{\Omega}_{C}:=\\{\bm{s}_{\Omega}\in\mathbb{R}^{3}\ \arrowvert\
\bm{q}_{\textrm{min}}<\bm{q}(\bm{s_{\Omega}})<\bm{q}_{\textrm{max}},\\\
\bm{z}_{\textrm{hip}}(\bm{s_{\Omega}})>\bm{z}_{\textrm{min}},\\\
\bm{z}_{\textrm{knee}}(\bm{s_{\Omega}})>\bm{z}_{\textrm{min}}\\},\\\
\bm{\Omega}_{T}:=\\{\bm{t}_{\textrm{opt}}\in\mathbb{R}^{3}\ \arrowvert\
0.1<\bm{t}_{\textrm{opt}}<0.5\\},\end{aligned}$ (11)

where $\bm{\Omega}_{C}$ is a set of robot’s configurations $\bm{s}_{\Omega}$
in different jumping tasks and phases w.r.t. world frame, which satisfies
joint angle and joint position constraints. The constraint of joint position
($z_{\textrm{hip}}$ and $z_{\textrm{knee}}$) means that the hip joint and knee
joint should not be in contact with the ground during the jump.
$\bm{\Omega}_{T}$ is the time range of four feet contacts, two feet contacts,
and flight jumping phases that are manually selected. For $\bm{\Omega}_{C}$,
due to the complex relationship between $\bm{s}_{\Omega}$ and $\bm{q}$,
$\bm{z}_{\textrm{hip}}$, and $\bm{z}_{\textrm{knee}}$ the shape of
$\bm{\Omega}_{C}$ is difficult to describe with analytical formulas. The value
range of the three elements in $\bm{s}_{\Omega}$ depends on hardware
limitations. Then we split each value range into 50 equal parts to get 125000
points. Finally, the shape of $\bm{\Omega}_{C}$ can be obtained (see Fig. 5)
by removing the points that do not satisfy the constraints of joint angles and
joint positions. Therefore, for different jumping tasks and feet contact
modes, the DLC algorithm can directly optimize $\bm{s}_{\Omega}$ in the
corresponding $\bm{\Omega}_{C}$ to speed up the progress of finding local
optimal $\bm{s}_{\Omega}$.

Figure 5: The 3-dimensional (3D) configuration space for different jumping
tasks and contact modes. (a) Front jump configuration space with the front,
rear, and four feet contact modes. (b) Side jump configuration space with
left, right, and four feet contact modes.

Figure 6: The optimization time with the Pre-motion Library of four-leg front
jump motion and convergence comparison of DE algorithm with and without LHS.
(a) The DLC algorithm running time of the four contact front jumping task with
$\bm{D}_{res}^{*}$ of ${\bm{s}_{\Omega}^{*}}=[0.6,0.2,0]$ in Pre-motion
Library. The high-level information $\bm{s_{t}}=[x_{c},z_{c},0]$, where
$x_{c}\in[0.5,0.7]\ m,z_{c}\in[0.2,0.4]\ m$ and a sampling point was taken
every 0.005 (m) in the two directions. (b) DE algorithm with and without LHS.
Figure 7: The DLC framework solving time on four-leg jump, two-leg jump, and
back-flip with or without Pre-motion library. The solving time has random
noise ($\pm 0.05$ (m)) at desired $\bm{s}_{\Omega}$. (a), (c) and (e) are the
back-flip, four-leg jumping, and two-leg jumping solution times with the Pre-
motion Library. (b), (d) and (f) are the solution time without the Pre-motion
Library of those three jump motions. Figure 8: Different jumping motions
experiments to validate the proposed DLC framework. (a) Back-flip with desired
pitch angle at $\theta=-2\pi$(rad). (b) Side-flip with desired roll angle at
$\varphi=-2\pi$ (rad). (c) Two-leg vertical jump with desired pitch angle at
$\theta=-\frac{\pi}{2}$ (rad). (d) Four-leg vertical jump with desired height
of 0.8 (m). (e) Side jump with a desired distance of 0.3 (m). (f) Yaw-spinning
with desired yaw angle $\pi$ (rad). (g) Four legs continuous jump. (h) Rear
jump with desired distance 0.3 (m).

Figure 9: Joint angle and torque of the back-flip: leg 0 and leg 3 joint
angles are shown in (a) and (c). (b) and (d) represent the joint torques of
leg 0 and leg 3. Different color shadows of the figure show the different
jumping phases of the different legs.

###  III-D Pre-motion Library

This section aims to establish an offline library about a set of the 12 local
optimal optimization variables ($\bm{D}_{\textrm{res}}$) called the Pre-motion
Library to accelerate online optimization.

The central idea for building the Pre-motion Library is to generate a set of
$\bm{D}_{\textrm{res}}$ offline with 12 local optimal optimization variables
($\bm{D}^{*}_{\textrm{res}}$). According to the fixed step size ($\sim 0.05\
m$), $\bm{s}_{\Omega}$ is uniformly divided to obtain the target state of the
robot. Then, the obtained target robot states are input into the DLC
framework. The corresponding $\bm{D}^{*}_{\textrm{res}}$ are saved and
collected to form the Pre-motion Library. The library comprises 567
$\bm{D}_{\textrm{res}}$ representing various kinds of jumping motion (e.g.,
front/rear/side, backflip, side flip, two/four-leg jump). When re-planning is
required, pre-calculated optimization variables can be shared with new
evolution as a warm start.

An index file (Yaml-file) maintains all of the CoM’s pre-motion trajectories.
In addition, the Pre-motion file is $\sim 30$ Megabytes in size (MB). It will
be loaded into memory at the start of the controller’s engine. The desired
trajectory from the library is based on the minimum Euclidean distance with a
specified threshold (0.05 (m)), the input is the high-level information
$\bm{s}_{\Omega}$.

TABLE I: Average solve times for different jump motion type Jump Motion | Four-contact | Back-flip | Two-contact
---|---|---|---
With Pre-motion Library | 0.14 (s) | 0.79 (s) | 0.657 (s)
Without Pre-motion Library | 2.19 (s) | 5.7 (s) | 9.11 (s)
Offline DE[16] | 65 (s) | 167 (s) | 266 (s)

###  III-E Online DLC Algorithm

After the C-Space, Pre-motion Library, and optimization variables are
proposed, then the online DLC framework can be introduced.

The online DLC algorithm utilizes the prioritization fitness function (see
(8)) to search for solutions in C-space. We introduce ${\bm{\Omega}_{C}}$ and
${\bm{\Omega}_{T}}$ into the searching space ${\bm{\Omega}_{s}}$ to limit the
mutation region. Then, in contrast to the conventional DE algorithm’s random
population initiation, we use Latin hypercube sampling (LHS) to produce a more
uniform initial population distribution[29], which improves algorithm
iteration convergence speed (see Fig. 6). For the objective robot state
$\bm{s}_{t}$ whose Euclidean distance to $\bm{D}_{\textit{res}}^{*}(t_{3})$ is
less than the threshold $\varepsilon$, it is obtained from the Pre-motion
library, otherwise, it continues to use the LHS for initialization.

The details of the DLC algorithm are shown in algorithm 1, where
${\bm{s}_{t}}\in{\mathbb{R}^{3}}$ is the desired position and Euler angular of
the CoM and ${\bm{O}_{k}}\in{\mathbb{R}^{12}}$ is the location of obstacles
coming from the high-level information in our framework. Maxgen and ${NP}$
represent the maximum generation and population numbers, respectively. ${r}$
is the neighborhood radius of ${{\bm{D}}_{\textrm{res}}^{*}}$. ${\varepsilon}$
is the fitness value at which the algorithm stops and returns
$\bm{D}_{\textrm{res}}$, which is usually less than $\beta$. $g$ is the number
of the DLC generations, $M(\cdot)$, $C(\cdot)$, and $\textrm{LHS}(\cdot)$
present the mutation, crossover, and Latin hypercube sampling functions.
${\bm{U}_{m}(g)}$ is the unit vector w.r.t. optimization parameters.

##  IV Implementation Details and Experiments

This section’s primary objective is to experimentally verify the efficacy and
adaptability of the proposed framework via various jumping motion types with
the open-source MIT Mini-Cheetah[28]. The jumping controller uses a joint-
level PD controller with DLC generated torque. And a first-order low-pass
filter for $\bm{q}$ and $\bm{\tau}$ is used for the landing controller. In
order to protect the mechanical components of the robot, positive flexible
landing control is necessary, here we employ relatively small PD gains[16].

To study the solving efficiency of the proposed framework, we conduct
experiments on the trajectory of optimization on both the simulation and the
real robot. We do not just repeat the verification of the feasible solutions
in the jump library; rather, we conducted a small-scale randomization ($\pm
0.05(m)$ of the target position) of each offline-obtained feasible solution to
evaluate the algorithm’s adaptability. The optimization time for general
motions (without touching the C-space boundary and hardware limits) is often
less than 0.3 (s) (see Fig. 7) with the Pre-motion Library. Still, it will
take about 3-9 seconds to optimize actions with extreme boundaries (such as
the highest vertical jump or highest double-leg jump height). The average
solving time is shown in the Table. I. Using back-flip as an illustration, the
average optimization time spans from 197s to 0.79s, while the solution speed
is approximately 200 times faster. The DE algorithm with LHS typically
requires fewer iterations than the conventional initial population technique
(see Fig. 6). Our experiments organize into five categories: jumping motions,
flipping motions, flipping from a platform, yaw-spin jumps, and vertical
jumps. The supplementary video contains demonstrations of the experiments.

In the flipping motion studies, our framework is employed to validate the
back-flip, left-flip, and flip from a platform (see Fig. 8 and Fig. 1). The
robot can perform a backflip from a 34-centimeter-high platform and land
safely. For the second DLC technique, the offline-generated library is
maintained onboard. The experimental data for back-flip jumping is depicted in
Fig. 9. The experimental data shows that the torque is restricted at the
maximal joint torque of 24 (Nm), showing that the robot requires a great deal
of energy to leave the ground. Initially, we optimize the jumps using the
robot’s own computer (Intel ATOM x5-Z8350); however, with pre-motion, it takes
the robot around $\sim 3s$ or even large to optimize due to computational
restrictions. Hence, a remote computer optimized online and sent the robot’s
trajectory through UDP.

##  V CONCLUSIONS

In this paper, a novel online evolutionary-based time-friendly optimization
motion planning framework has been proposed for quadruped jumping. Experiments
show that an evolutionary-based method can be an alternative approach to
solving the complicated motion planning problems of legged robots.
Optimization variables transformation and C-space compress the DE searching
region, and Latin hypercube sampling gives a more uniform initial population
with limit points, which enhances the ability of the DE algorithm to escape
from the local minimum. Those three core contributions can give a very obvious
improvement in the convergence speed of the evolutionary algorithm. In
particular, a small-scale random perturbation to the feasible solution in the
pre-motion library is nevertheless capable of ensuring the approximate
convergence speed. At the same time, the feasible solution in Pre-motion
Library as a warm-start can significantly boost the framework optimization
progress. Experimental results indicate a significant reduction in the
convergence speed compared with our previous work[16].

Additionally, our framework prioritizes optimizing time consumption rather
than landing precision of jumping. And, the optimization time for extreme
cases which touch the C-space boundary (e.g., jumping to a high enough desk
(0.4 (m)) or side-flipping over high enough obstacles) still needs to be
shortened.

## References

  * [1] Di Carlo J, Wensing P M, Katz B, et al. Dynamic locomotion in the mit cheetah 3 through convex model-predictive control[C],2018 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS). IEEE, 2018: 1-9.
  * [2] Park, Hae-Won, Patrick M. Wensing, and Sangbae Kim. High-speed bounding with the MIT Cheetah 2: Control design and experiments. The International Journal of Robotics Research 36.2 (2017): 167-192.
  * [3] Donald B, Xavier P, Canny J, et al. Kinodynamic motion planning[J] Journal of the ACM (JACM), 1993, 40(5): 1048-1066.
  * [4] PARK, Hae-Won; WENSING, Patrick M.; KIM, Sangbae. Jumping over obstacles with MIT Cheetah 2. Robotics and Autonomous Systems, 2021, 136: 103703.
  * [5] N. Rudin, H. Kolvenbach, V. Tsounis and M. Hutter, Cat-Like Jumping and Landing of Legged Robots in Low Gravity Using Deep Reinforcement Learning, IEEE Transactions on Robotics, vol. 38, no. 1, pp. 317-328, Feb. 2022.
  * [6] Lee J, Hwangbo J, Wellhausen L, et al. Learning quadrupedal locomotion over challenging terrain[J], Science robotics, 2020, 5(47): eabc5986.
  * [7] Li Z, Peng X B, Abbeel P, et al. Robust and Versatile Bipedal Jumping Control through Multi-Task Reinforcement Learning[J]. arXiv preprint arXiv:2302.09450, 2023.
  * [8] Choi S, Ji G, Park J, et al. Learning quadrupedal locomotion on deformable terrain[J]. Science Robotics, 2023, 8(74): eade2256.
  * [9] V. Kurtz, H. Li, P. M. Wensing and H. Lin, Mini Cheetah, the Falling Cat: A Case Study in Machine Learning and Trajectory Optimization for Robot Acrobatics, 2022 International Conference on Robotics and Automation (ICRA), 2022, pp. 4635-4641
  * [10] Nguyen Q, Powell M J, Katz B, et al. Optimized jumping on the mit cheetah 3 robot[C]. 2019 International Conference on Robotics and Automation (ICRA), IEEE, 2019: 7448-7454.
  * [11] Chignoli, Matthew, et al. The MIT humanoid robot: Design, motion planning, and control for acrobatic behaviors. 2020 IEEE-RAS 20th International Conference on Humanoid Robots (Humanoids), IEEE, 2021.
  * [12] Gilroy S, Lau D, Yang L, et al. Autonomous navigation for quadrupedal robots with optimized jumping through constrained obstacles[C]. IEEE 17th International Conference on Automation Science and Engineering (CASE), IEEE, 2021: 2132-2139.
  * [13] Ding, Yanran, Chuanzheng Li, and Hae-Won Park. Kino-dynamic motion planning for multi-legged robot jumping via mixed-integer convex program. 2020 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), IEEE, 2020.
  * [14] Hwangbo J, Lee J, Dosovitskiy A, et al. Learning agile and dynamic motor skills for legged robots[J], Science Robotics, 2019, 4(26): eaau5872.
  * [15] AHMAD, Mohamad Faiz, et al. Differential evolution: A recent review based on state-of-the-art works. Alexandria Engineering Journal, 2021.
  * [16] Song Z, Yue L, Sun G, et al. An Optimal Motion Planning Framework for Quadruped Jumping[C]//2022 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS). IEEE, 2022: 11366-11373.
  * [17] Dong H, Li X, Yang Z, et al. A two-layer surrogate-assisted differential evolution with better and nearest option for optimizing the spring of hydraulic series elastic actuator[J]. Applied Soft Computing, 2021, 100: 107001.
  * [18] Wang W, Liu H L, Tan K C. A surrogate-assisted differential evolution algorithm for high-dimensional expensive optimization problems[J]. IEEE Transactions on Cybernetics, 2022.
  * [19] Sutyasadi P, Parnichkun M. Gait Tracking Control of Quadruped Robot Using Differential Evolution Based Structure Specified Mixed Sensitivity Robust Control[J]. Journal of Control Science and Engineering, 2016.
  * [20] A. K. Qin, V. L. Huang and P. N. Suganthan, Differential Evolution Algorithm With Strategy Adaptation for Global Numerical Optimization, IEEE Transactions on Evolutionary Computation,vol. 13, no. 2, pp. 398-417, April 2009.
  * [21] Winkler A W, Bellicoso C D, Hutter M, et al. Gait and trajectory optimization for legged systems through phase-based end-effector parameterization, IEEE Robotics and Automation Letters, 2018, 3(3): 1560-1567.
  * [22] Dai H, Valenzuela A, Tedrake R. Whole-body motion planning with centroidal dynamics and full kinematics[C],2014 IEEE-RAS International Conference on Humanoid Robots. IEEE, 2014: 295-302.
  * [23] Kajita, Shuuji, et al. Biped walking pattern generation by using preview control of zero-moment point. IEEE International Conference on Robotics and Automation, (Cat. No. 03CH37422). Vol. 2. IEEE, 2003.
  * [24] Hereid, Ayonga, and Aaron D. Ames. Frost: Fast robot optimization and simulation toolkit. 2017 IEEERSJ International Conference on Intelligent Robots and Systems (IROS), IEEE, 2017.
  * [25] Srinivas, Taarun, et al. Valkyrie—Design and development of gaits for quadruped robot using particle swarm optimization. Applied Sciences, 11.16 (2021): 7458.
  * [26] Kim D, Di Carlo J, Katz B, et al. Highly dynamic quadruped locomotion via whole-body impulse control and model predictive control[J]. arXiv preprint arXiv:1909.06586, 2019.
  * [27] Das S, Suganthan P N. Differential evolution: A survey of the state-of-the-art[J], IEEE transactions on evolutionary computation, 2010, 15(1): 4-31.
  * [28] Katz B, Di Carlo J, Kim S. Mini cheetah: A platform for pushing the limits of dynamic quadruped control[C]. 2019 International Conference on Robotics and Automation (ICRA). , IEEE, 2019: 6295-6301.
  * [29] Ayyub B M, Lai K L. Structural reliability assessment using latin hypercube sampling[C]. Structural Safety and Reliability. ASCE, 1989: 1177-1184.