MSC

# Triality for homogeneous polynomials

Laura P. Schaposnik and Sebastian Schulz  Laura P. Schaposnik,
University of Illinois at Chicago,
<EMAIL_ADDRESS>Sebastian Schulz,
University of Texas at Austin, USA.,
<EMAIL_ADDRESS>
###### Abstract

Through the triality of ${\rm SO}(8,{\mathbb{C}})$, we study three
interrelated homogenous basis of the ring of invariant polynomials of Lie
algebras, which give the basis of three Hitchin fibrations, and identify the
explicit automorphisms that relate them.

###### keywords:

Triality, Invariant polynomials, Hitchin systems

##  1 Introduction: Triality, Higgs bundles and invariant polynomials

.

Triality. An avatar of triality is triality of vector spaces, which is given
by a trilinear form $\rho:V_{1}\times V_{2}\times V_{3}\to\mathbb{R}$ that is
non-degenerate in the sense that fixing any two non-zero vectors yields a non-
zero linear functional in the third entry. Put differently, fixing a non-zero
vector yields a duality of the two remaining vector spaces, i.e. a non-
degenerate bilinear form in the usual sense. Vector spaces that are connected
via triality can be (non-canonically) identified with a fixed vector space $V$
which is a division algebra. To see this, consider two non-zero vectors
$e_{1}\in V_{1}$, and $e_{2}\in V_{2}$. Then, $\rho$ induces isomorphisms
$V_{2}\xrightarrow{\sim}V_{3}^{\ast}$ and
$V_{1}\xrightarrow{\sim}V_{3}^{\ast}$, and thus one can identify these spaces
with a vector space $V$. The trilinear form can then be dualized to a map
$V\times V\to V$ that we shall call multiplication, and the non-degeneracy
states precisely that each multiplication has both a left- and a right-
inverse, turning $V$ into a division algebra.

The upshot of the above perspective is that triality is a very rigorous
phenomenon and over the real numbers it can only appear for vector spaces of
dimensions 1, 2, 4 and 8. Across these notes, we are interested in that of
dimension 8, where the three vector spaces in question are the vector
representation $\Delta_{0}$ and the two irreducible spin representations
$\Delta_{1}$ and $\Delta_{2}$ of $\mathrm{Spin}(8)$. The spin representations
are self-dual, and so the trilinear form connecting these vector spaces can be
seen as the homomorphism $\Delta_{0}\times\Delta_{1}\to\Delta_{2}$ that is
obtained by restricting the action of the Clifford algebra $\mathrm{Cliff}(8)$
to the vector space $\Delta_{0}\simeq{\mathbb{R}}^{8}=\mathrm{Cliff}_{1}(8)$
of degree 1 elements. In terms of the trilinear form $\rho$, triality of
$\mathrm{Spin}(8)$ means that for every $g\in\mathrm{Spin}(8)$ there exist
unique $g_{1},g_{2}\in\mathrm{Spin}(8)$ such that for all $v_{i}\in V_{i}$ one
has that

$\displaystyle\rho(v_{0},v_{1},v_{2})=\rho(gv_{0},g_{1}v_{1},g_{2}v_{2}).$ (1)

Higgs bundles and the Hitchin fibration. When considering triality between
vector spaces and groups, it is natural to ask about its consequences on
different mathematical objects defined through those groups and vector spaces.
In this paper, we shall ask this question in relation to Higgs bundles, which
were introduced by Hitchin in 1987 for the general linear group [5], and whose
“classical” definition is the following:

A Higgs bundle on a compact Riemann surface $\Sigma$ is a pair $(E,\Phi)$ for
a holomorphic vector bundle $E$ on $\Sigma$, and the Higgs field $\Phi\in
H^{0}(\Sigma,\text{End}(E)\otimes K)$, where $K=T^{*}\Sigma$.

This definition can be generalized to encompass principal
$G_{\mathbb{C}}$-bundles, for $G_{\mathbb{C}}$ a complex semi-simple Lie group
[6], which shall be consider across this paper. A $G_{\mathbb{C}}$-Higgs
bundle on a compact Riemann surface $\Sigma$ is a pair $(P,\Phi)$ where $P$ is
a principal $G_{\mathbb{C}}$-bundle over $\Sigma$, and the Higgs field $\Phi$
is a holomorphic section of the vector bundle ad$P\otimes_{\mathbb{C}}K$, for
ad$P$ the vector bundle associated to the adjoint representation and
$K=T^{*}\Sigma$.

When $G_{\mathbb{C}}\subset GL(n,\mathbb{C})$, a $G_{\mathbb{C}}$-Higgs bundle
gives rise to a Higgs bundle in the classical sense, with some extra structure
reflecting the definition of $G_{\mathbb{C}}$. In particular, classical Higgs
bundles are given by $GL(n,\mathbb{C})$-Higgs bundles. Through what is known
as the Non-Abelian Hodge correspondence [2, 3, 5, 14, 15] and the Riemann-
Hilbert correspondence, Higgs bundles manifest themselves as both flat
connections and surface group representations, fundamental objects in
contemporary mathematics, and closely related to theoretical physics.

By imposing stability conditions, one may form the moduli space
$\mathcal{M}_{G_{\mathbb{C}}}$ of $G_{\mathbb{C}}$-Higgs bundles, which in
turn has a natural fibration associated to it, the Hitchin fibration. The
Hitchin fibration is most easily defined through a choice of a homogeneous
basis $\\{p_{i}\\}_{i=1}^{k}$ for the algebra of invariant polynomials of the
Lie algebra $\mathfrak{g}_{c}$ of $G_{\mathbb{C}}$, of degrees
$\\{d_{i}\\}_{i=1}^{k}$. Then, the Hitchin fibration, introduced in [6], is
given by

$\displaystyle h\leavevmode\nobreak\ :\leavevmode\nobreak\
\mathcal{M}_{G_{\mathbb{C}}}$ $\displaystyle\longrightarrow$
$\displaystyle\mathcal{A}_{\mathfrak{g}_{c}}:=\bigoplus_{i=1}^{k}H^{0}(\Sigma,K^{d_{i}}),$
(2) $\displaystyle(E,\Phi)$ $\displaystyle\mapsto$
$\displaystyle(p_{1}(\Phi),\ldots,p_{k}(\Phi)).$ (3)

The map $h$ is referred to as the Hitchin map: it is a proper map for any
choice of basis of invariant polynomials [6], and the space
$\mathcal{A}_{\mathfrak{g}_{c}}$ is known as the Hitchin base111Notice that
the base depends only on the Lie algebra $\mathfrak{g}_{c}$ as indicated by
the notation.. It is important to note that through the Hitchin fibration,
$\mathcal{M}_{G_{\mathbb{C}}}$ gives examples of hyperkähler manifolds which
are integrable systems [6], leading to remarkable applications in physics.
Moreover, Hausel-Thaddeus [9] related Higgs bundles to mirror symmetry, and
with Donagi-Pantev presented $\mathcal{M}_{G_{\mathbb{C}}}$ as a fundamental
example of mirror symmetry for Calabi-Yau manifolds, whose geometry and
topology continues to be studied [4]. More recently, Kapustin-Witten [10] used
Higgs bundles and the Hitchin fibration to obtain a physical derivation of the
geometric Langlands correspondence through mirror symmetry. Soon after, Ngô
found the Hitchin fibration a key ingredients when proving the fundamental
lemma in [11].

Summary of our work. Inspired by the triality induced between three Hitchin
fibrations through the triality of Lie groups, Lie algebras and their rings of
invariant polynomials, we dedicate this short note to fill a gap we found in
the literature when looking for explicit descriptions of correspondences
between homogenous bases of the rings of invariant polynomials of Lie algebras
arising from the triality of ${\rm SO}(8,{\mathbb{C}})$. The present work is
organized as follows: in Section 2 we shall give an overview of the group-
theoretic construction of triality. Then, in Section 3 we introduce the
perspective through which one may understand triality within Hitchin systems:

Proposition 3.1. The natural map ${\rm G}_{2}\rightarrow\rm Spin(8)$ induced
by triality is obtained by combining the action of

$\mathcal{M}:=\frac{1}{2}\begin{pmatrix}-1&-1&-1&-1\\\ 1&1&-1&-1\\\
1&-1&1&-1\\\ 1&-1&-1&1\end{pmatrix}$

on all seven quadruples giving the 28-dimensional Lie algebra
$\mathfrak{so}(8)$ in (10), defining an automorphism $\sigma$ of
$\mathfrak{so}(8)$ that preserves the Lie bracket, and whose fixed subalgebra
is isomorphic to $\mathfrak{g}_{2}$, the Lie algebra of ${\mathrm{G}_{2}}$.

Our main interest lies in the study of the above action on different
homogenous bases of the ring of invariant polynomials of Lie algebras, since
those describe the base of Hitchin fibrations. We hence dedicate Section 4 to
study the action of the triality automorphism $\sigma$ described in
Proposition 3.1 on the algebra of invariant polynomials of $\mathfrak{so}(8)$.
To this end, recall that a particular choice of basis is given by the four
polynomials $p_{1}(M)=\operatorname{Tr}(M^{2})$,
$p_{2}(M)=\operatorname{Tr}(M^{4})$, $p_{3}(M)=\operatorname{Tr}(M^{6})$ and
$\mathrm{Pf}(M)$, where the latter denotes the Pfaffian. We then prove the
following:

Theorem 4.1. Under the order 3 automorphism $\sigma$ of $\mathfrak{so}(8)$ in
Proposition 3.1, the basis of $\mathbb{C}[\mathfrak{so}(8)]^{\mathrm{SO}(8)}$
transforms as

$\displaystyle\operatorname{Tr}(\sigma(M)^{2})$
$\displaystyle=\operatorname{Tr}(M^{2}),$
$\displaystyle\operatorname{Tr}(\sigma(M)^{4})$
$\displaystyle=\frac{3}{8}\operatorname{Tr}(M^{2})^{2}-\frac{1}{2}\operatorname{Tr}(M^{4})-12\mathrm{Pf}(M),$
$\displaystyle\mathrm{Pf}(\sigma(M))$
$\displaystyle=-\frac{1}{64}\operatorname{Tr}(M^{2})^{2}+\frac{1}{16}\operatorname{Tr}(M^{4})-\frac{1}{2}\mathrm{Pf}(M),$
$\displaystyle\operatorname{Tr}(\sigma(M)^{6})$
$\displaystyle=\frac{15}{64}\operatorname{Tr}(M^{2})^{3}-\frac{15}{16}\operatorname{Tr}(M^{2})\cdot\operatorname{Tr}(M^{4})-\frac{15}{2}\operatorname{Tr}(M^{2})\cdot\mathrm{Pf}(M)+\operatorname{Tr}(M^{6}).$

Finally, we conclude the manuscript with some directions of further research
for which we envisage the present results shall prove very useful.

Acknowledgements The authors are thankful to S. Rayan for his thorough
comments on a draft of the manuscript. The work of S.S. is partially supported
by NSF grants DMS 1107452, 1107263, 1107367 ”RNMS: GEometric structures And
Representation varieties” (the GEAR Network).” L.P.S. was partially supported
by NSF DMS 1509693 and NSF CAREER Award DMS 1749013, as well as by the
Alexander Von Humboldt foundation. This material is also based upon work
supported by NSF DMS 1440140 while L.P.S. was in residence at the Mathematical
Sciences Research Institute in Berkeley, California, during the Fall 2019
semester. Both authors are thankful for the support of the Simons Center for
Geometry and Physics during the Spring 2019 program on Geometry and Physics of
Hitchin systems.

##  2 Triality of ${\mathfrak{so}}(8,{\mathbb{C}})$

We shall recall here how triality appears for the complex Lie algebra
${\mathfrak{so}}(8,{\mathbb{C}})$ and the associated simply-connected Lie
group $\mathrm{Spin}(8,{\mathbb{C}})$ from a few different perspectives, which
will become useful across these notes. The group $\mathrm{Out}(\mathfrak{g})$
of outer automorphisms of a Lie algebra is the symmetry group of its Dynkin
diagram, which for the case at hand is the group $S_{3}$ of permutations on 3
letters. In particular, these automorphisms permute the three 8-dimensional
irreducible representations of $\mathrm{Spin}(8)$ which are given by the
vector representation $\Delta_{0}$ (modelled on $\mathbb{C}^{8}$) and two
chiral spin representations $\Delta_{i}$ for $i=1,2$.

###  2.1 Triality via the octonions.

We shall start by describing the compact real group ${\mathrm{G}_{2}}$ as the
group of algebra morphisms of the octonions ${\mathbb{O}}$, the maximal real
finite-dimensional division algebra. The octonions form a non-associative,
non-commutative unital algebra that is real eight-dimensional. We recall here
some of its properties that are needed for our study of triality on Higgs
bundles, following [16], which the reader may want to consult for details.

