# Bound for the cocharacters of the identities of irreducible representations
of $\mathfrak{sl}_{2}(\mathbb{C})$

Mátyás Domokos  Alfréd Rényi Institute of Mathematics, Reáltanoda utca 13-15,
1053 Budapest, Hungary<EMAIL_ADDRESS>
###### Abstract.

For each irreducible finite dimensional representation of the Lie algebra
$\mathfrak{sl}_{2}(\mathbb{C})$ of $2\times 2$ traceless matrices, an explicit
uniform upper bound is given for the multiplicities in the cocharacter
sequence of the polynomial identities satisfied by the given representation.

###### Key words and phrases:

weak polynomial identities, simple Lie algebra, irreducible representation,
cocharacter sequence

###### 2010 Mathematics Subject Classification:

16R30; 16R10; 17B01; 17B20; 20C30.

Partially supported by the Hungarian National Research, Development and
Innovation Office, NKFIH K 138828, K 132002.

> Dedicated to Vesselin Drensky on his $70$th birthday

##  1\. Introduction

Let $\rho:\mathfrak{g}\to\mathfrak{gl}(V)$ be a finite dimensional
representation of the Lie algebra $\mathfrak{g}$ over a field $K$ of
characteristic zero; that is, $\mathfrak{gl}(V)=\mathrm{End}_{K}(V)$, the
space of all $K$-linear transformations of the finite dimensional $K$-vector
space $V$, viewed as a Lie algebra with Lie product $[A,B]:=A\circ B-B\circ A$
for $A,B\in\mathrm{End}_{K}(V)$, and $\rho$ is a homomorphism of Lie algebras.
Denote by $F_{m}:=K\langle x_{1},\dots,x_{m}\rangle$ the free associative
$K$-algebra with $m$ generators. Consider $F_{m}$ a subalgebra of $F_{m+1}$ in
the obvious way, and write $F:=\bigcup_{m=1}^{\infty}F_{m}$ for the free
associative algebra of countable rank. We say that _$f=0$ is an identity of
the representation $\rho$ of $\mathfrak{g}$_ (or briefly, of the pair
$(\mathfrak{g},\rho)$) for some $f\in F_{m}$ if for any elements
$A_{1},\dots,A_{m}\in\mathfrak{g}$ we have the following equality in the
associative $K$-algebra $\mathrm{End}_{K}(V)$:

$f(\rho(A_{1}),\dots,\rho(A_{n}))=0\in\mathrm{End}_{K}(V).$

Note that an identity of the representation $\rho$ of the Lie algebra
$\mathfrak{g}$ is also called in the literature a _weak polynomial identity_
for the pair $(\mathrm{End}_{K}(V),\rho(\mathfrak{g}))$. This notion was
introduced and powerfully applied first by Razmyslov [13, 14, 15, 16] (see
Drensky [8] for a recent survey on weak polynomial identities). Set

$I(\mathfrak{g},\rho):=\\{f\in F\mid f=0\text{ is an identity of
}(\mathfrak{g},\rho)\\}.$

Clearly $I(\mathfrak{g},\rho)$ is an ideal in $F$ stable with respect to all
$K$-algebra endomorphisms of $F$ of the form $x_{i}\mapsto u_{i}$, where
$u_{i}$ for $i=1,2,\dots$ is an element of the Lie subalgebra of $F$ generated
by $x_{1},x_{2},\dots$. In particular, the general linear group
$\mathrm{GL}_{m}(K)$ acts on $F_{m}$ via $K$-algebra automorphisms: for
$g=(g_{ij})_{i,j=1}^{m}$ we have $g\cdot x_{j}=\sum_{i=1}^{m}g_{ij}x_{i}$, and
$I(\mathfrak{g},\rho)\cap F_{m}$ is a $\mathrm{GL}_{m}(K)$-invariant subspace
of $F_{m}$. The _multilinear component_ of $F_{m}$ is

$P_{m}:=\mathrm{Span}_{K}\\{x_{\pi(1)}\cdots x_{\pi(m)}\mid\pi\in S_{m}\\},$

where $S_{m}$ is the symmetric group of degree $m$. It is well known that when
$\mathrm{char}(K)=0$, the ideal $I(\mathfrak{g},\rho)$ is determined by the
multilinear components $I(\mathfrak{g},\rho)\cap P_{m}$, $m=1,2,\dots$.
Identifying $S_{m}$ with the subgroup of permutation matrices in
$\mathrm{GL}_{m}(K)$ we get its action on $F_{m}$ via $K$-algebra
automorphisms (more explicitly, $\pi\in S_{m}$ is the automorphism of $F_{m}$
given by $x_{i}\mapsto x_{\pi(i)}$), and the subspaces $P_{m}$ and
$I(\mathfrak{g},\rho)\cap P_{m}$ are $S_{m}$-invariant. Define the _$m$ th
cocharacter of $(\mathfrak{g},\rho)$_ as

$\chi_{m}(\mathfrak{g},\rho):=\text{ the character of the }S_{m}\text{-module
}P_{m}/(I(\mathfrak{g},\rho)\cap P_{m}).$

We call

$\chi(\mathfrak{g},\rho):=(\chi_{m}(\mathfrak{g},\rho)\mid m=1,2,\dots)$

the _cocharacter sequence of_ $(\mathfrak{g},\rho)$. The irreducible
$S_{m}$-modules are labeled by partitions of $m$; let $\chi^{\lambda}$ denote
the character of the irreducible $S_{m}$-module associated to the partition
$\lambda=(\lambda_{1},\dots,\lambda_{m})\vdash m$. We have

$\chi_{m}(\mathfrak{g},\rho)=\sum_{\lambda\vdash
m}\mathrm{mult}_{\lambda}(\mathfrak{g},\rho)\chi^{\lambda},$

and we are interested in the multiplicities
$\mathrm{mult}_{\lambda}(\mathfrak{g},\rho)$ of the irreducible
$S_{m}$-characters in the cocharacter sequence. Note that the value of
$\chi_{m}(\mathfrak{g},\rho)$ on the identity element of $S_{m}$ is

$c_{m}(\mathfrak{g},\rho):=\dim_{K}(P_{m}/(I(\mathfrak{g},\rho)\cap P_{m})),$

and

$(c_{m}(\mathfrak{g},\rho)\mid m=1,2,\dots)$

is called the _codimension sequence of_ $(\mathfrak{g},\rho)$. It was proved
by Gordienko [10] that $\lim_{m\to\infty}\root m
\of{c_{m}(\mathfrak{g},\rho)}$ exists and is an integer. As is observed in
[10, Example 3], an obvious upper bound for $c_{m}(\mathfrak{g},\rho)$ can be
obtained from the fact that there is a natural $K$-linear embedding

(1) $P_{m}/(I(\mathfrak{g},\rho)\cap
P_{m})\hookrightarrow\mathrm{Hom}_{K}(\rho(\mathfrak{g})^{\otimes
m},\mathrm{End}_{K}(V)).$

Our starting observation is that the adjoint representation of $\mathfrak{g}$
on itself induces a natural representation of $\mathfrak{g}$ on
$\rho(\mathfrak{g})^{\otimes m}$ (the $m$th tensor power of
$\rho(\mathfrak{g})$) and on $\mathrm{End}_{K}(V)$, such that the image of the
embedding (1) is contained in the subspace of $\mathfrak{g}$-module
homomorphisms from $\rho(\mathfrak{g})^{\otimes m}$ to $\mathrm{End}_{K}(V)$.
So (1) can be refined as

(2) $P_{m}/(I(\mathfrak{g},\rho)\cap
P_{m})\hookrightarrow\mathrm{Hom}_{\mathfrak{g}}(\rho(\mathfrak{g})^{\otimes
m},\mathrm{End}_{K}(V)).$

This will be used to give an upper bound for the multiplicities in the
cocharacter sequence $\chi(\mathfrak{sl}_{2}(\mathbb{C}),\rho^{(d)})$ of the
$d$-dimensional irreducible representation

$\rho^{(d)}:\mathfrak{sl}_{2}(\mathbb{C})\to\mathfrak{gl}(\mathbb{C}^{d})=\mathbb{C}^{d\times
d}$

of $\mathfrak{sl}_{2}(\mathbb{C})$ for $d=1,2,\dots$. Note that throughout the
paper we shall identify $\mathfrak{gl}(\mathbb{C}^{d})$ with the associative
algebra $\mathbb{C}^{d\times d}$ of $d\times d$ complex matrices, viewed as a
Lie algebra with Lie bracket $[A,B]=AB-BA$.

######  Theorem 1.1.

The multiplicity
$\mathrm{mult}_{\lambda}(\mathfrak{sl}_{2}(\mathbb{C}),\rho^{(d)})$ in
$\chi(\mathfrak{sl}_{2}(\mathbb{C}),\rho^{(d)})$ is non-zero only if
$\lambda=(\lambda_{1},\lambda_{2},\lambda_{3})$ (i.e. $\lambda$ has at most
$3$ non-zero parts), and in this case we have the inequality

$\mathrm{mult}_{\lambda}(\mathfrak{sl}_{2}(\mathbb{C}),\rho^{(d)})\leq
3^{d-2}.$

######  Remark 1.2.

(i) The exact values of
$\mathrm{mult}_{\lambda}(\mathfrak{sl}_{2}(\mathbb{C}),\rho^{(d)})$ are known
for $d\leq 3$. For $d=1$ all the multiplicities are obviously zero. It was
proved in [12] (see also [7, Exercise 12.6.12]) that

$\mathrm{mult}_{\lambda}(\mathfrak{sl}_{2}(\mathbb{C}),\rho^{(2)})=1\text{ for
all }\lambda=(\lambda_{1},\lambda_{2},\lambda_{3}).$

The multiplicities
$\mathrm{mult}_{\lambda}(\mathfrak{sl}_{2}(\mathbb{C}),\rho^{(3)})$ are
computed in [5, Theorem 3.7, Proposition 3.8]. It turns out that
$\mathrm{mult}_{\lambda}(\mathfrak{sl}_{2}(\mathbb{C}),\rho^{(3)})\in\\{1,2,3\\}$
for each $\lambda=(\lambda_{1},\lambda_{2},\lambda_{3})$.

(ii) Theorem 1.1 shows in particular that for each dimension $d$, there is a
uniform bound (depending on $d$ only) for the multiplicities
$\mathrm{mult}_{\lambda}(\mathfrak{sl}_{2}(\mathbb{C}),\rho^{(d)})$. For
comparison we mention that the multiplicities in the cocharacter sequence of
the ordinary polynomial identities of $2\times 2$ matrices are unbounded: see
[6] and [9]. For example, for any partition
$\lambda=(\lambda_{1},\lambda_{2})$ with $\lambda_{2}>0$, the multiplicity is
$(\lambda_{1}-\lambda_{2}+1)\lambda_{2}$. On the other hand, the cocharacter
multiplicities of any PI algebra are polynomially bounded by [2].

(iii) There is no uniform upper bound independent of $d$ for the
multiplicities
$\mathrm{mult}_{\lambda}(\mathfrak{sl}_{2}(\mathbb{C}),\rho^{(d)})$, because
by Proposition 4.1,
$\max\\{\mathrm{mult}_{\lambda}(\mathfrak{sl}_{2}(\mathbb{C}),\rho^{(d)})\mid
m=1,2,\dots,\ \lambda\vdash m\\}\geq d-1$ for $d\geq 2$.

