# On Lengths of $\mathbb{F}_{2}[x,y,z]/(x^{d_{1}},y^{d_{2}},z^{d_{3}},x+y+z)$

Han  University of Michigan<EMAIL_ADDRESS>,  Kenkel  Grinnell College
<EMAIL_ADDRESS>,  Li  University of Michigan<EMAIL_ADDRESS>,
Venkatesh  University of Michigan<EMAIL_ADDRESS>and  Wiles  University of
Michigan<EMAIL_ADDRESS>
###### Abstract.

In this paper, we provide a formula for the vector space dimension of the ring
$\mathbb{F}_{2}[x,y,z]/(x^{d_{1}},y^{d_{2}},z^{d_{3}},x+y+z)$ over
$\mathbb{F}_{2}$ when $d_{1},d_{2},d_{3}$ all lie between successive powers of
$2$. For general $d_{1},d_{2},d_{3}$, we provide a simple algorithm to
calculate the vector space dimension of
$\mathbb{F}_{2}[x,y,z]/(x^{d_{1}},y^{d_{2}},z^{d_{3}},x+y+z)$ by combining our
formula with certain results of [Han92].

##  1\. Introduction

Let $R=\mathbb{F}[x_{1},\dots,x_{n}]$ be the polynomial ring over a field
$\mathbb{F}$ and let $I$ be an ideal such that $R/I$ is artinian, and thus a
finite-dimensional vector space over $\mathbb{F}$. A natural question is to
ask for the vector space dimension of $R/I$, both in total, and in each graded
component. Perhaps the simplest example is
$R/(x_{1}^{d_{1}},\dots,x_{n}^{d_{n}})$ for some non-negative integers
$d_{1},\dots,d_{n}$; its total vector space dimension is just
$\prod_{i=1}^{n}d_{i}$ while the vector space dimension in each graded
component was studied in [RRR91]. Adding in only one ideal generator
complicates the problem; the vector space dimensions of $R/I$ when
$I=(x_{1}^{d_{1}},\dots,x_{n}^{d_{n}},x_{1}+\dots+x_{n})$ are remarkably more
complicated. Properties of this ring have been studied in [Han92, HM93, Vra15,
KRV23, KRV22], for example. In this paper, we study this ring in the special
case $\mathbb{F}=\mathbb{F}_{2}:=\mathbb{Z}/2\mathbb{Z}$ and $n=3$.

For a graded ring $S$, let $S_{D}$ denote the degree $D$ component. In the
case that $\mathbb{F}$ is a field of characteristic 0, it was shown by Stanley
[Sta80, Theorem 2.4] that the element $x+y+z+J$ has the Strong Lefschetz
Property in the ring $\mathbb{F}[x,y,z]/(x^{d_{1}},y^{d_{2}},z^{d_{3}})$
meaning that the map

$\mathbb{F}[x,y,z]/(x^{d_{1}},y^{d_{2}},z^{d_{3}})_{D}\xrightarrow[]{x+y+z+J}\mathbb{F}[x,y,z]/(x^{d_{1}},y^{d_{2}},z^{d_{3}})_{D+1}$

has maximal possible rank, where $J=(x^{d_{1}},y^{d_{2}},z^{d_{3}})$. In other
words, multiplication by $x+y+z+J$ is either injective or surjective,
depending on the vector space dimension of
$\mathbb{F}[x,y,z]/(x^{d_{1}},y^{d_{2}},z^{d_{3}})$ in degrees $D$ and $D+1$.
One could use this information to calculate
$\dim_{\mathbb{F}}(R/(x^{d_{1}},y^{d_{2}},z^{d_{3}},x+y+z))_{D}$.

