# Artinian Meadows

João Dias  and  Bruno Dinis  Departamento de Matemática, Universidade de Évora
<EMAIL_ADDRESS>Departamento de Matemática, Universidade de Évora
<EMAIL_ADDRESS>
###### Abstract.

We introduce the notion of Artinian meadow as an algebraic structure
constructed from an Artinian ring which is also a common meadow, i.e. a
commutative and associative structure with two operations (addition and
multiplication) with additive and multiplicative identities and for which
inverses are total. The inverse of zero in a common meadow is an error term
$\mathbf{a}$ which is absorbent for addition. We show that, in analogy with
what happens with commutative unital Artinian rings, Artinian meadows
decompose as a product of local meadows in an essentially unique way. We also
provide a canonical way to construct meadows from unital commutative rings.

###### Key words and phrases:

Artinian meadows, Artinian rings, local rings, decomposition of rings

###### 2010 Mathematics Subject Classification:

13E10,16U90, 06B15

##  1\. Introduction

Bergstra and Tucker introduced in [5] the notion of _meadow_ as an algebraic
structure with two operations (addition and multiplication) where both
addition and multiplication are operations for which the inverses are total.
This means in particular that in meadows one is allowed to divide by zero. At
the time, the main idea was to view these structures as abstract data types
given by equational axiomatizations [1, 2, 4, 5] so that one is able to obtain
simple term rewriting systems which are easier to automate in formal reasoning
[1, 6]. (see also [7, 8] for other recent developments).

An alternative line of research was made possible due to a recently discovered
connection between meadows and rings [11] (see Theorem 2.5 below). In fact,
for the purposes of this paper, and from a purely algebraic point of view, two
different classes of meadows are relevant: _common meadows_ , introduced by
Bergstra and Ponse in [3] and _pre-meadows with $\mathbf{a}$_, introduced by
the authors in [11]. In both pre-meadows with $\mathbf{a}$ and common meadows
the inverse of zero is an element (denoted $\mathbf{a}$) that is absorbent for
both operations. This is in contrast, for example, with involutive meadows
where the inverse of zero is zero itself [5, 9]. The interesting thing about
pre-meadows with $\mathbf{a}$ (and common meadows) is that they can be
decomposed as disjoint unions of rings [11]. When compared with common
meadows, pre-meadows with $\mathbf{a}$ take a step back by not requiring the
existence of an inverse function. This turns out to be of relevance in trying
to enumerate finite common meadows [12]. In the finite case, the two classes
are even more deeply related since if $P$, a pre-meadow with $\mathbf{a}$ such
that $0\cdot P$ is finite, and the partial order in $0\cdot P$ is a total
order, then $P$ is actually a common meadow. Note that since zero is
invertible, some usual algebraic properties are not satisfied. For example
$0\cdot x$ may not be equal to $0$.

After recalling all the necessary definitions and results about pre-meadows
with $\mathbf{a}$ and common meadows, in Section 2, we present in Section 3 a
canonical construction $M(R)$, of a pre-meadow with $\mathbf{a}$, starting
from a unital commutative ring $R$. We show that in case $R$ is Artinian, the
pre-meadow with $\mathbf{a}$ is actually a common meadow.

In Section 4 we introduce a class of common meadows, called _Artinian meadows_
, in analogy with the similar notion in rings. We show a decomposition result
for Artinian meadows in terms of _local meadows_ – common meadows whose
associated directed lattice have a single penultimate vertex. This
decomposition is unique up to permutation.

##  2\. Preliminaries

In this section we recall some definitions and results on common meadows.

######  Definition 2.1.

A _pre-meadow_ is a structure $(P,+,-,\cdot)$ satisfying the following
equations

  1. $(P_{1})$

$(x+y)+z=x+(y+z)$

  2. $(P_{2})$

$x+y=y+x$

  3. $(P_{3})$

$x+0=x$

  4. $(P_{4})$

$x+(-x)=0\cdot x$

  5. $(P_{5})$

$(x\cdot y)\cdot z=x\cdot(y\cdot z)$

  6. $(P_{6})$

$x\cdot y=y\cdot x$

  7. $(P_{7})$

$1\cdot x=x$

  8. $(P_{8})$

$x\cdot(y+z)=x\cdot y+x\cdot z$

  9. $(P_{9})$

$-(-x)=x$

  10. $(P_{10})$

$0\cdot(x+y)=0\cdot x\cdot y$

Let $P$ be a pre-meadow and let $P_{z}:=\\{x\in M\mid 0\cdot x=z\\}$. We say
that $P$ is a _pre-meadow with $\mathbf{a}$_ if there exists a unique $z\in
0\cdot P$ such that $|P_{z}|=1$ (denoted by $\mathbf{a}$) and
$x+\mathbf{a}=\mathbf{a}$, for all $x\in P$. A _common meadow_ is a pre-meadow
with $\mathbf{a}$ equipped with an inverse function $(\cdot)^{-1}$ satisfying

  1. $(M_{1})$

$x\cdot x^{-1}=1+0\cdot x^{-1}$

  2. $(M_{2})$

$(x\cdot y)^{-1}=x^{-1}\cdot y^{-1}$

  3. $(M_{3})$

$(1+0\cdot x)^{-1}=1+0\cdot x$

  4. $(M_{4})$

$0^{-1}=\mathbf{a}$

######  Definition 2.2.

Let $f:M\rightarrow N$ be a function. We say that $f$ is an _homomorphism of
(common) meadows_ if $M,N$ are common meadows and for all $x,y\in M$

  1. (1)

$f(x+y)=f(x)+f(y)$.

  2. (2)

$f(x\cdot y)=f(x)\cdot f(y)$.

  3. (3)

$f(1_{M})=1_{N}$.

######  Definition 2.3.

A _directed lattice_ of rings $\Gamma$ over a countable lattice $L$ consists
on a family of commutative rings $\Gamma_{i}$ indexed by $i\in L$, such that
$\Gamma_{i}$ is a unital commutative ring for all $i\in L\setminus\min(L)$ and
$\Gamma_{\min(L)}$ is the zero ring, together with a family of ring
homomorphisms $f_{i,j}:\Gamma_{j}\rightarrow\Gamma_{i}$ whenever $i<j$ such
that $f_{i,j}\circ f_{j,k}=f_{i,k}$ for all $i<j<k$.

Each pre-meadow has an associated directed lattice whose vertices are rings.
The ring homomorphisms of the associated lattice are called _transition maps_.

######  Example 2.4.

Consider the following lattice $L$ over the set $\\{1,2,3,4,5\\}$

${0}$${1}$${2}$${3}$${4}$${5}$

A directed lattice $\Gamma$ over $L$ is a labeling of the vertices by unital
commutative rings and a labeling of the arrows by unital ring homomorphisms.
For instance, the following labelling

${(\mathbb{Z})_{0}}$${{(\mathbb{Z}_{2})_{1}}}$${(\mathbb{Q})_{2}}$${{(\mathbb{Z}_{3})_{3}}}$${(\mathbb{R})_{4}}$${{\\{\mathbf{a}\\}}}$$\scriptstyle{\pi}$$\scriptstyle{\iota_{1}}$$\scriptstyle{\rho}$$\scriptstyle{\iota_{2}}$

where $\pi$ and $\rho$ are the projection homomorphisms to the quotients
$\mathbb{Z}/(2)\simeq\mathbb{Z}_{2}$ and $\mathbb{Z}/(3)\simeq\mathbb{Z}_{3}$
and $\iota_{1}$ and $\iota_{2}$ are the inclusion homomorphisms (note that
$\iota_{2}\circ\iota_{1}$ is the inclusion map of $\mathbb{Z}$ into
$\mathbb{R}$). The unlabelled arrows correspond to the unique map that exists
to the trivial ring. Since this map is unique we chose to omit its label.

We denote by $R^{\times}$ the set of invertible elements of the ring $R$. The
following theorem from [11] provides a link between rings and common meadows.

######  Theorem 2.5.

Let $\Gamma$ a directed lattice of rings over a lattice $L$ such that, for all
$i\in I$ and all $x\in\Gamma_{i}$ the set:

$I_{x}=\\{j\in I\mid f_{j,i}(x)\in\Gamma_{j}^{\times}\\}$

has a greatest element. Then $M=\bigsqcup_{i\in L}\Gamma_{i}$ with the
operations

  * •

$x+_{M}y=f_{i\wedge j,i}(x)+_{i\wedge j}f_{i\wedge j,j}(y)$, where $+_{i\wedge
j}$ is the sum in $\Gamma_{i\wedge j}$;

  * •

$x\cdot_{M}y=f_{i\wedge j,i}(x)\cdot_{i\wedge j}f_{i\wedge j,j}(y)$, where
$\cdot_{i\wedge j}$ is the product in $\Gamma_{i\wedge j}$.

is a common meadow such that $0\cdot M$ is lattice-equivalent to $L$.

######  Example 2.6.

Consider the following directed lattice of rings

${{(\mathbb{Z})_{0}}}$${{(\mathbb{Z})_{1}}}$${{(\mathbb{Q})_{2}}}$${{\\{\mathbf{a}\\}}}$

Let $x\in(\mathbb{Z})_{0}$ and $y\in(\mathbb{Q})_{2}$. Then by Theorem 2.5 we
have that $x+_{M}y=x+y\in(\mathbb{Q})_{2}$, since $2=1\wedge 2$. In the
figure, the sum (and the product) of two elements can be calculated by r
“going down” on the lattice until the vertex where they first meet. In
particular, the sum (and the product) of any element of $(\mathbb{Z})_{1}$
with any element of $(\mathbb{Q})_{2}$ will always give $\mathbf{a}$.

From now on, and to increase readability, we will drop the index in $+_{M}$
and $\cdot_{M}$. We will also often drop the indices in the labels of the
vertices.

######  Corollary 2.7.

Let $\Gamma$ be a directed lattice of rings over a lattice $L$. Then, there
exists $M=\bigsqcup_{i\in I}\Gamma_{i}$, a pre-meadow with $\mathbf{a}$, such
that the lattice $0\cdot M$ is equivalent to $L$.

######  Definition 2.8.

Let $P$ be a pre-meadow with $\mathbf{a}$. We define a partial order on
$0\cdot P$ as follows: $z\leq z^{\prime}$ if $z\cdot z^{\prime}=z$, for all
$z,z^{\prime}\in 0\cdot P$.

######  Proposition 2.9.

Let $M$ be a pre-meadow with $\mathbf{a}$. If $z,z^{\prime}\in 0\cdot M$ are
such that $z\leq z^{\prime}$, then the map

$\displaystyle f_{z,z^{\prime}}:M_{z^{\prime}}$ $\displaystyle\rightarrow
M_{z}$ $\displaystyle x$ $\displaystyle\mapsto x+z$

is a ring homomorphism.

Moreover, if $z,z^{\prime},z^{\prime\prime}\in 0\cdot M$ are such that
$z^{\prime\prime}\leq z^{\prime}\leq z$, then $f_{z,z^{\prime}}\circ
f_{z^{\prime},z^{\prime\prime}}=f_{z,z^{\prime\prime}}$.

The following proposition is useful to show immediately that certain directed
lattices are common meadows, since it entails that if all the vertices of the
associated lattice of a pre-meadow with $\mathbf{a}$ are fields, then it
defines a common meadow.

######  Corollary 2.10.

Let $P$ be a pre-meadow with $\mathbf{a}$ such that $P_{0\cdot z}$ is a field,
for all $0\cdot z\in 0\cdot P$. Then $P$ is a common meadow.

###### Proof.

Let $P$ be a pre-meadow with $\mathbf{a}$ such that $P_{0\cdot z}$ is a field,
for all $0\cdot z\in 0\cdot P$. Given an $x\in P\setminus 0\cdot P$, we have
that if $x$ is invertible in $P_{0\cdot x}$, then the set $I_{x}$ has $0\cdot
x$ as a maximal element. If $x\in 0\cdot P$ then $I_{x}=\\{\mathbf{a}\\}$
which clearly has a maximal element. Hence $P$ is a common meadow by Theorem
2.5. ∎

##  3\. From rings to Meadows

In this section we provide a canonical construction $M(R)$, of a pre-meadow
with $\mathbf{a}$, starting from a unital commutative ring $R$. If the ring is
Artinian, then the pre-meadow with $\mathbf{a}$ is shown to be a common meadow
(see Theorem 3.3 below). We recall that a ring is said to be _Artinian_ if
every descending sequence of ideals eventually stabilizes.

