Multi-Scale LPA* with low worst-case complexity guarantees
Yibiao Lu, Xiaoming Sharon Huo, Oktay Arslan, Panagiotis Tsiotras · 2011 IEEE/RSJ International Conference on Intelligent Robots and Systems · 2011
In this paper we consider dynamic shortest path-planning problems on a graph with a single endpoint pair and with potentially changing edge weights over time. Several incremental algorithms exist in the literature that solve this problem, notably among them the Lifelong Planning A* (LPA*) algorithm. Although, in most cases, the LPA* algorithm requires a relatively small number of updates, in some other cases the amount of work required by the LPA* to find the optimal path can be overwhelming. To address this issue, in this paper we propose an extension of the baseline LPA* algorithm, by making efficient use of a multiscale representation of the environment.