Precise but Natural Specifications for Robot Tasks

arXiv:1803.02238v1 [cs.RO] 6 Mar 2018

Brendon Boldt1

Ivan Gavran2

Abstract— We present Flipper, a natural language interface
for describing high level task specifications for robots that are
compiled into robot actions. Flipper starts with a formal core
language for task planning that allows expressing rich temporal
specifications and uses a semantic parser to provide a natural
language interface. Flipper provides immediate visual feedback
by executing an automatically constructed plan of the task
in a graphical user interface. This allows the user to resolve
potentially ambiguous interpretations. Flipper extends itself via
naturalization: users of Flipper can define new commands,
which are generalized and added as new rules to the core
language, gradually growing a more and more natural task
specification language. Unlike other task-specification systems,
Flipper enables natural language interactions while maintaining
the expressive power and formal precision of a programming
language. We show through an initial user study that natural
language interactions and generalization can considerably ease
the description of tasks. Moreover, over time, users employ
more and more concepts outside of the initial core language.
Such extensions are available to the Flipper community, and
users can use concepts that others have defined.

I. I NTRODUCTION
With a long-anticipated migration of robots from factories
to homes and offices, bridging the gap between tasks defined
in a high-level, natural language and plans implemented
on physical robots navigating a dynamic environment has
become one of the fundamental challenges in robotics.
Research in planning has focused on precise programming
languages for robot tasks. These languages are expressive,
have a clear semantics, and plans can be automatically generated [1]–[6]. Unfortunately, the precision of such languages
comes with unforgiving syntax. Thus, it is hard for end-users
to translate tasks in a natural language to valid programs.
The usual mechanism to incorporate natural language is to
add a fixed set of “syntactic sugar” to express commands
in a structured subset [7]. On the other hand, advances in
natural language processing have enabled rich models of
natural language to be built, but the application to robot task
planning is usually limited to a fixed set of the most common
scenarios [8]–[10]. Thus, users are either limited to a handful
of natual language idioms, or they can use their language
freely, but the robot can only do a handful of actions.
In this paper, we present Flipper, a system for end-users to
program mobile robots using natural language. The core of
Flipper is a high-level formal programming language for task
specification. A semantic parser [11] translates natural language utterances into internal representations for programs,
allowing more flexibility in specifying tasks. While the
1 Marist College, USA, 2 Max Planck Institute for Software Systems,
Germany
Brendon Boldt was supported by a DAAD RISE Internship.

Eva Darulova2

Rupak Majumdar2

Fig. 1: Simulation world of Flipper

core language is always available to programmers, Flipper
further allows to extend the capability of the language and
parsing through a process of naturalization [12]. Whenever
the semantic parser fails to parse an utterance, the user
can define the new utterance in terms of a sequence of
utterances already understood (i.e., parseable) by the system.
The semantic parser generalizes the definition and adds it as
a set of new production rules in the underlying language.
Thus, over time, Flipper builds up a large lexicon of defined
concepts through user interaction and generalization. Initial
users program in the core language, but build up idioms natural to the domain; future users can use all concepts defined
by the community previously. Along the way, each parsed
form retains the precise semantics of the core language.
Thus, Flipper helps bridge the gap between expressive and
precise programming languages with restricted syntax and
the flexible but ambiguous natural language. While defined
concepts are the usual way to express a formal language,
for example using the library mechanism in a programming
language, Flipper exploits two key features of the robotics
domain. First, it can provide quick visual feedback to the user
about the effect of an utterance by simulating the plan on the
world. This allows quick resolution of ambiguity. Second,
unlike a library in a general purpose language, in which
a programmer parameterizes a function explicitly, Flipper
uses grammar induction within the parser to generalize from
concrete utterances. While grammar induction may not be
powerful enough for general-purpose computation, it works
remarkably well in the restricted context of planning worlds.
Interacting with Flipper Let us be more specific. The
user of Flipper instructs a single robot which moves in
a world consisting of several connected rooms separated
by walls, presenting obstacles for the robot. These rooms
contain a number of items with different properties; for