The starting point is a particular basis $\\{e_{0}=1,e_{1},\dots,e_{7}\\}$ for
which $e_{i}^{2}=-1$ ($i\neq 0$) and $e_{i}e_{j}=-e_{j}e_{i}$ ($0\neq i\neq
j\neq 0$). The multiplication of octonions is then completely described by the
relations encoded in the Fano plane (see Figure 1). Here, the bottom line for
instance reads $e_{5}\cdot e_{2}=e_{3}$ and cyclic permutations thereof. Note
that $(e_{1},e_{2},e_{4})$ also forms an ordered colinear triple in this way.

Figure 1: The Fano plane captures multiplication of octonions.

The Fano plane is encoding subalgebras: there is a canonical subalgebra
isomorphic to $\mathbb{R}$, which is $\mathrm{span}\\{e_{0}\\}$. Moreover,
every vertex $e_{i}$ of the diagram identifies a subalgebra
$\mathrm{span}\\{e_{0},e_{i}\\}$ isomorphic to $\mathbb{C}$, and every ordered
colinear triple $(e_{i},e_{j},e_{k})$ gives a subalgebra
$\mathrm{span}\\{e_{0},e_{i},e_{j},e_{k}\\}$ isomorphic to the quaternions
$\mathbb{H}$. Furthermore, every $e_{i}$ ($i\neq 0$) sits on exactly three
lines, which in the setting of Figure 1 are, for indices taken mod 7, given by

$(e_{i},e_{i+1},e_{i+3}),\hskip 28.45274pt(e_{i},e_{i+2},e_{i+6}),\hskip
28.45274pt(e_{i},e_{i+4},e_{i+5}).$ (4)

Rotating the Fano plane by $2\pi/3$ induces an (order 3) automorphism of
${\mathbb{O}}$ given by $e_{0}\mapsto e_{0}$ and $e_{i}\mapsto e_{2i}$ where
$i\in\\{1,\dots,7\\}$ is taken mod 7. Note that there are also natural order 2
automorphisms given by reflection along one of the central axes, but these
have to be accompanied by a sign flip for certain elements to accommodate the
correct direction of the arrows. Similar to the quaternions, for
$a_{i}\in{\mathbb{R}}$ and $x\in{\mathbb{O}}$, the octonions come equipped
with

  * •

a conjugation
$\overline{a_{0}+\sum_{i=1}^{7}a_{i}e_{i}}=a_{0}-\sum_{i=1}^{7}a_{i}e_{i}$,

  * •

a real part $\operatorname{Re}(x)=\frac{1}{2}(x+\overline{x})$,

  * •

an inner product $(\sum a_{\mu}e_{\mu},\sum b_{\nu}e_{\nu})=\sum
a_{\mu}b_{\mu}=\operatorname{Re}\big{(}(\sum
a_{\mu}e_{\mu})\cdot\overline{(\sum b_{\nu}e_{\nu})}\big{)}$,

  * •

the induced norm $|x|=\sqrt{(x,x)}$.

The group ${\mathrm{G}_{2}}$ is the group of algebra automorphisms of the
octonions, i.e.

$\mathrm{G}_{2}:=\\{\alpha\in\operatorname{Aut}_{\mathbb{R}}({\mathbb{O}})\,|\,\alpha(xy)=(\alpha
x)(\alpha y)\hskip 2.84544pt\forall x,y\in{\mathbb{O}}\\}.$ (5)

The above condition implies in particular that any $\alpha\in{\mathrm{G}_{2}}$
obeys $(\alpha x,\alpha y)=(x,y)$ and hence realises ${\mathrm{G}_{2}}$ as a
closed subgroup of

$\mathrm{O}(8)=\mathrm{O}({\mathbb{O}})=\\{\alpha\in\operatorname{Aut}_{\mathbb{R}}({\mathbb{O}})\,|\,(\alpha
x,\alpha y)=(x,y)\hskip 2.84544pt\forall x,y\in{\mathbb{O}}\\}.$ (6)

In particular, ${\mathrm{G}_{2}}$ is compact. It is easy to see that it acts
trivially on the real part of the octonions (as a morphism of algebras it
preserves the unit: $\alpha 1=1$), and that the action can be restricted to
its orthogonal complement
${\mathbb{O}}^{\prime}=\textrm{span}\\{e_{1},\dots,e_{7}\\}$ where
$\overline{\alpha e_{i}}=-\alpha e_{i}$ ($i=1,\dots,7$), so that
${\mathrm{G}_{2}}$ is really a subgroup of

$\mathrm{O}(7)=\\{\alpha\in\mathrm{O}({\mathbb{O}})\,|\,\alpha 1=1\\}.$ (7)

###  2.2 Triality of $\mathrm{Spin}(8)$.

The assignment $\sigma_{i}:g\mapsto g_{i}$ from Eq. (1) is an automorphism
that is in fact outer. Recall that an inner automorphism of a group $G$ is an
automorphism coming from conjugation by some group element $h$, i.e. $g\mapsto
h\cdot g\cdot h^{-1}=:C_{h}(g)$. Inner automorphisms form a normal subgroup
$\mathrm{Inn}(G)$ of the group $\mathrm{Aut}(G)$ with quotient

$\mathrm{Out}(G):=\mathrm{Aut}(G)/\mathrm{Inn}(G).$

For a simple Lie group, $\mathrm{Inn}(G)$ is naturally isomorphic to
$G_{ad}=G/Z(G)$, the adjoint form of the group. If $G$ is additionally simply-
connected, $\mathrm{Out}(G)$ is the symmetry group of its associated Dynkin
diagram which here is $\mathrm{Out}(\mathrm{Spin}(8))\simeq S_{3}$, the group
of permutations on 3 elements (see Figure 2).

Figure 2: The Dynkin diagram $D_{4}$ presenting its exceptional symmetries,
and the two foldings
$\mathfrak{f}_{1}:\mathfrak{so}(8)\leadsto\mathfrak{sp}(6)$, and
$\mathfrak{f}_{2}:\mathfrak{so}(8)\leadsto{\rm G}_{2}$

The external nodes of the Dynkin diagram correspond to the fundamental
representations $\Delta_{0},\Delta_{1},\Delta_{2}$ of $\mathfrak{so}(8)$ and
these are permuted by outer automorphisms, e.g. by $\sigma_{1}$ and
$\sigma_{2}$ in Eq. (1). The center of $\mathrm{Spin}(8)$ is
$\mathbb{Z}_{2}\times{\mathbb{Z}}_{2}$, which has three elements
$\omega_{0},\omega_{1},\omega_{2}$ of order two, such that each $\omega_{i}$
spans the kernel of $\Delta_{i}$. Quotiening $Spin(8)$ by one central
${\mathbb{Z}}_{2}$ to ${\mathrm{SO}}(8)$ action brakes the $S_{3}$ symmetry to
${\mathbb{Z}}_{2}$. This order 2 automorphism of ${\mathrm{SO}}(8)$ can be
represented by conjugation by an element $M\in\mathrm{O}(8)$ of determinant
$-1$. Conversely, the outer automorphism of $SO(8)$ induces an automorphism of
$Spin(8)$ which fixes $\omega_{0}$ and interchange $\omega_{1}$ and
$\omega_{2}$.

From the perspective of Dynkin diagrams, recall that Dynkin diagrams can be
folded by a symmetry, yielding a new, generally multiply laced diagram as
shown in Figure 2. Folding by an order 2 automorphism collapses two of the
external edges, yielding the Dynkin diagram $C_{3}$, while folding by an
automorphism of order 3 yields the Dynkin diagram $G_{2}$. These operations
are in the appropriate sense dual to taking fixed loci under automorphisms.

##  3 Triality as an automorphism

In order to understand the appearance of triality via Higgs bundles and the
Hitchin fibration, we shall define these subgroups as fixed points of an
automorphism to which we turn our attention now, and whose action on the
moduli space of Higgs bundles will be studied in the following sections.
Recall that the Lie algebra of ${\rm Spin}(8)$ is given by

$\mathfrak{so}(8)=\mathfrak{so}({\mathbb{O}})=\\{D\in\operatorname{Hom}_{\mathbb{R}}({\mathbb{O}})\,|\,(Dx,y)+(x,Dy)=0\;\forall
x,y\in{\mathbb{O}}\\}$ (8)

with a basis $\\{G_{i,j}\,|\,0\leqslant i<j\leqslant 7\\}$ defined through

$G_{i,j}e_{j}=e_{i},\hskip 28.45274ptG_{i,j}e_{i}=-e_{j},\hskip
28.45274ptG_{i,j}e_{k}=0\;(k\neq i,j).$ (9)

It is a 28-dimensional Lie algebra that admits a vector space decomposition
into seven 4-dimensional vector spaces with bases

$\\{G_{0,i},G_{i+1,i+3},G_{i+2,i+6},G_{i+4,i+5}\\},$ (10)

where $i\in\\{1,\dots,7\\}$, and the indices different from $0$ and $7$ are
understood mod 7. Notice in particular the resemblance with Eq. (4). In this
setting, the folding
$\mathfrak{f}_{1}:\mathfrak{so}(8)\leadsto\mathfrak{sp}(6)$ is exhibited by
taking the fixed locus of an order 2 automorphism, which yields a subalgebra
isomorphic to $\mathfrak{so}(7)$. The desired $\mathfrak{sp}(6)$ is then its
Langlands dual, and it is in this sense that folding is dual to taking fixed
loci. In order to understand the action of $\mathfrak{f}_{2}$, consider the
linear action of the matrix

$\mathcal{M}:=\frac{1}{2}\begin{pmatrix}-1&-1&-1&-1\\\ 1&1&-1&-1\\\
1&-1&1&-1\\\ 1&-1&-1&1\end{pmatrix}$ (11)

on the four-dimensional subspaces from Eq. (10), for which one can show the
following:

######  Proposition 3.1.

The natural inclusion ${\rm G}_{2}\hookrightarrow\mathrm{Spin}(8)$ is obtained
by combining the action of $\mathcal{M}$ from Eq. (11) on all seven quadruples
in Eq. (10), which defines an automorphism that preserves the Lie bracket

$\displaystyle\sigma:\mathfrak{so}(8)\rightarrow\mathfrak{so}(8),$ (12)

and whose fixed subalgebra is
$\mathfrak{so}(8)^{\sigma}\cong\mathfrak{g}_{2}$, the Lie algebra of
${\mathrm{G}_{2}}$.

######  Proof 3.2.

It is straightforward to check that $\mathcal{M}^{2}=\mathcal{M}^{T}$ and that
$\mathcal{M}^{3}=\mathbbm{1}_{4}$, i.e. $\mathcal{M}$ is of order 3. The fact
that it preserves the Lie bracket is a computation that follows from [16]. The
fact that the fixed subalgebra is isomorphic to $\mathfrak{g}_{2}$ follows
from general facts about fixed loci of Lie algebra automorphisms, or can be
checked by hand.

######  Remark 3.3.

The folding $\mathfrak{f}_{2}:\mathfrak{so}(8)\leadsto\mathfrak{g}_{2}$ is
obtained by taking the fixed locus of an automorphism, followed by Langlands
duality. Moreover, as before, folding does not give rise to a natural map
between the two Lie algebras.

Whilst we have studied above the compact real form ${\mathrm{G}_{2}}$, from
now on we will care about its complexification which by abuse of notation we
will also denote ${\mathrm{G}_{2}}$.

##  4 Triality and homogeneous invariant polynomials

Even though the foldings $\mathfrak{f}_{1}$ and $\mathfrak{f}_{2}$ do not give
rise to natural maps of Lie algebras, they remarkably lead to maps on the
level of algebras of invariant polynomials, to which we turn our attention
now. For this, we shall first consider how the eigenvalues of matrices are
transformed.

###  4.1 The choices of homogenous basis.

In order to choose the homogenous basis of invariant polynomials which we
shall be studying, we shall look into how the Hitchin base for different
$G_{\mathbb{C}}$-Hitchin systems are constructed, as described in Eq. (2)-(3).
Since we want to focus on the Lie theoretic aspect of the research here, we
shall not go into details on Hitchin systems: the interested reader can find
further details on Hitchin base in [6] for complex Lie groups, and in [12] for
real Lie groups. Moreover, recent applications and open questions in the topic
can be found in [13]. In what follows we take $G_{\mathbb{C}}$ to be one of
the complex Lie groups in Table 1 below.

