Research on PAGV path planning based on artificial immune ant colony fusion algorithm

Abstract

With the rapid development of modern science and technology, more and more high-tech has appeared in front of the common people, in particular, the recent rise of artificial intelligent robots and other supernova scientific developments. In order to move the robot according to the direction of the system design, it is necessary to plan the robot’s walking path to a certain extent; this requires the use of specific algorithms to achieve. This paper was based on the application of path planning at the present stage, the artificial immune and ant colony fusion algorithm were used to plan and analyze the AGV path, the ant colony algorithm based on the artificial immune algorithm to enhance the recognition function of the immune system and the ant searching for food secretion pheromone as the optimal path finding method was the basic algorithm developed in this paper, the path planning of AGV was analyzed and studied.

Keywords

Immune algorithm path planning ant colony algorithm

1 Introduction

Artificial intelligent robot as a hot research direction in modern times, effective applications is obtained in a variety of industrial projects, such as mechanical automation, large-scale engineering, product assembly and so on [1]. In these areas of research, besides, artificial intelligence robots can replace human beings to do relatively simple jobs, the rising emerging intelligent AI system also gives the robot the ability to think, it’s far greater than human computing power, it makes its application very extensive [2]. Artificial immune algorithm and ant colony algorithm also have important applications in many fields as a long time algorithm, but the application of artificial intelligence has just begun in recent years, [3]. Artificial immune algorithm uses bionic principle to simulate the effect of human immune system and the mechanism of antibody in human body and the self regulation function of immune system are displayed in the computational method by bionic way, and the ant colony algorithm mainly uses the ant colony to mark the path node when the pheromone is secreted in the search for food, ant colony algorithm will label nodes with pheromone, memory function is motivated when the pheromone set is at a certain critical point, then when the part is finished, the pheromone is automatically dissipated, so as to achieve the ultimate goal of the algorithm [4].

At present, many experts for AGV path planning algorithm are still stuck in the old-fashioned thinking, the algorithms used have many shortcomings, which has seriously affected the maturity of artificial intelligent robots in path finding, and then it has a huge impact on the efficiency of many jobs, resulting in low efficiency, and seriously reduces the accuracy of robot work results [5]. In the process of AGV path planning, many scholars have found, most of the traditional ACA algorithms have the problem of generating local optimal solution easily, this makes the advantages of artificial immune ant colony fusion algorithm gradually revealed, artificial immune ant colony fusion algorithm can not only avoid the problem of local optimal solution, but also reduce the phenomenon of the algorithm which is not comparable to the algorithm in the conventional algorithm, this solves the problem of AGV path planning for artificial intelligent robot, the optimal path calculation is achieved [6].

2 Installing and using the Microsoft Word template

The artificial immune ant colony fusion algorithm will apply to the AGV path planning process, it can effectively solve the local optimization of the experimental path in the current path planning process, but the optimal problem of candidate set is not reached, and effectively use the pheromone marking method in mobile nodes to confirm the nodes in AGV path planning, reducing the accuracy of traditional algorithms in node, thus the global optimal solution can be obtained [7]. This paper is based on the current research results of AGV path planning, the path was analyzed by using artificial immune ant colony fusion algorithm, the above problem has been solved successfully.

In the research of AGV path planning, firstly, the artificial immune algorithm is used to construct the global structure of the path planning, the positive feedback and negative feedback of the information are given by using the antibody targeted attack in the artificial immune algorithm and the automatic adjustment function of the algorithm immune system [8]. Then the ant colony algorithm is used to analyze the local construction of AGV path, and will mark nodes with pheromone, ensure that each inflection point is in the construction of the whole path planning [9]. Finally, the two algorithms are fused, and produces the local optimal solution, the global optimal local solutions are compared and analyzed, then the global optimization path is generated [10].

3 Methodology

3.1 Research on AGV path planning based on artificial immune ant colony fusion algorithm

