# Optimal Trajectory Generation for Autonomous Vehicles Under Centripetal
Acceleration Constraints for In-lane Driving Scenarios

Yajia Zhang*, Hongyi Sun, Jinyun Zhou, Jiangtao Hu, Jinghao Miao Yajia Zhang,
Hongyi Sun, Jinyun Zhou, Jiangtao Hu, Jinghao Miao are with Baidu USA LLC, 250
Caribbean Drive Sunnyvale, USA *Corresponding author: Yajia Zhang
<EMAIL_ADDRESS>
The paper was accepted by IEEE International Conference on Intelligent
Transportation Systems (ITSC) 2019

###### Abstract

This paper presents a noval method that generates optimal trajectories for
autonomous vehicles for in-lane driving scenarios. The method computes a
trajectory using a two-phase optimization procedure. In the first phase, the
optimization procedure generates a close-form driving guide line with
differetiable curvatures. In the second phase, the procedure takes the driving
guide line as input, and outputs dynamically feasible, jerk and time optimal
trajectories for vehicles driving along the guide line. This method is
especially useful for generating trajectories at curvy road where the vehicles
need to apply frequent accelerations and decelerations to accommodate
centripetal acceleration limits.

##  I Introduction

Trajectory planning is an important component in autonomous driving systems
(ADS). It plays a critical role on safety and comfort. Safety is of top
priority as any collision might lead to hazardous situations. Assuming
predicted trajectories of surrounding obstacles are given from upper stream
module of ADS, path-time obstacle graph is a commonly used tool for collision
avoidance analysis if future path of the autonomous driving vehicle (ADV) is
determined. This method projects the predicted trajectories of surrounding
obstacles onto the spatio-time plane and forms path-time obstacles which
specify at which time the further path of the ADV would be on collision. The
free area forms the collision-free zone for trajectory planning. This method
is particularly useful for autonomous vehicles in structured road scenarios.
It fully utilizes the domain knowledge, as most vehicles are driving along
lanes. The method we propose adopts path-time-obstacle graph in collision
avoidance analysis and always plans a trajectory that lie within the
collision-free zone.

Comfort is another goal to achieve for ADS. Several factors affect and are
used to measure the comfort of one trajectory. Acceleration and acceleration
change rate (commonly known as jerk) are most commonly used metrics for
vehicle trajectories. Furthermore, depending on the direction, human weight
acceleration and jerk significant differently for longitudinal and lateral
movement. Acceleration and jerk in lateral direction must be bounded and
minimized. For driving along a curvy road, the longitudinal speed must be
adjusted frequently according to the curve, i.e., the curvature of the road. A
driving guide line is an abstraction of the road center line, which contains
the geometrical information of the road. We assume the target of the
autonomous vehicle in-lane driving is following the driving guide line. To
achieve comfortable riding experience, the vehicle needs to accelerate and
decelerate according to the curvature of the driving guide line. In our
proposed method, the algorithm can directly consider the geometrical
information of the driving guide line.

Optimization is a common approach in trajectory generation as it takes the
objective or cost function and constraints directly into trajectory
generation. For high degrees of freedom (DOFs) configuration space,
optimization for trajectory generation is generally slow and prone to local
minima, it is generally suitable for lower dimensional vehicle configuration
space. In our method, we use a two-phase optimization procedure. Each one
intends to solve a subset of trajectory generation problem. In this way, it
greatly reduces the overall complexity of optimization. For the first phase,
our method generates a smooth driving guide line for ADV to follow; in the
second phase, the optimization procedure takes the collision-free zone
resulted from path-time obstacle graph analysis and the close-formed driving
guide line as input, and generates a collision-free and comfort trajectory
that minimizes longitudinal acceleration, and centripetal acceleration and
jerk.

##  II Related Work

Trajectory planning is a critical component in autonomous driving systems.
Recently, a number of algorithms [7, 8, 10] have been developed since DARPA
Grand Challenge (2004, 2005) and Urban Challenge (2007).

Randomized planners such as Rapidly Exploring Random Tree (RRT)[6] are
intended to solve high-DOF robot motion planning with differential
constraints. However, it is difficult for randomized planners to utilize the
domain knowledge from the structured environment for quickly convergence.
Nevertheless, the computed trajectory is generally low quality and thus cannot
be used directly without a post-processing step. Recent research on optimal
randomized planner, such as [3], can produce high-quality trajectories given
enough planning time. But the convergence to optimal trajectory takes rather
long time thus it cannot be used in the dynamically changing environment.

Discrete search method [5] computes a trajectory by concatenating a sequence
of pre-computed maneuvers. The contatenation is done by checking whether the
ending state of a maneuver is sufficiently close to the starting state of the
target maneuver. This method generally works well for simple environment such
as highway scenarios. However, the number of required maneuvers needs to grow
exponentially in order to solve complex urban driving cases.

The work in [13] runs an quadratic programming procedure in global/map frame.
The trajectory is finely discretized in Cartesian space. The positional
attributions of the trajectory are directly used as optimization variables,
and outputs a trajectory that minimizes the objective function which combines
the measurement of safety and comfort. The advantage of using optimization is
it provides direct enforcement of optimality modeling. The dense
discretization approach provides maximal control of trajectory to tackle
complex scenarios.

In [12], trajectory planning is performed in Frenet frame. Given a smooth
driving guide line, this method decouples the movement of vehicle in map frame
into two orthogonal movements, one longitudinal movement that along the
driving guide line and one lateral movement that perpendicular to the guide
line. For both movements, the trajectories are generated using random samples,
i.e., the end conditions and parameter are discretized into certain
resolution. The sampled end conditions are directly connected with the initial
condition using quintic or quartic polynomials. Then these longitudinal and
lateral trajectories are combined and selected according to a predefined cost
function.

The major drawback with the method is it lacks control of the trajectory. For
complex driving scenarios, it is difficult for this method to generate
feasible trajectories. Nevertheless, some caveats of using polynomial include
problems with stopping, unexpected acceleration and deceleration. To tackle
complex problems in real world, we need to maximize our ability of controlling
the trajectory. Thus, optimization is a promising direction as constraints in
the task domain can be directly considered in trajectory generation. Existing
optimization-based methods such as [13] [9] runs the optimization in map
frame.

The overall algorithm framework we proposed is similar to the one in [12],
however, we use optimization to solve the 1d planning problems, which greatly
enhances the flexibility of the trajectory.

The method we present hybrids the Frenet frame trajectory planning framework
and optimization-based trajectory generation. Also, the trajectory
optimization is performed in two-phases, where each phase is a lower
dimensional problem. In this proposed method, the difficulty of optimization
is greatly reduced.

##  III Problem Definition

The configuration for a vehicle with differential constraints in Cartesian
space can be represented using three variables, $(x,y,\theta)$, where $x$, $y$
specify the coordinate of some reference point for the vehicle and $\theta$
specifies the vehicle’s heading angle in the Cartesian space. In our work, we
incorporate one more dimension $\kappa$, which is the instant curvature
resulted from vehicle’s steering, into the configuration space for more
accurate configuration modeling, and hence the computed trajectory provides
additional information that can be used for better designing the feedback
controller. Trajectory planning for non-holonomic vehicles is essentially
finding a function ${\boldsymbol{\tau}}(t)$ that maps a time $t$ to a specific
configuration $(x,y,\theta,\kappa)$.

### Trajectory Planning in Frenet frame

Our method adopts a similar framework as in [12], which utilizes the concept
of Frenet frame for trajectory planning (see Fig. 1). Given a smooth driving
guide line, a Frenet frame decouples the vehicle motions in Cartesian space
into two independent 1D movements, longitudinal movement that moves along the
guide line and lateral movement that moves orthogonally to the guide line.
Thus, a trajectory planning problem in Cartesian space is transformed to two
lower dimensional and independent planning problems in Frenet frame. This
framework exploits the task domain that most vehicles are moving along the
lane, and it is particularly advantageous as it greatly simplifies problem by
reducing the dimensionality of planning.

Figure 1: Illustration of vehicle trajectory planning in assist of Frenet
frame. First, the vehicle dynamic state $(x,y,\theta,\kappa,v,a)$, which
represents vehicles position, heading, steering angle, velocity and
acceleration, respective, is projected on to a given driving guide line to
obtain its decoupled states in Frenet frame. $(s,\dot{s},\ddot{s})$ represents
the vehicle state, i.e., position, velocity and acceleration, along the guide
line (i.e., longitudinal state) and $(d,\dot{d},\ddot{d})$ represents the
vehicle state, i.e., position, velocity and acceleration, perpendicular to the
guild line (i.e., lateral state). Then, plan longitudinal and lateral motions
independently. Finally, longitudinal and lateral motions in Frenet frame are
combined and transformed to a trajectory in Cartesian space.

We assume that the autonomous vehicle is roughly driving around the guild
line. The main task for in lane driving is to generate a trajectory for the
autonomous vehicle driving along the guide line. In this paper, we assume the
vehicle will stay close to the guide line and possible lateral deviations to
the guide line can be corrected by the controller. Thus, lateral state of the
vehicle is always zero. The trajectory planning problem in our work is now
reduced to finding a function $\boldsymbol{s}(t)$, where $s$ is the
longitudinal coordinate along the guide line. For any given time $t$,
$\boldsymbol{s}(t)$ returns a vehicle longitudinal state
$(s,\dot{s},\ddot{s})$ at time $t$. $\boldsymbol{s}(t)$ along with a zero
function $\boldsymbol{d}(t)$ forms a trajectory in Cartesian space.

##  IV Phase I: Smooth Driving Guide Line Generation

A guide line is the prerequisite for planning in Frenet frame. The smoothness
of a guide line is critical to generating high quality trajectories as the
vehicle’s velocity, acceleration, heading and steering information are
implicitly encoded in the guide line. According to Cartesian-Frenet frame
conversions (see [12] for details), to obtain continuous acceleration and
steering angles, the derivative of curvature of the guide line must be
continuous as well.

Generally, the guide line is obtained from map in the form of a sequence of
coordinates in map frame, i.e, $(x_{0},y_{0}),\ldots,(x_{n-1},y_{n-1})$,
without having the necessary geometrical information, such as curve tangent
angle . Before the guide line can be used, a smoothing phase that assigns the
necessary geometrical information is needed. In our implementation, we use a
non-linear optimization procedure for guide line smoothing as optimization
provides direct control of optimality and constraint satisfactions.

