Model-Free Self-Identification of Dexterous Manipulation via
Non-parametric Learning and Model Predictive Control

Podshara Chanrungmaneekul
, Kejia Ren
, Kaiyu Hang

Building control models between the hand’s actuation input and the in-hand object’s motion are crucial for precise real-time dexterous manipulation. Especially with underactuated robot hands, the challenging factor comes from the difficulty of obtaining exact gripper, object, and contact models. Therefore, we introduce a manipulation system that enables the robot to self-identify its own underlying control models using minimal sensing and to self-correct using sensory feedback for an online adaptation during the operation. In this paper, we propose an approach that uses Gaussian process (GP) regression based on data gathered from exploratory manipulation to learn the model of the system and improve the estimate of the models to better deal with uncertainty. The compliance nature of the underactuated hand helps stabilize the hand-object interaction during the self-exploratory process. Embedding this data-based update scheme in a Model Predictive Control (MPC) framework helps mitigate errors caused by inaccuracy in the learned models. The effectiveness of the self-identification process is demonstrated in the application of trajectory tracking and the system's performance with different parameter settings shows that utilization of MPC with the GP model provides accuracy, efficiency, and adaptability.

§ INTRODUCTION

The robot physically interacts with the environment mainly via manipulation. Dexterous in-hand manipulation has a number of advantages over full-arm manipulation. For the most common pick-and-place tasks, relying only on full-arm manipulation could face some challenges in energy consumption, human-interaction softness, and overcomplicated robot movements <cit.>. Using dexterous in-hand manipulation could focus on a smaller scale, and work around obstacles and joint singularities, which provide additional precision and lower energy/gains using the finger motion <cit.>. To achieve dexterous in-hand manipulation, underactuated robotic hand designs have been heavily utilized to facilitate high-dimension control systems with fewer actuators through passive compliance <cit.>. With these passively adaptive hands, the grasp could be stable even without high certainty in object pose/sensor feedback, or accurate pre-planned motions.

The manipulation task is defined using a partially constrained trajectory of the manipulation frame.

Various features of using adaptive hands, however, come with a few limitations and drawbacks. The use of under-actuation complicates the manipulation problem, introducing certain kinematic constraints imposed by the hardware, while the use of compliant elements complicates the kinematics and dynamics analysis. To be able to accurately manipulate the object with these underactuated hands, the underlying systems need to be identified for including an accurate model of the robot hand, physical properties, and contact profiles <cit.>. However, acquiring such a physics-based model is often difficult and time prohibitive for applications such as real-time optimal control and manipulation.

There are several factors that make modeling complicated physical systems difficult. First, the unavailability of the joint measurement in unaccounted degrees of freedom and the use of flexible transmission (i.e. springs, tendons, elastic materials) <cit.> make the process of acquiring an accurate model of the robotic hand challenging. Even if an accurate model is present, there could be changes over time in the physical properties like spring tension and joint displacement. Thus, the system identification must be repeated to keep the model updated. Also, model-based control rules are developed specifically for certain robotics systems. However, the robotics system often has many slightly different versions that could serve its niche purposes or tasks. Therefore, this modeling process must be repeated for every new system. To circumvent the aforementioned challenges of deriving an analytical physical model, the self-identification process is introduced using data-driven methods to anticipate the future state of the system, in combination with a controller-based method to intervene proactively to achieve the intended behavior. These strategies make use of real-time sensor feedback to enhance local control performance.

In this work, we develop a self-identification framework for underactuated in-hand manipulation as outlined in Fig  <ref>. Utilizing the robot's compliance, The underlying control system is learned via a GP regression model <cit.> using control samples collected from exploratory actions. In addition, using MPC <cit.> for non-parametric model-based in-hand manipulation introduces an additional fail-safe strategy to gain more control over unexpected errors in the system. The advantages of this method are demonstrated with experiments using trajectory tracing (see Fig  <ref>) with various shapes/sizes of objects.

A visualization of the structure of the proposed self-identification process for in-hand manipulation. The real raw data of control samples are collected from the physical system by executing exploratory action. The system motion functions are learned via GP regression. A model predictive control is used to produce the next actuation input with the goal to follow the trajectory. After the action is executed, the sensory feedback is measured and models are updated accordingly using newly collected from the exploratory actions.

§ RELATED WORK

Different analytic approaches to dexterous in-hand manipulation using these systems are, for example, contact models <cit.> and finger curvature models <cit.>, hand kinematic models <cit.>, impedance control <cit.>, trajectory optimization <cit.>, and combination of position/force control <cit.>. These manipulation problems could be formulated with exact mathematical models. However, most of the approach highly depends on the quality of the model parameters or requires explicit models of contact. To overcome uncertainties in the analytical models, data-driven approaches to grasping <cit.> and in-hand manipulation <cit.> have gained substantial popularity in recent years. These approaches often do not make assumptions about the models and could perform a more general manipulation behavior, but the data-collection process could only be done in simulation and the methods require massive computational resources to learn the black-box system representation <cit.>.

Some of the manipulation problems could be nullified when using underactuated and adaptive hands that could reconfigure noise caused by control or model error <cit.>. The use of underactuated hands relaxes the control dimensionality and constraints of the task while compensating for the lack of explicit models by close loop manipulation through sensor feedback using vision <cit.>, or tactile sensing <cit.>. Utilize the compliance of the robot hands, the system could learn manipulation through self-identification<cit.> where the robot hand could do random exploratory action and estimates the hand-object configuration while maintaining a stable grasp without an accurate control model. However, the prior method still requires knowledge about the robot hand model for self-identification and manipulation. This motivates us to develop a model-free predictive method to self-identify the hand-object system model without knowing or inferring the system parameters.

§ HAND-OBJECT SYSTEMS AND PROBLEM FORMULATION

The goal of this work is to create a closed-loop control and planning policy that enables the underactuated robot hand to manipulate some object to trace. We begin by modeling the robot as a discrete-time dynamical system defined by the transition function of the form

\begin{equation}
\begin{split}
s_{t+1} &= g(s_t, u_t)\
\end{split}
\label{eq:transition}
\end{equation}

where the underlying state of the object-hand configuration is $s_t \in \Rb^N$ at time $t$. The system states $s_t$ contains all physical properties of the system, such as joint configurations and object-hand contact locations. The system executes an actuation input $u_t \in \Rb^C$ and ends up at state $s_{t+1}$ at time $t + 1$. The unknown function $g: \Rb^N \times \Rb^C \to \Rb^N$ captures the dynamic model of the hand-object system.

However, the state $s_t$ represents the system in an over-complicated manner and contains several parameters that could not be directly obtained from the system like contact points and joint angles. To generalize the state, the geometric properties of an arbitrary object within grasp [34] are being tracked as a fixed point on the object's surface, termed the point of manipulation (POM). A frame at POM $z_t \in SE(2)$ portrays the object's local geometry and standardizes the hand-object configuration's representation $s_t$. Thus, the goal of the manipulation task is to move a frame of POM $z_t$ through all $T$ waypoints in reference trajectory $X = {x_1, \cdots, x_T}$, where $x_t \in SE(2)$.

We could define a local control region as a region where the changes of the hand-object states are minimal and negligible after applying a small control. Within this region, we could derive an estimated system motion function without the knowledge of the current hand-object configuration $s_t$ as $\Gamma: \Rb^C \to se(2)$

\begin{equation}
\begin{split}
\Gamma(u_t) &\mathrel{\widehat{=}} z_{t+1} - z_t
\end{split}
\label{eq:estimate}
\end{equation}

Therefore, an accurate estimate function $\Gamma(u_t)$ is a key factor that dictates in-hand manipulation's performance. In addition, the system also learns the inverse system motion function $\Gamma^{-1}(\dot): se(2) \to \Rb^C$ generating an initialization for a robust controller that stabilizes the system during manipulation. While tracing the reference trajectory, the system will continuously refine the estimating models and improve the manipulation performance.

In this paper, we formulate the manipulation process as illustrated in Fig  <ref> and outlined in Algorithm  <ref>. $\Gamma(\dot)$ and $\Gamma^-1(\dot)$ models are learned using data collected from the exploratory actions defined in Section <ref>. Starting from the initial position $x_0$, the system controls the frame at POM to sequentially go through $x_1, \cdots, x_T$ in $X$. The control framework utilizes Model Predictive Control (MPC) to optimize the next actuation input $u_t$ in order to reach the currently targeted waypoint $x_i$. If the manipulation frame is found to have reached $x_i$ within some distance threshold, $\alpha$, the targeted waypoint is updated to be $x_{i+1}$. The process will continue until reaching $x_T$. After each executed action, the system observes the object's POM by sensors and uses the sensor readings to improve $\Gamma$ and $\Gamma^{-1}$.

Manipulation System via Self-Id and MPC

Input Targeted trajectory $X$, Distance threshold $\alpha$

Output Control sequence $U$
[1]
$t = 0$
$x_0, z_0 \gets \Call{Initial POM}{} $
$\Gamma, \Gamma^{-1} \gets \Call{Learning from exploratory actions}{}$
Section <ref>
$x_i \in X$ , $i = 1,\cdots, n$
$\|x_i - z_t \| < \alpha$
$u_t \gets \Call{MPC}{z_t}$ Section <ref>
$z_{t+1} \gets \Call{Execute Action}{u_t}$
$\Gamma, \Gamma^{-1} \gets \Call{Model Improvement}{z_{t+1}}$
Section <ref>
$U \text{ add } u_t$
$t \gets t+1$

§ HAND-OBJECT MODEL LEARNING

GPs are stochastic processes capable of modeling continuous functions. They are infinite-dimensional extensions of multivariate Gaussian distributions. GPs may be regarded and utilized as distributions over functions since they extend Gaussian distributions to the case of infinite dimensionality. Because of their expressiveness and flexibility, GPs are excellent nonlinear function approximators when specifying parametric forms for unknown functions and models is challenging, and high-quantity data collection is difficult<cit.>.

In this section, we present an approach to learning the manipulation model of an underactuated hand through exploratory actions. Taking advantage of the robot's compliance, the system could gather motion samples for the training dataset, while maintaining grasp stability. Given a set of $P$ training data points $\{\bar{u}_i, \bar{z}_i\}_{i=1,\cdots,P}$, we intended to learn the functions $\Gamma$ and $\Gamma^{-1}$, which correlated the actuation input with the object's motion, by using Gaussian Process (GP) regression. The shape of the GP is governed by a Radial basis function (RBF) kernel

\begin{equation}
k(x_p, x_q) = \exp\left(-\frac{\|x_p - x_q\|^2}{2l^2}\right)
\end{equation}

where $l > 0$ is a length-scale hyperparameter of the kernel function.

§.§ Exploratory manipulation actions

To obtain data points for GP models estimation, a set of actuation input $\bar{U} \subset \Rb^{C}$ is executed, then the system could observe the corresponding change in the object's POM $\bar{Z} \subset se(2)$. Without prior knowledge about the hand-object configuration, the system begins by generating initial $d$ actuation input $U_{random}$. Each of the $d$ random actuation inputs is randomly generated from the C-dimension uniform distribution $\mathcal{U}_C(-l, l)$ where $l$ is defined to be arbitrarily small, while not being overwhelmed by the noise from the system's physical constraints. The random actions are executed and the change in the object's POM is recorded accordingly as $Z_{random}$.

However, certain patterns of objects' POM motions might not be presented in $Z_{random}$ when using only a limited amount of random actions. So, we intended to fill the gap in set $\bar{Z}$ by selecting additional $a$ actuation inputs by assuming a linear relationship between $\bar{U}$ and $\bar{Z}$. One by one, the next actuation input $u_select$ is selected so that it approximately creates an object's POM motion located in the largest gap in $\bar{Z}$. Let $Z'$ be a sorted list of the existing $\bar{Z}$ and $U'$ be a reordered list of the existing $\bar{U}$. $u_select$ is selected to be linear interpolation between the largest gap between  index $\widehat{k}$ and $\widehat{k} - 1$ according to the optimization problem

