## 4 Multi-Objective Evolutionary Algorithm for the PP Problem
### Initialization  
Generally, generating an initial population is always the first step of evolutionary algorithms. Potential solutions (individuals) are generated and evolved. The individual in the population is a random path. Each path consists of \(k\) random rotation points in the free workspace. \(k\) is a random number ranging from 1 to 3. The number of rotation points on the path varies after using evolutionary operators.  
Three objectives (length, safety, and smoothness) were optimized in this article. To further improve the evolutionary efficiency, we found the local minimum value of each objective (if it could be found) and put the corresponding feasible paths into the initial population. For the length and safety of path, we provide the following two ideas to find the local minimum feasible paths. In regard to the smoothness objective of the path, the local minimum smooth path exists in the region near the local minimum distance path or the local minimum safety path, so improvements in the local minimum distance and safety of the paths were sufficient.  
For the path length, we used the Dijkstra algorithm to find the local minimum distance path, as follows: (1) Find the set (\(Q\)) of obstacles that collide with the line segment (\(\overline{ST}\)). (2) For each obstacle (\(j\); \(j\in Q\)), if the line segment between any vertex of \(j\) and the start point (\(S\)) collides with obstacle \(k\) (\(k\
otin Q\)), or the line segment between any vertex of \(j\) and the target point (\(T\)) collides with obstacle \(k\) (\(k\
otin Q\)), obstacle \(k\) is put into set \(Q\). (3) For each obstacle (\(j\); \(j\in Q\)), all vertices are stored into set \(Vertex\). (4) For any two vertices (\(i,j\); \(i,j\in Vertex\)), if the line segment (\(\overline{i}\)) is located in the semi-free space, the line segment (\(\overline{i}\)) is put into the edges set (\(Edge\)). (5) For all vertexes (\(Vertex\)) and edges (\(Edge\)), the local minimum length path can be obtained with the Dijkstra algorithm.  
Figure 7: Position update operator.  
Next, we show how to find the local minimum safety path. This idea is inspired by dividing the continuous workspace into discrete grids, as follows. (1) First, divide the workspace into \(N=N_{1}\times N_{2}\) grids, calculate the clearance distance of each grid from corresponding nearest obstacles, and convert the clearance distance into a safety value--the closer to the obstacle, the greater the safety value is. Conversely, the farther away from the barrier, the smaller the safety value is. (2) Taking into account the safety values of all grids and the four-connected relationship (namely, each grid has 4 adjacent grids), the Dijkstra algorithm can be used to find the local minimum safety path from the start grid (where the start point is located) to the target grid (where the target point is located). (3) If the local minimum safety path does not exist or the path is not feasible, the number (\(N\)) of grids is increased and we go back to step (1). Note that the initial grids (\(N\)) can be set to a small value, such as 400, and then the value of \(N\) is gradually increased.  
Finally the parameters are set as follows. The size of population is set to 80. The maximum generation number is set to 100. The size of repository is set to 300. The objective search space is divided into \([12;12;12]\) grid regions. In addition, we set the probabilities of safety, shortest, mutation, smoothness, shortness, and positions update operators to 0.5, 0.1, 0.5, 0.5, 0.5, respectively. Furthermore, the velocity constraints \([Min\_v,Max\_v]\) in the position update operator are set to \(\pm 1\%\) of the vector distance between the upper boundary and lower boundary of the workspace.