{'fraction_non_alphanumeric': 0.05052241766962042, 'fraction_numerical': 0.01216770268483005, 'mean_word_length': 4.441112976733029, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 3, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 3, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Q-learning for POMDP: An application to learning locomotion gaits

This paper presents a Q-learning framework for learning optimal locomotion gaits in robotic systems modeled as coupled rigid bodies. Inspired by prevalence of periodic gaits in bio-locomotion, an open loop periodic input is assumed to (say) affect a nominal gait. The learning problem is to learn a new (modified) gait by using only partial noisy measurements of the state. The objective of learning is to maximize a given reward modeled as an objective function in optimal control settings. The proposed control architecture has three main components: (i) Phase modeling of dynamics by a single phase variable; (ii) A coupled oscillator feedback particle filter to represent the posterior distribution of the phase conditioned in the sensory measurements; and (iii) A Q-learning algorithm to learn the approximate optimal control law. The architecture is illustrated with the aid of a planar two-body system. The performance of the learning is demonstrated in a simulation environment.


I. INTRODUCTION
Biological locomotion is the movement of an animal from one location to another location, through periodic changes in the shape of the body, along with interaction with the environment [7]. The periodic motion of the shape, which constitutes the building block of locomotion, is called the locomotion gait. Examples of the locomotion gait are legged locomotion, flapping of the wings for flying, or wavelike motion of the fish for swimming. It is a wonderful example for learning because the dynamics are complicated but the goals (reward function) are easily modeled. In direct application of Q-learning to these problems, however, a problem arises because the full state is not available.
The dynamics for such robotic systems are modeled using coupled rigid bodies. The configuration space is split into two sets of variables: (i) the shape variable that describes the robot's internal degrees of freedom; (ii) and the group variable that describes the global position and orientation of the robot. The dynamics of the shape variable is given by a second-order differential equation driven by control inputs. The dynamics of the group variable is given by a first-order differential equation governed by non-holonomic constraints in the system (e.g conversation laws or no slipping conditions).
A typical approach to design the locomotion gait is to search for a periodic orbit in the shape space that leads to a desired net change in the group variable. This idea of producing a net change through underlying periodic motion Financial support from the NSF grant CMMI-1462773 and ARO grant W911NF1810334 is gratefully acknowledged.
T. Wang, A. Taghvaei and P. G. Mehta are with the Coordinated Science Laboratory and the Department of Mechanical Science and Engineering at the University of Illinois at Urbana-Champaign (UIUC).
tixianw2@illinois.edu; taghvae2@illinois.edu; mehtapg@illinois.edu is known as mechanical rectification [3], [11] and the net change in the group variable is called geometric phase [9], [10], [12]. The optimal gait is obtained by searching over a parameterized set of trajectories in the shape space to optimize a given optimization criteria [2], [17], [26], [15], [18], [6]. The resulting control law is open-loop and can suffer from issues due to uncertainties in the environment, or disturbance which perturbs the trajectory away from the orbit.
The problem considered in this paper is to learn an approximate optimal gait given an open-loop periodic input. We do not assume any control over this input: for example, it may correspond to the nominal gait or it may be exerted from the environment. The presence of the periodic input creates a limit cycle in the high-dimensional configuration space. The control problem is to actuate some of the system parameters to learn new types of gaits.
For the purpose of learning, no knowledge of dynamic models is assumed. Furthermore, knowledge of full state is not assumed. At each time, one only has access to partial noisy measurements of the state. The proposed control architecture builds upon our prior work on phase estimation [22] and its use for optimal control of bio-locomotion [20]. As in [20], the control problem is modeled as an optimal control problem. Since full state feedback is not assumed, we are in the partially observed settings. The original contribution of this work is to extend our prior work to a reinforcement learning framework whereby new gaits can be learned by the robot only through the use of noisy measurements and observed rewards.
The proposed control architecture has three parts: 1. Phase modeling: Under the assumed periodic input, the shape trajectory is a limit cycle in the high-dimensional phase space. The main complexity reduction technique is to introduce a phase variable θ (t) ∈ [0, 2π] to parametrize the low-dimensional periodic orbit. The inspiration comes from neuroscience where phase reduction is a popular technique to obtain reduced order model of neuronal dynamics [8], [4].
2. Coupled oscillator feedback particle filter: We construct a nonlinear filtering algorithm to approximate the posterior distribution of the phase variable θ (t), given time history of sensory measurements. The coupled oscillator feedback particle filter (FPF) is comprised of a system of N coupled oscillators [23], [21]. The empirical distribution of the oscillators is used to approximate the posterior distribution.

Reinforcement learning:
The control problem is cast as a partially observed optimal control problem. The posterior distribution represents an information state for the problem. A Q-learning algorithm is proposed where the Q-function is approximated through a linear function approximation. The weights are learned by implementing a gradient descent algorithm to reduce the Bellman error [27], [25], [13].
The key component of the proposed architecture is the system of coupled oscillators that is used to both represent the posterior distribution (the belief state) and to learn the optimal control policy. This control system can be viewed as a central pattern generator (CPG) which integrates sensory information to learn closed-loop optimal control policies for bio-locomotion.
The proposed CPG control architecture is illustrated with the aid of a two-body planar system depicted in Fig. 1. An open-loop periodic torque is applied at the joint connecting the two links, which results in the body to oscillate in a periodic (but uncontrolled) manner. The control objective is to turn the head clockwise by actuating the length of the tail body. Although only a two-body system is considered in this paper, the proposed architecture can easily be generalized to coupled body models of snake-robots and swimming fish robots. This is the subject of ongoing work.
The remainder of this paper is organized as follows: The problem is formulated in Section II. The proposed solution is described in Section III. The numerical results appear in Section IV.

A. Modeling and dynamics
Consider a system of two planar rigid bodies, the head body B 1 and the tail body B 2 , connected by a single degree of freedom pin joint as depicted in Figure 1. The configuration variables of the system are divided into two sets: i) the shape variable; ii) and the group variable. For the two-body system, the shape variable is the relative orientation between two bodies. It is denoted as the angle x. The group variable is the absolute orientation of the frame rigidly affixed to head body. It is denoted as the angle q.
There is no external force applied to the system, which means that the total angular momentum is conserved. The joint is assumed to be actuated by a motor with driven torque τ. An open-loop periodic input is assumed for the torque actuation: where ω 0 is the frequency and τ 0 is the amplitude. There is no control objective associated with this torque input, except to have the shape variable x oscillate in a periodic manner. It is assumed that there exists a control actuation that changes the length of the tail body B 2 according to whered is the nominal length and u represents the control input.
The dynamics of the two-body system is described by a second-order ODE for the shape variable and a first-order ODE for the group variable: The explicit form of the functionsf andg and their derivations appear in [20]. In this paper, the explicit form off and g are assumed unknown. Rather, the dynamic model is treated as a simulator (black-box) that is used to simulate the dynamics (3a)-(3b).

