Equations an Solution for 2 robots moving on circle
Regions: Areas of Regions 1 & 2
Regions 1 & 2:
These regions were described previously in the post "Two robots moving in a circle". In summary, call region 1 to the flat drawing of our configuration of space without any alteration; Region 2 would be the flat drawing of the configuration of space for the two robots moving in a circle but already transformed to a cylindrical flat drawing. It is important to have this transformation in mind since regions 1 and 2 are topologically equal, geometrically they are different. Dealing with the geometry of this flat drawing will be essential to present our solution to the two robots moving in a circle problem.
Areas $A_U$, $A_D$, sub-areas$A_2, A_4, A_1 and A_3$ and tranformations.-
On Region 2:
$A_D=A_2+A_4$
$A_{UT}=A_{1T}+A_{3T}$
$A_2=A_4 - A_D$
$A_{1T}=A_{3T}+A_{DT}$
Special cases.-
$A_{3T}$
$x<y<-x+\ \frac{1}{2}$
$A_4$
$x>y>-x+\ \frac{8}{5}$
Antipodal and Non-Antipodal Cases:
Identification of an Antipodal and Non-Antipodal case.-
Antipodal if $(x_0+y_0)-(x'_0+y'_0)= \mathbb{Z}$
Non Antipodal if $(x_0+y_0)-(x'_0+y'_0) \neq \mathbb{Z}$
Antipodal Cases:
Antipodal case in $A_2$ and $A_{1T}$.-
$A_2$, then $P(x_0,y_0)$
$A_{1T}$, then $P(x_0,y_0 - 1)$
$A_{1T}$, then $P(x_0,y_0 - 1)$
Deformation line for point $P(x_0,y_0)$.-
$y=-x+(x_0+y_0)$
Interception between deformation line and Antipodal circle for point $P(x_0,y_0)$.-
$( \frac {x_0+y_0}{2} + \frac {1}{4} , \frac {x_0+y_0}{2} - \frac {1}{4})$
Deformation line for point $P(x_0,y_0 - 1)$.-
$y=-x+(x_0+y_0 - 1)$
Interception between deformation line and Antipodal circle for point $P(x_0,y_0 - 1)$.-
$( \frac {x_0+y_0}{2} - \frac {1}{4} , \frac {x_0+y_0}{2} - \frac {3}{4})$
Antipodal Case in $A_{3T}$ and $A_4$.-
For $A_{3T}$:
Deformation line.- $y=-x+(x_0+y_0 - 1)$
Interception between deformation line and Antipodal circle.-
$( \frac {x_0+y_0}{2} + \frac {3}{4} , \frac {x_0+y_0}{2} + \frac {1}{4})$
For $A_4$.-
Deformation line.- $y=-x+(x_0+y_0)$
Interception between deformation line and Antipodal circle,-
$( \frac {x_0+y_0}{2} - \frac {3}{4} , \frac {x_0+y_0}{2} - \frac {5}{4})$
Algorithm for antipodal case.-
Since the distance is constant when the pairs a strictly antipodal, our algorithm for this case will be to go clockwise.
Non-Antipodal Cases:
When $(x_0+y_0)-(x'_0+y'_0) \neq \mathbb{Z}$, then we have a non-antipodal case.
Non-Antipodal case in $A_2$ and $A_{1T}.-
The generic equations for antipodal cases will also apply for non-antipodal cases, but the difference will be in the algorithm that we will create for this specific case.
Algorithm for non-antipodal case.-
In this case, the algorithm will be for the two robots, when laying on the Strictly Antipodal Circle (SAC) while having a distance $d \neq \frac {\sqrt {2}}{2}$, go the shortest path from initial intersection to final intersection.
Shortest path.-
Depending on the on the distance between two points laying on SAC, the shortest distance will always vary. Therefore, we will have to set some conditions in order to classify different cases:
$$d > \frac{\sqrt {2}}{2} \rightarrow d_{move}= d - \frac{\sqrt {2}}{2}$$ $$d \frac{\sqrt {2}}{2}\rightarrow d_{move}=d $$
Algorithm for one robot moving on number $8$ and a bouquet of seven petals
In this post, we will find the algorithm for a robot moving on an $8$(bouquet of two circles) and on a bouquet of seven petals. To find that we need to know what is the topological complexity $TC$. If the section is discontinuous, then we can divide the Cartesian product into local domains, so that in each domains section is continuous. The number of $TC$ tells us how many local domains we have.
We know that sections are the functions which take two points on Cartesian product and gives a path between them as an output.
$$s: 8 \times 8 \to P8$$
As we know that figure, $8$ is not contractible to a point, and according to Farber's theorem, the section is discontinuous.
We know that sections are the functions which take two points on Cartesian product and gives a path between them as an output.
$$s: 8 \times 8 \to P8$$
As we know that figure, $8$ is not contractible to a point, and according to Farber's theorem, the section is discontinuous.
Also, physical and configuration space in both the problems will be the same($8$ and a bouquet of seven petals).
In our last post, we founded that the $TC$ for a robot moving on an $8$ and on a bouquet of seven petals is $3$. Now, we need to find what are those three different rules to give an explicit algorithm. Here, the local sections are called rules, or instructions, and the algorithm would be the set of instructions.
Let's look at some of the examples of both the problems and then finalize our algorithm. In both our case, the initial and final position of a robot is a blank circle and solid circle respectively. Let's also call the vertex(0) of the graph as our center and the points antipodal to the center as poles in all circles. After looking at these examples, we will be able to figure out three algorithms for both 8 and a bouquet of seven petals.
Let's look at some of the examples of both the problems and then finalize our algorithm. In both our case, the initial and final position of a robot is a blank circle and solid circle respectively. Let's also call the vertex(0) of the graph as our center and the points antipodal to the center as poles in all circles. After looking at these examples, we will be able to figure out three algorithms for both 8 and a bouquet of seven petals.
Finding the three algorithms for a robot moving on an 8:
If the position is in the blue circle and in the red circle, then we will use $xB$ and $yR$ as the notation respectively where $(x,y \in [0,2π])$.
Now, let's recall Farber's definition.
Now, let's recall Farber's definition.
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)$. We know that $TC$ of an $8$ is $3$. This means that we have to divide the Cartesian product of an $8$ into three different domains $U$, $V$ and $W$. It also means that three commands are given to a robot moving on an $8$.
We have to divide the configuration space $8 \times 8$ into three domains such that $$8 \times 8 = U \cup V \cup W$$
where $U$, $V$ and $W$ are the local domains of $8 \times 8$.
Let's consider the first domain as the region where we take the shortest path and then, we can find what positions would cause the discontinuity. Following is the first domain and section function respectively for the shortest path:
$U \subset 8 \times 8$, where $$U = \{(x, y)| \mbox{ we will move from x to y following the shortest distance}\}$$
$$s_1: U \rightarrow P8$$We will find the precise domain $U$ after analyzing our entire problem.
Example 1: Travel from $π/2B$ to $7π/4B$.
The movement for this example is shown in Figure 1.
 |
