Integrating Answer Set Programming with Semantic Dictionaries for Robot Task Planning

1 Introduction

Service robots are becoming more and more powerful and robust to perform low-level actions [Du Toit and Burdick, 2012; Hofmann et al., 2015; Misra et al., 2016]. However, when robot interacting with end users, task instructions are often expressed in natural language with abstract concepts, such as "I have a headache", "I am thirsty", and "make breakfast". To response, robots need to know how to map user instructions in an open-ended form into low-level (executable) actions. This is a key challenge for robot task planning that has recently attracted many attentions in both the AI and robotics communities [Buehler and Pagnucco, 2014; Cashmore et al., 2015; Chen et al., 2012; Gaschler et al., 2013; Hanheide et al., 2015; Keller et al., 2010; Misra et al., 2016; Nyga and Beetz, 2012; Stock et al., 2015].

A typical approach for task planning is hierarchical task decomposition. More precisely, user instructions or high-level tasks are decomposed into a sequence of low-level subtasks based on pre-defined knowledge, obtained from either domain experts [Misra et al., 2016; Tellex et al., 2011] or open resources [Chen et al., 2013; 2012; Nyga and Beetz, 2012]

∗Corresponding Author.

such as Open Mind Indoor Common Sense (OMICS) [Gupta et al., 2004]. For instance, a high-level user task "serve a drink from fridge" can be decomposed into a sequence of subtasks as "go to fridge", "open the fridge door", and "take the drink", based on the knowledge in OMICS.

Unfortunately, there are two main issues with this approach. Firstly, existing knowledge resources (e.g., OMICS) are far from complete so that one cannot find corresponding decomposition rules for a large number of high-level tasks. Secondly, even such a rule exits, it could be the case that the decomposed subtasks are still relatively high-level so that they cannot be directly executed by robots.

Alternatively, researchers turned to automated planning to generate plans with manually created knowledge in the preconditions and/or postconditions. To date, there are many approaches along this track for robot task planning [Buehler and Pagnucco, 2014; Cashmore et al., 2015; Gaschler et al., 2013; Ghallab et al., 2014; Hanheide et al., 2015]. However, most of them depend on hand-coded action effects. For example, in order to automatically generate a plan, robots need to know the beer is on dinner table after executing the task "take a beer from refrigerator to dinner table".

In this paper, we propose a novel approach that integrates Answer Set Programming (ASP) [Gelfond and Lifschitz, 1988] with semantic dictionaries [Baker et al., 1998; Fellbaum, 1998] for robot task planning. We aim to addressing two critical challenges: (a) how to obtain large-scale and general-purpose action descriptions particularly about the effects of actions, and (b) how to formalize action descriptions in order to be used in automated planning. Specifically, to address (a), we exploit definitions of common verbs in semantic dictionaries such as FrameNet [Baker et al., 1998] and WordNet [Fellbaum, 1998], which are handcrafted by linguists. More importantly, such dictionaries are beneficial to both language processing and formalizing more sophisticated than simple hand-coded effects. For (b), we represent action definitions in semantic dictionaries as logic rules and call ASP solvers to generate plans. By doing so, we can do robot task planning and handle large-scale user instructions using knowledge both from action decomposition in knowledge bases (e.g., OMICS) and common-verb descriptions in sematic dictionaries (e.g., FrameNet) in a single framework. This significantly reduces workload of hand-coding and increases the degree of autonomy of service robots.

Empirically, we compare our approach with the state-ofthe-art solution and our experimental results confirm the advantage of our method. Notably, the proposed technique has been used in our service robot and show encouraging performance in the RoboCup@Home competitions.

Our main contributions are summarized as follow:

• We introduce a meta-language (Section 3.1) to formalize semantic roles of common verbs described in semantic dictionaries (e.g., FrameNet), the knowledge of which is missing in existing open resources and not fully described by existing action description languages.
• We propose a method to automatically convert action descriptions in the meta-language to rules in ASP (Section 3.2), which then can be used by standard ASP solvers to generate plans (Section 3.3).

2 SystemOverview