simplicity we consider here different colors and shapes. The
robot can modify this world by moving to free locations,
and by applying a set of actions, such as picking up or
dropping items. Figure 1 shows a simulation of such a
world. The user specifies actions for the robot as an utterance. For example, the utterance (in the core language)
visit world containing item has color blue instructs the robot
to visit some point that contains a blue item. Flipper parses
the utterance into a task specification in the core language,
constructs a plan over the simulated world, and provides
visual feedback first, showing what the robot would do. This
is especially useful if there are multiple possible interpretations, e.g., due to ambiguities in the semantic parsing.
Once the user selects an interpretation, the robot proceeds
with an action (ideally, in the real world; in our current
implementation, still in simulation).
In case the plan is unrealizable, the user receives feedback
specifying which primitive part of the action is not realizable.
It is possible, however, that Flipper is not able to parse
a command. For example, the user might state “visit blue
item” to specify the same task in a more natural way. In this
case, Flipper asks the user to define this utterance in terms of
one or more parseable commands already understood by the
system. This is the situation in Figure 1. Flipper generalizes
the definition and creates new grammar rules. Thus, it can
now also understand the utterance “visit red item.”
We have implemented Flipper on top of Sempre [11], the
trainable semantic parser, its interactive version introduced
by the Voxelurn naturalization tool [12], and a temporal
path planner. In a preliminary study on thirteen users (with
programming experience), we demonstrate that naturalization
helps specify tasks in a more succinct way, that users
define derived concepts as building blocks, and these derived
concepts are reused by later users as their basis for interacting
with the system.

Control flow:
Stmt

→ Act | Stmt; Stmt | repeat Num times Stmt
| foreach point in Area Stmt | if Cnd Stmt | while Cnd Stmt

Actions:
→ visit Area | visit Area while avoiding Area
| move right | move left | . . .
| ItemAct QItm | strict Act
ItemAct → pick | drop
Act

Locations:
→ world | Pnt | [Pnt, Pnt, ..., Pnt] | Area containing Itm
| Area and Area | Area or Area | Area minus Area
Pnt → [Num, Num] | point

Area

Items:
→ every Itm | Itm
→ item | item Fltr
→ has Prop |
| Fltr and Fltr | Fltr or Fltr | not Fltr
Prop → color C | shape S
C
→ red | blue | green | yellow | . . .
S
→ triangle | square | circle | . . .

QItm
Itm
Fltr

Conditions:
Cnd

→ Itm at Area | robot has Item | robot at Area | possible Stmt

Fig. 2: Syntax of core language (subset). Reserved constants
and variable names are marked in italic.

Example 1. Go to a red item and pick it up . . .
visit world containing item has color red;
pick item has color red

. . . but avoid all circular items along the way
II. C ORE L ANGUAGE AND P LANNING
Flipper starts with a core language for specifying temporal
tasks for a robot in the abstract world. Figure 2 shows the
most interesting subset of the syntax of the core language.
While the abstract world in which our robot operates may
seem relatively simple, the core language allows expressing
many interesting scenarios. For example, it allows us to
express the tasks in Figure 3.
Intuitively, the core language interprets a program as a
temporal goal for the robot in a grid world. The model of
the grid world consists of a tuple (M, I, r) where M is a
two-dimensional grid of points divided into free points and
obstacles, I is a set of items, and r is the robot. Each item
i ∈ I has associated attributes such as color, shape, and a
unique identifier. Additionally, if it is not held by the robot,
it has a position which is a point in M . The robot r has a
position in M and holds a possibly empty set of items.
The core language has a set of actions that manipulate
the world and combines actions through standard imperative
constructs such as sequencing, conditionals, or loops. We
focus here on the non-standard parts of the language.

visit world containing item has color red
while avoiding world containing item has shape circle;
pick item has color red



Example 2. Gather all red items
foreach point in world containing item has color red
{ visit point; pick every item has color red }



Example 3. If possible, form a horizontal line on the floor
out of all the items the robot currently has (starting at robot’s
current position and to the right)
strict {while robot has item {drop item; move right}};



Example 4. Place as many items in a horizontal line as fit.
drop item;
while possible {move right; drop item} {move right; drop item}



Fig. 3: Example commands in the core language