| Figure 1: First problem shortest path |
The movement is shown in Figure 2.
 |
| Figure 2: Second problem shortest path |
The movement is shown in Figure 3.
 |
| Figure 3: Third problem shortest path |
The movement is shown in Figure 4.
 |
| Figure 4: Fourth problem shortest path |
Example 5: Travel from $π/4R$ to $πB$(pole).
Possible movements are shown in Figure 5.
 |
| Figure 5: Fifth problem shortest path(section discontinuous) |
Possible movements are shown in Figure 6.
 |
| Figure 6: Sixth problem shortest path(section discontinuous) |
Possible movements are shown in Figure 7.
 |
| Figure 7: Seventh problem shortest path(section discontinuous) |
Possible movements are shown in Figure 8.
 |
| Figure 8: Eighth problem shortest path(section discontinuous) |
$V \subset 8 \times 8$, where $$V = \{(x, y)| \mbox{case i) both positions of a robot are in the same circle and are antipodal, and case ii) both positions are}$$ $$\mbox{in different circle, and only one position is at the poles}\}$$
$$s_2: V \rightarrow P8$$In case i, the robot will move in a clockwise direction. In case ii, the robot will move to the center in a clockwise/shortest path followed by shortest path/clockwise direction, respectively.
Figure 9 to 12 shows the results for example 5- 8, respectively. For these examples, section $s_2$ is continuous.
 |
| Figure 9: Fifth problem- Section $s_2$ |
 |
| Figure 10: Sixth problem- Section $s_2$ |
 |
| Figure 11: Seventh problem- Section $s_2$ |
 |
