# Pathfinding in multi goal, multi agent environment

I have an environment in which I have multiple agents (a), multiple goals (g) and obstacles (o).

.  .  .  a  o  .  .  .
.  .  .  .  o  .  g  .
.  a  .  .  .  .  .  .
.  .  .  .  o  .  .  .
.  o  o  o  o  .  g  .
.  o  .  .  .  .  .  .
.  o  .  .  .  .  o  .
.  .  .  o  o  o  o  a


What would an appropriate algorithm for pathfinding in this environment?

The only thing I can think of right now, is to Run a separate version of A* for each goal separately, but i don't think that's very efficient.

• How do you know it's not very efficient? Have you tried it? If your environment is that small, it'll be fine. – Ray Dey Nov 23 '11 at 21:39
• my environment is about 200*200 with about 10-100 agents. – Rohan Agrawal Nov 25 '11 at 22:07

I know this question is old, but since no answer has been selected I'm going to post my own and hope it helps someone else.

Depends on the situation of your map whether you can apply a simple A* algorithm, or use a collaborative A* algorithm. By the situation I mean: Can two agents occupy the same space at a given time? If the answer is yes, then a simple A* algorithm for each agent will do the thing. In the case the answer is no, the application of a collaborative path-finding algorithm could be helpful. After doing a little research, I found that this algorithm is a perfect example of how a collaborative algorithm works using A*, this could help as a starting point to apply a collaborative algorithm that could be later improved to fulfil your needs.

You might want to check out some sort of All pair shortest path algorithm, maybe this one can be a good start.

If there are a small number of goals, and a large number of agents then you can do a BFS from each goal.

If there are more goals than agents you can also do it the more usual way round - start the search from the agents.

Either way you end up with the best path from each agent to each goal, without having to run A* for number_of_agents * number_of_goals.

• Running a BFS will most likely be far less efficient than running A* with a half-decent heuristic. Worst-case if the agent is in the top left corner and the goal is in the bottom right, and there are no obstacles, it will search the ENTIRE search space. A* in the same situation would (ideally go down in a diagonal path). -1 for this answer since I feel it's wrong. – Ray Dey Nov 23 '11 at 23:46
• It depends on the situation. For example if there's 100 agents and 4 goals. To get the path from every agent to every goal would require running A* 400 times, or a BFS 4 times. Also if there's no obstacles at all you don't need any path finding algorithm, you just need to move directly towards the goal. – Adam Nov 24 '11 at 1:11
• @RayDey 4 goals to 100 agents is the same as 100 agents to 4 goals. Either way, it's 400. Unless, and I don't know if this is possible, A* can go for multiple goals in one "run". – Richard Marskell - Drackir Nov 24 '11 at 22:56
• @Drackir doh! Well that was silly, thanks. Tiredness kills. Initial point still stands, but ignore the followup hehe :) – Ray Dey Nov 24 '11 at 23:24

I'm going to just answer with the obvious here.

Use A*

If your environment is going to be that small, it's not going to be a problem. Give your CPU some credit, it's a lot more capable than you think it is.

Don't prematurely optimize. Implement your A* algorithm and run it on each agent. If you find it's slow, look into why it's slow. Profile it. Is the heuristic slow? Is it inadmissable? Look here for examples of heuristics that could help.

How many times are you generating a path? If you're generating a path from the same source and destination, then think about caching paths in a lookup table so you don't have to go through the path generation process again.

• my environment is about 200*200 with about 10-100 agents. I think i would have to generate new paths on every move, because new goals can appear at any moment at any place. – Rohan Agrawal Nov 25 '11 at 22:10

A* is great if you have a single objective for every agents. If you have several objectives for every agents (for instance if your agents have to go to the closest objective), Dijkstra is better.

Now it depend on what you want to do.

Do you already have each agent a assigned to a single goal g? If so, I agree with the other answers: A* would work well, although for such a small map it may not matter which pathfinding algorithm you use. If each agent a can go to any of the goals then you could use Dijkstra's algorithm and stop whenever any goal g is reached.

If however you want at most one agent a to be assigned to each goal g then you need to first assign agents to goals. You could use something like Kuhn-Munkres to make the assignment. Here's the Wikipedia description of the assignment problem:

There are a number of agents and a number of tasks. Any agent can be assigned to perform any task, incurring some cost that may vary depending on the agent-task assignment. It is required to perform all tasks by assigning exactly one agent to each task in such a way that the total cost of the assignment is minimized.

You'll need to come up with costs; you could do that either with the same heuristic you use for A*, or you could calculate the path lengths exactly (perhaps with Dijkstra's or Floyd-Warshall). After you've made the assignment you'll need to find the paths. If you computed the paths in order to get the costs, you'll already have them, but if you used a heuristic, you'll need to use A* at this point to find the paths.