Detecting danger in gridworlds using Gromov’s Link Condition
Authors: Thomas F Burns
Robert Tang
Venue: Accepted by TMLR ()

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, a higher-dimensional analogue of state graphs, 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 for agent-only cases 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 environments.

Published in Transactions on Machine Learning Research (11/2023)
Detecting danger in gridworlds using Gromov's Link Condition
Thomas F Burns
thomas. thomas. Doist.pp
Neural Coding and Brain Computing Unit OIST Graduate University 1919-1 Tancha, Onna-son, Kunigami-gun Okinawa, Japan 904-0495
Robert Tang
robert. Cenortttan@@riiiee edu.com
Department of Pure Mathematics Xi'an -ivverol University 111 Ren'ai Road, Suahou Industriol Park Suzhou, Jiangsu Province, China 215123
Reviewed on OpenReview: https: https:///penrewieeu openreview. net/ forum? id= t4p612Df
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 rescarch. We initiate a study of gridworlds using the mathematical framework reconfigurable systems and state complezes due to Abrams, Ghrist & Peterson. State complexes, higher-dimensional analogue of state graphs, represent all possible configurations of system a single geometric space, thus making them conducive to study using geometric, topological, combinatorial methods. The main contribution of this work is 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 Gromou's Link Condition). Serendipitously, we discover these failures for agent-only cases occur exactly where undesirable or dangerous states appear in the gridworld. Our results therefore provide 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 lcarning systems. More broadly, our work introduces tools from geometric group theory and combinatorics to the AT community and demonstrates a proof-of-concep. for this geometric viewpoint of the task domain through the example of simple environments.
1 Introduction
The notion of a state (or configuration/plan all the possible states of a given system as a single geometric (or topological) object. This perspective provides bridge which allows for tools from gcometry and topology to be applicd to the system of concern. Morcover, certain features of given system are reflected by some geometrie aspects of the associated state space (such 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.
space commonly used in mathematics and physics to represent
In discrete settings, state spaces have most commonly be represented in the artificial intelligence (AI) literature using graphs. In a state graph, each vertex represents a state, and states are connected via edges if a transition between them dynamically possible. Such graphs are typically incorporated within Markov decision processes (MDPs), including in multi-agent navigation and cooperation tasks (Rizk et al., 2019). MDPs inchude additional information about probabilities of and expected rewards associated with particular

---

Published in Transactions on Machine Learning Research (11/2023)
state transitions. Within this literature, there has been some work of a more geometric (Arslan et al. 2016) topological (Waradpande et al. 2020) flavour. With few exceptions, however, where such works incorporate geometric realisations, concepts, or techniques, they typically do so in an empirical way and do not utilise higher dimensional objects such as simplicial or cube complexes.
In the current work, we focus on a higher dimensional analogue of state graphs which take the form of cube complexes. Abrams, Ghrist & Peterson's state complezes (Abrams & Ghrist 2004] Ghrist & Peterson 2007) provide general framework for representing discrete reconfigurable systems non-positively curved (NPC) cube complexes, giving access to wealth of mathematical and computational benefits via efficient optimisation algorithms guided by geometric insight (Ardila et al., 2012). These have been used to develop efficient algorithms for robotic motion planning (Ardila et al. 2014
2017)
and self-reconfiguration of modular possess rich hyperplane structures
robots [Larkworthy & Ramamoorthy 2010 NPC cube complexes also
which geometrically capture binary classification (Chatterji Niblo 2005 Wise 2012
Sageev 2014). However,
their broader utility to fields like 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 gridworkss. We introduce natural modification to the state complex appropriate to the setting of multi-agent gridworlds (to capture the braiding or relative movements of agents); however, in the agent-only case 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 for these agent-only cases, and relate this to features of the gridworkds (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 via our modification. Current approaches to collision-detection and navigation during multi-agent navigation often rely on modelling and predicting collisions based on large training datasets (Kenton et al. 2019 Fan et al.,
2020: Qin et al.) 2021) or by explicitly modelling physical movements (Kano et al., 2021). However, our approach is purely geometric, requires no training, and can accommodate many conccivable types of actions and inter-actions, not. just simple movements.
In the context of single-agent motor learning and navigation, there has been some work (Peng & van de Panne 2017: Reda et al.] 2020 Schneider et al. 2023) on how the choices of what and how information is represented in learning system can effect lask performance. Implicitly, these works can be viewed as empirical investigations on how changes to the geometry or topology of state spaces relate to the efficacy of the applied learning algorithms. However, these studies do not seek to incorporate higher-level geometric or topological information of the originating domain or task in a substantial way, or investigate this formally, before applying or investigating the performance of the learning algorithms and even fewer do so for multi-agent systems (Rizk et al. 2019). One possible reason for this is a lack of known suitable tools. Our experimental and thcoretical results show there is wealth of geometric information available in (even very simple) task domains, which is accessible using tools from geometric group theory and combinatories. Our work therefore joins a growing body of research aimed towards understanding AI systems from more geometric perspective Hauser & Ray 2017 Stober et al. 2011).
Lei et al. 2020
Stephenson et al. 2021 Archer et al. 2021
2 State complex of a gridworld
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 sctting, 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 utilised setting in AI research, particularly reinforcement learning, since they are simple yet scalable in size and sophistication (Da Silva et al. 2020 Waradpande et al. 2020). They also offer clear analogies to many real-world applications or questions, such as robot navigation (Hodge el al., 2021 b, emergent behaviour Kajic le al. 2020), and operations research (Laurent et al. 2021). For these reasons, gridworlds have also been developed for formally specifying problems in AI safety (Leike et al. 2017).
2

---