\begin{align} \label{eq:select_gap}
\widehat{k} &= \underset{1 < k \leq \|Z'\|}{\Call{Argmax}{}}\|z'_k - z'_{k-1}\|\\
u_{select} &= \frac{u'_{\hat{k}} + u'_{\hat{k}-1}}{2}
\end{align}

The selected actions are executed and the change in the object's POM is recorded as $z_{random}$. The process is repeated for $a$ times so that all of the new control samples are added to the training data set $\{\bar{u}_i, \bar{z}_i\}_{i=1,\cdots,P}$. Finally, the system uses the training data set to train $\Gamma$ and $\Gamma^{-1}$ using the GP regression model.

Learning from exploratory actions

Input Number of random actions $d$, Number of selected actions $a$

Output $\Gamma, \Gamma^{-1}$

$\bar{U} , \bar{Z} \gets \Call{Previous data}{}$
$U_{random} \gets \Call{Random actions}{d}$ Alg.  <ref>
$Z_{random} \gets \Call{Execute actions}{U_{random}}$ Alg.  <ref>
$\bar{U} \gets \bar{U} + U_{random}$, $\bar{Z} \gets \bar{Z} + Z_{random}$
$i = 1, \cdots, a$
$iter \gets \Call{Argsort}{\bar{Z}}$
$U' = \bar{U}[iter]$, $Z' = \bar{Z}[iter]$
$\hat{k} \gets \underset{1 < k \leq \|Z'\|}{\Call{Argmax}{}}\|z'_k - z'_{k-1}\|$
$u_{select} \gets (u'_{\hat{k}} + u'_{\hat{k}-1}) / 2$
$z_{select} \gets \Call{Execute actions}{\{x_{select}\}}$ Alg.  <ref>
$\bar{U} $ add $u_{select}$, $\bar{Z}$ add $z_{select}$
$\Gamma \gets \Call{GP Model}{\bar{Z}, \bar{U}}$
$\Gamma^{-1} \gets \Call{GP Model}{\bar{U}, \bar{Z}}$

$\Gamma$, $\Gamma^{-1}$

Random Actions

Input The number of actions $d$

Output Exploratory actions $\widehat{U}$

$i = 1, \cdots, d$
$l \gets \Call{Acutation input limits}{}$
$\widehat{U}$ add $\mathcal{U}_c(-l, l)$

Execute Actions

Input Exploratory actions $\widehat{U}$

Output Sensory feedback $Z$

$i = 1, \cdots, \|\widehat{U}\|$
$z_{t+1} \gets \Call{Execute Action}{\widehat{u}_i}$
$Z$ add $z_{t+1} - z_{t}$

§.§ Transfer Model

The initial data-gathering process will take a significant amount of time for the exploratory action selection. We could speed up the system using the transfer model that improves a learner from one domain of a hand-object configuration by transferring information from a related domain. If the actuation inputs and the measured object's POM output are both derived from in-hand manipulation using the same robot hand and similar-size rigid object, models learned in different domains would certainly retain a number of common characteristics.

Each object manipulation could have a different setting, for example, different manipulated objects, different initial grasping locations, or different robot's physical configurations. These differences create a unique domain, in which the relationship between the object and the robot's hand happens differently due to these physical conditions. We define a source domain $\mathcal{S}$ where training data $\{\bar{u}_i, \bar{z}_i\}_{i=1,\cdots,P}^\mathcal{S}$ is collected. Thus, we could define a transfer model process by using the training data $\{\bar{u}_i, \bar{z}_i\}_{i=1,\cdots,P}^\mathcal{S}$ from the source domain to train the system motion model $\Gamma_\mathcal{T}$ and $\Gamma_\mathcal{T}^{-1}$ in the target domain $\mathcal{T}$. So, the targeted domain could skip Section <ref> to accelerate the initial learning process.

Next, we propose our second method for improving the system efficiency based on MPC.

§ MODEL PREDICTIVE CONTROL

The proposed self-identification framework utilizes Model Predictive Control (MPC) as the next control input optimizer after each system step. The framework helps mitigate errors caused by inaccurate prediction models $\Gamma$ and $\Gamma^{-1}$ or unmodeled physical scenarios i.e. rolling or slipping in hand-object contacts. For the currently targeted waypoint $x_i$ for $i = 1, \cdots, T$, intermediate trajectory $W_i = \left(w_i^1, w_i^2, \cdots, w_i^M\right)$ with $M$ waypoints is created from the linear interpolation between $x_i$ and $x_{i-1}$ with the interpolation distance $\beta$ to smooth out the manipulation.

To optimize for the next auction input, MPC creates $Q$ actuation input sequence. For each sequence, $U^q$ where $q = 1, \cdots, Q$, the controller evaluates the cost of actuation inputs over a prediction horizon $N$. This horizon parameter indicates how far ahead the control framework evaluates the trajectories. The prediction starts at the waypoint $w^{j^*}_i$ on $W_i$ that is nearest to the current state $z_t$ where

\begin{equation} \label{eq:nearest_point}
j^* = \underset{j}{\Call{Argmax}{}} \| w^j_i - z_t\|
\end{equation}

Then, the MPC recursively propagates the predicted trajectories for the next $L = \Call{Min}{N, M - }$ system steps where it completes the prediction horizon $N$ reaches the end of trajectory $W_i$. The state and control prediction is recursively calculated using the learned model $\Gamma$ and $\Gamma^{-1}$ respectively

\begin{equation} \label{eq:prop}
\begin{aligned}
\widehat{u}_{t+k}^q &= \Gamma(w_i^{j^*+k} - \widehat{z}_{t+k}^j) + \epsilon\\
\widehat{z}_{t+k+1}^q &= \Gamma^{-1}(\widehat{u}_{t+k}^q) + \widehat{z}_{t+k}^q
\end{aligned}
\end{equation}

where $\widehat{u}_{t+k}^q$ is a predicted control at time $t+k$ of the sequence $q$ starting at time $t$, $\widehat{z}_{t+k}^q$ is a predicted system state at time $t+k$ of the sequence $q$ starting at time $t$, $\sigma$ is a MPC optimization scale, and $\epsilon$ is a manipulation disturbance generate from $\mathcal{N}(0, \sigma \mathbb{I}_{c\times c})$

With such a formulation of state prediction, the controller generates the control sequence $U^q = (\widehat{u}_t^q, \cdots, \widehat{u}_{t+L}^q)$, where the state and control prediction is slightly different due to the randomness from $\epsilon$ as demonstrated in Fig. <ref>. The prediction with the minimum cost function will be chosen by using the optimization procedure. The optimization problem is

\begin{equation}  \label{eq:min}
q^* = \underset{q}{\Call{Argmin}{}}\left(\sum^L_{k=0}\|\widehat{z}^q_{t+k} - w_i^{j^*+k}\|\right)
\end{equation}

Even though control input is calculated for the next $L$ control steps, only the first control input, $\widehat{u}_t^{q^*}$, of the chosen prediction is executed as the actuation input $\dot{a}_{t+1}$ by the robot hand, and the optimization problem is solved again for the iteration with a new starting position and targeted waypoints.

Input Current frame at POM $z_t$, Trajectory $W_i$

Output Control Input $\dot{a}_{i+1}$

$j^* \gets \underset{j}{\Call{Argmax}{}} \| w^j_i - z_t\|$Get nearest waypoint
$L \gets \Call{min}{N, M - j^*}$
$q = 1, \cdots , Q$
$k = 0, \cdots, L-1$
$\sigma \gets \Call{MPC Optimization Scale}{}$
$\epsilon \gets \mathcal{N}(0, \sigma \mathbb{I}_{c\times c})$
$\widehat{u}_{t+k}^q \gets \Gamma(w_i^{j^*+k} - \widehat{z}_{t+k}^j) + \epsilon$
$\widehat{z}_{t+k+1}^q \gets \Gamma^{-1}(\widehat{u}_{t+k}^q) + \widehat{z}_{t+k}^q$
$q^* \gets \underset{q}{\Call{Argmin}{}}\left(\sum^L_{k=0}\|\widehat{z}^q_{t+k} - w_i^{j^*+k}\|\right)$

Prediction made by MPC: The blue line indicated the best prediction that is closest to the reference trajectory $W_i$. All $Q$ predictions are shown as light grey lines with slight differences generated by random variable $epsilon$. The Number of deviation is $Q = 50$ and the optimization window size is $N = 5$

§.§ Model Improvement

During the manipulation, the predicted models could lose a locality due to changes in grasp configuration or system states. These changes could cause manipulation errors larger than what MPC could cover. We define the manipulation errors by

\begin{equation} \label{eq:manipulation_error}
\varepsilon(t) = \|z_t - w_i^{j^*}\|
\end{equation}

where $z_t$ is the current frame at POM and $w_i^{j^*}$ is the nearest point on the $W_i$ to $z_t$ (See eq. <ref>). Each time the error $\varepsilon(t)$ crosses a certain error threshold $\gamma$, the system will locally re-sample and generate additional $b$ data points at the current system state following the Algorithm <ref> and add them to the training dataset $\{\bar{u}_i, \bar{z}_i\}_{i=1,\cdots,P}$. Then, the algorithm generates new $\Gamma$ and $\Gamma^{-1}$ models with the new training dataset as shown in Fig  <ref>.

Model Improvement

Input Current frame POM $z_t$, Trajectory $W_i$, the number of generated data $b$

Output $\Gamma$, $\Gamma^{-1}$

$j^* \gets \underset{j}{\Call{Argmax}{}} \| w^j_i - z_t\|$ Get nearest waypoint
$\| z_t - w^{j^*}_i \| \geq \gamma$
$\Call{Exploratory actions}{0, b}$ Section  <ref>
$\Gamma$, $\Gamma^{-1}$ The models remain unchanged

Datapoint from exploratory manipulation actions: (A) Initial $d+a$ samples obtained at the beginning of each manipulation task, (B) The manipulation error $\varepsilon(t)$ is exceeded the threshold $\gamma$ triggering the resampling process. (C)  Additional $b$ data points sampled from the re-sampling method: The red lines indicate the collected measurement $\bar{Z}$ corresponding to each exploratory action

§ EXPERIMENT AND RESULT

In this section, we will evaluate and challenge the proposed self-identification algorithm on a Yale Model O underacted hand. As shown in  Fig. <ref>, Model O has three identical fingers with two joints and one actuator motor. The gripper provides mechanical compliance during a precision grasp; when the springs are active (not in the resting state), they provide restoring force that keeps contact with the object. The gripper is able to do precise object manipulations. In this experiment, the two side fingers are restricted to be parallel to each other and have the same starting configuration and the same actuation input, which limits the movement of the object's POM to be on a planar.

We track the trajectory of the manipulated object using a camera fixed directly above to observe the motion of the POM. Each object has a different AprilTag <cit.> on top for the POM tracking, which is observed via an AprilTag tracker. Note that, other vision-based tracking methods could replace the current tag-based POM.

With this setup, camera calibration is not needed since the reference trajectory and predicted motions of POM are both defined in the camera's frame. The camera is set to 512x1024 pixels resolution and 30 fps capture rate. In each experiment, the object is handed to the gripper by the experimenter with the AprilTag facing the camera. Other parameters such as object model, hand configuration, or contact locations are unknown to the system.

Experimental setup: The hand-object system is validated using a Yale Model O hand. The manipulated objects are observed by one top camera, which is used for tracking the Apriltags on the POM of the object.

In-hand manipulation applications based on self-identification with MPC: The POM of the object was controlled to move through waypoints to draw geometric shapes including triangle, square, pi, and spiral. Green lines represent the reference trajectory for the POM to follow, and the black dots are the waypoints that the POM needs to go through sequentially.

Test Objects: five objects for the experiments including a pill bottle, a mustard bottle (YCB dataset #006), an apple (YCB dataset #013), an orange box, and a toy airplane (YCB dataset #072a) respectively from left to right <cit.>.

§.§ Experiment with the number of initial samples

With a different number of exploratory actions for training the initial GP model, we evaluated the performance of the self-identification process by manipulating objects in Fig.<ref> through different trajectories in Fig.<ref>. For each experiment, the robot hand randomly manipulates the object and generates initial d = 5 samples then use a method in Section <ref> to generate more samples until reaching the targeted number of initial samples. The system could acquire more data points when the manipulation error $\varepsilon(t)$ exceeds the threshold $\gamma =$ 2mm as stated in Section <ref>. As shown in Fig. <ref>, each trajectory consists of multiple waypoints. To complete the trajectory tracing task, the system must visit each waypoint with a tolerance limit of $\alpha =$ 1 mm in the correct order. The maximum scale of the shape was 16 mm in both horizontal and vertical directions. For each setting, the experiment is repeated 5 times. We then record the total number of data points including those from the re-sampling section, and the average manipulation error presented in Fig. <ref> and Fig. <ref> respectively. From these figures, it can be seen that with smaller numbers of initial samples, the average manipulation errors are higher and the numbers of re-sampling instances are higher as well. The performance of the system is improved with the increasing number of initial samples up to 20 initial samples that system have enough data point with just the initial samples and the re-sampling method rarely happen.

The experiment with the number of initial samples using the orange box. The average manipulation error $\varepsilon(t)$ (See eq. <ref>) for all system steps $t$. Each box represents an experiment with all of the trajectories from Fig  <ref> with the same object and the number of initial samples.

The experiment with the number of initial samples using the orange box. The total number of data points acquired via re-sampling is presented. Each box represents an experiment with all of the trajectories from Fig  <ref> with the same object and the number of initial samples.

§.§ Experiment with MPC optimization scale

To evaluate the effectiveness of an MPC method to compensate for errors generated by the GP model, we experiment with different $\sigma$ values that would change the MPC optimization scale and the coverage of the MPC method. The higher the $\sigma$ value is the more randomness we apply to the disturbance model. In this section, we also only use the rectangular shape for the consistency of the evaluation. For the MPC method, the optimization window is set to 5 and the number of predicted sequences $Q$ is 50. The experiment setting is similar to Section <ref> with the number of initial samples parameter: the hand has to trace the manipulated object’s POM through different trajectories and the experiment is repeated 5 times for each setting.

Then, we record the number of data points from model improvement in Section <ref>. A high number of re-sampling data points indicate that the manipulation system is more likely to not be robust enough to compensate for the manipulation error, which is represented through x. As seen from a result in Fig. <ref>, the MPC method couldn't compensate for the error very well with zero to low $\sigma$ value (variance less than 0.02) as reflected in a high number of re-sampling data points. However, with a high enough $\sigma$ value, the MPC is doing a much better job at keeping the manipulation error low and the number of re-sampling instances is significantly lower.

The experiment with the manipulation disturbance value in Model Predictive Control(MPC). The total number of data points acquired via re-sampling is presented. Each box represents an experiment with all of the trajectories from Fig  <ref> with the same object and manipulation disturbance value.

§.§ Transferring model to different grasp configurations

In this section, we challenge self-identification and evaluate the generalizability of the learned GP models. Each time the robot grasps an object, there would be some differences in grasp configuration coming from changes in contact location and object shape itself: however, there are still some similarities in robot control input and object’s trajectory. It is deemed possible to use some knowledge learned from previous manipulation tasks in the next one. When the hand manipulates the object the algorithm will save the GP model. Then, the algorithm will use that model in place of the initial exploratory manipulation actions in Section <ref> when manipulating a different object or different grasp location. In this experiment, we save models trained on the rectangular shape with 25 samples and then use the model with objects shown in Fig. <ref> for the trajectory tracing. The experiment is repeated 4 times for each setting. As shown in Fig.  <ref>, there is no significant increase in the average manipulation error from the source domain compared to the targeted domains of the transfer model method. While the targeted domain requires more instances of the re-sampling method, the total number of exploratory actions needed is reduced from an average of 25 to averages of less than 12 samples as shown in Fig.<ref>

The experiment with transferring model to different grasp configurations. The average manipulation error during the entire task is presented. Each box represents an experiment with all of the trajectories from Fig  <ref> with one of the objects shown in Fig  <ref>.

The experiment with transferring model to different grasp configurations. The total number of data points used to train the GP model is presented. Each box represents an experiment with all of the trajectories from Fig  <ref> with one of the objects shown in Fig  <ref>.

§ CONCLUSION

In this paper, we proposed a method that combines a non-parametric learning model with an MPC method with the goal of learning a controller for in-hand manipulations that guarantee stability with improving performance. A Gaussian Process (GP) is used to learn a nonlinear model of the unknown dynamics systems. Based on the self-exploratory actions, the model is updated, and learned the system model. Finally, a controller will compensate for some uncertainty that occurs from the model. Experiments on the Yale O Model underactuated hand showed that the controller improve as more data became available and MPC increase the performance of in-hand manipulation. Also, it is shown that a transfer model that learned from one hand configuration to a different hand configuration will preserve the high-precision manipulation

In future work, we aim to improve the exploratory action selection algorithm to guarantee a certain level of equal distribution of those selected actions in the object’s movement space based on the predicted model. Also, we intended to subsequently test the self-identification algorithm with higher dimensions in both robot actuation input and the object’s POM space.


[datatype=bibtex, overwrite=true] [fieldsource=booktitle,
match=.*Interspeech.*, replace=Proc. Interspeech] [fieldsource=journal,
match=.*INTERSPEECH.*, replace=Proc. Interspeech] [fieldsource=booktitle,
match=.*ICASSP.*, replace=Proc. ICASSP] [fieldsource=booktitle,
match=.*icassp_inpress.*, replace=Proc. ICASSP (in press)]
[fieldsource=booktitle, match=.*Acoustics,.*Speech.*and.*Signal.*Processing.*,
replace=Proc. ICASSP] [fieldsource=booktitle,
match=.*International.*Conference.*on.*Learning.*Representations.*,
replace=Proc. ICLR] [fieldsource=booktitle,
match=.*International.*Conference.*on.*Computational.*Linguistics.*,
replace=Proc. COLING] [fieldsource=booktitle,
match=.*SIGdial.*Meeting.*on.*Discourse.*and.*Dialogue.*, replace=Proc.
SIGDIAL] [fieldsource=booktitle,
match=.*International.*Conference.*on.*Machine.*Learning.*, replace=Proc.
ICML] [fieldsource=booktitle,
match=.*North.*American.*Chapter.*of.*the.*Association.*for.*Computational.*Linguistics:.*Human.*Language.*Technologies.*,
replace=Proc. NAACL] [fieldsource=booktitle,
match=.*Empirical.*Methods.*in.*Natural.*Language.*Processing.*, replace=Proc.
EMNLP] [fieldsource=booktitle,
match=.*Association.*for.*Computational.*Linguistics.*, replace=Proc. ACL]
[fieldsource=booktitle,
match=.*Automatic.*Speech.*Recognition.*and.*Understanding.*, replace=Proc.
ASRU] [fieldsource=booktitle, match=.*Spoken.*Language.*Technology.*,
replace=Proc. SLT] [fieldsource=booktitle,
match=.*Speech.*Synthesis.*Workshop.*, replace=Proc. SSW]
[fieldsource=booktitle, match=.*workshop.*on.*speech.*synthesis.*,
replace=Proc. SSW] [fieldsource=booktitle,
match=.*Advances.*in.*neural.*information.*processing.*, replace=Proc.
NeurIPS] [fieldsource=booktitle,
match=.*Advances.*in.*Neural.*Information.*Processing.*, replace=Proc.
NeurIPS] [fieldsource=booktitle, match=.*Workshop.*on.* Applications.* of.*
Signal.*Processing.*to.*Audio.*and.*Acoustics.*, replace=Proc. WASPAA]
[fieldsource=publisher, match=.+, replace=] [fieldsource=month, match=.+,
replace=] [fieldsource=location, match=.+, replace=] [fieldsource=address,
match=.+, replace=] [fieldsource=organization, match=.+, replace=]
ffiliation=1]DarshanPrabhu ffiliation=2]YifanPeng ffiliation=1]PreethiJyothi
ffiliation=2]ShinjiWatanabe

