Suppose we have $N$ fixed points (set $S$ with $|S|=N$) on the plane and $m$ agents with fixed, known initial positions ($m<N$) outside $S$. We should transfer the agents so that in our final configuration they are all positioned to different points of $S$. How could we achieve it by minimizing the total distance covered by the agents?
$\begingroup$
$\endgroup$
4
-
$\begingroup$ it might be a good question..if we could understand what the question is $\endgroup$– Sasho NikolovCommented Jul 15, 2012 at 18:54
-
4$\begingroup$ My interpretation of the problem: You have to move $m$ agents so that each agent uniquely occupies one of $N$ fixed points, and you want to find the mapping that minimizes total distance. This can be solved as a min-cost flow problem. $\endgroup$– AaronCommented Jul 15, 2012 at 20:11
-
7$\begingroup$ Specifically, it's a min-weight bipartite matching problem. $\endgroup$– JeffECommented Jul 15, 2012 at 22:46
-
$\begingroup$ I'm having difficulty understanding what quantity you want to minimize. What do you mean by "total distance covered by the agents"? Is there some definition of when a point is covered by an agent, or something? $\endgroup$– D.W. ♦Commented Oct 3, 2014 at 0:37
Add a comment
|
3 Answers
$\begingroup$
$\endgroup$
2
My understanding of this question is that you have a two lists of $n$ two-dimensional coordinates. The first list represents the position of a bunch of agents (robots, maybe, or police cars). The second list represents where those agents need to go (which places need to have police cars dispatched to them), and may be longer than the first list.
It is always possible to minimize the sum distance traveled by all agents, if that's what you're worried about: there are $!n$ ways we could dispatch the robots to new positions, we can enumerate all of them, calculate the distance the agents have to travel, and pick the one that has the least distance. As written, "enumerate all the possibilities" I think counts as an answer to your question, though it's probably not the one you wanted.
There are a couple of more precise questions, all or none of which might be interesting and/or research-level. (I'm not a Theory A person...)
- Is a solution possible if each agent (robot/police officer) has to make a decision independently, or has a limited ability to coordinate with other agents?
How quickly could the central dispatcher come up with a plan to dispatch everyone most efficiently?
Aaron Roth observes in the comments that this can be solved as a min-cost flow problem. I think that solution looks like this (hopefully I won't make a total fool of myself here): each agent is a source vertex and each dispatch target is an intermediate vertex. There is a capacity-1 edge from each source to a vertex representing the dispatch target, and the cost along that edge is proportional to the distance between the agent's initial position and the dispatch target. There is also a capacity-1, cost-0 edge from each dispatch target vertex to the sink.
- How quickly could the central dispatcher come up with a plan to dispatch everyone that is some multiple of the most efficient solution?
-
$\begingroup$ A really interesting issue here is the first question made by Rob Simmons: How could we develop a distributed algorithm which solves the problem? $\endgroup$ Commented Jul 18, 2012 at 9:21
-
$\begingroup$ @d.th.man Practically, we can't, if you take a "distributed algorithm" to mean that each agent decides where to go, then observes where the others go and possibly changes its destination. If any of them starts moving and doesn't target to the place where the optimal solution would take him, a distributed algorithm cannot be optimal anymore. $\endgroup$ Commented Dec 30, 2018 at 20:38
$\begingroup$
$\endgroup$
This is an assignment problem which can, for example, be solved by the Hungarian algorithm or by expressing it as linear program. Note that you can adapt your problem to the definition by padding the set of agents with $N-m$ dummy agents which have travel cost $0$ to all nodes.
$\begingroup$
$\endgroup$
7
how about creating tuples of all M agents with N points, sorting them by distance and then greedily picking the first M. this is basically what kruskal does. we could modulate this as a graph where we have a root noe connected to all agents(with edge weight 0) then create all edges from agents to points with the distance as weight, the mst should be the answer we are looking for. is this correct?
-
$\begingroup$ If @Raphael's answer, which does not depend on greedy algorithms, is correct, this answer is unlikely to be correct. $\endgroup$– John L.Commented Dec 30, 2018 at 11:39
-
$\begingroup$ but kruskal is proved to be right. and what i am offering is creating an mst. the mst kruskal picks is basically the best option for each robot given the constraints. could you elaborate a bit why you think this is incorrect? $\endgroup$ Commented Dec 30, 2018 at 12:13
-
$\begingroup$ Two agent A1 and A2. Two point P1 and P2. d(A1, P1)=1, d(A1, p2)=2, d(A2,p1)=2, d(A2,p2)=10. Greedy choice will not work. $\endgroup$– John L.Commented Dec 30, 2018 at 12:22
-
-
$\begingroup$ @Apass.Jack Your counterexample violates the triangular equation. Would be interesting to know what's the worst case for the greedy algorithm for n targets, m agents, and all distances being euclidean distances. You could add a second phase where two agents swap destinations if it leads to savings. $\endgroup$ Commented Dec 30, 2018 at 20:41