Optimizing Monitoring Utility of Uncrewed Aerial Vehicles Considering Adverse Effects

For Unmanned Aerial Vehicles (UAVs) monitoring tasks, capturing high quality images of target objects is important for subsequent recognition. Concerning the problem, many prior works study placement/trajectory planning for UAVs to maximize the quality of captured images. However, all of them overlook a fact that <i>UAV monitoring may cause a huge risk/annoyance on living objects.</i> In this paper, we investigate the novel problem of o<u>P</u>timizing uncrewed a<u>E</u>rial vehicles pl<u>A</u>cement by <u>C</u>onsidering both monitoring utility and adverse <u>E</u>ffects (PEACE). We propose an approach to solve PEACE, which is proved to be NP-hard. Overall, our approach achieves a <inline-formula><tex-math notation="LaTeX">$1- \frac{1}{e}-\varepsilon$</tex-math></inline-formula> approximation ratio. First, we approximate the original problem of PEACE as a classical problem of Monotone Submodular function Maximization under a Uniform Matroid constraint (MSMUM) with a controlled gap. Then, for MSMUM, we propose a combination of algorithms achieving a <inline-formula><tex-math notation="LaTeX">$1-\frac{1}{e}$</tex-math></inline-formula> approximation and <inline-formula><tex-math notation="LaTeX">$O(n\log n)$</tex-math></inline-formula> time complexity considering the correlation among the UAV monitoring strategies. The proposed algorithms outperform existing algorithms for MSMUM through theoretical analysis and experimental results. Extensive simulations and field experiments demonstrate the effectiveness of our approach, achieving performance gains of 9.0% to 1434.5% compared to existing methods.