Constructing Parsimonious Analytic Models for Dynamic Systems via Symbolic Regression
Erik Derner Jiří Kubalík Nicola Ancona Robert Babuška






a1,a2]Erik Derner
a1]Jiří Kubalík
a3]Nicola Ancona
a1,a3]Robert Babuška

[a1]Czech Institute of Informatics, Robotics, and Cybernetics, Czech Technical University in Prague, Prague, 16000, Czech Republic
[a2]Department of Control Engineering, Faculty of Electrical Engineering, Czech Technical University in Prague, Prague, 12135, Czech Republic
[a3]Cognitive Robotics, Delft University of Technology, Delft, 2628 CD, The Netherlands
Corresponding author: Erik Derner, 


Developing mathematical models of dynamic systems is central to many disciplines of engineering and science. Models facilitate simulations, analysis of the system's behavior, decision making and design of automatic control algorithms. Even inherently model-free control techniques such as reinforcement learning (RL) have been shown to benefit from the use of models, typically learned online. Any model construction method must address the tradeoff between the accuracy of the model and its complexity, which is difficult to strike. In this paper, we propose to employ symbolic regression (SR) to construct parsimonious process models described by analytic equations. We have equipped our method with two different state-of-the-art SR algorithms which automatically search for equations that fit the measured data: Single Node Genetic Programming (SNGP) and Multi-Gene Genetic Programming (MGGP). In addition to the standard problem formulation in the state-space domain, we show how the method can also be applied to input–output models of the NARX (nonlinear autoregressive with exogenous input) type. We present the approach on three simulated examples with up to 14-dimensional state space: an inverted pendulum, a mobile robot, and a bipedal walking robot. A comparison with deep neural networks and local linear regression shows that SR in most cases outperforms these commonly used alternative methods. We demonstrate on a real pendulum system that the analytic model found enables a RL controller to successfully perform the swing-up task, based on a model constructed from only 100 data samples.











symbolic regression genetic programming model learning reinforcement learning







§ INTRODUCTION



Numerous methods rely on an accurate model of the system. Model-based techniques comprise a wide variety of methods such as model predictive control <cit.>, time series prediction <cit.>, fault detection and diagnosis <cit.>, or reinforcement learning (RL) <cit.>.

Even though model-free algorithms are available, the absence of a model slows down convergence and leads to extensive learning times <cit.>.
Various model-based methods have been proposed to speed up learning <cit.>. To that end, many model-learning approaches are available: time-varying linear models <cit.>, Gaussian processes <cit.> and other probabilistic models <cit.>, basis function expansions <cit.>, regression trees <cit.>, deep neural networks <cit.> or local linear regression <cit.>.

All the above approaches suffer from drawbacks induced by the use of the specific approximation technique, such as a large number of parameters (deep neural networks), local nature of the approximator (local linear regression), computational complexity (Gaussian processes), etc. In this article, we propose another way to capture the system dynamics: using analytic models constructed by means of the symbolic regression method (SR). Symbolic regression is based on genetic programming and it has been used in nonlinear data-driven modeling, often with quite impressive results <cit.>.

Symbolic regression appears to be quite unknown to the machine learning community as only a few works have been reported on the use of SR for control of dynamic systems. For instance, modeling of the value function by means of genetic programming is presented in <cit.>, where analytic descriptions of the value function are obtained based on data sampled from the optimal value function. Another example is the work <cit.>, where SR is used to construct an analytic function, which serves as a proxy to the value function and a continuous policy can be derived from it. A multi-objective evolutionary algorithm was proposed in <cit.>, which is based on interactive learning of the value function through inputs from the user. SR is employed to construct a smooth analytic approximation of the policy in <cit.>, using the data sampled from the interpolated policy.

To our best knowledge, there have been no reports in the literature on the use of symbolic regression for constructing a process model in model-based control methods. We argue that the use of SR for model learning is a valuable element missing from the current nonlinear control schemes and we demonstrate its usefulness.

In this paper, we extend our previous work <cit.>, which indicated that SR is a suitable tool for this task. It does not require any basis functions defined a priori and contrary to (deep) neural networks it learns accurate, parsimonious models even from very small data sets. Symbolic regression can handle also high-dimensional problems and it does not suffer from the exponential growth of the computational complexity with the dimensionality of the problem, which we demonstrate on an enriched set of experiments including a complex bipedal walking robot system. In this work, we extend the use of the method to the class of input–output models, which are suitable in cases when the full state vector cannot be measured. By testing our method with two different state-of-the-art genetic programming algorithms, we demonstrate that the method is not dependent on the particular choice of the SR algorithm.