#  Multi-Convformer: Extending Conformer with
Multiple Convolution Kernels

###### Abstract

Convolutions have become essential in state-of-the-art end-to-end Automatic
Speech Recognition (ASR) systems due to their efficient modelling of local
context. Notably, its use in Conformers has led to superior performance
compared to vanilla Transformer-based ASR systems. While components other than
the convolution module in the Conformer have been reexamined, altering the
convolution module itself has been far less explored. Towards this, we
introduce Multi-Convformer that uses multiple convolution kernels within the
convolution module of the Conformer in conjunction with gating. This helps in
improved modeling of local dependencies at varying granularities. Our model
rivals existing Conformer variants such as CgMLP and E-Branchformer in
performance, while being more parameter efficient. We empirically compare our
approach with Conformer and its variants across four different datasets and
three different modelling paradigms and show up to 8% relative word error rate
(WER) improvements.

###### keywords:

Automatic Speech Recognition, Conformer, Multiple Convolutions, CgMLP.

##  1 Introduction

In recent years, end-to-end automatic speech recognition (ASR) systems have
emerged as the preferred model of choice to obtain state-of-the-art ASR
performance. An integral component of such systems is the speech encoder [1,
2] that uses Attention via Transformers [3] to map the input speech into high-
level acoustic representations. Transformer-based ASR systems [4, 5] often
struggle to model local relationships effectively. To address this limitation,
Gulati et al. [6] proposed the Conformer [7] architecture, that combines
multi-headed attention with convolutions [8, 9, 10]. With the advent of
Conformer models, the idea of using convolutions alongside attention to
independently model both local and global relationships has been widely
explored [11, 12, 13, 14].

Figure 1: Overview of our MultiConv encoder layer. It comprises a stacked
architecture similar to Conformer, except the convolution block is replaced
with a gated multi-kernel convolution block. We omit residual connections and
layer norm for readability.

Despite these notable advancements, prior work [11] has shown that the use of
fixed-kernel convolutions within these models creates a bottleneck, forcing
the model to re-purpose some of its attention heads to function as local
information extractors. This negatively impacts the performance of attention,
whose primary purpose is to model global information. To address this
limitation, in our work, we propose a multiple convolution-based enhancement
to the Conformer architecture (that we call Multi-Convformer). Additionally,
we incorporate gating, a technique that has proven to be effective in encoder
architectures [15, 11, 12]. By combining these approaches, we achieve
significant improvements (up to 8% relative WER improvement) over the original
Conformer architecture and perform at par or better than its variants such as
CgMLP [15] and E-Branchformer [12]. The use of multiple convolutions in order
to generate better local context has been widely adopted in image-related
tasks [16, 17, 18, 19, 20]. Such enhancements have also been used in speech
emotion recognition [21] and robust ASR [22, 23]; the latter works use
multiple convolutions within fully convolutional or TDNN-style architectures
(unlike our work).

Figure 2: Overview of the four variants of the Fusion() operation in our
proposed Multi-kernel Convolutional Spatial Gating Unit (M-CSGU) block that
demonstrates how convolution kernels with $K=\\{7,15,23,31\\}$ are used in our
MultiConv block. Briefly, the four architectures are as follows: In (a)
element-wise addition is employed on the outputs of the convolutions to
generate the final output. (b) builds upon (a) by learning weights that
determine the importance of each convolution's output. (c) uses compression
kernels to reduce the input by $1/4^{\text{th}}$ and then concatenates all of
them frame-wise to generate the output. (d) further enhances (c) by using an
additional depthwise convolution at the end that takes neighboring frames into
account when generating the final output.

In summary, our main contributions are as follows:

  * •

We propose Multi-Convformer, a variant of Conformer that uses multiple
convolution kernels instead of a fixed kernel convolution to capture local
context more effectively.111Our code is available in the ESPnet toolkit.

  * •

We show the effectiveness of our approach by comparing with Conformer and its
variants on ASR and Spoken Language Understanding (SLU). We experiment with
multiple datasets (Librispeech [24], Tedlium2 [25], AISHELL [26] and SLURP
[27]) and various modelling paradigms and obtain up to 8% relative WER
improvement over Conformer. We also conduct several analyses and ablations to
showcase the effectiveness and interpretability of our approach.

##  2 Methodology

