Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 2: Strong Reject: For instance, a paper with major technical flaws, and/or poor evaluation, limited impact, poor reproducibility and mostly unaddressed ethical considerations.
review_content: 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.  

Understanding 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.  
strengths_and_weaknesses: ### Strengths 
* The presented mathematical ideas are potentially novel to AI.
* Collision checking is used in several areas of AI, and new insights could be impactful. 
* Many potential connections to areas of AI research.
 

### Weaknesses
* 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.
* 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.
* Poorly organized and unclear writing. The paper does not effectively communicate ideas to its intended target audience.
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?
* What is the difference between a state complex and the configuration space used in robotics [(LaVelle, 2006)](http://lavalle.pl/planning/node144.html)?

limitations: ### Significance

The 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. 

Computing 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.  

### Clarity 

This 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.

Instead 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.

The 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.

Many 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.

### Empirical Study

Simply 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. 

### Potential Related Work

Consider 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.
review_title: null

final_score: rating: 4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.
review_content: 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.
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.

While 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.

I 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.

Finally, 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.

Following the rebuttal, the score has been adjusted to take into account all comments by the authors and reviewers.
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)

(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).
review_title: null

final_score: rating: 3: Reject: For instance, a paper with technical flaws, weak evaluation, inadequate reproducibility and incompletely addressed ethical considerations.
review_content: 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. 
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. 

The 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. 
questions: See above. 
limitations: See above.
review_title: null

Meta-review: metareview: This paper analyses grid worlds, more precisely multiple objects moving in grid worlds, using the mathematical idea of state complexes.  The state complex represents all possible configurations as a single space, from which domain properties can be ascertained by group-theoretic, combinatorial, or geometric analysis.  In particular, the paper develops a theory around "Gromov's Link Condition" to analyze conditions under which collisions can be prevented in such domains.

The reviewers had a mixed initial response to this paper.  On the positive side, the reviewers appreciated the theoretical development (txoD) and novelty (2SSW).  On the negative side, the reviewers struggled to see the significance or relevance of the work to learning or AI (2SSW, 5vs3).  The reviewers understood the work as a mechanism for collision checking (2SSW), a means to support learning (5vs3), and a computational mechanism for analyzing gridworld dynamics (txoD).  The author response clarified several aspects of the reviews that were misunderstood.  The author response did not sway the reviewers.  Primarily, the concern is that the paper failed to communicate the relevance of the mathematical analysis of gridworlds to an AI audience.  The sole positive reviewer ultimately concurred with the arguments made by the negative reviewers.  

Two reviewers indicate to reject, and one indicates a weak accept.  Based on the failure of the paper to clearly communicate the relevance of its ideas to any reviewer, the paper is rejected.  One suggestion for a future revision would be to present these ideas in the general setting of an MDP (instead of a specific domain of a gridworld).  The local combinatorial analysis on a generic MDP could potentially be more useful to the MDP community when considering planning for AI safety or problems of mechanism design.  The evidence needed to validate the ideas for those communities might again be different from the evidence provided in this paper.  As a separate comment, the analysis of the transition dynamics of actions may have related work stemming from predictive state representations.  In the paper's current form, the reviewers were unable to see a clear contribution.
confidence: Certain
Decision: Reject