AAMAS Conference 2010 Conference Paper
ESP: Pursuit Evasion on Series-Parallel Graphs
- Kenny Daniel
- Richard Borie
- Sven Koenig
- Craig Tovey
We develop a heuristic approach, called ESP, that solves large pursuit-evasionproblems on series-parallel (that is, treewidth-2) graphs quickly and withsmall costs. It exploits their topology by performing dynamic programming ontheir decomposition graphs. We show that ESP scales up to much larger graphsthan a strawman approach based on previous results from the literature.