#  Nowcasting economic activity in European regions using a mixed-frequency
dynamic factor model

Luca Barbagliaa, Lorenzo Frattarolob, Niko Hauzenbergerc, Dominik Hirschbühla,
Florian Huberd, Luca Onorantea, Michael Pfarrhofere, Luca Tiozzo Pezzolia

aEuropean Commission, Joint Research Centre
bUniversità degli studi di Verona
cUniversity of Strathclyde
dUniversity of Salzburg
eVienna University of Economics and Business

Abstract: Timely information about the state of regional economies can be
essential for planning, implementing and evaluating locally targeted economic
policies. However, European regional accounts for output are published at an
annual frequency and with a two-year delay. To obtain robust and more timely
measures in a computationally efficient manner, we propose a mixed-frequency
dynamic factor model that accounts for national information to produce high-
frequency estimates of the regional gross value added (GVA). We show that our
model produces reliable nowcasts of GVA in 162 regions across 12 European
countries.

JEL: C22, C53, R11
Keywords: factor models, mixed-frequency, nowcasting, regional data

We thank Gary Koop, Stuart McIntyre, James Mitchell, Ping Wu, and participants
of the brown bag seminar in the Department of Economics at the University of
Strathclyde, as well as the participants to the JRC-DG ECFIN seminar, for
insightful comments and discussions. The views expressed are purely those of
the authors and should not, in any circumstances, be regarded as stating an
official position of the European Commission.
E-mail<EMAIL_ADDRESS>(corresponding author);
<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>luca.tiozzo-
<EMAIL_ADDRESS>
##  1 Introduction

The timely availability of information on the state of regional economies is
essential for the implementation and evaluation of targeted economic policies.
These are often designed to address specific economic challenges or
opportunities in a particular region, and their effectiveness can only be
accurately assessed if policymakers have access to timely, detailed data on
the economic conditions prevailing in that region. However, EU-specific data
collected by Eurostat on regional output and income comes with two
limitations: (1) the frequency of publication is annual, and (2) new data is
released with a significant delay of two years (Commission and Eurostat,
2023). These two shortcomings, combined with cross-country and cross-regional
heterogeneity in terms of economic fundamentals, severely complicate
monitoring and fine-tuning the impact of policy changes.

Our model aims to address the issue of limited and delayed regional economic
data by leveraging more frequently available national data. We propose a mixed
frequency dynamic factor model (MF-DFM) that uses national information, which
is available on a quarterly basis, to obtain quarterly estimates of regional
gross value added (GVA), which is only available at annual frequency and with
a substantial time lag. The need to combine low and high frequency information
in multivariate time series models has precedent in the literature (see, e.g.,
Mariano and Murasawa, 2003, 2010; Schorfheide and Song, 2015, 2020; Huber et
al., 2023). These models are often used to obtain a monthly (or higher)
frequency estimate of national GDP, using information from higher frequency
time series such as industrial production, unemployment rates or financial
data. This usually involves small to medium size specifications, since
standard estimation algorithms use computationally intensive filtering and
smoothing steps that do not scale well to high dimensions.

Our goal is to obtain estimates of regional GVA at a quarterly frequency. We
concentrate on NUTS2-level regions, implying that the dimension of the cross-
section becomes sizeable. This calls for a model that is capable of handling a
large number of time series simultaneously. The potentially large size of the
cross section is one problem, the annual frequency of our target variables is
another. In our empirical work, we model quarterly movements in annual
regional data dating back to only 2001 – considering the required lag-
structures, data availability results in $20$ observations over time for each
region (in the full sample), and even shorter series when we conduct out-of-
sample forecast experiments.

In a recent paper, Koop et al. (2020) use a model for regional GVA in the
United Kingdom (UK). This model includes a moderate number of time series (the
$12$ NUTS1 regions in the UK and a few additional national quantities with
annual data dating back to the 1970s) and applies Markov Chain Monte Carlo
(MCMC) estimation techniques to carry out estimation and inference. In
addition, they introduce cross-sectional restrictions such that the sum of the
regional GVA series (at the quarterly level) is equivalent to the national
aggregate. Related work and refinements are provided in Koop et al. (2019,
2022, 2023). Since our focus is on NUTS2 data for EU member states, the number
of endogenous variables sharply increases which renders standard MCMC-based
estimation tools impractical.111Other work at a comparable level of regional
granularity often zooms into specific countries or even subsets of regions
within countries, e.g., as Henzel et al. (2015); Lehmann and Wohlrabe (2015);
Claudio et al. (2020); Lehmann and Wikman (2023) for Germany; Billé et al.
(2023) use panel data methods for even smaller-scale considerations of Italy.
A notable exception with respect to our comments about MCMC methods being
infeasible is Chan et al. (2023), who discuss computationally efficient
algorithms for estimating high-dimensional state space models. A possible
solution to this scalability issue is also provided in Gefang et al. (2020).
This paper uses variational Bayes (VB) approximation techniques to estimate
mixed frequency VARs. The resulting model, however, may be hard to tune and
the size of the approximation errors induced by VB-based estimation is
difficult to assess.

In this paper, we propose a dynamic factor model that combines the virtues of
the MF-DFM proposed in Mariano and Murasawa (2010) with the cross-sectional
and inter-temporal restrictions of Koop et al. (2020). We assume that the
latent high frequency quantities of regional GVA co-move and feature a factor
structure. This choice is motivated by the fact that regions close to each
other (in geographical or economic terms, e.g., within a particular country)
are often exposed to common economic shocks and these trigger substantial co-
movements across regional output dynamics. A factor model is capable of
handling such a behaviour in a very parsimonious manner. Since the model might
be prone to overfitting if the number of factors and/or lags is large,
particularly with our short time series, we use Bayesian shrinkage priors on
the VAR coefficients determining the law of motion of the high frequency
measures as well as the factor loadings. The resulting model can be applied to
large cross-sections since it effectively deals with computational and
statistical issues by reducing the state space through factor restrictions and
the introduction of highly flexible shrinkage priors.

Our resulting regional MF-DFM is then applied country-by-country to model the
corresponding NUTS2 regions within a particular country. We first provide
predictive evidence that our model improves upon a simple random walk (RW)
benchmark, often at sizeable margins. While we find the model to improve
forecasts across all considered countries, there is some heterogeneity in
predictive performance. Based on this forecast exercise, we discuss several
modelling aspects that are relevant for practitioners. Finally, we investigate
high-frequency dynamics of the resulting quarterly regional time series, and
provide a brief (regional) case study about the onset of the COVID-19
pandemic.

The remainder of the paper is structured as follows. Section 2 discusses the
econometric framework and implementation. Section 3 introduces the dataset and
contains our forecast exercise alongside additional empirical results. The
final section concludes.

##  2 Econometric framework

###  2.1 The mixed-frequency dynamic factor model

For modelling economic activity across disaggregate regions, we propose a
mixed-frequency dynamic factor model (MF-DFM). Our model exploits the fact
that regions within a country tend to co-move due to their exposure to common
shocks.

Let $\boldsymbol{y}_{t}^{\ast}=(y_{1t}^{\ast},\ldots,y_{Nt}^{\ast})^{\prime}$
denote a vector of observed real GVA measures for regions $i=1,\ldots,N$,
where $t=1,\ldots,T$, runs on a quarterly frequency. This implies that
$\boldsymbol{y}_{t}^{\ast}$ features missing values, since regional GVA is
only observed annually and with a lag. We model these quantities as year-on-
year differences. Define $\tilde{\boldsymbol{f}}_{t}$ as a $Q_{f}$-vector of
latent factors, and $\boldsymbol{z}_{t}$ are $Q_{z}$-observed factors. We
collect these in the $Q_{f}+Q_{z}=Q\times 1$ vector
$\boldsymbol{f}_{t}=(\tilde{\boldsymbol{f}}_{t}^{\prime},\boldsymbol{z}_{t}^{\prime})^{\prime}$.
That is, $Q\ll N$, and the framework we propose thus only relies on modelling
$Q_{f}$ latent processes that govern within-year dynamics across regions,
rather than $N$ separate processes for each individual region. While national
GVA must always be included, $\boldsymbol{z}_{t}$ may include further
information such as interest rates, unemployment, or other quantities that
affect economic activity across regions.222This feature offers additional
inferential possibilities such as identifying structural shocks nationally,
and trace their propagation on a regional level. We leave such aspects for
future research. The variables $\tilde{\boldsymbol{f}}_{t}$ are never
observed, while $z_{\text{GVA},t}$ are quarter-on-quarter log-differences of
GVA on the national level which are observed each quarter.

We link the observed regional GVA measures to the latent and observed factors
by constructing an inter-temporal restriction. For quarters when we observe
annual regional GVA, we assume:

$\displaystyle y_{it}^{\ast}=$
$\displaystyle\left(\sum_{q=1}^{Q_{f}}\lambda_{iq}\left(\frac{1}{4}\tilde{f}_{qt}+\frac{2}{4}\tilde{f}_{qt-1}+\frac{3}{4}\tilde{f}_{qt-2}+\tilde{f}_{qt-3}+\frac{3}{4}\tilde{f}_{qt-4}+\frac{2}{4}\tilde{f}_{qt-5}+\frac{1}{4}\tilde{f}_{qt-6}\right)\right)+$
$\displaystyle\sum_{\tilde{q}={Q_{f}+1}}^{Q}\lambda_{i\tilde{q}}z_{\tilde{q}t}+\epsilon_{it},\quad\epsilon_{it}\sim\mathcal{N}\left(0,\sigma_{\text{ME},i}^{2}\right),$
(1)

while in the quarters without regional observations, we have
$y_{it}^{\ast}=\varnothing$. This equation serves two main purposes. First, it
distributes the latent growth rates of the quarter throughout the year via the
triangular weighting scheme which arises from considering log-growth rates, as
proposed in Mariano and Murasawa (2003). Second, the unobserved and observed
latent factors are then linked to observed regional growth by the factor
loadings $\lambda_{iq}$ which we store in an $N\times Q$ matrix
$\boldsymbol{\Lambda}$. In related papers, the inter-temporal restriction is
typically specified to hold exactly; due to our factor structure, by contrast,
we introduce region-specific Gaussian measurement errors centred on zero with
variance $\sigma_{\text{ME},i}^{2}$.

A key feature of our setup is that regional growth rates can be linked to
those observed quarterly on the national level (see also Koop et al., 2020).
We may impose this restriction with the following measurement equation which
we label the cross-sectional restriction:

$z_{\text{GVA},t}=\sum_{q=1}^{Q_{f}}\left(\sum_{i=1}^{N}\omega_{i}\lambda_{iq}\tilde{f}_{qt}\right)+\varepsilon_{t},\quad\varepsilon_{t}\sim\mathcal{N}\left(0,\sigma_{\text{CS}}^{2}\right),$

