Grid-Based Path Planner Using Multivariant Optimization Algorithm

Danjv LvXinling ShiYufeng Zhangand Jianhua Chen

（1．School of Information Science and Engineering，Yunnan University，Kunming 650091，China；2．Oil Equipment Intelligent Control Engineering Laboratory of Henan Provice，Physics＆Electronic Engineering College，Nanyang Normal University，Nanyang Henan 473061，China；3．School of Information Technology and Engineering，Yuxi Normal University，Yuxi 653100，China）

Grid-Based Path Planner Using Multivariant Optimization Algorithm

Baolei Li1，2，Danjv Lv1，Xinling Shi1?，Zhenzhou An3，Yufeng Zhang1and Jianhua Chen1

（1．School of Information Science and Engineering，Yunnan University，Kunming 650091，China；2．Oil Equipment Intelligent Control Engineering Laboratory of Henan Provice，Physics＆Electronic Engineering College，Nanyang Normal University，Nanyang Henan 473061，China；3．School of Information Technology and Engineering，Yuxi Normal University，Yuxi 653100，China）

To solve the shortest path planning problems on grid-based map efficiently，a novel heuristic path planning approach based on an intelligent swarm optimization method called Multivariant Optimization Algorithm（MOA）and a modified indirect encoding scheme are proposed.In MOA，the solution space is iteratively searched through global exploration and local exploitation by intelligent searching individuals，who are named as atoms.MOA is employed to locate the shortest path through iterations of global path planning and local path refinements in the proposed path planning approach.In each iteration，a group of global atoms are employed to perform the global path planning aiming at finding some candidate paths rapidly and then a group of local atoms are allotted to each candidate path for refinement.Further，the traditional indirect encoding scheme is modified to reduce the possibility of constructing an infeasible path from an array.Comparative experiments against two other frequently use intelligent optimization approaches：Genetic Algorithm（GA）and Particle Swarm Optimization（PSO）are conducted on benchmark test problems of varying complexity to evaluate the performance of MOA.The results demonstrate that MOA outperforms GA and PSO in terms of optimality indicated by the length of the located path.

multivariant optimization algorithm；shortest path planning；heuristic search；grid map；optimality of algorithm

1 Introduction

Path planning on grid-based maps is an essential task in mini-unmanned aerial vehicle［1］，mobile robot navigation［2］，and video games［3］and so on.The objective of the shortest path planning（SPP）is to find out the shortest feasible path（optimal solution）from a starting position to a destination position among all paths（solution space）between these two positions whilst avoiding all obstacles.Thus，the shortest path planning is a constrained optimization problem［4］. When the complexity of the environment increases，traditional methods such as methods based on potential field require excessive computational time［5-6］，which makes them suffer from serious performance bottlenecks［7］.Given that the intelligent optimization algorithms are quickly convergent［8］，robust and flexible［9］，many intelligent approaches such as the ant colony algorithm［10］，genetic algorithm（GA）［11-12］and particle swarm optimization（PSO）［13］have been applied to solve the path planning problems.These intelligent optimization algorithms have represented a great improvement over traditional approaches［14］. However，there is room for improvement because they are likely to fall into local optima［15-16］.

To improve the quality of solution through enhancing the ability of escaping from local traps，a novel intelligent path planner based on Multivariant Optimization Algorithm（MOA）is proposed in this paper.In MOA，the solution space is iteratively searched through alternating global exploration and local exploitation by intelligent agents named as atoms. The global exploration is carried out by global atoms which are generated in the whole solution space；the local exploitation is implemented by the local atoms which are generated in each niche of better global atoms.MOA is characterized by that global atoms have the global view ability while local atoms have local refinement ability［17］，which makes it suitable for solving SPP problems.The global and local atoms have variety of characters in responsibility and the global atoms in different areas represent multiple solutions，thus the proposed algorithm is named as Multivariant Optimization Algorithm.In each iteration of the MOA-based shortest path planning approach，candidate paths（intermediate solution）are located by global atoms through exploring the whole map and then the candidate paths are refined by multiple local atom groups with different numbers of local atoms.The motivations of using local atom groups with different population size are that more local atoms should be allotted to the shorter candidate path for a high level refinement and vice versa.From the searching strategy of MOA，it can be seen that the shortest feasible path（optimal solution）can be obtained through improving the intermediate solution iteratively.

