# Mobile Robot Path Planning Based on Improved Coyote Optimization Algorithm

Authors: Jingyao Huang; Huihui Wu
Journal: Mathematical Problems in Engineering
 (2022)

---

## Abstract

An improved coyote optimization algorithm (ICOA) is proposed to meet the requirements of global search capability, convergence speed, and stability for mobile robot path planning problems. Firstly, the population is divided into the elite group and the general groups after initialization, and the coyote individuals in the general groups are evolved by introducing the strategy of the best leading the poor. Secondly, after returning to the original position, coyotes adopt a new growth mode, and each individual makes a certain contribution to improve the level of the whole group. Thirdly, different from the original greedy algorithm, the survival of the fittest is carried out after each group of coyotes grows up, and the individuals do not affect each other. Finally, ICOA and the other seven optimization algorithms are simulated on four maps for mobile robot path planning. The simulation results show that ICOA can keep the diversity of the population, and has a strong global search ability, better stability, fast convergence speed, which reflects the strong optimization ability.


---

## Body

## 1. Introduction

Path planning is one of the key technologies in the research field of mobile robots. Mobile robots are required to be familiar with the map before driving and be able to plan a safe path from the starting point to the ending point without touching obstacles in the process. In recent years, more and more research has been made on mobile robot path planning, and common algorithms including particle swarm optimization algorithm (PSO) [1], genetic algorithm [2], ant colony optimization algorithm (ACO) [3], Dijkstra algorithm [4], probabilistic roadmap method [5], Q-learning algorithm [6], and A∗ algorithm [7]. These algorithms can solve the path planning problem of mobile robots to a certain extent, but when the map becomes complicated, it is inevitable to fall into the local optimal solution easily, the convergence speed is slow, and the obtained solution is not optimal, which not only affects the stability and effectiveness of the algorithm but also affects the efficiency of the subsequent work.For metaheuristic algorithms, in recent years, many researchers have proposed monarch butterfly optimization (MBO) [8], slime mould algorithm (SMA) [9], moth search algorithm (MSA) [10], hunger games search (HGS) [11], Runge Kutta method (RUN) [12], colony predation algorithm (CPA) [13], weighted mean of vectors (INFO) [14], and Harris Hawks optimization (HHO) [15] separately. These algorithms have their own unique optimization mechanism and have certain advantages. However, no scholars have applied these algorithms to mobile robot path planning. For many other algorithms, many scholars have studied and put forward their own improvement ideas.In view of the problem that PSO algorithm tends to fall into local optimality, Li [16] used the path planning method of improved particle swarm fusion artificial potential field method to construct gravitational field and repulsive field models, and proposed traction operation, which overcame the shortcomings of traditional algorithms. Song [17] proposed a new insertion operator to shorten the path and improve the speed for complex maps where genetic algorithm is not suitable for many turns. Hu [18] put forward the optimization of the multistep long ant colony algorithm on the characteristics of slow convergence speed, redundant inflection point, not the shortest path and so on a series of problems, by enlarging the visual field and activity field of the robot, adding simplified operators, updating pheromone, and improving heuristic function so that increase the smoothness of the path and improve the convergence speed.COA is a new optimization algorithm that simulates coyote population birth, growth, death, deportation, and acceptance [19]. The structure of the algorithm is unique, the algorithm can stay fast convergence speed under the condition of population diversity, it has the global search ability to a certain. But the algorithm has been around for a relatively short time and is not perfect enough in some aspects: (a) in COA, the growth mode of each coyote is single, and the differences between individuals are not taken into account, the advantages of each coyote cannot be fully exploited, resulting in the insufficient optimization ability of the algorithm; (b) the group leading mode of head coyote and cultural trend is easy to make the algorithm fall into local optimal solution and increase the phenomenon of individual convergence; (c) the probability of deportation and acceptance of coyotes is low, which leads to a low degree of information sharing between groups and increases the probability of local optimal occurrence; and (d) the method of survival of the fittest and subgroup search slow down the convergence speed of the algorithm.Some scholars have further studied COA. To further improve the optimization performance of COA, Zhang [20] proposed a multistrategy coyote optimization algorithm, which balanced exploration and exploitation to maximize the performance of the algorithm, with stronger search ability, faster running speed, and higher search efficiency. However, they ignored the effects of other coyotes except the best coyote, the worst coyote, and random coyotes in the groups, which could not reflect the social level of the whole group to some extent, and there was a certain probability of falling into the local optimal solution. Chen [21] designed an adaptive coyote algorithm and studied the UAV offline track planning problem from the perspective of optimization, the adaptive coyote algorithm has a strong global search ability and can adapt to the offline track planning problem of different dimensions. But the adaptive mechanism has certain advantages for some individuals, while other individuals may not be able to choose the most suitable update mode during the selection process, thus they cannot play their full advantages, resulting the algorithm performance cannot reach the optimal. Zhang [22] proposed a method to strengthen the best and worst coyotes to solve the problem of insufficient optimization performance, which improved the population diversity, strengthened the global search ability, and applied it to the second assignment problem with good results. But the performance of the improved algorithm is limited and cannot perform best to some extent, which needs further study.When COA solves the problem of mobile robot path planning, it has quick convergence and strong global search ability, the optimization has obvious advantages for the simple tasks, but for complex tasks, its special way may lead to a local optimum, the search for a long time or cannot find the shortest path. Based on the current research status, COA is improved and applied to the path planning of mobile robots. And the simulation analysis on different maps shows obvious advantages of the improved algorithm. The improvements are as follows.(a)
Before coyotes grow, the original grouping method was changed in the algorithm, and the strategy of leading the poor was introduced to evolve the coyotes with poor social adaptability, which could give full play to the advantages of coyotes with good social adaptability. Evolving coyotes with poor social adaptability before they start to grow can raise the population level and enable the algorithm to have local search capability. The degree of information sharing between groups can be increased after the evolved coyotes return to their original position.(b)
When coyotes grow, the traditional single growth mode of coyotes is broken, and the cultural level of the whole group is improved according to the contribution of each coyote to the whole group. The more capable coyotes contribute more to the group, while the less capable coyotes contribute less to the group, making the best use of every individual. The change of the head coyote and cultural trend can break the tradition, it is not easy to fall into the local optimal situation, and it also improves the whole group according to the contribution of each individual, thus increasing the global search ability of the algorithm.(c)
After coyotes grow, the whole group of coyotes carry out survival of the fittest, and individuals do not affect each other. In COA, the convergence speed of the algorithm is fast by survival of the fittest. ICOA can not only stay the fast convergence speed, but also increase the running speed and stability of the algorithm.The main research work of this paper is as follows.(1)
In the first section, introduce the background and significance of this research, summarize the research status of mobile robot path planning, and analyze the problems studied by some researchers. Explain the existing problems of COA and put forward some improvements of COA.(2)
In the second section, introduce the background of the problem and the working model of mobile robot.(3)
In the third section, describe the working principles and disadvantages of COA.(4)
In the fourth section, aiming at the shortcomings of COA, ICOA is proposed.(5)
In the fifth section, apply ICOA in mobile robot path planning, and the effectiveness of ICOA is verified on different maps. Analyze the results, consider the influence of parameters on ICOA, and add time complexity analysis.(6)
In the last section, discuss and summarize the study, and provide some suggestions for future research.