| Figure 12: Eighth problem- Section $s_2$ |
Example 9: Travel from $πB$(pole) to $πR$(pole).
Possible movements are shown in Figure 13.
Example 10: Travel from $πR$(pole) to $πB$(pole).
Possible movements are shown in Figure 14.
Here, the robot will move in the clockwise direction twice.
Figure 15 to 16 shows the results for example 9 and 10, respectively. For these examples, section $s_3$ is continuous.
From all the above examples, the three algorithms for a robot moving an $8$ is as shown below:
Possible movements are shown in Figure 13.
 |
| Figure 13: Ninth problem shortest path(section discontinuous) |
Possible movements are shown in Figure 14.
 |
| Figure 14: Tenth problem shortest path(section discontinuous) |
If we want to include pairs of examples 9 and 10 in the domain $U$ and $V$, then the section $s_1$ and $s_2$ would not be continuous. Therefore, we need a third domain $W$ here.
$W \subset 8 \times 8$, where $$W = \{(8, 8)| \mbox{both positions are at the poles}\}$$
$$s_3: W \rightarrow P8$$Here, the robot will move in the clockwise direction twice.
Figure 15 to 16 shows the results for example 9 and 10, respectively. For these examples, section $s_3$ is continuous.
 |
| Figure 15: Ninth problem clockwise direction(two antipodals) |
 |
| Figure 16: Tenth problem clockwise direction(two antipodals) |
Rules for a robot moving on a number $8$:
Rule 1: If the initial and the final position of a robot are in the same circle and are non-antipodal or they are in different circles, and neither initial or final position is at poles, then the robot will take the shortest path.Rule 2: If both positions of a robot are in the same circle and are antipodal, or both positions are in different circle, and only one position is at the poles, then the robot will move in clockwise direction or will move to the center clockwise/shortest path followed by shortest path/clockwise, respectively.
Rule 3: If the initial and final position of the robot is at the poles, then the robot will take the clockwise direction from the initial to the center and then followed by the clockwise direction to reach the final position.
Section and Domain for a robot moving on an $8$:
$U \subset 8 \times 8$ where $$U = \{(x, y)| \mbox{case i) pairs are in the same circle and are non-antipodal, and case ii) pairs are in different circles}\}$$
$$s_1: U \rightarrow P8$$ or
$$s_1= \mbox{shortest distance}$$
$V \subset 8 \times 8$, where $$V = \{(x, y)| \mbox{case i) both positions of a robot are in the same circle and are antipodal, and case ii) both positions are}$$ $$\mbox{in different circle, and only one position is at the poles}\}$$
$$s_2: V \rightarrow P8$$ or
$$s_2= \mbox{for case i, the robot will move in a clockwise direction and for case ii, it will move to the center in clockwise/}$$ $$\mbox{shortest path followed by shortest path/clockwise}$$
$W \subset 8 \times 8$, where $$W = \{(x, y)| \mbox{both positions are at the poles}\}$$
$$s_3: W \rightarrow P8$$ or
$$s_3= \mbox{move in clockwise direction twice}$$Find the three algorithms for the robot moving on a bouquet of seven petals:
Figure 17 shows our figure of a bouquet of seven poles. We will consider all the points antipodal to the vertex as poles and vertex as the center. For the notation of initial position, we will use $mX$ and the final position as $nX$, where $m, n \in [0, 2π]$ and $X \in {A, B, C, D, E, F, G}$. We will denote bouquet of seven petals as $7$.
 |
| Figure 17: Original bouquet of seven petals |
We have to divide the configuration space $7 \times 7$ into three domains such that $$7 \times 7 = U \cup V \cup W$$
where $U$, $V$ and $W$ are the local domains of $7 \times 7$.
Let's consider the first domain as the shortest path and then, we can find what positions are causing the discontinuity. Following is the first domain and section function respectively for the shortest path:
$U \subset 7 \times 7$, where $$U = \{(x, y)| \mbox{All pairs of points where the shortest distance between initial and final position is applied}\}$$
$$s_1: U \rightarrow P7$$We will find the precise domain $U$ after analyzing our complete problem.
Example 1: Travel from $π/4E$ to $πE$.
Movement is shown in Figure 18.
 |
| Figure 18: First problem shortest path |
Movement is shown in Figure 19.
 |
| Figure 19: Second problem shortest path |
The movement is shown in Figure 20.
 |
| Figure 20: Third problem shortest path |
The movement is shown in Figure 21.
 |
