# Faster Exact MPE and Constrained Optimization
with Deterministic Finite State Automata

Filippo Bistaffa IIIA-CSIC<EMAIL_ADDRESS>
###### Abstract

We propose a concise function representation based on deterministic finite
state automata for exact _most probable explanation_ and _constrained
optimization_ tasks in graphical models. We then exploit our concise
representation within Bucket Elimination (BE). We denote our version of BE as
FABE. FABE significantly improves the performance of BE in terms of runtime
and memory requirements by minimizing redundancy. Results on _most probable
explanation_ and _weighted constraint satisfaction_ benchmarks show that FABE
often outperforms the state of the art, leading to significant runtime
improvements (up to 5 orders of magnitude in our tests).

##  1 Introduction

Graphical models are a widely used theoretical framework that provides the
basis for many reasoning tasks both with probabilistic and deterministic
information Dechter (2013). These models employ graphs to concisely represent
the structure of the problem and the relations among variables.

One of the most important algorithms for exact reasoning on graphical models
is Bucket Elimination (BE) proposed by Dechter [1996; 2013], a general
approach based on the concept of _variable elimination_ that accommodates many
inference and optimization tasks, including _most probable explanation_ (MPE)
and _constrained optimization_. Solving these tasks is fundamental in real-
world applications domains such as genetic linkage analysis Fishelson and
Geiger (2002), protein side-chain interaction Yanover et al. (2008), and Earth
observation satellite management Bensana et al. (1999). BE is also a
fundamental component—the approximate version of BE Dechter (1997) is used to
compute the initial heuristic that guides the search—of all the AND/OR search
algorithms by Marinescu _et al_. [2007; 2009; 2014; 2015] that represent the
state of the art for exact MPE inference. On the other hand, BE is
characterized by memory requirements that grow _exponentially_ with respect to
the _induced width_ of the primal graph associated to the graphical model
Dechter (2013), severely hindering its applicability to large exact reasoning
tasks. As a consequence, several works have tried to mitigate this drawback
Dechter (1997); Bistaffa et al. (2017); Bistaffa and Farinelli (2018), but
none of these approaches really managed to overcome such a limitation. One of
the major reasons for such memory requirements is the fact that the functions
employed during BE’s execution are usually represented as _tables_ , whose
size is the product of the domains of the variables in the scope, regardless
of the actual values of such functions. This representation can lead to
storing many repeated values in the same table, causing a potential waste of
memory and other computational resources.

Against this background, in this paper we propose a function representation
specifically devised for exact MPE inference and constrained optimization
that, instead of the traditional mapping _variable assignment_ $\to$ _value_ ,
adopts a different approach that maps each value $v$ to the minimal _finite
state automaton_ Hopcroft and Ullman (1979) representing all the variable
assignments that are associated to $v$.

Compact function representations have already been investigated by different
works Srinivasan et al. (1990); Bahar et al. (1997); Chavira and Darwiche
(2007); Gogate and Domingos (2013), which have analyzed the potential benefits
of the use of different types of _decision diagrams_ from a theoretical point
of view. Nonetheless, as noted by Chavira and Darwiche [2007] the
effectiveness of these approaches has been limited in practice, because the
overhead they incur may very well outweigh any gains. Indeed, no approach
based on decision diagrams has ever been shown to outperform the current state
of the art, i.e., the AND/OR search algorithms by Marinescu _et al_. [2014;
2015].

To address the above-mentioned limitations, in this paper we propose the novel
use of automata theory techniques to efficiently represent and manipulate
functions in a compact way within our approach called FABE. By representing
each value only once, and by exploiting the well-known capabilities of
automata of compactly representing sets of strings (with a reduction that can
be _up to exponential_ with respect to a full table), we significantly improve
the performance of BE in terms of runtime and memory requirements. In more
detail, this paper advances the state of the art in the following ways:

  * •

We propose a function representation for exact MPE inference and constrained
optimization based on finite state automata, which we exploit within FABE.

  * •

Results on standard benchmark datasets show that FABE often outperforms the
current state of the art, with improvements of up to 5 orders of magnitude in
our tests.

  * •

Results also show that FABE outperforms the _structured message passing_ (SMP)
approach by Gogate and Domingos [2013], i.e., the most recent approach in the
literature based on decision diagrams.

  * •

Our work paves the way for an improved version of BE as a key component of
AND/OR search algorithms, in which the computation of the initial heuristic
can represent a bottleneck Kishimoto et al. (2015).

This paper is structured as follows. Section 2 provides the background on
graphical models and deterministic finite state automata. Section 3 positions
our approach _wrt_ existing literature. Section 4 presents our function
representation and how we exploit it within FABE. Section 5 presents our
experimental evaluation on standard benchmark datasets, in which we compare
FABE against the state of the art. Section 6 concludes the paper and outlines
future research directions.

##  2 Background

###  2.1 Graphical Models

_Graphical models_ (e.g., Bayesian Networks Pearl (1989), Markov Random Fields
Lauritzen (1996), and Cost Networks Dechter (2013)) capture the factorization
structure of a distribution over a set of $n$ variables. Formally, a graphical
model is a tuple
$\mathcal{M}=\left\langle\mathbf{X},\mathbf{D},\mathbf{F}\right\rangle$, where
$\mathbf{X}=\\{X_{i}:i\in V\\}$ is a set of variables indexed by set $V$ and
$\mathbf{D}=\\{D_{i}:i\in V\\}$ is the set of their finite domains of values.
$\mathbf{F}=\\{\psi_{\alpha}:\alpha\in F\\}$ is a set of discrete local
functions defined on subsets of variables, where $F\subseteq 2^{V}$ is a set
of variable subsets. We use $\alpha\subseteq V$ and
$\mathbf{X}_{\alpha}\subseteq\mathbf{X}$ to indicate the _scope_ of function
$\psi_{\alpha}$, i.e.,
$\mathbf{X}_{\alpha}=var(\psi_{\alpha})=\\{X_{i}:i\in\alpha\\}$. The function
scopes yield a _primal graph_ $G$ whose vertices are the variables and whose
edges connect any two variables that appear in the scope of the same function.
An important inference task that appears in many real-world applications is
MPE. MPE finds a complete assignment to the variables that has the highest
probability (i.e., a mode of the joint probability), namely:
$\mathbf{x}^{*}=\operatorname*{arg\,max}_{\mathbf{x}}\prod_{\alpha\in
F}\psi_{\alpha}(\mathbf{X}_{\alpha})$. The task is NP-hard Pearl (1989).
Another important task over deterministic graphical models (e.g., Cost
Networks) is the optimization task of finding an assignment or a configuration
to all the variables that minimizes the sum of the local functions, namely:
$\mathbf{x}^{*}=\operatorname*{arg\,min}_{\mathbf{x}}\sum_{\alpha\in
F}\psi_{\alpha}(\mathbf{X}_{\alpha})$. This is the task that has to be solved
in Weighted Constraint Satisfaction Problems (WCSPs). The task is NP-hard to
solve Dechter (2013).

To solve the above-mentioned tasks we consider the BE algorithm as discussed
by Dechter [2013] (Algorithm 1). BE is a general algorithm that can
accommodate several exact inference and optimization tasks over graphical
models. In this paper we focus on the version that can optimally solve the
above-mentioned MPE and optimization tasks. BE operates on the basis of a
_variable ordering_ $d$, which is used to partition the set of functions into
sets called _buckets_ , each associated with one variable of the graphical
model. Each function is placed in the bucket associated with the last bucket
that is associated with a variable in its scope. Then, buckets are processed
from last to first by means of two fundamental operations, i.e., _combination_
($\otimes\in\\{\prod,\sum\\}$) and _projection_
($\operatorname*{\Downarrow}\in\\{\max,\min\\}$). All the functions in
$bucket_{p}$, i.e., the current bucket, are combined with the $\otimes$
operation, and the result is the input of a $\operatorname*{\Downarrow}$
operation. Such an operation removes $X_{p}$ from the scope, producing a new
function $h_{p}$ that does not involve $X_{p}$, which is then placed in the
last bucket that is associated with a variable appearing in the scope of the
new function. To solve the MPE (resp. optimization) task, $\otimes=\prod$
(resp. $\sum$) and $\operatorname*{\Downarrow}=\max$ (resp. $\min$) operators
are used.

Algorithm 1 Bucket Elimination Dechter (2013)

1:A graphical model
$\mathcal{M}=\left\langle\mathbf{X},\mathbf{D},\mathbf{F}\right\rangle$, an
ordering $d$.

2:A max probability (resp. min cost) assignment.

3:Partition functions into buckets according to $d$.

4:Define $\psi_{i}$ as the $\otimes$ of $bucket_{i}$ associated with $X_{i}$.

5:for $p\leftarrow n$ down to 1 do

6: for $\psi_{p}$ and messages $h_{1},h_{2},\ldots,h_{j}$ in $bucket_{p}$ do

7:
$h_{p}\leftarrow\operatorname*{\Downarrow}_{X_{p}}(\psi_{p}\otimes\bigotimes_{i=1}^{j}h_{i})$.

8: Place $h_{p}$ into the largest index variable in its scope.

9:Assign maximizing (resp. minimizing) values in ordering $d$, consulting
functions in each bucket.

10:return Optimal solution value and assignment.

The computational complexity of the BE algorithm is directly determined by the
ordering $d$. Formally, BE’s time and space complexity are
$\mathcal{O}\left(r\cdot k^{w^{*}(d)+1}\right)$ and $\mathcal{O}\left(n\cdot
k^{w^{*}(d)}\right)$ respectively, where $k$ bounds the domain size, and
$w^{*}(d)$ is the induced width of its primal graph along $d$ Dechter (2013).
Hence, it is of utmost importance to adopt a variable ordering $d$ that
minimizes the induced width $w^{*}(d)$. The task of computing such ordering is
NP-complete, and, for this reason, a greedy procedure is usually adopted to
compute a variable ordering of acceptable quality. Several $metric(\cdot)$
functions have been proposed in the literature. One of the most widely used is
min-fill, such that $metric(X_{i})$ is the number of fill edges for $X_{i}$’s
parents in the primal graph Dechter (2013).

###  2.2 Deterministic Finite State Automata

Let $\Sigma$ denote a finite alphabet of characters and $\Sigma^{*}$ denote
the set of all strings over $\Sigma$. The size $\left|\Sigma\right|$ of
$\Sigma$ is the number of characters in $\Sigma$. A language over $\Sigma$ is
any subset of $\Sigma^{*}$. A Deterministic Finite State Automaton (DFSA)
Hopcroft and Ullman (1979) $\delta$ is specified by a tuple $\left\langle
Q,\Sigma,t,s,F\right\rangle$, where $Q$ is a finite set of states, $\Sigma$ is
an input alphabet, $t:Q\times\Sigma\to 2^{Q}$ is a transition function, $s\in
Q$ is the start state and $F\subseteq Q$ is a set of final states. A string
$x$ over $\Sigma$ is accepted (or recognized) by $\delta$ if there is a
labeled path from $s$ to a final state in $F$ such that this path spells out
the string $x$. Thus, the language $L_{\delta}$ of a DFSA $\delta$ is the set
of all strings that are spelled out by paths from $s$ to a final state in $F$.
It is well known that a general DFSA can accept an _infinite_ language (i.e.,
a infinite set of strings) Hopcroft and Ullman (1979). In this paper we focus
on Deterministic Acyclic Finite State Automata (DAFSA), i.e., DFSA whose
corresponding graph is a directed acyclic graph. In contrast with general
DFSA, DAFSA only accept _finite_ languages Daciuk (2002).

##  3 Related Work

In recent years, a strand of literature has investigated the use of different
algorithms on AND/OR search spaces, progressively showing the effectiveness of
these approaches for exact MPE inference and constrained optimization.
Specifically, _branch-and-bound_ (AOBB) Marinescu and Dechter (2009), _best-
first_ (AOBF) Marinescu and Dechter (2007), _recursive best-first_ (RBFAOO)
Kishimoto and Marinescu (2014) and _parallel recursive best-first_ (SPRBFAOO)
Kishimoto et al. (2015) algorithms have been proposed. To this day, RBFAOO
Kishimoto and Marinescu (2014) and SPRBFAOO Kishimoto et al. (2015) still
represent the state of the art for exact MPE inference, since, to the best of
our knowledge, no algorithms have been shown to outperform them in terms of
runtime. For this reason, we compare our approach against these two algorithms
in Section 5. All these approaches use the standard tabular representation to
store functions in memory. In the context of constrained optimization, the
only approach that tries to reduce the size of tables in memory is the one by
Bistaffa _et al_. [2017], which avoids representing _unfeasible_ assignments
during the solution of WCSPs with BE.

