# The transformation of edge-regular and pseudo strongly regular graphs under
graph operations

Jeepamol J. Palathingal 111Email<EMAIL_ADDRESS>
Department of Mathematics
PM Government College
Chalakudy-680722, Kerala, India.
Aparna Lakshmanan S.222E-mail<EMAIL_ADDRESS><EMAIL_ADDRESS>
Department of Mathematics
Cochin University of Science and Technology
Cochin-682022, Kerala, India.
Greg Markowsky 333E-mail<EMAIL_ADDRESS>
School of Mathematics
Monash University
Clayton, VIC Australia

###### Abstract

The graph $G$ is said to be strongly regular with parameters
$(n,k,\lambda,\mu)$ if the following conditions hold: (1) each vertex has $k$
neighbours; (2) any two adjacent vertices of $G$ have $\lambda$ common
neighbours; (3) any two non-adjacent vertices of $G$ have $\mu$ common
neighbours. In this paper we study two weaker notions of strongly regular
graphs. A graph satisfying the conditions $(1)$ and $(2)$ is called an edge-
regular graph with parameters $(n,k,\lambda)$. We call a graph satisfying the
conditions $(1)$ and $(3)$ a pseudo strongly regular graph with parameters
$(n,k,\mu)$. In this paper we study the impact of various graph operations on
edge regular graphs and pseudo strongly regular graphs.

Keywords: Strongly regular graph, edge-regular graph, pseudo strongly regular
graph, graph operations.

##  1 Introduction

The graph $G$ is said to be strongly regular [2] with parameters
$(n,k,\lambda,\mu)$ if the following conditions hold:
(1) each vertex has $k$ neighbours;
(2) any two adjacent vertices of $G$ have $\lambda$ common neighbours;
(3) any two non-adjacent vertices of $G$ have $\mu$ common neighbours.

In literature there are several classes of graphs containing the strongly
regular graphs, but which are defined by a weakening of these conditions. A
graph satisfying the conditions $(1)$ and $(2)$ is called an edge-regular
graph [18] with parameters $(n,k,\lambda)$. This is a relatively weak
condition, and there are numerous examples. Recent research has focussed on
the clique structure of such graphs ([11, 21]). A graph such that the number
of common neighbours of any pair of vertices can be one of just two values is
called a Deza graph with parameters $(n,\lambda,\mu)$; this family has
attracted considerable recent interest ([7, 8, 10]). A graph satisfying the
conditions $(1)$ and $(3)$ has been mentioned in [18], but to our knowledge
has not been given any specific name. Since it is a weaker version of strongly
regular graph, we will refer to it as a pseudo strongly regular graph. It is
evident that strongly regular graphs are edge-regular, Deza, and pseudo
strongly regular, but the converse does not hold. In fact, the class of
strongly regular graphs is far more restricted than that of others, with a
rich structure that has attracted numerous researchers. For excellent
overviews on this topic, see [4, 5, 9].

In this paper we study how applying graph operations transforms edge-regular,
pseudo strongly regular, and strongly regular graphs. For that we consider the
following graph operations: the complement of a graph, the cartesian product,
the direct product, the composition, the strong product, the join, the line
graph, the subdivision graph, and the semi-total point graph. The next section
gives a few examples of edge-regular and pseudo strongly regular graphs, and
then each of the subsequent sections will be devoted to one of the operations,
and will contain the required definitions.

All graph theoretic notations and terminology we use are standard and can be
found, for instance, in [1]. Before beginning our investigation, we isolate
some notation for the readers convenience. We will write $u\sim v$ for $u$
adjacent to $v$, $u\nsim v$ for $u$ non-adjacent to $v$ [6], and we denote the
number of common neighbors of $u$ and $v$ by $|com\\{u,v\\}|$.

##  2 Examples of edge-regular and pseudo strongly regular graphs

There are many examples of edge-regular graphs present in the literature ([3]
contains a plethora). We also have the following direct observations.

  1. 1.

All $K_{3}$-free regular graphs are edge-regular.

  2. 2.

The graph $C_{4}\vee 2K_{1}$ (see Section 8) is edge-regular with parameters
$(6,4,2)$. This is the well-known octahedral graph.

  3. 3.

The semi-total point graph $R(G)$ of a graph $G$ is obtained from $G$ by
adding a new vertex corresponding to every edge of $G$, then joining each new
vertex to the end vertices of the corresponding edge [19]. Take two copies of
$R(C_{n})$. Let $v_{1},v_{2},...,v_{n}$ be the vertices of degree $2$ in the
first copy of $R(C_{n}$) and
$v_{1}^{\prime},v_{2}^{\prime},...,v_{n}^{\prime}$ be the vertices of degree
$2$ in the second copy of $R(C_{n}$). Merge $v_{i}$ with $v_{i}^{\prime}$. The
new graph is edge-regular with parameters $(3n,4,1)$.

The class of pseudo strongly regular graphs is not as well documented as that
of the edge-regular graphs, but in light of Theorem 3.1 below the easiest way
to construct them is as complements of edge-regular graphs. This does not
always lead to interesting examples, for instance the complement of the
octahedral graph is the disjoint union of three copies of $K_{2}$. However,
the complement of the graph made from two copies of $R(C_{n})$ described above
is a more interesting example. It is pseudo strongly regular with parameters
$(3n,3n-5,3n-7)$.

##  3 Complement

If $G$ is a graph, then the complement of $G$, denoted $G^{c}$, has the same
vertex set as $G$ with adjacency in $G^{c}$ defined by $x\sim y$ in $G^{c}$
precisely when $x\nsim y$ in $G$. The following theorem may be considered
known, due to its importance in connection with strongly regular graphs (see
the corollary below), but is nevertheless included for completeness.

######  Theorem 3.1.

$G$ is an edge-regular graph with parameters $(n,k,\lambda)$ if and only if
$G^{c}$ is a pseudo strongly regular graph with parameters
$(n,n-k-1,n-2k+\lambda)$.

###### Proof.

Consider an edge regular graph $G$ with parameters $(n,k,\lambda)$. Clearly,
$G^{c}$ is $(n-1-k)$-regular. Now consider two vertices $u$ and $v$ which are
not adjacent in $G^{c}$. Then $u$ and $v$ are adjacent in $G$. Then the number
of common neighbours of $u$ and $v$ in $G^{c}$ is $n-2-(2k-2-\lambda)$. Hence
$G^{c}$ is pseudo strongly regular with parameters $(n,n-k-1,n-2k+\lambda)$.

For the converse, assume $G^{c}$ is pseudo strongly regular with parameters
$(n,n-k-1,\lambda)$. Clearly $G$ is $k$-regular. Now consider two adjacent
vertices $u$ and $v$ in $G$. The number of common neighbours of $u$ and $v$ in
$G$ is $n-2-(2(n-k-1)-(n-2k+\lambda))$. Hence $G^{c}$ is an edge-regular graph
with parameters $(n,k,\lambda)$. ∎

######  Corollary 3.2.

If $G$ is a strongly regular graph with parameters $(n,k,\lambda,\mu)$ then
$G^{c}$ is strongly regular with parameters
$(n,n-k-1,n-2-2k+\mu,n-2k+\lambda)$.

##  4 Cartesian product

The Cartesian product [14, 20] of $G$ and $H$, written $G\square H$, is the
graph with vertex set $V(G_{1})\times V(G_{2})$ and with adjacency defined by
having $(u,v)$ adjacent to $(u^{\prime},v^{\prime})$ precisely when
(1)$u=u^{\prime}$ and $vv^{\prime}\in E(H)$, or
(2) $v=v^{\prime}$ and $uu^{\prime}\in E(G)$.

The question of whether the Cartesian product of two edge-regular graphs is
itself edge-regular has a rather pleasing answer, as follows.

######  Theorem 4.1.

Let $G_{1}=(n_{1},k_{1},\lambda_{1})$ and $G_{2}=(n_{2},k_{2},\lambda_{2})$ be
two edge-regular graphs. $G_{1}\square G_{2}$ is an edge-regular graph with
parameters $(n_{1}n_{2},k_{1}+k_{2},\lambda)$ if and only if
$\lambda_{1}=\lambda_{2}=\lambda$.

###### Proof.

By the definition of cross product $G_{1}\square G_{2}$ is
$(k_{1}+k_{2})$-regular. Now consider two adjacent vertices in $G_{1}\square
G_{2}$. Then either the vertices are of the form $(u_{i},v_{l}),(u_{i},v_{m})$
where $v_{l}$ and $v_{m}$ are adjacent in $G_{2}$ or the vertices are of the
form $(u_{i},v_{l}),(u_{j},v_{l})$ where $u_{i}$ and $u_{j}$ are adjacent in
$G_{1}$. For the first case the number of common vertices of $(u_{i},v_{l})$
and $(u_{i},v_{m})$ is $\lambda_{2}$ while for the second case the number of
common vertices of $(u_{i},v_{l})$ and $(u_{j},v_{l})$ is $\lambda_{1}$. Hence
$G_{1}\square G_{2}$ is edge-regular if and only if $\lambda_{1}=\lambda_{2}$.
∎

We can also ask when this Cartesian product is pseudo strongly regular, but
the answer is not as interesting. We omit the straightforward proof.

######  Theorem 4.2.

If $G_{1}=(n_{1},k_{1},\mu_{1})$ and $G_{2}=(n_{2},k_{2},\mu_{2})$ are two
edge-regular graphs, then $G_{1}\square G_{2}$ is pseudo strongly regular if
and only if one of the graphs is complete and the other is totally
disconnected.

##  5 Direct product

The direct(or tensor or Kronecker) product [12] of $G_{1}$ and $G_{2}$,
written $G_{1}\times G_{2}$, is the graph with vertex set $V(G_{1})\times
V(G_{2})$ and with adjacency specified by having $(u_{1},v_{1})$ adjacent to
$(u_{2},v_{2})$ precisely when $u_{1}$ is adjacent to $v_{1}$ in $G_{1}$ and
$u_{2}$ is adjacent to $v_{2}$ in $G_{2}$. In contrast to the Cartesian
product, the direct product of two edge-regular graphs is always edge-regular.

######  Theorem 5.1.

Let $G_{1}=(n_{1},k_{1},\lambda_{1})$ and $G_{2}=(n_{2},k_{2},\lambda_{2})$ be
two edge-regular graphs. Then $G_{1}\times G_{2}$ is an edge-regular graph
with parameters $(n_{1}n_{2},k_{1}k_{2},\lambda_{1}\lambda_{2})$.

###### Proof.

The degree of an arbitrary vertex in $G_{1}\times G_{2}$ is $k_{1}k_{2}$. If
$(u_{i},v_{l})$ and $(u_{j},v_{m})$ are adjacent in $G_{1}\times G_{2}$ then
$u_{i}$ and $u_{j}$ are adjacent in $G_{1}$ and $v_{l}$ and $v_{m}$ are
adjacent in $G_{2}$. The number of common vertices of $(u_{i},v_{l})$ and
$(u_{j},v_{m})$ is $\lambda_{1}\lambda_{2}$. Hence $G_{1}\times G_{2}$ is an
edge-regular graph with parameters
$(n_{1}n_{2},k_{1}k_{2},\lambda_{1}\lambda_{2})$. ∎

Following the definitions, it can be shown that $G_{1}\times G_{2}$ is pseudo
strongly regular if and only if $G_{1}$ and $G_{2}$ are strongly regular and
$\lambda_{2}=\mu_{2}=k_{2},\lambda_{1}=\mu_{1}=k_{1}$. However, no such graphs
can exist, since we must always have $\lambda\leq k-1$ for a strongly regular
graph.

##  6 Composition

The composition (or wreath or lexicographic product) of $G_{1}$ and $G_{2}$,
written $G_{1}[G_{2}]$, is the graph with vertex set $V(G_{1})\times
V(G_{2})$, with adjacency specified by having $(u_{1},v_{1})$ adjacent to
$(u_{2},v_{2})$ precisely when $u_{1}$ is adjacent to $v_{1}$ in $G_{1}$ or
$u_{1}=v_{1}$ and $u_{2}$ is adjacent to $v_{2}$ in $G_{2}$. The question of
the edge-regularity of the composition product of two edge-regular graphs is
handled by the following theorem.

######  Theorem 6.1.

Let $G_{1}=(n_{1},k_{1},\lambda_{1})$ and $G_{2}=(n_{2},k_{2},\lambda_{2})$ be
two edge-regular graphs. $G_{1}[G_{2}]$ is edge-regular with parameters
$(n_{1}n_{2},k_{1}n_{2}+k_{2},\lambda)$ if and only if
$\lambda_{1}n_{2}+2\lambda_{2}=k_{1}n_{2}+\lambda_{2}=\lambda$.

###### Proof.