| Figure 21: Fourth problem shortest path |
The movement is shown in Figure 22.
 |
| Figure 22: Fifth problem shortest path |
Example 6: Travel from $0B$ to $πB$.
Possible movements are shown in Figure 23.
 |
| Figure 23: Sixth problem shortest path(section discontinuous) |
Possible movements are shown in Figure 24.
 |
| Figure 24: Seventh problem shortest path(section discontinuous) |
Possible movements are shown in Figure 25.
 |
| Figure 25: Eight problem shortest(section discontinuous) |
Possible movements are shown in Figure 26.
 |
| Figure 26: Ninth problem shortest(section discontinuous) |
If we want to include pairs of examples 6-9 in the domain $U$, then the section $s_1$ would not be continuous. Therefore, we need a second domain $V$ here.
$V \subset 7 \times 7$, where $$V = \{(x, y)| \mbox{ case i) both positions of a robot are in the same petal and are antipodal, and case ii) both positions are}$$ $$\mbox{in different petals and only one position is at the poles}\}$$
$$s_2: V \rightarrow P7$$In case i, the robot will move in a clockwise direction. In case ii, the robot will move to the center in a clockwise/shortest path followed by shortest path/clockwise direction, respectively.
 |
| Figure 27: Sixth example- Section $s_2$ |
 |
| Figure 28: Seventh example- Section $s_2$ |
 |
| Figure 29: Eighth example- Section $s_2$ |
 |
| Figure 30: Ninth example- Section $s_2$ |
Possible movements are shown in Figure 31.
 |
| Figure 31: Tenth problem shortest(section discontinuous) |
Possible movements are shown in Figure 32.
Here, the robot will move in a clockwise direction twice.
Figure 33 to 34 shows the results for example 10 and 11, respectively. For these examples, section $s_3$ is continuous.
Algorithm 2: If both positions of a robot are in the same petal and are antipodal, or both positions are in different petal, and only one position is at the poles, then the robot will move in the clockwise direction or will move to the center in clockwise/shortest path followed by shortest path/clockwise, respectively.
Algorithm 3: If the initial and final position of the robot is at the poles, then the robot will take the clockwise direction from the initial to the center and then followed by the clockwise direction to reach the final position.
 |
| Figure 32: Eleventh problem shortest(section discontinuous) |
If we want to include pairs of examples 10 and 11 in the domain $U$ and $V$, then the section $s_1$ and $s_2$ would not be continuous. Therefore, we need a third domain $W$ here.
$W \subset 7 \times 7$, where $$W = \{(x, y)| \mbox{both positions are at the poles}\}$$
$$s_3: W \rightarrow P8$$Here, the robot will move in a clockwise direction twice.
Figure 33 to 34 shows the results for example 10 and 11, respectively. For these examples, section $s_3$ is continuous.
 |
| Figure 33: Tenth problem- Section $s_3$ |
 |