The propositions of the logical language specify either
sets of items or sets of points, and can be combined using
Boolean operations as usual. The syntactic class “Locations”
describes sets of points in the grid M . The user can, for
instance, start with the entire grid M using the keyword world
and filter the grid points to those which contain interesting
items using the containing clause (see Example 1). Similarly,
the syntactic class “Items” describes sets of items. All
items can be selected with the every keyword and specific
items can be chosen by filtering based on (possibly Boolean
combinations) of attributes (Example 2).
Actions modify the state of the world. For example, pick
changes the world from a state where there is an item i
in the current position of the robot to a world in which
the item is being carried by the robot. Actions can be
temporal. The temporal action visit T, for a set T ⊆ M of
points, requires that the robot is moved to some position in
T . The temporal action visit T while avoiding A additionally
requires that along the way the robot never visits any point
in A ⊆ M (see Example 1). They can be written in linear
temporal logic (LTL) as ♦T and ¬A U T , respectively.
The language is expressive enough to subsume LTL with
propositions ranging over points and items.
In a complex command, only some part of a command
may be realizable. Consider Example 3: the robot may be
able to move right once but not as many times as it has items.
The default behavior is lenient in that it executes those parts
of the command which are realizable and prints a warning
about those which are not. The strict modifier allows to
specify more rigid behavior that either performs the complete
action or no part of it.
In a slight modification of the scenario above, if we
want to place as many items to the right as possible, as in
Example 4, then we can use the while possible S T construct
which executes T repeated while S is realizable.
Given a goal expressed in the core language, Flipper
generates an execution plan for the robot to satisfy it in
the grid world. Currently, Flipper’s planner is based on A*
search [13] with Christofides algorithm [14] for iterated
reachability. However, the planner interface is generic and
one can use a different planner [1], [3], [6], [15], [16]. Fast
planning is crucial for user interaction and we found A* to
be fast and sufficient to find plans.
The plan generated is shown to the user visually in
Flipper’s graphical interface by simulating the robot’s moves
step by step in the UI. This visual feedback is important to
verify that a possibly complex command given to the robot
works as expected. Furthermore, ambiguities in the grammar
can lead to several alternative plans being generated; the UI
enables the user to select the plan which best matches his or
her intentions.
III. PARSING , NATURALIZATION , AND G ENERALIZATION
We now describe how naturalization works in Flipper. We
start by showing two examples of naturalization and then
explain the inner mechanism of the naturalization process.

foreach point in world containing item has color red
{visit point; pick every item has color red };
visit room1; drop every item has color red;
foreach point in world containing item has color green
{visit point; pick every item has color green};
visit room2; drop every item has color green;
foreach point in world containing item has color blue
{visit point; pick every item has color blue};
visit room3; drop every item has color blue;
foreach point in world containing item has color yellow
{visit point; pick every item has color yellow};
visit room4; drop every item has color yellow

Fig. 4: Sorting items based on colors using the core language

Example 5. Suppose a user writes the command pick 3 items.
Since this is not a valid program in the core language,
Flipper asks for a definition. Suppose the user responds
with repeat 3 times pick item. From this, Flipper’s grammar
induction module now induces the following two grammar
rules:
Act
Act

→ pick Num items
::= repeat Num times pick item
→ ItemAct Num items ::= repeat Num times ItemAct item

Note that these rules are a generalization of the user-provided
definition. Thus, when the next user issues the command
drop 2 items, the semantic parser will be able to parse it and
Flipper will successfully execute it.

Example 6. Naturalization not only helps accommodate
many different language styles, it can also significantly
simplify programs. Consider the task of distributing items
of different colors to different rooms. Conceptually, this is
fairly simple: the robot should first gather all red items and
put them into room1, then do the same for the blue items
and room2 and so on. Figure 4 shows an implementation of
this specification in the core language. Each marked part
corresponds to gathering items of a specific color (as in
Example 2) and bringing them to a specific room. Clearly,
there is a significant amount of redundancy.
With naturalization, we can accomplish the same task by
first defining gather red as
foreach point in world containing item has color red
{visit point; pick every item has color red}

Then using this new command, we define

red to room1

as

gather red; visit room1; drop every item has color red

and finally we can accomplish our complete task with
red to room1; green to room2; blue to room3; yellow to room4

If we next want to put all items of different shapes to different
rooms, the generalization allows us to re-use the commands
defined above and simply write:
triangle to room1; circle to room2; square to room3



