Frontier-Based RTDP: A New Approach to Solving the Robotic Adversarial Coverage Problem
Roi Yehoshua, Noa Agmon, Gal A. Kaminka · 2015
Area coverage is an important problem in robotics, where one or more robots are required to visit all points in a given area. In this paper we consider a recently introduced version of the problem, adversarial coverage, in which the cover-ing robot operates in an environment that contains threats that might stop it. The objective is to cover the target area as quickly as possible, while minimizing the probability that the robot will be stopped before completing the cov-erage. We first model this problem as a Markov Decision Process (MDP), and show that finding an optimal policy of the MDP also provides an optimal solution to this prob-lem. Since the state space of the MDP is exponential in the size of the target area’s map, we use real-time dynamic pro-gramming (RTDP), a well-known heuristic search algorithm for solving MDPs with large state spaces. Although RTDP achieves faster convergence than value iteration on this prob-lem, practically it cannot handle maps with sizes larger than 7 × 7. Hence, we introduce the use of frontiers, states that separate the covered regions in the search space from those uncovered, into RTDP. Frontier-Based RTDP (FBRTDP) converges orders of magnitude faster than RTDP, and ob-tains significant improvement over the state-of-the-art solu-tion for the adversarial coverage problem.