3
$\begingroup$

Alright, I am not entirely sure if this is the right place to ask this, but here goes:

I have a map of coordinates of robots and obstacles. The first robot is awake from the start of the problem and it can wake up other robots on the map by walking next to them. Once a robot is woken up by another, it can also traverse the map and wake up other robots. The goal is to awaken all the robots using the minimum possible path.

Below I added an example of how a solution to a certain data set would look like. example image picturing the path of the robots: A wakes up B after which B wakes up C and D, and finally C wakes up D

I refrain from providing input/output files because I only want to ask for insights into and algorithm in pseudocode or even natural language, but if those would help I could add them as well!

Thank you very much in advance and should I provide any more info, do not hesitate to tell me!

EDIT #1: In the example, both robot A and robot B can traverse the path to C and D. The different colors show that in this example, robot B traversed the path to C and D. There are no cases where the robots hull interferes with the obstacles. The 'hull' can touch the obstacles. All robots have the same specifications. By minimum path I am trying to refer to the shortest time to wake up all the robots (i.e. time elapsed from when the first robot starts up until all robots are woken up).

$\endgroup$
  • $\begingroup$ I see a problem statement. What is your question about that problem? Are you looking for an algorithm that is provably correct and finds the minimum possible path? Such an algorithm, with minimum possible running time? What are your thoughts? What approaches have you already considered, and why did you reject them? This is a question-and-answer site, so it's important to articulate a question, and sharing your research helps others and helps you get more relevant answers. Also, what does "combined with freeze tag" mean? $\endgroup$ – D.W. Feb 20 '17 at 22:11
  • $\begingroup$ When you write about "minimum possible path", what are you trying to minimize? Elapsed time? Or total time travelled by all robots? Or something else? $\endgroup$ – D.W. Feb 20 '17 at 22:59
  • $\begingroup$ @Evil I added the information in the first edit. Thank you very much for your input! $\endgroup$ – Alexandru Chiriac Feb 21 '17 at 15:44
  • $\begingroup$ @D.W. I clarified what I wanted to mean by minimum path in the edit. The running time does not really matter, but a smaller running time would be preferred. I have considered Prim's algorithm, but it's way far off from providing an optimal solution considering the complications. By 'combined with freeze tag' I was referring to the 'freeze tag' optimization problem which describes a similar case but with no obstacles. $\endgroup$ – Alexandru Chiriac Feb 21 '17 at 15:51
  • 6
    $\begingroup$ "This problem is a subject of a student programming competition, taking place this week as a part of the course I teach. I'm kindly asking to withhold further answers until Saturday, February 25, 2017, as having them posted here would provide @alexandru-chiriac and other student participants who discovered this post with an unfair advantage. Thanks." Posted by Ilya Sergey $\endgroup$ – Evil Feb 22 '17 at 17:03
5
$\begingroup$

Define a fully connected, undirected graph $G$ so that there is a vertex for the initial position of each robot, and an edge between each two vertices whose length corresponds to the time for a robot to move from one position to the other. The edge lengths can be computed using the A* algorithm or any other pathfinding algorithm.

Now I think you want a rooted spanning tree $T$ for the graph $G$, with the following properties:

  • The root of the tree is the vertex that corresponds to the initial position of the awake robot.

  • Every node of the tree has two children, except for the root, which has one child.

  • The tree is a spanning tree, i.e., every vertex in $G$ appears somewhere in the three.

  • The "duration" of the tree is minimal among all such trees.

Here we define the duration of a tree to be the maximum of the lengths of all path from the root to some leaf.

I don't know whether there is an efficient algorithm to find such a tree.

$\endgroup$
  • $\begingroup$ How is this answer significantly different from the one below? I'm asking in order to improve my own. $\endgroup$ – combo Feb 21 '17 at 0:53
  • 1
    $\begingroup$ @combo, the difference is whether we are trying to minimize the total duration to awaken all robots or the total distance travelled. I've asked the original poster for clarification on which was intended; hopefully we'll get a response to that, and it will be clearer what the situation is. Your answer is a good one if we're trying to minimize total distance travelled. $\endgroup$ – D.W. Feb 21 '17 at 0:58
  • $\begingroup$ I see - and that could have an impact on whether we could solve the "find the best tree" sub-problem. In the "minimize total distance" case, it is the degree constrained MST (which is NP-complete) but in the "minimize elapsed time" case we are looking for a shortest path binary tree (which also seems to be difficult to find) $\endgroup$ – combo Feb 21 '17 at 1:07
1
$\begingroup$

Note: This answer was written for a related problem where the goal is to minimize total distance travelled rather than elapsed time.

This looks a lot like a minimum spanning tree problem (as your tags indicate). If we can compute a minimum spanning binary tree, then you could do the following (note that computing such a tree might take a while).

  1. Construct a complete undirected graph with a node for each "asleep" robot.
  2. Compute the shortest paths between each pair of robots using your favorite collision free path planner (Dijkstra's in grid-world, RRT, FMT, etc). If both robots are asleep, put that weight on the edge between the corresponding nodes for the robots. Denote the length of the shortest path from the awake robot to robot $k$ as $w_k$.
  3. Compute the minimum spanning tree starting from each of the nodes, and denote the sum of the weights of the edges in the tree starting from the $k$th robot by $W_k$. Return the tree with the smallest value of $W_k + w_k$ (which we'll call $T^*$).
  4. Send the first robot to the root of $T^*$. As long as there are robots left to awaken: send the "just-awakened" robot down the "left" edge and the "awakener" robot down the "right" edge (define "left" and "right" however you like).

By property of your path planner, you know that you have collision free, shortest paths between each pair of robots. By property of your minimum spanning tree, you know that you have the shortest cumulative-distance paths to visit all robots.

You could define "left" and "right" to minimize the maximum distance travelled by any robot by defining an edge as "left" if its shortest path to a leaf node is longer than the "right" edge. This ensures that just-awakened robots (which have travelled less) take the longer routes.

$\endgroup$
  • $\begingroup$ If you care about distance rather than elapsed time, then it does measure cost correctly (note the OP says "minimum possible path" without specifying distance or time). I made a bad assumption that we would be able to compute a binary MST, but that turns out to be NP-complete. Added a caveat above. $\endgroup$ – combo Feb 20 '17 at 22:55

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.