Thus, the naturalization process is a convenient way of
giving alternative names to existing concepts and defining
functions by example, akin to extending a programming
language through new functions, but with two differences.
Unlike usual programming languages, which require every
definition to be in the core syntax, we use a semantic parser
to allow for relaxed syntax and natural linguistic styles.
Second, the user always provides concrete values and the
underlying system takes care of parameter inference through
grammar induction. These features make the overall system
more accessible to non-programmers over time. Moreover,
each defined notion is available for use in the future and
to different users. Thus, over time, Flipper develops the
common linguistic style and phraseology of its user base.
We now describe the semantic parser and grammar induction.
A. Semantic Parsing
Semantic parsing is the task of turning a natural language
utterance (x) into a ranked list of formal representations
(such as a logical formula, a formal specification, or a formal
language expression) for actions [17]. For example, if x =
“How much is three times four?”, a possible intermediate
representation is 3∗4 and a resulting action is computing the
product. In Flipper, the role of the semantic parser is to turn
an utterance x into a ranked list of temporal goals represented
in the core language. The corresponding actions are the plans
for these goals. Flipper uses the interactive semantic parser
presented in [12]. The semantic parser outputs a ranked list
because utterance parses may be ambiguous. In Flipper, ambiguous derivations can occur due to ambiguities in the core
language or due to conflicting definitions (e.g., by different
users) for the same utterance. An example for the former
is pick item not has color red and has shape circle which could
mean either pick item not {has color red and has shape circle}
or pick item {not has color red} and {has shape circle}. The
latter occurs when for one user take red means pick up a
red item from the current field, but for the other find a red
item and then pick it up.
To rank the potential parses, the parser uses a model
pθ (d|x, u) which gives the probabilities over derivations d
given the utterance x by the user u, using a set of parameters
θ. Flipper then offers three best-ranked derived programs to
the user who visually inspects their execution in simulation.
Based on the user’s choice, the model’s parameters θ are
updated. The set of features influencing the model include
whether the rule comes from the core language or it is
induced, whether the author of the rule is the same person
as u, the user providing the utterance, etc.
B. Grammar Induction
When the semantic parser is unable to parse an utterance, it
asks the user to provide a definition. The grammar induction
module generalizes the definition for a particular utterance
into a new grammar rule. The grammar induction module
receives an utterance x, and its definition y. For instance, in
Example 5, x = pick 3 items and y = repeat 3 times pick item.

