Robotics: Science and Systems 2013 Berlin, …

1 Robotics: ScienceandSystems2013 Berlin, Germany,June24-28,20131 sorry Dave, I m Afraid I Can t Do that : ExplainingUnachievable robot tasks using Natural LanguageVasumathi Raman , Constantine Lignos , Cameron Finucane , Kenton Lee , Mitch Marcus and Hadas Kress-Gazit Department of Computer Science , Cornell University, Ithaca, NY 14850 Email: Department of Computer and Information Science , University of Pennsylvania, Philadelphia, PA 19104 Email: Sibley School of Mechanical and Aerospace Engineering, Cornell University, Ithaca, NY 14850 Email: This paper addresses the challenge of enabling non-expert users to command robots to perform complex high-leveltasks using natural language. It describes an integrated systemthat combines the power of formal methods with the acces-sibility of natural language, providing correct-by-constructioncontrollers for high-level specifications that can be implemented,and easy-to-understand feedback to the user on those that cannotbe achieved.

2 This is among the first works to close this feedbackloop, enabling users to interact with the robot in order to identifya succinct cause of failure and obtain the desired controller. Thesupported language and logical capabilities are illustrated usingexamples involving a robot assistant in a INTRODUCTIONAs robots become more ubiquitous, multi-capable andgeneral-purpose, it is desirable for them to be easily con-trollable by non-expert users. The near future will likelysee robots in homes and offices, performing everyday taskssuch as fetching coffee and tidying rooms. The challenge ofprogramming robots to perform these tasks has until recentlybeen the domain of experts, requiring hard-coded high-levelimplementations and ad-hoc use of low-level techniques suchas path-planning during execution. Recent advances in the ap-plication of formal methods to robot control have enabled au-tomated synthesis of correct-by-construction hybrid controllersfor complex high-level tasks ( , [15, 13, 1, 4, 17, 26]).

3 However, most current approaches require the user to pro-vide task specifications in logic, or a similarly structuredspecification language [16]; users must formally reason aboutsystem requirements rather than providing an intuitive descrip-tion of the desired outcome. This motivates a robot controlplatform that allows users to specify behaviors via naturallanguage (text or speech) and provides either the desired robotcontroller or an explanation for why one cannot paper presents an integrated platform that enables robotcontrol from natural language specifications for situated high-level tasks . Natural language commands to the robot are parsedusing semantic analysis into a formal specification which isused to synthesize a hybrid controller. If no implementationexists, the user is provided with an explanation and theportions of the specification that cause failure.

4 The proposedsystem thus combines the power of formal methods withthe accessibility of natural language, providing correct-by-construction controllers for specifications that can be imple-mented and easy-to-understand feedback for those that are several previous approaches that use naturallanguage for controlling robots. Some frameworks translateinstructions in unconstrained natural language into formal goaldescriptions and action scripts for tasks like navigation andmanipulation [9, 18, 25]. Others map high-level instructions tomore fine-grained sequences of commands, filling in missinginformation [5]. This paper builds on components presented in[6], adding natural language capabilities to deal with a widerclass of specifications, and providing fine-grained feedback onspecifications that cannot be the controller synthesis front, recent work has tackled theproblem of analyzing high-level specifications that are unsyn-thesizable.

5 Feedback about the cause of unsynthesizability canbe provided to the user in the form of a modified specification[10, 14], a highlighted fragment of the original specification[20], or by allowing the user to interact with an adversarial en-vironment that prevents the robot from achieving the specifiedbehavior [21, 22]. Building upon these approaches, this workprovides minimal explanations of unsatisfiable specifications,as described in Section V, and provides fine-grained naturallanguage feedback that is not necessarily just a subset of theoriginal natural language specification. It also enhances theinteractive visualization tool with feedback on why particularrobot actions may be disallowed in a given state, as describedin Section SYSTEMOVERVIEWFig. 1 shows the system s main components and the con-nections between them. The Situated Language UnderstandingRobot Platform (SLURP) consists of parsing, semantic inter-pretation, LTL generation, and feedback components; theseare described in detail in Section III.