Let $P$ be a pre-meadow with $\mathbf{a}$ and $0\cdot z\in 0\cdot P$. Then
there is a transition map $f_{0\cdot z,0}:P_{0}\to P_{0\cdot z}$ defined by
$x\mapsto x+0\cdot z$, which by Proposition 2.9 is a ring homomorphism. By the
first isomorphism theorem $P_{0}/\ker(f_{0\cdot z,0})$ is isomorphic to a
subring of $P_{0\cdot z}$, namely the image of the map $f_{0\cdot z,0}$.

A sort of inverse construction is also possible: starting with a unital
commutative ring $R$ and considering all the quotients of $R$ by its ideals.
The following example illustrates this idea.

######  Example 3.1.

Recall that all the ideals $I$ of the integer ring $\mathbb{Z}$ are of the
form $I=(n)$, where $n\in\mathbb{N}$, i.e. the ideals are generated by a
unique integer. The set $\\{(n)\mid n\in\mathbb{N}\\}$ is therefore ordered by
inclusion (and divisibility), and so we can create a lattice of such ideals,
partially represented below

${(0)}$${\cdots}$${(6)}$${(2)}$${(3)}$${(1)}$

Note that $(2)+(3)=(1)=\mathbb{Z}$, $(2)\cap(3)=(6)$ and $(0)=0$ (the trivial
ring). Given this specific lattice we can construct the following directed
lattice of rings

${{\mathbb{Z}/(0)}}$${\cdots}$${{\mathbb{Z}/(6)}}$${{\mathbb{Z}/(2)}}$${{\mathbb{Z}/(3)}}$${{\mathbb{Z}/(1)}}$

where the transition maps are the natural projections, and
$\mathbb{Z}/(1)\simeq 0$ and $\mathbb{Z}/(0)\simeq\mathbb{Z}$. However, this
directed lattice does not define a common meadow. Indeed, the class
$[2]_{m}\in\mathbb{Z}/(m)\simeq\mathbb{Z}_{m}$ is invertible if and only if
$2$ does not divide $m$. Since the set $J_{[2]_{0}}=\\{m\in\mathbb{N}\mid
2\nmid m\\}$ has no greatest element, by Theorem 2.5 the directed lattice is
not associated with a common meadow.

Example 3.1 also shows that the constructed pre-meadow with $\mathbf{a}$ is
not necessarily a common meadow. However, that is always the case if we
restrict ourselves to Artinian rings. In order to show that, we first prove
the following lemma.

######  Lemma 3.2.

Let $R$ be a unital commutative ring, and $I,J\trianglelefteq R$ be ideals of
$R$. Let $x\in R$. Then the following are equivalent:

  1. (1)

$x+I$ and $x+J$ are invertible in the rings $R/I$ and $R/J$, respectively.

  2. (2)

$x+I\cap J$ is invertible in the ring $R/I\cap J$.

###### Proof.

Suppose first that $x+I$ and $x+J$ are invertible in the rings $R/I$ and
$R/J$, respectively. That is, there exist $y_{1},y_{2}\in R$ such that $x\cdot
y_{1}-1\in I$ and $x\cdot y_{2}-1\in J$.

Then

$(x\cdot y_{1}-1)\cdot(x\cdot y_{2}-1)=x^{2}\cdot y_{1}\cdot
y_{2}-x\cdot(y_{1}+y_{2})+1=x\cdot(x\cdot y_{1}\cdot y_{2}-(y_{1}+y_{2}))+1\in
I\cap J.$

In particular, since $I\cap J$ is an ideal we have that

$-(x\cdot(x\cdot y_{1}\cdot y_{2}-(y_{1}+y_{2}))+1)=x\cdot(-x\cdot y_{1}\cdot
y_{2}+(y_{1}+y_{2}))-1\in I\cap J.$

Hence $x+I\cap J$ is invertible, with inverse $(-x\cdot y_{1}\cdot
y_{2}+(y_{1}+y_{2}))$.

The other implication follows immediately from the existence of ring
homomorphisms – the projection maps – from $R/I\cap J$ to $R/I$, and from
$R/I\cap J$ to $R/J$. ∎

######  Theorem 3.3.

Let $R$ be a unital commutative ring. Then $M(R)=\bigsqcup_{I\trianglelefteq
R}R/I$, with the operations defined by

  * •

$(x+I)+(y+J)=(x+y)+I+J$

  * •

$(x+I)\cdot(y+J)=(x\cdot y)+I+J$

  * •

$-(x+I)=-x+I$,

is a pre-meadow with $\mathbf{a}$. Furthermore, if $R$ is Artinian then $M(R)$
is a common meadow.

###### Proof.

It is straightforward to check that the operations are well defined and that
they define a pre-meadow with $\mathbf{a}$.

Suppose now that $R$ is Artinian and let us see that $M(R)$ is a common
meadow. By Theorem 2.5 it is enough to prove that the set $I_{x}$ has a
greatest element, for all $x\in M(R)$. For each $x\in R$ consider the set

$I_{x}=\\{I\trianglelefteq R\mid x+I\in(R/I)^{\times}\\}.$

Since $R$ is Artinian we have that $I_{x}$ has at least one maximal element
(note that the partial order in $I_{x}$ coincides with the reversed partial
order given by the inclusion). Suppose now that $I_{x}$ has at least two
maximal elements $I,J\trianglelefteq R$. By Lemma 3.2 we have that $I\cap J\in
I_{x}$, and $I\cap J\geq I,J$. Then by the maximality of $I$ and $J$ we must
have $I=I\cap J$ and $J=I\cap J$, and so $I=J$. Hence there exists a unique
maximal element. To see that for all $I\trianglelefteq R$ and $x\in R$ the set
$I_{x+I}$ has a greatest element is similar. We then conclude that $M(R)$ is a
common meadow, by Theorem 2.5. ∎

Let us illustrate Theorem 3.3 with some examples.

######  Example 3.4.

  1. (1)

Consider the finite ring $\mathbb{Z}_{6}$ (which is clearly Artinian). By
Theorem 3.3 the following directed lattice, where the transition maps are the
quotient maps, represents a common meadow

${{\mathbb{Z}_{6}/([0]_{6})}}$${{\mathbb{Z}_{6}/([2]_{6})}}$${{\mathbb{Z}_{6}/([3]_{6})}}$${{\mathbb{Z}_{6}/([1]_{6})}}$

  2. (2)

It is well-known that if $\Bbbk$ is a field, then the polynomial ring
$\Bbbk[x]$ is not Artinian. In fact, $1+x$ is invertible in $\Bbbk[x]/I$ if
and only if $I$ is not the zero ideal. Then $I_{1+x}$ is equivalent to the set
of all non zero ideals of $\Bbbk[x]$, and since it is not Artinian $I_{1+x}$
does not have a greatest element. In particular, $M(\Bbbk[x])$ is not a common
meadow. However, given any non-trivial ideal $I$ of the ring $\Bbbk[x]$, the
quotient ring $\Bbbk[x]/I$ is Artinian. Take for instance $I=(x^{2})$. Then
the direct lattice associated with this ring

${{\Bbbk[x]/(x^{2})}}$${{\Bbbk[x]/(x)}}$${{\Bbbk[x]/(x-1)}}$${\cdots}$${0}$

represents a common meadow by Theorem 3.3.

  3. (3)

One can do a similar construction with finite abelian groups. Let $R$ be a
unital commutative ring and $A$ a finite abelian group. The set of formal sums
of elements in $A$ with coefficients in $R$

$R[A]=\left\\{\sum_{g\in A}r_{g}g\mid r_{g}\in R\right\\}$

is called the _group algebra_ of $A$ (see [10] for more on group algebras).
The group algebra is a useful object when studying representation theory of
groups. We have that if $H\trianglelefteq A$ is a (normal) subgroup, then the
map

$\displaystyle\varphi:R[A]$ $\displaystyle\to R[A/N]$ $\displaystyle\sum_{g\in
A}r_{g}g$ $\displaystyle\mapsto\sum_{g\in A}r_{g}gN$

is a ring homomorphism, such that $\ker(\varphi)$ is the ideal generated by
$\\{h-1\mid h\in H\\}$. Since $\varphi$ is clearly surjective we have that

$R[A]/(h-1\mid h\in H)\simeq R[A/H].$

We can then define the common meadow $M_{R}(A)=(\bigsqcup_{H\leq
A}R[A/N])\bigsqcup\\{\mathbf{a}\\}$. Take for instance the cyclic group
$\mathbb{Z}_{12}$. Its subgroups are generated by $1,2,3,4$ and $0$ (the non-
negative divisors of $12$) then $M_{\mathbb{C}}(\mathbb{Z}_{12})$ is defined
by the following directed lattice:

${{\mathbb{C}[\mathbb{Z}_{12}]}}$${{\mathbb{C}[\mathbb{Z}_{4}]}}$${{\mathbb{C}[\mathbb{Z}_{6}]}}$${{\mathbb{C}[\mathbb{Z}_{2}]}}$${{\mathbb{C}[\mathbb{Z}_{3}]}}$${\mathbb{C}}$${{\\{\mathbf{a}\\}}}$

Note that if $m>0$ divides $12$ (i.e. $m=6,4,3,2,1$) we have that $m$
generates a subgroup $\langle m\rangle$ such that $\mathbb{Z}_{12}/\langle
m\rangle$ is isomorphic to $\mathbb{Z}_{12/m}$. So the transition maps
$\mathbb{C}[\mathbb{Z}_{12}]\to\mathbb{C}[\mathbb{Z}_{12/m}]$ are defined by
$g\mapsto g\langle m\rangle$.

######  Proposition 3.5.

Let $R$ and $S$ be commutative unital rings. Then $M(R)$ is isomorphic to
$M(S)$ if and only if $M(R)_{0}=R$ is isomorphic to $M(S)_{0}=S$.

###### Proof.

If $M(R)$ is isomorphic to $M(S)$, then in particular $M(R)_{0}=R$ and
$M(S)_{0}=S$ are isomorphic rings.

Suppose now that $\psi:R\to S$ is a ring isomorphism. If $I$ is an ideal of
$R$, then $\psi(I)$ is an ideal of $S$. Hence

$\displaystyle\psi^{\prime}$ $\displaystyle:M(R)\to M(S)$ $\displaystyle
x+I\mapsto\psi(x)+\psi(I)$

is an isomorphism of common meadows. ∎

######  Example 3.6.

Proposition 3.5 implies the existence of pre-meadows with $\mathbf{a}$, say
$P$, which are completely determined by $P_{0}$. However this is not always
the case. Take for example the common meadows $M$ and $M^{\prime}$ associated
with the following lattices

${\mathbb{Z}}$${\mathbb{Z}}$${\mathbb{R}}$${\mathbb{Z}}$${\mathbb{R}}$${{\\{\mathbf{a}\\}}}$${{\\{\mathbf{a}\\}}}$$\scriptstyle{\iota}$$\scriptstyle{\mathrm{Id}_{\mathbb{Z}}}$$\scriptstyle{\iota}$

Even though $M_{0}$ and $M^{\prime}_{0}$ are isomorphic, (as rings) $M$ and
$M^{\prime}$ are not isomorphic since they have different lattice structures.

######  Definition 3.7.

We say that a common meadow $M$ is _Artinian_ if it is isomorphic to $M(R)$,
for some Artinian ring $R$.

We now show that every surjective ring homomorphism between Artinian rings
gives rise to an homomorphism of common meadows (Proposition 3.8). This
homomorphism of common meadows can then be used to define a functor between a
subcategory of Artinian rings and the category of common meadows (Corollary
3.10).

######  Proposition 3.8.

Let $f:R\to S$ be a surjective ring homomorphism of unital commutative
Artinian rings. Then the map $\overline{f}:M(R)\to M(S)$ defined by
$x+I\mapsto f(x)+f(I)$ is a common meadow homomorphism.

###### Proof.

The result is an immediate consequence of the fact that a surjective
homomorphism preserves ideals. ∎

######  Example 3.9.

In Proposition 3.8, the condition of $f:R\to S$ being surjective is necessary.
In order to see this, consider for example the inclusion
$i:\mathbb{Z}\to\mathbb{Q}$. Since $\mathbb{Q}$ is a field, the only ideals
are the trivial ones, there is no ring homomorphism from
$\mathbb{Z}/(m)\to\mathbb{Q}$.

