This paper describes multi-robot experiments and systems which exploit their embodied nature to reduce needs for sensory, effector, and computational resources. Many natural phenomena, such as territorial markings or ant pheromone trails, take great advantage of the ability mark the environment, and of the natural dissipative processes which cause these markings to decay. In this way, globally complex behavior can result from simple local rules. The information invariants (\cite{DonaldBook}, \cite{DonJenRus}) literature raises the issue of robots similarly recording information, or even ``programs,'' into the physical environment. This paper provides example systems that dynamically encode information and ``programs'' into the physical environment, and by so doing, increase their own robustness and reduce their resource requirements and computational complexity. The main experimental system that we present, a robot ``chain'' used for foraging, is modeled after the natural phenomenon of ant pheromone trail formation. ``Minimal'' agents with local sensing and action form a system that can perform position-dependent tasks. We discuss how this system can dynamically adapt to environmental changes, both by forming efficient paths to changing resource locations and by dynamically assuming roles. We also demonstrate a robot soccer system that exhibits such dynamic role assumption and flexible teamwork, subject to global constraints, using only limited local sensing and no explicit communication. We discuss how moving information and computation into the shared physical environment improves our ability to generate complex global behaviors from simple locally interacting agents.