(iv) The irreducible representations of $\mathfrak{sl}_{2}(\mathbb{C})$ are
defined over $\mathbb{Q}$. For any field $K$ of characteristic zero and any
positive integer $d$, the Lie algebra $\mathfrak{sl}_{2}(K)$ has a unique (up
to isomorphism) $d$-dimensional irreducible representation $\rho^{(d)}_{K}$
over $K$. By well-known general arguments, the multiplicities
$\mathrm{mult}_{\lambda}(\mathfrak{sl}_{2}(K),\rho^{(d)}_{K})$ do not depend
on $K$. Therefore Theorem 1.1 implies that
$\mathrm{mult}_{\lambda}(\mathfrak{sl}_{2}(K),\rho^{(d)}_{K})\leq 3^{d-2}$ for
any field $K$ of characteristic zero.

(v) A different interpretation and approach to the study of
$\mathrm{Hom}_{\mathfrak{g}}(\rho(\mathfrak{g})^{\otimes
m},\mathrm{End}_{K}(V))$ for $\mathfrak{g}=\mathfrak{sl}_{2}(\mathbb{C})$ and
$\rho=\rho^{(d)}$ is given in our parallel preprint [4], using classical
invariant theory.

We close the introduction by mentioning the recent paper of da Silva Macedo
and Koshlukov [3, Theorem 3.7], where the codimension growth of polynomial
identities of representations of Lie algebras is studied. In particular, in
[3, Theorem 3.7] the identities of representations of
$\mathfrak{sl}_{2}(\mathbb{C})$ play a decisive role.

##  2\. Matrix computations

Denote by
$\widetilde{\rho}^{(d)}:\mathfrak{sl}_{2}(\mathbb{C})\to\mathfrak{gl}(\mathbb{C}^{d\times
d})$ the representation given by

(3) $\widetilde{\rho}^{(d)}(A)(L)=\rho^{(d)}(A)L-L\rho^{(d)}(A)\text{ for
}A\in\mathfrak{sl}_{2}(\mathbb{C}),\ L\in\mathbb{C}^{d\times d}.$

We have $\widetilde{\rho}^{(d)}\cong\rho^{(d)}\otimes{\rho^{(d)}}^{*}$. The
representations of $\mathfrak{sl}_{2}(\mathbb{C})$ are self-dual, and so by
the Clebsch-Gordan rules we have

(4)
$\widetilde{\rho}^{(d)}\cong\rho^{(d)}\otimes{\rho^{(d)}}\cong\bigoplus_{n=1}^{d}\rho^{(2n-1)}.$

We shall need an explicit decomposition of $\mathbb{C}^{d\times d}$ as a
direct sum of minimal $\widetilde{\rho}^{(d)}$-invariant subspaces.

Set

$e:=\left(\begin{array}[]{cc}0&1\\\ 0&0\end{array}\right),\quad
f:=\left(\begin{array}[]{cc}0&0\\\ 1&0\end{array}\right),\quad
h:=\left(\begin{array}[]{cc}1&0\\\ 0&-1\end{array}\right),$

so $e,f,h$ is a $\mathbb{C}$-vector space basis of
$\mathfrak{sl}_{2}(\mathbb{C})$, with $[h,e]=2e$, $[h,f]=-2f$, and $[e,f]=h$.

Recall that given a representation
$\psi:\mathfrak{sl}_{2}(\mathbb{C})\to\mathfrak{gl}(V)$, by a _highest weight
vector_ we mean a non-zero element $w\in V$ such that $\psi(e)(w)=0\in V$ and
$\psi(h)(w)=nw$ for some non-negative integer $n$ (the non-negative integer
$\lambda$ is called the _weight_ of $w$); in this case $w$ generates a minimal
$\mathfrak{sl}_{2}(\mathbb{C})$-invariant subspace in $V$, on which the
representation of $\mathfrak{sl}_{2}(\mathbb{C})$ is isomorphic to
$\rho^{(n+1)}$. Moreover, any finite dimensional irreducible
$\mathfrak{sl}_{2}(\mathbb{C})$-module contains a unique (up to non-zero
scalar multiples) highest weight vector.

######  Lemma 2.1.

Consider the $\mathfrak{sl}_{2}(\mathbb{C})$-module $\mathbb{C}^{d\times d}$
via the representation $\widetilde{\rho}^{(d)}$. To simplify notation set
$\rho:=\rho^{(d)}$ and $\widetilde{\rho}:=\widetilde{\rho}^{(d)}$.

  * (i)

$\rho(e)^{n}$ is a highest weight vector in $\mathbb{C}^{d\times d}$ of weight
$2n$ for $n=0,1,\dots,d-1$.

  * (ii)

$\rho(e)^{n-1}$ generates a minimal $\widetilde{\rho}$-invariant subspace
$V_{n}$ on which $\mathfrak{sl}_{2}(\mathbb{C})$ acts via $\rho^{(2n-1)}$ for
$n=1,\dots,d$.

  * (iii)

$\mathbb{C}^{d\times d}=\bigoplus_{n=1}^{d}V_{n}$.

  * (iv)

For $L_{1}\in V_{n_{1}}$ and $L_{2}\in V_{n_{2}}$ with $1\leq n_{1}\neq
n_{2}\leq d$ we have $\mathrm{Tr}(L_{1}L_{2})=0$.

###### Proof.

(i) We have
$\widetilde{\rho}(e)(\rho(e)^{n})=\rho(e)\rho(e)^{n}-\rho(e)^{n}\rho(e)=0$ and

$\widetilde{\rho}(h)(\rho(e)^{n})=\rho([h,e])\rho(e)^{n-1}+\rho(e)\rho([h,e])\rho(e)^{n-2}+\cdots+\rho(e)^{n-1}\rho([h,e])=2n\rho(e)^{n}.$

This shows that $\rho(e)^{n}$ is a highest weight vector of weight $2n$ for
the representation $\widetilde{\rho}$.

(ii) Statement (i) implies that $\rho(e)^{n-1}$ generates an irreducible
$\mathfrak{sl}_{2}(\mathbb{C})$-submodule of $\widetilde{\rho}$ isomorphic to
$\rho^{(2n-1)}$ for $n=1,\dots,d$.

(iii) follows from (ii) and (4).

(iv) Consider the symmetric non-degenerate bilinear form

$\beta:\mathbb{C}^{d\times d}\times\mathbb{C}^{d\times
d}\to\mathbb{C},\quad(L,M)\mapsto\mathrm{Tr}(LM).$

Note that $\beta$ is $\widetilde{\rho}$-invariant:

$\displaystyle\beta([\rho(A),L],M)+\beta(L,[\rho(A),M])=\mathrm{Tr}([\rho(A),L]M)+\mathrm{Tr}(L[\rho(A),M])$
$\displaystyle=\mathrm{Tr}([\rho(A),LM])=0\quad\text{ for any
}A\in\mathfrak{sl}_{2}(\mathbb{C}).$

The radical of the bilinear form $\beta_{V_{n}}:V_{n}\times
V_{n}\mapsto\mathbb{C}$ (the restriction of $\beta$ to $V_{n}\times V_{n}$) is
a $\widetilde{\rho}$-invariant subspace in $V_{n}$, so it is either $V_{n}$ or
$\\{0\\}$. We claim that it is not $V_{n}$. Indeed, $V_{n}$ contains a non-
zero diagonal matrix $D$ with real entries, since the zero weight subspace in
$\mathbb{C}^{d\times d}$ (with respect to $\widetilde{\rho}(h)$) is the
subspace of diagonal matrices, and $V_{n}$ intersects the zero-weight space in
a $1$-dimensional subspace (defined over the reals). Now being a sum of
squares of non-zero real numbers, $0\neq\mathrm{Tr}(D^{2})=\beta(D,D)$. Thus
$\beta_{V_{n}}$ is non-degenerate. The representation $\widetilde{\rho}$ is
multiplicity free by (4), and by (ii) and (iii), every
$\widetilde{\rho}$-invariant subspace is of the form $\sum_{j\in J}V_{j}$ for
some subset $J\subseteq\\{1,2,\dots,d\\}$. As we showed above, the orthogonal
complement of $V_{n}$ (with respect to $\beta$) is disjoint from $V_{n}$, so
it is the sum of the other minimal invariant subspaces $V_{j}$,
$j\in\\{1,\dots,d\\}\setminus\\{n\\}$. ∎

The representation $\rho^{(2)}$ is the defining representation of
$\mathfrak{sl}_{2}(\mathbb{C})$ on $\mathbb{C}^{2}$, and $\rho^{(d)}$ is the
$(d-1)$th symmetric tensor power of $\rho^{(2)}$. Denote by $x,y$ the standard
basis vectors in $\mathbb{C}^{2}$, and take the basis
$x^{d-1},x^{d-1}y,\dots,y^{d-1}$ in the $(d-1)$th symmetric tensor power of
$\mathbb{C}^{2}$. Then denoting by $E_{i,j}$ the matrix unit with entry $1$ in
the $(i,j)$ position and zeros in all other positions, the representation
$\rho^{(d)}$ as a matrix representation
$\mathfrak{sl}_{2}(\mathbb{C})\to\mathbb{C}^{d\times d}$ is given as follows:

$\rho^{(d)}(e)=\sum_{i=1}^{d-1}iE_{i,i+1},\quad\rho^{(d)}(f)=\sum_{i=1}^{d-1}(d-i)E_{i+1,i},\quad\rho^{(d)}(h)=\sum_{i=1}^{d}(d+1-2i)E_{i,i}$

######  Lemma 2.2.

For $d\geq 3$ the $\mathbb{C}$-vector space $\mathbb{C}^{d\times d}$ is
spanned by

$\\{\rho^{(d)}(A_{1})\cdots\rho^{(d)}(A_{d-1})\mid
A_{1},\dots,A_{d-1}\in\mathfrak{sl}_{2}(\mathbb{C})\\}.$

###### Proof.

To simplify the notation write $\rho:=\rho^{(d)}$ and
$\widetilde{\rho}:=\widetilde{\rho}^{(d)}$. Let $\mathcal{L}$ be the subspace
of $\mathbb{C}^{d\times d}$ spanned by the products
$\rho(A_{1})\cdots\rho(A_{d-1})$, where
$A_{1},\dots,A_{d-1}\in\mathfrak{sl}_{2}(\mathbb{C})$. Clearly $\mathcal{L}$
is a $\widetilde{\rho}$-invariant subspace of $\mathbb{C}^{d\times d}$. Since
the representation $\widetilde{\rho}$ is multiplicity free by (4), we have
$\mathcal{L}=\sum_{j\in J}V_{j}$ for some subset $J\subseteq\\{1,2,\dots,d\\}$
by Lemma 2.1 (ii) and (iii). Therefore to prove the equality
$\mathcal{L}=\mathbb{C}^{d\times d}$ it is sufficient to show that
$\mathcal{L}\cap V_{n}\neq\\{0\\}$ for each $n=1,\dots,d$, or equivalently,
that $\mathcal{L}$ is not contained in
$\sum_{j\in\\{1,\dots,d\\}\setminus\\{n\\}}V_{j}$. Since $V_{d}$ is generated
by $\rho(e)^{d-1}\in\mathcal{L}$, we have $V_{d}\subseteq\mathcal{L}$.
Moreover, to prove
$\mathcal{L}\nsubseteq\sum_{j\in\\{1,\dots,d\\}\setminus\\{n+1\\}}V_{j}$ for
$n\in\\{0,1,\dots,d-2\\}$, it is sufficient to present an element
$L_{n}\in\mathcal{L}$ with $\mathrm{Tr}(\rho(e)^{n}L_{n})\neq 0$ by Lemma 2.1
(i), (ii) and (iv). We shall give below such elements $L_{n}\in\mathcal{L}$
for $n=0,1,\dots,d-2$.

