Anytime Safe Interval Path Planning for Dynamic Environments

Abstract

Path planning in dynamic environments is significantly more difficult than navigation in static spaces due to the increased dimensionality of the problem, as well as the importance of returning good paths under time constraints. Anytime planners are ideal for these types of problems as they find an initial solution quickly and then improve it as time allows. In this paper, we develop an anytime planner that builds off of Safe Interval Path Planning (SIPP), which is a fast A*-variant for planning in dynamic environments that uses intervals instead of timesteps to represent the time dimension of the problem. In addition, we introduce an optional time-horizon after which the planner drops time as a dimension. On the theoretical side, we show that in the absence of time-horizon our planner can provide guarantees on completeness as well as bounds on the sub-optimality of the solution with respect to the original space-time graph. We also provide simulation experiments for planning for a UAV among 50 dynamic obstacles, where we can provide safe paths for the next 15 seconds of execution within 0.05 seconds. Our results provide a strong evidence for our planner working under realtime constraints.