While y must be fully parseable using the current grammar
rules, only some parts of x may be parseable. In order to
induce new rules, we are interested in finding matches—
parseable spans appearing in both x and y. A set of nonoverlapping parsable spans is called a packing.
New grammar rules are generated in one of the following
three ways:
simple packing: only primitive values are matched (in Flipper those are directions, numbers, colors, shapes and
points). Once matched, a new rule is introduced in the
form of Cy → x[a1 /A1 , . . . , ak /Ak ], where Cy is the
category of y and x[a1 /A1 , . . . , ak /Ak ] is the utterance
with all occurrences of primitive value ai replaced
by its category Ai . For Example 5 the only primitive
match would be number 3. Therefore, a new rule will
be added to the grammar Act -> pick Num items with the
same action specification as repeat Num times pick item
best packing: considers maximal packings, i.e. those that
would become overlapping by adding any other derivation. This method chooses the packing that scores the
best under the model pθ . Subsequently, a rule induction (similar to the one described for simple packing) based on the matching between y and the found
best maximal packing is performed. As an example,
take x = pick item has color green and shape circle and
y = pick item has color green and has shape circle. Two
maximal packings of x are α and β
Bα
Cα
Aα
}|
{
z }| { z }| {
z
pick item has color green and shape |circle
|{z} |
{z
}
| {z } {z }
Aβ

Bβ

Cβ

Dβ

and their matching parts in y
Aα

Bα

Cα

z }| { z }| {
z
}|
{
pick item has color green and has shape |circle
|{z} |
{z
}
| {z } {z }
Aβ

Bβ

Cβ

Dβ

The best of all maximal packings (there are more
than just α and β) is β, so a new rule is produced
Act

→ ItemAct item Fltr and Prop

alignment: Utterance x and derivation y are compared and
if they align almost perfectly, a new rule is produced.
As an example, for x = throw item and y = drop item, a
new rule is added ItemAct → throw ::= drop.
In order to avoid unintended generalizations, the implementation of grammar induction introduces many restrictions
for the above three methods, such as stopping the search
after finding the first alignment match, and limiting the
differences in size between matches. We dropped some
of those restrictions in order to induce more rules, and
observed no significant penalty on overall user experience.
Unintended generalization happens nonetheless, but their
effect is dampened when users choose between multiple
offered behaviors, which dynamically updates the parameters
of the model in the semantic parser. This effectively removes
unintended generalizations from the system over time.
We add one additional new improvement to the process
of grammar induction. Sometimes users, especially those not

very adept at programming in the core language, will define
their utterances specific to the state of the world rather than
in the most general form. In Example 5, such a specific definition might be pick 3 items = pick item; pick item; pick item.
This definition, however, will not generalize to pick 2 items
using any of the described methods. A solution would
be to explore the space of semantically equivalent definitions and feed them as an additional input into the
previous three methods to obtain more meaningful new
rules. Currently, the exploration is limited only to rulebased search for hidden loops. In our example, the definition equivalent to pick item; pick item; pick item would be
repeat 3 times pick item, which would generalize correctly.
The mentioned changes turned out to be useful in practice.
IV. E VALUATION
Flipper is available at flipper.mpi-sws.org. It consists
of a backend responsible for semantic parsing, a frontend
that visually demonstrates to the user the effect of each
interpretation of an utterance (both based on [12]), and a
planning module. As our core language is a mixture of
concepts typical for imperative programming (e.g. move left)
and an avoid-until- reach temporal specification, we use an
adapted version of the A∗ [18] algorithm as our planner.
A. Goal of Evaluation
Our final goal is to create a system which people with
different levels of proficiency in the core language would
use. Envisioned users range from expert users, i.e., those
that define new commands to make the communication with
the robot simpler, all the way to those who do not know the
language at all. The latter take advantage of commands that
sound as if they should work, and which were defined by
other users of the system.
In the evaluation we were thus interested in two properties:
1) whether or not users are inclined to define new commands and whether those commands make their work
easier, and
2) how much they are able to benefit from other people’s
definitions (without knowing them in advance).
The first property corresponds to the ability to define
functions in a programming language, except that Flipper
generalizes definitions from examples. The second property
describes how much closer the system gets to pure naturallanguage interface if there is a number of active expert users.
We thus want to test our intuition that different people use
similar linguistic expressions for similar commands and that
is why they do not have to be aware of existing definitions.
B. Setup
We created a list of 21 tasks. The tasks levels ranged from
easy (e.g. “get one green square”) to difficult (e.g. ”bring all
red items to a room that contains a yellow square”). The list
of all tasks, as well as all our experimental data is available at
Flipper’s website. We recruited thirteen participants, all with
prior programming experience but without any knowledge of
the system, and split them into three groups:

Group A (4 members) was only allowed to use the core
language,
• Group B (6 members) could additionally define their
own concepts,
• Group C (3 members) additionally had access to concepts defined by two expert users (familiar with the
system and the language) as well as by other participants
from group C in real time.
At the start of the experiment, each group had 30 minutes to
familiarize themselves with the core language by following
a tutorial. Then participants were instructed to solve the
21 tasks as they saw fit, i.e., not necessarily in the most
general way. The average time needed to solve all tasks
was 90 minutes (no deadline was set). For each participant,
we measured the number of accepted commands, i.e., the
syntactically correct ones coming either from the core or the
induced language, and the total number of words, defined
concepts, and induced commands used to finish all tasks.
For induced commands we additionally distinguish whether
they were defined by the same or by another participant.
Learning any new programming language in half an hour
is a nontrivial task. In our experiment, the average number
of successfully parsed queries in group A (only using the
core language) was 75%, with some differences between the
participants (63%, 70%, 77% and 90%).
•

