# Detecting danger in gridworlds using Gromov's Link Condition

arXiv: https://arxiv.org/abs/2201.06274 · HTML: https://mlsanity.com/paper/2201.06274/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 16 of its 56 references that are in the map.
- First posted on arXiv 17 Jan 2022.

## Builds on (most cited first, 16 of 16)

- [Acquisition of Chess Knowledge in AlphaZero](https://mlsanity.com/paper/2111.09259/) (2021)
- [Topology of deep neural networks](https://mlsanity.com/paper/2004.06093/) (2020)
- [AI Safety Gridworlds](https://mlsanity.com/paper/1711.09883/) (2017)
- [Learning Safe Multi-Agent Control with Decentralized Neural Barrier Certificates](https://mlsanity.com/paper/2101.05436/) (2021)
- [On the geometry of generalization and memorization in deep neural networks](https://mlsanity.com/paper/2105.14602/) (2021)
- [Exploratory Not Explanatory: Counterfactual Analysis of Saliency Maps for Deep Reinforcement Learning](https://mlsanity.com/paper/1912.05743/) (2019)
- [Learning Locomotion Skills Using DeepRL: Does the Choice of Action Space Matter?](https://mlsanity.com/paper/1611.01055/) (2016)
- [Geometric Understanding of Deep Learning](https://mlsanity.com/paper/1805.10451/) (2018)
- [Learning to Locomote: Understanding How Environment Design Matters for Deep Reinforcement Learning](https://mlsanity.com/paper/2010.04304/) (2020)
- [Learning to cooperate: Emergent communication in multi-agent navigation](https://mlsanity.com/paper/2004.01097/) (2020)
- [Flatland Competition 2020: MAPF and MARL for Efficient Train Coordination on a Grid World](https://mlsanity.com/paper/2103.16511/) (2021)
- [Generalizing from a few environments in safety-critical reinforcement learning](https://mlsanity.com/paper/1907.01475/) (2019)
- [Quantitative Performance Assessment of CNN Units via Topological Entropy Calculation](https://mlsanity.com/paper/2103.09716/) (2021)
- [Coordinated Robot Navigation via Hierarchical Clustering](https://mlsanity.com/paper/1507.01637/) (2015)
- [Graph-based State Representation for Deep Reinforcement Learning](https://mlsanity.com/paper/2004.13965/) (2020)
- [A space of goals: the cognitive geometry of informationally bounded agents](https://mlsanity.com/paper/2111.03699/) (2021)

## Built on by (most cited first, 1 of 1)

- [Simplicial Hopfield networks](https://mlsanity.com/paper/2305.05179/) (2023)

## Abstract (arXiv)

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.