Figure 1 depicts the overall architecture of our integrated system. To start, the Speech Recognition system transcribes speech signal/voice into utterances and the Human-Robot Dialog system manages the dialog with users. A sentence in the dialog is then transferred to the Task Planning module, which generates plans for the task expressed in natural language. Then, a sequence of commands corresponding to low-level executable actions of the robot is computed by the Motion Planning module. Finally, the commands are executed by the Robot Control module.

Here, we focus on the Task Planning module that takes a sentence as its input and outputs plans. As shown in Figure 1, the main components of our Task Planning module include an external Open Knowledge Resource, a Semantic Parser, an Open-Knowledge (OK) Search for (e.g., task decomposition) [Chen et al., 2012] and our Task Planner using semantic dictionaries (e.g., FrameNet, WordNet).

2.1 Knowledge Resources

Our knowledge base integrates two major resources: task decomposition rules from OMICS described in [Chen et al., 2012] for Open-Knowledge (OK) planner and semantic roles of common verbs from FrameNet [Baker et al., 1998] for our ASP planner. FrameNet is introduced as follows.

FrameNet is a digital semantic dictionary providing rich semantic information for action verbs. It groups action verbs into "Frames" and specifies word definitions in terms of semantic roles called Frame Elements (FEs) for each frame. It is known that the connections between an action verb and its semantic roles are very useful for resolving under-specification of naturalistic instructions. However, this knowledge cannot be directly used by robots since it is not formalized in FrameNet. To address this, we developed a formalized version of FrameNet, by translating FrameNet knowledge into a formal meta-language, which can be automatically translated into ASP rules.

2.2 Semantic Parser

A semantic parser translates a user instruction in natural language to a task expressed in our meta-language (see Section 3). We use the frame-semantic parser SEMAFOR proposed by [Das et al., 2012] and the basic idea is as follows. Firstly, a delivered natural language sentence is sent to the framesemantic parser, which was trained using two log-linear models, and the frame-semantic representation of the sentence is returned by the parser. Then the representation is converted into a task expressed in our meta-language.

Suppose that a user task is decomposed into a sequence of steps with one of the steps as "take a beer from the refrigerator to the dinner table". The frame-semantic representation of this step, as shown in Figure 2, is computed by SEMAFOR. Then the representation is translated into the task definition:

(meta-task take-Bringing Theme Source Goal

( : parameters beer refrigerator dinner-table) )

where verb "take" maps to frame "Bringing" in FrameNet and objects "beer", "refrigerator", and "dinner-table" fill into roles THEME, SOURCE, and GOAL respectively.

2.3 Task Planner

The Task Planner module generates plans for user instructions. In this paper, we introduce two types of planners. The first is OK planner [Chen et al., 2013; 2012] which generates plans for high-level tasks by decomposition rules in OMICS. Nevertheless, due to lack of knowledge, i.e., decomposition rules and action effects, the performance of the OK planner is severely restricted.

Fortunately, FrameNet (and other semantic dictionaries) provides rich knowledge about common verbs. We have discovered that the FrameNet definition of an action verb can be reorganized by a set of precondition, postcondition, and invariant over semantic roles of the action (called the functional definition of action). But generally no decomposition knowledge of actions can be obtained from FrameNet. Therefore, we need a classical planner that can utilize formalized functional definition of an action to plan the action.

To this end, we significantly improve the OK planner and propose a new robot task planner called the ASP planner. Our new planner makes use of semantic roles of common verbs in semantic dictionaries (e.g., FrameNet) and automatically generates plans.

3 ASP + FrameNet for Task Planning

In this section, we present a new method for robot task planning by integrating ASP with rules obtained from FrameNet. In order to use FrameNet in ASP, we first need to present a meta-language that formalizes semantic roles of common verbs defined in FrameNet and their corresponding user tasks. Then, we convert such action descriptions in the metalanguage into rules in ASP. Based on which, we call an ASP solver to generate plans for a working example. The main reason that we use ASP is because ASP can serve not only as an inference engine for automated plan generation but also a rich representation language to encode action descriptions in FrameNet.

3.1 Meta-Language

