A cell decomposition approach to online evasive path planning and the video game Ms. Pac-Man

Journal Article

This paper presents an approach for optimizing paths online for a pursuit-evasion problem where an agent must visit several target positions within a region of interest while simultaneously avoiding one or more actively-pursuing adversaries. This is relevant to applications such as robotic path planning, mobile-sensor applications, and path exposure. The methodology described utilizes cell decomposition to construct a modified decision tree to achieve the objective of minimizing the risk of being caught by an adversary and maximizing a reward associated with visiting the target locations. By computing paths online, the algorithm can quickly adapt to unexpected movements by the adversaries or dynamic environments. The approach is illustrated through a modified version of the video game Ms. Pac-Man which is shown to be a benchmark example of the pursuit-evasion problem. The results show that the approach presented in this paper runs in real-time and outperforms several other methods as well as most human players. © 2011 IEEE.

Full Text

Duke Authors

Cited Authors

  • Foderaro, G; Raju, V; Ferrari, S

Published Date

  • 2011

Published In

  • IEEE International Symposium on Intelligent Control - Proceedings

Start / End Page

  • 191 - 197

Digital Object Identifier (DOI)

  • 10.1109/ISIC.2011.6045414