Research on AGV path planning is based on artificial immune ant colony fusion algorithm, it consists of four parts: data marking stage, antigen restriction phase input stage, antibody mutation stage and node pheromone marking stage. The specific steps are as follows: One is data mark coding phase. The AGV path planning research uses the artificial intelligence robot measured in the practice of driving route data into the database, and the basic data label is used to encode the antibody, each antibody has its own unique identification code, this stage is the basic data processing and antibody determination stage; the two is the restriction stage of antigen input. The upper stage was completed after the labeling of antibodies was completed, we will inputting the antigen part in the AGV path planning, antigen data are derived from path diagrams of artificial intelligence robots in path scanning, the constraint conditions are set up for these path data, the path data that meets our requirements are filtered out, and the scan path data that does not meet our requirements is eliminated, this stage is the preprocessing stage where we get the path data; three is the stage of antibody variation. At this stage, we will be based on the preprocessing of path basic data based on artificial immune operator mutation, get new path data, then the new path data will be obtained to calculate the antibody affinity of the results, population data with strong affinity, finally, the population data with strong affinity are re entered into the database, update the database; four is the node pheromone marking stage. The first three parts are all processed by the artificial immune algorithm, this part uses the pheromone node marking function of ant colony algorithm to mark the turning point in the path of the artificial intelligent robot, and calculate the probability distribution of the robot at the last node to the next stage, and recursive recursion is used to process the data, finally leave a good antibody for the next step. The flow chart of the above steps is shown in the following picture:

The structure diagram of the artificial immune ant colony fusion algorithm in AGV path planning is shown in the figure above, you can see it clearly in the picture above, the design of the whole process runs in strict accordance with the operation rules. In the intermediate link of the above process, that is, preprocessing path data for the first part of artificial immune and ant colony algorithm, the choice of “yes” and “no” in computer rules will be used to analyze the path basic data that the entry algorithm will enter into the algorithm, and uses “Whether the termination condition is met” this process node classifies the entire underlying data, if it satisfies the termination condition, the basic data will enter the next algorithm calculation link, if the condition of termination is not satisfied, data will be rejected and destroyed at the same time in the database, therefore, these useless basic data will not enter the next algorithm calculation stage, resulting in a large error rate and computation, it doesn’t take up the space of the system, causing serious waste of system space. Because the path planning process contains a large number of basic parameters, therefore, the table method is used to classify the basic parameters in order to understand, the basic parameters after classification are shown below:

Fig. 1

AIAC Flow chart.

3.2 Calculation of artificial immune ant colony fusion algorithm

After the construction of the basic structure based on artificial immune ant colony fusion algorithm, we’re going to calculate these algorithms, this part is not reflected in the above structure, but it is the basis of the above third steps and fourth steps, it is the algorithm processing process for the basic data in the above step algorithm. In the calculation process of this algorithm, in order to avoid the traditional algorithm of overexpansion of local optimal solution and error rate of transition nodes in AGV path planning, the resulting global optimal solution is overwhelmed by the huge amount of data, therefore, the artificial immune ant colony fusion algorithm is used to calculate the basic path data of the AGV path planning in this calculation, the calculation process of the algorithm is shown as follows.

