StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>The LBAP (linear bottleneck assignment) is only one specific sub-class in a whole family of <strong>assignment and path-routing problems</strong> that are pertinent to your case. </p> <p>You have quite a choice when deciding on the <strong>MinMax</strong> routing algorithm to implement for your n robots. Here's what I'd do: I'd start with the simplest implementation of <strong>Dijkstra's shortest path algorithm.</strong></p> <p>The <a href="http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm" rel="nofollow">wikipedia page for Dijkstra</a> has a nice visual example, but their pseudo code looks more daunting than it needs to be. It even links to <a href="http://en.wikipedia.org/wiki/Motion_planning" rel="nofollow">robot motion planning</a> though from your question it looks like you are looking for path-algorithms to implement.</p> <p><strong>[updated based on OP's clarification re. MinMax]</strong></p> <p>Dijkstra still works, but you need to a few additional steps. Here's the basic strategy:</p> <pre><code>For each robot r = 1 to n calculate the shortest time-path for r from source of r to sink of r - (suggest starting with Dijkstra's) [if you are assuming constant speeds, then distance and length become equivalent] Next r </code></pre> <p><strong>MinMax schema:</strong></p> <ol> <li>sort all the paths (times) by time taken and take the longest one. (This is your theoretical minmax time.) - let's call it <code>t_max</code></li> <li>Ever other robot r has a time <code>"slack"</code>- <code>t_max</code> minus <code>time_r</code></li> <li>Take each pair of robots and see if their paths conflicts. <ul> <li>If no conflict, you are done.</li> <li>If yes to conflict, then you have to reroute (conflicted node/edge avoidance) but inside of the slack time. (Simplest rerouting is to wait until the conflicting robot clears the edge or intersection.)</li> </ul></li> <li>If you are able to route within <code>slack</code> , you are done. Otherwise, update t_max to be the longest (rerouted) path.</li> </ol> <p>Here are some examples of Dijkstra code that you should be able to use. (Web search will yield tons more.)</p> <ol> <li><a href="http://cs.fit.edu/~ryan/java/programs/graph/Dijkstra-java.html" rel="nofollow">http://cs.fit.edu/~ryan/java/programs/graph/Dijkstra-java.html</a> (Java)</li> <li><a href="https://gist.github.com/1001947" rel="nofollow">Here's a gist in Ruby</a></li> </ol> <p><strong>Additional Notes:</strong></p> <ol> <li>You don't have to limit yourself to Dijkstra's method. You can swap out and try other routing algorithms as you find them. Try out a few routing algorithms.</li> <li>Remember to check for conflicts. ( i.e. Two robots being at the same node at the same time t) The most basic implementation of conflict-free routing involves some precedence rules for one robot to wait until the node is clear before it proceeds.</li> </ol> <p>Hope that helps.</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload