# 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