In this work, we experiment with the three most popular ASR architectures: the
attention-based encoder-decoder model (AED) [28], the encoder-only model (pure
CTC) [29] and the RNN-Transducer model (RNN-T) [30]. An essential component
common to all these architectures is the encoder (Enc) module that maps an
input sequence of speech
features$X=\\{\mathbf{x}_{1},\mathbf{x}_{2},\ldots,\mathbf{x}_{L}|\mathbf{x}_{i}\in\mathbb{R}^{c}\\}$
to a (typically smaller) sequence of contextualized representations
$H=\textsc{Enc}(X)=\\{\mathbf{h}_{1},\mathbf{h}_{2},\ldots\mathbf{h}_{T}|\mathbf{h}_{i}\in\mathbb{R}^{d}\\}$.
Thereafter, the manner in which $H$ is trained to predict the final $M$-length
ground-truth token sequence
$Y=\\{y_{1},y_{2},\ldots,y_{M}|y_{i}\in\mathbb{N}^{+}\\}$ depends on the
underlying architecture. AED uses an attention-based decoder and a CTC module
to jointly learn a mapping from $H$ to $Y$. However, pure CTC and RNN-T are
encoder-only models that employ CTC [31] and RNN-T [30] losses, respectively,
to generate $Y$. Since our modifications are constrained to the encoder, in
subsequent sections, we restrict our discussion only to the composition of the
Enc module.

###  2.1 Multi-Convformer Encoder

Figure 1 illustrates the overall architecture of a single Multi-Convformer
encoder layer and Figure 2 gives an overview of how the outputs from multiple
convolutions are merged together. The Multi-Convformer encoder layer consists
of four blocks that are stacked together and interspersed with layer
normalization [32] and residual connections. The two position-wise feed-
forward layers aid in refining the point-wise information, while the multi-
head attention and convolution are responsible for incorporating contextual
information. This stacked architecture has been widely used in prior work [6,
11, 12, 33]. We adopt this same stack, but replace the fixed single-kernel
convolution block with a more expressive multi-kernel convolution module that
will henceforth be referred to as MultiConv.

Table 1: Comparing the performance (CER or WER %) of our proposed system
against Transformer and Conformer on three datasets. The three sections are:
(1) AED: Encoder-Decoder models with joint CTC-Attention loss, (2) Pure CTC:
Encoder-only model where only CTC loss is employed and (3) RNN-T: RNN based
Transducer model.  denotes the best CER / WER across all experiments.
$\dagger$ and $\ddagger$ indicate statistically significant results compared
to Conformer at $p<0.05$ and $p<0.001$ using MAPSSWE test [34], respectively.

Method | Librispeech-100h (WER) | Tedlium2 (WER) | AISHELL (CER)
---|---|---|---
# params | Dev Clean | Dev Other | Test Clean | Test Other | # params | Dev | Test | # params | Dev | Test
Attention Encoder Decoder (AED) models
Transformer [35] | 40.9M | 8.02 | 20.14 | 8.39 | 20.34 | 33.8M | 10.13 | 8.83 | 47.7M | 5.16 | 5.53
Conformer [6] | 37.4M | 6.59 | 17.24 | 6.89 | 17.27 | 33.9M | 9.30 | 7.65 | 54.2M | 4.23 | 4.63
black!50 black $\textsc{MultiConv}_{\texttt{sum}}$ | 37.0M | 6.00 |  green!20 16.56 $\ddagger$ | 6.33 |  green!20 16.60 $\ddagger$ | 33.5M |  green!20 7.99 $\ddagger$ | 7.34 | 54.2M | 4.18 | 4.47
$\textsc{MultiConv}_{\texttt{weighted}}$ | 37.1M | 6.17 | 17.03 | 6.48 | 17.36 | 33.6M | 8.15 | 7.41 | 54.4M | 4.40 | 4.67
$\textsc{MultiConv}_{\texttt{concat}}$ | 37.0M | 6.23 | 17.19 | 6.41 | 17.15 | 33.5M | 8.32 | 7.42 | 54.2M |  green!20 4.16 $\dagger$ |  green!20 4.46 $\dagger$
$\textsc{MultiConv}_{\texttt{depth}}$ | 37.2M |  green!20 5.87 $\ddagger$ | 16.63 |  green!20 6.18 $\ddagger$ | 17.00 | 33.7M | 8.01 |  green!20 7.27 $\ddagger$ | 54.7M | 4.18 |  green!20 4.46
Encoder Only (Pure CTC) models
Transformer [35] | 28.9M | 12.32 | 27.49 | 12.88 | 28.26 | 27.7M | 11.97 | 11.71 | 28.7M | 6.51 | 7.02
Conformer [6] | 25.4M | 9.33 | 22.60 | 9.76 | 23.10 | 24.2M | 9.65 | 8.80 | 39.9M | 5.98 | 6.59
black!50 black $\textsc{MultiConv}_{\texttt{depth}}$ | 25.1M |  green!20 9.24 |  green!20 22.26 $\dagger$ |  green!20 9.47 $\dagger$ |  green!20 23.09 | 24.0M |  green!20 8.81 $\dagger$ |  green!20 8.44 $\ddagger$ | 40.2M |  green!20 5.67 $\ddagger$ |  green!20 6.01 $\ddagger$
RNN Transducer (RNN-T) models
Transformer [35] | 32.5M | 9.18 | 22.40 | 9.43 | 22.95 | 28.7M | 10.26 | 9.65 | 31.8M | 5.69 | 6.21
Conformer [6] | 28.9M | 6.79 | 18.28 | 7.19 | 18.70 | 25.2M | 8.37 | 7.96 | 43.0M | 4.93 | 5.22
black!50 black $\textsc{MultiConv}_{\texttt{depth}}$ | 28.7M |  green!20 6.60 |  green!20 17.53 $\ddagger$ |  green!20 7.05 |  green!20 18.23 $\ddagger$ | 24.9M |  green!20 8.20 |  green!20 7.67 | 43.4M |  green!20 4.65 $\ddagger$ |  green!20 5.05

As illustrated in Figure 1, in a single encoder layer, the output from the
multi-head attention block
$A=\\{\mathbf{a}_{1},\mathbf{a}_{2},\ldots,\mathbf{a}_{T}\
|\mathbf{a}_{j}\in\mathbb{R}^{d}\\}$ is first normalized with a layer
normalization. Subsequently, it undergoes channel projection to increase its
dimensionality from $d$ to $d_{\text{inter}}$222Here $d_{\text{inter}}>d$.
Typically, $d_{\text{inter}}=6d$. Using a higher intermediate dimension has
been shown to be an effective strategy for position-wise feedforward layers
[36].. To introduce non-linearity to the representation, we apply GELU [37]
activation. The resulting output,
$\hat{A}=\\{\mathbf{\hat{a}}_{1},\mathbf{\hat{a}}_{2},\ldots,\mathbf{\hat{a}}_{T}|\mathbf{\hat{a}}_{j}\in\mathbb{R}^{d_{\text{inter}}}\\}$,
is then passed through our Multi-kernel Convolutional Spatial Gating Unit
(M-CSGU). M-CSGU is a more powerful alternative [11, 12] to the standard
convolution block due to its usage of gates [38] along with convolutions.
Finally, we employ another channel projection layer that projects the output
from $\mathbb{R}^{d_{\text{inter}}}$ back to $\mathbb{R}^{d}$, followed by
dropout for regularization.

Multi-kernel Convolutional Spatial Gating Unit (M-CSGU): M-CSGU module takes
$\hat{A}$ as its input. We first bifurcate each representation in $\hat{A}$
into two parts, each having dimension $d^{\prime}=d_{\text{inter}}/2$. Only
one part undergoes layer normalization and passes through multiple
convolutions; the other part stays intact. These parts are multiplied element-
wise, thus creating a gate. Next, we use $P$ depthwise convolutions with
kernel sizes $K=\\{k_{1},k_{2},\ldots,k_{P}\\}$. Formally, these operations
are as follows:

$\displaystyle[Z_{l},Z_{r}]$
$\displaystyle=[\hat{A}[:,:d^{\prime}],\texttt{LayerNorm}(\hat{A}[:,d^{\prime}:])]$
$\displaystyle[V_{1},V_{2},\ldots,V_{P}]$
$\displaystyle=[\texttt{Conv}_{k_{1}}(Z_{r}),\ldots,\texttt{Conv}_{k_{P}}(Z_{r})]$
$\displaystyle\tilde{Z}_{r}$
$\displaystyle=\textsc{Fusion}([V_{1},V_{2},\ldots,V_{P}])$
$\displaystyle\hat{C}$ $\displaystyle=Z_{l}\odot\tilde{Z}_{r}$ (1)

where $\hat{A},\hat{C}\in\mathbb{R}^{T\times d_{\text{inter}}}$,
$Z_{l},Z_{r},V_{j},\tilde{Z}_{r}\in\mathbb{R}^{T\times d^{\prime}}$, $\odot$
represents element-wise products, $\texttt{Conv}_{k_{i}}()$ refers to a
depthwise convolution with kernel size of $k_{i}$ and $\hat{C}$ is the final
output from this block which is further passed to a position-wise feed-forward
layer. Since Fusion must preserve the dimensionality of the input, the number
of input channels to each Conv becomes $d^{\prime}$, however the size of the
output channels depends on the nature of the $\textsc{Fusion}()$ operation. We
explore four different fusion mechanisms, shown in Figure 2, that we can
further group into two categories: Sum-based and Concat-based Fusion.

Sum-based Fusion: In this mechanism, both the input and output channels are of
the same size. The outputs obtained from each convolution are combined using
an element-wise addition operation as shown in Figure 2(a). That is,
$\tilde{Z}_{r}$ in Equation 1 is computed as:
$\tilde{Z}_{r}=V_{1}+V_{2}\ldots+V_{P}$. In our experiments, we refer to this
fusion approach as $\textsc{MultiConv}_{\texttt{sum}}$. We further enhance
this fusion by learning weights that decide the importance of each convolution
for every frame of the input, as shown in Figure 2(b) and defined formally
below:

$\displaystyle\alpha^{s}$
$\displaystyle=\\{\alpha^{s}_{1},\ldots\alpha^{s}_{P}\\}=\texttt{Softmax}(\textsc{FFN}_{d^{\prime}\rightarrow
P}(Z^{s}_{r}))$ $\displaystyle\tilde{Z}^{s}_{r}$
$\displaystyle=\alpha^{s}_{1}\cdot V^{s}_{1}+\alpha^{s}_{2}\cdot
V^{s}_{2}+\ldots+\alpha^{s}_{P}\cdot V^{s}_{P}$ $\displaystyle\tilde{Z}_{r}$
$\displaystyle=[\tilde{Z}^{1}_{r},\tilde{Z}^{2}_{r},\ldots\tilde{Z}^{T}_{r}]$

where $\textsc{FFN}_{a\rightarrow b}$ is a projection layer that projects
$a$-dimensional inputs to $b$-dimensional outputs and $\alpha_{j}\in[0,1]$ is
the importance given by the $s^{th}$ frame $Z^{s}_{r}$ to the output
$V^{s}_{j}$ of the $j^{th}$ kernel. We refer to this fusion mechanism as
$\textsc{MultiConv}_{\texttt{weighted}}$ in our experiments.

Concat-based Fusion: In contrast to sum, the concat-based fusion allocates a
portion of the output to each convolution, causing the number of input and
output channels for these convolutions to be different. This reconstruction
allocates $1/P$ of the total number of features $d^{\prime}$ to each
convolution, resulting in the number of output channels to be $d^{\prime}/P$
as shown in Figure 2(c). This operation is shown below:

$\displaystyle\tilde{Z}^{s}_{r}$
$\displaystyle=\texttt{Concat}(V^{s}_{1},V^{s}_{2}\ldots,V^{s}_{P})$
$\displaystyle\tilde{Z}_{r}$
$\displaystyle=[\tilde{Z}^{1}_{r},\tilde{Z}^{2}_{r},\ldots\tilde{Z}^{T}_{r}]$

where $V^{s}_{j},\tilde{Z}^{s}_{r}\in\mathbb{R}^{d^{\prime}/P}$. In our
experiments, we call this $\textsc{MultiConv}_{\texttt{concat}}$. We further
enhance this fusion by introducing a depthwise convolution after the frame
reconstruction to take neighboring frames into account while combining the
convolution outputs, as shown in Figure 2(d). We refer to this architecture as
$\textsc{MultiConv}_{\texttt{depth}}$ in our experiments.

##  3 Experimental Setup