C. Results
Usefulness of Naturalization: To assess the usefulness
of naturalization, we compare the total number of tokens
needed to finish the tasks for the different groups (Figure 5),
and how often participants in groups B and C used defined
concepts (Figure 6). The latter shows that participants who
were allowed to define their own concepts also used that
opportunity. When comparing the participants from groups
B and C to those of group A, it is clear that the participants
who were able to use naturalization end up with less work
in terms of total number of tokens needed to finish the
tasks. Specifically, the average number of tokens needed
for groups B and C is 1156, while for group A it is
1765. This takes into account all tokens, also the ones from
unsuccessful commands. We include these, as some number
of unsuccessful commands by groups that use naturalization
comes from trying out commands they believed might be
defined by others. Only considering successful commands,
groups B and C use in total 738 tokens compared to 1287
in group A, i.e., an improvement of 43% with respect to the
usage of the core language only. These results suggest that
naturalization reduces users’ effort. It is important to note
that individual performances of participants within a single
group vary, as shown in Figure 5.
Naturalization across Users: Participants in group C
had access to the concepts defined by others. Interestingly,
these participants adopted different strategies. While they
were on average more likely to use induced language than the
core language (43 vs. 35 commands), only one participant
relied primarily on the induced language. The other two users
used slightly more core than induced language (see Figure 6).

3,000

2,500

# tokens

2,000

1,500

1,000

500

A1

A2

A3

A4

B1

B2

B3

B4

successful commands

B5

B6

C1

C2

C3

all commands

Fig. 5: Total number of tokens used per participant

150

# commands

The main point of the experiment for group C was to
see whether the existence of previously defined concepts is
helpful. We first notice that participants were indeed using
concepts defined by others (Figure 7). Again, the numbers
differ among participants. By looking closer at the kinds
of commands issued by each participant, we see that these
differences stem from their individual styles: participant C2
chose to try small building blocks that matched the style
of the two expert users whose definitions were available to
group C. Participant C3, on the other hand, used commands
similar to the core language. Curiously, after the experiment
two participants (C1 and C3) claimed that they have not
much used the predefined rules and that they ended up using
almost exclusively self-defined concepts (in addition to the
the core language). The data, however, told a different story
(Figure 7): C1 roughly equally used rules defined by others
and by himself, while C3 used much more induced rules.
Upon inspection of the logs, it turned out that on many
occasions they believed they were using the core language,
while in fact they used induced concepts defined by others
(e.g. move 2 right or drop all blue items).
Types of Defined Concepts: Upon closer inspection of the concepts the participants defined, we see
that a majority falls into two categories: (1) simplifying individual commands and (2) defining functions. Examples for the first case are pick green square defined
as pick item has color green and visit empty space defined as
visit world minus {world containing item}.
For the second case a simple example is
visit both triangle and green defined as

100

50

visit { {world containing item has shape triangle} and
{world containing item has color green} }

There were also function definitions that involved previous function definitions, such as line red being defined
as fetch all red; while {robot has item} {drop item; move left}.
Another noticeable phenomenon was that group C had to
define some concepts already defined by others. The reason
was small variations in the utterances (e.g. pick red vs.
take a red vs. take a red item) which can be caught by a more
comprehensive natural language processing module.
V. R ELATED WORK
There are many systems commanding or communicating
naturally with robots as well as creating programming languages for robots usable by non-programmers, starting with
the seminal work in SHRDLU [19], and continuing over
the years [9], [10], [20]. For example, Thomason et al. [9]
demonstrate a system in which utterances are mapped to λcalculus computations and the robot fills in the gaps in a
simple action-patient-recipient pattern, supporting navigation
and delivery.
Formal and logical languages for planning have a long
research tradition in AI and formal methods. Recently,
the work by Kress-Gazit et al. [7], [8], [15] focuses on
translating natural language into linear temporal logic to
bridge the gap from users to formal methods tools. One

0
B1 B2 B3 B4 B5 B6 C1 C2 C3
induced

core

Fig. 6: Core-language commands vs induced commands for
groups B and C

project uses a pipeline of general-purpose NLP methods [8],
with VerbNet [21] at the core of semantic interpretation.
A robot is additionally able to give an answer to what it
is currently doing, based on the natural language to LTL
translation tree, as well as to explain why an action is
unrealizable. A limitation is, however, that the set of actions a
robot can perform is still restricted to implemented semantic
behaviours. On the other hand, [7] can process any (GR(1))
LTL specification, but the burden is on the human to use
only structured English. Flipper accomplishes both, with the
tradeoff that at least some of the users are able to learn the
core language.
Tellex et al. [22] solve the problem of grounding utterances
from the command to objects in space by introducing a hierarchical structure that connects expressions such as beside

