Acceleration of Heuristic Motion Planning for Unmanned Aerial Vehicles

In this paper, we propose a heuristic-based fast motion planning framework which can be readily incorporated by the
on-board path planner of Unmanned Aerial Vehicles (UAVs) to generate safe and efficient trajectories while traversing
through challenging environments cluttered with obstacles. The proposed planning technique is effective for the
scenarios where the exact obstacle locations need to be detected during flight and the obstacle detection range is limited
by degraded environmental conditions like fog. Unlike many kinematic based planning strategies, the generated
planned trajectories can be tracked effectively as they preserve the dynamics of the UAV. The planning problem is
graphically represented by discretizing input and state spaces to facilitate usage of discrete search algorithms. We
also propose a heuristic calculation strategy based on dynamics relaxation to accurately encode the obstacle. The
Bellman optimality condition is used to modify the heuristic to facilitate faster search. This faster planning contributes
to requiring a reduced minimum obstacle detection range for receding horizon planning. The proposed algorithm has
been compared against an off-the-shelf nonlinear program solver and the proposed method produced superior planning
times and feasible trajectories avoiding collisions. Further, we analyzed the sub-optimality of the planned trajectories
and the minimum obstacle detection range required for the receding horizon planning framework.