Lie algebra $\mathfrak{g}$ |  Lie group $G_{\mathbb{C}}$ |  Compact real form $\mathfrak{u}$ |  dim $\mathfrak{u}$
---|---|---|---
$\mathfrak{d}_{4}$ | ${\mathrm{SO}}(8,\mathbb{C})$ | $\mathfrak{so}(8)$ | $28$
$\mathfrak{b}_{3}$ | ${\mathrm{SO}}(7,\mathbb{C})$ | $\mathfrak{so}(7)$ | $21$
$\mathfrak{c}_{3}$ | ${\mathrm{Sp}}(6,\mathbb{C})$ | $\mathfrak{sp}(6)$ | $21$
$\mathfrak{g}_{2}$ | ${\rm G}_{2}$ | $\mathfrak{g}_{2}$ | $14$
Table 1: The Lie groups and Lie algebras we consider.

Since we are looking to further our understanding of the effect of triality on
Higgs bundles, recall that an ${\mathrm{SO}}(8,{\mathbb{C}})$-Higgs bundle on
a compact Riemann surface $\Sigma$ is a pair $(E,\Phi)$, for $E$ a rk 8
holomorphic vector bundle with a symmetric bilinear form $(\cdot,\cdot)$, and
the Higgs field $\Phi:E\rightarrow E\otimes T^{*}\Sigma$, which is a
holomorphic map for which $(\Phi v,w)=-(v,\Phi w)$. In local coordinates,
$\Phi(z)=M(z)dz$ is a holomorphic $\mathfrak{so}(8)$-valued 1-form whose
eigenvalues we denote by
$\pm\lambda_{1},\pm\lambda_{2},\pm\lambda_{3},\pm\lambda_{4}$. We shall be
interested on how the eigenvalues change under the action induced by the
automorphism $\sigma$. For ease of notation we shall denote by
$K:=T^{*}\Sigma$. The characteristic polynomial of the matrix valued map
$\Phi$ defines a curve by considering the equation

$\displaystyle\left\\{\prod_{i=1}^{4}(\eta^{2}-\lambda_{i}^{2})=0\right\\}\subset{\rm
Tot}(K).$ (13)

The coefficients $a_{i}\in H^{0}(\Sigma,K^{2i})$ in Eq. (13) give a point in
the Hitchin base. In order to understand the transformation of this point
under triality, it is useful to describe the polynomial in Eq. (13) in terms
of traces, which we can express as:

$\displaystyle\eta^{8}-\left(\sum_{i=1}^{4}\lambda_{i}^{2}\right)\eta^{6}+\left(\sum_{i<j}\lambda_{i}^{2}\lambda_{j}^{2}\right)\eta^{4}-\left(\sum_{i<j<k}\lambda_{i}^{2}\lambda_{j}^{2}\lambda_{k}^{2}\right)\eta^{2}+\left(\prod_{i=1}^{4}\lambda_{i}^{2}\right).\leavevmode\nobreak\
\leavevmode\nobreak\ $ (14)

Since the action in Proposition 3.1 can be nicely described in terms of
actions on Traces and Pfaffians, it is useful to describe the characteristic
polynomial of Eq. (14) in terms of those invariant polynomials, which can be
done as follows:

$\displaystyle\det(\Phi-\eta\cdot\operatorname{Id})$ $\displaystyle=$
$\displaystyle\eta^{8}-\left(\frac{1}{2}{\rm
Tr}(\Phi^{2})\right)\eta^{6}+\left(\frac{1}{4}{\rm
Tr}(\Phi^{2})^{2}+\frac{1}{8}{\rm Tr}(\Phi^{4})\right)\eta^{4}$ (15)
$\displaystyle+$ $\displaystyle\left(\frac{1}{48}{\rm Tr}(\Phi^{2})^{3}-6{\rm
Tr}(\Phi^{2}){\rm Tr}(\Phi^{4})+8{\rm Tr}(\Phi^{6})\right)\eta^{2}+{\rm
Pf}(\Phi)^{2}.\leavevmode\nobreak\ \leavevmode\nobreak\ $

Hence, a basis of invariant polynomials is given by the Pfaffian $p_{4}={\rm
Pf}(\Phi)$ and

$\displaystyle a_{1}$ $\displaystyle=$ $\displaystyle\frac{1}{2}{\rm
Tr}(\Phi^{2}),$ (16) $\displaystyle a_{2}$ $\displaystyle=$
$\displaystyle\frac{1}{4}{\rm Tr}(\Phi^{2})^{2}+\frac{1}{8}{\rm
Tr}(\Phi^{4}),$ (17) $\displaystyle a_{3}$ $\displaystyle=$
$\displaystyle\frac{1}{48}{\rm Tr}(\Phi^{2})^{3}-6{\rm Tr}(\Phi^{2}){\rm
Tr}(\Phi^{4})+8{\rm Tr}(\Phi^{6}).$ (18)

###  4.2 The action on the homogenous basis.

In what follows, we shall be consider the values of the invariant polynomials
$p_{i}(M)=\operatorname{Tr}(M^{2i})$ for $i=1,2,3$ as well as
$p_{4}(M)=\mathrm{Pf}(M)$ for $\mathfrak{so}(8)$, as well as its Lie
subalgebras $\mathfrak{so}(7)$ and $\mathfrak{g}_{2}$. Recall that any
$M\in\mathfrak{so}(8)$ has eigenvalues that come in opposite pairs
$\pm\lambda_{i}$ for $i=1,\ldots,4$. For the Lie subalgebras mentioned these
restrictions become more severe: It is an easy exercise to see that for
$M\in\mathfrak{so}(7)$, written in the 8-dimensional representation obtained
by inclusion in $\mathfrak{so}(8)$, two of the eigenvalues must vanish.
Moreover, for $M\in\mathfrak{g}_{2}$ additionally the eigenvalues appear in
triples $\lambda_{3}=\lambda_{1}+\lambda_{2}$ (for the correct choice of
signs). This, together with the subsequent values of the invariant polynomials
is given in Tables 2-3, which will be used to describe the induced triality
morphism on the homogenous basis of invariant polynomials for
$\mathfrak{so}(8)$.

$\mathfrak{g}$ | Eigenvalues | ${\rm Tr}(M^{2})$ | ${\rm Tr}(M^{4})$
---|---|---|---
$\mathfrak{so}(8)$ | $\pm\lambda_{1},\pm\lambda_{2},\pm\lambda_{3},\pm\lambda_{4}$ | $2\sum_{i=1}^{4}\lambda_{i}^{2}$ | $2\sum_{i=1}^{4}\lambda_{i}^{4}$
$\mathfrak{so}(7)$ | $\pm\lambda_{1},\pm\lambda_{2},\pm\lambda_{3},0,0$ | $2\sum_{i=1}^{3}\lambda_{i}^{2}$ | $2\sum_{i=1}^{3}\lambda_{i}^{4}$
$\mathfrak{g}_{2}$ | $\pm\lambda_{1},\pm\lambda_{2},\pm(\lambda_{1}+\lambda_{2}),0,0$ | $4(\lambda^{2}_{1}+\lambda_{1}\lambda_{2}+\lambda_{2}^{2})$ | $4(\lambda_{1}^{2}+\lambda_{1}\lambda_{2}+\lambda_{2}^{2})^{2}$
Table 2: Eigenvalues and invariant polynomials, where $\operatorname{Tr}(M^{4})=1/4\operatorname{Tr}(M^{2})^{2}$ for $M\in\mathfrak{g_{2}}$. $\mathfrak{g}$ | Eigenvalues | ${\rm Tr}(M^{6})$ | ${\rm Pf}(M)$
---|---|---|---
$\mathfrak{so}(8)$ | $\pm\lambda_{1},\pm\lambda_{2},\pm\lambda_{3},\pm\lambda_{4}$ | $2\sum_{i=1}^{4}\lambda_{i}^{6}$ | $\lambda_{1}\cdot\lambda_{2}\cdot\lambda_{3}\cdot\lambda_{4}$
$\mathfrak{so}(7)$ | $\pm\lambda_{1},\pm\lambda_{2},\pm\lambda_{3},0,0$ | $2\sum_{i=1}^{3}\lambda_{i}^{6}$ | 0
$\mathfrak{g}_{2}$ | $\pm\lambda_{1},\pm\lambda_{2},\pm(\lambda_{1}+\lambda_{2}),0,0$ | $2(\lambda_{1}^{6}+\lambda_{2}^{6}+(\lambda_{1}+\lambda_{2})^{6})$ | 0
Table 3: Eigenvalues and invariant polynomials.

The algebra of invariant polynomials for $\mathfrak{so}(7)$ is given by
${\mathbb{C}}[\mathfrak{so}(7)]^{{\mathrm{SO}}(7)}$ and admits a basis
$\\{p_{1},p_{2},p_{3}\\}$ with $p_{i}(M)=\operatorname{Tr}(M^{2i})$ as before,
which gives rise to the natural map
${\mathbb{C}}[\mathfrak{so}(7)]^{{\mathrm{SO}}(7)}\rightarrow{\mathbb{C}}[\mathfrak{so}(8)]^{{\mathrm{SO}}(8)}.$
In terms of Hitchin systems, the map
$\mathcal{A}_{\mathfrak{so}(7)}\rightarrow\mathcal{A}_{\mathfrak{so}(8)}$ is
onto the part of the Hitchin base whose preimage under the Hitchin map
consists of Higgs bundles with vanishing Pfaffian, or, equivalently, onto the
fixed locus under an outer involution (induced by conjugation by a matrix
$A\in\mathrm{O}(8)$ with $\det A=-1$). Recall that a choice of invariant
bilinear form gives an isomorphism
$\mathcal{A}_{\mathfrak{sp}(6)}\xrightarrow{\sim}\mathcal{A}_{\mathfrak{so}(7)}$,
just like it does for any pair of Langlands dual reductive groups, and the two
maps together yield the embedding of the base for the folded Lie algebra.

We shall now turn our attention to the more interesting case of
$\mathfrak{g}_{2}\hookrightarrow\mathfrak{so}(8)$ as the fixed locus of the
triality automorphism. The following theorem establishes how the basis of
invariant polynomials transforms:

######  Theorem 4.1.

Under the order 3 automorphism $\sigma$ of $\mathfrak{so}(8)$ in (12) induced
from Eq. (11), the basis $\\{p_{1},p_{2},p_{3},p_{4}\\}$ of
$\mathbb{C}[\mathfrak{so}(8)]^{\mathrm{SO}(8)}$ transforms as

$\displaystyle\operatorname{Tr}(\sigma(M)^{2})$
$\displaystyle=\operatorname{Tr}(M^{2}),$ (19)
$\displaystyle\operatorname{Tr}(\sigma(M)^{4})$
$\displaystyle=\frac{3}{8}\operatorname{Tr}(M^{2})^{2}-\frac{1}{2}\operatorname{Tr}(M^{4})-12\mathrm{Pf}(M),$
(20) $\displaystyle\mathrm{Pf}(\sigma(M))$
$\displaystyle=-\frac{1}{64}\operatorname{Tr}(M^{2})^{2}+\frac{1}{16}\operatorname{Tr}(M^{4})-\frac{1}{2}\mathrm{Pf}(M),$
(21) $\displaystyle\operatorname{Tr}(\sigma(M)^{6})$
$\displaystyle=\frac{15}{64}\operatorname{Tr}(M^{2})^{3}-\frac{15}{16}\operatorname{Tr}(M^{2})\cdot\operatorname{Tr}(M^{4})$
$\displaystyle-\frac{15}{2}\operatorname{Tr}(M^{2})\cdot\mathrm{Pf}(M)+\operatorname{Tr}(M^{6}).$
(22)

######  Proof 4.2.

The first identity is straightforward: The space of invariant polynomials of
degree 2 is one-dimensional, and $\sigma$ defines an action of
$\mathbb{Z}_{3}$ on it, hence acts through multiplication by a cubic root of
unity. It is easy to see from the definition of $\sigma$ that it acts purely
real, hence leaving $\operatorname{Tr}(M^{2})$ invariant.

For the other three polynomials one need to perform some further analysis. In
order to understand the action of $\sigma$, we shall cosnider the values of
the invariant polynomials in terms of the matrix entries of $M=\\{M_{ij}\\}$.
As for any antisymmetric matrix, the trace of its square is

$\displaystyle\operatorname{Tr}(M^{2})=\sum_{i}(M^{2})_{ii}=\sum_{i,j}M_{ij}M_{ji}=\sum_{i,j}-(M_{ij})^{2}=-2\sum_{i<j}M_{ij}^{2},$
(23)

where $i,j,\dots=0,\dots,7$ unless otherwise noted. Since $M^{2}$ is itself
symmetric, then

