# Smooth Model Predictive Path Integral Control without Smoothing

Taekyung Kim, Gyuhyun Park, Kiho Kwak, Jihwan Bae, and Wonsuk Lee Manuscript
received: February 24, 2022; Revised: June 4, 2022; Accepted: July 14, 2022.
This paper was recommended for publication by Editor H. Kurniawati upon
evaluation of the Associate Editor and Reviewers’ comments. (Corresponding
author: Wonsuk Lee.)Taekyung Kim, Kiho Kwak, Jihwan Bae, and Wonsuk Lee are
with the Ground Technology Research Institute, Agency for Defense Development,
Daejeon 34186, Republic of Korea (e-mail<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>wsblues@add.re.kr).Gyuhyun Park is with the Department of
Mechanical Engineering, Seoul National University, Seoul 08826, Republic of
Korea and also with the Ground Technology Research Institute, Agency for
Defense Development, Daejeon 34186, Republic of Korea (e-mail:
khpark@add.re.kr).Digital Object Identifier (DOI): 10.1109/LRA.2022.3192800

###### Abstract

We present a sampling-based control approach that can generate smooth actions
for general nonlinear systems without external smoothing algorithms. Model
Predictive Path Integral (MPPI) control has been utilized in numerous robotic
applications due to its appealing characteristics to solve non-convex
optimization problems. However, the stochastic nature of sampling-based
methods can cause significant chattering in the resulting commands. Chattering
becomes more prominent in cases where the environment changes rapidly,
possibly even causing the MPPI to diverge. To address this issue, we propose a
method that seamlessly combines MPPI with an input-lifting strategy. In
addition, we introduce a new action cost to smooth control sequence during
trajectory rollouts while preserving the information theoretic interpretation
of MPPI, which was derived from non-affine dynamics. We validate our method in
two nonlinear control tasks with neural network dynamics: a pendulum swing-up
task and a challenging autonomous driving task. The experimental results
demonstrate that our method outperforms the MPPI baselines with additionally
applied smoothing algorithms.

###### Index Terms:

Optimization and optimal control, planning under uncertainty, model learning
for control, autonomous vehicle navigation, field robots.

##  I Introduction

Controlling an autonomous vehicle in complex environments is a challenging
problem. When the vehicle drives on a structured road, it can be modeled as a
linear or a kinematic system that is easy to solve. However, the nature of the
real world dictates non-linearity and this characteristic is highlighted more
at high vehicle speeds and low road surface friction levels. The majority of
autonomous driving research has been focused on normal driving conditions,
while areas of aggressive maneuvering in highly nonlinear environments have
not been fully addressed by prior work.

Figure 1: A simplified representation of the MPPI algorithm during each
optimization iteration. For clarity, we only visualize one sampled trajectory
(in green). (a) Amount of changes between previously computed control sequence
and the next control sequence (along the “i-axis”). (b) Amount of changes in
control values during MPPI rollouts (along the “t-axis”), which are hard to be
minimized by the MPPI baseline.

Gradient-based Model Predictive Control (MPC) methods have been introduced as
powerful solutions for solving the problems of nonlinear control systems [1,
2]. Despite the fact that there have been successful real-world applications
with these methods [3, 4], they still possess the limitation that the cost
function has to be differentiable. Sampling-based Model Predictive Path
Integral (MPPI) control has been proposed to optimize both convex and non-
convex objectives [5] and has benefitted greatly from recent advances in
Graphics Processing Units (GPUs), as a large number of samples can be computed
in parallel to achieve better real-time performance.

While MPPI presents general performances in various situations, it may
encounter chattering when implemented on an actual platform, which is a common
characteristic of sampling-based methods [6]. Rapid changes in action commands
are widely known to burden the actuators and cause the system to become
unstable. Meanwhile, the key property of MPPI for achieving high-level control
performance is to draw samples upon the previously optimized control sequence.
However, this property can instead hinder the entire sequence from converging
quickly to the optimal distribution when the environment changes too rapidly
[7]. Under such circumstances, in particular, chattering becomes more
prominent.

Therefore, a smoothing algorithm is often employed to smooth the control
sequence in practice. However, because the optimization procedure and this
external smoothing mechanism are completely decoupled, the smoothed sequence
may unintentionally lose its optimality. In addition, it may present a
significant problem if the algorithm behaves incorrectly, even if it is tuned
to perform well in most situations. In the worst case, the resulting sequence
may violate the physical constraints or diverge.

In this paper, we propose the Smooth Model Predictive Path Integral (SMPPI)
control method that combines MPPI with an input-lifting strategy to generate
smooth actions without any additional smoothing algorithms. We include
derivative actions as control inputs, in which this technique is commonly used
to smooth jerky commands in control studies [8, 9]. To the best of our
knowledge, we seamlessly apply this idea in the MPPI framework for the first
time while preserving the information theoretic interpretation of optimal
control. Additionally, our method offers a new smoothing mechanism which is
ineligible in the MPPI baseline. The smoothing effects of our approach are
twofold. First, it smooths the gap between the control sequences of previous
and current iterations. We refer to this as smoothing along the “i-axis.”
Second, it smooths the optimized control sequence during trajectory rollouts.
We refer to this as smoothing along the “t-axis.” The amount of changes in the
control values of each axis that can be reduced by our method are depicted in
Fig. 1. Unlike MPPI, where efforts to realize smoothing along both axes would
obstruct its ability to adapt to rapidly changing environments, SMPPI can
achieve both smoothness and agility. We conduct experiments to compare our
method with different smoothing methods in a classical control benchmark. We
also demonstrate our idea in a challenging autonomous driving task. 111Our
video can be found at: https://youtu.be/fyngK8PCoyM

##  II Background

This section provides a brief overview of the MPPI algorithm. The benefit of
the sampling-based method is that it does not require a gradient of the
objective function and the cost function [10]. Recent works including MPPI
have integrated a sampling-based approach with MPC formulations to solve non-
convex optimization problems [5, 6]. They combine information theoretic
control and stochastic optimal control using free energy and the KL divergence
to derive an optimal control distribution with importance sampling [11].

Consider a discrete time dynamic system with a state ${\bf
x}_{t}\in\mathbb{R}^{n}$ and a control input ${\bf v}_{t}\in\mathbb{R}^{m}$.
We applied the general noise assumption that holds that we could not directly
control the system over ${\bf v}_{t}$, but could over the mean ${\bf u}_{t}$
of the density function of noise $\bm{\epsilon}_{t}$:

${\bf v}_{t}\sim\mathcal{N}({\bf u}_{t},\bm{\Sigma}).$

Noise is simply defined as ${\bf v}_{t}={\bf u}_{t}+\bm{\epsilon}_{t}$. Given
a sequence of inputs $V=\\{{\bf v}_{0},{\bf v}_{1},\dots\bf v_{T-1}\\}$ and
mean input variables $U=\\{{\bf u}_{0},{\bf u}_{1},\dots\bf u_{T-1}\\}$ along
a finite time horizon $t\in\\{0,1,\dots T-1\\}$, we can define the probability
density function $q(V)$ as:

$q(V)=\prod_{t=0}^{T-1}Z^{-1}\exp\left(-\frac{1}{2}({\bf v}_{t}-{\bf
u}_{t})^{\mathrm{T}}\bm{\Sigma}^{-1}({\bf v}_{t}-{\bf u}_{t})\right),$ (1)

where $Z=\left((2\pi)^{m}|\bm{\Sigma}|\right)^{\frac{1}{2}}$. Similarly, we
can also define the uncontrolled density function $p(V)$ where $U$ is usually
0:

$p(V)=\prod_{t=0}^{T-1}Z^{-1}\exp\left(-\frac{1}{2}{\bf
v}_{t}^{\mathrm{T}}\bm{\Sigma}^{-1}{\bf v}_{t}\right).$ (2)

These two density functions correspond to the distributions of $\mathbb{Q}$
and $\mathbb{P}$, respectively. Here, we define an optimal density function
using the free energy of the system [11], which corresponds to the optimal
distribution $\mathbb{Q}^{*}$:

$q^{*}(V)=\frac{1}{\eta}\exp\left(-\frac{1}{\lambda}S(V)\right)p(V),$ (3)

where $\eta$ denotes the normalizing constant and $S(V)$ denotes the state-
dependent cost. The input sequence in state cost is iteratively transformed
into state values ${\bf x}$ through the non-affine system dynamics ${\bf F}$
[6]:

$\displaystyle S(V;{\bf F})$ $\displaystyle=\phi({\bf
x}_{T})+\sum_{t=0}^{T-1}c({\bf x}_{t}),$ (4) $\displaystyle{\bf x}_{t+1}$
$\displaystyle={\bf F}({\bf x}_{t},{\bf v}_{t}).$

As proposed in [6], we can now derive the optimal control input by minimizing
the KL divergence between $\mathbb{Q}$ and $\mathbb{Q}^{*}$:

$\mathbb{E}_{{\mathbb{Q}^{*}}}{\left[{\bf v}_{t}\right]}=\int q^{*}(V){\bf
v}_{t}{\mathrm{d}}V.$ (5)

Here, the best solution of (5) is to draw samples directly over
$\mathbb{Q}^{*}$, but this is not possible. Importance sampling is therefore
employed to compute the integral over the known distribution $\mathbb{Q}$:

$\displaystyle\mathbb{E}_{{\mathbb{Q}^{*}}}{\left[{\bf v}_{t}\right]}$
$\displaystyle=\int{w(V)}{q(V)}{\bf v}_{t}{\mathrm{d}}V$
$\displaystyle=\mathbb{E}_{{\mathbb{Q}_{U,\bm{\Sigma}}}}{\left[w(V){\bf
v}_{t}\right]},$ (6)

where the importance weighting term is:

$\displaystyle
w(V)=\left(\frac{q^{*}(V)}{p(V)}\right)\left(\frac{p(V)}{q(V)}\right)$
$\displaystyle=\frac{1}{\eta}\exp\left(-\frac{1}{\lambda}\left(S(V)+\frac{1}{2}\lambda\sum_{t=0}^{T-1}{\bf
u}_{t}^{\mathrm{T}}\bm{\Sigma}^{-1}({\bf
u}_{t}+2\bm{\epsilon}_{t})\right)\right).$ (7)

Let $\mathcal{E}$ be a noise sequence
$\\{\bm{\epsilon}_{0},\bm{\epsilon}_{1},\dots\bm{\epsilon}_{T-1}\\}$ and $K$
be the number of trajectory samples. Finally, we have the iterative optimal
control update law to compute the weights when the sampled trajectory cost
$\\{C(V^{0}),C(V^{1}),\dots C(V^{K-1})\\}$ is given:

$\displaystyle{\bf u}_{t}^{i+1}$ $\displaystyle={\bf
u}_{t}^{i}+\sum_{k=0}^{K-1}w(\mathcal{E}^{k})\bm{\epsilon}_{t}^{k}$ (8)
$\displaystyle w(\mathcal{E}^{k})$
$\displaystyle=\frac{1}{\eta}\exp\left(-\frac{1}{\lambda}\left(C(V^{k})-\beta\right)\right),$
(9)

where we subtract the minimum state cost $\beta$ to ensure that at least one
sample has a numerically non-zero importance sampling weight. The trajectory
cost in (9) is then simplified as follows:

$C(V^{k})=S(V^{k})+\lambda\sum_{t=0}^{T-1}{\bf
u}_{t}^{\mathrm{T}}\bm{\Sigma}^{-1}\bm{\epsilon}_{t}^{k}.$ (10)

##  III Smooth Model Predictive Path Integral Control

###  III-A Limitations of External Smoothing Algorithms

The sampling-based approach of the MPPI algorithm makes possible the
consideration of involving non-convex objectives in optimization problems.
However, the stochastic nature of this method can cause significant chattering
in the resulting commands. Due to the unique property by which perturbed
trajectories are sampled around the previously optimized mean control sequence
$U$, MPPI cannot respond effectively when the optimal control distribution
greatly deviates from the previous iteration. Undesirable chattering effects
stand out more in the scenarios mentioned above.

A common approach to mitigate such a problem is to smooth the resulting
control sequence using, for instance, sliding window smoothing methods or
filtering based methods [12, 13]. It was suggested that a Savitzky-Golay
filter (SGF) [14] would be an effective solution for this control method [6].
It smooths the subsets of adjacent data by fitting the local polynomial
approximations in a convolutional manner.

However, this type of approach can have negative effects, as external
manipulations of control values are not considered in the optimization
process. Consider a general state-action system dynamics with clamping
function ${\bf g}_{{\bf u}}$ for handling control constraints:

${\bf x}_{t+1}={\bf F}\left({\bf x}_{t},{\bf g}_{{\bf u}}({\bf
v}_{t})\right).$ (11)

Because the perturbed control ${\bf v}_{t}$ is bounded by the physical limits
of the actuators, the sampled noise should be bounded as follows:

$\bar{\bm{\epsilon}}_{t}={\bf g}_{{\bf u}}({\bf v}_{t})-{\bf u}_{t}.$ (12)

Two possible ways exist to apply the SGF in the control sequence.

####  III-A1 Smoothing weighted noise sequence

First, we can apply smoothing to the weighted noise sequence:

${\bf u}_{t}^{i+1}={\bf
u}_{t}^{i}+\operatorname{SGF}\left(\sum_{k=0}^{K-1}w(\bar{\mathcal{E}}^{k})\bar{\bm{\epsilon}}_{t}^{k}\right).$
(13)

This makes data points smoother while compensating for the noise, which
changes considerably along the time horizon. During this procedure, the
control variable ${\bf u}$ may violate the constraint conditions given that
the bounded noises are manipulated by the filter. On the other hand, the
nature of this process makes it vulnerable to phase distortion [15]. In
addition to violating the given constraints, the control sequence will diverge
if the noises are overlapped repeatedly and amplified over time. We describe
this phenomenon further in Section V-D.

####  III-A2 Smoothing control sequence

Second, we can apply the SGF after the control sequence is updated using the
weighted noise:

${\bf u}_{t}^{i+1}=\operatorname{SGF}\left({\bf
u}_{t}^{i}+\sum_{k=0}^{K-1}w(\bar{\mathcal{E}}^{k})\bar{\bm{\epsilon}}_{t}^{k}\right).$
(14)

Although this method guarantees that the control variables are meeting the
bounded condition, it can cause a delay in the system response. It is common
to provide history values as they are required in the convolution-based
smoothing method. The early values in the control sequence are then affected
by the history, which means that polynomial approximation hinders the
controlled distribution from rapidly shifting to an optimal distribution [16].
Note that the first control action is the key value in the MPC problem.

###  III-B Decoupling Control Space and Action Space

In the original MPPI, the running control cost in (10) only plays a role in
reducing the distance between control values of the current and previous
iterations [17]. Chattering innately occurs because the control trajectory is
sampled randomly, and the variance along the “t-axis” in the new control
trajectory is not taken into account during optimization. To this end, it is
possible to impose an additional cost in terms of the variation of the input,
i.e., chattering on the “t-axis.” [18] suggested an additional running cost
for variation of the inputs, but it cannot be applied generally, as it assumes
that the dynamics are affine in control under special conditions. We intend to
expand the MPPI baseline [6], which is likely to be adopted more extensively,
but arbitrary modifications for the additional cost associated with input
sequences violate the theoretical derivation of MPPI as the control cost is
determined inherently through the importance sampling scheme.

In order to handle such an issue while preserving the MPPI framework,
therefore, we suggest the lifting of the control variables as derivative
actions. This strategy can mitigate the chattering problem in terms of two
points of view.

####  III-B1 Smoothing along the “i-axis”

Henceforth, let us decouple the control space and action space by defining
action sequence $A=\\{{\bf a}_{0},{\bf a}_{1},\dots\bf a_{T-1}\\}$. Noisy
sampling is performed on a higher order control space $U$. Then, the resulting
control sequence is integrated to become a smoother action sequence. The
control distribution is hereby distinguished from the MPPI baseline. The
variance of the injected noise is adjusted according to the physical limit of
the input rate of change. This in turn reduces the variation along the
“i-axis” and consequently mitigates damage to the actuator.

Note that one can attempt to smooth resulting actions in the MPPI framework by
reducing the variance in the same manner as described above. In this setting,
however, MPPI would be unable to respond to rapidly changing environments. On
the other hand, increasing the variance to cover a wider action range would
not only be physically implausible but would also eventually result in
chattering. The method proposed here is free from this trade-off, as its new
search space $U$ can be handled adaptively depending on the environment.

####  III-B2 Smoothing along the “t-axis”

In contrast to MPPI, our control distribution corresponds to derivative
action, allowing action variables to be treated as augmented state elements
and hence making them independent of the control cost. Variation of action can
now be easily included in the state cost such that chattering with regard to
the “t-axis” can be minimized. Here, we introduce an extra action cost
$\Omega$ to smooth the action sequence along the “t-axis” by minimizing the
variance of $A$ without violating the information theoretic interpretation of
MPPI:

$\Omega(A)=\sum_{t=1}^{T-1}({\bf a}_{t}-{\bf
a}_{t-1})^{{\mathrm{T}}}{\bm{\omega}}\,({\bf a}_{t}-{\bf a}_{t-1}),$ (15)

where $\bm{\omega}$ is the weighting parameter in the form of a diagonal
matrix.

Finally, we obtain the following action sequence update law:

$\displaystyle{\bf u}_{t}^{i+1}$ $\displaystyle={\bf
u}_{t}^{i}+\sum_{k=0}^{K-1}w(\mathcal{E}^{k})\bm{\epsilon}_{t}^{k},$ (16)
$\displaystyle{\bf a}_{t}^{i+1}$ $\displaystyle={\bf a}_{t}^{i}+{\bf
u}_{t}^{i+1}{\Delta{t}},$ (17)

and the trajectory cost (10) now takes the form:

$C(V^{k},A)=S(V^{k})+\Omega(A+V^{k}{\Delta{t}})+\lambda\sum_{t=0}^{T-1}{\bf
u}_{t}^{\mathrm{T}}\bm{\Sigma}^{-1}\bm{\epsilon}_{t}^{k}.$ (18)

Afterwards, we apply clamping function ${\bf g}_{{\bf a}}$ to the action
commands to impose box constraints on the vehicle’s physical limits. The
overall algorithm of SMPPI is shown in Alg. 1.

Given : ${\bf F}$: Dynamics model;

$K,T$: Number of samples, timesteps;