The paper is organized as follows. Sections <ref> and <ref> present the relevant context for model learning and the proposed method. The experimental evaluation of the method is reported in Section <ref> and the conclusions are drawn in Section <ref>. <ref> describes the RL method used in this paper and <ref> lists detailed results of the experiments.



§ THEORETICAL BACKGROUND



The discrete-time nonlinear state-space process model is described as


    x_k+1   = f(x_k,u_k)


with the state x_k, x_k+1∈𝒳⊂ℝ^n and the input u_k ∈𝒰⊂ℝ^m. Note that the actual process can be stochastic (typically when the sensor readings are corrupted by noise), but in this paper we aim at constructing a deterministic process model (<ref>).

The full state vector cannot be directly measured for a vast majority of processes and a state estimator would have to be used. In the absence of an accurate process model, such a reconstruction is inaccurate and has a negative effect on the overall performance of the control algorithm on the real system. Note that this problem has not been explicitly addressed in the literature, as most results are demonstrated on simulation examples in which the state information is available.

Therefore, next to state-space models, we also investigate the use of dynamic input–output models of the NARX (nonlinear autoregressive with exogenous input) type. The NARX model establishes a relation between the past input–output data and the predicted output:


    y_k+1=g(y_k,y_k-1,…,y_k-n_y+1,u_k,u_k-1,…,u_k-n_u+1),


where n_y and n_u are user-defined integer parameters based on the expected system's order, and g is a static function, different from the function f used in the state-space model (<ref>).

For the ease of notation, we group the lagged outputs and inputs into one vector:

    φ_k = [y_k,y_k-1…,y_k-n_y+1,u_k-1,…,u_k-n_u+1]

and write model (<ref>) as:


    y_k+1=g(φ_k, u_k) .


Note that in this setting, the model function and also the control policy are found from data samples which live in a space that is very different from the state space. The lagged outputs y_k, y_k-1, …, y_k-n_y+1 are highly correlated and therefore span a deformed space. This presents a problem for many types of approximators. For instance, basis functions defined by the Cartesian product of the individual lagged variables will cover the whole product space y_k × y_k-1×…× y_k-n_y+1, while data samples only span a small, diagonally oriented part of the space, as illustrated in Figure <ref>. The SR approach described in this paper does not suffer from such drawbacks.



In this paper, we use reinforcement learning as the control method of choice. Please refer to <ref> for details on the RL method used.



§ METHOD


In this section, we explain the principle of our method, briefly describe two variants of genetic programming algorithms used in this work, and discuss the computational complexity of our approach.



 §.§ Symbolic Regression



Symbolic regression is employed to approximate the unknown state transition function f in the state-space model (<ref>) or g in the input–output model (<ref>). The analytic expressions describing the process to be controlled are constructed through genetic programming. SR methods were reported in the literature to work faster when using a linear combination of evolved nonlinear functions instead of evolving the whole analytic expression at once <cit.>. Therefore, we define the class of analytic state-space models as:


    f(x,u) = β_0 + ∑_i=1^n_fβ_i f_i(x,u)


and the class of analytic input–output (NARX) models as:


    g(φ,u) = β_0 + ∑_i=1^n_fβ_i g_i(φ,u) .


The nonlinear functions f_i(x,u) or g_i(φ,u), called features, are constructed from a set of user-defined elementary functions. These functions can be nested and are evolved by means of standard evolutionary algorithm operations, such as mutation, so that the mean-square error calculated over the training data set is minimized. No a priori knowledge on the structure of the nonlinear model is needed. The set of elementary functions may be broad to let the SR algorithm select functions that are most suitable for fitting the given data. However, it is also possible to provide the algorithm with a partial knowledge about the problem. A narrower selection of elementary functions restricts the search space and speeds up the evolution process.

To avoid over-fitting, we control the complexity of the regression model by imposing a limit on the number of features n_f and the maximum depth d of the tree representation of the features. The coefficients β_i are estimated by least squares.



 §.§ Genetic Programming Methods Used



In order to demonstrate that our method is not dependent on the particular choice of the SR algorithm, we test our approach with two different genetic programming methods: a modified version of Single Node Genetic Programming (SNGP) <cit.> and a modified version of Multi-Gene Genetic Programming (MGGP) <cit.>. Both methods have been successfully used for symbolic regression, with several applications in the RL and robotics domains <cit.>.

