Evolution is a widely used paradigm of computing that is finding an application in all domains. Evolutionary algorithms use an analogy from natural evolution to model the problem solving approach. They consist of a set of individuals that are the solutions to the problem and make a population pool. The various operators are used to modify the population pool of individuals. This consists of scaling, selection, mutation, crossover, and elite. Evolutionary algorithms are used for the problem of motion planning of the robots. Non-holonomicity is a major issue associated with mobile robots. The paths returned by the planners need to be smooth to ensure easy tracking by the robot control algorithms. The authors make use of BSplines and Bezzier curves to solve the problem. These are smooth curves that are controlled by the control points on the maps. Adaptation is another major aspect studied in evolutionary algorithms. The authors use evolutionary strategies to solve the problem of motion planning. These are self-adaptive in nature and are able to adapt the evolutionary parameters during optimization. Covariance Matrix Adaptation Evolutionary Strategy is the studied method of implementation.
TopIntroduction
Evolution is a major computing paradigm. Most of the problems that we see all around are fairly complex in nature. They have a lot many constraints that must be met. This makes it impossible for the conventional problem solving techniques to solve the problem and return the output within finite time. Hence, better techniques for solving these problems are required. The essence is that it may not be desirous for the solution generated to be perfect, but it is desirable for the solution to be returned within finite time. In this manner, we may convert an unsolvable problem to a solvable problem with some loss to the accuracy of the solution.
The evolutionary algorithms are inspired from the natural evolution process. All the individuals have different capabilities of acting and surviving in the world. The set of all the individuals is known as population. Different individuals in the population have different characteristics. All these individuals, however, compete with each other for survival. The basic philosophy comes from Darwin’s theory of survival of the fittest, which states that the individuals in a population that are most adaptive to change survive. Hence, the fittest individuals from a generation go to the next generation. They interact with the other fitter individuals and generate their offspring. The offspring are believed to be better than the parents as per the changing scenario or the environment. In this manner, evolution goes on and on. This evolution has resulted in the generation of different kinds of species that suit their environment and are able to survive well.
The evolutionary algorithms make the same analogy. Here the algorithm generates a number of random solutions to the problem. These solutions may solve the problem in different degrees that determines their fitness. Better solutions have better fitness values. The attempt is to carry forward changes in this set of individuals or population to make a higher generation population. The changes are carried out with the help of a number of genetic operators. These operators attempt to generate better solutions as possible for the next generation.
Optimization is a major problem of study for most of the problems. Optimization problems deal with maximization or minimization of a functional value, where the functional value changes as per some parameters. The optimization algorithm is supposed to find the correct set of parameters as well as the optimal (minimal or maximal) value of the function for this combination of parameters. Many problems that we see all around can be converted into optimization problems, and hence this class of problem is under heavy study. Evolutionary algorithms are extensively used for optimization problems. These become very valuable tools when the problem has too many parameters that need to be tuned, over which the performance of the function depends. Further, many times the function may not be differentiable and all derivative approaches that try to find a slope of the function to figure out the maxima or minima fail.
Genetic Algorithm is a member of the general class of evolutionary algorithms and is widely used for solving problems like optimization. While the conventional optimization problems only deal with simple parameter tuning, the genetic algorithm is able to perform a wider variety of tasks, one being the generation of the robotic path, which we shall be studying in this chapter. We look in detail regarding the working methodology, terms, and concepts of this algorithm and the manner in which it is used for solving the problem of robot motion planning in the following sections.
The problem of robot path planning can be easily stated to be a problem where the path of a robot is to be produced, given the source point, goal point, and the map. It may be seen that for every map a variety of paths may be possible. Some of these may be feasible while the others are infeasible. Infeasible paths mean that these do not reach from source to the goal without collision. Hence, these can never be used for the motion of the robot. The feasible paths may again be of variable lengths, depending upon the landmarks they use to reach the goal. Some paths may be using obvious routes to reach the goal, while others may be at some bigger routes. Further, the paths going through obvious routs may have different landmarks where they make a turn. These may go to different extents near or farther from the obstacle in their entire journey. Hence, there are always wide possibilities of paths from the source to the goal for any map. The optimal path that leads to the goal from the source may have any kind of shape. So far, the only intention is to have the path of the least possible length and the validity of the non-holonomic constraints as far as possible.