To formulate an optimization for guide line smoothing, we consider the
following aspects:

  1. 1.

Objective Minimal wiggling of geometrical properties. The wiggling of the
geometrical properties will lead to unsmooth acceleration and wiggling of
vehicle steering. The objective of the optimization is designed to minimize
the length of the guide line $s$, curvature $\kappa$ and curvature derivative
$\dot{\kappa}$ (i.e., $d{\kappa}/ds$).

  2. 2.

Line Representation The representation of driving guide line is flexible
enough for complex road shapes. We choose a discrete-continuous hybridyzation
for the guide line representation: the input points in Cartesian space work as
”knots” and close-form curves connect consecutive input points with continuous
geometrical properties at the joint points. For a raw guide line with $n$
input points, $n-1$ pieces of curves are used.

  3. 3.

Constraints The resulted guide line do not necessarily need to pass through
input points as the Cartesian coordinates might have errors from map
generation; however, the deviations to input points must be limited within
certain threshold to preserve the original shape. This requirement is
formulated as constraints in optimization.

In our implementation, we are inspired by [2] to use polynomial spiral curve
as piecewise baseis. Spiral curve, which represents its shape using a function
of curve tangent angle $\theta$ w.r.t. accumulated curve length $s$, is the
key element in guide line smoothing. The advantage of using spiral curves is
the geometric properties, such as curve direction $\theta$, curvature $\kappa$
($d\theta/ds$) and curvature change rate $\dot{\kappa}$ ($d\theta^{2}/ds^{2}$)
can be easily derived by just taking the derivative of the function
$\boldsymbol{\theta}(s)$ w.r.t. $s$ directly. Compared to other curve
formulations, such as parametric curves in Cartesian space, the objective
function can be greatly simplified.

In the guide line smoothing problem, we use quintic polynomial spiral curves
to connect consecutive input points. The following are the variables in the
optimization where $\theta_{i}$, $\dot{\theta}_{i}$ and $\ddot{\theta}$
represent curve tangent angle, curvature and curvature change rate for some
input point $i$ and $\Delta s_{i}$ is the length of the spiral curve that
connects point $i$ and $i+1$:

The geometrical property variables $\theta_{i}$, $\dot{\theta}_{i}$,
$\ddot{\theta}_{i}$, $\theta_{i+1}$, $\dot{\theta}_{i+1}$,
$\ddot{\theta}_{i+1}$ and the curve length variable $\Delta s_{i}$ uniquely
determines the coefficients $c_{j}$ of a quintic polynomial:

$\displaystyle\boldsymbol{\theta}_{i}(s)=\sum_{j=0}^{5}c_{j}*s^{j}$

The objective function for optimization is approximated by evaluating a
predefined $m$ equal spacing internal points for each piecewise spiral curve.
The optimization procedure finds the optimal values for variables $\theta$,
$\dot{\theta}$, $\ddot{\theta}$ and $\Delta s$ that minimizes the objective
function. The result of guide line optimization is a sequence of quintic
spiral curves that are smoothly connected at the input points. By taking the
derivative w.r.t. $s$, we are able to obtain a sequence of smooth quartic
polynomials that represent curvature of the guide line, where curvature and
curvature derivative info are smoothly connected at the input points.

$\displaystyle\boldsymbol{\kappa}_{i}(s)=\sum_{j=1}^{5}j*c_{j}*s^{j-1}$

Commonly, the guide line is finely discretized to certain resolution for
trajectory generation. However, keeping the piecewise close-form of curvature
representation is the key to Phase II.

|  |
---|---|---
Figure 2: An example of guide line smoothing. The first figure shows the guide
line in Cartesian space, which describes a common U-turn scenario with turning
radius 10 $m$. The input is a sequence of discretized points (in yellow) and
the output (in green) is a sequence of spiral paths that connect the input
points. The input points are deliberately perturbed with random noise within
0.1 $m$. The second figure shows the tangent direction of the optimized guide
line and the third figure shows the curvature.

##  V Phase II: Trajectory Generation

###  V-A Optimality Modeling

The goal of trajectory generation for autonomous vehicles is to compute a
trajectory that drives the passengers to the destination safely and
comfortably. The following are key factors that are commonly used to measure
the quality of a trajectory:

####  V-A1 Task achievement

The most important application of autonomous driving is letting the vehicle
transport the passenger to a predefined destination. For in-lane driving
scenarios, basically there are two tasks:

  * •

Cruise The vehicle reaches a target cruise speed. When a front obstacle with
lower speed exists, the vehicle maintains safe distance to the front obstacle.

  * •

Stop The vehicle stops at a certain point. When the vehicle reaches a
predefined destination, or an intermediate target, e.g., a red light or stop
sign, etc, it proceeds with a full stop.

The task achievement can be evaluated by measuring the difference between task
specific target state and vehicle’s state at the end of trajectory.

####  V-A2 Safety

We limit the application of proposed algorithm for in-lane driving scenarios,
i.e., driving along a predetermined guide line. To avoid collisions with
obstacles in the environment, we use the concept of path-time-obstacle graph.
The path-time decomposition was firstly introduced by Kant and Zucker [4] to
tackle the problem of dynamic obstacle avoidance along a given path under
velocity constraints. We assume the path (driving guide line) for ego vehicle
is pre-determined, and trajectories for nearby obstacles can be accurately
predicted. The essential idea of path-time-obstacle graph is computing which
time $t$ that which portion $s$ of the predetermined guide line is blocked by
obstacles (see Fig. 3). The output of the collision avoidance analysis is
allowable region(s) $[s_{min},s_{max}]$ for a given time $t$. If the ego
vehicle at time $t$ stays within the allowable regions, collision to obstacles
is avoided. In complex cases, it is possible that the allowable regions for a
given time $t$ are not unique. In our work, simple heuristics is used to
uniquely determine a region by considering the dynamics of the vehicle,
however, a formal situation reasoning module with more advanced techniques can
surely provide better decisions. The result of reasoning can be abstracted as
a function $\boldsymbol{s}_{free}(t)$ that returns a region
$(s_{min},s_{max})$ given any time $t$. A safety margin can also be added by
increasing $s_{min}$ or decreasing $s_{max}$ for the autonomous driving
vehicle to keep certain distance to front obstacle.

Figure 3: Path-time-obstacle graph for one driving scenario. Left: Scenario
illustration. Ego vehicle (in green) drives along the center of the lane while
obstacle vehicle (in red) on adjacent lane tries to change to the left lane.
Right: Path-time-obstacle graph. The s axis represents the accumulated length
of the center lane of ego vehicle; the t axis represents time. The path-time-
obstacle (approximated) is shown in red which it represents at certain time t,
which part of the center lane would be blocked by the obstacle, considering
the geometry of the obstacle vehicle. Two quadratic lines represents the
boundaries of reachable portions on the center lane by considering the
dynamical limits, e.g., velocity and acceleration bounds, of the ego vehicle.

####  V-A3 Comfort

Comfort is an important metric of trajectory quality. In our formulation, the
comfort is modeled using the following factors:

  * •

Longitudinal acceleration: minimization of longitudinal acceleration to reduce
frequent throttle or brake input.

  * •

Longitudinal acceleration change rate (jerk): minimization of jerk in
longitudinal direction, i.e., minimization of input changes of throttle or
brakes.

  * •

Centripetal acceleration: minimization of centripetal acceleration along the
trajectory. When the vehicle approaches a curve, it must decelerate gracefully
to reduce the centripetal acceleration resulted from the curve.

  * •

Time: for accomplishing certain task, e.g., reaching a target velocity, the
time is minimized.

###  V-B Constraints

As our algorithm is intended for vehicle driving in structured environment, we
assume the vehicle is always moving forward monotonically. Based on vehicle’s
dynamical properties, the following constraints must be satisfied at any time
$t$ of the trajectory with time range $t_{\tau}$ to achieve safety and
comfort:

  * •

Longitudinal velocity bounds
$\boldsymbol{\dot{s}}(t)\in[0,\dot{s}_{max}]$

  * •

Longitudinal acceleration bounds
$\boldsymbol{\ddot{s}}(t)\in[\ddot{s}_{min},\ddot{s}_{max}]$

  * •

Longitudinal jerk bounds
$\boldsymbol{\dddot{s}}(t)\in[\dddot{s}_{min},\dddot{s}_{max}]$

  * •

Centripetal acceleration bounds
$\boldsymbol{a}_{\boldsymbol{c}}(t)\in[-\dot{a}_{c_{max}},\dot{a}_{c_{max}}]$

Besides dynamical constraints, to achieve collision avoidance, the spatial
value $s$ for any given time $t$ must lie within the allowable regions given
by $\boldsymbol{s}_{free}(t)$:

  * •

Safety bounds
$\boldsymbol{s}(t)\in\boldsymbol{s}_{free}(t)$

###  V-C Trajectory Formulation and Discretization

To effectively compute an optimal trajectory while evaluating constraint
satisfaction in practice, a common approach is discretizing the trajectory
$\boldsymbol{s}(t)$ according to a certain parameter. The objective function
is then approximated by evaluating these discretized points, and constraint
satisfaction is checked on these points as well.

Depending on the parameter we use for trajectory discretization, the
formulation of optimization, including objective function, constraint
formulation, can be quite differently. In this section, we discuss two choices
of parameters for discretization and their pros and cons. Despite difference
on choice of parameters for discretization, both methods discretize the
trajectory to second-order derivative of $s$, i.e., $\ddot{s}$ to achieve
accurate controlling to the acceleration level, and assume a constant third-
order term $\dddot{s}$ (i.e., jerk) connects consecutive discretized points.

####  V-C1 Spatial Parameter Discretization

The first choice is discretizing the trajectory using spatial parameter $s$ to
a predefined resolution $\Delta s$. The resulting trajectory is represented by
the following variables, assuming the starting point with $s=0$:

In this formulation, between consecutive discretized point is an equal spatial
distance $\Delta s$. The optimization variables include the velocity
$\dot{s}$, acceleration $\ddot{s}$ at each point and the time intervals
$\Delta t$ between consecutive points. As we have discussed in previous
section, the curvature of the guide line $\boldsymbol{\kappa}$ is a function
of spatial parameter $s$.

