# On directed and undirected diameters of vertex-transitive graphs

Saveliy V. Skresanov

###### Abstract

A directed diameter of a directed graph is the maximum possible distance
between a pair of vertices, where paths must respect edge orientations, while
undirected diameter is the diameter of the undirected graph obtained by
symmetrizing the edges. In 2006 Babai proved that for a connected directed
Cayley graph on $n$ vertices the directed diameter is bounded above by a
polynomial in undirected diameter and $\log n$. Moreover, Babai conjectured
that a similar bound holds for vertex-transitive graphs. We prove this
conjecture of Babai, in fact, it follows from a more general bound for
connected relations of homogeneous coherent configurations. The main novelty
of the proof is a generalization of Ruzsa’s triangle inequality from additive
combinatorics to the setting of graphs.

##  1 Introduction

Given a (finite) connected directed graph $\Gamma$, let
$\overrightarrow{\mathrm{diam}}(\Gamma)$ denote the directed diameter, which
is the maximum directed distance between a pair of vertices of $\Gamma$. The
undirected diameter $\operatorname{diam}(\Gamma)$ is the maximum undirected
distance between a pair of vertices, that is, we forget about edge
orientations in $\Gamma$ when measuring distances. Clearly
$\operatorname{diam}(\Gamma)\leq\overrightarrow{\mathrm{diam}}(\Gamma)$.

In general, it is not possible to bound the directed diameter in terms of the
undirected diameter only, yet it is interesting how close these two quantities
are if the graph is symmetric enough. One of the classical examples when the
difference between the directed and undirected diameters manifests itself, is
the famous question of Babai about the diameters of Cayley graphs of finite
simple groups. Given a finite group $G$ and its generating set $S\subseteq G$,
recall that a Cayley graph $\mathrm{Cay}(G,S)$ is a directed graph with vertex
set $G$, where two vertices $x,y\in G$ are joined by a directed edge if $y=xg$
for some $g\in S$. Let $\log n$ denote the base-2 logarithm of $n$. Babai
proposed the following conjecture:

[4, Conjecture 1.7] _Given a nonabelian finite simple group $G$ generated by
$S\subseteq G$, we have_

$\operatorname{diam}(\mathrm{Cay}(G,S))\leq(\log|G|)^{C}$

_for some universal constant $C>0$._

Although this conjecture is still open, there have been a plethora of results
solving the conjecture in some particular cases and obtaining nontrivial
bounds for the diameter (see [11, 13, 7, 4, 2], to name a few). These works
often make heavy use of the fact that we may assume our generating set $S$ to
be closed under taking inverses, for example, the proof of [2] requires taking
commutators of group elements, i.e. words of the form $x^{-1}y^{-1}xy$ for
$x,y\in G$. Such a word does not correspond to a proper path in the directed
Cayley graph, so one has to work with undirected graphs instead.

Luckily, in 2006 Babai proved a result which resolved this issue for Cayley
graphs.

######  Proposition 1.1 ([1, Theorem 1.4]).

Let $\Gamma$ be a connected Cayley graph on $n$ vertices. Then
$\overrightarrow{\mathrm{diam}}(\Gamma)=O(\operatorname{diam}(\Gamma)^{2}(\log
n)^{3})$.

In particular, it immediately follows that if
$\operatorname{diam}(\mathrm{Cay}(G,S))\leq(\log|G|)^{C}$ for some group $G$
and a generating set $S$, then
$\overrightarrow{\mathrm{diam}}(\mathrm{Cay}(G,S))=O((\log|G|)^{2C+3})$, so it
is enough to solve Babai’s conjecture for undirected Cayley graphs only.

The proof of Proposition 1.1 relies on a result of Babai and Erdős [3] about
fast generating sets of finite groups, and a theorem of Babai and Szegedy on
expansion in vertex-transitive graphs [5]. Since Cayley graphs are vertex-
transitive, it is natural to ask if a similar bound on the directed diameter
holds for vertex-transitive graphs. To this end, Babai makes the following
conjecture:

[1, Conjecture 6.1] _Given a connected vertex-transitive graph $\Gamma$ on $n$
vertices, there exists a polynomial bound on
$\overrightarrow{\mathrm{diam}}(\Gamma)$ in terms of
$\operatorname{diam}(\Gamma)$ and $\log n$._

In the same paper Babai found such a bound under a condition that the
outdegree of $\Gamma$ is bounded. If $k$ is the outdegree of $\Gamma$, then in
[1, Theorem 1.1] it is proved that
$\overrightarrow{\mathrm{diam}}(\Gamma)=O(\operatorname{diam}(\Gamma)\cdot
k\log n)$ and in [1, Corollary 1.2] that
$\overrightarrow{\mathrm{diam}}(\Gamma)=O(\operatorname{diam}(\Gamma)^{2}\cdot
k\log k)$. If $\Gamma$ is edge-transitive, then by [1, Theorem 1.5] we have
$\overrightarrow{\mathrm{diam}}(\Gamma)=O(\operatorname{diam}(\Gamma)\log n)$,
so the conjecture holds in this case.

The main result of this paper is the solution of the above conjecture of Babai
on vertex-transitive graphs.

######  Theorem 1.2.

Let $\Gamma$ be a connected vertex-transitive graph on $n$ vertices. Then

$\overrightarrow{\mathrm{diam}}(\Gamma)=O(\operatorname{diam}(\Gamma)^{2}(\log
n)^{2}).$

Note that in the case of Cayley graphs our result improves Babai’s by a factor
of $\log n$.

We derive Theorem 1.2 as a corollary of a more general result about
homogeneous coherent configurations (also known as association schemes [6]).
Namely, in Theorem 4.1 we prove that the above bound for directed diameter
holds when $\Gamma$ is a connected relation of a homogeneous coherent
configuration. Since a vertex-transitive graph is a relation of a coherent
configuration corresponding to its full automorphism group, Theorem 1.2
follows at once.

To prove Theorem 4.1 we employ a vertex expansion bound for undirected
relations of homogeneous coherent configurations (Proposition 2.2), analogous
to the Babai-Szegedy bound [5] for undirected graphs. In order to relate the
vertex expansion of the original directed graph with expansion of its
symmetrization, we introduce the _Ruzsa triangle inequality for graphs_
(Theorem 3.1), which we think might be of independent interest. To state the
result, let $a,b\subseteq\Omega\times\Omega$ be some relations (or,
equivalently, directed graphs) on the set $\Omega$ and let
$ab\subseteq\Omega\times\Omega$ denote their product. Let
$b^{*}\subseteq\Omega\times\Omega$ denote the transposed relation, and let
$\|a\|$ be the maximum outdegree of a vertex in $a$ (we give precise
definitions of these notions in Sections 2 and 3). If
$a,b,c\subseteq\Omega\times\Omega$ and $b$ is regular, then

$\|ac\|\cdot\|b\|\leq\|ab\|\cdot\|b^{*}c\|.$

When $a,b,c$ are Cayley graphs, this gives the classical Ruzsa inequality for
groups [14], an indispensable tool in additive combinatorics. In Section 3 we
show how this can be used to bound the directed diameter when the underlying
coherent configuration has a certain commutativity condition (Proposition
3.4). For instance, if $\Gamma$ is a connected Cayley graph on $n$ vertices
over an abelian group, then

$\overrightarrow{\mathrm{diam}}(\Gamma)=O(\operatorname{diam}(\Gamma)\log\log
n).$

In Section 5 we show that in general it is not possible to bound the directed
diameter or directed girth in terms of the undirected diameter only, even in
the case of Cayley graphs over abelian groups. This answers two other
questions of Babai [1, Problems 6.4 and 6.5], and the proof relies on a
construction of Haight and Ruzsa [10, 15] of special subsets of cyclic groups.

The structure of the paper is as follows. In Section 2 we give preliminaries
on coherent configurations and prove a generalization of the Babai-Szegedy
bound [5] to relations of homogeneous coherent configurations (Proposition
2.2). In Section 3 we prove the Ruzsa inequality for graphs (Theorem 3.1) and
give an application for coherent configurations with a commutativity condition
(Proposition 3.4). The main result is proved in Section 4, and in Section 5 we
give examples of Cayley graphs with bounded undirected diameter and unbounded
directed diameter and girth.

##  2 Preliminaries

Let $\Omega$ be a finite set. Given two relations
$a,b\subseteq\Omega\times\Omega$ let

$ab=\\{(\alpha,\beta)\in\Omega\times\Omega\mid(\alpha,\gamma)\in
a,\,(\gamma,\beta)\in b\text{ for some }\gamma\in\Omega\\}$

denote the product relation. We write
$1_{\Omega}=\\{(\alpha,\alpha)\mid\alpha\in\Omega\\}$ for the diagonal
relation, and
$a^{*}=\\{(\beta,\alpha)\in\Omega\times\Omega\mid(\alpha,\beta)\in a\\}$ for
the transposition of $a$. Note that $(a^{*})^{*}=a$ and $(ab)^{*}=b^{*}a^{*}$.

We will view _graphs_ on the vertex set $\Omega$ as relations on $\Omega$, and
will use these two terms interchangeably. All our graphs are directed by
default, and we say that a graph $a\subseteq\Omega\times\Omega$ is
_undirected_ , if $a=a^{*}$. If $a$ is a connected graph on $\Omega$, we write
$\overrightarrow{\mathrm{diam}}(a)$ for the _directed diameter_ of $a$, that
is, the largest possible distance between a pair of vertices in $a$, where
paths between vertices must preserve edge orientations. Similarly,
$\operatorname{diam}(a)$ denotes the _undirected diameter_ of $a$, which is
the largest distance between a pair of vertices where paths are not required
to preserve edge orientations; in other words,
$\operatorname{diam}(a)=\overrightarrow{\mathrm{diam}}(a\cup a^{*})$.

Let $S$ be a partition of $\Omega\times\Omega$ into relations. We say that a
tuple $\operatorname{\mathfrak{X}}=(\Omega,S)$ is a homogeneous coherent
configuration or, shortly, a _scheme_ , if the following holds [9, Definition
2.1.3]:

  1. 1.

$1_{\Omega}\in S$,

  2. 2.

If $a\in S$, then $a^{*}\in S$,

  3. 3.

For any $a,b,c\in S$ and any $(\alpha,\beta)\in a$, the number

$|\\{\gamma\in\Omega\mid(\alpha,\gamma)\in b,\,(\gamma,\beta)\in c\\}|$

does not depend on the choice of $(\alpha,\beta)\in a$.

