Cellular ANTomata: Food-Finding and Maze-Threading

Abstract

A model for realizing ant-inspired algorithms that coordinate robots within a fixed, geographically constrained environment is proposed and illustrated. The model, dubbed cellular ANTomata, inverts the relationship between ant-robots and the environment that they navigate: intelligence now resides in the environment rather than in the ants. The cellular ANTomaton model is illustrated via three proof-of-concept problems: having ants "park" in the nearest corner; having ants seek "food items" (both with and without impenetrable obstacles); having a single ant thread a maze. In all cases, "unintelligent" cellular-ANTomata-based ant-robots accomplish goals provably more efficiently than traditional "intelligent" ant-robots can; indeed, "intelligent" ant-robots cannot park at all! All of the presented algorithms are scalable: they provably work within any finite-size environment.