The Research of Robot Path Planning System
Keqing LIN
College of Information Science and Engineering, Northeastern University, P. R. China

Abstract: First we analyze all of the aspects of the algorithm in detail, including environmental modeling, path initialization, the fitness function design, the operator design, the analysis and selection of algorithm parameters. Then, use the MATLAB write, simulate and debug the program, continually analyze the simulation result in static environment. Simulation results showed that genetic simulated annealing algorithm in a variety of obstacles environment can plan out an optimal or near-optimal path effectively, which demonstrate the effectiveness of the algorithm.
Key words: Path planning、Genetic algorithms、Simulated annealing algorithms

Introduction
Robot is the agent which can stay in the physical state, is a automatic or semi-automatic machine to perform work. It can be perceived by the sensor surroundings in the surrounding environment to make certain reactions. Robot is the popular trend of modern scientific and technological research in the 21st century which will increasingly play an important role in reflecting its importance. Since the invention of the world's first generation of robots, robots applications in various fields widely, the ability to interact with the environment are increasing. Robots need to focus on the following issues specially, namely: determine where it is, where to go, how to get. The third problem is the so-called path planning problem, it is an important branch in the field of robotics research, mainly refers to how to find a path from the initial state to the target state can best avoid obstacles in its workspace path
The main task of path planning is to seek a path with minimum cost from the starting point to the end in an environment with robots. The path should be avoiding the collisions. Besides, the path planning requires that the path should be as smooth as possible and meet a certain security. This thesis focus on the characteristic of path planning, analyzes the advantages and disadvantages of various path planning methods, for example, topological method, Genetic Algorithm, Neural network algorithm, Simulated annealing algorithms, etc. Proposed the genetic simulated annealing algorithm which based on genetic algorithm and simulated annealing algorithm, this algorithm can solve the shortcoming of easy to fall into local optimum and low efficiency operation in other algorithms effectively.
Methods
As mentioned earlier, Genetic simulated annealing algorithm is an algorithm combined genetic algorithm and simulated annealing algorithm. GA has implicit parallelism and global optimization capability, which makes genetic algorithm can search of all possible solutions comprehensive during the optimization computing and with the high speed of parallel computing, so genetic algorithm can be more extensive and more effective to solve the problem.
However, the genetic algorithm itself also has its own shortcomings, the main aspects of the genetic algorithm is easy to fall into local optima and premature, and therefore genetic algorithms in solving multi-objective optimization problem may be premature convergence to a local optimal solution, so that the entire optimization process stalled, and will not search the optimal or suboptimal solution. So in order to search for the optimal solution of the question, in this paper, we combined genetic algorithm and simulated annealing algorithm for the path plan, which is using genetic simulated annealing algorithm, when use the combination of these two algorithms to find the path, no longer only used to the path selection, crossover and mutation operation, but also join the procedure of simulated annealing to strengthen the ability of local optimization and use the Metropolis to determine whether to accept the new solution, prevent the premature convergence of the algorithm.
Path coding
Path set
Path copy
Path cross
Path variation
Path encoding
Set of the actual path
Evolution
Path adaptability evaluation
Simulated annealing process
Local optimal path
Optimal path

Path coding
Path set
Path copy
Path cross
Path variation
Path encoding
Set of the actual path
Evolution
Path adaptability evaluation
Simulated annealing process
Local optimal path
Optimal path

The entire genetic simulated annealing algorithm for path planning process shown in Figure 1:

Figure 1: Simulated annealing genetic algorithm
Results
The simulated result of the genetic algorithm showed as Figure 2:

Figure 2: The shortest path searched by genetic annealing algorithm
The simulated result of the genetic annealing algorithm showed as Figure 3:

Figure 3: The shortest path searched by genetic simulated annealing algorithm

Conclusion
Compared with genetic algorithms and as the result shows, simulated annealing genetic algorithm is more effective, the search results of the simulated annealing genetic algorithm (Figure 3) are better than the results of the genetic algorithm (Figure 2); For the genetic simulated annealing algorithm, the group size, the maximum number of genetic iteration and the other parameters’ set of the algorithm determined the results of the search. When setting the value of the parameters, it should according to the actual situation, not be too small nor too large; This optimization algorithm is a stochastic search algorithm, which cannot always search the optimal solution, so when solving specific problems it tends to run more than one time, then find the relative optimum solution between the several results as the final result.
References
Ahmed Elshamli, Hussein Abdullah, & Shawki Areibi. (2004). Genetic Algorithm for Dynamic Path Planning. CCECE 2004-CCGEI 2004, Niagara Falls, 677-680.
Goldberg, D. (1989). Genetic algorithms in search, optimization and machine learning. Massachusetts: Addison-Wesley Press.
Kirkpatrick, S. Gelato, C. D. & Vichy, M. P. (1983). Optimization by simulated annealing. Science, 4598, 671-680.
Maes, P. (1998). Modeling adaptive autonomous agents. Landon: The MIT Press.
Shibata, T. & Fukuda, T. (1994). Coordination in evolutionary multi-agent-robotic system using fuzzy and genetic algorithm. Control Engineering Practice, 1, 103-111.
Yahja, A. (2000). An Efficient On-line Path Planner for Outdoor Mobile Robots. Robotics and Autonomous Systems, 32: 129-143.