Remark 1:
The modeling procedure is easily generalized to a chain of n planar rigid links, e.g used to model snake robots as in [9]. In such systems, the group variable is the position and orientation of the robot, and the configuration space of shape variable is n − 1 dimensional. With n links, the dimension of the system is 2n + 1. An interesting problem for the snake robot is to learn a turning maneuver by changing the friction coefficients with respect to the surface.

B. Observation process
For the purposes of learning and control design, the state (x,ẋ) is assumed to be unknown. The following continuoustime observation model is assumed for the sensor: where Z(t) ∈ R denotes the observation at time t, W (t) is a standard Wiener process, and σ W > 0 is the noise strength. The observation functionh : R 2 → R is known and is assumed to be C 1 .

C. Optimal control problem
The control objective is to turn the head body B 1 clockwise by actuating the control input u(t). An uncontrolled periodic torque input (1) is assumed to be present. The control objective is modeled as a discounted infinite-horizon optimal control problem: subject to the dynamic constraints (3a). Here, γ > 0 is the discount rate and the cost functioñ with ε > 0 as the control penalty parameter. The minimum is over all control inputs u(·) adapted to the filtration Z t := σ (Z(s); s ∈ [0,t]) generated by the observation process. The limit cycle solution for the shape dynamics (x(t),ẋ(t)) together with its limit cycle approximation (see (21)).
The particular form of the cost function is assumed to maximize the rate of change, in the clockwise direction, in the group variable q. Indeed, by (3b),f (x,ẋ, u) =q. Therefore, minimizing the cost leads to net negative change in the head orientation q(t). This corresponds to the clockwise rotation.