$10^{3}$$10^{4}$$10^{5}$$10^{6}$60708090100Total number of values in local
functionsRedundancy (%)pedigreegridproteinmastermindiscas89spot5 Figure 1:
Redundancy in MPE and WCSPs instances. Best viewed in colors.

The task of concisely representing functions for inference has been studied by
different works over the years. In the context of this work, the most closely
related strand of literature is concerned with the use of _decision diagrams_
to compactly represent knowledge. A decision diagram is a directed acyclic
graph that maps several decision nodes to two or more terminal nodes.
Different types of decision diagrams exist, depending on the domains of the
variables and the types of employed operations. Along these lines, several
works have proposed the use of Binary Decision Diagrams (BDDs) Gogate and
Domingos (2013), Algebraic Decision Diagrams (ADDs) Bahar et al. (1997),
affine ADDs Sanner and McAllester (2005), Multi-valued Decision Diagrams
(MDDs) Srinivasan et al. (1990); Chavira and Darwiche (2007) within variable
elimination and/or message passing algorithms for inference.

While it is true that DAFSA and decision diagrams are very closely related, to
the best of our knowledge the use of automata theory has never been
investigated in the context of concise function representation and inference.
In this sense, the use of DAFSA cannot be considered entirely novel (indeed, a
DAFSA can be considered equivalent to an MDD). On the other hand, our proposed
use of automata theory techniques for compilation Daciuk (2002), minimization
Bubenzer (2011), union Han and Salomaa (2008), and determinization Hopcroft
and Ullman (1979) is, as far as we know, entirely novel in the context of
inference on graphical models.

Moreover, as noted by Chavira and Darwiche [2007] the effectiveness of
approaches based on decision diagrams has been limited in practice, because
the overhead they incur may very well outweigh any gains. Indeed, no approach
based on any compact representations has ever been shown to outperform the
current state of the art, i.e., the AND/OR search algorithms by Marinescu _et
al_. [2014; 2015]. Against this background, we believe that our contribution,
i.e., to show that a new approach based on well-known theoretical concepts can
still be competitive with the current state of the art, can be very useful for
the scientific community.

Given the limited amount of available space, in this paper we decided to
compare FABE only with the SMP approach by Gogate and Domingos [2013], since
it is, to the best of our knowledge, the most recent and relevant one among
the above-mentioned works focusing on decision diagrams.111Our decision is
also motivated by the fact that, to the best of our knowledge, none of these
works has an available implementation. We also remark that, despite the
importance of considering this strand of literature, the current state of the
art is represented by more recent approaches based on completely different
techniques Kishimoto and Marinescu (2014); Kishimoto et al. (2015). Hence, our
evaluation in Section 5 is mainly devoted to the comparison against these
approaches.

The use of MDDs has also been investigated by Mateescu _et al_. [2008] within
the above-mentioned AND/OR search algorithms, but this approach has been
subsumed and outperformed by more recent and advanced approaches based on
AND/OR search trees, such as (SP)RBFAOO. For this reason, in Section 5 we only
compare with the most recent ones in such a strand of literature.222We cannot
directly compare with the approach by Mateescu _et al_. [2008] also because
its implementation is not publicly available.

_Lifted probabilistic inference_ (LPI) Kersting (2012) is also concerned with
reducing redundancy within probabilistic inference. Specifically, LPI tackles
redundancy _between different factors_ , whereas we tackle redundancy _inside
the same factor_. Assessing the effectiveness of the combined approach _wrt_
to the separate ones is a non-trivial research question, which will be
considered in future work. Finally, the approach by Demeulenaere _et al_.
[2016] aims at representing _compact tables_ by maintaining _generalized arc
consistency_ (i.e., by removing from domains all values that have no support
on a constraint) and not by minimizing redundancy due to repeated values, as
we explain in the next section.

##  4 A Novel DAFSA-based Version of BE

All the datasets commonly used as benchmarks for MPE Kishimoto et al. (2015)
and constrained optimization Marinescu and Dechter (2009) are characterized by
a very high _redundancy_ , i.e., many different variable assignments are
associated to the same value in the local functions. Figure 1 shows that the
value of redundancy for local functions (defined as $1-\frac{\text{number of
unique values}}{\text{total number of values}}$) for all MPE and WCSP
instances is always above 80% (except for smaller grid instances).

Furthermore, in probabilistic graphical models, local functions represent
probabilities with values in the interval $[0,1]$, which, in theory, contains
_infinite_ real values. In practice, such values are represented by _floating
point numbers_ that can only represent a _finite_ amount of values. Thus,
while a table $\psi$ has an arbitrarily large size that is the product of the
domains of the variables in its scope, in practice the maximum number of
unique values in $\psi$ is bounded by a parameter that depends on the
numerical representation. These remarks motivate the study of a novel concise
representation that exploits such a redundancy to reduce the amount of
computation. Notice that state of the art approaches for exact inference
Kishimoto et al. (2015) represent functions as _full tables_ , whose size is
the product of the domains of the variables in the scope.

In this paper we propose a way to represent functions by means of DAFSA, as
shown in the example in Figure 2. In the traditional way of representing
functions as tables, rows are indexed using variable assignments as _keys_
(Figure 2, left).

$v_{2}$$v_{1}$$v_{3}$$\psi$00$\ast$110101$\ast$0$X_{1}$$X_{2}$$X_{4}$ $X_{1}$ | $X_{2}$ | $X_{4}$ | $\psi$
---|---|---|---
0 | 0 | 0 | $v_{1}$
0 | 0 | 1 | $v_{1}$
0 | 1 | 0 | $v_{2}$
0 | 1 | 1 | $v_{1}$
1 | 0 | 0 | $v_{3}$
1 | 0 | 1 | $\infty$
1 | 1 | 0 | $v_{3}$
1 | 1 | 1 | $\infty$
Figure 2: Standard table (left) and corresponding DAFSA-based representation
(right). All variables are binary. Best viewed in colors.

In contrast, here we propose a novel approach that uses _values_ as keys
(Figure 2, right). Formally,

######  Definition 1.

Given a function $\psi$ that maps each possible assignment of the variables in
its scope to a value $v\in\mathbb{R}\cup\\{\infty\\}$,333We allow $\infty$ as
a possible value, since it can used to represent variable assignments that
violate hard constraints in WCSPs. we denote as $D(\psi)$ its corresponding
representation in terms of DAFSA. Formally, $D(\psi)=\\{(v,\delta)\\}$, where
$v$ is a value in $\psi$ and $\delta$ is the _minimal_ DAFSA that accepts all
the strings corresponding to the variable assignments that were mapped to $v$
in $\psi$. For the sake of simplicity, we do not represent the scope of the
function in $D(\psi)$, as we assume it is equal to $var(\psi)$. We label a
transition that accepts all the values of a variable’s domain as $\ast$.
Notice that each $\delta$ is acyclic because it accepts a finite language
Daciuk (2002).

######  Remark 1.

Given that values are employed as keys in our function representation, it is
crucial to ensure the absence of duplicates in such a set of keys, i.e., we
must be able to correctly determine whether two values $v_{1}$ and $v_{2}$ are
equal. While this is a trivial task in theory, in practice it can be very
tricky when $v_{1}$ and $v_{2}$ are floating point numbers representing real
values. Indeed, even if $v_{1}$ and $v_{2}$ are theoretically equal, their
floating point representations can differ due to numerical errors implicit in
floating point arithmetic, especially if $v_{1}$ and $v_{2}$ are the result of
a series of operations whose numerical errors have accumulated. To mitigate
this aspect, we use a well-known technique for comparing floating point
numbers known as _$\epsilon$ -comparison_, i.e., $v_{1}$ and $v_{2}$ are
considered equal if they differ by a quantity smaller than a small $\epsilon$.
While there exist more advanced techniques of tackling numerical issues
related to floating point arithmetic Higham (2002), they are well beyond the
scope of this paper. This should _not_ be considered as an approximation,
rather as a standard method to avoid the propagation of numerical errors.

A crucial property of DAFSA is that one path can accept multiple strings, or,
in our case, represent multiple variable assignments. In the example in Figure
2, the DAFSA corresponding to $v_{3}$ contains only one path, but it
represents both $\left\langle 1,0,0\right\rangle$ and $\left\langle
1,1,0\right\rangle$. By exploiting this property, our representation can reach
a reduction in terms of memory that is, in the best case, _up to_ exponential
_wrt_ the traditional table representation. We remark that memory is the main
bottleneck that limits the scalability of BE, hence reducing its memory
requirements is crucial, leading to significant improvements as shown by our
results in the experimental section. Finally, our representation allows one to
trivially avoid representing unfeasible assignments, similarly to Bistaffa et
al. (2017). Predicting the size (e.g., the number of states) of a minimal
DAFSA accepting a given set of strings remains, to the best of our knowledge,
an open problem, since it depends on the common prefixes/suffixes of the input
set.

A minimal DAFSA can be efficiently constructed from a set of assignments by
using the algorithm described by Daciuk [2002]. Since all the strings accepted
by each DAFSA are of the same length (equal to the cardinality of the scope of
the function), so are all the paths in the DAFSA. Thus, there is a mapping
between each edge at depth $i$ in each path and the $i$th variable in the
scope (see Figure 2). Without loss of generality, our representation always
maintains the variables in the scope ordered _wrt_ their natural ordering. We
now discuss our DAFSA-based version of BE, i.e., its $\otimes$ and
$\operatorname*{\Downarrow}$ operations.

###  4.1 A DAFSA-Based Version of $\otimes$

In order to better discuss our DAFSA-based version the $\otimes$ operation,
let us first recall how this operation works for traditional tabular functions
with an example (Figure 3).

$X_{1}$ | $X_{2}$ | $X_{4}$ | $\psi_{1}$
---|---|---|---
0 | 0 | 0 | $v_{1}$
0 | 0 | 1 | $v_{1}$
0 | 1 | 0 | $v_{2}$
0 | 1 | 1 | $v_{1}$
1 | 0 | 0 | $v_{3}$
1 | 0 | 1 | $\infty$
1 | 1 | 0 | $v_{3}$
1 | 1 | 1 | $\infty$
$X_{1}$ | $X_{2}$ | $X_{3}$ | $X_{4}$ | $\psi_{1\otimes 2}$
---|---|---|---|---
0 | 0 | 0 | 0 | $v_{1}\otimes v_{3}$
0 | 0 | 0 | 1 | $v_{1}\otimes v_{7}$
0 | 0 | 1 | 0 | $v_{1}\otimes v_{3}$
0 | 0 | 1 | 1 | $v_{1}\otimes v_{1}$
0 | 1 | 0 | 0 | $v_{2}\otimes v_{3}$
0 | 1 | 0 | 1 | $v_{1}\otimes v_{7}$
0 | 1 | 1 | 0 | $v_{2}\otimes v_{3}$
$\vdots$ | $\vdots$
$X_{3}$ | $X_{4}$ | $\psi_{2}$
---|---|---
0 | 0 | $v_{3}$
0 | 1 | $v_{7}$
1 | 0 | $v_{3}$
1 | 1 | $v_{1}$
$\otimes$$=$ Figure 3: An example of the $\otimes$ operation.

The result of the $\otimes$ operation is a new function whose scope is the
union of the scopes of the input functions, and in which the value of each
variable assignment is the $\otimes\in\\{\cdot,+\\}$ of the values of the
corresponding assignments (i.e., with the same assignments of the
corresponding variables) in the input functions. For example, the assignment
$\left\langle X_{1}=0,X_{2}=1,X_{3}=1,X_{4}=0\right\rangle$ in the result
table corresponds to $\left\langle X_{1}=0,X_{2}=1,X_{4}=0\right\rangle$ and
$\left\langle X_{3}=1,X_{4}=0\right\rangle$ in the input tables, hence its
value is $v_{2}\otimes v_{3}$. The $\otimes$ operation is closely related to
the _inner join_ of relational algebra.

To efficiently implement $D(\psi_{1})\otimes D(\psi_{2})$ we will make use of
the _intersection_ operation on automata Hopcroft and Ullman (1979).
Intuitively, the intersection of two automata accepting respectively $L_{1}$
and $L_{2}$ is an automaton that accepts $L_{1}\cap L_{2}$, i.e., all the
strings appearing both in $L_{1}$ and $L_{2}$. In our case, we will exploit
the intersection operation to identify all the corresponding variable
assignments in $D(\psi_{1})$ and $D(\psi_{2})$. To make this possible, we
first have to make sure that both functions have the same scope, so that
corresponding levels in $D(\psi_{1})$ and $D(\psi_{2})$ correspond to the same
variables. We achieve this by means of the AddLevels operation.

######  Definition 2.

Given two functions $D(\psi_{1})$ and $D(\psi_{2})$, the AddLevels operation
inserts (i) one or more levels labeled with $\ast$ in each DAFSA and (ii) one
or more variables in the respective scopes, in a way that the resulting scope
is $var(\psi_{1})\cup var(\psi_{2})$. Each level and variable is added so as
to maintain the scope ordered _wrt_ the variable ordering.