Let $\mathrm{Ring^{Art}}$ be the category whose objects are unital commutative
Artinian rings, and the morphisms are surjective ring homomorphisms and
$\mathrm{M}_{d}$ be the category of common meadows (see [11]). As a
consequence of Theorem 3.3 and Proposition 3.8 we have the following result.

######  Corollary 3.10.

There is a functor $M:\mathrm{Ring^{Art}}\to\mathrm{M}_{d}$ defined by
$R\mapsto M(R)$.

##  4\. A decomposition theorem

The class of unital commutative Artinian rings is a well-behaved class of
rings. For example, unital commutative Artinian rings admit a unique
decomposition into unital commutative Artinian local rings (see e.g. [13,
Corollary 2.16]). For more on Artinian rings we refer to [13]. Motivated by
this we introduce the notion of _local common meadow_ and show that (similarly
with what happens in the case of Artinian rings) there exists a class of
common meadows, that we call _Artinian meadows_ , which admits a unique
decomposition into local common meadows.

A ring is _local_ if it has a unique maximal ideal. If $R$ is a local ring and
$I$ and $J$ are ideals of $R$ such that $I+J=R$, then $I=R$ or $J=R$, since if
$I$ and $J$ are proper ideals then they are contained in the unique maximal
ideal of $R$.

######  Definition 4.1.

Let $P$ be a pre-meadow with $\mathbf{a}$. We say that $P$ is _local_ if

$x+y=\mathbf{a}\to x=\mathbf{a}\lor y=\mathbf{a},$

for all $x,y\in P$.

######  Example 4.2.

  1. (1)

Consider the following directed lattice

${\mathbb{C}}$${\mathbb{C}}$${\mathbb{C}}$${\mathbb{C}}$${{\\{\mathbf{a}\\}}}$$\scriptstyle{\mathrm{Id}}$$\scriptstyle{\mathrm{Id}}$$\scriptstyle{\mathrm{Id}}$$\scriptstyle{\mathrm{Id}}$

Since the vertices are labelled by fields, the directed lattice defines a
common meadow by Corollary 2.10. It is in fact a local meadow because the
product of any two elements different from $\mathbf{a}$ will never be mapped
to $\mathbf{a}$.

  2. (2)

The common meadow associated with the following directed lattice

${(\mathbb{C})_{0}}$${(\mathbb{C})_{1}}$${(\mathbb{C})_{2}}$${{\\{\mathbf{a}\\}}}$$\scriptstyle{\mathrm{Id}}$$\scriptstyle{\mathrm{Id}}$$\scriptstyle{\mathrm{Id}}$$\scriptstyle{\mathrm{Id}}$

is not local since we can take $x\in(\mathbb{C})_{1}$ and
$y\in(\mathbb{C})_{2}$, which are clearly different from $\mathbf{a}$, and
their sum $x+y$ is $\mathbf{a}$.

We now turn to show that if $R$ is Artinian, the common meadow $M(R)$ admits a
unique decomposition into local meadows.

######  Theorem 4.3.

Let $R=\bigoplus R_{i}$ be the decomposition of a unital commutative Artinian
ring $R$ into local rings $R_{i}$. Then $M(R)$ decomposes into the product of
local meadows of the form $M(R_{i})$ and this decomposition is unique up to
permutation.

######  Definition 4.4.

Let $L$ be a lattice. We say that an element $a\in L$ is an _atom_ if $0\neq
a$ and

$\forall x\in L\,(0\leq x\leq a\to(x=0\lor x=a)).$

We say that $L$ is _atomic_ if for each $x\in L$ there is an atom $a$ such
that $a\leq x$.

In a common meadow $P$, an element of $0\cdot P$ is an atom if it is not equal
to $\mathbf{a}$ and there is no element between the atom and $\mathbf{a}$. We
will say that $P$, a pre-meadow with $\mathbf{a}$, is _atomic_ if $0\cdot P$
is an atomic lattice. It is easy to see that all finite pre-meadows with
$\mathbf{a}$ are atomic.

######  Example 4.5.

Not all common meadows are atomic. Take for example
$M=(\mathbb{Q}\times\mathbb{N})\sqcup\\{\mathbf{a}\\}$, with addition and
multiplication defined by

  * •

$(\alpha,x)+(\beta,y)=(\alpha+\beta,\max\\{x,y\\})$

  * •

$(\alpha,x)\cdot(\beta,y)=(\alpha\cdot\beta,\max\\{x,y\\})$

  * •

$(\alpha,x)+\mathbf{a}=\mathbf{a}+(\alpha,x)=\mathbf{a}$

  * •

$(\alpha,x)\cdot\mathbf{a}=\mathbf{a}\cdot(\alpha,x)=\mathbf{a}$.

A simple calculation shows that $M$ is a common meadow with $0\cdot
M=(0\times\mathbb{N})\sqcup\\{\mathbf{a}\\}$, where the order is the usual
order in $\mathbb{N}$. The lattice $0\cdot M$ has no atom since $\mathbb{N}$
has no maximal element, and so $M$ is not atomic.

Even though not all pre-meadows with $\mathbf{a}$ are atomic, the pre-meadows
with $\mathbf{a}$ of the form $M(R)$ have atomic lattices, since every unital
commutative ring $R$ has at least one maximal ideal. Since every ideal of $R$
is contained in a maximal ideal, we have that $M(R)$ is atomic.

The following lemma gives a characterization of local common meadows.

######  Lemma 4.6.

Let $M$ be an atomic common meadow, then $M$ is local if and only if $0\cdot
M$ has a unique atom.

###### Proof.

Suppose that $M$ is local but there exist two distinct atoms $0\cdot z,0\cdot
w\in 0\cdot M$. Since they are atoms we must have $0\cdot w+0\cdot
z=\mathbf{a}$. Since the common meadow is local either $0\cdot w=\mathbf{a}$
or $0\cdot z=\mathbf{a}$, which contradicts the hypothesis that they are
atoms.

Suppose now that $0\cdot M$ has a unique atom, say $0\cdot z$. Let $x,y\in M$
be such that $x+y=\mathbf{a}$ and let us first assume that $x\neq\mathbf{a}$
and $y\neq\mathbf{a}$. Then, we must have $0\cdot z\leq 0\cdot x$ and $0\cdot
z\leq 0\cdot y$ with $0\cdot z$ the unique atom of $0\cdot M$. In particular,
$0\cdot z\leq 0\cdot(x+y)=\mathbf{a}$, and so $0\cdot z$ cannot be a atom.
Hence $x=\mathbf{a}$ or $y=\mathbf{a}$, and so $M$ is local. ∎

The condition of being atomic is essential to have the equivalence given in
Lemma 4.6. Indeed, the common meadow in Example 4.5 is a local meadow which is
not atomic since the associated lattice has no atoms.

The term _local meadow_ is justified by the following connection with local
rings.

######  Lemma 4.7.

If $R$ is a commutative Artinian ring, then $R$ is a local ring if and only if
$M(R)$ is a local common meadow.

###### Proof.

Given a unital commutative ring $R$, the atoms of the lattice $0\cdot M(R)$
are in bijection with the maximal ideals of $R$. By definition we have that
$R$ is local if and only if it has a unique maximal ideal, which is equivalent
to $0\cdot M(R)$ having a unique atom. By Lemma 4.6 we then have that $R$ is
local if and only if $M(R)$ is local, as we wanted. ∎

Note that if $R$ is a unital commutative local ring then $M(R)$ may fail to be
a common meadow. However, it will still be a local pre-meadow with
$\mathbf{a}$.

######  Example 4.8.

Consider the pre-meadow with $\mathbf{a}$ defined by the following directed
lattice

${{\mathbb{Z}_{2}\times\mathbb{Z}_{2}}}$${{\mathbb{Z}_{2}}}$${{\mathbb{Z}_{2}}}$${{\mathbb{Z}_{2}}}$${{\\{\mathbf{a}\\}}}$$\scriptstyle{\pi_{1}}$$\scriptstyle{\pi_{1}}$$\scriptstyle{\mathrm{Id}}$$\scriptstyle{\mathrm{Id}}$

Since the set $I_{(1,0)}$ has two different maximal elements we have that this
pre-meadow with $\mathbf{a}$ is not a common meadow. Nevertheless it is a
local pre-meadow since it has a unique atom.

Before we progress we recall the following property of ideals of unital
commutative rings.

######  Proposition 4.9 ([14][Exercise III.3.22).

Let $R_{1}$ and $R_{2}$ be unital commutative rings. Then the ideals of
$R_{1}\times R_{2}$ are of the form $I\times J$ with $I$ an ideal of $R_{1}$
and $J$ an ideal of $R_{2}$.

If $P$ and $Q$ are pre-meadows with $\mathbf{a}$ we can define their Cartesian
product $P\times Q$ in a way that it is a pre-meadow with $\mathbf{a}$. In
[11, Section 4] it is claimed, without a proof, that the Cartesian product of
meadows is again a meadow. We show that the product $P\times Q$ of pre-meadows
with $\mathbf{a}$ is a common meadow if and only if $P$ and $Q$ are themselves
common meadows. We start with a lemma which gives a relation between the
structure of $P$ and $Q$ with the product $P\times Q$.

######  Lemma 4.10.

Let $P$ and $Q$ be pre-meadows with $\mathbf{a}$. Then $P\times Q$ is a pre-
meadow with $\mathbf{a}$ such that $(P\times Q)_{(0\cdot z,0\cdot
w)}=P_{0\cdot z}\times P_{0\cdot w}$. In particular we have

$P\times Q=\bigsqcup_{(0\cdot z,0\cdot w)\in(0\cdot P)\times(0\cdot
Q)}P_{0\cdot z}\times Q_{0\cdot w}.$

###### Proof.

We start by showing that $(P\times Q)_{(0\cdot z,0\cdot w)}=P_{0\cdot z}\times
P_{0\cdot w}$. Let $(x,y)\in(P\times Q)_{(0\cdot z,0\cdot w)}$. Then

$(0\cdot z,0\cdot w)=(x,y)\cdot(0,0)=(0\cdot x,0\cdot y),$

and so $(x,y)\in P_{0\cdot z}\times P_{0\cdot w}$. Similarly, if we take a
$(x,y)\in P_{0\cdot z}\times P_{0\cdot w}$, then

$(x,y)\cdot(0,0)=(0\cdot x,0\cdot y)=(0\cdot z,0\cdot w),$

and so $(P\times Q)_{(0\cdot z,0\cdot w)}=P_{0\cdot z}\times P_{0\cdot w}$.

The result then follows from the fact that

$\begin{split}P\times Q&=\bigsqcup_{(0\cdot z,0\cdot w)\in(0\cdot
P)\times(0\cdot Q)}(P\times Q)_{(0\cdot z,0\cdot w)}\\\ &=\bigsqcup_{(0\cdot
z,0\cdot w)\in(0\cdot P)\times(0\cdot Q)}P_{0\cdot z}\times P_{0\cdot
w}.\qed\end{split}$

Using Lemma 4.10 we can prove that any finite product of common meadows is
still a common meadow.

######  Theorem 4.11.

Let $P$ and $Q$ be pre-meadows with $\mathbf{a}$ then $P\times Q$ is a common
meadow if and only if $P$ and $Q$ are common meadows.

###### Proof.

Suppose that $P$ and $Q$ are common meadows. By Theorem 2.5 we have that
$P\times Q$ is a common meadow if for all $(x,y)\in P\times Q$ the set

$I_{(x,y)}=\\{(0\cdot z,0\cdot w)\in 0\cdot P\times 0\cdot Q\mid(x+0\cdot
z,y+0\cdot w)\in(P_{0\cdot z}\times Q_{0\cdot w})^{\times}\\}$

has a greatest element. In fact, by Lemma 4.10 we have that $(P\times
Q)_{(0\cdot z,0\cdot w)}=P_{0\cdot z}\times P_{0\cdot w}$, and so an element
$(x+0\cdot z,y+0\cdot w)$ is invertible in $P_{0\cdot z}\times P_{0\cdot w}$
if and only if $x+0\cdot z$ is invertible in $P_{0\cdot z}$ and $y+0\cdot w$
is invertible in $Q_{0\cdot w}$, that is we have that $I_{(x,y)}=I_{x}\times
I_{y}$.

Since $P$ and $Q$ are common meadows, $I_{x}$ and $I_{y}$ both have a greatest
element and so $I_{(x,y)}$ must also have a greatest element. We conclude that
$P\times Q$ is a common meadow.

