Let's start with a simplified case and work up from there: Just one AI agent exploring the graph.

Calculating the *perfect* route to explore the whole graph in an acceptable time is [an unsolved problem][1]. So we shouldn't even try to find a perfect solution and instead aim for a simple solution which provides "good enough" results. 

One such algorithm is the "greedy" algorithm: Always walk to the closest unexplored node.

This algorithm is very easy to implement and will cover a good amount of area in the short-term. But it has an unfortunate side-effect. It might lead the AI actor on a journey far away from the starting location before it fully explored its vicinity. You would usually expect them to look close to their starting location and then expand further when they don't find anything nearby.

A good way to account for that is to integrate this into the rating function for picking the next node. When you rate the nodes by priority, don't just take the distance to the current location of the agent into account, but also the distance to the starting location. How you weight these two criteria in relation to each other is more of an art than a science. Just experiment with this until you get a result you like.

Now how do we extend this to multiple cooperating agents? When they all perform the same algorithm, they will all walk to the same tile. They will likely stick close together and not make any use of their superior number. 

In order to get them to divide and split, add a 3rd criteria to your rating function: proximity between the node and the next other agent. But assign a *negative* weight to this criteria. That means agents will avoid those tiles which are close to other agent and will instead focus on those areas of the graph no other agent currently attends to yet.

So final node rating formula:

`node_rating = distance_agent * a + distance_origin * b - distance_closest_other_agent * c`

Adjust the values of the constants `a`, `b` and `c` to taste.

Lowest rating wins.


 [1]: https://en.wikipedia.org/wiki/Travelling_salesman_problem