GPS Denied UAV Routing with Communication Constraints

A novel GPS denied routing problem for UAVs is described, where the UAVs cooperatively navigate through a restricted zone deployed with noncommunicating Unattended Ground Sensors (UGS). The routing algorithm presenting in this paper ensures the UAVs maintain strict contact with at least one UGS, which allows the UGS act as beacons for relative navigation eliminating the need for dead reckoning. This problem is referred to as the Communication Constrained UAV Routing Problem (CCURP). Two architectures for cooperative navigation of two or three UAVs are considered. For the two UAV problem, a -approximation algorithm is developed. The three UAV problem is transformed into a one-in-a-set Traveling Salesman Problem (TSP), which is solved as a regular asymmetric TSP using existing methods after applying a second transformation. Computational results corroborating the performance bounds are presented.