The set $S=S(\operatorname{\mathfrak{X}})$ is the set of _basis relations_ of
$\operatorname{\mathfrak{X}}$, and we define
$S^{\cup}=S^{\cup}(\operatorname{\mathfrak{X}})$ as the set of all unions of
basis relations of $\operatorname{\mathfrak{X}}$, in particular, $S\subseteq
S^{\cup}$. It follows from the definition of a scheme that $S^{\cup}$ is
closed under taking products and transpositions of relations [9, Proposition
2.1.4]. Moreover, if $a\in S^{\cup}$ then the indegree and outdegree of any
vertex of $a$ are the same and do not depend on the vertex [9, Definition
2.1.10 and Corollary 2.1.13]. In particular, all graphs (relations) from
$S^{\cup}$ are regular.

Given a transitive permutation group $G$ on $\Omega$ one can construct a
scheme as follows (see also [9, Definition 2.2.3]). We set
$\operatorname{\mathfrak{X}}=(\Omega,S)$ where $S$ is the partition of the set
$\Omega\times\Omega$ into orbits of $G$ in its natural action on pairs; one
can easily check that $\operatorname{\mathfrak{X}}$ is indeed a scheme. If
$\Gamma$ is a vertex-transitive graph (for example, a Cayley graph) on
$\Omega$ with the full automorphism group $G$, then $\Gamma$ can be
partitioned into orbits of $G$ and hence $\Gamma\in
S^{\cup}(\operatorname{\mathfrak{X}})$.

The following lemma is a generalization of the third property from the
definition of a scheme.

######  Lemma 2.1 ([9, Exercise 2.7.25]).

Let $\operatorname{\mathfrak{X}}=(\Omega,S)$ be a scheme, and let $r$,
$r_{1},\dots,r_{m-1}\in S$, $m\geq 2$ and $(u,w)\in r$. Then the number of
tuples $(v_{1},\dots,v_{m})\in\Omega^{m}$ such that $(v_{1},v_{m})=(u,w)$ and
$(v_{i},v_{i+1})\in r_{i}$, $i=1,\dots,m-1$ does not depend on the choice of
$(u,w)\in r$.

Let $b\subseteq\Omega\times\Omega$ be an undirected graph on $\Omega$. For a
subset $T\subseteq\Omega$ let $\partial_{b}(T)$ denote the set of vertices
outside of $T$ adjacent in $b$ to a vertex in $T$, i.e.

$\partial_{b}(T)=\\{\beta\in\Omega\setminus T\mid\alpha\in
T,\,(\alpha,\beta)\in b\\}.$

Babai and Szegedy [5, Theorem 2.2] showed that for a connected vertex-
transitive graph $b$ and $T\subseteq\Omega$, $0<|T|\leq|\Omega|/2$, the vertex
expansion ratio $|\partial_{b}(T)|/|T|$ can be bounded from below in terms of
$\operatorname{diam}(b)$. To prove Theorem 4.1, we show that this bound holds
in the setting of schemes. The argument is essentially the same as in [5], but
requires a few technicalities to count paths between vertices in relations of
schemes.

######  Proposition 2.2.

Let $\operatorname{\mathfrak{X}}=(\Omega,S)$ be a scheme, and let $b\in
S^{\cup}$ be a connected relation with $b=b^{*}$. For any nonempty subset $T$
of $\Omega$ we have

$\frac{|\partial_{b}(T)|}{|T|}\geq\frac{2(1-|T|/|\Omega|)}{\operatorname{diam}(b)+|T|/|\Omega|}.$

In particular, if $|T|\leq|\Omega|/2$, then

$\frac{|\partial_{b}(T)|}{|T|}\geq\frac{2}{2\operatorname{diam}(b)+1}.$

###### Proof.

We may view $b$ as an undirected graph on $\Omega$. For $x,y\in\Omega$ let
$d(x,y)$ denote the distance between $x$ and $y$ in $b$. A path
$x_{0},x_{1},\dots,x_{m}$ in $b$ will be called a geodesic if
$m=d(x_{0},x_{m})$. Note that a geodesic is an ordered sequence of points, so
$x_{m},\dots,x_{1},x_{0}$ is a different geodesic.

By [9, Theorem 2.6.7] the distance-$i$ graph
$\\{(u,v)\in\Omega\times\Omega\mid d(u,v)=i\\}$ lies in $S^{\cup}$, in
particular, the distance between points $x$ and $y$ depends only on the
relation where $(x,y)$ lies.

Let $p(x,y)$ denote the number of geodesics between $x$ and $y$. If $z$ is
some vertex, then we claim that the number

$P_{z}=\sum_{x,y\in V}\frac{1}{p(x,y)}|\\{L\mid L\text{ is a geodesic from
}x\text{ to }y\text{ passing through }z\\}|$

does not depend on the choice of $z\in\Omega$. Indeed, by Lemma 2.1, the
number $p(x,y)$ depends only on the relation where $(x,y)$ lies. The number of
geodesics from $x$ to $y$ passing through $z$ can be expressed as

$N_{z}(x,y)=\begin{cases}p(x,z)\cdot p(z,y),&\text{ if
}d(x,z)+d(z,y)=d(x,y),\\\ 0,&\text{ otherwise.}\end{cases}$

By the paragraph above, this number depends only on the relations where
$(x,z)$, $(z,y)$ and $(x,y)$ lie. Therefore we have the following formula:

$P_{z}=\sum_{r,s,t\in S}\sum_{\begin{subarray}{c}x,y\in\Omega,\\\ (x,z)\in
r,(z,y)\in s,(x,y)\in t\end{subarray}}\frac{1}{p(x,y)}N_{z}(x,y).$

By applying Lemma 2.1 to the path $z,x,y,z$, we see that the number of tuples
$(x,y)\in t$ satisfying $(x,z)\in r$, $(z,y)\in s$ does not depend on the
choice of $z$. Hence $P=P_{z}$ does not depend on the choice of $z$, as
claimed.

Set $n=|\Omega|$. We claim that

$n\cdot P=\sum_{x,y\in\Omega}(d(x,y)+1).$

Since $P$ does not depend on the choice of $z\in\Omega$ we have

$n\cdot P=\sum_{z\in\Omega}\sum_{x,y\in\Omega}\frac{1}{p(x,y)}|\\{L\mid
L\text{ is a geodesic from }x\text{ to }y\text{ passing through }z\\}|\\\
=\sum_{x,y\in\Omega}\frac{1}{p(x,y)}\sum_{z\in\Omega}|\\{L\mid L\text{ is a
geodesic from }x\text{ to }y\text{ passing through }z\\}|.$

There are $d(x,y)+1$ vertices in a geodesic from $x$ to $y$, and there are
$p(x,y)$ such geodesics, hence

$\sum_{x,y\in\Omega}\frac{1}{p(x,y)}\sum_{z\in\Omega}|\\{L\mid L\text{ is a
geodesic from }x\text{ to }y\text{ passing through }z\\}|\\\
=\sum_{x,y\in\Omega}\frac{1}{p(x,y)}\cdot(d(x,y)+1)p(x,y)=\sum_{x,y\in\Omega}(d(x,y)+1),$

which proves the claim.

Now we are ready to prove the expansion bound. Let $T$ be a nonempty subset of
$\Omega$. Consider a set of pairs

$K=(T\times(\Omega\setminus T))\cup((\Omega\setminus
T)\times(T\cup\partial_{b}(T))).$

A path between $T$ and $\Omega\setminus T$ must intersect $\partial_{b}(T)$,
hence

$|K|=\sum_{(x,y)\in K}\frac{1}{p(x,y)}|\\{L\mid L\text{ is a geodesic from
}x\text{ to }y\text{ through }\partial_{b}(T)\\}|.$

We extend summation to the whole of $\Omega$ and derive

$|K|\leq\sum_{x,y\in\Omega}\frac{1}{p(x,y)}|\\{L\mid L\text{ is a geodesic
from }x\text{ to }y\text{ through }\partial_{b}(T)\\}|\\\
\leq\sum_{x,y\in\Omega}\frac{1}{p(x,y)}\sum_{z\in\partial_{b}(T)}|\\{L\mid
L\text{ is a geodesic from }x\text{ to }y\text{ through }z\\}|\\\
=\sum_{z\in\partial_{b}(T)}\sum_{x,y\in\Omega}\frac{1}{p(x,y)}|\\{L\mid
L\text{ is a geodesic from }x\text{ to }y\text{ through }z\\}|\\\
=\sum_{z\in\partial_{b}(T)}P=|\partial_{b}(T)|\cdot
P=\frac{|\partial_{b}(T)|}{n}\sum_{x,y\in\Omega}(d(x,y)+1)\leq
n\cdot|\partial_{b}(T)|\cdot(\operatorname{diam}(b)+1).$

To compute the size of $K$, recall that $T$ and $\partial_{b}(T)$ are
disjoint, hence

$|K|=|T\times(\Omega\setminus T)|+|(\Omega\setminus
T)\times(T\cup\partial_{b}(T))|=(n-|T|)(2|T|+|\partial_{b}(T)|).$

After substituting in the inequality above and dividing by $n|T|$ we derive

$\left(1-\frac{|T|}{n}\right)\left(2+\frac{|\partial_{b}(T)|}{|T|}\right)\leq\frac{\partial_{b}(T)}{|T|}(\operatorname{diam}(b)+1).$

The claimed result follows after rearranging terms in the inequality. ∎

We note that a similar bound for the edge expansion of basis relations of
coherent configurations was proved in [12, Proposition 2.8].

##  3 Ruzsa inequality for graphs

One of the central tools in additive combinatorics is the Ruzsa triangle
inequality [14]. Let $G$ be an arbitrary group. Given subsets $A,B\subseteq G$
let $AB=\\{ab\mid a\in A,b\in B\\}$ denote the product set and let
$A^{-1}=\\{a^{-1}\mid a\in A\\}$ be the inverse set. If $A,B,C\subseteq G$ are
finite subsets, then the Ruzsa triangle inequality claims that

$|AC|\cdot|B|\leq|AB|\cdot|B^{-1}C|.$

The naming stems from the fact that Ruzsa’s inequality implies that the
function

$d(A,B)=\log\frac{|AB^{-1}|}{(|A|\cdot|B|)^{1/2}}$

obeys the usual triangle inequality $d(A,C)\leq d(A,B)+d(B,C)$.

The proof of this beautiful result is rather simple: we construct an injective
mapping $f:AC\times B\to AB\times B^{-1}C$ in the following manner. For all
$x\in AC$ fix some decomposition $x=a_{x}c_{x}$, $a_{x}\in A$, $c_{x}\in C$.
Now for $b\in B$ set $f(x,b)=(a_{x}b,\,b^{-1}c_{x})$. This map is indeed
injective, since if $f(x,b)=(y,z)$ then
$x=a_{x}c_{x}=(a_{x}b)(b^{-1}c_{x})=yz$, and $b=(a_{x})^{-1}y$; in other
words, one can recover $x$ and $b$ from $y$ and $z$.