| Figure 34: Eleventh problem- Section $s_3$ |
From all above examples, three algorithms for a robot moving on a bouquet of seven petals are as follows.
Algorithm for a robot moving on a bouquet of $7$ petals:
Algorithm 1: If the initial and the final position of a robot are in the same petal and are non-antipodal, or they are in different petals, and neither initial or final position is at poles, then the robot will take the shortest path.
Algorithm 2: If both positions of a robot are in the same petal and are antipodal, or both positions are in different petal, and only one position is at the poles, then the robot will move in the clockwise direction or will move to the center in clockwise/shortest path followed by shortest path/clockwise, respectively.
Algorithm 3: If the initial and final position of the robot is at the poles, then the robot will take the clockwise direction from the initial to the center and then followed by the clockwise direction to reach the final position.
Section and Domain for a robot moving on a bouquet of seven petals:
$U \subset 7 \times 7$, where $$U = \{(x, y)| \mbox{ case i) pairs are in the same petal and are non-antipodal, and case ii) they are in different petals}\}$$
$$s_1: U \rightarrow P7$$ or
$$s_1= \mbox{shortest distance}$$
$V \subset 7 \times 7$, where $$V = \{(x, y)| \mbox{case i) both positions of a robot are in the same petal and are antipodal, and case ii) both positions are}$$ $$\mbox{in different petals and only one position is at the poles}\}$$
$$s_2: V \rightarrow P7$$ or
$$s_2= \mbox{for case i, the robot will move in a clockwise direction and for case ii, it will move to the center in clockwise/}$$ $$\mbox{shortest path followed by shortest path/clockwise}$$
$W \subset 7 \times 7$, where $$W = \{(x, y)| \mbox{both positions are at the poles}\}$$
$$s_3: W \rightarrow P7$$ or
$$s_3= \mbox{move in clockwise direction twice}$$
Posted by Chintan Patel.
Topology and complexity
Check this lecture by Professor Weinberger:
https://www.simonsfoundation.org/event/topology-and-complexity/
https://www.simonsfoundation.org/event/topology-and-complexity/
Farber's theorem for Topological Complexity $TC$ and $TC$ of a robot moving on $8$ and a bouquet of seven circles.
In this post, we will be introducing Farber's other theorems that will be helpful to us to find the topological complexity of one robot moving on number $8$ and on a bouquet of $7$ circles.
Farber's Theorem $1$: "For any path-connected paracompact locally contractible space $X$ one has
where $\dim X$ denotes the covering dimension of $X$. "
This means that if we know the dimension of any space $X$, then we can find the upper bound of the $TC(X)$. For example, if the space is a circle, then its dimension is $1$. Therefore, the upper bound for the $TC(S^1)$ of a robot moving on a circle $S^1$ is $3$, i.e., $TC(S^1) \leq 3$. If space is a sphere $S^2$, then its dimension is $2$. Therefore, $TC(S^2) \leq 5$.
Also, Farber gave a Lemma on finding the $TC(X)$ using the Lusternik-Schnirelmann Category $cat(X)$. Below is the Lemma:
Farber's Lemma $1$: "One has
John Oprea and Jeff Strom(2010) in their paper "Lusternik-Schirelmann category, complements of skeleta and a theorem of Dranishnikov" stated the definition of Lusternik-Schirelmann category $cat(X)$ as:
"The Lusternik–Schnirelmann category of a space $X$, denoted $cat(X)$, is the smallest integer $m$ so that $X$ can be covered by open sets $U_0, U_1, \cdots, U_m$, each of which is contractible to a point in $X$."
This means that any space $X$ can be divided into smallest integer $m$ such that each part is contractible to a point in space $X$ itself. For example, if the space is a circle $S^1$, then the $cat(S^1)$ will be $2$ because there are two minimum open sets(curve) which will be contractible to a point in space $S^1$.
Now, if we use the rule of inequalities and combine the Theorem $1$ and Lemma $1$, we will get:
$$cat(X) \leq TC(X) \leq 2\dim X +1$$
For the case of circle $S^1, cat(S^1)$ is $2$ and $dim S^1$ is $1$. Therefore, we will have:
$$2 \leq TC(S^1) \leq 3.$$
We already solved this problem in one of our last posts as we founded that the $TC(S^1)$ is $2$. Our challenge is to find the $TC$ of a robot moving on a number $8$ and on the bouquet of seven circles.
We know that the $cat(8)$ and of the bouquet of seven circles is $2$ and their dimension is $1$. Therefore, we get:
$$2 \leq TC(S^1) \leq 3.$$
Now, we have to find the exact $TC$ to solve our problem. Let's introduce the new theorem of Farber based on graphs and Betti numbers of independent 1-dimensional space $b_1$.
Farber's Theorem $2$: "If $X$ is a connected finite graph then
$$TC(X) =
\begin{cases}
1 & \text {if} \, b_1(X) =0, \\
2 & \text{if} \, b_1(X)=1, \\
3 & \text{if} \, b_1(X) > 1.
\end{cases}
$$
Here, a graph(as in Graph Theory) is something where there are points in space called vertices, and they are connected by a line called edges. Betti numbers $b_t$ are the total numbers of $t$-independent higher dimensional surfaces(or $t$ dimensional holes) in any space $X$. To find the 1st-Betti numbers of graphs, the formula is $m-n+k$ where $m$ is edges, $n$ is vertices, and $k$ is the total numbers of connected components of the graph. This formula can only be used to find 1st-Betti numbers(i.e. it is not applicable when $t \neq 1$). To understand Betti numbers in depth, watch this lecture on Homology and to learn more about graph theory, read this article.
To understand it more clearly, let's take an example of $8$ as shown in Figure $1$. Here, there is only one vertex $1$ which is the center of $8$ and two edges(loops). Now, Betti numbers of $1$-independent higher dimensional surfaces $b_0$ is $1$, $1$-dimensional surface $b_1$ is $2$, and $2$-dimensional surface $b_2$ is $0$.
Now, if the graph(space) is a line, then there is one edge, two vertices, and one connected component. According to the formula to find the Betti number $b_1$ of a graph, we get:
$$m-n+k=1-2+1=0$$
From above theorem, we know that $b_1$ is $0$ and so, the $TC$ is 1.
If the graph is a circle $S^1$, then there is one edge, one vertex, and one connected component. So, $b_1$ will be 1. Therefore, from the theorem, $TC$ of a robot moving on a circle will be $2$.
We know that space $8$ and a bouquet of seven circles are connected finite graphs. Also, for the space $8$:
$$b_1(8)=m-n+k=2-1+1$$
and for bouquet of seven circles (rose with seven petals), $b_1$ is $7$($m-n+k=7-1+1$). According to the above theorem, in both our cases, $b_1(X) >1$. Therefore, the topological complexity of a robot moving on a number $8$ and on a bouquet of seven circles is $3$, i.e., $TC=3$.
Farber, Michael (2005) Topology of Robot Motion Planning, Springer. Printed in the Netherlands., 195-240.
Oprea, John; Strom, Jeff Lusternik-Schnirelmann category, complements of skeleta and a theorem of Dranishnikov. Algebr. Geom. Topol. 10 (2010), no. 2, 1165–1186.
Posted by Chintan Patel.
Farber's Theorem:
Michael Farber gave a theorem which gives the upper bound for $TC(X)$. The theorem is as below:Farber's Theorem $1$: "For any path-connected paracompact locally contractible space $X$ one has
$TC(X) \leq 2\dim X + 1$
where $\dim X$ denotes the covering dimension of $X$. "
This means that if we know the dimension of any space $X$, then we can find the upper bound of the $TC(X)$. For example, if the space is a circle, then its dimension is $1$. Therefore, the upper bound for the $TC(S^1)$ of a robot moving on a circle $S^1$ is $3$, i.e., $TC(S^1) \leq 3$. If space is a sphere $S^2$, then its dimension is $2$. Therefore, $TC(S^2) \leq 5$.
Also, Farber gave a Lemma on finding the $TC(X)$ using the Lusternik-Schnirelmann Category $cat(X)$. Below is the Lemma:
Farber's Lemma $1$: "One has
$cat(X) \leq TC_2(X) \leq cat(X \times X).$ "
Mathematician Lazar Lyusternik and Lev Schirelmann first introduced the definition of Lusternik- Schirelmann category $cat(X)$.
John Oprea and Jeff Strom(2010) in their paper "Lusternik-Schirelmann category, complements of skeleta and a theorem of Dranishnikov" stated the definition of Lusternik-Schirelmann category $cat(X)$ as:
"The Lusternik–Schnirelmann category of a space $X$, denoted $cat(X)$, is the smallest integer $m$ so that $X$ can be covered by open sets $U_0, U_1, \cdots, U_m$, each of which is contractible to a point in $X$."
This means that any space $X$ can be divided into smallest integer $m$ such that each part is contractible to a point in space $X$ itself. For example, if the space is a circle $S^1$, then the $cat(S^1)$ will be $2$ because there are two minimum open sets(curve) which will be contractible to a point in space $S^1$.
Now, if we use the rule of inequalities and combine the Theorem $1$ and Lemma $1$, we will get:
$$cat(X) \leq TC(X) \leq 2\dim X +1$$
For the case of circle $S^1, cat(S^1)$ is $2$ and $dim S^1$ is $1$. Therefore, we will have:
$$2 \leq TC(S^1) \leq 3.$$
We already solved this problem in one of our last posts as we founded that the $TC(S^1)$ is $2$. Our challenge is to find the $TC$ of a robot moving on a number $8$ and on the bouquet of seven circles.
Topological Complexity of a robot moving on 8 and a bouquet of seven circles:
We know that the $cat(8)$ and of the bouquet of seven circles is $2$ and their dimension is $1$. Therefore, we get:
$$2 \leq TC(S^1) \leq 3.$$
Now, we have to find the exact $TC$ to solve our problem. Let's introduce the new theorem of Farber based on graphs and Betti numbers of independent 1-dimensional space $b_1$.
Farber's Theorem $2$: "If $X$ is a connected finite graph then
$$TC(X) =
\begin{cases}
1 & \text {if} \, b_1(X) =0, \\
2 & \text{if} \, b_1(X)=1, \\
3 & \text{if} \, b_1(X) > 1.
\end{cases}
$$
Here, a graph(as in Graph Theory) is something where there are points in space called vertices, and they are connected by a line called edges. Betti numbers $b_t$ are the total numbers of $t$-independent higher dimensional surfaces(or $t$ dimensional holes) in any space $X$. To find the 1st-Betti numbers of graphs, the formula is $m-n+k$ where $m$ is edges, $n$ is vertices, and $k$ is the total numbers of connected components of the graph. This formula can only be used to find 1st-Betti numbers(i.e. it is not applicable when $t \neq 1$). To understand Betti numbers in depth, watch this lecture on Homology and to learn more about graph theory, read this article.
To understand it more clearly, let's take an example of $8$ as shown in Figure $1$. Here, there is only one vertex $1$ which is the center of $8$ and two edges(loops). Now, Betti numbers of $1$-independent higher dimensional surfaces $b_0$ is $1$, $1$-dimensional surface $b_1$ is $2$, and $2$-dimensional surface $b_2$ is $0$.
Now, if the graph(space) is a line, then there is one edge, two vertices, and one connected component. According to the formula to find the Betti number $b_1$ of a graph, we get:
$$m-n+k=1-2+1=0$$
From above theorem, we know that $b_1$ is $0$ and so, the $TC$ is 1.
If the graph is a circle $S^1$, then there is one edge, one vertex, and one connected component. So, $b_1$ will be 1. Therefore, from the theorem, $TC$ of a robot moving on a circle will be $2$.
 |