Suppose now that $P\times Q$ is a common meadow, and let us see that $P$ is a
common meadow. Consider the function $\psi:P\to P\times Q$ defined by
$\psi(x)=(x,\mathbf{a})$. It is straightforward to check that $\psi$ is an
homomorphism of semigroups for both operations. In particular, the restriction
$\tilde{\psi}:P_{0\cdot z}\to P_{0\cdot z}\times\\{\mathbf{a}\\}$ is a ring
homomorphism that commutes with the transition maps. Then, given $x\in P$ and
$0\cdot z\in 0\cdot P$ (such that $0\cdot z\cdot x=0\cdot z$) we have that
$x+0\cdot z\in P_{0\cdot z}^{\times}$ if and only if $P_{0\cdot
z}^{\times}\times\\{\mathbf{a}\\}$. Then
$I_{(x,\mathbf{a})}=I_{x}\times\\{\mathbf{a}\\}$ and since $P\times Q$ is a
common meadow we have that $I_{(x,\mathbf{a})}=I_{x}\times\\{\mathbf{a}\\}$
has a greatest element and so $I_{x}$ also has a greatest element and
consequently $P$ is a common meadow. The argument for $Q$ is similar. ∎

Next we will see that a decomposition of a unital commutative ring $R$ gives
rise to a decomposition of $M(R)$. In particular, common meadows of the form
$M(R)$ with $R$ an unital commutative Artinian ring decompose into a product
of local common meadows.

######  Theorem 4.12.

Let $R=\bigoplus_{i=1}^{n}R_{i}$ be a decomposition of a unital commutative
ring. Then

$M(R)\simeq\prod_{i=1}^{n}M(R_{i}).$

###### Proof.

We start by showing that

(1) $M(R)\simeq\bigsqcup_{I_{i}\trianglelefteq
R_{i}}\prod_{i=1}^{n}R_{i}/I_{i}.$

We consider only the case $R=R_{1}\times R_{2}$, since the general case then
follows by an easy induction on $n$. By Proposition 4.9, the ideals of $R$ are
of the form $I\times J$, where $I\trianglelefteq R_{1}$ and $J\trianglelefteq
R_{2}$.

We have that

$\begin{split}M(R)&=\bigsqcup_{K\trianglelefteq R_{1}\times R_{2}}(R_{1}\times
R_{2})/K\\\ &=\bigsqcup_{I\trianglelefteq R_{1},J\trianglelefteq
R_{2}}(R_{1}\times R_{2})/(I\times J)\\\ &\simeq\bigsqcup_{I\trianglelefteq
R_{1},J\trianglelefteq R_{2}}(R_{1}/I\times R_{2}/J).\end{split}$

Where the isomorphism is given by $(x,y)+I\times J\mapsto(x+I,y+J)$. Hence
$M(R)\simeq\bigsqcup_{I_{i}\trianglelefteq R_{i}}\prod_{i=1}^{n}R_{i}/I_{i}$.

Now, by Lemma 4.10 and equation (1) we have that

$\prod_{i=1}^{n}M(R_{i})=\bigsqcup_{I_{i}\trianglelefteq
R_{i}}\prod_{i=1}^{n}R_{i}/I_{i}\simeq M(R),$

which entails the result. ∎

By Theorem 4.11 we have that $M(R)$ is a common meadow if and only if
$M(R_{i})$ is a common meadow for all $i\in\\{1,\cdots,n\\}$.

######  Definition 4.13.

Let $M$ be a common meadow. If $M\simeq\prod_{i=1}^{n}M_{i}$ with $M_{i}$
local meadows, we say that $M$ _decomposes_ into (the product of) local
meadows.

We are now able to prove the first part of the main result.

######  Corollary 4.14.

If $R$ is a commutative unital Artinian ring, then $M(R)$ decomposes into a
finite product of local common meadows.

###### Proof.

Let $R$ be a unital commutative Artinian ring. Then, there exist local rings
$R_{i}$ such that $R\simeq\bigoplus_{i=1}^{n}R_{i}$. By Lemma 4.12 we have
that $M(R)\simeq\prod_{i=1}^{n}M(R_{i})$. Hence, each $M(R_{i})$ is a local
meadow, by Lemma 4.7. ∎

Corollary 4.14 shows that in case $R$ is a unital commutative Artinian ring,
the common meadow $M(R)$ admits a decomposition into local meadows. We now
turn to show that such decomposition is essentially unique.

The following result provides a useful characterization of atomic meadows in
terms of its components.

######  Lemma 4.15.

Let $M$ be a common meadow, with $M\simeq\prod_{i=1}^{t}M_{i}$. Then $M$ is
atomic if and only if $M_{i}$ is atomic for all $i\in\\{1,\dots,t\\}$.

###### Proof.

Let us consider the case $t=2$, i.e. $M\simeq M_{1}\times M_{2}$, and then
$0\cdot M\simeq 0\cdot M_{1}\times 0\cdot M_{2}$. The general case follows by
an easy induction on $t$.

Suppose first that $M$ is atomic. Then, for each $(x,\mathbf{a})\in 0\cdot
M_{1}$, there is an atom $(a,b)\in 0\cdot M_{1}\times 0\cdot M_{2}$ such that
$(a,b)\leq(x,\mathbf{a})$. This means that $b=\mathbf{a}$, since $\mathbf{a}$
is the minimum, and $a\in 0\cdot M_{1}$ is an atom such that $a\leq x$, which
means that $0\cdot M_{1}$ is atomic. With a similar argument one sees that
$0\cdot M_{2}$ is atomic.

Suppose now that $0\cdot M_{1}$ and $0\cdot M_{2}$ are atomic and take a
$(x,y)\in 0\cdot M_{1}\times 0\cdot M_{2}$. Then there exist atoms $x_{1}\in
0\cdot M_{1}$ and $y_{1}\in 0\cdot M_{1}$ such that $x_{1}\leq x$ and
$y_{1}\leq y$, which means that $(x_{1},y_{1})\leq(x,y)$. Since $x_{1}$ and
$y_{1}$ are atoms we have that $(x_{1},y_{1})$ is also an atom and so $0\cdot
M$ is atomic. ∎

######  Lemma 4.16.

Every decomposition of an atomic common meadow into local meadows has the same
number of factors.

###### Proof.

Let $M$ be a common meadow with atomic lattice such that
$M=\prod_{i=1}^{t}M_{i}$, where $M_{i}$ is a local meadow, for all
$i\in\\{1,\cdots,t\\}$. In particular each $M_{i}$ is atomic by Lemma 4.15,
and has a unique atom, by Lemma 4.6.

Let $a_{i}$ be the unique atom of $0\cdot M_{i}$ and $\mathbf{a}_{j}$ the
inverses of zero in each $M_{j}$. One can easily see that the atoms of $0\cdot
M$ are of the form $\mathbf{a}_{1}\times\cdots\times\mathbf{a}_{i-1}\times
a_{i}\times\mathbf{a}_{i+1}\cdots\times\mathbf{a}_{t}$, that is, the elements
of $0\cdot M$ that are products of the $\mathbf{a}_{j}$’s of the rings
$M_{j}$, with the exception of exactly one occurrence of $a_{i}$. Then the
number of atoms of $M$ is exactly $t$, and therefore any other decomposition
into local meadows must also have $t$ factors. ∎

######  Proposition 4.17.

Let $R$ be a unital commutative Artinian ring that decomposes into local rings
$R=\bigoplus_{i=1}^{t}R_{i}$. If $M(R)=\prod_{i=1}^{t}M_{i}$, then there is a
permutation function $\pi\in S_{t}$ such that $M_{i}=M(R_{\pi(i)})$.

###### Proof.

We again consider the case where $t=2$ since the general case follows by an
easy induction on $t$. So, we may consider $R=S\times T$ and $M(R)\simeq
M\times N$. The general case follows by an easy induction on $t$. We have that
$M_{0}\times N_{0}\simeq S\times T$ is a decomposition into local rings,
because if $M_{0}$ is not a local ring, then it would decompose into the
product of local rings (since $M_{0}\simeq M_{0}\times N_{0}/0\times N_{0}$ is
Artinian) and the decomposition into local rings would not be unique. Without
loss of generality we can assume that $M_{0}\simeq S$ and $N_{0}\simeq T$.

By hypothesis, $M\times N\simeq M(R)\simeq M(S)\times M(T)$ so there is a
bijection

$\psi:\\{I\times J\mid I\trianglelefteq S,J\trianglelefteq T\\}\to 0\cdot
M\times 0\cdot N.$

Hence the following diagram commutes

${{S\times T}}$${{M_{0}\times N_{0}}}$${{S/I\times T/J}}$${{M_{\psi(I\times
J)_{1}}\times N_{\psi(I\times
J)_{2}}}}$$\scriptstyle{\Phi_{0}}$$\scriptstyle{\pi_{I}\times\pi_{J}}$$\scriptstyle{f_{\psi(I\times
J)_{1}}\times f_{\psi(I\times J)_{2}}}$$\scriptstyle{\Phi_{I\times J}}$

Here the horizontal arrows represent the isomorphism $\Phi:M(S)\times M(T)\to
M\times N$. Note that $\Phi_{0}(S)=M_{0}$ and $\Phi_{0}(T)=N_{0}$. Since the
diagram is commutative we have that $\Phi_{I\times J}(S/I\times
0)=M_{\psi(I\times J)_{1}}$ and $\Phi_{I\times J}(0\times T/J)=N_{\psi(I\times
J)_{2}}$ and hence $M(S)\simeq M$ and $M(T)\simeq N$. ∎

The proof of Theorem 4.3 is now straightforward.

###### Proof of Theorem 4.3.

Let $R$ be a unital commutative Artinian ring. By Corollary 4.14 we have that
$M(R)\simeq\prod_{i=1}^{t}M(R_{i})$ and, by Proposition 4.17, this
decomposition is unique up to permutation. ∎

We would like to point out that not all common meadows decompose into a
product of local meadows, as illustrated by the following example.

######  Example 4.18.

Let $M$ be the common meadow defined by the following directed lattice

${{\mathbb{Z}_{2}}}$${{\mathbb{Z}_{2}}}$${{\mathbb{Z}_{2}}}$${{\\{\mathbf{a}\\}}}$$\scriptstyle{\mathrm{Id}}$$\scriptstyle{\mathrm{Id}}$

If $M$ could be decomposed into $M\simeq N\times N^{\prime}$, then
$\mathbb{Z}_{2}=N_{0}\times N_{0}^{\prime}$ and so $N_{0}$ or $N^{\prime}_{0}$
would need to be $0$ since $\mathbb{Z}_{2}$ is a local ring. However, even if
$M_{0}$ is not a local ring, it can happen that $M$ is indecomposable. Since a
decomposition of a meadow also gives a lattice decomposition we have that
$|0\cdot M|$ is prime then $M$ is indecomposable.

In conclusion, a decomposition of a meadow $M$ also gives a decomposition of
the lattice $0\cdot M$ and a decomposition of the rings $M_{0\cdot x}$, for
all $0\cdot x\in 0\cdot M$.

We conclude the paper with some open questions: Our first question is a sort
of converse of Theorem 3.3.

######  Question.

Are there other classes of unital commutative rings for which $M(R)$ is a
common meadow?

######  Question.

Is it possible to characterize which common meadows decompose into the product
of local meadows?

## References

  * [1] J. Bergstra, Arithmetical datatypes, fracterms, and the fraction definition problem, Transmathematica, (2020).
  * [2] J. Bergstra, Y. Hirshfeld, and J. Tucker, Fields, Meadows and Abstract Data Types, Springer Berlin Heidelberg, Berlin, Heidelberg, 2008, pp. 166–178.
  * [3] J. Bergstra and A. Ponse, Division by Zero in Common Meadows, Springer International Publishing, Cham, 2015, pp. 46–61.
  * [4] , Arithmetical datatypes with true fractions, Acta Inform., 57 (2020), pp. 385–402.
  * [5] J. Bergstra and J. Tucker, The rational numbers as an abstract data type, J. ACM, 54 (2007), p. 7–es.
  * [6] , On the axioms of common meadows: Fracterm calculus, flattening and incompleteness, The Computer Journal, 66 (2023), pp. 1565–1572.
  * [7] J. A. Bergstra and J. V. Tucker, Fracterm calculus for signed common meadows, Transmathematica, (2024).
  * [8] J. A. Bergstra and J. V. Tucker, Rings with common division, common meadows and their conditional equational theories, 2024.
  * [9] E. Bottazzi and B. Dinis, Flexible involutive meadows, 2023.  (to appear in the Journal of Applied Logics) arXiv: 2309.01284.
  * [10] C. W. Curtis and I. Reiner, Methods of representation theory. Vol. I, Pure and Applied Mathematics, John Wiley & Sons, Inc., New York, 1981.  With applications to finite groups and orders, A Wiley-Interscience Publication.
  * [11] J. Dias and B. Dinis, Strolling through common meadows, Communications in Algebra, (2024), pp. 1–28.
  * [12] J. Dias and B. Dinis, Towards an enumeration of finite common meadows, International Journal of Algebra and Computation, (2024).
  * [13] D. Eisenbud, Commutative algebra: with a view toward algebraic geometry, vol. 150, Springer Science & Business Media, 2013.
  * [14] T. W. Hungerford, Algebra, vol. 73, Springer Science & Business Media, 2012.

