Physical Orienteering Problem for Unmanned Aerial Vehicle Data Collection Planning in Environments With Obstacles

This letter concerns a variant of the orienteering problem (OP) that arises from multi-goal data collection scenarios where a robot with a limited travel budget is requested to visit given target locations in an environment with obstacles. We call the introduced OP variant the physical OP (POP). The POP sets out to determine a feasible, collision-free, path that maximizes collected reward from a subset of the target locations and does not exceed the given travel budget. The problem combines motion planning and combinatorial optimization to visit multiple target locations. The proposed solution to the POP is based on the variable neighborhood search (VNS) method combined with the asymptotically optimal sampling-based probabilistic road map (PRM*) method. The VNS-PRM*. uses initial low-dense roadmap that is continuously expanded during the VNS-based POP optimization to shorten paths of the promising solutions and, thus, allows maximizing the sum of the collected rewards. The computational results support the feasibility of the proposed approach by a fast determination of high-quality solutions. Moreover, an experimental verification demonstrates the applicability of the proposed VNS-PRM* approach for data collection planning for an unmanned aerial vehicle in an urban-like environment with obstacles.