patternMinor
Minimum path - robot motion problem combined with freeze tag problem
Viewed 0 times
problempathrobottagwithminimumfreezemotioncombined
Problem
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.
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).
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.
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).
Solution
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.
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.
Context
StackExchange Computer Science Q#70566, answer score: 5
Revisions (0)
No revisions yet.