摘要: Search with Subgoal Graphs (Uras, Koenig, and Hernandez 2013) was a non-dominated optimal path-planning algorithm in the Grid-Based Path Planning Competitions 2012 2013. During preprocessing phase, it computes Simple Graph from given grid, which is analogous to visibility graph for continuous terrain, then partitions vertices into global local subgoals obtain Two-Level Graph. performs an A* search that ignores are not relevant search, significantly reduces size of being searched. In this paper, we generalize partitioning process any undirected show can be recursively applied generate more than two levels, searched even further. We distinguish between basic partitioning, only different advanced also add new edges. construction Simple-Subgoal grids instances generalized partitioning. report on experiments demonstrate effects types levels our N-Level achieve speed up 1.6 compared graphs maps video games StarCraft Dragon Age: Origins.
参考文章(12)
Yngvi Björnsson, Kári Halldórsson, Improved heuristics for optimal pathfinding on game maps national conference on artificial intelligence. pp. 9- 14 ,(2006)
Nathan R. Sturtevant, Ariel Felner, Neil Burch, Jonathan Schaeffer, Max Barrer, Memory-based heuristics for explicit state spaces international joint conference on artificial intelligence. pp. 609- 614 ,(2009)
Sabine Storandt, Contraction Hierarchies on Grid Graphs 36th Annual German Conference on AI (KI 2013). pp. 236- 247 ,(2013) , 10.1007/978-3-642-40942-4_21
Nir Pochter, Jeffrey S. Rosenschein, Ariel Felner, Aviv Zohar, Search space reduction using swamp hierarchies national conference on artificial intelligence. pp. 155- 160 ,(2010)
Tristan Cazenave, Optimizations of data structures, heuristics and algorithms for path-finding on maps computational intelligence and games. pp. 27- 33 ,(2006) , 10.1109/CIG.2006.311677
R. C. Holte, C. Drummond, M. B. Perez, R. M. Zimmer, A. J. MacDonald, Searching With Abstractions: A Unifying Framework and New High-Performance Algorithm 1 ,(1994)
Wheeler Ruml, Robert C. Holte, Michael J. Leighton, Faster optimal and suboptimal hierarchical search annual symposium on combinatorial search. ,(2011)
Robert Geisberger, Peter Sanders, Dominik Schultes, Daniel Delling, Contraction hierarchies: faster and simpler hierarchical routing in road networks WEA'08 Proceedings of the 7th international conference on Experimental algorithms. pp. 319- 333 ,(2008) , 10.1007/978-3-540-68552-4_24
Nathan Sturtevant, Michael Buro, Partial pathfinding using map abstraction and refinement national conference on artificial intelligence. pp. 1392- 1397 ,(2005)
Nathan R. Sturtevant, Ariel Felner, Meir Goldenberg, Jonathan Schaeffer, Portal-Based True-Distance Heuristics for Path Finding annual symposium on combinatorial search. ,(2010)