Accepted for the 1st International Workshop on Automatic Translation for
Signed and Spoken Languages (ATS4SSL), August 20, 2021

# Sign and Search: Sign Search Functionality for Sign Language Lexica

Manolis Fragkiadakis<EMAIL_ADDRESS>
Leiden University Centre for Digital Humanities, Leiden University, Leiden,
2311VJ, the Netherlands Peter van der Putten
<EMAIL_ADDRESS>
Leiden Institute of Advanced Computer Sciences, Leiden University, Leiden,
2333CA, the Netherlands

###### Abstract

Sign language lexica are a useful resource for researchers and people learning
sign languages. Current implementations allow a user to search a sign either
by its gloss or by selecting its primary features such as handshape and
location. This study focuses on exploring a reverse search functionality where
a user can sign a query sign in front of a webcam and retrieve a set of
matching signs. By extracting different body joints combinations (upper body,
dominant hand’s arm and wrist) using the pose estimation framework OpenPose,
we compare four techniques (PCA, UMAP, DTW and Euclidean distance) as distance
metrics between 20 query signs, each performed by eight participants on a 1200
sign lexicon. The results show that UMAP and DTW can predict a matching sign
with an 80% and 71% accuracy respectively at the top-20 retrieved signs using
the movement of the dominant hand arm. Using DTW and adding more sign
instances from other participants in the lexicon, the accuracy can be raised
to 90% at the top-10 ranking. Our results suggest that our methodology can be
used with no training in any sign language lexicon regardless of its size.

##  1 Introduction

Sign language lexica are a valuable source for people learning sign languages,
teachers and parents who need to communicate in signs with their deaf children
as well as researchers studying the languages in question. These lexica allow
the user to submit a query containing a unique identifier that by definition
refers to a sign (commonly referred to as gloss) and retrieve a video or an
image of that sign. In addition to this functionality, some lexica let the
user define the formal parameters of the target sign (i.e. its location,
handshape, or movement) and retrieve all the signs that contain these
features. It is then at the users’ discretion to view all the provided signs
and select the desired ones. These search functionalities are particularly
useful as sign languages, contrary to spoken languages, do not have any
unified notation system for sign representation.

Even though a sign search functionality which is based on formal parameters is
a user-friendly option in sign language lexica, it still requires manual
annotation. Dictionary compilers have to manually link these values to the
individual videos of signs. This is a time consuming and prone to errors task
and, as Zwitserlood, (2010) discusses, it is the reason why only a few of such
dictionaries exist to date. More importantly, according to Zwitserlood, these
dictionaries are unidirectional “giving only signed translations of words from
a spoken language in a one-to-one relation” (Zwitserlood,, 2010). Furthermore,
as the retrieved results contain only the parameters selected by the user, the
signs are presented in no particular order.

In this paper, we describe a methodology and its experimental results for
multi-directional search functionality for sign language lexica. Our proposed
method, extending on previous efforts by Schneider et al., (2019) and
Fragkiadakis et al., (2020), utilizes either the Uniform Manifold
Approximation and Projection for Dimension Reduction (UMAP) technique or the
Dynamic Time Warping (DTW) algorithm to measure the distance between a query
sign and all the signs in a lexicon. Both techniques require no training, thus
making our methodology applicable to any sign language. Requiring training
would add further obstacles to making dictionaries widely available, similar
to how the need for manual annotation is limiting dictionary availability.
Finally, these methods have been compared to two other techniques namely
Principal Component Analysis (PCA) and Euclidean distance.

The paper is organized as follows: in Section 2 we discuss the research which
has been conducted in relation to search functionality for sign language
lexica or has the potential to be applied in that domain. In Section 3 we
describe our methodology regarding the extraction of the body joint
coordinates as well as the methods and algorithms compared in this study. In
Section 4 we present the results of our experiments. We discuss them in
Section 5 and conclude and motivate future research in Section 6.

##  2 Related Work

Over the last decade, many research projects have examined the use of
computer-vision techniques to allow a user to search a sign in a database or
lexicon by performing it in front of a camera or sensor. Wang et al., (2012)
have developed a system for semi-automatic search functionality. In their
system, a user marks the start and end frames of a sign and denotes whether
the sign is one- or two-handed. Consequently, the system detects the hands on
the basis of skin color and motion. The user can correct, if needed, the
detected hand locations and pass the query to the system. Using Dynamic Time
Warping their approach computes the similarity between the query sign and all
the signs in the database. Their results suggest a 78% accuracy on the top-10
retrieved signs on a 1113 sign lexicon. While the accuracy rate is high
enough, the user still needs to indicate the handedness feature (one- or two-
handed) as well as the duration of the sign. Additionally, the data-set used
in this study has been recorded under studio conditions posing the question of
applicability on noisy real-life conditions on the video query.

Conly et al., (2015) have used Dynamic Time Warping to match a sign on an
American Sign Language dictionary. Using Microsoft’s Kinect they detect the
hand positions and perform sign matching. Their results suggest an accuracy of
77.3% on the top-50 retrieved signs. A major advantage over Wang’s et al.
(2012) implementation is that this system does not require the intervention of
the user.

Metaxas et al., (2018) have developed a framework that analyzes handshape,
orientation, location, and motion trajectories to recognize 350 ASL signs. By
passing the extracted features into Hidden Conditional Ordinal Random Fields
(HCORF) they achieve a top-1 accuracy of 93.3% and a top-5 accuracy of 97.9%.

Vidalón and Martino, (2016) have created a system for Brazilian Sign Language
recognition using Dynamic Time Warping, a Nearest-Neighbor classifier and
Kinect. On a data-set of 107 signs, they have reported an accuracy of
approximately 98%. A major drawback of their results is the fact that their
data-set is user-dependent.

The majority of the aforementioned studies use either a depth sensor or
computer-vision techniques. These techniques primarily rely on color and
motion detection algorithms, as feature extraction methods, which imposes
additional problems. Such techniques can be prone to errors and most
importantly require studio conditions in order to predict the required
features such as the face and the hands. While such conditions can be true for
the videos in a lexicon they cannot be assumed for the query videos. Searching
a lexicon can be done in any possible space and lighting conditions, thus it
is important that the technique used to capture the required features to be as
much as inclusive as possible.

In 2017 Cao et al., (2017) presented a framework for multi-person 2D pose
estimation, OpenPose. This framework can efficiently detect body, foot, hand
and facial key-points from a simple RGB video or picture. Its high accuracy,
performance and easy implementation make it the ideal framework to parse sign
language and gestural videos. Its output consists of multiple json (or
differently formatted) files containing all the pixel x, y coordinates of the
body, hand and face joints. Most studies use OpenPose to pre-process the
videos and use its output to further train or compare machine and deep
learning models.

Schneider et al., (2019) have used OpenPose as well as DTW and Nearest-
Neighbor algorithm to perform classification of six gestures. Their results
suggested an accuracy of 77.4%. Most recently, Fragkiadakis et al., (2020)
have used OpenPose and DTW to predict a sign recorded using a webcam from a
100 signs lexicon. Their method predicted the matching sign with an 87% and
74% accuracy at the top-10 and top-5 retrieved signs by using the path of the
dominant hand’s wrist.

This study extends on previous efforts for efficient sign ranking for sign
language lexica by:

  * •

Considering a far larger lexicon compared to previous efforts: 1200 signs in
total

  * •

Comparing four different techniques: Principal Component Analysis (PCA),
Uniform Manifold Approximation and Projection for Dimension Reduction (UMAP),
Dynamic Time Warping (DTW) and Euclidean distance

  * •

Comparing three different skeletal joint combinations (upper body, dominant
hand arm, dominant hand wrist)

  * •

Exploring potential accuracy increase by adding more sign instances in the
lexicon

An important difference from previous studies in search functionality for sign
language dictionaries is that in our case we expect signers to not “properly”
sign a particular sign. As Alonzo et al., (2019) discuss, it is possible that
people would not remember exactly how a sign is performed, and as a result,
they might sign it slightly differently. Thus it is expected that the matching
sign would not be in the first retrieved sign result. This is precisely the
reason why we tested our methodologies on a data-set that contains signs
performed also by people with no or little experience in sign language. In
most sign language data-sets used for sign language recognition tasks, signs
are mostly performed by people familiar with sign languages. However, sign
language lexica are intended also for people with little knowledge of sign
language. As a result, high variability is expected when recording a sign.

Another limitation posed in our study is that sign language lexica do not
often contain multiple instances of a particular sign. While various studies
using deep learning techniques have shown high accuracy in predicting
different signs (Li et al.,, 2020; Gökçe et al.,, 2020; Sincan and Keles,,
2020; Hosain et al.,, 2021), they cannot be used in our case. These techniques
often require vast amount of data in order to be trained which might not be
available on all sign language lexica. Our main goal is to develop a system
that can be easily used in any sign language lexicon regardless of the amount
of data in it and most importantly the language itself. However, in this
study, we explore the possibility of having a few additional sign instances in
the lexicon and their potential benefit to successful sign retrieval.

##  3 Data-sets and Methods

In this section we describe the data pre-processing as well as the data-sets
and methods used in this study.

###  3.1 Data Pre-processing and Normalization

OpenPose outputs x, y pixel coordinates for each predicted body and finger
joint. These pixel coordinates are relative to the frame size and as a result
it is important to normalize them to account for different positions in the
frame. As all people in the data-set (both in participants’ and lexicon’s
data) are expected to be in an upright position in front of the camera,
rotational in-variance is omitted. The normalization process is the following:
for each detected person in a frame, the neck key-point coordinates are
subtracted from all the other key-points. Subsequently, all key point
coordinates are being divided by the distance between the left and right
shoulder key-point. Finally, a horizontal flip is applied when a participant
is left-handed by calculating the average velocity of each hand’s wrist. The
overall normalization process is based on previous studies by Celebi et al.,
(2013), Schneider et al., (2019) and Fragkiadakis et al., (2020). Furthermore,
all signs have been re-interpolated to 86 frames which is the mean sign
length. Although it makes little difference to DTW’s accuracy, equal length
inputs make it easier to handle.

###  3.2 Data-sets

For this study we used the Ghanaian Sign Language lexicon (GSL) (Fragkiadakis
et al.,, 2021; HANDS!Lab,, 2020). This lexicon consists of 1200 signs from one
signer and has been compiled for educational purposes to be used in a mobile
application. A lot of studies in the sign language recognition field have used
sign language data-sets from well documented sign languages with primarily
signers with light skin tones. We have decided to apply our methodology in a
sign language less documented and analyzed with computer vision and machine
learning algorithms in order to further explore how these techniques can
perform in such conditions.

In addition, the data gathered by Fragkiadakis et al., (2020) have been used
to compare the different algorithms described in the next section. This data-
set contains the data of ten participants. Each one of them performed the same
20 signs, from the original lexicon, in front of a webcam. The data of two
participants have been discarded due to inconsistencies of OpenPose on
recognizing their right-hand finger’s and left arm joints.

