Scribd
Upload
16 views1 page

Analyzing AI States in Gridworlds

This document discusses gridworlds as a test-bed for AI algorithms, particularly in reinforcement learning, and introduces the concept of state complexes to analyze the underlying structures of these environments. It defines gridworlds and reconfigurable systems, explaining how state complexes capture symmetries and relationships between states. Future research aims to explore theoretical aspects of state complexes across various gridworld configurations to enhance AI algorithm efficiency and safety.

Uploaded by

bkko2936
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
16 views1 page

Analyzing AI States in Gridworlds

This document discusses gridworlds as a test-bed for AI algorithms, particularly in reinforcement learning, and introduces the concept of state complexes to analyze the underlying structures of these environments. It defines gridworlds and reconfigurable systems, explaining how state complexes capture symmetries and relationships between states. Future research aims to explore theoretical aspects of state complexes across various gridworld configurations to enhance AI algorithm efficiency and safety.

Uploaded by

bkko2936
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

A BSTRACT S.C.

S OF G RIDWORLDS
Gridworlds are a popular and powerful test-bed
for artificial intelligence (AI) algorithms, especially
in reinforcement learning and associated AI safety
problems. To describe how AI agents behave in
such gridworlds, we consider gridworlds as recon-
figurable systems and construct their state com-
plexes. These state complexes reveal the underly-
ing structures and patterns in the system’s possible
reconfigurations. This work incorporates the con-
cepts of gridworlds, reconfigurable systems, and
state complexes to show structures and patterns
found in the state complexes of example grid-
worlds.
We generate a for- State complexes often capture symmetries in a
gridworlds’ geometry or labelling, as shown in these

G RIDWORLDS
agent object floor wall
mal representation of examples. The petal-like state complex above
shows different scales of geometry; for each posi-
tion of the object there exists a subgraph of 8 ver-
ticies (representing the 8 possible locations of the

all possible states and agent) which is connected to as many other sub-
graphs as is possible for the agent to push or pull
the object to a different location from the current
location represented in that subgraph.

state transitions of AI
Gridworlds are simplified, grid-like environments in
which each cell of the grid may be assigned a la-
bel. In the example above, these labels are agent,
object, floor, and wall. Such environments can be
agents interacting on
used to test and develop AI algorithms, particularly
in reinforcement learning [1].
a grid We also find that some state complexes are sub-
graphs of others.
R ECONFIGURABLE SYSTEMS
Ghrist & Peterson [2] define reconfigurable systems
as a collection of labels on a graph, where local
rearrangements of the labels represent reconfigu-
rations of the system.
From [2]: G is a graph. A is a set of possible labels
on the vertices of G.
A generator φ is a collection of three objects: Tom Burns and Robert Tang
• the support, SU P (φ) ⊂ G OIST Graduate University, Japan
• the trace, T R(φ) ⊂ SU P (φ)

• a relabelling for the vertex set T R(φ)

S TATE C OMPLEXES

F UTURE R ESEARCH
We are currently exploring patterns and theoretical
aspects of state complexes that hold across grid-
worlds of arbitrary size, geometry, and labelling. For
example, an upper bound for the total number of
states of a gridworld without objects is nk where


n is the total number of non-floor and non-wall la-


bels and k is the total number of agent labels. Such
information may be useful to incorporate into AI al-
gorithms or for analysis of the efficiency, accuracy,
Ghrist & Peterson [2] define a state of a reconfig- or safety of such algorithms in gridworlds.
urable system as a choice of labels (chosen from
A) for every vertex of G.
R EFERENCES
si : V (G) → A [1] J. et al. Leike. AI safety gridworlds. arXiv, 1711.09883,
2017.
The state complex S is a graph with vertices corre- [2] R. Ghrist and V. Petereson. The Geometry and Topol-
sponding to states, with edges connecting a pair [Link] | [Link]@[Link] | +81 (0)90 6863 7039 ogy of Reconfiguration. Advances in Applied Math-
states differing by a single generator. ematics, 38(3):302–323, 2007.

You might also like