# Certain Types of Total Irregularities of Graphs and Digraphs

Johan Kok  Tshwane Metropolitan Police Department
City of Tshwane, Republic of South Africa
E-mail<EMAIL_ADDRESS>Sudev Naduvath Department of Mathematics
Vidya Academy of Science & Technology
Thalakkottukara, Thrissur - 680501, India.
E-mail<EMAIL_ADDRESS>
###### Abstract

The total irregularity of a simple undirected graph $G$ is denoted by
$irr_{t}(G)$ and is defined as $irr_{t}(G)=\frac{1}{2}\sum\limits_{u,v\in
V(G)}|d(u)-d(v)|$. In this paper, the concept called edge-transformation in
relation to total irregularity of simple undirected graphs with at least one
cut edge is introduced. We also introduce the concept of an edge-joint between
two simple undirected graphs. We also introduce the concept of total
irregularity in respect of in-degree and out-degree in simple directed graphs.
These invariants are called total in-irregularity and total out-irregularity
respectively. In this paper, we initiate a study on these parameters of given
simple undirected graphs and simple digraphs.

Key Words: Total irregularity, branch-transformation, edge-transformation,
edge-joint, total in-irregularity, total out-irregularity.

Mathematics Subject Classification: 05C07, 05C20, 05C38, 05C70, 05C75.

##  1 Introduction

For general notations and concepts in graph theory, we refer to [5], [8] and
[11] and for digraph theory, we further refer to [6] and [10]. All graphs
mentioned in this paper are simple, connected and finite graphs, unless
mentioned otherwise. Also, except for Section 4, all the graphs mentioned here
are undirected graphs.

A graph $G$ is said to be regular if the degree of all vertices are equal. A
graph that is not regular is called an irregular graph. The total irregularity
of a given simple connected graph is defined in [1] as follows.

######  Definition 1.1.

[1] The imbalance of an edge $e=uv$ in a given graph $G$ is defined as
$|d(u)-d(v)|$. The total irregularity of a graph $G$, denoted by $irr_{t}(G)$,
is defined as $irr_{t}(G)=\frac{1}{2}\sum\limits_{u,v\in V(G)}|d(u)-d(v)|$.

If the vertices of a graph $G$ on $n$ vertices are labelled as
$v_{i},i=1,2,3,\ldots,n$, then the definition may be
$irr_{t}(G)=\frac{1}{2}\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{n}|d(v_{i})-d(v_{j})|=\sum\limits_{i=1}^{n}\sum\limits_{j=i+1}^{n}|d(v_{i})-d(v_{j})|$
or $\sum\limits_{i=1}^{n-1}\sum\limits_{j=i+1}^{n}|d(v_{i})-d(v_{j})|$. For a
graph on a singular vertex (_1-null_ graph or $K_{1}$), we define
$irr_{t}(G)=0$. Clearly, $irr_{t}(G)=0$ if and only if $G$ is regular.

The notion of branch-transformation of a graph has been introduced in [12] as
follows.

######  Definition 1.2.

[12] Let $G$ be a graph with at least two pendent vertices. Without loss of
generality, let $u$ be a vertex of $G$ with $d_{G}(u)\geq 3$, $T$ be a hanging
tree of $G$ connecting to $u$ with $|V(T)|\geq 1$ and $v$ be a pendant vertex
of $G$ with $v\notin T$. Let $G^{\prime}$ be the graph obtained from $G$ by
deleting $T$ from vertex $u$ and attaching it to vertex $v$. We call the
transformation from $G$ to $G^{\prime}$ a branch-transformation on $G$ from
vertex $u$ to vertex $v$.

Certain studies on irregularities and total irregularities of given graphs and
the properties graphs related to these irregularities have been studied in [2,
3, 4, 1, 7, 9] and [12]. Motivated from these studies, in this paper, we
initiate a study on certain types of total irregularities of given graphs and
directed graphs. We introduce the notion of edge-transformation in relation to
total irregularity of simple graphs with at least one cut edge as well as an
edge-joint between two graphs. We also introduce the notion of total
irregularity with respect to in-degree and out-degree in directed graphs.

##  2 Total Irregularity Resulting from Edge-Joints

Consider a graph $G$ on $n$ vertices with two connected components $G_{1}$ and
$G_{2}$. Therefore, $G=G_{1}\cup G_{2}$. Hence, the total irregularity of $G$
is given by
$irr_{t}(G)=irr_{t}(G_{1})+irr_{t}(G_{2})+\sum\limits_{i=1}^{r}\sum\limits_{j=1}^{s}|d(u_{i})-d(v_{j})|$,
where $u_{i}\in V(G_{1})$, $v_{j}\in V(G_{2})$ and $r=|V(G_{1})|$ and
$s=|V(G_{2})|$.

The concept of an edge-joint between two simple undirected graphs $G$ and $H$
is defined below.

######  Definition 2.1.

The edge-joint of two graphs $G$ and $H$ is the graph obtained by adding one
edge, say $uv$, where $u\in V(G),v\in V(H)$, and is denoted by
$G\rightsquigarrow_{uv}H$.

######  Remark 2.2.

It is to be noted that $G\rightsquigarrow_{uv}H=G\cup H+uv$ and
$G\rightsquigarrow_{uv}H\simeq H\rightsquigarrow_{vu}G$.

Now, we make the following standard definitions and notation.

######  Definition 2.3.

Let $G$ be a graph on $n$ vertices with two connected components $G_{1}$ and
$G_{2}$ whose vertex sets are $V(G_{1})=\\{u_{i}:1\leq i\leq r\\}$ and
$V(G_{2})=\\{v_{j}:1\leq j\leq s\\}$. We fix the vertices $u_{1}$ from $G_{1}$
and $v_{1}$ from $G_{2}$. Now, we define the vertex subsets
$V_{1}=\\{u_{x}:d_{G_{1}}(u_{x})\leq d_{G_{1}}(u_{1}),x\neq 1\\}$;
$V_{2}=\\{u_{y}:d_{G_{1}}(u_{y})>d_{G_{1}}(u_{1})\\}$ and let $|V_{1}|=a$ and
$|V_{2}|=b$. Then, choose $V_{3}=\\{v_{x}:d_{G_{2}}(v_{x})\leq
d_{G_{1}}(u_{1})\\}$ and
$V_{4}=\\{v_{y}:d_{G_{2}}(v_{y})>d_{G_{1}}(u_{1})\\}$, where
$|V_{3}|=a^{\ast}$ and $|V_{4}|=b^{\ast}$. Similarly, let
$V_{5}=\\{v_{z}:d_{G_{2}}(v_{z})\leq d_{G_{2}}(v_{1}),~{}z\neq 1\\}$ and
$V_{6}=\\{v_{w}:d_{G_{2}}(v_{w})>d_{G_{2}}(v_{1})\\}$ where $|V_{5}|=c$ and
$|V_{6}|=d$ and choose $V_{7}=\\{u_{z}:d_{G_{1}}(u_{z})\leq
d_{G_{2}}(v_{1})\\}$ and $V_{8}=\\{u_{w}:d_{G_{1}}(u_{w})>d_{G_{2}}(v_{1})\\}$
where $|V_{7}|=c^{\ast}$ and $|V_{8}|=d^{\ast}$.

In view of the above definition, we have the relation between the
cardinalities of the the above mentioned vertex subsets of $V(G_{1})$ and
$V(G_{2})$ as follows.

######  Remark 2.4.

With regard to definition 2.3, define the variables $b=r-a$, $d=s-c=n-r-c$,
$b^{\ast}=r-a^{\ast}$ and $d^{\ast}=s-c^{\ast}=n-r-c^{\ast}$.

######  Theorem 2.5.

Let $G$ be a graph on $n$ vertices with two connected components $G_{1}$ and
$G_{2}$, where $V(G_{1})=\\{u_{i}:1\leq i\leq r\\}$ and
$V(G_{2})=\\{v_{j}:1\leq j\leq s\\}$ . Also, let
$G^{\prime}=G_{1}\rightsquigarrow_{u_{1}v_{1}}G_{2}$. Then, we have
$irr_{t}(G^{\prime})=irr_{t}(G_{1})+irr_{t}(G_{2})+\sum\limits_{i=1}^{r}\sum\limits_{j=1}^{s}|d_{G_{1}}(u_{i})-d_{G_{2}}(v_{j})|+2n-2(b+b^{\ast}+d+d^{\ast})-2$
or
$irr_{t}(G^{\prime})=irr_{t}(G_{1})+irr_{t}(G_{2})+\sum\limits_{i=1}^{r}\sum\limits_{j=1}^{s}|d_{G_{1}}(u_{i})-d_{G_{2}}(v_{j})|+2(a+a^{\ast}+c+c^{\ast})-2n+2$.

###### Proof.

Clearly, for the graph $G=G_{1}\cup G_{2}$, we have
$irr_{t}(G)=irr_{t}(G_{1})+irr_{t}(G_{2})+\sum\limits_{i=1}^{r}\sum\limits_{j=1}^{s}|d_{G_{1}}(u_{i})-d_{G_{2}}(v_{j})|$
with $|V(G_{1})|=r$ and $|V(G_{2})|=s$.

By increasing $d_{G_{1}}(u_{1})$ by 1 we increase the partial sum
$\sum\limits_{\begin{subarray}{c}j=1\\\ w_{j}\in
V_{1}\end{subarray}}^{a}|d_{G_{1}}(u_{1})-d_{G_{1}}(w_{j})|$ by exactly
$(a-1)$. It also reduces the partial sum
$\sum\limits_{\begin{subarray}{c}j=1\\\ w_{j}\in
V_{2}\end{subarray}}^{b}|d_{G_{1}}(u_{1})-d_{G_{1}}(w_{j})|$ by exactly $b$.
It also increases the partial sum $\sum\limits_{\begin{subarray}{c}j=1\\\
w_{j}\in V_{3}\end{subarray}}^{a^{\ast}}|d_{G_{1}}(u_{1})-d_{G_{2}}(w_{j})|$
by exactly $a^{\ast}$ and decreases the partial sum
$\sum\limits_{\begin{subarray}{c}j=1\\\ w_{j}\in
V_{4}\end{subarray}}^{b^{\ast}}|d_{G_{1}}(u_{1})-d_{G_{2}}(w_{j})|$ by exactly
$b^{\ast}$. Furthermore, by increasing $d_{G_{2}}(v_{1})$ by 1, we increase
the partial sum $\sum\limits_{\begin{subarray}{c}j=1\\\ w_{j}\in
V_{5}\end{subarray}}^{c}|d_{G_{2}}(v_{1})-d_{G_{2}}(w_{j})|$ by exactly
$(c-1)$. It also reduces the partial sum
$\sum\limits_{\begin{subarray}{c}j=1\\\ w_{j}\in
V_{6}\end{subarray}}^{d}|d_{G_{1}}(u_{1})-d_{G_{2}}(w_{j})|$ by exactly $d$.
It also increases the partial sum $\sum\limits_{\begin{subarray}{c}j=1\\\
w_{j}\in V_{7}\end{subarray}}^{c^{\ast}}|d_{G_{1}}(u_{1})-d_{G_{1}}(w_{j})|$
by exactly $c^{\ast}$ and decreases the partial sum
$\sum\limits_{\begin{subarray}{c}j=1\\\ w_{j}\in
V_{8}\end{subarray}}^{d^{\ast}}|d_{G_{1}}(u_{1})-d_{G_{1}}(w_{j})|$ by exactly
$d^{\ast}$.

