Group cohesion and consensus have primarily been studied in the context of discrete decisions, but some group tasks require making serial decisions that build on one another. We examine such collective problem solving by studying obstacle navigation during cooperative transport in ants. In cooperative transport, ants work together to move a large object back to their nest. We blocked cooperative transport groups of Paratrechina longicornis with obstacles of varying complexity, analyzing groups' trajectories to infer what kind of strategy the ants employed. Simple strategies require little information, but more challenging, robust strategies succeed with a wider range of obstacles. We found that transport groups use a stochastic strategy that leads to efficient navigation around simple obstacles, and still succeeds at difficult obstacles. While groups navigating obstacles preferentially move directly toward the nest, they change their behavior over time; the longer the ants are obstructed, the more likely they are to move away from the nest. This increases the chance of finding a path around the obstacle. Groups rapidly changed directions and rarely stalled during navigation, indicating that these ants maintain consensus even when the nest direction is blocked. Although some decisions were aided by the arrival of new ants, at many key points, direction changes were initiated within the group, with no apparent external cause. This ant species is highly effective at navigating complex environments, and implements a flexible strategy that works for both simple and more complex obstacles.