Jump Point Search
Jump Point Search (JPS) is a recent algorithm for improving path planning on uniform cost grids. Our recent work breaks down JPS into several pieces that can be applied or modified independently. Understanding these pieces will help understand the performance of JPS as a whole. Read our paper above for the full details; the videos below illustrate these differences. You can also check out the talk slides and the poster. (The videos below were part of the talk, but don't show up in the slides.)
A* Example First, watch A* solve a sample problem. The red states are on the closed list and the green states are on open. Notice that there is a thick border of green states around the red states. On these grids A* generates 8 neighbors for every state visited.
Canonical A* Example
The first component of JPS is a canonical ordering. This is a partial ordering over optimal paths. In cases where there are many optimal paths (the number can grow exponentially), a canonical ordering reduces this significantly, often only generating a single optimal path. This example runs A* with the canonical ordering. The canonical ordering is in light gray in the background. If you compare to A*, Canonical A* puts far fewer states onto the open list. (States in green).
JPS Example
In addition to the canonical ordering, JPS jumps over many states and does not put them into the open list. The only states that JPS puts on the open list are the start, the goal, and jump points. In simple terms, jump points are points at the corners of obstacles. These are places where the canonical ordering has to be reset to reach all states in the state space. While JPS expands far fewer nodes, note that it generates states that A* does not. This because it follows the canonical ordering to the edge of the map while looking for jump points.
Bounded JPS Example (BJPS) In practice JPS can generate far too many states to be effective. This partially depends on how open the map is. So, instead of jumping all of the way to a jump point, BJPS limits how far it can jump. Once this limit is reached, states are placed into the open list. Depending on the jump limit, BJPS interpolates between CA* (limit=0) and JPS (limit=∞). This reduces the number of nodes generated, but increases the number of nodes expanded.
You can download all the movies or
you can download the movie frames for personal or non-commercial use.