We generate a formal
representation of all pos-
sible states and state
transitions of AI agents in-
teracting on a grid
Tom Burns and Robert Tang
OIST Graduate University, Japan
[Link] | [Link]@[Link] | +81 (0)90 6863 7039
A BSTRACT S TATE C OMPLEXES R EFERENCES
Gridworlds are a popular and powerful test-bed for artifi-
cial intelligence (AI) algorithms, especially in reinforcement [1] J. et al. Leike. AI safety gridworlds. arXiv, 1711.09883,
learning and associated AI safety problems. To describe 2017.
how AI agents behave in such gridworlds, we consider grid-
worlds as reconfigurable systems and construct their state [2] R. Ghrist and V. Petereson. The Geometry and Topology
complexes. These state complexes reveal the underlying of Reconfiguration. Advances in Applied Mathematics,
structures and patterns in the system’s possible reconfigu- 38(3):302–323, 2007.
rations. This work incorporates the concepts of gridworlds,
reconfigurable systems, and state complexes to show struc-
tures and patterns found in the state complexes of example
gridworlds. F UTURE R ESEARCH
We are currently exploring patterns and theoretical aspects
G RIDWORLDS of state complexes that hold across gridworlds of arbitrary
size, geometry, and labelling.
Ghrist & Peterson [2] define a state of a reconfigurable sys- For example, an upper bound for the total number of states
agent tem as a choice of labels (chosen from A) for every vertex of of a gridworld without objects is nk where n is the total num-
object G. ber of non-floor and non-wall labels and k is the total number
floor si : V (G) → A of agent labels. Such information may be useful to incorpo-
wall rate into AI algorithms or for analysis of the efficiency, accu-
The state complex S is a graph with vertices corresponding
racy, or safety of such algorithms in gridworlds.
to states, with edges connecting a pair states differing by a
Gridworlds are simplified, grid-like environments in which single generator.
each cell of the grid may be assigned a label. In the exam-
ple above, these labels are agent, object, floor, and wall.
Such environments can be used to test and develop AI al- S TATE C OMPLEXES OF G RIDWORLDS
gorithms, particularly in reinforcement learning [1].
State complexes often capture sym- We also find that some state com-
metries in a gridworlds’ geometry or plexes are subgraphs of others.
R ECONFIGURABLE SYSTEMS labelling, as shown in these examples.
Ghrist & Peterson [2] define reconfigurable systems as a col- The petal-like state complex above
lection of labels on a graph, where local rearrangements of shows different scales of geometry;
the labels represent reconfigurations of the system. for each position of the object there
From [2]: G is a graph. A is a set of possible labels on the exists a subgraph of 8 verticies (rep-
vertices of G. resenting the 8 possible locations of
A generator φ is a collection of three objects: the agent) which is connected to as
many other subgraphs as is possible
• the support, SU P (φ) ⊂ G for the agent to push or pull the ob-
ject to a different location from the
• the trace, T R(φ) ⊂ SU P (φ) current location represented in that
• a relabelling for the vertex set T R(φ) subgraph.