Detecting danger in gridworlds using Gromov's Link Condition
Authors: Thomas F Burns
Robert Tang
Venue: NeurIPS 2022 Submitted (2022)
Keywords: safety
multi-agent navigation
geometry
topology
braiding
collision-avoidance
curvature
cube complex
gridworld
configuration space

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

Detecting danger in gridworlds using Gromov's Link Condition
Anonymous Author(s)
Affiliation
Address
email
Abstract
Gridworlds have been long-utilised in Al research, particularly in reinforcement learning, they provide simple yet scalable models for many real-world applica- tions such as robot navigation, emergent behaviour, and operations research. We initiate study of gridworlds using the mathematical framework of reconfigurable systems and state complexes due to Abrams, Ghrist Peterson. State complexes represent all possible configurations of 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 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 's Link Condi- tion). Serendipitously,
5
10
11
discover these failures occur exactly where undesirable or dangerous states appear in the gridworld. Our results therefore provide a novel method for seeking guaranteed safety limitations in discrete task environments with single or multiple agents, and offer useful safety information (in geometric and topological forms) for incorporation or analysis of machine learning sys- tems. More broadly, our work introduces tools from geometric group theory and combinatorics the AI community and demonstrates proof-of-concep for this geometric viewpoint of the task domain through the example of simple gridworld environments.
13
14
15
16
17
18
20
Introduction
21
The notion of state (or configuration/phase) space is commonly used in mathematics and physics to represent all the possible states a given system as single geometric (or topological) object. This perspective provides bridge which allows for tools from geometry and topology be applied to the system of concern. Moreover, certain features of given system are reflected by some geometric 25
29
24
26 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.
27
28
29 In discrete settings, state spaces are typically represented by graphs or their higher dimensional analogues such simplicial complexes cube complexes. Abrams, Ghrist & Peterson's 's state complexes (AG04) (PO7) provide a general framework for representing discrete reconfigurable
30
31
systems non-positively curved (NPC) cube complexes, giving access to wealth of mathematical
33 and computational benefits via efficient optimisation algorithms guided by geometric insight [AOS
34 These have been used develop efficient algorithms for robotic motion planning [4Y]4 ABCG17
35 and self-reconfiguration of modular robots [LR10]. NPC cube complexes also possess rich hyperplane structures which geometrically capture binary classification [CN05 Wis Sag14), However, their broader utility to fields like artificial intelligence (AI) has until now been relatively unexplored.
36
37
Submitted to 36th Conference on Neural Information Processing Systems (NeurIPS 2022). Do not distribute.

---

38
Our main contribution is the first application of this geometric approach (of using state complexes) to the setting of multi-agent gridworlds. We introduce a natural modification the state complex appropriate to the setting of gridworlds (to capture the braiding or relative movements of agents); however, this can lead to state complexes which are no longer NPC. Nevertheless, by applying Gromov's s Link Condition, we completely characterise when positive curvature occurs in our new state complexes, and relate this to features of the gridworlds (see Theorem [52)). Serendipitously, we discover that the states where Gromov's Link Condition fails are those in which agents can potentially collide. In other words, collision-detection is naturally embedded into the intrinsic geometry of the system. Current approaches to collision-detection and navigation during multi- agent navigation often rely on modelling and predicting collisions based on large training datasets [FGEET F2L QZC 21) or by explicitly modelling physical movements [KIU21]. However, our approach is purely geometric, requires no training, and can accommodate many conceivable types of actions and inter-actions, not just simple movements.
39
40
41
42
43
44
45
47
49
50
51
Our work relates to a growing body of research aimed towards understanding, from geometric perspective, how deep learning methods transform input data into decisions, memories, or actions HR17 LAG 20, SPG+21 I SMKII) However, such studies do not usually incorporate the geometry of the originating domain or task in a substantial way, before applying or investigating
53
54
55 the performance of learning algorithms and even fewer do so for multi-agent systems. One possible reason for this is a lack of known suitable tools. Our experimental and theoretical results show there
57 a wealth of geometric information available in (even very simple) task domains, which is accessible using tools from geometrie group theory and combinatorics.
59 2
State complex of gridworld
60 A gridworld is two-dimensional, flat array of cells arranged in a grid,
61 much like a chess or checker board. Each cell can be occupied or un- occupied. A cell may be occupied, in our setting, by one and only one mrvely-moving agent or movable object. Other gridworlds may in- clude rewards, punishments, buttons, doors, locks, keys, checkpoints, dropbears, etc., much like many basic video games. Gridworlds have been long-un -utlgdd setting in AI research, particularly reinforcement learning, since they are simple yet scalable in size and sophistication (DSHLKT20) WKK20). They also offer clear analogies to many real- world applications or questions, such as robot navigation [HH22]] emer- gent behaviour [KP200], and operations research LSS++21) For these reasons, gridworlds have also been developed for formally specifying problems AI safety [LMK+17]
63
64
65
67
68
69
71
72
Figure 1: A 3 x 3 grid- world with one agent (a koala) and one object (a beach ball).
73 state of gridworld can be encoded by assigning each cell a label, In
74 the example shown in Figure [ these labels are shown for an agent,
75 object, and empty floor. A change in the state, such as an agent moving from one cell to adjacent empty cell, can be encoded by relabelling the
77 cells involved. This perspective allows us to take advantage of the notion of reconfigurable systems as introduced by Abrams, Ghrist & Peterson [AG04 GP07..
78
79 More formally, consider graph and set of labels. state is a function s V(G)) - A, iee an assignment of label to each vertex of G. A possible relabelling is encoded using generator d; this comprises the following data:
81
subgraph PU)( C G called the support;
subgraph (R) C SU P()) called the trace; and
unordered pair of local states
loc 40 un : V(SUP()) + A
that agree on V(SUP())) - (TT(())) but differ V(TR(O)).
A generator o is admissible at state if s|su uge (or ) in other words, if the assignment of labels to ((SUP()) given by completely matches the labelling from (exactly) one of the two

---

88
local states, If this holds, we may apply & to the state to obtain a new state Ø(s) given by
u Loc s(v),
(v),
V VEV())())
otherwise.
This has the effect of relabelling the vertices in (and only in) TR()) to match the other local state 90 of Φb Since the local states unordered, if is admissible then it is also admissible d(s): moreover, < [[][)]] = 8.
89
81
92
Definition 2.1 (Reconfigurable system AAG04 GP07]). A reconfigurable system on a graph with of labels A consists of a set of generators together with set of states closed under the action of admissible generators.
94
Configurations and their reconfigurations be used construct state graph (or transition graph), which represents all possible states and transitions between these states in a reconfigurable system. More formally:
96
Definition 2.2 (State graph). The state graph S()) associated reconfigurable system has as its vertices the set of all states, with edges connecting pairs of states differing by single generator.
96
99
100
Let us now return our attention to gridworlds. define graph to have vertices corresponding to the cells of 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 chosen to be
102
A { ''gent', 'object', 'floor'
103
We do not distinguish between multiple instances of the same label. We consider two generators:
104
Push/Pull. 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.
106
107
These two generators have the effect of enabling agents 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
108
109 any configuration if there is sufficient room to move. For both types of generators, the trace coincides with the support. For the Push/Pull generator, the support is a row or column of three contiguous cells, whereas for the Move generator, the support a pair of neighbouring cells. simple example of state graph, together with the local states for the two generator types, is shown in Figure [
111
Push/Pull
Move
Figure 2: An example 5 gridworld with one agent and one object with two generators - Push/Pull and Move and the resulting state graph. In the state graph, edge colours indicate the generator type which relabels the gridworld.
In typical reconfigurable system, there may be many admissible generators at given state If the 114 trace of admissible generator di is disjoint from the support of another admissible generator d2, then d2 remains admissible at Φ1 [s]. This is because the relabelling by Φi does not interfere with

---

116
Sag 14). If (ø1...., 2n) is a set of commuting admissible generators at state then there are 2n states that can be obtained by applying any subset of these generators to s. These 2n states form the vertices of an n-cube the labels on (U2() More generally, a set of admissible generators fØi...., 9n at state commutts if (U,
117
1 for all i * j. When this holds, these generators can be applied independently of one another, and the resulting state does not depend on the order in which they are applied. A simple example of this in the context of gridworlds large room with n. agents spread sufficiently far apart to allow for independent simultaneous movement.
118
119
120
121
Abrams, Ghrist & Peterson represent this mutual commutativity by adding higher dimensional cubes to the state graph to form cube com- plex called the state complex. We give an infor- mal definition here, and refer their papers for the precise formulation [AG04 GPO7]. Further background on cube complexes can be found in 1
122
123
124
125
128
127
128
129
131
133 in the state complex. Each n n-cube is bounded by 2n faces, where each face is an (n l)-cube: by disallowing a generator di, we obtain a pair of faces corresponding to those states (in the given n-cube) that agree with one of the two respective local states of Φ; on SU P(.:).
Figure 3: State complex of a 2 x 2 gridworld with two agents. Shading indicates squares attached to the surrounding 4-cycles.
135
137
138
Definition 2.3 (State complex). The state complex S of a reconfigurable system is the cube complex constructed from the state graph (()) by inductively adding cubes as follows: whenever there is 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 cubes obtained by disallowing a generator. particular, every cube is uniquely determined by its vertices.
140
141
143
145
In our gridworlds setting, each generator involves exactly one agent. This means commuting generators can only occur if there multiple agents. A simple example of state complex for two agents in 2 x 2 room is shown in Figure 3 Note that there are six embedded 4-cycles in the state graph, however, only two of these are filled in by squares: these correspond to independent movements of the agents, either both horizontally or both vertically.
146
147
148
149
150
3
Exploring gridworlds with state complexes
151
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 chosen state of the gridworld to form the first vertex of g and also the first entry on L. The state complex is computed according to a breadth-first search by repeatedly applying the following:
152
153
154
Let v be the first entry on L. List all admissible generators at v. For each such generator di
If ø(v] already appears vertex of G, add an edge between v and Φ[v] (if it does not already exist).
157
158
If Φ(v) does not appear in G, add it as a new vertex to g and add an edge connecting it to u. Append ø[u] the end of L.
159
160
Remove from L.
161
The process terminates when C is empty. The output is the graph G. When L is 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 disconnected, in which case the above algorithm will only return a connected component G. For our purposes, we shall limit our study to systems with connected state graphs. From the state graph, we construct the state complex by first finding all 4-cycles in the state graph. Then, by examining the states involved, we can determine whether given 4-cycle bounds square representing pair of commuting moves.
162
163
164
165
186

---

188
possible To visualise the state complex, we first draw the state graph using the Kawada-Kawai force-directed algorithm [KK99] which attempts to draw edges have similar length. We then shade the region(s) enclosed by 4 4-cycles representing commuting moves. For ease of visual interpretation in our figures, we not also shade higher-dimensional cubes, although such cubes are noticeable and can be easily computed and visualised if desired.
189
171
172
173
Constructing and analysing state com- plexes of gridworlds is in and of itself an in- teresting and useful way of exploring their intrinsic geometry. For example. Figure 4
174
175
178
177
shows the state complex of 3 3 grid- world with one agent and one object. The
178
179
state complex reveals two scales of geom- etry: larger 'blobs' of states organised in a
181
grid, representing the location of the object; and, within each blob, copies of the room's remaining empty space, which the agent may walk around and ap- proach the object to Push/Pull. Each 12- cycle 'petal' represents 12 step choreog- raphy wherein the agent pushes and pulls the object around in 4-cycle in the grid- world. In this example, the state complex is the state graph, since there commuting moves.
185
185
Figure 4: State complex (left) of 3 x 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 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.
187
189
191
The examples discussed thus far all have planar state graphs. Planarity does not hold in general indeed, the n-cube graph for
193
195
n 2 4 non-planar, and a state graph can contain c-cuues if the gridworld has n agents and sufficient space move around. It is tempting to think that the state complex of gridworld with more agents should therefore look quite different to one with fewer agents. However, Figure [3 shows this may not always be the case: there symmetry induced by swapping all 'agent' labels with 'florr'
197
199
labels.
Figure 5: State complex (centre) of 3 x gridworld with three agents (left) and six agents (right). They share the same state complex due to the 'agent" <> 'floor" label inversion symmetry.
4
Dancing with myself
200
201
The state complex of gridworld with n agents can be thought of as a discrete analogue of the configuration space of points the 2D-plane. However, there is problem with this analogy: there can be 'holes' created by 4-cycles in the state complex where single agent walks in a small equare-shaper dance by itself, shown in Figure
203
205
The presence of these holes would suggest something meaningful about the underlying gridworld's intrinsic topology, e.g., something obstructing the agent's movement at that location in the gridworld
207
that the agent must move around. In reality, environment essentially (discretised) 2D-plane with nothing blocking the agent from traversing those locations. Indeed, these 'holes' are uninteresting
5

---

Figure 6: State complex of a 2 x 2 gridworld with agent under the original definition of Abrams, Ghrist & Peterson [AG44 GP07 (left) and with our modification (right). The blue shading is a filled in square indicating dance.
209
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 AG04 GP07 and choose to fill in these 'dance' 4-cycles with squares
Formally, define dance 8 comprise the following data:
213
the support SU P()) given by a 2 x 2 subgrid in the gridworld,
214
four local states defined on SU P()), each consisting of exactly one agent label and three floor labels, and
215
216
four Move generators, each which transitions between two of the four local states (as in Figure 6).
218
We say that 8 is admissible at a state s if s P()) agrees with one of the four local states of d. Moreover, these four local states are precisely the states that be reached when we apply some combination of the four constituent Moves. We do not define the trace of dance, however, we may view the trace of each of the four constituent Moves as subgraphs of PU)(
219
220
221
222
The notion of commutativity can be extended incorporate dancing. Suppose that we have a set .1,...,, 5m of admissible generators and admissible dances at state We say ti, {
224
that this set commutes the supports of its elements are pairwise disjoint. When this holds, there 2 possible states that be obtained by applying some combination of the generators and dances to s: there are two choices of local state for each Φi, and four for each ōj. We capture this extended notion of commutativity by attaching additional cubes to the state complex form our modified state complex.
226
227
228
229
Definition 4.1 (Modified state complex). The modified state complex S' of gridworld is the cube complex obtained by filling in the state graph S(1) with higher dimensional cubes whenever there set of commuting moves dances. Specifically, whenever set of 2 + states related by a commuting set of generators and m dances, we add an n-cube having the given set of states + 2m. Each of the 2n. faces of such n-cube is identified with an n cu-e obtained by either disallowing a generator Φ; and choosing one of its two local states, or replacing dance dj with one of its four constituent Moves.
230
232
its vertices, where
234
235
236
Our modification removes uninteresting topology. This can be observed by examining 4-cycles in S'. the one hand, some 4-cycles are trivial (they can be 'filled in'): wiite--------yyyself 4-cycles, and commuting moves (two agents moving back and forth) 4-cycles (which were trivial under the original definition). These represent trivial movements of agents relative to one another. the other hand, there is non-trivial 4-cycle in the state complex for two agents in x 2 room, can be in the centre of Figure (here, no dancing is possible so the modified state complex the same as the original). This 4-cycle represents the two agents moving half 'revolution' relative one another
237
239
241
Ghrist and Peterson themselves ask if there could be better ways to complete the state graph to a higher- dimensional object with better properties (Question 6.4 in [GP77).

---

243
indeed, performing this twice would give full revolution. (There are three other non- non-trivial 4 cyccles,, topologically equivalent this central one, that also achieve the half-revolution.)
244
245
In a more topological sense 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
247
to study the braiding or mixing of agents, and also allows us to consider path-homotopic paths as eessentially' the same. One immediate difference this creates with the original state complexes is loss of symmetries like those shown in Figure since there is no label inversion for a dance when
248
249
250
other agents are crowding the flnce-floor.
Gromov's Link Condition
251
252
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
254
255
geometry is no longer guaranteed we test. for this on a vertex-by fetex-by-vertee by-vertex basis using classical geometric result due to Gromov (see also Theorem 5.20 of [B999 and [Sag14))
256
257
Theorem 5.1 (Gromov's Link Condition [rro87), finie-ddmensional cube complex is NPC if and only if the link of every vertex is a flag simplicial complex.
258
U
259 We provide a brief mathematical back- ground cube complexes and the finer details of Gromov's Link Condition in Ap- pendix A. For current purposes, sufficient to know that under the Abrams,
261
262
263
264
Ghrist & Peterson setup, if is state in S
Φ
285
then the vertices of its link (k(v)) represent the possible admissible generators at v.
42
6
286
257
Since cubes in S are associated with com-
268
muting sets of generators, each simplex in Ik(v) represents set of commuting gener- ators. Gromov's Link Condition for (k) can be reinterpreted as follows: whenever a set of admissible generators pairwise commutative, then it is setwise commuta- tive. Using this, it is straightforward for Abrams, Ghrist & Peterson to verify that this always holds for their state complexes (see Theorem 4.4 of [GP07)).
269
270
6
5,
272
4
Φ
2
274
276
Figure 7: The two situations which lead to failure of Gro- mov's Link Condition in multi-agent gridworlds. Maroon arrows indicate admissible moves and blue squares indi- cate admissible dances. Note that in the links (bottom row), the triangle is missing in the left example, while the (solid) tetrahedron is missing in the right (however, all 2D faces are present). This is due to the respective collections of moves and dances failing commute an agent interrupts the other's 's dance (left) or two dances collide (right).
278
For our modified states complexes, the sit- uation is not as straightforward. The key issue is that our cubes do not only arise from commuting generators we must take dances into account. Indeed, when attempting to prove that Gromov's 's Link Condition holds, we discovered some very simple gridworlds where it actually fails; see Figure and Appendix A.4.
279
280
282
284
286
Failure of the Link Condition can indicate 287
288
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 something akin to what real-time computer strategy games call 'fog war' (distance-dependent limiting of observations which extends from the player-controlled agents), and more specifically the viewable distance from an agent's 's line-of-sight. Such fog makes Al systems operating in such environments particularly challenging, although remarkable success has been achieved in games like
290
252
294
StarCraft fVBC+ 19
By considering the fundamental group.
7

---

295
Despite this apparent drawback, we nevertheless show that Figure 7 accounts for all the possible failures of Gromov's Link Condition in the setting of agent-only gridworld
296
297
Theorem 5.2 (Gromov's ' Link Condition in the modified state complex), Ler v be a vertex in the modified state complex S' of an agent-only gridworld. Then
298
299
Uk(e) satisfies Gromov's 's Link Condition if and only if it has no empty simiplices nor 3 simplice and
300
if [k<()) fails Gromov's Link Condition then there exist a pair of agents whose positions differ by either a knight move or a 2-step bishop move (as in Figure 7.
302
303
We provide a proof in Appendix A.2. Consequently, if the Link Condition fails at all, it must fail at dimension or This can be interpreted as saying that we only need a bounded amount of foresight to detect potential collisions: under fog-of-war, each agent needs line-of-sight of only four moves.
304
306
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 be filled in. Doing this in 'natural' way is in itself a non-trivial task, and is the subject of further investigation.
307
308
309
310
6
Experiments and applications
Although our main contribution is theoretical, we conduct some small initial experiments to demon- strate the type of information which can be captured in the geometry and topology (see Appendix A.4). To run these experiments, we developed and used custom wython-based tool (detailed in Appendix A.3). Our focus on small rooms is largely expository, i.c., they are the simplest non-trine trivirivill examples illustrating the key features we want to isolate, and naturally reoccur in all larger rooms. Our intention is also to demonstrate a combinatorial explosion in the number of states. We don't ' recommend constructing the entire state complex in practical applications (indeed, to implement addition of integers on a computer, it is infeasible and unnecessary to construct all integers).
312
314
316
318
Remark 6.1. By simple counting argument, one can deduce the total number of states in gridworld. For an agent-only gridworld with n cells and agents, there is total of (x) states. If there are n cells, k agents, and j objects, then there are (x) (""=") states. Thus, even for a moderately sized
320
321
10 X 10 room with 50 agents, there are (100) = 1.008 x 1029 vertices in the state complex.
322
By Theorem 5.2 checking if (k(r) satisfies Gromov's 's Link Condition requires computing the link only up to dimension and then checking whether is a flag complex; if not, we count the number of empty simplices. Checking this for given vertex in the state complex is not too computationally demanding, however when a state complex has many vertices it becomes more difficult. In practical applications, such calculating collision-avoidin avoiding navigation routes, it is again, by Theorem 5.2 only necessary to construct a small local subcomplex. But perhaps even more importantly, to
324
326
328
detect potential collisions between agents, it is not even necessary to construct Ik(u), since Theorem provides a computational shortcut: just check for supports of knight or two-step bishop moves between agents.
330
332 By using Gromov's Link Condition, we can identify a precise measure of how far ahead agents ought to look in order to safely proceed without fear of collisions. Appendix A.4 gives a summary analysis 334 of a 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 as previously illustrated in Figure 5). However, curiously, the number of dances has a symmetry about 3.5 agents. This difference leads to the asymmetrical distribution of positive curvature and failures of Gromov's Link Condition which, while maximal for 3 agents as a proportion of total states, exhibited the highest mean failure rate for 4 agents.
336
338
339
'Wiile writing this paper, the first author was involved in two scooter accidents collisions involving only agents (luckily without serious injury). So, while this class of gridworlds is strictly smaller than those also involving objects or other labels, is by no means an unimportant one. If only the scooters had Gromov's Link Condition checkers!
In other words, if there "hollow" triangles or tetrahedra like those in Figure 7
8

---

340
This shows that, heuristically, we expect most states to satisfy NPC (see Appendix A.4), and so existing greedy algorithms [AOS12] for calculating geodesies will work well in most situations. However, to implement an efficient, collision-free path-finding algorithm in our modified state complexes, we need add an additional check. Specifically, when we are near potentially dangerous state, we should implement predefined 'detour' to avoid the collision, which can be done on a local basis using the identified supports which lead to positive curvature (as in Figure 77)
341
342
343
344
345
7
Conclusions and future directions
346
347
This study presents novel upplications 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 a task space serendipitously embeds safety information and makes it possible to determine how far ahead in time Al system needs to observe to be guaranteed of avoiding dangerous actions.
349
350
351
352
Leike et al. [LMK 17] show deep reinforcement learning agents cannot solve many AI safety prob- lems specified on gridworlds, e.g., minimising unwanted side-effects or ensuring robustness to agent eelf-modification. Having described the agent-only case in this study, there is now ripe opportunity to account for positive curvature or other geometric features arising due to other labels or generators (actions) present in specified AI safety problems, e.g., agents pushing/pulling objects, pressing buttons, modifying their form or behaviour, rewards//umishments, opening/unlocking doors, etc.. By considering directed modified state complexes, irreversible actions can be captured by "invariant subcomplexes" (i.e., you can't It escape from them), allowing geometric study of the tree/flowchart of irreveriille actions and related recurrencerransience. Braiding can be used to study route planning, back- trackkng. cooperation, assembly, and topological entropy in congestion [Ghr09]. Numerous extensions are possible, allowing us to study and geometrically represent further problems with a
353
355
357
359
360
361
362
363
view to developing efficient, geometricalll-insiiee. local algorithms without the need for training.
364
Do learning algorithms already implement such coometrically-insiiee algorithms, the related ge- ometry, or approximations thercof? To find out, we are investigating how modified state complexes map to learned internal representations of neural networks trained to predict multi-agent gridworld dynamics. This mapping connects the geometry and topology of a task space directly to optimisation procedures and learning trajectories in latent representation spaces, highlighting unexpected topologi-
385
367
368
369
cal and geometric differences and opportunities for deeper insight and improvement of optimisation procedures, in the spirit of 2NL ZZ22]. We can also compare biological optimisation processes and internal representations of allocentric and egocentric navigation [Bur06] GHP* 22), and how this interacts with the position of other agents DDIS SB20
370
371
372
373
From a more mathematical perspective, state complexes of gridworlds give rise to an interesting class of geometric spaces. It would be worthwhile to investigate their geometric and topological properties to more dceply understand various aspects of multi-agent gridworlds. For example, for a gridworld with agents in sufficiently large room, we hypothesise that the modified state complex should be a classifying space for the stsraand braid group. This is clearly false when the room is packed full of agents (in which case the state complex is single point), it may be fruitful to determine if there is some 'critical' density at which a topological transition occurs.
375
377
378
379
Using the failure of Gromov's 's Link Condition in an 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. To our knowledge, the only other works which go against this trend are [AG04], in which failure detects global disconnection of a metamorphic system, and [BDTI9) 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.
381
383
385
386 A limitation of our work is that we have so far only explored very simple AI environments. Further work is needed to expand the framework and results to more general, sophisticated, and real-world environments. For this reason, although our work provides new geometric perspectives, data, and potential algorithms for an important AI safety issue, we caution against hasty real-world implementation of the main results. To avoid potential negative societal impacts, it would still be important to perform rigorous checks and tests in application domains, since our results do not directly extend to situations beyond which the stated assumptions hold.
387
388
389
391
9

---

References
393
394
[ABCG17]
Federico Ardila, Hanner Bastidas, Cesar Ceballos, and John Guo, The configuration space of a robotic arm in tunnel, SIAM Journal on Discrete Mathematics 31 (2017), no. 4, 2675-2702,
385
396
[ABY14]
Federico Ardila, Tia Baker, and Rika Yatchak, Moving robots efficiently using the combinatorics of CAT(O) cubical complexes, SIAM Journal on Discrete Mathematics 28 (2014), no. 2. 986- 1007.
397
398
[AG04]
Aaron Abrams and Robert Ghrist. State complexes for metamorphic robots, The International Journal of Robotics Research 23 (2004), no. 7-8, 811-826.
400
401
[AOS12]
Federico Ardila, Mcgan Owen, and Seth Sullivant, Geodesics in CAT(O) cubical complexes, Adv. in Appl. Math. 48 (2012), no. 1, 142-163.
402
403
[AVBP21]
Karen Archer, Nicola Catenacei Volpi. Franziska Bröker, and Daniel Polani, space of goals: the cognitive geometry of informationally bounded o (ar
404
2021.
[BDT19]
Mark C. Bell, Valentina Disarlo, and Robert Tang, Cubical geometry in the polygonalisation complex, Math. Proc. Cambridge Philos. Soc. 167 (2019), no. 1-22.
406
407
[BH19]]
Martin R. Bridson and André Haefliger, Metric spaces of non-positive curvature, Grundlehren der mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences), vol. 319, Springer- Verlag, Berlin, 1999.
408
410
[Bur06]
Neil Burgess, Spatial memory: how egocentric and allocentric combine, Trends in Cognitive Sciences 10 (2006), no. 12, 551-557.
411
[CNO5]
Indira Chatterji and Graham Niblo, From wall spaces CAT(O) cube complexex, International Journal of Algebra and Computation 15 (2005), no. 05n06, 875-80 $75-885.
413
[DJ18]
É. Duvelle and K.J. Jeffery, Social spaces: Place cells represent the locations of others, Current Biology 28 (2018), no. R271-R273.
415
416
[DSHLKT20]
Felipe Leno Da Silva, Pablo Hernandez-L.cal Bilal Kartal, and Matthew F. Taylor, Uncertainty- aware action advising for deep reinforcement learning agents, Proceedings of the AAAI Confer- ence on Artificial Intelligence 34 (2020), no. 04, 5792-5799.
417
419
[FLLP20]
Tingxiang Fan, Pinxin Long. Wenxi Liu, and Jia Pan, Distributed multi-robot collision avoidance via deep reinforcement learning for navigation in complex scenarios, The International Journal of Robotics Research 39 (2020), no. 7, 856-892.
420
422
22
Richard J. Gardner, Erik Hermansen, Marius Pachitariu, Yoram Burak, Nils A. Baas, Benjamin Dunn, May-Britt Moser, and Edvard I. Moser, Torvidal topology of population activity in grid cells, Nature 602 (2022), no. 7895, 123-128.
423
424
425
[Ghr09]
Robert Ghrist, Configuration spaces, braids, and robotics, pp. 263-304, World Scientific Pub- lishing, 2009.
426
427
[GP07]
R. Ghrist and V. Peterson, The geometry and topology of reconfiguration. Advances in Applied Mathematics 38 (2007), 3, 302-323.
429
[rr887]
M. Gromov, Hyperbolic groups, Essays in Group Theory (S. M. Gersten, ed.), Springer New York, New York, NY, 1987, pp. 75-263.
430
[HHA21]
Victoria J. Hodge, Richard Hawkins, and Rob Alexander, Deep reinforcement learning for drone navigation using sensor data, Neural Computing and Applications 33 (2021), no. 2015-2033.
432
433
[HR17]
Michacl Hauser and Asok Ray, Principles of Riemannian geometry in neural networks, Advances in Neural Information Processing Systems (I. Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett, eds.), vol. 30, Curran Associates, Inc., 2017.
436
[KAP20]
Ivana Kajic, Eser Aygun, and Doina Precup, Learning to cooperate: Emergent communication in multi-agen navigation, 42nd Annual Virtual Meeting of the Cognitive Science Society (CogSci 2020). 2020.
437
439
[KFGE19]
Zac Kenton, Angelos Filos, Yarin Gal, and Owain Evans, Generalizing from a few environments in safety-critical reinforcement learning. Safe Machine Learning workshop at ICLR (2019), 1-9. Takeshi Kano, Mayuko Iwamoto, and Daishin Ueyama, Decentralised control of multiple mobile agents for quick, smooth, and safe movement, Physica A: Statistical Mechanics and its Applications 572 (2021), 125898.
440
[KIU21]
442
443
[KK89]
Tomihisa Kamada and Satoru Kawai, An algorithm for drawing general undirected graphs, Information Processing Letters 31 (1989), 1, 7-15.
446
[LAG + 20
Na Lei, Dongsheng An, Yang Guo, Kehua Su, Shixia Liu, Zhongxuan Luo, Shing Tung Yau. and Xianfeng Gu, A geometric understanding of deep learning, Engineering 6 (2020), no. 3. 361-374.
447
10

---

449
[LMK 17]
Jan Leike, Miljan Martic, Victoria Krakovna, Pedro A. Ortega, Tom Everitt, Andrew Lefrancq. Laurent Orseau, and Shane Legg, Al safety gridworlds, arXivv11111.088) 2017.
451
[LR10]
Tom Larkworthy and Subramanian Ramamoorthy, An efficcennt algorithm for self-reconfiguration planning in a modular robot, 2010 IEEE International Conference on Robotics and Automation, 2010, pp. 5139-5133 5146.
452
454
21J
Florian Laurent, Manuel Schneider, Christian Scheller, Jeremy Watson, Jiaoyang Li, Zhe Chen, Yi Zheng, Shao-Hung Chan, Konstantin Makhnev, Oleg Svidchenko, Vladimir Egorov, Dmitry Ivanow, Alcksei Shpilman, Evgenija Spirovska, Oliver Tanevski, Aleksandar Nikov, Ramon Grunder, David Galevski, Jakov Mitrovski, and Sharada Mohanty, Flarland competition 2020: MAPF and MARL for efficient train coordination on a grid world, pp. 275-301, PMLR, 08 2021.
455
457
458
459
[NZL20]]
Gregory Naitzat, Andrey Zhitnikov, and Lek-Heng Lim, Topology of deep neural networks, Journal of Machine Learning Research 21 (2020), no. 184, 1-40.
460
461
IQZC 21]
Zengyi Qin, Kaiqing Zhang, Yuxiao Chen, Jingkai Chen, and Chuchu Fan, Learning safe multi- agent control with decentralized neural burrier certificates, International Conference on Learning Representations, 2021.
482
464
[Sag14]
Michah Sageev, CO cube complexes and groups, Geometric group theory, IAS/Park City Math. Ser., vol. 21, Amer. Math. Soc., Providence, RI, 2014, pp. 7 7-54.
485
468
[SB20]
Christina Sutherland and David K. Bilkey, Hippocampal coding of conspecific position, Brain Research 1745 (2020), 146920.
467
[SMKI1]
Jeremy Stober, Risto Miikkulainen, and Benjamin Kuipers, Learning geometry from sensorimotor experience, 2011 IEEE International Conference on Development and Learning (ICDL), vol. 201 pp. 1-6.
489
470
[S]
Cory Stephenson, Suchismita Padhy, Abhinav Ganesh, Yue Hui, Hanlin Tang, and Yeon Chung. On the geometry of generalization and memorization deep neural networks, Interna- tional Conference on Learning Representations, 2021.
473
[VBC* 19]
Oriol Vinyals, Igor Babuschkin, Wojeiech M Czamecki, Michaël Mathieu, Andrew Dudzik, Junyoung Chung. David I Choi, Richard Powell, Timo Ewalds, Petko Georgiev. Junhyuk Oh, Dan Horgan, Manuel Kroiss, Ivo Danihelka, Aja Huang. Laurent Sifre, Trevor Cai, John Agapiou, Max Jaderberg, Alexander S Vezhnevets, Rémi Leblond, Tobias Pohlen, Valentin Dalibard, David Budden, Yury Sulsky, James Molloy, Tom L Paine, 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 1l using multi-agent reinforcement learning. Nature 575 (2019), no. 7782, 350-354.
478
477
478
480
481
482
[Wis12]
Daniel T. Wise, From riches to raags: 3-manifolds, right-angled Artin groups, and cubical geom- eiry, CBMS Regional Conference Series Mathematics, vol. 117, Published for the Conference Board of the Mathematical Sciences, Washington, DC; by the American Mathematical Society, Providence, RI, 2012.
484
485
486
487
[WKK20]
Vikram Waradpande, Daniel Kudenko, and Megha Khosla, Deep reinforcement learning with graph-basee state representations, |arXiv22004.3366 13965 2020.
488
[ZZ22]
Yang Zhao and Hao Zhang. Quantitative performance assessment CNN units via topological entropy calculation, International Conference on Learning Representations, 2022.
490

---

Checklist
482
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
494
contributions and scope? [Yes]
485
(b) Did you descrihe the limitations of your work? [Yes]
496
(c) Did you discuss any potential negative societal impacts of your work? [Yes]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
498
499
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
501
(b) Did you include complete proofs of all theoretical results? [Yes] see Appendix A.2
3. If you experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as a URL)? [Yes] and we will provide a link to the publicly-hoster code for community usage upon acceptance (see Appendix A.3)
504
506
507
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [N/A]
508
509
(c) Did you report error bars (e.g., with respect the random seed after running experi- ments multiple times)? [N/A]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes] see Appendix A.3
512
513
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
514
(a) your work uses existing assets, did you eite the creators? [N/A]
515
(b) Did you mention the license of the assets? [N/A]
516
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
518
(d) Did you discuss whether and how consent was obtained from people whose data you're you're using/curating? [N/A]
519
(c) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
521
522
5. If you used crowdsoureing or conducted research with human subjects...
(a) Did you include the full text of instructions given participants and screenshots, if applicable? [N/A]
824
525
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
526
527
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
12


Reviews:
[{"review_id": "cvWg65rCebk", "reviewer": "Reviewer_txoD", "summary": "This paper considers gridworlds, 2D grids where cells are occupied by objects that can either move around the grid themselves or be moved by other objects. The authors use state complexes to analyse multi-agent gridworlds, and find that they are not always non-positively curved by determining if Gromov's Link Condition is satisfied or not. The condition fails in situations where two agents might collide with each other, thus the condition can be used as a test for safety in the gridworld. They find that agents separated by either a knight or 2-step bishop move could collide, and interpret this as saying that agents only need to know what other agents are doing 4 steps in advance to avoid potential collisions.", "questions": "(1) What does it mean for a square in the state complex to be \"filled in\", and why is this beneficial? (see \"strengths and weaknesses\" section for more detail)\n\n(2) The authors acknowledge that constructing the entire state complex of large gridworlds is computationally intractable, so I wonder about how this work could be applied to other areas, as discussed in the Conclusions. Gridworlds seem like a very simple environment to apply these geometric methods to, and you already find that state complexes become too large to work with for even moderately sized environments. How do you think other problems could be tackled, given how computationally expensive the simple environments in this paper are to analyse?", "limitations": "I believe limitations have mostly been acknowledged, but have asked for a little more information in question (2).", "rating": 4, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The main contribution and strength of this paper is in its theoretical developments. A mathematical result is derived in detail, and verified by simulation as well. While the end result (knight and 2-step bishop separations are potentially dangerous, and a 4 step line of sight is sufficient) is not groundbreaking, the methods the authors use to reach these conclusions are interesting and could be applied to other scenarios, as mentioned in the Conclusions.\n\nWhile I am not an expert in this area, I feel the authors mostly did a good job of explaining the concepts with clear diagrams, so I could gain a good general understanding of the work. However, I'm somewhat confused by what the modification in Section 4 achieves. What effect does \"filling in\" the holes in the state complex brought about by dances have? I think I'm probably missing what it means for a square to be \"filled in\", so can this be explained better? Given Sections 2 and 3 seem to basically summarise the work of Abrams, Ghrist, and Peterson whereas Section 4 is the new contribution of this paper, perhaps Sections 2 and 3 could be shortened to allow more space to discuss Section 4.\n\nI found Figure 7 hard to understand initially. It would be beneficial to include a diagram of the state complex to show how the links come about (similar to Figure 8 in Appendix A1). I also don't quite understand what is meant by \"the triangle is missing in the left example\", as this shows a triangle but with one of the edges in blue instead of red. This relates back to my previous point about what \"filled in\" squares actually mean: I guess you're trying to point out that the triangle is not filled in. Perhaps you could include an example of a situation in which Gromov's Link Condition *does* hold, in order to better illustrate the differences.\n\nFinally, there are a few examples of informal language that should be removed in any published version of this work. For example, page 2 \"dropbears\" or footnote 3 on page 8.\n\nFollowing the rebuttal, the score has been adjusted to take into account all comments by the authors and reviewers.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "cOa9JzAVSw0", "reviewer": "Reviewer_5vs3", "summary": "The paper studies the geometry of the state space specific to 2-dimensional grid-world environments. The methods provide a way of identifying unsafe states in discrete environments. ", "questions": "See above. ", "limitations": "See above. ", "rating": 3, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Although the study of geometric structures of state complexes is interesting, it is hard to see the computational benefits of doing so. In particular, it is hard for me to see where the geometry of state transitions can help with learning beyond standard RL. In particular, the identification of unsafe states by observing transitions between states can be exactly captured by Q-learning, which propagates values to implicitly identify the geometry of the state complexes. \n\nThe experiments have not attempted to compare with any RL baselines, while the complexities of Q-learning or value iteration can be directly analyzed in the simple gridworld setting. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "-5K67TrJGMH", "reviewer": "Reviewer_2SSW", "summary": "This paper advocates for the use of group theory to characterize geometric features of grid worlds. The paper claims these geometric features reflect information about obstructions that can ultimately be used to check for collisions. The paper develops its ideas through an extension of state complexes, then formally argues that preconditions for a special geometric property (Gromov’s Link Condition) are not satisfied when some geometric features are present.  \n\nUnderstanding how domain geometry constrains the agency of a decision maker is an ambitious and potentially interesting line of research. However, the current paper has not done enough in this regard to be published, as it fails to communicate how its ideas can be operationalized in AI research. The paper's poor organization is one of its major issues, as is its largely unsubstantiated claims and unconvincing empirical remarks. All taken together, the paper needs more work to achieve the goals it sets for itself. I believe that with a major overhaul this could eventually become an interesting line of research.  ", "questions": "* Consider that AI systems are often used in settings when the full state space topology is unknown. Do you see these ideas being relevant in the absence of that information?\n* What is the difference between a state complex and the configuration space used in robotics [(LaVelle, 2006)](http://lavalle.pl/planning/node144.html)?\n", "limitations": "### Significance\n\nThe paper centers around the claim that its ideas help with collision checking. However, the notion of collisions here is totally different than the way others conceptualize collisions. The paper seems to view collisions as something gives a state space its inherent topology, even in settings where the topology is just a product of discretization. So even in an empty space, the paper assumes an obstacle prevents the agent from moving diagonally between a four-action topology. This seems strange, and its not obvious this abstraction buys an AI researcher additional insight into the domain. \n\nComputing the objects needed to perform the collision checking seems computationally intractable, even for small domains. The paper even mentions in Remark 6.1 computing a state complex for a 10x10 grid world and multiple agents requires on the order of $10^29$ states. With such a combinatorial demand for resources, it's not clear these ideas could be used by practical resource-constrained computing systems.  \n\n### Clarity \n\nThis paper failed to communicate to its target audience. In the introduction, several key technical concepts are discussed without definition or sufficient context. One example is non-positively curved systems. Another is Gromov's Link Condition---an esoteric mathematical concept. If the authors want to see the adoption of these ideas in AI, then they need to recognize that average members of this audience will be unfamiliar with these concepts and require some motivation.\n\nInstead of aiming at the entire AI community that uses grid worlds, it could be better to reorient this work toward a specific community, such as algorithmic game theory, reinforcement learning, or robotics. Ask how could these communities use your geometric characterization to enhance, simplify, or better understand their own algorithms. Right now it is not clear what anyone can do with this.\n\nThe paper claims it \"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.\" However, this paper has little to do with deep learning. And furthermore, deep learning methods are usually applied in much more complex environments with many states.\n\nMany concepts are precisely defined while others are vague. One example comes from the claim that determining collisions with this approach applies to multiple kinds of actions: \"actions and inter-actions.\" It is unclear what an inter-action is in a grid world. Typically actions are represented as edges in the graph. Another example is \"fog-of-war\", which seems to relate to some notion of partial observability---a concept which seems unrelated to the paper's narrative around geometry and collision checking.\n\n### Empirical Study\n\nSimply put, there is no empirical study. Though I believe the paper could have designed small-scale experiments to demonstrate the utility of its geometric domain characterization. Consider experiments that support claims about collision checking properties in relation to existing collision checking algorithms. \n\n### Potential Related Work\n\nConsider how this work could be connected with prior work in robotics. For instance, Robert Ghrist had some work with Subrajit Bhattacharya on topological motion planning, which used knowledge of homotopy classes to perform efficient optimal planning. Work from this same group includes Jason Derenick, who uses simplicial approximation algorithms to efficiently solve common robot map building problems.", "rating": 2, "confidence": 3, "soundness": 2, "presentation": 1, "contribution": 1, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "### Strengths \n* The presented mathematical ideas are potentially novel to AI.\n* Collision checking is used in several areas of AI, and new insights could be impactful. \n* Many potential connections to areas of AI research.\n \n\n### Weaknesses\n* Significance unclear and limited. Though the paper's goal was to introduce novel mathematical ideas to AI, it's not clear that this addresses a specific problem of significance.\n* Empirical study is severely incomplete. The paper has an \"Experiments and applications\" section containing no experiments: no description of methodology, empirical research questions, or results.\n* Poorly organized and unclear writing. The paper does not effectively communicate ideas to its intended target audience.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Reject