# Mobile Robot Path Planning Using Polyclonal-Based Artificial Immune Network

Authors: Lixia Deng; Xin Ma; Jason Gu; Yibin Li
Journal: Journal of Control Science and Engineering
 (2013)

---

## Abstract

Polyclonal based artificial immune network (PC-AIN) is utilized for mobile robot path planning. Artificial immune network (AIN) has been widely used in optimizing the navigation path with the strong searching ability and learning ability. However, artificial immune network exists as a problem of immature convergence which some or all individuals tend to the same extreme value in the solution space. Thus, polyclonal-based artificial immune network algorithm is proposed to solve the problem of immature convergence in complex unknown static environment. Immunity polyclonal algorithm (IPCA) increases the diversity of antibodies which tend to the same extreme value and finally selects the antibody with highest concentration. Meanwhile, immunity polyclonal algorithm effectively solves the problem of local minima caused by artificial potential field during the structure of parameter in artificial immune network. Extensive experiments show that the proposed method not only solves immature convergence problem of artificial immune network but also overcomes local minima problem of artificial potential field. So, mobile robot can avoid obstacles, escape traps, and reach the goal with optimum path and faster convergence speed.


---

## Body

## 1. Introduction

Robot path planning is one of the most fundamental functions for mobile robot. There are two types of planning for autonomous mobile robot based on how much information is known about static environment: global path planning when the environment is clearly known and sensory-based local path planning when partial or no information about the environment is known in advance [1]. In the global path planning, the environment surrounding the robot and the position of obstacles are well known in advance, and the robot is required to navigate to its destination with avoiding obstacles. The complete robot path in such applications can be calculated from the prior knowledge of the coordinates of the starting point, the destination point, and obstacles. On the other hand, the local motion planning dynamically guides the robot according to the locally sensed obstacles, which requires less prior knowledge about the environment. Therefore, the local path planning methods are more suitable and practical for mobile robot, since the environment is too complicated to be known precisely and may also be time-varying [2]. While, the local path planning faces significant challenges.This paper focuses on mobile robot path planning in unknown complex static environment. Artificial immune network (AIN) can optimize mobile robot path planning, but it exists as a problem of immature convergence. So polyclonal-based artificial immune network (PC-AIN) is proposed to solve the problem. Immunity polyclonal algorithm (IPCA) increases the diversity of antibodies which tend to the same extreme value through clonal operator, clonal crossover operator, clonal mutation operator and clonal selection operator, and finally selects the antibody with highest concentration. Meanwhile, immunity polyclonal algorithm solves the problem of local minima caused by artificial potential field during the structure of parameter in artificial immune network. Experimental results show that the proposed method effectively optimizes path planning and improves the performance of path planning.The remainder of this paper is organized as follows. The next section discusses related works for autonomous mobile robot path planning in unknown complex environment. Section3 presents the proposed mobile robot path planning algorithm in detail. Simulation results and real-time experiments are presented in Section 4. Finally, Section 5 concludes the paper.


## 2. The Related Works

Local path planning in unknown complex environment is a hot research topic in recent years. Artificial potential field-based path planning algorithm [3, 4] utilizes the attractive force from goals and the repulsive force from obstacles for mobile robot path planning. This method is known for its mathematical simplicity and little computation, but it suffers from a problem of local minima. Many artificial intelligent techniques have been proposed by scholars for mobile robot path planning, such as reinforcement learning, fuzzy logic, and genetic algorithm. Reinforcement learning algorithm [1, 5, 6] has simple and complete theory, but it is mostly used in static environment because its infinite state in complex environment. Fuzzy logic control (FLC) [7–9] has the capacity to handle uncertain and imprecise information obtained from sensors using linguistic rules. The advantages of fuzzy system are that it does not require precise analytical models of environment and it has better real-time performance, but its computational complexity increases with the geometric progression growth of rules’ number. Genetic algorithm (GA) [10, 11] is a multipoint searching algorithm, and it is more likely to search the global optimal solution in static and dynamic environment. However, GA suffers from immature convergence in complex environment.Artificial immune system (AIS) is an optimization algorithm based on the biological immune system. It has the following features: self-organization, intelligence, recognition, adaptation, and self-learning. There are lots of researches investigating the interactions between various components of the immune system or the overall behaviors of systems based on an immunological point of view. Artificial immune system mainly includes the following categories.Innate immune-based path planner: Deepak et al. [12] proposed a motion planner motivated from the biological innate immune system. To actuate a suitable robotic action, one new parameter named as learning rate has been introduced. The further movement of robot is decided by selecting of a suitable robot predefined task, so the robot will move in sequence until it reaches to its destination. Robot actions are defined as antibodies and environmental scenarios are defined as antigens. The algorithm is simple and less numerical complex because of very few controlling parameters in this structure.Immune genetic algorithm: Chen et al. [13] proposed a new method of optimal path planning for mobile robots based on immune genetic algorithm with elitism. The grid theory is utilized to establish the free space model of the mobile robot in a given environment, and a sequence number is used to identify a grid. The initial chromosomes are generated with a string of sequence numbers. Meanwhile, an insertion operator and a deletion operator are defined to ensure that each obtained path is continuous and collision-free.Jerne’s idiotypic immune network: many researchers utilize the equation generated by Farmer et al. based on the hypothesis proposed by Jerne (1973) for path planning.(1)Immune network model: Raza and Fernandez [14] used the dynamic equation of the idiotypic system to perform searching and rescuing operation in unstructured environment. The environment is translated into antigen according to the sensory arrangement of every robot. Antibody stimulation and suppression are implemented to navigate robots along with the idiotypic connections to establish interrobot communications. Yuan et al. [15] proposed an improved artificial immune network strategy based on APF method to avoid absolute random transition of antibody and improve the searching efficiency of immune network. The environment surrounding the robot is defined as antigen and robot action is defined as antibody, respectively. The planning results of APF method is regarded as prior knowledge, and the instruction definition of new antibody is initialized through vaccine extraction and inoculation. (2)Reactive immune network: Luh and Liu [16] proposed reactive immune network algorithm for mobile robot path planning with data representation for antigens and steering directions for antibodies in the U-shape environment. In [16], the resultant force of artificial potential field is defined as the affinity between antigen and antibody. Adaptive virtual target method is used to solve the local minima problem of artificial potential field method. (3)Mixture of artificial immune algorithm: Challoo et al. [17] proposed a mixture algorithm based on immune network and negative selection. The introduction of negative selection makes the system faster to react for certain conditions which are defined as self-conditions. After computing the concentration of antibodies, there is a reward or a penalty to train an antibody incrementally. The proposed controller provides a principled way for organizing an intelligent robotic system. Moreover, implementation of this controller is done in real time in three different scenarios. Ozcelik and Sukumaran [18] used the dynamic equation of the idiotypic system as output and the concentration of helper T cells as feedback system to control the output. The squashing function is performed by awarding or penalizing the antibody based on the antibody that has the highest priority. The highest priority is given to the antibody which perfectly matches to the antigen. The concentration of helper T cells is used to compute the number of penalties computing.But the existing artificial immune network algorithm exists as a problem of immature convergence. The ability of optimizing navigation path is decreased with the decreasing of antibody diversity.Clonal selection algorithm [19–26] is a new algorithm of artificial immune algorithm, which is designed based on the adaptive immune clonal selection principle and is widely used in pattern recognition, control, optimization, multimodal, and combination problem.Clonal selection: Cortes and Coello [22] introduced a new multiobjective optimization approach based on the clonal selection principle. They indicate that the use of an artificial immune system for multiobjective optimization is a viable alternative. Huizar et al. [24] used the clonal selection algorithm to generate optimal or nearly optimal solutions for solving combinatorial optimization problems. Meng and Qiuhong [23] proposed a new artificial immune algorithm based on the clonal selection theory and the structure of anti-idiotype (IAAI). IAAI is improved to achieve the evolution of the whole antibody population, and the new algorithm has strong searching capability which makes it reach better performance by performing global search and local search in many directions in the solution space.Monoclonal algorithm: Liu et al. [25] proposed Immune Monoclonal Strategy Algorithm (IMSA) which realizes the global optimal computation as well as the local search. According to antibody-antigen affinity, the algorithm adaptively adjusts the clonal scale of antibody population. Moreover, it shows that IMSA has the strong abilities in having high convergence speed, enhancing the diversity of the population, and avoiding the immature convergence to some degree. However, the algorithm has the problem of weakening local searching ability because of that the local searching mechanism of the algorithm itself is not perfect and the optimization function is complicated.Polyclonal algorithm: ployclonal is the foundation of the specific immune response. Different from the monoclonal strategy which has only one or a few antigenic determinant and epitope, polyclonal performance at the cellular level is the structure of extreme diversity of TCR (T cell antigen receptors) and BCR (B cell antigen receptor). Therefore, it can directly lead to the diversity of antibody network, memory, and specificity. Shen and Yuan [26] proposed a novel polyclone particle swarm optimization algorithm (PCPSOA) for mobile robot path planning. PCPSOA is characterized by strong searching ability and quick convergence speed. The simulation results show that the path planning based on PCPSOA is feasible and effective.Immunity polyclonal algorithm is used to solve the immature convergence problem of artificial immune network and the local minima problem of artificial potential field method. The proposed polyclonal based artificial immune algorithm increases diversity of antibodies which tend to the same extreme value in the solution space of artificial immune network using clonal operator, clonal crossover operator, clonal mutation operator, and clonal selection operator.