Hence, we have an interim result as follows.

$irr_{t}(G^{\prime})=irr_{t}(G_{1})+irr_{t}(G_{2})+\sum\limits_{i=1}^{r}\sum\limits_{k}{j=1}^{s}|d_{G_{1}}(u_{i})-d_{G_{2}}(v_{j})|+(a-1)-b+a^{\ast}-b^{\ast}+(c-1)-d+c^{\ast}-d^{\ast}\\\
=irr_{t}(G_{1})+irr_{t}(G_{2})+\sum\limits_{i=1}^{r}\sum\limits_{j=1}^{s}|d_{G_{1}}(u_{i})-d_{G_{2}}(v_{j})|+(a-b)+(a^{\ast}-b^{\ast})+(c-d)+(c^{\ast}-d^{\ast})-2$.

By substituting the variables $b,d,b^{\ast}$, and $d^{\ast}$ as defined in
Definition 2.3 the final result is as follows.

$irr_{t}(G^{\prime})=irr_{t}(G_{1})+irr_{t}(G_{2})+\sum\limits_{i=1}^{r}\sum\limits_{j=1}^{s}|d_{G_{1}}(u_{i})-d_{G_{2}}(v_{j})|+2n-2(b+b^{\ast}+d+d^{\ast})-2$,
or;
$irr_{t}(G^{\prime})=irr_{t}(G_{1})+irr_{t}(G_{2})+\sum\limits_{i=1}^{r}\sum\limits_{j=1}^{s}|d_{G_{1}}(u_{i})-d_{G_{2}}(v_{j})|+2(a+a^{\ast}+c+c^{\ast})-2n+2$,
follows. ∎

Clearly $irr_{t}(G^{\prime})$ is edge dependent in general but we have the
following Corollary.

######  Corollary 2.6.

Let the degree sequence of graphs $G_{1}$ and $G_{2}$ be
$(d_{G_{1}}(u_{1})\leq d_{G_{1}}(u_{2})\leq d_{G_{1}}(u_{3})\leq\ldots\leq
d_{G_{1}}(u_{n}))$ and $(d_{G_{2}}(v_{1})\leq d_{G_{2}}(v_{2})\leq
d_{G_{2}}(v_{3})\leq\ldots\ldots\leq d_{G_{2}}(v_{m}))$ respectively. If
$d_{G_{1}}(u_{i})=d_{G_{2}}(v_{j})$ for some $i,j$ and
$d_{G_{1}}(u_{k})=d_{G_{2}}(v_{l})$ for some $k,l$ and
$G^{\prime}=G_{1}\rightsquigarrow_{u_{i}v_{l}}G_{2}$ and
$G^{\prime\prime}=G_{1}\rightsquigarrow_{u_{k}v_{j}}G_{2}$ then,
$irr_{t}(G^{\prime})=irr_{t}(G^{\prime\prime})$.

###### Proof.

Begin the proof by choosing any vertex degree value $t_{1}$ in the degree
sequence of $G_{1}$ and identify largest vertex index say, $i$ for which
$d_{G_{1}}(u_{i})=t_{1}$. Similarly, choose any vertex degree value $t_{2}$ in
the degree sequence of $G_{2}$ and identify largest vertex index say, $l$ for
which $d_{G_{2}}(v_{l})=t_{2}$. Here, we have to consider the following cases.

Case 1: With respect to $G^{\prime}=G_{1}\rightsquigarrow_{u_{i}v_{l}}G_{2}$,
using definition 2.3, set the values as follows.

  1. (i)

$|V_{1}|=a=i-1$,

  2. (ii)

$|V_{2}|=b=n-i$,

  3. (iii)

$|V_{3}|=a^{\ast}=j$,

  4. (iv)

$|V_{4}|=b^{\ast}=m-j$

  5. (v)

$|V_{5}|=c=l-1$,

  6. (vi)

$|V_{6}|=d=m-l$,

  7. (vii)

$|v_{7}|=c^{\ast}=k$,

  8. (viii)

$|V_{8}|=d^{\ast}=n-k$.

Therefore, we have $2(n+m)-2((n-i)+(m-j)+(m-l)+(n-k))-2=2(i+j+k+l-(n+m))-2$.

Case 2: In respect of
$G^{\prime\prime}=G_{1}\rightsquigarrow_{u_{k}v_{j}}G_{2}$ and using
definition 2.3, set the values as follows.

  1. (i)

$|V_{1}|=a=k-1$,

  2. (ii)

$|V_{2}|=b=n-k$,

  3. (iii)

$|V_{3}|=a^{\ast}=l$,

  4. (iv)

$|V_{4}|=b^{\ast}=m-l$

  5. (v)

$|V_{5}|=c=j-1$,

  6. (vi)

$|V_{6}|=d=m-j$,

  7. (vii)

$|v_{7}|=c^{\ast}=i$,

  8. (viii)

$|V_{8}|=d^{\ast}=n-i$.

Therefore, here we have
$2(n+m)-2((n-k)+(m-l)+(m-j)+(n-i))-2=2(k+l+j+i-(n+m))-2$.

Since Case 1 and Case 2 yields the same result, the result
$irr_{t}(G^{\prime})=irr_{t}(G^{\prime\prime})$ follows from 2.5. ∎

An immediate consequence of Corollary 2.6 is that for regular graphs $G_{1}$
and $G_{2}$ we have
$irr_{t}(G_{1}\rightsquigarrow_{vu}G_{2})_{\begin{subarray}{c}u\in V(G_{1})\\\
v\in V(G_{2})\end{subarray}}$ is a constant. This result is proved in the
following proposition.

######  Proposition 2.7.

For the regular graphs $G_{1},G_{2}$ on $n,m$ vertices respectively with
$d_{G_{1}}(u)\geq d_{G_{2}}(v)$ we have

$irr_{t}(G_{1}\rightsquigarrow_{uv}G_{2})=\begin{cases}2(n+m)-2,&\text{if
$d_{G_{1}}(u)=d_{G_{2}}(v)$,}\\\ n\cdot
m|d_{G_{1}}(u)-d_{G_{2}}(v)|+2(n-1),&\text{if
$d_{G_{1}}(u)>d_{G_{2}}(v)$.}\end{cases}$

###### Proof.

The proof follows immediately from definitions 2.3, Remark 2.4 and Corollary
2.6. ∎

We note that if $G_{1}$ and $G_{2}$ are of equal $k$-regularity, then
$irr_{t}(G_{1}\rightsquigarrow_{uv}G_{2})$ is independent of the $k$\- degree
of the vertices.

##  3 Total Irregularity Due to Edge-Transformation

Consider a graph $G$ on $n=l_{1}+l_{2}$ vertices and a cut edge $u_{1}v_{1}$.
Let $G=(G_{1}\cup G_{2})+u_{1}v_{1}$, $u_{1}\in V(G_{1})=\\{u_{i}:1\leq i\leq
l_{1}\\}$ and $v_{1}\in V(G_{2})=\\{v_{i}:1\leq i\leq l_{2}\\}$. Edge-
transformation with respect to $u_{1}$ will be the graph $G^{u_{i}v_{1}}$
obtained by deleting the edge $u_{1}v_{1}$ and adding the edge $u_{i}v_{1}$
for any $i\neq 1$. We call $G_{1}$ the master graph and $G_{2}$ the slave
graph.

Let us now introduce the notion of edge-transformation partitioning of a
vertex set of a given graph as follows.

######  Definition 3.1.

The edge-transformation partitioning of the vertex set $V(G)$ of a graph $G$
on $n$ vertices with at least one cut edge say $u_{1}v_{1}$, is defined to be
$V_{h}=\\{u_{i},v_{k}:d_{G_{1}}(u_{i})=d_{G_{1}}(u_{1})-1\\}$ and
$d_{G_{2}}(v_{k})=d_{G_{1}}(u_{1})-1\\}\cup\\{u_{1}\\},h=|V_{h}|$, and
$V_{s}=\\{u_{i},v_{k}:d_{G_{1}}(u_{i})>d_{G_{1}}(u_{1})-1\\}$ and
$d_{G_{2}}(v_{k})>d_{G_{1}}(u_{1})-1\\},s=|V_{s}|$ and
$V_{t}=\\{u_{i},v_{k}:d_{G_{1}}(u_{i})<d_{G_{1}}(u_{1})-1\\}$ and
$d_{G_{2}}(v_{k})<d_{G_{1}}(u_{1})-1\\},t=|V_{t}|$.

Invoking Definition 3.1, we now define certain vertex sets in $G$ as given
below.

######  Definition 3.2.

We define the certain important sets as follows. Let
$V_{s_{1}}=\\{u_{j},v_{k}:d_{G_{1}}(u_{j})\leq d_{G_{1}}(u_{i})$ and
$d_{G_{2}}(v_{k})\leq d_{G_{1}}(u_{i})$ and $u_{j},v_{k}\in
V_{s}\\},m=|V_{s_{1}}|$, and
$V_{s_{2}}=\\{u_{j},v_{k}:d_{G_{1}}(u_{j})>d_{G_{1}}(u_{i})$ and
$d_{G_{2}}(v_{k})>d_{G_{1}}(u_{i})$ and $u_{j},v_{k}\in
V_{s}\\},l=|V_{s_{2}}|$, and $V_{t_{1}}=\\{u_{j},v_{k}:d_{G_{1}}(u_{j})\leq
d(u_{i})$ and $d_{G_{2}}(v_{k})\leq d_{G_{1}}(u_{i})$ and $u_{j},v_{k}\in
V_{t}\\},m_{1}=|V_{t_{1}}|$, and
$V_{t_{2}}=\\{u_{j},v_{k}:d_{G_{1}}(u_{j})>d_{G_{1}}(u_{i})$ and
$d_{G_{2}}(v_{k})>d_{G_{1}}(u_{i})$ and $u_{j},v_{k}\in
V_{t}\\},l_{1}=|V_{t_{2}}|$.

In view of the above definitions, we propose the following theorem

######  Theorem 3.3.

For a graph $G$ with a cut edge $u_{1}v_{1}$, let $G-u_{1}v_{1}=G_{1}\cup
G_{2}$. After edge-transformation in respect of $v_{1}$ we have

$irr_{t}(G^{u_{i}v_{1}})=\begin{cases}irr_{t}(G),&\text{if}\quad
d_{G_{1}}(u_{i})=d_{G_{1}}(u_{1})-1,\\\ irr_{t}(G)+2m,&\text{if}\quad
d_{G_{1}}(u_{i})>d_{G_{1}}(u_{1})-1,\\\ irr_{t}(G)-2(h+l_{1}),&\text{if}\quad
d_{G_{1}}(u_{i})<d_{G_{1}}(u_{1})-1.\end{cases}$

###### Proof.

