Comparative Analysis of A* and Deep Q-Learning Algorithms for UAV Path Planning

Sammanfattning

The use of unmanned aerial vehicles (UAVs) has increased significantly in the last decades, with both military and commercial applications. Path planning is a crucial aspect of UAV operation, particularly in dynamic or unknown environments. This thesis investigates the performance of the A* path planning algorithm to approach the problem and compare it to a reinforcement learning approach, more specifically the Deep Q-Learning algorithm (DQL). The evaluation focuses on handling unseen environments, time complexity, and path optimality for both short-short range and long-range navigation. A simulation environment is developed using Gazebo and ROS2, featuring a quadrotor model equipped with a depth camera. An A* path planner with obstacle detection and a re-planning component is implemented for navigation in partially mapped environments. For the reinforcement learning approach a DQL path planner is designed, with two agents trained using slightly different reward functions and strategies to update the Q-values. The results indicate that the A* path planner performs better than the DQL-agents in all environments and for most of the evaluated criteria. The RL-planners have a tendency to get stuck behind obstacles and rarely reaches the target while the A* path planner successfully navigates to the goal point in all missions. The A* planner has an average step time 3-4 times higher than the RL-planners, although this includes overhead for map updates, which the RL-planners do not require. The RL-planner performs better in short-range navigation than long-range navigation but is outperformed by the A* path planner in both cases. Ultimately, a potential method for combining the two path planning approaches is proposed.