Path-planning with waiting in spatiotemporally-varying threat fields.

We address the problem of finding an optimal path for a vehicle in a planar environment where traversal costs are based on a time-varying spatial field defined over the environment. The resulting optimal path may contain instances of waiting, where the vehicle hovers, parks, or loiters. First, we consider path-planning on a uniform grid over the workspace. It is known that the computational complexity of the problem is significantly higher when waiting is allowed. We study the trade-off between the increased computational complexity and potential cost reductions in the resultant path with allowance for waiting. The results of numerical studies in this work identify characteristics of the threat fields in which optimal paths can involve waiting. Furthermore, we provide a local condition on the threat field that precludes waiting from providing any cost reductions in the resultant path. We show that this condition can be used in the path-planning algorithm to prune search trees and provide significant reductions in computation time without significant suboptimality. Next, we consider path-planning on a vehicle-centric multiresolution grid. We use a wavelet-based multiresolution decomposition to evaluate the multiresolution path planner and compare against the uniform resolution grid using the same family of threat fields. We show that with a vehicle-centric multiresolution map and an appropriate path-planning algorithm, the added computational effort of allowance for waiting is negligible. [ABSTRACT FROM AUTHOR]