We first propose a meta language LM to formalize semantic roles of common verbs described in FrameNet. In LM, formulas are defined recursively upon atomic formulas (i.e, a predicate with its associated arguments) and propositional connectives such as and, or and not.

Then, we define meta tasks in the following BNF:

<meta-task-def> ::= <func-def> | <proc-def> <func-def> ::= ( define ( meta-task <string> ( :parameters <variable list> ) (:task-variables <task variable list>)) [<precond-def>]∗ [<postcond-def>]∗ [<invariant-def>]∗ <proc-def> ::= [<step-def>]∗ <precond-def> ::= ( :precondition <formula> ) <postcond-def> ::= ( :postcondition <formula> ) <invariant-def> ::= ( :invariant <formula> ) | ( and <invariant-def>+ ) | ( or <invariant-def>+ ) | ( not <invariant-def> ) <step-def> ::= ( :step <task variable>+ ) <variable list> ::= <variable>∗ <task variable list> ::= <task variable>∗ <variable> ::= ?<string> <task variable> ::= ?<string>

Intuitively, a meta task specifies the knowledge extracted from FrameNet for a common verb with a certain frame.

Here, we consider two types of meta tasks. A procedural meta task (i.e., <proc-def>) is specified by a sequence of steps, in which each step is a subtask. This is a hierarchical task decomposition rule stating that the high-level task can be accomplished by the sequence of steps (i.e., subtasks). In FrameNet, some FEs provide procedural definitions of a frame. A functional meta task (i.e., <func-def>) is specified by a tuple of preconditions ??i.e., <precond-def>), postconditions (i.e., <postcond-def>) and/or invariants (i.e., <invariant-def>). For executing a functional meta task, precondition/postcondition is a formula that has to be true before/after the execution, while invariant is a formulas that remains to be true during the whole execution.

Then, given the definition of semantic roles of a common verb, we can formalize its corresponding action description in our meta language LM. For better understanding, we illustrate LM with the following example.

Example 1 Consider the description of verb take with frame Bringing in FrameNet, in which the set of linguistic meta variables is {Robot, Theme, Source, Goal, Carrier}.

1. Theme is portable;
2. Source is the initial location of Theme when take starts;
3. Goal is the final location of Theme when take ends;
4. Source and Goal should not be the same location;
5. Theme and Robot share the same location during the execution of take;
6. Theme is on Robot or in Carrier operated by Robot.

We formalize this as a meta task take-Bringing in our meta language LM as follow:

( define ( meta-task take-Bringing ( :parameters ?robot ?theme ?source ?goal ?carrier ) ( :task-variables ) ) ( :precondition ( and ( location ?source ) ( location ?goal ) ) ) ( :precondition ( portable ?theme ) ) ( :precondition ( at ?theme ?source ) ) ( :postcondition ( at ?theme ?goal ) ) ( :precondition ( not ( equal ?source ?goal ) ) ) ( :invariant ( same-location ?theme ?robot ) ) ( or ( :invariant ( on ?theme ?robot ) ) ( :invariant ( and ( in ?theme ?carrier ) ( operated ?robot ?carrier ) ) ) ) )

In order to convert semantic roles of common verbs in FrameNet into our meta-language, we first adopted existing tools, including PREPOST [Sil et al., 2010] and some open information extraction tools [Angeli et al., 2015], to help us automatically extracting information related to frames and FEs. For example, by using the tool from [Angeli et al., 2015], "Source is the initial location of Theme when take starts" is translated to (Source, initial location, Theme), which is then converted to :precondition ( at ?theme ?source ). Occasionally, we may need to validate and revise these action formalizations. This requests much less human involvement than hand-coding all rules by experts and save us a lot of time to formalize action descriptions into our meta-language.

3.2 Converting Action Descriptions to ASP Rules