A key issue of applying optimization algorithms in path planning is how to construct a path from an array efficiently.Previously，two encoding techniques have been widely used in the construction of a path，i.e. direct and indirect encoding，which had been described in detail in Ref.［18］.In this study，a modified version of the indirect encoding technique is presented to improve the efficiency through reducing the possibility of constructing infeasible path.

To evaluate the efficiency of the proposed MOA-based path planning method，experiments on benchmark problem sets［19］in a commercial video games named Dragon Age：Origins（DAO），are conducted by using MOA，GA and PSO.The performance of investigated methods is observed and evaluated based on path length carves against the number of iterations.It is observed that the solution quality in MOA gradually grows and surpasses those in GA and PSO as the number of iterations increases，which shows the superior performance of the proposed method in optimality.

2 Multivariant Optimization Algorithm

To locate the optimal solution，the solution space is searched through the alternating global exploration and local exploitation iterations based on a data structure which is made up of a queue and some stacks. In each iteration of MOA，the global atoms are generated in the whole solution space for a global exploration firstly.Secondly，a group of local atoms are generated in each neighborhood of the global atoms in the queue for local exploitations.Thirdly，the new generated atoms are evaluated according to the handling problem.Fourthly，the queue of the structure is updated to record the potential areas，which is to be exploited in the next iteration.The pseudo of MOA is given in Algorithm 1 whereDsis the data structure used for storing and managing the atoms’information，andDs（i，j）．Ais an atom stored in rowicolumnjandDs（i，j）．Fvis its fitness value which is calculated in the step of evaluating new generated atoms，andTqis a temp queue used to temporarily store the information of the prior generation global atoms.Details about the atom and data structure are provided in the following sections.

2.1 Atoms

In MOA，an intelligent agent represented by an array is named as an atom.To give consideration to both the global exploration and the local exploitation，atoms are divided into two types：global exploration atoms and local exploitation atoms.The global exploration atoms are generated uniformly at random in the whole solution space for a global view of the environment and the local exploitation atoms are generated in the neighborhood of the global atom for local exploitation.In ann-dimensional search space，the global search atomAgis generated according to Eq.（1）.

wherelianduiare the lower and the upper bounds of theithdimension of the search space；the function unifrnd（li，ui）returns a random number which is uniformly distributed on the interval fromlitoui．

A local search atomAlin the neighborhood of a global atomAgis generated according to Eq.（2）.

wherehi（i＝1，2…，n）are random numbers uniformly distributed on［-1，1］，and the neighborhood is a circle in a fixed radiusraround the centerAg．

The fitness value of an atom is the quality of the solution achieved from the atom according to an encode scheme.In the proposed method，the fitness value of an atom is just the length of the path constructed by it according to the encode scheme.

From Algorithm 1，it can be seen that the atom in the queue is the center of a potential area，which will be exploited in the next iteration and the position of it determines the exploitation level.

2.2 Data Structure of MOA

The iteration of MOA is managed by a data structure illustrated in Fig.1.It can be seen that there is a horizontal sorted doubly-linked list and each of its nodes points to a vertical sorted doubly-linked list in the data structure.To simplify the description，the horizontal sorted doubly-linked list and the vertical sorted doubly-linked list are named as the queue and the stack，respectively.

Fig.1 Data structure of MOA

The update of the queue is the core of MOA，because it determines the search strategies in the next iteration.The pseudo of updating of the queue is given in Algorithm 2 whereDsis the data structure.Tlis a temple list used to temporarily store the global atoms.Tlfv（i）records the fitness values of the atom：Tl（i）．A．the function sort（Tlfv）returns an index vector of values inTlfvin ascending order.Tqis a temp queue used to temporarily store the information of the prior generation global atoms.