An arbitrary vertex $(u_{i},v_{l})$ in $G_{1}[G_{2}]$ is adjacent to
$k_{1}n_{2}+k_{2}$ vertices. Hence $G_{1}[G_{2}]$ is
$(k_{1}n_{2}+k_{2})$-regular. Now consider two adjacent vertices in
$G_{1}[G_{2}]$. Then either the vertices are of the form
$(u_{i},v_{l}),(u_{j},v_{m})$, where $u_{i}$ and $u_{j}$ are adjacent in
$G_{1}$, or the vertices are of the form $(u_{i},v_{l}),(u_{i},v_{m})$ where
$v_{l}$ and $v_{m}$ are adjacent in $G_{2}$. For the first case a vertex
$(x,y)$ is adjacent to both $(u_{i},v_{l})$ and $(u_{j},v_{m})$ if and only if
one of the following conditions are satisfied.

  1. 1.

$x\sim\\{u_{i},u_{j}\\}$.

  2. 2.

$x=u_{i},y\sim v_{l}$.

  3. 3.

$x=u_{j},y\sim v_{m}$.

Combining these conditions we see that in this case the number of common
vertices is $\lambda_{1}n_{2}+2\lambda_{2}$. For the second case a vertex
$(x,y)$ is adjacent to both $(u_{i},v_{l})$ and $(u_{i},v_{m})$ if and only if
either one of the following conditions are satisfied.

  1. 1.

$x\sim u_{i}$.

  2. 2.

$x=u_{i},y\sim\\{v_{l},v_{m}\\}$.

In this case the number of common vertices is $k_{1}n_{2}+\lambda_{2}$. Hence
$G_{1}\square G_{2}$ is edge-regular if and only if
$\lambda_{1}n_{2}+2\lambda_{2}=k_{1}n_{2}+\lambda_{2}$. ∎

######  Theorem 6.2.

Let $G_{1}=(n_{1},k_{1},\mu_{1})$ and $G_{2}=(n_{2},k_{2},\mu_{2})$ be two
pseudo strongly regular graphs then $G_{1}[G_{2}]$ is pseudo strongly regular
if and only if $\mu_{1}=k_{1}$ and $\mu_{2}=0$ (in this case, $G_{2}$ is a
disjoint union of complete graphs).

###### Proof.

Consider two non-adjacent vertices $x$ and $y$ in $G_{1}\times G_{2}$. Since
$x$ and $y$ are non adjacent the following cases are possible.

  1. 1.

$x=(u_{1},v_{1}),y=(u_{2},v_{2})$, $u_{1}\nsim u_{2}$.

  2. 2.

$x=(u_{1},v_{1}),y=(u_{2},v_{2}),u_{1}=u_{2},v_{1}\nsim v_{2}$.

For the first case a vertex $(p,q)$ is adjacent to $(u_{1},v_{1})$ and
$(u_{2},v_{2})$ if and only if $p\sim\\{u_{1},u_{2}\\}$. Then
$|com\\{x,y\\}|=\mu_{1}n_{2}$. Now for the second case $(p,q)$ is adjacent to
$(u_{1},v_{1})$ and $(u_{1},v_{2})$ if and only if either $p\sim u_{1}$ or
$p=u_{1}$ and $q\sim\\{v_{1},v_{2}\\}$. In this case,
$|com\\{x,y\\}|=k_{1}n_{2}+\mu_{2}$. Hence $G_{1}[G_{2}]$ is pseudo strongly
regular if and only if $\mu_{1}n_{2}=k_{1}n_{2}+\mu_{2}$. Since there exists
no graphs with $\mu_{1}>k_{1}$, $G_{1}[G_{2}]$ is pseudo strongly regular if
and only if $\mu_{1}=k_{1}$ and $\mu_{2}=0$. ∎

##  7 Strong product

The Strong (or normal) product [12], denoted by $G1\boxtimes G2$ is the union
of cartesian and direct prodcts, ie; $(G_{1}\square G_{2})\cup(G_{1}\times
G_{2})$. The edge-regularity of the composition product of two edge-regular
graphs is determined by the following theorem.

######  Theorem 7.1.

Let $G_{1}=(n_{1},k_{1},\lambda_{1})$ and $G_{2}=(n_{2},k_{2},\lambda_{2})$ be
two edge-regular graphs. Then $G_{1}\boxtimes G_{2}$ is an edge regular graph
with parameters $(n_{1}n_{2},k_{1}+k_{2}+k_{1}k_{2},\lambda)$ if and only if
$\lambda_{2}+k_{1}\lambda_{2}+2k_{1}=\lambda_{1}+k_{2}\lambda_{1}+2k_{2}=\lambda_{1}\lambda_{2}+2\lambda_{2}+2\lambda_{1}+2=\lambda$.

###### Proof.

From the definition it is clear that $G_{1}\boxtimes G_{2}$ is
$(k_{1}+k_{2}+k_{1}k_{2})$-regular. When we consider two adjacent vertices in
$G_{1}\boxtimes G_{2}$ the following three cases are possible.

  * $(i)$

The vertices are of the form $(u_{i},v_{l}),(u_{i},v_{m})$, where $v_{l}$ and
$v_{m}$ are adjacent in $G_{2}$

  * $(ii)$

The vertices are of the form $(u_{i},v_{l}),(u_{j},v_{l})$, where $u_{i}$ and
$u_{j}$ are adjacent in $G_{1}$

  * $(iii)$

The vertices are of the form $(u_{i},v_{l}),(u_{j},v_{m})$, where $u_{i}$ and
$u_{j}$ are adjacent in $G_{1}$ and $v_{l}$ and $v_{m}$ are adjacent in
$G_{2}$.

For the Case $(i)$, a vertex $(x,y)$ is adjacent to both $(u_{i},v_{l})$ and
$(u_{i},v_{m})$ if and only if either one of the following conditions are
satisfied.

  1. 1.

$x=u_{i},y\sim\\{v_{l},v_{m}\\}$.

  2. 2.

$x\sim u_{i},y\sim\\{v_{l},v_{m}\\}$

  3. 3.

$x\sim u_{i},y=v_{l}$.

  4. 4.

$x\sim u_{i},y=v_{m}$.

In this case the number of common vertices is
$\lambda_{2}+k_{1}\lambda_{2}+2k_{1}$. In the same way, for Case $(ii)$, we
can prove that the number of common vertices is
$\lambda_{1}+k_{2}\lambda_{1}+2k_{2}$. Now, for the Case $(iii)$, a vertex
$(x,y)$ is adjacent to both $(u_{i},v_{l})$ and $(u_{j},v_{m})$ if and only if
either one of the following conditions are satisfied.

  1. 1.

$x\sim\\{u_{i},u_{j}\\},y\sim\\{v_{l},v_{m}\\}$.

  2. 2.

$x=u_{i},y\sim\\{v_{l},v_{m}\\}$.

  3. 3.

$x=u_{j},y\sim\\{v_{l},v_{m}\\}$.

  4. 4.

$x\sim\\{u_{i},u_{j}\\},y=v_{l}$.

  5. 5.

$x\sim\\{u_{i},u_{j}\\},y=v_{m}$.

  6. 6.

$(x,y)=(u_{i},v_{m})$ or $(x,y)=(u_{j},v_{l})$

In this case the number of common vertices is
$\lambda_{1}\lambda_{2}+2\lambda_{2}+2\lambda_{1}+2$. Hence $G_{1}\boxtimes
G_{2}$ is edge-regular if and only if
$\lambda_{2}+k_{1}\lambda_{2}+2k_{1}=\lambda_{1}+k_{2}\lambda_{1}+2k_{2}=\lambda_{1}\lambda_{2}+2\lambda_{2}+2\lambda_{1}+2$.
∎

It is straightforward to verify that $G_{1}\boxtimes G_{2}$ is pseudo strongly
regular if and only if $G_{1}$ and $G_{2}$ are strongly regular and
$\mu_{2}=1+k_{2},\mu_{1}=k_{1}$. But since we must always have $\mu_{2}\leq
k_{2}$, such graphs do not exist.

##  8 Join

Let $G_{1}$ and $G_{2}$ be vertex-disjoint graphs. Then the join, $G_{1}\vee
G_{2}$, of $G_{1}$ and $G_{2}$ is the supergraph of the vertex disjoint union
of $G_{1}$ and $G_{2}$ in which each vertex of $G_{1}$ is adjacent to every
vertex of $G_{2}$ [1]. The following theorem addresses whether the join of two
edge-regular graphs is again edge-regular.

######  Theorem 8.1.

Let $G_{1}=(n_{1},k_{1},\lambda_{1})$ and $G_{2}=(n_{2},k_{2},\lambda_{2})$ be
two edge-regular graphs. Then $G_{1}\vee G_{2}$ is an edge regular graphs with
parameters $(n_{1}+n_{2},k,\lambda)$ if and only if
$k_{1}+n_{2}=k_{2}+n_{1}=k$ and
$\lambda_{1}+n_{2}=\lambda_{2}+n_{1}=k_{1}+k_{2}=\lambda$.

###### Proof.

By the definition $G_{1}\vee G_{2}$ is regular if and only if
$k_{1}+n_{2}=k_{2}+n_{1}$. Similarly to the previous theorem when we consider
two adjacent vertices $u$ and $v$ of $G_{1}\vee G_{2}$ the following three
cases arise. Either $\\{u,v\\}\in V(G_{1})$ or $\\{u,v\\}\in V(G_{2})$ or
$u\in V(G_{1})$ (or $V(G_{2})$) and $v\in V(G_{2})$ (or $V(G_{1})$). For the
first case the number of common vertices is $\lambda_{1}+n_{2}$. For the
second case the number of common vertices is $\lambda_{2}+n_{1}$. For the
third case the number of common vertices is $k_{1}+k_{2}$. Hence $G_{1}\vee
G_{2}$ is edge-regular if and only if
$\lambda_{1}+n_{2}=\lambda_{2}+n_{1}=k_{1}+k_{2}$ and
$k_{1}+n_{2}=k_{2}+n_{1}$. ∎

Similarly, we can determine whether the join of two pseudo strongly regular
graphs is again pseudo strongly regular.

######  Theorem 8.2.

Let $G_{1}=(n_{1},k_{1},\mu_{1})$ and $G_{2}=(n_{2},k_{2},\mu_{2})$ be two
pseudo strongly regular graphs. Then $G_{1}\vee G_{2}$ is pseudo strongly
regular with parameters $(n_{1}+n_{2},k,\mu)$ if and only if
$k_{1}+n_{2}=k_{2}+n_{1}=k$ and $\mu_{1}+n_{2}=\mu_{2}+n_{1}=\mu$.

###### Proof.

As in Theorem 8.1, $G_{1}\vee G_{2}$ is regular if and only if
$k_{1}+n_{2}=k_{2}+n_{1}$. As in the previous theorem when we consider two
non-adjacent vertices $u$ and $v$ belong to $G_{1}\vee G_{2}$, either
$\\{u,v\\}\in V(G_{1})$ or $\\{u,v\\}\in V(G_{2})$ . For the first case
$|com\\{u,v\\}|=\mu_{1}+n_{2}$. For the second case
$|com\\{u,v\\}|=\mu_{2}+n_{1}$. Hence $G_{1}\vee G_{2}$ is edge-regular if and
only if $\mu_{1}+n_{2}=\mu_{2}+n_{1}$ and $k_{1}+n_{2}=k_{2}+n_{1}$. ∎

##  9 Line graph

The line graph $L(G)$ of a graph $G$ has the edges of $G$ as its vertices, and
two vertices corresponging to distinct edges of $G$ are adjacent in $L(G)$ if
the two edges are incident in $G$ [16]. Line graphs are important in algebraic
graph theory; for instance, [9] devotes an entire chapter to them. The line
graph of an edge-regular graph can only be edge-regular in the extreme cases
$\lambda=0$ or $\lambda=n-2$, as we now show.

######  Theorem 9.1.

Let $G=(n,k,\lambda)$ be an edge-regular graph. Then $L(G)$ is edge-regular if
and only if either $G$ is $K_{3}$-free or $G$ is a complete graph.

###### Proof.

Since $G$ is $k$-regular, $L(G)$ is $(2k-2)$-regular. Now consider two
adjacent vertices $u$ and $v$ in $L(G)$. Since they are adjacent in $L(G)$ the
corresponding edges $e_{1}$ and $e_{2}$ are incident in $G$. The number of
common vertices of $u$ and $v$ is same as the number of edges which are
incident on both $e_{1}$ and $e_{2}$ in $G$. If $e_{1}$ and $e_{2}$ induce a
$K_{3}$ in $G$ then it is $k-1$, otherwise it is $k-2$. Hence $L(G)$ is edge-
regular if and only if either $G$ is $K_{3}$-free or $G$ is $K_{1,2}$-free. ∎

Remarkably, the property of pseudo strong regularity behaves better than edge
regularity with regards to line graphs. Before showing this, we need a
preperatory lemma.

######  Lemma 9.2.

Suppose $H$ is a pseudo strongly regular graph with parameters $(m,k,\mu)$ and
$H\cong L(G)$. Then $\mu\leq 4$.

###### Proof.