## 2. Mathematical Model

As shown in Figure1, the working environment of the mobile robot is a square grid map, with a unit of 1 m for each grid. In the map, each grid is encoded as a real number, the white grids are the part where the robot can move, marked 1 in the array, and the black grids are obstacles, marked 0 in the array. Each point has a coordinate, and the starting point and the ending point have been indicated. The robot is required to be able to find the shortest path from the starting point to the ending point without touching obstacles on the map [23].Figure 1
(a) The grid map. (b) The coded grid map.
(a)(b)To reflect the effectiveness of the algorithm, the simulation is carried out in different maps. In this study, map specifications are set as20×20 and 30×30, and each specification generates human-designed maps and randomly generated maps.


## 3. COA Theoretical Background

COA is a swarm intelligence optimization algorithm proposed by Pierezan in 2018 inspired by the coyote population [8]. Compared with other swarm intelligence optimization algorithms, COA has a unique structure. COA simulates the birth, growth, death, and migration of coyotes, so it is divided into four stages: population initialization, growth of coyotes, birth and death of coyotes, deportation and acceptance [24].


### 3.1. Population Initialization

To initialize the population and group randomly, firstly set the algorithm parameters: the number of population isN, Np is the number of groups, Nc is the number of coyotes in each group, and N=Nc×Np, Nc≤14. Each individual is randomly initialized, and each individual is represented in the form of a vector, then the social state of the cth individual in the pth population can be expressed as(1)xj=lj+r×uj−lj,soccp=x1,x2,…,xD,where j=1,2,…,D, D is the dimension, r is the random number between [0.1], and uj and lj are the upper and lower limits of the social factor in the jth dimension.The adaptability of each coyote to society is known as fitness, suppose that the fitness function isfx, then the corresponding fitness value of each coyote is(2)fit=fsoc.


### 3.2. The Growth of Coyotes

In COA, each group is composed of a certain number of coyotes and a leading coyote, the coyote who adapts most to society is the leading individual of the group (i.e., the head coyote), denoted byalpha. In addition, COA focuses on the shared social structure and behavior of coyotes, defined as intragroup cultural trends, denoted by cult, and represented by the median individual in each group.(3)alphap=soccp|argcminfsoccp,cultp=QNc/2p+QNc+1/2p2,Nc∈even numbers,QNc+1/2p,Nc∈odd  numbers,where alpha is the coyote whose fitness function is smallest within the group, and Q is the rank of social factors in each group.The growth of coyotes in the group depends not only onalpha and cult, but also on the choice of two random coyotes in the group. In the process of coyote growth, coyote individuals will be updated successively, and new coyotes will be obtained, denoted by new_soc. Choose whether to accept the new individuals according to the greedy algorithm, that is, if the social fitness of the coyote is better after growth, the new coyote will be retained; otherwise, the new coyote will remain unchanged.(4)δ1=alphap−soccr1p,δ2=cultp−soccr2p,new_soccp=soccp+r1×δ1+r2×δ2,soccpt+1=new_soccpt,fnew_soccpt<fsoccpt,soccpt,otherwise,where cr1,cr2 are randomly selected individuals in each group, and r1,r2 are random numbers between [0,1].


### 3.3. The Birth and Death of Coyotes

The birth and death of coyotes are determined by both parents and environmental factors, and the birth of coyotes is defined as(5)pupjp=socm1,jp,rndj<Psorj=j1,socm2,jp,rndj≥Ps+Paorj=j1,Rj,otherwise,where m1,m2 are two random coyotes in the pth group, j1,j2 are random dimension, rndj is the uniformly distributed random number within [0, 1], Rj is the random number generated within the scope of the jth dimensional social state, Ps is a discrete probability, and Pa is associated probability, which are defined as(6)Ps=1D,Pa=1−Ps2.When a new coyote born, an individual is added to the population. To keep the population size unchanged, the fitness value of each coyote will determine whether the coyote in the population will live or die. If the fitness value of the newborn coyote is the worst in the population, the newborn coyote dies. If there was a coyote with worse fitness than newborn coyote, the coyote with the worst fitness dies.


### 3.4. Deportation and Acceptance of Coyotes

To ensure information sharing and further cultural communication between groups, coyotes will leave the current group and enter other groups at a certain probability, with the probability as follows:(7)Pe=0.005Nc2,Nc≤14.Compared with other algorithms, COA has a special structure, showing the following advantages: (1) The population grouping system, showing a better search model and framework, has certain search ability. (2) The algorithm has a certain local search ability through the leading coyote and cultural trend guidance. (3) Using greedy algorithm to select the fittest can accelerate the convergence speed of the algorithm. (4) Newborn coyotes are affected by environment and parent coyotes, so the algorithm has a certain global search ability. (5) Deportation and acceptance of population enable cultural exchange between groups and maintain the diversity of the population, thus increasing the global search ability of the algorithm.


## 3.1. Population Initialization

To initialize the population and group randomly, firstly set the algorithm parameters: the number of population isN, Np is the number of groups, Nc is the number of coyotes in each group, and N=Nc×Np, Nc≤14. Each individual is randomly initialized, and each individual is represented in the form of a vector, then the social state of the cth individual in the pth population can be expressed as(1)xj=lj+r×uj−lj,soccp=x1,x2,…,xD,where j=1,2,…,D, D is the dimension, r is the random number between [0.1], and uj and lj are the upper and lower limits of the social factor in the jth dimension.The adaptability of each coyote to society is known as fitness, suppose that the fitness function isfx, then the corresponding fitness value of each coyote is(2)fit=fsoc.


## 3.2. The Growth of Coyotes

In COA, each group is composed of a certain number of coyotes and a leading coyote, the coyote who adapts most to society is the leading individual of the group (i.e., the head coyote), denoted byalpha. In addition, COA focuses on the shared social structure and behavior of coyotes, defined as intragroup cultural trends, denoted by cult, and represented by the median individual in each group.(3)alphap=soccp|argcminfsoccp,cultp=QNc/2p+QNc+1/2p2,Nc∈even numbers,QNc+1/2p,Nc∈odd  numbers,where alpha is the coyote whose fitness function is smallest within the group, and Q is the rank of social factors in each group.The growth of coyotes in the group depends not only onalpha and cult, but also on the choice of two random coyotes in the group. In the process of coyote growth, coyote individuals will be updated successively, and new coyotes will be obtained, denoted by new_soc. Choose whether to accept the new individuals according to the greedy algorithm, that is, if the social fitness of the coyote is better after growth, the new coyote will be retained; otherwise, the new coyote will remain unchanged.(4)δ1=alphap−soccr1p,δ2=cultp−soccr2p,new_soccp=soccp+r1×δ1+r2×δ2,soccpt+1=new_soccpt,fnew_soccpt<fsoccpt,soccpt,otherwise,where cr1,cr2 are randomly selected individuals in each group, and r1,r2 are random numbers between [0,1].


