language=csh, linewidth=stringstyle=, escapeinside=(**), basicstyle=,
keywordstyle=,
morekeywords=@start,@output,@input,string,bool,string[],int,Tuple,<,>,language,@values,using,Regex,
morecomment=[l][]//

#  Cornet: A neurosymbolic approach to learning conditional table formatting
rules by example

Mukul Singh1, José Cambronero2, Sumit Gulwani211footnotemark: 1, Vu
Le211footnotemark: 1, Carina Negreanu311footnotemark: 1,
Mohammad Raza211footnotemark: 1, Gust Verbruggen211footnotemark: 1 Listed in
alphabetical order

###### Abstract

Spreadsheets are widely used for table manipulation and presentation.
Stylistic formatting of these tables is an important property for both
presentation and analysis. As a result, popular spreadsheet software, such as
Excel, supports automatically formatting tables based on data-dependent rules.
Unfortunately, writing these formatting rules can be challenging for users as
that requires knowledge of the underlying rule language and data logic. In
this paper, we present Cornet, a neuro-symbolic system that tackles the novel
problem of automatically learning such formatting rules from user examples of
formatted cells. Cornet takes inspiration from inductive program synthesis and
combines symbolic rule enumeration, based on semi-supervised clustering and
iterative decision tree learning, with a neural ranker to produce conditional
formatting rules. To motivate and evaluate our approach, we extracted tables
with formatting rules from a corpus of over 40K real spreadsheets. Using this
data, we compared Cornet to a wide range of symbolic and neural baselines. Our
results show that Cornet can learn rules more accurately, across varying
conditions, compared to these baselines.

## Introduction

Tables are a popular form of representing structured data for understanding
and sharing. Spreadsheets are the most common table manipulation software,
with around a billion monthly active users (N. 2022). Formatting is a
fundamental and frequently used visual aid to better display, highlight or
distinguish between data points in a spreadsheet. In an analysis of a large
public spreadsheet corpus (Barik et al. 2015; Fisher and Rothermel 2005), we
find that close to 25% of spreadsheets have some formatting to present data.

_Conditional formatting_ (CF) is a feature that automates table formatting
based on user-defined data-dependent rules. It is a standard feature in all
major spreadsheet manipulation tools, such as Microsoft Excel, Google Sheets
and Apple Numbers. All these tools support predefined templates for popular
rules, such as _value greater than a specific value_. Excel and Sheets also
support custom rules, where a user can enter a boolean-valued formula to
format cells. Figure 1 illustrates adding CF Rule in Excel with a real
example.

Unfortunately, creating conditional formatting rules requires users to
understand the syntax and logic behind them. As of June 2022, more than 10,000
conditional formatting related questions were posted on the Excel tech help
community alone (Excel 2022). By analyzing the posts we discovered three key
struggles that prevent users from using CF to its full potential. First, many
users are unaware of this feature and manually apply formatting to their
spreadsheets. Second, when a user does enter a CF rule, they sometimes fail to
do so correctly and end up manually formatting the sheet. Third, even when
users write valid rules that matches their desired formatting, the rules are
either unnecessarily complex (can be rewritten to much simpler rules), or not
generalizable (may produce wrong formatting when the columns change).

###### Example 1

Figure 2 shows a case from a public spreadsheet where the user wanted to
highlight cells with value $<5$, but wrote an incorrect rule and had to
manually format the sheet.

Figure 1: Adding a CF Rule in Excel: 1 CF Option in Styles Pane; 2 CF Dropdown
Menu to add new rule 3 CF New Rule Dialog box; 4 Resulting formatted column
from rule. After the user formats two cells, Cornet automatically suggest the
intended CF rule for the user.

Some of these struggles are reinforced by limitations in the interface used to
apply conditional formatting. For example, using logical operations like or
and and requires writing custom formulas. Additionally, there is no validation
for data types, which can cause surprising results, for example, it is
possible to write a rule that formats cells whose value is _less than 5_ for a
text column.

In this paper we present Cornet (Conditional ORNamentation by Examples in
Tables), a system that allows users to automatically generate a formatting
rule from examples, thus obviating the challenges outlined. Cornet takes a
small number of user formatted cells as input to learn the most likely
formatting rule that generalizes to other cells. Cornet explores possible
predicates for the target column, hypothesizes cell grouping via semi-
supervised clustering and then learns candidate rules by employing an
iterative tree learning procedure. Since multiple rules match the examples,
Cornet uses a neural ranker to return the most likely CF rule to the user. For
example, in Fig. 1, after the user formats two cells, Cornet suggests the
intended CF rule.

Traditional programming-by-example (PBE) systems (Gulwani 2011; Le and Gulwani
2014) can typically derive useful search constraints by relating properties of
the outputs to the inputs provided (e.g. an output text may share spans with
an input text). This is challenging to do in CF learning as the user only
provides what amounts to a small number of formatting labels. The predicate
generation and clustering step in Cornet mitigates this by generating and
applying simple predicates, which jointly can help _hypothesize_ such
formatting labels for the entire target column. Once these hypothesized labels
are available, we can apply our iterative rule enumeration procedure. Much
like other PBE problems, we enumerate multiple possible programs consistent
with our hypothesized outputs. Our enumeration uses tree learning as we can
easily enforce consistency over user-provided examples. The learning process
is iterative to induce diversity of candidate rules. Finally, we employ a
ranker that can disambiguate between these competing programs by capturing
properties not just of the rule but also of the underlying data and the
execution of the rule on that data.

Figure 2: Example of incorrectly using CF: 1 a user defined a custom rule that
always evaluates to false (it compares the cell to the string “5” instead of
the number 5); 2 because the rule does not format any cell, the user had to
manually format the sheet; 3 the correct rule for the formatting.

To evaluate Cornet, we created a benchmark of 968 real user tasks from public
Excel spreadsheets. Cornet outperforms symbolic and neural baselines that were
adapted to our problem, by accurately learning conditional formatting rules
with as few as two or three formatted examples.

This paper makes the following key contributions:

  * •

Based on the observation that users often struggle to format their tabular
data, we introduce the novel problem of learning conditional formatting rules
from examples.

  * •

We propose a neurosymbolic system Cornet to learn CF rules from examples over
tabular data. Cornet is based on a novel PBE methodology that leverages few
examples to predict more examples and then generalize them into an intended CF
rule. This is done via a novel combination of symbolic (predicate set)
enumeration, ML methods of semi-supervised clustering (to predict more
examples using predicate set) and iterative tree learning (to propose
candidate rules), and a neural ranker (to pick an intended rule).

  * •

We create a dataset of 968 real formatting tasks. We release this dataset to
encourage future research.

  * •

We evaluate Cornet extensively and show that it outperforms the baselines by
20–25% on our benchmark.

Conditional formatting is often a preliminary step to performing further
sophisticated analysis such as conditional transformations for data cleaning
or visualizations. Our work on automating conditional formatting shall
motivate research in automating such more encompassing workflows.

## Problem Definition

Let $C=[c_{i}]_{i=1}^{n}$ be a column of $n$ cells with each cell $c_{i}$
represented by a tuple $(v_{i},t_{i})$ of its value $v_{i}\in\mathcal{V}$ and
its annotated type $t_{i}\in\mathcal{T}$. In this paper, we consider string,
number, and date as possible types—these are available in most spreadsheet
software. We associate a format identifier $f_{i}\in\mathbb{N}_{0}$ (or simply
format) with each cell, which corresponds to a unique combination of
formatting choices made by the user. A special identifier $f_{\perp}=0$ is
reserved for cells without any specific formatting. In this paper, we consider
cell fill color, font color, font size, and cell borders.

A conditional formatting rule (or simply _rule_) is a function
$r:\mathcal{C}\rightarrow\mathbb{N}_{0}$ that maps a cell to a formatting
identifier. Given a column $C$ and specification, the goal of automatic
formatting is to find a rule $r$ such that $r(c_{i})=f_{i}$ for all $c_{i}\in
C$.

Let $C_{\star}=\\{c_{i}\mid c_{i}\in C,f_{i}\neq f_{\perp}\\}$ be the cells
with formatting applied. The goal of automatic formatting by example is to
find $r$ given only a small, observed subset $C_{obs}\subset C_{\star}$ and
throughout this work we will refer to the elements of $C_{obs}$ as _formatted
examples_. Any cell in $C\setminus C_{obs}$ is considered unlabeled, including
_unformatted cells_.

The examples in $C_{obs}$ do not provide a complete problem specification. To
find the best $r$, we cast the problem as a heuristic search over candidate
rules $\mathcal{R}$. Let
$h:\mathcal{R}\times\mathcal{C}^{n}\rightarrow\mathbb{R}$ be a function that
takes a rule $r$ and a column $C$ and returns an estimate of the quality of
$r$ with respect to $C$—how likely it is that a user would have wanted this
rule. Given a column $C$ with only a few formatted cells we then want to find
the rule $r^{*}=\operatorname*{arg\,max}_{r\in\mathcal{R}}h(r,C)$ that
maximizes this heuristic. In this regard, learning CF rules shares motivations
with multilabel classification with limited and noisy supervision.

For automatic conditional formatting by example we require a space of possible
rules $\mathcal{R}$, a method to enumerate candidate rules $r\in\mathcal{R}$
and a method of evaluating the quality of such rules. In the following section
we introduce our approach, aided by an analysis of real user spreadsheets.

## Approach