We will now show that essentially the same argument applies to finite graphs.
Let $\Omega$ be some finite set. Given a relation
$a\subseteq\Omega\times\Omega$ and $\omega\in\Omega$, let $\omega
a=\\{\beta\in\Omega\mid(\omega,\beta)\in a\\}$ denote the neighborhood of
$\omega$ in $a$. For a subset $T\subseteq\Omega$ we similarly define
$Ta=\\{\beta\in\Omega\mid(\alpha,\beta)\in a,\,\alpha\in T\\}$.

To make our results visually closer to analogous statements from additive
combinatorics, we will write $\|a\|$ for the maximum outdegree of a relation
$a\subseteq\Omega\times\Omega$, i.e. $\|a\|=\max_{\omega\in\Omega}|\omega a|$.
For any relations $a,b\subseteq\Omega\times\Omega$ we trivially have
$\|ab\|\leq\|a\|\cdot\|b\|$. We say that the relation $a$ is _regular_ , if
$|\omega a|$ does not depend on the choice of $\omega\in\Omega$.

######  Theorem 3.1 (Ruzsa triangle inequality for graphs).

Let $\Omega$ be a finite set, and let $a,b,c\subseteq\Omega\times\Omega$. If
$b$ is regular, then

$\|ac\|\cdot\|b\|\leq\|ab\|\cdot\|b^{*}c\|.$

###### Proof.

Fix a point $\omega\in\Omega$ such that $\|ac\|=|\omega ac|$. Set $m=\|ac\|$
and $k=\|b\|$. Then $m=|\omega ac|$, so
$\\{\gamma_{1},\dots,\gamma_{m}\\}=\omega ac$ for some necessarily distinct
points $\gamma_{i}$. Choose points $\alpha_{i}$, $i=1,\dots,m$, such that
$(\omega,\alpha_{i})\in a$ and $(\alpha_{i},\gamma_{i})\in c$. For each
$i\in\\{1,\dots,m\\}$ choose $k$ distinct points $\beta_{i1},\dots,\beta_{ik}$
such that $(\alpha_{i},\beta_{ij})\in b$ for all $i=1,\dots,m$, $j=1,\dots,k$.

Define a map $f:\\{1,\dots,m\\}\times\\{1,\dots,k\\}\to\Omega\times\Omega$ by
the rule $f(i,j)=(\beta_{ij},\gamma_{i})$. Let $I=\\{f(i,j)\mid
i=1,\dots,m,\,j=1,\dots,k\\}$ be the image of that map. Then

$I=\bigcup_{\beta\in\omega
ab}\\{f(i,j)\mid\beta_{ij}=\beta,\,i=1,\dots,m,\,j=1,\dots,k\\}.$

Observe that sets in that union are disjoint, therefore

$|I|=\sum_{\beta\in\omega
ab}|\\{\gamma_{i}\mid\beta_{ij}=\beta,\,i=1,\dots,m,\,j=1,\dots,k\\}|.$

Since $(\beta_{ij},\alpha_{i})\in b^{*}$ and $(\alpha_{i},\gamma_{i})\in c$,
we have $\gamma_{i}\in\beta_{ij}b^{*}c$. Hence

$|I|\leq\sum_{\beta\in\omega ab}|\\{\gamma_{i}\in\beta b^{*}c\mid
i=1,\dots,m\\}|\leq\sum_{\beta\in\omega
ab}\|b^{*}c\|\leq\|ab\|\cdot\|b^{*}c\|.$

Now we show that $f$ is injective. Suppose $f(i,j)=f(i^{\prime},j^{\prime})$
for some $i\in\\{1,\dots,m\\}$ and $j\in\\{1,\dots,k\\}$. Then
$\beta_{ij}=\beta_{i^{\prime}j^{\prime}}$ and
$\gamma_{i}=\gamma_{i^{\prime}}$. Last equality implies $i=i^{\prime}$, so
$\beta_{ij}=\beta_{ij^{\prime}}$ and $j=j^{\prime}$ follows.

Since $f$ is injective, we have $m\cdot k\leq|I|$ which is the desired
inequality. ∎

As all relations of a scheme are regular, we have the following immediate
corollary.

######  Corollary 3.2 (Ruzsa triangle inequality for schemes).

Let $\operatorname{\mathfrak{X}}$ be a scheme and $a,b,c\in
S^{\cup}(\operatorname{\mathfrak{X}})$. Then

$\|ac\|\cdot\|b\|\leq\|ab\|\cdot\|b^{*}c\|.$

To illustrate how this can be used, we apply Ruzsa’s inequality to bound the
directed diameter in schemes with a certain commutativity condition.

######  Lemma 3.3.

For a scheme $\operatorname{\mathfrak{X}}$ and $a,b\in
S^{\cup}(\operatorname{\mathfrak{X}})$ we have

$\|aa^{*}\|^{1/2}\cdot\|b\|^{1/2}\leq\|ab\|.$

###### Proof.

Ruzsa’s inequality gives
$\|aa^{*}\|\cdot\|b\|\leq\|ab\|\cdot\|b^{*}a^{*}\|=\|ab\|^{2}$, where the last
equality uses the fact that $\|c\|=\|c^{*}\|$ for any $c\in
S^{\cup}(\operatorname{\mathfrak{X}})$. ∎

Note that if $a$ is a connected relation from
$S^{\cup}(\operatorname{\mathfrak{X}})$ for some scheme
$\operatorname{\mathfrak{X}}$ on $\Omega$, then
$\overrightarrow{\mathrm{diam}}(a)$ is equal to the smallest $k$ such that

$(a\cup 1_{\Omega})^{k}=\underbrace{(a\cup 1_{\Omega})\cdot\dots\cdot(a\cup
1_{\Omega})}_{k\text{ times}}=\Omega\times\Omega.$

Here we used that $1_{\Omega}$ acts as a multiplicative identity, i.e.
$a1_{\Omega}=1_{\Omega}a=a$. In its turn, $\operatorname{diam}(a)$ is equal to
the smallest $k$ such that $(a\cup a^{*}\cup
1_{\Omega})^{k}=\Omega\times\Omega$.

Observe also that if $a\in S^{\cup}(\operatorname{\mathfrak{X}})$ is such that
$\|a\|>n/2$ where $n=|\Omega|$, then $\|a^{*}\|>n/2$, and
$aa=\Omega\times\Omega$ by pigeonhole principle.

######  Proposition 3.4.

Let $\operatorname{\mathfrak{X}}$ be a scheme on $n$ points and let $a\in
S^{\cup}(\operatorname{\mathfrak{X}})$ be a connected relation such that
$aa^{*}=a^{*}a$. Then
$\overrightarrow{\mathrm{diam}}(a)=O(\operatorname{diam}(a)\log\log n)$.

###### Proof.

Set $k=\operatorname{diam}(a)$. We may always assume that $1_{\Omega}\subseteq
a$, so $(a\cup a^{*})^{k}=\Omega\times\Omega$. By expanding the brackets and
using commutativity we see that $a^{k}(a^{*})^{k}=\Omega\times\Omega$, in
particular, $\|a^{k}(a^{*})^{k}\|=n$. Since $(a^{*})^{k}=(a^{k})^{*}$ we have
$\|a^{k}(a^{k})^{*}\|=n$ and thus $\|a^{k}\|\geq n^{1/2}$.

By Lemma 3.3, for any $m\geq 2$ we have

$\|a^{m\cdot k}\|\geq\|a^{k}(a^{k})^{*}\|^{1/2}\cdot\|a^{(m-1)k}\|^{1/2}\geq
n^{1/2}\cdot\|a^{(m-1)k}\|^{1/2},$

so by induction we derive

$\|a^{m\cdot k}\|\geq
n^{\frac{1}{2}+\frac{1}{4}+\dots+\frac{1}{2^{m}}}=n^{1-\frac{1}{2^{m}}},$

for any positive integer $m$. Now set $m=\lceil\log\log n\rceil+1$. Then
$\|a^{m\cdot k}\|>n/2$ and hence $\|(a^{m\cdot k})^{*}\|>n/2$, so $a^{2m\cdot
k}=\Omega\times\Omega$. Therefore

$\overrightarrow{\mathrm{diam}}(a)\leq 2\operatorname{diam}(a)(\lceil\log\log
n\rceil+1),$

as claimed. ∎

A Cayley graph can be viewed as a relation of a certain _Cayley scheme_ [9,
Definition 2.4.1], and the condition $aa^{*}=a^{*}a$ of the proposition above
simply means that the generating set of the Cayley graph must commute with its
inverse. Hence the above proposition applies to Cayley graphs over abelian
groups or, more generally, to Cayley graphs with normal connection sets, so we
have a considerable improvement to Babai’s bound in these cases. Connected
relations of _commutative schemes_ [9, Section 2.3.1] also satisfy the
conditions of the proposition.

##  4 Proof of the main result

Theorem 1.2 is a consequence of the following more general result about
relations of schemes.

######  Theorem 4.1.

Let $\operatorname{\mathfrak{X}}=(\Omega,S)$ be a scheme on $n=|\Omega|$
points, and let $a\in S^{\cup}$ be a connected relation. Then

$\overrightarrow{\mathrm{diam}}(a)=O(\operatorname{diam}(a)^{2}(\log n)^{2}).$

###### Proof.

Without loss of generality we may assume that $1_{\Omega}\subseteq a$. Let
$b=a\cup a^{*}$ be the symmetrization of $a$.

Suppose $t\in S^{\cup}$ is such that $\|t\|\leq n/2$. Choose an arbitrary
point $\omega\in\Omega$, and set $T=\omega t$. For brevity, let
$d=\operatorname{diam}(a)=\operatorname{diam}(b)$. By Proposition 2.2,

$\frac{|\partial_{b}(T)|}{|T|}\geq\frac{2}{2d+1}\geq\frac{1}{2d}.$

As $1_{\Omega}\subseteq a$, we have $T\subseteq Ta$. Now,
$T\cup\partial_{b}(T)=Ta\cup Ta^{*}$, and since $T$ and $\partial_{b}(T)$ are
disjoint, we have $|T|+|\partial_{b}(T)|=|Ta\cup Ta^{*}|$. As $a\cup
a^{*}\subseteq aa^{*}$, we derive $|Ta\cup Ta^{*}|\leq|Taa^{*}|$. Since all
relations of a scheme are regular, we have $\|taa^{*}\|=|\omega taa^{*}|$ and
$\|t\|=|\omega t|$, hence

$\frac{\|taa^{*}\|}{\|t\|}=\frac{|\omega taa^{*}|}{|\omega
t|}=\frac{|Taa^{*}|}{|T|}\geq\frac{|T|+|\partial_{b}(T)|}{|T|}\geq
1+\frac{1}{2d}.$

