SIGFPT 23: Stigmergy 3 - Pebble Automata

Participants: _vgr

The SIGFPT group continued its summer-long exploration of stigmergy with a focus on pebble automata as a formal model. The session examined a foundational 1978 paper by Blum and Kozen that explores computation with minimal internal state, using the compass as a metaphor for agent capabilities. The discussion centered on two critical properties for stigmergic systems: statelessness (how agents operate without memory) and observability (what agents can perceive from their environment). Pebble automata serve as an abstract toy problem that illuminates these constraints while remaining applicable to real-world examples ranging from swarm robotics to distributed AI agents. By studying this formalism, the group aims to better understand how stigmergic coordination emerges from simple local interactions mediated through environmental modification.

• Pebble automata provide a toy problem formalism for understanding statelessness and observability in stigmergic systems, bridging abstract theory with practical applications.
• The classical 1978 Blum and Kozen work on compass-based computation illuminates how agents can accomplish complex tasks without maintaining internal state through environmental interaction.
• Stigmergic principles apply across diverse domains from swarm robotics to AI agents, with pebble automata serving as a unifying theoretical framework.

View discussion in Discord →