numbersnone#1none:
left:
right:

**footnotetext: These authors contributed equally to this work

# A Step-by-step Introduction to the Implementation of Automatic
Differentiation

Yu-Hsueh Fang∗ National Taiwan University  He-Zhe Lin∗ National Taiwan
University  Jie-Jyun Liu  National Taiwan University  Chih-Jen Lin  National
Taiwan University  Mohamed bin Zayed University of Artificial Intelligence

###### Abstract

Automatic differentiation is a key component in deep learning. This topic is
well studied and excellent surveys such as Baydin et al. (2018) have been
available to clearly describe the basic concepts. Further, sophisticated
implementations of automatic differentiation are now an important part of
popular deep learning frameworks. However, it is difficult, if not impossible,
to directly teach students the implementation of existing systems due to the
complexity. On the other hand, if the teaching stops at the basic concept,
students fail to sense the realization of an implementation. For example, we
often mention the computational graph in teaching automatic differentiation,
but students wonder how to implement and use it. In this document, we
partially fill the gap by giving a step by step introduction of implementing a
simple automatic differentiation system. We streamline the mathematical
concepts and the implementation. Further, we give the motivation behind each
implementation detail, so the whole setting becomes very natural.

##  1 Introduction

In modern machine learning, derivatives are the cornerstone of numerous
applications and studies. The calculation often relies on automatic
differentiation, a classic method for efficiently and accurately calculating
derivatives of numeric functions. For example, deep learning cannot succeed
without automatic differentiation. Therefore, teaching students how automatic
differentiation works is highly essential.

Automatic differentiation is a well-developed area with rich literature.
Excellent surveys including Chinchalkar (1994), Bartholomew-Biggs et al.
(2000), Baydin et al. (2018) and Margossian (2019) review the algorithms for
automatic differentiation and its wide applications. In particular, Baydin et
al. (2018) is a comprehensive work focusing on automatic differentiation in
machine learning. Therefore, there is no lack of materials introducing the
concept of automatic differentiation.

On the other hand, as deep learning systems now solve large-scale problems, it
is inevitable that the implementation of automatic differentiation becomes
highly sophisticated. For example, in popular deep learning systems such as
PyTorch (Paszke et al., 2017) and Tensorflow (Abadi et al., 2016), at least
thousands of lines of code are needed. Because of this, many places of
teaching automatic differentiation for deep learning stop at the basic
concepts. Then students fail to sense the realization of an implementation.
For example, we often mention the computational graph in teaching automatic
differentiation, but students wonder how to implement and use it. In this
document, we aim to partially fill the gap by giving a tutorial on the basic
implementation.

In recent years, many works111https://towardsdatascience.com/build-your-own-
automatic-differentiation-
program-6ecd585eec2a,222https://sidsite.com/posts/autodiff,333https://mdrk.io/introduction-
to-automatic-differentiation-
part2/,444https://github.com/dlsyscourse/lecture5/blob/main/5_automatic_differentiation_implementation.ipynb,555https://github.com/karpathy/micrograd
have attempted to discuss the basic implementation of automatic
differentiation. However, they still leave room for improvement. For example,
some are not self-contained – they quickly talk about implementations without
connecting to basic concepts. Ours, which is very suitable for the beginners,
has the following features:

  * •

We streamline the mathematical concepts and the implementation. Further, we
give the motivation behind each implementation detail, so the whole setting
becomes very natural.

  * •

We use the example from Baydin et al. (2018) for the consistency with past
works. Ours is thus an extension of Baydin et al. (2018) into the
implementation details.

  * •

We build a complete tutorial including this document, slides and the source
code at
https://www.csie.ntu.edu.tw/~cjlin/papers/autodiff/.

##  2 Automatic Differentiation

There are two major modes of automatic differentiation. In this section, we
introduce the basic concepts of both modes. Most materials in this section are
from Baydin et al. (2018). We consider the same example function

$y=f(x_{1},x_{2})=\log x_{1}+x_{1}x_{2}-\sin x_{2}.$

###  2.1 Forward Mode

First, we discuss the forward mode. Before calculating the derivative, let us
check how to calculate the function value. Assume that we want to calculate
the function value at $(x_{1},x_{2})=(2,5)$. Then, in the following table, we
have a forward procedure.

| $x_{1}$ |  | $=2$
---|---|---|---
| $x_{2}$ |  | $=5$
| $v_{1}$ | $=\log{x_{1}}$ | $=\log{2}$
| $v_{2}$ | $=x_{1}\times x_{2}$ | $=2\times 5$
| $v_{3}$ | $=\sin{x_{2}}$ | $=\sin{5}$
| $v_{4}$ | $=v_{1}+v_{2}$ | $=0.693+10$
| $v_{5}$ | $=v_{4}-v_{3}$ | $=10.693+0.959$
| $y$ | $=v_{5}$ | $=11.652$

We use variables $v_{i}$ to record the intermediate outcomes. First, we know
$\log$ function is applied to $x_{1}$. Therefore, we have $\log(x_{1})$ as a
new variable called $v_{1}$. Similarly, there is a variable $v_{2}$, which is
$x_{1}\times x_{2}$. Each $v_{i}$ is related to a simple operation. The
initial value of this member is zero when a node is created. In the end, our
function value at $(2,5)$ is $y=v_{5}$. As shown in the table, the function
evaluation is decomposed into a sequence of simple operations. We have a
corresponding computational graph as follows:

$x_{1}$$v_{1}$$v_{4}$$x_{2}$$v_{2}$$v_{3}$$v_{5}$$y=f(x_{1},x_{2})$

Because calculating both $v_{1}$ and $v_{2}$ needs $x_{1}$, $x_{1}$ has two
links to them in the graph. The following graph shows all the intermediate
results in the computation.

$x_{1}$$=2$$v_{1}$$=\ln x_{1}$$\log
2$$v_{4}$$=v_{1}+v_{2}$$0.693+10$$x_{2}$$=5$$v_{2}$$=x_{1}\times
x_{2}$$2\times
5$$v_{3}$$=\sin{x_{2}}$$\sin{5}$$v_{5}$$=v_{4}-v_{3}$$10.693-(-0959)$$f(x_{1},x_{2})$

The computational graph tells us the dependencies of variables. Thus, from the
inputs $x_{1}$ and $x_{2}$ we can go through all nodes for getting the
function value $y=v_{5}$ in the end.

Now, we have learned about the function evaluation. But remember, we would
like to calculate the derivative. Assume that we target at the partial
derivative ${\partial y}/{\partial x_{1}}$. Here, we denote

$\dot{v}=\frac{\partial v}{\partial x_{1}}$

as the derivative of the variable $v$ with respect to $x_{1}$. The idea is
that by using the chain rule, we can obtain the following forward derivative
calculation to eventually get $\dot{v}_{5}=\partial f/\partial x_{1}$.

| $\dot{x}_{1}$ | $=\partial x_{1}/\partial x_{1}$ | $=1$
---|---|---|---
| $\dot{x}_{2}$ | $=\partial x_{2}/\partial x_{1}$ | $=0$
| $\dot{v}_{1}$ | $=\dot{x}_{1}/x_{1}$ | $=1/2$
| $\dot{v}_{2}$ | $=\dot{x}_{1}\times x_{2}+\dot{x}_{2}\times x_{1}$ | $=1\times 5+0\times 2$
| $\dot{v}_{3}$ | $=\dot{x}_{2}\times\cos{x_{2}}$ | $=0\times\cos{5}$
| $\dot{v}_{4}$ | $=\dot{v}_{1}+\dot{v}_{2}$ | $=0.5+5$
| $\dot{v}_{5}$ | $=\dot{v}_{4}-\dot{v}_{3}$ | $=5.5-0$
| $\dot{y}$ | $=\dot{v}_{5}$ | $=5.5$

The table starts from $\dot{x}_{1}$ and $\dot{x}_{2}$, which are ${\partial
x_{1}}/{\partial x_{1}}=1$ and ${\partial x_{2}}/{\partial x_{1}}=0$. Based on
$\dot{x}_{1}$ and $\dot{x}_{2}$, we can calculate other values. For example,
let us check the partial derivative $\partial{v_{1}}/\partial{x_{1}}$. From

$v_{1}=\log x_{1},$

by the chain rule,

$\dot{v}_{1}=\frac{\partial v_{1}}{\partial x_{1}}\times\frac{\partial
x_{1}}{\partial x_{1}}=\frac{1}{x_{1}}\times\frac{\partial x_{1}}{\partial
x_{1}}=\frac{\dot{x}_{1}}{x_{1}}.$

Therefore, we need $\dot{x}_{1}$ and $x_{1}$ for calculating $\dot{v}_{1}$ on
the left-hand side. We already have the value of $\dot{x}_{1}$ from the
previous step (${\partial x_{1}}/{\partial x_{1}}=1$). Also, the function
evaluation gives the value of $x_{1}$. Then, we can calculate
$\dot{x}_{1}/x_{1}=1/2$. Clearly, the chain rule plays an important role here.
The calculation of other $\dot{v}_{i}$ is similar.

###  2.2 Reverse Mode

Next, we discuss the reverse mode. We denote

$\bar{v}=\frac{\partial y}{\partial v}$

as the derivative of the function $y$ with respect to the variable $v$. Note
that earlier, in the forward mode, we considered

$\dot{v}=\frac{\partial v}{\partial x_{1}},$

so the focus is on the derivatives of all variables with respect to one input
variable. In contrast, the reverse mode focuses on $\bar{v}={\partial
y}/{\partial v}$ for all $v$, the partial derivatives of one output with
respect to all variables. Therefore, for our example, we can use
$\bar{v}_{i}$’s and $\bar{x}_{i}$’s to get both ${\partial y}/{\partial
x_{1}}$ and ${\partial y}/{\partial x_{2}}$ at once. Now we illustrate the
calculation of

$\dfrac{\partial y}{\partial x_{2}}.$

By checking the variable $x_{2}$ in the computational graph, we see that
variable $x_{2}$ affects $y$ by affecting $v_{2}$ and $v_{3}$.

$x_{1}$$=2$$v_{1}$$=\log
x_{1}$$v_{4}$$=v_{1}+v_{2}$$x_{2}$$=5$$v_{2}$$=x_{1}\times
x_{2}$$v_{3}$$=\sin{x_{2}}$$v_{5}$$=v_{4}-v_{3}$$f(x_{1},x_{2})$forward
calculation of function valuereverse calculation of derivative value

This dependency, together with the fact that $x_{1}$ is fixed, means if we
would like to calculate $\partial y/\partial x_{2}$, then it is equal to
calculate

$\frac{\partial y}{\partial x_{2}}=\frac{\partial y}{\partial
v_{2}}\frac{\partial v_{2}}{\partial x_{2}}+\frac{\partial y}{\partial
v_{3}}\frac{\partial v_{3}}{\partial x_{2}}.$ (1)

We can rewrite Equation 1 as follows with our notation.

$\bar{x}_{2}=\bar{v}_{2}\frac{\partial v_{2}}{\partial
x_{2}}+\bar{v}_{3}\frac{\partial v_{3}}{\partial x_{2}}.$ (2)

If $\bar{v}_{2}$ and $\bar{v}_{3}$ are available beforehand, all we need is to
calculate ${\partial v_{2}}/{\partial x_{2}}$ and ${\partial v_{3}}/{\partial
x_{2}}$. From the operation between $x_{2}$ and $v_{3}$, we know that
${\partial v_{3}}/{\partial x_{2}}=\cos(x_{2})$. Similarly, we have ${\partial
v_{2}}/{\partial x_{2}}=x_{1}$. Then, the evaluation of $\bar{x}_{2}$ is done
in two steps:

$\begin{split}&\bar{x}_{2}\leftarrow\bar{v}_{3}\frac{\partial v_{3}}{\partial
x_{2}}\\\ &\bar{x}_{2}\leftarrow\bar{x}_{2}+\bar{v}_{2}\frac{\partial
v_{2}}{\partial x_{2}}.\end{split}$

These steps are part of the sequence of a reverse traversal, shown in the
following table.

| $\bar{x}_{1}$ |  |  | $=5.5$
---|---|---|---|---
| $\bar{x}_{2}$ |  |  | $=1.716$
| $\bar{x}_{1}$ | $=\bar{x}_{1}+\bar{v}_{1}\frac{\partial v_{1}}{\partial x_{1}}$ | $=\bar{x}_{1}+\bar{v}_{1}/x_{1}$ | $=5.5$
| $\bar{x}_{2}$ | $=\bar{x}_{2}+\bar{v}_{2}\frac{\partial v_{2}}{\partial x_{2}}$ | $=\bar{x}_{2}+\bar{v}_{2}\times x_{1}$ | $=1.716$
| $\bar{x}_{1}$ | $=\bar{v}_{2}\frac{\partial v_{2}}{\partial x_{1}}$ | $=\bar{v}_{2}\times x_{2}$ | $=5$
| $\bar{x}_{2}$ | $=\bar{v}_{3}\frac{\partial v_{3}}{\partial x_{2}}$ | $=\bar{v}_{3}\times\cos{x_{2}}$ | $=-0.284$
| $\bar{v}_{2}$ | $=\bar{v}_{4}\frac{\partial v_{4}}{\partial v_{2}}$ | $=\bar{v}_{4}\times 1$ | $=1$
| $\bar{v}_{1}$ | $=\bar{v}_{4}\frac{\partial v_{4}}{\partial v_{1}}$ | $=\bar{v}_{4}\times 1$ | $=1$
| $\bar{v}_{3}$ | $=\bar{v}_{5}\frac{\partial v_{5}}{\partial v_{3}}$ | $=\bar{v}_{5}\times(-1)$ | $=-1$
| $\bar{v}_{4}$ | $=\bar{v}_{5}\frac{\partial v_{5}}{\partial v_{4}}$ | $=\bar{v}_{5}\times 1$ | $=1$
| $\bar{v}_{5}$ | $=\bar{y}$ | $=1$ |

To get the desired $\bar{x}_{1}$ and $\bar{x}_{2}$ (i.e., $\partial y/\partial
x_{1}$ and $\partial y/\partial x_{2}$), we begin with

$\bar{v}_{5}=\frac{\partial y}{\partial v_{5}}=\frac{\partial y}{\partial
y}=1.$

From the computational graph, we then get $\bar{v}_{4}$ and $\bar{v}_{3}$.
Because $v_{4}$ affects $y$ only through $v_{5}$, we have

$\bar{v}_{4}=\frac{\partial y}{\partial v_{4}}=\frac{\partial y}{\partial
v_{5}}\frac{\partial v_{5}}{\partial v_{4}}\\\ =\bar{v}_{5}\frac{\partial
v_{5}}{\partial v_{4}}=\bar{v}_{5}\times 1$

The above equation is based on that we already know $\partial y/\partial
v_{5}=\bar{v}_{5}$. Also, the operation from $v_{4}$ to $v_{5}$ is an
addition, so ${\partial v_{5}}/{\partial v_{4}}$ is a constant $1$. By such a
sequence, in the end, we obtain

$\frac{\partial y}{\partial x_{1}}=\bar{x}_{1}\text{ and }\frac{\partial
y}{\partial x_{2}}=\bar{x}_{2}$

at the same time.

##  3 Implementation of Function Evaluation and the Computational Graph

With the basic concepts ready in Section 2, we move to the implementation of
the automatic differentiation. For simplicity, we consider the forward mode.
The reverse mode can be designed in a similar way. Consider a function
$f:R^{n}\to R$ with

$y=f({\boldsymbol{x}})=f(x_{1},x_{2},\dots,x_{n}).$

For any given ${\boldsymbol{x}}$, we show the computation of

$\dfrac{\partial y}{\partial x_{1}}$

as an example.

###  3.1 The Need to Calculate Function Values

We are calculating the derivative, so at the first glance, function values are
not needed. However, we show that function evaluation is necessary due to the
function structure and the use of the chain rule. To explain this, we begin
with knowing that the function of a neural network is usually a nested
composite function

$f({\boldsymbol{x}})=h_{k}(h_{k-1}(\dots h_{1}({\boldsymbol{x}})))$

due to the layered structure. For easy discussion, let us assume that
$f({\boldsymbol{x}})$ is the following general composite function

$f({\boldsymbol{x}})=g(h_{1}({\boldsymbol{x}}),h_{2}({\boldsymbol{x}}),\dots,h_{k}({\boldsymbol{x}})).$

We can see that the example function considered earlier

$f(x_{1},x_{2})=\log x_{1}+x_{1}x_{2}-\sin x_{2}$ (3)

can be written in the following composite function

$\displaystyle g(h_{1}(x_{1},x_{2}),h_{2}(x_{1},x_{2}))$

with

$\displaystyle g(h_{1},h_{2})$ $\displaystyle=h_{1}-h_{2},$ $\displaystyle
h_{1}(x_{1},x_{2})$ $\displaystyle=\log x_{1}+x_{1}x_{2},$ $\displaystyle
h_{2}(x_{1},x_{2})$ $\displaystyle=\sin(x_{2}).$

To calculate the derivative at ${\boldsymbol{x}}={\boldsymbol{x}}_{0}$ using
the chain rule, we have

$\dfrac{\partial f}{\partial
x_{1}}\Big{|}_{{\boldsymbol{x}}={\boldsymbol{x}}_{0}}=\sum_{i=1}^{k}\left(\dfrac{\partial
g}{\partial
h_{i}}\Big{|}_{{\boldsymbol{h}}={\boldsymbol{h}}({\boldsymbol{x}}_{0})}\times\dfrac{\partial
h_{i}}{\partial x_{1}}\Big{|}_{{\boldsymbol{x}}={\boldsymbol{x}}_{0}}\right),$

where the notation

$\dfrac{\partial g}{\partial
h_{i}}\Big{|}_{{\boldsymbol{h}}={\boldsymbol{h}}({\boldsymbol{x}}_{0})}$

means the derivative of $g$ with respect to $h_{i}$ evaluated at
${\boldsymbol{h}}({\boldsymbol{x}}_{0})={\begin{bmatrix}h_{1}({\boldsymbol{x}}_{0})&\cdots&h_{k}({\boldsymbol{x}}_{0})\end{bmatrix}}^{T}$.
Clearly, we must calculate the inner function values
$h_{1}({\boldsymbol{x}}_{0}),\dots,h_{k}({\boldsymbol{x}}_{0})$ first. The
process of computing all $h_{i}({\boldsymbol{x}}_{0})$ is part of (or almost
the same as) the process of computing $f({\boldsymbol{x}}_{0})$. This
explanation tells why for calculating the partial derivatives, we need the
function value first.

Next, we discuss the implementation of getting the function value. For the
function (3), recall we have a table recording the order to get
$f(x_{1},x_{2})$:

| $x_{1}$ |  | $=2$
---|---|---|---
| $x_{2}$ |  | $=5$
| $v_{1}$ | $=\log{x_{1}}$ | $=\log{2}$
| $v_{2}$ | $=x_{1}\times x_{2}$ | $=2\times 5$
| $v_{3}$ | $=\sin{x_{2}}$ | $=\sin{5}$
| $v_{4}$ | $=v_{1}+v_{2}$ | $=0.693+10$
| $v_{5}$ | $=v_{4}-v_{3}$ | $=10.693+0.959$
| $y$ | $=v_{5}$ | $=11.652$

Also, we have a computational graph to generate the computing order

$x_{1}$$=2$$v_{1}$$=\log x_{1}$$\log
2$$v_{4}$$=v_{1}+v_{2}$$0.693+10$$x_{2}$$=5$$v_{2}$$=x_{1}\times
x_{2}$$2\times
5$$v_{3}$$=\sin{x_{2}}$$\sin{5}$$v_{5}$$=v_{4}-v_{3}$$10.693-(-0959)$$f(x_{1},x_{2})$

Therefore, we must check how to build the graph.

###  3.2 Creating the Computational Graph

A graph consists of nodes and edges. We must discuss what a node/edge is and
how to store information. From the graph shown above, we see that each node
represents an intermediate expression:

$\displaystyle v_{1}$ $\displaystyle=\log x_{1},$ $\displaystyle v_{2}$
$\displaystyle=x_{1}\times x_{2},$ $\displaystyle v_{3}$ $\displaystyle=\sin
x_{2},$ $\displaystyle v_{4}$ $\displaystyle=v_{1}\times v_{2},$
$\displaystyle v_{5}$ $\displaystyle=v_{4}-v_{3}.$

The expression in each node is from an operation to expressions in other
nodes. Therefore, it is natural to construct an edge

$u\to v,$

if the expression of a node $v$ is based on the expression of another node
$u$. We say node $u$ is a parent node (of $v$) and node $v$ is a child node
(of $u$). To do the forward calculation, at node $v$ we should store $v$’s
parents. Additionally, we need to record the operator applied on the node’s
parents and the resulting value. For example, the construction of the node

$v_{2}=x_{1}\times x_{2},$

requires to store $v_{2}$’s parent nodes $\\{x_{1},x_{2}\\}$, the
corresponding operator “$\times$” and the resulting value. Up to now, we can
implement each node as a class Node with the following members.

member | data type | example for Node $v_{2}$
---|---|---
numerical value | float | $10$
parent nodes | List[Node] | $[x_{1},x_{2}]$
child nodes | List[Node] | $[v_{4}]$
operator | string |  "mul" (for $\times$)

At this moment, it is unclear why we should store child nodes in our Node
class. Later we will explain why such information is needed. Once the Node
class is ready, starting from initial nodes (which represent $x_{i}$’s), we
use nested function calls to build the whole graph. In our case, the graph for
$y=f(x_{1},x_{2})$ can be constructed via

y = sub(add(log(x1), mul(x1, x2)),sin(x2)).

let us see this process step by step and check what each function must do.
First, our starting point is the root nodes created by the Node class
constructor.

x1$x_{1}$x2$x_{2}$

These root Nodes have empty members “parent nodes,” “child nodes,” and
“operator” with only “numerical value” respectively set to $x_{1}$ and
$x_{2}$. Then, we apply our implemented log(node) to the node x1.

x1$x_{1}$log$v_{1}=\log x_{1}$

The implementation of our log function should create a Node instance to store
$\log(x_{1})$. Therefore, what we have is a wrapping function that does more
than the $\log$ operation; see details in Section 3.3. The created node is the
$v_{1}$ node in our computational graph. Next, we discuss details of the node
creation. From the current $\log$ function and the input node $x_{1}$, we know
contents of the following members:

  * •

parent nodes: $[x_{1}]$

  * •

operator: "log"

  * •

numerical value: $\log 2$

However, we have no information about children of this node. The reason is
obvious because we have not had a graph including its child nodes yet.
Instead, we leave this member “child nodes” empty and let child nodes to write
back the information. By this idea, our log function should add $v_{1}$ to the
“child nodes” of $x_{1}$. See more details later in Section 3.3.

We move on to apply mul(node1, node2) on nodes x1 and x2.

x1$x_{1}$x2$x_{2}$$\times$$v_{2}=x_{1}\times x_{2}$

Similarly, the mul function generates a Node instance. However, different from
log(x1), the node created here stores two parents (instead of one). Then we
apply the function call add(log(x1), mul(x1, x2)).