## 3.3. The Birth and Death of Coyotes

The birth and death of coyotes are determined by both parents and environmental factors, and the birth of coyotes is defined as(5)pupjp=socm1,jp,rndj<Psorj=j1,socm2,jp,rndj≥Ps+Paorj=j1,Rj,otherwise,where m1,m2 are two random coyotes in the pth group, j1,j2 are random dimension, rndj is the uniformly distributed random number within [0, 1], Rj is the random number generated within the scope of the jth dimensional social state, Ps is a discrete probability, and Pa is associated probability, which are defined as(6)Ps=1D,Pa=1−Ps2.When a new coyote born, an individual is added to the population. To keep the population size unchanged, the fitness value of each coyote will determine whether the coyote in the population will live or die. If the fitness value of the newborn coyote is the worst in the population, the newborn coyote dies. If there was a coyote with worse fitness than newborn coyote, the coyote with the worst fitness dies.


## 3.4. Deportation and Acceptance of Coyotes

To ensure information sharing and further cultural communication between groups, coyotes will leave the current group and enter other groups at a certain probability, with the probability as follows:(7)Pe=0.005Nc2,Nc≤14.Compared with other algorithms, COA has a special structure, showing the following advantages: (1) The population grouping system, showing a better search model and framework, has certain search ability. (2) The algorithm has a certain local search ability through the leading coyote and cultural trend guidance. (3) Using greedy algorithm to select the fittest can accelerate the convergence speed of the algorithm. (4) Newborn coyotes are affected by environment and parent coyotes, so the algorithm has a certain global search ability. (5) Deportation and acceptance of population enable cultural exchange between groups and maintain the diversity of the population, thus increasing the global search ability of the algorithm.


## 4. Improved Coyote Optimization Algorithm

Although COA has many advantages, it still has some shortcomings due to its short presentation time: (1) The growth mode of coyotes is single, which may not apply to all coyotes, and it may show insufficient optimization ability for complex tasks. (2) The leading coyote and the cultural trend can reflect a certain local optimization ability, but it is easy to fall into the local optimal solution. In addition, the proximity of other individuals in the population may reduce the diversity of the population and increase the phenomenon of convergence. (3) Although the selection of greedy algorithm to survive the fittest can accelerate the convergence speed of the algorithm, coyotes with better social fitness are directly involved in the growth of the next generation, which will easily fall into local optimal, and the stability will be relatively reduced. To solve these problems, this paper proposed ICOA.


### 4.1. The Change in the Mode of Grouping

“Helping” is a common way of team cooperation, in this way, a group of optimal individuals can be selected to grow internally and help other groups at the same time, to achieve the purpose of improving team ability and rapid growth of the latter. Under the influence of this method, the coyote population was divided into an elite group and general groups, and the operation of the elite group leading the general groups was carried out.After randomly generatingNc×Np individuals, the fitness value of each individual is calculated, and the Nc individuals with the best social fitness are divided into a group, namely the elite group. The remaining Nc×Np−1 individuals are randomly divided into Np−1 general groups, and the Nc individuals in each group are sorted according to their social fitness, as shown in Figure 2.Figure 2
Group sorted population.


### 4.2. The Strategy of Leading the Poor

After grouping and ordering the population, the coyote with the highest social fitness in the elite group is used to guide the coyotes with the least social fitness in the other groups, and the coyote with the second highest social fitness in the elite group is used to guide the coyotes with the penult social fitness in the other groups. The coyote with the least social fitness in the elite group is used to guide the coyotes with the highest social fitness in the general groups, as shown in Figure3. By improving the social ability of the general groups, the general groups can develop in a better direction.Figure 3
Strategy of leading the poor.The cuckoo algorithm [25] is a new swarm intelligence algorithm proposed by Yang in 2009, based on cuckoo nest parasitism and the Levy flight mechanism, cuckoo algorithm has few parameters, simple operation, fast convergence speed, can help quickly jump out of local optimum, and has certain global search ability [26].According to the nest position updating mechanism in the cuckoo algorithm, individuals in the elite group guide the individuals in the general groups, which can be expressed as follows:(8)stepc=α×s.×xc−yNc−cpp,s=μv1/β,new_yNc−cpp=yNc−cpp+r×stepc+1−r×yNc−cpp1−yNc−cpp2,where α is the scaling factor of step size, α=0.01; s is the step of Levy flight, β=1.5, μ,v are normally distributed random numbers; xc is the cth individual in the elite group, yNc−cpp is the (Nc-c) th individual in the ppth general group, new_yNc−cpp is the (Nc-c) th new individual in the ppth general group, pp=1,2,…,p−1; yNc−cpp1 and yNc−cpp2 are (Nc-c) th individuals in the pp1 th and pp2 th general group, and r is the random number between [0,1].After generating new individuals in the general group, judge the size ofrd and Pd, and rd is a random number between [0,1], take 0.25 for Pd, if rd>Pd, the new individual updates according to formula:(9)new_yNc−cpp=yNc−cpp+rd×xc−yNc−cpp.Ifrd<Pd, the new individual is not updated.In the above process, the elite group can reflect the social fitness of the whole population to a certain extent. Through the strategy of leading the poor, the individuals in the general groups can develop in a better direction, which reflects the strong local search ability. In the process of the evolution of new individuals, due to the differences between the elite group of individuals and the general groups of individuals, the randomness of the Levy flight mechanism and the selection of random individuals in the same level population, so that the global search ability of the algorithm increases. In conclusion, the application of the strategy of leading the poor can not only make the coyotes with poor social fitness develop in a better direction but also increase the search ability of the algorithm, thus improving the social level of the whole population.


### 4.3. New Growth Mode