### Acknowledgments

Both authors acknowledge the support of FCT - Fundação para a Ciência e
Tecnologia under the project: 10.54499/UIDB/04674/2020, and the research
center CIMA – Centro de Investigação em Matemática e Aplicações.

The second author also acknowledges the support of CMAFcIO – Centro de
Matemática, Aplicações Fundamentais e Investigação Operacional under the
project UIDP/04561/2020.


# PlaTe: Visually-Grounded Planning
with Transformers in Procedural Tasks

Jiankai Sun∗, De-An Huang†, Bo Lu∗, Yun-Hui Liu∗, Bolei Zhou∗, Animesh Garg†,‡
∗Chinese University of Hong Kong, †Nvidia, ‡University of Toronto & Vector
Institute.

###### Abstract

In this work, we study the problem of how to leverage instructional videos to
facilitate the understanding of human decision-making processes, focusing on
training a model with the ability to plan a goal-directed procedure from real-
world videos. Learning structured and plannable state and action spaces
directly from unstructured videos is the key technical challenge of our task.
There are two problems: first, the appearance gap between the training and
validation datasets could be large for unstructured videos; second, these gaps
lead to decision errors that compound over the steps. We address these
limitations with Planning Transformer (PlaTe), which has the advantage of
circumventing the compounding prediction errors that occur with single-step
models during long model-based rollouts. Our method simultaneously learns the
latent state and action information of assigned tasks and the representations
of the decision-making process from human demonstrations. Experiments
conducted on real-world instructional videos and an interactive environment
show that our method can achieve a better performance in reaching the
indicated goal than previous algorithms. We also validated the possibility of
applying procedural tasks on a UR-5 platform. Please see
pair.toronto.edu/plate-planner for additional details.

##  I Introduction

Intelligent reasoning in embodied environments requires that an agent has
explicit representations of parts or aspects of its environment to reason
about [1]. As a generic reasoning application, action planning and learning is
a crucial skill for cognitive robotics. Planning, in the traditional AI sense,
means deliberating about a course of actions for an agent to take for
achieving a given set of goals. The desired plan is a set of actions whose
execution transforms the initial situation into the goal situation (goal
situations need not be unique). Normally, actions in a plan cannot be executed
in arbitrary sequence, but have to obey an ordering, ensuring that all
preconditions of each action are valid at the time of its execution. In
practice, there are two challenges for planning. First, typically not all
information that would be needed is available. Planning is meant for real
environments in which many parameters are unknown or unknowable. Second, even
if everything for a complete planning were known, then it would very likely be
so computationally intensive that the real world would run too slowly. Thus,
many planning systems and their underlying planning algorithms accept the
restrictive assumptions of information completeness, determinism,
instantaneousness, and idleness [1, 2].

Figure 1: PlaTe Overview. Given a visual observation as start and goal, the
encoder $f(\cdot)$ extracts the feature about the planning trajectory. This
transformer-based procedure planning model is responsible for learning
plannable latent representations $\hat{s}$ and actions $\hat{a}$.

Procedure planning in instructional videos [3] (as shown in Figure 1) aims to
make goal-conditioned decisions by planning a sequence of high-level actions
that can bring the agent from current observation to the goal. Planning in
instructional videos is a meaningful task since the ability to perform
effective planning is crucial for building an instruction following agent.
Although learning from instructional videos is natural to humans, it is
challenging for the AI system because it requires understanding human
behaviors in the videos, focusing on actions and intentions. How to learn
structured and plannable state and action spaces directly from unstructured
videos is the key technical challenge of our task. Other challenges include:
1) Learning to make accurate predictions with high-dimensional observations is
still challenging [4], especially for visually complex long-horizon tasks. 2)
Appearance gap between the training and validation dataset could be large for
unstructured videos. Thus, the agent needs to have the generalization
capability. 3) These gaps lead to decision errors that compound over the
steps.

It is crucial for autonomous agents to plan for complex tasks in everyday
settings from visual observations [3]. Although reinforcement learning
provides a powerful and general framework for decision making and control, its
application in practice is often hindered by the need for extensive feature
and reward engineering [5]. Moreover, deep RL algorithms are often sensitive
to factors such as reward sparsity and magnitude, making well-performing
reward functions particularly difficult to engineer. In many real-world
applications, specifying a proper reward function is difficult.

In this paper, we proposed a new framework for procedure planning from visual
observations. We address these limitations with a new formulation of procedure
planning and novel algorithms for modeling human behavior through a
Transformer-based planning network PlaTe. Our method simultaneously learns the
high-level action planning of assigned tasks and the representations of the
decision-making process from human demonstrations.

We summarize our contributions as follows:

  * •

We proposed a novel method, Planning Transformer network (PlaTe), for
procedure planning in instructional videos task, which enjoys the advantage of
long-term planning.

  * •

We integrate Beam Search to PlaTe to prevent it from large search
discrepancies, and eliminate the performance degradation.

  * •

Experimental results show that our framework outperforms the baselines in the
procedure planning task on both a real-world dataset and an interactive
environment. We also validated the possibility of applying procedural tasks on
a real UR-5 platform.

##  II Related Work

Self-Attention and Transformer. Transformer-based architectures, eschew the
use of recurrence in neural networks and instead trust entirely on self-
attention mechanisms to draw global dependencies between inputs and outputs.
Self-attention [6] is particularly suitable for procedure planning, which can
be seen as a sequence modeling task. Compared with Recurrent Neural Networks
(RNNs), long short-term memory (LSTM) [7] and gated recurrent neural networks
[8], the advantages of self-attention includes avoiding compressing the whole
past into a fixed-size hidden state, less total computational complexity per
layer, and more parallelizable computations. In this paper, thanks to
Transformers’ computational efficiency and scalability, we explore the
possibility of marrying Transformer-based architecture for procedure planning.

Learning to Plan from Pixels. Another related work is learning dynamics models
for model-based RL [9, 10]. Recent works have shown that deep networks can
learn to plan directly from pixel observations in domains such as table-top
manipulation [11, 12], navigation in VizDoom [13], and locomotion in joint
space [14]. Universal Planning Networks (UPN) [12] assumes the action space to
be differentiable and uses a gradient descent planner to learn representations
from expert demonstrations. Prior work [3] proposes the conjugate dynamics
model to expedite the latent space learning, but suffers from compounding
error. Without using explicit action supervision, causal InfoGAN [11] extracts
state representations by learning salient features. Instead, our method builds
a transformer-based model that is amenable to long-horizon planning, operating
directly on real-world videos and handling the semantics of actions with
sequential learning.

Learning from Instructional Videos. The interest has dramatically increased in
recent years in understanding human behaviors by analyzing instructional
videos [15, 16]. Event discovery tasks such as action recognition and temporal
action segmentation [17, 18, 19], state understanding [20], and video
summarization / captioning [21, 15] study recognition of human actions in
video sequences. The others works [22] perform egocentric action anticipation
model the relationships between past, future events, and incomplete
observations. Action label prediction [23, 24] addresses the problem of
anticipating all activities within a time horizon. However, the correct answer
is often not unique due to the large uncertainty in human actions. Unlike the
previous works that predict "what is happening" or "what is going to happen",
we focus on understanding decision-making processes given the start
observation and the visual goal.

Figure 2: PlaTe Framework. Given the start and goal visual observations,
encoder $f$ outputs the latent representations $\hat{s}$. We set
$\hat{a}_{0}=0$. The latent representation and predicted action are inferred
using transformer-based action prediction model $h(\cdot)$ and state
prediction model $g(\cdot)$. During training, the ground-truth action $a$ and
state $s$ are given. During inference, we use Beam Search to enhance the
trained $h(\cdot),g(\cdot)$. The right part shows the Transformer architecture
we used for planning model.

##  III Our Method: PlaTe

###  III-A Problem Setup

We consider a similar setup to [3]: given the start visual observation $o_{t}$
and a visual goal $o_{g}$ that indicates the desired outcome for a particular
task. During training, we have access to the observation-action pairs
$\\{(o_{t:g},a_{t:g})\\}\sim\pi_{E}$ that were collected by an expert
attempting to reach the goals. When testing, only the start visual observation
$o_{t}$ and a visual goal $o_{g}$ are given. Our objective is to plan a
sequence of actions $[\hat{a}_{t},\dots,\hat{a}_{t+T-1}]$ that can bring the
underlying state of $o_{t}$ to that of $o_{g}$. $T$ is the horizon of
planning, which means the number of task-level action steps the model is
allowed to take. Figure 1 shows a goal-oriented plannable example where the
intermediate steps of performing a complex planning task are planned.

Our key insight is that the compounding error can be reduced by jointly
learning the state and action representation with Transformer-based
architecture. As shown in the overall architecture in Figure 2, the procedure
planning problem $p(\hat{a}_{1:T}|o_{1},o_{T})$ is formulated as

$\begin{split}&p(\hat{a}_{1:T}|o_{1},o_{T})\\\
=&\textrm{Pr}(\hat{s}_{1}|o_{1})\textrm{Pr}(\hat{s}_{T}|o_{T})\prod_{t=1}^{T}\textrm{Pr}(\hat{a}_{t}|\hat{s}_{t},\hat{a}_{t-1},\hat{s}_{T})\textrm{Pr}(\hat{s}_{t+1}|\hat{s}_{t},\hat{a}_{t},\hat{s}_{T}).\end{split}$
(1)

In the following sections, we first discuss how to encode the latent semantic
representation. Then, we will introduce how to solve the long-term procedure
planning task with transformer-based architecture. Lastly, we will discuss how
to apply learned representation to solve the procedure planning by integrating
Beam Search.

###  III-B Latent Semantic Representation

First, we use the state encoder $\hat{s}=f(o)$ that encodes the visual
observation to a latent semantic representation.

The remaining question is: how to learn a planning model
$p(\hat{a}_{1:T},\hat{s}_{1:T}|\hat{s}_{1},\hat{s}_{T})$ to reconstruct the
action sequence and corresponding latent state representation? We assume the
underlying process in Figure 1 is a fully observable goal-conditioned Markov
Decision Process ($\mathcal{S,A,T}$), where $\mathcal{S}$ is the state space,
$\mathcal{A}$ is the action space, $\mathcal{T:S\times A\rightarrow S}$ is the
unknown transition probability distribution. We denote
$h(\hat{a}_{t}|\hat{s}_{t},\hat{a}_{t-1},\hat{s}_{T})$ as the _action
prediction model_ conditioned on the current state, previous action, and goal
state, and $g(\hat{s}_{t+1}|\hat{s}_{t},\hat{a}_{t},\hat{s}_{T})$ as the
_state prediction model_ conditioned on the previous state, goal state, and
previous action. They plan the sequence of actions and hidden states that
serves as a path from the initial state to the goal state. In this way, we are
able to factorizes the planning model
$p(\hat{a}_{1:T},\hat{s}_{1:T}|\hat{s}_{1},\hat{s}_{T})$ as:

$\begin{split}&p(\hat{a}_{1:T},\hat{s}_{1:T}|\hat{s}_{1},\hat{s}_{T})\\\
=&\prod_{t=1}^{T}h(\hat{a}_{t}|\hat{s}_{t},\hat{a}_{t-1},\hat{s}_{T})g(\hat{s}_{t+1}|\hat{s}_{t},\hat{a}_{t},\hat{s}_{T}),\end{split}$
(2)

where we use the convention that $\hat{s}_{0}=0$, $\hat{a}_{0}=0$.

However, there are still several vital difficulties: I) compounding error, II)
generalization capability from the training set to the validation set on the
real-world dataset. We extend the Transformer framework to tackle these
problems.

###  III-C Transition Transformer

