Multi-objective optimal path planning using elitist non-dominated sorting genetic algorithms

METHODOLOGIES AND APPLICATION

Multi-objective optimal path planning using elitist non-dominated sorting genetic algorithms

Faez Ahmed ?Kalyanmoy Deb

Published online:18December 2012

óSpringer-Verlag Berlin Heidelberg 2012

Abstract A multi-objective vehicle path planning method has been proposed to optimize path length,path safety,and path smoothness using the elitist non-dominated sorting genetic algorithm—a well-known soft computing approach.Four different path representation schemes that begin their coding from the start point and move one grid at a time towards the destination point are proposed.Mini-mization of traveled distance and maximization of path safety are considered as objectives of this study while path smoothness is considered as a secondary objective.This study makes an extensive analysis of a number of issues related to the optimization of path planning task-handling of constraints associated with the problem,identifying an ef?cient path representation scheme,handling single versus multiple objectives,and evaluating the proposed algorithm on large-sized grids and having a dense set of obstacles.The study also compares the performance of the proposed algorithm with an existing GA-based approach.The eval-uation of the proposed procedure against extreme condi-tions having a dense (as high as 91%)placement of obstacles indicates its robustness and ef?ciency in solving complex path planning problems.The paper demonstrates

the ?exibility of evolutionary computing approaches in dealing with large-scale and multi-objective optimization problems.

Keywords Multi-objective path planning áPotential ?eld áPath length áPath safety á

Path smoothness áNSGA-II áGenetic algorithms

1Introduction

In recent years we have seen much advancement in the ?eld of industrial robotics,but mobile intelligent machines have mainly been con?ned to research labs.For an autonomous vehicle to be used in real-world applications it must be able to navigate autonomously and take intelligent decisions.Vehicle path planning comprises of not only generating collision-free paths from a given location to its destination point but also ?nding an optimized path that minimizes or maximizes certain critical 15a679f73169a4517623a3d0Valle (2006)and Hwang and Ahuja (1992)provide a broad coverage of the ?eld of motion planning algorithms focusing on vehicle motion planning.

There have been many conventional methods for two-dimensional path planning using classical optimization methods (Bisse et al.1995;Xue et al.2010),arti?cial potential ?eld method (Ge and Cui 2002;Al-Sultan and

Aliyu 2010),visibility graph (Lozano-Pe

′rez and Wesley 1979;Murrieta-Cid et al.2005),Voronoi road-map (Choset 1996),etc.Many soft computing methods such as arti?cial neural networks (Glasius et al.1995;Yang and Meng 2000),fuzzy logic method (Oriolo et al.1997;Pratihar et al.1999),genetic algorithms (Gerke 1999;Burchardt and Saloman 1831)and ant colony optimization (Sauter et al.2002)have recently come to forefront for

Communicated by F.Herrera.

F.Ahmed áK.Deb (&)

Department of Mechanical Engineering,

Indian Institute of Technology Kanpur,Kanpur,India e-mail:deb@iitk.ac.in F.Ahmed

e-mail:faez.iitk@15a679f73169a4517623a3d0

K.Deb

Department of Information and Service Economy,Aalto University School of Economics,00100Helsinki,Finland

123

Soft Comput (2013)17:1283–1299DOI 10.1007/s00500-012-0964-8

path planning.In a path planning task,a majority of research has been dedicated to?nding a feasible shortest path by formulating a single-objective optimization prob-lem.However,?nding the optimized path is never a single-objective problem,as many other attributes such as path safety(or path vulnerability)(Ahmed et al.2011)and path smoothness are also desirable for a navigation vehicle.The path vulnerability objective is associated with how close the vehicle pass through an obstacle.To compute this objective,we have taken help of the arti?cial potential?eld concept.Each obstacle holds a large potential in its center and the potential is assumed to reduce away from the obstacle.Thus,for a given path and a given setting of obstacles,the overall potential computed for the entire path accumulated due to the effect of all obstacles is denoted as the path vulnerability.Path smoothness is directly related to the amount of turn a vehicle has to take along the path from the start to the end of its motion.

Besides the single versus multiple con?icting objectives associated with the path planning problem,there are a number of other issues that must be resolved during an optimization process.One important matter is the scheme used to represent a path within the optimization procedure, as the performance of an optimization algorithm depends largely on the chosen representation scheme.In this paper, we propose four different techniques for path representa-tion based on a binary,mixed or integer coding of a path description.Second,the issue of a two-objective versus a three-objective optimization is another matter that will concern the practitioner and will test the usefulness of the chosen algorithm.Third,the use of obstacle avoidance as a hard constraint in the optimization process or handling of it softly through a penalty term is another matter that will determine the performance of the chosen algorithm. Finally,for a path planning problem,the scaling of the chosen optimization algorithm with the number of obsta-cles and the grid size must be well understood before the method can be recommended for a practical use.In this paper,we address all the above issues related to the path planning problem one at a time by considering obstacle scenarios that were adopted in earlier path planning studies.

A bi-objective algorithm minimizing path length and path vulnerability is proposed based on a popular multi-objec-tive optimization algorithm—the elitist non-dominated sorting genetic algorithm(NSGA-II)(Deb et al.2002),but the algorithm is modi?ed to use the third objective(path smoothness)to introduce diversity in the population and also to help in a subsequent decision making.To provide a stiff challenge to the proposed algorithm,the complexities of obstacle placement are gradually increased to have as high as91%of the cells occupied by obstacles.For this purpose,the search domain is also increased from898to a staggering1289128.These extremities are rarely used in the past computational path planning studies and the successful working of the proposed algorithm in them amply demonstrates their practical importance.Although other evolutionary multi-objective optimization(EMO) algorithms,such as SPEA2(Zitzler et al.2001)or MOEA/D (Zhang and Li2007)or others,can very well be used to obtain similar results,the purpose of this paper is not establish superiority of this or that algorithm,but to dem-onstrate that a multi-objective treatment of the path planning problem with an appropriate representation scheme can produce better results than an usual single-objective opti-mization algorithm,particularly in a scenario having a dense set of obstacles.

In the remainder of the paper,four new path represen-tation techniques are discussed in Sect.2.Three objectives used in this study are described next in Sect.3.Section4 discusses two different constraint handling methodologies and compares the three representation schemes suggested in this paper.Results for bi-objective problems are shown comparing them to a benchmark problem in Sect.5.A comparative study of single and three-objective optimiza-tion runs is also done.Thereafter,Sect.6makes random placements of obstacles on differently sized grids and investigates the ef?ciency of the proposed algorithm in ?nding a feasible path in the presence of an increasing number of obstacles.Problems having as large as 1289128grids and91%coverage of grids with obsta-cles,thereby resembling extreme practical scenarios,are considered next.Conclusions of the study are made in Sect.7.

2Path representation through a grid

