A model-based cell decomposition approach to on-line pursuit-evasion path planning and the video game Ms. Pac-Man

Abstract

This paper presents an on-line approach for optimizing paths for a pursuit-evasion problem, in which an agent must visit several target positions within an environment while simultaneously avoiding one or more actively-pursuing adversaries. This problem is found in a variety of fields, such as robotic path planning, mobile-sensor applications, and path exposure. The methodology developed utilizes cell decomposition to construct a modified decision tree, which balances the reward associated with visiting target locations and the risk of capture by the adversaries. By computing paths on-line, the algorithm can quickly adapt to unexpected adversary behaviors and dynamic environments. The methodology developed in this paper is implemented as a controller for an artificial player in the Ms. Pac-Man arcade games and is entered into the IEEE CIG 2012 screen capture Ms. Pac-Man competition. The approach presented achieved a high score of 44,630 points.