We propose a transformer-based network architecture that can learn the action-
state correlation and generate planning sequences. The overview of this
architecture is shown in Figure 2. We introduce some critical design choices
that assist in learning cross-modal correspondence and, more importantly,
improve the accuracy of generated planning sequences. These choices include
cross-modal transformer architecture, attention mechanism-causal attention
[25] vs. full attention [26] for each transformer and the supervision scheme.
Our design choices are explained in detail below.

We introduce two cross-modal transformers: the action transformer
$h(\hat{a}_{t}|\hat{s}_{t},\hat{a}_{t-1},\hat{s}_{T})$, which learns the
correspondence between previous action feature $\hat{a}_{t-1}$ and state
feature $\hat{s}_{t}$, $\hat{s}_{T}$ and generates the action prediction
$\hat{a}_{t}$; the state transformer
$g(\hat{s}_{t+1}|\hat{s}_{t},\hat{a}_{t},\hat{s}_{T})$, which learns the
correspondence between the state feature $\hat{s}_{t}$, $\hat{s}_{T}$ and
action feature $\hat{a}_{t}$ and generates the future state prediction
$\hat{s}_{t+1}$. Attention is the core of transformer network [6, 27]. We set
up four different settings: causal attention [25], and full-attention [26]
with future-$\\{1,2,3\\}$ supervision. Specifically, the output of the
attention layer, the context vector $\bm{C}$ is computed using the query
vector $\bm{Q}$ and the key $\bm{K}$ value $\bm{V}$ pair from the input with a
mask $\bm{M}$ via

$\begin{split}\bm{C}&={\rm Attn}(\bm{Q,K,V,M})\\\ &={\rm
softmax}\left(\frac{\bm{QK}^{T}+\bm{M}}{\sqrt{D}}\right)\bm{V},\end{split}$
(3)

where $D$ is the number of channels in the attention layer. The look-ahead-
mask $\bm{M}$ is a triangular matrix.

###  III-D Beam Search in Procedure Planning

Given an action transformer model parameterized by $\theta$ and an input $x$,
which contains the information of current state, previous action step, and
goal state, the problem of procedure planning task consists of finding a
action sequence $\hat{a}$ such that $\hat{a}=\operatorname*{arg\,max}_{a\in
A}P_{\theta}(a|x)$, where $A$ is the set of all sequences.
$a=\\{\hat{a}_{1},\cdots,\hat{a}_{T}\\}$ can be regarded as a sequence of
tokens from vocabulary $\mathcal{V}$, where $T$ is the length of the sequence
$\hat{a}$. Then $P_{\theta}(\hat{a}|x)$ can be factored as

$\begin{split}\log
P_{\theta}(\hat{a}|x)&=\log\prod_{t=1}^{T}P_{\theta}(\hat{a}_{t}|\\{\hat{s}_{1},\hat{a}_{0}\\};\cdots;\\{\hat{s}_{t},\hat{a}_{t-1}\\};\hat{s}_{T})\\\
&=\sum_{t=1}^{T}\log
P_{\theta}(\hat{a}_{t}|\\{\hat{s}_{1},\hat{a}_{0}\\};\cdots;\\{\hat{s}_{t},\hat{a}_{t-1}\\};\hat{s}_{T}).\end{split}$
(4)

In the context of searching for procedure planning, _search discrepancy_ means
extending a partial sequence with a token that is not the most probable one.
More formally, a sequence $\hat{a}$ is considered to have a search discrepancy
at time step $t$ if

$\begin{split}&\log
P_{\theta}(\hat{a}_{t}|\\{\hat{s}_{1},\hat{a}_{0}\\};\cdots;\\{\hat{s}_{t},\hat{a}_{t-1}\\};\hat{s}_{T})\\\
&<\max_{\hat{a}\in\mathcal{V}}\log
P_{\theta}(\hat{a}|\\{\hat{s}_{1},\hat{a}_{0}\\};\cdots,\\{\hat{s}_{t},\hat{a}_{t-1}\\};\hat{s}_{T}),\end{split}$
(5)

The discrepancy gap is the difference in log-probability between the most
likely token and the chosen token [28]. At time step $t$, the discrepancy gap
is

$\begin{split}\max_{\hat{a}\in\mathcal{V}}&[\log
P_{\theta}(\hat{a}|\\{\hat{s}_{1},\hat{a}_{0}\\};\cdots;\\{\hat{s}_{t},\hat{a}_{t-1}\\};\hat{s}_{T})\\\
&-\log
P_{\theta}(\hat{a}_{t}|\\{\hat{s}_{1},\hat{a}_{0}\\};\cdots,\\{\hat{s}_{t},\hat{a}_{t-1}\\};\hat{s}_{T})].\end{split}$
(6)

To avoid long-term procedure planning from significant search discrepancies,
we introduce the discrepancy-constrained Beam Search during the _inference
phase of procedure planning_. Given a threshold $\mathcal{N}$, we modify
$A_{t}$, the set of possible action sequence at step $t$, to only include the
top $\mathcal{N}$ one-token extensions in each beam. The action log-
probability output by action prediction model $h(\cdot)$ is used as the score
function. The inference algorithm is shown as Algorithm 1. In this way, we can
eliminate the performance degradation.

Figure 3: Attention Mechanism Comparison. Causal models are often supervised
to predict the immediate next future for each input tensor, while full
attention predict the $N$ future time steps from the last timestamp.

###  III-E Learning

As shown in Figure 2, we have three main components to optimize: state encoder
$f$, action prediction model $h$, and state prediction model $g$. We refer to
the expert trajectory as $\tau^{E}=\\{(s_{t}^{E},a_{t}^{E})\\}$ and predicted
trajectory $\tau=\\{(\hat{s}_{t},\hat{a}_{t})\\}$ as state-action pairs
visited by the current planning model.

We optimize by descending the gradient in Equation 7.

$\min_{\theta}\sum_{t=1}^{T}||\hat{s}_{t}-s_{t}^{E}||_{2}+{\rm
CE}(\hat{a}_{t},a_{t}^{E})$ (7)

where ${\rm CE}$ is the cross-entropy loss. In training, $T$-step sequence is
output once. In testing, single-step inference is made with Beam Search.

Algorithm 1 PlaTe: Planning Inference Phase

Input: sequence $\mathbf{x}$, maximum hypothesis length $n_{\max}$, beam nodes
buffer $B$, buffer size $\mathcal{N}$, scoring function
$\textrm{score}(\cdot,\cdot)$, maximum beam size $k$, planning model
$p(\hat{s}_{t}^{i},\hat{a}_{t}^{i}|\hat{s}_{t-1}^{i},\hat{a}_{t-1}^{i},\hat{s}_{T}^{i})$
Output: searched sequence $B.\rm{max()}$

$B_{0}\leftarrow\\{<0,\rm{BOS}>\\}$

for $t\in\\{1,\cdots,n_{\max}-1$} do

$B\leftarrow\emptyset$

for $<w,(\hat{s}_{t-1}^{i},\hat{a}_{t-1}^{i},\hat{s}_{T}^{i})>\in B_{t-1}$ do

if $\hat{s}_{t-1}^{i}.{\rm last()}={\rm EOS}$ then

$B.{\rm add}(<w,(\hat{s}_{t-1}^{i},\hat{a}_{t-1}^{i},\hat{s}_{T}^{i})>)$

continue

end if

$(\hat{s}_{t}^{i},\hat{a}_{t}^{i})\leftarrow
p(\hat{s}_{t}^{i},\hat{a}_{t}^{i}|\hat{s}_{t-1}^{i},\hat{a}_{t-1}^{i},\hat{s}_{T}^{i})$

$w\leftarrow{\rm score}(\hat{s}_{t}^{i},\hat{a}_{t}^{i},\hat{s}_{T}^{i})$

$B.{\rm add}(<w,(\hat{s}_{t}^{i},\hat{a}_{t}^{i},\hat{s}_{T}^{i})>)$

end for

$B_{t}\leftarrow B.{\rm top}(k)$

end for

return $B.\rm{max()}$

##  IV Experiments

In our experiments, we aim to answer the following questions: (1) Is PlaTe
efficient and scalable to procedure planning tasks? (2) Can PlaTe learn to
plan on the interactive environment? (3) Can PlaTe learn procedure planning
that is robust in the real-world? To answer Question 1, we evaluate PlaTe on
CrossTask, a real-world offline instructional video dataset. We show procedure
planning with our algorithm performs better on the CrossTask dataset than
previous methods. To answer Question 2, we compare PlaTe with baselines on
ActioNet. We find that our method can perform procedure planning in an
interactive setup while vastly outperforming baselines. To answer Question 3,
we evaluate our method on a real-world UR-5 robot arm platform. We also
perform an ablation study on attention mechanism design, input type, and
action sequence length. It is worth noting that, compared with the baselines,
our method has an advantage in long-term procedure planning due to the
transformer-based architecture and discrepancy-constrained Beam Search.

Figure 4: Procedure planning qualitative results on CrossTask. Procedure Planning qualitative results for _Make Pancakes_. The top row describes the correct action sequence required to "make pancakes". To examine our method’s robustness, We vary the start and goal observations to evaluate our method. The results show that our approach is robust to perform planning within different stages in the video. TABLE I: CrossTask Results. Our model significantly outperforms baselines with $\sim 50\%$ improvement in terms of success rate. Method | Prediction Length $T=3$ | Prediction Length $T=4$
---|---|---
Success Rate (%) | Accuracy (%) | mIoU (%) | Success Rate (%) | Accuracy (%) | mIoU (%)
Random |  $<$0.01 | 0.94 | 1.66 |  $<$0.01 | 0.83 | 1.66
RB [21] | 8.05 | 23.30 | 32.06 | 3.95 | 22.22 | 36.97
RL [29] | 8.25 | 24.20 | 33.25 | 4.16 | 23.29 | 38.63
WLTDO [14] | 1.87 | 21.64 | 31.70 | 0.77 | 17.92 | 26.43
UAAA [24] | 2.15 | 20.21 | 30.87 | 0.98 | 19.86 | 27.09
UPN [12] | 2.89 | 24.39 | 31.56 | 1.19 | 21.59 | 27.85
DDN [3] | 12.18 | 31.29 | 47.48 | 5.97 | 27.10 | 48.46
PlaTe (Ours) | $\bm{18.50}$ | $\bm{39.33}$ | $\bm{65.91}$ | $\bm{14.00}$ | $\bm{35.29}$ | $\bm{55.36}$

###  IV-A Experimental Setup

Datasets. We evaluate PlaTe on an instructional video dataset CrossTask [16]
and an interactive dataset ActioNet [30], which is based on AI2-THOR [31]. For
real-world UR-5 experiments, we collect a _UR-5 Reaching Dataset_ which
consists of 100 trajectories (2150 first-person-view RGB image and
corresponding action pairs) as a training set and evaluate on a real UR-5
platform. We perform an ablation study on CrossTask dataset.

Baselines. We compare to the following methods:

\- Random Policy. Random Policy selects an action randomly from the full
actions candidate set, which serves as the empirical performance lower bound.

\- Retrieval-based (RB) [21]. Inspired by Sun  _et al._ [21], the procedure
planning problem can be approached from a more static view: RB finds the
nearest neighbor of the start and goal visual observations pair by querying
the training set and then directly output the actions in between.

\- Reinforcement Learning (RL) [29]. We adapt Model-based Policy Optimization
(MBPO) [29], one of the most popular model-based RL (MBRL) algorithm as our
offline RL baseline. We first learn the latent space and then use the
L2-distance in the latent space as a reward for the RL algorithm. The farther
a state is from the final goal in the latent space, the lower the reward is.
It can be seen that, without Transformer architecture, MBRL performs not as
well as our model.

\- WLTDO [14]. WLTDO plans using a recurrent model for egocentric videos.
Given two non-consecutive observations, WLTDO predicts the intermediate action
sequence. We add a softmax layer to the original model to output discrete
actions.

\- UAAA [24]. UAAA is a two-step approach to infer the action labels in the
observed frames with RNN-HMM architecture, and then to predict the future
action labels using an auto-regressive model. UAAA is modified to condition on
both the start visual observation frame and the visual goal frame as our
baseline.

\- Universal Planning Networks (UPN) [12]. Aiming to learn a plannable
representation using supervision, UPN assumes a continuous and differentiable
action space to enable gradient-based planning by minimizing the supervised
imitation loss. We adapt UPN by adding a softmax layer to output discrete
actions.

