Online Decision Making for UAVs via Receding Horizon MDP and POMDPs

When finding solutions for planning and decision making problems for uncrewed aerial vehicles (UAVs), the size of the state space quickly becomes complicated and large. This leads to problems that are difficult to solve, without a large amount of time and compute resources are made available. UAVs may not have access to the large amount of resources needed to create high quality solutions so, often, the policy is calculated offline. However, this means the policy cannot be adapted at runtime, leading to policies that may quickly become outdated in dynamic environments. We propose a method for solving Markov Decision Process (MDP) and Partially Observable MDP (POMDP) problems iteratively, online by using a receding horizon approach, where only a subset of the full state space is included and a locally optimal policy can be found. This policy then can be used to select the next action, and the policy can be recalculated at each step, resulting in a recursively optimal solution. We tested this approach on three different problems: a solar-supplemented drone (MDP), a rock sampling rover (POMDP) and a drone surveillance task (POMDP). The receding horizon approach was compared to traditional solving methods. While the receding horizon approach had more computational overhead in the MDP scenario, it decreased calculation time in the POMDP cases, while maintaining a recursively optimal policy in all cases. Importantly, the receding horizon approach was able to solve high-resolution and uncertain MDP and POMDP problems that could not be solved in a reasonable amount of time using traditional methods.