However, the element $x+y+z+J$ does not have the Strong Lefschetz Property
when $\mathbb{F}$ is a field of positive characteristic. As an example,
consider $\mathbb{F}=\mathbb{F}_{2}$ and $d_{1}=d_{2}=d_{3}=2$ and
$J=(x^{2},y^{2},z^{2})$. Then
$(\mathbb{F}_{2}[x,y,z]/((x^{2},y^{2},z^{2}))_{1}$ has vector space basis
$\\{x,y,z\\}$ and thus is dimension 3, and
$\mathbb{F}_{2}[x,y,z]/((x^{2},y^{2},z^{2})_{2}$ has vector space basis
$\\{xy,xz,yz\\}$ and also has dimension 3. Yet multiplication by $x+y+z+J$ is
not injective; note that $x+y+z$ is not in the ideal $(x^{2},y^{2},z^{2})$,
yet

$(x+y+z)\cdot(x+y+z)=x^{2}+y^{2}+z^{2},$

which is in the ideal $(x^{2},y^{2},z^{2})$. Thus
$(x+y+z+J)\cdot(x+y+z+J)=0+J$ in the quotient ring
$\mathbb{F}[x,y,z]/(x^{2},y^{2},z^{2})$, so multiplication by $x+y+z+J$ is not
injective.

######  Notation 1.1.

We write $\dim_{\mathbb{F}}(R/I)$ to denote the vector space dimension of
$R/I$ over the field $\mathbb{F}$. Additionally, for convenience of notation,
let

$\displaystyle\dim_{\mathbb{F}}(d_{1},d_{2},d_{3})$
$\displaystyle:=\dim_{\mathbb{F}}\mathbb{F}[x,y,z]/(x^{d_{1}},y^{d_{2}},z^{d_{3}},x+y+z).$

In [Han92, Chapter 2], it was shown that, when $\mathbb{F}$ is a field of
positive characteristic, there exists a half-integer
$[d_{1},d_{2},d_{3}]_{\mathbb{F}}$ such that

$\dim_{\mathbb{F}}(d_{1},d_{2},d_{3})=\frac{2d_{1}d_{2}+2d_{1}d_{3}+2d_{2}d_{3}-d_{1}^{2}-d_{2}^{2}-d_{3}^{2}}{4}+([d_{1},d_{2},d_{3}]_{\mathbb{F}})^{2}.$

Furthermore, the value of $[d_{1},d_{2},d_{3}]_{\mathbb{F}}$ is such that the
generators of the colon ideal (see Definition 2.2 for the definition of a
colon ideal) $J=(x^{d_{1}},y^{d_{2}}:(x+y)^{d_{3}})$ have degrees
$\frac{d_{1}+d_{2}-d_{3}}{2}-[d_{1},d_{2},d_{3}]_{\mathbb{F}}$ and
$\frac{d_{1}+d_{2}-d_{3}}{2}+[d_{1},d_{2},d_{3}]_{\mathbb{F}}$. The value of
these ideal generators is not trivial to calculate; in [Han92, Proposition
2.5], she gives a relationship between $[d_{1},d_{2},d_{3}]_{\mathbb{F}}$ and
a certain matrix of binomial coefficients. In [Han92, Theorem 2.23], she also
gives a way of determining $[d_{1},d_{2},d_{3}]_{\mathbb{F}}$ depending on
where the point $(d_{1},d_{2},d_{3})$ lies in a geometric honeycombing of
$\mathbb{R}^{3}$ with octahedra and tetrahedra.

The goal of this paper is to obtain explicit formulas for
$\dim_{\mathbb{F}}(d_{1},d_{2},d_{3})$ when $\mathbb{F}=\mathbb{F}_{2}$. In
the case that $d_{1},d_{2}\leq 2^{e}\leq d_{3}$,
$\dim_{\mathbb{F}_{2}}(d_{1},d_{2},d_{3})$ was given in [Han92, Proposition
1.6(i)], and the case that $d_{1}\leq 2^{e}\leq d_{2},d_{3}$,
$\dim_{\mathbb{F}_{2}}(d_{1},d_{2},d_{3})$ was described in [Han92,
Proposition 1.6(ii)] in terms of the dimension of a smaller vector space. The
only remaining case is when $2^{e}\leq d_{1}\leq d_{2}\leq d_{3}\leq 2^{e+1}$,
the case in which all three powers are between two consecutive powers of 2.
Our main result is the following formula for the dimension in this case.

######  Theorem 1.2.

Let $q$ be a power of $2$ and let $\frac{q}{2}<d_{1},d_{2},d_{3}\leq q$. Then:

$\dim_{\mathbb{F}_{2}}\frac{\mathbb{F}_{2}[x,y,z]}{(x^{d_{1}},y^{d_{2}},z^{d_{3}},x+y+z)}=d_{1}d_{2}+d_{2}d_{3}+d_{1}d_{3}-q(d_{1}+d_{2}+d_{3})+q^{2}.$

We will now say a few words on how we came up with the formula. Using
Macaulay2 ([GS]), we first restricted our attention to the case when
$d_{2}=d_{3}$. To seek a pattern, we compared
$\dim_{\mathbb{F}_{2}}(d_{1},d_{2},d_{2})$ to
$\dim_{\mathbb{F}_{2}}(d_{1},d_{2}-1,d_{2}-1)$ and looked at values of $d_{1}$
ranging from 1 to 128, and $d_{2}$ ranging from 1 to 64. Part of the data is
shown in Figure 1.

Figure 1. Column $i$, row $j$ stores the value:
$\dim_{\mathbb{F}_{2}}(i,j,j)-\dim_{\mathbb{F}_{2}}(i,j-1,j-1)$

Notice that the value in each row in Figure 1 increases by 2 up until the row
is a power of 2. Furthermore, for a fixed column, the data repeats after the
row is larger than some power of 2. It follows that to find
$\dim_{\mathbb{F}_{2}}(i,j,j)$, we could add up every entry in column $i$
(note also that $\dim_{\mathbb{F}_{2}}(i,0,0)=0$). Using the formula for the
sum of consecutive odds, and by observing how much the pattern deviates (see
rows 8 and 9) after the next immediate power of 2, we were able to guess a
formula for $\dim_{\mathbb{F}_{2}}(d_{1},d_{2},d_{3})$. Finally, by fixing
$d_{1}$ and varying $d_{2},d_{3}$ all within the consecutive powers of 2, we
were able to come up with a conjectural formula for
$\dim_{\mathbb{F}_{2}}(d_{1},d_{2},d_{3})$ when
$\frac{q}{2}<d_{1},d_{2},d_{3}\leq q$ for some $q=2^{e}$, which we then proved
by rather elementary methods.

It is unclear how well these results can be generalized to different ideals,
as general ideals will not exhibit symmetry in the variables like the ideal
$(x^{d_{1}},y^{d_{2}},z^{d_{3}},x+y+z)$. Interestingly, a similar pattern was
observed for the case of polynomials over $\mathbb{F}_{3}$, however it appears
to be much more complex.

Outline. The paper is organized as follows. We recall some standard
definitions in Section 2 and the relevant results of [Han92] in Section 3. We
then give a proof of Theorem 1.2 in Section 4 and describe the algorithm for
computing the dimension in the general case in Section 5.

Acknowledgements. We would like to thank the LoG(M) program ([LoG]) at the
University of Michigan for providing a platform to run this project. We
appreciate the guidance of Ahmad Barhoumi and Sam Hansen.

##  2\. Background

Let $R=\mathbb{F}[x_{1},\ldots,x_{n}]$ denote the polynomial ring in $n$
variables with coefficients in a field $\mathbb{F}$. We recall the following
standard definitions.

######  Definition 2.1.

  1. (1)

An element $f\in R$ is said to be a monomial if $f=x_{1}^{i_{1}}\dots
x_{n}^{i_{n}}$ for some $i_{1},\dots,i_{n}\in\mathbb{Z}_{\geq 0}$.

  2. (2)

The degree of a monomial $x_{1}^{i_{1}}\dots x_{n}^{i_{n}}$ is defined to be
$i_{1}+\dots+i_{n}$ and the degree of a polynomial
$f=\displaystyle\sum_{(i_{1},\dots,i_{n})\in(\mathbb{Z}_{\geq
0})^{n}}a_{i_{1},\dots,i_{n}}x_{1}^{i_{1}}\dots x_{n}^{i_{n}}\in R$ is defined
to be $\max\\{i_{1}+\dots+i_{n}\mid a_{i_{1},\dots,i_{n}}\neq 0\\}$.

We will now review some definitions from commutative algebra.

######  Definition 2.2 (Colon Ideal).

Let $I$ and $J$ be arbitrary ideals in a commutative ring $R$. The colon ideal
$(I:J)$ is the set

$(I:J)\coloneqq\\{r\in R:rJ\subseteq I\\}.$

To verify that this is an ideal, suppose $a_{1},a_{2}\in(I:J)$. Then
$a_{1}j\in I$ for all $j\in J$ and $a_{2}j\in I$ for all $j\in J$. Thus
$(a_{1}+a_{2})j=a_{1}j+a_{2}j\in I$, since $I$ is an ideal and thus closed
under addition. Similarly, if $a\in(I:J)$ and $r\in R$, then $(ra)j=r(aj)\in
I$ for all $j\in J$, since $I$ is an ideal.

######  Definition 2.3 (Short Exact Sequence).

Let $A,B$ and $C$ be vector spaces, and let $f,g$ be linear transformations
$f:A\to B,g:B\to C$ such that $f$ is injective, $g$ is surjective, and
$\ker(g)=\operatorname{im}(f)$. Then we say that the sequence

$0\to A\xrightarrow[]{f}B\xrightarrow[]{g}C\to 0$

is a short exact sequence. Note that the kernel of each map is equal to the
image of the previous map.

######  Lemma 2.4.

Let $A,B$ and $C$ be vector spaces such that

$0\to A\xrightarrow[]{f}B\xrightarrow[]{g}C\to 0$

is a short exact sequence. Then

$\dim(B)=\dim(A)+\dim(C).$

In other words, vector space dimension is additive across short exact
sequences.

###### Proof.

By the Rank Nullity Theorem,

$\dim(B)=\operatorname{rank}(g)+\dim(\ker(g)).$

By assumption, $g$ is surjective, so $\operatorname{rank}(g)=\dim(C)$.
Furthermore, we also assumed that $\ker(g)=\operatorname{im}(f)$, so
$\dim(\ker(g))=\dim(\operatorname{im}(f))=\operatorname{rank}(f)$. Since $f$
is injective, another use of the Rank Nullity Theorem tells us that

$\dim(A)=\operatorname{rank}(f)+\dim(\ker(f))=\operatorname{rank}(f).$

Thus we have that

$\dim(B)=\dim(A)+\dim(C).$

∎

As a precursor to our main result, we will now discuss the vector space
dimension of simpler rings: $R/(x_{1}^{d_{1}},\ldots,x_{n}^{d_{n}})$ and
$R_{D}$, where $R=\mathbb{F}[x_{1},\dots,x_{n}]$.

  1. (1)

Observe that the set of all monomials is a basis for $R$ as a vector space
over $\mathbb{F}$. Similarly, we see that the set of monomials
$S=\\{x_{1}^{i_{1}}\dots x_{n}^{i_{n}}\mid 0\leq i_{j}\leq d_{j}-1\text{ for
every }j\\}$ is a basis for $R/(x_{1}^{d_{1}},\ldots,x_{n}^{d_{n}})$. The
number of elements of $S$ is given by $\prod_{i=1}^{n}d_{i}$ since for an
arbitrary element $x_{1}^{i_{1}}\dots x_{n}^{i_{n}}$ of $S$, $i_{j}$ has
$d_{j}$ choices for each $j$. This gives

$\dim_{\mathbb{F}}R/(x_{1}^{d_{1}},\ldots,x_{n}^{d_{n}})=\prod_{i=1}^{n}d_{i}.$

  2. (2)

To calculate $\dim_{\mathbb{F}}(R_{D})$, we count the number of monomials
$x_{1}^{d_{1}}\cdots x_{n}^{d_{n}}$ of degree $D$, which is equivalent to
finding the number of non-negative integer solutions to:

$d_{1}+\ldots+d_{n}=D\quad\text{such that}\quad 0\leq d_{i}$

We use a “stars and bars” argument, in which we think of $D$, the total number
of indeterminates in the monomial, as the number of stars, and the bars divide
the indeterminates into $n$ categories, one for each variable
$x_{1},\dots,x_{n}$. We then see that

$\dim_{\mathbb{F}}(R_{D})=\binom{D+n-1}{n-1}.$

##  3\. Han’s results

We now revisit the quotient ring of interest $R/I$ where
$R=\mathbb{F}_{2}[x,y,z]$ and $I=(x^{d_{1}},y^{d_{2}},z^{d_{3}},x+y+z)$.
Notice that $I$ is not a monomial ideal and so, unlike in the previous
section, nonzero monomials in $R/I$ don’t necessarily form a basis for $R/I$
over $\mathbb{F}$. For example, the elements $\\{x+I,y+I,z+I\\}$ do not form a
linearly independent set since $x+y+z+I=0+I$. So, counting the vector space
dimension of $R/I$ is more complicated.

We now construct an isomorphism of $R/I$ to a polynomial ring in one fewer
variable. First, we define notation that will be useful.

######  Notation 3.1.

Let $R$ be a commutative ring, $I$ an ideal of $R$, and $r$ and element of
$R$. When the ideal $I$ is clear by context, we use $\overline{r}$ to denote
the congruence class $r+I\in R/I$.

Consider the map:

$\displaystyle\phi:\mathbb{F}_{2}[x,y,z]/(x^{d_{1}},y^{d_{2}},z^{d_{3}},x+y+z)$
$\displaystyle\to\mathbb{F}_{2}[x,y]/(x^{d_{1}},y^{d_{2}},(x+y)^{d_{3}})$
$\displaystyle\varphi(\overline{f(x,y,z))})$
$\displaystyle=\overline{f(x,y,(x+y))}$

We can easily check that $\varphi$ is well defined and a ring homomorphism. In
fact, $\varphi$ is an isomorphism since we can define the inverse map as
follows:

$\displaystyle\varphi^{-1}:\mathbb{F}_{2}[x,y]/(x^{d_{1}},y^{d_{2}},(x+y)^{d_{3}})$
$\displaystyle\to\mathbb{F}_{2}[x,y,z]/(x^{d_{1}},y^{d_{2}},z^{d_{3}},x+y+z)$
$\displaystyle\varphi^{-1}(\overline{f(x,y)})$
$\displaystyle=\overline{f(x,y)}.$

Let us check that $\varphi^{-1}$ is well-defined. Suppose that
$f(x,y)-g(x,y)\in(x^{d_{1}},y^{d_{2}},(x+y)^{d_{3}}))$. Then
$f(x,y)-g(x,y)=ax^{d_{1}}+by^{d_{2}}+c(x+y)^{d_{3}}$ for some
$a,b,c\in\mathbb{F}_{2}[x,y]$. Note also that in
$\mathbb{F}_{2}[x,y,z]/(x^{d_{1}}$,$y^{d_{2}},z^{d_{3}},(x+y+z))$, the
congruence classes $z+(x^{d_{1}},y^{d_{2}},z^{d_{3}},x+y+z)$ and
$x+y+(x^{d_{1}},y^{d_{2}},z^{d_{3}},x+y+z)$ are equal. Thus,
$\overline{(x+y)^{d_{3}}}=\overline{z^{d_{3}}}$. Therefore,
$ax^{d_{1}}+by^{d_{2}}+c(x+y)^{d_{3}}\in(x^{d_{1}},y^{d_{2}},z^{d_{3}},(x+y+z))$.
Thus $\overline{f(x,y)}=\overline{g(x,y)}$ in
$\mathbb{F}_{2}[x,y,z]/(x^{d_{1}},y^{d_{2}},z^{d_{3}},(x+y+z))$, so the map is
well-defined.

Let us now check that $\varphi\circ\varphi^{-1}$ and
$\varphi^{-1}\circ\varphi$ are the identity maps on
$\mathbb{F}_{2}[x,y]/(x^{d_{1}},y^{d_{2}},(x+y)^{d_{3}})$ and
$\mathbb{F}_{2}[x,y,z]/(x^{d_{1}},y^{d_{2}},z^{d_{3}},(x+y+z))$, respectively.
For any $f\in\mathbb{F}_{2}[x,y]$. we have

$\displaystyle\varphi(\varphi^{-1}(\overline{f(x,y}))$
$\displaystyle=\varphi(\overline{f(x,y)})$ $\displaystyle=\overline{f(x,y)}$

since $f(x,y)$ does not contain $z$. Conversely, for any
$f(x,y,z)\in\mathbb{F}_{2}[x,y,z]$, we have

$\displaystyle\varphi^{-1}(\varphi(\overline{f(x,y,z))})$
$\displaystyle=\varphi^{-1}(\overline{f(x,y,x+y)})$
$\displaystyle=\overline{f(x,y,x+y)}$ $\displaystyle=\overline{f(x,y,z))}$

since $\overline{x+y}=\overline{z}$ in
$\mathbb{F}_{2}[x,y,z]/(x^{d_{1}},y^{d_{2}},z^{d_{3}},x+y+z)$. Thus we have an
isomorphism:

$\mathbb{F}_{2}[x,y,z]/(x^{d_{1}},y^{d_{2}},z^{d_{3}},x+y+z)\xrightarrow{\sim}\mathbb{F}_{2}[x,y]/(x^{d_{1}},y^{d_{2}},(x+y)^{d_{3}})$

In particular, we have:

(1)
$\dim_{\mathbb{F}_{2}}\mathbb{F}_{2}[x,y,z]/(x^{d_{1}},y^{d_{2}},z^{d_{3}},x+y+z)=\dim_{\mathbb{F}_{2}}\mathbb{F}_{2}[x,y]/(x^{d_{1}},y^{d_{2}},(x+y)^{d_{3}}),$

Also, we note that the LHS above is symmetric in $d_{1},d_{2},d_{3}$ and so,
the RHS is as well. Therefore we may and will assume that $d_{1}\leq d_{2}\leq
d_{3}$.

We now state two results from [Han92], specialized to the particular case
$\mathbb{F}=\mathbb{F}_{2}$, which tell us how to calculate
$\dim_{\mathbb{F}_{2}}\mathbb{F}_{2}[x,y]/(x^{d_{1}},y^{d_{2}},(x+y)^{d_{3}})$
in certain cases.

