# the relationship between graphs and Nichols braided Lie algebras

Weicai Wu a, Shouchuan Zhang b, Zhengtang Tanc
$a$. School of Mathematics, Hunan Institute of Science and Technology,
Yueyang 414006, P. R. China.
$b$. Department of Mathematics, Hunan University,
Changsha 410082, P.R. China.
c. School of Engineering and Design, Hunan Normal University,
Changsha $410081$, P.R. China.
Emails<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

In this paper we give the relationship between the connected components of
pure generalized Dynkin graphs and Nichols braided Lie algebras.

2010 Mathematics Subject Classification: 16W30, 22E60, 05L25
Keywords: Braided vector space, Nichols algebra, Nichols (braided) Lie
algebra, Graph.

##  1 Introduction

Nichols algebras have found significant applications in various areas of
mathematics and mathematical physics including the theories of pointed Hopf
algebras and logarithmic quantum fields. In [He05], one-to-one correspondences
between Nichols algebras of diagonal type and arithmetic root systems as well
as between generalized Dynkin diagrams and twisted equivalence classes of
arithmetic root systems were established. The problem of finite-dimensionality
of Nichols algebras forms a substantial part of the recent investigations (see
e.g. [AHS08, AS10, He05, He06a, He06b, WZZ15a, WZZ15b]. Lie algebra arising
from a Nichols algebra was studied in [AAB16].

Braided Lie algebras were studied in [Ka77, BMZP92, Gu86, GRR95, Kh99, Pa98,
Sc79, BFM96, ZZ03]. The current paper will focus on Nichols Lie and braided
Lie algebras. In [He05] and [He06a], a classification on braided vector spaces
of diagonal type with finite-dimensional Nichols algebras was given. In
[WZZ15b, WZZ16], we studied the relationship between Nichols algebras and
Nichols braided Lie algebras. It was proven that a Nichols algebra is finite-
dimensional if and only if the corresponding Nichols (braided) Lie algebra is
finite-dimensional. In [WWZZ17] we show that a monomial belongs to Nichols
braided Lie algebra $\mathfrak{L}(V)$ of braided vector space $V$ of diagonal
type if and only if that this monomial is connected. This is one of the main
results in this paper, which enables us to obtain the bases of the Nichols
braided Lie algebras of arithmetic root systems and the dimensions of Nichols
braided Lie algebras of finite Cartan type. We give the sufficient and
necessary conditions for $\mathfrak{B}(V)=F\oplus\mathfrak{L}^{-}(V)$ and
$\mathfrak{L}^{-}(V)=\mathfrak{L}(V)$, where $\mathfrak{B}(V)$,
$\mathfrak{L}^{-}(V)$ and $\mathfrak{L}(V)$ denote Nichols algebra, Nichols
Lie algebra and Nichols braided Lie algebra over $V$. We also obtain an
explicit basis of $\mathfrak{L}^{-}(V)$ over quantum linear space $V$ with
$\dim V=2$. This provides a new method for determining when a Nichols algebra
is finite dimensional.

In this paper we give the relationship between the connected components of
pure generalized Dynkin graphs and Nichols braided Lie algebras;

##  Preliminaries

For any matrix $(q_{ij})_{n\times n}$ over $F^{*}$, define a bicharacter
$\chi$ from $\mathbb{Z}^{n}\otimes\mathbb{Z}^{n}$ to $F^{*}$ such that
$\chi(e_{i},e_{j})=q_{ij}$ for $1\leq i,j\leq n$, where
$\\{e_{1},e_{2},\cdots,e_{n}\\}$ is a basis of $\mathbb{Z}^{n}.$ Let $V$ be a
vector space with basis $x_{1},x_{2},\cdots,x_{n}$. Define
$\alpha(e_{i},x_{j})=q_{ij}x_{j}$ and $\delta(x_{j})=e_{j}\otimes x_{j}$ for
$1\leq i,j\leq n$. It is clear that $(V,\alpha,\delta)$ is a Yetter-Drinfeld
module over $\mathbb{Z}^{n}$ and $(V,C)$ is a braided vector space under
braiding $C,$ where $C(x_{i}\otimes x_{j})=q_{ij}x_{j}\otimes x_{i}$ and
$C^{-1}(x_{i}\otimes x_{j})=q_{ji}^{-1}x_{j}\otimes x_{i}.$ In this case, $V$
is called a braided vector space of diagonal type and $(q_{ij})_{n\times n}$
is called a braiding matrix of $V$. Throughout this paper braided vector space
$V$ is of diagonal type with basis $x_{1},x_{2},\cdots,x_{n}$ and
$C(x_{i}\otimes x_{j})=q_{ij}x_{j}\otimes x_{i}$ without special announcement.
Let $\mathfrak{B}(V)$ be the Nichols algebra over the braided vector space
$V$. Define $p_{ij}:=q_{ij}$ for $1\leq i,j\leq n$ and $p_{uv}:=\chi({\rm
deg}(u),{\rm deg}(v))$ for any homogeneous element $u,v\in\mathfrak{B}(V).$
Denote ${\rm ord}(p_{uu})$ the order of $p_{uu}$ with respect to
multiplication. Let $|u|$ denote length of homogeneous element
$u\in\mathfrak{B}(V).$ Let $D=:\\{[u]\mid[u]\hbox{ is a hard super-letter
}\\}$, $\Delta^{+}(\mathfrak{B}(V)):=\\{\deg(u)\mid[u]\in D\\}$,
$\Delta(\mathfrak{B}(V)):=\Delta^{+}(\mathfrak{B}(V))\cup\Delta^{-}(\mathfrak{B}(V))$,
which is called the root system of $V.$ If $\Delta(\mathfrak{B}(V))$ is
finite, then it is called an arithmetic root system. Let $\mathfrak{L}(V)$
denote the braided Lie algebras generated by $V$ in $\mathfrak{B}(V)$ under
Lie operations $[x,y]=yx-p_{yx}xy$, for any homogeneous elements
$x,y\in\mathfrak{B}(V)$. $(\mathfrak{L}(V),[\ ])$ is called Nichols braided
Lie algebra of $V$. Let $\mathfrak{L}^{-}(V)$ denote the Lie algebras
generated by $V$ in $\mathfrak{B}(V)$ under Lie operations $[x,y]^{-}=yx-xy$,
for any homogeneous elements $x,y\in\mathfrak{B}(V)$. $(\mathfrak{L}^{-}(V),[\
]^{-})$ is called Nichols Lie algebra of $V$. The other notations are the same
as in [WZZ15a].

Recall the dual $\mathfrak{B}(V^{*})$ of Nichols algebra $\mathfrak{B}(V)$ of
rank $n$ in [He05, Section 1.3]. Let $y_{i}$ be a dual basis of $x_{i}$.
$\delta(y_{i})=g_{i}^{-1}\otimes y_{i}$, $g_{i}\cdot y_{j}=p_{ij}^{-1}y_{j}$
and $\Delta(y_{i})=g_{i}^{-1}\otimes y_{i}+y_{i}\otimes 1.$ There exists a
bilinear map $<\cdot,\cdot>$:
$(\mathfrak{B}(V^{*})\\#FG)\times\mathfrak{B}(V)$ $\longrightarrow$
$\mathfrak{B}(V)$ such that

$<y_{i},uv>=<y_{i},u>v+g_{i}^{-1}.u<y_{i},v>$ and
$<y_{i},<y_{j},u>>=<y_{i}y_{j},u>$

for any $u,v\in\mathfrak{B}(V)$. Furthermore, for any
$u\in\oplus_{i=1}^{\infty}\mathfrak{B}(V)_{(i)}$, one has $u=0$ if and only if
$<y_{i},u>=0$ for any $1\leq i\leq n.$ We have

$\displaystyle[[u,v],w]=[u,[v,w]]+p_{vw}^{-1}[[u,w],v]+(p_{wv}-p_{vw}^{-1})v\cdot[u,w],$
(1) $\displaystyle[u,v\cdot w]=p_{wu}[uv]\cdot w+v\cdot[uw].$ (2)

We now recall some basic concepts of the graph theory (see [Ha69]). Let
$\Gamma_{1}$ be a non-empty set and $\Gamma_{2}\subseteq\\{\\{u,v\\}\mid
u,v\in\Gamma_{1},\hbox{ with }u\not=v\\}\subseteq 2^{\Gamma_{1}}.$ Then
$\Gamma=(\Gamma_{1},\Gamma_{2})$ is called a graph; $\Gamma_{1}$ is called the
vertex set of $\Gamma$; $\Gamma_{2}$ is called the edge set of $\Gamma$;
Element $\\{u,v\\}\in\Gamma_{2}$ is called an edge, written $a_{u,v}$. If
$G=(G_{1},G_{2})$ is a graph and $G_{1}\subseteq\Gamma_{1}$ and
$G_{2}\subseteq\Gamma_{2}$, then $G$ is called a subgraph of $\Gamma.$ If
$\emptyset\not=H_{1}\subseteq\Gamma_{1}$ and
$H_{2}=\\{a_{u,v}\in\Gamma_{2}\mid u,v\in H_{1}\\}$, then $H=(H_{1},H_{2})$ is
a subgraph, called the subgraph generated by $H_{1}$ in $\Gamma$.

$a_{u_{m}u_{m-1}}\cdots a_{u_{3}u_{2}}a_{u_{2}u_{1}}$ is called a walk from
$u_{1}$ to $u_{m}.$ We can define an equivalent relation on $\Gamma_{1}$ as
follows: for any $u,v\in\Gamma_{1}$, $u$ and $v$ are equivalent if and only if
there exists a walk from $u$ to $v$ or $u=v.$ Every subgraph generated by
every equivalent class of $\Gamma_{1}$ is called a connected component of
$\Gamma.$

Let $\Gamma(V)$ be the generalized Dynkin diagram of $V$ which excludes
$p_{x_{i},x_{i}},\widetilde{p}_{x_{i},x_{i}}$ for $1\leq i\leq n$. This is
called a pure generalized Dynkin graph of $V$, i.e.
$\Gamma(V)_{1}=\\{1,2,\cdots,n\\}$ and $\Gamma(V)_{2}=\\{a_{ij}\mid
p_{ij}p_{ji}\not=1,i\not=j\\}$.

Let $\Gamma_{a}(V)_{1}=\\{1,2,\cdots,n\\}$ and
$\Gamma_{a}(V)_{2}=\\{a_{ij}\mid p_{ij}\not=1,i\not=j\\}$.
$\Gamma_{a}(V)=(\Gamma_{a}(V)_{1},\Gamma_{a}(V)_{2})$ is called the augmented
Dynkin graph of $V$.

Let $u=h_{1}h_{2}\cdots h_{m}$ be a monomial with $h_{j}=x_{i_{j}}$ for $1\leq
i_{1},i_{2},\ldots,i_{m}\leq n,1\leq j\leq m$. ${\rm
deg}(u)=\lambda_{1}e_{1}+\cdots+\lambda_{n}e_{n},$ where ${\rm
deg}(x_{i})=e_{i}.$ Let ${\rm deg}_{x_{i}}(u):=\lambda_{i}$. Let
$\mu(u):=\\{x_{i_{1}},\cdots,x_{i_{m}}\\}$ and $\Gamma(u)$ be a pure
generalized Dynkin subgraph generated by $\mu(u)$. If $\Gamma(u)$ is
connected, then $u$ is called connected (or $\mu(u)$ is called connected).
Otherwise, $u$ is called disconnected (or $\mu(u)$ is called disconnected).

For $u,v\in\mathfrak{B}(V)$, if there exists a non-zero $a\in F$ such that
$u=av$, then we write $u\sim v.$ This is an equivalent relation. If there
exist $x_{i}\in\mu(u)$ and $x_{j}\in\mu(v)$ such that
$\widetilde{p}_{x_{i},x_{j}}\not=1$, then we say that it is connected between
monomial $u$ and monomial $v$, written $u\diamondsuit v$ in short. Otherwise,
we say that it is disconnected between monomial $u$ and monomial $v$.

Remark: When $u\not=0$, $\mu(u)$ is independent of the choice of
$h_{1},h_{2},\cdots,h_{m},$ since $\mathfrak{B}(V)$ is graded and ${\rm
deg}(u)$ is unique. Therefore, the connectivity of $u$ is independent of the
choice of $h_{1},h_{2},\cdots,h_{m}.$ When $u=0$, $\mu(u)$ is dependent on the
choice of $h_{1},h_{2},\cdots,h_{m}.$ For example, ${\rm deg}(V)>1$,
$p_{12}p_{21}=1,$ $p_{11}=-1,$ $u=x_{1}^{2}=x_{1}^{2}x_{2}=0.$ Therefore,
$\mu(u)=\\{x_{1}\\}$ and $u$ is connected. Meantime,
$\mu(u)=\\{x_{1},x_{2}\\}$ and $u$ is disconnected.

Throughout, $\mathbb{Z}=:\\{x\mid x\hbox{ is an integer}\\}.$
$\mathbb{R}=:\\{x\mid x\hbox{ is a real number}\\}$. $\mathbb{N}_{0}=:\\{x\mid
x\in\mathbb{Z},x\geq 0\\}.$ $\mathbb{N}=:\\{x\mid x\in\mathbb{Z},x>0\\}$. $F$
denotes the base field, which is an algebraic closed field with characteristic
zero. $F^{*}=F\backslash\\{0\\}$. $\mathbb{S}_{n}$ denotes symmetric group,
$n\in\mathbb{N}$. For any set $X$, $\mid X\mid$ is the cardinal of $X$. ${{\rm
int}}(a)$ means the biggest integer not greater than $a\in\mathbb{R}$.

##  2 Relationships between pure generalized Dynkin graph $\Gamma(V)$ and
$\mathfrak{L}(V)$

Obviously, every pure generalized Dynkin graph is a graph in terms of the
graph theory (see [Ha69]). Conversely, assume that $\Gamma$ is a graph with
vertex $\\{1,2,\cdots,n\\}$. We define a matrix $(p_{ij})_{n\times n}$ such
that $p_{ij}p_{ji}\neq 1$ (e.g. $p_{ij}=2$ and
$p_{11}=p_{22}=\cdots=p_{nn}=2$) if and only if there exists an edge between
$i$ and $j.$ Let $V$ be the braided vector space with braiding matrix
$(p_{ij})_{n\times n}$. Then $\Gamma$ is a pure generalized Dynkin graph of
$V.$

By [WWZZ17, Corollary 2.5 and 5.2 ] we have

######  Theorem 2.1.

(i) $\Gamma(u)$ is a connected component of $\Gamma(V)$ with a non-zero
monomial $u$ if and only if $\mu(u)$ is a maximal element in $\\{\mu(v)\mid
v\hbox{ is a non-zero monomial in }\mathfrak{L}(V)\\}$ under order
$\subseteq$.

(ii) The following conditions are equivalent.

(a). $\Gamma(V)$ is connected

(b). $x_{n}x_{n-1}\cdots x_{1}\in\mathfrak{L}(V)$.

(c). $x_{1}x_{2}\cdots x_{n}\in\mathfrak{L}(V)$

(d). there exists a non-zero monomial $u\in\mathfrak{L}(V)$ with
$\mid\mu(u)\mid=\dim V$.

##  3 Relationships between augmented Dynkin graph $\Gamma_{a}(V)$ and Nichols
Lie algebra $\mathfrak{L}^{-}(V)$

######  Proposition 3.1.

Assume that $h_{i}\in\\{x_{1},\cdots,x_{n}\\}$ for $1\leq i\leq m$ and
$u=h_{1}h_{2}\cdots h_{m}.$

(i) If it is disconnected between monomial $u$ and monomial $v$ in
$\Gamma_{a}(V)$ (i.e. ${p}_{x_{i},x_{j}}=1$ for any $x_{i}\in\mu(u)$,
$x_{j}\in\mu(v)$ and $i\not=j$), then $[u,v]^{-}=0.$

(ii) If $\Gamma_{a}(u)$ is disconnected in $\Gamma_{a}(V)$ or
$\mid\mu(u)\mid=1$ ), then $\sigma(h_{1},h_{2},\cdots,h_{m})=0$ for any method
$\sigma$ of adding bracket $[\ ]^{-}$ on $h_{1},h_{2},\cdots,h_{m}.$

Proof. (i) $u$ and $v$ are commutative (i.e. $uv=vu$ ) since
$x_{i}x_{j}=x_{j}x_{i}$ for any $x_{i}\in\mu(u)$, $x_{j}\in\mu(v)$.

(ii) We show this by induction on $m$. $[h_{1},h_{2}]^{-}=0$ for $m=2.$ For
$m>2,$ $\sigma(h_{1},h_{2},\cdots,h_{m})$

$=[\sigma_{1}(h_{1}h_{2}\cdots h_{t}),\sigma_{2}(h_{t+1}h_{t+2}\cdots
h_{m})]^{-}$. If both $h_{1}h_{2}\cdots h_{t}$ and $h_{t+1}h_{t+2}\cdots
h_{m}$ are connected in $\Gamma_{a}(V)$, then it is disconnected between
$h_{1}h_{2}\cdots h_{t}$ and $h_{t+1}h_{t+2}\cdots h_{m}$ in $\Gamma_{a}(V)$.
By Part (i), $\sigma(h_{1},h_{2},\cdots,h_{m})=0$. If either $h_{1}h_{2}\cdots
h_{t}$ or $h_{t+1}h_{t+2}\cdots h_{m}$ is disconnected in $\Gamma_{a}(V)$,
then either $\sigma_{1}(h_{1}h_{2}\cdots h_{t})=0$ or
$\sigma_{2}(h_{t+1}h_{t+2}\cdots h_{m})=0$ by inductive hypothesis.

$\Box$

## References

  * [AS10] N. Andruskiewitsch, H.-J. Schneider, On the classification of finite-dimensional pointed Hopf algebras, Ann. Math. 171 (2010), 375-417.
  * [AHS08] N. Andruskiewitsch, I. Heckenberger and H.J. Schneider, The Nichols algebra of a semisimple Yetter-Drinfeld module, Amer. J. Math. 132 (2010), 1493-1547.
  * [AAB16] N. Andruskiewitsch, I Angiono, F. R. Bertone, A finite-dimensional Lie algebra arising from a Nichols algebra of diagonal type (rank 2), arXiv:1603.09387.
  * [BFM96] Y. Bahturin, D. Fishman and S. Montgomery, On the generalized Lie structure of associative algebras, J. Alg. 96 (1996), 27-48.
  * [BFM01] Y. Bahturin, D. Fischman and S. Montgomery, Bicharacter, twistings and Scheunert’s theorem for Hopf algebra, J. Alg. 236 (2001), 246-276.
  * [BMZP92] Y. Bahturin, D. Mikhalev, M. Zaicev and V. Petrogradsky, Infinite dimensional Lie superalgebras, Walter de Gruyter Publ. Berlin, New York, 1992.
  * [GRR95] D. Gurevich, A. Radul and V. Rubtsov, Noncommutative differential geometry related to the Yang-Baxter equation, J. Math. Sci. 77  (1995), 3051-3062.
  * [Gu86] D. I. Gurevich, The Yang-Baxter equation and the generalization of formal Lie theory, Dokl. Akad. Nauk SSSR, 288 (1986), 797-801.
  * [He06a] I. Heckenberger, Classification of arithmetic root systems, Adv. Math. 220 (2009), 59-124.
  * [He06b] I. Heckenberger, The Weyl-Brandt groupoid of a Nichols algebra of diagonal type, Invent. Math. 164 (2006), 175-188.
  * [He05] I. Heckenberger, Nichols algebras of diagonal type and arithmetic root systems, Habilitation, 2005.
  * [Ha69] Frank Harary, Graph Theory, Addison CWesley, USA, 1969
  * [Hu78] Humphreys, James E. Introduction to Lie Algebras and Representation Theory, Second printing, revised. Graduate Texts in Mathematics, 9. Springer-Verlag, New York, 1978.
  * [Ka77] V. G. Kac, Lie Superalgebras, Adv. Math. 26 (1977), 8-96.
  * [Kh99] V. K. Kharchenko, A Quantum analog of the poincar$\acute{e}$-Birkhoff-Witt theorem, Algebra and Logic, 38 (1999), 259-276
  * [LR95] P. Lalconde and A. Ram, Standard Lyndon bases of Lie algebra and enveloping algebras, Trans. AMS 347 (1995), 1821-1830.
  * [Ma94b] S. Majid, Quantum and braided Lie algebras, J. Geom. Phys. 13 (1994), 307-356.
  * [Ma95] S. Majid, Foundations of quantum group, Cambradge University Press, 1995.
  * [Pa98] B. Pareigis, On Lie algebras in the category of Yetter-Drinfeld modules. Appl. Categ. Structures, 6 (1998), 151-175.
  * [Sc79] M. Scheunert, Generalized Lie algebras, J. Math. Phys. 20 (1979), 712-720.
  * [WZZ15a] W. Wu, S. Zhang and Y.-Z. Zhang, Relationship between Nichols braided Lie algebras and Nichols algebras, J. Lie Theory 25 (2015), 45-63.
  * [WZZ15b] W. Wu, S. Zhang and Y.-Z. Zhang, On Nichols (braided) Lie algebras, Int. J. Math. 26 (2015), 1550082.
  * [WZZ16] W. Wu, S. Zhang and Y.-Z. Zhang, Finiteness of Nichols algebras and Nichols (braided) Lie algebras, arXiv:1607.07955.
  * [ZZ03] S. C. Zhang and Y.-Z. Zhang, Braided m-Lie algebras, Lett. Math. Phys. 70 (2004), 155-167.
  * [WWZZ17] Weicai Wu, Jing Wang, Shouchuan Zhang, Yao-Zhong Zhang, Structures of Nichols (braided) Lie algebras of diagonal type, Journal of Lie Theory, 28 (2018), 357-380. Also see arXiv:1704.06810.


Law of Large Numbers for Roots of Finite Free Multiplicative Convolution

Law of Large Numbers for Roots of Finite Free
Multiplicative Convolution of Polynomials

Katsunori FUJIE a and Yuki UEDA b

K. Fujie and Y. Ueda

a) Department of Mathematics, Hokkaido University,
a) North 10 West 8, Kita-Ku, Sapporo, Hokkaido, 060-0810, Japan
<EMAIL_ADDRESS>
b) Department of Mathematics, Hokkaido University of Education,
b) Hokumon-cho 9, Asahikawa, Hokkaido, 070-8621, Japan
<EMAIL_ADDRESS>
Received August 25, 2022, in final form January 09, 2023; Published online
January 14, 2023

