Behavior of Compassless Automata on Ladder Graphs

Abstract

The objective of this note is to examine the capabilities of collectives of compassless automata in exploring ladder graphs. Each graph is anonymous, meaning the vertices of the graph lack identifying labels, and thus, all vertices of the same degree appear identical to the automata. The automata do not distinguish between vertices based on their coordinates or direction (which means the automata have no compass). We considered collectives consisting of a controlling automaton and some pebbles, which are automata of the simplest form, whose positions are entirely determined by the controlling automaton. We have presented minimal collectives that explore ladder graphs and some of their subgraphs.