The major advantage of spatial parameter discretization is the spatial value
$s$ for each discretized point is fixed, thus the curvature. Therefore, the
speed upper limit resulted from the centripetal acceleration constraint can be
precomputed and remains fixed throughout the optimization. However, there are
several drawbacks with this formulation:

  * •

Difficult objective function for optimization. For one term in optimality
modeling, longitudinal jerk minimization, the jerk is computed using the
differencing between consecutive points. In this formulation, there would be a
division term between optimization variables in objective function, which
leads to a difficult non-convex optimization problem.

  * •

Difficult to enforce safety bound constraint. For path-time-obstacle analysis,
the output is a function $\boldsymbol{s}_{free}(t)$ that maps a time $t$ to a
safe region $(s_{min},s_{max})$. In this formulation, as the time $t$ is a
variable, the safe region for one point changes as time $t$ changes.

Because of these issues, despite the formulation of centripetal acceleration
constraint is simplified, it is not a good choice to discretize the trajectory
using spatial parameter.

####  V-C2 Temporal Parameter Discretization

In the contrast, we propose temporal parameter discretization, which
discretizes the trajectory using time $t$ to a given resolution $\Delta t$.
The resulting trajectory is represented by the following variables, assuming
the starting point with $t=0$:

In this formulation, the optimization variables include the spatial parameter
$s$, velocity $\dot{s}$ and acceleration $\ddot{s}$ at each discretized point.
Compared to spatial-space discretization, this formulation avoids the
divisional problem between variables for computing the longitudinal jerk term.
Also, it is easier to incorporate safety bound constraint as safety bound as
the safety bound remains fixed for each point throughout the optimization.

A major challenge with temporal parameter discretization is the difficulty to
consider the constraints and objectives involving centripetal acceleration, in
contrast to spatial parameter discretization. Centripetal acceleration at one
point is decided by two factors: the velocity $\dot{s}$, and the curvature
$\kappa$. Since $\kappa$ is associated with spatial parameter $s$, as $s$
changes iteratively in the optimization procedure, the curvature $\kappa$
changes correspondingly. In other words, the velocity limit for one
discretized point is now a function involving $\boldsymbol{\kappa}$(s).
Assuming the maximal allowed centripetal acceleration is a fixed value
${a_{c}}_{max}$, the constraint for centripetal acceleration limit is as
follows:

$\displaystyle-{a_{c}}_{max}\leq\dot{s}^{2}*\boldsymbol{\kappa}(s)\leq{a_{c}}_{max}$

In order to apply the constraint to an optimization procedure, the term
$\dot{s}^{2}*\boldsymbol{\kappa}(s)$ must be differentiable. One of our major
contributions is using a sequence of close-form spiral paths directly as the
representation of guide line and thus making the term differentiable.

Another difficulty of temporal parameter discretization is modeling the
preference of minimal time for task accomplishment. To model the preference,
we introduce a reference velocity term in the objective formulation. The
reference velocity models the preferred velocity without considering the
obstacle and curves. The integral of difference between current velocity and
reference velocity is included in the objective function. This term encourages
the vehicle to reach the reference velocity with minimal time spent. In next
section, we discuss the detailed optimization formulation using temporal
parameter discretization.

###  V-D Complete Optimization Formulation

Following the discussion at V-A, suppose a trajectory $\boldsymbol{s}(t)$ is
parameterized by time $t$ with maximal time length $t_{\tau}]$, the objective
function is designed as follows:

$\displaystyle\boldsymbol{f}$
$\displaystyle=w_{\ddot{s}}*\int_{0}^{t_{\tau}}\boldsymbol{\ddot{s}}(t)^{2}dt$
(1)
$\displaystyle+w_{\dddot{s}}*\int_{0}^{t_{\tau}}\boldsymbol{\dddot{s}}(t)^{2}dt$
(2)
$\displaystyle+\,w_{a_{c}}*\int_{0}^{t_{\tau}}\boldsymbol{\dot{s}}(t)^{2}*\boldsymbol{\kappa}(\boldsymbol{s}(t))dt$
(3)
$\displaystyle+\,w_{\dot{s}_{ref}}*\int_{0}^{t_{\tau}}(\boldsymbol{\dot{s}}(t)-\dot{s}_{ref})^{2}dt$
(4) $\displaystyle+\,w_{s_{task}}*(\boldsymbol{s}(t_{\tau})-s_{task})^{2}$ (5)
$\displaystyle+\,w_{\dot{s}_{task}}*(\boldsymbol{\dot{s}}(t_{\tau})-\dot{s}_{task})^{2}$
(6)
$\displaystyle+\,w_{\ddot{s}_{task}}*(\boldsymbol{\ddot{s}}(t_{\tau})-\ddot{s}_{task})^{2}$
(7)

where $\dot{s}$, $\ddot{s}$ are the linear velocity and acceleration
respectively. $\boldsymbol{\kappa}$ is a function that takes a spatial
parameter $s$ as input and outputs the curvature $\kappa$ at the given point.
Term 1-3 directly model the longitudinal acceleration, jerk and centripetal
acceleration respectively. Term 4 implicitly models the minimization of time
for accomplishing certain task. This term encourages the trajectory quickly
reach a reference speed $\dot{s}_{ref}$. Term 5-7 are used to model the task
preference, which encourage the vehicle to reach certain predefined state by
the end of trajectory.

As we discretize the trajectory using temporal parameter, the objective
function can be approximated by evaluating the $n$ discretized points.

$\displaystyle\boldsymbol{\tilde{f}}$
$\displaystyle=w_{\ddot{s}}*\sum_{i=0}^{n-1}\ddot{s}_{i}^{2}$
$\displaystyle+\,w_{\dddot{s}}*\sum_{i=0}^{n-2}\dddot{s}_{i\rightarrow
i+1}^{2}$
$\displaystyle+\,w_{a_{c}}*\sum_{i=0}^{n-1}\dot{s}_{i}^{2}*\boldsymbol{\kappa}(s_{i})$
$\displaystyle+\,w_{\dot{s}_{ref}}*\sum_{i=0}^{n-1}(\dot{s}_{i}-\dot{s}_{ref})^{2}$
$\displaystyle+\,w_{s_{task}}*(s_{n-1}-s_{task})^{2}$
$\displaystyle+\,w_{\dot{s}_{task}}*(\dot{s}_{n-1}-\dot{s}_{task})^{2}$
$\displaystyle+\,w_{\ddot{s}_{task}}*(\ddot{s}_{n-1}-\ddot{s}_{task})^{2}$

As discussed in V-C, a constant jerk term $\dddot{s}$ is used to connect
consecutive points. Its value can be computed by differencing the acceleration
terms:

$\displaystyle\dddot{s}_{i\rightarrow
i+1}=\frac{\ddot{s}_{i+1}-\ddot{s}_{i}}{\Delta t}$

Constraint checking is performed on these discretized points as well: $\forall
i\in\mathbb{Z},i\in[0,n-1]$,

$\displaystyle s_{i}$ $\displaystyle\in\boldsymbol{s}_{free}(i*\Delta t)$
$\displaystyle\dot{s}_{i}$ $\displaystyle\in[0,\dot{s}_{max}]$
$\displaystyle\ddot{s}_{i}$ $\displaystyle\in[\ddot{s}_{min},\ddot{s}_{max}]$
$\displaystyle\dddot{s}_{i\rightarrow i+1}$
$\displaystyle\in[\dddot{s}_{min},\dddot{s}_{max}]$ $\displaystyle a_{c_{i}}$
$\displaystyle\in[-a_{c_{max}},a_{c_{max}}],\,a_{c_{i}}=\dot{s}_{i}^{2}*\boldsymbol{\kappa}(s_{i})$

Nevertheless, to maintain the continuity of the piecewise constant-jerk
trajectory, the following equality equations must be satisfied between
consecutive points:

$\displaystyle\ddot{s}_{i+1}$ $\displaystyle=\ddot{s}_{i}+\int_{0}^{\Delta
t}\dddot{s}_{i}dt$ $\displaystyle=\ddot{s}_{i}+\dddot{s}_{i}*\Delta{t}$
$\displaystyle\dot{s}_{i+1}$ $\displaystyle=\dot{s}_{i}+\int_{0}^{\Delta
t}\ddot{s}_{i+1}dt$
$\displaystyle=\dot{s}_{i}+\ddot{s}_{i}*\Delta{t}+\frac{1}{2}*\dddot{s}_{i}*\Delta{t}^{2}$
$\displaystyle s_{i+1}$ $\displaystyle=s_{i}+\int_{0}^{\Delta t}\dot{s}_{i}dt$
$\displaystyle=s_{i}+\dot{s}_{i}*\Delta{t}+\frac{1}{2}*\ddot{s}_{i}*\Delta{t}^{2}+\frac{1}{6}*\dddot{s}_{i\rightarrow
i+1}*\Delta{t}^{3}$

|  |  |
---|---|---|---
|  |  |
|  |  |
|  |  |
Figure 4: Trajectory optimization result for U-turn scenario. The vehicle
starts at $s_{init}=0$, $\dot{s}_{init}=15m/s$, $\ddot{s}_{init}=0m/s^{2}$
with target cruise velocity 20 $m/s$. First two rows: trajectory optimization
results for cruise task using two sets of parameters, one comfortable and one
for sporty driving behavior. In order to show a complete u-turn, different
trajectory total time are used. The first column shows the accumulated
distance versus time. The comfort trajectory has 18 $s$ time length with
121.83 $m$ spatial length, and the sporty trajectory has 15 $s$ and 128.04
$m$. The second column shows the optimized velocity (in blue) and velocity
bounds (in red). The velocity lower bound is 0 $m/s$ and upper bound is
computed by considering the speed limit (30 $m/s$), curvature of the guild
line and maximal centripetal acceleration (2 $m/s^{2}$). The third column
shows the optimized acceleration (in blue) and predefined acceleration bounds
(in red, 2 $m/s^{2}$ for accelerating and -4 $m/s^{2}$ for braking). For
sporty trajectory, the optimized acceleration hits acceleration boundaries to
maximize the distance traveled while the comfortable trajectory brakes early
to reduce resulted centripetal acceleration and accelerate gracefully to reach
the target velocity. Third row: trajectory optimization for stop task. The
vehicle starts from $s=0$ and has a predefined full stop point at $s=130$. The
end state of the trajectory has 0 velocity and acceleration. Fourth row:
trajectory optimization result for cruise task with a low speed vehicle (3
$m/s$) in the front for 10 $s$. The ego vehicles slows down and maintains a
predefined safety buffer (5 $m$).