$v_{2}$$v_{1}$$v_{3}$$\psi_{1}$001$\ast$$\ast$$\ast$101$\ast$01$\ast$$\ast$0$X_{1}$$X_{2}$$X_{3}^{+}$$X_{4}$$v_{3}$$v_{1}$$v_{7}$$\psi_{2}$$\ast$$\ast$11$\ast$$\ast$$\ast$1$\ast$$\ast$01$X_{1}^{+}$$X_{2}^{+}$$X_{3}$$X_{4}$
Figure 4: The result of the AddLevels operation on $D(\psi_{1})$ and
$D(\psi_{2})$, where $\psi_{1}$ and $\psi_{2}$ are the tables in Figure 3.
Added levels and variables are denoted with dotted lines and + superscript.

Figure 4 shows an example of AddLevels. The operation of adding one level to a
DAFSA $\delta$ has a linear complexity _wrt_ the number of paths in $\delta$.
This has to be executed
$\left|D(\psi_{1})\right|\\!\cdot\\!\left|var(\psi_{2})\\!\setminus\\!var(\psi_{1})\right|\\!+\\!\left|D(\psi_{2})\right|\\!\cdot\\!\left|var(\psi_{1})\\!\setminus\\!var(\psi_{2})\right|$
times.

Our DAFSA-based $\otimes$ operation is implemented by Algorithm 2.
Intuitively, for each couple of values $(v_{i},v_{j})$, where $v_{i}$ and
$v_{j}$ are values in $D(\psi_{1})$ and $D(\psi_{2})$ respectively, we compute
the variable assignments associated to their $\otimes$ by computing the
intersection $\delta_{i}\cap\delta_{j}$ between the corresponding DAFSA
$\delta_{i}$ and $\delta_{j}$. The result is then associated to the value
$v_{i}\otimes v_{j}$ in the output function. We maintain only one entry for
each value $v_{i}\otimes v_{j}$ (see Remark 1 in this respect) by accumulating
(i.e., taking the union of) all the DAFSA that are associated to the same
value (Line 4).

Union and intersection over DAFSA have a time complexity of
$\mathcal{O}\left(nm\right)$ Han and Salomaa (2008), where $n$ and $m$ are the
number of states of the input automata. Depending on their implementations,
such operations may not directly produce a minimal DAFSA. Nonetheless, DAFSA
can be minimized in linear time _wrt_ the number of states with the algorithm
by Bubenzer [2011].

Algorithm 2 $D(\psi_{1})\otimes D(\psi_{2})$

1:$(D(\psi_{1})^{\prime},D(\psi_{2})^{\prime})=\textsc{AddLevels}(D(\psi_{1}),D(\psi_{2}))$.

2:for all $(v_{i},\delta_{i})\in D(\psi_{1})^{\prime},(v_{j},\delta_{j})\in
D(\psi_{2})^{\prime}$ do

3: if $\exists(v_{i}\otimes v_{j},\delta_{k})\in D(\psi_{1})\otimes
D(\psi_{2})$ then

4: $\delta_{k}=\delta_{k}\cup(\delta_{i}\cap\delta_{j})$.

5: else

6: Add $\\{(v_{i}\otimes v_{j},\delta_{i}\cap\delta_{j})\\}$ to
$D(\psi_{1})\otimes D(\psi_{2})$.

7:return $D(\psi_{1})\otimes D(\psi_{2})$.

###  4.2 A DAFSA-Based Version of $\operatorname*{\Downarrow}$

The $\operatorname*{\Downarrow}\in\\{\max,\min\\}$ operation effectively
realizes _variable elimination_ within the BE algorithm. Specifically,
$\operatorname*{\Downarrow}_{X_{i}}\psi$ removes $X_{i}$ from the scope of
$\psi$, and, from all the rows that possibly have equal variable assignments
as a result of the elimination of the column associated to $X_{i}$, it only
maintains the one with the $\max$ (in the case of MPE, or $\min$ in the case
of optimization) value. Like $\otimes$, $\operatorname*{\Downarrow}$ is also
related to a relational algebra operation, i.e., the _project_ operation. In
terms of SQL, $\operatorname*{\Downarrow}_{X_{i}}\psi$ is equivalent to SELECT
$var(\psi)\setminus X_{i},\max(\psi(\cdot))$ FROM $\psi$ GROUP BY
$var(\psi)\setminus X_{i}$, in the case of $\max$.

We realize the elimination of the column associated to $X_{i}$ with the
RemoveLevel operation, which can be intuitively thought of as the inverse of
AddLevels. Remove $\textsc{Level}(D(\psi),X_{i})$ removes $X_{i}$ from the
scope of $D(\psi)$ and collapses all the edges at the level associated to
$X_{i}$ from all the DAFSA in $D(\psi)$. RemoveLevel has similar computational
properties _wrt_ AddLevels, so we do not repeat the discussion due to space
limitations. Notice that the RemoveLevel operation could result in a _non-
deterministic_ automaton if the removal happens in correspondence of a
branching. Our approach takes this into account by using a determinization
algorithm Hopcroft and Ullman (1979).

In general, determinising an automaton could produce a growth (up to
exponential, in the worst case) of the number of states. On the other hand, in
all our experiments such a worst-case never happens and the growth factor is,
on average, only around 10%. Results confirm that such a growth does not
affect the overall performance of our approach, which is able to outperform
the competitors as described in Section 5.

We then implement the maximization (resp. minimization) of the values as
follows. Without loss of generality, we assume that the values
$v_{1},\ldots,v_{\left|D(\psi)\right|}$ are in decreasing (resp. increasing)
order. For each $(v_{i},\delta_{i})\in D(\psi)$, we subtract from $\delta_{i}$
all $\delta_{j}$ such that $v_{j}$ precedes $v_{i}$ in the above-mentioned
ordering (i.e., $v_{j}\geq v_{i}$, resp. $\leq$). In this way, we remove all
duplicate variable assignments and we ensure that each assignment is _only_
associated to the maximum (resp. minimum) value, correctly implementing the
$\operatorname*{\Downarrow}$ operation. Subtraction over DAFSA has a time
complexity of $\mathcal{O}\left(nm\right)$ Han and Salomaa (2008), where $n$
and $m$ are the number of states of the input automata. Algorithm 3 details
our $\operatorname*{\Downarrow}$ implementation.

Algorithm 3 $\operatorname*{\Downarrow}_{X_{i}}D(\psi)$

1:$D(\psi)^{\prime}=\textsc{RemoveLevel}(D(\psi),X_{i})$.

2:for all $(v_{i},\delta_{i})\in D(\psi)^{\prime}$ with decr. (resp. incr.)
$v_{i}$ do

3: $\delta_{i}=\delta_{i}\setminus\delta_{prec}$.

4: $\delta_{prec}=\delta_{prec}\cup\delta_{i}$.

5:return $D(\psi)^{\prime}$.

We remark that both our versions of $\otimes$ and $\operatorname*{\Downarrow}$
entirely operate on our concise representation, never expanding any function
to a full table. We directly employ our $\otimes$ and
$\operatorname*{\Downarrow}$ operations within Algorithm 1. We call our DAFSA-
based version of BE “Finite state Automata Bucket Elimination” (FABE). Since
the results of our $\otimes$ and $\operatorname*{\Downarrow}$ operations are
equivalent to the original ones, it follows that, as BE, FABE is also an exact
algorithm. Finally, we remark that our $\otimes$ and
$\operatorname*{\Downarrow}$ operations can directly be used within the
approximated version of BE, i.e., Mini-Bucket Elimination (MBE) Dechter
(1997).

protein | 1duw | 1hcz | 1fny | 2hft | 1ad2 | 1atg | 1qre | 1qhv | 1pbv | 1g3p | 2fcb | 1euo
---|---|---|---|---|---|---|---|---|---|---|---|---
FABE | $21.36$ | $10.33$ | $6.60$ | $322.33$ | $25.28$ | $3.28$ | $3.47$ | $16.54$ | $234.70$ | $1.21$ | $3.80$ | $39.81$
RBFAOO |  $>$ 2 h | $749.39$ |  $>$ 2 h | $1765.22$ | $1654.75$ | $1697.87$ | $734.85$ |  $>$ 2 h | $1543.11$ | $5080.64$ | $1677.44$ |  $>$ 2 h
SMP |  $>$ 2 h |  $>$ 2 h | $2036.29$ | $6569.95$ |  $>$ 2 h | $4098.89$ | $1721.50$ | $4376.94$ |  $>$ 2 h | $580.33$ | $6780.26$ | $1374.51$
toulbar | $25.89$ | $13.12$ | $8.09$ | $0.02$ | $25.75$ | $0.04$ | $6.87$ | $23.08$ | $0.05$ | $2.05$ | $3.97$ | $57.08$
pedigree | 25 | 30 | 39 | 18 | 31 | 34 | 51 | 9 | 13 | 7 | 41 | 37
FABE | $28.82$ | $7.23$ | $3.21$ | $7.42$ | $910.46$ | $8.83$ | $132.92$ | $473.94$ | $519.08$ | $21.79$ | $24.06$ | $6.73$
RBFAOO | $6.32$ | $61.34$ | $22.46$ | $20.11$ |  $>$ 2 h |  $>$ 2 h |  $>$ 2 h | $100.19$ |  $>$ 2 h | $323.77$ |  $>$ 2 h | $146.23$
SMP | $197.89$ | $40.86$ | $17.06$ | $40.89$ | $5881.66$ | $60.78$ | $789.65$ | $2040.32$ | $2011.26$ | $136.11$ | $151.40$ | $27.91$
toulbar | $5962.05$ | $581.43$ | $17.43$ | $166.29$ | $1505.02$ | $9.59$ |  $>$ 2 h |  $>$ 2 h | $623.89$ | $24.23$ | $727.16$ | $7.89$
grid | 90$\cdot$26$\cdot$5 | 90$\cdot$25$\cdot$5 | 90$\cdot$24$\cdot$5 | 75$\cdot$23$\cdot$5 | 90$\cdot$23$\cdot$5 | 75$\cdot$22$\cdot$5 | 90$\cdot$22$\cdot$5 | 75$\cdot$21$\cdot$5 | 90$\cdot$21$\cdot$5 | 50$\cdot$20$\cdot$5 | 75$\cdot$20$\cdot$5 | 90$\cdot$20$\cdot$5
FABE | $3192.15$ |  $>$ 2 h | $5112.09$ |  $>$ 2 h | $508.75$ |  $>$ 2 h | $4883.60$ |  $>$ 2 h | $142.23$ |  $>$ 2 h | $831.80$ | $267.50$
RBFAOO | $925.47$ | $902.19$ | $1758.19$ | $791.70$ | $158.17$ | $816.87$ | $20.37$ | $4.71$ | $8.22$ | $163.44$ | $19.01$ | $10.27$
SMP |  $>$ 2 h |  $>$ 2 h |  $>$ 2 h |  $>$ 2 h | $2453.45$ |  $>$ 2 h |  $>$ 2 h |  $>$ 2 h | $802.17$ |  $>$ 2 h | $3711.20$ | $946.07$
toulbar | $0.04$ | $0.07$ | $0.02$ | $1.68$ | $0.03$ | $1.44$ | $0.02$ | $0.20$ | $0.02$ | $1030.17$ | $0.10$ | $0.01$
Table 1: Runtime results (in seconds) on 12 largest MPE instances. Dataset |  protein |  pedigree |  grid
---|---|---|---
Average Redundancy |  96% |  85% |  64%
FABE speed-up _wrt_ RBFAOO |  $58.6$ (1%, 11%) |  $5.5$ (0%, 32%) |  $0.1$ (43%, 0%)
FABE speed-up _wrt_ SMP |  $1006.5$ (1%, 38%) |  $6.8$ (0%, 5%) |  $4.0$ (43%, 70%)
SPRBFAOO speed-up _wrt_ RBFAOO |  $\sim$7 |  $\sim$7 |  $\sim$5
FABE speed-up _wrt_ toulbar |  $1.0$ (1%, 0%) |  $20.6$ (0%, 23%) |  $0.0$ (43%, 0%)
Dataset |  spot5 |  mastermind |  iscas89
Average Redundancy |  85% |  85% |  87%
FABE speed-up _wrt_ RBFAOO |  $36.9$ (0%, 0%) |  $6.2$ (0%, 0%) |  $0.4$ (0%, 0%)
FABE speed-up _wrt_ SMP |  $5.8$ (0%, 0%) |  $2.5$ (0%, 0%) |  $5.1$ (0%, 0%)
FABE speed-up _wrt_ toulbar |  $10\,615.5$ (0%, 50%) |  $0.4$ (0%, 0%) |  $0.1$ (0%, 0%)
FABE speed-up _wrt_ CPLEX |  $2.0$ (0%, 0%) |  $7.2$ (0%, 0%) |  $0.8$ (0%, 0%)
FABE speed-up _wrt_ GUROBI |  $1.2$ (0%, 0%) |  $4.4$ (0%, 0%) |  $0.8$ (0%, 0%)
Table 2: Average speed-up results for MPE (top) and WCSP (bottom) instances.
For SPRBFAOO we report the same speed-up values reported by the authors
Kishimoto et al. (2015). Values in parentheses indicate the percentages of
instances unsolved by first and second approach.

