Comment by card_zero

There certainly are naive ways, although whatever I suggest here will be poorly thought out and will lead to the next problem. But OK, I suggest a scent trail. Each unit paints where it's been and prefers not to go that way again. Then of course it could paint itself into a corner, so it needs a local-maximum-busting strategy too, which probably means marching off in an arbitrary direction to see if it gets unstuck.

This would be behaving like a caged animal, and in a game, that's good, and better than a smarter algorithm. You don't want them to be idiots, but you don't want them to be magic, either.

The old "follow the left-hand wall" maze-solving strategy is another naive way to get out of a trap. It's not fun gameplay, but it's naive and it exists, so better naive strategies do too.