$\displaystyle Tr(M^{4})=\sum_{i,j}(M^{2})_{ij}^{2}$
$\displaystyle=2\sum_{i<j}M_{ij}^{4}+4\sum_{i<j<k}\left(M_{ij}^{2}M_{ik}^{2}+M_{ij}^{2}M_{jk}^{2}+M_{ik}^{2}M_{jk}^{2}\right)$
(24)
$\displaystyle+8\sum_{i<j<k<l}\left(M_{ij}M_{ik}M_{jl}M_{kl}-M_{ij}M_{jk}M_{kl}M_{il}+M_{ik}M_{il}M_{jk}M_{jl}\right).$

The expression for $\operatorname{Tr}(M^{6})$ is increasingly complicated, but
can be calculated in a similar fashion. Lastly, we can compute the Pfaffian
from the expression of the determinant, see Figure 3, to obtain

$\displaystyle\begin{aligned} \mathrm{Pf}(M)&=\frac{1}{6\cdot 8}\sum_{\eta\in
S_{7}}\mathrm{sgn}(\eta)\cdot M_{0\eta(1)}\cdot M_{\eta(2)\eta(3)}\cdot
M_{\eta(4)\eta(5)}\cdot M_{\eta(6)\eta(7)}\\\ &=\frac{1}{4!\cdot
2^{4}}\sum_{\eta\in S_{8}}\mathrm{sgn}(\eta)\cdot M_{\eta(0)\eta(1)}\cdot
M_{\eta(2)\eta(3)}\cdot M_{\eta(4)\eta(5)}\cdot
M_{\eta(6)\eta(7)},\end{aligned}$ (25)

where $S_{7}$ (resp. $S_{8}$) is the symmetric group on the letters
$\\{1,\dots,7\\}$ (resp. on $\\{0,\dots,7\\}$).

Figure 3: The Pfaffian $\mathrm{Pf}(M)=\sqrt{\det M}$.

One should note that the prefactor in the first line of Eq. (25) arises
(compared to Figure 3) from permuting the individual factors without the
subscript $0$ (alternatively, from imposing $\eta(2)<\eta(4)<\eta(6)$), as
well as from ordering the individual subscripts by size using $M_{ij}=-M_{ji}$
(alternatively by imposing $\eta(i)<\eta(i+1)$ for $i=2,4,6$), and similarly
for the second line.

Finally, recall that the automorphism $\sigma$ acting on $\mathfrak{so}(8)$ is
induced from the linear action of the matrix defined in Eq. (11) on the linear
subspaces spanned by

$\\{M_{0,i},M_{i+1,i+3},M_{i+2,i+6},M_{i+4,i+5}\\},$

where $i\in\\{1,\dots,7\\}\mod 7$. Hence, as an example, the first column of
the transformed matrix $X:=\sigma(M)$ takes the form

$\frac{1}{2}\left(\begin{array}[]{c}0\\\ M_{01}+M_{24}+M_{37}+M_{56}\\\
M_{02}+M_{35}+M_{67}-M_{14}\\\ M_{03}+M_{46}-M_{17}-M_{25}\\\
M_{04}+M_{12}+M_{57}-M_{36}\\\ M_{05}+M_{23}-M_{16}-M_{47}\\\
M_{06}+M_{15}+M_{34}-M_{27}\\\ M_{07}+M_{13}+M_{26}+M_{45}\end{array}\right).$

By degree reasons, $\operatorname{Tr}(X^{4})$ can be expressed as

$\operatorname{Tr}(X^{4})=A\cdot\operatorname{Tr}(M^{2})^{2}+B\cdot\operatorname{Tr}(M^{4})+C\cdot\mathrm{Pf}(M),$
(26)

for some constants $A,B,C$ which we shall determine next. To this end, note
that $\operatorname{Tr}(X^{4})$ has the following shape:

$\displaystyle\operatorname{Tr}(X^{4})$
$\displaystyle=\frac{1}{2}\left(M_{01}^{4}+M_{02}^{4}+\dots\right)$ (27)
$\displaystyle+\left(M_{01}^{2}M_{02}^{2}+M_{01}^{2}M_{12}^{2}+M_{02}^{2}M_{12}^{2}+\dots\right)$
$\displaystyle+3\left(M_{01}^{2}M_{23}^{2}+M_{01}^{2}M_{24}^{2}+\dots\right)$
$\displaystyle+4\left(M_{01}M_{12}M_{23}M_{03}-M_{02}M_{03}M_{12}M_{13}\pm\dots\right)$
$\displaystyle-12\left(M_{01}M_{23}M_{45}M_{67}-M_{02}M_{13}M_{45}M_{67}\pm\dots\right).$

Since we know the coefficients for the similar terms in our basis, the
constants $A,B,C$ can be determined from the (over-constrained) system,
yielding

$\operatorname{Tr}(X^{4})=\frac{3}{8}\operatorname{Tr}(M^{2})^{2}-\frac{1}{2}\operatorname{Tr}(M^{4})-12\mathrm{Pf}(M)$

as in Theorem 4.1. In the same way, one can find the coefficients for
$\operatorname{Tr}(X^{6})$ and $\mathrm{Pf}(X)$, though the computations are
even more lenghthy: For the Pfaffian, one first needs to find a closed formula
for taking the square-root of the determinant, while for
$\operatorname{Tr}(X^{6})$ the linear system as well as the individual
expressions simply increase in size.

To understand the action of the order three automorphism on the basis of
homogenous invariant polynomials, note that the transformations from Theorem
4.1 are most conveniently encoded by the following matrix

$T=\begin{pmatrix}1&0&0&0\\\ 3/8&-1/2&-12&0\\\ -1/64&1/16&-1/2&0\\\
15/64&-15/16&-15/2&1\end{pmatrix},$ (28)

The action on a basis for homogeneous invariant polynomials of degree 6 can
thus be seen as follows:

$\begin{pmatrix}\operatorname{Tr}(\sigma(M)^{2})^{3}\\\
\operatorname{Tr}(\sigma(M)^{2})\operatorname{Tr}(\sigma(M)^{4})\\\
\operatorname{Tr}(\sigma(M)^{2})\mathrm{Pf}(\sigma(M))\\\
\operatorname{Tr}(\sigma(M)^{6})\end{pmatrix}=\begin{pmatrix}1&0&0&0\\\
3/8&-1/2&-12&0\\\ -1/64&1/16&-1/2&0\\\
15/64&-15/16&-15/2&1\end{pmatrix}\begin{pmatrix}\operatorname{Tr}(M^{2})^{3}\\\
\operatorname{Tr}(M^{2})\operatorname{Tr}(M^{4})\\\
\operatorname{Tr}(M^{2})\mathrm{Pf}(M)\\\
\operatorname{Tr}(M^{6})\end{pmatrix}.$

Moreover, a reiterated action can be computed by powers of this transformation
matrix $T$, through which we have:

$T^{2}=\begin{pmatrix}1&0&0&0\\\ 3/8&-1/2&12&0\\\ 1/64&-1/16&-1/2&0\\\
15/64&-15/16&15/2&1\end{pmatrix},$ (29)

and $T^{3}=I$ since $\sigma^{3}$ acts as the identity. Since $\sigma$ acts
linearly, the fixed locus is easily determined by finding the eigenspace of an
associated matrix, and we find the following:

######  Proposition 4.3.

The space of invariant polynomials of $SO(8,{\mathbb{C}})$ of degree six which
are invariant under the induced action of the automorphism $\sigma$ is two-
dimensional and spanned by

$\operatorname{Tr}(M^{2})^{3}\leavevmode\nobreak\ {\rm\leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ and\leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ }\leavevmode\nobreak\
5\operatorname{Tr}(M^{2})\operatorname{Tr}(M^{4})-8\operatorname{Tr}(M^{6}).$

######  Proof 4.4.

This is easily verified by computing the +1-eigenspace of $T^{t}$.

The previous Proposition is important because the algebra of invariant
polynomials of ${\mathrm{G}_{2}}$ is generated by two homogeneous polynomials,
one of degree two and one of degree six. The image of $\mathfrak{g}_{2}$
inside of $\mathfrak{so}(8)$ is contained in the set of matrices $M$ with
eigenvalues $(0,0,\pm\eta_{1},\pm\eta_{2},\pm\eta_{3})$ such that
$\eta_{1}+\eta_{2}+\eta_{3}=0$, see [7]. In terms of this representation, the
two generating invariant polynomials take values

$\displaystyle
c_{1}=\eta_{1}^{2}+\eta_{2}^{2}+\eta_{3}^{2}\leavevmode\nobreak\
\leavevmode\nobreak\ {\rm and}\leavevmode\nobreak\ \leavevmode\nobreak\
c_{3}=(\eta_{1}\leavevmode\nobreak\ \eta_{2}\leavevmode\nobreak\
\eta_{3})^{2}.$ (30)

The following Proposition explains their role with respect to the previous
generating set $\\{p_{1},p_{2},p_{3},p_{4}\\}$:

######  Proposition 4.5.

The invariant polynomials $p_{1},p_{2},p_{3},p_{4}$ of $\mathfrak{so}(8)$
restrict to invariant polynomials of $\mathfrak{g}_{2}$. As invariant
polynomials of $\mathfrak{g}_{2}$ they relate to the generating polynomials
$c_{1},c_{3}$ via

$\displaystyle c_{1}$
$\displaystyle=\frac{1}{2}\operatorname{Tr}(M^{2})=\frac{1}{2}p_{1},$ (31)
$\displaystyle c_{3}$
$\displaystyle=\frac{1}{16}p_{1}^{3}-5p_{1}p_{2}+8p_{3}.$ (32)

######  Proof 4.6.

The invariant polynomials restrict by general arguments about subgroups,
namely because

${\mathbb{C}}[\mathfrak{g}_{2}]^{{\mathrm{G}_{2}}}\hookrightarrow{\mathbb{C}}[\mathfrak{so}(8)]^{{\mathrm{G}_{2}}}\twoheadrightarrow{\mathbb{C}}[\mathfrak{so}(8)]^{{\mathrm{SO}}(8)}.$
(33)

The equations are readily verified using the description of $\mathfrak{g}_{2}$
inside of $\mathfrak{so}(8)$ from above, since one can restrict them to
matrices with eigenvalues $(0,0,\pm\eta_{1},\pm\eta_{2},\pm\eta_{3})$ such
that $\eta_{1}+\eta_{2}+\eta_{3}=0$.

######  Remark 4.7.

Notice in particular that Propositions 4.3 and 4.5 verify that

${\mathbb{C}}[\mathfrak{g}_{2}]^{{\mathrm{G}_{2}}}\subset({\mathbb{C}}[\mathfrak{so}(8)]^{{\mathrm{SO}}(8)})^{\sigma}$

as expected. Moreover, one can see that for a matrix
$M\in\mathfrak{g}_{2}\subset\mathfrak{so}(8)$ one has $\mathrm{Pf}(M)=0$ and
$\operatorname{Tr}(M^{4})=1/2\operatorname{Tr}(M^{2})^{2}$ which shows the
opposite inclusion.

###  4.3 Final remarks on further directions.

We shall conclude this short note mentioning two directions in which the
present results could be useful for. However, to maintain our focus on the Lie
theoretic aspect of the research, we shall leave these questions to future
work.

A natural questions arising from Proposition 4.5 is to identify the image of
$\mathcal{A}_{{\mathrm{G}_{2}}}\rightarrow\mathcal{A}_{{\mathrm{SO}}(8)}$
appearing through Eq. (33). When considering this question one should note
that the action of $\sigma$ on the group $G={\mathrm{SO}}(8)$ requires a
choice of splitting of the sequence
$0\rightarrow\textrm{Inn}(G)\rightarrow\textrm{Aut}(G)\rightarrow\textrm{Out}(G)\rightarrow
0.$ This sequence is always split but not canonically so: A choice of
splitting is equivalent to a choice of Cartan and Borel for $G$. The action on
$\mathcal{M}_{G_{\mathbb{C}}}$ is independent of choices, since any two
representatives differ by conjugation, which via non-abelian Hodge theory acts
trivially on $\mathcal{M}_{G_{\mathbb{C}}}$.

Finally, with views towards applications within Langlands duality and mirror
symmetry, it is also natural to ask what the effect of triality is on
Lagrangian subspaces of the moduli space of Higgs bundles defined through
other automorphisms, such as those used in [1, 8].