We have decided to include in the lexicon the data from a random participant
every time we tested the methodology. As the lighting conditions on the
participants’ videos were of poor quality, the predicted body joints by
OpenPose had substantially more noise compared to the ones predicted on the
lexicon’s data. By extending the database with another participant’s data, we
introduced some noise to the otherwise non-noisy data-set. As a result, each
participant’s sign was compared with 1220 signs in our database (1200 from the
GSL lexicon and 20 from another random participant). A complete overview of
the participants’ data-set and the apparatus used to gather the data can be
found in Fragkiadakis’s et al. (2020) study.

One of the main goals of this study is to find if and how different skeletal
joints affect the accuracy of the algorithms. As a result, we have compiled 3
different data-sets per condition per participant’s data. The first data-set
contains the upper body joints as well as the dominant hand fingers joints’
coordinates resulting in a $86\times 29\times 2$ (frames _by_ skeletal joints
_by_ x, y coordinates) dimensionality per sign. Consecutively, the second
data-set contains the dominant hand arm joints’ coordinates (nose, neck,
shoulder, elbow, wrist) resulting in a $86\times 5\times 2$ dimensionality per
sign. Finally, the data-set regarding the dominant hand wrist data has a
$86\times 2$ dimensionality per sign.

###  3.3 Methods

The following section describes the methods and the four techniques used in
this study.

####  3.3.1 Dimensionality Reduction

As described in the previous section, each sign in each compiled data-set can
be seen as a multidimensional vector. To properly project it into the 2D space
while still retaining most of the original information, we used two
dimensionality reduction techniques.

The first technique applied is Principal Component Analysis (PCA). PCA is an
orthogonal linear transformation that converts the data to a new frame of
reference. PCA constructs Principal Components as linear combinations of the
initial variables. These components are not correlated and most of the
information within the introductory variables is compressed into the first
components. By disposing the components with low information and taking into
account the remaining ones as new variables, it allows for dimensionality
reduction without loosing information. As a technique it has been widely used
in the gestural as well as the sign language domain either as a visualization
technique or as a pre-processing stage prior to other machine and deep
learning stages (Gweth et al.,, 2012; Sawant and Kumbhar,, 2014; Haque et
al.,, 2019; Gao et al.,, 2021).

Furthermore, the Uniform Manifold Approximation and Projection for Dimension
Reduction (UMAP) technique has been utilized. This method has been used
instead of another popular dimensionality reduction technique called
t-distributed stochastic neighbor embedding (T-sne) (Van der Maaten and
Hinton,, 2008). T-sne’s inability to preserve the global structure of the data
makes it unusable if distances between different clusters or points need to be
calculated such as in our case (McInnes et al.,, 2018). In contrast, UMAP can
better preserve both local and most of the global structure in the data
allowing the calculation of distance metrics between clusters. Moreover, the
lack of normalization in UMAP effectively reduces the time of computation of
the high-dimensional graph.

In our study both PCA and UMAP have been used to reduce the dimensionality of
each sign to a single x, y coordinate. Subsequently, we measured the euclidean
distance between all the signs of the lexicon and the participants’ signs.
Accuracy for each participant’s sign was measured based on whether the target
sign was on the top-k shortest distant signs.

Furthermore, in order to validate the results produced by the UMAP algorithm
in its ability to preserve the global distances of the data, we calculated
their euclidean distances in the original high-dimensional space. This method
has been used as a benchmark to compare the results of both PCA and UMAP.

####  3.3.2 Dynamic Time warping

In addition to the dimensionality reduction techniques described above,
Dynamic Time Warping (DTW) has been used to measure the similarity between the
different signs. Dynamic Time Warping is a dynamic programming based time
series comparison algorithm to produce a distance metric between two inputs.
It has been widely used in the speech recognition domain (Myers et al.,, 1980;
Abdulla et al.,, 2003; Axelrod and Maison,, 2004) as well as the gestural and
sign language recognition fields as shown in Section 2.

In this study we utilize a DTW python implementation with open beginning and
ending attributes by Giorgino, (2009) and Tormene et al., (2009) which in a
preliminary experiment produced better results compared to the previous DTW
implementation by Fragkiadakis et al., (2020). Similarly, we used a median
filter with radius $r=3$ for smoothing the time series signals from the body
joints.

Finally, the overall pipeline of the experiment can be seen in Figure 1.

Figure 1: Pipeline of the overall study.

####  3.3.3 How many signs?

Many sign language lexica allow their users to submit their own versions of
signs. As a result, different instances of the same sign can be stored in the
database. One of our research questions is whether having multiple instances
of each sign can potentially improve the accuracy of the algorithms. To verify
that, we progressively added the 20 signs from other participants to the
lexicon. Subsequently, we measured the average top-1 and top-10 accuracy for
each algorithm and each skeletal condition.

Such information can be useful to sign language lexicographers when compiling
sign language lexica. They can take advantage of crowd-sourcing material,
contributing not only to the augmentation of their lexica but also to the
accuracy of the models used for enhanced search functionality.

##  4 Results

Table 1 presents the overall accuracy for each of the skeletal conditions.
Top-k refers to the number of signs a user must look up before finding a
correct match. Accuracy indicates whether the target sign is present in the
top-k retrieved signs and is averaged across all participants and all signs.

Highest accuracy is apparent at a top-50 level at 95% using the UMAP algorithm
and the joints of the dominant hand arm. Furthermore, top-20 rank shows an
adequate accuracy at 80% again using UMAP and the dominant hand arm
coordinates. Figure 2 presents the visualizations of the UMAP algorithm for
each of the skeletal condition for one participant. The results of the
calculated euclidean distances on the original high-dimensional space show an
adequate accuracy of approximately 68% at the top-50 rank in both dominant
hand arm and wrist data-sets.

Principal component analysis (PCA) performed, on average, better using the
wrist coordinates and showed the highest accuracy at the top-50 at
approximately 41%.

DTW showed the highest accuracy at 79% at top-50 rank using the data of the
dominant hand wrist and 77% using the dominant hand arm. On average, DTW had
the best accuracy at around 70% at the top-20 retrieved signs regardless of
the skeletal condition used, with a slight increase noticed using the dominant
hand arm data.

Figure 3 presents the top-1 and top-10 accuracy levels using DTW and UMAP that
have been computed by incrementally adding other participants’ data in the
lexicon. It can be observed that by adding more sign instances from 6
different participants, the accuracy reached a 90% level at the top-10
retrieved signs using DTW and the upper body and dominant hand wrist data.
Furthermore, a raise of approximately 15% can be noticed at the top-1 rank on
DTW using the upper body and dominant hand wrist joints by adding the data of
just 2 participants (Figure 3a). On the other hand, UMAP did not show any
adequate raise at the top-1 accuracy regardless of the added participants’
data and skeletal condition. However, an increase, of approximately 35%, can
be seen at the top-10 ranking level using the data of 2 participants (Figure
3b).

Skeletal condition | Upper body | Dominant hand arm | Dominant hand wrist
---|---|---|---
Top-k | Top - 1 | Top - 10 | Top - 20 | Top - 50 | Top - 1 | Top - 10 | Top - 20 | Top - 50 | Top - 1 | Top - 10 | Top - 20 | Top - 50
PCA | 0.0375 | 0.1562 | 0.2187 | 0.325 | 0.025 | 0.1562 | 0.2125 | 0.3437 | 0.0187 | 0.1562 | 0.2125 | 0.4125
UMAP | 0.1312 | 0.4125 | 0.6562 | 0.6937 | 0.0812 | 0.4375 | 0.8 | 0.95 | 0.1125 | 0.2562 | 0.3687 | 0.4575
DTW | 0.57 | 0.64 | 0.67 | 0.687 | 0.5188 | 0.65 | 0.7188 | 0.7763 | 0.5265 | 0.6562 | 0.7125 | 0.7937
Euclidean distance | 0.2125 | 0.4625 | 0.5325 | 0.6188 | 0.2625 | 0.5 | 0.6063 | 0.6938 | 0.1875 | 0.445 | 0.55 | 0.675

Table 1: Sign retrieval accuracy per algorithm (by row) on the three skeletal
conditions based on the top-k retrieved signs (highest value per column in
bold).

(a) upper body

(b) dominant hand arm

(c) dominant hand wrist

Figure 2: UMAP visualizations for one participant for the different skeletal
conditions. With red are the signs of the participant and with blue the
targeted signs.

(a) Top-1

(b) Top-10

Figure 3: Top-1 (a) and Top-10 (b) accuracy using DTW and UMAP based on added
participants’ data in the lexicon.

##  5 Discussion

In this study we have investigated the use of OpenPose and four different
implementations as distance metrics for an efficient ranking pipeline to
retrieve matching signs from a sign language lexicon. The results demonstrated
that, on a large vocabulary of 1200 signs, such a task can be achieved with an
adequate accuracy rate using the Uniform Manifold Approximation and Projection
for Dimension Reduction (UMAP) or Dynamic Time Warping (DTW) and the dominant
arm joints’ coordinates.

With regard to the visualizations produced by the UMAP algorithm, a few
observations can be made. Firstly, by using the upper body joints UMAP
produces discrete clusters. These clusters seem to reflect an abstract
representation of the movement of each sign. This behavior has been observed
also using the dominant hand arm coordinates, although it is more noticeable
using all the upper-body joints. We have observed that signs that have similar
movement but different handshapes are grouped close to each other.

However, special consideration needs to be made when viewing the
visualizations produced by UMAP, especially the one using the upper body
joints. The distances between the noticeable clusters, as well as their size
relative to each other, do not hold any particular meaning. This is because of
the use of local distances by the algorithm when constructing the graph.
However, our results using the euclidean distances on the high-dimensional
space suggest that UMAP preserves the original global distances.

Finally, it is worth mentioning that DTW performs equally well irrespective of
the skeletal condition used at around 70% at the top-20 rank. Overall, it
produces the most stable and consistent accuracy at the top-10 retrieved signs
at around 65%. This accuracy level can be further raised reaching 90% by
adding 6 more sign instances (from different signers) into the original
lexicon. This attribute can be further explored by lexicographers by asking
users of their lexica to submit their own versions of signs. This process can
significantly boost the performance of DTW in its ability of retrieving the
closest matching sign. A broad benefit of using such an algorithm is the fact
that lexica compilers do not need to re-train any model if more signs or sign
instances are added to their lexica.

In general, while our accuracy does not reach the ones reported by Schneider
et al., (2019) and Fragkiadakis et al., (2020) (77.4% top-1 and 74% top-5
accuracy respectively) using similar algorithms and frameworks, our methods
have been applied on a far larger lexicon (1200 signs instead of 6 and 100
respectively). As a result, we provide a better approximation on how these
methods can actually be used in real world lexica.

##  6 Conclusions

To sum up, we have obtained satisfactory results demonstrating that UMAP and
DTW, in combination with the pre-trained pose estimation framework OpenPose,
can be used as an efficient sign ranking and retrieval system. Our method can
effectively be applied to any sign language lexicon without any training
process involved.

To the best of our knowledge, this is the first study using UMAP as a
dimensionality reduction technique within the sign language domain and
showcasing the strength of such algorithm compared to other implementations.