##  5 Experiments

We evaluate FABE on standard benchmark datasets444Online at:
www.ics.uci.edu/~dechter/softwares/benchmarks. for exact MPE inference (i.e.,
protein, pedigree, grid) Kishimoto and Marinescu (2014); Kishimoto et al.
(2015) and WCSP (i.e., spot5, mastermind, iscas89) Marinescu and Dechter
(2009), comparing it with several state of the art approaches. For MPE, we
consider RBFAOO Kishimoto and Marinescu (2014) as our main competitor since it
has been empirically shown to be superior to other sequential algorithms for
exact MPE inference, namely AOBB Marinescu and Dechter (2009) and AOBF
Marinescu and Dechter (2007) (see Section 3). We cannot directly compare
against the _parallel_ version of RBFAOO, i.e., SPRBFAOO Kishimoto et al.
(2015), because its implementation has not been made public. We discarded the
option of re-implementing SPRBFAOO, as it would have probably led to an unfair
comparison due to a sub-optimal implementation. Nonetheless, since RBFAOO is
also used as a baseline for speed-up calculation in Kishimoto et al. (2015),
in Table 2 we compare our values of speed-up with the ones reported for
SPRBFAOO by its authors. As a second competitor we consider toulbar Hurley et
al. (2016), a widely used open-source solver used for exact optimization. We
also compare FABE against the SMP approach by Gogate and Domingos [2013] (see
associated discussion in Section 3). Since SMP relies on ADDs (which cannot
represent non-binary variables natively), we encode non-binary variables using
_one-hot_ encoding, following a standard practice. We do not show results
comparing FABE against the standard version of BE with tabular functions
Dechter (2013), since the latter runs out of memory on most of the instances.
For WCSPs we also compare against CPLEX and GUROBI, two off-the-shelf solvers
for constrained optimization.

FABE’s reported runtimes also include the compilation of automata. Since both
FABE and RBFAOO require an ordering $d$ (see Section 2), we consider this as
pre-processing and we do not include its runtime in the results (also because
it is negligible _wrt_ the solution phase). For each instance, we compute $d$
using a weighted Min-Fill heuristic Dechter (2013), and we use the same $d$
for both algorithms.

We execute RBFAOO with the parameters detailed in authors’ previous work
Kishimoto and Marinescu (2014); Kishimoto et al. (2015), including cache size
and $i$ parameter. Every other approach is executed with default parameter
values. Following Kishimoto et al. (2015), we set a time limit of 2 hours. We
exclude from our analysis all instances that could not be solved by any
algorithm in the considered time limit. FABE and SMP are implemented in
C++.555Code available at https://github.com/filippobistaffa/FABE. We employ
the implementations of RBFAOO and toulbar provided by the authors. All
experiments have been run on a cluster whose computing nodes have 2.50GHz CPUs
and 384 GBytes of RAM. As for Remark 1, for FABE we consider
$\epsilon\\!=\\!10^{-10}$.

Given the large number of instances in MPE datasets, in Table 1 we report the
runtimes on the 12 largest instances _wrt_ the number of variables. In Table 2
we report the aggregated results of the speed-ups achieved by FABE _wrt_ other
approaches, calculated considering the instances where both algorithms
terminate within the time limit.

###  5.1 Summary of Results

Results confirm that FABE’s performance depends on the degree of redundancy.
FABE obtains good performance on the protein and pedigree datasets, achieving
speed-ups of $\sim$1–2 orders of magnitude, and solving a total of 34
instances that RBFAOO could not solve. We also observe that toulbar is
superior on a handful of protein instances and on the grid dataset, which is
characterized by low redundancy. Results also show that, despite not employing
parallelism, FABE’s speed-up on the protein dataset is much higher than the
one reported for SPRBFAOO, while it is comparable on the pedigree datasets.

As for WCSPs (detailed results in Table 3), FABE outperforms all competitors
on the spot5 dataset, notably achieving a speed-up of 5 orders of magnitude
_wrt_ toulbar. On the mastermind dataset, FABE is comparable with toulbar
(since both compute solutions in tenths of seconds) except for
3$\cdot$8$\cdot$5 and 10$\cdot$8$\cdot$3 instances, but it is, on average,
better than every other competitor. We also observe that toulbar is clearly
superior on the iscas89 dataset.

Finally, FABE consistently outperforms SMP using one-hot encoding, confirming
that the use of additional encodings (required by the presence of non-binary
variables that cannot be represented by ADDs) introduces a significant
overhead compared to our representation using DAFSA, which can natively
represent non-binary variables. Such an impact is more pronounced on datasets
with larger variable domains. Indeed, FABE obtains a speed-up of 3 orders of
magnitude on the protein dataset, where variables reach a domain of 81.

##  6 Conclusions

We proposed FABE, an algorithm for exact MPE and constrained optimization that
exploits our function representation based on DAFSA. Results obtained
following an established methodology confirm the efficacy of our
representation.

Future research directions include extending FABE to marginal inference tasks
and integrating FABE to compute the initial heuristic for AND/OR search
algorithms, which, at the moment, use the table-based implementation of BE.
The computation of such an heuristic represents a bottleneck for high values
of $i$, as acknowledged in Kishimoto et al. (2015). A faster version of MBE
could represent an important contribution, allowing one to employ more precise
heuristics and, thus, improving the performance of the AND/OR search.

spot5 | 42b | 505b | 408b | 29 | 503 | 54
---|---|---|---|---|---|---
FABE | $0.26$ | $0.26$ | $0.29$ | $0.09$ | $0.05$ | $0.07$
RBFAOO | $13.37$ | $10.27$ | $9.97$ | $5.61$ | $1.37$ | $1.36$
SMP | $1.62$ | $1.80$ | $1.60$ | $0.72$ | $0.27$ | $0.30$
CPLEX | $0.35$ | $0.34$ | $0.39$ | $0.37$ | $0.10$ | $0.18$
GUROBI | $0.38$ | $0.40$ | $0.41$ | $0.13$ | $0.25$ | $0.21$
toulbar |  $>$ 2 h |  $>$ 2 h |  $>$ 2 h | $0.10$ | $1957.80$ | $0.09$
master. | 3$\cdot$8$\cdot$5 | 10$\cdot$8$\cdot$3 | 4$\cdot$8$\cdot$4 | 3$\cdot$8$\cdot$4 | 4$\cdot$8$\cdot$3 | 3$\cdot$8$\cdot$3
FABE | $247.27$ | $69.30$ | $0.36$ | $0.22$ | $0.10$ | $0.06$
RBFAOO | $4.93$ | $3.01$ | $2.96$ | $1.96$ | $0.85$ | $0.68$
SMP | $659.42$ | $185.45$ | $0.95$ | $0.43$ | $0.29$ | $0.11$
CPLEX | $3.26$ | $0.66$ | $1.26$ | $0.67$ | $1.54$ | $1.28$
GUROBI | $1.77$ | $0.66$ | $0.72$ | $0.51$ | $0.97$ | $0.75$
toulbar | $0.18$ | $0.09$ | $0.09$ | $0.12$ | $0.05$ | $0.06$
iscas89 | s1238 | c880 | s1196 | s953 | s1494 | s1488
FABE | $38.50$ | $25.36$ | $73.54$ | $286.43$ | $1.42$ | $1.12$
RBFAOO | $1.47$ | $1.17$ | $0.61$ | $0.54$ | $0.41$ | $0.39$
SMP | $229.64$ | $146.43$ | $410.96$ | $1464.98$ | $9.78$ | $6.02$
CPLEX | $0.19$ | $0.20$ | $0.09$ | $0.19$ | $0.28$ | $0.23$
GUROBI | $0.17$ | $0.14$ | $0.09$ | $0.15$ | $0.26$ | $0.17$
toulbar | $0.04$ | $0.06$ | $0.04$ | $0.04$ | $0.04$ | $0.07$
Table 3: Runtime results (in seconds) on WCSP instances.

## Ethical Statement

There are no ethical issues.

## Acknowledgments

The author was supported by the “YOMA Operational Research” project funded by
the Botnar Foundation. The author gratefully acknowledges the computer
resources at Artemisa, funded by the European Union ERDF and Comunitat
Valenciana as well as the technical support provided by the Instituto de
Fisica Corpuscular, IFIC (CSIC-UV).

## References

  * Bahar et al. [1997] Iris Bahar, Erica Frohm, Charles Gaona, Gary Hachtel, Enrico Macii, Abelardo Pardo, and Fabio Somenzi.  Algebric decision diagrams and their applications.  Formal Methods in System Design, 10(2):171–206, 1997.
  * Bensana et al. [1999] Eric Bensana, Michel Lemaitre, and Gerard Verfaillie.  Earth observation satellite management.  Constraints, 4(3):293–299, 1999.
  * Bistaffa and Farinelli [2018] Filippo Bistaffa and Alessandro Farinelli.  A COP model for graph-constrained coalition formation.  Journal of Artificial Intelligence Research, 62:133–153, 2018.
  * Bistaffa et al. [2017] Filippo Bistaffa, Nicola Bombieri, and Alessandro Farinelli.  An efficient approach for accelerating bucket elimination on GPUs.  IEEE Transactions on Cybernetics, 47(11):3967–3979, 2017.
  * Bubenzer [2011] Johannes Bubenzer.  Minimization of acyclic DFAs.  In Prague Stringology Conference, pages 132–146, 2011.
  * Chavira and Darwiche [2007] Mark Chavira and Adnan Darwiche.  Compiling Bayesian networks using variable elimination.  In International Joint Conference on Artificial Intelligence (IJCAI), pages 2443–2449, 2007.
  * Daciuk [2002] Jan Daciuk.  Comparison of construction algorithms for minimal, acyclic, deterministic, finite-state automata from sets of strings.  In International Conference on Implementation and Application of Automata, pages 255–261, 2002.
  * Dechter [1996] Rina Dechter.  Bucket elimination: A unifying framework for probabilistic inference.  In Conference on Uncertainty in Artificial Intelligence (UAI), pages 211–219, 1996.
  * Dechter [1997] Rina Dechter.  Mini-buckets: A general scheme for generating approximations in automated reasoning.  In International Joint Conference on Artificial Intelligence (IJCAI), pages 1297–1303, 1997.
  * Dechter [2013] Rina Dechter.  Reasoning with Probabilistic and Deterministic Graphical Models: Exact Algorithms.  Synthesis Lectures on Artificial Intelligence and Machine Learning. Morgan & Claypool Publishers, 2013.
  * Demeulenaere et al. [2016] Jordan Demeulenaere, Renaud Hartert, Christophe Lecoutre, Guillaume Perez, Laurent Perron, Jean-Charles Régin, and Pierre Schaus.  Compact-table: efficiently filtering table constraints with reversible sparse bit-sets.  In International Conference on Principles and Practice of Constraint Programming (CP), pages 207–223. Springer, 2016.
  * Fishelson and Geiger [2002] Maáyan Fishelson and Dan Geiger.  Exact genetic linkage computations for general pedigrees.  Bioinformatics, 18(suppl_1):S189–S198, 2002.
  * Gogate and Domingos [2013] Vibhav Gogate and Pedro Domingos.  Structured message passing.  In Conference on Uncertainty in Artificial Intelligence (UAI), page 252–261, 2013.
  * Han and Salomaa [2008] Yo-Sub Han and Kai Salomaa.  State complexity of union and intersection of finite languages.  International Journal of Foundations of Computer Science, 19(03):581–595, 2008.
  * Higham [2002] Nicholas Higham.  Accuracy and Stability of Numerical Algorithms.  Siam, 2002.
  * Hopcroft and Ullman [1979] John Hopcroft and Jeffrey Ullman.  Introduction to Automata Theory, Languages and Computation.  Addison-Wesley, 1979.
  * Hurley et al. [2016] Barry Hurley, Barry O’Sullivan, David Allouche, George Katsirelos, Thomas Schiex, Matthias Zytnicki, and Simon De Givry.  Multi-language evaluation of exact solvers in graphical model discrete optimization.  Constraints, 21(3):413–434, 2016.
  * Kersting [2012] Kristian Kersting.  Lifted probabilistic inference.  In European Conference on Artificial Intelligence (ECAI), pages 33–38, 2012.
  * Kishimoto and Marinescu [2014] Akihiro Kishimoto and Radu Marinescu.  Recursive best-first AND/OR search for optimization in graphical models.  In Conference on Uncertainty in Artificial Intelligence (UAI), pages 400–409, 2014.
  * Kishimoto et al. [2015] Akihiro Kishimoto, Radu Marinescu, and Adi Botea.  Parallel recursive best-first AND/OR search for exact MAP inference in graphical models.  In Conference on Neural Information Processing Systems (NeurIPS), pages 928–936, 2015.
  * Lauritzen [1996] Steffen Lauritzen.  Graphical models.  Clarendon Press, 1996.
  * Marinescu and Dechter [2007] Radu Marinescu and Rina Dechter.  Best-first AND/OR search for graphical models.  In AAAI Conference on Artificial Intelligence (AAAI), pages 1171–1176, 2007.
  * Marinescu and Dechter [2009] Radu Marinescu and Rina Dechter.  AND/OR branch-and-bound search for combinatorial optimization in graphical models.  Artificial Intelligence, 173(16-17):1457–1491, 2009.
  * Mateescu et al. [2008] Robert Mateescu, Rina Dechter, and Radu Marinescu.  AND/OR multi-valued decision diagrams (AOMDDs) for graphical models.  Journal of Artificial Intelligence Research, 33:465–519, 2008.
  * Pearl [1989] Judea Pearl.  Probabilistic Reasoning in Intelligent Systems.  Morgan Kaufmann, 1989.
  * Sanner and McAllester [2005] Scott Sanner and David McAllester.  Affine algebraic decision diagrams (AADDs) and their application to structured probabilistic inference.  In International Joint Conference on Artificial Intelligence (IJCAI), pages 1384–1390, 2005.
  * Srinivasan et al. [1990] Arvind Srinivasan, Timothy Ham, Sharad Malik, and Robert Brayton.  Algorithms for discrete function manipulation.  In International Conference on Computer-Aided Design (ICCAD), pages 92–93, 1990.
  * Yanover et al. [2008] Chen Yanover, Ora Schueler-Furman, and Yair Weiss.  Minimizing and learning energy functions for side-chain prediction.  Journal of Computational Biology, 15(7):899–911, 2008.