In COA, the growth mode of coyotes includes: the guidance of the head coyote and group cultural trends, and use greedy algorithm to survive the fittest. Although the mode has certain local search ability, the head coyote and group cultural trends in each group are the same. It is easy to fall into local optimal solution, increase the possibility of convergence, decrease the species diversity, so the ability of optimization is insufficient. Therefore, a new growth method is proposed to solve these problems.As coyotes of general groups evolve, individuals in each group return to their original position and start to grow. Since COA has a fixed head coyote in each group, its guidance will increase the possibility of convergence and falling into the local optimal solution. Considering that each individual in each group has a certain contribution and influence on the group, in the comprehensive evaluation, the weight of the comprehensive evaluation can be determined by combining the information entropy with the contribution rate of the principal component [27]. Considering the contribution degree of each individual in each group to the level of the group, the updating method of the head coyote in each group is as follows:(1)
Calculate the fitness value of each individual in each group and arrange the fitness values in descending order, denoting asFp=fit1p,fit2p,…,fitNcp.(2)
Calculate the contribution of each individual to the social fitness of the group, which can be expressed as(10)ω1p=fit1p∑Fp,ω2p=fit2p∑Fp,ωNcp=fitNcp∑Fp.(3)
Sort coyotes of each group according to the social fitness value from small to large, and write assocp=soc1p,soc2p,…,socNcp. The updating formula of the new head coyote becomes(11)new_alphap=ω1p×soc1p+ω2p×soc2p+…+ωNcp×socNcp.After getting a new head coyote, one individual will be added to each group, the individual with the worst social fitness value will be weeded out to maintain consistency in the population.The updating formula of cultural trends in the group has changed from the original median to the average of the social fitness of the coyotes in each group. The choice of the median will not be influenced by small or large data, but it cannot reflect the level of the whole group. The average value can reflect the individuals' contribution and influence on the overall level in each group, and it represents the overall trend of the group, so the new trend of a group culture is expressed as(12)new_cultp=meanQp,where meanQp represents the average social status of all coyotes in the pth group.Standard deviation reflects the dispersion degree and overall level of a group to a certain extent, and plays a certain auxiliary role in the renewal of coyotes. After obtaining the cultural trends and the head coyote of each group, the renewal mode of each individual becomes:(13)δ3=stdQp,new_soccp=soccp+δ1×r1+δ2×r2+δ3×r3,where stdQp represents the deviation of the social status of all coyotes in the pth population, and r3 is the random number between [0, 1].Individuals returning to their original position after evolution can increase cultural communication between groups, thus increasing the degree of information sharing. The new growth mode uses the contribution degree of each individual to the whole level of the group to renew the head coyote, so that each individual has a certain influence on the development of the group, which reflects the strong global search ability. According to the calculation of contribution degree, it is not difficult to find that coyotes with better social fitness contribute more to the group, while coyotes with poor social fitness contribute less to the group, showing certain local search ability. The calculation method of group cultural trend using average value instead of the original median reflects the contribution of each individual in each group to the group cultural trend, and then reflects the social level of the whole group. Adding standard deviation to the growth mode of coyotes expresses the influence of group stability on the growth of coyotes, and also reflects the overall social level of the group. Therefore, the new growth mode focuses more on the influence of each individual on the whole group, so that individuals in the group can better carry out cultural communication, which helps to jump out of the local optimal, ensures the search and mining ability of the algorithm, and improves the global search ability of the algorithm.


### 4.4. New Survival Strategy

COA evaluates the social fitness of each coyote after they grow up, and selects the greedy algorithm for the survival of the fittest. If the updated coyote has better social fitness than the original one, the updated coyote will be retained, otherwise it will remain unchanged. After optimal selection, the cultural trends of coyotes, individuals of coyotes, and the head coyotes will be updated successively, and then the next generation will be updated, which shows the local search ability of the algorithm. The grow-up coyotes participate in the growth of the other coyotes, which slows down the running speed. The updated coyotes will also lead the whole group to develop in the same direction, increasing the possibility of falling into local optimization, which leads to the instability of the algorithm, so the new update mode of survival of the fittest is selected.After the coyote in each group grows up, the social fitness of each individual is not evaluated, nor the survival of the fittest is carried out by greedy algorithm. Instead, after the whole group of coyotes grow up, the social fitness of each individual is evaluated, and then the survival of the fittest is carried out according to the comparison of social fitness values. In this way, each individual in each group grows on his or her own without affecting the rest of the group. It can help the algorithm jump out of the local optimal solution, improve the running speed of the algorithm, and ensure the stability of the algorithm.


### 4.5. Algorithm Principle

After COA is improved, the method is applied to the path planning of mobile robots. The path is a line segment connecting the starting point, connection points, and the ending point, and each path is denoted aszt=z1t,z2t,…,zDt. md,nd is used to represent the coordinates of the dth connection point, d=1,2,…,D , and the fitness function is(14)fit=∑dD−1md+1−md2+nd+1−nd2.The algorithm steps are as follows.(1)
Initialize the population, set the maximum number of iterationsT, and t=0.(2)
Calculate the fitness value of individuals in the population.(3)
The elite group and the general groups are generated according to the fitness value and are sorted according to the fitness value from small to large.(4)
The elite group leads the general groups to evolve, and then each individual returns to their original position.(5)
The coyotes grow in a new growth way after evolution, and complete the survival of the fittest according to the new strategy, then carry out normal birth, death, and transition, and record the optimal coyote.(6)
Sett=t+1, judge whether the maximum number of iterations is reached. If not, proceed to step (2); otherwise, the iteration ends and the optimal solution is output. The flowchart is shown in Figure 4.Figure 4
Flowchart of ICOA.


## 4.1. The Change in the Mode of Grouping

“Helping” is a common way of team cooperation, in this way, a group of optimal individuals can be selected to grow internally and help other groups at the same time, to achieve the purpose of improving team ability and rapid growth of the latter. Under the influence of this method, the coyote population was divided into an elite group and general groups, and the operation of the elite group leading the general groups was carried out.After randomly generatingNc×Np individuals, the fitness value of each individual is calculated, and the Nc individuals with the best social fitness are divided into a group, namely the elite group. The remaining Nc×Np−1 individuals are randomly divided into Np−1 general groups, and the Nc individuals in each group are sorted according to their social fitness, as shown in Figure 2.Figure 2
Group sorted population.


## 4.2. The Strategy of Leading the Poor

After grouping and ordering the population, the coyote with the highest social fitness in the elite group is used to guide the coyotes with the least social fitness in the other groups, and the coyote with the second highest social fitness in the elite group is used to guide the coyotes with the penult social fitness in the other groups. The coyote with the least social fitness in the elite group is used to guide the coyotes with the highest social fitness in the general groups, as shown in Figure3. By improving the social ability of the general groups, the general groups can develop in a better direction.Figure 3
Strategy of leading the poor.The cuckoo algorithm [25] is a new swarm intelligence algorithm proposed by Yang in 2009, based on cuckoo nest parasitism and the Levy flight mechanism, cuckoo algorithm has few parameters, simple operation, fast convergence speed, can help quickly jump out of local optimum, and has certain global search ability [26].According to the nest position updating mechanism in the cuckoo algorithm, individuals in the elite group guide the individuals in the general groups, which can be expressed as follows:(8)stepc=α×s.×xc−yNc−cpp,s=μv1/β,new_yNc−cpp=yNc−cpp+r×stepc+1−r×yNc−cpp1−yNc−cpp2,where α is the scaling factor of step size, α=0.01; s is the step of Levy flight, β=1.5, μ,v are normally distributed random numbers; xc is the cth individual in the elite group, yNc−cpp is the (Nc-c) th individual in the ppth general group, new_yNc−cpp is the (Nc-c) th new individual in the ppth general group, pp=1,2,…,p−1; yNc−cpp1 and yNc−cpp2 are (Nc-c) th individuals in the pp1 th and pp2 th general group, and r is the random number between [0,1].After generating new individuals in the general group, judge the size ofrd and Pd, and rd is a random number between [0,1], take 0.25 for Pd, if rd>Pd, the new individual updates according to formula:(9)new_yNc−cpp=yNc−cpp+rd×xc−yNc−cpp.Ifrd<Pd, the new individual is not updated.In the above process, the elite group can reflect the social fitness of the whole population to a certain extent. Through the strategy of leading the poor, the individuals in the general groups can develop in a better direction, which reflects the strong local search ability. In the process of the evolution of new individuals, due to the differences between the elite group of individuals and the general groups of individuals, the randomness of the Levy flight mechanism and the selection of random individuals in the same level population, so that the global search ability of the algorithm increases. In conclusion, the application of the strategy of leading the poor can not only make the coyotes with poor social fitness develop in a better direction but also increase the search ability of the algorithm, thus improving the social level of the whole population.


