# Mobile Robot Path Planning Algorithm Based on NSGA-II
## 2 Global Path Planning
### Designing the Fitness Function  
In the algorithm, the fitness function is primarily used to quantitatively describe individuals. Therefore, the design of the fitness function is crucial. If the fitness function is not appropriate, this may lead to deception phenomena. In the early stages of the algorithm, individual extraordinary individuals may emerge due to their outstanding fitness, leading to a strong competitiveness. This may result in the dominance of this individual in the selection process, thereby significantly affecting the global optimization of the algorithm. Alternatively, in the later stages of the algorithm, after multiple iterations, the fitness differences among individuals in the population are small, leading to a decrease in individual diversity and possibly causing the algorithm to fall into local optima.  
In the path planning process of mobile robots, path length is an important consideration. Path length is directly related to the energy consumption of the mobile robot. Since the battery capacity of mobile robots is limited, efficiently completing tasks with limited energy is an important criterion for evaluating robot efficiency. Therefore, in feasible situations, shorter paths for mobile robots are preferred. In addition to path length, path smoothness is an important evaluation criterion for mobile robot path planning. Due to the constraints of kinematics and dynamics, and for safety reasons during robot motion, the turning angle of the robot should not be too large, and the number of turns should not be too high. Therefore, in this paper, path length and path smoothness are considered as the objective functions for path planning.  
Considering a path \(L_{j}\), where \(j=1,2,\ldots,M\) and \(M\) represents the maximum number of individuals contained in the population, \(L_{j}\) can be denoted as \(L_{j}=\{O_{1},O_{2},\ldots,O_{m}\}\), where \(m\) signifies the number of nodes in path \(L_{j}\), \(O_{i}\) represents a node within path \(L_{j}\), \(O_{1}\) denotes the starting point of path \(L_{j}\), and \(O_{m}\) signifies the target point.  
The sum of distances between all adjacent nodes, including the starting point and the target point, constitutes the path length. The expression for the path length function \(f_{1}\) is  
\[f_{1}(L)=\sum_{i=1}^{m-1}l_{i}, \tag{3}\]  
where \(O_{i}\) represents the \(i\)th node in a path, \(m\) denotes the total number of nodes in that path, and \(l_{i}\) signifies the distance between adjacent nodes in the path. The expression is as follows:  
\[l_{i}=|O_{i}O_{i+1}|=\sqrt{(x_{i+1}-x_{i})^{2}+(y_{i+1}-y_{i})^{2}},i=1,2, \ldots,m-1, \tag{4}\]  
where \(x_{1}\) and \(y_{i}\) represent the horizontal and vertical coordinates of the nodes, respectively.  
Path smoothness reflects the smoothness of the mobile robot's trajectory. The path smoothness function \(f_{2}\) is defined as  
\[f_{2}(L)=\sum_{i=1}^{m-2}e^{(\pi-\theta_{i})}(\lg\pi-\lg\theta_{i}), \tag{5}\]  
where \(\theta_{i}\) represents the angle formed between the path segment from node \(O_{i}\) to node \(O_{i+1}\) and the path segment from node \(O_{i+1}\) to node \(O_{i+2}\), as depicted in Figure 2, and \(m\) is the number of nodes in the path. When the path angle is right, the path is the smoothest, and \(f_{2}\) is minimized. Conversely, when the path angle is acute, the path is the least smooth, and \(f_{2}\) is maximized.  
Therefore, in this paper, the objective function of path planning is  
\[\min\ \ \ \ \ \ f_{1}(L)=\sum_{i=1}^{m-1}l_{i},f_{2}(L)=\sum_{i=1}^{m-2}e^{\pi- \theta_{i}}(\lg\pi-\lg\theta_{i}). \tag{6}\]