Multi-UAV path planning in obstacle rich environments using Rapidly-exploring Random Trees

This paper presents path planning algorithms using Rapidly-exploring Random Trees (RRTs) to generate paths for multiple unmanned air vehicles (UAVs) in real time, from given starting locations to goal locations in the presence of static, pop-up and dynamic obstacles. Generating non-conflicting paths in obstacle rich environments for a group of UAVs within a given short time window is a challenging task. The difficulty further increases because the turn radius constraints of the UAVs have to be comparable with the corridors where they intend to fly. Hence we first generate a path quickly using RRT by taking the kinematic constraints of the UAVs into account. Then in order to generate a low cost path we develop an anytime algorithm that yields paths whose quality improves as flight proceeds. When the UAV detects a dynamic obstacle, the path planner avoids it based on a set of criteria. In order to track generated paths, a guidance law based on pursuit and line-of-sight is developed. Simulation studies are carried out to show the performance of the proposed algorithm.