$({\bf u}_{0},{\bf u}_{1},...\,{\bf u}_{T-1})$: Initial control sequence;

$({\bf a}_{0},{\bf a}_{1},...\,{\bf a}_{T-1})$: Initial action sequence;

$\bm{\Sigma},\lambda,\phi,c,\Omega$: Control parameters and cost functions;

for  _$i\leftarrow 0$ to maximum iterations_ do

${\bf x}_{0}\leftarrow\text{SubscribeState()}$;

for  _$k\leftarrow 0$ to $K-1$_ do

${\bf x}\leftarrow{\bf x}_{0}$;

Sample
$\mathcal{E}^{k}=\left(\bm{\epsilon}_{0}^{k}\dots\bm{\epsilon}_{T-1}^{k}\right),~{}\bm{\epsilon}_{t}^{k}\in\mathcal{N}(0,\bm{\Sigma})$;

for  _$t\leftarrow 0$ to $T-1$_ do

${\bf v}_{t}^{k}={\bf u}_{t}+\bm{\epsilon}_{t}^{k}$;

${\bf a}_{t}^{k}={\bf a}_{t}+{\bf v}_{t}^{k}\Delta{t}$;

${\bf x}\leftarrow{\bf F}({\bf x},\,{\bf a}_{t}^{k})$;

$C_{k}\mathrel{+}=c({\bf x})+\lambda{\bf
u}_{t}^{\mathrm{T}}\bm{\Sigma}^{-1}\bm{\epsilon}_{t}^{k}$;

$C_{k}\mathrel{+}=\phi({\bf x})+\Omega({\bf a}_{0}^{k},{\bf
a}_{1}^{k},\,\dots\,{\bf a}_{T-1}^{k})$;

$w_{k}\leftarrow\text{ComputeWeights}(C_{0},C_{1},\dots C_{k-1})$;

for  _$t\leftarrow 0$ to $T-1$_ do

$U^{i+1}\leftarrow
U^{i}+\left(\sum_{k=0}^{K-1}w_{k}^{{\mathrm{T}}}\,\mathcal{E}^{k}\right)$;

$A^{i+1}\leftarrow A^{i}+U^{i+1}{\Delta{t}}$;

$\text{SendToController}({\bf a}_{0})$;

for  _$t\leftarrow 1$ to $T-1$_ do

${\bf u}_{t-1},\,{\bf a}_{t-1}\leftarrow{\bf u}_{t},\,{\bf a}_{t}$;

${\bf u}_{T-1},\,{\bf a}_{T-1}\leftarrow\text{Initialize}({\bf u}_{T-1},{\bf
a}_{T-1})$;

Algorithm 1 SMPPI

##  IV Experiments on an Inverted Pendulum

Figure 2: Average state costs during optimization procedures with different
control methods. Each iteration consists of $20$ time steps. Note that we
apply logarithmic scaling to the y-axis and that the costs are clamped to a
minimum of $0.01$.

We tested MPPI and SMPPI in a simulated inverted pendulum swing-up task. One
of the important characteristics of the pendulum swing-up task is that the
available torque is insufficient to push the pendulum to reach an upright
position in a single rotation. The controller should swing the pendulum
multiple times to gather energy, and during this process, the optimal control
sequence changes rapidly. Consequently, it is a simple yet effective benchmark
for evaluating our method. To exploit the fact that our idea is generalized to
allow non-affine dynamics, we used a neural network to learn the dynamics
model in this experiment.

We designed the dynamics model with two fully-connected hidden layers, each
with 32 neurons. The state-action dataset was repeatedly collected during the
control procedure and the model was trained with the dataset every 50 time
steps. No bootstrap dataset was used because the dimensionality of the
inverted pendulum system is sufficiently low. The running state cost function
$c({\bf x})$ in (4) is formulated as follows:

$c({\bf
x}\equiv[\theta,\dot{\theta}]^{\mathrm{T}})=\theta^{2}+0.1{\dot{\theta}^{2}}.$
(19)

We compared five different methods: i) the original MPPI without smoothing
(abbreviated as “MPPI baseline”), ii) applying an additional action cost for
smoothing on MPPI, iii) applying the SGF on the noise sequence (abbreviated as
“MPPI ($\operatorname{SGF}(\bm{\epsilon})$)”), iv) applying the SGF on the
control sequence (abbreviated as “MPPI ($\operatorname{SGF}(U)$)”), and v)
SMPPI. In this task, control parameter $\lambda$ was set to 10. For SMPPI, the
action sequence cost parameter $\bm{\omega}$ was set to 1. They were tested
with seven different initial angular velocities
($\dot{\theta}\in\\{-3,-2,\dots 3\\}$) starting from the initial position
vertically downward. We fixed the random seed for a fair comparison. The state
costs (19) during online optimization are shown in Fig. 2.

The results show that only SMPPI successfully stabilized the pendulum in the
upright position in all cases. As seen in our video, the other methods showed
similar results. They continually failed to push the pendulum to the upright
position because they did not apply enough torque during the swinging motions.
In the case of MPPI baseline i), it was vulnerable to chattering and could not
converge into an optimal control sequence when the optimal distribution
changed rapidly. Imposing an additional action cost ii), which was employed to
alleviate chattering, also failed because this strategy violates the
information theoretic interpretation of MPPI while using non-affine dynamics.
Methods using external smoothing algorithms iii)$-$iv) failed due to the
negative effects of external smoothing. We discuss these issues further in
Section V-D.

##  V Experiments on a Vehicle Simulator

###  V-A Experimental Setup

Our research goal is to perform high-speed driving successfully under
challenging conditions, including those with unknown friction surfaces and
sharp corners. The performance of the model-based control policy is highly
dependent on the accuracy of the model [19, 20]. The vehicle model should be
trained with all possible maneuvers to minimize any model bias. Because the
control sequence update is processed by evaluating the perturbed control
trajectories with sampling, situations in which control values change
significantly over time that make the vehicle unstable should be included in
the training dataset. Obtaining such data from an actual vehicle would be
dangerous. Therefore, we used CarMaker to collect driving data and to evaluate
the control performances. This is a widely used, high-fidelity vehicle
simulator that precisely solves nonlinear dynamics in real time.

We built a race track modeled after an actual kart circuit known as “KART
2000” in Kirchlengern, Germany (see Fig. 3). The length of the track was
$1016$ m and it had two moderate curves and four sharp curves. Note that when
the vehicle reaches the entry of sharp corners, the controller should reduce
the vehicle’s speed and apply a large steering angle quickly. Otherwise, the
vehicle will understeer and collide with the track boundary.

Figure 3: Trajectory of our proposed method with a reference speed of $60$
km/h.

In some prior research on autonomous driving on race tracks, electric vehicles
without transmissions were used [6, 4, 8]. Unlike these vehicles, the majority
of current vehicles use an automatic transmission to shift gears. The dynamic
characteristics of the vehicle will definitely change as a gear shifts.
Therefore, throttle control is not feasible for use in common vehicles. Here,
we simply overcome this issue by taking desired speed ($v_{des}$) as the
feedforward command of MPPI. A low-level feedback controller then manages the
throttle and brake via a Proportional-Integral (PI) loop. A Volvo XC90 was
used as the control vehicle.

###  V-B Training the Neural Network Vehicle Model

There are two main characteristics that make the vehicle dynamics challenging
to model: First, vehicle motions under unknown friction are difficult to
predict. In particular, the lateral tire forces will slip into the nonlinear
region on low friction corners [21]. Second, the automatic gear shifting
mechanism is highly complex to model explicitly. We propose to model such
complex and nonlinear dynamics using a neural network with state-action
history, which enables the network to capture time-varying behavior [22]. The
overall structure of our vehicle model, which is a feedforward fully-connected
neural network, is shown in Table I. The terms $\left|{\bf x}\right|$ and
$\left|{\bf a}\right|$ denote correspondingly the size of the state and the
action space, and $h$ represents the number of state-action pairs in the
previous history. A Rectified Linear Unit (ReLU) is used for the activation of
hidden layers. The Mean Squared Error (MSE) loss was used as the loss function
and the Adam optimization was used for mini-batch gradient descent.

TABLE I: Overall architecture of the vehicle model | Size | Activation
---|---|---
Input | $(\left|{\bf x}\right|+\left|{\bf a}\right|)\times h$ | -
Hidden Layer 1 |  $2\times$Input Size | ReLU
Hidden Layer 2 |  $4\times$Input Size | ReLU
Hidden Layer 3 |  $6\times$Input Size | ReLU
Hidden Layer 4 |  $2\times$Input Size | Linear
Output | $\left|{\bf x}\right|$ | -

We collected a human-controlled driving dataset in a manner similar to that
utilized in our prior work on the training of a dynamics model [23]. The
vehicle state is defined as ${\bf x}=[v_{x},v_{y},r]^{\mathrm{T}}$, where
$v_{x}$ and $v_{y}$ are the longitudinal and lateral velocities, and $r$ is
the yaw rate. The action command is defined as ${\bf
a}=[\delta,v_{des}]^{\mathrm{T}}$, where $\delta$ is the steering angle
command. We carefully selected three distinct maneuvers:

  1. i)

Zig-zag driving at low speeds ($20-25$ km/h) on the race track.

  2. ii)

High-speed driving on the race track while trying to maintain a speed of $40$
km/h as much as possible.

  3. iii)

