Two robots moving on a letter T

We will continue this post from the last post about Configuration space of a robot and two robots moving on a letter $T$.

In that post, we already discussed the whole problem of a robot moving on a letter $T$. 

We also proved using Farber's theorem that topological complexity of two robots moving on a letter $T$ is 2. In the robot motion planning problem, it means that we have to give two commands for robots to perform its task. How can we find two commands? I will answer this question in this post.

Let's recap some of the figures from the last post. 

Figure 1: $T \times T - \Delta$ (White line is $\Delta$)

Figure 2: Edited $T \times T-\Delta$ (Flower)

Figure 3: Contract Flower to a star with a hole at center

Figure 4: Star with no surface

Figure 5: Final Circle

Figure 6: Physical space $T$

Figure 7: Final circle and inner hole

Now, we know the configuration space was contractible to a circle giving us $TC$ as 2. We also know the two command for a robot moving in a circle. First, at non-antipodal points, the algorithm is the shortest path. Second, at antipodal points, we choose the algorithm clockwise direction. Let's solve the algorithm separately for both commands. First, we will find all the pairs of points in Figure 1(Configuration space) where the robots are non-antipodals or antipodals position. 

Non-Antipodal Points in Configuration space: 

We discussed in one of the posts that the command can be the shortest distance between initial and final for non-antipodal points. Figure 8 shows the initial position of a robot as a circle of brown color and last position is a sheet with a brown color circle. The command will be the shortest distance, and the robot will move in a circle as the arrow is pointed. 

Figure 8: Shortest Distance

Our problem is two robots moving on a $T$, so we have to trace the pairs of initial and final position in Figure 2. Here, both our initial and final position is the initial and final position of two robots moving on a letter $T$ which is shown in configuration space(Figure 8). This space is contracted from a star as shown in Figure 9 and the star is contracted from a figure as shown in Figure 3.

Figure 9: Circle to Star

To understand further, we use the Figure 7 where topologically Figure 3 can be contracted to either inner or outer circle in Figure 7. If we keep our configuration points on both the circles in Figure 7, we get Figure 10. Here, the brown line indicates that all the points are possible for the configuration points in Figure 8. Much better view for that is shown in Figure 11.

Figure 10: Brown line indicates all possible points

Figure 11

Figure 12

Figure 12 shows all the corresponding points for Figure 8(Circle). To move the shortest path, the initial configuration point will go first at the center, take a sharp turn, and then it will move to the final configuration point. We will not trace this into Figure 1($T \times T - \Delta$) as it would be difficult to trace back. But, we know that we can easily trace points from physical space $T$ to flower, so after we know what points on the flower are antipodal and non-antipodals, we can trace forth the points from physical space to flower. This is one of the examples of non-antipodal points where the robots will take the shortest path.

You are explaining what are non-antipodal points in the configuration space. There are no paths yet. Be sure you separate the ideas.

Plus, if these are paths, I am not sure I understand. What path are these? Do they pass thru the center???

Following are other examples where the two robots will take the shortest path.

Figure 13: Examples of shortest path

From the above examples, all the initial and final configuration which are not opposite are non-antipodal points. Now, let's look at the antipodal points and then we can solve the algorithms.

Antipodal points in Configuration space:

Figure 14 shows the antipodal points where the section is discontinuous. 

Figure 14: Antipodal points

Here, as we solved that the answer for above picture is to give the second command which goes clockwise direction. Figure 15 shows that. 

Figure 15: Antipodal points- Clockwise direction

Now, if we look that into the star with a hole, we get the Figure 16 as shown below. 

Figure 16

In flower, we get as shown in Figure 17.

Figure 17

This is one of the examples of pairs of antipodal points. Also, if we look at the flower, the half cut plane is extruded down. Therefore, all the points in that half plane are antipodal to their different half plane. Below are the examples of this situations.

Figure 18: Antipodals plane

Also, other examples of the pair of antipodal points are as shown in Figure 19.

Figure 19: Example of Antipodal points

Now, our final goal in this post is to show how does this configuration space affects the two robots moving on a letter $T$. 

Non-Antipodal points:

Example 1: If the initial and final position of the two robots is as shown in Figure 20. What is the command you can give to change the initial position to the last position? Black robots are the initial position, and black filled robots are the final position.

Figure 20: Example 1 Physical Space

Here, as we have to plug the initial and final position in the Cartesian product, we will take circle robot as X coordinates and a square robot as the Y coordinates. Now, let's plug the pair of initial and final position in our configuration space. Our initial position is $(10R, 5R)$ and final position is $(10G, 10B)$ where $R, B, G$ indicates if the robot is on red, blue or green line respectively.

Figure 21 shows these pairs in the configuration space.

Figure 21: Example 1- Configuration space

As it is challenging to find the solution using the original configuration space, let's see how this looks in the Flower. Figure 22 shows the two points in the Flower.

Figure 22: Example 1- Flower

If we contract the plane where the initial point is noted, we get Figure 23. 

Figure 23: Example 1- Star

Now, as we did before, these two points are non-antipodal points. Therefore, their path should be the shortest path as shown in Figure 24(Star) and Figure 25(Flower).

Figure 24: Example 1- Star movement

Figure 25: Example 2- Flower movement

Now, As we slowly move the initial position in the configuration space towards the final position, we can also trace that points in the physical space.

First, let's take the initial position from the red plane to the yellow plane which will give us Figure 24. The new point will be $(10R, 0R)$. Figure 26 shows how the robots moved in the physical space. 

Figure 26: Example 1- Change in position of Square robot