## 3. The Proposed Path Planning Algorithm

### 3.1. Graphical Representation of the Proposed Algorithm

In this paper, polyclonal-based artificial immune network (PC-AIN) is used for mobile robot path planning in unknown static environment. Artificial immune network (AIN) is used to compute concentrations of antibodies. Immunity polyclonal algorithm (IPCA) is used to solve the problems of immature convergence and local minima. The graphical representation of the proposed path planning system is depicted in Figure1.Figure 1
The graphic representation of the proposed path planning system. Antigen represents the local environment surrounding the robot. Antigen’s epitope represents a data set detected by sensors including the azimuth of the goal, the distance between obstacles and sensor, and the azimuth of sensor. Antibody represents robot’s steering direction. The interaction between antibodies is achieved by idiotope and paratope. Only the antibody with highest concentration will be selected to act on robot.


### 3.2. Antigen and Antibody Representation

Artificial immune network algorithm transforms the actual state of robot and defines antibodies and antigens from the perspective of information processing. Antigen's epitope is a data set detected by sensors and provides the information about the relationship among the current positions of robot, obstacles, and goal. An antigen may have several different epitopes, which means that an antigen can be recognized by a number of different antibodies. However, an antibody can bind only one antigen’s epitope. In this paper, a paratope with a built-in robot’s steering direction is regarded as antibody. These antibodies/steering directions are induced by recognition of the available antigens/detected information. It should be noted that only the antibody with highest concentration will be selected to act on robot according to the immune network hypothesis. Antigen represents the local environment surrounding the robot, and its epitope is a data set containing the azimuth of the goalθg, the distance between obstacles and the jth sensor dj, and the azimuth of sensor θSj:
(1)Agj≡{θg,dj,θSj},j=1,2,…,NS,
where NS is the number of sensors equally spaced around the base plate of the mobile robot, dmin≤dj≤dmax. Parameters dmin and dmax represent the nearest and longest distance measured by the range sensors, respectively. θSj=2π(j-1)/NS,  j=1,2,…,NS.In addition, the relationship between antibody and steering direction is illustrated as follows:(2)Abi≡θi=2πNAb(i-1),i=1,2,…,NAb,
where NAb is the number of antibodies and θi is the steering angle between the moving path and the head orientation of the mobile robot. Note that 0≤θi≤2π. There is no necessary relationship between NAb and NS since they depend on the hardware of mobile robot. Nevertheless, simulation results show that better performance could be derived if NS equal to or larger than NAb. In this paper, NS=NAb=8.


### 3.3. Artificial Immune Network

Immune response forms a dynamic balance network through the interaction between antibody and antigen and the interaction between antibodies. When antigens invade the body, it achieves a new balance through the regulation of the immune system. Even when no antigen intrusion, it maintains the appropriate intensity through mutual stimulation and suppression between antibodies and it conforms to the idiotypic network hypothesis. In this paper, this reaction mechanism is adopted. The dynamic equation proposed by Farmer et al. is employed to calculate the variation of antibody concentration as shown in the following equations:(3)dAi(t)dt=(∑j=1NAb‍mijstaj(t)-∑k=1NAb‍mkisuak(t)+mi-ki)×ai(t),(4)ai(t)=11+exp(0.5-Ai(t)),
where i,j,k=0,1,…,NAb are the subscripts to distinguish the antibody types and NAb is the number of antibodies. ai is the concentration of the ith antibody and dAi/dt is the rate of change of concentration. mijst, mkisu indicate the stimulative and suppressive affinity between the ith and the jth, kth antibodies, respectively. mi denotes the affinity between antigen and the ith antibody, and ki represents the natural death coefficient. Equation (3) is composed of four terms. The first term shows the stimulative interaction between antibodies, while the second term depicts the suppressive interaction between antibodies. The third term is the stimulus from the antigen, and the final term is the natural extinction term, which indicates the dissipation tendency in the absence of any interaction. Equation (4) is a squashing function to ensure the stability of the concentration [16].The affinity between antigen and theith antibody mi is computed using artificial potential field method. In the proposed immune network, the resultant force of artificial potential field is defined as mi, and the calculating process of mi is illustrated as follows.


#### 3.3.1. Attractive Force of theith Antibody/Steering Direction

Consider(5)Fgoali=1.0+cos(θi-θg)2.0,i=1,2,…,NAb,
where 0≤Fgoali≤1. Obviously, the attractive force is at its maximal level (Fgoali=1) when the mobile robot goes straightforward to the goal (θi-θg=0). On the contrary, it is minimized (Fgoali=0) when the robot’s steering direction is the opposite of the goal (θi-θg=π).


#### 3.3.2. Repulsive Force of theith Antibody/Steering Direction

