  We develop a framework for self-induced phase changes in programmable matter
in which a collection of agents with limited computational and communication
capabilities can collectively perform appropriate global tasks in response to
local stimuli that dynamically appear and disappear. Agents reside on graph
vertices, where each stimulus is only recognized locally, and agents
communicate via token passing along edges to alert other agents to transition
to an "aware" state when stimuli are present and an "unaware" state when the
stimuli disappear. We present an Adaptive Stimuli Algorithm that is robust to
competing waves of messages as multiple stimuli change, possibly adversarially.
Moreover, in addition to handling arbitrary stimulus dynamics, the algorithm
can handle agents reconfiguring the connections (edges) of the graph over time
in a controlled way.
  As an application, we show how this Adaptive Stimuli Algorithm on
reconfigurable graphs can be used to solve the foraging problem, where food
sources may be discovered, removed, or shifted at arbitrary times. We would
like the agents to consistently self-organize using only local interactions,
such that if the food remains in position long enough, the agents transition to
a gather phase, collectively forming a single large component with small
perimeter around the food. Alternatively, if no food source has existed
recently, the agents should self-induce a switch to a search phase in which
they distribute themselves randomly throughout the lattice region to search for
food. Unlike previous approaches to foraging, this process is indefinitely
repeatable. Like a physical phase change, microscopic changes such as the
deletion or addition of a single food source triggers these macroscopic,
system-wide transitions as agents share information about the environment and
respond locally to get the desired collective response.