Now, in the configuration space, the initial position will move towards diagonal and will reach at point $(0R, 10B)$ as shown in physical space in Figure 27. The movement in the diagonal means that both the circle and a square robot will move at the same time and pace. Therefore, the square robot reaches its final position.

Figure 27: Example 1- Move diagonally

Now, as the square robot has reached its final destination, only circle robot will move on the line green. Therefore, in the configuration space, it moves from position $(0R, 10B)$ to $(10G, 10B)$. Now, both the robots have reached their final destination and therefore, our example 1 is solved.

Say what happens in the configuration space with each of these movements in the physical space. Does the point moves in the configuration space following the edge? goes straight to the center? be precise.

Example 2: Initial and final position are given in the physical space $T$(Figure 28). Find the movement of the robots from initial to the final position. Here, in the configuration space, initial point is $(10R, 7.5G)$ and final point is $(10G, 5B)$.

Figure 28: Example 2- Physical Space

Figure 29 shows the initial configuration point and final configuration point in the Flower while Figure 30 shows those points on the star.

Figure 29: Example 2- Flower

Figure 30: Example 2- Star

 As discussed above, Figure 29 says that two points are non-antipodal points. To find the path, see Figure 31 where the shortest path is given between initial and final configuration point on the star. In Figure 32, the path is shown on Flower.

Figure 31: Example 2- Movement in Star

Figure 32: Example 2- Movement in Flower

This path is a choice. There are many others (for instance a straight segment from initial to final). Why this choice corresponds exactly to the movement that you are describing in the T. Are you moving the square whilst the circle is stopped? or you are moving both at the same time? I think that this will make a difference in the movement in the petals, if one is stopped, waiting for the other to pass, your (pieces of) paths should be parallel to the sides of the petal.




As shown in Figure 32, in the configuration space, there are three different points the robot will move to go the shortest path. Figure 33 shows the first movement to point $(2.5R, 0B)$ in the physical space and Figure 34 shows the second change to point $(2.5G, 5B)$. The final movement will take us to our final position, and thus, the problem is solved.

Figure 33: Example 2- Physical space first shift

Figure 34: Example 2- Physical space second shift

Antipodal points:

 Example 3: Initial and final position are given in the physical space $T$(Figure 35) and Figure 36. Find the movement of the robots from initial to the final position. Here, in the configuration space, initial point is $(10R, 2.5R)$ and final point is $(2.5R, 10R)$.

Figure 35: Example 3- Initial position in physical space

Figure 36: Example 3- Final position in physical point

 In Figure 37, the initial and final position is shown using a black triangle on the general configuration space.

Figure 37: Example 3- Configuration points in original $T \times T$

 Figure 38 shows that the initial and final position in the different half red plane.

Figure 38: Example 3- Configuration points on Flower

 If we contract both the red planes, the antipodal points will also contract as shown in Figure 39.

Figure 39: Example 3- Configuration points on Star

Figure 40 shows the path between two antipodal points. Now, to find how the physical space will be affected by the path in configuration space, we will divide the path in configuration space into six parts. This way we can easily trace back our points in the physical space.

Figure 40: Example 3- Antipodal points and path between them in Flower

You are making a choice here. This is important. You chose to go around the hole in a particular side, as your algorithm says (clockwise). This choice should be reflected in the strategy to move the robots in the T. Who goes first? Be sure you are very precise with this description.


 Figure 41 shows the first shift from the initial point to the next point $(7.5R, 0B)$.

Figure 41: Example 3- First shift in physical space

 Figure 42 shows the second shift from the point $(7.5R, 0B)$ to $(6.5R, 1B)$.

Figure 42: Example 3- Second shift in the physical space

 Figure 43 shows the third shift from the point $(6.5R, 1B)$ to $(1G, 1B)$.

Figure 43: Example 3- Third shift in the physical space

 Figure 44 shows the fourth shift from the point $(1G, 1B)$ to $(1G, 0R)$.

Figure 44: Example 3- Fourth shift in the physical space

Figure 45 shows the fifth shift from the point $(1G, 0R)$ to $(0R, 1R)$ and finally, to the final position $(2.5R, 10R)$.

Figure 45: Example 3- Fifth shift in the physical space

Example 4: Initial and final position are given in the physical space $T$(Figure 46) and Figure 47. Find the movement of the robots from initial to the final position. Here, in the configuration space, initial point is $(7.5G, 7.5B)$ and the final position is $(7.5B, 7.5G)$.

Figure 46: Example 4- Initial position in the physical space

Figure 47: Example 5- Final position in the physical space

Figure 48 shows the configuration points in the general cartesian product $T\times T$.

Figure 48: Example 4- Configuration point in general 

 Figure 49 shows the initial and final configuration points in the Flower. As we studied above, we know that these two points are antipodal to each other. Therefore, they will take clockwise direction.

Figure 49: Example 4- Configuration point in the Flower

 Figure 50 shows the clockwise path between the initial and the final configuration point. To find out how this resonates with our physical space, we divide the path into two parts as shown below.

Figure 50: Example 4- Path between two antipodal points

 The shift in their first path is shown in Figure 51 where the points move from $(7.5G, 7.5B)$ to $(0B, 1R)$. Finally, our final movement will go to the point $(7.5B, 7.5G)$ completing our problem.

Figure 51: Example 4- Shifting in the physical space

I see you addressed at the end the problem I described above. Be sure you tie everything together and come up with an precise rule for the algorithm. Something like: If the initial and final positions of the two robots in the T are such and such then do this. If not, do this other thing. And describe exactly what are those things. 

Posted by: Chintan Patel

October 28th, 2017, 4:00 pm