III. SOLUTION APPROACH
Solving the optimal control problem (5) is challenging because of the following reasons: 1) The functiong in the dynamic model (3a) is not known.
For coupled rigid bodies, the model is nonlinear and complicated due to the details of the geometry, models of contact forces with the environment, uncertain parameters, etc.
2) The problem is partially observed, i.e., the state (x,ẋ) is not known. As the number of links grow, the state can be very high dimensional.
3) The explicit form of the functionf which captures the relationship between shape and group dynamics is not known.
These challenges are tackled by the following three-step procedure: A. Step 1. Phase modeling Consider the second-order equation (3a) for the shape variable x under the open-loop periodic input τ(t) given by (1). The following assumption is made concerning its solution: Assumption A1 Under periodic forcing τ(t) as in (1), the solution to (3a) is given by an isolated asymptotically stable periodic orbit (limit cycle) with period 2π/ω 0 .
Denote the set of points on limit cycle as P ⊂ R 2 . The limit cycle solution is parameterized by a phase coordinate θ ∈ [0, 2π) in the sense that there exists an invertible map X LC : [0, 2π) → P such that X LC (θ (t)) = (x(t),ẋ(t)), where θ (t) = (ω 0 t + θ (0)) mod 2π (see Figure 2). The definition of the phase variable is extended locally in a small neighborhood of the limit cycle by using the notion of isochrons [8].
The optimal control problem (5) in terms of the phase variable is given by where c(θ , u) = f (θ , u) + 1 2ε u 2 and the minimum is over all control inputs u(·) adapted to the filtration Z t .
In contrast to the original problem, the new problem is described by a single phase variable. With u(t) ≡ 0, the dynamics is described by the oscillator model θ (t) = (ω 0 t + θ 0 ) mod 2π. Now, in the presence of (small) control input, the dynamics need to be augmented by additional terms due to control: B. Step 2. Feedback particle filter (FPF) A feedback particle filter is constructed to obtain the posterior distribution of the phase variable θ (t) given the noisy observations (7). The filter is comprised of N stochastic is the state of the i-th particle (oscillator) at time t. The dynamics evolves according to dθ i (t) = ω i dt + εg(θ i (t)), u(t)) dt (10) where is the frequency of the i-th oscillator, the initial condition θ i (0) = θ i 0 ∼ Unif([0, 2π]), andĥ(t) := E[h(θ i (t))|Z t ]. The notation • denotes Stratonovich integration. In the numerical implementation, . Based on the FPF theory, the gain function K(θ ,t) is the solution of the Poisson equation, expressed in the weak-form as (11) for all test functions ψ where ψ is the derivative. In the numerical implementation, the gain function is approximated by choosing ψ from the Fourier basis functions {sin(θ ), cos(θ )} and approximating the expectations with empirical distribution of the oscillators {θ i (t) : 1 ≤ i ≤ N}. The detailed numerical algorithm to approximate the gain function appears in [23].

Remark 2:
There are two manners in which control input u(t) affects the dynamics of the filter state θ i (t): 1) The O(ε) term εg(·, u(t)) which models the effect of dynamics; 2) The FPF update term which models the effect of sensor measurements. This is because the control input u(t) affects the state x(t) (see (3a)) which in turn affects the sensor measurements Z(t) (see (4)).

