Towards Time-Optimal Any-Angle Path Planning With Dynamic Obstacles
This work addresses a critical limitation in path planning for dynamic environments, offering optimal algorithms that could benefit robotics and AI applications, though it builds incrementally on existing static any-angle methods.
The paper tackles the problem of finding time-optimal paths with dynamic obstacles in any-angle path planning, presenting two algorithms that provably achieve optimal solutions, with one algorithm matching the speed of a greedy non-optimal solver while improving solution quality by up to 76% in rare cases and less than 1% on average.
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).