Pac-Man is Overkill
Renato Fernando dos Santos, Ragesh K. Ramachandran, Marcos A. M. Vieira, Gaurav S. Sukhatme
Abstract
Pursuit-Evasion Game (PEG) consists of a team of pursuers trying to capture one or more evaders. PEG is important due to its application in surveillance, search and rescue, disaster robotics, boundary defense and so on. In general, PEG requires exponential time to compute the minimum number of pursuers to capture an evader. To mitigate this, we have designed a parallel optimal algorithm to minimize the capture time in PEG. Given a discrete topology, this algorithm also outputs the minimum number of pursuers to capture an evader. A classic example of PEG is the popular arcade game, Pac-Man. Although Pac-Man topology has almost 300 nodes, our algorithm can handle this. We show that Pac-Man is overkill, i.e., given the Pac-Man game topology, Pac-Man game contains more pursuers/ghosts (four) than it is necessary (two) to capture evader/Pac-man. We evaluate the proposed algorithm on many different topologies.
BibTeX
@inproceedings{iros2020_pacmanisoverkill,
title = {Pac-Man is Overkill},
author = {Renato Fernando dos Santos and Ragesh K. Ramachandran and Marcos A. M. Vieira and Gaurav S. Sukhatme},
booktitle = {IROS 2020},
year = {2020}
}