Intelligent Mining for Path Planning using Evolutionary Algorithms and Artificial Neural Network for UAV

Intelligent Mining for Path Planning using Evolutionary Algorithms and Artificial Neural Network for UAV

Ramya Srinivasan Manjula K

1. ech(CSE), Dept of CSE, Asst Professor, Dept of CSE Don Bosco Institute of Technology Don Bosco Institute of Technology

   Bengaluru, India Bengaluru, India

   Abstract: Planning a path for unmanned aerial vehicle system is a huge task as it been adjusted automatically. As thing has to been controlled automatically the system must be designed as path must be planned for the aerial vehicle. To solve the problem by finding the solution for path by using optimization technique to avoid the obstacle which is been located during path planning for unmanned aerial vehicle. This optimization problem for path planning for unmanned vehicle is been achieved by using global optimization tool called Genetic Algorithm which is used greatly for all purpose. The Evolution algorithm which will help us find the best solution, Genetic algorithm and Memetic algorithm is used for find optimized path for UAV.

   Artificial Neural Network will help in fitting function fast and quick, it will get an approximately any function. Genetic Algorithm is very efficiently used for globally optimum solution from one generation to another generation. Each new generation will get better and better result than previous generation. Neural network will work quickly and fast when compare to genetic algorithm, but neural network is only for local optimum than global optimum.

   In this paper a new technique for path planning by combining evolution algorithm such as Genetic algorithm and Memetic algorithm. Artificial Neural Network which is a proposed system with the conventional output generated by both evolutionary algorithm, which is optimized data let for training in to neural network for modeling an unmanned aerial vehicle. The result produced is optimized fast data.

   Keywords: Unmanned Aerial Vehicle, path planning, Genetic Algorithms, Memetic Algorithm, Artificial Neural Networks, Evolutionary Algorithms

   1. INTRODUCTION

      An Unmanned Aerial Vehicle (UAV), commonly known as drone is an aircraft which does not have a human pilot onboard. Its flight is regulated either automatically using AI techniques employed in its onboard computers or by the remote control of the pilot in the ground or in some other vehicle. UAVs are usually used in military and special operations but can also be used in a large number of civil applications like policing, firefighting areas where floods, earthquake and other natural or manmade disasters have occurred. Their importance can never be ignored in rescuing operations and military war fields where there is a great danger to human life. UAVs can also be used in

      surveillance operations, where scrutiny of an area can be done with UAV.

      For movement form one position to another position safely, the UAV needs to avoid the obstacles coming in its path and take an alternate path through which the UAV can travel safely and also care must be taken that it takes shortest path from all the available options. Secure and impressive path planning techniques are usually made by solving the optimization problems . The problem of path planning in UAV can be viewed as a path planning in robotic navigation.

      With the advent in computational intelligence research area so many methods of path planning for obstacle avoidance in robotic navigation have been proposed. Among them Evolutionary Algorithms are used to form the strategy of path planning in a natural manner. In a[3] technique has been presented for UAV path planning in an adversarial environment in which Genetic Algorithms based optimization techniques are used to plan a path which is shortest in length and distance of UAV from maximum obstacle. The obstacle can be radar.

      As compared to other similar approaches for path planning, the Genetic Algorithms try to find the solution for a given problem in a globally optimum way instead of converging early to local optima. It means Genetic Algorithms (GA) knows how to sacrifice short term benefits for long term benefits. Global optimum solution means best solution and local minimum mean solution which seems to be better than currently available solutions but some other solution may exist in the solution space which could be better than the current solution.

      Genetic Algorithms use operations like selection which is the process through which the elite or best solutions are selected at each generation and then the crossover operation is performed in which the parts of two or more different solutions belonging to the same generation are interchanged with each other to form a new solution. After that the mutation operation is performed in which some parts of the solution are replaced by new solution for introducing the diversity in the population. The idea is that the newly formed population at each generation is better

      than their previous generation which is formed as a result of applying the genetic operators namely selection, crossover and mutation.

      The proposed system based on Genetic relation augmented with local search using Memetic algorithm, increases the accuracy in retrieving exact and related information. The algorithm proposed in consists of several steps: initial set of population is generated randomly consisting of several solutions. Here the solution is the path which the UAV can follow to move from one position to another position safely. The chromosome represents a path. A gene represents a waypoint of path. Then various solutions are analyzed in terms of their fitness value and then crossover and mutation operations are applied which results in new set of solutions which are nothing but the new generation of solutions which is assumed to be better than its previous generations.

      Artificial Neural networks (ANN)[1] are used in association with the computer industry since 1950s. Neural Networks are capable of performing sophisticated computational tasks like fitting of a function, pattern recognition, associative recall and learning[4]. ANN imitates human brain where the information is stored in the form of interconnections between several neurons which constitute memory of a person shown in figure1.

      An ANN is shown in Fig.2.The ANN is set for solving a specific problem through a learning process in which the weights of links between different neurons are adjusted so as to map the input to the target and once the neural network is trained it can be used for obtaining the output for unknown inputs also. Each link which connects the neurons is associated with some weight which specifies the strength of interconnection of neurons. The set of weights for links constitute the memory.

      The weights of links connecting the neurons are adjusted during the training process so that when the input is given the output generated can be matched to the desired output.

      This process is known as training the Artificial Neural Network. The training can be supervised, unsupervised or reinforced

   2. GENETIC ALGORITHM, NEURAL NETWORK AND PATH PLANNING FOR UAVS

      The GA finds the solution of a given problem which is in the form of a fitness function which has to be minimized. So GA attempts to find the minimum value of the variable for which the entire fitness functions value is found to be minimum in a globally optimum way. That means it finds the value of variables involved in the fitness function so that the value of the function obtained is minimum.

      The idea is that if the fitness function is made to be the total length of the path, then GA will attempt to minimize the lengt of the path following the constraints that path should have maximum distance from the obstacle. For optimization and hence finding the solution for a given fitness function, the GA starts from the initial set of population which could be far away from the globally optimum solution.

      Fig.2. Internal Layered Architecture of ANN [3].

      The initial population is generated randomly based on the given linear, non-linear and bound constraints. Then three operations of selection, crossover and mutation are performed over the population consisting of set of solutions and then the new set of solutions is produced which is assumed to be better than the previous generations. The process is repeated many times till the final solution is arrived which is also known as the final generation .

      In case of UAVs path planning problem, the solution is the path from the initial position to the goal position. Each path is consisting of intermediate waypoints which are called the genes. The collection of genes or waypoints which make a path is called a chromosome. At any given generation, the population consists of set of chromosomes

      or paths. The GA works by employing the operators to produce new paths which are assumed to be better than the previous set of paths from the previous generation .

      1. Initial population

         The population at any generation for the Genetic Algorithm consists of some paths which are known as a set of solutions or chromosomes made up of way points which are joined together to form a path. The initial set of paths generated stochastically constitutes initial population. The initial population is created randomly based on the given linear, nonlinear and bound constraints imposed to the Genetic Algorithm. The initial population can be far away from the final global optimum set of solutions or chromosomes of final generation. The Unmanned Aerial Vehicle begins to move along the straight line and continues its movement as long as it doesnt perceive the radar signals, but once it perceives the radar signals it starts generating the initial set of population which consists of paths which are away from the radar but their length may not be globally minimum till the final generation of population.

      2. Evaluation

         Each of the generated paths is evaluated in terms of its fitness value which is found to be in direct proportion to the distance from the radar and inversely proportional to the total length of path from the initial position to the goal position.

         n-1

         Length(p)= l(wpi,wpi+1) = (1) i=1

         Where Length(p) denotes the total length of the path p,l(wpi,wpi+1) is the length of line segment from neighboring waypoint wpi to wpi+1 in the path.

         Obstacle(p)=distance of the path(p) from the obstacle

         =(2)

         The fitness is computed as follows:

         Fitness(p)=w*obstacle(p)/length(p) =(3)

         Equation (3) indicates that fitness of the function must be directly proportional to distance of the UAV from the obstacle and inversely proportional to the total length of the path from initial to the final position.

      3. Operators

      Selection operator takes the decision regarding which paths in the solution should survive and participate in other operations like crossover and mutation in order to form the new set of paths which will be the part of population of new generation. Crossover operator selects two paths in the population of a generation, then it combines some portion

      of one path by some portion of another path i.e. it mixes some portions of two different paths to generate a new path

      . Crossover can take the form of a single point or multipoint crossover where single or multiple portions inside path are selected for crossover operation.

      Mutation operation changes the values of some genes in the chromosome in order to bring some diversity in the population otherwise the newly generated generation of population will be similar to its previous generation. After the application of the aforementioned three operations viz. selection, crossover & mutation the resulting population could be expected to be better than its previous generation of solution in terms of satisfying the fitness function specified in (3).

      The GA applies the above three operators for finding the path whose length is global minimum and the distance from the obstacle is maximum or at least the path should let the UAV avoid the obstacle which is found when a straight line is assumed as a path from initial to goal position. Fig.3 describes the process by which the GA finds the solution for path planning problem of UAV. Artificial neural networks can fit a function well. If input and target data are given as an input to the ANN, it can approximate the function and produce the results as if it has been produced by the function itself which it is approximating. This is the case of supervised learning. ANN can produce the results fast comparative to Genetic Algorithms but may converge to local optimum instead of global optimum.

      Fig.3. Genetic Algorithm and Neural Network flow for Path Planning

      So using the results produced from the GA to train the ANN is a good alternative for finding solutions fast which are globally optimum, as the data set is generated by the Genetic Algorithm so it will be globally optimum & training of ANN is done through the globally optimum data so ANN can be

      made to learn how to find the solutions which are globally optimum fast.

      The UAV assumes that the straight line connecting the initial and goal position is minimum in length so it starts its movement along that straight line only. When the onboard sensors in the UAV

      perceive that there is radar in its path, which is obstacle in this case [1], then GA starts working as shown in Fig.2 as follows:

      Step 1: Generation of Initial Individuals- The generation of initial individuals which constitutes the first generation of population is done stochastically but they may not be regarded as perfect in terms of satisfying the fitness function criteria specified in (3).

      Step 2: Evaluation- The paths or chromosomes generated in step 1 are tested in terms of fulfillment of their fitness function criteria as specified in (3).

      Step 3: Ranking-The paths of the population generated in step 2 are ranked according to their fulfillment criteria of fitness function of (3).

      Step 4: Selection- Here the top ranked paths are selected ignoring the low ranked paths as the top ranked paths are assumed to be fit than low ranked paths.

      Step 5: Crossover- Here two or more paths are selected from the generation and their portions i.e.

      waypoints are interchanged to form new path.

      Step 6: Mutation- Here some waypoints of the paths are changed to introduce the diversity in the population in such a way that the obtained path is found to be better in terms of fulfillment of fitness criteria specified in (3).

      Stopping criteria: This is the condition at which the GA stops performing further operations and produces the population of final generation as output. There can be several reasons some of which are maximum number of generation specified reached, time limit, fitness limit, stall generations, stall time limit, function tolerance, non-linear constraint tolerance.

      Step 7: Generate the Output- The final generation of population is considered to be the output generated from GA. The above algorithm is run several times with different feasible inputs to get the outputs and all the input and their respective output values are stored separately to train the ANN at step 9.

      Step 8: Create the Neural Network- The neural network is created with input, hidden and output layers which best suits to solve the problem [5].

      Step 9: Train the Neural Network-The ANN created at step 8 is trained with data set generated above.

      The output generated from the Genetic Algorithms is found to be globally optimum [2]. So the output generated from the Genetic Algorithm can be used as a trainingdata set for the Artificial Neural Networks, so that the ANN will also start producing the optimal solutions.

   3. IMPROVED APPROCH USING MEMETIC

      ALGORITHM

      MAs are similar to GAs but the elements that form a chromosome are called memes [2], not genes. The unique aspect of the MAs algorithm is that all chromosomes and off springs are allowed to gain some experience, through a local search, before being involved in the evolutionary process. From the algorithm procedure of Memetic Algorithm (MA), we can observe that the parameters involved in MAs are the same four parameters used in GAs: population size, number of generations, crossover

      rate, and mutation rate m addition to a local search mechanism.

      So using the result produced from the local search (Memetic algorithm) and GA to train the ANN is a good alternative for finding solutions fast which are globally optimum, as the output data set which is generated by the Genetic Algorithm so it will be globally optimum & training of ANN is done through the globally optimum data so ANN can be made to learn how to find the solutions which are globally optimum fast.

      UAV, In which the connection between the initial and goal position is minimum in length so it starts its movement along that straight line only. When the onboard sensors in the UAV perceive that there is radar in its path, which is obstacle in this case, then GA starts working as shown in Fig.4 as follows:

      Step 1: Generation of Initial Individuals- The generation of initial individuals which constitutes the first generation of population is done stochastically considering random variables.

      Step 2: Local search [2] The values obtained output generated from step 1, by initial individuals an simple local search is done to select an data set to evaluation.

      Fig.4. Evolutionary Algorithm(MAs AND GAs) and Neural Network flow for Path Planning.

      Step 3: Evaluation- The paths or chromosomes generated in step 1 are tested in terms of fulfillment of their fitness function criteria as specified in equation(3).

      Step 4: Ranking-The paths of the population generated in step 2 are ranked according to their fulfillment criteria of fitness function of equation (3).

      Step 5: Selection- Here the top ranked paths are selected ignoring the low ranked paths as the top ranked paths are assumed to be fit than low ranked paths.

      Step 6: Crossover- Here two or more paths are selected from the generation and their portions i.e. waypoints are interchanged to form new path.

      Step 7: Mutation- Here some waypoints of the paths are changed to introduce the diversity in the population in such a way that the obtained path is found to be better in terms of fulfillment of fitness criteria specified in equation(3).

      Stopping criteria: This is the condition at which the GA stops performing further operations and produces the population of final generation as output. There can be several reasons some of which are maximum number of generation specified reached, time limit, fitness limit, stall generations, stall time limit, function tolerance, non-linear constraint tolerance.

      Step 8: Generate the Output- The final generation of population is considered to be the output generated from GA and MA. The above algorithm is run several times with different feasible inputs to get the outputs and all the input and their respective output values are stored separately to train the ANN at step 10.

      Step 9: Create the Neural Network- The neural network is created with input, hidden and output layers which best suits to solve the problem.

      Step 10: Train the Neural Network-The ANN created at step 9 is trained with data set generated above

   4. SIMULATION

      The implementation is done through simulation using v Realm Builder tool in MATLABR2012b. All the simulations are performed on a computer with 4GB RAM and 2.20GHz Pentium core2 Duo processor. The operating system used is windows7 operating system. The above discussed evolutionary algorithm(GA,MA) and neural network is implemented in MATLAB R2012b.

      Let us assume that it belongs to a security application, i.e. military UAV searching task, the UAV starts flying from its initial position to the goal position along the straight line connecting initial and goal position without assuming there exist some obstacle in its path. Here radar is considered to be an obstacle . A straight line from initial to goal position is supposed to be the path with minimum length without obstacle.

      UAV continues moving along the straight path till the onboard sensors of UAV detect the radar. Then the Genetic Algorithm

      is called to find an alternate path satisfying the fitness criteria of (3). Here the number of intermediate waypoints is taken to

      be three, if the number of intermediate waypoints is increased, more smooth path can be generated i.e. the smoothness of curve and perfection of path are directly proportional to the number of intermediate waypoints in the path. It means with increase in the number of waypoints which makes the path can lead to better solution. Here the UAVs movement is in 3D environment.

      Fig.5a shows the UAV front position ,fig 5b: UAV moving along initial position, Fig.5c shows the UAV to be moving towards right from initial to final position, and Fig.5d, Fig5e showns the movement of path planned using all the above evolutionary algorithm fig5f. the UAV to its final position. This path is planned by using the evolutionary algorithm optimized data into the trained neural network for fast and optimized function.

      FIG 5a: Front View

      FIG 5b: Top View with left movement

      FIG 5c: Top View with right movement

      FIG 5d: Top View with straight position

      FIG 5e: Top View, reaching initial position

      FIG 5f: Top View, back with initial position

   5. CONCLUSIONS