This section describes how Cornet learns rules from a small number of
examples. We restrict rules to being logical combinations of boolean-valued
properties of cells. Still, the space of combinations of predicates is much
larger than the space of possible outputs. Rather than directly learning a
program that generalizes to unlabeled cells, we therefore first predict the
expected output on the whole column.

Figure 3 shows a schematic overview of Cornet. Step 1 enumerates cell
properties using predicates. Step 2 computes the expected output using semi-
supervised clustering. Once this is known, we enumerate programs that match
this output in step 3, and rank them in step 4. The following sections
describe the challenges and solutions for each step.

Figure 3: Proposed system architecture illustrated through the example case
from Figure 1: 0 input table with partial formatting, 1 predicate generation
for all cells in the table, 2 semi supervised clustering using examples and
other cells to address the challenge of unlabeled cells, 3 enumerating rules
based on the clustering using multiple decision trees, 4 neural ranker to
score generated rules, and 5 final learned conditional formatting rule.

### Predicate Generation

This step enumerates a set of properties that hold for a strict subset of the
cells of the given column. Each property is encoded as a predicate—a boolean-
valued function that takes a cell $c$, zero or more arguments and returns true
if the property that it describes holds for $c$. To avoid redundancy, all
predicates are assigned a type $t_{i}$ and they only match cells of their
type. Supported predicates are shown in Table 1.

Table 1: Supported predicates and their arguments for each data type. The $d$ argument in datetime predicates determines which part of the date is compared—day, month, year, or weekday. For example, greater($c$, 2, month) matches datetime cells with a date in March or later for any year. Numeric | Datetime | Text
---|---|---
greater($c$, $n$) | greater($c$, $n$, $d$) | equals($c$, $s$)
greaterEquals($c$, $n$) | greaterEquals($c$, $n$, $d$) | contains($c$, $s$)
less($c$, $n$) | less($c$, $n$, $d$) | startsWith($c$, $s$)
lessEquals($c$, $n$) | lessEquals($c$, $n$, $d$) | endsWith($c$, $s$)
between($c$, $n_{1}$, $n_{2}$) | between($c$, $n_{1}$, $n_{2}$, $d$) |

Given a column of cells and a predicate, the goal is to initialize each
additional argument to a constant value such that the predicate returns true
for a strict subset of the column. Table 2 shows an overview of how the
additional argument values are initialized for predicates of each type.

### Semi-supervised Clustering

Rather than immediately combine predicates into rules, we first predict the
expected output of the rules on the column’s unobserved (i.e., unformatted)
cells. This allows us to leverage the relatively small search space of output
configurations over cell properties to find programs that generalize to
similar cells. Cornet biases the output using a programmatic vocabulary of
predicates instead of relying on arbitrary cell clustering. (Padhi et al.
2017) uses the same concept but with the programmatic vocabulary of regular
expressions.

More concretely, we assign a (potentially noisy) formatting label
$\hat{f_{i}}$ to each unobserved cell $c_{i}\notin C_{obs}$ by building on two
insights. First, tables are typically annotated by users from top to bottom,
which implies that there is positional information available. In particular,
cells $c_{i}\notin C_{obs}$ such that there exist $c_{j},c_{k}\in C_{obs}$ for
which $j<i<k$ are likely intended to have no formatting associated with them.
We refer to this set of $c_{i}$ as _soft negative examples_ (Raza and Gulwani
2020). Second, user provided examples $C_{\text{obs}}$ should be treated as
hard constraints—we assume that the user has provided their formatting goals
without errors.

We perform iterative clustering over $k$ clusters, where $k$ is the number of
unique format identifiers for our column, plus one cluster for unassigned
cells. The distance between two cells is the size of the symmetric difference
between the sets of predicates that hold for either cell. Let
$\text{cluster}_{f}$ be the cluster associated with format $f$. Some
supervision is introduced by initializing each cell $c_{i}\in C_{\text{obs}}$
to $\text{cluster}_{f_{i}}$ and soft negative example cells to
$\text{cluster}_{0}$. These cells are never assigned to another cluster. The
remaining cells $C_{u}$ are assigned to the unknown formatting cluster,
labeled $\text{cluster}_{u}$. Taking inspiration from $k$-medoids (Kaufman and
Rousseeuw 2009) we iteratively reassign $c_{u}\in C_{u}$ to a new cluster.
Instead of computing a cluster medoid, however, we combine the minimal and
maximal distance to any element of the cluster. This is computationally much
more efficient (linear instead of quadratic in the number of distance
computations) and was found to perform well in practice. When clusters become
stable or a maximal number of iterations is reached, each cell takes the
format value of their associated cluster, with $\text{cluster}_{u}$ added to
$\text{cluster}_{0}$. If $c_{i}\in C_{obs}$, we have $\hat{f}_{i}=f_{i}$.

Table 2: Overview of constants for concretizing predicates of each type. For example, we generate constants for text predicates from two token sources. Type | Arg(s) |  Values
---|---|---
numeric | $n$ |  all numbers that occur in the column
numeric | $n$ |  summary statistics: mean, min, max, and percentiles
numeric | $n$ |  popular constants such as $0$, $1$ and $10^{n}$
numeric |  $n_{1}$ and $n_{2}$ |  use numeric generators for $n$ and keep the ones $n_{1}<n_{2}$
text | $s$ |  tokens obtained by splitting on non-alphanumeric delimiters
text | $s$ |  tokens from prefix trie
date |  $n$ and $d$ |  for available $d$, extract numeric value and use generator for $n$

### Candidate Rule Enumeration

After clustering, we have a target formatting label $\hat{f}_{i}$ for each
$c_{i}$ in $C$. We now learn a set of candidate rules $R$ such that
$r(c_{i})=\hat{f}_{i}$ for all $r\in R$. We define the space of rules and a
search procedure in the following two subsections.

#### Predicates to Rules

A rule in Cornet for a column $C$ consists of a set of tuples $(r_{f},f)$ with
$r_{f}:\mathcal{C}\rightarrow\mathbb{B}$ a function that takes a cell and
returns a boolean and $f\in\mathbb{N}_{0}$ a format identifier. These $r_{f}$
are disjoint with respect to $C$ such that for each $c\in C$, there is at most
one $r_{f}$ such that $r_{f}(c)=\textsf{true}$ and we say that $r_{f}$ matches
$c$. For a given cell, the rule returns the associated $f$ if it evaluates to
true. The cell is left unformatted if all $r_{f}$ evaluate to false. Cornet
supports $r_{f}$ that can be built as a propositional formula in disjunctive
normal form over predicates. In other words, every $r_{f}$ is of the form

$\boldsymbol{\left(\right.}p_{1}(c)\wedge
p_{2}(c)\wedge\ldots\boldsymbol{\left.\right)}\vee\boldsymbol{\left(\right.}p_{j}(c)\wedge
p_{j+1}(c)\wedge\ldots\boldsymbol{\left.\right)}\vee\ldots$

with $p_{i}$ a generated predicate or its negation. Our goal is to strike a
balance between expressiveness and simplicity.

#### Enumerating Rules

Despite the large search space, we can generate candidates by learning rules
for each format separately in a _one versus all_ setting. In this setting, the
rule for a format $f$ is expected to consist of predicates that either hold
for many cells with format $f$ and few with other formats, or vice versa.
Taking this one step further, the combination of predicates in a conjunction
in one $r_{f}$ should either only hold for cells with format $f$ or not hold
for any cell with format $f$.

Figure 4: Ranking model architecture: 1 inputs to the model are the data
column and the rule to be scored; 2 the column encoding model pools BERT token
embeddings, passes them through cross attention with the rule’s execution
outputs (i.e. formatted or not), and then through a linear layer; and 3 the
resulting embedding is concatenated with manually-engineered rule features and
fed into a final linear layer which outputs the score after applying a sigmoid
activation.

Based on this intuition, we greedily enumerate promising candidates by
iteratively learning decision trees and using predicates as features. Each
decision tree then corresponds to a rule in disjunctive normal form (Blockeel
and De Raedt 1998). We identify and address three challenges: variety in
rules, simplicity of rules, and coping with noisy labels. To ensure variety,
the root feature is removed from the set of candidates after each iteration.
To ensure simplicity, we only accept decision trees with $\lambda_{n}$ or
fewer nodes. To deal with noisy labels, we only require decision trees to have
perfect accuracy on observed examples, we consider labeled cells to be twice
as important as unlabeled ones and we stop learning more rules once the
accuracy falls below a threshold. This learning procedure is shown in
Algorithm 1.

Algorithm 1 Rule Enumeration using Decision Trees

0: Matrix of features $P$ and vector of labels $Y$

0: A set of candidate rules

1: rules $\leftarrow\\{\\}$

2: forbidden $\leftarrow\\{\\}$

3: while accuracy $\geq\lambda_{a}$ and $|P\setminus\text{forbidden}|>0$ do

4: tree $\leftarrow\textsc{fit}(P\setminus\text{forbidden},Y)$

5: accuracy
$\leftarrow\textsc{evaluate}(\text{tree},P\setminus\text{forbidden},Y)$

6: forbidden $\leftarrow\text{forbidden}\cup\textsc{root}(\text{tree})$

7: if $\text{tree \emph{satisfies user
examples}}\wedge\text{accuracy}\geq\lambda_{n}$ then

8: rules $\leftarrow\text{rules}\cup\textsc{rules}(\text{tree})$

9: return rules

### Candidate Rule Ranking

We first assign scores to rules for each format separately and combine and
rank them later. Rules for different formats must be disjoint with respect to
the given column. Combined rules are ranked by the highest total score. We use
this section to describe how to assign scores to rules $r_{f}$ for one format.

