In this paper, we develop an autonomous construction system in which self-contained ground robots build a protective barrier by means of compliant pockets. We present a stochastic control algorithm based on two biological mechanisms–stigmergy and templates–that takes advantage of compliant pockets for autonomous construction with single and multiple robots. The control algorithm guides the robot(s) to build the protective barrier without relying on a central planner, an external computer, or a motion capture system. We propose a statistical model to represent the structures built with the compliant pockets, and we provide a set of criteria for assessing the performance of the proposed system. To demonstrate the feasibility of the proposed system, real-robot and simulation experiments were carried out. The results show the viability of the proposed autonomous construction system.