Frontiers in Computing and Intelligent Systems 
ISSN: 2832-6024 | Vol. 2, No. 3, 2022 

 

78 

Robot path planning based on improved genetic 
algorithm 

Zhenxing Guo, Li Mo 

College of Mechanical and Electrical Engineering, Southwest Petroleum University, Chengdu 610000, China 

 

Abstract: In order to solve the problems of the basic genetic algorithm in robot path planning, such as the path is not smooth 

enough, the number of turns is too many, and it is easy to fall into the local optimal solution, an improved genetic algorithm is 

proposed. The method introduces the turning angle and turning times as the evaluation objectives, improving the practicability 

of the fitness function; The elitist retention strategy is added to improve the convergence speed of the algorithm; The adaptive 

change strategy of crossover probability and mutation probability is optimized, so that the algorithm can adapt to various 

scenarios and improve the optimization ability and convergence speed of the algorithm. The simulation results show that the 

improved genetic algorithm is more suitable for robot movement than the basic genetic algorithm. 

Keywords: Robot; Path planning; Genetic algorithm. 

 

1. Introduction 

Path planning is an important part of mobile robots. 

Improving the efficiency of mobile robots and reducing the 

energy consumption of robots are the research hotspots 

nowadays [1,2]. To solve the problem of robot path planning, 

researchers have put forward a variety of methods, among 

which the intelligent optimization algorithm is more widely 

used, including genetic algorithm [3], ant colony algorithm 

[4], particle swarm optimization algorithm [5], etc. Genetic 

algorithm is widely used because of its strong robustness. 

However, it has the disadvantages of slow iteration speed and 

easy to fall into local optimal solution, which limits its 

development. SUN Bo and others added the idea of simulated 

annealing to the genetic algorithm, effectively improving the 

global search ability of the algorithm [6]. XU Mengying and 

others combined immune clonal operator and adaptive 

operator in genetic algorithm, and changed the coding method 

to improve the quality of the solution [7]. The above methods 

improve the optimization ability of the genetic algorithm path 

planning, but there are still shortcomings such as too many 

path curves and slow convergence speed. 

To solve these problems, this paper modifies the fitness 

function on the basis of the basic genetic algorithm to 

adaptively change the crossover probability and mutation 

probability, and introduces the elitist retention strategy in the 

selection operation. Experiments show that the improved 

algorithm effectively improves the path planning 

performance of the robot. 

2. Path planning grid model 

Path planning is the robot's automatic avoidance of 

obstacles from the beginning to the end. Grid map is the most 

commonly used modeling method in path planning. The 

actual map is represented by grid. In a grid map, the area 

where the robot can move freely is called free grid, and the 

area where the robot cannot move freely is called obstacle 

grid.  

Figure 1 is an example of grid map. The white area in the 

figure represents the free grid, and the black area represents 

the obstacle grid. Given a starting point and an end point, 

there are many paths between the two points. The purpose of 

robot path planning is to select the most suitable path without 

touching obstacles. 

 
Fig. 1 Path planning grid map 

3. Improved genetic algorithm 

3.1. Fitness function 

Energy consumption is an important consideration for 

robot movement. The methods to reduce robot energy 

consumption include shortening the moving distance, 

reducing the turning angle and reducing the number of turns. 

The improved fitness function is as follows: 

fit = a × fit1 + b × fit2 (1) 

Where, a and b are the weights of length factor and 

smoothness factor, fit1  is the length factor expression as 

follows: 

fit1 =
1

length
(2) 

l = abs(xi − xi+1) + abs(yi − yi+1) (3) 

