Well having no environment collision to avoid helped ;) But yeah that'd be a tricky problem to solve with navmesh!
I did have a bit of code to steer them away from on-coming collisions, but it was really pretty basic tbh, they just steered toward their target and accelerated when facing it.