where $\omega_{i}$ are pre-determined weights that reflect the share of the
respective region in national GVA. The final aspect of our framework refers to
how we model the dynamics of the observed and latent states. We achieve this
by using a vector autoregressive (VAR) state equation which requires $P\geq 7$
lags:

$\displaystyle\boldsymbol{f}_{t}$
$\displaystyle=\boldsymbol{A}_{1}\boldsymbol{f}_{t-1}+\ldots+\boldsymbol{A}_{P}\boldsymbol{f}_{t-P}+\boldsymbol{\epsilon}_{t},\quad\boldsymbol{\epsilon}_{t}\sim\mathcal{N}(\boldsymbol{0},\boldsymbol{\Sigma}).$
(2)

Here, $\boldsymbol{A}_{p}$ are $Q\times Q$-matrices of VAR coefficients
associated with the respective $p$th lag, and $\boldsymbol{\epsilon}_{t}$ is a
Gaussian error term with zero mean and $Q\times Q$-covariance matrix
$\boldsymbol{\Sigma}$. Our measurement equations, in conjunction with this
state equation, provide us with a fairly straightforward Gaussian state-space
model.

###  2.2 Prior setup and algorithm

Our model is simpler than larger VAR models that explicitly feature equations
for each region due to the proposed factor structure. However, the size of the
cross-section and the required number of factors still yields a large number
of parameters to be estimated. The latter also implies that Equation (2) may
result in a comparatively large VAR. We thus regularise the parameter space
via shrinkage priors, and enable equation-by-equation estimation of
multivariate systems of equations.

We achieve this by estimating Equation (2) in its structural form via
decomposing
$\boldsymbol{\Sigma}=\boldsymbol{B}_{0}^{-1}\boldsymbol{H}\boldsymbol{B}_{0}^{-1}{{}^{\prime}}$,
such that
$\boldsymbol{B}_{0}^{-1}\boldsymbol{\eta}_{t}=\boldsymbol{\epsilon}_{t}$ and
$\boldsymbol{\eta}_{t}\sim\mathcal{N}(\boldsymbol{0},\boldsymbol{H})$. Here,
$\boldsymbol{B}_{0}$ is lower triangular matrix with unit-diagonal,
$\boldsymbol{H}=\text{diag}(h_{1},\ldots,h_{Q})$ is a diagonal matrix
collecting the variances of the structural shocks.333Triangularizing the VAR
this way also provides the opportunity of adding stochastic volatility (SV)
with ease by introducing state equations for the elements on the diagonal of
$\boldsymbol{H}$. Indeed, we have experimented with SV but found that it was
unnecessary for the data used in our application. We thus may write:

$\boldsymbol{B}_{0}\boldsymbol{f}_{t}=\boldsymbol{B}_{1}\boldsymbol{f}_{t-1}+\ldots+\boldsymbol{B}_{P}\boldsymbol{f}_{t-P}+\boldsymbol{\eta}_{t},\quad\boldsymbol{\eta}_{t}\sim\mathcal{N}(\boldsymbol{0},\boldsymbol{H}),$

where the reduced form coefficients can be recovered from computing
$\boldsymbol{A}_{p}=\boldsymbol{B}_{0}^{-1}\boldsymbol{B}_{p}$ for
$p=1,\ldots,P$. This approach of estimating the VAR is very close to Koop et
al. (2020), as is our prior setup which exploits the favourable shrinkage
properties of a global-local prior. Specifically, we rely on regularising the
$\boldsymbol{B}_{p}$’s, the free elements of $\boldsymbol{B}_{0}$ and
$\boldsymbol{\Lambda}$ via Horseshoe (HS, see Carvalho et al., 2010) priors.
Stationarity of the factors is imposed via a rejection sampling step. Standard
filtering and smoothing may subsequently be carried out using the reduced form
coefficients of the VAR.

The remaining priors relate to innovations in the state and measurement
equations. Here, we use inverse Gamma priors on all of them. In the state
equation, we have a moderately informative prior,
$h_{q}\sim\mathcal{G}^{-1}(3,0.3)$ for $q=1,\ldots,Q$. On the measurement
errors we impose more prior information. Since our intertemporal restriction
is combined with a factor model, it is not exactly binding as in related
papers. By assuming $\sigma_{\text{ME},i}^{2}\sim\mathcal{G}^{-1}(100,0.01)$
for $i=1,\ldots,N$, we express the belief that the restriction almost holds,
although the prior allows for deviations in case it is required due to
regional heterogeneity in light of the factors. Similarly, we use
$\sigma_{\text{CS}}^{2}\sim\mathcal{G}^{-1}(5,0.05)$ on the cross-sectional
restriction. This somewhat looser prior is due to measurement errors or
potential revisions of the annual data.

##  3 Nowcasting GVA in European Regions

###  3.1 Data overview, nowcasting design and model specification

We study a multi-country data set, consisting of Austria (AT), Belgium (BE),
Germany (DE), Greece (EL), Spain (ES), Finland (FI), France (FR), Ireland
(IE), Italy (IT), Netherlands (NL), Portugal (PT) and Slovakia (SK). Following
Koop et al. (2020) our target variable is GVA and we obtain regional and
national GVA figures from Eurostat regional economic accounts at
ec.europa.eu/eurostat. We select euro area countries that have more than two
NUTS2 regions and exclude all extra-regions entities indexed by the “ZZ”
suffix. Our final data set contains 162 NUTS2 regions in 12 European
countries. Recall that GVA figures at the NUTS2 level are available on a
yearly basis while they are quarterly at the country level. The annual
regional figures start in 2001 and are released between February 15 and March
31 of each year, with a two-year publication delay.444For instance, the latest
annual regional figures included in our exercise relate to 2021 and were
published on February 20 2023. For more details, see ec.europa.eu/eurostat.

In our empirical work, we have three goals. First, we show that our proposed
model produces nowcasts of yearly GVA figures that are accurate relative to a
benchmark (discussed below). Second, we zoom into cross-regional and cross-
country differences in nowcast performance and tease out key predictive
properties of our model. Third, we discuss the qualitative features of the
quarterly regional nowcasts for selected time periods (2019Q4 to 2020Q2) and
across regions and countries.

To produce and evaluate our pseudo real-time nowcasts, we rely on the
following design. Our first target in the hold-out sample is regional GVA in
2016. To reflect the publication schedule, we run the model using yearly data
from 2001 to 2014 and quarterly data through 2016Q4. This information set is
used to produce a prediction for 2016 (and a backcast for 2015 as a by-
product, which we omit in our empirical discussions since our focus is on
nowcasting). After obtaining the corresponding predictive densities, we add
one more year of data and produce quarterly estimates of regional GVA to
generate a nowcast of yearly GVA. This is done until we reach the end of our
sample (annual GVA in 2021). We thus, crucially for such an exercise, respect
the release calendar, but note that we do not explicitly take care of
potential data revisions.

For each country in our data set, we start by estimating the MF-DFM
independently and select the optimal number of factors $Q$ based on their
density nowcasting performance. We use a grid of values for factors ranging
from $1$ to the minimum between the number of regions in a country and an
experimental threshold $Q_{max}$ that we set to $10$. In other words, for
countries with fewer than $10$ NUTS2 regions we test the fully-specified
model, while for the other countries we take 10 as the maximum number of
factors. Note that the overspecified factor model closely resembles the MF-VAR
model by Koop et al. (2020).

In principle, modelling all countries (and associated regions) within a single
model would be possible. However, we opt for not doing so for three reasons.
First, while still being tractable, computation becomes much more cumbersome.
This is because the space of observed series becomes much larger dimensional,
and filtering algorithms turn out to be slow. Moreover, since we might have to
include a more significant number of factors, the dimension of the state
equation might also increase a lot. Second, model calibration becomes an issue
since we introduce both cross-sectional and intertemporal restrictions. Third,
we wanted to exploit cross-country heterogeneity in the number of regions to
investigate its consequences in the choice of the number of endogenous
factors, something not possible in estimating a single European model.

We asses the nowcasting performance through the continuous ranked probability
score (CRPS, Gneiting and Raftery, 2007), weighted by the historical regional
GVA shares. This provides an overall measure of regional density nowcasting
performance where regions are weighted by their relative economic
significance. The nowcasting results are then benchmarked against a simple
random walk (RW) model specified terms of the growth rate of GVA.555As a
robustness check, we also implement a standard AR($1$) model, whose nowcasting
performance is comparable to the RW. The proposed MF-DFM model attains, on
average, a 30% nowcast gain with respect to both benchmarks. To simplify the
exposition of the results, the main paper considers only the RW benchmark. The
results for the AR model are available upon request. We note that our hold-out
consists of six observations, and we thus refrain from formally testing for
statistical significance of differences between competing approaches.

###  3.2 Nowcasting results

We start by discussing the findings of our nowcasting exercise averaged over
time. These are provided in Table 1 which reports the average CRPS by country
(in columns) and number of factors $Q$ (in rows). The figures are relative to
the CRPS of the RW: values below 1 indicate a better performance of the
proposed MF-DFM. Missing values in the table indicates the countries that have
fewer than 10 NUTS2 regions: for these countries, the upper threshold for $Q$
is set equal to the number of regions.

$Q$ | IE | SK | FI | PT | AT | BE | NL | EL | ES | IT | FR | DE
---|---|---|---|---|---|---|---|---|---|---|---|---
1 | 0.77 | 0.77 | 1.26 | 1.27 | 1.18 | 1.03 | 1.27 | 0.55 | 1.42 | 1.00 | 1.11 | 1.15
2 | 0.74 | 0.57 | 1.12 | 1.11 | 1.02 | 0.86 | 1.04 | 0.44 | 1.28 | 0.89 | 1.00 | 0.96
3 | 0.79 | 0.60 | 1.02 | 0.99 | 0.90 | 0.80 | 1.04 | 0.41 | 1.11 | 0.83 | 0.92 | 0.82
4 |  | 0.62 | 0.90 | 0.99 | 0.87 | 0.75 | 0.91 | 0.41 | 1.06 | 0.78 | 0.85 | 0.76
5 |  |  | 0.88 | 0.92 | 0.85 | 0.76 | 0.89 | 0.41 | 1.00 | 0.73 | 0.80 | 0.75
6 |  |  |  | 0.90 | 0.85 | 0.83 | 0.89 | 0.40 | 0.98 | 0.75 | 0.76 | 0.76
7 |  |  |  | 0.94 | 0.87 | 0.85 | 0.88 | 0.42 | 0.95 | 0.76 | 0.77 | 0.74
8 |  |  |  |  | 0.89 | 0.97 | 0.91 | 0.42 | 0.97 | 0.79 | 0.86 | 0.78
9 |  |  |  |  | 0.93 | 0.94 | 0.89 | 0.43 | 0.97 | 0.81 | 0.87 | 0.79
10 |  |  |  |  |  | 1.07 | 0.94 | 0.48 | 1.02 | 0.86 | 0.86 | 0.83
Table 1:  Average CRPS across out-of-sample years (2016-2021) by country and
choice of the number of factors $Q$ for the MF-DFM. The CRPS is weighted by
the historical GVA share by country. The CRPS is reported relative to the one
of the RW: values below 1 indicate a better performance than the benchmark.
Missing values in the table indicates the countries that have fewer than 10
NUTS2 regions (i.e., the experimental upper threshold for the grid search over
the number of factors).

