Jump Point Search (JPS) is an algorithm we designed with Daniel Harabor. It was initially introduced for uniform cost 8-connected grids, but current work is aiming at generalising those results. Daniel gave a pretty good description of JPS at this address.
JPS relies on the idea that moving North West (NW) and then North (N) is generally the same as moving N and then NW. Based on this idea, we prune the successors so that, in many instances, a node has only one successor. We then explore that successor immediately, until a node is reached where we have several successors (in which case, we start at this node, and this is called a jump) or a node with no successor is reached (dead-end). These second case is quite important, because the remaining nodes that have several successors are often such all but one of these successors have one successors; those successors are immediately explored and often lead to dead-end, which means that only one successor remains, which successor can be immediately explored.
JPS has been proved [1] to be quite efficient, as much as 40x faster than A*. JPS returns the optimal path. It requires no pre-processing, it has no memory overhead.
Extensions are under investigation. A pre-processed version has been proposed to identify the jump-points early. We have quite a few ideas to apply these results in other context.
JPS has received some positive feedback from the outside world. It received a 2012 Highly Commended Nasscom IT Innovation Student Award. Here is an example of the sort of specialised article we received. Some pretty cool videos are also available (also here). We entered the first grid path planning competition but, unfortunately, did not do as well as expected; it seems that the reason is that our entry was the only one to sit on top of the HOG platform. Well, that's how you learn
More recently, Steve Rabin started building stuff on top of JPS+. His extension, goal bounding, integrates quite well with it. Look at the video.
Additional link:
Compressed data bases (CPD) are an efficient way to represent the optimal from each point to each other point of a map. It has been developed by Adi Botea [B1]. I will not enter the details of this work but, essentially, the idea is to store, for each node and each target, the first move of the optimal path from the node to the target. Once this first move is known, the first move from the new node to the target can be requested again, and so on until the target is reached. The first move table can be quite large (in the worst-case, quadratic in the number of nodes) but, for a given node and a set of nearby targets, the first move is often the same, which enables powerful compressions.
My work in this field has so far been in the repair of the CPD in case the map is modified, i.e., if an edge is removed. Computing the CPD requires a lot of time (which is acceptable since it is done at pre-process time and it is computed only once); when the map is modified on-line, we want a new CPD quickly, possibly to the cost of optimality.
I have had two students so far, working on this topic. The first student is Harta Wijaya who did a summer project on the topic. The second student is Hao (Harry) Jiang who is doing a Honours project.
Besides the repair of CPD, there are a number of topics I would like to investigate, such as mixing CPD with JPS.