Dominance regions in the Homicidal Chauffeur Problem

This paper studies pursuit-evasion games that feature two players moving in the plane, where one is a pursuer and the other is an evader. The goal of the pursuer is to capture the evader, which requires the distance between the pursuer and the evader to become smaller than a prescribed constant. The goal of the evader is to avoid capture. Specifically, this paper focuses on the Homicidal Chauffeur problem, where the pursuer has a speed advantage, but the evader has a maneuverability advantage. The key achievement of this paper is that it analyzes the game using dominance regions, where a point in the environment is said to be dominated by the evader if the evader can reach the point without being captured, regardless of the actions of the pursuer. This analysis method has recently been applied to games with obstacles and games with uncertain measurements, but in those cases the players all move with simple motion, where they are able to turn instantaneously. Dominance regions have not been applied to the Homicidal Chauffeur problem in the existing literature. One benefit of this approach is that the optimal strategies follow from the construction of the dominance regions.