At a general level, we observe that our model produces nowcasts that are
considerably more accurate than the ones of the benchmark for most countries
under consideration. These gains vary across countries and number of factors.
For some countries and values of $Q$, improvements are substantial. For
instance, in the case of Greece we observe gains of approximately 60%. In
Slovakia, our model produces smaller but still substantially accuracy premia
of around 40%. For other countries (Austria, Belgium, France), we observe
gains between 15 and 20%. However, there are also some few cases where our
model does not improve upon the benchmark. For instance, in Spain we find a
weaker performance, with average gains below 5% (and in fact losses for low
choices of $Q$).

When we relate the nowcasting performance within a particular country to the
number of factors, we find a consistent pattern. In case the number of factors
is very low, the predictive performance of the models is poor and (with three
exceptions) inferior to the one of the random walk benchmark, pointing towards
underfitting. Two of these three exceptions (Ireland and Slovakia) are small
countries with only a few NUTS2 regions. In this case, a single factor is
sufficient to summarise the cross-sectional variation in GVA. As a general
pattern, we find that the relationship between the number of factors and
nowcast performance is U-shaped; the predictive performance first increases,
and, if $Q$ is set too large, declines again. This points towards overfitting
if the number of factors is set too large, providing some evidence that our
factor model (if it is well specified) is capable of efficiently summarising
the bulk of cross-regional variation. It is worth noting that the penalty in
terms of predictive losses is much larger for underfitting specifications when
contrasted with overfitting ones.

Our discussion also suggests that there exists a relationship between country
size and the optimal number of factors. This relationship is depicted in
Figure 1 which is a scatter plot between country size (as measured by the
number of NUTS2 regions) and the optimal value of $Q$. The relationship
between country size and $Q$ appears to be nonlinear and a logarithmic fit
approximates this relation well. This result has important practical
implications. First, few factors seems to be sufficient to summarise the
information even when the nowcasting regional economic activity in large
countries. Second, practitioners and forecasters can exploit the relationship
between the number of regions and factors as a rule-of-thumb when setting up
their nowcasting model. A particularly simple rule that can be used in
practice that exploits this relationship sets:

$Q^{*}=\left\lceil\log(N)\right\rceil,$ (3)

where $\left\lceil\cdot\right\rceil$ rounds to the next integer and $N$ is the
number of NUTS2 regions within a country.This rule thus sets the optimal
number of factors as a function of $N$. In principle, this choice leads to
relative CRPSs which are often extremely close to the best performing value of
$Q$ in Table 1.

Figure 1: Optimal number of factors versus number of NUTS2 regions by country.
The blue solid line is the logarithmic fit.

All results discussed so far have been based on country-specific loss
measures. In the next step, we dig deeper into how nowcast performance varies
with $Q$ by taking into account cross-regional variation within a given
country. Figure 2 includes boxplots for each country. The lower and upper
quantiles in each box-plot represent the variation in CPRSs across NUTS2
regions and the median is the unweighted median performance per country. The
figure gives rise to several relevant insights. First, the U-shaped
relationship between $Q$ and nowcast accuracy is observed once again. This is
evidenced by the decrease in median with increasing values of $Q$ (before
deteriorating slightly), as well as the downward shift in the full cross-
sectional distribution of CRPSs. Second, the cross-sectional dispersion in
forecast gains declines with increasing values of $Q$. This implies that more
factors can better accommodate local dynamics, leading to a more homogeneous
forecast performance for a larger value of $Q$. It is worth stressing,
however, that this reduction in cross-sectional variance is not linear; we
find a substantial reduction in variance when the number of factors is low but
the effect of increasing the number of factors, if $Q$ is large, is
negligible. Third, adding too many factors hurts nowcast performance not only
on aggregate but also for most regions under consideration. Recall that the
fully-specified model (which sets $Q=N$ or $Q=10$) approximates the MF-VAR by
Koop et al. (2020), in particular if the number of NUTS2 regions is below
$10$. When we compare models, we find that our proposed model achieves
sizeable gains with respect to this additional “benchmark.”

Figure 2:  Boxplots of CRPS across number of factors for the MF-DFM models by
country. The maximum number of factors is limited by the number of regions in
the country. The CRPS is weighted by the historical GVA share across the full
sample. The CRPS is reported relative to the one of the RW: values below 1
indicate a better performance than the benchmark.

The boxplots provide only a rough gauge on the overall cross-regional
variation. To shed further light on how well our model (with an optimal number
of factors) works in particular regions, we present a map of average
nowcasting gains in Figure 3. Regions shown in blue point towards a better
performance of the proposed model with respect to the RW benchmark.

Figure 3: Average CRPS across hold-out periods (2016-2021) by NUTS2 for MF-DFM
models. The CRPS is reported relative to the one of the RW: values below 1 (in
blue) indicate a better performance than the benchmark.

The proposed models improve upon the benchmark in 97% of the regions, with
average gains of around 37% across regions. This is evidenced by a great deal
of blue shaded areas. Only in five out of 162 regions, the RW improves upon
our proposed specification. These regions are spread across Finland, Ireland
and Portugal, thus suggesting this relatively weaker performance is not
country-specific. There are also several regions where improvements vis-á-vis
the random walk are particularly pronounced. These are mostly located in
Greece, France and Italy. Our model, with its flexibility and its use of
quarterly information on national output growth, is capable of capturing this,
leading to more precise nowcasts.

Considering average predictive performance over the hold-out period masks
information about whether our model performs differently over distinct points
in time. To gain a better understanding of whether the good performance of our
model is driven by a few periods in which the random walk benchmark performs
poorly or whether the performance is stable and consistently better throughout
the hold-out, we consider the relative CRPSs over time. These are in the form
of boxplots which measure cross-sectional variation, as shown in Figure 4.
Again, we select the number of factors based on the average CRPS performance
over time.

Figure 4: Boxplots of CRPS across out-of-sample years for the MF-DFM models by
country. The CRPS is weighted by the historical GVA share across the full
sample. The CRPS is reported relative to the one of the RW: values below 1
indicate a better performance than the benchmark.

The figure reveals that forecast performance relative to the benchmark is
remarkably stable over time. For some countries, we observe slight variation
during 2020. For instance, for Austria we observe that the cross-sectional
dispersion (measured through the distance between the first and third
quartile) declines and substantial mass shifts downwards. A similar finding,
but somewhat less pronounced, can be found for Spain.

###  3.3 Full sample estimates of quarterly regional GVA

Important outputs of our model are quarterly series of annually released
regional GVA. While the resulting time series are interesting in their own
right, we also use this section to showcase some of the implications of the
implementation of our model. At the heart of our framework lie the quarterly
latent regional factors $\tilde{\boldsymbol{f}}_{t}$. These are extracted from
the annually observed data using the measurement Equation (1) in conjunction
with state Equation (2).

The raw latent processes are not interesting by themselves, but can be
transformed to the scale of the observed regional measurements via the
intertemporal restriction. The “temporal” loadings ($1/4,2/4,3/4,\ldots$) map
the latent states to annualised values, while the region-specific loadings
$\lambda_{iq}$ weight these factors with respect to their importance regarding
individual regions. Note that, in the absence of measurement errors, we would
obtain identities for regional annual observations at the end of each year.
Due to the factor structure and measurement errors we assume this is not the
case, although we will see later that within-year uncertainty decreases
appreciably when the intertemporal restriction holds at least approximately.
The resulting posterior median estimates across all countries are shown in
Figure 5; individual regions are distinguished in different shades of blue. It
is worth noting that running our model on a quarterly basis establishes a
sequence of vintages of (in-sample) regional GVA series.

Figure 5:  Posterior median of quarterly regional output by country (regions
are shown in different shades of blue). Number of factors selected based on
average forecast performance country-by-country.

Overall we find that business cycle dynamics within countries (i.e., across
regions for each country) are in many cases very similar, although sometimes
peaks and troughs differ with respect to both timing and magnitude. Examples
of such deviations are present and particularly striking in Belgium, Finland
or the Netherlands. This provides evidence of the merits of our approach:
substantial region-specific co-movement is modelled efficiently with the
factors, but the framework is flexible enough to allow for region-specific
idiosyncrasies.

Another important finding is that the quarterly regional series tend to to be
correlated across countries. Since we consider independent models for the
regions of each country, we do not exploit this apparent empirical regularity.
We again note that extensions of our framework, e.g., featuring all European
regions at once subject to country-specific and area-wide factors may be an
interesting aspect for future research, but comes with several complications
that we discussed earlier. A noteworthy exception to the co-movement across
countries is Ireland. Irish regional output is affected by similar factors
(i.e., the presence of a large number of US-multinational companies) as
national GDP measurement.

To illustrate specifics about the resulting higher-frequency estimates of
regional GVA, we pick Austria as an illustrative example. We choose this
country due to its moderate number of regions and because its dynamics are
representative of what we typically observe across all countries that we
consider. The quarterly regional series are shown in Figure 6 alongside annual
observations (black crosses). We now also indicate posterior uncertainty
surrounding the point estimates of the quarterly time series. Moreover, we
compare two distinct specifications of the model. First, the one-factor case,
which in light of our nowcast results can be characterised as an underfitting
version. Second, the multi-factor version with $Q=5$, which is selected based
on predictive evidence.

Figure 6: Regional output series for Austrian regions. Maximum number of
latent factors, $Q=5$, selected based on forecast performance. Black crosses
mark annual observations, shaded areas refer to 68 and 90 percent posterior
credible sets. Grey lines are posterior medians for all regions other than
those indicated on the y-axis.

Varying the number of factors has several implications for the resulting
quarterly series. First, by design, the one-factor case results in the
regional GVA series being proportional to one another, since they are scaled
versions of the same underlying latent quarterly states. The model thus has a
hard time balancing the fit across all cross-sectional units, and the actual
observations in many cases are far from the estimated regional series. Second,
we note that the uncertainty measures in these charts do not reflect the
measurement errors, which is why the credible sets in many cases do not cover
the realisations. Compared to the multi-factor model, the measurement errors
are much larger in this specification as the error term compensates for the
underfitting of the model. The shown posterior credible sets, as a consequence
of $Q=1$ resulting in a small-scale model with only a moderate number of
parameters, however, are tighter when compared to the $Q=5$ case. Having more
factors thus increases estimation uncertainty, but also improves region-by-
region fit of actual annual observations. Third, increasing the number of
factors usually results in smoother estimates. This phenomenon is also visible
in Figure 5 — the resulting estimates for large countries, which have a larger
number of factors, are typically smoother. Finally, as mentioned above, the
intertemporal restriction is not exactly binding due to the factor structure
we assume. Thus, we also observe variation surrounding estimates in quarters
when regional GVA is observed.