# LLM-Based Cooperative Agents using Information Relevance and Plan Validation

SeungWon Seo
Department of Artificial Intelligence
Kyung Hee University
Yongin, South Korea
<EMAIL_ADDRESS>
Junhyeok Lee
Department of Software Convergence
Kyung Hee University
Yongin, South Korea
<EMAIL_ADDRESS>
SeongRae Noh
Department of Artificial Intelligence
Kyung Hee University
Yongin, South Korea
<EMAIL_ADDRESS>
HyeongYeop Kang
Department of Software Convergence
Kyung Hee University
Yongin, South Korea
<EMAIL_ADDRESS>
Corresponding author<EMAIL_ADDRESS>
###### Abstract

We address the challenge of multi-agent cooperation, where agents achieve a
common goal by interacting with a 3D scene and cooperating with decentralized
agents under complex partial observations. This involves managing
communication costs and optimizing interaction trajectories in dynamic
environments. Our research focuses on three primary limitations of existing
cooperative agent systems. Firstly, current systems demonstrate inefficiency
in managing acquired information through observation, resulting in declining
planning performance as the environment becomes more complex with additional
objects or goals. Secondly, the neglect of false plans in partially observable
settings leads to suboptimal cooperative performance, as agents struggle to
adapt to environmental changes influenced by the unseen actions of other
agents. Lastly, the failure to incorporate spatial data into decision-making
processes restricts the agent’s ability to construct optimized trajectories.
To overcome these limitations, we propose the RElevance and Validation-
Enhanced Cooperative Language Agent (REVECA), a novel cognitive architecture
powered by GPT-3.5. REVECA leverages relevance assessment, plan validation,
and spatial information to enhance the efficiency and robustness of agent
cooperation in dynamic and partially observable environments while minimizing
continuous communication costs and effectively managing irrelevant dummy
objects. Our extensive experiments demonstrate the superiority of REVECA over
previous approaches, including those driven by GPT-4.0. Additionally, a user
study highlights REVECA’s potential for achieving trustworthy human-AI
cooperation. We expect that REVECA will have significant applications in
gaming, XR applications, educational tools, and humanoid robots, contributing
to substantial economic, commercial, and academic advancements.

_K_ eywords Multi-agent planning $\cdot$ Cooperative agent $\cdot$ Dynamic
environments $\cdot$ Large Language Models

##  1 Introduction

Digital agents collaborating with humans are crucial in games, educational
platforms, and virtual universes. Known as Non-Player Characters (NPCs), these
agents enhance user immersion in commercial applications but often operate on
pre-scripted behaviors, limiting adaptability and resulting in repetitive
actions. In games like World of Warcraft and Diablo, NPCs who must be escorted
by the player often fail to comprehend the situational context, rushing into
danger and creating challenges for players. This lack of adaptive intelligence
detracts from the gaming experience, highlighting the need for advanced AI-
driven agents.

Recently, OpenAI showcased an AGI Robot using large language models (LLMs) for
recognition of natural language and household tasks. Inspired by this, we aim
to create adaptive, intelligent cooperative agents. By facilitating natural
language interactions, high-level planning, and scene-dedicated low-level
controllers, these LLM-based agents will address cooperative problems more
effectively than traditional methods relying on static, learnable models or
reinforcement learning.

This paper introduces REVECA, a RElevance and Validation-Enhanced Cooperative
Language Agent, an LLM-based agent framework addressing decentralized control,
costly communication, complex tasks, partially observable environments, and
noisy settings. Similar to prior work [1], we focus on multi-objective
household tasks using well-constructed virtual settings. Specifically, we
focus on two decentralized agents cooperating on a multi-objective, long-
horizon household task under complex partial observations. Additionally,
continuous communication incurs time costs, and irrelevant dummy objects add
noise, complicating the environment.

The primary advancements of REVECA over previous works are threefold. Firstly,
REVECA leverages LLMs to assess the relevance of newly acquired information
before storage, prioritizing it and reducing reasoning complexity for
planning. Previous research [1, 2] stored all information in memory, leading
to performance declines due to increasing memory requirements, limited context
length, and intensifying reasoning complexity. Some studies [3, 4] used queues
to retain recent $K$ pieces of information, but this resulted in suboptimal
planning due to the limited historical information.

Secondly, REVECA uses a novel modular cognitive architecture to mitigate false
planning. This occurs in partially observable environments because changes
induced by collaborators are not immediately reflected in the agent’s memory.
Traditional approaches [5] update information via constant pre-task
communication, which is costly. REVECA’s Validation Module checks plan
validity by assessing information relevance and estimating collaborators’
recent plans, enabling communication only when necessary and improving
efficiency and effectiveness.

Lastly, REVECA excels in planning by incorporating spatial information.
Previous studies often neglected spatial information due to its integration
challenge in language models. Although some studies [1, 3] have attempted to
incorporate spatial information through image or text representations, they
did not report performance improvements. We attempt to address this by
considering the spatial distance between agents and objects in LLM reasoning
processes. By employing a prompting technique, that effectively integrates
numerical distances, REVECA enhances the cooperative performance.

We conducted comparative analysis, ablation studies, and user studies, using
three multi-room simulation environments: Communicative Watch-And-Help
(C-WAH), ThreeDWorld Multi-Agent Transport (TDW-MAT), and Noisy-C-WAH. Noisy-
C-WAH, a variant of C-WAH with dummy obstacles, tested REVECA in noisy
settings. Results show that REVECA achieves higher success rates, efficiency,
and robustness than recent studies.

In summary, our main contributions are as follows:

  * •

Addressed cooperative challenges: decentralized control, costly communication,
complex long-horizon tasks, partially observable environments, and noisy
multi-object settings.

  * •

Developed an LLM-based relevance estimation method for optimal planning and
robustness in noisy environments.

  * •

Introduced an agent framework that validates plans and incorporates spatial
information for mitigating false planning.

  * •

Conducted extensive evaluations that show REVECA’s superior performance over
previous studies in C-WAH, TDW-MAT, and Noisy-C-WAH.

  * •

Performed a user study demonstrating potential trustworthy human-AI
cooperation.

##  2 Related Work

Research on cooperative agents has a long history [6, 7]. The traditional
cooperative agent has been studied across various directions, mainly
leveraging reinforcement learning technique [8, 9, 10, 11, 12, 13, 14, 15, 16,
17, 18, 19, 20, 21, 22, 23, 24, 25]. These approaches have facilitated the
development of agents that can autonomously learn to cooperate by maximizing
cumulative rewards through trial and error in various simulated settings.
Notable studies have explored aspects such as visual reinforcement learning
for navigation and interaction [8], mapping state spaces to actions
effectively [9], and enhancing the robustness of learning algorithms in multi-
agent systems [10].

Some other researchers have aimed to develop platforms to test cooperative
agents [26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37]. These provide
standardized environments to benchmark the performance and generalization
capabilities of the agents.

However, a significant limitation of previous work is the lack of support for
natural language-based communication between agents [38, 39, 40, 11, 30, 34].
The effective communication is crucial for enhancing collaboration, especially
in complex, multi-agent environments. Natural language processing capabilities
enable agents to exchange information in a more intuitive and human-like
manner.

LLMs have recently attracted significant interest in both academia and
industry, also gaining attention in the field of agents [41, 42]. The common-
sense reasoning capabilities and natural language processing abilities of LLMs
have contributed to enhancing the agent’s decision-making [13, 43, 44, 45, 46,
47, 48] and planning [49, 50, 51, 52, 53, 5, 54] abilities.

Recent studies on LLM-based embodied agents [1, 3, 2, 4] represent a
significant step forward in this field. These agents utilize LLMs for
understanding the environment, planning tasks, and communicating with human
users and other agents. However, existing studies face suboptimal performance
due to issues with LLMs, such as inadequate spatial data processing
capabilities [55], performance degradation with large input data [56], and
insufficient reasoning abilities with complex reasoning tasks [57].

This paper introduces REVECA, an LLM-based embodied agent framework designed
to address the limitations of the previous works by leveraging information
relevance, plan validation, and effective communication strategies.

##  3 Problem Definition

The problem we focus on is an extension of the decentralized partially
observable Markov decision process (DEC-POMDP) [58, 59, 60, 10, 1, 4],
characterized by the tuple
$(n,S,\\{\Sigma_{i}\\},\\{A_{i}\\},\\{O_{i}\\},T,G,h)$. Here, $n$ represents
the number of agents; $S$ denotes a finite set of states; $A_{i}=A^{W}_{i}\cup
A^{C}_{i}$ denotes the action set for agent $i$, comprising a finite set of
world actions $A^{W}_{i}$ and a communication action $A^{C}_{i}$ to send a
message $\sigma_{i}\in\Sigma_{i}$. The observation set for agent $i$,
$O_{i}=O^{W}_{i}\times O^{C}_{i}$, comprises world observations $O^{W}_{i}$
and the set of possible messages the agent can receive from teammates
$O^{C}_{i}=\Sigma_{1}\times\cdots\times\Sigma_{n}$. The joint transition
model, $T(s,a,s^{\prime})=p(s^{\prime}\mid s,a)$, defines the probability of
transitioning to a new state $s^{\prime}\in S$ after taking joint action $a\in
A_{1}\times\cdots\times A_{n}$ in state $s\in S$. The set
$G=\\{g_{1},\ldots,g_{k}\\}$ defines the goal with several sub-goals for the
agents to complete. Decentralized agents, starting from an initial state
$s_{0}$, must plan and execute actions to reach the goal $G$ as efficiently as
possible within the planning horizon $h$, based on partial observations that
guide their decision-making processes.

This paper focuses on a scenario where two decentralized intelligent agents
collaborate on a long-horizon rearrangement task [61] within an indoor multi-
room environment, utilizing noise-free broadcast communication. While the
focus is on two agents, the methods and experiments are generalizable to
scenarios with more agents. The agents can perform navigation actions,
interaction actions, and communication actions. The task includes several
predicates $g_{i}$ with specified counts, such as $IN(cupcake,fridge):2$,
which represents the sub-task of placing two cupcakes in the fridge.

Figure 1: The interaction flow between the six modules of REVECA and the
environment.  Figure 2: An example scenario demonstrating REVECA’s
comprehensive operational flow, highlighting the interaction between various
modules, collaborators, and the environment to achieve a common goal.

##  4 REVECA framework

