In this paper, we develop an autonomous construction system in which a self-contained ground robot builds a protective barrier by means of compliant pockets (i.e., filled bags). We present a stochastic control algorithm based on two biological mechanisms (stigmergy and templates) that takes advantage of compliant pockets for autonomous construction. The control algorithm guides the robot to build the structure without relying on any external motion capture system or external computer. 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 experiments were carried out. In each experiment, the robot successfully built the structure. The results show the viability of the proposed autonomous construction system.