robotics domain.

65

VI. C ONCLUSION

# commands

60

40

20

17

22

20

6
0

0
C1

C2
rules by others

C3
rules by self

Fig. 7: Using rules induced by others vs. self-induced rules

the truck and beside the box. Paul et al. [23] solve the same
problem, but support abstract expressions such as first cube
in the second row. This line of work is connected to the one
described in the previous paragraph in the work by Boteanu
et al. [24]—there the grounding problem is put in the context
of reactive temporal commands. In this line of work, unlike
in Flipper, the robot cannot be taught new concepts. On the
other hand, Flipper does not support talking about abstract
spatial relations between items in its world. To support this,
Flipper’s core language would need to be modified (and one
could then use the mentioned techniques).
Flipper is inspired by and based upon the work on naturalization of formal languages by Wang et al. [12], which
considers a block world where a user can build various
shapes of different colors. The application of naturalization to
a robot world introduces new challenges: the language contains declarative and unrealizable commands and dynamic
behavior that changes the state of the world. A similar
approach of learning the language from users is presented
in [25], but in the context of personal assistants. Iyer et
al. [26] use user’s feedback to minimize the effort needed
for additional annotation of data and iteratively improve their
semantic parser that translates natural language utterances
to SQL queries. Beltagy and Quirk [27] train a model
(an ensemble of a neural network and logistic regression)
that translates a task description from an IFTTT dataset
into executable representations. They show several ways to
improve the performance, the most interesting of which is
creating synthetic data by paraphrasing task descriptions.
Work by Lin et al. [28] has a similar motivation: starting with
questions from popular programming-help websites that describe programmers’ intentions, they devise bash one-liners
accomplishing it. This kind of work enables semantic parsing
from less direct instructions, but is not easily adaptable
to users interactively giving clues to the system about the
meaning of the utterance. None of these papers targeted the

We have shown that naturalizing a domain-specific programming language is well suited to provide a natural language interface to robot task specifications. Flipper provides
the precision, expressivity, and extensibility of a programming language, while ensuring a natural experience for
humans. Flipper adapts its language to its users by learning
new concepts from them. The results of our initial evaluation
are encouraging and suggest that a formal language for
instructing robots can be turned with community effort into
a domain specific natural language.
To accomplish our goal to its full extent, a few challenges
remain to be solved. The first one is lowering the entry
bar to the system in its early phase, i.e. learning the core
language. This could be accomplished by adding syntactic
sugar or a specialized interface, while keeping the rich
formalism as a latent representation of the space of robot
tasks. Finally, the user experience of Flipper can be improved
to offer explanations for unparseable utterances, better depict
alternate interpretations of an utterance which have the
same execution, or auto-complete for available pre-defined
concepts.
R EFERENCES
[1] H. Levesque, R. Reiter, Y. Lespérance, F. Lin, and R. Scherl,
“GOLOG: A logic programming language for dynamic domains,” J.
Log. Program., vol. 31, no. 1-3, 1997.
[2] R. Fikes and N. J. Nilsson, “STRIPS: A new approach to the
application of theorem proving to problem solving,” Artif. Intell.,
vol. 2, no. 3/4, 1971.
[3] M. Ghallab, C. Aeronautiques, C. K. Isi, and D. Wilkins, “PDDL: The
planning domain definition language,” Tech. Rep. CVC TR98003/DCS
TR1165, Yale Center for Computational Vision and Control, 1998.
[4] G. E. Fainekos, A. Girard, H. Kress-Gazit, and G. J. Pappas, “Temporal
Logic Motion Planning for Dynamic Robots,” Automatica, vol. 45,
no. 2, pp. 343–352, 2009.
[5] J. Hoffmann and B. Nebel, “The FF Planning System: Fast Plan
Generation Through Heuristic Search,” CoRR, vol. abs/1106.0675,
2011.
[6] A. Desai, I. Saha, J. Yang, S. Qadeer, and S. A. Seshia, “DRONA: a
Framework for Safe Distributed Mobile Robotics,” in ICCPS, 2017.
[7] H. Kress-Gazit, G. E. Fainekos, and G. J. Pappas, “Translating
Structured English to Robot Controllers,” Advanced Robotics, vol. 22,
no. 12, pp. 1343–1359, 2008.
[8] C. Lignos, V. Raman, C. Finucane, M. P. Marcus, and H. Kress-Gazit,
“Provably Correct Reactive Control from Natural Language,” Auton.
Robots, vol. 38, no. 1, pp. 89–105, 2015.
[9] J. Thomason, S. Zhang, R. J. Mooney, and P. Stone, “Learning to Interpret Natural Language Commands through Human-Robot Dialog,”
in IJCAI, 2015.
[10] T. Kollar, V. Perera, D. Nardi, and M. M. Veloso, “Learning Environmental Knowledge from Task-Based Human-Robot Dialog,” in ICRA,
2013.
[11] J. Berant, A. Chou, R. Frostig, and P. Liang, “Semantic Parsing on
Freebase from Question-Answer Pairs,” in EMNLP, 2013.
[12] S. I. Wang, S. Ginn, P. Liang, and C. D. Manning, “Naturalizing a
Programming Language via Interactive Learning,” in ACL, 2017.
[13] P. E. Hart, N. J. Nilsson, and B. Raphael, “A Formal Basis for
the Heuristic Determination of Minimum Cost Paths,” IEEE Trans.
Systems Science and Cybernetics, vol. 4, no. 2, pp. 100–107, 1968.
[14] N. Christofides, “Worst-Case Analysis of a New Heuristic for the
Travelling Salesman Problem,” Technical Report 388, Graduate School
of Industrial Administration, Carnegie Mellon University, 1976.
[15] C. Finucane, G. Jing, and H. Kress-Gazit, “LTLMoP: Experimenting
with Language, Temporal Logic and Robot Control,” in IROS, 2010.

