Keywords

1 Introduction

The use of ‘Automated traversing’ object has increased in recent time. This automated traversing object could be a UAV or a mobile robot, which has to traverse a certain path for fulfillment of the purpose. It has wide applications in military missions, monitoring weather forecasting, traffic control, rescuing people and lot more. It may happen that UAV has to be used in a littered and obstacle-rich environment, for instance, in a metropolitan area and therefore, it is very much essential for a UAV to adopt a path planning mechanism to make sure that the path which is traversed by UAV should be free from collision and path length must be optimal [1]. One of the major problems in trajectory planning of these objects is that they have to traverse between the starting and the ending point, and there are chances that they may encounter a lot of obstacles and these obstacles can be fixed at one location or vary during the flight. To overcome the above problem, it is necessary to plan a path where automated objects could overcome the rough path, by optimizing and finding the feasible path.

This paper is based on planning the trajectory of automated traversing objects, in two-dimensional space, with the use of evolutionary algorithm. Over the last decade, evolutionary algorithms have emerged as very effective optimization and searching techniques. Evolutionary algorithms are a part of evolutionary computations and also belong to a group of modern heuristics-based search technique. As they have inherited the properties like flexibility and robustness from evolutionary computation, they can efficiently solve global optimization problems. In many applications, high complexity evolutionary algorithms have been used [2], such as Rathbun et al. [3] proposed an evolution based path planning algorithm for autonomous motion of a UAV through uncertain environments.

2 Evolutionary Algorithms

Path planning algorithms based on evolutionary algorithms use a population formed of possible solutions and gradually modify them to perform the stochastic search. The population is initialized randomly. At each step, various operations are performed upon the population. Then the cost function is used as a measure of fitness. Based on the fitness, population is either modified or selected for the next iteration. The same operations are repeated until stopping criteria are met. Figure 1 explains the basic working principle of evolutionary algorithms. It is not the best solution always, but an optimal solution, whose optimality can be increased, by modifying the control parameters, according to the complexity and scalability of the problem.

Fig. 1
figure 1

Working of evolutionary algorithms

Full size image

Table 1 depicts some of the evolutionary algorithms and inspirations from where they have been taken from.

Table 1 Name of evolutionary algorithms and from where they have been inspired by
Full size table

Genetic algorithm (GA) was coined in 1970 by John H. Holland and his student [2]. It was inspired by Charles Darwin’s theory of natural evolution. GA uses several operators such as crossover and mutation to get the solution to a problem. Particle swarm optimization (PSO) was coined in 1995 by James Kennedy [4]. The theory was inspired by the flocking of birds. It is a method where the problem gets the optimal solution by repeatedly trying to enhance the particle best solution with regard to a given measure of quality. Ant colony optimization (ACO) algorithm was developed by Marco Dorigo in 1992 in his Ph.D. [6]. He was inspired by the searching behaviour of ants, especially the pheromone communication between ants for finding the best path between the ants and the food source. Also, it helps us solve the problem which can be optimized for finding the best path. Differential evolution (DE) is a new heuristic approach for minimizing the nonlinear and non-differentiable continuous space functions [5]. DE was proposed by Rainer Storn in 1996 and was inspired by the theory of evolution. The extensive tests demonstrated that it converges faster with more accuracy than any other existing global optimization methods. Artificial bee colony (ACO) was developed by Dervis Karaboga in the year 2005, inspired by the searching behaviour of bees [7]. It commonly uses the parameters such as size of colony and cycle number should be maximum. It is an optimization technique that provides search on the basis of population procedure in which bees modify food’s positions with time and they discover places with food resources with higher amount of nectar. Social group optimization is a population-based optimization technique [9] which is motivated by the concept of humans’ social behaviour for solving a highly complex problem. It is observed that in the population-based category, social group optimization will enhance the class of effective and efficient evolutionary optimization techniques and will provide researchers a large scope to choose this in various problems and applications. Teaching–learning-based optimization was proposed by Rao et al. in 2011 [8]. Like other algorithms, it was also inspired by the effective guidance of the teacher on the performance by the students of the class. To get the global solution, TLBO uses a population (class of learners) of solutions so it also falls in the category of population-based method.

2.1 Application of Evolutionary Algorithm in Trajectory Planning

Evolutionary algorithms were inspired by the mechanism of how various species of nature interact and develop intelligence to solve their problem optimally. To maximize the function’s quality, a set of elements (possible solutions) are generated randomly in function domain. The quality function is now the fitness function which is applied to the main problem domain. On the basis of the fitness function, the candidates with best fitness value are selected or modified for the next generation. This is realized by applying some biological operators inspired by the biological processes. This is repeatedly done until the best solution is found.

A suitable fitness function can be defined for trajectory planning that can be optimized using evolutionary algorithm. The designing of fitness function is the main challenge and the crucial part for optimizing the path planning. Figure 2 depicts the application of evolutionary algorithms to path planning. Though we have some specific algorithms like ACO, which is specifically designed for path planning, we can also apply other evolutionary algorithms if we can design an appropriate fitness function because most of the evolutionary algorithms focus on optimizing the fitness function. The more optimal the fitness value is, the more optimized the trajectory will be. Table 2 shows some of the evolutionary algorithms used for trajectory planning in UAV, mobile robots, etc.

Fig. 2
figure 2

Working of evolutionary algorithms in trajectory planning

Full size image
Table 2 Evolutionary algorithms in trajectory planning
Full size table

Arantes et al. derived a heuristic approach for UAV path planning by using genetic algorithm under critical situation. The algorithm defines a new path to land UAV by considering all the constraints. Similarly, Atencia et al. solved complex multi-UAV problem by using multi-objective genetic algorithm [11]. It defined various hybrid fitness functions which satisfy the constraints and try to find the optimal solution by checking whether the solution is valid or not. Ghamry et al. with the help of PSO coined a forest fire fighting application by using multi-UAV [12]. The major challenge in firefighting mission was to carry out tasks with higher efficiency and efficiently minimize amount of time. In the similar manner, Phunga et al. enhanced more by considering vision-based surface [13]. The algorithm assumes the fire spots are pre-detect and by considering input constraints while surpassing UAV collisions during motion. Mirjalili et al. with the help of ant colony optimization (ACO) designed the trajectory planning for AUV [14]. It also included that the algorithm may all achieve the optimal path for UAV when the obstacle number is increased gradually from one number to many numbers. Similarly, Chen et al. considered path planning by avoiding the obstacles in path planning [15]. Pan et al. optimized the route planning of UAV by using artificial bee colony (ABCO) and also focused on saving memory [16]. Liu et al. also enhanced his approach by using ABCO by making the application of evacuation of crowd in buildings [7].

3 Conclusion and Future Work

There have been various approaches to find an optimal path while planning a trajectory, but solving it by using evolutionary algorithms makes the process simple and efficient. Evolutionary algorithms are easy to implement, simple, and time-efficient. Hence, they can be applied for real-time trajectory planning. There are several optimization algorithms which have not been used for trajectory planning till date. Figure 3 represents an approximate number of research works using some of the evolutionary algorithms taken from Google Scholar database (https://scholar.google.com/). Hence, application of other algorithms to this problem may serve as an emerging area of research.

Fig. 3
figure 3

Graph showing approximate number of research work based on some of the evolutionary algorithms

Full size image