Future work will focus on exploring additional deep learning implementations
for an efficient handshape and pose recognition. Their use, as well as
supplementary hyper-parameter optimization for the techniques used in this
study, could lead to an increase in accuracy. Whilst as we argued that for the
availability of dictionaries it will be good to focus on zero training
approaches, in future work we intend to run comparative analysis to understand
the impact of training based approaches on performance. We propose that
further research should also be undertaken in order to assess the application
of our method on different datasets and languages. On a wider level, the
techniques used in this study could be further explored to measure variation
in different sign languages. The results from the use of UMAP and DTW on a
large vocabulary suggest that these techniques might be well suited for
variation measurement tasks, broadening their use beyond the search
functionality for sign language lexica.

## References

  * Abdulla et al., (2003) Abdulla, W. H., Chow, D., and Sin, G. (2003).  Cross-words reference template for dtw-based speech recognition systems.  In Proceedings of the TENCON Conference on Convergent Technologies for Asia-Pacific Region, volume 4, pages 1576–1579. Allied Publishers Pvt. Ltd.
  * Alonzo et al., (2019) Alonzo, O., Glasser, A., and Huenerfauth, M. (2019).  Effect of automatic sign recognition performance on the usability of video-based search interfaces for sign language dictionaries.  In Proceedings of the 21st International ACM SIGACCESS Conference on Computers and Accessibility, pages 56–67. ACM.
  * Axelrod and Maison, (2004) Axelrod, S. and Maison, B. (2004).  Combination of hidden markov models with dynamic time warping for speech recognition.  In Proceedings of the 2004 IEEE International Conference on Acoustics, Speech, and Signal Processing, volume 1, pages I–173–6, Montreal, Que., Canada. IEEE.
  * Cao et al., (2017) Cao, Z., Simon, T., Wei, S.-E., and Sheikh, Y. (2017).  Realtime multi-person 2d pose estimation using part affinity fields.  In Proceedings of the 2017 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pages 1302–1310. IEEE.
  * Celebi et al., (2013) Celebi, S., Aydin, A. S., Temiz, T. T., and Arici, T. (2013).  Gesture recognition using skeleton data with weighted dynamic time warping.  In Proceedings of the 2013 International Joint Conference on Computer Vision, Imaging, and Computer Graphics Theory and Applications (VISAPP), pages 620–625.
  * Conly et al., (2015) Conly, C., Zhang, Z., and Athitsos, V. (2015).  An integrated RGB-D system for looking up the meaning of signs.  In Proceedings of the 8th ACM International Conference on PErvasive Technologies Related to Assistive Environments (PETRA), pages 1–8. ACM Press.
  * Fragkiadakis et al., (2021) Fragkiadakis, M., Nyst, V., and Nyarko, M. (2021).  Ghanaian Sign Language Lexicon.  https://zenodo.org/record/4533753.
  * Fragkiadakis et al., (2020) Fragkiadakis, M., Nyst, V., and van der Putten, P. (2020).  Signing as input for a dictionary query: matching signs based on joint positions of the dominant hand.  In Proceedings of the 9th Workshop on the Representation and Processing of Sign Languages, pages 69–74. European Language Resources Association.
  * Gao et al., (2021) Gao, Y., Xue, C., Wang, R., and Jiang, X. (2021).  Chinese fingerspelling recognition via gray-level co-occurrence matrix and fuzzy support vector machine.  EAI Endorsed Transactions on e-Learning, 7(20):1–13.
  * Giorgino, (2009) Giorgino, T. (2009).  Computing and visualizing dynamic time warping alignments in R: the dtw package.  Journal of statistical Software, 31(7):1–24.
  * Gökçe et al., (2020) Gökçe, Ç., Özdemir, O., Kındıroğlu, A. A., and Akarun, L. (2020).  Score-level multi cue fusion for sign language recognition.  In Computer Vision – ECCV 2020 Workshops, pages 294–309. Springer International Publishing.
  * Gweth et al., (2012) Gweth, Y. L., Plahl, C., and Ney, H. (2012).  Enhanced continuous sign language recognition using PCA and neural network features.  In Proceedings of the 2012 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pages 55–60. IEEE.
  * HANDS!Lab, (2020) HANDS!Lab (2020).  Ghanaian Sign Language app.  https://play.google.com/store/apps/details?id=com.ljsharp.gsldictionary&hl=es_US.
  * Haque et al., (2019) Haque, P., Das, B., and Kaspy, N. N. (2019).  Two-handed bangla sign language recognition using principal component analysis (pca) and knn algorithm.  In Proceedings of the 2019 International Conference on Electrical, Computer and Communication Engineering (ECCE), pages 1–4. IEEE.
  * Hosain et al., (2021) Hosain, A. A., Santhalingam, P. S., Pathak, P., Rangwala, H., and Kosecka, J. (2021).  Hand pose guided 3d pooling for word-level sign language recognition.  In Proceedings of the IEEE/CVF Winter Conference on Applications of Computer Vision (WACV), pages 3429–3439.
  * Li et al., (2020) Li, D., Rodriguez, C., Yu, X., and Li, H. (2020).  Word-level deep sign language recognition from video: A new large-scale dataset and methods comparison.  In Proceedings of the IEEE/CVF Winter Conference on Applications of Computer Vision (WACV), pages 1459–1469.
  * McInnes et al., (2018) McInnes, L., Healy, J., and Melville, J. (2018).  Umap: Uniform manifold approximation and projection for dimension reduction.  arXiv preprint arXiv:1802.03426.
  * Metaxas et al., (2018) Metaxas, D., Dilsizian, M., and Neidle, C. (2018).  Linguistically-driven framework for computationally efficient and scalable sign recognition.  In Proceedings of the 11th International Conference on Language Resources and Evaluation (LREC), Miyazaki, Japan. European Language Resources Association (ELRA).
  * Myers et al., (1980) Myers, C., Rabiner, L., and Rosenberg, A. (1980).  Performance tradeoffs in dynamic time warping algorithms for isolated word recognition.  IEEE Transactions on Acoustics, Speech, and Signal Processing, 28(6):623–635.
  * Sawant and Kumbhar, (2014) Sawant, S. N. and Kumbhar, M. S. (2014).  Real time sign language recognition using pca.  In Proceedings of the 2014 IEEE International Conference on Advanced Communications, Control and Computing Technologies, pages 1412–1415. IEEE.
  * Schneider et al., (2019) Schneider, P., Memmesheimer, R., Kramer, I., and Paulus, D. (2019).  Gesture recognition in RGB videos using human body keypoints and dynamic time warping.  In RoboCup 2019: Robot World Cup XXIII, pages 281–293. Springer International Publishing.
  * Sincan and Keles, (2020) Sincan, O. M. and Keles, H. Y. (2020).  Autsl: A large scale multi-modal turkish sign language dataset and baseline methods.  IEEE Access, 8:181340–181355.
  * Tormene et al., (2009) Tormene, P., Giorgino, T., Quaglini, S., and Stefanelli, M. (2009).  Matching incomplete time series with dynamic time warping: an algorithm and an application to post-stroke rehabilitation.  Artificial Intelligence in Medicine, 45(1):11–34.
  * Van der Maaten and Hinton, (2008) Van der Maaten, L. and Hinton, G. (2008).  Visualizing data using t-SNE.  Journal of machine learning research, 9(11).
  * Vidalón and Martino, (2016) Vidalón, J. E. Y. and Martino, J. M. D. (2016).  Brazilian sign language recognition using kinect.  In Lecture Notes in Computer Science, pages 391–402. Springer International Publishing.
  * Wang et al., (2012) Wang, H., Stefan, A., Moradi, S., Athitsos, V., Neidle, C., and Kamangar, F. (2012).  A system for large vocabulary sign search.  In Trends and Topics in Computer Vision, pages 342–353. Springer, Berlin, Heidelberg.
  * Zwitserlood, (2010) Zwitserlood, I. (2010).  Sign language lexicography in the early 21st century and a recently published dictionary of sign language of the netherlands.  International Journal of Lexicography, 23(4):443–476.


# Learning to Reason over Scene Graphs:
A Case Study of Finetuning GPT-2 into a Robot Language Model for Grounded Task
Planning

Georgia Chalvatzaki 1,2,3, Ali Younes 1, Daljeet Nandha 1, An Le 1, Leonardo
F. R. Ribeiro 4,† and Iryna Gurevych1,2
1 Computer Science Department, Technische Universität Darmstadt, Germany
2 Hessian.AI, Darmstadt, Germany
3 Center for Mind, Brain and Behavior, Uni. Marburg and JLU Giessen, Germany
4 Amazon Alexa, Seattle, Washington, United States
$\dagger$ Work done while at TU Darmstadt, Germany
<EMAIL_ADDRESS>

###### Abstract

Long-horizon task planning is essential for the development of intelligent
assistive and service robots. In this work, we investigate the applicability
of a smaller class of large language models (LLMs), specifically GPT-2, in
robotic task planning by learning to decompose tasks into subgoal
specifications for a planner to execute sequentially. Our method grounds the
input of the LLM on the domain that is represented as a scene graph, enabling
it to translate human requests into executable robot plans, thereby learning
to reason over long-horizon tasks, as encountered in the ALFRED benchmark. We
compare our approach with classical planning and baseline methods to examine
the applicability and generalizability of LLM-based planners. Our findings
suggest that the knowledge stored in an LLM can be effectively grounded to
perform long-horizon task planning, demonstrating the promising potential for
the future application of neuro-symbolic planning methods in robotics.

##  1 Introduction

The autonomous execution of long-horizon tasks is of utmost importance for
future assistive and service robots. An intelligent robot should reason about
its surroundings, e.g., regarding the included objects and their spatial-
semantic relations, and abstract an action plan for achieving a goal that will
purposefully alter the perceived environment. Such an elaborate course of
robot actions requires scene understanding, semantic reasoning, and planning
over symbols and geometries. The advent of Deep Learning led many researchers
to faithfully follow end-to-end approaches due to the representation power of
differentiable deep neural networks [1].

The problem of sequential decision-making has been addressed both with search-
based and optimization approaches [2, 3, 4, 5, 6], as well as learning-based
[7, 8, 9] and hybrid methods [10, 11, 12, 13]. While the first ones enjoy
probabilistic completeness, they require full domain specification and have
high computational demands. The learning-based methods require broad
exploration to learn from experience, but they have shown better
generalization capabilities in similar domains to those experienced during
training.

In recent years, Large Language Models (LLMs) have exhibited an unprecedented
generative ability [14], thanks to the transformer architecture [15] combined
with massive datasets distilled from the internet. Naturally, in the quest for
general artificial intelligence, researchers try to benchmark such models in
reasoning tasks, among others [16, 17]. Robotic embodied intelligence requires
both logical and geometric reasoning; hence, it is a holy grail of AI. Several
researchers saw a benefit in LLMs, and it was not long before several works
started exploring their application to robotics for endowing robots with the
long-wished objective of reasoning in the scope of autonomous task planning
and interaction [18, 19]. However, most of these works have focused on the
prompting [20] and the subsequent prompt engineering [21] , in which engineers
provide appropriate inputs to LLMs for extracting outputs that can be
realizable by a robotic agent, either for human-instruction following [22] or
for planning [23, 24].