For $n=1,\dots,d-1$ we have

$\rho(e)^{n}=\sum_{j=1}^{d-n}j\cdot(j+1)\cdots(j+n-1)E_{j,j+n}$
$\rho(f)^{n}=\sum_{j=1}^{d-n}(d-j)\cdot(d-j-1)\cdots(d-j-n+1)E_{j+n.j}$

and $\rho(e)^{0}=I_{d}=\rho(f)^{0}$, where $I_{d}$ is the $d\times d$ identity
matrix. It follows that for $n=1,\dots,d-1$,

$\rho(e)^{n}\rho(f)^{n}=\sum_{j=1}^{d-n}j(j+1)\cdots(j+n-1)\cdot(d-j)(d-j-1)\cdots(d-j-n+1)E_{j,j}$

is a diagonal matrix with non-negative integer entries, and the $(1,1)$-entry
is positive. The same holds for $\rho(e)^{0}\rho(f)^{0}=I_{d}$. For $n$ with
$d-1-n$ even, $\rho(h)^{d-1-n}$ is the square of a diagonal matrix with
integer entries, and its $(1,1)$-entry is positive. Hence
$\mathrm{Tr}(\rho(e)^{n}\rho(f)^{n}\rho(h)^{d-1-n})\neq 0$, being a positive
integer. So in this case we may take $L_{n}:=\rho(f)^{n}\rho(h)^{d-1-n}$. For
$n<d-2$ with $d-1-n$ odd, note that
$\rho(e)\rho(f)-\rho(f)\rho(e)=\rho([e,f])=\rho(h)$, and thus

$\rho(f)^{n}\rho(h)^{d-2-n}=\rho(f)^{n}\rho(h)^{d-3-n}(\rho(e)\rho(f)-\rho(f)\rho(e))$

also belongs to $\mathcal{L}$. Since $\rho(h)^{d-2-n}$ is a diagonal matrix
with non-negative integer entries, and with a positive $(1,1)$-entry, we may
take $L_{n}:=\rho(f)^{n}\rho(h)^{d-2-n}$ in this case. It remains to deal with
the case $n=d-2$. Then

$\rho(e)^{d-2}\rho(f)^{d-2}=(d-1)((d-2)!)^{2}\cdot(E_{1,1}+E_{2,2}),$

hence taking $L_{d-2}:=\rho(f)^{d-2}\rho(h)$ we get

