Student research opportunities
Optimal Compressed Path Databases for Ultra Fast Path Finding in Maps
Project Code: CECS_872
This project is available at the following levels:
Honours, Summer Scholar
Please note that this project is only for undergraduate students.
Keywords:
Path finding
Supervisor:
Dr Alban GrastienOutline:
Compressed-Path Databases (CPD) have been introduced recently for path finding in maps and grids. The idea is to compute the first move table for each pair of points in the map <s,t>: the table indicates what is the first step from s to t. After this first step, the algorithm iteratively searches for the second step, until the complete path has been recovered.
Because this table can be huge (potentially 1012 entries, it needs to be compressed. The method used in CPD is based on the symmetries that can be found in the table: for a given point s, if all the points t1,...,tk that belong to a rectangle share the same first move deicison, then the entries <s,ti> are replaced by the rectangle. Such rectangles can contains thousands of points, hence the compactness of the CPD.
The number of rectangles is important both for the compactness of the CPD (which can still be in the order of Gigabytes) and the quickness of the path finder. An algorithm has been proposed to compute the rectangles. The goal of this project however is to find a better decomposition of the map into rectangle.
Goals of this project
The student will be asked to explore the following three directions:
- determine how far from the optimal solution the current algorithm is
- improve the current algorithm (possibly propose an optimal algorithm
- explore a redirection approach (for instance, to reach ``NICTA'', follow the same path as ``The ANU''
Background Literature
Adi Botea. 2011. Ultra-fast Optimal Pathfinding without Runtime Search. Proceedings of the Conference on AI and Interactive Digital Entertainment (AIIDE-11). Palo Alto, California, USA. http://abotea.rsise.anu.edu.au/data/botea-aiide11.pdf