Rules can be ranked based on output features (Natarajan et al. 2019) or rule
features (Ellis and Gulwani 2017). The proposed neural ranker combines
information from both. Information about the rule is captured by handpicked
features. Information about the column data is captured by turning it into a
sequence of words and using a pre-trained language model (Devlin et al. 2019)
to obtain cell-level embeddings. These embeddings are augmented with
information about the execution of the rule through cross-attention (Lee et
al. 2018). Both vectors of information are merged by concatenating them and
learning weights that produce a single score. This score thus combines both
syntactic (rule) and semantic (data and execution) information. For our task,
using simple heuristics such as “choose the shortest rule that matches user
examples” does not necessarily work. For example, in Figure 3 the gold rule is
longer than other candidates consistent with the user’s examples. Figure 4
shows an overview of our ranker, further detailed in the appendix.

We train the model by treating this problem as binary classification (i.e., a
rule candidate matches the gold CF rule) and using the output of the final
activation as the score. Training data is generated by using Cornet up to rule
enumeration on a held-out dataset of columns with conditional formatting. We
provide 1, 3 or 5 examples and only keep rules that do _not_ match the gold as
negative samples. Additionally, we apply gold rules on other columns to obtain
both positive (by construction) and negative (by the procedure above)
examples. All gold rules in this dataset are also used. This process results
in approximately 3500 examples for our model.

## Evaluation

We perform experiments to answer the following questions:

  * Q1.

How does Cornet compare to baselines?

  * Q2.

How does the input table configuration affect learning?

  * Q3.

How do design decisions impact our effectiveness?

We first describe the components we built to evaluate Cornet: our benchmark,
evaluation metrics and baselines.

##### Benchmark

To evaluate Cornet, we created a benchmark by crawling 22,000 publicly
available Excel workbooks from the web. Among these, 2,500 workbooks contain
at least one CF rule added by users, from which we extracted 10,000 CF rules
and their corresponding cell values and formatting. After removing duplicates
and restricting to rules that operate on at least five cells and format at
least two of them, we retain 968 tasks. Table 3 shows a summary of the
benchmark. Text rules are the most popular, followed by numeric then date.

Table 3:  Summary of rules in our benchmark with number of rules, average number of cells, average number of formatted cells, and depth of CF rule (by parsing into our grammar). Type | Rules | # Cells | # Formatted | Rule Depth
---|---|---|---|---
Text | 586 | 54.8 | 17.1 | 2.1
Numeric | 329 | 72.6 | 25.0 | 1.7
Date | 53 | 28.9 | 10.4 | 1.8
Total | 968 | 59.5 | 19.4 | 1.9

##### Evaluation Metrics

We consider two metrics: exact match and execution match. _Exact match_ is a
syntactic match between a conditional rule candidate and the gold rule, with
tolerance for differences arising from white space, alternative argument
order, and a set of basic semantics-preserving rewrite rules. _Execution
match_ consists of executing a rule and comparing the produced formatting to
the gold formatting—there is an execution match if the two formattings are
identical. This distinction between exact and execution match is also made in
related areas, such as natural language to code (Poesia et al. 2022; Liguori
et al. 2022).

Table 4: Comparison of Cornet with both published (Pub.) and new baselines. The performance is evaluated on exact and execution match for 1, 3 and 5 user formatted examples (ex.). The column Rules denotes if a system generates symbolic rules or just the output formatting. Cornet outperforms both neural and symbolic baselines in both execution and exact rule match. System Description | Execution Match | Rule Match
---|---|---
Name | Technique | Rules | Pub. | 1 ex. | 3 ex. | 5 ex. | 1 ex. | 3 ex. | 5 ex.
Decision Tree | Symbolic | Yes | No | 44.8 | 56.4 | 60.1 | 14.4 | 18.9 | 19.6
Predicates + Decision Tree | Symbolic | Yes | No | 54.8 | 67.9 | 71.7 | 42.9 | 50.1 | 51.5
Predicates + Decision Tree + Ranking | Symbolic | Yes | No | 55.2 | 69.9 | 74.3 | 43.2 | 51.2 | 52.2
Popper | Symbolic | Yes | Yes | 57.3 | 62.5 | 66.4 | 43.4 | 52.1 | 54.7
Popper + Predicates | Symbolic | Yes | Yes | 57.9 | 63.6 | 68.2 | 43.7 | 52.8 | 55.2
Constrained Clustering | Symbolic | No | Yes | 54.4 | 61.3 | 65.9 | – | – | –
TUTA for Cell Type Classification | Neural | No | Yes | 57.1 | 63.5 | 67.8 | – | – | –
TAPAS + Cell Classification | Neural | No | Yes | 40.1 | 52.2 | 55.2 | – | – | –
BERT + Cell Classification (Custom) | Neural | No | No | 37.8 | 53.4 | 57.8 | – | – | –
Cornet | Neuro-symbolic | Yes | No | 65.4 | 77.6 | 82.5 | 46.2 | 54.6 | 60.7

##### Baselines

As existing systems do not target CF directly, we adapt as baselines a variety
of symbolic and neural systems designed for general classification or table
tasks. We implemented six symbolic and three neural baselines:

  * •

Three decision tree variants: We fit a standard decision tree, treating user
(un)formatted cells as (negative) positive labels, respectively. Numeric and
datetime columns are fed directly into the decision tree, while text columns
are encoded using an ordinal label encoder. We explore variants of this
baseline where we learn a decision tree over our generated predicates ($P$)
and add our ranker. We report the best performance across hyper-parameters.

  * •

Popper (Cropper and Morel 2020): We use the state-of-the-art inductive logic
programming (ILP) tool by casting CF rules as an ILP problem over the same
space of rules as Cornet. Similar to the decision tree baseline, we consider
raw column values as well as representing these with our generated predicates.

  * •

COP-KMeans (Wagstaff et al. 2001): Learning CF rules can be treated as a
constrained clustering problem. COP-KMeans is a $k$-means based clustering
strategy that supports linkage constraints for clusters.

  * •

TAPAS (Herzig et al. 2020), TUTA (Wang et al. 2020) and TaBERT (Yin et al.
2020): We use three neural table encoders that are trained for different
objectives. TAPAS is a BERT model trained to answer questions over tables,
TUTA is a tree-based transformer, pre-trained (as one of its objectives) for
cell type classification and TaBERT is an encoder trained to summarize table
information. We also present a custom neural baseline which uses cell level
embeddings and a cross attention over formatted and unformatted cells
(detailed architecture in the appendix). Starting from pre-trained versions,
we further train the models on a collection of 50,000 CF rules that are
synthetically generated by randomly formatting cells in unformatted columns
and using Cornet to learn CF rules. We fine-tune on a held-out set of 1650
gold user-written CF rules that were not used for creating benchmarks. Since
these models only predict whether a cell is formatted or not, we only evaluate
them on execution match.

### Q1. Comparison against baselines

Table 4 presents an overview of our results. Cornet outperforms both symbolic
and neural baselines using both rule and execution match metrics. Cornet is
also able to learn CF rules with fewer examples than baselines. We found that
although Cornet consistently learns better rules than the symbolic baselines,
sometimes the neural baselines succeed while Cornet fails. This happens when
Cornet is given very few examples, and as a result, its learning procedure
does not generalize to a more complex rule. For example, to learn a rule with
OR Cornet requires at least 2 formatted examples. Furthermore, unlike neural
models that can color cells arbitrarily, Cornet is bound by a grammar. Because
we design our grammar to capture common CF patterns, Cornet may not support
scenarios that require arbitrary Excel formulas. However, such cases are rare
in practice (11 such cases in our benchmark). The Appendix presents an
extended analysis and a visual comparison of Cornet with baselines on selected
examples.

_Execution versus exact match._ Additional analysis revealed that in 56% of
the cases where Cornet’s generated rules matched in execution, but were not an
exact match, the user written rules could be simplified. To explore Cornet’s
potential to simplify user rules, we created a dataset of 1000 CF rules,
randomly sampled from the held-out data used to fine tune neural baselines. We
found that Cornet can simplify 117 rules by using fewer predicates. Figure 5
presents two examples and further examples can be found in the Appendix.

Figure 5: Examples showing Cornet’s ability to generate simpler rules
equivalent to the user’s rules. The top (red) rule is user-written and the
bottom (black) is Cornet-generated.

### Q2. Impact of Input Configuration

Next we study how Cornet’s performance varies with the number of formatted
examples and unformatted cells.

_The number of formatted examples._ Fig. 6 shows the execution match accuracy
over the number of examples across different column types. The convergence
rates vary significantly per column type. For example, the performance growth
diminishes for Text after 2 examples, but steadily increases for Numeric even
after 14 examples. This is because numeric rules are harder to learn (the
numeric value can be anything from a cell value, an aggregated value, or a
constant). Being aware of such differences is important as we could
proactively suggest text rules after a couple of examples, whereas for numeric
rules we should be more conservative.

Figure 6: Execution match over the number of formatted examples for different
column data types. Cornet has higher accuracy for Text and DateTime columns.
Numeric columns need more examples to converge to the correct rule, given the
larger search space.

_The number of unformatted cells._ When deploying systems like Cornet data
availability might be restricted (e.g., in browsers or on mobile devices),
which led us to investigate the impact of the number of unformatted cells on
Cornet’s performance, as in practice, we have significantly more unformatted
cells than formatted examples. Our results show that performance growth
stabilizes after 30 unformatted cells. Most browsers have at least 30 cells in
their view. Refer to the Appendix for a detailed convergence plot.