If $d_{G_{1}}(u_{i})=d_{G_{1}}(u_{1})-1$, then reducing $d_{G_{1}}(u_{1})$ by
1, reduces the partial sum $\sum\limits_{\begin{subarray}{c}j=1\\\ w_{j}\in
V_{h}\end{subarray}}^{h}|d_{G_{1}}(u_{1})-d(w_{j})|$ by exactly $(h-1)$. It
also increases the partial sum $\sum\limits_{\begin{subarray}{c}j=1\\\
w_{j}\in V_{s}\end{subarray}}^{s}|d_{G_{1}}(u_{1})-d(w_{j})|$ by exactly $s$
and finally it reduces the the partial sum
$\sum\limits_{\begin{subarray}{c}j=1\\\ w_{j}\in
V_{t}\end{subarray}}^{t}|d_{G_{1}}(u_{1})-d(w_{j})|$ by exactly $t$.

Case 1: By increasing $d_{G_{1}}(u_{i}),u_{i}\in V_{h}$ by $1$, the partial
sum $\sum\limits_{\begin{subarray}{c}j=1\\\ w_{j}\in
V_{h}\end{subarray}}^{h}|d_{G_{1}}(u_{i})-d(w_{j})|$ increases by exactly
$(h-1)$. It also decreases the partial sum
$\sum\limits_{\begin{subarray}{c}j=1\\\ w_{j}\in
V_{s}\end{subarray}}^{s}|d_{G_{1}}(u_{i})-d(w_{j})|$ by exactly $s$ and
finally it increases the the partial sum
$\sum\limits_{\begin{subarray}{c}j=1\\\ w_{j}\in
V_{t}\end{subarray}}^{t}|d_{G_{1}}(u_{i})-d(w_{j})|$ by exactly $t$. Hence,
the result,
$irr_{t}(G^{u_{i}v_{1}})=irr_{t}(G)-(h-1)+s-t+((h-1)-s+t)=irr_{t}(G)$ follows.

Case 2: By increasing $d_{G_{1}}(u_{i}),u_{i}\in V_{s}$ by 1, the partial sum
$\sum\limits_{\begin{subarray}{c}j=1\\\ w_{j}\in
V_{h}\end{subarray}}^{h}|d_{G_{1}}(u_{i})-d(w_{j})|$ increases by exactly $h$.
It also changes the partial sum $\sum\limits_{\begin{subarray}{c}j=1\\\
w_{j}\in V_{s}\end{subarray}}^{s}|d_{G_{1}}(u_{i})-d(w_{j})|$ by exactly
$(m-1)-l$ and finally it increases the the partial sum
$\sum\limits_{\begin{subarray}{c}j=1\\\ w_{j}\in
V_{t}\end{subarray}}^{t}|d_{G_{1}}(u_{i})-d(w_{j})|$ by exactly $t$. Hence,
the result,
$irr_{t}(G^{u_{i}v_{1}})=irr_{t}(G)-(h-1)+s-t+h+(m-1)-l+t=irr_{t}(G)+2m$
follows.

Case 3: By increasing $d_{G_{1}}(u_{i}),v_{i}\in V_{t}$ by 1, the partial sum
$\sum\limits_{\begin{subarray}{c}j=1\\\ w_{j}\in
V_{t}\end{subarray}}^{h}|d_{G_{1}}(u_{i})-d(w_{j})|$ decreases by exactly $h$.
It also decreases the partial sum $\sum\limits_{\begin{subarray}{c}j=1\\\
w_{j}\in V_{t}\end{subarray}}^{s}|d_{G_{1}}(u_{i})-d(w_{j})|$ by exactly $s$
and finally it changes the the partial sum
$\sum\limits_{\begin{subarray}{c}j=1\\\ w_{j}\in
V_{t}\end{subarray}}^{t}|d_{G_{1}}(u_{i})-d(w_{j})|$ by exactly
$(m_{1}-1)-l_{1}$.

Hence, the result
$irr_{t}(G^{u_{i}v_{1}})=irr_{t}(G)-(h-1)+s-t-(h-1)-2-s+(m_{1}-1)-l_{1}=irr_{t}(G)-2(h+l_{1})$
follows. ∎

It is to be noted Theorem 3.3 provides an alternate proof for the following
that lemma provided in [12].

######  Lemma 3.4.

[12] Let $G^{\prime}$ be the graph obtained from $G$ by branch-transformation
from $u$ to $v$. Then $irr_{t}(G)>irr_{t}(G^{\prime})$.

Theorem 3.3 can be extended to multi graphs also as explained in the following
result.

######  Corollary 3.5.

If multiple edges or loops are allowed in the graph or if edge-transformation
is performed in a simple graph without a cut edge to give
$G^{w_{i}v_{1}}_{w_{i}\in G}$ then, we have

$irr_{t}(G^{u_{i}v_{1}})=\begin{cases}irr_{t}(G),&\text{if}\quad
d_{G_{1}}(u_{i})=d_{G_{1}}(u_{1})-1,\\\ irr_{t}(G)+2m,&\text{if}\quad
d_{G_{1}}(u_{i})>d_{G_{1}}(u_{1})-1,\\\ irr_{t}(G)-2(h+l_{1}),&\text{if}\quad
d_{G_{1}}(u_{i})<d_{G_{1}}(u_{1})-1.\end{cases}$

###### Proof.

The proof of this theorem follows immediately as a consequence of Theorem 3.3.
∎

##  4 Total Irregularities of Directed Graphs

In this section, we extend the concept of total irregularities of graphs
mentioned in above sections to directed graphs. Since the edges of a digraph
$D$ are directed edges and the vertices of $D$ has two types of degrees, in-
degrees and out-degrees, we need to define two types of total irregularities
for a digraph, which are called total in-degree irregularities and total out-
degree irregularities.

Let the vertices of a simple directed graph $D^{\rightarrow}$ on $n$ vertices
be labelled as $v_{i};i=1,2,3,\ldots,n$ and let
$d^{+}_{D^{\rightarrow}}(v_{i})=d^{+}(v_{i})$ and
$d^{-}_{D^{\rightarrow}}(v_{i})=d^{-}(v_{i})$. Then, the notion of total in-
irregularity of a given directed graph is introduced as follows.

######  Definition 4.1.

The total in-irregularity of a directed graph $D$ with respect to the in-
degree of all vertices of $D$, denoted by $irr_{t}^{-}(D^{\rightarrow})$, is
defined as
$irr_{t}^{-}(D^{\rightarrow})=\frac{1}{2}\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{n}|d^{-}(v_{i})-d^{-}(v_{j})|=\sum\limits_{i=1}^{n}\sum\limits_{j=i+1}^{n}|d^{-}(v_{i})-d^{-}(v_{j})|$
or
$\sum\limits_{i=1}^{n-1}\sum\limits_{j=i+1}^{n}|d^{-}(v_{i})-d^{-}(v_{j})|$.

Similarly, the total out-irregularity of a digraph can also be defined as
follows.

######  Definition 4.2.

The total out-irregularity of a directed graph $D$ with respect to the out-
degree of all vertices of $D$, denoted by $irr_{t}^{+}(D^{\rightarrow})$, is
defined as
$irr_{t}^{+}(G^{\rightarrow})=\frac{1}{2}\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{n}|d^{+}(v_{i})-d^{+}(v_{j})|=\sum\limits_{i=1}^{n}\sum\limits_{j=i+1}^{n}|d^{+}(v_{i})-d^{+}(v_{j})|$
or
$\sum\limits_{i=1}^{n-1}\sum\limits_{j=i+1}^{n}|d^{+}(v_{i})-d^{+}(v_{j})|$.

Re-orientation of an arc or arc-transformation of an arc will find application
in most classical applications of directed graphs like tournaments,
transportation problems, flow analysis or alike.

###  4.1 Total Irregularities of Directed Paths and Cycles

The total in-irregularity and the total out-irregularity of a directed path
are determined in the following proposition.

######  Proposition 4.3.

For a directed path $P_{n}^{\rightarrow}$ which is consecutively directed from
left to right for which vertices $v_{1},v_{n}$ are called the start-vertex and
the end-vertex respectively, we have

  1. (i)

$irr_{t}^{-}(P_{n}^{\rightarrow})=irr_{t}^{+}(P_{n}^{\rightarrow})=n-1$,

  2. (ii)

$irr^{-}_{t}(P_{n}^{\rightarrow})=\begin{cases}n-1,&\text{if the orientation
of}~{}(v_{1},v_{2})\text{is reversed},\\\ 3n-5,&\text{if the orientation
of}~{}(v_{i},v_{i+1}),2\leq i\leq(n-1)\\\ &\text{is reversed}\end{cases}$

  3. (iii)

$irr^{+}_{t}(P_{n}^{\rightarrow})=\begin{cases}n-1,&\text{if the orientation
of}~{}(v_{n-1},v_{n})\text{is reversed},\\\ 3n-5,&\text{if the orientation
of}~{}(v_{i},v_{i+1}),\leq i\leq n-2\\\ &\text{is reversed}.\end{cases}$

###### Proof.

The proof is obvious from the definition of total in-irregularity and total
out-irregularity of a given digraph. ∎

The total in-irregularity and the total out-irregularity of a directed cycle
are determined in the following proposition.

######  Proposition 4.4.

For a directed cycle $C_{n}^{\rightarrow}$ which is consecutively directed
clockwise we have

  1. (i)

$irr_{t}^{-}(C_{n}^{\rightarrow})=irr_{t}^{+}(C_{n}^{\rightarrow})=0$,

  2. (ii)

$irr_{t}^{-}(C_{n}^{\rightarrow})=irr_{t}^{+}(C_{n}^{\rightarrow})=2(n-1)$, if
we reverse the orientation of any arc.

###### Proof.

The proof is obvious from the definition of total in-irregularity and total
out-irregularity of a given digraph. ∎

Through a simple change of Definition 3.1 the in-arc-transformation
partitioning in respect of $v_{1}$ and the out-arc-transformation partitioning
in respect of $v_{1}$ can be defined.

######  Definition 4.5.

The in-arc-transformation partitioning with respect to a vertex $v_{i}$ of the
vertex set $V(G)$ of a simple connected directed graph $G^{\rightarrow}$ on
$n$ vertices is defined to be
$V_{h}=\\{v_{i}:d^{-}(v_{i})=(d^{-}(v_{1})-1)\\}\cup\\{v_{1}\\},h=|V_{h}|$,
and $V_{s}=\\{v_{i}:d^{-}(v_{i})>(d^{-}(v_{1})-1)\\},s=|V_{s}|$ and
$V_{t}=\\{v_{i}:d^{-}(v_{i})<(d^{-}(v_{1})-1)\\},t=|V_{t}|$.

In view of Definition 4.5, we define the following sets

######  Definition 4.6.

Invoking the above definition, some vertex sets of a given digraph are defined
as follows. $V_{s_{1}}=\\{v_{j}:|d^{-}(v_{j})\leq d^{-}(v_{i}),v_{j}\in
V_{s}\\},m=|V_{s_{1}}|$ and
$V_{s_{2}}=\\{v_{j}:d^{-}(v_{j})>d^{-}(v_{i}),v_{j}\in V_{s}\\},l=|V_{s_{2}}|$
and $V_{t_{1}}=\\{v_{j}:d^{-}(v_{j})\leq d^{-}(v_{i}),v_{j}\in
V_{t}\\},m_{1}=|V_{t_{1}}|$ and
$V_{t_{2}}=\\{v_{j}:d^{-}(v_{j})>d^{-}(v_{i}),v_{j}\in
V_{t}\\},l_{1}=|V_{t_{2}}|$.