###  3.4 The onset of the pandemic through the lens of our model

High-frequency estimates of the regional GVA can become an essential tool for
policy formulation and evaluation. As an example, we investigate the behaviour
of the estimated high-frequency GVA in correspondence to the breakthrough of
the COVID-19 pandemic in Europe (see Carvalho et al., 2021 for a timeline of
the COVID-19 evolution). Figure 7 plots the maps of the quarterly GVA growth
in the last quarter of 2019 and the first two quarters of 2020 estimated using
our full sample.

The plot for 2019Q4 shows the pre-pandemic situation. While COVID-19 was
already spreading at the end of 2019, its impact on economic activities
materialised only starting from the first quarter of the following year. The
majority of European regions experienced mildly positive output growth, except
for the Greek region of Western Macedonia, the Liège region in Belgium, Köln
in Germany, and the Basilicata and Umbria regions in Italy.

The first major governmental restrictions to limit the spreading of the virus
in Europe were taken at the end of February 2020 in Northern Italy and were
rapidly followed by similar measures in the rest of the continent. The central
panel of Figure 7 shows the estimated GVA growth in 2020Q1. Compared to the
previous quarter, we observe a clear deterioration in economic conditions
across Europe. The northern Italian regions of Piedmont, Lombardy and Veneto
show a stronger decrease in GVA growth (the estimated GVA growth in all three
regions is smaller than $-3$%) than the rest of the sample, reflecting the
fact that those regions were the first ones to be badly hit by COVID-19.

Moving to the second quarter of 2020, the situation deteriorates in all
regions in our sample. Europe is now the epicentre of the COVID-19 pandemic
with the highest number of reported cases and deaths worldwide, accompanied by
mobility restrictions and lockdowns.666See this World Health Organisation
statement. The Northern Italian regions are again largely impacted by the
negative consequences of the COVID-19 spreading, with an average estimated
quarterly GVA growth of approximately $-7$%. Other regions that show the
largest contractions of GVA are some coastal regions in Portugal, as well as
the insular regions in Spain and Greece: these territories are characterised
by a strong dependence on the tourism and hospitality industries, which were
among the most impacted by the pandemic (Plzáková and Smeral, 2022).

Figure 7: Quarterly estimates of regional GVA growth in 2019 Q4 and 2020 Q1-2.
Negative values are in red, while positive ones are in blue.

These high-frequency estimates of regional output can provide quantitative
guidance for both policy formulation and evaluation in all situations where
there is a need to target particular help to the most impacted regions.
Moreover, in case of budgetary constraints, these estimates can help allocate
the limited resources efficiently and promote the cohesion of regional
policies across European territories. The data set of quarterly GVA estimates
will be made available via the JRC Data Catalogue.777JRC Data Catalogue
available at data.jrc.ec.europa.eu.

##  4 Conclusions

Using regional data gives rise to (at least) two challenges. First, key series
such as GVA (as a measure of output) are only available on a yearly basis and
released with delays of over two years. Second, estimating joint regional
models implies that the number of time series to process becomes large. We
address both issues by proposing a MF-DFM model. Our model flexibly combines
national GVA data, available at the quarterly frequency, with regional GVA
series that are only available at an annual frequency. We introduce temporal
and cross-sectional restrictions to interpolate the yearly series and thus
obtain quarterly measures of regional GVA. We thoroughly investigate the
choice of the number of endogenous factors, leveraging on independent
estimates for the different European countries characterised by different
numbers of regions and other sources of heterogeneity. In a nowcasting
exercise, we show that our approach yields precise density forecasts. In a
case study, we show that our approach is capable of detecting the substantial
decline in regional GVA during the pandemic in a timely manner.

The basic model developed in this paper can be extended along further
directions. For instance, one shortcoming is that we model the countries
separately. In principle, pooling all series together and thus estimating a
huge dimensional factor model would be feasible. Another possible extension of
our model is to allow for time-varying parameters in the state and/or the
observation equation. Finally, and more from a practitioner’s perspective, it
is worth emphasising that our model can also be used as a tool to carry out
structural inference on the regional level.

## References

  * Billé et al. (2023) Billé AG, Tomelleri A, Ravazzolo F. 2023.  Forecasting regional GDPs: a comparison with spatial dynamic panel data models.  _Spatial Economic Analysis_ 0: 1–22.
  * Carvalho et al. (2010) Carvalho CM, Polson NG, Scott JG. 2010.  The horseshoe estimator for sparse signals.  _Biometrika_ 97: 465–480.
  * Carvalho et al. (2021) Carvalho T, Krammer F, Iwasaki A. 2021.  The first 12 months of COVID-19: a timeline of immunological insights.  _Nature Reviews Immunology_ 21: 245–256.
  * Chan et al. (2023) Chan JC, Poon A, Zhu D. 2023.  High-dimensional conditionally Gaussian state space models with missing data.  _Journal of Econometrics_ 236: 105468.
  * Claudio et al. (2020) Claudio JC, Heinisch K, Holtemöller O. 2020.  Nowcasting East German GDP growth: a MIDAS approach.  _Empirical Economics_ 58: 29–54.
  * Commission and Eurostat (2023) Commission E, Eurostat. 2023.  _Eurostat regional yearbook – 2023 edition_.  Publications Office of the European Union.
  * Gefang et al. (2020) Gefang D, Koop G, Poon A. 2020.  Computationally efficient inference in large Bayesian mixed frequency VARs.  _Economics Letters_ 191: 109120.
  * Gneiting and Raftery (2007) Gneiting T, Raftery AE. 2007.  Strictly proper scoring rules, prediction, and estimation.  _Journal of the American Statistical Association_ 102: 359–378.
  * Henzel et al. (2015) Henzel SR, Lehmann R, Wohlrabe K. 2015.  Nowcasting regional GDP: The case of the free state of saxony.  _Review of Economics_ 66: 71–98.
  * Huber et al. (2023) Huber F, Koop G, Onorante L, Pfarrhofer M, Schreiner J. 2023.  Nowcasting in a pandemic using non-parametric mixed frequency VARs.  _Journal of Econometrics_ 232: 52–69.
  * Koop et al. (2019) Koop G, McIntyre S, Mitchell J. 2019.  UK regional nowcasting using a mixed frequency vector auto-regressive model with entropic tilting.  _Journal of the Royal Statistical Society Series A: Statistics in Society_ 183: 91–119.
  * Koop et al. (2020) Koop G, McIntyre S, Mitchell J, Poon A. 2020.  Regional output growth in the United Kingdom: More timely and higher frequency estimates from 1970.  _Journal of Applied Econometrics_ 35: 176–197.
  * Koop et al. (2022) Koop G, McIntyre S, Mitchell J, Poon A. 2022.  Using stochastic hierarchical aggregation constraints to nowcast regional economic aggregates.  _International Journal of Forecasting_ (in press).
  * Koop et al. (2023) Koop G, McIntyre SG, Mitchell J, Poon A, Wu P. 2023.  Incorporating short data into large mixed-frequency VARs for regional nowcasting.  _Journal of the Royal Statistical Society Series A: Statistics in Society_ (in press).
  * Lehmann and Wikman (2023) Lehmann R, Wikman I. 2023.  Quarterly GDP estimates for the German states: New data for business cycle analyses and long-run dynamics .
  * Lehmann and Wohlrabe (2015) Lehmann R, Wohlrabe K. 2015.  Forecasting GDP at the regional level with many predictors.  _German Economic Review_ 16: 226–254.
  * Mariano and Murasawa (2003) Mariano RS, Murasawa Y. 2003.  A new coincident index of business cycles based on monthly and quarterly series.  _Journal of Applied Econometrics_ 18: 427–443.
  * Mariano and Murasawa (2010) Mariano RS, Murasawa Y. 2010.  A coincident index, common factors, and monthly real GDP.  _Oxford Bulletin of Economics and Statistics_ 72: 27–46.
  * Plzáková and Smeral (2022) Plzáková L, Smeral E. 2022.  Impact of the covid-19 crisis on european tourism.  _Tourism Economics_ 28: 91–109.
  * Schorfheide and Song (2015) Schorfheide F, Song D. 2015.  Real-time forecasting with a mixed-frequency VAR.  _Journal of Business & Economic Statistics_ 33: 366–380.
  * Schorfheide and Song (2020) Schorfheide F, Song D. 2020.  Real-time forecasting with a (standard) mixed-frequency VAR during a pandemic.  _FRB of Philadelphia WP_ 20-26.


# AutoTAMP: Autoregressive Task and Motion Planning with LLMs as Translators
and Checkers

Yongchao Chen
MIT / Harvard University
<EMAIL_ADDRESS>
&Jacob Arkin
MIT
<EMAIL_ADDRESS>
Yang Zhang
MIT-IBM Watson AI Lab
<EMAIL_ADDRESS>
&Nicholas Roy
MIT
<EMAIL_ADDRESS>
&Chuchu Fan
MIT
<EMAIL_ADDRESS>

###### Abstract

For effective human-robot interaction, robots need to understand, plan, and
execute complex, long-horizon tasks described by natural language. The recent
and remarkable advances in large language models (LLMs) have shown promise for
translating natural language into robot action sequences for complex tasks.
However, many existing approaches either translate the natural language
directly into robot trajectories, or factor the inference process by
decomposing language into task sub-goals, then relying on a motion planner to
execute each sub-goal. When complex environmental and temporal constraints are
involved, inference over planning tasks must be performed jointly with motion
plans using traditional task-and-motion planning (TAMP) algorithms, making
such factorization untenable. Rather than using LLMs to directly plan task
sub-goals, we instead perform few-shot translation from natural language task
descriptions to an intermediary task representation that can then be consumed
by a TAMP algorithm to jointly solve the task and motion plan. To improve
translation, we automatically detect and correct both syntactic and semantic
errors via autoregressive re-prompting, resulting in significant improvements
in task completion. We show that our approach outperforms several methods
using LLMs as planners in complex task domains.111Datasets and Codes are
available at https://github.com/yongchao98/AutoTAMP

> Keywords: Large Language Models, Task and Motion Planning, Human-Robot
> Interaction

##  1 Introduction

A long-standing goal of robotics has been to provide agents with the ability
to find and execute optimal plans for complex tasks. Robots not only need to
reason about the task in the environment and find a satisfying sequence of
actions but also verify the feasibility of executing those actions according
to the robot’s motion capabilities. This problem is referred to as task and
motion planning (TAMP), and there has been considerable research on efficient
algorithms [1]. Classic solutions rely on specifying tasks in a dedicated
planning representation amenable to such algorithms [2, 3, 4, 5].

While this approach to task specification has been quite successful, directly
using these representations requires training and experience, making them a
poor candidate as an interface for non-expert users. As an alternative,
natural language (NL) provides an intuitive and flexible mode of task
descriptions. Excitingly, pre-trained large language models (LLMs) have
demonstrated surprisingly good performance on many language-related tasks [6],
and there has been an associated burst of research investigating their various
potential applicability to TAMP [7, 8, 9, 10, 11, 12, 13].