This work investigates the applicability of a smaller class of LLMs for
robotics, i.e., GPT-2 [25], and we propose and investigate a method that
decomposes a long-horizon task into subgoals in the form of a goal-
specification for a robotic task planner to execute. The main contribution of
our work is the representation of the domain as a scene graph and the
subsequent linearization of the graph to keep its structure and relations
while forming a suitable input for the finetuning of the GPT-2 model. Our
thorough experimental evaluation shows that finetuning GPT-2 by additionally
grounding its input on the domain can help translate human requests (tasks) to
executable robot plans, to learn to reason over long-horizon tasks, as those
encountered in the ALFRED benchmark [26]. We compare our proposed approach
with classical planning methods to investigate the applicability and
generalizability of the Pre-trained Language Model (PLM)-based planners
compared to classical task planners operating on a limited computational
budget for a fair comparison. We conclude that the knowledge stored in a PLM
can be grounded on different domains to perform long-horizon task planning,
showing encouraging results for the future application of neuro-symbolic
planning methods in robotics.

##  2 State of the Art

###  2.1 Reasoning with Large Language Models

LLMs have attracted much attention for understanding the commonsense and
reasoning patterns in their latent space [27, 28, 29]. It has been shown that
some abilities in logical and mathematical reasoning seem to emerge when LLMs
are prompted appropriately [18, 30]. However, the engineering effort, as well
as the lack of robustness, is a key issue in prompting massive models [31,
32]. While great effort seems to be consumed on few-shot prompting of huge
parametric models, it has also been shown by other lines of work show that
efficient finetuning of much smaller models [33], or the use of small
adaptation modules (Adapters) [34, 35] can lead to methods that perform more
robustly than large-scale generalist few-shot prompters. In the same
direction, the chatbot versions of those huge models raised several points of
criticism recently, showing that much more is needed than just prompting a
blind human-preference alignment1117 problems facing Bing, Bard, and the
future of AI search, from The Verge.

###  2.2 Robot behavior planning

Long-horizon robot behavior planning is an NP-hard problem [36]. Current
advances in ML and perception led researchers to revisit this fundamental
problem, i.e., the execution of multi-stage tasks, whose completion requires
many sequential goals to be achieved, considering learning-based heuristics
[11]. Researchers consider such problems as Task And Motion Planning (TAMP)
problems [3, 12, 37], with a symbolic plan over entities and predicate with
respective action operators with preconditions and effects in the environment.
In contrast, a motion plan tries to find a feasible path to the goal.
Nevertheless, most TAMP methods rely on manually specified rules; they do not
integrate perception, and the combinatorial explosion when searching over
symbolic and continuous parameters prohibits scaling the methods to
challenging, realistic problems [10, 4].

Transformer models [15] that revolutionized the field of Natural Language
Processing (NLP) opened the way for multiple new applications, in particular
for robotics, e.g., visual-language instruction following [38], 3D scene
understanding and grounding [39, 40], language-based navigation [41, 42]. Due
to their training on extensive databases, several works explored the use of
LLMs for task planning and long-horizon manipulation [43], mainly employing
clever prompting [24, 44], using multimodal information [23, 45], grounding
with value-functions [19, 46, 47], and deploying advances in code generation
to extract executable robot plans [48]. [49] propose to use a PLM as a
scaffold for decision-making policies in interactive environments,
demonstrating benefits in the generalization abilities for policy learning
even when language is not provided as input or output. Recently, PALM-e [11]
has integrated a vision transformer with the PALM language model and has
encoded some robotic state data to propose a multimodal embodied model, which
showed the potential of integrating geometric information of the robot state
but achieved limited performance in robotic tasks.

##  3 Language models for grounded robot task planning

###  3.1 Problem statement

Let us assume an agent that is able to move and manipulate objects in an
environment, e.g., a mobile manipulator robot in a household environment. Let
the environment be composed of a combination of rooms, such as ‘bathroom,’
‘living room,’ or ‘kitchen.’ Each room contains objects and receptacles, i.e.,
objects that are able to receive other objects, such as ‘table,’ ‘drawer,’ or
‘sink.’ Each object has (household-specific) properties associated with it
that define whether it can be picked up, cleaned, heated, cooled, cut, etc.
These properties can change, meaning that the objects have a state. The agent
can pick up only one object at a time, meaning the agent also has a state,
e.g., ‘object in hand.’ Given the fact that the state is preserved over time
and future actions depend on past actions, the environment can be
characterized as sequential. Therefore, a series of actions has to be reasoned
upon for an agent to be able to execute a series of actions for solving a
long-horizon task, i.e., a task that requires the completion of several
subtasks and potentially the manipulation of various objects to achieve the
end goal.

###  3.2 The ALFRED benchmark

Figure 1: AI2-THOR simulator rendering a sample rollout from the ALFRED [26].
The scenes show a room with household objects and the robot executing a task.
Note that the robot does not have an arm, and the object automatically floats
in front of the camera; it interacts with the environment through discrete
actions. The discrete actions are shown underneath each frame in the form of
PDDL commands.

The ALFRED benchmark [26] contains human-annotated training samples and image-
based recordings of everyday household tasks; this is “25,743 English language
directives describing 8,055 expert demonstrations averaging 50 steps each,
resulting in 428,322 image-action pair”. In addition to that, the dataset
provides a PDDL domain of the overall task and a PDDL problem for each sample
[50]. ALFRED heavily depends on AI2-THOR [51], which acts as the underlying
controller and simulation environment (based on the Unity game engine):
trajectories for each sample of the ALFRED dataset were generated with
AI2-THOR and the validation of user-generated actions requires the AI2-THOR
controller. Figure 1 shows a sample scene loaded into the AI2-THOR simulator.
Each sample in the dataset consists of a high-level plan in PDDL and the
trajectory of the agent’s actions which lead to successful task completion,
together with a description of the task goal and each plan step in Natural
Language (NL).

####  3.2.1 Data augmentation

Each sample in the ALFRED dataset can be replayed in the AI2-THOR simulator to
collect additional information not contained in the original dataset. ALFRED
provides a script that has been modified for that purpose. Data augmentation
is necessary for Graph2NL (c.f. §3.8) to generate a graph representation from
the environment state. For each replayed sample, the complete list of objects
in the scene, with their respective name, position, and rotation, and the
agent position is saved to a separate file next to the trajectory data. This
file is later loaded and turned into a processable graph.

###  3.3 State and action space

The state space defines the feedback provided by the environment, while the
action space defines the available actions to interact with the environment.

State space. The AI2-THOR environment can be framed either as fully observable
when access to the complete simulator state is given, or partially observable
when the agent uses its perception (images) to observe the environment without
having access to the true state. AI2-THOR eliminates most physics-related
aspects (e.g., objects are automatically picked up and placed by a single
action), which makes the highly dynamic and stochastic household environment
almost static and deterministic — almost because some physics still exists.
This simplifies the core TAMP problem, together with the discrete agent
actions coming from the ALFRED dataset. Therefore, the ALFRED benchmark
represents an appropriate choice for studying the problem of learning for
robotic task planning, where motion failures are minimized by the underlying
AI2-THOR controllers. Hence, we can focus on the reasoning aspects of the
problem, which is the focus of this study. In this paper, the environment is
assumed to be fully observable. The state space, therefore, includes the whole
domain as provided by the simulation. In the proposed methods, the state is
transformed to NL context (§3.8) and not used directly as a model input.

Action space. ALFRED has an action space of eight discrete high-level actions:
GotoLocation, PickupObject, PutObject, CoolObject, HeatObject, CleanObject,
SliceObject and ToggleObject. The actions CoolObject, HeatObject, CleanObject
themselves are a composition of the remaining high-level actions. The
underlying AI2-THOR controller also has a discrete action space for the low-
level actions: The agent can move forward, backward, left or right and rotate
clockwise or counter-clockwise in fixed steps.

###  3.4 Task categories

The ALFRED dataset encompasses seven categories of household tasks: ‘Look at
object’, ‘Pick and place’, ‘Pick two and place’, ‘Pick and place with movable
receptacle’, ‘Pick, clean then place’, ‘Pick, cool then place’, ‘Pick, heat
then place’. Because, in mobile manipulation, objects can be placed in
different corners of a room, each of these tasks includes the sub-problem of
navigation.

For the ‘pick’ or ‘place’ subtasks executing the respective PickupObject or
PutObject action is sufficient. But, the subtasks ‘clean’, ‘cool’ and ‘heat’
must be seen as planning problems on their own, because the corresponding
actions are a composition of high-level state-dependent actions. In regards to
the household environment, the subtask ‘cool’ requires a fridge, ‘heat’
requires a microwave (or oven), and ‘clean’ requires a sink as an receptacle.

Adding to the difficulty of the ‘clean,’ ‘cool,’ ‘heat,’ and ‘cut’ subtasks is
the fact that the ALFRED simulator tracks the state of each object: the
subtask is only considered successful when the final object state is correct.
For example, if the task category is ‘Pick, clean then place’, the task goal
is only completed when the placed object is marked as ‘clean.’ The
implementation aspects of these task categories are discussed in Section 4.

###  3.5 RobLM: Robot Language Model for Task plan generation

Just like images can be represented by discretizing color space, NL can be
expressed as a sequence of tokens $\mathbf{x}=[x_{1},x_{2},...,x_{n}]$, where
each token is mapped to an embedding (lookup table). The Language Model (LM)
places a probability distribution $p(\mathbf{x})$ over the output token
sequence. $p(\mathbf{x})$ can be decomposed into a conditional probability
distribution $p(x_{i+1}|x_{i})$, where the probability of each token depends
on all previous tokens. This results in the following joint distribution
$p(\mathbf{x})$ for a sequence of tokens $\mathbf{x}$:

$p(\mathbf{x})=\prod_{i}p(x_{i}|x_{0},x_{1},...,x_{i-1})$ (1)

In regards to Neural Network (NN), $p(\mathbf{x})$ is commonly estimated with
the Softmax function [52] 222The Softmax function applies the exponential
function to each element of the input vector and normalizes the values, by
dividing by the sum of the exponentials.

$p(\mathbf{x})=Softmax(\mathbf{Wh^{T}+b})=\frac{\exp(\mathbf{Wh^{T}+b})}{\sum\exp(\mathbf{Wh^{T}+b})},$
(2)

where $\mathbf{W}$ is the learned weight matrix, $\mathbf{b}$ the bias and
$\mathbf{h^{T}}$ the output vector of the NN. For text generation, the joint
probability distribution $p(\mathbf{x})$ (see Equation 1) can be formulated as
a maximum-likelihood objective, where the objective is to maximize the
likelihood of the next token occurrence for the given data.

Our goal is to fine-tune a LM to get a Robot Language Model (RobLM) that can
generate a complete high-level task plan in one shot, given the domain
information and a task goal. Because LM s are unsupervised learners, a single
training sample contains both given and desired information as NL text. A
restriction to the text format (a string of characters) comes with challenges:
structural information needs to be condensed into a single linear dimension,
and conceptually different aspects of the input need to be annotated in the
text. This text format, including the syntax, has to be designed in such a way
that information can be fed to and extracted from the LM reliably.