SNGP is a graph-based genetic programming technique that evolves a population of nodes organized in the form of an ordered linear array. The nodes can be of various types depending on the particular problem. In the context of SR, the node can either be a terminal, i.e., a constant or a variable, or some operator or function chosen from a set of functions defined by the user for the problem at hand. The individuals are interconnected in the left-to-right manner, meaning that an individual can act as an input operand only of those individuals which are positioned to its right in the population. Thus, the whole population represents a graph structure with multiple expressions rooted in the individual nodes. Expressions rooted in the function nodes can represent non-linear symbolic functions of various complexity. The population is evolved through a local search procedure using a single reversible mutation operator.

MGGP is a tree-based genetic programming algorithm utilizing multiple linear regression. The main idea behind MGGP is that each individual is composed of multiple independent expression trees, called genes, which are put together by a linear combination to form a single final expression. The parameters of this top-level linear combination are computed using multiple linear regression where each gene acts as an independent feature. In this article, we build upon a particular implementation of MGGP – GPTIPS2 <cit.>. This particular instance of MGGP uses two crossover operators: (i) high-level crossover that combines gene sets of two parents; (ii) low-level crossover which is a classical Koza-style <cit.> subtree crossover operating on corresponding pairs of parental genes. Also, there are two mutation operators: (i) subtree mutation, which is a classical Koza-style subtree mutation; (ii) constant mutation, which alters the numerical values of leaves representing constants. Both the crossover and mutation operators are chosen stochastically.

Detailed explanation of these algorithms and their parameters is beyond the scope of this paper and we refer the interested reader to <cit.> and <cit.>.



 §.§ Computational Complexity


The computational complexity of the symbolic regression algorithms used in this work increases linearly with the size of the training data set as well as with the dimensionality of the problem. For example, considering a problem with one-dimensional state, one-dimensional input, one-dimensional output, and a data set of 1000 samples, a single run of the SNGP or MGGP algorithm with the default configuration takes about 3 minutes on a single core of a standard desktop PC. For a system with a 14-dimensional regressor and a 6-dimensional input, a single run takes up to 20 minutes.



§ EXPERIMENTAL RESULTS