######  Proposition 3.2.

[Han92, Proposition 1.6 (i)] Suppose that $d_{1},d_{2}\leq q$, and $d_{3}\geq
q$ where $q=2^{e}$ is some power of 2. Then:

$\displaystyle\dim_{\mathbb{F}_{2}}\mathbb{F}_{2}[x,y]/(x^{d_{1}},y^{d_{2}},(x+y)^{d_{3}})$
$\displaystyle=\dim_{\mathbb{F}_{2}}\mathbb{F}_{2}[x,y]/(x^{d_{1}},y^{d_{2}})$
$\displaystyle=d_{1}\cdot d_{2}$

######  Proposition 3.3.

[Han92, Proposition 1.6 (ii)] Suppose that $d_{1}\leq q$, and $d_{2},d_{3}\geq
q$ where $q=2^{e}$ is some power of 2. Then:

$\displaystyle\dim_{\mathbb{F}_{2}}\mathbb{F}_{2}[x,y]/(x^{d_{1}},y^{d_{2}},(x+y)^{d_{3}})=\>$
$\displaystyle d_{1}\cdot q$ $\displaystyle+\>$
$\displaystyle\dim_{\mathbb{F}_{2}}\mathbb{F}_{2}[x,y]/(x^{d_{1}},y^{d_{2}-q},(x+y)^{d_{3}-q})$

##  4\. Proof of Theorem 1.2

In this section, we provide a proof of Theorem 1.2. Let us recall the
statement.

See 1.2

By Equation 1, it suffices to show that

$\dim_{\mathbb{F}_{2}}\frac{\mathbb{F}_{2}[x,y]}{(x^{d_{1}},y^{d_{2}},(x+y)^{d_{3}})}=d_{1}d_{2}+d_{2}d_{3}+d_{1}d_{3}-q(d_{1}+d_{2}+d_{3})+q^{2}.$

To prove Theorem 1.2, we first prove the following lemmas.

######  Lemma 4.1.

Let $q$ be a power of $2$ and let $\frac{q}{2}<d_{1}\leq d_{2}\leq q$. For any
$\frac{q}{2}<t<q$, define:

$\displaystyle J_{t}:=(x^{d_{1}},y^{d_{2}},(x+y)^{t}).$

Then:

$\dim\frac{J_{t}}{J_{t+1}}=d_{1}+d_{2}-q.$

###### Proof.

Consider $S=\\{x^{i}(x+y)^{t}\mid 0\leq i\leq d_{1}+d_{2}-q-1\\}$. We will
prove in two steps that $S$ is a basis of $\frac{J_{t}}{J_{t+1}}$, thereby
proving the lemma.

Step 1: Let us show that $S$ is a spanning set of $\frac{J_{t}}{J_{t+1}}$.
First observe that:

$\displaystyle(x+y)^{t+1}$ $\displaystyle=(x+y)(x+y)^{t}$
$\displaystyle=x(x+y)^{t}+y(x+y)^{t}$ $\displaystyle\implies x(x+y)^{t}$
$\displaystyle=y(x+y)^{t}\text{ in }\frac{J_{t}}{J_{t+1}}.$

Thus $\frac{J_{t}}{J_{t+1}}$ is spanned by the set $\\{x^{i}(x+y)^{t}\mid
i\geq 0\\}$. Now, if we have $x^{i}(x+y)^{t}$ for any $i\geq d_{1}+d_{2}-q$,
writing $i=i_{1}+i_{2}$ with $i_{1}\geq d_{1}-\frac{q}{2}$ and $i_{2}\geq
d_{2}-\frac{q}{2}$, we get:

$\displaystyle x^{i}(x+y)^{t}$
$\displaystyle=x^{i_{1}}y^{i_{2}}(x+y)^{\frac{q}{2}}(x+y)^{t-\frac{q}{2}}$
$\displaystyle=x^{i_{1}}y^{i_{2}}(x^{\frac{q}{2}}+y^{\frac{q}{2}})(x+y)^{t-\frac{q}{2}}$
$\displaystyle=(x^{\frac{q}{2}+i_{1}}y^{i_{2}}+x^{i_{1}}y^{\frac{q}{2}+i_{2}})(x+y)^{t-\frac{q}{2}}$
$\displaystyle=0$

since $x^{d_{1}}=0=y^{d_{2}}\text{ in }\frac{J_{t}}{J_{t+1}}$. This finishes
Step 1.

Step 2: Let us show that $S$ is linearly independent. Assume for the sake of
contradiction that there exists:

$\sum_{i=0}^{d_{1}+d_{2}-q-1}\lambda_{i}x^{i}(x+y)^{t}=0\text{ in
}\frac{J_{t}}{J_{t+1}}$

with $\lambda_{a}\neq 0$ (equivalently, $\lambda_{a}=1$) for some $0\leq a\leq
d_{1}+d_{2}-q-1$. We get:

$\displaystyle\sum_{i=0}^{d_{1}+d_{2}-q-1}\lambda_{i}x^{i}(x+y)^{t}=x^{d_{1}}f+y^{d_{2}}g+(x+y)^{t+1}h\text{
in }\mathbb{F}_{2}[x,y]$ $\displaystyle\implies$
$\displaystyle(x+y)^{t}\left(\sum_{i=0}^{d_{1}+d_{2}-q-1}\lambda_{i}x^{i}-(x+y)h\right)=x^{d_{1}}f+y^{d_{2}}g.$

for some $f,g,h\in\mathbb{F}_{2}[x,y]$. Now look at this equality in degree
$t+a$:

$(x+y)^{t}\left(x^{a}-(x+y)\widetilde{h}\right)=x^{d_{1}}\widetilde{f}+y^{d_{2}}\widetilde{g}$

where $\widetilde{f},\widetilde{g},\widetilde{h}$ are homogeneous polynomials.
Multiply by $(x+y)^{q-1-t}$ on both sides to get:

(2)
$(x+y)^{q-1}\left(x^{a}-(x+y)\widetilde{h}\right)=x^{d_{1}}\left[(x+y)^{q-1-t}\widetilde{f}\right]+y^{d_{2}}\left[(x+y)^{q-1-t}\widetilde{g}\right].$

We will now produce a term $x^{b_{1}}y^{b_{2}}$ in the LHS such that
$b_{1}<d_{1}$ and $b_{2}<d_{2}$. This would be a contradiction since every
monomial $x^{a_{1}}y^{a_{2}}$ appearing in the RHS of (2) has either
$a_{1}\geq d_{1}$ or $a_{2}\geq d_{2}$. By Lemma 4.2 below, we can write

$\displaystyle x^{a}-(x+y)\widetilde{h}=\sum_{i=0}^{a}\mu_{i}x^{i}y^{a-i}$

with $\mu_{i}$ satisfying $\displaystyle\sum_{i=0}^{a}\mu_{i}=1$. Therefore we
get:

$\displaystyle(x+y)^{q-1}\left(\sum_{i=0}^{a}\mu_{i}x^{i}y^{a-i}\right)$
$\displaystyle=\left(\sum_{i=0}^{q-1}x^{i}y^{q-1-i}\right)\left(\sum_{i=0}^{a}\mu_{i}x^{i}y^{a-i}\right)$
$\displaystyle=\sum_{i=0}^{q-1+a}\left(\sum_{k=\max(i-(q-1),0)}^{\min(i,a)}\mu_{k}\right)x^{i}y^{q-1+a-i}.$

Now, consider the term $x^{d_{1}-1}y^{q+a-d_{1}}$. Since $d_{1}-1<q-1$, we
have that $\max(d_{1}-1-(q-1),0)=0$, and since $d_{1}-1\geq
d_{1}-1+d_{2}-q\geq a$, we have that $\min(d_{1}-1,a)=a$. Therefore the
coefficient of $x^{d_{1}-1}y^{q+a-d_{1}}$ is just
$\displaystyle\sum_{k=0}^{a}\mu_{i}=1$. This implies that the term
$x^{d_{1}-1}y^{q+a-d_{1}}$ survives in the LHS of (2) and it is indeed of the
form $x^{b_{1}}y^{b_{2}}$ s.t. $b_{1}<d_{1}$ and $b_{2}<d_{2}$, since
$q+a-d_{1}<d_{2}$. This finishes the proof. ∎

######  Lemma 4.2.

Let $S_{d}$ denote the set of all homogeneous degree $d$ polynomials in
$\mathbb{F}_{2}[x,y]$. Consider the following injective map:

$\displaystyle\varphi_{a}:S_{a-1}$ $\displaystyle\hookrightarrow S_{a}$
$\displaystyle p(x,y)$ $\displaystyle\mapsto x^{a}-p(x,y)(x+y).$

Then the image is exactly the subset

$\left\\{\sum_{i=0}^{a}\mu_{i}x^{i}y^{a-i}\mid\displaystyle\sum_{i=0}^{a}\mu_{i}=1\right\\}.$

###### Proof.

Note that $S_{a}$ is a vector space over $\mathbb{F}_{2}$ of dimension $a+1$.
Consider the linear map given by evaluating at $(1,1)$:

$\displaystyle\mathrm{ev}:S_{a}$ $\displaystyle\to\mathbb{F}_{2}$
$\displaystyle\sum_{i=0}^{a}\mu_{i}x^{i}y^{a-i}=:r(x,y)$ $\displaystyle\mapsto
r(1,1)=\sum_{i=0}^{a}\mu_{i}.$

Observe:

$\mathrm{ev}^{-1}(1)=\\{\sum_{i=0}^{a}\mu_{i}x^{i}y^{a-i}\mid\sum_{i=0}^{a}\mu_{i}=1\\}.$

The set $\mathrm{ev}^{-1}(1)$ has $2^{a}$ elements since it is a translate of
the kernel of $\mathrm{ev}$. Now, for any $p(x,y)\in S_{a-1}$, we have that
$x^{a}-p(x,y)(x+y)\in\mathrm{ev}^{-1}(1)$ since its value at $(1,1)$ is $1$.
Thus $\mathrm{Im}(\varphi_{a})\subset\mathrm{ev}^{-1}(1)$. But since both sets
have $2^{a}$ elements, we get $\mathrm{Im}(\varphi_{a})=\mathrm{ev}^{-1}(1)$
as required. ∎

We can now finally prove Theorem 1.2.

###### Proof of Theorem 1.2.

We will prove the theorem by descending induction on $d_{3}$ with the base
case being $d_{3}=q$. Denote:

$f(d_{1},d_{2},d_{3})=d_{1}d_{2}+d_{2}d_{3}+d_{1}d_{3}-q(d_{1}+d_{2}+d_{3})+q^{2}.$

When $d_{3}=q$, Corollary 3.2 gives:

$\dim_{\mathbb{F}_{2}}\frac{\mathbb{F}_{2}[x,y]}{(x^{d_{1}},y^{d_{2}},(x+y)^{q})}=d_{1}d_{2},$

while

$\displaystyle f(d_{1},d_{2},q)$
$\displaystyle=d_{1}d_{2}+d_{2}q+qd_{1}-q(d_{1}+d_{2}+q)+q^{2}$
$\displaystyle=d_{1}d_{2},$