Early efforts showed promising results using LLMs as direct task planners [7],
i.e., generating a sequence of sub-tasks based on a set of natural language
instructions, but were limited by a lack of feedback and verification of
executability of the sub-task sequence. Further research addressed
executability by connecting sub-tasks to control policy affordance functions
[8], providing environmental feedback of robot actions [10], and interleaving
action feasibility checking with LLM action proposals [9]. However, these
approaches struggle with various task complexities, such as temporally-
dependent multi-step actions, action sequence optimization, task constraints,
etc. Furthermore, these frameworks factor the planning problem and use LLMs to
infer a task plan separately from the motion plan. In many situations, the
task and motion plan must optimized together to fulfill the task. For
instance, when the task is ‘reach all locations via the shortest path’, the
order of places to be visited (task planning) depends on the geometry of the
environment and the related motion optimization. Unfortunately, as we show in
this paper, LLMs do not seem capable of directly generating trajectories,
possibly related to limitations in complex spatial and numerical reasoning
[14, 15].

Notably, the task representations used in classic TAMP, such as PDDL [2] or
Temporal Logics [3], are sufficiently expressive to specify task complexities
from which existing planning algorithms can find and verify action sequences
satisfying those specifications. To benefit from both the user-friendliness of
NL and the capabilities of existing TAMP algorithms, we approach the problem
by using LLMs to translate from high-level task descriptions to formal task
specifications. We are not the first to use LLMs as translators of task
specifications [16, 17], but our work contributes several new ideas that
improve the performance of such approaches. First, previous work focused on
translating natural language into PDDL goals [16] or Linear Temporal Logics
(LTL) [18], which only considered the problem of task planning. Here we
utilize Signal Temporal Logic (STL) as the intermediary representation, from
which the planner directly optimizes the whole trajectory, i.e, task and
motion planning together, thus improving planning success rate. Second, we
also use re-prompting to automatically correct task specification errors, both
via an existing syntactic error correction framework and a novel semantic
error checking and correcting loop using LLMs, resulting in significantly
improved performance. We also conduct an ablation study integrating a fine-
tuned NL-to-STL model [19] with our AutoTAMP approach and show that GPT-4 few-
shot learning is competitive with fine-tuning. We conclude that in-context
learning with pre-trained LLMs is well suited for language-to-task-
specification translation for solving TAMP problems.

In this paper, we contribute the following:

  * •

Pre-trained LLM (GPT-3 and GPT-4) few-shot translation from NL task
descriptions to STLs, and execution of trajectories via an STL planner.

  * •

A novel autoregressive re-prompting technique for automatic checking and
correcting of semantic errors in generated task specifications via LLMs. We
show that, when combined with automatic syntactic correction, this technique
greatly improves task success rates.

  * •

Comprehensive experiments in challenging task domains, including several
multi-agent tasks. We show that our approach outperforms direct LLM planning
methods for tasks with hard geometric and temporal constraints.

  * •

In addition to our code, we publish a dataset of 1400 test cases consisting of
the language instruction, environments, produced STL specifications, and
resulting trajectories.

##  2 Problem Description

Figure 1:  GPT-4 failure case for direct end-to-end trajectory planning. The
orange line shows the correct path obeying the instruction. The purple and
gray dashed lines show the trajectories from GPT-4 after first and second
prompts, respectively. GPT-4 generates a list of $(x,y)$ locations with
associated timepoints. The initial prompt describes the language modeling
task, environment state, and instruction. Each object is a rectangle described
by $(x,y)$ boundaries.

As shown in Figure 1, we aim to convert a natural language instruction,
including spatial and temporal constraints, into a motion plan for a robot
encoded as a set of timed waypoints, e.g., $(x_{i},y_{i},t_{i})$. The
environment state is encoded as set of named obstacles described as polygons
and is provided as additional context. Our task is to generate a constraint-
satisfying trajectory based on the given instruction and the environment
state. The robot must not surpass its maximum velocity, and the total
operation time should not exceed the task time limit. We assume that the full
trajectory is a linear interpolation between the timed waypoints; complex
trajectories can be specified by dense waypoint sequences.

##  3 Methods

Figure 2:  Illustration of different approaches applying LLMs for task and
motion planning.

Figure 2 illustrates three of the approaches we compare in our work, each
using LLMs in some capacity. Each takes as input (1) a text-based
representation of the global environment state, (2) in-context examples for
few-shot learning, and (3) a natural language instruction. For methods using
feedback or re-prompting, we describe details of the re-prompt context in
Appendix A.

###  3.1 LLM End-to-end Motion Planning

One natural idea is to use an LLM to handle both the task and motion planning
by directly generating a trajectory for a given language instruction; we refer
to this as LLM End-to-end Motion Planning. Where the generated trajectory
violates constraints, we re-prompt the model with the constraint violation to
produce another trajectory, allowing up to five such re-prompts. Figure 1
illustrates this pipeline, including a specific failure case with two
constraint-violating trajectories.

###  3.2 LLM Task Planning

A more common approach is to use an LLM to handle the task planning by
directly generating a sequence of sub-tasks from a given language instruction;
we refer to this as LLM Task Planning. To generate a final trajectory, the
sub-tasks are handled by an independent motion planner. In this work, these
sub-tasks are limited to navigation actions, and the motion planning is
handled by the STL planner used by our proposed approach; this permits fair
comparison of results across methods. Each sub-task is converted to STL to be
consumed by the planner (more details are presented in Appendix B). We
evaluate and compare against three methods that each use LLMs for task
planning: (1) Naive Task Planning, (2) SayCan, and (3) LLM Task Planning +
Feedback.

Naive Task Planning As proposed by Huang et al. [7], we evaluate using LLMs to
generate the entire sub-task sequence without checking for executability.

SayCan Alternatively, an LLM can be autoregressively prompted to generate each
subsequent sub-task conditioned on the previous sub-tasks in the sequence. The
next sub-task can be selected from the top K candidates by combining the
language model likelihood with a feasibility likelihood of the candidate
action and choosing the most-likely next sub-task. This is the method proposed
by Ahn et al. [8]. We set K to 5 in our evaluations.

LLM Task Planning + Feedback A third task planning method combines full
sequence generation with feasibility checking to both find sub-task sequences
that satisfy the full task and verify their feasibility before execution. For
any infeasible sub-tasks, the LLM can be re-prompted with feedback about the
infeasible actions to generate a new sub-task sequence. This is similar to the
hierarchical method proposed by Lin et al. [9] but with feedback for re-
prompting.

Figure 3:  An example of full prompt used by our AutoTAMP framework

###  3.3 Autoregressive LLM Specification Translation&Checking + Formal
Planner

Unlike LLM Task Planning, our approach translates NL to STL with an LLM and
then plans the trajectory with an STL planner, as shown in Figure 2. We
include two re-prompting techniques to improve translation performance: one
for syntactic errors and another for semantic errors. We show one example of
the prompt in Figure 3.

Signal Temporal Logic Syntax In this work, we use STL [20] as a formal task
specification that supports continuous real-time constraints suitable for
time-critical missions. An STL formula is defined recursively according to the
following syntax:

$\phi::=\pi^{\mu}\;|\;\neg\phi\;|\;\phi\land\varphi\;|\;\phi\lor\varphi\;|\;\textbf{F}_{[a,b]}\phi\;|\;\textbf{G}_{[a,b]}\phi\;|\;\phi\textbf{U}_{[a,b]}\varphi$
(1)

where $\phi$ and $\varphi$ are STL formulas, and $\pi^{\mu}$ is an atomic
predicate. $\neg$ (negation), $\land$ (and), $\lor$ (or), $\Rightarrow$
(imply), and $\Leftrightarrow$ (equal)) are logical operators.
$\textbf{F}_{[a,b]}$ (eventually/finally), $\textbf{G}_{[a,b]}$
(always/globally), and $\textbf{U}_{[a,b]}$ (until) are temporal operators
with real-time constraints $t\in[a,b]$. Temporal operators with time
constraints are illustrated by Appendix C, and other operators can be
presented using the basic syntax. The action primitives in this work are
’enter(room_name)’ and ’not_enter(room_name)’. To avoid issues of parentheses
matching, the generated STLs adhere to pre-order form, as discussed in
Appendix D.

STL Trajectory Planner We use a state-of-the-art STL planner [21] capable of
multi-agent planning. It defines the validity of an STL formula with respect
to a trajectory and then optimizes the trajectory to maximize the validity.
The planner only considers the state within or out of a region, and outputs a
sequence of location & time pairs.

Syntactic Checking & Semantic Checking Open-loop translation can suffer from
syntactic and semantic errors. We use two re-prompting techniques to
automatically correct such errors. Like Skreta et al. [22] we use a verifier
to check for syntax errors; any found are provided as feedback when re-
prompting the LLM to generate corrected STL. We repeat until no errors are
found (up to five iterations). For semantic errors, we propose a novel
autoregressive re-prompting technique that feeds the STL planner’s generated
state sequence (i.e., [[in(road), 0], [in(red kitchen), 0.5], [in(blue
restroom2), 1.2]…]) back into the LLM to check whether it satisfies the
original instruction. If it does not, the LLM is prompted to modify the STL,
which repeats the syntactic and semantic re-prompting. This process terminates
in the case of no detected errors or no change in STL (up to three
iterations).

##  4 Experimental Design

Each of our task scenarios is set in a 2D environment and entails navigation
of one or more robots; the robots have extent in the environment and are
initialized with varying start positions. Each environment is comprised of
regions with a shape, location, and characteristics (e.g., color, name,
function). For each method we evaluate, the LLM is initially prompted with a
description of the language task (e.g. task planning) and five in-context
examples (these depend on the language task). To mitigate variance across
prompts, we initially tested six different sets of examples for each method
and chose the one that performed best. Through this testing, we found that the
variance over prompts was insignificant relative to overall performance.

We evaluated the different methods described in Section 3 across six different
task scenarios (three single-agent and three multi-agent) with different
combinations of geometric and temporal constraints. For each scenario
description below, we indicate the presence of these constraints below with G
and T, respectively. For each method, we evaluate performance with both GPT-3
and GPT-4 as the LLM. Note that in multi-agent scenarios, we do not test
SayCan or LLM Task Planning + Feedback because these methods are not straight-
forwardly adaptable for multiple agents. We also terminate and report failure
for test cases that take more than 90 minutes. We automatically check
resulting trajectories via hard-coded checkers. The full set of experiments
took two weeks using four 16-core CPUs; the cost of LLM API calls was
~1500USD.

Figure 4:  HouseWorld and Chip’s Challenge are single-agent scenarios.
Overcooked, Rover, and Wall are multi-agent scenarios. The black square in
Overcooked is inadmissible. The lines indicate the correct trajectories
following the instructions. For the HouseWorld and Chip’s Challenge
environments, the black round dot and pentagonal dot indicate the start and
end positions, respectively.

