In a robotic laboratory of one university, the lab members are testing mobile robots. Each robot has a radio transmitter that it uses to communicate with a base station, and they find that if the robots get too close to one another, then there are problems with interference among the transmitters. So a problem arises: how to plan the motion of the robots in such a way that each robot gets to its intended destination, but in the process the robots don’t come close enough together to cause interference problems. This problem could be modeled as: suppose that we have an undirected graph G=(V,E), representing the floor plan of a building, and there are two robots initially located at nodes a and b in the graph. The robot at node a wants to travel to node c along a path in G, and the robot at node b wants to travel to node d. This is accomplished by means of a schedule: at each time step, the schedule specifies that one of the robots moves across a single edge, from one node to a neighboring node; at the end of the schedule, the robot from node a should be sitting on c, and the robot from b should be sitting on d. A schedule is interference-free if there is no point at which the two robots occupy nodes that are at a distance ≤r from one another in the graph, for a given parameter r. We’ll assume that the two starting nodes a and b are at a distance greater than r, and so are the two ending nodes c and d. Give a polynomial-time algorithm that decides whether there exists an interference-free schedule by which each robot can get to its destination.
In a robotic laboratory of one university, the lab members are testing mobile robots. Each robot has a radio transmitter that it uses to communicate with a base station, and they find that if the robots get too close to one another, then there are problems with interference among the transmitters. So a problem arises: how to plan the motion of the robots in such a way that each robot gets to its intended destination, but in the process the robots don’t come close enough together to cause interference problems.
This problem could be modeled as: suppose that we have an undirected graph G=(V,E), representing the floor plan of a building, and there are two robots initially located at nodes a and b in the graph. The robot at node a wants to travel to node c along a path in G, and the robot at node b wants to travel to node d. This is accomplished by means of a schedule: at each time step, the schedule specifies that one of the robots moves across a single edge, from one node to a neighboring node; at the end of the schedule, the robot from node a should be sitting on c, and the robot from b should be sitting on d.
A schedule is interference-free if there is no point at which the two robots occupy nodes that are at a distance ≤r from one another in the graph, for a given parameter r. We’ll assume that the two starting nodes a and b are at a distance greater than r, and so are the two ending nodes c and d.
Give a polynomial-time
Trending now
This is a popular solution!
Step by step
Solved in 3 steps