Sliding maneuvers during combinations of acceleration and deceleration with
small, medium, and large steering angles. Subsequently, we controlled the
vehicle with rapidly changing commands for random movements, representing the
sampled noisy trajectories of MPPI. These maneuvers were performed on flat
ground in both the left and right directions.

Each maneuver was done with multiple road friction coefficients
$\mu\in\\{0.4,0.5,\dots 1.0\\}$. The maneuvers on the race track were done in
both clockwise and counter-clockwise directions. Each one was logged for two
minutes. We collected a total of 35 maneuvers, which amounted to 70 minutes of
driving. The dataset was split into two portions: 70$\%$ for training and
30$\%$ for testing. To evaluate the generalization performance of the trained
model, the validation dataset was collected on the same race track while the
friction coefficients were modified. From Corner #1 to Corner #6 (depicted in
Fig. 3), the friction coefficients were assigned with values that were not
included in the training dataset: $[0.95,0.85,0.75,0.65,0.55,0.45]$,
respectively. The other regions were assigned values of $\mu=0.8$.

The test and validation errors after training are shown in Table II. The
results show that our trained model can precisely represent the vehicle system
dynamics regardless of the road friction. The estimation results on the
validation data are visualized in Fig. 4. The Root Mean Square Error (RMSE) is
denoted as $\mathbf{E}_{RMS}$ and the max error is denoted as
$\mathbf{E}_{max}$.

TABLE II: Training results of the neural network vehicle model. |  $v_{x}$ [m/s] |  $v_{y}$ [m/s] |  $r$ [rad/s]
---|---|---|---
| $\mathbf{E}_{RMS}$ | $\mathbf{E}_{max}$ | $\mathbf{E}_{RMS}$ | $\mathbf{E}_{max}$ | $\mathbf{E}_{RMS}$ | $\mathbf{E}_{max}$
Test | 0.0311 | 0.5530 | 0.0216 | 0.4723 | 0.0175 | 0.2506
Val. | 0.0252 | 0.3744 | 0.0136 | 0.1500 | 0.0123 | 0.1400
Figure 4: Estimation results on the validation dataset.

###  V-C Cost Function and Other Parameters

Following prior work [6], we designed a state-dependent cost function $c({\bf
x})$, which consisted of three components:

$c({\bf x})=\alpha_{1}{\text{Track}({\bf x})}+\alpha_{2}{\text{Speed}({\bf
x})}+\alpha_{3}{\text{Slip}({\bf x})}.$ (20)

The track cost indicates whether the vehicle is inside the track or outside of
the given boundary. The states of the sampled trajectories are transformed
into global positions $(p_{x},p_{y})$ and they lookup the values of a two-
dimensional cost map M, which represents the area of the outer boundary as 1
and the area of the inner boundary as 0. Our sampling-based controller allows
this impulse-like cost function:

$\text{Track}({\bf x})=(0.9)^{t}\,{10000\textbf{M}(p_{x},p_{y})}.$ (21)

The speed cost is the quadratic cost to achieve the reference vehicle speed:

$\text{Speed}({\bf x})=(v_{x}-v_{ref})^{2}.$ (22)

The slip cost penalizes the sideslip angle to plan a stable future trajectory.
Additionally, it imposes a hard cost to reject samples which are estimated to
have a larger sideslip angle than $0.2$ rad (approximately 11.46∘) in the
future:

$\displaystyle\text{Slip}({\bf x})$
$\displaystyle=\sigma^{2}+10000I\left(\\{\left|\sigma\right|>0.2\\}\right)$
(23) $\displaystyle\sigma$
$\displaystyle=-\text{arctan}\left(\frac{v_{y}}{\lVert v_{x}\rVert}\right),$

where $I$ is an indicator function.

We conducted a grid search for each controller to identify the best control
parameters exhibiting the most successful performance. The sampling variance
was adjusted to cover most of the control range of each controller. MPPI used
$\bm{\Sigma}=\text{Diag}(4.0,3.0)$ for the action noise and SMPPI used
$\bm{\Sigma}=\text{Diag}(0.7,0.4)$ for the derivative action noise. The
feedforward control frequency was $10$ Hz and the controllers used a time
horizon of $4$ s. The control parameters $K$ and $\lambda$ were
correspondingly set to 10000 and 15.0 during the experiments. For SMPPI, it
used $\bm{\omega}=\text{Diag}(0.8,0.8)$.

###  V-D Experimental Results

We conducted an ablation study for our framework. The track used in these
experiments is identical to that used to collect the validation data. We
measured the average lap time taken by the vehicle to traverse each corner
during five laps around the track, where the reference speed was set to $40$
km/h. If the vehicle went outside a boundary, it was placed at the start point
and had to start a new lap. The same pre-trained vehicle model was used and
there was no extra training during experiments. The results are shown in Table
III.

TABLE III: Average lap times (in [s]) on six corners with different control methods. For SMPPI with $\Omega$, the minimum speed (in [km/h]) and the maximum slip angle (in [∘]) while passing through each corner are also analyzed below. Lap time [s] | #1 | #2 | #3 | #4 | #5 | #6
---|---|---|---|---|---|---
Original MPPI | 11.08 | 9.60 | N/A | N/A | N/A | N/A
MPPI ($\operatorname{SGF}(\bm{\epsilon})$) | 11.75 | 9.90 | N/A | N/A | N/A | N/A
MPPI ($\operatorname{SGF}(U)$) | 7.82 | N/A | N/A | N/A | N/A | N/A
SMPPI w/o $\Omega$ | 8.39 | 7.71 | 11.64 | 8.77 | 9.86 | 13.11
SMPPI w/ $\Omega$ | 7.36 | 7.66 | 10.83 | 8.47 | 9.39 | 12.86
Min. Speed [km/h] | 24.71 | 20.37 | 23.30 | 36.51 | 28.24 | 29.77
Max. Slip [∘] | 5.34 | 11.09 | 9.64 | 2.91 | 5.32 | 4.94

While all methods showed promising results on straight roads and on Corner #1,
MPPI with different control update laws (8), (13), (14) failed to complete
Corner #2 and Corner #3, which are the sharpest corners of the track. The
vehicles collided with the boundary or lost control after entering these
turns. In contrast, both of the proposed methods successfully controlled the
vehicle to traverse all of the laps at high speeds. One notable finding is
that SMPPI with the additional action cost $\Omega$ showed faster lap times in
all corners than SMPPI without an action cost. This suggests that reducing
chattering along the “t-axis” can improve the control performance on the MPPI
structure. Clearly, reducing the unnecessary noise in the steering and
throttle commands is strongly related to increasing the speed of the vehicle.
The trajectories taken by the three controllers are shown in Fig. 5.

Figure 5: Visualization of trajectories of the compared controllers. The
friction coefficient of corner #2 (in gray) is 0.85 and that of corner #3 (in
brown) is 0.75.

Finally, we examined in more detail the actual optimization procedure of each
method to verify our idea. The sequences computed by the four controllers
right after taking Corner #2 are visualized in Fig. 6. While passing through
this sharp corner, the neural network was able to estimate that the vehicle
would slide off the track if it did not slow down due to the friction limits.
Therefore, the controller was required to apply the brakes and a large
positive steering angle to make an appropriate right turn. During this
procedure, the gap between the optimal and the current control sequence
increased in an instant. The control sequence in the MPPI baseline attempted
to respond to the rapidly changing optimal distribution. However, chattering
occurred (see Fig. 6a) and caused the vehicle to lose its stability (see Fig.
5). This is because perturbed samples incorporating high-frequency noise
survived after importance sampling, to minimize the impulse-like state cost
despite the chattering. In the case of “MPPI
($\operatorname{SGF}(\bm{\epsilon})$)”, the external smoothing filter
distorted the phase of the weighted noise. The noise sequence then escalated
the chattering into the control sequence and finally led to divergence (see
Fig. 6b). On the other hand, smoothing was suitably applied in “MPPI
($\operatorname{SGF}(U)$)”, but this rather hindered the controller from
quickly generating the correct command (see Fig. 6c). This behavior is also
well illustrated in Fig. 5. In contrast, SMPPI successfully responded to the
environment and generated a smooth action sequence without the need for an
additional smoothing filter. The derivative action sequence still possessed
inevitable chattering, but it was integrated to become a smoother action
sequence. The actual commands applied to the vehicle were also shown to be
stable (along the “i-axis”), an achievement realized due to the strong
benefits of SMPPI.

Figure 6: The first 10 steps of the weighted sum of noise sequences (in green)
and action sequences (in red) from different controllers right after entering
Corner #2 ($t=i=0$ at this instant). For clarity, only the steering angle
commands are visualized. The results after applying the SGF filter are shown
in blue. For SMPPI, the augmented action sequence is shown in purple. The
actual steering commands applied to the vehicle for 25 steps ($2.5$ s) are
shown on the right-hand side (in black).

##  VI Conclusion

We presented the Smooth Model Predictive Path Integral algorithm, which is
designed to generate smooth control commands within the MPPI algorithm. Our
method can attenuate chattering, which is a natural problem of sampling-based
algorithms, without the need to design external smoothing filters. In
particular, our method outperforms the MPPI baseline in cases in which the
environment changes rapidly. In addition, our proposed method is not confined
to employing action smoothing cost, as the control domain is shifted to the
derivative action distribution. We showed that SMPPI can improve the general
performance when it is applied to autonomous driving tasks. SMPPI was
demonstrated to be capable of controlling an autonomous vehicle with agility
on sharp and slippery corners. Furthermore, this chattering-free controller is
also beneficial in reducing damage to the actuators.

