<p>This paper presents a new online mission planning algorithm based on the Markov Decision Process (MDP) for multi-target reconnaissance missions of unmanned aerial vehicles (UAVs). Using a multiresolution approximation of the mission environment, the proposed algorithm offers the advantage of calculating the high-resolution path in the vicinity of the UAV while substantially reducing the overall problem size to improve computational performance for online mission planning. To this end, an MDP problem is mathematically formulated for the multi-target reconnaissance mission while taking into account the survival probability, the detection success probability, and the communication success probability to improve the situational awareness of the UAV. Based on the numerical simulation results using MATLAB, the proposed algorithm turns out to be more efficient in terms of computational throughput and memory requirements compared to the conventional matrix-based MDP algorithm. Furthermore, the optimality of the proposed MDP formulation has been validated by comparing performance metrics for detection probability, communication success probability, and survival probability. Finally, robustness has been demonstrated through Monte Carlo simulations for various mission conditions.</p>