Student research opportunities
Improvements on compressed path database
Project Code: CECS_1144
This project is available at the following levels:
Summer Scholar
Please note that this project is only for undergraduate students.
Keywords:
Path-finding, navigation, CPD
Supervisor:
Dr Alban GrastienOutline:
Finding the shortest path between two points in a map is a
well-studied problem that has many concrete applications.
First move database (FMD) are preprocessed data structure that stores,
for each pair of points, the first move for the optimal path from the
first point to the second. The optimal path, if necessary, can be
easy extracted with a linear number of calls to the database. For
realistic maps, i.e., maps with millions of points, a naive
representation of the FMD will fail. Enters the compressed path
database (CPD), a technique to represent the FMD compactly.
The purpose of the present project is to enhance the existing CPD
technique by reducing its size and, hopefully as a consequence,
improving its access time performance. One of the main ideas will be
to use a redirect technique, similar to one found on the road network
when a sign says: ``To go to X, follow the direction Y.'' Another
idea will be to study and estimate how far from optimal the existing
compacting techniques are. The student will also be encourage to
implement her/his own ideas.
Requirements/Prerequisites
Solid programming skills
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
