Any-time path-planning: Time-varying wind field + moving obstacles

Abstract

We consider the problem of real-time path-planning in a spatiotemporally varying wind-field with moving obstacles. We are provided with changing wind and obstacle predictions along a (D + 1)-dimensional space-time lattice. We present an Any-Time algorithm that quickly finds an αβ-suboptimal solution (a path that is not longer than αβ times the optimal time-length), and then improves α and β while planning time remains or until new wind/obstacle predictions trigger a restart. The factor α comes from an α-overestimate of the A*-like cost heuristic. β is proportional to motion modeling error. Any-Time performance is achieved by: (1) improving the connectivity model of the environment from a discrete graph to a continuous cost-field (decreasing β); (2) using the established method of incrementally deflating α. Our method was deployed as the global planner on a fixed-wing unmanned aircraft system that uses Doppler radar and atmospheric models for online real-time wind sensing and prediction. We compare its performance vs. other state-of-the-art methods in simulated environments.