patternMinor
Optimality in multi-agent multi-target path finding
Viewed 0 times
pathtargetmultiagentoptimalityfinding
Problem
Suppose I have a regular rectangular weighted grid with multiple agents and obstacles. Agents cannot be in grid sites that contain obstacles, and for simplicity assume multiple agents can be in the same grid site.
If I select a single location on the grid and want to find the nearest agent to that location, a good solution is easy: I can simply do a breadth-first (BF) search.
However, suppose I have n target locations and m>=n agents. I want to visit the target locations with n agents simultaneously. I do not care which agent goes to which location, but the total distance travelled must be minimal. Or, to rephrase, I'm attempting to find a distance-weighted maximum matching for two sets of nodes on a graph.
One solution would be to calculate the shortest path from all agents to all targets and then do a bipartite matching. Since the graph may be disconnected by obstacles, this could result in needless multiple sampling of the entire grid space of a connected region. This hardly seems optimal. (Solution 1)
I propose the following 'algorithm' (Solution 2):
-
from each target location start a BF search until there is one agent in every target's searched space
-
if the number of unique agents in the searched spaces is less than n, continue searching from all target locations
-
if a matching between targets and agents in their respective searched spaces is not possible with full target covering, continue searching from the target locations where covering was not possible and all other target sites that share agents with the uncovered target sites all target locations.
-
the first matching that fulfils step 3 is the solution
now I have two questions:
-
is solution 2 optimal, i.e. is it guaranteed that I will select precisely those agents with the least total distance to their assigned targets? I.e. am I not neglecting any agents by not continuing the search for long enough?
-
if solution 2 is optimal, are there any further ways of reducing the computation
If I select a single location on the grid and want to find the nearest agent to that location, a good solution is easy: I can simply do a breadth-first (BF) search.
However, suppose I have n target locations and m>=n agents. I want to visit the target locations with n agents simultaneously. I do not care which agent goes to which location, but the total distance travelled must be minimal. Or, to rephrase, I'm attempting to find a distance-weighted maximum matching for two sets of nodes on a graph.
One solution would be to calculate the shortest path from all agents to all targets and then do a bipartite matching. Since the graph may be disconnected by obstacles, this could result in needless multiple sampling of the entire grid space of a connected region. This hardly seems optimal. (Solution 1)
I propose the following 'algorithm' (Solution 2):
-
from each target location start a BF search until there is one agent in every target's searched space
-
if the number of unique agents in the searched spaces is less than n, continue searching from all target locations
-
if a matching between targets and agents in their respective searched spaces is not possible with full target covering, continue searching from the target locations where covering was not possible and all other target sites that share agents with the uncovered target sites all target locations.
-
the first matching that fulfils step 3 is the solution
now I have two questions:
-
is solution 2 optimal, i.e. is it guaranteed that I will select precisely those agents with the least total distance to their assigned targets? I.e. am I not neglecting any agents by not continuing the search for long enough?
-
if solution 2 is optimal, are there any further ways of reducing the computation
Solution
Read the following paper on the generalization of your problem with "makespan" as the objective. The proposed algorithm should work even if $m\neq n$.
H. Ma and S. Koenig. "Optimal Target Assignment and Path Finding for Teams of Agents." http://idm-lab.org/bib/abstracts/papers/aamas16a.pdf
H. Ma and S. Koenig. "Optimal Target Assignment and Path Finding for Teams of Agents." http://idm-lab.org/bib/abstracts/papers/aamas16a.pdf
Context
StackExchange Computer Science Q#67713, answer score: 2
Revisions (0)
No revisions yet.