## 4.3. New Growth Mode

In COA, the growth mode of coyotes includes: the guidance of the head coyote and group cultural trends, and use greedy algorithm to survive the fittest. Although the mode has certain local search ability, the head coyote and group cultural trends in each group are the same. It is easy to fall into local optimal solution, increase the possibility of convergence, decrease the species diversity, so the ability of optimization is insufficient. Therefore, a new growth method is proposed to solve these problems.As coyotes of general groups evolve, individuals in each group return to their original position and start to grow. Since COA has a fixed head coyote in each group, its guidance will increase the possibility of convergence and falling into the local optimal solution. Considering that each individual in each group has a certain contribution and influence on the group, in the comprehensive evaluation, the weight of the comprehensive evaluation can be determined by combining the information entropy with the contribution rate of the principal component [27]. Considering the contribution degree of each individual in each group to the level of the group, the updating method of the head coyote in each group is as follows:(1)
Calculate the fitness value of each individual in each group and arrange the fitness values in descending order, denoting asFp=fit1p,fit2p,…,fitNcp.(2)
Calculate the contribution of each individual to the social fitness of the group, which can be expressed as(10)ω1p=fit1p∑Fp,ω2p=fit2p∑Fp,ωNcp=fitNcp∑Fp.(3)
Sort coyotes of each group according to the social fitness value from small to large, and write assocp=soc1p,soc2p,…,socNcp. The updating formula of the new head coyote becomes(11)new_alphap=ω1p×soc1p+ω2p×soc2p+…+ωNcp×socNcp.After getting a new head coyote, one individual will be added to each group, the individual with the worst social fitness value will be weeded out to maintain consistency in the population.The updating formula of cultural trends in the group has changed from the original median to the average of the social fitness of the coyotes in each group. The choice of the median will not be influenced by small or large data, but it cannot reflect the level of the whole group. The average value can reflect the individuals' contribution and influence on the overall level in each group, and it represents the overall trend of the group, so the new trend of a group culture is expressed as(12)new_cultp=meanQp,where meanQp represents the average social status of all coyotes in the pth group.Standard deviation reflects the dispersion degree and overall level of a group to a certain extent, and plays a certain auxiliary role in the renewal of coyotes. After obtaining the cultural trends and the head coyote of each group, the renewal mode of each individual becomes:(13)δ3=stdQp,new_soccp=soccp+δ1×r1+δ2×r2+δ3×r3,where stdQp represents the deviation of the social status of all coyotes in the pth population, and r3 is the random number between [0, 1].Individuals returning to their original position after evolution can increase cultural communication between groups, thus increasing the degree of information sharing. The new growth mode uses the contribution degree of each individual to the whole level of the group to renew the head coyote, so that each individual has a certain influence on the development of the group, which reflects the strong global search ability. According to the calculation of contribution degree, it is not difficult to find that coyotes with better social fitness contribute more to the group, while coyotes with poor social fitness contribute less to the group, showing certain local search ability. The calculation method of group cultural trend using average value instead of the original median reflects the contribution of each individual in each group to the group cultural trend, and then reflects the social level of the whole group. Adding standard deviation to the growth mode of coyotes expresses the influence of group stability on the growth of coyotes, and also reflects the overall social level of the group. Therefore, the new growth mode focuses more on the influence of each individual on the whole group, so that individuals in the group can better carry out cultural communication, which helps to jump out of the local optimal, ensures the search and mining ability of the algorithm, and improves the global search ability of the algorithm.


## 4.4. New Survival Strategy

COA evaluates the social fitness of each coyote after they grow up, and selects the greedy algorithm for the survival of the fittest. If the updated coyote has better social fitness than the original one, the updated coyote will be retained, otherwise it will remain unchanged. After optimal selection, the cultural trends of coyotes, individuals of coyotes, and the head coyotes will be updated successively, and then the next generation will be updated, which shows the local search ability of the algorithm. The grow-up coyotes participate in the growth of the other coyotes, which slows down the running speed. The updated coyotes will also lead the whole group to develop in the same direction, increasing the possibility of falling into local optimization, which leads to the instability of the algorithm, so the new update mode of survival of the fittest is selected.After the coyote in each group grows up, the social fitness of each individual is not evaluated, nor the survival of the fittest is carried out by greedy algorithm. Instead, after the whole group of coyotes grow up, the social fitness of each individual is evaluated, and then the survival of the fittest is carried out according to the comparison of social fitness values. In this way, each individual in each group grows on his or her own without affecting the rest of the group. It can help the algorithm jump out of the local optimal solution, improve the running speed of the algorithm, and ensure the stability of the algorithm.


## 4.5. Algorithm Principle

After COA is improved, the method is applied to the path planning of mobile robots. The path is a line segment connecting the starting point, connection points, and the ending point, and each path is denoted aszt=z1t,z2t,…,zDt. md,nd is used to represent the coordinates of the dth connection point, d=1,2,…,D , and the fitness function is(14)fit=∑dD−1md+1−md2+nd+1−nd2.The algorithm steps are as follows.(1)
Initialize the population, set the maximum number of iterationsT, and t=0.(2)
Calculate the fitness value of individuals in the population.(3)
The elite group and the general groups are generated according to the fitness value and are sorted according to the fitness value from small to large.(4)
The elite group leads the general groups to evolve, and then each individual returns to their original position.(5)
The coyotes grow in a new growth way after evolution, and complete the survival of the fittest according to the new strategy, then carry out normal birth, death, and transition, and record the optimal coyote.(6)
Sett=t+1, judge whether the maximum number of iterations is reached. If not, proceed to step (2); otherwise, the iteration ends and the optimal solution is output. The flowchart is shown in Figure 4.Figure 4
Flowchart of ICOA.


## 5. Simulation and Results

### 5.1. Simulation Settings