Consider(6)Fobsi=∑j=1NS‍αijd-j,
where αij=exp(-NS×(1-δij)) and δij=(1+cos(θi-θSj))/2. Parameter αij indicates the weighting ratio for the jth sensor to steering angle θi, while d¯j represents the normalized distance between the jth sensor and obstacles. Coefficient δij expresses influence and importance of each sensor at different locations. d¯j is fuzzified using the fuzzy set definitions. Three fuzzy if-then rules are defined to compute d¯j:
(7)ifdjiss,theny=L1,ifdjism,theny=L2,ifdjisd,theny=L3,
where L1, L2, and L3 are defined as 0.25,0.5,and1.0, respectively. The input variable of each rule is the detected distance dj of the jth sensor. s,m, and d represent safe, medium, and danger, respectively. The membership function of s,m, and d are defined as (8), (9), and (10), respectively
(8)μs={0,dj≤dm,dj-dmdmax-dm,dm<dj≤dmax,1,dj>dmax,(9)μm={0,dj≤dmin,dj-dmindm-dmin,dmin<dj≤dm,dmax-djdmax-dm,dm<dj≤dmax,0,dj>dmax,(10)μd={1,dj≤dmin,dm-djdm-dmin,dmin<dj≤dm,0,dj>dm.The normalized distance betweenjth sensor and obstacles dj¯ is computed as (11)
(11)dj¯=μs×L1+μm×L2+μd×L3μs+μm+μd.


#### 3.3.3. Resultant Force of theith Antibody/Steering Direction

Consider(12)mi=ω1Fgoali+ω2Fobsi,i=1,2,…,NAb,
where parameters ω1,ω2 indicate the weighting ratio between attractive and repulsive forces, 0≤ω1,ω2≤1, ω1+ω2=1.The stimulative and suppressive affinity between antibodies are combined and the stimulative-suppressive affinity between antibodiesmilss is defined as (13)
(13)milss=milst-mlisu=cos(θi-θl)=cos(Δθil),s(θi-θl)=cos(Δ)i,l=1,2,…,NAb.Obviously, stimulative-suppressive effect is positive (milss>0) if 0<Δθil<π/2, or 3π/2<Δθil<2π. On the contrary, stimulative-suppressive effect is negative (milss<0) if π/2<Δθil<3π/2. In addition, there is no any net effect between orthogonal antibodies (i.e., Δθil=π/2, or Δθil=3π/2).Equations (3) and (4) are discretized:
(14)Ai(n+1)=Ai(n)+(∑j=1NAb‍mijstaj(n)-∑k=1NAb‍mkisuak(n)+mi-ki)×ai(n),ai(n+1)=11+exp(0.5-Ai(n+1)),
where n is the initial time at every step and n+1 is the current time at every step.


### 3.4. Immunity Polyclonal Algorithm

Artificial immune network exists as a problem of immature convergence which some or all individuals in the solution space tend to the same extreme value and robot will stop moving or move with wrong direction. From the view of biology, the reason of immature convergence problem is that the antibody concentration increases exponentially and some or all individuals tend to the same extreme value, so the diversity of antibody is decreased, and one antigen’s epitope can be recognized by several antibodies at the same time. The phenomenon does not conform with the biological immune theory which one epitope can only be identified by one antibody. Specific to the process of mobile robot path planning, the normalized distance between sensor and obstacles reaches the maximum value1 when the distance between robot and obstacles is less than the risk threshold, and concentrations of some or all antibodies tend to the same extreme value. Robot selects the antibody with highest concentration to act on at every step, but at the above situation, the moving probabilities toward certain directions are equal, and the robot has multiple optimal solutions at this point. So the robot will act wrongly.Artificial potential field method is applied to compute parameter in artificial immune network, so artificial immune network exists as a problem of local minima. Attractive force and repulsive force have effect on robot, and there are some points which balance the attractive force and repulsive force, so the resultant force is zero at these points. It is the cause of local minima. More densely obstacles and more repulsive forces act on robot, so greater danger of local minima. When the robot traps in local minima, robot will shock or stop at this point, and this phenomenon is known as “dead lock”.When the problems of immature convergence and local minima appear in the process of mobile robot path planning, robot periodically wanders around at the point and cannot reach the goal successfully. In this paper, immunity polyclonal algorithm is utilized to solve the above two problems.The essence of immunity polyclonal algorithm is creating a new subpopulation based on the value of affinity around the candidate solution in the generation of evolution and expanding the searching scope. Meanwhile, immunity polyclonal algorithm implements the exchange of information between populations and increases the diversity of antibodies. In other words, polyclonal transforms the problem from a low dimensional space into a high dimensional space and then maps the result into the low dimensional space.The antigen of immunity polyclonal algorithm corresponds to the objective function of optimal problem and various constraints, the antibody corresponds to the optimal solution and the affinity between antigen, and antibody corresponds to the matching degree of objective function and homographic solution. In this paper, the antigen corresponds to the local environmental information, the antibody corresponds to the individuals tending to the same extreme value in solution space of artificial immune network, and the affinity between antigen and antibody corresponds tomi of artificial immune network.Assuming the initial antibody populationA={c1,c2,…,cn}, n is the size of initial antibody population, and ci is the concentration of ith antibody which is one of individuals tending to the same extreme value in the solution space of artificial immune network. Polyclonal operator divided the point ci∈A into qi same points ci′∈A′, and then getting the new antibody population through clonal operator, clonal crossover operator, clonal mutation operator, and clonal selection operator. Polyclonal operator can be described as follows.


#### 3.4.1. Clonal Operator

Defined as(15)Θ(A)=[Θ(c1),Θ(c2),…,Θ(cn)]T,
where Θ(ci)=Ii×ci, i=1,2,…,n and Ii is a qi-dimensional vector.Generally(16)qi=Int(N×m(ci)∑j=1nm(cj)),i=1,2,…,n.N>n is a given value related to the clonal scale and Int(x) rounds the argument x toward the least integer greater than x. m(ci) is the affinity between antigen and antibody, qi is used to reflect the clonal scale of antibody. The previous equation implies that every antibody will be viewed locally and has its clonal scale different from the other ones. After cloning, the initial antibody population becomes the following population:
(17)B={A,A1′,A2′,…,An′},
where
(18)Ai′={ci1,ci2,…,ciqi-1},
where cij=ci,j=1,2,…,qi-1.The range of clonal scale is [10,100]. The bigger the clonal scale, the more time complexity of the algorithm. In this paper, the affinity between antigen and every antibody is same, so every antibody’s clonal scale is same. Clonal scale of every antibody is Nc=N×B=40, B is clonal coefficient, and 0<B<1, B=0.125, N=320.


#### 3.4.2. Clonal Crossover Operator

Crossover selects two individuals from the population by the larger probability and exchanges one or some components of two individuals. Crossover guarantees the search of solution space will not trap into immature convergence because of high fitness individuals and makes the search stronger.Clonal crossover operator maintains the information of initial population and does not act onA∈A′. The following crossover method is adopted. Considering two antibodies ci={x1,x2,…,xNc} and cj={y1,y2,…,yNc}, the s1th component is selected as crossover point; namely,
(19)TcC(ci,cj)={x1,…,xs1,y1,…,ys2},s1+s2=Nc,ci∈A′,cj∈A′.The range of crossover probability values are [0.5,0.99]. In this paper, the crossover probability is Pc=0.8.


#### 3.4.3. Clonal Mutation Operator

Clonal mutation operator changes some genes in the group list of population, and the exchange is to put negation of some genetic value, that is,0→1 or 1→0. The specific step is described as follows: the clonal mutation probability Pm and every gene of the path produce a random number R∈[0,1], if Pm≥R, the gene produces mutation (0→1 or 1→0).The range of mutation probability values are [0.01,0.05]. In this paper, the mutation probability is Pm=0.03.


#### 3.4.4. Clonal Selection Operator

For alli=1,2,…,n, if there is a mutated antibody b such that m(b)=max{m(ci)} satisfying the following
(20)m(ci)<m(b),ci∈A′,
then b replaces ci in the antibody population.In this paper, immunity polyclonal algorithm increases the diversity of antibodies which tend to the same extreme value and selects the antibody with highest concentration as the final antibody/steering direction. Thus, it overcomes the problems of immature convergence and local minima.


## 3.1. Graphical Representation of the Proposed Algorithm

In this paper, polyclonal-based artificial immune network (PC-AIN) is used for mobile robot path planning in unknown static environment. Artificial immune network (AIN) is used to compute concentrations of antibodies. Immunity polyclonal algorithm (IPCA) is used to solve the problems of immature convergence and local minima. The graphical representation of the proposed path planning system is depicted in Figure1.Figure 1
The graphic representation of the proposed path planning system. Antigen represents the local environment surrounding the robot. Antigen’s epitope represents a data set detected by sensors including the azimuth of the goal, the distance between obstacles and sensor, and the azimuth of sensor. Antibody represents robot’s steering direction. The interaction between antibodies is achieved by idiotope and paratope. Only the antibody with highest concentration will be selected to act on robot.


## 3.2. Antigen and Antibody Representation

Artificial immune network algorithm transforms the actual state of robot and defines antibodies and antigens from the perspective of information processing. Antigen's epitope is a data set detected by sensors and provides the information about the relationship among the current positions of robot, obstacles, and goal. An antigen may have several different epitopes, which means that an antigen can be recognized by a number of different antibodies. However, an antibody can bind only one antigen’s epitope. In this paper, a paratope with a built-in robot’s steering direction is regarded as antibody. These antibodies/steering directions are induced by recognition of the available antigens/detected information. It should be noted that only the antibody with highest concentration will be selected to act on robot according to the immune network hypothesis. Antigen represents the local environment surrounding the robot, and its epitope is a data set containing the azimuth of the goalθg, the distance between obstacles and the jth sensor dj, and the azimuth of sensor θSj:
(1)Agj≡{θg,dj,θSj},j=1,2,…,NS,
where NS is the number of sensors equally spaced around the base plate of the mobile robot, dmin≤dj≤dmax. Parameters dmin and dmax represent the nearest and longest distance measured by the range sensors, respectively. θSj=2π(j-1)/NS,  j=1,2,…,NS.In addition, the relationship between antibody and steering direction is illustrated as follows:(2)Abi≡θi=2πNAb(i-1),i=1,2,…,NAb,
where NAb is the number of antibodies and θi is the steering angle between the moving path and the head orientation of the mobile robot. Note that 0≤θi≤2π. There is no necessary relationship between NAb and NS since they depend on the hardware of mobile robot. Nevertheless, simulation results show that better performance could be derived if NS equal to or larger than NAb. In this paper, NS=NAb=8.


## 3.3. Artificial Immune Network

Immune response forms a dynamic balance network through the interaction between antibody and antigen and the interaction between antibodies. When antigens invade the body, it achieves a new balance through the regulation of the immune system. Even when no antigen intrusion, it maintains the appropriate intensity through mutual stimulation and suppression between antibodies and it conforms to the idiotypic network hypothesis. In this paper, this reaction mechanism is adopted. The dynamic equation proposed by Farmer et al. is employed to calculate the variation of antibody concentration as shown in the following equations:(3)dAi(t)dt=(∑j=1NAb‍mijstaj(t)-∑k=1NAb‍mkisuak(t)+mi-ki)×ai(t),(4)ai(t)=11+exp(0.5-Ai(t)),
where i,j,k=0,1,…,NAb are the subscripts to distinguish the antibody types and NAb is the number of antibodies. ai is the concentration of the ith antibody and dAi/dt is the rate of change of concentration. mijst, mkisu indicate the stimulative and suppressive affinity between the ith and the jth, kth antibodies, respectively. mi denotes the affinity between antigen and the ith antibody, and ki represents the natural death coefficient. Equation (3) is composed of four terms. The first term shows the stimulative interaction between antibodies, while the second term depicts the suppressive interaction between antibodies. The third term is the stimulus from the antigen, and the final term is the natural extinction term, which indicates the dissipation tendency in the absence of any interaction. Equation (4) is a squashing function to ensure the stability of the concentration [16].The affinity between antigen and theith antibody mi is computed using artificial potential field method. In the proposed immune network, the resultant force of artificial potential field is defined as mi, and the calculating process of mi is illustrated as follows.


### 3.3.1. Attractive Force of theith Antibody/Steering Direction

Consider(5)Fgoali=1.0+cos(θi-θg)2.0,i=1,2,…,NAb,
where 0≤Fgoali≤1. Obviously, the attractive force is at its maximal level (Fgoali=1) when the mobile robot goes straightforward to the goal (θi-θg=0). On the contrary, it is minimized (Fgoali=0) when the robot’s steering direction is the opposite of the goal (θi-θg=π).


### 3.3.2. Repulsive Force of theith Antibody/Steering Direction

Consider(6)Fobsi=∑j=1NS‍αijd-j,
where αij=exp(-NS×(1-δij)) and δij=(1+cos(θi-θSj))/2. Parameter αij indicates the weighting ratio for the jth sensor to steering angle θi, while d¯j represents the normalized distance between the jth sensor and obstacles. Coefficient δij expresses influence and importance of each sensor at different locations. d¯j is fuzzified using the fuzzy set definitions. Three fuzzy if-then rules are defined to compute d¯j:
(7)ifdjiss,theny=L1,ifdjism,theny=L2,ifdjisd,theny=L3,
where L1, L2, and L3 are defined as 0.25,0.5,and1.0, respectively. The input variable of each rule is the detected distance dj of the jth sensor. s,m, and d represent safe, medium, and danger, respectively. The membership function of s,m, and d are defined as (8), (9), and (10), respectively
(8)μs={0,dj≤dm,dj-dmdmax-dm,dm<dj≤dmax,1,dj>dmax,(9)μm={0,dj≤dmin,dj-dmindm-dmin,dmin<dj≤dm,dmax-djdmax-dm,dm<dj≤dmax,0,dj>dmax,(10)μd={1,dj≤dmin,dm-djdm-dmin,dmin<dj≤dm,0,dj>dm.The normalized distance betweenjth sensor and obstacles dj¯ is computed as (11)
(11)dj¯=μs×L1+μm×L2+μd×L3μs+μm+μd.


### 3.3.3. Resultant Force of theith Antibody/Steering Direction

Consider(12)mi=ω1Fgoali+ω2Fobsi,i=1,2,…,NAb,
where parameters ω1,ω2 indicate the weighting ratio between attractive and repulsive forces, 0≤ω1,ω2≤1, ω1+ω2=1.The stimulative and suppressive affinity between antibodies are combined and the stimulative-suppressive affinity between antibodiesmilss is defined as (13)
(13)milss=milst-mlisu=cos(θi-θl)=cos(Δθil),s(θi-θl)=cos(Δ)i,l=1,2,…,NAb.Obviously, stimulative-suppressive effect is positive (milss>0) if 0<Δθil<π/2, or 3π/2<Δθil<2π. On the contrary, stimulative-suppressive effect is negative (milss<0) if π/2<Δθil<3π/2. In addition, there is no any net effect between orthogonal antibodies (i.e., Δθil=π/2, or Δθil=3π/2).Equations (3) and (4) are discretized:
(14)Ai(n+1)=Ai(n)+(∑j=1NAb‍mijstaj(n)-∑k=1NAb‍mkisuak(n)+mi-ki)×ai(n),ai(n+1)=11+exp(0.5-Ai(n+1)),
where n is the initial time at every step and n+1 is the current time at every step.


## 3.3.1. Attractive Force of theith Antibody/Steering Direction

Consider(5)Fgoali=1.0+cos(θi-θg)2.0,i=1,2,…,NAb,
where 0≤Fgoali≤1. Obviously, the attractive force is at its maximal level (Fgoali=1) when the mobile robot goes straightforward to the goal (θi-θg=0). On the contrary, it is minimized (Fgoali=0) when the robot’s steering direction is the opposite of the goal (θi-θg=π).


## 3.3.2. Repulsive Force of theith Antibody/Steering Direction

Consider(6)Fobsi=∑j=1NS‍αijd-j,
where αij=exp(-NS×(1-δij)) and δij=(1+cos(θi-θSj))/2. Parameter αij indicates the weighting ratio for the jth sensor to steering angle θi, while d¯j represents the normalized distance between the jth sensor and obstacles. Coefficient δij expresses influence and importance of each sensor at different locations. d¯j is fuzzified using the fuzzy set definitions. Three fuzzy if-then rules are defined to compute d¯j:
(7)ifdjiss,theny=L1,ifdjism,theny=L2,ifdjisd,theny=L3,
where L1, L2, and L3 are defined as 0.25,0.5,and1.0, respectively. The input variable of each rule is the detected distance dj of the jth sensor. s,m, and d represent safe, medium, and danger, respectively. The membership function of s,m, and d are defined as (8), (9), and (10), respectively
(8)μs={0,dj≤dm,dj-dmdmax-dm,dm<dj≤dmax,1,dj>dmax,(9)μm={0,dj≤dmin,dj-dmindm-dmin,dmin<dj≤dm,dmax-djdmax-dm,dm<dj≤dmax,0,dj>dmax,(10)μd={1,dj≤dmin,dm-djdm-dmin,dmin<dj≤dm,0,dj>dm.The normalized distance betweenjth sensor and obstacles dj¯ is computed as (11)
(11)dj¯=μs×L1+μm×L2+μd×L3μs+μm+μd.


## 3.3.3. Resultant Force of theith Antibody/Steering Direction

Consider(12)mi=ω1Fgoali+ω2Fobsi,i=1,2,…,NAb,
where parameters ω1,ω2 indicate the weighting ratio between attractive and repulsive forces, 0≤ω1,ω2≤1, ω1+ω2=1.The stimulative and suppressive affinity between antibodies are combined and the stimulative-suppressive affinity between antibodiesmilss is defined as (13)
(13)milss=milst-mlisu=cos(θi-θl)=cos(Δθil),s(θi-θl)=cos(Δ)i,l=1,2,…,NAb.Obviously, stimulative-suppressive effect is positive (milss>0) if 0<Δθil<π/2, or 3π/2<Δθil<2π. On the contrary, stimulative-suppressive effect is negative (milss<0) if π/2<Δθil<3π/2. In addition, there is no any net effect between orthogonal antibodies (i.e., Δθil=π/2, or Δθil=3π/2).Equations (3) and (4) are discretized:
(14)Ai(n+1)=Ai(n)+(∑j=1NAb‍mijstaj(n)-∑k=1NAb‍mkisuak(n)+mi-ki)×ai(n),ai(n+1)=11+exp(0.5-Ai(n+1)),
where n is the initial time at every step and n+1 is the current time at every step.


## 3.4. Immunity Polyclonal Algorithm

Artificial immune network exists as a problem of immature convergence which some or all individuals in the solution space tend to the same extreme value and robot will stop moving or move with wrong direction. From the view of biology, the reason of immature convergence problem is that the antibody concentration increases exponentially and some or all individuals tend to the same extreme value, so the diversity of antibody is decreased, and one antigen’s epitope can be recognized by several antibodies at the same time. The phenomenon does not conform with the biological immune theory which one epitope can only be identified by one antibody. Specific to the process of mobile robot path planning, the normalized distance between sensor and obstacles reaches the maximum value1 when the distance between robot and obstacles is less than the risk threshold, and concentrations of some or all antibodies tend to the same extreme value. Robot selects the antibody with highest concentration to act on at every step, but at the above situation, the moving probabilities toward certain directions are equal, and the robot has multiple optimal solutions at this point. So the robot will act wrongly.Artificial potential field method is applied to compute parameter in artificial immune network, so artificial immune network exists as a problem of local minima. Attractive force and repulsive force have effect on robot, and there are some points which balance the attractive force and repulsive force, so the resultant force is zero at these points. It is the cause of local minima. More densely obstacles and more repulsive forces act on robot, so greater danger of local minima. When the robot traps in local minima, robot will shock or stop at this point, and this phenomenon is known as “dead lock”.When the problems of immature convergence and local minima appear in the process of mobile robot path planning, robot periodically wanders around at the point and cannot reach the goal successfully. In this paper, immunity polyclonal algorithm is utilized to solve the above two problems.The essence of immunity polyclonal algorithm is creating a new subpopulation based on the value of affinity around the candidate solution in the generation of evolution and expanding the searching scope. Meanwhile, immunity polyclonal algorithm implements the exchange of information between populations and increases the diversity of antibodies. In other words, polyclonal transforms the problem from a low dimensional space into a high dimensional space and then maps the result into the low dimensional space.The antigen of immunity polyclonal algorithm corresponds to the objective function of optimal problem and various constraints, the antibody corresponds to the optimal solution and the affinity between antigen, and antibody corresponds to the matching degree of objective function and homographic solution. In this paper, the antigen corresponds to the local environmental information, the antibody corresponds to the individuals tending to the same extreme value in solution space of artificial immune network, and the affinity between antigen and antibody corresponds tomi of artificial immune network.Assuming the initial antibody populationA={c1,c2,…,cn}, n is the size of initial antibody population, and ci is the concentration of ith antibody which is one of individuals tending to the same extreme value in the solution space of artificial immune network. Polyclonal operator divided the point ci∈A into qi same points ci′∈A′, and then getting the new antibody population through clonal operator, clonal crossover operator, clonal mutation operator, and clonal selection operator. Polyclonal operator can be described as follows.


### 3.4.1. Clonal Operator

Defined as(15)Θ(A)=[Θ(c1),Θ(c2),…,Θ(cn)]T,
where Θ(ci)=Ii×ci, i=1,2,…,n and Ii is a qi-dimensional vector.Generally(16)qi=Int(N×m(ci)∑j=1nm(cj)),i=1,2,…,n.N>n is a given value related to the clonal scale and Int(x) rounds the argument x toward the least integer greater than x. m(ci) is the affinity between antigen and antibody, qi is used to reflect the clonal scale of antibody. The previous equation implies that every antibody will be viewed locally and has its clonal scale different from the other ones. After cloning, the initial antibody population becomes the following population:
(17)B={A,A1′,A2′,…,An′},
where
(18)Ai′={ci1,ci2,…,ciqi-1},
where cij=ci,j=1,2,…,qi-1.The range of clonal scale is [10,100]. The bigger the clonal scale, the more time complexity of the algorithm. In this paper, the affinity between antigen and every antibody is same, so every antibody’s clonal scale is same. Clonal scale of every antibody is Nc=N×B=40, B is clonal coefficient, and 0<B<1, B=0.125, N=320.


### 3.4.2. Clonal Crossover Operator

Crossover selects two individuals from the population by the larger probability and exchanges one or some components of two individuals. Crossover guarantees the search of solution space will not trap into immature convergence because of high fitness individuals and makes the search stronger.Clonal crossover operator maintains the information of initial population and does not act onA∈A′. The following crossover method is adopted. Considering two antibodies ci={x1,x2,…,xNc} and cj={y1,y2,…,yNc}, the s1th component is selected as crossover point; namely,
(19)TcC(ci,cj)={x1,…,xs1,y1,…,ys2},s1+s2=Nc,ci∈A′,cj∈A′.The range of crossover probability values are [0.5,0.99]. In this paper, the crossover probability is Pc=0.8.


### 3.4.3. Clonal Mutation Operator

Clonal mutation operator changes some genes in the group list of population, and the exchange is to put negation of some genetic value, that is,0→1 or 1→0. The specific step is described as follows: the clonal mutation probability Pm and every gene of the path produce a random number R∈[0,1], if Pm≥R, the gene produces mutation (0→1 or 1→0).The range of mutation probability values are [0.01,0.05]. In this paper, the mutation probability is Pm=0.03.


### 3.4.4. Clonal Selection Operator

For alli=1,2,…,n, if there is a mutated antibody b such that m(b)=max{m(ci)} satisfying the following
(20)m(ci)<m(b),ci∈A′,
then b replaces ci in the antibody population.In this paper, immunity polyclonal algorithm increases the diversity of antibodies which tend to the same extreme value and selects the antibody with highest concentration as the final antibody/steering direction. Thus, it overcomes the problems of immature convergence and local minima.


## 3.4.1. Clonal Operator

Defined as(15)Θ(A)=[Θ(c1),Θ(c2),…,Θ(cn)]T,
where Θ(ci)=Ii×ci, i=1,2,…,n and Ii is a qi-dimensional vector.Generally(16)qi=Int(N×m(ci)∑j=1nm(cj)),i=1,2,…,n.N>n is a given value related to the clonal scale and Int(x) rounds the argument x toward the least integer greater than x. m(ci) is the affinity between antigen and antibody, qi is used to reflect the clonal scale of antibody. The previous equation implies that every antibody will be viewed locally and has its clonal scale different from the other ones. After cloning, the initial antibody population becomes the following population:
(17)B={A,A1′,A2′,…,An′},
where
(18)Ai′={ci1,ci2,…,ciqi-1},
where cij=ci,j=1,2,…,qi-1.The range of clonal scale is [10,100]. The bigger the clonal scale, the more time complexity of the algorithm. In this paper, the affinity between antigen and every antibody is same, so every antibody’s clonal scale is same. Clonal scale of every antibody is Nc=N×B=40, B is clonal coefficient, and 0<B<1, B=0.125, N=320.


## 3.4.2. Clonal Crossover Operator

Crossover selects two individuals from the population by the larger probability and exchanges one or some components of two individuals. Crossover guarantees the search of solution space will not trap into immature convergence because of high fitness individuals and makes the search stronger.Clonal crossover operator maintains the information of initial population and does not act onA∈A′. The following crossover method is adopted. Considering two antibodies ci={x1,x2,…,xNc} and cj={y1,y2,…,yNc}, the s1th component is selected as crossover point; namely,
(19)TcC(ci,cj)={x1,…,xs1,y1,…,ys2},s1+s2=Nc,ci∈A′,cj∈A′.The range of crossover probability values are [0.5,0.99]. In this paper, the crossover probability is Pc=0.8.


## 3.4.3. Clonal Mutation Operator

Clonal mutation operator changes some genes in the group list of population, and the exchange is to put negation of some genetic value, that is,0→1 or 1→0. The specific step is described as follows: the clonal mutation probability Pm and every gene of the path produce a random number R∈[0,1], if Pm≥R, the gene produces mutation (0→1 or 1→0).The range of mutation probability values are [0.01,0.05]. In this paper, the mutation probability is Pm=0.03.


## 3.4.4. Clonal Selection Operator

For alli=1,2,…,n, if there is a mutated antibody b such that m(b)=max{m(ci)} satisfying the following
(20)m(ci)<m(b),ci∈A′,
then b replaces ci in the antibody population.In this paper, immunity polyclonal algorithm increases the diversity of antibodies which tend to the same extreme value and selects the antibody with highest concentration as the final antibody/steering direction. Thus, it overcomes the problems of immature convergence and local minima.


## 4. Simulation and Discussions

Some experiments are carried out for validating the proposed algorithm using MATLAB 2011 (a) GUI. The initial position of robot, goal, and obstacles get randomly in experimental environment. Assume robot has eight uniformly distributed distance sensors (NS= 8) and eight moving directions (NAb= 8) including forward, left, right, back, forward left, forward right, back left, and back right. Experimental environment is 20×20m, obstacles are expressed with black square and the size of obstacles is 1×1m.


### 4.1. PC-AIN Comparison with AIN

#### 4.1.1. PC-AIN Improves Immature Convergence Problem of AIN

Artificial immune network (AIN) for mobile robot path planning exists as an immature convergence problem because some or all individuals in the solution space tend to the same extreme value. In this case, the robot will stop moving or move with wrong direction.Experimental environment sets are as follows: the initial position of robot (9,8), the goal position (8,16), and the velocity of robot is0.1m/s. In Figures 2(a) and 2(b), artificial immune network is utilized for mobile robot path planning. There exists a condition that some or all individuals in the solution space of AIN tend to the same extreme value as shown in Figure 2(a). At this point robot randomly selects one of the directions to move because the moving probabilities toward several directions are equal. If this condition cannot improved effectively, robot will collide with obstacle as shown in Figure 2(b) and path planning fails at this time. The situation that some or all individuals in solution space tend to the same extreme value appeared, and robot’s path is shown in Figure 2(b) expressed by black circle, and the selected antibody at every step when some or all concentrations in solution space tend to the same extreme value is shown in Figure 2(d) expressed by red “*”.Mobile robot path planning with AIN and PC-AIN.
(a)
Some or all individuals tend to the same extreme value
(b)
Robot moves wrongly with AIN
(c)
PC-AIN for path planning
(d)
The selected antibody of AIN and PC-AIN at every stepImmunity polyclonal algorithm increases the diversity of antibodies which tend to the same extreme value in the solution space of AIN through clonal operator, clonal crossover operator, clonal mutation operator, and clonal selection operator. In polyclonal-based artificial immune network (PC-AIN) for mobile robot path planning, robot will move with the optimal direction at every step and get optimal path finally. Figure2(c) shows polyclonal-based artificial immune network algorithm for mobile robot path planning under the experimental environment in Figure 2(a). The black circle represents the path when some or all individuals tend to the same extreme value in solution space of AIN, and the selected antibody at every step during this path is shown in Figure 2(d) expressed by black “*”. From Figure 2(c), it can be seen that polyclonal-based artificial immune network (PC-AIN) solves the problem of immature convergence with increasing diversity of antibodies, and robot successfully reaches the goal in this condition.Based on Figure2, the selected antibody when some or all individuals tend to the same extreme value in solution space of AIN and PC-AIN is shown in Figure 2(d). It can be seen that artificial immune network (AIN) cannot effectively select the antibody with highest concentration, and robot traps into immature convergence problem when some or all individuals tend to the same extreme value in concentration solution space, while polyclonal-based artificial immune network (PC-AIN) successfully selects the antibody/steering direction with highest concentration and solves the problem of immature convergence with increasing the diversity of antibodies, and robot successfully reaches the goal.


#### 4.1.2. Performance Comparison of AIN and PC-AIN

Experimental environment sets are as follows: the initial position of robot (5, 4), the goal position (10, 16), the number of obstacles are 5, the obstacles position (9, 10), (7, 6), (5, 8), (8, 13), and (6, 12), respectively. The velocity is0.1m/s. AIN and PC-AIN for mobile robot path planning is in the above environment. Table 1 is the results of performance comparison for mobile robot path planning between AIN and PC-AIN. The performance involves steps of path planning and running time from the initial position to the goal. From the property of running time, it can be seen that the running time of PC-AIN is less than the running time of AIN for the same operating environment. Meanwhile, from the comparison of steps, the length of PC-AIN is shorter than the length of AIN. AIN and PC-AIN for mobile robot path planning are shown in Figures 3(a) and 3(b), respectively.Table 1
Performance comparison of AIN and PC-AIN.
Algorithm
PC-AIN
AIN
Running time(s)
6.37
8.13
Steps of path planning
157
227Mobile robot path planning with AIN and PC-AIN.
(a)
Path planning with AIN
(b)
Path planning with PC-AINFrom the above comparison, it can be seen that the polyclonal-based artificial immune network algorithm solves the problem of immature convergence with increasing the diversity of antibodies which tend to the same extreme value, and it has better optimal ability than artificial immune network.


### 4.2. Local Minima

A series of experiments are performed to compare the behavior of the proposed algorithm with reactive immune network [16] in solving the problem of local minima. Experimental environment sets are as follows: robot's initial position (3, 8), goal's initial position (12, 11), and obstacles' position (9, 10), (7, 11), (5, 8), and (12, 8). The velocity is 0.1m/s and t=1s.


#### 4.2.1. Reactive Immune Network

Virtual target method is used to solve local minima problem in reactive immune network (RIN). Robot moves to the goal under the interaction from virtual target, original goal, and obstacles. Revoking the virtual target until the robot is out of the local minima problem and then the robot moves to the original goal under the interaction from original goal and obstacles. When robot meets local minima again, it creates virtual target until reaching the goal.In the above experimental environment, reactive immune network (RIN) is utilized for mobile robot path planning and the simulation result is shown in Figure4(a).Mobile robot path planning with RIN and PC-AIN.
(a)
Path planning with RIN
(b)
Path planning with PC-AIN


#### 4.2.2. Polyclonal-Based Artificial Immune Network

Polyclonal-based artificial immune network effectively solves the problem of local minima caused by artificial potential field during the structure of parameter in artificial immune network through ployclonal operator. Under the above environment, PC-AIN solves the problem of local minima, and the path planning is shown in Figure4(b).Figure5 shows the comparison of steps from the initial position to the goal with reactive immune network and polyclonal-based artificial immune network. Figure 5 shows that path length of PC-AIN is less than the path length of RIN for mobile robot path planning, when the robot traps in local minima problem under the same experimental environment.Figure 5
Path planning comparison of RIN and PC-AIN.


### 4.3. Robot’s Moving Velocity Impact on the Convergence Rate

Robot’s experimental environment is the same as Figure3, where t=1s. When the robot moves at different velocity, the convergence rate of the algorithm is different. When the velocity within a certain range, robot’s convergence rate increases with rising of the velocity. While when the velocity beyond a certain range, robot's convergence rate decreases with increasing of the velocity.As shown in Figure6, the robot moves at different velocities  0.05 m/s,  0.1 m/s,  0.15 m/s,  0.2 m/s,  0.25 m/s, and 0.3 m/s, respectively. With different velocities, robot has different running steps and different convergence rate. The result shows that when the velocity is less than 0.25 m/s, steps used reaching the goal are reduced and convergence rate is increased with rising of velocity. While when the robot’s velocity is 0.25 m/s, steps of robot for path planning are greater than the steps with the speed of 0.2 m/s and 0.15 m/s, and when the robot’s velocity is 0.3 m/s, steps of robot for path planning are greater than the steps with the speed of 0.2 m/s. So, robot’s convergence rate does not increase with rising of velocity.Figure 6
Moving velocity impact on convergence rate.Accordingly, the velocity of robot is not faster or better in mobile robot path planning, and the velocity has certain limitations. Selecting a proper velocity increases the convergence rate for mobile robot path planning.


### 4.4. The Interaction between Antibodies

This experiment is mainly used for validating stimulative affinity and suppressive affinity between antibodies, and expounding the antibody does not exist in the body independently. Figure7 shows the affinity between antibody 1 and other antibodies.Figure 7
Affinity variation of antibody 1 with other antibodies.There are eight antibodies in the experiment; affinity between antibody1 and other antibodies expressed by red “*” in Figure 7. The other antibodies have stimulative affinity impact on antibody 1 if the affinity is greater than zero, and the other antibodies have suppressive affinity impact on antibody 1 if the affinity is less than zero. And the antibody 1 has the maximum stimulative affinity impact on antibody 1. The results correspond to (13). Stimulative-suppressive effect is positive if 0<Δθil<π/2, or 3π/2<Δθil<2π, and stimulative-suppressive effect is negative if π/2<Δθil<3π/2. The interaction between antibodies has a great impact on the immune network.


### 4.5. Analysis of Time Complexity

Polyclonal-based artificial immune network optimizes the path planning and speeds up the convergence rate. Meanwhile, it also solves the problems of immature convergence and local minima, but it's time complexity of each generation increases because of the use of clonal operator, clonal crossover operator, clonal mutation operator, and clonal selection operator.Assuming thatn is the size of antibody population, N>n is a given value related to the clonal scale and Nc is every antibody's clone scale. In this paper, Nc=5n. At every generation of evolution, the worst time complexity of clonal operator is O(nNc), the worst time complexity of clonal crossover operator is O(N), the worst time complexity of clonal mutation operator is O(N), and the worst time complexity of clonal selection operator is O(N+n). So, the worst time complexity of the proposed algorithm in the generation is computed as follows:
(21)O(nNc)+O(N)+O(N)+O(N+n)=O(nNc+3N+n)=O(n·5n+3n·Nc+n)=O(5n2+3n·5n+n)=O(5n2+15n2+n)=O(20n2+n).So, the worst time complexity of the proposed algorithm in the generation isO(n2).


### 4.6. Real-Time Simulation

In this experimental, amigo is used to validate the proposed algorithm, and programming languages used are MATLAB and C++. The system mainly consists of the following parts: host computer, vision system, amigo with an on-board PC, and wireless Ethernet. The camera is used to get the environmental information including obstacles and goal in this system. MATLAB is used to execute the path planning algorithm, and C++ is used to control the motion of robot. The host computer controls the on-board PC through wireless Ethernet.The robot is a differential drive two-wheeled mobile robot. In Cartesian coordinates, the pose, velocity, and angular of differential drive two-wheeled mobile robot can be described as (22) [27]
(22)[xyθ]=[cosθ0sinθ001][vω],
where v is the robot translation velocity and ω is the robot rotation velocity defined as (23)
(23)ω=vR-vLdw,v=vR+vL2.vR and vL are right and left wheels translation velocities of robot, respectively, and dw is the distance between two wheels centers as shown in Figure 8.Figure 8
Differential drive mobile robot.In this paper, polyclonal-based artificial immune network is used to get the pose of robot. At real environment, two wheels velocities are computed through robot pose.AssumingΔSR and ΔSL are the displacement of right and left wheels during Δt, so
(24)Δx=ΔSL+ΔSR2×cosθ,Δy=ΔSL+ΔSR2×sinθ,Δθ=ΔSR-ΔSLb.
Based on (24), the displacement of right and left wheels is computed as follows:
(25)ΔSR=Δxcosθ+dwΔθ2,cosθ≠0,ΔSL=Δxcosθ-dwΔθ2,cosθ≠0
or
(26)ΔSR=Δysinθ+dwΔθ2,sinθ≠0,ΔSL=Δysinθ-dwΔθ2,sinθ≠0.From (25) and (26), left and right wheels velocities are computed.The proposed algorithm is validated at the following scenarios as shown in Figures9 and 10. Figure 9 is a barrier wall, and Figure 10 is a complex environment. Robot reaches the target successfully at the previous scenarios.Figure 9
Barrier wall.Figure 10
Complex environment.


## 4.1. PC-AIN Comparison with AIN

### 4.1.1. PC-AIN Improves Immature Convergence Problem of AIN

Artificial immune network (AIN) for mobile robot path planning exists as an immature convergence problem because some or all individuals in the solution space tend to the same extreme value. In this case, the robot will stop moving or move with wrong direction.Experimental environment sets are as follows: the initial position of robot (9,8), the goal position (8,16), and the velocity of robot is0.1m/s. In Figures 2(a) and 2(b), artificial immune network is utilized for mobile robot path planning. There exists a condition that some or all individuals in the solution space of AIN tend to the same extreme value as shown in Figure 2(a). At this point robot randomly selects one of the directions to move because the moving probabilities toward several directions are equal. If this condition cannot improved effectively, robot will collide with obstacle as shown in Figure 2(b) and path planning fails at this time. The situation that some or all individuals in solution space tend to the same extreme value appeared, and robot’s path is shown in Figure 2(b) expressed by black circle, and the selected antibody at every step when some or all concentrations in solution space tend to the same extreme value is shown in Figure 2(d) expressed by red “*”.Mobile robot path planning with AIN and PC-AIN.
(a)
Some or all individuals tend to the same extreme value
(b)
Robot moves wrongly with AIN
(c)
PC-AIN for path planning
(d)
The selected antibody of AIN and PC-AIN at every stepImmunity polyclonal algorithm increases the diversity of antibodies which tend to the same extreme value in the solution space of AIN through clonal operator, clonal crossover operator, clonal mutation operator, and clonal selection operator. In polyclonal-based artificial immune network (PC-AIN) for mobile robot path planning, robot will move with the optimal direction at every step and get optimal path finally. Figure2(c) shows polyclonal-based artificial immune network algorithm for mobile robot path planning under the experimental environment in Figure 2(a). The black circle represents the path when some or all individuals tend to the same extreme value in solution space of AIN, and the selected antibody at every step during this path is shown in Figure 2(d) expressed by black “*”. From Figure 2(c), it can be seen that polyclonal-based artificial immune network (PC-AIN) solves the problem of immature convergence with increasing diversity of antibodies, and robot successfully reaches the goal in this condition.Based on Figure2, the selected antibody when some or all individuals tend to the same extreme value in solution space of AIN and PC-AIN is shown in Figure 2(d). It can be seen that artificial immune network (AIN) cannot effectively select the antibody with highest concentration, and robot traps into immature convergence problem when some or all individuals tend to the same extreme value in concentration solution space, while polyclonal-based artificial immune network (PC-AIN) successfully selects the antibody/steering direction with highest concentration and solves the problem of immature convergence with increasing the diversity of antibodies, and robot successfully reaches the goal.


### 4.1.2. Performance Comparison of AIN and PC-AIN

Experimental environment sets are as follows: the initial position of robot (5, 4), the goal position (10, 16), the number of obstacles are 5, the obstacles position (9, 10), (7, 6), (5, 8), (8, 13), and (6, 12), respectively. The velocity is0.1m/s. AIN and PC-AIN for mobile robot path planning is in the above environment. Table 1 is the results of performance comparison for mobile robot path planning between AIN and PC-AIN. The performance involves steps of path planning and running time from the initial position to the goal. From the property of running time, it can be seen that the running time of PC-AIN is less than the running time of AIN for the same operating environment. Meanwhile, from the comparison of steps, the length of PC-AIN is shorter than the length of AIN. AIN and PC-AIN for mobile robot path planning are shown in Figures 3(a) and 3(b), respectively.Table 1
Performance comparison of AIN and PC-AIN.
Algorithm
PC-AIN
AIN
Running time(s)
6.37
8.13
Steps of path planning
157
227Mobile robot path planning with AIN and PC-AIN.
(a)
Path planning with AIN
(b)
Path planning with PC-AINFrom the above comparison, it can be seen that the polyclonal-based artificial immune network algorithm solves the problem of immature convergence with increasing the diversity of antibodies which tend to the same extreme value, and it has better optimal ability than artificial immune network.


## 4.1.1. PC-AIN Improves Immature Convergence Problem of AIN

Artificial immune network (AIN) for mobile robot path planning exists as an immature convergence problem because some or all individuals in the solution space tend to the same extreme value. In this case, the robot will stop moving or move with wrong direction.Experimental environment sets are as follows: the initial position of robot (9,8), the goal position (8,16), and the velocity of robot is0.1m/s. In Figures 2(a) and 2(b), artificial immune network is utilized for mobile robot path planning. There exists a condition that some or all individuals in the solution space of AIN tend to the same extreme value as shown in Figure 2(a). At this point robot randomly selects one of the directions to move because the moving probabilities toward several directions are equal. If this condition cannot improved effectively, robot will collide with obstacle as shown in Figure 2(b) and path planning fails at this time. The situation that some or all individuals in solution space tend to the same extreme value appeared, and robot’s path is shown in Figure 2(b) expressed by black circle, and the selected antibody at every step when some or all concentrations in solution space tend to the same extreme value is shown in Figure 2(d) expressed by red “*”.Mobile robot path planning with AIN and PC-AIN.
(a)
Some or all individuals tend to the same extreme value
(b)
Robot moves wrongly with AIN
(c)
PC-AIN for path planning
(d)
The selected antibody of AIN and PC-AIN at every stepImmunity polyclonal algorithm increases the diversity of antibodies which tend to the same extreme value in the solution space of AIN through clonal operator, clonal crossover operator, clonal mutation operator, and clonal selection operator. In polyclonal-based artificial immune network (PC-AIN) for mobile robot path planning, robot will move with the optimal direction at every step and get optimal path finally. Figure2(c) shows polyclonal-based artificial immune network algorithm for mobile robot path planning under the experimental environment in Figure 2(a). The black circle represents the path when some or all individuals tend to the same extreme value in solution space of AIN, and the selected antibody at every step during this path is shown in Figure 2(d) expressed by black “*”. From Figure 2(c), it can be seen that polyclonal-based artificial immune network (PC-AIN) solves the problem of immature convergence with increasing diversity of antibodies, and robot successfully reaches the goal in this condition.Based on Figure2, the selected antibody when some or all individuals tend to the same extreme value in solution space of AIN and PC-AIN is shown in Figure 2(d). It can be seen that artificial immune network (AIN) cannot effectively select the antibody with highest concentration, and robot traps into immature convergence problem when some or all individuals tend to the same extreme value in concentration solution space, while polyclonal-based artificial immune network (PC-AIN) successfully selects the antibody/steering direction with highest concentration and solves the problem of immature convergence with increasing the diversity of antibodies, and robot successfully reaches the goal.


## 4.1.2. Performance Comparison of AIN and PC-AIN

Experimental environment sets are as follows: the initial position of robot (5, 4), the goal position (10, 16), the number of obstacles are 5, the obstacles position (9, 10), (7, 6), (5, 8), (8, 13), and (6, 12), respectively. The velocity is0.1m/s. AIN and PC-AIN for mobile robot path planning is in the above environment. Table 1 is the results of performance comparison for mobile robot path planning between AIN and PC-AIN. The performance involves steps of path planning and running time from the initial position to the goal. From the property of running time, it can be seen that the running time of PC-AIN is less than the running time of AIN for the same operating environment. Meanwhile, from the comparison of steps, the length of PC-AIN is shorter than the length of AIN. AIN and PC-AIN for mobile robot path planning are shown in Figures 3(a) and 3(b), respectively.Table 1
Performance comparison of AIN and PC-AIN.
Algorithm
PC-AIN
AIN
Running time(s)
6.37
8.13
Steps of path planning
157
227Mobile robot path planning with AIN and PC-AIN.
(a)
Path planning with AIN
(b)
Path planning with PC-AINFrom the above comparison, it can be seen that the polyclonal-based artificial immune network algorithm solves the problem of immature convergence with increasing the diversity of antibodies which tend to the same extreme value, and it has better optimal ability than artificial immune network.


## 4.2. Local Minima

A series of experiments are performed to compare the behavior of the proposed algorithm with reactive immune network [16] in solving the problem of local minima. Experimental environment sets are as follows: robot's initial position (3, 8), goal's initial position (12, 11), and obstacles' position (9, 10), (7, 11), (5, 8), and (12, 8). The velocity is 0.1m/s and t=1s.


### 4.2.1. Reactive Immune Network

Virtual target method is used to solve local minima problem in reactive immune network (RIN). Robot moves to the goal under the interaction from virtual target, original goal, and obstacles. Revoking the virtual target until the robot is out of the local minima problem and then the robot moves to the original goal under the interaction from original goal and obstacles. When robot meets local minima again, it creates virtual target until reaching the goal.In the above experimental environment, reactive immune network (RIN) is utilized for mobile robot path planning and the simulation result is shown in Figure4(a).Mobile robot path planning with RIN and PC-AIN.
(a)
Path planning with RIN
(b)
Path planning with PC-AIN


### 4.2.2. Polyclonal-Based Artificial Immune Network

Polyclonal-based artificial immune network effectively solves the problem of local minima caused by artificial potential field during the structure of parameter in artificial immune network through ployclonal operator. Under the above environment, PC-AIN solves the problem of local minima, and the path planning is shown in Figure4(b).Figure5 shows the comparison of steps from the initial position to the goal with reactive immune network and polyclonal-based artificial immune network. Figure 5 shows that path length of PC-AIN is less than the path length of RIN for mobile robot path planning, when the robot traps in local minima problem under the same experimental environment.Figure 5
Path planning comparison of RIN and PC-AIN.


## 4.2.1. Reactive Immune Network

Virtual target method is used to solve local minima problem in reactive immune network (RIN). Robot moves to the goal under the interaction from virtual target, original goal, and obstacles. Revoking the virtual target until the robot is out of the local minima problem and then the robot moves to the original goal under the interaction from original goal and obstacles. When robot meets local minima again, it creates virtual target until reaching the goal.In the above experimental environment, reactive immune network (RIN) is utilized for mobile robot path planning and the simulation result is shown in Figure4(a).Mobile robot path planning with RIN and PC-AIN.
(a)
Path planning with RIN
(b)
Path planning with PC-AIN


## 4.2.2. Polyclonal-Based Artificial Immune Network

Polyclonal-based artificial immune network effectively solves the problem of local minima caused by artificial potential field during the structure of parameter in artificial immune network through ployclonal operator. Under the above environment, PC-AIN solves the problem of local minima, and the path planning is shown in Figure4(b).Figure5 shows the comparison of steps from the initial position to the goal with reactive immune network and polyclonal-based artificial immune network. Figure 5 shows that path length of PC-AIN is less than the path length of RIN for mobile robot path planning, when the robot traps in local minima problem under the same experimental environment.Figure 5
Path planning comparison of RIN and PC-AIN.


## 4.3. Robot’s Moving Velocity Impact on the Convergence Rate

Robot’s experimental environment is the same as Figure3, where t=1s. When the robot moves at different velocity, the convergence rate of the algorithm is different. When the velocity within a certain range, robot’s convergence rate increases with rising of the velocity. While when the velocity beyond a certain range, robot's convergence rate decreases with increasing of the velocity.As shown in Figure6, the robot moves at different velocities  0.05 m/s,  0.1 m/s,  0.15 m/s,  0.2 m/s,  0.25 m/s, and 0.3 m/s, respectively. With different velocities, robot has different running steps and different convergence rate. The result shows that when the velocity is less than 0.25 m/s, steps used reaching the goal are reduced and convergence rate is increased with rising of velocity. While when the robot’s velocity is 0.25 m/s, steps of robot for path planning are greater than the steps with the speed of 0.2 m/s and 0.15 m/s, and when the robot’s velocity is 0.3 m/s, steps of robot for path planning are greater than the steps with the speed of 0.2 m/s. So, robot’s convergence rate does not increase with rising of velocity.Figure 6
Moving velocity impact on convergence rate.Accordingly, the velocity of robot is not faster or better in mobile robot path planning, and the velocity has certain limitations. Selecting a proper velocity increases the convergence rate for mobile robot path planning.


## 4.4. The Interaction between Antibodies

This experiment is mainly used for validating stimulative affinity and suppressive affinity between antibodies, and expounding the antibody does not exist in the body independently. Figure7 shows the affinity between antibody 1 and other antibodies.Figure 7
Affinity variation of antibody 1 with other antibodies.There are eight antibodies in the experiment; affinity between antibody1 and other antibodies expressed by red “*” in Figure 7. The other antibodies have stimulative affinity impact on antibody 1 if the affinity is greater than zero, and the other antibodies have suppressive affinity impact on antibody 1 if the affinity is less than zero. And the antibody 1 has the maximum stimulative affinity impact on antibody 1. The results correspond to (13). Stimulative-suppressive effect is positive if 0<Δθil<π/2, or 3π/2<Δθil<2π, and stimulative-suppressive effect is negative if π/2<Δθil<3π/2. The interaction between antibodies has a great impact on the immune network.


## 4.5. Analysis of Time Complexity

Polyclonal-based artificial immune network optimizes the path planning and speeds up the convergence rate. Meanwhile, it also solves the problems of immature convergence and local minima, but it's time complexity of each generation increases because of the use of clonal operator, clonal crossover operator, clonal mutation operator, and clonal selection operator.Assuming thatn is the size of antibody population, N>n is a given value related to the clonal scale and Nc is every antibody's clone scale. In this paper, Nc=5n. At every generation of evolution, the worst time complexity of clonal operator is O(nNc), the worst time complexity of clonal crossover operator is O(N), the worst time complexity of clonal mutation operator is O(N), and the worst time complexity of clonal selection operator is O(N+n). So, the worst time complexity of the proposed algorithm in the generation is computed as follows:
(21)O(nNc)+O(N)+O(N)+O(N+n)=O(nNc+3N+n)=O(n·5n+3n·Nc+n)=O(5n2+3n·5n+n)=O(5n2+15n2+n)=O(20n2+n).So, the worst time complexity of the proposed algorithm in the generation isO(n2).


## 4.6. Real-Time Simulation

In this experimental, amigo is used to validate the proposed algorithm, and programming languages used are MATLAB and C++. The system mainly consists of the following parts: host computer, vision system, amigo with an on-board PC, and wireless Ethernet. The camera is used to get the environmental information including obstacles and goal in this system. MATLAB is used to execute the path planning algorithm, and C++ is used to control the motion of robot. The host computer controls the on-board PC through wireless Ethernet.The robot is a differential drive two-wheeled mobile robot. In Cartesian coordinates, the pose, velocity, and angular of differential drive two-wheeled mobile robot can be described as (22) [27]
(22)[xyθ]=[cosθ0sinθ001][vω],
where v is the robot translation velocity and ω is the robot rotation velocity defined as (23)
(23)ω=vR-vLdw,v=vR+vL2.vR and vL are right and left wheels translation velocities of robot, respectively, and dw is the distance between two wheels centers as shown in Figure 8.Figure 8
Differential drive mobile robot.In this paper, polyclonal-based artificial immune network is used to get the pose of robot. At real environment, two wheels velocities are computed through robot pose.AssumingΔSR and ΔSL are the displacement of right and left wheels during Δt, so
(24)Δx=ΔSL+ΔSR2×cosθ,Δy=ΔSL+ΔSR2×sinθ,Δθ=ΔSR-ΔSLb.
Based on (24), the displacement of right and left wheels is computed as follows:
(25)ΔSR=Δxcosθ+dwΔθ2,cosθ≠0,ΔSL=Δxcosθ-dwΔθ2,cosθ≠0
or
(26)ΔSR=Δysinθ+dwΔθ2,sinθ≠0,ΔSL=Δysinθ-dwΔθ2,sinθ≠0.From (25) and (26), left and right wheels velocities are computed.The proposed algorithm is validated at the following scenarios as shown in Figures9 and 10. Figure 9 is a barrier wall, and Figure 10 is a complex environment. Robot reaches the target successfully at the previous scenarios.Figure 9
Barrier wall.Figure 10
Complex environment.


## 5. Conclusion

This paper deals with a polyclonal-based artificial immune network algorithm for mobile robot path planning in unknown static environment. This algorithm overcomes the immature convergence problem of artificial immune network and local minima problem of artificial potential field with increasing diversity of antibodies which tend to the same extreme value in solution space. Different simulated test scenarios are conducted to test the performance of the proposed algorithm. Simulation results validate the flexibility, efficiency, and effectiveness of the robot path planning architecture, especially the immature convergence and local minima problem. Meanwhile, some real-time experiments validate the implementability of the proposed algorithm.



---

*Source: 416715-2013-09-29.xml*