Research Training Group 1194 "Self-organizing Sensor-Actuator-Networks"
search
Research Training Group 1194 "Self-organizing Sensor-Actuator-Networks"
Research Training Group 1194 "Self-organizing Sensor-Actuator-Networks"
Mainpage
Members

Heuristic Contraction Hierarchies with Approximation Guarantee

  • Name:

    Symposium on Combinatorial Search (SoCS 2010)

  • Venue:

    Stone Mountain, Atlanta, Georgia, USA

  • Date:

    July 2010

  • Author:

    R. Geisberger, D. Schieferdecker

  • Speaker:

    Robert Geisberger

  • Abstract

    We present a new heuristic point-to-point shortest paths algorithm based on contraction hierarchies (CH). Given an epsilon > 0, we can prove that the length of the path computed by our algorithm is at most (1 + epsilon) times the length of the optimal (shortest) path. Exact CH is based on node contraction: removing nodes from a network and adding shortcuts to preserve shortest path distances. Our heuristic CH tries to avoid shortcuts even when a replacement path is epsilon times longer. However, we cannot avoid all such shortcuts, as we need to ensure that errors do not stack. Combinations with goal-directed techniques bring further speed-ups.