Let $k$ be the smallest positive integer such that
$\|a^{k+1}\|\leq(1+\frac{1}{2d})^{1/2}\cdot\|a^{k}\|$. Notice that $k=O(d\log
n)$, indeed, if $\|a^{m+1}\|>(1+\frac{1}{2d})^{1/2}\|a^{m}\|$ for all $m<k$,
then $\|a^{k}\|>(1+\frac{1}{2d})^{(k-1)/2}$. Hence
$n>(1+\frac{1}{2d})^{(k-1)/2}$ and $k<1+4d\log n$.

We now apply Ruzsa’s triangle inequality for schemes to obtain

$\|taa^{*}\|\cdot\|a^{k}\|\leq\|taa^{k}\|\cdot\|(a^{k})^{*}a^{*}\|,$

and after dividing by $\|t\|\cdot\|a^{k}\|$ we get:

$\frac{\|taa^{*}\|}{\|t\|}\leq\frac{\|ta^{k+1}\|}{\|t\|}\cdot\frac{\|a^{k+1}\|}{\|a^{k}\|}\leq\frac{\|ta^{k+1}\|}{\|t\|}\cdot\left(1+\frac{1}{2d}\right)^{1/2}.$

This inequality together with ($\star$), implies that for any $t\in S^{\cup}$
with $\|t\|\leq n/2$ we have

$\frac{\|ta^{k+1}\|}{\|t\|}\geq\left(1+\frac{1}{2d}\right)^{1/2}.$

We repeatedly apply the inequality above for $t$ equal to $a^{k+1}$,
$a^{2(k+1)}$ etc., so if $\|a^{l(k+1)}\|\leq n/2$ for some $l$, then

$\|a^{(l+1)(k+1)}\|\geq\left(1+\frac{1}{2d}\right)^{(l+1)/2}.$

Therefore for some $m=O(d\log n)$ we have $\|a^{m(k+1)}\|>n/2$. As we noted
earlier, this implies $a^{2m(k+1)}=\Omega\times\Omega$. Therefore
$\overrightarrow{\mathrm{diam}}(a)\leq 2m(k+1)=O(d^{2}(\log n)^{2})$ proving
the claim. ∎

If $\Gamma$ is a connected vertex-transitive graph on $\Omega$, then as
mentioned in Section 2, its full automorphism group induces a scheme on
$\Omega$ such that $\Gamma$ is a relation of that scheme. This immediately
implies that the proposition above applies to $\Gamma$ and hence Theorem 1.2
follows.

It is interesting to know whether one can lower the exponent of
$\operatorname{diam}(\Gamma)$ in the upper bound. To this end, Babai states
the following problem:

[1, Conjecture 6.3] _Given a connected vertex-transitive graph $\Gamma$ on $n$
vertices, do we have
$\overrightarrow{\mathrm{diam}}(\Gamma)=O(\operatorname{diam}(\Gamma)(\log
n)^{C})$ for some universal constant $C$?_

As far as the author is aware, this is not known even for Cayley graphs. Note
that if one drops vertex-transitivity, then the directed diameter can grow
quadratically in terms of the undirected diameter: for every $d\geq 1$ Chvátal
and Thomassen [8, Theorem 4] constructed an undirected graph of diameter $d$
such that every orientation of the graph has directed diameter at least
$d^{2}/2+d$.

##  5 Negative results

It is interesting whether one really needs the logarithmic factor in the upper
bound on the directed diameter. Indeed, Babai asks

[1, Problem 6.4] _Is it possible to bound the directed diameter of a vertex-
transitive graph in terms of its undirected diameter only?_

We give a negative answer to that question. The crux of the argument depends
on the following construction of Haight and Ruzsa [10, 15]. Given a subset $A$
of some abelian group written additively, let $k\cdot A$ denote the $k$-fold
sumset $A+\dots+A$.

######  Lemma 5.1 ([15]).

For any fixed $k\geq 1$ there exists $\alpha_{k}<1$ such that for all
sufficiently large integer $q$ there is a subset $A\subseteq\mathbb{Z}_{q}$
with $A-A=\mathbb{Z}_{q}$ and $|k\cdot A|<q^{\alpha_{k}}$.

######  Corollary 5.2.

For any $k$ there exists a Cayley graph over an abelian group with undirected
diameter at most $2$ and directed diameter at least $k$.

A weaker version of the previous question was also suggested in [1]:

[1, Problem 6.5] _Does there exist a bound on the length of the shortest
directed cycle in a vertex-transitive digraph, depending only on the
undirected diameter?_

The answer to this question is also negative, but we need a more involved
construction.

Note that in the setting of Lemma 5.1 we can always replace $A$ by a shift
$x+A=\\{x+a\mid a\in A\\}$ where $x\in\mathbb{Z}_{q}$. Indeed,
$(x+A)-(x+A)=A-A=\mathbb{Z}_{q}$ and $k\cdot(x+A)=k\cdot x+k\cdot A$, so
$|k\cdot(x+A)|=|k\cdot A|<q^{\alpha_{k}}$. In particular, we can always assume
that $0\in A$.

######  Proposition 5.3.

For any $k\geq 1$ there exists a Cayley graph over an abelian group with
undirected diameter at most $2$ such that the length of the shortest directed
cycle is at least $k$.

###### Proof.

By the previous lemma, for all sufficiently large $q$ there exists a subset
$A\subseteq\mathbb{Z}_{q}$ such that $0\in A$, $A-A=\mathbb{Z}_{q}$ and
$|k\cdot A|<q^{\alpha_{k}}$ where $\alpha_{k}<1$. For $x\neq 0$ let
$I_{x}=\\{x,2\cdot x,\dots,k\cdot x\\}$ be an arithmetic progression in
$\mathbb{Z}_{q}$. We claim that for $q$ large enough it is possible to find
$x\neq 0$ such that $I_{x}\subseteq\mathbb{Z}_{q}\setminus(k\cdot A)$.

Indeed, set $P_{i}=\\{x\in\mathbb{Z}_{q}\mid i\cdot x\in k\cdot A\\}$ for
$i=1,\dots,k$. We can assume that $q$ is a large prime number, in particular,
$\mathbb{Z}_{q}$ is a field with $q>k$. Therefore $|P_{i}|=|k\cdot A|$ and
$|P_{1}\cup\dots\cup P_{k}|\leq k|k\cdot A|<kq^{\alpha_{k}}<q-1$ for $q$ large
enough. Hence there exists $x\neq 0$ such that $x\notin P_{1}\cup\dots\cup
P_{k}$ which implies $I_{x}\subseteq\mathbb{Z}_{q}\setminus(k\cdot A)$.

Notice that we can assume that
$\\{1,\dots,k\\}=I_{1}\subseteq\mathbb{Z}_{q}\setminus(k\cdot A)$. Indeed,
consider $A^{\prime}=\\{x^{-1}a\mid a\in A\\}$. Clearly
$A^{\prime}-A^{\prime}=\mathbb{Z}_{q}$ and $k\cdot A^{\prime}=\\{x^{-1}a\mid
a\in k\cdot A\\}$, so we may replace $A$ by $A^{\prime}$.

We first construct a Cayley graph with undirected diameter at most $4$ and the
length of the shortest nontrivial directed cycle at least $k$. Let
$V=\mathbb{Z}_{q}\times\mathbb{Z}_{q}$ be the underlying abelian group and let
$B=\\{(a,-1),\,(-1,a)\mid a\in A\\}$ be the connection set. As
$A-A=\mathbb{Z}_{q}$, the difference $B-B$ contains
$(\mathbb{Z}_{q},0)=\\{(x,0)\mid x\in\mathbb{Z}_{q}\\}$ and similarly
$(0,\mathbb{Z}_{q})$. Now $V=(\mathbb{Z}_{q},0)+(0,\mathbb{Z}_{q})$, so
$B-B+B-B=V$ and the undirected diameter of the Cayley graph
$\mathrm{Cay}(V,B)$ is at most $4$.

Consider a nontrivial directed cycle in our Cayley graph. It involves $n$
generators of the form $(a_{1},-1),\dots,(a_{n},-1)$ and $m$ generators of the
form $(-1,a^{\prime}_{1}),\dots,(-1,a^{\prime}_{m})$, where
$a_{1},\dots,a_{n},a^{\prime}_{1},\dots,a^{\prime}_{m}\in A$. Since it is a
cycle, we have the following equalities modulo $q$:

$\begin{cases}a_{1}+\dots+a_{n}-m=0,\\\
-n+a^{\prime}_{1}+\dots+a^{\prime}_{m}=0.\end{cases}$

Assume that $n\leq k$ and $m\leq k$. If $m=0$, then second equality implies
that $n=0$ modulo $q$, which is a contradiction with $q>k$ and the fact that
we consider a nontrivial cycle. Hence $m\geq 1$ and, similarly, $n\geq 1$.
Now, $m\in n\cdot A$ and $0\in A$ implies $n\cdot A\subseteq k\cdot A$, so $m$
lies in $k\cdot A$. Recall that the interval $\\{1,\dots,k\\}$ lies fully
outside of $k\cdot A$ hence we have a contradiction. Therefore $n$ or $m$ is
larger than $k$ and the length of any nontrivial directed cycle is at least
$k$.

Finally, to construct the required Cayley graph of undirected diameter at most
$2$, use the argument above with $2k$ in place of $k$ to construct a Cayley
graph $\mathrm{Cay}(V,B)$, $B\subseteq V$, such that $B-B+B-B=V$ and the
length of the shortest nontrivial directed cycle in the graph is at least
$2k$. Now in $\mathrm{Cay}(V,2\cdot B)$ a shortest nontrivial directed cycle
has length at least $k$, and the undirected diameter of the graph is at most
$2$, since $2\cdot B-2\cdot B=V$. The claim is proved. ∎

The examples above are Cayley graphs over abelian groups, so it would be
interesting to know if it is possible to construct similar examples over
groups which are far from being abelian, for example, over finite simple
groups.

##  6 Acknowledgements

The author would like to express his gratitude to prof. A.V. Vasil’ev for
numerous remarks improving the text, and to prof. L. Pyber for suggesting him
the statement of Proposition 2.2.

The research was carried out within the framework of the Sobolev Institute of
Mathematics state contract (project FWNF-2022-0002).