Published in Transactions on Machine Learning Research (11/2023)
A state of gridworld can be encoded by assigning each cell label. In the example shown in Figure | these labels are shown for an agent, 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 reconffguruble systems as introduced by Abrams, Ghrist & Peterson 4Abrams & Ghrist, 2004 Ghrist & Peterson 2007
More formally, consider graph G and A of labels. A state is function V(G) > A, i.c. an assignment of label to cach vertex of G. A possible relabelling is encoded using a generalor o; this comprises the following data:
subgraph SUP(Ø) S G called the support: a subgraph TR( S (O) called the trace; and an unordered pair of local states
Figure 1: A 3 3 gridworld with one agent (a koala) and one object (a beach ball).
u ufoc V(SUP())) + A
that agree V(SUP(0)) V(TR(O)) but differ on V(TR(Ø)).
A generator o is admissible at a state s if s|suP(0) = uge (or ufr",, in other words, if the assignment of labels to ((S)P(#) given by s completely matches the labelling from (exactly) one of the two local states. If this holds, we may apply & to the state s to obtain new state Φis) given by
Φbs](v) = [ (v), v VEV(R)()))
{ s(v), otherwise.
This has the effect of relabelling the vertices in (and only in) TR( to match the other local state of Φ. Since the local states are unordered, if is admissible then it is also admissible at. Φ[s); moreover, a[p[+]]
Definition 2.1 (Reconfigurable system (Abrams & Ghrist 2004 Ghrist & Peterson 2007 A reconfigurable system graph G with set of labels A consists of set of generators together with set of states closed under the action of admissible generators.
Configurations and their reconfigurations be used to construct state graph (or transition graph), which represents all possible states and transitions between these states in reconfigurable system. More formally:
Definition 2.2 (State graph). The state graph ((1) associated reconfigurable system has its vertices the set of all states, with edges connecting pairs of states differing by single generator H
Let now return our attention to gridworlds. We define 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
A = l'agent', 'object', '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.
For cell complex X, it standard notation use (k) for its k-skeleton (the subcomplex formed by the union of all cells of dimension at most k).
3

---

Published in Transactions on Machine Learning Research (11/2023)
Push/Pull
Move
An example 1 5 gridworld with agent and one object with two generators Push/Pul and Move and the resulting state graph. In the state graph, edge colours indicate the generator type which relabels the gridworld.
Figure 2:
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 lo move. For both types of generators, the trace coincides with the support. For the Push/Put generator, the support is a row or column of three contiguous cells, whereas for the Move generator, the support pair of neighbouring cells. simple example of state graph, together with the local states for the two generator types, is shown in Figure]
In typical reconfigurable system, there may be many admissible generators given state If the trace of admissible generator Φ1 is disjoint from the support of another admissible generator Φ2. then Φ2 remains admissible at [1[)]. This is because the relabelling by &1 does not interfere with the labels on SU2())). More generally, a set of admissible generators (ø1,.... (a) at a state commutes if SU P().) n (T)(())) = 0 for all i.j. j. When this holds, these generators can be applied independently 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 large room with agents spread sufficiently far apart to allow for independent simultaneous movement.
A Abrams, Ghrist & Peterson represent this mutual commutativity by adding higher dimensional cubes to the state graph to form a cube complex called the state complez. We give an informal definition here, and refer to their papers for the precise formulation [Abrams & Ghrist 2004 Ghrist & Peterson 2007).
Cube complexes are higher dimensional analogues of graphs that appear prominently in topology, geometric group theory, and combinatorics. Background on cube complexes can be found Schwer (2019); Sageev
(2014) Wise 2
Informally, cube complex is space that can be constructed by gluing cubes together in fashion not too dissimilar to a child's building blocks. An n nubube is modelled on
( En) E R" 0 x; S for all i}.
By restricting co-ordinates to either 0 or 1, cube has 2n vertices and is bounded by 2n faces which are themselves (n - 1) cubes. A cube complez X is union of cubes, where the intersection of every pair of distinct cubes is either empty, or a common subcube.
obtain lower dimensional subcubes. In particular,
In the state complex, if {ør...., Φn} is a set commuting admissible generators at a state s then there are 2n states that can be oblained by applying any subset of these generators s. These 2n stales form
Much of the literature geometric group theory focusses primarily on non-positively curved cube complexes, whereas in our study, the presence of positive curvature plays crucial role.
4

---

Published in Transactions on Machine Learning Research (11/2023)
an the vertices of n-cube in the state complex. Each n-cube is bounded by 2n faces, where each face is (n cu-bb by disallowing a generator di, we obtain a pair of faces corresponding to those states (in the given n cubee) that agree with one of the two respective local states of Φ, on SU.().)
Definition 2.3 (State complex). The state compler S of a reconfigurable system is the cube complex constructed from the state graph ( by inductively adding cubes as follows: whenever there is a set of 2" 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 generalor involves exactly one agent. This means commuting generators can only occur if there are multiple agents. A simple example of state complex for two agents in 2 room is shown in Figure 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 (finite) gridworld, we first initialise an empty graph G and an empty 'to-do' list L. As input, we take a chosen state of the gridworld to form the first vertex of G and also the first entry on L. The state complex computed according breadth-first search by repeatedly applying the following:
Figure 3: State complex of a 2 x 2 gridworld with Iwo agents. Shading indicates squares allached to the surrounding 4 cycles.
Let e be the first entry on L. List all admissible generators at v. For each such generator d:
If ofu] already appears as vertex of g, add an edge between v and Φ/v] (if it does not already exist).
If <lu] does not appear in G, add it as new vertex to & and add an edge connecting it to v. Append Φ(v] to the end of L.
Remove from L.
The process terminates when L is empty. The output is the graph G. When L empty, we have fully explored all possible states that can be reached from the initial state. may be possible that the true state graph is disconnccted, in which case the above algorithm will only return connected component G. For our purposes, we shall limit our study to systems with connected state graphe 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 (Kamada & Kawai 1989) which attempts draw edges 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
3'heree is theoretical resson for limiting our study to connected state complexes. In fact, main theorem would still hold without the connectedness assupttion it is purely local statement. If one begins with an initial state, then its connected component comprises preciscly all states which can be reached by applying and computational standpoint, one only deals with connected component of the full state complex when exploring from specific instance of gridworld. Another issue that without the connectedness assumption, the problem of finding shortest. path between two given states could he impossible.
sequence of generators. Thus, from practical
5

---

Published in Transactions on Machine Learning Research (11/2023)
not also shade higher-dimensions cubes, although such cubes noticeable and can be easily computed and visualised if desired.
Constructing and analysing state complexes of gridworlds is in and of itself an interesting and useful way exploring their intrinsic geometry. For example, Figure shows the state complex of 3 gridworld with agent and one object. The state complex reveals two scales of geometry: larger 'blobs' of states organised in a 3 x 3 grid, representing the location of the object; and, within each blob, copies the room's remaining empty space, which the agent may walk around and approach the object to Push/Pull. Each 12 cycle 'petal' rep- resents 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.
Figure 4: State complex (left) of a 3 x 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 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.
The examples discussed thus far all have planar state graphs. Planarity does not hold in general indeed, the cube graph for 2 4 is non- planar, and a state graph can contain n cubbu if the gridworld has n agents and sufficient space to move around. It is tempting to think that the stale complex of a gridworld with more agents should therefore look quite different one with fewer agents. However, Figure 5 shows this may not always be the case: there is symmetry induced by swapping all 'agent' labels with 'floor' labels.
Figure 5: State complex (centre) of a 3 x 3 gridworld with three agents (Ieft) and six agents (right). They share the same state complex due to the 'agent" + 'floor' label inversion symmetry.
We observe an interesting pattern Figure 5 where 'clusters' of vertices the state complex are arranged in gridlike fashion on the plane. This gridlike arrangement is also exhibited in Figures I0 and 12 in Appendix A.1 as well in other experiments involving agent-only gridworlds in larger rooms. It is worth emphasising that these visualisations were generated purely by feeding the state graph into the graph-drawing algorithm, with no human input involved. This suggests that the gridlike clustering could be revealing an intrinsic feature of the state complex, rather than simply being an artefact of a particular visualisation.
Indeod, by inspecting several examples, appears that the visualisation approximates a natural projection map from the state complex of an agent-only gridworld the integer lattice E² Let identify the cell in row and column in gridworld with the integer co-ordinate (i.j) 72, Then for each state E 8

---