######  Definition 4.7.

The out-arc-transformation partitioning with respect to a vertex $v_{i}$ of
the vertex set $V(G^{\rightarrow})$ of a simple connected directed graph
$G^{\rightarrow}$ on n vertices is defined to be
$V_{h^{\ast}}=\\{v_{i}:d^{+}(v_{i})=(d^{+}(v_{1})-1)\\}\cup\\{v_{1}\\},h^{\ast}=|V_{h^{\ast}}|$,
and
$V_{s^{\ast}}=\\{v_{i}:d^{+}(v_{i})>(d^{+}(v_{1})-1)\\},s^{\ast}=|V_{s^{\ast}}|$
and
$V_{t^{\ast}}=\\{v_{i}:d^{+}(v_{i})<(d^{+}(v_{1})-1)\\},t^{\ast}=|V_{t^{\ast}}|$.

In view of Definition 4.7, we define the following sets

######  Definition 4.8.

Invoking the above definition, some vertex sets of a given digraph are defined
as follows. $V_{s^{\ast}_{1}}=\\{v_{j}:d^{+}(v_{j})\leq d^{+}(v_{i}),v_{j}\in
V_{s}\\},m^{\ast}=|V_{s^{\ast}_{1}}|$ and
$V_{s^{\ast}_{2}}=\\{v_{j}:d^{+}(v_{j})>d^{+}(v_{i}),v_{j}\in
V_{s}\\},l^{\ast}=|V_{s^{\ast}_{2}}|$ and
$V_{t^{\ast}_{1}}=\\{v_{j}:d^{+}(v_{j})\leq d^{+}(v_{i}),v_{j}\in
V_{t}\\},m^{\ast}_{1}=|V_{t^{\ast}_{1}}|$ and
$V_{t^{\ast}_{2}}=\\{v_{j}:d^{+}(v_{j})>d^{+}(v_{i}),v_{j}\in
V_{t}\\},l^{\ast}_{1}=|V_{t^{\ast}_{2}}|$.

Analogous to Theorem 3.3, we propose the following result.

######  Proposition 4.9.

Consider a simple connected directed graph $G$. After in-arc-transformation in
respect of $v_{1}$ we have

  1. (i)

$irr_{t}^{-}(G^{v_{i}u_{1}})=\begin{cases}irr_{t}^{-}(G),&\text{if}\quad
d^{-}(v_{i})=d^{-}(v_{1})-1\\\ irr_{t}^{-}(G)+2m,&\text{if}\quad
d^{-}(v_{i})>d^{-}(v_{1})-1,\\\ irr_{t}^{-}(G)-2(h+l_{1}),&\text{if}\quad
d^{-}(v_{i})<d^{-}(v_{1})-1\end{cases}$

and

  2. (ii)

$irr_{t}^{+}(G^{v_{i}u_{1}})=\begin{cases}irr_{t}^{+}(G),&\text{if}\quad
d^{+}(v_{i})=d^{+}(v_{1})-1,\\\ irr_{t}^{+}(G)+2m^{\ast},&\text{if}\quad
d^{+}(v_{i})>d^{+}(v_{1})-1,\\\
irr_{t}^{+}(G)-2(h^{\ast}+l^{\ast}_{1}),&\text{if}\quad
d^{+}(v_{i})<d^{+}(v_{1})-1.\end{cases}$

###### Proof.

The proof is similar to Theorem 3.3. ∎

###  4.2 Total Irregularities of Directed Complete Graphs

In this section, we initiate a study on the two types of irregularities of
directed complete graphs. Consider a complete undirected graph $K_{n}$ and
label the vertices $v_{1},v_{2},v_{3},\ldots,v_{n}$. Assign direction the
edges of $K_{n}$ to get a directed graph, with $K_{n}$ as its underlying
graph, in such a way that the edge $v_{i}v_{j}$ becomes the arc
$(v_{i},v_{j})$ of this directed graph if $i<j$. We denote this directed graph
by $K^{\rightarrow}_{n}$. The following lemma discusses the two types of
irregularities of $K^{\rightarrow}_{n}$.

######  Lemma 4.10.

For the directed complete graph $K^{\rightarrow}_{n}$, the total
irregularities are given by
$irr_{t}^{+}(K^{\rightarrow}_{n})=irr_{t}^{-}(K^{\rightarrow}_{n})=\sum\limits_{i=1}^{n-1}\sum\limits_{j=1}^{i}j=\frac{1}{6}n(n^{2}-1)$.

###### Proof.

The orientation results in an in-degree sequence $(0,1,2,\ldots,(n-1))$ and an
out-degree sequence $(n-1,n-2,n-3,\ldots,0)$. Choose the $k$-th entry of the
in-degree sequence. We know that the $k$-th term is given by
$\sum\limits_{j=k+1}^{n}|d^{-}(v_{k})-d^{-}(v_{j})|=\sum\limits_{i=1}^{n-(k+1)}i$.
Also, we have
$irr_{t}^{-}=\sum\limits_{i=1}^{n-1}\sum\limits_{j=i+1}^{n}|d^{-}(v_{i})-d^{-}(v_{j})|$
and hence
$irr_{t}^{-}(K^{\rightarrow}_{n})=\sum\limits_{i=1}^{n-1}i+\sum\limits_{i=1}^{n-2}i+\ldots+\sum\limits_{i=1}^{n-(n-1)}i=\sum\limits_{i=1}^{n-1}\sum\limits_{j=1}^{i}j=\frac{1}{6}n(n^{2}-1)$.
Furthermore, since the out-degree sequence is a mirror image of the in-degree
sequence and
$irr_{t}^{+}=\sum\limits_{i=1}^{n-1}\sum\limits_{j=i+1}^{n}|d^{+}(v_{i})-d^{+}(v_{j})|$,
the result follows similarly. ∎

A general application this study can be the following.

Consider any connected undirected graph $G$ on $n$ vertices and label its
vertices randomly by $v_{1},v_{2},v_{3},\ldots,v_{n}$. Assign direction to the
edges of the graph $G$ to be arcs according to the condition mentioned above
and refer to the directed graph as the root directed graph,
$G^{\rightarrow}_{root-graph}$. Then, calculate both
$irr_{t}^{+}(G^{\rightarrow}_{root-graph})$ and
$irr_{t}^{-}(G^{\rightarrow}_{root-graph})$. In a derivative graph
$G^{\rightarrow}_{derivative}$ identify all arcs which were re-oriented or
subjected to arc-transformation and apply the applicable results to
recursively determine the total in-irregularity and total out-irregularity.

Consider the complete bipartite graph $K_{(m,n)}$ and call the $m$ vertices in
the first bipartition by left-side vertices and the $n$ vertices in the second
bipartition by right-side vertices. Assign directions to the edges of
$K_{m,n}$ strictly from left-side vertices to right-side vertices to obtain
$K^{l\rightarrow r}_{m,n}$.

######  Proposition 4.11.

For the directed graph $K^{l\rightarrow r}_{m,n}$, we have
$irr^{-}_{t}(K^{l\rightarrow r}_{m,n})=m^{2}n$ and
$irr^{+}_{t}(K^{l\rightarrow r}_{m,n})=mn^{2}$.

###### Proof.

The orientation of the directed complete bipartite graph $K^{l\rightarrow
r}_{m,n}$ results in the in-degree sequence
$(\underbrace{0,0,\ldots,0,}_{m-entries}\underbrace{m,m,\ldots,m}_{n-enties})$
and the out-degree sequence $(\underbrace{n,n,\ldots,n,}_{m-entries}\\\
\underbrace{0,0,\ldots,0}_{n-enties})$. Here, we have the following cases.

Case 1: For the above mentioned in-degree sequence of $K^{l\rightarrow
r}_{m,n}$, we have the sum
$\sum\limits_{i=1}^{(m+n)-1}\sum\limits_{j=(i+1)}^{(m+n)}|d^{-}(v_{i})-d^{-}(v_{j})|$
results in the value $m$, ($mn$ times) and $0$, ($(m+n)-2$ times). Hence,
$irr_{t}^{-}(K^{l\rightarrow r}_{(m,n)})=m^{2}n$.

Case 2: For the above mentioned out-degree sequence of $K^{l\rightarrow
r}_{m,n}$, we have the sum
$\sum\limits_{i=1}^{(m+n)-1}\sum\limits_{j=(i+1)}^{(m+n)}|d^{+}(v_{i})-d^{+}(v_{j})|$
results in the value $n$, ($mn$ times) and $0$, ($(m+n)-2$) times). Hence,
$irr_{t}^{+}(K^{l\rightarrow r}_{(1,n)})=mn^{2}$. This completes the proof. ∎

Invoking from Proposition 4.11, we note that for the directed bipartite graph
$K^{l\rightarrow r}_{1,n}$, we have $irr^{-}_{t}(K^{l\rightarrow r}_{1,n})=n$
and $irr^{+}_{t}(K^{l\rightarrow r}_{(1,n)})=n^{2}$ and
$irr^{-}_{t}(K^{l\rightarrow r}_{m,1})=m^{2}$ and $irr^{+}_{t}(K^{l\rightarrow
r}_{m,1})=m$.

The following is a challenging and interesting problem in this context.

######  Problem 4.12.

Describe an efficient algorithm to determine
$irr_{t}^{-}(G^{\rightarrow}_{derivative})$ and
$irr_{t}^{+}(G^{\rightarrow}_{derivative})$ from
$irr_{t}^{-}(G^{\rightarrow}_{root-graph})$ and
$irr_{t}^{+}(G^{\rightarrow}_{root-graph})$.

##  5 Conclusion

In this paper, we have studied certain types of total irregularities of
certain graphs and digraphs. More problems in this area still remain
unsettled. More studies on different types of irregularities for different
graph classes, graph operations, graph products and on certain associated
graphs such as line graphs and total graphs of given graphs and digraphs
remain open. All these facts indicates that there is a wide scope for further
investigations in this area.

## References

  * [1] M. O. Albertson, The irregularity of a graph, Ars Combinatoria, 46(1997) 219–225.
  * [2] H. Abdo, S. Brandt and D. Dimitrov, The total irregularity of a graph, Discrete Mathematics and Theoretical Computer Science, 16 (1) (2014) 201-206.
  * [3] H. Abdo, N. Cohen, and D. Dimitrov, Bounds and computation of irregularity of a graph, Filomat, to appear.
  * [4] H. Abdo and D. Dimitrov, The total irregularity of a graph under graph operations, Miskolc Mathematical Notes, 15 (1) (2014) 3-17.
  * [5] J. A. Bondy and U. S. R. Murty, Graph theory with applications, Macmillan Press, London, 1976.
  * [6] G. Chartrand and L. Lesniak, Graphs and Digraphs, CRC Press, 2000.
  * [7] D. Dimitrov and R. Škrekovski, Comparing the irregularity and the total irregularity of graphs, Ars Mathematica Contemporanea. In press.
  * [8] F. Harary, Graph Thory, Addison-Wesley Pub., 1969.
  * [9] M. A. Henning, D. Rautenbach, On the irregularity of bipartite graphs, Discrete Mathematics 307(2007), 467-1472.
  * [10] J. B. Jensen and G. Gutin, Digraphs-Theory, Applications and Algorithms, Springer-Verlag, 2007
  * [11] D. B. West, Introduction to Graph Theory, Pearson Education Inc., 2001.
  * [12] Y. Zhu, L. You and J. Yang, J., The minimal total irregularity of graphs, Preprint. arXiv: 1404.0931v1 [math.CO].