HouseWorld1 (single-agent) As shown in Figure 4(a), this is a house
environment from Finucane et al. [23]. We first manually constructed 10
different instructions of varying complexity (see Appendix E) before prompting
GPT-4 to paraphrase each into 9 differently worded instructions with the same
meaning, resulting in 100 total instructions for this environment. For each
instruction, we randomly initialize between two start-end position pairs for
200 total test cases. For this scenario, we do not impose a hard time
constraint for the planned trajectory.
Example instruction: ’Visit two rooms with color closest to red, but not the
pure red color.’
Corresponding STL: (finally room_purple and finally room_pink).

HouseWorld2 (T, single-agent) This scenario is identical to HouseWorld1, but
each planned trajectory is subjected to a hard time constraint. This time
limit is pre-determined by completing the correct trajectory with 0.8 maximum
velocity.
Example instruction: ’Visit two rooms with color closest to red, but not the
pure red color. The task should be completed within 10 seconds.’
Corresponding STL: (finally[0, 10] room_purple and finally[0, 10] room_pink).

The remaining task scenarios were designed with specific rules and goals for
the agent(s) to follow. For each scenario, GPT-4 was used to paraphrase the
original description into 20 uniquely worded variants with the same meaning.
We instantiate three different instances of the environment for each scenario
and randomize five different start/end location pairs for a total of 300 test
cases. Note that the avoidance of collision among multiple agents has been
inherently encoded in the STL planner.

Chip’s Challenge (G, single-agent) Figure 4(b) shows a scenario inspired by a
level from Chip’s Challenge, a classic puzzle solving game with strict
geometric and logical constraints. The robot must reach all goal regions
(blue) but must acquire a unique key to pass through the corresponding door.
The task planning must obey both the spatial and logical constraints.
Example instruction: ’Try to reach all the goals but you have to reach the
corresponding key first to open the specific door. For example, you have to
reach key1 ahead to open door1. Also remember always do not touch the walls.’
Corresponding STL: finally enter(goali) (i = 1,2,3…) and ( negation
enter(doorj) until enter(keyj) (j = 1,2,3…) ) and globally not_enter(walls)

Overcooked (G & T, multi-agent) Figure 4(c) shows a scenario inspired by
Overcooked, a popular cooking simulation game with strict time constraints.
The agents must cooperatively gather ingredients and return to CookingRoom in
a limited time. In this scenario, the multi-agent motion planning is
challenged by limited space for agents to maneuver.
Example instruction: ’Enter all the ingredient room to pick up food. Once
entered ingredient rooms, go to cooking room within 3 seconds. And all the
agents should not collide each other and black obstacles.’
Corresponding STL: finally enter(ingredienti) (i = 1,2,3…) and (
enter(ingredientj) imply finally[0, 3] enter(CookingRoom) (j = 1,2,3…) ) and
globally not_enter(walls)

Rover (G & T, multi-agent) Figure 4(d) is a scenario used by Sun et al. [21].
Multiple agents must reach each observation region (blue goals) before
transmitting the observations by entering a red region, all while subjected to
time and energy constraints.
Example instruction: ’All rovers must reach the blue charging station within 5
units of time each time they exit it. Once they reach their destination, they
need to get to a yellow transmitter within 2 time units to send the collected
information to the remote control. Rovers must keep clear of black walls and
other rovers. All target areas need to be visited.’
Corresponding STL: finally enter(goali) (i = 1,2,3…) and ( enter(goalj) imply
finally[0, 2] ( enter(Transmitter_1) or enter(Transmitter_2) ) (j = 1,2,3…) )
and ( not_enter(Charging) imply finally[0, 5] enter(Charging) and globally
not_enter(walls) )

Wall (G & T, multi-agent) Figure 4(e) is also a scenario from Sun et al. [21].
Multiple agents must occupy each goal region (blue) while subject to a time
constraint and a maneuver bottleneck.
Example instruction: ’Reach all the goals and stay there. Take care of the
collision among each agent and to the walls.’
Corresponding STL: finally globally enter(goali) (i = 1,2,3…) and globally
not_enter(walls)

Appendix F shows key frame sequences of correctly planned trajectories for the
three multi-agent scenarios as produced via our AutoTAMP method.

##  5 Results

###  5.1 Task Success Rates

Table 1: Task success rates in single-agent scenarios. The scenarios have hard temporal or geometric constraints. | HouseWorld1 | HouseWorld2 | Chip Challenge
---|---|---|---
| (soft time cst.) | (hard time cst.) | (hard geo. cst.)
GPT-3 end2end | $0\%$ | $0\%$ | $0\%$
GPT-3 naive task planning | $74\%$ | $36\%$ | $0\%$
SayCan | $75.5\%$ | $36\%$ | $0\%$
GPT-3 task planning/feed. | 79% | $40\%$ | $0\%$
GPT-3/STL | $28\%$ | $27\%$ | $29\%$
GPT-3/STL/Syn. | $49\%$ | $47\%$ | $66\%$
GPT-3/STL/Syn./Sem. (AutoTAMP) | $62\%$ | 62% | 74.3%
GPT-4 end2end | $9.5\%$ | $9.5\%$ | $0\%$
GPT-4 naive task planning | $90\%$ | $45\%$ | $0\%$
SayCan | $90\%$ | $47.5\%$ | $0\%$
GPT-4 task planning/feed. | 92% | $49\%$ | $0\%$
GPT-4/STL | $43.5\%$ | $42\%$ | $42.7\%$
GPT-4/STL/Syn. | $59.5\%$ | $59\%$ | $70\%$
GPT-4/STL/Syn./Sem. (AutoTAMP) | $82.5\%$ | 82% | 87.7%
Table 2: Task success rates in multi-agent scenarios. Each scenario has hard temporal and geometric constraints. | Overcooked | Rover | Wall
---|---|---|---
| (multi-agent, hard time & geo. cst.)
GPT-3 end2end | $0\%$ | $0\%$ | $0\%$
GPT-3 naive task planning | $13.3\%$ | $0\%$ | $7\%$
GPT-3/STL | $25\%$ | $22\%$ | $74\%$
GPT-3/STL/Syn. | $70\%$ | $35\%$ | $85\%$
GPT-3/STL/Syn./Sem. (AutoTAMP) | 89% | 60.7% | 89.7%
GPT-4 end2end | $5\%$ | $0\%$ | $6\%$
GPT-4 naive task planning | $17\%$ | $0\%$ | $47\%$
GPT-4/STL | $85\%$ | $46\%$ | $95\%$
GPT-4/STL/Syn. | $94\%$ | $67\%$ | $95\%$
GPT-4/STL/Syn./Sem. (AutoTAMP) | 100% | 79% | 100%

We report the task success rates for the single-agent and multi-agent
scenarios in Table 1 and Table 2, respectively. For HouseWorld1 (Figure 4(a))
with no hard time constraint, we find that all methods using LLMs as task
planners outperform our approach; this environment permits direct trajectories
between any two positions and thus lacks geometric challenges that such
methods will struggle with. When adding a strict time constraint
(HouseWorld2), we see that such methods perform much worse while AutoTAMP’s
success rate persists. For the remaining tasks that include geometric
constraints, LLM End-to-end Motion Planning and Naive Task Planning both
perform quite poorly. Unsurprisingly, we observe a general trend that GPT-4
outperforms GPT-3 for all methods.

###  5.2 Failure examples for LLM Task Planning and AutoTAMP Methods

LLM Task Planning: We observe that LLM Task Planning methods may fail at tasks
that require long-horizon planning. Figure 5 below illustrates two examples.
In (a), these methods inefficiently grab the key for a particular door only
when that door is the next immediate obstacle. Rather than grab both key1 and
key2 that are near the starting position before unlocking door1, it sequences
the actions to grab key1, unlock door1, then grab key2. This inefficiency can
lead to a violation of time constraints that are part of the task
specification, resulting in task failure. In (b), ingredient1 is unnecessarily
(and inefficiently) visited by both agents.

Figure 5:  Two examples of failures by LLM Task Planning methods.

AutoTAMP: AutoTAMP (and the ablations) primarily fail because of translation
errors. While the re-prompting techniques we use to improve translation are
effective, there are still translation errors that result in task failure.

###  5.3 Planning Time

We report timing information for AutoTAMP with GPT-4 in Table 3. For each
scenario, we report 10th, 50th, and 90th percentile runtime cost for the
following steps in the overall process: GPT-4 API call, STL planner planning
time, code execution time, GPT-4 translation to STL, syntactic check loop,
semantic check loop. Overall, the STL planner runtime is the main bottleneck.
In cases where the GPT-4 API call takes an excessive amount of time (i.e. more
than 100s), we note that this is likely due to unstable latency and may not be
a good proxy for decoding runtime.

We also report the number of iterations for both the syntactic and semantic
re-prompting techniques for each task scenario. Note that semantic re-
prompting subsequently requires an additional round of syntactic re-prompting
for the new STL output; thus, syntactic re-prompting can have more total
iterations than the limit of 5 since this limit is applied per STL output.

Table 3: Timing information for each step of AutoTAMP using GPT-4; Iteration counts for the syntactic and semantic re-prompting. For each, We report the 10th, 50th, and 90th percentile. Time (s) | HouseWorld2 | Chip. | Overcooked | Rover | Wall
---|---|---|---|---|---
Total Time | $15/42/221$ | $403/871/1579$ | $34/77/157$ | $79/123/174$ | $21/43/67$
GPT-4 API | $2/3/55$ | $8/21/160$ | $3/5/7$ | $10/14/18$ | $4/6/7$
STL Planner | $10/35/152$ | $310/732/1482$ | $30/74/148$ | $68/89/142$ | $17/34/49$
Code Processing | $3/3/3$ | $3/4/4$ | $3/3/3$ | $3/4/4$ | $3/3/3$
GPT-4/STL | $5/9/10$ | $172/457/681$ | $16/20/45$ | $15/18/29$ | $6/9/15$
Syntactic Check | $1/3/60$ | $11/23/163$ | $4/7/12$ | $5/6/7$ | $2/3/5$
Semantic Check | $6/36/157$ | $141/630/850$ | $17/58/106$ | $75/102/134$ | $14/31/54$
Iterations | HouseWorld2 | Chip. | Overcooked | Rover | Wall
Syntactic Check | $1/2/2$ | $3/5/7$ | $1/2/2$ | $2/3/6$ | $1/2/3$
Semantic Check | $1/2/3$ | $3/3/3$ | $2/2/3$ | $2/3/3$ | $2/2/3$

###  5.4 Ablation Studies

Syntactic and Semantic Checkers In Table 1 and 2, we also evaluate the impact
of syntactic and semantic error correction on using LLMs to translate to STL.
The results show that translation with no error correction has modest success
across task scenarios, but both syntactic and semantic error correction
significantly improve performance; this trend is present across all scenarios.

