Indoor Pursuit-Evasion with Hybrid Hierarchical Partially Observable Markov Decision Processes for Multi-Robot Systems

Abstract

In this paper, we examine a pursuit-evasion problem where more than one pursuer may search for one evader in indoor environments. Partially Observable Markov Decision Processes (POMDPs) provide a framework to model the uncertainty arisen from the unknown location of the evader. However, the approach is intractable even with a single pursuer and an evader. Therefore, we propose a Hybrid Hierarchical POMDP structure for improved scalability and efficiency. The structure consists of (i) the base MDPs for the cases where the evader is visible to the pursuers, (ii) the abstract POMDPs for the evader states that are not directly observable, and (iii) the transition states bridging between the base MDPs and abstract POMDPs. This hybrid approach significantly reduces the number of states expanded in the policy tree to solve the problem by abstracting environment structures. Experimental results show that our method expands only 5% of nodes generated from a standard POMDP solution.