Abstract:A new single-boundary rectangle expansion A* (REA*) algorithm is presented. The new algorithm adopts the forced expansion rule, and the two redundant adjacent boundaries between adjacent rectangles are replaced with a shared boundary during the process of exploring map in rectangular units, which will improve the efficiency, simplify the termination conditions and optimize the quality of the result paths. Without any offline pre-processing, the new algorithm can speed up a highly optimized A* algorithm by an order of magnitude and more. The algorithm guarantees the grid-optimal path point sequence, while the final result path (which consists of the straight lines between path points) is always shorter than grid-optimal path. Experimental results on typical benchmark problem sets show that compared with the existing REA* algorithms, the ability to deal with complex maps and the upper limit of the algorithm efficiency are improved by the proposed algorithm. The shorter result paths and less turning points are achieved with the proposed algorithm, so the quality of result paths are better. The average speed of the proposed algorithm is also better than that of REA*, except in the low complex and low open maps.
[1] Hart P E, Nilsson N J, Raphael B. A formal basis for the heuristic determination of minimum cost paths[J]. IEEE Transactions on Systems Science and Cybernetics, 1968, 4(2):100-107.
[2] Harabor D, Botea A, Kilby P. Path symmetries in undirected uniform-cost grids[C]//Proceedings of the 9th Symposium on Abstraction, Reformulation, and Approximation. Menlo Park, USA:AAAI Press, 2011:58-61.
[3] Harabor D, Botea A. Breaking path symmetries on 4-connected grid maps[C]//Proceedings of the 6th Artificial Intelligence and Interactive Digital Entertainment Conference. Menlo Park, USA:AAAI Press, 2010:33-38.
[4] Harabor D. Graph pruning and symmetry breaking on grid maps[C]//Proceedings of the 22nd International Joint Conference on Artificial Intelligence. Menlo Park, USA:AAAI Press, 2011:2816-2817.
[5] Yap P, Burch N, Holte R, et al. Block A*:Database-driven search with applications in any-angle path-planning[C]//Proceedings of the 25th AAAI Conference on Artificial Intelligence. Menlo Park, USA:AAAI Press, 2011:120-125.
[6] Harabor D, Grastien A. Online graph pruning for pathfinding on grid maps[C]//Proceedings of the 25th AAAI Conference on Artificial Intelligence. Menlo Park, USA:AAAI Press, 2011:1114-1119.
[7] Harabor D, Grastien A. Improving jump point search[C]//Proceedings of the 24th International Conference on Automated Planning and Scheduling. Menlo Park, USA:AAAI Press, 2014:128-135.
[8] Uras T, Koenig S, Hernández C. Subgoal graphs for optimal pathfinding in eight-neighbor grids[C]//Proceedings of the 23rd International Conference on Automated Planning and Scheduling. Menlo Park, USA:AAAI Press, 2013:24-32.
[9] Botea A. Ultra-fast optimal pathfinding without runtime search[C]//Proceedings of the 7th AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment. Menlo Park, USA:AAAI Press, 2011:122-127.
[10] Botea A. Fast, optimal pathfinding with compressed path databases[C]//Proceedings of the 5th Annual Symposium on Combinatorial Search. Menlo Park, USA:AAAI Press, 2012:204-205.
[11] Botea A, Harabor D. Path planning with compressed all-pairs shortest paths data[C]//Proceedings of the 23rd International Conference on Automated Planning and Scheduling. Menlo Park, USA:AAAI Press, 2013:293-297.
[12] Strasser B, Harabor D, Botea A. Fast first-move queries through run-length encoding[C]//Proceedings of the 7th Annual Symposium on Combinatorial Search. Menlo Park, USA:AAAI Press, 2014:157-165.
[13] Nash A, Koenig S. Any-angle path planning[J]. AI Magazine, 2013, 34(4):85-107.
[14] Daniel K, Nash A, Koenig S, et al. Theta*:Any-angle path planning on grids[J]. Journal of Artificial Intelligence Research, 2010, 39(1):533-579.
[15] Nash A, Koenig S, Tovey C. Lazy theta*:Any-angle path planning and path length analysis in 3D[C]//Proceedings of the 3rd Annual Symposium on Combinatorial Search. Menlo Park, USA:AAAI Press, 2010:153-154.
[16] Thorpe C E, Matthies L H. Path relaxation:Path planning for a mobile robot[C]//Proceedings of the 4th National Conference on Artificial Intelligence. Menlo Park, USA:AAAI Press, 1983:318-321.
[17] Zhang A, Li C, Bi W. Rectangle expansion A* pathfinding for grid maps[J]. Chinese Journal of Aeronautics, 2016, 29(5):1385-1396.
[18] Sturtevant N R. Benchmarks for grid-based pathfinding[J]. IEEE Transactions on Computational Intelligence and AI in Games, 2012, 4(2):144-148.
[19] Sturtevant N R. The grid-based path planning competition[J]. AI Magazine, 2014, 35(3):66-69.