x1$x_{1}$x2$x_{2}$log$v_{1}=\log x_{1}$$\times$$v_{2}=x_{1}\times
x_{2}$$+$$v_{4}=\log x_{1}+x_{1}\times x_{2}$

Next, we apply sin(node) to x2.

x2$x_{2}$sin$v_{3}=\sin x_{2}$

Last, applying sub(node1,node2) to the output nodes of add(log(x1), mul(x1,
x2)) and sin(x1) leads to

x1$x_{1}$x2$x_{2}$log$v_{1}=\log x_{1}$$\times$$v_{2}=x_{1}\times
x_{2}$$+$$v_{4}=\log x_{1}+x_{1}\times x_{2}$sin$v_{3}=\sin
x_{2}$$-$$v_{5}=\log x_{1}+x_{1}\times x_{2}-\sin x_{2}$

We can conclude that each function generates exactly one Node instance;
however, the generated nodes differ in the operator, the number of parents,
etc.

###  3.3 Wrapping Functions

We mentioned that a function like “mul” does more than calculating the product
of two numbers. Here we show more details. These customized functions “add”,
“mul” and “log” in the previous pages are wrapping functions, which “wrap”
numerical operations with additional codes. An important task is to maintain
the relation between the constructed node and its parents/children. This way,
the information of graph can be preserved.

For example, we may implement the following “mul” function.

Listing 1: The wrapping function “mul”

⬇

def mul(node1, node2):

value = node1.value * node2.value

parent_nodes = [node1, node2]

newNode = Node(value, parent_nodes, "mul")

node1.child_nodes.append(newNode)

node2.child_nodes.append(newNode)

return newNode

In this code, we add the created node to the “child nodes” lists of the two
input nodes: node1 and node2. As we mentioned earlier, when node1 and node2
were created, their lists of child nodes were unknown and left empty. Thus, in
creating each node, we append the node to the list of its parent(s).

The output of the function should be the created node. This setting enables
the nested function call. That is, calling

y = sub(add(log(x1), mul(x1, x2)),sin(x2))

finishes the function evaluation. At the same time, we build the computational
graph.

##  4 Topological Order and Partial Derivatives

Once the computational graph is built, we want to use the information in the
graph to compute

$\dfrac{\partial y}{\partial x_{1}}=\dfrac{\partial v_{5}}{\partial x_{1}}.$

###  4.1 Finding the Topological Order

Recall that $\partial v/\partial x_{1}$ is denoted by $\dot{v}$. From the
chain rule,

$\dot{v}_{5}=\dfrac{\partial v_{5}}{\partial v_{4}}\dot{v}_{4}+\dfrac{\partial
v_{5}}{\partial v_{3}}\dot{v}_{3}.$ (4)

We are able to calculate

$\dfrac{\partial v_{5}}{\partial v_{4}}\text{\ \ and\ \ }\dfrac{\partial
v_{5}}{\partial v_{3}},$ (5)

because the node $v_{5}$ stores the needed information related to its parents
$v_{4}$ and $v_{3}$. We defer the details on calculating (5), so the focus is
now on calculating $\dot{v}_{4}$ and $\dot{v}_{3}$. For $\dot{v}_{4}$, we
further have

$\dot{v}_{4}=\dfrac{\partial v_{4}}{\partial v_{1}}\dot{v}_{1}+\dfrac{\partial
v_{4}}{\partial v_{2}}\dot{v}_{2},$ (6)

which, by the same reason, indicates the need of $\dot{v}_{1}$ and
$\dot{v}_{2}$. On the other hand, we have $\dot{v}_{3}=0$ since $v_{3}$ (i.e.,
$\sin(x_{2})$) is not a function of $x_{1}$. The discussion on calculating
$\dot{v}_{4}$ and $\dot{v}_{3}$ leads us to find that

$\text{$v$ is not reachable from $x_{1}$ in the graph $\Rightarrow$
$\dot{v}=0$}.$ (7)

We say a node $v$ is reachable from a node $u$ if there exists a path from $u$
to $v$ in the graph. From (7), now we only care about nodes reachable from
$x_{1}$. Further, we must properly order nodes reachable from $x_{1}$ so that,
for example, in (4), $\dot{v}_{4}$ and $\dot{v}_{3}$ are ready before
calculating $\dot{v}_{5}$. Similarly, $\dot{v}_{1}$ and $\dot{v}_{2}$ should
be available when calculating $\dot{v}_{4}$.

To consider nodes reachable from $x_{1}$, from the whole computational graph
$G=\langle V,E\rangle$, where $V$ and $E$ are respectively sets of nodes and
edges, we define

$V_{R}=\\{v\in V\mid v\text{ is reachable from }x_{1}\\}$

and

$E_{R}=\\{(u,v)\in E\mid u\in V_{R},\ v\in V_{R}\\}.$

Then,

$G_{R}\equiv\langle V_{R},E_{R}\rangle$

is a subgraph of $G$. For our example, $G_{R}$ is the following subgraph with

$V_{R}=\\{x_{1},v_{1},v_{2},v_{4},v_{5}\\}$

and

$E_{R}=\\{(x_{1},v_{1}),(x_{2},v_{2}),(v_{1},v_{4}),(v_{2},v_{4}),(v_{4},v_{5})\\}.$
$x_{1}$$v_{1}$$v_{4}$$v_{2}$$v_{5}$

We aim to find a “suitable” ordering of $V_{R}$ satisfying that each node
$u\in V_{R}$ comes before all of its child nodes in the ordering. By doing so,
$\dot{u}$ can be used in the derivative calculation of its child nodes; see
(6). For our example, a “suitable” ordering can be

$x_{1},v_{1},v_{2},v_{4},v_{5}.$

In graph theory, such an ordering is called a topological ordering of $G_{R}$.
Since $G_{R}$ is a directed acyclic graph (DAG), a topological ordering must
exist.666We do not get into details, but a proof can be found in Kleinberg and
Tardos (2005). We may use depth first search (DFS) to traverse $G_{R}$ to find
the topological ordering. For the implementation, earlier we included a member
“child nodes” in the Node class, but did not explain why. The reason is that
to traverse $G_{R}$ from $x_{1}$, we must access children of each node.

Based on the above idea, we can have the following code to find a topological
ordering.

Listing 2: Using depth first search to find a topological ordering

⬇

def topological_order(rootNode):

def add_children(node):

if node not in visited:

visited.add(node)

for child in node.child_nodes:

add_children(child)

ordering.append(node)

ordering, visited = [], set()

add_children(rootNode)

return list(reversed(ordering))

The function add_children implements the depth-first-search of a DAG. From the
input node, it sequentially calls itself by using each child as the input.
This way explores all nodes reachable from the input node. After that, we
append the input node to the end of the output list. Also, we must maintain a
set of visited nodes to ensure that each node is included in the ordering
exactly once. For our example, the input in calling the above function is
$x_{1}$, which is also the root node of $G_{R}$. The left-most path of the
depth-first search is

$x_{1}\rightarrow v_{1}\rightarrow v_{4}\rightarrow v_{5},$ (8)

so $v_{5}$ is added first. In the end, we get the following list

$[v_{5},v_{4},v_{1},v_{2},x_{1}].$

Then, by reversing the list, a node always comes before its children. One may
wonder whether we can add a node to the list before adding its child nodes.
This way, we have a simpler implementation without needing to reverse the list
in the end. However, this setting may fail to generate a topological ordering.
We obtain the following list for our example:

$[x_{1},v_{1},v_{4},v_{5},v_{2}].$

A violation occurs because $v_{2}$ does not appear before its child $v_{4}$.
The key reason is that in a DFS path, a node may point to another node that
was added earlier through a different path. Then this node becomes after one
of its children. For our example,

$x_{1}\to v_{2}\to v_{4}\to v_{5}$

is a path processed after the path in (8). Thus, $v_{2}$ is added after
$v_{4}$ and a violation occurs. Reversing the list can resolve the problem. To
this end, in the function add_children, we must append the input node in the
end.

In automatic differentiation, methods based on the topological ordering are
called tape-based methods. They are used in some real-world implementations
such as Tensorflow. The ordering is regarded as a tape. We read the nodes one
by one from the beginning of the sequence (tape) to calculate the derivative
value.

Based on the obtained ordering, subsequently let us see how to compute each
$\dot{v}$.

###  4.2 Computing the Partial Derivative

By the chain rule, we have