which proves the base case of the induction.

Now, fix an $N\in\mathbb{N}$ with $\frac{q}{2}<N<q$ and assume by induction
that the result is true for all $d_{3}$ with $N<d_{3}\leq q$. Let us prove the
result for $d_{3}=N$. With notation as in Lemma 4.1, we have:

$\dim_{\mathbb{F}_{2}}\frac{\mathbb{F}_{2}[x,y]}{J_{N+1}}=d_{1}d_{2}+d_{2}(N+1)+(N+1)d_{1}-q(d_{1}+d_{2}+N+1)+q^{2}.$

We have the exact sequence:

$0\to\frac{J_{N}}{J_{N+1}}\to\frac{\mathbb{F}_{2}[x,y]}{J_{N+1}}\to\frac{\mathbb{F}_{2}[x,y]}{J_{N}}\to
0.$

By Lemma 4.1, we have that:

$\dim_{\mathbb{F}_{2}}\frac{J_{N}}{J_{N+1}}=d_{1}+d_{2}-q.$

Putting all of these together, we get:

$\displaystyle\dim_{\mathbb{F}_{2}}\frac{\mathbb{F}_{2}[x,y]}{J_{N}}=$
$\displaystyle\dim_{\mathbb{F}_{2}}\frac{\mathbb{F}_{2}[x,y]}{J_{N+1}}-\dim_{\mathbb{F}_{2}}\frac{J_{N}}{J_{N+1}}$
$\displaystyle=$
$\displaystyle\left(d_{1}d_{2}+d_{2}(N+1)+(N+1)d_{1}-q(d_{1}+d_{2}+N+1)+q^{2}\right)$
$\displaystyle-(d_{1}+d_{2}-q)$ $\displaystyle=$ $\displaystyle
d_{1}d_{2}+d_{2}N+Nd_{1}-q(d_{1}+d_{2}+N)+q^{2}$ $\displaystyle=$
$\displaystyle f(d_{1},d_{2},N).$

This finishes the proof. ∎

##  5\. Algorithm for calculating
$\dim\mathbb{F}_{2}[x,y,z]/(x^{d_{1}},y^{d_{2}},z^{d_{3}},x+y+z)$

We now give an algorithm to calculate the dimension of
$\mathbb{F}_{2}[x,y,z]/(x^{d_{1}},y^{d_{2}},z^{d_{3}},x+y+z)$.

Let $d_{1},d_{2},d_{3}$ be positive integers. If there exists a $q=2^{e}$ such
that $\frac{q}{2}\leq d_{1},d_{2},d_{3}\leq q$ or $d_{1},d_{2}\leq q\leq
d_{3}$, then $\dim_{\mathbb{F}_{2}}(d_{1},d_{2},d_{3}))$ is given by Theorem
1.2 or Corollary 3.2, respectively. Otherwise, it must be that there is some
$q=2^{e}$ such that $\frac{q}{2}<d_{1}\leq q\leq d_{2},d_{3}$. Then Corollary
3.3 allows us to reduce to the case of $d_{1},d_{2}-q$ and $d_{3}-q$. If
$d_{2}-q,d_{3}-q\leq\frac{q}{2}$, we are again in the case of Corollary 3.2;
if $\frac{q}{2}<d_{1},d_{2}-q,d_{3}-q\leq q$, then we are again in the case of
Theorem 1.2. Else we apply Corollary 3.3 again. At every stage we either have
a formula for $\mathbb{F}_{2}[x,y,z]/(x^{d_{1}},y^{d_{2}},z^{d_{3}},x+y+z)$ or
a way to decrease two of the exponents. This process must eventually
terminate, since $d_{1},d_{2},d_{3}$ are positive integers.

Algorithm 1

$d_{1},d_{2},d_{3}\in\mathbb{Z}_{\geq
0}$$\dim_{\mathbb{F}_{2}}[x,y,z]/(x^{d_{1}},y^{d_{2}},(x+y)^{d_{3}})$

1:$\tt{sum}\leftarrow 0$

2:

3:$i\leftarrow\max\\{\lfloor\log_{2}(d_{1})\rfloor,\lfloor\log_{2}(d_{2})\rfloor,\lfloor\log_{2}(d_{3})\rfloor\\}$
$i\geq 0$

4:reorder $d_{1},d_{2},d_{3}$ in non-decreasing order

5:$q\leftarrow 2^{i}$ $d_{1},d_{2},d_{3}<q$

6:do nothing $d_{1},d_{2}<q$ and $q\leq d_{3}$ $\triangleright$ Corollary 3.2

7:$\tt{sum}\leftarrow\tt{sum}+d_{1}d_{2}$

8:break $d_{1}<q$ and $q\leq d_{2},d_{3}$ $\triangleright$ Corollary 3.3

9:$\tt{sum}\leftarrow\tt{sum}+d_{1}q$ $q\leq d_{1},d_{2},d_{3}$
$\triangleright$ Theorem 1.2

10:$\tt{sum}\leftarrow\tt{sum}+d_{1}d_{2}+d_{1}d_{3}+d_{2}d_{3}-(d_{1}+d_{2}+d_{3})q+q^{2}$

11:break

12:$i\leftarrow i-1$

13:

14:return sum

## References

  * [Sta80] Richard P. Stanley  “Weyl groups, the hard Lefschetz theorem, and the Sperner property”  In _SIAM J. Algebraic Discrete Methods_ 1.2, 1980, pp. 168–184  DOI: 10.1137/0601021
  * [RRR91] Les Reid, Leslie G. Roberts and Moshe Roitman  “On complete intersections and their Hilbert functions”  In _Canad. Math. Bull._ 34.4, 1991, pp. 525–535  DOI: 10.4153/CMB-1991-083-9
  * [Han92] Chungsim Han  “The Hilbert-Kunz function of a diagonal hypersurface” Thesis (Ph.D.)–Brandeis University  ProQuest LLC, Ann Arbor, MI, 1992, pp. 59  URL: http://gateway.proquest.com.proxy.lib.umich.edu/openurl?url_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:dissertation&res_dat=xri:pqdiss&rft_dat=xri:pqdiss:9217481
  * [HM93] C. Han and P. Monsky  “Some surprising Hilbert-Kunz functions”  In _Math. Z._ 214.1, 1993, pp. 119–135  DOI: 10.1007/BF02572395
  * [Vra15] Adela Vraciu  “On the degrees of relations on $x_{1}^{d_{1}},\ldots,x_{n}^{d_{n}},(x_{1}+\cdots+x_{n})^{d_{n+1}}$ in positive characteristic”  In _J. Algebra_ 423, 2015, pp. 916–949  DOI: 10.1016/j.jalgebra.2014.11.004
  * [KRV22] Andrew R. Kustin, Rebecca R.. and Adela Vraciu  “The resolution of $(x^{N},y^{N},z^{N},w^{N})$”  In _J. Algebra_ 590, 2022, pp. 338–393  DOI: 10.1016/j.jalgebra.2021.10.009
  * [KRV23] Andrew R. Kustin, Rebecca R.. and Adela Vraciu  “The syzygies of the ideal $(x^{N}_{1},x^{N}_{2},x^{N}_{3},x^{N}_{4})$ in the hypersurface ring defined by $x^{n}_{1}+x^{n}_{2}+x^{n}_{3}+x^{n}_{4}$”  In _J. Algebra_ 615, 2023, pp. 205–242  DOI: 10.1016/j.jalgebra.2022.10.020
  * [GS] Daniel R. Grayson and Michael E. Stillman  “Macaulay2, a software system for research in algebraic geometry”, Available at http://www.math.uiuc.edu/Macaulay2/
  * [LoG] LoG(M)  “Lab of Geometry at Michigan”, https://lsa.umich.edu/math/undergraduates/research-and-career-opportunities/LoGM.html


# Learning to Retrieve Relevant Experiences for Motion Planning

Constantinos Chamzas, Aedan Cullen, Anshumali Shrivastava, Lydia E. Kavraki
All authors are affiliated with the Department of Computer Science, Rice
University, Houston TX, USA {chamzas, aedan, anshumali<EMAIL_ADDRESS>This work was supported in part by NSF 1718478, NSF-GRFP 1842494 and Rice
University Funds.

###### Abstract

Recent work has demonstrated that motion planners’ performance can be
significantly improved by retrieving past experiences from a database.
Typically, the experience database is queried for past similar problems using
a similarity function defined over the motion planning problems. However, to
date, most works rely on simple hand-crafted similarity functions and fail to
generalize outside their corresponding training dataset. To address this
limitation, we propose (fire), a framework that extracts local representations
of planning problems and learns a similarity function over them. To generate
the training data we introduce a novel self-supervised method that identifies
similar and dissimilar pairs of local primitives from past solution paths.
With these pairs, a Siamese network is trained with the contrastive loss and
the similarity function is realized in the network’s latent space. We evaluate
fire on an 8-dof manipulator in five categories of motion planning problems
with sensed environments. Our experiments show that fire retrieves relevant
experiences which can informatively guide sampling-based planners even in
problems outside its training distribution, outperforming other baselines.

##  I Introduction

Motion planning is used in real-time autonomous vehicles [1], manipulators in
dynamic environments [2], and as a subroutine in planners for complex missions
(e.g. task and motion planning [3]), all of which rely heavily on efficiency.
However, motion planning is still challenging, especially for high-dimensional
systems [4]. Sampling-based planners [5, 6, 7] are a class of motion planning
algorithms that have found widespread adoption in the planning community.
Although significant progress has been made over the years, planning is still
computationally expensive [8], hindering the adoption of robotic solutions.
Thus, to endow robots with real-time capabilities, faster motion planning
algorithms are necessary.

Figure 1: Three example problems $M_{0},M_{1},M_{2}$ where the robot is tasked
with picking one object from a shelf starting from the same tuck (home)
configuration (not shown for visual clarity). The motion planning problems
$M_{0}$ and $M_{1}$ have similar solution paths even though their workspaces
are visually different. On the other hand, visually similar workspaces such as
$M_{1}$ and $M_{2}$ can have different solution paths for subtle reasons (e.g.
slightly different goals, obstacle arrangements, and robot base orientation).

A promising avenue is to guide planning by leveraging the past experiences of
a robot. Several methods have shown that storing and retrieving experiences
[9, 10] can significantly improve motion planners’ efficiency. These methods
have focused on what to store and how to adapt/repair it for the current
situation, but not on how to retrieve the most relevant experiences,
defaulting to simple similarity functions. In other words, little emphasis has
been placed on finding suitable functions that quantify the similarity of
motion planning problems, limiting the generalizability of retrieval-based
methods outside their training dataset.

In this context, for similar motion planning problems or subproblems, the
solution path of one can be used to expedite the search when solving the
other. Capturing this notion of similarity is the core investigation of this
work. Designing a good similarity function is very challenging for motion
planning problems. For example, in Fig. 1 two visually dissimilar workspaces
$M_{0}$, $M_{1}$ have similar solution paths while visually similar workspaces
$M_{1}$ and $M_{2}$ have different solution paths. A good similarity function
should capture the commonalities between $M_{0}$ and $M_{1}$ while still
distinguishing between $M_{1}$ and $M_{2}$. These problems are part of the
“Tall-Shelf” dataset described in Sec. V.

To address this problem we propose Fast retrIeval of Relevant Experiences
(fire). As detailed in Sec. IV, fire extracts suitable local representations,
called local primitives, from previous problems. fire finds pairs of similar
and dissimilar local primitives using a self-supervised method. With these
pairs, a similarity function is learned which can be used to retrieve relevant
experiences and guide a motion planner. We demonstrate the effectiveness of
fire with an 8-dof mobile manipulator in five categories of diverse problems
with sensed environments as shown (Fig. 1). Through our experiments (Sec. V)
we show that fire generalizes better outside its training dataset even with
less data, and is faster in terms of planning time than prior work. The
implementation of fire and the generated datasets are open-source
111https://github.com/KavrakiLab/pyre.

Overall, the main contributions of this work lie in 1) defining suitable local
representations of motion planning problems, 2) learning a similarity function
over them, and 3) applying it in the motion planning problem through our new
framework. Although fire is tailored to retrieval frameworks that use local
features and biased sampling distributions [11, 12] we believe it could be
easily adapted to work with other retrieval-based methods [13, 14, 15].