\- Dual Dynamics Networks (DDN) [3]. As the first work to propose the
procedure planning task in instructional videos, DDN learns the conjugate
dynamics model and forward dynamics model, and explicitly leverages the
structured priors to perform sample-based planning.

Metrics. We use the following metrics:

\- Success Rate. Success rate measures the correctness of _entire action
sequence_. For the offline CrossTask dataset, the planned action sequence is
considered successful only if each planned action matches the ground-truth.
For the interactive ActioNet and _UR5-Reaching_ dataset, a planned sequence of
actions is considered successful only if the planned sequence of actions
reaches the goal.

\- Top-1 Accuracy. Top-1 accuracy measures the correctness of _action at each
time step_. Accuracy is a relaxation of the success rate because it doesn’t
require the whole sequence to match the ground-truth. Accuracy is averaged
over individual actions to balance the effect of repeating actions.

\- mIoU. Mean Intersection over Union (mIoU) is the least strict metric which
used to capture the cases where the model can output the required actions but
fail to discern the order of actions. Same as Chang _et al._ [3], we compute
IoU
$\frac{|\\{a_{t}\\}\cap\\{\hat{a}_{t}\\}|}{|\\{a_{t}\\}\cup\\{\hat{a}_{t}\\}|}$
between the set of planned actions $\\{\hat{a}_{t}\\}$ and the set of ground-
truth $\\{a_{t}\\}$.

Implementation Details. We use the Transformer architecture [6] as the
transition model with $8$ self-attention layers and $8$ heads. The transition
model, which is two-headed: one for action prediction the other for state
prediction. The state encoder in our model is two fully-connected layers with
[64,32] units in each layer and Leaky-ReLU as non-linearity function. During
training, all models are optimized by Adam [32] with the starting learning
rate of $10^{-4}$. We train our model for 200 epochs with batch size of 256 on
a single GTX 1080 Ti GPU.

TABLE II: Ablation Study on CrossTask.

Type | T=3
---|---
Success Rate (%) | Accuracy (%) | mIoU (%)
beam width $k=1$ | 14.18 | 35.92 | 52.36
beam width $k=3$ | 15.33 | 37.67 | 58.08
visual start & lang. goal | 16.05 | 36.46 | 60.51
lang. start & lang. goal | 14.05 | 34.21 | 57.19
Causal-Attn. | 15.23 | 34.34 | 58.15
Full-Attn. Future-$1$ | 17.84 | 38.91 | 63.02
PlaTe (Ours) | $\bm{18.50}$ | $\bm{39.33}$ | $\bm{65.91}$

###  IV-B Evaluating Procedure Planning on CrossTask

First, we choose a real-world instructional video dataset CrossTask [16] to
conduct our experiments. CrossTask comprises $2,750$ videos ($212$ hours).
Each video depicts one of the $18$ primary long-horizon tasks—for example,
_Make Pancakes_ , _Add Oil to Your Car_ or _Make Lemonade_. To test the
trained agent’s generalization capability, for the videos in each task, we
randomly divide the videos in each task into $70\%/30\%$ splits for training
and testing. There are various procedure steps in different tasks. For
example, the most simple task is "Jack Up a Car", which only contains 3 steps.
Complex tasks such as "Grill Steak", "Make Bread and Butter Pickles", "Pickle
Cucumbers", and "Change a Tire" require 11 steps to finish. For each video,
there are dense temporal boundaries and action labels that describe the
person’s actions in the video. Each video can be regarded as a sequence of
images $V_{i}$ (where $i$ is the index of frames) that have annotated with a
sequence of action labels $a_{j}$ and each action starts at frame index
$s_{j}$ and ends at frame index $e_{j}$. Same as the setup of [3]: we choose
frames around the beginning of the captions
$V_{s_{t}-\delta/2:s_{t}+\delta/2}$ as $o_{t}$ , caption description $a_{t}$
as the semantic meaning of action, and images nearby the end
$V_{e_{t}-\delta/2:e_{t}+\delta/2}$ as the next observation $o_{t+1}$. Here,
$\delta$ controls the duration of each observation, and we set $\delta=2$ for
all data we have used in our paper. Our state-space $\mathcal{S}$ is the pre-
computed features provided in CrossTask: each second of the video is encoded
into a $3,200$-dimensional feature vector , which is a concatenation of the
I3D [33], Resnet-152 [34], and audio VGG features [35]. The action space
$\mathcal{A}$ is constructed by enumerating all combinations of predicates and
objects, which provides $105$ action labels and is shared across all $18$
tasks. Our method is suitable for modeling longer trajectories, but we
restrict the experiments to horizontal lengths $T=3\sim 4$ to maintain a
consistent comparison with state-of-the-art methods.

Recall that in procedure planning, given the start and goal observations
$o_{1}$ and $o_{T}$, the agent needs to output a valid procedure
$\\{a_{1},\cdots,a_{T}\\}$ to reach the specified goal. As illustrated in
Table I, as instructional videos’ action space is not continuous, the
gradient-based planner of UPN cannot work well. By introducing Beam Search,
our PlaTe has a better performance in terms of success rate, accuracy, and
mIoU. By designing a model with transformer-based components, we show that our
model outperforms all the baseline approaches on real-world videos.

In Figure 4, we visualize some examples of the predicted procedure planning
results on CrossTask, where the task is to _Make Pancake_. Our model is able
to predict a sequence of actions with correct ordering. Specifically, the most
challenging step in _Make Pancake_ is the "add flour" and "add sugar" step,
where visual differences are not significant, and it can only be inferred from
context and sequence relationships.

In Figure 5, we further show our model’s performance as the planning horizon
increases. Our model consistently outperforms the RB, UPN, DDN baseline for
success rate metric because PlaTe enjoys the advantage of the transformer-
based architecture and discrepancy-constrained Beam Search to find the
sequence of actions that reaches the goal.

Figure 5: PlaTe consistently outperforms baselines as the horizon of planning $T$ increases. It can be seen that PlaTe is better at long-term planning. Figure 6: Procedure Planning qualitative results on ActioNet. Procedure Planning qualitative results for _Wash Dishes_. The top row describes the correct action sequence required to repot the plant. To examine our mode’s robustness, We vary the start and goal observations to evaluate our method.  TABLE III: Success Rate (%) of ActioNet and UR5. Method | ActioNet | UR5
---|---|---
Prediction Length | $T=3$ | $T=4$ | $T=3$ | $T=4$
Random |  $<$0.01 |  $<$0.01 |  $<$0.01 |  $<$0.01
RB [21] | 7.62 | 3.67 | 32 | 26
RL [3] | 7.41 | 3.55 | 50 | 44
WLTDO [14] | 1.61 | 0.69 | 42 | 38
UAAA [24] | 1.99 | 0.79 | 44 | 40
UPN [12] | 2.27 | 1.02 | 44 | 38
DDN [3] | 10.06 | 4.06 | 52 | 46
PlaTe (Ours) | $\bm{16.45}$ | $\bm{8.55}$ | $\bm{60}$ | $\bm{52}$

###  IV-C Ablation Study on CrossTask

We also conduct experiments on CrossTask dataset with variations of our model:

  * •

Beam width $k=1/2/3$. We investigate the impact of beam width on Beam Search.

  * •

Causal Attention vs. Full Attention with Future-$N$ supervision.

  * •

Visual Input vs. Lang. Input. Instead of using visual observations, we replace
the start and goal visual observations with language, respectively, and see
what the impact is.

As shown in Table II, our model uses beam width $k=2$, visual input and visual
goal as observation, and Full-Attention Future-$2$. Learning the model without
beam search (beam width $k=1$) will significantly hurt the overall
performance. With Beam Search, our model can select a number of best
alternatives with the highest probability as the most likely possible choices
for the time step. If beam width $k=1$, the learned policy will excessively
focus on the single-step action modeling, which is not desired for long-term
planning. However, our results show that larger beam width leads to
increasingly large early discrepancies. We also note that the increase in
future-$N$ makes the performance slightly better. After replacing the visual
observation with the language description, the performance is not as good as
visual observations. This is due to the fact that text description contains
less context information than visual observations.

We calculate the mean square error (MSE) between the encoder
$\hat{s}_{t}=f(o_{t})$ and the transition model
$g(\hat{s}_{t+1}|\hat{s}_{t},\hat{a}_{t},\hat{s}_{T})$ from $t=1$ to $t=T$ as
the compounding error. We compare PlaTe using Fully Connected (FC) Layer and
Transformer architecture. The quantitative results of compounding error are
reported as Figure 7.

Figure 7: Compounding Error (CE) Comparison.

###  IV-D Evaluating Procedure Planning on ActioNet

To further illustrate the effectiveness of our method, we experiment on a
second dataset ActioNet [30]. ActioNet is an interactive end-to-end platform
for data collection and augmentation of the task-based dataset in 3D
environment. Comprising over $3000$ hierarchical task structures and videos,
this dataset contains narrated instruction videos across $50$ different scenes
to give over $150,000$ video. There are a total of 34 action candidates. The
narrated instruction videos describe diverse tasks such as _Close the shower
curtain_. Compared with CrossTask, this dataset has more tasks, and the
average trajectory length is longer.

As illustrated in Table III, Both WLTDO and UAAA perform similar to UPN, which
can be seen as an RNN goal-conditional policy directly trained with imitation
objectives. Our model combines the strengths of transformer-based architecture
and low discrepancy Beam Search, enabling us to predict actions from long-term
videos to outperform all the baseline approaches on all metrics.

In Figure 6, we visualize some procedure planning examples on ActioNet, where
the task is _Wash Dishes_. Our full model is able to predict a sequence of
intermediate actions with correct ordering. Specifically, the most challenging
step in _Wash Dishes_ is the "Put Object" and "Pickup Object". These two
actions can be distinguished only by taking into account the temporal
information.

Figure 8: Procedure Planning qualitative results on UR5.

###  IV-E Evaluating Procedure Planning on Real Robot

Previous Procedure Planning research has rarely reported experimental results
in real robots. There remains a gap between offline training and real-world
applications. To validate the possibility of applying procedural tasks in the
real environment, we conduct experiments on "Reaching a block" (cf. Fig. 8)
using a Universal Robot UR5 system. This task while easy in simulation, but
can be difficult for real robot [36, 37]. Our agent learns to achieve tasks by
imitating expert demonstrations. After the RGB-D camera is installed in front
of the manipulator, the observation space includes the raw RGB images at
current position and goal position. The action space includes None, Up, Down,
Left, Right, Forward, Backward. UR5 Reacher consists of episodes of
interactions, where each episode is $T$ time steps long. The fingertip of UR5
Reacher is confined within a 3-dimensional 0.7m × 0.5m × 0.4m boundary. The
robot is also constrained within a joint-angular boundary to avoid self-
collision.

In the task of Reaching, the robot is required to start at the current
observation and then move to a goal observation. Since the controller of the
robot is imperfect, we consider a reach to be successful if the robot reaches
within $5$cm of the block. The UR5 robotic arm is controlled by human
volunteers to reach the target, and thus 100 offline expert demonstration
trajectories are generated. All methods are evaluated on a real UR5 robotic
arm for 50 episodes. As shown in Table III, our approach outperforms the other
methods. Even though other baseline strategy has succeeded in offline dataset,
real robotic reaching lags far behind human performance and remains unsolved
in the field of robot learning.

##  V Conclusion

To conclude, we propose a cross-modal transformer-based architecture to
address the procedure planning problem, which can capture long-term time
dependencies. Moreover, We propose to enhance the transformer-based planner
with Beam Search. Finally, we evaluate our method on a real-world
instructional video dataset, and an interactive environment. The results
indicate that our method can learn a meaningful action sequence for planning
and recover the human decision-making process. We also validated the
possibility of applying procedural tasks on a real UR-5 platform.