To optimize any given path of a vehicle through an opti-mization technique,the foremost requirement is an ef?-cient path representation that can be incorporated in the programming environment and importantly that is suitable to be ef?ciently used with the chosen optimization algo-rithm.In this study,we use a genetic algorithm(GA)as an optimization algorithm.Since a GA allows a?exible way to represent a solution,we suggest four different repre-sentation schemes for the purpose.

To facilitate a discrete representation and also for the ease of navigation purposes,a grid-based approach is adopted here.In a given problem of2-D off-line path planning,we map the environment on a grid of size n9n,where the grid size n is decided depending on the accuracy required in the path planning problem.The size of the vehicle is taken to be smaller than unit cell size in grid so that the dynamics of vehicle rotation is not to be con-sidered.For simplicity,we always take the start location as the bottom-left corner,denoting grid location(1,1).In the

1284 F.Ahmed,K.Deb 123

Cartesian coordinate system,the destination is then?xed as (n,n)(or the top-right corner of the grid).This assumption is a reasonable one since most other path planning scenario can be mapped on to such a grid by simple linear trans-formations,such as translation,rotation,and scaling.Now if we consider the characteristics of the entire path between a start location and?nal location then different paths taken by a vehicle may have different lengths,directions,and turns at different points.A possible solution is a linked-list representation(Xiao and Michalewicz2000)of the entire path having a variable length gene.Such a representation of a path by genes of variable length is cumbersome con-sidering various GA operations,like crossover as well as the absence of knowledge about the bounds of path length.

A generalized representation would considerably increase the search space and hence slowing down the search pro-cess.Considering these dif?culties with variable-length gene representations,we propose a?xed-length path rep-resentation here.Motivated by another study(Sugihara and Smith1999),we consider only paths which are monoto-nous along one axis.That is,starting from location(1,1), the path moves one grid at a time towards right till it reaches the destination point(n,n).Since there are n col-

umns in the search domain and the vehicle is already at the ?rst column,we would require(n-1)genes to represent a path.We propose three different techniques of representing a path involving binary,integer or mixed-valued genes.We describe these representation schemes in the following subsections.

2.1Binary-coded genes

Our proposed path representation technique was inspired by a recent study(Sugihara and Smith1999).We?rst describe the procedure and then our coding method to alleviate a dif?culty associated with the earlier procedure. Let us consider the grid as comprised of rows and columns. To represent a path,following symbols were de?ned:

–‘A’denotes an upper diagonal step from one column to the next parallel to(^it^j).

–‘B’denotes a lower diagonal step from one column to the next parallel to(^ià^j).

–‘C’denotes a horizontal step from one column to the next parallel to(^i).

–‘D y’denotes an upward vertical movement by y units within a column parallel to(t^j).

–‘E y’denotes downward vertical movement by y units within a column parallel to(à^j).

Graphical notion of the above symbols is given in Fig.1,where^i corresponds to positive x-axis and^j to positive y-axis.A gene comprises of(n-1)movements where each movement is one transition step(A,B or C) followed by a vertical motion(D y or E y)within a column, where y denotes magnitude of vertical motion.In Sugihara and Smith(1999),transition from one column to other was either through A,B or C,but any vertical movement D y or E y within a column was ignored if the last transition was either A or B.That is,if a diagonal move is taken,the path cannot go upwards or downwards;it can only go forward, whereas to move up more than one grid up or down,the only option is to go horizontally towards right and then make a vertical move up or down.This is restrictive and as we shall discuss later it will create paths that are dominated by diagonal paths.We modify the above coding by allowing vertical steps after type A or B movements as well.

In our proposed binary-coding,each gene comprises of two parts.First two bits represent the direction of transition to the next column in four possible ways.The vehicle can move diagonally up by one grid and then a distance y up along the column.We call this movement A-D y and it is represented by a11substring followed by a second sub-string decoding to y.Since n is the maximum grid size, d log2n e bits are needed to represent y.Thus,a movement by one grid towards right requires(2td log2n e)bits.This and other three scenarios are depicted in Fig.1.