##  II Problem Description and Notation

Feasible Path Planning: Consider a robot in a workspace $\mathcal{W}$. A
configuration of the robot $x$ is a point in the configuration space
($\mathcal{C}$-space), $x\in\mathcal{C}$. Obstacles in the workspace induce
$\mathcal{C}$-space obstacles $X_{\text{obs}}\subset\mathcal{C}$. The set of
configurations that are not in collision is denoted by
$X_{\text{free}}=\mathcal{C}-X_{\text{obs}}$. We are interested in finding a
path $p$, from $x_{\textsc{start}}\in X_{\text{free}}$ to
$x_{\textsc{goal}}\in X_{\text{free}}$, as a continuous map with
$p(0)=x_{\textsc{start}},~{}p(1)=x_{\textsc{goal}}$ such that for all
$t\in[0,1]$, $p(t)\in X_{\text{free}}$. We denote the motion planning problem
by $\mathcal{M}=(x_{\textsc{start}},x_{\textsc{goal}},\mathcal{W})$.

“Challenging Regions” and “Critical Samples”: In this work, we are concerned
with planning for high-dimensional robotic manipulators, and focus on
sampling-based motion planners. A common theme in learning-based approaches is
to produce configurations in $\mathcal{C}$-space regions with low visibility
[16], which are the main bottleneck for sampling-based motion planners [17].
We denote these “challenging regions”, and configurations inside them
“critical samples.”

Retrieval-Based Learning for Motion Planning: Given a dataset
$\mathcal{DS}=\\{\mathcal{M}^{i}:p^{i}\\}^{N}_{i=1}$ of past problems
$\mathcal{M}$ and their feasible paths $p$, retrieval-based methods extract
information from $\mathcal{DS}$ and store it in a database denoted
$\mathcal{DB}$. In this context, $\mathcal{DB}$ is a structure that contains
$\langle key:value\rangle$ entries, with the experiences (values) being
“critical samples.” The indices (keys) of the database are local primitives
denoted by $\ell\in\mathcal{L}$, where $\mathcal{L}$ is the space of local
primitives. Each local primitive includes local workspace information [12]
along with $x_{\textsc{start}}$, $x_{\textsc{goal}}$ information (as defined
in Sec. IV-A). This work aims to learn a suitable similarity function
$\textsc{sim}:\mathcal{L}\times\mathcal{L}\rightarrow\\{0,1\\}$ over the local
primitives in order to retrieve relevant “critical samples” for a given
problem $\mathcal{M}$.

##  III Related work

Over the years many techniques have been proposed to guide sampling-based
motion planners. Many examples use heuristics to bias sampling, such as Bridge
sampling [17], Gaussian sampling [18], Medial-Axis sampling [19], and
workspace-based sampling [20]. However, these predefined heuristics may or may
not apply in different situations.

Thus, a growing number of works attempt to learn how to guide planning by
utilizing past solutions to motion planning problems. One set of methods
learns interesting regions in $\mathcal{W}$ [21, 22] but requires an inverse
kinematics solver to infer samples in “challenging regions”. A similar class
of methods directly computes relevant configurations in $\mathcal{C}$ from a
motion planning problem $\mathcal{M}$ using a neural network. For example,
some methods train a conditional variational autoencoder to reconstruct
samples from previous paths [23] or “challenging regions” [24, 25, 26]. The
authors of [27, 28] use a 3d CNN to sample in “challenging regions”, while
[29, 30, 31] use neural networks as motion planners.

Although these methods have shown some promising results, mapping
$\mathcal{M}$ to paths or “challenging regions” in $\mathcal{C}$ is hard in
high-dimensional problems. Motion planning is sensitive to input; small
changes in $\mathcal{W}$, $x_{\textsc{start}}$, or $x_{\textsc{goal}}$ can
drastically alter the resulting solution [14, 12, 32]. Furthermore, this
mapping is usually multi-modal, since a motion planning problem may have
multiple solution paths or multiple disjoint “challenging regions” [15, 33].

For these reasons, some approaches have adopted retrieval-based methods, also
known as library- [34] or memory-based [35] methods. Such methods typically
store in memory a database $\mathcal{DB}$ and retrieve relevant information in
the form of paths [36, 37] or sampling distributions [11, 38] based on a
similarity function over $\mathcal{M}$. These methods naturally apply to
multi-modal problems, since for similar or identical $\mathcal{M}$ multiple
outputs can be retrieved. Another advantage of these methods is that they are
incremental since new experiences can simply be added to the database
$\mathcal{DB}$. The main challenge lies in constructing a good similarity
function over $\mathcal{M}$.

Defining a similarity function is challenging because $\mathcal{M}$ contains
heterogeneous parameters; $x_{\textsc{start}},x_{\textsc{goal}}\in\mathcal{C}$
while $\mathcal{W}$ is a 3D representation. Some approaches do not use a
similarity function but learn problem invariants [39, 40], others construct
the similarity only over $x_{\textsc{start}}$ and $x_{\textsc{goal}}$ [10,
36], and some construct it only over $\mathcal{W}$ [13, 12]. In [12] a hand-
crafted similarity function over local workspaces is defined, while [13]
defines workspace similarity based on geometric deformation of obstacles. Most
similarly to our work, [9] learned a similarity function over
$x_{\textsc{start}}$, $x_{\textsc{goal}}$, and $\mathcal{W}$ using a weighted
combination of global workspace features. In contrast, our work uses local
features and leverages latent space representations obtained from neural
networks.

Learning similarity functions [41] in the latent space has been successfully
employed in computer-vision tasks, such as image classification [42] and 3D
object classification [43]. Our work is inspired by these methods, and applies
similar metric learning methods to the motion planning problem.

##  IV Methodology

Figure 2:  a) The blue dots depict the 10 projections defined on the arm and
gripper of the Fetch robot. Each blue dot is one projection point
$\pi(x)_{p}\in\mathbb{R}^{3}$ of $x\in\mathcal{C}$. Specifically, each robotic
link of the arm+gripper was used as a projection, as described in its urdf. b)
Examples of local occupancy grids and their position in space derived from the
sensed scene ($lw=(b,v$)). Note that only non-empty local occupancy grids are
generated.

We propose fire, a framework that learns a similarity function to retrieve
relevant experiences from a database in the form of “critical samples”. In
Sec. IV-A we formulate the local primitives which are the input to the
similarity function, and we extract them from past problems in Sec. IV-B.
Then, we describe how to generate similar and dissimilar local primitives
(Sec. IV-C). In Sec. IV-D, we train a Siamese network by minimizing the
contrastive loss of the local primitive pairs and realize the similarity
function in the learned latent space. Finally, Sec. IV-E explains how the
similarity function can guide a sampling-based planner.

###  IV-A Local primitives

First, we define a set of projections
${\pi}(x):\mathcal{C}\rightarrow\mathbb{R}^{3}$ used to extract and compare
local primitives. Each configuration $x$ is projected to multiple points in
$\mathcal{W}$ and stacked as a vector

${\Pi}(x)=[{\pi}_{1}(x),{\pi}_{2}(x),\ldots,{\pi}_{P}(x)]\in\mathbb{R}^{3\times
P}$

where $P$ is the number of projections. Fig. 2a) shows the 10 projections on
the Fetch which we used. Specifically, we used the link frames of the
arm+gripper from the Fetch [44] urdf. Projections have often been used to
guide motion planners [45] and specifying them is often a research problem in
itself, albeit outside the scope of this work.

Now we define the local primitives $\ell$, which include a local 3d occupancy
grid and its position $lw$ [12] along with some auxiliary $\mathcal{C}$-space
information $x_{\textsc{target}}$ and $x_{\textsc{proj}}$:

$\displaystyle\ell=[lw,x_{\textsc{target}},x_{\textsc{proj}}]$

More specifically, $lw=(b,v)$ where $b\in\\{0,1\\}^{64}$ is a 64-bit binary
vector that represents a (4x4x4) local occupancy grid and $v\in\mathbb{R}^{3}$
is the center position of the grid. Examples of $lw$ are shown in Fig. 2b. The
variable $x_{\textsc{target}}\in\mathcal{C}$ is either $x_{\textsc{start}}$ or
$x_{\textsc{goal}}$, depending on the situation as explained in Alg. 1 and
Sec. IV-E. Finally, we calculate $x_{\textsc{proj}}$ from
$x_{\textsc{target}}$ and the center position $v$ of $lw$. We project
$x_{\textsc{target}}$ to $P$ points in the workspace
${\Pi}(x_{\textsc{target}})\in\mathbb{R}^{3\times P}$ and then aggregate all
the distances between the $P$ points and $v$ to calculate $x_{\textsc{proj}}$:

$\displaystyle x_{\textsc{proj}}=[\left\lVert
v-{\pi}_{1}(x_{\textsc{target}})\right\rVert,\ldots,\left\lVert
v-{\pi}_{P}(x_{\textsc{target}})\right\rVert]\in\mathbb{R}^{P}$

The variable $x_{\textsc{proj}}$ serves as an interleaved representation of
$x_{\textsc{target}}$ and $lw$ and was empirically validated to improve the
latent space structure.

###  IV-B Creating the experience database

Alg. 1 describes how to create the experience database $\mathcal{DB}$ from
$\mathcal{DS}=\\{(x_{\textsc{start}},x_{\textsc{goal}},W)^{i}:p^{i}\\}^{N}_{i=1}$
by associating each local primitive with a configuration from a solution path.

First, the paths are shortcutted [46] to remove redundant nodes not in
“challenging regions” (Alg. 1 in Alg. 1) and keep only “critical samples”.
Finding “critical samples” is still an open research problem [24, 22, 12] but
this simple shortcutting heuristic has been used previously in [11, 39].

