  Stochastic patrol routing is known to be advantageous in adversarial
settings; however, the optimal choice of stochastic routing strategy is
dependent on a model of the adversary. We adopt a worst-case omniscient
adversary model from the literature and extend the formulation to accommodate
heterogeneous defenses at the various nodes of the graph. Introducing this
heterogeneity leads to interesting new patrol strategies. We identify efficient
methods for computing these strategies in certain classes of graphs. We assess
the effectiveness of these strategies via comparison to an upper bound on the
value of the game. Finally, we leverage the heterogeneous defense formulation
to develop novel defense placement algorithms that complement the patrol
strategies.