Consider two non adjacent vertices $u$ and $v$ in $H$. Let $e_{1}$ and $e_{2}$
be the corresponding edges in $G$. Then $|com\\{u,v\\}|$ is same as the number
of edges incident on both $e_{1}$ and $e_{2}$ in $G$. Since $e_{1}$ and
$e_{2}$ cannot have a common vertex in $G$, the number of such edges is at the
most $4$. Hence $\mu\leq 4$. ∎

Note: The line graph of a pseudo strongly regular graph is pseudo strongly
regular with $\mu=0$ if and only if $L(G)$ is the union of triangles or
isolated vertices (equivalently, $G$ is union of triangles or edges). Note
that, though $L(K_{1,3})$ is $K_{3}$, which is pseudo strongly regular,
$K_{1,3}$ is not even regular. In general, there are graphs which are not
pseudo strongly regular, but whose line graph is pseudo strongly regular. For
example, $G=K_{1,n}$ is not regular and hence not pseudo strongly regular, but
$L(K_{1,n})$ is strongly regular and hence also pseudo strongly regular.

######  Lemma 9.3.

There does not exist any pseudo strongly regular graph $G$ whose $L(G)$ is
pseudo strongly regular with parameter $\mu=3$.

###### Proof.

On the contrary, assume that $G$ is a graph such that $L(G)$ is pseudo
strongly regular with parameter $\mu=3$. By Lemma 9.2, the graph $G$ is
$K_{4}$-free and any two non-adjacent edges of $G$ belong to a diamond. Let
$u_{1},u_{2},u_{3}$ and $u_{4}$ induce a diamond in $G$, where $u_{1}$ and
$u_{4}$ are the non-adjacent pair. Since $G$ is regular, there exists at least
one vertex adjacent to $u_{1}$, say $u_{5}$. Since the edges $u_{1}u_{5}$ and
$u_{3}u_{4}$ are not adjacent, the vertices $u_{1},u_{5},u_{3}$ and $u_{4}$
induce a diamond. Since the graph is $K_{4}$-free, the only possibility is
$u_{5}$ is adjacent to both $u_{3}$ and $u_{4}$. Now, consider the non-
adjacent pair of edges $u_{1}u_{5}$ and $u_{2}u_{4}$. By the same argument
either $u_{2}u_{5}$ or $u_{1}u_{4}$ is an edge in $G$ and in either case the
graph contains a $K_{4}$, which is a contradiction. The lemma follows. ∎

######  Theorem 9.4.

Let $G=(n,k,\mu)$ be a pseudo strongly regular graph. Then $L(G)$ is pseudo
strongly regular with parameter,

  1. 1.

$\mu=4$ if and only if $G\cong K_{n}$, where $n\geq 4$;

  2. 2.

$\mu=2$ if and only if $G$ is (diamond, $K_{4}$)-free and any two edges belong
to a $C_{4}$;

  3. 3.

$\mu=1$ if and only if $G$ is (diamond, $K_{4},C_{4}$)-free and any two edges
belong to a $P_{4}$.

###### Proof.

By Lemma 9.2, $L(G)$ is pseudo strongly regular with $\mu=4$ if and only if
any two non-adjacent edges belong to a $K_{4}$ and $\mu=2,1$ if and only if
any two non-adjacent edges of $G$ belong to a $C_{4}$, $P_{4}$ respectively.
The result follows. ∎

##  10 Subdivision graph

If $uv$ is an edge of $G$, then $uv$ may be subdivided by introducing a new
vertex $w$ and then replacing $uv$ by the edges $uw$ and $wv$. If every edge
of $G$ is subdivided then the resulting graph is the subdivision graph,
denoted by $S(G)$ [13].

######  Theorem 10.1.

Let $G=(n,k,\lambda)$ be an edge-regular graph. $S(G)$ is edge-regular if and
only if $G$ is the disjoint union of cycles.

###### Proof.

Since $S(G)$ is $K_{3}$-free the number of common vertices of two adjacent
vertices is zero. But the new vertices have degree $2$. Therefore $S(G)$ is
edge-regular if and only if $G$ is a $2$-regular graph. Hence $S(G)$ is edge-
regular if and only if $G$ is the disjoint union of cycles. ∎

On the other hand, it is not hard to see that there does not exists any graph
$G$ such that $S(G)$ is pseudo strongly regular. As in the proof of the
previous theorem, $S(G)$ is regular if and only if $G$ is 2-regular, in other
words $G$ is the disjoint union of cycles. Among these graphs the only pseudo
strongly regular graph is the $C_{5}$. But odd cycles are forbidden in $S(G)$,
and hence there does not exist any graph $G$ such that $S(G)$ is pseudo
strongly regular.

##  11 Concluding remarks

We have given a number of examples of graph operations and their effect on the
classes of edge-regular and pseudo strongly regular graphs, however there are
a seemingly limitless supply of other operations that we have not touched
upon. Doubtless there are many other results analogous to ours waiting to be
uncovered.

## References

  * [1] Balakrishnan, R. and K. Ranganathan, A textbook of graph theory, Springer, 1999.
  * [2] Bapat, R.B., Graphs and Matrices, Springer, 2010.
  * [3] Bragan, K., Topics in Edge Regular Graphs (Doctoral dissertation), 2014.
  * [4] Brouwer, A. and Van Maldeghem, H., Strongly regular graphs, https://homepages.cwi.nl/ãeb/math/srg/rk3/srgw.pdf.
  * [5] Cameron, P., Strongly regular graphs, Topics in Algebraic Graph Theory, 102, 2004, 203-221.
  * [6] Cvetcovic, D., Rowlinson, P., and Simic, S., An Introduction to the Theory of Graph Spectra, London Mathematical Society Students Texts, 2010.
  * [7] Deza, M. and Huang, T.,  A generalization of strongly regular graphs.  Southeast Asian Bulletin of Mathematics, 26(2), p. 193–201, 2003.
  * [8] Erickson, M., Fernando, S., Haemers, W., Hardy, D., and Hemmeter, J.,  Deza graphs: A generalization of strongly regular graph.  Journal of Combinatorial Designs, 7(6), p. 395–405, 1999.
  * [9] Godsil, C. and Royle, G., Algebraic graph theory. Vol. 207. Springer Science and Business Media, 2001.
  * [10] Goryainov, S. and Shalaginov, L.,  Deza graphs: a survey and new results.  arXiv preprint arXiv:2103.00228, 2021.
  * [11] Greaves, G. and Koolen, J.  Edge-regular graphs with regular cliques.  European Journal of Combinatorics, 71:194–201, 2018.
  * [12] Hammack, R., Imrich, W., Klavžar, S., Imrich, W., and Klavžar, S.,  Handbook of product graphs,  CRC press Boca Raton, 2011.
  * [13] Harary, F., Graph Theory, Narora publishing House, 1988.
  * [14] Imrich, W., Klavzar, S., and Rall, D.  Topics in graph theory: Graphs and their Cartesian product,  CRC Press, 2008.
  * [15] Kavitha, K. and David, N.G., Dominator coloring of some classes of graphs, International Journal of Mathematical Archive, 3(11), p. 3954 - 3957, 2012.
  * [16] Prisner, E., ”Graph Dynamics”, Longman, 1995.
  * [17] Le, V. B., Gallai graphs and Anti-Gallai Graphs, Discrete Mathematics, 159, p. 179 - 189, 1996.
  * [18] Beineke, L., Wilson, R., and Cameron, P.,Topics in Algebraic Graph Theory: 102 (Encyclopedia of Mathematics and its Applications, Series Number 102), Cambridge University Press, 2004.
  * [19] Sampathkumar, E. and Chikkodimath, S.B., The Semitotal graphs of a graph-II, J. Karnatak Univ. Sci, 18, p. 281 - 284, 1973.
  * [20] West, B., Introduction to Graph Theory, Prentice-Hall, 1999.
  * [21] Soicher, L.,  On cliques in edge-regular graphs.  Journal of Algebra, 421:260–267, 2015.


# Kinematic Base State Estimation for Humanoid using Invariant Extended Kalman
Filter

Amirhosein Vedadi1, Aghil Yousefi-Koma1, Masoud Shariat-Panahi1, Mahdi Nozari1
1School of Mechanical Engineering, College of Engineering, University of
Tehran, Tehran, Iran<EMAIL_ADDRESS>
###### Abstract

This paper presents the design and implementation of a Right Invariant
Extended Kalman Filter (RIEKF) for estimating the states of the kinematic base
of the Surena V humanoid robot. The state representation of the robot is
defined on the Lie group $SE_{4}(3)$, encompassing the position, velocity, and
orientation of the base, as well as the position of the left and right feet.
In addition, we incorporated IMU biases as concatenated states within the
filter.

The prediction step of the RIEKF utilizes IMU equations, while the update step
incorporates forward kinematics. To evaluate the performance of the RIEKF, we
conducted experiments using the Choreonoid dynamic simulation framework and
compared it against a Quaternion-based Extended Kalman Filter (QEKF). The
results of the analysis demonstrate that the RIEKF exhibits reduced drift in
localization and achieves estimation convergence in a shorter time compared to
the QEKF. These findings highlight the effectiveness of the proposed RIEKF for
accurate state estimation of the kinematic base in humanoid robotics.

##  I INTRODUCTION

Humanoid and bipedal robots have become increasingly popular in recent years
due to their ability to perform complex tasks in a variety of environments.
Accurate estimation of the base position, velocity, and orientation of the
robot is of paramount importance for ensuring successful operation,
particularly when considering the inherent noise present in its sensor
measurements. The significance of accurate base position and velocity
estimation is twofold. On one hand, knowing the precise position and velocity
of the base allows us to compute the center of mass (CoM) position and
velocity [1], as well as the divergent component of motion, which plays a
critical role in robot control [2, 3]. On the other hand, accurately
determining the robot’s position is essential for localization purposes and
planning subsequent tasks.

The most straightforward approach for estimating the base of a humanoid robot
involves utilizing its forward kinematics. In this method, it is assumed that
the supporting foot experiences neither rotation nor slippage while in contact
with the ground. By employing encoders on each joint and employing kinematic
modeling of the robot, an estimation of the base can be obtained. However, the
effectiveness of this method is hindered by various factors such as sensor
noise, slip in the contact of the foot, and inaccuracies in the kinematic
modeling, ultimately leading to less desirable outcomes.

Figure 1:  Lower limb model of the Surena V robot in the Choreonoid simulator.
Also, it illustrates the coordinate system for the kinematic base and feet.

To address the aforementioned challenges, researchers have proposed combining
data from various sensors available on humanoid robots, such as IMUs, with
forward kinematics. Notably, Blouch et al. conducted significant research in
this field [4]. In their study, they employed IMU equations within the
prediction step of an error state extended Kalman filter. A key contribution
of their research was the inclusion of foot positions as state variables,
facilitating the direct consideration of errors in leg slippage and movement.
To model the movement of the foot in the contact equation, they utilized
Brownian motion. In the update step of their filter, they incorporated
kinematics equations specific to a quadruped robot. It was demonstrated that
due to the unobservability of the yaw angle and absolute position of the base,
drift in the filter results became unavoidable over time. Rotella et al. [5]
proposed a similar filter to the aforementioned approach specifically designed
for humanoid robots. Given that humanoid robots typically possess flat feet,
any changes in their rotation can directly impact their position. To address
this, the researchers included foot orientation as a state variable, allowing
for its direct consideration in the estimation process. In another study by
Falon et al. [6], a no-drift estimator was developed to address the issue of
drift in humanoid robot localization. The researchers integrated IMU
measurements, forward kinematics equations, and the output of a LIDAR point
cloud to achieve accurate localization. To accomplish this, they employed a
particle filter algorithm, which effectively localized the humanoid robot
within a predefined map while mitigating the effects of drift.

In recent years, there has been an increasing demand to formulate estimation
problems accurately in legged robots. This demand has led to the emergence of
utilizing Lie groups theory and invariant estimator design as a significant
development in this field. By leveraging the principles of Lie groups theory,
researchers have been able to design estimators that are invariant, meaning
they are robust and unaffected by transformations or changes in the robot’s
configuration. The utilization of Lie groups theory has resulted in improved
uncertainty modeling for systems with states represented in Lie groups [7].
Bourmaod et al. [8] presented a framework for discrete and continuous state
estimation utilizing an Extended Kalman Filter (EKF) with predict and update
equations formulated in the context of Lie groups. In their paper, they
introduced the concept of a concentrated Gaussian distribution, which defines
a Gaussian distribution on both the Lie group and its equivalent Lie algebra.
To facilitate computations, this distribution was transformed to Euclidean
space using exponential mapping. The key advantage of this approach is that
the resulting distribution in Euclidean space is no longer normal, thereby
enabling improved performance in addressing nonlinear problems.

Invariant filters are a class of filters where the estimation error of their
state remains constant under different transformations applied to their state
space [9]. Barau and Bonnabel [10] extended the concept of invariant filters
to systems defined on Lie groups. These filters ensure that the state
estimation error remains invariant under transformations in the Lie group
space. In other words, these filters leverage the symmetry of the system to
achieve a more robust formulation and enhance performance.

