Topological Robotics (Wilbur Wright College): Configuration space of a robot and two robots moving on a letter $T$

To find the motion planning problem, we need to know how to find the configuration space and solving the Topological Complexity which was introduced by Farber in his paper. Let's first look at the problem where only one robot is moving.

Motion planning of a robot moving on a letter $T$:

Three segments are glued together to form a letter $T$. So, the robot is moving on a letter $T$ as shown in Figure 1.

As there is only one robot, the physical and configuration space is same and it's $T$. Below is Figure 2 which shows the initial and final position on the physical space, and their path is shown on the configuration space $ T $.

The configuration space $T$ is easily contractible to a point because there are no holes in $T$. According to the Farber's theorem 3, if two spaces are homotopic to each other, then their TC is the same. We know that TC of a point is 1 and as $T$ is contractible to a point, TC($T$) is also 1. This proves that we can give just one command to a robot on that space $T$.

The domain is $U=T\times T$ and it can also be written as $$U=\{(A, B) | A\in T \mbox{ and } B\in T\}$$

An example of a motion planning can be considered as $s: U \rightarrow PT $ as shown in Figure 1 where a command can be given to move the position of a robot to the shortest distance. As only one robot is moving, there is no diagonal and so it can move freely.

Figure 1

Motion planning of two robots moving on a letter $T$:

We have to find the physical and configuration space, and the Topological Complexity using the configuration space.

The physical space is the space where the robots are moving and therefore, it is $T$. To find the configuration space, we have to find:
$$C^2(T)= T \times T - \Delta $$

Let's first find the Cartesian product $T \times T$ and then we can cut the diagonal points.

The letter $T$ is connected by three segments of the line. Therefore, for the cartesian product to connected, we have to extrude the letter $T$ in three different directions. The initial $T$ is shown in Figure 2.

Figure 2

If we multiply the first segment of $T$ with red, we get Figure 3 as shown.

Figure 3

If we fill the surface with different colors, then we will use the combination of colors. As shown in Figure 4, red and red turns to be red, blue and red turns to be magenta, and green and red turns out to be yellow.

Figure 4

Figure 5 shows the border of the surface and makes it clearer that we multiplied red. Figure 6 shows the two $T's$ that we get when we extrude one time.

Figure 5

Figure 6

Now, we will multiply the original $T$ with a blue segment in the front as shown in Figure 7. Here, we have multiplied blue segment.

Figure 7

Figure 8 shows the combination of colors applied in extrusion. We get blue when we combine blue and blue, and green and blue gives you cyan.

Figure 8

Figure 9 and 10 shows that we multiplied blue segment the second time and we get new T's respectively.

Figure 9

Figure 10

Now, we will extrude the original $T$ third time, but with the green segment. Figure 11 shows all the three extrusions from the center $T$. Figure 12 shows the combination of colors used on the surface.

Figure 11

Figure 12

Here, the above image is the cartesian product of $T \times T$ and our goal next would be to find the diagonal points here. Figure 13 shows the $T's$ that you get from extrusion and Figure 14 shows the multiplying segment.

Figure 13

Figure 14

Figure 15 to 20 are different view angle for the cartesian product $T \times T$.

Figure 15

Figure 16

Figure 17

Figure 18

Figure 19

Figure 20

Now, let's try to find out the diagonal for this problem. We know that diagonal are the points where two robots are overlapping. Let's think of only when the robots are overlapping on the red segment. If both the robots are in the same segment, then their diagonal should be somewhere on the red plane in the cartesian product. We get the diagonal as shown in Figure 21.

Figure 21

Similarly, we get the diagonal when both robots are on blue segment and green segment as shown in Figure 22 and 23 respectively.

Figure 22

Figure 23

To find the final configuration, we need to transform this image into simpler image, so that we can easily solve the problem. First, we split the diagonal attached with red plane and we get the following figure as in Figure 24. In Figure 25, the figure has been slightly changed by shifting some part of the configuration space.

Figure 24

Figure 25

Figure 26 is the side view of the above Cartesian product.

Figure 26

Figure 27 shows the separation of diagonal between blue plane and that plane is flipped along X-axis.

Figure 27

In Figure 28, the yellow, half blue, and two half green are flipped and are pointed up.

Figure 28

Figure 29 is the front view of Figure 28 which shows a proper view of the flipped surface.

Figure 29

Finally, we rotate the half blue, magenta and cyan to get a shape like flower as shown in figure 30.

Figure 30

To better understand the configuration space of $T \times T$, lets first look at Figure 31. This is a black and white version of the configuration space.

Figure 31

Figure 32 shows the border line of the plane of half cutted diagonal. We can also see that the two half cutted red, blue and green plane are opposite of each other.

Figure 32

Figure 33 shows the border color line for all the surfaces of the configuration space.

Figure 33

Figure 34 completes the figure by coloring each surfaces by appropriate colors. We can observe that the magenta, cyan and yellow surfaces are opposite to each other.

Figure 34

We know that to find the topological complexity of the above figure is difficult. Therefore, we use the Farber's theorem which we discussed in our last post. Farber's Theorem 2 said that "$TC(X)$ depends only on the homotopy type of $X$." This theorem proves that if $X$ is homotopic to $Y$, then $TC(X)=TC(Y)$. If we see Figure 34 from top view, we get Figure 36.

Figure 35

If we contract the diagonal plane down to the full plane, we get Figure 36. Remember that we have to remove the central point as it is the point where two robots overlap at the center of $T$. Therefore, there is hole there.