We provide the law of large numbers for roots of finite free multiplicative
convolution of polynomials which have only non-negative real roots. Moreover,
we study the empirical root distributions of limit polynomials obtained
through the law of large numbers of finite free multiplicative convolution
when their degree tends to infinity.

finite free probability; finite free multiplicative convolution; law of large
numbers

46L54; 26C10; 60F05

##  1 Introduction

###  1.1 Free probability theory

Denote by $\mathcal{P}$ and $\mathcal{P}_{+}$ the set of all probability
measures on $\mathbb{R}$ and $[0,\infty)$, respectively. Moreover, we define
$\mathcal{P}_{c}$ and $\mathcal{P}_{+,c}$ as the set of all compactly
supported probability measures on $\mathbb{R}$ and $[0,\infty)$, respectively.
The notation $\xrightarrow{w}$ means the weak convergence of sequences of
probability measures.

Voiculescu initiated free probability theory to attack problems related to the
free product of operator algebras. One of the most important notions in this
theory is the free independence of non-commutative random variables. In this
paper, we say free random variables as freely independent non-commutative
random variables for short.

The law of large numbers (LLN) is well-known as a result that a sample average
of independent identically distributed random variables with finite mean
concentrates on the theoretical mean when the sample size is sufficiently
large. As the analogous result on classical probability, the LLN for free
random variables was also established (see [5]). More precisely, for any
$\mu\in\mathcal{P}$ with mean $\alpha$, we have $D_{1/n}\big{(}\mu^{\boxplus
n}\big{)}\xrightarrow{w}\delta_{\alpha}$ as $n\rightarrow\infty$, where (i)
$D_{c}(\nu)$ is the push-forward of a measure $\nu$ by the mapping $x\mapsto
cx$ for $c\in\mathbb{R}$ and (ii) $\mu\boxplus\nu$ is called the free additive
convolution, which is the probability distribution of addition $X+Y$ of free
random variables $X$ and $Y$ distributed as $\mu\in\mathcal{P}$ and
$\nu\in\mathcal{P}$, respectively, in particular $\mu^{\boxplus n}$ is the
$n$-th power of free additive convolution of $\mu$.

The LLN for multiplication of (classically or freely) independent positive
random variables are also considered. In classical probability, it is easy to
formulate and investigate the LLN of multiplication by considering the
exponential mapping of those random variables. However, it is not easy to
consider the LLN for multiplication in free probability since ${\rm
e}^{X+Y}\neq{\rm e}^{X}{\rm e}^{Y}$ for (non-commutative) random variables $X$
and $Y$. In [8], the LLN for multiplication of free bounded positive random
variables was obtained. After that, this LLN was extended to one for
multiplication of free positive random variables (which are not necessary to
be bounded) in [3]. More precisely, the LLN for multiplication of free
positive random variables can be formulated as the convergence of

$\displaystyle\Big{\\{}\big{(}\mu^{\boxtimes
n}\big{)}^{\frac{1}{n}}\Big{\\}}_{n\in\mathbb{N}},$ (1.1)

for $\mu\in\mathcal{P}_{+}$, where (i) $\nu^{\alpha}$ denotes the push forward
of a measure $\nu$ by the mapping $x\mapsto x^{\alpha}$ for
$\alpha\in\mathbb{R}$ and (ii) $\mu\boxtimes\nu$ is called the free
multiplicative convolution, which is the probability distribution of
multiplication $\sqrt{X}Y\sqrt{X}$ of free random variables $X\geq 0$ and $Y$
distributed as $\mu\in\mathcal{P}_{+}$ and $\nu\in\mathcal{P}$, respectively,
in particular $\mu^{\boxtimes n}$ is the $n$-th power of free multiplicative
convolution of $\mu$ (see [10] and [2] for more details). According to [3],
the limit distribution of the sequence (1.1) always exists and is denoted by
$\Phi(\mu)$. For $\mu\neq\delta_{0}$, the measure
$\Phi(\mu)\in\mathcal{P}_{+}$ is characterized by the S-transform (see Section
2.1 for details).