## References

  * [1] L. Babai, _On the diameter of Eulerian orientations of graphs_ , Proc. 17th Ann. Symp. on Discr. Alg. (SODA ’06), ACM-SIAM 2006, 822–831.
  * [2] L. Babai, R. Beals, Á. Seress, _On the diameter of the symmetric group: polynomial bounds_ , Proc. 31st FOCS, IEEE Computer Society 1990, 857–865.
  * [3] L. Babai, P. Erdős, Representations of group elements as short products. Annals of Discrete Math. 12 (1982), 27–30.
  * [4] L. Babai, Á. Seress, _On the diameter of permutation groups_ , European J. Combin. 13:4 (1992), 231–243.
  * [5] L. Babai, M. Szegedy, _Local expansion of symmetrical graphs_ , Combinatorics, Probability and Computing 1 (1992), 1–11.
  * [6] E. Bannai, T. Ito, _Algebraic combinatorics I: association schemes_ , Benjamin/Cummings Pub. Co., Menlo Park, Calif., 1984.
  * [7] E. Breuillard, B. Green, T. Tao, _Approximate subgroups of linear groups_ , Geom. Funct. Anal. 21:4 (2011), 774–819.
  * [8] V. Chvátal, C. Thomassen, _Distances in orientations of graphs_ , J. Comb. Theory Ser. B 24 (1978), 61–75.
  * [9] G. Chen, I. Ponomarenko, _Lectures on coherent configurations_ , Central China Normal Univ Press, Wuhan, 2019.
  * [10] J.A. Haight, _Difference covers which have small k-sums for any k_ , Mathematika 20:1 (1973), 109–118.
  * [11] H.A. Helfgott, Á. Seress, _On the diameter of permutation groups_ , Ann. Math. 179:2 (2014), 611–658.
  * [12] L. Pyber, S.V. Skresanov, _On the automorphism group of a distance-regular graph_ , arXiv:2312.00383 (2023).
  * [13] L. Pyber, E. Szabó, _Growth in finite simple groups of Lie type_ , J. Amer. Math. Soc. 29 (2016), 95–146.
  * [14] I. Ruzsa, _Sums of finite sets_ , in Number Theory: New York Seminar (1996), 281–293.
  * [15] I.Z. Ruzsa, _More differences than multiple sums_ , arXiv:1601.04146v1 (2016).

_Saveliy V. Skresanov_

_Sobolev Institute of Mathematics, 4 Acad. Koptyug avenue, Novosibirsk,
Russia_

_Email address<EMAIL_ADDRESS>


# Emergence of Different Modes of Tool Use in a Reaching and Dragging Task

Khuong Nguyen and Yoonsuck Choe

###### Abstract

Tool use is an important milestone in the evolution of intelligence. In this
paper, we investigate different modes of tool use that emerge in a reaching
and dragging task. In this task, a jointed arm with a gripper must grab a tool
(T, I, or L-shaped) and drag an object down to the target location (the bottom
of the arena). The simulated environment had real physics such as gravity and
friction. We trained a deep-reinforcement learning based controller (with raw
visual and proprioceptive input) with minimal reward shaping information to
tackle this task. We observed the emergence of a wide range of unexpected
behaviors, not directly encoded in the motor primitives or reward functions.
Examples include hitting the object to the target location, correcting error
of initial contact, throwing the tool toward the object, as well as normal
expected behavior such as wide sweep. Also, we further analyzed these
behaviors based on the type of tool and the initial position of the target
object. Our results show a rich repertoire of behaviors, beyond the basic
built-in mechanisms of the deep reinforcement learning method we used.

## Introduction

The ability to solve a task using different types of tools indicates high
cognitive function, including the ability to reason and perceive what is best
to use for a job. In non-human species, Corvids such as the New Caledonian
crows have been observed to not only be able to use different types of tools
(Holzhaider et al. 2008) but also to make new tools from existing materials to
gain access to food (Mehlhorn et al. 2010; von Bayern et al. 2018). Primates
such as chimpanzees and Capuchin monkeys have also been seen to exhibit such
behavior (Sirianni, Mundry, and Boesch 2015; Luncz et al. 2016).

In artificial intelligence research, there is an increasing interest in tool
use. Work by Nishide et al. (2011) focused on the tool-body assimilation
aspect where they used self-organizing maps to extract the information from
visual input to identify different type of tools, followed by recurrent neural
networks for learning the dynamics, and a hierarchical neural network for
tool-body assimilation (this work served as the main motivation for our work
reported here). Saponaro et al. (2017) used a visual and motor mechanism to
represent different hand postures to generalize tool affordance learning (for
affordance, see Gibson 1977). Recent work of Xie et al. (2019) demonstrated a
robot that can learn from demonstration to use novel objects as an
improvisational tool to complete a simple sweeping task. Wicaksono and Sammut
(2016) used inductive logic programming to model the learning but the study is
limited in that each tool is learned separately and the trained robot can only
handle one type of tool for each trained model. Baker et al. (2020) showed
that with standard deep reinforcement learning, together with multi-agent
competition, can exhibit rich collaborative tool use behavior, even when the
game rule was very simple. However, in their work, the tools were boxes,
ramps, and walls, and the only mode of interaction with the tool was pushing
and pulling these objects.

In our paper, we investigate tool use behavior using standard deep RL
algorithms, as in Baker et al. (2020). One key difference with Baker et al. is
that our agent is a jointed limb with a gripper which has to grasp a tool and
wield it to reach and drag an object, so that the agent has to be more
deliberate than simple pushing/pulling. Our main focus is on how different
affordances offered by different types of tools (T-, L-, and I-shaped tools)
and the environment affect the behavior of the deep RL agent (in our previous
work, we considered T-shaped tool only, and did not include extensive
behavioral analysis: Nguyen, Yoo, and Choe 2019). We show that, with standard
deep RL and simple rewards, the agent can exhibit novel behaviors such as
hitting, throwing, and exaggerated movement to compensate for the shortcoming
of specific tools. Our quantitative analysis indicates that these emergent
behaviors are largely necessitated by the different affordances of the tools
and the task situation.

## Methods

### Task Environment

The environment introduces (similar to our prior work Nguyen, Yoo, and Choe
2019) a robot with a three-joint arm with one gripper (which has its own
joint), three types of tools (T-, L-, and I-shaped tools [only T-shaped in
Nguyen, Yoo, and Choe 2019]), and a small target object, all enclosed in a
rectangular arena (figure 1). The task of the agent is to try to grasp the
tool and use it to drag the object down to the target area, which is the
bottom of the arena. The target is initially placed beyond the reach of the
gripper, so tool use is necessary.

Each state $S$ (the input) at time $t$ provided to the agent by the
environment consists of 4 consecutive snapshots of the environment: 4 images
and 4 proprioceptive and/or kinesthetic feedbacks (joint position and angular
velocity). The visual inputs are acquired using the image frames of the
scenes, and the proprioceptive/kinesthetic feedbacks are computed from the
information provided by OpenAI’s MuJoCo-py API. Pixel inputs are normalized by
dividing by 255, and proprioceptive feedbacks are normalized by using running
estimates of their means and standard deviations.

The movements were in a continuous action space. The actions include four
continuous values where three of them are the torques that apply to the three
joints on the agent’s limb. The fourth action value is applied to the gripper
joint and considered as a discrete value where 1.0 is applied to close the
gripper if the action input for the joint is greater than 0, otherwise -1.0 is
applied to open the gripper. Since the actions are in continuous space, their
values are produced by sampling multidimensional normal distributions (4 in
this case) with $\mu_{i}$ and $\sigma_{i}$ being the mean and standard
deviation of the $i$-th normal distribution, generated by the reinforcement
learning algorithm (the policy network).

Figure 1: Task Environment and Model Architecture.

Three types of tools, including the T-shaped, I-shaped, and L-shaped tool were
used, following Nishide et al. (2011). During testing, the type of tool is
arbitrarily chosen and placed randomly in the environment, within reach of the
agent in each running episode. The tools appear with equal probability to
prevent any bias or preference for a specific tool. The target object position
is generated randomly so that it is within a certain distance from the
randomly located tool. These features are expected to increase the complexity
of the environment and therefore increase the difficulty level to solve the
task. The environment was implemented using the MuJoCo physics simulator
(friction, force, etc. modeled: Todorov, Erez, and Tassa 2012) and OpenAI Gym
(Brockman et al. 2016).

### Actor-Critic Based Controller

The description below closely follows our prior work (Nguyen, Yoo, and Choe
2019). For our deep RL controller, we used a modified version of the Actor-
Critic using Kronecker-Factored Trust-Region (ACKTR) algorithm. ACKTR was
introduced by (Wu et al. 2017) where the method showed higher performance than
other state-of-the-art reinforcement learning approaches such as A2C (Mnih et
al. 2016), PPO (Schulman et al. 2017), and TRPO (Schulman et al. 2015a). The
modified version of ACKTR we used turns the original ACKTR into a synchronous
ACKTR (Kostrikov 2018). This method gives us the benefit of A2C, where it
creates multiple versions of the agent to interact with multiple versions of
the environment to learn more efficiently. At the same time, it still
preserves all the advantages that the original ACKTR has.

The Actor-Critic architecture we used is shown in figure 1. The Actor and
Critic share the same block that contains 3 Conv+Pooling layers (55$\times$48
RGB image input [4 frames], 32 channels with 8$\times$8 receptive field [RF],
64 channels with 4$\times$4 RF, 32 channels with 3$\times$3 RF) followed by a
512-neuron fully connected (FC) layer, each with Leaky ReLU activation. The
Actor model (policy network) consists of three FC layers (64 neurons, 64
neurons, and 8 output neurons) with Tanh activation. The Critic (value
network) has three FC layers (64 neurons, 64 neurons, and 1 output neuron)
with Leaky ReLU activation. The last FC layer of the Actor model learns a
Gaussian distribution. It returns the mean and standard deviation for the
actions while the last FC layer of the Critic returns one value that is used
to assess the performance of the Actor. Both the shared Conv output and the
proprioceptive inputs are normalized before they are fed into the value
network and the policy network. This unit utilizes the standard score
normalization formula to normalize the input:
$x^{\prime}=\frac{x-\mu}{\sigma}$, where $x^{\prime}$ is the normalized data,
$x$ is the original data, $\mu$ is the mean of the input, and $\sigma$ is the
standard deviation of the input. This helped with the convergence of the
network during training.

At time $t$, reward $r_{t}$ (more details below) and state

$S_{t}=4*\\{visual\\_input,p^{\overrightarrow{j_{1}}},p^{\overrightarrow{j_{2}}},p^{\overrightarrow{j_{3}}},p^{\overrightarrow{g}}\,v^{\overrightarrow{j_{1}}},v^{\overrightarrow{j_{2}}},v^{\overrightarrow{j_{3}}},v^{\overrightarrow{g}}\\}$

(visual and optional proprioceptive/kinesthetic inputs) are generated, then
fed into the policy and the value network. Next, the policy network produces
the stochastic policy $\pi(A_{t}|S_{t},\theta)$. The actions $A_{t}$ are
sampled from the multidimensional normal distribution. The sampled action
vector $A_{t}$ are fed into the advantage function and used to perform the
next action. The value network estimates the value of the state
$v^{(S_{t},w)}$, which is fed into the advantage function. The advantage
function $A^{\pi}(S_{t},A_{t})$ accumulates the values of $A_{t}$,
$v^{(S_{t},w)}$, and the reward $r_{t}$ for $k$ time steps, then use them to
update the policy and value network using the natural gradient for the trust
region. The environment receives the sampled action vector $A_{t}$, takes the
next step, and produces the new state and reward ($S_{t+1}$ and $r_{t+1}$).

