Path planning for a UAV with kinematic constraints in the presence of polygonal obstacles

Abstract

We present a two step path planning algorithm for unmanned aerial vehicles (UAVs) with kinematic constraints in the presence of polygonal obstacles. We use a visibility graph representation for the environment and a Dubins vehicle approximation to model UAV kinematics. A modified Dijkstra's shortest path algorithm is developed as first step of our approach to plan paths for a UAV. The algorithm in step one takes polynomial time in the number of obstacle vertices in the visibility graph. The second step performs a reverse search on the graph to find feasible paths and uses results of the first step as priors to speed up the search. We present simulation results to substantiate the claims.