Published in Transactions on Machine Learning Research (11/2023)
define f(s) E Z² to be the sum of all co-ordinates corresponding to the cells occupied by agent. We view I as map which assigns a state to 'cluster' in Z?. Applying single Move generator to results in a state such that f(=") differs from f(s) by either (#1,0) 0) or (0, In particular, any pair of states mapping to a common 'cluster' in Z² must be non-adjacent in the state graph. Thus, f extends to a graph map from the state graph S(1) the standard inleger grid (regarded as a graph on the plane).
It would be interesting to if there could be other graph maps from the state graph the integer grid which are not related to the map by obvious symmetry. If the answer is no, then this could help explain why the graph-drawing algorithm appears to produce consistently similar projections for varying numbers of agents and sizes of rooms.
4 Dancing with myself
The state complex of gridworld with n agents can be thought of as 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 a small square-shaped dance by itself, as shown in Figure G
Figure 6: State complex of a 2 2 gridworld with one agent under the original definition of Abrams, Ghrist & Peterson (Abrams & Ghrist 2004 Ghrist & Peterson 2007) (left) and with our modification (right). The blue shading is filled in square indicating dance.
The presence of these holes would suggest something meaningful about the underlying gridworld's intrinsic topology, e.g., something obstructing the agent's movement 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 graph. We therefore deviate from the original definition of state complexes by Abrams, Ghrist & Peterson (Abrams & Ghrist 2004 Ghrist & Peterson, 2007 and choose to fill in these 'dance' cyclls with squares
Formally, we define a dance 8 to comprisc the following data:
the support SU)( given by a 2 subgrid in the gridworld,
four local states defined on SU SU)) 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
4Ghrist and Peterson themselves there could he better ways complete state graph higher-dimensional object with better properties (Question 6.4 in Ghrist. Peterson 2007

---

Published in Transactions on Machine Learning Research (11/2023)
We say that 8 is admissible at state if P(S))P8) agrees with one of the four local states of ó. 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 PU)(
A dance is itself not a generator in the sense of Abrams, Ghrist & Peterson; rather, it is a set of 4 states related by Move generators. Observe that a dance exists precisely when an agent is able to execute a 'diagonal move' via two different move sequences: a horizontal move followed by vertical move; or a vertical followed by horizontal one. We can thus view dance as capturing 'spatially commuting" relationship between these two move sequences. Note that these Moves are not commuting in the strict Abrams, Ghrist & Peterson sense (which could be viewed as a 'temporally commuting"' relationship between generators), as the pairs of generators involved do not even coincide. Our modifications to the state complex, detailed below, allow us to treat both notions of commutativity simultancously via cubes. This demonstrates a conceptual advantage of working with a complex rather than a graph: with a graph, we can only capture relations between pairs of states; by allowing higher-dinensional cubes, we can also caplure relations between sets of generators or states.
The notion of commutativity can be extended to incorporate dancing as follows. Suppose that we have set (øi,..., Φ1, 61,...,6m,) } of l admissible generators and m admissible dances at a state 8. We say that this set, commutes if the supports of its elements are pairwise disjoint. When this holds, there are 2/+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 6i, and four for each 6y. 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 compler S' of gridworld is the cube complex obtained by filling in the state graph ((1) with higher dimensional cubes whenever there is a set of commuting moves or dances. Specifically, whenever a set of 2/+2m states are related by commuting set of l generators and dances, we add an n cube having the given set of states its vertices, where = I+ 2m. Each of the 2n faces of such an n-cube is identified with an (n 1)-cube obtained by either disallowing a generator di and choosing one of its two local states, or replacing a dance 5, with one of its four constituent. Moves.
Our modification removes uninteresting topology. This can be observed by examining 4 cycles in S'. On the one hand, some 4-cycles are trivial (they can be 'filled in'): Sancing-with-mmssee 4-cycles, and commuting moves (two agents moving back and forth) 4 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 x room, as can be seen the centre of Figure 3 (here, no dancing is possible so the modified state complex is the same as the original). This 4-cyele represents the two agents moving half 'revolution' relative to one another indeed, performing this twice would give full revolution. (There are three other non-trivial 4 cycles, topologically equivalent to this central one, that also achieve the revouuivv)
In a more topological sensd 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- hothhooootopic 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 dance when other agents are crowding the danco-ftoor.
Remark 4.2. Another approach could be to add edges to the state complex to represent diagonal moves instead of filling in 'dance' squares. However, doing so would further complicate the topology of the state complex. Heuristically, adding more edges would increase the rank of the fundamental group, introducing even more unnatural topology. In the example of complete graph on 4 vertices the state graph (or complex), whose fundamental group is a free group of rank 3. However, the original state complex is homolopy equivalent to a circle, with the group of integers (the free group of rank 1) as its fundamental group. Thus, we choose the approach of attaching higher dimensional cells in order to remove undesirable topology and reduce the rank. In the 2 x 2 example, the modified state complex is contractible and hence has trivial fundamental group.
2 gridworld with one agent, we would obtain a
By considering the fundamental group.
8

---