Following the same idea of Satplan [Kautz and Selman, 2006] to view automated planning as a constraint satisfaction problem, ASP can be used as an automated planner as well [Lifschitz, 2002]. Given a planning problem P , one can construct an ASP program ΠP such that 〈s0, a1, s1, . . . , an, sn〉 is a trajectory of a plan of P iff there exists an answer set of ΠP that contains holds(f, i) for each fluent f and 0 ≤ i ≤ n such that si |= f, holds(¬f, i) for each fluent f and 0 ≤ i ≤ n such that si |= ¬f and occurs(ai, i) for each action ai and 1 ≤ i ≤ n. Intuitively, that holds(f, i) (holds(¬f, i)) belongs to S means that the fluent f is true (false) in the state si; that occurs(ai, i) belongs to S means that the action ai occurs at the state si-1.

Here, one of the main challenges of ASP is how to obtain the rules about action effects. Traditionally, this is handcoded by experts. In our approach, we present a new method to obtain those rules by exploiting semantic roles of common verbs in semantic dictionaries (e.g., FrameNet). In the previous section, we formalize semantic roles of common verbs in FrameNet into action descriptions in our meta language LM. Now, we show how to automatically convert those action descriptions into ASP rules.

We first translate formulas in LM into rules. Formally, let F be a form obtained from <formula>. We use tr(F, i) (for some nonnegative integer i) to denote the set of ASP rules:

• If F is in the form ( p t1 · · · tm ) where p is the name of a predicate and t1, . . . , tm are semantic roles, then p(t1, . . . , tm) is a fluent in the action signature, thus

• If F is in the form ( and F1 · · · Fm ) where F1, . . . , Fm are <formula>, then tr(Fj , i) for each 1 ≤ j ≤ m and

• If F is in the form ( or F1 · · · Fm ) where F1, . . . , Fm are <formula>, then tr(Fj , i) for each 1 ≤ j ≤ m and

· · ·

• If F is in the form ( not F1 ), then tr(F1, i) and

Based on this, we are able to translate meta tasks in LM into rules in ASP as well. Let φ be a task based on the meta task Φ, and I a <invariant-def> in Φ, we use tr(I, k, n) (for some nonnegative integers k and n s.t. k ≤ n) to denote the set of ASP rules:

• If the form is ( :invariant <formula> ) and F is <formula>, then tr(F, i) (k ≤ i ≤ n) and

• If the form is ( :and I1 · · · Im ) where I's are <invariant-def>, then tr(Ii, k, n) (k ≤ i ≤ n) and

• If the form is ( :or I1 · · · Im ) where I's are <invariant-def>, then tr(Ii, k, n) (k ≤ i ≤ n) and

· · ·

• If the form is ( :not I1 ) where I1 is <invariant-def>, then tr(I1, k, n) and

Let φ be a task based on the meta task Φ, we use tr(φ, k, n) (k ≤ n) to denote the set of ASP rules:

• For each <precond-def> in Φ and F be a <formula>, then tr(F, k) and

• For each <postcond-def> in Φ and F be a <formula>, then tr(F, n) and

• For each <step-def> S in Φ and φ1 · · · φm be the sequence of task/action names obtained from <task variable list>, then for every possible sequence n1 , . . . , nm-1 of nonnegative integers with k ≤ n1 ≤ · · · ≤ nm-1 ≤ n, we denote n0 = k and nm = n, then for each 1 ≤ i ≤ m,
• if φi is an action, then ← complete(φi, ni-1 , ni ), not occurs(φi, ni-1+1).
• if φi is a task, then tr(φi, ni-1 , ni ), and the rules

Finally, tr(φ, k, n) contains rules:

3.3 Plan Generation

Now, we are able to use an ASP program including the rules obtained from semantic roles of common verbs in FrameNet for robot task planning. Suppose that we have a robot task planning problem with a high-level task and some potential low-level actions and fluents (i.e. atomic formulas with time arguments) in a domain. Firstly, we seek for related common verbs in FrameNet. If found, we convert the semantic roles of these common verbs into ASP rules by the aforementioned techniques. Together with rules obtained from the high-level task and other rules for ASP planning, we form an ASP program. Finally, we call an ASP solver to compute an answer set of the ASP program grounded by objects in the domain, which corresponds to a executable plan for the highlevel task.

Example 2 [Continued with Example 1] Consider the high level task "take a beer from the refrigerator to the dinner table" with some (not limited to) low level actions