One notable consequence of using invariant filters is that if the system
exhibits the group-affine property, the estimation error in the Lie algebra
space follows linear differential equations, and the linearization process
becomes independent of the estimated states. This characteristic of invariant
filters contributes to improved convergence performance.

Hartley et al. [11] applied these invariant filters to effectively combine IMU
equations with forward kinematics for accurate base estimation. Their work
demonstrated that linear differential equations can describe the error
dynamics in the Lie algebra space. Additionally, they highlighted the
advantage that contrary to normal EKF approaches, the linearized system and
update equations become independent of the estimated states. They also
addressed the incorporation of IMU bias and foot positions as state variables
in the filtering equations.

In a related study, Teng et al. [12] utilized a similar invariant filter to
estimate the base in slippery environments. They dynamically adjusted the
noise parameters online and incorporated forward kinematic velocity
measurements in the update step to enhance the estimation accuracy.

Another application of these filters was demonstrated by Ramadoss et al. [13],
who considered the flat feet of a humanoid robot and applied the invariant
filter to the iCub humanoid robot. They also conducted a comparative analysis
of their filter with Rotella’s filter, evaluating their performance in
humanoid base estimation.

The primary objective of this paper is to introduce an approach for base
estimation and localization of the Surena-V humanoid robot by designing an
invariant filter. Notably, this study leverages the Choreonoid simulator [14],
to evaluate the performance of the proposed filter. The utilization of this
simulator provides a realistic and robust platform for validating the
effectiveness of the invariant filter. The results of this filter will be
compared with a Quaternion-based Extended Kalman Filter (QEKF) [4].

In Section II, a concise introduction to Lie group theory will be provided,
followed by a detailed description of the filter equations design. In Section
III, the designed invariant filter will be tested using a Choreonoid
simulation environment. Finally, in Section IV, the paper will be concluded by
summarizing the findings and discussing the implications of the proposed
invariant filter.

##  II Material AND Methods

In this section, we provide a detailed account of the key concepts underlying
the proposed methodology, including an overview of Lie groups and Lie
algebras. Moreover, we delve into the explanation of the Invariant Extended
Kalman Filter (InEKF), elucidating its distinct components and their
respective roles within the designed filter.

###  II-A Overview of Lie Group and Lie Algebra

Lie groups are mathematical groups characterized by their properties as smooth
manifolds. Smooth manifolds, in turn, are topological spaces that possess
differentiable properties at each point and exhibit local linearity.

If ($\boldsymbol{\mathcal{X}}(t)$) represents a point on the Lie group
($\boldsymbol{\mathcal{G}}$), the velocity
($\frac{\partial\boldsymbol{\mathcal{X}}}{\partial t}$) of this point belongs
to the tangent space of ($\boldsymbol{\mathcal{G}}$) at this point
($\mathcal{T}_{\boldsymbol{\mathcal{X}}}\mathcal{G}$). The structure of this
tangent space remains consistent throughout the manifold due to its inherent
smoothness. In particular, the tangent space at the identity element of the
group ($\mathcal{T}_{\boldsymbol{\mathcal{I}}}\mathcal{G}$) corresponds to the
Lie algebra ($\mathfrak{g}$). It is worth noting that each Lie group is
associated with a unique Lie algebra.

In Lie algebra, the elements are represented as skew-symmetric matrices. These
matrices can be transferred to the vector space of ($\mathbb{R}^{m}$) using
the ($.^{\vee}$) operator, which transforms the matrix into a column vector
($m$ is Lie group’s degree of freedom). Similarly, the ($.^{\wedge}$) operator
converts elements from the vector space back to skew-symmetric matrices in the
Lie algebra. To uniquely transform vectors from a Lie algebra
($\boldsymbol{\xi}$) to a Lie group matrix ($\boldsymbol{\mathcal{X}}$), the
exponential transformation is utilized. This transformation maps elements of
the Lie algebra to the corresponding elements of the Lie group. Conversely,
the inverse of the exponential transformation is known as the logarithmic
mapping.

$\displaystyle\text{exp:}\quad\boldsymbol{\mathcal{X}}=exp(\boldsymbol{\xi}^{\wedge})$
(1)
$\displaystyle\text{log:}\quad\boldsymbol{\xi}^{\wedge}=log(\boldsymbol{\mathcal{X}})$
(2)

Lie algebras can be locally defined at other points and subsequently
transformed into a global Lie algebra using the adjoint transformation of the
group.

$Ad_{\boldsymbol{\mathcal{X}}}(\boldsymbol{\xi}^{\wedge})=\boldsymbol{\mathcal{X}}\boldsymbol{\xi}^{\wedge}\boldsymbol{\mathcal{X}}^{-1}\quad
Ad_{\boldsymbol{\mathcal{X}}}:\mathfrak{m}\to\mathfrak{m}$ (3)

Lie groups commonly used in robotics include ($SO(3)$) for three-dimensional
rotations, ($SE(3)$) for combined rotations and translations, and
($SE_{k}(3)$) for extended rigid body transformations with deformations or
kinematic changes. For further insights into this subject matter, please refer
to the relevant resource [15].

###  II-B Invariant Extended Kalman Filter

In this section, we will provide a comprehensive description of our filter,
its equation, and its respective components. Firstly, we will outline the
state variables that form the foundation of our analysis. Secondly, we will
delve into the prediction equations, which integrate the IMU measurements and
foot contact state to forecast the kinematic base state of the humanoid robot.
Lastly, we will elucidate the update equations, which leverage the forward
kinematics of the robot to refine and improve the estimated base state based
on sensor measurements.

####  II-B1 State Variables

In the context of the kinematic base state estimation for humanoid robots, the
state variables encompass several key components. These include the position
($\boldsymbol{p}$), velocity ($\boldsymbol{v}$), and rotation
($\boldsymbol{R}$) of the kinematic base itself. Additionally, the positions
of the left and right foot ($\boldsymbol{p}^{c_{L}}$ and
$\boldsymbol{p}^{c_{R}}$) are also considered as distinct states within the
estimation process. The inclusion of foot states is crucial as it enables the
assessment of their respective errors and their impact on the accuracy of the
base state estimation. The states are defined within the mathematical
framework of $SE_{4}(3)$ as follows:

$\boldsymbol{\mathcal{X}}=\begin{bmatrix}\boldsymbol{R}&\boldsymbol{v}&\boldsymbol{p}&\boldsymbol{p}^{c_{L}}&\boldsymbol{p}^{c_{R}}\\\
\boldsymbol{0}_{1\times 3}&1&0&0&0\\\ \boldsymbol{0}_{1\times 3}&0&1&0&0\\\
\boldsymbol{0}_{1\times 3}&0&0&1&0\\\ \boldsymbol{0}_{1\times
3}&0&0&0&1\end{bmatrix}\in SE_{4}(3)$ (4)

The Lie algebra associated with the states can be expressed as follows:

$\boldsymbol{\xi}^{\wedge}=\begin{bmatrix}(\boldsymbol{\xi}^{R})^{\wedge}&\boldsymbol{\xi}^{v}&\boldsymbol{\xi}^{p}&\boldsymbol{\xi}^{p_{c_{L}}}&\boldsymbol{\xi}^{p_{c_{R}}}\\\
\boldsymbol{0}_{1\times 3}&0&0&0&0\\\ \boldsymbol{0}_{1\times 3}&0&0&0&0\\\
\boldsymbol{0}_{1\times 3}&0&0&0&0\\\ \boldsymbol{0}_{1\times
3}&0&0&0&0\end{bmatrix}$ (5)

In our state representation, we do not incorporate IMU biases due to the
absence of a Lie group that adheres to the group affine property of the system
dynamics [16]. However, it is worth noting that an alternative approach can be
employed by designing an incomplete invariant filter. This filter, while not
fully satisfying the properties of an invariant filter, has been shown to
yield improved results compared to other filters [11]. Consequently, we
introduce the bias states in the following manner:

$\boldsymbol{\theta}=vec(\boldsymbol{b}^{g},\boldsymbol{b}^{a})$ (6)

So the concatenated state representation of the system can be expressed as
$(\boldsymbol{\mathcal{X}},\boldsymbol{\theta})\in\mathcal{G}\times\mathbb{R}^{6}$,
where $\mathcal{G}$ represents the Lie group defined on $SE_{4}(3)$, and
$\mathbb{R}^{6}$ represents the six-dimensional vector space associated with
IMU biases states.

####  II-B2 Prediction Equations

To model the values of the IMU sensor, we employ the following equations:

$\displaystyle\tilde{\boldsymbol{\omega}}=\boldsymbol{\omega}+\boldsymbol{w}^{g}+\boldsymbol{b}^{g}$
(7)
$\displaystyle\tilde{\boldsymbol{a}}=\boldsymbol{a}+\boldsymbol{w}^{a}+\boldsymbol{b}^{a}$
(8)

Here, $\tilde{\boldsymbol{\omega}}$ and $\tilde{\boldsymbol{a}}$ represent the
measured outputs of the IMU sensor, while $\boldsymbol{\omega}$ and
$\boldsymbol{a}$ denote their respective actual values. The terms
$\boldsymbol{w}^{g}$ and $\boldsymbol{w}^{a}$ represent the white noise
components, while $\boldsymbol{b}^{g}$ and $\boldsymbol{b}^{a}$ represent the
biases associated with the gyroscope and accelerometer, respectively. This
particular modeling approach has been widely utilized in previous studies. The
prediction step of this filter can be formulated by the following equations:

$\displaystyle\dot{\boldsymbol{R}}=\boldsymbol{R}(\tilde{\boldsymbol{\omega}}-\boldsymbol{b}^{g}-\boldsymbol{w}^{g})^{\wedge}=\boldsymbol{R}(\bar{\boldsymbol{\omega}}-\boldsymbol{w}^{g})^{\wedge}$
(9)
$\displaystyle\dot{\boldsymbol{v}}=\boldsymbol{a}=\boldsymbol{R}(\tilde{\boldsymbol{a}}-\boldsymbol{b}^{a}-\boldsymbol{w}^{a})+\boldsymbol{g}=\boldsymbol{R}(\bar{\boldsymbol{a}}-\boldsymbol{w}^{a})+\boldsymbol{g}$
(10) $\displaystyle\dot{\boldsymbol{p}}=\boldsymbol{v}$ (11)
$\displaystyle\dot{\boldsymbol{p}}^{c_{i}}=\boldsymbol{R}\boldsymbol{R}_{fk}^{c_{i}}(-\boldsymbol{w}^{c_{i}}),\quad
i={L,R}$ (12) $\displaystyle\dot{\boldsymbol{b}}^{g}=\boldsymbol{w}^{bg}$ (13)
$\displaystyle\dot{\boldsymbol{b}}^{a}=\boldsymbol{w}^{ba}$ (14)

In equation (9), to derive the difference equation of rotation, we follow a
similar approach as outlined in research [7]. The operator $()^{\wedge}$
denotes the skew-symmetric matrix operator. In equation (10), we initially
perform a coordinate frame transformation from the IMU coordinate frame to the
global coordinate frame. Subsequently, we eliminate the gravity vector
($\boldsymbol{g}$) from the transformed equation. In equation (12), we model
the dynamics of the contact foot using a Brownian model, incorporating a noise
vector represented by $\boldsymbol{w}^{c_{i}}$. The term
$\boldsymbol{R}_{fk}^{c_{i}}$ denotes the rotation matrix that describes the
orientation of the foot relative to the base. Equations (13) and (14) describe
the modeling of IMU biases as a Brownian motion process, incorporating noise
vectors represented by $\boldsymbol{w}^{bg}$ and $\boldsymbol{w}^{ba}$,
respectively.

To implement these equations, it is necessary to employ the deterministic and
discrete forms of the equations. For the discretization of the equations, we
adopt the analytical integration technique, which has been employed in prior
research studies such as [11, 17, 7].

One of the key distinctions of the Invariant Extended Kalman Filter (InEKF)
lies in the method used to define the error for state variables. In this
filter, the error for the first part of the states is defined as the right
invariant error on a Lie group. The inverse of our states group can be
expressed as follows:

$\boldsymbol{\mathcal{X}}^{-1}=\begin{bmatrix}\boldsymbol{R}^{T}&-\boldsymbol{R}^{T}\boldsymbol{v}&-\boldsymbol{R}^{T}\boldsymbol{p}&-\boldsymbol{R}^{T}\boldsymbol{p}^{c_{L}}&-\boldsymbol{R}^{T}\boldsymbol{p}^{c_{R}}\\\
\boldsymbol{0}_{4\times 3}&&&\boldsymbol{I}_{4\times 4}\end{bmatrix}$ (15)

so the error is as follows:

$\begin{gathered}\boldsymbol{\eta}=exp(\boldsymbol{\xi}^{\wedge})=\bar{\boldsymbol{\mathcal{X}}}\boldsymbol{\mathcal{X}}^{-1}=\\\
\begin{bmatrix}\bar{\boldsymbol{R}}\boldsymbol{R}^{T}&\bar{\boldsymbol{v}}-\bar{\boldsymbol{R}}\boldsymbol{R}^{T}\boldsymbol{v}&\bar{\boldsymbol{p}}-\bar{\boldsymbol{R}}\boldsymbol{R}^{T}\boldsymbol{p}&\bar{\boldsymbol{p}}^{c_{L}}-\bar{\boldsymbol{R}}\boldsymbol{R}^{T}\boldsymbol{p}^{c_{L}}&\bar{\boldsymbol{p}}^{c_{R}}-\bar{\boldsymbol{R}}\boldsymbol{R}^{T}\boldsymbol{p}^{c_{R}}\\\
\boldsymbol{0}_{4\times 3}&&&\boldsymbol{I}_{4\times
4}\end{bmatrix}\end{gathered}$

(16)

With the inclusion of bias states, the concatenated error can be expressed as
follows:

$\boldsymbol{e}=(\boldsymbol{\eta},\boldsymbol{\zeta})=(\bar{\boldsymbol{\mathcal{X}}}\boldsymbol{\mathcal{X}}^{-1},\bar{\boldsymbol{\theta}}-\boldsymbol{\theta})$
(17)

(a) X-direction position (b) Y-direction position (c) Yaw angle

Figure 2: Comparison of the output from both filters with the ground truth

Figure 3: Comparison of convergence for QEKF and RIEKF filters in the presence
of noisy initial conditions of the states

To propagate the covariance in the prediction step, it is necessary to derive
the error dynamics by differentiating equation (17). We refer to reference
[11] to obtain the differentiation of the elements in equation (16).

$\begin{matrix}\frac{d}{dt}(\bar{\boldsymbol{R}}\boldsymbol{R}^{T})\approx(\boldsymbol{R}(\boldsymbol{w}^{g}-\boldsymbol{\zeta}^{g}))^{\wedge}\\\
\frac{d}{dt}(\bar{\boldsymbol{v}}-\bar{\boldsymbol{R}}\boldsymbol{R}^{T}\boldsymbol{v})\approx\boldsymbol{g}^{\wedge}\boldsymbol{\xi}^{R}+\boldsymbol{v}^{\wedge}\boldsymbol{R}(\boldsymbol{w}^{g}-\boldsymbol{\zeta}^{g})+\boldsymbol{R}(\boldsymbol{w}^{a}-\boldsymbol{\zeta}^{a})\\\
\frac{d}{dt}(\bar{\boldsymbol{p}}-\bar{\boldsymbol{R}}\boldsymbol{R}^{T}\boldsymbol{p})\approx\boldsymbol{\xi}^{v}+\bar{\boldsymbol{p}}^{\wedge}\boldsymbol{R}(\boldsymbol{w}^{g}-\boldsymbol{\zeta}^{g})\\\
\frac{d}{dt}(\bar{\boldsymbol{p}^{c_{i}}}-\bar{\boldsymbol{R}}\boldsymbol{R}^{T}\boldsymbol{p}^{c_{i}})\approx(\bar{\boldsymbol{p}^{c_{i}}})^{\wedge}\bar{\boldsymbol{R}}(\boldsymbol{w}^{g}-\boldsymbol{\zeta}^{g})+\boldsymbol{R}\boldsymbol{R}_{fk}^{c_{i}}\boldsymbol{w}^{c_{i}}\end{matrix}$
(18)

By assuming that $\boldsymbol{\eta}=exp(\boldsymbol{\xi}^{\wedge})$ can be
approximated as $\boldsymbol{I}+\boldsymbol{\xi}^{\wedge}$, we can linearize
the equation. Taking into account the bias terms, the resulting linearized
equation will be:

$\frac{d}{dt}\begin{bmatrix}\boldsymbol{\xi}\\\
\boldsymbol{\zeta}\end{bmatrix}=\boldsymbol{F}\begin{bmatrix}\boldsymbol{\xi}\\\
\boldsymbol{\zeta}\end{bmatrix}+\begin{bmatrix}Ad_{\bar{\boldsymbol{\mathcal{X}}}}&\boldsymbol{0}_{15\times
6}\\\ \boldsymbol{0}_{6\times 15}&\boldsymbol{I}_{6\times
6}\end{bmatrix}\boldsymbol{w}$ (19)

In this equation, $\boldsymbol{F}$ and $\boldsymbol{w}$ are:

$\begin{matrix}\boldsymbol{F}=\begin{bmatrix}\boldsymbol{0}_{3\times
3}&\boldsymbol{0}_{3\times 3}&\boldsymbol{0}_{3\times
3}&\boldsymbol{0}_{3\times 3}&\boldsymbol{0}_{3\times
3}&-\bar{\boldsymbol{R}}&\boldsymbol{0}_{3\times 3}\\\
\boldsymbol{g}^{\wedge}&\boldsymbol{0}_{3\times 3}&\boldsymbol{0}_{3\times
3}&\boldsymbol{0}_{3\times 3}&\boldsymbol{0}_{3\times
3}&-\bar{\boldsymbol{v}}^{\wedge}\bar{\boldsymbol{R}}&-\bar{\boldsymbol{R}}\\\
\boldsymbol{0}_{3\times 3}&\boldsymbol{I}_{3\times 1}&\boldsymbol{0}_{3\times
3}&\boldsymbol{0}_{3\times 3}&\boldsymbol{0}_{3\times
3}&-\bar{\boldsymbol{p}}^{\wedge}\bar{\boldsymbol{R}}&\boldsymbol{0}_{3\times
3}\\\ \boldsymbol{0}_{3\times 3}&\boldsymbol{0}_{3\times
3}&\boldsymbol{0}_{3\times 3}&\boldsymbol{0}_{3\times
3}&\boldsymbol{0}_{3\times
3}&-(\bar{\boldsymbol{p}}^{c_{L}})^{\wedge}\bar{\boldsymbol{R}}&\boldsymbol{0}_{3\times
3}\\\ \boldsymbol{0}_{3\times 3}&\boldsymbol{0}_{3\times
3}0&\boldsymbol{0}_{3\times 3}&\boldsymbol{0}_{3\times
3}&\boldsymbol{0}_{3\times
3}&-(\bar{\boldsymbol{p}}^{c_{R}})^{\wedge}\bar{\boldsymbol{R}}&\boldsymbol{0}_{3\times
3}\\\ &&&\boldsymbol{0}_{6\times 7}&&&\end{bmatrix}\\\ \\\
\boldsymbol{w}=vec(\boldsymbol{w}^{g},\boldsymbol{w}^{a},\boldsymbol{0}_{3\times
1},\boldsymbol{R}_{fk}^{c_{L}}\boldsymbol{w}^{c_{L}},\boldsymbol{R}_{fk}^{c_{R}}\boldsymbol{w}^{c_{R}},\boldsymbol{w}^{bg},\boldsymbol{w}^{ba})\end{matrix}$

As evident in F, only the elements corresponding to noise and bias are
dependent on the estimated variables. Hence, in a system without considering
biases, the error would be independent of the estimated states. According to
equation (19), the noise covariance matrix in continuous space can be
represented as follows:

$\boldsymbol{Q}_{c}=\begin{bmatrix}Ad_{\bar{\boldsymbol{\mathcal{X}}}}&\boldsymbol{0}_{15\times
6}\\\ \boldsymbol{0}_{6\times 15}&\boldsymbol{I}_{6\times
6}\end{bmatrix}Cov(\boldsymbol{w})\begin{bmatrix}Ad_{\bar{\boldsymbol{\mathcal{X}}}}&\boldsymbol{0}_{15\times
6}\\\ \boldsymbol{0}_{6\times 15}&\boldsymbol{I}_{6\times 6}\end{bmatrix}^{T}$
(20)

Regarding $Cov(\boldsymbol{w})$, we have the following expression:

$Cov(\boldsymbol{w})=blkdiag(\boldsymbol{Q}^{g},\boldsymbol{Q}^{a},\boldsymbol{0}_{3\times
3},\boldsymbol{Q}^{c_{L}},\boldsymbol{Q}^{c_{R}},\boldsymbol{Q}^{bg},\boldsymbol{Q}^{ba})$
(21)

The operator blkdiag(.) represents the formation of a block diagonal matrix.
The matrices $\boldsymbol{Q}^{g},\boldsymbol{Q}^{a},\boldsymbol{Q}^{bg}$, and
$\boldsymbol{Q}^{ba}$ can be understood as block diagonal matrices with
elements representing the square of the standard deviations of the noise in
angular velocity, linear acceleration, angular velocity bias, and linear
acceleration bias, respectively. Regarding $\boldsymbol{Q}^{c_{i}}$, it is
important to note that when one of the robot’s legs is not in contact with the
ground, its prediction equation is temporarily eliminated. During this state,
the noise covariance associated with that leg is assigned a high value to
increase uncertainty. Once the leg returns to contact with the ground, this
value is decreased.

$\boldsymbol{Q}^{c_{i}}=\boldsymbol{R}_{fk}^{c_{i}}(\boldsymbol{Q}^{c}_{i}+(1-contact(c_{i}))\times
10^{5})(\boldsymbol{R}_{fk}^{c_{i}})^{T},i=L,R$ (22)

The covariance matrix $\boldsymbol{Q}^{c}_{i}$ represents the noise covariance
associated with the contact foot. The function $contact(.)$ is used to
determine whether the foot is in contact with the ground or not.

Once $\boldsymbol{F}$ and $\boldsymbol{Q}_{c}$ are determined, they need to be
discretized. To achieve this, we employ the following approximations:

$\displaystyle{\boldsymbol{F}}_{k}=exp(\boldsymbol{F}\Delta
t)=\boldsymbol{I}+\boldsymbol{F}\Delta t$ (23)
$\displaystyle\boldsymbol{Q}_{k}={\boldsymbol{F}}_{k}\boldsymbol{Q}_{c}{\boldsymbol{F}}_{k}^{T}\Delta
t$ (24)

After obtaining the discretized matrices, we can proceed to propagate the
covariance of states using the following equation:

${\boldsymbol{P}}_{k+1|k}=\boldsymbol{F}_{k}\boldsymbol{P}_{k|k}\boldsymbol{F}_{k}^{T}+\boldsymbol{Q}_{k}$
(25)

####  II-B3 Update Equations

In the update step, we will utilize the forward kinematics equations of the
robot. The primary equation can be expressed as follows:

$_{B}{}\boldsymbol{p}^{c_{i}}=\boldsymbol{R}^{T}(\boldsymbol{p}^{c_{i}}-\boldsymbol{p})+\boldsymbol{w}^{c_{i}}$
(26)

To leverage the outcomes of the InEKF, we express this equation in the form of
right invariant observations
($\boldsymbol{Y}=\boldsymbol{\mathcal{X}}^{-1}\boldsymbol{b}+\boldsymbol{V}$),
as suggested in reference [16]:

$\underbrace{\begin{bmatrix}{}_{B}{}\boldsymbol{p}^{c_{i}}\\\ 0\\\ 1\\\ -1\\\
0\end{bmatrix}}_{\boldsymbol{Y}}=\underbrace{\begin{bmatrix}\boldsymbol{R}^{T}&-\boldsymbol{R}^{T}\boldsymbol{v}&-\boldsymbol{R}^{T}\boldsymbol{p}&-\boldsymbol{R}^{T}\boldsymbol{p}^{c_{L}}&-\boldsymbol{R}^{T}\boldsymbol{p}^{c_{R}}\\\
\boldsymbol{0}_{4\times 3}&&&\boldsymbol{I}_{4\times
4}\end{bmatrix}}_{{\boldsymbol{\mathcal{X}}^{-1}}}\underbrace{\begin{bmatrix}\boldsymbol{0}_{3\times
1}\\\ 0\\\ 1\\\ -1\\\
0\end{bmatrix}}_{{\boldsymbol{b}}}+\underbrace{\begin{bmatrix}\boldsymbol{w}^{c_{i}}\\\
0\\\ 0\\\ 0\\\ 0\end{bmatrix}}_{{\boldsymbol{V}}}$

(27)

therefore, the update equations for states can be formulated as follows:

$\hat{\boldsymbol{\mathcal{X}}}=exp(\boldsymbol{L}(\bar{\boldsymbol{\mathcal{X}}}\boldsymbol{Y}-\boldsymbol{b}))\bar{\boldsymbol{\mathcal{X}}}$
(28)

In this equation, $\boldsymbol{L}$ represents the gain matrix,
$\hat{\boldsymbol{\mathcal{X}}}$ is updated states and
$\bar{\boldsymbol{\mathcal{X}}}\boldsymbol{Y}-\boldsymbol{b}$ denotes the
innovation term. The update equation for the right invariant error can be
expressed as follows:

$\hat{\boldsymbol{\eta}}=\hat{\boldsymbol{\mathcal{X}}}\boldsymbol{\mathcal{X}}^{-1}=exp(\boldsymbol{L}(\boldsymbol{\eta}\boldsymbol{b}-\boldsymbol{b}+\bar{\boldsymbol{\mathcal{X}}}\boldsymbol{V}))\boldsymbol{\eta}$
(29)