Next, `TARGET` (Alg. 1 in Alg. 1) samples near $x_{\textsc{start}}$ and
$x_{\textsc{goal}}$ and chooses the one which yielded the most in-collision
samples with the workspace. This aims to create the same local representation
for motion plans with the same solution path but swapped $x_{\textsc{start}}$
and $x_{\textsc{goal}}$. Consider for example the task in Fig. 1, where the
robot plans from the home ($x_{\textsc{start}}$) to a grasp configuration
($x_{\textsc{goal}}$). The same solution path applies for planning between the
grasp configuration ($x_{\textsc{start}}$) back to the tuck configuration
($x_{\textsc{goal}}$). Thus, to ensure that both plans have the same local
representations `TARGET` should choose the same configuration as
$x_{\textsc{target}}$ (e.g. the grasp configuration). We then decompose the
workspace to local occupancy grids (Alg. 1 in Alg. 1) by traversing the
octomap tree similarly to [12].

1

2

Input : MP problem $\mathcal{W},x_{\textsc{start}},x_{\textsc{goal}}$ Path $p$

Output : Database $\mathcal{DB}$

3 Shortcut $p^{\prime}=\textnormal{{SHORTCUT}}(p)$

4 Find target $x_{\textsc{target}}$ $\leftarrow$ TARGET ($x_{\textsc{goal}}$,
$x_{\textsc{start}}$)

5 Decompose $\mathcal{W}$ to
$\mathcal{LW}\leftarrow\\{lw_{1},\ldots,lw_{M}\\}$

6 foreach  _$lw\in\mathcal{LW}$_ do

7 foreach  _$x\in p^{\prime}$_ do

8 foreach  _${\pi}\in{\Pi}$_ do

9 if  _CONTAINS ($lw$, ${\pi}(x)$)_ then

10 $x_{\textsc{proj}}\leftarrow|\tilde{v}-{\Pi}(x_{\textsc{target}})|$

11 $\ell\leftarrow[lw,x_{\textsc{target}},x_{\textsc{proj}}]$

12 $x^{n}\leftarrow\textnormal{{NEXT}}(x,p)$

13 $x^{p}\leftarrow\textnormal{{PREV}}(x,p)$

14 Insert $\langle\ell:x^{p},x,x^{n}\rangle$ in $\mathcal{DB}$

return $\mathcal{DB}$

Algorithm 1 Creating the experience database

Afterward, we iterate over the configurations in each path, the local
occupancy grids, and the projections. The subroutine `CONTAINS` associates
each configuration with its relevant regions in the workspace. `CONTAINS`
checks for every projection ${\pi}(x)_{p}\in\mathbb{R}^{3}$ of the
configuration $x$ if it is contained in the bounding box of an occupancy grid;
if so we store the local primitive $\ell$ along with the critical $x$, the
previous waypoint configuration $x^{p}$, and the next waypoint configuration
$x^{n}$ in $\mathcal{DB}$. The previous and next configurations are only used
to help us create similar pairs as described in Alg. 2 and are not part of the
retrieved experience.

###  IV-C Creating a dataset of similar pairs

Alg. 2 describes a novel method to create a dataset of similar pairs of local
primitives over which to learn the similarity function. This is the key
problem investigated in this paper.

Given a database $\mathcal{DB}$, we iterate over all pairs of local primitives
and perform the following checks. First, the subroutine `SAME_PROJ` checks if
the two local primitives were generated by the same projection (Alg. 2 in Alg.
2). Then we check whether the centers $v$ of the local occupancy grids are
close enough in $\mathcal{W}$ (Alg. 2 in Alg. 2) and whether the stored
configurations are also close enough in $\mathcal{C}$-space (Alg. 2 in Alg.
2). The variable $lw_{side}$ is the length of the side of the local occupancy
bounding box $lw$.

Finally (Alg. 2 in Alg. 2) we sample up to N times
$x^{near}_{j}\sim\mathcal{N}(x_{j},\sigma^{2})$ until a configuration
$x^{near}_{j}$ is found which passes the `VALID` check. The `VALID` subroutine
checks if $x^{near}_{j}$ can connect through a collision-free edge (in the
full workspace $\mathcal{W}$ of $\ell_{i}$) with the next $x^{n}_{i}$ and
previous $x^{p}_{i}$ configuration of the local primitive $\ell_{i}$. If such
a configuration is found then we consider $\langle\ell_{i},\ell_{j}\rangle$
similar and add them to $\mathcal{S}$. This procedure aims to discover local
primitives whose “critical samples” are good substitutes for one another by
emulating how “critical samples” are used to bias sampling during planning
(Sec. IV-E). To generate dissimilar pairs we randomly choose local primitives
from $\mathcal{DB}$ and generate an equal number of dissimilar pairs. We
denote the set that includes these dissimilar pairs $\mathcal{NS}$.

1

2

Input : Database $\mathcal{DB}$

Output : Pairs of similar local primitives $\mathcal{S}$

3 foreach  _$\langle\ell_{i}:x^{p}_{i},x^{i},x^{n}_{i}\rangle\in\mathcal{DB}$_
do

4 foreach  _$\langle\ell_{j}:x^{p}_{j},x_{j},x^{n}_{j}\rangle\in\mathcal{DB}$_
do

5 if  _SAME_PROJ(_$\ell_{i},\ell_{j}$_)_ then

6 if  _$\left\lVert v_{j}-v_{j}\right\rVert_{1} <=size_{lw}$_ then

7 if  _$||x_{i}-x_{j}|| <10\sigma^{2}$_ then

8 repeat  _N_ times

9 $x^{near}_{j}\sim\mathcal{N}(x_{j},\sigma^{2})$

10 if  _VALID(_$x^{p}_{i},x^{near}_{j},x^{n}_{i}$_)_ then

11 $\mathcal{S}$ $\leftarrow\langle\ell_{j},\ell_{i}\rangle$

12 break

13

return $\mathcal{S}$

Algorithm 2 Creating a dataset of similar pairs

Note that Alg. 2 needs the “critical samples” extracted from solution paths to
find similar local primitives, and cannot be used as a similarity function
when solving a new motion planning problem where only
$W,x_{\textsc{goal}},x_{\textsc{start}}$ is available.

###  IV-D Learning the similarity function

The learned similarity function is realized in the latent space of a Siamese
network. A Siamese network [47] is comprised of two identical encoder networks
as shown in Fig. 3. Each encoder maps $\ell$ to a latent variable
$z\in\mathbb{R}^{8}$. The overall network is relatively small with around 3500
parameters, and was trained with the contrastive loss [48]:

$\mathcal{L}(\ell_{i},\ell_{j})=\begin{cases}\max(0,d_{m}-\left\lVert
z_{i}-z_{j}\right\rVert^{2})&\text{if
}\langle\ell_{j},\ell_{i}\rangle\in\mathcal{NS}\\\
||z_{i}-z_{j}||^{2}&\text{if
}\langle\ell_{j},\ell_{i}\rangle\in\mathcal{S}\end{cases}$

This loss tries to bring local primitives that belong in $\mathcal{S}$
(similar) as close as possible in the latent space $Z$, while local primitives
that belong in $\mathcal{NS}$ (dissimilar) must have at least a margin
distance $d_{m}=0.5$. After having structured the latent space $Z$ the
similarity function is defined as follows:

$\textsc{sim}(\ell_{i},\ell_{j})=\begin{cases}1&\text{if}\left\lVert
z_{i}-z_{j}\right\rVert^{2}<R\\\ 0&\text{ otherwise}\end{cases}$

where $R=0.2d_{m}$ is the retrieval radius. A lower retrieval radius than the
margin distance $d_{m}$ must be used to avoid retrieving dissimilar pairs.
After structuring the latent space $Z$ all the local primitives in
$\mathcal{DB}$ are projected to $Z$ and added in a K-D tree [49] structure for
fast retrieval. Finding similar local primitives with sim is equivalent [50]
to retrieving all the neighbors within radius $R$ in the latent space $Z$.

Figure 3: The Siamese network architecture used. The activation function for
all the layers was ReLU. Conv3D denotes a 3D convolutional layer, MaxPool
takes the maximum value out of every subgrid, and FC denotes a fully connected
layer. The parameters of each layer are shown in the figure.

###  IV-E Retrieving relevant experiences

When solving a new problem $\mathcal{M}$
=($x_{\textsc{start}}$,$x_{\textsc{goal}}$, $\mathcal{W}$) the new local
primitives are created with the following procedure. First, we extract the
local occupancy grids from $\mathcal{W}$. Then, for each local occupancy grid
$lw$ we generate two local primitives: one with
$x_{\textsc{target}}=x_{\textsc{start}}$ and one with
$x_{\textsc{target}}=x_{\textsc{goal}}$. The value of $x_{\textsc{proj}}$ is
calculated from $x_{\textsc{target}}$ and $\ell$ as explained in Alg. 1. Each
created local primitive is projected to $Z$ and its neighbors within radius
$R$ are retrieved, effectively obtaining their associated “critical samples”
from $\mathcal{DB}$. Finally, similarly to [12], we aggregate all the $K$
“critical samples” and convert them to a Gaussian Mixture Model (gmm):

$P(x|\mathcal{M})=\frac{1}{K}\sum^{K}_{i=0}\mathcal{N}(x_{i},\sigma^{2})$

The gmm can be used to bias the sampling of any sampling-based planner. To
keep the probabilistic completeness guarantees of sampling-based planners we
sample from $P(x|\mathcal{M})$ with probability $0<\lambda<1$ and from a
standard uniform distribution with probability $(1-\lambda)$. If the planner
uses a local expansion strategy like est [6] we simply sample from the
mixtures that are within the local sampling radius.

##  V Experiments

Figure 4: a) An example problem from the “Small-Shelf” dataset. We generate
different problems by uniformly sampling the robot pose, the position of the
obstacles, and the height of the shelf. This is similar to the “Small-Shelf”
used in [12] but the shelf is shorter, making it more challenging due to the
narrow area the robot has to traverse. b) Planning time (including retrieval)
with different underlying planners for 100 test examples from the “Small-
Shelf” dataset. The timeout was set to 180 seconds.

We demonstrate the effectiveness of the learned similarity function on five
generated datasets with MotionBenchMaker [51]. Each dataset contains an 8-dof
(arm+torso) Fetch robot [44] with a workspace represented by an octomap [52],
performing a pick task as shown in Fig. 4a. We consider this a realistic
representation since point clouds can easily be obtained from a simple depth
camera. The five datasets generated were “Small-Shelf” (Fig. 4a), “Tall-Shelf”
(Fig. 5a), “Thin-Shelf” (Fig. 5b), “Table” (Fig. 5c), and “Cage” (Fig. 7a). As
shown in the figures, the starting configuration $x_{\textsc{start}}$ for all
datasets was a home (tuck) position, except for “Table” where
$x_{\textsc{start}}$ is a random configuration under the table. The goal
configuration $x_{\textsc{goal}}$ is an inverse kinematics (IK) solution
placing the end-effector in a grasping pose relative to an object. For the
“Shelf” datasets, one object per shelf is grasped and it is always the one
furthest back. For “Table” and “Cage” the grasped object is shown in the
figures. We generate different motion planning problems similarly to [12] by
uniformly sampling poses for the robot base and scene objects. Note that such
variation generates highly diverse planning problems since even small changes
in the positions of the obstacles relative to the robot drastically affect
$X_{\text{obs}}$ and the resulting $x_{\textsc{goal}}$.

