Research On Multi-objective Path Planning Of Mobile Robot

In many domains,such as mobile robots,wireless sensor networks,video games,and driverless vehicles,path planning has continually attracted researchers' attention.In the field of mobile robots,the path planning problem is to find one or more feasible paths from the starting point to the target point in the limited space.In various path planning problems,it is not enough to consider obstacle avoidance.It is often necessary to consider multiple optimization objectives,such as the energy consumption of the robot's travel route,the path safety factor,and so on.These objectives are contradictory and restrained each other.The performance improvement of one indicator often leads to the degradation of at least one additional indicator,that is,it is difficult for multiple indicators to achieve optimality at the same time.Therefore,multi-objective path planning has always been a topic which has the general concern.This paper aims to study from two perspectives:the deterministic algorithms and population-based evolutionary algorithms.The innovative work of this paper is summarized as follows:In Chapter 2,the deterministic and set-oriented cell mapping algorithm is applied to the path planning research field for the first time to solve the multi-objective optimization problem.Two optimization objectives of path length and safety are designed.The cell mapping algorithm can find the set of the non-dominated costs from all cells to the target cell in the discrete grid space;that is,the single source multi-objective optimization problem is solved.To further improve the computational efficiency and precision of cell mapping algorithm in path planning problems,a hybrid cell mapping algorithm based on subdivision technology is proposed in Chapter 3.Similar to the concept of the feasible region in decision space,the idea of path space coverage domain is introduced,and the coverage domain is subdivided based on subdivision technology to form a higher precision grid space.Then the path planning problem can be again solved by the cell mapping algorithm.Finally,the numerical calculation results of the hybrid cell mapping algorithm and the cell mapping algorithm are compared.The numerical results show that the non-dominated Pareto front generated by the hybrid cell map is more evenly distributed and closer to the real Pareto front.Since the mesh is more refined,although the path smoothness objective is not considered,it can be seen that the randomly selected path is smoother.In Chapter 4,a new population evolutionary algorithm is proposed for the path planning problem.Different from the elite strategy of the non-dominated sorting genetic algorithm which preserves better individuals(solutions)and maintains the diversity of individuals within the population,the proposed algorithm divides the objective function space into a discrete space and uses the number of solutions in the lattice to evaluate the fitness function value of the lattice.The smaller the number of solutions in the lattice,the larger the fitness function value of the lattice,and the higher the probability that the solution in the lattice is selected.Besides,a novel evolutionary algorithm framework and several practical evolutionary operators are designed.These operators can improve the quality of the solution.Some local optimal solutions are generated by the Dijkstra algorithm and put into the initial population to further enhance the efficiency of algorithm evolution.The proposed algorithm is examined with particle swarm optimization.Then the comparison results are evaluated with the quality metrics(hypervolume indicator and set coverage metric).The numerical results show that non-dominated solutions generated by the proposed algorithm have excellent characteristics.An improved non-dominated sorting genetic algorithm is proposed to solve the path planning problem in Chapter 5.Several evolutionary operators are designed to improve the quality of the solution further.Moreover,the parameters involved in the algorithm are studied.The results show that larger population sizes,higher numbers of generations and high operator probabilities are indispensable in complex environments.The improved genetic algorithm is compared with the evolutionary algorithm proposed in the previous chapter.Then the comparison results are evaluated with the quality metrics.The numerical results show that non-dominated solutions generated by both algorithms have excellent characteristics.Besides,the knee point in the set of non-dominated solutions is shorter,smoother,and safer.Decision makers can adopt it in the subsequent decision-making process.This paper introduces two kinds of algorithms for solving multi-objective path planning problems of mobile robots in static environments.They are deterministic cell mapping algorithms and evolutionary algorithms based on population evolution strategies.The cell mapping algorithm finds the non-dominated labels(database)from any cell to the target cell in the discrete workspace with the global perspective.And then based on the database,the optimal paths can be obtained from the start cell to the target cell.Next,a hybrid cell mapping algorithm is proposed to improve the efficiency and accuracy further.Evolutionary algorithms solve problems from the perspective of population evolution.A series of evolutionary operators act on the population(the set of paths)to generate a new population.After many iterations,the set of non-dominated solutions is continually approaching the real Pareto front.