We conduct experiments on five datasets namely Librispeech-100h (LS-100) [24],
Librispeech-960h (LS-960) [24], Tedlium-2 [25], AISHELL-1 [26] and SLURP [27].
We use ESPnet toolkit [39] to run all our experiments on a combination of
NVIDIA RTX A6000 and NVIDIA Tesla V100 GPUs.333We ensure same GPU and
environment is used while running all the experiments on a particular dataset.
All our models take $80$-dimensional log-Mel features as input that are
extracted with a 25ms window size and 10ms stride. We also use 3-way speed
perturbation with ratios $\\{0.9,1.0,1.1\\}$ and SpecAugment [40]. In all our
experiments, we use the experimental settings recommended in ESPnet recipes.
For all datasets except LS-960 and SLURP, the encoder-decoder architecture
consists of $12$ encoder and $6$ decoder layers with an attention dimension of
$d=256$ and $4$ attention heads. However, for LS-960 and SLURP, we use an $18$
layer encoder with $8$ attention heads and an attention dimension of $d=512$.

##  4 Experimental Results and Analysis

Table 2.1 compares all four variants of our proposed Multi-Convformer
(elaborated in Section 2.1) to Transformer [35] and Conformer [6] models. Our
method significantly outperforms both these approaches across all three
datasets and multiple modelling paradigms; results that are statistically
significant are shown with $\ddagger$. Additionally, we find that among the
four Fusion methods (Figure 2), $\textsc{MultiConv}_{\texttt{sum}}$ and
$\textsc{MultiConv}_{\texttt{depth}}$ perform better. Henceforth, we will only
show results with using the $\textsc{MultiConv}_{\texttt{depth}}$ fusion
strategy.

###  4.1 ASR and SLU Experiments

Table 2: Comparison of our system (WER %) with CgConv and E-Branchformer
(reproduced using ESPnet recipes [39]) on the test splits of the three
datasets.

Method | Librispeech-100h | Tedlium2 | AISHELL
---|---|---|---
Test Clean | Test Other | Test | Test
Attention Encoder Decoder (AED) models
CgConv | 6.36 | 17.18 | 7.44 | 4.55
E-Branchformer [12] | 6.50 | 17.06 | 7.34 | 4.47
black!50 black $\textsc{MultiConv}_{\texttt{depth}}$ | 6.18 | 17.00 | 7.27 | 4.46
Encoder Only (Pure CTC) models
CgConv | 9.66 | 23.79 | 8.78 | 6.33
E-Branchformer [12] | 10.05 | 23.87 | 8.78 | 6.04
black!50 black $\textsc{MultiConv}_{\texttt{depth}}$ | 9.47 | 23.09 | 8.44 | 6.01
RNN Transducer (RNN-T) models
CgConv | 6.95 | 18.18 | 7.72 | 5.24
E-Branchformer [12] | 6.87 | 18.09 | 7.71 | 5.17
black!50 black $\textsc{MultiConv}_{\texttt{depth}}$ | 7.05 | 18.23 | 7.67 | 5.05

Figure 3: Line plot showing the degree of diagonality seen in each encoder
layer's self-attention block. A higher value indicates that the attention
weight matrix is more concentrated along its diagonal [41].

Comparison with Conformer variants. Table 4.1 shows the WER comparison between
our system and two Conformer variants: CgConv (Conformer with convolution
replaced by Convolutional Spatial Gating Unit [15])444This is a stronger
variant of the original CgMLP architecture [15], which is a pure MLP-based
system. and E-Branchformer (Conformer with disentangled attention and
convolution branches) [12, 42]. We note here that
$\textsc{MultiConv}_{\texttt{sum}}$ can be considered as an improved version
of CgConv, as it reduces to CgConv when a single fixed convolution kernel is
employed instead of multiple kernels. Further, we find that the use of a gate
in conjunction with convolution allows the model to selectively utilize
convolution, thereby introducing a natural branching capability. As a result,
our proposed architecture can be viewed as an enhancement to CgConv and a
parameter-efficient variant of Branchformer that achieves comparable or better
performance on speech-related tasks.

In Figure 3, we compare the diagonal properties of self-attention blocks among
Transformer, Conformer, and Multi-Convformer via the diagonality metric [41,
11]. This metric is an indication of the degree to which attention heads focus
on capturing local information rather than global information. We find that
Multi-Convformer allows for more global self-attention blocks, resulting in a
decreased diagonality value when compared to both Transformer and Conformer,
yielding 17% and 3% relative reductions in average diagonality values across
all layers, respectively.

Performance on Librispeech-960h. Table 4.1 compares WERs of our proposed
system with other architectures on the full Librispeech [24] dataset. For
baselines, we reuse the numbers reported by Peng et al. [12]. We evaluate with
and without the use of an external language model (LM) during inference. In
both settings, our model is on par with state-of-the-art architectures
achieving comparable performance when trained with large amounts of data.

SLU experiments. To evaluate the effectiveness of our proposed approach on
tasks other than ASR, in Table 4.1 we evaluate our method on SLU with the
SLURP [27] dataset. Multi-Convformer outperforms both Conformer and
E-Branchformer achieving the best accuracy and F1-score for both intent
classification and entity recognition tasks, while having the least number of
parameters.

Summary of results. In small-scale training data scenarios for ASR
(Librispeech-100h, Tedlium2 and AISHELL shown in Table 2.1) and SLU (SLURP),
Multi-Convformer performs consistently better than Conformer. Moreover, our
proposed system exhibits comparable or improved performance when compared to
other state-of-the-art Conformer variants such as CgMLP and E-Branchformer.
With large scale datasets like Librispeech-960h, we find Multi-Convformer to
be on par with all these architectures.

Figure 4: Heatmap showing the importance given to each convolution kernel
across all encoder layers. A dark blue cell indicates a high level of
importance given to a specific kernel.

Table 3: Comparison of the performance (WER %) of our system against other
architectures on the full Librispeech dataset.

Kernels | Params | Without LM | With LM
---|---|---|---
Test Clean | Test Other | Test Clean | Test Other
Conformer [6] | 147.8M | 2.16 | 4.74 | 1.84 | 3.95
Branchformer [11] | 146.7M | 2.25 | 4.83 | 1.93 | 4.00
E-Branchformer [12] | 148.9M | 2.14 | 4.55 | 1.85 | 3.71
black!50 black $\textsc{MultiConv}_{\texttt{fusion}}$ | 147.4M | 2.15 | 4.69 | 1.89 | 3.92

Table 4: Comparison (accuracy % and F1) of our system against other
architectures on the SLU task.

Method | Params | Intent Classification | Entity Recognition
---|---|---|---
Valid Acc. | Test Acc. | SLU-F1 | Precision | Recall
Conformer [6] | 109M | 87.4 | 86.7 | 77.2 | 80.0 | 74.5
E-Branchformer [12] | 110M | 88.3 | 87.4 | 78.5 | 80.7 | 76.5
black!50 black $\textsc{MultiConv}_{\texttt{fusion}}$ | 108M | 88.8 | 87.4 | 78.9 | 80.8 | 77.1

###  4.2 Analysis of Convolution Kernels

To better understand how the kernels are being utilized, in Figure 4, we
visualize the weights learned by the gate in
$\textsc{MultiConv}_{\texttt{weighted}}$ (shown in Figure 2(b)) on the test-
other split of Librispeech-100h, Tedlium2, and AISHELL datasets. We observe
that not every layer benefits from having multiple convolution kernels. While
the initial few encoder layers rely mostly on the smaller kernels, the
intermediate and final encoder layers reap the most benefits of having
multiple convolution kernels.

Table 5: Comparison of the performance (WER %) of our system with varying
number and size of convolution kernels.

Kernels | Params | Librispeech-100h
---|---|---
Test Clean | Test Other
$K=\\{3,7\\}$ | 36.8M | 6.15 | 17.03
$K=\\{23,31\\}$ | 37.0M | 6.21 | 17.06
$K=\\{7,31\\}$ | 36.9M | 6.36 | 17.19
$K=\\{7,15,23,31\\}$ | 37.2M | 6.18 | 17.00
$K=\\{7,15,31,63\\}$ | 37.4M | 6.38 | 17.18
$K=\\{37,43,49,55\\}$ | 37.8M | 6.22 | 17.13

In Table 5, we evaluate the performance of our system by varying the number
and size of the convolution kernels. We observe that when convolutions with
large kernel sizes (i.e. greater than $32$) are used, performance is
negatively impacted. Performance also diminishes when there is a large gap
between the chosen kernel sizes. Finally, using four kernels instead of two
further improves performance. Thus in all our experiments, we use kernel sizes
$K=\\{7,15,23,31\\}$.

##  5 Conclusion

In this work, we propose Multi-Convformer that utilizes multiple convolution
kernels instead of a single fixed convolution as in Conformers. We demonstrate
the effectiveness of Multi-Convformer by comparing with Conformer and its
variants on multiple datasets (Librispeech-960, Tedlium2, AISHELL and
Librispeech-100), diverse modelling paradigms (AED, CTC, RNN-T) and different
speech tasks (ASR, SLU). We also conduct ablations and analysis for a more
comprehensive understanding of our architecture.

##  6 Acknowledgements

Our computing resources are supported by PSC Bridges2 and NCSA Delta via
ACCESS allocation CIS210014, under National Science Foundation grants
#2138259, #2138286, #2138307, #2137603, and #2138296. Additionally, the third
author would like to gratefully acknowledge support from the National Language
Translation Mission (NLTM): Bhashini project funded by the Ministry of
Electronics and Information Technology (MeitY), Government of India.

##  7 References

