MDP models for task allocation in persistent robotic security service

Abstract

We develop a generic MDP model for task allocation in persistent UAV security service that incorporates random customer arrivals and task durations. Due to the fuel limitation of UAVs, the hand off of tasks from one vehicle to another is required. Since the state space is prohibitively large and the transition probability matrix is sparse, we created efficient methods to represent meaningful states and transitions. For small problems, the MDP can be solved via value iteration. We developed a greedy task assignment heuristic (GDH) and a simplified MDP based heuristic (MDH). For small example problems, numerical studies demonstrate that while GDH is about 22% suboptimal, MDH is about 3% suboptimal.