Modified A-Star (A*) Approach to Plan the Motion of a Quadrotor UAV in Three-Dimensional Obstacle-Cluttered Environment

Abstract

Motion-planning algorithms play a vital role in attaining various levels of autonomy for any ground or flying agent. Three-dimensional (3D) motion-planning is interesting, but rather complex, especially for flying agents such as autonomous unmanned aerial vehicles (UAVs), due to the increased dimensionality of space and consideration of dynamical constraints for a feasible trajectory. Usually, in 3D path search problems, it is hard to avoid extra expanded nodes due to increased dimensionality with various available search options. Therefore, this paper discusses and implements a modified heuristic-based A* formalism that uses a truncation mechanism in order to eradicate the mentioned problem. In this formalism, the complete motion planning is divided into shortest path search problem and smooth trajectory generation. The shortest path search problem is subdivided into an initial naïve guess of the path and the truncation of the extra nodes. To find a naïve shortest path, a conventional two-dimensional (2D) A* algorithm is augmented for 3D space with six-sided search. This approach led to the inclusion of extra expanded nodes and, therefore, it is not the shortest one. Hence, a truncation algorithm is developed to further process this path in order to truncate the extra expanded nodes and then to shorten the path length. This new approach significantly reduces the path length and renders only those nodes that are obstacle-free. The latter is ensured using a collision detection algorithm during the truncation process. Subsequently, the nodes of this shortened path are used to generate a dynamically feasible and optimal trajectory for the quadrotor UAV. Optimal trajectory generation requires that the plant dynamics must be differentially flat. Therefore, the corresponding proof is presented to ensure generation of the optimal trajectory. This optimal trajectory minimizes the control effort and ensures longer endurance. Moreover, quadrotor model and controllers are derived as preliminaries, which are subsequently used to track the desired trajectory generated by the trajectory planner. Finally, results of numerical simulations which ultimately validate the theoretical developments are presented.

Keywords

• heuristic search
• 3D A-star search
• quadrotor
• UAV
• motion planning
• trajectory generation