Our framework comprises six key modules: Communication Module, Observation
Module, Memory Module, Planning Module, Validation Module, and Execution
Module. Communication Module facilitates natural language-based information
sharing. Observation Module gathers and categorizes information into four
relevance levels while the agent explores the environment. Memory Module
comprises six components: common goal, communication history, scene
observation history, self-information history, collaborators-information
history, and a low-level action skill book. It is responsible for storing and
updating data. Planning Module employs memory data to generate efficient
plans, considering information relevancy, predicted proximity of all agents,
and collaborators’ information history. Validation Module checks for false
plans by generating and confirming collaborators’ possible interaction
scenarios between observation and planning times, then discards and
reformulates plans if needed. Execution Module executes validated plans using
the low-level action skill book. The modular design of REVECA is illustrated
in Figure 1 and an example scenario presenting REVECA’s workflow is depicted
in Figure 2.

Figure 3: Four cases when the Communication Module is invoked: (a) Simulation
Initiation. (b) Validation Requests. (c) Response to Validation Requests. (d)
Sub-goal Achievement.

###  4.1 Communication for information sharing

The Communication Module, facilitating natural language information sharing,
is invoked in four cases. 1) Simulation Initiation: Agents exchange initial
information about their locations and surrounding objects. 2) Validation
Requests: Agents query about task history. 3) Response to Validation Requests:
Agents provide task completion history. 4) Sub-goal Achievement: Agents
announce sub-goal completion. The detailed illustrations for each case are
presented in Figure 3.

Figure 4: An example of determining the relevance score for scene information.
If the common goal is to put milk in the fridge, the fridge and milk have
strong relevance. Since the milk could also be placed in containers, the
drawer and cabinet are estimated to have a moderate relevance.

###  4.2 Observation-time: Relevance Estimation and Storage

During observation time, agents acquire four types of information: scene,
self-agent, communication, and collaborator-agent. Scene information includes
object details like 3D position, ID, name, room, and interactions. Self-agent
information includes the held object, current position, and completed plan
history. These are obtained at every simulation step. Communication
information, conveyed in natural language, is obtained when it occurs.
Collaborator-agent information is acquired when communicating with or seeing a
specific agent. It includes the same details as self-agent information.

Scene and communication information are stored in scene observation history
and communication history, respectively, with four relevance levels (strong,
medium, low, none) assessed by LLMs. This prioritizes information, avoiding
the need to re-reference all memory entries and reducing the reasoning
complexity during the LLM-based planning process. An example of determining
the relevance score for scene information is depicted in Figure 4.

Self-agent information, which is fully observable, is directly stored in self-
information history. Conversely, collaborator-agent information, which is
acquired discontinuously, is interpolated to address gaps before being stored
in collaborators-information history.

Figure 5: The two-step planning procedure of REVECA. In the first step, a set
of $K=3$ plans are created, each plan evaluated for proximity and relevance.
The second step involves reasoning through these plans using the LLM with
chain-of-thought prompting. The LLM evaluates the plans based on input data,
including self-information and collaborator information, recommending the most
efficient action.

###  4.3 Planning-time: Real-Time Adaptation

Existing research on agent-based simulations [62, 63, 64, 65] often constructs
sequential long-term plans for specific goals, effective in individual tasks
where the agent is the sole entity influencing the environment and in
centralized settings where a manager oversees the environment. However, in
decentralized cooperative tasks within partially observable environments,
agents must dynamically adapt their plans to changes, as long-term plans
devised at earlier stages can become impractical and lead to false plans.

To address this, we propose a Planning Module that devises the next optimal
action at each decision point, both at the start of the simulation and
following the execution of each action. It starts with creating $K$ plans
based on information relevance and relative proximity of collaborators. LLMs
then utilize zero-shot chain-of-thought prompting [66] to select the optimal
plan, prioritizing tasks based on relevance, self-information, and
collaborators’ information. This approach implicitly guides the planning
process to prioritize tasks that are crucial for achieving the goal while
ensuring the agent’s actions are more efficient than those of its
collaborators. This two-step planning procedure is depicted in Figure 5.

Figure 6: Demonstrates how REVECA’s Validation Module enhances collaboration
between Alice and Bob. The action history indicates which actions Alice knows
about and which are unknown to her. Without validation, Alice’s plan fails due
to missing information about Bob’s actions. When the Validation Module is
used, Alice communicates with Bob, confirming the status of the milk and
successfully completing the task by grabbing the cupcake.

###  4.4 Validation-time: Scenario-based Validation

Even a well-constructed plan may become invalid due to the environmental
changes caused by collaborators during the interval between observation and
planning. In partially observable environments, determining whether such
changes have occurred is challenging for the agent.

A straightforward method to resolve this is to revisit the object’s location
or query all collaborators about their interactions. However, this can result
in inefficient path planning and incur significant communication costs.

To address this, REVECA includes scenario-based plan validation, estimating
plan validity using stored information. The agent generates all possible
scenarios for the object’s interactions with collaborators between the
observation and planning times. The agent then uses collaborator information
from its Memory Module to ask the LLM to determine the most likely scenario
employing the zero-shot chain-of-thought prompting technique [66]. If the
scenario where no collaborator interacted with the object is most likely, the
agent assumes the plan is valid. If another scenario is likely, the agent
communicates with the collaborator to confirm the interaction. If confirmed,
the agent discards the original plan, creates a new one, and repeats the
scenario-based validation. The scenarios with and without the Validation
Module are shown in Figure 6.

###  4.5 Executing Navigation and Contextual Actions

After the plan is determined, the Execution Module retrieves sub-task
information from the Memory Module to identify the target location. We use the
A-star search algorithm for efficient pathfinding. Upon approaching the
object, the agent retrieves a predefined animation from the low-level action
skill book to execute the planned interaction.

Figure 7: The layouts of the two virtual environments used in the REVECA
experiments. (a) C-WAH. (b) TDW-MAT.

##  5 Experiment

###  5.1 Experimental Settings

We conducted experiments using three types of indoor multi-room simulation
environments: C-WAH, TDW-MAT [1], and Noisy-C-WAH. To ensure a fair
comparison, we adopted the detailed parameters defined in the previous study’s
settings [1].

C-WAH [1], an extended version of the Watch-And-Help Challenge [34], is built
on the realistic multi-agent simulation platform, VirtualHome [67]. This
environment includes five household tasks, such as setting the table and doing
the dishes, forming the common goal. Our experiments consist of 10 episodes,
each with five different household tasks across two test environments. In
C-WAH, agents can acquire or provide information through communication with
other agents while executing instructions. When an agent enters a specific
room, it can observe all objects not inside a container like fridges or
microwaves. To observe objects inside containers, the agent is required an
additional action of opening containers. Agents are limited to using up to 500
characters per frame to mimic real-world communication costs. Horizon $h$ is
set to 250 steps, and each task includes 3 to 5 subgoals (or objects). Failing
to achieve the common goal within the 250 steps results in an episode failure.
The layout is shown in Figure 7(a).

TDW-MAT, an extended version of the ThreeDWorld Transport Challenge [68], is
built on the TDW [69]. It features more natural object placements and a
variety of objects and containers that assist in transporting items. The
common goals involve transporting items in two categories: Food and Stuff.
Each episode includes 10 target objects, and 2 to 5 containers are placed to
facilitate moving multiple items simultaneously. Unlike C-WAH, agents in TDW-
MAT cannot obtain complete room information without performing a 360-degree
rotation in 15-degree increments. Communication is limited to 500 characters
per frame, and $h$ is set to 3,000 steps. The layout is shown in Figure 7(b).

Noisy-C-WAH is a customized version of C-WAH augmented with an additional 10
or 20 dummy objects per episode to demonstrate the robustness of our framework
in noisy environments. These dummy objects increase the complexity of the
environment, challenging the agents’ observation, planning, and communication
processes.

In C-WAH and Noisy-C-WAH, we evaluate the agent performance using Simulation
Steps (SS), Travel Distance (TD), Communication Steps (CS), and Character
Counts (CC) to measure the time cost to achieve the common goal, the average
distance traveled, the time cost to perform communication, and the average
number of characters used in the communication, respectively. In TDW-MAT,
performance is evaluated based on the success rate of transporting items,
including the overall success rate (TOTAL), and specific success rates for
objects categorized as Food (FOOD) and Stuff (STUFF).

###  5.2 REVECA and Baselines

In comparative experiments, our REVECA was evaluated against three baselines:
the MCTS-based Hierarchical Planner (MHP), the Rule-based Hierarchical Planner
(RHP), and the Cooperative Embodied Language Agent (CoELA). We compared REVECA
with MHP and CoELA in C-WAH, with RHP and CoELA in TDW-MAT, and with CoELA in
Noisy-C-WAH.

REVECA leverages GPT-3.5 through the OpenAI API. Although GPT-4 is the latest
model, its high token cost makes extensive experimentation impractical. Thus,
we employed GPT-3.5 with default parameters: a temperature of 0.7, top-p of 1,
and a maximum token limit of 256.

MHP, from the Watch-And-Help Challenge, is a Hierarchical Planner with a high-
level planner utilizing MCTS and a low-level planner based on regression
planning [70].

RHP, from the ThreeDWorld Transport Challenge, is a Hierarchical Planner with
a high-level planner using heuristics and a low-level A-start-based planner
for navigation using a semantic map and Frontier Exploration strategy.

CoELA leverages LLMs for planning and communication, enabling collaborative
task-solving. For a fair comparison and cost efficiency, we used
GPT-3.5-driven CoELA (CoELA-3.5) for the experiment and provided
GPT-4.0-driven CoELA (CoELA-4.0) performance from the CoELA manuscript [1] for
a comprehensive analysis of different LLM capacities.

###  5.3 Comparative Analysis Results

Table 1: Comparative experimental results with C-WAH. |  | SS $\downarrow$ |  | TD (m) $\downarrow$ |  | CS $\downarrow$ |  | CC $\downarrow$
---|---|---|---|---|---|---|---|---
REVECA |  | 48.90 |  | 40.34 |  | 6.90 |  | 79.65
CoELA-3.5 |  | 71.90 |  | 61.29 |  | 10.40 |  | 158.46
CoELA-4.0 |  | 57.00 |  | / |  | / |  | /
MHP |  | 69.40 |  | 58.96 |  | / |  | /
Table 2: Comparative experimental results with TDW-MAT. | TOTAL (%) $\uparrow$ |  | FOOD (%) $\uparrow$ |  | STUFF (%) $\uparrow$
---|---|---|---|---|---
REVECA | 0.86 |  | 0.88 |  | 0.84
CoELA-3.5 | 0.64 |  | 0.69 |  | 0.59
CoELA-4.0 | 0.71 |  | 0.82 |  | 0.61
RHP | 0.79 |  | 0.83 |  | 0.76
Figure 8: Comparative experimental results with Noisy-C-WAH, incorporating
varying numbers of dummy objects.

Table 1 shows that REVECA outperforms other baselines in C-WAH. Specifically,
GPT-3.5-driven REVECA uses fewer steps to complete tasks compared to
CoELA-4.0, CoELA-3.5, and MHP, demonstrating superior effectiveness. The
performance of CoELA significantly drops with GPT-3.5, even below MHP,
highlighting CoELA’s reliance on GPT-4.0’s reasoning capability. REVECA also
shows fewer average travel distances, communication steps, and characters used
per communication.

Table 2 presents TDW-MAT results, where GPT-3.5-driven REVECA outperforms all
baselines, including GPT-4.0-driven CoELA, across all metrics (TOTAL, FOOD,
and STUFF).

In Noisy-C-WAH, the experiment included 10 or 20 additional dummy objects. As
shown in Figure 8, REVECA outperforms CoELA-3.5 in all metrics. CoELA’s
strategy of storing all acquired information in text form leads to a
significant decline in reasoning performance. As dummy objects increase, the
advantages of using relevance scores become more evident.

###  5.4 Ablation Study Results

Table 3: Ablation study result with C-WAH. The highest performance score in each metric is highlighted in underlined bold, while scores that surpass those of REVECA are indicated in bold. | SS $\downarrow$ | TD (m) $\downarrow$ | CS $\downarrow$ | CC $\downarrow$
---|---|---|---|---
REVECA | 48.90 | 40.34 | 6.90 | 79.65
w/o spatial info | 64.80 | 56.93 | 9.60 | 86.81
w/o relevance score | 43.80 | 35.75 | 8.20 | 79.64
w/o Validation Module | 54.20 | 48.47 | 5.10 | 46.90
always ask before action | 46.90 | 38.05 | 9.10 | 84.00
w/o collaborator’s info | 59.60 | 51.18 | 9.2 | 83.25
K=2 | 55.40 | 46.32 | 7.50 | 66.47
K=4 | 53.30 | 45.00 | 9.30 | 86.72
R=3 | 53.00 | 46.02 | 8.10 | 77.41
R=5 | 54.90 | 46.75 | 8.70 | 88.47
Table 4: Ablation study result with Noisy-C-WAH augmented by 20 dummy objects. The highest performance score in each metric is highlighted in underlined bold, while scores that surpass those of REVECA are indicated in bold. | SS $\downarrow$ | TD (m) $\downarrow$ | CS $\downarrow$ | CC $\downarrow$
---|---|---|---|---
REVECA | 63.60 | 54.37 | 8.80 | 103.03
w/o spatial info | 89.00 | 77.86 | 13.10 | 126.00
w/o relevance score | 95.30 | 79.66 | 9.80 | 110.33
w/o Validation Module | 75.80 | 68.53 | 5.00 | 46.84
always ask before action | 56.80 | 49.97 | 13.30 | 127.14
w/o collaborator’s info | 80.40 | 70.96 | 9.70 | 110.42
K=2 | 65.20 | 55.68 | 7.40 | 109.16
K=4 | 72.50 | 62.38 | 9.90 | 120.30
R=3 | 64.60 | 55.15 | 8.60 | 95.03
R=5 | 76.90 | 64.86 | 7.70 | 100.05