• move(L)1 : move to the location L;
• grasp(x): grip the object x and pick it up;
• putdown(x): put the object x down;
• open(y): open the object y;
• close(y): close the object y;
• takeout(x, y): take the object x out of the object y; as well as some (not limited to) fluent:

• location(L): L is a location;
• portable(x): the object x is portable by the robot;
• at(x,L): the object x is located at the location L;
• in(x, y): the object x is in the object y;
• on(x, y): the object x is on the object y;
• opened(y): the object y is opened;
• same-location(x, y): x, y have the same location;
• equal(L1,L2): location L1 and L2 are the same.

We first analyze the high-level task "take a beer from the refrigerator to the dinner table" by the semantic parser. From which, we know that "take" is a high level task while "beer", "refrigerator" and "dinner table" are concrete objects in the domain. Then, we seek for related common verbs in FrameNet that are similar to the task name "take", and we find a matching one "task-bringing". Next, we convert the semantic roles of the common verb "task-bringing" into ASP rules, as shown in aforementioned techniques. Then, we ground the program obtained from those rules and the domain objects "beer", "refrigerator" and "dinner table", and we can found that "beer" is matched as a ?theme, "refrigerator" as a ?source, and "dinner table" as a ?goal.

Finally, we call an ASP solver iclingo/oclingo 2 to solve the grounded ASP program and find the following answer set:

which is a plan for the original high level task "take a beer from the refrigerator to the dinner table".

4 Experiments

In the experiments, we evaluated our ASP planner on the common benchmarks widely used for domestic service robots [Chen et al., 2013; 2012; Kunze et al., 2010; Tenorth and Beetz, 2013], consisting of two data sets with 11885 task-oriented user instructions from the Tasks/Steps table and 467 desire-oriented user instructions from the Help table of OMICS. Table 1 shows the top 10 most frequently used common verbs in the data sets. It can be observed that most of them are not low-level executable actions (such as move, find, pick up, put down, open and close) but high-level common verbs (such as put, turn, get and place). Hence, it is crucial for service robots to do task planning, i.e., generating a sequence of low-level executable actions in order to complete the required tasks described by those high-level common verbs in the benchmark problems.

1 An action name with variables is consider to be a shorthand for the set of all ground instances.

2 http://www.cs.uni-potsdam.de/oclingo/

We compared our ASP planner to the OK planner [Chen et al., 2013] - currently the leading task planner for domestic service robots that is capable of exploiting open knowledge. Specifically, we compared both planners in terms of the number of successfully planned tasks on the aforementioned benchmarks. In addition, we consider two sets of configurations. The first is about the searching method. While local means that the system only use one decomposition rule, global means that it will explore all decomposition rules in the data sets. The second configuration is whether the task planner utilizes other semantic dictionaries such as WordNet [Fellbaum, 1998] for measuring word similarities. For instance, "set down" is semantically similar to "put down". Here, WordNet means that this technique is used.

Table 2 summarizes our results. Our ASP planner significantly outperforms the OK planner in terms of the number of successfully planned tasks in all categories. For instance, for using the local search method without WordNet on 11885 task-oriented instructions, while the OK planner can only successfully generate 66 plans, our ASP planner can generate 765, which is 11.6 times better. Even for the least improvements, i.e., the global search method with WordNet on desireoriented instructions, our ASP planner is 2.25 (=379/168) times better than the OK planner.

There are two main reasons for this improvement. Firstly, semantic roles of common verbs in FrameNet brings more knowledge for task decomposition and planning. Secondly, the ASP solver can automatically explore all possible combinations of action sequences and generate plans, which is much more powerful than predefined hand-coded task decomposition rules.

Notably, the ASP planner + WordNet approach can achieve a high success rate of 81.16% (379 out of 467) for task planning on desire-oriented instructions. This is because the approach utilizes many semantic roles of common verbs in FrameNet. Indeed, as shown in Figure 3, the more frames added, the higher success rate we have. Notice that sometimes the curves experience a flat improvement (e.g., our ASP planner for task-oriented instructions in the middle). This is due to the limit of our robots' capability to perform some low-level executable actions so that some frames (e.g., Mass motion and Waiting) cannot be grounded.