lenth = ∑ {
lenth + 1       (l = 1)

lenth + sqrt(2)  (l > 1)

end−1

i=1

(4) 



 

79 

x and y represent the coordinates of the grid, fit2 is the 

smoothness factor, and the expression is as follows: 

fit2 = ∑
1

pθi + pti

end−1

i=1

(5) 

Where, pθi  is the penalty imposed by the turning angle 

between two adjacent grids on the path. The greater the 

turning angle, the greater the value of pθi. pti is the penalty 

for the number of turns of the path. The more turns, the greater 

the value of pti. 

3.2. Select Action 

Selection operation is the most important step in genetic 

algorithm. According to the fitness of each individual, 

individuals with high fitness can be retained through roulette. 

However, roulette is random, and individuals with high 

adaptability may also be eliminated. To avoid this, the elite 

retention strategy is added in the selection process. Before 

roulette, the individuals with the highest fitness will be 

selected first, and will not participate in the subsequent 

roulette. Finally, the individuals with the highest fitness will 

be selected together with the individuals selected by roulette 

for the subsequent crossover operation and mutation 

operation, which can effectively prevent the loss of elite 

individuals and speed up the iterative efficiency of the 

algorithm. 

3.3. Adaptive change of crossover probability 

and mutation probability 

Crossover probability refers to the probability of crossover 

operation during each iteration. Crossover operation refers to 

swapping and recombining two intersecting paths, resulting 

in two sub-paths. This method can generate new sub-paths, 

and then retain the paths with good fitness, and discard the 

paths with poor fitness. The principle of this method is similar 

to that of gene recombination. After crossover operation, the 

fitness of the sub-path may be higher than that of the parent 

path, so as to achieve the purpose of finding the best path. 

Mutation probability refers to the probability of mutation 

operation during each iteration. Mutation operation refers to 

randomly selecting a new point in the path, and then replacing 

the original point in the path, so that a new path will be created. 

The value of crossover probability and mutation 

probability will affect the convergence rate and final solution 

of the algorithm, so it is not suitable to choose a fixed 

crossover probability and mutation probability. In order to 

improve the performance of the algorithm, this paper 

proposes a scheme to adaptively adjust the crossover 

probability and mutation probability. The convergence speed 

of the current algorithm is measured by using the sum of the 

average value of the length factor and the average value of the 

smoothness factor of the current generation population to 

compare with the sum of the average value of the length factor 

and the average value of the smoothness factor of the previous 

generation population. A larger ratio indicates that the 

algorithm is close to stable, and the mutation probability and 

crossover probability need to be increased to generate new 

individuals and increase the diversity of species. On the 

contrary, a smaller ratio indicates that the algorithm is 

converging rapidly. In order not to destroy good individuals, 

a smaller crossover probability and mutation probability 

should be used. The evaluation indicators are as follows: 

MC

MP
=

1
n

∑ fit1(t, i) +n
i=1

1
n

∑ fit2(t, i)n
i=1

1
n

∑ fit1(t − 1, i) +n
i=1

1
n

∑ fit2(t − 1, i)n
i=1

(6) 

MC represents the crossover probability and MP represents 

the mutation probability. MC/MP is the ratio of length factor 

and smoothness factor of two generation population. n is the 

number of individuals for the contemporary population; fit1 

is the length factor; fit2 is the smoothness factor; t indicates 

the generation of the current population. 

In genetic algorithm, the value of crossover probability and 

genetic probability can be between 0 and 1. However, 

considering that too low value will lead to the stagnation of 

population evolution and fall into local optimal solution, and 

too high value will destroy excellent individuals in the 

process of evolution. Therefore, the value range of restricted 

crossover probability is 0.5 to 0.8, and the value range of 

restricted mutation probability is 0.01 to 0.3. The specific 

values of crossover probability and mutation probability are 

shown in Table 1. 

Table 1. Value of crossover probability and mutation probability 

MC

MP
 Pc Pm 

<=0.2 0.5 0.01 

[0.2,0.4] 0.6 0.1 

[0.2,0.6] 0.7 0.2 

[0.6,0.8] 0.75 0.25 

>=0.8 0.8 0.3 

3.4. Algorithm flow 

The calculation flow of the improved genetic algorithm 

robot path planning proposed in this paper is shown in Figure 

2. The termination condition of the algorithm is to reach the 

maximum number of iterations. 

 

Fig. 2 Flow chart of improved genetic algorithm 

4. Experimental analysis 

In order to verify the effect of the improved genetic 

algorithm in robot path planning, this paper uses matlab 

software to carry out simulation experiments and compares it 

with the basic genetic algorithm. The starting coordinate is 

(1,1) and the ending coordinate is (20,20). The number of 

populations is 200, the maximum number of iterations is 100, 

the weight coefficient a is 1, and the weight coefficient b is 

1.5. 



 

80 

 

Fig.3 Results of improved genetic algorithm 

 

Fig.4 Basic genetic algorithm results 

Figure 3 shows the improved genetic algorithm path 

planning results, and Figure 4 shows the basic genetic 

algorithm path planning results. It can be seen that both 

algorithms can find a shortest path for the robot. However, the 

improved genetic algorithm results in fewer turns, which is 

more suitable for robot motion. 

 

Fig.5 Comparison of convergence curves of two algorithms 

Figure 5 shows the comparison of the convergence curves 

of the two algorithms. It can be seen that the improved genetic 

algorithm converges faster. These advantages come from 

adaptive adjustment of crossover probability and mutation 

probability and elite retention strategy. 

Since genetic algorithm is a random algorithm, in order to 

avoid chance, 20 simulation tests were carried out on the basic 

genetic algorithm and the improved genetic algorithm 

respectively, and the results are shown in Table 2.  

Table 2. Comparison of multiple simulation results 

Item Basic genetic 

algorithm 

Improved genetic 

algorithm 

Optimal length 29.8 29.8 

Average number 

of turns 

12.5 5 

Average length 30.703 30.9 

Average number 

of iterations 
18.5 11.25 

The analysis shows that the theoretical shortest path of the 

map is 29.8, and both the basic genetic algorithm and the 

improved genetic algorithm are capable of finding the shortest 

path. However, because sometimes the number of turns of the 

shortest path is too many, it is not suitable for the robot to 

move, so the path calculated by the improved genetic 

algorithm may not be the shortest path. The number of turns 

calculated by the improved algorithm is greatly reduced, and 

the convergence speed of the algorithm is fast, which can 

preliminarily prove the superiority of the improved genetic 

algorithm. 

5. Summary 

This paper proposes an improved genetic algorithm path 

planning for robots. The algorithm modifies the basic genetic 

algorithm: changing the fitness function; Making crossover 

probabilities and mutation probabilities adaptively altered; 

An elite retention strategy was introduced. The improved 

genetic algorithm reduces the number of turns in the path, 

reduces the turning angle, accelerates the convergence speed 

of the algorithm, and significantly reduces the energy 

consumption of the robot. There are still many aspects to be 

improved in the research content of this paper, such as how to 

apply the algorithm to the dynamic obstacle environment, and 

improve the adaptability of the algorithm to the complex 

environment. 

References 

[1] Ma Xiaolu, Li Ruyi, Wu Lihui. Review on Local Path Planning 
Algorithm for Intelligent Vehicle. Automobile Applied 
Technology. Vol. 47 (2022) No. 23, p. 232-237. 

[2] LI Xiaoxu, Ma Xinglu, Wang Xianpeng. A Survey of Path 
Planning Algorithms for Mobile Robots. Computer 
Measurement & Control. Vol. 30 (2022) No. 07, p. 9-19. 

[3] Xin Gang, Song Shaozhong, Zhang Hui, et al. Route Planning 
Problem Application Based on Improved Genetic Algorithm. 
Journal of Jilin University (Information Science Edition). Vol. 
40 (2022) No. 06, p. 946-957. 

[4] ZHOU Jing⁃dong, GAO Wei-zhou, YANG Wen-guang, et al. 
path planning of mobile robot based on improved ant colony 
algorithm. Science Technology and Engineering. Vol. 22 (2022) 
No. 28, p. 12484-12490. 

[5] WANG Yi-hu, WANG Si-ming. UAV path planning based on 
improved particle swarm optimization. Computer Engineering 
and Science. Vol. 42 (2022) No. 09, p. 1690-1696. 



 

81 

[6] SUN Bo, JIANG Ping, ZHOU Genrong, et al. Application of 
Improved Genetic Algorithm in Path Planning of Mobile 
Robots. Computer Engineering and Applications. Vol. 55 
(2019) No. 17, p. 162-168. 

[7] XU Mengying, WANG Jiaojiao, LIU Bao, et al. Path planning 
for robot based on improved genetic algorithm. Journal of 
Shihezi University (Natural Science). Vol. 39 (2021) No. 03, p. 
391-396.