A PARTITIONING SCHEME FOR HIERARCHICAL PATH FINDING ROBUST TO LINK COST UPDATE
Kyu-Yeong Kim · 1998
this paper proposes a partitioning scheme that isolates dynamic links from static ones. This scheme is a tradeoff between update cost and path finding time. This tradeoff is viable if a large portion of a graph is static. This condition holds for typical real-world road maps, where real-time traffic information is collected only for major roads. INTRODUCTION