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.

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

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