# APEX: Ambidextrous Dual-Arm Robotic Manipulation Using
Collision-Free Generative Diffusion Models

Apan Dastider, Hao Fang, and Mingjie Lin

###### Abstract

Dexterous manipulation, particularly adept coordinating and grasping,
constitutes a fundamental and indispensable capability for robots,
facilitating the emulation of human-like behaviors. Integrating this
capability into robots empowers them to supplement and even supplant humans in
undertaking increasingly intricate tasks in both daily life and industrial
settings. Unfortunately, contemporary methodologies encounter serious
challenges in devising manipulation trajectories owing to the intricacies of
tasks, the expansive robotic manipulation space, and dynamic obstacles. We
propose a novel approach, APEX, to address all these difficulties by
introducing a collision-free latent diffusion model for both robotic motion
planning and manipulation. Firstly, we simplify the complexity of real-life
ambidextrous dual-arm robotic manipulation tasks by abstracting them as
aligning two vectors. Secondly, we devise latent diffusion models to produce a
variety of robotic manipulation trajectories. Furthermore, we integrate
obstacle information utilizing a classifier-guidance technique, thereby
guaranteeing both the feasibility and safety of the generated manipulation
trajectories. Lastly, we validate our proposed algorithm through extensive
experiments conducted on the hardware platform of ambidextrous dual-arm
robots. Our algorithm consistently generates successful and seamless
trajectories across diverse tasks, surpassing conventional robotic motion
planning algorithms. These results carry significant implications for the
future design of diffusion robots, enhancing their capability to tackle more
intricate robotic manipulation tasks with increased efficiency and safety.
Complete video demonstrations of our experiments can be found in
https://sites.google.com/view/apex-dual-arm/home.

###### Index Terms:

Ambidextrous dual-arm robotic manipulation, Latent diffusion model, Collision-
free, Classifier guidance

Figure 1: a)Dual-arm robotic manipulation platform (b) Overall diagram of our
algorithm. (c) Our diffusion models learn the distribution of trajectory using
training data (black line) and generate a new planning trajectory (green
dashed line). Further, it adapts the generated trajectory (red dashed line) to
avoid the potential obstacles (red box).

##  I Introduction

Ambidextrous dual-arm robotic manipulation requires sophisticated coordination
and control to synchronize the movements of both arms and hands seamlessly.
Unlike well-studied single-arm robots, ambidextrous robots must coordinate the
actions of two separate arms and two hands while navigating complex
environments and interacting with dynamic objects. This heightened level of
complexity necessitates advanced planning and control strategies to ensure
successful task execution and obstacle avoidance. However, realizing such
ambidextrous dual-arm robotic manipulation in real world is complicated [1].
First, different from the prior 7-DoF robotic arm model, the ambidextrous
dual-arm robotic system allows more joint freedom, which requires more
parameters and faces complex constraints to comprehensively describe the joint
configuration space [2]. Second, the aim of the ambidextrous dual-arm robotic
system is to perform more complicated human-like tasks, such as packaging,
stacking, steering liquid in a cup, and etc; which impose more dexterous
manipulation requirements such as smoothness and diversity. Third, the real-
time moving obstacles should be avoided during manipulation, which requires
the algorithm to work under a close-loop fashion [3]. Fourth, it is crucial
that motion planning algorithms exhibit computational efficiency to support
real-time adaptive control of both robotic arms and hands [4]. All these
challenges collectively impede the advancement of motion planning algorithms
in dual-arm robotic manipulation tasks.

Figure 2: Solving the real-world dexterous dual-arm robotic manipulation
tasks. The first row indicates various robotic manipulation tasks. The second
row is the initial position of the manipulation tasks. The third row distills
the manipulation tasks by abstracting them as vector alignment problems, which
can be solved using our proposed algorithm. The last row shows the successful
completeness of the manipulation tasks.

To date, diffusion models have emerged as a powerful tool in robotics, owing
to their flexibility and multi-modality. However, their application in the
context of dual-arm robotic manipulation remains relatively unexplored,
particularly concerning real-time performance and the diversity of
manipulation tasks. In this paper, we propose a collision-free diffusion model
to address the aforementioned challenges. The key contributions of our work
are outlined below:

  * •

Abstracting real-life ambidextrous dual-arm robotic manipulation tasks as two
vector alignment problems, a conceptualization that significantly simplifies
the tasks and underscores the model’s applicability across various real-world
scenarios.

  * •

Development of latent diffusion models for generating diverse robotic
manipulation trajectories. Additionally, we integrate obstacle information
using the classifier-guidance technique, ensuring the practicality and safety
of the resulting manipulation trajectories.

  * •

Validation of the proposed algorithm on a hardware platform featuring
ambidextrous dual-arm robots. Our algorithm consistently produces successful
and seamless trajectories across multiple tasks, outperforming conventional
robotic motion planning algorithms. These findings carry implications for the
future design of diffusion robots, particularly in tackling more complex
robotic manipulation tasks effectively.

##  II Related work

###  II-A Dual-arm robotic manipulation

Dual-arm robotic manipulation has been traditionally formulated as a classical
optimal control problem, which primarily involves minimizing a desired cost
function using a simplified model of the dynamical system [5, 4]. Second,
researchers also primarily relied on the classic sampling framework of
Rapidly-exploring Random Trees (RRT) algorithms [6, 7], which mainly develops
graph traversal methods in the robotic configuration space, whose trajectory
planning ability becomes limited and useless if the dimension of the robotic
configuration space becomes higher. Recently, reinforcement learning (RL)
algorithms [8, 9], have been introduced by maximizing a reward function for
accomplishing such dual-arm manipulation tasks. Imitation Learning (IL)
algorithms initially gather a substantial number of task samples, such as
human demonstrations, and then employs deep learning architectures like
convolutional/recurrent neural networks[10, 11] or transformers[12] to train
the model through teacher-forcing training. However, the above learning-based
methods may be severely suffered by the heterogeneous data distribution shift,
i.e., the training and test data are sampled from different manipulation tasks
or the obstacles distribution is biased, and limited trajectory generation
diversity, which ultimately decreases their potential advantages. Although
these approaches have proven highly effective in some cases, they do not
address highly complex real-world working spaces with potentially dynamic
obstacles or the full coordination of robotic arms and hands.

###  II-B Diffusion models

Diffusion models have been illustrated with great potential as generative
models of images [13] and videos [14] and outperform other generative models
such as adversarial networks (GANs) [15] and variational autoencoders (VAEs).
Ho et al [16] proposes denoising diffusion probabilistic models (DDPMs) by
treating the training procedure as minimizing the mean-square error of noise
at each time step. To facilitate the sampling time, latent diffusion models
(LDMs) are proposed to first integrate autoencoders (AEs) for latent
representation and then to train the diffusion model in the corresponding
latent space [17]. After sampling, the generated latent representation will be
sent through a decoder to recover the generated images. For most of the
diffusion models, the underlying backbone architecture is selected as
convolutional neural networks (CNNs), such as U-Nets [18]. To date, there are
few works that incorporate the diffusion models for robotic motion planning
[19, 20, 21, 22, 23]. For instance, [19] utilized a zero-shot learning
mechanism with pre-trained generative models to complete object arrangement
tasks. On the contrary, [21] implemented a reward mechanism along with
diffusion model-based trajectory generation and the authors proposed a reward-
based guidance for optimization with maximum utility for task completion.

Figure 3: The diagram of our ambidextrous dual-arm robotic manipulation
algorithm using latent diffusion models to generate the collision-free
trajectory. The input of our trajectory data $x$ first goes into a pre-trained
variational autoencoder to have a low-dimensional latent embedding $z_{0}$,
which will be used to train a diffusion model. In the sampling procedure, we
randomly generate Gaussian noise trajectory $z_{T}$ and pass it through
reverse denoising steps to generate clean trajectory latent embedding
$z^{{}^{\prime}}_{0}$, which can be decoded using a pre-trained VAE decoder.
Further, to ensure the generated trajectory $x^{{}^{\prime}}$ is collusion-
free, we add two mechanisms on top of the latent diffusion models. First, we
use the obstacle information $g$ as the conditional constraint in both
training and sampling process. Second, our trajectory generation process works
in a close-loop manner, where we check the possibility of collision violation
and resample a new trajectory if necessary.

##  III Methods

###  III-A Distill ambidextrous dual-arm manipulation tasks as vector
alignment problems

Many day-to-day tasks such as stacking packages or pouring liquid from one cup
to another cup can be summarized and simplified. In our work, we distill the
dual-arm manipulation tasks by vector alignment problems. Here, we
demonstrated several dual-arm manipulation tasks as well as their
distillations in Fig.2. We first used the well-established YOLO algorithm (a
typical type of convolutional neural network in computer vision) for object
detection from the captured frame using the depth sensor [24]. The YOLO
algorithm localized the object of interest at each time frame and detected the
position and orientations of those objects. Then we drew simple 2D vectors
$v_{1}$ and $v_{2}$ along the orientations of the objects as depicted in the
upper row of Fig.2. Once we captured the orientations of two vectors, we can
convert the complex manipulation task to a simple vector alignment problem.
Therefore, this distillation reduces computationally heavy image-based motion
planning problems to a simple vector-conditioned trajectory planning problem.
Take the first task (Ball in a cup) for an illustration, the two vectors are
randomly placed initially, where we are required to develop a motion planning
algorithm such that inital two vectors are aligned in the desired positions
and opposite orientations. Once our proposed algorithm finishes the task, we
can measure the robot configuration space using the measured initial state and
final state for the performance evaluation of our algorithm. Further, we also
consider dynamic obstacles during our tasks for the mimic of more complicated
real-world robotic motion planning tasks.

Let $\mathcal{S}\subseteq\mathbb{R}^{n}$ and $U\subseteq\mathbb{R}^{m}$ define
the state space and control input for our dual-arm robotic system. The robotic
system evolves through the following discrete time-dynamics,

$\mathcal{S}_{t+1}=f(\mathcal{S}_{t},u_{t})$ (1)

where $f(\cdot)$ is a function controlling the discrete-time system
progression for action $u_{t}$ from state $\mathcal{S}_{t}$ to
$\mathcal{S}_{t+1}$. We assume the $\mathcal{S}_{\text{safe}}$ and
$\mathcal{S}_{\text{unsafe}}$ are the collision-free and collision space with
$\mathcal{S}_{\text{safe}}\cap\mathcal{S}_{\text{unsafe}}=\emptyset$,
respectively. During the task distillation, we get the initial state vector,
$\mathcal{S}_{\text{ini}}\in\mathcal{S}_{\text{safe}}$ and target vector,
$\mathcal{S}_{\text{goal}}\in\mathcal{S}_{\text{safe}}$ and current point
obstacle information. Together, all the above information constitutes a
conditional guidance vector $g_{t}$. The goal of our algorithm is to generate
a trajectory, $\tau=\\{\tau_{0},\cdots,\tau_{T-1}\\}$ conditioned on $g_{t}$
such that it is safe against dynamically moving obstacles
($\tau\in\mathcal{S}_{\text{safe}}$) and drive the two-arm robotic system
reaching the goal state $\mathcal{S}_{\text{goal}}$.

