Fast Subset Path Planning/Replanning to Avoid Obstacles with Time-Varying Probabilistic Motion Patterns

摘要

Many efficient path planners have been invented for finding paths while avoiding obstacles in a dynamic environment. However, most global path planning methods focus on problems where the knowledge of the environment is deterministic or that the states of the environment are stationary over time. This paper aims to introduce a path planning method to avoid obstacles which have a probabilistic moving pattern. Such approach can find its wide use in planning applications for unmanned aerial vehicles (UAVs), which not only have to avoid no-fly zones delimited by the airspace, but also zones of hazardous weather conditions such as turbulences and clouds, which move over time. First a spatiotemporal state space is defined to provide a formal representation of the time-varying search problem. The benefit of a spatiotemporal state space for the path planning of a vehicle moving in a time-varying vector field is also highlighted. Then a linear probabilistic movement model based on Gaussian distribution is proposed to estimate the probability of a state being occupied by obstacles. This probability is subsequently used to compute the travel cost in a discrete shortest path search. Finally, a fast subset path planning/replanning method is introduced. The planning method consists of performing the search on a selected subset of the state-space to reduce computation runtime. By adapting the subset of the state space, the efficiency of the search can be greatly increased and hence a fast global replanning is possible. An efficient replanning is necessary since the UAV cannot remain stationary while waiting for a new path planned.