In this paper, a novel and efficient method based on Genetic Algorithms and Artificial Neural network is presented for path planning of UAV, for avoiding the obstacle which is radar in this case. The output obtained from the Genetic Algorithms has been successfully used to train the Artificial Neural Networks and its performance in all the cases is realized using simulations in 3D. It is found that the above approach of training the Neural Networks using the output of Genetic Algorithms can let the UAV plan its path faster and better as compared to using GA alone. The future scope of this research can include multiple UAVs communicating with each other during a mission for sharing of information regarding obstacle

I. REFERENCES

1. DR. YASHPAL SINGH, ALOK SINGH CHAUHAN Neural Networks In Data Mining2010

2. Si-Yao Fu Li-Wei Han ; Yu Tian ; Guo-Sheng Yang Path Planning For Unmanned Aerial Vehicle Based On Genetic Algorithm2012

3. Ms. Surekha More ,Ms. Ujwala BharambeIntelligent Web Mining Technique Using evolutionary Algorithms

4. Si-Yao Fu, Li-Wei Han, Yu Tian, and Guo-Sheng Yang, Path Planning for Unmanned Aerial Vehicle based on Genetic Algorithm, Proc. 11th IEEE Int. Conf. on Cognitive Informatics & Cognitive Computing, 2012

5. J. David Schaffer, Darrell Whitley, Larry J. Eshelman, Combinations of Genetic Algorithms and Neural Networks; A Survey of the State of the Art, IEEE, 1992.

6. Ms.Dharmistha, D.Vishwakarma, Genetic Algorithm based Weights Optimization of Artificial Neural Network, International Journal of Advanced Research in Electrical, Electronics and Instrumentation Engineering. Vol.1, issue 3, August 2012.

7. S. Thrun, Bayesian landmark learning for mobile robot localization, Machine Learning, vol. 33, no.1, pp. 41-76, 1998.

8. Imran Shafil, Jamil Ahmad2, MIEEE, Syed Ismail Shap, Sr. MIEEE, and Faisal M Kashif3, Impact of Varying Neurons and Hidden Layers in Neural Network Architecture for a Time Frequency Application, IEEE, 2006.

9. E. Lawler, A. Rinnooy, J. Lenstr,. The traveling salesman prblem: a guided tour of combinatorial optimization, John Wiley and Sons, 1985.