Upon careful examination of the equation (28), it can be observed that the
first four rows of $\boldsymbol{b}$ are zero. By computing the subsequent four
rows of $\bar{\boldsymbol{\mathcal{X}}}\boldsymbol{Y}-\boldsymbol{b}$, it can
be deduced that they will also be zero. Hence, it is possible to utilize a
reduced-order gain and a selector matrix, denoted as $\boldsymbol{K}$, and
$\boldsymbol{\Pi}=blkdiag(\boldsymbol{I}_{3\times 3},\boldsymbol{0}_{3\times
4})$, and rewrite equation as follows:

$\begin{matrix}\hat{\boldsymbol{\mathcal{X}}}=exp(\boldsymbol{K}\boldsymbol{\Pi}\bar{\boldsymbol{\mathcal{X}}}\boldsymbol{Y})\bar{\boldsymbol{\mathcal{X}}}\end{matrix}$
(30)

To update the covariance matrix of states, we need to linearize equation (29)
using the approximation
$\boldsymbol{\eta}=exp(\boldsymbol{\xi}^{\wedge})=\boldsymbol{I}+\boldsymbol{\xi}^{\wedge}$.
This linearization process yields the following result, as described in
reference [11]:

$\hat{\boldsymbol{\xi}}=\boldsymbol{\xi}-\boldsymbol{K}(\boldsymbol{H}^{c_{i}}\boldsymbol{\xi}-\bar{\boldsymbol{R}}\boldsymbol{w}^{c_{i}})$
(31)

In this equation, the H matrix for the left and right leg can be represented
as follows:

$\begin{matrix}\boldsymbol{H}^{c_{L}}=\begin{bmatrix}\boldsymbol{0}_{3\times
3}&\boldsymbol{0}_{3\times 3}&-\boldsymbol{I}_{3\times
3}&\boldsymbol{I}_{3\times 3}&\boldsymbol{0}_{3\times 3}\end{bmatrix}\\\
\boldsymbol{H}^{c_{R}}=\begin{bmatrix}\boldsymbol{0}_{3\times
3}&\boldsymbol{0}_{3\times 3}&-\boldsymbol{I}_{3\times
3}&\boldsymbol{0}_{3\times 3}&\boldsymbol{I}_{3\times
3}\end{bmatrix}\end{matrix}$ (32)

Now, following the standard Kalman filter approach, we can update the
covariance matrix using the following equations:

$\begin{matrix}\boldsymbol{N}=\boldsymbol{R}Cov(\boldsymbol{w}^{c_{i}})\boldsymbol{R}^{T}\\\
\boldsymbol{S}=\boldsymbol{H}^{c_{i}}\boldsymbol{P}(\boldsymbol{H}^{c_{i}})^{T}+\boldsymbol{N}\\\
\boldsymbol{K}=\boldsymbol{P}(\boldsymbol{H}^{c_{i}})^{T}\boldsymbol{S}^{-1}\\\
\boldsymbol{P}_{k+1|k+1}=(\boldsymbol{I}-\boldsymbol{K}\boldsymbol{H}^{c_{i}})\boldsymbol{P}(\boldsymbol{I}-\boldsymbol{K}\boldsymbol{H}^{c_{i}})^{T}+\boldsymbol{K}\boldsymbol{N}\boldsymbol{K}^{T}\end{matrix}$
(33)

These equations are independent of IMU biases. When considering IMU biases, we
include two 3x3 zero matrices at the end of the matrix H. Additionally, when
both of the robot’s feet are in contact with the ground, we employ the
following concatenated matrices for them:

$\begin{matrix}\boldsymbol{Y}=\begin{bmatrix}\boldsymbol{Y}^{L}\\\
\boldsymbol{Y}^{R}\end{bmatrix},\boldsymbol{b}=\begin{bmatrix}\boldsymbol{b}^{L}\\\
\boldsymbol{b}^{R}\end{bmatrix},\begin{bmatrix}\boldsymbol{H}^{L}\\\
\boldsymbol{H}^{R}\end{bmatrix},\\\
\boldsymbol{N}=blkdiag(\boldsymbol{N}^{L},\boldsymbol{N}^{R}),\boldsymbol{\Pi}=blkdiag(\boldsymbol{\Pi},\boldsymbol{\Pi}),\bar{\boldsymbol{\mathcal{X}}}=blkdiag(\bar{\boldsymbol{\mathcal{X}}},\bar{\boldsymbol{\mathcal{X}}})\end{matrix}$

(34)

##  III Simulations and Results

In this section, a comparative analysis will be conducted between the results
obtained from the right invariant filter and the quaternion-based filter [4].

###  III-A System Overview

For the simulation of the designed filters, we employed the Choreonoid dynamic
simulator (Figure 1), coupled with ROS to extract data from the simulation for
the filters. This simulator has been widely utilized for dynamic simulations
of humanoid robots [18, 19]. In our study, we utilized the lower limb model of
the SURENA V robot, which is equipped with an IMU sensor on its base.
Additionally, the robot’s joints are equipped with encoders, allowing us to
determine the forward kinematics of the robot based on its geometric
properties. Contact detection was performed by leveraging the trajectory
planning data of the robot.

The robot executed turning movements with a step length of 17 cm and an angle
of 0.15 radians. Each step time was 1 second, with a double support phase of
0.1 seconds (equivalent to a speed of 0.61 km/h). The trajectory planning for
the walking motion in this study is based on the research presented in
reference [20]. The robot’s control system operated at a frequency of 500 Hz.
To enhance realism, Gaussian noise was introduced to the output of the IMU and
forward kinematics. The standard deviations of these noise sources are
presented in Table I.

TABLE I: Standard Deviations of Noise Added to the Simulation Data Parameter | Value
---|---
angular velocity | $0.05\frac{rad}{s}$
linear acceleration | $0.015\frac{m}{s^{2}}$
forward kinematics | $0.002m$
TABLE II: Standard Deviations of Sensor Noise and Initial States Noise for Both Filters Incorporated in the Filtering Equations Sensor Parameter | Value | Initial State Parameter | Value
---|---|---|---
angular velocity | $0.05\frac{rad}{s}$ | orientation | $0.1rad$
linear acceleration | $0.08\frac{m}{s^{2}}$ | velocity | $0.15\frac{m}{s}$
angular velocity bias | $0.001\frac{rad}{s^{2}}$ | position | $0.1m$
linear acceleration bias | $0.001\frac{m}{s^{3}}$ | feet position | $0.1m$
forward kinematic | $0.05m$ | angular velocity bias | $0.2\frac{rad}{s}$
contact foot velocity | $0.1\frac{m}{s}$ | linear acceleration bias | $0.2\frac{m}{s^{2}}$

Figure 4: Distribution of mean squared error (MSE) for different observable
states

###  III-B Evaluation of Localization

During the robot’s walking, both filters were employed to estimate the
kinematic base states. The standard deviations listed in Table II were used to
represent the uncertainty in the initial state and sensor noises in the
formulas of both filters. As highlighted in previous studies [11, 4],
accurately estimating the base position and yaw angle poses challenges in
terms of observability. In this study, we specifically examine the estimation
of these states during walking. Figure 2 presents the results of the estimated
values obtained from our approach, compared against the ground truth values
derived from simulation computations. The comparison reveals that the RIEKF
exhibits less drift than the QEKF along the robot’s path, as evident from the
results. Additionally, the mean squared error of the estimated states was
computed by comparing them with the ground truth data, as presented in Table
III.

TABLE III: Mean Square Error of $p_{x}$, $p_{y}$ and $yaw$ for QEKF and RIEKF methods Filter | $p_{x}(m)$ | $p_{y}(m)$ | $yaw(rad)$
---|---|---|---
RIEKF | 0.0000097 | 0.0006052 | 0.0002286
QEKF | 0.0002555 | 0.0014 | 0.0012

###  III-C Evaluation of Convergence

In order to evaluate the convergence time of the two filters for observable
states, a series of experiments was conducted. The states were randomly
initialized 100 times from a normal distribution, with a standard deviation
corresponding to the values reported in Table II. Subsequently, the filters
were executed using these initial conditions, and the resulting outputs were
visualized in Figure 3. The figures clearly demonstrate that the RIEKF filter
consistently achieves convergence earlier than the QEKF filter.

Additionally, the mean squared error was calculated between the filter results
and the ground truth obtained from the simulation for the 100 conducted tests,
and their distribution was analyzed. The distribution of these MSE values is
illustrated in Figure 4 using a violin plot. It is noteworthy that the RIEKF
filter consistently exhibits lower MSE values compared to the QEKF filter for
all states.

##  IV Conclusion

In this research, we developed a Right Invariant Extended Kalman Filter
(RIEKF) for performing base state estimation in a humanoid robot. The states
of the filter were defined on a Lie group $SE_{4}(3)$. We used IMU equations
for the prediction step and forward kinematics for the update step. To
validate the performance of the RIEKF, we conducted a comparative analysis
with a Quaternion-based Extended Kalman Filter (QEKF) using the Choreonoid
dynamic simulation platform. The results demonstrated that the RIEKF
outperformed the QEKF in terms of reduced drift for unobservable states and
faster convergence time for observable states. The findings of this research
highlight the effectiveness of the RIEKF in improving base state estimation
for humanoid robots.

Looking ahead, future work will focus on incorporating visual filters to
complement the RIEKF and further improve state estimation accuracy. By
combining the RIEKF with visual-based filters, we aim to reduce drift over
longer periods of time, enhancing the overall robustness and reliability of
the state estimation system in humanoid robotics applications.

## References

  * [1] K. Masuya and K. Ayusawa, “A review of state estimation of humanoid robot targeting the center of mass, base kinematics, and external wrench,” _Advanced Robotics_ , vol. 34, no. 21-22, pp. 1380–1389, 2020.
  * [2] H. Jeong, I. Lee, J. Oh, K. K. Lee, and J.-H. Oh, “A robust walking controller based on online optimization of ankle, hip, and stepping strategies,” _IEEE Transactions on Robotics_ , vol. 35, no. 6, pp. 1367–1386, 2019.
  * [3] P. Abdolahnezhad, A. Yousefi-Koma, A. Vedadi, K. Sinaei, B. Maleki, and M. Shafiee, “Online bipedal locomotion adaptation for stepping on obstacles using a novel foot sensor,” in _2022 IEEE-RAS 21st International Conference on Humanoid Robots (Humanoids)_. IEEE, 2022, pp. 344–349.
  * [4] M. Bloesch, M. Hutter, M. A. Hoepflinger, S. Leutenegger, C. Gehring, C. D. Remy, and R. Siegwart, “State estimation for legged robots-consistent fusion of leg kinematics and imu,” _Robotics_ , vol. 17, pp. 17–24, 2013.
  * [5] N. Rotella, M. Blösch, L. Righetti, and S. Schaal, “State estimation for a humanoid robot,” _CoRR_ , vol. abs/1402.5450, 2014. [Online]. Available: http://arxiv.org/abs/1402.5450
  * [6] M. F. Fallon, M. Antone, N. Roy, and S. Teller, “Drift-free humanoid state estimation fusing kinematic, inertial and lidar sensing,” in _2014 IEEE-RAS International Conference on Humanoid Robots_. IEEE, 2014, pp. 112–119.
  * [7] J. Sola, “Quaternion kinematics for the error-state kalman filter,” _arXiv preprint arXiv:1711.02508_ , 2017.
  * [8] G. Bourmaud, R. Mégret, M. Arnaudon, and A. Giremus, “Continuous-discrete extended kalman filter on matrix lie groups using concentrated gaussian distributions,” _Journal of Mathematical Imaging and Vision_ , vol. 51, no. 1, pp. 209–228, 2015.
  * [9] S. Bonnabel and P. Rouchon, “On invariant observers,” in _Control and observer design for nonlinear finite and infinite dimensional systems_. Springer, 2005, pp. 53–65.
  * [10] A. Barrau and S. Bonnabel, “The invariant extended kalman filter as a stable observer,” _IEEE Transactions on Automatic Control_ , vol. 62, no. 4, pp. 1797–1812, 2016.
  * [11] R. Hartley, M. Ghaffari, R. M. Eustice, and J. W. Grizzle, “Contact-aided invariant extended kalman filtering for robot state estimation,” _The International Journal of Robotics Research_ , vol. 39, no. 4, pp. 402–430, 2020\.
  * [12] S. Teng, M. W. Mueller, and K. Sreenath, “Legged robot state estimation in slippery environments using invariant extended kalman filter with velocity update,” in _2021 IEEE International Conference on Robotics and Automation (ICRA)_. IEEE, 2021, pp. 3104–3110.
  * [13] P. Ramadoss, G. Romualdi, S. Dafarra, F. J. A. Chavez, S. Traversaro, and D. Pucci, “Diligent-kio: A proprioceptive base estimator for humanoid robots using extended kalman filtering on matrix lie groups,” in _2021 IEEE International Conference on Robotics and Automation (ICRA)_. IEEE, 2021, pp. 2904–2910.
  * [14] S. Nakaoka, “Choreonoid: Extensible virtual robot environment built on an integrated gui framework,” in _2012 IEEE/SICE International Symposium on System Integration (SII)_. IEEE, 2012, pp. 79–85.
  * [15] J. Sola, J. Deray, and D. Atchuthan, “A micro lie theory for state estimation in robotics,” _arXiv preprint arXiv:1812.01537_ , 2018.
  * [16] A. Barrau, “Non-linear state error based extended kalman filters with applications to navigation,” Ph.D. dissertation, Mines Paristech, 2015.
  * [17] K. Eckenhoff, P. Geneva, and G. Huang, “Direct visual-inertial navigation with analytical preintegration,” in _2017 IEEE International Conference on Robotics and Automation (ICRA)_. IEEE, 2017, pp. 1429–1435.
  * [18] H. Jeong, I. Lee, O. Sim, K. Lee, and J.-H. Oh, “A robust walking controller optimizing step position and step time that exploit advantages of footed robot,” _Robotics and Autonomous Systems_ , vol. 113, pp. 10–22, 2019.
  * [19] S. Caron, A. Kheddar, and O. Tempier, “Stair climbing stabilization of the hrp-4 humanoid robot using whole-body admittance control,” in _2019 International conference on robotics and automation (ICRA)_. IEEE, 2019, pp. 277–283.
  * [20] A. Vedadi, K. Sinaei, P. Abdolahnezhad, S. S. Aboumasoudi, and A. Yousefi-Koma, “Bipedal locomotion optimization by exploitation of the full dynamics in dcm trajectory planning,” in _2021 9th RSI International Conference on Robotics and Mechatronics (ICRoM)_. IEEE, 2021, pp. 365–370.