###  1.2 Finite free probability and main result

In [6] and [7], Marcus, Spielman and Srivastava investigated a link between
polynomial convolutions and the sum of random matrices related to free
probability theory. For monic polynomials
$p(x)=\sum_{i=0}^{d}(-1)^{i}p_{i}x^{d-i}$ and
$q(x)=\sum_{i=0}^{d}(-1)^{i}q_{i}x^{d-i}$ of degree $d$, the finite free
additive convolution $p\boxplus_{d}q$ is defined by

$\displaystyle\big{(}p\boxplus_{d}q\big{)}(x):=\sum_{i+j\leq
d}(-1)^{i+j}\frac{(d-i)!(d-j)!}{(d-i-j)!d!}p_{i}q_{j}x^{d-i-j}.$

The finite free additive convolution plays an important role in studying
characteristic polynomials of the sum of (random) matrices. More precisely,
for $d\times d$ real symmetric matrices $A$ and $B$ with characteristic
polynomials $\chi_{A}$ and $\chi_{B}$, respectively,
$\chi_{A}\boxplus_{d}\chi_{B}$ is given by

$\displaystyle\big{(}\chi_{A}\boxplus_{d}\chi_{B}\big{)}(x)=\mathbb{E}_{Q}\det[xI_{d}-A-QBQ^{*}],$

where the expectation is taken over unitary matrices $Q$ distributed uniformly
on the unitary group in dimension $d$. Furthermore, the finite free additive
convolution is very closely related to free additive convolution because it
turned out to be that the empirical root distribution of
$p_{d}\boxplus_{d}q_{d}$ converges weakly to $\mu\boxplus\nu$ when $d$ tends
to infinity, where $\mu,\nu\in\mathcal{P}$ are limit laws of sequences of
empirical root distribution of $p_{d}$ and $q_{d}$, respectively. Moreover,
Marcus [6] obtained the typical limit theorems (LLN, the central limit theorem
and the Poisson’s law of small numbers, etc.) for finite free additive
convolution. According to the evidence above, we can treat finite free
probability as a discrete approximation theory for free probability.

In this paper, we investigate the LLN for finite free multiplicative
convolution. The finite free multiplicative convolution $\boxtimes_{d}$ of
monic polynomials $p(x)=\sum_{i=0}^{d}(-1)^{i}p_{i}x^{d-i}$ and
$q(x)=\sum_{i=0}^{d}(-1)^{i}q_{i}x^{d-i}$ of degree $d$ with non-negative real
roots is defined by

$\displaystyle\big{(}p\boxtimes_{d}q\big{)}(x):=\sum_{i=0}^{d}(-1)^{i}\frac{p_{i}q_{i}}{\binom{d}{i}}x^{d-i}.$

In particular, $p^{\boxtimes_{d}n}$ denotes the $n$-th power of finite free
multiplicative convolution of $p$. We formulate the LLN for roots of finite
free multiplicative convolution of polynomials as the convergence of a
sequence of

$\displaystyle\Big{\\{}\big{(}\lambda_{1}^{(n)}\big{)}^{\frac{1}{n}}\geq\dots\geq\big{(}\lambda_{d}^{(n)}\big{)}^{\frac{1}{n}}\Big{\\}}_{n\in\mathbb{N}},$
(1.2)

where $\lambda_{i}^{(n)}$ is the $i$-th (non-negative) root of
$p^{\boxtimes_{d}n}$ for a monic polynomial $p$ of degree $d$ with non-
negative roots.

We define the notations for later use. For a finite multiset
$\Lambda=\\{\lambda_{1},\dots,\lambda_{d}\\}$ of complex numbers, the $i$-th
elementary symmetric polynomials $e_{i}(\Lambda)$ is denoted by

$\displaystyle e_{i}(\Lambda):=\sum_{J\subset[d],\,|J|=i}\bigg{(}\prod_{j\in
J}\lambda_{j}\bigg{)},\qquad e_{0}(\Lambda):=1,$

where $[d]:=\\{1,2,\dots,d\\}$. In addition, we define

$\displaystyle\widetilde{e}_{i}(\Lambda):=\frac{e_{i}(\Lambda)}{\binom{d}{i}}.$

for each $0\leq i\leq d$.

We then obtain the limit theorem for the sequence (1.2) as follows.

######  Theorem 1.1 (LLN for $\boxtimes_{d}$).

Let $p$ be a monic polynomial of degree $d$ with non-negative real roots
$\Lambda$ and let us set $k=k(p)$ as the number of zeros in $\Lambda$. Then,

$\displaystyle\lim_{n\rightarrow\infty}\big{(}\lambda_{i}^{(n)}\big{)}^{\frac{1}{n}}=\frac{\tilde{e}_{i}(\Lambda)}{\tilde{e}_{i-1}(\Lambda)}$

for $1\leq i\leq d-k$, and
$\lim_{n\rightarrow\infty}\big{(}\lambda_{i}^{(n)}\big{)}^{\frac{1}{n}}=0$ for
$d-k+1\leq i\leq d$.

The paper consists of $4$ sections. In Section 2, we introduce some concepts
and preliminary results on free probability and finite free probability
theories. In Section 3, we study the roots of finite free multiplicative
convolution of polynomials and provide a proof of our main result (Theorem
1.1). In Section 4, we investigate the behavior of the empirical root
distribution of polynomials obtained by the LLN for finite free multiplicative
convolution when their degree tends to infinity. In the last of this section,
we give a conjecture related to a connection between LLNs for $\boxtimes_{d}$
and $\boxtimes$ from evidence obtained by this section.

##  2 Preliminaries

###  2.1 Free multiplicative convolution

In this section, we introduce free multiplicative convolution and its
characterization via the S-transform (see [2] for more details). For a
probability measure $\mu\neq\delta_{0}$ on $[0,\infty)$, we define

$\displaystyle\psi_{\mu}(z):=\int_{0}^{\infty}\frac{tz}{1-tz}\ \mu({\rm
d}t),\qquad z\in\mathbb{C}\setminus[0,\infty).$

It is known that its inverse function $\psi_{\mu}^{-1}$ exists in a
neighborhood of $(\mu(\\{0\\})-1,0)$, and so we define the S-transform of
$\mu$ by

$\displaystyle S_{\mu}(z):=\frac{z+1}{z}\psi_{\mu}^{-1}(z),\qquad
z\in(\mu(\\{0\\})-1,0).$

According to [2], for probability measures $\mu,\nu\neq\delta_{0}$ on
$[0,\infty)$, the free multiplicative convolution $\mu\boxtimes\nu$ is
characterized by

$\displaystyle S_{\mu\boxtimes\nu}(z)=S_{\mu}(z)S_{\nu}(z),$

for all $z$ in the common interval where all three S-transform are defined.
Note that the common interval is not empty since
$\big{(}\mu\boxtimes\nu\big{)}(\\{0\\})=\max\\{\mu(\\{0\\}),\nu(\\{0\\})\\}$
(see [2, Lemma 6.9]).

The LLN for free multiplicative convolution of a probability measure on
$[0,\infty)$ was obtained by Tucci [8] and Haagerup and Möller [3].

######  Proposition 2.1.

Let us consider $\mu\in\mathcal{P}_{+}$. As $n\rightarrow\infty$, the sequence
of $\big{(}\mu^{\boxtimes n}\big{)}^{\frac{1}{n}}$ converges weakly to the
measure $\Phi(\mu)\in\mathcal{P}_{+}$ characterized by

$\displaystyle\Phi(\mu)$
$\displaystyle\left(\left[0,\frac{1}{S_{\mu}(t-1)}\right]\right)=t,\qquad
t\in(\mu(\\{0\\}),1),$ $\displaystyle\Phi(\mu)$
$\displaystyle(\\{0\\})=\mu(\\{0\\}).$

Moreover, the support of the measure $\Phi(\mu)$ is the closure of the
interval

$\displaystyle\left(\left(\int_{0}^{\infty}t^{-1}\mu({\rm
d}t)\right)^{-1},\int_{0}^{\infty}t\,\mu({\rm d}t)\right)\subset[0,\infty].$

######  Example 2.2.

  1. (1)

Let ${\bf MP}$ be the Marchenko–Pastur distribution which is defined by

$\displaystyle\mathbf{MP}({\rm d}t)=\frac{\sqrt{t(4-t)}}{2\pi
t}\mathbf{1}_{(0,4)}(t)\,{\rm d}t.$

Then $\Phi({\bf MP})$ is the uniform distribution ${\bf U}(0,1)$ on the open
interval $(0,1)$ by [9].

  2. (2)

Consider $\mu=\frac{1}{2}(\delta_{0}+\delta_{1})$. Then we have

$\Phi(\mu)=\frac{1}{2}\delta_{0}+\frac{1}{2(1-t)^{2}}\mathbf{1}_{(0,1/2)}(t)\,{\rm
d}t,$

since $S_{\mu}(t)=(2+2t)/(1+2t)$, $t\in(-1/2,0)$ implies that
$\Phi(\mu)([0,t])=2^{-1}(1-t)^{-1}$ for all $1/2<t<1$.

###  2.2 Finite free multiplicative convolution

In this section, we introduce some concepts and preliminary results on finite
free probability that are used in the remainder of this paper; see [1, 6, 7]
for more details.

######  Definition 2.3.

For monic polynomials $p$ and $q$ of degree $d$ which have only non-negative
real roots:

$\displaystyle p(x)=\sum_{i=0}^{d}(-1)^{i}p_{i}x^{d-i},\qquad\text{ and
}\qquad q(x)=\sum_{i=0}^{d}(-1)^{i}q_{i}x^{d-i},$

the finite free multiplicative convolution $p\boxtimes_{d}q$ is defined by

$\displaystyle\big{(}p\boxtimes_{d}q\big{)}(x):=\sum_{i=0}^{d}(-1)^{i}\frac{p_{i}q_{i}}{\binom{d}{i}}x^{d-i}.$

In [7, Theorem 1.5], the finite free multiplicative convolution
$\boxtimes_{d}$ can be realized as a characteristic polynomial of a product of
positive definite matrices. That is, if $\chi_{A}$ and $\chi_{B}$ are
characteristic polynomials of $d\times d$ positive definite matrices $A$ and
$B$, respectively, then

$\displaystyle\big{(}\chi_{A}\boxtimes_{d}\chi_{B}\big{)}(x)=\mathbb{E}_{Q}\det[xI-
AQBQ^{*}],$

where the expectation is taken over unitary matrices $Q$ distributed uniformly
on the unitary group in dimension $d$. Moreover, if $p$ and $q$ have only non-
negative real roots, then so is $p\boxtimes_{d}q$ (see [7, Theorem 1.6]).

There is the following asymptotic relation between finite free multiplicative
convolution and free multiplicative convolution by [1, Theorem 1.4]. Let us
consider $p_{d}$ and $q_{d}$ as real-rooted monic polynomials of degree $d$ in
which $p_{d}$ has only non-negative real roots. Assume the empirical root
distributions of $p_{d}$ and $q_{d}$ converge weakly to
$\mu\in\mathcal{P}_{+,c}$ and $\nu\in\mathcal{P}_{c}$ as $d\rightarrow\infty$,
respectively. Then the empirical root distribution of
$p_{d}\boxtimes_{d}q_{d}$ converges weakly to $\mu\boxtimes\nu$ as
$d\rightarrow\infty$.

##  3 Main result

In this section, we provide the LLN for finite free multiplicative
convolution. First, we calculate the $n$-th power of finite free
multiplicative convolution of polynomials which have only non-negative real
roots. Let $\Lambda^{(n)}$ be the set of roots of $p^{\boxtimes_{d}n}$ for
$n\geq 1$ and a monic polynomial $p$ of degree $d$ with non-negative real
roots. We put $\Lambda:=\Lambda^{(1)}$, for short.

######  Lemma 3.1.

Let $p$ be a monic polynomial of degree $d$ with non-negative real roots
$\Lambda$. Then we have

$\displaystyle\widetilde{e}_{i}\big{(}\Lambda^{(n)}\big{)}=\widetilde{e}_{i}(\Lambda)^{n},\qquad
0\leq i\leq d.$ (3.1)

In particular, the number of zeros in $\Lambda$ is the same as the one in
$\Lambda^{(n)}$.

###### Proof.

Note that

$\displaystyle
p(x)=\sum_{i=0}^{d}(-1)^{i}\binom{d}{i}\widetilde{e}_{i}(\Lambda)x^{d-i},$

then by Definition 2.3

$\displaystyle
p^{\boxtimes_{d}n}(x)=\sum_{i=0}^{d}(-1)^{i}\binom{d}{i}\widetilde{e}_{i}(\Lambda)^{n}x^{d-i}.$

