AI planners solve classic Cops and Robbers graph theory problem

The classic Cops and Robbers problem asks: given k cops on an undirected graph, can they guarantee capture of a moving robber? This paper from Connor Little, Meagan Mann, Erin Meger, and Christian Muise frames the question as an AI planning task. Instead of traditional graph-theoretic proofs, they cast cop movements as non-deterministic actions (to cover all possible strategies) and robber movements as deterministic. Using off-the-shelf planners, they can automatically determine if a graph is k-copwin.

The approach opens doors for computational verification of graph properties that were previously only analyzed mathematically. The authors incorporate known variations (e.g., distance constraints, active/passive cops) and demonstrate that modern planners can handle the complexity. This work sits at the intersection of AI and game theory, showing how planning algorithms can solve combinatorial problems beyond typical robotics or logistics domains.