# Mobile Robot Path Planning Algorithm Based on NSGA-II
## 2 Global Path Planning
### Population Initialization  
The process of population initialization aims to generate a set of initial paths, serving as the foundation for algorithm iteration. Improving the efficiency of initialization is beneficial for enhancing path planning efficiency and influencing algorithm convergence. The quality of the initial paths also impacts the calculation of optimal paths. Most scholars opt for a random method during population initialization. In this approach, random path nodes are initially generated within the feasible region of the map. Subsequently, the usefulness of these randomly generated path nodes is assessed based on whether they can form a feasible path. However, this process often results in numerous ineffective nodes and paths, significantly increasing the computational overheads and decreasing algorithm efficiency. Moreover, the random distribution of the generated paths may lead to uneven distribution. If the random solution set predominantly lies in local optimal positions, this may inadvertently steer the algorithm towards local optima. This is one of the reasons why the NSGA-II algorithm is prone to local optima. To address these issues, this paper introduces the concept of a search window to constrain the generation of random points. The search window is a fixed-size square region, within which new nodes are generated. The position of the search window changes continuously based on the location of the generated nodes, always facing towards the target point. Specifically, when the target point is directly above the mobile robot, the robot should be positioned at the bottom center of the search window. When the target point is to the top right of the mobile robot, the robot should be positioned on the left side of the bottom of the search window. Similar adjustments are made for other target point positions relative to the robot. The search window continuously moves towards the target point direction based on the mobile robot's position, until a complete path from the start point to the target point is generated. By constraining the range and orienting the search window towards the target point, this paper improves the efficiency of generating initial paths, reduces the number of redundant nodes, and avoids misguiding the initial path set. The specific steps of the improved population initialization method can be summarized as follows:  
1. Generate a search window from the robot's position towards the target point, using the robot's position and the target point as reference points, as shown in Figure 1.  
2. Generate a random path node within the feasible area in the search window where there is no robot present. 3. Determine whether the robot can move directly to the position of this path node. Since the mobile robot can move directly to the grid in eight directions adjacent to its position, the judgment condition expression is as follows: \[\delta=\max\{abs(x_{i+1}-x_{i}),abs(y_{i+1}-y_{i})\},\] (1) where \((x_{i},y_{i})\) represents the coordinates of the grid where the mobile robot is located, and \((x_{i+1},y_{i+1})\) represents the coordinates of the generated path node. If \(\delta\) takes the value 1, i.e., \(\delta=1\), this means the generated path node is located within the eight grids that the mobile robot can directly move to, so the node's position is updated directly to the robot's position. Otherwise, \(\delta\
eq 1\), which indicates that the generated node position is not within the eight grids the mobile robot can directly move to, so intermediate nodes need to be supplemented. In this text, we use the method of interpolation to supplement the path nodes. The expression for selecting intermediate path nodes is as follows:  
\[ \begin{split} x_{middle}&=int(\frac{x_{i+1}+x_{i}}{ 2}),\\ y_{middle}&=int(\frac{y_{i+1}+y_{i}}{2}),\end{split}  \tag{2}\]  
where int denotes rounding. After calculation, if the position is obstructed, it is necessary to choose another grid.