This is equivalent to (3.1). The rest is because the number of zeros in
$\Lambda$ is equal to $k$ if and only if

$\displaystyle e_{d-k}(\Lambda)>0\quad\text{and}\quad e_{d-k+1}(\Lambda)=0,$

where we understand $e_{d+1}(\Lambda)=0$. ∎

Due to the relation (3.1), we obtain the following LLN for roots of finite
free multiplicative convolution of polynomials.

######  Theorem 3.2.

Consider a monic polynomial $p$ of degree $d$ with non-negative real roots
$\Lambda$ and let $k=k(p)$ be the number of zeros in $\Lambda$. Let
$\Lambda^{(n)}:=\big{\\{}\lambda_{1}^{(n)}\geq\lambda_{2}^{(n)}\geq\dots\geq\lambda_{d}^{(n)}\big{\\}}$
be the set of non-negative real roots of $p^{\boxtimes_{d}n}$. Then we get

$\displaystyle\lim_{n\rightarrow\infty}\big{(}\lambda_{i}^{(n)}\big{)}^{\frac{1}{n}}=\frac{\widetilde{e}_{i}(\Lambda)}{\widetilde{e}_{i-1}(\Lambda)},\qquad
1\leq i\leq d-k.$

######  Remark 3.3.

Note that $\lambda_{i}^{(n)}=0$ for $d-k+1\leq i\leq d$ by Lemma 3.1.

###### Proof.

For $1\leq i\leq d-k$, the equation (3.1) implies that

$\displaystyle\frac{\widetilde{e}_{i}\big{(}\Lambda^{(n)}\big{)}}{\widetilde{e}_{i-1}\big{(}\Lambda^{(n)}\big{)}}=\left(\frac{\widetilde{e}_{i}(\Lambda)}{\widetilde{e}_{i-1}(\Lambda)}\right)^{n}.$
(3.2)

For $i=1$, the equation (3.2) implies that

$\displaystyle\frac{\lambda_{1}^{(n)}+\dots+\lambda_{d}^{(n)}}{d}=\widetilde{e}_{1}\big{(}\Lambda^{(n)}\big{)}=\widetilde{e}_{1}(\Lambda)^{n}.$

Since

$\displaystyle\frac{\lambda_{1}^{(n)}}{d}\leq\frac{\lambda_{1}^{(n)}+\dots+\lambda_{d}^{(n)}}{d}\leq\lambda_{1}^{(n)},$

we obtain

$\displaystyle\widetilde{e}_{1}(\Lambda)\leq\big{(}\lambda_{1}^{(n)}\big{)}^{\frac{1}{n}}\leq
d^{\frac{1}{n}}\widetilde{e}_{1}(\Lambda),$

and therefore
$\big{(}\lambda_{1}^{(n)}\big{)}^{\frac{1}{n}}\rightarrow\widetilde{e}_{1}(\Lambda)$
as $n\rightarrow\infty$.

For $2\leq i\leq d-k$, we have

$\displaystyle\frac{e_{i}\big{(}\Lambda^{(n)}\big{)}}{e_{i-1}\big{(}\Lambda^{(n)}\big{)}}$
$\displaystyle=\frac{\sum_{J\subset[d],\ |J|=i}\left(\prod_{j\in
J}\lambda_{j}^{(n)}\right)}{\sum_{J\subset[d],\ |J|=i-1}\left(\prod_{j\in
J}\lambda_{j}^{(n)}\right)}\geq\frac{\sum_{J\subset[d],\
|J|=i}\left(\prod_{j\in
J}\lambda_{j}^{(n)}\right)}{\binom{d}{i-1}\lambda_{1}^{(n)}\lambda_{2}^{(n)}\cdots\lambda_{i-1}^{(n)}}$
$\displaystyle\geq\frac{\lambda_{1}^{(n)}\lambda_{2}^{(n)}\cdots\lambda_{i}^{(n)}}{\binom{d}{i-1}\lambda_{1}^{(n)}\lambda_{2}^{(n)}\cdots\lambda_{i-1}^{(n)}}=\binom{d}{i-1}^{-1}\lambda_{i}^{(n)}.$

Similar to the estimation above, we obtain

$\displaystyle\frac{e_{i}\big{(}\Lambda^{(n)}\big{)}}{e_{i-1}\big{(}\Lambda^{(n)}\big{)}}$
$\displaystyle\leq\frac{\binom{d}{i}\lambda_{1}^{(n)}\lambda_{2}^{(n)}\cdots\lambda_{i}^{(n)}}{\lambda_{1}^{(n)}\lambda_{2}^{(n)}\cdots\lambda_{i-1}^{(n)}}=\binom{d}{i}\lambda_{i}^{(n)}.$

Consequently, we have

$\displaystyle\binom{d}{i}^{-1}\frac{e_{i}\big{(}\Lambda^{(n)}\big{)}}{e_{i-1}\big{(}\Lambda^{(n)}\big{)}}\leq\lambda_{i}^{(n)}\leq\binom{d}{i-1}\frac{e_{i}\big{(}\Lambda^{(n)}\big{)}}{e_{i-1}\big{(}\Lambda^{(n)}\big{)}},$

and therefore

$\displaystyle\binom{d}{{i-1}}^{-1}\left(\frac{\widetilde{e}_{i}(\Lambda)}{\widetilde{e}_{i-1}(\Lambda)}\right)^{n}\leq\lambda_{i}^{(n)}\leq\binom{d}{{i}}\left(\frac{\widetilde{e}_{i}(\Lambda)}{\widetilde{e}_{i-1}(\Lambda)}\right)^{n}$

by using (3.2). Taking the $n$-th root of each value in the above inequality,
we get

$\displaystyle\binom{d}{{i-1}}^{-\frac{1}{n}}\frac{\widetilde{e}_{i}(\Lambda)}{\widetilde{e}_{i-1}(\Lambda)}\leq\big{(}\lambda_{i}^{(n)}\big{)}^{\frac{1}{n}}\leq\binom{d}{{i}}^{\frac{1}{n}}\frac{\widetilde{e}_{i}(\Lambda)}{\widetilde{e}_{i-1}(\Lambda)}.$

Hence, we obtain
$\big{(}\lambda_{i}^{(n)}\big{)}^{\frac{1}{n}}\rightarrow{\widetilde{e}_{i}(\Lambda)}/{\widetilde{e}_{i-1}(\Lambda)}$
as $n\rightarrow\infty$. ∎

For a positive number $\alpha>0$ and a monic polynomial
$p(x)=\prod_{i=1}^{d}(x-\lambda_{i})$ with non-negative real roots, we define

$p^{(\alpha)}(x):=\prod_{i=1}^{d}\big{(}x-\lambda_{i}^{\alpha}\big{)}.$

######  Remark 3.4.

According to Theorem 3.2, if $p$ is a monic polynomial of degree $d$ with non-
negative real roots $\Lambda$ and $k$ is the number of zeros in $\Lambda$,
then

$\displaystyle\lim_{n\rightarrow\infty}\big{(}p^{\boxtimes_{d}n}\big{)}^{\left(\frac{1}{n}\right)}(x)=x^{k}\prod_{i=1}^{d-k}\left(x-\frac{\widetilde{e}_{i}(\Lambda)}{\widetilde{e}_{i-1}(\Lambda)}\right).$

Thus, the LLN for finite free multiplicative convolution of polynomials is
established.

######  Remark 3.5.

Let $p$ be a monic polynomial of degree $d$ with non-negative real roots
$\Lambda=\\{\lambda_{1}\geq\dots\geq\lambda_{d}\\}$, $k$ the number of zeros
in $\Lambda$, and $\lambda_{i}^{(n)}$ the $i$-th real root of
$p^{\boxtimes_{d}n}$ for $1\leq i\leq d$. By Newton’s inequality (see, e.g.,
[4]), we have

$\displaystyle\frac{\widetilde{e}_{i}(\Lambda)}{\widetilde{e}_{i-1}(\Lambda)}\geq\frac{\widetilde{e}_{i+1}(\Lambda)}{\widetilde{e}_{i}(\Lambda)},\qquad
1\leq i\leq d-k-1,$ (3.3)

where the equality holds if and only if $\lambda_{1}=\dots=\lambda_{d}$.
However, the inequality (3.3) can be directly proven by Theorem 3.2 due to
$\lambda_{i}^{(n)}\geq\lambda_{i+1}^{(n)}$.

Consequently, we find the following remarkable phenomenon; except for trivial
cases, the limit roots of
$\big{(}p^{\boxtimes_{d}n}\big{)}^{\left(\frac{1}{n}\right)}$, not being zero,
are all distinct.

In particular, we apply Theorem 3.2 to the (renormalized) Laguerre polynomial
and a polynomial with two real roots.

######  Example 3.6 (case of the Laguerre polynomial).

Consider $d\geq 1$. We define

$\displaystyle p(x):=d!(-d)^{-d}L_{0,d}(dx),$

where $L_{\alpha,d}$ is the Laguerre polynomial which is defined by

$\displaystyle
L_{\alpha,d}(x):=\sum_{i=0}^{d}\frac{(-x)^{i}}{i!}\binom{d+\alpha}{d-i}.$

Let $\Lambda$ be the set of positive real roots of $p$. Note that $p$ has no
zero roots since $p(0)=d!(-d)^{-d}\neq 0$. Computing the polynomial $p$, we
have

$\displaystyle p(x)$
$\displaystyle=d!(-d)^{-d}\sum_{i=0}^{d}\frac{(-dx)^{i}}{i!}\binom{d}{d-i}$
$\displaystyle=x^{d}+\sum_{j=1}^{d}(-1)^{j}\binom{d}{j}\left(\frac{d}{d}\cdot\frac{d-1}{d}\cdots\frac{d-j+1}{d}\right)x^{d-j},$

where the last equality holds by changing variable to $j=d-i$. This implies
that

$\displaystyle\widetilde{e}_{j}(\Lambda)=\frac{d}{d}\cdot\frac{d-1}{d}\cdots\frac{d-j+1}{d},\qquad
1\leq j\leq d.$

Suppose that $\lambda_{1}^{(n)}\geq\dots\geq\lambda_{d}^{(n)}$ are non-
negative real roots of $p^{\boxtimes_{d}n}$. By Theorem 3.2, we obtain

$\displaystyle\lim_{n\rightarrow\infty}\big{(}\lambda_{i}^{(n)}\big{)}^{\frac{1}{n}}$
$\displaystyle=\frac{\widetilde{e}_{i}(\Lambda)}{\widetilde{e}_{i-1}(\Lambda)}=\frac{\frac{d}{d}\cdot\frac{d-1}{d}\cdots\frac{d-i+1}{d}}{\frac{d}{d}\cdot\frac{d-1}{d}\cdots\frac{d-i+2}{d}}=\frac{d-i+1}{d}$

for $1\leq i\leq d$, where note that $\tilde{e}_{0}(\Lambda)=1$.

######  Example 3.7 (case of a polynomial with two roots).

Given $d\geq 1$, consider the following monic polynomial $p$ of $2d$ degree:

$\displaystyle p(x)=x^{d}(x-1)^{d},\qquad d\geq 1,$

and put $\Lambda=\\{\underbrace{1,\dots,1}_{d\text{
times}},\underbrace{0,\dots,0}_{d\text{ times}}\\}$ as the set of roots of
$p$. Then we get

$\displaystyle\widetilde{e}_{j}(\Lambda)=\frac{\binom{d}{j}}{\binom{2d}{j}},\qquad
0\leq j\leq d,$

and $\tilde{e_{j}}(\Lambda)=0$ for $d+1\leq j\leq 2d$. Suppose that
$\lambda_{1}^{(n)}\geq\dots\geq\lambda_{d}^{(n)}$ are positive real roots of
$p^{\boxtimes_{d}n}$. By Theorem 3.2, we have

$\displaystyle\lim_{n\rightarrow\infty}\big{(}\lambda_{i}^{(n)}\big{)}^{\frac{1}{n}}=\frac{d-i+1}{2d-i+1},$

for all $1\leq i\leq d$.

At the end of this section, we mention the rate of convergence in the LLN for
roots of finite free multiplicative convolution of polynomials.

######  Remark 3.8.

According to a proof of Theorem 3.2, it is easy to see that

$\displaystyle\log\big{(}\lambda_{i}^{(n)}\big{)}^{\frac{1}{n}}=\log\left(\frac{\widetilde{e}_{i}(\Lambda)}{\widetilde{e}_{i-1}(\Lambda)}\right)+O\left(\frac{1}{n}\right),$

as $n\rightarrow\infty$.

We demonstrate an example in which the rate of convergence is of order $1/n$
and it is optimal. Consider $d=2$ in Example 3.6, that is,
$p(x)=x^{2}-2x+2^{-1}$. As a consequent result of a proof of Lemma 3.1, we
obtain $p^{\boxtimes_{2}n}(x)=x^{2}-2x+2^{-n}$ for $n\in\mathbb{N}$. Hence
(positive) real roots of $p^{\boxtimes_{2}n}$ are given by

$\lambda_{1}^{(n)}=1+\sqrt{1-2^{-n}},\qquad\lambda_{2}^{(n)}=1-\sqrt{1-2^{-n}}.$

