J Intell Robot Syst (2010) 60:111–131 DOI 10.1007/s10846-010-9408-9
A Novel Immune Network Strategy for Robot Path Planning in Complicated Environments Mingxin Yuan · Sun-an Wang · Canyang Wu · Naijian Chen
Received: 12 October 2008 / Accepted: 22 February 2010 / Published online: 23 March 2010 © Springer Science+Business Media B.V. 2010
Abstract To solve the path planning in complicated environments, an improved artificial immune network strategy for robot path planning is presented. Taking the environment surrounding the robot and robot action as antigen and antibody respectively, an artificial immune network is constructed through the stimulation and suppression between the antigen and antibody, and the optimal path is searched in the network. To further improve the convergence property of immune network, the planning results of artificial potential field (APF) method is taken as the prior knowledge, and the instruction definition of new antibody is initialized through the vaccine extraction and inoculation. The accessibility of proposed improved immune network algorithm (IINA) is analyzed using the Markov chain theory. Compared with simple immune network algorithm (SINA) and ant colony algorithm (ACA), simulation results indicate that the proposed algorithm is characterized by high convergence speed, short planning path and self-learning, which solves the path planning well in complicated environments. Keywords Path planning · Immune network · Artificial potential field · Vaccine · Markov chain
1 Introduction As one of the key technology in mobile robot autonomous navigation, path planning refers to searching an optimal and collision-free path from starting point to goal
M. Yuan (B) · S.-a. Wang · C. Wu · N. Chen School of Mechanical Engineering, Xi’an Jiaotong University, Xi’an 710049, China e-mail:
[email protected] M. Yuan School of Mechanical and Metallurgical Engineering, Jiangsu University of Science and Technology, Zhangjiagang, 215600, China
112
J Intell Robot Syst (2010) 60:111–131
according to certain optimization criterion (e.g., minimal working cost, shortest walking route). At present, the common path planning methods include APF [1], genetic algorithm (GA) [2], ACA [3], and so on. However, to some extent, they have several disadvantages, such as local minimum, large calculation, difficult division of grid, etc. From the development of path planning, much attention has been focused on the bionic artificial intelligence algorithms (e.g. neural network, particle swarm optimization, GA, ACA,) which have already been demonstrated robustness and flexibility. Biological immune system (BIS) is a complicated distributed adaptively learning system, and it has various interesting features such as immunologic defence, tolerance, memory, surveillance and so on [4]. Inspired by the mechanism of BIS, artificial immune system (AIS) has become a key focus [5] after evolutionary algorithm, fuzzy logical and neural network, and its application scope has been gradually expanded to pattern recognition, intelligent optimization, data mining, robotics, automatic control, and fault diagnosis and so on. In the 1980s, Farmer et al. [6] presented a dynamic model for immune system based on idiotypic network hypothesis. On the basis of Farmer’s dynamic model, Ishiguro et al. [7] firstly developed a new behavior—based AI technique, and realized mobile robot path planning in dynamic and complicated environments. Subsequently, Ishiguro provided a kind of behavior arbitration mechanism [8], and the mechanism was evaluated on a garbage-collecting problem. Meshref et al. [9] and Li et al. [10] solved the dog and sheep problem in distributed autonomous robotics system (DARS) by using Farmer’s model. Farmer’s dynamic model demonstrated robustness and flexibility in mobile robot path planning, however, it was short of the global optimization ability. Inspired by the mechanism of idiotypic network hypothesis, Wang et al. [11] converted the path planning into the space search in antibody network by using the stimulation and suppression between the antigen and antibody, and presented a new simple immune network algorithm (SINA), which improved the immune planning ability well, however, the global searching mechanism of SINA is so simple that the searching precision and convergence property need further improvement. In this paper, on the basis of idiotypic network hypothesis, the immune network is constructed through the stimulation and suppression between the antigen and antibody, and a new antibody choice operator is constructed, which improve the search rationality of immune network. For new antibody, the planning results of APF method are taken as prior knowledge, and the initial instruction definition is initialized through the vaccine extraction and inoculation, which improve the convergence property of immune network. This paper is arranged as follows. Section 2 describes the artificial immune system. Section 3 presents the immune network algorithm based on APF method. Section 4 gives the accessibility analysis of IINA. Section 5 is the simulations and analysis, including the path planning and the analysis of algorithm parameters. Section 6 gives an experiment. Finally, Section 7 states some conclusions.
2 Artificial Immune System Biological immune system is a highly evolved, complicated adaptability system, which can identify and resist antigenic foreign bodies like bacteria and viruses
J Intell Robot Syst (2010) 60:111–131
113
Fig. 1 Jerne’s idiotypic network
Epitope
Paratope
Antigen
B-cell2 Id2
Idiotope B-cell1 Id1
Ab2
P2
B-cell3 Ab1
Id3 Ab3
P1 Stimulation Suppression
P3
and maintain the stability in the vivo environment. Despite the plentiful research achievements on the bio-immunology, biological immune system is complex and not yet fully understood by human. Idiotypic network hypothesis [12, 13], developed by Jerne based on the theory of clone selection in 1974, is one of the important immune theories. The concept of network hypothesis is that B-lymphocytes are not isolated, namely they are communicating to each other among different species of B-lymphocytes through the interaction among antibodies. The idea of Jerne’s is schematically shown in Fig. 1. From the figure it can be seen that the stimulation and suppression chains among B-lymphocytes form a large-scaled network and works as a self and non-self recognizer. When an antibody’s idiotope is recognized by the paratopes of other antibodies, it is suppressed and its concentration is reduced. However, when an antibody’s paratope recognizes the idiotopes of other antibodies or the epitopes of antigens, it is stimulated and its concentration increases. Artificial immune system is the simulation of biological immune system. Inspired by the mechanism of Jerne’s idiotypic network hypothesis, the artificial immune system in this paper is constructed as follows: The omni-directional mobile robot is taken as the immune agent, and it is equipped symmetrically but unevenly with eight virtual sensors around according to the different contributions of environment information to path planning. The detection distance of virtual sensor is dived into three grades: near, mid and far, and the detection direction is 1∼8 as shown in Fig. 2. The robot can move according to eight different moving instructions C = {a, b , c, d, e, f , g, h}, i.e. {forward, left forward, right forward, left move, right move, Fig. 2 Detection direction of omni-directional mobile robot
Far 3
1 Mid 2 Near
5
4 Robot
7
Sensor 6 8
114 Fig. 3 Corresponding relation between BIS and AIS
J Intell Robot Syst (2010) 60:111–131
Paratope
Antigen
Environment Instruction Environment information
Epitope Idiotope
Environment information
Antibody
Robot Action
left back, right back and back}, and the stop instruction is adopted at the goal. The environment surrounding the robot is regarded as antigen, and the antigen epitope is the environment information including obstacles and goal. The robot action aiming at the environment is regarded as antibody, the antibody idiotope is environment information too, and the antibody paratope is the moving instruction. The match between the antigen and antibody is called stimulation and the non-match is called suppression, which are evaluated through antigen-antibody affinity. We code the environment information with binary. The corresponding relation between the BIS and AIS is shown in Fig. 3. In this paper, we construct the model of artificial immune network for path planning as shown in Fig. 4. A virtual robot sets off from the “S” point, and searches the “G” point by using the match between the antigen and antibody. The moving trail of virtual robot can be described with a series of antibodies, and the connection among antibodies is not invariable, which depends on the environment surrounding the robot and instruction definition. A large-scaled artificial immune network is constructed from “S” to “G”. The essence of path planning is to find an inner figure composed of antibodies, and the figure describing the moving trails of robot is the best.
3 Immune Network Algorithm Based on APF Method 3.1 Basic Definitions To simplify the description of our proposed algorithm, some basic definitions are provided firstly. Fig. 4 Model of artificial immune network
Antibody
. ..
Antigen Stimulation
Optimal Path
Suppression
G
. .. Immune Network
S
J Intell Robot Syst (2010) 60:111–131
115
Definition 1 Let antigen (Ag) be the environment information (i.e. obstacle information χ AgO and goal information χ AgG ) surrounding the robot at time t. χ AgO is coded according to the detecting directions and distances of sensors, and χ AgG is coded according to the detecting directions. In this paper, the antigen is defined as follows: Ag = χAgO , χAgG (1) 8
where, χAgO = ∪ AgOi . ∀ i = 1,2, ...,8, AgOi ∈ {00, 01, 10, 11}, the element of the i=1
set denotes non-obstacle, near distance, middle distance and far distance at direction 8
i respectively. χAgG = ∪ AgGi . ∀ i = 1,2, ...,8, AgGi ∈ {0, 1}, the element of the set i=1
denotes non-goal and goal at direction i respectively. Definition 2 Let antibody (Ab) be the robot action aiming at environment at time t, which includes the environment information (i.e. obstacle information χ AbO and goal information χ AbG ) and moving instruction set C. The antibody is defined as follows: Ab = (χAbO , χAbG , C)
(2)
8
where, χAbO = ∪ AbOi , ∀ i = 1,2, . . . ,8, AbOi ∈ {00, 01, 10, 11}. χAbG = i=1
8
∪ AbGi ,∀ i = 1,2, . . . ,8, AbGi ∈ {0, 1}. The elements of the above two sets are
i=1
defined as the same way as in antigen. Definition 3 In this paper, the antigen-antibody affinity ζ is used to evaluate the matching degree between the antigen and antibody. In the biological immune system, the genes of antigen or antibody at different positions are of equal importance. However, in this paper, the coded information of obstacle is taken as genes of antigen or antibody, and the genes give different contributions. From Fig. 2, it can be seen that the contribution of the frontal information of the robot is bigger than its rear information, the foremost contribution is the biggest, the hindmost contribution is the least, and the left and right contribution are symmetrical and equal. To embody the different contributions of information at different positions in path planning, the antibody-antigen affinity ζ is defined as follows: ⎛ ⎞ 8 AGi ⎟ 8 ⎜
⎜ ⎟ i=1 ζ = ⎜1 − 1+ (3) εi AOi ⎟ ⎝ 2 ⎠ i=1
Where, AGi = (AgGi ⊕AbGi ) denotes the matching information of goal between the antigen and antibody at direction i, the sign ⊕ represents XOR logical operator, AOi = (AgOi ⊕AbOi ) denotes the matching information of obstacles between the antigen and antibody at direction i, εi is the contribution weight of obstacle information, and ε = {2, 0.5, 0.5, 0.15, 0.15, 0.1, 0.1, 0.01} in our experiment. From Eq. 3, we can see the antigen-antibody affinity ζ will be zero if the goal of antigen doesn’t absolutely match that of antibody, contrarily, when the goals of
116
J Intell Robot Syst (2010) 60:111–131
antigen and antibody are a good match, the antigen-antibody affinity ζ will only depend on the matching information of obstacles, and it is correlative with the contribution of the obstacle information. To avoid quick expansion of rule database and improve the searching efficiency of IINA, let ζ 0 be the critical antigen-antibody affinity when the obstacle and goal information of antibody from detecting direction 1 to 5 are the same with those of antigen in this paper, and ζ 0 ≈ 0.7. 3.2 Vaccine Extraction and Inoculation Based on APF If there is no any prior knowledge, the initial instruction definition of new antibody is τ i = 1/N (N is the number of instruction of an antibody), namely the choice probability of each instruction is equal. To avoid absolute random transition of antibody and improve the search efficiency of immune network, the planning results based on APF method are taken as prior knowledge, and the initial instruction definition of new antibody is initialized through vaccine extraction and inoculation. 3.2.1 APF Method APF was proposed by Khatib in 1986 [14]. The main concept of APF is: The attractive potential field U att is constructed according to the goal, the repulsive potential field U rep is constructed according to the obstacles, and the robot moves to the goal under the total virtual force of attractive force Fatt of U att and repulsive force Frep of U rep . For simplicity, we assume that the robot is of point mass and moves in a twodimensional (2D) workspace. Its position in the workspace is denoted by P = [x y]T . The attractive potential is generally defined as follows: 1 U att p = ξρ m p, pgoal 2
(4)
where, ξ is a positive scaling factor, Pgoal is the position of goal, ρ(P, Pgoal ) = Pgoal − P is the euclidean distance between the robot and goal. Different m will result in different shapes of attractive potential field. When m = 2, the virtual attractive force is defined as the negative gradient of the attractive potential field in terms of position, i.e. Fatt p = −∇U att p = ξρ p, pgoal nRG
(5)
where, nRG is the unit vector pointing from the robot to goal. To solve the GNRON (goals nonreachable with obstacles nearby) problem in basic APF method, the repulsive potential field can be defined as follows [15]: U rep p =
1 − λ ρ p,p1 ( obs ) 2
1 ρ0
0
2
ρ n p, pgoal if ρ p, pobs ≤ ρ0 if ρ p, pobs > ρ0
(6)
where, λ is a positive scaling factor, Pobs is the position of obstacle, ρ(P, Pobs ) is the euclidean distance between the robot and obstacle, ρ 0 is the influence range of obstacle, and n is a positive constant. In this paper, n = 2.
J Intell Robot Syst (2010) 60:111–131
117
Similar to the definition of attractive force, the repulsive force is defined as the negative gradient of the repulsive potential in terms of position. F1 nOR + F2 nRG if ρ p, pobs ≤ ρ0 Frep = −∇U rep p = (7) 0 if ρ p, pobs > ρ0
1 1 − F1 = λ ρ0 ρ p, pobs
ρ p, pgoal ρ p, pobs
2 1 1 1 − F2 = λ 2 ρ0 ρ p, pobs
(8)
(9)
where, nOR is the unit vector pointing from the obstacle to robot. After the calculation of the attractive and repulsive forces, the total virtual force can be obtained by Ftotal =
Nobs
Frepi + Fatt
(10)
i=1
where, Nobs is the number of obstacle, and Frepi is the repulsive force brought by ith obstacle. 3.2.2 Vaccine Extraction and Inoculation In the complicated environments where there is no local minimum point, the robot can have a quick and safe obstacle avoidance based on APF method. Accordingly, the moving direction for avoidance will be the optimal reference for instruction selection of antibody. To improve the search efficiency of IINA, the planning results of APF method are taken as prior knowledge, and the instruction definition of new antibody is initialized through vaccine extraction and inoculation. The concrete operating sequences are as follows: Step 1 Confirm a new antibody. Step 2 Calculate the attractive force Fatt and repulsive force Frep of robot based on APF method. Step 3 Calculate the deflexion direction of the robot according to the total virtual force Ftotal . Step 4 Calculate the angles among deflexion direction and all moving directions of instructions. Step 5 The instruction with minimal angle is given the maximal instruction definition, then the instruction is taken as center, and other instructions are given the definition symmetrically with equal weights. If the robot moves according to the instruction whose definition is the maximum, the initial path will be the planning result of APF method. However, the instruction of antibody is selected according to the roulette-wheel algorithm in this paper, the instruction with maximal definition will be selected with high probability, which will accelerate the efficiency of obstacle avoidance, and the instruction with minimal definition has possibility to be selected too, which guarantees the rationality and diversity. In our experiment, according to the increasing sequence of angles, the
118
J Intell Robot Syst (2010) 60:111–131
initial definitions of eight instructions are given {0.4, 0.2, 0.2, 0.08, 0.08, 0.015, 0.015, 0.01} respectively. 3.3 Flow of INA Based on APF Step 1 Initialize parameters: maximal cycle times kmax , ξ , λ, ρ 0 and so on. Step 2 Initialize the planning task. Step 3 Extract the environment information, and code antigen according to (1). Look for the matching antibody whose affinity ζ is bigger than ζ 0 and is the biggest according to (3) from the rule database. If there is none, a new antibody is produced according to (2), otherwise go to step 5. Step 4 Finish the vaccine extraction and inoculation to the new antibody based on APF method, and the new antibody is written in rule database. Step 5 Antibody transition. To realize the reasonable transition of virtual robot from antibody i to j, and improve the transition efficiency, we take the instruction definition of antibody i and variation of distance from the goal after execution of instruction as variables in this paper, and construct a new instruction selection probability of antibody as follows: α β τij (t) · qij (t) pij (t) = 8 (11) β α [τil (t)] · qil (t) l=1
where, α is the instruction definition enlightening factor, β is the goal enlightening factor, τ ij (t) is the instruction definition from antibody i to j at time t, qij(t) is the goal enlightening function and defined as follows: qij (t) =
1 d ( j ) − min ( d) + υ
(12)
where, υ is the adjusting coefficient, and υ > 0. d is the variation of distance. d ( j ) = d Ab i , Abj (13) = pgoal − pAb − pgoal − pAb i
j
where, · is the euclidean distance, PAb and PAb j are the position coordinates of antibody i and j respectively. Step 6 Judge whether the virtual robot wanders or collides. If not, go to the next step, otherwise, carry out the learning strategy of instruction definition, update the rule database, and go to step 3. The learning purpose of instruction definition is to decrease the definition of instructions causing the collision and wandering, and increase the attending probability of other instructions. The detailed operations are as follows: First, the robot retraces Nb steps until the front obstacles are far away or there are no obstacles in front of robot from the point of collision or wandering, then the corresponding instruction definitions are learnt. The learning function of instruction definition is: τ n (t) = τ n (t − 1) ∗ (1 − 1/n)
(14)
J Intell Robot Syst (2010) 60:111–131
119
Here, n(1 ≤ n ≤ Nb ) is the retracing step. If n = 1, the definition of instruction causing collision or wandering is 0, which provides attending opportunity for other instructions in the same environment. Step 7 Judge whether the virtual robot has reached goal. If not, go to step 3, otherwise hold optimal path and update instruction definition. To improve search efficiency of IINA, the executing instructions which successfully finish the path planning should be encouraged and their instruction definition should be improved. When the same antigens are met with during the next planning task, the successful instructions will be executed again with high probability, which will form a positive feedback mechanism and accelerate the recognition of antigen. In addition, the instructions of other antibodies will be forgotten with certain forgetting rate. With the progress of path planning, the unused or unreasonable instructions of antibodies will be forgotten, and the excellent instructions w ill be saved. Encouraging function of instruction definition: τ (t) = τ (t − 1) + μ/L
(15)
Where, μ is a constant, L is the length of found path in one cycle. Forgetting function of instruction definition: τ (t) = γ · τ (t − 1)
(16)
where, γ is the forgetting rate. Step 8 Judge whether the algorithm has finished all cycles. If not, go to step 2, otherwise output the optimal path.
4 Accessibility Analysis of IINA The accessibility of IINA can be described: If there is a feasible path from the starting point to goal, the IINA can convergence to the goal from the starting point with probability 1 in each cycle. Theorem 1 The planning process based on IINA is a f inite homogeneous Markov chain. Proof Let X(t) = {τ (t), AbNet(t), f ∗ (t)},(t = 1,2, . . . ) be a random process, where τ (t) is the instruction definition, AbNet(t) is the antibody network, f is the optimization function for path planning, and f ∗ (t) is the optimal path length. According to the planning course of IINA, the construction of AbNet(t) depends on the transition of antibody based on the instruction selection. From Eq. 11, we can know that the selection probability lies on τ (t), and τ (t) lies on (τ (t− 1), AbNet(t− 1)), so X(t) only lies on the state at cycle t− 1 and has no relation to previous state and cycle period t. Accordingly, the path planning based on IINA is a finite homogeneous Markov chain in this paper.
Lemma 1 All points in Markov chain transition diagram M based on immune network algorithm are connected [16].
120
J Intell Robot Syst (2010) 60:111–131
Lemma 2 The goal of robot is a single point and one closed set in the state transition diagram M [16]. Lemma 3 In the state transition diagram M, there is one and only one closed set including goal. Proof If there is a closed set except the goal in the transition diagram M, the set will be necessarily constructed by the state points where the virtual robot meets with collision and wandering. Aiming at the above collision and wandering, the learning strategy of instruction definition is carried out in this paper, namely, according to the AbNet(t), the virtual robot retraces Nb steps to point P, and the instruction definitions are learnt based on τ n (t) = τ n (t − 1)*(1 − 1/n) (1 ≤ n ≤ Nb ), which will provide chances for other antibodies. If all paths from the point P are traversed, and the virtual robot can’t always get out of the closed set, the virtual robot will retrace Nb steps again from P, and the instruction definition will suffer the same learning treatment. With the same operation, the robot will finally retrace to the starting point, consequently the starting point is a closed set, which contradicts the assumption of proposition (i.e. there is a feasible path from the starting point to goal). Accordingly, there is one and only one closed set in the transition diagram M.
Theorem 2 The IINA can converge to the goal from the starting point with probability 1 in each cycle. Proof According to the Lemmas 1, 2 and 3, the virtual robot will find a feasible path from the starting point to goal with probability 1 when each point in transition diagram M is connected and there is one and only one closed set including goal, which guarantees the IINA will convergence to the goal with probability 1 in each cycle.
5 Simulation Experiments and Discussion 5.1 Path Planning in Complicated Environments To verify the effectiveness of IINA in complicated environments, aiming at four different environments as shown in Fig. 5, we carried out some simulations with Matlab 7.0 on an Intel Pentium IV 2.99 GHz computer with 512 MB RAM. Environment 1 and 2 are relatively simple and there are no obvious local minimum points, but the number of obstacles is different. Environment 3 and 4 are very complex and there are obvious local minimum points before the goal, especially there is an local minimum point of concave type in environment 4 which is very difficult for robot to find the optimal path. The planning results are compared with those of SINA [11] and ACA [3]. The path planning based on IINA are carried out with vaccine inoculation and non-inoculation. Considering the randomness, each algorithm in each environment is independently tested for 30 times. For the antibody (or ant) path is tortuous and not suitable for robot to move in local region, the path is simply treated by straightening and smoothing in this paper. In IINA, kmax = 50, ξ = 10, λ = 2, ρ 0 = 4 m, α = 1, β = 2, υ = 0.01, μ = 3, γ = 0.1. In SINA, maximal cycle times is 50, population size
J Intell Robot Syst (2010) 60:111–131
121 (m) 8
(m) 8
6
6
G
S
4
S
4
G
2
2
0
0 0
5
10
15
20 (m)
0
5
a
10
15
20 (m)
b (m) 8
(m) 8
6
6
S
4
G
S
4
G
2
2
0
0 0
5
10
c
15
20 (m)
0
5
10
15
20 (m)
d
Fig. 5 Four simulation environments. a Environment 1. b Environment 2. c Environment 3. d Environment 4
is 10, matching rate is 0.1, and forgetting rate is 1%. In ACA, the environment is divided into 20 × 50,ant number is 20, pheromone and goal enlightening factors are 1 and 2 respectively, and evaporation factor is 0.1. Table 1 is the performance comparison of planning results among three algorithms. The performance involves average convergence generation, average path length of antibody (or ant), average smooth path length, optimal path length of antibody (or ant) and optimal smooth path. Firstly, from the property of average convergence, it can be seen that SINA and IINA are better than ACA for they make full use of stimulation and suppression between the antigen and antibody and immunological memory. Although the convergence speed of SINA is the fastest, it is only the local convergence. The convergence speed of IINA with inoculation is much quicker than that of IINA with non-inoculation. From the average and optimal antibody (or ant) path, the length of SINA is the longest, which fully shows that the ability of optimal planning of SINA is weak. The path length of IINA with inoculation is the shortest, and the lengths of IINA with non-inoculation and ACA are close. From the average and optimal smooth path, we can see that the smooth path lengths of antibody after treating are better than that of ACA, and the length of IINA with inoculation is obviously the shortest. Figure 6 is the evolutionary curves of three algorithms in environment 4. From the figure, it can be seen that SINA and IINA can avoid all kinds of obstacles, especially the local minimum point, and find the optimal path by self-organization, self-learning and immunological memory, which preferably show the flexible and robustness of immune network algorithm. Contrasting the evolutionary curves of
IINA
SINA ACA IINA
SINA ACA IINA
SINA ACA IINA
1
2
3
4
SINA ACA
Algorithm
Environment
Inoculation Non-inoculation
Inoculation Non-inoculation
Inoculation Non-inoculation
Inoculation Non-inoculation
13.35 15.40 10.39 24.40 12.80 13.31 11.08 22.77 14.55 16.35 12.34 24.77 13.28 16.94 12.94 23.50
Average convergence generation
Table 1 Performance comparison of planning results among three algorithms
24.08 24.62 26.14 24.36 23.28 23.55 25.92 24.62 24.04 25.72 27.54 25.14 23.83 24.77 26.91 24.92
Average path length of antibody (or ant), m’ 22.85 22.94 23.26 23.73 22.19 22.67 23.87 24.08 23.27 24.08 24.18 24.77 23.08 23.86 24.06 24.17
Average smooth path length, m 22.40 22.83 25.60 22.91 22.00 22.80 24.80 23.25 22.80 23.20 25.44 23.71 22.80 23.40 25.20 23.25
Optimal path length of antibody (or ant), m
21.29 21.83 22.62 22.25 21.45 21.60 22.26 22.89 21.86 21.89 22.28 23.11 21.99 22.17 22.46 22.56
Optimal smooth path length, m
122 J Intell Robot Syst (2010) 60:111–131
J Intell Robot Syst (2010) 60:111–131 (m) 8
123 (m) 8
All Antibody Networks Optimal Antibody Path
6
All Antibody Networks Optimal Antibody Path
6
S
G
S 4
4
2
2
0
G
0
0
5
10
20 (m)
15
0
5
a
(m) 8
10
15
20 (m)
b All Antibody Networks Optimal Antibody Path
6
S
G
4 2 0 0
5
10
20 (m)
15
c Fig. 6 Evolutionary curves of two algorithms in environment 4. a IINA with inoculation. b IINA with non-inoculation. c SINA
Fig. 6a, b with c, we can obviously see that the convergence property of IINA with improved instruction selection operator is better than SINA. In addition, the vaccine extraction and inoculation accelerates the convergence speed of IINA, and the convergence property of IINA with inoculation is obviously better than that of IINA with non-inoculation. Figures 7 and 8 are the optimal planning results of three algorithms in environment 2 and 4. Figures 7a and 8a are the optimal antibody (or ant) paths, and Figs. 7b and 8b are the relevant optimal smooth paths.
(m) 8
IINA with inoculation IINA with non-inoculation SINA ACA
6
S
(m) 8
G
4
IINA with inoculation IINA with non-inoculation SINA ACA
6
S
G
4 2
2
0
0 0
5
10
a
15
20 (m)
0
5
10
15
20 (m)
b
Fig. 7 Optimal planning results of three algorithms in environment 2. a Optimal antibody (or ant) path. b Optimal smooth path
124
J Intell Robot Syst (2010) 60:111–131
(m) 8
IINA with inoculation IINA with non-inoculation SINA ACA
(m) 8
IINA with inoculation IINA with non-inoculation SINA ACA
6
6
G
S
G
S
4
4
2
2 0
0 0
5
10
20 (m)
15
0
5
10
a
15
20 (m)
b
Fig. 8 Optimal planning results of three algorithms in environment 4. a Optimal antibody (or ant) path. b Optimal smooth path
Figures 9 and 10 are the average convergence curves of three algorithms in environment 2 and 4 respectively. From the two figures, we can obviously see that the optimal planning property of SINA is weak, and the IINA with inoculation is the best. In the relatively simple environment 2, the planning property of IINA with non-inoculation is close to that of IINA with inoculation, however, in environment 4, the property of IINA with non-inoculation is close to that of ACA, which further shows the importance of inoculation in complicated environments. 5.2 Parameter Experiments for IINA The testing results in Table 1 show that IINA is characterized by quick convergence speed and strong planning ability, especially IINA with inoculation. However, different algorithm parameters will cause different planning results in the same environment. It is very important to have a study on the parameters of IINA for planning properties. In this paper, the main parameters of IINA, namely instruction definition enlightening factor α, goal enlightening factor β, forgetting rate γ , are studied.
Fig. 9 Average convergence curves in environment 2
32
(m) IINA with inoculation IINA with non-inoculation SINA ACA
30 28 26 24 22 0
10
20
30
40 50 (Generation)
J Intell Robot Syst (2010) 60:111–131
125
Fig. 10 Average evolution curves in environment 4
(m) 32
IINA with inoculation IINA with non-inoculation SINA ACA
30 28 26 24 22 0
10
20
30
40 50 (Generation)
5.2.1 Selection of Instruction Def inition Enlightening Factor α Enlightening factor α reflects the relative importance of instruction definition to the state transition during the antibody search. Aiming at the above four environments, under the invariability of other algorithm parameters, we independently perform the experiments for 30 times with the increase of α in [0, 5], and observe the changes of average convergence generation and planning distance. From Fig. 11, it can be seen that with the increase of α, the probability that the previous antibody instructions is selected is increased, the convergence speed is quickened and the global searching ability is weakened. However, if α is too big, the virtual robot is easy to trap into local minimum point, which will cause the prematurity of algorithm. If α is too small, the random of IINA is increased, and the ability of finding optimal antibody path is strengthened, however, the positive feedback of instruction definition isn’t obvious, and the convergence speed is slowed. Accordingly, the selection of α should be proper. Experiment results show that the search effect is the best when α is about 1.
20
(Generation)
30
Environment 1 Environment 2 Environment 3 Environment 4
(Generation) Environment 1 Environment 2 Environment 3 Environment 4
28
15 26 10 24
5
0
1
2
3
4
5
22
0
1
2
3
(α)
(α)
a
b
4
5
Fig. 11 Simulation results of instruction definition enlightening factor α. a Average convergence curves. b Average planning distance
126
J Intell Robot Syst (2010) 60:111–131
5.2.2 Selection of Goal Enlightening Factor β Enlightening factor β reflects the relative importance of distance variation from goal to the instruction selection during the antibody search. The enlightening factors of goal and instruction definition restrict and influence each other. Aiming at the above four environments, under the invariability of other algorithm parameters, we independently perform the experiments for 30 times with the increase of β in [0, 5], and observe the changes of average convergence generation and planning distance. From Fig. 12, it can be seen that the selecting probability of instruction causing shorter distance between the virtual robot and goal is increased as β increase. However, if β is too big, IINA tends to the classical greed search algorithm. Although the convergence speed of IINA is quickened, the virtual robot is easy to trap into local minimum point. If β is too small, IINA is easy to trap into random search, the search efficiency is decreased, and the convergence speed is slowed. Accordingly, considering the search effect of IINA, the value of β should be proper too. Experiments results show that the search effect of IINA is the best when β is about 2. 5.2.3 Selection of Forgetting Rate γ Forgetting rate γ reflects the remains of instruction definition as time goes on. The magnitude of γ directly reflects global search ability and convergence speed of IINA. Aiming at the above four environments, under the invariability of other algorithm parameters, we independently perform the experiments for 30 times with the increase of γ in [0, 1], and observe the changes of average convergence generation and planning distance. From Fig. 13, it can be seen that the instruction definition which is rarely used tends to 0 with the increase of γ , which will decrease the global search ability of IINA, and the instruction definition that is often used will be increased, which affects the random of IINA and makes IINA trap into local minimum value. Contrarily, the random and global search ability of IINA will be improved by diminishing the value of γ , however, the convergence speed of IINA
20
(Generation)
30
Environment 1 Environment 2 Environment 3 Environment 4
18
(Generation) Environment 1 Environment 2 Environment 3 Environment 4
28
16 26 14 24 12 22
10 8
0
1
2
(β)
a
3
4
5
20
0
1
2
(β)
3
4
5
b
Fig. 12 Simulation results of goal enlightening factor β. a Average convergence curves. b Average planning distance
J Intell Robot Syst (2010) 60:111–131 20
127
(Generation)
26
Environment 1 Environment 2 Environment 3 Environment 4
(Generation) Environment 1 Environment 2 Environment 3 Environment 4
25. 5
15 25 24. 5 10 24 5
0
0.2
0.4
(γ)
0.6
0.8
1
a
23. 5
0
0.2
0.4
(γ)
0.6
0.8
1
b
Fig. 13 Simulation results of forgetting rate γ . a Average convergence curves. b Average planning distance
will be decreased. Experiment results show that the searching effect is the best when γ is about 0.1.
6 Experiment 6.1 Experimental Setup To further verify the validity of IINA in the practical environment, aiming at a known environment, an experiment for path planning is carried out. As shown in Fig. 14, the experimental environment consists of wireless sensor network (WSN) based on Zigbee technology, a two-wheeled differential-drive tracked mobile robot using stepper motor, and five obstacles. The WSN system involves a host computer, a location dongle connected to the host computer through serial port (RS232), eight reference nodes, a blind node installed on the robot. During the experiment, on the one hand the robot communicates with the WSN system and receives the controlling instructions from the host computer through the blind node; on the other hand the robot gets the environment information surrounding the robot through WSN system and realizes the self-location. 6.2 Model of Tracked Mobile Robot [17] In the experiment, a tracked mobile robot is adopted. The model of the robot is shown in Fig. 15, where x–o–y and x0 –o0 –y0 are the global and body coordinate systems respectively. vl and vr are the velocities of the left and right tracks. θ l and θ r are the rotating angles of left and right driving wheels. v is the velocity at the center of tracked robot. b is the distance between the left and right wheels. l is the distance between the centers of wheel and robot. R is the radius of driving wheel. θ is the orientation of the robot with respect to the global coordinate system. Supposing that the sideslips of inner and outer tracks are synchronous when the robot turns and there is no any displacement between the wheel and track
128
J Intell Robot Syst (2010) 60:111–131 Optimal Path
Host Computer
Location Dongle Blind Node (Robot)
Reference Node
Obstacles
Fig. 14 Experimental system for the path planning
of crawler mechanism. The kinematics equation of the tracked mobile robot is given by + lbR sin θ − lbR
cos θ
R cos θ 2 R sin θ 2
+ lbR
− bR
⎤
⎥ θ˙r cos θ ⎦ θ˙l R
− lbR sin θ
(17)
vl
b
y
x0 y0 v θ
θ
R
vr
l
o0
b θr
Fig. 15 Model of the tracked mobile robot
R cos θ 2 R sin θ 2
l
⎡ ⎤ ⎡ x˙ ⎢ ⎥ ⎢ ⎣ y˙ ⎦ = ⎣ θ˙
o
x
J Intell Robot Syst (2010) 60:111–131
129
Then
θ˙r θ˙l
=
R 2
cos θ +
lR b
sin θ
R 2
cos θ −
lR b
sin θ
R 2
sin θ −
lR b
cos θ
R 2
sin θ +
lR b
cos θ
−1 x˙ y˙
(18)
According to the relationship between the period of PWM pulse and turning rate of wheels, the velocity of tracked mobile robot can be easily controlled. 6.3 Experimental Results The experimental results of immune planning based on the Zigbee–wireless sensor networks in known environment are shown in Fig. 16 with 12 photos, (a)∼(l), taken during the experiment. Figure 16a shows the initial position of the robot. Figure 16b∼j show that the robot tracked the optimal path by receiving the orders from the host computer through WSN system and successfully detoured the obstacles. Figure 16j∼k show that the robot moved toward goal and reached there. Compared the optimal path with real track of robot, it can be seen that there is some differences between them which are caused by the errors of wireless location.
Fig. 16 Experiment results in known environment
130
J Intell Robot Syst (2010) 60:111–131
To further improve the navigation precision, the location of robot will be finished through visual location in the next step.
7 Conclusions Inspired by the mechanism of idiotypic network hypothesis, aiming at the path planning in complicated environments, a novel immune network strategy for path planning based on APF method is presented in this paper. On the basis of theory analysis, simulations and experiment, we can draw the following conclusions: 1. IINA is characterized by self-organization and self-learning, and can find the feasible path by continuous self-learning, which avoids trapping into local minimum points when the planning environments are complicated. 2. Aiming at new antibody, the planning results of APF method is taken as prior knowledge, and the initial instruction definition is inoculated through vaccine, which obviously improves the planning efficiency and precision of IINA. 3. Study on parameters of IINA will be helpful to further improve the planning ability of immune network algorithm. A large number of simulations and experiment show that the optimal planning ability and convergence property of IINA are better than SINA, especially IINA with inoculation. Acknowledgements We thank anonymous referees for helpful comments. The support of the National Nature Science Foundation of China (NSFC; No. 50905136) is gratefully acknowledged.
References 1. Ge, S.S., Cui, Y.J.: Dynamic motion planning for mobile robots using potential field method. Auton. Robots. 13(3), 207–222 (2002). doi:10.1023/A:1020564024509 2. Liu, J., Yang, D.Y.: Path planning based on double-layer genetic algorithm. In: Proceeding of the Third International Conference on Natural Computation, pp. 357–361 (2007) 3. Liu, G.Q., Li, T.J., Li, Y.P.: The ant algorithm for solving robot path planning problem. In: Proceeding of the Third International Conference on Information Technology and Applications, pp. 25–27 (2005) 4. Jiao, L.C., Du, H.F.: Development and prospect of the artificial immune system. Acta Electron. Sin. 31(10), 1540–1548 (2003) 5. Dasgupta, D.: Artificial neural networks and artificial immune systems: similarities and differences. In: Proceeding of the IEEE International Conference on Systems, Man, and Cybernetics, pp. 873–878 (1997) 6. Farmer, J.D., Packard, N.H., Perelson, A.S.: The immune system, adaptation and machine learning. Physica D. 2(2), 187–204 (1986). doi:10.1016/0167-2789(86)90240-X 7. Ishiguro, A., Watanabe, Y., Uchikawa, Y.: An immunological approach to dynamic behavior control for autonomous mobile robots. In: Proceeding of the IEEE/RSJ International Conference on Intelligent Robots and Systems, pp. 495–500 (1995) 8. Ishiguro, A., Watanabe, Y., Kondo, T.: Decentralized consensus-making mechanisms based on immune system-application to a behavior arbitration of an autonomous mobile robot. In: Proceeding of the IEEE International Conference on Evolutionary Computation, pp. 82–87 (1996) 9. Meshref, H., VanLandingham, H.: Artificial immune systems: application to autonomous agents. In: Proceeding of the IEEE International Conference on Systems, Man, and Cybernetics, pp. 61–66 (2000)
J Intell Robot Syst (2010) 60:111–131
131
10. Li, J.H., Wang, S.A.: Model of immune agent and application in path finding of autonomous robots. In: Proceeding of the IEEE International Conference on Machine Learning and Cybernetics, pp. 1961–1964 (2003) 11. Wang, S.A., Zhuan, J.: An immunity algorithm for path finding and optimizing of the moving robot. J. Syst. Simul. 14(8), 995–997 (2002) 12. Jerne, N.K.: The immune system. Sci. Am. 229(1), 52–60 (1973) 13. Jerne, N.K.: Idiotypic networks and other preconceived ideas. Immunol. Rev. 79, 5–24 (1984). doi:10.1111/j.1600-065X.1984.tb00484.x 14. Khatib, O.: Real-time obstacle avoidance for manipulators and mobile robots. Int. J. Rob. Res. 5(1), 90–98 (1986). doi:10.1177/027836498600500106 15. Ge, S.S., Cui, Y.J.: New potential functions for mobile robot path planning. IEEE Trans. Robot. Autom. 16(5), 615–620 (2000). doi:10.1109/70.880813 16. Zhuang, J., Wang, S.A.: Further study of robot path planning algorithm based on artificial immune net theory. J. Syst. Simul. 16(5), 1017–1019 (2004) 17. Wang, L.: Kinematics modeling and study for path tracking of track robot. Dissertation, Inner Mongolia University of Technology (2007)