# Long-Term Planning with Deep Reinforcement Learning on Autonomous Drones

Ugurkan Ates
Department of Computer Science
Gebze Technical University
Istanbul, Turkey
<EMAIL_ADDRESS>
Evaluation run test video can be seen at YouTube

###### Abstract

In this paper, we study a long-term planning scenario that is based on drone
racing competitions held in real life. We conducted this experiment on a
framework created for "Game of Drones: Drone Racing Competition" at NeurIPS
2019. The racing environment was created using Microsoft’s AirSim Drone Racing
Lab. A reinforcement learning agent, a simulated quadrotor in our case, has
trained with the Policy Proximal Optimization(PPO) algorithm was able to
successfully compete against another simulated quadrotor that was running a
classical path planning algorithm. Agent observations consist of data from IMU
sensors, GPS coordinates of drone obtained through simulation and opponent
drone GPS information. Using opponent drone GPS information during training
helps dealing with complex state spaces, serving as expert guidance allows for
efficient and stable training process. All experiments performed in this paper
can be found and reproduced with code at our GitHub repository

_Keywords_ Deep Reinforcement Learning $\cdot$ Path Planning $\cdot$ Machine
Learning $\cdot$ Drone Racing

##  1 Introduction

_Deep Learning_ methods are replacing traditional software methods in solving
real-world problems. Cheap and easily available computational power combined
with labeled big datasets enabled deep learning algorithms to show their full
potential. AlexNet paper(2012; Krizhevsky et al.[9]) showed feeding sufficient
data into deep neural networks successfully learned to extract representations
better than handcrafted features which let the start an era known as the rise
of Deep Learning. Their great success in solving otherwise hard engineering
problems such as _object detection , voice recognition, chatbots, robotic
manipulation and autonomous systems_ shown they can be applied to various
fields thanks to their generalisation capability.[16]

Path Planning(Motion Planning) is defined as computing a continuous path from
starting position S to destination position D while avoiding any known
obstacles in the way.[20] Whether it is in 2D or 3D geometry, any robotic
system then will able to follow the computed path to reach it’s destination.
Real World robotic systems tend to use more explainable and reproducible
algorithms based on interval based search ( A star or Dijkstra) or sampling-
based algorithms. We wanted to show a reward based algorithm that depends on
Markov Decision Process(MDP) by trying to maximize cumulative future rewards
can also complete long term path planning tasks. Advantage of using this
option will allow autonomous robot(in our case simulated quadrotor) to create
paths in non holonomic constraints which is something current methods fails to
achieve.[1][17]

Deep reinforcement learning (RL) has been demonstrated to effectively learn a
wide range of reward driven skills, including playing games (Mnih et al.,
2013)[13], controlling robots (2017; Schulman et al., 2015b)[15] and
navigating complex environments (Lei et al., 2017).[10]

Figure 1: An overview of simulated racing track.

We wanted to show an autonomous quadrotor acting as an agent in a fully known
MDP can successfully learn to plan the optimized path on simulated drone
racing track. Our agent was trained with PPO a very well-known once state of
art continuous control algorithm that is still used due ease to implement and
reproducible with few hyperparameters possible compared to other complex
algorithms.

Our result shows after a fully trained agent could easily gain the ability to
plan a long term planning scenario within a simulated racing track which
consists passing ten of checkpoints. We also deployed our trained agent into
similar conditions and it was able to generalize its path planning skills
efficiently.

This shows promising results in the usage of drones in path planning scenarios
as well as the deployment of these trained policies into real life. Our sensor
data is highly configurable and one can replace simulated sensors with actual
sensor data. With proper calibration, trained policies can be deployed into
real life systems.

##  2 Preliminaries

##### Machine Learning

Machine Learning is in most basic form can be described as acquiring domain
knowledge with a large number of examples of the desired objective.

These examples are called training set and fed into a learning algorithm of
interest. Evaluated on test data they show the success rate of the training
process. Learning algorithms try to maximize the success rate to reduce the
disparity between predictions and actual outputs.[16][13]

##### Reinforcement Learning

Reinforcement Learning is in the middle of supervised and unsupervised
learning. Unlike unsupervised learning methods we have some form guidance
supervision system but this doesn’t affect the output of our desired output
predictions instead, it acts like a feedback signal that tries to steer our
policy to an optimal one, improving with each update to collect maximum
cumulative reward.[7]

##### Deep Reinforcement Learning

Deep Reinforcement Learning (DRL) has achieved great success on sequential
task problems involving high dimensional sensory inputs such as RGB images or
actual physical sensor data on real life robotic systems. Working on with
highly dimensional input data there is some feature extraction layer that
extracts using neural networks. These abstracted features then later used on
to approximate Q value. Deep Q Networks (DQN) update policy regarding to
Bellman expectation equation which includes an approximation of Q(state,
action) with a neural network. Another approach is the directly optimizing
policy which results in Policy Gradient methods. These methods result in more
stable training but they fail to generalize into any complex problem.

Both critic and value use separate neural networks during training, Critic is
updated with loss regarding bellman expectation function just like DQN, while
critic updates with gradient ascent to maximize its policy to take actions
that resulted in good rewards.

PPO is an advantage based actor-critic algorithm that tries to be conservative
with policy updates. Using KL divergence and clipped surrogate function it can
update multiple steps of update in one trajectory without worrying about
policy fluctuating wildly[15]. TRPO another similar algorithm does this by
enforcing a hard trust-region constraint which solved with second-order
methods. PPO does this by with first-order optimization its clipped objective.
[6][7]

##### Path Planning

The motion planning problem is often related to the subtask graph execution
problem. Problem is often mapped to a graph and thus becoming a graph search
problem. The key concept behind the problem is to solve finding an optimal
path toward the target while avoiding obstacles in the way.[20][3]

##  3 Related Work

##### Hierarchical Reinforcement Learning

In recent years Hierarchical Reinforcement Learning (HRL) has started to show
promising results, solving long horizon problems on environments with sparse
or delayed rewards. We could classify these algorithms into two type. First
algorithm type focuses on high level policies ability to choose low level
actions which they are called selector methods Second type of algorithms
rather focuses on determining high level policies from low-level policies
which are called subgoal based methods.

Both algorithm type can show enable transfer within different environments and
can solve diverse tasks. Selector algorithms mostly

Selector methods enable convenient skill transferring and can solve diverse
tasks. They often require training of high-level and low-level policies within
different environments, where the low-level skills are pre-trained either by
proxy reward , by maximizing diversity , or in designed simple tasks.[11][21]

Subgoal-based methods are designed to solve sparse reward problems. A distance
measure is required in order for low-level policies to receive internal
rewards according to its current state and the subgoal. Many algorithms simply
use Euclidean distance [8, 9] or cosine-distance as measurements.[18]

##### Multi Task Reinforcement Learning

Multi-Task Learning (MTL) tries a more general approach when dealing with a
problem with multiple sub-tasks. Instead, it uses leveraging the power of
Machine Learning to generalize upon each task given properly chosen
hyperparameters and given enough training time it learns other subtasks. This
method also increases the learning capacity of each subtask at once and
improves the ability to learn several tasks. This is mostly achieved due to
similarities of subtasks that could be learned from features extracted in
hidden layers could be more efficiently exploited to learn other tasks and by
a general representation of each subtask to learn.[19]

Multi-Task RL(MTRL) methods could pass these efficiency improvements made in
the Deep Learning domain to the RL domain by allowing multiple tasks to be
learned by a single agent. The same domain example to this could be reaching
race-walking and running, a similar domain example could be a single pendulum
or double pendulum balancing task. [8]

Authors conducted an experiment to compare MTRL algorithms. Multi Deep Q
Networks with separate replay memories for each task learned ability to
generalize on multiple tasks while having time complexity then Vanilla DQN.
They also constructed to actor-critic domain with Multi Deep Deterministic
Policy Gradient extended their ability to learn continuous action domains in
the same vein, which they showed with pendulum task.

##### Path Planning with Reinforcement Learning

There are many works of motion planning with DRL [1, 10, 2, 3],. Bae et al.
compared Depth-first methods with RL their results on experiments and shown a
RL algorithm shown paths generated by RL methods more easily executed by
robots then Depth Methods, which generate a polygonal line paths Paths
generated by RL almost in all situations achieve a low orientation error when
executed on the real robot. [2]

They also showed combined with local LIDAR information a RL based path
planning was able to generalize into wider applications and providing better
generalization performance without getting trained for each unknown dynamic
environment.

The problem of multi robot path planning is motivated by many practical tasks
because of its efficiency for performing given missions. However, since each
robot operates individually or cooperatively depending on the situation, the
search area of robot is increased. [3]

Reinforcement learning in the robot’s path planning algorithm is mainly
focused on moving in a fixed space where each part is interactive. In most
cases, existing path planning algorithms highly depend on the environment.
[10]

##### Drones with Reinforcement Learning

The works on Drones have long existed since the beginning of RL.[14, 12, 17] .
Some the early work done was involving dynamic programming algorithms to some
complete basic tasks with RL algorithm to show the capability of RL with
drones but due lack of powerful function approximators such as neural networks
they couldn’t be used in complex real-life situations.

With Deep Learning revolution we have seen drones starting to use Deep
Learning based object detection, image recognition, etc. techniques to better
navigate their paths and thus complete highly precision required tasks such as
delivering cargo[14] and creating HD maps of dangerous parts of the world.
This, of course, comes with a caveat, since DL methods are more compute hungry
battery lives become a more apparent problem.

##  4 Long Term Planning with Deep RL on Autonomous Drones

###  4.1 How does it works

We had access to modeled accurate representation of the actual drone racing
track.[12] The track is highly customizable thanks to AirSim APIs,(see Section
4.1) this helped to easily modify parts of it in towards to achieve domain
randomization. We spawned our training agent in different locations during the
training process for learning to recover it’s the path when it went off during
the evaluation process.

Our long term task is the complete racing track which consists of ten(10)
mini-tasks to finishing faster than competitor drone. Our agent should try to
avoid corners of gate checkpoints, hitting too many corners would distract our
planning and lead us into an unrecoverable state.

Agent gets rewards signals for each step taken in the environment. Reward
engineering is the process of creating appropriate rewards for learning agents
to collect during training.[4, 5] Our technical details regarding details of
explained in here.(See Section 5). Completing all subtasks and finishing race
defined as one episode of MDP process.PPO algorithm we used here can update
its policy multiple times with one trajectory. We used competitor drone
equipped the same physical appearance and aerodynamics to collect guidance
data via API calls. A simple path planning algorithm has been used for
competitor drone. Using an expert-guided approach allows our agent to not
stuck in local optima and away from the target goal. Especially with high
dimensional state problems its very hard to train agents from scratch.
Exploration in the environment mostly supplied with expert guidance and hand-
designed rewards.

Using a function approximator like neural networks we achieved near-real human
operator performance with enough training time. We have explained our
observations and actions in detail.(see Section 4.1.2 )

After 2.5 million steps taken in simulations, our agent started partially
complete ten gate checkpoints while hitting some of the obstacles and stuck in
local optima. Using the same network we have trained 4 million steps more
training with the same seed. While continuing trained networks isn’t much
common in Deep RL domain we had to due limited computational power we
experimented with. After starting of each continued training process agent had
to adapt itself to new trajectories thus felt a performance drops were
expected.

####  4.1.1 AirSim Drone Racing Lab Framework

Figure 2: General overview of communication between agent and simulation .