Published in Transactions on Machine Learning Research (11/2023)
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 Bridson & Haefliger (1999] and Sageev
(0044)
Before discussing Gromov's Link Condition, we provide brief explanations of simplicial complexes and links. Readers familiar with these objects and concepts may safely skip. Further background on simplicial complexes
are detailed in standard algebraic topology lexts (Hatcher 2002:
Edelsbrunner & Harer 2010
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
(x11..., Int1) E R*+1 : 2 for all i, Σ2; = 1]:
this has n +1 vertices and is bounded by n n faces which are themselves (n- simplices. For n = 0,1,2,3, an nimimplex is respectively a point, line segment, triangle, and tetrahedron. A simplicial compler 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 form the vertices of (or spans) at most one simplex; thus simplices in K are uniquely determined by their vertices. (This rules out loops multi-edges in the 1 1-skeleton.)
Links. The local geometry about a vertex u in a cube complex X is captured by a simplicial complex known as its link lk(w)) Intuitively, this is the intersoction of small sphere centrod at e within X, and can be regarded as the space of possible directions emanating from v. Each edge in X emanating from o determines vertex (0 (0-simplex) in (k(v). If two such edges bound a 'corner' of square in X based at v, then there is an edge (I simplex) connecting the associated vertices in Ik(v). More generally, each 'corner' of an n-cube incident to u gives rise to an (n simsixpe in [k(v); morcover, 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 (k(v) is also completely determined by its vertices. Figure]) illustrates four separate examples of links of verticos in cube complexes.
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 NPC where there is an absence of positive curvature. In the bottom-right example Figure 7 where there is positive curvature, we observe 'hollow' triangle in its link. In the other examples of Figure where there is only negative zero curvalure, there are such hollow triangles (or hollow simplices).
This absence of 'hollow' or 'empty' simplices is formalised by the flag property: simplicial complex is flag if whenever set of n +1 vertices spans a complete subgraph in the 1 I-skeleton, they must span an simplex.. In particular, a flag simplicial complex is determined completely by its 1 skeleton. If u is a vertex in a cube complex X, then the flag condition on Il((v) can be ro-interproted 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- n-cube actually exists.
Theorem (Gromov's Link Condition (Gromov 1987)). A finite-dimensional cube complex X is non- non-posittvell curved if and only if the link of each verter in X a flag simplicial compler.
Thus, the local geometry of a cube complex is determined by the combinatorics of its links.
6n the sense that geodesic triangles are no fatter than Fuclidean triangles Bridson & Haefliger
1999
9

---

Published in Transactions on Machine Learning Research (11/2023)
Ik(v)
Ik(v)
Ik(v)
Ik(v)
Figure 7: Four separate examples of links of vertices in cube complexes. In the bottom-right example, where there is positive curvature, Ik(u) is 'hollow' triangle and is thus not a flag simplicial complex. For the other examples, Ik(v) is a flag complex and therefore, by Gromov's 's Link Condition, there 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.
Under the Abrams, Ghrist & Peterson setup, if u is a state in S then the vertices of its link (k(v) represent the possible admissible generators at u. Since cubes in S are associated with commuting sets of gencrators, each simplex in Ik(v) represents a set of commuting generators. Gromov's Link Condition for Ik(u)) can be reinterpreted follows: whenever a set of admissible generators 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 Ghrist & Peterson (2007).
Remark 5.1. The terms "non-positively curved (NPC)" and "locally CAT(O)" are synonymous in the context of geodesic metric spaces. For a cube complex, the CAT(() property is equivalent to it being both NPC (via Gromov's 's Link Condition) and simply connected (i.e. it has trivial fundamental group). The state complexes of Abrams, Ghrist Peterson are always NPC, but they are not necessarily simply connected. For example, the x 2 gridworld with 2 agents is homotopy equivalent a circle (see Figure 3 hence not simply connected and therefore not CAT( In the work of Ardila arms, it is the simple connectedness (a global property) which is harder to establish NPC geometry holds immediately thanks to Abrams & Ghrist (2004); Ghrist & Peterson (2007). Thus, in the interest. of technical correctness, we consider it preferable to use the terms "NPC" or "locally CAT(O)" instead of "CAT(0)" to describe the geometry of a cube complex when the status of simple connectedness is unknown.
al. (2012) on state complexes for robotic
For our modified states complexes, the situation not as straightforward. The key issue that our cubes do not only arise from commuting generators we must take dances into account. Indeed, when attempting prove that Gromov's Link Condition holds, we discovered some very simple gridworlds where it actually fails; Figure g and Appendix A..] Despite this apparent drawback, nevertheless show that Figure g accounts for all the possible failures of Gromov's Link Condition in the setting of agent-only gridworlds"
While writing this paper, the first author involved in two scooter accidents collisions involving only agents (luckily without serious injury). So, while this class gridworlds strictly smaller than those also involving objects other labels, is by no means an unimportant one. only the scooters had Gromov's Link Condition checkers!
10

---

Published in Transactions on Machine Learning Research (11/2023)
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 AT systems operating such environments particularly challenging, although remarkable success has been achieved games like StarCraft. |Vinyals al. 2019
To further explicate the connection between the structure of links and collision avoidance in the gridworlds setting, consider the follow- ing setup. Each time step involves a planning phase and an execution phase. In the plan- ning phase, each agent may propose an action (e-g,, Move). Our modified setup also permits agent to simultaneously propose both horizontal and vertical Move from common Dance to indicate an intended 'diagonal step'. The set of proposed actions P can be regarded as a set of vertices in (k(v) of the current state v. If spans a simplex in (k(v), then all ac- tions can be safely performed simultaneously in the exccution phase. If not, then choose maximal simplex in the subcomplex of (k(v) spanned by P, yielding a maximal subset of simultancously valid actions to be executed. More formally, we could regard such a 'colli- sion avoidance policy' as function from the power set of (Ik(o)) (k(v). Thus, we can reframe the problem of collision avoidance in terms of the combinatorial structure of links which, in turn, is captured by the local geom- etry of the state complex.
Φ
42
Φ
Φ
6
5
O 4
$
Figure 8: The two siluations 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 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 now characterise the situations leading to failures of Gromov's Link Condition in the agent-only case. Before doing so, let us first classify low-dimensional simplices in Uk(c) for vertex in our modified state complex S'. A O-simplex in Ik(r) corresponds to an admissible move at v. However, a 1-simplex either represents a pair of commuting moves, or two moves in common dance. A 2 simplex either represents three agents moving pairwise independently, or a dancing agent commuting with a moving agent. Finally, a 3 -immllex represents either four agents moving pairwise independently, one dancing agent and two moving agents that pairwise commute, or a pair of commuting dancers.
Thcorem 5.2 (Gromov's Link Condition in the modified state complex). Let v be a verter in the modified state complez S' of an agent-ondl gridworld. Then
Uk(v) satisfies Gromov's Link Condition if and only if it has empty 2 simpllices nor 3 simmplices, and
if (k(u) fails Gromov's 's Link Condition then there exist pair of agents whose positions differ by either a knight move or a 2 slep bishop move (as in Figurel
Proof. If [k(()) satisfies Gromov's Link Condition, then it has no empty simplices of any dimension, giving the forward implication. For the converse, assume that Ik(U) has no empty 2 simplices nor 3 simpliicss.
11

---

Published in Transactions on Machine Learning Research (11/2023)
Suppose there exist n + vertices spanning a complete subgraph of Ik()), where n 2 4. We want to show that these vertices span an n-mpple.x By induction, we may assume that every subset of n vertices from this set spans an (n 1) simplex. Since n 2 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, polential failures can only be caused by empty 2 2-simpliess or 3 simmpiics..
Next, we want to determine when three pairwise adjacent vertices in Ik(u) span 2-simplex. These vertices represent three admissible moves at v. Since they 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, cach of the two admissible moves within the dance has disjoint support with the second agent's '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 arisc is if the agents' positions differ by a 'knight move' (sec Figure for illustration).
It remains to determine when four pairwise adjacent vertices in (k(r) span a 3 simplex. We may assume that each triple of vertices in this set spans a 2 simplex, for otheewise 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 O-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-simplicos, 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' (sce Figure g for illustration).
]
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 of ofr, 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. To run these experiments, we developed and used a custom Python-based tool (detailed in Appendix AA.).. p. Our focus on small rooms is largely expository, i..,, 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 computer, it is infeasible and unnecessary to construct all integers).
Remark 6.1. By simple counting argument, one can deduce the total number of states in a gridworld. For agent-only gridworld with n cells and & agents, there is a total of (x) states. If there are n cells, k agents, and j objects, then there are (*) (*7²) states. Thus, even for a moderately sized 10 10 room with 50 agents, there are (60) 1.008 x 1029 vertices in the state complex.
12

---

thanks to Theorem Published in Transactions on Machine Learning Research (11/2023)
By Theorem 5.2 checking if Ik(u) satisfies Gromov's Link Condition requires computing the link only up to dimension 3 and then checking whether it is flag complex; if not, we count the number of empty simplices. Checking this for an individual vertex in the state complex is not too computationally demanding, however doing so across the entire state complex becomes more difficult due to the combinatorial explosion in the number of stales as the number of agents or room size grows. In practical applications, such as calculating collision-avoiding navigation routes, is again, by Theorem 5.2 only necessary to construct small local subcomplex. But perhaps even more importantly, detect potential collisions between agents, it is not even necessary to construct Ik(v), since Theorem 5.2 provides computational shortcut: just check for supports of knight or two-step bishop moves between agents.
To quantify the reduction in the computation workload, let us estimate the potential number of simplices in the link vs. the number of those which actually require checking. The number k-simplices in the link should be on the order of most n*+1, however, we don't need check these for
5.2 The number potential 3 simpliiss in the link could be quartic in the number of agents (arising due agents moving); however, there are at most quadratically many that require checking since failure only arise due to pair of agents, again by Theorem 5.2 Similarly, the number of potential 2 simplices is at most cubic, but only quadratically many of these need to be checked. Consequently, chocking Gromov's 's Link Condition at given state is at most quadratic in the number of agents (due to the number of possible pairs).
By using Gromov's Link Condition, we can identify precise measure how ahead agents ought to look in order to safely proceed without fear collisions. Table [ gives a summary analysis of 3 x room with varying numbers of agents. We noticed several symmetries. Commuting moves and the number of states have symmetry about 4.5 agents (due to the label-inversion symmetry previously illustrated in Figure 5 However, curiously, the number of dances has 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 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 Table D. and so existing greedy algorithms (Ardila et al.] 2012) for calculating geodesics will work well in most situations. However, implement an efficient, collision-free path-fnddig algorithm in our modified state complexes, we need add additional check. Specifically, when predefined 'detour' to avoid the collision, which can be done on local basis using the identified supports which lead to positive curvature (as in Figure
near potentially dangerous state, should implement
Table 1: Data of Gromov's Link Condition failure and commuting 4 cyccles in the state complexes of a 3 x room with varying numbers of agents and no objects. The percentage of NPC states (shown in brackets the second column) rounded 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 's Link
Condition Failures
Agents
States (% NPC)
Dances
Commuting moves
Total
Mean
Max
0
1 (100)
0
1
9 (100)
0
2
36 (78)
20
44
32
0.89
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
84 (86)
220
16
0.19
2
7
36 (100)
0
8
9 (100)
0
0
9
1 (100)
0
13

---

Published in Transactions on Machine Learning Research (11/2023)
7 Conclusions and future directions
This study presents novel applications of tools from geometric group theory and combinatorics to the Al research community, opening new ways for recasting and analysing Al problems as geometric ones. Using these tools, we show an example of how the intrinsic geometry of task space serendipitously embeds safety information and makes it possible to determine how far ahead in time an AT system needs to observe to be guaranteod of avoiding dangerous actions.
Leike al. (2017) 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 Al safety problems, e.g., agents pushing/ mushing/puuling pulling objects, pressing buttons, modifying their form or behaviour, rewards/ palls//unnissmtssss.. opening/ gpening/unlocking 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/transing /transienccc. Braiding can be used to study route planning, back-tracking, cooperation, assembly, and topological entropy in congestion [Ghrist 2009). Numerous extensions are possible, allowing to study and geometrically represent further problems with view to developing efficient, geometrically-insiter local algorithms without the need for training.
Do learning algorithms already implement such geometricalll-insiieee algorithms, the related geometry, or approximations thereof? To find out, it will be interesting to investigate how modified state complexes map to learned internal representations of neural networks trained to predict multi-agent gridworld dynamics. Such mappings would connect the geometry and lopology of task space directly to optimisation procedures and learning trajectories in latent representation spaces, potentially highlighting topological and geometric differences and opportunities for deeper insight and improvement of optimisation procedures, in the spirit of Naitzat et al. (2020): Zhao & Zhang (2022). One could also compare biological optimisation processes and internal representations of allocentric and egocentric navigation (Burgess 2006
Gardner et al.] 2022).
and how this interacts with the position of other agents (Duvelle & Jeffery 2018
Sutherland & Bilkey
2020). Additionally, geometrically integrating safety information to constrain learning and control algorithms Verginis et al., 2021 may be fruitful.
From more mathematical perspective, state complexes of gridworlds give rise to interesting class of geometric spaces. It would be worthwhile to investigale their geometric and lopological 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 hypothosise 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 essential way appears to be relatively unexplored approach. Indeed, much of the mathematical literature concerning cube complexes focusses on showing that the Link Condition always holds. In works such as Abrams & Ghrist (2004); Ghrist & Peterson (2007); Ardila let al. (2012) NPC is a property which may be exploited using subsequent related properties of the cube complex (e.g., known hyperplane arrangements or CAT(O) geometry) to prove statements about the modelled systems. In contrast, since NPC does not always hold in our modified state complexes, we can instcad use it (or its failure) as condition detect some interesting features; namely, potential collisions of agents. To our knowledge, the only other works which go against this trend are Abrams & Ghrist (2004), in which failure detects global disconnection of metamorphic system, and Bell et al. (2019), 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.
Another interesting mathematical direction to explore is the potential connection of (modified) state complexes and the work of Ghrist & Lavalle (2006). In Ghrist & Lavalle (2006), a 'roadmap co-ordination space' is constructed by taking product of n graphs, then deleting an 'obstacle' set. Here, each graph involved
14

---

Published in Transactions on Machine Learning Research (11/2023)
represents 'roadmap' where the corresponding agent move. One may adapt this to the setting of n (distinguished) agents in gridworld: choose the gridworld as the roadmap for each agent, then delete cubes when there is a collision between two agents (this needs to be done carefully). We expect the resulting roadmap co-ordination space to be the same as the state complex for the (labelled) n agent gridworld obtained by directly constructing the (unmodified) state complex. In other words, we believe the Christ-Lavalli and Abrams- Ghrrsst Caarist-Peterson approaches should both yield the same object the context of distinguished agents in gridworld. Under either approach, one obtains an object which is NPC. However, both frameworks suffer from common limitation: each agent is confined to move graph 1 1-dimensional space. However, we argue in Section 4 a gridworld ought to be regarded as discretised 2- 2-dimensional domain. In this light, it would be interesting to define a 'modified roadmap configuration space' which allows each roadmap to be a (discretised) rectangle (or whatever shape the room might. be). It seems plausible that by deleting "collision' cubes in an appropriate manner, one should recover our modified state complex (for n labelled agents). If so, it would further support the case that filling squares whenever there are dances is the most natural approach. Indeed, our guiding intuition for the modified slate complex of an n-agent gridworld is that it should serve discrete analogue of the configuration space of points on the plane.
Broader Impact Statement
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 statod assumptions hold.
Acknowledgements
This project began a rotation project during the first author's PhD programme. We wish to acknowledge and thank Anastasiaa Tsvietkova for supporting the first author to do research rotation in the Topology and Geometry of Manifolds Unit at OIST, in which the second author was 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) and the Suzhou Science and Technology Programme (2XL2022473). We thank anonymous reviewers for their suggestions to improve exposition. The authors declare no other competing interests.
References
Aaron Abrams and Robert Ghrist. State complexes for metamorphic robots. The International Journal of Robotics Research, 23(7-8):811 11-86661111111111111111111111111 2004.
Karen Archer, Nicola Catenacci Volpi, Franziska Bröker, and Daniel Polani. A space of goals: the cognitive geometry of informationally bounded agents. aarXiv2211103699) 2021.
Federico Ardila, Megan Owen, and Seth Sullivant. Geodesics in CAT(() cubical complexes. Adv. Appl. Math., 48(1):142 163, 2012. ISSN 0196-8858, doi: 10.1016/j.aam.200 waw..mmm0100000044 URL 1016/j /016/j. 2011..m.......666... 06.
Federico Ardila, Tia Baker, and Rika Yatchak. Moving robots efficiently using the combinatorics of CAT(() cubical complexes. SIAM Journal on Discrete Mathematics, 28(2):986-1007, 2014. doi: 10.1137/1208081155
URL https://doi. http://....37//088111111
Federico Ardila, Hanner Bastidas, Cesar Ceballos, and John Guo. The configuration space of a robotic arm in a tunnel. SIAM Journal on Discrete Mathematics, (14)::665522000 2017. doi: 111137/16M1089411..
URL https://doi.ors wwtpooi..rgg/... http:/10..13///M10000000
15

---

Published in Transactions on Machine Learning Research (11/2023)
Omur Arslan, Dan P Guralnik, and Daniel E Koditschek. Coordinated robot navigation via hierarchical clustering. IEEE Transactãons on Robolies, 32(2):352-33 371, 2016.
Mark C. Bell, Valentina Disarlo, and Robert Tang. Cubical geometry in the polygonalisation complex. Math. Proc. Combridge Philos. Soc., 167 (1):1) 22, 2019. ISSN 0305-0041. doi: 10.1017/003050041100001333 URL https://doii org/ 10. 1017 111.1001170000000111100010011110
Martin R. Bridson and André Haefliger. Metric spaces of non-positive curvolure, volume 319 of Grundlehren der mathematischen Wissenschaften [Pundamental Principles of Mathematical Sciences). Springer- Verlag, Berlin, 1999. ISBN 3-540-64324-9, doi: (0.1007/978-3-00 3-2-266622----99 URL 978-3 6623-6662-1294-3
Neil Burgess. Spatial memory: how egocentric and allocentric combine. Trends in Cognitive Sciences, 10(12):551-53, 2006. ISSN 1364-6613. doi: httpps///hoi.rrg//11000//// 2000....000....
URL https:
Indira Chatterji and Graham Niblo. From wall spaces to CAT(() cube complexes. International Journal
of Algebra and Computation, (5(05n06):875 885, 2005. doi: 10.1122/90011190005006666 URL https //doi org/ 10. 1142//92288199755028888
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, (4(04))5792-5779, Apr. 2020. doi: 10.1609 (0.1609/aaai.ve
w0000//aaa..34444..00.0... v34104.6036. URL https:://oj. aaai org/
index. index.php/AMMe http:p/p/////aartttcc/////e/////
E. Duvelle and K.J. Jeffery. Social spaces: Place cells represent the locations of others. Currend Biology,
28(6):R271 2018. ISSN 0960-9822. doi: httpes///oliorrr//..00///....b 201.0.0.00 URL https
Herbert Edelsbrunner and John L. Harer. Compulational Topology: An Introduction. American Mathematical Society, 01 2010. ISBN 978-0-8218-4925-55 doi: 10.1007/978-3-5544 540-33259-66
Tingxiang Fan, Pinxin Long, Wenxi Liu, and Jia Pan. Distributed multi-robot collision avoidance via deep re- inforcement learning for navigation in complex scenarios. The International Journal of Robotics Research, 39 (7):856-899) 892, 2020. doi: 10.1177/02788 0777777027786--9211666881 URL lattps://dot org/10....ooo /tt.://///o0o.oo0/01111117000020 11777077777788999911555
Richard J. Gardner, Erik Hermansen, Marius Pachitariu, Yoram Burak, Nils A. Baas, Benjamin A. Dunn, May-Britt Moser, and Edvard Moser. Toroidal topology of population activity in grid cells. Nature 602 (7895):123 128, Feb 2022. ISSN 1476-4687. doi: 10.008//4411886002--2666... URL httph::////// https://doi.org///
1098/44116--021-02888--
R. Ghrist and V. Peterson. The geometry and topology of reconfiguration. Advances in Applied Mathematics,
38(3):302 323, 2007. ISSN 0196-8858, doi: https://loi.rr///11110........ 200.000.00.0000 URL https:
Robert Ghrist. Configuration spaces, braids, and robotics, pp. 263-304- World Scientific Publishing,
2009. doi: 10. 10.1142/9789814220 /97899942911115 0004. URL http:ppp//rrr.oorrrccccaaooccooe 1142/ 9789814291415 0004
Robert Ghrist and Steven Lavalle. Nonpositive curvature and pareto optimal coordination of robots. SIAM Journal on Control and Oplimization, 45(5):1697-17133 2006.
M. Gromov. Hyperbolic groups. In S. M. Gersten (ed.), Essays in Group Theory, pp. 75-263. Springer New York, New York, NY, 1987. ISBN 978-1-4613-9586-7, doi: 10.1007/9978111-6633996868 3. URL http://...0../0..000000001111111 btttps///don http://i.oooooo.o.//o/. 1000:/00001007778--111
Allen Hatcher. Algebracc topology. Cambridge University Press, 2002.
16

---

Published in Transactions on Machine Learning Research (11/2023)
Michael Hauser and Asok Ray. Principles of Riemannian geometry in neural networks. In I. Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett (eds.), Advances in Neural Information Processing Systems, volume 30. Curran Associates, Inc., 2017. URL https:
Victoria J. Hodge, Richard Hawkins, and Rob Alexander. Deep reinforcement learning for drone navigation
using semsor data. Newral Computing and Applications, 33(6):2015 2033, Mar 2021. ISSN 1433-3058. doi:
10.1007/:000211-20-05500 020-0099700. URL httppp///aaa..oor.......///////0
Tvana Kajic, Eser Aygün, and Doina Precup. Learning to cooperate: Emergent communication in multi-agent
navigation. In 4.2nd Annual Virtual Meeting of the Coynitive Science Society (CogSci 2020), 2020. URL
httpss//oogsct..mmddddddlll11 mwndmodeling..nnnmmmmmmm
html
Tomihisa Kamada and Saloru Kawai. An algorithm for drawing general undirected graphs. Information
Processing Letters, (17:7511 1989. ISSN 0020-0190. doi:
URL htttp://www..cceeceddiieeee wtw.eiieeneeeeettooiiiioioio..ee http:///cccccaeeeeococc//aaaaaaa
Takeshi Kano, Mayuko Iwamoto, and Daishin Ucyama. Decentralised control of multiple mobile agents for quick, smooth, and safe movement. Physica A: Statistionl Mechanics and ils Applications, 572:125898, 2021.
ISSN 0378-4371. doi: https://dooi.org/11... 101600...111.ppp/.. 20t. URL https://ww..ccieneddirree
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, pp. 9, 2019.
Tom Larkworthy and Subramanian Ramamoorthy. An efficient algorithm for self-reconfiguration planning in a modular robot. In 2010 IEEE International Conference on Robolics and Aulomalion, pp- 2010. doi: 10.1109/
10.119//OBBOT ROTOOOOOOTTTT 2010.5509482.
Florian Laurent, Manuel Schneider, Christian Scheller, Jeremy Watson, Jiaoyang Li, Zhe Chen, Yi Zheng, Shao-Hung Chan, Konstantin Makhnov, Oleg Svidchenko, Vladimir Egorov, Dmitry Ivanov, Alcksci 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 Grid World, pp. 275 301. PMLR, 08 2021.
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(3):361 374, 2020. ISSN 2095-8099, doi: https://ddo..or//10..000 wtt.:/eee.........001... URL httpp::/www.ssiamccerrrr.c.o p11/$220580991930227999
Jan Leike, Miljan Martic, Victoria Krakovna, Pedro A. Ortega, Tom Everitt, Andrew Lefranc,,,, Laurent Orseau, and Shane Legg, Al safety gridworkds. srXiv:1711.09982 2017. URL http:://aarxiiiorrggabb////////s
Gregory Naitzat, Andrey Zhitnikov, and Lek-Hong Lim. Topology of deep neural networks. Journal of Machine Learning Research, 21(184):1-40, 2020. URL http:://jnll..orr/pppprss///////
html
Xue Bin Peng and Michiel van de Panne. Learning locomotion skills using deeprl: Does the choice of action space matter? In Proceedings of the ACM SIGGRAPH / Eurroraphics Symposium on Computer Animation, SCA '17, New York, NY, USA, 2017. Association for Computing Machinery. ISBN 9781450350914. doi: 00.1145/3099564.00 30099567. URL hattps://date www.oii..rr/.... 1145/3099564. 3099567
Zengyi Qin, Kaiqing Zhang, Yuxiao Chen, Jingkai Chen, and Chuchu Fan. Learning safe multi-agent control with decentralized neural barrier certificates. In International Conference on Learning Representations, 2021. URL /twpo////w////////////////////// wttp://wwwweeeeeeooururreerrre _1BRxx
Daniele Reda, Tianxin Tao, and Michiel van de Panne. Learning to locomote: Understanding how environment design matters for deep reinforcement learning. In Proceedings of the 13th ACM SIGGRAPH Conference on Motion, Interaction and Games, pp. 1-10, 2020.
17

---

Published in Transactions on Machine Learning Research (11/2023)
Yara Rizk, Marictte Awad, and Edward W Tunstel. Cooperative heterogeneous multi-robot systems: A survey. ACM Compuling Surveys (CSUR), 52(2):1-31, 2019.
Michah Sageev. CAT(O) cube complexes and groups. In Geometric group theory, volume 21 of [AS/Part City Math. Ser., pp- 7-54. Amer. Math. Soc., Providence, RI, 2014. doi: (0.1090/pcms//e /02. URL https://dbl..rgg/ http://00/0/ppp///////////
Jan Schneider, Pierre Schumacher, Daniel Häufle, Bernhard Schölkopf, and Dieter Büchler. Investigating the impact of action reprosentations in policy gradient algorithms. arXiv preprint arXiv:2309.06921, 2023.
Petra Schwer. Lecture notes on CAT(O) cube complexes, 2019. URL
06815
Cory Stephenson, Suchismita Padhy, Abhinav Ganesh, Yue Hui, Hanlin Tang, and Sue Chung. On the geometry of generalization and memorization in deep neural networks. In International Conference Learning Represenlations, 2021. URL
Jeremy Stober, Risto Miikkulainen, and Benjamin Kuipers. Learning geomelry from sensorimotor experience. In 2011 IEEE International Conference on Development and Learning (ICDL), volume 2, pp. 1-6, 2011. doi: 10.1109 10.110000EEELEEEE 100.DDEEL...211.666511
Christina J. Sutherland and David K. Bilkey. Hippocampal coding of conspecific position. Brain Research, 1745:146920 2020. ISSN 0006-8993, doi: http:r//bboorr//...lf///iiiiesse 20w.uuree..2...1492000 URL https
//www www.ssicieeedreet...m otc.aaaci....ooo/ooooooo/ooo///0
Christos K. Verginis, Franck Djeumou, and Ufuk Topcu. Learning-based safety-constrained control from scarce data via reciprocal barriers. In 2021 60th IEEE Conference on Decision and Control (CDC), pp. 83 89, 2021. doi: 10.1109/ 10.1109/CDDC45484.2002 (CDC45444420221965522
Oriol Vinyals, Igor Babuschkin, Wojeiech 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 Painc, Caglar Gulcchre, 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(7782):356) 350-354, 2019. ISSN 0028-0836.
doi: 10. 0505//44556-9999777
Vikram Waradpande, Daniel Kudenko, and Megha Khosla. Deep reinforcement learning with graph-basod state representations. arXiv:2004.10 13965 2020. URL http:////arrii..or/aa///////////
Daniel T. Wisc. From riches to raags: 3-manifolds, right-angled Artin groups, and cubical geometry, volume 117 of CBMS Regional Conference Series in Matherattis.. Published for the Conference Board of the Mathematical Sciences, Washington, DC; by the American Mathematical Society, Providence, RI, 2012. ISBN 975-0-8218-8800-L doi: 10.1090/cbms/117 URL https://doi. httt::://doi.orr/1000. 11t1:110////////111/01110
Yang Zhao and Hao Zhang. Quantitative performance assessment of CNN units via topological entropy calculation. In International Conference on Learning Representations, 2022. URL Nttpp://openreviier
het/forrum?rd=xxPyyyewPPP
18

---

Published in Transactions on Machine Learning Research (11/2023)
A
Appendix
A.1 Gallery.
The 2 x 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 's Link Condition fails due to the agents being separated by a knight's s move (see Theorem 5.2p. At this state, there are actually two empty 2 simplices in link this is because the pattern appearing the c-lell subgrid with two agents (as Figure x arises in two different ways within the given state on the gridworld. The only other state where Gromov's Link Condition fails mirror image of the one shown.
Further small gridworkds and their respective state complexes are shown in Figures 10 and 12
Figure 9: A 2 x 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).
A.2 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 Lenovo IdeaPad 510-15ISK laptop. The open-source code is available here: htttps//ggtthb..e
For the sake of generality and Kuture-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 agent-only gridworlds. Another of computational efficiency available in many rooms in the symmetries of the
19

---

Published in Transactions on Machine Learning Research (11/2023)
Figure 10: A 3 3 room with two agents (right) and its state complex (left), where dances shaded blue and commuting moves are shaded red. The darker-shaded vertex represents the state of the gridworld shown. Naturally-oceurring copies of this state complex can be found as sub-complexes in the state complex shown in Figure 12
Figure 11: A 4 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-occuriigg copies of this state complex can be found as sub-complexes in the state complex shown in Figure 12
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 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 coordinate system is not an issuc an agent label sees neighbouring vertex with an empty floor label, the support exists and the generator can be used. However, Push/Pull Pull only allows objects to be pushed pulled by the agent in straight line within the gridworld. We ensure
20

---

Published in Transactions on Machine Learning Research (11/2023)
Figure 12: A room with two agents (right) and its state complex (left), where dances are shaded blue and commuting moves are shaded red. The darkor-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 corridor with two agents, shown in Figure I1 There are also naturally-occuriing copies of state complex of the 3 3 room with two agents, shown in Figure 10
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 colls (* ('agent', 'object', and 'floor'), such that together they form 2 grid.
A.3 Classification of 4-cycles
A 4-cycle in the state graph could arise in several different ways. For example, it could arise from a pair of commuting moves, agent dancing, two agents doing half-revolution about one another as in Figure 3 To distinguish these in our implementation for agent-only gridworlds, count the number of times cell is occupied by an agent within the 4-cycle. We use this fact in our Python tool to identify commuting move and dancing c-ccle..
For the remainder of this section, let vo U1, U2, vn denote the vertices an embedded 4 cycle in the modified state complex of an aglnt-only gridworld, and suppose &i is the generator such that @.[u%]] = us+1 (modulo 4) for each i. Let U = P(o))
Lemma A.1 (Supports of cycles). There are ezactly 4 cells contained in U.
Proof. Consider applying the generators do, Φ1, 62, d3 sequentially starting from the initial state up- Each di is a Move generator which swaps the 'agent' and 'floor' labels in a pair of adjacent cells. Since we return to to at the end of this 4 cycle, each cell in U appears in an even number of the de's. Therefore, U comprises at most cells.
Suppose for contradiction that U contains exactly S colls. Suppose that there are k 'agent" labels appearing on any (hence every) restricted state vslu. Then there are (2) possible ways label the cells of U with exactly ie agents. Since (?) < 3 for all < 3 and 0 < l < n, follows that the wyl cannot all be distinct. Since all i; agree outside U, we deduce that Vo. V1, 02, U3 cannot all be distinct. This contradicts the assumption that they form embedded 4 4-cycl.
21

---

Published in Transactions on Machine Learning Research (11/2023)
Lemma A.2 (y-ceele classification). Any embedded 4 4-cycle in the modified state compler of an agent-only
gridworld arises from either:
single agent doing dance,
pair of commuuling moves,
pair of agents doing a half-twist in 2 x 2 subgrid,
three agents doing an 'inverted' dance.
Proof. We consider the cases depending the number of involved agents, that is, the number of 'agent' labels appearing volu.
If there is only one involved agent, then this agent must occupy each cell in U exactly once throughout the 4- cycle. Since the agent must Move to an adjacent cell at each step, it must move along an embedded 4 4-cycle in the (dual graph of the) gridworld. The only way this can occur is U is a 2 subgrid. Therefore, the agents performs a dance.
The case of three involved agents follows analogously by inverting the 'agent' and 'floor' labels.
Now suppose there are two agents involved. After performing the cycle, the two agents either return to their starting locations, swap their positions. In the former case, each agent must move exactly twice throughout the 4 cycle. The only way this can occur is if each agent moves to an adjacent cell and then moves back to its initial position. Since U comprises exactly cells, the supports of the respective Moves must disjoint. Therefore, the agents perform a pair of commuting Moves.
It remains to deal with the case where the agents swap positions. Let us view an induced subgraph in the gridworld. Since the agents swap positions, U must be connected. Since U has 4 cells, it must be isomorphic to either path graph of length 3, 'tripod' (a tree with one vertex of valence 3 and three verlices of valence 1), or cycle graph of length 4. If U is path graph then it is impossible for the agents to swap positions. The state graph for two agents in a tripod isomorphic to cycle graph of length (as in Figure 13,, therefore the agents cannot swap positions using only Moves. follows that must be a cycle graph, and so the involved cells form 2 x subgrid. Therefore, our problem reduces examining 4-cycles in the state complex for two agents in a 2 room, as depicted Figure 3 The cycles where the agents swap positions are precisely those that not filled in with square. In each of these cases, our cycle arises from two agents performing "half-twist in 2 x subgrid.
Lemma A.3 (4 cycle identification). The type of an embedded cycle in the modified state complex of an agent-only gridworld can identified by counting the occurrences each involved grid cell is occupied by on agent. Specifically, we have
a dance + one count in each of the four cells,
commuling moves + two counts in each of the four cells,
half-Iwist > three counts in one cell, two counds in two cells, one count in one cell, and
an inverted dance three counts in each of the four cells.
Proof. This follows by inspecting each case described in Lemma A.2 and counting the number of occurrences each grid cell occupied by an agent.
22

---

Published in Transactions on Machine Learning Research (11/2023)
Figure 13: The state complex T-shaped room with two agents, forming a 6-cycle.
23


Reviews:
[{"review_id": "4VIl1ed74V", "reviewer": "Reviewer_oPeG", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n - the writing is clear and concise, and translates complex math in a way that could be accessible for someone without as much formal training in that area\n - good examples and illustrations are given\n\nWeaknesses:\n - the work analyzes a simplistic model that does not capture many complex motion planning.  Yet, this sort of set-up is used in many planning areas of robotics when the world can indeed be discretized.  \n - the main contribution is a bit hard to understand, and one basically needs to read the entire paper to understand what the contribution is. \n - the paper does not make connections directly into ML/AI, but rather provides mathematics that could be used as the basis of contributions.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper provides an algebraic/topological analysis of a simple grid-world set up used in robotics and AI.  It considers a fixed grid-defined state space where each position can be occupied by a single agent or a single object, or not occupied.  Agents can move to a neighboring unoccupied cell, and can push or pull adjacent objects with them.  \n\nThe papers main results is an extension of a previous characterization by Adams, Ghrist, and Peterson.  The new analysis identifies some rare situations which do not satisfy the conditions from the prior work which ensures the space is non-positively curved.  These cases correspond with potential grid lock and other challenges in planning.  \n\nWhile this paper does not directly use these findings in AI for robotics, they could potentially provide the scaffold for others to do so, in ways that the work of Adams, Christ, and Peterson did in years before.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "The paper is fine for what it is.", "broader_impact_concerns": "No broader impact concerns.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "GG7kzWpglm", "reviewer": "Reviewer_jxVD", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "It well-written and does make me interested in learning more about state complexes to see what it can add to how I think about tasks I study, though it is far from clear to me at this point even if I find the connections intriguing. \n\nThe main weakness is that the article targets an audience and journal for whom the material is far removed and what it delivers is not really tangible but still seems more of theoretical mathematical interest in the sense of adding more examples of interest to the mathematical study of state complexes and ways general geometric properties materialises in them. The authors do, however, make attempts at alleviating this weakness by some concrete illustrative experiments. The direction of seeing if this theory can help bring understanding to what representations are learnt by deep neural networks I find the most promising for further future work.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The authors takes the theory of state complexes in geometric group theory to multi-agent grid-worlds.\nThey provide a well-written introduction to this area, which is quite far removed from almost all work in the multi-agent reinforcement learning field to whom I take this as being targeted. \nThe authors noticed a connection between the geometric concept of positive curvature in the state complex and the risk of collision between agents moving in this world.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "I do not have any concrete input to this work, which I review with very low confidence.", "broader_impact_concerns": "None", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "o6Dqk8Pf4C", "reviewer": "Reviewer_2GJX", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "*Positives:*\n- Adopts a principled approach to safe planning in gridworlds, based on the mathematical framework of reconfigurable systems.\n- Identifies a potentially interesting connection between NPC failures and undesirable states.\n- Mentions connections to the notion of 'fog-of-war' from real-time strategy games.\n- Proposes simple local tests to detect/anticipate undesirable states, e.g., in an AI planner.\n\n*Needs work:*\n- Key definitions need to be clarified; see below.\n- ~The main result, which can be seen in Figure 8, is fairly obvious, which sheds doubts on the potential of the proposed approach to bring about fundamental progress in this application area. This is not helped by the fact that the state complex is prohibitively large, even when restricted to small neighborhoods or scenarios, which hinders its adoption in practice.~\n- The main result, as summarized in Figure 8, appears obvious. This leaves doubts as to the how much it helps in practice. It would help greatly to demonstrate concrete benefits in an AI planning application, beyond the statistics reported in the experimental section.\n- Positioning with respect to prior work needs to be clarified as well; see below.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper adopts the framework of reconfigurable systems and state complexes to the study of gridworlds. Using a collection of figures, the paper offers a friendly introduction to the construction of state complexes for simple environments with agents and movable objects, with additional visualizations of the resulting state ~graphs~ complexes.\n\nThe main result is a theoretical characterization of local failures of the Gromov link condition, and the implied non-positive curvature (NPC), for a modified state ~graph~ complex. The modification is proposed to remove uninteresting topology of 4-cycles that don't bound an actual obstacle or void, where agents are only allowed to move horizontally or vertically to empty cells within the grid. Since NPC served as the basis of multiple key results in reconfigurable systems, this deviation is potentially interesting. (Note that the authors only derive this characterization for agent-only environments.)\n\nThe paper concludes with statistics of NPC failures in a fixed grid with varying number of agents.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "**Claims:**\n- [abstract] *More broadly, our work introduces tools from geometric group theory and combinatorics to the AI community*\n  - For this claim to hold, I believe the paper needs to make a better job rigorously presenting background mathematical tools with a more thorough survey of how those tools were applied to related problems, e.g., in motion planning. See comments below for presentation issues.\n- [page 1] *Our main contribution is the first application of this geometric approach (of using state complexes) to the setting of multi-agent gridworlds.*\n  - For this claim to hold, the paper needs to make concrete progress on a fundamental problem in the study of gridworlds using the geometric approach in question. In contrast, experimental results only report statistics for newly-introduced notions. In addition, state complexes have been utilized numerous times in the study of multi-agents in very similar settings.\n- [page 1] *Nevertheless, by applying Gromov’s Link Condition, we completely characterise when positive curvature occurs in our new state complexes*\n  - This claim is overstated (completely). This result was only derived for an agent-only environment, which does not qualify as a complete characterization.\n- [page 2] *Current approaches to collision-detection and navigation during multi-agent navigation often rely on modelling and predicting collisions based on large training datasets [..] or by explicitly modelling physical movements [..]*\n  - This claim is overstated (often). Prior work applied other theories, including the ~NPC~ Gromov link condition~s~ studied in this paper.\n- [page 2] *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*\n  - This framing is difficult to justify given the actual content of the article. I would recommend deferring this connection to the discussion or future work sections at the end.\n- [page 2] *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.*\n  - This claim lacks evidence. There has certainly been a lot of work in machine learning on understanding the geometry of the input data and how it impacts learning algorithms, e.g., manifold hypothesis.\n\n**Missing technical discussion:**\n- Section 2\n  - It is necessary to explain explicitly how generators stand for the more common notion of turn-taking. That is, the state complex also discretizes time from the perspective of agents.\n  - Also explain how the notion of commutativity relates to simultaneous action by independent agents, i.e., agents perceiving the system at a given state can decide to move simultaneously if the resulting actions commute.\n  - This leaves non-commuting moves under-specified. From a physical viewpoint, those aren't realizable without collision. It is not clear if the resulting (invalid) states are included in the state graph, for otherwise the simultaneous execution of a non-commuting set of moves cannot happen by definition. For example, fewer legal actions can be selectively allowed, e.g., by tie-breaking, which seems to be how many computer games resolve this issue.\n  - The above setting is both natural and practical, and similar formulations were studied in prior works, for example:\n    - Ghrist, Robert, and Steven M. Lavalle. \"Nonpositive curvature and pareto optimal coordination of robots.\" SIAM Journal on Control and Optimization 45, no. 5 (2006): 1697-1713.\n    - Please cite and discuss, clearly positioning the proposed contributions in this light.\n  - Perhaps discussing 'fog of war' at this point would help clarify the scope of the contribution.\n- Section 4\n  - Please explain explicitly whether dances allow agents to move diagonally. If so, wouldn't it be more natural to include diagonal moves from the get-go?\n  - It appears dances only allow diagonal moves if the move can be executed both as a sequence of horizontal+vertical or vertical+horizontal moves, i.e., if only one of those two sequences are admissible, the diagonal move cannot happen. I don't see a justification for this restriction, since the stated purpose of dances is to more faithfully describe the continuum of a 2D plane -- following the same reasoning at the bottom of Page 6.\n- Section 5\n  - Please note that the article makes no mention of CAT(0).\n  - Would it help to use computer-aided proofs or enumeration to characterize NPC failures involving objects or multiple agents+objects?\n\n**Presentation Issues:**\n- The notation $\\mathcal{S}^{(1)}$ was not justified.\n- The discussion (3 paragraphs) near Figure 3 seems too verbose, and seems to reappear each time a complex is defined.\n  - I would recommend presenting a formal definition as a simple equation.\n- In justifying small environments (first paragraph of Section 6) I found the analogy to integer addition unnecessary. The remark was much more relevant to the discussion.\n- It is not immediately clear how label-inversion and loss of symmetry help the main development, or fit the same motivations towards practical applications.\n  - I would recommend deferring to an appendix with more space to say more for motivation, or at least limiting such discussion to specific points where they are deemed most relevant.\n- Section 3 appears largely unrelated to the development towards the main result, and does not offer specific technical contributions.\n  - Breadth-first-search is a standard technique, and limiting the study to connected state graphs makes this less interesting.\n  - It may be true that visualizations can be revealing for small subsets of the state ~graph~ complex, but this point was not adequately developed.\n  - The section seems to report a collection of observations before digressing into further unanswered questions.\n  - I would strongly recommend to defer this discussion and related figure to an appendix.\n- Last paragraph of Section 4 seems to digress beyond the scope of the paper: ``*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.*''", "broader_impact_concerns": "Adequately addressed by the authors.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This is a fairly specialized result, but should prove relevant for planning problems in AI, which is within TMLR's scope.  It provides mathematical foundation for an actively used class of planning problems, and characterizes a set of scenarios which require specific attention in planning.  
This will help formalize when certain planning approaches will work, and identify specific scenarios where things will not automatically work, and special cases will be needed to handle.  

However, there are numerous things that should be addressed before the paper is accepted.  These will need to be reviewed by the action editor (myself) before final approval.  
With regard to this, I approve the authors plan (amended as):
> 1. Add discussion of prior work on state graphs and emphasize the distinction between graphs vs complexes in the introduction section.
> 2. Add the computational discussion to section 6.
> 3. Make it clear in the introduction and abstract that our proof is for the agent-only case.
> 4. Add discussion of "temporal commutativity" in section 2 and "spatial commutativity" in section 5.
> 5. Include a finer discussion on the interpretation of collision-detection to section 5.
> 6. Cite and discuss the recommended references provided by Reviewer 2GJX.

Please provide a summary of changes when you have made them.
Decision: Accept (poster)