##  VI Implementation and Experiments

The proposed two-step optimization are implemented using non-linear
optimization package Interior Point OPTimizer (IPOPT) [11]. The source code is
planned to be released as part of Baidu Apollo Open Source Platform [1].

All experiments are carried out on an Intel Xeon 2.6GHz PC with 32GB RAM. We
use a synthetic 108°U-turn scenario with turning radius roughly 10 meters
($m$), which is common for urban driving, for testing. In guide line smoothing
phase, the optimization for this 17-point 150 $m$ guide line takes 948
millisecond $ms$. The input points are randomly perturbed within radius 0.05
$m$. The maximal allowed deviation is set to 0.1 $m$. Fig. 2 shows the
geometrical properties of the smoothed guide line.

The testings on trajectory optimization phase are carried out on this U-turn
scenario. The vehicle starts with an initial speed of 15 $m/s$ and the
reference speed is set to 20 $m/s$. The following tables shows the vehicle’s
dynamical limits we set in the experiments:

| min. | max.
---|---|---
$\dot{s}$ ($m/s$) | 0 | 30
$\ddot{s}$ ($m/s^{2}$) | -4 | 2
$\dddot{s}$ ($m/s^{3}$) | -4 | 4
$a_{c}$ ($m/s^{2}$) | -2 | 2

The trajectory is discretized by 0.1 second ($s$). The computation time is
strongly affected by the number of discretized point, the number of
constraints (e.g., whether there is a preferred task state or there are
obstacles exist). Our experiments show the optimization time for optimizing an
18-second trajectory ranging from 76 $ms$ to 617 $ms$ with an average of 259
$ms$. Fig. 4 shows the optimization results with different driving behaviors
in cruise task, stop task and cruise task with a lead vehicle.

##  VII Conclusion and Future work

We present a new non-linear optimization based trajectory generation method
for in-lane driving scenarios. This method consists of two-step optimizations
with one step computing a smooth driving guide line and the next step
computing a safe and comfortable trajectory along the guide line. The
experiments show the algorithm can generate jerk minimal and bounded
trajectory under centripetal acceleration constraint.

For future work, we intend to expand the algorithm to tackle multi-lane
driving scenarios. There are two possible directions for the expansion, both
use the strategy that path planning deals with static obstacles while speed
planning deals with dynamic obstacles.

In the first direction, the guide line can be dynamically adjusted to take
static obstacle avoidance into consideration. The guide line generation
essentially becomes a path planning problem for static obstacle avoidance. The
advantage of this direction is the rest of the algorithm can remain unchanged.
However, the computation for smoothing the guide line is costly and adjustment
of the guide line online may not be feasible for fast planning cycles.

Another direction is using optimization to generate the lateral
trajectory/path $\boldsymbol{d}(s)$ that directly considers the projected
static obstacles onto the Frenet frame. This direction is more consistent with
the framework in Frenet frame planning. The benefit is the smooth guide line
can be generated and stored offline and be loaded dynamically for online uses.
Also, lane change actions will be handled more cleanly as lane changing can be
planned by simply substituting the guide line.

## References

  * [1] Baidu apollo project.  http://apollo.auto/.
  * [2] Shilpa Gulati, Chetan Jhurani, and Benjamin Kuipers.  A nonlinear constrained optimization framework for comfortable and customizable motion planning of nonholonomic mobile robots-part i.  arXiv preprint arXiv:1305.5024, 2013.
  * [3] Jeong hwan Jeon, Sertac Karaman, and Emilio Frazzoli.  Anytime computation of time-optimal off-road vehicle maneuvers using the rrt.  In Decision and Control and European Control Conference (CDC-ECC), 2011 50th IEEE Conference on, pages 3276–3282. IEEE, 2011.
  * [4] Kamal Kant and Steven W Zucker.  Toward efficient trajectory planning: The path-velocity decomposition.  The international journal of robotics research, 5(3):72–89, 1986\.
  * [5] Yoshiaki Kuwata, Justin Teo, Gaston Fiore, Sertac Karaman, Emilio Frazzoli, and Jonathan P How.  Real-time motion planning with applications to autonomous urban driving.  IEEE Transactions on Control Systems Technology, 17(5):1105–1118, 2009.
  * [6] Steven M LaValle and James J Kuffner Jr.  Randomized kinodynamic planning.  The international journal of robotics research, 20(5):378–400, 2001\.
  * [7] J. Levinson, J. Askeland, J. Becker, J. Dolson, D. Held, S. Kammel, J. Z. Kolter, D. Langer, O. Pink, V. Pratt, M. Sokolsky, G. Stanek, D. Stavens, A. Teichman, M. Werling, and S. Thrun.  Towards fully autonomous driving: Systems and algorithms.  In 2011 IEEE Intelligent Vehicles Symposium (IV), pages 163–168, June 2011.
  * [8] Isaac Miller, Mark Campbell, Dan Huttenlocher, Frank-Robert Kline, Aaron Nathan, Sergei Lupashin, Jason Catlin, Brian Schimpf, Pete Moran, Noah Zych, et al.  Team cornell’s skynet: Robust perception and planning in an urban environment.  Journal of Field Robotics, 25(8):493–527, 2008.
  * [9] Julian Schlechtriemen, Kim Peter Wabersich, and Klaus-Dieter Kuhnert.  Wiggling through complex traffic: Planning trajectories constrained by predictions.  In Intelligent Vehicles Symposium (IV), 2016 IEEE, pages 1293–1300. IEEE, 2016.
  * [10] Chris Urmson, Joshua Anhalt, Drew Bagnell, Christopher Baker, Robert Bittner, MN Clark, John Dolan, Dave Duggins, Tugrul Galatali, Chris Geyer, et al.  Autonomous driving in urban environments: Boss and the urban challenge.  Journal of Field Robotics, 25(8):425–466, 2008.
  * [11] Andreas Wächter and Lorenz T Biegler.  On the implementation of an interior-point filter line-search algorithm for large-scale nonlinear programming.  Mathematical programming, 106(1):25–57, 2006.
  * [12] Moritz Werling, Julius Ziegler, Sören Kammel, and Sebastian Thrun.  Optimal trajectory generation for dynamic street scenarios in a frenet frame.  In Robotics and Automation (ICRA), 2010 IEEE International Conference on, pages 987–993. IEEE, 2010.
  * [13] Julius Ziegler, Philipp Bender, Markus Schreiber, Henning Lategahn, Tobias Strauss, Christoph Stiller, Thao Dang, Uwe Franke, Nils Appenrodt, Christoph Gustav Keller, et al.  Making bertha drive-an autonomous journey on a historic route.  IEEE Intell. Transport. Syst. Mag., 6(2):8–20, 2014.


# Conservation laws of the Haldane-Shastry type spin chains

Junpeng Cao  Beijing National Laboratory for Condensed Matter Physics,
Institute of Physics, Chinese Academy of Sciences, Beijing 100190, People's
Republic of China  Peng He  Beijing National Laboratory for Condensed Matter
Physics, Institute of Physics, Chinese Academy of Sciences, Beijing 100190,
People's Republic of China  Yuzhu Jiang  Beijing National Laboratory for
Condensed Matter Physics, Institute of Physics, Chinese Academy of Sciences,
Beijing 100190, People's Republic of China  Yupeng Wang∗ Beijing National
Laboratory for Condensed Matter Physics, Institute of Physics, Chinese Academy
of Sciences, Beijing 100190, People's Republic of China

###### Abstract

A systematic method to construct the complete set of conserved quantities of
the Haldane-Shastry type spin chains is proposed. The hidden relationship
between the Yang-Baxter relation and the conservation laws of the long-range
interacting integrable models is exposed explicitly. An integrable anisotropic
Haldane-Shastry model is also constructed.

###### pacs:

02.30.Ik, 75.10.Jm

A typical characteristic of the integrable models is that each of them
possesses a complete set of conservation laws. For an integrable system with a
finite number of degrees of freedom, the number of linearly independent
conserved quantities is exactly the same as that of the degrees of freedom,
while for a continuous integrable model, there is an infinite number of
conserved quantities. It is well known that the conservation laws of the
integrable models with short-range interactions are tightly related to the
Yang-Baxter relation. The conserved quantities can be obtained from the
derivatives of the transfer matrix of the system tak ; bax . On the other
hand, there is another class of integrable models with $r^{-2}$ type
interaction potentials which are called as the Calogero-Sutherland (CS) model
cs  in the continuous case and the Haldane-Shastry (HS) model hs-1 ; hs-2  in
the lattice case. These models belong to the long-range interacting ones and
have many applications in the fields of two-dimensional fractional quantum
Hall effect and fractional statistics st . Because of the importance, these
models have been studied extensively hs2 ; h21 ; h12 ; h2 ; s2 ; hs3 ; hs4 ;
hs5 ; hs6 ; hs7 ; hs8 . Several people have tried to construct the
conservation laws of these models. For example, by using the Dunkl operators
dun , Polychronakos pol1  constructed the invariants of motion of the CS
continuous model. Nevertheless, the demonstration of the integrability of the
HS Lattice model is still a challenge problem. Borrowed Polychronakos's idea,
Fowler and Minahan fow  proposed a set of conserved quantities for the HS
model. However, there are still some debates cyb ; pol2  on this construction
because the HS Hamiltonian appears in the third level of invariants, and
should act on some magnon states to erase the unwanted terms.

The main difficulty of the demonstration of the complete integrability of HS
type models is lack of a systematic method to construct the complete set of
conservation laws. Recalling the case of nearest neighbor interacting
integrable models, an interesting question may arise: Is there any intrinsic
relationship between the HS model and the Yang-Baxter relation cyb ? In this
Letter, we expose this intrinsic relationship exactly and develop a systematic
method to construct the complete set of conservation laws of HS model. This
provides us not only a deep understanding to this important model but also a
general method to construct other integrable models with long-range couplings.

Our starting point is the following Lax operator