## References

  * [1] D. Baraglia and L. P. Schaposnik,  Real structures on moduli spaces of Higgs bundles, Adv. Theor. Math. Phys. 20 no. 3, (2016) 525–551.
  * [2] K. Corlette,  Flat $G$-bundles with canonical metrics, J. Differential Geom. 28 no. 3, (1988) 361–382.
  * [3] S. K. Donaldson,  Twisted harmonic maps and the self-duality equations, Proc. London Math. Soc. (3) 55 no. 1, (1987) 127–131.
  * [4] R. Donagi and T. Pantev,  Langlands duality for Hitchin systems, Invent. Math. 189 no. 3, (2012) 653–735.
  * [5] N. J. Hitchin,  The self-duality equations on a riemann surface, Proc. London Math. Soc. (3) 55 no. 1, (1987) 59–126.
  * [6] N. J. Hitchin,  Stable bundles and integrable systems, Duke Math. J. 54 no. 1, (1987) 91–114.
  * [7] N. J. Hitchin, “Langlands duality and $G_{2}$ spectral curves,” Q. J. Math. 58 no. 3, (2007) 319–344.
  * [8] S. Heller and L. P. Schaposnik,  Branes through finite group actions, J. Geom. Phys. 129 (2018) 279–293.
  * [9] T. Hausel and M. Thaddeus,  Mirror symmetry, langlands duality, and the Hitchin system, Invent. Math. 153 no. 1, (2003) 197–229.
  * [10] A. Kapustin and E. Witten,  Electric-magnetic duality and the geometric Langlands program, Commun. Number Theory Phys. 1 no. 1, (2007) 1–236.
  * [11] B.C. Ngô, Le lemme fondamental pour les algebres de Lie, I.H.E.S., (2010).
  * [12] L. P. Schaposnik,  Spectral data for G-Higgs bundles, DPhil Thesis –University of Oxford (United Kingdom) (2013) 1.
  * [13] L. P. Schaposnik,  Higgs bundles – recent pplications, Notices of the AMS, 67 no. 5, (2020).
  * [14] C.T. Simpson, Constructing variations of Hodge structure using Yang-Mills theory and applications to uniformization. J. Amer. Math. Soc. 1 4 (1988) 867-918.
  * [15] K. Uhlenbeck and S.-T. Yau,  On the existence of Hermitian-Yang-Mills connections in stable vector bundles, Comm. Pure Appl. Math. 39 no. S, suppl., (1986) S257–S293.
  * [16] I. Yokota,  Exceptional lie groups, (2009).


# On the Roles of LLMs in Planning: Embedding LLMs into Planning Graphs

Hankz Hankui Zhuo  Xin Chen  Rong Pan

###### Abstract

Plan synthesis aims to generate a course of actions or policies to transit
given initial states to goal states, provided domain models that could be
designed by experts or learnt from training data or interactions with the
world. Intrigued by the claims of emergent planning capabilities in large
language models (LLMs), works have been proposed to investigate the planning
effectiveness of LLMs, without considering any utilization of off-the-shelf
planning techniques in LLMs. In this paper, we aim to further study the
insight of the planning capability of LLMs by investigating the roles of LLMs
in off-the-shelf planning frameworks. To do this, we investigate the
effectiveness of embedding LLMs into one of the well-known planning
frameworks, graph-based planning, proposing a novel LLMs-based planning
framework with LLMs embedded in two levels of planning graphs, i.e., mutual
constraints generation level and constraints solving level. We empirically
exhibit the effectiveness of our proposed framework in various planning
domains.

##  1 Introduction

Plan synthesis aims to generate a course of actions or policies to transit
given initial states to goal states, provided domain models that could be
designed by experts or learnt from training data (Aineto et al., 2019) or
interactions with the world (Lamanna et al., 2023; Jin et al., 2022b). It is a
time- and space-consuming open issue in the planning community (Ghallab et
al., 2004). Intrigued by the claims of emergent planning capabilities in large
language models (LLMs), works have been proposed to investigate the planning
effectiveness of LLMs, without considering any utilization of off-the-shelf
planning techniques in LLMs (Valmeekam et al., 2023b). As demonstrated by
(Valmeekam et al., 2023b), even in a seemingly simple common-sense domain like
Blocksworld that humans usually find easy to solve, LLMs are evaluated to be
quite ineffective in planning autonomously.

An interesting result shown by (Valmeekam et al., 2023b) is when taking the
solution generated by LLMs, which is generally incorrect, as a seed plan to be
repaired by an off-the-shelf planner, e.g., LPG (Gerevini & Serina, 2002), a
significant improvement in search steps can be seen over the empty plan
provided as a seed plan for the planner. This indicates that LLMs can indeed
provide some helpful information (e.g., in some sense of heuristics) for
planning, even though they cannot solve planning problems solely. Inspired by
the result of loosely using plans generated by LLMs as seed plans, we are
curious if it is possible to “dig” more helpful information from LLMs to
assist planning deeply, e.g., by inserting LLMs into planning frameworks. By
doing this, we aim to answer the question: what roles can be played exactly by
LLMs in planning? Indeed, there have been attempts to explore off-the-shelf
planning techniques to help LLMs solving planning problems (Liu et al., 2023).
Similar to (Valmeekam et al., 2023b), they only view planners as black-boxes
without deepening the integration of LLMs in planning frameworks.

To do this, we investigate the effectiveness of embedding LLMs into one of the
well-known planning frameworks, graph-based planning (Blum & Furst, 1997). We
propose a novel LLMs-based planning framework with LLMs embedded in two levels
of the planning framework (namely LLMs4Plan), i.e., (a) selecting promising
actions in each action-level to expand the planning graph, and (b) building
non-mutual action sets in each action-level of the expanded planning graph,
which correspond to two critical steps that influence the efficiency and
effectiveness of graph planning.

(a) Expantion

(b) Backtracking

Figure 1: Two critical steps in graph planning

_For example, as shown in Figure 1(a), there could be many actions in “action-
level 1” after expanding the planning graph based on “state-label 0” with
Graphplan (Blum & Furst, 1997). We expect that LLMs will help select only a
few promising actions in each action level, e.g., $\\{a_{1},a_{2},a_{3}\\}$ in
“action-level 1”. In Figure 1(b), when backtracking from “state-level $K$”
that contains goals, there could be many candidate sets of actions to be
explored (e.g., “action set 1”, “action set 2”, “action set 3”) — actions in
each candidate set are not mutual with each other. It is particularly time-
consuming to search all of the valid candidate sets based on the _mutual
constraints_ in each action-level. We expect that LLMs are capable of helping
select only a few candidate sets to be backtracked, e.g., only “action set 1”
is selected to be backtracked by LLMs._

Specifically, in LLMs4Plan, for each action-level $i$, we first automatically
generate prompts based on _propositions_ in state-level $i-1$, _goals_ and
_domain models_ when using LLMs to select actions to expand planning graphs in
action-level $i$. After that, when backtracking from the last state-level of
expanded planning graphs, i.e., the last state-level in expanded planning
graphs contains goals, we automatically generate prompts based on propositions
in state-level $j$ (from which backtracking is conducted), propositions from
state-level 0, mutual constraints in action-level $j$, and _domain models_. We
embed the above two components into one of the well-known off-the-shelf graph
planners, Graphplan. We study the effectiveness of different cases of adding
or removing the above one or two components in Graphplan to see the
significance of roles LLMs play in the graph planning framework.

Through this study, we provide new clues for how to _deeply_ embed LLMs into
off-the-shelf planning frameworks, i.e., first identifying critical steps
(generally time-consuming ones) in specific planning frameworks, and then
designing proper prompt generation procedure to be embedded into the
frameworks. We verify that soly relying on LLMs to do planning is far from a
good option, while leveraging LLMs to help deal with some critical steps in
the graph planning framework is possible.

##  2 Related work

LLMs as planners: Many works have investigated how to leverage LLMs to
accomplish planning tasks, such as Chain-of-Thoughts (Wei et al., 2022), Tree-
of-Thoughts (Yao et al., 2023a) and Zero-Shot Planner (Huang et al., 2022a),
which utilize prompts to guide LLMs for generating action sequences for
planning related tasks. Approaches such as HuggingGPT (Shen et al., 2023) and
Chameleon (Lu et al., 2023) aim to generate initial plans using different
tools and then call the corresponding APIs for execution by augmenting LLMs
with plug-and-play modules for compositional reasoning. They designed an LLM-
based planner to assemble a sequence of tools to execute to generate final
solution plans for planning tasks. There are also some works that prompt LLMs
to compose plans in the form of PDDL (Planning Domain Definition Language) in
planning community (Liu et al., 2023; Pallagani et al., 2023). All of the
above-mentioned approaches generally synthesize plans without consideration of
feedback from external environments. In order to consider environmental
feedback, SayCan (Ichter et al., 2022), ReAct (Yao et al., 2023b), Reflexion
(Shinn et al., 2023) and Inner Monologue (Huang et al., 2022b) allow LLMs to
take single-step actions according to the environmental feedback, assuming
LLM-generated initial plans are correct without any adaptation of them. They
only adjust the immediate action being executed and are prone to fall into
local sub-optimal actions without considering long-term goals. In
consideration of removing this assumption, the evaluation of planning
capabilities in the literature involves the user incrementally interacting
with LLMs, and re-prompting it to point out flaws in its plans, with the hope
that the LLM eventually reaches an executable plan (Huang et al., 2022b; Yao
et al., 2023b; Raman et al., 2022; Wang et al., 2023; Sun et al., 2023; Silver
et al., 2023). Such evaluations are notoriously with the actual planning being
done by humans in the loop rather than LLMs themselves. Instead of considering
human-in-the-loop, (Valmeekam et al., 2023a) built another framework for
automatically evaluating planning capabilities of LLMs by leveraging automated
planning models and tools to generate the queries and validate answers from
LLMs. All of the above-mentioned approaches view LLMs as a sole planner rather
than being leveraged as components and embedded into off-the-shelf planning
frameworks, which means the planning capability of planning frameworks is not
leveraged by them.

LLMs finetuned to be Planners: Another issue of broad interest in LLMs is to
investigate how to finetune LLMs to be capable of planning. Some works (Reed
et al., 2022; Brohan et al., 2023) collected paired visual, language and
action data and trained an enormous neural networks for tackling long-horizon
tasks. Collecting those data, however, is often expensive and difficult to
scale up. Different from training LLMs from scratch, finetuning off-the-shelf
LLMs (Driess et al., 2023; Li et al., 2022) to deal with visual and language
related tasks using task-specific robot demonstrations is an option to
alleviate issues of data collection. It is, however, still problematic since
finetuning most high-performing language models, such as GPT3.5/4 (Ouyang et
al., 2022) and PaLM (Chowdhery et al., 2023), is currently impossible, as the
model weights are not open-sourced. Besides, paired vision and language
robotics demonstrations, which are still needed for finetuning, are not
readily available in practice. Considering this, (Ajay et al., 2023) propose
compositional foundation models for hierarchical planning, where a foundation
model is a composition of different expert models trained on language, vision,
and action data individually. Given an abstract language instruction
describing the desired task, they use a large language model to generate a
sequence of sub-tasks and then use a large video diffusion model to capture
geometric and physical information about the world and generate a more
detailed plan. Finetuning LLMs to be a planner indicates training data are
required to be available and the planning capability of finetuned LLMs to be
transferred to other tasks is still an open issue. Instead of finetuning LLMs,
we aim to leverage both benefits of LLMs and planning frameworks to solve
planning tasks without any training data.

LLMs as components in planners: Some studies try to use LLMs as heuristics
(Zhang et al., 2023) or transition function (Hao et al., 2023) in MCTS,
boosting the performance in coding or small-scale reasoning. Utilizing LLMs as
a world model in depth, however, is not discussed (Zhao et al., 2023). LLMs
can also provide a commonsense model of the world in addition to a policy that
acts on it. The world model and the policy are combined in Monte Carlo Tree
Search (MCTS) to scale up task planning (Zhao et al., 2023), which is
demonstrated to be effective by embedding LLMs in the MCTS framework. The idea
is similar to our work in the sense that LLMs are embedded into an off-the-
shelf framework in depth. However, they aim to learn MCTS policies from
interactions with environments, while our work aims to solve planning problems
with LLMs embedded into an off-the-shelf planner, planning-graph planner,
without any interactions or learning from environments.

##  3 Problem Formulation