From Algorithm 2，it can be seen that atoms compete to be stored in the queue according to their fitness values.After some alternating global-local search iterations，the better solutions are all remembered in the queue.

3 Problem Formulation and Path Encoding Scheme

3.1 Problem Formulation

In this paper，the path planning problem is to be implemented on grid-based maps where tiles are indexed by their row and column numbers.On the map，diagonal and cardinal movements to free tiles are allowed.To calculate the path length，it is assumed that the step length of per diagonal and cardinal movement is2and 1，respectively.The length of a path is calculated by adding up the lengths for all steps needed to move from the start to the end along the path.To simplify the description，the following map illustrated in Fig.2 is used as a demo through our description.Where the black tiles are obstacles and the white tiles are free tiles，“S”and“D”stand for the starting and ending positions，respectively.

Fig.2 A demo map with 6 rows and 6 columns

3.2 Modified Indirect Encoding Scheme

Recently，two typical encoding techniques，which are direct and indirect，have been used for path encoding in solving the SPP problems by optimization algorithms.In the direct representation scheme，the chromosome in the GA or the particle position in the PSO is represented by the sequence of the tiles’positions in a path.In the indirect encoding scheme，some guiding information“priorities”about the tiles are used to represent the path.The path is constructed by keeping on adding the available tiles with the highest priority into the path until the destination tile is reached.Details about these two types of encoding techniques can be found in Ref.［18］.

In MOA-based shortest path planning algorithm，the atom is represented by randomly selected tiles and the path is constructed by a visibility graphic of the selected tiles.An atom containingntiles is encoded into a 2nlength integer string as illustrated in Fig.3，whereRiandCiare the row number and column number of theithtile in an atom，respectively.

Fig.3 Representation scheme for an atom

To construct a path from an atom，the atom should be decoded to get some guiding information“priorities”.The steps of constructing a path for the demo atom shown in Fig.4 are as follows：

Step 1Set up the visibility graphic（VG）．AVGis a graph（V，E）whereVis the set of tiles including starting tile，destination tile and tiles in the atom andEare the set of all edges connecting any two tiles inVthat do not pass through any obstacles.The weight of an edge connecting two tilest（x1，y1）andt（x2，y2）is their distance which is calculated by Eq.（3）.

wherexiandyiare the row and column number of the tailt（xi，yi）（i＝1，2），respectively.The visibility graphic of the demo is shown in Fig.5.

Step 2Construct the shortest path according to the visibility graphic generated in Step 1.The pseudocode for constructing the shortest path of the demo is shown in Algorithm 3 whereLis a list storing the tiles having a chance to be expanded in the next loop，andhis an array whereh（i）records the shortest distance from theithtile to the destination，andNextis an array whereNext（i）records the optimal tile from theithtile，andNis the index number of the selected tile to be expanded in the next loop，andcListis an array recording the visible tiles of the selected tile indexed byN，Precords the constructed path，the starting tile and the destination tile are indexed by 4 and 5，respectively.After the search of visibility graphic in Step 2，the path can be yielded by going on adding the optimal tile（recorded inNext）of each tile into the path from the starting tile until the destination tile is reached or the number inNextis 0.The path is infeasible if it cannot lead us to the destination tile.

Fig.4 Encoding scheme of the demo atom

Fig.5 Visibility graphic of the demo

4 Path Planner Based on MOA

Based on the aforementioned problem formulation and path encoding scheme，MOA is employed to locate the shortest path through iterations of global path planning and local path refinement.Specifically，rough feasible paths are located after the global atoms view the whole map and then multiple local groups with different population are allotted to them for different levels of local exploitations with the aim of improving them efficiently.In each iteration，firstly，global atoms are generated in the whole map for global path planning.Secondly，local atoms are generated in the neighborhoods of global atoms for local path refinement. Thirdly，new exploration information is achieved by the evaluations of new generated atoms.Fourthly，the queue is updated according to the historical and new exploration information to guide the local path refinements in the next iteration.The algorithm stops when a predefined maximum number of iteration is reached.

