T ITLE OF THE P OSTER
{ L IST OF A UTHORS } OIST G RADUATE U NIVERSITY, J APAN
1. A BSTRACT 3. R ECONFIGURABLE 5. S TATE C OMPLEXES OF G RIDWORLDS
Gridworlds are a popular and powerful test-bed Ghrist & Peterson [1] define reconfigurable systems
for artificial intelligence (AI) algorithms, especially as a collection of labels on a graph, where local rear-
in reinforcement learning and associated AI safety rangements of the labels represent reconfigurations
problems. To describe how AI agents behave in such of the system.
gridworlds, we consider gridworlds as reconfig- From [1]: G is a graph. A is a set of possible labels
urable systems and construct their state complexes. on the vertices of G.
These state complexes reveal the underlying struc-
tures and patterns in the system’s possible recon- A generator φ is a collection of three objects:
figurations. This work incorporates the concepts of • the support, SU P (φ) ⊂ G
gridworlds, reconfigurable systems, and state com-
plexes to show structures and patterns found in the • the trace, T R(φ) ⊂ SU P (φ)
state complexes of example gridworlds.
• a relabelling for the vertex set T R(φ)
2. G RIDWORLDS
4. S TATE C OMPLEXES R ESEARCH
agent object floor wall
State complexes often capture symmetries in a gridworlds’ geometry or labelling, as shown in these examples.
The petal-like state complex above shows different scales of geometry; for each position of the object there
exists a subgraph of 8 verticies (representing the 8 possible locations of the agent) which is connected to as
many other subgraphs as is possible for the agent to push or pull the object to a different location from the
current location represented in that subgraph.
Ghrist & Peterson [1] define a state of a reconfig-
Gridworlds are simplified, grid-like environments
urable system as a choice of labels (chosen from A)
in which each cell of the grid may be assigned a label.
for every vertex of G.
In the example above, these labels are agent, object,
floor, and wall. Such environments can be used to si : V (G) → A
test and develop AI algorithms, particularly in rein- The state complex S is a graph with vertices cor-
forcement learning [2]. responding to states, with edges connecting a pair
states differing by a single generator.
R EFERENCES 6. F UTURE R ESEARCH C ONTACT I NFORMATION
[1] R. Ghrist and V. Petereson. The Geometry and We are currently exploring patterns and theoretical aspects of state complexes that hold across gridworlds
Topology of Reconfiguration. Advances in Applied of arbitrary size, geometry, and labelling. For example, an upper bound for the total number of states of a Web [Link]
n
Mathematics, 38(3):302–323, 2007. gridworld without objects is k where n is the total number of non-floor and non-wall labels and k is the total Email [Link]@[Link]
number of agent labels. Such information may be useful to incorporate into AI algorithms or for analysis of Phone +81 (0)90 6863 7039
[2] J. e. a. Leike. AI safety gridworlds. arXiv, the efficiency, accuracy, or safety of such algorithms in gridworlds.
1711.09883, 2017.