In this work we consider classical planning problems specified in the form of
STRIPS language (Fikes & Nilsson, 1971). Similar idea can be extended into
more expressive planning language such as PDDL (Ghallab et al., 1998). A
STRIPS domain is composed of a set of action models $\mathcal{A}$, each of
which is a quadruple $\langle
a,\textrm{PRE}(a),\textrm{ADD}(a),\textrm{DEL}(a)\rangle$, where $a$ is an
action name with zero or more parameters,
$\textrm{PRE}(a)\subseteq\mathcal{L}$ is a precondition list indicating the
conditions under which $a$ can be applied,
$\textrm{ADD}(a)\subseteq\mathcal{L}$ is an adding list and
$\textrm{DEL}(a)\subseteq\mathcal{L}$ is a deleting list indicating the
effects of $a$. $\mathcal{L}$ is a set of atoms, each of which is composed of
a predicate with zero or more parameters. We define a planning problem as
$\mathcal{P}=\langle\mathcal{R},s_{0},g,\mathcal{A}\rangle$, where
$s_{0}\subseteq\mathcal{R}$ is an initial state and $g\subseteq\mathcal{R}$ is
a goal. $\mathcal{R}$ is a set of propositions. A solution plan $\pi=\langle
A,C\rangle$ to $\mathcal{P}$ consists of a set of actions $A$ and a set of
partial order constraints $C$ among actions. Some actions in $A$ are allowed
to be executed in parallel so long as there are no _conflicts_ among them,
e.g., there are conflicts between two actions if one deletes a precondition or
an adding effect of the other (more detailed description of conflicts will be
given in Section 4.2). A partial order plan can be _equivalently_ stretched
into a total order linear plan, which means both of them can successfully
transit initial state $s_{0}$ to goal $g$. An intuitive example of our
planning problem is as shown below.
=========== _Beginning of the example_ ============
_Example 1:_ Suppose we would like to clean a bedroom using a vacuum which is
placed in a tool room. We can formulate the problem
$\mathcal{P}=\langle\mathcal{R},s_{0},g,\mathcal{A}\rangle$ in the form of
planning language as shown below (note that we assume there is no parameter
for each predicate and action for simplicity):

  * •

the set of propositions:
$\mathcal{R}=\\{dirty(),toolroom(),clean(),bedroom()\\}$, which indicates the
set of all propositions in the problem.

  * •

initial state: $s_{0}$={_dirty()_ , _toolroom()_}, which indicates the bedroom
to be cleaned is dirty, and the tool vacuum is in the tool room.

  * •

goal: $g=\\{clean(),toolroom()\\}$, which indicates the bedroom is clean, and
the tool vacuum is back to the tool room.

  * •

action models: $\mathcal{A}$ is as shown below:

Action | Preconditions | Effects
---|---|---
$vacuum()$ |  $dirty()$, |  $clean()$,
| $bedroom()$ | $\neg dirty()$
$move2tr()$ | $bedroom()$ |  $toolroom()$,
|  | $\neg bedroom()$
$move2br()$ | $toolroom()$ |  $bedroom()$,
|  | $\neg toolroom()$

Action _vacuum_ aims to vacuuming the bedroom, the preconditions of which are
the bedroom is dirty and the vacuum-cleaner is in the bedroom. The effects of
_vacuum_ are the bedroom is clean (deleting _dirty_() as well). Action
$move2tr$ aims to move the vacuum-cleaner to the tool room, the precondition
of which is the vacuum-cleaner is in the $bedroom$. The effects are the
vacuum-cleaner is in the _tool room_ and not in the _bedroom_. Similarly,
action $move2br$ aims to move the vacuum-cleaner to the bedroom, the
precondition of which is the vacuum-cleaner is in the _tool room_. The effects
are the vacuum-cleaner is in the _bedroom_ and not in the _tool room_.

The solution plan $\pi$ to the problem $\mathcal{P}$ is:
$move2br(),vacuum(),move2tr()$.
============= _End of the example_ ==============

##  4 Our LLMs4Plan approach

An overview of our LLMs4Plan approach is as shown in Algorithm 1. In Step 1,
we first build a planning graph $PG$ with the help of LLMs given the planning
problem $\mathcal{P}$ such that the goal is included by the last state-level
in $PG$. If the number of levels in $PG$ is less than the maximal levels
$MaxIter$, we build mutual constraints $\mathcal{C}$ and sort the candidate
sets of actions, resulting in the list of candidate sets $\mathbb{A}$ — each
of which satisfies $\mathcal{C}$ — with the help of LLMs. After that we make a
deep first search based on $\mathbb{A}$ to get $\pi$. If $\pi$ is not
_Failure_ , it is returned as the solution plan; otherwise, we expand $PG$
with one more level using LLMs and repeat Steps 2-11 of the algorithm until
the maximal level $MaxIter$ is reached or a solution plan $\pi$ is found and
returned in Step 7. In the following subsections, we will detail main steps of
Algorithm 1.

Algorithm 1 An overview of our LLMs4Plan approach

Input:  Planning problem $\mathcal{P}$
Output:  Solution $\pi$

1: Build graph: $(PG,k)=buildGraphLLMs(\mathcal{P})$

2: while $k<MaxIter$ do

3: Build constraints: $\mathcal{C}=buildConstraints(PG)$

4: Sort action sets: $\mathbb{A}=sortActionsLLMs(PG,\mathcal{C})$

5: Search solutions: $\pi=depthFirstSearch(\mathbb{A},PG)$

6: if $\pi\neq$ Failure then

7: return $\pi$

8: end if

9: Expand graph: $PG\leftarrow expandGraphLLMs(PG)$

10: $k\leftarrow k+1$

11: end while

12: return Failure

###  4.1 Building Planning Graphs with LLMs

A planning graph $PG$ is the search space for a relaxed version of the
planning problem, an intuitive framework of which is shown in Figure 5. It
alternates layers of ground literals and actions. “Square” nodes at action-
level $i+1$ indicate actions that might be possible to be executed in state
$s_{i}$. Maintenance actions indicate dump operators that keep literals
unchanged between state-levels $i$ and $i+1$. “Black circle” nodes at state-
level $i$ indicate literals that might possibly be true at time $i$. Edges
between state-level $i$ and action-level $i$ indicate literals in state-level
$i$ are preconditions of actions in action-level $i$, while edges between
action-level $i$ and state-level $i+1$ indicate literals in state-level $i+1$
are adding or deleting effects of actions in action-level $i$. The nodes in
the first state-level indicate literals that are true in initial state
$s_{0}$.

Figure 2: The framework of a planning graph

The procedure of build the planning graph with LLMs (i.e., _buildGraphLLMs_)
based on the given planning problem
$\mathcal{P}=\langle\mathcal{R},s_{0},g,\mathcal{A}\rangle$ is as follows:

  1. 1.

All propositions in $s_{0}$ and the negation of propositions in
$\mathcal{R}-s_{0}$ are added into state-level 0.

  2. 2.

All actions in $\mathcal{A}$, whose preconditions are satisfied in state-level
0 and selected by LLMs, are added into action-level 1; a maintenance action
corresponding to each proposition in state-level 0 is added into action-level
1.

  3. 3.

The propositions added or deleted by actions in action-level 1 are added into
state-level 1; and all propositions in state-level 0 are added into state-
level 1 as well (i.e., which is done by the maintenance action).

  4. 4.

We repeat steps 1-3 by increasing state-level 0 to 1 (or $i$ to $i+1$) until
all propositions in goal $g$ are included by state-level $k$.

Figure 3: The prompt for consulting LLMs

In Step 2, we use LLMs to help select actions to build the planning graph.
Note that in classical planning graph-based planning (Blum & Furst, 1997), all
actions whose preconditions are satisfied will be added into the action-level.
We design the prompt to consult LLMs as shown in Figure 3, where
“$\langle$domain$\rangle$”, “$\langle$initial state$\rangle$”,
“$\langle$goal$\rangle$”, “$\langle$proposition set$\rangle$”, and
”$\langle$candidate actions$\rangle$” are action models $\mathcal{A}$, initial
state $s_{0}$, goal $g$, the set of propositions $\mathcal{R}$ and all of the
candidate actions whose preconditions are satisfied in $s_{0}$. The text in
BLUE is the command used to guide LLMs to select actions. “¡example of output
format¿” is used to guide LLMs to output actions in the desired format, e.g.,
“move ’?from’: ’rooma’, ’?to’: ’roomb’”.

###  4.2 Building Mutual Constraints

Due to the satisfaction of action models being relaxed, actions and/or states
in action-levels or state-labels may be inconsistent, i.e., there may be some
actions mutually exclusive in action-levels, or some literals mutually
exclusive in state-levels. As shown in Figure 4, there are there types mutual
exclusion constraints among actions.

Figure 4: Mutual exclusion of actions

Specifically, two actions at the same action-level are mutex, if they satisfy
the following conditions:

  * •

An effect of one negates an effect of the other, which is called _inconsistent
effects_.

  * •

One deletes a precondition of the other, which is called _interference_.

  * •

They have mutually exclusive preconditions, which is called _Competing needs_.

Otherwise they do not interfere with each other, i.e., both may appear in a
solution plan. Two literals at the same state-level are mutex if one is the
negation of the other, or all ways of achieving them are pairwise mutex,
namely _inconsistent support_.

An example planning graph corresponding to Example 1 is as shown in Figure 5.

Figure 5: An example of planning graph and mutual constraints indicated in RED
arcs

Action _vacuum_ is mutually exclusive with action _dumb_ for _toolroom_ at
_action-level 2_ since _vacuum_ ’s precondition _bedroom_ is mutually
exclusive with _toolroom_ at _state-level 1_.

###  4.3 Sort Action Sets with LLMs and Search Solutions

After we build the set of constraints in Step 3 of Algorithm 1, we use off-
the-shelf procedure presented in (Blum & Furst, 1997) to compute candidate
action sets such that there are no conflicts (i.e., satisfying the constraints
$\mathcal{C}$) among actions in each action set. After that, we consult LLMs
to sort the action sets by designing the prompts as shown in Figure 6, which
is similar to the prompt shown in Figure 3 except the command in BLUE. After
we get the sorted action sets $\mathbb{A}$, we conduct the dept-first search
procedure as done in (Blum & Furst, 1997) by giving the priority of action
sets based on the sorted action sets in $\mathbb{A}$.

Figure 6: The prompt for consulting LLMs to sort action sets

In Step 9 of Algorithm 1 (i.e., $expandGraphLLMs(PG)$), we expand $PG$ with
the same prompt as shown in Figure 3 when selecting actions for expanding one
more level of $PG$.

##  5 Experiment

###  5.1 Experimental Setup

In this experiment, we pick four domains with different scenarios, including
gripper, miconic, logistics, and movie. 10 problems are randomly selected for
each domain. The specific scenarios and scale are described as follows:

  * •

Gripper: Tasks utilize an existing robot arm to move objects between rooms,
with between 6 and 20 objects in the scene.

  * •

Miconic: Tasks uses elevators to serve guests between floors and help them
reach the floor they want to go to, with between 6 and 50 objects in the
scene.

  * •

Logistics: One of the classic logistics problems. Transportation of items
between different locations in different cities using trucks and airplanes,
with between 10 and 30 objects in the scenario.

  * •

Movie: Simulate some simple behaviors while watching a movie with between 45
and 155 objects in the scene.

To demonstrate the effectiveness of our LLMs4Plan approach, we designed five
sets of comparison experiments. The methods were implemented using Python. We
compared our LLMs4Plan approach with four other methods, which are listed
below:

  * •

GP: It is the graph-based planning algorithm mentioned above. We implement the
traditional graph planning algorithm as the most important baseline for
comparison. We directly provide domain.pddl and problem.pddl to the planner
for solving.

  * •

GPT-3.5: We simply construct and splice the contents of domain.pddl and
problem.pddl directly. We then add the necessary command prompts to form a
complete prompt into GPT3.5 and command the model to solve the problem
directly.

  * •

GPT-4: The process is the same as GPT-3.5.

  * •

LLMs4Plan-GPT3.5: When we are expanding the hierarchy or backtracking, we are
faced with a candidate action selection with LLMs. We guide the LLMs to select
a minimal subset of actions from them and utilize this subset of actions for
the next algorithmic operations, where LLMs are specifically GPT-3.5.

  * •

LLMs4Plan-GPT4: Replaced the LLM model with GPT4, otherwise same as LLMs4Plan-
GPT3.5.

###  5.2 Experimental Results

In the experimental framework described, we employed five distinct metrics to
assess the efficacy of various methodologies: the problem-solving success
rate, the cumulative count of expansion actions, the aggregate number of
mutually exclusive actions, the quantity of expansion layers, and the node
count for backtracking in Depth-First Search (DFS).

Problem-solving success rate. The solvability of a problem is a crucial metric
in assessing planning problems. All approaches are required to generate a
sequence of actions that is sufficient to solve the problem, and only if the
problem can be transferred from the initial state to the goal state through
this sequence of actions can the corresponding problem be considered to be
successfully solved. Furthermore, we imposed a maximum time constraint of five
minutes for problem resolution; any problems unsolved within this duration are
deemed failures.