## APPENDIX

We also demonstrated our method on a more aggressive driving task. The
reference speed was set to $60$ km/h. We collected an extra training dataset
of high-speed maneuvers on the race track, following the strategy described in
Section V. Then, we trained the vehicle model with the augmented dataset.
Finally, the SMPPI controller was deployed on the validation race track. From
Corner #1 to Corner #6 (depicted in Fig. 3), the friction coefficients were
assigned the following corresponding values: $[1.0,0.95,0.9,0.85,0.8,0.75]$.
The other regions were set such that $\mu=0.9$. All five laps were completed
at high speeds on challenging roads with varying amounts of friction. The
trajectory taken by the vehicle is visualized in Fig. 3. We were able to
observe the controller taking “out-in-out” trajectories on sharp corners
because this is the best way to preserve high speeds and prevent large slip
angles according to the predictions of the neural network model. We encourage
readers to watch our supplementary video, where all of our experiments are
shown in detail.

## References

  * [1] W. Li and E. Todorov, “Iterative linear quadratic regulator design for nonlinear biological movement systems.” in _ICINCO_. Citeseer, 2004, pp. 222–229.
  * [2] Y. Tassa, N. Mansard, and E. Todorov, “Control-limited differential dynamic programming,” in _IEEE International Conference on Robotics and Automation (ICRA)_. IEEE, 2014, pp. 1168–1175.
  * [3] U. Rosolia and F. Borrelli, “Learning how to autonomously race a car: A predictive control approach,” _IEEE Transactions on Control Systems Technology_ , vol. 28, no. 6, pp. 2713–2719, 2020.
  * [4] J. Kabzan, M. I. Valls, V. J. Reijgwart, H. F. Hendrikx, C. Ehmke, M. Prajapat, A. Bühler, N. Gosala, M. Gupta, R. Sivanesan _et al._ , “Amz driverless: The full autonomous racing system,” _Journal of Field Robotics_ , vol. 37, no. 7, pp. 1267–1294, 2020.
  * [5] G. Williams, N. Wagener, B. Goldfain, P. Drews, J. M. Rehg, B. Boots, and E. A. Theodorou, “Information theoretic mpc for model-based reinforcement learning,” in _IEEE International Conference on Robotics and Automation (ICRA)_. IEEE, 2017, pp. 1714–1721.
  * [6] G. Williams, P. Drews, B. Goldfain, J. M. Rehg, and E. A. Theodorou, “Information-theoretic model predictive control: Theory and applications to autonomous driving,” _IEEE Transactions on Robotics_ , vol. 34, no. 6, pp. 1603–1622, 2018.
  * [7] J. Yin, Z. Zhang, E. Theodorou, and P. Tsiotras, “Trajectory Distribution Control for Model Predictive Path Integral Control using Covariance Steering,” in _IEEE International Conference on Robotics and Automation (ICRA)_ , 2022.
  * [8] J. L. Vázquez, M. Brühlmeier, A. Liniger, A. Rupenyan, and J. Lygeros, “Optimization-based hierarchical motion planning for autonomous racing,” in _IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)_. IEEE, 2020, pp. 2397–2403.
  * [9] E. Chisari, A. Liniger, A. Rupenyan, L. Van Gool, and J. Lygeros, “Learning from simulation, racing in reality,” in _IEEE International Conference on Robotics and Automation (ICRA)_. IEEE, 2021, pp. 8046–8052.
  * [10] M. Kobilarov, “Cross-entropy motion planning,” _The International Journal of Robotics Research_ , vol. 31, no. 7, pp. 855–871, 2012.
  * [11] E. A. Theodorou and E. Todorov, “Relative entropy and free energy dualities: Connections to path integral and kl control,” in _IEEE Annual Conference on Decision and Control (CDC)_. IEEE, 2012, pp. 1466–1473.
  * [12] S. Särkkä, “Unscented rauch–tung–striebel smoother,” _IEEE Transactions on Automatic Control_ , vol. 53, no. 3, pp. 845–849, 2008.
  * [13] H.-C. Ruiz and H. J. Kappen, “Particle smoothing for hidden diffusion processes: Adaptive path integral smoother,” _IEEE Transactions on Signal Processing_ , vol. 65, no. 12, pp. 3191–3203, 2017.
  * [14] A. Savitzky and M. J. Golay, “Smoothing and differentiation of data by simplified least squares procedures.” _Analytical Chemistry_ , vol. 36, no. 8, pp. 1627–1639, 1964.
  * [15] K. Adhikari, S. Tatinati, K. C. Veluvolu, and J. A. Chambers, “Physiological tremor filtering without phase distortion for robotic microsurgery,” _IEEE Transactions on Automation Science and Engineering_ , 2020.
  * [16] J. Wang, Y. Ye, X. Pan, X. Gao, and C. Zhuang, “Fractional zero-phase filtering based on the riemann–liouville integral,” _Signal Processing_ , vol. 98, pp. 150–157, 2014.
  * [17] S. Nakatani and H. Date, “Swing up control of inverted pendulum on a cart with collision by monte carlo model predictive control,” in _Annual Conference of the Society of Instrument and Control Engineers of Japan (SICE)_. IEEE, 2019, pp. 1050–1055.
  * [18] G. Williams, A. Aldrich, and E. A. Theodorou, “Model predictive path integral control: From theory to parallel computation,” _Journal of Guidance, Control, and Dynamics_ , vol. 40, no. 2, pp. 344–357, 2017.
  * [19] A. Nagabandi, G. Kahn, R. S. Fearing, and S. Levine, “Neural network dynamics for model-based deep reinforcement learning with model-free fine-tuning,” in _IEEE International Conference on Robotics and Automation (ICRA)_. IEEE, 2018, pp. 7559–7566.
  * [20] R. Sekar, O. Rybkin, K. Daniilidis, P. Abbeel, D. Hafner, and D. Pathak, “Planning to explore via self-supervised world models,” in _International Conference on Machine Learning (ICML)_. PMLR, 2020, pp. 8583–8592.
  * [21] N. A. Spielberg, M. Brown, N. R. Kapania, J. C. Kegelman, and J. C. Gerdes, “Neural network vehicle models for high-performance automated driving,” _Science Robotics_ , vol. 4, no. 28, 2019.
  * [22] A. Punjani and P. Abbeel, “Deep learning helicopter dynamics models,” in _IEEE International Conference on Robotics and Automation (ICRA)_. IEEE, 2015, pp. 3223–3230.
  * [23] J. Bae, T. Kim, W. Lee, and I. Shim, “Curriculum learning for vehicle lateral stability estimations,” _IEEE Access_ , vol. 9, pp. 89 249–89 262, 2021\.


# Scaling Synthetic Logical Reasoning Datasets
with Context-Sensitive Declarative Grammars

Damien Sileo

###### Abstract

Logical reasoning remains a challenge for natural language processing, but it
can be improved by training language models to mimic theorem provers on
procedurally generated problems. Previous work used domain-specific proof
generation algorithms, which biases reasoning toward specific proof traces and
limits auditability and extensibility. We present a simpler and more general
declarative framework with flexible context-sensitive rules binding multiple
languages (specifically, simplified English and the TPTP theorem-proving
language). We construct first-order logic problems by selecting up to 32
premises and one hypothesis. We demonstrate that using semantic constraints
during generation and careful English verbalization of predicates enhances
logical reasoning without hurting natural English tasks. We use relatively
small DeBERTa-v3 models to achieve state-of-the-art accuracy on the FOLIO
human-authored logic dataset, surpassing GPT-4 in accuracy with or without an
external solver by $12\%$.

Scaling Synthetic Logical Reasoning Datasets
with Context-Sensitive Declarative Grammars

##  1 Introduction

Language models trained only on natural language show lackluster capabilities
at logical reasoning McCoy et al. (2023); Mahowald et al. (2024). As a
countermeasure, we can train neural models to match the output of symbolic
reasoning systems (e.g., logic theorem provers, or other algorithms) on
procedurally generated problems, to sharpen their reasoning capabilities. This
process improves accuracy on some human-authored problems Wu et al. (2021);
Clark et al. (2020); Wu et al. (2022); Liu et al. (2023).

Previous work on synthetic first-order logic (FOL) reasoning datasets,
RuleTaker Clark et al. (2020), LogicNLI Goodwin et al. (2020a) and FLD
Morishita et al. (2023), write dedicated code re-implementing the FOL axioms
from scratch to generate proofs, and translate the generated problems to
natural language. We propose Unigram, a framework for synthetic reasoning data
generation, specifically designed to generate problems jointly into multiple
languages. We represent grammars with concise and expressive rules binding two
languages, and constraints to prune unwanted generations.

We write the most extensive grammar of FOL semantic fragments to our
knowledge. We structure the generated expressions into Premise, Hypothesis
pairs, and annotate their logical relationship
(entailment/contradiction/neutral) with a FOL solver, following the natural
language inference (NLI) framework Goodwin et al. (2020b). A simplistic FOL
NLI problem is: Premise: Everyone who is happy is rich. Mary is rich.
Hypothesis: Mary is happy Label: Neutral.