Nevertheless, there are still a large number of task-oriented instructions that cannot be successfully planned by our approach. There are two typical types of failures. The first failure type is about the natural language processing, that is, our semantic parser cannot retrieve any frames from FrameNet. As far as we have counted, 26.7% of the failures belong to this category. The second failure type is ASP failures. In this case, our ASP planner fails to generate a plan. There are two main reasons. First, FrameNet is far from complete so that there is a huge lack of knowledge about actions. Second, the number of low-level executable actions for our robot is restricted so that some high-level actions are essentially beyond its capability. However, the success rate will be improved by using the same method proposed in our approach with more knowledge created in new online resources and more reliable information extraction tools.

Apart from the above corpus-based experiments, it is worth pointing out that our integrated system with the proposed ASP planner has been deployed in a service robot and used in the annual RoboCup@Home 3 competitions for planning tasks with user instructions in natural language, which won the champion in 2014 and the runner-up in 2015. This confirms the usefulness of our approach for real robot task planning. A demo video with our robot system is available at: https://youtu.be/bBU86dciEwo

5 RelatedWork

Many approaches on task planning for service robots have been proposed in the literature. Unlike our integrated system, most of them decompose user instructions into lowlevel subtasks based on pre-given knowledge obtained from domain experts [Misra et al., 2016; Tellex et al., 2011], which usually scale poorly to large number of tasks. To improve generality and scalability, researchers have tried to exploit open knowledge resources [Chen et al., 2013; 2012; Nyga and Beetz, 2012]. Still, there are a large portion of tasks that cannot be decomposed based on the decomposition rules using existing open resources. This motivates us to develop our system with ASP planner and sematic dictionaries.

3 http://www.robocupathome.org

There are also a number of approaches using AI techniques for robot task planning. To name a few, these planning systems are implemented for performing service tasks in a kitchen environment [Keller et al., 2010], finding sequence of actions required by several different robots [Buehler and Pagnucco, 2014], or embedded into Robot Operating System (ROS) [Cashmore et al., 2015]. [Hanheide et al., 2015] implemented a three-layer architecture on a mobile robot to enable robots to plan with uncertain and incomplete information. Some approaches [Gaschler et al., 2013] do not only reason about low-level executable actions but also on geometric preconditions and the effects of complex actions. However, most of them require hand-coded action effects for specific domains with restricted scalability and generality.

Our meta-language is related to the Modular Action Description (MAD) language proposed by [Lifschitz and Ren, 2006]. MAD is devised to compile a general-purpose database of knowledge about actions, in which one can "factor out" common elements of specific action domains on commonsense reasoning and planning. There are also several significant differences from ours. Firstly, our meta-language is motivated to express rewritten knowledge related to common verbs and their corresponding user tasks, while MAD focuses on representing common features of actions in order to make the language more elaboration tolerant [McCarthy, 1998]. Secondly, the definition of a common verb may involve a sequence of steps on how to accomplish the corresponding tasks as in our meta-language.

6 Conclusion

We have presented a novel integrated system for large-scale, general-purpose robot task planning. Specifically, we proposed a new method that combines automated planning in ASP and semantic roles of common verbs defined in semantic dictionaries (e.g., FrameNet). Our experimental results on the OMICS datasets show that the integrated system benefitted from the knowledge about actions obtained from FrameNet and significantly outperformed the state-of-the-art solution. Furthermore, based on the planning system, our service robot achieved encouraging results with one champion and one runner-up in the RoboCup@Home competitions.

For future work, one potential direction is to automatically extract knowledge about actions from not only semantic dictionaries but also other resources including plain texts and web pages. Additionally, we plan to consider a richer syntax that is able to represent different kinds of knowledge.

Acknowledgments

This work was supported by National Natural Science Foundation of China under grant No. U1613216. Feng Wu was supported in part by National Natural Science Foundation of China under grant No. 61603368, the Youth Innovation Promotion Association of CAS (No. 2015373), and Natural Science Foundation of Anhui Province under grant No. 1608085QF134.