## References

  * [1] Jinyu Li  ``Recent Advances in End-to-End Automatic Speech Recognition''  In _APSIPA Transactions on Signal and Information Processing_ 11.1, 2022  DOI: 10.1561/116.00000050
  * [2] Rohit Prabhavalkar et al.  ``End-to-End Speech Recognition: A Survey''  In _IEEE/ACM Transactions on Audio Speech and Language Processing_ 32, 2024, pp. 325–351  DOI: 10.1109/TASLP.2023.3328283
  * [3] Ashish Vaswani et al.  ``Attention is All you Need''  In _Proc. NeurIPS_ 30, 2017
  * [4] Linhao Dong, Shuang Xu and Bo Xu  ``Speech-Transformer: A No-Recurrence Sequence-to-Sequence Model for Speech Recognition''  In _Proc. ICASSP_ , 2018, pp. 5884–5888  DOI: 10.1109/ICASSP.2018.8462506
  * [5] Shigeki Karita et al.  ``A Comparative Study on Transformer vs RNN in Speech Applications''  In _Proc. ASRU_ , 2019, pp. 449–456  DOI: 10.1109/ASRU46091.2019.9003750
  * [6] Anmol Gulati et al.  ``Conformer: Convolution-augmented Transformer for Speech Recognition''  In _Proc. Interspeech_ , 2020, pp. 5036–5040  DOI: 10.21437/Interspeech.2020-3015
  * [7] Pengcheng Guo et al.  ``Recent Developments on Espnet Toolkit Boosted By Conformer''  In _Proc. ICASSP_ , 2021, pp. 5874–5878  DOI: 10.1109/ICASSP39728.2021.9414858
  * [8] Alex Krizhevsky, Ilya Sutskever and Geoffrey E Hinton  ``ImageNet Classification with Deep Convolutional Neural Networks''  In _Proc. NeurIPS_ 25, 2012
  * [9] Vincent Dumoulin and Francesco Visin  ``A guide to convolution arithmetic for deep learning''  In _arXiv preprint arXiv:1603.07285_ , 2016
  * [10] Saad Albawi, Tareq Abed Mohammed and Saad Al-Zawi  ``Understanding of a convolutional neural network''  In _Proc. ICET_ , 2017, pp. 1–6  DOI: 10.1109/ICEngTechnol.2017.8308186
  * [11] Yifan Peng et al.  ``Branchformer: Parallel MLP-Attention Architectures to Capture Local and Global Context for Speech Recognition and Understanding''  In _Proc. ICML_ 162, 2022, pp. 17627–17643
  * [12] Kwangyoun Kim et al.  ``E-Branchformer: Branchformer with Enhanced Merging for Speech Recognition''  In _Proc. SLT_ , 2023, pp. 84–91
  * [13] Zengwei Yao et al.  ``Zipformer: A faster and better encoder for automatic speech recognition''  In _Proc. ICLR_ , 2024  URL: https://openreview.net/forum?id=9WD9KwssyT
  * [14] Guangyong Wei et al.  ``LFEformer: Local Feature Enhancement Using Sliding Window With Deformability for Automatic Speech Recognition''  In _IEEE Signal Processing Letters_ 30, 2023, pp. 180–184  DOI: 10.1109/LSP.2023.3241558
  * [15] Jin Sakuma, Tatsuya Komatsu and Robin Scheibler  ``MLP-ASR: Sequence-length agnostic all-MLP architectures for speech recognition''  In _arXiv preprint arXiv:2202.08456_ , 2022
  * [16] Yinpeng Chen et al.  ``Dynamic Convolution: Attention Over Convolution Kernels''  In _Proc. CVPR_ , 2020, pp. 11027–11036  DOI: 10.1109/CVPR42600.2020.01104
  * [17] Xiyang Dai et al.  ``Dynamic DETR: End-to-End Object Detection With Dynamic Attention''  In _Proc. ICCV_ , 2021, pp. 2988–2997
  * [18] Haoyu Chen, Jinjin Gu and Zhi Zhang  ``Attention in attention network for image super-resolution''  In _arXiv preprint arXiv:2104.09497_ , 2021
  * [19] Yikang Zhang et al.  ``Dynet: Dynamic convolution for accelerating convolutional neural networks''  In _arXiv preprint arXiv:2004.10694_ , 2020
  * [20] Yunsheng Li et al.  ``Revisiting Dynamic Convolution via Matrix Decomposition''  In _Proc. ICLR_ , 2021  URL: https://openreview.net/forum?id=YwpZmcAehZ
  * [21] Zixuan Peng et al.  ``Efficient Speech Emotion Recognition Using Multi-Scale CNN and Attention''  In _Proc. ICASSP_ , 2021, pp. 3020–3024  DOI: 10.1109/ICASSP39728.2021.9414286
  * [22] Joanna Rownicka, Peter Bell and Steve Renals  ``Multi-Scale Octave Convolutions for Robust Speech Recognition''  In _Proc. ICASSP_ , 2020, pp. 7019–7023  DOI: 10.1109/ICASSP40776.2020.9053703
  * [23] Kyu J. Han et al.  ``Multistream CNN for Robust Acoustic Modeling''  In _Proc. ICASSP_ , 2021, pp. 6873–6877  DOI: 10.1109/ICASSP39728.2021.9414639
  * [24] Vassil Panayotov et al.  ``Librispeech: An ASR corpus based on public domain audio books''  In _Proc. ICASSP_ , 2015, pp. 5206–5210  DOI: 10.1109/ICASSP.2015.7178964
  * [25] Anthony Rousseau, Paul Deléglise and Yannick Esteve  ``Enhancing the TED-LIUM corpus with selected data for language modeling and more TED talks.''  In _Proc. LREC_ , 2014, pp. 3935–3939
  * [26] Bu Hui et al.  ``AIShell-1: An Open-Source Mandarin Speech Corpus and A Speech Recognition Baseline''  In _Oriental COCOSDA_ , 2017, pp. 1–5  DOI: 10.1109/ICSDA.2017.8384449
  * [27] Emanuele Bastianelli et al.  ``SLURP: A Spoken Language Understanding Resource Package''  In _Proc. EMNLP_ , 2020, pp. 7252–7262  DOI: 10.18653/v1/2020.emnlp-main.588
  * [28] Suyoun Kim, Takaaki Hori and Shinji Watanabe  ``Joint CTC-attention based end-to-end speech recognition using multi-task learning''  In _Proc. ICASSP_ , 2017, pp. 4835–4839  DOI: 10.1109/ICASSP.2017.7953075
  * [29] Yifan Peng, Kwangyoun Kim and Felix Wu  ``OWSM-CTC: An Open Encoder-Only Speech Foundation Model for Speech Recognition, Translation, and Language Identification''  In _Proc. ACL_ , 2024
  * [30] Alex Graves  ``Sequence Transduction with Recurrent Neural Networks''  In _proc. ICML_ , 2012
  * [31] Alex Graves et al.  ``Connectionist temporal classification: labelling unsegmented sequence data with recurrent neural networks''  In _Proc. ICML_ , 2006, pp. 369–376  DOI: 10.1145/1143844.1143891
  * [32] Jimmy Lei Ba, Jamie Ryan Kiros and Geoffrey E Hinton  ``Layer normalization''  In _arXiv preprint arXiv:1607.06450_ , 2016
  * [33] Sehoon Kim et al.  ``Squeezeformer: An Efficient Transformer for Automatic Speech Recognition''  In _Proc. NeurIPS_ 35, 2022, pp. 9361–9373
  * [34] L. Gillick and S.J. Cox  ``Some statistical issues in the comparison of speech recognition algorithms''  In _Proc. ICASSP_ , 1989, pp. 532–535 vol.1  DOI: 10.1109/ICASSP.1989.266481
  * [35] Linhao Dong, Shuang Xu and Bo Xu  ``Speech-Transformer: A No-Recurrence Sequence-to-Sequence Model for Speech Recognition''  In _Proc. ICASSP_ , 2018, pp. 5884–5888  DOI: 10.1109/ICASSP.2018.8462506
  * [36] Mor Geva et al.  ``Transformer Feed-Forward Layers Are Key-Value Memories''  In _Proc. EMNLP_ , 2021, pp. 5484–5495  DOI: 10.18653/v1/2021.emnlp-main.446
  * [37] Dan Hendrycks and Kevin Gimpel  ``Gaussian Error Linear Units (GELUs)''  In _arXiv preprint arXiv:1606.08415_ , 2016
  * [38] Hanxiao Liu et al.  ``Pay Attention to MLPs''  In _Proc. NeurIPS_ 34, 2021, pp. 9204–9215
  * [39] Shinji Watanabe et al.  ``ESPnet: End-to-End Speech Processing Toolkit''  In _Proc. Interspeech_ , 2018, pp. 2207–2211  DOI: 10.21437/Interspeech.2018-1456
  * [40] Daniel S. Park et al.  ``SpecAugment: A Simple Data Augmentation Method for Automatic Speech Recognition''  In _Proc. Interspeech_ , 2019, pp. 2613–2617  DOI: 10.21437/Interspeech.2019-2680
  * [41] Shucong Zhang et al.  ``On The Usefulness of Self-Attention for Automatic Speech Recognition with Transformers''  In _Proc. SLT_ , 2021, pp. 89–96  DOI: 10.1109/SLT48900.2021.9383521
  * [42] Yifan Peng, Kwangyoun Kim and Felix Wu  ``A Comparative Study on E-Branchformer vs Conformer in Speech Recognition, Translation, and Understanding Tasks''  In _Proc. Interspeech_ , 2023, pp. 2208–2212  DOI: 10.21437/Interspeech.2023-1194


$\boldsymbol{S}$-Motzkin paths with catastrophes and air pockets (very early
version)

Helmut Prodinger1,***Corresponding author<EMAIL_ADDRESS>

1Helmut Prodinger, Department of Mathematical Sciences, Stellenbosch
University, 7602 Stellenbosch, South Africa, and NITheCS (National Institute
for Theoretical and Computational Sciences), South Africa

(Received: Day Month 202X. Received in revised form: Day Month 202X. Accepted:
Day Month 202X. Published online: Day Month 202X.)

###### Abstract

So called $S$-Motzkin paths are combined the concepts ‘catastrophes’ and ‘air
pockets. The enumeration is done by properly set up bivariate generating
functions which can be extended using the kernel method.
Keywords: $S$-Motzkin path; catastrophe; kernel method; air pocket.
2020 Mathematics Subject Classification: 05A15.

## 1 Introduction

Dyck paths consist of up-steps $(1,1)$ and down-steps $(1,-1)$, start at the
origin and do not go below the $x$-axis; they appear in many texts, we just
give one major reference, [12]. Typically, the path returns to the $x$-axis at
the end, but we also consider the scenario of open paths, where the paths end
at level $j$, say. A popular variation of Dyck paths are Motzkin paths; the
difference is just that now a horizontal step $(1,0)$ is also allowed.

In this paper, we concentrate on $S$-Motzkin paths, which is a subfamily of
all Motzkin paths: all three steps (up, level, down) must appear $n$ times,
and, ignoring the down-steps, the sequence is
$(1,0)(1,1)(1,0)(1,1)(1,0)(1,1)\dots(1,0)(1,1)$. The follow figure shows how
these paths are recognized: The two layers enforce that the flat and up steps
are interlaced. Only paths that end in the origin are $S$-Motzkin but we
consider all paths wherever they end.

Here is an example of such an $S$-Motzkin path with 15 steps:

Now we present a graph (automaton) to recognize exactly the $S$-Motzkin paths:

$0$$1$$2$$3$$4$$5$$6$$7$$8$ Figure 1: Graph to recognize $S$-Motzkin paths;
they start and end at the special state (origin).

This subfamily of Motzkin paths originated from a question in a student
competition; see [10] and [7] for history and analysis. In the following we
will combine this family with _catastrophes_ and _air pockets_ , both
originating in papers by Jean-Luc Baril and his team [5], [3]; the older paper
by Banderier and Wallner [2] might be called the standard reference for
lattice paths with catastrophes. The very recent papers [4, 5] contain some
bijective aspects. Our own paper [9] investigates the situation in the context
of skew Dyck paths.

Dyck (and other lattice) paths with catastrophes are characterized by
additional steps (‘catastrophes’) that bring the path back to the $x$-axis in
just one step from any level $j\geq 2$. For $S$-Motzkin paths the definition
is similar, and the graphical description in Figure 2 is easiest to
understand; the catastrophes are drawn in special colors.

In the last section, $S$-Motzkin paths with air pockets will be discussed.
Briefly, down steps of any length are now allowed, but no two down steps may
follow each other.

## 2 $S$-Motzkin paths with catastrophes

$0$$1$$2$$3$$4$$5$$6$$7$$8$ Figure 2: Graph to recognize $S$-Motzkin paths
with catastrophes. Purple arrows lead to the initial state. Olive arrows lead
to the level 0 state in the second layer.

In the sequel, we analyze the paths as in Fig. 2.

We introduce generating functions $f_{i}=f_{i}(z)$, where the coefficient of
$z^{n}$ counts the number of paths starting at the origin (=the big circle)
and ending after $n$ steps at state $i$ (=level $i$) in the upper layer. The
generating functions $g_{i}=g_{i}(z)$, where the coefficient of $z^{n}$ counts
the number of paths starting at the origin (=the big circle) and ending after
$n$ steps at state $i$ (=level $i$) in the lower layer.

The following recursions are easy to see:

$\displaystyle f_{0}$ $\displaystyle=1+z(f_{1}+f_{2}+f_{3}+f_{4}+\cdots),$
$\displaystyle f_{i}$ $\displaystyle=zg_{i-1}+zf_{i+1},\ i\geq 1,$
$\displaystyle g_{0}$
$\displaystyle=zf_{0}+z(g_{1}+g_{2}+g_{3}+g_{4}+\cdots),$ $\displaystyle
g_{i}$ $\displaystyle=zf_{i}+zg_{i+1},\ i\geq 1.$

Since $f_{0}$ and $g_{0}$ are somewhat special, we leave them out for the
moment and compute the other ones, $f_{i}$, $g_{i}$, $i\geq 1$. Eventually we
will solve the equations for $f_{0}$ and $g_{0}$, which will turn out to be
just linear. Therefore we introduce the bivariate generating functions

$F(u)=F(u,z)=\sum_{i\geq 1}u^{i-1}f_{i},\quad G(u)=G(u,z)=\sum_{i\geq
1}u^{i-1}g_{i}$

and we treat $f_{0}$ and $g_{0}$ as parameters. Summing the recursions over
all possible values of $i$,

$F(u)=zg_{0}+zuG(u)+\frac{z}{u}[F(u)-f_{1}],\quad
G(u)=zF(u)+\frac{z}{u}[G(u)-g_{1}].$

Note that $f_{1}=F(0)$ and $g_{1}=G(0)$. We compute

$\displaystyle F(u)$
$\displaystyle=\frac{z(-u^{2}g_{0}+zug_{0}+uf_{1}-zf_{1}+zu^{2}g_{1})}{z^{2}u^{3}-u^{2}+2zu-z^{2}},$
$\displaystyle G(u)$
$\displaystyle=\frac{z(-zu^{2}g_{0}+ug_{1}+zuf_{1}-zg_{1})}{z^{2}u^{3}-u^{2}+2zu-z^{2}}.$

To factor the denominator, we set $u=zv$, and also $z^{3}=x=t(1-t)^{2}$ to get