| Figure 1: Graph with vertex (1} and two edges(loops) |
$$b_1(8)=m-n+k=2-1+1$$
and for bouquet of seven circles (rose with seven petals), $b_1$ is $7$($m-n+k=7-1+1$). According to the above theorem, in both our cases, $b_1(X) >1$. Therefore, the topological complexity of a robot moving on a number $8$ and on a bouquet of seven circles is $3$, i.e., $TC=3$.
References:
Farber, Michael (2005) Topology of Robot Motion Planning, Springer. Printed in the Netherlands., 195-240.
Oprea, John; Strom, Jeff Lusternik-Schnirelmann category, complements of skeleta and a theorem of Dranishnikov. Algebr. Geom. Topol. 10 (2010), no. 2, 1165–1186.
Posted by Chintan Patel.
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???
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.
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 29 shows the initial configuration point and final configuration point in the Flower while Figure 30 shows those points on the 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.
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 28: Example 2- Physical Space |
 |
| Figure 29: Example 2- Flower |
 |
| Figure 30: Example 2- Star |
 |
| Figure 31: Example 2- Movement in Star |
 |
| Figure 32: Example 2- Movement in Flower |
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)$.
In Figure 37, the initial and final position is shown using a black triangle on the general configuration space.
Figure 38 shows that the initial and final position in the different half red plane.
If we contract both the red planes, the antipodal points will also contract as shown in Figure 39.
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.
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 42 shows the second shift from the point $(7.5R, 0B)$ to $(6.5R, 1B)$.
Figure 43 shows the third shift from the point $(6.5R, 1B)$ to $(1G, 1B)$.
Figure 44 shows the fourth shift from the point $(1G, 1B)$ to $(1G, 0R)$.
Figure 45 shows the fifth shift from the point $(1G, 0R)$ to $(0R, 1R)$ and finally, to the final position $(2.5R, 10R)$.
 |
| Figure 35: Example 3- Initial position in physical space |
 |
| Figure 36: Example 3- Final position in physical point |
 |
| Figure 37: Example 3- Configuration points in original $T \times T$ |
 |
| Figure 38: Example 3- Configuration points on Flower |
 |
| Figure 39: Example 3- Configuration points on Star |
 |
| 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: Example 3- Second shift in the physical space |
 |
| Figure 43: Example 3- Third shift in the physical space |
 |
| Figure 44: Example 3- Fourth shift in the physical space |
 |
| 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 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 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.
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.
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.
 |
| 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: Example 4- Configuration point in the Flower |
 |
| Figure 50: Example 4- Path between two antipodal points |
 |
| Figure 51: Example 4- Shifting in the physical space |
Posted by: Chintan Patel
October 28th, 2017, 4:00 pm
Subscribe to:
Posts (Atom)