Path Planning In A Static Environment Based On Genetic Simulated Annealing Algorithm

Path planning for mobile robots is a complex problem that not only guarantees a collision-free path with minimum traveling distance but also requires smoothness and security. This dissertation presents a genetic simulated annealing algorithm approach for solving the path planning problem in static mobile robot environments.Firstly, we summarize and analyze the status and research method of path planning in several active areas. Meanwhile the significance and the contents of the research are pointed out. Secondly, we develop a genetic simulated annealing algorithm, a hybrid of genetic and simulated annealing algorithm, by analyzing and comparing the advantages and disadvantages of them. The new algorithm has better capability of searching globally and locally. Thirdly, according to the characteristic of path planning problem, every component of the algorithm is analyzed carefully, including environment representation, chromosome coding, fitness function design, genetic operators design and simulated annealing algorithm parameters selection.Before path planning process, robot's working environment is built by neural network method. Get the network structure without training and learning, and use the output of the neural network model to carry out the constraint together with the fitness function of the genetic algorithm. Rapid rejection and cross experiments are used to make sure that the path not intersect with the roadblock. The security, smoothness and length of a path determine an efficient fitness function. Select strategy uses proportion select method; crossover operator is one-point crossover strategy. Mutation operator firstly uses heuristic mutation to transform all the paths to feasible paths; then the algorithm randomly selects a mutation point in each path and mutates the point at certain probability. In the simulated annealing, random moving rule uses Metropolis rule and devise efficient temperature update function. The simulation of simple genetic algorithm and genetic simulated annealing algorithm in a static environment is carried out in MATLAB.The simulation results show that the genetic simulated annealing algorithm is faster to plan a better path in complex environment than the simple genetic algorithm, and validated the effectiveness of the proposed approach.