Figure 5: The three datasets used to test the evaluated methods. Different
problems are generated similarly to Fig. 4. a) An example environment from the
“Tall-Shelf” dataset. The “Tall-Shelf” is created by stacking the “Small-
Shelf” three times. b) An example environment from the “Thin-Shelf” dataset.
This is also a bookcase like “Small-Shelf” and “Tall-Shelf”, but the shelves
are shorter and there is a divider, making it a much more challenging problem.
c) An example environment from the “Table” dataset, which includes a table
with several objects and is very different from the other datasets. Figure 6:
Planning time (including retrieval) when testing in the three datasets shown
in Fig. 5. All of the methods are only trained with the “Small-Shelf” dataset.
The timeout was set to 180 seconds.

All evaluated methods produce biased samples in $\mathcal{C}$ which can guide
any sampling-based motion planner. We evaluated these methods within rrt-
connect (rrtc) [53] and bidirectional est (biest) [6], implemented in the Open
Motion Planning Library (ompl) [54]. Additionally, we considered two versions
of each planner: one with default ompl parameters (rrtc-default and biest-
default) and one with a tuned range parameter (rrtc-tuned and biest-tuned)
found by a parameter sweep over a diverse set of problems. In our experiments
we compare fire with the following methods:

  * •

uniform: Default uniform sampling of the $\mathcal{C}$-space.

  * •

mpnet-smp [29]: This is the sampling-biasing version of Motion Planning
Networks. Given a training dataset of 3d point cloud workspaces,
$x_{\textsc{start}}$, $x_{\textsc{goal}}$, and solution paths, mpnet-smp
learns to iteratively produce samples that mimic the solution paths. We
adapted the provided implementation and tuned its hyperparameters to achieve
the best performance for the given problems.

  * •

flame [12]: This framework is similar to fire and also retrieves “critical
samples” from a $\mathcal{DB}$. However, the local primitives are simpler,
including only workspace information ($lw$) and not considering
$x_{\textsc{goal}}$ or $x_{\textsc{start}}$. The similarity function considers
$lw_{i}$ similar to $lw_{j}$ if they have the same position and binary
representation.

  * •

static [39, 40]: These methods generate a static sampling distribution by
extracting key configurations from past trajectories. They do not rely on a
similarity function but instead attempt to capture the problem’s invariants.
We emulate the static sampling idea of these methods by retrieving all the
$\mathcal{C}$-space samples we have stored in $\mathcal{DB}$.

We consider these methods representative of the works discussed in Sec. III,
with mpnet-smp being a non-retrieval method that directly maps $\mathcal{M}$
to $\mathcal{C}$-space samples using a neural network, flame a retrieval-based
method with a hand-crafted similarity function, and static a method that
learns problem invariants.

We evaluate the performance of fire and the generalization of the learned
similarity function when both the training and testing examples come from the
same dataset (Sec. V-A), and also when the testing dataset is increasingly
different from the training dataset (Sec. V-B). Finally, we evaluate fire when
retrieving experiences it was not trained on, and while the $\mathcal{DB}$
includes unrelated experiences (Sec. V-C). For our experiments we used
Robowflex with MoveIt [55, 56] and the ompl benchmarking tools [57]. The
sampling parameters for fire were the same as [12]
($\sigma^{2}=0.2,\lambda=0.5$).

###  V-A Generalizing in similar problems

####  V-A1 Learning (Training)

In this experiment, mpnet-smp, flame, and fire were trained in problems that
come from the “Small-Shelf” dataset. fire and flame were given enough training
examples for their performance to converge in the “Small-Shelf” dataset. By
convergence, we mean that the average planning time did not improve after
doubling the number of experiences in $\mathcal{DB}$. Specifically, fire was
trained with a total of 500 training examples. From these 500 examples, 200
were used to learn the similarity function and all of the 500 examples were
added to $\mathcal{DB}$. Training the Siamese network of fire took around 1
hour for 200 epochs. flame was trained with 1000 examples which were added to
$\mathcal{DB}$ as described in [12]. Since it was difficult to profile the
convergence of mpnet-smp ($\approx$1 day of training time) we provided it 5000
training examples to ensure that it has enough data. This is of a similar
order to [29] (10000).

####  V-A2 Evaluation (Testing)

The methods were tested in a different set of 100 problems that also come from
“Small-Shelf”. As seen in Fig. 4b, fire outperformed all other methods in all
four different settings in terms of planning time. We do include the retrieval
time in the total planning time for flame and fire but it was negligible in
all cases ($0.01-0.1$ seconds). We also notice that the tuning of the
underlying planner and the use of experiences interact synergistically, with
the best performance being achieved by fire with rrtc-tuned.

###  V-B Generalizing in increasingly different problems

####  V-B1 Learning (Training)

We do not perform any additional training in these experiments and simply use
the methods trained on “Small-Shelf” from Sec. V-A.

####  V-B2 Evaluation (Testing)

In these experiments, the methods were tested on three datasets that are
increasingly different from “Small-Shelf” as shown in Fig. 5. The “Tall-Shelf”
is created by stacking the “Small-Shelf” three times. The “Thin-Shelf” is also
a bookcase but is different from “Tall-Shelf” and “Small-Shelf” because there
is a divider and the distance between the shelves has changed. Finally,
“Table” is significantly different from “Small-Shelf” regarding $\mathcal{W}$.
We used 100 testing examples for each of these three datasets. As shown in
Fig. 6, mpnet-smp could not outperform uniform in “Tall-Shelf” and “Table”
except for rrtc-default, while in “Thin-Shelf” it was not able to improve upon
uniform given the time limits. In some cases mpnet-smp performed worse than
uniform; we attribute this behavior to the testing examples being outside the
training dataset of mpnet-smp. flame did offer some improvement for the “Tall-
Shelf” environment but could not transfer to “Thin-Shelf” or “Table”. Also, in
some cases flame performed worse than uniform; this is attributed to the
retrieval of very few critical samples leading to poor biased sampling (if
nothing is retrieved it defaults to uniform). On the other hand, fire
outperformed all other methods even in “Thin-Shelf” and “Table”, demonstrating
that the learned similarity function generalizes to problems that are
significantly different than those in the training dataset. We also note that
“Table” has a different $x_{\textsc{start}}$ configuration than the training
dataset “Small-Shelf”. This demonstrates the usefulness of independently
considering $x_{\textsc{start}}$ and $x_{\textsc{goal}}$ in the local
primitives defined by fire.

Figure 7:  a) An example problem from the “Cage” dataset. b) Planning time for
100 test examples from the “Cage” dataset using the rrtc-tuned planner. The
timeout was set to 60 seconds. The x-axis shows the number of experiences that
exist in $\mathcal{DB}$ from “Small-Shelf” and from “Cage”. Note that “Small-
Shelf” and “Cage” have very different solution paths. In other words, the
experiences from “Small-Shelf” do not transfer to “Cage”.

###  V-C Robustness to irrelevant experiences

####  V-C1 Learning (Training)

In this experiment, we do not retrain fire’s similarity function and use the
one obtained from training on “Small-Shelf” from Sec. V-A. However, now we add
to $\mathcal{DB}$ example problems from both “Cage” and “Small-Shelf”. Note
that the problems from “Cage” and “Small-Shelf” are highly dissimilar in terms
of solution paths. Thus, when solving a problem from “Cage” a good similarity
function should not retrieve experiences generated from “Small-Shelf”. The
x-axis in Fig. 7b shows the ratio of example problems from “Cage” and “Small-
Shelf”. For example, $500/0$ denotes an experience database $\mathcal{DB}$
that has 500 examples from “Cage” and 0 examples from “Small-Shelf”.

####  V-C2 Evaluation (Testing)

In this experiment, we tested on 100 example problems from the “Cage” dataset
using rrtc-tuned as the underlying planner. We compared with static to
illustrate how irrelevant experiences from “Small-Shelf” affect performance.
The results in Fig. 7b show that although static significantly outperforms
uniform, its performance degrades as we add irrelevant experiences in the
training dataset. On the other hand, fire is robust to the irrelevant
experiences from “Small-Shelf” added to $\mathcal{DB}$ since it maintains its
good performance even with the $500/4500$ ratio. fire’s similarity function
was only trained on “Small-Shelf” while $\mathcal{DB}$ includes experiences
from “Cage”. This demonstrates that the learned latent space can successfully
structure local primitives it was not trained on.

##  VI Conclusion

In this work, we have proposed fire, a framework that learns a similarity
function for motion planning problems with sensed environments. Using the
learned similarity function, fire retrieves relevant experiences from a
database in the form of “critical samples” that can informatively guide any
sampling-based motion planner. Through our experiments, we demonstrated the
generalization of fire outside its training dataset. Furthermore, fire can
also learn incrementally without retraining by simply adding experiences in
$\mathcal{DB}$, and can discriminate between relevant and irrelevant
experiences.

In the future, we would like to improve fire by bounding its memory
requirements and treating biased samples differently from uniform samples [22,
24]. Additionally, we would like to investigate how the same ideas apply to
other problems that include motion planning such as task and motion planning
or kinodynamic planning.