[16] I. Gavran, R. Majumdar, and I. Saha, “Antlab: A Multi-Robot Task
Server,” ACM Trans. Embed. Comput. Syst., vol. 16, no. 5s, pp. 190:1–
190:19, 2017.
[17] P. Liang, “Learning Executable Semantic Parsers for Natural Language
Understanding,” Commun. ACM, vol. 59, no. 9, pp. 68–76, 2016.
[18] P. Rodriguez-Mier, A. Gonzalez-Sieira, M. Mucientes, , M. Lama,
and A. Bugarin, “Hipster: An Open Source Java Library for Heuristic
Search,” in CISTI, 2014.
[19] T. Winograd, Understanding Natural Language. Academic Press, Inc.,
1972.
[20] S. Alexandrova, Z. Tatlock, and M. Cakmak, “RoboFlow: A FlowBased Visual Programming Language for Mobile Manipulation Tasks,”
in ICRA, 2015.
[21] K. K. Schuler, Verbnet: A Broad-coverage, Comprehensive Verb Lexicon. PhD thesis, University of Pennsylvania, Philadelphia, PA, USA,
2005. AAI3179808.
[22] S. Tellex, T. Kollar, S. Dickerson, M. R. Walter, A. G. Banerjee, S. J.
Teller, and N. Roy, “Understanding Natural Language Commands for

Robotic Navigation and Mobile Manipulation,” in AAAI, 2011.
[23] R. Paul, J. Arkin, N. Roy, and T. M. Howard, “Efficient Grounding
of Abstract Spatial Concepts for Natural Language Interaction with
Robot Manipulators,” in Robotics: Science and Systems XII, 2016.
[24] A. Boteanu, T. M. Howard, J. Arkin, and H. Kress-Gazit, “A Model
for Verifiable Grounding and Execution of Complex Natural Language
Instructions,” in IROS, 2016.
[25] A. Azaria, J. Krishnamurthy, and T. M. Mitchell, “Instructable Intelligent Personal Agent,” in AAAI, 2016.
[26] S. Iyer, I. Konstas, A. Cheung, J. Krishnamurthy, and L. Zettlemoyer,
“Learning a Neural Semantic Parser from User Feedback,” in ACL,
2017.
[27] I. Beltagy and C. Quirk, “Improved Semantic Parsers For If-Then
Statements,” in ACL, 2016.
[28] X. V. Lin, C. Wang, D. Pang, K. Vu, L. Zettlemoyer, and M. D. Ernst,
“Program Synthesis from Natural Language using Recurrent Neural
Networks,” tech. rep., University of Washington, 2017.