###  III-B Diffusion-based deep generative learning

In this section, we develop the main component of our diffusion-based deep
generative model for the synthesis of alignment trajectories. We consider the
following Gaussian diffusion models, which include a forward process and a
reverse process. The forward noise process describes conditional probability
distribution $q(x_{t}|x_{0})$ given the initial data distribution $q(x_{0})$,
which can be the collected trajectory data in our case.

$q(x_{t}|x_{0})=\mathcal{N}(x_{t};\sqrt{\bar{\alpha}_{t}}x_{0},(1-\bar{\alpha}_{t})\mathbf{I}),$
(2)

where $\bar{\alpha}_{t}$ is are predefined constant for introducing noise at
each forward process [16]. Using the property of Gaussian distribution and
parameterization trick, one can directly sample $x_{t}$ using (2) by
$x_{t}=\sqrt{\bar{\alpha}_{t}}x_{0}+\sqrt{(1-\bar{\alpha}_{t})}\epsilon_{t}$,
where $\epsilon_{t}$ follows standard Gaussian distribution
$\mathcal{N}(\mathbf{0},\mathbf{I})$. The reverse diffusion process is to
learn a set of the neural network parameters $\theta$ that reverse the forward
noise process,

$p(x_{t-1}|x_{t})=\mathcal{N}(x_{t-1};\mu_{\theta}(x_{t}),\Sigma_{\theta}(x_{t}).$
(3)

Therefore, the goal of the diffusion models is to ensure the prediction
$p_{\theta}(x_{0})$ using learned neural network parameters $\theta$ that can
recover the original data distribution $q(x_{0})$ as close all possible, which
can be quantified using evidence lower bound (ELBO) [16]. Thus, one can
maximize the lower bound of the log-likelihood of $x_{0}$ with the following
loss function

$L(\theta)=-\mathbb{E}_{x_{0:T\sim
q}}[\text{log}p_{\theta}(x_{0:T})-\text{log}q(x_{1:T}|x_{0})].$ (4)

However, the above loss function (4) has been recognized as hard for fasting
training since it focuses on image reconstructions. Essentially, the diffusion
model need to care more about the reverse denoising process by focusing on
cleaning the forward noise corruption, which inspires the design of noise
prediction work [16],

$L(\theta)=\Sigma^{t=T}_{t=1}||\epsilon_{\theta}(x_{t})-\epsilon_{t}||^{2}_{2}.$
(5)

Therefore, we utilize this simple mean-square error loss through our training
process. In the sampling case, we randomly sample $x_{T}$ from standard
Gaussian distribution $\mathcal{N}(\mathbf{0},\mathbf{I})$ and pass through
the reverse denoising process to graduate clean the noisy trajectories step by
step $p(x_{t-1}|x_{t})$ (see Figure 3). The above equations (2), (3), (5)
describe how we construct the diffusion model for the generation of new
trajectories. Also, the backbone of the diffusion model follows the U-Net
architecture, a typical type of symmetric conventional convolution neural
networks (CNNs).

However, the above naive diffusion model meets two difficulties for the
robotic trajectory generations. First, the robotic planning trajectory usually
has high temporal dimensions. Thus, directly training and sampling on the
high-dimensional trajectory space is hard and time-consuming. Second, the
manipulation of robotics usually involves the interaction of dynamic
environments, meaning that the robot needs to react to the environmental
obstacles and replan the trajectories to avoid any potential collisions.
Therefore, we leverage the latent diffusion models by first training a
variational autoencoder to embed the high-dimensional trajectory as
$z=\text{Encoder}(\tau)$. Then, we train the proposed diffusion model in the
embedded space. Last, we use a trained decoder $\tau=\text{Decoder}(z)$ to map
the sampled low-dimensional trajectory embedding back to the original
trajectories for later manipulation of ambidextrous dual-arm robots. To deal
with the second difficulty, we integrate the classifier guidance technique as
the real-time feedback condition to guide the generation of safe and feasible
trajectories (see next section).

###  III-C Obstacle guidance as feedback to close the loop

The most advanced diffusion robot works mainly applied the diffusion framework
for synthesizing planning trajectories without considering dynamic
environmental obstacles [21, 22, 25, 26]. Our second innovative contribution
is to use the classifier guidance technique [15, 27] as the real-time feedback
condition to guide the generation of safe and feasible trajectories.
Specifically, we assume at certain steps, our camera sensor can take the image
of the current interaction of the robotic arms and environment (denoted as
$g_{t}$), abstractly representing the current alignment procedure and
potential environmental obstacles. The conditional diffusion models using the
obstacle guidance technique can be developed under the Bayes theorem
$p(x|g)\propto p(x)p(g|x)$,

$\nabla_{x}\text{log}p_{\theta}(x|g)=\nabla_{x}\text{log}p_{\theta}(x)+\gamma\nabla_{x}\text{log}p_{\theta}(g|x),$
(6)

where $\gamma$ controls the guidance scale; $g$ is the interaction information
that we described above. Put equation (6) into the diffusion model, it turns
out that we only need to modify noise prediction at the sampling stage via

$\hat{\epsilon}_{\theta}(x_{t})=\epsilon_{\theta}(x_{t})-\gamma\sqrt{(1-\alpha_{t})}\nabla_{x_{t}}\text{log}p_{\theta}(g|x).$
(7)

In the extreme case $\gamma=0$, this conditional diffusion model degrades to
the previous diffusion model, which can generate diverse but unsafe
manipulation trajectories. On the contrary, we impose the conditional
generation of collision-free trajectory as we increase the guidance scale
$\gamma$. Therefore, by integrating the classifier-guidance technique as
obstacle-guidance, we essentially build a closed-loop trajectory generation
procedure, where we adapt the prior generated trajectory at certain time steps
using the real-time obstacle feedback.

To this end, we complete the development of our proposed algorithm. A summary
of the algorithm can be found in the algorithm 1 and figure 3.

——–TRAINING——–

Input: Dataset,
$\mathcal{D}:\\{\text{Trajectory}\;\tau_{i},\text{Guidance}\;g_{i}\\}_{i=1}^{N}$,
Conditional Diffusion Model, $\epsilon_{\theta}$; $\bar{\alpha}_{t},T$

Output: Trained model, $\tilde{\epsilon_{\theta}}$

Function  _train( $\mathcal{D},\bar{\alpha}_{t},\epsilon_{\theta},T$):_

while  _not converged_ do

# sample batch of traj. and respective conditional vector

$(\tau_{0},g_{0})\sim\mathcal{D},\epsilon\sim\mathcal{N}(0,I),t\sim\mathcal{U}(1,T)$

# concat time-embedding and $g_{i}$

$t\\_cond=concat(pos\\_emb(t),\phi_{\omega}(g_{i}))$

# create noisy trajectory

$\tau_{\epsilon}(t)\leftarrow\sqrt{\bar{\alpha}_{t}(t)}\tau_{0}+\sqrt{1-\bar{\alpha}_{t}(t)}\epsilon$

# MSE Error calc.

$L_{\theta}=||\epsilon-\epsilon_{\theta}(\tau_{\epsilon}(t),t\\_cond)||_{2}^{2}$

# Gradient Update

$\theta\leftarrow\theta+\nabla_{\theta}L_{\theta}$

——–SAMPLING——–

Input: Frame $f_{0}$, Trained Model, $\tilde{\epsilon}_{\theta}$ ,
$\lambda_{obs}$

Output: Feasible Trajectory, $\tau^{*}$

Function  _execute( $f_{0},\tilde{\epsilon}_{\theta},\lambda_{obs})$:_

# Task Distil. for Vector Alignment and obs info

$g_{0}\leftarrow vect\\_align(f_{0})$

# Sample Noisy Trajectory

$\tau_{T}\leftarrow\mathcal{N}(0,I)$

# Noise Prediction

$\epsilon_{T}\leftarrow\epsilon_{\theta}(\tau_{T},concat(pos\\_emb(T),\phi_{\omega}(g_{0})))$

# Initial Safe Trajectory Calc.

$\tau_{0}\leftarrow traj\\_calc(\alpha_{t},\epsilon_{T},\tau_{T})$

while  _not done_ do

CALCULATE:

Distance, $d_{obs}\leftarrow GJK(robot,obstacle)$

# Collision Checking

if  _$d_{obs} <\lambda_{obs}$_ then

UPDATE:

# Sample new trajectory for collision avoidance

$\tau_{new}\leftarrow generate\\_traj(f_{curr},\tilde{\epsilon}_{\theta})$

else

EXECUTE:

# Action Execution following generated traj.

Dual Arm-hand Control,
$\tau_{i}\rightarrow\\{[\theta_{0}^{k},\cdots\theta_{6}^{k}]_{k=1,2},\theta_{h}^{1},\theta_{h}^{2}\\}_{i}$

Algorithm 1 APEX

###  III-D Platforms and implementation details

We utilized two high-fidelity 7-DoF Franka Emika Panda robot arms and
assembled them on two separate table-top for smoother and collision-free
operation. We used two anthropomorphic five-fingered hands named QB SoftHand2
Research in left-right hand combinations. To locate objects and track dynamic
obstacles with depth information, we used an Intel RealSense Depth Camera
D435i. On each frame captured by depth camera, we run YOLO for object
detection and obstacle localization. Later, we detected the orientation and
position of vectors associated with each object. To differentiate the obstacle
from objects, we used color-based segmentation on detected frames. By applying
the conventional hand-to-eye calibration, we transported the $[x,y,z]_{o}$
information from the camera reference frame to the robot coordinate system.
Our algorithm utilized this feedback from depth sensors to avoid obstacles in
real-world scenarios by computing the distance between the 3D geometry of the
obstacle and the collision meshes of robot links using the
Gilbert–Johnson–Keerthi distance (GJK)[28] algorithm. This distance feedback
triggers the controller to search for a new trajectory if chances of collision
occur while completing the vector alignment task. To validate our approach, we
replicated the exact model of the Franka Emika Panda Arms with QB SoftHand2 in
the Robot Operating System (ROS). We utilized the libfranka and Franka ROS, to
establish low-latency and low-noise communication protocols for data
processing and parallel execution among simulation environments and real
hardware. QB Softhand2 research hands were operated through serial
communication in parallel for object grasping and placement into the assigned
alignment by associated vectors.

Figure 4: Snapshots of hardware demonstration from vertical (a)-(e) and
horizontal alignment task (f)-(j). (a)-(b) Robotic arms grasp the boxes from a
table. (c)-(d) Right robotic arm avoids possible collision (red box). (e)
Successful task completed. (f)-(g) Two arms take the cup and the ball to
prepare a task in hand. (h) A dynamic obstacle appears in the workspace and
the left robotic arm faces probable collision, (i) The Left arm moves over the
obstacle to avoid collision. Now, the right arm gets into a probable collision
with the moving red box. (j) Both arms dodge the obstacles and complete the
task. Figure 5: Denoising diffusion process for the generation of manipulation
trajectories. From left to right, we gradually show how the denoising
diffusion process generates a smooth and feasible trajectory to reach the
predefined goal position.

We collected high-dimensional trajectory $\tau_{i}$ samples for dual-arm
manipulation setup from ROS, where each data sample $\tau_{i}^{j}$ contains
total $16$ float values – $14$ joint values from two robotic arms
$[\theta_{0}^{k},\cdots\theta_{6}^{k}]_{k=1,2}$ and $2$ synergy joint values
from two robotic hands $[\theta_{h}^{1},\theta_{h}^{2}]$. We only use robotic
hands for grasping tasks. Thus, we only exploit the first synergy of robotic
hands. As a result, each robotic hand can either close or open, where the
synergy value indirectly controls the $19$ self-healing finger joints. The
conditional constraint vector has $35$ float values – $16$ values for initial
or current system state which contains
$\\{[\theta_{0}^{k},\cdots\theta_{6}^{k}]_{k=1,2},\theta_{h}^{1},\theta_{h}^{2}\\}_{ini}$,
$16$ values for final or target state
$\\{[\theta_{0}^{k},\cdots\theta_{6}^{k}]_{k=1,2},\theta_{h}^{1},\theta_{h}^{2}\\}_{tar}$,
$3$ values for obstacle point $[x,y,z]_{o}$. Then, the conditional vector $g$
goes through a MLP network $\phi_{\omega}(g)$ parameterized by $\omega$ and
the output of $\phi_{\omega}(\cdot)$ applies residual connections to each
convolution layer in the U-Net(see Fig. 3), and later also uses positional
embedding of each timestep during the model training. After obstacle
detection, the GJK algorithm localizes the nearest point on obstacle body by
calculating the distance from full robot meshes. We collected 500k collision-
free trajectory samples with different starting and ending alignment
configurations from our simulation platform. Each trajectory samples consist
$256$ discrete trajectory steps, which are from the starting state to the
final ending state. Also, the dense trajectory samples allow us to perform
adaptive planning from any initial state to the target goal state and handle
dynamic obstacles simultaneously. Our algorithm was implemented using the
Pytorch library and ran on a Lambda QUAD GPU workstation equipped with an
Intel Core-i9-9820X processor and $4$ Nvidia $3080-ti$ GPU machines. It took
10 hours to train our collision-free generative diffusion models.

###  III-E Experiments setup and evaluation metrics

We design both comprehensive Monte Carlo computer simulations and hardware
experiments to evaluate our proposed APEX algorithm for achieving dual-arm
alignment manipulations. Our experiments mainly focus on two aspects: A) the
vertical alignment, such as stacking, which can simplify the package sorting
and stacking tasks in real life; B) the horizontal alignment, such as peg and
hole task, which can be used to represent any insertion task in real life. We
believe that by illustrating the performance on the above vertical and
horizontal alignment tasks, we essentially evaluate our algorithms across a
wide range of dual-arm robotic manipulation tasks. Further, we also implement
typical existing robotic motion planning algorithms in our experiments, where
we include the RRT [29] and GPMP [30], a transformer-based imitation learning
algorithm for motion planning [12] and our prior VAE-based graph traversal
planning algorihtm [3]. For object grasping, we utilize advanced
functionalities from ROS MoveIt Grasps API.