$\displaystyle\mathrm{Tr}(\rho(e)^{d-2}L_{d-2})$
$\displaystyle=\mathrm{Tr}((d-1)((d-2)!)^{2}\cdot((d-1)E_{11}+(d-3)E_{22})$
$\displaystyle=(2d-4)(d-1)((d-2)!)^{2},$

which is non-zero for $d\geq 3$. This finishes the proof of the equality
$\mathcal{L}=\mathbb{C}^{d\times d}$. ∎

##  3\. Adjoint invariants

Denote by
$\mathrm{ad}:\mathfrak{sl}_{2}(\mathbb{C})\to\mathfrak{gl}(\mathfrak{sl}_{2}(\mathbb{C}))$
the _adjoint representation_ of $\mathfrak{sl}_{2}(\mathbb{C})$ on itself, so
$\mathrm{ad}(A)(B)=[A,B]$ for $A,B\in\mathfrak{sl}_{2}(\mathbb{C})$. Take the
$n$-fold direct sum $\mathrm{ad}^{\oplus
n}:\mathfrak{sl}_{2}(\mathbb{C})\to\mathfrak{gl}(\mathfrak{sl}_{2}(\mathbb{C})^{\oplus
n})$ of the adjoint representation, and write
$\mathcal{O}[\mathfrak{sl}_{2}(\mathbb{C})^{n}]^{\mathfrak{sl}_{2}(\mathbb{C})}$
for the algebra of $\mathrm{ad}^{\oplus n}$-invariant polynomial functions on
$\mathfrak{sl}_{2}(\mathbb{C})^{\oplus n}$. There is a right action of
$\mathrm{GL}_{n}(\mathbb{C})$ on $\mathfrak{sl}_{2}(\mathbb{C})^{n}$ that
commutes with $\mathrm{ad}^{\oplus n}$: for $g=(g_{ij})_{i,1=1}^{n}$ and
$(A_{1},\dots,A_{n})\in\mathfrak{sl}_{2}(\mathbb{C})^{n}$ we have

$(A_{1},\dots,A_{n})\cdot
g:=(\sum_{i=1}^{n}g_{i1}A_{i},\dots,\sum_{i=1}^{n}g_{in}A_{i}).$

This induces a left $\mathrm{GL}_{n}(\mathbb{C})$-action on the coordinate
ring $\mathcal{O}[\mathfrak{sl}_{2}(\mathbb{C})^{n}]$: for
$g\in\mathrm{GL}_{n}(\mathbb{C})$,
$f\in\mathcal{O}[\mathfrak{sl}_{2}(\mathbb{C})^{n}]$ and
$(A_{1},\dots,A_{n})\in\mathfrak{sl}_{2}(\mathbb{C})^{n}$ we have $(g\cdot
f)(A_{1},\dots,A_{n})=f((A_{1},\dots,A_{n})\cdot g)$.

######  Lemma 3.1.

Consider the linear map $\iota:F_{m}=\mathbb{C}\langle
x_{1},\dots,x_{m}\rangle\to\mathcal{O}[\mathfrak{sl}_{2}(\mathbb{C})^{m+d-1}]$
given by

$\iota(f)(A_{1},\dots,A_{m+d-1})=\mathrm{Tr}(f(\rho^{(d)}(A_{1}),\dots,\rho^{(d)}(A_{m}))\cdot\rho^{(d)}(A_{m+1})\cdots\rho^{(d)}(A_{m+d-1}))$

for $f\in F_{m}$ and
$(A_{1},\dots,A_{m+d-1})\in\mathfrak{sl}_{2}(\mathbb{C})^{m+d-1}$. It has the
following properties:

  * (i)

The image of $\iota$ is contained in the subalgebra
$\mathcal{O}[\mathfrak{sl}_{2}(\mathbb{C})^{m+d-1}]^{\mathfrak{sl}_{2}(\mathbb{C})}$
of $\mathfrak{sl}_{2}(\mathbb{C})$-invariants.

  * (ii)

For $d\geq 3$ the kernel of $\iota$ is the ideal
$I(\mathfrak{sl}_{2}(\mathbb{C}),\rho^{(d)})\cap F_{m}$.

  * (iii)

The map $\iota$ is $\mathrm{GL}_{m}(\mathbb{C})$-equivariant, where we
restrict the $\mathrm{GL}_{m+d-1}(\mathbb{C})$-action on
$\mathcal{O}[\mathfrak{sl}_{2}(\mathbb{C})^{m+d-1}]$ to the subgroup
$\mathrm{GL}_{m}(\mathbb{C})\cong\\{\left(\begin{array}[]{cc}g&0\\\
0&I_{d-1}\end{array}\right)\mid g\in\mathrm{GL}_{m}(\mathbb{C})\\}$ in
$\mathrm{GL}_{m+d-1}(\mathbb{C})$.

###### Proof.

For notational simplicity we shall write $\rho$ instead of $\rho^{(d)}$.

(i) By linearity of $\iota$ it is sufficient to show that
$\iota(x_{i_{1}}\cdots x_{i_{k}})$ is an
$\mathfrak{sl}_{2}(\mathbb{C})$-invariant for any
$i_{1},\dots,i_{k}\in\\{1,\dots,m\\}$. Setting $n=k+d-1$,
$B_{1}=A_{i_{1}},\dots,B_{k}=A_{i_{k}},B_{k+1}=A_{m+1},\dots,B_{n}=A_{m+d-1}$
we have

(5) $\iota(x_{i_{1}}\cdots
x_{i_{k}})(A_{1},\dots,A_{m+d})=\mathrm{Tr}(\rho(B_{1})\cdots\rho(B_{n})).$

For any $X\in\mathfrak{sl}_{2}(\mathbb{C})$ we have

$\displaystyle 0$
$\displaystyle=\mathrm{Tr}([\rho(X),\rho(B_{1})\cdots\rho(B_{n})])$
$\displaystyle=\mathrm{Tr}(\sum_{j=1}^{n}\rho(B_{1})\cdots\rho(B_{j-1})[\rho(X),\rho(B_{j})]\rho(B_{j+1})\cdots\rho(B_{n}))$
$\displaystyle=\mathrm{Tr}(\sum_{j=1}^{n}\rho(B_{1})\cdots\rho(B_{j-1})\rho([X,B_{j}])\rho(B_{j+1})\cdots\rho(B_{n}))$
$\displaystyle=\sum_{j=1}^{n}\mathrm{Tr}(\rho(B_{1})\cdots\rho(B_{j-1})\rho([X,B_{j}])\rho(B_{j+1})\cdots\rho(B_{n})).$

The equalities (5) and

$\sum_{j=1}^{n}\mathrm{Tr}(\rho(B_{1})\cdots\rho(B_{j-1})\rho([X,B_{j}])\rho(B_{j+1})\cdots\rho(B_{n}))=0$

mean that $\iota(x_{i_{1}}\cdots x_{i_{k}})$ is
$\mathfrak{sl}_{2}(\mathbb{C})$-invariant, so (i) holds.

(ii) Suppose that $f\in\ker(\iota)$. Then
$\mathrm{Tr}(f(\rho(A_{1}),\dots,\rho(A_{m}))B)=0$ for all
$B\in\mathbb{C}^{d\times d}$ by Lemma 2.2. By non-degeneracy of the trace we
get $f(\rho(A_{1}),\dots,\rho(A_{m}))=0$. That is, $f\in
I(\mathfrak{sl}_{2}(\mathbb{C}),\rho)$. Thus $\ker(\iota)\subseteq
I(\mathfrak{sl}_{2}(\mathbb{C}),\rho)\cap F_{m}$. The reverse inclusion
$I(\mathfrak{sl}_{2}(\mathbb{C}),\rho)\cap F_{m}\subseteq\ker(\iota)$ is
obvious.

(iii) Take $g=(g_{ij})_{i,j=1}^{m}\in\mathrm{GL}_{m}(\mathbb{C})$. For $f\in
F_{m}$ and $(A_{1},\dots,A_{m})\in\mathfrak{sl}_{2}(\mathbb{C})^{m}$ we have
(by linearity of $\rho$)

$\displaystyle\iota(g\cdot f)(A_{1},\dots,A_{m})$
$\displaystyle=\mathrm{Tr}(f(\sum_{i=1}^{m}g_{i1}\rho(A_{i}),\dots,\sum_{i=1}^{m}g_{im}\rho(A_{i}))\cdot\rho(A_{m+1})\cdots\rho(A_{m+d}))$
$\displaystyle=\mathrm{Tr}(f(\rho(\sum_{i=1}^{m}g_{i1}(A_{i})),\dots,\rho(\sum_{i=1}^{m}g_{im}(A_{i}))\cdot\rho(A_{m+1})\cdots\rho(A_{m+d}))$
$\displaystyle=(g\cdot\iota(f))(A_{1},\dots,A_{m}).$

This shows (iii). ∎

Restricting the action of $\mathrm{GL}_{n}(\mathbb{C})$ on
$\mathcal{O}[\mathfrak{sl}_{2}(\mathbb{C})^{n}]$ to the subgroup of diagonal
matrices we get an $\mathbb{N}_{0}^{n}$-grading on
$\mathcal{O}[\mathfrak{sl}_{2}(\mathbb{C})^{n}]$, preserved by the action of
$\mathfrak{sl}_{2}(\mathbb{C})$. Denote by
$\mathcal{O}[\mathfrak{sl}_{2}(\mathbb{C})^{n}]_{(1^{n})}$ the
multihomogeneous component of multidegree $(1,\dots,1)$; this is the space of
$n$-linear functions on $\mathfrak{sl}_{2}(\mathbb{C})$. The spaces
$\mathcal{O}[\mathfrak{sl}_{2}(\mathbb{C})^{n}]_{(1^{n})}$ and
$\mathcal{O}[\mathfrak{sl}_{2}(\mathbb{C})^{n}]_{(1^{n})}^{\mathfrak{sl}_{2}(\mathbb{C})}$
are $S_{n}$-invariant (where we restrict the
$\mathrm{GL}_{n}(\mathbb{C})$-action to its subgroup $S_{n}$ of permutation
matrices). Lemma 3.1 has the following immediate consequence:

######  Corollary 3.2.

For $d\geq 3$ the restriction of $\iota$ to the multilinear component $P_{m}$
of $\mathbb{C}\langle x_{1},\dots,x_{m}\rangle$ factors through an
$S_{m}$-equivariant $\mathbb{C}$-linear embedding

$\bar{\iota}:P_{m}/(I(\mathfrak{sl}_{2}(\mathbb{C}))\cap
P_{m})\to\mathcal{O}[\mathfrak{sl}_{2}(\mathbb{C})^{m+d-1}]_{(1^{m+d-1})}^{\mathfrak{sl}_{2}(\mathbb{C})}$

where on the right hand side we consider the restriction of the
$S_{m+d-1}$-action to its subgroup $S_{m}$ (the stabilizer in $S_{m+d-1}$ of
the elements $m+1,m+2,\dots,m+d-1$).

For a partition $\lambda\vdash m$ denote by $r(\lambda)$ the multiplicity of
$\chi^{\lambda}$ in the restriction to $S_{m}$ of the $S_{m+d-1}$-module
$\mathcal{O}[\mathfrak{sl}_{2}(\mathbb{C})^{m+d-1}]_{(1^{m+d-1})}^{\mathfrak{sl}_{2}(\mathbb{C})}$.
Corollary 3.2 immediately implies the following:

######  Corollary 3.3.

For $d\geq 3$ and any partition $\lambda\vdash m$ we have the inequality

$\mathrm{mult}_{\lambda}(\mathfrak{sl}_{2}(\mathbb{C}),\rho^{(d)})\leq
r(\lambda).$

The $S_{n}$-character of
$\mathcal{O}[\mathfrak{sl}_{2}(\mathbb{C})^{n}]_{(1^{n})}^{\mathfrak{sl}_{2}(\mathbb{C})}$
is known:

######  Proposition 3.4.

For a partition $\lambda\vdash n$ denote by $\nu(\lambda)$ the multiplicity of
$\chi^{\lambda}$ in the $S_{n}$-character of
$\mathcal{O}[\mathfrak{sl}_{2}(\mathbb{C})^{n}]_{(1^{n})}^{\mathfrak{sl}_{2}(\mathbb{C})}$.
Then we have

$\nu(\lambda)=\begin{cases}1\text{ for
}\lambda=(\lambda_{1},\lambda_{2},\lambda_{3})\text{ with
}\lambda_{1}\equiv\lambda_{2}\equiv\lambda_{3}\text{ modulo }2\\\ 0\text{
otherwise.}\end{cases}$

###### Proof.

The $\mathrm{GL}_{n}(\mathbb{C})$-module structure of
$\mathcal{O}[\mathfrak{sl}_{2}(\mathbb{C})^{n}]^{\mathfrak{sl}_{2}(\mathbb{C})}$
is given for example in [12, Theorem 2.2]. The isomorphism types of the
irreducible $\mathrm{GL}_{n}(\mathbb{C})$-module direct summands of the degree
$n$ homogeneous component of $\mathcal{O}[\mathfrak{sl}_{2}(\mathbb{C})^{n}]$
are labeled by partitions of $n$ with at most $3$ non-zero parts. The
multiplicity $\mu(\lambda)$ of the irreducible
$\mathrm{GL}_{n}(\mathbb{C})$-module $W_{\lambda}$ in the degree $n$
homogeneous component of
$\mathcal{O}[\mathfrak{sl}_{2}(\mathbb{C})^{n}]^{\mathfrak{sl}_{2}(\mathbb{C})}$
is $1$ if $\lambda_{1},\lambda_{2},\lambda_{3}$ have the same parity and is
zero otherwise. Note finally that the multilinear component of $W_{\lambda}$
is $S_{n}$-stable, and its $S_{n}$-character is $\chi^{\lambda}$ (see for
example [1, Corollary 6.3.11]). ∎

Following [11, Section I.1] for partitions $\lambda\vdash n$ and $\mu\vdash k$
we write $\lambda\subset\mu$ is $\lambda_{i}\leq\mu_{i}$ for all $i$.
Moreover, given $\lambda\vdash m$ and $\mu\vdash m+d-1$ with
$\lambda\subset\mu$, by a _standard tableau of shape_ $\mu/\lambda$ we mean a
sequence $\lambda^{(0)}\subset\lambda^{(1)}\subset\dots\subset\lambda^{(d-1)}$
of partitions $\lambda^{(i)}\vdash m+i$, where $\lambda^{(0)}=\lambda$,
$\lambda^{(d-1)}=\mu$. By the well-known branching rules for the symmetric
group, for $\lambda\vdash m$ the multiplicity of $\chi^{\lambda}$ in the
restriction to $S_{m}$ of the irreducible $S_{m+d-1}$-character $\chi^{\mu}$
equals the number of standard tableaux of shape $\mu/\lambda$ (see for example
[1, Theorem 6.4.11]). Therefore Proposition 3.4 has the following consequence.

######  Corollary 3.5.

We have the equality

$\displaystyle r(\lambda)=|\\{T\mid$ $\displaystyle T\text{ is a standard skew
tableau of shape }\mu/\lambda,$ $\displaystyle\mu\vdash m+d-1,\
\mu=(\mu_{1},\mu_{2},\mu_{3}),\ \mu_{1}\equiv\mu_{2}\equiv\mu_{3}\textrm{
modulo }2\\}|.$

######  Corollary 3.6.

For $d\geq 3$ we have the inequality $r(\lambda)\leq 3^{d-2}$.

###### Proof.

Associate to a standard skew tableau
$T=\lambda^{(0)}\subset\lambda^{(1)}\subset\dots\subset\lambda^{(d-1)}$ of
shape $\mu/\lambda$, where $\mu=(\mu_{1},\mu_{2},\mu_{3})\vdash m+d-1$ and
$\mu_{1}\equiv\mu_{2}\equiv\mu_{3}\textrm{ modulo }2$ the function
$f_{T}:\\{1,\dots,d-1\\}\to\\{1,2,3\\}$, which maps $j\in\\{1,\dots,d-1\\}$ to
the unique $i\in\\{1,2,3\\}$ such that the $i$th component of the partition
$\lambda^{(j)}$ is $1$ greater than the $i$th component of $\lambda^{(j-1)}$.
The assignment $T\mapsto f_{T}$ is obviously an injective map from the set of
standard skew tableaux of shape $\mu/\lambda$ into the set of functions
$\\{1,\dots,d-1\\}\to\\{1,2,3\\}$. We claim that at most $3^{d-2}$ functions
are contained in the image of this map. Indeed, if the three parts of
$\lambda^{(d-3)}$ have the same parity, then
$(f_{T}(d-2),f_{T}(d-1))\in\\{(1,1),(2,2),(3,3)\\}$, since the three parts of
$\mu=\lambda^{(d-1)}$ must have the same parity. If the three parts of
$\lambda^{(d-3)}$ do not have the same parity, say the first two components of
$\lambda^{(d-3)}$ have the same parity, and the third part has the opposite
parity, then $(f_{T}(d-2),f_{T}(d-1))\in\\{(1,2),(2,1)\\}$. Hence $r(\lambda)$
is not greater than $3$-times the number of functions from a $(d-3)$-element
set to a $3$-element set. Thus $r(\lambda)\leq 3^{d-2}$. ∎

###  3.1. Proof of Theorem 1.1

For $d\geq 3$ the statement follows from Corollary 3.3 and Corollary 3.6. For
the cases $d\leq 3$ see Remark 1.2 (i).

##  4\. A lower bound

######  Proposition 4.1.

For $d\geq 2$ we have the equality

$\mathrm{mult}_{(d-1,1)}(\mathfrak{sl}_{2}(\mathbb{C}),\rho^{(d)})=d-1.$

###### Proof.

For $k=0,1,\dots,d-2$ consider the element

$w_{k}:=x_{1}^{k}[x_{1},x_{2}]x_{1}^{d-2-k}\in\mathbb{C}\langle
x_{1},x_{2}\rangle=F_{2}.$

These elements are $\mathrm{GL}_{2}(\mathbb{C})$-highest weight vectors with
weight $(d-1,1)$, hence each generates an irreducible
$\mathrm{GL}_{2}(\mathbb{C})$-submodule isomorphic to $W_{(d-1,1)}$ (see the
proof of Proposition 3.4 for the notation $W_{\lambda}$: it is the polynomial
$\mathrm{GL}_{2}(\mathbb{C})$-module with highest weight
$\lambda=(\lambda_{1},\lambda_{2})$). Moreover, they are linearly independent
modulo the ideal $I(\mathfrak{sl}_{2}(\mathbb{C}),\rho^{(d)})$: indeed, make
the substitution $x_{1}\mapsto\rho(h)$, $x_{2}\mapsto\rho(e)$. Then we get

$\displaystyle w_{k}(\rho(h),\rho(e))$
$\displaystyle=(\sum_{i=1}^{d}(d+1-2i)E_{i,i})^{k}\cdot(2\sum_{i=1}^{d-1}iE_{i,i+1})\cdot(\sum_{i=1}^{d}(d+1-2i)E_{i,i})^{d-2-k}$
$\displaystyle=2\sum_{i=1}^{d-1}i(d+1-2i)^{k}(d-1-2i)^{d-2-k}E_{i,i+1}.$

Denote by $Z=(Z_{i,j})_{i,j=1}^{d-1}$ the $(d-1)\times(d-1)$ matrix whose
$(i,k+1)$ entry is the $(i,i+1)$-entry of $w_{k}(\rho(h),\rho(e))$ (i.e. the
coefficient of $E_{i.i+1}$ on the right hand side of the above equality). If
$i\neq\frac{d-1}{2}$, then

$Z_{i,k+1}=2(d-1-2i)^{d-2}\cdot\left(\frac{d+1-2i}{d-1-2i}\right)^{k}.$

Thus when $d$ is even, $Z$ is obtained from a Vandermonde matrix via
multiplying each row by a non-zero integer. Since the numbers
$\frac{d+1-2i}{d-1-2i}$, $i=1,\dots,d-1$ are distinct, we conclude that
$\det(Z)\neq 0$. When $d=2f-1$ is odd, the $(f-1)$th row of $Z$ is

$(0,\dots,0,2(f-1)2^{d-2}).$

Expand the determinant of $Z$ along this row; the $(d-2)\times(d-2)$ minor of
$Z$ obtained by removing the $(f-1)th$ row and the last column of $Z$ is again
obtained from a Vandermonde matrix by multiplying each row by a non-zero
integer. So $\det(Z)$ is non-zero also when $d$ is odd. This shows that the
elements $w_{k}(\rho(h),\rho(e))$, $k=0,1,\dots,d-2$ are linearly independent
in $\mathbb{C}^{d\times d}$. Consequently, no non-trivial linear combination
of $w_{0},w_{1},\dots,w_{d-2}$ belongs to
$I(\mathfrak{sl}_{2}(\mathbb{C}),\rho^{(d)})$. It follows that
$F_{2}/(I(\mathfrak{sl}_{2}(\mathbb{C}),\rho^{(d)})\cap F_{2})$ contains the
irreducible $\mathrm{GL}_{2}(\mathbb{C})$-module $W_{(d-1,1)}$ with
multiplicity $\geq d-1$. This multiplicity is in fact equal to $d-1$, because
$d-1$ is the multiplicity of $W_{(d-1,1)}$ as a summand in $F_{2}$. Recall
finally that for $\lambda=(\lambda_{1},\lambda_{2})\vdash m$, the multiplicity
of $\chi^{\lambda}$ in the cocharacter sequence coincides with the
multiplicity of $W_{\lambda}$ in
$F_{2}/(I(\mathfrak{sl}_{2}(\mathbb{C}),\rho^{(d)})\cap F_{2})$. ∎

## References

  * [1] E. Aljadeff, A. Giambruno, C. Procesi, A. Regev, Rings with Polynomial Identities and Finite Dimensional Algebras, AMS Colloquium Publications, Vol 66, Amer. Math. Soc., Providence, RI, 2020.
  * [2] A. Berele, A. Regev, Applications of hook Young diagrams to P.I. algebras, J. Algebra 82 (1983), 559-567.
  * [3] D. L. da Silva Macedo, P. Koshlukov, Codimension growth for weak polynomial identities and non-integrality of the PI exponent, Proc. Edinb. Math. Soc. 63 (2020), 929-949.
  * [4] M. Domokos, Matrix valued concomitants of $\mathfrak{sl}_{2}(\mathbb{C})$, preprint.
  * [5] M. Domokos, V. Drensky, Cocharacters for the weak polynomial identities of the Lie algebra of $3\times 3$ skew-symmetric matrices, Adv. Math. 374, Paper no: 107343 (2020).
  * [6] V. Drensky, Codimensions of T-ideals and Hilbert series of relatively free algebras, J. Algebra 91 (1984), 1-17.
  * [7] V. Drensky, Free Algebras and PI-Algebras, Springer-Verlag, Singapore, 2000.
  * [8] V. Drensky, Weak polynomial identities and their applications, Communications in Mathematics 29 (2021), 291-324.
  * [9] E. Formanek, Invariants and the ring of generic matrices, J. Algebra 89 (1984), 178-223.
  * [10] A. S. Gordienko, Codimensions of polynomial identities of representations of Lie algebras, Proc. Amer. Math. Soc. 141 (2013), 3369-3382.
  * [11] I.G. Macdonald, Symmetric Functions and Hall Polynomials, Oxford Univ. Press (Clarendon), Oxford, 1979, Second Edition, 1995.
  * [12] C. Procesi, Computing with $2\times 2$ matrices, J. Algebra 87 (1984), 342-359.
  * [13] Yu.P. Razmyslov, Finite basing of the identities of a matrix algebra of second order over a field of characteristic zero (Russian), Algebra i Logika 12 (1973), 83-113. Translation: Algebra and Logic 12 (1973), 47-63.
  * [14] Yu.P. Razmyslov, On a problem of Kaplansky (Russian), Izv. Akad. Nauk SSSR, Ser. Mat. 37 (1973), 483-501. Translation: Math. USSR, Izv. 7 (1973), 479-496.
  * [15] Yu.P. Razmyslov, Finite basis property for identities of representations of a simple three-dimensional Lie algebra over a field of characteristic zero (Russian), Algebra, Work Collect., dedic. O. Yu. Shmidt, Moskva 1982, 139-150. Translation: Transl. Am. Math. Soc. Ser. 2 140 (1988), 101-109.
  * [16] Yu.P. Razmyslov, Identities of Algebras and Their Representations (Russian), “Sovremennaya Algebra”, “Nauka”, Moscow, 1989. Translation: Translations of Math. Monographs 138, AMS, Providence, R.I., 1994.


# MoMa-Pos: Where Should Mobile Manipulators Stand in Cluttered Environment
Before Task Execution?

Beichen Shao1†, Yan Ding2†∗, Xingchen Wang1, Xuefeng Xie3, Fuqiang Gu1, Jun
Luo4, Chao Chen4∗ * Corresponding authors are Yan Ding
<EMAIL_ADDRESS>and Chao Chen (cschaochen@cqu.edu.cn). † Beichen Shao
and Yan Ding contribute equally.1 College of Computer Science, Chongqing
University2 Thomas J. Watson College of Engineering and Applied Science,
Binghamton University3 School of Management Science and Real Estate, Chongqing
University4 State Key Laboratory of Mechanical Transmission for Advanced
Equipment, Chongqing University

###### Abstract

Mobile manipulators always need to determine feasible base positions prior to
carrying out navigation-manipulation tasks. Real-world environments are often
cluttered with various furniture, obstacles, and dozens of other objects.
Efficiently computing base positions poses a challenge. In this work, we
introduce a framework named MoMa-Pos to address this issue. MoMa-Pos first
learns to predict a small set of objects that, taken together, would be
sufficient for finding base positions using a graph embedding architecture.
MoMa-Pos then calculates standing positions by considering furniture
structures, robot models, and obstacles comprehensively. We have extensively
evaluated the proposed MoMa-Pos across different settings (e.g., environment
and algorithm parameters) and with various mobile manipulators. Our empirical
results show that MoMa-Pos demonstrates remarkable effectiveness and
efficiency in its performance, surpassing the methods in the literature.
Supplementary material can be found at https://yding25.com/MoMa-Pos.

##  I Introduction

Mobile manipulators are increasingly being used in everyday environments like
homes, hospitals, and malls to perform a variety of navigation-manipulation
tasks. The importance of research in this field is rapidly growing, and
leading organizations, including Meta AI, have been frequently organizing
mobile manipulation challenges in recent years, such as the HomeRobot [1] and
Habitat Rearrangement [2] competitions. In these challenges, robots typically
navigate to targets like cups or refrigerators and then perform manipulation
tasks such as picking up cups or opening refrigerator doors. It is well-
recognized that the success of these tasks is heavily dependent on the robots’
base positioning [3, 4, 5]. Poor base positioning can significantly hinder the
robots’ ability to manipulate effectively, as illustrated in Fig. 1. Thus,
identifying practical base positions is crucial for the successful completion
of navigation-manipulation tasks.

However, the problem of practical base positions identification remains
challenging, especially in complex environments like residential spaces. The
location of the target object relative to furniture, such as refrigerators,
drawers, or tables, significantly influences the robot’s positioning. For
instance, a robot needs to be positioned directly in front of a refrigerator
to access its contents, whereas it can approach an item on a table from
various angles. Such complexity is further increased by potential obstacles
like chairs or children’s toys near the furniture. Worse still, different
robot models, each with unique design features, also require specific base
positions. For example, robots with shorter arms, such as Mobile ALOHA [6] and
Stretch [7], may need to position themselves closer to the target object.
These varying factors add to the complexity of calculating feasible base
positions.

Figure 1: The mobile manipulator’s current base position is not optimal for
effectively grasping the red bowl in the refrigerator (see Subfigure a) or the
bowl on the dining table (see Subfigure b). This is because the robot arm’s
movement is hindered by a complex environment. This is because the robot arm’s
movement is obstructed by a complex environment.

Current solutions for determining the base positions of mobile manipulators
have several limitations. One approach, detailed in [8, 3, 9], manually
defines feasible base position areas but fails to consider potential obstacles
near targets or differences in robot models. Another approach, as proposed in
[4], employs learning-based techniques to predict feasible base positions
while taking obstacles into account. Yet, this approach requires extensive
data collection and model training specific to each robot and scenario,
limiting its practical use. In light of these challenges, there is a critical
need for a universally adaptable method. Such a method should efficiently
address the complexities of various working environments and accommodate
different robot models as well.

A base position is considered feasible if the robot can plan a collision-free
trajectory and complete the manipulation task in the real world. This planning
is typically verified in a simulation before executing it in the real world.
However, simulating all environmental objects is time-consuming [10, 11]. We
propose that not all objects require simulation. For example, when calculating
a position to grasp a cup from a table, the robot does not need to consider
distant objects, like a refrigerator. By simulating only crucial objects, we
are able to reduce unnecessary modeling and collision detection. Nevertheless,
how to select the crucial objects is not simple. It requires careful
consideration of the specific environmental context to ensure that important
objects, such as chairs near the table, are included. Failing to include
sufficient items could result in incorrect assessments of feasible base
positions for the robot.

This work introduces MoMa-Pos, an efficient framework for determining feasible
base positions for mobile manipulators in cluttered environments before task
execution. The framework begins with the selection of important objects for
simulation, using a graph embedding architecture. It then dynamically
identifies a potential base position area for a robot, considering its
specific model, the target object’s position, and the furniture structure
comprehensively. Finally, a feasible base position is determined within the
area, ensuring efficiency by considering each position’s feasibility and
navigation cost. MoMa-Pos has been thoroughly tested with various
environments, algorithm parameters, and robots, demonstrating remarkable
effectiveness and efficiency that notably outperforms existing methods in the
literature.

##  II Problem Defnition

Figure 2: A mobile manipulator model includes three primary components: a
base, a body, and an arm. The symbol $\Delta r$ represents the horizontal
distance on the x-y plane between base’s position and the target object. For
explanations of additional symbols, see Section II. There are three types of
robots: Fetch, Husky+UR5e, and Segway+UR5e222For additional information on the
robots, refer to the following resources: Fetch Robotics (Zebra Technologies);
Husky Unmanned Ground Vehicle (Clearpath Robotics); UR5e Collaborative Robot
(Universal Robots); and Segway Robotics (Segway Robotics)..

In this section, we define the _base position computation problem_ in an
environment, denoted as $Env^{O}$. This environment encompasses a set of
objects, represented as $O=\\{o_{1},o_{2},\cdots,o_{N}\\}$. The target object
within these is specified as $o_{t}$, where $t\in[1,N]$. Each object $o_{i}$
has a 3D position $o_{i}^{p}$, a bounding box $o_{i}^{b}$ and a simulation
model $o_{i}^{sim}$. Note that this paper presupposes the ability of current
vision technologies to acquire these information, especially $o_{i}^{sim}$
[12, 13, 14].

A mobile manipulator is tasked with manipulating object $o_{t}$. This robot
model generally consists of at least three main components: a base, a body,
and an arm, as shown in Fig. 2. These components are represented by the tuple
$(r^{b},r^{h},r^{l})$, where $r^{b}$ indicates the base’s dimensions
$(r^{x},r^{y},r^{z})$ \- width, length, and height, respectively; $r^{h}$ is
the body’s height; and $r^{l}$ is the arm’s extension length. The robot’s 2D
base position is denoted as $r^{p}$. We assume $r^{p}$ is aligned vertically
with the arm base.

The primary _objective_ of this work is to pinpoint a feasible base position
$r^{p*}$ for navigation-manipulation tasks. Such a position must meet two
critical criteria: the arm must be able to compute collision-free trajectories
for task execution, and the base must avoid collisions with any objects in
$Env^{O}$.

Additionally, we define the _selective modeling problem_. In this context, the
robot’s task is to select a subset of objects $S\subseteq O$ for simulation,
which constitutes a subenvironment labeled $Env^{S}$. The _goal_ is to compute
$\min|S|$ such that isFeasible($r^{p},Env^{S},Env^{O}$) holds true. The
function isFeasible ensures that any position $r^{p}$ deemed feasible in
$Env^{S}$ is also feasible in $Env^{O}$.

##  III The MoMa-Pos Framework

In this section, we introduce MoMa-Pos, a three-stage method targeting two key
problems: predicting the importance of objects to solve the selective modeling
problem; calculating a potential area and pinpointing a feasible base position
for the mobile manipulator to address the base position computation problem.

###  III-A Predicting Object Importance for Modeling

Here, our objective is to select a subset of objects, $S$, from the set of
objects $O$. Instead of directly predicting $S$, we assess the importance of
each object and include those in $S$, whose importance surpasses a predefined
threshold $\alpha$. This approach of evaluating individual object importance
is efficient and allows for easy adjustment in case of initial selection
errors: simply decrease $\alpha$ and retry, as outlined in [15]. We have
developed a prediction model, $f:O\times O\rightarrow(0,1]$, to facilitate
this strategy. The model output, $f(o_{i},o_{t})$, indicates the likelihood of
including object $o_{i}$ in $S$ relative to the target object $o_{t}$. We
define this output as the _importance_ of object $o_{i}$ concerning object
$o_{t}$.

When considering model training methods, we faced a choice between supervised
and unsupervised learning techniques. Due to the difficulties in obtaining
precise labels, even in small-scale environments, we chose an unsupervised
learning approach. This decision was guided by _our observation that an
object’s importance score, $o_{i}$, is often positively correlated with its
spatial proximity to the target object, $o_{t}$, and its size, denoted as
$o_{i}^{b}$._ Recognizing these correlations enabled us to bypass the need for
exact labels, as we could infer importance based on spatial and size
attributes. To implement this insight in our unsupervised model, we structured
our method into three steps. The central idea is to calculate spatial
proximity between objects $o_{i}$ and $o_{t}$ within a graph-based
architecture.

####  III-A1 Modeling Environment $Env^{O}$ as a Directed Graph $G=(V,E)$

In $Env^{O}$, each object $o$ is represented as a node $v\in V$ , with
attributes such as the object’s size $o^{b}$. The spatial relationships
between objects are expressed through edges in the set $E$, where $E\subseteq
V\times V$. An edge $(v_{i},v_{j})\in E$ signifies the spatial relationship
between objects linked to nodes $v_{i}$ and $v_{j}$. The _direction_ of this
edge reflects their spatial hierarchy. An edge $(v_{i},v_{j})\in E$ exists if
object $o_{i}$ is _on_ , _in_ , or _inside_ object $o_{j}$, or if both objects
$o_{i}$ and $o_{j}$ are _on the floor_. The _weight_ of an edge
$(v_{i},v_{j})$ determined by the formula
${1}/{\text{dist}_{xy}(o_{i},o_{j})}$, where $\text{dist}_{xy}$ measures the
horizontal distance between $o_{i}$ and $o_{j}$.

####  III-A2 Embedding Graph $G$ with DeepWalk Algorithm

To evaluate the importance score of object $o_{i}$ (represented as node
$v_{i}$ in graph $G$), we adapted the DeepWalk algorithm, originally proposed
by Perozzi et al. [16], focusing on the spatial proximity between node $v_{i}$
and the target node $v_{t}$. DeepWalk generates node sequences through _random
walks_ on the graph. Starting at a node, it randomly moves to adjacent nodes
for a set number of steps, creating a node “sentence”. These sequences,
similar to sentences in natural language, help in learning nodes’ latent
representations, reflecting their contextual relationships in the graph. Our
approach innovates by utilizing _biased random walks_ , which adjust the
transition probability $P$ between any two nodes, $v_{i}$ and $v_{j}$,
according to the equation below, using a weighted function
$w(v_{i},v_{j})=k_{0}/\text{dist}_{xy}(o_{i},o_{j})+(1-k_{0})\times
size(o_{j})$. Here, $k_{0}$ acts as a tuning parameter. This adjustment allows
for generating sequences that more accurately reflect the nodes’ significance.

$P(v_{i},v_{j})=\begin{cases}\frac{w(v_{i},v_{j})}{\sum_{u\in
N(v_{i})}w(v_{i},u)},&(v_{i},v_{j})\in E\\\ 0,&otherwise\end{cases}$

where $N(v_{i})$ represents the set of nodes adjacent to $v_{i}$.

####  III-A3 Scoring Object Importance

After obtaining node embeddings in graph $G$, we determine the importance
score of each object $o_{i}$ (node $v_{i}$) by calculating the cosine
similarity [17] with the reference target node $v_{t}$. The nodes are then
ranked according to these importance scores. Objects with a score exceeding a
predefined threshold $\alpha$, where $\alpha\in[0.0,1.0]$, are added to the
set $S$. An intelligent framework should allow $\alpha$ to self-adjust for
optimal performance. In our version, we start with a slightly higher $\alpha$,
based on empirical data. If MoMa-Pos fails, we reduce $\alpha$ to accommodate
more new objects.

Figure 3: The upper left figure provides a comprehensive view of the robots’
operating environment. The three figures on the right highlight selected
objects crucial for the tasks at hand in simulation. The positions where the
robots could potentially stand are indicated by squares. The target objects
are shown with red circles, located within various pieces of furniture such as
a fridge, drawer, and table. In example (1), it’s evident that when an object
is positioned deep inside the fridge, the number of feasible base positions is
smaller. This observation aligns with our common sense. Best viewed in the
enlarged digital version.

###  III-B Computing Potential Base Position Area

To determine the potential base position area, $A$, for a robot, we consider
both the robot’s model and the target object’s position, $o_{t}^{p}$,
together. However, not every position inside $A$ ensures successful object
manipulation due to potential interference from furniture and obstacles. Our
next step involves assessing each sampled position $r^{p}\in A$ for
feasibility using a potential-based method. These two steps are detailed in
the following.

The area $A$ can be calculated according to the following equation:

$\begin{split}A=\left\\{r^{p}\mid\text{dist}_{xy}(r^{p},o_{t}^{p})\leq\Delta
r,\,\forall
i,\,\neg\text{overlap}\left(r^{p},r^{b},o_{i}^{p},o_{i}^{b}\right)\right\\}\end{split}$

Here, $\Delta r$ is the allowable horizontal distance between a position
position $r^{p}$ and the target $o_{t}^{p}$, illustrated in a red line in Fig.
2(c). The overlap function checks collisions between the robot’s base and each
surrounding object $o_{i}$ by comparing their positions and boundaries. More
specifically, $\Delta r$ can be calculated using the formula
$\sqrt{(r^{l})^{2}-(o_{t}^{p.z}-r^{z}-r^{h})^{2}}$. Here, $r^{l}$, the
distance from the object to the robot’s arm base (shown in green in the
figure), varies within the arm’s extension range, $l_{1}$ to $l_{2}$. These
limits, $l_{1}$ and $l_{2}$, can be derived from the robot’s DH matrix. The
term $|o_{t}^{p.z}-r^{z}-r^{h}|$, marked as a blue line in the figure,
indicates the z-axis distance between these points.

To assess the feasibility of a position $r^{p}\in A$, we examine it in the
context of the surrounding furniture. This method is inspired by the potential
field concept [18], where the target object $o_{t}$ exerts an attractive
force, and furniture exerts a repulsive force. Initially, we sample a 3D
position $(r^{p},z)$, and connect it to target object position $o_{t}^{p}$
forming a line. We then evaluate if this line collides with the furniture’s
bounding box, considering $z$ values within the range
$[\omega,r_{z}+r_{h}+l_{2}]$. Here, $\omega$ denotes the lowest z-axis value
attainable by the robot gripper. In case of a collision, the potential value
$F(r^{p},z)$ is set to $0.0$, indicating that the robot gripper is unable to
reach the target object without encountering obstacles. Otherwise, we
calculate $F(r^{p},z)$ using the equation:
$F(r^{p},z)=k_{2}/\text{dist}_{xy}(r^{p},o_{t}^{p})$, where $k_{2}$ is a
negative coefficient. We average the potential values for each 2D base
position $r^{p}$ using the formula
$F(r^{p})=1/k_{3}\times\sum_{i=1}^{k_{3}}F(r^{p},z_{i})$, where $k_{3}$ is a
positive constant. Generally, lower potential values suggest a base position
is more feasible. Fig. 3 illustrates potential values for various sampled
positions in a specific kitchen environment with furniture during object
manipulation tasks.

###  III-C Identifying a Feasible Base Position

Inside the area $A$, we uniformly sample $M$ 2D positions $r^{p}_{i}$, where
$M\in[1,\infty)$ in total. Each position has an average potential value,
$F(r^{p}_{i})$, where lower values suggest better feasibility. Our MoMa-Pos
aims to provide a single feasible base position. One naive approach might
first try the base position with the lowest potential value and compute a
collision-free trajectory to manipulate the target object using a motion
planner, denoted as PLAN (e.g., RRT* [19]), to identify if the base position
is feasible. If this fails, we would test positions with incrementally higher
potential values until a feasible one is found. However, this method may incur
high navigation costs. To optimize, our goal is to strike a balance between
potential values and navigation costs.

We aim to find an optimal path that connects all sampled base positions,
minimizing both factors. This problem resembles the Traveling Salesman Problem
(TSP) [20], but with a key distinction: the robot does not need to return to
the starting position, making it an Open TSP [21]. Considering the high number
of positions ($M$ will be pretty big), we simplify the problem by grouping
positions into smaller sets based on their potential values, where each set
contains $T$ candidate positions which is much smaller than $M$. Each set is
then analyzed to determine the optimal path, proceeding to the next set if a
feasible base position is not found within the current one. Within a set, each
edge directly connects two sampled positions, $r^{p}_{i}$ and $r^{p}_{j}$. The
weight of each edge considers both the distance
$\text{dist}_{xy}(r^{p}_{i},r^{p}_{j})$, and their potential values. More
specifically, the weight is calculated using the formula:
$k_{4}\times\text{dist}(r^{p}_{i},r^{p}_{j})+k_{4}^{\prime}\times\left(F(r^{p}_{j})-F(r^{p}_{i})\right)$,
where $k_{4}$ and $k_{4}^{\prime}$ are two user-specified positive
coefficients. To solve the Open TSP, we can apply various algorithms, ranging
from exact methods [22] suitable for smaller groups ($T$) to heuristic [23]
and metaheuristic [24] approaches for larger datasets. Upon determining the
sequence of positions, we sequentially visit and compute trajectory for each.
The search concludes when a collision-free trajectory is found, and the
corresponding position, $r^{p*}$, is selected as the feasible base position
for output eventually.

Lemma 1 (MoMa-Pos is complete). _Given any object importance scorer $f:O\times
O\rightarrow(0,1]$, threshold $\alpha\in[0.0,1.0]$, and $M$ uniformly sampled
positions, $M\in[1,\infty)$, if the motion planner PLAN is complete, then
MoMa-Pos is complete._

###### Proof:

Given the codomain of $f$ excludes 0, an $\alpha>0$ exists such that $\forall
o\in O,f(o,o)\geq\alpha$. With $M\rightarrow\infty$, a feasible position, if
existent, will be sampled eventually. Given PLAN’s completeness, MoMa-Pos also
achieves completeness. Hence, for any task and an infinite number of samples,
MoMa-Pos will identify at least one solution, assuming one exists, through
PLAN. ∎

##  IV Experiments

In our experiments, we aim to answer the following questions: Q1: How does
MoMa-Pos’s ability to identify feasible base positions compare with current
approaches? Q2: How effective is the object importance scoring function within
MoMa-Pos? Q3: How do key parameters within MoMa-Pos affect its performance?
Q4: How does MoMa-Pos perform across different mobile manipulators?

###  IV-A Experimental Setup

In this study, we tasked a mobile manipulator with grasping a target object in
a complex kitchen environment featuring various pieces of furniture with fixed
locations, as shown in Fig. 3. Besides these pieces of furniture, there are 10
other objects, such as a plate and a bowl, placed randomly in different
locations. We set one target object for the trials, with its placement varying
randomly. The target positions are categorized into six types: _on the dinner
table_ , _on the table_ , _on the countertop_ , _in the fridge_ , _in the
drawer_ , and _in the dishwasher_. These mentioned pieces of furniture can be
divided into two groups: _containers_ and _non-containers_. Containers, with
their more complex internal structures, may increase the complexity of
computing base positions. In our experiments, we ensured that the doors of
these containers were fully opened. For each category, the approach for
identifying base position underwent 25 trials. In each trial, the exact
position of the target object was different. For instance, in one trial, the
target object might be deep inside the fridge. The sampling-based motion
planner employs RRT*, implemented using the well-known open-source library
OMPL [25]. We chose the Segway+UR5e mobile manipulator as depicted in Fig. 2
(c), with a consistent starting position in all trials.

Methods |  _On Dinner Table_ (Non-Container) |  _On Table_ (Non-Container) |  _On Countertop_ (Non-Container)
---|---|---|---
|  Time (s) |  Cost (m) |  Rate (%) |  Time (s) |  Cost (m) |  Rate (%) |  Time (s) |  Cost (m) |  Rate (%)
_MoMa-Pos_ (ours) |  3.5 $\pm$ 0.8 |  2.1 $\pm$ 0.1 |  100.0 |  3.2 $\pm$ 1.0 |  1.3 $\pm$ 0.0 |  100.0 |  2.4 $\pm$ 0.1 |  1.5 $\pm$ 0.1 |  100.0
_Habitat_ |  3.3 $\pm$ 0.4 |  2.2 $\pm$ 0.0 |  100.0 |  3.3 $\pm$ 1.2 |  1.4 $\pm$ 0.1 |  100.0 |  2.6 $\pm$ 0.1 |  1.7 $\pm$ 0.1 |  100.0
_M3_ |  3.3 $\pm$ 0.4 |  2.3 $\pm$ 0.0 |  100.0 |  3.3 $\pm$ 1.2 |  1.4 $\pm$ 0.0 |  100.0 |  2.8 $\pm$ 0.1 |  1.7 $\pm$ 0.1 |  100.0
_Reuleaux_ |  5.7 $\pm$ 1.0 |  2.6 $\pm$ 0.4 |  100.0 |  6.3 $\pm$ 0.6 |  1.9 $\pm$ 0.3 |  100.0 |  6.3 $\pm$ 0.7 |  2.1 $\pm$ 0.3 |  100.0

Methods |  _In Fridge_ (Container) |  _In Drawer_ (Container) |  _In Dishwasher_ (Container)
---|---|---|---
|  Time (s) |  Cost (m) |  Rate (%) |  Time (s) |  Cost (m) |  Rate (%) |  Time (s) |  Cost (m) |  Rate (%)
_MoMa-Pos_ (ours) |  15.5 $\pm$ 8.4 |  2.0 $\pm$ 0.3 |  100.0 |  15.8 $\pm$ 2.2 |  2.6 $\pm$ 0.4 |  100.0 |  12.8 $\pm$ 3.7 |  2.8 $\pm$ 0.3 |  100.0
_Habitat_ |  5.8 $\pm$ 2.4 |  1.0 $\pm$ 0.2 |  20.0 |  5.0 $\pm$ 0.1 |  2.1 $\pm$ 0.2 |  40.0 |  4.6 $\pm$ 1.1 |  1.4 $\pm$ 0.0 |  20.0
_M3_ |  50.1 $\pm$ 43.7 |  5.2 $\pm$ 3.1 |  60.0 |  49.5 $\pm$ 36.8 |  7.9 $\pm$ 5.5 |  60.0 |  50.1 $\pm$ 43.0 |  5.9 $\pm$ 3.9 |  60.0
_Reuleaux_ |  32.5 $\pm$ 30.8 |  3.3 $\pm$ 2.9 |  80.0 |  40.7 $\pm$ 10.6 |  5.7 $\pm$ 2.9 |  80.0 |  19.5 $\pm$ 8.2 |  3.0 $\pm$ 0.8 |  100.0

TABLE I: A comparison between MoMa-Pos and baseline methods in terms of task
execution time (Time), navigation cost (Cost), and success rate (Rate) across
different furniture categories, namely containers and non-containers. The
optimal results are highlighted in bold.

We compare our methods with the following baselines:

  * •

Habitat [2]: For non-container furniture like tables, the closest navigable
position to the target is chosen. For container furniture such as drawers and
refrigerators, a fixed position relative to the furniture is selected.

  * •

M3 [3]: It begins by designating a specific area, divided into $5\times 5$ cm
cells. For non-container furniture, the closest navigable position to the
target is chosen. For container furniture, it randomly selects base positions
within the designated area until it finds one that is feasible.

  * •

Reuleaux [26]: Similar to M3, it starts by designating a specific area,
divided into $5\times 5$ cm cells. It then evaluates how easily the robot can
reach the target without obstacles. The robot chooses its base position
randomly, prioritizing those with the highest reachability to ensure optimal
accessibility.

To ensure a fair comparison, all baselines are evaluated within a complete
working environment, excluding the time cost of modeling the simulation
environment. We measure performance of all approaches using the following
metrics: _task execution time_ (Time), measured in seconds; _navigation cost_
(Cost) measured in meters; and _success rate_ (Rate) within a 100-second
timeframe. To provide a more detailed analysis of the time consumption for
identifying feasible positions, we calculated the time taken for each step
involved in the process. The process involves two primary stages: first,
identifying potential candidates, with the time required for this phase
represented by $\text{Time}_{\text{Phase1}}$; second, assessing the viability
of these candidates through the application of RRT*, with the associated time
consumption denoted as $\text{Time}_{\text{Phase2}}$. To concentrate on the
efficiency of the task’s main elements, we omit navigation time from the task
execution time. This decision stems from the robot’s moving speed variability,
which can add considerable variance unrelated to the task’s completion
efficiency. Instead, the navigation cost metric separately evaluates the
robot’s spatial movement efficiency, ensuring it doesn’t affect the direct
assessment of task performance.

Our experiments were conducted on a computer equipped with an AMD EPYC 7452
32-Core Processor, 64 CPU threads, an Nvidia GTX 2080 graphics card, and 128GB
of RAM. To support reproducibility, we have made all the code publicly
available. Visit our website for more information: https://yding25.com/MoMa-
Pos.

###  IV-B Results and Analysis

####  IV-B1 MoMa-Pos vs. Baselines

We aim to answer question Q1 here. The main results are shown in TABLE I. The
table reveals that our method consistently achieves a 100% success rate across
all trials in the working environment. Compared to the baseline methods
(Habitat, M3, and Reuleaux), the success rate of MoMa-Pos is significantly
higher, especially with container-type furniture like fridge. This is
attributed to our method’s ability to consider furniture structure,
effectively avoiding obstructions. MoMa-Pos also stands out in efficiency,
outperforming baselines M3 and Reuleaux. These methods depend on random
sampling within a predefined area and often fail to locate a viable position
quickly, leading to increased time costs and performance inconsistency, as
seen with the high variance in M3 and Reuleaux’s results. Although Habitat is
more efficient sometimes, its much lower success rate, particularly with
container-type furniture, limits its practical application. Our method not
only shows significant advantages in success rate and time efficiency with
container-type furniture but also ensures the lowest navigation cost for
finding feasible solutions. MoMa-Pos consistently identifies a feasible
solution within a maximum of 15.8 seconds in our tests.

Interestingly, MoMa-Pos exhibits slightly higher efficiency than Habitat when
the target object is placed on both the table and the countertop. To
understand this result, we calculated $\text{Time}_{\text{Phase1}}$ and
$\text{Time}_{\text{Phase2}}$ for MoMa-Pos and Habitat in the “On Table”
scenario, as shown in TABLE II. MoMa-Pos outperforms Habitat in both metrics.
This is attributed to the sometimes large predefined area, which marginally
increases the time needed to find a navigable position. Additionally, the time
required for an IK solution near the target’s closest position is also
slightly longer, likely due to increased obstacles in that area.

Methods |  $\text{Time}_{\text{Phase1}}$ |  $\text{Time}_{\text{Phase2}}$
---|---|---
_MoMa-Pos_ (ours) |  0.045 $\pm$ 0.00038 |  3.09 $\pm$ 1.1
_Habitat_ |  0.097 $\pm$ 0.00049 |  3.19 $\pm$ 1.6
TABLE II: Time consumption comparison between MoMa-Pos and Habitat for various
stages, where the target object is placed _on the table_.

####  IV-B2 Object Importance Prediction in MoMa-Pos

We aim to answer question Q2 here. Our experimentation begins by setting the
threshold value $\alpha$ (specifically, 0.45) within the object importance
prediction module. The achieved success rate of 100% confirms that no crucial
object has been overlooked. Fig. 4 illustrates the task execution times for
MoMa-Pos and a variant devoid of the prediction module. It is clear that
incorporating prediction in MoMa-Pos markedly decreases computation time.
Additionally, it is observed that the execution time for container-type
furniture is slightly higher. For example, the average execution time for a
fridge stands at about 4.2 seconds, in contrast to less than 1.2 seconds for a
table. This variation is primarily due to the higher number of objects
situated around the fridge and their inclusion within the simulation
environment, consequently extending the modeling time for a fridge.

Figure 4: The modeling time comparison between MoMa-Pos and its variant, which
lacks the object importance prediction component, with the $x$-axis denoting
the location of the target object.

####  IV-B3 Important Parameters in MoMa-Pos

We aim to answer question Q3 here. We evaluate the success rate of MoMa-Pos
over various timeframes. It’s evident that the allotted timeframe
significantly influences performance metrics. Given sufficient time, MoMa-Pos
is inherently complete, capable of invariably identifying a viable base
position. To ascertain the impact of different time constraints on success
rates, we designate timeframes of 10, 15, 20, 25, 30, and 35 seconds for our
assessment. The outcomes, as detailed in TABLE III, reveal a positive
correlation between extended timeframes and improved success rates,
corroborating intuitive expectations. Notably, the success rate keeps 100%
when the duration exceeds 20 seconds.

Timeframe (s) |  10 |  15 |  20 |  25 |  30 |  35
---|---|---|---|---|---|---
Rate |  86% |  96% |  100% |  100% |  100% |  100%
TABLE III: Performance of MoMa-Pos across various timeframes

We are also interested in examining the distribution of time required to
pinpoint a feasible base position. Fig. 5 presents the results of this
examination. It is evident from the figure that the majority of the time (over
98% of the total time cost) is dedicated to identifying the feasibility
through a sampling-based motion planner, namely RRT*. In contrast, the time
allocated for selecting candidates is significantly lesser, accounting for
less than 2% of the total time cost (approximately 0.1 seconds). This duration
includes the time spent on solving the Open Traveling Salesman Problem (TSP).

Figure 5: Distribution of the time allocated for identifying a feasible base
position when placing the target object in non-container-type and container-
type furniture, respectively.

####  IV-B4 Different Mobile Manipulators

Our framework was subjected to testing across a variety of mobile
manipulators. The results, as depicted in TABLE IV, underscore a 100% success
rate, highlighting the framework’s robustness. This demonstrates the
versatility of our method, making it adaptable to a wide range of scenarios.

Robot Type |  Fetch |  Husky+UR5e |  Segway+UR5e
---|---|---|---
Rate |  100% |  100% |  100%
TABLE IV: Performance of MoMa-Pos across various robot types

##  V Related Work

This section discusses two principal methodologies for computing robot base
positions in robotics: rule-based and learning-based approaches.

###  V-A Rule-based Base Position Computation

Rule-based approaches typically utilize precomputed robot reachability maps to
quickly determine suitable base positions. These maps, generated using Inverse
Kinematics (IK) solutions, illustrate feasible tool center point (TCP)
positions for a stationary robot base. Representative studies include [27, 28,
26, 29, 30, 31]. Some techniques, such as [27, 26], use a compact 6D grid to
simplify these maps, although this requires extensive grid point calculations.
Frequently, identifying a single feasible base position is sufficient, rather
than mapping all possible positions. Zhang et al. [5] enhanced this
methodology by incorporating factors like energy efficiency and rapid
execution. They combined reachability maps with evolutionary algorithms. Other
strategies involve defining feasible positions manually and applying heuristic
techniques for fixed-base tasks, as demonstrated in [2]. Our proposed method,
MoMa-Pos, distinguishes itself in this domain by being the first to account
for complex furniture structures, such as refrigerators and drawers, when
determining feasible robot base positions. MoMa-Pos is not just efficient; it
prioritizes identifying a single viable position, which is vital for smooth
integration with other systems. Additionally, MoMa-Pos features a selective
modeling process, further enhancing the system’s overall efficiency.

###  V-B Learning-based Base Position Computation

Learning-based methods, in contrast to rule-based ones, utilize data-driven
techniques for greater adaptability in various scenarios, particularly in
dynamic and unstructured environments. For instance, Stulp et al. [32]
directly learn the robot arm’s reachability and inverse reachability using
density networks. Meanwhile, Zhang et al. [4] aim to improve the navigation of
mobile manipulators in obstacle-rich environments. They develop a model, which
is trained on a specialized dataset, to specifically predict the feasibility
of base positions. Further, Honerkamp et al. [33] introduce a deep
reinforcement learning approach for generating dynamic motions in mobile
manipulators. This method effectively adapts end-effector trajectories to
various kinematic scenarios and platforms, applicable in both simulations and
real-world settings. Additionally, Gu et al. [3] manually define an initial
base position area for robots and subsequently train a reinforcement learning
policy to execute tasks within the designated area. In contrast to these
methods, our MoMa-Pos system requires significantly less training and is
designed for straightforward integration with other systems. Moreover, unlike
reinforcement learning-based methods, MoMa-Pos is capable of providing
explicit base positions.

##  VI Discussion and Future Work

In this work, we demonstrated that MoMa-Pos effectively identifies feasible
positions for navigation-manipulation tasks. We conclude by acknowledging the
limitations of our study, reflecting on the implications of our findings, and
highlighting opportunities for future research. A significant limitation we
encountered is the lack of discussion on the performance of MoMa-Pos with
inaccurate simulation models. In the real world, encountering inaccurate
models is common, despite the remarkable advancements in computer vision and
3D modeling technologies. We have not explored whether MoMa-Pos’s performance,
particularly in terms of task execution time, would deteriorate under such
conditions. Theoretically, MoMa-Pos should still be able to find feasible
positions, as we have demonstrated its completeness. Another constraint of the
current framework is the inability of certain critical parameters, such as
$\alpha$, to adapt automatically. Moving forward, we aim to address these
limitations to enhance MoMa-Pos’s performance further.

## References

  * [1] S. Yenamandra, A. Ramachandran, K. Yadav, A. Wang, M. Khanna, T. Gervet, T.-Y. Yang, V. Jain, A. W. Clegg, J. Turner, _et al._ , “Homerobot: Open-vocabulary mobile manipulation,” _arXiv preprint arXiv:2306.11565_ , 2023.
  * [2] S. Andrew, Y. Karmesh, C. Alex, B. Vincent-Pierre, G. Aaron, C. Angel, S. Manolis, K. Zsolt, and B. Dhruv, “Habitat rearrangement challenge 2022,” 2022.
  * [3] J. Gu, D. S. Chaplot, H. Su, and J. Malik, “Multi-skill mobile manipulation for object rearrangement,” _arXiv preprint arXiv:2209.02778_ , 2022.
  * [4] X. Zhang, Y. Zhu, Y. Ding, Y. Zhu, P. Stone, and S. Zhang, “Visually grounded task and motion planning for mobile manipulation,” _arXiv preprint arXiv:2202.10667_ , 2022.
  * [5] H. Zhang, K. Mi, and Z. Zhang, “Base placement optimization for coverage mobile manipulation tasks,” _arXiv preprint arXiv:2304.08246_ , 2023.
  * [6] Z. Fu, T. Z. Zhao, and C. Finn, “Mobile aloha: Learning bimanual mobile manipulation with low-cost whole-body teleoperation,” in _arXiv_ , 2024.
  * [7] C. C. Kemp, A. Edsinger, H. M. Clever, and B. Matulevich, “The design of stretch: A compact, lightweight mobile manipulator for indoor human environments,” in _International Conference on Robotics and Automation (ICRA)_ , 2022, pp. 3150–3157.
  * [8] A. Szot, A. Clegg, E. Undersander, E. Wijmans, Y. Zhao, J. Turner, N. Maestre, M. Mukadam, D. S. Chaplot, O. Maksymets, _et al._ , “Habitat 2.0: Training home assistants to rearrange their habitat,” _Advances in Neural Information Processing Systems_ , vol. 34, pp. 251–266, 2021.
  * [9] X. Puig, E. Undersander, A. Szot, M. D. Cote, T.-Y. Yang, R. Partsey, R. Desai, A. W. Clegg, M. Hlavac, S. Y. Min, _et al._ , “Habitat 3.0: A co-habitat for humans, avatars and robots,” _arXiv preprint arXiv:2310.13724_ , 2023.
  * [10] K. Mo, S. Zhu, A. X. Chang, L. Yi, S. Tripathi, L. J. Guibas, and H. Su, “Partnet: A large-scale benchmark for fine-grained and hierarchical part-level 3d object understanding,” in _IEEE/CVF conference on Computer Vision and Pattern Recognition_ , 2019, pp. 909–918.
  * [11] Q. Chen, M. Memmel, A. Fang, A. Walsman, D. Fox, and A. Gupta, “Urdformer: Constructing interactive realistic scenes from real images via simulation and generative modeling,” in _Towards Generalist Robots: Learning Paradigms for Scalable Skill Acquisition@ CoRL2023_ , 2023.
  * [12] W. Liu, D. Anguelov, D. Erhan, C. Szegedy, S. Reed, C.-Y. Fu, and A. C. Berg, “Ssd: Single shot multibox detector,” in _ECCV_ , 2016, pp. 21–37.
  * [13] R. Girshick, “Fast R-CNN,” in _ICCV_ , 2015, pp. 1440–1448.
  * [14] T. Hodaň, M. Sundermeyer, B. Drost, Y. Labbé, E. Brachmann, F. Michel, C. Rother, and J. Matas, “Bop challenge 2020 on 6d object localization,” in _ECCV Workshops_ , 2020, pp. 577–594.
  * [15] T. Silver, R. Chitnis, A. Curtis, J. B. Tenenbaum, T. Lozano-Perez, and L. P. Kaelbling, “Planning with learned object importance in large problem instances using graph neural networks,” in _AAAI_ , vol. 35, no. 13, 2021, pp. 11 962–11 971.
  * [16] B. Perozzi, R. Al-Rfou, and S. Skiena, “Deepwalk: Online learning of social representations,” in _Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining_ , 2014, pp. 701–710.
  * [17] M. Vijaymeena and K. Kavitha, “A survey on similarity measures in text mining,” _Machine Learning and Applications: An International Journal_ , vol. 3, no. 2, pp. 19–28, 2016.
  * [18] S. S. Ge and Y. J. Cui, “Dynamic motion planning for mobile robots using potential field method,” _Autonomous robots_ , vol. 13, pp. 207–222, 2002.
  * [19] S. Karaman and E. Frazzoli, “Sampling-based algorithms for optimal motion planning,” _The international journal of robotics research_ , vol. 30, no. 7, pp. 846–894, 2011.
  * [20] K. L. Hoffman, M. Padberg, G. Rinaldi, _et al._ , “Traveling salesman problem,” _Encyclopedia of operations research and management science_ , vol. 1, pp. 1573–1578, 2013.
  * [21] H. H. Chieng and N. Wahid, “A performance comparison of genetic algorithm’s mutation operators in n-cities open loop travelling salesman problem,” in _Recent Advances on Soft Computing and Data Mining: SCDM-2014_. Springer, 2014, pp. 89–97.
  * [22] S. Boyd and J. Mattingley, “Branch and bound methods,” _Notes for EE364b, Stanford University_ , vol. 2006, p. 07, 2007.
  * [23] G. Kizilateş and F. Nuriyeva, “On the nearest neighbor algorithms for the traveling salesman problem,” in _Advances in Computational Science, Engineering and Information Technology: CCSEIT-2013_. Springer, 2013, pp. 111–118.
  * [24] E. Osaba, X.-S. Yang, and J. Del Ser, “Traveling salesman problem: a perspective review of recent research and new results with bio-inspired metaheuristics,” _Nature-inspired Computation and Swarm Intelligence_ , pp. 135–164, 2020.
  * [25] I. A. Sucan, M. Moll, and L. E. Kavraki, “The open motion planning library,” _IEEE Robotics & Automation Magazine_, vol. 19, no. 4, pp. 72–82, 2012.
  * [26] A. Makhal and A. K. Goins, “Reuleaux: Robot base placement by reachability analysis,” in _IEEE International Conference on Robotic Computing (IRC)_ , 2018, pp. 137–142.
  * [27] N. Vahrenkamp, T. Asfour, and R. Dillmann, “Robot placement based on reachability inversion,” in _IEEE International Conference on Robotics and Automation_ , 2013, pp. 1970–1975.
  * [28] F. Zacharias, C. Borst, M. Beetz, and G. Hirzinger, “Positioning mobile manipulators to perform constrained linear trajectories,” in _IROS_ , 2008, pp. 2578–2584.
  * [29] M. Attamimi, K. Ito, T. Nakamura, and T. Nagai, “A planning method for efficient mobile manipulation considering ambiguity,” in _IEEE/RSJ International Conference on Intelligent Robots and Systems_ , 2012, pp. 965–972.
  * [30] F. Zacharias, C. Borst, and G. Hirzinger, “Capturing robot workspace structure: representing robot capabilities,” in _IROS_ , 2007, pp. 3229–3236.
  * [31] F. Reister, M. Grotz, and T. Asfour, “Combining navigation and manipulation costs for time-efficient robot placement in mobile manipulation tasks,” _IEEE Robotics and Automation Letters_ , vol. 7, no. 4, pp. 9913–9920, 2022.
  * [32] F. Stulp, A. Fedrizzi, and M. Beetz, “Action-related place-based mobile manipulation,” in _IROS_ , 2009, pp. 3115–3120.
  * [33] D. Honerkamp, T. Welschehold, and A. Valada, “Learning kinematic feasibility for mobile manipulation through deep reinforcement learning,” _IEEE Robotics and Automation Letters_ , vol. 6, no. 4, pp. 6289–6296, 2021.