To demonstrate the significance of each component in our framework, we
conducted an ablation study within C-WAH and Noisy-C-WAH environments, the
latter augmented with 20 dummy objects. The results are presented in Table 3
and Table 4.

Figure 9: Two example scenarios involving Alice, who needs to place a green
plate and a red plate into the sink. This demonstrates the difference in path
planning efficiency with and without using spatial information. In scenario
(a), Alice, without spatial information, follows a suboptimal path to complete
the task, moving back and forth unnecessarily. Scenario (b) showcases the
improved efficiency when spatial information is used, enabling Alice to plan a
more direct and logical route.

Initially, we examined the REVECA without spatial information and without
relevance scores to evaluate their impact on performance. The absence of
spatial information degraded performance across all metrics, highlighting its
importance in effective planning. Omitting relevance scores improved SS and TD
scores but worsened CS scores in C-WAH while degrading all scores in Noisy-C-
WAH. This suggests that relevance scores are crucial in more complex
environments like Noisy-C-WAH with over 20 objects. To aid readers understand,
example scenarios with and without using spatial information are illustrated
in Figure 9

Next, we tested REVECA without the Validation Module and with a setting where
communication occurred before every action. The absence of the Validation
Module worsened SS and TD scores. Conversely, frequent communication before
every action slightly improved SS and TD but significantly degraded CS and CC
scores, indicating that the Validation Module enhances performance without
excessive communication.

We also tested the REVECA without considering collaborator information,
resulting in significantly degraded performance across all scores. This
underscores the importance of collaborator information, even when some details
are inferred.

Lastly, we varied the number of plans ($K$) and relevance levels ($R$)
considered by the LLM planner. Our default parameters of $K$ = 3 and $R$ = 4
yielded the best performance.

Figure 10: User study results with C-WAH. This figure illustrates the mean
scores and associated standard errors for responses to four research
questions.

###  5.5 User Study Results

We conducted a user study to evaluate REVECA’s ability to collaborate
seamlessly with humans to achieve common goals. Five participants (four men
and one woman) with an average age of 23.4 years were recruited. The
experiment was conducted in the C-WAH environment using four methods: REVECA,
REVECA without communication (w/o comm), REVECA with always ask before action
(always ask), and CoELA. Participants shared the same observation and action
space as the agents and interacted with the environment by selecting actions
from a predefined list.

Participants completed 5 sub-goals with each method. After each, they answered
a 7-point Likert scale (1: strongly disagree, 7: strongly agree) questionnaire
on four research questions: 1) Did the agent respond appropriately to your
intentions? (Appropriateness), 2) Was the interaction with the agent helpful
in achieving the goal? (Usefulness), 3) Did the agent’s performance help
achieve the goal quickly? (Efficiency), and 4) Did you feel a sense of trust
with the agent? (Trust) The “w/o comm" method excluded Appropriateness and
Usefulness questions, due to the lack of interaction. Participants were then
interviewed about each method.

As shown in Figure 10, REVECA scored highest across all four questions,
excelling in human collaboration. Participants noted that CoELA often produced
messages focused on status reports and planning rather than addressing their
questions, resulting in lower scores in Appropriateness and Usefulness. In the
“always ask" condition, participants found the agent’s repetitive questions
disruptive and demotivating. Regarding Trust, participants noted that the lack
of communication in the “w/o comm" method made it difficult to understand the
agent’s actions and situation, thereby hindering trust-based collaboration.

##  6 Conclusion

In this paper, we introduced REVECA, an LLM-driven cognitive architecture
designed for multi-objective household tasks, enabling efficient cooperation
between decentralized agents under complex partial observations. By leveraging
relevance assessment, spatial information, and plan validation, REVECA
enhances agent cooperation in dynamic and partially observable environments,
while minimizing continuous communication costs and effectively managing
irrelevant dummy objects.

REVECA’s applications extend beyond household tasks to gaming, virtual
universes, and educational environments. In gaming, REVECA can revolutionize
NPC behavior, enabling adaptive and intelligent interactions for a richer
player experience. In virtual universes, REVECA can enhance user-agent
interactions, facilitating collaborative tasks and social interactions for
more seamless experiences. In education, REVECA can manage complex tasks and
provide real-time feedback, supporting personalized learning and creating
interactive simulations and virtual tutors tailored to individual needs.

However, REVECA has limitations that warrant further exploration. Its
effectiveness in highly dynamic and unpredictable outdoor settings remains to
be validated. The framework has been tested primarily with two agents, and
scaling to more agents may introduce new challenges in social interactions and
coordination. Additionally, REVECA’s use of a low-level action skill book
could be enhanced by integrating recent advancements in animation generation
technologies, enabling more realistic and context-sensitive actions.

Addressing these limitations could make future REVECA even more robust and
applicable across a broader range of multi-agent environments and tasks.