We have carried out experiments with three nonlinear systems: a mobile robot, a 1-DOF inverted pendulum and a bipedal walking robot. The data, the codes and the detailed configuration of the experiments is available in our repository[<https://github.com/erik-derner/symbolic-regression>].


The simulation experiment with the mobile robot illustrates the use of the presented method, showing the precision and compactness of the models found in the case where the ground truth is known (Section <ref>). We show that the method is not dependent on the particular choice of the SR algorithm by comparing the performance of two SR methods, SNGP and MGGP. The subsequent experiment with the walking robot presents a more complex example and shows the performance of the method in a high-dimensional space (Section <ref>). With this example, we demonstrate the ability of the method to construct standard state-space models as well as input–output (NARX) models and we show how the method performs compared to two deep neural networks with different architectures. We conclude our set of experiments with the inverted pendulum system (Section <ref>). Similarly as in the experiment with the mobile robot, we evaluate the method with SNGP and MGGP, and we compare the results to two alternative approaches: neural networks and local linear regression. In addition to measuring the model prediction error, we perform real-time closed-loop control experiments with a lab setup to evaluate the performance of the algorithm in real-world conditions.







 §.§ Mobile Robot



The state of a two-wheel mobile robot, see Figure <ref> and <cit.>, is described by x = [x_pos, y_pos, ϕ]^⊤, with x_pos and y_pos the position coordinates and ϕ the heading. The control input is u = [v_f, v_a]^⊤, where v_f represents the forward velocity and v_a the angular velocity of the robot.



The continuous-time dynamic model of the robot is:


    ẋ_pos   = v_f  cos(ϕ) , 
    ẏ_pos   = v_f  sin(ϕ) , 
    ϕ̇   = v_a .




  §.§.§ Data Sets


We generated a noise-free data set by using the Euler method to simulate the differential equations (<ref>). With a sampling period T_s = 0.05 s, the discrete-time approximation of (<ref>) becomes:


    x_pos,   k+1   = x_pos,   k + 0.05   v_f,   k cos(ϕ) , 
    
    y_pos,   k+1   = y_pos,   k + 0.05   v_f,   k sin(ϕ) , 
    ϕ_k+1   = ϕ_k + 0.05   v_a,   k .


We generated training data sets of different sizes n_s. The initial state x_0 and the control input u_k for the whole simulation were randomly chosen from the ranges:


    x_pos   ∈ [-1, 1]  m , 
    
    y_pos   ∈ [-1, 1]  m , 
    ϕ   ∈ [-π, π]  rad , 
    
    v_f    ∈ [-1, 1]  m · s^-1 , 
    
    v_a    ∈[-π 2, π 2]  rad · s^-1 .


A test data set was generated in order to assess the quality of the analytic models on data different from the training set. The test data set entries were sampled on a regular grid with 11 points spanning evenly each state and action component domain, as defined by (<ref>). These samples were stored together with the next states calculated by using the Euler approximation.



  §.§.§ Experiment Setup


The purpose of this experiment was to test the ability of the SNGP and MGGP algorithms to recover from the data the analytic process model described by a known state-transition function. In order to assess the performance depending on the size of the data set and the complexity of the model, different combinations of the number of features n_f and the size of the training set n_s were tested. As the used algorithms only allow modeling one output at a time, they were run independently for each of the state components x_pos,   k+1, y_pos,   k+1 and ϕ_k+1.

The size of the SNGP population was set to 500 individuals and the evolution duration to 30000 generations. The set of elementary functions was defined as {*,   +,   -,  sin,  cos}. The maximum depth d of the evolved nonlinear functions was set to 7 and the number of features was n_f ∈{1, 2, 10}. To ensure a fair evaluation, the parameters of the MGGP algorithm were set similarly to provide both methods with a comparable amount of computational resoruces, taking into account the conceptual differences between the two algorithms.



  §.§.§ Results


The models found by symbolic regression were evaluated by calculating the RMSE median on the test data set over 30 independent runs of the SR algorithm. Note that each run yields a different model because the evolution process is guided by a unique sequence of random numbers. The results are listed in Table <ref> in <ref>.

An example of a process model found by running SNGP with the parameters n_f=2 and n_s=100 is:


    x̂_pos,   k+1 =     1.0   x_pos,   k + 0.0499998879   v_f,   k cos(ϕ_k)   , 
    ŷ_pos,   k+1 =     1.000000023   y_pos,   k + 0.0500000056   v_f,   ksin(ϕ_k) + 0.0000000191   , 
    ϕ̂_k+1 =     0.9999982931  ϕ_k + 0.0500000536   v_a,   k - 0.0000059844   .


The coefficients are rounded to 10 decimal digits in order to demonstrate the magnitude of the error compared to the original Euler approximation (<ref>). The results show that even with a small training data set, a precise, parsimonious analytic process model can be found based on noise-free data.

The results also demonstrate how the number of features n_f plays an important role in the setting of the experiment parameters. In general, the RMSE decreases with an increasing number of features, whereas the complexity naturally grows by adding more features to the final model (<ref>). The higher RMSE error when using only one feature is caused mainly by the fact that all parameters have to be evolved by the genetic algorithm, which is hard. On the other hand, when using more features, the least squares method can quickly and accurately find the coefficients of the features. These results support our choice to define the class of analytic models as a linear combination of features, as explained in Section <ref>. As a corollary, if the outline of the model structure is known in advance, it is recommended to set the number of features at least equal to the number of terms expected in the underlying function. Otherwise, it is advisable to set the number of features large enough, e.g. n_f = 10.







 §.§ Walking Robot



The robot LEO is a 2D bipedal walking robot <cit.>, see Figure <ref>. It has 7 actuators: two in the ankles, knees and hips and one in its shoulder that allows the robot to stand up after a fall. LEO is connected to a boom with a parallelogram construction. This keeps the hip axis always horizontal, which makes it effectively a 2D robot and thus eliminates the sideways stability problem.



The state vector of LEO x = [ψ, ψ̇]^⊤ consists of 14 components, where


    ψ = [ψ_TRS, ψ_LH, ψ_RH, ψ_LK, ψ_RK, ψ_LA, ψ_RA]^⊤


represents the angles of the torso, left and right hip, the knee and the ankle. Likewise,


    ψ̇ = [ψ̇_TRS, ψ̇_LH, ψ̇_RH, ψ̇_LK, ψ̇_RK, ψ̇_LA, ψ̇_RA]^⊤


are the angular velocities of the torso, hips, knees and ankles. The action space of LEO comprises the voltage inputs to the seven joint actuators.



  §.§.§ Data Sets


In order to apply symbolic regression, the walking robot LEO was modeled using the Rigid Body Dynamics Library (RBDL) <cit.> and the data sets were generated using the Generic Reinforcement Learning Library (GRL) <cit.>, which  allowed us to record trajectories while the robot was learning to walk.

We split the data set into two disjoint subsets: a training set and a test set. Both subsets are composed of consecutive samples from the simulation, which was run with a sampling period T_s = 0.03 s.



  §.§.§ Experiment Setup


The experiment was designed to evaluate the performance of our method on a more complex, high-dimensional example and to construct input–output (NARX) models in addition to the standard state-space models. We chose to use only the SNGP algorithm for this experiment and the main parameters were configured as follows. The population size was set to 500 and the number of generations to 30000. The depth limit d was fixed to 5 and the number of features was n_f ∈{1, 5, 10}. The elementary function set was defined as {*, +, -, sin, cos, square, cube}.

During the simulation used to obtain the data sets, the shoulder was not actuated. Therefore, the input vector had only 6 components, one for each actuator. As in the case of the mobile robot, SNGP was run separately for each of the 14 state components.

In Experiment B1, we used SR to generate standard state-space models. In Experiment B2, we generated input–output models with the regression vector defined as φ = [ψ_k, ψ_k-1, u_k-1].



  §.§.§ Results


In order to evaluate the ability of SNGP to approximate the state-transition function, we calculated the RMSE medians over 30 runs of the algorithm on the test data set. The results for the state-space models are reported in Table <ref> and for the input–output models in Table <ref> in <ref>.

The results show the expected trend, which can be seen in all experiments: the quality of the models improves with the size of the training data set. However, it is noteworthy that the difference between the RMSE for models trained on 100 samples and for those trained on 5000 samples are in most cases negligible. This confirms our earlier observation that SR can be used to find accurate analytic process models on batches of data as small as 100 samples <cit.> even for high-dimensional systems.

The results for the input–output models are generally just slightly worse than those for the state-space models, with the benefit of speeding up the algorithm by reducing the number of modeled variables to a half.



  §.§.§ Comparison with Alternative Methods



Deep neural networks are widely used to model an unknown system. In order to compare our method to alternative state-of-the-art methods, we have constructed two different neural networks:


 
  * Deep neural network DNN-A was implemented in PyTorch. It consists of an input linear layer of size 20 × 200, followed by three linear layers with the size of 200 × 200, with a ReLU activation function used after each linear layer. The output layer has 200 × 14 units. The batch size was set to 32. The SGD algorithm <cit.> was used with the learning rate of 8.5 × 10^-4.
 
  * Deep neural network DNN-B was implemented in TensorFlow. It is a fully connected network with 1 hidden layer, consisting of 512 units with ELU nonlinearity and 50% dropout. The batch size was set to 8. The Adam optimizer <cit.> was used with a learning rate of 10^-3 and early stopping.


We chose the RMSE medians of SNGP with n_s = 1000 and n_f = 10 as the benchmark configuration. State-space models were used in this scenario. The training and test sets were the same for all compared methods. Figure <ref> shows an overview of the performance of the two variants of DNN compared to the SNGP algorithm and detailed results are presented in Table <ref> in <ref>. The results show that the SNGP algorithm is able to find substantially better models than the neural networks for the angles, while the performance on the angular velocities is comparable among all the tested methods.









 §.§ Inverted Pendulum



The inverted pendulum system consists of a weight of mass m attached to an actuated link which rotates in the vertical plane, see Figure <ref>a. The state vector is x = [α, α̇]^⊤, where α is the angle and α̇ is the angular velocity of the link. The control input is the voltage u. The continuous-time model of the pendulum dynamics is:


    α̈= 1/J·(K/R  u - m   g   l  sin(α) - b  α̇- K^2/R α̇- c  sign(α̇) )


with J = 1.7937 × 10^-4 kg · m^2, m = 0.055  kg, g = 9.81  m · s^-2, l = 0.042  m, b = 1.94 × 10^-5 N · m · s · rad^-1, K = 0.0536  N · m · A^-1, R = 9.5  Ω and c = 8.5 × 10^-4 kg · m^2· s^-2. The angle is α = 0 or α = 2π for the pendulum pointing down and α = π for the pendulum pointing up.



The reward function used in the RL experiments was defined as follows:

    ρ(x_k, u_k, x_k+1) = - 0.5 |α_r - α_k| - 0.01 |α̇_r - α̇_k| - 0.05 |u_k| ,


where [α_r, α̇_r]^⊤ is a constant reference (goal) state.



  §.§.§ Data Collection


As we will present an experiment with the inverted pendulum performing a control task, we start this section by a short overview of the data collection methods used. Two different situations can be distinguished: initial model learning and model learning under a given policy.



  
Initial Model Learning

At the beginning, when the control policy is not yet available, the system can be excited by a test signal in order to obtain a sufficiently rich data set. Various methods for designing suitable test signals are described in the literature, such as the generalized binary noise (GBN) sequence <cit.>. The important parameters to be selected are the input signal amplitude, the way the random signal is generated (e.g., the `switching' probability) and the experiment duration.



  
Model Learning Under a Given Policy

Once an acceptable control policy has been learned, the system can be controlled to execute the required task. Data can be collected while performing the control task and used to further improve the model. As the information captured in the data under steady operating conditions might not be sufficient in certain situations, the control input can be adjusted by adding a test signal in this case as well. The characteristics of this test signal are usually different from the one used for initial model learning; for instance, it typically has a lower amplitude.



  §.§.§ Data Sets



We used both simulated and real measured data in the experiments with the inverted pendulum. In all experiments, the discrete-time sampling period used was T_s = 0.05 s.

At first, we generated a noise-free data set for Experiment C1 by using the Euler method to simulate the differential equation (<ref>):


    α_k+1 =    α_k + 0.05  α̇_k , 
    α̇_k+1 =     0.9102924564  α̇_k - 0.2369404025  sign(α̇_k) 
        + 1.5727561084   u_k - 6.3168590065  sin(α_k) .


The data set for Experiment C2 was created by integrating (<ref>) by using the fourth-order Runge-Kutta method and adding Gaussian noise. The transformation from the original states x = [α, α̇]^⊤ to the states with Gaussian noise x_n = [α_n, α̇_n]^⊤ is defined as


    α_n    = α + πλ r_n,1 , 
    α̇_n    = α̇+ 40 λ r_n,2 ,


where r_n,1,   r_n,2 are random numbers drawn from a normal distribution with zero mean and a standard deviation of 1. The constant λ∈{ 0, 0.01, 0.05, 0.1 } controls the amount of noise and the constants π and 40 make sure that the added noise is approximately proportional to the range of each variable.

In both Experiments C1 and C2, the initial state was α = 0, α̇= 0 and the control input was chosen randomly at each time step k from the range u_k ∈ [-5, 5]  V.

The test data sets were created similarly as in Section <ref>. The samples were generated on a regular grid of 31 × 31 × 31 points, spanning the state and action domain: α∈ [-π, π]  rad, α̇∈ [-40, 40]  rad · s^-1 and u ∈ [-5, 5]  V. For all samples, the next states in the test set for Experiment C1 were calculated using the Euler approximation. In Experiment C2, we generated a noise-free test set by applying the fourth-order Runge-Kutta method to all samples on the grid.

The real data for Experiment C3 were measured on the real inverted pendulum system shown in Figure <ref>b. At first, the system was excited by applying a uniformly distributed random control input u_k within the range [-5, 5]  V at each time step k. The random interaction with the system lasted for 5 seconds and the recorded data set comprised 100 samples. The data are shown in Figure <ref>. The data set was later enriched by samples recorded while applying the control policy (<ref>) to perform the swing-up task on the real system, which will be described in the following section.



The sequences recorded for Experiment C3 were split into training and test subsets. Every third sample was used for the test set, while the remaining samples formed the training set. In all experiments, the reported RMSE values were calculated on the respective test data set.



  §.§.§ Experiment Setup


Similarly as in the experiment with the mobile robot, the SNGP and MGGP algorithms were first employed in Experiment C1 to test the ability of SR to generate precise models for the inverted pendulum system using a data set generated by the Euler method. The experiment serves to evaluate how the training data set size n_s and the number of features n_f influence the quality of the model.

Experiment C2 demonstrates how the analytic process models are evolved using the Runge-Kutta simulation data set with noise. The maximum number of features n_f in the symbolic regression algorithms was set to 10 in order to facilitate the evolution of models capturing the more complex underlying function. This experiment tests the behavior of the method in environments with noisy measurements.

We conclude the experiments with Experiment C3, which shows the intended use of the method within RL on the example of the underactuated swing-up task, performed on a real inverted pendulum system. The control goal is to stabilize the pendulum in the unstable equilibrium x_r = [α_r, α̇_r]^⊤ = [π, 0]^⊤. As the input is limited to the range u ∈ [-2, 2] V, the available torque is insufficient to push the pendulum directly up from the majority of initial states, and therefore it has to be first swung back and forth to gather energy. At first, we constructed 30 analytic models using the data set recorded under random input and then selected the model with the lowest RMSE on the test set. This initial model was employed to calculate the policy for the swing-up task (see <ref>). To find an approximation of the optimal value function, we used the fuzzy V-iteration algorithm <cit.>. We applied the policy to the real system in four independent runs, starting at the initial state x_0 = [0, 0]^⊤. In addition, we performed other four swing-ups with exploration noise added to the control input. The exploration noise was normally distributed with the standard deviation ranging from 0.2 to 0.5 V. All eight sequences, each consisting of approximately 50 measurements, were added to the initial data set recorded under random input. Using this extended data set, 30 refined analytic process models were learned and the model with the lowest error on the test set was chosen as the final refined model. Like in Experiment C2, the number of features was set to n_f = 10 to facilitate modeling the more complex state-transition function.

In all experiments, the size of the SNGP population was set to 500 and the evolution was limited to 30000 generations. The elementary function set was {*,   +,   -,  sin,  cos,  sign}. The maximum depth d was set to 7. In Experiment C1, various numbers of features were tested: n_f ∈{1, 2, 10} for α and n_f ∈{1, 4, 10} for α̇.  The parameters of the MGGP algorithm in Experiment C1 and C2 were set similarly, taking into account the conceptual differences between the two algorithms to allow for a fair comparison.



  §.§.§ Results


The results of Experiment C1 are summarized in Table <ref> in <ref> for the SNGP and MGGP algorithm. Similarly as in the previous examples, the results indicate that the precision of the models increases with increasing number of features. The overall performance of both SR algorithms is comparable.

An example of an analytic process model found with the parameters n_f=2 for α, n_f=4 for α̇ and n_s=20 is:


    α̂_k+1 =    α_k + 0.05  α̇_k - 0.0000000001   , 
    α̂̇̂_k+1 =     0.9102924745  α̇_k - 0.2369403835  sign(α̇_k)+ 1.5727561072   u_k 
    
     -     6.3168589936  sin(α_k) + 0.0000000013   .


The error of the analytic model w.r.t. the Euler approximation (<ref>) is very small. These results confirm that the proposed method can find precise models even on small data sets.

The results of Experiment C2 presented in Table <ref> in <ref> show that the analytic models are able to approximate the state-transition function well even on data with a reasonable amount of noise. The use of the Runge-Kutta method to generate data sets leads to substantially more complicated models than when using the data generated by using the Euler method. Again, the performance of the SNGP and MGGP algorithm is comparable.

In Experiment C3, we have shown that SR is able to find analytic process models using data collected on the real system. Already after a short (5 s) interaction under the random input, an analytic process model is found which enables RL to perform the swing-up, see Figure <ref>a. Performing the swing-up task allows to collect more data in important parts of the state space around the trajectory to the goal state. Figure <ref>b shows that the performance of the model further improves after adding data collected while performing the swing-up task with the initial model. Figure <ref> compares the swing-up response with the initial and the refined model. The histogram in Figure <ref> and a two-sample t-test with unpooled variance applied to the discounted return show that the performance improvement between the policy based on the initial and the refined analytic process model is statistically significant (p = 2 × 10^-22). The RMSE medians over 30 runs of the SNGP algorithm were 1.70 × 10^-2 for α and 6.03 × 10^-1 for α̇ in case of the initial model and 1.16 × 10^-2 for α and 3.35 × 10^-1 for α̇ in case of the refined model.









  §.§.§ Comparison with Alternative Methods


We compared our modeling results with local linear regression (LLR) <cit.>. We selected the Runge-Kutta data set with 1000 samples and zero noise as a reference training set and the regular grid as a test set (see Section <ref> for details). The LLR memory contained 1000 samples and the number of nearest neighbors was set to 10. The RMSE achieved by LLR was 1.73 × 10^-1 for α and 6.93 × 10^0 for α̇. In both cases, the SNGP algorithm achieved a better RMSE by at least one order of magnitude (6.11 × 10^-3 for α and 5.04 × 10^-1 for α̇).

We also compared the results of our method to a neural network. Given the relative simplicity of the problem, the network had one hidden layer, consisting of 40 neurons, and it was trained using the Levenberg-Marquardt algorithm. The number of neurons in the hidden layer was tuned by testing networks with 5 to 100 neurons and choosing the one that performed best on the test data. The RMSE achieved on the aforementioned reference data set was 6.82 × 10^-2 for α and 2.59 × 10^0 for α̇. Again, compared to the RMSE values achieved by our method (stated at the end of the previous paragraph), symbolic regression finds substantially better models in terms of RMSE compared to those found by the neural network.



§ CONCLUSIONS


We showed that symbolic regression is a very effective method for constructing dynamic process models from data. It generates parsimonious models in the form of analytic expressions, which makes it a good alternative to black-box models, especially in problems with limited amounts of data. Prior knowledge on the type of nonlinearities and model complexity can easily be included in the symbolic regression procedure. Despite the technique is not yet broadly used in the field of robotics and dynamic systems, we believe that it will become a standard tool for system identification.

The experiments with the walking robot demonstrate that symbolic regression can be used to construct precise process models even for high-dimensional systems. We have confirmed empirically that the computational complexity of the algorithm grows linearly with the dimensionality of the system. It is also worth mentioning that the complexity of the analytic models does not grow significantly with the complexity of the system.

The real-world experiment with the inverted pendulum shows that already after 5 seconds of interaction with the system, an initial analytic process model is found, which not only accurately predicts the process behavior, but also serves as a reliable model for the design of an RL controller. By collecting the data during several executions of the swing-up task using the initial analytic model and adding them to the data set used by SR to learn the model, the performance on the swing-up task further improves.

Our evaluation shows that two distinct symbolic regression algorithms, SNGP and MGGP, perform comparably well on the evaluated systems. This indicates that the proposed method is not dependent on the particular choice of the symbolic regression method. We compared the performance of symbolic regression with alternative state-of-the-art methods, in particular with neural networks and with local linear regression. The results show that the proposed method performs in most cases significantly better than the alternatives.

Another important outcome is that SR can be used to find both state-space and input–output models. The use of input–output models is beneficial because it does not require the observations of the full state vector and it also makes the algorithm faster because of modeling a reduced number of variables.

We have identified several possibilities for future extensions of this work. The main objective is to apply SR methods within the entire RL scheme, i.e., also for approximating the V-function, and also to use analytic models in combination with actor-critic online RL. In some cases, especially when using many features, analytic models tend to be unnecessarily complex. In our future work, we will investigate systematic reduction of analytic models.



§ ACKNOWLEDGMENTS


This work was supported by the European Regional Development Fund under the project Robotics for Industry 4.0 (reg. no. CZ.02.1.01/0.0/0.0/15_003/0000470) and by the Grant Agency of the Czech Technical University in Prague, grant no. SGS19/174/OHK3/3T/13.

The authors thank Tim de Bruin and Jonáš Kulhánek for their help with the DNN experiments for the walking robot and Jan Žegklitz for his help with experiments using the MGGP algorithm.







§ REINFORCEMENT LEARNING



The system for which an optimal control strategy is to be learnt can be described by the nonlinear state-space model (<ref>) or the input–output (NARX) model (<ref>). The following text describes the case using the state-space models. For the input–output models, the reward function, the return, the value function and the optimal control action (<ref>)–(<ref>) can be defined analogously using the regressor φ instead of the state variable x.

The  reward function assigns a scalar reward r_k+1∈ℝ to the state transition from x_k to x_k+1, under action u_k:


    r_k+1   = ρ(x_k, u_k, x_k+1) .


The reward function ρ specifies the control goal, typically as the distance of the current state to a given goal state.

Based on model (<ref>), we compute the optimal control policy π: 𝒳→𝒰 such that in each state it selects a control action so that the expected cumulative discounted reward over time, called the return, is maximized:


    R^π = E{∑^∞_k=0γ^kρ(x_k,π(x_k),x_k+1)} .


Here γ∈ (0,1) is a discount factor and the initial state x_0 is drawn from the state space domain 𝒳 or its subset. Over the whole state space, the return is captured by the value function V^π:𝒳→ℝ defined as:


    V^π(x) = E{∑^∞_k=0γ^kρ(x_k,π(x_k),x_k+1)| . x_0 = x} .


An approximation of the optimal V-function, denoted by V̂^*(x), can be computed by solving the Bellman optimality equation


    V̂^*(x) = max_u∈𝒰[ρ(x,u,f(x,u))+γ V̂^*(f (x,u))] .


To simplify the notation, we drop the superscripts; V(x) therefore denotes an approximation of the optimal V-function. Based on V(x), the corresponding approximately optimal control action is found as the one that maximizes the right-hand side of (<ref>):


    u = _u'∈ U[ρ(x, u', f(x,u')) + γ  V(f(x,u')) ] .


In this work, the above equation is used online as the control policy π with a set of discretized inputs U, so that the near-optimal control action can be found by enumeration.



§ DETAILED EXPERIMENT RESULTS



In this appendix, we present detailed results of the experiments described in Section <ref>.














elsarticle-num


