Project "Preprocessing-Based Path-Planning Algorithms"
(scroll down for publications)

Path planning on graphs has many applications in video games, robotics, and navigation systems. Preprocessing-based path-planning (PBPP) algorithms first analyze a given graph in a preprocessing phase to generate auxiliary information which can then be used to significantly speed-up online shortest-path queries. The performance of these algorithms can be characterized by their runtime/memory trade-off, as it is often possible to achieve shorter runtimes by using more memory. A number of competitions have been held to evaluate PBPP (and other) algorithms, including a DIMACS Implementation Challenge and the Grid-Based Path-Planning Competition. One example of PBPP algorithms is contraction hierarchies and our closely-related (N-level) subgoal graphs, that essentially reinvented a similar concept with its own advantages and disadvantages. We now study what their properties and relationship are, how to combine their features, and how to develop even better PBPP algorithms. Another example of PBPP algorithms is FastMap, that embeds a given non-negative edge-weighted undirected graph in a Euclidean space and approximately preserves the pairwise shortest path distances between vertices. We now study applications of FastMap to heuristic search in a variety of domains, such as path finding and networking. For example, the Euclidean space can be used either for heuristic guidance of A* or for geometric interpretations that facilitate the application of techniques from analytical geometry.

Code

Representative Publications on Subgoal Graphs

Representative Publications on FastMap

Many publishers do not want authors to make their papers available electronically after the papers have been published. Please use the electronic versions provided here only if hardcopies are not yet available. If you have comments on any of these papers, please send me an email! Also, please send me your papers if we have common interests.

This page was automatically created by a bibliography maintenance system that was developed as part of an undergraduate research project, advised by Sven Koenig.


Home Page of Sven Koenig