The pseudo code of MOA based shortest path planning is shown in Algorithm 4.Details of global path planning，local path refinement，fitness evaluation and queue update are provided as follows：

The details of main operations in Algorithm 4 are as follows：

1）Global Path Planning：the global path planning is implemented by generating global atoms in the whole environment.The tiles in global atoms are selected at random and they have a uniform distribution in the whole map.Rough paths can be constructed from the global atoms which have a global view of the environment.

2）Local Path Refinement：a group of local atoms are generated in the neighborhood of a global atom in the queue for local exploitation aiming at refining the path constructed by the global atom.The neighborhood is a circle area with center at the global atom and a fixed radius which determines the scope of the neighborhood.The number of local atoms in a group is determined by the depth of the stack where they will be stored.It is obviously that the group with larger number of local atom can carry out a higher level local exploitation.

3）Fitness Evaluation：the length of a path constructed by an atom serves as the fitness value of the atom.The shorter the path is the better the atom is.The length of a constructed path is calculated by Eq.（4）.

wherePis the path；P（i）is theithtile inP，Pis considered infeasible if it can not guide us to the destination.

4）Queue Update：as shown in Algorithm 2，the update of the queue is a two stage operation.Firstly，theithglobal atom in the queue will be replaced by the atom in theithstack if its fitness value is larger than the fitness value of the atom in theithstack.Secondly，the new generated atoms and atoms in the queue are sorted according to their fitness values and then the better ones are inserted into the queue in order.

From the process of MOA，it can be seen that the management of multiple search groups increases the complexity of MOA compared with GA and PSO. However，the increased complexity is negligible because of the strong computational power of recent computers.

5 Experiment

5.1 Experimental Environment

In this paper，tests on six 0-1 grid-based benchmark game（Dragon Age：Origins）maps are carried out by using Matlab 7.8（The Mathworks，Inc.，Natick，MA，USA）on the PC with a 1.6-GHz Intel Processor and 2.0-GB RAM.For each map，one of the benchmark test set problems given in Ref.［19］is chosen as the testing problem where there exists a shortest path with the length from 50 to 60.Details of these testing problems are listed in Table 1.

Table 1 Testing problems

These testing maps are illustrated in Fig.6 where astraight dash is drawn from the starting tile to the destination tile.From Fig.6，it can be seen that the problems can be roughly classified into two types according to their complexity.Problems in arena，den204d and den901d are considered as simple problems where the optimal paths are a little curve and the others are treated as complex problems where the optimal paths are zigzag.

5.2 Parameters Setup

To illustrate the strength of MOA，GA and PSO are chosen as the comparison methods implemented through using PSO toolbox and GA toolbox.These algorithms stop when a maximum of 100 iterations is reached.All the investigative methods have the same population size and dimension which are 20 and 12，respectively.They also use the same encoding scheme and fitness function.The used parameters of GA are from Ref.［20］where single point uniform cross-over with the rate of 0.8，ranking selection with the elite retention strategy and Gaussian mutation with the rate of 0.01.The best parameters of PSO suggested in the conclusion of Ref.［21］are as follows：the additional inertia weight is 0.729.The learning factors are set to 1.494.

To compare the performance of these algorithms fairly，50 independent tests are carried out on each problem and the averaged path length curves against the number of iterations are plotted.The performance of all compared algorithms is measured in terms of the optimality of the located optimal solution which is indicated by the path length.The algorithm obtaining the shortest path length is considered to be the best in optimality.Further，the reason behind the result is also discussed according to the averaged path length curves against the number of iterations.

Fig.6 Benchmark maps and problems

6 Results and Discussion

6.1 Iterative Process of MOA