In RobLM, the format definition for a NL task description must comply with the
following syntactic rule (spaces added for readability):

        Goal [<SEP> Context] <BOS> Plan <EOS>

        [...] := optional
        <SEP> := separator token
        <BOS> := begin-of-sequence token
        <EOS> := end-of-sequence token

Goal is the task goal in NL. Context is any additional, yet optional
information provided to the LM. The task might have ambiguous solutions, and
the inherent assumption is that the LM will better “understand” the task if
given a context. Examples of a context are the name of the room, the name of
the target object, or a NL description of the environment (see 3.8).

Plan is the sequence of high-level task actions and their respective
arguments, such as objective name or location. Because PLM have been trained
on a diverse corpus of NL, including program code, the format for plans
follows syntactical rules similar to that of a generic programming language:

        Action0(arg0[,arg1]); Action1(arg0[,arg1]); ...

The sequence between the special tokens $<\text{BOS}>$ and $<\text{EOS}>$ can
be extracted to retrieve the plan from the LM-generated output.

###  3.6 Training

RobLM generate a plan as a text given the goal and the context, which involves
causal language modeling for text generation. Decoder-only autoregressive
language models 2 are frequently used for the problem of text generation.
Hence, we chose GPT2 model as the base model for RobLM. RobLM uses the base
version of the GPT-2 PLM (‘gpt-2’) [25], loaded and initialized with pre-
trained weights from the Huggingface [53] Transformer library. Fine-tuning
GPT-2 for causal language generation has a self-supervised setup, where the
labels are the inputs shifted to the right, which entitles learning to predict
the next token in a sequence.

Figure 2: Decoder-only Transformer architecture. The input to the decoder is
tokenized text, and the output is probabilities over the tokens in the
tokenizer vocabulary. The positional encoding is added to the embedded input
to account for the order. Transformer’s decoder can have multiple transformer
blocks, each of which contains multi-head attention with linear layers and
layer normalization. GPT models uses GeLU activation between the last linear
layers.

The GPT-2 PLM is fine-tuned to the pre-processed training data of the ALFRED
dataset, which has around 20.000 samples, with three sets of NL descriptions
for each sample. The ADAM [54] optimizer is used with a learning rate of
$5e^{-5}$ and the LM is trained for two epochs. Fine-tuning a GPT-2 LM to the
ALFRED training data with a single GPU-accelerated computer takes around 30
minutes (27 iterations/s - measurement not representative due to hardware
dependence).

###  3.7 Generation pipeline

Figure 3: Illustration of a forward pass through RobLM for text generation
with a greedy next-token selection strategy. The forward passes are repeated
in a recursive manner until an end-of-text token is encountered or the defined
sequence limit is reached.

For inference, RobLM takes only the NL task goal together with an optional
context and outputs the complete step-by-step plan for completing the goal.
This plan is composed of high-level instructions rather than low-level
controller commands.

Example Given the task “Put the soap into the drawer:”, RobLM (no context)
generates the following plan:

        Put the soap into the drawer:
        0.GotoLocation(countertop)
        1.PickupObject(soap)
        2.GotoLocation(drawer)
        3.PutObject(soap,drawer)

The plan is generated by consecutive forward passes through the Transformer
model. For a vocabulary size of $k$ and a token sequence of length $l$ (with
$l\leq 1024$ for GPT-2), the forward pass of the Transformer yields an output
vector of size $k\times l$ with values in the interval $[0,1]$.

The Transformer outputs scores, called logits, for each token in the input
sequence. These scores are converted to a probability distribution
$p(\mathbf{x})$ by using the Softmax function, as described in Equation 2.

Two possible generation strategies for selecting the next token from
$p(\mathbf{x})$ are: greedy search and top-k / top-p sampling [55]. In the
greedy strategy, the token $x_{sel}$ with the highest likelihood is picked
with $x_{sel}=\arg\max{p(\mathbf{x}})$. In the top-k sampling strategy, as the
name suggests, the scores are sorted, and one of the first k candidate tokens
is randomly sampled. By extending the top-k sampling with an additional top-p
strategy, the sum of the $k$ candidates must be equal to or greater than
$p\in[0,1]$. Simply put, top-k widens the choice over the next tokens and
top-p filters out low-probability tokens.

Figure 3 illustrates, on the basis of an example, a forward pass through the
Transformer with a greedy selection strategy. These steps are repeated
recursively until an end-of-text token is encountered or the defined sequence
limit is reached to generate the full plan.

This LM model was fine-tuned to generate a structured output, omitting special
tokens, characterized by numbered actions and their arguments in parenthesis.
Note that the input is always part of the output, due to the generation
function utilized by RobLM.

Note that it is not guaranteed that the ‘soap’ can be found inside the
‘drawer’ on the ‘countertop’. In fact, it could be in any possible location
permitted by the environment. However, given a greedy search strategy, for the
given task goal the likelihood for the ‘soap’ being on the ‘countertop’ is the
highest in this case.

###  3.8 Transforming Scene Graphs to Natural Language: Graph2NL

PLM s are trained on NL. Because of this, NL is a natural modality for fine-
tuning a PLM. When a context is provided to the LM, this context must be
presented in NL just like the input sequence. If the context should
encapsulate the environment state, this means that the state has to be
transformed into NL before being supplied to the PLM.

Graph2NL is a novel method that “translates” the object-centric scene graph
representation of the environment state to NL. Optionally, domain knowledge
about the environment333Domain knowledge entails every possible room, object,
and receptacle name and their allowed relations, as described in the
respective documentation:
https://ai2thor.allenai.org/ithor/documentation/objects/object-types can be
infused into this graph. The following steps describe the core Graph2NL
process:

  1. 1.

Generate an object-scene graph $G$ with a node for the agent and nodes
corresponding to objects, node attributes being the position and rotation of
the object in Euclidean space and their respective distance and orientation
vectors as edge attributes.

  2. 2.

(Optional) Infuse domain knowledge about the environment by connecting all
dependent nodes and all nodes reachable by the agent.

  3. 3.

Connect the agent (node) to all reachable nodes, if given domain knowledge, or
to all nodes, if not given domain knowledge.

  4. 4.

Given a task and the identified target object, find all paths in the graphs
leading from the agent (node) to the target object (node).

  5. 5.

Use edge attributes in the found paths to describe the task-centric
environment state, by mapping geometric relations to NL tokens.

####  3.8.1 NL mapping

To translate geometric relations attributed by the graph edges into a NL
description, a mapping function is designed. In human speech, distances are
expressed by a vocabulary of words such as “close” or “far” and orientations
are expressed by words such as “in front” or “behind”. Graph2NL adapts this
vocabulary to describe the (numeric) distance and orientation from one node
relative to another in NL.

Table 1: Graph2NL mapping table. Distances are mapped to NL vocabulary (or a
symbol) in a one-to-one relation. Yaw describes the orientation along the
surface normal when viewed from a top-down perspective, and Pitch describes
the z-planar offset (altitude) in relation to the origin.

Distance [m]
---
Value | NL | Symbol
$>5$ | distant | a
$>4$ | far | b
$>3$ | reachable | c
$>2$ | near | d
$>1$ | close | e
$>0.5$ | closer | f
$>0.1$ | next | g
$<0.1$ | in | h

Yaw [°]
---
Value | NL | Symbol
45 to 135 | right | i
135 to 225 | back | j
225 to 315 | left | k
315 to 45 | front | l
Pitch [°]
Value | NL | Symbol
$\geq 0$ | above | m
$<0$ | below | n

Table 1 summarizes the mapping used in Graph2NL. The distance between nodes is
expressed in Cartesian space and orientation in polar coordinates, where Yaw
is the azimuth angle (rotation along the surface normal) and Pitch is the
zenith angle (altitude). With this mapping, the geometric relation between two
nodes can be explained by three words (one for each: distance, pitch, and
yaw).

The vocabulary contains 8 words to express the distance, 4 words to express
the vertical, and 2 words to express the horizontal orientation.
Combinatorially, this gives 64 possible geometric configurations. By treating
each of these configurations as a relation and assigning a special symbol
(token) for each relation, the geometric relationship is expressed in a
condensed form. A simple approach, referring to the Symbol column in Table 1,
is by assigning a symbol to each word. By combining the symbols for distance,
pitch, and yaw, the condensed (three-letter) representation of the geometric
relationship is created.

These symbolic representations can optionally be added to the LM tokenizer as
so-called special tokens. Shorter token sequences, in general, decrease both
the training and inference time.

Example Let the task goal be: “Put the soap into the drawer”. The input query
to Graph2NL would consist of the target object ‘soap’. Figure 4 shows the
graph constructed by Graph2NL from the augmented data (§3.2), including
domain-specific knowledge.

Figure 4: Graph2NL example graph. After locating the root (‘agent’) and target
node (‘soapbar’), the shortest paths connecting those nodes are found and
summarized in NL by mapping all edge attributes along the path.

After finding the shortest paths between the root (‘agent’) and target node
(‘soapbar’), Graph2NL produces an output in the following form (cut-off at
search depth 2):

        [Bathroom=
        - closer below left sink near below back soapbar
        - closer below left cabinet near above back soapbar
        - closer above left countertop next above back soapbar
        - close below back toilet closer below back soapbar
        - closer below back garbagecan close below back soapbar]

The NL context by Graph2NL starts with the name of the room extracted from the
scene graph, followed by the geometric description of each node connected to
the target node on the path from the agent. ‘-’ indicates the root note, which
is the agent.

For this example, Graph2NL would produce the following condensed form:

        [Bathroom=
        - fnk sink dnj soapbar
        - fnj cabinet dmj soapbar
        - fmk countertop gmj soapbar
        - enj toilet fnj soapbar
        - fnj garbagecan enj soapbar]

This form of state representation is unique for each problem configuration and
forms the context that grounds RobLM.

##  4 Experiments

###  4.1 Preliminary analysis for task plan generation with GPT-2 and GPT-3

LLMs s can represent knowledge from the data they have been trained on,
however, the question remains, if this knowledge can be leveraged to solve
planning tasks, i.e., can LM s reason? This is investigated by comparing the
text-generation results of GPT-2 (Zero-Shot Learning (ZSL)) and GPT-3 (Few-
Shot Learning (FSL)) for a planning task.

Let an example planning task be the following:

        Given an instruction to a household robot,
        formulate the steps to complete the instruction.

        The instruction is: ‘‘Put a washed slice of apple on the table.’’

The results for this task vary greatly between the two LM s.

GPT-2 (‘gpt-2’ model, 1.5B parameters) completely fails this task and produces
an output that resembles a repetition of phrases in the input sentence:

        Put a washed slice of apple on the table.
        Put a washed slice of apple on the table.
        Put a washed slice of apple on the table.
        ...

Similar behavior has been observed for other LM falling into the ZSL category.
The input sentence is not an open-ended question and requires a high level of
reasoning capabilities.

