# Mobile Robot Path Planning with a Non-Dominated Sorting Genetic Algorithm
## 1 Introduction  
Path planning (PP) has been fundamental in many areas in recent decades, for instance mobile robots [1; 2; 3], unmanned surface vehicles (USVs) [4; 5], wireless sensor networks (WSNs) [6; 7; 8] and video games [9]. For mobile robots, path planning is devised to find one or more feasible routes from the initial location to the target in a given workspace. The related algorithms in the field of path planning are reviewed in [10; 11]. In [12], several path planning and navigation algorithms commonly employed in the domain of unmanned aerial vehicles (UAVs) were studied. The commonly-used methods are the probabilistic roadmap method (PRM) [13], the artificial potential field method (ARF) [14], the rapidly-exploring random tree method (RRT) [15], A\({}^{\star}\) and its variants [16; 17], and so on. In [18], the fast marching method (FMM) was applied to the path planning problem. Moreover, the research revealed that the algorithm can successfully attain the collision-free shortest route in many static environments. Most conventional approaches attain available paths and seldom optimize several objectives concurrently. However, optimization problems in most disciplines should study multiple objectives simultaneously, not just a single one. For example, in the product design process, the cost and quality of the product are often contradictory, that is and decrease in the price of the product and the quality has to decrease, and vice versa. How to decrease the cost of the product and enhance the quality comprise a dual-objective optimization problem. Path planning problems are no exception. In this study, three objectives are presented. Path length is related to the operation time of the mobile robot. Path safety represents the length from the path to the nearest obstacle. Path smoothness indicates the degree of bending of the path. In general, at least two objectives are conflicting. At present, based on the complexity of the path planning problem, this issue is identified as NP-hard [19]. Multiple competing goals need to be considered concurrently. Subsequently, common multi-objective weighting methods are employed to solve problems [20; 21]. The principle of the weighting method is to set the weighting factors of the objectives and combine the targets into a new one. However, because there is no apparent measurable relationship between these objectives, it is difficult to set their weighting factors. In other words, the transformation process itself is also a multi-objective optimization problem. Therefore, the weighting method is not proper. On the other hand, some researchers extended the deterministic heuristic A\({}^{\star}\) algorithm to multi-objective cases [22; 23; 24]. In these algorithms, the heuristic function of any node in the graph search space is a vector. In later years, evolutionary algorithms (EA) were universally employed for path planning. A practical framework of multi-objective evolutionary algorithm (MOEA) was designed in [25]. Besides, several practical evolution operators were presented. To further advance the computational efficiency, in the initial step, some individuals were generated by the Dijkstra algorithm. In [26], the traditional method was first employed to generate the roadmap in the workspace, and then, the Hopfield neural network was applied to improve path length and safety. In [27], the modified rapidly-exploring random tree was presented to obtain the path. Then, the path length and smoothness were improved based on the neural network curve post-processing strategy. In [28], the Q-learning method was developed to optimize the path. A fast two-stage ant colony optimization algorithm was shown in [29]. This algorithm contained two phases: map preprocessing and ant colony optimization. In the map preprocessing, they calculated the minimum number of steps from all free nodes to the target node. Next, the path length was optimized by the modified ant colony optimization.