To verify the effectiveness and accuracy of the algorithm in this paper, four maps were simulated on MATLAB R2016a. The four maps are, respectively, the scale of20×20 and 30×30, each scale generates artificially generated map and randomly generated map, and obstacles vary in number and shape. Table 1 shows the simulation environments in each map.Table 1
Description of simulation environments.
MapScaleProportion of obstacles (%)The starting point/Real numberThe ending point/Real number120×2018.00(1,1)/1(20,20)/328220×2020.50(1,20)/301(20,1)/15330×3015.56(8,8)/183(23,23)/578430×3020.33(1,30)/692(30,1)/27To contrast obviously, choose the other seven algorithms compared with the algorithm in this paper, select COA, grey wolf optimizer (GWO), PSO, five-elements cycle optimization algorithm (FECO), ACO, artificial bee colony algorithm (ABC), and sparrow search algorithm (SSA). Parameter settings of other algorithms are the best parameter settings, and the parameters of eight algorithms are shown in Table2.Table 2
Parameter settings of each algorithm.
AlgorithmsBrief descriptionParameter settingsICOAImproved coyote optimization algorithmN=100,Np=20,Nc=5,T=100.COACoyote optimization algorithmN=100,Np=20,Nc=5,T=100.GWOGrey wolf optimizera=2goes down to0,N=100,T=100.PSOParticle swarm optimization algorithmc1=c2=1.5,vmin=−1,vmax=1,wmax=0.9,wmin=0.4,T=100,N=100.FECOFive-elements cycle optimization algorithmL=5,q=20,Ps=1.0,Pm=0.9,T=100.ACOAnt colony optimization algorithmK=100,M=100,α=1,β=7,Rho=0.3,Q=1.ABCArtificial bee colony algorithmnVar=3,T=100,N=100,a=1.SSASparrow search algorithmF=20%,SD=10%,ST=0.8,T=100,N=100.


### 5.2. Simulation and Analysis of Results

These eight algorithms are used for path planning and the results are shown in Figure5.Figure 5
Eight algorithms for path planning. (a) Map 1 (20×20 by human-designed). (b) Map 2 (20×20 by randomly generated). (c) Map 3 (30×30 by human-designed). (d) Map 4 (30×30 by randomly generated).
(a)(b)(c)(d)As can be seen from Figure5, eight algorithms can effectively avoid obstacles and successfully plan paths, but the algorithm in this paper can successfully plan the shortest paths. ICOA has fewer redundant points and inflection points, while other algorithms take many detours. For instance, in map 1, ACO takes many detours, GWO and FECO fall into the trap, and none of the other four algorithms can plan the shortest path; In map 2, the other seven algorithms go further than ICOA, especially COA, FECO, and ACO. In complicated maps, ICOA’s advantage is even more obvious. In map 3, COA and FECO bypass the obstacles and go a longer way, and in map 4, ABC and SSA fall into the trap. The superiority of GWO, FECO, and ABC is obviously insufficient. Clearly that the proposed algorithm can not only be implemented in simple maps, but also can plan the shortest path in complex maps, which shows the global search ability, reflects the effectiveness and accuracy of the algorithm.Due to the randomness of initial data, to avoid accidental situations, 50 times of path planning are carried out for eight algorithms, respectively, and the results obtained are shown in Table3 and Figure 6.Table 3
The results of 50 times path planning by eight algorithms.
MapAlgorithmsNumberMaximumMinimumAverageStandard deviation1ICOA156.8754.8754.910.28COA264.3860.3860.570.78GWO3116.1860.3864.8910.71PSO462.3860.3860.420.37FECO574.9760.9765.373.02ACO6148.6182.08120.9814.60ABC766.3860.3860.751.22SSA862.3860.3860.690.412ICOA128.0926.3326.370.24COA241.7930.9731.411.66GWO346.3830.9734.293.29PSO431.7930.9730.980.41FECO540.1432.9736.182.11ACO636.6230.0431.811.82ABC736.6230.0431.381.25SSA834.3830.9731.500.843ICOA126.9626.1326.180.17COA245.3126.3827.283.55GWO351.2126.3837.847.03PSO429.5526.3827.641.03FECO545.5526.3835.584.69ACO637.2126.3835.094.27ABC736.1426.3826.911.79SSA841.6926.3829.594.194ICOA145.4243.4243.540.47COA262.6248.0448.502.19GWO369.2148.0452.614.35PSO448.6248.0448.100.57FECO556.8748.8752.802.38ACO663.3546.1852.383.41ABC757.5946.8747.461.91SSA852.8746.8747.591.10Figure 6
Algorithms performance by maps.Characteristic indexes of comparison including maximum, minimum, average, and standard deviation. No matter which index, ICOA is the smallest, which means ICOA produces an optimal solution every time.In ICOA, the maximum and the minimum are pretty much the same, but in other algorithms, maximum and minimum values differ greatly, GWO and ACO are obvious in map 1, six algorithms except PSO are obvious in map 2, the same situation happens in map 3 and map 4. A large difference indicates that some of the paths planned by these algorithms are large and some are small, and the paths planned each time are different. They can plan shorter paths to a certain extent, but they are extremely unstable, resulting in insufficient optimization performance of the algorithms. The average reflects a central tendency, as can be seen from these indicators, the results obtained by each path planning fluctuate around the average, ICOA fluctuates less, because the maximum, minimum, and average values are not much different, and other algorithms fluctuates more, which reflects the effectiveness of ICOA. The standard deviation can reflect the dispersion degree of a set of data, and from these values, the standard deviation value of the path distance of ICOA is the smallest, and every standard deviation is going to go to 0, which reflects the stability of the algorithm.Figure7 shows the convergence curves of each algorithm for planning each map. Table 4 shows the convergence of each algorithm on each map. As can be seen, ICOA can converge before 10 generations, the curves converge in the third, sixth, seventh, and fourth generations, thus reaching a stable state, indicating that the convergence speed of ICOA is fast, thus effectively shortening the iteration speed of the mobile robot. While other algorithms can also achieve stable state, but they have more iterations, so their convergence speed is slow. In contrast, it reflects the rapidity of ICOA.Figure 7
Convergence curves.Table 4
The convergence of algorithms on maps.
Algorithms map12345678133950254343403026253295259593637405224384345544439603644504948


### 5.3. Influence of Parameters

For ICOA, the influence of setting different parameters on the algorithm is considered in this paper, considering the number of subgroups of the population. If the population size is set to 100, based on the number of individuals in each population must be greater than 3, the possible grouping is as follows:Np=20,Nc=5; Np=10,Nc=10; Np=25,Nc=4. In order to verify the effectiveness of the grouping method in this paper, running tests on 9 different test functions [28] are shown in Table 5.Table 5
Results of different groups on 9 test functions.
Test functionsNp=20,Nc=5Np=10,Nc=10Np=25,Nc=4f1x=∑i=1nxi24.90e-127.19e-085.13e-04f2x=∑i=1nxi+∏i=1nxi3.75e-072.04e-081.40e-04f3x=∑i=1n∑j=1ixj21.61e-049.17e-042.3362f4x=maxixi,1≤i≤n8.28e-040.65343.8191f5x=∑i=1n−1100xi+1−xi22+xi−127.54e-040.23662.1809f6x=∑i=1nxi+0.526.26e-123.74e-071.29e-05f7x=∑i=1nixi4+random0,10.00980.00380.0047f8x=∑i=1nxi2−10cos2πxi+101.04e-091.10e-078.76e-05f9x=−20exp−0.21/n∑i=1nxi2−exp1/n∑i=1ncos2πxi+20+e1.04e-061.96e-040.0221Friedman sorting1.331.782.89Table5 shows different situations in grouping, the results obtained when Np=20,Nc=5 are generally better than the other two cases. The above results were Friedman tested and the significance level was set to 0.005. According to Friedman sorting, the most suitable parameter is Np=20,Nc=5.