C. Step 3. Q-learning
Using the FPF, following the approach presented in [14], express the partially observed optimal control problem (8) as a fully observed optimal control problem in terms of oscillator states θ (N) (t) = (θ 1 (t), . . . , θ N (t)) according to subject to (10), where the cost c (N) (θ (N) , u) := 1 N ∑ N i=1 c(θ i , u) and the minimization is over all control laws adapted to the filtration X t := {θ i (s); s ≤ t, 1 ≤ i ≤ N}. The problem is now fully observed because the states of oscillators θ (N) (t) are known.
The analogue of the Q-function for continuous-time systems is the Hamiltonian function: where D u is the generator for (10) defined such that The dynamic programming principle for the discounted problem implies: Substituting this into the definition of the Hamiltonian (13) yields the fixed-point equation: where H (N) (θ (N) ) := min u H (N) (θ (N) , u). This is the fixedpoint equation that appears in the Q-learning.
Linear function approximation: Learning the exact Hamiltonian (Q-function) is an infinite-dimensional problem. Therefore, we set the goal to learn an approximation. For this purpose, consider a fixed set of M real-valued functions {φ (m) (θ , u)} M m=1 . The Hamiltonian is approximated as the linear combination of the basis functions as follows: where w ∈ R M is a vector of parameters (or weights) and φ = (φ (1) , φ The following learning algorithm is proposed to find the optimal parameters d dt where α(t) is the time-varying learning gain and u(t) is chosen to explore the state-action space. For convergence analysis of the Q-learning algorithm see [24], [19], [5], [16].
Given a learned weight vector w * , the learned optimal control policy is given by:

D. Information structure
In order to implement the algorithm, one requires knowledge of the following models: 1) A model for g(θ , u) which represents the reduced order model of dynamics as these affect the phase variable; 2) A model for h(θ ) which represents the reduced order model of the sensor. These models are needed to implement the coupled oscillator FPF (10). It is noted that both the models are described with respect to the phase variable θ .
In the simulation results presented next, we assume knowledge of h(θ ) and ignore the term εg(θ i (t), u(t)) in the FPF. The formal reason for ignoring the term is that it is small (O(ε)) compared to other terms, O(1) frequency ω 0 and the update term. Although, we assume knowledge of the sensor model h(θ ) for this paper, a learning algorithm could also be implemented to learn the sensor model in an online manner. This is the subject of future work.
In numerical implementation, the generator D u is approximated as ∆t where ∆t is the discrete time step-size in the numerical algorithm and {θ i (t)} N i=1 is the state of the oscillators at time t.
The reward function f (θ (t), u(t)) in the cost function is approximated as The overall algorithm appears in Table 1.

E. Approximate formula for optimal control input
Assuming the knowledge of the explicit form of the function f (θ , u), a semi-analytic approach is presented in [20] to derive the following approximate formula for optimal control: where C is a constant that depends on the parameters of the model. The formula was shown to be valid in the asymptotic limit as ε → 0. The control policy (20) is implemented in [20] Algorithm 1 Q-learning for Optimal Contol of Two-body System Input: Parameters in Table I and a simulator for (3a)-(3b)-(4) Output: Optimal control policyû * (θ (N) ; w). 1: Initialize particles {θ i 0 } N i=1 ∼ Unif([0, 2π]); 2: Initialize weight vector w 0 according to (22). 3: for k = 0 to t T /∆t − 1 do 4: Choose control input u k according to (23); 5: Input u k to the simulator and output Z k and q k 6: Update particles in FPF k ; w k ))
where it is numerically shown to lead to clockwise rotation of the head body.
The formula (20) serves as a baseline for comparison with the results of the numerical implementation of the Q-learning algorithm.

IV. NUMERICS
In this section, we present the numerical results. These results illustrate the i) phase modeling; ii) the performance of coupled oscillator FPF; and iii) the performance of Qlearning algorithm. The numerical results are based on the use of Algorithm 1. The simulation parameters are tabulated in Table I.