### Q3. Impact of design decisions on effectiveness

Table 5: Execution match for the top rule for 1, 3 and 5 user formatted examples (ex.). “–” means the corresponding component is removed, _Iter. Enum._ stands for iterative rule enumeration. Full Cornet outperforms all ablations.  Model | 1 ex. | 3 ex. | 5 ex.
---|---|---|---
Cornet – Clustering | 54.5 | 72.4 | 77.5
Cornet – Iter. Enum. | 60.5 | 73.8 | 80.5
Cornet – Iter. Enum. – Clustering | 52.0 | 70.4 | 75.8
Cornet without negatives | 60.3 | 73.7 | 79.6
Cornet with hard negatives | 62.2 | 75.4 | 80.1
Cornet | 65.4 | 77.6 | 82.5

Our ablation studies, summarized in Table 5, show that different components of
Cornet (clustering, use of positional information through soft negative
examples, iterative rule enumeration through repeated tree learning, and
neurosymbolic ranker) contribute substantially to its performance.

_Clustering and Iterative Rule Enumeration._ We compare Cornet with three
ablated versions (1) without clustering, (2) without iterative rule
enumeration, and (3) without either. The approach without iterative rule
enumeration first enumerates trees but only extracts a rule from the tree with
the highest accuracy on the extended labels (see Algorithm 1). Table 5 shows
that clustering and rule enumeration have the highest impact on performance,
demonstrating the value of our _output-oriented_ synthesis procedure and our
use of iterated tree learning to produce multiple viable rule candidates
(which are then disambiguated by the ranker).

_Hard versus Soft Examples._ We compare the performance of Cornet with: (a) no
negative examples, and (b) treating all negative examples as hard constraints.
As Table 5 shows, performance drops in both cases. Intuitively, negative
examples capture positional information associated with a top down filling
order in columns which is beneficial information for Cornet. However we find
that treating negative examples as hard constraints can lead to overfitting,
and thus negative examples should be treated as soft constraints.

_Neural versus Symbolic Ranker._ We compare Cornet’s neurosymbolic ranker with
two ablated versions (1) a pure symbolic ranker obtained by keeping only the
handpicked features and removing the column encoding module, and (2) a pure
neural ranker obtained by replacing the hand picked features with a CodeBERT
(Feng et al. 2020) encoding of the CF rule. Table 6 shows that Cornet’s ranker
outperforms the symbolic and neural ablations across all Top-k configurations.
Furthermore the execution match accuracy gap between Cornet’s Top-1 and the
oracle ranker (Top-All) is around 6% suggesting that future work should focus
on improving rule enumeration, rather than rule ranking.

Table 6: Execution match within Top-k candidates with 3 formatted examples for different ranking models. Top-All represents the performance of an oracle ranker. Cornet’s ranker improves over both ablated rankers. Ranker | Top-1 | Top-3 | Top-5 | Top-10 | Top-All
---|---|---|---|---|---
Symbolic | 74.3 | 76.1 | 78.4 | 80.6 | 83.7
Neural | 65.7 | 69.2 | 74.5 | 75.6 | 83.7
Cornet | 77.6 | 79.7 | 80.2 | 83.3 | 83.7

## Related Work

Despite the needs for CF in spreadsheet systems, there have been relatively
few formal studies on this feature. (Abramovich et al. 2004) discusses how CF
in Excel can improve the demonstration of mathematical concepts. (Dong et al.
2020) describes CellGAN, a conditional Generative Adversarial Network model
which focuses on borders and alignment of cells to learn hierarchical headers
and data groups in tables. In contrast, Cornet targets value based formatting
of cells and also generates their associated formatting rules.

Cornet uses a program-by-example (PBE) paradigm, which has been popularized by
systems like FlashFill (Gulwani 2011) and FlashExtract (Le and Gulwani 2014).
These systems, which are available in Excel, learn string transformation and
data extraction programs from few input-output examples. (Raza and Gulwani
2017) finds outputs and programs together, while (Natarajan et al. 2019) finds
programs and then ranks them based on output. In contrast, Cornet first
hypothesizes the outputs (cell formats) and then learns the associated rule.
Cornet is the first system to take an “output-first” synthesis approach
motivated by the fact that in this case output space is much smaller than
program space.

In terms of search techniques, (Polozov and Gulwani 2015) uses goal-driven
top-down symbolic backpropagation. This is not applicable in our setting
because the boolean signal (i.e., is a cell in a particular format group) is
too-weak to derive strong-enough constraints to navigate the search space.
Another popular alternative in PBE is bottom-up enumeration (Odena et al.
2021), but our search space is too large.

Past PBE work has ranked programs using program features (Ellis and Gulwani
2017) or output features (Natarajan et al. 2019). Cornet uses a neural ranking
model that combines both the rule (program) and its execution (output).

Neural approaches have previously been applied in various table tasks. For
example, TaBERT (Yin et al. 2020) and TAPAS (Herzig et al. 2020) are popular
Sequential Question Answering systems that use a neural model to encode the
table and query vector. TUTA (Wang et al. 2020) is another system for cell and
table type classification tasks. TabNet (Sun, Rayudu, and Pujara 2021) uses a
neuro-symbolic model to understand relational structure of data in tables by
predicting cell types. Unlike these systems, Cornet targets the task of
learning table formatting rules from examples.

## Conclusion

We introduce the problem of learning conditional formatting rules for
spreadsheet data from user examples. We introduce Cornet, a neuro-symbolic
system that learns such data-dependent rules from few examples. To evaluate
Cornet, we created a benchmark of 968 CF tasks from real Excel sheets. We
compare Cornet to both symbolic and neural approaches on this benchmark and
find that it performs significantly better. This paper opens future work such
as purely predictive CF rule learning and combining multiple input modalities
to capture user formatting intent. This paper also acts as the initial step to
performing more complex analysis such as conditional transformations for data
cleaning, or visualizations. This work shall inspire more research in
automating workflows that include such downstream tasks.

## Acknowledgements

We would like to thank Almog-Ben Kandi, Sophie Gerzie, Avital Nevo, and Yoav
Hayun for their feedback on this research.