It is easy to see that
$\lim_{n\rightarrow\infty}\big{(}\lambda_{1}^{(n)}\big{)}^{\frac{1}{n}}=1$,
$\lim_{n\rightarrow\infty}\big{(}\lambda_{2}^{(n)}\big{)}^{\frac{1}{n}}=1/2$
and also

$\displaystyle n\left(\log\big{(}\lambda_{1}^{(n)}\big{)}^{\frac{1}{n}}-\log
1\right)\rightarrow\log 2,\qquad
n\left(\log\big{(}\lambda_{2}^{(n)}\big{)}^{\frac{1}{n}}-\log\frac{1}{2}\right)\rightarrow-\log
2,$

as $n\rightarrow\infty$. Consequently, the order $1/n$ is optimal.

##  4 Relation to the LLN for free multiplicative convolution

In this section, given a monic polynomial of degree $d$, we investigate how
the empirical root distributions of their limit polynomial obtained by Theorem
3.2 (or Remark 3.4) converge weakly as $d\rightarrow\infty$. For the reason
above, we emphasize their degree as follows.

Let $p_{d}$ be a monic polynomial of degree $d$ with non-negative real roots
$\Lambda_{d}=\\{\lambda_{1,d}\geq\dots\geq\lambda_{d,d}\\}$ and let $k_{d}$ be
the number of zeros in $\Lambda_{d}$. Denote by $R_{i}(\Lambda_{d})$ the limit
roots of $\big{(}p_{d}^{\boxtimes_{d}n}\big{)}^{\left(\frac{1}{n}\right)}$ as
$n\rightarrow\infty$ for $1\leq i\leq d$, that is,

$R_{i}(\Lambda_{d})=\frac{\tilde{e}_{i}(\Lambda_{d})}{\tilde{e}_{i-1}(\Lambda_{d})},$

as provided in Theorem 3.2. In the following, we investigate relationships
between the empirical root distributions:

$\mu_{d}:=\frac{1}{d}\sum_{i=1}^{d}\delta_{\lambda_{i,d}},\qquad\text{and}\qquad\nu_{d}:=\frac{1}{d}\sum_{i=1}^{d}\delta_{R_{i}(\Lambda_{d})}.$

######  Lemma 4.1.

Let $p_{d}$ be a monic polynomial of degree $d$ with non-negative real roots
$\Lambda_{d}$. Assume that $k_{d}=0$ $($equivalently, $\lambda_{d,d}>0$ or
$R_{d}(\Lambda_{d})>0$$)$. Then we have

$\displaystyle\int_{0}^{\infty}(\log t)\,\mu_{d}({\rm
d}t)=\int_{0}^{\infty}(\log t)\,\nu_{d}({\rm d}t).$

###### Proof.

Note that the integrals $\int_{0}^{\infty}(\log t)\,\mu_{d}({\rm d}t)$ and
$\int_{0}^{\infty}(\log t)\,\nu_{d}({\rm d}t)$ are finite since $k_{d}=0$. A
direct computation shows that

$\displaystyle\int_{0}^{\infty}(\log t)\,\nu_{d}({\rm d}t)$
$\displaystyle=\frac{1}{d}\sum_{i=1}^{d}\log R_{i}(\Lambda_{d})$
$\displaystyle=\frac{1}{d}\sum_{i=1}^{d}\log\frac{\widetilde{e}_{i}(\Lambda_{d})}{\widetilde{e}_{i-1}(\Lambda_{d})}\qquad\text{(by
Theorem \ref{thm:LLN})}$
$\displaystyle=\frac{1}{d}\log\widetilde{e}_{d}(\Lambda_{d})\qquad\text{(since
$\widetilde{e}_{0}(\Lambda_{d})=1$)}$
$\displaystyle=\frac{1}{d}\log\prod_{i=1}^{d}\lambda_{i,d}$
$\displaystyle=\frac{1}{d}\sum_{i=1}^{d}\log\lambda_{i,d}=\int_{0}^{\infty}(\log
t)\,\mu_{d}({\rm d}t).$ ∎

We study how the empirical root distributions
$\nu_{d}=\frac{1}{d}\sum_{i=1}^{d}\delta_{R_{i}(\Lambda_{d})}$ behave as
$d\rightarrow\infty$ when
$\mu_{d}=\frac{1}{d}\sum_{i=1}^{d}\delta_{\lambda_{i,d}}$ converges weakly to
some probability measure on $[0,\infty)$.

######  Proposition 4.2.

Let $p_{d}$ be a monic polynomial of degree $d$ with non-negative real roots
$\Lambda_{d}$. Assume that there exist $\mu\in\mathcal{P}_{+,c}$ and a compact
set $K$ in $[0,\infty)$, such that the measures $\mu_{d}$ and $\mu$ are
supported on $K$ for all $d\geq 1$, and such that $\mu_{d}\xrightarrow{w}\mu$
as $d\rightarrow\infty$. Then we obtain

$R_{1}(\Lambda_{d})\rightarrow\int_{0}^{\infty}t\,\mu({\rm d}t)$

as $d\rightarrow\infty$. In addition, if $0\notin K$, then it satisfies that

$R_{d}(\Lambda_{d})\rightarrow\left(\int_{0}^{\infty}t^{-1}\mu({\rm
d}t)\right)^{-1}\qquad\text{and}\qquad\int_{0}^{\infty}(\log t)\nu_{d}({\rm
d}t)\rightarrow\int_{0}^{\infty}(\log t)\Phi(\mu)({\rm d}t)$

as $d\rightarrow\infty$, where $\Phi(\mu)$ is defined in Proposition 2.1.

###### Proof.

By the assumptions and Theorem 3.2, we get

$\displaystyle
R_{1}(\Lambda_{d})=\widetilde{e}_{1}(\Lambda_{d})=\frac{1}{d}\sum_{i=1}^{d}\lambda_{i,d}=\int_{0}^{\infty}t\,\mu_{d}({\rm
d}t)\rightarrow\int_{0}^{\infty}t\,\mu({\rm d}t)$

as $d\rightarrow\infty$.

Moreover, we assume that $0\notin K$ in the following. Note that the functions
$t\mapsto t^{-1}$ and $t\mapsto\log t$ are bounded and continuous on $K$. We
then obtain

$\displaystyle
R_{d}(\Lambda_{d})=\frac{\widetilde{e}_{d}(\Lambda_{d})}{\widetilde{e}_{d-1}(\Lambda_{d})}=\left(\frac{1}{d}\sum_{i=1}^{d}\lambda_{i,d}^{-1}\right)^{-1}=\left(\int_{0}^{\infty}t^{-1}\mu_{d}({\rm
d}t)\right)^{-1}\rightarrow\left(\int_{0}^{\infty}t^{-1}\mu({\rm
d}t)\right)^{-1}$

as $d\rightarrow\infty$. It follows that $k_{d}=0$ from $0\notin K$. By Lemma
4.1, we obtain

$\displaystyle\int_{0}^{\infty}(\log t)\nu_{d}({\rm
d}t)=\int_{0}^{\infty}(\log t)\mu_{d}({\rm
d}t)\rightarrow\int_{0}^{\infty}(\log t)\mu({\rm d}t).$

According to [3, Proposition 1], the last integral equals to
$\int_{0}^{\infty}(\log t)\Phi(\mu)({\rm d}t)$, and therefore we get the
convergence. ∎

We give examples of the weak limit laws of empirical root distributions
$\frac{1}{d}\sum_{i=1}^{d}\delta_{R_{i}(\Lambda_{d})}$ as
$d\rightarrow\infty$.

######  Example 4.3.

  1. (1)

In Example 3.6, it was shown that $R_{i}(\Lambda_{d})=\frac{d-i+1}{d}$ when we
consider

$p_{d}(x)=d!(-d)^{-d}L_{0,d}(dx)$

with non-negative real roots $\Lambda_{d}$ for each $d\geq 1$. It is easy to
see that

$\displaystyle\frac{1}{d}\sum_{i=1}^{d}\delta_{\frac{d-i+1}{d}}\xrightarrow{w}{\bf
U}(0,1)=\Phi({\bf MP}),$

as $d\rightarrow\infty$, where the last equality holds due to Example 2.2 (1).

  2. (2)

In Example 3.7, we obtained that $R_{i}(\Lambda_{2d})=\frac{d-i+1}{2d-i+1}$
for $1\leq i\leq d$ when $p_{d}(x)=x^{d}(x-1)^{d}$ with non-negative real
roots $\Lambda_{2d}$. For any bounded continuous functions $f$ on
$[0,\infty)$, we get

$\displaystyle\int_{0}^{\infty}f(t)\left[\frac{1}{2}\delta_{0}+\frac{1}{2d}\sum_{i=1}^{d}\delta_{\frac{d-i+1}{2d-i+1}}\right]({\rm
d}t)$
$\displaystyle=\frac{1}{2}f(0)+\frac{1}{2d}\sum_{i=1}^{d}f\left(\frac{d-i+1}{2d-i+1}\right)$
$\displaystyle=\frac{1}{2}f(0)+\frac{1}{2d}\sum_{\ell=1}^{d}f\left(\frac{\ell}{d+\ell}\right)$
$\displaystyle=\frac{1}{2}f(0)+\frac{1}{2d}\sum_{\ell=1}^{d}f\left(\frac{\frac{\ell}{d}}{1+\frac{\ell}{d}}\right)$
$\displaystyle\rightarrow\frac{1}{2}f(0)+\frac{1}{2}\int_{0}^{1}f\left(\frac{t}{1+t}\right){\rm
d}t$
$\displaystyle=\frac{1}{2}f(0)+\frac{1}{2}\int_{0}^{1/2}\frac{f(u)}{(1-u)^{2}}{\rm
d}u,$

where the last equality holds by changing variable to $u=t/(1+t)$, and
therefore

$\frac{1}{2}\delta_{0}+\frac{1}{2d}\sum_{i=1}^{d}\delta_{\frac{d-i+1}{2d-i+1}}\xrightarrow{w}\frac{1}{2}\delta_{0}+\frac{1}{2(1-t)^{2}}\mathbf{1}_{(0,1/2)}(t){\rm
d}t=\Phi\left(\frac{1}{2}(\delta_{0}+\delta_{1})\right),$

as $d\rightarrow\infty$, where the last equality holds due to Example 2.2 (2).

According to Proposition 4.2 and Example 4.3, it is natural to conjecture the
following statement.

######  Conjecture 4.4.

Let $p_{d}$ be a monic polynomial of degree $d$ with non-negative real roots
$\Lambda_{d}=\\{\lambda_{1,d}\geq\dots\geq\lambda_{d,d}\\}$. Let us further
consider $\mu\in\mathcal{P}_{+,c}$. Assume that the empirical root
distributions of $p_{d}$, that is,
$\frac{1}{d}\sum_{i=1}^{d}\delta_{\lambda_{i,d}}$ converge weakly to $\mu$ as
$d\rightarrow\infty$. Then we obtain

$\displaystyle\frac{1}{d}\sum_{i=1}^{d}\delta_{R_{i}(\Lambda_{d})}\xrightarrow{w}\Phi(\mu)$

as $d\rightarrow\infty$.

### Acknowledgements

This work was supported by JSPS Open Partnership Joint Research Projects
JPJSBP120209921 and Bilateral Joint Research Projects (JSPS-MEAE-MESRI,
JPJSBP120203202). Moreover, K.F. was supported by the Hokkaido University
Ambitious Doctoral Fellowship (Information Science and AI). Y.U. was supported
by JSPS Grant-in-Aid for Scientific Research (B) 19H01791 and also JSPS Grant-
in-Aid for Young Scientists 17H04823 and 22K13925. The both authors would like
to thank Nikhil Srivastava (UC Berkeley) for giving us a three-day lecture on
finite free probability theory at Kyoto University. The both authors also
thank Benoît Collins (Kyoto University) and Noriyoshi Sakuma (Nagoya City
University) for introducing the discussion. Thanks to the lectures, the
authors could start to study the LLN for finite free multiplicative
convolution. Furthermore, the authors would also like to thank the referees
who gave useful comments to improve this paper.

## References

  * [1] Arizmendi O., Garza-Vargas J., Perales D., Finite free cumulants: multiplicative convolutions, genus expansion and infinitesimal distributions, arXiv:2108.08489.
  * [2] Bercovici H., Voiculescu D., Free convolution of measures with unbounded support, Indiana Univ. Math. J. 42 (1993), 733–773.
  * [3] Haagerup U., Möller S., The law of large numbers for the free multiplicative convolution, in Operator Algebra and Dynamics,Springer Proc. Math. Stat., Vol. 58, Springer, Heidelberg, 2013, 157–186, arXiv:1211.4457.
  * [4] Hardy G.H., Littlewood J.E., Pólya G., Inequalities, 2nd ed., Cambridge University Press, Cambridge, 1952.
  * [5] Lindsay J.M., Pata V., Some weak laws of large numbers in noncommutative probability, Math. Z. 226 (1997), 533–543.
  * [6] Marcus A.W., Polynomial convolutions and (finite) free probability, arXiv:2108.07054.
  * [7] Marcus A.W., Spielman D.A., Srivastava N., Finite free convolutions of polynomials, Probab. Theory Related Fields 182 (2022), 807–848, arXiv:1504.00350.
  * [8] Tucci G.H., Limits laws for geometric means of free random variables, Indiana Univ. Math. J. 59 (2010), 1–13, arXiv:0802.4226.
  * [9] Ueda Y., Max-convolution semigroups and extreme values in limit theorems for the free multiplicative convolution, Bernoulli 27 (2021), 502–531, arXiv:2003.05382.
  * [10] Voiculescu D., Multiplication of certain noncommuting random variables, J. Operator Theory 18 (1987), 223–235.