$\displaystyle L_{0j}(u)=1+\frac{\eta}{u}{\bf\sigma}_{0}\cdot{\bf S}_{j},$ (1)

where $u$ is the spectral parameter; $\eta$ is the crossing parameter;
${\bf\sigma}_{0}$ is the auxiliary Pauli matrix and ${\bf S}_{j}$ is the
spin-$1/2$ operator on site $j$. It is well known that the integrability of
the Heisenberg spin chain model is related to the monodromy matrix
$T_{0}(u)=L_{01}(u)\cdots L_{0N}(u)$ which satisfies the Yang-Baxter relation

$L_{12}(u_{1}-u_{2})T_{1}(u_{1})T_{2}(u_{2})=T_{2}(u_{2})T_{1}(u_{1})L_{12}(u_{1}-u_{2}).$
(2)

Define the transfer matrix $t(u)=tr_{0}T_{0}(u)$. From Eq.(2), one can prove
that the transfer matrices with different spectral parameters are mutually
commutative, i.e., $[t(u),t(v)]=0$. Therefore, $t(u)$ serves as the generating
function of the conserved quantities of the corresponding system. The first
order derivative of logarithm of the transfer matrix gives the Hamiltonian of
the Heisenberg spin chain

$\displaystyle H_{H}=\frac{1}{2\eta}\left.\frac{\partial}{\partial u}\ln
t(u)\right|_{u=\frac{\eta}{2}}+(\frac{1}{\eta^{2}}-\frac{1}{4})N=\sum_{j=1}^{N}{\bf
S}_{j}\cdot{\bf S}_{j+1}.$ (3)

In fact, the inhomogeneous Lax operator $L_{0j}(u-\delta_{j})$ with a site-
dependent shift $\delta_{j}$ to the spectral parameter $u$ and the
inhomogeneous transfer matrix $\tilde{T}_{0}(u)\equiv
L_{01}(u-\delta_{1})\cdots L_{0N}(u-\delta_{N})$ also satisfy the Yang-Baxter
relation Eq.(2). Consider the classical expansion of the Lax operator
$L_{0j}(u-\delta_{j})=1+\eta{\cal L}_{0j}(u-\delta_{j})$ and define the
classical monodromy matrix ${\cal T}_{0}(u)=\sum_{j=1}^{N}{\cal
L}_{0j}(u-\delta_{j})$. We find that they satisfy the following classical
Yang-Baxter relation skly

$[{\cal T}_{1}(u_{1}),{\cal T}_{2}(u_{2})]=[{\cal T}_{1}(u_{1})+{\cal
T}_{2}(u_{2}),{\cal L}_{12}(u_{1}-u_{2})].$ (4)

The Eq.(4) ensures that the functional $\tau(u)\equiv tr_{0}{{\cal
T}_{0}}^{2}(u)/4$ with different spectral parameters are mutually commutative,
i.e., $[{\tau}(u),{\tau}(v)]=0$. Therefore, ${\tau}(u)$ can be treated as the
generating functional of a series of conserved quantities which can be written
out explicitly as

${\tau}(u)=\sum_{j=1}^{N}\frac{3}{8(u-\delta_{j})^{2}}+\sum_{j=1}^{N}\frac{h_{j}}{u-\delta_{j}},$
(5)

where

$\displaystyle h_{j}=\sum_{l=1,\neq j}^{N}\frac{1}{\delta_{j}-\delta_{l}}{\bf
S}_{j}\cdot{\bf S}_{l}.$ (6)

The operators $h_{j}$ are nothing but the Gaudin operators gau  associated
with the Heisenberg spin chain. It is easy to prove that the Gaudin operators
commute with each other, i.e., $[h_{j},h_{k}]=0$. This allows us to construct
the mutually commutative operators $I_{n}=\sum_{j=1}^{N}{h_{j}}^{n}$ for
arbitrary $n$. If we choose one of $I_{n}$ as the Hamiltonian, $\\{I_{n}\\}$
form a set of conserved quantities and the Hamiltonian describes an integrable
system. For a translational invariant lattice $\delta_{j}=j$ and $N\to\infty$,
we find

$\displaystyle H_{ISE}$ $\displaystyle=$
$\displaystyle\lim_{N\to\infty}\left[-\sum_{j=1}^{N}h_{j}^{2}+\frac{\pi^{2}}{16}N\right]$
(7) $\displaystyle=$
$\displaystyle{\sum_{l<j}}^{\prime}\frac{1}{(j-l)^{2}}{\bf S}_{j}\cdot{\bf
S}_{l}.$

$H_{ISE}$ is just the Hamiltonian of inverse square exchanging (ISE) model.
The prime in the summation means that $j$ and $l$ in the summation take values
from negative to positive infinity. Obviously, operators $h_{j}=\sum_{l\neq
j}^{\prime}(j-l)^{-1}{\bf S}_{j}\cdot{\bf S}_{l}$ and their arbitrary
combinations commute with the Hamiltonian (7) and form a set of the conserved
quantities. In addition, the model (7) has another set of conserved quantities
$h_{j}^{\prime}=\sum_{l\neq j}^{\prime}{\bf S}_{j}\cdot{\bf S}_{l}$ by simply
checking $[H_{S},h_{j}^{\prime}]=0$. We note that (7) with arbitrary
$\delta_{j}$ gives a disordered integrable system. Now it is clear that there
is an intrinsic relationship between the short-range coupling Heisenberg model
and the long-range coupling ISE model, i.e., they share the common Yang-Baxter
equation. This provides us a powerful method to construct new integrable
models with long-range interactions from the known solutions of the Yang-
Baxter equation or to obtain the conservation laws of the predicted integrable
models with $r^{-2}$ type potentials. For example, from the Lax operator of
the anisotropic XXZ Heisenberg spin chain tak  we have the following mutually
commutative Gaudin operators

$\displaystyle h_{j}=\sum_{l=1,\neq
j}^{N}\left[\frac{S_{j}^{x}S_{l}^{x}+S_{j}^{y}S_{l}^{y}}{\sin(\delta_{j}-\delta_{l})}+\cot(\delta_{j}-\delta_{l})S_{j}^{z}S_{l}^{z}\right].$
(8)

For the equally spaced $\delta_{j}=\pi j/N$, we obtain

$\displaystyle H_{AHS}$ $\displaystyle=$
$\displaystyle-\sum_{j=1}^{N}h_{j}^{2}-\frac{1}{4}\left(\sum_{j=1}^{N}S_{j}^{z}\right)^{2}+\frac{1}{16}N(N^{2}-N+1)$
(9) $\displaystyle=$
$\displaystyle\sum_{l<j}^{N}\frac{\cos\frac{\pi}{N}(j-l)(S_{j}^{x}S_{l}^{x}+S_{j}^{y}S_{l}^{y})+S_{j}^{z}S_{l}^{z}}{\sin^{2}\frac{\pi}{N}(j-l)}.$

Notice that in the anisotropic XXZ spin chain, the total spin is no longer a
good quantum number but $\sum_{l=1}^{N}S_{l}^{z}$ is indeed a conserved
quantity which commutes with the $h_{j}$ in Eq.(8) and the $H_{AHS}$ in
Eq.(9). Therefore, $H_{AHS}$ can be treated as the Hamiltonian of an
anisotropic HS model. In fact, the ISE Hamiltonian (7) is the limiting case of
the anisotropic HS model (9), i.e.,
$H_{ISE}=\lim_{N\to\infty}{\pi^{2}}/{N^{2}}H_{AHS}$. By putting $N\to\infty$
and $\delta_{m}=im$, where $i$ is the imaginary unit, we readily obtain the
hyperbolic version of this integrable Hamiltonian

$\displaystyle
H_{HAHS}={\sum_{l<j}}^{\prime}\frac{\cosh(j-l)(S_{j}^{x}S_{l}^{x}+S_{j}^{y}S_{l}^{y})+S_{j}^{z}S_{l}^{z}}{\sinh^{2}(j-l)}.$
(10)

Motivated by these findings, we introduce the following local operators

$\displaystyle h_{j}=\sum_{l=1,\neq j}^{N}f(\delta_{j}-\delta_{l}){\bf
S}_{j}\cdot{\bf S}_{l},$ (11)

and look for the solutions of $[h_{j},h_{k}]=0$, where
$f(\delta_{j}-\delta_{l})$ is a function to be determined. For simplicity, we
denote $f(\delta_{j}-\delta_{l})\equiv f_{jl}$. With the relation $[{\bf
S}_{j}\cdot{\bf S}_{l},{\bf S}_{j}\cdot{\bf S}_{k}]=i{\bf S}_{j}\cdot({\bf
S}_{l}\times{\bf S}_{k})$ for $l\neq j\neq k$, we obtain

$\displaystyle[h_{j},h_{k}]=i\sum_{l=1,\neq
j,k}^{N}(f_{jl}f_{kj}-f_{jl}f_{kl}+f_{jk}f_{kl}){\bf S}_{j}\cdot({\bf
S}_{l}\times{\bf S}_{k}).$ (12)

Therefore, the constraint for $[h_{j},h_{k}]=0$ is the solution of
$f_{jl}f_{kj}-f_{jl}f_{kl}+f_{jk}f_{kl}=0$. After some simple algebra, we find
three sets of solutions:

(i) The first solution is $f(x)=x^{-1}$. This solution just gives Eq.(6) and
thus the ISE Hamiltonian (7).

(ii) The second solution is $f(x)=\cot(x)\pm i$. The operators $h_{j}$ and
$h_{j}^{\dagger}$ take the forms

$\displaystyle h_{j}=\sum_{l=1,\neq
j}^{N}\left[\cot(\delta_{j}-\delta_{l})+i\right]{\bf S}_{j}\cdot{\bf S}_{l},$
$\displaystyle h_{j}^{\dagger}=\sum_{l=1,\neq
j}^{N}\left[\cot(\delta_{j}-\delta_{l})-i\right]{\bf S}_{j}\cdot{\bf S}_{l}.$
(13)

