# Mobile Robot Path Planning with a Non-Dominated Sorting Genetic Algorithm
## 6 Results  
In this work, the results of the improved non-dominated sorting genetic algorithm (NSGA-II) in various spaces are presented. To better examine the results, different quality metrics [58,59] and the multi-objective evolutionary algorithm (MOEA) algorithm [25] were employed. The hypervolume indicator (HV) [58] can be used to evaluate the volume of non-dominated solutions in the solution space. In the d-dimensional solution space, the related concepts are defined. \(A=\{a_{1},a_{2},...,a_{n}\}\) is the non-dominated solutions, and \(r=(r_{1},r_{2},...,r_{d})\) denotes the reference point, respectively. The Lebesgue measure [60] can be used to compute the hypervolume area of the non-dominated solutions bound by the reference point. The calculation of the HV is shown in Equation (8). \[ \begin{split} h(a_{i})=[a_{i_{1}},r_{1}]\times[a_{i_{2}},r_{2}] \times...\times[a_{i_{d}},r_{d}]\\ HV(A,r)=L(\bigcup\limits_{i=1}^{|A|}h(a_{i})|a_{i}\in A).\end{split}  \tag{8}\]  
Furthermore, the set coverage metric (SCM) [59] can be applied for computing the dominance ratio of the two sets of non-dominated solutions. \(A=\{a_{1},a_{2},...,a_{n}\}\) and \(B=\{b_{1},b_{2},...,b_{m}\}\) denote the two sets. Consequently, \(scm(A,B)\) can be computed with Equation (9). As the relationship (\(\preceq\)) represents a weak dominance relationship and is asymmetrical, it is also essential to determine \(scm(B,A)\). \[scm(A,B)=\frac{|\{b\in B|\exists a\in A:a\preceq b\}|}{|B|}. \tag{9}\]  
In this work, several maps are considered in Figure 11. There are different shapes of obstacles on each map. The starting and target points for these maps are displayed in Table 1. On each map, both algorithms run 30 times. In each run, the two sets of non-dominated solutions obtained by the two algorithms are compared with the quality metrics. The results of the hypervolume are given in Table 2. In contrast, these two sets are dense. Besides, in Table 3, the results of the set coverage metric (SCM) are exhibited. The average of scm (NSGA-II,MOEA) and SCM (MOEA,NSGA-II) is 95.01% and 94.47%,  
Figure 22: Effect of the shortest operator rate. respectively. It is evident that the most solutions within any set are non-dominated relative to another set. This also implies that the solutions obtained by these two algorithms are close to the Pareto front. Additionally, in each map, the reference points need to be calculated. The ideal reference point is optimal in every dimension, and the nadir reference point is worst. Table 4 shows the reference points. An ideal shortest route is the line segment from the start to the destination. The smoothness of the ideal smoothest path should be zero. For the minimum safety of path, this value can be estimated with enhancing the safety of the safest route by 10% in the non-dominated solutions. At this point, the three values of the ideal reference point have been set. Next, the three values of the nadir reference point are set. For the length and smoothness of the nadir reference point, the two values can be calculated by referring to the above means of estimating the minimum safety. The maximum safety of path is zero. Figures 23-27 present the approximate Pareto front of maps. The yellow circle is the ideal reference point. Red triangles and black asterisks are the non-dominated solutions with the improved NSGA-II and MOEA, respectively. In non-dominated solutions, the knee spot is a solution closest to the ideal reference point. Figures 28-32 show the path of the knee point obtained via NSGA-II. Comparison results are analyzed as follows. From the two different quality metrics of hypervolume and set coverage, the improved NSGA-II demonstrates a characteristic that is no worse than MOEA. Moreover, the non-dominated solutions generated via NSGA-II are denser. Besides, the path corresponding to the knee point also takes into account several designed objectives. The path is shorter, smoother and safer