1
$\begingroup$

I've been thinking about path planning and am trying to make good heuristics for cases with multiple agents.

Suppose there are sets $S_i$ of coordinates in $\mathbb R^2$ or $\mathbb R^3$, each of the same size n, for each possible value of $i$ where $i \in [0, ... k]$.

A path is defined as k line segments connecting a sequence of k+1 coordinates, made up of one coordinate from each set $S_i$ in consecutive order. I want to find n paths such that (a) no two paths have the same point for a given index i in the sequence, and b) the combined path length of all the paths is minimized. In other words, assign coordinates from each set without replacement to construct paths with the goal of making the total path length as small as possible.

Right now i can do the minimization from some $i$ to $i+1$, but I am not sure if locally minimizing each step will yield a global minimum. I know I could brute force it, but that explodes really quickly.

$\endgroup$
  • $\begingroup$ Isn't the sum of the path lengths the same for all solutions? (i.e., the same regardless of how you assign candidates from each set to paths?) $\endgroup$ – D.W. Feb 29 at 19:19
  • 1
    $\begingroup$ What does requirement (a) mean? Can you state it more clearly? Is the index i given in the input? In that case can you list all inputs to the algorithm? What do you mean by same coordinate? Do you mean the same point? In $\mathbb{R}^2$, I think of a point in $\mathbb{R}^2$ as having two coordinates, the x-coordinate and the y-coordinate. Is that how you are using terminology too? $\endgroup$ – D.W. Feb 29 at 19:20
  • $\begingroup$ @D.W.: I think by "coordinate" s/he meant "point". (At least it makes no sense to me otherwise...) $\endgroup$ – j_random_hacker Feb 29 at 21:55
  • $\begingroup$ The sum of path lengths is not the same for all solutions. The first requirement is just saying that each path gets one element from each set, and they all get different elements for each i. Sorry for the confusion, by coordinate I just mean a specified (x,y) or (x,y,z). $\endgroup$ – JJJJJJJJJJJJJJJJ Mar 1 at 20:27
2
$\begingroup$

You can solve this optimally in $O(kn^3)$ time by solving a sequence of $k$ Assignment problems.

Let $f(i)$ be the lowest sum of costs of any set of $n$ paths beginning at step $i$ and continuing to step $k$ (i.e., the end). We would therefore like to compute $f(0)$, as well as a set of paths realising it.

Assume we have already computed $f(i+1)$. (Clearly $f(k) = 0$, so we have a starting point.) Let $A_{i,i+1}$ be the solution to the Assignment problem (minimum-weight bipartite matching) in which one set of vertices are the points in $S_i$ and the other is the points in $S_{i+1}$. I claim that we can compute $f(i)$ as $A_{i,i+1} + f(i+1)$.

Suppose this claim is not correct: then for some $i$, there is a better solution with cost $B_i < f(i)$, which can likewise be decomposed as $B_i = B_{i,i+1} + B_{i+1,k}$. In particular, let $i$ be the maximum possible $i$ for which $B_i < f(i)$. Then at least one of $B_{i,i+1} < A_{i,i+1}$ or $B_{i+1,k} < f(i+1)$ must be true for our assumption $B_i < f(i)$ to be true.

It cannot be that $B_{i,i+1} < A_{i,i+1}$, since $A_{i,i+1}$ is the minimum possible cost by definition of the Assignment problem. So it must be that $B_{i+1,k} < f(i+1)$. But this cannot be true either, since if it were then it would violate our assumption that $i$ is maximum possible. Thus supposing the existence of a solution with a better cost $B_i$ leads to a contradiction, so it cannot be true, meaning that $f(i)$ gives the optimal cost after all.

$f(0)$ gives you the cost of the optimal solution. To extract such a solution, just record the matchings produced by the Assignments problems you solved along the way.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thanks for the response! I am convinced by your reasoning and am glad to see that I already had the solution in my hands. Eventually I want to answer this question for curved paths instead of a sequence of line segments, but haven't been able to formulate the question yet. $\endgroup$ – JJJJJJJJJJJJJJJJ Mar 5 at 6:22
  • $\begingroup$ You're welcome! I think curved paths will be harder, since even if you just want to consider 2 possible "entry angles" for each curve at step $i+1$, you now have to solve $2^k$ Assignment problems at each step instead of 1. $\endgroup$ – j_random_hacker Mar 5 at 13:52

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.