Both $\\{h_{j}\\}$ and $\\{h_{j}^{\dagger}\\}$ are not hermitian for real
$\delta_{j}$ but each of them form a set of mutually commutative operators,
though $h_{j}$ and $h_{k}^{\dagger}$ do not commute with each other,
$[h_{j},h_{k}^{{\dagger}}]=2\sum_{l=1,\neq
j,k}^{N}\left[\cot(\delta_{j}-\delta_{k})+i\right]{\bf S}_{j}\cdot({\bf
S}_{l}\times{\bf S}_{k})$. A key problem is to construct a hermitian
Hamiltonian from those non-hermitian operators. Fortunately, we find that
$I_{2}\equiv\sum_{j=1}^{N}h_{j}^{2}=\sum_{j=1}^{N}{h_{j}^{\dagger}}^{2}$ is a
hermitian operator. For $\delta_{j}=\pi j/N$, the HS Hamiltonianhs-1 ; hs-2
can be derived as

$\displaystyle H_{HS}$ $\displaystyle=$
$\displaystyle-\sum_{j=1}^{N}h_{j}^{2}+\frac{i}{2}(N-4)\sum_{j=1}^{N}h_{j}+\frac{1}{16}N(3N^{2}-6N-5)$
(14) $\displaystyle=$
$\displaystyle\sum_{j<l}^{N}\frac{1}{\sin^{2}\frac{\pi}{N}(j-l)}{\bf
S}_{j}\cdot{\bf S}_{l}.$

An obvious fact is that $[H_{HS},h_{j}]=[H_{HS},h_{j}^{\dagger}]=0$. We
readily have two independent sets of conserved hermitian quantities for
$H_{HS}$:

$\displaystyle{I_{j}}^{+}=\frac{1}{2}(h_{j}+h_{j}^{\dagger})=\sum_{l=1,\neq
j}^{N}\cot\frac{\pi}{N}(j-l){\bf S}_{j}\cdot{\bf S}_{l},$
$\displaystyle{I_{j}}^{-}=\frac{1}{2i}(h_{j}-h_{j}^{\dagger})=\sum_{l=1,\neq
j}^{N}{\bf S}_{j}\cdot{\bf S}_{l}.$ (15)

For the spin half system, we know that the number of degrees of freedom of
each site is two. The two linearly independent conserved quantities
$I_{j}^{\pm}$ clearly show that the HS Hamiltonian is completely integrable.

Actually, we can also define the classical operators ${\cal
L}_{0j}(u-\delta_{j})=[\cot(u-\delta_{j})+i]{\bf S}_{0}\cdot{\bf S}_{j}$ and
${\cal T}_{0}(u)=\sum_{j=1}^{N}{\cal L}_{0j}(u-\delta_{j})$ for this solution.
They satisfy the following deformed classical Yang-Baxter relation

$\displaystyle[{\cal T}_{1}(u),{\cal T}_{2}(v)]=[{\cal L}_{21}(v-u),{\cal
T}_{1}(u)]+[{\cal T}_{2}(v),{\cal L}_{12}(u-v)].$ (16)

Define a functional $\tau(u)=tr_{0}{\cal T}_{0}^{2}(u)$, which can be written
out explicitly as

$\displaystyle{\tau}(u)=\sum_{j=1}^{N}\left[\frac{3\cos
2(u-\delta_{j})}{8\sin^{2}(u-\delta_{j})}+\frac{3}{4}i\cot(u-\delta_{j})\right]$
$\displaystyle\qquad\quad+\sum_{j=1}^{N}\left[\cot(u-\delta_{j})+i\right]h_{j}.$
(17)

From the deformed Yang-Baxter relation (16), we can prove that the functional
$\tau(u)$ with different spectral parameters are mutually commutative and thus
can be treated as the generation functional of a integrable system. Obviously,
for $\delta_{j}=j\pi/N$, $[H_{HS},\tau(u)]=0$, implying that the conserved
quantities of the HS model can also be generated by $\tau(u)$.

(iii) The third solution is $f(x)=\coth(x)\pm 1$ and
$h_{j}^{\pm}=\sum_{l=1,\neq j}^{N}\left[\coth(\delta_{j}-\delta_{l})\pm
1\right]{\bf S}_{j}\cdot{\bf S}_{l}$. With the same procedure, we find that
the Inozemtsev Hamiltonian hs2

$\displaystyle H_{I}={\sum_{l<j}}^{\prime}\frac{1}{\sinh^{2}(j-l)}{\bf
S}_{j}\cdot{\bf S}_{l}$ (18)

can be easily derived from $\sum_{j}^{\prime}{h_{j}^{+}}^{2}$ or
$\sum_{j}^{\prime}{h_{j}^{-}}^{2}$ by taking $\delta_{j}=j$ and $N\to\infty$.
The operators $h_{j}^{\pm}=\sum_{l\neq j}^{\prime}\left[\coth(j-l)\pm
1\right]{\bf S}_{j}\cdot{\bf S}_{l}$ span the complete space of the conserved
hermitian quantities and the Inozemtsev model (18) is also completely
integrable.

Similarly, we can construct the conservation laws of the $SU(M)$-invariant HS
and Inozemtsev models. In these cases, the generating operators $h_{j}$ take
the form:

$\displaystyle h_{j}=\sum_{l=1,\neq j}^{N}f(\delta_{j}-\delta_{l})(P_{jl}-c),$
(19)

where $P_{ij}$ is the $SU(M)$ spin permutation operator and $c$ is a constant.
One can easily check that

$\displaystyle[h_{j},h_{k}]=\sum_{l=1,\neq
j,k}^{N}(f_{jl}f_{kj}-f_{jl}f_{kl}+f_{jk}f_{kl})P_{jl}(P_{kj}-P_{kl}).$ (20)

The constraint $[h_{j},h_{k}]=0$ gives the same solutions of $f(x)$ as those
in the (i) - (iii). The $SU(M)$ HS Hamiltonian can be constructed from the
linear combination of $\sum_{j=1}^{N}{I_{j}^{+}}^{2}$ and
$\sum_{j=1}^{N}I_{j}^{+}$, whose explicit form reads

$\displaystyle
H_{SU(M)}=\sum_{l<j}^{N}\frac{P_{jl}}{\sin^{2}\frac{\pi}{N}(j-l)}.$ (21)

In conclusion, we establish the intrinsic relationship between the inverse
square potential spin chain models and the Yang-Baxter relation. This provides
us a powerful method to construct new integrable models with long-range
couplings from the solutions of the Yang-Baxter relation obtained from the
systems with short-range interactions. As an example, an integrable
anisotropic HS spin chain model is derived. The complete sets of conservation
laws of the ISE, HS and Inozemtsev models are constructed in quite simple
forms.

This work was supported by the National Natural Science Foundation of China,
the Knowledge Innovation Project of Chinese Academy of Sciences, and the
National Program for Basic Research of MOST.

* Email<EMAIL_ADDRESS>
## References

  * (1) L. A. Takhtadzhan and L. D. Faddeev, Rush. Math. Surveys 34, 11 (1979).
  * (2) R. J. Baxter, Exactly Solved Models in Statistical Mechanics (Academic Press, London, 1982).
  * (3) F. Calogero, J. Math. Phys. 10, 2191 (1969); 10, 2197 (1969); B. Sutherland, J. Math. Phys. 12, 246 (1971); 12, 250 (1971); Phys. Rev. A 4, 2019 (1971); 5, 1372 (1972).
  * (4) F. D. M. Haldane, Phys. Rev. Lett. 60, 635 (1988).
  * (5) B. S. Shastry, Phys. Rev. Lett. 60 639 (1988).
  * (6) A. P. Polychronakos, Nucl. Phys. B 324, 597 (1989); F.D.M. Haldane, Phys. Rev. Lett. 67 937 (1991); Z.N.C. Ha, Nucl. Phys. B 435, 604 (1995).
  * (7) V. I. Inozemtsev, J. Stat. Phys. 59, 1143 (1989).
  * (8) B. S. Shastry and B. Sutherland, Phys. Rev. Lett. 70, 4029 (1993).
  * (9) B. Sutherland and B. S. Shastry, Phys. Rev. Lett. 71, 5 (1993).
  * (10) F. D. M. Haldane, Phys. Rev. Lett. 66, 1529 (1991).
  * (11) B. S. Shastry, Phys. Rev. Lett. 69, 164 (1992).
  * (12) H. Kiwata and Y. Akutsu, J. Phys. Soc. Jpn. 61, 1441 (1992).
  * (13) N. Kawakami, Phys. Rev. B 46, 1005 (1992); 46, 3191 (1992).
  * (14) Z. N. C. Ha and F. D. M. Haldane, Phys. Rev. B 46, 9359 (1992).
  * (15) V. I. Inozemtsev, Commun. Math. Phys. 148, 359 (1992).
  * (16) B. D. Simons and B. L. Altschuler, Phys. Rev. B 50, 1102 (1994).
  * (17) D. Bernard, V. Pasquier and D. Serban, Europhys. Lett. 30, 301 (1995).
  * (18) C. F. Dunkl, Trans. Amer. Math. Soc. 311, 167 (1989).
  * (19) A. P. Polychronakos, Phys. Rev. Lett. 69, 703 (1992).
  * (20) M. Fowler and J. A. Minahan, Phys. Rev. Lett. 70, 2325 (1993).
  * (21) J. C. Talstra, F. D. M. Haldane, J. Phys. A: Math. Gen. 28, 2369 (1995).
  * (22) A. P. Polychronakos, Phys. Rev. Lett. 70, 2329 (1993).
  * (23) E. K. Sklyanin, J. Sov. Math. 47, 2473 (1989).
  * (24) M. Gaudin, J. Phys. (Paris) 37, 1087 (1976).


# Summarization with Precise Length Control

Lesly Miculicich Yujia Xie Song Wang Pengcheng He
Microsoft
<EMAIL_ADDRESS>

###### Abstract

Many applications of text generation such as summarization benefit from
accurately controlling the text length. Existing approaches on length-
controlled summarization either result in degraded performance or can only
control the length approximately. In this work, we present a framework to
generate summaries with precisely the specified number of tokens or sentences,
while maintaining or even improving the text quality. In addition, we jointly
train the models to predict the lengths, so our model can generate summaries
with optimal length. We evaluate the proposed framework on the CNNDM dataset
and show improved performance compared to existing methods.

##  1 Introduction