We define the following evaluation metrics to effectively quantify the
performance. First, we define the failure ratio,

$R_{f}=\frac{F}{N}\times 100\%,$ (8)

where $F$ counts the failed tasks and $N$ denotes the total number of tasks
that we performed. Therefore, smaller $R_{f}$ means the generated trajectories
successfully avoid obstacles and realize better alignment performances. Then,
we quantify the smoothness of the executing trajectory of dual-arm robots by
summing up the joint space configuration change in sampled trajectory as

$S_{r}=\sum_{i=0}^{N-1}||\Theta_{i}-\Theta_{i+1}||_{2}$ (9)

where $\Theta_{i}$ is joint space configuration at $\tau_{i}$. Last, we use
the Frechet inception distance (FID) to measure the generation diversity of
our obstacle-guidance diffusion models,

$\text{FID}=||\mu_{R}-\mu_{G}||^{2}+\text{Tr}(\Sigma_{R}+\Sigma_{G}-2(\Sigma_{R}\Sigma_{G})^{\frac{1}{2}}),$
(10)

where $\mu_{R}$ and $\mu_{G}$ denote the feature-wise mean of the oracle and
generated trajectories; $\Sigma_{R}$ and $\Sigma_{G}$ are the covariance
matrix for the real and generated feature trajectories; $\text{Tr}(.)$ refers
to the trace operation in linear algebra. Notice that researchers widely use
the above FID score to quantify the realism and diversity in evaluating the
performance of generative models[31]. Here, we focus on the trajectory data
and use pre-trained VAE model on our collected dataset. Therefore, we use the
mean $\mu_{G}$ and variance $\Sigma_{G}$ calculated from the VAE model for the
measurement of the FID score.

##  IV Results

We use comprehensive experiments to evaluate our proposed APEX algorithm.
Specifically, our experiments seek to investigate the following questions:

  1. 1.

Can the ambidextrous dual-arm robots successfully complete the manipulation
tasks using APEX?

  2. 2.

What are the qualitative advantages and the essential trade-off of APEX
compared to SOTA algorithms?

  3. 3.

Why the obstacle guidance and closed-loop fashion are important for safe
planning?

  4. 4.

Are the trajectories generated by our algorithm diverse?

###  IV-A Successful and smooth ambidextrous dual-arm robotic manipulation
trajectory

