In computer science, jump point search (JPS) is an optimization to the A* search algorithm for uniform-cost grids. It reduces symmetries in the search procedure by means of graph pruning,[1] eliminating certain nodes in the grid based on assumptions that can be made about the current node's neighbors, as long as certain conditions relating to the grid are satisfied. As a result, the algorithm can consider long "jumps" along straight (horizontal, vertical and diagonal) lines in the grid, rather than the small steps from one grid position to the next that ordinary A* considers.[2]
Jump point search preserves A*'s optimality, while potentially reducing its running time by an order of magnitude.[1]
Historyedit
Harabor and Grastien's original publication provides algorithms for neighbor pruning and identifying successors.[1] The original algorithm for neighbor pruning allowed corner-cutting to occur, which meant the algorithm could only be used for moving agents with zero width, limiting its application to either real-life agents (e.g., robotics) or simulations (e.g., many games).
The authors presented modified pruning rules for applications where corner-cutting is not allowed the following year.[3] This paper also presents an algorithm for pre-processing a grid in order to minimize online search times.
A number of further optimizations were published by the authors in 2014.[4] These optimizations include exploring columns or rows of nodes instead of individual nodes, pre-computing "jumps" on the grid, and stronger pruning rules.
Future workedit
Although jump point search is limited to uniform cost grids and homogeneously sized agents, the authors are placing future research into applying JPS with existing grid-based speed-up techniques such as hierarchical grids.[4][5]
Referencesedit
^ abcD. Harabor; A. Grastien (2011). Online Graph Pruning for Pathfinding on Grid Maps(PDF). 25th National Conference on Artificial Intelligence. AAAI.
^Witmer, Nathan (5 May 2013). . zerowidth positive lookahead. Archived from the original on 2014-03-10. Retrieved 10 March 2014.
^D. Harabor; A. Grastien (2012). . 26th National Conference on Artificial Intelligence. AAAI. Archived from the original on 2020-11-09. Retrieved 2015-07-11.
^ abHarabor, Daniel; Grastien, Alban. "Improving Jump Point Search" (PDF). Australian National University College of Engineering and Computer Science. Association for the Advancement of Artificial Intelligence (www.aaai.org). Retrieved 11 July 2015.
^Adi Botea; Martin Muller (2004). "Near Optimal Hierarchical Path-Finding" (PDF). University of Alberta. University of Alberta.
April 14, 2024
jump, point, search, computer, science, jump, point, search, optimization, search, algorithm, uniform, cost, grids, reduces, symmetries, search, procedure, means, graph, pruning, eliminating, certain, nodes, grid, based, assumptions, that, made, about, current. In computer science jump point search JPS is an optimization to the A search algorithm for uniform cost grids It reduces symmetries in the search procedure by means of graph pruning 1 eliminating certain nodes in the grid based on assumptions that can be made about the current node s neighbors as long as certain conditions relating to the grid are satisfied As a result the algorithm can consider long jumps along straight horizontal vertical and diagonal lines in the grid rather than the small steps from one grid position to the next that ordinary A considers 2 Jump point search preserves A s optimality while potentially reducing its running time by an order of magnitude 1 History editHarabor and Grastien s original publication provides algorithms for neighbor pruning and identifying successors 1 The original algorithm for neighbor pruning allowed corner cutting to occur which meant the algorithm could only be used for moving agents with zero width limiting its application to either real life agents e g robotics or simulations e g many games The authors presented modified pruning rules for applications where corner cutting is not allowed the following year 3 This paper also presents an algorithm for pre processing a grid in order to minimize online search times A number of further optimizations were published by the authors in 2014 4 These optimizations include exploring columns or rows of nodes instead of individual nodes pre computing jumps on the grid and stronger pruning rules Future work editAlthough jump point search is limited to uniform cost grids and homogeneously sized agents the authors are placing future research into applying JPS with existing grid based speed up techniques such as hierarchical grids 4 5 References edit a b c D Harabor A Grastien 2011 Online Graph Pruning for Pathfinding on Grid Maps PDF 25th National Conference on Artificial Intelligence AAAI Witmer Nathan 5 May 2013 Jump Point Search Explained zerowidth positive lookahead Archived from the original on 2014 03 10 Retrieved 10 March 2014 D Harabor A Grastien 2012 The JPS Pathfinding System 26th National Conference on Artificial Intelligence AAAI Archived from the original on 2020 11 09 Retrieved 2015 07 11 a b Harabor Daniel Grastien Alban Improving Jump Point Search PDF Australian National University College of Engineering and Computer Science Association for the Advancement of Artificial Intelligence www aaai org Retrieved 11 July 2015 Adi Botea Martin Muller 2004 Near Optimal Hierarchical Path Finding PDF University of Alberta University of Alberta Retrieved from https en wikipedia org w index php title Jump point search amp oldid 1199084044, wikipedia, wiki, book, books, library,
