3
$\begingroup$

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):

  1. from each target location start a BF search until there is one agent in every target's searched space

  2. if the number of unique agents in the searched spaces is less than n, continue searching from all target locations

  3. 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.

  4. the first matching that fulfils step 3 is the solution

now I have two questions:

  1. 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?

  2. if solution 2 is optimal, are there any further ways of reducing the computational complexity?

Improve this question
$\endgroup$
4
  • $\begingroup$ @D.W. 1. the set of targets is fixed 2. uncovered target sites: those that don't have any agent going to it in a maximal matching. Does that clear it up? $\endgroup$ – mueslo Dec 22 '16 at 17:07
  • $\begingroup$ @D.W. no, I mean that in any particular maximal matching no agent is matched to that target. I initially thought part 2 (keep searching from all targets that share agents in the searched space) is sufficient, but it isn't (there are counter-examples I can think of). I assume I need to keep searching from all target sites that haven't exhausted their search space. $\endgroup$ – mueslo Dec 22 '16 at 17:22
  • $\begingroup$ OK, that makes more sense. Thanks! I'll think more about this -- seems like a nice question. $\endgroup$ – D.W.♦ Dec 22 '16 at 17:26
  • $\begingroup$ I think you need to clarify step 3 a bit more. Continue searching -- until when? When do you stop searching? As soon as you've found one more new agent-target combination? $\endgroup$ – D.W.♦ Dec 22 '16 at 18:48
2
$\begingroup$

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

Improve this answer
$\endgroup$
0
$\begingroup$

No, your proposed algorithm is not correct: it might output a matching that is sub-optimal. Here is a counter example.

We have three agents, A, B, and C. We have three targets, T, U, and V. Here are the distances:

Distances to T: A: 1, B: 100, C: 101
Distances to U: A: 2, B: 1, C: 3
Distances to V: A: 101, B: 1, C: 100

In the first round of your algorithm, you'll discover the AT, BU, and BV distances, but no complete matching is possible, so you'll continue searching. In the second round, you'll discover the BT, AU, and CV distances. Now a complete matching is possible, and A-T B-U C-V is the minimal matching given the information so far, so your algorithm will output that assignment, for a total cost of 102. However, this isn't the optimal answer; the optimal answer is A-T C-U B-V, for a total cost of 5. So in this example, your algorithm outputs the wrong answer.

In general, if you have a candidate algorithm like this and you want to know whether it is correct, a good strategy is to test it with random testing. Implement your proposed algorithm, and implement a (slower) golden-reference algorithm that is known to be correct. Now generate a million random small test cases (i.e., random inputs), and run both implementations on each and check that both implementations give the same answer in all cases. If you find any mismatch, you know your algorithm is incorrect and it's back to the drawing board. If you don't find any mismatches, that doesn't prove your algorithm is correct -- but the procedure is still helpful for catching some buggy ideas.

Improve this answer
$\endgroup$
2
  • $\begingroup$ I disagree. In the second round it would disocver AU and CU, and the resulting matching would be optimal. $\endgroup$ – mueslo Dec 23 '16 at 2:57
  • $\begingroup$ @mueslo, OK! In that case, can you edit the question to clarify what your step 3 is doing: you talk about continuing the search, but for how far and how long, and when exactly do you stop it? Apparently I must have misunderstood what you intended, so it might help if the question could state more explicitly what you intended. $\endgroup$ – D.W.♦ Dec 23 '16 at 3:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.