## References

  * [1] Y. Kuwata, J. Teo, G. Fiore, S. Karaman, E. Frazzoli, and J. P. How, “Real-time motion planning with applications to autonomous urban driving,” IEEE Trans. on Control Syst. Tech., vol. 17, no. 5, pp. 1105–1118, 2009\.
  * [2] S. Murray, W. Floyd-Jones, Y. Qi, D. J. Sorin, and G. Konidaris, “Robot motion planning on a chip,” in Robotics: Science and Syst., 2016.
  * [3] N. T. Dantam, Z. Kingston, S. Chaudhuri, and L. E. Kavraki, “An incremental constraint-based framework for task and motion planning,” Int. J. of Robotics Research, vol. 37, no. 10, pp. 1134–1151, 2018.
  * [4] J. F. Canny, The Complexity of Robot Motion Planning.  MIT Press, 1988.
  * [5] L. E. Kavraki, P. Švestka, J.-C. Latombe, and M. Overmars, “Probabilistic roadmaps for path planning in high-dimensional configuration spaces,” IEEE Trans. Robot. Autom., vol. 12, no. 4, pp. 566–580, 1996.
  * [6] D. Hsu, J.-C. Latombe, and R. Motwani, “Path planning in expansive configuration spaces,” Int. J. of Computational Geometry and Applications, vol. 9, no. 4n5, pp. 495–512, 1999.
  * [7] S. M. LaValle and J. J. Kuffner, “Rapidly-exploring random trees: Progress and prospects,” in Algorithmic and Computational Robotics: New Directions, pp. 293–308, 2000.
  * [8] O. Salzman, “Sampling-based robot motion planning,” Communications of the ACM, vol. 62, no. 10, pp. 54–63, 2019.
  * [9] N. Jetchev and M. Toussaint, “Fast motion planning from experience: trajectory prediction for speeding up movement generation,” IEEE J. Robot. Autom., vol. 34, no. 2, pp. 111–127, 2013.
  * [10] D. Coleman, I. A. Sucan, M. Moll, K. Okada, and N. Correll, “Experience-based planning with sparse roadmap spanners,” in IEEE Int. Conf. Robot. Autom., pp. 900–905, 2015.
  * [11] C. Chamzas, A. Shrivastava, and L. E. Kavraki, “Using local experiences for global motion planning,” in IEEE Int. Conf. Robot. Autom., pp. 8606–8612, May 2019.
  * [12] C. Chamzas, Z. Kingston, C. Quintero-Peña, A. Shrivastava, and L. E. Kavraki, “Learning Sampling Distributions Using Local 3D Workspace Decompositions for Motion Planning in High Dimensions,” in IEEE Int. Conf. Robot. Autom., June 2021.
  * [13] J.-M. Lien and Y. Lu, “Planning motion in environments with similar obstacles,” Robotics: Science and Syst., 2009.
  * [14] G. Tang and K. Hauser, “Discontinuity-sensitive optimal control learning by mixture of experts,” in IEEE Int. Conf. Robot. Autom., pp. 7892–7898, 2019.
  * [15] W. Merkt, V. Ivan, T. Dinev, I. Havoutis, and S. Vijayakumar, “Memory clustering using persistent homology for multimodality-and discontinuity-sensitive learning of optimal control warm-starts,” IEEE Trans. Robot., 2020.
  * [16] D. Hsu, T. Jiang, J. Reif, and Z. Sun, “The bridge test for sampling narrow passages with probabilistic roadmap planners,” IEEE Int. Conf. Robot. Autom., vol. 3, pp. 4420–4426, 2003.
  * [17] D. Hsu, J.-C. Latombe, and H. Kurniawati, “On the probabilistic foundations of probabilistic roadmap planning,” Int. J. of Robotics Research, vol. 25, no. 7, pp. 627–643, 2006.
  * [18] V. Boor, M. H. Overmars, and a. V. D. Stappen, “The gaussian sampling strategy for probabilistic roadmap planners,” in IEEE Int. Conf. Robot. Autom., vol. 2, pp. 1018–1023, May 1999.
  * [19] J.-M. Lien, S. L. Thomas, and N. M. Amato, “A general framework for sampling on the medial axis of the free space,” in IEEE Int. Conf. Robot. Autom., vol. 3, pp. 4439–4444, 2003.
  * [20] H. Kurniawati and D. Hsu, “Workspace-based connectivity oracle: An adaptive sampling strategy for prm planning,” in Int. Wksp. on the Algorithmic Foundations of Robotics, pp. 35–51, Springer, 2008.
  * [21] M. Zucker, J. Kuffner, and J. A. Bagnell, “Adaptive workspace biasing for sampling-based planners,” IEEE Int. Conf. Robot. Autom., pp. 3757–3762, 2008.
  * [22] D. Molina, K. Kumar, and S. Srivastava, “Learn and link: Learning critical regions for efficient planning,” in IEEE Int. Conf. Robot. Autom., pp. 10605–10611, 2020.
  * [23] B. Ichter, J. Harrison, and M. Pavone, “Learning sampling distributions for robot motion planning,” in IEEE Int. Conf. Robot. Autom., pp. 7087–7094, May 2018.
  * [24] B. Ichter, E. Schmerling, T.-W. E. Lee, and A. Faust, “Learned critical probabilistic roadmaps for robotic motion planning,” in IEEE Int. Conf. Robot. Autom., pp. 9535–9541, 2020.
  * [25] R. Kumar, A. Mandalika, S. Choudhury, and S. S. Srinivasa, “LEGO: Leveraging experience in roadmap generation for sampling-based planning,” IEEE/RSJ Int. Conf. on Intell. Robots and Syst., 2019.
  * [26] R. K. Jenamani, R. Kumar, P. Mall, and K. Kedia, “Robotic motion planning using learned critical sources and local sampling,” arXiv preprint arXiv:2006.04194, 2020.
  * [27] I. Patil, B. K. Rout, and V. Kalaichelvi, “Prediction of bottleneck points for manipulation planning in cluttered environment using a 3d convolutional neural network,” 2019 7th International Conference on Control, Mechatronics and Automation (ICCMA), pp. 358–364, 2019.
  * [28] R. Terasawa, Y. Ariki, T. Narihira, T. Tsuboi, and K. Nagasaka, “3d-cnn based heuristic guided task-space planner for faster motion planning,” in IEEE Int. Conf. Robot. Autom., pp. 9548–9554, IEEE, 2020.
  * [29] A. H. Qureshi, Y. Miao, A. Simeonov, and M. C. Yip, “Motion planning networks: Bridging the gap between learning-based and classical motion planners,” IEEE Trans. Robot., 2020.
  * [30] T. Jurgenson and A. Tamar, “Harnessing reinforcement learning for neural motion planning,” in Robotics: Science and Syst., 2019.
  * [31] B. Chen, B. Dai, Q. Lin, G. Ye, H. Liu, and L. Song, “Learning to plan in high dimensions via neural exploration-exploitation trees,” in Int. Conf. on Learn. Repr., 2020.
  * [32] M. Farber, “Topological complexity of motion planning,” Discrete and Computational Geometry, vol. 29, no. 2, pp. 211–221, 2003.
  * [33] J. J. Rice and J. Schimmels, “Multi-homotopy class optimal path planning for manipulation with one degree of redundancy,” Mechanism and Machine Theory, vol. 149, p. 103834, 2020.
  * [34] M. Stolle, H. Tappeiner, J. Chestnutt, and C. G. Atkeson, “Transfer of policies based on trajectory libraries,” in IEEE/RSJ Int. Conf. on Intell. Robots and Syst., pp. 2981–2986, IEEE, 2007.
  * [35] T. S. Lembono, A. Paolillo, E. Pignat, and S. Calinon, “Memory of motion for warm-starting trajectory optimization,” IEEE Robot. Autom. Letters, vol. 5, no. 2, pp. 2594–2601, 2020.
  * [36] D. Berenson, P. Abbeel, and K. Goldberg, “A robot path planning framework that learns from experience,” in IEEE Int. Conf. Robot. Autom., pp. 3671–3678, 2012.
  * [37] È. Pairet, C. Chamzas, Y. R. Petillot, and L. E. Kavraki, “Path planning for manipulation using experience-driven random trees,” IEEE Robot. Autom. Letters, vol. 6, p. 3295–3302, Apr. 2021.
  * [38] S. Finney, L. P. Kaelbling, and T. Lozano-Pérez, “Predicting Partial Paths from Planning Problem Parameters,” in Robotics: Science and Syst., 2007.
  * [39] T. F. Iversen and L.-P. Ellekilde, “Kernel density estimation based self-learning sampling strategy for motion planning of repetitive tasks,” in IEEE/RSJ Int. Conf. on Intell. Robots and Syst., pp. 1380–1387, IEEE, 2016.
  * [40] P. Lehner and A. Albu-Schaeffer, “Repetition sampling for efficiently planning similar constrained manipulation tasks,” IEEE/RSJ Int. Conf. on Intell. Robots and Syst., pp. 2851–2856, 2017.
  * [41] E. Hoffer and N. Ailon, “Deep metric learning using triplet network,” in International workshop on similarity-based pattern recognition, pp. 84–92, Springer, 2015.
  * [42] O. Vinyals, C. Blundell, T. Lillicrap, K. Kavukcuoglu, and D. Wierstra, “Matching networks for one shot learning,” in Proceedings of the 30th International Conference on Neural Information Processing Systems, pp. 3637–3645, 2016.
  * [43] A. Zeng, S. Song, M. Nießner, M. Fisher, J. Xiao, and T. Funkhouser, “3DMatch: Learning local geometric descriptors from rgb-d reconstructions,” in CVPR, 2017.
  * [44] M. Wise, M. Ferguson, D. King, E. Diehr, and D. Dymesich, “Fetch and Freight: Standard platforms for service robot applications,” in Wksp. on Autom. Mobile Service Robots, 2016.
  * [45] A. Orthey, A. Escande, and E. Yoshida, “Quotient-space motion planning,” in IEEE/RSJ Int. Conf. on Intell. Robots and Syst., pp. 8089–8096, IEEE, 2018.
  * [46] B. Raveh, A. Enosh, and D. Halperin, “A little more, a lot better: Improving path quality by a path-merging algorithm,” IEEE Trans. Robot., vol. 27, no. 2, pp. 365–371, 2011.
  * [47] D. Chicco, “Siamese neural networks: An overview,” Artificial Neural Networks, pp. 73–94, 2020.
  * [48] R. Hadsell, S. Chopra, and Y. LeCun, “Dimensionality reduction by learning an invariant mapping,” in IEEE Computer Society Conf. on Computer Vision and Pattern Recognition, vol. 2, pp. 1735–1742, 2006.
  * [49] J. L. Bentley, “Multidimensional binary search trees used for associative searching,” Communications of the ACM, vol. 18, no. 9, pp. 509–517, 1975\.
  * [50] M.-F. Balcan, A. Blum, and N. Srebro, “A theory of learning with similarity functions,” Machine Learning, vol. 72, no. 1-2, pp. 89–112, 2008.
  * [51] C. Chamzas, C. Quintero-Peña, Z. Kingston, A. Orthey, D. Rakita, M. Gleicher, M. Toussaint, and L. E. Kavraki, “MotionBenchMaker: A Tool to Generate and Benchmark Motion Planning Datasets,” IEEE Robot. Autom. Letters, vol. 7, p. 882–889, Apr. 2022.
  * [52] A. Hornung, K. M. Wurm, M. Bennewitz, C. Stachniss, and W. Burgard, “OctoMap: An efficient probabilistic 3D mapping framework based on octrees,” Autonomous Robots, vol. 34, no. 3, pp. 189–206, 2013.
  * [53] J. J. Kuffner and S. M. LaValle, “RRT-Connect: An efficient approach to single-query path planning,” in IEEE Int. Conf. Robot. Autom., vol. 2, pp. 995–1001, 2000.
  * [54] I. A. Şucan, M. Moll, and L. E. Kavraki, “The Open Motion Planning Library,” IEEE Robot. Autom. Magazine, vol. 19, no. 4, pp. 72–82, 2012\.
  * [55] S. Chitta, I. Sucan, and S. Cousins, “Moveit!,” IEEE Robot. Autom. Magazine, vol. 19, no. 1, pp. 18–19, 2012.
  * [56] Z. Kingston and L. E. Kavraki, “Robowflex: Robot motion planning with moveit made easy,” arXiv preprint arXiv:2103.12826, 2021.
  * [57] M. Moll, I. A. Şucan, and L. E. Kavraki, “Benchmarking motion planning algorithms: An extensible infrastructure for analysis and visualization,” IEEE Robot. Autom. Magazine, vol. 22, no. 3, pp. 96–102, 2015.