In order to make the whole process of MOA clearer，the paths encoded by global atoms at the first，33rd，66thand 100thiteration are illustrated in Fig.7. The path planning problem in the map named arena is chosen because there are multiple global optima in this problem.Comparison between the results at the first iteration and that at the 33rditeration shows that there is no feasible path at the first iteration and some feasible paths are achieved after 33 iterations，which suggests that the path planner based on MOA is effective in planning multiple feasible paths after some iterations of global exploration and local exploitation. Comparison between the results at the 66rditeration and that at the 100thiteration shows that the paths achieved at the 66rditeration are improved during 44 iterations. Obviously，the path planner based on MOA can movetoward the global optima through improving the optimality of intermediate solutions.It is worth noting that the path planner based on MOA has the ability to provide multiple solutions，thus，the name of MOA matches the reality.

6.2 Comparison Among GA PSO and MOA

To show the good performance of MOA，the curves of average path length against iteration number achieved by using GA，PSO and MOA are illustrated in Fig.8.

Fig.7 Paths planed at the first，33rd，66thand 100thiteration

Fig.8 Average path length versus number of iterations

On simple problems including arena，den204d and den901d，after 100 iterations，the paths located by MOA and PSO are shorter than those obtained by GA，which shows the optimality of the solution located in MOA.From the averaged path length curve in the first column of Fig.8，it can be seen that MOA and PSO keep on improving the located path but GA stops improving the path.This suggests that GA is more likely to be trapped into local optima and cause premature convergence than MOA and PSO.The reasons are as follows：the diversity of chromosomes in GA decreases when the iteration number increases，which enhances its local exploitation at the cost of reducing global exploration，as a result，GA can hardly jump out of local traps only by means of mutation operator at the end of search；the global exploration in MOA is carried out by global atoms at the beginning of each iteration，thus，the global exploration will not be influenced by the local exploitation and will not decrease when the iteration number increases.

On complex problems including den009d，den202d and den403d，the paths located by MOA are shorter than those obtained by GA and PSO；this demonstrates that MOA outperforms GA and PSO in the optimality of the located solution.From the averaged path length curve in the second column of Fig.8，it can be seen that both GA and PSO stop improving the historical located path after about 20 iterations but MOA gradually improves it.As a result，MOA obtains the shortest path after 100 iterations.The reason is that GA and PSO are easy to be trapped into local optima and cause premature convergence，so the increase ofiterations dose not contribute to improving the historical located path.However，MOA explores the solution space not at the beginning of the algorithm but at the beginning of each iteration，which prevents the global exploration ability from degeneration in the wake of the decrease of population diversity.To be specific，once the global atoms find better areas than local traps，the atoms in the local traps will be eliminated from the structure in the update queue step and new atoms will be generated in these better areas in the local path refinement step.

7 Conclusions

The grid-based path planner using multivariant optimization algorithm is proposed to solve the shortest planning problems in this paper.It is characterized by powerful global and local search ability and new solution encoding scheme.The proposed algorithm is tested on benchmark test sets and compared with two other popular swarm optimization algorithms，and the experimental results show that MOA has the ability to provide multiple solutions and outperforms GA and PSO in optimality indexed by the obtained path length especially on complex problems.MOA is a promising candidate method for shortest path planning problems on grid-based maps.

Applying the proposed method to solve SSP problems in dynamic environments，it needs more steps to extend the current work.The multiple paths obtained by MOA-based planner will be users’alternative solutions when the optimal path becomes infeasible in dynamic environments.

［1］Hong Ye，F(xiàn)ang Jiancheng.Development of ground control station and path planning for autonomous MUAV.Journal of Harbin Institute of Technology（New Series），2010，17（6）：789-794.

［2］Raja P，Pugazhenthi S.Optimal path planning of mobile robots：a review.International Journal of Physical Sciences，2012，7（9）：1314-1320.

［3］Mocholi J A，Jaen J，Catala A，et al.An emotionally biased ant colony algorithm for pathfinding in games.Expert Systems with Applications，2010，37（7）：4921-4927.

［4］Liang J J，Song H，Qu B Y.Performance evaluation of dynamic multi-swarm particle swarm optimizer with different constraint handling methods on path planning problems.Proceedings of IEEE Workshop on Memetic Computing.Piscataway：IEEE，2013.65-71.