Controlling the length of the output is an important aspect of text
summarization, as the desired length of the summary can vary depending on
factors such as the size of the input document and the level of detail
required in the summary. For example, a summary can range from a single
sentence, providing a brief overview of the main topic or idea in the
document, to several paragraphs providing a more detailed summary of the
content. This can be particularly relevant in applications such as
customizable summarization and constrained or fixed length summarization,
where the text must fit specific device specifications such as screen width.

The success of length-controlled summarization is measured by both the
language quality and the length accuracy of the generated summary. Initial
approaches introduced the desired length as a parameter or vector embedding in
the model Kikuchi et al. (2016); Liu et al. (2018) but these methods produced
summaries with lower Rouge scores than their baselines. More successful
approaches divide the training data into buckets or bins, each with specific
length ranges (e.g. 0-30, 30-60) and use this information to build a summary
prefix Fan et al. (2018); He et al. (2020) or as a constrain Takase and
Okazaki (2019). While the summary quality improves in comparison with previous
approaches, this methods lose the ability for accurate length control with a
specific number of tokens. Another way to control the summary length is by
manipulating the probabilities of the end-of-sentence (EOS) token Chan et al.
(2021); Liu et al. (2022), but it may lead to fluency issues and lack of
coverage when forcing an earlier sequence termination.

In this work, we consider two practical cases of length-controlled
summarization: token-level control and sentence-level control. We propose two
easy-to-implement methods for the two cases, respectively. The first, REverse
Position Induced Length-cOntrolled Text generation _REPILOT_ , controls the
precise number of tokens to produce. The second, explicit sentence enumeration
_SentEnum_ , controls number of sentences. Both methods are highly accurate
and show improvements on Rouges scores on two data-sets. Moreover, we jointly
train the models to predict the optimal length of the summary given the input
document. So our models can handle cases where the input length is not
provided and it replaces the use length penalty during inference. Our
evaluation results show that these methods produce summary quality that is
comparable with state-of-the-art models and are significantly more accurate
than previous approaches.

In summary, our contributions are: 1) A method for highly accurate length
control of tokens and sentences with comparable or improved quality of the
summary. 2) A baseline for sentence-based length control for summarization. 3)
Length prediction in the summarization models to manage cases where the length
is not given.

##  2 Related Work and Baselines

Various methods for controlling the length of summaries have been proposed in
the literature. Kikuchi et al. (2016) proposed a method that uses a learnable
length embedding input at the beginning of the decoding process, called
_LenInit_. They also experimented with inputting the remaining length at each
time step of the decoding, called _LenEmb_. Makino et al. (2019) improved upon
this approach by optimizing the loss function with an overweight penalty,
called _GOLC_. Liu et al. (2018) proposed a method that uses a length
parameter as part of their CNN-based model, called _LC_. Liu et al. (2022)
used two attention mechanisms, one for controlling the information selection
and another for the end-of-sentence token. They first pre-trained a model with
balanced length data _LAAM_ , and then fine-tuned it with original data
_PtLAAM_. Saito et al. (2020) proposed to control the summary length by
inputting an extracted summary prototype _LPAS_ , and Takase and Okazaki
(2019) modified the sinusoidal positional embedding to allow length control
during decoding.

Some additional studies have proposed generic approaches for controlled
summarization with different features, including length. Fan et al. (2018)
proposed a method that divides the training data into buckets and prepends the
corresponding bucket id to the summary. He et al. (2020) pre-trained a model
by prepending extracted key-phrases from the summary. For length control they
divided the training on predefined buckets, and used the mean key-phrases per
bucket to control the summary length. Chan et al. (2021) proposed a method to
control the decoding based on a Constrained Markov Decision Process. For
length control, they use a cost function that computes the normalized distance
between the bucket ids of the generated summary and the reference.

##  3 Length Controlled Summarization

Denote $x=\\{x_{1},\cdots,x_{n}\\}$ as the input document, and $\ell$ as the
desired length, i.e., number of tokes or sentences. Our goal is to train a
probability model $p(y|x,l)$, where $y=\\{y_{1},\cdots,y_{l}\\}$ is the
summary. If the length is not given, our models can also estimate the length
of the summary as $p(l|x)$.

Figure 1: Left: Regular model. Right: Reverse Position Induced Length-
Controlled Text generation (REPILOT)

###  3.1 REPILOT

The REverse Position Induced Length-cOntrolled Text generation (REPILOT)
method is a light-weighted solution for accurately controlling the generated
text lengths. Specifically, we simply reverse the indices of position encoding
as “7, 6, …, 2, 1, 0”, as illustrated in the right of Figure 1. In this way,
the model is aware of the information of how many more tokens should be
decoded in each decoding step. By starting the position embedding with the
target length, we can control the length.

In practice, we observe that training the model with the exact number of
tokens may lead to abrupt ending of the generation, i.e., the generation will
end once the position index reach 0, no matter whether the sentences have
semantically ended. Therefore, we add a scalar noise to the position indices.
Specifically, we sample a scalar $\delta\sim\mathcal{N}(0,1)$, truncate it to
integer, and add it to the sequence of position indices.

###  3.2 SentEnum

We propose a simple yet effective solution for generating a desired number of
sentences in the output text. To the best of our knowledge, it is the first
solution for controlling the number of sentences to generate; as previous
solutions control the number of tokens. Controlling sentences is a challenging
problem because sentences boundaries like punctuation marks and spacing are
often ambiguous. We guide the generation by using explicit enumeration of
sentences. The required length is indicated as a number prefix to the summary.
The inserted numbers are preceded by an special token _[SN]_ to differentiate
them from the text111We preprocess the training data with the previously
described annotation, using the sentence tokenizer from NLTK
https://www.nltk.org/api/nltk.tokenize.html, and we post-processed the summary
to remove the annotation at inference time., the following is an example:

[SN]3 [SEP] [SN]1 Nearly 40 endangered forest elephants were killed in 2
parks. [SN]2 Sudanese poachers on horseback are believed to be responsible.
[SN]3 Forest and savanna elephant populations have declined drastically

###  3.3 Length Prediction

The models are trained to predict both the length and the summary as multi-
task learning. In the case of _REPILOT_ , we use a head classifier for
predicting the number of tokens. The loss is computed with a weighted average
from both length classifier and summarization, where we adopt the mean squared
loss for the length prediction and the cross entropy loss for the text
generation. In the case of _SentEnum_ , we simply train the model to predict
the length prefix together with the summary as a text string. This method is
easier to implement and preliminary experiments show similar performance as
having a separate head to predict the number of sentences.

##  4 Experimental Setup

We initialize our models with Zcode++ He et al. (2022), a large pre-trained
language model that reported strong results when fine-tuned in summarization.
Unless specified we use the same hyper parameters and configuration.

Data-sets: We perform experiments on CNNDM data Nallapati et al. (2016) and
Arxiv Cohan et al. (2018). Information and statistics are detailed in Appendix
A.

Metrics: We use the standard Rouge score (R1, R2) for evaluating the summary
outputs. To evaluate the success of the length control, we measure the
accuracy (Acc.) and the mean absolute difference (Diff.).

##  5 Results and Analysis

###  5.1 Summary quality

Table 1 shows the Rouge scores on CNNDM. We compare with the reported results
of previous works described in Section 2. All previous approaches use the
length of the annotated reference summary to report rouge scores (marked as G
in the Table 1); and some of them use an external model to extract information
from the document such as key-phases or -sentences (marked as E in the Table
1) which are not directly comparable to ours. Our approach is the first to
predict the expected length jointly with the summary. We show the results with
our two models _REPILOT_ and _SentEnum_ with both golden and predicted
lengths. In addition, we report the scores of Zcode++ finetuned on CNNDM. We
use beam search of size 3 and no length penalty. The length penalty adjust the
model to the typical length of the test set. We argue that the length
prediction can replace the use of this hyper-parameter and preliminary
experiments showed that our models archive better scores without it. We
however report results of Zcode++ with and without length penalty.

Both _REPILOT_ and _SentEnum_ using reference target lengths archive higher
Rouge score than Zcode++. In addition, our models with predicted length
performed better than Zcode++ without the length penalty adjustment, and on
par with Zcode++ with length penalty. The results are also comparable with the
reported results of similar approaches even though we do not use external
model to extract information from the document to guide the summary
generation.

###  5.2 Length Control Accuracy on _REPILOT_

Table 2 shows the performance of the length control measured in number of
tokens for _REPILOT_. We compare it with 3 baselines: a fine-tuned Zcode++
model and two models that group the summaries into different number of buckets
and use the bucket ids as the length control Fan et al. (2018); He et al.
(2020). The models are evaluated using golden lengths of reference summaries
and using the same decoding method: greedy decoding without n-gram blocking.
Our results show that _REPILOT_ achieved better ROUGE scores and lower mean
absolute difference between requested and predicted lengths.

###  5.3 Length Control Accuracy on _SentEnum_

Table 3 shows the evaluation for _SentEnum_. We compare it with three
baselines: a fine-tuned Zcode++, a model that groups the summaries into
_Buckets_ Fan et al. (2018); He et al. (2020), and a model that uses only the
required number of sentences as prefix without sentence enumeration
_SentPrefix_. As the diversity of number of sentences in the summaries is
small in CNNDM (Appendix A), we include experiments in Arxiv. The results are
obtained with greedy decoding without n-gram blocking which archived the best
accuracy for all methods. We utilize the golden lengths as input, and evaluate
the generated vs. the golden length. _SentEnum_ is significantly more accurate
to generate the required number of sentences and shows higher R2 scores.
Appendix B shows additional details about the percentage of over and under
generation respect to the input length. _SentEnum_ shows the least percentage
of errors.

Additionally, we evaluated the accuracy on an out-of-domain test set of 50
samples using length from 1 to 8 for all examples. Figure 2 shows the results
comparing _Buckets_ , _SentPrefix_ and _SentEnum_. The vertical axis show the
accuracy of the generated length and the horizontal axis the input lengths.
_SentEnum_ model shows higher accuracy for all input lengths, spatially in the
middle range.

###  5.4 Length Prediction Accuracy

Finally, we evaluate the length predictor. Table 4 shows the Diff. of the
predicted vs. the reference length. We compare with a _Encoder-based
classifier_ trained using DeBerta. He et al. (2021) with mean square loss. The
jointly trained predictors are slightly more accurate than the individually
trained ones showing that the multitask approach is effective.

##  6 Conclusions

