I would have been more surprised to learn that they do a truly random walk search.

They lay down pheromones to create trails, isn't that part of the answer to how they avoid crossing paths?