Multi-UAV motion planning for guaranteed search
Andreas Kolling, Alexander Kleiner · 2013
We consider the problem of detecting all moving and evading tar-gets in 2.5D environments with teams of UAVs. Targets are as-sumed to be fast and omniscient while UAVs are only equipped with limited range detection sensors and have no prior knowledge about the location of targets. We present an algorithm that, given an elevation map of the environment, computes synchronized tra-jectories for the UAVs to guarantee the detection of all targets. The approach is based on coordinating the motion of multiple UAVs on sweep lines to clear the environment from contamination, which represents the possibility of an undetected target being located in an area. The goal is to compute trajectories that minimize the number of UAVs needed to execute the guaranteed search. This is achieved by converting 2D strategies, computed for a polygonal representa-tion of the environment, to 2.5D strategies. We present methods for this conversion and consider cost of motion and visibility con-straints. Experimental results demonstrate feasibility and scalabil-ity of the approach. Experiments are carried out on real and artifi-cial elevation maps and provide the basis for future deployments of large teams of real UAVs for guaranteed search.