## References

  * Abramovich et al. (2004) Abramovich, S.; Sugden, S.; Abramovich, S.; and Sugden, S. J. 2004.  Spreadsheet Conditional Formatting: An Untapped Resource for Mathematics Education.  _Spreadsheets in Education_ , 85105.
  * Barik et al. (2015) Barik, T.; Lubick, K.; Smith, J.; Slankas, J.; and Murphy-Hill, E. 2015.  Fuse: a reproducible, extendable, internet-scale corpus of spreadsheets.  In _2015 IEEE/ACM 12th Working Conference on Mining Software Repositories_ , 486–489. IEEE.
  * Blockeel and De Raedt (1998) Blockeel, H.; and De Raedt, L. 1998.  Top-down induction of first-order logical decision trees.  _Artificial intelligence_ , 101(1-2): 285–297.
  * Cropper and Morel (2020) Cropper, A.; and Morel, R. 2020.  Learning programs by learning from failures.  _CoRR_ , abs/2005.02259.
  * Devlin et al. (2019) Devlin, J.; Chang, M.-W.; Lee, K.; and Toutanova, K. 2019.  BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding.  _ArXiv_ , abs/1810.04805.
  * Dong et al. (2020) Dong, H.; Wang, J.; Fu, Z.; Han, S.; and Zhang, D. 2020.  Neural Formatting for Spreadsheet Tables.  In _Proceedings of the 29th ACM International Conference on Information & Knowledge Management_, CIKM ’20, 305–314. New York, NY, USA: Association for Computing Machinery.  ISBN 9781450368599.
  * Ellis and Gulwani (2017) Ellis, K.; and Gulwani, S. 2017.  Learning to Learn Programs from Examples: Going Beyond Program Structure.  In _IJCAI 2017_.
  * Excel (2022) Excel, M. 2022.  Excel Tech Help Forum.  https://techcommunity.microsoft.com/t5/forums/searchpage/tab/message?q=conditional“%20formatting.  Last Accessed: 2022-06-30.
  * Feng et al. (2020) Feng, Z.; Guo, D.; Tang, D.; Duan, N.; Feng, X.; Gong, M.; Shou, L.; Qin, B.; Liu, T.; Jiang, D.; and Zhou, M. 2020.  CodeBERT: A Pre-Trained Model for Programming and Natural Languages.  _CoRR_ , abs/2002.08155.
  * Fisher and Rothermel (2005) Fisher, M.; and Rothermel, G. 2005.  The EUSES spreadsheet corpus: a shared resource for supporting experimentation with spreadsheet dependability mechanisms.  In _Proceedings of the first workshop on End-user software engineering_ , 1–5.
  * Gulwani (2011) Gulwani, S. 2011.  Automating String Processing in Spreadsheets using Input-Output Examples.  In _PoPL’11, January 26-28, 2011, Austin, Texas, USA_.
  * Gulwani et al. (2020) Gulwani, S.; Le, V.; Radhakrishna, A.; Radicek, I.; and Raza, M. 2020.  Structure interpretation of text formats.  In _Object-Oriented Programming, Systems, Languages & Applications (OOPSLA)_. ACM.
  * Herzig et al. (2020) Herzig, J.; Nowak, P. K.; Müller, T.; Piccinno, F.; and Eisenschlos, J. M. 2020\.  Tapas: Weakly Supervised Table Parsing via Pre-training.  In _Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_. Seattle, Washington, United States.
  * Hurst, Marriott, and Moulder (2005) Hurst, N.; Marriott, K.; and Moulder, P. 2005.  Toward tighter tables.  In _Proceedings of the 2005 ACM symposium on Document engineering_ , 74–83.
  * Kaufman and Rousseeuw (2009) Kaufman, L.; and Rousseeuw, P. J. 2009.  _Finding groups in data: an introduction to cluster analysis_.  John Wiley & Sons.
  * Le and Gulwani (2014) Le, V.; and Gulwani, S. 2014.  FlashExtract: a framework for data extraction by examples.  In _2014 Programming Language Design and Implementation_ , 542–553. ACM.
  * Lee et al. (2018) Lee, K.-H.; Chen, X.; Hua, G.; Hu, H.; and He, X. 2018.  Stacked Cross Attention for Image-Text Matching.
  * Liguori et al. (2022) Liguori, P.; Al-Hossami, E.; Cotroneo, D.; Natella, R.; Cukic, B.; and Shaikh, S. 2022.  Can We Generate Shellcodes via Natural Language? An Empirical Study.  _CoRR_ , abs/2202.03755.
  * Lin (2006) Lin, X. 2006.  Active layout engine: Algorithms and applications in variable data printing.  _Computer-Aided Design_ , 38(5): 444–456.
  * N. (2022) N., J. 2022.  Number of Google Sheets and Excel Users Worldwide.  https://askwonder.com/research/number-google-sheets-users-worldwide-eoskdoxav.  Last Accessed: 2022-07-30.
  * Natarajan et al. (2019) Natarajan, N.; Simmons, D.; Datha, N.; Jain, P.; and Gulwani, S. 2019.  Learning Natural Programs from a Few Examples in Real-Time.  In _AIStats_.
  * Neuwirth and Arganbright (2003) Neuwirth, E.; and Arganbright, D. 2003.  _The Active Modeler: Mathematical Modeling With Microsoft Excel_.  Duxbury Press.
  * Odena et al. (2021) Odena, A.; Shi, K.; Bieber, D.; Singh, R.; and Sutton, C. 2021.  BUSTLE: Bottom-up program-Synthesis Through Learning-guided Exploration.  _ArXiv_ , abs/2007.14381.
  * Padhi et al. (2017) Padhi, S.; Jain, P.; Perelman, D.; Polozov, O.; Gulwani, S.; and Millstein, T. D. 2017.  FlashProfile: Interactive Synthesis of Syntactic Profiles.  _CoRR_ , abs/1709.05725.
  * Poesia et al. (2022) Poesia, G.; Polozov, O.; Le, V.; Tiwari, A.; Soares, G.; Meek, C.; and Gulwani, S. 2022.  Synchromesh: Reliable code generation from pre-trained language models.  _CoRR_ , abs/2201.11227.
  * Polozov and Gulwani (2015) Polozov, O.; and Gulwani, S. 2015.  FlashMeta: A Framework for Inductive Program Synthesis.  _SIGPLAN Not._ , 50(10): 107–126.
  * Raggett, Hors, and Jacobs (1999) Raggett, D.; Hors, A.; and Jacobs, I. 1999.  HTML 4.01 specification, section ‘autolayout algorithm’.
  * Raza and Gulwani (2017) Raza, M.; and Gulwani, S. 2017.  Automated Data Extraction using Predictive Program Synthesis.  In _AAAI 2017_. Association for the Advancement of Artificial Intelligence.
  * Raza and Gulwani (2020) Raza, M.; and Gulwani, S. 2020.  Web data extraction using hybrid program synthesis: A combination of top-down and bottom-up inference.  In _Proceedings of the 2020 ACM SIGMOD International Conference on Management of Data_ , 1967–1978.
  * Sun, Rayudu, and Pujara (2021) Sun, K.; Rayudu, H.; and Pujara, J. 2021.  A Hybrid Probabilistic Approach for Table Understanding.  _Proceedings of the AAAI Conference on Artificial Intelligence_ , 35(5): 4366–4374.
  * Wagstaff et al. (2001) Wagstaff, K.; Cardie, C.; Rogers, S.; and Schrödl, S. 2001.  Constrained K-Means Clustering with Background Knowledge.  In _Proceedings of the Eighteenth International Conference on Machine Learning_ , ICML ’01, 577–584. San Francisco, CA, USA: Morgan Kaufmann Publishers Inc.  ISBN 1558607781.
  * Wang et al. (2020) Wang, Z.; Dong, H.; Jia, R.; Li, J.; Fu, Z.; Han, S.; and Zhang, D. 2020.  Structure-aware Pre-training for Table Understanding with Tree-based Transformers.  _CoRR_ , abs/2010.12537.
  * Yin et al. (2020) Yin, P.; Neubig, G.; Yih, W.-t.; and Riedel, S. 2020.  TaBERT: Pretraining for Joint Understanding of Textual and Tabular Data.  In _Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics_ , 8413–8426. Online: Association for Computational Linguistics.


# An Efficient Generation Method based on Dynamic Curvature of the Reference
Curve for Robust Trajectory Planning

