Reduced State Value Iteration for Multi-Drone Persistent Surveillance with Charging Constraints

Abstract

This paper presents Reduced State Value Iteration (RSVI), an algorithm to compute policies for Markov Decision Processes (MDPs) that have natural checkpoints, allowing for a solution based on a reduced state space. The algorithm is applied to find policies for multiple drones to persistently surveil an environment subject to charging constraints. RSVI leverages the structure of the true MDP to build an MDP with a smaller state-action space. Monte Carlo simulations are used to estimate transitions between the states in the reduced MDP, which are used in value iteration to compute a policy for the reduced MDP. States in the true MDP are mapped to reduced states. Actions in the reduced space from the policy are then mapped to actions in the full space for execution on the true MDP. Performance of the RSVI policy improves as the state discretization becomes finer, but with increasing computational requirements, thus giving a natural trade-off between computational resources and policy suboptimality. Results of simulated persistent surveillance experiments show that our RSVI policy outperforms a baseline heuristic.