We first presented horizontal and vertical task demos to visualize the
trajectories generated by our proposed algorithm. Fig. 4 presented the
successful ambidextrous dual-arm robotic manipulation performance in both
vertical and horizontal tasks. Here, we took the horizontal tasks for example.
We observed that the two arm-hand robots were far away and randomly placed in
the configuration space at the beginning (see Fig. 4(f)). After our diffusion
model generated a trajectory, two robots gradually began to align resulting in
a smooth trajectory (see Fig. 4(g)). During the middle point of the alignment,
an obstacle was imposed manually, which may resulted in the potential
collision (see Fig. 4(h)-(i)). Therefore, our robots stopped for avoiding any
collision and generated a new trajectory, which lifted the two arms up to
avoid the imposed hard obstacles (see Fig. 4(h)-(i)). Finally, our two arm-
hand robots successfully realized horizontal alignment, which completed the
manipulation task ((see Fig. 4(j)). Similar successful and smooth ambidextrous
dual-arm robotic manipulation trajectories are observed in our vertical tasks
(see Fig. 4(a)-(e)).

Meanwhile, we also looked into the denoising diffusion process in our APEX
algorithm. The beginning manipulation trajectory ($t=0$) was randomly sampled
as a Gaussian image, which led to a rigid and aimless trajectory. Then, the
denoising diffusion process gradually cleaned the noise trajectory (snapshots
at $t=64$ and $t=128$). Finally, the cleaned trajectory enabled a successful
completion of the task and the planar movement of the arm-hand robots was
smooth ($t=256$). The above two illustrations of manipulation tasks provide
interesting collision-free trajectory generation results and show promising
advantages of our proposed generative diffusion model.

###  IV-B Comparison results with SOTA algorithms

Next, we comprehensively evaluated our proposed algorithms for achieving
various vertical and horizontal tasks from different initial positions and
orientations. Further, to illustrate the potential advantages of our proposed
algorithm, we compare our algorithm with other SOTA motion planning algorithms
to evaluate the potential advantages.

Figure 6:  (a) Collision While doing horizontal alignment task, (b) Two arms
are stuck in the middle and can not replan, (c) Incorrect orientation position
for vertical aloignment task Figure 7:  (a) Comparison of failure ratio with
SOTA algorithms, (b) Comparison of the smoothness with SOTA algorithms.

We started by looking some failure cases of both vertical and horizontal
alignments using other algorithms. Fig. 6 provides various failure examples.
For example, Fig. 6(b) showed that the traditional RRT seemed simply generated
half of the trajectories, where two robotic arms stopped during the alignment;
Fig. 6(a) showed that the imitation learning algorithm can not deal with the
obstacles, leading to a collision; Fig. 6(c) showed that how DAMON failed to
complete the alignment task and ended in a faulty configuration for box
placement task. In total, fig. 7(a) gave the comprehensive comparison of
different algorithms in executing vertical and horizontal tasks. We observed
that our prior work DAMON and the most advanced imitation learning (IL)
algorithms achieved better performance compared to the RRT and GPMP (Failure
ratio: DAMON 32.65 v.s. IL 25.79 v.s. RRT 48.12 v.s. GPMP 39.26). However, our
proposed diffusion-based generative models achieved extraordinary performance
with the lowest failure ratio across both vertical and horizontal tasks
(Failure ratio (avg): vertical 5.57 and horizontal 8.95). We argue that the
possible reason why the vertical failure ratio is even lower than the
horizontal task is due to the more complicated orientation alignment in
horizontal tasks. For example, the vertical alignment task mimics the stacking
manipulation, which does not involve orientation manipulations, whereas
horizontal alignment tasks such as ball-insertion-in-a-cup require more
complicated orientational manipulations. Above all, our APEX algorithm
achieved the best alignment performance across all comparison algorithms and
tasks.

Figure 8: Snapshots of hardware demonstration. (a)-(c) Without guidance, the
robots can only operate under small obstacles and partially complete the task.
(d)-(e)The right robotic arm collides with a larger obstacle can not complete
the task.

Second, smoothness is also very important for avoiding awkward robotic
manipulation behaviors. Prior demos illustrate that our diffusion models can
generate smooth trajectories. One possible mechanism is the reverse diffusion
process, where we use the trained noise prediction network to gradually
denoise from a pure Gaussian noise trajectory. Advanced imitation learning
(IL) algorithms also have mechanisms to ensure the smoothness of trajectory
since the goal of IL is to mimic the training trajectories with mean square
error loss. Fig. 7(b) gave the overall smoothness metric in our experiments,
where we observed that our diffusion models achieved the smallest value
indicating the most smooth manipulation trajectories ($S_{r}$ ours: 2.36 v.s.
DAMON 6.25 v.s. IL 5.23 v.s. RRT 8.72 v.s. GPMP 6.87).

In total, the above experimental results showed that our proposed diffusion
models have many promising advantages such as lower failure rate and smooth
trajectory, and outperformed other algorithms.

###  IV-C Importance of obstacle guidance as real-time feedback to avoid
obstacles and achieve alignment

In Methods section III-C, we emphasized that integrating the obstacle guidance
technique is important as it functions as the real-time closed-loop feedback
condition to guide the generation of safe and feasible trajectories.
Therefore, we use an ablation study to comprehensively evaluate the
functionality of the obstacle guidance component.

Figure 9:  Comparison of Failure Ratio with APEX and guidance-free stable
diffusion algorithm for static and dynamic obstacle

Similar as the prior section, we first provide the manipulation demos for
dynamical obstacles. Here we focused on two algorithms, our proposed algorithm
and our algorithm without the obstacle guidance component. From the demos (see
Fig. 8(a)-(c)), we observed that if the obstacles were small, it was still
possible for the no-guidance diffusion model to generate a safe and feasible
manipulation trajectory. It can be understood if the sampler was lucky enough
since the obstacles only occupied a small area in the configuration space.
However, when we increased the size and number of obstacles or even enabled
dynamical obstacles, the chance level using the diffusion model without
guidance dropped drastically, leading to the collision trajectories (see
Figure 8(e)). On the contrary, our obstacle-guidance diffusion models can
incorporate real-time video sensor images as the conditional guidance for the
generation of future potential collision-free trajectories, which consistently
resulted in lower failure ratios even in dynamical obstacle cases. We
summarized the experimental results in Fig. 9, where our methods achieved a
significantly lower failure ratio compared to the no-guidance diffusion model
(Failure ratio in static for the largest obstacle: ours 6.56 v.s. no-guidance
diffusion model 67.19; Failure ratio in dynamic and large obstacle: ours 9.36
v.s. no-guidance diffusion model 98.45). We further showed in Fig. 9 that the
failure ratio for the no-guidence diffusion model increased as the obstacle
volume increased. On the contrary, APEX showed consistently low failure ratio
across static and dynamic obstacles. Thus, our ablation study confirmed the
essential contribution of the obstacle guidance technique in generating safe
and feasible ambidextrous dual-arm robotic manipulation trajectories.

###  IV-D Diversity of the trajectory generation

Last, we show two interesting findings. It is believed that by using different
initial Gaussian noise, the diffusion models can generate various types of
images or videos. Therefore, we also test our obstacle-guidance diffusion
models by giving different initial Gaussian noise in the sampling process. We
observed that our models indeed can generate multiple feasible and collision-
free manipulation trajectories (see Fig. 10(a)), meaning that our model
essentially learned complicated manipulation-task dependent distributions and
realized effective multi-modal sampling from the learned distribution.
Compared with other algorithms, our methods still have the most diverse
trajectory generation performance. Further, we compute the FID for measurement
of the generation diversity. Our FID results also confirmed that our proposed
obstacle-guidance diffusion achieved the highest score across all the
comparison algorithms (see Fig 10(b)). Second, regarding to the FID score
comparison between our obstacle-guidance model and no-guidance diffusion
model. We observed that our obstacle-guidance model has the lower FID score
but faster trajectory generation speed (the FID score: ours 21.51 v.s. no-
guidance diffusion model 48.63; the computational time ours 8.36s v.s. no-
guidance diffusion model 19.63s), which revealed another trade-off that we
sacrifice part of the generation diversity but both improve the sampling speed
and ensure the feasibility and safety of the generated trajectories.

Figure 10:  (a) Several collision-free trajectories are generated from APEX.
The $\bigoplus$ denotes the starting position and $\bigtriangledown$ denotes
the goal position. The upper and lower panels are in X and Y coordinations.
(b) FID comparison.

##  V Discussion and Conclusion

Effectively coordinating dual-arm movements while controlling 5-finger robotic
hands to perform manual tasks poses serious challenges for real-time execution
in a cluttered environment. APEX successfully leverages deep generative models
for robotic motion planning to synthesize diverse feasible trajectories
precisely and accurately. This achievement leads to low failure rates and
flexible planning trajectories, fundamentally differing from traditional
robotic planning algorithms and prior imitation learning-based deep neural
networks.

APEX introduces three major innovations. Firstly, our task distillation
dramatically simplifies training costs and enhances algorithm efficiency, thus
facilitating adaptive obstacle avoidance, which proves crucial in addressing
dynamic obstacles. Secondly, the task demonstrations of APEX using latent
diffusion models [17], mainly consisting of a Variational Autoencoder (VAE)
and conventional U-Net structure, were trained and evaluated separately as the
initial trial of our algorithms. Lastly, to further ensure that the generated
trajectory is feasible and collision-free, we incorporate the obstacle-
guidance technique by utilizing real-time obstacle and target information to
construct conditional diffusion models.

APEX exhibits the capability to generate diverse feasible trajectories with
lower failure rates for completing both vertical and horizontal dual-arm
robotic manipulation tasks compared to state-of-the-art approaches. We
validate the effectiveness of our proposed algorithm through computer
simulations and experiments with ambidextrous dual-arm robotic systems. These
results offer promising prospects for the future development of ambidextrous
dual-arm robotics to tackle more intricate tasks. Given the generalizability
of our proposed algorithm, we also foresee future explorations in other
robotic systems such as robotic dogs [32].

## References

  * [1] M. Abbas _et al._ , “A systematic review on cooperative dual-arm manipulators: modeling, planning, control, and vision strategies,” _International Journal of Intelligent Robotics and Applications_ , vol. 7, no. 4, p. 683–707, Jul. 2023.
  * [2] X. Zhao _et al._ , “A dual-arm robot cooperation framework based on a nonlinear model predictive cooperative control,” _IEEE/ASME Transactions on Mechatronics_ , pp. 1–13, 2023.
  * [3] A. Dastider and M. Lin, “Damon: Dynamic amorphous obstacle navigation using topological manifold learning and variational autoencoding,” in _2023 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)_ , 2023, pp. 251–258.
  * [4] Y. He, M. Wu, and S. Liu, “A distributed optimal control framework for multi-robot cooperative manipulation in dynamic environments,” _Journal of Intelligent and Robotic Systems_ , vol. 105, no. 1, Apr. 2022. [Online]. Available: http://dx.doi.org/10.1007/s10846-022-01621-4
  * [5] C. Zhou _et al._ , “Topp-mpc-based dual-arm dynamic collaborative manipulation for multi-object nonprehensile transportation,” in _2022 International Conference on Robotics and Automation (ICRA)_ , 2022, pp. 999–1005.
  * [6] W. Shi _et al._ , “Obstacle avoidance path planning for the dual-arm robot based on an improved rrt algorithm,” _Applied Sciences_ , vol. 12, no. 8, 2022.
  * [7] N. Vahrenkamp _et al._ , “Humanoid motion planning for dual-arm manipulation and re-grasping tasks,” in _2009 IEEE/RSJ International Conference on Intelligent Robots and Systems_ , 2009, pp. 2464–2470.
  * [8] L. Liu _et al._ , “A collaborative control method of dual-arm robots based on deep reinforcement learning,” _Applied Sciences_ , vol. 11, no. 4, 2021.
  * [9] M. Alles and E. Aljalbout, “Learning to centralize dual-arm assembly,” _Frontiers in Robotics and AI_ , vol. 9, p. 830007, 2022.
  * [10] F. Xie _et al._ , “Deep imitation learning for bimanual robotic manipulation,” in _Advances in Neural Information Processing Systems_ , H. Larochelle _et al._ , Eds., vol. 33. Curran Associates, Inc., 2020, pp. 2327–2337.
  * [11] H. Kim, Y. Ohmura, and Y. Kuniyoshi, “Goal-conditioned dual-action imitation learning for dexterous dual-arm robot manipulation,” _IEEE Transactions on Robotics_ , pp. 1–20, 2024.
  * [12] ——, “Transformer-based deep imitation learning for dual-arm robot manipulation,” in _2021 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)_ , 2021, pp. 8965–8972.
  * [13] F.-A. Croitoru _et al._ , “Diffusion models in vision: A survey,” _IEEE Transactions on Pattern Analysis and Machine Intelligence_ , vol. 45, no. 9, pp. 10 850–10 869, 2023.
  * [14] J. Ho _et al._ , “Video diffusion models,” in _Advances in Neural Information Processing Systems_ , vol. 35. Curran Associates, Inc., 2022, pp. 8633–8646.
  * [15] P. Dhariwal and A. Nichol, “Diffusion models beat gans on image synthesis,” in _Advances in Neural Information Processing Systems_ , M. Ranzato, A. Beygelzimer, Y. Dauphin, P. Liang, and J. W. Vaughan, Eds., vol. 34. Curran Associates, Inc., 2021, pp. 8780–8794.
  * [16] J. Ho, A. Jain, and P. Abbeel, “Denoising diffusion probabilistic models,” _Advances in neural information processing systems_ , vol. 33, pp. 6840–6851, 2020.
  * [17] R. Rombach _et al._ , “High-resolution image synthesis with latent diffusion models,” in _Proceedings of the IEEE/CVF conference on computer vision and pattern recognition_ , 2022, pp. 10 684–10 695.
  * [18] O. Ronneberger, P. Fischer, and T. Brox, “U-net: Convolutional networks for biomedical image segmentation,” in _Medical image computing and computer-assisted intervention–MICCAI 2015: 18th international conference, Munich, Germany, October 5-9, 2015, proceedings, part III 18_. Springer, 2015, pp. 234–241.
  * [19] I. Kapelyukh, V. Vosylius, and E. Johns, “Dall-e-bot: Introducing web-scale diffusion models to robotics,” _IEEE Robotics and Automation Letters_ , vol. 8, no. 7, pp. 3956–3963, 2023.
  * [20] T. Power _et al._ , “Sampling constrained trajectories using composable diffusion models,” in _IROS 2023 Workshop on Differentiable Probabilistic Robotics: Emerging Perspectives on Robot Learning_ , 2023.
  * [21] M. Janner _et al._ , “Planning with diffusion for flexible behavior synthesis,” in _International Conference on Machine Learning_ , 2022.
  * [22] J. Carvalho _et al._ , “Motion planning diffusion: Learning and planning of robot motions with diffusion models,” in _2023 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)_ , 2023, pp. 1916–1923.
  * [23] T. Yoneda _et al._ , “To the noise and back: Diffusion for shared autonomy,” in _Robotics: Science and Systems XIX, Daegu, Republic of Korea, July 10-14, 2023_ , 2023.
  * [24] Z. Sun _et al._ , “Bifa-yolo: A novel yolo-based method for arbitrary-oriented ship detection in high-resolution sar images,” _Remote Sensing_ , vol. 13, no. 21, 2021.
  * [25] C. Chi _et al._ , “Diffusion policy: Visuomotor policy learning via action diffusion,” _ArXiv_ , vol. abs/2303.04137, 2023. [Online]. Available: https://api.semanticscholar.org/CorpusID:257378658
  * [26] M. Reuss _et al._ , “Goal conditioned imitation learning using score-based diffusion policies,” in _Robotics: Science and Systems_ , 2023.
  * [27] J. Ho and T. Salimans, “Classifier-free diffusion guidance,” _arXiv preprint arXiv:2207.12598_ , 2022.
  * [28] A. H. Khan _et al._ , “Obstacle Avoidance and Tracking Control of Redundant Robotic Manipulator: An RNN-Based Metaheuristic Approach,” _IEEE Transactions on Industrial Informatics_ , vol. 16, no. 7, pp. 4670–4680, 2020.
  * [29] O. Adiyatov and H. A. Varol, “A novel rrt*-based algorithm for motion planning in dynamic environments,” in _2017 IEEE International Conference on Mechatronics and Automation_ , 2017, pp. 1416–1421.
  * [30] M. Mukadam, X. Yan, and B. Boots, “Gaussian process motion planning,” in _2016 IEEE International Conference on Robotics and Automation (ICRA)_ , 2016, pp. 9–15.
  * [31] M. Heusel, H. Ramsauer, T. Unterthiner, B. Nessler, and S. Hochreiter, “Gans trained by a two time-scale update rule converge to a local nash equilibrium,” in _Proceedings of the 31st International Conference on Neural Information Processing Systems_ , ser. NIPS’17. Red Hook, NY, USA: Curran Associates Inc., 2017, p. 6629–6640.
  * [32] Y. Zhao _et al._ , “Intelligent control of multilegged robot smooth motion: A review,” _IEEE Access_ , vol. 11, pp. 86 645–86 685, 2023.