Robot Path Planning Using Cellular Automata and Genetic Algorithm
Subject Areas : Pattern Analysis and Intelligent SystemsZeynab Sedreh 1 , Mehdi Sadeghzadeh 2
1 - Computer Engineering Department, Dezfoul Branch, Islamic Azad University, Dezfoul, Iran.
2 - Mahshahr Branch, Islamic Azad University, Mahshahr, Iran.
Keywords: Optimal Routing, Cellular Automata, Robot Path Planning, Optimization Algorithms, Genetic algorithm,
Abstract :
In path planning Problems, a complete description of robot geometry, environments and obstacle are presented; the main goal is routing, moving from source to destination, without dealing with obstacles. Also, the existing route should be optimal. The definition of optimality in routing is the same as minimizing the route, in other words, the best possible route to reach the destination. In most of the routing methods, the environment is known, although, in reality, environments are unpredictable;But with the help of simple methods and simple changes in the overall program, one can see a good view of the route and obstacles ahead. In this research, a method for solving robot routing problem using cellular automata and genetic algorithm is presented.In this method, the working space model and the objective function calculation are defined by cellular automata, and the generation of initial responses and acceptable responses is done using the genetic algorithm.During the experiments and the comparison we made, we found that the proposed algorithm yielded a path of 28.48 if the lengths of the paths obtained in an environment similar to the other algorithm of 15 / 32, 29.5 and 29.49, which is more than the proposed method.
[1] Malboobi, M., Khademi, M., AkbarZade Tutunchi, M. and Rajabi Mashhadi, H., 2002. Routing Mobile Robot Using Genetic Algorithm. 10th Iranian conference on electrical engineering (ICEE), Vol.3
[2] Salaki, A. and Kufigar, H., 2014, Comprehensive Robot Motion Optimization Algorithm in the Presence of Obstacles based on Genetic Algorithm. 12th Iranian Conference on Intelligent Systems, Bam Institute of Higher Education
[3] Saadatpour, M., Noori Zehmakan, A., Eslahi, M., 2014. Robot routing with the common purpose using cellular automata. First National Conference on Electrical and Computer Engineering in the north of the country, Bandar Anzali, Moj Higher Education Institute.
[4] Saniei Abade, M. and Jebel Amelian, Z., 2015. Evolutionary Algorithms and Biosciences.
[5] Najafi, N., 2009. Using Multilayer Cellular Automata for Robot Routing. MS, Faculty of Basic Sciences, Shahed University.
[6] Masihi, E., Barzinpoor, F., Saedi, S., 2011. Routing a Moving Robot Using a New Method Based on Genetic Algorithm with Variable Variable Length. International Journal of Industrial Engineering and Production Management, University of Science & Technology, Vol. 22, No. 2, Page 100-111
[7] Galcernan, E., Carreras, M., 2013. A Survey on Coverage Path Planning for Robotics. University of Girona Underwater Robotics Research Center (CIRS).
[8] Behring, C., Bracho, M., Castro, M. and Moreno, J.A., 2001. An Algorithm for Robot Path Planning with Cellular Automata. Springer-Verlag London Limited, pp 11-19
[9] Chaudhari, Y. and Jena, S., 2016. Global Optimal Path Planning of Mobile Robot Using Genetic Algorithm. International Journal of innovative research in electrical, electronics, instrumentation and control engineering vol.4 , issue 5.
[10] Alpap Rashamwala , Deepika P Vinchurkar, 2013 , Robot Path Planning using An Ant Colony Optimization, International Journal Research in Artificial Intelligence (IJARAI),Vol.2 , No.3.
[11] Marchese, F., 1996. Cellular Automata in Robot Path Planing. IEEE Conferences, pp. 116-125
[12] Chen, j., Xie, Sh., Li, H., Luo, J. and Feng, k., 2015. Robot path planning based on adaptive integrating of genetic and ant colony algorithm. International journal of innovative computing, information and control, Vol.11, No.3, pp. 833-850.
[13] Wang, X.Y., Zhang, G.X., Zhao, G.B., Rong, H.N., Ipate, F. and Lefticaru, R., 2015. A Modified Membrane-Inspired Algorithm Based on Particle Swarm Optimization for Mobile Robot Path Planning. International journal of computers communications & control, Vol.10, No.5, pp. 732-745.
3
Journal of Advances in Computer Engineering and Technology
Robot Path Planning Using Cellular Automata and Genetic Algorithm
Abstract — In path planning Problems, a complete description of robot geometry, environments and obstacle are presented; the main goal is routing, moving from source to destination, without dealing with obstacles. Also, the existing route should be optimal. The definition of optimality in routing is the same as minimizing the route, in other words, the best possible route to reach the destination. In most of the routing methods, the environment is known, although, in reality, environments are unpredictable;
But with the help of simple methods and simple changes in the overall program, one can see a good view of the route and obstacles ahead. In this research, a method for solving robot routing problem using cellular automata and genetic algorithm is presented.
In this method, the working space model and the objective function calculation are defined by cellular automata, and the generation of initial responses and acceptable responses is done using the genetic algorithm.
During the experiments and the comparison we made, we found that the proposed algorithm yielded a path of 28.48 if the lengths of the paths obtained in an environment similar to the other algorithm of 15 / 32, 29.5 and 29.49, which is more than the proposed method.
Key Words— Robot Path Planning, Optimization Algorithms, Cellular Automata, Genetic Algorithm, Optimal Routing
I. Introduction
Following the ever-increasing advances in technology, the demand and the need to use mobile robots in various industries, and even the not-so-big-world businesses, have grown enormously. The importance of using such robots in moving objects in large environments, the use of hazardous materials and ... have led the researchers to consider ways to increase the efficiency and efficiency of such robots.
Mobile robots are widely used in various fields, especially those that are at risk for humans, such as space research, the nuclear industry, and the mining industry. In these applications, finding a reliable path for the robot is necessary for the robot's success.
Therefore, finding an appropriate routing algorithm for moving a robot from point to point and without interfering with obstacles in the environment is one of the important robotic necessities.
The optimal design of the robot's path is one of the most important and influential factors in determining the efficiency and efficiency of mobile robots. Therefore, various investigations have been carried out by researchers in this field. Each of these researchers has tried to get an optimal response to this problem by choosing the right method. This issue, especially on a large scale, has many complexities that cannot be solved by conventional optimization methods. For this reason, the use of intelligent algorithms for solving this problem has been of great interest to the researchers.
In this research, using the genetic optimizer algorithm and considering the limitations and parameters such as path softness (maintaining the path uniformity of the path), an attempt has been made to find an optimal solution to this problem. The Genetic algorithm is considered one of the most powerful optimization algorithms in the class of continuous class algorithms and is designed and presented with inspiration from inheritance rules.
In this research, along with cellular automata, a genetic algorithm is used which, by factoring in the slowness of the algorithm, Finding the shortest path possible, is considered as an optimality criterion; the purpose of this research is to identify the paths that are reliable. In other words, the goal is to provide the robot with a high precision, low-impact, and least cost barrier.
II. Express the issue
One of the issues that arise in the discussion of mobile robots is the issue of scheduling motion. The robot's routine planning is to find a sequence of moves for a robot in an environment with fixed or moving objects starting at a starting point and ending at an end without colliding with obstacles. In the planning problem of motion, the path to be achieved should be optimal. This criterion is defined according to the type of problem. Finding the shortest path possible, obtaining a path that the robot can reach as quickly as possible or creating a path that has the maximum possible distance from the obstacles are examples of different criteria of optimization.
Moving robotic routing methods can be divided into two types of on-line and off-line methods. In the off-line method, it is assumed that the shape and location of the obstacles in the robot's motion environment are known, and most of the off-line paths of the robot's motion environment are modeled by a graph, and then the robot's start and end points are added to this graph, In the next step, with general graph searching techniques, you can get the path that connects the starting point to the end point, and then transfer the path obtained in the graph to the robot's moving environment using existing methods.
In the routing method on the line, there is no information about the geographic location of the environment, the shape and position of the obstacles around it. In other words, global routing is based on the information received from the environment at the beginning of the search.
The algorithms used to guide a robot using a routine method include fuzzy methods, genetic algorithms, neural networks, or a combination of these methods.
The advantage of the on-line method is that it allows the robot to be guided in unknown environments such as spatial or oil spills that cannot provide a general mapping environment, but their disadvantages are compared to the algorithms out of line. The topic is due to the time it takes to identify the environment around the robot.
III. Robot Workspace Model
In a given issue, a robot is trying to reach its destination in an environment. In general, in each environment, three basic elements are considered: robot, deterrent factors (obstacle) and destination (goal). The robot tries to reach its goal at the least time and with the least distance. However, in all stages, the robot must minimize the amount of encounter with obstacles. Simply put, the environment can be considered as a network n×m, in which the robot moves from cell to cell. For example, Fig 1 shows a 5 × 5 environment with R robot and its obstacle.
Fig.1.Displaying an environment including Robot (R), Obstacle and Objective (G)
Given that the distance traveled by the robot in the real world, then the moving distance of a robot from one home to another is calculated in Euclidean form.
If it is assumed that the distance between each cell and neighbors adjacent to the horizontal and its vertical (neighbors 4, 3, 2, 1 in Fig 2) is 1, then the distance from the X to the other neighbors (cells 8, 7, 6, 5) is √2 according to Pythagoras.
Fig.2.Show the cell X and its neighbors
Obviously, the goal is to find the paths for the robot to reach the destination with the shortest path and the least possible obstacle encounter. Considering the nature of the cellular automaton network, the network environment can be considered as corresponding to a cellular automaton. Cellular automata is a discrete time dynamic, that is, at each time point, all cells simultaneously shift according to the transfer function. As a result, the target environment adapted to the cellular automata functions in such a way that all obstacles remain constant at each stage of time. The agent or robot moves on the basis of the transfer function, which is the main discussion of algorithms based on cellular automata.
IV. Allocation of labels to cells
In this way, we first assume that we want to reach the goal (G) to the robot (R). So move from point G to a row and assign a number to each cell. (Fig 3)
Fig.3.Cell numbering
V. weighing the grid
The network is converted into a weighted network so that the number corresponding to each home network shows the minimum distance from the desired target to the target regardless of the position of the robot.
The numbers of each cell begin to move, and the smallest distance between each cell and its neighbors is calculated to the nearest cell to the G point and allocated to that cell. As already mentioned, the distance between cells is calculated in Euclidean, so the distance between each cell and the other cell is 1 or 
.
The minimum distance from cell 1 to point G is 1. So the number 1 is assigned to this cell. The neighbors of cell 1 are cells 2 and 5. The closest cell to cell 2, which has the smallest distance with the point G, is cell 1. The distance between cell 2 and cell 1 is 1, so the total distance between cell 2 and the target point is 2.
Therefore, number 2 is allocated to cell 2. The closest cell to cell 5, which has the smallest distance with the G point, is also cell 1. The distance between cell 5 and cell 1 is. Therefore, the smallest distance from cell 5 to the target cell is the distance between the cell 5 and the cell 1, plus the distance between the cell 1 and the point G, which is + 1 + 2. Therefore, this value is assigned to cell 5 as the least distance to the target cell.
This process proceeds in the same way so that the minimum distance between all cells is determined by the target cell. This method is the same as weighing the grid. Fig 4 shows a weighted 5 × 5 grid.
Fig.4.Displaying a 5 × 5 grid in weighted mode
VI. How to move the robot in the environment
The robot can move in 8 directions to move from one cell to another adjacent to the cell, as shown in Fig 5. These robot motifs have been used in various articles.
Here, for faster convergence to the final point, only forward directions to the final point (here 1, 2, 3, and 4) are used. When the robot chooses one of the reverse direction directions (here 5, 6, 7, and 8), the value of the cost item will be fined.
Fig.5.Eight Movement Directions of the Robot
During the movement, the robot cannot enter the squares that are blocked, but because it is neglected, it can pass through obstacles in Fig 6.
Fig.6.The path allowed moving the robot between obstacles
The conditions outlined in Fig 6 will definitely occur at the edge of the two obstacles encountered, and with the consideration of the safety range mentioned, as well as the dimensions of the robot, such a move is allowed to be empty.
VII. cost Function
Given the robot's working environment and the barrier profile of the environment, it is necessary to determine the path through which the robot can at its lowest cost and without passing through the barrier cells from the point to the point Finalize.
The cost function to be minimized is considered as follows:
Cost = PL + PS (1)
PL: The path length traveled by the robot, or in other words, the number of paths from the starting point to the final point.
PS: The variable is related to the softness of the path. If a robot maintains its path to move from one cell to another, it will typically cost less than when it needs to be replaced. Changes related to these costs are stored in the variable PS.
In this case, the softness of the path is defined as follows: During the path, if moving from one cell to another, the direction to move with the previous direction is equal, the angle between the lines is zero, the value of 0.05 to the variable PS If the angle π / 4 is 0.25, if π / 2, then the value of 0.5, if 3π / 4 is 0.75 and if π (180 °) The value of 1 is added to the variable PS.
VIII. The objective function
After identifying the propositions and assumptions of the problem, the final target function is determined as follows and minimized by the genetic algorithm:
F=Cost × (1+β1×MeanVO+ β2×ViolationLength) (2)
So that:
Cost: The total length of the track and the path softness parameter
MeanVO: Mean violation of automatic movement (cell to cell movement)
ViolationLength: The violation caused by the length of the path traveled (the length of the traversed should not be less than the Euclidean distance of the robot and the target)
β2 and β1 are finite coefficients. Here, a value of 100 is assigned to each of them.
Obviously, the answers given are acceptable when the constraints mentioned are met. In other words, there is no violation. In such a situation, MeanVO and ViolationLength must be both zero. This issue has been monitored by a parameter called Acceptable. So that in each occurrence, in the case of zero infractions, the Acceptable value is equal to one and otherwise equal to zero.
IX. Problem Solving Method
The search engine is designed to create a path from a point that is considered as the starting point. Using the genetic algorithm, the initial responses are generated randomly, followed by subsequent generations. Then all populations are evaluated and the best and worst responses are stored. This step is done as follows:
1) Calculate the probability of selection (this section is used if the roulette wheel function is used to select parents).
2) Population generation by crossover method.
This process includes the following steps:
• Parents choosing one of the "Roulette wheel", "Tournament" and "Random" methods.
• Apply the crossover function to the selected parent
• Evaluation of the produced children resulting from the operation of the crossover function
3) Population generation by mutation method.
This process includes the following steps:
• Parent selection by random method
• Apply the mutation function to the selected parent
• Evaluation of mutated individuals
4) Integration of all three types of production (initial population, population derived from crossover and population from mutation).
When the condition for stopping the algorithm is established, the operation stops, and among the acceptable responses obtained in the previous step, the answer with the lowest value of the objective function is chosen as the optimal response.
The problem-solving diagram with the genetic algorithm is shown in Fig 7.
Fig.7.Flowchart of the Problem Solving Method with Genetic Algorithm
X. Provide results
After designing the model and connecting it to the genetic optimization algorithm, the program was implemented. Information about the parameters of the algorithm is given in Table Ⅰ. Information about the dimensions of the environment, the number of cells and the number of obstacles are also shown in Table Ⅱ. The schematic of the evaluated environment can be seen in (Fig 8).
Fig.8.Evaluation model in this research
Table Ⅰ: Adjustment Algorithm Parameters
Parameter | value |
Maximum number of replays | 3000 |
Population size | 20 |
Crossover rate | 0/8 |
mutation rate | 0/3 |
The condition for stopping the algorithm | Firstly acceptable. Second, the objective function is constant after 30 consecutive repetitions |
Table Ⅱ: Environmental Information
Parameter | Number |
Dimensions of the environment | 5 * 5 |
The total number of cells | 25 |
Number of obstacle | 5 |
Dimensions of each cell | 1 * 1 |
Euclidean distance between robot and target | 66/5 |
Given that the genetic algorithm (in general, meta-algorithms) yields random answers, different responses are obtained at each run. Usually, in order to evaluate the responses generated by such algorithms, the algorithm is executed at different times (usually 10 times), and then, based on the best answer (or the average of the answers given), the results are analyzed and evaluated.
Here, the algorithm was executed ten times to evaluate the algorithm's performance. Table Ⅲ lists the results of the program for 10 runs. In Table Ⅲ, the status of acceptable responses is also mentioned. Acceptable responses are responses that are obtained for adherence to problem constraints.
Table Ⅲ: The result of the genetic algorithm in multiple Performances
Run number
| Iteration | path length | Path Softness | Objective function value |
1 | 4067 | 6.24 | 6.75 | 12.99 |
2 | 1328 | 6.24 | 6.75 | 12.99 |
3 | 4753 | 6.24 | 7 | 13.24 |
4 | 5271 | 6.82 | 8 | 14.82 |
5 | 532 | 6.24 | 6.75 | 12.99 |
6 | 1125 | 6.24 | 6.75 | 12.99 |
7 | 1508 | 6.82 | 8 | 14.82 |
8 | 1117 | 6.24 | 6.75 | 12.99 |
9 | 89 | 6.24 | 6.75 | 12.99 |
10 | 160.5 | 6.24 | 6.75 | 12.99 |
Based on the data from Table Ⅲ, the result of the implementation of the ninth best (optimal) response is presented. The convergence process of the algorithm and the path graph for the ninth performance (which has the best results out of 10 runs) are shown in Figures 9 and 10 respectively.
In Fig 10, the coordinates of the location of obstacles with yellow squares, the coordinates of the starting point with the green point, the coordinates of the target point with the red circle and the other points of the path are shown with white circles.
Fig.9.Algorithm convergence process for the number of times the algorithm is executed for best execution
Fig.10.The path graph is based on the response obtained from the best execution of the algorithm (implementation of ninth, table Ⅲ)
XI. Conclusion
In this research, we examined the problem of routing robotics. We proposed an algorithm based on cellular automaton and genetic algorithm. By analyzing the proposed algorithm with the genetic algorithm, we find that the proposed algorithm has a better performance than the genetic algorithm.
Based on the results of the implementation of the algorithm, the path length obtained using the proposed algorithm is less than the length of the paths presented by the combined methods of the genetic algorithm.
Future work can be carried out on a multi-player multi-robot pathway by combining genetic algorithms and cellular automata, in which the issue of the non-occurrence of robots with each other and the goal of reaching all the robots is raised.
References
[1] Malboobi, M., Khademi, M., AkbarZade Tutunchi, M. and Rajabi Mashhadi, H., 2002. Routing Mobile Robot Using Genetic Algorithm. 10th Iranian conference on electrical engineering (ICEE), Vol.3
[2] Salaki, A. and Kufigar, H., 2014, Comprehensive Robot Motion Optimization Algorithm in the Presence of Obstacles based on Genetic Algorithm. 12th Iranian Conference on Intelligent Systems, Bam Institute of Higher Education
[3] Saadatpour, M., Noori Zehmakan, A., Eslahi, M., 2014. Robot routing with the common purpose using cellular automata. First National Conference on Electrical and Computer Engineering in the north of the country, Bandar Anzali, Moj Higher Education Institute.
[4] Saniei Abade, M. and Jebel Amelian, Z., 2015. Evolutionary Algorithms and Biosciences.
[5] Najafi, N., 2009. Using Multilayer Cellular Automata for Robot Routing. MS, Faculty of Basic Sciences, Shahed University.
[6] Masihi, E., Barzinpoor, F., Saedi, S., 2011. Routing a Moving Robot Using a New Method Based on Genetic Algorithm with Variable Variable Length. International Journal of Industrial Engineering and Production Management, University of Science & Technology, Vol. 22, No. 2, Page 100-111
[7] Galcernan, E., Carreras, M., 2013. A Survey on Coverage Path Planning for Robotics. University of Girona Underwater Robotics Research Center (CIRS).
[8] Behring, C., Bracho, M., Castro, M. and Moreno, J.A., 2001. An Algorithm for Robot Path Planning with Cellular Automata. Springer-Verlag London Limited, pp 11-19
[9] Chaudhari, Y. and Jena, S., 2016. Global Optimal Path Planning of Mobile Robot Using Genetic Algorithm. International Journal of innovative research in electrical, electronics, instrumentation and control engineering vol.4 , issue 5.
[10] Alpap Rashamwala , Deepika P Vinchurkar, 2013 , Robot Path Planning using An Ant Colony Optimization, International Journal Research in Artificial Intelligence (IJARAI),Vol.2 , No.3.
[11] Marchese, F., 1996. Cellular Automata in Robot Path Planing. IEEE Conferences, pp. 116-125
[12] Chen, j., Xie, Sh., Li, H., Luo, J. and Feng, k., 2015. Robot path planning based on adaptive integrating of genetic and ant colony algorithm. International journal of innovative computing, information and control, Vol.11, No.3, pp. 833-850.
[13] Wang, X.Y., Zhang, G.X., Zhao, G.B., Rong, H.N., Ipate, F. and Lefticaru, R., 2015. A Modified Membrane-Inspired Algorithm Based on Particle Swarm Optimization for Mobile Robot Path Planning. International journal of computers communications & control, Vol.10, No.5, pp. 732-745.