Fine-tuned NL2TL Translation Model Prior work (NL2TL [19]) has investigated
translating from natural language to STL via a modular pipeline that utilizes
a fine-tuned LLM. While incorporating NL2TL into our AutoTAMP framework was
not part of our primary investigation, we report here its impact on task
success in Table 4. The top three rows report AutoTAMP + NL2TL with ablations
over syntactic and semantic re-prompting. The bottom three rows report the
original ablation results of AutoTAMP without NL2TL. We see that integrating
NL2TL generally provides a modest improvement. However, it is exciting that
AutoTAMP appears competitive without the use of a fine-tuned model since it
does not rely on a targeted dataset or additional offline training.

Table 4: Ablation studies of the AutoTAMP with/without integrating the finetuned NL2TL model. | HouseWorld2 | Chip. | Overcooked | Rover | Wall
---|---|---|---|---|---
GPT-4/STL/NL2TL | $53\%$ | $61\%$ | $87\%$ | $58\%$ | $95\%$
GPT-4/STL/Syn./NL2TL | $64\%$ | $73\%$ | $94\%$ | $70\%$ | $95\%$
GPT-4/STL/Syn./Sem./NL2TL | 83.5% | 86% | 100% | 79.7% | 100%
(AutoTAMP) |  |  |  |  |
GPT-4/STL | $42\%$ | $42.7\%$ | $85\%$ | $46\%$ | $95\%$
GPT-4/STL/Syn. | $59\%$ | $70\%$ | $94\%$ | $67\%$ | $95\%$
GPT-4/STL/Syn./Sem. | 82% | 87.7% | 100% | 79% | 100%
(AutoTAMP) |  |  |  |  |

##  6 Related Work

LLMs for TAMP Recent claims about the impressive reasoning capabilities of
LLMs [6, 24] have led to interest in such models for task and motion planning.
One approach is to directly use LLMs as planners [7, 8, 9, 10, 11, 12, 13,
25]. Initial work showed that naive zero-shot generation of a primitive action
sequence from a high-level task description had relatively poor executability,
but few-shot in-context learning, constraining output to admissible actions,
and autoregressive step-by-step action generation significantly improved
performance [7]. Subsequent efforts connected to motion planning by grounding
the primitive actions to motion control policies and using affordance
functions to guide LLM-based task and motion planning [8, 9]; Huang et al.
[10] closed the loop by prompting with feedback, such as action success
indication, before querying for the next action. Other work focused on how
prompting can inform task execution, such as few-shot summarization for user
task preferences [11] or extraction of commonsense arrangements for
underspecified object placement [13]. Despite these successes, however, there
is some evidence that LLMs exhibit poor performance on more realistic tasks
[15, 26], motivating different approaches. While we are interested in LLMs for
TAMP, our work does not directly use LLMs as planners.

Translating Language to Task Representations A natural alternative is to rely
on dedicated planners by mapping from natural language to a planning
representation. For over a decade, research has investigated mapping language
to lambda calculus [27], motion planning constraints [28], linear temporal
logic [29, 30, 31], and signal temporal logic [32, 33], among others. To
address challenges of data availability, task generalization, and linguistic
complexity, recent work has applied LLMs to this translation problem. Modular
approaches have used LLMs to extract referring expressions with corresponding
logic propositions to then construct a full temporal logic specification [34,
19]. Relying on LLMs for direct translation, other work has mapped from
language to PDDL goals [17] or full PDDL problems [35, 16]. Our work similarly
translates to a task specification, but we can represent complex constraints
(e.g. temporal), and we introduce a novel mechanism for automatic detection
and correction of semantic errors.

Re-prompting of LLMs The quality of LLM output is greatly improved with useful
context, such as few-shot in-context learning for novel tasks [6]. LLMs for
TAMP are typically also provided task-relevant information, such as
environment state or admissible actions [12]. Re-prompting with additional
context based on LLM output has been shown to be extremely beneficial, such as
with iterative action generation [7], environmental feedback [10],
inadmissible actions [7, 8, 9], unmet action preconditions [36, 35], code
execution errors [37], and syntactic errors in structured output [22]. Our
work utilizes the same syntactic correction re-prompting technique as Skreta
et al. [22], but we further introduce automatic detection and correction of
semantic errors via re-prompting.

##  7 Conclusion and Limitations

This paper presented AutoTAMP, a framework for using pre-trained LLMs as
translators from language task descriptions to formal task specifications in
STL via few-shot learning; a key contribution is that we show that our use of
STL significantly improves the performance of the planner, and that the
translation via automatic correction of syntax errors and a novel
autoregressive re-prompting technique for semantic error checking and
correction lead to further performance gains. Our experimental results show
using LLMs to translate to task specifications that can be solved via a formal
planner outperforms approaches that use LLMs directly as planners when
handling tasks with complex geometric and temporal constraints.

Limitations 1) Though our results rely on using the best prompt out of several
candidates, the prompt used may not be the optimal for eliciting the best
performance of our LLMs. As a result, the individual results for each method
may be improvable, but we expect the trends to persist and will continue to
support the conclusion that LLMs are not well suited for direct complex TAMP.
2) Though the task success rates of AutoTAMP are good, the cost of the
planning time is high, especially for multiple syntactic and semantic re-
prompting iterations. Further work is needed that focuses on how to accelerate
formal planners and decrease LLM inference latency. 3) Some tasks still fail
due to translation errors. As part of future work, we aim to explore whether
feedback via a human-in-the-loop framework can both improve translation and
reduce AutoTAMP iterations.

#### Acknowledgments

We thank OpenAI for approving the usage of GPT-3/4 APIs.

The authors would also like to thank Charles Dawson, Oswin So, and Yue Meng
for the early-stage discussion and final reviews of the work.

This work was supported by ONR under Award N00014-22-1-2478 and MIT-IBM Watson
AI Lab. However, this article solely reflects the opinions and conclusions of
its authors.

