Grounding Abstract Spatial Concepts for Language Interaction with Robots

1 Introduction

Natural language communication with robots has been a long standing goal in robotics and AI. As robots to enter our factories, workplaces and homes where e�ective communication between humans and robots is vital. Natural language provides a rich, intuitive and flexible medium for humans and robots to interact and share information. The problem of "grounding" or understanding natural language instructions involves determining the higher-order semantic concepts expressed in the utterance and relating these concepts with entities perceived in the world. Inspired by statistical machine translation, recent approaches [Howard et al., 2014b; Tellex et al., 2011; Boularias et al., 2015; Matuszek et al., 2012; Oh et al., 2015] pose the grounding problem as inference on a graphical model structured according to the well studied parse structure of language. These models estimate correspondences between linguistic constituents in an instructions and semantic entities perceived in the world. Present models can only ground concrete entities such as objects/regions, and cannot model abstract semantic concepts. E.g., spatial aggregations like "rows, columns or groups" common in human language, Figure 1.

We present the Adaptive Distributed Correspondence Graph (ADCG) model that enables grounding of abstract concepts referenced in language utterances. The model introduces a factorization over concrete and abstract symbols such that reflects the hierarchical structure of abstractions and allows e�cient approximate inference in the exponentiallylarge space of abstractions. Empirical evaluation revealed significantly lower inference runtime with equivalent accuracy compared to the state of the art baseline. This work appeared in [Paul et al., 2016]. Here, we present an abridged version elucidating the central contribution.

2 Grounding Natural Language Instructions

Consider the robot manipulator operating in a workspace � modeled as a collection of rigid bodies. Let, groundings � denote semantic concepts that are conveyed by an input language instruction �. These include notions such as objects, locations, regions derived from the world model or future actions the robot can execute. E.g., the instruction "pick up the block on the table" include objects for phrases "the block" and "the table", the phrase "on" is interpreted as a region above the "table" and the phrase "pick up" associated with the intended grasp action to be executed by the robot. The instruction � consists of a set of phrases f�1; �2; : : : ; �ng determined from a parse tree �(�). The grounding problem is posed as estimating the likely set of groundings � = f�1; �2; : : : ; �ng for each phrase in the input instruction:

Contemporary techniques such as Distributed Correspondence Graphs (DCG) [Howard et al., 2014a] pose the grounding problem as inference on a factor graph. The grounding process is mediated by a binary correspondence variable �i j that expresses the degree to which the phrase �i 2 � corresponds to a possible grounding �i j 2 �. The graph is constructed according to the parse structure of the input instruction such that the latent grounding for a phrase �i is conditioned only on groundings � ci for child phrases:

Next, we introduce Adaptive Distributed Correspondence Graphs (ADCG) that enable modeling and inference over abstract concepts.

3 Probabilistic Model

In this section, we first define the space of groundings followed by detailing the probabilistic model and finally discuss the inference procedure.

3.1 Generalized Space of Groundings

We define the space of grounding symbols � that represent semantic concepts expressed in input language �. The robot's workspace is represented as the set of objects O each possessing geometric, appearance and pose information, typically obtained from a perception system. We assume that the robot is capable of executing a set of manipulation actions ("pick", "place", "clear" etc.) parameterized by the objects under consideration. Additionally, we incorporate symbols expressing cardinality ("two", "three", "four" etc.), ordinality ("fifth", "sixth", "seventh" etc.) and spatial regions ("left", "center", "behind" etc.) associated with objects in the scene. The introduced symbols collectively form the space of concrete symbols � C .

Abstract concepts such as "rows", "columns", "groups", "towers" etc. are introduced as hierarchical symbols composed of concrete entities as conveyed in an instruction like "the column of red blocks". Formally, an abstraction � includes a subset of objects Oj � O possessing a common spatial characteristic ("linearity", "circularity", "directivity" etc.) denoted by the set �: � = f(�i;Oj)j�i 2 � ;Oj � Og. The number of possible containers is j�j � jP(O)j, where P denotes the power set. Hence, the symbol space of containers and associated regions is exponential O(2 NO ) in the number of objects populating the world model. The symbolic representation presented above forms the space of abstract groundings � A . Note that the space of concrete groundings grows linearly as O(NO). However, the space of abstractions is exponentially large in the number of concrete groundings O(2 NO ). Even in a simplistic block world setup with 20 objects, Figure 1, results in an abstract search space that includes 17.3 million symbols.

3.2 Factor Graph