First, we define subtasks $req_{1}$ through $req_{4}$, based on the various
body, tool, and target position: $p^{\overrightarrow{\text{G}}}$ is the pinch
position of the gripper, $p^{\overrightarrow{\text{L}}}$ is the position of
the left claw of the gripper, $p^{\overrightarrow{\text{R}}}$ is the position
of the right claw of the gripper, $p^{\overrightarrow{\text{H}}}$ is the
position of the tool handle, $p^{\overrightarrow{\text{E}}}$ is the position
of the tool end-effector, $p^{\overrightarrow{\text{O}}}$ is the position of
the object, and $p^{\overrightarrow{\text{T}}}$ is the position of the target
(arena’s bottom).

  * •

Reach-Tool: The agent’s gripper reaches the tool

$req_{1}=\lVert
p^{\overrightarrow{\text{G}}}-p^{\overrightarrow{\text{H}}}\rVert_{2}<\frac{1}{2}gripper\\_claw\\_length$
(1)

  * •

Grasp-Tool: The gripper grabs and holds the tool handle

$\displaystyle req_{2}=req_{1}\wedge(close\\_theshold$ $\displaystyle<$
$\displaystyle\lVert
p^{\overrightarrow{\text{L}}}-p^{\overrightarrow{\text{R}}}\rVert_{2}$
$\displaystyle<$ $\displaystyle open\\_threshold)$

  * •

Tool-Reach-Object: The tool end-effector reaches the object

$req_{3}=req_{2}\wedge(\lVert
p^{\overrightarrow{\text{E}}}-p^{\overrightarrow{\text{O}}}\rVert_{2}<\frac{1}{2}tool\\_tip\\_length)$
(3)

  * •

Object-Reach-Target: The target object reaches the bottom of the arena

$req_{4}=\lVert
p^{\overrightarrow{\text{O}}}-p^{\overrightarrow{\text{T}}}\rVert_{2}<\frac{1}{2}arena\\_boundary\\_thickness$
(4)

The reward function utilizing the subtasks above are as follows. Note that
none of the body, tool, or object positions are provided directly to the agent
(these have to be determined by the agent on its own, based on the visual
input).

$r_{\rho}=\begin{cases}300+k_{s}*(s_{max}-s_{k}),&\text{if ($4$)}\\\
1.5+1.5*r_{c3},&\text{if $\neg$($4$)$\wedge$($3$)}\\\
0.25+1.25*r_{c2},&\text{if $\neg$($4$)$\wedge\neg$($3$)$\wedge$($2$)}\\\
0.125,&\text{if $\neg$($4$)$\wedge\neg$($3$)$\wedge\neg$($2$)$\wedge$($1$)}\\\
0.125*r_{c1},&\text{otherwise}\end{cases}$ (5)

where:
$\rho=\\{p^{\overrightarrow{\text{G}}},p^{\overrightarrow{\text{L}}},p^{\overrightarrow{\text{R}}},p^{\overrightarrow{\text{H}}},p^{\overrightarrow{\text{H}}},p^{\overrightarrow{\text{O}}},p^{\overrightarrow{\text{T}}}\\}$,
$k_{s}$ is a constant used to weight the speed of the task completion. It is
set to 3.0 in our experiment, $s_{max}$ is the maximum time step for each
episode (500 steps), $s_{k}$ is the time steps so far,
$r_{c1}=1-tanh^{2}(\frac{\lVert
p^{\overrightarrow{\text{G}}}-p^{\overrightarrow{\text{H}}}\rVert_{2}}{k_{w}})$
$r_{c2}=1-tanh^{2}(\frac{\lVert
p^{\overrightarrow{\text{E}}}-p^{\overrightarrow{\text{O}}}\rVert_{2}}{k_{w}})$
$r_{c3}=1-tanh^{2}(\frac{\lVert
p^{\overrightarrow{\text{O}}}-p^{\overrightarrow{\text{T}}}\rVert_{2}}{k_{w}})$
$k_{w}$ is a constant that is set to the width of the arena,

We trained the networks with the modified ACKTR learning algorithm. ACKTR with
Generalized Advantage Estimator (GAE: Schulman et al. 2015b) computes an
estimator of the $k$-step discounted advantage (equation 6) and use equation 7
to compute the GAE which is the reduced sum of discounted Temporal Difference
residuals

$\hat{A}_{t}^{(k)}=\sum_{l=0}^{k-1}\gamma^{l}\delta_{t+l}^{V}$ (6)

$\hat{A}_{t}^{GAE(\gamma,\lambda)}=\sum_{l=0}^{\infty}(\gamma\lambda)^{l}\delta_{t+l}^{V}$
(7)

where $\lambda$ is a smoothing parameter used for reducing the variance
$0\leq\lambda\leq 1$, $\gamma$ is the discount factor constant, and
$\delta^{V}_{t}=r_{t}+\gamma V(s_{t+1}-V(s_{t}))$.

The advantage of using Generalized Advantage Estimation is that adjusting the
smoothing parameter $\lambda$ might help reduce the variance and lower the
biased estimates, which would improve the sample efficiency of Policy Gradient
methods significantly.

## Experiments and Results

First, we report the success rate, the mean reward, and the mean episode
length of each tool when handled by the trained agent (the same agent was
trained to use all three tools). The next step is to quantify the types of
behaviors that were displayed by the trained agent while using each tool. The
purpose is to examine the environmental condition and the properties of the
tools that trigger such behavior. We conducted visual inspection of the
episodes to produce a rough interpretation of the agent’s strategy in solving
the task to support the analysis, and how the tool affordance affected the
emergent strategies.

Trial 1 Trial 2 Trial 3 Trial 4 Trial 5

Figure 2: Training Results: (Top) Reward. (Bottom) Episode Length. Running
average and actual reward/episode length.

Multiple training sessions were conducted. Each session used twelve workers
corresponding to the number of threads. Since the reinforcement learning
method that we used is asynchronous, each worker works on a different
incarnation of the environment. The number of training threads was divided
equally between the types of tools to balance the overall experience provided
to the agent. As such, three of the threads were dedicated to training the
agent to use the T-shaped tool. Three others were dedicated the L-shaped tool
with the end effector pointing to the right and three for the L-shaped tool
with the end effector pointing to the left. The rest was for the I-shaped
tool.

The number of maximum time steps for an episode was 500, where a time step is
equivalent to 10 simulated milliseconds. If the agent finishes its task before
reaching the maximum time steps, the remaining time is treated as extra
reward. During each training session, the average reward and the average
episode length over the threads were recorded.

Each training session ran for 19,000 episodes (Intel Core i7-8700K CPU @
3.7GHz$\times$12, Nvidia GTX 1080-Ti GPU with 11GB memory, RAM 32GB, typical
training time of 7 days). An episode is considered to be successful if
requirement 4 (equation 4) is satisfied, and the total number of time steps is
within 500. In all of the five runs, the training successfully converged. On
average, training reached a reward of approximately 800 after 19,000 training
iterations (note: baseline reward is 300 for just moving the object to the
target location; equation 5).

### Training results

Figure 2 shows the training results from five training sessions. All of the
sessions successfully converged. According to the plot, the training becomes
relatively stable after 10,000 episodes with an average reward of
approximately 800. To solve the task, the agent must satisfied requirement 4.
When the agent finishes the task early (less than 500 time-steps), it will
receive a bonus that is proportion to the extra time steps. Additionally,
figure 2 depict the length of the episode of all five runs. Note that these
results show the overall performance of the agent using the three given tools,
not performance specific to a certain tool.

### Quantitative Analysis of Behavior

#### Performance by tool type:

Table 1 shows the success rate of the trained agent in handling the three
tools over 100 episode runs. An episode is considered as completed if the last
requirement (equation 4) is satisfied. From the left to the right, the success
rate of the T-shaped tool, L-shaped tool, and I-shaped tool are shown. The
T-shaped tool has the highest success rate (62%), followed by the L-shaped
tool (50%), and the I-shaped tool has the lowest success rate (45%). This
result indicates that the T-shaped tool provides the best option to complete
the task. This is expected since the T-shaped tool has the shape and physical
features that are more advantageous than the other two tools when it comes to
dragging the target object from different positions.

Table 1 also shows the average episode length of the agent when handling each
of the three tools over 100 episode runs. An episode finishes when the agent
satisfies the last requirement (equation 4) before the time limit is reached
(500-time steps). From the left to the right, the episode length when the
agent use the T-shaped tool (280.92), the L-shaped tool (302.51), and the
I-shaped tool (374.56). Note that the shorter the episode length, the better
it is since the agent finishes the task early and get extra reward bonus.
Overall, the T-shaped tool enabled the trained agent to solve the task more
effectively and faster compared to the other two tools.

T-shaped L-shaped I-shaped Success rate 62% 50% 45% Reward 943.2 806.2 644.7
Episode Length 280.92 302.51 374.56

Table 1: Results by Tool Type (mean over 100 episodes)

#### L-shaped Tool (I-like and T-like Use):

Over the 50 successful episodes of the agent handling the L-shaped tool, we
observed that when the tool’s end effector points toward the target object the
agent exhibit the same hooking behavior similar to the T-shaped tool case
(figure 4 Top). However, when the tool’s end-effector pointed away from the
target object (figure 4 Bottom) the agent usually expresses two interesting
behaviors. We named the first behavior as Act-Liked-I behavior to describe the
way the agent uses the L-shaped tool in the same manner as the I-shaped tool.
It reaches and grasps the tool then uses the body of the tool to wipe down the
target object. On the other hand, we named the other behavior as Maneuver
behavior (figure 5) where the agent navigate the tool to the other side of the
target object so that the tool’s end-effector points toward the target object.
This way, the agent can effectively use the tool to hook on the target object
and drag it down to the bottom of the arena.

Table 2 presents the quantitative analysis results of the trained agent’s
behaviors when it handles the L-shaped tool while the tool tip points away
from the target object. Over 20 successful episode, 60% of the time the agent
exhibit the Act-Like-I behavior while 40% of the time, the agent display the
Maneuver behavior. Going further into the details, table 2 shows that when the
agent displays the Maneuver behavior, the target object is located in the
upper half of the arena 52.5% of the time and the target object is located in
the lower part of the arena 7.5% of the time. This result indicates that when
the target object is located in a position that is high above the agent, the
most effective approach to gain access to the target object is to take
advantage of the tool’s end effector. In this case, the agent will maneuver
the tool to hook on to the target object. If the agent uses the other approach
(Act-Like-I), the target object might slip out of the control of the tool,
thus resulting in a failed episode.

I-like use T-like use Upper Arena 3.33% 52.5% Lower Arena 36.67% 7.5% Overall
40% 60%

