Scenarios requiring the coordination of many individual units to accomplish some higher-level task are common to systems at many scales in biology, yet the ability of individual animals to join together to create functional structures is rare and confined to the social insects. Eciton army ants build complex “bridges” using linked individuals to span gaps in their foraging trail, including gaps exceeding the reach of ants from either side, by processes which have never been investigated. We performed novel field studies using an apparatus to induce a variable angle of deviation from (and return to) the natural foraging trails of Eciton hamatum. Our aim is to understand how bridges are built and how their position is affected by the angle of path deviation and traffic flow. While the presence of bridges optimises the length of the trail network, the colony also pays a cost in the number of ants locked up in the structure and hence unable to forage. We use our findings to examine how the ants respond to this cost-benefit trade-off. We make the unprecedented discovery that army ants dynamically adjust the location of their bridges, initiating bridges at the furthest point from the main trail axis and moving them in over time, lengthening the structures such that large gaps can be spanned. The final resting location of the structure meets a cost-benefit trade-off at the colony level, where large bridges increase foraging trail efficiency but sequester more workers from the foraging pool. Our study demonstrates not only how a group of simple units can self-assemble to make a complex structure without a blueprint or global controller, but also how this structure can be dynamically modified to meet optimality constraints in a cost-benefit trade-off, without any individual unit having information on either global benefits or costs. Insights generated by our study can inform future engineers in programming robot swarms capable of constructing a broad range of self-assemblages.