GPT-3 (‘text-davinci-002’ model, 175B parameters), when given the same
instruction as input, is able to make assumptions and formulate a whole plan
based on these assumptions:

        Assuming the apple is not cut and not washed.

        1. Pick up the apple from the counter.
        2. Cut the apple into a slice.
        3. Wash the apple slice.
        4. Place the apple slice on the table.

The FSL paradigm allows GPT-3 to be very sensitive to context changes and
seemingly understand the request at hand. However, smaller GPT-3 PLM s (GPT-3
curie, GPT-3 babbage, GPT3-ada) show a degraded quality in the produced plan.
[56] have shown that GPT-3 would not pass the Turing test444a test that makes
an artificial system indistinguishable from a human, as to having “no
understanding of the semantics and contexts of the request, but only a
syntactic (statistical) capacity to associate words […]”.

These tests have shown that plan generation capabilities of LLMs s vary
dramatically depending on the underlying learning paradigm, model
architecture, and parameter size. GPT-2, out of the box, is completely
unsuited for solving planning tasks that require a minimum level of text
understanding. However, as later (§3.5) shown, GPT-2 is able to successfully
generate plans when fine-tuned to a training dataset (§3.2). The question of
whether a fine-tuned GPT-2 model can leverage knowledge for planning is
addressed in the following section. GPT-3, unfortunately, is only accessible
through a paid service by OpenAI as part of the OpenAI Beta program555OpenAI
Beta program: https://beta.openai.com/playground (requires registration).
Fine-tuning of own GPT-3 models is possible through the provided service.
Practical applications, however, are limited because each query has to be sent
to and processed by the OpenAI service. Even if a PLM was made available, the
hardware requirements for running GPT-3 models are immense, even for today’s
standards, due to the sheer parameter count. It is for these reasons that
GPT-3 is not considered as a basis for fine-tuning to RobLM.

###  4.2 Evaluation of RobLM

This section presents the main experiments conducted for evaluation of RobLM.
We first define the appropriate metrics and a baseline method required to make
the evaluations measurable and comparable. The grounding problem is explained
in accordance with the practical aspects of integrating the available methods
into the simulator. For the experimentation part, a set of fine-tuned LLMs s
is compared with the baseline performance.

####  4.2.1 Metrics

To validate a fine-tuned LM, only the NL task goal of each validation sample
and optionally, the context is fed to the RobLM generation pipeline (see
Figure 3). Validation is performed over each task category rather than all the
validation data. This enables the analysis of a task-dependent performance:
some task categories are more complex than others leading to a longer
trajectory of actions and hence an increased difficulty.

Two metrics are defined for validation: LM accuracy and plan success rate.

Definition — Accuracy. Accuracy measures how accurately the LM is able to
predict the following parts of the plan:

  * •

the correct count and names of all actions in the plan (action accuracy)

  * •

the correct count and names of all arguments in the plan (argument accuracy)

  * •

the correct count and names of all actions and arguments in the plan (“full
plan” accuracy)

For a found plan, the accuracy of actions and arguments counts if all actions
or arguments are correct. With this metric, it is possible to anchor the cause
of plan failure to either the actions or the arguments, or both.

Having an accurate LM does not necessarily mean that the generated plan leads
to success — at least, as long the “full plan” accuracy is below $1.0$, i.e.,
the trajectory is not replicated perfectly. A second metric is required that
measures the actual success rate of the fine-tuned LM in simulation. There are
two possible scenarios that justify this additional metric: First, the plan
could fail in simulation, even if it seems accurate. And second, the plan
could succeed in simulation, even if the plan is not completely accurate.

Definition — Success rate. The success rate is a measure of the successful
completion of individual sub-tasks of a validation task. After loading the
trajectory, environment state, and goal from the validation sample into the
AI2-THOR simulator, the actions predicted by the LM are translated into low-
level controller actions via task and geometric grounding (§4.2.4), which are
then passed to the AI2-THOR controller and executed in the simulator. After
every simulator step, a check is performed to determine whether the target
conditions for sub-task completion have been met. If the target conditions are
kept unsatisfied after execution of the last low-level action, it counts as a
success towards the sub-task, or otherwise, as a failure.

####  4.2.2 Baseline

A baseline is an oracle, or upper bound, that serves as a measurement
reference. Fast Downward (FD) [57] is used as the baseline for evaluation. We
consider a classical task planner like FD appropriate since it also has access
to the full domain and is a complete algorithm [57]. Therefore, the ability of
a RobLM to match or outperform FD (for a given time budget) would reveal
whether LM s can be helpful towards learning task planning. Every ALFRED
validation sample comes with a PDDL problem file, while the PDDL domain is
shared by all tasks; this allows the PDDL planner to generate a plan for each
sample.

To generate a plan using FD, the PDDL problem files provided by ALFRED have to
be pre-processed. FD is able to handle Action Description Language (ADL)
instructions, as found in the PDDL problem, but is not able to process
optimization-related additional information present in the files.

####  4.2.3 Hardware setup

For fine-tuning LM s and evaluating each model, we used the Lichtenberg
Cluster of TU Darmstadt, which contains stacks of NVIDIA® A100 and V100 GPUs.
Internal tests have shown that a single GPU can decrease the training time by
a factor of 10 (these tests are not representative because performance depends
on every hardware component). To run experiments in the AI2-THOR simulation,
we used a PC with an NVIDIA® RTX 3080Ti GPU.

####  4.2.4 Instruction grounding

Grounding van be defined as mapping a high-level, abstract, or symbolic
representation to a low-level (ground) representation. Grounding of an
abstract plan to objects is called object or geometric grounding (or “world
grounding”), and grounding of NL to robot tasks is called task grounding. In
this case, instructions generated by the LM are made up of actions that
require a task grounding, and arguments, which require a geometric grounding.

####  4.2.5 Task grounding

Plans generated by RobLM consist of high-level actions and are not directly
executable by the AI2-THOR controller. Each possible action predicted by the
LM has to be grounded to a task, which then translates to a sequence of low-
level controller actions.

For task grounding, three possible types of tasks are defined: navigation,
manipulation and composite. In a navigation task, the agent is required to
move from one to another location. In a manipulation task, the agent performs
an action affecting the environment state. Composite tasks are a composition
of manipulation tasks that need to be completed in a specific order.

Task grounding is performed as follows:

  * •

The action GotoLocation is grounded to the navigation task and delegated to a
trajectory planner for navigation (see below).

  * •

The actions PickupObject, PutObject, ToggleObject and SliceObject are grounded
to the manipulation task, the actions can be directly executed by the low-
level controller.

  * •

The actions HeatObject, CoolObject and CleanObject are grounded to the
composite task, which is translated to this sequence of low-level actions:
ToggleObject $\rightarrow$ PutObject $\rightarrow$ ToggleObject $\rightarrow$
ToggleObject $\rightarrow$ PickupObject $\rightarrow$ ToggleObject (example
given below).

For example, the action HeatObject in a scene containing a microwave would be
grounded to the composite task and translate to a series of low-level actions
that involve opening the microwave (ToggleObject), putting the target object
inside (PutObject), closing the microwave (ToggleObject), waiting (no action),
opening the microwave (ToggleObject), picking up the heated target object
(PickupObject) and finally closing the microwave (ToggleObject).

####  4.2.6 Geometric grounding

An argument can be anything from a location to an object name. An argument
produced by the LM might be ambiguous or non-existing in the environment. In
order to be understood by the controller, these arguments have to be grounded
on a geometric level.

For grounding arguments, first, all available objects are retrieved from the
simulation. Then, the world coordinates of all objects matching the predicted
symbol (target object) are gathered. E.g., if the predicted target object is
‘soap’, the position of all ‘soap’-type objects can be queried and retrieved
from the simulator. The low-level control commands are finally generated with
the help of the ground-truth navigation graph of the scene.

####  4.2.7 Navigation

By overlaying the world with a grid, every position in the world is given a
discrete coordinate. A navigation graph (not to be confused with a scene graph
or Graph2NL graph) creates a node for each coordinate and connects all the
nodes that are accessible one from another.

Similar to the procedure of Graph2NL (§3.8), the navigation graph is traversed
after locating the agent and target node by the object name. A search
algorithm is used to find the shortest path in the graph from the agent to the
target object - in this case, it is the A* algorithm666Refer to [58] as a work
on path planning in mobile robotics using the A* search algorithm. The search
returns a sequence of nodes, which corresponds to a sequence of coordinates (a
trajectory). Lastly, a motion planner takes the trajectory as an input and
outputs a sequence of low-level controller actions (AI2-THOR conveniently
provides a motion planner for navigation).

####  4.2.8 Experimental results

A set of fine-tuned RobLM models are evaluated against the baseline. The fine-
tuned models differ in the amount of context provided during training time:

  1. 1.

‘No context’ — Only task goal

  2. 2.

‘Scene knowledge’ — List of all available objects in the environment, found in
the PDDL problem

  3. 3.

‘Scene graph’ — Description of geometric relations to the target object,
generated by Graph2NL

  4. 4.

‘Full context’ — Description of geometric relations of all objects, generated
by Graph2NL

Given a PDDL problem file, Graph2NL automatically generates the context in the
specified text format. This context is provided to the LM for training and
inference.

##### Results — Accuracy

Figure 5: Prediction accuracy of actions and arguments for previously unseen
data across a set of tasks. Neither RobLM model is able to outperform the
baseline (blue) but shows high accuracy in the prediction of plan actions.
Context-driven models (green, red, and purple) perform better than the model
without any scene-related context (orange).

Figure 5 summarizes the evaluation of the fine-tuned RobLM models compared to
the FD baseline for previously unseen (validation) data. It can be observed
that none of the fine-tuned RobLM models is able to outperform the baseline.
Going through each of the models and starting with the ‘No context’ model it
is surprising that this model, even without any contextual information, is
able to generate the correct plan actions with high accuracy. The ‘Scene
knowledge’ and ‘Scene graph’ models have a similar performance, the ‘Scene
graph’ generally being slightly more accurate in both actions and argument
prediction. Both of these models overall outperform the ‘No context’ model,
with a significant improvement of the context models in the arguments
prediction.

Given these results, the following conclusions about the examined models can
be made:

  1. 1.

Failed plans are mostly caused by wrong arguments (objects or locations) and
only in some cases by wrong actions.

  2. 2.

The LM is able to learn the structure of tasks, but not scene-dependent
components.

RobLM is able to distinguish between the task categories and provide a correct
task action plan. However, where this model fails is in finding all correct
action arguments, i.e., locations and object names. This can be explained by
the fact that the task goal alone does not reveal the actual location of the
target object. Because the target can be in any accessible location in the
environment, or in any accessible receptacle, the produced argument is the
result of the LM imitating the most-likely cases observed in the training
data.

Overall, these results are consistent with the point made on contextual
information and prediction accuracy: giving the model information about the
environment, i.e., fine-tuning a model to be grounded to the scene, does
improve performance.

###  4.3 Results — Success rate

