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) an...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.展开更多
Search speed, quality of resulting paths and the cost of pre-processing are the principle evaluation metrics of a pathfinding algorithm. In this paper, a new algorithm for grid-based maps, rectangle expansion A＊ （RE...Search speed, quality of resulting paths and the cost of pre-processing are the principle evaluation metrics of a pathfinding algorithm. In this paper, a new algorithm for grid-based maps, rectangle expansion A＊ （REA＊）, is presented that improves the performance of A＊ significantly. REA＊ explores maps in units of unblocked rectangles. All unnecessary points inside the rectangles are pruned and boundaries of the rectangles （instead of individual points within those boundaries） are used as search nodes. This makes the algorithm plot fewer points and have a much shorter open list than A＊. REA＊ returns jump and grid-optimal path points, but since the line of sight between jump points is protected by the unblocked rectangles, the resulting path of REA＂ is usually better than grid-optimal. The algorithm is entirely online and requires no offline pre-processing. Experimental results for typical benchmark problem sets show that REA＊ can speed up a highly optimized A＊ by an order of magnitude and more while preserving completeness and optimality. This new algorithm is competitive with other highly successful variants of A＊.展开更多
基金Sponsored by the National Natural Science Foundation of China(Grant No.61261007,61002049)the Key Program of Yunnan Natural Science Foundation(Grant No.2013FA008)
文摘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.
基金supported by the National Natural Science Foundation of China (No.61573283)
文摘Search speed, quality of resulting paths and the cost of pre-processing are the principle evaluation metrics of a pathfinding algorithm. In this paper, a new algorithm for grid-based maps, rectangle expansion A＊ （REA＊）, is presented that improves the performance of A＊ significantly. REA＊ explores maps in units of unblocked rectangles. All unnecessary points inside the rectangles are pruned and boundaries of the rectangles （instead of individual points within those boundaries） are used as search nodes. This makes the algorithm plot fewer points and have a much shorter open list than A＊. REA＊ returns jump and grid-optimal path points, but since the line of sight between jump points is protected by the unblocked rectangles, the resulting path of REA＂ is usually better than grid-optimal. The algorithm is entirely online and requires no offline pre-processing. Experimental results for typical benchmark problem sets show that REA＊ can speed up a highly optimized A＊ by an order of magnitude and more while preserving completeness and optimality. This new algorithm is competitive with other highly successful variants of A＊.
