Topological Robotics (Wilbur Wright College): November 2017

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.

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.

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.

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

Example 2: Travel from $πB$(pole) to $7π/4B$.
The movement is shown in Figure 2.

Figure 2: Second problem shortest path

Example 3: Travel from $5π/4R$ to $7π/4B$.
The movement is shown in Figure 3.

Figure 3: Third problem shortest path

Example 4: Travel from $5π/4R$ to $0R$(center).
The movement is shown in Figure 4.

Figure 4: Fourth problem shortest path

For all the examples from 1- 4, the section $s_1$ is continuous. We know that $TC$ is $3$, and therefore, we know that at some position, section $s_1$ is discontinuous. Let's see some more examples.

Example 5: Travel from $π/4R$ to $πB$(pole).
Possible movements are shown in Figure 5.

Figure 5: Fifth problem shortest path(section discontinuous)

Example 6: Travel from $5π/4R$ to $π/4R$.
Possible movements are shown in Figure 6.

Figure 6: Sixth problem shortest path(section discontinuous)

Example 7: Travel from $πR$(pole) to $π/2B$.
Possible movements are shown in Figure 7.

Figure 7: Seventh problem shortest path(section discontinuous)

Example 8: Travel from $πB$(pole) to $5π/4R$.
Possible movements are shown in Figure 8.

Figure 8: Eighth problem shortest path(section discontinuous)

If we want to include pairs of examples 5-8 in the domain $U$, then the section $s_1$ would not be continuous. Therefore, we need a second domain $V$ here.

$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.

Figure 13: Ninth problem shortest path(section discontinuous)

Example 10: Travel from $πR$(pole) to $πB$(pole).
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)

From all the above examples, the three algorithms for a robot moving an $8$ is as shown below:

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}$$

$$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 know that $TC$ for a bouquet of seven petals is $3$. This means that we have to divide the Cartesian product of a bouquet of seven petals into three different domains $U$, $V$ and $W$. It also means that three commands are given to two robots moving on $8$(configuration space for two robots moving on $8$ is a 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

Example 2: Travel from $3π/2B$ to $π/2G$.
Movement is shown in Figure 19.

Figure 19: Second problem shortest path

Example 3: Travel from $5π/4F$ to $5π/4C$.
The movement is shown in Figure 20.

Figure 20: Third problem shortest path

Example 4: Travel from $3π/2D$ to $0D$.
The movement is shown in Figure 21.

Figure 21: Fourth problem shortest path

Example 5: Travel from $0E$ to $3π/4E$.
The movement is shown in Figure 22.

Figure 22: Fifth problem shortest path

For all the examples from 1- 5, the section $s_1$ is continuous. We know that $TC$ is $3$, and therefore, we know that at some position, section $s_1$ is discontinuous. Let's see some more examples.

Example 6: Travel from $0B$ to $πB$.
Possible movements are shown in Figure 23.

Figure 23: Sixth problem shortest path(section discontinuous)

Example 7: Travel from $πA$ to $5π/4D$.
Possible movements are shown in Figure 24.

Figure 24: Seventh problem shortest path(section discontinuous)

Example 8: Travel from $3π/2F$ to $πE$.
Possible movements are shown in Figure 25.

Figure 25: Eight problem shortest(section discontinuous)

Example 9: Travel from $3π/2G$ to $π/2G$.
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 to 30 shows the results for example 6- 9, respectively. For these examples, section $s_2$ is continuous.

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$

Example 10: Travel from $πG$ to $πD$.
Possible movements are shown in Figure 31.

Figure 31: Tenth problem shortest(section discontinuous)

Example 11: Travel from $πA$ to $πB$.

Possible movements are shown in Figure 32.

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.

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:

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)

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$.

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.

Topological Robotics (Wilbur Wright College)

symbols

Algorithm for one robot moving on number $8$ and a bouquet of seven petals