## References

  * [1] M. Beetz, R. Chatila, J. Hertzberg, and F. Pecora, “Ai reasoning methods for robotics,” in _Springer Handbook of Robotics_.
  * [2] J. Sun, H. Sun, T. Han, and B. Zhou, “Neuro-symbolic program search for autonomous driving decision module design,” in _Proceedings of the Conference on Robot Learning (CoRL) 2020_.
  * [3] C.-Y. Chang, D.-A. Huang, D. Xu, E. Adeli, L. Fei-Fei, and J. C. Niebles, “Procedure planning in instructional videos,” in _ECCV_. Springer, 2020, pp. 334–350.
  * [4] M. Watter, J. Springenberg, J. Boedecker, and M. Riedmiller, in _NeurIPS_.
  * [5] J. Huang, S. Xie, J. Sun, Q. Ma, C. Liu, D. Lin, and B. Zhou, “Learning a decision module by imitating driver’s control behaviors,” in _Proceedings of the Conference on Robot Learning (CoRL) 2020_.
  * [6] A. Vaswani, N. Shazeer, N. Parmar, J. Uszkoreit, L. Jones, A. N. Gomez, L. u. Kaiser, and I. Polosukhin, in _NeurIPS_.
  * [7] S. Hochreiter and J. Schmidhuber, “Long short-term memory,” 1997.
  * [8] J. Chung, C. Gulcehre, K. Cho, and Y. Bengio, “Empirical evaluation of gated recurrent neural networks on sequence modeling,” _arXiv preprint arXiv:1412.3555_ , 2014.
  * [9] D. Hafner, T. Lillicrap, I. Fischer, R. Villegas, D. Ha, H. Lee, and J. Davidson, “Learning latent dynamics for planning from pixels,” in _International Conference on Machine Learning_ , 2019.
  * [10] J. Sun, L. Yu, P. Dong, B. Lu, and B. Zhou, “Adversarial inverse reinforcement learning with self-attention dynamics model,” _IEEE Robotics and Automation Letters_ , vol. 6, no. 2, pp. 1880–1886, 2021.
  * [11] T. Kurutach, A. Tamar, G. Yang, S. J. Russell, and P. Abbeel, in _NeurIPS_ , S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett, Eds.
  * [12] A. Srinivas, A. Jabri, P. Abbeel, S. Levine, and C. Finn, “Universal planning networks: Learning generalizable representations for visuomotor control,” in _International Conference on Machine Learning_ , 2018.
  * [13] D. Pathak, P. Agrawal, A. A. Efros, and T. Darrell, “Curiosity-driven exploration by self-supervised prediction,” in _International Conference on Machine Learning_.
  * [14] K. Ehsani, H. Bagherinezhad, J. Redmon, R. Mottaghi, and A. Farhadi, “Who let the dogs out? modeling dog behavior from visual data,” in _CVPR_ , 2018, pp. 4051–4060.
  * [15] L. Zhou, C. Xu, and J. Corso, “Towards automatic learning of procedures from web instructional videos,” in _AAAI_.
  * [16] D. Zhukov, J.-B. Alayrac, R. G. Cinbis, D. Fouhey, I. Laptev, and J. Sivic, “Cross-task weakly supervised learning from instructional videos,” in _CVPR_.
  * [17] D.-A. Huang, L. Fei-Fei, and J. C. Niebles, “Connectionist temporal modeling for weakly supervised action labeling,” in _ECCV_.
  * [18] C.-Y. Chang, D.-A. Huang, Y. Sui, L. Fei-Fei, and J. C. Niebles, “D3tw: Discriminative differentiable dynamic time warping for weakly supervised action alignment and segmentation,” in _CVPR_.
  * [19] B. Pan, J. Sun, W. Lin, L. Wang, and W. Lin, “Cross-stream selective networks for action recognition,” in _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR) Workshops_ , June 2019.
  * [20] J.-B. Alayrac, I. Laptev, J. Sivic, and S. Lacoste-Julien, “Joint discovery of object states and manipulation actions,” in _ICCV_.
  * [21] C. Sun, A. Myers, C. Vondrick, K. Murphy, and C. Schmid, “Videobert: A joint model for video and language representation learning,” in _ICCV_.
  * [22] X. Wang, J.-F. Hu, J.-H. Lai, J. Zhang, and W.-S. Zheng, “Progressive teacher-student learning for early action prediction.”
  * [23] F. Sener and A. Yao, “Zero-shot anticipation for instructional activities.”
  * [24] Y. Abu Farha and J. Gall, “Uncertainty-aware anticipation of activities,” in _Proceedings of the IEEE/CVF International Conference on Computer Vision (ICCV) Workshops_ , 2019.
  * [25] A. Radford, K. Narasimhan, T. Salimans, and I. Sutskever, “Improving language understanding by generative pre-training,” 2018.
  * [26] J. Devlin, M.-W. Chang, K. Lee, and K. Toutanova, “Bert: Pre-training of deep bidirectional transformers for language understanding,” _arXiv preprint arXiv:1810.04805_ , 2018.
  * [27] R. Li, S. Yang, D. A. Ross, and A. Kanazawa, “Learn to dance with aist++: Music conditioned 3d dance generation,” 2021.
  * [28] C. Meister, T. Vieira, and R. Cotterell, “Best-first beam search,” _Transactions of the Association for Computational Linguistics_ , vol. 8, pp. 795–809, 2020.
  * [29] M. Janner, J. Fu, M. Zhang, and S. Levine, “When to trust your model: Model-based policy optimization,” _arXiv preprint arXiv:1906.08253_ , 2019\.
  * [30] J. Duan, S. Yu, H. L. Tan, and C. Tan, “Actionet: An interactive end-to-end platform for task-based data collection and augmentation in 3d environment,” in _2020 IEEE International Conference on Image Processing (ICIP)_ , 2020.
  * [31] E. Kolve, R. Mottaghi, W. Han, E. VanderBilt, L. Weihs, A. Herrasti, D. Gordon, Y. Zhu, A. Gupta, and A. Farhadi, “AI2-THOR: An Interactive 3D Environment for Visual AI,” _arXiv_ , 2017.
  * [32] D. P. Kingma and J. Ba, “Adam: A method for stochastic optimization,” _International Conference for Learning Representations_ , 2015.
  * [33] J. Carreira and A. Zisserman, “Quo vadis, action recognition? a new model and the kinetics dataset,” in _CVPR_ , 2017.
  * [34] K. He, X. Zhang, S. Ren, and J. Sun, “Deep residual learning for image recognition,” in _CVPR_.
  * [35] S. Hershey, S. Chaudhuri, D. P. W. Ellis, J. F. Gemmeke, A. Jansen, R. C. Moore, M. Plakal, D. Platt, R. A. Saurous, B. Seybold, M. Slaney, R. J. Weiss, and K. Wilson, “Cnn architectures for large-scale audio classification,” in _IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)_ , 2017.
  * [36] S. Gu, E. Holly, T. Lillicrap, and S. Levine, “Deep reinforcement learning for robotic manipulation with asynchronous off-policy updates.”
  * [37] X. Chen, Z. Ye, J. Sun, Y. Fan, F. Hu, C. Wang, and C. Lu, “Transferable active grasping and real embodied dataset,” in _2020 IEEE International Conference on Robotics and Automation (ICRA)_ , 2020, pp. 3611–3618.


Language Development Environment}. In \bibinfo{booktitle}{\emph{Compiler
Construction, 10th International Conference, {CC} 2001 Held as Part of the
Joint European Conferences on Theory and Practice of Software, {ETAPS} 2001
Genova, Italy, April 2-6, 2001, Proceedings}}. \bibinfo{pages}{365--370}.
\newblock
\urldef\tempurl%
\url{https://doi.org/10.1007/3-540-45306-7\_26}
\showDOI{\tempurl}

\bibitem[\protect\citeauthoryear{Visser}{Visser}{2001a}]%
\bibfield{author}{\bibinfo{person}{Eelco Visser}.}
\bibinfo{year}{2001}\natexlab{a}.
\newblock \showarticletitle{Stratego: {A} Language for Program Transformation
Based on Rewriting Strategies}. In \bibinfo{booktitle}{\emph{Rewriting
Techniques and Applications, 12th International Conference, {RTA} 2001,
Utrecht, The Netherlands, May 22-24, 2001, Proceedings}}.
\bibinfo{pages}{357--362}.
\newblock
\urldef\tempurl%
\url{https://doi.org/10.1007/3-540-45127-7\_27}
\showDOI{\tempurl}

\bibitem[\protect\citeauthoryear{Visser}{Visser}{2001b}]%
\bibfield{author}{\bibinfo{person}{Eelco Visser}.}
\bibinfo{year}{2001}\natexlab{b}.
\newblock \showarticletitle{A Survey of Strategies in Program Transformation
\newblock \bibinfo{journal}{\emph{Electr. Notes Theor. Comput. Sci.}}
\bibinfo{volume}{57} (\bibinfo{year}{2001}), \bibinfo{pages}{109--143}.
\newblock
\urldef\tempurl%
\url{https://doi.org/10.1016/S1571-0661(04)00270-1}
\showDOI{\tempurl}

\bibitem[\protect\citeauthoryear{Visser}{Visser}{2004}]%
\bibfield{author}{\bibinfo{person}{Eelco Visser}.}
\bibinfo{year}{2004}\natexlab{}.
\newblock \showarticletitle{Program transformation with Stratego/XT}.
\newblock In \bibinfo{booktitle}{\emph{Domain-specific program generation}}.
\bibinfo{publisher}{Springer}, \bibinfo{pages}{216--238}.
\newblock

\bibitem[\protect\citeauthoryear{Visser}{Visser}{2005}]%
\bibfield{author}{\bibinfo{person}{Eelco Visser}.}
\bibinfo{year}{2005}\natexlab{}.
\newblock \showarticletitle{A survey of strategies in rule-based program
transformation systems}.
\newblock \bibinfo{journal}{\emph{J. Symb. Comput.}} \bibinfo{volume}{40},
\bibinfo{number}{1} (\bibinfo{year}{2005}), \bibinfo{pages}{831--873}.
\newblock
\urldef\tempurl%
\url{https://doi.org/10.1016/j.jsc.2004.12.011}
\showDOI{\tempurl}

\bibitem[\protect\citeauthoryear{Visser, Benaissa, and Tolmach}{Visser
\bibfield{author}{\bibinfo{person}{Eelco Visser},
\bibinfo{person}{Zine{-}El{-}Abidine Benaissa}, {and}
\bibinfo{person}{Andrew~P. Tolmach}.} \bibinfo{year}{1998}\natexlab{}.
\newblock \showarticletitle{Building Program Optimizers with Rewriting
Strategies}. In \bibinfo{booktitle}{\emph{Proceedings of the third {ACM}
{SIGPLAN} International Conference on Functional Programming {(ICFP} '98),
Baltimore, Maryland, USA, September 27-29, 1998.}} \bibinfo{pages}{13--26}.
\newblock
\urldef\tempurl%
\url{https://doi.org/10.1145/289423.289425}
\showDOI{\tempurl}

\bibitem[\protect\citeauthoryear{Yuki, Gupta, Kim, Pathan, and Rajopadhye}{Yuki
\bibfield{author}{\bibinfo{person}{Tomofumi Yuki}, \bibinfo{person}{Gautam
Gupta}, \bibinfo{person}{DaeGon Kim}, \bibinfo{person}{Tanveer Pathan}, {and}
\bibinfo{person}{Sanjay~V. Rajopadhye}.} \bibinfo{year}{2012}\natexlab{}.
\newblock \showarticletitle{AlphaZ: {A} System for Design Space Exploration in
the Polyhedral Model}. In \bibinfo{booktitle}{\emph{Languages and Compilers
for Parallel Computing, 25th International Workshop, {LCPC} 2012, Tokyo,
Japan, September 11-13, 2012, Revised Selected Papers}}.
\bibinfo{pages}{17--31}.
\newblock
\urldef\tempurl%
\url{https://doi.org/10.1007/978-3-642-37658-0\_2}
\showDOI{\tempurl}

\bibitem[\protect\citeauthoryear{Zhang, Yang, Baghdadi, Kamil, Shun, and
Amarasinghe}{Zhang et~al\mbox{.}}{2018}]%
\bibfield{author}{\bibinfo{person}{Yunming Zhang}, \bibinfo{person}{Mengjiao
Yang}, \bibinfo{person}{Riyadh Baghdadi}, \bibinfo{person}{Shoaib Kamil},
\bibinfo{person}{Julian Shun}, {and} \bibinfo{person}{Saman~P. Amarasinghe}.}
\bibinfo{year}{2018}\natexlab{}.
\newblock \showarticletitle{GraphIt: a high-performance graph {DSL}}.
\newblock \bibinfo{journal}{\emph{{PACMPL}}} \bibinfo{volume}{2},
\bibinfo{number}{{OOPSLA}} (\bibinfo{year}{2018}),
\bibinfo{pages}{121:1--121:30}.
\newblock
\urldef\tempurl%
\url{https://doi.org/10.1145/3276491}
\showDOI{\tempurl}

\end{thebibliography}

%% Appendix
% \appendix
% \section{Appendix}

% Text of appendix \ldots

\end{document}