$\dot{v}=\sum_{u\in\text{$v$'s parents}}\dfrac{\partial v}{\partial u}\
\dot{u}.$ (9)

If we calculate the derivative according to the topological order, the second
term

$\dot{u}=\dfrac{\partial u}{\partial x_{1}}$

should be readily available when we’re computing $\dot{v}$. Therefore, all we
need is to check the calculation of the first term

$\dfrac{\partial v}{\partial u}.$

At $v$, we know that $u$ is one of its parent(s). We further know the
operation involving $v$’s parent(s). For example, we have $v_{4}=v_{1}\times
v_{2}$, so

$\dfrac{\partial v_{4}}{\partial v_{1}}=v_{2}\text{ and }\dfrac{\partial
v_{4}}{\partial v_{2}}=v_{1}.$

These values can be immediately computed and stored when we construct the
computational graph. Therefore, we add one member “gradient w.r.t. parents” to
our Node class. In addition, we need a member “partial derivative” to store
the accumulated sum in the calculation of (9). In the end, this member stores
the $\dot{v}_{i}$ value. More details are in Listing 4. The complete list of
members of our node class is in the following table.

member | data type |  | example for Node $v_{2}$
---
numerical value | float | $10$
parent nodes | List[Node] | $[x_{1},x_{2}]$
child nodes | List[Node] | $[v_{4}]$
operator | string | "mul"
gradient w.r.t parents | List[float] | $[5,2]$
partial derivative | float | $5$

We update the mul function accordingly.

Listing 3: The wrapping function “mul”. The change from Listing 1 is in red
color.

⬇

def mul(node1, node2):

value = node1.value * node2.value

parent_nodes = [node1, node2]

newNode = Node(value, parent_nodes, "mul")

newNode.grad_wrt_parents = [node2.value,node1.value]

node1.child_nodes.append(newNode)

node2.child_nodes.append(newNode)

return newNode

As shown above, we must compute

$\dfrac{\partial\texttt{ newNode}}{\partial\texttt{ parentNode}}$

for each parent node in constructing a new child node. Here are some examples
other than the mul function:

  * •

For add(node1, node2), we have

$\dfrac{\partial\texttt{ newNode}}{\partial\texttt{
Node1}}=\dfrac{\partial\texttt{ newNode}}{\partial\texttt{ Node2}}=1,$

so the red line is replaced by

$\texttt{newNode.grad\\_wrt\\_parents = [1., 1.]}.$

  * •

For log(node), we have

$\dfrac{\partial\texttt{ newNode}}{\partial\texttt{
Node}}=\dfrac{1}{\texttt{Node.value}},$

so the red line becomes

$\texttt{newNode.grad\\_wrt\\_parents = [1/node.value]}.$

Now, we know how to get each term in (9), i.e., the chain rule for calculating
$\dot{v}$. Therefore, if we follow the topological ordering, all $\dot{v}_{i}$
(i.e., partial derivatives with respect to $x_{1}$) can be calculated. An
implementation to compute the partial derivatives is as follows. Here we store
the resulting value in the member partial_derivative of each node.

Listing 4: Evaluating derivatives

⬇

def forward(rootNode):

rootNode.partial_derivative = 1

ordering = topological_order(rootNode)

for node in ordering[1:]:

partial_derivative = 0

for i in range(len(node.parent_nodes)):

dnode_dparent = node.grad_wrt_parents[i]

dparent_droot = node.parent_nodes[i].partial_derivative

partial_derivative += dnode_dparent * dparent_droot

node.partial_derivative = partial_derivative

###  4.3 Summary

The procedure for forward mode includes three steps:

  1. 1.

Create the computational graph

  2. 2.

Find a topological order of the graph associated with $x_{1}$

  3. 3.

Compute the partial derivative with respect to $x_{1}$ along the topological
order

We discuss not only how to run each step but also what information we should
store. This is a minimal implementation to demonstrate the forward mode
automatic differentiation.

## Acknowledgements

This work was supported by National Science and Technology Council of Taiwan
grant 110-2221-E-002-115-MY3.

## References

  * Abadi et al. (2016) M. Abadi, P. Barham, J. Chen, Z. Chen, A. Davis, J. Dean, M. Devin, S. Ghemawat, G. Irving, M. Isard, M. Kudlur, J. Levenberg, R. Monga, S. Moore, D. G. Murray, B. Steiner, P. Tucker, V. Vasudevan, P. Warden, M. Wicke, Y. Yu, and X. Zheng.  Tensorflow: A system for large-scale machine learning.  In _Proceedings of the 12th USENIX Symposium on Operating Systems Design and Implementation (OSDI)_ , pages 265–283, 2016.
  * Bartholomew-Biggs et al. (2000) M. Bartholomew-Biggs, S. Brown, B. Christianson, and L. Dixon.  Automatic differentiation of algorithms.  _Journal of Computational and Applied Mathematics_ , 124(1-2):171–190, 2000.
  * Baydin et al. (2018) A. G. Baydin, B. A. Pearlmutter, A. A. Radul, and J. M. Siskind.  Automatic differentiation in machine learning: a survey.  _Journal of Machine Learning Research_ , 18(153):1–43, 2018.
  * Chinchalkar (1994) S. Chinchalkar.  The application of automatic differentiation to problems in engineering analysis.  _Computer Methods in Applied Mechanics and Engineering_ , 118(1-2):197–207, 1994.
  * Kleinberg and Tardos (2005) J. Kleinberg and E. Tardos.  _Algorithm Design_.  Addison-Wesley Longman Publishing Co., Inc., 2005.  ISBN 0321295358.
  * Margossian (2019) C. C. Margossian.  A review of automatic differentiation and its efficient implementation.  _Wiley interdisciplinary reviews: data mining and knowledge discovery_ , 9(4):e1305, 2019.
  * Paszke et al. (2017) A. Paszke, S. Gross, S. Chintala, G. Chanan, E. Yang, Z. DeVito, Z. Lin, A. Desmaison, L. Antiga, and A. Lerer.  Automatic differentiation in Pytorch.  2017\.


# Detecting danger in gridworlds using
Gromov’s Link Condition

Thomas F Burns
Neural Coding and Brain Computing Unit
OIST Graduate University
1919-1 Tancha, Onna-son, Kunigami-gun
Okinawa, Japan 904-0495
<EMAIL_ADDRESS>
&Robert Tang
Department of Pure Mathematics
Xi’an Jiaotong–Liverpool University
111 Ren’ai Road, Suzhou Industrial Park
Suzhou, Jiangsu Province, China 215123
<EMAIL_ADDRESS>

###### Abstract

Gridworlds have been long-utilised in AI research, particularly in
reinforcement learning, as they provide simple yet scalable models for many
real-world applications such as robot navigation, emergent behaviour, and
operations research. We initiate a study of gridworlds using the mathematical
framework of reconfigurable systems and state complexes due to Abrams, Ghrist
& Peterson. State complexes represent all possible configurations of a system
as a single geometric space, thus making them conducive to study using
geometric, topological, or combinatorial methods. The main contribution of
this work is a modification to the original Abrams, Ghrist & Peterson setup
which we introduce to capture agent braiding and thereby more naturally
represent the topology of gridworlds. With this modification, the state
complexes may exhibit geometric defects (failure of Gromov’s Link Condition).
Serendipitously, we discover these failures occur exactly where undesirable or
dangerous states appear in the gridworld. Our results therefore provide a
novel method for seeking guaranteed safety limitations in discrete task
environments with single or multiple agents, and offer useful safety
information (in geometric and topological forms) for incorporation in or
analysis of machine learning systems. More broadly, our work introduces tools
from geometric group theory and combinatorics to the AI community and
demonstrates a proof-of-concept for this geometric viewpoint of the task
domain through the example of simple gridworld environments.

##  1 Introduction

The notion of a state (or configuration/phase) space is commonly used in
mathematics and physics to represent all the possible states of a given system
as a single geometric (or topological) object. This perspective provides a
bridge which allows for tools from geometry and topology to be applied to the
system of concern. Moreover, certain features of a given system are reflected
by some geometric aspects of the associated state space (such as gravitational
force being captured by _curvature_ in spacetime). Thus, insights into the
structure of the original system can be gleaned by reformulating them in
geometric terms.

In discrete settings, state spaces are typically represented by graphs or
their higher dimensional analogues such as simplicial complexes or cube
complexes. Abrams, Ghrist & Peterson’s _state complexes_ [AG04, GP07] provide
a general framework for representing discrete reconfigurable systems as non-
positively curved (NPC) cube complexes, giving access to a wealth of
mathematical and computational benefits via efficient optimisation algorithms
guided by geometric insight [AOS12]. These have been used to develop efficient
algorithms for robotic motion planning [ABY14, ABCG17] and self-
reconfiguration of modular robots [LR10]. NPC cube complexes also possess rich
hyperplane structures which geometrically capture binary classification [CN05,
Wis12, Sag14]. However, their broader utility to fields like artificial
intelligence (AI) has until now been relatively unexplored.

Our main contribution is the first application of this geometric approach (of
using state complexes) to the setting of multi-agent gridworlds. We introduce
a natural modification to the state complex appropriate to the setting of
gridworlds (to capture the braiding or relative movements of agents); however,
this can lead to state complexes which are no longer NPC. Nevertheless, by
applying Gromov’s Link Condition, we completely characterise when positive
curvature occurs in our new state complexes, and relate this to features of
the gridworlds (see Theorem 5.2). Serendipitously, we discover that the states
where Gromov’s Link Condition fails are those in which agents can potentially
collide. In other words, collision-detection is naturally embedded into the
intrinsic geometry of the system. Current approaches to collision-detection
and navigation during multi-agent navigation often rely on modelling and
predicting collisions based on large training datasets [KFGE19, FLLP20,
QZC+21] or by explicitly modelling physical movements [KIU21]. However, our
approach is purely geometric, requires no training, and can accommodate many
conceivable types of actions and inter-actions, not just simple movements.

Our work relates to a growing body of research aimed towards understanding,
from a geometric perspective, how deep learning methods transform input data
into decisions, memories, or actions [HR17, LAG+20, SPG+21, AVBP21, SMK11].
However, such studies do not usually incorporate the geometry of the
originating domain or task in a substantial way, before applying or
investigating the performance of learning algorithms – and even fewer do so
for multi-agent systems. One possible reason for this is a lack of known
suitable tools. Our experimental and theoretical results show there is a
wealth of geometric information available in (even very simple) task domains,
which is accessible using tools from geometric group theory and combinatorics.

##  2 State complex of a gridworld

Figure 1: A $3\times 3$ gridworld with one agent (a koala) and one object (a
beach ball).

A _gridworld_ is a two-dimensional, flat array of _cells_ arranged in a grid,
much like a chess or checker board. Each cell can be occupied or unoccupied. A
cell may be occupied, in our setting, by one and only one freely-moving agent
or movable object. Other gridworlds may include rewards, punishments, buttons,
doors, locks, keys, checkpoints, dropbears, etc., much like many basic video
games. Gridworlds have been a long-utilised setting in AI research,
particularly reinforcement learning, since they are simple yet scalable in
size and sophistication [DSHLKT20, WKK20]. They also offer clear analogies to
many real-world applications or questions, such as robot navigation [HHA21],
emergent behaviour [KAP20], and operations research [LSS+21]. For these
reasons, gridworlds have also been developed for formally specifying problems
in AI safety [LMK+17].

A _state_ of a gridworld can be encoded by assigning each cell a label. In the
example shown in Figure 1, these labels are shown for an agent, an object, and
empty floor. A change in the state, such as an agent moving from one cell to
an adjacent empty cell, can be encoded by _relabelling_ the cells involved.
This perspective allows us to take advantage of the notion of reconfigurable
systems as introduced by Abrams, Ghrist & Peterson [AG04, GP07].

More formally, consider a graph $G$ and a set $\mathcal{A}$ of labels. A
_state_ is a function $s:V(G)\to\mathcal{A}$, i.e. an assignment of a label to
each vertex of $G$. A possible relabelling is encoded using a generator
$\phi$; this comprises the following data:

  * •

a subgraph $SUP(\phi)\subseteq G$ called the support;

  * •

a subgraph $TR(\phi)\subseteq SUP(\phi)$ called the trace; and

  * •

an unordered pair of _local states_

$u_{0}^{loc},u_{1}^{loc}:V(SUP(\phi))\to\mathcal{A}$

that agree on $V(SUP(\phi))-V(TR(\phi))$ but differ on $V(TR(\phi))$.

A generator $\phi$ is _admissible_ at a state $s$ if
$s|_{SUP(\phi)}=u_{0}^{loc}$ (or $u_{1}^{loc}$), in other words, if the
assignment of labels to $V(SUP(\phi))$ given by $s$ completely matches the
labelling from (exactly) one of the two local states. If this holds, we may
apply $\phi$ to the state $s$ to obtain a new state $\phi[s]$ given by

$\phi[s](v):=\begin{cases}u_{1}^{loc}(v),&v\in V(TR(\phi))\\\
s(v),&\textrm{otherwise.}\end{cases}$

This has the effect of relabelling the vertices in (and only in) $TR(\phi)$ to
match the other local state of $\phi$. Since the local states are unordered,
if $\phi$ is admissible at $s$ then it is also admissible at $\phi[s]$;
moreover, $\phi[\phi[s]]=s$.

######  Definition 2.1 (Reconfigurable system [AG04, GP07]).

A _reconfigurable system_ on a graph $G$ with a set of labels $\mathcal{A}$
consists of a set of generators together with a set of states closed under the
action of admissible generators.

Configurations and their reconfigurations can be used to construct a _state
graph_ (or transition graph), which represents all possible states and
transitions between these states in a reconfigurable system. More formally:

######  Definition 2.2 (State graph).

The state graph $\mathcal{S}^{(1)}$ associated to a reconfigurable system has
as its vertices the set of all states, with edges connecting pairs of states
differing by a single generator.

Let us now return our attention to gridworlds. We define a graph $G$ to have
vertices corresponding to the cells of a gridworld, with two vertices declared
adjacent in $G$ exactly when they correspond to neighbouring cells (i.e. they
share a common side). Our set of labels is chosen to be

$\mathcal{A}=\\{\texttt{`agent'},\texttt{`object'},\texttt{`floor'}\\}.$

We do not distinguish between multiple instances of the same label. We
consider two generators:

  * •

Push/Pull. An agent adjacent to an object is allowed to push/pull the object
if there is an unoccupied floor cell straight in front of the object/straight
behind the agent; and

  * •

Move. An agent is allowed to move to a neighbouring unoccupied floor cell.

These two generators have the effect of enabling agents to at any time move in
any direction not blocked by objects or other agents, and for agents to push
or pull objects within the environment into any configuration if there is
sufficient room to move. For both types of generators, the trace coincides
with the support. For the Push/Pull generator, the support is a row or column
of three contiguous cells, whereas for the Move generator, the support is a
pair of neighbouring cells. A simple example of a state graph, together with
the local states for the two generator types, is shown in Figure 2.

Figure 2: An example $1\times 5$ gridworld with one agent and one object with
two generators – Push/Pull and Move – and the resulting state graph. In the
state graph, edge colours indicate the generator type which relabels the
gridworld.

In a typical reconfigurable system, there may be many admissible generators at
a given state $s$. If the trace of an admissible generator $\phi_{1}$ is
disjoint from the support of another admissible generator $\phi_{2}$, then
$\phi_{2}$ remains admissible at $\phi_{1}[s]$. This is because the
relabelling by $\phi_{1}$ does not interfere with the labels on
$SUP(\phi_{2})$. More generally, a set of admissible generators
$\\{\phi_{1},\ldots,\phi_{n}\\}$ at a state $s$ _commutes_ if
$SUP(\phi_{i})\cap TR(\phi_{j})=\emptyset$ for all $i\neq j$. When this holds,
these generators can be applied independently of one another, and the
resulting state does not depend on the order in which they are applied. A
simple example of this in the context of gridworlds is a large room with $n$
agents spread sufficiently far apart to allow for independent simultaneous
movement.

Figure 3: State complex of a $2\times 2$ gridworld with two agents. Shading
indicates squares attached to the surrounding 4–cycles.

Abrams, Ghrist & Peterson represent this mutual commutativity by adding higher
dimensional cubes to the state graph to form a cube complex called the _state
complex_. We give an informal definition here, and refer to their papers for
the precise formulation [AG04, GP07]. Further background on cube complexes can
be found in [Wis12, Sag14]. If $\\{\phi_{1},\ldots,\phi_{n}\\}$ is a set of
commuting admissible generators at a state $s$ then there are $2^{n}$ states
that can be obtained by applying any subset of these generators to $s$. These
$2^{n}$ states form the vertices of an $n$–cube in the state complex. Each
$n$–cube is bounded by $2n$ faces, where each face is an $(n-1)$–cube: by
disallowing a generator $\phi_{i}$, we obtain a pair of faces corresponding to
those states (in the given $n$–cube) that agree with one of the two respective
local states of $\phi_{i}$ on $SUP(\phi_{i})$.

######  Definition 2.3 (State complex).

The _state complex_ $\mathcal{S}$ of a reconfigurable system is the cube
complex constructed from the state graph $\mathcal{S}^{(1)}$ by inductively
adding cubes as follows: whenever there is a set of $2^{n}$ states related by
a set of $n$ admissible commuting generators, we add an $n$–cube so that its
vertices correspond to the given states, and so that its $2n$ boundary faces
are identified with all the possible $(n-1)$–cubes obtained by disallowing a
generator. In particular, every cube is uniquely determined by its vertices.

In our gridworlds setting, each generator involves exactly one agent. This
means commuting generators can only occur if there are multiple agents. A
simple example of a state complex for two agents in a $2\times 2$ room is
shown in Figure 3. Note that there are six embedded $4$–cycles in the state
graph, however, only two of these are filled in by squares: these correspond
to independent movements of the agents, either both horizontally or both
vertically.

##  3 Exploring gridworlds with state complexes

To compute the state complex of a (finite) gridworld, we first initialise an
empty graph $\mathcal{G}$ and an empty ‘to-do’ list $\mathcal{L}$. As input,
we take a chosen state of the gridworld to form the first vertex of
$\mathcal{G}$ and also the first entry on $\mathcal{L}$. The state complex is
computed according to a breadth-first search by repeatedly applying the
following:

  * •

Let $v$ be the first entry on $\mathcal{L}$. List all admissible generators at
$v$. For each such generator $\phi$:

    * –

If $\phi[v]$ already appears as a vertex of $\mathcal{G}$, add an edge between
$v$ and $\phi[v]$ (if it does not already exist).

    * –

If $\phi[v]$ does not appear in $\mathcal{G}$, add it as a new vertex to
$\mathcal{G}$ and add an edge connecting it to $v$. Append $\phi[v]$ to the
end of $\mathcal{L}$.

  * •

Remove $v$ from $\mathcal{L}$.

The process terminates when $\mathcal{L}$ is empty. The output is the graph
$\mathcal{G}$. When $\mathcal{L}$ is empty, we have fully explored all
possible states that can be reached from the initial state. It may be possible
that the true state graph is disconnected, in which case the above algorithm
will only return a connected component $\mathcal{G}$. For our purposes, we
shall limit our study to systems with connected state graphs. From the state
graph, we construct the state complex by first finding all $4$–cycles in the
state graph. Then, by examining the states involved, we can determine whether
a given $4$–cycle bounds a square representing a pair of commuting moves.

To visualise the state complex, we first draw the state graph using the
Kamada–Kawai force-directed algorithm [KK89] which attempts to draw edges to
have similar length. We then shade the region(s) enclosed by $4$–cycles
representing commuting moves. For ease of visual interpretation in our
figures, we do not also shade higher-dimensional cubes, although such cubes
are noticeable and can be easily computed and visualised if desired.

Figure 4: State complex (left) of a $3\times 3$ gridworld with one agent and
one object (right). The darker vertex in the state complex represents the
state shown in the gridworld state on the right. Edges in the state complex
are coloured according to their generator – orange for Push/Pull and maroon
for Move. Grey circles which group states where the ball is static have been
added to illustrate the different scales of geometry.

Constructing and analysing state complexes of gridworlds is in and of itself
an interesting and useful way of exploring their intrinsic geometry. For
example, Figure 4 shows the state complex of a $3\times 3$ gridworld with one
agent and one object. The state complex reveals two scales of geometry: larger
‘blobs’ of states organised in a $3\times 3$ grid, representing the location
of the object; and, within each blob, copies of the room’s remaining empty
space, in which the agent may walk around and approach the object to
Push/Pull. Each $12$–cycle ‘petal’ represents a $12$–step choreography wherein
the agent pushes and pulls the object around in a $4$–cycle in the gridworld.
In this example, the state complex is the state graph, since there are no
possible commuting moves.

The examples discussed thus far all have planar state graphs. Planarity does
not hold in general – indeed, the $n$–cube graph for $n\geq 4$ is non-planar,
and a state graph can contain $n$–cubes if the gridworld has $n$ agents and
sufficient space to move around. It is tempting to think that the state
complex of a gridworld with more agents should therefore look quite different
to one with fewer agents. However, Figure 5 shows this may not always be the
case: there is a symmetry induced by swapping all ‘agent’ labels with ‘floor’
labels.

Figure 5: State complex (centre) of a $3\times 3$ gridworld with three agents
(left) and six agents (right). They share the same state complex due to the
‘agent’ $\leftrightarrow$ ‘floor’ label inversion symmetry.

##  4 Dancing with myself

The state complex of a gridworld with $n$ agents can be thought of as a
discrete analogue of the configuration space of $n$ points on the 2D–plane.
However, there is a problem with this analogy: there can be ‘holes’ created by
$4$–cycles in the state complex where a single agent walks in a small square-
shaped dance by itself, as shown in Figure 6.

The presence of these holes would suggest something meaningful about the
underlying gridworld’s intrinsic topology, e.g., something obstructing the
agent’s movement at that location in the gridworld that the agent must move
around. In reality, the environment is essentially a (discretised) 2D–plane
with nothing blocking the agent from traversing those locations. Indeed, these
‘holes’ are uninteresting topological quirks which arise due to the
representation of the gridworld as a graph. We therefore deviate from the
original definition of state complexes by Abrams, Ghrist & Peterson [AG04,
GP07] and choose to fill in these ‘dance’ $4$–cycles with squares.111Ghrist
and Peterson themselves ask if there could be better ways to complete the
state graph to a higher-dimensional object with better properties (Question
6.4 in [GP07]).

Figure 6: State complex of a $2\times 2$ gridworld with one agent under the
original definition of Abrams, Ghrist & Peterson [AG04, GP07] (left) and with
our modification (right). The blue shading is a filled in square indicating a
dance.

Formally, we define a dance $\delta$ to comprise the following data:

  * •

the support $SUP(\delta)$ given by a $2\times 2$ subgrid in the gridworld,

  * •

four local states defined on $SUP(\delta)$, each consisting of exactly one
agent label and three floor labels, and

  * •

four Move generators, each of which transitions between two of the four local
states (as in Figure 6).

We say that $\delta$ is _admissible_ at a state $s$ if $s|_{SUP(\delta)}$
agrees with one of the four local states of $\delta$. Moreover, these four
local states are precisely the states that can be reached when we apply some
combination of the four constituent Moves. We do not define the trace of a
dance, however, we may view the trace of each of the four constituent Moves as
subgraphs of $SUP(\delta)$.

The notion of commutativity can be extended to incorporate dancing. Suppose
that we have a set
$\\{\phi_{1},\ldots,\phi_{l},\delta_{1},\ldots,\delta_{m}\\}$ of $l$
admissible generators and $m$ admissible dances at a state $s$. We say that
this set _commutes_ if the supports of its elements are pairwise disjoint.
When this holds, there are $2^{l+2m}$ possible states that can be obtained by
applying some combination of the generators and dances to $s$: there are two
choices of local state for each $\phi_{i}$, and four for each $\delta_{j}$. We
capture this extended notion of commutativity by attaching additional cubes to
the state complex to form our modified state complex.

######  Definition 4.1 (Modified state complex).

The _modified state complex_ $\mathcal{S}^{\prime}$ of a gridworld is the cube
complex obtained by filling in the state graph $\mathcal{S}^{(1)}$ with higher
dimensional cubes whenever there is a set of commuting moves or dances.
Specifically, whenever a set of $2^{l+2m}$ states are related by a commuting
set of $l$ generators and $m$ dances, we add an $n$–cube having the given set
of states as its vertices, where $n=l+2m$. Each of the $2n$ faces of such an
$n$–cube is identified with an $(n-1)$–cube obtained by either disallowing a
generator $\phi_{i}$ and choosing one of its two local states, or replacing a
dance $\delta_{j}$ with one of its four constituent Moves.

Our modification removes uninteresting topology. This can be observed by
examining $4$–cycles in $\mathcal{S}^{\prime}$. On the one hand, some
$4$–cycles are trivial (they can be ‘filled in’): _dancing-with-myself_
$4$–cycles, and _commuting moves_ (two agents moving back and forth)
$4$–cycles (which were trivial under the original definition). These represent
trivial movements of agents relative to one another. On the other hand, there
is a non-trivial $4$–cycle in the state complex for two agents in a $2\times
2$ room, as can be seen in the centre of Figure 3 (here, no dancing is
possible so the modified state complex is the same as the original). This
$4$–cycle represents the two agents moving half a ‘revolution’ relative to one
another – indeed, performing this twice would give a full revolution. (There
are three other non-trivial $4$–cycles, topologically equivalent to this
central one, that also achieve the half-revolution.)

In a more topological sense222By considering the fundamental group., by
filling in such squares and higher dimensional cubes, our state complexes
capture the non-trivial, essential relative movements of the agents. This can
be used to study the braiding or mixing of agents, and also allows us to
consider path-homotopic paths as ‘essentially’ the same. One immediate
difference this creates with the original state complexes is a loss of
symmetries like those shown in Figure 5, since there is no label inversion for
a dance when other agents are crowding the dance-floor.

##  5 Gromov’s Link Condition

The central geometric characteristic of Abrams, Ghrist, & Peterson’s state
complexes is that they are _non-positively curved_ (NPC). Indeed, this local
geometric condition is conducive for developing efficient algorithms for
computing geodesics. However, with our modified state complexes, this NPC
geometry is no longer guaranteed – we test for this on a vertex-by-vertex
basis using a classical geometric result due to Gromov (see also Theorem 5.20
of [BH99] and [Sag14]).

######  Theorem 5.1 (Gromov’s Link Condition [Gro87]).

A finite-dimensional cube complex is NPC if and only if the link of every
vertex is a flag simplicial complex. ∎

Figure 7: The two situations which lead to failure of Gromov’s Link Condition
in multi-agent gridworlds. Maroon arrows indicate admissible moves and blue
squares indicate admissible dances. Note that in the links (bottom row), the
triangle is missing in the left example, while the (solid) tetrahedron is
missing in the right (however, all 2D faces are present). This is due to the
respective collections of moves and dances failing to commute – an agent
interrupts the other’s dance (left) or two dances collide (right).

We provide a brief mathematical background on cube complexes and the finer
details of Gromov’s Link Condition in Appendix A.1. For our current purposes,
it is sufficient to know that under the Abrams, Ghrist & Peterson setup, if
$v$ is a state in $\mathcal{S}$ then the vertices of its link $lk(v)$
represent the possible admissible generators at $v$. Since cubes in
$\mathcal{S}$ are associated with commuting sets of generators, each simplex
in $lk(v)$ represents a set of commuting generators. Gromov’s Link Condition
for $lk(v)$ can be reinterpreted as follows: whenever a set of admissible
generators is _pairwise_ commutative, then it is _setwise_ commutative. Using
this, it is straightforward for Abrams, Ghrist & Peterson to verify that this
always holds for their state complexes (see Theorem 4.4 of [GP07]).

For our modified states complexes, the situation is not as straightforward.
The key issue is that our cubes do not only arise from commuting generators –
we must take dances into account. Indeed, when attempting to prove that
Gromov’s Link Condition holds, we discovered some very simple gridworlds where
it actually fails; see Figure 7 and Appendix A.4.

Failure of the Link Condition can indicate available moves at some state that
cannot be safely performed simultaneously and independently without risking
collisions between labels. Another interpretation of positive curvature in
this context is something akin to what real-time computer strategy games call
‘fog of war’ (distance-dependent limiting of observations which extends from
the player-controlled agents), and more specifically the viewable distance
from an agent’s line-of-sight. Such fog makes AI systems operating in such
environments particularly challenging, although remarkable success has been
achieved in games like StarCraft [VBC+19].

Despite this apparent drawback, we nevertheless show that Figure 7 accounts
for all the possible failures of Gromov’s Link Condition in the setting of
agent-only gridworlds333While writing this paper, the first author was
involved in two scooter accidents – collisions involving only agents (luckily
without serious injury). So, while this class of gridworlds is strictly
smaller than those also involving objects or other labels, it is by no means
an unimportant one. If only the scooters had Gromov’s Link Condition
checkers!.

######  Theorem 5.2 (Gromov’s Link Condition in the modified state complex).

Let $v$ be a vertex in the modified state complex $\mathcal{S}^{\prime}$ of an
agent-only gridworld. Then

  * •

$lk(v)$ satisfies Gromov’s Link Condition if and only if it has no empty
$2$–simplices nor $3$–simplices444In other words, if there are no ‘hollow’
triangles or tetrahedra like those in Figure 7., and

  * •

if $lk(v)$ fails Gromov’s Link Condition then there exist a pair of agents
whose positions differ by either a knight move or a $2$–step bishop move (as
in Figure 7).

We provide a proof in Appendix A.2. Consequently, if the Link Condition fails
at all, it must fail at dimension 2 or 3. This can be interpreted as saying
that we only need a bounded amount of foresight to detect potential
collisions: under fog-of-war, each agent needs a line-of-sight of only four
moves.

Positive curvature could indicate collisions between any specified labels
(e.g., objects), however, for this interpretation to be valid we would need to
carefully identify which other potential cycles in the state complex ought to
be filled in. Doing this in a ‘natural’ way is in itself a non-trivial task,
and is the subject of further investigation.

##  6 Experiments and applications

Although our main contribution is theoretical, we conduct some small initial
experiments to demonstrate the type of information which can be captured in
the geometry and topology (see Appendix A.4). To run these experiments, we
developed and used a custom Python-based tool (detailed in Appendix A.3). Our
focus on small rooms is largely expository, i.e., they are the simplest non-
trivial examples illustrating the key features we want to isolate, and
naturally reoccur in all larger rooms. Our intention is also to demonstrate a
combinatorial explosion in the number of states. We don’t recommend
constructing the entire state complex in practical applications (indeed, to
implement addition of integers on a computer, it is infeasible and unnecessary
to construct _all_ integers).

######  Remark 6.1.

By a simple counting argument, one can deduce the total number of states in a
gridworld. For an agent-only gridworld with $n$ cells and $k$ agents, there is
a total of $\binom{n}{k}$ states. If there are $n$ cells, $k$ agents, and $j$
objects, then there are $\binom{n}{k}\binom{n-k}{j}$ states. Thus, even for a
moderately sized $10\times 10$ room with 50 agents, there are
$\binom{100}{50}\approx 1.008\times 10^{29}$ vertices in the state complex.

By Theorem 5.2, checking if $lk(v)$ satisfies Gromov’s Link Condition requires
computing the link only up to dimension $3$ and then checking whether it is a
flag complex; if not, we count the number of empty simplices. Checking this
for a given vertex in the state complex is not too computationally demanding,
however when a state complex has many vertices it becomes more difficult. In
practical applications, such as calculating collision-avoiding navigation
routes, it is – again, by Theorem 5.2 – only necessary to construct a small
local subcomplex. But perhaps even more importantly, to detect potential
collisions between agents, it is not even necessary to construct $lk(v)$,
since Theorem 5.2 provides a computational shortcut: just check for supports
of knight or two-step bishop moves between agents.

By using Gromov’s Link Condition, we can identify a precise measure of how far
ahead agents ought to look in order to safely proceed without fear of
collisions. Appendix A.4 gives a summary analysis of a $3\times 3$ room with
varying numbers of agents. We noticed several symmetries. Commuting moves and
the number of states have a symmetry about $4.5$ agents (due to the label-
inversion symmetry as previously illustrated in Figure 5). However, curiously,
the number of dances has a symmetry about $3.5$ agents. This difference leads
to the asymmetrical distribution of positive curvature and failures of
Gromov’s Link Condition – which, while maximal for $3$ agents as a proportion
of total states, exhibited the highest mean failure rate for $4$ agents.

This shows that, heuristically, we expect most states to satisfy NPC (see
Appendix A.4), and so existing greedy algorithms [AOS12] for calculating
geodesics will work well in most situations. However, to implement an
efficient, collision-free path-finding algorithm in our modified state
complexes, we need to add an additional check. Specifically, when we are near
a potentially dangerous state, we should implement a predefined ‘detour’ to
avoid the collision, which can be done on a local basis using the identified
supports which lead to positive curvature (as in Figure 7).

##  7 Conclusions and future directions

This study presents novel applications of tools from geometric group theory
and combinatorics to the AI research community, opening new ways for recasting
and analysing AI problems as geometric ones. Using these tools, we show an
example of how the intrinsic geometry of a task space serendipitously embeds
safety information and makes it possible to determine how far ahead in time an
AI system needs to observe to be guaranteed of avoiding dangerous actions.

Leike et al. [LMK+17] show deep reinforcement learning agents cannot solve
many AI safety problems specified on gridworlds, e.g., minimising unwanted
side-effects or ensuring robustness to agent self-modification. Having
described the agent-only case in this study, there is now ripe opportunity to
account for positive curvature or other geometric features arising due to
other labels or generators (actions) present in specified AI safety problems,
e.g., agents pushing/pulling objects, pressing buttons, modifying their form
or behaviour, rewards/punishments, opening/unlocking doors, etc.. By
considering _directed_ modified state complexes, irreversible actions can be
captured by ‘invariant subcomplexes’ (i.e., you can’t escape from them),
allowing geometric study of the tree/flowchart of irreversible actions and
related recurrence/transience. Braiding can be used to study route planning,
back-tracking, cooperation, assembly, and topological entropy in congestion
[Ghr09]. Numerous extensions are possible, allowing us to study and
geometrically represent further problems with a view to developing efficient,
geometrically-inspired local algorithms without the need for training.

Do learning algorithms already implement such geometrically-inspired
algorithms, the related geometry, or approximations thereof? To find out, we
are investigating how modified state complexes map to learned internal
representations of neural networks trained to predict multi-agent gridworld
dynamics. This mapping connects the geometry and topology of a task space
directly to optimisation procedures and learning trajectories in latent
representation spaces, highlighting unexpected topological and geometric
differences and opportunities for deeper insight and improvement of
optimisation procedures, in the spirit of [NZL20, ZZ22]. We can also compare
biological optimisation processes and internal representations of allocentric
and egocentric navigation [Bur06, GHP+22], and how this interacts with the
position of other agents [DJ18, SB20].

From a more mathematical perspective, state complexes of gridworlds give rise
to an interesting class of geometric spaces. It would be worthwhile to
investigate their geometric and topological properties to more deeply
understand various aspects of multi-agent gridworlds. For example, for a
gridworld with $n$ agents in a sufficiently large room, we hypothesise that
the modified state complex should be a classifying space for the $n$–strand
braid group. This is clearly false when the room is packed full of agents (in
which case the state complex is a single point), so it may be fruitful to
determine if there is some ‘critical’ density at which a topological
transition occurs.

Using the _failure_ of Gromov’s Link Condition in an essential way appears to
be a relatively unexplored approach. Indeed, much of the mathematical
literature concerning cube complexes focusses on showing that the Link
Condition always holds. To our knowledge, the only other works which go
against this trend are [AG04], in which failure detects global disconnection
of a metamorphic system, and [BDT19], where failure detects non-trivial loops
on topological surfaces. It would be interesting to explore cube complexes
arising in other settings where failure captures critical information.

A limitation of our work is that we have so far only explored very simple AI
environments. Further work is needed to expand the framework and results to
more general, sophisticated, and real-world environments. For this reason,
although our work provides new geometric perspectives, data, and potential
algorithms for an important AI safety issue, we caution against hasty real-
world implementation of the main results. To avoid potential negative societal
impacts, it would still be important to perform rigorous checks and tests in
application domains, since our results do not directly extend to situations
beyond which the stated assumptions hold.

## Acknowledgments and Disclosure of Funding

This project began as a rotation project during the first author’s PhD
programme. We wish to acknowledge and thank Anastasiia Tsvietkova for
supporting a computational neuroscientist to do a research rotation in the
Topology and Geometry of Manifolds Unit at OIST, in which the second author
was a postdoctoral scholar. The first author thanks Nick Owad for 3D printing
a model state complex. The second author acknowledges the support of the
National Natural Science Foundation of China (NSFC 12101503). We thank
anonymous reviewers for their suggestions to improve exposition.

## References

  * [ABCG17] Federico Ardila, Hanner Bastidas, Cesar Ceballos, and John Guo, _The configuration space of a robotic arm in a tunnel_ , SIAM Journal on Discrete Mathematics 31 (2017), no. 4, 2675–2702.
  * [ABY14] Federico Ardila, Tia Baker, and Rika Yatchak, _Moving robots efficiently using the combinatorics of CAT(0) cubical complexes_ , SIAM Journal on Discrete Mathematics 28 (2014), no. 2, 986–1007.
  * [AG04] Aaron Abrams and Robert Ghrist, _State complexes for metamorphic robots_ , The International Journal of Robotics Research 23 (2004), no. 7-8, 811–826.
  * [AOS12] Federico Ardila, Megan Owen, and Seth Sullivant, _Geodesics in $\rm CAT(0)$ cubical complexes_, Adv. in Appl. Math. 48 (2012), no. 1, 142–163.
  * [AVBP21] Karen Archer, Nicola Catenacci Volpi, Franziska Bröker, and Daniel Polani, _A space of goals: the cognitive geometry of informationally bounded agents_ , arXiv:2111.03699, 2021.
  * [BDT19] Mark C. Bell, Valentina Disarlo, and Robert Tang, _Cubical geometry in the polygonalisation complex_ , Math. Proc. Cambridge Philos. Soc. 167 (2019), no. 1, 1–22.
  * [BH99] Martin R. Bridson and André Haefliger, _Metric spaces of non-positive curvature_ , Grundlehren der mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], vol. 319, Springer-Verlag, Berlin, 1999\.
  * [Bur06] Neil Burgess, _Spatial memory: how egocentric and allocentric combine_ , Trends in Cognitive Sciences 10 (2006), no. 12, 551–557.
  * [CN05] Indira Chatterji and Graham Niblo, _From wall spaces to CAT(0) cube complexes_ , International Journal of Algebra and Computation 15 (2005), no. 05n06, 875–885.
  * [DJ18] É. Duvelle and K.J. Jeffery, _Social spaces: Place cells represent the locations of others_ , Current Biology 28 (2018), no. 6, R271–R273.
  * [DSHLKT20] Felipe Leno Da Silva, Pablo Hernandez-Leal, Bilal Kartal, and Matthew E. Taylor, _Uncertainty-aware action advising for deep reinforcement learning agents_ , Proceedings of the AAAI Conference on Artificial Intelligence 34 (2020), no. 04, 5792–5799.
  * [EH10] Herbert Edelsbrunner and John L. Harer, _Computational Topology: An Introduction_ , American Mathematical Society, 01 2010.
  * [FLLP20] Tingxiang Fan, Pinxin Long, Wenxi Liu, and Jia Pan, _Distributed multi-robot collision avoidance via deep reinforcement learning for navigation in complex scenarios_ , The International Journal of Robotics Research 39 (2020), no. 7, 856–892.
  * [GHP+22] Richard J. Gardner, Erik Hermansen, Marius Pachitariu, Yoram Burak, Nils A. Baas, Benjamin A. Dunn, May-Britt Moser, and Edvard I. Moser, _Toroidal topology of population activity in grid cells_ , Nature 602 (2022), no. 7895, 123–128.
  * [Ghr09] Robert Ghrist, _Configuration spaces, braids, and robotics_ , pp. 263–304, World Scientific Publishing, 2009.
  * [GP07] R. Ghrist and V. Peterson, _The geometry and topology of reconfiguration_ , Advances in Applied Mathematics 38 (2007), no. 3, 302–323.
  * [Gro87] M. Gromov, _Hyperbolic groups_ , Essays in Group Theory (S. M. Gersten, ed.), Springer New York, New York, NY, 1987, pp. 75–263.
  * [HHA21] Victoria J. Hodge, Richard Hawkins, and Rob Alexander, _Deep reinforcement learning for drone navigation using sensor data_ , Neural Computing and Applications 33 (2021), no. 6, 2015–2033.
  * [HR17] Michael Hauser and Asok Ray, _Principles of Riemannian geometry in neural networks_ , Advances in Neural Information Processing Systems (I. Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett, eds.), vol. 30, Curran Associates, Inc., 2017.
  * [KAP20] Ivana Kajic, Eser Aygün, and Doina Precup, _Learning to cooperate: Emergent communication in multi-agent navigation_ , 42nd Annual Virtual Meeting of the Cognitive Science Society (CogSci 2020), 2020.
  * [KFGE19] Zac Kenton, Angelos Filos, Yarin Gal, and Owain Evans, _Generalizing from a few environments in safety-critical reinforcement learning_ , Safe Machine Learning workshop at ICLR (2019), 1–9.
  * [KIU21] Takeshi Kano, Mayuko Iwamoto, and Daishin Ueyama, _Decentralised control of multiple mobile agents for quick, smooth, and safe movement_ , Physica A: Statistical Mechanics and its Applications 572 (2021), 125898.
  * [KK89] Tomihisa Kamada and Satoru Kawai, _An algorithm for drawing general undirected graphs_ , Information Processing Letters 31 (1989), no. 1, 7–15.
  * [LAG+20] Na Lei, Dongsheng An, Yang Guo, Kehua Su, Shixia Liu, Zhongxuan Luo, Shing-Tung Yau, and Xianfeng Gu, _A geometric understanding of deep learning_ , Engineering 6 (2020), no. 3, 361–374.
  * [LMK+17] Jan Leike, Miljan Martic, Victoria Krakovna, Pedro A. Ortega, Tom Everitt, Andrew Lefrancq, Laurent Orseau, and Shane Legg, _AI safety gridworlds_ , arXiv:1711.09883, 2017.
  * [LR10] Tom Larkworthy and Subramanian Ramamoorthy, _An efficient algorithm for self-reconfiguration planning in a modular robot_ , 2010 IEEE International Conference on Robotics and Automation, 2010, pp. 5139–5146.
  * [LSS+21] Florian Laurent, Manuel Schneider, Christian Scheller, Jeremy Watson, Jiaoyang Li, Zhe Chen, Yi Zheng, Shao-Hung Chan, Konstantin Makhnev, Oleg Svidchenko, Vladimir Egorov, Dmitry Ivanov, Aleksei Shpilman, Evgenija Spirovska, Oliver Tanevski, Aleksandar Nikov, Ramon Grunder, David Galevski, Jakov Mitrovski, and Sharada Mohanty, _Flatland competition 2020: MAPF and MARL for efficient train coordination on a grid world_ , pp. 275–301, PMLR, 08 2021.
  * [NZL20] Gregory Naitzat, Andrey Zhitnikov, and Lek-Heng Lim, _Topology of deep neural networks_ , Journal of Machine Learning Research 21 (2020), no. 184, 1–40.
  * [QZC+21] Zengyi Qin, Kaiqing Zhang, Yuxiao Chen, Jingkai Chen, and Chuchu Fan, _Learning safe multi-agent control with decentralized neural barrier certificates_ , International Conference on Learning Representations, 2021.
  * [Sag14] Michah Sageev, _$\rm CAT(0)$ cube complexes and groups_, Geometric group theory, IAS/Park City Math. Ser., vol. 21, Amer. Math. Soc., Providence, RI, 2014, pp. 7–54.
  * [SB20] Christina J. Sutherland and David K. Bilkey, _Hippocampal coding of conspecific position_ , Brain Research 1745 (2020), 146920.
  * [Sch19] Petra Schwer, _Lecture notes on CAT(0) cube complexes_ , 2019.
  * [SMK11] Jeremy Stober, Risto Miikkulainen, and Benjamin Kuipers, _Learning geometry from sensorimotor experience_ , 2011 IEEE International Conference on Development and Learning (ICDL), vol. 2, 2011, pp. 1–6.
  * [SPG+21] Cory Stephenson, Suchismita Padhy, Abhinav Ganesh, Yue Hui, Hanlin Tang, and SueYeon Chung, _On the geometry of generalization and memorization in deep neural networks_ , International Conference on Learning Representations, 2021\.
  * [VBC+19] Oriol Vinyals, Igor Babuschkin, Wojciech M Czarnecki, Michaël Mathieu, Andrew Dudzik, Junyoung Chung, David H Choi, Richard Powell, Timo Ewalds, Petko Georgiev, Junhyuk Oh, Dan Horgan, Manuel Kroiss, Ivo Danihelka, Aja Huang, Laurent Sifre, Trevor Cai, John P Agapiou, Max Jaderberg, Alexander S Vezhnevets, Rémi Leblond, Tobias Pohlen, Valentin Dalibard, David Budden, Yury Sulsky, James Molloy, Tom L Paine, Caglar Gulcehre, Ziyu Wang, Tobias Pfaff, Yuhuai Wu, Roman Ring, Dani Yogatama, Dario Wünsch, Katrina McKinney, Oliver Smith, Tom Schaul, Timothy Lillicrap, Koray Kavukcuoglu, Demis Hassabis, Chris Apps, and David Silver, _Grandmaster level in StarCraft II using multi-agent reinforcement learning_ , Nature 575 (2019), no. 7782, 350–354.
  * [Wis12] Daniel T. Wise, _From riches to raags: 3-manifolds, right-angled Artin groups, and cubical geometry_ , CBMS Regional Conference Series in Mathematics, vol. 117, Published for the Conference Board of the Mathematical Sciences, Washington, DC; by the American Mathematical Society, Providence, RI, 2012.
  * [WKK20] Vikram Waradpande, Daniel Kudenko, and Megha Khosla, _Deep reinforcement learning with graph-based state representations_ , arXiv:2004.13965, 2020.
  * [ZZ22] Yang Zhao and Hao Zhang, _Quantitative performance assessment of CNN units via topological entropy calculation_ , International Conference on Learning Representations, 2022.

##  Appendix A Appendix

###  A.1 Mathematical background on cube complexes and Gromov’s Link Condition

Cube complexes and simplicial complexes are higher dimensional analogues of
graphs that appear prominently in topology, geometric group theory, and
combinatorics. Background on cube complexes can be found in [Sch19, Sag14,
Wis12]555Much of the literature in geometric group theory focusses primarily
on non-positively curved cube complexes, whereas in our study, the presense of
positive curvature plays a crucial role., while simplicial complexes are
detailed in standard algebraic topology texts [EH10]. Here, we will only
provide brief explanations in order to discuss Gromov’s Link Condition.

#### Cube complexes.

Informally, a cube complex is a space that can be constructed by gluing cubes
together in a fashion not too dissimilar to a child’s building blocks. An
$n$–cube is modelled on

$\\{(x_{1},\ldots,x_{n})\in\mathbb{R}^{n}~{}:0\leq x_{i}\leq 1\textrm{ for all
}i\\}.$

By restricting some co-ordinates to either 0 or 1, we can obtain lower
dimensional subcubes. In particular, an $n$–cube has $2^{n}$ vertices and is
bounded by $2n$ faces which are themselves $(n-1)$–cubes. A _cube complex_ $X$
is a union of cubes, where the intersection of every pair of distinct cubes is
either empty, or a common subcube.

#### Simplicial complexes.

Simplicial complexes are constructed in a similar manner to cube complexes,
except that we use higher dimensional analogues of triangles or tetrahedra
instead of cubes. An $n$–dimensional simplex (or $n$–simplex) is modelled on

$\\{(x_{1},\ldots,x_{n+1})\in\mathbb{R}^{n+1}~{}:x_{i}\geq 0\textrm{ for all
}i,~{}\sum_{i}x_{i}=1\\};$

this has $n+1$ vertices and is bounded by $n+1$ faces which are themselves
$(n-1)$–simplices. For $n=0,1,2,3$, an $n$–simplex is respectively a point,
line segment, triangle, and tetrahedron. A _simplicial complex_ $K$ is an
object that can be constructed by taking a graph and then inductively filling
in simplices of progressively higher dimension; this graph is called the _$1$
–skeleton_ of $K$. We require that every finite set of vertices in $K$ form
the vertices of (or _spans_) at most one simplex; thus simplices in $K$ are
uniquely determined by their vertices. (This rules out loops or multi-edges in
the $1$–skeleton.)

#### Links.

The local geometry about a vertex $v$ in a cube complex $X$ is captured by a
simplicial complex known as its _link_ $lk(v)$. Intuitively, this is the
intersection of a small sphere centred at $v$ within $X$, and can be regarded
as the space of possible directions emanating from $v$. Each edge in $X$
emanating from $v$ determines a vertex ($0$–simplex) in $lk(v)$. If two such
edges bound a ‘corner’ of a square in $X$ based at $v$, then there is an edge
($1$–simplex) connecting the associated vertices in $lk(v)$. More generally,
each ‘corner’ of an $n$–cube incident to $v$ gives rise to an $(n-1)$–simplex
in $lk(v)$; moreover, the boundary faces of the simplex naturally correspond
to the faces of the cube bounding the corner. Since the cube complexes we
consider have cubes completely determined by their vertices, each simplex in
$lk(v)$ is also completely determined by its vertices. Figure 8 illustrates
four separate examples of links of vertices in cube complexes.

Figure 8: Four separate examples of links of vertices in cube complexes. In
the bottom-right example, where there is positive curvature, $lk(v)$ is a
‘hollow’ triangle and is thus not a flag simplicial complex. For the other
examples, $lk(v)$ is a flag complex and therefore, by Gromov’s Link Condition,
there is only negative or zero curvature. In the bottom-left example, the cube
complex is a solid cube joined to a filled-in square at a common vertex $v$.

#### Gromov’s Link Condition.

Local curvature in a cube complex can be detected by examining the
combinatorial structure of the links of its vertices. Specifically, Gromov’s
Link Condition gives a method for proving that a cube complex is _non-
positively curved_ (NPC)666In the sense that geodesic triangles are no fatter
than Euclidean triangles [BH99]., where there is an absence of positive
curvature. In the bottom-right example in Figure 8, where there is positive
curvature, we observe a ‘hollow’ triangle in its link. In the other examples
of Figure 8, where there is only negative or zero curvature, there are no such
hollow triangles (or hollow simplices).

This absence of ‘hollow’ or ‘empty’ simplices is formalised by the _flag_
property: a simplicial complex is _flag_ if whenever a set of $n+1$ vertices
spans a complete subgraph in the $1$–skeleton, they must span an $n$–simplex.
In particular, a flag simplicial complex is determined completely by its
$1$–skeleton. If $v$ is a vertex in a cube complex $X$, then the flag
condition on $lk(v)$ can be re-interpreted as a ‘no empty corner’ condition
for the cube complex: whenever we see (what appears to be) the corner of an
$n$–cube, then the whole $n$–cube actually exists.

######  Theorem (Gromov’s Link Condition [Gro87]).

A finite-dimensional cube complex $X$ is non-positively curved if and only if
the link of each vertex in $X$ is a flag simplicial complex. ∎

Thus, the local geometry of a cube complex is determined by the combinatorics
of its links.

###  A.2 Proof of Theorem 5.2

Before giving our proof, we first classify low-dimensional simplices in
$lk(v)$ for a vertex $v$ in our modified state complex $\mathcal{S}^{\prime}$.
A $0$–simplex in $lk(v)$ corresponds to an admissible move at $v$. However, a
$1$–simplex either represents a pair of commuting moves, or two moves in a
common dance. A $2$–simplex either represents three agents moving pairwise
independently, or a dancing agent commuting with a moving agent. Finally, a
$3$–simplex represents either four agents moving pairwise independently, one
dancing agent and two moving agents that pairwise commute, or a pair of
commuting dancers.

######  Theorem (Gromov’s Link Condition in the modified state complex).

Let $v$ be a vertex in the modified state complex $\mathcal{S}^{\prime}$ of an
agent-only gridworld. Then

  * •

$lk(v)$ satisfies Gromov’s Link Condition if and only if it has no empty
$2$–simplices nor $3$–simplices, and

  * •

if $lk(v)$ fails Gromov’s Link Condition then there exist a pair of agents
whose positions differ by either a knight move or a $2$–step bishop move (as
in Figure 7).

###### Proof.

If $lk(v)$ satisfies Gromov’s Link Condition, then it has no empty simplices
of any dimension, giving the forward implication. For the converse, assume
that $lk(v)$ has no empty $2$–simplices nor $3$–simplices. Suppose there exist
$n+1$ vertices spanning a complete subgraph of $lk(v)$, where $n\geq 4$. We
want to show that these vertices span an $n$–simplex. By induction, we may
assume that every subset of $n$ vertices from this set spans an
$(n-1)$–simplex. Since $n\geq 4$, every quartuple of vertices in this subgraph
spans a $3$–simplex. Therefore, appealing to our classification of low-
dimensional simplices, every pair of moves or dances involved has disjoint
supports. Thus, the desired $n$–simplex exists. Consequently, potential
failures can only be caused by empty $2$–simplices or $3$–simplices.

Next, we want to determine when three pairwise adjacent vertices in $lk(v)$
span a $2$–simplex. These vertices represent three admissible moves at $v$.
Since they are pairwise adjacent, they either correspond to three agents each
doing a Move, or to one agent dancing with another one moving. In the former
case, the supports are pairwise disjoint and so these moves form a commuting
set of generators. Therefore, the desired $2$–simplex exists (indeed, in the
absence of dancers, the situation is the same as the original Abrams, Ghrist &
Peterson setup). For the latter case, suppose that the first agent is dancing
while the second moves. Since the $0$–simplices are pairwise adjacent, each of
the two admissible moves within the dance has disjoint support with the second
agent’s move. Thus, the only way the support of the dance fails to be disjoint
from that of the second agent’s move is if the second agent can move into the
diagonally opposite corner of the dance. Therefore, the only way an empty
$2$–simplex can arise is if the agents’ positions differ by a ‘knight move’
(see Figure 7 for illustration).

It remains to determine when four pairwise adjacent vertices in $lk(v)$ span a
$3$–simplex. We may assume that each triple of vertices in this set spans a
$2$–simplex, for otherwise we can reduce to the previous case. Let us analyse
each case by the number of involved agents. If there are four involved agents,
then each $0$–simplex corresponds to exactly one agent moving. Since no dances
are involved, it immediately follows that the desired $3$–simplex exists. If
there are three involved agents, then one is dancing while the other two move.
Since each triple of $0$–simplices spans a $2$–simplex, we deduce that each
move has disjoint support with the dance. Therefore, the dance and the two
moves form a commuting set, and so the $3$–simplex exists. Finally, if there
are two agents then they must both be dancers. By the assumption on
$2$–simplices, each admissible move within the dance of one agent has disjoint
support from the dance of the other agent. Thus, the only way for the two
dances to have overlapping supports is if their respective diagonally opposite
corners land on the same cell. Therefore, the only way an empty $3$–simplex
can arise (assuming no empty $2$–simplices) is if two agents’ positions differ
by a ‘$2$–step bishop move’ (see Figure 7 for illustration). ∎

###  A.3 Python tool for constructing gridworlds and their state complexes

We developed a Python-based tool for constructing gridworlds with objects and
agents. It includes a GUI application for the easy specification of gridworlds
and a script which will produce plots and data of the resulting state complex.
We ran all experiments on a Lenovo IdeaPad 510-15ISK laptop. The open-source
code is available here: https://github.com/tfburns/State-Complexes-of-
Gridworlds.

For the sake of generality and future-proofing of our software, we chose to
construct the links in our implementation of checking Gromov’s Link Condition
in gridworlds, which is not necessary in-practice. Instead, in practical
situations, one can directly check for supports of knight or two-step bishop
moves between agents, which per Theorem 5.2 provides a computational short-cut
for detecting failures in agent-only gridworlds. Another area of computational
efficiency available in many rooms are in the symmetries of the room itself.
For example, an evenly-sized square room can be cut into eighths (like a
square pizza), where each eighth is geometrically identical to every other.

Users of the code will notice a small but important implementation detail in
the code which we chose to omit the particulars of in this paper: in the code,
we need to include labelled walls along the borders of our gridworlds. This is
because we construct our gridworlds computationally as coordinate-free,
abstract graphs. For Move, the lack of a coordinate system is not an issue –
if an agent label sees a neighbouring vertex with an empty floor label, the
support exists and the generator can be used. However, Push/Pull only allows
objects to be pushed or pulled by the agent in a straight line within the
gridworld. We ensure this straightness in the abstract graph by identifying a
larger subgraph around the object and agent than is illustrated in Figure 2.
Essentially, we incorporate three wildcard cells (cells of any labelling)
adjacent to three labelled cells (‘agent’, ‘object’, and ‘floor’), such that
together they form a $2\times 3$ grid.

###  A.4 Experiments in small rooms

Table 1: Data of Gromov’s Link Condition failure and commuting $4$–cycles in the state complexes of a $3\times 3$ room with varying numbers of agents and no objects. The percentage of NPC states (shown in brackets in the second column) is rounded to the nearest integer. The mean number of Gromov’s Link Condition failures (shown in the penultimate column) is the mean number of failures over the total number of states, and is rounded to two decimal places. |  |  |  |  | Gromov’s Link
---
Condition Failures
Agents | States (% NPC) | Dances | Commuting moves | Total | Mean | Max
0 | 1 (100) | 0 | 0 | 0 | 0 | 0
1 | 9 (100) | 4 | 0 | 0 | 0 | 0
2 | 36 (78) | 20 | 44 | 32 | 0.89 | 4
3 | 84 (62) | 40 | 220 | 184 | 2.19 | 14
4 | 126 (65) | 40 | 440 | 288 | 2.29 | 11
5 | 126 (68) | 20 | 440 | 152 | 1.21 | 6
6 | 84 (86) | 4 | 220 | 16 | 0.19 | 2
7 | 36 (100) | 0 | 44 | 0 | 0 | 0
8 | 9 (100) | 0 | 0 | 0 | 0 | 0
9 | 1 (100) | 0 | 0 | 0 | 0 | 0

Summary statistics for the $3\times 3$ room with varying numbers of agents is
shown in Table 1, showing the distribution in failures of Gromov’s Link
Condition across these conditions. The $2\times 3$ room with two agents shows
multiple instances of local positive curvature in the associated (modified)
state complex. Figure 9 shows one such state where Gromov’s Link Condition
fails due to the agents being separated by a knight’s move (see Theorem 5.2).
At this state, there are actually two empty $2$–simplices in its link – this
is because the pattern appearing in the $5$–cell subgrid with two agents (as
in Figure 7) arises in two different ways within the given state on the
gridworld. The only other state where Gromov’s Link Condition fails is a
mirror image of the one shown.

Further small gridworlds and their respective state complexes are shown in
Figures 10, 11, and 12.

Figure 9: A $2\times 3$ room with two agents (top right) and its state complex
(top left), where dances are shaded blue and commuting moves are shaded red.
The darker-shaded vertex represents the state of the gridworld shown. Also
shown is the state complex with only commuting moves (bottom left) and only
dances (bottom right). Figure 10: A $3\times 3$ room with two agents (right)
and its state complex (left), where dances are shaded blue and commuting moves
are shaded red. The darker-shaded vertex represents the state of the gridworld
shown. Naturally-occurring copies of this state complex can be found as sub-
complexes in the state complex shown in Figure 12. Figure 11: A $4\times 1$
corridor with two agents (right) and its state complex (left). There are no
dances and only one commuting move, shaded red. The darker-shaded vertex
represents the state of the gridworld shown. Naturally-occurring copies of
this state complex can be found as sub-complexes in the state complex shown in
Figure 12. Figure 12: A $4\times 4$ room with two agents (right) and its state
complex (left), where dances are shaded blue and commuting moves are shaded
red. The darker-shaded vertex represents the state of the gridworld shown.
Embedded within this state complex are naturally-occurring copies of the state
complex of the $4\times 1$ corridor with two agents, shown in Figure 11. There
are also naturally-occurring copies of state complex of the $3\times 3$ room
with two agents, shown in Figure 10.