2

Yes, D*-lite is a directed graph algorithm, so it works fine with asymmetric edge weights by definition. However, note that the heuristic being admissible is not sufficient. According to the paper, it must be consistent. Based on what you described, I would guess Euclidean distance would be consistent for your graph, but we can't know for sure without ...


2

I will outline two solutions. Both have the same asymptotic worst-case running time, namely $O(B \cdot |E| \cdot \log (B\cdot |V|))$, but the second might be slightly more efficient in practice. Increase the size of the graph Create a new graph $G'$ where edges have only lengths, not costs. Each vertex is of the form $\langle v,b \rangle$ where $v \in V$ ...


Only top voted, non community-wiki answers of a minimum length are eligible