A. Simulator
The simulator takes the control input u(t) and outputs the shape variable x(t), the head orientation q(t), and the observation Z(t) according to (3a), (3b), and (4) respectively. The explicit form of the simulated dynamics (3a)-(3b) are as follows: where the parameters are defined in Table I; cf., [20] for additional details on modeling. The resulting state trajectory x(t) and head orientation q(t), under periodic open-loop torque τ(t) (see (1)), are depicted in Figure 3(a). It is observed that without control input, the head orientation oscillates, without any net change.  The observation signal y(t) := (Z(t + ∆t) − Z(t))/∆t, with the step-size ∆t = 0.01 is depicted in Figure 3(b). The observation model is taken ash(x,ẋ) = x. The noise strength σ w = 0.1.

B. Phase modeling
The limit cycle solution for the shape dynamics (3a) is depicted in Figure 2. The mapX LC (θ (t)) = (x(t),ẋ(t)) is approximated as where r = 0.56 is numerically determined.

C. Coupled oscillator feedback particle filter
The trajectories of N = 1000 particles in the FPF algorithm (10) are depicted in Figure 4(a). The initial conditions θ i 0 are drawn from a uniform distribution in [0, 2π]. The initial transients due to the initial condition converge rapidly. The true phase variable θ (t) is also depicted as a solid line. It is observed that the ensemble of particles synchronize and track the true phase.
The true state (x(t),ẋ(t)), along with the empirical distribution of the particles, at two time instants, are shown in Figure 4(b). The particles are positioned on the approximate limit cycle map (21). These results show that the filter is able to track the true state on the limit cycle accurately.

D. Q-learning
To approximate the Hamiltonian function in (16), the basis functions are selected to be the product of Fourier basis The reason for choosing the particular initialization for w (9) 0 is to avoid numerical issues due to large control values whenever w (9) 0 is small. The exploration control input u(t) to be used in (18) is chosen as a combination of sinusoidal functions with irrationally related frequencies as follows: The rationale for doing so is to explore the state-action space [1].
The L 2 -norm of the point-wise Bellman error (17), over the j-th period is denoted as e j and defined to be: The average of the error e j and its variance over fifty Monte-Carlo runs are depicted in Figure 5(a). It is observed that the Bellman error drops by over three orders of magnitude. This suggests that the algorithm is able to learn the Hamiltonian function that solves the dynamic programming fixed-point equation (15). The learned optimal control policy (19) in terms of the selected basis functions is given by: w (5) w (9) cos(θ i ) + w (6) w (9) sin(θ i ) (7) w (9) cos(2θ i ) + w (8) w (9) sin(2θ i ) (25) The traces of the four components of the weight vector {w (5) (t), w (6) (t), w (7) (t), w (8) (t)} are depicted in Figure 5  It is observed that the components (weights) converge quickly. Also, the component w (5) (t), which corresponds to cos(·), dominates while other components converge to zero. Figure 6(a) depicts the learned optimal control policy as a function of time. Also depicted is a comparison with the semi-analytical solution (20). It is observed that the learned optimal control coincides with the analytical formula in terms of both phase and amplitude. Figure 6(b) depicts the resulting head orientation with i) the learned optimal control policy (25); ii) the analytical control law (20); and iii) with no control input (u(t) ≡ 0). It is observed that the learned optimal control input induces nearly the same net change in the head orientation as the analytical control law. That is, the Q-learning algorithm is able to learn the optimal control policy to rotate the head body clockwise. .

V. CONCLUSIONS AND FUTURE WORK
We introduced a coupled oscillator-based framework for learning the optimal control of periodic locomotory gaits. The framework does not require knowledge of the explicit form of the dynamic models or observation of the full state. The framework was illustrated on the problem of turning the two-body planar system. One direction for future work, is to apply the framework to more complicated models such as coupled kinematic chains and continuum models. Another direction of future work is to consider more advanced tasks such as turning to a certain angle or locating a target.