The goal of our AirSim Drone Racing Lab simulation framework is to help bridge
the gap between simulation and reality by utilizing high fidelity graphics and
physics simulation.[12] It uses Epic’s Unreal Engine 4 for graphic rendering
pipeline while physics engine is deployed into developed by themselves. The
main goal of it enabling to train different machine learning algorithms with
the ability to create unique scenarios and conditions with given high level
APIs to developers. It features the ability to use their flight controller as
well as replacing the default controller with something more sophisticated. It
also features ability to specify inertial sensors which would enable more
realistic training sessions.

Drone racing involves multiple competitor agents and due nature can also be
modeled as multi-agent problem. We have used an already available basic path
planning algorithm implemented inside the simulation environment which helped
us with training and evaluation processes. It is also fairly easy to import 3D
models such as drone gates, obstacles to randomize domain. We can achieve most
of the racing info with API calls which let us access monitor score and
progress as well as time penalties.

It is also fairly simple to get camera data located on the top and behind each
drone available in the simulation. Ground truth data can be extracted from
simulation which would ease the process of data labeling in an Imitation
Learning approach.

####  4.1.2 Proximal Policy Optimization

Proximal Policy Optimization is model free on-policy actor critic algorithm
introduced by Open AI (Schulman et al. 2017)[15] that tries to uses clipped
surrogate function as an optimization goal.

With it’s easy to implement nature and requirement to adjust fewer parameters
with comparable results to other on-policy algorithms,PPO has become one of
the most frequently used continuous control problems.

$\max_{\theta}\mathop{\mathbb{E_{T}}}[\frac{\pi_{\theta}(a_{t}|s_{t})}{{\pi_{\theta}}_{old}(a_{t}|s_{t})}]A_{t}(s_{t},a_{t})$
(1)

Here $A_{t}$ stands for generalized advantage function. (Schulman et al.
2015b)[15]

$\varepsilon$ hyperparameter is used for ratio of clipping between
1-$\varepsilon$ , 1+$\varepsilon$ depending on whether advantage is positive
or negative.

It is widely believed that the key innovation of PPO responsible for its
improved performance over the baseline of TRPO is the ratio clipping mechanism
over KL divergence.

####  4.1.3 Observations and Actions

The RL-agent needs to get all relevant information about the current state of
the environment to be able to fulfill the task successfully. The following
listing provides the raw data that has been identified as relevant. In this
work, we have used quadrotors IMU(Inertial Measurement Unit) sensors which
contains information of linear velocity,angular velocity, gyroscope data for
which contains pitch(x-axis), roll (y-axis), and yaw (z-axis).  The gyroscope
has no initial frame of reference (like gravity), you can combine its data
with data from an accelerometer to measure the angular position. We also used
GPS data we were able to collect from APIs of AirSim. These provided a rich
understanding of the environment thanks to realistic continuous state inputs.

We also use our competitor drone equipped with a classical path planning
algorithm also provide us its location which acts a guidance mechanism during
training.

We have opted to use already implemented low-level drone PID controller -
Since our focus was on path planning rather than improving on PID controller,
though this also reminds a point for improvement in the future.

From our tests, we have seen need for clipping due to inefficient learning so
we have used clipped versions of each sensor input data and outputs from our
neural nets. Our neural network outputs speed difference in terms of x,y,z
coordinates each step given to controller API which then allows our drone to
balance and improve on.

####  4.1.4 Reward Engineering

Reward engineering is a highly active research topic in the RL domain and
researchers have come up with different ideas related to it. Inverse RL tries
to approximate reward function from expert demonstrations shown some success
in small toy tasks but has yet to generalize for complex tasks. Handwritten
reward engineering techniques remains a common practice when designing a RL
system though problems such as low-sparse dilemma remain to be solved. In our
experiment, we have handcrafted rewards and which was the most time-consuming
part of this project.

Our agent had to pass the checkpoint at gates without hitting collapses in 3D
geometric space. We had to create a feedback signal mechanism so it wouldn’t
receive negative rewards for not getting the next gate after passing a gate.
We created a timer function that would keep track of each gate time and decide
rewards for that gate given expert demonstrations by our competitor drone.

Each training episode spawned at a different but constricted random location
which had 2.0 -3.5 meters into actual gate checkpoints, this allowed for more
domain randomization.

We feed agents with positive reward signals based on proportional to their
distance its current target gate. Distance between each was approximately is
10-15 meters, and we had given extra positive rewards when the agent was in
close range of 3 meters to target as a positive incentive. When an agent was
0.5 meters close to its current target gate we started calling our distance
calculation function to properly calculate if our agent passes inside the
gate.

Our calculation was based on L2 distance of the middle point of each gate
proportional to drone orientation. We give a huge positive reward at the
passing of each gate and start timer alongside with it. Until timer for each
game runs out our agent has to leave its current area and to move towards the
next target gate. We have given penalty rewards to our agent that stuck with
the old target gate. Choosing the right values for this situation required a
lot of trial and errors to find the proper fit.

Figure 3: A timer starts to incentive drone to reach next gate checkpoint.

We terminated episodes if the agent was going too far from its target
destination. Any attempt on going too far from gate checkpoint that wasn’t
detected by us was crashing simulation and we could detect crashes in
simulation thus allowed reset environment for next training run.We also kept
track of time and number of hits collisions to gate corners for negative
penalty signals.

##  5 Experiment

####  5.0.1 Implementation Details

Our neural network has 3 layered MLP outputting speed coordinates (x,y,z)
respectively that should be inputted controller of quadrotor to increase or
decrease the speed. We thought about using a recurrent neural network for
allowing better memorisation but at first tests it didnt seem to improve much
so we dropped for a more simplistic network. Our neural network had hidden
size of 256 along with starting learning rate 1e-4. Our trajectories were 2048
steps and mini-batch consisted of 256 transitions each time.

We clipped neural network output to between -1 and 1. In our experiment, this
shows stability and convergence unlike first the approach we tried resulted
have failed results.

We also normalized every state value and rewards for an efficient training
process. We run the simulation at arbitrary 640x480 resolution at 60 frames
per second with all graphical effects in low, shadows disabled. Our training
conducted in cloud GPU providers and we downloaded model weights regularly to
see the running model in the local simulation. Unfortunately, Unreal Engine
API didn’t allow us to record video on server machines.

We have created a mechanism to stop training and continue as efficiently
possible with minimal effect on pre-train drops Communication with our model
and simulation was made possible via TCP communication built inside the
simulation , we have also extended some of its abilities for remote monitoring
of data packages.

####  5.0.2 Evaluation and Results

Our goal was to show teach a RL trained agent to complete ten gate checkpoints
track given time limits, minimizing hitting obstacles and being able to
recover and continue the optimal path from given limits.In order to achieve
this we have hand crafted a unique solution customized for drone racing
environment which can be extended to similar domains. In our early tests we
have seen bad effects of no clipping which led stuck in various local optima
positions. In order to eliminate this issue we have normalized our state and
action values , this way any in case of getting away from optimal path would
result in big negative penalty but it was still recoverable due advantage
policy update nature of algorithm.

Figure 4: Episodic Reward - Time Steps during training.

We have recorded a video of the drone during the evaluation run and published
our results as reproducible with network weights to test and improve upon.

##  6 Conclusion and Future Work

In this experiment, we have shown a fully trained reinforcement learning agent
with using AirSim Drone Racing simulation can achieve successful long term
planning using continuous state values and continuous actions.

Deep Reinforcement Learning algorithms coupled with strong function
approximators can achieve great results at path planning tasks as well as
generalization of said tasks. Spawning agents from different starting
positions achieve tries to achieve domain randomization for agents which then
allows recovery from hard states. This has shown with deploying agents on
different spawn points and seeing their ability to recover and continue at an
optimal path. This work can be extended to real-life drone racing situations
due to the similarity between

We believe a properly calculated IMU data of actual drone can allow us to
deploy trained policy into real life without having a hard time adapting.
Deploying trained simulation policies can allow training for a lot of
interesting planning scenarios due to the ease of training agents in the
simulation. One example could feature planning and delivery tasks for a drone
that carries packages in real life.

##  7 References and Source Code

The documentation and source code for `project` may be found at

https://github.com/ugurkanates/NeurIRS2019DroneChallengeRL

## References

  * [1] Dennis Barrios Aranibar and Pablo Javier Alsina.  Reinforcement Learning-Based Path Planning for Autonomous Robots.  semanticschool, 2019.
  * [2] Hyansu Bae, Kim Gidong, Jonguk Kim, Dianwei Qian, and Sukgyu Lee.  Multi-robot path planning method using reinforcement learning.  Applied Sciences, 9:3057, 07 2019.
  * [3] Kuanqi Cai, Chaoqun Wang, Jiyu Cheng, Clarence W. De Silva, and Max Q.-H. Meng.  Mobile Robot Path Planning in Dynamic Environments: A Survey.  arXiv:2006.14195 [cs], June 2020.  arXiv: 2006.14195.
  * [4] Daniel Dewey.  Reinforcement learning and the reward engineering principle.  aaai spring, 2014.
  * [5] Benjamin Eysenbach, Abhishek Gupta, Julian Ibarz, and Sergey Levine.  Diversity is all you need: Learning skills without a reward function.  arxiv, 2018.
  * [6] Daniel Graves, Nhat M. Nguyen, Kimia Hassanzadeh, and Jun Jin.  Learning predictive representations in autonomous driving to improve deep reinforcement learning.  arxiv, 2018.
  * [7] Peter Henderson, Riashat Islam, Philip Bachman, Joelle Pineau, Doina Precup, and David Meger.  Deep Reinforcement Learning that Matters.  arXiv:1709.06560 [cs, stat], January 2019.  arXiv: 1709.06560.
  * [8] Lianwen Jin, Zhaoyang Yang, Kathryn Merrick, and Hussein Abbass.  Multi-Task Deep Reinforcement Learning for Continuous Action Control.  ijcai, pages 3301–3307, 2017.
  * [9] Alex Krizhevsky, Ilya Sutskever, and Geoffrey E Hinton.  Imagenet classification with deep convolutional neural networks.  In F. Pereira, C. J. C. Burges, L. Bottou, and K. Q. Weinberger, editors, Advances in Neural Information Processing Systems 25, pages 1097–1105. Curran Associates, Inc., 2012.
  * [10] Xiaoyun Lei, Zhian Zhang, and Peifang Dong.  Dynamic Path Planning of Unknown Environment Based on Deep Reinforcement Learning.  Journal of Robotics, 2018:e5781591, September 2018.
  * [11] Siyuan Li, Rui Wang, Minxue Tang, and Chongjie Zhang.  Hierarchical Reinforcement Learning with Advantage-Based Auxiliary Rewards.  arXiv:1910.04450 [cs], October 2019.  arXiv: 1910.04450.
  * [12] Ratnesh Madaan, Nicholas Gyde, Sai Vemprala, Matthew Brown, Keiko Nagami, Tim Taubner, Eric Cristofalo, Davide Scaramuzza, Mac Schwager, and Ashish Kapoor.  AirSim Drone Racing Lab.  arXiv:2003.05654 [cs], March 2020.  arXiv: 2003.05654.
  * [13] Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Alex Graves, Ioannis Antonoglou, Daan Wierstra, and Martin Riedmiller.  Playing Atari with Deep Reinforcement Learning.  arXiv:1312.5602 [cs], December 2013.  arXiv: 1312.5602.
  * [14] Guillem Muñoz, Cristina Barrado, Ender Çetin, and Esther Salami.  Deep reinforcement learning for drone delivery.  Drones, 3(3), 2019.
  * [15] John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov.  Proximal Policy Optimization Algorithms.  arXiv:1707.06347 [cs], August 2017.  arXiv: 1707.06347.
  * [16] Osvaldo Simeone.  A Very Brief Introduction to Machine Learning With Applications to Communication Systems.  arXiv:1808.02342 [cs, math], November 2018.  arXiv: 1808.02342.
  * [17] Satinder Singh, Andrew G. Barto Roderic A. Grupen, Roderic A. Grupen, and Christopher I. Connolly.  Robust Reinforcement Learning in Motion Planning.  CiteSeer, 1995.
  * [18] Sungryull Sohn, Junhyuk Oh, and Honglak Lee.  Hierarchical Reinforcement Learning for Zero-shot Generalization with Subtask Dependencies.  arXiv:1807.07665 [cs, stat], May 2019.  arXiv: 1807.07665.
  * [19] Tung-Long Vuong, Do-Van Nguyen, Tai-Long Nguyen, Cong-Minh Bui, Hai-DangKieu, Viet-Cuong Ta, Quoc-Long Tran, and Thanh-Ha Le.  Sharing experience in multitask reinforcement learning.  IJCAI-19, 2020.
  * [20] wikipedia.  Motion planning, June 2020.  Page Version ID: 962698400.
  * [21] Fisher Yu, Haofeng Chen, Xin Wang, Wenqi Xian, Yingying Chen, Fangchen Liu, Vashisht Madhavan, and Trevor Darrell.  Bdd100k: A diverse driving dataset for heterogeneous multitask learning.  arxiv, 2018.