Towards Time-Optimal Any-Angle Path Planning With Dynamic Obstacles
  Path finding is a well-studied problem in AI, which is often framed as graph
search. Any-angle path finding is a technique that augments the initial graph
with additional edges to build shorter paths to the goal. Indeed, optimal
algorithms for any-angle path finding in static environments exist. However,
when dynamic obstacles are present and time is the objective to be minimized,
these algorithms can no longer guarantee optimality. In this work, we elaborate
on why this is the case and what techniques can be used to solve the problem
optimally. We present two algorithms, grounded in the same idea, that can
obtain provably optimal solutions to the considered problem. One of them is a
naive algorithm and the other one is much more involved. We conduct a thorough
empirical evaluation showing that, in certain setups, the latter algorithm
might be as fast as the previously-known greedy non-optimal solver while
providing solutions of better quality. In some (rare) cases, the difference in
cost is up to 76%, while on average it is lower than one percent (the same cost
difference is typically observed between optimal and greedy any-angle solvers
in static environments).