## References

  * [1] Hongxin Zhang, Weihua Du, Jiaming Shan, Qinhong Zhou, Yilun Du, Joshua B Tenenbaum, Tianmin Shu, and Chuang Gan.  Building cooperative embodied agents modularly with large language models.  arXiv preprint arXiv:2307.02485, 2023.
  * [2] Wenhao Li, Dan Qiao, Baoxiang Wang, Xiangfeng Wang, Bo Jin, and Hongyuan Zha.  Semantically aligned task decomposition in multi-agent reinforcement learning.  ArXiv, abs/2305.10865, 2023.
  * [3] Ceyao Zhang, Kaijie Yang, Siyi Hu, Zihao Wang, Guanghe Li, Yi Eve Sun, Chen Zhang, Zhaowei Zhang, Anji Liu, Song-Chun Zhu, Xiaojun Chang, Junge Zhang, F. Yin, Yitao Liang, and Yaodong Yang.  Proagent: Building proactive cooperative agents with large language models.  In AAAI Conference on Artificial Intelligence, 2023.
  * [4] Hongxin Zhang, Zeyuan Wang, Qiushi Lyu, Zheyuan Zhang, Sunli Chen, Tianmin Shu, Yilun Du, and Chuang Gan.  Combo: Compositional world models for embodied multi-agent cooperation.  ArXiv, abs/2404.10775, 2024.
  * [5] Huao Li, Yu Quan Chong, Simon Stepputtis, Joseph Campbell, Dana Hughes, Michael Lewis, and Katia P. Sycara.  Theory of mind for multi-agent collaboration via large language models.  In Conference on Empirical Methods in Natural Language Processing, 2023.
  * [6] Peter Stone and Manuela Veloso.  Multiagent systems: A survey from a machine learning perspective.  Autonomous Robots, 8:345–383, 2000.
  * [7] Sven Gronauer and Klaus Diepold.  Multi-agent deep reinforcement learning: a survey.  Artificial Intelligence Review, 55(2):895–943, 2022.
  * [8] Yuke Zhu, Daniel Gordon, Eric Kolve, Dieter Fox, Li Fei-Fei, Abhinav Gupta, Roozbeh Mottaghi, and Ali Farhadi.  Visual semantic planning using deep successor representations.  In Proceedings of the IEEE international conference on computer vision, pages 483–492, 2017.
  * [9] Dipendra Misra, Andrew Bennett, Valts Blukis, Eyvind Niklasson, Max Shatkhin, and Yoav Artzi.  Mapping instructions to actions in 3d environments with visual goal prediction.  arXiv preprint arXiv:1809.00786, 2018.
  * [10] Chris Amato, George Dimitri Konidaris, Leslie Pack Kaelbling, and Jonathan P. How.  Modeling and planning with macro-actions in decentralized pomdps.  The journal of artificial intelligence research, 64:817–859, 2019\.
  * [11] Max Jaderberg, Wojciech M Czarnecki, Iain Dunning, Luke Marris, Guy Lever, Antonio Garcia Castaneda, Charles Beattie, Neil C Rabinowitz, Ari S Morcos, Avraham Ruderman, et al.  Human-level performance in 3d multiplayer games with population-based reinforcement learning.  Science, 364(6443):859–865, 2019.
  * [12] Tabish Rashid, Mikayel Samvelyan, Christian Schroeder De Witt, Gregory Farquhar, Jakob Foerster, and Shimon Whiteson.  Monotonic value function factorisation for deep multi-agent reinforcement learning.  Journal of Machine Learning Research, 21(178):1–51, 2020.
  * [13] Pratyusha Sharma, Antonio Torralba, and Jacob Andreas.  Skill induction and planning with latent language.  arXiv preprint arXiv:2110.01517, 2021.
  * [14] Hengyuan Hu, Adam Lerer, Brandon Cui, Luis Pineda, Noam Brown, and Jakob Foerster.  Off-belief learning.  In International Conference on Machine Learning, pages 4369–4379. PMLR, 2021.
  * [15] Siyi Hu, Fengda Zhu, Xiaojun Chang, and Xiaodan Liang.  Updet: Universal multi-agent reinforcement learning via policy decoupling with transformers.  arXiv preprint arXiv:2101.08001, 2021.
  * [16] Linghui Meng, Muning Wen, Yaodong Yang, Chenyang Le, Xiyun Li, Weinan Zhang, Ying Wen, Haifeng Zhang, Jun Wang, and Bo Xu.  Offline pre-trained multi-agent decision transformer: One big sequence model tackles all smac tasks.  arXiv preprint arXiv:2112.02845, 2021.
  * [17] DJ Strouse, Kevin McKee, Matt Botvinick, Edward Hughes, and Richard Everett.  Collaborating with humans without human data.  Advances in Neural Information Processing Systems, 34:14502–14515, 2021.
  * [18] Andrei Lupu, Brandon Cui, Hengyuan Hu, and Jakob Foerster.  Trajectory diversity for zero-shot coordination.  In International conference on machine learning, pages 7204–7213. PMLR, 2021.
  * [19] Keane Lucas and Ross E Allen.  Any-play: An intrinsic augmentation for zero-shot coordination.  arXiv preprint arXiv:2201.12436, 2022.
  * [20] Muning Wen, Jakub Kuba, Runji Lin, Weinan Zhang, Ying Wen, Jun Wang, and Yaodong Yang.  Multi-agent reinforcement learning is a sequence modeling problem.  Advances in Neural Information Processing Systems, 35:16509–16521, 2022.
  * [21] Chao Yu, Akash Velu, Eugene Vinitsky, Jiaxuan Gao, Yu Wang, Alexandre Bayen, and Yi Wu.  The surprising effectiveness of ppo in cooperative multi-agent games.  Advances in Neural Information Processing Systems, 35:24611–24624, 2022.
  * [22] Rui Zhao, Jinming Song, Yufeng Yuan, Haifeng Hu, Yang Gao, Yi Wu, Zhongqian Sun, and Wei Yang.  Maximum entropy population-based training for zero-shot human-ai coordination.  In Proceedings of the AAAI Conference on Artificial Intelligence, volume 37, pages 6145–6153, 2023.
  * [23] Yang Li, Shao Zhang, Jichen Sun, Yali Du, Ying Wen, Xinbing Wang, and Wei Pan.  Cooperative open-ended learning framework for zero-shot coordination.  In International Conference on Machine Learning, pages 20470–20484. PMLR, 2023.
  * [24] Yang Li, Shao Zhang, Jichen Sun, Wenhao Zhang, Yali Du, Ying Wen, Xinbing Wang, and Wei Pan.  Tackling cooperative incompatibility for zero-shot human-ai coordination.  arXiv preprint arXiv:2306.03034, 2023.
  * [25] Yifan Zhong, Jakub Grudzien Kuba, Xidong Feng, Siyi Hu, Jiaming Ji, and Yaodong Yang.  Heterogeneous-agent reinforcement learning.  Journal of Machine Learning Research, 25:1–67, 2024.
  * [26] Ryan Lowe, Yi I Wu, Aviv Tamar, Jean Harb, OpenAI Pieter Abbeel, and Igor Mordatch.  Multi-agent actor-critic for mixed cooperative-competitive environments.  Advances in neural information processing systems, 30, 2017.
  * [27] Eric Kolve, Roozbeh Mottaghi, Winson Han, Eli VanderBilt, Luca Weihs, Alvaro Herrasti, Matt Deitke, Kiana Ehsani, Daniel Gordon, Yuke Zhu, et al.  Ai2-thor: An interactive 3d environment for visual ai.  arXiv preprint arXiv:1712.05474, 2017.
  * [28] Tianmin Shu and Yuandong Tian.  M3̂rl: Mind-aware multi-agent management reinforcement learning.  arXiv preprint arXiv:1810.00147, 2018.
  * [29] Fei Xia, Amir R Zamir, Zhiyang He, Alexander Sax, Jitendra Malik, and Silvio Savarese.  Gibson env: Real-world perception for embodied agents.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 9068–9079, 2018.
  * [30] Mikayel Samvelyan, Tabish Rashid, Christian Schroeder De Witt, Gregory Farquhar, Nantas Nardelli, Tim GJ Rudner, Chia-Man Hung, Philip HS Torr, Jakob Foerster, and Shimon Whiteson.  The starcraft multi-agent challenge.  arXiv preprint arXiv:1902.04043, 2019.
  * [31] Manolis Savva, Abhishek Kadian, Oleksandr Maksymets, Yili Zhao, Erik Wijmans, Bhavana Jain, Julian Straub, Jia Liu, Vladlen Koltun, Jitendra Malik, et al.  Habitat: A platform for embodied ai research.  In Proceedings of the IEEE/CVF international conference on computer vision, pages 9339–9347, 2019.
  * [32] 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 Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pages 10740–10749, 2020.
  * [33] Fanbo Xiang, Yuzhe Qin, Kaichun Mo, Yikuan Xia, Hao Zhu, Fangchen Liu, Minghua Liu, Hanxiao Jiang, Yifu Yuan, He Wang, et al.  Sapien: A simulated part-based interactive environment.  In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pages 11097–11107, 2020.
  * [34] Xavier Puig, Tianmin Shu, Shuang Li, Zilin Wang, Yuan-Hong Liao, Joshua B Tenenbaum, Sanja Fidler, and Antonio Torralba.  Watch-and-help: A challenge for social perception and human-ai collaboration.  arXiv preprint arXiv:2010.09890, 2020.
  * [35] Aishwarya Padmakumar, Jesse Thomason, Ayush Shrivastava, Patrick Lange, Anjali Narayan-Chen, Spandana Gella, Robinson Piramuthu, Gokhan Tur, and Dilek Hakkani-Tur.  Teach: Task-driven embodied agents that chat.  In Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, pages 2017–2025, 2022.
  * [36] Chengshu Li, Ruohan Zhang, Josiah Wong, Cem Gokmen, Sanjana Srivastava, Roberto Martín-Martín, Chen Wang, Gabrael Levine, Michael Lingelbach, Jiankai Sun, et al.  Behavior-1k: A benchmark for embodied ai with 1,000 everyday activities and realistic simulation.  In Conference on Robot Learning, pages 80–93. PMLR, 2023.
  * [37] Qinhong Zhou, Sunli Chen, Yisong Wang, Haozhe Xu, Weihua Du, Hongxin Zhang, Yilun Du, Joshua B Tenenbaum, and Chuang Gan.  Hazard challenge: Embodied decision making in dynamically changing environments.  arXiv preprint arXiv:2401.12975, 2024.
  * [38] Jiechuan Jiang and Zongqing Lu.  Learning attentional communication for multi-agent cooperation.  In Neural Information Processing Systems, 2018.
  * [39] Abhishek Das, Théophile Gervet, Joshua Romoff, Dhruv Batra, Devi Parikh, Michael G. Rabbat, and Joelle Pineau.  Tarmac: Targeted multi-agent communication.  In International Conference on Machine Learning, 2018.
  * [40] Micah Carroll, Rohin Shah, Mark K Ho, Tom Griffiths, Sanjit Seshia, Pieter Abbeel, and Anca Dragan.  On the utility of learning about humans for human-ai coordination.  Advances in neural information processing systems, 32, 2019.
  * [41] Zhiheng Xi, Wenxiang Chen, Xin Guo, Wei He, Yiwen Ding, Boyang Hong, Ming Zhang, Junzhe Wang, Senjie Jin, Enyu Zhou, et al.  The rise and potential of large language model based agents: A survey.  arXiv preprint arXiv:2309.07864, 2023.
  * [42] Lei Wang, Chen Ma, Xueyang Feng, Zeyu Zhang, Hao Yang, Jingsen Zhang, Zhiyuan Chen, Jiakai Tang, Xu Chen, Yankai Lin, et al.  A survey on large language model based autonomous agents.  Frontiers of Computer Science, 18(6):1–26, 2024.
  * [43] 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.
  * [44] Sherry Yang, Ofir Nachum, Yilun Du, Jason Wei, Pieter Abbeel, and Dale Schuurmans.  Foundation models for decision making: Problems, methods, and opportunities.  arXiv preprint arXiv:2303.04129, 2023.
  * [45] Theodore R Sumers, Shunyu Yao, Karthik Narasimhan, and Thomas L Griffiths.  Cognitive architectures for language agents.  arXiv preprint arXiv:2309.02427, 2023.
  * [46] Guanzhi Wang, Yuqi Xie, Yunfan Jiang, Ajay Mandlekar, Chaowei Xiao, Yuke Zhu, Linxi Fan, and Anima Anandkumar.  Voyager: An open-ended embodied agent with large language models.  arXiv preprint arXiv:2305.16291, 2023.
  * [47] Wenlong Huang, Fei Xia, Dhruv Shah, Danny Driess, Andy Zeng, Yao Lu, Pete Florence, Igor Mordatch, Sergey Levine, Karol Hausman, et al.  Grounded decoding: Guiding text generation with grounded models for robot control.  arXiv preprint arXiv:2303.00855, 2023.
  * [48] Siyu Yuan, Jiangjie Chen, Ziquan Fu, Xuyang Ge, Soham Shah, Charles Robert Jankowski, Yanghua Xiao, and Deqing Yang.  Distilling script knowledge from large language models for constrained language planning.  arXiv preprint arXiv:2305.05252, 2023.
  * [49] Wenlong Huang, F. Xia, Ted Xiao, Harris Chan, Jacky Liang, Peter R. Florence, Andy Zeng, Jonathan Tompson, Igor Mordatch, Yevgen Chebotar, Pierre Sermanet, Noah Brown, Tomas Jackson, Linda Luu, Sergey Levine, Karol Hausman, and Brian Ichter.  Inner monologue: Embodied reasoning through planning with language models.  In Conference on Robot Learning, 2022.
  * [50] Wenlong Huang, Pieter Abbeel, Deepak Pathak, and Igor Mordatch.  Language models as zero-shot planners: Extracting actionable knowledge for embodied agents.  In International Conference on Machine Learning, pages 9118–9147. PMLR, 2022.
  * [51] Shreyas Sundara Raman, Vanya Cohen, Eric Rosen, Ifrah Idrees, David Paulius, and Stefanie Tellex.  Planning with large language models via corrective re-prompting.  In NeurIPS 2022 Foundation Models for Decision Making Workshop, 2022\.
  * [52] Vishal Pallagani, Bharath Muppasani, Keerthiram Murugesan, Francesca Rossi, Lior Horesh, Biplav Srivastava, Francesco Fabiano, and Andrea Loreggia.  Plansformer: Generating symbolic plans using transformers.  arXiv preprint arXiv:2212.08681, 2022.
  * [53] Maitrey Gramopadhye and Daniel Szafir.  Generating executable action plans with environmentally-aware language models.  In 2023 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), pages 3568–3575. IEEE, 2023.
  * [54] Zihao Wang, Shaofei Cai, Guanzhou Chen, Anji Liu, Xiaojian Shawn Ma, and Yitao Liang.  Describe, explain, plan and select: interactive planning with llms enables open-world multi-task agents.  Advances in Neural Information Processing Systems, 36, 2024.
  * [55] Sébastien Bubeck, Varun Chandrasekaran, Ronen Eldan, John A. Gehrke, Eric Horvitz, Ece Kamar, Peter Lee, Yin Tat Lee, Yuan-Fang Li, Scott M. Lundberg, Harsha Nori, Hamid Palangi, Marco Tulio Ribeiro, and Yi Zhang.  Sparks of artificial general intelligence: Early experiments with gpt-4.  ArXiv, abs/2303.12712, 2023.
  * [56] Mosh Levy, Alon Jacoby, and Yoav Goldberg.  Same task, more tokens: the impact of input length on the reasoning performance of large language models.  ArXiv, abs/2402.14848, 2024.
  * [57] Tomer David Ullman.  Large language models fail on trivial alterations to theory-of-mind tasks.  ArXiv, abs/2302.08399, 2023.
  * [58] Daniel S. Bernstein, Shlomo Zilberstein, and Neil Immerman.  The complexity of decentralized control of markov decision processes.  In Conference on Uncertainty in Artificial Intelligence, 2000.
  * [59] Claudia V. Goldman and Shlomo Zilberstein.  Optimizing information exchange in cooperative multi-agent systems.  In Adaptive Agents and Multi-Agent Systems, 2003.
  * [60] Matthijs T. J. Spaan, Geoffrey J. Gordon, and Nikos A. Vlassis.  Decentralized planning under uncertainty for teams of communicating agents.  In Adaptive Agents and Multi-Agent Systems, 2006.
  * [61] Dhruv Batra, Angel X. Chang, S. Chernova, Andrew J. Davison, Jia Deng, Vladlen Koltun, Sergey Levine, Jitendra Malik, Igor Mordatch, Roozbeh Mottaghi, Manolis Savva, and Hao Su.  Rearrangement: A challenge for embodied ai.  ArXiv, abs/2011.01975, 2020.
  * [62] Lei Wang, Wanyu Xu, Yihuai Lan, Zhiqiang Hu, Yunshi Lan, Roy Ka-Wei Lee, and Ee-Peng Lim.  Plan-and-solve prompting: Improving zero-shot chain-of-thought reasoning by large language models.  In Annual Meeting of the Association for Computational Linguistics, 2023.
  * [63] Simeng Sun, Y. Liu, Shuo Wang, Chenguang Zhu, and Mohit Iyyer.  Pearl: Prompting large language models to plan and execute actions over long documents.  ArXiv, abs/2305.14564, 2023.
  * [64] Noah Shinn, Federico Cassano, Beck Labash, Ashwin Gopinath, Karthik Narasimhan, and Shunyu Yao.  Reflexion: language agents with verbal reinforcement learning.  In Neural Information Processing Systems, 2023.
  * [65] Archiki Prasad, Alexander Koller, Mareike Hartmann, Peter Clark, Ashish Sabharwal, Mohit Bansal, and Tushar Khot.  Adapt: As-needed decomposition and planning with language models.  ArXiv, abs/2311.05772, 2023.
  * [66] Takeshi Kojima, Shixiang Shane Gu, Machel Reid, Yutaka Matsuo, and Yusuke Iwasawa.  Large language models are zero-shot reasoners.  ArXiv, abs/2205.11916, 2022.
  * [67] Xavier Puig, Kevin Kyunghwan Ra, Marko Boben, Jiaman Li, Tingwu Wang, Sanja Fidler, and Antonio Torralba.  Virtualhome: Simulating household activities via programs.  2018 IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 8494–8502, 2018.
  * [68] Chuang Gan, Siyuan Zhou, Jeremy Schwartz, Seth Alter, Abhishek Bhandwaldar, Dan Gutfreund, Daniel L. K. Yamins, James J. DiCarlo, Josh H. McDermott, Antonio Torralba, and Joshua B. Tenenbaum.  The threedworld transport challenge: A visually guided task-and-motion planning benchmark towards physically realistic embodied ai.  2022 International Conference on Robotics and Automation (ICRA), pages 8847–8854, 2021.
  * [69] Chuang Gan, Jeremy Schwartz, Seth Alter, Martin Schrimpf, James Traer, Julian De Freitas, Jonas Kubilius, Abhishek Bhandwaldar, Nick Haber, Megumi Sano, Kuno Kim, Elias Wang, Damian Mrowca, Michael Lingelbach, Aidan Curtis, Kevin T. Feigelis, Daniel Bear, Dan Gutfreund, David Cox, James J. DiCarlo, Josh H. McDermott, Joshua B. Tenenbaum, and Daniel L. K. Yamins.  Threedworld: A platform for interactive multi-modal physical simulation.  ArXiv, abs/2007.04954, 2020.
  * [70] Richard E. Korf.  Planning as search: A quantitative approach.  Artif. Intell., 33:65–88, 1987.