## 3 Re-Entry Path Planning for Robots Based on Dynamic Inver-Over Evolutionary Algorithm
### Dynamic Inver-Over Evolutionary Algorithm  
Following integration, the Occupy operator is capable to convert the static Inver-Over evolutionary algorithm for TSP into the dynamic Inver-Over evolutionary algorithm for the purpose of re-entry path planning. As shown in Algorithm 3, non-cleaned cells shall be coded in pseudocode of the dynamic Inver-Over evolutionary algorithm, and the each population element is taken as the number of a cell. For instance, the gene sequence saved by the individual \(S_{i}\) containing information of 8 cells is 1-2-3-4-5-6-7-8, which indicates that the robot will depart from Cell 1 to pass by cells 2, 3, 4, 5, 6, 7 and 8 in succession. In this paper, path length is taken to evaluate whether individual genes are good. The individual genes are decomposed into a number of individual phenotypes. Then, individual path \(length(S_{i})\) is calculated, so:  
\[length(S_{i})=\sum_{j=1}^{n}\mathbf{d}(n_{j},n_{j+1}) \tag{9}\]  
\[\mathbf{d}(n_{j},n_{j+1})=\sqrt{\left(y_{j+1}-y_{j}\right)^{2}+\left(x_{j+1}-x_{j} \right)^{2}} \tag{10}\]  
where \(n\) indicates the number of cells, while \(d(n_{j},\,n_{j+1})\) denotes the distance between Cells \(j\) and \(j+1\). Individuals with higher \(length(S_{i})\) will be eliminated with algorithms. ```
Input: locations of cities and \(\mathbf{Darray}\) Output: dynamic optimal route
1: load the uncleaned cell locations and initialize the population \(P\) and \(t=0\)
2: output the best route by Inver-Over(\(P(t)\))
3:while not arrive end time do
4:while Darray is not empty do
5:\(cell\_occupy\) = Darray
6: Occupy(\(cell\_occupy\))
7:endwhile
8: output the best route in \(P(t)\)
9:endwhile
```  
**Algorithm 3** Dynamic Inver-Over (0)  
In Algorithm 3, Inver-Over operator plays significant roles. This operator primarily involves two search processes, which are mutation and crossover operations. Each individual performs an operation at probability \(k\). After new solutions are determined, both types of operations are compared  
Figure 5: Practical instance of occupy operator: (**a**) static route; (**b**) new route by occupy operator. against each other in terms of their strengths and weaknesses, in order to preserve the best solutions. For mutation operation, two cells are selected from a sequence on a random basis, and the content between two cells is completely reversed, as illustrated in Figure 6a. As for crossover operations, a cell is chosen from the current Individual 1, and a cell is selected from another Individual 2. Reversion will be made unnecessary if the two cells are adjacent. On the contrary, the content between the two cells will be completely reversed, as shown in Figure 6b. Both operations of the Inver-Over operator are conducive to an effective convergence of the algorithm and ensuring the search for the global optimal solution. Premised on the static Inver-Over evolutionary algorithm, a group of solutions appropriate for the identification of the optimal path can be obtained. Despite this, this path remains not suited to coping with environmental changes. Nevertheless, this problem is addressed by the dynamic Occupy operator in Algorithm 3. When the cleaning robot works under the backtracking mode, the cells are possibly occupied by dynamic obstacles. Under this circumstance, the overall number of cells will vary. To find out about which cells are blocked, the location information of block cells is saved during the robot's work with the assistance of the Darray. Besides, the data in the Darray are further processed by the Occupy operator. This operator collects global information by making full use of static algorithm and avoids redundant operations for algorithm to re-start. For changing cells of environment, it is prompt to determine a new path by connecting and occupying adjacent cells. Therefore, it can be easily executed. While making response in real time, it reduces occupation of computer resources and is capable to be put into industrial practices with more ease.