### 5.4. Time Complexity Analysis

In this paper, the time complexity of the algorithm includes the complexity of the objective function and the complexity of the algorithm itself [20]. Due to the consistency of the working environment and some parameters, the complexity of the objective function is not considered during the calculation of all algorithms, and only considers the complexity of the algorithm itself here. ICOA including: population initialization, population grouping strategy, the strategy of leading the poor, new growth mode, new survival strategy, birth and death, and transition. Set their calculation time in units as t1,t2,t3,t4,t5,t6,t7, the maximum number of iterations is T, the population size is N, Np=20,Nc=5, and the dimension is D. The time complexity of ICOA is(15)OICOA=OD×N×t1+T×t2+T×D×Np×t3+T×D×N×t4+T×D×Np×t5+T×D×Np×t6+T×D×Np×t7.Although ICOA adds the strategy of population grouping and leading the poor, new survival strategy changes. New survival strategy reduces the running time, and the strategy of population grouping and leading the poor increase the running time. Figure8 shows the time complexity of all algorithms.Figure 8
The time complexity of all algorithms.Compared with FECO, PSO, and ACO, ICOA has insufficient advantages in running speed, but its performance is better than COA, GWO, ABC, and SSA. As ICOA is an improved algorithm of COA, the average running time of ICOA and COA are, respectively, 8.96 s and 9.55 s, although the time is similar, ICOA is a little bit faster, which indicates that the new survival strategy reduces more time, thus reducing the time complexity.In conclusion, although other algorithms can also plan certain paths, their obstacle avoidance ability is poor, which affects the quality and stability of solution. Even though some algorithms can plan paths with similar distances to ICOA, their stability is far less than that of ICOA. ICOA has obvious advantages over other algorithms in terms of distance, stability, and effectiveness, which indicates the correctness of ICOA.


## 5.1. Simulation Settings

To verify the effectiveness and accuracy of the algorithm in this paper, four maps were simulated on MATLAB R2016a. The four maps are, respectively, the scale of20×20 and 30×30, each scale generates artificially generated map and randomly generated map, and obstacles vary in number and shape. Table 1 shows the simulation environments in each map.Table 1
Description of simulation environments.
MapScaleProportion of obstacles (%)The starting point/Real numberThe ending point/Real number120×2018.00(1,1)/1(20,20)/328220×2020.50(1,20)/301(20,1)/15330×3015.56(8,8)/183(23,23)/578430×3020.33(1,30)/692(30,1)/27To contrast obviously, choose the other seven algorithms compared with the algorithm in this paper, select COA, grey wolf optimizer (GWO), PSO, five-elements cycle optimization algorithm (FECO), ACO, artificial bee colony algorithm (ABC), and sparrow search algorithm (SSA). Parameter settings of other algorithms are the best parameter settings, and the parameters of eight algorithms are shown in Table2.Table 2
Parameter settings of each algorithm.
AlgorithmsBrief descriptionParameter settingsICOAImproved coyote optimization algorithmN=100,Np=20,Nc=5,T=100.COACoyote optimization algorithmN=100,Np=20,Nc=5,T=100.GWOGrey wolf optimizera=2goes down to0,N=100,T=100.PSOParticle swarm optimization algorithmc1=c2=1.5,vmin=−1,vmax=1,wmax=0.9,wmin=0.4,T=100,N=100.FECOFive-elements cycle optimization algorithmL=5,q=20,Ps=1.0,Pm=0.9,T=100.ACOAnt colony optimization algorithmK=100,M=100,α=1,β=7,Rho=0.3,Q=1.ABCArtificial bee colony algorithmnVar=3,T=100,N=100,a=1.SSASparrow search algorithmF=20%,SD=10%,ST=0.8,T=100,N=100.


## 5.2. Simulation and Analysis of Results

These eight algorithms are used for path planning and the results are shown in Figure5.Figure 5
Eight algorithms for path planning. (a) Map 1 (20×20 by human-designed). (b) Map 2 (20×20 by randomly generated). (c) Map 3 (30×30 by human-designed). (d) Map 4 (30×30 by randomly generated).
(a)(b)(c)(d)As can be seen from Figure5, eight algorithms can effectively avoid obstacles and successfully plan paths, but the algorithm in this paper can successfully plan the shortest paths. ICOA has fewer redundant points and inflection points, while other algorithms take many detours. For instance, in map 1, ACO takes many detours, GWO and FECO fall into the trap, and none of the other four algorithms can plan the shortest path; In map 2, the other seven algorithms go further than ICOA, especially COA, FECO, and ACO. In complicated maps, ICOA’s advantage is even more obvious. In map 3, COA and FECO bypass the obstacles and go a longer way, and in map 4, ABC and SSA fall into the trap. The superiority of GWO, FECO, and ABC is obviously insufficient. Clearly that the proposed algorithm can not only be implemented in simple maps, but also can plan the shortest path in complex maps, which shows the global search ability, reflects the effectiveness and accuracy of the algorithm.Due to the randomness of initial data, to avoid accidental situations, 50 times of path planning are carried out for eight algorithms, respectively, and the results obtained are shown in Table3 and Figure 6.Table 3
The results of 50 times path planning by eight algorithms.
MapAlgorithmsNumberMaximumMinimumAverageStandard deviation1ICOA156.8754.8754.910.28COA264.3860.3860.570.78GWO3116.1860.3864.8910.71PSO462.3860.3860.420.37FECO574.9760.9765.373.02ACO6148.6182.08120.9814.60ABC766.3860.3860.751.22SSA862.3860.3860.690.412ICOA128.0926.3326.370.24COA241.7930.9731.411.66GWO346.3830.9734.293.29PSO431.7930.9730.980.41FECO540.1432.9736.182.11ACO636.6230.0431.811.82ABC736.6230.0431.381.25SSA834.3830.9731.500.843ICOA126.9626.1326.180.17COA245.3126.3827.283.55GWO351.2126.3837.847.03PSO429.5526.3827.641.03FECO545.5526.3835.584.69ACO637.2126.3835.094.27ABC736.1426.3826.911.79SSA841.6926.3829.594.194ICOA145.4243.4243.540.47COA262.6248.0448.502.19GWO369.2148.0452.614.35PSO448.6248.0448.100.57FECO556.8748.8752.802.38ACO663.3546.1852.383.41ABC757.5946.8747.461.91SSA852.8746.8747.591.10Figure 6
Algorithms performance by maps.Characteristic indexes of comparison including maximum, minimum, average, and standard deviation. No matter which index, ICOA is the smallest, which means ICOA produces an optimal solution every time.In ICOA, the maximum and the minimum are pretty much the same, but in other algorithms, maximum and minimum values differ greatly, GWO and ACO are obvious in map 1, six algorithms except PSO are obvious in map 2, the same situation happens in map 3 and map 4. A large difference indicates that some of the paths planned by these algorithms are large and some are small, and the paths planned each time are different. They can plan shorter paths to a certain extent, but they are extremely unstable, resulting in insufficient optimization performance of the algorithms. The average reflects a central tendency, as can be seen from these indicators, the results obtained by each path planning fluctuate around the average, ICOA fluctuates less, because the maximum, minimum, and average values are not much different, and other algorithms fluctuates more, which reflects the effectiveness of ICOA. The standard deviation can reflect the dispersion degree of a set of data, and from these values, the standard deviation value of the path distance of ICOA is the smallest, and every standard deviation is going to go to 0, which reflects the stability of the algorithm.Figure7 shows the convergence curves of each algorithm for planning each map. Table 4 shows the convergence of each algorithm on each map. As can be seen, ICOA can converge before 10 generations, the curves converge in the third, sixth, seventh, and fourth generations, thus reaching a stable state, indicating that the convergence speed of ICOA is fast, thus effectively shortening the iteration speed of the mobile robot. While other algorithms can also achieve stable state, but they have more iterations, so their convergence speed is slow. In contrast, it reflects the rapidity of ICOA.Figure 7
Convergence curves.Table 4
The convergence of algorithms on maps.
Algorithms map12345678133950254343403026253295259593637405224384345544439603644504948


