Student research opportunities
Generalised Jump Point Search
Project Code: CECS_1170
This project is available at the following levels:
Summer Scholar
Please note that this project is only for undergraduate students.
Keywords:
Pathfinding Jump point search Graph search
Supervisor:
Dr Alban GrastienOutline:
Path-finding is the problem of finding the shortest path
between a given origin and a given target in a graph.
Fast path-finding is important in many applications,
in particular when many requests are made
(e.g., in video games).
In 2011 a new approach was proposed for a specific type of graphs,
in namely uniform-cost 8-connected grids.
This approach, dubbed jump point search (JPS),
enjoys very good performance
but is only applicable for the grids mentioned above.
Its performance are even further improved with a very light pre-processing.
JPS works by determining early that most moves in the graph
are only necessary for certain (local) targets.
Removing these moves allows to ``jump'' quickly in the graph during the search.
The goal of this project is to apply a generalised version
of jump point search with pre-processing to any graph.
This generalisation would consist in identifying the local moves
to allow for quick jump in the search graph.
Requirements/Prerequisites
This project requires reasonable programming skills.
Background Literature
[1] Daniel Harabor and Alban Grastien. Online graph pruning for pathfinding on grid maps. In Conference on Artificial Intelligence (AAAI-11), 2011.
[2] Daniel Harabor and Alban Grastien. Improving jump point search. In International Conference on Automated Planning and Scheduling (ICAPS-14), pages 128-135, 2014.