Similarly,B-E y would represent a move diagonally down by one grid and then a further movement down by y grids. This process is represented by a(00followed by d log2n e) bits decoding to y.Substrings(10or(01represents

a Fig.1Representation scheme denoting(left)steps corresponding to alphabetic codewords,(center)decoded binary bits,and(right) representation schemes of transition followed by vertical movement step in terms of alphabetic codewords

Multi-objective optimal path planning using elitist NSGA-II1285

123

horizontal movement by one grid,but each is integrated with a further upward or a downward movement of y grids.The upward movement is denoted as C-D y and downward movement is by C-E y.Thus,to represent all(n-1)grid movements towards right from start to destination,a total of enà1Te2td log2n e)bits would be required.

A careful thought will reveal that by the above repre-sentation scheme,we have eliminated a diagonally up movement followed by a downward movement or A-E y,as the same can be achieved with a smaller path length and path safety using a C-D y or a C-E y movement.Since in our multi-objective formulation A-E y would always be domi-nated by either C-D y or C-E y,we simply do not allow A-E y or B-D y movements.Thus,this representation scheme reduces the feasible search space and in turn helps the optimization algorithm to work better.

Next,we discuss an end-?xing mechanism that goes with the above representation scheme.It is mentioned above that every path originates from the start point (1,1),but following a particular coding of(n-1)genes

(as mentioned above)every path may not end up reaching the destination point(n,n).To make sure that every path reaches the destination point,we modify the(n-1)-th gene as follows.The path is followed by the?rst substring of the(n-1)-th gene,but the value of y from the second substring is ignored.A(11)will take the path one grid diagonally up,a(00)will take the path one grid diagonally down,and(10)or(01)will take the path horizontally by one grid.Thereafter,instead of using y to determine whe-ther to go up or down,the path is simply joined to the destination point.Since the second substring coded to represent y for the(n-1)-th gene is redundant,we use it to represent any upward movement of the vehicle at the start grid.We take a couple of examples to illustrate this representation scheme.

In Fig.2,two sample paths are shown on a898grid. Thus,n=8in this example.The binary representation of Path1is given as follows:

(000,11-010,11-000,10-000,00-001, 00-000,10-000,11)

Note that the seventh gene is split into two,of which the ?rst substring indicating a diagonally upward movement from seventh to eighth grid is represented by the?nal(11), and its associated substring(000)is shown at the begin-ning to indicate that there is no vertical movement of the path at the start grid.Other movements—for example,from ?rst to second grid there is an upward diagonal movement (decoded by(11))followed by two grids(decoded value of (010)of upward movement(A-D2),and others—are straightforward.Notice how the end-?xing on the right-most column takes the path to the destination point.The vertical movement of?ve grids is not coded in the string,but is?xed algorithmically,making sure that the overall path goes from the start to the end grid.On the same manner,Path2can be represented by the following binary string:

(101,11-000,01-000,11-000,00-001, 00-000,11-001,11)

Here,notice that at the start the vehicle moves by?ve grids(decoded value of(101)shown at the front of the string)at the start and then follows the other grid-wise movements.At the?nal grid,the vehicle makes an upward diagonal movement and reaches the destination point on its own.Thus,in this path,no end-?xing is needed for the path to reach the destination point.

In addition to the end-?xing involving the start and the n-th columns,if at any intermediate column the vehicle goes out of the search area(to the bottom of?rst row or to the top of n-th row),it is brought back to the search area using an edge-?xing procedure.In this event,the y com-ponent of the string is ignored and the vehicle is placed randomly at a row with a linear probability distribution having its maximum at the respective edge of the search area to zero at the current row of the vehicle.In both Paths 1and2,this scenario did not occur and no edge-?xing was required.

The advantage with the above binary coding is that a binary-coded genetic algorithm can now be used directly to evolve the population members.The usual single or multi-point crossover operators and the bit-wise mutation oper-ator can be applied directly.Here,we have used a two-point crossover and a bit-wise mutation operator for this purpose;however,the mutation probability is linearly reduced to1/5-th of its initial value at the?nal

generation. Fig.2Example paths with corresponding binary representation along with a few non-represented steps in path

1286 F.Ahmed,K.Deb 123

Moreover,since the search space is substantially reduced by not allowing intuitively dominated paths to appear through the representation scheme,the search is also likely to be ef?cient.The?x-ups mentioned above will also make the paths realizable.The drive towards feasible and even-tually optimized paths will then be achieved by the way of handling the objective function and constraints.

2.2Mixed-coded genes

The above binary-coded representation makes a signi?cant improvement from the existing study(Sugihara and Smith 1999)in terms of reducing the dominated paths.However, some thoughts will reveal that the coding can be made more ef?cient by using a mixed binary-integer represen-tation of a path.

Consider,for example,a C-D2path going from(1,1) to(2,1)to(2,3).This path is dominated by another path (A-D1)which makes an upward diagonal movement and then move up vertically by one grid.This path is shorter than C-D2and since the vehicle is considered to be small compared with the grid dimension,it is also as safe as C-D2.Thus,on both account,A-D1is no worse than C-D2 and hence C-D2can be considered redundant in our search process.To eliminate such dominated paths to appear through our coding scheme,here we use one bit to repre-sent upward or downward movement and a direct integer value to represent the extent of vertical movement,if any. We discuss this mixed-coding scheme in the following paragraph.

The mixed-coding representation for a gene has two components as before.But here,the?rst component has just one bit.However,the meaning of the bit depends on the associated second component—an integer in the range [0,n](both inclusive)representing vertical movement y.If y=0,a1or a0in the?rst substring would mean an identical movement(C),that is,a movement of one grid horizontally to the right.However,if y[0,then a1in the ?rst component would mean a move diagonally upwards and then make(y-1)vertical grids up.Thus,1-y means A-D(y-1)for y C1.Similarly,a0with a non-zero y would mean a downward diagonal movement followed by (y-1)vertical grids down.Thus,0-y means B-E(y-1). This mixed-coding does not allow the path to have a hori-zontal move followed by any vertical upward or downward movement,as they were allowed in the binary-coded rep-resentation.Any up or downward movement must be achieved with a non-zero y at any gene.This restriction does not prevent any feasible non-dominated sub-path to be represented.This substantially reduce the number of domi-nated solutions in the search space.

Path1shown in Fig.2would now be represented by the following coding:(01-31-10-00-20-11-01) Like before,the?rst element(a zero)indicates no ver-tical movement at the start grid.Next mixed-gene indicates that an upward diagonal movement and then a vertical movement of(3-1)or two grids up.The path can then be followed by the above-mentioned coding principle.At the (n-1)-th column,a1indicates a diagonal movement upward.A0would have indicated a horizontal movement to the n-th column.Since the seventh gene is a1,the vehicle moves one grid diagonally upward.From this position,the end-?xing rule is applied and the vehicle is moved up another?ve grids up to reach the destination point.Path2can be represented as follows:

(51-11-01-10-20-11-21) The edge-?xing and top-row-?xing rules are applicable here as well.Although the above gene representation makes the explanation of the path easier,in a GA,we concatenate all bits together and form a(n-1)-bit string and all integer values are put together to form a(n-1)-size integer vector.The binary string is operated by the standard single-point crossover and bit-wise mutation operators and the integer-valued vector is operated by the discrete versions of the simulated binary crossover(SBX) (Deb and Agrawal1995;Deb and Goyal1998)and the polynomial mutation operator(Deb2001).

2.3Integer-coded genes

It is clear from the above mixed-coded representation that there is a still a small redundancy in the coding.A hori-zontal movement by one grid can be represented by using either0-0or1-0.As mentioned above,as long as y=0, the value of the preceding bit was not important.We remove this redundancy in the mixed-coding scheme by completely eliminating the binary coding and representing y of each gene by an integer in the range[-(n-1),(n-1)].Only in the?rst gene,y values in the range[0,(n-1)]is allowed.Other end-?xing,edge-?xing and top-row-?xing rules are applicable here as well.Thus,to represent Path1 in Fig.2,the following(n-1)-variable vector would be used:

(0,3,1,0,-2,-1,0)

Here,the?rst element represents the movement at the start column and the?nal element represents the movement at the(n-2)-th column to(n-1)-th column.The movement from(n-1)-th to n-th column has just two options before the end-?xing operation.The vehicle can go either upward and a possible vertical movement thereafter to reach the destination point or a horizontal movement to directly reach the destination point.This is because a horizontal move followed by a vertical move always gets dominated in our set-up by a direct diagonal movement.At the end of string coding,we investigate the string for either

Multi-objective optimal path planning using elitist NSGA-II1287

123

of the two scenarios and arrange the path accordingly.For Path1,we need to move diagonally one grid up,as the current location of the vehicle is below the destination point and then moves?ve grids vertically upward to reach the destination point.Thus,the transition from(n-1)-th column to the n-th column is never coded in the proposed integer-coding scheme and is?xed based on the above argument.Path2can be represented by the following integer-coding:

(5,1,0,1,-2,-1,2)

This path also requires a diagonal movement from seventh column to the eighth column,as the location of the vehicle at the seventh column is below to that of the des-tination point.

To demonstrate the difference between the three coding schemes discussed above,let us consider a couple of alternate paths shown in Fig.2.Let us denote ABCDENFGHIJK as Path3and ABCDEFGHOIJK as Path4.These paths can be represented by our binary-coded representation scheme,but cannot be represented by our mixed or integer-coded scheme.In Path3,the part ENFG takes the vehicle from the initial cell E to cell G in the next column.This can always be replaced by EFG to reach the same location with a shorter path length and path vulner-ability(to be de?ned in a later section).Similarly,in Path 4,the part HI dominates the part HOI.Therefore,Paths3 and4are dominated by another path and can never be on the true Pareto-optimal front.

2.4Absolutely positioned integer-coded genes

As a fourth representation scheme,the integer-valued genes described in the previous subsection can be replaced with the absolute location of the grids along each column. Since a path always starts from the grid location(1,1),a set of(n-1)integer values in the range[1,n]will determine the path exactly.The?nal transition from(n-1)-th col-umn to the n-th column can be made using the procedure described in the previous subsection.A similar represen-tation scheme was suggested elsewhere(Elshamli et al. 2004).

The integer-valued coding in the previous subsection is sensitive to the initial part of the path.A small change in the initial part may make a signi?cant change in the?nal part of the path,as every gene represents a relative change in location from the previous gene.The absolute-positioned integer-coding scheme described here does not have such a dif?culty.However,when we perform simulation runs on some simpler scenarios,we noticed the inadequacy of this absolutely positioned integer-coded representation.Due to the insensitivity of each gene over the other,the relative movement between one column to the next is not important in this coding and this leads to a zig-zag path and the path often results in infeasible paths.Since a genetic algorithm is believed to work by?nding lower-order building blocks to form higher-order building blocks,the relative repre-sentation may provide a GA to focus on the initial part of the path?rst and then may enable to form the remaining path grid by grid till the complete path is formed.Such an implicit ordering in forming the optimized path may turn out to be an important property for the successful working of a GA.Discouraged by these proof-of-principle experi-ments,we have not continued with the absolutely-posi-tioned integer-coded gene representation scheme in this study.

3Objectives of the path planning problem

In this paper,we have considered three speci?c objectives of the path planning problem.Of these,minimizing path length and enhancing safety are the major objectives of the study while path smoothness is used as a secondary objective.We describe the objectives in the following subsections.

3.1Minimum path length

Every path planning problem must provide some impor-tance to a shorter path.In this study,since a path is rep-resented on a rectangular grid,we simply compute the path length by summing the distance between consecutive grid points along the path.The vehicle is always considered to be traversing through the center of a grid cell and thus,a distance between(i,j)-th grid to(k,l)grid(where i;j;k;l2?1;n )is computed as the Euclidean distance between coordinate points(i-0.5,j-0.5)to(k-0.5, l-0.5).

3.2Minimum path vulnerability

The?ip side of following a shortest path is the danger of colliding with an obstacle.To estimate how precariously the vehicle moves close to obstacles,we follow the com-monly used potential?eld approach.The potential value in a cell represents directly the dif?culty in traversing through it.Since each cell is allotted a potential value according to obstacle distribution,we sum the potential of each cell through which the path traverses to compute the total vulnerability level.

The potential?eld approach is a widely studied method (Ahuja and Chuang1997;Connolly et al.1990;Khatib 1986).It gained popularity because it displayed a great reduction in computational demand when compared with the con?guration space approach.In this method,each obstacle in the system is surrounded by a repulsive

1288 F.Ahmed,K.Deb 123

potential?eld while the goal location is surrounded by an attractive potential?eld.A vehicle applies the resulting force experienced at its location as a control input to the driving system.The approach,however,suffers from a major problem.This has to do with the formation of local potential minima that can trap the vehicle before it reaches its destination point.In this study,we have used practical approach of assigning a bell-shaped(Gaussian)potential ?eld at every cell containing an obstacle.The obstacle containing cells are given extremely high potentials.A variance of50%of the cell size is used here;however, higher or lower values of variance can be used to have an effect of more or less conservative paths,respectively.

3.3Path smoothness

The smoothness of a path is evaluated by summing the angle of each turn the vehicle has to make in traversing the path.The smoothness of a trajectory is a desired attribute in vehicle path planning(Kanayama and Hartman1997). Smooth paths decrease unnecessary curvature discontinuity and possible stops and thus lower the possibility of slip-page.It leads to lesser power consumption as well as lesser travel time.Though smoothness is desired in a path,it need not be used as an objective function in most path planning optimization tasks,as the true optimized smooth path that ignores path vulnerability and other maneuvering issues may not be what a path planner would be looking for.

In this study,we consider path smoothness as a sec-ondary goal of the path planning task.In a bi-objective optimization framework of minimizing path length and path vulnerability,path smoothness can be used as a tie-breaker or as a decision-making aid.We shall discuss the interaction of path smoothness with the other two objec-tives in the next section.

4Optimization methodologies

In this section,we discuss various optimization method-ologies developed for solving the path planning problems from various perspectives.

4.1Obstacle avoidance procedures

It is intuitive to keep constraint from interfering with an obstacle.In our algorithms,we have used a potential function for this purpose.Each cell having an obstacle has a high potential at its center and it reduces away from the center.Thus,any path that crosses a cell having an obstacle will accumulate a large potential value.Thereafter,using the overall potential(called as path vulnerability above)in the optimization problem either as an objective to be minimized or a constraint to be satis?ed,the optimization process will drive the search towards paths that are obstacle-free.

However,in an extended version of our optimization algorithms,in addition,we count the number of obstacles a path crosses and call this number the‘Number of inter-fering cells’.The multi-objective optimization problem is modi?ed as follows:

Minimize Path length;

Minimize Path vulnerability

Subject to Potential P0;

e1Tand the single-objective problem is modi?ed as follows: Minimize Path length or path vulnerability;

Subject to Number of interfering cells0:

e2T

If,for any path,the number of interfering cells is greater than zero,we declare the path to be infeasible.Further-more,in our proposed approach,we use the parameter-less single(Deb2000)or multi-objective(Deb et al.2002) constraint handling technique,as the case may be,to handle infeasible and feasible solutions.In the tournament selection of comparing two solutions,if an infeasible solution is compared with a feasible solution,the latter always wins(Deb2000,2001).On the other hand,if both solutions are feasible,the solution with a smaller objective value or having a better non-dominated front or a larger crowding distance value wins.Finally,if both solutions are infeasible,the one with a smaller count on interfering cells wins.For brevity,we do not present any simulation results here but state that this extended approach works well for cases with sparse obstacles,but fails to?nd a feasible path in cases with a highly dense set of obstacles in a single objective study.It has been observed that a better technique is to penalize the objective(s)with the count of interfering cells.Initial populations usually have infeasible solutions, but the drive the search towards minimizing penalized functions eventually brings the number of interfering cells to zero.Based on these initial proof-of-principle studies, we use the penalty function approach for the rest of the paper here.

5Multi-objective path planning

In this paper,we modify the elitist non-dominated sorting genetic algorithm or NSGA-II algorithm(Deb et al.2002) for this purpose;however,other evolutionary multi-objective optimization(EMO)algorithms can also be used to obtain similar results.For details of NSGA-II,readers are encouraged to refer to the original NSGA-II study(Deb et al.2002).Here we describe the procedure brie?y.

Multi-objective optimal path planning using elitist NSGA-II1289

123

Initially,a population is initialized randomly.Thereaf-ter,the population members are sorted based on their non-domination level in the population.In the so-called non-dominated sorting,the?rst front members are non-dominated members of the entire population.The second front members are those that are non-dominated population members for which?rst front members are excluded,and so on.Each individual in a front is assigned a crowding distance based on the distance of the neighboring solutions from it.A solution has a large crowding distance if its nearest neighbor lies far away from it in the objective space.In a tournament of comparing two solutions,a solution is considered better if it lies on a better front or has a larger crowding distance value(thereby indicating an isolated solution).After the mating pool is created,they are used to create a new population using crossover and mutation operator exactly the same way as they are done in the case of single-objective GA.In the NSGA-II approach, both parent and newly created populations are merged and the combined population is sorted for their non-domination level again.Population members lying on the better fronts are chosen one at a time till the new population cannot accommodate any new front.To maintain the population size,all members of the last front,which could not be accommodated as a whole,are compared for their crowding distance values—a measure of emptiness in a solution’s vicinity in the objective space(Deb et al.2002)—and the ones having the largest crowding distance values are selec-ted.This process is continued till the termination condition is met.

Since an EMO algorithm,including NSGA-II,is sto-chastic in nature and is likely to produce different sets of trade-off solutions in each run,we propose a more reliable multi-objective optimization algorithm here.We perform 10runs of the proposed NSGA-II starting with different initial random populations for a particular choice of rep-resentation scheme until the speci?ed termination criterion is satis?ed.Thereafter,we combine all10sets of non-dominated fronts and present the overall non-dominated front.

5.1Third objective as a decision-maker

In the path planning problem,we have used both path length and path vulnerability as two objectives.The num-ber of interfering cells is used as a constraint and is handled using the penalty function approach.To introduce the path smoothness as a criterion to prefer smooth paths,we modify the above NSGA-II’s selection scheme somewhat. For two paths being compared in a tournament or in choosing the?nal front members,solutions of the same rank are checked for their smoothness values,instead of their crowding distance values.The solution with a better path smoothness wins.If two solutions being compared have an identical non-domination rank and identical path smoothness value,then the crowding distance value is checked and the one with a higher crowding distance wins. We also introduce the path smoothness criterion in another way to emphasize preferred paths.In the post-processing step,if two or more paths lie on the same point in the objective space(length-vulnerability trade-off front),path smoothness criterion is used to choose the single solution having the largest smoothness value.Thus,in both cases, the third objective of path smoothness is used as a decision-making aid.

5.2Parameter settings

A little thought will reveal the fact that the complexity of the path planning problem would depend on the relative location of the obstacles in a grid system.For an identical grid system,a?xed number of obstacles may be placed in such a manner that?nding a valid path from start to?nish may be dif?cult or in some cases impossible.Thus,the parameter settings for any path planning task are dependent on placement of obstacles and also on the grid size. Increasing the grid size requires more computation due to increase in the number of variables.It is also observed that higher obstacle density usually requires more function evaluations to converge,but location of the obstacles is an important matter.

Based on initial studies on many such path planning problems prior to this study,we choose the following NSGA-II parameter settings for all multi-objective test cases of this paper(n is the size of the grid): Population size(N)=500,

Generations(t)=500,

Generations(t)=500,

Crossover rate(p c)=0.9,

Crossover distribution index(g c)(Deb and Agrawal 1995)=10,

Mutation rate(p m)=1/n,

Mutation distribution index(g m)(Deb2001)=20.

Higher population sizes and the number of generations may be essential to handle a higher grid size problem and a more densely packed obstacles than that used in this study, but we use the above setting for all problems irrespective of density of obstacles and grid size.The bi-objective path planning scheme elaborated above is generic and before proceeding to show results on test cases,performances of three representation schemes are compared.

The purpose of this paper was not to compare one EMO algorithm with another method,but to demonstrate the importance of an EMO algorithm in obtaining trade-off path planning solutions.Hence,in this paper,we refrain

1290 F.Ahmed,K.Deb 123

from comparing the chosen NSGA-II algorithm with any other EMO algorithm;however,such an application remains as an important future study.

5.3Comparison of three representation schemes

In this section,we use the three representation schemes discussed earlier,namely,the binary-coded,mixed-coded, and integer-coded representation schemes.To compare, here we choose a32932obstacle arrangement shown in Fig.4.173obstacles were randomly kept in different cells.

As mentioned above,we choose a population of size500 and run the bi-objective NSGA-II for500generations.Ten runs with different initial populations are taken for each scheme to obtain the trade-off solutions.Thereafter,all the solutions of a particular scheme are combined to study convergence behavior.Figure3shows all the trade-off points obtained in the?nal trade-off fronts obtained in ten different runs for three different schemes.It can be seen that the obtained trade-off frontiers for integer coding are clearly better than that obtained with the mixed coding or binary-coded representation schemes.Binary-coded scheme is found to be consistently performing poorly.The trade-off solutions for integer-coded scheme dominate the other two. Similar results are also observed on a few other test prob-lems,which are not shown for brevity.

The superior performance of integer-coded representa-tion scheme is explained here.As discussed in Sect.2,the search space in integer-coded scheme to represent the same problem is substantially smaller than the other two schemes.Thus,it is relatively easier to?nd valid and meaningful paths using the integer-coded scheme.This leads to improvement in the performance of the optimi-zation algorithm.Three paths are marked on the non-dominated trade-off front,corresponding to the mini-mum path distance solution,minimum path vulnerability solution,and an intermediate compromised solution in Fig.4.It shows how the intermediate solution negotiates the distance and safety and becomes a compromised alternative solution.

5.4Bi-objective path planning

Having found that the integer-coded representation scheme produces a consistently better performance compared with other two potential coding schemes,we use the integer-coded scheme from now on.In this section,we take two sample problems with grid sizes16916and32932, respectively,to demonstrate the trade-off paths obtained by the proposed modi?ed NSGA-II approach.First,we con-sider a benchmark problem shown in Fig.5b which helps to compare our method directly with another existing study.The study also used a genetic algorithm approach. This scenario was the most complex scenario considered in the path planning study,while,as we shall see later,the current scenario is much simpler than some of the later scenarios which our proposed algorithm could handle.

The obstacle pro?le is as shown in Fig.5b along with three paths obtained by the integer-coding representation scheme.The modi?ed NSGA-II is used with the path smoothness criterion used as a decision-making aid as discussed earlier with500population members and run for 500generations.Ten runs with different initial populations are taken and the?nal solution set of each run is combined. Thereafter,we?nd the non-dominating points from this set to locate the trade-off front.The trade-off front is shown in Fig.5a and the paths marked on it correspond to minimum path length,minimum path vulnerability,and an

Multi-objective optimal path planning using elitist NSGA-II1291

123

intermediate compromised solution,respectively.It is interesting to note that how the minimum path length solution nudges close to some of the obstacles to reduce the overall path length and how the minimum path vulnera-bility solution is keeping the path away from the obstacles to ensure adequate safety.The intermediate solution is a compromise between these two extreme solutions.It is clear that the compromised solution lies on a‘knee’region of this trade-off front.When there exists such a knee point on a trade-off frontier,it is often a preferred solution(Deb and Gupta2001),as there is not enough motivation to move away from the knee point due to unfavorable trade-offs.

The solution reported in the existing GA study(Castillo and Trujillo2005)is also marked on Fig.5a for a com-parison purpose.The study did not show multiple paths clearly with interconnecting grids;however,we extract the minimum path length con?guration from the reported ?gure and compute path vulnerability using our computa-tional method.Figure5a shows that the earlier reported solution(indicated by‘Path X’)gets dominated by our minimum path length solution and two other solutions, thereby indicating ef?cacy of our proposed procedure.

We now discuss the results obtained with this multi-objective optimization algorithm on a sparse obstacle sce-nario presented in Fig.6b.Here also,we use the integer-coding representation and a population of size500and run the modi?ed multi-objective NSGA-II algorithm for500 generations to obtain trade-off solutions.Ten runs are taken and?nal non-dominated set of points is found.The trade-off solutions are shown in Fig.6a.The ranges of path vulner-ability and path length values obtained by this study show that a diverse set of solutions are found by the proposed multi-objective optimization algorithm.Figure6b shows three paths picked from the obtained trade-off frontier.The solid line represents the shortest path,the dotted line shows the least vulnerable path,and the dashed line shows an intermediate path.It seems that the chosen intermediate path makes a good compromise between the two extreme solu-tions(not too long and not too close to obstacles)and can be a preferred solution for an application.Interestingly,the shortest and least dif?cult paths are similar to those obtained by the single-objective optimization study in Fig.7a.

1292 F.Ahmed,K.Deb 123

5.5Single-objective path planning

In the previous subsection,we have shown results from the bi-objective study ?rst;here we show results from a single-objective study in which integer-coded representation scheme is used and either the path length or the path vul-nerability is minimized one at a time.The number of interfering cells is used as a constraint.Parameter settings are identical to that used in NSGA-II run,except that g c =2is used (Deb and Agrawal 1995).In Fig.7we have shown two single-objective optimi-zation results—one with path length as an objective and the other with path vulnerability as an objective—for two-obstacle scenarios.In the sparse obstacle scenario on a 16916grid (Fig.7a),both individual optimized paths are shown.It is interesting to observe that the minimum path length solution (solid line)traverses almost in a straight line from start to ?nish.This is expected particularly if the straight line path is feasible.On the other hand,the mini-mum path vulnerability solution (dotted line)takes

a

(a)

(b)

Multi-objective optimal path planning using elitist NSGA-II 1293

123

somewhat longer path,traversing through a region with no or a few obstacles.This is again expected,as a minimum vulnerable path is the one that avoids the obstacles as much as possible.The trade-off between the two objectives becomes clear from this example.It is worth mentioning here that the same problem was solved using a multi-objective optimization algorithm in Sect.4involving both path length and path vulnerability as objective functions in a bi-objective set-up and two very similar extreme solutions were obtained by the proposed multi-objective optimization algorithm as well.The outcome of both single-and multi-objective optimizations supports each other’s results and provides an idea that the obtained solutions may be close to being truly optimal.

We shall now discuss the results obtained using the single-objective optimization on the larger grid size prob-lem having a more dense obstacle scenario and also having 64964grid(shown in Fig.7b).There are791obstacles in the grid and the problem is more dif?cult than the pre-vious one.The single-objective GA(with path length as the sole objective)fails to?nd a valid path after500genera-tions run with500population members.The best solution obtained in10runs collides with one of the obstacles. Similarly,the single-objective optimization to minimize path vulnerability objective alone also fails to?nd any feasible path in10runs with identical parameter settings. The best solution for this objective collides with three obstacles.Since no valid path is obtained by both single-objective optimizations,we show the least constraint-vio-lated solutions from each run in Fig.7.The same problem is solved later(in Sect.6)with a multi-objective formu-lation.As shown in Fig.11a,feasible paths are found in 80%runs and each solution does not collide with any of the791obstacles.

Based on these two simulation studies and our experi-ence in solving a few other scenarios,we conclude that the proposed single-objective GA can be utilized to?nd the extremities of trade-off front for simple cases with a low density of obstacles.A single-objective GA is unable to perform well on large grid size and dense obstacle cases. However,the multi-objective GA proposed here with both path length and path vulnerability is able to?nd a feasible path in different grid sizes and on both sparse-and dense obstacle scenarios.

The reason for superior performance of multi-objective GA lies in the maintenance of diversity in the population. Diversity preservation is an important matter for genetic operations to work properly.When multiple con?icting objectives are used,a multi-objective GA does not allow solutions to converge towards any individual optimized solution.Thus,a natural diversity is maintained in such an application,besides the ability of the algorithm to ?nd multiple trade-off solutions.A single-objective GA attempts to?nd a single optimized solution and it becomes easy for the algorithm to lose its diversity,particularly in complex and constrained problems.Robot path planning problem is highly constrained and in the presence of a dense set of obstacles it becomes dif?cult to?nd a feasible solution.Diversity preservation is a key to the creation of feasible solutions and the proposed multi-objective GA is able to perform well in the dif?cult version of the problem.

5.6Three-objective path planning

So far,we have used a two-objective NSGA-II in which in addition to path length and path vulnerability objectives, we have introduced the path smoothness objective as a decision-maker.Thereafter,we have shown that a single-objective GA is not able to maintain diversity in the pop-ulation on its own and fails to?nd a feasible solution in complex constrained problems.

In this subsection,we study the effect of a truly three-objective NSGA-II with path smoothness as the third objective.For this purpose,we used the original NSGA-II procedure with crowding distance as the sole diversity preserving metric(Deb et al.2002).We consider the same sparse obstacle scenario as considered in Fig.6and use the integer-coding scheme to?nd trade-off paths.Again,a population of size500is used for500generations.The path smoothness is denoted by the total turn(summation of angles turned in the entire path)which is minimized to improve smoothness.Ten runs are taken and non-domi-nated three dimensional trade-off front is found from the combined solution set.Figure8a shows the obtained three-dimensional trade-off front and Fig.8b shows its projec-tion on length-vulnerability axes for a comparison with the two-objective front obtained earlier in Fig.6a.

The trade-off between the three objectives are clear from the?gure.A solution marked‘H’in both?gures indicates that although this solution is dominated with respect to path length and path vulnerability objectives,it is the best solution for the path smoothness objective.

Path smoothness is an objective,which on its own may not lead to an interesting path.To avoid twists and turns,an optimized path smoothness solution may be the one that prefers concatenation of a few straight-line segments(to avoid turns)to reach the destination.Figure9shows the path corresponding to path H marked in Fig.8.

Although in this simple scenario path H seems to be a reasonable solution,in more complex obstacle scenario the smoothest path may not even pass through the intermediate portion of the grid,but instead may prefer to lie along grid axes,depending on obstacle scenario.Such a path may become a trivial solution and of not much interest to an user.But in the presence of other two objectives,path smoothness may reveal solutions that are smooth as well as

1294 F.Ahmed,K.Deb 123

reasonable with respect to other two objectives.When the obtained trade-off solutions are projected on the path-vul-nerability plane (Fig.8b),the non-dominated front is found to be similar to that obtained using the two-objective study.This gives us con?dence about the accuracy of both two-and three-objective NSGA-II optimization approaches.However,although a few solutions with smooth paths are now obtained,this happens at the cost of the minimal path length solution which was found in the two-objective study.With a focus on all three objectives,the effect of a ?nite population size makes an emphasis to the interme-diate portion of the trade-off front,thereby losing the individual optimized solutions in some occasions.This is

the trade-off between one,two,and three-objective opti-mization approaches that we have observed here.1.

Single-objective optimization cannot keep diversity due to a singular focus and hence cannot ?nd a feasible solution in complex obstacle scenarios.

2.

Three-objective optimization can ?nd a three-dimen-sional trade-off frontier,but this may come at the expense of some individual optimized solutions.

3.

Two-objective optimization with third objective as a decision-maker seems to be adequate in obtaining the entire set of trade-off solutions.

Thus,if path smoothness is not an absolute necessity,we suggest using the modi?ed two-objective NSGA-II approach,whereas if the all three objectives are important,the three-objective original NSGA-II provides a good set of trade-off solutions.

Having established the fact that (i)obstacle avoidance constraint handling is better through the penalty function approach,(ii)multi-objective optimization is better than single-objective path planning approach,and (iii)a two-objective approach coupled with path smoothness as a decision-making aid is a better approach than considering all three objectives in the optimization problem,we are now ready to test the algorithm on increasingly dif?cult cases.

6Path planning under extreme conditions

An extreme test of a path planning algorithm proposed here is made for attempting to solve problems having a

large

Multi-objective optimal path planning using elitist NSGA-II 1295

123

grid size and a dense set of obstacles.When adequate spaces are available,multi-objective optimization algo-rithms can be used to?nd a set of trade-off solutions. However,when there are more obstacles than the available space in a grid,?nding a single feasible path is often a challenging task.Thus,in this section,we employ the two-objective NSGA-II proposed above,but terminate the run as soon as a feasible path is found.

We create increasingly higher grid size and increasingly dense obstacle scenarios in which obstacles are placed randomly on a two-dimensional grid.However,we make sure that there exists at least one feasible path from start to the destination point,so that the application of an optimi-zation algorithm is meaningful.To achieve this,we?rst generate a random valid path on the entire grid.Then,we randomly create obstacles with p0probability of occur-rence of obstacle in every cell except those lying on the above-generated path.Hence,a probability of p0=1 would mean that all grid cells have obstacles on them except the cells lying on the random path initially created. Such a problem would be a very dif?cult path planning problem to solve for any algorithm.To make the problems of different size,we use grid size that is varied to8,16,and 32.The probability p0is varied from0.1to1,as tabulated in Table1.

For all problems,the integer-coded representation scheme is used.For each problem,a population of size200 is used and the NSGA-II is run for a maximum of500 generations.The comparatively low computational cost is chosen here since the main objective of the study is only to ?nd a feasible solution and not the Pareto-optimal solu-tions.For each problem,100runs are taken and the per-centage of successful runs in?nding a feasible path from start to destination point,mean minimum path length obtained,and the median of generation numbers in which the?rst feasible path is obtained are noted.The?rst entry indicates the likelihood of?nding a feasible path,the

second entry denotes the ability to further minimize path length for feasible path while the third entry denotes how quickly the?rst feasible path is found on an average.

Figure10shows a few of the obtained solutions. Figure10d,for example,shows how in a large grid size and among a large density of obstacles,the proposed methodology is able to locate a feasible path,a task which looks apparently daunting.

There are several observations to be made from the table.First,as expected,as the grid size increases,the success percentage reduces;however,the proposed NSGA-II is able to still?nd the feasible path in all problems with 898and16916grids.The number of generations needed to?nd a feasible path is also reasonably small.

The second matter to note is that with16916grid problems;the proposed methodology is able to?nd a feasible path in a problem having a density of obstacles as large as233/(16916)or91%.This is a remarkable result.The third aspect to note is that as the density of the obstacles increase,the problem gets harder to solve and more generations are needed to locate a feasible path.

Third,for32932grid,Table1shows that the success percentage is less than100%for obstacle density of0.3or more.Since a population of size200is used,it is not adequate for32932grid problems.A larger population size would have yielded better performance,but instead of showing results with a higher population size for32932 grid problems,we use a population size of500for higher grid problems.

To investigate how the proposed bi-objective procedure will fair on even larger grid size problems,?nally we apply our methodology on a few64964and1289128grid Table1Path planning under different volumes of dense obstacles Grid

size

Obstacle

density,

p0

#of

obstacles

Success

percentage

(%)

Median

generations

Mean

min.

path

length 8980.1410029.90

0.210100210.49

0.315100210.49

0.420100210.49

0.526100511.07

0.631100411.07

0.740100511.07

0.843100611.07

0.950100711.07

1.054100711.07 169160.124100221.21

0.247100522.14

0.365100923.3

0.4801001822.34

0.51151002822.37

0.61501002222.57

0.71641002522.3

0.82861004022.13

0.92141004122.48

1.023*******

2.4 329320.181100647.08

0.21731001653.4

0.3253973853.72

0.4386857353.61

0.54703623054.38

0.65567414453.64

0.76664129553.9

0.87675229854.31

0.98703937854.13

1.09673033954.19

1296 F.Ahmed,K.Deb 123

(a)(b)

Fig.11Feasible paths for large

grid size problems obtained

using the proposed bi-objective procedure Multi-objective optimal path planning using elitist NSGA-II 1297123

problems with500population size and500generations. Figure11a shows two runs and the obtained feasible paths in both cases.Clearly,when4,979obstacles are scattered randomly on a two-dimensional grid(as shown in Fig.11b, it is impossible to obtain a feasible path manually. Although many other solutions may be possible in this case,our proposed algorithm is able to?nd one feasible path.

7Conclusions

In this paper,we have dealt with several issues of a two-dimensional path planning problem having various complexities using a soft computing approach.

First,we have suggested three path representation schemes for optimal path planning tasks to be solved by using a multi-objective genetic algorithm.The?exibility in their usage enables an ef?cient application of an evolu-tionary multi-objective optimization technique for the path planning problem.Of the three schemes,the integer-coded gene representation scheme that directly codes the relative movements of a vehicle from one column to the next has been found to yield best results.

Second,it has been observed that instead of considering three different criteria—path length,path vulnerability,and path smoothness—as objectives,the use of the?rst two as objectives and the third as a decision-making aid is a better option.This approach makes a good compromise between a single-objective approach which has been found to suffer from lack of diversity in a GA population and a three-objective NSGA-II approach which suffers from its concentration in the intermediate portion of the three-dimensional front.

Third,the above multi-objective consideration has been found to be better than a single-objective treatment of say path length or path vulnerability alone.

Fourth,compared with existing studies,the proposed two-objective approach has been shown to be more accu-rate in?nding feasible and trade-off paths.Particularly,the proposed approach has been demonstrated to work on large-sized grids having a dense set of obstacles(as high as 91%of the space),thereby demonstrating the ef?cacy of the proposed multi-objective optimization and novel rep-resentation scheme.Such results are rarely demonstrated in the literature.

While the existing past studies limited their studies to small-size grids,here we have shown that A GA-based two-objective approach can?nd feasible paths in grids as large as1289128and having as large as4,979obstacles occupying more than90%of the space by obstacles.These results remain as the hallmark achievement of this paper.

This paper can be extended to include non-monotonic paths along both axes which will make it a more practical scheme for real-world applications.Three-dimensional path planning can also be tried with minor modi?cations in the proposed integer-coded representation scheme.Never-theless,extensive simulation results of this study indicate that the current multi-objective technique is a reliable tool for a point-to-point,off-line path planning task and must be pursued further.

Acknowledgments The study is supported by JC Bose National Fellowship to Prof.K.Deb and Department of Science and Tech-nology,Government of India,under SERC-Engineering Sciences scheme(No.SR/S3/MERC/091/2009).Funding from Academy of Finland under grant133387for executing a part of this research is also appreciated.

References

Ahmed F,Deb K(2011)Multi-objective path planning using spline representation.In:Proceedings of the IEEE international conference on robotics and biomimetics(IEEE-ROBIO2011), Piscatway

Ahuja N,Chuang J(1997)Shape representation using a generalized potential?eld model.Pattern Analysis and Machine Intelligence.

IEEE Transactions on19(2):169–176

Al-Sultan KS,Aliyu MDS(2010)A new potential?eld-based algorithm for path planning.Journal of Intelligent&Robotic Systems17(3):265–282

Bisse E,Bentounes M,Boukas EK(1995)Optimal path generation for a simulated autonomous mobile robot.Autonomous Robots 2(1):11–27

Burchardt H,Saloman R(2006)Implementation of path planning using genetic algorithms on mobile robots.In:Proceedings of the World Congress on evolutionary computation(WCCI-2006), pp1831–1836

Castillo O,Trujillo L(2005)Multiple objective optimization genetic algorithms for path planning in autonomous mobile robots.

International Journal of Computers,Systems and Signals6(1): 48–63

Castillo O,Trujillo L,Melin P(2007)Multiple objective genetic algorithms for path-planning optimization in autonomous mobile robots.Soft Computing-A Fusion of Foundations,Methodolo-gies and Applications11(3):269–279

Choset H(1996)Sensor based motion planning:the hierarchical generalized Voronoi graph.PhD thesis,Citeseer

Connolly C,Burns J,Weiss R(1990)Path planning using laplace’s equation.In:Proceedings of IEEE international conference on robotics and automation.IEEE,pp2102–2106

Deb K(2000)An ef?cient constraint handling method for genetic 15a679f73169a4517623a3d0put Methods Appl Mech Eng186(2–4):311–338 Deb K(2001)Multi-objective optimization using evolutionary algorithms.Wiley,Chichester

Deb K,Agrawal RB(1995)Simulated binary crossover for contin-uous search 15a679f73169a4517623a3d0plex Systems9(2):115–148

Deb K,Goyal M(1998)A robust optimization procedure for mechanical component design based on genetic adaptive search.

Transactions of the ASME:Journal of Mechanical Design 120(2):162–164

Deb K,Gupta S(2011)Understanding knee points in bicriteria problems and their implications as preferred solution principles.

Engineering Optimization43(11):1175–1204

1298 F.Ahmed,K.Deb 123

Deb K,Agrawal S,Pratap A,Meyarivan T(2002)A fast and elitist multi-objective genetic algorithm:NSGA-II.IEEE Trans Evol Comput6(2):182–197

Elshamli A,Abdullah HA,Areibi S(2004)Genetic algorithms for dynamic path planning.In:Proceedings of IEEE Canadian conference on electrical and computer engineering(CCECE-04), pp677–680

Ge SS,Cui YJ(2002)Dynamic motion planning for mobile robots using potential?eld method.Autonomous Robots13(3):207–222 Gerke M(1999)Genetic path planning for mobile robots.In: Proceedings of the American control conference,vol4.IEEE, pp2424–2429

Glasius R,Komoda A,Gielen S(1995)Neural network dynamics for path planning and obstacle avoidance.Neural Networks8(1): 125–133

Hwang Y,Ahuja N(1992)Gross motion planninga survey.ACM Computing Surveys(CSUR)24(3):219–291

Kanayama Y,Hartman B(1997)Smooth local-path planning for autonomous vehicles.Int J Robot Res16(3):263

Khatib O(1986)Real-time obstacle avoidance for manipulators and mobile robots.Int J Robot Res5(1):90

LaValle S(2006)Planning algorithms.Cambridge University Press, Cambridge

Lozano-Pe′rez T,Wesley M(1979)An algorithm for planning collision-free paths among polyhedral 15a679f73169a4517623a3d0mun ACM 22(10):560–570

Murrieta-Cid R,Tovar B,Hutchinson S(2005)A sampling-based motion planning approach to maintain visibility of unpredictable targets.Autonomus Robots19(3):285–300

Oriolo G,Ulivi G,Vendittelli M(1997)Fuzzy maps:a new tool for mobile robot perception and planning.Journal of Robotic Systems14(3):179–197Pratihar D,Deb K,Ghosh A(1999)Fuzzy-genetic algorithms and time-optimal obstacle-free path generation for mobile robots.

Engineering Optimization32:117–142

Sauter J,Matthews R,van Dyke Parunak H,Brueckner S(2002) Evolving adaptive pheromone path planning mechanisms.In: Proceedings of the?rst international joint conference on autonomous agents and multiagent systems,part 1.ACM, pp434–440

Sugihara K,Smith J(1999)Genetic algorithms for adaptive planning of path and trajectory of a mobile robot in2D terrains.IEEE Transactions on Information and Systems82(1):309–317

Xiao M,Michalewicz Z(2000)An evolutionary computation approach to robot planning and navigation.Soft Computing in Mechatronics,pp117–128

Xue Q,Sheu PCY,Maciejewski AA,Chien SYP(2010)Planning of collision-free paths for a recon?gurable dual manipulator equipped mobile robot.Journal of Intelligent&Robotic Systems 17(3):223–242

Yang SX,Meng M(2000)Real-time collision-free path planning of robot manipulators using neural network approaches.Autono-mous Robots9(1):27–39

Zhang Q,Li H(2007)MOEA/D:A multiobjective evolutionary algorithm based on decomposition.Evolutionary Computation, IEEE Transactions on11(6):712–731

Zitzler E,Laumanns M,Thiele L(2001)SPEA2:improving the strength Pareto evolutionary algorithm for multiobjective opti-mization.In:Giannakoglou KC,Tsahalis DT,Pe′riaux J, Papailiou KD,Fogarty T(eds)Evolutionary methods for design optimization and control with applications to industrial prob-lems.International Center for Numerical Methods in Engineer-ing(CIMNE),Athens,Greece,pp95–100

Multi-objective optimal path planning using elitist NSGA-II1299

123

本文来源：https://www.bwwdw.com/article/rife.html