Yuchen Sun, Dongchun Ren, Shiqi Lian, Mingyu Fan, and Xiangyi Teng  Section of
Self-driving Vehicle
Meituan Group, Beijing, China 100102
Email: {sunyuchen03, lianshiqi, rendongchun, fanmingyu,
<EMAIL_ADDRESS>
###### Abstract

Trajectory planning is a fundamental task on various autonomous driving
platforms, such as social robotics and self-driving cars. Many trajectory
planning algorithms use a reference curve based Frenet frame with time to
reduce the planning dimension. However, there is a common implicit assumption
in classic trajectory planning approaches, which is that the generated
trajectory should follow the reference curve continuously. This assumption is
not always true in real applications and it might cause some undesired issues
in planning. One issue is that the projection of the planned trajectory onto
the reference curve maybe discontinuous. Then, some segments on the reference
curve are not the image of any part of the planned path. Another issue is that
the planned path might self-intersect when following a simple reference curve
continuously. The generated trajectories are unnatural and suboptimal ones
when these issues happen. In this paper, we firstly demonstrate these issues
and then introduce an efficient trajectory generation method which uses a new
transformation from the Cartesian frame to Frenet frames. Experimental results
on a simulated street scenario demonstrated the effectiveness of the proposed
method.

##  I INTRODUCTION

Trajectory planning is used to create a safe and smooth trajectory for an
agent (e.g., a robot or a self-driving car) from one state (including the
location, the velocity, the acceleration, the orientation and so on) to
another state under certain constraints or cost functions [1]. There are many
ways to plan a trajectory for an intelligent agent and it is a common practice
to use a reference curve, which is generated off-line, as the target to find
the output trajectory. In this way, the trajectory planning algorithm only
need to follow the given reference curve and does not require the information
of map like signs, turns and so on. To achieve optimality and time efficiency,
many trajectory planning algorithms [2, 3, 4] are developed in Frenet frames
with time to reduce the planning dimension with the help of a reference curve.
In a Frenet frame, finding the optimal trajectory is essentially a three
dimensional constrained optimization problem.

There are roughly two types of trajectory planning algorithms: the direct
methods [5, 6] that use trajectory sampling or lattice search to find the
optimal trajectory and the path-speed decoupled methods [7, 8] that optimize
path and speed separately. In both of the methods, all obstacles and
environment information are projected onto the lane center based Frenet frames
for each candidate lane, and the drivable area is bounded by lane boundaries.
When using the Frenet frame, a projection operator which identifies the
corresponding projection point on the reference curve is always required and
used as the transformation from the Cartesian frame to Frenet frames. The most
widely used projection operator is defined as the nearest point on the
reference curve, which is also the orthogonal projection point. Given a
reference curve, there are two sub-tasks in trajectory planning that a
projection operator is necessary, which are:

  * •

Reference curve following: One has to determine whether a candidate trajectory
is actually following the lane by checking its projection on the reference
curve.

  * •

Trajectories generation: One need to generate as many as possible candidate
trajectories that follows the reference curve for subsequent planning and
optimization.

However, under certain circumstances, the projection of a candidate trajectory
onto the reference curve maybe discontinuous [3, 4] , which is commonly
ignored in real applications. Some continuous segments on the reference curve
could not be mapped back onto the generated trajectory and make the first sub-
task difficult. Moreover, trajectories generated by previous methods might
self-intersect when continuously following a simple reference curve. The
generated trajectories might be unnatural and suboptimal trajectories for the
second sub-task. These discussed issues motivate us to develop novel a
trajectory generation method that could produce reasonable candidate
trajectories under most of the circumstances. In this paper, based on our
theoretical result on trajectory following, the derived method could generate
trajectories that guarantee smooth, anomaly free, and follow the reference
curve always.

Figure 1: An illustration of the transformation from Cartesian frame to Frenet
frames

##  II RELATED WORK

The past decades have witnessed a great progress in trajectory planning. Many
researches have been proposed and studied [3], [9, 10, 11] that they can
generate global trajectories connecting a start and a possibly distant end
state. Some approaches for trajectory planning follow a discrete sampling or a
road map-based scheme [12] [13], which firstly sample multiple rows of points
and then generate a finite set of trajectories with cost values, typically by
differential functions that describe vehicle dynamics and kinematics. A
candidate trajectory is selected if and only if it corresponds to the minimal
cost value.

Kelly and Nagy [14] proposed an efficient path planning algorithm which
employs polynomials to ensure the smooth variation of the curvature. Based on
this method, a new approach proposed in [6] firstly samples points along the
reference lane and then connects the sampled points using polynomials. In this
way, all generated candidate trajectories conform to the lane shape. However,
these methods use Cartesian coordinate system rather than the Frenet frames.
Therefore, the planning dimension is relatively high and the optimization is
complicated.

To address the issue, Werling et al. [3] used the lane center line based
Frenet frames to decouple the lateral and longitudinal motion. This strategy
makes the reference curve coincide with the lane shape. Based on Frenet frame,
the generation of the lateral and longitudinal motions can be achieved
separately by using quintic polynomials versus time, which ensures continuous
acceleration. Given the advantages of the Frenet frames, many trajectory
planning methods [4, 15] are proposed based on it and achieve a roaring
success in addressing various planning problems in real applications. However,
most of the methods ignore an intrinsic problem in the transformation from
Cartesian frame to Frenet frames, which may cause unnatural and suboptimal
trajectories for the downstream tasks. In this paper, based on our theoretical
result on trajectory following, the proposed method could generate candidate
trajectories following the reference curve and guarantee smoothness and
anomaly free.

Figure 2: The representation of a candidate trajectory in a Frenet frame

##  III Preliminaries and Our Theoretical Results

(a) discontinuous

(b) self-interact

Figure 3: The issues of discontinuous projection operator p, (a) multiple
outputs for a single $\vec{x}$, and the projection of $L_{1}$ onto $L2$ is
discontinuous, (b) a suboptimal trajectory when following the reference curve
faithfully. $L_{1}$ is a candidate trajectory and $L_{2}$ is the reference
curve

###  III-A The Frenet Frame

A reference curve is always defined by parametric curves [16][17] such as the
spline curve. When $s(t)$ (or $s$ for short) is the modular length of time
$t$, we assume the vector function $\vec{r}(s)$ denotes a moving point on the
reference curve $L$ in Euclidean space. Let $\vec{t}_{r}(s)$ and
$\vec{n}_{r}(s)$ are the unimodular tangent vector and normal vector at
$\vec{r}(s)$, respectively. Then,
$\left\\{\vec{t}_{r}(s),\vec{n}_{r}(s)\right\\}$ formulates a dynamic
orthogonal coordinate system. For any Cartesian coordinates $\vec{x}$,
assuming $\vec{r}(s)$ is the root point of $\vec{x}$, we have

$\displaystyle\vec{x}(s,k_{x},d_{x})=\vec{r}(s)+k_{x}\vec{t}_{r}(s)+d_{x}\vec{n}_{r}(s),$
(1)

where $k_{x}=k_{x}(t)$ and $d_{x}=d_{x}(t)$ are the horizontal and
perpendicular offsets, respectively. And the frenet coordinates of $\vec{x}$
can be denoted by $(s,k_{x},d_{x})$. Figure 1 is an example of a Frenet frame.
To simplify the expression, one common practice is to use the nearest point to
$\vec{x}$ on $L$ as the root point, such that $k_{x}=0$. Then the Frenet
coordinate of $\vec{x}$ can be denoted by $(s(t),d_{x}(t))$ and the
corresponding projection operator p of $\vec{x}$ onto $L$ is $s(t)$. That is
to say, the projector ${\bf p}$ satisfies:

$\displaystyle{\bf p}(\vec{x})=s(t).$ (2)

###  III-B The Projection Operator

Considering $L_{2}$ be the reference curve and the $L_{1}$ is a candidate
trajectory of a moving agent, there are two implicitly ideal
properties/desirable assumptions of the projection operator p for trajectory
planning tasks [3], which are summarized as below.

  * •

p is a continuous and smooth projector such that the image (math) of a
continuous segment on $L_{1}$ should be a continuous interval on $L_{2}$.

  * •

The moving agent on the candidate trajectory $L_{1}$ should be actually
following the reference curve $L_{2}$, which can be mathematically represented
as $\langle\dot{{\bf p}}(\vec{x}),\vec{t}_{r}(s)\rangle>0$.

However, the definition of the projection operator p given in (2) is
incomplete and the neither of the two desired properties is guaranteed in most
of the previous motion planning studies. That means that it may have several
outputs at some point $\vec{x}$ when following the given reference curve
$L_{2}$. Fig. 3(a) presents a reference curve with a 90 degrees turn. When a
virtual agent on $L_{1}$ moves into the turn with a reasonable large distance
to the reference curve $L_{2}$, the trajectory $L_{1}$ should be contained in
the available set for optimization. If the projection operator p is
continuous, the image of p should contain all segment between $A_{2}$ and
$B_{2}$. As can be seen, the point $X$ on $L_{2}$ is not the projection of any
point from $L_{1}$ and this violates the assumption that p is continuous. Fig.
3(b) presents an example in path following. The reference curve has a rotation
arc whose radius is $R$. The virtual agent is following $L_{2}$ continuously
with the constraint that the lateral distance is constant $d_{x}(t)=2R$. When
the agent moves from $B_{1}$ to $A_{1}$, the direction of its movement on the
candidate trajectory is opposite with the direction of projection point on the
reference curve.

###  III-C Our Theoretical Results

To address the intrinsic issues of the definition of the projection operator
p, the curvature $\kappa$ is required to develop a novel transformation, to
replace the original projection operator $\mathbf{p}$, from Cartesian
coordinates to Frenet coordinates. Our method is based on the following
theoretical result.

###### Theorem III.1

Let $L_{2}$ be the reference curve and $\vec{x}$ be any point (an agent) on
the candidate trajectory $L_{1}$. $\vec{r}(t)$ is the nearest point on $L_{2}$
to $\vec{x}$ and $\kappa d_{x}(t)<1$ , then $\vec{r}-\vec{x}$ is perpendicular
to the tangent $\vec{t}_{r}(t)$ and the agent is actually following $L_{2}$ at
the same direction.

The theorem III.1 indicates that the projection point $\vec{r}(t)$ follows
reference curve $L_{2}$ at the same direction if and only if $\kappa
d_{x}(t)<1$. Moreover, $\vec{r}(t)$ will jump and be discontinuous on $L_{2}$
at these points where the curvature $\kappa$ is large. If a method can handle
the discontinuous points properly and guarantee $\kappa d_{x}(t)<1$, it can
generate the smoothness of the generated trajectories which follow the
reference curve at the same direction.

For the convenience the downstream optimizers, it is a common practice to
discretize the reference curve in the form of vectors. The discretization is
realized through point sampling on the reference curve. The sampling points on
the curve is connected into a polygonal line, where the sampling points are
sequenced in the order of their distance to one end point of the curve. The
obtained polygonal line is used to represent the original curve. To avoid the
intractable cases such as sharp angles and fractals, the following empirical
conditions should be satisfied in the sampling process:

  * •

The distance between two adjacent samples should be extremely smaller than
$1/\kappa$.

  * •

The angle between two adjacent sample points should not exceed 10$\degree$.

  * •

The distances between every pair of adjacent samples are identical.

It should be noted that the polygonal line has finite length due to the
limitations of sampling size. As a result, the obtained polygonal line that is
built by line segments is not enough to ensure that the normal line at each
point on the reference curve go through of it. To deal with this, the linear
extension strategy [18] is adopted to extend the polygonal line. Specifically,
the first and last segments on the polygonal line are extended to rays with
infinite length.

Algorithm 1 The Projection Operator: TransF-$\kappa$

0: The polygonal line in the form of vectors:
$U=\\{L_{c}:(x_{c},y_{c})|c=1,2,...,M\\}$ , which is formulated by sampling
points from the reference curve $L$ ($M$ denotes the sampling size); the
Cartesian coordinates of a point $A:(x_{A},y_{A})$.

0: The Frenet coordinate of $A:(s_{A},d_{A})$

1: Compute the distances between $A$ and all points in $U$.

2: Identify all the points in $U$ that have the identical and the nearest
distance to $A$, which form a subset $N$.

3: Choose the point $L_{m}$ such that $m=\arg\max c:L_{c}\in N$, i.e., the
biggest index from subset $N$.

4: if $L_{m}$ is not an end point then

5: $v_{+}=\langle\overrightarrow{L_{m}A},\overrightarrow{L_{m}L_{m+1}}\rangle$
# where $\overrightarrow{X_{1}X_{2}}=X_{2}-X_{1}$ is the difference of the
coordinates of two points

6: $v_{-}=\langle\overrightarrow{L_{m}A},\overrightarrow{L_{m}L_{m-1}}\rangle$
# where $\langle\cdot,\cdot\rangle$ is the inner product of two vectors

7: if $v_{-}<v_{+}$ then

8: $m=m+1$

9: end if

10: ($s_{A},d_{A}$)=AffineTrans$(A,m,U)$ # Algo 2

11: else

12: ($s_{A},d_{A}$)=ParallelTrans$(A,m,U)$ # Algo 3

13: end if

14: return $A:(s_{A},d_{A})$

Algorithm 2 Affine Transform

0: The polygonal line in the form of vectors:
$U=\\{L_{c}:(x_{c},y_{c})|c=1,2,...,M\\}$ ($M$ denotes the sampling size); the
index $m$ of the reference piece; The Cartesian coordinates of a point
$A:(x_{A},y_{A}$)

0: The Frenet coordinate of $A:(s_{A},d_{A})$

1: Get the heading vector $\vec{b_{1}}$ of the angular bisector at the
junction $L_{m-1}$.

2: Get the heading vector $\vec{b_{2}}$ of the angular bisector at the
junction $L_{m}$.

3: if $\vec{b_{1}}$ is parallel to $\vec{b_{2}}$ then

4: ($s_{A},d_{A}$)=$ParallelTrans(A,m,U)$

5: else

6: $s_{m-1}=\sum_{i=1}^{m-1}\Arrowvert\overrightarrow{L_{i-1}L_{i}}\Arrowvert$

7: Calculate the intersection point $O$ of the two angular bisectors, which go
through points $L_{m-1}$ and $L_{m}$ with headings $\vec{b_{1}}$ and
$\vec{b_{2}}$, respectively.

8: Calculate the intersection point $P$ of line $\overrightarrow{OA}$ and
$\overrightarrow{L_{m-1}L_{m}}$.

9: $s_{A}=s_{m-1}+\Arrowvert\overrightarrow{L_{m-1}P}\Arrowvert$

10: $d_{A}=$ distance from $A$ to the line $L_{m-1}L_{m}$.

11: end if

12: return ($s_{A},d_{A}$)

Algorithm 3 Parallel Transform

0: The polygonal line in the form of vectors:
$U=\\{L_{c}:(x_{c},y_{c})|c=1,2,...,M\\}$ ($M$ denotes the sampling size); the
index $m$ of the reference piece; The Cartesian coordinates of
$A:(x_{A},y_{A}$)

0: The Frenet coordinate of $A:(s_{A},d_{A})$

1: if $m=$ 0 then

2: Denote $\overrightarrow{L_{0}L_{1}}$ as $\vec{E}$.

3: Set $s_{A}=0$.

4: Denote $\overrightarrow{L_{0}A}$ as $\vec{V}$

5: else

6: Denote $\overrightarrow{L_{m-1}L_{m}}$ as $\vec{E}$

7: Set
$s_{A}=\sum_{i=1}^{m-1}\Arrowvert\overrightarrow{L_{i-1}L_{i}}\Arrowvert$

8: Denote $\overrightarrow{L_{m-1}A}$ as $\vec{V}$

9: end if

10: Let $\vec{E}_{\perp}$ be a nonzero orthogonal vector to $\vec{E}$ such
that $\langle\vec{E}_{\perp},\vec{E}\rangle=0$.

11: $s_{A}=s_{A}+\vec{V}\cdot\vec{E}/\Arrowvert\vec{E}\Arrowvert$.

12:
$d_{A}=|\langle\vec{V},\vec{E}_{\perp}\rangle/\Arrowvert\vec{E}_{\perp}\Arrowvert|$

13: return ($s_{A},d_{A}$)

##  IV The Proposed Method

In this section, we propose a new efficient trajectory generation method such
that the generated candidate trajectories are smooth and guarantees to follow
the reference curve at the same direction. The method is developed based on a
new projection operator, TransF-$\kappa$, from the Cartesian frame to Frenet
frames.

###  IV-A Our Projection Operator: TransF-$\kappa$

Based on the theorem III.1 and sampling requirements, it is intuitive and
natural to project a moving point onto the nearest point on the reference
curve $L$. However, there may be several nearest projection points with the
identical distance. In our projection operator: TransF-$\kappa$, we choose the
projection point with the biggest $s$ to ensure that the moving point is
actually following at the same direction with $L$, where $s$ denotes the
distance on curve from the projection point to the start point on $L$.
Algorithm 1 shows the details of TransF-$\kappa$, the transformation from a
Cartesian coordinates to the Frenet coordinate of an arbitrary point.

In Algorithm 1 lines 1-2, we first pick out all points on $U$ which are the
nearest to $A$ and form a set containing all such points. Then we choose the
last one, i.e. one whose index is the biggest. At line 3, This point with the
biggest $s$ is used and the output trajectory is shorten. With the point
$L_{m}$, lines 5-9 decide A should be projected to the former or latter
adjacent piece to $L_{m}$. The condition at line 7 identifies which side $A$
should be projected on. The inverse image of two pieces are separated by the
angular bisector at $L_{m}$. Finally, lines 10-12 are used to calculate the
projection point. The Affine Transform given in Algorithm 2 is applied on the
pieces of $U$ without linear extension while the Parallel Transform given in
Algorithm 3 is employed on the extended pieces of $U$. One significant
difference between these two operators is that the inverse image of common
pieces is bounded by two angular bisectors while the extended pieces is
bounded by only one angular bisector. The calculation approaches of the
projection results are based on these two situations. The details of Affine
Transform operator and Parallel Transform operator are given in Algorithm 2
and 3, respectively.

Further discussions about Algorithm 2 and 3 should be made for clarification.
As can be seen, both Affine and Parallel Transform are approximation to the
transform function Eq. (1) in Section III. The reason why we need the
approximation methods are that the polygonal line $U$ as a sampled
approximation for reference curve $L$ is no longer smooth and thus there is no
curvature, tangent vector and so on. Therefore, two approximation operators
are used to make the lateral distance $d$ vary continuously when the point $A$
moves cross an angular bisector. In other words, they guarantee that point $A$
on an angular bisector has the same projection point on $U$ no matter it is
projected to the former or latter piece. However, since they are approximation
methods, some error may occur. An apparent error is that the created
coordinate system may not be orthogonal to the reference curve. That is why we
introduce some sampling conditions which should be satisfied in Section III.C.
Those conditions ensure that the approximation errors are small enough to be
ignored and make them work well in real-world applications.

Algorithm 4 A Commonly-used Continuous Candidate Trajectory Generation Method
(May cause self-interaction!)

0: The polygonal line in the form of vectors:
$U=\\{L_{c}:(s_{c},d_{c}=0)|c=1,2,...,M\\}$ ($M$ denotes the sampling size);
Vectors of the lateral boundaries at the sample points: $B_{c}=[a_{c},b_{c}]$,
$c=1,2,...,M$.

0: A candidate trajectory $T$ consisted of vectors of $M$ points:
$T=\\{T_{c}:(s_{c}^{\prime},d_{c}^{\prime})|c=1,2,...,M\\}$

1: $i=0$

2: $T=\varnothing$

3: while $i<M$ do

4: $i=i+1$

5: $d_{i}^{\prime}$= randomly pick a number between $a_{i}$ and $b_{i}$

6: $s_{i}^{\prime}=s_{i}$

7: $T=T\cup(s_{i}^{\prime},d_{i}^{\prime})$

8: end while

9: return A candidate trajectory $T$

Algorithm 5 The Proposed Trajectory Generation Method

0: An $n$-order differentiable reference curve $L$; The polygonal line in the
form of vectors: $U=\\{L_{c}:(s_{c},d_{c}=0)|c=1,2,...,M\\}$; The candidate
trajectory of $M$ points:
$T=\\{T_{c}:(s_{c}^{\prime},d_{c}^{\prime})|c=1,2,...,M\\}$ which is generated
by Algo 4.

0: A renewed candidate trajectory $T^{\prime}$ from $T$: $T^{\prime\prime}$=
$\\{T_{c}^{\prime\prime}(s_{c}^{\prime\prime},d_{c}^{\prime\prime})|c=1,2,...,M\\}$

1: $i=0$

2: $T^{\prime\prime}=\varnothing$

3: while $i<M$ do

4: $i=i+1$

5: Calculate $\kappa$ = curvature of $L$ at $L_{i}$($s_{i}$).

6: if $\kappa d_{i}^{\prime}<1$ then

7: $T^{\prime\prime}=T^{\prime\prime}\cup(s_{i}^{\prime},d_{i}^{\prime})$

8: else

9: Calculate the Euclidean coordinates of Frenet coordinates
$(s_{i}^{\prime},d_{i}^{\prime})$, which is denoted as $(x_{i},y_{i})$.

10: Calculate the Frenet coordinates of $(x_{i},y_{i})$ referring to $U$,
$(s_{i}^{\prime\prime},d_{i}^{\prime\prime})$ = TransF-$\kappa$
(U,$(x_{i},y_{i})$).  # Algo1

11:
$T^{\prime\prime}=T^{\prime\prime}\cup(s_{i}^{\prime\prime},d_{i}^{\prime\prime})$

12: $i=min\\{i|s_{i}^{\prime}>s_{i}^{\prime\prime}\\}$

13: end if

14: end while

15: return A renewed trajectory $T^{\prime\prime}$ from $T^{\prime}$

###  IV-B Our Trajectory Generation Algorithm

Trajectory generation is a key step in trajectory planning in dynamic and
unknown environments. The downstream trajectory optimizer [19] may fail to
create an acceptable trajectory plan that obeys traffic rules and without
misleading directions (such as self-interactions) when the input candidate
trajectories are sloppy. Algorithm 4 is a common framework for trajectory
generation. Many sophisticated generation methods can be extended from
Algorithm 4. Without loss of generality, we choose Algorithm 4 as the basis of
our generation method.

As discussed in Section III, Algorithm 4 and the related sophisticated
generation methods will produce candidate trajectories with misleading
directions and self-interaction when the curvature is large and the gap of the
corridor boundaries is wide. Typical examples can be found in Fig. 3.

To ensure the candidate trajectory is actually following at the same direction
as the reference curve, our method introduce the curvature $\kappa$ that
$\kappa d_{x}(t)<1$ as an additional restriction condition to repair the
generated trajectories by Algorithm 4. Algorithm 5 is our proposed trajectory
generation method which uses the outputs of Algorithm 4.

The inputs of Algorithm 5 include the $n$-order differentiable reference curve
$L$. The curvature $\kappa$ at any points on $L$ can be calculated by
$\kappa=\langle\dot{t_{r}},n_{r}\rangle$, where $t_{r}=\vec{t_{r}}(s)$ and
$n_{r}=\vec{n_{r}}(s)$ are the uni-modular tangent and normal vectors at
$\vec{r}_{s}$ on $L$, respectively (the same notations as in Section III.A).
The input of Algorithm 5 $T$ is an output of Algorithm 4, which might consist
of misleading directions and self-interactions. The output of Algorithm 5 is a
renewed candidate trajectory $T^{\prime}$, which is repaired from $T$. At the
line 5 of algorithm 5, the curvature at the sampling point $L_{i}$ is
calculated. If $\kappa d_{i}^{\prime}<1$, it is safe to include the point
$T_{i}:(s_{i}^{\prime},d_{i}^{\prime})$ into the candidate trajectory.
Otherwise, at lines 9-12, the point have to be transformed into the Cartesian
frame and then transformed back into the Frenet frame. Because several nearest
points to $(x_{i},y_{i})$ might be identified in $U$,
$(s_{i}^{\prime\prime},d_{i}^{\prime\prime})$ is different with
$(s_{i}^{\prime},d_{i}^{\prime})$. In this way, the segment on reference curve
$L$ with high curvature $\kappa$ is jumped over and the obtained new point is
safe to be included into $T^{\prime\prime}$.

##  V SIMULATION STUDY AND DISCUSSION

Figure 4: The sub-figures shown in (a)-(d) illustrate a result of trajectory
planning by Algorithm 4 . The sub-figures shown in (e)-(h) present a result of
trajectory planning by Algorithm 5.

In this section, we create an artificial environment for trajectory planning.
The generation algorithms 4 and 5 are used and compared in trajectory
planning. High resolution video clips of these experimental results have been
uploaded as supplement materials.

###  V-A Experimental settings

In our planning environment, an U shaped curved road is assumed and the lane-
center curve is provided. Additionally, a static obstacle is placed near the
corner of the road to mimic parking cars or road blockers. A moving agent is
required to move from one end point of the road center to the other end point.
The moving agent should follow the lane-center curve smoothly and avoid the
obstacle.

The detailed trajectory planning consists of the following steps:

  * •

Implement candidate trajectory generation method multiple times to create many
candidate trajectories. (Algorithm 4 or Algorithm 5)

  * •

Use the constrained planning optimizer to generate the final planed
trajectory.

###  V-B Experimental results and discussions

We recorded the whole simulation process of the planning and movement of the
moving agent in the form of videos. Screenshots of several representative time
stamps from the videos are from collected and shown in Fig. 4. The blue curve
denotes the lane center line and also the reference curve. The moving agent is
represented as a triangle and its planned trajectory is shown as the red line.
The obstacle is denoted as black cross marks.

Figs. 4(a)-(e) are the screenshots from the experimental results based on
Algorithm 4 for trajectory generation. Fig. 4(a) is the initial state, where
the planned trajectory works well. However, in Fig. 4(b), the planned
trajectory is heading the opposite with the reference curve. The reason why
such a situation occurs is that at this moment there exists multiple points on
reference curve (lane center line) which have the same nearest distance to the
last point of trajectory. Since Algorithm 4 randomly samples the points from
the reference curve, it may choose a wrong projection point and thus follow
the opposite direction to the reference curve. Figs. 4(c) and (d) are the
consequences of this issue when the moving agent continues to move forward.
Apparently, the generated trajectories is unnatural and unacceptable for a car
to execute. Actually, the issue occurs frequently and may cause serious
accidents when an autonomous vehicle passing a U-shaped curved road.

For comparisons, the results of trajectory planning based on Algorithm5 have
been shown in Fig. 4(f)-(g). Fig. 4(f) is the initial state of the moving
agent and the planned trajectory is more reasonable than the one shown in Fig.
4(a). Then, instead of randomly picking a number, Algorithm 5 decides whether
the requirement of product of$\kappa$ and lateral distance is smaller than 1
is successfully satisfied. If not, it uses Algorithm 1 to calculate the Frenet
coordinate. Subsequently, Algorithm 5 manages to address the problem caused by
Algorithm 4 by choosing the biggest index among those nearest points. As a
result, the Fig. 4(f) shows a more reasonable planned trajectory. Fig. 4(g)
and (h) are the following steps of the moving agent which successfully passes
the obstacle and follows the U-shaped curved road.

##  VI CONCLUSION

Classic trajectory planning algorithms with Frenet frame make a common
implicit assumption that any segment on the reference curve is the image
(math) of some part of the planned trajectory, which means the agent should
follow the reference curve continuously. However, this assumption is not
always true in practice and it may cause some serious issues.

In this paper, we study and analyze these issues and discussed their possible
consequences in details. Then we propose an efficient candidate trajectory
generation algorithm where a new projection operator from the Cartesian frame
to Frenet frame is used. The new trajectory generation method is able to
generate as many as possible candidate trajectories that follows the reference
curve at the same direction for subsequent planning and optimization. As far
as we know, it is the first time that a trajectory generation method is
proposed with the constrain of $\kappa d<1$. The proposed trajectory planning
algorithm enjoys the same computational time complexity as the classic
algorithms and has been successfully applied in our real practice.

## References

  * [1] W. Zhan, J. Chen, C. Chan, C. Liu, and M. Tomizuka, “Spatially-partitioned environmental representation and planning architecture for on-road autonomous driving,” in _2017 IEEE Intelligent Vehicles Symposium (IV)_ , 2017, pp. 632–639.
  * [2] J. Fickenscher, S. Schmidt, F. Hannig, B. Bouzouraa, and J. Teich, “Path planning for highly automated driving on embedded gpus,” _Journal of Low Power Electronics and Applications_ , vol. 8, no. 35, 2018.
  * [3] M. Werling, J. Ziegler, S. Kammel, and S. Thrun, “Optimal trajectory generation for dynamic street scenarios in a frenét frame,” in _IEEE International Conference on Robotics and Automation_ , 2010.
  * [4] A. Oulmas, N. Andreff, and S. Regnier, “Chained formulation of 3d path following for nonholonomic autonomous robots in a serret-frenet frame,” in _American Control Conference_ , 2016.
  * [5] J. Ziegler and C. Stiller, “Spatiotemporal state lattices for fast trajectory planning in dynamic on-road driving scenarios,” in _2009 IEEE/RSJ International Conference on Intelligent Robots and Systems_ , 2009, pp. 1879–1884.
  * [6] M. Mcnaughton, C. Urmson, J. M. Dolan, and J. W. Lee, “Motion planning for autonomous driving with a conformal spatiotemporal lattice,” in _IEEE International Conference on Robotics and Automation_ , 2011.
  * [7] Tianyu Gu, J. Atwood, Chiyu Dong, J. M. Dolan, and Jin-Woo Lee, “Tunable and stable real-time trajectory planning for urban autonomous driving,” in _2015 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)_ , 2015, pp. 250–256.
  * [8] H. Fan, F. Zhu, C. Liu, L. Zhang, L. Zhuang, D. Li, W. Zhu, J. Hu, H. Li, and Q. Kong, “Baidu apollo EM motion planner,” _CoRR_ , vol. abs/1807.08048, 2018. [Online]. Available: http://arxiv.org/abs/1807.08048
  * [9] O. Ljungqvist, N. Evestedt, D. Axehill, M. Cirillo, and H. Pettersson, “A path planning and path-following control framework for a general 2-trailer with a car-like tractor,” _Journal of Field Robotics_ , vol. 36, no. 8, 2019.
  * [10] C. Wriedt and C. Beierle, “Implementation of trajectory planning for automated driving systems using constraint logic programming,” in _11th International Conference on Agents and Artificial Intelligence_ , 2019.
  * [11] T. Heil, A. Lange, and S. Cramer, “Adaptive and efficient lane change path planning for automated vehicles,” in _IEEE International Conference on Intelligent Transportation Systems_ , 2016.
  * [12] H. SChoset, K. Lynch, S. Hutchinson, G. Kantor, W. Burgard, L. Kavraki, and S. Thrun, _Principles of Robot Motion: Theory, Algorithms, and Implementations_. MIT Press: Cambridge, MA, USA, 2005.
  * [13] L. Jaillet, J. Cortés, and T. Siméon, “Sampling-based path planning on configuration-space costmaps,” _IEEE Transactions on Robotics_ , vol. 26, no. 4, pp. 635–646, 2010.
  * [14] A. Kelly and B. Nagy, “Reactive nonholonomic trajectory generation via parametric optimal control,” _The International journal of robotics research_ , vol. 22, no. 7/8, pp. p.583–601, 2003.
  * [15] M. Fu, T. Wang, Y. Xu, and S. Gao, “Path-following control of an underactuated hovercraft with dynamic uncertainties under serret-frenet frame,” in _36th CHinese Control Conference (CCC)_ , 2017.
  * [16] E. Abbena, A. Gray, and S. Salamon, “Modern differential geometry of curves and surfaces with mathematica, fourth edition,” _American Mathematical Monthly_ , vol. 26, no. 1, pp. 203–208, 2016.
  * [17] M. Berger and B. Gostiaux, _Differential Geometry: Manifolds, Curves, and Surfaces_. Springer Science and Business Media, 2012.
  * [18] Y. Brudnyi and P. Shvartsman, “The whitney problem of existence of a linear extension operator,” _Journal of Geometric Analysis_ , vol. 7, no. 4, pp. 515–574, 1997.
  * [19] L. Huiying, H. Shaoping, and G. Yuxian, “Robot continuous trajectory planning based on frenet-serret formulas,” in _International Conference on Computer, Mechatronics, Control and Electronic Engineering_ , 2010.