［5］Barraquand J，Langlois B，Latombe J C.Numerical potential field techniques for robot path planning.IEEE Transactions on Systems，Man and Cybernetics，1992，22（2）：224-241.

［6］Yu Zhenzhong，Yan Jihong，Zhao Jie，et al.Mobile robot path planning based on improved artificial potential field method.Journal of Harbin Institute of Technology，2011，43（1）：50-55.（in Chinese）

［7］Botea A，Müller M，Schaeffer J.Near optimal hierarchical path-finding.Journal of Game Development，2004，1（1）：7-28.

［8］Gao Fang，Zhao Qiang，Li Guixian.Path planning of continuum robot based on a new improved particle swarm optimization algorithm.Journal of Harbin Institute of Technology（New Series），2013，20（4）：78-84.

［9］Gong Yuejiao，Shen M，Zhang Jun，et al.Optimizing RFID network planning by using a particle swarm optimization algorithm with redundant reader elimination.IEEE Transactions on Industrial Informatics，2012，8（4）：900-912.

［10］Jin Feihu，Gao Huijun，Zhong Xiaojian.Research on path planning of robot using adaptive ant colony system.Journal of Harbin Institute of Technology，2010，42（7）：1014-1018.（in Chinese）

［11］Piao Songhao，Hong Bingrong.Robot path planning using genetic algorithms.Journal of Harbin Institute of Technology（New Series），2001，8（3）：215-317.

［12］Gemeinder M，Gerke M.GA-based path planning for mobile robot systems employing an active search algorithm. Applied Soft Computing，2003，3（2）：149-158.

［13］Qin Yuanqing，Sun Debao，Li Ning，et al.Path planning for mobile robot using the particle swarm optimization with mutation operator，2004.Proceedings of the IEEE Internat ional Conference on Machine Learning and Cybernetics. Piscataway：IEEE，2004.2473-2478.

［14］Sooda K，Nair T R.A comparative analysis for determining the optimal path using PSO and GA.International Journal of Computer Applications，2011，32（4）：8-12.

［15］Qi Yong，Wei Zhiqiang，Yin Bo，et al.Path planning optimization based on reinforcement of artificial potential field.Journal of Harbin Institute of Technology，2009，41（3）：130-133.（in Chinese）

［16］Zhan Zhihui，Zhang Jun.Discrete particle swarm optimization for multiple destination routing problems. Applications of Evolutionary Computing.Heidelberg：Springer，2009.117-122.

［17］Li Baolei，Shi Xinling，Gou Changxing，et al.Multivariant optimization algorithm for multimodal optimization. Proceedings of the International Conference on Mechanical Engineering，Materials and Energy.Switzerland：Trans Tech Publications Ltd.，2014.453-457.

［18］Mohemmed A W，Sahoo N C，Geok T K.Solving shortest path problem using particle swarm optimization.Applied Soft Computing，2008，8（4）：1643-1653.

［19］Sturtevant N R.Benchmarks for grid-based path finding. IEEE Transactions on Computational Intelligence and AI in Games，2012，4（2）：144-148.

［20］Sugihara K，Smith J.Genetic algorithms for adaptive motion planning of an autonomous mobile robot. Proceedings of the 1997 IEEE International Symposium on Computational Intelligence in Robotics and Automation. Piscataway：IEEE，1997.138-143.

［21］Eberhart R C，Shi Y.Comparing inertia weights and constriction factors in particle swarm optimization. Proceedings of the IEEE Congress on Evolutionary Computation.Piscataway：IEEE，2000.84-88.

TP24

：

：1005-9113（2015）05-0089-08

10.11916／j.issn.1005-9113.2015.05.014

2014-05-24.

Sponsored by the National Natural Science Foundation of China（Grant No.61261007，61002049），and the Key Program of Yunnan Natural Science Foundation（Grant No.2013FA008）.

?Corresponding author.E-mail：xlshi＠ynu.edu.cn.