The first is the calculation of antibodies, antibodies in the process of artificial immune refers to the acceptance of specific antigen stimulation and make a certain stress response substances, a feasible solution to the problem of replacing the fingers in the artificial immune algorithm, this part of the feasible solution is unique, each feasible solution is aimed at a particular objective function or a constraint condition. In the study of this issue, any set of nodes in the AGV path becomes the antibody to the problem, the calculations are as follows: $len = \sum_{i = 1}^{n−1} d (v_{i}, v_{i + 1}$ (1)

In the above formula, len is expressed as the path length of each antibody, L is antigen. Because although the feasible solution is unique for a particular problem, but there is instability in their relationship, this problem is mainly due to the different affinity between each antibody and antigen, in the process, we need to find antibodies that have strong affinity for antigens into the next part, so we’re going to calculate the affinity of antibodies to antigens next, the calculation formula is as follows: $f (π_{i}) = \frac{76.5 • L • \sqrt{N}}{D_{π i}}$ (2)

In the above formula, L represents the length of the AGV path, N is the number of nodes, D_πi is the length of the path in the permutation π_i. The above formula is based on artificial immune ant colony fusion algorithm AGV path construction, artificial immune algorithm basic data formula construction is completed, the next part is the ant colony algorithm for the above fourth steps in the calculation of basic data, the formula is as follows.

We’ll use n to represent the size of the node, representing m as the number of nodes, therefore, the relationship between n and m can be described by the following formula: $m = \sum_{i = 1}^{n} b_{i} (t)$ (3)

Because in the calculation process of ant colony algorithm, the pheromone of the node will disappear automatically after the completion of the function, so we use a special formula to calculate the time that the pheromones disappear, the pheromone residues at the nodes of the t at the moment are shown in the following formula:

Table 1

Parameter description in AIAC

parameter	Name	Effect
X	Node coordinate	Node coordinates are generated automatically according to the number of nodes
D	Distance matrix	Generating node distance matrix using Distanse function according to randomly generated node coordinates
N	Node number	The number of nodes in Wireless Sensor Networks
NIND	Population size	Initialize the population size of AIAC
MAXGEN	Maximal iterated algebra	Initializing AIAC iterations
Pc	Cross probability	The probability of AIAC antibody cross operation
Pm	Mutation probability	The probability of AIAC antibody mutation operation
m	Ant number	Initialize the number of ants in AIAC
Alpha	Importance factor of pheromone	The amount of information that represents the amount of information left on each node is valued
Beta	Importance factor of heuristic function	The extent to which heuristic information is valued
Rho	Pheromone volatilization factor	Represents the retention rate of pheromones

Γ = {τ_{ij} (t) / c_{i}, c_{j} \subset C}

(4)

At the initial moment, the amount of data remaining at the node is shown below: $τ_{ij} (0) = const$ (5)

Every ant goes along the path, leaving pheromones behind, when the pheromone accumulates to a certain extent; it will submerge the enlightening information, so you need to set the corresponding information. Ant colony algorithm imitates the memory characteristics of human brain, every time an ant goes one step or completes the traversal of all nodes, the algorithm will updates pheromone, the pheromones that each ant residues on each path gradually evaporate over time. That, the pheromone residue on the ij path t + n can be calculated by the following formula: $τ_{ij} (t + n) = (1 - ρ) \cdot τ_{ij} (t) + Δ τ_{ij} (t)$ (6)

The following diagram shows the flow diagram of ant colony algorithm:

Ant colony algorithm has the following advantages and disadvantages: one is compared with other intelligent algorithms, ant colony algorithm has strong robustness, easy to combine with other intelligent algorithms, to form a better intelligent algorithm; two is the need to set more parameters, these parameters are important in the program, if it is not set properly, it will lead to slow solution and affect the quality of solution; third the calculation of ant colony algorithm is quite large. Therefore, the ant colony algorithm and artificial immune algorithm fusion can not only play their own advantages, and can effectively avoid their shortcomings. The calculation of basic data of artificial immune ant colony fusion algorithm is completed, the next part will optimize and test the algorithm, and this section will be explained in the following sections.

Fig. 2

Flow chart of ant colony algorithm.

Table 2

Function and expression of immunity

Immunity	Normal performance (favorable)	Abnormal performance (harmful)
Immune defense	Resistance to pathogen invasion and toxin action	Hypersensitivity reaction and immunodeficiency disease
immunologic homeostasis	Tolerance to self components and clear antigen foreign bodies	Immune disorders and autoimmune diseases
Immune surveillance	Prevent cell canceration or persistent infection	Tumor or persistent viral infection

4 Result analysis and discussion

After the AGV path planning based on artificial immune ant colony algorithm is completed, we have tested the artificial intelligence robot in practice, we find it in the test compared with the traditional ACA algorithm, based on artificial immune ant colony algorithm of node data processing and data on the basis of the sensitive extent should be a stroke above, and in practice, artificial intelligence robots have little chance of error, and far less than the traditional ACA algorithm, so we use artificial immune ant colony fusion algorithm for the construction of AGV path is successful. But at the same time, we also find that in practice, the artificial immune ant colony fusion algorithm is less than our expectation in the accuracy of the node data and the sensitivity to the path basic data, so we test the shortcomings of our fusion algorithms in this section using algorithm testing, and correct it before the final experiment, finally, the optimal algorithm is obtained. So in the next part, we need to optimize the AGV path and perform energy efficiency ratio test, in this test, we selected 30 nodes for testing, the parameters of the test input are shown below:

Table 3
Setting up experimental parameters of 30 nodes

AIAC Node Number 30 genetic algorithm Node Number 30

NIND 15 NIND 20

MAXGEN 500 MAXGEN 30

Pc 0.9 Pc 3

Pm 0.05 Pm 8

threohold 0.6 threohold 0.1

GGAP 0.9 GGAP 50

Node Number	30	Node Number	30
NIND	15	NIND	20
MAXGEN	500	MAXGEN	30
Pc	0.9	Pc	3
Pm	0.05	Pm	8
threohold	0.6	threohold	0.1
GGAP	0.9	GGAP	50

Fig. 3

Time delay contrast chart.

As you can see from the picture above, the contrast parameters are selected from 30 nodes, although the following parameters are not consistent, they have differences between the two algorithms, and it’s not the basic data that is deliberately chosen, so the test results are correct. In the process of this test, the difference between genetic algorithm and artificial immune ant colony fusion algorithm is chosen as the test object, in the process of comparison, the vector we selected is a small robot, because artificial immune ant colony algorithm is applied to small robots, the path optimization of artificial intelligence robot embodies the largest, so this robot carrier has the advantage of miniaturization, so in the subsequent testing process, the success of robot miniaturization reflects the difference between algorithms. In the next test, we need to compare the difference in efficiency between the two algorithms, the specific test results are sorted into a line chart as follows:

From the above results, we can find that, the time difference between the algorithms is not very different, but when the number of nodes increases, the advantage of the artificial immune-ant hybrid algorithm (AIAC) highlights the number of nodes at 30 nodes, AIAC consumes the shortest time in all algorithms, it’s three quarters of the colony algorithm(ACO), comparing artificial immune algorithm (AIAC), genetic algorithm (GA), simulated annealing algorithm (SA) time, AIAC’s optimization speed is relatively fast. Through a lot of contrast experiments in front, it can be seen that AIAC has a great advantage both on path optimization and delay. Compared to SA, GA, ACO when the number of nodes becomes more, easy to fall into local optimal solution, the path sought is only a better approximation rather than an optimal solution, the consumption time also increased rapidly.

In summary, in this artificial immune ant colony fusion algorithm and other algorithms in the horizontal contrast, we can conclude that, the artificial immune ant colony algorithm has the advantages of efficiency and accuracy, in these two aspects, artificial immune ant colony fusion algorithm has overcome the other algorithms with great advantage. This proves that the algorithm we selected is correctly, the success of AGV path planning of artificial intelligence robot has a positive effect.

5 Conclusion

This research on AGV path planning based on artificial immune ant colony fusion algorithm, it consists of four parts: data marking stage, antigen restriction phase input stage, antibody mutation stage and node pheromone marking stage. In this paper, the artificial immune algorithm and ant colony algorithm based on the two are fused together, artificial immunity was clarified—the principle of ant colony algorithm, basic concepts, detailed design is carried out, artificial immunity was obtained—ant Colony Hybrid Algorithm (AIAC). This algorithm is used to find the optimal path in the population of artificial immune system, through the simulation of different number of multi node, the other algorithms are compared under the same conditions, the artificial immunity in this paper is confirmed—ant colony algorithm can effectively optimize the AGV path of artificial intelligent robot, and compared with other algorithms, it considerable improvements in energy and delay have been achieved.

References

J.Z.

Huang and

Y.W.

Cen , A path-planning algorithm for AGV based on the combination between ant colony algorithm and immune regulation, Advanced Materials Research422(16) (2017), 3–9.

Li ,

Dong ,

Li , et al., Study on robot path collision avoidance planning based on the improved ant colony algorithm.international conference on intelligent human-machine systems and cybernetics, IEEE, (2016).

Shen , Implementation of the AVG path planning based on the ant colony algorithms, Information Technology (2011).

Yue ,

Shen and

Zhu , Research on the mobile robots intelligent path planning based on ant colony algorithm application in manufacturing logistics, International Journal of Computer Science & Information Tedinolo (2014).

Y.B.

Hou ,

Y.Q.

Yuan and

B.P.

Li , Path optimization for automatic guided vehicle based on fusion algorithm of particle swarm and ant colony, Applied Mechanics & Materials182-183(2015), 1452–1457.

Z.W.

Sun ,

X.K.

Liu and

X.D.

Wu , et al., Path planning based on ant colony and genetic fusion algorithm for communication supporting spacecraft, Guangxue Jingmi Gongcheng/optics & Precision Engineering21(12) (2016), 3308–3316.

Liu .

Xiao and

X.Z.

Sha , The research on path planning of wall climbing robot based on ant colony algorithm and minimum gravity consumption algorithm, Applied Mechanics & Materials44-47(6) (2017), 414–424.

Wen ,

Zhang and

Liu , Path planning for laser navigation wheeled robots based on improved ant colony algorithm, Machinery & Electronics34(5) 2016), 73–76.

Zhu ,

Dong ,

Yan , et al., Research for the path planning of the agricultural robot based on the improved ant colony algorithm, Journal of Agricultural Mechanization Research (9) (2016), 48–52.

10.

Saidi-Mehrabad ,

Dehnavi-Arani ,

Evazabadian , et al., An ant colony algorithm (ACA) for solving the new integrated model of job shop scheduling and conllict-free routing of AGVs, Computers & Industrial Engineering86(C) (2014), 2–13.