$z^{2}(vt-1)(v^{2}t^{2}-2tv^{2}+vt+v^{2}-2v+1).$

Therefore the three roots (expressed again in the variable $u$) are given by

$\displaystyle u_{1}=\frac{z}{t},\qquad
u_{2}=-z\frac{t-2+\sqrt{4t-3t^{2}}}{2(1-t)^{2}},\qquad
u_{3}=-z\frac{t-2-\sqrt{4t-3t^{2}}}{2(1-t)^{2}}$

and so

$z^{2}u^{3}-u^{2}+2zu-z^{2}=z^{2}(u-u_{1})(u-u_{2})(u-u_{3}).$

These three roots appear already in [7], were more details are provided.
Therefore

$F(u)=\frac{-u^{2}g_{0}+zug_{0}+uf_{1}-zf_{1}+zu^{2}g_{1}}{z(u-u_{1})(u-u_{2})(u-u_{3})}\quad\text{and}\quad
G(u)=\frac{-zu^{2}g_{0}+ug_{1}+zuf_{1}-zg_{1}}{z(u-u_{1})(u-u_{2})(u-u_{3})}.$

Cancelling the bad factors $(u-u_{2})(u-u_{3})$ out, we get

$F(u)=\frac{-g_{0}+zg_{1}}{z(u-u_{1})}\quad\text{and}\quad
G(u)=\frac{-g_{0}}{(u-u_{1})}.$

As a general remark, factors are bad if $\frac{1}{u-\overline{u}}$ has no
power series expansion around $z=0$, $u=0$. This is part of the kernel method,
see [6] for a user-friendly collection of examples. Plugging in $u=0$, we get

$f_{1}=\frac{g_{0}-zg_{1}}{zu_{1}}\quad\text{and}\quad
g_{1}=\frac{g_{0}}{u_{1}}=\frac{g_{0}t}{z}\quad\text{and thus}\quad
f_{1}=g_{0}\frac{1-\frac{z}{u_{1}}}{zu_{1}}=g_{0}\frac{t(1-t)}{z^{2}}.$

Now we can solve for $f_{0}$ and $g_{0}$:

$\displaystyle f_{0}$
$\displaystyle=1+z(f_{1}+f_{2}+f_{3}+f_{4}+\cdots)=1+zF(1)=1+\frac{-g_{0}+zg_{1}}{1-u_{1}}$
$\displaystyle g_{0}$
$\displaystyle=zf_{0}+z(g_{1}+g_{2}+g_{3}+g_{4}+\cdots)=zf_{0}+\frac{-zg_{0}}{1-u_{1}},$

Therefore

$f_{0}=\frac{-t+z-zt}{-t+z-2zt+zt^{2}}\quad\text{and}\quad
g_{0}=\frac{z(z-t)}{-t+z-2zt+zt^{2}}.$

Using the Lagrange inversion formula (or contour integration), we get the
expansion

$t=\sum_{n\geq 1}\frac{1}{n}\binom{3n-2}{n-1}x^{n}=\sum_{n\geq
1}\frac{1}{n}\binom{3n-2}{n-1}z^{3n}.$ $\displaystyle f_{0}$
$\displaystyle=1+z^{3}+z^{5}+3z^{6}+z^{7}+7z^{8}+13z^{9}+11z^{10}+43z^{11}+70z^{12}+89z^{13}+264z^{14}+424z^{15}+650z^{16}+1657z^{17}+\cdots$
$\displaystyle g_{0}$
$\displaystyle=z+2z^{4}+2z^{6}+7z^{7}+2z^{8}+15z^{9}+32z^{10}+23z^{11}+96z^{12}+174z^{13}+192z^{14}+604z^{15}+1048z^{16}+1434z^{17}+\cdots$

The coefficients are not ‘nice’, in the sense that there are no simple
expressions available for them. Consequently, $f_{k}$ and $g_{k}$ also do not
have nice coefficients, although the factor $\frac{1}{u-u_{1}}$ leads to nice
coefficients, as can be seen from [7].

Now we move to asymptotics.

As can be seen from the discussion in [10], the asymptotic enumeration of
$S$-Motzkin paths is driven by a square-root type singulariy, as it often
happens in the enumeration of trees and lattice paths:

$t\sim\frac{1}{3}-\frac{2}{3\sqrt{3}}\Bigl{(}1-\frac{27x}{4}\Bigr{)}^{1/2},$

and the closest singularity (in $x$) is at $\frac{4}{27}$. Switching to the
$z$-notation, as we have to in the context of catastrophes, we must look at
the three roots closest to origin of modulus
$\bigl{(}\frac{4}{27}\bigr{)}^{1/3}=0.5291336839$. Consequently, the
exponential growth of $S$-Motzkin paths is given by the reciprocal:
$1.88988157485^{n}$. The exponent $n$ refers to the length $n$ of the
$S$-Motzkin path. There are only paths when $n$ is divisible by 3, but that is
of no concern.

For the case of catastrophes, we get a closer singularity. We need the
dominant zero of the denominator $-t+z-2zt+zt^{2}$. A computer provides the
value $\overline{z}=0.5248885986\dots$ and the corresponding value
$\overline{t}=0.2755080409\dots$ . As we can see, the value is slightly
smaller: $0.5248885986<0.5291336839$. Consequently this number leads to a
_simple_ pole, and the exponential growth is larger, as is not too surprising,
considering the additional steps that are possible. The calculations are as
follows:

We must expand $f_{0}$ and $g_{0}$ at the simple pole $z=\overline{z}$. First
note that

$\frac{t}{dz}=\frac{dx}{dz}\frac{dt}{dx}\frac{t}{dt}=3z^{2}\frac{1}{(1-t)(1-3t)}\quad\text{and}\quad\frac{t}{dz}\Big{|}_{z=\overline{z},t=\overline{t}}=\frac{3\overline{z}^{2}}{(1-\overline{t})(1-3\overline{t})}=$
$\displaystyle-t+z-2zt+zt^{2}$
$\displaystyle\sim\frac{d}{dz}(-t+z-2zt+zt^{2})\Big{|}_{z=\overline{z}}(z-\overline{z})=\Big{(}-\frac{t}{dz}+1-2t-2z\frac{t}{dz}+t^{2}+2zt\frac{t}{dz}\Big{)}\Big{|}_{z=\overline{z}}(z-\overline{z})$
$\displaystyle\sim-11.0530836206(z-\overline{z})\sim
21.0579609634(1-1.905166167z),$

and further

$f_{0}=\frac{-t+z-zt}{-t+z-2zt+zt^{2}}\sim
0.0049752931\frac{1}{1-1.905166167z}.$

Since $f_{0}(z)$ is the generating function of $S$-Motzkin paths with
catastrophes, we got an asymptotic equivalent of these numbers of length $n$
via $[z^{n}]f_{0}(z)\sim 0.0049752931(1.905166167)^{n}$.

A similar computation leads to $[z^{n}]g_{0}(z)\sim
0.0062160344(1.905166167)^{n}$. We continue with

$F(u)=\frac{-g_{0}+zg_{1}}{z(u-u_{1})}=\frac{g_{0}(1-t)t}{z^{2}(1-u\frac{t}{z})}$

and therefore

$[u^{k}]F(u)=\frac{(z-t)(1-t)}{-t+z-2zt+zt^{2}}\frac{t^{k+1}}{z^{k+1}}.$

Similarly,

$[u^{k}]G(u)=[u^{k}]\frac{t(z-t)}{-t+z-2zt+zt^{2}}\frac{1}{(1-\frac{ut}{z})}=\frac{t(z-t)}{-t+z-2zt+zt^{2}}\frac{t^{k}}{z^{k}}.$

We note that $G(1)=\frac{zt}{-t+z-2zt+zt^{2}}$. Now we move to partial
$S$-Motzkin paths with arbitrary endpoint. In terms of generating functions,
it just means $u:=1$, and we found the generating function

$\displaystyle f_{0}(z)+F(1,z)+g_{0}(z)+G(1,z)$
$\displaystyle=\frac{1}{-t+z-2zt+zt^{2}}\Big{[}(-t+z-zt)+(1-t)t+z(z-t)+zt\Big{]}$
$\displaystyle=\frac{z+z^{2}-zt-t^{2}}{-t+z-2zt+zt^{2}}$
$\displaystyle=1+z+{z}^{2}+2{z}^{3}+3{z}^{4}+5{z}^{5}+10{z}^{6}+16{z}^{7}+30{z}^{8}+58{z}^{9}+98{z}^{10}+189{z}^{11}+\cdots.$

The asymptotic behaviour of the coefficients is also of the form
$\textsf{const.}(1.905166167)^{n}$.

## 3 Right-to-left S-Motzkin paths with catastrophes

$0$$1$$2$$3$$4$$5$$6$$7$$8$ Figure 3: Graph to recognize $S$-Motzkin paths
with catastrophes from right-to-left.

We use similar generating functions as before, namely $a_{i}(z)$ for the top
layer, and $b_{i}(z)$ for the bottom layer. Then

$\displaystyle a_{0}$ $\displaystyle=1+zb_{0},\quad a_{1}=zb_{1}+za_{0},\quad
a_{i}=zb_{i}+za_{i-1}+za_{0},\ i\geq 2,$ $\displaystyle b_{0}$
$\displaystyle=za_{1},\quad b_{1}=zb_{0}+za_{2},\quad
b_{i}=za_{i+1}+zb_{i-1}+zb_{0},\ i\geq 2.$

As before, we introduce

$A(u)=\sum_{i\geq 1}u^{i-1}a_{i},\quad B(u)=\sum_{i\geq 1}u^{i-1}b_{i}.$

We compute

$\displaystyle A(u)$ $\displaystyle=a_{1}+\sum_{i\geq
2}u^{i-1}a_{i}=a_{1}+z\sum_{i\geq 2}u^{i-1}[b_{i}+a_{i-1}+a_{0}]$
$\displaystyle=a_{1}+z\sum_{i\geq 2}u^{i-1}b_{i}+z\sum_{i\geq
2}u^{i-1}a_{i-1}+z\sum_{i\geq 2}u^{i-1}a_{0}$
$\displaystyle=a_{1}+zB(u)-zb_{1}+zuA(u)+\frac{zu}{1-u}a_{0}$

and

$\displaystyle B(u)$ $\displaystyle=b_{1}+\sum_{i\geq
2}u^{i-1}b_{i}=b_{1}+z\sum_{i\geq 2}u^{i-1}[a_{i+1}+b_{i-1}+b_{0}]$
$\displaystyle=b_{1}+z\sum_{i\geq 2}u^{i-1}a_{i+1}+z\sum_{i\geq
2}u^{i-1}b_{i-1}+z\sum_{i\geq 2}u^{i-1}b_{0}$
$\displaystyle=b_{1}+\frac{z}{u}\sum_{i\geq
0}u^{i}a_{i+1}-\frac{z}{u}a_{1}-za_{2}+zuB(u)+\frac{zu}{1-u}b_{0}$
$\displaystyle=\frac{z}{u}A(u)-\frac{z}{u}a_{1}+zuB(u)+\frac{z}{1-u}b_{0}.$

We rewrite this system in the form

$\displaystyle A(u)$
$\displaystyle=zuA(u)+zB(u)+\Phi(u),\quad\Phi(u)=a_{1}-zb_{1}+\frac{zu}{1-u}a_{0},$
$\displaystyle B(u)$
$\displaystyle=\frac{z}{u}A(u)+zuB(u)+\Psi(u),\quad\Psi(u)=-\frac{z}{u}a_{1}+\frac{z}{1-u}b_{0}.$

The solution is

$A(u)=\frac{z(zub_{0}-zu^{2}a_{0}-za_{1}+zua_{1}+ua_{0})}{(z^{2}u^{3}-2zu^{2}+u-z^{2})(1-u)},\quad
B(u)=\frac{z(-zu^{2}b_{0}-zu^{2}a_{1}+a_{1}u+b_{0}u+zua_{1}+za_{0}-a_{1})}{(z^{2}u^{3}-2zu^{2}+u-z^{2})(1-u)}.$

Recall that if

$\displaystyle u_{1}=\frac{z}{t},\qquad
u_{2}=-z\frac{t-2+\sqrt{4t-3t^{2}}}{2(1-t)^{2}},\qquad
u_{3}=-z\frac{t-2-\sqrt{4t-3t^{2}}}{2(1-t)^{2}};$

