Redirection for Pathfinding based on Compressed Path Database

Research areas

Description

* Background

Pathfinding is the problem of finding the shortest path in a directed weighted graph between two vertices.
There exist many algorithms to solve pathfinding problems,
that differ on their requirement (online memory, offiline memory, computation time, etc.).
In this project we concentrate on a method called Compressed Path Database (CPD).

A path database is a map that associates any pair of vertices with the first edge
of the optimal path between these two vertices.
Given such a database path finding is very easy:
use the path database to compute the first edge;
extract the new location;
check whether the target has been reached and stop if so;
recursively search for the optimal path from the current location to the target.

THe path database is an n*n matrix, which is too large to be stored explicitly.
It is possible however to compress this table to make it fit into memory.
Compression techniques won't be explained in this project description
(cf. references below)
but it should be obvious that given a source vertex,
the collection of targets that can be reached
optimally from this vertex through a given edge
can be easily represented without enumerating all these targets
(for instance, in a 2D graph, large portion of the map shsare the same edge).

* Project

The purpose of this project is to add a layer to the CPD algorithm
that allows to reduce the sizez of the CPD.
The expected benefits are multiple:
+ we expect that the size of the (best) CPD will be smaller;
+ we expect that finding a good CPD will be easier;
+ we expect that the reduced size of the CPD will accelerate the CPD algorithm.

Practically we want to introduce the notion of ``redirection''.
A redirection is an indication that the first move on the optimal path
from a given source to a given target
is the same as the first move on the optimal path
from this source to another target
(we redirect the first target to the second target).
This is similar to a road sign
that says ``To go to Canberra, follow Yass.''

The redirection will be defined as a list of triples (t1,t2,x)
that read ``If the problem is to find the shortest path
to t1 and if the current location is at a distance of x or more
(in a straight-line distance)
then the first move is identical to the first move
of the shortest path to t2''.

The project will consist in:
+ finding and implementing fast methods that find ``good'' redirections;
+ testing the impact of the redirection on the time required
  to compute a good CPD;
+ testing the impact of the redirection on the size of the CPD;
+ testing the impact of the redirection on the path-finding algorithm.  

 

Background Literature

* Adi Botea. Ultra-fast optimal pathfinding without runtime search. In AI and Interactive Digital Entertainment Conference (AIIDE-11), pages 122-127, 2011.

* Ben Strasser, Adi Botea, and Daniel Harabor. Compressing optimal paths with run length encoding. Journal of Artificial Intelligence Research (JAIR), 54:593-629, 2015.

Keywords

Path-finding

Updated:  1 November 2018/Responsible Officer:  Dean, CECS/Page Contact:  CECS Marketing