Domain Design for the Cops and Robbers Problem
Connor Little, Meagan Mann, Erin Meger, Christian Muise
Abstract
Cops and Robbers is a well-studied problem in graph theory. The setting consists of a robber and one or more cops placed on an undirected graph. Taking turns moving throughout the graph, the cops try to capture the robber. The property of interest is whether $k$ cops suffice to ensure at least one cop occupies the same vertex as the robber, after a finite number of turns, given any configuration of their initial placement; if successful, the graph is referred to as ``$k$-copwin''. In this work, we cast the problem of determining whether a graph is $k$-copwin as a non-deterministic planning problem and use state-of-the-art planners to compute this property. The cop movement is cast as non-deterministic movement (to capture all possible strategies), while the robber movement is deterministic in nature. We also extend the base model using several variations from the graph theory literature.
Topics
Classified with taxonomy v2 on Sat, 5 Sept 2026.