## 5.3. Influence of Parameters

For ICOA, the influence of setting different parameters on the algorithm is considered in this paper, considering the number of subgroups of the population. If the population size is set to 100, based on the number of individuals in each population must be greater than 3, the possible grouping is as follows:Np=20,Nc=5; Np=10,Nc=10; Np=25,Nc=4. In order to verify the effectiveness of the grouping method in this paper, running tests on 9 different test functions [28] are shown in Table 5.Table 5
Results of different groups on 9 test functions.
Test functionsNp=20,Nc=5Np=10,Nc=10Np=25,Nc=4f1x=∑i=1nxi24.90e-127.19e-085.13e-04f2x=∑i=1nxi+∏i=1nxi3.75e-072.04e-081.40e-04f3x=∑i=1n∑j=1ixj21.61e-049.17e-042.3362f4x=maxixi,1≤i≤n8.28e-040.65343.8191f5x=∑i=1n−1100xi+1−xi22+xi−127.54e-040.23662.1809f6x=∑i=1nxi+0.526.26e-123.74e-071.29e-05f7x=∑i=1nixi4+random0,10.00980.00380.0047f8x=∑i=1nxi2−10cos2πxi+101.04e-091.10e-078.76e-05f9x=−20exp−0.21/n∑i=1nxi2−exp1/n∑i=1ncos2πxi+20+e1.04e-061.96e-040.0221Friedman sorting1.331.782.89Table5 shows different situations in grouping, the results obtained when Np=20,Nc=5 are generally better than the other two cases. The above results were Friedman tested and the significance level was set to 0.005. According to Friedman sorting, the most suitable parameter is Np=20,Nc=5.


## 5.4. Time Complexity Analysis

In this paper, the time complexity of the algorithm includes the complexity of the objective function and the complexity of the algorithm itself [20]. Due to the consistency of the working environment and some parameters, the complexity of the objective function is not considered during the calculation of all algorithms, and only considers the complexity of the algorithm itself here. ICOA including: population initialization, population grouping strategy, the strategy of leading the poor, new growth mode, new survival strategy, birth and death, and transition. Set their calculation time in units as t1,t2,t3,t4,t5,t6,t7, the maximum number of iterations is T, the population size is N, Np=20,Nc=5, and the dimension is D. The time complexity of ICOA is(15)OICOA=OD×N×t1+T×t2+T×D×Np×t3+T×D×N×t4+T×D×Np×t5+T×D×Np×t6+T×D×Np×t7.Although ICOA adds the strategy of population grouping and leading the poor, new survival strategy changes. New survival strategy reduces the running time, and the strategy of population grouping and leading the poor increase the running time. Figure8 shows the time complexity of all algorithms.Figure 8
The time complexity of all algorithms.Compared with FECO, PSO, and ACO, ICOA has insufficient advantages in running speed, but its performance is better than COA, GWO, ABC, and SSA. As ICOA is an improved algorithm of COA, the average running time of ICOA and COA are, respectively, 8.96 s and 9.55 s, although the time is similar, ICOA is a little bit faster, which indicates that the new survival strategy reduces more time, thus reducing the time complexity.In conclusion, although other algorithms can also plan certain paths, their obstacle avoidance ability is poor, which affects the quality and stability of solution. Even though some algorithms can plan paths with similar distances to ICOA, their stability is far less than that of ICOA. ICOA has obvious advantages over other algorithms in terms of distance, stability, and effectiveness, which indicates the correctness of ICOA.


## 6. Discussion and Conclusion

In this paper, we propose an improved algorithm to solve the path planning problem of mobile robots, i.e., IOCA. It can meet the requirements of global search capability, convergence speed, and stability. Based on traditional COA, we made the following improvements: (a) The traditional grouping method is changed, and the strategy of leading the poor is introduced, and the formula is updated by levy flight mechanism in cuckoo algorithm, so that the individuals with better performance can give full play to their advantages and guide the evolution of the individuals with worse performance. (b) As the less expressive individuals evolved and coyotes started grow, we changed the way coyotes grew to include information entropy and contribution rate. The ratio of individual fitness value to the fitness value of the whole group was taken as the contribution rate, and the smaller individual fitness value would contribute more, while the larger individual fitness value would contribute less, so as to renew the head coyote. In the update of group cultural trend, the original median was changed to mean, and the influence of standard deviation was added. This reflects each individual’s contribution to the whole population. (c) The method of survival of the fittest is changed. In traditional COA, each individual is compared with the original individual after growth, so as to be eliminated. This method is easy to fall into local optimum and has poor stability. In ICOA, after the whole group grow, the survival of the fittest is carried out, weeding out the individuals with poor fitness values. On the premise of ensuring the convergence speed of the algorithm, the global search ability is enhanced and the stability is improved.ICOA is applied to the path planning of mobile robot. In the experiment, four maps are used to simulate, respectively. The results show that ICOA can plan the shortest path on simple maps and has obvious advantages on complex maps. In order to compare clearly, other seven different algorithms are used to simulate respectively, and the results show that ICOA has better optimization ability, rapidity and stability than other algorithms.However, this algorithm is only applicable to static path planning, for dynamic path planning, the advantages of this algorithm are not obvious, resulting in limited scope of application. In terms of running time, the algorithm's running time is only slightly better than that of COA and slightly worse than the others. In the future, dynamic path planning, improvement of running time and trajectory optimization will be further studied.



---

*Source: 4465542-2022-06-17.xml*