Total number of expansion actions. In the GP algorithm, the expansion of
actions at each layer is a fundamental process, and the number of these
expansions serves as a vital metric. Under the premise of preserving effective
actions, fewer expansions result in a reduced count of mutually exclusive
action pairs and subsequently fewer branches in the deep search phase of
backtracking, thereby enhancing efficiency. Consequently, we compute the
average total number of action expansions per layer across all problems,
applying different methods within various domains, as a significant metric for
comparison.

Total number of mutually exclusive actions. Mutually exclusive actions are
generated from the set of candidate expansion actions based on many different
mutually exclusive conditions. The critical aspect of this metric lies in the
fact that a lower total number of mutually exclusive actions translates into
significant computational time savings. This efficiency is evident both during
the generation of the mutually exclusive action set in the forward expansion
phase and in the filtering of candidate actions based on this set during the
backtracking process.

Expansion Layers. Expansion layers hold significant importance in the GP
algorithm, as each additional expansion layer exponentially increases the
complexity of DFS during backtracking. Theoretically, the GP algorithm,
provided it can compute a solution, achieves the minimal number of levels and
the shortest action sequence. Therefore, maintaining a minimal increase in
expansion levels is pivotal and it ensures the consistent attainment of a
near-optimal action sequence.

Number of nodes for backtracking DFS. This metric serves as the cornerstone
for validating our optimization efforts, as the DFS during backtracking
accounts for the majority of the computational load in the GP algorithm,
overshadowing the forward expansion phase. Particularly when dealing with
increasing expansion depths, the exponentially growing number of DFS poses the
most significant challenge for GP algorithms in tackling large-scale problems
or complex solution sequences. We primarily utilize this metric to ascertain
which method truly enhances the efficiency of the planning process.

Regarding the latter four metrics, our analysis was confined to data from the
GP and LLMs4Plan-GPT4 methods, primarily for two reasons. Firstly, these
metrics are relevant only in scenarios where the problem is successfully
solved; failed solutions do not yield countable data. Consequently, we
excluded LLMs4Plan-GPT3.5 from our statistical analysis due to its
comparatively lower success rate. Secondly, these metrics are inherently
calculable within the GP framework alone. Hence, directly solving problems
using GPT-3.5 and GPT-4 precludes the possibility of gathering this data, as
these methods operate outside the GP framework.

We display the above metrics in two distinct tables. Table 1 shows the
problem-solving success rates, while table 2 focuses on the last four metrics
previously mentioned.

Table 1: Success rate results. In the table, each row corresponds to a distinct domain, while each column represents a separate approach or method. The values presented within the table indicate the success rate for each combination of domain and approach, with these rates quantified on a scale ranging from 0 to 1. | GPT-3.5 | GPT-4 | GP |  LLMs4Plan-GPT3.5 |  LLMs4Plan-GPT4
---|---|---|---|---|---
gripper | 0.0 | 0.6 | 0.6 | 0.0 | 0.6
miconic | 0.1 | 0.5 | 0.3 | 0.1 | 0.5
logistics | 0.2 | 0.6 | 0.6 | 0.2 | 0.8
movie | 1.0 | 1.0 | 1.0 | 1.0 | 1.0
Table 2: LLM pruning results. In the table, each column signifies a distinct domain. It displays the statistical outcomes of the two methods across four indicators. Smaller numbers in the table denote lower computational resource usage and greater effectiveness. | Expansion Actions | Mutex Actions | Expansion Layers | DFS Nodes
---|---|---|---|---
Domain | GP | LLMs4Plan | GP | LLMs4Plan | GP | LLMs4Plan | GP | LLMs4Plan
gripper | 157 | 128 | 1656 | 1179 | 4 | 4 | 21321 | 498
miconic | 181 | 176 | 792 | 668 | 5 | 6 | 2018484 | 11891
logistics | 294 | 167 | 1726 | 161 | 5 | 5 | 1261250 | 59
movie | 401 | 308 | 7 | 7 | 2 | 2 | 10869160 | 975163

###  5.3 Ablation Experiment

We conducted four ablation experiments to ascertain the effectiveness of
forward pruning and backward sorting, detailed as follows:

  1. 1.

LLMs4Plan-pruned-sorted: This method involves both forward pruning and
backward sorting, corresponding to the LLMs4Plan-GPT4 approach in our
experiments setup.

  2. 2.

LLMs4Plan-pruned-unsorted: Here, we implement pruning without sorting.

  3. 3.

LLMs4Plan-unpruned-sorted: In this approach, sorting is used, but not pruning.

  4. 4.

LLMs4Plan-unpruned-unsorted: This method involves neither pruning nor sorting,
akin to the GP method in our experimental setup.

Table 3 reveals that both pruning and sorting contribute to enhanced search
efficiency, with their combination amplifying this effect. Notably, pruning
appears slightly more effective than sorting. This is likely because LLM,
while pruning, also organizes the remaining actions logically. In contrast,
sorting may lead to minor errors due to the multitude of actions and lengthy
text. The experiments also indicate that LLM tends not to prioritize empty
actions in graph planning, favoring their later arrangement. This aligns with
our analysis suggesting that prioritizing non-empty actions is more
productive, as a layer without any action is essentially redundant.

Table 3: In the table, each row corresponds to a distinct domain, while each column represents a group of ablation experiments. The values presented within the table indicate the number of nodes for backtracking DFS. Both pruning and sorting effectively enhance search efficiency, leading to a substantial reduction in the number of nodes required for searching. Generally, pruning tends to be slightly more effective than sorting. | pruned-sorted | pruned-unsorted | unpruned-sorted | unpruned-unsorted
---|---|---|---|---
gripper | 498 | 1858 | 8317 | 21321
miconic | 11891 | 47863 | 445145 | 2018484
logistics | 59 | 85 | 1226 | 1261250
movie | 975163 | 1211830 | 975163 | 10869160

###  5.4 Experimental Analysis

Analyzing Table 1, GPT-3.5 only handles simpler tasks like movie, showing low
success rates in other domains and thus offering limited enhancement to the GP
algorithm. GPT-4 exhibits significant improvements over GPT-3.5, particularly
in reasoning and the decision of long action sequences. Leveraging GPT-4’s
advanced reasoning and common sense, GP demonstrates improved problem-solving
success in certain domains. The observed discrepancy largely stems from GP’s
timeout failures in some cases. However, with LLM-based pruning, GP
successfully resolves these issues within the set time limit, thereby boosting
the success rate.

Turning to the second table, we assess how the GP method, augmented by LLM,
enhances its success rate. The data indicates that both the total number of
expansion actions and mutually exclusive actions experience a consistent
decline with LLM integration. This suggests a reduction in the computational
effort required for forward expansion. Concurrently, the number of expansion
layers remains relatively stable, contributing to the generation of near-
optimal action sequences. During the DFS in backtracking, LLM pruning
significantly cuts down the number of search nodes, thereby endowing the GP
method with expedited problem-solving capabilities, including for problems
that were previously unsolvable.

We illustrate an example from the logistics domain in Figure 7, where we
compare the number of expansion actions before and after LLM pruning. The
application of LLM for pruning demonstrates significant efficacy across all
layers.

Figure 7: An example of action pruning. Both the GP and LLMs4Plan-GPT4 methods
expanded through 10 layers. The horizontal axis represents the layer number,
with lower numbers indicating proximity to the initial state and higher
numbers nearing the goal state. The vertical axis shows the count of expanded
actions, including both domain-specific actions and numerous empty actions,
characteristic of the graph planning algorithm. This implies a high pruning
ratio for genuinely effective actions. LLM prunes almost every layer of
expansion actions and the data in the table also contains many empty actions.

After checking the specific generated action sequences, we found that although
the solution success rates of GPT-4 and our approach were almost equivalent,
the length of the action sequences generated with GPT4 alone is generally
longer. In contrast, integrating GPT-4 with graph planning yields more
efficient and superior action sequences.

Upon analyzing examples where solutions failed, we observed that GPT4 is more
prone to pruning errors at deeper expansion levels. This results in the
discarding of effective actions, thereby unnecessarily increasing the
expansion layers and hindering problem resolution. We attribute this to two
primary factors. Firstly, as the expansion level deepens, both the predicate
set and the candidate action set expand, leading to increasingly lengthy input
prompts. This prolonged text can cause GPT-4 to gradually lose track of
previous information, resulting in decision-making errors. Secondly, the
nature of the predicate set in graph planning diverges from traditional
planning’s current state representation. This discrepancy impairs LLM’s
ability to accurately analyze the predicate set, leading to the erroneous
elimination of effective actions. LLM lacks capacity to analyze complex
predicate set combinations.

In response to GPT4’s pruning errors at deeper levels, we experimented with
pruning only at shallower levels. This approach successfully avoids the
earlier drawbacks, improving problem-solving success and efficiency. The key
is that shallow-layer pruning with GPT-4 sidesteps the issues identified
earlier. Therefore, identifying the optimal layers for LLM application in
graph planning requires further research and experimentation.

Our analysis of additional failure examples indicates that graph planning
excels in efficiently handling numerous non-mutually exclusive actions in
parallel, due to its ability to group these actions within the same layer.
However, its limitation becomes apparent in scenarios requiring the execution
of longer, complex actions. If a problem’s optimal solution sequences are
lengthy, the planning graph must be expanded considerably deeper. Despite
effective pruning, this does not resolve the issue of exponential complexity
growth in backtracking DFS caused by increased depth.

##  6 Conclusion and Future Work

Our comparative experiments in multiple domains demonstrated the efficacy of
our LLMs4Plan in significantly enhancing the problem-solving capabilities of
graph planning algorithms. Notably, LLMs4Plan boosts not just the success rate
of problem resolution but also markedly enhances search efficiency and
substantially reduces computational complexity. The runtime of LLMs4Plan is
currently hindered by multiple LLMs calls. While our method requires multiple
LLMs calls, it provides substantially improved results. There are also various
ways to enhance runtime performance like using smaller LLMs like Llama
(Touvron et al., 2023) or distilling LLMs’ knowledge into a smaller model
(Shridhar et al., 2023; Hsieh et al., 2023; Liang et al., 2023). Those are
interesting avenues for future research. Instead of leveraging LLMs to assist
planning, it would also be possible to study acquring action models (Zhuo et
al., 2011; Zhuo, 2015; Zhuo & Kambhampati, 2017) and more planning frameworks
(Jin et al., 2022a) with the help of LLMs.

