In this post, we will learn everything that we need to make a robot move on a circle $S^1$ on its own. To do that, I will introduce Farber's Theorem later on this post.
We know that sections are the functions which take two points on Cartesian product and gives any path between them as an output.
$$s:S^1 \times S^1 \to PS^1$$
Let's look at some example of sections with the help of Cartesian product $S^1 \times S^1$.
Example 1: If we give the command to a robot to move to the shortest path, then the following Figure 1 illustrates the initial and final position of a robot and its path in Physical Space. We can also plug a pair of initial and final points in the Cartesian product $S^1 \times S^1$. Example for that is shown in Figure 2.
Example 2: If we assign an algorithm to a robot to move counterclockwise, then its initial and final position and its path are shown in physical space in Figure 3. Figure 4 shows that pair in the Cartesian product $S^1 \times S^1$.
Above, we saw two examples of a robot moving on a circle, but the problem arises because the section function is discontinuous. In one of our post, we discussed the continuity of sections and stated that the sections are continuous only if we have two points nearby, then the path between them should give a nearby path. Here, when a robot is given a command to take the shortest path to reach that point, the problem arises when the two points are antipodal to each other i.e. the section is not continuous as shown in Figure 5. In Figure 6, we have pairs of all the antipodal points on cartesian product $S^1 \times S^1$ described as a curve and are discontinuous at all points on that curve.
Now, to solve that problem, we will use Farber's theorem and his definition of Topological complexity.
Farber's Theorem 1: "A continuous motion planning $s: X \times X \to PX$ exists if and only if the configuration space $X$ is contractible."
This theorem says that if the configuration space is contractible i.e. homotopic to a point, then the continuous motion planning exists (i.e. section is continuous).
But, in our case, our configuration space is a circle which is not contractible to a point and hence, our section is discontinuous. For that, Farber gave a definition of Topological Complexity in his paper answering this problem.
Farber's definition: "Given a path-connected topological space $X$, we define the topological complexity of the motion planning in $X$ as the minimum number $TC(X)=k$, such that the Cartesian product of $X \times X$ may be covered by $k$ open subsets
$$X \times X = U_1 \cup U_2 \cup U_3 \cup \cdots \cup U_k $$
such that for any $i=1,2, ... , k$ there exists a continuous motion planning $s_i: U_i \to PX$, $ \pi \circ s_i = id \, over \, U_i $. If no such $k$ exists we will set $TC(X)= \infty $"
This theorem says that, if the section is discontinuous, then the Cartesian product can be divided into $k$ open subsets over each of which there is a continuous section. Here, $k$ is the number of Topological Complexity$(TC)$. For example, we will see here that the topological complexity of a circle is 2. This means that we have to divide the Cartesian product of the circle into two different domains $U_1$ and $U_2$. It also means that two commands are given to a robot which is moving on a circle.
Here, is the second theorem of Farber which we will use in our next post.
Farber's Theorem 2: "$TC(X) $ depends only on the homotopy type of $X$."
This theorem basically proves that if some space $X$ is homotopy to space $Y$, then $TC(X)=TC(Y)$. Just keep this theorem in mind, we will use it in the problem of $T$.
We discussed Farber's Theorem 1 which said that continuous motion planning exists if and only if space X is contractible. In our case, a circle is not contractible to a point because there is a hole in it. Therefore, Farber's Theorem proves that the sections for $C^1(S^1)$ are discontinuous.
Farber's main reason for introducing topological complexity and this theorem was to solve the problem of the discontinuity of the sections in all configuration spaces. Above, we discussed the definition of topological complexity $TC$ which was given by Farber.
Topological complexity $TC$ is a number $k$ which counts how many discontinuity processes are there in motion planning in a configuration space X. We will use this number $k$ to divide the Cartesian product $ X \times X $ into the total number $k$ such that $ X \times X = U_1 \cup U_2 \cup \cdots \cup U_k $.
Since the topological complexity, ${TC}$ is not one, we are going to partition $ S^1 \times S^1 $ into smaller sets. According to Farber's definition, we divide the configuration space $ S^1 \times S^1$ into two domains such that $$ S^1 \times S^1 = U_1 \cup U_2 $$
where $ U_1 $ and $ U_2 $ are the local domains. Here, antipodal points are the points which cause discontinuity, therefore one local domain consists of all antipodal points and remaining points in the other domain. Hence, domain which contains all non-antipodal points is $ U_1 \subset S^1 \times S^1 $ where $ U_1 = \{(A,B); A \neq -B\} $. For example, one of the section which is continuous in this domain is the shortest distance between $ A $ and $B$ given by $ s_1: U_1 \rightarrow PS^1 $ which takes pairs of all points as an input except antipodal points and gives the shortest path as an output. The second domain which contains the antipodal points is $ U_2 \subset S^1 \times S^1 $ where $ U_2 = \{(A,B); A= -B\} $. One of the examples of the motion planning for this domain is to give a command to a robot to move in a clockwise direction from $A$ to point $B$. This is given by section $ s_2: U_2 \rightarrow PS^2 $ which takes pairs of antipodal points as an input and gives a path which goes in a clockwise direction as an output.
We know that sections are the functions which take two points on Cartesian product and gives any path between them as an output.
$$s:S^1 \times S^1 \to PS^1$$
Let's look at some example of sections with the help of Cartesian product $S^1 \times S^1$.
Example 1: If we give the command to a robot to move to the shortest path, then the following Figure 1 illustrates the initial and final position of a robot and its path in Physical Space. We can also plug a pair of initial and final points in the Cartesian product $S^1 \times S^1$. Example for that is shown in Figure 2.
 |