# Hypergraph-based Multi-robot Motion Planning with Topological Guidance

Courtney McBeth1, James Motes1, Marco Morales1, and Nancy M. Amato1 1Courtney
McBeth, James Motes, Marco Morales, and Nancy M. Amato are with the Parasol
Lab, Department of Computer Science, University of Illinois Urbana-Champaign,
Champaign, IL 61820 USA {cmcbeth2, jmotes2, moralesa<EMAIL_ADDRESS>
###### Abstract

We present a multi-robot motion planning algorithm that efficiently finds
paths for robot teams up to ten times larger than existing methods in
congested settings with narrow passages in the environment. Narrow passages
represent a source of difficulty for sampling-based motion planning
algorithms. This problem is exacerbated for multi-robot systems where the
planner must also avoid inter-robot collisions within these congested spaces,
requiring coordination. Topological guidance, which leverages information
about the robot’s environment, has been shown to improve performance for
mobile robot motion planning in single robot scenarios with narrow passages.
Additionally, our prior work has explored using topological guidance in multi-
robot settings where a high degree of coordination is required of the full
robot group. This high level of coordination, however, is not always necessary
and results in excessive computational overhead for large groups. Here, we
propose a novel multi-robot motion planning method that leverages topological
guidance to inform the planner when coordination between robots is necessary,
leading to a significant improvement in scalability.

##  I Introduction

Multi-robot systems are becoming increasingly prevalent in constrained
settings like warehouses and factories. Here, it is important to be able to
quickly find collision-free paths for robot teams. These constrained
environments often feature narrow aisles that several robots must maneuver
through. Sampling-based motion planning methods struggle with the narrow
passage problem, referring to the difficulty of exploring tight areas of the
environment. Considering multi-robot systems, this problem is exacerbated by
the need to avoid both obstacle and inter-robot collisions.

Decoupled multi-robot motion planning (MRMP) methods [1] plan for each robot
separately and provide no coordination during planning, making them unsuitable
for overly constrained environments. On the other end of the spectrum, coupled
methods [1] plan for all robots together in the composite space, the joint
planning space of all robots. These methods have full knowledge of each
robot’s configuration at all times and thus do provide the high level of
coordination required to solve these difficult problems. However, the size of
the composite space is exponential in the number of robots, making these
methods computationally intractable for large robot teams.

Hybrid methods [2, 3, 4] provide a mix of decoupled and coupled planning to
provide scalability along with an increased level of coordination during
planning when necessary. Often, these methods start by planning completely
decoupled and then progressively explore more of the composite space as they
resolve conflicts between individual robots. In the worst case, they explore
the full composite space while incurring the computational effort required to
escalate to that level.

Prior work [5, 6, 7, 8] has explored leveraging information about the topology
of the workspace, the environment that the robot physically exists within, to
guide planning through narrow passages. We recently introduced Composite
Dynamic Region-biased RRT (CDR-RRT) [9], a coupled MRMP method that leverages
topological guidance to efficiently plan paths in congested environments with
narrow passages. CDR-RRT provides the high level of coordination required to
resolve complex inter-robot conflicts while its use of topological guidance
limits its exploration of the composite space to areas likely to yield a
solution. While CDR-RRT achieves high coordination by planning in the
composite space, we can further exploit topological guidance to allow us to
achieve this same coordination while searching lower dimensional spaces,
resulting in more efficient planning for large groups of robots.

In this paper, we build off of CDR-RRT while utilizing an existing hybrid
planning framework to propose the Workspace Decomposable State Space
Hypergraph (Workspace-DaSH) method, a novel hybrid MRMP approach that
leverages topological guidance to decompose the motion planning problem. By
considering when robots will be physically near each other in the workspace,
we are able to provide coordination by planning within the composite spaces of
subgroups of robots when necessary. By taking advantage of topological
guidance to limit time spent resolving conflict, we show our method’s ability
to plan for groups of size up to ten times larger than existing methods. Our
contributions include:

  * •

A novel hybrid MRMP method that leverages the workspace to guide planning by
informing when the composite spaces of robots should be considered.

  * •

The development of a novel workspace representation for multi-robot planning,
the hypergraph skeleton structure.

  * •

An extensive experimental validation showing that our approach scales to robot
groups up to ten times larger than previous methods.

##  II Preliminaries and Prior Work

In this section, we describe relevant motion planning preliminaries and
discuss prior work in the field of multi-robot motion planning.

###  II-A Motion Planning Preliminaries

In motion planning, a configuration refers to a set of values for a robot’s
degrees of freedom, including their position in the workspace, orientation,
and other parameters such as joint angles. The configuration space
($\mathcal{C}_{space}$) consists of all possible configurations and can be
partitioned into $\mathcal{C}_{free}$ and $\mathcal{C}_{obst}$ made up of
valid and invalid configurations respectively. Motion planning is the problem
of finding a path from a start configuration $q_{s}$ to a goal configuration
$q_{g}$ through $\mathcal{C}_{free}$. Computing the full $\mathcal{C}_{obst}$
is intractable [10, 11], thus state-of-the-art methods turned to sampling-
based motion planning [12, 13]. One such method, Rapidly-exploring Random
Trees [13], iteratively grows a tree made up of configurations and local
connections between them until reaching the goal. This method achieves fast
exploration of the $\mathcal{C}_{space}$ by growing the tree toward randomly
sampled configurations. Alternatively, graph-based methods aim to build a
roadmap graph, a discretized approximation of $\mathcal{C}_{free}$ [12, 14,
15].

###  II-B Multi-robot Motion Planning

The multi-robot motion planning problem is an extension of the motion planning
problem which consists of finding valid paths for a set of robots that also
avoid inter-robot collision. Multi-agent pathfinding (MAPF) is the discrete
state space equivalent of the MRMP problem which consists of finding
collision-free paths for a set of robots over a given graph representation
(e.g. a grid) rather than through continuous space. In environments with
narrow passages, it is non-trivial to construct a graph representation that
captures the connectivity of the planning space, hence our consideration of
MRMP.

Decoupled methods, such as Decoupled PRM [1], plan paths for each robot
separately. These methods are incomplete and, thus, cannot resolve complex
inter-robot conflicts. Some coupled methods, including Composite PRM [1] and
Composite RRT [13] provide a high level of coordination by planning directly
in the composite space, $C_{0}\times...\times C_{n-1}$ where $C_{i}$ is the
configuration space of robot $i$. This becomes computationally intractable due
to the high dimensionality of the space with large groups of robots. Other
coupled methods, including MRdRRT [16] and its variants [17, 18], construct
single-robot roadmaps and then use these to search an implicit composite space
roadmap.

Hybrid methods seek to leverage the benefits of both decoupled and coupled
planning. CBS-MP [2] performs a low-level search to find decoupled paths for
each robot and resolves conflicts using a high-level search in the composite
space. Several hybrid MAPF methods have been proposed to find collision-free
paths given a representation of the $\mathcal{C}_{space}$ (e.g. roadmap). M*
[3] conducts an A*-like search, following the optimal individual paths for
each robot until a conflict occurs. Then, the conflicting agents are merged
together and a new conflict-free composite path is found. The Multi-agent
Pathfinding with Constraints (MAPF/C) approach [4] annotates the underlying
representation with constraints indicating that two robots cannot occupy two
vertices, two edges, or an edge and a vertex at the same time. These
constraints are then used by a general MAPF method to find conflict-free
paths. While these methods perform well in open environments, in constrained
settings, they expend excess computation on conflict resolution, limiting
planning efficiency.

###  II-C Guided Motion Planning

Guided motion planning methods leverage external information to more
efficiently find paths. Prior work has explored using knowledge of the
workspace to guide planning. The Exploring/Exploiting Tree (EET) algorithm [7]
propagates a wavefront expansion through the environment, which it uses to
grow a tree from the start to the goal. SyCLoP [8] partitions the environment
into workspace decomposition regions, then finds a high-level plan over these
decomposition regions from the start region to the goal region. This high-
level plan is then used to guide the growth of an RRT through
$\mathcal{C}_{space}$. These single-robot approaches show the benefit of
utilizing workspace guidance for efficient planning.

####  II-C1 Skeleton-Guided Motion Planning

Skeleton graphs have been built to leverage information about the workspace. A
skeleton is an embedded graph in which edges represent free areas of the
workspace and vertices represent connections between these areas. Examples
include medial axis skeletons [19] and Reeb graphs [20] for 2D environments
and mean curvature skeletons [21] for 3D. They are generally quick to compute,
for example, medial axis skeletons can be computed in $O(n\log n)$ time where
$n$ is the number of obstacle edges [22]. Skeleton-guided motion planning
methods [5, 6, 23] use dynamic regions, bounded local areas of the workspace
that advance along skeleton edges, to efficiently explore free areas of the
environment, including narrow passages. Dynamic Region-biased RRT (DR-RRT)
[5], a single-robot motion planning method, initializes a region on the
skeleton vertex closest to the start. Then, iteratively, configurations are
sampled from within this region and the region is moved forward along its
skeleton edge. When it reaches the end of its edge, new regions are spawned on
the newly reached outgoing edges. This procedure continues until the goal is
reached.

(a) Robot 1

(b) Robot 2

(c) Robot 3

Figure 1:  An example of a composite skeleton edge and a composite region.
Each of the three robots has its own workspace skeleton, shown in purple.
Three skeleton edges that comprise a composite skeleton edge are shown in
blue. Three individual regions that make up a composite region along this
composite skeleton edge are shown in green.

####  II-C2 Composite Dynamic Region-biased RRT

We extended DR-RRT to multi-robot motion planning for scenarios with narrow
passages where a high level of coordination during planning is required.
Composite Dynamic Region-biased RRT (CDR-RRT) [9] is a coupled method that
lazily builds and searches over a composite skeleton (Fig. 1), which is the
Cartesian product graph of the workspace skeleton for each robot in the group.
MAPF is used to generate a path over the workspace skeleton for each robot,
taking into account the capacity of each edge as given by the clearance to
obstacles in the environment. These paths are then combined to form composite
skeleton edges, each of which represents a set of workspace skeleton edges,
one per robot. These edges form a path through the composite skeleton. As in
DR-RRT, regions advance along these composite skeleton edges, building a tree
from the start until the goal is reached. Here, however, the regions exist in
the composite space, representing a set of individual regions, one per robot.

Although CDR-RRT shows a significant improvement in scalability compared to
other state-of-the-art methods in extremely congested environments with narrow
passages where coordination between the full robot group is required during
planning [9], considering the full composite space of all robots comes with
significant computational overhead due to its large size. We now propose a
hybrid method extended from CDR-RRT that uses topological guidance to inform
when planning in the composite space (of all or just a subgroup of robots) is
necessary.

Figure 2: An example hypergraph representation of a hybrid planning space for
a group of four robots. The planner moves between different levels of
composition, coupling robots together to resolve conflicts and decoupling them
when possible. The orange trees represent an example plan through each space.
The dashed hyperarc, for example, represents a change in composition wherein
the red robot can now be considered in its own planning space while the green,
yellow, and blue robots must now coordinate and are considered jointly.

###  II-D Decomposable State Space Hypergraph

The Decomposable State Space Hypergraph (DaSH) framework [24] for hybrid
multi-robot planning leverages a hypergraph representation to enable
coordination between relevant groups of robots without considering the full
composite space unless necessary. A hypergraph
$\mathcal{H}=(\mathcal{V},\mathcal{E})$ is a generalization of a graph where
hyperarcs $E\in\mathcal{E}$ represent connections between sets of vertices,
the tail set containing the source of the hyperarc and the head set containing
the target [25].

This method first builds a high-level hypergraph representation wherein
vertices are task space elements representing the robots required to
coordinate and hyperarcs represent transitions in the composition of robots.
Figure 2 shows an example of a high-level hypergraph representation for a
hybrid MRMP planning space. During planning, robots are coupled together when
necessary and decoupled to improve scalability when possible. The high-level
hypergraph is then used to build a low-level motion hypergraph in which
vertices represent configurations and hyperarcs represent transitions between
them. Hyperarcs in the motion hypergraph give a local plan for the subset of
robots in the group being considered and do not make assumptions about the
locations of the other robots. As such, a hyperpath through the motion
hypergraph represents an optimistic solution. There is no guarantee that each
robot’s path is collision-free considering the full group. The scheduled
variant of CBS-MP [2] is then run over the optimistic solution to find a
validated solution. We build off of the DaSH framework, incorporating skeleton
guidance to propose a novel hybrid MRMP method that is able to efficiently
find paths for robot teams of size up to ten times larger than existing state-
of-the-art methods.

##  III Workspace-DaSH

In this section, we explain the Workspace-DaSH method and describe how we
leverage the skeleton representation of the environment to quickly find motion
plans for large robot teams. The hypergraph skeleton, our high-level
hypergraph representation, functions as a high-level plan to guide the
construction of paths through the workspace. Following the DaSH framework, we
translate this high-level representation into a motion hypergraph, which
stores each robot’s path through the $\mathcal{C}_{space}$.

Algorithm 1 Workspace-DaSH

1:Skeleton $S$ and a Query $\\{q_{s},q_{g}\\}$

2:$\mathcal{H}_{m}\leftarrow\emptyset$ $\triangleright$ Motion hypergraph

3:$hyperpath\leftarrow\emptyset$ $\triangleright$ Motion solution

4:$C\leftarrow\emptyset$ $\triangleright$ MAPF constraints

5:while $hyperpath=\emptyset$

6: $P\leftarrow\textsc{MAPF}(S,C,q_{s},q_{g})$

7:
$\mathcal{H}_{s}=(\mathcal{V}_{s},\mathcal{E}_{s})\leftarrow\textsc{BuildHypergraphSkeleton}(P)$

8:
$C^{skelEdge}\leftarrow\textsc{SimplifiedCDRRRT}(\mathcal{E}_{s}^{skelEdge},\mathcal{H}_{m})$

9: $C^{comp}\leftarrow\emptyset$ $\triangleright$ Composition hyperarc
constraints

10: if $C^{skelEdge}=\emptyset$ $\triangleright$ Continue only if all edges
succeeded

11:
$C^{comp}\leftarrow\textsc{SampleLocalPaths}(\mathcal{E}_{s}^{comp},\mathcal{H}_{m})$

12: if $C^{comp}=\emptyset$ $\triangleright$ Continue only if all hyperarcs
succeeded

13: $hyperpath\leftarrow\textsc{ValidateSolution}(\mathcal{H}_{m})$

14: $C\leftarrow C\cup C^{skelEdge}\cup C^{comp}$ $\triangleright$ Update MAPF
constraints

Algorithm 2 Simplified CDR-RRT

1:Skeleton edge hyperarcs $\mathcal{E}_{s}^{skelEdge}$, motion hypergraph
$\mathcal{H}_{m}$, maximum extension failures $\tau$

2:$C\leftarrow\emptyset$ $\triangleright$ MAPF constraints

3:for $E\in\mathcal{E}_{s}^{skelEdge}$

4: $r\leftarrow\textsc{InitializeSamplingRegion}(E.\textsc{source})$

5: $coveredEdge\leftarrow false$

6: while $\neg coveredEdge$ and $r.\textsc{NumFailures}<\tau$

7: $q_{rand}\leftarrow\textsc{SampleCfg}(r)$ $\triangleright$ Sample from
region

8: $q_{new}\leftarrow\textsc{ExtendLocalPath}(\mathcal{H}_{m},q_{rand})$

9: if $\neg q_{new}.\textsc{ExtensionSucceeded}()$

10: $r.\textsc{IncrementFailures}()$

11: else

12: while $r.\textsc{ContainsCfg}(q_{new})$

13: $r.\textsc{AdvanceAlongSkeletonEdge}(E)$

14: if $r.\textsc{ReachedEndOfSkeletonEdge}(E)$

15: $coveredEdge\leftarrow true$

16: if $r.\textsc{NumFailures}>\tau$

17: $C\leftarrow C\cup\\{E\\}$ $\triangleright$ Add constraint for failed
hyperarc

18: break $\triangleright$ Replan MAPF solution

19:return $C$

###  III-A High-level Hypergraph Skeleton Construction

The hypergraph skeleton is a data structure that captures both the topology of
the environment and the composition of the search space to consider in that
area. To reduce the size of the search space explored, we explicitly construct
a hyperpath through the hypergraph skeleton and only add additional vertices
and hyperarcs if the initial hyperpath cannot yield a motion solution.

Algorithm 1 shows an overview of Workspace-DaSH. Given a skeleton of the
workspace, we first construct a valid path over the skeleton for each robot
using a MAPF algorithm (line 6). We set the capacity of each workspace
skeleton edge as given by the minimum clearance to an obstacle. We then
combine these paths to form a hyperpath through the hypergraph skeleton (line
7). The hypergraph skeleton is composed of vertices representing positions for
a set of robots and hyperarcs representing a change in composition and/or
motion for a group of robots. These hyperarcs can be classified as one of five
types (Fig. 3):

####  III-A1 Skeleton Edge Hyperarcs

Represent a workspace skeleton edge and store the group of robots that move
along it.

####  III-A2 Opposite Direction Decouple Hyperarcs

Represent the change in composition that occurs when a robot group decouples
into two smaller groups after moving in opposite directions along a skeleton
edge.

####  III-A3 Skeleton Vertex Merge Hyperarcs

Occur when two or more groups of robots approach a skeleton vertex along
different skeleton edges. To mitigate the risk of inter-robot collisions
within this congested area, we compose these groups together a small distance
out from the vertex and then sample a local composite path into the vertex
region together. This type of hyperarc represents both this motion and the
change in composition.

####  III-A4 Skeleton Vertex Split Hyperarcs

Occur after a skeleton vertex merge hyperarc if robots within the group of the
merge hyperarc leave the skeleton vertex region onto different workspace
skeleton edges. We sample a local composite path for the robots out of the
skeleton vertex region a short distance onto their respective skeleton edges.
This type of hyperarc again represents both this motion and the change in
composition of the full merge group splitting into two or more smaller groups.

####  III-A5 Opposite Direction Couple Hyperarcs

Represent the change in composition that occurs when two robot groups moving
in opposite directions along the same skeleton edge are coupled together into
one group.

(a) Segment of Robot Paths over Skeleton

(b) Composition Hyperarcs Generated

Figure 3: A segment of the robot paths over the skeleton and their
corresponding composition hyperarcs in the hypergraph skeleton. The green and
red robots are initially moving in opposite directions along the same skeleton
edge. Then, red and blue reach the skeleton vertex together and go on to
different edges. The yellow robot begins moving in the opposite direction of
the red robot when the red robot reaches the next skeleton edge.

###  III-B Translation to Low-level Motion Hypergraph

Once the hypergraph skeleton is constructed from the MAPF solution, we
translate the hypergraph skeleton into an optimistic set of robot paths by
constructing the motion hypergraph. As in the DaSH framework, vertices in the
motion hyperarc represent configurations for a given group of robots and
hyperarcs represent local paths between these configurations.

The skeleton edge hyperarcs are translated to motion hyperarcs using a
simplified version of CDR-RRT (Alg. 1 line 8; Alg. 2). Since the tail and head
sets of a skeleton edge hyperarc both only contain one vertex, a skeleton edge
hyperarc is equivalent to a composite skeleton edge. Thus, a composite-space
RRT is grown along each skeleton edge hyperarc using composite dynamic region
advancement as in CDR-RRT.

The opposite direction decouple and couple hyperarcs only represent changes in
composition and not motion, so they directly translate to composition
hyperarcs in the motion hypergraph. The skeleton vertex merge and split
hyperarcs are translated to motion hyperarcs by using Composite RRT [13] to
connect the trees already created along the incoming and outgoing skeleton
edge hyperarcs (Alg. 1 line 11).

It is possible that the translation of a hypergraph skeleton hyperarc into a
motion hyperarc could fail. This would happen if the RRT failed to be extended
a given number of times during the translation of either a skeleton edge
hyperarc (Alg. 2 line 16) or a skeleton vertex merge or split hyperarc. If a
skeleton edge hyperarc fails, we impose a constraint that the MAPF solution
cannot contain the same set of robots moving along that skeleton edge (Alg. 1
lines 8, 14). If a skeleton vertex merge or split hyperarc fails, we impose
the constraint that the MAPF solution cannot contain the same groups of robots
moving along the incoming and outgoing skeleton edges to and from the merge or
split (Alg. 1 lines 11, 14). We then replan the MAPF solution and try again to
translate the hypergraph skeleton into a complete motion hyperpath.

To guarantee that the produced paths for the robots are inter-robot collision-
free, as in DaSH, we run the scheduled variant of CBS-MP [2] over the paths
(Alg. 1 line 13).

Figure 4: In the Warehouse environment, robots located on the top and bottom
of each narrow aisle must swap places with the robot they are vertically
aligned with.

(a) Tunnels Environment

(b) Tunnels Query

Figure 5: In the Tunnels environment, robots must find and traverse multiple
tunnels while moving from the red start positions at the back to the blue goal
positions at the front.

(a) GridMaze

(b) GridMaze Query

Figure 6: In the GridMaze environment, robots must move between randomly
located starts (red) and goals (blue) within the maze, some of which overlap.

(a) Mining

(b) Mining Query

Figure 7: In the mining environment, robots must swap places with another robot located in an adjacent mine shaft, query locations are shown in red. Figure 8: Average runtime results for the Warehouse scenario. The standard deviation is shown by the shaded region around each line. The running time for the Scheduled CBS validation step of Workspace-DaSH is shown by the dashed line. Data is omitted where all seeds failed. TABLE I: Warehouse results. Data omitted where all seeds failed Method | Robots | Runtime (s) | Success Rate
---|---|---|---
Avg | Std Dev
Workspace-DaSH | 2 | 4.8 | 1.2 | 100%
CDR-RRT | 4.5 | 1.3 | 100%
Composite RRT | 50.6 | 52.5 | 100%
M* | 31.9 | 18.5 | 100%
MRdRRT | 74.2 | 101.7 | 53.3%
Workspace-DaSH | 4 | 9.4 | 1.9 | 100%
CDR-RRT | 12.5 | 2.5 | 100%
Composite RRT | 346.0 | - | 6.7%
M* | 346.6 | 212.8 | 26.7%
MRdRRT | 119.0 | - | 6.7%
Workspace-DaSH | 8 | 17.6 | 3.1 | 100%
CDR-RRT | 123.7 | 55.2 | 100%
Workspace-DaSH | 16 | 30.2 | 5.4 | 100%
Workspace-DaSH | 32 | 71.4 | 23.7 | 100%
Workspace-DaSH | 64 | 248.0 | 99.2 | 86.7%
Workspace-DaSH | 80 | 441.7 | 137.6 | 86.7%

##  IV Validation

We run scaling MRMP scenarios in environments designed to highlight the
strengths and weaknesses of our method relative to other state-of-the-art
approaches.

###  IV-A Experimental Setup

We measure the performance of Workspace-DaSH against CDR-RRT [9] as well as a
set of other approaches we feel are relevant for comparison. Composite RRT
[13] operates in the full composite space, providing a high level of
coordination. MRdRRT [16] was originally intended for manipulators, but we
feel its implicit search of the composite space makes it pertinent for
comparison. M* [3] uses subdimensional expansion to limit the size of the
search space which is similar in concept to our hypergraph representation. M*
is a multi-agent pathfinding method, so we use PRM [12] to generate the
underlying $\mathcal{C}_{space}$ representation. We use Conflict-based Search
[26] to generate the MAPF solutions over the workspace skeleton from which we
construct the hypergraph skeleton for Workspace-DaSH. Each method was
implemented in the open-source Parasol Planning Library. All experiments were
run using a computer with an AMD Ryzen 7 6800H CPU at 3.2GHz and 16GB of RAM.
We run 15 seeds for each scenario. Each method is given 600 seconds to solve a
scenario or is considered a failure.

Figure 9: Average runtime results for the Tunnels scenario. The standard deviation is shown by the shaded region around each line. Data is omitted where all seeds failed. Data is omitted where all seeds failed. TABLE II: Tunnels results. Data omitted where all seeds failed Method | Robots | Runtime (s) | Success Rate
---|---|---|---
Avg | Std Dev
Workspace-DaSH | 2 | 21.9 | 2.3 | 100%
CDR-RRT | 18.8 | 3.3 | 100%
Workspace-DaSH | 4 | 37.5 | 3.2 | 100%
CDR-RRT | 58.4 | 11.2 | 100%
Workspace-DaSH | 8 | 74.8 | 5.7 | 100%
CDR-RRT | 130.5 | 12.0 | 100%
Workspace-DaSH | 16 | 94.3 | 2.5 | 100%
CDR-RRT | 290.0 | 17.8 | 100%
Workspace-DaSH | 32 | 208.2 | 6.3 | 100%
Workspace-DaSH | 64 | 487.4 | 12.0 | 86.7%
Figure 10: Average runtime results for the Mining scenario. The standard deviation is shown by the shaded region around each line. Data is omitted where all seeds failed. TABLE III: Mining results. Data omitted where all seeds failed Method | Robots | Runtime (s) | Success Rate
---|---|---|---
Avg | Std Dev
Workspace-DaSH | 2 | 5.9 | 4.9 | 100%
CDR-RRT | 8.3 | 1.7 | 100%
Workspace-DaSH | 4 | 7.6 | 1.1 | 100%
CDR-RRT | 42.3 | 14.1 | 100%
Workspace-DaSH | 8 | 13.7 | 1.3 | 100%
CDR-RRT | 124.3 | 45.9 | 100%
Workspace-DaSH | 16 | 28.9 | 0.9 | 100%
CDR-RRT | 316.8 | 94.9 | 93.3%
Workspace-DaSH | 32 | 88.5 | 15.6 | 93.3%
Workspace-DaSH | 64 | 412.6 | 378.7 | 73.3%

###  IV-B Environments

Here, we describe our experimental environments and explain which aspects of
our approach these scenarios are designed to highlight.

####  IV-B1 Warehouse (Fig. 4)

The Warehouse environment features a series of narrow aisles. Robots start on
the top and bottom of the aisles and must swap places with the robot with
which they are vertically aligned. This scenario measures each approach’s
ability to efficiently handle narrow passages within the environment. We
highlight Workspace-DaSH’s ability to decompose the problem using topological
guidance. In the Warehouse environment, we also run an extended-time scaling
experiment with 80 robots and a 1000-second time limit.

####  IV-B2 Tunnels (Fig. 5)

The Tunnels environment is three-dimensional and features several narrow
passages that the robots must traverse. Because of the three-dimensional
workspace, the size of the planning space becomes very large. This scenario is
intended to measure each algorithm’s performance with respect to the geometric
complexity, rather than the congestion, of the environment. Each robot must
find and traverse multiple narrow passages to reach its goal, but its shortest
path does not conflict with any other robot’s.

####  IV-B3 Mining (Fig. 7)

The Mining environment is a 3D environment meant to mimic a set of mine
shafts. Again, it features several narrow passages; however, here robots must
move in close proximity to each other. We show that Workspace-DaSH is capable
of efficiently finding paths for large robot teams in real-world scenarios.

####  IV-B4 GridMaze (Fig. 6)

The GridMaze environment is a 3D environment featuring several intersecting
narrow tunnels intended to elicit high congestion for large groups of robots
in addition to geometric complexity. We demonstrate Workspace-DaSH’s ability
to efficiently find paths for large groups of robots in these congested
settings.

Figure 11: Average runtime results for the GridMaze scenario. The standard deviation is shown by the shaded region around each line. Data is omitted where all seeds failed. Lines for Composite RRT, M*, and MRdRRT are not visible since they only succeeded for the 2-robot scenario. TABLE IV: GridMaze results. Data omitted where all seeds failed Method | Robots | Runtime (s) | Success Rate
---|---|---|---
Avg | Std Dev
Workspace-DaSH | 2 | 2.2 | 0.3 | 100%
CDR-RRT | 8.1 | 2.1 | 100%
Composite RRT | 297.0 | - | 6.7%
M* | 423.0 | 156.4 | 53.3%
MRdRRT | 417.8 | 106.6 | 26.7%
Workspace-DaSH | 4 | 5.2 | 0.3 | 100%
CDR-RRT | 157.5 | 30.6 | 100%
Workspace-DaSH | 8 | 8.6 | 0.7 | 100%
Workspace-DaSH | 16 | 21.6 | 1.2 | 100%
Workspace-DaSH | 32 | 62.6 | 15.1 | 93.3%

In the Warehouse scenario (results in Fig. 8 and Tab. I), all methods except
MRdRRT achieve a 100% success rate in the 2-robot scenario. However, the
methods that do not leverage topological guidance begin to struggle with the
4-robot scenario and cannot solve the 8-robot scenario. CDR-RRT is able to
solve up to the 8-robot scenario where the exponential size of the composite
space leads to a significant decrease in performance. Workspace-DaSH, like
CDR-RRT, sees the benefit of using the skeleton representation to guide
planning through narrow passages and the coordination provided by using the
composite space of multiple robots. Additionally, by using the workspace to
inform the planner when to move between different levels of composition,
Workspace-DaSH is able to focus planning within smaller spaces than CDR-RRT,
making it able to plan for significantly larger robot teams, up to 64 robots,
within the 600-second time limit. Planning time for Workspace-DaSH in the
larger groups is dominated by the path validation step, which becomes evident
in the 64 and 80-robot scenarios as shown in Fig. 8.

In the Tunnels environment (results in Fig. 9 and Tab. II), the size of the
search space is increased significantly relative to the Warehouse environment
since the robot now has six degrees of freedom. Composite RRT, M*, and MRdRRT
are unable to find a solution for the 2-robot scenario. This is due both to
the large size of the search space and the complexity of the environment.
Here, the narrow passage problem is exacerbated since the query requires the
planner to find and traverse multiple narrow passages. By leveraging skeleton
guidance, CDR-RRT and Workspace-DaSH are able to find solutions for larger
groups of robots. Searching the composite space, which grows exponentially
with the number of robots, hinders CDR-RRT’s performance, leaving it unable to
solve the 32-robot scenario within the time limit. Workspace-DaSH is able to
efficiently find solutions for up to 64 robots within the time limit due to
its ability to decompose the planning space.

In the Mining environment (results in Fig. 10 and Tab. III), Composite RRT,
M*, and MRdRRT are unable to find a solution for the 2-robot scenario due to
the large size of the search space and inter-robot conflicts. By leveraging
topological guidance to limit exploration of the composite space, CDR-RRT is
able to solve up to the 16-robot scenario. However, it is unable to solve the
32-robot scenario. Workspace-DaSH, by considering the composite space only
when necessary, is able to efficiently solve up to the 64-robot scenario
within the time limit. The higher variance in Workspace-DaSH’s performance in
the Mining 64-robot scenario as compared to the Tunnels 64-robot scenario
results from the increased difficulty of resolving forced inter-robot
conflicts while moving between narrow passages in the Mining environment.

In the 3D GridMaze scenario (results in Fig. 11 and Tab. IV), as a result of
the large size of the planning space as well as the difficulty posed by the
long narrow passages, Composite RRT, M*, and MRdRRT struggle with the 2-robot
scenario and all fail to produce a solution for the 4-robot scenario. While
CDR-RRT is able to solve the 4-robot scenario, the large size of the composite
space prevents it from finding a solution for the 8-robot scenario within the
time limit. Alternatively, by leveraging the ability to plan in smaller spaces
when robots are not physically near each other, Workspace-DaSH is able to find
solutions up to 32 robots, where the environment becomes extremely congested
due to robots moving in close proximity to each other.

##  V Conclusion and Future Work

In this paper, we present Workspace-DaSH, a scalable hybrid multi-robot motion
planning method that leverages topological guidance in multiple ways, both to
inform how to move between different levels of composition during planning and
to guide sampling through narrow passages in the workspace. By using knowledge
of the workspace, our method is able to efficiently find paths for robot
groups of size up to ten times larger than existing state-of-the-art methods.
Building off of this work, we plan to explore using parallel computing to
further improve the performance of this method, taking advantage of the
hypergraph’s ability to naturally decompose the multi-robot motion planning
problem.

## References

  * [1] G. Sanchez and J.-C. Latombe, “Using a prm planner to compare centralized and decoupled planning for multi-robot systems,” in _Proc. IEEE Int. Conf. Robot. Autom. (ICRA)_ , vol. 2, 2002, pp. 2112–2119.
  * [2] I. Solis, J. Motes, R. Sandström, and N. M. Amato, “Representation-optimal multi-robot motion planning using conflict-based search,” _IEEE Robotics and Automation Letters_ , vol. 6, no. 3, pp. 4608–4615, 2021.
  * [3] G. Wagner and H. Choset, “M*: A complete multirobot path planning algorithm with performance bounds,” in _Proc. IEEE Int. Conf. Intel. Rob. Syst. (IROS)_ , 2011, pp. 3260–3267.
  * [4] W. Hönig, J. A. Preiss, T. K. S. Kumar, G. S. Sukhatme, and N. Ayanian, “Trajectory planning for quadrotor swarms,” _IEEE Transactions on Robotics_ , vol. 34, no. 4, pp. 856–869, 2018.
  * [5] J. Denny, R. Sandström, A. Bregger, and N. M. Amato, “Dynamic region-biased rapidly-exploring random trees,” in _Alg. Found. Robot. XII_. Springer, 2020, (WAFR ‘16).
  * [6] R. Sandstrom, D. Uwacu, J. Denny, and N. M. Amato, “Topology-guided roadmap construction with dynamic region sampling,” _IEEE Robotics and Automation Letters_ , vol. 5, no. 4, pp. 6161–6168, 2020.
  * [7] M. Rickert, A. Sieverling, and O. Brock, “Balancing exploration and exploitation in sampling-based motion planning,” _IEEE Transactions on Robotics_ , vol. 30, no. 6, pp. 1305–1317, 2014.
  * [8] E. Plaku, L. Kavraki, and M. Vardi, “Motion planning with dynamics by a synergistic combination of layers of planning,” _IEEE Trans. Robot._ , vol. 26, no. 3, pp. 469–482, June 2010.
  * [9] C. McBeth, J. Motes, D. Uwacu, M. Morales, and N. M. Amato, “Scalable multi-robot motion planning for congested environments with topological guidance,” _IEEE Robotics and Automation Letters_ , vol. 8, no. 11, pp. 6867–6874, 2023.
  * [10] J. T. Schwartz and M. Sharir, “On the “piano movers” problem. ii. general techniques for computing topological properties of real algebraic manifolds,” _Advances in applied Mathematics_ , vol. 4, no. 3, pp. 298–351, 1983.
  * [11] J. F. Canny, _The Complexity of Robot Motion Planning_. Cambridge, MA: MIT Press, 1988.
  * [12] L. E. Kavraki, P. Švestka, J. C. Latombe, and M. H. Overmars, “Probabilistic roadmaps for path planning in high-dimensional configuration spaces,” _IEEE Trans. Robot. Automat._ , vol. 12, no. 4, pp. 566–580, Aug. 1996.
  * [13] S. M. Lavalle, “Rapidly-exploring random trees: A new tool for path planning,” Iowa State University, Tech. Rep. 11, 1998.
  * [14] C. Holleman and L. E. Kavraki, “A framework for using the workspace medial axis in prm planners,” in _Proc. IEEE Int. Conf. Robot. Autom. (ICRA)_ , vol. 2, San Franasisco, CA, 2000, pp. 1408–1413.
  * [15] J. D. Marble and K. E. Bekris, “Asymptotically near-optimal planning with probabilistic roadmap spanners,” _IEEE Trans. Robot._ , vol. 29, pp. 432–444, 2013.
  * [16] K. Solovey, O. Salzman, and D. Halperin, “Finding a needle in an exponential haystack: Discrete rrt for exploration of implicit roadmaps in multi-robot motion planning,” _The International Journal of Robotics Research_ , vol. 35, no. 5, pp. 501–513, 2016.
  * [17] A. Dobson, K. Solovey, R. Shome, D. Halperin, and K. E. Bekris, “Scalable asymptotically-optimal multi-robot motion planning,” in _2017 international symposium on multi-robot and multi-agent systems (MRS)_. IEEE, 2017, pp. 120–127.
  * [18] R. Shome, K. Solovey, A. Dobson, D. Halperin, and K. E. Bekris, “drrt*: Scalable and informed asymptotically-optimal multi-robot motion planning,” _Autonomous Robots_ , vol. 44, no. 3, pp. 443–467, 2020.
  * [19] H. Blum, “A transformation for extracting new descriptors of shape,” in _Models for Perception of Speech and Visual Form_ , W. Wathen-Dunn, Ed. Cambridge, MA: MIT Press, 1967.
  * [20] G. Reeb, “Sur les points singuliers d’une forme de pfaff completement integrable ou d’une fonction numerique,” _Comptes Rendus Acad. Sciences Paris_ , no. 222, pp. 847–849, 1946.
  * [21] A. Tagliasacchi, I. Alhashim, M. Olson, and H. Zhang, “Mean curvature skeletons,” _Computer Graphics Forum_ , vol. 31, pp. 1735–1744, 08 2012\.
  * [22] D. T. Lee, “Medial axis transformation of a planar shape,” _IEEE Transactions on Pattern Analysis and Machine Intelligence_ , vol. PAMI-4, no. 4, pp. 363–369, 1982.
  * [23] D. Uwacu, A. Yammanuru, M. Morales, and N. M. Amato, “Hierarchical planning with annotated skeleton guidance,” _IEEE Robotics and Automation Letters_ , vol. 7, no. 4, pp. 11 055–11 061, 2022.
  * [24] J. Motes, T. Chen, T. Bretl, M. M. Aguirre, and N. M. Amato, “Hypergraph-based multi-robot task and motion planning,” _IEEE Transactions on Robotics_ , vol. 39, no. 5, pp. 4166–4186, 2023.
  * [25] G. Gallo, G. Longo, S. Pallottino, and S. Nguyen, “Directed hypergraphs and applications,” _Discrete Applied Mathematics_ , vol. 42, no. 2, pp. 177–201, 1993. [Online]. Available: https://www.sciencedirect.com/science/article/pii/0166218X9390045P
  * [26] G. Sharon, R. Stern, A. Felner, and N. R. Sturtevant, “Conflict-based search for optimal multi-agent pathfinding,” _Artificial Intelligence_ , vol. 219, pp. 40–66, 2015.