Table 2: L-shaped Tool Use Modes when Tip of L is Facing Away from Object

Table 2 also shows the Act-Like-I behavior versus the position of the target
object when the trained agent encounters the L-shaped tool with its end-
effector point away from the target object. We can see that 36.67% of the time
the agent display this behavior is when the target object is located in the
lower part of the arena and 3.33% the rest of the time, the target object is
located in the upper part of the arena. This can be explained as when the
target object position is low, it is easier for the agent to just use the tool
to wipe the target object down instead of taking the complicated step of
maneuvering the tool to the other side.

#### I-shaped Tool (Wide Sweep and Hitting):

Table 3 shows the break down of the behaviors that occur while the trained
agent uses the I-shaped tool. The most common behavior is the Wide-Sweep
behavior (happens 71.11% of the time; figure 6), followed by the hitting
behavior (happens 11.11% of the time; figure 7) and other behaviors occur
approximately 17.78% of the time. Since the I-shaped tool is the hardest to
use among the three tools (according to the success rate in table 1) due to
the lack of the hook-like tip, the agent has to develop a strategy to
compensate for the tool’s disadvantages. The wide-sweep behavior is an example
in this case as making wide sweep does help with preventing the target object
from slipping out of its control. On the other hand, the hitting behavior
exhibited by the trained agent while handling the I-shaped tool might indicate
the ability to exploit the physics of the environment. This property of the
I-shaped tool enables the agent to use the tool tip at the other end to hit
the target object down as if using a bat.

Table 3 also shows these behaviors when using the I-shaped tool in relation to
the target object positions. According to the plot, wide-sweep behavior
appears the majority of time in the upper part of the arena (55.56%) and the
rest (15.56%) in the lower part of the arena. When the target object is
located high above the agent, it makes sense that the agent has to extend its
arm longer to make wider sweep with the target object in order to keep it from
slipping. In contrast, the hitting behavior observed in the I-shaped tool
scenarios happens most often when the target object is placed in the lower
part of the arena (8.89%) and some times in the upper part (2.22%). The other
less occur behaviors take 17.78% of the time.

Wide sweep Hitting Other Upper Arena 55.56% 2.22% 15.56% Lower Arena 15.56%
8.89% 2.22% Overall 71.11% 11.11% 17.78%

Table 3: I-shaped Tool Use Modes

#### Correcting and Throwing Behaviors:

Two other less common behaviors that were observed in all types of tools are
throwing and correcting. These behavior appear less frequent compared to other
major behaviors. The throwing behavior is described as when the agent, after
grasping the tool, moves and throws the tool to hit the target object
resulting in the target object slide to the bottom of the arena thus
completing the task (figure 9). This behavior might have been the result of
the fact that requirement 4 in itself does not require that the agent keep
holding on to the tool when the target object is already at the bottom. Table
4 shows that the throwing behavior only happens when the trained agent handle
the L-shaped and I-shaped tools (2% for the L-shaped case and 11.11% for the
I-shaped tool case.). The last behavior that is investigated in this study is
the Correcting behavior (figure 8). As its name suggests, this behavior
indicates that the agent can correct itself nudging the object away and then
coming back to drag it. From our experimental results, this behavior happens
most frequently when the trained agent uses the T-shaped tool (9.68% of the
time). In the case of the L-shaped tool, it happens 6% of the time and 11.11%
of the time for the I-shaped tool.

Correcting Throwing Others T-shaped 9.68% 0.00% 90.32% L-shaped 6.00% 2.00%
92.00% I-shaped 6.67% 11.11% 82.22%

Table 4: Throwing and Correcting Behavior by Tool Type

### Example Behaviors

#### T-shaped Tool (Typical Behavior):

Figure 3 shows a successful episode of the trained agent that uses the
T-shaped tool to complete the task. The episode begins when the agent
recognizes the tool’s location in the environment thanks to the input that it
receives. The agent then moves toward the tool and gradually open its grips.
In most of the observed cases, to successfully grasp the tool, the agent has
to be able to slide its grips to cover the right amount of the tool handle. At
this point, it then drives the tool toward the target object. When the agent
can use the tool to hook on the target object, it will then drag the target
object to the bottom of the arena.

t = 8 t = 11 t = 25 t = 27 t = 29 t = 30

Figure 3: T-shaped Tool: Typical Behavior (The semi-transparent overlays show
immediate preceding frames.)

#### L-shaped Tool (T-like vs. I-like):

When learning to use the L-shaped tool, the agent exhibits different behaviors
in handling the tool. In the case where the tool’s end-effector points toward
the target object, it displays the same behavior as when it uses the T-shaped
tool (see figure 4 [Top]). However, in the case where the tool’s end-effector
point away from the target object, it shows two different behaviors. One such
behavior is that the agent operates the tool to pull the target object down
like the way it uses the I-shaped tool (see figure 4 [Bottom]). The other
behavior is that it maneuvers the tool to the other side of the target object
so that the tool’s end-effector points toward the target object then hook and
pull it down. Figure 5 depicts the behavior.

t = 10 t = 23 t = 29 t = 5 t = 26 t = 30

Figure 4: L-shaped Tool: Tool Tip Direction Relative to Object. (Top) Tip of L
points toward the object (T-like). (Bottom) Tip of L points away from the
object (I-like).

t = 7 t = 13 t = 15 t = 26 t = 29 t = 30

Figure 5: L-shaped Tool: Maneuvering Tip Around Object.

#### I-shaped Tool (Wide Sweep and Hitting):

In the case of the I-shaped tool, the agent exhibits two interesting
behaviors. One is the wide-sweep where the target object is usually located in
the upper part of the arena (figure 6; also see figure 4 bottom row, I-like
behavior). After grasping the tool ($t=6$), the agent has to extend the tool
way beyond the object ($t=10$ to $t=12$) to make a wide swipe ($t=15$ to
$t=16$). This ensures that the target object does not slip off the tool during
the successive motion. The other behavior is the hitting behavior where the
target object is usually located in the lower part of the arena (figure 7). In
this scenario, after grasping the tool ($t=6$), the agent swings the tool and
use its tip to hit the target object ($t=14$), propelling it down.

t = 3 t = 6 t = 10 t = 12 t = 15 t = 16

Figure 6: I-shaped Tool: Wide Sweep Behavior

t = 3 t = 6 t = 7 t = 12 t = 14 t = 15

Figure 7: I-shaped Tool: Hitting Behavior

#### Correcting and Throwing:

Two behaviors that are not common but can occur sometimes are the correcting
behavior and the Throwing behavior. In the case of the correcting behavior,
the agent makes a mistake by nudging the object away (figure 8, $t=10$).
However, it circles back and hooks on the object ($t=12$ to $t=14$) and moves
it to the other side dragging it to the bottom. In the throwing behavior case
(figure 9), after grasping the tool ($t=9$), the agent moves it for a short
distance then throw it toward the target object in an effort to bring it down
($t=15$ to $t=16$). This may happen when the grip on the tool is weak and the
agent is about to lose the grip.

t = 4 t = 9 t = 10 t = 12 t = 13 t = 14 t = 15 t = 17 t = 18

Figure 8: L-shaped Tool: Correcting Behavior.

t = 3 t = 9 t = 13 t = 14 t = 15 t = 16

Figure 9: I-shaped Tool: Throwing Behavior

#### Failure Cases:

Most of the observed failed cases were because the agent could not properly
grasp the tool. To grasp the tool correctly, the agent has to approach the
tool-handle from a proper direction so that the gripper does not miss and
nudge the tool to a distance that the agent cannot reach (figure 10 [Top]). In
this case, the correct move is to bend the arm and position the gripper to
face the tool handle. Then from this position, the agent should approach the
tool to place the tool-handle inside its grippers. Another failed case is when
the agent could not control the tool to make the right moves resulting in a
wrong way to approach the target object. This usually ends up pushing the
target object away from the reach of the agent and its tool. In such
circumstances, the result is the agent losing track of its goal, stumbling or
freezing until the simulation reaches the limit number of time steps (figure
10 [Middle]). Another unsuccessful scenario is when the agent fails to use the
tool properly. For example, in figure 10 (Bottom), when dealing with the
I-shaped tool, the agent has to carefully manage the tool so that the target
object does not slip out of its hold. In this case, the agent did not extend
its arm long enough to make a wider swing, thus failed to move the target
object.

t = 4 t = 5 t = 6 t = 7 t = 4 t = 6 t = 7 t = 8 t = 4 t = 6 t = 7 t = 8

Figure 10: Failure Modes: (Top) Lose grasp of tool. (Middle) Nudge object
away. (Bottom) Flailing.

## Discussion

The main novelty of our work compared to our prior work (Nguyen, Yoo, and Choe
2019) is in the detailed comparison of multiple tool use behavior and
quantitative analysis. In our prior work, we focused on adding raw visual
input to the agent, simulated physics, and the gripper, with the only tool
being the T-shaped tool. Thus, previously we were not able to study the effect
of different tool affordances.

Overall, we observed that the agent handles each tool in various manners
depending on their affordances. The learned behaviors are specifically aligned
with the physical property (shape) of the tool, the environmental condition
(the target object position), and also the basic physics of the environment.

In the case of the T-shaped tool, the tool provides the agent with better
options to solve the task since it has the hook-like tip facing both ways at
the end of the tool end. Therefore, the agent does not have to worry about the
object slipping off the tool end. Due to this, the agent can complete the job
faster and with higher reward than when using the two other tools.

In the case of the L-shaped tool, the agent exhibited two interesting
behaviors when the tool’s hook-like tip points away from the target object.
This is due to the L-shape having both the T-like (hook) and I-like (no hook)
property. It is interesting that the agent could learn to use the tool in both
ways, and furthermore, not always strictly dependent on the location of the
target object relative to the tool tip direction.

For the I-shaped tool, since it is the most disadvantaged type, more ingenious
strategies emerged. These included wide sweep (extending the tool way beyond
the object to avoid slipping), hitting (like using a bat), and throwing the
tool toward the object. Although the I-shaped tool has lower success rate than
the other two, these unique behaviors make it an interesting case study.

These strategies are quite unique and unexpected, and they are largely
dependent on the affordance of the different types of tools, the location of
the objects, and also the physics. It is all the more interesting since we
used a standard deep RL algorithm, without any direct rewards or motor
primitives to for these kinds of behaviors.

In future work, we intend to analyze the inner workings of our trained neural
networks to understand the functional origin of these emergent behaviors. Are
there different modules that emerge in the neural networks, corresponding to
the different behaviors? How much do the Conv layers contribute to the
assessment of the situation? Also, we will investigate if the learned tool use
strategy can be transferable to novel tools (e.g., with a different shape).
The tool-body assimilation model in Nishide et al. (2011) provides a hint. In
their work, they trained the model with only the T-shaped and the I-shaped
tool, and used the L-shaped tool as a novel tool for testing. We expect our
method, when trained and tested in this manner, would show transferability,
due to the generalizability of the Conv net.