We fine-tune DeBERTa NLI models He et al. (2021) on Unigram-FOL and compare it
with previous similar datasets. The 184M parameters (base-size) beats GPT-4
augmented or not with external theorem provers, on the FOLIO Han et al. (2022)
dataset. Our contributions are as follows: (i) A dataset of reasoning problems
expressed in English and TPTP (a language that can be interfaced with numerous
theorem provers) alongside Vampire proof annotations, covering FOL with
equality and both finite and open domains, improved compositionality, and more
extensive quantifiers. (ii) Ablations measuring the effect of constraining
material conditionals usage, of using realistic English predicates, and of
reimplementing LogicNLI with declarative generation instead of proof tree
generation, highlighting that declarative can work better but that a richer
logical modeling drives most of the improvement. (iii) A general reasoning
problem grammar-based generation framework relying on solvers. The generation
library, grammars, models, and generated dataset are publicly
available111[code:GitHub ][data:HF-datasets ].

##  2 Related work

#### Synthetic datasets for reasoning

Numerous works investigate the logical capabilities of NLP models using
textual datasets and symbolic reasoning Helwe et al. (2022). We focus on the
grammar-derived synthetic datasets. RuleTaker (Clark et al., 2020) explores
this area with a subset of first-order logic. LogicNLI addresses a broader FOL
subset (Tian et al., 2021). FLD explores full FOL Morishita et al. (2023) and
increased compositionality. Richardson et al. (2020); Richardson and Sabharwal
(2022) use a solver to study the satisfiability in natural language using the
Z3 solver and dedicated generation logic on constrained problems. Other work
explore non-standard logic with synthetic dataset, notably probabilistic
(Sileo and Moens, 2023), paraconsistant Kazemi et al. (2024), epistemic Sileo
and Lernould (2023) logics.

#### Generation frameworks

Multiple frameworks already implement generation from handwritten grammars.
NLTK (Bird and Loper, 2004) has a context-free grammar tool, but cannot
natively handle multiple languages or large-scale generation. Grammatical
Framework (Ranta, 2004) is the closest tool to ours. It enables generation
from abstract grammars and linearization into concrete grammars (e.g. French
and English) but it is translation-oriented and not context-sensitive. GLIF
(Schaefer and Kohlhase, 2020) extends Grammatical Framework to parse English
into logical formulas but is not suited for generation either.

##  3 Scalable dataset generation without forward inference

###  3.1 Forward inference

Previous NLI-style FOL reasoning datasets (RuleTaker, LogicNLI, FLD) generate
examples using proof generators that are based on the axioms of FOL. This
requires domain-specific generation code and introduces unwanted complexity.
Elimination and Introduction rules can cancel each other and create an
illusion of reasoning depth. We found that some examples in the Proofwriter
dataset Tafjord et al. (2021) directly contain the premise in the hypothesis
despite having a reasoning depth of 5. When constructing NLI pairs, generating
neutral examples requires special strategies introducing a sampling bias, and
it can be the same for contradiction generation. Proof generation techniques
enable high reasoning depth but at the cost of breadth (linguistic variety and
reasoning variety).

###  3.2 Declarative generation

We fully rely on an existing FOL solver and we propose Unigram, a simpler,
more generic method to generate problems with multilingual grammars where
rules bind multiple surface form realization templates. A Unigram Rule
declaration specifies a type signature, and two surface form realizers, and
optional validity constraints: $\textbf{R}(\text{output\\_type, input\\_types,
realizers, constraints})$ The signature specifies the type of the rule output
and the type of the arguments. The realizers take the arguments as input and
map them to a string. We can have a realizer for a logic code and a realizer
for English. Using functions allows more expressivity than context-free
grammars (Hunter, 2021), but for most cases with can treat template strings as
functions using Python https://anytree.readthedocs.io/anytree tree.
Constraints are binary functions checking construction validity. One useful
constraint is distinctness, e.g. (arguments of the same type should have a
different realization), to avoid repetitions or statements like Mary likes
Mary. We enable this constraint by default.

#### Generation algorithm

We use a depth-first algorithm that recursively fills in the leftmost non-
terminal leave with random type-matching rule sampling until constraints are
satisfied. This enables left-to-right generation, allowing realizers and
constraints to access the current context. We recursively call realizers to
construct surface forms (e.g. English text).

##  4 Application to first-order logic (FOL)

We use Unigram to enrich FOL problem generation while also avoiding ambiguity,
starting as a superset of LogicNLI (grammar in Appendix A). To create a
problem, we uniformly sample 1 to 32 sentences as premises and 1 sentence per
hypothesis ensuring that all symbols are present in the premise. We exclude
non-satisfiable formulas (paradoxes) in premise groups and hypotheses. We
label pairs as entailment if $(premise\land\neg hypothesis)$ is unsatisfiable,
as contradiction if $(premise\land hypothesis)$ is unsatisfiable, and as
neutral otherwise. Following Ruletaker and LogicNLI, we create problems with
predicates over named individuals (e.g. Mary is young). We generate gender-
balanced English surnames with CensusName. We now present new logical modeling
features absent from the previous comparable datasets:

#### Explicit finite and open domains

We explicitly mention the domain when using the quantifiers. We introduce two
locations, anywhere, and a room with occupants e.g. Mary, and Paul are the
only persons in the room. which logically means $\forall
x,room(x)\to(x=\text{Mary}\lor x=\text{Paul})$. We can then quantify over the
room (everyone in the room) or anywhere (everyone anywhere). By doing this, we
can generate induction problems (checking that everyone in the room is happy
if Mary and Paul are happy) and test reasoning with both finite and open
domains. This requires handling FOL with equality which was not implemented in
previous work.

#### Quantifiers and logical relationships