## References

  * Garrett et al. [2021] C. R. Garrett, R. Chitnis, R. Holladay, B. Kim, T. Silver, L. P. Kaelbling, and T. Lozano-Pérez.  Integrated task and motion planning.  _Annual review of control, robotics, and autonomous systems_ , 4:265–293, 2021.
  * Fox and Long [2003] M. Fox and D. Long.  Pddl2. 1: An extension to pddl for expressing temporal planning domains.  _Journal of artificial intelligence research_ , 20:61–124, 2003.
  * Emerson [1990] E. A. Emerson.  Temporal and modal logic.  In _Formal Models and Semantics_ , pages 995–1072. Elsevier, 1990\.
  * He et al. [2015] K. He, M. Lahijanian, L. E. Kavraki, and M. Y. Vardi.  Towards manipulation planning with temporal logic specifications.  In _2015 IEEE International Conference on Robotics and Automation (ICRA)_ , pages 346–352, 2015.  doi:10.1109/ICRA.2015.7139022.
  * Fikes and Nilsson [1971] R. E. Fikes and N. J. Nilsson.  Strips: A new approach to the application of theorem proving to problem solving.  _Artificial Intelligence_ , 2(3):189–208, 1971\.  ISSN 0004-3702.  doi:https://doi.org/10.1016/0004-3702(71)90010-5.  URL https://www.sciencedirect.com/science/article/pii/0004370271900105.
  * Brown et al. [2020] T. Brown, B. Mann, N. Ryder, M. Subbiah, J. D. Kaplan, P. Dhariwal, A. Neelakantan, P. Shyam, G. Sastry, A. Askell, et al.  Language models are few-shot learners.  _Advances in neural information processing systems_ , 33:1877–1901, 2020.
  * Huang et al. [2022] W. Huang, P. Abbeel, D. Pathak, and I. Mordatch.  Language models as zero-shot planners: Extracting actionable knowledge for embodied agents.  In _International Conference on Machine Learning_ , pages 9118–9147. PMLR, 2022.
  * Ahn et al. [2022] M. Ahn, A. Brohan, N. Brown, Y. Chebotar, O. Cortes, B. David, C. Finn, K. Gopalakrishnan, K. Hausman, A. Herzog, et al.  Do as i can, not as i say: Grounding language in robotic affordances.  _arXiv preprint arXiv:2204.01691_ , 2022.
  * Lin et al. [2023] K. Lin, C. Agia, T. Migimatsu, M. Pavone, and J. Bohg.  Text2motion: From natural language instructions to feasible plans.  _arXiv preprint arXiv:2303.12153_ , 2023.
  * Huang et al. [2022] W. Huang, F. Xia, T. Xiao, H. Chan, J. Liang, P. Florence, A. Zeng, J. Tompson, I. Mordatch, Y. Chebotar, et al.  Inner monologue: Embodied reasoning through planning with language models.  _arXiv preprint arXiv:2207.05608_ , 2022.
  * Wu et al. [2023] J. Wu, R. Antonova, A. Kan, M. Lepert, A. Zeng, S. Song, J. Bohg, S. Rusinkiewicz, and T. Funkhouser.  Tidybot: Personalized robot assistance with large language models.  _arXiv preprint arXiv:2305.05658_ , 2023.
  * Singh et al. [2023] I. Singh, V. Blukis, A. Mousavian, A. Goyal, D. Xu, J. Tremblay, D. Fox, J. Thomason, and A. Garg.  ProgPrompt: Generating situated robot task plans using large language models.  In _International Conference on Robotics and Automation (ICRA)_ , 2023\.  URL https://arxiv.org/abs/2209.11302.
  * Ding et al. [2023] Y. Ding, X. Zhang, C. Paxton, and S. Zhang.  Task and motion planning with large language models for object rearrangement.  _arXiv preprint arXiv:2303.06247_ , 2023.
  * Wake et al. [2023] N. Wake, A. Kanehira, K. Sasabuchi, J. Takamatsu, and K. Ikeuchi.  Chatgpt empowered long-step robot control in various environments: A case application.  _arXiv preprint arXiv:2304.03893_ , 2023.
  * Valmeekam et al. [2022] K. Valmeekam, A. Olmo, S. Sreedharan, and S. Kambhampati.  Large language models still can’t plan (a benchmark for llms on planning and reasoning about change).  _arXiv preprint arXiv:2206.10498_ , 2022.
  * Liu et al. [2023] B. Liu, Y. Jiang, X. Zhang, Q. Liu, S. Zhang, J. Biswas, and P. Stone.  Llm+ p: Empowering large language models with optimal planning proficiency.  _arXiv preprint arXiv:2304.11477_ , 2023.
  * Xie et al. [2023] Y. Xie, C. Yu, T. Zhu, J. Bai, Z. Gong, and H. Soh.  Translating natural language to planning goals with large-language models.  _arXiv preprint arXiv:2302.05128_ , 2023.
  * Pan et al. [2023] J. Pan, G. Chou, and D. Berenson.  Data-efficient learning of natural language to linear temporal logic translators for robot task specification.  _arXiv preprint arXiv:2303.08006_ , 2023.
  * Chen et al. [2023] Y. Chen, R. Gandhi, Y. Zhang, and C. Fan.  Nl2tl: Transforming natural languages to temporal logics using large language models.  _arXiv preprint arXiv:2305.07766_ , 2023.
  * Maler and Nickovic [2004] O. Maler and D. Nickovic.  Monitoring temporal properties of continuous signals.  In _Formal Techniques, Modelling and Analysis of Timed and Fault-Tolerant Systems: Joint International Conferences on Formal Modeling and Analysis of Timed Systmes, FORMATS 2004, and Formal Techniques in Real-Time and Fault-Tolerant Systems, FTRTFT 2004, Grenoble, France, September 22-24, 2004. Proceedings_ , pages 152–166. Springer, 2004.
  * Sun et al. [2022] D. Sun, J. Chen, S. Mitra, and C. Fan.  Multi-agent motion planning from signal temporal logic specifications.  _IEEE Robotics and Automation Letters_ , 7(2):3451–3458, 2022.
  * Skreta et al. [2023] M. Skreta, N. Yoshikawa, S. Arellano-Rubach, Z. Ji, L. B. Kristensen, K. Darvish, A. Aspuru-Guzik, F. Shkurti, and A. Garg.  Errors are useful prompts: Instruction guided task programming with verifier-assisted iterative prompting.  _arXiv preprint arXiv:2303.14100_ , 2023.
  * Finucane et al. [2010] C. Finucane, G. Jing, and H. Kress-Gazit.  Ltlmop: Experimenting with language, temporal logic and robot control.  In _2010 IEEE/RSJ International Conference on Intelligent Robots and Systems_ , pages 1988–1993. IEEE, 2010.
  * Kojima et al. [2022] T. Kojima, S. S. Gu, M. Reid, Y. Matsuo, and Y. Iwasawa.  Large language models are zero-shot reasoners.  In _ICML 2022 Workshop on Knowledge Retrieval and Language Models_ , 2022.  URL https://openreview.net/forum?id=6p3AuaHAFiN.
  * Liang et al. [2022] J. Liang, W. Huang, F. Xia, P. Xu, K. Hausman, B. Ichter, P. Florence, and A. Zeng.  Code as policies: Language model programs for embodied control.  _arXiv preprint arXiv:2209.07753_ , 2022.
  * Silver et al. [2022] T. Silver, V. Hariprasad, R. S. Shuttleworth, N. Kumar, T. Lozano-Pérez, and L. P. Kaelbling.  PDDL planning with pretrained large language models.  In _NeurIPS 2022 Foundation Models for Decision Making Workshop_ , 2022.  URL https://openreview.net/forum?id=1QMMUB4zfl.
  * Dzifcak et al. [2009] J. Dzifcak, M. Scheutz, C. Baral, and P. Schermerhorn.  What to do and how to do it: Translating natural language directives into temporal and dynamic logic representation for goal management and action execution.  In _2009 IEEE International Conference on Robotics and Automation_ , pages 4163–4168. IEEE, 2009.
  * Howard et al. [2014] T. M. Howard, S. Tellex, and N. Roy.  A natural language planner interface for mobile manipulators.  In _2014 IEEE International Conference on Robotics and Automation (ICRA)_ , pages 6652–6659. IEEE, 2014.
  * Boteanu et al. [2016] A. Boteanu, J. Arkin, T. Howard, and H. Kress-Gazit.  A model for verifiable grounding and execution of complex language instructions.  In _Proceedings of the 2016 IEEE/RSJ International Conference on Intelligent Robots and Systems_ , Oct. 2016.
  * Gopalan et al. [2018] N. Gopalan, D. Arumugam, L. L. Wong, and S. Tellex.  Sequence-to-sequence language grounding of non-markovian task specifications.  In _Robotics: Science and Systems_ , volume 2018, 2018.
  * Kress-Gazit et al. [2008] H. Kress-Gazit, G. E. Fainekos, and G. J. Pappas.  Translating structured english to robot controllers.  _Advanced Robotics_ , 22(12):1343–1359, 2008\.
  * He et al. [2022] J. He, E. Bartocci, D. Ničković, H. Isakovic, and R. Grosu.  Deepstl: from english requirements to signal temporal logic.  In _Proceedings of the 44th International Conference on Software Engineering_ , pages 610–622, 2022.
  * Mohammadinejad et al. [2022] S. Mohammadinejad, J. Thomason, and J. V. Deshmukh.  Interactive learning from natural language and demonstrations using signal temporal logic.  _arXiv preprint arXiv:2207.00627_ , 2022.
  * Liu et al. [2022] J. X. Liu, Z. Yang, B. Schornstein, S. Liang, I. Idrees, S. Tellex, and A. Shah.  Lang2LTL: Translating natural language commands to temporal specification with large language models.  In _Workshop on Language and Robotics at CoRL 2022_ , 2022.  URL https://openreview.net/forum?id=VxfjGZzrdn.
  * Guan et al. [2023] L. Guan, K. Valmeekam, S. Sreedharan, and S. Kambhampati.  Leveraging pre-trained large language models to construct and utilize world models for model-based task planning.  _arXiv preprint arXiv:2305.14909_ , 2023.
  * Raman et al. [2022] S. S. Raman, V. Cohen, E. Rosen, I. Idrees, D. Paulius, and S. Tellex.  Planning with large language models via corrective re-prompting.  In _NeurIPS 2022 Foundation Models for Decision Making Workshop_ , 2022.  URL https://openreview.net/forum?id=cMDMRBe1TKs.
  * Silver et al. [2023] T. Silver, S. Dan, K. Srinivas, J. B. Tenenbaum, L. P. Kaelbling, and M. Katz.  Generalized planning in pddl domains with pretrained large language models.  _arXiv preprint arXiv:2305.11014_ , 2023.

##  Appendix A Recursive LLM Prompts

In this work, some methods need to re-prompt LLMs with context of the prompt
history. Unlike the GPT-4 API that provides a template for this, the GPT-3 API
template is for a single inference history; so, it is necessary to include any
prompt history as context that indicates prior user input and LLM responses.
We show an example in Figure 6.

Figure 6:  Example of prompting GPT-3 API recursively. The prompt should
indicate previous user prompts and LLM responses with tags (red).

##  Appendix B Convert Sub-task Sequence to STL

In order to evaluate LLM Task Planning methods, we use an STL planner [21]
(this is the same planner we use for our AutoTAMP method) as the motion
planner for generating trajectories. The LLM Task Planning methods generate
output of the form [[$enter(room_{1})$, $t_{1}$], [$enter(room_{2})$,
$t_{2}$],…, [$enter(room_{i})$, $t_{i}$], [$enter(room_{i+1})$, $t_{i+1}$]].
We automatically convert to STL to be consumed by the planner, i.e.,
finally[$t_{1}$, $t_{1}$] $enter(room_{1})$ and finally[$t_{2}$, $t_{2}$]
$enter(room_{2})$ … and finally[$t_{i}$, $t_{i}$] $enter(room_{i})$ and
globally $not\\_enter(walls)$. If the LLM Task Planning method also requires
an executability check (e.g. SayCan, LLM Task Planing + Feedback), we apply
the same conversion per sub-task; for example, given a sub-trajectory $i$, we
would convert to STL of the form finally[$t_{i+1}-t_{i}$, $t_{i+1}-t_{i}$]
$enter(room_{i+1})$ and globally $not\\_enter(walls)$ to then be checked for
executability.

##  Appendix C STL Syntax

Table 5: STL illustration $\textbf{F}_{[a,b]}\phi$ |  True at time $t$ if there exists a time in the interval $[t+a,t+b]$ where $\phi$ is true.
---|---
$\phi\textbf{U}_{[a,b]}\varphi$ |  True at time $t$ if $\varphi$ is true for some time $t^{{}^{\prime}}$ in the interval $[t+a,t+b]$, and for all times between $t$ and $t^{{}^{\prime}}$, the formula $\phi$ holds.
$\textbf{G}_{[a,b]}\phi$ |  True at time $t$ if for all times in the interval $[t+a,t+b]$, the formula $\phi$ holds.
$\varphi\textbf{$\Rightarrow$}\textbf{F}_{[300,infinite]}\phi$ |  If $\varphi$ happens, then some time after the next 300 time steps $\phi$ should happen.
$\neg\varphi_{1}\textbf{$\lor$}(\varphi_{2}\textbf{U}_{[286,348]}\varphi_{3})$ |  $\varphi_{1}$ should not happen , or else $\varphi_{2}$ happens and continues until at some point during the 286 to 348 time units $\varphi_{3}$ happens .

##  Appendix D Pre-order and In-order STL Formats

As shown in Figure 7, each STL can be viewed as a binary tree with each node
in the tree having at most two child nodes. When requesting NL-to-STL
translation, the targeted tokens of STLs can be linearized in an in-order
(left subtree, root, right subtree) or pre-order (root, left subtree, right
subtree) manner. For this work, we prompt LLMs to generate STL in the pre-
order format to avoid parentheses matching errors and for compatability with
the STL planner. We note that the translation performance with GPT-4 is
similar for both formats.

Figure 7:  Illustration of pre-order and in-order formats of STL. (a)
Different text representations of the formats for the same STL. (b) An example
binary tree representation of STL.

##  Appendix E Manually Designed Instructions for HouseWorld Scenario

  1. 1.

Navigate into the green bedroom and then go to the yellow restroom.

  2. 2.

Travel to the yellow restroom, and then go to the pink bedroom. Visit both the
kitchen and the dining room. Finally end in the red bathroom.

  3. 3.

Navigate into the green bedroom and then go to the yellow restroom, but
remember do not touch the livingroom at anytime.

  4. 4.

Go to one room with cyan color, then enter the bedroom and stay there for 5
seconds, finally reach the restroom. remember always do not touch the two true
blue areas.

  5. 5.

Visit two rooms with color closest to red, but not the pure red color.

  6. 6.

Visit every room that is not light pink or cyan.

  7. 7.

Always go to the kitchen immediately before entering either bathroom. Go to
the yellow room and the red room, but do not enter any blue rooms.

  8. 8.

Move to the kitchen, then move to the bedroom without entering any blue rooms.
Stay there for at least 10 seconds, then return to the kitchen via the living
room.

  9. 9.

Eventually end up in the master bedroom, but first go to both restrooms. After
you have gone to each restroom, do not pass through any other rooms.

  10. 10.

Visit every room at least once, but not go to the pink room until you are in a
larger blue room.

##  Appendix F Keyframes of Trajectories for Multi-agent Scenarios.

Figure 8:  Multi-agent task scenarios: Overcooked, Rover, and Wall. For
Overcooked, the blue regions represent target ingredients, the center black
square in an inadmissible region, and the yellow and green squares are agents.
For Rover and Wall, the blue regions represent goals, the black lines
represent walls, and the agents are the brown, yellow, orange, and green
squares. In all scenarios, the agents occupy space and are consequently
constrained by the inadmissible regions when moving through the environments.