Jump point search

From Wikipedia, the free encyclopedia
Jump to: navigation, search

In computer science, Jump Point Search (JPS) is an optimization to the A* search algorithm pathfinding 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[edit]

Harabor and Grastien's original publication provides algorithms for neighbour pruning and identifying successors.[1] The original algorithm for neighbour 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 minimise online search times.

A number of further optimisations 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[edit]

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]

References[edit]

  1. ^ a b c D. Harabor; A. Grastien (2011). Online Graph Pruning for Pathfinding on Grid Maps (PDF). 25th National Conference on Artificial Intelligence. AAAI. 
  2. ^ Witmer, Nathan (5 May 2013). "Jump Point Search Explained". zerowidth positive lookahead. Retrieved 9 March 2014. 
  3. ^ D. Harabor; A. Grastien (2012). The JPS Pathfinding System. 26th National Conference on Artificial Intelligence. AAAI. 
  4. ^ 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 Arti- ficial Intelligence (www.aaai.org). Retrieved 11 July 2015. 
  5. ^ Adi Botea; Martin Muller (2004). "Near Optimal Hierarchical Path-Finding" (PDF). University of Alberta. University of Alberta.