Table 2: Success rates of sub-task completion in simulation — RobLM (‘No context’) compared to the baseline on seen and unseen validation data. Success rate | Baseline | RobLM (‘No context’)
---|---|---
Task | seen | unseen | seen | unseen
GotoLocation | 0.318 | 0.393 | 0.422 | 0.499
PickupObject | 0.466 | 0.474 | 0.776 | 0.749
PutObject | 0.385 | 0.331 | 0.116 | 0.092
SliceObject | 0.629 | 0.5 | 0.94 | 0.98
ToggleObject | 0 | 0 | 0.84 | 0.864

A plan is successful if each of the sub-tasks for a stated task is completed.
Table 2 summarizes the success rate of RobLM compared to the baseline for
actions of the navigation task (GotoLocation) and manipulation task
(PickupObject, PutObject, etc.). Composite tasks have been omitted from this
evaluation because of high failure rates caused by their task grounding
complexity.

Regarding geometric grounding, arguments predicted by RobLM are grounded to
all matching objects in the world, and RobLM is allowed to “try” all
possibilities. E.g., when the objective is to “Get soap”, multiple ‘soap’-type
objects could exist in the scene. Each possibility given by the geometric
grounding is simulated by storing and restoring the simulator state. While
this is a clear advantage for RobLM over the baseline, the evaluation still
holds because the LM is required to predict the correct location or object
names.

Based on the presented results, the LM-based system performs exceptionally
well on sub-tasks requiring the action PickupObject, while the action
PutObject does not succeed equally well, since it does not come close to the
baseline performance.

Overall, the success rate of the baseline method is not nearly as high as
expected, hinting at potential implementation-specific failures in the task
grounding and in the low-level controller interaction with objects. In the
low-level controller, visual information is not included. This means that the
robot is controlled in a “blind flight” mode. The AI2-THOR simulation requires
the target object to be in view. If the object is not visible, e.g., because
the agent is looking in the wrong direction, the interaction fails and with
it, the sub-task. Because of the fact that both systems have been evaluated
within the same framework, these results do not dismiss a potential use-case
for LM in planning.

####  4.3.1 Additional Results

We provide additional experiments for a deeper analysis of potential points of
failure of RobLM. These experiments entail a different sampling strategy and
context refinement.

##### Top-k / top-p sampling

Table 3: Top-k and top-p sampling ($k=10$ and $p=0.9$) — tokens are sampled
three times for the ‘Pick Simple’ task, giving only slight deviations in the
final accuracy. RobLM ‘No context’ model, ‘Pick Simple’ task
---
Accuracy of | 1st sample | 2nd sample | 3rd sample
Actions | 0.7746 | 0.8169 | 0.7817
Arguments | 0.3803 | 0.4085 | 0.3944
GotoLocation | 0.8772 | 0.9123 | 0.8904
PickupObject | 0.8380 | 0.8662 | 0.8451
PutObject | 0.7971 | 0.8227 | 0.7986
GotoLocation_Args | 0.5658 | 0.5877 | 0.5833
PickupObject_Args | 0.7535 | 0.8028 | 0.7746
PutObject_Args | 0.6449 | 0.6667 | 0.6331

So far, every experiment conducted has used a greedy next-token selection
strategy. In order to be able to tell with certainty that a found plan is the
“best possible” plan, a comparison with another sampling strategy is required.
This additional experiment repeats the previous one, but this time with a
top-k and top-p sampling strategy. The comparison is done with the ‘No
context’ RobLM model, for all tasks with $k=10$ and $p=0.9$, i.e., tokens are
sampled from the top-10 predictions and sum up to a probability $\geq 0.9$.

Since a similar pattern was observed in the individual task evaluations, Table
3 reports the results for the ‘Pick Simple’ task only. Each token is sampled
three times, giving three possible solutions to be evaluated. Slight — uniform
and hence dismissable — variations in the prediction accuracy exist between
these three runs. The sampling-based method performs slightly worse than the
greedy strategy.

##### Refined context

Figure 6: Prediction accuracy of actions and arguments for unseen tasks of a
model with a refined context. This experiment compares a model fine-tuned to
the task goal and a context consisting of a NL description of the first plan
instruction (green) with the baseline (blue) and previous RobLM ‘No context’
model (orange).

In a deeper analysis of RobLM failure cases, it has been found that the first
argument in the generated plan is the hardest to predict correctly by the LM.
The LM is not able to draw enough conclusions about the first instruction from
the supplied context of any form.

This causality becomes obvious after the following experiment: Given the task
goal and a NL description of the first instruction as context, how does the
overall accuracy of the LM change? The following text is an example of an
instruction description in NL, as found in the ALFRED dataset:

    Turn left and walk across the room towards the shelves on the wall.

The results in Figure 6 show that, given this extra information, RobLM is
almost able to reach the performance levels of the baseline measurement across
all tasks; it shows very high accuracy on “full plan” actions and arguments.
The conclusion of this experiment is that the more precisely the supplied
context is tailored towards the key issue of LM generation task, the more
accurate the generated plan becomes. For this specific problem, finding the
correct first argument is key to a successful plan, and with a NL description
of the first instruction, the LM is able to draw the necessary connections
from context to plan.

The overall conclusion of this observation is that LM are adaptive. In other
words: LM are able to adapt new information into the plan generation, towards
a more accurate sequence of instructions.

###  4.4 Run-time analysis

Table 4: Comparison of inference speeds — RobLM against baseline. GPU
acceleration used for LM (NVIDIA® GeForce RTX 2080 SUPER). The timer starts
only after the program or model has been loaded into memory, i.e., only
computation (inference) time is measured. ‘No context’ has a maximum token
sequence length of 200 and ‘Full context’ has a maximum length of 1024 tokens
for generation. Iterations per second (average over 800 samples)
---
Baseline | RobLM ‘No context’ | RobLM ‘Full context’
2.9 | 1.0 | 0.2

Time is an important factor when it comes to real-life applications. This is
especially true for industrial robotics, where cycle times are important. But
not every robotic application is time-critical, e.g., a household robot is not
expected to respond in a sub-second time. However, if task planning is seen as
a programming problem, a fast execution time greatly enhances the operator
experience.

Table 4 shows a comparison of the inference speeds of RobLM against the
baseline (FD). RobLM, in all cases, is very slow compared to the baseline,
which is likely due to the reliance on the full GPT-2 vocabulary size for the
LM tokenizer and the usage of a LM-internal, implementation-specific
generation function777Huggingface generation function:
‘transformers/src/transformers/generation_utils.py’.

##  5 Conclusion

We presented a framework for finetuning grounded Large Language Models (LLMs)
and investigated the applicability of such models combined with planning in
solving ling-horizon robot reasoning tasks. This paper has shown that LLMs can
extract commonsense knowledge through precise queries and adjust their
behavior based on available information or context. Among our contributions
are the development of RobLM, a grounded finetuned LLM that generates plans
directly from natural language commands, and Graph2NL, which creates natural
language text describing graph-based data, to represent scene graphs as inputs
into RobLM. Our extensive experimental results have revealed, nevertheless,
the challenges in representing structured and geometric data in natural
language.

However, LLMs still need to demonstrate a consistent ability to perform long-
horizon planning tasks and, therefore, cannot replace classical planning
systems. Despite their limitations, LLMs possess powerful features such as
efficient storage and retrieval of commonsense knowledge, which can be useful
in planning tasks when presented with partially observable environments.

For future work, exploring larger models like GPT-3 or GPT-NeoX could increase
the accuracy and success rate of RobLM. Providing structured context to the
Transformer model and exploring multi-modal inputs, such as visual
information, may also improve the planning capabilities of LLMs. Further
research in the field of applied natural language processing in robotics could
help unlock the full potential of LLMs and contribute to the development of
more advanced neuro-symbolic planning systems.

## Conflict of Interest Statement

The authors declare that the research was conducted in the absence of any
commercial or financial relationships that could be construed as a potential
conflict of interest.

## Funding

This research has been supported by the German Research Foundation (DFG)
through the Emmy Noether Programme (CH 2676/1-1) and by the Hessian.AI
Connectom Fund “Robot Learning of Long-Horizon Manipulation bridging Object-
centric Representations to Knowledge Graphs”.

## Acknowledgments

The authors would like to acknowledge Snehal Jauhri and Haau-Sing Li for the
fruitful discussions and suggestions.

## Data Availability Statement

Code of the presented research is publicly available through the link:
https://github.com/dnandha/RobLM.git