## Conclusion

In this work, we showed that a single deep reinforcement learning agent can
utilize three different types of tools to achieve a common goal, through novel
emergent behaviors. The main contribution of this work is to have shown the
importance of the type of tool affordance and environmental factors in the
emergence of novel behaviors in deep reinforcement learning based control.
These behaviors included the use of a single tool in two distinct modes (use
of L-shaped as T-shaped or I-shaped), hitting, throwing, correcting, and wide
sweep, dependent on tool type and situation. We expect our study to further
motivate research on tool use and affordances in deep learning.

## References

  * Baker et al. (2020) Baker, B.; Kanitscheider, I.; Markov, T.; Wu, Y.; Powell, G.; McGrew, B.; and Mordatch, I. 2020.  Emergent Tool Use From Multi-Agent Autocurricula.  In _International Conference on Learning Representations_.
  * Brockman et al. (2016) Brockman, G.; Cheung, V.; Pettersson, L.; Schneider, J.; Schulman, J.; Tang, J.; and Zaremba, W. 2016.  Openai gym.  _arXiv preprint arXiv:1606.01540_ .
  * Gibson (1977) Gibson, J. J. 1977.  The theory of affordances.  _Hilldale, USA_ 1(2).
  * Holzhaider et al. (2008) Holzhaider, J. C.; Hunt, G. R.; Campbell, V. M.; and Gray, R. D. 2008.  Do wild New Caledonian crows (Corvus moneduloides) attend to the functional properties of their tools?  _Animal Cognition_ 11(2): 243–254.
  * Kostrikov (2018) Kostrikov, I. 2018.  PyTorch Implementations of Reinforcement Learning Algorithms.  https://github.com/ikostrikov/pytorch-a2c-ppo-acktr.
  * Luncz et al. (2016) Luncz, L. V.; Falótico, T.; Pascual-Garrido, A.; Corat, C.; Mosley, H.; and Haslam, M. 2016.  Wild capuchin monkeys adjust stone tools according to changing nut properties.  _Scientific reports_ 6: 33089.
  * Mehlhorn et al. (2010) Mehlhorn, J.; Hunt, G. R.; Gray, R. D.; Rehkämper, G.; and Güntürkün, O. 2010.  Tool-making New Caledonian crows have large associative brain areas.  _Brain, behavior and evolution_ 75(1): 63–70.
  * Mnih et al. (2016) Mnih, V.; Badia, A. P.; Mirza, M.; Graves, A.; Lillicrap, T.; Harley, T.; Silver, D.; and Kavukcuoglu, K. 2016.  Asynchronous methods for deep reinforcement learning.  In _International conference on machine learning_ , 1928–1937.
  * Nguyen, Yoo, and Choe (2019) Nguyen, K. N.; Yoo, J.; and Choe, Y. 2019.  Speeding Up Affordance Learning for Tool Use, Using Proprioceptive and Kinesthetic Inputs.  In _2019 International Joint Conference on Neural Networks (IJCNN)_ , 1–8. IEEE.
  * Nishide et al. (2011) Nishide, S.; Tani, J.; Takahashi, T.; Okuno, H. G.; and Ogata, T. 2011.  Tool–body assimilation of humanoid robot using a neurodynamical system.  _IEEE transactions on autonomous mental development_ 4(2): 139–149.
  * Saponaro et al. (2017) Saponaro, G.; Vicente, P.; Dehban, A.; Jamone, L.; Bernardino, A.; and Santos-Victor, J. 2017.  Learning at the ends: From hand to tool affordances in humanoid robots.  In _2017 Joint IEEE International Conference on Development and Learning and Epigenetic Robotics (ICDL-EpiRob)_ , 331–337. IEEE.
  * Schulman et al. (2015a) Schulman, J.; Levine, S.; Abbeel, P.; Jordan, M.; and Moritz, P. 2015a.  Trust region policy optimization.  In _International Conference on Machine Learning_ , 1889–1897.
  * Schulman et al. (2015b) Schulman, J.; Moritz, P.; Levine, S.; Jordan, M.; and Abbeel, P. 2015b.  High-dimensional continuous control using generalized advantage estimation.  _arXiv preprint arXiv:1506.02438_ .
  * Schulman et al. (2017) Schulman, J.; Wolski, F.; Dhariwal, P.; Radford, A.; and Klimov, O. 2017.  Proximal policy optimization algorithms.  _arXiv preprint arXiv:1707.06347_ .
  * Sirianni, Mundry, and Boesch (2015) Sirianni, G.; Mundry, R.; and Boesch, C. 2015.  When to choose which tool: multidimensional and conditional selection of nut-cracking hammers in wild chimpanzees.  _Animal Behaviour_ 100: 152–165.
  * Todorov, Erez, and Tassa (2012) Todorov, E.; Erez, T.; and Tassa, Y. 2012.  Mujoco: A physics engine for model-based control.  In _Intelligent Robots and Systems (IROS), 2012 IEEE/RSJ International Conference on_ , 5026–5033. IEEE.
  * von Bayern et al. (2018) von Bayern, A. M. P.; Danel, S.; Auersperg, A.; Mioduszewska, B.; and Kacelnik, A. 2018.  Compound tool construction by New Caledonian crows.  _Scientific reports_ 8(1): 15676.
  * Wicaksono and Sammut (2016) Wicaksono, H.; and Sammut, C. 2016.  Relational tool use learning by a robot in a real and simulated world.  In _Proceedings of ACRA_.
  * Wu et al. (2017) Wu, Y.; Mansimov, E.; Grosse, R. B.; Liao, S.; and Ba, J. 2017.  Scalable trust-region method for deep reinforcement learning using kronecker-factored approximation.  In _Advances in neural information processing systems_ , 5279–5288.
  * Xie et al. (2019) Xie, A.; Ebert, F.; Levine, S.; and Finn, C. 2019.  Improvisation through Physical Understanding: Using Novel Objects as Tools with Visual Foresight.  _arXiv preprint arXiv:1904.05538_ .

## Appendix

## Software and Hardware Used

The following software and versions were used.

  * •

MuJuCo v1.31

  * •

Python 3.7

  * •

OpenAI Gym v0.9.3

  * •

OpenAI baselines v0.1.5

The hardware used were as follows:

  * •

CPU: Intel Core i7-8700K CPU @ 3.7GHz$\times$12

  * •

GPU: Nvidia GTX 1080-Ti GPU with 11GB memory, RAM 32GB,

## Model details

Layer | Spec | Activation
---|---|---
Input | 55$\times$48, 3 channels (RGB), 4 frames |
Conv 1 | 32 channels @ 8$\times$8 RF, stride = 4 | Leaky ReLU
Conv 2 | 64 channels @ 4$\times$4 RF, stride = 2 | Leaky ReLU
Conv 3 | 32 channels @ 3$\times$3 RF, stride = 1 | Leaky ReLU
FC | 512 neurons | Leaky ReLU
Table 5: Shared Convolutional Network. Note: no pooling layer was used. Layer | Spec | Activation
---|---|---
FC layer 1 | 64 neurons | tanh
FC layer 2 | 64 neurons | tanh
FC layer 3 | 8 neurons | tanh
Table 6: Policy Network. Layer | Spec | Activation
---|---|---
FC layer 1 | 64 neurons | Leaky ReLU
FC layer 2 | 64 neurons | Leaky ReLU
FC layer 3 | 1 neurons | Leaky ReLU
Table 7: Value Network.

The parameters for the Kronecker-factored Approximate Curvature (K-FAC)
optimizer and Generalized Advantage Estimator (GAE) were as follows:

  * •

K-FAC Optimizer: learning rate = 0.25

  * •

K-FAC Optimizer: desired KL: 0.001

  * •

K-FAC Optimizer: damping factor: 1e-2

  * •

GAE discount factor $\gamma$: 0.99

  * •

GAE smoothing parameter $\lambda$: 0.95

  * •

Number of steps taken (actions sampled) before an update: 30

## Animations

These are the animations corresponding to figures 3 to 10 in the main paper.
Note: The PDF animation works only in Adobe Acrobat reader.

[loop,controls,autoplay,width=0.8]7T3/T_TL/T_330

Figure 11: [Animation] T-shaped tool: Typical behavior. Figure 3 in the main
paper.

[loop,controls,autoplay,width=0.8]6T3/LR_TL/LR_330

Figure 12: [Animation] L-shaped tool: T-like behavior. Figure 4 (top) in the
main paper.

[loop,controls,autoplay,width=0.8]6T3/LL_TL/LL_230

Figure 13: [Animation] L-shaped tool: I-like behavior. Figure 4 (bottom) in
the main paper.

[loop,controls,autoplay,width=0.8]6T3/LLC_TL/LLC_230

Figure 14: [Animation] L-shaped tool: Changing tool tip direction relative to
object. Figure 5 in the main paper.

[loop,controls,autoplay,width=0.8]6T3/CR_LL/CR_LL_218

Figure 15: [Animation] L-shaped tool: Correcting behavior. Figure 6 in the
main paper.

[loop,controls,autoplay,width=0.8]6T3/I_wide_contact/I_WC_216

Figure 16: [Animation] I-shaped tool: Wide Sweep behavior. Figure 7 in the
main paper.

[loop,controls,autoplay,width=0.8]6T3/I_hitting/I_hit_216

Figure 17: [Animation] I-shaped tool: Hitting behavior. Figure 8 in the main
paper.

[loop,controls,autoplay,width=0.8]6T3/CR_I/CR_I_218

Figure 18: [Animation] I-shaped tool: Throwing behavior. Figure 9 in the main
paper.

[loop,controls,autoplay,width=0.8]4T3/Failed_T/T_28

Figure 19: [Animation] T-shaped tool: Failure case. Figure 10 (Top) in the
main paper.

[loop,controls,autoplay,width=0.8]4T3/Failed_LL/LL_28

Figure 20: [Animation] L-shaped tool: Failure case. Figure 10 (Middle) in the
main paper.

[loop,controls,autoplay,width=0.8]4T3/Failed_I/I_28

Figure 21: [Animation] I-shaped tool: Failure case. Figure 10 (Bottom) in the
main paper.

## Extra Animations

These are unreported results.

[loop,controls,autoplay,width=0.8]2T3/FC_I/FC_I_36

Figure 22: [Animation] I-shaped tool: Failure case. Tool thrown but failed to
make object reach the target.

[loop,controls,autoplay,width=0.8]3T3/FC_T/FC_T_26

Figure 23: [Animation] T-shaped tool: Failure case. Failed to grab took.

[loop,controls,autoplay,width=0.8]5T2/c230

Figure 24: [Animation] Trained with T-shaped tool only. Complex maneuvering
and corraling of the object.