then

$z^{2}u^{3}-2zu^{2}+u-z^{2}=z^{2}\Big{(}u-\frac{1}{u_{1}}\Big{)}\Big{(}u-\frac{1}{u_{2}}\Big{)}\Big{(}u-\frac{1}{u_{3}}\Big{)};$

this can be checked directly, compare also [7]. Since
$\frac{1}{u_{1}}=\frac{t}{z}\sim z^{2}$, the factor
$\big{(}u-\frac{1}{u_{1}}\big{)}$ is ‘bad’ and must cancel out. Plugging in
$u=\frac{t}{z}$ into the numerators, we must get 0. Dividing out the factor
$u-\tfrac{t}{z}$, the solutions now look like

$A(u)=\frac{z(zb_{0}+za_{1}-uza_{0}-a_{0}t+a_{0})}{z^{2}\big{(}u-\frac{1}{u_{2}}\big{)}\big{(}u-\frac{1}{u_{3}}\big{)}(1-u)},\quad
B(u)=\frac{z(-zub_{0}+za_{1}-zua_{1}+a_{1}+b_{0}-tb_{0}-ta_{1})}{z^{2}\big{(}u-\frac{1}{u_{2}}\big{)}\big{(}u-\frac{1}{u_{3}}\big{)}(1-u)}.$

Note that

$\Big{(}u-\frac{1}{u_{2}}\Big{)}\Big{(}u-\frac{1}{u_{3}}\Big{)}=u^{2}+\frac{t-2}{z}u+\frac{z}{t}.$

Now we can plug in $u=0$ to get

$A(0)=a_{1}=\frac{z(zb_{0}+za_{1}-a_{0}t+a_{0})}{(1-t)^{2}},\quad\text{and}\quad
a_{1}=\frac{z(zb_{0}+a_{0}-a_{0}t)}{-z^{2}+1-2t+t^{2}}.$

Since $a_{0}=1+zb_{0}$, we get
$a_{1}=\dfrac{z(2zb_{0}+1-t-ztb_{0})}{-z^{2}+1-2t+t^{2}}$. We also get

$B(0)=b_{1}=\frac{z(za_{1}+a_{1}+b_{0}-tb_{0}-ta_{1})}{(1-t)^{2}}.$

From $b_{0}=za_{1}$ we find

$b_{0}=\frac{z^{2}(zb_{0}+a_{0}-a_{0}t)}{-z^{2}+1-2t+t^{2}}=\frac{t(1-t)}{-t+z-2zt+zt^{2}},\quad\text{and}\quad
a_{0}=1+zb_{0}=f_{0}=\frac{-t+z-zt}{-t+z-2zt+zt^{2}}.$

In principle, one could also write formulæ for general $a_{k}$ and $b_{k}$, by
using partial fraction decomposition. Since the results look very complicated
and do not provide extra insight, we refrain from giving such explicit
results.

A brief comment about asymptotics: Since the denominators are the same as in
the left-right instance, we get again an exponential behaviour, with the same
rate as before. The concept of open end does not make sense here since there
are infinitely many such paths of a given length $n\geq 1$.

While one might be tempted to attack the current question using some bijective
tricks, it is worthwhile to note that our approach is very flexible, and, e.
g., subsets of the catastrophes may be considered, with little extra efforts.

## 4 $S$-Motzkin paths and air pockets

Now we move to another model popularized by Baril, namely introducing air
pockets. These are maximal chains of downsteps, but this time only counted as
one step. Since the main issue of $S$-Motzkin paths to keep the pattern flat,
up, flat, up, flat, up, …alive, the downsteps live their own live, and we
managed to construct a graph with 4 layers of states, describing all possible
scenarios.

Figure 4: Four layers of states.

Note that the wavy edges represent transitions without reading a symbol. The
generating functions for the four layers, reaching level $i$, can be read off
from the diagram; note that the wavy edge is labelled by 1, not by $z$, since
there is no step done.

$\displaystyle a_{0}$ $\displaystyle=1,\quad a_{i}=zd_{i-1},\ i\geq 1,\quad
b_{i}=a_{i}+z\sum_{j>i}a_{j},$ $\displaystyle c_{i}$
$\displaystyle=zb_{i},\quad d_{i}=c_{i}+z\sum_{j>i}c_{j}.$

The bivariate generating functions are $A(u)=\sum_{i\geq 0}u^{i}a_{i}$,
$B(u)=\sum_{i\geq 0}u^{i}b_{i}$, etc. Summing the recursions over all values
of $i$, we find the system

$\displaystyle A(u)$ $\displaystyle=1+zuD(u),\quad
B(u)=A(u)+\frac{z}{1-u}[A(1)-A(u)],$ $\displaystyle C(u)$
$\displaystyle=zB(u),\quad D(u)=C(u)+\frac{z}{1-u}[C(1)-C(u)].$

The system can be reduced to two equations

$\displaystyle C(u)$ $\displaystyle=zA(u)+\frac{z^{2}}{1-u}[A(1)-A(u)],$
$\displaystyle\frac{A(u)-1}{u}$
$\displaystyle=zC(u)+\frac{z^{2}}{1-u}[C(1)-C(u)];$

and so, by solving,

$\displaystyle A(u)$
$\displaystyle={\frac{-{z}^{2}uC(1)+{z}^{3}{u}^{2}A(1)-1+2u+{z}^{4}uA(1)-{u}^{2}+{z}^{2}{u}^{2}C(1)-{z}^{3}uA(1)}{-1+2u-{u}^{2}+{z}^{2}u-2{z}^{2}{u}^{2}-2{z}^{3}u+{z}^{2}{u}^{3}+2{z}^{3}{u}^{2}+{z}^{4}u}},$
$\displaystyle C(u)$
$\displaystyle={\frac{\left({z}^{2}{u}^{2}C(1)-{u}^{2}-zu+2u+zA(1)u+{z}^{3}uC(1)-{z}^{2}uC(1)-1+z-zA(1)\right)z}{-1+2u-{u}^{2}+{z}^{2}u-2{z}^{2}{u}^{2}-2{z}^{3}u+{z}^{2}{u}^{3}+2{z}^{3}{u}^{2}+{z}^{4}u}}.$

Plugging in $u=1$ gives the void equations $A(1)=A(1)$ and $C(1)=C(1)$.
Therefore the denominator has to be investigated. We find that
$-1+2u-{u}^{2}+{z}^{2}u-2{z}^{2}{u}^{2}-2{z}^{3}u+{z}^{2}{u}^{3}+2{z}^{3}{u}^{2}+{z}^{4}u=z^{2}(u-\rho)(u-\sigma)(u-\tau)$;
the explicit forms provided by Maple are useless, but fortunately gfun (in
Maple) allows manipulations with the relevant series:

$\displaystyle\rho$
$\displaystyle={z}^{-2}-2z-2{z}^{3}-{z}^{4}-2{z}^{5}-6{z}^{6}-4{z}^{7}-15{z}^{8}-22{z}^{9}-33{z}^{10}-86{z}^{11}-115{z}^{12}-256{z}^{13}-486{z}^{14}-804{z}^{15}-1783{z}^{16}-3074{z}^{17}$
$\displaystyle-6049{z}^{18}-12104{z}^{19}-21902{z}^{20}-44918{z}^{21}-85235{z}^{22}-165124{z}^{23}-331137{z}^{24}-631740{z}^{25}-1261785{z}^{26}-2477694{z}^{27}+\cdots$

The other roots are ugly but we compute the simpler
$(u-\sigma)(u-\tau)=u^{2}+Ku+L$ with

$\displaystyle K$
$\displaystyle=-2{z}^{2}-2{z}^{5}-{z}^{6}-2{z}^{7}-6{z}^{8}-4{z}^{9}-15{z}^{10}-22{z}^{11}-33{z}^{12}-86{z}^{13}-115{z}^{14}-256{z}^{15}-486{z}^{16}+\cdots,$
$\displaystyle L$
$\displaystyle={z}^{2}+2{z}^{5}+2{z}^{7}+5{z}^{8}+2{z}^{9}+14{z}^{10}+16{z}^{11}+27{z}^{12}+74{z}^{13}+86{z}^{14}+222{z}^{15}+395{z}^{16}+\cdots.$

So we must divide this term out from numerator and denominator. Therefore

$A(u)=\frac{z^{3}A(1)+z^{2}C(1)-1}{z^{2}(u-\rho)},\quad\text{and}\quad
C(u)=\frac{z^{2}C(1)-1}{z(u-\rho)},$

and by $u=1$ and solving,

$A(1)=\frac{-1+\rho}{z^{2}(-1+\rho+z)^{2}},\quad\text{and}\quad
C(1)=\frac{1}{z(-1+\rho+z)}.$

Since these values are known, we find

$A(u)=\frac{\rho}{\rho-u}\quad\text{and}\quad
C(u)=\frac{1-\rho}{z(1-\rho-z)(\rho-u)},$

where the identity
$1-2\rho+{\rho}^{2}-{z}^{2}\rho+2{z}^{2}{\rho}^{2}+2{z}^{3}\rho-{z}^{2}{\rho}^{3}-2{z}^{3}{\rho}^{2}-{z}^{4}\rho=0$
was used for simplification. One sees $A(0)=1$, which is clear from
combinatorial reasons. Further

$a_{k}=[u^{k}]A(u)=\rho^{-k}\quad\text{and}\quad
c_{k}=[u^{k}]C(u)=\frac{1-\rho}{z(1-\rho-z)}\rho^{-k-1}.$

The other quantities are then $b_{k}=\frac{1}{z}c_{k}$ and
$d_{k}=\frac{1}{z}a_{k+1}$, for any $k\geq 0$.

We leave the analysis of this air pocket model from right to left, as well as
other parameters, to the interested reader. The factorization
$(u-\rho^{-1})(u-\sigma^{-1})(u-\tau^{-1})$ will play a role here, and only
one factor is bad, namely $(u-\rho^{-1})$.

It is possible to consider catastrophes and air pockets at the same time; we
leave such considerations to enthousiastic young researchers.

## References

  * [1] C. Banderier and P. Flajolet.  Basic analytic combinatorics of directed lattice paths,  Theor. Comput. Sci., 281 (2002), 37–80.
  * [2] C. Banderier and M. Wallner.  Lattice paths with catastrophes,  Discrete Math. Theor. Comput. Sci., 19 (2017), Paper No. 23, 32 pages.
  * [3] J.-L. Baril, S. Kirgizov, R. Maréchal, and V. Vajnovszki, Enumeration of Dyck paths with air pockets, https://arxiv.org/abs/2202.06893
  * [4] J.-L. Baril, S. Kirgizov.  Bijections from Dyck and Motzkin meanders with catastrophes to pattern avoiding Dyck paths,  Discrete Mathematics Letters, 7 (2021), 5–10.
  * [5] J.-L. Baril, J. L. Ramírez, and L. M. Simbaqueba,  Counting prefixes of skew Dyck paths,  J. Integer Seq., 24 (2021), Art. 21.8.2, 15.
  * [6] H. Prodinger.  The Kernel Method: A Collection of Examples,  Séminaire Lotharingien de Combinatoire, B50f (2004), 19 pp.
  * [7] H. Prodinger.  Enumeration of S-Motzkin paths from left to right and from right to left — a kernel method approach,  PU. M. A., Vol. 29 (2020), No.1, pp. 28–38.
  * [8] H. Prodinger, Partial skew Dyck paths—a kernel method approach, Graphs and Combinatorics 38 (2022): 135 (11 pages).
  * [9] H. Prodinger, Skew Dyck paths with catastrophes, Discrete Mathematics Letters, 10 (2022), 9–13, H. Prodinger.
  * [10] H. Prodinger, S. Selkirk, and S. Wagner, On Two Subclasses of Motzkin Paths and Their Relation to Ternary Trees, Algorithmic Combinatorics: Enumerative Combinatorics, Special Functions and Computer Algebra In Honour of Peter Paule on his 60th Birthday, Veronika Pillwein and Carsten Schneider, Editors, 2020, 297–316, Springer-Verlag.
  * [11] N. J. A. Sloane,  The on-line encyclopedia of integer sequences, 2022. Available at https://oeis.org/.
  * [12] R. P. Stanley. Catalan numbers, Cambridge University Press, 2015.