A new evolving mechanism of genetic algorithm for multi-constraint intelligent camera path planning

Abstract

The main goal of intelligent camera path planning is to determine an optimal pathway that proceeds from the starting position to the target position under several constraint conditions in the given environment. Genetic algorithm-based method has found wide application in path optimization problem in the intelligent camera community recently. Because the roaming environments are very complex, the planning path of the intelligent camera should meet other constraint conditions in addition to the path length constraint and the obstacle-free constraint. In this study, a new fitness function was developed in the genetic algorithm, which can consider the constraint conditions in terms of free obstacle, path length, path smoothness, and the visibility of the objective of interest in advance during the camera roaming. In addition, a new evolving operator was introduced into the genetic algorithm, so that the number of iteration can be significantly reduced, and thus, the efficiency of the genetic algorithm can be improved. Experimental results show that the proposed genetic algorithm can obtain a high-quality path under multi-constraint conditions for intelligent camera with less numbers of iteration as compared with several conventional methods.

1 Introduction

With the rapid development of artificial intelligence, scientific visualization has attracted increasing attentions in many fields, which include chemistry, medicine, astronomy, and agriculture, etc. Over the past decades, many researches have been conducted to improve scientific visualization (Bryson 1996; Liang and Li 2008; Pierre and Zakaria 2011; Wang and Tao 2017). Intelligent camera control, first introduced by Drucker and Zeltzer (1994), is the core issue of scientific visualization, which aims to plan an optimal pathway from the starting position to the target one in order to meet several constraint conditions. Although there exist a number of researches on the path planning problem in the literature, path planning is still a main subject of scientific visualization and deserves further investigation in the future.

It has been reported that path planning problem is a NP-hard optimization one (Srinivas and Patnaik 1994; Kuang et al. 2006; Manikas et al. 2007), which can be only solved by heuristic algorithms (Chaudhari et al. 2017; Liu et al. 2017; Contreras-Cruz et al. 2015; Sahoo et al. 2018; Tharwat et al. 2019). In recent years, the membrane algorithm area is focusing on developing new variants of heuristic algorithms for solving complex optimization problems, including the motion planning problem in robotics, by using either the hierarchical or network membrane structures, evolution rules and computational capabilities of membrane systems (Wang et al. 2015; Zhang et al. 2017; Perez-Hurtado et al. 2018, 2020). Among these heuristic algorithms, the genetic algorithm has been proved to be an effective and popular method to deal with the path planning problem. Nowadays, a variety of algorithm-based methods have been proposed to solve the path planning problem (Hu and Yang 2004; Pol and Murugan 2015; Song et al. 2016; Elhoseny et al. 2018; Patle et al. 2018; Nazarahari et al. 2019). For example, Ali et al. (2005) employed the genetic algorithm to determine the collision-free path of manipulators and found that the genetic algorithm works better than the conventional A* method in terms of path length and computation time. Karami and Hasanzadeh (2015) designed a novel selection operator for a new adaptive genetic algorithm in order to maintain the diversity of individuals and escape from the local optima. And they confirmed that their algorithm outperforms the related methods in terms of solution quality and finding an optimum path based on the experimental results. Lee and Kim (2016) proposed an effective initialization method for genetic algorithm with variable-length chromosomes for robot to find a feasible path without intersecting any obstacles in the given environment. The results reveal that the proposed initialization method can effectively improve the performance of the genetic algorithm. Despite a lot of interesting achievements on the genetic algorithms for path planning, researches on the improvement of path planning by the genetic algorithm-based methods have never cease. One of the reasons lies in the fact that many existing genetic algorithms require huge execution time in order to find a high-quality path. Therefore, in order to promote the application of genetic algorithms on the path planning problem, it is of necessity to conduct studies on the genetic algorithms in terms of their efficiency.

The optimal solution of the path planning problem determined by genetic algorithms refers to the one that can satisfy certain constraint conditions, e.g., the planning path is the shortest among all the feasible cases or it won’t pass through any obstacles in the working field, etc. Up to now, lots of genetic algorithms have been put forward for path planning problem, and most of them focused on the optimization of path planning under a single constraint condition. Researches on the path planning problem under multi-constraint condition are relatively limited (Ahuactzin et al. 1991; Xiao et al. 1997; Wang et al. 2004; Zhou et al. 2008; Mou et al. 2008). In fact, the roaming environments are very complex, so the planning path of the intelligent camera should meet other constraint conditions in addition to the path length constraint and the obstacle-free constraint. For example, a sharp turn must be avoided during the roaming process of the intelligent camera, and the planning path should be as smooth as possible in order to minimize the dizziness effect. Besides, the objective of interest should enter the vision field as soon as possible, so that the user can experience a pleasant interaction with the objective during the roaming process. Although several studies have been conducted to investigate the multi-constraint optimization of path panning (Brindle 1980; Vadakkepat et al. 2000; Ahmed and Deb 2013; Ramirez-Atencia et al. 2017; Nazarahari et al. 2019), this issue is far from being fully solved since the constraint conditions are complex and will vary with the working field (e.g., UAVs, vehicles, and robots). Therefore, in order to obtain the optimal path under the constraint conditions in real-life situation, it is important to study the path planning of intelligent camera under the multi-constraint condition.