| Figure 1 |
 |
| Figure 2 |
Example 2: If we assign an algorithm to a robot to move counterclockwise, then its initial and final position and its path are shown in physical space in Figure 3. Figure 4 shows that pair in the Cartesian product $S^1 \times S^1$.
 |
| Figure 3 |
 |
| Figure 4 |
Discontinuity of a Section: Antipodal Points:
Above, we saw two examples of a robot moving on a circle, but the problem arises because the section function is discontinuous. In one of our post, we discussed the continuity of sections and stated that the sections are continuous only if we have two points nearby, then the path between them should give a nearby path. Here, when a robot is given a command to take the shortest path to reach that point, the problem arises when the two points are antipodal to each other i.e. the section is not continuous as shown in Figure 5. In Figure 6, we have pairs of all the antipodal points on cartesian product $S^1 \times S^1$ described as a curve and are discontinuous at all points on that curve.  |
| Figure 5 |
 |
| Figure 6 |
Now, to solve that problem, we will use Farber's theorem and his definition of Topological complexity.
Farber's Theorem 1: "A continuous motion planning $s: X \times X \to PX$ exists if and only if the configuration space $X$ is contractible."
This theorem says that if the configuration space is contractible i.e. homotopic to a point, then the continuous motion planning exists (i.e. section is continuous).
But, in our case, our configuration space is a circle which is not contractible to a point and hence, our section is discontinuous. For that, Farber gave a definition of Topological Complexity in his paper answering this problem.
Farber's definition: "Given a path-connected topological space $X$, we define the topological complexity of the motion planning in $X$ as the minimum number $TC(X)=k$, such that the Cartesian product of $X \times X$ may be covered by $k$ open subsets
$$X \times X = U_1 \cup U_2 \cup U_3 \cup \cdots \cup U_k $$
such that for any $i=1,2, ... , k$ there exists a continuous motion planning $s_i: U_i \to PX$, $ \pi \circ s_i = id \, over \, U_i $. If no such $k$ exists we will set $TC(X)= \infty $"
This theorem says that, if the section is discontinuous, then the Cartesian product can be divided into $k$ open subsets over each of which there is a continuous section. Here, $k$ is the number of Topological Complexity$(TC)$. For example, we will see here that the topological complexity of a circle is 2. This means that we have to divide the Cartesian product of the circle into two different domains $U_1$ and $U_2$. It also means that two commands are given to a robot which is moving on a circle.
Here, is the second theorem of Farber which we will use in our next post.
Farber's Theorem 2: "$TC(X) $ depends only on the homotopy type of $X$."
This theorem basically proves that if some space $X$ is homotopy to space $Y$, then $TC(X)=TC(Y)$. Just keep this theorem in mind, we will use it in the problem of $T$.
We discussed Farber's Theorem 1 which said that continuous motion planning exists if and only if space X is contractible. In our case, a circle is not contractible to a point because there is a hole in it. Therefore, Farber's Theorem proves that the sections for $C^1(S^1)$ are discontinuous.
Farber's main reason for introducing topological complexity and this theorem was to solve the problem of the discontinuity of the sections in all configuration spaces. Above, we discussed the definition of topological complexity $TC$ which was given by Farber.
Topological complexity $TC$ is a number $k$ which counts how many discontinuity processes are there in motion planning in a configuration space X. We will use this number $k$ to divide the Cartesian product $ X \times X $ into the total number $k$ such that $ X \times X = U_1 \cup U_2 \cup \cdots \cup U_k $.
Local Domains and Sections for $C^1$($S^1$):
Since the topological complexity, ${TC}$ is not one, we are going to partition $ S^1 \times S^1 $ into smaller sets. According to Farber's definition, we divide the configuration space $ S^1 \times S^1$ into two domains such that $$ S^1 \times S^1 = U_1 \cup U_2 $$
where $ U_1 $ and $ U_2 $ are the local domains. Here, antipodal points are the points which cause discontinuity, therefore one local domain consists of all antipodal points and remaining points in the other domain. Hence, domain which contains all non-antipodal points is $ U_1 \subset S^1 \times S^1 $ where $ U_1 = \{(A,B); A \neq -B\} $. For example, one of the section which is continuous in this domain is the shortest distance between $ A $ and $B$ given by $ s_1: U_1 \rightarrow PS^1 $ which takes pairs of all points as an input except antipodal points and gives the shortest path as an output. The second domain which contains the antipodal points is $ U_2 \subset S^1 \times S^1 $ where $ U_2 = \{(A,B); A= -B\} $. One of the examples of the motion planning for this domain is to give a command to a robot to move in a clockwise direction from $A$ to point $B$. This is given by section $ s_2: U_2 \rightarrow PS^2 $ which takes pairs of antipodal points as an input and gives a path which goes in a clockwise direction as an output.
Posted by Chintan Patel
This is really great. Very good explanation.
ReplyDelete