We extend previous work with more complete quantifiers not all, nobody, not
everyone. We leverage context-sensitivity to create a rule for polysyllogisms
(predicate chains of the form all A are B, all B are C, all C are D. We also
introduce only if, unless, otherwise as conditionals and allow sentence-level
negation.

#### Constraining material conditionals

Like previous work, we use material conditional to express conditional
statements: if p then q is formalized as $p\to q$ i.e. $\neg p\lor q$. This
means that the implication is true if $p$ is false, and that negating $p\to q$
entails $q$ both $\neg p$ which can be counter-intuitive. We use a constraint
to eliminate all conditionals within the scope of negations and of other
conditionals.

#### Improving predicate verbalization

RuleTaker and LogicNLI use adjectives as logical predicates but do not handle
their semantic interference. RuleTaker do not consider being both blue and
being green as contradictory. LogicNLI uses 379 adjectives treated as
independent, including ugly and ugliest. FLD uses pseudo language like  the
lard does hurtle pushup. We prompted GPT-4 (May version) to Generate 150
predicates where each predicate does not contradict nor entail any other
predicate. Two examples: "enjoys wildlife photography" and "owns a smart tv".
We remove errors and provide manual negations. We also use relationships
(like, is a sibling of, modeling symmetry axioms when relevant, and
adjectives.

#### Logical representation language

Previous LogicNLI, RuleTaker, FLD, and FOLIO all use their own logical format,
representing formulas as lists or strings. We use the TPTP Sutcliffe (2010)
TPTP FOF language which is a standard syntax for theorem provers evaluation
and is compatible with many theorem provers, notably Vampire Reger et al.
(2022), Z3 De Moura and Bjørner (2008) or Prover9 McCune (2005). We select the
Vampire Reger et al. (2022) theorem prover which provides short and readable
proofs and details all the premises used during a derivation.

#### Complexity control

Methods based on forward inference can theoretically control the proof depth
using hyperparameters. Here, to avoid mostly sampling shallow problems, we
limit the number of non-neutral examples where the proof to the number of
examples using 5 inputs, for each number of inputs. Neutrals are still a
majority by an order of magnitude. To sample hard neutral examples, we use a
Gradient Boosting classifier with 100 trees (and scikit-learn 1.5.0 Pedregosa
et al. (2011) default parameters otherwise) to predict the labels based on
unigram counts of the logical operators in the premise and hypothesis. We
train on $1k$ examples, discard these, and then discard the most confident
neutral predictions to achieve balanced labels.

##  5 Experiments

Model size | Auxilary training | FOLIO | +ft | WANLI | +ft | CTRL | +ft | Fragments
---|---|---|---|---|---|---|---|---
D-base | - | 49.5 | 74.3 | 65.2 | 77.4 | 46.2 | 56.7 | 63.6
D-base | RuleTaker | 55.1 | 71.3 | 60.9 | 73.8 | 36.0 | 53.0 | 48.7
D-base | LogicNLI | 50.5 | 69.3 | 61.1 | 72.4 | 38.4 | 54.4 | 56.3
D-base | FLD | 59.9 | 72.3 | 60.0 | 73.6 | 38.2 | 55.8 | 56.8
D-base | Unigram-FOL | 64.4 | 78.2 | 63.6 | 75.6 | 42.8 | 56.6 | 65.4
D-base |  $-$ Constrained_Conditionals | 63.4 | 81.2 | 62.2 | 71.8 | 40.6 | 55.4 | 59.8
D-base |  $-$ Realistic_Predicates | 62.4 | 76.2 | 65.8 | 74.4 | 41.8 | 53.2 | 68.2
D-base | Unigram-LogicNLI | 57.4 | 71.3 | 61.6 | 76.4 | 38.6 | 55.6 | 57.8
D-large | - | 49.5 | 70.0 | 66.2 | 77.0 | 49.6 | 62.0 | 67.6
D-large | RuleTaker | 58.1 | 77.2 | 68.5 | 77.9 | 43.1 | 60.7 | 61.7
D-large | LogicNLI | 58.7 | 73.3 | 68.5 | 77.4 | 45.4 | 60.9 | 64.4
D-large | FLD | 60.9 | 78.2 | 68.0 | 77.6 | 44.0 | 59.8 | 61.7
D-large | Unigram-FOL | 63.4 | 82.2 | 75.4 | 81.6 | 48.2 | 62.2 | 73.2
D-large | Unigram-FOL+FLD | 78.2 | 88.6 | 65.2 | 78.4 | 42.2 | 57.9 | 75.4
Figure 1: Comparison of auxiliary synthetic training datasets effect on the
evaluation tasks. We report the average accuracy of two runs. $\mathcal{D}$
column refer to zero-shot $\mathcal{D}$ test accuracy after synthetic
auxiliary training, and +ft refers to the test accuracy after auxiliary
training then further fine-tuning $\mathcal{D}$ training set (in the previous
column).

###  5.1 Methodology

We fine-tune a pre-trained NLI model on multiple synthetic FOL datasets:
LogicNLI, FLD, RuleTaker, and on Unigram-FOL. We then evaluate the direct
effect on other three-way entailment downstream tasks, and on further fine-
tuning on the training data of evaluation tasks Phang et al. (2018). We use
the DeBERTa-v3 He et al. (2021) NLI models trained on the tasksource
collection (Sileo, 2024)222 hf.co/deberta-v3-base-tasksource-nli. We use a
learning rate of $1e{-}5$ for DeBERTa-large and $2e{-}5$ Mosbach et al. (2021)
for DeBERTa-base, 1 or 3 epochs (based on intrinsic validation accuracy) and
Huggingface Transformers Wolf et al. (2019) version 4.41 default Trainer
arguments otherwise. We generate $100k$ examples with a $80/10/10$
train/dev/test split. but we only use $40k$ training training examples to
match FLD. We use the FLD$\star$ version of FLD. We use the ProofWriter
Tafjord et al. (2021) open-world-assumption version of RuleTaker. We exclude
LogicNLI examples labeled as paradoxes and we map all labels to NLI labels.

###  5.2 Evaluation datasets

We evaluate on two pure reasoning datasets, FOLIO and Fragments, and on two
more general datasets: FOLIO (Han et al., 2022) contains human-written FOL
problems. We evaluate on the validation set to compare to Olausson et al.
(2023) results who report $72.5\%$ accuracy using a GPT-4 with a solver and
$75.3\%$ with chain-of-thoughts. We construct another validation set from
$10\%$ of train and map labels to NLI labels. Wei et al. (2022) WANLI Liu et
al. (2022) is a NLI dataset with diverse and challenging reasoning patterns.
ConTRoL Liu et al. (2021) is a NLI dataset requiring multiple premises to
derive the correct label, measuring contextual reasoning. Fragments Richardson
et al. (2020) is based on formal semantics templates and evaluate reasoning
with quantifiers; this dataset is mostly suited to evaluation, as training
quickly leads to almost perfect test accuracy.

#### Comparison with previous synthetic datasets

Table 1 shows the accuracy of multiple auxiliary training datasets on the
evaluation dataset. Unigram-FOL outperforms RuleTaker, LogicNLI, and FLD on
all tasks with a comfortable margin, and leads to lesser degradation on the
datasets that are not only focused on logic (WANLI, ConTRoL). The last line of
the table combines Unigram-FOL (with the full 100k examples) with FLD and
shows that combining generation methods can further push the state of the art
on FOLIO. We conduct ablations to better understand the source of this
improvement, presented in the middle of Table 1.

#### Unigram-LogicNLI

We use our declarative generation method on the base LogicNLI grammar to
disentangle the effect of the generation technique from the grammar itself.
This outperforms the original LogicNLI but not Unigram-FOL which highlights
the value of our additional constructions.

#### Replacing Realistic Predicates

We replace our generated predicates with the original LogicNLI adjectives
(containing semantic interferences); this degrades FOLIO accuracy but does not
strongly impact other NLI tasks, notably Fragments which mainly use adjectives
as predicates.

#### Removing Conditionals Constraints

Unrestricting usage of material conditionals harms the zero-shot transfer on
FOLIO and the capabilities at more general reasoning, which confirms that
removing counter-intuitive constructs can help transferability.

##  6 Conclusion

We showed that simple declarative grammars paired with solvers can outperform
complex proof tree generators for reasoning dataset generations and released a
new FOL reasoning dataset, models, and ablations. Our framework can help
future reasoning research, notably on explanation since fully aligned TPTP
code can be leveraged to model necessity and sufficiency. We plan to extend
Unigram to planning, constraint satisfaction and modal logic.

## Limitations

Reasoning methods based on neural networks do not provide formal guarantees
and can introduce biases in real applications. They can be used as a
complement to externalization methods Olausson et al. (2023). Automatically
formalizing a problem is difficult and can lead to mistakes Olausson et al.
(2023) which could be detected by internalization-based methods. Our dataset
could be used to automate formalization but we did not try such experiments.
In addition, our work is only conducted with English language and encoder
models, mainly used for verification and not generation. We only used one
model architecture, DeBERTa, while other architectures like Albert Lan et al.
(2020) or other recursive architectures could be more suited to reasoning.

## Ethical considerations

Our models are derived from language models which inherit bias from their
training corpus. We did not conduct any human annotations, relying on already
annotated datasets to validate our methodology. We use encoder models which
have lower energy consumption than decoders Luccioni et al. (2024) and
performed experiments with less than 20 total days on a Nvidia A100 GPU.

## References

  * Bird and Loper (2004) Steven Bird and Edward Loper. 2004.  NLTK: The natural language toolkit.  In _Proceedings of the ACL Interactive Poster and Demonstration Sessions_ , pages 214–217, Barcelona, Spain. Association for Computational Linguistics.
  * Clark et al. (2020) Peter Clark, Oyvind Tafjord, and Kyle Richardson. 2020.  Transformers as soft reasoners over language.  In _Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence, IJCAI-20_ , pages 3882–3890. International Joint Conferences on Artificial Intelligence Organization.  Main track.
  * De Moura and Bjørner (2008) Leonardo De Moura and Nikolaj Bjørner. 2008.  Z3: An efficient smt solver.  In _International conference on Tools and Algorithms for the Construction and Analysis of Systems_ , pages 337–340. Springer.
  * Goodwin et al. (2020a) Emily Goodwin, Koustuv Sinha, and Timothy J O’Donnell. 2020a.  Probing linguistic systematicity.  _arXiv preprint arXiv:2005.04315_.
  * Goodwin et al. (2020b) Emily Goodwin, Koustuv Sinha, and Timothy J. O’Donnell. 2020b.  Probing linguistic systematicity.  In _Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics_ , pages 1958–1969, Online. Association for Computational Linguistics.
  * Han et al. (2022) Simeng Han, Hailey Schoelkopf, Yilun Zhao, Zhenting Qi, Martin Riddell, Luke Benson, Lucy Sun, Ekaterina Zubova, Yujie Qiao, Matthew Burtell, et al. 2022.  Folio: Natural language reasoning with first-order logic.  _arXiv preprint arXiv:2209.00840_.
  * He et al. (2021) Pengcheng He, Jianfeng Gao, and Weizhu Chen. 2021.  Debertav3: Improving deberta using electra-style pre-training with gradient-disentangled embedding sharing.  _arXiv preprint arXiv:2111.09543_.
  * Helwe et al. (2022) Chadi Helwe, Chloé Clavel, and Fabian Suchanek. 2022.  Logitorch: A pytorch-based library for logical reasoning on natural language.  In _The 2022 Conference on Empirical Methods in Natural Language Processing: System Demonstrations_.
  * Hunter (2021) Tim Hunter. 2021.  The chomsky hierarchy.  _A companion to Chomsky_ , pages 74–95.
  * Kazemi et al. (2024) Mehran Kazemi, Quan Yuan, Deepti Bhatia, Najoung Kim, Xin Xu, Vaiva Imbrasaite, and Deepak Ramachandran. 2024.  Boardgameqa: A dataset for natural language reasoning with contradictory information.  _Advances in Neural Information Processing Systems_ , 36.
  * Lan et al. (2020) Zhenzhong Lan, Mingda Chen, Sebastian Goodman, Kevin Gimpel, Piyush Sharma, and Radu Soricut. 2020.  Albert: A lite bert for self-supervised learning of language representations.  In _International Conference on Learning Representations_.
  * Liu et al. (2022) Alisa Liu, Swabha Swayamdipta, Noah A. Smith, and Yejin Choi. 2022.  WANLI: Worker and AI collaboration for natural language inference dataset creation.  In _Findings of the Association for Computational Linguistics: EMNLP 2022_ , pages 6826–6847, Abu Dhabi, United Arab Emirates. Association for Computational Linguistics.
  * Liu et al. (2021) Hanmeng Liu, Leyang Cui, Jian Liu, and Yue Zhang. 2021.  Natural language inference in context - investigating contextual reasoning over long texts.  _Proceedings of the AAAI Conference on Artificial Intelligence_ , 35(15):13388–13396.
  * Liu et al. (2023) Qian Liu, Fan Zhou, Zhengbao Jiang, Longxu Dou, and Min Lin. 2023.  From zero to hero: Examining the power of symbolic tasks in instruction tuning.  _arXiv preprint arXiv:2304.07995_.
  * Luccioni et al. (2024) Sasha Luccioni, Yacine Jernite, and Emma Strubell. 2024.  Power hungry processing: Watts driving the cost of ai deployment?  In _The 2024 ACM Conference on Fairness, Accountability, and Transparency_ , pages 85–99.
  * Mahowald et al. (2024) Kyle Mahowald, Anna A Ivanova, Idan A Blank, Nancy Kanwisher, Joshua B Tenenbaum, and Evelina Fedorenko. 2024.  Dissociating language and thought in large language models.  _Trends in Cognitive Sciences_.
  * McCoy et al. (2023) R Thomas McCoy, Shunyu Yao, Dan Friedman, Matthew Hardy, and Thomas L Griffiths. 2023.  Embers of autoregression: Understanding large language models through the problem they are trained to solve.  _arXiv preprint arXiv:2309.13638_.
  * McCune (2005) William McCune. 2005.  Release of prover9.  In _Mile high conference on quasigroups, loops and nonassociative systems, Denver, Colorado_.
  * Morishita et al. (2023) Terufumi Morishita, Gaku Morio, Atsuki Yamaguchi, and Yasuhiro Sogawa. 2023.  Learning deductive reasoning from synthetic corpus based on formal logic.  In _International Conference on Machine Learning_ , pages 25254–25274. PMLR.
  * Mosbach et al. (2021) Marius Mosbach, Maksym Andriushchenko, and Dietrich Klakow. 2021.  On the stability of fine-tuning {bert}: Misconceptions, explanations, and strong baselines.  In _International Conference on Learning Representations_.
  * Olausson et al. (2023) Theo Olausson, Alex Gu, Ben Lipkin, Cedegao Zhang, Armando Solar-Lezama, Joshua Tenenbaum, and Roger Levy. 2023.  LINC: A neurosymbolic approach for logical reasoning by combining language models with first-order logic provers.  In _Proceedings of the 2023 Conference on Empirical Methods in Natural Language Processing_ , pages 5153–5176, Singapore. Association for Computational Linguistics.
  * Pedregosa et al. (2011) Fabian Pedregosa, Gaël Varoquaux, Alexandre Gramfort, Vincent Michel, Bertrand Thirion, Olivier Grisel, Mathieu Blondel, Peter Prettenhofer, Ron Weiss, Vincent Dubourg, et al. 2011.  Scikit-learn: Machine learning in python.  _the Journal of machine Learning research_ , 12:2825–2830.
  * Phang et al. (2018) Jason Phang, Thibault Févry, and Samuel R Bowman. 2018.  Sentence encoders on stilts: Supplementary training on intermediate labeled-data tasks.  _arXiv preprint arXiv:1811.01088_.
  * Ranta (2004) Aarne Ranta. 2004.  Grammatical framework.  _Journal of Functional Programming_ , 14(2):145–189.
  * Reger et al. (2022) Giles Reger, Martin Suda, Andrei Voronkov, Laura Kovács, Ahmed Bhayat, Bernhard Gleiss, Marton Hajdu, Petra Hozzova, JR Evgeny Kotelnikov, Michael Rawson, et al. 2022.  Vampire 4.7-smt system description.
  * Richardson et al. (2020) Kyle Richardson, Hai Hu, Lawrence Moss, and Ashish Sabharwal. 2020.  Probing natural language inference models through semantic fragments.  _Proceedings of the AAAI Conference on Artificial Intelligence_ , 34:8713–8721.
  * Richardson and Sabharwal (2022) Kyle Richardson and Ashish Sabharwal. 2022.  Pushing the limits of rule reasoning in transformers through natural language satisfiability.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 36, pages 11209–11219.
  * Schaefer and Kohlhase (2020) Jan Frederik Schaefer and Michael Kohlhase. 2020.  Glif: A declarative framework for symbolic natural language understanding.  In _FCR@ KI_ , pages 4–11.
  * Sileo (2024) Damien Sileo. 2024.  tasksource: A large collection of nlp tasks with a structured dataset preprocessing framework.  In _Proceedings of the 2024 Joint International Conference on Computational Linguistics, Language Resources and Evaluation (LREC-COLING 2024)_ , pages 15655–15684.
  * Sileo and Lernould (2023) Damien Sileo and Antoine Lernould. 2023.  MindGames: Targeting theory of mind in large language models with dynamic epistemic modal logic.  In _Findings of the Association for Computational Linguistics: EMNLP 2023_ , pages 4570–4577, Singapore. Association for Computational Linguistics.
  * Sileo and Moens (2023) Damien Sileo and Marie-francine Moens. 2023.  Probing neural language models for understanding of words of estimative probability.  In _Proceedings of the 12th Joint Conference on Lexical and Computational Semantics (*SEM 2023)_ , pages 469–476, Toronto, Canada. Association for Computational Linguistics.
  * Sutcliffe (2010) Geoff Sutcliffe. 2010.  The tptp world–infrastructure for automated reasoning.  In _International Conference on Logic for Programming Artificial Intelligence and Reasoning_ , pages 1–12. Springer.
  * Tafjord et al. (2021) Oyvind Tafjord, Bhavana Dalvi, and Peter Clark. 2021.  ProofWriter: Generating implications, proofs, and abductive statements over natural language.  In _Findings of the Association for Computational Linguistics: ACL-IJCNLP 2021_ , pages 3621–3634, Online. Association for Computational Linguistics.
  * Tian et al. (2021) Jidong Tian, Yitian Li, Wenqing Chen, Liqiang Xiao, Hao He, and Yaohui Jin. 2021.  Diagnosing the first-order logical reasoning ability through LogicNLI.  In _Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing_ , pages 3738–3747, Online and Punta Cana, Dominican Republic. Association for Computational Linguistics.
  * Wei et al. (2022) Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, Fei Xia, Ed Chi, Quoc V Le, Denny Zhou, et al. 2022.  Chain-of-thought prompting elicits reasoning in large language models.  _Advances in neural information processing systems_ , 35:24824–24837.
  * Wolf et al. (2019) Thomas Wolf, Lysandre Debut, Victor Sanh, Julien Chaumond, Clement Delangue, Anthony Moi, Pierric Cistac, Tim Rault, Rémi Louf, Morgan Funtowicz, et al. 2019.  Huggingface’s transformers: State-of-the-art natural language processing.  _arXiv preprint arXiv:1910.03771_.
  * Wu et al. (2022) Yuhuai Wu, Felix Li, and Percy S Liang. 2022.  Insights into pre-training via simpler synthetic tasks.  _NEURIPS 2022_ , 35:21844–21857.
  * Wu et al. (2021) Yuhuai Wu, Markus N Rabe, Wenda Li, Jimmy Ba, Roger B Grosse, and Christian Szegedy. 2021.  Lime: Learning inductive bias for primitives of mathematical reasoning.  In _ICML_ , pages 11251–11262. PMLR.

##  Appendix A Unigram LogicNLI reimplementation

⬇

\parfrom unigram import Rule as R

\par\parADJECTIVES = [’rich’,’quiet’,’old’,’tall’,’kind’,’brave’,’wise’,

’happy’, ’strong’,’curious’,’patient’,’funny’,’generous’,’humble’]

# (We selected adjectives with no clear semantic interference)

NAMES = [’mary’, ’paul’, ’fred’, ’alice’, ’john’, ’susan’, ’lucy’]

\parR.init([’tptp’,’eng’], "fof")

\parR(’premise(’ + ’,’.join([’rule’]*16’)’+’,’+’.’join([’fact]*8)+’)’,

’&\n’.join([f’({i})’ for i in range(24)]),

’\n’.join([f’{i}’ for i in range(24)]))

\parR(’hypothesis(person,a)’,’1(0)’,’0 is 1’)

\parfor a in ADJECTIVES:

R(’adj’, a), R(’adj’, f’~{a}’, f’not {a}’, weight=0.2)

\parR(’property(adj,adj)’, ’(0(?)&1(?))’, ’both 0 and 1’)

R(’property(adj,adj)’, ’(0(?)|1(?))’, ’0 or 1’)

R(’property(adj,adj)’, ’(0(?)<~>1(?))’, ’either 0 or 1’, weight=0.5)

R(’property(adj)’, ’0(?)’, ’0’)

\parR(’rule(property,property)’, ’![X]:(0[?←X]=>1[?←X])’,

’everyone who is 0 is 1’)

R(’rule(property,property)’, ’![X]:(0[?←X]<=>1[?←X])’,

’everyone who is 0 is 1 and vice versa’)

\parfor p in NAMES:

R(’person’, p)

\parR(’fact(person,property)’,’1[?←0]’, ’0 is 1’)

R(’fact(property)’, ’?[X]:(0[?←X])’, ’someone is 0’, weight=0.2)

\parR(’rule(fact,fact)’, ’(0)=>(1)’, ’if 0 then 1’)

R(’rule(fact,fact)’, ’(0)<=>(1)’, ’if 0 then 1 and vice versa’)