Estimating the likely correspondences � between the input natural language instruction � and the generalized space of groundings � C [ � A is posed as inference on a factor graph. Following the DCG factor graph construction [Howard et al., 2014a], the concrete correspondence variables � C i j are introduced that relate a phrase �i with concrete groundings � C i j . Next, we introduce notions of abstract symbols in the model. Figure 2(b-left) illustrates an approach that introduces a shared factor between all concrete correspondences, modeling an abstract such as a "row" composed of concrete groundings like "blocks". Although, this factor expresses the distribution over possible aggregations of concrete groundings, the representation possesses the disadvantage that grounding for a parent phrase such as, "the middle block in the row" becomes correlated with the inference over abstractions from concrete groundings. Consequently, we introduce explicit abstract grounding variables � A ik and correspondences � A ik , Figure 2(b-right). In this formulation, the abstract correspondences act as indicator functions distinguishing each expressed aggregation and and form a Markov boundary for the concrete correspondences. Given the knowledge of the abstract correspondence variables, a hierarchically linked grounding, like "the middle block" is de-correlated with the joint distribution over concrete constituents. Figure 2(b) presents the factor graph. The joint distribution is modeled as a product of factor potentials � given as:

Each factor in the model relates unknown concrete � C i j or abstract � A ik correspondences between an input phrase �i and probable groundings � C i j or � A ik respectively. The grounding for a phrase is conditioned on expressed groundings from the child phrase indicated by correspondences � C ci and � A ci . An abstract factor links the input phrase with correspondences related to abstract groundings. Let the variable set � C i denote the concrete correspondences for the current phrase. Each abstract factor estimates correspondence � A ik and jointly reasons with the estimated concrete child groundings � C i for the current phrase. This expresses the probabilistic linkage between a hierarchical abstract grounding and the set of concrete groundings, e.g. "column of blocks on the right". Factor potentials � are endowed with a log-linear model composed of a linear combination of predictive feature function incorporating spatial and lexical cues.

3.3 Approximate Inference

Inference in the graphical model is posed as tree-structured search over possible correspondences between phrases and groundings given child context. The inclusion of abstract groundings leads to an exponential increase in the size of the search space, rendering exhaustive search infeasible. In order to search e�ciently, we leverage a partitioning of the joint distribution between concrete and abstract factors, Equation 3. For each phrase, factor evaluations are ordered such that the distribution over concrete symbols given child groundings is determined first and the set of probable solutions above a confidence threshold are obtained. The set of possible object groundings are obtained as:

Instead of exhaustively searching over the entire abstract search space, the procedure uses the expressed concrete groundings to selectively instantiate a restricted space of probable abstract symbols that is then explored for solutions. The estimated object groundings are used to estimate a reduced space of probable abstractions: d �(i) = f(�i;c Oj)j�i 2 � ; c Oj � Og. Note that each abstract factor is conditioned on the expressed concrete groundings as well as groundings from child phrases. Instead of exhaustively searching over the entire abstract search space, the procedure uses the expressed concrete groundings to selectively instantiate a restricted space of probable abstract symbols that is then explored for solutions. The approximate abstract search space � d A(i) is not fixed, but varies dynamically per phrase �i and is determined based on the estimated true concrete groundings. The induced abstract factors constitute the following approximate joint distribution:

4 Evaluation

The proposed model was evaluated using a corpus generated from a user study.

The corpus consisted of natural language descriptions paired with simulated scenes demonstrating a Baxter robot carrying out manipulation tasks with varying blocks arrangements, Figure 3. The language descriptions were provided by human subjects via the Amazon Mechanical Turk platform. The data set consisted of 135 language descriptions, each paired with spatial context arising from 21 randomized workspaces resulting in a total of 1672 annotated phrases. The input instructions were tagged with part-of-speech labels from the Penn Tagset [Marcus et al., 1993] and parsed using the Cocke-Kasami-Younger (CKY) algorithm [Younger, 1967]. The proposed ADCG model was compared against the DCG [Howard et al., 2014b] model as a baseline. For a fair comparison, the DCG search space was expanded to include all possible abstract concepts (the power set of concrete constituents) as independent without being hierarchically linked with concrete groundings. The log-linear model training step, feature sets and training remained the same for both models.

Figure 4 compares the grounding accuracy for instructions in the corpus for the proposed ADCG model and the baseline DCG model. Training was carried out using randomly sampled subsets and increasing the holdout fraction from 0.2 to 0.8 in increments of 0.05 with 9 runs for each fraction. Maximum probable groundings (above a 0.75 threshold) were determined for each phrase in the parsed instruction. The ADCG accuracy closely followed the DCG baseline. The model correctly grounded instructions like, "the second farthest block to the left in the row of blocks in front of the robot". References to abstract concepts in the context of spatial and numeric information like "horizontal line of four blocks", "farthest three blocks", "row of blocks in front", "group of eight blocks", "nearest two blocks" etc. are correctly grounded. References to constituent elements like "middle", "second farthest", "nearest" are also correctly inferred by the system.

Table 1 presents the total average inference runtime normalized by the number of phrases per instruction for the corpus. The ADCG model has significantly lower average runtime than the DCG baseline. The runtime gain for the ADCG model is more pronounced with greater scene complexity. The runtime for grounding abstract concepts is determined by the total size of the grounding space searched for solutions. The ADCG model is able to determine a reduced space of probable hypotheses and hence searches an approximate reduced space compared to the DCG baseline model that exhaustively searches for solutions. This approximation leads to a significant e�ciency gain with minimal loss in accuracy, as demonstrated in Figure 4. We believe that the technique of ordering factor computations and exploiting the conditional structure of hierarchical concepts linked with concrete concepts to estimate a smaller space of probable concepts may have applicability for search in other domains where similar structure exists.

Acknowledgements

This work was supported in part by the Robotics Consortium of the U.S Army Research Laboratory under the Collaborative Technology Alliance Program and by the National Science Foundation under Grant No.1427547.