6 This module is thenatural language connection between the user and the logicalrepresentations used within the Linear Temporal Logic Mis-siOn Planning (LTLMoP) toolkit [11]. LTLMoP, which alsointerfaces with the SAT solver PicoSAT [2], provides an envi-ronment for creating, analyzing, and executing GameParsingFeedbackUserAnalysisRobotunsa tisfiableunrealizableunsynthesizablesynt hesizableSemanticInterpretationLTL GenerationFig. 1: System OverviewSubcomponents of LTLMoP are detailed in Section TRANSFORMINGNATURALLANGUAGE INTOLOGICWITHSLURPThe Situated Language Understanding robot Platform(SLURP) enables the conversion of natural language spec-ifications into Linear Temporal Logic formulas. The user sinstructions are processed through a pipeline of natural lan-guage components which identify the syntactic structure of thesentences, extract semantic information from them, and createlogical formulas to be used in controller synthesis.

7 Whilemany previous natural language Systems for robot control haverelied on per-scenario grammars that allow the unificationof semantic information and natural language representations[8], this work uses a combination of robust, general-purposecomponents. An advantage of this approach compared to per-scenario grammars is that the core language models need notbe modified across scenarios; to adapt to new scenarios all thatis required is that the LTL generation be extended to supportadditional types of Identifying Linguistic StructureBefore a sentence may be converted into logical formulas,the linguistic structure of the sentence must be ) Parsing:Parsing is the process of assigning a hierar-chical structure to a sentence. While simple natural languageunderstanding can be performed with shallower processingtechniques, parsing allows for recovery of the hierarchicalstructure of the sentence, allowing for proper handling of natu-ral language phenomena such as negation ( ,Never go to thelounge) and coordination ( ,Go to the lounge and kitchen)which are crucial to understanding commands.

8 SLURP usesthe pipeline of natural language processing components usedby Brooks et al. [6]: the Bikel parser [3] combined with thenull element (understood subject) restoration of Gabbard et al.[12] to parse sentences. Before being given to the parser, theinput is tagged using MXPOST [23]. The models used bythese Systems require no in-domain training. The output ofthese modules is given in Figure ) Semantic interpretation:The semantic interpretationmodule uses the parse tree to extract verbs and their example, in the sentenceCarry meals from the kitchen *(A) Tagging, parsing, and null element restorationAgent:* (understood subject)Verb:goPreposition:toLocation:th e hallway(B) VerbNet frame matchingInitially, the hallway has not been visited: a persistent memory of going to the hallway: ( ( ))Always eventually have a memory of visiting the hallway: ( )(C) LTL formula generationFig.

9 2: Conversion of the sentence Go to the hallway. intoLTL formulas through parsing, semantic interpretation, andLTL patient rooms, the desired structure is acarrycommandwith an object ofmeals, a source ofkitchen, and a destinationofall patient extract verbs and their arguments from parse trees,SLURP uses VerbNet [24], a large database of verbs andthe types of arguments they can take. The VerbNet databaseidentifies verbs as members of senses: groups of verbs whichin similar contexts have similar meanings. For example, theverbscarry,lug, andhaulbelong to the general senseCARRY,because in some contexts they are roughly equivalent inmeaning. For each sense, VerbNet provides a set of frames,which indicates the possible arguments to the sense. Considerthe following sentence:Carry meals to all patient verbcarryis mapped to the senseCARRY.

10 An exampleof a frame for this sense is [AGENT, VERB, THEME, TOTOWARDS, DESTINATION]. Each role in the frame, subjectto its associated syntactic constraints, is mapped to a partof the parse tree. In this case, SLURP creates the followingmapping: [AGENT *, VERB carry, .., DESTINATION all patient rooms]. Among the frames that completely matchthe parse tree, SLURP chooses the frame that expresses themost semantic roles. The chosen match is then used to fill inthe appropriate fields in the Generation of LTL FormulasThe information provided by VerbNet allows the identifica-tion of verbs and their arguments; these verbs must then beused to generate logical formulas defining robot ) Linear Temporal Logic (LTL):The underlying logicalformalism used in this work is Linear Temporal Logic (LTL),a modal logic that includes temporal operators, allowingformulas to specify the truth values of atomic propositions overtime.