## References

  * [1] Yann LeCun, Yoshua Bengio, and Geoffrey Hinton.  Deep learning.  Nature, 2015.
  * [2] Leslie Pack Kaelbling and Tomás Lozano-Pérez.  Hierarchical task and motion planning in the now.  In 2011 IEEE International Conference on Robotics and Automation, pages 1470–1477. IEEE, 2011.
  * [3] Caelan Reed Garrett, Rohan Chitnis, Rachel Holladay, Beomjoon Kim, Tom Silver, Leslie Pack Kaelbling, and Tomás Lozano-Pérez.  Integrated task and motion planning.  Annual review of control, robotics, and autonomous systems, 2021\.
  * [4] Caelan Reed Garrett, Tomás Lozano-Pérez, and Leslie Pack Kaelbling.  Pddlstream: Integrating symbolic planners and blackbox samplers via optimistic adaptive planning.  In ICAPS, 2020.
  * [5] Marc Toussaint.  Logic-geometric programming: An optimization-based approach to combined task and motion planning.  2015\.
  * [6] Danny Driess and Marc Toussaint.  Hierarchical task and motion planning using logic-geometric programming (hlgp).  2019\.
  * [7] Suraj Nair and Chelsea Finn.  Hierarchical foresight: Self-supervised learning of long-horizon tasks via visual subgoal generation.  arXiv preprint arXiv:1909.05829, 2019.
  * [8] Christopher Hoang, Sungryull Sohn, Jongwook Choi, Wilka Carvalho, and Honglak Lee.  Successor feature landmarks for long-horizon goal-conditioned reinforcement learning.  Advances in Neural Information Processing Systems, 34:26963–26975, 2021.
  * [9] Niklas Funk, Georgia Chalvatzaki, Boris Belousov, and Jan Peters.  Learn2assemble with structured representations and search for robotic architectural construction.  Conference on Robot Learning (CoRL), 2021.
  * [10] Beomjoon Kim, Zi Wang, Leslie Pack Kaelbling, and Tomás Lozano-Pérez.  Learning to guide task and motion planning using score-space representation.  IJRR, 2019.
  * [11] Danny Driess, Jung-Su Ha, and Marc Toussaint.  Deep visual reasoning: Learning to predict action sequences for task and motion planning from an initial scene image.  In RSS, 2020.
  * [12] Tianyu Ren, Georgia Chalvatzaki, and Jan Peters.  Extended task and motion planning of long-horizon robot manipulation.  arXiv:2103.05456, 2021.
  * [13] Niklas Funk, Svenja Menzenbach, Georgia Chalvatzaki, and Jan Peters.  Graph-based reinforcement learning meets mixed integer programs: An application to 3d robot assembly discovery.  IROS + Conf. on Learning Graphs, 2022.
  * [14] Rishi Bommasani, Drew A Hudson, Ehsan Adeli, Russ Altman, Simran Arora, Sydney von Arx, Michael S Bernstein, Jeannette Bohg, Antoine Bosselut, Emma Brunskill, et al.  On the opportunities and risks of foundation models.  arXiv:2108.07258, 2021.
  * [15] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Łukasz Kaiser, and Illia Polosukhin.  Attention is all you need.  NeurIPS, 2017.
  * [16] Alex Wang, Amanpreet Singh, Julian Michael, Felix Hill, Omer Levy, and Samuel R Bowman.  Glue: A multi-task benchmark and analysis platform for natural language understanding.  arXiv preprint arXiv:1804.07461, 2018.
  * [17] Alex Wang, Yada Pruksachatkun, Nikita Nangia, Amanpreet Singh, Julian Michael, Felix Hill, Omer Levy, and Samuel Bowman.  Superglue: A stickier benchmark for general-purpose language understanding systems.  Advances in neural information processing systems, 32, 2019.
  * [18] Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, Fei Xia, Ed H Chi, Quoc V Le, Denny Zhou, et al.  Chain-of-thought prompting elicits reasoning in large language models.  In NeurIPS, 2022.
  * [19] Anthony Brohan, Yevgen Chebotar, Chelsea Finn, Karol Hausman, Alexander Herzog, Daniel Ho, Julian Ibarz, Alex Irpan, Eric Jang, Ryan Julian, et al.  Do as i can, not as i say: Grounding language in robotic affordances.  In CoRL, 2022.
  * [20] Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al.  Language models are few-shot learners.  NeurIPS, 2020.
  * [21] Jules White, Quchen Fu, Sam Hays, Michael Sandborn, Carlos Olea, Henry Gilbert, Ashraf Elnashar, Jesse Spencer-Smith, and Douglas C Schmidt.  A prompt pattern catalog to enhance prompt engineering with chatgpt.  arXiv:2302.11382, 2023.
  * [22] Long Ouyang, Jeff Wu, Xu Jiang, Diogo Almeida, Carroll L Wainwright, Pamela Mishkin, Chong Zhang, Sandhini Agarwal, Katarina Slama, Alex Ray, et al.  Training language models to follow instructions with human feedback.  arXiv:2203.02155, 2022.
  * [23] Andy Zeng, Adrian Wong, Stefan Welker, Krzysztof Choromanski, Federico Tombari, Aveek Purohit, Michael Ryoo, Vikas Sindhwani, Johnny Lee, Vincent Vanhoucke, et al.  Socratic models: Composing zero-shot multimodal reasoning with language.  arXiv:2204.00598, 2022.
  * [24] Ishika Singh, Valts Blukis, Arsalan Mousavian, Ankit Goyal, Danfei Xu, Jonathan Tremblay, Dieter Fox, Jesse Thomason, and Animesh Garg.  Progprompt: Generating situated robot task plans using large language models.  arXiv:2209.11302, 2022.
  * [25] Alec Radford, Jong Wook Kim, Chris Hallacy, and Aditya Ramesh et al.  Learning transferable visual models from natural language supervision.  In ICML, 2021.
  * [26] Mohit Shridhar, Jesse Thomason, Daniel Gordon, Yonatan Bisk, Winson Han, Roozbeh Mottaghi, Luke Zettlemoyer, and Dieter Fox.  Alfred: A benchmark for interpreting grounded instructions for everyday tasks.  In CVPR, 2020.
  * [27] Xiang Lorraine Li, Adhiguna Kuncoro, Cyprien de Masson d’Autume, Phil Blunsom, and Aida Nematzadeh.  Do language models learn commonsense knowledge?  arXiv preprint arXiv:2111.00607, 2021.
  * [28] Xuhui Zhou, Yue Zhang, Leyang Cui, and Dandan Huang.  Evaluating commonsense in pre-trained language models.  In Proceedings of the AAAI conference on artificial intelligence, volume 34, pages 9733–9740, 2020.
  * [29] Ning Bian, Xianpei Han, Le Sun, Hongyu Lin, Yaojie Lu, and Ben He.  Chatgpt is a knowledgeable but inexperienced solver: An investigation of commonsense problem in large language models.  arXiv preprint arXiv:2303.16421, 2023.
  * [30] Jason Wei, Yi Tay, Rishi Bommasani, Colin Raffel, Barret Zoph, Sebastian Borgeaud, Dani Yogatama, Maarten Bosma, Denny Zhou, Donald Metzler, et al.  Emergent abilities of large language models.  TMLR, 2022.
  * [31] Laura Ruis, Akbir Khan, Stella Biderman, Sara Hooker, Tim Rocktäschel, and Edward Grefenstette.  Large language models are not zero-shot communicators.  arXiv preprint arXiv:2210.14986, 2022.
  * [32] Karthik Valmeekam, Alberto Olmo, Sarath Sreedharan, and Subbarao Kambhampati.  Large language models still can’t plan (a benchmark for llms on planning and reasoning about change).  arXiv:2206.10498, 2022.
  * [33] Yi Tay, Jason Wei, Hyung Won Chung, Vinh Q Tran, David R So, Siamak Shakeri, Xavier Garcia, Huaixiu Steven Zheng, Jinfeng Rao, Aakanksha Chowdhery, et al.  Transcending scaling laws with 0.1% extra compute.  arXiv:2210.11399, 2022.
  * [34] Neil Houlsby, Andrei Giurgiu, Stanislaw Jastrzebski, Bruna Morrone, Quentin De Laroussilhe, Andrea Gesmundo, Mona Attariyan, and Sylvain Gelly.  Parameter-efficient transfer learning for nlp.  In ICML, 2019.
  * [35] Jonas Pfeiffer, Aishwarya Kamath, Andreas Rücklé, Kyunghyun Cho, and Iryna Gurevych.  Adapterfusion: Non-destructive task composition for transfer learning.  In ACL, 2021.
  * [36] Andrew M Wells, Neil T Dantam, Anshumali Shrivastava, and Lydia E Kavraki.  Learning feasibility for task and motion planning in tabletop environments.  IEEE RAL, 2019.
  * [37] Lei Xu, Tianyu Ren, Georgia Chalvatzaki, and Jan Peters.  Accelerating integrated task and motion planning with neural feasibility checking.  arXiv preprint arXiv:2203.10568, 2022.
  * [38] Alexander Pashevich, Cordelia Schmid, and Chen Sun.  Episodic transformer for vision-and-language navigation.  In Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 15942–15952, 2021.
  * [39] William Chen, Siyi Hu, Rajat Talak, and Luca Carlone.  Leveraging large language models for robot 3d scene understanding.  arXiv:2209.05629, 2022.
  * [40] Oier Mees, Jessica Borja-Diaz, and Wolfram Burgard.  Grounding language with visual affordances over unstructured data.  arXiv:2210.01911, 2022.
  * [41] Chenguang Huang, Oier Mees, Andy Zeng, and Wolfram Burgard.  Visual language maps for robot navigation.  arXiv:2210.05714, 2022.
  * [42] Dhruv Shah, Błażej Osiński, Sergey Levine, et al.  Lm-nav: Robotic navigation with large pre-trained models of language, vision, and action.  In CoRL, 2022.
  * [43] Wenlong Huang, Pieter Abbeel, Deepak Pathak, and Igor Mordatch.  Language models as zero-shot planners: Extracting actionable knowledge for embodied agents.  In ICML, 2022.
  * [44] Shreyas Sundara Raman, Vanya Cohen, Eric Rosen, Ifrah Idrees, David Paulius, and Stefanie Tellex.  Planning with large language models via corrective re-prompting.  arXiv:2211.09935, 2022.
  * [45] Yunfan Jiang, Agrim Gupta, Zichen Zhang, Guanzhi Wang, Yongqiang Dou, Yanjun Chen, Li Fei-Fei, Anima Anandkumar, Yuke Zhu, and Linxi Fan.  Vima: General robot manipulation with multimodal prompts.  In NeurIPS Foundation Models for Decision Making Workshop, 2022\.
  * [46] Wenlong Huang, Fei Xia, Ted Xiao, Harris Chan, Jacky Liang, Pete Florence, Andy Zeng, Jonathan Tompson, Igor Mordatch, Yevgen Chebotar, et al.  Inner monologue: Embodied reasoning through planning with language models.  In CoRL, 2022.
  * [47] Boyuan Chen, Fei Xia, Brian Ichter, Kanishka Rao, Keerthana Gopalakrishnan, Michael S Ryoo, Austin Stone, and Daniel Kappler.  Open-vocabulary queryable scene representations for real world planning.  arXiv:2209.09874, 2022.
  * [48] Jacky Liang, Wenlong Huang, Fei Xia, Peng Xu, Karol Hausman, Brian Ichter, Pete Florence, and Andy Zeng.  Code as policies: Language model programs for embodied control.  arXiv:2209.07753, 2022.
  * [49] Shuang Li, Xavier Puig, Chris Paxton, Yilun Du, Clinton Wang, Linxi Fan, Tao Chen, De-An Huang, Ekin Akyürek, Anima Anandkumar, et al.  Pre-trained language models for interactive decision-making.  Advances in Neural Information Processing Systems, 35:31199–31212, 2022.
  * [50] Constructions Aeronautiques, Adele Howe, Craig Knoblock, ISI Drew McDermott, Ashwin Ram, Manuela Veloso, Daniel Weld, David Wilkins SRI, Anthony Barrett, Dave Christianson, et al.  Pddl| the planning domain definition language.  Technical Report, Tech. Rep., 1998.
  * [51] Eric Kolve, Roozbeh Mottaghi, Winson Han, Eli VanderBilt, Luca Weihs, Alvaro Herrasti, Daniel Gordon, Yuke Zhu, Abhinav Gupta, and Ali Farhadi.  Ai2-thor: An interactive 3d environment for visual ai.  arXiv:1712.05474, 2017.
  * [52] Yoshua Bengio, Réjean Ducharme, and Pascal Vincent.  A neural probabilistic language model.  Advances in neural information processing systems, 13, 2000.
  * [53] Thomas Wolf, Lysandre Debut, Victor Sanh, Julien Chaumond, Clement Delangue, Anthony Moi, Pierric Cistac, Tim Rault, Rémi Louf, Morgan Funtowicz, et al.  Huggingface’s transformers: State-of-the-art natural language processing.  arXiv preprint arXiv:1910.03771, 2019.
  * [54] Diederik P Kingma and Jimmy Ba.  Adam: A method for stochastic optimization.  arXiv preprint arXiv:1412.6980, 2014.
  * [55] Ari Holtzman, Jan Buys, Li Du, Maxwell Forbes, and Yejin Choi.  The curious case of neural text degeneration.  In International Conference on Learning Representations, 2020.
  * [56] Luciano Floridi and Massimo Chiriatti.  Gpt-3: Its nature, scope, limits, and consequences.  Minds and Machines, 30(4):681–694, 2020.
  * [57] Malte Helmert.  The fast downward planning system.  Journal of Artificial Intelligence Research, 26:191–246, 2006.
  * [58] František Duchoň, Andrej Babinec, Martin Kajan, Peter Beňo, Martin Florek, Tomáš Fico, and Ladislav Jurišica.  Path planning with modified a star algorithm for a mobile robot.  Procedia Engineering, 96:59–69, 2014.