We study two simple methods for precisely controlling the length of tokens and
sentences in text summarization. These techniques generated text with a
specified length more accurately than previous methods. Additionally, we
introduced a length predictor, making the models more versatile and easier to
use without requiring an input length. These techniques can also be applied to
other tasks such as text simplification and translation.

R1 R2 _w/o pre-trained LM_ LenInit Kikuchi et al. (2016) G 25.87 8.27 LenEmb
Kikuchi et al. (2016) G 26.73 8.39 LC Liu et al. (2018) G 35.45 14.50 GOLC
Makino et al. (2019) G 38.27 16.30 LenCtrl Fan et al. (2018) G 39.16 15.54
LenAttn Yu et al. (2021) G 39.82 17.31 GPT2 CMDP Chan et al. (2021) G 41.72
17.99 LPAS Saito et al. (2020) GE _42.55_ _20.09_ _w/ pre-trained LM_ BART
Lewis et al. (2020) N 44.16 21.28 BLPAS Liu et al. (2022) GE _42.95_ _20.29_
LAAM Liu et al. (2022) GE _43.55_ _20.44_ PtLAAM Liu et al. (2022) GE _44.17_
_20.63_ CtrlSum He et al. (2020) E _45.65_ _22.35_ CtrlSum He et al. (2020) GE
_46.26_ _22.60_ Zcode++ He et al. (2022) N 45.53 22.55 Zcode++ w/o length
penalty N 45.19 22.41 \+ REPILOT G 46.20 22.03 \+ REPILOT + length pred. N
45.61 22.13 \+ SentEnum. G 46.02 22.60 \+ SentEnum. + length pred. N 45.54
22.56

Table 1: Evaluation Results on CNNDM data. G: Use length from the reference
summary. E: Use extracted information from the document. N: None of the above.

R1 $\uparrow$ R2 $\uparrow$ Diff. $\downarrow$ Zcode++ 44.76 21.33 16.68
Buckets-10 45.82 21.76 5.84 Buckets-100 45.86 21.54 1.43 REPILOT 46.36 22.08
1.30

Table 2: Results of the REPILOT modelon CNNDM using greedy decoding and
without n-gram blocking.

R1 $\uparrow$ R2 $\uparrow$ Acc. $\uparrow$ Diff. $\downarrow$ _CNNDM_ Zcode++
44.8 21.3 60.1 0.5 Buckets 45.8 21.8 87.1 0.1 SentPrefix 45.7 21.7 94.0 0.1
SentEnum 45.7 22.1 98.6 0.02 _Arxiv_ Zcode++ 46.3 19.5 20.3 1.5 Buckets 50.1
21.0 77.5 0.2 SentPrefix 50.0 20.9 79.9 0.2 SentEnum 49.8 21.3 93.3 0.1

Table 3: Results of _SenEnum_ model using greedy decoding and without n-gram
blocking.

Tokens Sentences Encoder-based classifier 15.42 1.04 Jointly trained
classifier 15.13 0.90

Table 4: Diff. of the predicted length vs. gold length. Figure 2: Accuracy of
the produced summary length respect to the input number of sentences. The
evaluation is done on a out-of-distribution set.

## Limitations

Our methods are not the perfect solution to control summarization granularity.
We will keep exploring semantic aware length control to control the
granularity of generated text in a more meaningful way. Additionally, the
methods were not tested on unseen lengths in the training data. _SentEnum_ is
less accurate when the input length is higher due to the fewer number of long
examples in the training data. This suggest it doesn’t generalize for all
lengths. Another limitation of _SentEnum_ is the quality of the sentence
splitter. In our experiments, the errors introduced by the splitter did not
have a significant impact on the results but it may not be the case for
noisier data-sets or different languages.

## Ethics Statement

Our work is committed to comply with all applicable ACL Ethics Policy
222https://www.aclweb.org/portal/content/acl-code-ethics. We presented methods
which are simple to replicate and do not required high computation resources
as they can use pre-trained language or summarization models. We acknowledge
the risk of any text generation model to produce outputs that could lead to
misinformation, bias or misuse. We however committed to use publicly available
datasets whose content is relatively safe.

## References

  * Chan et al. (2021) Hou Pong Chan, Lu Wang, and Irwin King. 2021.  Controllable summarization with constrained Markov decision process.  _Transactions of the Association for Computational Linguistics_ , 9:1213–1232.
  * Cohan et al. (2018) Arman Cohan, Franck Dernoncourt, Doo Soon Kim, Trung Bui, Seokhwan Kim, Walter Chang, and Nazli Goharian. 2018.  A discourse-aware attention model for abstractive summarization of long documents.  In _Proceedings of the 2018 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 2 (Short Papers)_ , pages 615–621, New Orleans, Louisiana. Association for Computational Linguistics.
  * Fan et al. (2018) Angela Fan, David Grangier, and Michael Auli. 2018.  Controllable abstractive summarization.  In _Proceedings of the 2nd Workshop on Neural Machine Translation and Generation_ , pages 45–54, Melbourne, Australia. Association for Computational Linguistics.
  * He et al. (2020) Junxian He, Wojciech Kryscinski, Bryan McCann, Nazneen Fatema Rajani, and Caiming Xiong. 2020.  Ctrlsum: Towards generic controllable text summarization.  _CoRR_ , abs/2012.04281.
  * He et al. (2021) Pengcheng He, Xiaodong Liu, Jianfeng Gao, and Weizhu Chen. 2021.  {DEBERTA}: {DECODING}-{enhanced} {bert} {with} {disentangled} {attention}.  In _International Conference on Learning Representations_.
  * He et al. (2022) Pengcheng He, Baolin Peng, Liyang Lu, Song Wang, Jie Mei, Yang Liu, Ruochen Xu, Hany Hassan Awadalla, Yu Shi, Chenguang Zhu, Wayne Xiong, Michael Zeng, Jianfeng Gao, and Xuedong Huang. 2022.  Z-code++: A pre-trained language model optimized for abstractive summarization.
  * Kikuchi et al. (2016) Yuta Kikuchi, Graham Neubig, Ryohei Sasano, Hiroya Takamura, and Manabu Okumura. 2016.  Controlling output length in neural encoder-decoders.  In _Proceedings of the 2016 Conference on Empirical Methods in Natural Language Processing_ , pages 1328–1338, Austin, Texas. Association for Computational Linguistics.
  * Lewis et al. (2020) Mike Lewis, Yinhan Liu, Naman Goyal, Marjan Ghazvininejad, Abdelrahman Mohamed, Omer Levy, Veselin Stoyanov, and Luke Zettlemoyer. 2020.  BART: Denoising sequence-to-sequence pre-training for natural language generation, translation, and comprehension.  In _Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics_ , pages 7871–7880, Online. Association for Computational Linguistics.
  * Liu et al. (2022) Yizhu Liu, Qi Jia, and Kenny Zhu. 2022.  Length control in abstractive summarization by pretraining information selection.  In _Proceedings of the 60th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , pages 6885–6895, Dublin, Ireland. Association for Computational Linguistics.
  * Liu et al. (2018) Yizhu Liu, Zhiyi Luo, and Kenny Zhu. 2018.  Controlling length in abstractive summarization using a convolutional neural network.  In _Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing_ , pages 4110–4119, Brussels, Belgium. Association for Computational Linguistics.
  * Makino et al. (2019) Takuya Makino, Tomoya Iwakura, Hiroya Takamura, and Manabu Okumura. 2019.  Global optimization under length constraint for neural text summarization.  In _Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics_ , pages 1039–1048, Florence, Italy. Association for Computational Linguistics.
  * Nallapati et al. (2016) Ramesh Nallapati, Bowen Zhou, Cicero dos Santos, Çağlar Gulçehre, and Bing Xiang. 2016.  Abstractive text summarization using sequence-to-sequence RNNs and beyond.  In _Proceedings of the 20th SIGNLL Conference on Computational Natural Language Learning_ , pages 280–290, Berlin, Germany. Association for Computational Linguistics.
  * Saito et al. (2020) Itsumi Saito, Kyosuke Nishida, Kosuke Nishida, Atsushi Otsuka, Hisako Asano, Junji Tomita, Hiroyuki Shindo, and Yuji Matsumoto. 2020.  Length-controllable abstractive summarization by guiding with summary prototype.  _CoRR_ , abs/2001.07331.
  * Takase and Okazaki (2019) Sho Takase and Naoaki Okazaki. 2019.  Positional encoding to control output sequence length.  In _Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long and Short Papers)_ , pages 3999–4004, Minneapolis, Minnesota. Association for Computational Linguistics.
  * Yu et al. (2021) Zhongyi Yu, Zhenghao Wu, Hao Zheng, Zhe XuanYuan, Jefferson Fong, and Weifeng Su. 2021.  LenAtten: An effective length controlling unit for text summarization.  In _Findings of the Association for Computational Linguistics: ACL-IJCNLP 2021_ , pages 363–370, Online. Association for Computational Linguistics.

##  Appendix A Data Statistics

The following table shows the number of examples for training, development and
testing for the reported data-sets:

Train Dev. Test CNNDM 287,113 13,368 11,490 Arxiv 202,914 6,436 6,440

The following statistics are calculated from the summaries of the training
sets.

Max Min Mean Med. P75 P95 STD _CNNDM_ Words 1,246 4 49 46 57 85 20 Sent. 36 1
3.8 4 4 6 1.3 _Arxiv_ Words 26K 2 278 164 237 482 587 Sent. 20 1 6.1 6 8 10
2.2

##  Appendix B Over and Under Length Generation

We count the percentage of examples with generated length shorter and longer
than the gold length. We called % Over) and %Under generation. This results
were obtained with the _SentEnum_ model using with greedy decoding and without
n-gram blocking in CNNDM and Arxiv data-sets. Given the data distribution, the
number of shorter training examples is higher than the longer ones. Thus, all
methods have tendency to under produce rather than over produce. However,
_SentEnum_ show significantly better results.

%Over$\downarrow$ %Under $\downarrow$ _CNNDM_ Zcode++ 14.5 25.4 Buckets 1.8
11.1 SentPrefix 1.1 4.9 SentEnum 0.8 0.6 _Arxiv_ Zcode++ 19.9 59.8 Buckets 6.8
16.6 SentPrefix 5.9 14.7 SentEnum 2.4 4.3