## References

  * Aineto et al. (2019) Aineto, D., Celorrio, S. J., and Onaindia, E.  Learning action models with minimal observability.  _Artif. Intell._ , 275:104–137, 2019.  doi: 10.1016/J.ARTINT.2019.05.003.  URL https://doi.org/10.1016/j.artint.2019.05.003.
  * Ajay et al. (2023) Ajay, A., Han, S., Du, Y., Li, S., Gupta, A., Jaakkola, T. S., Tenenbaum, J., Kaelbling, L. P., Srivastava, A., and Agrawal, P.  Compositional foundation models for hierarchical planning.  _CoRR_ , abs/2309.08587, 2023.
  * Blum & Furst (1997) Blum, A. and Furst, M. L.  Fast planning through planning graph analysis.  _Artif. Intell._ , 90(1-2):281–300, 1997.
  * Brohan et al. (2023) Brohan, A., Brown, N., et al.  RT-1: robotics transformer for real-world control at scale.  In Bekris, K. E., Hauser, K., Herbert, S. L., and Yu, J. (eds.), _Robotics: Science and Systems XIX, Daegu, Republic of Korea, July 10-14, 2023_ , 2023.
  * Chowdhery et al. (2023) Chowdhery, A., Narang, S., et al.  Palm: Scaling language modeling with pathways.  _J. Mach. Learn. Res._ , 24:240:1–240:113, 2023.
  * Driess et al. (2023) Driess, D., Xia, F., et al.  Palm-e: An embodied multimodal language model.  In _International Conference on Machine Learning, ICML 2023, 23-29 July 2023, Honolulu, Hawaii, USA_ , volume 202 of _Proceedings of Machine Learning Research_ , pp. 8469–8488. PMLR, 2023.
  * Fikes & Nilsson (1971) Fikes, R. and Nilsson, N. J.  STRIPS: A new approach to the application of theorem proving to problem solving.  _Artif. Intell._ , 2(3/4):189–208, 1971.  doi: 10.1016/0004-3702(71)90010-5.  URL https://doi.org/10.1016/0004-3702(71)90010-5.
  * Gerevini & Serina (2002) Gerevini, A. and Serina, I.  LPG: A planner based on local search for planning graphs with action costs.  In Ghallab, M., Hertzberg, J., and Traverso, P. (eds.), _Proceedings of the Sixth International Conference on Artificial Intelligence Planning Systems, April 23-27, 2002, Toulouse, France_ , pp. 13–22. AAAI, 2002.  URL http://www.aaai.org/Library/AIPS/2002/aips02-002.php.
  * Ghallab et al. (1998) Ghallab, M., Knoblock, C., Wilkins, D., Barrett, A., Christianson, D., Friedman, M., Kwok, C., Golden, K., Penberthy, S., Smith, D., Sun, Y., and Weld, D.  Pddl - the planning domain definition language.  08 1998.
  * Ghallab et al. (2004) Ghallab, M., Nau, D., and Traverso, P.  _Automated Planning: Theory and Practice_.  Morgan Kaufmann, 2004.
  * Hao et al. (2023) Hao, S., Gu, Y., et al.  Reasoning with language model is planning with world model.  In Bouamor, H., Pino, J., and Bali, K. (eds.), _Proceedings of the 2023 Conference on Empirical Methods in Natural Language Processing, EMNLP 2023, Singapore, December 6-10, 2023_ , pp. 8154–8173. Association for Computational Linguistics, 2023.  URL https://aclanthology.org/2023.emnlp-main.507.
  * Hsieh et al. (2023) Hsieh, C., Li, C., Yeh, C., Nakhost, H., Fujii, Y., Ratner, A., Krishna, R., Lee, C., and Pfister, T.  Distilling step-by-step! outperforming larger language models with less training data and smaller model sizes.  In Rogers, A., Boyd-Graber, J. L., and Okazaki, N. (eds.), _Findings of the Association for Computational Linguistics: ACL 2023, Toronto, Canada, July 9-14, 2023_ , pp. 8003–8017. Association for Computational Linguistics, 2023.  doi: 10.18653/V1/2023.FINDINGS-ACL.507.  URL https://doi.org/10.18653/v1/2023.findings-acl.507.
  * Huang et al. (2022a) Huang, W., Abbeel, P., Pathak, D., and Mordatch, I.  Language models as zero-shot planners: Extracting actionable knowledge for embodied agents.  In Chaudhuri, K., Jegelka, S., Song, L., Szepesvári, C., Niu, G., and Sabato, S. (eds.), _International Conference on Machine Learning, ICML 2022, 17-23 July 2022, Baltimore, Maryland, USA_ , volume 162 of _Proceedings of Machine Learning Research_ , pp. 9118–9147. PMLR, 2022a.  URL https://proceedings.mlr.press/v162/huang22a.html.
  * Huang et al. (2022b) Huang, W., Xia, F., et al.  Inner monologue: Embodied reasoning through planning with language models.  In _Conference on Robot Learning, CoRL 2022, 14-18 December 2022, Auckland, New Zealand_ , volume 205 of _Proceedings of Machine Learning Research_ , pp. 1769–1782. PMLR, 2022b.
  * Ichter et al. (2022) Ichter, B., Brohan, A., et al.  Do as I can, not as I say: Grounding language in robotic affordances.  In _Conference on Robot Learning, CoRL 2022, 14-18 December 2022, Auckland, New Zealand_ , volume 205 of _Proceedings of Machine Learning Research_ , pp. 287–318. PMLR, 2022.  URL https://proceedings.mlr.press/v205/ichter23a.html.
  * Jin et al. (2022a) Jin, K., Zhuo, H. H., Xiao, Z., Wan, H., and Kambhampati, S.  Gradient-based mixed planning with symbolic and numeric action parameters.  _Artif. Intell._ , 313:103789, 2022a.  doi: 10.1016/j.artint.2022.103789.  URL https://doi.org/10.1016/j.artint.2022.103789.
  * Jin et al. (2022b) Jin, M., Ma, Z., Jin, K., Zhuo, H. H., Chen, C., and Yu, C.  Creativity of AI: automatic symbolic option discovery for facilitating deep reinforcement learning.  In _Thirty-Sixth AAAI Conference on Artificial Intelligence, AAAI 2022, Thirty-Fourth Conference on Innovative Applications of Artificial Intelligence, IAAI 2022, The Twelveth Symposium on Educational Advances in Artificial Intelligence, EAAI 2022 Virtual Event, February 22 - March 1, 2022_ , pp. 7042–7050. AAAI Press, 2022b.  doi: 10.1609/AAAI.V36I6.20663.  URL https://doi.org/10.1609/aaai.v36i6.20663.
  * Lamanna et al. (2023) Lamanna, L., Faridghasemnia, M., Gerevini, A., Saetti, A., Saffiotti, A., Serafini, L., and Traverso, P.  Learning to act for perceiving in partially unknown environments.  In _Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence, IJCAI 2023, 19th-25th August 2023, Macao, SAR, China_ , pp. 5485–5493. ijcai.org, 2023.  doi: 10.24963/IJCAI.2023/609.  URL https://doi.org/10.24963/ijcai.2023/609.
  * Li et al. (2022) Li, S., Puig, X., et al.  Pre-trained language models for interactive decision-making.  In _Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, NeurIPS 2022, New Orleans, LA, USA, November 28 - December 9, 2022_ , 2022.
  * Liang et al. (2023) Liang, C., Zuo, S., Zhang, Q., He, P., Chen, W., and Zhao, T.  Less is more: Task-aware layer-wise distillation for language model compression.  In _International Conference on Machine Learning, ICML 2023, 23-29 July 2023, Honolulu, Hawaii, USA_ , volume 202 of _Proceedings of Machine Learning Research_ , pp. 20852–20867. PMLR, 2023.  URL https://proceedings.mlr.press/v202/liang23j.html.
  * Liu et al. (2023) Liu, B., Jiang, Y., Zhang, X., Liu, Q., Zhang, S., Biswas, J., and Stone, P.  LLM+P: empowering large language models with optimal planning proficiency.  _CoRR_ , abs/2304.11477, 2023.  doi: 10.48550/ARXIV.2304.11477.  URL https://doi.org/10.48550/arXiv.2304.11477.
  * Lu et al. (2023) Lu, P., Peng, B., Cheng, H., Galley, M., Chang, K., Wu, Y. N., Zhu, S., and Gao, J.  Chameleon: Plug-and-play compositional reasoning with large language models.  _CoRR_ , abs/2304.09842, 2023.
  * Ouyang et al. (2022) Ouyang, L., Wu, J., et al.  Training language models to follow instructions with human feedback.  In _Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, NeurIPS 2022, New Orleans, LA, USA, November 28 - December 9, 2022_ , 2022.
  * Pallagani et al. (2023) Pallagani, V., Muppasani, B., Srivastava, B., Rossi, F., Horesh, L., Murugesan, K., Loreggia, A., Fabiano, F., Joseph, R., and Kethepalli, Y.  Plansformer tool: Demonstrating generation of symbolic plans using transformers.  In _Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence, IJCAI 2023, 19th-25th August 2023, Macao, SAR, China_ , pp. 7158–7162. ijcai.org, 2023.
  * Raman et al. (2022) Raman, S. S., Cohen, V., Rosen, E., Idrees, I., Paulius, D., and Tellex, S.  Planning with large language models via corrective re-prompting.  _CoRR_ , abs/2211.09935, 2022.  doi: 10.48550/ARXIV.2211.09935.  URL https://doi.org/10.48550/arXiv.2211.09935.
  * Reed et al. (2022) Reed, S. E., Zolna, K., et al.  A generalist agent.  _Trans. Mach. Learn. Res._ , 2022, 2022.
  * Shen et al. (2023) Shen, Y., Song, K., Tan, X., Li, D., Lu, W., and Zhuang, Y.  Hugginggpt: Solving AI tasks with chatgpt and its friends in huggingface.  _CoRR_ , abs/2303.17580, 2023.
  * Shinn et al. (2023) Shinn, N., Labash, B., and Gopinath, A.  Reflexion: an autonomous agent with dynamic memory and self-reflection.  _CoRR_ , abs/2303.11366, 2023.
  * Shridhar et al. (2023) Shridhar, K., Stolfo, A., and Sachan, M.  Distilling reasoning capabilities into smaller language models.  In Rogers, A., Boyd-Graber, J. L., and Okazaki, N. (eds.), _Findings of the Association for Computational Linguistics: ACL 2023, Toronto, Canada, July 9-14, 2023_ , pp. 7059–7073. Association for Computational Linguistics, 2023.  doi: 10.18653/V1/2023.FINDINGS-ACL.441.  URL https://doi.org/10.18653/v1/2023.findings-acl.441.
  * Silver et al. (2023) Silver, T., Dan, S., Srinivas, K., Tenenbaum, J. B., Kaelbling, L. P., and Katz, M.  Generalized planning in PDDL domains with pretrained large language models.  _CoRR_ , abs/2305.11014, 2023.
  * Sun et al. (2023) Sun, H., Zhuang, Y., Kong, L., Dai, B., and Zhang, C.  Adaplanner: Adaptive planning from feedback with language models.  In _NeurIPS_ , 2023.
  * Touvron et al. (2023) Touvron, H., Lavril, T., et al.  Llama: Open and efficient foundation language models.  _CoRR_ , abs/2302.13971, 2023.  doi: 10.48550/ARXIV.2302.13971.  URL https://doi.org/10.48550/arXiv.2302.13971.
  * Valmeekam et al. (2023a) Valmeekam, K., Marquez, M., Olmo, A., Sreedharan, S., and Kambhampati, S.  Leveraging pre-trained large language models to construct and utilize world models for model-based task planning.  In _NeurIPS_ , 2023a.
  * Valmeekam et al. (2023b) Valmeekam, K., Marquez, M., Sreedharan, S., and Kambhampati, S.  On the planning abilities of large language models : A critical investigation.  In _NeurIPS_ , 2023b.
  * Wang et al. (2023) Wang, Z., Cai, S., Liu, A., Ma, X., and Liang, Y.  Describe, explain, plan and select: Interactive planning with large language models enables open-world multi-task agents.  _CoRR_ , abs/2302.01560, 2023.
  * Wei et al. (2022) Wei, J., Wang, X., Schuurmans, D., Bosma, M., Ichter, B., Xia, F., Chi, E. H., Le, Q. V., and Zhou, D.  Chain-of-thought prompting elicits reasoning in large language models.  In Koyejo, S., Mohamed, S., Agarwal, A., Belgrave, D., Cho, K., and Oh, A. (eds.), _Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, NeurIPS 2022, New Orleans, LA, USA, November 28 - December 9, 2022_ , 2022.
  * Yao et al. (2023a) Yao, S., Yu, D., Zhao, J., Shafran, I., Griffiths, T. L., Cao, Y., and Narasimhan, K.  Tree of thoughts: Deliberate problem solving with large language models.  _CoRR_ , abs/2305.10601, 2023a.
  * Yao et al. (2023b) Yao, S., Zhao, J., Yu, D., Du, N., Shafran, I., Narasimhan, K. R., and Cao, Y.  React: Synergizing reasoning and acting in language models.  In _The Eleventh International Conference on Learning Representations, ICLR 2023, Kigali, Rwanda, May 1-5, 2023_. OpenReview.net, 2023b.  URL https://openreview.net/pdf?id=WE_vluYUL-X.
  * Zhang et al. (2023) Zhang, S., Chen, Z., Shen, Y., Ding, M., Tenenbaum, J. B., and Gan, C.  Planning with large language models for code generation.  _CoRR_ , abs/2303.05510, 2023.  doi: 10.48550/ARXIV.2303.05510.  URL https://doi.org/10.48550/arXiv.2303.05510.
  * Zhao et al. (2023) Zhao, Z., Lee, W. S., and Hsu, D.  Large language models as commonsense knowledge for large-scale task planning.  _CoRR_ , abs/2305.14078, 2023.
  * Zhuo (2015) Zhuo, H. H.  Crowdsourced action-model acquisition for planning.  In _AAAI_ , pp. 3439–3446, 2015.
  * Zhuo & Kambhampati (2017) Zhuo, H. H. and Kambhampati, S.  Model-lite planning: Case-based vs. model-based approaches.  _Artif. Intell._ , 246:1–21, 2017.  doi: 10.1016/j.artint.2017.01.004.  URL https://doi.org/10.1016/j.artint.2017.01.004.
  * Zhuo et al. (2011) Zhuo, H. H., Yang, Q., Pan, R., and Li, L.  Cross-domain action-model acquisition for planning via web search.  In Bacchus, F., Domshlak, C., Edelkamp, S., and Helmert, M. (eds.), _Proceedings of the 21st International Conference on Automated Planning and Scheduling, ICAPS 2011, Freiburg, Germany June 11-16, 2011_. AAAI, 2011\.  URL http://aaai.org/ocs/index.php/ICAPS/ICAPS11/paper/view/2678.