Pathfinding in multi goal, multi agent environment

Question

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.

Answer 1

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.

Answer 2

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

Answer 3

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.

Answer 4

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.

Answer 5

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.

Answer 6

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.