The purpose of this study is to propose a new path planning method by introducing an evolving operator, with the aim to reduce the number of iteration and improve the efficiency of the genetic algorithm. In addition, a new fitness function is developed for the proposed method, so that the optimized path can satisfy the multiple constraint conditions, i.e., (1) the path is obstacle-free, (2) the objectives can enter the vision field of camera as soon as possible, (3) the path is relatively short, and (4) the path is smooth enough to reduce the dizziness effect during the roaming process. The rest of this paper is organized as follows: Section 2 presents a brief introduction about how to conduct path planning by genetic algorithm. The new fitness function to characterize the multiple constraint conditions and the new evolving operator to improve the efficiency of the genetic algorithm during the path planning are described in Sect. 3. In Sect. 4, we will introduce the experimental settings of the numerical tests and compare the simulation results by our algorithm with those by some of the state-of-the-art methods. Finally, the main findings are summarized in Sect. 5.

2 Path planning with genetic algorithm

As a natural-inspired algorithm, genetic algorithm was developed based on the concept of Darwinian evolution. Genetic algorithm is a kind of random search and optimization algorithm similar to the evolution of biological population, which involves an initialization method, fitness function, natural selection, crossover, and mutation operators. In genetic algorithm, an initial population is generated randomly. In order to obtain the optimal solution of the problem, the quality of each chromosome in the population is evaluated by a fitness function. Then, the parents will be selected to be subjected to the reproduction according to their fitness values. Crossover is applied to produce new offspring based on the selected parents in the previous step. The genetic structures of some chromosomes will be changed by the mutation operator in order to guarantee the diversity of the population. The genetic algorithm will be stopped until the optimal solution is determined, i.e., the stopping criteria are satisfied (Sugisaka and Fan 2001). The pseudo-code of genetic algorithm is shown in Table 1.

Table 1 Pseudo-code of genetic algorithm for path planning

2.1 Representation of environment

During the process of path planning, the intelligent camera will interact with the virtual environment to determine the optimal pathway. Therefore, it is necessary to represent the environment by a model that can be identified by the intelligent camera. Recently, several models including grid-based model, polygon model, and the cell tree have been used to represent the environment (Lamini et al. 2018). In this study, the grid-based model, one of the most widely used models, was used to characterize the environment due to its good performance and easy implementation. Figure 1 shows a typical environment during the roaming of the intelligent camera and the corresponding grid-based model. As shown in Fig. 1c, the working space of the intelligent camera is represented by an even numbered grid. All the positions in the grid can be divided into two categories: One is the vacuum space that enables the intelligent camera to move freely, while the other is obstacle zone (black zone shown in Fig. 1c) where the intelligent camera cannot go through. Obviously, a feasible solution of the path planning problem is the pathway from the starting position to the target position that crosses a set of obstacle-free positions.

Fig. 1

Typical roaming environment of intelligent camera and the corresponding grid-based model

2.2 Encoding of paths (chromosomes)

In the genetic algorithm, each path corresponds to one chromosome. The choice of encoding of chromosomes is a very important step for the successful implementation of the genetic algorithm. It has been reported that different methods can be used to encode the pathway, which depends on the path planning problem to be solved (Lamini et al. 2018). The binary encoding method is one of the most widely used methods. However, we employed an orderly numbered method to encode the paths since it is simpler in form and easier to be operated by genetic operator. In the orderly numbered method, each position in the grid-based model can be represented by a unique number. For example, P = {p₁, p₂, p₃, …, p_n} denotes a path from the starting position (p₁) to the target position (p_n) in the grid-based model. p_i is the ith point on the pathway. More detailed descriptions about the orderly numbered method can refer to the reference (Adem and Mehmet 2012). It is noted that in this study, the length of paths is variable. The optimal path should be as short as possible in addition to satisfy other constraints of the path planning problem.

2.3 Initialization of population

The efficiency of the genetic algorithm is greatly influenced by the initial population. An efficient initial population method can improve the search effectiveness of the genetic algorithm. Recently, several methods such as random, key cells, potential field, and greedy approach method have been employed to obtain the initial paths (Lamini et al. 2018). In order to meet the diversity and randomness requirements of the initial population, random number method (Li et al. 2017) was used to generate the initial population in this study. Since the intelligent camera will pass through the grids between the starting position and the target position, one grid will be chosen randomly from each row of the grid-based model. By setting (x₀, y₀) as the starting point and (x_n, y_n) as the ending point, where x_n ≥ x₀ and y_n ≥ y₀, the position of current point is (x_i, y_i), then the position of the next point ((x_i+1, y_i+1)) can be generated randomly by the following equation:

$$ \left\{ {\begin{array}{*{20}c} {x_{i + 1} = x_{i} + \left( {x_{n} - x_{i} } \right)} \\ {y_{i + 1} = y_{0} + \left( {y_{n} - y_{0} } \right)} \\ \end{array} } \right. $$

(1)

Then, these randomly selected grids will be connected into a continuous path based on the midpoint connection method (Wei and Long 2019). The random number method used for initialization of population in this study can ensure the continuity of path; however, the initialized path may go through the obstacles in the grid-based model, which will turn into an invalid path. In this study, the invalid path will be penalized in the fitness function; therefore, it will not be selected for the rest operations of the genetic algorithm. The specific process will be introduced in Sect. 3.2 in detail.

2.4 Fitness function

When the initial population is generated based on the random number method, the genetic algorithm needs to evaluate the performance of each individual in the initial population. Usually, the fitness function can be used to assess the quality of each individual, which should consider several constraints of path planning problem such as length, safety, and smoothness of path. The definition of fitness function is crucial to the genetic algorithm because it influences the convergence quality as well as the optimization solution of the genetic algorithm. In this study, a new fitness function that considers multi-constraints will be proposed, which will be introduced in Sect. 3.1 in detail.

2.5 Selection operator

The main objective of selection process of genetic algorithm is to choose the potentially better individuals to form a mating pool. Therefore, individuals with good performance can be obtained in the next generation. An appropriate selection operator can avoid the loss of useful information and improve the global convergence and calculation efficiency. Up to now, many selection operators including roulette wheel selection, rank selection, elitism selection, tournament selection, and deterministic sampling selection have been proposed for the path planning problem by genetic algorithm, which are summarized in Table 2.

Table 2 Summary of typical selection operators for genetic algorithm in the literature

In this study, the deterministic sampling selection method will be used to conduct the selection process of the genetic algorithm, which can ensure that some individuals with great fitness value can be retained in the next generation, while those with small fitness value can be removed from the next generation. The main procedures of the deterministic sampling selection are shown as follows:

• 1. The expectation of the survival number of individuals (N_i) in the next generation can be calculated according to Eq. 2.

  $$ N_{i} = M_{p} \cdot f_{i} /\sum\limits_{i = 1}^{{M_{p} }} {f_{i} } $$

  (2)

  where M_p is the number of individuals (chromosomes); f_i is the fitness value of the i th individual.

• 2. For the i th individual, the number of the survived individual in the next generation is [N_i], where, [N_i] represents the rounding down operator.

• 3. All the individuals are sorted in descending mode in terms of N_i−[N_i]; then, the first $M_{p} - \sum\nolimits_{i = 1}^{{M_{p} }} {\left[ {N_{i} } \right]}$ individuals will be added based on the sorting results into the next generation.

2.6 Crossover operator

The main purpose of crossover operator is to combine the features of two parent chromosomes to form the offspring. Therefore, the diversity of the population can be enriched, and the solution to the path planning problem won’t be easy to fall into local optima. Currently, there exist many crossover schemes, e.g., single-point crossover, two-point crossover, uniform crossover, and arithmetic crossover, which are summarized in Table 3.

Table 3 Summary of typical crossover operators for genetic algorithm in the literature

In this study, single-point crossover is employed due to its high computational efficiency. When the two paths have an intersection, the parts of the two paths will be swapped after the intersecting point. If there exists more than one intersecting point, only one point will be selected randomly to conduct the crossover operation. When there is no intersection for the two paths, the crossover operation won’t be performed, which can avoid the discontinuity of the paths.

It is noted that in the original genetic algorithm, the crossover probability is fixed, which may lead to premature convergence and local optima. In order to solve these problems, a modified self-adaptive adjustment formula that uses a sigmoid function to adjust crossover probability was employed in this study, which is expressed as:

$$ P_{c} = \left\{ {\begin{array}{*{20}l} {\frac{{p_{c\hbox{max} } - p_{c\hbox{min} } }}{{1 + \exp \left[ {\left( {p_{c\hbox{max} } - p_{c\hbox{min} } } \right)\left( {\frac{{f_{c} - f_{{c{\text{ave}}}} }}{{f_{c\hbox{max} } - f_{{c{\text{ave}}}} }}} \right)} \right]}} + \frac{{p_{c\hbox{max} } { + }p_{c\hbox{min} } }}{2},} \hfill & {f_{c} \ge f_{{c{\text{ave}}}} } \hfill \\ {p_{c\hbox{max} } p_{c\hbox{max} } ,} \hfill & {f_{c} < f_{{c{\text{ave}}}} } \hfill \\ \end{array} } \right. $$

(3)

where P_cmin and P_cmax are the lower and upper limit values of crossover probability, respectively; f_c is the greater fitness of the two individuals involved in the crossover operation, f_cmax and f_cave denote the maximum and average fitness values in the crossover operation, respectively.

It is clear that from Eq. 3 that the crossover probability of the individuals with fitness value lower than f_cave will be set as p_cmax, which can promote the gene changes of such individuals. In addition, Eq. 3 possesses the characteristics of decreasing in [f_cave, f_cmax], which can guarantee the continuity stability of the crossover probability. Moreover, when f_c approaches f_cmax, the crossover probability is $\frac{{p_{c\hbox{max} } - p_{c\hbox{min} } }}{{1 + \exp \left( {p_{c\hbox{max} } - p_{c\hbox{min} } } \right)}} + p_{c\hbox{min} }$, and the local convergence resulting from very small crossover probability can be avoided.

2.7 Mutation operator

Mutation process is also an important part of genetic algorithm, which refers to the process that candidate paths do an actual change at some points; therefore, the population diversity can be expanded and the global search for optimal path can be ensured, which can avoid the premature convergence. Recently, many mutation operators including simple mutation, uniform mutation, boundary mutation, non-uniform mutation, and Gaussian mutation have been used in genetic algorithm, which are summarized in Table 4.

Table 4 Summary of typical mutation operators for genetic algorithm in the literature

In this study, the mutation operator is conducted like this: randomly select two points called mutation points from the candidate path (the starting and target points are not included), a segmented path is generated between the two mutation points, and finally a new path is created by combining the segmented path formed by the mutation points and the other segmented paths formed by the remaining points in the candidate path.

Similar to the crossover operator, a modified self-adaptive adjustment formula that uses a sigmoid function to adjust mutation probability is employed to avoid premature convergence and local optima, which is expressed as:

$$ P_{m} = \left\{ {\begin{array}{*{20}l} {\frac{{p_{m\hbox{max} } - p_{m\hbox{min} } }}{{1 + \exp \left[ {\left( {p_{m\hbox{max} } - p_{m\hbox{min} } } \right)\left( {\frac{{f_{m} - f_{{m{\text{ave}}}} }}{{f_{m\hbox{max} } - f_{{m{\text{ave}}}} }}} \right)} \right]}} + \frac{{p_{m\hbox{max} } { + }p_{m\hbox{min} } }}{2},} \hfill & {f_{m} \ge f_{{m{\text{ave}}}} } \hfill \\ {p_{m\hbox{max} } ,} \hfill & {f_{m} < f_{{m{\text{ave}}}} } \hfill \\ \end{array} } \right. $$

(4)

where P_mmin and P_mmax are the lower and upper limit values of mutation probability, respectively; f_m is the fitness value of mutation individuals, f_mmax and f_mave denote the maximum and average fitness values of all the individuals, respectively.

3 Proposed methods for genetic algorithm

3.1 A new fitness function for path planning

The main goal of path planning problem is to find an optimal path between the starting point and the target point. The optimal path refers to the path with best performance under the given constraint conditions. The performance of the candidate paths can be evaluated by the fitness function. It should be noted that the “optimal” here means that the planning must satisfy some criterions including the length of the planning path is the shortest, or the energy consumption of robot is the lowest, etc. However, most of the existing algorithms are developed to meet single constraint condition, e.g., the length of planning path should be the shortest. Actually, in many real-life situations, the path segment with a sharp turn small should be avoided when the intelligent camera is used in the virtual environment. If such path segment exists, it will bring dizziness effect to users when they are using the head-mounted display (HMD). Besides, the objective of interest should enter the vision field as soon as possible, so that the user can experience a pleasant interaction with the objective during the roaming process. Intelligent camera path planning can be regarded as a NP-hard problem with multiple optimal objects, which is difficult to find the precise solution. Consequently, a multi-constraint path planning algorithm for intelligent camera is proposed with the aim to the multiple constraint conditions. In order to meet the constraint conditions in terms of free obstacle, path length, path smoothness, and the visibility of the objective of interest in advance during the camera roaming, a new fitness function consisting of four components to consider the above constraint conditions is developed as Eq. 5. The greater the fitness function is, the better performance the path possesses, i.e., the path with a greater fitness value will have a higher probability of being selected to generate the optimal path during the genetic algorithm.

$$ fit(p) = 1/\sum\limits_{i = 1}^{4} {w_{i} f_{i} (p} ) $$

(5)

where $f_{i} \left( p \right)$ is the fitness component to characterize the i th constraint for path p; w_i is the weight of the i th fitness component.

3.1.1 Free obstacle constraint

In this study, the fundamental constraint for path planning problem is that the feasible path cannot pass through any obstacle during the camera roaming. And the fitness component is expressed as Eq. 6. Clearly, the fitness component of all feasible paths that do not pass through any obstacle will be zero.

$$ f_{1} (p) = \left\{ {\begin{array}{*{20}c} {1,_{{}}^{{}} I_{i} \in \varepsilon_{{}}^{{}} \left( {i = 1, \ldots ,n} \right)} \\ {0,_{{}}^{{}} I_{i} \notin \varepsilon_{{}}^{{}} \left( {i = 1, \ldots ,n} \right)} \\ \end{array} } \right. $$

(6)

where I_i is the i th point in path p; n is the number of points in path p; ε denotes the point set of obstacles in the grid-based model.

3.1.2 Path length constraint

Finding the shortest path from the feasible solutions is one important goal of path planning problem. In this study, the fitness component to take the path length constraint into consideration is computed based on Euclidean distance, which can be written as Eq. 7. A smaller $f_{2} (p)$ means the candidate path exhibits a better performance.

$$ f_{2} (p) = \sum\limits_{i = 1}^{n - 1} {\sqrt {(x_{i + 1} - x_{i} )^{2} + (y_{i + 1} - y_{i} )^{2} } } $$

(7)

3.1.3 Advance visibility constraint

During the roaming of intelligent camera, it is sometimes required that the objective of interest should enter the vision field of intelligent camera as soon as possible, so that the user can experience a pleasant interaction with the objective. Figure 2 illustrates the advance visibility constraint of two possible paths for virtual camera roaming. As shown in Fig. 2, the objective 1 of interest can be observed for the first time at Points A1 and B1 on the Paths A and B, respectively. By considering the path length of the two paths, objective 1 can be observed more early on Path A than on Path B. Therefore, Path A performs better than Path B in terms of advance visibility constraint.

Fig. 2

Illustration of advance visibility of two possible paths for virtual camera roaming

In this study, the fitness component defined as Eq. 8 is employed to consider the advance visibility constraint. It can be inferred from Eq. 8 that a feasible path with a better performance will have a lower value of $f_{3} (p)$.

$$ f_{3} (p) = \frac{{\sum\nolimits_{i = 1}^{m - 1} {\sqrt {(x_{i + 1} - x_{i} )^{2} + (y_{i + 1} - y_{i} )^{2} } } }}{{\left| {x_{n} - x_{1} } \right|}} $$

(8)

where m is the m th point on the possible path at which the objective of interest can be observed by the intelligent camera for the first time.

3.1.4 Path smoothness constraint

In order to minimize the dizziness effect caused by the sudden turn of intelligent camera during the roaming process, the optimal path determined by the genetic algorithm should be smooth as possible. In this study, the mean turning angle of intelligent camera is introduced to consider the path smoothness constraint. The mean turning angle denotes the change of angle per unit path length, which can be expressed as Eq. 9. It is evident that the path with better performance will possess a smaller mean turning angle.

$$ f_{4} (p) = \frac{{\sum\nolimits_{i = 1}^{n - 2} {\left| {\theta_{i + 1} - \theta_{i} } \right|} }}{{\sum\nolimits_{i = 1}^{n - 1} {\sqrt {(x_{i + 1} - x_{i} )^{2} + (y_{i + 1} - y_{i} )^{2} } } }} $$

(9)

where $\left| {\theta_{i + 1} - \theta_{i} } \right|$ is the angle between the path segments $p_{i} p_{i + 1}$ and $p_{i + 1} p_{i + 2}$, $\theta_{i} = \arctan \left( {\frac{{x_{i + 1} - x_{i} }}{{y_{i + 1} - y_{i} }}} \right)$ represents the angle between the path segment $p_{i} p_{i + 1}$ and the y coordinate.

3.2 A new evolving operator for path planning

It is widely accepted that one of the main drawbacks of original genetic algorithm is the premature problem, i.e., the result obtained by the genetic algorithm will prematurely converge to a local optima. During the process of finding the optimal solution by genetic algorithm, when certain individual performs much better than the other individuals, i.e., its fitness is much greater than those of the other individuals, this individual will be selected by the selection operator to generate the next generation with a high probability. As a result, most of the generated individuals from the next generation will possess similar features with the individual with a much greater fitness in the former generation. Therefore, the solution of the genetic algorithm will easily get trapped in a local optimum, and the selection operator and crossover operator usually fail to avoid such premature problem. Theoretically, the mutation operator can contribute to avoiding the premature problem. However, in order to ensure the stability of genetic algorithm, the mutation probability of the generated individual is usually very low (e.g., 0.01); therefore, it will require many numbers of iteration to generate a new individual that is quite different from those in the former generation, which will slow significantly the convergence speed of genetic algorithm. Furthermore, when the fitness of the new individual generated by the mutation operator is much smaller than the sum of the fitness of all the individuals, the new individual won’t be probably be selected by the selection operator for the following operations. Thus, the premature problem cannot be effectively solved by the conventional mutation operator.

In this study, a new evolving operator was introduced to solve the premature problem in the path planning by genetic algorithm, which is similar to the conventional mutation operator. However, it is noted that the evolving operator will be performed for all the individuals to randomly and independently generate new individuals that may possess different features from those in the former generation. Moreover, in order to ensure that the individual with great fitness is not destroyed by the evolving operator, only the generated individual with a greater fitness by the evolving operator than that of the original one will be preserved for the following processes of genetic algorithm. Therefore, the diversity of the population can be increased significantly, which can extend the searching space of path planning problem and avoid falling into a local optima, and thus, the number of iterations of genetic algorithm can be effectively reduced.

The evolving operator is conducted after the crossover operation and the mutation operation. The pseudo-code of the evolving operator is shown in Table 5. The main procedures of the evolving operator are shown as follows: For each feasible path in the population, two points except the starting and target points are randomly selected. Then, the path segment between these two points is removed. A new path segment using these two points of the original path before being evolved is generated. Grids will be chosen randomly from each row of the grid-based model between the two points. Then, these randomly selected grids will be connected into a continuous path based on the midpoint connection method.

Table 5 Pseudo-code of evolving operator

In the midpoint connection method, the following equation can used to judge whether the two adjacent points are continuous:

$$ \Delta = \hbox{max} \{ |x_{i + 1} - x_{i} |,|y_{i + 1} - y_{i} |\} $$

(10)

where (x_i, y_i) and (x_i+1, y_i+1) are the coordinates of Points p_i and p_i+1, respectively.

It is obvious that $\Delta = 1$ denotes that Points p_i and p_i+1 are two adjacent points. Otherwise, more points need to be inserted between Points p_i and p_i+1. The inserted point $p_{i}^{{\prime }}$ can be expressed as:

$$ \left\{ \begin{aligned} x_{i}^{{\prime }} = (x_{i + 1} + x_{i} )/2 \hfill \\ y_{i}^{{\prime }} = (y_{i + 1} + y_{i} )/2 \hfill \\ n_{i} = x_{i}^{{\prime }} + l \times y_{i}^{{\prime }} \hfill \\ \end{aligned} \right. $$

(11)

where $(x_{i}^{{\prime }} ,y_{i}^{{\prime }} )$ is the coordinate of Points $p_{i}^{{\prime }}$; $n_{i}^{{\prime }}$ is the grid number of the inserted point; l is the column number of the inserted point.

It should be noted that when the inserted point is located in the obstacle, the free grid nearest to the initial point located in the obstacle will be selected as the inserted point. If there exist duplicate grids in the generated path, the segmented path between the duplicate grids will be removed from the generated path, which is shown in Fig. 3.

Fig. 3

Illustration of elimination duplicate grids in the initialized path

The midpoint connection method used in this study can ensure the continuity of the randomly generated path; however, the generated path by connecting all the points may still go through the obstacles in the grid-based model, which will turn into an invalid path. In this study, the invalid path that cannot meet the multiple constraint conditions will be penalized in the fitness function; therefore, the invalid path that go through the obstacles will not be selected for the rest operations of the genetic algorithm.

Then, the fitness value of the new path obtained from the evolving operation will be evaluated according to the new fitness function proposed in Sect. 3.1, which will be compared with that of the original path. If the fitness value of the new path is greater than that of the original path, the original path will be replaced by the new path, which will be restored for the next operations, otherwise, the original path will be restored without any operation.

In this study, the evolving operator is controlled by the maximum number of iteration, i.e., when the specified maximum number of iteration is reached, the evolving process will be terminated and the optimal solution will be output. It is noted that the maximum number of iteration will vary with the size of grid-based model to represent the environment. Although it will increase the computing time of genetic algorithm to a certain extent, the evolving operation can effectively improve the searching ability of genetic algorithm to determine the optimal solution and avoid being trapped in a local optimum. Therefore, the number of iteration can be significantly reduced, and thus, the efficiency of the genetic algorithm can be improved.

4 Experimental results

4.1 Experimental settings

In this section, the performance of the genetic algorithm proposed in the study will be discussed based on the experimental results. Some of the state-of-the-art methods were employed in the experiments for comparison. The experiments were conducted in the two-dimensional grid-based model with different numbers of obstacles of different sizes and shapes. All the experimental simulations, coded in MATLAB language, were performed on a computer equipped with Intel Xeon E5 12 core processor (2.20 GHz clock rate) and 32 GB of random access memory. The parameters of the proposed method were summarized as follows: The population size was set as 200, the crossover and mutation probability were adaptive, and the penalty coefficients in fitness function were set as 0.38, 0.04, 0.56, 0.02 for w_i (i = 1, …, 4), respectively. The comparison of the results obtained by our proposed genetic algorithm and those in the literature in terms of iteration number, visibility in advance, path length, and path smoothness will be presented in the following section. All the simulation experiments were conducted for 50 independent runs. Due to the fact that the nature of metaheuristic algorithms is stochastic and different results may be obtained in different runs, the statistical analysis on the simulated results was performed to support the conclusions drawn in this study. First, the well-known nonparametric test, i.e., Kruskal–Wallis test, was used to analyze the data to validate the performances of all the algorithms used for comparison and to find out whether there are significant differences among these algorithms. If there exist significant differences among the experimental data of these algorithms, the multiple comparison procedure using the analysis of variance (ANOVA) test will be carried out to analyze the results of Kruskal–Wallis test, and the estimated value of the mean ranks for each group (algorithm) can be achieved, which can be used to evaluate the performance of the algorithms (Kruskal and Wallis 1952; Vargha and Delaney 1998; McKight and Najab 2010). A lower mean rank indicates that the algorithm has a better performance.

4.2 Comparison on iteration number

The iteration number affects the performance and the computational time of genetic algorithms. The iteration number of our proposed method was evaluated in the environment represented by the 2D grid-based model shown in Fig. 4. The genetic algorithms by Ahuactzin et al. (1991) and Alajlan et al. (2013) were also employed in the experimental simulations for comparison. The main features of these three genetic algorithms are summarized in Table 6. And the values for the parameters of the algorithms selected for comparison are summarized in Table 7.

Fig. 4

2D grid-based model used in the experiments to evaluate the iteration number

Table 6 Summary of genetic algorithms used in the experimental simulations

Table 7 Summary of the parameters in the genetic algorithms used for comparison

Figure 5 displays the comparison of iteration number of different genetic algorithms to find the shortest path in the environment shown in Fig. 4. Three scenarios with different starting and target points shown in Table 8 are considered. For each scenario, the typical optimal paths determined by the three genetic algorithms are also shown in Table 8.

Table 8 Typical paths obtained by different genetic algorithms for Scenario 1, Scenario 2, and Scenario 3

It can be seen from Fig. 5 that the iteration number of the genetic algorithms by Ahuactzin et al. (1991) and Alajlan et al. (2013), and our proposed one decrease in turn. For example, the iteration number of our proposed algorithm is about 8–82% of that of the genetic algorithm by Ahuactzin et al. (1991).

Fig. 5

Comparison of iteration number of different genetic algorithms to find the shortest path in the environment shown in Fig. 4

In order to examine whether there exist significant differences among the performances of all the algorithms used for comparison, Kruskal–Wallis test was conducted on the simulated results, which are shown in Table 9. It can be seen that all p-values for three scenarios are less than 0.05, so the null hypothesis are false, which indicates there exist significant differences among the experimental data of these algorithms. Thus, multiple comparison procedures were carried out to analyze the results of Kruskal–Wallis tests, and the estimated value of the mean ranks for each group is achieved, as shown in Table 10. It can be seen that the estimated values of the mean ranks of iteration number of our proposed algorithm are the smallest one for the three scenarios, which means the computational efficiency of our proposed algorithm is the best among these three algorithms. The main reason is related to the evolving operator proposed in our study.

Table 9 Kruskal–Wallis ANOVA Table of iteration number for different genetic algorithms to find the shortest path in the environment shown in Fig. 4

Table 10 The estimated values of the mean ranks of iteration number for different genetic algorithms to find the shortest path in the environment shown in Fig. 4

To further illustrate why our proposed algorithm performs better than the other two algorithms, Fig. 6 shows the comparison of iteration number of our proposed genetic algorithm with and without the evolving operator. It is interest to observe from Fig. 6 that the genetic algorithm with the evolving operator requires less iteration number in all scenarios, which is only 4–76% of that by the genetic algorithm without the evolving operator. Through analyzing these data with Kruskal–Wallis tests (Table 11), we can find that the algorithm with the evolving operator is different from that without the evolving operator since all the p-values are less than 0.05. Table 12 summarizes the estimated values of the mean ranks of iteration number for our proposed genetic algorithm with and without the evolving operator. It can be seen from Table 12 that the estimated value of the mean ranks of iteration number of our proposed genetic algorithm with the evolving operator is the smallest, which verifies again that the evolving operator proposed in this study can contribute greatly to the reduction of iteration number of genetic algorithm for path planning problem.

Fig. 6

Comparison of iteration number of our proposed genetic algorithms with and without the evolving operator

Table 11 Kruskal–Wallis ANOVA Table of iteration number for our proposed genetic algorithms with and without the evolving operator

Table 12 The estimated values of the mean ranks of iteration number for our proposed genetic algorithms with and without the evolving operator

4.3 Comparison on visibility in advance

In order to evaluate the advance visibility of objective of interest on the path, this section conducted experimental simulation in different scenarios shown in Table 13. The position to observe the objective of interest on typical paths obtained by different genetic algorithms is also marked in Table 13. Figure 7 shows the comparison of the advance visibility of objective by the genetic algorithms by Ahuactzin et al. (1991) and Alajlan et al. (2013), and our proposed genetic algorithm. A smaller advance visibility means that the genetic algorithm performs better in terms of advance visibility constraint. It can be seen from Fig. 7 that the advance visibility determined by the genetic algorithms by Ahuactzin et al. (1991) and Alajlan et al. (2013) and our proposed one decrease in turn. For example, the advance visibility of our proposed algorithm is about 57–80% (79–92%) of that of the genetic algorithm by Ahuactzin et al. (1991) (the genetic algorithm by Alajlan et al. (2013)).

Table 13 The position to observe the objective of interest on typical paths obtained by different genetic algorithms for Scenario 4, Scenario 5, and Scenario 6

Fig. 7

Comparison of advance visibility of different genetic algorithms to find the shortest path in the environment shown in Table 13

Then, both Kruskal–Wallis test and ANOVA test were performed on the simulated results in terms of advance visibility by different algorithms; the results are shown in Tables 14 and 15. It can be seen from Table 14 that all p-values are less than 0.05, which means at least one algorithm is significantly different from others. Based on the estimated value of the mean ranks of advance visibility shown in Table 15, it can be seen that the estimated value of the mean ranks of advance visibility by our proposed method is the smallest. The reason lies in that only our proposed algorithm considers advance visibility constraint in the fitness function.

Table 14 Kruskal–Wallis ANOVA Table of advance visibility for different genetic algorithms to find the shortest path in the environment shown in Table 13

Table 15 The estimated values of the mean ranks of advance visibility for different genetic algorithms to find the shortest path in the environment shown in Table 13

Based on the above results, it can be concluded that the visibility constraint of objective of interest in advance during the roaming of intelligent camera can be realized by our proposed genetic algorithm.

4.4 Comparison on path length

The length of the optimal path is an important index to assess the performance of the genetic algorithm in the path planning problem. In this study, three environments shown in Table 16, namely the 16 × 16-gird environment (Scenario 7), the 32 × 32-gird environment (Scenario 8), and the 64 × 64-gird environment (Scenario 9), were used in the experimental simulations. It is noted that the minimum unit of path length shown in this section is one pixel. In addition to our proposed genetic algorithm, the genetic algorithms by Ahuactzin et al. (1991), Ahmed and Deb (2013), and Alajlan et al. (2013) were used in the experimental simulation. The typical optimal path determined by these four genetic algorithms in the three environments is also plotted in Table 16. It can be seen that the optimal path varies with the employed genetic algorithm.

Table 16 Comparison of path length and path smoothness of the optimal path determined by different algorithms in 2D grid-based environments

Figure 8 shows the comparison of length of the optimal paths determined by different genetic algorithms. As the environment becomes more complex, i.e., the grid size of the environment becomes larger, the length difference between the original and modified genetic algorithms is more significant. For example, the length of the optimal path can be reduced by up to 39–97% by our proposed genetic algorithm as compared with the one by Ahuactzin et al. (1991).

Fig. 8

Comparison of length of the optimal paths determined by different genetic algorithms in the environments shown in Table 16

Based on the Kruskal–Wallis ANOVA Table of length of the optimal paths determined by different genetic algorithms shown in Table 17, it can be seen that all p-values are less than 0.05, which means at least one algorithm is significantly different from others. Table 18 shows the estimated value of the mean ranks of path length by different algorithms, which reveals that the estimated value of the mean ranks of path length by our proposed algorithm is the smallest. What’s more, the length of the optimal path determined by our proposed genetic algorithm is slightly shorter than that of the other two genetic algorithms in the environments shown in Table 16, confirming that our proposed genetic algorithm can perform well in the path planning problem in terms of the path length constraint.

Table 17 Kruskal–Wallis ANOVA Table of length of the optimal paths determined by different genetic algorithms in the environments shown in Table 16

Table 18 The estimated values of the mean ranks of length of the optimal paths determined by different genetic algorithms in the environments shown in Table 16

4.5 Comparison on path smoothness

Path smoothness is also a key factor that needs to be considered during the path planning for intelligent camera, since the dizziness effect caused by the sharp turn of the intelligent camera will lead to a bad user experience. This section is dedicated to the assessment of the smoothness of the optimal path determined by our proposed genetic algorithm. For better illustration, the other three genetic algorithms used in Sect. 4.4 were employed in the experimental simulations.

Figure 9 shows the comparison of smoothness of the optimal paths determined by different genetic algorithms in the environments shown in Table 16. The smoothness is evaluated by the mean turning angle shown in Eq. 9. Similar to path length results, the genetic algorithm by Ahuactzin et al. (1991) gives an optimal path with less smoothness; the smoothness difference between the genetic algorithm by Ahuactzin et al. (1991) and the other ones tends to increase with increasing grid size of the environment.

Fig. 9

Comparison of smoothness of the optimal paths determined by different genetic algorithms in the environments shown in Table 16

In this section, both Kruskal–Wallis test and ANOVA test were performed on the simulated results in terms of path smoothness by different algorithms; the results are shown in Tables 19 and 20, respectively. It can be seen from Table 19 that all p-values are less than 0.05, which means at least one algorithm is significantly different from others. Based on the estimated value of the mean ranks of path smoothness shown in Table 20, it can be seen that the estimated value of the mean ranks of path smoothness by our proposed algorithm is the smallest, which indicates that our proposed algorithm performs better than other algorithms in terms of path smoothness. What’s more, the mean turning angle of the optimal path determined by our proposed genetic algorithm is smaller than that of the other two genetic algorithms in the environments shown in Table 16, which indicates that the dizziness effect during the roaming of intelligent camera can be minimized by our proposed genetic algorithm.

Table 19 Kruskal–Wallis ANOVA Table of smoothness of the optimal paths determined by different genetic algorithms in the environments shown in Table 16

Table 20 The estimated values of the mean ranks of smoothness of the optimal paths determined by different genetic algorithms in the environments shown in Table 16

The above experimental results reveal that our proposed genetic algorithm is capable of reducing the dizziness effect during the path planning of intelligent camera.

5 Conclusions

In this study, a modified genetic algorithm for the path planning problem of intelligent camera was proposed. In the proposed method, a new fitness function was developed with the goal to meet the multi-constraint requirements during the roaming of intelligent camera. In addition, an evolving operator was also introduced into the modified genetic algorithm, which is designed to improve the efficiency of the algorithm.

Based on the experimental results conducted in different environments, our proposed genetic algorithms perform well in terms of iteration number, visibility in advance, path length, and path smoothness as compared with some state-of-the-art genetic algorithms. This confirms the feasibility and efficiency of our proposed method in the path planning problem of intelligent camera under multiple constraint conditions.

For the future work, different experiments in a real large-scale dynamic environment will be conducted in order to further verify and improve our proposed genetic algorithm. In addition, we would like to extend this work to dynamic environments with moving obstacles and goal positions.